7.5.1. СРАВНЕНИЕ С ЭТАЛОНОМ — МЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

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

Предположим, что у нас есть градиентное изображение, такое, как на рис. 7.3, на котором представлены простые геометрические тела в виде контуров, и мы хотели бы выяснить, имеется ли на этом изображении треугольник. (Треугольник указывает на присутствие клина.) Очень простой подход к решению этой задачи может заключаться в следующем: нужно построить эталон или трафарет, такой, например, как на рис. 7.12, и просматривать через него последовательно все изображение. Если мы найдем такую позицию, при которой «отверстие» в эталоне заполнено белым, можно будет сделать вывод, что в этом месте обнаружен треугольник. Сразу же возникает возражение против такой процедуры: любая достаточно большая сплошная область белого цвета может быть ошибочно принята за треугольник.

Эту трудность можно преодолеть, если искать не просто белую

область, заполняющую эталон, а белую треугольную область, окруженную черными областями. На рис. 7.13 показано схематически, как эту операцию можно выполнить с помощью некоторого эталона. При работе с новым эталоном мы будем считать, что треугольник обнаружен только в том случае, если каждая область эталона закрывает зону изображения, уровень полутонов которой соответствует эталонной разметке. Другими словами, области эталона, помеченные нулем, должны «регистрировать» только нулевые значения полутонов, а области, помеченные единицей,— только единичные значения. Заметим, что эталон на рис. 7.13 сам является бинарным изображением. (Для простоты мы не показали его разбиения на квад

 

ратные элементы.) Размер эталона, однако, обычно меньше, чем размер исходного изображения, так как наша цель заключается в том, чтобы обнаружить присутствие некоторого «малого изображения» в пределах большого. Говоря языком математики, область определения эталона меньше, чем область определения исходного изображения.

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

Пусть S'(t, /) — наше дискретное изображение, t{i, j) — эталон и D — область определения эталона. (Например, D — квадрат размером 20x20, а область определения изображения — квадрат размером 500x500.) Тогда меру соответствия между частью изображения и эталоном можно определить следующим образом;

Заметим, что это определение сводится к сдвигу эталона t(i, /) в положение (т, п) на изображении и к присвоению величине М {т, п) значения, равного числу элементов, в которых уровни полутонов изображения и размещенного на нем эталона различны. В связи с тем что мы, по-видимому, хотим найти соответствие эталону где-то в пределах всего изображения, нам придется вычислять М (т, п) для всех положений эталона [т, п) и фиксировать те позиции, для которых величина М (т, п) мала.

Выделим теперь из предшествующего обсуждения основные элементы процедуры сравнения с эталоном. Используя понятие функции интенсивности, эту процедуру можно сформулировать следующим образом; мы ищем такую область плоскости изображения, в которой функция интенсивности сходна с некоторой заранее заданной функцией интенсивности, называемой эталоном. Следовательно, нам в общем случае необходимо средство для определения сходства или расстояния между двумя функциями интенсивности, и здесь оказывается полезным понятие о метрике. В данный момент нет необходимости приводить формальное определение класса функций, задающих метрику; заметим лишь, что здесь подразумевается обычное обобщение понятия евклидова расстояния. Наша функция М (т, п) в формуле (1) удовлетворяет этому определению и иногда называется метрикой L Ч Приведем здесь еще две метрики;

и

где в каждом случае область изменения і и / та же, что и в формуле (I). Формула (2) задает обычное евклидово расстояние между двумя векторами. Определение (3) иногда называется метрикой L*. Заметим, что эти определения относятся не только к бинарным изображениям, хотя, как мы видели выше, определение метрики может иметь особенно простую интерпретацию, если ограничиться бинарными изображениями.

Исследуем определение (2) более подробно. Часто бывает удобно убрать квадратный корень, приняв, что мера расстояния должна

быть £2(m, rt). Если мы сделаем это и возведем разность в квадрат, то получим

где, как обычно, суммирование проводится по всем і и /, таким, что аргументы функции t остаются внутри области ее определения. Теперь видно, что при перемещении эталона по всему изображению путем -изменения тип результат суммирования для последнего члена остается неизменным, так как при любых значениях тип область аргументов для совпадает с областью определения функции t. Результат суммирования для первого члена — энергия изображения в пределах окна,— вообще говоря, изменяется с изменением тип, так как эти величины определяют область возможных значений для і и j. Положим на какое-то время, что эти изменения в энергии изображения достаточно малы и ими можно пренефечь. Тогда величина Е^{т, п) становится малой, когда сумма y,Xg(t.

/) — т, / — п) возрастает. В соответствии с этим определим функцию взаимной корреляции Rgt ірг, п) между двумя функциями g и t следующей формулой:

где, как всегда, мы суммируем по всем і и / внутри области, занимаемой передвинутым эталоном. Можно использовать это определение как меру сходства между эталоном и областью изображения вблизи точки (т, п); эталон и изображение считаются похожими, если взаимная корреляция велика. Конечно, если мы поместим эталон в белую область изображения, взаимная корреляция будет иметь значительную величину. Другими словами, наше первоначальное предположение о независимости суммы g^ (t, j) от точки (m, п)

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

где мы накладываем обычные ограничения на область значений і и /. Согласно неравенству Коши — Шварца,

причем равенство имеет место в том и только том случае, когда функция интенсивности в интересующей нас области пропорциональна

эталонной функции. Следовательно, нормированная функция взаимной корреляции принимает максимальное значение, когда соответствие эталона и функции интенсивности абсолютное (с точностью до масштабного коэффициента). С другой стороны, при некоторых условиях наше предположение относительно суммы 22g2 выполняется в точности. Например, предположим, что у нас имеется бинарное изображение, и пусть белое соответствует 1, черное соответствует—1, но не нулю, как обычно. Тогда сумма квадратов значений функции интенсивности по любой области фиксированного размера постоянна, и взаимная корреляция имеет максимальное значение именно тогда, когда функция Е- минимальна. Использование взаимной корреляции в качестве критерия сходства имеет также свои корни в некоторых похожих, но не идентичных задачах классификации образов и обнаружения сигналов. Взаимную корреляцию до сих пор еще часто применяют, возможно, потому, что известно много случаев ее эффективной реализации. Как мы убедились, однако, использование взаимной корреляции для сравнения с эталоном влечет за собой неявное предположение о том, что энергия функции интенсивности внутри любого окна приблизительно одна и та же.

Рассмотрим снова наш исходный пример — задачу обнаружения местонахождения треугольника на рис. 7.3. Предположив, что мы уже приняли одно из определений расстояния в качестве меры сходства, мы все-таки должны еще спроектировать сам эталон. После некоторого размышления придем к заключению, что эта проблема в том виде, в каком она поставлена, может быть решена только с помощью целого набора эталонов. Клин, например, если нет каких-либо явных ограничений, может находиться в любом месте сцены и может быть виден под любым углом. Следовательно, видимый размер его треугольной грани будет колебаться в широких пределах и кажущаяся величина его внутренних углов также может быть самой разной. Для каждого такого положения клина нам, очевидно, необходим отдельный эталон, и в связи с тем, что каждый эталон нужно перемещать по всей сцене, объем вычислений будет, по-видимому, большим. В такой ситуации естественным подходом к решению этой задачи является замена глобального эталона набором локальных эталонов. Локальные эталоны проектируются таким образом, что они соответствуют различным частям интересующего нас объекта. Основной довод в пользу этого разделения заключается в том, что отдельные части меняются по своему виду меньше, чем целый объект.

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

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

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

Мы могли бы использовать «бинарный» эталон (подобный эталону на рис. 7.13, но в форме одной вертикальной линии) и применять его к градиентному изображению. С другой стороны, можно было бы легко придумать эталон, соответствующий по форме вертикальной линии на исходном изображении. (На самом деле, если бы мы оперировали с исходным изображением, мы, возмсйкно, захотели бы использовать два эталона: один для переходов «темное — светлое» и другой для переходов «светлое — темное». Если мы работаем с градиентным изображением, этот связанный с симметрией вопрос не возникает, потому что мы обычно берем модуль градиента.) На рис. 7.14 показан эталон, который будет обнаруживать переходы слевй направо от темного к светлому вдоль вертикальной линии, если для определения сходства использовать формулу (1). Область эталона, отмеченная словом «низкая», имела бы при этом значения интенсивности, соответствующие темному концу полутоновой шкалы, а область с пометкой «высокая» — светлому. Трудность, которая может возникнуть при использовании этого эталона, заключается в том, что он не инвариантен к абсолютным значениям уровня полутонов; добавление константы к значениям полутонов изменит степень соответствия. Это соображение может привести нас к процедуре, в которой областям эталона, отмеченным словами «низкая» и «высокая», приписаны значения —1 и +1 соответственно, а в качестве меры сходства используется корреляция, вычисляемая по формуле (4). Такая процедура эквивалентна вычитанию элементов из смежных столбцов и сумми-

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

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