7.3. ЭЛЕМЕНТЫ ГЕОМЕТРИИ ДИСКРЕТНОЙ ПЛОСКОСТИ

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

не имеют аналогов для дискретных изображений (множеств пикселов). Итак, необходимо уделить некоторое внимание определению соответствующих понятий для дискретных изображений.

Определение 7.1. Два пиксела называются непосредственными соседями (-соседями), если соответствующие элементы имеют общую сторону, и косвенными соседями , если соответствующие элементы касаются лишь углами. Термин сосед относится к соседству обоих типов. Термин где будет использоваться для обозначения пиксела, позиция которого определяется его положением на рис. 7.4 в соответствии с различными значениями

Рис. 7.4. Обозначение, определяющее положение отдельных пикселов относительно положения пиксела Р

Рис. 7.5. Пример топологических противоречий, возникающих при определении связности на дискретной сетке

Отметим, что н-соседи являются -соседями при четных значениях а к-соседи соответствуют нечетным значениям

Определение 7.2. К-мартрутом (или просто маршрутом) называется такая последовательность пикселов в которой при пиксел является соседом пиксела и при пиксел является соседом пиксела Если на аналогичную последовательность наложить условие, заключающееся в том, чтобы входящие в нее пикселы являлись не просто соседями, а н-соседями, то такую последовательность будем называть н-маршрутом. Простым называется маршрут, все пикселы которого являются различными и ни один из них не имеет в маршруте более н-соседей. Замкнутым называется маршрут, первый и последний пикселы которого совпадают.

Определение 7.3. Множество пикселов называется связным (или к-связным), если для каждой пары пикселов С и в 5 существует к-маршрут, начальным и конечным элементами которого служат пикселы С и соответственно, а все его остальные пикселы принадлежат множеству 5. Значения термина «н-связное» очевидно.

В литературе проблеме связности уделено определенное внимание, поскольку охарактеризовать ее можно двумя различными способами. Рассмотрим парадокс, который иллюстрируется рис. 7.5.

Естественно, было бы желательно распространить понятие связности, введенное для дискретной плоскости, на плоскость непрерывную. Если множество пикселов является связным в соответствии с введенным выше определением, то желательно, чтобы связным являлось и множество элементов воспроизведения изображения. Рассматривая пример, приведенный на рис. 7.5, естественно допустить, что на непрерывной плоскости множества темных и светлых точек не пересекаются и оба эти множества полностью покрывают изображенную часть непрерывной плоскости, поскольку отсутствуют точки какого-либо другого цвета. Если связность определяется как к-связность, то возникает следующая ситуация: маршрут, соединяющий пиксел А с пикселом В (см. рис. 7.5), может пересекать маршрут, соединяющий пиксел С с пикселом хотя каждый из этих двух маршрутов целиком входит в одно (соответствующее) из двух непересекающихся множеств. Таким образом, точка X должна одновременно принадлежать как множеству светлых, так и множеству темных точек. Если связность определяется как н-связность, то ни множество темных, ни множество светлых пикселов не являются связными. Отсюда следует, что маршрут, связывающий пиксел А с пикселом В (или пиксел С с пикселом не может целиком принадлежать лишь одному из множеств. Поскольку отрезки прямых и пересекаются в точке X, эта точка не должна принадлежать ни одному из множеств. Однако последнее противоречит допущению, согласно которому темные и светлые элементы полностью покрывают область плоскости, изображенную на рис. 7.5.

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

ввести (Систему координат х, у и задать области, представленные на рис. 7.5, аналитически. Если — длина стороны квадрата и начало координат находится в нижнем левом углу, то имеем следующее:

Точка Х имеет координаты и совершенно очевидно является темной.

Рассматривая некоторое изображение как множество пикселов, получаем непротиворечивые определения, используя понятие н-связности для светлых пикселов и к-связности — для темных. Подобный выбор многократно описан в литературе, однако он перестает быть оправданным при работе с изображениями, состоящими из пикселов нескольких цветов (более двух). Можно допускать, что включение в множество некоторых точек его границы определяется не цветом последних, а ориентацией этой границы. Перпендикуляр к границе некоторого объединения квадратных элементов может быть проведен извне по следующим направлениям: 0, 2, 4 и 6 (обозначения направлений соответствуют рис. 7.4). Можно считать что точки границы принадлежат этому множеству в том и только в том случае, если выполняется одно из двух следующих условий: а) перпендикуляр проведен по направлению 0 или 2; б) данная точка является углом, перпендикуляры к сторонам которого проведены по направлениям 0 и 2 соответственно. Эти условия проиллюстрированы на рис. 7.6. При этих условиях пикселы одного цвета (Соприкасающиеся углами, будут считаться связными в том и только в том случае, если направление биссектрис этих углов соответствует 1 (см. рис. 7.4). Согласно этому определению

Рис. 7.6. Определение вхождения граничных точек в множество элементов воспроизведения изображения в зависимости от ориентации границы Жирными линиями отмечены участки границы, которые состоят из точек, принадлежащих множеству элементов воспроизведения изображения

аналитическое описание некоторого прямоугольника будет иметь следующий вид:

Практический выбор определения может зависеть от целого ряда факторов. Например, в растровых графических устройствах прямые строятся таким образом, что составляющие их пикселы соприкасаются только углами. Следовательно, чтобы определение связности было совместимо с данным способом реализации, необходимо для изображаемых объектов предусмотреть к-связность, а для фона — н-связность. Этот принцип остается справедливым даже при использовании цветных графических устройств, поскольку объекты и фон представляют собой такие элементы воспроизводимого отображения, которые поддаются точному определению. Единственное обстоятельство, которое потенциально может составить проблему, возникает при изменении задания изображаемых объектов и фона в процессе формирования отображения, в результате чего происходит пересечение линий разных цветов. Можно пользоваться также и более сложными определениями связности, однако их обсуждение выходит за рамки, установленные нами для данной книги (см. работу [3.7, р. 62-64]).