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

Белорусский Державний Університет Інформатики і Радиоэлектроники.

Контрольна робота з дисциплине.

«МАТИ».

Виконав студент групи 500 501.

Балахонів Є. В.

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

Алгоритми виділення контурів можна умовно розбити на дві групи: які відстежують і сканирующие.

1. Які Відстежують алгоритми з прикладу алгоритму «жука».

1 Загальне опис алгоритма.

Які Відстежують алгоритми засновані у тому, що у зображенні відшукується об'єкт (перша яка зустрілася точка об'єкта) і контур об'єкта відстежується і векторизуется. Перевагою даних алгоритмів був частиною їхнього простота, до недоліків можна віднести їх не послідовну реалізацію і деяку складність у пошуку та їх обробки внутрішніх контурів. Приклад відстежує алгоритму — «алгоритму жука «- наведено на рис. 5.12. Жук починає рух із білою області з до чорної, Як він потрапляє про чорний елемент, він повертає ліворуч кермо і переходить ось до чого елементу. Якщо це елемент білий, то жук повертається направо, інакше — наліво. Процедура повторюється до того часу, поки жук не повернеться вихідну точку. Координати точок переходу з чорного на біле і з білого на чорне й описують кордон объекта.

На рис. 1 показано схема роботи такого алгоритму. [pic].

Рис. 1. Схема роботи відстежує алгоритму «жука».

1.2 Створення програми, який реалізує даний алгоритм.

Ця програма реалізована серед програмування Borland З++ Builder 4.

Загальний вид головного вікна програми в вихідному становищі показаний на рис. 2.

[pic].

Рис. 2. Головне вікно програми в вихідному положении.

Зліва перебуває вихідне зображення, справа перебуває зображення на якому буде вималювалася виділені контури объекта.

Вихідні тексти форми представлені у листингу 1.

У листингах 2 і трьох перебувають вихідні тексти головного модуля програми і модуля головною формы.

У листингу 4 представлений модуль, яке у собі функції виділення контурів объектов.

На рис. 3 помітні результат роботи алгоритмів виділення контуров.

[pic].

Рис. 3. Результат роботи відстежує алгоритму виділення контуров.

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

2.2. Загальне опис алгоритма.

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

Розглянемо алгоритм, заснований на розробленої схемою зберігання смуги зображення на пам’яті ЕОМ й знаходження контурних точок у процесі руху смуги з усього зображенню. Для обробки інформацією смузі розрізняють два випадку: виявлення ситуації у смузі зображення її дозвіл. У смузі одночасно зберігаються два простих рядки зображення (поточна і попередня). Аналізуються Х координати чорних серій обох рядків порядку їх зростання (зліва-направо) вдається виявити п’ять ситуацій, які можуть опинитися возникнуть.

Ситуація «початок «виникає у тому випадку, коли чорна серія поточної рядки повністю покривається білої серією попередньої рядки (рис. 4, а).

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

Якщо дві сусідні чорні серії поточної рядки покриваються чорної серією попередньої рядки, виникає ситуація «галуження «(рис. 4, в).

Ситуація «злиття «виявляється у разі, коли чорна серія поточної рядки двох сусідніх чорних серій попередньої рядки (рис. 4, р). Ситуація «кінець «виникає, коли біла серія поточної рядки повністю покриває чорну серію попередньої рядки (рис. 4, д).

[pic].

Рис. 4. Ситуации.

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

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

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

При виявленні ситуації «галуження «точки розгалуження обробляються по аналогії із ситуацією «початок » .

Ситуація «злиття «виникає тоді, коли закінчено відстеження внутрішнього контуру, і коли об'єднуються гілки одного контуру. У першому разі відбувається об'єднання інформації обох гілок і запис в вихідну структуру. У другий випадок гілка із меншим номером «поглинає «гілку з великим номером і його пару. Об'єднана інформація зберігається у буфері гілки із меншим номером, а поточної рядку адресу буфера парної гілки змінюється на адресу буфера що залишилася гілки. У обох випадках буферы «поглинутою «пари освобождаются.

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

[pic].

Рис. 6. Результат роботи сканирующего алгоритму виділення контуров.

У листингу 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;

TImage *FromImage;

TPanel *Panel2;

TImage *ToImage;

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 (FromImage->Picture->Bitmap,.

ToImage->Picture->Bitmap);

ToImage->Visible = false;

ToImage->Visible = true;

}.

//——————————————————————————————————— ——;

Лістинг 4. Модуль виділення контуров.

Файл заголовка:

//——————————————————————————————————— ——;

#ifndef GraphicUnitH.

#define GraphicUnitH.

//——————————————————————————————————— ——;

#include.

extern void AlgorithmBeatle (Graphics:TBitmap* FromImage,.

Graphics:TBitmap* ToImage); extern void AlgorithmScan (Graphics:TBitmap* FromImage,.

Graphics:TBitmap* ToImage);

#endif.

cpp файл:

//——————————————————————————————————— ——;

#include.

#pragma hdrstop.

#include «GraphicUnit.h «.

//——————————————————————————————————— ——;

#pragma package (smart_init).

#include.

/*.

Що Відстежує алгоритм виділення контуров.

" Алгоритм жука «.

*/.

void AlgorithmBeatle (Graphics:TBitmap* FromImage,.

Graphics:TBitmap* ToImage).

{ typedef enum {North, East, South, West} TDirectional; int X, Y; // Координати першої зустрічі з об'єктом int cX, cY; // Поточні координати маркера.

Byte *Line, *ToLine; // Оброблювані линии.

Byte B; // Значення поточного пиксела.

TDirectional Direct; // Напрямок руху жука.

// Йдемо до того часу, доки зустрінемо чорну область for (Y = 0; Y < FromImage->Height; Y++).

{.

Line = (Byte*)FromImage->ScanLine[Y]; for (X = 0; X < FromImage->Width; X++).

{.

B = Line[X]; if (B < 255) break;

}.

// Якщо зустрінутий об'єкт, відрізняється від кольору фону (255 — белый).

// перервати пошук if (X ≠ FromImage->Width) break;

}.

// Якщо знайшли жодної чорної пиксела, то виходимо з процедури if ((X == FromImage->Width) && (Y == FromImage->Height)) return;

// Якщо всі нормально, починаємо обхід за алгоритмом жука.

ToLine = (Byte*)ToImage->ScanLine[Y];

ToLine[X] = 0;

// Повертаємо наліво (новий напрям — північ) cX = X; cY = Y — 1;

Direct = North;

Line = (Byte*)FromImage->ScanLine[cY];

// Поки що прийдемо в вихідну точку, виділяємо контур об'єкта while ((cX ≠ X) || (cY ≠ Y)).

{.

// Залежно від того плинного напрями руху жука switch (Direct).

{.

// Північ case North:

{.

B = Line[cX];

// Якщо елемент «чорний », повертаємо знову «наліво «if (B < 255).

{.

ToLine = (Byte*)ToImage->ScanLine[cY];

ToLine[cX] = 0;

Direct = West; cX—;

}.

// Інакше повертаємо «направо «else.

{.

Direct = East; cX++;

}.

} break;

// Схід case East:

{.

B = Line[cX];

// Якщо елемент «чорний », повертаємо знову «наліво «if (B < 255).

{.

ToLine = (Byte*)ToImage->ScanLine[cY];

ToLine[cX] = 0;

Direct = North; cY—;

Line = (Byte*)FromImage->ScanLine[cY];

}.

// Інакше повертаємо «направо «else.

{.

Direct = South; cY++;

Line = (Byte*)FromImage->ScanLine[cY];

}.

} break;

// Південь case South:

{.

B = Line[cX];

// Якщо елемент «чорний », повертаємо знову «наліво «if (B < 255).

{.

ToLine = (Byte*)ToImage->ScanLine[cY];

ToLine[cX] = 0;

Direct = East; cX++;

}.

// Інакше повертаємо «направо «else.

{.

Direct = West; cX—;

}.

} break;

// Захід case West:

{.

B = Line[cX];

// Якщо елемент «чорний », повертаємо знову «наліво «if (B < 255).

{.

ToLine = (Byte*)ToImage->ScanLine[cY];

ToLine[cX] = 0;

Direct = South; cY++;

Line = (Byte*)FromImage->ScanLine[cY];

}.

// Інакше повертаємо «направо «else.

{.

Direct = North; cY—;

Line = (Byte*)FromImage->ScanLine[cY];

}.

}.

}.

}.

}.

// ——————————————————————————————————- ——-;

void AlgorithmScan (Graphics:TBitmap* FromImage,.

Graphics:TBitmap* ToImage).

{.

// Тип галузі (ліва чи права) 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 < FromImage->Height; Y++).

{.

Line.L1 = (Byte*)FromImage->ScanLine[Y];

Y++;

Line.L2 = (Byte*)FromImage->ScanLine[Y];

// Пробуємо виявити ситуации:

// Шукаємо перший чорний елемент на другий лінії сканируемой смуги for (X = 0; X < FromImage->Width; X++).

{ if (Line.L2[X] < 255).

{.

// Якщо чорний елемент знайдено, намагаємося уточнити ситуацию.

CurrentSituation = sBegin; for (cX = X; cX < FromImage->Width; cX++).

{.

}.

}.

}.

}.

}.