9.3. АСИНХРОННЫЕ АЛГОРИТМЫ ПРОРЕЖИВАНИЯ

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

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

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

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

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

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

Определение 9.3. Если 4- или 2-сосед кратного пиксела имеет нулевое значение метки, то последний квалифицируется как удаляемый пиксел при условии, что у него нет соседа, который был бы уже квалифицирован как удаляемый.

Последнее ограничение необходимо для предотвращения получения несвязных объектов в случаях, аналогичных представленному на рис. 9.5. Здесь внутренние пикселы обозначены единицей; пикселы контура, не соответствующие ни одной из существенных конфигураций, обозначены двойкой; пикселы контура, соответствующие одной из конфигураций, приведенных на рис. 9.3,а, обозначены тройкой; пикселы контура, соответствующие конфигурации на рис. 9.3, б, обозначены четверкой или символом Оба пиксела, снабженные меткой 4, имеют 4- или -соседа с нулевой меткой, однако один из этих пикселов следует оставить. Алгоритм 9.2. Основной алгоритм прореживания

Обозначения. — множество пикселов исходного изображения, значения которых равны — граница множества — множество кратных пикселов, входящих в множество

(см. скан)

В алгоритме 9.2 реализуется определение 9.2. Он не зависит от способа отыскания кратных пикселов.

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