Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 74

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 74)

Корнем этого утверждения является тот факт, что число Эйлера для объекта может быть вычислено посредством линейной суммы, каждый член которой зависит только от нескольких элементов. А именно пусть У вЂ” число элементов объекта, Р— число пар элементов, смежных по горизонтали или вертикали, и Я вЂ” число «квадратов» объекта размером 2х2 элемента.

Нетрудно показать, что тогда число Эйлера определяется формулой Е=С вЂ” Н=И вЂ” Р+Я. Эту формулу можно доказать с помощью индукции по У, т. е. по числу элементов. Она явно справедлива для объекта, содержащего один элемент. Доказательство состоит нз анализа вариантов, в котором перебираются все возможные пути увеличения имеющегося 373 9.3. Олисаяиг формы объекта на один элемент. В качестве примера такого анализа предположим, что мы увеличиваем объект, добавляя один элемент таким образом, чтобы он касался только одного из имевшихся ранее элементов объекта.

(Напомним, что подразумевается «касание» по правилу 4-связки.) Такого рода добавление элемента не может изменить ни числа связных компонент, ии числа дыр, поэтому число Эйлера для данного объекта не изменяется. Как следствие, число элементов У увеличивается на единицу, число пар Р увеличивается на единицу, а число квадратов 9 не изменяется, поэтому величина '«) — Р+Ц также остается неизменной и переход по индукции для этого случая подтверждается.

Одна из причин интереса к результату 3 заключается в том, что он показывает, как можно определить число Эйлера другим способом, связав его с такими свойствами объекта, которые вычислимы посредством линейных схем. Результат 47 Все возможные топологические свойства конечного порядка являются функциями числа Эйлера. Под «конечным порядком» мы подразумеваем, что порядок не возрастает неограниченно при неограниченном возрастании числа элементов сетчатки.

Интересно отметить, что, хотя линейная схема конечного порядка может вычислить для объекта число Эйлера, она не может определить, является ли он связным. Мы приведем последний результат относительно линейных свойств, касающийся понятия вьиуклости. Объект называется выпуклым, если любой прямолинейный сегмент, концевые точки которого принадлежат объекту, также принадлежит объекту. Из этого определения можно заключить, что объект выпуклый, если он содержит середину прямого отрезка во всех случаях, когда он содержит концы этого отрезка. Теперь мы можем догадаться, что в схеме для вычисления выпуклости необходимо рассматривать только тройки точек сетчатки, и это на самом деле верно.

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

Гм Э. Они«ения а«чьи и 4юрми 374 9.3.3. МЕТРИЧЕСКИЕ СВОЙСТВА Остаток этой главы мы посвятим свойствам объектов, которые связаны в конечном счете с понятием метрики. Смысл этого термина заключается в обобщении понятия евклидова расстояния, и поэтому метрические свойства будут в общем изменяться, если плоскость изображения подвергать каким-либо деформациям. В таком случае, следовательно, мы можем ожидать, что метрические свойства будут чаще приводить к более информативным описаниям объекта, чем топологическне, которые обсуждались ранее.

Мы начнем с повторения формального определения метрики, данного в гл. 6. Метрикой а' называется вещественная функция двух точек плоскости изображения, которая для любых точек этой плоскости х, у и г обладает следующими свойствами: 1) а(х, у))0, причем а(х, у)=0 тогда и только тогда, когда х=у (положительность); В) д(х, у)=«((у, х) (симметрия); ш) а(х, у)+«((у, г))а(х, г) (неравенство треугольника). Самой обычной метрикой является, конечно, евклидова расстояние. Пусть точками будут х=(х„х,) и у=(у„у,); нетрудно убедиться, что функция «(е(х, у) =1(х,— у,)»+(х» — у,)»)м« удовлетворяет условиям 1 — И.

Двумя другими метриками, полезными в анализе сцен, являются метрика абсолютного значения й«(х, у) = ~ х,— у, ~+ ~х,— у,~ и метрика максимального значения ам (х, у) = гпах Я х, — у, ~, ~ х,— у, Ц, Читатели, знакомые с функциональным анализом, узнают в величине «(л метрику, основанную на норме А', а в величине йм метрику, основанную на норме «.". Один из способов уяснить себе смысл этих определений заключается в том, чтобы построить для каждой метрики геометрическое место точек иа плоскости изображения, удаленных на единичное расстояние от начала координат. Эти геометрические места вычерчены на рис.

9.14. Метрику а«иногда называют «метрикой городских кварталов» (хотя геометрическое место имеет форму бриллианта) из-за того, что расстояния измеряются параллельно осям координат. Покажем в качестве упражнения, чтофуикция е(я действительно удовлетворяет условиям( — ВЕ Сразу же видно, что функция а« положительна и симметрична. Чтобы проверить неравенство треугольника, напишем (.(х,у)+~.(у, ) =~х,— у,~+~х.— .~+Ь,— х,~+~ .— х.~- У.З. Описание Формы Но !х,— у,~+~у,— г,(= 1х,— г,1 согласно неравенству треугольника для вещественных чисел, и то же самое имеет место для вторых компонент; поэтому с(,(х, у)+с(л(у, г))1х,— г, (+~х,— гз~ =с(л(х, г), и условие ш удовлетворяется.

Прежде чем покончить с формальными определениями, мы хотели бы обратить внимание на несколько привлекательных с виду функций„которые не являются метриками. Функция дв не является метрикой, поскольку, как можно устано- г=! а' =У а'=7 Рис. 9.14. Геометрические места точек, удзленных на единичное расстоиние от начала координат, построенные для различных метрик.

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

Если мы непременно хотим иметь целые расстояния, у нас может появиться соблазн округлять истинное евклидово расстояние. Для этой функции округленного евклидова расстояния неравенство треугольника, к сожалению, нарушается, что можно видеть, взяв х=(0, О), у=(1, 1) и г=(2, 2) и получив при этом й(х, у)=1, з((у, г)= — 1 и й(х, г)=3. В качестве альтернативы мы можем попытаться уменьшать евклидово расстояние до ближайшего целого вместо того, чтобы округлять его, но это также нарушит неравенство треугольника, в чем можно убедиться, взяв х=-(0, О), у=(1, !) и г=(3, 4). На практике эти трудности часто обходят, либо просто пренебрегая ими, либо используя более простую в вычислительном отношении метрику абсо- Гл.

У. Они«инин линии и формы 376 лютного значения, которая всегда дает целые расстояния, Если точки имеют целые координаты. Выполнив эти предварительные формальности, перечислим теперь некоторые наиболее очевидные метрические свойства, которые могут использоваться при опознавании формы. К простейшим метрическим свойствам объекта относятся площадь и периметр. Их легко вычислить для дискретных объектов, и они часто используются либо как составные части более сложных описаний, либо как параметры начальной сортировки, позволяющие определить, который из нескольких объектов в сцене должен обрабатываться первым, Совместно их используют, чтобы вычислить отношение толщины Т, которое для объекта с площадью А н периметром Р определяется формулой Т=4п( —,). Знаменитая теорема, известная еще в древности, гласит, что максимальное значение Т равно единице и достигается в том случае, если обьект, форма которого исследуется, представляет собой круг.

Аналогично из всех треугольников равносторонний треугольник имеет максимальное значение Т (для него Т=п)' 3/9), а из всех четырехугольников максимальное значение Т имеет квадрат (для него Т=п/4). В более общем случае отношение толщины правильного п-угольника равно и эта величина монотонно стремится к единице при возрастании числа сторон. Грубо говоря, чем толще объект, тем больше связанное с ним отношение толщины; напротив, объекты, похожие на линию, будут иметь отношение толщины, близкое к нулю. Более того, отношение толщины безразмерно и, следовательно, зависит только от формы (но не от масштаба) объекта.

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

Характеристики

Список файлов книги