| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск маленького изображения |
| Автор: December 11.1.2003, 12:46 |
| Hi All! Кто-нибудь занимался вопросом поиска маленькой картинки внутри большого изображения? Если да, буду рад выслушать соображения по поводу оптимизации процесса. |
| Автор: podval 12.1.2003, 00:15 |
| Давай сначала определимся с тем, что дано. Размеры большой и малой картинок предполагаются заранее известными, например, для определенности (NxN) и (nxn)? |
| Автор: December 12.1.2003, 02:25 | ||
Естесственно. Дано всё, и картинка, и размеры, формат для простоты возьмём TBitmap, можно брать его как массив целых чисел, если необходимо. Есть всё. |
| Автор: podval 12.1.2003, 04:32 |
| Например, формируется маленькая матрица из маленькой картинки и большая из большой. Вводится некоторая метрика, показывающая меру сходства. Потом маленькой матрицей мы как-бы пошагово "сканируем", как "маской", большую матрицу. Там, где метрика даст экстремум, по идее и находится то, что мы ищем. Ну, эт пока первое, что пришло в голову. |
| Автор: December 12.1.2003, 07:18 |
| Моя первая идея была копирование с XOR'oм... Но это неэффективный метод. Всё гораздо проще. Маленькая картинка скрывается в большой в точности, т.е. ни малейшего отклонения в цвете и размерах. Фишка в том, чтобы наиоптимальнейшим образом осуществить это "пошаговое сканирование". Ориентировочные размеры: маленькой картинки - 32х32; большой - 1000х800. |
| Автор: neutrino 12.1.2003, 20:51 |
| Так размеры непропорциональны |
| Автор: December 12.1.2003, 23:42 | ||
Ну и что? Маленькая картинка с комфортом помещается внутри большой. |
| Автор: podval 13.1.2003, 03:04 | ||
Ты хочешь сказать, что условия идельны: нет шумов изображения и расфокусировки? Тогда не надо метрику вводить. Сразу при "сканировании" проверяем равенство матриц. А как его оптимизировать - вот вопрос. Пошаговое - самый верный способ. |
| Автор: December 13.1.2003, 08:08 |
| Скажу точнее: надо найти стандартный элемент междумордия винды в скриншоте. Мой пошаговый алгоритм находит кнопку "закрыть прогу" в конце 800*600 изображения за 15 секунд. Хотелось бы шустрее. |
| Автор: podval 14.1.2003, 07:01 |
| Ну тогда выложи хоть в какой-нибудь форме свой алгоритм, обмозгуем. А вообще на первый взгляд кажется, что время отработки такого алгоритма сильно зависит от начальной точки "сканирования". Надо подумать над тем, как бы ее получше задавать. |
| Автор: December 14.1.2003, 08:13 | ||
Это безусловно. Строго говоря, острой необходимости в решении данного вопроса нет, так как чаще всего картинка будет искаться на поле 100х100 или 200х200. Но сам по себе вопрос достаточно интересный. Сейчас будет алгоритм на Дельфи. 1. Результат (просто для 100% ясности). TFIResponce=record Quantity:integer; fX:integer; fY:integer; end;{record} |
| Автор: December 14.1.2003, 08:15 |
| 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} |
| Автор: December 14.1.2003, 08:20 |
Конечно, степень успеха зависит от индивидуального подхода к картинкам. Ещё пришло в голову, что есть, например, цвет, рядом с которым данная картинка быть не может; в случае с кнопкой закрытия окна этот цвет - белый (рабочее поле для всяких текстов обычно). При нахождении белого пиксела я проскакивал следующие 4. Но этот метод никакого прироста в скорости почему-то не дал  И я его убрал из кода. |
| Автор: December 14.1.2003, 08:23 |
| Если захочешь протестировать, то вот готовая процедурка: 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} |
| Автор: stab 14.1.2003, 18:53 |
| а я такую фигню делал: 1. берем скришот текста, скажем SDK 2. в проге вводим текст для поиска и шрифт 3. прога делает битмап из текста 4. ищем этот битмап в скриншоте и помечаем где нашли поиск тупым сканированием быстро работает: 1024x768, 20 ms, Athlon 1600+, но так как 20 ms это время переключения контекста значит все еще быстрее  а методы ускорения такие же как для ускореного поиска текста тока с учетом 2D |
| Автор: December 15.1.2003, 08:53 | ||
К сожалению, у меня AMD K6-2 333MHz, и, как я уже писал, поиск по 800х600 изображения 16х14 работает 20 секунд (худший случай). Покажи, как там у тебя это пашет 20 мс. |
| Автор: stab 15.1.2003, 14:20 |
| To December: глянь почту |
| Автор: December 16.1.2003, 10:29 |
| Спасибо за файлики. На самом деле, крутая библиотечка. Буду копаться. |
| Автор: stab 16.1.2003, 13:07 |
| CmpPattern все что ближе к концу библиотеки я сам делал |
| Автор: DENNN 1.2.2003, 06:03 |
| Может кто предложить алгоритм, для варианта: искомое изображение есть в общей картинке, но оно повернуто на неопределенный угол ? |
| Автор: December 1.2.2003, 09:39 |
| Можно так: берёшь две точки в маленьком изображении, желательно такие, чтобы их цвет встречался как можно реже в большом. Находишь первую точку; просматриваешь около неё такой круг, в котором могла бы находиться вторая точка. Если находишь вторую, вычисляешь угол наклона и проверяешь прямым сличением (или третьей точкой). |
| Автор: stab 1.2.2003, 20:44 |
Эт наверно надо будет нейронные сети юсать, я слышал что они могут учитывать: поворот, маштаб, не равное изменение маштаба по X и Y, перекашивание (skew). Только вот где нарыть исходники или хотя бы теорию именно по такой сети незнаю.  |
| Автор: DENNN 1.2.2003, 21:26 | ||||||
Это кто же тебе возмет и пальцем тыкнет: Бери вот эту точку? Если ищешь изображение 100x100, то это уже 10000 точек. Врядли там всегда будет уникальная точека.
нейронные сети это хорошо, толко для них вроде бы и комп нужен не HOME PC. А эта задача в общем виде решаеться в теории распознавания образов.
 |
| Автор: December 2.2.2003, 03:29 | ||
Автоматически. Берёшь большое изображение, сортируешь в нём цвета по частоте использования. Выбираешь минимальный. Находишь в маленьком рисунке первую и последнюю точку данного цвета, они и будут осью мира. Вот и всё. |
| Автор: podval 2.2.2003, 06:01 | ||
Надо перейти в полярную систему координат и, как ни покажется странным, уйти в частотную область, например, преобразованием Фурье. Теперь угол поворота будет не важен. |
| Автор: stab 11.2.2003, 10:33 |
| podval переход в полярную систему координат делять так, как ты уже описывал -- декарт. --> поляр. --> выстраивание в одну линию? Но вот как последний этам делать я точно понять не могу. Я думаю так: идем по четверти окружности [0..pi/2] с радиусом 0, заносим в массив все пиксели с удаленностью 0 и текущим углом, затем увеличиваем радиус на 1 и опять по окружности, и опять заносим в массив, так? И еще вопрос как быть с данными о цвете, как от RGB перейти к одному вещественному числу [0.0..1.0]? Цвет ведь очень важен, скажем если на рисунке два яблока, зеленое и красное, а я хочу найти только красное. |
| Автор: podval 12.2.2003, 02:33 | ||||||
угу
А почему нельзя в цвете и работать? |
| Автор: stab 12.2.2003, 05:07 | ||
цвет это DWORD, прямо от этого DWORD и делать Фурье или вейвлет? или с каждям каналом работать отдельно, но это повышает трудоемкость Слушай, а этот метод точно работает, а то делаю делаю, а потом бац вторая смена Особенно интересно, как этот метод работает с фоном: есть эталон буква A на белом фоне, берем образец для теста, букву A на фоне леса. Что будет в этом случае? Как у этого метода с маштабом? И как искать маленький образец на большой картинке, букву A на отсканенной странице?... и еще куча вопросов |
| Автор: podval 12.2.2003, 23:23 | ||||
Метод сработает и с dword.
Ну не знаю, надо пробовать. Если другие буквы на подобном фоне, то по идее не спутает. Все же "А" на фоне леса больше похожа на себя на белом фоне, чем "Б", например.
А это зачем? Подобие FineReader'a? |
| Автор: stab 13.2.2003, 03:55 | ||
дано Изображение содержащее буквы и цифры; возможно с наклоном; возможно с фоном; возможно сами буквы и цифры залиты каким-либо изображением; возможны вариации букв по цвету; возможны вариации букв по написанию т.е. курсив, болд; шрифт заранее неизвестен..., короче то, что ты видишь при регистрации на маил.ру и всяких форумах найти текст в виде PChar, char *, String, CString, ... решение  чуствую, что работать надо с контуром изображения, но какие же методики использовать |
| Автор: December 13.2.2003, 05:19 |
| 1. Найти фон сделать его одноцветным. 2. Найти заливку букв и сделать её одноцветной. 3. ??Попробовать перевести в векторную форму?? - не знаю, как, но может облегчить задачу. |
| Автор: stab 13.2.2003, 07:04 |
| найти фон, заливку мдя, рекурсивная задача -- для того что бы найти изображение надо найти изображение. ТУФТА! |
| Автор: December 13.2.2003, 09:24 | ||
Для того, чтобы найти заливку, нужно работать с частотой появления данного цвета в рисунке, а не изображение искать. Алгоритм описать или сам в состоянии? |
| Автор: stab 15.2.2003, 04:39 |
какая нафиг частота появления цвета при таком рисунке: |
| Автор: Unregistered 16.2.2003, 20:38 |
| Мне кажеься в приведенной функции есть большие резервы для оптимизации даже без поиска каких то более оптимальных алгоритмов. Известно что обращение к Bitmap через Canvas.Piexels[] операция очень медленная. Поэтому более оптимально сравнивать используя непосредственный доступ к Bitmap через ScanLine. Получится несколько сложней из за необходимости учитывать формат пикселя но зато гораздо быстрее. По крайней мере у меня в свое время удалось таким образом увеличть скорость в несколько раз. |
| Автор: December 17.2.2003, 08:09 | ||
Я не говорил, что этот алгоритм ловит все ситуации. Он может раскусить многие антиавторег-картинки. |
| Автор: Guest 17.2.2003, 23:54 | ||
Вот вместо Pixels[] неплохобы использовать ScanLine Часто позволяет ускорить в несколько разы правда придется усложнить процедуру для работы с разными форматами Bitmap. Возможно и необходимость в сложных алгоритмах отпадет. |
| Автор: December 18.2.2003, 08:28 |
| Да, я так и сделал (в других местах). Всё круто. От 80 секунд остались 0,8 секунды! |
| Автор: wds 1.4.2003, 02:53 |
| быстрый поиск ИМХО должен быть реализован в виде вложенныйх циклов проверки: ищем на большой верхний левый пиксел маленькой, если находим то проверяем, на совпадают ли цвета пиксела, находящегося справа, внизу. справа+1, внизу+1, справа-внизу и т.д. по всей маленькой картинке. особо привлекательно это при поиске очеь маленькой картинки на очень большой, так как в таком случае можно реализовать его без рекурсивных вызовов процедур в виде простых циклов. при организации писка с помощью рекурсивных вызовов (что, в принципе, универсально - т.е. теоритечески можно сделать поиск картинки любого размера на любой картинке), но в результате получим проигрыш в скорости, разве что писать все на асме, храня при этом картины в локальном буфере.  а если бы еще и в однозадачной среде.... |
| Автор: GePo 1.4.2003, 21:54 |
| Есть такой алгоритм, по поиску картинок в в очень большой картинки(я лично решал - картинка была 100000x1000). Вот суть. Ты берёшь свою маленькую картинку и потсрочно её кодируешь, т.е если у тебя картинка ввиде матрицы: 36 58 12 - (3) 24 59 35 - (6) 86 78 93 - (9) Откуда я взял числа в скобках. Ты строишь дерево с корнем в нулевой вершине. Если у тебя первый цвет с кодом 36 и из вершины в которой ты находишься нет ребенка с значение 36, то создаешь его и инкрементишь счетчик. Как проходишь одну строчку запоминаешь счетчик за данной строкой. Теперь идя по строкам перемещаешься по дереву в соответствии с кодом нового цвета. Если пути в новый цвет нет, то ты берешь твою последовательность и сдвигаешь влево. И опять ищещь такую вершину в дереве. Полезно значения такой функции запонить в массиве. Аналогично для вертикального. Кодируешь таким же образом твою картинку в новое дерево(для одной картинки всегда будет одна вершина с номером 1). Тут уже можно и не запоминать(но не желательно) значения функции для каждого значения нового кода строчки. Этот алгоритм при правильной реализации работает на матрице MxN за O(MxN) |
| Автор: DENNN 1.4.2003, 22:26 |
| Давайте внесем немного ясности: 1)стороны малой картинки паралельный сторонам большой или не обязательно? 2) искомое изображение совпадает полностью с эталоном или возможны шумы/колебания яркости и цвета? 3) искомое изображение полностью присутствует в исходном или возможно наличие только части изображения? 4) искомое изображение встречается только раз в большом или его количество не определено? 5) масштаб искомого изображения неизменен? Самый простой случай: все паралельно, одномасштабно, содержится один раз и полностью. Наум приходит сразу несколько решений от простого перебора до рекурсивных процедур и пр. В более сложном случае надо вначале применять частотный анализ и т.п. математические алгоритмы (возможно использовать нейронные сети). |
| Автор: GePo 1.4.2003, 22:39 |
| Этот алгоритм самый быстрый для самого простого случая и для очень больших картинок, и зачастую когда ищется несколько разных картинок в одной большой, он все равно работает за то же время. И кстати для любого количества вхождений в большую картинку |
| Автор: December 2.4.2003, 05:51 | ||||||||||
| Джентльмены, вообще-то задача решена, то есть, премного благодарен, если вы мне помогаете, но всё уже позади. Есди же вы обсуждаете данный вопрос как абстрактную задачу, то вот как был поставлен вопрос с самого начала:
Да
Совпадает
Полностью
Не суть важно, где один, там и десять.
Да. Как показала практика, выигрыш в скорости за счёт использования ScanLine на порядок выше выигрыша от хитроумных алгоритмов. |
| Автор: esperanto 31.5.2003, 19:10 |
| вообще-все это ускоряется трансформом фурье быстрым |
| Автор: Crait 31.5.2003, 20:38 |
| Если можно, подробнее. |