Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Say I have some two-dimensional black and white image, which we can represent as a set of coordinates $(c_1, ..., c_N) \in C$ for the placement of dark/black pixels on a bounded rectangular plane with dimensions $X \times Y$. Let $p_x \times p_y$ be the size of each rectangular pixel (feel free to assume $p_x \approx p_y$).

I wish to reconstruct this image by taking a series of photographs of the surface using a camera with the following properties:

  • The pixels of the camera are arrayed in a hexagonal lattice with spacing $s$ between nearest-neighbors. Alternatively, we can imagine a rectangular lattice with spacing $s_x$ between pixels along the $x$-axis and spacing $s_y$ between pixels along the $y$-axis. Here, $s = cp_x \approx cp_y$ for some constant $c>1$ (the same holds for $s_x$ and $s_y$ in the rectangular lattice case).

  • The total size of the lattice is proportional to the size of the plane we're attempting to image.

  • The "lens" of the camera is always oriented to point straight down (i.e. we never take shots at an angle), but for every image, the pixels on the lens are randomly rotated and translated with respect to the bounded plane. To apply some restriction to translational freedom, we can say that there must be at least one dark/black pixel in the field-of-view of the camera for a shot to be retained.

Under what conditions (perhaps with regard to camera pixel spacing relative to image pixel size) is it possible for me to recover the coordinates $c_i$ for the pixels in my image within some error $\epsilon$? How can I estimate the number of photographs (with random orientation and translation) necessary to accomplish this reconstruction?

Also, I was going to attempt a sort of simulated annealing approach with regards to the build-up, but are there known algorithms that might be applicable here?

(By the way, please feel free to remove the "compressed-sensing" tag, which may not be appropriate.)

share|improve this question
Have a look at: pages.cs.wisc.edu/~brecht/papers/… to see if their ideas apply to your case. –  Suvrit Jan 20 '13 at 8:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.