fast finding of small image in a bigger image

Question

I need to get the coordinates of a small image location residing in a big image (let say I need to search for a specific tree inside a forest photograph. If the sub-image is found then the result would be something like: x=120 y=354 by example).

Is there a fast algorithm that I could use ?

I'm using Delphi (can also use Java if needed)

Answer 1

Edit: A few things about the theory:

In a nutshell, there are two "spaces" to apply filters on an image: in color spare or in frequency space. If you decided the space(freq here, there are two sorts of filters: applied as convolution and correlation(here). To keep it simple, we assume that appling correlation simple means "we multiplicate two things". With using the correlation in frequency space of an image you can measure how similar images are. Two images are similar, if the grayscale gradients are. This is measured by the covariance. (Maybe someone can help me with inserting formulars here.) The crosscorrelationcoefficent is the normalised covariance (insert formular here:( ) If you put this into a algorithm for searching affinities between a "model" and a "reference image" (model is a small section that you search within the ref. img.), you get the matlab code, which I commented too. The formular that the code uses is this one: FT([f°g] (m,n))=F(u,v)*G°(u,v). Where F is the fft and G° is the complex conjugated of G (G is the fft of the model)

Please define fast. :) The solution I have in mind will need the fft, which is fast, but maybe not as fast as you want. It searches for the small "I_ausschnitt" image inside the I image and gives the position with the highes "possibility".

In matlab, this one will work. I hope you can put it into delphi. :)

I = im2double(imread('Textiltextur.tif')); // This is our reference image
I_model = imcrop( I, [49 36 42 28] ); // Our model - what we want so search in I

[X Y] = size( I ); // Get the size of the reference image. 
f = fft2(I); // Perform the fast fourier transform->put the image into frequency space. 
f_model = fft2(I_model ,X,Y); // Perform the fft of the model but do this in the size of the original image. matlab will center I_model and set other pixel to zero
w = conj(model ); // Complex conjugated
g = real( ifft2(w.*f)); // .* will perform a komponent wise multiplicaion e.g. [0][0]*[0][0], [0][1]*[0][1] and not a matrix mul. 
gs =im2uint8(mat2gray(g)); // Convert the resulting correlation into an grayscale image with larger values->higher correlation

// Rest of the code is for displaying only
figure(1);
imshow(gs);
colormap hsv

figure;
[ XX YY] = meshgrid(1:Y,1:X );
colormap hsv 
surfc(XX,YY,double(gs)), title('3D Korrelation') 
min_corr = min(min(gs))
max_corr = max(max(gs))
%axis([1 X 1 Y min_corr max_corr])
colorbar

Edit: This will only work for grayscale images.

Answer 2

One possibility is a Boyer-Moore string search: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

You'll have to adapt it to your image search problem, of course. Supposing the large image has N pixels and the small one M pixels, you'd be looking at an average case performance of N/M, which is rather good.