4.2.3. Итеративная модификация

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

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

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

Рис. 4.13. Построение нового бинарного изображения на основе большого числа вычислительных элементов, каждый из которых связан с небольшим числом соседних элементов изображения.

Рис. 4.14. Замена нулевого значения элемента, окруженного нулями, на единицу. Возникает новый объект, и тем самым число Эйлера увеличивается на единицу.

К счастью, число Эйлера удовлетворяет свойству аддитивности; поэтому его изменение зависит лишь от соседей конкретного элемента. Если поменять нулевое значение элемента с нулевыми соседями на единицу (рис. 4.14), то независимо от значений остальных элементов число Эйлера увеличится на единицу. Аналогично если все соседи (кроме одного) — нули или единицы, то число Эйлера остается неизменным при инвертировании значения в центральном элементе; в этом случае мы просто расширяем объект или сокращаем отверстие.

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

Рис. 4.15. (см. скан) Дифференциал Эйлера для каждого из пяти возможных вариантов окружения. Его можно получить, определяя изменение числа Эйлера при замене в центральном элементе нуля на единицу.

числа Эйлера Е, т. е. изменение числа Эйлера при замене в центральном элементе нуля на единицу. [В случае противоположной замены в центральном элементе (единицы на нуль) число Эйлера изменится на - Е.] Нас особенно интересуют такие случаи, когда поскольку мы можем произвольно варьировать изображение, не меняя числа Эйлера. Существует пять принципиально различных случаев (рис. 4.15):

а) , если все соседи — нули, возникает новый объект;

б) , если все соседи — единицы заполняется отверстие;

в) , если шесть соседей, рассматриваемые в виде циклической последовательности, можно разбить на одну последовательную группу нулей и одну последовательную группу единиц; если имеются две группы единиц, чередующиеся с двумя группами нулей: здесь объединяются два объекта или перегораживается отверстие;

с) , если три единицы чередуются с тремя нулями.

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

Остается еще одна трудность. Если мы будем обрабатывать все элементы изображения параллельно, то в итоге невольно можем изменить число Эйлера. Объясняется это тем, что мы можем испортить содержимое соседей какого-либо элемента изображения и тем самым исказить для него значение дифференциала Эйлера. Например, оба примыкающих друг к другу элемента со значением «единица», окруженные нулевым фоном, имеют дифференциал Эйлера, равный нулю:

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

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

Строка под ней нумеруется аналогично, только начинается с числа 2, а следующая строка — с числа 3:

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

Она решает проблему взаимного влияния изменений в соседних элементах при параллельной обработке. Все же для описания алгоритма итеративной модификации изображения мы нуждаемся в более четких обозначениях. Во-первых, обозначим через подмножество введенного выше множества стандартных случаев маркировки соседей. Положим величину равной единице, если случай маркировки соседей элемента изображения с координатами принадлежит Через обозначим значение самого элемента. Для каждого элемента. подразделенного на поля изображения, мы вычисляем его новое бинарное значение, которое является результатом работы итеративного алгоритма модификации над этим элементом. Нам остается указать способ вычисления нового значения на основе величин и

Здесь а, b и с — булевы переменные, они могут принимать значения лишь «нуль» и «единица». Вычисление с на основе эквивалентно заданию булевой функции двух переменных. Всего имеется таких функций, приведенных ниже:

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

Некоторые из этих функций не представляют большого интереса. Номер 0, например, всегда выдает нуль, а номер 15 — единицу. Четыре других (с номерами 3, 5, 10 и 12) воспроизводят значения и их дополнения В, а. Более интересны логическое И ( — номер 1) и логическое ИЛИ (v — номер 7). Их записывают также в виде и а соответственно. Эти операции обладают важным свойством монотонности. Применение первой может привести лишь к удалению единиц из изображения, поскольку а тогда как применение второй — к удалению нулей, поскольку а Следовательно, итеративные действия на основе этих функций обязательно завершатся, потому что наступит момент, когда либо изменения в изображении прекратятся, либо все поле заполнится нулями или единицами соответственно. Некоторые из оставшихся булевых операций, такие, как и а представляют мало интереса из-за того, что тот же самый эффект достигается операциями над дополнением к Поэтому у нас остается лишь ИСКЛЮЧАЮЩЕЕ ИЛИ (номер 6), обозначаемое Эта операция не монотонна. В результате из шестнадцати функций потенциально пригодны лишь четыре:

а) отмечает части изображения с указанными случаями маркировки соседей;

б) , приводит к срезанию краев объектов;

в) приводит к наращиванию объектов;

г) порождает волны, распространяющиеся по изображению.

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

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

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

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