18.1. СВЯЗНОСТЬ

Основной этап при формировании символического описания изображения по массиву элементов или набору простейших признаков заключается в определении геометрических соотношений и связности между элементами, относительно которых предполагается, что они принадлежат одному классу [1, 2]. Для двоичной картинки, представленной на рис. 18.1.1, а, кольцо из четырех элементов, согласно всем принятым определениям связности, делит эту картинку на три области: белые элементы с внешней стороны кольца, белые элементы внутри кольца и черные элементы самого кольца. Говорят, что элементы внутри каждой области связаны друг с другом. Смысл этого понятия легко уяснить, обратившись к рис. 18.1.1, а, но если рассматривать рис. 18.1.1, б, то возникает неоднозначность. Определяют ли все черные элементы кольцо или же они представляют собой четыре прямолинейных отрезка? Ответ на этот вопрос до некоторой степени зависит от желаемого определения связности.

Рис. 18.1.1. К определению связности: а - кольцо; б - неоднозначная фигура.

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

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

Рис. 18.1.2. Определения связных элементов изображения: а - обозначения элементов окрестности; б - изолированный элемент; в - внутренний элемент; г - граничный элемент; д - элемент дуги.

Обратимся к рис. 18.1.2. Пусть заштрихованный элемент обладает свойством , а незаштрихованный – свойством . Тогда элемент  на рис. 18.1.2, б называется изолированным, если для него не соблюдается принцип восьмисвязности относительно любого из его соседей. На рис. 18.1.2 , в элемент  является внутренним элементом, для которого выполняется принцип четырехсвязности относительно каждого из его соседей , , , . Граничный элемент, как показано на рис. 18.1.2, г, не обладает четырехсвязностью, по крайней мере, с одним из ближайших соседей. Следуя этому определению, элемент  из окрестности  не может быть классифицирован как граничная точка. Рис. 18.1.2, д иллюстрирует определение точки дуги; элемент  обладает четырехсвязностью только со своими верхним и нижним (или правым и левым) соседями. Дуговой концевой элемент обладает четырехсвязностью лишь с одним соседом. Наконец, минимально связная дуга по определению есть множество точек дуги, для которых каждая внутренняя точка дуги (не являющаяся ее концом) обладает восьмисвязностью лишь с двумя соседями.

Предыдущие определения связности основаны на цифровой модели изображения, полученной посредством взятия отсчетов на поле непрерывного изображения в точках прямоугольного растра. Голэй [3] предложил гексагональную решетчатую структуру, показанную на рис. 18.1.3. Такая структура позволяет обойти многие трудности, обусловленные применением прямоугольной решетки. Говорят, что в случае гексагональной системы соседние элементы обладают шестисвязностью, если они имеют одинаковые свойства и граничат друг с другом по общему ребру. Для многих задач выделения признаков разработаны алгоритмы построения границ областей, использующие шестисвязность [4].

Рис. 18.1.3. Гексагональная решетка элементов изображения.

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