Saturday, December 31, 2011

Blob Detection, Connected Component (Pure Opencv)



Connected-component labeling (alternatively connected-component analysis, blob extraction, region labeling, blob discovery, or region extraction) is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled based on a given heuristic. Connected-component labeling is not to be confused with segmentation.


i got the initial code from this URL: http://nghiaho.com/?p=1102
However the code did not compile with my setup of OpenCV 2.2, im guessing it was an older version. so a refactored and corrected the errors to come up with this Class



class atsBlobFinder
    {
    public:
        atsBlobFinder()
        {
        }
        ///Original Code by http://nghiaho.com/?p=1102
        ///Changed and added commments. Removed Errors
        ///works with VS2010 and OpenCV 2.2+
        void FindBlobs(const cv::Mat &binary, vector < vector<cv::Point>  > &blobs)
        {
            blobs.clear();

            // Fill the label_image with the blobs
            // 0  - background
            // 1  - unlabelled foreground
            // 2+ - labelled foreground

            ///input is a binary image therefore values are either 0 or 1
            ///out objective is to find a set of 1's that are together and assign 2 to it
            ///then look for other 1's, and assign 3 to it....so on a soforth

            cv::Mat label_image;
            binary.convertTo(label_image, CV_32FC1); // weird it doesn't support CV_32S! Because the CV::SCALAR is a double value in the function floodfill

            int label_count = 2; // starts at 2 because 0,1 are used already

            //erode to remove noise-------------------------------
            Mat element = getStructuringElement( MORPH_RECT,
            Size( 2*3 + 1, 2*3+1 ),
            Point( 0, 0 ) );
            /// Apply the erosion operation
            erode( label_image, label_image, element );
            //---------------------------------------------------

            //just check the Matrix of label_image to make sure we have 0 and 1 only
            //cout << label_image << endl;

            for(int y=0; y < binary.rows; y++) {
                for(int x=0; x < binary.cols; x++) {
                    float checker = label_image.at<float>(y,x); //need to look for float and not int as the scalar value is of type double
                    cv::Rect rect;
                    //cout << "check:" << checker << endl;
                    if(checker == 1) {
                        //fill region from a point
                        cv::floodFill(label_image, cv::Point(x,y), cv::Scalar(label_count), &rect, cv::Scalar(0), cv::Scalar(0), 4);
                        label_count++;
                        //cout << label_image << endl <<"by checking: " << label_image.at<float>(y,x) <<endl;
                        //cout << label_image;

                        //a vector of all points in a blob
                        std::vector<cv::Point> blob;

                        for(int i=rect.y; i < (rect.y+rect.height); i++) {
                            for(int j=rect.x; j < (rect.x+rect.width); j++) {
                                float chk = label_image.at<float>(i,j);
                                //cout << chk << endl;
                                if(chk == label_count-1) {
                                    blob.push_back(cv::Point(j,i));
                                }                       
                            }
                        }
                        //place the points of a single blob in a grouping
                        //a vector of vector points
                        blobs.push_back(blob);
                    }
                }
            }
            cout << label_count <<endl;
            imshow("label image",label_image);
        }
    private:
    }; 


From the code comments, ive answered and tested a few parts which the original author did not discuss.

Running on Visual Studio 2010 and OpenCV 2.2 using the 4 connected neighbors and opencv internal function FloodFill.

1. Get the Binary image. the binary image should have values of 0 and 1 only.
2. go through each pixel and find the value 1, floodfill and replace all 1 with a counter ie. number 2
3. every blob found should now be part of floodfill and all neighbors value changed to an ascending number
4. from each blob, get the x and y coordinate of that blob and save it in a vector. giving you a vector<Point>
5. save each of those Vector<Point> into another Vector which represents all the blobs found
6. Output the value



atsBlobFinder blb;
cv::Mat output = cv::Mat::zeros(img.size(), CV_8UC3); //3 Channels

            cv::Mat binary;
            vector <vector<cv::Point>> blobs;

            blb.FindBlobs(binary, blobs);
            for(size_t i=0; i < blobs.size(); i++) {
                unsigned char r = 255 * (rand()/(1.0 + RAND_MAX));
                unsigned char g = 255 * (rand()/(1.0 + RAND_MAX));
                unsigned char b = 255 * (rand()/(1.0 + RAND_MAX));

                for(size_t j=0; j < blobs[i].size(); j++) {
                    int x = blobs[i][j].x;
                    int y = blobs[i][j].y;

                    output.at<Vec3b>(y,x)[0] = ima.at<uchar>(y,x); //channel 1
                    output.at<Vec3b>(y,x)[1] = ima.at<uchar>(y,x); //channel 2
                    output.at<Vec3b>(y,x)[2] = ima.at<uchar>(y,x); //channel 3
                }
            }
            imshow("con comp",output);

the vector<vector<Point>> blobs can create a mask and output the blob in separate images

Wednesday, December 28, 2011

Computing Gini Index of an image (measure of Impurity)

Using my previous posts Class file and this reference:
http://people.revoledu.com/kardi/tutorial/DecisionTree/how-to-measure-impurity.htm

float computeGiniIndex(Mat r, Mat g, Mat b)
    {
        float giniIndex = 0.0;
        float frequency = getFrequencyOfBin(r);
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(r,i));
            giniIndex += Hc*Hc;
        }
        frequency = getFrequencyOfBin(g);
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(g,i));
            giniIndex += Hc*Hc;
        }
        frequency = getFrequencyOfBin(b);
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(b,i));
            giniIndex += Hc*Hc;
        }
        giniIndex = 1 - (giniIndex);
        //cout << giniIndex <<endl;
        return giniIndex;
    }

Friday, December 23, 2011

Computing Entropy of an image (CORRECTED)

entropy is a measure of the uncertainty associated with a random variable.
basically i want to get a single value representing the entropy of an image.

1. Assign 255 bins for the range of values between 0-255
2. separate the image into its 3 channels
3. compute histogram for each channel
4. normalize all 3 channels unifirmely
5. for each channel get the bin value (Hc) and use its absolute value (negative log is infinity)
6. compute Hc*log10(Hc)
7. add to entropy and continue with 5 until a single value converges
5. get the frequency of each channel - add all the values of the bin
6. for each bin get a probability -
if bin 1 = 20
bin 2 = 30
then frequency is 50 and probability is 20/50 and 30/50
then compute using shannon formula

 REFERENCE: http://people.revoledu.com/kardi/tutorial/DecisionTree/how-to-measure-impurity.htm




class atsHistogram
{
public:
    cv::Mat DrawHistogram(Mat src)
    {
        /// Separate the image in 3 places ( R, G and B )
         vector<Mat> rgb_planes;
         split( src, rgb_planes );


         /// Establish the number of bins
         int histSize = 255;


         /// Set the ranges ( for R,G,B) )
         float range[] = { 0, 255 } ;
         const float* histRange = { range };


         bool uniform = true; bool accumulate = false;


         Mat r_hist, g_hist, b_hist;


         /// Compute the histograms:
         calcHist( &rgb_planes[0], 1, 0, Mat(), r_hist, 1, &histSize, &histRange, uniform, accumulate );
         calcHist( &rgb_planes[1], 1, 0, Mat(), g_hist, 1, &histSize, &histRange, uniform, accumulate );
         calcHist( &rgb_planes[2], 1, 0, Mat(), b_hist, 1, &histSize, &histRange, uniform, accumulate );


         // Draw the histograms for R, G and B
         int hist_w = 400; int hist_h = 400;
         int bin_w = cvRound( (double) hist_w/histSize );


         Mat histImage( hist_w, hist_h, CV_8UC3, Scalar( 0,0,0) );


         /// Normalize the result to [ 0, histImage.rows ]
         normalize(r_hist, r_hist, 0, histImage.rows, NORM_MINMAX, -1, Mat() );
         normalize(g_hist, g_hist, 0, histImage.rows, NORM_MINMAX, -1, Mat() );
         normalize(b_hist, b_hist, 0, histImage.rows, NORM_MINMAX, -1, Mat() );


         /// Draw for each channel
         /*for( int i = 1; i < histSize; i++ )
           {
             line( histImage, Point( bin_w*(i-1), hist_h - cvRound(r_hist.at<float>(i-1)) ) ,
                              Point( bin_w*(i), hist_h - cvRound(r_hist.at<float>(i)) ),
                              Scalar( 0, 0, 255), 2, 8, 0  );
             line( histImage, Point( bin_w*(i-1), hist_h - cvRound(g_hist.at<float>(i-1)) ) ,
                              Point( bin_w*(i), hist_h - cvRound(g_hist.at<float>(i)) ),
                              Scalar( 0, 255, 0), 2, 8, 0  );
             line( histImage, Point( bin_w*(i-1), hist_h - cvRound(b_hist.at<float>(i-1)) ) ,
                              Point( bin_w*(i), hist_h - cvRound(b_hist.at<float>(i)) ),
                              Scalar( 255, 0, 0), 2, 8, 0  );
            }*/
double entropy = (double)computeShannon(r_hist,g_hist,b_hist);
         //printf("Entropy: %f" , entropy );
         cout << entropy << endl;
         return histImage;
    }
    float getHistogramBinValue(Mat hist, int binNum)
    {
        //return cvRound(hist.at<float>(binNum));
        return hist.at<float>(binNum);
    }
    float computeShannon(Mat r, Mat g, Mat b)
    {
        int histSize = 255; //number of bins
        float entropy = 0.0;
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(r,i));
            //cout << "Red " << Hc << endl;
            entropy += Hc * log10(Hc);
            //cout << "-" << Hc << " -n- " << entropy << endl;
        }
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(g,i));
            //cout << "Green " << Hc << endl;
            entropy += Hc * log10(Hc);
        }
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(b,i));
            //cout << "Blue " << Hc << endl;
            entropy += Hc * log10(Hc);
        }
        entropy = entropy * -1;
        //cout << entropy <<endl;
        return entropy;
    }
private:
};

     float getHistogramBinValue(Mat hist, int binNum)
    {
        return hist.at<float>(binNum);
    }
    float getFrequencyOfBin(Mat channel)
    {
        float frequency = 0.0;
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(channel,i));
            frequency += Hc;
        }
        return frequency;
    }
    float computeShannonEntropy(Mat r, Mat g, Mat b)
    {
        float entropy = 0.0;
        float frequency = getFrequencyOfBin(r);
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(r,i));
            entropy += -(Hc/frequency) * log10((Hc/frequency));
        }
        frequency = getFrequencyOfBin(g);
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(g,i));
            entropy += -(Hc/frequency) * log10((Hc/frequency));
        }
        frequency = getFrequencyOfBin(b);
        for( int i = 1; i < histSize; i++ )
        {
            float Hc = abs(getHistogramBinValue(b,i));
            entropy += -(Hc/frequency) * log10((Hc/frequency));
        }
        entropy = entropy;
        //cout << entropy <<endl;
        return entropy;
    }