7.5. СРАВНЕНИЕ С ЭТАЛОНОМ

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

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

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

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

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

Рис. 7.12. Простой эталон.

Рис. 7.13. Более совершенный эталон.

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

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

Пусть наше дискретное изображение, эталон и D — область определения эталона. (Например, D — квадрат размером а область определения изображения — квадрат размером . Тогда меру соответствия между частью изображения и эталоном можно определить следующим образом:

все такие, что точка внутри

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

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

и

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

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

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

где, как обычно, суммирование проводится по всем i и таким, что аргументы функции t остаются внутри области ее определения. Теперь видно, что при перемещении эталона по всему изображению путем - изменения тип результат суммирования для последнего члена остается неизменным, так как при любых значениях тип область аргументов для совпадает с областью определения функции t. Результат суммирования для первого члена — энергия изображения в пределах окна, — вообще говоря, изменяется с изменением тип, так как эти величины определяют область возможных значений для i и Положим на какое-то время, что эти изменения в энергии изображения достаточно малы и ими можно пренебречь. Тогда величина становится малой, когда сумма возрастает. В соответствии с этим определим функцию взаимной корреляции между двумя функциями g и t следующей формулой:

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

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

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

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

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

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

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

Рис. 7.14. Эталон для вертикальных краев.

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

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

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

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

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

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

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

и

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

Предположим теперь, что мы хотим установить, представляет изображение g сцену или сцену s. Мы знаем из гл. 2, что по правилу классификации, дающему минимальную вероятность ошибок, нужно вычислять апостериорные вероятности и выбирать то событие ( или ), для которого апостериорная вероятность больше. Если допустить для простоты, что априорные вероятности появления этих двух сцен равны, это правило, как мы знаем, будет эквивалентно правилу, отбирающему класс, для которого условная вероятность больше. Как и в предыдущих главах, мы можем упростить дело, выбирая класс, для которого максимален логарифм условной вероятности. Таким образом, из (6) и (7) получаем, что необходимо вычислить

и

Заметим теперь, что отрицателен, так как мы задали кроме того, последние члены в (8) и (9) одинаковы. Следовательно, правило классификации изображения g, дающее минимальную вероятность ошибок, выбирает событие юг, если

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

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

Выше обсуждалась другая типичная ситуация. Часто интересующая нас идеальная сцена является только частью изображения

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

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