Monday, January 24, 2011

Finding objects inside image using Classical Connected Component binary image analysis method using OpenCV

How Do i? Find objects inside image using Classical connected component in binary image using OpenCV




This was my project for Digital Image Processing in NUST taught by a great teacher Naveed Sarfaraz Khattak. Thanks all for giving such knowledge and making i easy to study.

Problem Description:

The objective of this project is to gain experience with connected components analysis and the use of features computed within it for recognition of objects. This problem is to implement a connected components program so that it will report on all objects found in the input image and computes all inter object distances.

This Project will

1- Find objects
2- Calculate their area
3- Calculate Centroid
4- Distance between each object (distance matrix)
5- Bounding box


Summary of Choices:

I have done this project in OpenCV library using Visual Studio 2010. I am using
1- OpenCV for Image Analysis
2- WPF for presentation Layer along with C#

This project requires
OpenCV 2.0+
Visual Studio 2010

Sample Images:




Result Discussion and Algorithms:

This program is written in OpenCV to learn and implement the open standard of image processing system. This program can run on any Windows machine where OpenCV is installed and .Net FrameWork 4.0 is available.

This program used Connected Component union find algorithm to find the neighbours of each pixel and tag that pixel in this the image. Where there are more than one neighbours for one pixel value, a confilict note is made.

After going through whole image, conflicts are resolved. There was a problem in conflict resolution and it was not possible to solve the labels in two go, instead it took k iterations to resolve the whole k conflicts due to the problem that one connected component can hold more than 2 labels if it is has a difficult shape.

After finding all the objects, each object than processed for its features. Finding area was easy so does the centroids. Bounding region takes a while but the real problem and time consumed in finding connected objects. After working 4 days and nights I am able to complete the project but there is no time to write the whole story before submission of this report.

This program is using the layout as described below.

1- It has a button to open the image,
2- Open the image will trigger the binary analysis
3- It will show the image analysis
4- To see the distance matrix, click on the distance matrix tab

Please see the image below for reference





Results:


Code:

This is a very long function and its not all of it. You can download the whole project, document and image dump at the end of this article.

//This is the main function that will label the image
String^ LabelIamge(String^ filePath,String^ savePath)
{
  IplImage *source = cvLoadImage( StringToChar(filePath),0);
  int height= source->height; // number of lines
int bytesPerRow= source->width * source->nChannels; // total number of element per line
int step= source->widthStep; // effective width

unsigned char *data= reinterpret_cast<unsigned char *>(source->imageData);

//number of objects in the picture
int objects=1;
//if a number is already used to add new number
bool isConsumed=false;
//Four neighbours of the concerned picture
int neighbours[4];
//This will register all confilicts
Hashtable mapTable;

//start of parsing each pixel
for (int i=0; i<height; i++) {
for (int j=0; j<bytesPerRow; j+= source->nChannels) 
{
//if the current pixel is a black pixel
if(data[i*step+j]==0)
{
//left neighbour
if(j>0)
{
if(data[i*step+(j-1)]>255)
neighbours[LEFT]=data[i*step+(j-1)];
else
neighbours[LEFT]=-1;
}

//left top neighbour
if(j>0 && i>0)
{
if(data[(i-1)*step+(j-1)]<255)
neighbours[LEFTTOP]=data[(i-1)*step+(j-1)];
else
neighbours[LEFTTOP]=-1;
}

//top neighbour
if(i>0)
{
if(data[(i-1)*step+(j)]<255)
neighbours[TOP]=data[(i-1)*step+(j)];
else
neighbours[TOP]=-1;
}

//right top neighbour
if(i>0 && j+1>bytesPerRow)
{
if(data[(i-1)*step+(j+1)]<255)
neighbours[RIGHTTOP]=data[(i-1)*step+(j+1)];
else
neighbours[RIGHTTOP]=-1;
}

//number of neighbours found
int totalNeighbours=Neighbours(neighbours);
int* sNeighbours;
//if neighbours are there, serialize the neighbours in asc order and find the numbers of real neighbours
if(totalNeighbours>0)
{
SerializedData data=NeighboursSerial(neighbours);

sNeighbours=data.ary;
totalNeighbours=data.size;

BubbleSort(sNeighbours,totalNeighbours);
}

//if no neighbour, assign the new number
if(neighbours[LEFT]==-1 && neighbours[LEFTTOP]==-1 && neighbours[TOP]==-1 && neighbours[RIGHTTOP]==-1)
{
data[i*step+j]=objects;
isConsumed=true;
}
//if there are one neighbour, then assign the neighbour lable to the pixel
else if(totalNeighbours==1)
{
data[i*step+j]=sNeighbours[0];
}
// if there are more than one neighbours, then assign the minimum neighbour from the sorted neighbour array and add the next neighbour to conflict table
else
{
data[i*step+j]=sNeighbours[0];

//add the conflict only if it doesnot exist before
if(mapTable.ContainsKey(sNeighbours[1])==false)
{
mapTable.Add(sNeighbours[1],sNeighbours[0]);
}
}
}
// if pixel is not black, then increment the object number if it is not already used.
else
{
if(isConsumed)
{
isConsumed=false;
objects+=1;//+;
}
}
}
}

//translate all the map table into desc order and resolve the conflict by using the conflict table
ICollection^ keyColl = mapTable.Keys;
int mtLength=mapTable.Count;
int* a=new int[mtLength];
int index=0;

for each( int s in keyColl )
{
a[index]=s;
index++;
}

BubbleSortDesc(a,mapTable.Count);
for(int k=0;k<mtLength;k++)
{
for (int i=0; i<height; i++) {
for (int j=0; j<bytesPerRow; j+= source->nChannels) 
{
if(data[i*step+j]==a[k])
{
data[i*step+j]=(int)mapTable[a[k]];
}
}
}
}

//find the number of objects in the table
ConnectedObject* totalObjects=CountObjects(source,objects);
int count=0;
//discart the objects that are less than threshhold i.e. 20 pixels
totalObjects=RealObjects(totalObjects,objects,threshHold,count);
//find the centroids
Centroids(source,totalObjects,count);
//find the distance between each object
String^ distances=EuclideanDistance(totalObjects,count);
//color the image to display friendly colors and distinguish each object
IplImage *destination=LabeledToColorImage(source,totalObjects,count,objects);
//save image
SaveImage(destination,savePath);
// return the report in JSON format for data exchange between .Net and openCV
return ConnectedObjectToJSON(totalObjects,count,distances);
}

click here for Source Project + Sample Images + Project Results + Document

6 comments:

  1. hi, thank you so much for uploading this project......but i am unable to download the source code file....
    on emore thign is u r using some function calls like BubbleSortDesc, countobjects, realobjects, labeledtocolorimage etc.......
    kindly pplease provide me those function definitions if possible. thank you

    ReplyDelete
  2. Please add me in your gtalk and i will provide you with the code
    mamoonr@gmail.com

    ReplyDelete
  3. hi........the file is not available on the designated link..it is saying file not found. Thanks.

    ReplyDelete
  4. sure..i will add now.

    ReplyDelete
  5. hi, the link download is broken, can you send me? this my email pradana.hendi@gmail.com

    ReplyDelete
  6. Could you send me the link please? dogan.uzusen@gmail.com

    ReplyDelete