cvMatchTemplate

[anry 0]

Добрый день. у меня пара вопрос по работе функции cvMatchTemplate.

1. Нужно ли переводить изображение в градации серого.

2. Как вывести значение похожести на шаблон. Можно кусок кода, а то я в си пока плохо разбираюсь

[Smorodov 579]

Добрый день. у меня пара вопрос по работе функции cvMatchTemplate.

1. Нужно ли переводить изображение в градации серого.

2. Как вывести значение похожести на шаблон. Можно кусок кода, а то я в си пока плохо разбираюсь

Вот здесь есть код: http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html

[anry 0]

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

[Smorodov 579]

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

В документации написано вот что:

After the function finishes the comparison, the best matches can be found as global minimums (CV_TM_SQDIFF) or maximums (CV_TM_CCORR and CV_TM_CCOEFF) using the MinMaxLoc function.

что буквально значит:

После того, как функция завершит сравнение, наилучшие совпадения могут быть найдены как глобальные минимумы (метод поиска CV_TM_SQDIFF) или максимумы (методы поиска CV_TM_CCORR и CV_TM_CCOEFF) при помощи функции MinMaxLoc. Скорее всего Вы используете метод CV_TM_SQDIFF.

подробнее здесь: http://opencv.willowgarage.com/documentati...cvMatchTemplate

[anry 0]

В документации написано вот что:

After the function finishes the comparison, the best matches can be found as global minimums (CV_TM_SQDIFF) or maximums (CV_TM_CCORR and CV_TM_CCOEFF) using the MinMaxLoc function.

что буквально значит:

После того, как функция завершит сравнение, наилучшие совпадения могут быть найдены как глобальные минимумы (метод поиска CV_TM_SQDIFF) или максимумы (методы поиска CV_TM_CCORR и CV_TM_CCOEFF) при помощи функции MinMaxLoc. Скорее всего Вы используете метод CV_TM_SQDIFF.

подробнее здесь: http://opencv.willowgarage.com/documentati...cvMatchTemplate

Да, я использую метод CV_TM_SQDIFF.

Можно ли как-то сделать чтобы функция не учитывала фон на эталоне?

[Smorodov 579]

Да, я использую метод CV_TM_SQDIFF.

Можно ли как-то сделать чтобы функция не учитывала фон на эталоне?

Можно сделать шаблон, включающий не весь искомый объект, а какую-нибудь его характерную часть.

[Smorodov 579]

Написал програмку, позволяющую поэкспериментировать с cvMatchTemplate. Программа строит зависимости максимального и минимального отклика от угла поворота шаблона. Если открывать изображения больше чем 100х100 график строится корректно, но само изображение не помещается на панельки, масштабирование не делал умышленно, если кому нужно что то переделать, исходники в архиве.

Слева отображается само изображение, справа отклик, графики нормированы, для того чтобы посмотреть значения нужно навести мышь на график.

MatchTemplTool.rar

ЗЫ: С большими изображениями работает медленно (в процессе поворота ни на что не отвечает), так что лучше работать с маленькими (до 100 на 100) изображениями.

[mrgloom 242]

как сделать так чтобы искать не 1 пик, а смотреть чтобы совместились главный пик+ еще несколько локальных пиков? это должно повысить точность.

[mrgloom 242]

хмм вроде бы ответ

http://tech.dir.groups.yahoo.com/group/OpenCV/message/5681

сначала дилатация, а потом найти пики, видимо все равно придется писать руками или резать на полоски и потом cvmaxmin.

хотя не понятно как выбрать нужный уровень дилатации.

[Smorodov 579]

Можно бинаризировать по порогу, затем найти компоненты связности, затем использовать эти компоненты связности как маски для cvMinMaxLoc одну за другой.

[mrgloom 242]

я все таки не очень понял поможет это или нет.

cvMatchTemplate не особо удобна т.к. требуется расширять нулями первое(что требует доп памяти) или уменьшать второе(что может снизить точность) , и непонятно будет ли реализация с FFTW работать быстрее.

2 изображения которые перекрываются.

выделяем область перекрытия с запасом на 1 изображении, и берем небольшой кусок на втором. (в целом работает но бывают ошибки)

в каком то алгоритме видел параметр сколько пиков найти, но что это за пики непонятно, может второй кусок бьется на полоски и определяется их пики? а потом проверяется правильно ли они найдены?

[mrgloom 242]

http://www-cs.engr.ccny.cuny.edu/~wolberg/cs470/doc/logpolar.pdf

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.5186

[mrgloom 242]

зачем кстати cvMatchTemplate использует аж 6 разных методов?

и что если изображение переводить в серое или оставить только контуры?

пытаюсь понять всю эту кухню с корреляцией и ее нормированием

Principles of Digital Image Processing Core(11 глава) - вроде бы неплохая книга.

http://library.nu/docs/57XI2HCOZ9/Principles%20of%20Digital%20Image%20Processing%3A%20Fundamental%20Techniques%20%28Undergraduate%20Topics%20in%20Computer%20Science%29

[mrgloom 242]

http://students.ee.sun.ac.za/~riaanvdd/image_processing_tools.htm

http://www.mathworks.nl/matlabcentral/fileexchange/3000

Fourier-Mellin Transform

говорят инвариантен к скейлу и повороту

нормированная кросс-кореляция

http://isas.uka.de/Publikationen/SPIE01_BriechleHanebeck_CrossCorr.pdf

инвариантность к повороту и скейлу

http://www.seasdtc.com/events/2009_conference/downloads/pdf/sensor_exploitation/A10_(SEN005)_paper.pdf

http://www.gests.org/down/2518.pdf

[mrgloom 242]

http://paulbourke.net/miscellaneous/correlate/

можно считать в лоб ,а можно считать через фурье преобразование?

как выглядит процесс когда через фурье преобразование?

прямое фурье преобразование для всего изображение и темплейта, потом темплейт проходит по изображению и перемножается с областью которая находится под ним(пиксель на пиксель, потом сложение(?) и запись в среднюю точку?) (вообщем в этой части я вот не уверен), потом обратное фурье преобразование и поиск на изображении максимума\минимума.

т.е.

iFFT(FFT(image) * FFT(what your looking for))

Do normalization on phase, then search for maxima

но не очень понятно что имеется ввиду под операцией *

и что значит нормализация по фазе?

FFTW+opencv

http://opencv-code.com/Using_the_Fast_Fourier_Transform_Library_FFTW#more-262

[mrgloom 242]

есть ли смысл считать корреляцию по отдельным каналам изображения?

или достаточно только gray?

[Nuzhny 243]

Если сам цвет не нужен или не важен, то можно ограничиться gray.

[mrgloom 242]

попробовал библиотеку FFTW, но добиться ускорения не получилось.

во-первых не использовалось wisdom, преобразования с флагом FFTW_ESTIMATE, использовалось преобразование для одномерного массива, и возможно все считалось не совсем оптимально.

+ еще получается, что кол-во операций зависит только от размера изображения, а не от размера темплейта.

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

#include "stdafx.h"

#include "fftw3.h"

#include "cv.h"

#include "highgui.h"

#include <omp.h>

#include <time.h>


//get phase correlation from two images and save result to the third image

void phase_correlation( IplImage* src, IplImage *tpl, IplImage *poc )

{

	int 	i, j, k;

	double	tmp;


	/* get image properties */

	int width  	 = src->width;

	int height   = src->height;

	int step     = src->widthStep;

	int fft_size = width * height;


	/* setup pointers to images */

	uchar 	*src_data = ( uchar* ) src->imageData;

	uchar 	*tpl_data = ( uchar* ) tpl->imageData;

	double 	*poc_data = ( double* )poc->imageData;


	/* allocate FFTW input and output arrays */

	fftw_complex *img1 = ( fftw_complex* )fftw_malloc( sizeof( fftw_complex ) * width * height );

	fftw_complex *img2 = ( fftw_complex* )fftw_malloc( sizeof( fftw_complex ) * width * height );

	fftw_complex *res  = ( fftw_complex* )fftw_malloc( sizeof( fftw_complex ) * width * height );	


	/* setup FFTW plans */

	fftw_plan fft_img1 = fftw_plan_dft_1d( width * height, img1, img1, FFTW_FORWARD,  FFTW_ESTIMATE );

	fftw_plan fft_img2 = fftw_plan_dft_1d( width * height, img2, img2, FFTW_FORWARD,  FFTW_ESTIMATE );

	fftw_plan ifft_res = fftw_plan_dft_1d( width * height, res,  res,  FFTW_BACKWARD, FFTW_ESTIMATE );


		/*omp_set_num_threads(2);

	int t= omp_get_num_threads();*/

	//plan execution is thread-safe, but plan creation and destruction are not:

	//you should create/destroy plans only from a single thread,

	//but can safely execute multiple plans in parallel.

	//int f= fftw_init_threads();

	//fftw_plan_with_nthreads(2/*omp_get_num_threads()*/);//работает только если 1 тред


	/* load images' data to FFTW input */

	for( i = 0, k = 0 ; i < height ; i++ ) {

		for( j = 0 ; j < width ; j++, k++ ) {

			img1[k][0] = ( double )src_data[i * step + j];

			img1[k][1] = 0.0;


			img2[k][0] = ( double )tpl_data[i * step + j];

			img2[k][1] = 0.0;

		}

	}


	/* obtain the FFT of img1 */

	fftw_execute( fft_img1 );


	/* obtain the FFT of img2 */

	fftw_execute( fft_img2 );


	/* obtain the cross power spectrum */

	for( i = 0; i < fft_size ; i++ ) {

		res[i][0] = ( img2[i][0] * img1[i][0] ) - ( img2[i][1] * ( -img1[i][1] ) );

		res[i][1] = ( img2[i][0] * ( -img1[i][1] ) ) + ( img2[i][1] * img1[i][0] );


		tmp = sqrt( pow( res[i][0], 2.0 ) + pow( res[i][1], 2.0 ) );


		res[i][0] /= tmp;

		res[i][1] /= tmp;

	}


	/* obtain the phase correlation array */

	fftw_execute(ifft_res);


	/* normalize and copy to result image */

	for( i = 0 ; i < fft_size ; i++ ) {

        poc_data[i] = res[i][0] / ( double )fft_size;

	}


	/* deallocate FFTW arrays and plans */

	//fftw_cleanup_threads();

	fftw_destroy_plan( fft_img1 );

	fftw_destroy_plan( fft_img2 );

	fftw_destroy_plan( ifft_res );

	fftw_free( img1 );

	fftw_free( img2 );

	fftw_free( res );

}


//добавляет изображение в левый верхний угол и расширет под размер

IplImage* img_resize(IplImage* src, int w, int h)

{

	//только для одноканальных

	IplImage* out= cvCreateImage(cvSize(w,h),IPL_DEPTH_8U,1);

	cvZero(out);

	cvSetImageROI(out,cvRect(0,0,src->width,src->height));

	cvCopyImage(src,out);

	cvResetImageROI(out);

	return out;

}


CvPoint FFTW_test(IplImage* src,IplImage* temp)

{

	clock_t start=clock();


	/*if( argc < 3 ) {

		fprintf( stderr, "Usage: phase_correlation <image> <template> <result>\n" );

		return 1;	

	}*/


	/* load srcerence image */

	//src = cvLoadImage( "001_001.PNG"/*argv[1]*/, CV_LOAD_IMAGE_GRAYSCALE );


	///* always check */

	//if( src == 0 ) {

	//	fprintf( stderr, "Cannot load %s!\n", argv[1] );

	//	return 1;	

	//}


	/* load template image */

	//tpl = cvLoadImage( "templ4.png"/*argv[2]*/, CV_LOAD_IMAGE_GRAYSCALE );


	int t_w=temp->width;

	int t_h=temp->height;


	IplImage* tmp=  img_resize(temp,src->width,src->height);

	///* always check */

	//if( tpl == 0 ) {

	//	fprintf( stderr, "Cannot load %s!\n", argv[2] );

	//	return 1;	

	//}


	/* create a new image, to store phase correlation result */

	IplImage* poc = cvCreateImage( cvSize( tmp->width, tmp->height ), IPL_DEPTH_64F, 1 );


	/* get phase correlation of input images */

	phase_correlation( src, tmp, poc );


	//как быть если на изображении много темплейтов?

	/* find the maximum value and its location */

    CvPoint minloc, maxloc;

	double  minval, maxval;

	cvMinMaxLoc( poc, &minval, &maxval, &minloc, &maxloc, 0 );


	//получаются инвертированные координаты

	/*cvCircle(src,cvPoint(src->width-maxloc.x,src->height-maxloc.y),3,cvScalar(255,255,255));

	cvRectangle(src,cvPoint(src->width-maxloc.x,src->height-maxloc.y),

					cvPoint(src->width-maxloc.x+t_w,src->height-maxloc.y+t_h),

					cvScalar(255,255,255));*/


	///* display images and free memory */

	//cvNamedWindow( "tpl", CV_WINDOW_AUTOSIZE );

	//cvNamedWindow( "src", CV_WINDOW_AUTOSIZE );	

	//

	//cvShowImage( "tpl", temp );

	//cvShowImage( "src", src );

	//

	//cvWaitKey( 0 );

	//

	//cvDestroyWindow( "tpl" );

	//cvDestroyWindow( "src" );	


	/*cvReleaseImage( &src );

	cvReleaseImage( &temp );*/

	cvReleaseImage( &tmp );

	cvReleaseImage( &poc );


	clock_t end=clock();


	int time= end-start;


	fprintf( stdout, "Time= %d using clock() \n" ,time );

	fprintf( stdout, "Maxval at (%d, %d) = %2.4f\n", maxloc.x, maxloc.y, maxval );


	CvPoint pt;

	pt.x= src->width-maxloc.x;

	pt.y= src->height-maxloc.y;

	return pt;

}

CvPoint OPENCV_test(IplImage* src,IplImage* temp)

{

	clock_t start=clock();

	/*IplImage* src= cvLoadImage("001_001.PNG",0);

	IplImage* temp= cvLoadImage("templ4.png",0);*/

	/*int t_w= temp->width;

	int t_h= temp->height;*/


	int iwidth= src->width - temp->width + 1;

	int iheight= src->height - temp->height + 1;

	IplImage* dst= cvCreateImage( cvSize( iwidth, iheight ), 32, 1 );

	cvMatchTemplate( src, temp, dst, CV_TM_CCORR_NORMED);  //разные варианты последнего параметра дают разные результаты.(и требуют нахождения мин или макс!)

	double		minval, maxval;

	CvPoint		minloc, maxloc;

	cvMinMaxLoc( dst, &minval, &maxval, &minloc, &maxloc, 0 );


	//cvCircle(src,cvPoint(maxloc.x,maxloc.y),3,cvScalar(255,255,255));

	//cvRectangle(src,cvPoint(maxloc.x,maxloc.y),

	//				cvPoint(maxloc.x+t_w,maxloc.y+t_h),

	//				cvScalar(255,255,255));


	///* display images and free memory */

	//cvNamedWindow( "tpl1", CV_WINDOW_AUTOSIZE );

	//cvNamedWindow( "src1", CV_WINDOW_AUTOSIZE );	

	//

	//cvShowImage( "tpl1", src );

	//cvShowImage( "src1", temp );

	//

	//cvWaitKey( 0 );


	/*cvReleaseImage(&src);

	cvReleaseImage(&temp);*/

	cvReleaseImage(&dst);


	clock_t end=clock();


	int time= end-start;

	fprintf( stdout, "Time= %d using clock() \n" ,time );

	fprintf( stdout, "Maxval at (%d, %d) = %2.4f\n", maxloc.x, maxloc.y, maxval );

	//fprintf( stdout, "Minval at (%d, %d) = %2.4f\n", minloc.x, minloc.y, minval );


	CvPoint pt;

	pt.x= maxloc.x;

	pt.y= maxloc.y;

	return pt;

}

int _tmain(int argc, _TCHAR* argv[])

{


	IplImage* src= cvLoadImage("001_001.PNG",0);

	IplImage* temp= cvLoadImage("templ4.png",0);

	int t_w= temp->width;

	int t_h= temp->height;


	CvPoint pt_1,pt_2;


		pt_2= OPENCV_test(src, temp);

		pt_1= FFTW_test(src, temp);


	cvCircle(src,cvPoint(pt_1.x,pt_1.y),3,cvScalar(255,0,255));

	cvCircle(src,cvPoint(pt_2.x,pt_2.y),3,cvScalar(255,255,0));

	cvRectangle(src,cvPoint(pt_1.x,pt_1.y),

					cvPoint(pt_1.x+t_w,pt_1.y+t_h),

					cvScalar(255,0,255));

	cvRectangle(src,cvPoint(pt_2.x,pt_2.y),

					cvPoint(pt_2.x+t_w,pt_2.y+t_h),

					cvScalar(255,255,0));


	cvNamedWindow( "tpl1", CV_WINDOW_AUTOSIZE );

	cvNamedWindow( "src1", CV_WINDOW_AUTOSIZE );	

	cvShowImage( "tpl1", src );

	cvShowImage( "src1", temp );

	cvWaitKey( 0 );


	getchar();


	return 0;

}

[mrgloom 242]

ускорение cvMatchTemplate

http://opencv.willowgarage.com/wiki/FastMatchTemplate

единственное что пришлось сделать

так это изменить 1 строчку, не понятно на чем автор компилил, или я чего то не понял.

void MultipleMaxLoc( const IplImage& image, 

                     CvPoint**       locations,

                     int             numMaxima )

{

//double maxima[numMaxima];

  double* maxima= new double[numMaxima];

//..

delete[] maxima;

}

[Nuzhny 243]

Странно, у меня там немного другой код:

void MultipleMaxLoc(const Mat& image,

                    Point**    locations,

                    int        numMaxima)

{

    // initialize input variable locations

    *locations = new Point[numMaxima];


    // create array for tracking maxima

    float* maxima = new float[numMaxima];

    for(int i = 0; i < numMaxima; i++)

    {

        maxima[i] = 0.0;

    }


    Size size = image.size();


    // extract the raw data for analysis

    for(int y = 0; y < size.height; y++)

    {

        for(int x = 0; x < size.width; x++)

        {

            float data = image.at<float>(y, x);


            // insert the data value into the array if it is greater than any of the

            //  other array values, and bump the other values below it, down

            for(int j = 0; j < numMaxima; j++)

            {

                // require at least 50% confidence on the sub-sampled image

                // in order to make this as fast as possible

                if(data > 0.5 && data > maxima[j])

                {

                    // move the maxima down

                    for(int k = numMaxima - 1; k > j; k--)

                    {

                        maxima[k] = maxima[k-1];

                        (*locations)[k] = ( *locations )[k-1];

                    }


                    // insert the value

                    maxima[j] = data;

                    (*locations)[j].x = x;

                    (*locations)[j].y = y;

                    break;

                }

            }

        }

    }


    delete [] maxima;

}

Или успели поменять?

[mrgloom 242]

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

то ли такие выражения возможны в С, то ли GCC такое переваривает.

еще судя по всему есть cv::gpu::MatchTemplate, но его еще не тестил.

[mrgloom 242]

что если надо склеить 2 изображения.

если знать перекрытие, то можно отрезать от второго изображения кусок и использовать его как темплэйт, а что если не знать перекрытия?

(отрезать темплейты разного размера с шагом в 1 пиксель не очень хороший вариант)

[Smorodov 579]

Думается можно использовать пирамиду. Совместить на самом маленьком изображении и затем подниматься по пирамиде (или спускаться, кто как представляет ).

[mrgloom 242]

вопрос не в пирамидах ,а в том что в MatchTemplate принимает на вход тэмплейт, а у меня 2 изображения и я не знаю точно на сколько они перекрываются.

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

[Smorodov 579]

Я думаю что это переборная задача. Поэтому, нужно как можно сильнее уменьшить количество вариантов перебора, а это возможно только уменьшением масштаба изображения и шаблона. Правда это будет работать только если перекрытие не слишком маленькое.

ЗЫ: Может быть тут RANSAC приспособить?