2D subimage detection in Open CV

Question

What's the most sensible algorithm, or combination of algorithms, to be using from OpenCV for the following problem:

• I have a set of small 2D images. I want to detect the locations of these subimages in a larger image.
• The subimages are usually around 32x32 pixels, and the larger image is around 400x400.
• The subimages are not always square, and such contains alpha channel.
• Optionally - the larger image may be grainy, compressed, rotated in 3D, or otherwise slightly distorted

I have tried cvMatchTemplate, with very poor results (difficult to match correctly, and large numbers of false positives, with all match methods). Some of the problems come from the fact OpenCV can't seem to deal with alpha channel template matching.

I have tried a manual search, which seems to work better, and can include the alpha channel, but is very slow.

Thanks for any help.

Petuntse

Answer 1

1. cvMatchTemplate uses a MSE (SQDIFF/SQDIFF_NORMED) kind of metric for the matching. This kind of metric will penalize different alpha values severly (due to the square in the equation). Have you tried normalized cross-correlation? It is known to model linear variations in pixel intensities better.
2. If NCC does not do the job, you will need to transform the images to a space where the intensity differences do not have much effect. e.g. Compute a edge-strength image (canny, sobel etc) and run cvMatchTemplate on these images.
3. Considering the large difference in scales of the images (~10x). A image pyramid will have to be employed to figure out the correct scale for the matching. Recommend you start with a scale (2^1/x: x being the correct scale) and propagate the estimate up the pyramid.

Karren

Good answer. I have tried other metrics with no dissernable increase in reliability. A edge-strength preprocessing sounds like a good plan, I will try that. – Petuntse

Humm, pre-cannying the image doesn't seem to help, as slight compression differences produce sharp edge differences with bad NCC results... Any more tips? – Petuntse

This is because of the scale difference in the images. Your target image is ~10x smaller than the source. As a result you will have to estimate the scale space to do the matching too. – Karren

provide some sample images. If simple enough you could match images through shape or colour. – Crotchety

Answer 2

What you need is something like SIFT or SURF.

Embouchure

Great stuff, I tried out SURF and it looks like exactly what I need. My only issue is that it operates on grayscale images, which seems like a pointless reduction in information. What should I be doing cleverly to "include" that information in the SURF search? SURF on every channel? SURF on Hue? – Petuntse