Page 253 -

232 4 Feature detection and matching

1. Walk along the contour and create a list of (x i ,y i ,s i ) triplets, using the arc-length
formula
s i+1 = s i + x i+1 − x i . (4.32)

2. Resample this list onto a regular set of (x j ,y j ,j) samples using linear interpolation of
each segment.
3. Compute the average values of x and y, i.e., x and y and subtract them from your
sampled curve points.

4. Resample the original (x i ,y i ,s i ) piecewise-linear function onto a length-independent
set of samples, say j ∈ [0, 1023]. (Using a length which is a power of two makes
subsequent Fourier transforms more convenient.)

5. Compute the Fourier transform of the curve, treating each (x, y) pair as a complex
number.

6. To compare two curves, fit a linear equation to the phase difference between the two
curves. (Careful: phase wraps around at 360 . Also, you may wish to weight samples
◦
by their Fourier spectrum magnitude—see Section 8.1.2.)

7. (Optional) Prove that the constant phase component corresponds to the temporal shift
in s, while the linear component corresponds to rotation.

Of course, feel free to try any other curve descriptor and matching technique from the com-
puter vision literature (Tek and Kimia 2003; Sebastian and Kimia 2005).

Ex 4.10: Jigsaw puzzle solver—challenging Write a program to automatically solve a jig-
saw puzzle from a set of scanned puzzle pieces. Your software may include the following
components:

1. Scan the pieces (either face up or face down) on a flatbed scanner with a distinctively
colored background.
2. (Optional) Scan in the box top to use as a low-resolution reference image.

3. Use color-based thresholding to isolate the pieces.
4. Extract the contour of each piece using edge finding and linking.

5. (Optional) Re-represent each contour using an arc-length or some other re-parameterization.
Break up the contours into meaningful matchable pieces. (Is this hard?)
6. (Optional) Associate color values with each contour to help in the matching.

7. (Optional) Match pieces to the reference image using some rotationally invariant fea-
ture descriptors.

8. Solve a global optimization or (backtracking) search problem to snap pieces together
and place them in the correct location relative to the reference image.

9. Test your algorithm on a succession of more difficult puzzles and compare your results
with those of others.