8.3.1. ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ АЛГОРИТМА 8.3

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

Таблица 82

Интервалы изображения, представленного на рис. 8.4, при обработке которых необходима коррекция

Рис. 8.4. Пример построения границы области при наличии пиксела, имеющего три соседних пиксела; пикселы внутри области заштрихованы

Первоначально может сложиться впечатление, что пикселы В и не являются кратными в смысле определений, введенных в гл. 7. Можно, однако, одну дугу контура провести через пикселы К и А, а другую — через пикселы X, В, Аналогичный пример неоднозначности приведен на рис. 7.15, б; он использовался для обоснования требования о том, что внутренние части полных областей должны быть н-связными. Следует

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

Эти примеры представляют собой скорее иллюстрацию крайнего случая и при решении многих прикладных задач сетка выборки является достаточно точной для того, чтобы исключить появление кратных пикселов. Теперь покажем, что при выполнении этих условий алгоритм 8.3 обладает корректностью.

Теорема 8.1. Если область является полной, то для ее контура допустимы лишь следующие пары значений порядков: (0,2), (2,0) и (1,1).

Доказательство. Докажем эту теорему, продемонстрировав невозможность появления иных пар значений. Рассмотрим пару значений (0,1). Если данный интервал и интервал, расположенный под ним, содержат по одному пикселу, то имеем дело с пикселом, ко-соседи которого совпадают (рис. 8.5, а). Если интервал, расположенный ниже рассматриваемого, содержит два пиксела, то они являются н-соседями друг относительно друга (рис. 8.5, б).

Рис. 8.5. Примеры, использованные при доказательстве теоремы 8.1: а — значения порядков (0, 1) — один пиксел на строке, расположенной ниже рассматриваемой, б — значения порядков — два пиксела на строке, расположенной ниже рассматриваемой, в — значения порядков (0,1) — три пиксела на строке, расположенной ниже рассматриваемой; г — значения порядков (0,3), д — значения порядков (0,4)

Если в нем содержится более двух пикселов, то некоторые из них являются н-соседями пикселов контура, содержащихся в строке, расположенной над ними (рис. 8.5, в). Возникновение двух последних случаев не связано с числом пикселов, содержащихся в рассматриваемом интервале. Все три перечисленные конфигурации не соответствуют условиям определения 7.6 и, следовательно, не могут встречаться при полной области. Случай пары значений порядков (1,0) можно проанализировать аналогичным образом. Теперь необходимо показать, что при полной области ни одно

значение порядка не может превышать 2. Если значение порядка — нечетное, то это означает, что одна из ветвей обходится многократно (рис. 8.5, г), Если значение порядка — четное, то у некоторых пикселов на маршруте должно иметься более двух н-соседей (рис. 8.5, д).

Следствие. Если для обработки контура полной области используется алгоритм 8.3, то признак ошибки не появляется ни при каких обстоятельствах (шаг 11).

Итак, для заполнения контуров полных областей можно использовать сравнительно простой алгоритм, который одновременно работает с малым числом строк. Если область — неполная, то такой алгоритм может ошибаться, что было показано на рис. 8.4 и в табл. 8.2. К сожалению, при работе с неполными областями этот алгоритм не только допускает ошибки, но и не выводит признак ошибки. На рис. 8.6 представлен соответствующий пример (признак ошибки не появляется до тех пор, пока не будет проведено какое-либо неверное заполнение: пиксел, лежащий между интервалами и с).

Рис. 8.6 Пример контура, правильное заполнение которого с помощью алгоритма невозможно

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