Hi All!
Кто-нибудь занимался вопросом поиска маленькой картинки внутри большого изображения? Если да, буду рад выслушать соображения по поводу оптимизации процесса.

Давай сначала определимся с тем, что дано. Размеры большой и малой картинок предполагаются заранее известными, например, для определенности (NxN) и (nxn)?

Цитата(podval @ 11.1.2003, 15:15)

Давай сначала определимся с тем, что дано. Размеры большой и малой картинок предполагаются заранее известными, например, для определенности (NxN) и (nxn)?

Естесственно. Дано всё, и картинка, и размеры, формат для простоты возьмём TBitmap, можно брать его как массив целых чисел, если необходимо. Есть всё.

Например, формируется маленькая матрица из маленькой картинки и большая из большой. Вводится некоторая метрика, показывающая меру сходства. Потом маленькой матрицей мы как-бы пошагово "сканируем", как "маской", большую матрицу. Там, где метрика даст экстремум, по идее и находится то, что мы ищем.
Ну, эт пока первое, что пришло в голову.

Моя первая идея была копирование с XOR'oм... Но это неэффективный метод.
Всё гораздо проще. Маленькая картинка скрывается в большой в точности, т.е. ни малейшего отклонения в цвете и размерах. Фишка в том, чтобы наиоптимальнейшим образом осуществить это "пошаговое сканирование". Ориентировочные размеры: маленькой картинки - 32х32;
                                      большой - 1000х800.

Так размеры непропорциональны

Цитата(neutrino @ 12.1.2003, 11:51)

Так размеры непропорциональны

Ну и что? Маленькая картинка с комфортом помещается внутри большой.

Цитата

Маленькая картинка скрывается в большой в точности, т.е. ни малейшего отклонения в цвете и размерах.

Ты хочешь сказать, что условия идельны: нет шумов изображения и расфокусировки? Тогда не надо метрику вводить. Сразу при "сканировании" проверяем равенство матриц. А как его оптимизировать - вот вопрос. Пошаговое - самый верный способ.

Скажу точнее: надо найти стандартный элемент междумордия винды в скриншоте. Мой пошаговый алгоритм находит кнопку "закрыть прогу" в конце 800*600 изображения за 15 секунд. Хотелось бы шустрее.

Ну тогда выложи хоть в какой-нибудь форме свой алгоритм, обмозгуем.
А вообще на первый взгляд кажется, что время отработки такого алгоритма сильно зависит от начальной точки "сканирования". Надо подумать над тем, как бы ее получше задавать.

Цитата(podval @ 13.1.2003, 22:01)

Ну тогда выложи хоть в какой-нибудь форме свой алгоритм, обмозгуем. А вообще на первый взгляд кажется, что время отработки такого алгоритма сильно зависит от начальной точки "сканирования". Надо подумать над тем, как бы ее получше задавать.

Это безусловно.
Строго говоря, острой необходимости в решении данного вопроса нет, так как чаще всего картинка будет искаться на поле 100х100 или 200х200. Но сам по себе вопрос достаточно интересный.
Сейчас будет алгоритм на Дельфи.

1. Результат (просто для 100% ясности).

 TFIResponce=record
             Quantity:integer;
             fX:integer;
             fY:integer;
             end;{record}

function FindImage (gBI:TImage;gSI:TImage):TFIResponce;
var
 i,j,k,l:integer;
 w1,w2,h1,h2:integer;
 wc:TColor;
 found:boolean;
begin
w1:=gBI.Width;
h1:=gBI.Height;
w2:=gSI.Width;
h2:=gSI.Height;
result.fX:=-1;
result.fY:=-1;
result.Quantity:=0;
wc:=gSI.Canvas.Pixels[0,0];
j:=0;
with gBI.Canvas do
while j<=h1-h2 do
   begin
   i:=0;
   while i<=w1-w2 do
       begin
       if pixels[i,j]=wc then                              //Фигуративные точки для данной картинки, 3 шт.
       if pixels[i+8,j+6]=gSI.Canvas.Pixels[8,6] then
       if pixels[i+10,j+10]=gSI.Canvas.Pixels[10,10] then
           begin
           found:=true;
           l:=0;
           while found and (l<h2) do
               begin
               k:=0;
               while found and (k<w2) do
                 begin
                   if pixels[i+k,j+l]<>gSI.Canvas.Pixels[k,l] then found:=false;
                   inc(k);
                   end;{while (k)}
               inc(l);
               end;{while (l)}
           if found then
               begin
               inc(result.Quantity);
               if result.Quantity=1 then
                   begin
                   result.fX:=i;
                   result.fY:=j;
                   end;{if}
               end;{if}
           end;{if,if,if}
       inc(i);
       end;{while (i)}
   inc(j);
   end;{while (j), with}
end;{FindImage}

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

Если захочешь протестировать, то вот готовая процедурка:

procedure TestFI;
var
 im1,im2:TImage;
 wResp:TFIResponce;
begin
im1:=TImage.Create(MainF);
im1.Picture.LoadFromFile('E:\Delphi7\Projects\...\CloseButton.bmp');
im1.Width:=im1.picture.bitmap.width;
im1.Height:=im1.picture.bitmap.height;
im2:=TImage.Create(MainF);
im2.Picture.LoadFromFile('E:\Delphi7\Projects\...bmp');
im2.Width:=im2.picture.bitmap.width;
im2.Height:=im2.picture.bitmap.height;
wResp:=FindImage(im2,im1);
if wResp.Quantity=1 then ShowMessage(inttostr(wResp.fX)+'   '+inttostr(wResp.fY))
                   else ShowMessage(inttostr(wResp.Quantity));
im1.Free;
im2.Free;
end;{TestFI}

а я такую фигню делал:
1. берем скришот текста, скажем SDK
2. в проге вводим текст для поиска и шрифт
3. прога делает битмап из текста
4. ищем этот битмап в скриншоте и помечаем где нашли

поиск тупым сканированием быстро работает: 1024x768, 20 ms, Athlon 1600+, но так как 20 ms это время переключения контекста значит все еще быстрее

а методы ускорения такие же как для ускореного поиска текста тока с учетом 2D