Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to classify arbitrary 2D shapes. The classification should be invariant to at least affine transform. To achieve this invariance, I decided to "normalize" each shape by fitting it to a unit circle.

The shape is topologically equivalent to a circle, only deformed. I need to remove any linear deformations (translation, rotation, scale, skew) by fitting it in the unit circle so that the remaining deformities will characterize the shape.

The following picture illustrates the shape in red with its boundary denoted by $\alpha$ and the circle is denoted by $\beta$:

enter image description here

Now I would like to find a transform of the shape boundary points, such that distance between $\alpha$ and $\beta$ is minimized (in a least-squares sense).

The boundary point is $\alpha(t),\; t\in <0, 1>$ and the transform may look like this:

$$P\alpha(t)+T=\pmatrix{a & b\\c & d}\pmatrix{\alpha_{x}(t)\\\alpha_{y}(t)}+\pmatrix{t_{x}\\t_{y}}$$

The transform have six parameters: $a,b,c,d,t_{x}$ and $t_{y}$.

The solution may look like this:

enter image description here

I am able to parametrize the shape boundary to obtain any point on the boundary $\alpha$:

$$\alpha=\{\alpha(t),\quad t\in <0,1)\}$$

Now the problem can be formulated as a minimization problem, where objective function is given by:

$$e=\int_{0}^{1}\left( ||P\alpha(t)+T||_{2}-1\right)^{2} dt$$

In other words, $e$ is the distance between transformed boundary points $\alpha(t)$ and the unit circle. The norm $||\cdot||_{2}$ is simply a distance of the transformed point from origin, hence radius. We subtract this from the unit radius and square the result.

In practice, I will have a finite set of boundary points, so the above equation become a sum of squares.


Now for the question part:

Is this shape "normalization" sufficient for comparing shapes with affine invariance?

The least-squares solution is obviously not unique as the shape can be flipped and rotate freely within the unit circle. An ellipse would remove the rotation freedom, but there will still be a possible flip. Maybe a skewed ellipse or parallelogram would make the solution unique, but computing distance to these can be cumbersome. Is there a better way of how to ensure uniqueness of the solution?

share|improve this question
    
I'd take a different approach and consider moments of the given shapes to bring it into a standard position, size and rotation. Of course uniqueness can hardly be guaranteed by just a handful of parameters ... –  Hagen von Eitzen Oct 1 '12 at 11:08
add comment

1 Answer

(This is not an answer)

This is a very good, and "open", problem.

The objective function should be invariant with respect to reparametrizing the boundary curve $t\mapsto \alpha(t)$; but your proposed $e$ does not have this property. Even insisting on $t$ being arc length is not enough, because arc length is not affine invariant.

Here is a pointer to something affine invariant: For every bounded compact set $A\subset{\mathbb R}^2$ there is a unique ellipse $E_{\rm loew}(A)\supset A$ of minimal area, called the Loewner ellipsoid of $A$. There might be numerical algorithms around to find $E_{\rm loew}(A)$ from data about $A$. Mapping $E_{\rm loew}(A)$ to the unit disk $D$ gives an affine invariant representation of $A$ which is unique up to a rotation of $D$.

share|improve this answer
    
Thanks for the idea of using Loewner ellipsoid, this is something completely new to me. Why do you think $e$ is not invariant to reparametrization of boundary curve? It simply sums up distance from shape boundary points to nearest point of the circle. I am probably missing something important. –  Libor Oct 1 '12 at 11:21
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.