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

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

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

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

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

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

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

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

Общие проблемы

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

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

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

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

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

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

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

Этот метод обычно реализуется путем выбора части изображения поиска для использования в качестве шаблона. Позволять $S(x,y)$ представляют значение пикселя поискового изображения, где $(x,y)$ представляет координаты пикселя в искомом изображении. Для простоты предположим, что значения пикселей являются скалярными, как в изображении в оттенках серого . Аналогично, пусть ${\textstyle T(x_{t},y_{t})}$ представляют значение пикселя шаблона, где ${\textstyle (x_{t},y_{t})}$ представляет координаты пикселя в шаблонном изображении. Чтобы применить фильтр, просто переместите центр (или начало координат) изображения шаблона по каждой точке искомого изображения и вычислите сумму произведений, аналогичную скалярному произведению , между значениями пикселей в поиске и изображениями шаблона по всему область, охватываемая шаблоном. Более формально, если $(0,0)$ является центром (или началом координат) изображения шаблона, тогда взаимная корреляция $T\star S$ в каждой точке $(x,y)$ в изображении поиска можно вычислить как: $(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)$ Для удобства, $T$ обозначает как значения пикселей изображения шаблона, так и его домен , границы шаблона. Обратите внимание, что учитываются все возможные положения шаблона относительно искомого изображения. Поскольку значения взаимной корреляции являются наибольшими, когда значения пикселей поиска и шаблона совпадают, наилучшая совпадающая позиция $(x_{m},y_{m})$ соответствует максимальному значению $T\star S$ над $S$ .

Другой способ решения проблем перевода изображений с использованием сопоставления шаблонов — это сравнение интенсивностей пикселей с использованием меры суммы абсолютных разностей (SAD). Чтобы сформулировать это, пусть $I_{S}(x_{s},y_{s})$ и $I_{T}(x_{t},y_{t})$ обозначаем интенсивность освещенности пикселей в поисковых и шаблонных изображениях с координатами $(x_{s},y_{s})$ и $(x_{t},y_{t})$ , соответственно. Затем, переместив центр (или начало координат) шаблона в точку $(x,y)$ в поисковом изображении, как и раньше, сумма абсолютных разностей между интенсивностями шаблона и поискового пикселя в этой точке равна: $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$ При использовании этого показателя наименьшее значение SAD дает наилучшее положение шаблона, а не наибольшую величину, как при перекрестной корреляции. SAD, как правило, относительно прост в реализации и понимании, но также имеет тенденцию относительно медленно выполняться. простая реализация сопоставления шаблонов SAD на языке C++ Ниже приведена .

Выполнение

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

minSAD = VALUE_MAX;

// loop through the search image
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;

        // loop through the template image
        for ( size_t j = 0; j < T_cols; j++ )
            for ( size_t i = 0; i < T_rows; i++ ) {

                pixel p_SearchIMG = S[y+i][x+j];
                pixel p_TemplateIMG = T[i][j];
		
                SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
            }

        // save the best found position 
        if ( minSAD > SAD ) { 
            minSAD = SAD;
            // give me min SAD
            position.bestRow = y;
            position.bestCol = x;
            position.bestSAD = SAD;
        }
    }
    
}

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Р. Брунелли, Методы сопоставления шаблонов в компьютерном зрении: теория и практика , Wiley, ISBN 978-0-470-51706-2 , 2009 г. ( [1] Книга ТМ)
^ Аксой, МС; Торкул, О.; Чедимоглу, И.Х. (2004). «Промышленная система визуального контроля, использующая индуктивное обучение». Журнал интеллектуального производства . 15 (4): 569–574. дои : 10.1023/B:JIMS.0000034120.86709.8c . S2CID 35493679 .
^ Кириаку, Теохарис, Гвидо Бугманн и Станислао Лаурия. « Процедуры городской навигации на основе зрения для роботов с устным управлением ». Робототехника и автономные системы 51.1 (30 апреля 2005 г.): 69-80. Расширенное академическое обучение как можно скорее. Томсон Гейл.
^ ВАН, ЧИНГ ЯН, доктор философии. «ОБНАРУЖЕНИЕ КРАЕВ С ИСПОЛЬЗОВАНИЕМ СООТВЕТСТВИЯ ШАБЛОНОВ (ОБРАБОТКА ИЗОБРАЖЕНИЙ, ПОРОГОВАЯ ЛОГИКА, АНАЛИЗ, ФИЛЬТРЫ)». Университет Дьюка, 1985 г., 288 страниц; ААТ 8523046
^ Талми, Итамар; Мечрез, Рой; Зельник-Усадьба, Лихи (07.12.2016). «Сопоставление шаблонов с деформируемым разнообразием и сходством». arXiv : 1612.02190 [ cs.CV ].
^ Чжан, Ричард; Изола, Филипп; Эфрос, Алексей А.; Шехтман, Эли; Ван, Оливер (11 января 2018 г.). «Необоснованная эффективность глубоких функций как показателя восприятия». arXiv : 1801.03924 [ cs.CV ].
^ Талми, Мечрез, Зельник-Усадьба (2016). «Сопоставление шаблонов с деформируемым разнообразием и сходством». arXiv : 1612.02190 [ cs.CV ]. {{cite arXiv}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Ли, Юхай, Л. Цзянь, Т. Джинвэнь, С. Хонбо. « Быстро вращающееся сопоставление шаблонов на основе точечных объектов ». Труды SPIE 6043 (2005): 453-459. MIPPR 2005: РСА и обработка мультиспектральных изображений.
^ Б. Сирмачек, К. Унсалан. « Обнаружение городских территорий и зданий с использованием ключевых точек SIFT и теории графов », IEEE Transactions on Geoscience and Remote Sensing, Vol.47 (4), стр. 1156-1167, апрель 2009 г.
^ Луис А. Матеос, Дэн Шао и Уолтер Г. Кропач. Развертывание пирамиды нерегулярного графа для приближающегося объекта . CIARP 2009: 885-891.
^ Ф. Жюри и М. Дом. Надежное сопоставление шаблонов в режиме реального времени . На Британской конференции по машинному зрению, страницы 123–131, 2002 г.
^ Кристенсен, GE; Рэббитт, РД; Миллер, Мичиган (октябрь 1996 г.). «Деформируемая модель шаблона с использованием кинематики большой деформации». Транзакции IEEE при обработке изображений . 5 (10): 1435–1447. дои : 10.1109/83.536892 . ПМИД 18290061 .
^ Гонсалес Р., Вудс Р., Эддинс С. « Цифровая обработка изображений с использованием Matlab » Прентис Холл, 2004 г.
^ Э. Х. Адельсон, Ч. Х. Андерсон, Дж. Р. Берген, П. Дж. Берт и Дж. М. Огден, Пирамидальные методы обработки изображений http://web.mit.edu/persci/people/adelson/pub_pdfs/RCA84.pdf
^ Юань, По, MSEE «Инвариантная система распознавания образов перевода, масштабирования, вращения и порога». Техасский университет в Далласе, 1993 г., 62 страницы; ААТ EP13780
^ HY Ким и С.А. Араужо, « Инвариант сопоставления шаблонов в оттенках серого с вращением, масштабом, перемещением, яркостью и контрастностью », Тихоокеанский симпозиум IEEE по технологиям изображений и видео, Конспекты лекций по информатике, том. 4872, стр. 100–113, 2007.
^ Корман С., Райхман Д., Цур Г. и Авидан С., « FAsT-Match: быстрое сопоставление аффинных шаблонов », CVPR2013.
^ CT Yuen, M. Rizon, WS San и TC Seong. « Черты лица для распознавания лиц на основе сопоставления шаблонов ». Американский журнал инженерных и прикладных наук 3 (1): 899-903, 2010.
^ Эшли Абернити. «Автоматическое обнаружение кальцинированных узелков у больных туберкулезом». Университетский колледж Лондона, 2007 г.
^ Тахмасеби П., Хезархани А., Сахими М., 2012, Многоточечное геостатистическое моделирование на основе функций взаимной корреляции , Computational Geosciences, 16(3):779-79742.

Внешние ссылки

[1] Р. Брунелли, Методы сопоставления шаблонов в компьютерном зрении: теория и практика , Wiley, ISBN 978-0-470-51706-2 , 2009 г. ( [1] Книга ТМ)

[2] Аксой, МС; Торкул, О.; Чедимоглу, И.Х. (2004). «Промышленная система визуального контроля, использующая индуктивное обучение». Журнал интеллектуального производства . 15 (4): 569–574. дои : 10.1023/B:JIMS.0000034120.86709.8c . S2CID 35493679 .

[3] Кириаку, Теохарис, Гвидо Бугманн и Станислао Лаурия. « Процедуры городской навигации на основе зрения для роботов с устным управлением ». Робототехника и автономные системы 51.1 (30 апреля 2005 г.): 69-80. Расширенное академическое обучение как можно скорее. Томсон Гейл.

[4] ВАН, ЧИНГ ЯН, доктор философии. «ОБНАРУЖЕНИЕ КРАЕВ С ИСПОЛЬЗОВАНИЕМ СООТВЕТСТВИЯ ШАБЛОНОВ (ОБРАБОТКА ИЗОБРАЖЕНИЙ, ПОРОГОВАЯ ЛОГИКА, АНАЛИЗ, ФИЛЬТРЫ)». Университет Дьюка, 1985 г., 288 страниц; ААТ 8523046

[5] Талми, Итамар; Мечрез, Рой; Зельник-Усадьба, Лихи (07.12.2016). «Сопоставление шаблонов с деформируемым разнообразием и сходством». arXiv : 1612.02190 [ cs.CV ].

[6] Чжан, Ричард; Изола, Филипп; Эфрос, Алексей А.; Шехтман, Эли; Ван, Оливер (11 января 2018 г.). «Необоснованная эффективность глубоких функций как показателя восприятия». arXiv : 1801.03924 [ cs.CV ].

[7] Талми, Мечрез, Зельник-Усадьба (2016). «Сопоставление шаблонов с деформируемым разнообразием и сходством». arXiv : 1612.02190 [ cs.CV ]. {{cite arXiv}}: CS1 maint: несколько имен: список авторов ( ссылка )

[8] Ли, Юхай, Л. Цзянь, Т. Джинвэнь, С. Хонбо. « Быстро вращающееся сопоставление шаблонов на основе точечных объектов ». Труды SPIE 6043 (2005): 453-459. MIPPR 2005: РСА и обработка мультиспектральных изображений.

[9] Б. Сирмачек, К. Унсалан. « Обнаружение городских территорий и зданий с использованием ключевых точек SIFT и теории графов », IEEE Transactions on Geoscience and Remote Sensing, Vol.47 (4), стр. 1156-1167, апрель 2009 г.

[10] Луис А. Матеос, Дэн Шао и Уолтер Г. Кропач. Развертывание пирамиды нерегулярного графа для приближающегося объекта . CIARP 2009: 885-891.

[11] Ф. Жюри и М. Дом. Надежное сопоставление шаблонов в режиме реального времени . На Британской конференции по машинному зрению, страницы 123–131, 2002 г.

[12] Кристенсен, GE; Рэббитт, РД; Миллер, Мичиган (октябрь 1996 г.). «Деформируемая модель шаблона с использованием кинематики большой деформации». Транзакции IEEE при обработке изображений . 5 (10): 1435–1447. дои : 10.1109/83.536892 . ПМИД 18290061 .

[13] Гонсалес Р., Вудс Р., Эддинс С. « Цифровая обработка изображений с использованием Matlab » Прентис Холл, 2004 г.

[14] Э. Х. Адельсон, Ч. Х. Андерсон, Дж. Р. Берген, П. Дж. Берт и Дж. М. Огден, Пирамидальные методы обработки изображений http://web.mit.edu/persci/people/adelson/pub_pdfs/RCA84.pdf

[15] Юань, По, MSEE «Инвариантная система распознавания образов перевода, масштабирования, вращения и порога». Техасский университет в Далласе, 1993 г., 62 страницы; ААТ EP13780

[16] HY Ким и С.А. Араужо, « Инвариант сопоставления шаблонов в оттенках серого с вращением, масштабом, перемещением, яркостью и контрастностью », Тихоокеанский симпозиум IEEE по технологиям изображений и видео, Конспекты лекций по информатике, том. 4872, стр. 100–113, 2007.

[17] Корман С., Райхман Д., Цур Г. и Авидан С., « FAsT-Match: быстрое сопоставление аффинных шаблонов », CVPR2013.

[18] CT Yuen, M. Rizon, WS San и TC Seong. « Черты лица для распознавания лиц на основе сопоставления шаблонов ». Американский журнал инженерных и прикладных наук 3 (1): 899-903, 2010.

[19] Эшли Абернити. «Автоматическое обнаружение кальцинированных узелков у больных туберкулезом». Университетский колледж Лондона, 2007 г.

[20] Тахмасеби П., Хезархани А., Сахими М., 2012, Многоточечное геостатистическое моделирование на основе функций взаимной корреляции , Computational Geosciences, 16(3):779-79742.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]