Все режимы сопоставления с шаблоном можно классифицировать примерно как плотную (то есть пиксельную) метрику сходства или, что эквивалентно, но обратно, метрику расстояния между изображениями.
Как правило, у вас будет два изображения, и вы хотите их сравнить. Вне зависимости, сопоставление с шаблоном не помогает напрямую сопоставить масштабированные, повернутые или деформированные объекты. Сопоставление шаблонов строго связано с измерением сходства двух изображений в точности так, как они выглядят. Однако фактические метрики, используемые здесь, используются повсеместно в компьютерном зрении, в том числе для поиска преобразований между изображениями ... просто обычно в дополнение идут более сложные шаги (например, градиентный спуск, чтобы найти оптимальные параметры преобразования). Есть много вариантов для метрик расстояния, и они обычно имеют свои плюсы и минусы в зависимости от приложения.
Сумма абсолютных разностей (SAD)
Для первого старта самая основная метрика расстояния - это просто абсолютная разница между двумя значениями, то есть d(x, y) = abs(x - y). Для изображений простой способ расширить это на единичные значения - это просто суммировать все эти расстояния по пикселям, что приводит к метрике суммы абсолютных разностей (SAD);он также известен как Манхэттен или расстояние такси и определяет L1 норма . Досадно, что это не реализовано в качестве одного из режимов сопоставления шаблонов OpenCV, но все равно важно в этом обсуждении как сравнение с SSD.
В сценарии сопоставления шаблонов вы перемещаете шаблон по нескольким местам и просто находитегде наименьшая разница происходит. Это эквивалентно вопросу, какой индекс ближайшего к 5 значения находится в массиве [1, 4, 9]. Вы берете абсолютную разницу каждого значения в массиве с 5, а индекс 1 имеет наименьшую разницу, так что это местоположение наиболее близкого совпадения. Конечно, в шаблоне сопоставления значение не 5, а массив, а изображение - это большой массив.
Сумма квадратов разностей (SSD): TM_SQDIFF
Интересная особенностьметрика SAD заключается в том, что она не наказывает действительно большие различия, а не кучу действительно небольших различий. Допустим, мы хотим вычислить d(a, b) и d(a, c) со следующими векторами:
a = [1, 2, 3]
b = [4, 5, 6]
c = [1, 2, 12]
По элементам, принимая суммы абсолютных разностей, мы видим
SAD(a, b) = 3 + 3 + 3 = 9 = 0 + 0 + 9 = SAD(a, c)
В некоторыхприложения, может быть, это не имеет значения. Но в других приложениях вы можете захотеть, чтобы эти два расстояния на самом деле были совершенно разными. Возведение в квадрат различий, вместо того, чтобы брать их абсолютное значение, штрафует значения, которые находятся дальше от того, что вы ожидаете - это делает изображения на больше отдаленными с ростом разницы в значении. Это сопоставляет больше с тем, как кто-то может объяснить оценку как way off, даже если по значению это на самом деле не , что distant. Сумма квадратичных разностей (SSD) эквивалентна квадрату евклидова расстояния , функции расстояния для L2 нормы . С SSD мы видим, что наши два расстояния теперь совершенно разные:
SSD(a, b) = 3^2 + 3^2 + 3^2 = 27 != 81 = 0^2 + 0^2 + 9^2 = SSD(a, c)
Вы можете видеть, что L1 норма иногда называется робастная норма . Именно потому, что одна точка ошибки не будет увеличивать расстояние больше, чем сама ошибка. Но, конечно, с SSD, выброс сделает расстояние намного больше. Поэтому, если ваши данные в некоторой степени склонны к нескольким значениям, которые находятся очень далеко, обратите внимание, что SSD, вероятно, не является хорошим показателем подобия для вас. Хорошим примером может быть сравнение изображений, которые могут быть переэкспонированы. В какой-то части изображения у вас может быть просто белое небо, а другое совсем не белое, и вы получите огромное расстояние между изображениями.
Как SAD, так и SSD имеют минимальное расстояние:0, когда два сравниваемых изображения идентичны. Они оба всегда неотрицательны, поскольку абсолютные или квадратные различия всегда неотрицательны.
Кросс-корреляция (CC): TM_CCORR
SAD и SSD - это, как правило, дискретные метрики, поэтому они являются естественным фактором для дискретизированных сигналов, таких как изображения. Однако взаимная корреляция применима и к непрерывным и, следовательно, аналоговым сигналам, что является частью ее повсеместного распространения при обработке сигналов. В широком смысле попытка обнаружить наличие шаблона внутри сигнала называется согласованным фильтром , и вы можете в основном думать о нем как о непрерывном аналоге сопоставления с шаблоном.
Кросс-корреляция просто умножает два изображения вместе. Вы можете себе представить, что если два сигнала выстроятся в линию точно, их умножение просто выровняет шаблон. Если они не выстроены в ряд, значит, продукт будет меньше. Таким образом, место, где продукт максимизируется, - это место, где они выстраиваются наилучшим образом. Однако существует проблема с взаимной корреляцией в том случае, если вы используете ее в качестве метрики подобия сигналов, в которых вы не уверены, что они связаны, и это обычно показано в следующем примере. Предположим, у вас есть три массива:
a = [2, 600, 12]
b = [v, v, v]
c = [2v, 2v, 2v]
В общем, нет очевидной корреляции между a и b, * a и c. И вообще, a не должно коррелировать больше с b, чем с c. Но это продукт, и, следовательно, ccorr(a, c) = 2*ccorr(a, b). Так что это не идеально для того, чтобы пытаться найти шаблон внутри большего изображения. А поскольку мы имеем дело с дискретными цифровыми сигналами, которые имеют определенное максимальное значение (изображения), это означает, что ярко-белый участок изображения в основном всегда будет иметь максимальную корреляцию. Из-за этой проблемы TM_CCORR не особенно полезен в качестве метода сопоставления с шаблоном.
Средняя смещенная взаимная корреляция (коэффициент корреляции Пирсона): TM_CCOEFF
Один простой способ решения проблемыкорреляция с яркими пятнами - это просто вычесть среднее значение, прежде чем сравнивать сигналы. Таким образом, сигналы, которые просто сдвинуты, имеют ту же корреляцию, что и сигналы без сдвига. И это имеет смысл с нашей интуицией - сигналы, которые изменяются вместе, коррелированы.
Нормализация: TM_SQDIFF_NORMED, TM_CCORR_NORMED, TM_CCOEFF_NORMED
Все методы в OpenCV нормализованы одинаково. Точка нормализации - не , чтобы дать уверенность / вероятность, но дать метрику, которую вы можете сравнить с шаблонами разных размеров или со значениями в разных масштабах. Например, скажем, мы хотим выяснить, есть ли объект на изображении, и у нас есть два разных шаблона этого объекта. Два разных шаблона имеют разные размеры. Мы могли бы просто нормализовать по количеству пикселей, что сработало бы для сравнения шаблонов разных размеров. Тем не менее, скажем, мои шаблоны на самом деле сильно отличаются по интенсивности, так как один имеет гораздо более высокую дисперсию значений пикселей, чем другой. Как правило, в этом случае вы делите на стандартное отклонение (квадратный корень из суммы квадратов разностей от среднего). OpenCV делает это с помощью метода TM_CCOEFF_NORMED, поскольку квадратичная сумма средних разностей равна дисперсии, но другие методы не имеют среднего смещения, поэтому масштабирование - это всего лишь мера суммызначения изображения. В любом случае, результат похож, вы хотите масштабировать что-то, что связано с интенсивностью используемых исправлений изображения.
Другие показатели
Существуют и другие полезные метрики, которые OpenCV не предоставляет. Matlab предоставляет SAD, а также метрику максимальной абсолютной разности (MaxAD), которая также известна как метрика равномерного расстояния и дает L∞-норму . По сути, вы берете максимальную абсолютную разницу вместо их суммы. Другие используемые метрики обычно отображаются в настройках оптимизации, например, улучшенный коэффициент корреляции , который сначала был предложен для стереофонического согласования, а затем расширен для общего выравнивания. Этот метод используется в OpenCV, но не для сопоставления с шаблоном;Метрика ECC вы найдете в computeECC() и findTransformECC().
Какой метод использовать?
Чаще всего, вы увидите, что используются нормированные и ненормированные SSD (TM_SQDIFF_NORMED, TM_SQDIFF) и нормализованная по нулю кросс-корреляция / ZNCC (TM_CCOEFF_NORMED). Иногда вы можете увидеть TM_CCORR_NORMED, но реже. Согласно некоторым заметкам для лекций , которые я нашел в Интернете (там есть несколько хороших примеров и интуиции по этой теме!), В книге резюме Trucco и Verri говорится, что обычно SSD работает лучше, чем корреляция, но у меня нет книги T & V, чтобыпонять, почему они предлагают это;предположительно сравнение на реальных фотографиях. Но, несмотря на это, SAD и SSD определенно полезны, особенно для цифровых изображений.
Я не знаю каких-либо убедительных примеров того, что один или другой по своей природе лучше в большинстве случаев или что-то в этом роде - я думаю, это так. действительно зависит от ваших изображений и шаблона. Как правило, я бы сказал: если вы ищете точные или очень близкие к точным совпадениям, используйте SSD. Это быстро, и это определенно соответствует тому, что вы пытаетесь минимизировать (разница между шаблоном и патчем изображения). В этом случае нет необходимости нормализовать, это просто накладные расходы. Если у вас аналогичные требования, но вам нужно сопоставить несколько шаблонов, нормализуйте SSD. Если вы ищете совпадения, но вы работаете с реальными фотографиями, которые могут иметь различия в экспозиции или контрасте, среднее смещение и выравнивание дисперсии от ZNCC, вероятно, будет лучшим.
Что касается выбора правильного порога, значение из ZNCC или SSD вообще не является числом доверия или вероятности. Если вы хотите выбрать правильный порог, вы можете измерить параметр любым количеством типичных способов. Вы можете рассчитать кривые ROC или PR для разных порогов. Вы можете использовать регрессию, чтобы найти оптимальный параметр. Вам нужно будет пометить некоторые данные, но тогда, по крайней мере, у вас будут измерения того, как вы справляетесь с некоторым набором тестов, чтобы ваш выбор не был произвольным. Как обычно, с полем, заполненным данными, вам нужно убедиться, что ваши данные максимально приближены к реальным примерам, и что ваши тестовые данные охватывают ваши крайние случаи, а также ваши типичные изображения.