Очень часто необходимо получить контуры объектов для их дальнейшего анализа. Ниже представлен простейший алгоритм.
1 этап. Получение монохромного изображения (blog.vidikon.com/?p=87).
2 этап. Выделение граничных точек. Граничные точки отличаются от внутренних точек изображения наличием в качестве соседней одной или нескольких фоновых точек. При этом в качестве соседних к рассмотрению берутся только горизонтальные и вертикальные пиксели, либо только диагональные [1, 2]. Пусть имеется структура, описывающая изображение:
struct IMG
{
byte* bytes; //массив данных
int Width; //ширина в пикселях
int Width_1; //ширина в байтах
int Height; //высота
bool on; //загружено изображение или нет
BYTE format;//0 – 24бит 1 – 8 бит чёрнобелое
};
Для выделения граничных точек на 24-битном изображении можно использовать следующую функцию, которая на входе получает уже разделённое на 2 цвета изображение:
void AllocationBorders(IMG img)
{
int i,j,k;
for(i=0;i<img.Height;i++){
for(j=0;j<img.Width;j++)
{
if (img.bytes[j*3+i*img.Width_1]==255) continue;
k=0;
if (i!=0)
if (img.bytes[j*3+(i-1)*img.Width_1]==255) k=1;
if (i!=img.Height-1)
if (img.bytes[j*3+(i+1)*img.Width_1]==255) k=1;
if (j!=0)
if (img.bytes[(j-1)*3+i*img.Width_1]==255) k=1;
if (j!=img.Width-1)
if (img.bytes[(j+1)*3+i*img.Width_1]==255) k=1;
if (k==1) {
img.bytes[j*3+i*img.Width_1]=128;
img.bytes[j*3+i*img.Width_1+1]=0;
img.bytes[j*3+i*img.Width_1+2]=0;
}
}
}
}
3 этап. Поиск контуров. Для выделения контуров необходимо резервировать память под каждый контур. В простейшем случае контур может описываться следующей структурой:
struct C_POINT
{
int x,y;
};
struct CONTOUR_STRUCT
{
WORD all_elem;//общее количество точек в одном контуре
C_POINT* Points;//Указатель на массив точек
RECT Zone;//зона контура
int mama;//родитель если -1, то никого нет
int level;//уровень вхождения
};
Вообще все операции лучше проводить с 8-битным изображением, чем с 24 – так в OpenCV в основном все операции проводятся именно с такими изображениями для увеличения скорости. Поэтому дальше будет идти речь о 8-битном изображении.
В цикле перебираются все граничные точки (в нашем случае точки с цветом 128):
if (Image.bytes[j+i*Image.Width_1]==128 )
И найденной точке присваивается другое цветовое значение, сама точка добавляется как первая точка в контуре и собственно контролируется зона максимального и минимального значения для координат X и Y, например так:
Image.bytes[j+i*Image.Width_1]=1;
Point[all_elem].x=j;
Point[all_elem].y=i;
all_elem++;
Zone.left=j;Zone.right=j;
Zone.top=i;Zone.bottom=i;
После этого для найденной точки вызывается рекурсивная функция, в нашем случае это функция FindBorderPoint, которой передаются координаты точки. Внутри функции FindBorderPoint(int x,int y) смотрятся все граничные точки, включая диагональные:
WORD k=0;//переменная отслеживает в какую точку потом надо зайти рекурсивной функции
int w=(rect.right-rect.left);
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
//Перебираем 8 точек, без 9 центральной
if ((i==1 && j==1) || (j==0 && x==rect.left) || (j==2 && x==rect.right)
|| (i==0 && y==rect.top) || (i==2 && y==rect.bottom)) continue;
k=k*2;
if (Image.bytes[x-1+j+(y-1+i)*Image.Width_1]==128)
{
Image.bytes[x-1+j+(y-1+i)*Image.Width_1]=1;
k++;
Point[all_elem].x=x-1+j;
Point[all_elem].y=y-1+i;
//Смотрим минимум-максимум точек
if (Point[all_elem].x<Zone.left) Zone.left=Point[all_elem].x;
if (Point[all_elem].x>Zone.right) Zone.right=Point[all_elem].x;
if (Point[all_elem].y<Zone.top) Zone.top=Point[all_elem].y;
if (Point[all_elem].y>Zone.bottom) Zone.bottom=Point[all_elem].y;
all_elem++;
}
}
Переменная k выступает в качестве мониторинга – с какими параметрами рекурсивно вызвать функцию. Операции внутри условия совпадения с граничной точкой направлены на добавление точки в контур и определения границы зоны контура. После окончания цикла функция вызывается рекурсивно для найденных новых точек контура:
for(i=2;i>=0;i–)
for(j=2;j>=0;j–)
{
if (i==1 && j==1) continue;
if (k%2==1) FindBorderPoint(x-1+j,y-1+i);
k=k/2;
}
После того, как контур найден, изображение продолжает сканироваться на наличие других контуров. А, когда все контура найдены – определяются их вложенность и родительский контур.
Описанный способ нахождения контуров обладает недостатком – точки в нём находятся не последовательно по направлению обхождения контура. Но в некоторых задачах такое описание контура является достаточным. Для того, чтобы получить контур из последовательных точек надо использовать несколько другой алгоритм, о котором мы возможно поговорим в следующий раз.
1. Введение в контурный анализ; приложения к обработке изображений и сигналов/ Я.А.Фурман, А.В.Кревецкий, А.К.Передреев, А.А.Роженцов, Р.Г.Хафизов, И.Л.Егошина, А.Н.Леухин; Под ред. Я.А.Фурмана. – 2-е изд., испр. – М.:ФИЗМАТЛИТ, 2003. – 592 с.
2. Розенфельд А. Распознавание и обработка изображений. – М.: Мир, 1972.