Алгоритмы выделения контуров.
Алгоритмы выделения контуров можно условно разбить на две группы: отслеживающие
и сканирующие.
1. Отслеживающие алгоритмы на примере алгоритма “жука”.
Общее описание алгоритма.
Отслеживающие алгоритмы основаны на том, что на изображении отыскивается объект
(первая встретившаяся точка объекта) и контур объекта отслеживается и
векторизуется. Достоинством данных алгоритмов является их простота, к
недостаткам можно отнести их последовательную реализацию и некоторую сложность
при поиске и обработке внутренних контуров. Пример отслеживающего алгоритма -
"алгоритма жука" - приведен на рис. 5.12. Жук начинает движение с белой области
по направлению к черной, Как только он попадает на черный элемент, он
поворачивает налево и переходит к следующему элементу. Если этот элемент белый,
то жук поворачивается направо, иначе - налево. Процедура повторяется до тех пор,
пока жук не вернется в исходную точку. Координаты точек перехода с черного на
белое и с белого на черное и описывают границу объекта.
На рис. 1 показана схема работы такого алгоритма.
Рис. 1. Схема работы отслеживающего алгоритма “жука”.
1.2 Создание программы, реализующий данный алгоритм.
Данная программа реализована в среде программирования Borland C++ Builder 4.
Общий вид главного окна программы в исходном положении показан на рис. 2.
Рис. 2. Главное окно программы в исходном положении.
Слева находится исходное изображение, справа находится изображение на котором
будут рисоваться выделяемые контуры объекта.
Исходные тексты формы представлены в листинге 1.
В листингах 2 и 3 находятся исходные тексты главного модуля программы и модуля
главной формы.
В листинге 4 представлен модуль, содержащий в себе функции выделения контуров
объектов.
2. Сканирующие алгоритмы.
2.2. Общее описание алгоритма.
Сканирующие алгоритмы основаны на просмотре (сканировании) всего изображения и
выделения контурных точек без отслеживания контура объекта.
Рассмотрим алгоритм, основанный на разработанной схеме хранения полосы
изображения в памяти ЭВМ и нахождения контурных точек в процессе движения полосы
по всему изображению. Для обработки информации в полосе различают два случая:
выявление ситуации в полосе изображения и ее разрешение. В полосе одновременно
хранятся две строки изображения (текущая и предыдущая). Анализируются Х
координаты черных серий обеих строк в порядке их возрастания (слева направо) и
выявляются пять ситуаций, которые могут возникнуть.
Ситуация "начало" возникает в том случае, когда черная серия текущей строки
полностью покрывается белой серией предыдущей строки (рис. 4, а).
Для ситуации "продолжение" характерно частичное перекрытие черных серий обеих
строк (рис.4,б).
Если две соседние черные серии текущей строки покрываются черной серией
предыдущей строки, возникает ситуация "ветвление"(рис. 4, в).
Ситуация "слияние" выявляется в том случае, когда черная серия текущей строки
касается двух соседних черных серий предыдущей строки (рис.4, г).
Ситуация "конец" возникает, когда белая серия текущей строки полностью покрывает
черную серию предыдущей строки (рис.4, д).
Рис. 4. Ситуации.
Обрабатываемые строки представлены в виде массивов структур, куда входит
координата Х начала/конца черной серии и адрес буфера, предназначенного для
сбора и хранения информации по одной ветке (части контура), которая пересекает
обрабатываемую строку. В буфере содержатся тип ветки (левая или правая в
зависимости от расположения черной серии связной компоненты), ее внутренний
номер, параметры отслеженной части контура (длина, площадь, габариты) и ее
координатное описание, адрес буфера парной ветки, которая является частью того
же контура и некоторые другие параметры.
При выявлении ситуации "начало" из стека свободных буферов выбирают два (для
левой и правой веток). Каждая пара веток имеет свой уникальный номер, который
возрастает по мере появления новых веток.
При обнаружении ситуации "продолжение" в буферы, адреса которых выбираются из
описания верхней строки, дописываются координаты новых точек и уточняются
геометрические параметры. Одновременно производится полигональная аппроксимация
веток. В случае заполнения буфера метрическое описание соответствующего участка
контура записывается в выходной файл, а в буфере сохраняется адрес записанного
участка, что дает возможность связать ссылками участки одного контура.
При выявлении ситуации "ветвление" точки ветвления обрабатываются по аналогии с
ситуацией "начало".
Ситуация "слияние" возникает тогда, когда закончено отслеживание внутреннего
контура, и когда объединяются ветки одного контура. В первом случае происходит
объединение информации обеих веток и запись в выходную структуру. Во втором
случае ветка с меньшим номером "поглощает" ветку с большим номером и ее пару.
Объединенная информация сохраняется в буфере ветки с меньшим номером, а в
текущей строке адрес буфера парной ветки меняется на адрес буфера оставшейся
ветки. В обоих случаях буферы "поглощенной" пары освобождаются.
Ситуация "конец" свидетельствует о том. что либо закончилось отслеживание
внешнего контура, либо сливаются ветки одного контура. Обработка производится по
аналогии с обработкой ситуации "слияние".
В листинге 4 представлен модуль, содержащий в себе функции выделения контуров
объектов.
Листинг 2. Главный модуль программы:
//---------------------------------------------------------------------------
#include
#pragma hdrstop
USERES("Graphics.res");
USEFORM("MainUnit.cpp", Form1);
USEUNIT("GraphicUnit.cpp");
//---------------------------------------------------------------------------
WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
try
{
Application->Initialize();
Application->CreateForm(__classid(TForm1), &Form1);
Application->Run();
}
catch (Exception &exception)
{
Application->ShowException(&exception);
}
return 0;
}
//---------------------------------------------------------------------------
Листинг 3. Модуль главной формы
Файл заголовка:
//---------------------------------------------------------------------------
#ifndef MainUnitH
#define MainUnitH
//---------------------------------------------------------------------------
#include
#include
#include
#include
#include
#include
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:// IDE-managed Components
TPanel *Panel1;
T8308_ *From8308_;
TPanel *Panel2;
T8308_ *To8308_;
TButton *Button1;
void __fastcall Button1Click(TObject *Sender);
private:// User declarations
public:// User declarations
__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
cpp файл:
//---------------------------------------------------------------------------
#include
#pragma hdrstop
#include "MainUnit.h"
#include "GraphicUnit.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
AlgorithmBeatle(From8308_->Picture->Bitmap,
To8308_->Picture->Bitmap);
To8308_->Visible = false;
To8308_->Visible = true;
}
//---------------------------------------------------------------------------
Листинг 4. Модуль выделения контуров.
Файл заголовка:
cpp файл:
//---------------------------------------------------------------------------
#include
#pragma hdrstop
#include "GraphicUnit.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#include
/*
Отслеживающий алгоритм выделения контуров
"Алгоритм жука"
*/
void AlgorithmBeatle(Graphics::TBitmap* From8308_,
Graphics::TBitmap* To8308_)
{
typedef enum {North, East, South, West} TDirectional;
int X,Y; // Координаты первой встречи с объектом
int cX,cY; // Текущие координаты маркера
Byte *Line, *ToLine; // Обрабатываемые линии
Byte B; // Значение текущего пиксела
TDirectional Direct; // Направление движения жука
// Идем до тех пор, пока не встретим черную область
for (Y = 0; Y < From8308_->Height; Y++)
{
Line = (Byte*)From8308_->ScanLine[Y];
for (X = 0; X < From8308_->Width; X++)
{
B = Line[X];
if (B < 255)>
break;
}
// Если встречен объект, отличающийся от цвета фона (255 - белый)
// прервать поиск
if (X != From8308_->Width)
break;
}
// Если не нашли ни одного черного пиксела, то выходим из процедуры
if ((X == From8308_->Width) && (Y == From8308_->Height))
return;
// Если все нормально, начинаем обход по алгоритму жука
ToLine = (Byte*)To8308_->ScanLine[Y];
ToLine[X] = 0;
// Поворачиваем налево (новое направление - север)
cX = X;
cY = Y - 1;
Direct = North;
Line = (Byte*)From8308_->ScanLine[cY];
// Пока не придем в исходную точку, выделяем контур объекта
while ((cX != X) (cY != Y))
{
// В зависимости от текущего направления движения жука
switch (Direct)
{
// Север
case North:
{
B = Line[cX];
// Если элемент "черный", поворачиваем снова "налево"
if (B < 255)>
{
ToLine = (Byte*)To8308_->ScanLine[cY];
ToLine[cX] = 0;
Direct = West;
cX--;
}
// Иначе поворачиваем "направо"
else
{
Direct = East;
cX++;
}
}
break;
// Восток
case East:
{
B = Line[cX];
// Если элемент "черный", поворачиваем снова "налево"
if (B < 255)>
{
ToLine = (Byte*)To8308_->ScanLine[cY];
ToLine[cX] = 0;
Direct = North;
cY--;
Line = (Byte*)From8308_->ScanLine[cY];
}
// Иначе поворачиваем "направо"
else
{
Direct = South;
cY++;
Line = (Byte*)From8308_->ScanLine[cY];
}
}
break;
// Юг
case South:
{
B = Line[cX];
// Если элемент "черный", поворачиваем снова "налево"
if (B < 255)>
{
ToLine = (Byte*)To8308_->ScanLine[cY];
ToLine[cX] = 0;
Direct = East;
cX++;
}
// Иначе поворачиваем "направо"
else
{
Direct = West;
cX--;
}
}
break;
// Запад
case West:
{
B = Line[cX];
// Если элемент "черный", поворачиваем снова "налево"
if (B < 255)>
{
ToLine = (Byte*)To8308_->ScanLine[cY];
ToLine[cX] = 0;
Direct = South;
cY++;
Line = (Byte*)From8308_->ScanLine[cY];
}
// Иначе поворачиваем "направо"
else
{
Direct = North;
cY--;
Line = (Byte*)From8308_->ScanLine[cY];
}
}
}
}
}
// ---------------------------------------------------------------------------
void AlgorithmScan(Graphics::TBitmap* From8308_,
Graphics::TBitmap* To8308_)
{
// Тип ветви (левая или правая)
typedef enum {bLeft, bRight} TBranchType;
// Структура, описывающая ветвь
struct TBranch
{
TBranchType BranchType; // Тип ветви
TBranch* Branch; // Парная ветвь
};
// Структура, описывающая строку
struct TString
{
int BeginX; // Начало черной серии
int EndX; // Конец черной серии
TBranch* Branch; // Указатель на структуру ветви
};
// Возможные ситуации
typedef enum {
sBegin, // Начало
sNext, // Продолжение
sBranch, // Ветвление
sFusion, // Слияние
sEnd // Конец
} TSituation;
// Сканируемая полоса
struct TLine
{
Byte* L1; // Верхняя линия
Byte* L2; // Нижняя линия
};
int Y; // Текущая координата Y
int X; // Текущая координата X
int cX; // Временная координата X для сканирования
TLine Line; // Сканируемая полоса
TSituation CurrentSituation; // Текущая ситуация
for (Y = 0; Y < From8308_->Height; Y++)
{
Line.L1 = (Byte*)From8308_->ScanLine[Y];
Y++;
Line.L2 = (Byte*)From8308_->ScanLine[Y];
// Пробуем выявить ситуации:
// Ищем первый черный элемент во второй линии сканируемой полосы
for (X = 0; X < From8308_->Width; X++)
{
if (Line.L2[X] < 255)>
{
// Если черный элемент найден, пытаемся уточнить ситуацию
CurrentSituation = sBegin;
for (cX = X; cX < From8308_->Width; cX++)
{
}
}
}
}
}