SURF Souce Code (Part-1)

When you install openCV, openCV samples folder also gets installed. The samples will be present in your InstallationDirectory/samples/C. For me it's present in OpenCV-2.1.0/samples/c.This folder contains the sample codes of many good openCV programmes that can be used for a wide variety of purposes. One more thing is that, it also contains the compiled object files along with the source code for each programme. The programme , we will be looking is find_obj.cpp and the compiled code will be with the name find_obj. This programme uses SURF to do an object detection. The original code, written by Liu, is modified by me to give the below code. Note that the comments made by me, start with Dileep:

/*
 * A Demo to OpenCV Implementation of SURF
 * Further Information Refer to "SURF: Speed-Up Robust Feature"
 * Author: Liu Liu
 * liuliu.1987+opencv@gmail.com
 * Modified by : http://www.opencvuser.blogspot.com
 * Modifying Author : Dileep Kumar Kotha
 */

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

#include <iostream>
#include <vector>

using namespace std;

static double dis=0;//For calculating the average descriptor distance
// define whether to use approximate nearest-neighbor search
//#define USE_FLANN


IplImage *image = 0;

double
compareSURFDescriptors( const float* d1, const float* d2, double best, int length )
{
    double total_cost = 0;
    assert( length % 4 == 0 );
    for( int i = 0; i < length; i += 4 )
    {
        double t0 = d1[i] - d2[i];
        double t1 = d1[i+1] - d2[i+1];
        double t2 = d1[i+2] - d2[i+2];
        double t3 = d1[i+3] - d2[i+3];
        total_cost += t0*t0 + t1*t1 + t2*t2 + t3*t3;
/*
We are sending a total cost, that's slightly greater or smaller than the best 

  */
      if( total_cost > best )
            break;
    }
    return total_cost;
}


int
naiveNearestNeighbor( const float* vec, int laplacian,
                      const CvSeq* model_keypoints,
                      const CvSeq* model_descriptors )
{
    int length = (int)(model_descriptors->elem_size/sizeof(float));
    int i, neighbor = -1;
    double d, dist1 = 1e6, dist2 = 1e6;
    CvSeqReader reader, kreader;
    cvStartReadSeq( model_keypoints, &kreader, 0 );
    cvStartReadSeq( model_descriptors, &reader, 0 );

    for( i = 0; i < model_descriptors->total; i++ )
    {
        const CvSURFPoint* kp = (const CvSURFPoint*)kreader.ptr;
        const float* mvec = (const float*)reader.ptr;
     CV_NEXT_SEQ_ELEM( kreader.seq->elem_size, kreader );
        CV_NEXT_SEQ_ELEM( reader.seq->elem_size, reader );
        if( laplacian != kp->laplacian )
            continue;
        d = compareSURFDescriptors( vec, mvec, dist2, length );

        if( d < dist1 )
        {
            dist2 = dist1;
            dist1 = d;
            neighbor = i;
        }
        else if ( d < dist2 )
            dist2 = d;
    }
dis=dis+dist1;

    if ( dist1 < 0.6*dist2 )
        return neighbor;
    return -1;
}

void
findPairs( const CvSeq* objectKeypoints, const CvSeq* objectDescriptors,
           const CvSeq* imageKeypoints, const CvSeq* imageDescriptors, vector<int>& ptpairs )
{ 
    int i;
    CvSeqReader reader, kreader;
    cvStartReadSeq( objectKeypoints, &kreader );
    cvStartReadSeq( objectDescriptors, &reader );
    ptpairs.clear();

    for( i = 0; i < objectDescriptors->total; i++ )
    {
        const CvSURFPoint* kp = (const CvSURFPoint*)kreader.ptr;
        const float* descriptor = (const float*)reader.ptr;
        CV_NEXT_SEQ_ELEM( kreader.seq->elem_size, kreader );
        CV_NEXT_SEQ_ELEM( reader.seq->elem_size, reader );
        int nearest_neighbor = naiveNearestNeighbor( descriptor, kp->laplacian, imageKeypoints, imageDescriptors);
        if( nearest_neighbor >= 0 )
        {
            ptpairs.push_back(i);
            ptpairs.push_back(nearest_neighbor);
        }
    }

printf("\n%lf\n",(dis/objectDescriptors->total));////Dileep:Here's where I am outputting the distance between the images
/*Dileep: If you are using this for recognition, write this distance to a file along with the name of the image you are matching against. After doing this for several images, you can then sort them in ascending order to find the best possible match - the one with the smallest distance. Here, I am outputting the distance to stdout
*/
}
////Dileep:I am commenting the below one since it's of flann method and what ever the method we choose to find distance, the result is the same
/*
void
flannFindPairs( const CvSeq*, const CvSeq* objectDescriptors,
           const CvSeq*, const CvSeq* imageDescriptors, vector<int>& ptpairs )
{
 int length = (int)(objectDescriptors->elem_size/sizeof(float));

    cv::Mat m_object(objectDescriptors->total, length, CV_32F);
 cv::Mat m_image(imageDescriptors->total, length, CV_32F);


 // copy descriptors
    CvSeqReader obj_reader;
 float* obj_ptr = m_object.ptr<float>(0);
    cvStartReadSeq( objectDescriptors, &obj_reader );
    for(int i = 0; i < objectDescriptors->total; i++ )
    {
        const float* descriptor = (const float*)obj_reader.ptr;
        CV_NEXT_SEQ_ELEM( obj_reader.seq->elem_size, obj_reader );
        memcpy(obj_ptr, descriptor, length*sizeof(float));
        obj_ptr += length;
    }
    CvSeqReader img_reader;
 float* img_ptr = m_image.ptr<float>(0);
    cvStartReadSeq( imageDescriptors, &img_reader );
    for(int i = 0; i < imageDescriptors->total; i++ )
    {
        const float* descriptor = (const float*)img_reader.ptr;
        CV_NEXT_SEQ_ELEM( img_reader.seq->elem_size, img_reader );
        memcpy(img_ptr, descriptor, length*sizeof(float));
        img_ptr += length;
    }

    // find nearest neighbors using FLANN
    cv::Mat m_indices(objectDescriptors->total, 2, CV_32S);
    cv::Mat m_dists(objectDescriptors->total, 2, CV_32F);
    cv::flann::Index flann_index(m_image, cv::flann::KDTreeIndexParams(4));  // using 4 randomized kdtrees
    flann_index.knnSearch(m_object, m_indices, m_dists, 2, cv::flann::SearchParams(64) ); // maximum number of leafs checked

    int* indices_ptr = m_indices.ptr<int>(0);
    float* dists_ptr = m_dists.ptr<float>(0);
    for (int i=0;i<m_indices.rows;++i) {
     if (dists_ptr[2*i]<0.6*dists_ptr[2*i+1]) {
      ptpairs.push_back(i);
      ptpairs.push_back(indices_ptr[2*i]);
     }
    }
}


// a rough implementation for object location 
int
locatePlanarObject( const CvSeq* objectKeypoints, const CvSeq* objectDescriptors,
                    const CvSeq* imageKeypoints, const CvSeq* imageDescriptors,
                    const CvPoint src_corners[4], CvPoint dst_corners[4] )
{
    double h[9];
    CvMat _h = cvMat(3, 3, CV_64F, h);
    vector<int> ptpairs;
    vector<CvPoint2D32f> pt1, pt2;
    CvMat _pt1, _pt2;
    int i, n;

#ifdef USE_FLANN
    flannFindPairs( objectKeypoints, objectDescriptors, imageKeypoints, imageDescriptors, ptpairs );
#else
    findPairs( objectKeypoints, objectDescriptors, imageKeypoints, imageDescriptors, ptpairs );
#endif

    n = ptpairs.size()/2;
    if( n < 4 )
        return 0;

    pt1.resize(n);
    pt2.resize(n);
    for( i = 0; i < n; i++ )
    {
        pt1[i] = ((CvSURFPoint*)cvGetSeqElem(objectKeypoints,ptpairs[i*2]))->pt;
        pt2[i] = ((CvSURFPoint*)cvGetSeqElem(imageKeypoints,ptpairs[i*2+1]))->pt;
    }

    _pt1 = cvMat(1, n, CV_32FC2, &pt1[0] );
    _pt2 = cvMat(1, n, CV_32FC2, &pt2[0] );
    if( !cvFindHomography( &_pt1, &_pt2, &_h, CV_RANSAC, 5 ))
        return 0;

    for( i = 0; i < 4; i++ )
    {
        double x = src_corners[i].x, y = src_corners[i].y;
        double Z = 1./(h[6]*x + h[7]*y + h[8]);
        double X = (h[0]*x + h[1]*y + h[2])*Z;
        double Y = (h[3]*x + h[4]*y + h[5])*Z;
        dst_corners[i] = cvPoint(cvRound(X), cvRound(Y));
    }

    return 1;
}
*/

int main(int argc, char** argv)
{
    const char* object_filename = argc == 3 ? argv[1] : "box.png";
    const char* scene_filename = argc == 3 ? argv[2] : "box_in_scene.png";

    CvMemStorage* storage = cvCreateMemStorage(0);

    cvNamedWindow("Object", 1);
    cvNamedWindow("Object Correspond", 1);

    static CvScalar colors[] = 
    {
        {{0,0,255}},
        {{0,128,255}},
        {{0,255,255}},
        {{0,255,0}},
        {{255,128,0}},
        {{255,255,0}},
        {{255,0,0}},
        {{255,0,255}},
        {{255,255,255}}
    };

    IplImage* object = cvLoadImage( object_filename, CV_LOAD_IMAGE_GRAYSCALE );
    IplImage* image = cvLoadImage( scene_filename, CV_LOAD_IMAGE_GRAYSCALE );
    if( !object || !image )
    {
        fprintf( stderr, "Can not load %s and/or %s\n"
            "Usage: find_obj [<object_filename> <scene_filename>]\n",
            object_filename, scene_filename );
        exit(-1);
    }
    IplImage* object_color = cvCreateImage(cvGetSize(object), 8, 3);
    cvCvtColor( object, object_color, CV_GRAY2BGR );
    
    CvSeq *objectKeypoints = 0, *objectDescriptors = 0;
    CvSeq *imageKeypoints = 0, *imageDescriptors = 0;
    int i;
    CvSURFParams params = cvSURFParams(500, 1);

    double tt = (double)cvGetTickCount();
    cvExtractSURF( object, 0, &objectKeypoints, &objectDescriptors, storage, params );
    printf("Object Descriptors: %d\n", objectDescriptors->total);
    cvExtractSURF( image, 0, &imageKeypoints, &imageDescriptors, storage, params );
    printf("Image Descriptors: %d\n", imageDescriptors->total);
    tt = (double)cvGetTickCount() - tt;
    printf( "Extraction time = %gms\n", tt/(cvGetTickFrequency()*1000.));
    CvPoint src_corners[4] = {{0,0}, {object->width,0}, {object->width, object->height}, {0, object->height}};
    CvPoint dst_corners[4];
    IplImage* correspond = cvCreateImage( cvSize(image->width, object->height+image->height), 8, 1 );
    cvSetImageROI( correspond, cvRect( 0, 0, object->width, object->height ) );
    cvCopy( object, correspond );
    cvSetImageROI( correspond, cvRect( 0, object->height, correspond->width, correspond->height ) );
    cvCopy( image, correspond );
    cvResetImageROI( correspond );

#ifdef USE_FLANN
    printf("Using approximate nearest neighbor search\n");
#endif
/*
    if( locatePlanarObject( objectKeypoints, objectDescriptors, imageKeypoints,
        imageDescriptors, src_corners, dst_corners ))
    {
        for( i = 0; i < 4; i++ )
        {
            CvPoint r1 = dst_corners[i%4];
            CvPoint r2 = dst_corners[(i+1)%4];
            cvLine( correspond, cvPoint(r1.x, r1.y+object->height ),
                cvPoint(r2.x, r2.y+object->height ), colors[8] );
        }
    }
*/


    vector<int> ptpairs;
#ifdef USE_FLANN
    flannFindPairs( objectKeypoints, objectDescriptors, imageKeypoints, imageDescriptors, ptpairs );
#else
    findPairs( objectKeypoints, objectDescriptors, imageKeypoints, imageDescriptors, ptpairs );
#endif

////Dileep:It is used to draw the the lines and rectangles in the windows that display images. If you want just the distance, you can comment the whole 
////below code
    for( i = 0; i < (int)ptpairs.size(); i += 2 )
    {
        CvSURFPoint* r1 = (CvSURFPoint*)cvGetSeqElem( objectKeypoints, ptpairs[i] );
        CvSURFPoint* r2 = (CvSURFPoint*)cvGetSeqElem( imageKeypoints, ptpairs[i+1] );
        cvLine( correspond, cvPointFrom32f(r1->pt),
            cvPoint(cvRound(r2->pt.x), cvRound(r2->pt.y+object->height)), colors[8] );
    }

    cvShowImage( "Object Correspond", correspond );
    for( i = 0; i < objectKeypoints->total; i++ )
    {
        CvSURFPoint* r = (CvSURFPoint*)cvGetSeqElem( objectKeypoints, i );
        CvPoint center;
        int radius;
        center.x = cvRound(r->pt.x);
        center.y = cvRound(r->pt.y);
        radius = cvRound(r->size*1.2/9.*2);
        cvCircle( object_color, center, radius, colors[0], 1, 8, 0 );
    }
    cvShowImage( "Object", object_color );

    cvWaitKey(0);
//cvSaveImage("Object_1.png",correspond);
//cvSaveImage("Object_2.png",object_color);

    cvDestroyWindow("Object");
    cvDestroyWindow("Object SURF");
    cvDestroyWindow("Object Correspond");

    return 0;
}

There are enough comments in it, explaining what each part does. compile it. If you compile it to the object file find_obj, the command below works.

./find_obj

Otherwise, replace it with a.out. Also, copy the two images in the samples folder named box.png and box_in_scene.png into the folder where you run the above command.

Now for ./find_obj Since we are not supplying arguements, it will take the default box.png and box_in_scene.png and tries to find the first object inside the second object. The below figure appears.

What's actually happening here is object detection. But I included a "dis" variable and also printing it to standard ouput, so that you will also know the average distance of all the descriptors. If you want, you can keep two photographs of the same person with different facial expressions in the same folder and supply them as arg1 and arg2 (in which case you will get distance as zero, ofcourse :P)

./findobj arg1 arg2 

If we keep on changing the second arguement(the image we are supplying as arg2), we can actually use it for recognition. Then the one with the least distance is the best possible match for the first argument (the image we are supplying as arg1). In the next post, I will strip all the unnecessary components of this code and make this usable for recognition. You can try to do it yourself.

CSU - Face Evaluation System

Guess, you people have unzipped the CSU face evaluation system, about which I explained in the previous post. After unzipping, consider the folder in which we unzipped is called Main folder.

Inside the Main folder, there will be a README file, that instructs how to install the CSU face evaluation system. Do it, and make sure it happens with out any errors. If there is an error, it is related to some package absense. Look through the error carefully and install the missing packages.

After installing, with in that README file, there are some tests related to scraps data which is present in the Mainfolder/data/csuScrapShots/source/pgm folder. These are the images from the year book of 1925 of CSU. So we can perform initial tests of PCA, LDA, Bayesian and EBGM approaches using the commands listed in the README.

Also, with in that README file, if you have FERET database, there are tests related to grey FERET database. If you don't have a FERET database, you can try to get it online searching in google. I would have given you, but it's redistribution is prohibited.

After running the tests on either of them or any one of them, you can view the results in Mainfolder/results folder.

The UsersGuide pdf document, that is present in the main folder, explains you everything you need to know, to get started using that system. It is like a bible for CSU face evaluation system.

In the main folder, the src folder contains C-programmes related to various executables that we use while we are running tests related to biometric face recognition.

The data folder is the epi centre of all the data that we use in running the tests. The normalised images are also stored here.

The distances folder contains the distance metrics related to PCA, LDA and other approaches. Carefully observe these distance files, relating it to the data. It is because, if you build a face recognition system, you have to make the distance files similar to the ones present here and keep them in a folder just like PCA, LDA and all and trigger the comparison scripts.

The final results are stored in results folder. The training data, which is created when we are doing PCA, LDA or Bayesian training is stored in train folder. 

This is it guys, I have shown you a way into biometric face recognition. Now it's up to you to figure out. If you need any help, leave the comments, I am always ready to help. If I think there is a need for extra post, I will definitely do it. 

But I don't want you to stick to my blog for your entire career. That is the reason I kept a time frame.

Life has to go on. Hit the "+1" on right side bar and say good bye.

Review and what needs to be done - Biometric Face recognition system

We talked about haar training in the previous post. Let's see how far we have come till date

1. Installed opencv
2. Did some good exercises related to openCV intro programming
3. Created eye and face detectors using haar cascade classifiers
4. Learnt how to create an xml file with haar training that can be used to create an object detector

Now let's divulge into our main topic of biometric face recognition. In one of my previous posts, I told you about Biometric face recognition, it's significance and the contests related to it.

The reason I made you learn the creating of face detector due to the fact that the first step in face recognition is detecting the face in a back ground, like the one  shown below

Detecting face is just the beginning. The next step is to normalise the face, so that only the face part is cut. Then we will apply histogram equilisation to make the face invariant to brightness and contrast. Finally, we rotate the face, so that the eye coordinates remain on same height. This is needed, since we will be comparing photos for face recognition and if the guy tilts the head, his nose may be taken as one of the eyes, by mistake by the recognition system. In the end, the piece that we actually need looks like this

The face recognition system compares this face, with the faces like this to recognise people. Incidentally, there is a savior for us. It's the CSU face evaluation system. Just google for the name and download the zipped file. The beauty of CSU face evaluation system is that, you supply the image containing face, along with any back ground, with the eye center coordinates, and it returns you the face which is detected, normalised, equalised and rotated.

The only thing, that we need to supply it, is the eye center coordinates of the image i.e., the x and y coordinates of left eye center (eye ball center) and the same of the right eye. To get these coordinates, I used the eye detector, which I made you learn in the previous posts. Since, it draws a square around the eye, finding the center of that square is no big task. Will explain it to you in future posts, and the next post will be on sunday ( 28/08/11). For now, just download the CSU face evaluation system and try to decipher and also carefully go through it's documentation.

Face detector

Today, let's take an important step towards face recognition - face detection

First, let me tell you the difference between both.Face detection is just telling whether there is a face or not in the given image, on the other hand, face recognition is telling to which person that face belongs.

This is the code for face detection using your webcam.Actually, this is not exclusively my code, I hacked it from the code given by Nashruddin which inturn was hacked from the openCV samples.Any way, that's what makes the open source software better and better forever :)

Here's the code snippet

//Programme to detect faces through the webcam using the haar cascade
//Links Used:http://nashruddin.com/OpenCV_Face_Detection

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

CvHaarClassifierCascade *cascade;
CvMemStorage *Membuffer;

void detectfaces(IplImage *frame)
{
int i;
CvSeq *faces=cvHaarDetectObjects(frame,cascade,Membuffer,1.1,3,0,cvSize(30,30));//Maximum 3 neighbourhood images and the last cvsize gives minimum size of face
for(i=0;i<(faces?faces->total:0);i++)
{CvRect *r=(CvRect *)cvGetSeqElem(faces,i);
cvRectangle(frame,cvPoint(r->x,r->y),cvPoint(r->x+r->width,r->y+r->height),CV_RGB(255,0,0),1,8,0);

//Draws a rectangle with two points given with color of red and thickness as 8 and line type - 1
}

cvShowImage("Video",frame);


}


int main(int argc,char *argv[])

{IplImage *frame;
CvCapture *capture;
int key;
char filename[]="haarcascade_frontalface_alt.xml";//This is the cascading file that is needed for face detector it is generally present in if openCV is your installation folder, it is present in openCV/data/haarcascades folder, don't forget to paste the haarcascade file in the same folder as your program before compiling



cascade=(CvHaarClassifierCascade *)cvLoad(filename,0,0,0);

//Loading the haar... file

Membuffer=cvCreateMemStorage(0);//Allocating the default memory for image (64K at Present)

capture=cvCaptureFromCAM(0);//Capture the image from cam with index 0
//Note that if you are using a Laptop with an external webcam it has an index 1 since the Lappie cam's index is 0

assert(cascade && Membuffer && capture);//To make sure that everything needed is always available
cvNamedWindow("Video",1);

while(key!='q')

{frame=cvQueryFrame(capture);
if(!frame)
break;

//cvFlip(frame,frame,-1);//If you are using openCV on windows, uncomment this line
frame->origin=0;



detectfaces(frame);
key=cvWaitKey(10);//Wait for 10 milli seconds, the user may press 'q'
}
cvReleaseCapture(&capture);
cvDestroyWindow("Video");
cvReleaseHaarClassifierCascade(&cascade);
cvReleaseMemStorage(&Membuffer);
}

For your convenience, I have added the comments in the code above.Don't bother if you feel lazy to copy the content.I kept the above program and the haar cascade xml file that you need to use in the link below.




I know, some of you are even lazy to, compile the code, so I have included a Linux executable in the above download link.

And this is a bonus, a youtube video of me with my face detector.I shot the video with poor lighting conditions and a VGA cam, that's why not a good one (I look 10 times more handsome), but serves the purpose

Face recognition

Today, let me tell you about the importance of face recognition and why is it the most sought out research in the present decade.You may have already been using the "iphoto" from Apple, which lets you name people once and then it automatically searches through your entire photo library and names them.That's face recognition.Let me tell you something more.What if it names wrong ?

Credit: Simson Garfinkel and Beth Rosenberg

Here's the greatness of Apple, it updates it mathematical model and becomes more robust.Some times it may ask you doubts also, like a small child learning to crawl :)

Google's picasa also offers, I hadn't tested it, but reviews say it is in no way the nearest competitor to Apple.You may have already heard of facebook auto tagging feature, which is a very great idea, but facebook should not have automatically enabled that feature in all accounts.And the latest news is that Google's trying to take advantage of it.It's former CEO Eric Schmidt appealed to the US government that it's a threat to national security.You may have already heard of facebook hiring a private agency to launch "article" attack on google.That's a wholly different story let's come back to our topic.

Apart from fun, actually the main reason why face recognition had to be invented and to be moved forward like a crusade is the security threats.Reports say that after the 9/11 attacks, the US government has been heavily investing on this, so that the technology can be applied in airports, railway stations and other public places to detect terrorists.But whenever the terrorist grows some beard or changes hair style or face color, it fails.Although recently more scientists claim that they have discovered the best technologies, there is no clear winner in this arena, due to the diversity in the testing procedures.Some facial recognition technologies use one image per person, while others need more than four images per person, and some need facial landmark locations accurately.In order to over come this a common facial recognition test need to be conducted using the same data for all.

This need is discovered by the Us Government early on and they have carried out these tests for every four years or so.They started the tests in 1993 and successively conducted on 1993, 1994, 1996, 2000.Recently they started  a new format for testing called "Face Recognition Grand Challenge" (FRGC).The most recent one is the FRVT 2006.They may conduct another one in 2012

 If  your college or university wants to participate in that evaluation, you can visit their home page.Below is the link for it

http://www.frvt.org/FRGC/

More about face recognition later on.

I hope you are doing well with the assignments, tommorrow I will post all the code snippets for the assignments I gave you.By the end of this month you will be pursuing the research on face recognition I assure you.If you are a first timer, visiting this blog,  you can view the archives in the right hand side.