Оглавление
1. OpenCV шаг за шагом. Введение.
2. Установка.
3. Hello World.
4. Загрузка картинки.
…
29. Интегральное изображение
30. Трансформация изображения — аффинные преобразования, гомография
31. Типы данных OpenCV — хранилище памяти, последовательность
32. Нахождение контуров и операции с ними

Контурный анализ — это один из важных и очень полезных методов описания, хранения, распознавания, сравнения и поиска графических образов/объектов.

Контур — это внешние очертания (обвод) предмета/объекта.

При проведении контурного анализа:
* полагается, что контур содержит достаточную информацию о форме объекта;
* внутренние точки объекта во внимание не принимаются.

Вышеприведённые положения, разумеется, накладывают существенные ограничения на область применения контурного анализа, которые, в основном, связаны с проблемами выделения контура на изображениях:
* из-за одинаковой яркости с фоном объект может не иметь чёткой границы, или может быть зашумлён помехами, что приводит к невозможности выделения контура;
* перекрытие объектов или их группировка приводит к тому, что контур выделяется неправильно и не соответствует границе объекта.

Однако, переход к рассмотрению только контуров объектов позволяет уйти от пространства изображения – к пространству контуров, что существенно снижает сложность алгоритмов и вычислений.

Т.о., контурный анализ имеет довольно слабую устойчивость к помехам, и любое пересечение или лишь частичная видимость объекта приводит либо к невозможности детектирования, либо к ложным срабатываниям, но простота и быстродействие контурного анализа, позволяют вполне успешно применять данный подход (при чётко выраженном объекте на контрастном фоне и отсутствии помех).

Итак, мы определились, что контур — это некая граница объекта, которая отделяет его от фона (других объектов). Вспомним, как мы можем получить контуры?

Разумеется, первым вспоминается детектор границ Кенни, а затем можно привести любые другие методы получения двоичного изображения:
пороговое преобразование,
выделение объекта по цвету

Во всех этих случаях мы получаем бинарное изображение, которое явным образом задаёт нам границы объекта. Вот эта совокупность пикселей, составляющих границу объекта и есть контур объекта.

Чтобы оперировать полученным контуром, его необходимо как-то представить (закодировать).
Например, указывать вершины отрезков, составляющих контур.
Другой известный способ кодирования контура – это цепной код Фримена.

Цепной код Фримена (Фридмана) (Freeman Chain Code)

Цепные коды применяются для представления границы в виде последовательности отрезков прямых линий определённой длины и направления. В основе этого представления лежит 4- или 8- связная решётка. Длина каждого отрезка определяется разрешением решётки, а направления задаются выбранным кодом.
(для представления всех направлений в 4-связной решётке достаточно 2-х бит, а для 8-связной решётки цепного кода требуется 3 бита)

Библиотека OpenCV реализует удобные методы для детектирования и манипуляции с контурами изображения.

Для поиска контуров используется функция cvFindContours():

CVAPI(int)  cvFindContours( CvArr* image, CvMemStorage* storage, CvSeq** first_contour,
                            int header_size CV_DEFAULT(sizeof(CvContour)),
                            int mode CV_DEFAULT(CV_RETR_LIST),
                            int method CV_DEFAULT(CV_CHAIN_APPROX_SIMPLE),
                            CvPoint offset CV_DEFAULT(cvPoint(0,0)));

— нахождение контуров на двоичном изображении

image — исходное 8-битное одноканальное изображение (ненулевые пиксели обрабатываются как 1, а нулевые — 0)
Для получения такого изображения из градаций серого можно, например, использовать функции cvThreshold() или cvCanny()
storage — хранилище памяти для хранения данных найденных контуров
first_contour — указатель, который будет указывать на первый элемент последовательности, содержащей данные найденных контуров
header_size — размер заголовка элемента последовательности
mode — режим поиска:

#define CV_RETR_EXTERNAL 0 // найти только крайние внешние контуры
#define CV_RETR_LIST     1 // найти все контуры и разместить их списком
#define CV_RETR_CCOMP    2 // найти все контуры и разместить их в виде 2-уровневой иерархии
#define CV_RETR_TREE     3 // найти все контуры и разместить их в иерархии вложенных контуров

method — метод аппроксимации:

#define CV_CHAIN_CODE               0 // цепной код Фридмана
#define CV_CHAIN_APPROX_NONE        1 // все точки цепного кода переводятся в точки
#define CV_CHAIN_APPROX_SIMPLE      2 // сжимает горизонтальные, вертикальные и диагональные сегменты и оставляет только их конечные точки
#define CV_CHAIN_APPROX_TC89_L1     3 // применяется алгоритм
#define CV_CHAIN_APPROX_TC89_KCOS   4 // аппроксимации Teh-Chin
#define CV_LINK_RUNS                5 // алгоритм только для CV_RETR_LIST

offset — смещение, на которое сдвигать точки контура (полезно, если контуры извлекаются из ROI и затем должны анализироваться в контексте целого изображения)

обратите внимание, что функция cvFindContours() может находить внешние и вложенные контуры и определять их иерархию вложения.

а отобразить найденные контуры можно с помощью функции cvDrawContours():

CVAPI(void)  cvDrawContours( CvArr *img, CvSeq* contour,
                             CvScalar external_color, CvScalar hole_color,
                             int max_level, int thickness CV_DEFAULT(1),
                             int line_type CV_DEFAULT(8),
                             CvPoint offset CV_DEFAULT(cvPoint(0,0)));

— нарисовать заданные контуры

img — изображение на котором будут нарисованы контуры
contour — указатель на первый контур
external_color — цвет внешних контуров
hole_color — цвет внутренних контуров(отверстие)
max_level — максимальный уровень для отображения контуров (0 — только данный контур, 1 — данный и все следующие на данном уровне, 2 — все следующие контуры и все контуры на следующем уровне и т.д. ) Если величина отрицательная, то будут нарисованы контуры на предыдущем уровне перед contour.
thickness — толщина линии для отображения контуров (если величина отрицательная, то область, ограниченная контуром заливается выбранным цветом )
line_type — тип линии

//
// пример нахождения контуров с помощью функции cvFindContours()
//
// https://robocraft.ru
//

#include <cv.h>
#include <highgui.h>
#include <stdlib.h>
#include <stdio.h>

IplImage* image = 0;
IplImage* gray = 0;
IplImage* bin = 0;
IplImage* dst = 0;

int main(int argc, char* argv[])
{
	// имя картинки задаётся первым параметром
	char* filename = argc >= 2 ? argv[1] : "Image0.jpg";
	// получаем картинку
	image = cvLoadImage(filename,1);

	printf("[i] image: %s\n", filename);
	assert( image != 0 );

	// создаём одноканальные картинки
	gray = cvCreateImage( cvGetSize(image), IPL_DEPTH_8U, 1 );
	bin = cvCreateImage( cvGetSize(image), IPL_DEPTH_8U, 1 );
	// клонируем
	dst = cvCloneImage(image);
	// окно для отображения картинки
	cvNamedWindow("original",CV_WINDOW_AUTOSIZE);
	cvNamedWindow("binary",CV_WINDOW_AUTOSIZE);
	cvNamedWindow("contours",CV_WINDOW_AUTOSIZE);

	// преобразуем в градации серого
	cvCvtColor(image, gray, CV_RGB2GRAY);

	// преобразуем в двоичное
	cvInRangeS(gray, cvScalar(40), cvScalar(150), bin); // atoi(argv[2])

	CvMemStorage* storage = cvCreateMemStorage(0);
	CvSeq* contours=0;

	// находим контуры
	int contoursCont = cvFindContours( bin, storage,&contours,sizeof(CvContour),CV_RETR_LIST,CV_CHAIN_APPROX_SIMPLE,cvPoint(0,0));

	// нарисуем контуры
	for(CvSeq* seq0 = contours;seq0!=0;seq0 = seq0->h_next){
		cvDrawContours(dst, seq0, CV_RGB(255,216,0), CV_RGB(0,0,250), 0, 1, 8); // рисуем контур
	}

	// показываем картинки
	cvShowImage("original",image);
	cvShowImage("binary", bin);
	cvShowImage("contours", dst);

	// ждём нажатия клавиши
	cvWaitKey(0);

	// освобождаем ресурсы
	cvReleaseImage(&image);
	cvReleaseImage(&gray);
	cvReleaseImage(&bin);
	cvReleaseImage(&dst);
	// удаляем окна
	cvDestroyAllWindows();
	return 0;
}

скачать иcходник (32-cvFindContours.cpp)

Если задать параметром функции метод CV_CHAIN_CODE, то cvFindContours() вернёт цепной код Фримана, работать с которым можно через методы:

CVAPI(void) cvStartReadChainPoints( CvChain* chain, CvChainPtReader* reader );

— инициализация считывателя точек

CVAPI(CvPoint) cvReadChainPoint( CvChainPtReader* reader );

— считывает следующую точку цепного кода

Обычная последовательность действий при распознавании объектов методом контурного анализа:
1. предварительная обработка изображения (сглаживание, фильтрация помех, увеличение контраста);
2. бинаризация изображения;
3. выделение контуров объектов;
4. первичная фильтрация контуров (по периметру, площади и т.п.);
5. эквализация контуров (приведение к единой длине, сглаживание) — позволяет добиться инвариантности к масштабу;
6. перебор всех найденных контуров и поиск шаблона, максимально похожего на данный контур (или же сортировка контуров по каком-либо признаку, например, площади).

Свойства контуров

OpenCV предоставляет функции для определения таких полезных свойств найденных контуров, как площадь и длина(периметр).

CVAPI(double)  cvContourArea( const CvArr* contour,
                              CvSlice slice CV_DEFAULT(CV_WHOLE_SEQ));

— возвращает площадь контура
contour — контур (последовательность или массив вершин)
slice — начальная и конечные точки контура (по-умолчанию весь контур)

ориентация контура влияет на знак, т.о. функция может вернуть отрицательную величину.
Можно использовать fabs() чтобы получить абсолютное значение площади.

CVAPI(double)  cvArcLength( const void* curve,
                            CvSlice slice CV_DEFAULT(CV_WHOLE_SEQ),
                            int is_closed CV_DEFAULT(-1));
#define cvContourPerimeter( contour ) cvArcLength( contour, CV_WHOLE_SEQ, 1 )

— возвращает периметр контура или длину кривой (части контура)
curve — последовательность или массив точек кривой (контур)
slice — начальная и конечные точки контура (по-умолчанию весь контур)
is_closed — определяет закрыта кривая или нет:
is_closed = 0 — кривая полагается открытой
is_closed > 0 — кривая полагается закрытой
is_closed < 0 — если кривая — последовательность, флаг CV_SEQ_FLAG_CLOSED из ((CvSeq*)curve)->flags проверяется для определения закрыта кривая или нет, в противном случае (кривая представлена массивом (CvMat*) точек) она полагается открытой.

функция считает длину кривой, как сумму длин сегментов между последовательностью точек.

Простой пример использования этих функций — последующее нахождение отношения этих двух величин (т.н. компактность).
Например, как мы все помним ещё со школы, площадь круга равна пи эр квадрат (PI*R^2), а длина окружности при этом равна два пи эр (2*PI*R).
Чтобы получить значение инвариантное относительно радиуса разделим площадь круга на квадрат длины окружности:

PI*R^2 / (2*PI*R)*(2*PI*R) = 1/4*PI ~ 0.079577

Отлично! Теперь используя значение отношения площади контура к квадрату длины контура и сравнивая его с заданным значением 1/4*PI можно находить окружности!

Фактически — площадь — это количество пикселей области, а периметр — количество пикселей на границе области.
Отношение квадрата периметра к площади называется компактность.
Наиболее компактная фигура — это круг: 4*PI

//
// поиск кругов на изображении
// по отношению площади контура к квадрату его длины
//
//
// https://robocraft.ru
//

#include <cv.h>
#include <highgui.h>
#include <stdlib.h>
#include <stdio.h>

//  находит и показывает круги на изображении
void findCircles(IplImage* _image)
{
	assert(_image!=0);

	IplImage* bin = cvCreateImage( cvGetSize(_image), IPL_DEPTH_8U, 1);

	// конвертируем в градации серого
	cvConvertImage(_image, bin, CV_BGR2GRAY);
	// находим границы
	cvCanny(bin, bin, 50, 200);

	cvNamedWindow( "bin", 1 );
	cvShowImage("bin", bin);

	// хранилище памяти для контуров
	CvMemStorage* storage = cvCreateMemStorage(0);
	CvSeq* contours=0;

	// находим контуры
	int contoursCont = cvFindContours( bin, storage,&contours,sizeof(CvContour),CV_RETR_LIST,CV_CHAIN_APPROX_SIMPLE,cvPoint(0,0));

	assert(contours!=0);

	// обходим все контуры
	for( CvSeq* current = contours; current != NULL; current = current->h_next ){
		// вычисляем площадь и периметр контура
		double area = fabs(cvContourArea(current));
		double perim = cvContourPerimeter(current);

		// 1/4*CV_PI = 0,079577
		if ( area / (perim * perim) > 0.07 && area / (perim * perim)< 0.087 ){ // в 10% интервале
			// нарисуем контур
			cvDrawContours(_image, current, cvScalar(0, 0, 255), cvScalar(0, 255, 0), -1, 1, 8);
		}
	}

	// освобождаем ресурсы
	cvReleaseMemStorage(&storage);
	cvReleaseImage(&bin);
}

int main(int argc, char* argv[])
{
	IplImage *src=0, *dst=0;

	// имя картинки задаётся первым параметром
	char* filename = argc >= 2 ? argv[1] : "Image0.jpg";
	// получаем картинку
	src = cvLoadImage(filename, 1);

	printf("[i] image: %s\n", filename);
	assert( src != 0 );

	// покажем изображение
	cvNamedWindow( "original", 1 );
	cvShowImage( "original", src );

	dst = cvCloneImage(src);

	// находим круги на изображении
	findCircles(dst);

	cvNamedWindow( "circles", 1 );
	cvShowImage( "circles", dst);

	// ждём нажатия клавиши
	cvWaitKey(0);

	// освобождаем ресурсы
	cvReleaseImage(&src);
	cvReleaseImage(&dst);
	// удаляем окна
	cvDestroyAllWindows();
	return 0;
}

скачать иcходник (32-cvFindContours_findCircles.cpp)

Чтобы снизить ложные срабатывания можно ввести нижнее/верхнее ограничения на площадь круга.

Дополнительные полезные функции:

CVAPI(CvRect)  cvBoundingRect( CvArr* points, int update CV_DEFAULT(0) );

— возвращает прямоугольник, которым можно обвести контур
points — набор 2D-точек — последовательность или вектор (CvMat) точек
update — флаг обновления:
0 (CvContour) — прямоугольник не рассчитывается, а берётся из поля rect заголовка контура
1 (CvContour) — прямоугольник рассчитывается и записывается в поле rect заголовка контура
0 (CvSeq или CvMat) — прямоугольник рассчитывается и возвращается
1 (CvSeq или CvMat) — ! ошибка выполнения !

функция возвращает прямоугольник, у которого стороны строго вертикальны и горизонтальны (параллельны сторонам(системе координат) изображения).

CVAPI(CvBox2D)  cvMinAreaRect2( const CvArr* points,
                                CvMemStorage* storage CV_DEFAULT(NULL));

— возвращает минимально возможный прямоугольник, которым можно обвести контур
points — последовательность или массив точек
storage — опционально — временное хранилище памяти

отличие функции cvMinAreaRect2 от cvBoundingRect в типе возвращаемой структуры. cvMinAreaRect2 возвращает CvBox2D, которая описывает прямоугольник, который может быть повёрнут относительно системы координат изображения на угол angle.

typedef struct CvBox2D
{
    CvPoint2D32f center;  /* Center of the box.                          */
    CvSize2D32f  size;    /* Box width and length.                       */
    float angle;          /* Angle between the horizontal axis           */
                          /* and the first side (i.e. length) in degrees */
}
CvBox2D;

CVAPI(int)  cvMinEnclosingCircle( const CvArr* points,
                                  CvPoint2D32f* center, float* radius );

— находит окружность минимальной площади, которая содержит данный набор 2D-точек.
points — последовательность или ассив 2D-точек
center — возвращаемое значение — центр окружности
radius — возвращаемое значение — радиус окружности

пример, демонстрирующий работу cvMinEnclosingCircle()
указатель изображения передаётся функции EnclosingCircle(), которая переводит изображение в градации серого, затем использует детектор Кенни для нахождения границ. cvFindContours() находит все контуры границ, и затем для всех контуров по-очереди применяется функция cvMinEnclosingCircle(). Найденные параметры окружности передаются функции cvCircle() для отображения окружности на рисунке.

//
// демонстрация cvMinEnclosingCircle()
//
//
// https://robocraft.ru
//

#include <cv.h>
#include <highgui.h>
#include <stdlib.h>
#include <stdio.h>

void EnclosingCircle(IplImage* _image)
{
	assert(_image!=0);

	IplImage* bin = cvCreateImage( cvGetSize(_image), IPL_DEPTH_8U, 1);

	// конвертируем в градации серого
	cvConvertImage(_image, bin, CV_BGR2GRAY);
	// находим границы
	cvCanny(bin, bin, 50, 200);

	cvNamedWindow( "bin", 1 );
	cvShowImage("bin", bin);

	// хранилище памяти для контуров
	CvMemStorage* storage = cvCreateMemStorage(0);
	CvSeq* contours=0;

	// находим контуры
	int contoursCont = cvFindContours( bin, storage,&contours,sizeof(CvContour),CV_RETR_LIST,CV_CHAIN_APPROX_SIMPLE,cvPoint(0,0));

	assert(contours!=0);

	// обходим все контуры
	for( CvSeq* current = contours; current != NULL; current = current->h_next ){
		CvPoint2D32f center;
		float radius=0;
		// находим параметры окружности
		cvMinEnclosingCircle(current, & center, &radius);
		// рисуем
		cvCircle(_image, cvPointFrom32f(center), radius, CV_RGB(255, 0, 0), 1, 8);
	}

	// освобождаем ресурсы
	cvReleaseMemStorage(&storage);
	cvReleaseImage(&bin);
}

int main(int argc, char* argv[])
{
	IplImage *src=0, *dst=0;

	// имя картинки задаётся первым параметром
	char* filename = argc >= 2 ? argv[1] : "Image0.jpg";
	// получаем картинку
	src = cvLoadImage(filename, 1);

	printf("[i] image: %s\n", filename);
	assert( src != 0 );

	// покажем изображение
	cvNamedWindow( "original", 1 );
	cvShowImage( "original", src );

	dst = cvCloneImage(src);

	// показываем
	EnclosingCircle(dst);

	cvNamedWindow( "circles", 1 );
	cvShowImage( "circles", dst);

	// ждём нажатия клавиши
	cvWaitKey(0);

	// освобождаем ресурсы
	cvReleaseImage(&src);
	cvReleaseImage(&dst);
	// удаляем окна
	cvDestroyAllWindows();
	return 0;
}

скачать иcходник (32-cvMinEnclosingCircle.cpp)

использована функция для конвертации CvPoint2D32f в CvPoint:

CV_INLINE  CvPoint  cvPointFrom32f( CvPoint2D32f point )
{
    CvPoint ipt;
    ipt.x = cvRound(point.x);
    ipt.y = cvRound(point.y);

    return ipt;
}

CVAPI(CvSeq*)  cvApproxPoly( const void* src_seq,
                             int header_size, CvMemStorage* storage,
                             int method, double parameter,
                             int parameter2 CV_DEFAULT(0));

— аппроксимация контура(кривой) полигонами
src_seq — исходная последовательность или массив точек
header_size — размер заголовка кривой(контура)
storage — хранилище контуров. Если NULL, то используется хранилище входной последовательности
method — метод аппроксимации:

#define CV_POLY_APPROX_DP 0 // Douglas-Peucker algorithm

parameter — параметр метода аппроксимации, в случае CV_POLY_APPROX_DP — это желаемая точность
parameter2 — Если src_seq — последовательность, то параметр определяет должна ли аппроксимироваться только одна последовательность или все последовательности этого уровня и ниже. Если src_seq — массив CvMat* точек, то параметр определяет закрывается ли кривая (parameter2!=0) или нет (parameter2=0).

функция аппроксимирует одну или более кривых и возвращает результат аппроксимации. В случае нескольких кривых(контуров), результирующее дерево имеет ту же структуру, что и входящее.

	// находим контуры
	int contoursCont = cvFindContours( bin, storage, &contours, sizeof(CvContour), CV_RETR_LIST, CV_CHAIN_APPROX_SIMPLE, cvPoint(0,0));

	if(contours!=0){
		for(CvSeq* seq0 = contours;seq0!=0;seq0 = seq0->h_next){

			// аппроксимация контура полигонами
			CvSeq* result = cvApproxPoly( seq0, sizeof(CvContour), storage, CV_POLY_APPROX_DP, 0.1, 0 );
			printf("[d] %d %d\n", seq0->total, result->total);
		}
	}

CVAPI(CvSeq*) cvFindDominantPoints( CvSeq* contour, CvMemStorage* storage,
                                   int method CV_DEFAULT(CV_DOMINANT_IPAN),
                                   double parameter1 CV_DEFAULT(0),
                                   double parameter2 CV_DEFAULT(0),
                                   double parameter3 CV_DEFAULT(0),
                                   double parameter4 CV_DEFAULT(0));

— поиск ключевых точек контура (последовательности точек)

contour — исходная последовательность
storage — хранилище контуров.
method — метод:

#define CV_DOMINANT_IPAN 1 // алгоритм IPAN - Image and Pattern Analysis Group

parameter1 — минимальная дистанция
parameter2 — максимальная дистанция
parameter3 — дистанция сближения
parameter4 — максимальный угол отклонения (в градусах)

типичные значения 7, 9, 9, 150

далее: 33. Сравнение контуров через суммарные характеристики — моменты

Ссылки
http://en.wikipedia.org/wiki/Chain_code
Контурный анализ