PROCESAMIENTO DE IMAGENES - TEMPLATE MATCHING

Template Matching es una técnica dentro del procesamiento de imagenes que nos sirve para encontrar partes pequeñas de una imagen (template), dentro de una imagen completa. http://en.wikipedia.org/wiki/Template_matching
Es una medida de qué tan bien un template en niveles de gris g(x,y) se ajusta a una imagen f(x,y) dada. Se puede usar una función de distancia o una NCC (normalized cross-correlation). http://rkb.home.cern.ch/rkb/AN16pp/


Es una técnica de reconocimiento de patrones que consiste en buscar en una imagen I, una imagen mas pequeña denominada patron o template (T).

Dada una imagen A de tamaño (WxH), y P una imagen mas pequeña denominada patron de tamaño (wxh), el resultado es una imagen M de tamaño (W-w+1)x(H-h+1), en donde cada uno de sus pixeles indica la verosimilitud o probabilidad de que el rectangulo [x,y], [x+w-1, y+h-1] de A contenga el patron P.





El siguiente código ilustra el uso de la función cvMatchTemplate() de Open CV


MatchTemplate
Compares template against overlapped image regions
void cvMatchTemplate( const CvArr* I, const CvArr* T,CvArr* result, int method );
I
Image where the search is running. It should be single-chanel, 8-bit or 32-bit floating-point.
T
Searched template; must be not greater than the source image and the same data type as the image.
R
Image of comparison results; single-channel 32-bit floating-point. If I is W×H and T is w×h then R
must be W-w+1×H-h+1.
method
Specifies the way the template must be compared with image regions (see below).

The function cvMatchTemplate [p 202] is similiar to cvCalcBackProjectPatch [p 199] . It slids through I,
compares w×h patches against T using the specified method and stores the comparison results to result.
Here are the formular for the different comparison methods one may use (the summation is done over
template and/or the image patch: x’=0..w-1, y’=0..h-1):

method=CV_TM_SQDIFF:
R(x,y)=sum x’,y’ [T(x’,y’)-I(x+x’,y+y’)] 2

method=CV_TM_SQDIFF_NORMED:
R(x,y)=sum x’,y’ [T(x’,y’)-I(x+x’,y+y’)] 2 /sqrt[sum x’,y’ T(x’,y’) 2 ·sum x’,y’ I(x+x’,y+y’) 2 ]

method=CV_TM_CCORR:
R(x,y)=sum x’,y’ [T(x’,y’)·I(x+x’,y+y’)]


method=CV_TM_CCORR_NORMED:
R(x,y)=sum x’,y’ [T(x’,y’)·I(x+x’,y+y’)]/sqrt[sum x’,y’ T(x’,y’) 2 ·sum x’,y’ I(x+x’,y+y’) 2 ]

method=CV_TM_CCOEFF:
R(x,y)=sum x’,y’ [T’(x’,y’)·I’(x+x’,y+y’)],
where T’(x’,y’)=T(x’,y’) - 1/(w·h)·sum x",y" T(x",y") (mean template brightness=>0)
I’(x+x’,y+y’)=I(x+x’,y+y’) - 1/(w·h)·sum x",y" I(x+x",y+y") (mean patch brightness=>0)

method=CV_TM_CCOEFF_NORMED:
R(x,y)=sum x’,y’ [T’(x’,y’)·I’(x+x’,y+y’)]/sqrt[sum x’,y’ T’(x’,y’) 2 ·sum x’,y’ I’(x+x’,y+y’) 2 ]

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


#include "cv.h"
#include "highgui.h "
#include "stdio.h"


int main() {


IplImage* im = cvLoadImage( "../cam1.jpg", -1); //-1 indica que cargue la imagen en sus colores y caracteristicas originales

if( im == 0 ) {
std::cerr << "Error al cargar la imagen: " <<>
return 1;
}

IplImage* imG = cvCreateImage(cvSize(im->width, im->height), 8, 1);//direcciona un espacio en memoria con las dimensiones de ancho y alto de im, con 8 bits y 1 canal

cvCvtColor(im, imG, CV_BGR2GRAY);//img cambia su espacio de color al espacio de color de im, (BGR2GRAY)


//coordenadas iniciales del rectángulo
int xVal = 150;
int yVal = 50;
int neighLength = 25;
CvRect rect = cvRect(xVal,yVal,neighLength,neighLength);//traza una area rectangular

CvMat* tplate = cvCreateMat(neighLength, neighLength, CV_8UC1);//cvCreateMat crea una matriz(renglones, columnas, tipo de elemento)CV_8UC1(8 bits unsigned, 1 canal)

cvGetSubRect(imG, tplate, rect );//obtiene de img el area definida por rect y la asigna a tplate

//se especifica el tamaño necesario para realizar la función matching
int resultW = imG->width - tplate->width + 1;
int resultH = imG->height - tplate->height +1;

//direcciona el espacio para cada imagen
IplImage* result0 = cvCreateImage(cvSize(resultW, resultH), IPL_DEPTH_32F, 1);
IplImage* result1 = cvCreateImage(cvSize(resultW, resultH), IPL_DEPTH_32F, 1);
IplImage* result2 = cvCreateImage(cvSize(resultW, resultH), IPL_DEPTH_32F, 1);
IplImage* result3 = cvCreateImage(cvSize(resultW, resultH), IPL_DEPTH_32F, 1);
IplImage* result4 = cvCreateImage(cvSize(resultW, resultH), IPL_DEPTH_32F, 1);
IplImage* result5 = cvCreateImage(cvSize(resultW, resultH), IPL_DEPTH_32F, 1);

//se aplican cada una de las técnicas de matching
cvMatchTemplate(imG, tplate, result0, CV_TM_SQDIFF);
cvMatchTemplate(imG, tplate, result1, CV_TM_SQDIFF_NORMED);
cvMatchTemplate(imG, tplate, result2, CV_TM_CCORR);
cvMatchTemplate(imG, tplate, result3, CV_TM_CCORR_NORMED);
cvMatchTemplate(imG, tplate, result4, CV_TM_CCOEFF);
cvMatchTemplate(imG, tplate, result5, CV_TM_CCOEFF_NORMED);

//se muestra el resultado del matching
cvNamedWindow("SQDIFF", 0 );
cvNamedWindow("SQDIFF_NORMED",0);
cvNamedWindow("CCORR",0);
cvNamedWindow("CCORR_NORMED",0);
cvNamedWindow("CCOEFF",0);
cvNamedWindow("CCOEEFF_NORMED",0);

cvShowImage("SQDIFF", result0);
cvShowImage("SQDIFF_NORMED", result1);
cvShowImage("CCORR", result2);
cvShowImage("CCORR_NORMED", result3);
cvShowImage("CCOEFF", result4);
cvShowImage("CCOEEFF_NORMED", result5);

//marca el área en la imagen original de donde se obtuvo el template
cvRectangle(imG, cvPoint(xVal,yVal), cvPoint(xVal+neighLength,yVal+neighLength),
CV_RGB(255,0,255),2 , 8, 0);

//muestra la imagen y el template
cvNamedWindow("Image",0);
cvNamedWindow("Template",0);
cvShowImage("Image", imG);
cvShowImage("Template", tplate);

cvWaitKey(0);

cvReleaseImage(&imG);
cvReleaseMat(&tplate);
cvReleaseImage(&result0);
cvReleaseImage(&result1);
cvReleaseImage(&result2);
cvReleaseImage(&result3);
cvReleaseImage(&result4);
cvReleaseImage(&result5);

cvDestroyAllWindows();

return 0;

}