Friday, October 23, 2009

Object Detection using opencv III - Training an svm for the extracted hog features

This is a follow up post to an earlier post on calculation of hog feature vectors for object detection using opencv. Here I describe how a support vector machine (svm) can be trained for a dataset containing positive and negative examples of the object to detected. The code has been commented for easier understanding of how it works :



/*This function takes in a the path and names of
64x128 pixel images, the size of the cell to be
used for calculation of hog features(which should
be 8x8 pixels, some modifications will have to be 
done in the code for a different cell size, which
could be easily done once the reader understands
how the code works), a default block size of 2x2
cells has been considered and the window size
parameter should be 64x128 pixels (appropriate
modifications can be easily done for other say
64x80 pixel window size). All the training images
are expected to be stored at the same location and
the names of all the images are expected to be in
sequential order like a1.jpg, a2.jpg, a3.jpg ..
and so on or a(1).jpg, a(2).jpg, a(3).jpg ... The
explanation of all the parameters below will make
clear the usage of the function. The synopsis of
the function is as follows :

prefix : it should be the path of the images, along
with the prefix in the image name for
example if the present working directory is
/home/saurabh/hog/ and the images are in
/home/saurabh/hog/images/positive/ and are
named like pos1.jpg, pos2.jpg, pos3.jpg ....,
then the prefix parameter would be
"images/positive/pos" or if the images are
named like pos(1).jpg, pos(2).jpg,
pos(3).jpg ... instead, the prefix parameter
would be "images/positive/pos("

suffix : it is the part of the name of the image
files after the number for example for the
above examples it would be ".jpg" or ").jpg"

cell   : it should be CvSize(8,8), appropriate changes
need to be made for other cell sizes

window : it should be CvSize(64,128), appropriate
changes need to be made for other window sizes

number_samples : it should be equal to the number of
training images, for example if the
training images are pos1.jpg, pos2.jpg
..... pos1216.jpg, then it should be
1216

start_index : it should be the start index of the images'
names for example for the above case it
should be 1 or if the images were named
like pos1000.jpg, pos1001.jpg, pos1002.jpg
.... pos2216.jpg, then it should be 1000

end_index : it should be the end index of the images'
name for example for the above cases it
should be 1216 or 2216

savexml   : if you want to store the extracted features,
then you can pass to it the name of an xml
file to which they should be saved

normalization : the normalization scheme to be used for
computing the hog features, any of the
opencv schemes could be passed or -1
could be passed if no normalization is
to be done */

CvMat* train_64x128(char *prefix, char *suffix, CvSize cell,
CvSize window, int number_samples, int start_index,
int end_index, char *savexml = NULL, int canny = 0,
int block = 1, int normalization = 4) 
{

char filename[50] = "\0", number[8];
int prefix_length;
prefix_length = strlen(prefix);
int bins = 9;

/* A default block size of 2x2 cells is considered */

int block_width = 2, block_height = 2;

/* Calculation of the length of a feature vector for
an image (64x128 pixels)*/

int feature_vector_length;
feature_vector_length = (((window.width -
cell.width * block_width)/ cell.width) + 1) *
(((window.height - cell.height * block_height)
/ cell.height) + 1) * 36;

/* Matrix to store the feature vectors for
all(number_samples) the training samples */

CvMat* training = cvCreateMat(number_samples,
feature_vector_length, CV_32FC1);

CvMat row;
CvMat* img_feature_vector;
IplImage** integrals;
int i = 0, j = 0;

printf("Beginning to extract HoG features from
positive images\n");

strcat(filename, prefix);

/* Loop to calculate hog features for each
image one by one */

for (i = start_index; i <= end_index; i++) 
{
cvtInt(number, i);
strcat(filename, number);
strcat(filename, suffix);
IplImage* img = cvLoadImage(filename);

/* Calculation of the integral histogram for
fast calculation of hog features*/

integrals = calculateIntegralHOG(img);
cvGetRow(training, &row, j);
img_feature_vector
= calculateHOG_window(integrals, cvRect(0, 0,
window.width, window.height), normalization);
cvCopy(img_feature_vector, &row);
j++;
printf("%s\n", filename);
filename[prefix_length] = '\0';
for (int k = 0; k < 9; k++) 
{
cvReleaseImage(&integrals[k]);
}
}
if (savexml != NULL) 
{
cvSave(savexml, training);
}

return training;
}

/* This function is almost the same as
train_64x128(...), except the fact that it can
take as input images of bigger sizes and
generate multiple samples out of a single
image.

It takes 2 more parameters than
train_64x128(...), horizontal_scans and
vertical_scans to determine how many samples
are to be generated from the image. It
generates horizontal_scans x vertical_scans
number of samples. The meaning of rest of the
parameters is same.

For example for a window size of
64x128 pixels, if a 320x240 pixel image is
given input with horizontal_scans = 5 and
vertical scans = 2, then it will generate to
samples by considering windows in the image
with (x,y,width,height) as (0,0,64,128),
(64,0,64,128), (128,0,64,128), .....,
(0,112,64,128), (64,112,64,128) .....
(256,112,64,128)

The function takes non-overlapping windows
from the image except the last row and last
column, which could overlap with the second
last row or second last column. So the values
of horizontal_scans and vertical_scans passed
should be such that it is possible to perform
that many scans in a non-overlapping fashion
on the given image. For example horizontal_scans
= 5 and vertical_scans = 3 cannot be passed for
a 320x240 pixel image as that many vertical scans
are not possible for an image of height 240
pixels and window of height 128 pixels. */

CvMat* train_large(char *prefix, char *suffix,
CvSize cell, CvSize window, int number_images,
int horizontal_scans, int vertical_scans,
int start_index, int end_index,
char *savexml = NULL, int normalization = 4)
{
char filename[50] = "\0", number[8];
int prefix_length;
prefix_length = strlen(prefix);
int bins = 9;

/* A default block size of 2x2 cells is considered */

int block_width = 2, block_height = 2;

/* Calculation of the length of a feature vector for
an image (64x128 pixels)*/

int feature_vector_length;
feature_vector_length = (((window.width -
cell.width * block_width) / cell.width) + 1) *
(((window.height - cell.height * block_height)
/ cell.height) + 1) * 36;

/* Matrix to store the feature vectors for
all(number_samples) the training samples */

CvMat* training = cvCreateMat(number_images
* horizontal_scans * vertical_scans,
feature_vector_length, CV_32FC1);

CvMat row;
CvMat* img_feature_vector;
IplImage** integrals;
int i = 0, j = 0;
strcat(filename, prefix);

printf("Beginning to extract HoG features
from negative images\n");

/* Loop to calculate hog features for each
image one by one */

for (i = start_index; i <= end_index; i++) 
{
cvtInt(number, i);
strcat(filename, number);
strcat(filename, suffix);
IplImage* img = cvLoadImage(filename);
integrals = calculateIntegralHOG(img);
for (int l = 0; l < vertical_scans - 1; l++)
{
for (int k = 0; k < horizontal_scans - 1; k++)
{
cvGetRow(training, &row, j);
img_feature_vector = calculateHOG_window(
integrals, cvRect(window.width * k,
window.height * l, window.width,
window.height), normalization);

cvCopy(img_feature_vector, &row);
j++;
}

cvGetRow(training, &row, j);

img_feature_vector = calculateHOG_window(
integrals, cvRect(img->width - window.width,
window.height * l, window.width,
window.height), normalization);

cvCopy(img_feature_vector, &row);
j++;
}

for (int k = 0; k < horizontal_scans - 1; k++)
{
cvGetRow(training, &row, j);

img_feature_vector = calculateHOG_window(
integrals, cvRect(window.width * k,
img->height - window.height, window.width,
window.height), normalization);

cvCopy(img_feature_vector, &row);
j++;
}
cvGetRow(training, &row, j);

img_feature_vector = calculateHOG_window(integrals,
cvRect(img->width - window.width, img->height -
window.height, window.width, window.height),
normalization);

cvCopy(img_feature_vector, &row);
j++;

printf("%s\n", filename);
filename[prefix_length] = '\0';
for (int k = 0; k < 9; k++)
{
cvReleaseImage(&integrals[k]);
}

cvReleaseImage(&img);

}

printf("%d negative samples created \n",
training->rows);

if (savexml != NULL)
{
cvSave(savexml, training);
printf("Negative samples saved as %s\n",
savexml);
}

return training;

}


/* This function trains a linear support vector
machine for object classification. The synopsis is
as follows :

pos_mat : pointer to CvMat containing hog feature
vectors for positive samples. This may be
NULL if the feature vectors are to be read
from an xml file

neg_mat : pointer to CvMat containing hog feature
vectors for negative samples. This may be
NULL if the feature vectors are to be read
from an xml file

savexml : The name of the xml file to which the learnt
svm model should be saved

pos_file: The name of the xml file from which feature
vectors for positive samples are to be read.
It may be NULL if feature vectors are passed
as pos_mat

neg_file: The name of the xml file from which feature
vectors for negative samples are to be read.
It may be NULL if feature vectors are passed
as neg_mat*/


void trainSVM(CvMat* pos_mat, CvMat* neg_mat, char *savexml,
char *pos_file = NULL, char *neg_file = NULL) 
{


/* Read the feature vectors for positive samples */
if (pos_file != NULL) 
{
printf("positive loading...\n");
pos_mat = (CvMat*) cvLoad(pos_file);
printf("positive loaded\n");
}

/* Read the feature vectors for negative samples */
if (neg_file != NULL)
{
neg_mat = (CvMat*) cvLoad(neg_file);
printf("negative loaded\n");
}

int n_positive, n_negative;
n_positive = pos_mat->rows;
n_negative = neg_mat->rows;
int feature_vector_length = pos_mat->cols;
int total_samples;
total_samples = n_positive + n_negative;

CvMat* trainData = cvCreateMat(total_samples,
feature_vector_length, CV_32FC1);

CvMat* trainClasses = cvCreateMat(total_samples,
1, CV_32FC1 );

CvMat trainData1, trainData2, trainClasses1,
trainClasses2;

printf("Number of positive Samples : %d\n",
pos_mat->rows);

/*Copy the positive feature vectors to training
data*/

cvGetRows(trainData, &trainData1, 0, n_positive);
cvCopy(pos_mat, &trainData1);
cvReleaseMat(&pos_mat);

/*Copy the negative feature vectors to training
data*/

cvGetRows(trainData, &trainData2, n_positive,
total_samples);

cvCopy(neg_mat, &trainData2);
cvReleaseMat(&neg_mat);

printf("Number of negative Samples : %d\n",
trainData2.rows);

/*Form the training classes for positive and
negative samples. Positive samples belong to class
1 and negative samples belong to class 2 */

cvGetRows(trainClasses, &trainClasses1, 0, n_positive);
cvSet(&trainClasses1, cvScalar(1));

cvGetRows(trainClasses, &trainClasses2, n_positive,
total_samples);

cvSet(&trainClasses2, cvScalar(2));


/* Train a linear support vector machine to learn from
the training data. The parameters may played and
experimented with to see their effects*/

CvSVM svm(trainData, trainClasses, 0, 0,
CvSVMParams(CvSVM::C_SVC, CvSVM::LINEAR, 0, 0, 0, 2,
0, 0, 0, cvTermCriteria(CV_TERMCRIT_EPS,0, 0.01)));

printf("SVM Training Complete!!\n");

/*Save the learnt model*/

if (savexml != NULL) {
svm.save(savexml);
}
cvReleaseMat(&trainClasses);
cvReleaseMat(&trainData);

}




I hope the comments were helpful to understand and use the code. To see how a large collection of files can be renamed to a sequential order which is required by this implementation refer here. Another way to read in the images of dataset could be to store the paths of all files in a text file and parse then parse the text file. I will follow up this post soon, describing how the learnt model can be used for actual detection of an object in an image.

Thursday, October 22, 2009

Object Detection using opencv II - Calculation of Hog Features

This is follow up post to an earlier post where I have described how an integral histogram can be obtained from an image for fast calculation of hog features. Here I am posting the code for how this integral histogram can be used to calculate the hog feature vectors for an image window. I have commented the code for easier understanding of how it works :



/* This function takes in a block as a rectangle and
calculates the hog features for the block by dividing
it into cells of size cell(the supplied parameter),
calculating the hog features for each cell using the
function calculateHOG_rect(...), concatenating the so
obtained vectors for each cell and then normalizing over
the concatenated vector to obtain the hog features for a
block */ 

void calculateHOG_block(CvRect block, CvMat* hog_block, 
IplImage** integrals,CvSize cell, int normalization) 
{
int cell_start_x, cell_start_y;
CvMat vector_cell;
int startcol = 0;
for (cell_start_y = block.y; cell_start_y <= 
block.y + block.height - cell.height; 
cell_start_y += cell.height) 
{
for (cell_start_x = block.x; cell_start_x <= 
block.x + block.width - cell.width; 
cell_start_x += cell.width) 
{
cvGetCols(hog_block, &vector_cell, startcol, 
startcol + 9);

calculateHOG_rect(cvRect(cell_start_x,
cell_start_y, cell.width, cell.height), 
&vector_cell, integrals, -1);

startcol += 9;
}
}
if (normalization != -1)
cvNormalize(hog_block, hog_block, 1, 0, 
normalization);
}

/* This function takes in a window(64x128 pixels,
but can be easily modified for other window sizes)
and calculates the hog features for the window. It
can be used to calculate the feature vector for a 
64x128 pixel image as well. This window/image is the
training/detection window which is used for training
or on which the final detection is done. The hog
features are computed by dividing the window into
overlapping blocks, calculating the hog vectors for
each block using calculateHOG_block(...) and
concatenating the so obtained vectors to obtain the
hog feature vector for the window*/

CvMat* calculateHOG_window(IplImage** integrals,
CvRect window, int normalization) 
{

/*A cell size of 8x8 pixels is considered and each
block is divided into 2x2 such cells (i.e. the block
is 16x16 pixels). So a 64x128 pixels window would be
divided into 7x15 overlapping blocks*/ 

int block_start_x, block_start_y, cell_width = 8;
int cell_height = 8;
int block_width = 2, block_height = 2;

/* The length of the feature vector for a cell is
9(since no. of bins is 9), for block it would  be
9*(no. of cells in the block) = 9*4 = 36. And the
length of the feature vector for a window would be
36*(no. of blocks in the window */

CvMat* window_feature_vector = cvCreateMat(1,
((((window.width - cell_width * block_width)
/ cell_width) + 1) * (((window.height -
cell_height * block_height) / cell_height)
+ 1)) * 36, CV_32FC1);

CvMat vector_block;
int startcol = 0;
for (block_start_y = window.y; block_start_y
<= window.y + window.height - cell_height
* block_height; block_start_y += cell_height)
{
for (block_start_x = window.x; block_start_x
<= window.x + window.width - cell_width
* block_width; block_start_x += cell_width)
{
cvGetCols(window_feature_vector, &vector_block,
startcol, startcol + 36);

calculateHOG_block(cvRect(block_start_x,
block_start_y, cell_width * block_width, cell_height
* block_height), &vector_block, integrals, cvSize(
cell_width, cell_height), normalization);

startcol += 36;
}
}
return (window_feature_vector);
}




I will very soon post how a support vector machine (svm) can trained using the above functions for an object using a dataset and how the learned model can be used to detect the corresponding object in an image.

Friday, October 16, 2009

Radix 2 floating point FFT Implementation

I searched for fft code over the internet but couldn't find a simple code for the FFT. So I am posting the code. I think I have explained everything in the code code is what follows:

/*
The program follows is for the FFT of a one dimensional input
fft algorithm used is radix 2
so works only for input lengths powers of 2
input is complex and output obviously is complex
changes can be made to use the function for your requirement.
I have tried to comment the code anyway there shouldnt be any
problem its such a small program.
*/
//Header Files
#include <stdio.h>
#include<stdlib.h>
#include<math.h>

//Complex number structure
typedef struct complex
{
float real;            //Real part of the number
float imaginary;    //Imaginary part of the number
} complex;

//Function to calculate the FFT Method used is Radix 2
complex* fft(complex *in,int N){
//Local variables
complex *X,*Xg,*Xh;
complex *xe,*xo;
int i=0;
//Memory allocation
xe = (complex*)malloc(sizeof(complex)*(N/2));
xo = (complex*)malloc(sizeof(complex)*(N/2));
X = (complex *)malloc(sizeof(complex)*N);
//every recursion has to stop
//so here is the stopping condition of the recursion
if(N==2){
X[0].real        = in[0].real + in[1].real;
X[0].imaginary    = in[0].imaginary + in[1].imaginary;
X[1].real        = in[0].real - in[1].real;
X[1].imaginary    = in[0].imaginary - in[1].imaginary;
return X;
}
//Breaking the input for recursion
for (i=0;i<N;i++){
if(i%2==0){//even indexes
xe[i/2].real        = in[i].real;
xe[i/2].imaginary    = in[i].imaginary;
}
else{//odd indexes
xo[(i-1)/2].real        = in[i].real;
xo[(i-1)/2].imaginary    = in[i].imaginary;
}
}
//recursive calls
Xg = fft(xe,N/2);
Xh = fft(xo,N/2);
//Combining the two halfs here is where magic happens
for (i=0;i<N;i++){
X[i].real=Xg[i%(N/2)].real + Xh[i%(N/2)].real*cos(2*3.14*i/N)+Xh[i%(N/2)].imaginary*sin(2*3.14*i/N);
X[i].imaginary=Xg[i%(N/2)].imaginary+Xh[i%(N/2)].imaginary*cos(2*3.14*i/N)-Xh[i%(N/2)].real*sin(2*3.14*i/N);
}
//deallocating the waste memory
free(Xg);
free(Xh);
return X;//returning the result
}
//the main function
int main(int argc,char *argv[])
{
int N,i;
complex *x;//input
complex *X;//variable to store FFT of the input
//Note : N has to be a power of 2 otherwise the function doesnt work
//asking for the no of points in the FFT
printf("\nenter N must be a power of 2:");
scanf("%d",&N);
//allocating memory for the input
x = (complex*)malloc(N*sizeof(complex));
//taking the input
for(i=0;i<N;i++){
printf("\nenter %dth element real then imaginary",i);
scanf("%f",&(x[i].real));  
scanf("%f",&(x[i].imaginary));
}
//calling the fft function
X = fft(x,N);
//displaying the result
printf("\nFFT of the input is as follows");
for(i=0;i<N;i++){
printf("\nXr[%d] = %.2f + j %.2f",i,X[i].real,X[i].imaginary);
}
return 0;
}
//end of the program

Monday, October 12, 2009

Virtual Box - Shared Folders

The VirtualBox Guest Additions are software packages which can be installed inside of supported guest systems to improve their performance and to provide additional integration and communication with the host system.

After installing the Guest Additions, a virtual machine will support automatic adjustment of video resolutions, seamless windows and more.

In particular, Guest Additions provide for “shared folders”, which let you access files from the host system from within a guest machine.

This is how shared folders can be setup on a windows (xp) or linux (ubuntu) guest operating system :

1. Open up the virtual box interface by clicking on the virtual box shortcut or from the start menu.
2. In the left pane which contains the list of installed guest operating systems, select the system with which you want to share folders from the host operating system.
3. In the right pane, click on shared folders and select the folder you want to share. After this the number of shared folders which appears just beneath the shared folders option will increment by 1.
4. Now boot the virtual system.

For windows:

5. Open My computer and right click on network places in the right pane and select map network drive.
6. Choose a drive letter and to select the folder click on the browse... button. In the browse dialog box, expand the VirtualBox Shared Folders option and you'll find the folder you had shared there. Select it and click Ok.
7.In the Map Network Drive dialog box, check the Reconnect at logon checkbox if not already so and click on finish.
8. Now your shared folder will appear in the Network drives everytime you boot your virtual system. You can access the virtual drives just like normal drives from My Computer.

For linux:


5. To make folders mount everytime an ubuntu guest system is booted , you will have to edit the file with the filesystem static information, /etc/fstab.
6. To edit it open up a terminal and give the following commands :

cp /etc/fstab ~/fstab.backup
sudo nano /etc/fstab

6.Append at the end of the file

{name of shared folder} {path of the mount point}
(which will be something like /home/{user}/Desktop/downloads) vboxsf rw 0 2

7.To save press CTRL+O, then press CTRL+X to exit.
8.Restart the guest system and the shared folders will be mounted at the respective mount points.