# Variant of discrete fourier transform that isolates phase delay?

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:

and this one:

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!
• 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 Jul 12 '11 at 5:52
• It should be mentioned that 2+D phase unwrapping is a hard problem.
– Emanuel Landeholm
Oct 1 '11 at 12:19
• Look up phase transform (PHAT) Jul 3 '12 at 16:52
• 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? Jul 3 '12 at 17:38
• It's a translation. I'll edit the question as it is confusing; I used the word "rotation" in the sense of bitwise rotation. Jul 11 '12 at 7:12

## 1 Answer

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.

• 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.) Jul 24 '12 at 19:39
• @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. Jul 24 '12 at 20:22