9.2. КЛАССИЧЕСКИЕ АЛГОРИТМЫ ПРОРЕЖИВАНИЯ
Большинство алгоритмов, описанных в литературе, относят к категории остовных лишь такие пикселы, которые соответствуют конфигурациям, приведенным на рис. 7.20 и 9.3. а, т. е. пикселы, удовлетворяющие условию (а) теоремы 7.3. Для того чтобы не пропустить пикселы, удовлетворяющие другим условиям этой теоремы, в них используется очень специфический способ проверки условия 
Отметим, что условие 
представляет собой, в сущности, некоторый критерий связности и его последовательное применение к некоторому изображению приведет к стягиванию односвязной (т. е. не имеющей отверстий) области в один пиксел — очевидно, это не тот результат, к которому мы стремимся.
Рис. 9.3. Конфигурации окрестностей кратных пикселов а - по меньшей мере один из каждой группы пикселов, помеченных символами А и В должен иметь ненулевое значение, б — по меньшей мере один из пикселов, помеченных символом С, должен иметь ненулевое значение Если оба пиксела, обозначенные символом С, имеют ненулевые значения, то пикселы, обозначенные символами 
и В, могут принимать любые значения В противном случае, по меньшей мере, один из пикселов каждой пары пикселов, обозначенных символами А или В, должен иметь ненулевое значение
Такое затруднение можно преодолеть, осматривая пикселы параллельно и обобщая определение 9.2 посредством добавления в него условия, согласно которому пиксел, отнесенный к категории остовных в процессе одной из итераций, не может быть после этого исключен из рассмотрения. Так, если 
— горизонтально расположеный массив пикселов, то удаление из его середины одного из пикселов приводит к нарушению условия связности. Следовательно, удаляться будут лишь два концевых пиксела массива, а остальные будут считаться элементами окончательного решения. Остается, однако, одна трудность: если массив состоит из пар пикселов типа приведенных на рис. 7.17, то ни один из них не является определяющим с точки зрения связности, и поэтому все они будут удалены. Последнее препятствие можно преодолеть, используя сочетание параллельной и последовательной обработок. Одновременной проверке подвергаются не все пикселы контура, а только те, TV-соседи которых имеют нулевую метку, где N
принимает последовательно значения 0, 2, 4 и 6. Тогда массив, толщина которого равна двум пикселам, будет в первую очередь посредством прореживания превращен в массив толщиной в один пиксел, и, таким образом, часть пикселов этого массива будет сохранена. При использовании алгоритмов такого типа разметку остовных пикселов необходимо выполнять специальным образом с тем, чтобы предотвратить их удаление при какой-либо из очередных итераций вследствие их некритичности с точки зрения связности. Этот метод реализован в алгоритме 9.1. Он предназначен для работы с двухуровневым изображением, пикселы которого могут быть снабжены метками 0 или 1. Пикселы, составляющие изображения, могут в процессе прореживания получать также метки 2 или 3, так что при изучении конфигураций окрестностей такие значения меток следует считать индикатором наличия пиксела. Процедуру сопоставления конфигураций окрестностей, выполняемую на шаге 9, легко реализовать, если сформировать цепочку из меток восьми соседей пиксела 
. В этом случае приходится сравнивать всего лишь две цепочки символов. Пример применения данного алгоритма приведен на рис. 9.4.
Рис. 9.4. Пример, характеризующий работу классического алгоритма прореживания: символ «-» — удаленные пикселы, символ «О» — пикселы остова
Алгоритм 9.1. Классический алгоритм прореживания
Обозначения. I — изображение, подаваемое на вход алгоритма. Р — множество конфигураций окрестностей остовных пикселов, представленных на рис. 9.3, а, и конфигураций, полученных в результате поворота первой конфигурации на 90°
и трех последовательных поворотов второй на 90°. Истинное значение признака оставление используется для обозначения того, что пикселы, не принадлежащие остову, могут быть оставлены. Признак ост принимает истинное значение в случаях, когда окрестность пиксела соответствует одной из конфигураций окрестностей, входящих в множество Р. Единица в описании конфигурации соответствует пикселу окрестности, имеющему ненулевое значение.
(см. скан)
