## Tight Approximation of Image Matching

by Simon Korman, Daniel Reichman, and Gilad Tsur

#### Oded's comments

My focus is on the constant query case that refers to smooth images.
In fact, it suffices that one of the images be smooth
(whereas the other can violate smoothness due to noise).
Also, the result scales (or generalizes) to weaker notions
(or measures) of smoothness.
The basic idea is that the difference in the error
between two transformations of an image is upper-bounded
by the product of its smoothness measure
and the distance between the transformations
(in an appropriate transformation space).
(For example, in case of shifting transformations,
the latter distance is the difference between the offset/shift.)
Hence, it suffices to examine a small number of possible
trasformations (which differ in more than we can tolerate
by the foregoing consideration).

#### The original abstract

In this work we consider the {\em image matching} problem for two grayscale
$n \times n$ images, $M_1$ and $M_2$ (where pixel values range from 0 to
1). Our goal is to find an affine transformation $T$ that maps pixels from
$M_1$ to pixels in $M_2$ so that the differences over pixels $p$ between
$M_1(p)$ and $M_2(T(p))$ is minimized. Our focus here is on sublinear
algorithms that give an approximate result for this problem, that is, we
wish to perform this task while querying as few pixels from both images as
possible, and give a transformation that comes close to minimizing the
difference.

We give an algorithm for the image matching problem that returns a
transformation $T$ which minimizes the sum of differences (normalized by
$n^2$) up to an additive error of $\epsilon$ and performs
$\tilde{O}(n/\epsilon^2)$ queries. We give a corresponding lower bound
of $\Omega(n)$ queries showing that this is the best possible result in the
general case (with respect to $n$ and up to low order terms).
In addition, we give a significantly better algorithm for a natural family
of images, namely, smooth images. We consider an image smooth when the
total difference between neighboring pixels is O(n). For such images we
provide an approximation of the distance between the images to within an
additive error of $\epsilon$ using a number of queries depending
polynomially on $1/\epsilon$ and not on $n$. To do this we first consider
the image matching problem for 2 and 3-dimensional {\em binary} images, and
then reduce the grayscale image matching problem to the 3-dimensional
binary case.

See arXiv:1111.1713.

Back to
list of Oded's choices.