Соответствие шаблонов - Template matching

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

Соответствие шаблонов[1] это техника в цифровая обработка изображений для поиска небольших частей изображения, соответствующих шаблону изображения. Может использоваться на производстве как часть контроля качества,[2] способ управлять мобильным роботом,[3] или как способ обнаружения краев на изображениях.[4]

Основные проблемы в задаче сопоставления шаблонов: окклюзия, обнаружение нежестких преобразований, изменения освещения и фона, беспорядок фона и изменения масштаба.[5]

Функциональный подход

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

Подход, основанный на характеристиках, основан на извлечении таких характеристик изображения, как формы, текстуры, цвета, для соответствия целевому изображению или кадру. В настоящее время этот подход достигается за счет использования Нейронные сети и Глубокое обучение классификаторы, такие как VGG,[6] AlexNet, ResNet. Глубокий Сверточные нейронные сети обрабатывать изображение, пропуская его через различные скрытые слои, и на каждом слое создавать вектор с классификационной информацией об изображении. Эти векторы извлекаются из сети и используются в качестве характеристик изображения. Извлечение признаков используя Глубокие нейронные сети чрезвычайно эффективен и поэтому является стандартом в современных алгоритмах сопоставления шаблонов.[7]

Этот метод считается более надежным и современным, поскольку он может сопоставлять шаблоны с нежесткими и расположенными вне плоскости. трансформация, это может соответствовать сильному фоновому беспорядку и изменениям освещения.[8][9][10]

Шаблонный подход

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

Отслеживание движения и обработка окклюзии

В случаях, когда шаблон не может обеспечить прямое соответствие, может быть полезно реализовать использование собственные подпространства - шаблоны, которые детализируют совпадающий объект при различных условиях, таких как различные перспективы, освещение, цветовые контрасты или приемлемые «позы» совпадающего объекта.[11] Например, если пользователь искал лицо, собственные подпространства могут состоять из изображений (шаблонов) лиц в разных положениях камеры, в разных условиях освещения или с разными выражениями.

Также возможно, что соответствующее изображение будет затемнено или закрыто объектом; в этих случаях неразумно предоставлять множество шаблонов для покрытия каждой возможной окклюзии. Например, изображение для поиска может быть игральной картой, и в некоторых изображениях для поиска карта закрыта пальцами того, кто держит карту, или другой картой поверх нее, или любым предметом перед камерой. в этом отношении. В случаях, когда объект является податливым или позируемым, движение также становится проблемой, а проблемы, связанные как с движением, так и с окклюзией, становятся неоднозначными.[12] В этих случаях одним из возможных решений является разделение изображения шаблона на несколько фрагментов изображения и выполнение сопоставления для каждого подразделения.

Деформируемые шаблоны в вычислительной анатомии

Дальнейшая информация: Вычислительная анатомия § Сопоставление плотных изображений в вычислительной анатомии

Сопоставление шаблонов - центральный инструмент в Вычислительная анатомия (CA). деформируемая шаблонная модель[13] моделирует пространство человеческих анатомий и орбит под групповым действием диффеоморфизмов. Сопоставление шаблонов возникает как проблема сопоставления неизвестного диффеоморфизма, действующего на шаблон, с целевым изображением.

Алгоритмы сопоставления шаблонов в CA стали называть Диффеоморфное метрическое отображение большой деформации (ЛДДММ); теперь есть алгоритмы сопоставления шаблонов LDDMM для сопоставления ориентиры, кривые, поверхности, объемы.

Сопоставление на основе шаблона объяснено с использованием взаимной корреляции или суммы абсолютных различий

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

Этот метод обычно реализуется путем выбора сначала части изображения для поиска для использования в качестве шаблона: мы будем называть изображение для поиска S (х, у), куда (х, у) представляют координаты каждого пикселя в поисковом изображении. Мы будем называть шаблон Т (х т, y т), куда (Икст, yт) представляют координаты каждого пикселя в шаблоне. Затем мы просто перемещаем центр (или начало) шаблона. Т (х т, y т) по каждому (х, у) наведите курсор на поисковое изображение и вычислите сумму произведений между коэффициентами в S (х, у) и Т (хт, yт) по всей площади, охватываемой шаблоном. Поскольку рассматриваются все возможные позиции шаблона относительно поискового изображения, позиция с наивысшей оценкой является лучшей позицией. Этот метод иногда называют 'Линейная пространственная фильтрация' и шаблон называется маска фильтра[нужна цитата ].

Другой способ справиться с проблемами перевода изображений с помощью сопоставления шаблонов - сравнить интенсивность пиксели, с использованием ГРУСТНЫЙ (Сумма абсолютных разностей ) мера.

Пиксель в поисковом изображении с координатами (Иксs, ys) имеет интенсивность яs(Иксs, ys) и пиксель в шаблоне с координатами (Икст, yт) имеет интенсивность ят(Икст, yт ). Таким образом абсолютная разница в яркости пикселей определяется как Разница (xs, ys, Икс т, y т) = | яs(Иксs, ys) - Ят(Икс т, y т) |.

Математическое представление идеи прохождения пикселей в поисковом изображении, когда мы переводим исходную точку шаблона в каждый пиксель и измеряем SAD, выглядит следующим образом:

Sряды и Scols обозначают строки и столбцы поискового изображения и Тряды и Тcols обозначают строки и столбцы изображения шаблона, соответственно. В этом методе наименьшая оценка SAD дает оценку наилучшего положения шаблона в изображении для поиска. Метод прост в реализации и понимании, но это один из самых медленных методов.

Выполнение

В этой простой реализации предполагается, что описанный выше метод применяется к серым изображениям: Вот почему Серый используется как интенсивность пикселей. Последняя позиция в этой реализации дает верхнее левое положение, в котором изображение шаблона лучше всего соответствует изображению для поиска.

minSAD = VALUE_MAX;// перебираем поисковое изображениеза ( size_t Икс = 0; Икс <= S_cols - T_cols; Икс++ ) {    за ( size_t у = 0; у <= S_rows - T_rows; у++ ) {        ГРУСТНЫЙ = 0.0;        // перебираем изображение шаблона        за ( size_t j = 0; j < T_cols; j++ )            за ( size_t я = 0; я < T_rows; я++ ) {                пиксель p_SearchIMG = S[у+я][Икс+j];                пиксель p_TemplateIMG = Т[я][j];		                ГРУСТНЫЙ += пресс( p_SearchIMG.Серый - p_TemplateIMG.Серый );            }        // сохраняем лучшую найденную позицию         если ( minSAD > ГРУСТНЫЙ ) {             minSAD = ГРУСТНЫЙ;            // дайте мне минимальное САД            позиция.bestRow = у;            позиция.bestCol = Икс;            позиция.bestSAD = ГРУСТНЫЙ;        }    }    }

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

Ускорение процесса

В прошлом этот тип пространственной фильтрации обычно использовался только в специализированных аппаратных решениях из-за вычислительной сложности операции,[14] однако мы можем уменьшить эту сложность, отфильтровав ее в частотной области изображения, что называется «фильтрацией в частотной области», это достигается за счет использования теорема свертки.

Другой способ ускорить процесс сопоставления - использовать пирамиду изображений. Это серия изображений в разных масштабах, которые формируются путем многократной фильтрации и субдискретизации исходного изображения для создания последовательности изображений с пониженным разрешением.[15] Затем в этих изображениях с более низким разрешением можно искать шаблон (с аналогичным уменьшенным разрешением), чтобы получить возможные начальные позиции для поиска в более крупных масштабах. Затем можно искать более крупные изображения в небольшом окне вокруг начальной позиции, чтобы найти наилучшее расположение шаблона.

Другие методы могут обрабатывать такие проблемы, как перевод, масштабирование, поворот изображения и даже все аффинные преобразования.[16][17][18]

Повышение точности сопоставления

В метод сопоставления можно внести улучшения, используя более одного шаблона (собственных подпространств), эти другие шаблоны могут иметь разные масштабы и поворот.

Также возможно повысить точность метода сопоставления путем гибридизации подходов на основе признаков и на основе шаблонов.[19] Естественно, для этого требуется, чтобы у изображений поиска и шаблонов были функции, которые достаточно очевидны для поддержки сопоставления функций.

Подобные методы

Другие похожие методы включают 'Стерео сопоставление ', 'Регистрация изображения ' и 'Масштабно-инвариантное преобразование признаков '.

Примеры использования

Сопоставление шаблонов имеет различные приложения и используется в таких областях, как распознавание лиц (см. система распознавания лиц ) и обработка медицинских изображений. Системы были разработаны и использовались в прошлом для подсчета количества лиц, которые проходят по части моста за определенное время. Другие системы включают автоматическое обнаружение кальцинированных узелков на цифровом рентгеновском снимке грудной клетки.[20]Недавно этот метод был реализован в геостатистическом моделировании, которое могло обеспечить быстрый алгоритм.[21]

Смотрите также

Рекомендации

  1. ^ Р. Брунелли, Методы сопоставления шаблонов в компьютерном зрении: теория и практика, Wiley, ISBN  978-0-470-51706-2, 2009 ([1] Книга TM)
  2. ^ Аксой, М. С .; Торкул, О .; Чедимоглу, И. Х. (2004). «Промышленная система визуального контроля, использующая индуктивное обучение». Журнал интеллектуального производства. 15 (4): 569–574. Дои:10.1023 / B: JIMS.0000034120.86709.8c. S2CID  35493679.
  3. ^ Кириаку, Теохарис, Гвидо Бугманн и Станислао Лаурия. "Визуальные городские процедуры навигации для роботов с устными инструкциями. »Робототехника и автономные системы 51.1 (30 апреля 2005 г.): 69-80. Расширенный академический как можно скорее. Томсон Гейл.
  4. ^ ВАН, ЧИН ЯН, к.т.н. «ОБНАРУЖЕНИЕ КРАЯ С ПОМОЩЬЮ СОГЛАСОВАНИЯ ШАБЛОНА (ОБРАБОТКА ИЗОБРАЖЕНИЯ, ПОРОГОВАЯ ЛОГИКА, АНАЛИЗ, ФИЛЬТРЫ)». Duke University, 1985, 288 страниц; AAT 8523046
  5. ^ Талми, Итамар; Мехрез, Рой; Зельник-Усадьба, Лихи (07.12.2016). «Соответствие шаблонов с деформируемым подобием разнообразия». arXiv:1612.02190 [cs.CV ].
  6. ^ «Репозиторий препринтов arXiv достиг отметки в миллион загрузок». Физика сегодня. 2014. Дои:10.1063 / pt.5.028530. ISSN  1945-0699.
  7. ^ Чжан, Ричард; Изола, Филипп; Эфрос, Алексей А .; Шехтман, Эли; Ван, Оливер (2018-01-11). «Неоправданная эффективность глубинных функций как метрики восприятия». arXiv:1801.03924 [cs.CV ].
  8. ^ Талми, Мечрез, Зельник-Усадьба (2016). «Соответствие шаблонов с деформируемым подобием разнообразия». arXiv:1612.02190 [cs.CV ].CS1 maint: несколько имен: список авторов (связь)
  9. ^ Ли, Юхай, Л. Цзянь, Т. Цзиньвэнь, Х. Хонбо. «Сопоставление быстро вращающегося шаблона на основе точечного объекта. » Труды SPIE 6043 (2005): 453-459. MIPPR 2005: SAR и обработка многоспектральных изображений.
  10. ^ Б. Сирмачек, К. Унсалан. «Обнаружение городских территорий и зданий с использованием ключевых точек SIFT и теории графов ”, IEEE Transactions on Geoscience and Remote Sensing, Vol.47 (4), pp. 1156-1167, April 2009.
  11. ^ Луис А. Матеос, Дэн Шао и Вальтер Г. Кропач. Расширение пирамиды нерегулярного графа для приближающегося объекта. ЦИАРП 2009: 885-891.
  12. ^ Ф. Жюри и М. Дом. Надежное сопоставление шаблонов в реальном времени. В Британской конференции по машинному зрению, страницы 123–131, 2002 г.
  13. ^ Christensen, G.E .; Rabbitt, R.D .; Миллер, М. (Октябрь 1996 г.). «Деформируемая шаблонная модель с использованием кинематики больших деформаций». IEEE Transactions по обработке изображений. 5 (10): 1435–1447. Дои:10.1109/83.536892. PMID  18290061.
  14. ^ Гонсалес, Р., Вудс, Р., Эддинс, С. "Цифровая обработка изображений с использованием Matlab "Прентис Холл", 2004 г.
  15. ^ Э. Х. Адельсон, К. Х. Андерсон, Дж. Р. Берген, П. Дж. Берт и Дж. М. Огден, Пирамидальные методы в обработке изображений http://web.mit.edu/persci/people/adelson/pub_pdfs/RCA84.pdf
  16. ^ Юань, По, M.S.E.E. «Система распознавания образов с инвариантным переводом, масштабом, поворотом и порогом». Техасский университет в Далласе, 1993 г., 62 страницы; AAT EP13780
  17. ^ Х. Ю. Ким и С. А. Араужу "Согласование с шаблоном шкалы серого, инвариантное к повороту, масштабированию, перемещению, яркости и контрастности, "IEEE Pacific-Rim Symposium on Image and Video Technology, Lecture Notes in Computer Science, vol. 4872, pp. 100-113, 2007.
  18. ^ Корман С., Райхман Д., Цур Г. и Авидан С. "FAsT-Match: быстрое сопоставление аффинных шаблонов ", CVPR2013.
  19. ^ К. Т. Юэн, М. Ризон, В. С. Сан и Т. К. Сеонг. «Особенности лица для распознавания лиц на основе сопоставления шаблонов. » Американский журнал инженерных и прикладных наук 3 (1): 899-903, 2010.
  20. ^ Эшли Абернити. «Автоматическое определение кальцинированных узелков у больных туберкулезом». Университетский колледж Лондона, 2007 г.
  21. ^ Тахмасеби П., Хезархани А., Сахими М., 2012 г., Многоточечное геостатистическое моделирование на основе функций взаимной корреляции, Вычислительные науки о Земле, 16 (3): 779-79742.

внешняя ссылка