7.5.2. ОБХОД ВСЕХ КОНТУРОВ ОБЛАСТИ
Алгоритм 7.2 определяет все контуры области с помощью «писанной выше процедуры TRACER (ОБНАРУЖИТЕЛЬ КОНТУРА) и предусматривает, что контуры, обнаруженные с помощью этой процедуры, помещаются в очередь 
Поскольку описания контуров включают как пары значений координат 
так и кодовые последовательности, записанные в цепном коде, при организации очереди 
следует проявить определенную осторожность. Чтобы упростить описание алгоритма, допустим, что очередь 
содержит координаты х, у пиксела Р и значение цепного кода с. Если пиксел является начальной точкой контура, то 
Практически достаточно иметь массив, в котором хранятся только значения цепного кода, и использовать символ 8 для обращения к отдельному массиву, содержащему начальные точки. В таком случае координаты х, у каждой новой точки можно, учитывая информацию, содержащуюся в цепном коде, получать исходя из координат предыдущей точки. Данный алгоритм предусматривает также введение на изображении соответствующей маркировки для пикселов, выделенных в качестве элементов контура. Предполагается, что при работе с двухуровневыми изображениями первоначально пикселы, входящие в область, помечаются единицей, а не входящие в нее, — нулем. Процедуру TRACER можно модифицировать таким образом, что при присвоении пикселу метки «текущая точка» его значение увеличивается на 1. В результате в конце процесса построения контура образующие его пикселы будут иметь значения 2 или более. В частности, это значение будет
равно единице плюс число осмотров соответствующего пиксела в процессе обхода. Эти значения используются при поиске отверстий внутри области. Следующий метод позволяет избежать поиска в части изображения, лежащей за пределами представляющей интерес области.
После построения внешнего контура и введения его в очередь 
начинается изучение содержимого последней. Если встречается точка, расположенная на опускающейся дуге, поиск направляется вправо.
Рис. 7.10. Начало просмотра внутренней части области в точке перегиба внешнего контура. Цепной код, представляющий часть контура, изображенную с помощью стрелок, равен 665 456; точка В не выбирается в качестве начальной, а точка А выбирается
Такие пикселы легко определить, указав, что предшествующий элемент цепного кода должен иметь значения от 4 до 7, а следующий — от 5 до 7. Число 4 включено в диапазон допустимых значений предыдущего элемента для того, чтобы учесть точки перегиба, как показано на рис. 7.10. Поскольку для первого элемента направление предыдущего элемента неизвестно до тех пор, пока не будет установлено значение последнего элемента цепного кода данного контура, проверка первого элемента как начальной точки должна быть отложена до конца процедуры. (Мы не включили эту специфическую часть в описание алгоритма 7.2 для его упрощения.) В процессе просмотра по горизонтали необходимо отыскивать либо начало какого-либо отверстия, либо другую сторону внешнего контура. Эта задача осложняется тем, что некоторые пикселы могут одновременно входить во внешний контур какого-либо отверстия. Если известно, что таких пикселов нет, то необходимо искать лишь последовательности, состоящие из двух пикселов и имеющие значение 
(начало отверстия), и пары пикселов, имеющие значения 2 (или более) и 0 (внешний контур). При наличии пикселов, одновременно входящих в контур отверстия и внешний контур, требуется предусмотреть более сложные процедуры контроля, которые представлены как часть алгоритма 7 2.
Алгоритм 7.2. Полный алгоритм построения контура.
Обозначения. В очереди 
содержатся адреса пикселов Р и значения цепного кода с. Процедура REMOVE — та же, что и в алгоритме 6.3.
(см. скан)
(см. скан)
Для обозначения начала непросмотренного отверстия используется код 
поскольку некоторая дуга его контура может совпадать с некоторой дугой внешнего контура (рис. 7.11, а). С помощью кода 
обозначается просмотренное отверстие такого же типа, и после того, как поиск доходит до внешнего контура, он должен быть прекращен. Отметим, что области, целиком лежащие внутри отверстий (рис. 7.11, б), игнорируются. Дело в том, что контур отверстия, содержащего такую область, будет обнаружен в первую очередь (направление просмотра 
на рис. 7.11, б), после чего он будет построен и зарегистрирован. При перемещении направления просмотра вниз (например, направление VV на том же рисунке) просмотр прекратится вследствие обнаружения кодов 120 или 
Поскольку контуры отверстий, как и внешние контуры, встреченные при просмотре изображения, служат сигналом к прекращению просмотра, контуры отверстий также следует использовать в качестве отправного элемента поиска. Это осуществляется автоматически, так как эти контуры также помещаются в очередь 
На рис. 7.12 показан порядок обхода внутренней части области. Вложенные области могут быть обнаружены при последующих просмотрах изображения. Для повышения эффективности такого поиска в очередь можно поместить координаты х, у тех пикселов, на которых закончился просмотр внутренней части области по горизонтальному направлению; эта очередь должна просматриваться после построения контуров каждой связной области.
Рис. 7.11. Пример дуги, являющейся одновременно частью внешнего контура и частью контура отверстия (а), порядок просмотра вложенных областей (б)
Алгоритм 7.2 является эффективным, поскольку элементы изображения, не входящие ни в один из контуров, должны просматриваться лишь однократно, а элементы, принадлежащие одному из контуров, — лишь дважды. Так как нет необходимости помечать пикселы значениями, превышающими 3, алгоритм можно видоизменить таким образом, чтобы исключить приращение значений пикселов, после того как оно становится равным трем. В этом случае для хранения одного пиксела достаточно затрачивать два бита.
Рис. 7.12. Порядок просмотра внутренней части области
