2. Сканируюющие алгоритмы.

Сканирующие алгоритмы основаны на просмотре (сканировании) всего изображения и выделения контурных точек без отслеживания контура объекта.

Рассмотрим алгоритм, осно­ванный на разработанной схеме хранения полосы изображения в памяти ЭВМ и нахождения контурных точек в процессе движения полосы по всему изображению. Для обработки информации в полосе различают два случая: выявление ситуации в полосе изображения и ее разрешение. В полосе одновременно хранятся две строки изображения (текущая и предыдущая). Анализируются Х координаты черных серий обеих строк в порядке их возрастания (слева направо) и выявляются пять ситуаций, которые могут возникнуть.

Ситуация "начало" возникает в том случае, когда черная серия текущей строки полностью покрывается белой серией предыдущей строки (рис. 4, а).

Для ситуации "продолжение" характерно частичное перекрытие черных серий обеих строк (рис.4,б).

Если две соседние черные серии текущей строки покрываются черной серией предыдущей строки, возникает ситуация "ветвление"(рис. 4, в).

Ситуация "слияние" выявляется в том случае, когда черная серия текущей строки касается двух соседних черных серий предыдущей строки (рис.4, г).

Ситуация "конец" возникает, когда белая серия текущей строки полностью покрывает черную серию предыдущей строки (рис.4, д).

Рис. 4. Различные ситуации, встречающиеся в ходе сканирования.

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

При выявлении ситуации "начало" из стека свободных буферов выбирают два (для левой и правой веток). Каждая пара веток имеет свой уникальный номер, который возрастает по мере появления новых веток.

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

При выявлении ситуации "ветвление" точки ветвления обрабатываются по аналогии с ситуацией "начало".

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

"поглощенной" пары освобождаются.

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