Matching a rotated bitmap to a collage image

Question

Hi,

My problem is that I have an image of a detailed street map. On this map, there can be a certain small image of a sign (such as a traffic light icon) rotated at any angle, maybe resized. I have this small image in a bitmap. Is there any algorithm or technique by which I can locate this bitmap if a copy of it exists, rotated and maybe resized, in the large collage image?

This is similar to the problem with Augmented Reality and locating the marker image, but mine is only 2D with no perspective distortion.

Edit: The small bitmap and the copy of it in the collage image with which I want to match are approximately the same size, maybe 30% maximum size difference. The rotation is pure 2D, no shearing or any distortion.

Answer 1

This is a very tricky question here.

First: What are the resolutions for rotation/resizing? If you have sufficient pixels to avoid aliasing effects, then you might be ok, but if one or the other representation of the sign is very small (ie, it's small in the collage or small in the sample shot you have), rotations to an arbitrary angle could be bad.

Also, are you sure you don't have shearing or other kinds of effects? I'm assuming a purely 2D rotation, where the axis of rotation runs through the center of the camera (ie, a stop sign will just be an octagon, rotated, not a sheared octagon).

One thing you can try, if you have the patience and the sample data, is to implement Viola and Jones' face matching algorithm, but for the sign. Basically, you need a bunch of training data, where you have masked out the pixels that are interesting to you from the background/pixels that are not. Then, the algorithm is to randomly select pixels from that training data ('examples') and for each example, calculate a few hundred to a few thousand statistics ('features'). A feature can be anything from the current pixel intensity in the red channel to the summed intensity of a 5x5 neighborhood in the blue channel. Then, you build a histogram for each pixel and try to find features that have foreground pixels separated from background pixels on the histogram (ie, foreground is all on the left of the histogram, background the right). You then choose the best features for the job, and run them to find the sign in the collage.

That is a brief summary of a friend of mine's dissertation research. This kind of problem is hard to solve easily, and easy to make a bad solution for.

If you just have one sign and one collage and only want to have one solution, you can basically convolve the sign with the collage. Take the FFT of each one, pad the smaller image with zeroes so that it's the same size as the larger, then do a point-by-point multiplication. Then, perform an inverse fft on the result. You should see a spike in the location of the sign in the collage, depending on the severity of rotation and scaling (if you believe that they are very different, then you might need to experiment with a variety of different scaling and rotation techniques).

This second approach is easily done in matlab; otherwise, you'll need a library like the fftw to pull it off.