connectedcomponents.cpp

00001 /*M///////////////////////////////////////////////////////////////////////////////////////
00002 //
00003 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
00004 //
00005 //  By downloading, copying, installing or using the software you agree to this license.
00006 //  If you do not agree to this license, do not download, install,
00007 //  copy or use the software.
00008 //
00009 //
00010 //                        Intel License Agreement
00011 //                For Open Source Computer Vision Library
00012 //
00013 // Copyright (C) 2000, Intel Corporation, all rights reserved.
00014 // Third party copyrights are property of their respective owners.
00015 //
00016 // Redistribution and use in source and binary forms, with or without modification,
00017 // are permitted provided that the following conditions are met:
00018 //
00019 //   * Redistribution's of source code must retain the above copyright notice,
00020 //     this list of conditions and the following disclaimer.
00021 //
00022 //   * Redistribution's in binary form must reproduce the above copyright notice,
00023 //     this list of conditions and the following disclaimer in the documentation
00024 //     and/or other materials provided with the distribution.
00025 //
00026 //   * The name of Intel Corporation may not be used to endorse or promote products
00027 //     derived from this software without specific prior written permission.
00028 //
00029 // This software is provided by the copyright holders and contributors "as is" and
00030 // any express or implied warranties, including, but not limited to, the implied
00031 // warranties of merchantability and fitness for a particular purpose are disclaimed.
00032 // In no event shall the Intel Corporation or contributors be liable for any direct,
00033 // indirect, incidental, special, exemplary, or consequential damages
00034 // (including, but not limited to, procurement of substitute goods or services;
00035 // loss of use, data, or profits; or business interruption) however caused
00036 // and on any theory of liability, whether in contract, strict liability,
00037 // or tort (including negligence or otherwise) arising in any way out of
00038 // the use of this software, even if advised of the possibility of such damage.
00039 //
00040 // 2011 Jason Newton <nevion@gmail.com>
00041 //M*/
00042 //
00043 #include "precomp.hpp"
00044 #include <vector>
00045 
00046 namespace cv{
00047     namespace connectedcomponents{
00048 
00049     struct NoOp{
00050         NoOp(){
00051         }
00052         void init(int /*labels*/){
00053         }
00054         inline
00055         void operator()(int r, int c, int l){
00056             (void) r;
00057             (void) c;
00058             (void) l;
00059         }
00060         void finish(){}
00061     };
00062     struct Point2ui64{
00063         uint64 x, y;
00064         Point2ui64(uint64 _x, uint64 _y):x(_x), y(_y){}
00065     };
00066 
00067     struct CCStatsOp{
00068         const _OutputArray* _mstatsv;
00069         cv::Mat statsv;
00070         const _OutputArray* _mcentroidsv;
00071         cv::Mat centroidsv;
00072         std::vector<Point2ui64> integrals;
00073 
00074         CCStatsOp(OutputArray _statsv, OutputArray _centroidsv): _mstatsv(&_statsv), _mcentroidsv(&_centroidsv){
00075         }
00076         inline
00077         void init(int nlabels){
00078             _mstatsv->create(cv::Size(CC_STAT_MAX, nlabels), cv::DataType<int>::type);
00079             statsv = _mstatsv->getMat();
00080             _mcentroidsv->create(cv::Size(2, nlabels), cv::DataType<double>::type);
00081             centroidsv = _mcentroidsv->getMat();
00082 
00083             for(int l = 0; l < (int) nlabels; ++l){
00084                 int *row = (int *) &statsv.at<int>(l, 0);
00085                 row[CC_STAT_LEFT] = INT_MAX;
00086                 row[CC_STAT_TOP] = INT_MAX;
00087                 row[CC_STAT_WIDTH] = INT_MIN;
00088                 row[CC_STAT_HEIGHT] = INT_MIN;
00089                 row[CC_STAT_AREA] = 0;
00090             }
00091             integrals.resize(nlabels, Point2ui64(0, 0));
00092         }
00093         void operator()(int r, int c, int l){
00094             int *row = &statsv.at<int>(l, 0);
00095             row[CC_STAT_LEFT] = MIN(row[CC_STAT_LEFT], c);
00096             row[CC_STAT_WIDTH] = MAX(row[CC_STAT_WIDTH], c);
00097             row[CC_STAT_TOP] = MIN(row[CC_STAT_TOP], r);
00098             row[CC_STAT_HEIGHT] = MAX(row[CC_STAT_HEIGHT], r);
00099             row[CC_STAT_AREA]++;
00100             Point2ui64 &integral  = integrals[l];
00101             integral.x += c;
00102             integral.y += r;
00103         }
00104         void finish(){
00105             for(int l = 0; l < statsv.rows; ++l){
00106                 int *row = &statsv.at<int>(l, 0);
00107                 row[CC_STAT_WIDTH] = row[CC_STAT_WIDTH] - row[CC_STAT_LEFT] + 1;
00108                 row[CC_STAT_HEIGHT] = row[CC_STAT_HEIGHT] - row[CC_STAT_TOP] + 1;
00109 
00110                 Point2ui64 &integral  = integrals[l];
00111                 double *centroid = &centroidsv.at<double>(l, 0);
00112                 double area = ((unsigned*)row)[CC_STAT_AREA];
00113                 centroid[0] = double(integral.x) / area;
00114                 centroid[1] = double(integral.y) / area;
00115             }
00116         }
00117     };
00118 
00119     //Find the root of the tree of node i
00120     template<typename LabelT>
00121     inline static
00122     LabelT findRoot(const LabelT *P, LabelT i){
00123         LabelT root = i;
00124         while(P[root] < root){
00125             root = P[root];
00126         }
00127         return root;
00128     }
00129 
00130     //Make all nodes in the path of node i point to root
00131     template<typename LabelT>
00132     inline static
00133     void setRoot(LabelT *P, LabelT i, LabelT root){
00134         while(P[i] < i){
00135             LabelT j = P[i];
00136             P[i] = root;
00137             i = j;
00138         }
00139         P[i] = root;
00140     }
00141 
00142     //Find the root of the tree of the node i and compress the path in the process
00143     template<typename LabelT>
00144     inline static
00145     LabelT find(LabelT *P, LabelT i){
00146         LabelT root = findRoot(P, i);
00147         setRoot(P, i, root);
00148         return root;
00149     }
00150 
00151     //unite the two trees containing nodes i and j and return the new root
00152     template<typename LabelT>
00153     inline static
00154     LabelT set_union(LabelT *P, LabelT i, LabelT j){
00155         LabelT root = findRoot(P, i);
00156         if(i != j){
00157             LabelT rootj = findRoot(P, j);
00158             if(root > rootj){
00159                 root = rootj;
00160             }
00161             setRoot(P, j, root);
00162         }
00163         setRoot(P, i, root);
00164         return root;
00165     }
00166 
00167     //Flatten the Union Find tree and relabel the components
00168     template<typename LabelT>
00169     inline static
00170     LabelT flattenL(LabelT *P, LabelT length){
00171         LabelT k = 1;
00172         for(LabelT i = 1; i < length; ++i){
00173             if(P[i] < i){
00174                 P[i] = P[P[i]];
00175             }else{
00176                 P[i] = k; k = k + 1;
00177             }
00178         }
00179         return k;
00180     }
00181 
00182     //Based on "Two Strategies to Speed up Connected Components Algorithms", the SAUF (Scan array union find) variant
00183     //using decision trees
00184     //Kesheng Wu, et al
00185     //Note: rows are encoded as position in the "rows" array to save lookup times
00186     //reference for 4-way: {{-1, 0}, {0, -1}};//b, d neighborhoods
00187     const int G4[2][2] = {{1, 0}, {0, -1}};//b, d neighborhoods
00188     //reference for 8-way: {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}};//a, b, c, d neighborhoods
00189     const int G8[4][2] = {{1, -1}, {1, 0}, {1, 1}, {0, -1}};//a, b, c, d neighborhoods
00190     template<typename LabelT, typename PixelT, typename StatsOp = NoOp >
00191     struct LabelingImpl{
00192     LabelT operator()(const cv::Mat &I, cv::Mat &L, int connectivity, StatsOp &sop){
00193         CV_Assert(L.rows == I.rows);
00194         CV_Assert(L.cols == I.cols);
00195         CV_Assert(connectivity == 8 || connectivity == 4);
00196         const int rows = L.rows;
00197         const int cols = L.cols;
00198         //A quick and dirty upper bound for the maximimum number of labels.  The 4 comes from
00199         //the fact that a 3x3 block can never have more than 4 unique labels for both 4 & 8-way
00200         const size_t Plength = 4 * (size_t(rows + 3 - 1)/3) * (size_t(cols + 3 - 1)/3);
00201         LabelT *P = (LabelT *) fastMalloc(sizeof(LabelT) * Plength);
00202         P[0] = 0;
00203         LabelT lunique = 1;
00204         //scanning phase
00205         for(int r_i = 0; r_i < rows; ++r_i){
00206             LabelT * const Lrow = L.ptr<LabelT>(r_i);
00207             LabelT * const Lrow_prev = (LabelT *)(((char *)Lrow) - L.step.p[0]);
00208             const PixelT * const Irow = I.ptr<PixelT>(r_i);
00209             const PixelT * const Irow_prev = (const PixelT *)(((char *)Irow) - I.step.p[0]);
00210             LabelT *Lrows[2] = {
00211                 Lrow,
00212                 Lrow_prev
00213             };
00214             const PixelT *Irows[2] = {
00215                 Irow,
00216                 Irow_prev
00217             };
00218             if(connectivity == 8){
00219                 const int a = 0;
00220                 const int b = 1;
00221                 const int c = 2;
00222                 const int d = 3;
00223                 const bool T_a_r = (r_i - G8[a][0]) >= 0;
00224                 const bool T_b_r = (r_i - G8[b][0]) >= 0;
00225                 const bool T_c_r = (r_i - G8[c][0]) >= 0;
00226                 for(int c_i = 0; Irows[0] != Irow + cols; ++Irows[0], c_i++){
00227                     if(!*Irows[0]){
00228                         Lrow[c_i] = 0;
00229                         continue;
00230                     }
00231                     Irows[1] = Irow_prev + c_i;
00232                     Lrows[0] = Lrow + c_i;
00233                     Lrows[1] = Lrow_prev + c_i;
00234                     const bool T_a = T_a_r && (c_i + G8[a][1]) >= 0   && *(Irows[G8[a][0]] + G8[a][1]);
00235                     const bool T_b = T_b_r                            && *(Irows[G8[b][0]] + G8[b][1]);
00236                     const bool T_c = T_c_r && (c_i + G8[c][1]) < cols && *(Irows[G8[c][0]] + G8[c][1]);
00237                     const bool T_d =          (c_i + G8[d][1]) >= 0   && *(Irows[G8[d][0]] + G8[d][1]);
00238 
00239                     //decision tree
00240                     if(T_b){
00241                         //copy(b)
00242                         *Lrows[0] = *(Lrows[G8[b][0]] + G8[b][1]);
00243                     }else{//not b
00244                         if(T_c){
00245                             if(T_a){
00246                                 //copy(c, a)
00247                                 *Lrows[0] = set_union(P, *(Lrows[G8[c][0]] + G8[c][1]), *(Lrows[G8[a][0]] + G8[a][1]));
00248                             }else{
00249                                 if(T_d){
00250                                     //copy(c, d)
00251                                     *Lrows[0] = set_union(P, *(Lrows[G8[c][0]] + G8[c][1]), *(Lrows[G8[d][0]] + G8[d][1]));
00252                                 }else{
00253                                     //copy(c)
00254                                     *Lrows[0] = *(Lrows[G8[c][0]] + G8[c][1]);
00255                                 }
00256                             }
00257                         }else{//not c
00258                             if(T_a){
00259                                 //copy(a)
00260                                 *Lrows[0] = *(Lrows[G8[a][0]] + G8[a][1]);
00261                             }else{
00262                                 if(T_d){
00263                                     //copy(d)
00264                                     *Lrows[0] = *(Lrows[G8[d][0]] + G8[d][1]);
00265                                 }else{
00266                                     //new label
00267                                     *Lrows[0] = lunique;
00268                                     P[lunique] = lunique;
00269                                     lunique = lunique + 1;
00270                                 }
00271                             }
00272                         }
00273                     }
00274                 }
00275             }else{
00276                 //B & D only
00277                 const int b = 0;
00278                 const int d = 1;
00279                 const bool T_b_r = (r_i - G4[b][0]) >= 0;
00280                 for(int c_i = 0; Irows[0] != Irow + cols; ++Irows[0], c_i++){
00281                     if(!*Irows[0]){
00282                         Lrow[c_i] = 0;
00283                         continue;
00284                     }
00285                     Irows[1] = Irow_prev + c_i;
00286                     Lrows[0] = Lrow + c_i;
00287                     Lrows[1] = Lrow_prev + c_i;
00288                     const bool T_b = T_b_r                            && *(Irows[G4[b][0]] + G4[b][1]);
00289                     const bool T_d =          (c_i + G4[d][1]) >= 0   && *(Irows[G4[d][0]] + G4[d][1]);
00290                     if(T_b){
00291                         if(T_d){
00292                             //copy(d, b)
00293                             *Lrows[0] = set_union(P, *(Lrows[G4[d][0]] + G4[d][1]), *(Lrows[G4[b][0]] + G4[b][1]));
00294                         }else{
00295                             //copy(b)
00296                             *Lrows[0] = *(Lrows[G4[b][0]] + G4[b][1]);
00297                         }
00298                     }else{
00299                         if(T_d){
00300                             //copy(d)
00301                             *Lrows[0] = *(Lrows[G4[d][0]] + G4[d][1]);
00302                         }else{
00303                             //new label
00304                             *Lrows[0] = lunique;
00305                             P[lunique] = lunique;
00306                             lunique = lunique + 1;
00307                         }
00308                     }
00309                 }
00310             }
00311         }
00312 
00313         //analysis
00314         LabelT nLabels = flattenL(P, lunique);
00315         sop.init(nLabels);
00316 
00317         for(int r_i = 0; r_i < rows; ++r_i){
00318             LabelT *Lrow_start = L.ptr<LabelT>(r_i);
00319             LabelT *Lrow_end = Lrow_start + cols;
00320             LabelT *Lrow = Lrow_start;
00321             for(int c_i = 0; Lrow != Lrow_end; ++Lrow, ++c_i){
00322                 const LabelT l = P[*Lrow];
00323                 *Lrow = l;
00324                 sop(r_i, c_i, l);
00325             }
00326         }
00327 
00328         sop.finish();
00329         fastFree(P);
00330 
00331         return nLabels;
00332     }//End function LabelingImpl operator()
00333 
00334     };//End struct LabelingImpl
00335 }//end namespace connectedcomponents
00336 
00337 //L's type must have an appropriate depth for the number of pixels in I
00338 template<typename StatsOp>
00339 static
00340 int connectedComponents_sub1(const cv::Mat &I, cv::Mat &L, int connectivity, StatsOp &sop){
00341     CV_Assert(L.channels() == 1 && I.channels() == 1);
00342     CV_Assert(connectivity == 8 || connectivity == 4);
00343 
00344     int lDepth = L.depth();
00345     int iDepth = I.depth();
00346     using connectedcomponents::LabelingImpl;
00347     //warn if L's depth is not sufficient?
00348 
00349     CV_Assert(iDepth == CV_8U || iDepth == CV_8S);
00350 
00351     if(lDepth == CV_8U){
00352         return (int) LabelingImpl<uchar, uchar, StatsOp>()(I, L, connectivity, sop);
00353     }else if(lDepth == CV_16U){
00354         return (int) LabelingImpl<ushort, uchar, StatsOp>()(I, L, connectivity, sop);
00355     }else if(lDepth == CV_32S){
00356         //note that signed types don't really make sense here and not being able to use unsigned matters for scientific projects
00357         //OpenCV: how should we proceed?  .at<T> typechecks in debug mode
00358         return (int) LabelingImpl<int, uchar, StatsOp>()(I, L, connectivity, sop);
00359     }
00360 
00361     CV_Error(CV_StsUnsupportedFormat, "unsupported label/image type");
00362     return -1;
00363 }
00364 
00365 }
00366 
00367 int cv::connectedComponents(InputArray _img, OutputArray _labels, int connectivity, int ltype){
00368     const cv::Mat img = _img.getMat();
00369     _labels.create(img.size(), CV_MAT_DEPTH(ltype));
00370     cv::Mat labels = _labels.getMat();
00371     connectedcomponents::NoOp sop;
00372     if(ltype == CV_16U){
00373         return connectedComponents_sub1(img, labels, connectivity, sop);
00374     }else if(ltype == CV_32S){
00375         return connectedComponents_sub1(img, labels, connectivity, sop);
00376     }else{
00377         CV_Error(CV_StsUnsupportedFormat, "the type of labels must be 16u or 32s");
00378         return 0;
00379     }
00380 }
00381 
00382 int cv::connectedComponentsWithStats(InputArray _img, OutputArray _labels, OutputArray statsv,
00383                                      OutputArray centroids, int connectivity, int ltype)
00384 {
00385     const cv::Mat img = _img.getMat();
00386     _labels.create(img.size(), CV_MAT_DEPTH(ltype));
00387     cv::Mat labels = _labels.getMat();
00388     connectedcomponents::CCStatsOp sop(statsv, centroids);
00389     if(ltype == CV_16U){
00390         return connectedComponents_sub1(img, labels, connectivity, sop);
00391     }else if(ltype == CV_32S){
00392         return connectedComponents_sub1(img, labels, connectivity, sop);
00393     }else{
00394         CV_Error(CV_StsUnsupportedFormat, "the type of labels must be 16u or 32s");
00395         return 0;
00396     }
00397 }
00398