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

Hello all,

I'm interested in 2D discrete transforms (such as discrete wavelet transforms, Curvelets, Ridgelets, Beamlets etc.) that operate on a discrete unit disk and:

  1. Are invariant to rotations only
  2. Output a transformed signal with relatively low informational entropy
  3. Are computationally relatively efficient (in terms of computational complexity)

In other words, I'm interested in 2D discrete transforms that output the same transformation for arbitrary 2D rotations of the input, but that are not invariant to any other changes of the input. Ideally, these transforms should compress the input as much as possible in terms of information entropy (i.e. necessary bits to represent the output), and be "computable" in a practical sense.

As additional context to my question, I am planning on using such transforms in the domain of computer vision to train a classifier on instances of objects that might appear rotated arbitrarily around the image center point.

Update: From what I have learned in the past few days, Zernike polynomials are orthogonal and complete on the unit disk, and the absolute value of the Zernike coefficients are apparently invariant to rotation of the input. However, there are two problems with this, as far as I can tell:

  1. The original Zernike transform is defined on the continuous disk, for which the spectrum is not bounded, and infinitely many coefficients may be needed to reverse the transform; i.e. it is not really a discrete transform. In discrete transforms, such as the Discrete Cosine Transform (DCT) or the Discrete Fourier Transform (DTFT), the spectrum is bounded and discrete, and the number of harmonics is given by the dimensionality of the transform domain. Also, the Zernike polynomials do not form a basis on the sampled disk (See "Wave-front interpretation with Zernike Polynomials" by J. Y. Wang and D. E. Silva Applied Optics, Vol. 19, Issue 9, pp. 1510-1518 (1980)).

  2. The absolute value of the Zernike coefficients may not be injective beyond rotation (i.e. perturbations of the input function, other than rotations, may be transformed to the same coefficients).

Thank you


share|improve this question
    
Rotations about what? If you pick a basepoint in advance, then averaging the $O(2)$ orbit compresses the signal A LOT. –  Igor Rivin Jan 9 '11 at 2:06
1  
It seems to me that "2D discrete transform" does not go well with "arbitraty 2D rotation". Do you assume that your objects to be rotated are matrices in some sense? Then only rotation about 90° make sense (without interpolation)... –  Dirk Jan 9 '11 at 12:06
    
@Igor, I updated the question. We can assume rotations around the center point of a disk that holds the 2D signal. Would averaging the $O(2)$ orbit be invariant to rotations only? –  roseck Jan 9 '11 at 14:06
    
@Dirk, the "standard" representation of a 2D image in computer vision is a matrix, but for our purposes we can assume that the input signal is a disk of known radius. –  roseck Jan 9 '11 at 14:08
1  
@AV80: In what sense is the signal "discrete" then? –  Noah Stein Jan 9 '11 at 14:28
show 2 more comments

2 Answers 2

Fourier Mellin Transform is position rotation and scale invariant. See http://theja.scripts.mit.edu/pages/www/2008Sept_theja_paper_prsi.pdf for references.

share|improve this answer
add comment

I guess you could use a Riesz Transform which is known to be rotationnaly invariant. It is also getting quite used in image processing together with some wavelet frames or so.

You can find some details here: Steerable Wavelet Frames Based on the Riesz Transform . Hope it helped.

share|improve this answer
add comment

Your Answer

 
discard

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

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