fast finding of small image in a bigger image

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 wou开发者_高级运维ld 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)

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.

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.

There are a number of different techniques to find a sub image in an image.

The most straightforward is to use 2D correlation of your small image on the larger image. This will be quite slow but easy to implement. It also only works well if the sub image is aligned with the original (no rotation) and of the same scale.

If that is not the case (you have rotation and/or scale variations) then you need something more advanced. My choice would be to use a feature detection algorithm such as SIFT or SURF.

And just to reiterate what I have put in most of the previous answers: Using algorithms that are designed for 1D strings (Boyer-Moore) for image processing is just wrong. If you do you will most likely end up spending hours implementing and adapting something that does not work in the current context while there are other better algorithms that you could use.

It is pretty fast (fails to find in 160ms, finds in 90ms on 1600x900) and the only one you will find out there. Any speedups are welcome. Checked to work with 24-bit bitmaps under Win7/Win10 x64, XE2, XE5.

uses
  System.Generics.Collections;

type
  TSubImageInfo = record
    X: integer;
    Y: integer;
    Color: integer;
  end;

function ImageSearch(const ASubimageFile: string): TRect;
var
  X, Y, K, _Color: integer;
  _SubImageInfo: TSubImageInfo;
  _SubImageInfoList: TList<TSubImageInfo>;
  _SmallWidth, _SmallHeight, _BigWidth, _BigHeight: integer;
  _MatchingPixels: integer;
  _LTColor, _RTColor, _LBColor, _RBColor: integer;
  _FirstPixels: TList<TSubImageInfo>;
  _Offset: TPoint;
  _Desktop: HDC;
  _ScreenBitmap: TBitmap;
  _SubimageBitmap: TPNGImage;
  _Pos: TPoint;
begin
  Result.Left := -1;
  Result.Top := Result.Left;
  Result.Height := Result.Left;
  Result.Width := Result.Left;

  if not FileExists(ASubimageFile) then
    Exit;

  _SubImageInfoList := TList<TSubImageInfo>.Create;
  _ScreenBitmap := TBitmap.Create;
  _SubimageBitmap := TPNGImage.Create;
  _FirstPixels := TList<TSubImageInfo>.Create;
  try
    _SubimageBitmap.LoadFromFile(ASubimageFile);

    if (_SubimageBitmap.Height < 3) or (_SubimageBitmap.Width < 3) then
      Exit; // Image is too small

    X := 0;
    Y := _SubimageBitmap.Height div 2;
    while X < _SubimageBitmap.Width - 1 do
    begin
      _SubImageInfo.X := X;
      _SubImageInfo.Y := Y;
      _Color := _SubimageBitmap.Canvas.Pixels[X, Y];
      _SubImageInfo.Color := _Color;
      _SubImageInfoList.Add(_SubImageInfo);
      X := X + 3;
    end;

    Y := 0;
    X := _SubimageBitmap.Width div 2;
    while Y < _SubimageBitmap.Height - 1 do
    begin
      _SubImageInfo.X := X;
      _SubImageInfo.Y := Y;
      _Color := _SubimageBitmap.Canvas.Pixels[X, Y];
      _SubImageInfo.Color := _Color;
      _SubImageInfoList.Add(_SubImageInfo);
      Y := Y + 3;
    end;

    X := 0;
    Y := _SubimageBitmap.Height div 4;
    while X < _SubimageBitmap.Width - 1 do
    begin
      _SubImageInfo.X := X;
      _SubImageInfo.Y := Y;
      _Color := _SubimageBitmap.Canvas.Pixels[X, Y];
      _SubImageInfo.Color := _Color;
      _SubImageInfoList.Add(_SubImageInfo);
      X := X + 3;
    end;

    Y := 0;
    X := _SubimageBitmap.Width div 4;
    while Y < _SubimageBitmap.Height - 1 do
    begin
      _SubImageInfo.X := X;
      _SubImageInfo.Y := Y;
      _Color := _SubimageBitmap.Canvas.Pixels[X, Y];
      _SubImageInfo.Color := _Color;
      _SubImageInfoList.Add(_SubImageInfo);
      Y := Y + 3;
    end;

    X := 0;
    Y := (_SubimageBitmap.Height div 4) + (_SubimageBitmap.Height div 2);
    while X < _SubimageBitmap.Width - 1 do
    begin
      _SubImageInfo.X := X;
      _SubImageInfo.Y := Y;
      _Color := _SubimageBitmap.Canvas.Pixels[X, Y];
      _SubImageInfo.Color := _Color;
      _SubImageInfoList.Add(_SubImageInfo);
      X := X + 3;
    end;

    Y := 0;
    X := (_SubimageBitmap.Width div 4) + (_SubimageBitmap.Width div 2);
    while Y < _SubimageBitmap.Height - 1 do
    begin
      _SubImageInfo.X := X;
      _SubImageInfo.Y := Y;
      _Color := _SubimageBitmap.Canvas.Pixels[X, Y];
      _SubImageInfo.Color := _Color;
      _SubImageInfoList.Add(_SubImageInfo);
      Y := Y + 3;
    end;

    _Desktop := GetDC(0);
    _ScreenBitmap.PixelFormat := pf32bit;
    _ScreenBitmap.Width := Screen.Width;
    _ScreenBitmap.Height := Screen.Height;
    BitBlt(_ScreenBitmap.Canvas.Handle, 0, 0, _ScreenBitmap.Width,
      _ScreenBitmap.Height, _Desktop, 0, 0, SRCCOPY);
    _MatchingPixels := 0;
    _SmallWidth := _SubimageBitmap.Width - 1;
    _SmallHeight := _SubimageBitmap.Height - 1;
    _BigWidth := _ScreenBitmap.Width;
    _BigHeight := _ScreenBitmap.Height;

    _LTColor := _SubimageBitmap.Canvas.Pixels[0, 0];
    _RTColor := _SubimageBitmap.Canvas.Pixels[_SmallWidth, 0];
    _LBColor := _SubimageBitmap.Canvas.Pixels[0, _SmallHeight];
    _RBColor := _SubimageBitmap.Canvas.Pixels[_SmallWidth, _SmallHeight];

    for X := 1 to 3 do
    begin
      for Y := 1 to 3 do
      begin
        _SubImageInfo.X := X;
        _SubImageInfo.Y := Y;
        _SubImageInfo.Color := _SubimageBitmap.Canvas.Pixels[X, Y];
        _FirstPixels.Add(_SubImageInfo);
      end;
    end;

    X := 0;
    while X < _BigWidth - _SmallWidth do
    begin
      Y := 0;
      while Y < _BigHeight - _SmallHeight do
      begin
        _Color := _ScreenBitmap.Canvas.Pixels[X, Y];
        _Offset.X := 0;
        _Offset.Y := 0;
        for K := 0 to _FirstPixels.Count - 1 do
        begin
          if (_Color = _FirstPixels[K].Color) then
          begin
            _Offset.X := _FirstPixels[K].X;
            _Offset.Y := _FirstPixels[K].Y;
            Break;
          end;
        end;

        // Check if all corners matches of smaller image
        if ((_Offset.X <> 0) or (_Color = _LTColor)) and
          (_ScreenBitmap.Canvas.Pixels[X + _SmallWidth, Y] = _RTColor) and
          (_ScreenBitmap.Canvas.Pixels[X, Y + _SmallHeight] = _LBColor) and
          (_ScreenBitmap.Canvas.Pixels[X + _SmallWidth, Y + _SmallHeight]
          = _RBColor) then
        begin
          // Checking if content matches
          for K := 0 to _SubImageInfoList.Count - 1 do
          begin
            _Pos.X := X - _Offset.X + _SubImageInfoList[K].X;
            _Pos.Y := Y - _Offset.Y + _SubImageInfoList[K].Y;
            if (_ScreenBitmap.Canvas.Pixels[_Pos.X, _Pos.Y] = _SubImageInfoList
              [K].Color) then
              _MatchingPixels := _MatchingPixels + 1
            else
            begin
              _Pos.X := X - _Offset.X - 1 + _SubImageInfoList[K].X;
              _Pos.Y := Y - _Offset.Y + 1 + _SubImageInfoList[K].Y;
              if (_ScreenBitmap.Canvas.Pixels[_Pos.X, _Pos.Y]
                = _SubImageInfoList[K].Color) then
                _MatchingPixels := _MatchingPixels + 1
              else
              begin
                _MatchingPixels := 0;
                Break;
              end;
            end;
          end;
          if (_MatchingPixels - 1 = _SubImageInfoList.Count - 1) then
          begin
            Result.Left := X - _Offset.X;
            Result.Top := Y - _Offset.Y;

            Result.Width := _SubimageBitmap.Width;
            Result.Height := _SubimageBitmap.Height;
            Exit;
          end;
        end;
        Y := Y + 3;
      end;
      X := X + 3;
    end;

  finally
    FreeAndNil(_FirstPixels);
    FreeAndNil(_ScreenBitmap);
    FreeAndNil(_SubimageBitmap);
    FreeAndNil(_SubImageInfoList);
  end;
end;

What it does is it loads sub-image from file and searches it on the screen (it identifies image by corner colors then if those matches it searches as in attached image), but you can easily adapt it.

Result would be a screen coordinates next to PDF file icon letter E.

If you're searching for an exact match (i.e. not a single pixel is different between the pattern you're looking for and the area in the image you want to find), you can actually use the Boyer Moore algorithm. It should be quite straight-forward to adapt it for looking for a 2D pattern.

Let's say the pattern you look for is 20x20 pixels big. You build a table mapping greyvalues (or colors) to positions in the pattern image. Now can go through the search image in large strides, starting at pixel 19/19: If this pixel contains a greyvalue that's not contained in the pattern, you can skip this position and all the positions in a 20x20 area around it. So the next pixel you would check would be at 39/19 in the search image. If it contains a pixel that appeard e.g. in 3 positions in the pattern image, you can test these three positions relative to your current position in the search image (39/19).

Note that this algorithm makes two assumptions:

• you can only find exact matches. This is practically impossible for real-world images, unless the pattern image was extracted directly from the search image. It's even unlikely to work if source and pattern images are e.g. scanned from the same photograph with the same scanner. It won't work if the pattern or source image were compressed using a lossy compression (like jpeg) after the pattern was extracted.
• The speedup depends on the number of greyvalues used. If you're looking for a binary pattern in a binary image, this algorithm won't run in O(n/m) time.

I would take a practical approach to this problem for 2D position matching: They are probably going to be bitmaps...

Scan each line in the larger bitmap from 0 to Larger.height - Smaller.Height and from 0 to Larger.Width - Smaller.Width to find Smaller.TopLeft matching Pixels. When found:

IF Smaller.TopRight and smaller.bottomLeft and smaller.bottomRight are all equal to the corresponding pixels in the Larger bitmap (all the corners match) then initiate a full compare of that section.

Make sure that all comparisons fail early (do not continue comparing after any mismatch).

On average you will only need to scan less that 50% of the larger bitmap and will not start many full comparisons that fail.