Ускоренное сравнение с шаблоном / Теория распознавания образов / Recog.ru - Распознавание образов для программистов


Ускоренное сравнение с шаблоном

Здесь http://recog.ru/blog/opencv/57.htm показано, как использовать функции OpenCV cvMatchTemplate для сравнения с эталоном.
Недавно появилась статья «Tirui Wu, Alexander Toet Speed-Up Template Matching Through Integral Image Based Weak Classifiers // Journal of Pattern Recognition Research 1 (2014) 1-12.» (http://www.jprr.org/index.php/jprr/article/viewFile/516/193), в которой показано, как можно значительно ускорить процесс поиска шаблона.
Алгоритм работы следующий:
1. Шаблон и само изображение переводится к интегральному виду (т.е. в дальнейшем используются интегральные изображения).
2. Для шаблона вычисляется множество «слабых» бинарных блоков. Что такое «слабый» (weak) бинарный блок можно понять из следующего рисунка:

Т.е. меньше среднего означает -1, а больше или равно означает 1.
3. Установить окно на следующую позицию на сцене (на следующий пиксель, изначально естественно 0,0).
4. Если разница между средними значениями локального окна и средних значений шаблона превышает T, то перейти к этапу 3. Здесь имеется в виду, что по интегральному изображению средние значения (см. птичку на предыдущем рисунке) вычисляются очень быстро. И поэтому легко вычислить расхождения. Например, на реальном изображении будет 133 120 145 167 верхние блоки, тогда
T = |132-133|+|136-120|+|145-145|+|162-167|+…=1+16+0+5+…
5. Вычислить «слабые» бинарные блоки для окна и сравнить их со «слабыми» бинарными блоками на равенство.
6. Если общее количество несовпадений (в шаблоне 1, а в окне изображения -1 например) не превышает некоторого значения Lne, то значит текущая позиция считается кандидатом на правильное распознавание.
Lne вводится для того, чтобы сделать некоторую устойчивость к шумам, т.е. некоторые из блоков помечаются как возможно несовпадающие. На следующем рисунке показано 2 несовпадения Lne=2:

7. Перейти на этап 3, если еще не последняя позиция окна. Иначе на следующий этап.
8.Определить наилучший кандидат традиционным сравнением эталона с окнами кандидатов изображений.

Главное в этой работе то, что ускорение достигается за счет использование интегрального изображения – не нужно перебирать все пиксели для того, чтобы вычислить средние значения блоков. Об остальном – читайте оригинал статьи на английском.
  • 0
  • 25 декабря 2014, 18:44
  • vidikon

Комментарии (0)

RSS свернуть / развернуть

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