7.7. КРАТНЫЕ ПИКСЕЛЫ

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

В таком случае необходимо иметь определение, применимое к подмножествам области, а также (путем его расширения) к отдельным пикселам.

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

Определение 7.8. Ко-соседями пиксела, принадлежащего контуру С, называются пикселы, являющиеся для этого пиксела предыдущим и следующим элементами при обходе, осуществляемом в соответствии с алгоритмом 7.1.

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

Рис. 7.18. К определению ко-соседей для некоторого пиксела контура; пикселы В и являются ко-соседями пиксела А, а пиксел Е таковым не является; пикселы Е и А являются ко-соседями пиксела В

Рис. 7.19. Содержательная иллюстрация понятия «кратный пиксел»: А соответствует развороту границы [условие (б)]; В — двум непересекающимся дугам, отображенным на один и тот же пиксел [условие (а)], а С и являются соседними пикселами, на которые отображены непересекающиеся дуги границы [условие (в)]

Определение 7.9 Пиксел называется кратным при выполнении одного или нескольких из следующих условий:

(а) данный пиксел просматривается более одного раза в про цессе построения контура;

(б) данный пиксел не имеет соседей во внутренней части со ответствующей области;

(в) данный пиксел имеет, по меньшей мере, одного н-соседа, который принадлежит контуру, но не является его ко-соседом.

Смысл этого определения иллюстрируется на рис. 7.19. Кратными оказываются те пикселы, на которые попадают две дуги контура, а также пикселы, на которых происходит «разворот» контура. Первые два условия легко проверяются с помощью разметки, предусмотренной в процедуре TRACER (см. алгоритм 7.1). В самом деле, по окончании построения контура «обычные» пикселы

контура будут снабжены меткой, значение которой будет равно 2, а кратные пикселы, удовлетворяющие условию (а), будут иметь метки, значения которых будут больше 2. Условия (б) (отсутствие соседей со значением метки 1) и (в) (наличие н-соседа со значением метки, равным или больше 2, при условии, что он не является ко-соседом) могут быть проверены с помощью второго обхода. Несмотря на существенную простоту обнаружения кратных пикселов при помощи обходов контура, этот метод может оказаться неприемлемым при решении тех прикладных задач, в которых целесообразно использовать параллельную обработку. Поскольку проверка условия (в) существенным образом зависит от этой последовательной процедуры обхода, то определение 7.9 начинает создавать проблемы. Интуитивно кажется, что последовательность не должна быть столь уж важной, так как нас интересуют пикселы, на которые приходится две или несколько дуг контура, или те пикселы, на которых дуги изгибаются, т. е. конфигурации, не зависящие от порядка обхода.

Продолжим изучение пикселов, не зависящих от порядка обхода. Если в процессе построения контура некоторого множества некоторый пиксел просматривается более одного раза, то это может происходить только из-за отсутствия способа прохождения из одной части множества в другую его часть минуя данный пиксел. Следовательно, при удалении данного пиксела число связности множества уменьшится, по крайней мере, на единицу. И наоборот, любой пиксел, удаление которого из множества уменьшает его число связности, должен в процессе построения контура этого множества просматриваться более одного раза. Установить, существен ли некоторый пиксел с точки зрения связности соответствующей области, можно, изучив восемь его соседей. Нетрудно показать, что пиксел Р является существенным для связности соответствующей области в том и только том случае, если конфигурация его окрестности соответствует образцам, приведенным на рис. 7.20 (в том числе и полученным в результате их поворота на 90° в любом направлении). Таким образом, некоторый пиксел можно считать кратным в том и только том случае, если его окрестность имеет конфигурацию, соответствующую одному из представленных образов. На этом (и последующих) рисунке значения пикселов записываются следующим образом.

Определение 7.10. В качестве меток, присваиваемых некоторому пикселу в процессе обхода контура, используются

Рис. 7.20. Конфигурация окрестности пиксела, являющегося существенным для связности соответствующей области

следующие числа: 1— для пикселов, находящихся внутри области; 2 — для пикселов контура, осматриваемых однократно; 3 или большее число — для пикселов контура, осматриваемых более одного раза. С помощью числа, за которым следует знак обозначается пиксел, метка которого, по крайней мере, не меньше этого числа. Для обозначения пикселов, не принадлежащих соответствующему множеству, используется 0. Буквы, за исключением X, обозначают, что данный пиксел может иметь любую ненулевую метку. Метка X заменяет любое число (условие не имеет значения). Группа пикселов, помеченных одним и тем же символом (например, А), характеризуется тем свойством, что по меньшей мере один из этих пикселов имеет метку, значение которой больше нуля. Звездочка используется для обозначения пиксела, метка которого может иметь любое отличное от 1 значение.

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

Итак, нами доказано следующее.

Утверждение 7.2. Условие (а) определения 7.9 можно заменить требованием, чтобы восьмиэлементная окрестность пиксела соответствовала хотя бы одной из эталонных конфигураций, приведенных на рис. 7.20 (или полученных в результате их поворота на 90° в любом направлении).

Условие (б) легко поддается проверке с помощью какого-либо параллельного алгоритма. Ни один из восьми пикселов-соседей не может иметь метку, равную 1. Это обеспечивает сохранение одиночных (т. е. пикселов, не имеющих ни одного соседа) и концевых (пикселов, имеющих ровно одного соседа) точек. Таким образом, проверка соответствуя второму эталону на рис. 7.20 может быть упрощена, если допустить, чтобы все обозначенные символом А пикселы имели нулевые метки. Заметим, что условие (б) обеспечивает также сохранение всех линий, имеющих ширину, равную двум (типа линии, изображенной на рис. 7.17).

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

порождающие условие (в). Общий случай такой конфигурации представлен на рис. 7.21.

Без потери общности можно считать, что - осматриваемый в данный момент (текущий) пиксел, снабженный меткой — его н-сосед с меткой 0. (Напомним, что все пикселы, входящие в контур, имеют такого соседа.) Другие конфигурации можно получать с помощью поворота исходной конфигурации на 90°. Поскольку пиксел удовлетворяет условию (в) определения 7.9, он также должен иметь н-соседа с меткой, не меньшей 2.

Утверждение 7.3. Любой пиксел, удовлетворяющий условию (в) определения 7.9 и не удовлетворяющий условию (а) или (б), входит в конфигурацию, обозначаемую кодом и ориентированную по вертикали или горизонтали.

Рис. 7.21. Разметка пикселов, использованная при введении альтернативной формы определения 7.9

Доказательство. Докажем это свойство для пиксела Начнем с рассмотрения пиксела и покажем, что, если его метка не равна (т. е. данное утверждение не выполняется для горизонтальной конфигурации), то пиксел входит в некоторую вертикальную конфигурацию, обладающую указанным свойством. Если метка пиксела имеет нулевое значение, то пиксел либо многократно осматривается, либо является концевой точкой и, следовательно, в соответствии с условием (а) или (б) относится к категории кратных пикселов. Пусть его метка равна 1. Это означает, что пикселы не могут иметь нулевые метки, поскольку в противном случае пиксел должен входить в контур. Так как мы приняли, что условие (в) выполняется, значение метки пиксела или 62 должно быть не менее 2. Учитывая симметричность, необходимо рассмотреть лишь один из этих пикселов. Пусть пиксел имеет значение Если метка пиксела равна 0, то пиксел будет ко-соседом пиксела из чего следует, что метка пиксела должна также иметь значение не меньше 2, а пиксел должен иметь ненулевую метку (в силу симметричности конфигурации). Итак, продолжим доказательство, считая, что пиксел имеет ненулевую метку. В данном случае пиксел входит в контур; его н-соседями являются пикселы и а, имеющие ненулевые метки. Следовательно, метка пиксела должна быть нулевой, и, таким образом, пикселы образуют конфигурацию, имеющую код

Этот результат позволяет без потери общности допустить, что пиксел (см. рис. 7.21) имеет метку, значение которой не меньше

2. Теперь перейдем к рассмотрению допустимых конфигураций пикселов

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

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

Рис. 7.22. Иллюстрация к случаю 1: а — общий и — частный случай

Рис. 7.23. Иллюстрация к случаю 2: ни один из пикселов с метками 2 и не является существенным для связности, однако при удалении их обоих число связности изменяется

Случай 2. Пикселы имеют нулевые метки. В таком случае нетрудно убедиться в том, что пиксел не может иметь соседей с единичной меткой и, следовательно, должен классифицироваться в соответствии с условием На рис. 7.23 приведена конфигурация (и ее код), соответствующая этому случаю.

Случай 3. Пиксел имеет ненулевую метку, а пиксел — нулевую. (Случай, когда метка пиксела — нулевая, а значение метки пиксела больше нуля, аналогичен и мы не будем его обсуждать). Если пикселы имеют нулевые метки, то контур ведет от пиксела к пикселу и пиксел не может быть кратным, если он не удовлетворяет условию (в). Соответствующая конфигурация и ее код приведены на рис. 7.2.4, а а на рис. 7.2.4, б представлен частный случай. Если метки пикселов не равны нулю одновременно, а оба пиксела имеют нулевые метки, то пиксел не имеет соседей внутри области и должен классифицироваться в соответствии с условием

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

Утверждение 7.4. Проверка условия (в) эквивалентна поиску конфигурации вида, приведенного на рис. 7.25 (а также

конфигураций, полученных в результате поворота указанной конфигурации на 90° в произвольном направлении). По меньшей мере, один из обозначенных символом С пикселов должен иметь ненулевую метку; если ненулевую метку имеют оба пиксела, обозначенные символом то метки пикселов, обозначенных символами А и В, могут быть любыми, в противном случае по меньшей мере один из каждой пары пикселов А и В должен иметь ненулевую метку.

Рис. 7.24. Иллюстрация к случаю 3: а — общий и б — частный случаи

Рис. 7.25. Конфигурация, наличие которой эквивалентно выполнению условия (в)

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

Рис. 7.26. Пример кратного пиксела удовлетворяющего условию (в), причем этот пиксел не удовлетворяет ни одному из двух других условий (слева); пример, когда для пиксела Р условие (в) не выполняется (справа)

Итак, нами получено другое определение для кратных пикселов.

Теорема 7.3. Пиксел является кратным, если он удовлетворяет хотя бы одному из следующих условий:

(а) его окрестность соответствует одной из конфигураций, представленных на рис. 7.20 (или конфигурациям, полученным их поворотом на 90° в произвольном направлении); пикселы второй конфигурации, обозначенные символом А, могут иметь метки с произвольными значениями;

(б) пиксел имеет хотя бы одного соседа с ненулевой меткой или не имеет соседей с метками, равными единице;

(в) окрестность пиксела соответствует конфигурации, представленной на рис. 7.25 (или конфигурациям, полученным ее поворотом на 90° в произвольном направлении).

Очевидно, что перечисленные условия можно проверять как в последовательном, так и параллельном режимах. Сформулируем результат, связывающий понятие кратных пикселов с тонкими линиями и кривыми.

Утверждение 7.5. Любая линейчатая область состоит исключительно из кратных пикселов. И, наоборот, если некоторая область содержит только кратные пикселы, то она является линейчатой.

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

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