1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
8 //
9 //
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
15 //
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
18 //
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
21 //
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
25 //
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
28 //
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
39 //
40 // 2011 Jason Newton <nevion@gmail.com>
41 //M*/
42 //
43 #include "precomp.hpp"
44 #include <vector>
45
46 namespace cv{
47 namespace connectedcomponents{
48
49 struct NoOp{
NoOpcv::connectedcomponents::NoOp50 NoOp(){
51 }
initcv::connectedcomponents::NoOp52 void init(int /*labels*/){
53 }
54 inline
operator ()cv::connectedcomponents::NoOp55 void operator()(int r, int c, int l){
56 (void) r;
57 (void) c;
58 (void) l;
59 }
finishcv::connectedcomponents::NoOp60 void finish(){}
61 };
62 struct Point2ui64{
63 uint64 x, y;
Point2ui64cv::connectedcomponents::Point2ui6464 Point2ui64(uint64 _x, uint64 _y):x(_x), y(_y){}
65 };
66
67 struct CCStatsOp{
68 const _OutputArray* _mstatsv;
69 cv::Mat statsv;
70 const _OutputArray* _mcentroidsv;
71 cv::Mat centroidsv;
72 std::vector<Point2ui64> integrals;
73
CCStatsOpcv::connectedcomponents::CCStatsOp74 CCStatsOp(OutputArray _statsv, OutputArray _centroidsv): _mstatsv(&_statsv), _mcentroidsv(&_centroidsv){
75 }
76 inline
initcv::connectedcomponents::CCStatsOp77 void init(int nlabels){
78 _mstatsv->create(cv::Size(CC_STAT_MAX, nlabels), cv::DataType<int>::type);
79 statsv = _mstatsv->getMat();
80 _mcentroidsv->create(cv::Size(2, nlabels), cv::DataType<double>::type);
81 centroidsv = _mcentroidsv->getMat();
82
83 for(int l = 0; l < (int) nlabels; ++l){
84 int *row = (int *) &statsv.at<int>(l, 0);
85 row[CC_STAT_LEFT] = INT_MAX;
86 row[CC_STAT_TOP] = INT_MAX;
87 row[CC_STAT_WIDTH] = INT_MIN;
88 row[CC_STAT_HEIGHT] = INT_MIN;
89 row[CC_STAT_AREA] = 0;
90 }
91 integrals.resize(nlabels, Point2ui64(0, 0));
92 }
operator ()cv::connectedcomponents::CCStatsOp93 void operator()(int r, int c, int l){
94 int *row = &statsv.at<int>(l, 0);
95 row[CC_STAT_LEFT] = MIN(row[CC_STAT_LEFT], c);
96 row[CC_STAT_WIDTH] = MAX(row[CC_STAT_WIDTH], c);
97 row[CC_STAT_TOP] = MIN(row[CC_STAT_TOP], r);
98 row[CC_STAT_HEIGHT] = MAX(row[CC_STAT_HEIGHT], r);
99 row[CC_STAT_AREA]++;
100 Point2ui64 &integral = integrals[l];
101 integral.x += c;
102 integral.y += r;
103 }
finishcv::connectedcomponents::CCStatsOp104 void finish(){
105 for(int l = 0; l < statsv.rows; ++l){
106 int *row = &statsv.at<int>(l, 0);
107 row[CC_STAT_WIDTH] = row[CC_STAT_WIDTH] - row[CC_STAT_LEFT] + 1;
108 row[CC_STAT_HEIGHT] = row[CC_STAT_HEIGHT] - row[CC_STAT_TOP] + 1;
109
110 Point2ui64 &integral = integrals[l];
111 double *centroid = ¢roidsv.at<double>(l, 0);
112 double area = ((unsigned*)row)[CC_STAT_AREA];
113 centroid[0] = double(integral.x) / area;
114 centroid[1] = double(integral.y) / area;
115 }
116 }
117 };
118
119 //Find the root of the tree of node i
120 template<typename LabelT>
121 inline static
findRoot(const LabelT * P,LabelT i)122 LabelT findRoot(const LabelT *P, LabelT i){
123 LabelT root = i;
124 while(P[root] < root){
125 root = P[root];
126 }
127 return root;
128 }
129
130 //Make all nodes in the path of node i point to root
131 template<typename LabelT>
132 inline static
setRoot(LabelT * P,LabelT i,LabelT root)133 void setRoot(LabelT *P, LabelT i, LabelT root){
134 while(P[i] < i){
135 LabelT j = P[i];
136 P[i] = root;
137 i = j;
138 }
139 P[i] = root;
140 }
141
142 //Find the root of the tree of the node i and compress the path in the process
143 template<typename LabelT>
144 inline static
find(LabelT * P,LabelT i)145 LabelT find(LabelT *P, LabelT i){
146 LabelT root = findRoot(P, i);
147 setRoot(P, i, root);
148 return root;
149 }
150
151 //unite the two trees containing nodes i and j and return the new root
152 template<typename LabelT>
153 inline static
set_union(LabelT * P,LabelT i,LabelT j)154 LabelT set_union(LabelT *P, LabelT i, LabelT j){
155 LabelT root = findRoot(P, i);
156 if(i != j){
157 LabelT rootj = findRoot(P, j);
158 if(root > rootj){
159 root = rootj;
160 }
161 setRoot(P, j, root);
162 }
163 setRoot(P, i, root);
164 return root;
165 }
166
167 //Flatten the Union Find tree and relabel the components
168 template<typename LabelT>
169 inline static
flattenL(LabelT * P,LabelT length)170 LabelT flattenL(LabelT *P, LabelT length){
171 LabelT k = 1;
172 for(LabelT i = 1; i < length; ++i){
173 if(P[i] < i){
174 P[i] = P[P[i]];
175 }else{
176 P[i] = k; k = k + 1;
177 }
178 }
179 return k;
180 }
181
182 //Based on "Two Strategies to Speed up Connected Components Algorithms", the SAUF (Scan array union find) variant
183 //using decision trees
184 //Kesheng Wu, et al
185 //Note: rows are encoded as position in the "rows" array to save lookup times
186 //reference for 4-way: {{-1, 0}, {0, -1}};//b, d neighborhoods
187 const int G4[2][2] = {{1, 0}, {0, -1}};//b, d neighborhoods
188 //reference for 8-way: {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}};//a, b, c, d neighborhoods
189 const int G8[4][2] = {{1, -1}, {1, 0}, {1, 1}, {0, -1}};//a, b, c, d neighborhoods
190 template<typename LabelT, typename PixelT, typename StatsOp = NoOp >
191 struct LabelingImpl{
operator ()cv::connectedcomponents::LabelingImpl192 LabelT operator()(const cv::Mat &I, cv::Mat &L, int connectivity, StatsOp &sop){
193 CV_Assert(L.rows == I.rows);
194 CV_Assert(L.cols == I.cols);
195 CV_Assert(connectivity == 8 || connectivity == 4);
196 const int rows = L.rows;
197 const int cols = L.cols;
198 //A quick and dirty upper bound for the maximimum number of labels. The 4 comes from
199 //the fact that a 3x3 block can never have more than 4 unique labels for both 4 & 8-way
200 const size_t Plength = 4 * (size_t(rows + 3 - 1)/3) * (size_t(cols + 3 - 1)/3);
201 LabelT *P = (LabelT *) fastMalloc(sizeof(LabelT) * Plength);
202 P[0] = 0;
203 LabelT lunique = 1;
204 //scanning phase
205 for(int r_i = 0; r_i < rows; ++r_i){
206 LabelT * const Lrow = L.ptr<LabelT>(r_i);
207 LabelT * const Lrow_prev = (LabelT *)(((char *)Lrow) - L.step.p[0]);
208 const PixelT * const Irow = I.ptr<PixelT>(r_i);
209 const PixelT * const Irow_prev = (const PixelT *)(((char *)Irow) - I.step.p[0]);
210 LabelT *Lrows[2] = {
211 Lrow,
212 Lrow_prev
213 };
214 const PixelT *Irows[2] = {
215 Irow,
216 Irow_prev
217 };
218 if(connectivity == 8){
219 const int a = 0;
220 const int b = 1;
221 const int c = 2;
222 const int d = 3;
223 const bool T_a_r = (r_i - G8[a][0]) >= 0;
224 const bool T_b_r = (r_i - G8[b][0]) >= 0;
225 const bool T_c_r = (r_i - G8[c][0]) >= 0;
226 for(int c_i = 0; Irows[0] != Irow + cols; ++Irows[0], c_i++){
227 if(!*Irows[0]){
228 Lrow[c_i] = 0;
229 continue;
230 }
231 Irows[1] = Irow_prev + c_i;
232 Lrows[0] = Lrow + c_i;
233 Lrows[1] = Lrow_prev + c_i;
234 const bool T_a = T_a_r && (c_i + G8[a][1]) >= 0 && *(Irows[G8[a][0]] + G8[a][1]);
235 const bool T_b = T_b_r && *(Irows[G8[b][0]] + G8[b][1]);
236 const bool T_c = T_c_r && (c_i + G8[c][1]) < cols && *(Irows[G8[c][0]] + G8[c][1]);
237 const bool T_d = (c_i + G8[d][1]) >= 0 && *(Irows[G8[d][0]] + G8[d][1]);
238
239 //decision tree
240 if(T_b){
241 //copy(b)
242 *Lrows[0] = *(Lrows[G8[b][0]] + G8[b][1]);
243 }else{//not b
244 if(T_c){
245 if(T_a){
246 //copy(c, a)
247 *Lrows[0] = set_union(P, *(Lrows[G8[c][0]] + G8[c][1]), *(Lrows[G8[a][0]] + G8[a][1]));
248 }else{
249 if(T_d){
250 //copy(c, d)
251 *Lrows[0] = set_union(P, *(Lrows[G8[c][0]] + G8[c][1]), *(Lrows[G8[d][0]] + G8[d][1]));
252 }else{
253 //copy(c)
254 *Lrows[0] = *(Lrows[G8[c][0]] + G8[c][1]);
255 }
256 }
257 }else{//not c
258 if(T_a){
259 //copy(a)
260 *Lrows[0] = *(Lrows[G8[a][0]] + G8[a][1]);
261 }else{
262 if(T_d){
263 //copy(d)
264 *Lrows[0] = *(Lrows[G8[d][0]] + G8[d][1]);
265 }else{
266 //new label
267 *Lrows[0] = lunique;
268 P[lunique] = lunique;
269 lunique = lunique + 1;
270 }
271 }
272 }
273 }
274 }
275 }else{
276 //B & D only
277 const int b = 0;
278 const int d = 1;
279 const bool T_b_r = (r_i - G4[b][0]) >= 0;
280 for(int c_i = 0; Irows[0] != Irow + cols; ++Irows[0], c_i++){
281 if(!*Irows[0]){
282 Lrow[c_i] = 0;
283 continue;
284 }
285 Irows[1] = Irow_prev + c_i;
286 Lrows[0] = Lrow + c_i;
287 Lrows[1] = Lrow_prev + c_i;
288 const bool T_b = T_b_r && *(Irows[G4[b][0]] + G4[b][1]);
289 const bool T_d = (c_i + G4[d][1]) >= 0 && *(Irows[G4[d][0]] + G4[d][1]);
290 if(T_b){
291 if(T_d){
292 //copy(d, b)
293 *Lrows[0] = set_union(P, *(Lrows[G4[d][0]] + G4[d][1]), *(Lrows[G4[b][0]] + G4[b][1]));
294 }else{
295 //copy(b)
296 *Lrows[0] = *(Lrows[G4[b][0]] + G4[b][1]);
297 }
298 }else{
299 if(T_d){
300 //copy(d)
301 *Lrows[0] = *(Lrows[G4[d][0]] + G4[d][1]);
302 }else{
303 //new label
304 *Lrows[0] = lunique;
305 P[lunique] = lunique;
306 lunique = lunique + 1;
307 }
308 }
309 }
310 }
311 }
312
313 //analysis
314 LabelT nLabels = flattenL(P, lunique);
315 sop.init(nLabels);
316
317 for(int r_i = 0; r_i < rows; ++r_i){
318 LabelT *Lrow_start = L.ptr<LabelT>(r_i);
319 LabelT *Lrow_end = Lrow_start + cols;
320 LabelT *Lrow = Lrow_start;
321 for(int c_i = 0; Lrow != Lrow_end; ++Lrow, ++c_i){
322 const LabelT l = P[*Lrow];
323 *Lrow = l;
324 sop(r_i, c_i, l);
325 }
326 }
327
328 sop.finish();
329 fastFree(P);
330
331 return nLabels;
332 }//End function LabelingImpl operator()
333
334 };//End struct LabelingImpl
335 }//end namespace connectedcomponents
336
337 //L's type must have an appropriate depth for the number of pixels in I
338 template<typename StatsOp>
339 static
connectedComponents_sub1(const cv::Mat & I,cv::Mat & L,int connectivity,StatsOp & sop)340 int connectedComponents_sub1(const cv::Mat &I, cv::Mat &L, int connectivity, StatsOp &sop){
341 CV_Assert(L.channels() == 1 && I.channels() == 1);
342 CV_Assert(connectivity == 8 || connectivity == 4);
343
344 int lDepth = L.depth();
345 int iDepth = I.depth();
346 using connectedcomponents::LabelingImpl;
347 //warn if L's depth is not sufficient?
348
349 CV_Assert(iDepth == CV_8U || iDepth == CV_8S);
350
351 if(lDepth == CV_8U){
352 return (int) LabelingImpl<uchar, uchar, StatsOp>()(I, L, connectivity, sop);
353 }else if(lDepth == CV_16U){
354 return (int) LabelingImpl<ushort, uchar, StatsOp>()(I, L, connectivity, sop);
355 }else if(lDepth == CV_32S){
356 //note that signed types don't really make sense here and not being able to use unsigned matters for scientific projects
357 //OpenCV: how should we proceed? .at<T> typechecks in debug mode
358 return (int) LabelingImpl<int, uchar, StatsOp>()(I, L, connectivity, sop);
359 }
360
361 CV_Error(CV_StsUnsupportedFormat, "unsupported label/image type");
362 return -1;
363 }
364
365 }
366
connectedComponents(InputArray _img,OutputArray _labels,int connectivity,int ltype)367 int cv::connectedComponents(InputArray _img, OutputArray _labels, int connectivity, int ltype){
368 const cv::Mat img = _img.getMat();
369 _labels.create(img.size(), CV_MAT_DEPTH(ltype));
370 cv::Mat labels = _labels.getMat();
371 connectedcomponents::NoOp sop;
372 if(ltype == CV_16U){
373 return connectedComponents_sub1(img, labels, connectivity, sop);
374 }else if(ltype == CV_32S){
375 return connectedComponents_sub1(img, labels, connectivity, sop);
376 }else{
377 CV_Error(CV_StsUnsupportedFormat, "the type of labels must be 16u or 32s");
378 return 0;
379 }
380 }
381
connectedComponentsWithStats(InputArray _img,OutputArray _labels,OutputArray statsv,OutputArray centroids,int connectivity,int ltype)382 int cv::connectedComponentsWithStats(InputArray _img, OutputArray _labels, OutputArray statsv,
383 OutputArray centroids, int connectivity, int ltype)
384 {
385 const cv::Mat img = _img.getMat();
386 _labels.create(img.size(), CV_MAT_DEPTH(ltype));
387 cv::Mat labels = _labels.getMat();
388 connectedcomponents::CCStatsOp sop(statsv, centroids);
389 if(ltype == CV_16U){
390 return connectedComponents_sub1(img, labels, connectivity, sop);
391 }else if(ltype == CV_32S){
392 return connectedComponents_sub1(img, labels, connectivity, sop);
393 }else{
394 CV_Error(CV_StsUnsupportedFormat, "the type of labels must be 16u or 32s");
395 return 0;
396 }
397 }
398