Алгоритмы, методы, исходники / Форум

Алгоритмы, методы, исходники / Форум (http://forum.algolist.ru/)
-   Обработка изображений, звук, графика (http://forum.algolist.ru/algorithm-image-graphics/)
-   -   Свертка двух изображений для поиска фрагмента в рисунке (http://forum.algolist.ru/algorithm-image-graphics/1644-svertka-dvuh-izobrajenii-dlia-poiska-fragmenta-v-risunke.html)

гость 17.02.2009 23:52

Свертка двух изображений для поиска фрагмента в рисунке
 
Здравствуйте!

Сразу оговорюсь, что ранее обработкой изображений никогда не занимался, поэтому прошу прощения, если вопрос совсем детский.
Основная задача: найти фрагмент изображения на картинке. Фрагмент заранее известен, не меняется, и всегда присутствует на основной картинке. Он не вращается и не масштабируется. Время выполнения не сильно критично.
Для решения поставленной задачи пошел "в лоб": делаю свертку основного изображения и искомого ядра, причен не через БПФ, а "по определению" через сумму произведений. Ядро размером 50х50. Знаю, что быстрее было бы делать БПФ, но решил попробовать написать наиболее простой вариант.
Как делал. Ядро и картинку привожу в greyscale по байту на пиксел. 255 - максимальное значение. Делаю свертку шаблона с ядром 3х3 (центр 8, остальные -1) для выделения контуров. Свертка делается обычными вложенными циклами с последющей проверкой на вылет в отрицательный диапазон. Все отрицательные цисла заменяю на 0. Далее ищу максимум по ВСЕМ пикселям результата и делаю нормировку каждого пикселя: val = val / max * 255;
Полученное ядро аналогичным образом "сворачиваю" с основной картинкой и опять нормирую до 255.
Результат.
В тех местах, где искомые шаблоны действительно присутствуют, я вижу "пики" с ярко выраженным центральным пикселем амплитуды порядка 180ед. Ближайшие к пику точки около 120ед. Все как учили.
Внимание, вопрос! Очень смущает, что если на исходной картинке присутствуют большие (больше ядра) области, залитые белым (ну или почти белым), то и после свертки с ядром эти области так и остаются белыми (ну ессно размытыми). Причем уровень белого выше 200!!!
Сам шаблон поиска у меня имеет яркость порядка 100, после выделения контуров он становится весь черный с практическими белыми контурами.
Как же мне теперь искать ту самую точку "пика", которая "однозначно" должна говорить о вхождении шаблона в картинку в данной точке, если у меня есть целые области, залитые белым и при том не содержащие искомого шаблона???
Что я не так делаю??? Я думал, что после свертки вся картинка будет достаточно темная и светлые места будут ТОЛЬКО там, где картинка содержит шаблон :(
Может у меня где-то идеологическая ошибка? Или все правильно и свертка действительно "не ищет" в светлых областях темные шаблоны? Или все правильно и я должен искать именно "пики" а на области не обращать внимания??? И как быть с тем, что "высота" правильного "пика" получается меньше чем высота обманного "плато"?

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

гость2 18.02.2009 04:41

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

Цитата:

Очень смущает, что если на исходной картинке присутствуют большие (больше ядра) области, залитые белым (ну или почти белым), то и после свертки с ядром эти области так и остаются белыми
Разве применения фильтра для выделения контуров (ваше ядро 3x3) эти области не должны стать абсолютно черными?

Как я понимаю, вы вычисляете степень похожести шаблона и некоторого фрагмента картинки по формуле: сумма x[i]*y[i] по всем пикселям i (где x[i] - яркость шаблона в точке i, y[i] - яркость картинки), т.е. это просто скалярное произведение. Возможно, ее следует заменить на, например, сумму абсолютных разностей яркостей пикселей (сумма abs(x[i]-y[i])), или сумму квадратов разностей (сумма (x[i]-y[i])^2). Сумму квадратов можно расписать как (сумма x[i]^2) + (сумма y[i]^2) - 2*(сумма x[i]*y[i]), и поэтому ее тоже можно будет быстро вычислить через FFT.

MBo 18.02.2009 06:20

Не пробовали использовать не свертку, а корреляцию?

гость 18.02.2009 13:56

Цитата:

Сообщение от гость2 (Сообщение 6222)
Разве применения фильтра для выделения контуров (ваше ядро 3x3) эти области не должны стать абсолютно черными?

По классике, нужно применить выделение контуров и к картинке и шаблону, а потом результаты опять "свернуть". Но свертка обладает ассоциативным свойством, т.е., перегруппировав операции, мы можем выделение границ к картинке не применять (зачем же лишний раз комп грузить?), а применить его к ядру дважды. Но, второе применение того же выделения контура ничего не дает (почти). Поэтому считается, что достаточно выделить контуры только у ядра.

Цитата:

Сообщение от MBo
Не пробовали использовать не свертку, а корреляцию?

Простите, а что это? Я по глупости своей и думал, что свертка это и есть способ измерения корреляции двух изображений :(

Цитата:

Сообщение от гость2 (Сообщение 6222)
т.е. это просто скалярное произведение

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

гость 18.02.2009 14:10

Цитата:

Сообщение от MBo (Сообщение 6223)
Не пробовали использовать не свертку, а корреляцию?

Перепутал термины. Если я правильно понимаю, то именно корреляцию, а не свертку, я и использую. Т.е. я считаю просто скалярные произведения двух картинок, причем не переворачивую ядро. Оно ориентировано точно так же, как и на исследуемой картинке. Если я правильно понял, классическая свертка требует перевернуть ядро на 180 градусов. Я пробовал это сделать - белые пятна остаются, но пики в местах совпадения не появляются вообще.

MBo 18.02.2009 14:14

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


Вот здесь и то, и другое описано:
http://megalib.com/books/1809/part.pdf
850 к

MBo 18.02.2009 14:17

Когда писал, еще не видел последнего ответа.
Да, с неперевернутым ядром - корреляция, все верно

MBo 18.02.2009 16:08

В книге Дуда, Харт предлагается следующее решение проблемы белых областей - использовать нормированную функцию корреляции, разделить корреляцию на Sqrt(Sum(g(x,y)^2)) по области приложения шаблона.
Я попробовал, максимум ненормированной корреляции был в белой области (в верхней строке), а с нормировкой - там, где надо (белая точка указывает найденный максимум корреляции - место левого угла фрагмента в большой картинке).
http://slil.ru/26783541
Думаю, есть и другие методы борьбы с этим эффектом.

гость 19.02.2009 11:04

Цитата:

Сообщение от MBo (Сообщение 6231)
В книге Дуда, Харт предлагается следующее решение проблемы белых областей - использовать нормированную функцию корреляции, разделить корреляцию на Sqrt(Sum(g(x,y)^2)) по области приложения шаблона.
Я попробовал, максимум ненормированной корреляции был в белой области (в верхней строке), а с нормировкой - там, где надо (белая точка указывает найденный максимум корреляции - место левого угла фрагмента в большой картинке).
http://slil.ru/26783541
Думаю, есть и другие методы борьбы с этим эффектом.

Огромное спасибо! Буду пробовать.

гость 19.02.2009 12:33

На другом форуме (http://electronix.ru/forum/index.php?showtopic=59466) подсказали, что надо дать в шаблон смещение, чтобы сумма эламантов была равна нулю. После этого оказалось, что выделение контуров для шаблона при корреляции только мешает. Надо считать произведения "чистых" образов. Зато все заработало отлично. Там же, кстати, прикреплены файлы с результатом.

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


Часовой пояс GMT +4, время: 08:32.