Image in Image Algorithm

Question

I need an algorithm written in any language to find an image inside of an image, including at different scales. Does anyone know a starting point to solving a problem like this?

For example:

I have an image of 800x600 and in that image is a yellow ball measuring 180 pixels in circumference. I need to be able to find this image with a search pattern of a yellow ball having a circumference of 15 pixels.

Thanks

Answer 1

Here's an algorithm:

• Split the image into RGB and take the blue channel. You will notice that areas that were yellow in the color image are now dark in the blue channel. This is because blue and yellow are complementary colors.
• Invert the blue channel
• Create a greyscale search pattern with a circle that's the same size as what's in the image (180 pixels in circumference). Make it a white circle on a black background.
• Calculate the cross-correlation of the search pattern with the inverted blue channel.
• The cross-correlation peak will correspond to the location of the ball.

Here's the algorithm in action:

RGB and R:

G and B:

Inverted B and pattern:

Python + OpenCV code:

import cv
if __name__ == '__main__':
    image = cv.LoadImage('ball-b-inv.png')
    template = cv.LoadImage('ball-pattern-inv.png')

    image_size = cv.GetSize(image)
    template_size = cv.GetSize(template)
    result_size = [ s[0] - s[1] + 1 for s in zip(image_size, template_size) ]

    result = cv.CreateImage(result_size, cv.IPL_DEPTH_32F, 1)

    cv.MatchTemplate(image, template, result, cv.CV_TM_CCORR)

    min_val, max_val, min_loc, max_loc = cv.MinMaxLoc(result)

    print max_loc

Result:

misha@misha-desktop:~/Desktop$ python cross-correlation.py 
(72, 28)

This gives you the top-left co-ordinate of the first occurence of the pattern in the image. Add the radius of the circle to both x and y co-ordinates if you want to find the center of the circle.

Answer 2

You should take a look at OpenCV, an open source computer vision library - this would be a good starting point. Specifically check out object detection and the cvMatchTemplate method.