Using a Computer to Put a Picture Puzzle together

Take a scanned image of picture puzzle pieces and assemble the picture puzzle.

Problems:

(a) Segment Pieces. From the small sample below, we have scanned multiple pieces at the same time. So the first problem is to find the separate pieces and put each scanned piece in its own data structure. One difficulty is that there appear to be edge shadows around the pieces, caused by the depth of the piece and the type of light source used by the scanner.
(b) Represent Pieces. The individual pieces need to be represented. It has been suggested that the representation should be rotation invariant, since one obvious problem is that pieces may need to be rotated to be put in place. We could at this point check if all pieces are of (computably) different representations, or if several pieces are the same shape.
Hankel Transform (?) is like a Fourier transform, but invariant to rotation.
(c) Algorithm to Put Pieces Together. Given the representation defined above, what algorithm is to be used to put the pieces together? Can we compute where each piece goes or will we need a trial and error algorithm, with backup, in case we make a mistake.
(d) Display the Algorithm as it determines the location of each piece. One could envision a program that puts up the original scattered pieces and then moves each on the screen to its correct place, assembling the puzzle before your eyes.

Answer the age-old question -- do you need the color information to put the puzzle together or can you do it on just the shape information.

I have 8 GIF files of about 6 mega-bytes each representing a color scanned image of a 500 piece puzzle.

Small Example

There are 8 files of scanned pieces, each is a GIF file, approximately 6 Megabytes.