# Image processing, recognizing a small feature in a larger image

I am trying to write an image processing program to recognize bubbles in oil. It has been suggested I try computing the convolution of the image and an image of a typical bubble. i.e. : ifft(fft(a).fft(b)) will have high peaks near bubbles.

where:
ifft : inverse fourier transform
fft : fourier transform
a : the image
b : kernel image (bubbles)

Is this a good way to solve this problem? Also, for the dot product to work, I need the images to be the same dimension. This is not likely to be the case.

Template matching works well for some cases, with some caveats:

1) you will probably need to pre-whiten your image before it will work successfully.

2) your FFTs and IFFT should be of an appropriate length to avoid aliasing due to the circular convolution involved.

See this example of item 1:

The patch we are trying to find is the singer's nose. This is a toy example, because I've used the exact pixels from the image (rather than a "template"), but it illustrates the issue.

The bottom left image shows what happens when you use template matching (as you've described in the question) without doing any processing. The problem is that there is no localization at all: it's very hard to discern the true "peak" in the surface that is generated.

The bottom right image shows what happens when the same operation occurs, but a (stupidly simple) pre-whitening of applying the diff operation to both the image being searched and the template. It's a little hard to see because the peak is so small and large, but there is a red peak in the correct place.

This image shows the "side view" of the bottom two images.

What has been suggested to you is called template matching. If you don't mind re-using code (and working with C++), you can find an implementation in the OpenCV library.

A simpler alternative (that I would start with) would be to work with generalized Hough transform, but that will require some pre-processing first by detecting the edges in the image.

You must calculate correlation between kernel image "b" and sub-images of whole original image of same size in any possible position. If the correlation is quite high for some position - you have found bubble in this position. If size of kernel image is quite big - use FFT for calculation of correlation. If kernel is small - it may be better to use direct calculation of correlation. It is better to use normalization correlation. This calculation need very much computer power. So it's very important to do the calculation fast. There is classical article - J. P. Lewis "Fast Normalized Cross-Correlation. Search for citation to this article too. Article in wiki is very useful too - http://en.wikipedia.org/wiki/Template_matching#Speeding_up_the_Process

I confirm answer of sansuiso - OpenCV library has very good implementation of template matching. If size of bubbles is quite different it will be better to use another algorithm - see reference on generalized Hough transform in answer of sansuiso.