Оглавление
1. OpenCV шаг за шагом. Введение.
2. Установка.
3. Hello World.
4. Загрузка картинки.
...
26. Операторы Собеля и Лапласа
27. Детектор границ Кенни (Canny)
28. Преобразование Хафа

На прошлом шаге мы узнали о функции, реализующей детектор границ Кенни. Если вы немного поэкспериментировали с представленным примером, то обратили внимание, что cvCanny() помогает замечательно выделять границы предметов и окружающей обстановки. В нашем рукотворном мире городов и квартир преобладают прямые линии и другие простые геометрические формы (квадрат, прямоугольник, треугольник, круг).
Поэтому, одной из задач зрения робота может быть детектирование этих линий (для поиска каких-либо геометрических форм, например, дверного проёма, круглой розетки и т.п.)
Эта задача весьма неплохо решается с помощью т.н. преобразования Хафа.

Преобразование Хафа (Hough Transform) — это метод для поиска линий, кругов и других простых форм на изображении.

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

Преобразование Хафа основывается на представлении искомого объекта в виде параметрического уравнения. Параметры этого уравнения представляют фазовое пространство (т.н. аккумуляторный массив/пространство, пространство Хафа).
Затем, берётся двоичное изображение (например, результат работы детектора границ Кенни). Перебираются все точки границ и делается предположение, что точка принадлежит линии искомого объекта — т.о. для каждой точки изображения рассчитывается нужное уравнение и получаются необходимые параметры, которые сохраняются в пространстве Хафа.
Финальным шагом является обход пространства Хафа и выбор максимальных значений, за которые «проголосовало» больше всего пикселей картинки, что и даёт нам параметры для уравнений искомого объекта.
Запутано? Попробуем разобраться на примерах :)

Самым распространённым и простым случаем преобразования Хафа является поиск линий

Преобразовании Хафа для поиска линий (Hough Line Transform)

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

формула линии:

y = a*x+b 		// в декартовых координатак
p = x*cos(f)+y*sin(f) 	// в полярных координатах

Прямую на плоскости можно представить:

x*cos(f) + y*sin(f) = R

, где
R – длина перпендикуляра опущенного на прямую из начала координат,
f — угол между перпендикуляром к прямой и осью OX.
f находится в пределах от 0 до 2*PI,
R ограничено размерами входного изображения.

Через каждую точку (x, y) изображения можно провести несколько прямых с разными R и f, то есть каждой точке (x, y) изображения соответствует набор точек в фазовом пространстве (R, f), образующий синусоиду.

Так же каждой точке (R0, f0) пространства (R, f) можно поставить в соответствие счетчик, соответствующий количеству точек (x, y), лежащих на прямой

x*cos(f0) + y sin(f0) = R0

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

Можно попробовать реализовать преобразование Хафа самостоятельно, например что-то вроде этого:

//
// Hough transform - преобразование Хафа
// - нахождение линий
//
// долгий и нудный перебор, поэтому лучше тестировать
// на маленьких картинках :)
//
// http://robocraft.ru
//

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

//
// преобразование Хафа для нахождения линий
//
// код на Паскале: http://forum.graphicon.ru/viewtopic.php?p=20222#p20222
//
void houghLine(IplImage* original, float accuracy=0.1)
{
	assert(original!=0);

	IplImage *src=0, *rgb=0;
	IplImage *bin=0;
	IplImage *phase=0;

	src=cvCloneImage(original);

	// заведём цветную картинку
	rgb = cvCreateImage(cvGetSize(src), 8, 3);
	cvConvertImage(src, rgb, CV_GRAY2BGR);

	// бинарная картинка - для контуров
	bin = cvCreateImage(cvGetSize(src), IPL_DEPTH_8U, 1);
	cvCanny(src, bin, 50, 200);

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

	// максимальное расстояние от начала координат - это длина диагонали
	int RMax = cvRound( sqrt( (double)(src->width*src->width + src->height*src->height) ) );

	// картинка для хранения фазового пространства Хафа (r, f)
	// 0 < r < RMax
	// 0 < f < 2*PI
	phase = cvCreateImage(cvSize(RMax, 180), IPL_DEPTH_16U, 1);
	cvZero(phase);

	int x=0, y=0, r=0, f=0;
	float theta=0;

	// пробегаемся по пикселям изображения контуров
	for(y=0; y<bin->height; y++){
		uchar* ptr = (uchar*) (bin->imageData + y * bin->widthStep);
		for(x=0; x<bin->width; x++){
			if(ptr[x]>0){ // это пиксель контура?
				// рассмотрим все возможные прямые, которые могут 
				// проходить через эту точку
				for(f=0; f<180; f++){ //перебираем все возможные углы наклона
					short* ptrP = (short*) (phase->imageData + f * phase->widthStep);
					for(r=0; r<RMax; r++){ // перебираем все возможные расстояния от начала координат
						theta=f*CV_PI/180.0; // переводим градусы в радианы

						// Если решение уравнения достаточно хорошее (точность больше заданой)
						if ( abs(( (y)*sin(theta) + (x)*cos(theta)) - r) < accuracy ){
							ptrP[r]++; // увеличиваем счетчик для этой точки фазового пространства.
						}
					}
				}
			}
		}
	}

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

	// увеличим фазовую картинку
	IplImage* phaseImage = cvCreateImage( cvSize(phase->width*3, phase->height*3), IPL_DEPTH_16U, 1);
	cvResize(phase, phaseImage);

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

	// Выбираем точку фазового пространства которая набрала наибольшее число попаданий
	unsigned int MaxPhaseValue = 0;
	float Theta=0;
	int R=0;
	for(f=0; f<180; f++){ //перебираем все возможные углы наклона
		short* ptrP = (short*) (phase->imageData + f * phase->widthStep);
		for(r=0; r<RMax; r++){ // перебираем все возможные расстояния от начала координат
			if(ptrP[r]>MaxPhaseValue){
				MaxPhaseValue = ptrP[r];
				Theta = f;
				R = r;
			}
		}
	}

#if 1
	printf("[M] %d\n", MaxPhaseValue);

	// нормировка
	float scaler = 0xFFFFFFFF/(float)MaxPhaseValue;
	for(y=0; y<phaseImage->height; y++){
		short* ptr = (short*) (phaseImage->imageData + y * phaseImage->widthStep);
		for(x=0; x<phaseImage->width; x++){
			ptr[x]*=scaler;
		}
	}
	cvNamedWindow( "phaseImage2", 1 );
	cvShowImage( "phaseImage2", phaseImage);
#endif

	// Рисуем линию по точкам для  R, Teta которые получили в результате преобразования
	Theta=Theta*CV_PI/180.0;
	for(y=0; y<rgb->height; y++){
		uchar* ptr = (uchar*) (rgb->imageData + y * rgb->widthStep);
		for(x=0; x<rgb->width; x++){
			if ( cvRound(((y) * sin(Theta) + (x) * cos(Theta))) == R){
				ptr[3*x]=0;
				ptr[3*x+1]=0;
				ptr[3*x+2]=255; 
			}
		}
	}

	cvNamedWindow( "line", 1 );
	cvShowImage( "line", rgb );

	// освобождаем ресурсы
	cvReleaseImage(&src);
	cvReleaseImage(&rgb);

	cvReleaseImage(&bin);
	cvReleaseImage(&phase);
	cvReleaseImage(&phaseImage);
}

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

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

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

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

	houghLine(original);

	cvWaitKey(0);

	cvReleaseImage(&original);

	// удаляем окна
	cvDestroyAllWindows();
	return 0;
}

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


— получается оооочень долго :)

Но, в OpenCV уже есть функция, реализующая преобразование Хафа для поиска линий

CVAPI(CvSeq*)  cvHoughLines2( CvArr* image, void* line_storage, int method,
                              double rho, double theta, int threshold,
                              double param1 CV_DEFAULT(0), double param2 CV_DEFAULT(0));

— нахождение линий на двоичном изображении, используя преобразование Хафа

image — 8-битное двоичное изображение (в случае вероятностного метода изображение будет модифицироваться)
line_storage — хранилище памяти для сохранения найденных линий (можно использовать матрицу 1xЧисло_линий CvMat)
method — метод:

#define CV_HOUGH_STANDARD 0
#define CV_HOUGH_PROBABILISTIC 1
#define CV_HOUGH_MULTI_SCALE 2

CV_HOUGH_STANDARD — классический вариант трансформации Хафа. Каждая линия представляется двумя числами типа float (rho, theta), где rho — дистанция между точкой (0,0) и линией, а theta — угол между осью x и нормалью к линии (т.е. матрица должна иметь тип of CV_32FC2)
CV_HOUGH_PROBABILISTIC — вероятностный метод трансформации Хафа (более эффективен с случае изображений с несколькими длинными линейными сегментами). Возвращает сегменты линии, которые представляются точками начала и конца (т.е. матрица должна иметь тип of CV_32SC4)
CV_HOUGH_MULTI_SCALE — масштабный вариант классической трансформации Хафа. Линии представлены так же, как и в CV_HOUGH_STANDARD

Вероятностное преобразование Хафа (Probabilistic Hough Transform)
заключается в том, что для нахождения объекта достаточно провести преобразование Хафа только для части (a) точек исходного изображения, 0% <= a <= 100%. То есть сначала провести выделение «контрольных» точек с изображения, и для него провести преобразование Хафа.

rho — разрешение по дистанции
theta — разрешение по углу (в радианах)
threshold — пороговый параметр. Линия возвращается, если аккумулирующий параметр больше порогового значения.
param1 — первый параметр (в зависимости от метода трансфрмации:
CV_HOUGH_STANDARD — 0 — не используется
CV_HOUGH_PROBABILISTIC — минимальная длина линии
CV_HOUGH_MULTI_SCALE — делитель разрешения по дистанции (rho/param1))
param2 — второй параметр (в зависимости от метода трансфрмации:
CV_HOUGH_STANDARD — 0 — не используется
CV_HOUGH_PROBABILISTIC — максимальный промежуток между сегментами линии, лежащими на одной линии, чтобы считать их одним сегментом (объединить их вместе)
CV_HOUGH_MULTI_SCALE — делитель разрешения по углу (theta/param1))

если line_storage — указатель на хранилище памяти, то функция вернёт указатель на первый элемент последовательности, содержащей найденные линии.

В составе OpenCV уже идёт пример, демонстрирующий работу cvHoughLines2():
\OpenCV\samples\c\houghlines.c

//
// нахождение линий на изображении, 
// с использованием преобразования Хафа cvHoughLines2()
//
// модифицированный пример samples\c\houghlines.c
//
// http://robocraft.ru
//

#include <cv.h>
#include <highgui.h>
#include <math.h>

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

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

	if( !src ){
		printf("[!] Error: cant load image: %s \n", filename);
		return -1;
	}

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


	// хранилище памяти для хранения найденных линий
	CvMemStorage* storage = cvCreateMemStorage(0);
	CvSeq* lines = 0;
	int i = 0;


	dst = cvCreateImage( cvGetSize(src), 8, 1 );
	color_dst = cvCreateImage( cvGetSize(src), 8, 3 );

	// детектирование границ
	cvCanny( src, dst, 50, 200, 3 );

	// конвертируем в цветное изображение
	cvCvtColor( dst, color_dst, CV_GRAY2BGR );

	// нахождение линий
	lines = cvHoughLines2( dst, storage, CV_HOUGH_PROBABILISTIC, 1, CV_PI/180, 50, 50, 10 );

	// нарисуем найденные линии
	for( i = 0; i < lines->total; i++ ){
		CvPoint* line = (CvPoint*)cvGetSeqElem(lines,i);
		cvLine( color_dst, line[0], line[1], CV_RGB(255,0,0), 3, CV_AA, 0 );
	}

	// показываем
	cvNamedWindow( "Source", 1 );
	cvShowImage( "Source", src );

	cvNamedWindow( "Hough", 1 );
	cvShowImage( "Hough", color_dst );

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

	// освобождаем ресурсы
	cvReleaseMemStorage(&storage);
	cvReleaseImage(&src);
	cvReleaseImage(&dst);
	cvReleaseImage(&color_dst);
	cvDestroyAllWindows();
	return 0;
} 

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


Преобразовании Хафа для нахождения окружностей (Hough Circle Transform)

точки окружности можно представить формулой:

(x - a)^2 + (y - b)^2 = R2,

, где (a, b) – координаты центра окружности, а R – ее радиус.
т.е. формула, задающая семейство окружностей, имеет вид:

F (a, b, R, x, y) = (x - a)^2 + (y - b)^2 - R2 

Как видим, для нахождения окружностей нужно задавать уже 3 пераметра — координаты центра окружности и её радиус. Это приводит к увеличению пространства Хафа на целое измерение, что в итоге сказывается на скорости работы. Поэтому для поиска окружностей применяется т.н. градиентный метод Хафа (Hough gradient method).

эффективность использования преобразования Хафа резко падает при увеличении размерности фазового пространства, поэтому перед его применением желательно минимизировать каким-либо образом количество параметров кривой.
Можно существенно снизить количество кривых, потенциально проходящих через данную точку изображения, если рассматривать только кривые, касательная которой перпендикулярна градиенту яркости изображения в рассматриваемой точке. Таким образом, можно, например, свести задачу выделения окружностей с неизвестным радиусом к двумерному фазовому пространству.

Нахождение кругов
1. используется детектор границ Кенни для нахождения границ на изображении
2. для ненулевых точек высчитывается градиент (через вычисление 1-й производной по X и Y через cvSobel())
3. определяются центры кругов
4. относительно центра определяются ненулевые точки, лежащие на одном расстоянии

в OpenCV, преобразовании Хафа для нахождения окружностей реализуется функцией cvHoughCircles():

CVAPI(CvSeq*) cvHoughCircles( CvArr* image, void* circle_storage,
                              int method, double dp, double min_dist,
                              double param1 CV_DEFAULT(100),
                              double param2 CV_DEFAULT(100),
                              int min_radius CV_DEFAULT(0),
                              int max_radius CV_DEFAULT(0));

— нахождение кругов на изображении

image — исходное изображение (8-битное, одноканальное, градации серого)
line_storage — хранилище памяти для сохранения найденных кругов (можно использовать матрицу типа CV_32FC3, 1xЧисло_кругов CvMat). Круг хранится в виде трёх чисел типа float: координаты центра (x,y) и радиус.
method — метод, на настоящее время реализован только:

#define CV_HOUGH_GRADIENT 3

dp — разрешение сумматора, используемое для детектирования центров кругов (1 — одинаково с исходным изображением, 2 — половина высоты/ширины и т.д.)
min_dist — минимальная дистанция между центрами детектируемых кругов
param1 — первый параметр (в зависимости от метода трансфрмации:
CV_HOUGH_GRADIENT — верхнее пороговое значение, передаваемое детектору границ Кенни (нижнее пороговое значение будет в 2 раза меньше)

param2 — второй параметр (в зависимости от метода трансфрмации:
CV_HOUGH_GRADIENT — суммирующее пороговое значение детектированя центров

min_radius — минимальный радиус круга
max_radius — максимальный радиус круга

//
// Несколько модифицированный пример example 6-1 Hough circles
// нахождение кругов на изображении, 
// с использованием трансформации Хафа cvHoughCircles()
//
// из книги:
//   Learning OpenCV: Computer Vision with the OpenCV Library
//     by Gary Bradski and Adrian Kaehler
//     Published by O'Reilly Media, October 3, 2008
//
//
// http://robocraft.ru
//

#include <cv.h>
#include <highgui.h>
#include <math.h>

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

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

	// загрузим оригинальное изображении
	IplImage* src = cvLoadImage(filename ); 

	// хранилище памяти для кругов
	CvMemStorage* storage = cvCreateMemStorage(0);
	// сглаживаем изображение
	cvSmooth(image, image, CV_GAUSSIAN, 5, 5 );
	// поиск кругов
	CvSeq* results = cvHoughCircles( 
		image, 
		storage, 
		CV_HOUGH_GRADIENT, 
		10, 
		image->width/5 
		); 
	// пробегаемся по кругам и рисуем их на оригинальном изображении
	for( int i = 0; i < results->total; i++ ) {
		float* p = (float*) cvGetSeqElem( results, i );
		CvPoint pt = cvPoint( cvRound( p[0] ), cvRound( p[1] ) );
		cvCircle( src, pt, cvRound( p[2] ), CV_RGB(0xff,0,0) );
	}
	// показываем
	cvNamedWindow( "cvHoughCircles", 1 );
	cvShowImage( "cvHoughCircles", src);

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

	// освобождаем ресурсы
	cvReleaseMemStorage(&storage);
	cvReleaseImage(& image);
	cvReleaseImage(&src);
	cvDestroyAllWindows();
	return 0;
}

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


результат cvHoughCircles() очень сильно зависит от параметров,
например,

CvSeq* results = cvHoughCircles( 
		image, 
		storage, 
		CV_HOUGH_GRADIENT, 
		2, 
		image->width/5 
		); 

уже даёт результат:


Существует и так называемое Обобщённое преобразование Хафа, с помощью которого можно искать фигуры произвольной формы.
( хм… об Обобщённом преобразовании Хафа даже нету странички в русской википедии — сейчас исправим :))

Далее: 29. Интегральное изображение

Ссылки:
http://en.wikipedia.org/wiki/Hough_transform
http://ru.wikipedia.org/wiki/Преобразование_Хафа
http://ru.wikipedia.org/wiki/Обобщённое_преобразование_Хафа
Преобразование Хафа (Hough transform)
Использование алгоритма Хафа для коррекции наклона фотографии