Thursday, November 11, 2004

OpenCV codes

[Opencv] C++ code for matched filter:

/*

Author: Tristen Georgiou
Email: tristen_georgiou@hotmail.com
Date: August 5, 2004

This code presents an alternative (much faster) method to searching an image using OCV's cvMatchTemplate function.
Use at own risk, I have not extensively tested this (works great for my application though). All I ask in return
is that if you make improvements, either email it to me (so that I can also improve my code) or post back to the
files section of the Open Source Computer Vision Library Community, in Yahoo! Groups
(http://groups.yahoo.com/group/OpenCV/).

It is tailored to my application (and hence code), so you may have to make some modifications. I have tried to
remove any specific code, but there is likely some code I have missed. Enjoy!

Performance Testing:
CPU: AMD Athlon XP1600+
RAM: 256 mb
OS: Red Hat Linux 7.3
GUI: wxWindows
When searching a 640x480 image, the original OCV function, cvMatchTemplate, took ~25-30 seconds.
This function only took approximately 100-150 ms to search the same image, with identical results.

Background info on how the algorithm was formed:
the time it takes to perform the cvMatchTemplate is dependant on the sizes of the input images.
Assuming the image where the search is performed is constant (call it the search image), it can be found that the
most calculations performed occur when the template image is half the size of the search image, and the # of
calculations (using the CV_CCORR_NORMED method) approaches 50 billion calculations! Larger and smaller template
images require less calculations, and the function looks similar to a bell curve. If both the search image and
the template image are reduced to 1/4 of the size, and the function is performed again, we find the most
calculations again occurs when the template image is half the size of the search image, but the # of calculations
approaches 2 billion. If we again reduce by 1/4 of the size, we get an even more significant reduction in
calculations. Using this, I formed the following algorithm:

1. check image size, if it is less than 320*240 pixels, i = 1, if bigger i = 2 (if image is small, too much
downsampling will reduce image quality, and results are unknown. I have tested this but downsampling twice
reduces image size 16 times, and search times were about 100 ms, and I figured another downsample wouldn't increase
performance significantly.)
2. us cvPyrDown function to downsample the image i times
3. perform a cvMatchTemplate on the downsampled images
4. find the top numLocations matches in the result image (this array is in order from best match to worst)
5. coord transform the pntLocs[numLocations] points back to the original image
6. use the cvMatchTemplate on the original, large images, but set the ROI on the search image to the same size as
the template image, centred at the pntLocs[numLocations] points.
7. repeat 6 for remaining pntLocs[numLocations] until a suitable match is found

*/

/*
The following are some values that I have defined elsewhere in my code

iMatchTempParams[TEMPLATETYPE] = CV_TM_CCORR_NORMED
imgSize.width = 640
imgSize.height = 480

*/

/*
Function FastMatchTemplate
src - source image, where search takes place
temp - template image, image we are searching for
numLocations - number of best matches to look for ( I set this to 2 )
searchBorder - when transforming downsampled coords back to original image, chance that we are off by a few pixels,
so this value adds on a border to the search ROI when searching the large images ( I set this to 5 ).
score - returns the score of the best match
loc - returns the location of the best match
*/
void FastMatchTemplate( IplImage *src, IplImage *temp, int numLocations, int searchBorder, double &score, CvPoint &loc )
{
CvSize sizeTemp( imgSize ); // 640x480
CvRect rectTempSrc = cvGetImageROI( src );
CvRect rectTempTarg = cvGetImageROI( temp );
CvPoint pntLocs[numLocations];
int iX, iY;

for( int a = 0; a < numLocations; a++ )
{
pntLocs[a].x = 0;
pntLocs[a].y = 0;
}

// if source image is small, or has small ROI, don't want to down pyramid too much, or too much loss of information
int iNumLevels = 1;
if( (rectTempSrc.width*rectTempSrc.height) > (320*240) ) // larger than half of the image
iNumLevels = 2; // 2 down pyramids...

IplImage *pyrSrcImage;
IplImage *pyrTargImage;
IplImage *tempImage1;
IplImage *tempImage2;

tempImage1 = cvCloneImage( src );
tempImage2 = cvCloneImage( temp );

// Perform the down pyramiding
for( int i = 0; i < iNumLevels; i++ )
{
// reduce image size to a quarter (2 for width X 2 for height) of what it was...
sizeTemp.width /= 2;
sizeTemp.height /= 2;
// create storage images
pyrSrcImage = cvCreateImage(sizeTemp, 8, 1);
pyrTargImage = cvCreateImage(sizeTemp, 8, 1);
if( src->roi != NULL ) // if roi is defined
{
rectTempSrc.x /= 2;
rectTempSrc.y /= 2;
rectTempSrc.width /= 2;
rectTempSrc.height /= 2;
cvSetImageROI( pyrSrcImage, rectTempSrc );
}

if( temp->roi != NULL ) // if roi is defined
{
rectTempTarg.x /= 2;
rectTempTarg.y /= 2;
rectTempTarg.width /= 2;
rectTempTarg.height /= 2;
cvSetImageROI( pyrTargImage, rectTempTarg );
}
// sample images down down
cvPyrDown( tempImage1, pyrSrcImage, CV_GAUSSIAN_5x5 );
cvPyrDown( tempImage2, pyrTargImage, CV_GAUSSIAN_5x5 );
// prepare for next cycle, if there is one...
tempImage1 = cvCloneImage( pyrSrcImage );
tempImage2 = cvCloneImage( pyrTargImage );
}

// update the src image size
rectTempSrc = cvGetImageROI( pyrSrcImage );
rectTempTarg = cvGetImageROI( pyrTargImage );
IplImage *result = cvCreateImage(
cvSize( rectTempSrc.width - rectTempTarg.width + 1, rectTempSrc.height - rectTempTarg.height + 1 ),
IPL_DEPTH_32F, 1
);
cvMatchTemplate( pyrSrcImage, pyrTargImage, result, iMatchTempParams[TEMPLATETYPE] ); // match on reduced images
// find top numLocation matches
if( (iMatchTempParams[TEMPLATETYPE] == CV_TM_SQDIFF) || (iMatchTempParams[TEMPLATETYPE] == CV_TM_SQDIFF_NORMED) ) // use the minima from result
MultipleMinLoc( result, pntLocs, numLocations );
else // use the maxima from result
MultipleMaxLoc( result, pntLocs, numLocations );

// search large image at top numLocation locations
for( int j = 0; j < numLocations; j++ )
{
CvRect rectTempLargeSrc; // for setting the src image's ROI
rectTempSrc = cvGetImageROI( src );
rectTempTarg = cvGetImageROI( temp );

// transform coordinates to large image
pntLocs[j].x *= 2;
pntLocs[j].y *= 2;
if( iNumLevels == 2 )
{
pntLocs[j].x *= 2;
pntLocs[j].y *= 2;
}
// transforms coords in result image back to searched image
pntLocs[j].x = pntLocs[j].x + rectTempSrc.x + (rectTempTarg.width - 1)/2;
pntLocs[j].y = pntLocs[j].y + rectTempSrc.y + (rectTempTarg.height - 1)/2;

// set new search area for large images, set it slightly larger than target ROI, using searchBorder
rectTempLargeSrc.x = pntLocs[j].x - (rectTempTarg.width + searchBorder)/2;
rectTempLargeSrc.y = pntLocs[j].y - (rectTempTarg.height + searchBorder)/2;
rectTempLargeSrc.width = rectTempTarg.width + searchBorder;
rectTempLargeSrc.height = rectTempTarg.height + searchBorder;
// make sure that search border doesn't cause search area to be outside image area
if( rectTempLargeSrc.x < 0 )
rectTempLargeSrc.x = 0;
if( rectTempLargeSrc.x + rectTempLargeSrc.width > IMAGEWIDTH - 1 )
rectTempLargeSrc.width = IMAGEWIDTH - rectTempLargeSrc.x - 1;
if( rectTempLargeSrc.y < 0 )
rectTempLargeSrc.y = 0;
if( rectTempLargeSrc.y + rectTempLargeSrc.height > IMAGEHEIGHT - 1 )
rectTempLargeSrc.height = IMAGEHEIGHT - rectTempLargeSrc.y - 1;
// cannot set the src image's ROI from this function, not sure why, so use a temp image instead...
tempImage1 = cvCloneImage( src );
cvSetImageROI( tempImage1, rectTempLargeSrc );

result = cvCreateImage(
cvSize( (rectTempLargeSrc.width - rectTempTarg.width + 1), (rectTempLargeSrc.height - rectTempTarg.height + 1) ),
IPL_DEPTH_32F, 1
);
cvMatchTemplate( tempImage1, temp, result, iMatchTempParams[TEMPLATETYPE] ); // match on regular images, but only at specific locations.

if( (iMatchTempParams[TEMPLATETYPE] == CV_TM_SQDIFF) || (iMatchTempParams[TEMPLATETYPE] == CV_TM_SQDIFF_NORMED) ) // use the minima from result
{
MinLoc( result, score, loc );
score = 100 - score*100;
}
else // use the maxima from result
{
MaxLoc( result, score, loc );
score *= 100;
}
// transforms coords in result image back to searched image
iX = loc.x + rectTempLargeSrc.x + (rectTempTarg.width - 1)/2;
iY = loc.y + rectTempLargeSrc.y + (rectTempTarg.height - 1)/2;
if( score >= dTemplateScoreThresh ) // above or equal to score threshold, return to calling function
{
loc.x = iX;
loc.y = iY;
break; // break loop, target found
}
}

// release temporary images back to heap
cvReleaseImage( &pyrSrcImage );
cvReleaseImage( &pyrTargImage );
cvReleaseImage( &tempImage1 );
cvReleaseImage( &tempImage2 );
cvReleaseImage( &result );
}

// for some reason, cvMinMaxLoc crashed my application, so I implemented my own, a MaxLoc and a MinLoc
void MaxLoc( IplImage *image, double &max, CvPoint &location )
{
float* data;
int step;

CvSize size;
int x, y;

cvGetRawData( image, (uchar**)&data, &step, &size );
step /= sizeof(data[0]);

max = 0;
location.x = 0;
location.y = 0;

for( y = 0; y < size.height; y++, data += step )
for( x = 0; x < size.width; x++ )
{
if( data[x] > max )
{
max = (double)data[x];
location.x = x;
location.y = y;
}
}
}

void MinLoc( IplImage *image, double &min, CvPoint &location )
{
float* data;
int step;

CvSize size;
int x, y;

cvGetRawData( image, (uchar**)&data, &step, &size );
step /= sizeof(data[0]);

min = (double)data[0];
location.x = 0;
location.y = 0;

for( y = 0; y < size.height; y++, data += step )
for( x = 0; x < size.width; x++ )
{
if( data[x] < min )
{
min = (double)data[x];
location.x = x;
location.y = y;
}
}
}

// the next two functions will find multiple maxima and minima points, in order from largest/smallest to smallest/largest
void MultipleMaxLoc( IplImage *image, CvPoint location[], int iNumPoints )
{
float* data;
int step;

CvSize size;
int x, y, i, j;

double dMax[iNumPoints];

cvGetRawData( image, (uchar**)&data, &step, &size );
step /= sizeof(data[0]);

for( i = 0; i < iNumPoints; i++ )
dMax[i] = 0;

for( y = 0; y < size.height; y++, data += step )
{
for( x = 0; x < size.width; x++ )
{
for( i = 0; i < iNumPoints; i++ )
{
if( data[x] >= dMax[i] )
{
for( j = iNumPoints - 1; j > i; j-- )
{
dMax[j] = dMax[j-1];
location[j] = location[j-1];
}
dMax[i] = (double)data[x];
location[i].x = x;
location[i].y = y;
break;
}
}
}
}
}

void MultipleMinLoc( IplImage *image, CvPoint location[], int iNumPoints )
{
float* data;
int step;

CvSize size;
int x, y, i, j;

double dMin[iNumPoints];

cvGetRawData( image, (uchar**)&data, &step, &size );
step /= sizeof(data[0]);

for( i = 0; i < iNumPoints; i++ )
dMin[i] = 1;

for( y = 0; y < size.height; y++, data += step )
{
for( x = 0; x < size.width; x++ )
{
for( i = 0; i < iNumPoints; i++ )
{
if( data[x] <= dMin[i] )
{
for( j = iNumPoints - 1; j > i; j-- )
{
dMin[j] = dMin[j-1];
location[j] = location[j-1];
}
dMin[i] = (double)data[x];
location[i].x = x;
location[i].y = y;
break;
}
}
}
}
}





Write to AVI:




//----------------------------------------------------------------------------
// Example for generation of avi-files with OpenCV V4.0beta
//
// after starting the program you have to chose a codec (windows only)
// now you can place circles with left mouse button on the window,
// each frame is written to file "AviTest.avi" in the program directory,
// exit program by pressing any key
//
// Copyright (C) V0.1 3.11.2004 Frank Reifegerste
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this program; if not, write to the Free
// Software Foundation, Inc., 59 Temple Place, Suite 330,
// Boston, MA 02111-1307, USA.
//----------------------------------------------------------------------------

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

char img_name[]="AviTest";
IplImage* img=0;
CvCapture* capture=0;
CvVideoWriter* writer=0;

void on_mouse(int event, int x, int y, int flags) {

if (event==CV_EVENT_LBUTTONDOWN) {
cvCircle(img, cvPoint(x,y), 3, CV_RGB(255,64,0), 2, 8, 0);
cvShowImage(img_name, img);
cvWriteFrame(writer, img);
}
}

void main(void) {

// "init"
img=cvCreateImage(cvSize(256, 256), IPL_DEPTH_8U, 3);
cvSetZero(img);
cvNamedWindow(img_name, HG_AUTOSIZE);
cvShowImage(img_name, img);
writer=cvCreateVideoWriter("AviTest.avi", -1, 25, cvGetSize(img));

// "loop"
cvSetMouseCallback(img_name, on_mouse);
cvWaitKey(0);

// "cleanup"
cvReleaseVideoWriter(&writer);
cvDestroyAllWindows();
cvReleaseImage(&img);
}





Playing an avi file, capturing from usb cameras,snapshot:

No comments:

Post a Comment