Соответствие шаблону

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

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

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

Этот подход на основе признаков часто более надежен, чем описанный ниже подход на основе шаблонов. Таким образом, он стал передовым методом сопоставления шаблонов, поскольку он может сопоставлять шаблоны с нежесткими и внеплоскостными преобразованиями , а также с высоким фоновым беспорядком и изменениями освещенности. ^{[7] [8] [9]}

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

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

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

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

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

Базовый метод сопоставления шаблонов, иногда называемый «линейной пространственной фильтрацией», использует фрагмент изображения (т. е. «шаблонное изображение» или «маску фильтра»), адаптированный к определенной особенности изображений поиска для обнаружения. ^{[ требуется ссылка ]} Этот метод можно легко применить к серым изображениям или изображениям с краями , где дополнительная переменная цвета либо отсутствует, либо не имеет значения. Методы перекрестной корреляции сравнивают сходство изображений поиска и шаблонов. Их выходные данные должны быть самыми высокими в местах, где структура изображения соответствует структуре шаблона, т. е. где большие значения изображения поиска умножаются на большие значения изображения шаблона.

Этот метод обычно реализуется путем выбора части изображения поиска для использования в качестве шаблона. Пусть представляет значение пикселя изображения поиска, где представляет координаты пикселя в изображении поиска. Для простоты предположим, что значения пикселей являются скалярными, как в изображении в оттенках серого . Аналогично, пусть представляет значение пикселя шаблона, где представляет координаты пикселя в изображении шаблона. Чтобы применить фильтр, просто переместите центр (или начало координат) изображения шаблона по каждой точке в изображении поиска и вычислите сумму произведений, аналогичную скалярному произведению , между значениями пикселей в изображениях поиска и шаблона по всей области, охватываемой шаблоном. Более формально, если является центром (или началом координат) изображения шаблона, то кросс-корреляция в каждой точке в изображении поиска может быть вычислена как: Для удобства обозначает как значения пикселей изображения шаблона, так и его домен , границы шаблона. Обратите внимание, что рассматриваются все возможные положения шаблона относительно изображения поиска. Поскольку значения взаимной корреляции максимальны, когда значения пикселей поиска и шаблона совпадают, наилучшая совпадающая позиция соответствует максимальному значению более .${\displaystyle S(x,y)}$${\displaystyle (x,y)}$${\textstyle T(x_{t},y_{t})}$${\textstyle (x_{t},y_{t})}$${\displaystyle (0,0)}$${\displaystyle T\звезда S}$${\displaystyle (x,y)}$$${\displaystyle (T\star S)(x,y)=\sum _{(x_{t},y_{t})\in T}T(x_{t},y_{t})\cdot S(x_{t}+x,y_{t}+y)}$$${\displaystyle Т}$${\displaystyle (x_{м},y_{м})}$${\displaystyle T\звезда S}$${\displaystyle S}$

Другой способ решения проблем перевода изображений с использованием сопоставления шаблонов — сравнение интенсивностей пикселей с использованием меры суммы абсолютных разностей (SAD). Чтобы сформулировать это, пусть и обозначим интенсивность света пикселей в поисковом и шаблонном изображениях с координатами и соответственно. Затем, перемещая центр (или начало координат) шаблона в точку на поисковом изображении, как и прежде, сумма абсолютных разностей между интенсивностями пикселей шаблона и поиска в этой точке равна: При использовании этой меры наименьшее значение SAD дает наилучшее положение для шаблона, а не наибольшее, как при кросс-корреляции. SAD, как правило, относительно прост в реализации и понимании, но также, как правило, относительно медленен в выполнении. Ниже приведена простая реализация сопоставления шаблонов SAD на C++ .${\displaystyle I_{S}(x_{s},y_{s})}$${\displaystyle I_{T}(x_{t},y_{t})}$${\displaystyle (x_{s},y_{s})}$${\displaystyle (x_{t},y_{t})}$${\displaystyle (x,y)}$$${\displaystyle SAD(x,y)=\sum _{(x_{t},y_{t})\in T}\left\vert I_{T}(x_{t},y_{t})-I_{S}(x_{t}+x,y_{t}+y)\right\vert }$$

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

minSAD = VALUE_MAX ;  // цикл по искомому изображению for ( size_t x = 0 ; x <= S_cols - T_cols ; x ++ ) { for ( size_t y = 0 ; y <= S_rows - T_rows ; y ++ ) { SAD = 0.0 ;                               // цикл по шаблону изображения for ( size_t j = 0 ; j < T_cols ; j ++ ) for ( size_t i = 0 ; i < T_rows ; i ++ ) {                        пиксель p_SearchIMG = S [ y + i ][ x + j ]; пиксель p_TemplateIMG = T [ i ][ j ]; SAD += abs ( p_SearchIMG . Grey - p_TemplateIMG . Grey ); }                // сохранить лучшую найденную позицию if ( minSAD > SAD ) { minSAD = SAD ; // дать мне min SAD position . bestRow = y ; position . bestCol = x ; position . bestSAD = SAD ; } } }                        

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

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

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

Другие методы могут решать такие задачи, как перемещение, масштабирование, поворот изображения и даже все аффинные преобразования. ^{[15] [16] [17]}

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

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

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

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

• Система распознавания лиц
• Распознавание образов
• Компьютерное зрение
• Эластичное соответствие

• Сопоставление шаблонов в OpenCV
• Визуальное распознавание объектов с использованием сопоставления с шаблоном
• Демонстрационная программа сопоставления шаблонов с инвариантами вращения, масштабирования и трансляции
• перспективно-инвариантное сопоставление шаблонов
• Обширная библиография по шаблонам до 2009 г.