6.8. КОДИРОВАНИЕ ОБЛАСТЕЙ И ГРАФ СМЕЖНОСТИ ОБЛАСТЕЙ
Данный способ особенно хорошо подходит для представления изображения класса 2 и приближения изображений класса 1. Связную область определенного цвета можно полностью описать с помощью ее контура, причем такое описание обычно требует много меньших затрат памяти, чем описание через пикселы. Обработка представленных таким образом изображений упрощается при наличии графа смежности областей (ГСО). Вершины этого графа соответствуют отдельным областям и ребро соединяет пару вершин, если соответствующие области являются смежными. Следует подчеркнуть, что понятие смежности для дискретных изображений необходимо тщательно определить, чем мы займемся детально в гл. 7. Здесь мы ограничимся замечанием, что какое бы определение смежности областей ни предполагалось использовать, оно не должно допускать соединений, превращающих соответствующий ГСО в неплоский граф. Так, в частности, если четыре области имеют одну точку соприкосновения — угол, то недопустимо введение обоих диагональных соединений, как показано на рис. 6.12. Данное изображение включает пять областей, причем каждая из пар областей 
имеет общую границу, и следовательно, соответствующие вершины ГСО должны быть соединены. Кроме того, каждая из вершин А, В, С и D соединена с вершиной Е Если ввести соединения в парах вершин 
, то ГСО становится неплоским. Небольшое изменение положения точки, в которой соприкасаются четыре области, приведет к тому, что сохранится смежность только одной из двух последних пар областей и соответствующий ГСО будет плоским.
Рис. 6.12 Ограничения, налагаемые на определение смежности областей изображения
Рис. 6.13 Граф смежности областей
На рис. 6.13 приведен пример графа смежности областей, наложенного на изображение. Исследуя свойства ГСО, можно получить существенную информацию об изображении.
Приведем некоторые свойства ГСО и соответствующие им признаки изображений.
а. Порядок вершины определяется числом областей, смежных рассматриваемой области. Это число обычно пропорционально раз меру рассматриваемой области, и, следовательно, вершины, имеющие высокий порядок, соответствуют большим областям.
б. Если внутри некоторой области расположены какие-то другие области (например, А на рис. 6.13), то соответствующая ей вершина ГСО является разделяющей. Если ни одна из областей изображения не содержит отверстий (все области — односвязные), то ни одна из них не содержится в какой-то другой области и в ГСО нет разделяющих вершин. Поскольку существуют эффективные алгоритмы отыскания разделяющих вершин графа (см. разд. 6.11), то всю топологическую информацию об изображении можно извлечь из ГСО.
Вершины ГСО могут быть помечены информацией, характеризующей области, и поэтому, помимо топологических, могут быть изучены и другие свойства. Граф смежности областей можно использовать также для реализации изощренных способов страничного представления изображения. Отдельные страницы составляют части изображения, соответствующие небольшим кластерам вершин (или даже отдельным вершинам), что обеспечивает более естественное, чем при использовании произвольной сетки, разбиение.
И наконец, ГСО является основной структурой данных, используемой при сегментации изображения с помощью выделения областей путем наращивания, в том числе на основе алгоритмов расщепления — слияния. Один из недостатков алгоритма 6.6 состоит в том, что в конечном счете области, обладающие аналогичными признаками, могут не подвергнуться слиянию, если они не имеют в тетрарном дереве общего предка. Использование ГСО на этом последнем этапе позволяет объединять подобные области.
