Abstract
Many problems in image/video processing and computer
vision require the computation of a dense k-nearest neighbor
field (k-NNF) between two images. For each patch in a query
image, the k-NNF determines the positions of the k most similar patches in a database image. With the introduction of
the PatchMatch algorithm, Barnes et al. demonstrated that
this large search problem can be approximated efficiently
by collaborative search methods that exploit the local coherency of image patches. After its introduction, several
variants of the original PatchMatch algorithm have been
proposed, some of them reducing the computational time by
two orders of magnitude. In this work we study the convergence of PatchMatch and its variants, and derive bounds on
their convergence rate. We consider a generic PatchMatch
algorithm from which most specific instances found in the
literature can be derived as particular cases. We also derive
more specific bounds for two of these particular cases: the
original PatchMatch and Coherency Sensitive Hashing. The
proposed bounds are validated by contrasting them to the
convergence observed in practice