8.4.4. ОПИСАНИЕ ОСНОВНОГО АЛГОРИТМА

Содержательно этот алгоритм можно описать следующим образом. Горизонтальные строки заполняются в процессе обхода слева направо, начиная с пиксела, расположенного непосредственно справа от контура. [Для отыскания последнего в первой строке можно воспользоваться процедурой LEFT (затравочный пиксел).] Пусть — такой затравочный пиксел. Прежде чем приступать к собственно заполнению, производится обращение к процедуре с тем, чтобы проанализировать К-ГСС левого интервала контура. Если значения верхнего и нижнего порядков , то интервал представляет собой простую дугу и остается определить положение следующей просматриваемой строки. Если направление вертикального просмотра имеет значение «вниз», то задается рслед в противном случаерслед . Далее продолжается процесс заполнения по горизонтали, начиная с пиксела вплоть до обнаружения пиксела, принадлежащего контуру. Пусть Рправ — адрес последнего пиксела, находящегося внутри области. Производится обращение к процедуре Если в

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

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

Описанные механизмы представляют собой основу алгоритма

8.5. В нем помимо стека 5 используется стек в который одновременно с вводом адреса пиксела в стек 5 заносится соответствующее направление просмотра. (Допустимо, естественно, использовать и общий стек, элементами которого служат пары значений — адрес пиксела и направление просмотра.) Процедура (стек) описана в алгоритме 6.1. На шаге 3 некоторым переменным присваиваются значения в соответствии с текущим направлением просмотра. В частности, при в качестве следующего выбирается пиксел а при — пиксел Использование этих переменных избавляет от необходимости иметь отдельные коды для просмотра вверх и вниз. Основную часть алгоритма образует цикл, включающий шаги 5—17. Чтобы просмотреть верхнюю часть изображения, затравочный пиксел приходится помещать в стек дважды.

На шаге 5 определяется, является ли адрес следующего пиксела допустимым или этот пиксел уже прошел заполнение. В обоих случаях алгоритм выходит из внутреннего цикла и выполняет шаг 1. Если стек — непустой, выталкивается новый пиксел, после чего весь процесс повторяется. Если адрес следующего пиксела является допустимым и этот пиксел еще не проходил заполнения, то этот пиксел выбирается в качестве текущего (шаг 6). На шаге 7 определяются порядки К-ГСС для левой части контура.

На шаге 8 выполняется первая нетривиальная операция: проверяется достижение границы внутренней части области в текущем направлении просмотра. Если просмотр осуществляется вниз и значение верхнего порядка превышает единицу, то значит процесс заполнения дошел до «дна» контура (как показано на рис. 8.9, а) или возникла одна из представленных на рис. 8.9, б конфигураций. Наличие первой ситуации определяется посредством проверки того, находится ли текущий пиксел справа от пиксела рправу т. е. вне контура. В таком случае заполнение в этом направлении прекращается и алгоритм выходит из данного цикла. В противном случае текущий пиксел действительно находится внутри области. (При просмотре вверх используется аналогичный тест Для определения достижения «верхушки» контура.)

На шаге 9 проверяется, не равны ли нулю верхний и нижний порядки, и выбирается начальный пиксел в следующей строке. Не обязательно, чтобы оба значения порядков равнялись единице,

даже несмотря на то, что вершины со значениями порядков (1,2) и (2,1) для полных областей недопустимы. Для большинства пикселов контура условия этого шага выполняются и алгоритм переходит непосредственно к шагу 14. Если значение хотя бы одного из порядков равно нулю, то значит соответствующий пиксел следует поместить в стек (см. утверждение 8.1) и при выборе пиксела необходимо проявить определенную осмотрительность.

Рис. 8.9. Иллюстрация к работе алгоритма 8.5: а, б — конфигурации, для которых условие шага 8, заключенное в квадратные скобки выполняется при просмотре вниз. Достижение «дна» контура и прекращение просмотра в данном направлении зафиксировано лишь для конфигурации а; в — при обнаружении представленной конфигурации в процессе осмотра левой части контура пиксел вводится в стек; — два ГСС для конфигурации в

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

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

проверка для случая просмотра вверх, осуществляется на шаге

11. На рис. 8.10,а изображена конфигурация контура, для которой выполняются условия шага 11 для случая просмотра вниз.

Шаг 12 рассчитан на случай, когда в следующей строке (по направлению просмотра), примыкающей к контуру, отсутствуют пикселы контура. Такая конфигурация изображена на рис. 8.10, б для случая просмотра вниз.

Рис. 8.10. Иллюстрация к работе алгоритма 8.5: а — конфигурация, для которой выполняются условия шага 11, б — шага 12, в — если при исследовании правой части контура возникает представленная конфигурация, пиксел заносится в стек; — два ГСС для конфигурации в

Рассматривается пиксел, расположенный непосредственно над или непосредственно под текущим пикселом. Если рассматриваемый пиксел не прошел заполнения, то он выбирается в качестве следующего пиксела на линии просмотра, расположенной непосредственно справа от контура (см. комментарии к шагу 10, касающиеся существования подобной дуги контура).

На шаге 14 осуществляется реальное заполнение. Именно на этом шаге осматривается большинство пикселов. При его выполнении для каждого пиксела проверяется, не окрашен ли он в цвет контура и не заполняет ли он пиксел с правильным цветом.

Алгоритм 8.5. Заполнение контура по критерию связности

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

затравочный пикселнад. Адрес (затравочный пиксел) заносится в стек а значение направления просмотра вниз — в стек Если задан второй пиксел, его адрес (затравочный пикселнад) также заносится в стек а направление просмотра вверх — в стек

(см. скан)

(см. скан)

На шаге 15 определяются порядки вершины К-ГСС, соответствующей правой дуге контура. Если значение одного из ее порядков равно 0, то адрес пиксела, расположенного по другую сторону контура (пиксел на рис. 8.10, в), заносится в стек; в стек заносится также соответствующее значение направления. (Шаги 15-17.) Два ГСС, представляющие эту конфигурацию, приведены на рис. 8.10, г.

Очевидно, что одновременно в стеке находится максимум две вершины. С другой стороны, все вершины, связанные с заданной вершиной, либо попадут в стек, либо будут заполнены. Рассмотрим пример, приведенный на рис. 8.11. Пусть С — первая вершина, пройденная при обходе. В этом случае вершины В и заносятся в стек. При каждом повторном проходе через вершину (либо в результате ее выталкивания из стека, либо при заходе в нее из другой вершины) вершина Е будет помещаться в стек.

Можно показать также, что в случае полной области алгоритм 8.5 обеспечивает корректное заполнение. В самом деле, при этом в стек заносятся лишь те пикселы, которые являются смежными точками максимумов или минимумов по вертикали.

Рис. 8.11 Пример использования стека в алгоритме 8.5