## Thursday, November 11, 2004

### OpenCV codes

[Opencv] C++ code for matched filter:

/*Author: Tristen GeorgiouEmail: tristen_georgiou@hotmail.comDate: August 5, 2004This 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 returnis 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 mbOS: Red Hat Linux 7.3GUI: wxWindowsWhen 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 andthe 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 calculationsapproaches 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 increaseperformance significantly.)2. us cvPyrDown function to downsample the image i times3. perform a cvMatchTemplate on the downsampled images4. 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 image6. 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 codeiMatchTempParams[TEMPLATETYPE] = CV_TM_CCORR_NORMEDimgSize.width = 640imgSize.height = 480*//* Function FastMatchTemplatesrc - source image, where search takes placetemp - template image, image we are searching fornumLocations - 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 matchloc - 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 MinLocvoid 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/largestvoid 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: