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

Цитата(cully @ 14.1.2003, 09:53)

а я такую фигню делал: 1. берем скришот текста, скажем SDK 2. в проге вводим текст для поиска и шрифт 3. прога делает битмап из текста 4. ищем этот битмап в скриншоте и помечаем где нашли поиск тупым сканированием быстро работает: 1024x768, 20 ms, Athlon 1600+, но так как 20 ms это время переключения контекста значит все еще быстрее а методы ускорения такие же как для ускореного поиска текста тока с учетом 2D

К сожалению, у меня AMD K6-2 333MHz, и, как я уже писал, поиск по 800х600 изображения 16х14 работает 20 секунд (худший случай). Покажи, как там у тебя это пашет 20 мс.

To December: глянь почту

Спасибо за файлики.
На самом деле, крутая библиотечка. Буду копаться.

CmpPattern все что ближе к концу библиотеки я сам делал

Может кто предложить алгоритм, для варианта:
искомое изображение есть в общей картинке, но оно повернуто на неопределенный угол ?

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

Эт наверно надо будет нейронные сети юсать, я слышал что они могут учитывать: поворот, маштаб, не равное изменение маштаба по X и Y, перекашивание (skew). Только вот где нарыть исходники или хотя бы теорию именно по такой сети незнаю.

Цитата

берёшь две точки в маленьком изображении, желательно такие, чтобы их цвет встречался как можно реже в большом. Находишь первую точку; просматриваешь около неё такой круг, в котором могла бы находиться вторая точка.

Это кто же тебе возмет и пальцем тыкнет: Бери вот эту точку?
Если ищешь изображение 100x100, то это уже 10000 точек. Врядли там всегда будет уникальная точека.

Цитата

Эт наверно надо будет нейронные сети юсать, я слышал что они могут учитывать: поворот, маштаб, не равное изменение маштаба по X и Y, перекашивание (skew).

нейронные сети это хорошо, толко для них вроде бы и комп нужен не HOME PC.
А эта задача в общем виде решаеться в теории распознавания образов.

Цитата

Только вот где нарыть исходники или хотя бы теорию

Цитата(DENNN @ 1.2.2003, 17:26)

Это кто же тебе возмет и пальцем тыкнет: Бери вот эту точку? Если ищешь изображение 100x100, то это уже 10000 точек. Врядли там всегда будет уникальная точека.

Автоматически.
Берёшь большое изображение, сортируешь в нём цвета по частоте использования.
Выбираешь минимальный.
Находишь в маленьком рисунке первую и последнюю точку данного цвета, они и будут осью мира.
Вот и всё.

Цитата(DENNN @ 1.2.2003, 03:03)

Может кто предложить алгоритм, для варианта: искомое изображение есть в общей картинке, но оно повернуто на неопределенный угол ?

Надо перейти в полярную систему координат и, как ни покажется странным, уйти в частотную область, например, преобразованием Фурье. Теперь угол поворота будет не важен.

podval переход в полярную систему координат делять так, как ты уже описывал -- декарт. --> поляр. --> выстраивание в одну линию? Но вот как последний этам делать я точно понять не могу. Я думаю так: идем по четверти окружности [0..pi/2] с радиусом 0, заносим в массив все пиксели с удаленностью 0 и текущим углом, затем увеличиваем радиус на 1 и опять по окружности, и опять заносим в массив, так?

И еще вопрос как быть с данными о цвете, как от RGB перейти к одному вещественному числу [0.0..1.0]? Цвет ведь очень важен, скажем если на рисунке два яблока, зеленое и красное, а я хочу найти только красное.

Цитата

с радиусом 0

- это точка начала координат.

Цитата

затем увеличиваем радиус на 1 и опять по окружности, и опять заносим в массив, так?

угу

Цитата

как быть с данными о цвете

А почему нельзя в цвете и работать?

Цитата

А почему нельзя в цвете и работать?

цвет это DWORD, прямо от этого DWORD и делать Фурье или вейвлет? или с каждям каналом работать отдельно, но это повышает трудоемкость

Слушай, а этот метод точно работает, а то делаю делаю, а потом бац вторая смена Особенно интересно, как этот метод работает с фоном: есть эталон буква A на белом фоне, берем образец для теста, букву A на фоне леса. Что будет в этом случае? Как у этого метода с маштабом? И как искать маленький образец на большой картинке, букву A на отсканенной странице?

... и еще куча вопросов

Метод сработает и с dword.

Цитата

есть эталон буква A на белом фоне, берем образец для теста, букву A на фоне леса

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

Цитата

букву A на отсканенной странице

А это зачем? Подобие FineReader'a?

Цитата

А это зачем? Подобие FineReader'a?

дано

Изображение содержащее буквы и цифры; возможно с наклоном; возможно с фоном; возможно сами буквы и цифры залиты каким-либо изображением; возможны вариации букв по цвету; возможны вариации букв по написанию т.е. курсив, болд; шрифт заранее неизвестен..., короче то, что ты видишь при регистрации на маил.ру и всяких форумах

найти

текст в виде PChar, char *, String, CString, ...

решение



чуствую, что работать надо с контуром изображения, но какие же методики использовать

1. Найти фон сделать его одноцветным.
2. Найти заливку букв и сделать её одноцветной.
3. ??Попробовать перевести в векторную форму?? - не знаю, как, но может облегчить задачу.

найти фон, заливку мдя, рекурсивная задача -- для того что бы найти изображение надо найти изображение. ТУФТА!

Цитата(cully @ 12.2.2003, 22:04)

найти фон, заливку мдя, рекурсивная задача -- для того что бы найти изображение надо найти изображение. ТУФТА!

Для того, чтобы найти заливку, нужно работать с частотой появления данного цвета в рисунке, а не изображение искать. Алгоритм описать или сам в состоянии?

какая нафиг частота появления цвета при таком рисунке:



Это сообщение отредактировал(а) cully - 2.4.2003, 21:07

Мне кажеься в приведенной функции есть большие резервы для оптимизации даже без поиска каких то более оптимальных алгоритмов.
Известно что обращение к Bitmap через Canvas.Piexels[] операция очень медленная. Поэтому более оптимально сравнивать используя непосредственный доступ к Bitmap через ScanLine.
Получится несколько сложней из за необходимости учитывать формат пикселя но зато гораздо быстрее. По крайней мере у меня в свое время удалось таким образом увеличть скорость в несколько раз.

Цитата(cully @ 14.2.2003, 19:39)

какая нафиг частота появления цвета при таком рисунке:

Я не говорил, что этот алгоритм ловит все ситуации. Он может раскусить многие антиавторег-картинки.

Цитата(December @ 14.1.2003, 00:15)

//Фигуративные точки для данной картинки, 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

Вот вместо Pixels[] неплохобы использовать ScanLine
Часто позволяет ускорить в несколько разы правда придется усложнить процедуру для работы с разными форматами Bitmap.
Возможно и необходимость в сложных алгоритмах отпадет.

Да, я так и сделал (в других местах). Всё круто. От 80 секунд остались 0,8 секунды!

быстрый поиск ИМХО должен быть реализован в виде вложенныйх циклов проверки:
ищем на большой верхний левый пиксел маленькой, если находим то проверяем, на совпадают ли цвета пиксела, находящегося справа, внизу. справа+1, внизу+1, справа-внизу и т.д. по всей маленькой картинке.

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

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

а если бы еще и в однозадачной среде....

Есть такой алгоритм, по поиску картинок в в очень большой картинки(я лично решал - картинка была 100000x1000). Вот суть. Ты берёшь свою маленькую картинку и потсрочно её кодируешь, т.е если у тебя картинка ввиде матрицы:
36 58 12 - (3)
24 59 35 - (6)
86 78 93 - (9)
Откуда я взял числа в скобках. Ты строишь дерево с корнем в нулевой вершине. Если у тебя первый цвет с кодом 36 и из вершины в которой ты находишься нет ребенка с значение 36, то создаешь его и инкрементишь счетчик. Как проходишь одну строчку запоминаешь счетчик за данной строкой. Теперь идя по строкам перемещаешься по дереву в соответствии с кодом нового цвета. Если пути в новый цвет нет, то ты берешь твою последовательность и сдвигаешь влево. И опять ищещь такую вершину в дереве. Полезно значения такой функции запонить в массиве.
Аналогично для вертикального. Кодируешь таким же образом твою картинку в новое дерево(для одной картинки всегда будет одна вершина с номером 1). Тут уже можно и не запоминать(но не желательно) значения функции для каждого значения нового кода строчки. Этот алгоритм при правильной реализации работает на матрице MxN за O(MxN)

Давайте внесем немного ясности:
1)стороны малой картинки паралельный сторонам большой или не обязательно?
2) искомое изображение совпадает полностью с эталоном или возможны шумы/колебания яркости и цвета?
3) искомое изображение полностью присутствует в исходном или возможно наличие только части изображения?
4) искомое изображение встречается только раз в большом или его количество не определено?
5) масштаб искомого изображения неизменен?

Самый простой случай: все паралельно, одномасштабно, содержится один раз и полностью. Наум приходит сразу несколько решений от простого перебора до рекурсивных процедур и пр.

В более сложном случае надо вначале применять частотный анализ и т.п. математические алгоритмы (возможно использовать нейронные сети).

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

Это сообщение отредактировал(а) GePo - 1.4.2003, 22:43

Джентльмены,
вообще-то задача решена, то есть, премного благодарен, если вы мне помогаете, но всё уже позади. Есди же вы обсуждаете данный вопрос как абстрактную задачу, то вот как был поставлен вопрос с самого начала:

Цитата

1)стороны малой картинки паралельный сторонам большой или не обязательно?

Да

Цитата

2) искомое изображение совпадает полностью с эталоном или возможны шумы/колебания яркости и цвета?

Совпадает

Цитата

3) искомое изображение полностью присутствует в исходном или возможно наличие только части изображения?

Полностью

Цитата

4) искомое изображение встречается только раз в большом или его количество не определено?

Не суть важно, где один, там и десять.

Цитата

5) масштаб искомого изображения неизменен?

Да.
Как показала практика, выигрыш в скорости за счёт использования ScanLine на порядок выше выигрыша от хитроумных алгоритмов.

вообще-все это ускоряется трансформом фурье быстрым

Если можно, подробнее.