9.3. ОПИСАНИЕ ФОРМЫ

Займемся теперь проблемой описания формы объекта. Как обычно, будем полагать, что объект отделен от фона; следовательно, как и в случае описания линий, задача заключается в том, чтобы охарактеризовать некоторые подмножества плоскости (квантованной, возможно, с помощью прямоугольной сетки). Прежде чем пуститься в обсуждение конкретных методов, отвлечемся на время и рассмотрим несколько более тщательно понятие «описание».

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

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

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

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

9.3.1. ТОПОЛОГИЧЕСКИЕ СВОЙСТВА

Фундаментальный способ описания подмножества плоскости заключается в том, чтобы указать некоторые топологические свойства множества. Топологическим называется свойство, инвариантное по отношению к так называемым резинообразным искажениям. Представим себе, что плоскость изображения выполнена в виде резиновой пленки; тогда топологические свойства подмножеств этой пленки не должны изменяться при любых ее растяжениях. (Однако топологические свойства будут, вообще говоря, изменяться при разрывах пленки или при наложении ее частей друг на друга.)

Рис. 9.9. Объект, состоящий из двух связных компонент.

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

Одно из часто используемых топологических свойств множества — это число его связных компонент. Связная компонента множества — это такое его подмножество максимально возможного размера, что любые две его точки могут быть соединены связной кривой, целиком принадлежащей подмножеству. На рис. 9.9 показано множество из двух связных компонент. Ясно, что только что приведенное определение связной компоненты представляет собой просто формализацию интуитивного понятия связности. Читатель может вспомнить (из нашей дискуссии по поводу 4 и 8-связок на сетке из квадратных элементов), что даже это простое топологическое свойство может быть причиной неоднозначности, если плоскость изображения квантована. Как и раньше, когда мы имели дело с дискретными изображениями, квантованными с помощью сетки из квадратных

элементов, мы будем использовать 4-связку для точек объекта и 8-связку для точек фона.

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

Рис. 9.10. Объект с двумя дырами.

Пусть С — число связных компонент объекта, число дыр; тогда число Эйлера Е определяется как Очевидно, что число Эйлера также является топологическим свойством объекта.

Предположим на некоторое время, что мы ограничили наше внимание объектами, составленными только из прямых линий. Мы будем считать, что объект состоит только из самих прямых линий, поэтому, например, штриховой объект, показанный на рис. 9.11 а, содержит две связные компоненты (четырехугольник и треугольник). Штриховые объекты такого вида иногда называют многоугольными сетями. Иногда из каких-то соображений удобно различать два вида внутренних областей в такой сети и называть одни из них поверхностями, а другие дырами. На рис. 9.116 показана многоугольная сеть из двух связных компонент с тремя поверхностями и тремя дырами. Для многоугольной сети число Эйлера может быть записано в особенно простой форме. Если мы обозначим буквой V число вершин, буквой 5 число ребер (или краев), а буквой F число поверхностей, то знаменитая формула Эйлера, связывающая эти величины, будет выглядеть так:

Для рис. 9.116, например, получим

Топологические описания объектов находят применение в анализе сцен в качестве показателей для предварительной сортировки, для контроля точности других описаний и как дополнение к другим

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

Рис. 9.11 а. Многоугольная сеть.

Рис. 9.11 б. Многоугольная сеть.