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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

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


Контрольна робота

з дисципліни

«МАТИ»


Виконав студент групи 500501

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


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


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


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

Загальний опис алгоритму.


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

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

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


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


Дана програма реалізована в середовищі програмування Borland C + + Builder 4.

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



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


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


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


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


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


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



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


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


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


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

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

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

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

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

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

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



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


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

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

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

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

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

"Поглиненої" пари звільняються.

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


Рис. 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 + +)

{


}


}

}


}


}

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
23.7кб. | скачати


Схожі роботи:
Моделі теорії графів для виділення контурів по градиентному зображенню
Теодолитная зйомка контурів місцевості
Амплітудно частотні характеристики та налаштування пов`язаних контурів
Дослідження характеристик одиночних і пов`язаних коливальних контурів
Амплітудно-частотні характеристики та налаштування пов`язаних контурів
Виділення 2
Органи виділення
Фізіологія виділення
Генетичні алгоритми
© Усі права захищені
написати до нас