  Digital image inpainting is an interpolation problem, inferring the content
in the missing (unknown) region to agree with the known region data such that
the interpolated result fulfills some prior knowledge. Low-rank and nonlocal
self-similarity are two important priors for image inpainting. Based on the
nonlocal self-similarity assumption, an image is divided into overlapped square
target patches (submatrices) and the similar patches of any target patch are
reshaped as vectors and stacked into a patch matrix. Such a patch matrix
usually enjoys a property of low rank or approximately low rank, and its
missing entries are recoveried by low-rank matrix approximation (LRMA)
algorithms. Traditionally, $n$ nearest neighbor similar patches are searched
within a local window centered at a target patch. However, for an image with
missing lines, the generated patch matrix is prone to having entirely-missing
rows such that the downstream low-rank model fails to reconstruct it well. To
address this problem, we propose a region-wise matching (RwM) algorithm by
dividing the neighborhood of a target patch into multiple subregions and then
search the most similar one within each subregion. A non-convex weighted
low-rank decomposition (NC-WLRD) model for LRMA is also proposed to reconstruct
all degraded patch matrices grouped by the proposed RwM algorithm. We solve the
proposed NC-WLRD model by the alternating direction method of multipliers
(ADMM) and analyze the convergence in detail. Numerous experiments on line
inpainting (entire-row/column missing) demonstrate the superiority of our
method over other competitive inpainting algorithms. Unlike other
low-rank-based matrix completion methods and inpainting algorithms, the
proposed model NC-WLRD is also effective for removing random-valued impulse
noise and structural noise (stripes).
