  Blind image deblurring, i.e., deblurring without knowledge of the blur
kernel, is a highly ill-posed problem. The problem can be solved in two parts:
i) estimate a blur kernel from the blurry image, and ii) given estimated blur
kernel, de-convolve blurry input to restore the target image. In this paper, by
interpreting an image patch as a signal on a weighted graph, we first argue
that a skeleton image---a proxy that retains the strong gradients of the target
but smooths out the details---can be used to accurately estimate the blur
kernel and has a unique bi-modal edge weight distribution. We then design a
reweighted graph total variation (RGTV) prior that can efficiently promote
bi-modal edge weight distribution given a blurry patch. However, minimizing a
blind image deblurring objective with RGTV results in a non-convex
non-differentiable optimization problem. We propose a fast algorithm that
solves for the skeleton image and the blur kernel alternately. Finally with the
computed blur kernel, recent non-blind image deblurring algorithms can be
applied to restore the target image. Experimental results show that our
algorithm can robustly estimate the blur kernel with large kernel size, and the
reconstructed sharp image is competitive against the state-of-the-art methods.
