Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 73
Текст из файла (страница 73)
д. Очевидно, что топологические описания множеств будут в самом деле весьма общими, а потому и не очень информативными в обсуждавшемся выше смысле. Одно из часто используемых топологических свойств множества— зто число его соленых компонент. Связная компонента множества — это такое его подмножество максимально возможного размера, что любые две его точки могут быть соединены связной кривой, целиком принадлежащей подмножеству.
На рис. 9.9 показано множество из двух связных компонент. Ясно, что только что приведенное определение связной компоненты представляет собой просто формализацию интуитивного понятия связности. Читатель может вспомнить (из нашей дискуссии по поводу 4 и 8-связок на сетке из квадратных элементов), что даже это простое топологическое свойство может быть причиной неоднозначности, если плоскость изображения квантована. Как и раньше, когда мы имели дело с дискретными изображениями, квантованными с помощью сетки из квадрат- Гл.
9. Онисанин линии и йУорим ных элементов, мы будем использовать 4-связку для точек объекта и 8-связку для точек фона. Другое представляющее интерес топологическое свойство— это число дыр в объекте. Строго говоря, число дыр в обьекте на единицу меньше, чем число связных компонент в дополнении объекта ').
На рис. 9.!О показан объект с двумя дырами. Пусть С вЂ” число Рис. 9.10. Объект с двумя дырами. связных компонент объекта, а Н вЂ” число дыр; тогда число ЭШера Е определяется как Е=С вЂ” Н. Очевидно, что число Эйлера также является топологическим свойством объекта. Предположим на некоторое время, что мы ограничили наше внимание объектами, составленными только из прямых линий.
Мы будем считать, что объект состоит только из самих прямых линий, поэтому, например, штриховой объект, показанный на рис. 9.11а, содержит две связные компоненты !четырехугольник и треугольник). Штриховые объекты такого вида иногда называют многоугольными сгпими.
Иногда из каких-то соображений удобно различать два вида внутренних областей в такой сети и называть одни из ник поверхностями, а другие дырами. На рис. 9.1!б показана многоугольная сеть из двух связных компонент с тремя поверхностями и тремя дырами. Для многоугольной сети число Эйлера может быть записано в особенно простой форме. Если мы обозначим буквой 1т число вершин, буквой 5 число ребер (или краев), а буквой Е число поверхностей, то знаменитая формула Эйлера, связывающая эти величины, будет выглядеть так: 'и' — Я+Р=С вЂ” Н=Е.
Для рис. 9,116, например, получим 15 — 19+3=2 — 3= — 1. Топологические описания объектов находят применение в анализе сцен в качестве показателей для предварительной сортировки, для контроля точности других описаний и как дополнение к другим ') Имеется в виду фои, рассматриваемый как обьект.— Прим. нерее, У.З.
Оласангге формы описаниям. Например, некоторые методы опознавания знаков используют число дыр в качестве одного из признаков в описании формы знака. В общем задачи, в которых достаточно одного топологического описания, встреча!отея редко. Рнс. 9.1!а. Многоугольная сеть. Рнс. 9.1!б. Многоугольная сеть. 9.3,2. линейнь!е сВОЙстВА Для простоты на некоторое время ограничим наше внимание объектами, заданными на сетке квадратных элементов. Нас будут интересовать описания свойств таких объектов в зависимости от того, могут ли они вычисляться с помощью «простой» схемы. В частности, мы будем обсуждать свойства квантованных объектов, которые могут опознаваться с помощью линейной схемы, рассмотренной в ч.
!. Предположим тогда, что имеет место ситуация, показанная иа рис. 9.12. г1ы начнем с бинарного дискретного изображения, на котором элементы, равные «!>, представляют точки объекта. 1г1ы полагаем, что у нас есть семейство функций.преди тон 1ь которые воспринимают значения некоторых элементов изображения в качестве входных величин и дают на выходе либо нуль (ложь), либо зуо Гл. Э.
Описания лилии и формы единицу (истина). Функции ~, можно считать признаками объекта— объект либо обладает (-м признаком, либо нет. Признаки поступают на вход линейной схемы, которая формирует линейныекомбинации и Т= л гол и сравнивает их с порогом г. В конечном итоге мы гово- г=ь рим, что объект обладает свойством Р, если линейная комбинация превосходит порог г, и не обладает свойством Р в противном случае. Вопрос заключается в следующем: какой класс свойств объекта может вычислять такое устройство? рис. 9Л2. Схема длв вычисления линейных свойств. Сразу же ясно, что на этот вопрос не может быть дано представляющего интерес ответа до тех пор, пока мы не наложили ограничения на функции-предикаты ~ь Если мы примем, что единственный предикат может вычислять любое желаемое свойство объекта (т. е.
указывать, обладает объект этим свойством или нет), то используем этот единственный предикат и отбросим остальную часть схемы. В соответствии с этим мы наложим ограничения на способ, посредством которого фуикция-предикат получает информацию о точках изображения на сетчатке. Двумя видами ограничений, представляющих интерес, являются ограничение но диамептру и ограничение ло порядку. Мы будем говорить, что предикат ограничен по диаметру величиной й, если множество элементов изображения, от которых он зависит, целиком лежит внутри круга диаметра й.
Аналогично предикат ограничен по порядку величиной п, если он зависит не более чем от и элементов изображения "). Подобно этому, ограниченная по диаметру (или порядку) линейная схема — это такая схема, в которой все предикаты ограничены по диаметру (или порядку). Заметим, что мы не ограничиваем ни число предикатов, ни их логические формы — ограничиваем лишь выбор входных элементов для одного произвольного предиката. Будем называть линейным свойством объекта свойство, которое можно вычислить с помощью линейной схемы (с объявленными заранее ограничениями относительно предикатов). з» Мы, конечно, подразумеваем, что эти ограничения не бессмысленны, т.
е. считается, что диаметр сетчатки больше о н она содержит больше чем л элементов. 371 9.8. Олиеаиие формы Пользуясь этими определениями, мы можем изложить несколько замечательных результатов, относящихся к линейным свойствам обьектов. В некоторых случаях мы .будем доказывать результат, в других будем просто формулировать его. Читателя, заинтересовавшегося дальнейшим изложением этих вопросов, мы отсылаем к превосходной книге основоположников этой теории Минского и Пейперта (1969). Начнем с некоторого свойства ограниченных по диаметру линейных схем, которое легко доказывается. Результат 17 Ни одна ограниченная по диаметру линейная схема не способна определить, связный или нет некоторый произвольный объект.
Этот результат можно проверить с помощью примера. Задавшись максимальным диаметром е1, мы можем нарисовать объекты, опровергающие гипотезу о существовании ограниченной по диаметру линейной схемы, способной отличать связные объекты от несвязных. Груааа! куала Я Рис. 9.13. Примеры к результату относительно сиизиости. Нужные нам объекты изображены на рис. 9.13, а — 9.13, г, где для наглядности сетка квантования не показана. Примем, что во всех случаях ограничение по диаметру д меньше, чем ширина объекта, и поэтому ни один из предикатов ие может «видетьз оба конца. Для удобства мы сгруппировали преднкаты, как показано на рис.
9. 13, а. Предикаты группы 1 связаны с левым концом объекта, группы 2— с правым, а предикаты группы 3 связаны с остальной частью сетчатки. Без какой-либо потери общности предположим, что линейная сумма Т превосходит порог 1 для связных объектов. Поскольку 372 Гл. У. Описания линии и форма объект рис. 9.13, а несвязный, мы получим сумму, например Т„ меньшую порога Е Поскольку объект рис. 9.13, б связный, найдем, что Та= 1и, кроме того, что этот прирост Та — Т, должен полностью определяться вкладом предикатов группы 2. Точно так же для объекта рис.
9.!3, в мы получим, что Т; г и что прирост Т,— Т, должен определяться только предикатами группы 1. Наконец, для объекта рис. 9.13, г должен возрасти вклад в сумму от обеих групп предикатов, поскольку каждая группа «видит» те же изменения, что она видела и раньше. Таким образом, сумма, Т, для последнего изображения будет даже больше, чем каждая из сумм Та и Т„ поэтому' порог будет превышен и линейная схема ошибочно определит, что объект рис. 9.13, г связный. Подобного рода утверждение для ограниченных по порядку линейных схем выступает как Результат й Порядок линейной схемы, способной вычислять связность, неограниченно растет по мере того, как число элементов сетчатки стремится к бесконечности.
В частности, можно показать, что минимальный порядок линейной схемы, способной вычислять связность, пропорционален корню квадратному из числа элементов сетчатки. Оба первых результата вместе показывают, что связность — элементарное топологическое свойство — и в самом деле оказывается чересчур сложным для линейных схем. Наш третий результат касается способности ограниченных по диаметру и порядку линейных схем вычислять предикаты, определяющие число Эйлера. Результат Зг Свойство «число Эйлера для объекта больше чем й» может быть вычислено посредством линейной схемы порядка 4 и диаметра 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
