Білоруський Державний Університет Інформатики і радіоелектроніки.
Контрольна робота з дисципліни
«МАТИ»
Виконав студент групи 500501
Балахонов Е. В.
Алгоритми виділення контурів.
Алгоритми виділення контурів можна умовно розбити на дві групи:відстежують і скануючі.
1. Відстежують алгоритми на прикладі алгоритму «жука».
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. Головний модуль програми:
//------------------------------------- ---------------------------------< br>-----
# 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;
)
//------------------------------------------------ ----------------------< br>-----
Лістинг 3. Модуль головної форми
Файл заголовка:
//---------------------------- ------------------------------------------< br>-----
# ifndef MainUnitH
# define MainUnitH
//---------------- -------------------------------------------------- ----< br>-----
# include
# include
# include
# include
# include
# include
//-------------------------------- --------------------------------------< br>----- 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);
);
//-------- -------------------------------------------------- ------------< br>----- Extern PACKAGE TForm1 * Form1;
//------------------------------ ----------------------------------------< br>-----
# endif
cpp файл:
//----------------- -------------------------------------------------- ---
-----
# include
# pragma hdrstop
# include "MainUnit.h"
# include "GraphicUnit. h "
//--------------------------------------- -------------------------------< br>-----
# pragma package (smart_init)
# pragma resource "*. dfm"
TForm1 * Form1;
//----------------------------------------------- -----------------------< br>-----
__fastcall TForm1:: TForm1 (TComponent * Owner)
: TForm (Owner)
(
)
//----------------------------------------- -----------------------------< br>----- Void __fastcall TForm1:: Button1Click (TObject * Sender)
(
AlgorithmBeatle (FromImage-> Picture-> Bitmap,
ToImage - > Picture-> Bitmap);
ToImage-> Visible = false;
ToImage-> Visible = true;
)
//------------------------------------------------ ----------------------< br>-----
Лістинг 4. Модуль виділення контурів.
Файл заголовка:
//--------------------------- -------------------------------------------< br>-----
# ifndef GraphicUnitH
# define GraphicUnitH
//---------------- -------------------------------------------------- ----< br>-----
# include
extern void AlgorithmBeatle (Graphics:: TBitmap * FromImage,
Graphics:: TBitmap * ToImage); extern void AlgorithmScan (Graphics:: TBitmap * FromImage,
Graphics:: TBitmap * ToImage);
# endif
cpp файл:
//------------------------------------------------- ---------------------< br>-----
# include
# pragma hdrstop
# include "GraphicUnit.h"
//--- -------------------------------------------------- -----------------< br>-----
# 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 Height; Y ++) (
Line = (Byte *) FromImage-> ScanLine [Y ]; for (X = 0; X 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; < p> 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];
)
)
)
)
)
// ------------------------ ---------------------------------------------< br>------
void AlgorithmScan (Graphics:: TBitmap * FromImage,
Graphics:: TBitmap * ToImage)
( < p>// Тип гілки (ліва або права) 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;// Нижня лінія < p>);
int Y;// Поточна координата Y int X;// Поточна координата X int cX;// Тимчасова координата X для сканування
TLine Line;// сканується смуга
TSituation CurrentSituation;// Поточна ситуація
for (Y = 0; Y Height; Y ++) ( < p> Line.L1 = (Byte *) FromImage-> ScanLine [Y];
Y ++;
Line.L2 = (Byte *) FromImage-> ScanLine [Y];
// Пробуємо виявити ситуації:
// Шукаємо перший чорний елемент у другій лінії сканується смуги for (X = 0; X Width; X ++) (if (Line.L2 [X] <255)
(
// Якщо чорний елемент знайдений, намагаємося уточнити ситуацію
CurrentSituation = sBegin ; for (cX = X; cX Width; cX ++) (
)
)
)
)
)
