Глава 8. ЗАПОЛНЕНИЕ КОНТУРА

8.1. ВВЕДЕНИЕ

Определение внутренней части области, контур которой задан, является одной из самых распространенных задач машинной графики и анализа изображений. В сущности, речь идет о преобразовании изображения класса 3 в изображение класса 2. Например, любой алгоритм заштриховки решает эту задачу. Многие алгоритмы, применяемые в распознавании образов, предусматривают вычисление интеграла по площади некоторой области, для чего они должны быть снабжены информацией о внутренней части области. При использовании фотонабора комплект шрифта часто задается контурами, которые затем заполняются для получения искомого отпечатка. Задачу заполнения можно решать множеством способов, разделив их на два обширных класса. Первый из них предполагает наличие точного описания контура как прямоугольника, и решение о том, какие части плоскости лежат внутри рассматриваемой области, принимается, по существу, на основе анализа уравнений, задающих соответствующие линии. Эти методы, изложенные в разд. 8.2, можно было бы определить как методы многоугольника, однако мы будем пользоваться термином «заполнение области, ограниченной сторонами многоугольника». Методы второго класса предусматривают отображение заполняемого контура на дискретную плоскость и определение положения внутренней части области на основе значений яркости пикселов. Методы заполнения контура, основанные на анализе значений пикселов, обсуждаются в разд. 8.3-8.5.

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

Алгоритмы заполнения области, использующие проверку на четность, основываются на том, что произвольная прямая пересекает любую замкнутую кривую (типа контура некоторой области) четное число раз (рис. 8.1). Если известно, что первая

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

Рис. 8.1. Пример использования принципа проверки на четность для определения точек, лежащих внутри замкнутой кривой

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

(создав таким образом затравочную точку) и задать цель — заполнить контур. В разд. 8.4 нами будут рассмотрены алгоритмы, реализующие критерий связности.

Используя различные комбинации критериев связности и проверки на четность, можно получать новые алгоритмы. Подобные комбинированные критерии легко реализуются с применением какой-либо общепринятой структуры данных. Оказывается, что граф смежности строк контура (К-ГСС) подходит для реализации обеих критериев. Очевидно, что эта структура данных годится для реализации алгоритма заполнения области, основанного на анализе значений яркости пикселов и использующего критерий четности, поскольку главным объектом этого алгоритма является контур. При реализации алгоритмов, в которых используется критерий связности, в качестве структуры данных обычно выбирается граф смежности строк внутренней части области (В-ГСС), однако утверждение 6.5 указывает способ, позволяющий применять при реализации этих алгоритмов и К-ГСС. Если допустить, что внутренняя часть области характеризуется н-связностью, контур— к-связностью, внутренняя часть области окрашена в цвет X и пикселы контура — в цвет У, то утверждение 6.3 можно переформулировать следующим образом.

Утверждение 8.1. Если вершина В-ГСС имеет порядки то в К-ГСС на строке, смежной снизу со строкой рассматриваемой вершины В-ГСС, найдется вершина, имеющая порядки . Аналогичным образом, при в К-ГСС на строке, смежной сверху со строкой рассматриваемой вершины В-ГСС, найдется вершина, имеющая порядки Справедливо также обратное утверждение.

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