# FD used for shape matching

Given two 2D shapes represented by and , respectively, we can determine how similar they are to each other, independent of their location, size, orientation and starting point.

First, the matching problem can be approached in spatial domain by minimizing a distance between the two shapes:

If is small enough, and are similar.

Solving this problem requires a search for the minimum in a 5-dimensional space ( has both real and imaginary parts), and is therefore very time consuming.

We next consider solving the problem in frequency domain by comparing and , the FD's of the two shapes. The factor of location () can be easily eliminated by forcing the DC components and to zero, i.e., both shapes are centered at the origin. Now the FD's are

and

where is a variable related to the starting point :

The distance between and is defined as

We don't have to search a 3-dimensional space to find . Consider an objective function which is to be minimized:

where and is assumed to be real. Also note that if is a complex number, then

To find , , and that minimize , let

 (1)

 (2)

 (3)

Solving Eq. (1) for , we get

 (4)

From Eq. (2), we get

which yields
 (5)

Similarly, from Eq. (3), we can also get

 (6)

 (7)

Solving this equation we get , and then from either Eq. (5) or Eq. (6) we . We can then find from Eq. (4). Then is obtained.