Saturday, August 8, 2009

Object Detection Using opencv I - Integral Histogram for fast Calculation of HOG Features

Histograms of Oriented Gradients or HOG features in combination with a support vector machine have been successfully used for object Detection (most popularly pedestrian detection).
An Integral Histogram representation can be used for fast calculation of Histograms of Oriented Gradients over arbitrary rectangular regions of the image. The idea of an integral histogram is analogous to that of an integral image, used by viola and jones for fast calculation of haar features for face detection. Mathematically,



where b represents the bin number of the histogram. This way the calculation of hog over any arbitrary rectangle in the image requires just 4*bins number of array references. For more details on integral histogram representation, please refer,

Integral Histogram

The following demonstrates how such integral histogram can be calculated from an image and used for the calculation of hog features using the opencv computer vision library :

/*Function to calculate the integral histogram*/

IplImage** calculateIntegralHOG(IplImage* in)

{

/*Convert the input image to grayscale*/

IplImage* img_gray = cvCreateImage(cvGetSize(in), IPL_DEPTH_8U,1);
cvCvtColor(in, img_gray, CV_BGR2GRAY);
cvEqualizeHist(img_gray,img_gray);

/* Calculate the derivates of the grayscale image in the x and y directions using a sobel operator and obtain 2 gradient images for the x and y directions*/

IplImage *xsobel, *ysobel;
xsobel = doSobel(img_gray, 1, 0, 3);
ysobel = doSobel(img_gray, 0, 1, 3);
cvReleaseImage(&img_gray);


/* Create an array of 9 images (9 because I assume bin size 20 degrees and unsigned gradient ( 180/20 = 9), one for each bin which will have zeroes for all pixels, except for the pixels in the original image for which the gradient values correspond to the particular bin. These will be referred to as bin images. These bin images will be then used to calculate the integral histogram, which will quicken the calculation of HOG descriptors */

IplImage** bins = (IplImage**) malloc(9 * sizeof(IplImage*));
for (int i = 0; i < 9 ; i++) {
bins[i] = cvCreateImage(cvGetSize(in), IPL_DEPTH_32F,1);
cvSetZero(bins[i]);
}


/* Create an array of 9 images ( note the dimensions of the image, the cvIntegral() function requires the size to be that), to store the integral images calculated from the above bin images. These 9 integral images together constitute the integral histogram */

IplImage** integrals = (IplImage**) malloc(9 * sizeof(IplImage*)); for (int i = 0; i < 9 ; i++) {
integrals[i] = cvCreateImage(cvSize(in->width + 1, in->height + 1),
IPL_DEPTH_64F,1);
}

/* Calculate the bin images. The magnitude and orientation of the gradient at each pixel is calculated using the xsobel and ysobel images.{Magnitude = sqrt(sq(xsobel) + sq(ysobel) ), gradient = itan (ysobel/xsobel) }. Then according to the orientation of the gradient, the value of the corresponding pixel in the corresponding image is set */


int x, y;
float temp_gradient, temp_magnitude;
for (y = 0; y <in->height; y++) {

/* ptr1 and ptr2 point to beginning of the current row in the xsobel and ysobel images respectively. ptrs[i] point to the beginning of the current rows in the bin images */

float* ptr1 = (float*) (xsobel->imageData + y * (xsobel->widthStep));
float* ptr2 = (float*) (ysobel->imageData + y * (ysobel->widthStep));
float** ptrs = (float**) malloc(9 * sizeof(float*));
for (int i = 0; i < 9 ;i++){
ptrs[i] = (float*) (bins[i]->imageData + y * (bins[i]->widthStep));
}

/*For every pixel in a row gradient orientation and magnitude are calculated and corresponding values set for the bin images. */

for (x = 0; x <in->width; x++) {

/* if the xsobel derivative is zero for a pixel, a small value is added to it, to avoid division by zero. atan returns values in radians, which on being converted to degrees, correspond to values between -90 and 90 degrees. 90 is added to each orientation, to shift the orientation values range from {-90-90} to {0-180}. This is just a matter of convention. {-90-90} values can also be used for the calculation. */

if (ptr1[x] == 0){
temp_gradient = ((atan(ptr2[x] / (ptr1[x] + 0.00001))) * (180/ PI)) + 90;
}
else{
temp_gradient = ((atan(ptr2[x] / ptr1[x])) * (180 / PI)) + 90;
}
temp_magnitude = sqrt((ptr1[x] * ptr1[x]) + (ptr2[x] * ptr2[x]));

/*The bin image is selected according to the gradient values. The corresponding pixel value is made equal to the gradient magnitude at that pixel in the corresponding bin image */

if (temp_gradient <= 20) {

ptrs[0][x] = temp_magnitude;
}
else if (temp_gradient <= 40) {
ptrs[1][x] = temp_magnitude;
}
else if (temp_gradient <= 60) {

ptrs[2][x] = temp_magnitude;
}
else if (temp_gradient <= 80) {

ptrs[3][x] = temp_magnitude;
}
else if (temp_gradient <= 100) {

ptrs[4][x] = temp_magnitude;
}
else if (temp_gradient <= 120) {

ptrs[5][x] = temp_magnitude;
}
else if (temp_gradient <= 140) {

ptrs[6][x] = temp_magnitude;
}
else if (temp_gradient <= 160) {

ptrs[7][x] = temp_magnitude;
}
else {

ptrs[8][x] = temp_magnitude;
}
}
}

cvReleaseImage(&xsobel);
cvReleaseImage(&ysobel);

/*Integral images for each of the bin images are calculated*/

for (int i = 0; i <9 ; i++){
cvIntegral(bins[i], integrals[i]);
}

for (int i = 0; i <9 ; i++){
cvReleaseImage(&bins[i]);
}

/*The function returns an array of 9 images which consitute the integral histogram*/

return (integrals);

}


The following demonstrates how the integral histogram calculated using the above function can be used to calculate the histogram of oriented gradients for any rectangular region in the image:

/* The following function takes as input the rectangular cell for which the histogram of oriented gradients has to be calculated, a matrix hog_cell of dimensions 1x9 to store the bin values for the histogram, the integral histogram, and the normalization scheme to be used. No normalization is done if normalization = -1 */


void calculateHOG_rect(CvRect cell, CvMat* hog_cell,
IplImage** integrals, int normalization) {


/* Calculate the bin values for each of the bin of the histogram one by one */

for (int i = 0; i < 9 ; i++){

float a =((double*)(integrals[i]->imageData + (cell.y)
* (integrals[i]->widthStep)))[cell.x];

float b = ((double*) (integrals[i]->imageData + (cell.y + cell.height)
* (integrals[i]->widthStep)))[cell.x + cell.width];
float c = ((double*) (integrals[i]->imageData + (cell.y)
* (integrals[i]->widthStep)))[cell.x + cell.width];
float d = ((double*) (integrals[i]->imageData + (cell.y + cell.height)
* (integrals[i]->widthStep)))[cell.x];

((float*) hog_cell->data.fl)[i] = (a + b) - (c + d);

}


/*Normalize the matrix*/
if (normalization != -1){

cvNormalize(hog_cell, hog_cell, 1, 0, normalization);
}

}



I will describe how the HOG features for pedestrian detection can be obtained using the above framework and how an svm can be trained for such features for pedestrian detection in a later post.





29 comments:

  1. what is the frame rate of this code? thanks ;)

    ah! i'm working the samen project... pedestrian detection..

    ReplyDelete
  2. it works at around 5 frames/second for a 320x240 video

    ReplyDelete
  3. I am looking for that later post.Hope u can provide it soon, and thank btw really nice of u to share and explain this part

    ReplyDelete
  4. Thanks!
    I will post the remaining part soon

    FYI : opencv 2 has an implementation of hog features

    ReplyDelete
  5. hey can you share ur nxt post. it wil help us to do our project. thnx

    ReplyDelete
  6. A follow up to this post can be viewed here

    ReplyDelete
  7. Nice job! very useful. Just a little comment. For calculating the sobel image, i am not sure if you used your own func doSobel, but i didn't find in openCV the same function; instead, i found cvSobel

    ReplyDelete
  8. can you provide me any idea for detecting a ball in my video using your code?????

    ReplyDelete
  9. Is a histogram equalization step necessary? I thought the normalization scheme achieves the same result. Am more concerned about this because I happen to use images with 32F depth and cvEqualizeHist doesn't support that. Let me know.

    Thanks!

    ReplyDelete
  10. well there is some prob with the code i guess... did u really run and check the code... m not sure but u are doing arithmatic actually with pointers(address where the value is saved) instead of the value of the pointers it actually points to....
    temp_gradient = ((atan(ptr2[x] / ptr1[x])) * (180 / PI)) + 90);.............?????? could you plz explain this??? when i ran and printed the values its showing either NAN or INF do check once again

    regards

    ReplyDelete
  11. For the benefit of whoever is reading this, the doSobel seems to be custom code written by Saurabh. You can use the following code to calculacate the sobel.

    IplImage* HogFeatureExtractor::doSobel(IplImage* src, int dx, int dy, int apertureSize) {
    CvSize size = cvGetSize(src);

    IplImage* df = cvCreateImage(size, IPL_DEPTH_16S,1);
    cvSobel(src, df, dx, dy, apertureSize);

    IplImage* dest = cvCreateImage(size, IPL_DEPTH_8U,1);
    cvConvertScaleAbs(df,dest, 1, 0);

    cvReleaseImage(&df);
    return dest;
    }

    Also, in calculateIntegralHOG method, the ptr1 & ptr2 should be type casted to char instead of float.

    char* ptr1 = (char*) (xsobel->imageData + y * (xsobel->widthStep));
    char* ptr2 = (char*) (ysobel->imageData + y * (ysobel->widthStep));
    float** ptrs = (float**) malloc(_bins * sizeof(float*));
    for (int i = 0; i < _bins ;i++){
    ptrs[i] = (float*) (bins_ptr[i]->imageData + y * (bins_ptr[i]->widthStep));
    }

    Hope this helps!

    ReplyDelete
    Replies
    1. still,there is a calculation error in temp_gradient..hope you can rectify that..

      Delete
  12. I tried the above code. But i am getting values like -1.#IND 0 -1.#QNAN. I think there is something wrong with atan calculation. Can somebody give an idea, how to fix this?

    ReplyDelete
  13. I am also getting NAN values. Can anybody tell me the approx value we should get? I am getting values less that 10^(-25). Though the code like fine but I think there is something wrong as values are too small.

    ReplyDelete
  14. This comment has been removed by the author.

    ReplyDelete
  15. I tell you why you guys get NAN values:

    First, you have to declare the xsobel and ysobel in the format of IPL_DEPTH_32F, but not IPL_DEPTH_16U, IPL_DEPTH_16S or IPL_DEPTH_8U.

    The other thing is about function 'dosobel', you can use 'cvsobel' instead.

    Good luck

    ReplyDelete
  16. Nice work... Thank you...

    ReplyDelete
  17. Hey man..the tutorial is great..but please correct the arithmatic of the code as suggested by the ppl above,the pointers are not pointing to the values

    ReplyDelete
  18. My bad...the code is fine...the thing is the values are too small...so the gradient is always=90.00000001(approx) and magnitude is 0.00000001(approx)

    ReplyDelete
  19. hey man great post. but i am confused about the calculation of gradient. because dalal used in his implementation a 1d mask of [-1,0,1] and you used sobel which uses a 2d mask. are they same?

    ReplyDelete
  20. Good Article about Object Detection Using opencv I - Integral Histogram for fast Calculation of HOG Features

    ReplyDelete
  21. There is one thing I am not understanding, what is the role of the cvRect in the calculateHOG_rect function.

    What dimensions should it have?

    ReplyDelete
  22. Soluble vulcanized fiber helps to trim the measure of cholesterol in the rip oxidizes, it causes equipment casualty,
    so you need to lead antioxidants.

    Here is my web site ... medicine pain no cholesterol muscle
    My webpage > medicine pain no cholesterol muscle

    ReplyDelete
  23. We're a group of volunteers and starting a new scheme in our community. Your website offered us with valuable info to work on. You've done a formidable ϳob and our entiгe community ωill be thanκful tο you.


    my site ... premature ejaculation pills

    ReplyDelete
  24. Hi there just wanted to give you a quick heads up and let you know a few of
    the images aren't loading correctly. I'm not sure why but I think its
    a linking issue. I've tried it in two different internet browsers and both show the same outcome.

    Also visit my web-site ... legal amphetamines

    ReplyDelete
  25. salut est ce que vous pouvez me donner un programme qui détecte des véhicules dans un vidéo en implantant le HOG ou le HAAR

    ReplyDelete
  26. If anyone has noticed any problem while using the function
    cvIntegral(bins[i], integrals[i]);
    I thinkn it is not giving the kind of expected output. To debug you can write the values of integrals[i] into a text file and see for yourself.

    So instead of using cvIntegral(bins[i], integrals[i]), i implemented a simple integral calualation module that gave me the kind of expected .

    If you would like to try ..here is the simple implementation
    void find_integral(IplImage* src, IplImage* dst)
    {
    float* prev_p_int = 0;
    for(int row = 0; row < src->height; row++)
    {
    float* p_bin = (float*)(src->imageData + row * src->widthStep);
    float* p_int = (float*)(dst->imageData + row * dst->widthStep);
    if(row > 0)
    prev_p_int= (float*)(dst->imageData + (row-1) * dst->widthStep);
    for(int col = 0; col < src->width; col++)
    {
    if(row == 0)
    p_int[col] = p_bin[col] + p_int[col - 1];
    else
    p_int[col] = p_bin[col] + p_int[col - 1] + prev_p_int[col] - prev_p_int[col - 1];
    }
    }
    }

    If that helps anyone , and hope it is correct !

    ReplyDelete