6
$\begingroup$

I'm not quite sure of the mathematical terminology here but...

Is there a variant (or post-processing) of a Discrete Fourier Transform that separates the shape of a signal from any phase shift applied to the whole signal?

For example this image:
unrotated letter "A"
and this one:
letter "A" rotated 8 pixels right/3 pixels down
should differ in at most 2 coefficients (one for each dimension in which it is shifted) in the frequency domain.

Alternatively is there a way to index images so that any image can be found in a database given a translated copy as a key?

Notes

  1. My images are all 1D or 2D with power-of-two sizes (but not necessarily square.)
  2. This project has nothing to do with OCR (even though I used a character glyph in the example.) Please do not suggest OCR-specific algorithms/libraries!
|improve this question
$\endgroup$

migrated from stackoverflow.com Jul 24 '12 at 16:34

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ You should be able to do this by taking a normal FFT, calculating the phase for each bin (atan2(re, im)), then performing phase unwrapping. See e.g. ljmu.ac.uk/GERI/90202.htm and ccrma.stanford.edu/~jos/fp/Phase_Unwrapping.html $\endgroup$ – Paul R Jul 12 '11 at 5:52
  • $\begingroup$ It should be mentioned that 2+D phase unwrapping is a hard problem. $\endgroup$ – Emanuel Landeholm Oct 1 '11 at 12:19
  • $\begingroup$ Look up phase transform (PHAT) $\endgroup$ – Phonon Jul 3 '12 at 16:52
  • 1
    $\begingroup$ You may be able to use the DFT. A circular shift in the time/spatial domain like what you've shown will show up as a phase shift that varies linearly with frequency. Perhaps that is useful? $\endgroup$ – Jason R Jul 3 '12 at 17:38
  • $\begingroup$ It's a translation. I'll edit the question as it is confusing; I used the word "rotation" in the sense of bitwise rotation. $\endgroup$ – finnw Jul 11 '12 at 7:12
3
$\begingroup$

Since this is a comparison of a template image, to a spatially, (and circularly) translated variant of it, then the power spectra of both will remain the same, but the phase spectra will be different.

I believe in your example, the approach of a simple circular convolution between your image, and the template will be what you want. The result is also an image, and once you have that, you search for a peak. How much off in the vertical/horizontal direction that peak is from the a peak that you would have normally got had you circularly convolved the template with itself, will give you the spatial delay you have in both horizontal and vertical space respectively.

You can implement that by taking the (same size as images) Fourier transform of your template image, (first one), and multiplying it with the Fourier transform of your image, (second one), and then inverse Fourier transforming the result back into the spatial domain. Once there, you can look for the peak as mentioned in the first paragraph.

This is assuming your images are the same size, as you stated.

|improve this answer
$\endgroup$
  • $\begingroup$ If I understand correctly you are describing phase correlation. I will be doing this anyway. The problem is knowing which template to convolve with (without an exhaustive search.) $\endgroup$ – finnw Jul 24 '12 at 19:39
  • $\begingroup$ @finnw Yes and no - technically what I said is a circular convolution, and the phase correlation is, well, a correlation VS a convolution, but either method will work. $\endgroup$ – Spacey Jul 24 '12 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.