быстрое нахождение маленького изображения в большом изображении

Question

Мне нужно получить координаты местоположения небольшого изображения, находящегося на большом изображении (скажем, мне нужно найти определенное дерево внутри фотографии леса. Если будет найдено подизображение, результат будет примерно таким:x=120 y=354 на примере).

Есть ли быстрый алгоритм, который я мог бы использовать?

Я использую Delphi (также можно использовать Java при необходимости)

Answer 1

Редактировать: Несколько вещей о теории:

В двух словах, есть два «пробела» для применения фильтров к изображению: в запасе цвета или в частотном пространстве.Если вы определили пространство (здесь частота, есть два вида фильтров: применяемые как свертка и корреляция (здесь). Для простоты мы предполагаем, что применение простой корреляции означает «мы умножаем две вещи». Используя корреляцию по частотепространство изображения, которое вы можете измерить, насколько похожи изображения. Два изображения похожи, если градиенты градаций серого. Это измеряется ковариацией. (Может быть, кто-то может помочь мне с вставкой формул здесь.) Коэффициент взаимной корреляции - нормализованная ковариация (вставьтеФормуляр здесь :() Если вы вставите это в алгоритм поиска сходства между «моделью» и «эталонным изображением» (модель - это небольшой раздел, который вы ищете в ref. img.), вы получите код matlab, которыйЯ тоже прокомментировал. Формула, которую использует код:° - комплекс, сопряженный с G (G - это fft модели)

Пожалуйста, определитесь быстро. :) Для решения, которое я имею в виду, потребуетсяFFT, что быстро, но, возможно, не так быстро, как вы хотите.Он ищет маленькое изображение "I_ausschnitt" внутри изображения I и дает позицию с наибольшей "возможностью".

В matlab это будет работать.Я надеюсь, что вы можете поместить его в 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

Редактировать: Это будет работать только для изображений в градациях серого.

Answer 2

Одной из возможностей является поиск строки Бойера-Мура: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

Конечно, вам придется адаптировать ее к проблеме поиска изображений.Предположим, что у большого изображения есть N пикселей, а у маленького M пикселей, вы будете смотреть на среднюю производительность случая N / M, что довольно хорошо.

Answer 3

Это довольно быстро (не удается найти в 160 мс, находит в 90 мс на 1600x900) и единственный, который вы найдете там. Любые ускорения приветствуются. Проверено для работы с 24-битными растровыми изображениями под 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;

Что он делает, так это загружает субизображение из файла и ищет его на экране (оно идентифицирует изображение по угловым цветам, а затем, если совпадения, оно ищет, как на вложенном изображении), но вы можете легко адаптировать его.

Результатом будут координаты экрана рядом с буквой E. значка файла PDF *

Answer 4

Существует несколько различных способов поиска подизображения на изображении.

Самое простое - использовать 2D-корреляцию вашего маленького изображения на большом изображении.Это будет довольно медленно, но легко реализовать.Это также хорошо работает, только если вспомогательное изображение выровнено с оригиналом (без поворота) и того же масштаба.

Если это не так (у вас есть изменения поворота и / или масштаба), тогда вам нужно что-тоболее продвинутый.Мой выбор - использовать алгоритм обнаружения признаков, такой как SIFT или SURF.

И просто повторить то, что я положил в большинство предыдущих ответов: использование алгоритмов, предназначенных для одномерных строк (Бойер-Мур)для обработки изображений просто неправильно.Если вы это сделаете, вы, скорее всего, потратите часы на реализацию и адаптацию чего-то, что не работает в текущем контексте, в то время как есть другие лучшие алгоритмы, которые вы могли бы использовать.

Answer 5

Я бы взял практический подход к этой проблеме для согласования 2D-позиции: Они, вероятно, будут растровыми изображениями ...

Сканирование каждой строки в большом растровом изображении от 0 до Larger.height - Smaller.Height и от 0 до Larger.Width - Smaller.Width, чтобы найти Smaller.TopLeft соответствующие пиксели. Когда найдено:

ЕСЛИ Smaller.TopRight, less.bottomLeft и less.bottomRight равны соответствующим пикселям в растровом изображении большего размера (все углы совпадают), а затем начать полное сравнение этого раздела.

Убедитесь, что все сравнения провалились рано (не продолжайте сравнение после любого несоответствия).

В среднем вам нужно всего лишь отсканировать менее 50% от большого растрового изображения, и вы не начнете много полных сравнений, которые не пройдут.

Answer 6

Если вы ищете точное совпадение (т. Е. Ни один пиксель не отличается между шаблоном, который вы ищете, и областью на изображении, которое вы хотите найти), вы можете использовать алгоритм Бойера-Мура.Адаптировать его для поиска 2D-шаблона должно быть довольно просто.

Скажем, шаблон, который вы ищете, имеет размер 20x20 пикселей.Вы строите таблицу, отображающую значения серого (или цвета) в позициях на изображении шаблона.Теперь можно проходить поиск изображения большими шагами, начиная с пикселя 19/19. Если этот пиксель содержит серое значение, которого нет в шаблоне, вы можете пропустить эту позицию и все позиции в области 20x20 вокруг него.Таким образом, следующий пиксель, который вы бы проверили, должен быть в точке поиска 39/19.Если он содержит пиксель, который появляется, например, в 3 позициях на изображении шаблона, вы можете проверить эти три позиции относительно вашей текущей позиции в поисковом изображении (39/19).

Обратите внимание, что этот алгоритм делает два предположения:

• Вы можете найти только точные совпадения.Это практически невозможно для изображений реального мира, если изображение шаблона не было извлечено непосредственно из изображения поиска.Это даже маловероятно, если исходное изображение и изображение шаблона сканируются, например, с одной и той же фотографии с помощью одного и того же сканера.Это не будет работать, если шаблон или исходное изображение были сжаты с использованием сжатия с потерями (например, JPEG) после извлечения шаблона.
• Ускорение зависит от количества используемых значений серого.Если вы ищете двоичный шаблон в двоичном изображении, этот алгоритм не будет работать за время O (n / m).