Система числення

Алгоритми виділення контурів.
Алгоритми виділення контурів можна умовно розбити на дві групи: відстежують
і скануючі.
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. Модуль виділення контурів.
Файл заголовка:

//------------------------------------------------ --------------------------- # ifndef GraphicUnitH
# define GraphicUnitH
//------------------------------------------------ --------------------------- # include
extern void AlgorithmBeatle (Graphics:: TBitmap * From8308_,
Graphics:: TBitmap * To8308_);
extern void AlgorithmScan (Graphics:: TBitmap * From8308_,
Graphics:: TBitmap * To8308_);
# endif

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 Height; Y + +)
(
Line = (Byte *) From8308_-> ScanLine [Y];
for (X = 0; X 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 Height; Y + +)
(
Line.L1 = (Byte *) From8308_-> ScanLine [Y];
Y + +;
Line.L2 = (Byte *) From8308_-> ScanLine [Y];
//Пробуємо виявити ситуації:
//Ищем перший чорний елемент у другій лінії сканується смуги
for (X = 0; X Width; X + +)
(
if (Line.L2 [X] <255)>
(
//Якщо чорний елемент знайдений, намагаємося уточнити ситуацію
CurrentSituation = sBegin;
for (cX = X; cX Width; cX + +)
(
)
)
)
)
)