9.4. РЕАЛИЗАЦИЯ АСИНХРОННОГО АЛГОРИТМА ПРОРЕЖИВАНИЯ

Проверка выполнения трех условий, входящих в теорему 7.3, может выполняться следующим образом. Введем пять восьмибитовых регистров значения каждого разряда которых задаются в соответствии со значениями соседей пиксела. -сосед ставится в соответствие самому старшему разряду, -сосед — следующему по старшинству разряду и т. д. (используемые обозначения соответствуют рис. 7.4). Если значение пиксела равно у, то задаются значения соответствующих битов во всех байтах Первоначально все пикселы имеют значения 0 или 1, и поэтому можно задать значения лишь в байте Если выясняется, что пиксел принадлежит контуру, то его значение заменяется на двойку, в результате чего становится возможным задание значений в байте Конфигурации, приведенные на рис. 9.3, нетрудно представить как результаты побитового применения масок к указанным регистрам. Маски задаются в виде восьмеричных чисел. Например, первая из конфигураций рис. 9.3, а соответствует числу Мы будем использовать запись для обозначения побитовой операции И, примененной к цепочкам таким образом, в цепочке, полученной в результате операции единичные значения разрядов будут соответствовать ненулевым значениям 1-, 2- и -соседей текущего пиксела. Для работы с конфигурациями, полученными в результате поворота исходной на 90°, необходимо просто осуществить в каждом регистре сдвиг на два разряда. Поэтому ниже мы не будем больше заниматься такими конфигурациями. (Каждому заданному критерию соответствует еще один или три критерия, полученные при помощи указанной операции сдвига.) Имеет место следующий простой результат.

Утверждение 9.2. Справедливы следующие обратные им утверждения:

(а) пиксел принадлежит контуру, если результат операции не равен 2528;

(б) окрестность пиксела соответствует левой конфигурации, приведенной на рис. 9.3, а если

(в) окрестность пиксела соответствует правой конфигурации, приведенной на рис. 9.3, а если ;

(г) пиксел не имеет соседней внутренней области, если запись в тождественна записи в ;

(д) пиксел соответствует требованиям конфигурации, приве денной на рис. 9.3 б если и если вы полняется одно из следующих условий.

(д1) результаты операций больше один из результатов операций, включенный в условие

(д1), больше 0 и оба результата операций больше 0.

Доказательство. Все перечисленные утверждения можно доказать при помощи непосредственного использования соответствующих определений. Например, в утверждении цепочка 200а выделяет -соседа (самый старший бит маски является единичным). Наложение этой маски на с помощью операции дает 1, если -сосед принадлежит границе, и 0 — в остальных случаях. Цепочка выделяет -соседа и наложение этой маски на с помощью операции И дает 1, если этот пиксел имеет ненулевое значение, и 0 — в остальных случаях. Следовательно, два эти условия служат критерием конфигурации рис. 9.3, б, образованной тремя пикселями, которые находятся в среднем ряду.

Эти результаты использованы в алгоритме 9.3 На шаге 4 отыскиваются пикселы, находящиеся на границе; на шаге 5 проверяется часть условия (б) теоремы 7.3, а на шаге 6 проверяется условие, содержащееся в утверждении 9.2 (б). На шаге 8 проводится разметка пикселов, не имеющих соседей внутри области, а на шаге 9 проводится проверка соответствия конфигурации, приведенной на рис. 9.3, б. На шагах 11 и 12 проверяются условия определения 9.3. На шаге 15 удаляются все пикселы со значениями меток 2 и 5. Шаги 6, 9, 11 и 12 предусмотрены для обработки конфигураций, имеющих другие ориентации (последние воспроизводятся посредством сдвига битовых комбинаций на два разряда).

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

Алгоритм 9.3. Асинхронный алгоритм прореживания

Обозначения. С — значение счетчика числа итераций, увеличенное на 5. Признак удаление указывает, подвергались ли пикселы удалению.

(см. скан)

(см. скан)

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

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

Рис. 9.6. Результат применения асинхронного алгоритма прореживания: символ «-»- удалённые пикселы, символ «О» — пикселы остова