From 4c0cb2576d588b641b3496628eb2c07cfeedb7b6 Mon Sep 17 00:00:00 2001 From: Jason Newton Date: Sat, 25 Aug 2012 02:31:52 -0700 Subject: [PATCH] connectedComponents: peep-hole optimizations, mostly surrouding the fact that cv::Mat::at is expensive in a tight-loop -also added a "blobstats" version --- .../imgproc/include/opencv2/imgproc/imgproc.hpp | 17 +- modules/imgproc/src/connectedcomponents.cpp | 354 ++++++++++++++------- samples/cpp/connected_components.cpp | 2 +- 3 files changed, 252 insertions(+), 121 deletions(-) diff --git a/modules/imgproc/include/opencv2/imgproc/imgproc.hpp b/modules/imgproc/include/opencv2/imgproc/imgproc.hpp index 3d80cfe..0cb761b 100644 --- a/modules/imgproc/include/opencv2/imgproc/imgproc.hpp +++ b/modules/imgproc/include/opencv2/imgproc/imgproc.hpp @@ -1091,9 +1091,24 @@ enum { TM_SQDIFF=0, TM_SQDIFF_NORMED=1, TM_CCORR=2, TM_CCORR_NORMED=3, TM_CCOEFF CV_EXPORTS_W void matchTemplate( InputArray image, InputArray templ, OutputArray result, int method ); + +struct CV_EXPORTS ConnectedComponentStats +{ + int32_t lower_x; + int32_t lower_y; + int32_t upper_x; + int32_t upper_y; + double centroid_x; + double centroid_y; + uint64_t integral_x; + uint64_t integral_y; + uint32_t area; +}; //! computes the connected components labeled image of boolean image I with 4 or 8 way connectivity - returns N, the total -//number of labels [0, N-1] where 0 represents the background label. +//number of labels [0, N-1] where 0 represents the background label. L's value type determines the label type, an important +//consideration based on the total number of labels or alternatively the total number of pixels. CV_EXPORTS_W uint64_t connectedComponents(Mat &L, const Mat &I, int connectivity = 8); +CV_EXPORTS_W uint64_t connectedComponents(Mat &L, const Mat &I, std::vector &statsv, int connectivity = 8); //! mode of the contour retrieval algorithm diff --git a/modules/imgproc/src/connectedcomponents.cpp b/modules/imgproc/src/connectedcomponents.cpp index cc83f97..50a1ca1 100644 --- a/modules/imgproc/src/connectedcomponents.cpp +++ b/modules/imgproc/src/connectedcomponents.cpp @@ -41,15 +41,81 @@ //M*/ // #include "precomp.hpp" +#include namespace cv{ namespace connectedcomponents{ - using std::vector; + + template + struct NoOp{ + NoOp(){ + } + void init(const LabelT labels){ + (void) labels; + } + inline + void operator()(int r, int c, LabelT l){ + (void) r; + (void) c; + (void) l; + } + void finish(){} + }; + template + struct CCStatsOp{ + std::vector &statsv; + CCStatsOp(std::vector &_statsv): statsv(_statsv){ + } + inline + void init(const LabelT nlabels){ + statsv.clear(); + cv::ConnectedComponentStats stats = cv::ConnectedComponentStats(); + stats.lower_x = std::numeric_limits::max(); + stats.lower_y = std::numeric_limits::max(); + stats.upper_x = std::numeric_limits::min(); + stats.upper_y = std::numeric_limits::min(); + stats.centroid_x = 0; + stats.centroid_y = 0; + stats.integral_x = 0; + stats.integral_y = 0; + stats.area = 0; + statsv.resize(nlabels, stats); + } + void operator()(int r, int c, LabelT l){ + ConnectedComponentStats &stats = statsv[l]; + if(c > stats.upper_x){ + stats.upper_x = c; + }else{ + if(c < stats.lower_x){ + stats.lower_x = c; + } + } + if(r > stats.upper_y){ + stats.upper_y = r; + }else{ + if(r < stats.lower_y){ + stats.lower_y = r; + } + } + stats.integral_x += c; + stats.integral_y += r; + stats.area++; + } + void finish(){ + for(size_t l = 0; l < statsv.size(); ++l){ + ConnectedComponentStats &stats = statsv[l]; + stats.lower_x = std::min(stats.lower_x, stats.upper_x); + stats.lower_y = std::min(stats.lower_y, stats.upper_y); + stats.centroid_x = stats.integral_x / double(stats.area); + stats.centroid_y = stats.integral_y / double(stats.area); + } + } + }; //Find the root of the tree of node i template inline static - LabelT findRoot(const vector &P, LabelT i){ + LabelT findRoot(const LabelT *P, LabelT i){ LabelT root = i; while(P[root] < root){ root = P[root]; @@ -60,7 +126,7 @@ namespace cv{ //Make all nodes in the path of node i point to root template inline static - void setRoot(vector &P, LabelT i, LabelT root){ + void setRoot(LabelT *P, LabelT i, LabelT root){ while(P[i] < i){ LabelT j = P[i]; P[i] = root; @@ -72,7 +138,7 @@ namespace cv{ //Find the root of the tree of the node i and compress the path in the process template inline static - LabelT find(vector &P, LabelT i){ + LabelT find(LabelT *P, LabelT i){ LabelT root = findRoot(P, i); setRoot(P, i, root); return root; @@ -81,7 +147,7 @@ namespace cv{ //unite the two trees containing nodes i and j and return the new root template inline static - LabelT set_union(vector &P, LabelT i, LabelT j){ + LabelT set_union(LabelT *P, LabelT i, LabelT j){ LabelT root = findRoot(P, i); if(i != j){ LabelT rootj = findRoot(P, j); @@ -97,9 +163,9 @@ namespace cv{ //Flatten the Union Find tree and relabel the components template inline static - LabelT flattenL(vector &P){ + LabelT flattenL(LabelT *P, LabelT length){ LabelT k = 1; - for(size_t i = 1; i < P.size(); ++i){ + for(LabelT i = 1; i < length; ++i){ if(P[i] < i){ P[i] = P[P[i]]; }else{ @@ -109,137 +175,155 @@ namespace cv{ return k; } - ////Flatten the Union Find tree - inconsistent labels - //void flatten(int P[], int size){ - // for(int i = 1; i < size; ++i){ - // P[i] = P[P[i]]; - // } - //} - const int G4[2][2] = {{-1, 0}, {0, -1}};//b, d neighborhoods - const int G8[4][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}};//a, b, c, d neighborhoods //Based on "Two Strategies to Speed up Connected Components Algorithms", the SAUF (Scan array union find) variant //using decision trees //Kesheng Wu, et al - template + //Note: rows are encoded as position in the "rows" array to save lookup times + //reference for 4-way: {{-1, 0}, {0, -1}};//b, d neighborhoods + const int G4[2][2] = {{1, 0}, {0, -1}};//b, d neighborhoods + //reference for 8-way: {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}};//a, b, c, d neighborhoods + const int G8[4][2] = {{1, -1}, {1, 0}, {1, 1}, {0, -1}};//a, b, c, d neighborhoods + template, int connectivity = 8> struct LabelingImpl{ - LabelT operator()(Mat &L, const Mat &I){ + LabelT operator()(Mat &L, const Mat &I, StatsOp &sop){ const int rows = L.rows; const int cols = L.cols; - size_t nPixels = size_t(rows) * cols; - vector P; P.push_back(0); - LabelT l = 1; + size_t Plength = (size_t(rows + 3 - 1)/3) * (size_t(cols + 3 - 1)/3); + if(connectivity == 4){ + Plength = 4 * Plength;//a quick and dirty upper bound, an exact answer exists if you want to find it + //the 4 comes from the fact that a 3x3 block can never have more than 4 unique labels + } + LabelT *P = (LabelT *) fastMalloc(sizeof(LabelT) * Plength); + P[0] = 0; + LabelT lunique = 1; //scanning phase for(int r_i = 0; r_i < rows; ++r_i){ - for(int c_i = 0; c_i < cols; ++c_i){ - if(!I.at(r_i, c_i)){ - L.at(r_i, c_i) = 0; - continue; - } - if(connectivity == 8){ - const int a = 0; - const int b = 1; - const int c = 2; - const int d = 3; - - bool T[4]; - - for(size_t i = 0; i < 4; ++i){ - int gr = r_i + G8[i][0]; - int gc = c_i + G8[i][1]; - T[i] = false; - if(gr >= 0 && gr < rows && gc >= 0 && gc < cols){ - if(I.at(gr, gc)){ - T[i] = true; - } - } + LabelT *Lrow = (LabelT *)(L.data + L.step.p[0] * r_i); + LabelT *Lrow_prev = (LabelT *)(((char *)Lrow) - L.step.p[0]); + const PixelT *Irow = (PixelT *)(I.data + I.step.p[0] * r_i); + const PixelT *Irow_prev = (const PixelT *)(((char *)Irow) - I.step.p[0]); + LabelT *Lrows[2] = { + Lrow, + Lrow_prev + }; + const PixelT *Irows[2] = { + Irow, + Irow_prev + }; + if(connectivity == 8){ + const int a = 0; + const int b = 1; + const int c = 2; + const int d = 3; + const bool T_a_r = (r_i - G8[a][0]) >= 0; + const bool T_b_r = (r_i - G8[b][0]) >= 0; + const bool T_c_r = (r_i - G8[c][0]) >= 0; + for(int c_i = 0; Irows[0] != Irow + cols; ++Irows[0], c_i++){ + if(!*Irows[0]){ + Lrow[c_i] = 0; + continue; } + Irows[1] = Irow_prev + c_i; + Lrows[0] = Lrow + c_i; + Lrows[1] = Lrow_prev + c_i; + const bool T_a = T_a_r && (c_i + G8[a][1]) >= 0 && *(Irows[G8[a][0]] + G8[a][1]); + const bool T_b = T_b_r && *(Irows[G8[b][0]] + G8[b][1]); + const bool T_c = T_c_r && (c_i + G8[c][1]) < cols && *(Irows[G8[c][0]] + G8[c][1]); + const bool T_d = (c_i + G8[d][1]) >= 0 && *(Irows[G8[d][0]] + G8[d][1]); //decision tree - if(T[b]){ + if(T_b){ //copy(b) - L.at(r_i, c_i) = L.at(r_i + G8[b][0], c_i + G8[b][1]); + *Lrows[0] = *(Lrows[G8[b][0]] + G8[b][1]); }else{//not b - if(T[c]){ - if(T[a]){ + if(T_c){ + if(T_a){ //copy(c, a) - L.at(r_i, c_i) = set_union(P, L.at(r_i + G8[c][0], c_i + G8[c][1]), L.at(r_i + G8[a][0], c_i + G8[a][1])); + *Lrows[0] = set_union(P, *(Lrows[G8[c][0]] + G8[c][1]), *(Lrows[G8[a][0]] + G8[a][1])); }else{ - if(T[d]){ + if(T_d){ //copy(c, d) - L.at(r_i, c_i) = set_union(P, L.at(r_i + G8[c][0], c_i + G8[c][1]), L.at(r_i + G8[d][0], c_i + G8[d][1])); + *Lrows[0] = set_union(P, *(Lrows[G8[c][0]] + G8[c][1]), *(Lrows[G8[d][0]] + G8[d][1])); }else{ //copy(c) - L.at(r_i, c_i) = L.at(r_i + G8[c][0], c_i + G8[c][1]); + *Lrows[0] = *(Lrows[G8[c][0]] + G8[c][1]); } } }else{//not c - if(T[a]){ + if(T_a){ //copy(a) - L.at(r_i, c_i) = L.at(r_i + G8[a][0], c_i + G8[a][1]); + *Lrows[0] = *(Lrows[G8[a][0]] + G8[a][1]); }else{ - if(T[d]){ + if(T_d){ //copy(d) - L.at(r_i, c_i) = L.at(r_i + G8[d][0], c_i + G8[d][1]); + *Lrows[0] = *(Lrows[G8[d][0]] + G8[d][1]); }else{ //new label - L.at(r_i, c_i) = l; - P.push_back(l);//P[l] = l; - l = l + 1; + *Lrows[0] = lunique; + P[lunique] = lunique; + lunique = lunique + 1; } } } } - }else{ - //B & D only - const int b = 0; - const int d = 1; - assert(connectivity == 4); - bool T[2]; - for(size_t i = 0; i < 2; ++i){ - int gr = r_i + G4[i][0]; - int gc = c_i + G4[i][1]; - T[i] = false; - if(gr >= 0 && gr < rows && gc >= 0 && gc < cols){ - if(I.at(gr, gc)){ - T[i] = true; - } - } + } + }else{ + //B & D only + assert(connectivity == 4); + const int b = 0; + const int d = 1; + const bool T_b_r = (r_i - G4[b][0]) >= 0; + for(int c_i = 0; Irows[0] != Irow + cols; ++Irows[0], c_i++){ + if(!*Irows[0]){ + Lrow[c_i] = 0; + continue; } - - if(T[b]){ - if(T[d]){ + Irows[1] = Irow_prev + c_i; + Lrows[0] = Lrow + c_i; + Lrows[1] = Lrow_prev + c_i; + const bool T_b = T_b_r && *(Irows[G4[b][0]] + G4[b][1]); + const bool T_d = (c_i + G4[d][1]) >= 0 && *(Irows[G4[d][0]] + G4[d][1]); + if(T_b){ + if(T_d){ //copy(d, b) - L.at(r_i, c_i) = set_union(P, L.at(r_i + G4[d][0], c_i + G4[d][1]), L.at(r_i + G4[b][0], c_i + G4[b][1])); + *Lrows[0] = set_union(P, *(Lrows[G4[d][0]] + G4[d][1]), *(Lrows[G4[b][0]] + G4[b][1])); }else{ //copy(b) - L.at(r_i, c_i) = L.at(r_i + G4[b][0], c_i + G4[b][1]); + *Lrows[0] = *(Lrows[G4[b][0]] + G4[b][1]); } }else{ - if(T[d]){ + if(T_d){ //copy(d) - L.at(r_i, c_i) = L.at(r_i + G4[d][0], c_i + G4[d][1]); + *Lrows[0] = *(Lrows[G4[d][0]] + G4[d][1]); }else{ //new label - L.at(r_i, c_i) = l; - P.push_back(l);//P[l] = l; - l = l + 1; + *Lrows[0] = lunique; + P[lunique] = lunique; + lunique = lunique + 1; } } - } } } //analysis - LabelT nLabels = flattenL(P); + LabelT nLabels = flattenL(P, lunique); + sop.init(nLabels); - //assign final labels - for(size_t r = 0; r < rows; ++r){ - for(size_t c = 0; c < cols; ++c){ - L.at(r, c) = P[L.at(r, c)]; + for(int r_i = 0; r_i < rows; ++r_i){ + LabelT *Lrow_start = (LabelT *)(L.data + L.step.p[0] * r_i); + LabelT *Lrow_end = Lrow_start + cols; + LabelT *Lrow = Lrow_start; + for(int c_i = 0; Lrow != Lrow_end; ++Lrow, ++c_i){ + const LabelT l = P[*Lrow]; + *Lrow = l; + sop(r_i, c_i, l); } } + sop.finish(); + fastFree(P); + return nLabels; }//End function LabelingImpl operator() @@ -247,7 +331,8 @@ namespace cv{ }//end namespace connectedcomponents //L's type must have an appropriate depth for the number of pixels in I -uint64_t connectedComponents(Mat &L, const Mat &I, int connectivity){ +template +uint64_t connectedComponents_sub1(Mat &L, const Mat &I, int connectivity, StatsOp &sop){ CV_Assert(L.rows == I.rows); CV_Assert(L.cols == I.cols); CV_Assert(L.channels() == 1 && I.channels() == 1); @@ -261,98 +346,102 @@ uint64_t connectedComponents(Mat &L, const Mat &I, int connectivity){ if(lDepth == CV_8U){ if(iDepth == CV_8U || iDepth == CV_8S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_16U || iDepth == CV_16S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_32S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_32F){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_64F){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } } }else if(lDepth == CV_16U){ if(iDepth == CV_8U || iDepth == CV_8S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_16U || iDepth == CV_16S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_32S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_32F){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_64F){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } } }else if(lDepth == CV_32S){ + //note that signed types don't really make sense here and not being able to use uint32_t matters for scientific projects + //OpenCV: how should we proceed? .at typechecks in debug mode if(iDepth == CV_8U || iDepth == CV_8S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_16U || iDepth == CV_16S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_32S){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_32F){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } }else if(iDepth == CV_64F){ if(connectivity == 4){ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); }else{ - return (uint64_t) LabelingImpl()(L, I); + return (uint64_t) LabelingImpl()(L, I, sop); } + }else{ + CV_Assert(false); } } @@ -360,6 +449,33 @@ uint64_t connectedComponents(Mat &L, const Mat &I, int connectivity){ return -1; } +uint64_t connectedComponents(Mat &L, const Mat &I, int connectivity){ + int lDepth = L.depth(); + if(lDepth == CV_8U){ + connectedcomponents::NoOp sop; return connectedComponents_sub1(L, I, connectivity, sop); + }else if(lDepth == CV_16U){ + connectedcomponents::NoOp sop; return connectedComponents_sub1(L, I, connectivity, sop); + }else if(lDepth == CV_32S){ + connectedcomponents::NoOp sop; return connectedComponents_sub1(L, I, connectivity, sop); + }else{ + CV_Assert(false); + return 0; + } +} + +uint64_t connectedComponents(Mat &L, const Mat &I, std::vector &statsv, int connectivity){ + int lDepth = L.depth(); + if(lDepth == CV_8U){ + connectedcomponents::CCStatsOp sop(statsv); return connectedComponents_sub1(L, I, connectivity, sop); + }else if(lDepth == CV_16U){ + connectedcomponents::CCStatsOp sop(statsv); return connectedComponents_sub1(L, I, connectivity, sop); + }else if(lDepth == CV_32S){ + connectedcomponents::CCStatsOp sop(statsv); return connectedComponents_sub1(L, I, connectivity, sop); + }else{ + CV_Assert(false); + return 0; + } +} } diff --git a/samples/cpp/connected_components.cpp b/samples/cpp/connected_components.cpp index 6d3357f..7b362df 100644 --- a/samples/cpp/connected_components.cpp +++ b/samples/cpp/connected_components.cpp @@ -12,7 +12,7 @@ static void on_trackbar(int, void*) { Mat bw = threshval < 128 ? (img < threshval) : (img > threshval); Mat labelImage(img.size(), CV_32S); - int nLabels = connectedComponents(labelImage, bw, 8); + uint64_t nLabels = connectedComponents(labelImage, bw, 8); Vec3b colors[nLabels]; colors[0] = Vec3b(0, 0, 0);//background for(int label = 1; label < nLabels; ++label){ -- 2.7.4