Алгоритмы выделения контуров

Алгоритмы выделения контуров можно
условно разбить на две группы: отслеживающие и сканирующие. Отслеживающие алгоритмы основаны на том, что на
изображении отыскивается объект (первая встретившаяся точка объекта) и контур
объекта отслеживается и векторизуется. Достоинством данных алгоритмов является
их простота, к недостаткам можно отнести их последовательную реализацию и
некоторую сложность при поиске и обработке внутренних контуров. Пример
отслеживающего алгоритма - "алгоритма жука" - приведен на рис. 5.12. Жук
начинает движение с белой области по направлению к черной, Как только он
попадает на черный элемент, он поворачивает налево и переходит к следующему
элементу. Если этот элемент белый, то жук поворачивается направо, иначе -
налево. Процедура повторяется до тех пор, пока жук не вернется в исходную точку.
Координаты точек перехода с черного на белое и с белого на черное и описывают
границу объекта. Рис.
1. Схема работы отслеживающего алгоритма "жука". Данная программа реализована в среде
программирования Borland C++ Builder 4. Рис.
2. Главное окно программы в исходном положении. Слева находится исходное
изображение, справа находится изображение на котором будут рисоваться выделяемые
контуры объекта. В
листингах 2 и 3 находятся исходные тексты главного модуля программы и модуля
главной формы. 2. Сканирующие алгоритмы. основаны на просмотре
(сканировании) всего изображения и выделения контурных точек без отслеживания
контура объекта. Рассмотрим алгоритм, основанный на разработанной схеме
хранения полосы изображения в памяти ЭВМ и нахождения контурных точек в процессе
движения полосы по всему изображению. Для обработки информации в полосе
различают два случая: выявление ситуации в полосе изображения и ее разрешение. В
полосе одновременно хранятся две строки изображения (текущая и предыдущая).
Анализируются Х координаты черных серий обеих строк в порядке их возрастания
(слева направо) и выявляются пять ситуаций, которые могут возникнуть. Ситуация
"начало" возникает в том случае, когда черная серия текущей строки полностью
покрывается белой серией предыдущей строки (рис. 4, а). Если две соседние черные серии текущей строки покрываются черной
серией предыдущей строки, возникает ситуация "ветвление"(рис. 4, в). Ситуация
"слияние" выявляется в том случае, когда черная серия текущей строки касается
двух соседних черных серий предыдущей строки (рис.4, г). Ситуация "конец"
возникает, когда белая серия текущей строки полностью покрывает черную серию
предыдущей строки (рис.4, д). Обрабатываемые строки представлены в виде массивов структур,
куда входит координата Х начала/конца черной серии и адрес буфера,
предназначенного для сбора и хранения информации по одной ветке (части контура),
которая пересекает обрабатываемую строку. В буфере содержатся тип ветки (левая
или правая в зависимости от расположения черной серии связной компоненты), ее
внутренний номер, параметры отслеженной части контура (длина, площадь, габариты)
и ее координатное описание, адрес буфера парной ветки, которая является частью
того же контура и некоторые другие параметры. При выявлении ситуации "начало"
из стека свободных буферов выбирают два (для левой и правой веток). Каждая пара
веток имеет свой уникальный номер, который возрастает по мере появления новых
веток. При обнаружении ситуации "продолжение" в буферы, адреса которых
выбираются из описания верхней строки, дописываются координаты новых точек и
уточняются геометрические параметры. Одновременно производится полигональная
аппроксимация веток. В случае заполнения буфера метрическое описание
соответствующего участка контура записывается в выходной файл, а в буфере
сохраняется адрес записанного участка, что дает возможность связать ссылками
участки одного контура. Ситуация "слияние" возникает
тогда, когда закончено отслеживание внутреннего контура, и когда объединяются
ветки одного контура. В первом случае происходит объединение информации обеих
веток и запись в выходную структуру. Во втором случае ветка с меньшим номером
"поглощает" ветку с большим номером и ее пару. Объединенная информация
сохраняется в буфере ветки с меньшим номером, а в текущей строке адрес буфера
парной ветки меняется на адрес буфера оставшейся ветки. В обоих случаях буферы
"поглощенной" пары освобождаются. Ситуация "конец" свидетельствует о том. что
либо закончилось отслеживание внешнего контура, либо сливаются ветки одного
контура. Обработка производится по аналогии с обработкой ситуации "слияние". Листинг 2. Главный модуль программы: #pragma
hdrstop //--------------------------------------
------------------------------------- Application-
>CreateForm(__classid(TForm1), &Form1); Application-
>ShowException(&exception); Листинг 3. Модуль
главной формы #ifndef MainUnitH #include <Classes.hpp> #include <ExtCtrls.hpp> class TForm1 : public TForm T8308_ *To8308_; public:// User
declarations //-----------------
---------------------------------------------------------- #endif #include <vcl.h> //--------------
------------------------------------------------------------- //------------
--------------------------------------------------------------- //----------------
----------------------------------------------------------- To8308_->Picture->Bitmap); //--------------------
------------------------------------------------------- //-----------------------
---------------------------------------------------- //----------------------------------------
----------------------------------- Graphics::TBitmap* To8308_); cpp файл: #pragma hdrstop #pragma
package(smart_init) void
AlgorithmBeatle(Graphics::TBitmap* From8308_, int
X,Y; // Координаты первой встречи с объектом Byte B; // Значение
текущего пиксела for (Y = 0; Y <
From8308_->Height; Y++) B = Line[X]; // прервать поиск // Если не нашли ни одного черного пиксела, то выходим из процедуры // Если все нормально, начинаем обход по алгоритму жука // Поворачиваем налево
(новое направление - север) // Пока не придем в исходную точку,
выделяем контур объекта { if (B < 255) // Иначе
поворачиваем "направо" // Если элемент
"черный", поворачиваем снова "налево" cY--
; cY++; // Если элемент "черный", поворачиваем снова "налево" } case West: ToLine = (Byte*)To8308_->ScanLine[cY]; // Иначе поворачиваем "направо" // ------
--------------------------------------------------------------------- // Тип ветви (левая или правая)
TBranchType BranchType; // Тип ветви int BeginX;
// Начало черной серии // Возможные ситуации sEnd // Конец Byte* L2; // Нижняя
линия int cX; // Временная координата X для сканирования for
(Y = 0; Y < From8308_->Height; Y++) //
Пробуем выявить ситуации: { CurrentSituation = sBegin;