Поиск одного изображения в другом

← →
czuryk © (2009-01-23 15:48) [0]

Добрый день коллеги! Очень прошу помочь!

Давно уже бьюсь, но никак не могу расколоть сабжевую проблему, гугл выдает некую информацию, но мне никак не удается ее адаптировать для своих нужд. Учтите, речь идет не о сравнении одного изображения с другим.
Мне нужно организовать поиск одного изображения (маленького, порядка 100х50 пикселей) в другом - большом, порядка 1280х1024 пикселей, причем поиск должен осуществлятся максимально быстро < 1 сек. Результатом работы функкции должны быть координаты X,Y маленьгоко изображения в большом (исходном).
Причем поиск долже выполнятся по полному схождению части большого изображения и маленького. Так как если искать по нескольки ключевых точек, то такие функции в моем случае дают сбой.

procedure TForm1.Button4Click(Sender: TObject); Type TRGBTripleArray = ARRAY[WORD] OF TRGBTriple; pRGBTripleArray = ^TRGBTripleArray; var b1, b2: TBitmap; // c1, c2: PByteArray; c1, c2: pRGBTripleArray; x, y, i,: Integer; eq: boolean; resX, resY: integer; begin b1 := Image1.Picture.Bitmap; b2 := Image2.Picture.Bitmap; Assert(b1.PixelFormat = b2.PixelFormat); // they have to be equal for y := 0 to b1.Height - 1 do // Внешний цикл по строкам оригинала begin c1 := b1.Scanline[y]; c2 := b2.Scanline[0]; // Ищу на соответствие только по 1-й строке for x := 0 to b1.Width - 1 do begin eq := true; for i := 0 to b2.Width - 1 do // Цикл по строке искомой строки begin if (c1[x+i].RGBtRed <> c2[i].RGBtRed) or (c1[x+i].RGBtGreen <> c2[i].RGBtGreen) or (c1[x+i].RGBtBlue <> c2[i].RGBtBlue) then begin eq := false; break; end end; if ( eq ) then begin resX:=x; resY:=y; break; end; end; if ( eq ) then break; end; if ( eq ) then begin Memo1.Lines.Add("FOUND"); b1.canvas.Brush.Color := clRed; b1.canvas.Ellipse(resX-3, resY-3, resX+3, resY+3); end else Memo1.Lines.Add("NOT FOUND"); end;

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

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

... ... PInt = ^integer; var Form1: TForm1; implementation {$R *.dfm} function SearchBitmap(const bmMain,bmSub:TBitmap; var Res:TPoint):boolean; var iMainHeight, iMainWidth, iSubHeight, iSubWidth, iMainPXWidth, iSubPXWidth, iDiffPXWidth, iDiffHeight: integer; i,j:integer; eq: boolean; pRowMain, pRowSub : PByteArray; ltPt,rtPt,lbPt,rbPt : PInt; cPoints:array[0..3] of integer; begin Res.X := -1; Res.Y := -1; SearchBitmap := false; bmMain.PixelFormat:=pf24bit; bmSub.PixelFormat:=pf24bit; iMainHeight := bmMain.Height; iMainWidth := bmMain.Width; iMainPXWidth := iMainWidth * 3; iSubHeight := bmSub.Height; iSubWidth := bmSub.Width ; iSubPXWidth := iSubWidth *3 ; iDiffPXWidth := iMainPXWidth - iSubPXWidth; iDiffHeight:= iMainHeight - iSubHeight; pRowSub := bmSub.ScanLine[0]; cPoints[0]:= PInt(@(pRowSub^[0]))^ and $FFFFFF; cPoints[1]:= PInt(@(pRowSub^[iSubPXWidth-3]))^ and $FFFFFF; pRowSub := bmSub.ScanLine[iSubHeight-1]; cPoints[2]:= PInt(@(pRowSub^[0]))^ and $FFFFFF; cPoints[3]:= PInt(@(pRowSub^[iSubPXWidth-3]))^ and $FFFFFF; eq:=false; for i:=0 to iDiffHeight - 1 do begin pRowMain := bmMain.ScanLine[i]; pRowSub := bmMain.ScanLine[i+iSubHeight-1]; j:=0; ltPt := PInt(@pRowMain^[j]); lbPt := PInt(@pRowSub^[j]); //rtPt := PInt(pRowMain + iSubPXWidth - 3); //rbPt := PInt(pRowSub + iSubPXWidth - 3); asm mov eax,iSubPXWidth sub eax,3 mov ecx,eax add ecx,ltPt mov rtPt,ecx mov ecx,eax add ecx,lbPt mov rbPt,ecx end; while j<iDiffPXWidth do begin { eq := ((PInt(@(pRowMain^[j]))^ and $FFFFFF) = cPoints[0]) and ((PInt(@(pRowMain^[j+iSubPXWidth-3]))^ and $FFFFFF) = cPoints[1]) and ((PInt(@(pRowSub^[j]))^ and $FFFFFF ) = cPoints[2]) and ((PInt(@(pRowSub^[j+iSubPXWidth-3]))^ and $FFFFFF) = cPoints[3]); } eq := ((ltPt^ and $FFFFFF) = cPoints[0]) and ((rtPt^ and $FFFFFF) = cPoints[1]) and ((lbPt^ and $FFFFFF) = cPoints[2]) and ((rbPt^ and $FFFFFF) = cPoints[3]); if ( eq ) then begin Res.X := j div 3; Res.Y := i; SearchBitmap := true; break; end; asm add ltPt,3 add rtPt,3 add lbPt,3 add rbPt,3 end; inc(j,3); end; if eq then break; end; end; function CaptureScreenRect(ARect : TRect) : TBitmap; var ScreenDC: HDC; begin Result:=TBitmap.Create; with result, ARect do begin Width:=Right-Left; Height:=Bottom-Top; ScreenDC:=GetDC(0); try BitBlt(Canvas.Handle, 0,0,Width,Height,ScreenDC, Left, Top, SRCCOPY ); finally ReleaseDC(0, ScreenDC); end; end; end; procedure Search(pattern: string; p_color: TColor); var bmMain, bmSub: TBitmap; startPoint: TPoint; c: TCanvas; begin c := TCanvas.Create; c.Handle := GetDC(0); bmMain := TBitmap.Create(); bmSub := TBitmap.Create(); try // image1.Picture.Bitmap := CaptureScreenRect(Rect(0,0,Screen.Width,Screen.Height)); bmMain := CaptureScreenRect(Rect(0,0,Screen.Width,Screen.Height)); // bmMain.LoadFromFile("screen_main.bmp"); bmSub.LoadFromFile(pattern); if (SearchBitmap(bmMain, bmSub, startPoint)) then begin c.Brush.Color := p_color; c.Ellipse(startPoint.x-3, startPoint.y-3, startPoint.x+3, startPoint.y+3); end; finally bmMain.Free; bmSub.Free; c.Free; end; end;</CODE

← →
Anatoly Podgoretsky © (2009-01-23 15:57) [1]

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

Быстрого говоришь, а ведь тут примерно 1280х1024х100х50/2 сравнений.

← →
KilkennyCat © (2009-01-23 17:26) [2]

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

> Anatoly Podgoretsky ©
> примерно 1280х1024х100х50/2 сравнений.

сотню и полсотни можно ведь вычесть ?

← →
KSergey © (2009-01-23 17:29) [3]

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

2.Вам нужен готовый код или идеи?

← →
tesseract © (2009-01-23 17:33) [4]

Очередной замазыватель эмблемы канала ?

← →
KSergey © (2009-01-23 17:46) [5]

> tesseract © (23.01.09 17:33) [4]
> Очередной замазыватель эмблемы канала ?

Если так - то, конечно, не выйдет у него тогда так вот "просто".

А зафик ее замазывать?? Перепродавать эфир не платя отчислений?

← →
easy © (2009-01-23 18:11) [6]

> tesseract © (23.01.09 17:33) [4]
> Очередной замазыватель эмблемы канала ?
>

замазыватель делается не так.
рисуется логотип побольше и всё..

← →
czuryk © (2009-01-23 19:28) [7]

Нет ребят, замазывать я ничего не буду, мне нужно OCR-ить то что идет на экран. Есть одна извращенская программа написанная на JAVA, и с т.з. WinAPI к нейне подступиться, и приходится писать OCR модуль по шаблонуам.
Поэтому мне нужно реализовать совпадение до последнего пикселя.

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

2 KilkennyCat, вопрос с диаганалью, мне кажется не сильно даст прирост, в скорости, но я над этим еще подумаю. Спасибо!

← →
KilkennyCat © (2009-01-23 20:37) [8]

> опрос с диаганалью, мне кажется не сильно даст прирост,
> в скорости

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

← →
Anatoly Podgoretsky © (2009-01-23 20:40) [9]

> сотню и полсотни можно ведь вычесть ?

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

← →
AndreyV © (2009-01-23 21:10) [10]

> [2] KilkennyCat © (23.01.09 17:26)
> Просто сделать не тупой перебор, а поиск с вероятностью,

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

Другое дело, что достаточно проверить Н*М-н*м точек, Н*М - размер большой картинки

← →
KilkennyCat © (2009-01-23 21:13) [11]

> Anatoly Podgoretsky © (23.01.09 20:40) [9]

Ну, у нас внизуу и справа ведь отсекаются области, именно из-за полного вхождения. Не влезет шаблон.

> AndreyV © (23.01.09 21:10) [10]

Смысл в том, что не будет действительно полного перебора всех вариантов, посчитанных в [1]. Даже без заранее известных особенностей.

← →
KilkennyCat © (2009-01-23 21:26) [12]

Вообще, надо считать. Возможно, имеет смысл увеличить время выполнения каждой итерации цикла но снизить их количество в разы.
Возможно, булевская алгебра в асме выполнится намного быстрее, тогда можно привести матрицу экрана к виду
1110111
1111011
1101111
1011111
Где 0 - вхождение первой точки, и так далее.

← →
KilkennyCat © (2009-01-23 21:31) [13]

И еще: определение в шаблоне области размером 2x2 одного цвета в 4 раза уменьшит количество итераций первого цикла.

← →
KilkennyCat © (2009-01-23 21:36) [14]

И возможно ускорит запуск второго (и последующего циклов) в Thread

← →
AndreyV © (2009-01-23 21:42) [15]

> [11] KilkennyCat © (23.01.09 21:13)
> Смысл в том, что не будет действительно полного перебора
> всех вариантов, посчитанных в [1].

Не понимаю куда они денутся, кроме уже оговорённых краёв.

← →
tesseract © (2009-01-23 21:43) [16]

> Нет ребят, замазывать я ничего не буду, мне нужно OCR-ить
> то что идет на экран

Псих что-ли ? У тебя шаблонов будет около миллиарда, а то и больше.

> И еще: определение в шаблоне области размером 2x2 одного
> цвета

размер блока фиксирован, т.е метод приближения работает. Хотя по квадрату выясняй хоть по диагонали, для такой фичи требуеться поизучать RFC по mp2 или mp4 и плюс если в качестве источника видео будет выступать сжатое видео - там цвет пикселя плавает в широких пределах - т.е надо выяснять шаблон - шаблон, что для такого экрана за 1 секунду сделать нереально. Делать из картинки матрицу полной резкости тупо отбрасывая неподходящие шаблоны и создавая 5-6 шаговый алгоритм,,,,, это уже наверно только с CUDA возможно.

← →
KilkennyCat © (2009-01-23 22:02) [17]

> tesseract © (23.01.09 21:43) [16]

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

← →
KilkennyCat © (2009-01-23 22:11) [18]

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

← →
tesseract © (2009-01-23 22:35) [19]

> Диагональ, спираль, ход конем... Но это реально ускорит.

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

← →
Pavia © (2009-01-23 23:22) [20]

> Быстрого говоришь, а ведь тут примерно 1280х1024х100х50/2
> сравнений.

Несогласен вы про свертку забыли Будет примерно 1280х1024х11х10х2
И время сравнения порядка 1 секунды.
Свертку делать через FFT.

← →
KilkennyCat © (2009-01-23 23:32) [21]

> Свертку делать через FFT.

и припаять DSP :)

← →
Pavia © (2009-01-23 23:36) [22]

> и припаять DSP :)

Можно и на видео карте.

← →
czuryk © (2009-01-24 12:25) [23]

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

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

И вот еще пример. Нужно будет найти слово "Hello" в окне JAVA программы, то что это слово есть, мне будет известно, мне просто нужно найти его координаты. Поэтотому, у меня будут шаблоны для всех букв и я составлю из них один шаблон (шаблоны приходится использовать так как JAVA использует свои шрифты и извлечь их нет возможности), соединив Битмапы шаблонов нужной последовательности букв, и ища уже единый шаблон.

KilkennyCat, идея с матрицей неплоха, но ее внедрить не получится, т.к. работа идет с 24-битным цветом.

← →
Ramon © (2009-01-24 12:26) [24]

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

← →
czuryk © (2009-01-24 12:33) [25]

Привет Ramon, да, согласен. Я с него и начал... но он оооочень медленный. Прядка 1-2 секунд на двухядернике. Быстрее работает через ScanLine, но тоже недостаточно быстро, можешь посмотреть код, который я выложил.

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

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

> т.к. работа идет с 24-битным цветом.

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

Pavia, нет, текст это только одна из подзадач, вторая подзадача это поиск картинок, а с интегральнальными проекциями я не силен...

KilkennyCat, я пытался, но получаемая информация из ScanLine в виде массива не сравнивается как элементы массива, а нужно расшифровывать:
for i := 0 to b2.Width - 1 do // Цикл по строке искомой строки begin if (c1[x+i].RGBtRed <> c2[i].RGBtRed) or (c1[x+i].RGBtGreen <> c2[i].RGBtGreen) or (c1[x+i].RGBtBlue <> c2[i].RGBtBlue) then begin eq := false; break; end end;
Как это преодолеть я не знаю.

http://sql.ru/forum/actualthread.aspx?tid=632890

Johnmen, и? проблема до сих пор актуальна.

> czuryk © (24.01.09 19:20) [28]

Не нужно сканлайн и проч, это все теже танцы с графикой. Читаем память напрямую. Но это выше моего уровня, кодом не помогу, ибо мне придется пару дней сидеть за учебниками. Но я бы шел в этом направлении. Или в направлении
> Pavia © (23.01.09 23:22) [20]

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

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

Да тут достаточно scanline будет прямая работа с битмепом в памяти.
Только совет делать так через scanline получаем указатель на первый пиксель. Через разность получаем длину линии. Из-за выравнивания она будет отличаться от width*bytePerPixel. И еще вспомнить что у битмепа обратный порядок строк. И работать с указателями.

Pavia, а можно примерчик?

Вот тут представленны два неплохих алгоритма, которые быстро справляются с моей задачей:
http://forum.sources.ru/index.php?act=ST&f=11&t=263125

Всем спасибо.

Поиск одного изображения в другом Найти похожие ветки