Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.02.2009, 23:52
гость

 
Сообщений: n/a

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

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

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

 
Сообщений: n/a

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

Цитата:
Очень смущает, что если на исходной картинке присутствуют большие (больше ядра) области, залитые белым (ну или почти белым), то и после свертки с ядром эти области так и остаются белыми
Разве применения фильтра для выделения контуров (ваше ядро 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.
  #3  
Старый 18.02.2009, 06:20
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Не пробовали использовать не свертку, а корреляцию?
  #4  
Старый 18.02.2009, 13:56
гость

 
Сообщений: n/a

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

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

Сообщение от гость2 Посмотреть сообщение
т.е. это просто скалярное произведение
Да, это именно оно и есть. За советы спасибо, попробую. Но хотелось бы узнать почему не сработал классический алгоритм. Или он правильно сработал, а я от него жду слишком многого?
  #5  
Старый 18.02.2009, 14:10
гость

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
Не пробовали использовать не свертку, а корреляцию?
Перепутал термины. Если я правильно понимаю, то именно корреляцию, а не свертку, я и использую. Т.е. я считаю просто скалярные произведения двух картинок, причем не переворачивую ядро. Оно ориентировано точно так же, как и на исследуемой картинке. Если я правильно понял, классическая свертка требует перевернуть ядро на 180 градусов. Я пробовал это сделать - белые пятна остаются, но пики в местах совпадения не появляются вообще.
  #6  
Старый 18.02.2009, 14:14
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

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


Вот здесь и то, и другое описано:
http://megalib.com/books/1809/part.pdf
850 к
  #7  
Старый 18.02.2009, 14:17
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Когда писал, еще не видел последнего ответа.
Да, с неперевернутым ядром - корреляция, все верно
  #8  
Старый 18.02.2009, 16:08
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

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

 
Сообщений: n/a

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

 
Сообщений: n/a

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

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
определение точки на графическом рисунке карты sasha_trn Математические алгоритмы (другое) 3 17.02.2009 08:13
Алгоритмы шумов для изображений pretorian Реализация, исходники, языки 1 09.05.2008 14:14
Инженер по обработке изображений. Алексей Минаков Работа 2 21.01.2008 11:06
специалист по цифровой обработке изображений volodya Работа 0 06.07.2007 12:08
свертка через бпф GraphD Обработка изображений, звук, графика 11 01.01.2007 01:54