|
Реферат: Алгоритмы выделения контуров (Программирование)
Белорусский Государственный Университет Информатики и Радиоэлектроники.
Контрольная работа
по дисциплине
«МАТИ»
Выполнил студент группы 500501
Балахонов Е. В.
Алгоритмы выделения контуров.
Алгоритмы выделения контуров можно условно разбить на две группы:
отслеживающие и сканирующие.
1. Отслеживающие алгоритмы на примере алгоритма «жука».
1 Общее описание алгоритма.
Отслеживающие алгоритмы основаны на том, что на изображении
отыскивается объект (первая встретившаяся точка объекта) и контур объекта
отслеживается и векторизуется. Достоинством данных алгоритмов является их
простота, к недостаткам можно отнести их последовательную реализацию и
некоторую сложность при поиске и обработке внутренних контуров. Пример
отслеживающего алгоритма - "алгоритма жука" - приведен на рис. 5.12. Жук
начинает движение с белой области по направлению к черной, Как только он
попадает на черный элемент, он поворачивает налево и переходит к следующему
элементу. Если этот элемент белый, то жук поворачивается направо, иначе -
налево. Процедура повторяется до тех пор, пока жук не вернется в исходную
точку. Координаты точек перехода с черного на белое и с белого на черное и
описывают границу объекта.
На рис. 1 показана схема работы такого алгоритма.
[pic]
Рис. 1. Схема работы отслеживающего алгоритма «жука».
1.2 Создание программы, реализующий данный алгоритм.
Данная программа реализована в среде программирования Borland C++
Builder 4.
Общий вид главного окна программы в исходном положении показан на
рис. 2.
[pic]
Рис. 2. Главное окно программы в исходном положении.
Слева находится исходное изображение, справа находится изображение на
котором будут рисоваться выделяемые контуры объекта.
Исходные тексты формы представлены в листинге 1.
В листингах 2 и 3 находятся исходные тексты главного модуля программы
и модуля главной формы.
В листинге 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++)
{
}
}
}
}
}
Реферат на тему: Алгоритмы сортировки
Алгоритмы сортировки
Проблема упорядочивания данных с практической точки зрения:
достоинства и недостатки пяти различных методов сортировки.
Сортировка применяется во всех без исключения областях программирования,
будь то базы данных или математические программы.
Практически каждый алгоритм сортировки можно разбить на три части:
- сравнение, определяющее упорядоченность пары элементов;
- перестановку, меняющую местами пару элементов;
- собственно сортирующий алгоритм, который осуществляет сравнение и
перестановку элементов до тех пор, сока все элементы множества не будут
упорядочены.
Подобными свойствами обладают и те пять алгоритмов сортировки, которые
рассмотрены ниже. Они отобраны из множества алгоритмов, потому что,
во-первых, наиболее часто используются, а во-вторых, потому что большинство
остальных алгоритмов является различными модификациями описанных здесь.
Метод пузырька.
( метод назван также обменной сортировкой с выбором) .
Идея этого метода отражена в его названии. Самые легкие элементы массива
"всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно
реализовать следующим образом. Мы будем просматривать весь массив "снизу
вверх" и менять стоящие рядом элементы в там случае, если "нижний" элемент
меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий”
элемент всего массива. Теперь повторим всю оперно для оставшихся
неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже"
первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он
является непревзойденным в своей неэффективности. Немного более
эффективным, но таким наглядным является второй метод.
Сортировка выбором
На этот раз при просмотре мaccива мы будем искать наименьший элемент,
Сравнивая его с первым. Если такой элемент найден, поменяем его местами с
первым. Затем повторим эту операцию, но начнем не с первого элемента, а со
второго. И будем продолжать подобным образом, пока не рассортируем весь
массив.
Метод Шелла
Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея
этого алгоритма заключается в том, чтобы в начале ycтpанить массовый
беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как
видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается
до единицы. Это означает, что на поздних стадиях сортировка сводится просто
к перестановкам соседних элементов (если, конечно, такие перестановки
являются необходимыми).
Метод Хoopа
Этот метод, называемый также быстрой сортировкой(QuickSort), был
Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).
Суть метода заключается в том, чтобы найти такой элемент множества,
подлежащего сортировке, который разобьет его на два подмножества: те
элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею
можно реализовать многими способами.
| |
