Tight Approximation of Image Matching

Details Tight Approximation of Image Matching Tight Approximation of Image Matching

2011-11-07

arxiv.org/abs/1111.1713v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Tight Approximation of Image Matching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight Approximation of Image Matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight Approximation of Image Matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-693253