[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]
![]() |
vigra/labelimage.hxx | ![]() |
---|
00001 /************************************************************************/ 00002 /* */ 00003 /* Copyright 1998-2002 by Ullrich Koethe */ 00004 /* Cognitive Systems Group, University of Hamburg, Germany */ 00005 /* */ 00006 /* This file is part of the VIGRA computer vision library. */ 00007 /* ( Version 1.2.0, Aug 07 2003 ) */ 00008 /* You may use, modify, and distribute this software according */ 00009 /* to the terms stated in the LICENSE file included in */ 00010 /* the VIGRA distribution. */ 00011 /* */ 00012 /* The VIGRA Website is */ 00013 /* http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/ */ 00014 /* Please direct questions, bug reports, and contributions to */ 00015 /* koethe@informatik.uni-hamburg.de */ 00016 /* */ 00017 /* THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR */ 00018 /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 00019 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. */ 00020 /* */ 00021 /************************************************************************/ 00022 00023 00024 #ifndef VIGRA_LABELIMAGE_HXX 00025 #define VIGRA_LABELIMAGE_HXX 00026 00027 #include <vector> 00028 #include <functional> 00029 #include "vigra/utilities.hxx" 00030 #include "vigra/stdimage.hxx" 00031 00032 namespace vigra { 00033 00034 /** \addtogroup Labeling Connected Components Labeling 00035 The connected components algorithm may use either 4 or 8 connectivity. 00036 By means of a functor the merge criterium can be defined arbitrarily. 00037 */ 00038 //@{ 00039 00040 /********************************************************/ 00041 /* */ 00042 /* labelImage */ 00043 /* */ 00044 /********************************************************/ 00045 00046 /** \brief Find the connected components of a segmented image. 00047 00048 Connected components are defined as regions with uniform pixel 00049 values. Thus, <TT>SrcAccessor::value_type</TT> either must be 00050 equality comparable (first form), or an EqualityFunctor must be 00051 provided that realizes the desired predicate (second form). The 00052 destination's value type should be large enough to hold the labels 00053 without overflow. Region numbers will be a consecutive sequence 00054 starting with one and ending with the region number returned by 00055 the function (inclusive). The parameter '<TT>eight_neighbors</TT>' 00056 determines whether the regions should be 4-connected or 00057 8-connected. The function uses accessors. 00058 00059 <b> Declarations:</b> 00060 00061 pass arguments explicitly: 00062 \code 00063 namespace vigra { 00064 template <class SrcIterator, class SrcAccessor, 00065 class DestIterator, class DestAccessor> 00066 unsigned int labelImage(SrcIterator upperlefts, 00067 SrcIterator lowerrights, SrcAccessor sa, 00068 DestIterator upperleftd, DestAccessor da, 00069 bool eight_neighbors); 00070 00071 template <class SrcIterator, class SrcAccessor, 00072 class DestIterator, class DestAccessor, 00073 class EqualityFunctor> 00074 unsigned int labelImage(SrcIterator upperlefts, 00075 SrcIterator lowerrights, SrcAccessor sa, 00076 DestIterator upperleftd, DestAccessor da, 00077 bool eight_neighbors, EqualityFunctor equal); 00078 } 00079 \endcode 00080 00081 use argument objects in conjuction with \ref ArgumentObjectFactories: 00082 \code 00083 namespace vigra { 00084 template <class SrcIterator, class SrcAccessor, 00085 class DestIterator, class DestAccessor> 00086 unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src, 00087 pair<DestIterator, DestAccessor> dest, 00088 bool eight_neighbors); 00089 00090 template <class SrcIterator, class SrcAccessor, 00091 class DestIterator, class DestAccessor, 00092 class EqualityFunctor> 00093 unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src, 00094 pair<DestIterator, DestAccessor> dest, 00095 bool eight_neighbors, EqualityFunctor equal) 00096 } 00097 \endcode 00098 00099 Return: the number of regions found (= largest region label) 00100 00101 <b> Usage:</b> 00102 00103 <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br> 00104 Namespace: vigra 00105 00106 \code 00107 vigra::BImage src(w,h); 00108 vigra::IImage labels(w,h); 00109 00110 // threshold at 128 00111 vigra::transformImage(srcImageRange(src), destImage(src), 00112 vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>( 00113 128, 256, 0, 255)); 00114 00115 // find 4-connected regions 00116 vigra::labelImage(srcImageRange(src), destImage(labels), false); 00117 \endcode 00118 00119 <b> Required Interface:</b> 00120 00121 \code 00122 SrcImageIterator src_upperleft, src_lowerright; 00123 DestImageIterator dest_upperleft; 00124 00125 SrcAccessor src_accessor; 00126 DestAccessor dest_accessor; 00127 00128 SrcAccessor::value_type u = src_accessor(src_upperleft); 00129 00130 u == u // first form 00131 00132 EqualityFunctor equal; // second form 00133 equal(u, u) // second form 00134 00135 int i; 00136 dest_accessor.set(i, dest_upperleft); 00137 \endcode 00138 00139 */ 00140 template <class SrcIterator, class SrcAccessor, 00141 class DestIterator, class DestAccessor, 00142 class EqualityFunctor> 00143 unsigned int labelImage(SrcIterator upperlefts, 00144 SrcIterator lowerrights, SrcAccessor sa, 00145 DestIterator upperleftd, DestAccessor da, 00146 bool eight_neighbors, EqualityFunctor equal) 00147 { 00148 int w = lowerrights.x - upperlefts.x; 00149 int h = lowerrights.y - upperlefts.y; 00150 int x,y,i; 00151 00152 static const Diff2D neighbor[] = { 00153 Diff2D(-1,0), // left 00154 Diff2D(-1,-1), // topleft 00155 Diff2D(0,-1), // top 00156 Diff2D(1,-1) // topright 00157 }; 00158 00159 static const int left = 0, /* unused: topleft = 1, */ top = 2, topright = 3; 00160 int step = eight_neighbors ? 1 : 2; 00161 00162 SrcIterator ys(upperlefts); 00163 SrcIterator xs(ys); 00164 00165 // temporary image to store region labels 00166 IImage labelimage(w, h); 00167 00168 IImage::Iterator yt = labelimage.upperLeft(); 00169 IImage::Iterator xt(yt); 00170 00171 // Kovalevsky's clever idea to use 00172 // image iterator and scan order iterator simultaneously 00173 IImage::ScanOrderIterator label = labelimage.begin(); 00174 00175 // pass 1: scan image from upper left to lower right 00176 // to find connected components 00177 00178 // Each component will be represented by a tree of pixels. Each 00179 // pixel contains the scan order address of its parent in the 00180 // tree. In order for pass 2 to work correctly, the parent must 00181 // always have a smaller scan order address than the child. 00182 // Therefore, we can merge trees only at their roots, because the 00183 // root of the combined tree must have the smallest scan order 00184 // address among all the tree's pixels/ nodes. The root of each 00185 // tree is distinguished by pointing to itself (it contains its 00186 // own scan order address). This condition is enforced whenever a 00187 // new region is found or two regions are merged 00188 00189 00190 for(y = 0; y != h; ++y, ++ys.y, ++yt.y) 00191 { 00192 xs = ys; 00193 xt = yt; 00194 00195 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top); 00196 00197 for(x = 0; x != w; ++x, ++xs.x, ++xt.x) 00198 { 00199 int beginNeighbor = (x == 0) ? top : left; 00200 if(x == w-1 && endNeighbor == topright) endNeighbor = top; 00201 00202 for(i=beginNeighbor; i<=endNeighbor; i+=step) 00203 { 00204 if(equal(sa(xs), sa(xs, neighbor[i]))) 00205 { 00206 int neighborLabel = xt[neighbor[i]]; 00207 00208 for(int j=i+2; j<=endNeighbor; j+=step) 00209 { 00210 if(equal(sa(xs), sa(xs, neighbor[j]))) 00211 { 00212 int neighborLabel1 = xt[neighbor[j]]; 00213 00214 if(neighborLabel != neighborLabel1) 00215 { 00216 // find roots of the region trees 00217 while(neighborLabel != label[neighborLabel]) 00218 { 00219 neighborLabel = label[neighborLabel]; 00220 } 00221 while(neighborLabel1 != label[neighborLabel1]) 00222 { 00223 neighborLabel1 = label[neighborLabel1]; 00224 } 00225 00226 // merge the trees 00227 if(neighborLabel1 < neighborLabel) 00228 { 00229 label[neighborLabel] = neighborLabel1; 00230 neighborLabel = neighborLabel1; 00231 } 00232 else if(neighborLabel < neighborLabel1) 00233 { 00234 label[neighborLabel1] = neighborLabel; 00235 } 00236 } 00237 break; 00238 } 00239 } 00240 *xt = neighborLabel; 00241 break; 00242 } 00243 00244 } 00245 if(i > endNeighbor) 00246 { 00247 // new region 00248 // The initial label of a new region equals the 00249 // scan order address of it's first pixel. 00250 // This is essential for correct operation of the algorithm. 00251 *xt = x + y*w; 00252 } 00253 } 00254 } 00255 00256 // pass 2: assign one label to each region (tree) 00257 // so that labels for a consecutive sequence 1, 2, ... 00258 DestIterator yd(upperleftd); 00259 00260 unsigned int count = 0; 00261 i = 0; 00262 for(y=0; y != h; ++y, ++yd.y) 00263 { 00264 DestIterator xd(yd); 00265 for(x = 0; x != w; ++x, ++xd.x, ++i) 00266 { 00267 if(label[i] == i) 00268 { 00269 label[i] = ++count; 00270 } 00271 else 00272 { 00273 label[i] = label[label[i]]; 00274 } 00275 da.set(label[i], xd); 00276 } 00277 } 00278 return count; 00279 } 00280 00281 template <class SrcIterator, class SrcAccessor, 00282 class DestIterator, class DestAccessor, 00283 class EqualityFunctor> 00284 inline 00285 int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src, 00286 pair<DestIterator, DestAccessor> dest, 00287 bool eight_neighbors, EqualityFunctor equal) 00288 { 00289 return labelImage(src.first, src.second, src.third, 00290 dest.first, dest.second, eight_neighbors, equal); 00291 } 00292 00293 template <class SrcIterator, class SrcAccessor, 00294 class DestIterator, class DestAccessor> 00295 inline 00296 int labelImage(SrcIterator upperlefts, 00297 SrcIterator lowerrights, SrcAccessor sa, 00298 DestIterator upperleftd, DestAccessor da, 00299 bool eight_neighbors) 00300 { 00301 return labelImage(upperlefts, lowerrights, sa, 00302 upperleftd, da, eight_neighbors, 00303 std::equal_to<typename SrcAccessor::value_type>()); 00304 } 00305 00306 template <class SrcIterator, class SrcAccessor, 00307 class DestIterator, class DestAccessor> 00308 inline 00309 int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src, 00310 pair<DestIterator, DestAccessor> dest, 00311 bool eight_neighbors) 00312 { 00313 return labelImage(src.first, src.second, src.third, 00314 dest.first, dest.second, eight_neighbors, 00315 std::equal_to<typename SrcAccessor::value_type>()); 00316 } 00317 00318 /********************************************************/ 00319 /* */ 00320 /* labelImageWithBackground */ 00321 /* */ 00322 /********************************************************/ 00323 00324 /** \brief Find the connected components of a segmented image, 00325 excluding the background from labeling. 00326 00327 Connected components are defined as regions with uniform pixel 00328 values. Thus, <TT>SrcAccessor::value_type</TT> either must be 00329 equality comparable (first form), or an EqualityFunctor must be 00330 provided that realizes the desired predicate (second form). All 00331 pixel equal to the given '<TT>background_value</TT>' are ignored 00332 when determining connected components and remain untouched in the 00333 destination image and 00334 00335 The destination's value type should be large enough to hold the 00336 labels without overflow. Region numbers will be a consecutive 00337 sequence starting with one and ending with the region number 00338 returned by the function (inclusive). The parameter 00339 '<TT>eight_neighbors</TT>' determines whether the regions should 00340 be 4-connected or 8-connected. The function uses accessors. 00341 00342 <b> Declarations:</b> 00343 00344 pass arguments explicitly: 00345 \code 00346 namespace vigra { 00347 template <class SrcIterator, class SrcAccessor, 00348 class DestIterator, class DestAccessor, 00349 class ValueType> 00350 int labelImageWithBackground(SrcIterator upperlefts, 00351 SrcIterator lowerrights, SrcAccessor sa, 00352 DestIterator upperleftd, DestAccessor da, 00353 bool eight_neighbors, 00354 ValueType background_value ); 00355 00356 template <class SrcIterator, class SrcAccessor, 00357 class DestIterator, class DestAccessor, 00358 class ValueType, class EqualityFunctor> 00359 int labelImageWithBackground(SrcIterator upperlefts, 00360 SrcIterator lowerrights, SrcAccessor sa, 00361 DestIterator upperleftd, DestAccessor da, 00362 bool eight_neighbors, 00363 ValueType background_value, EqualityFunctor equal); 00364 } 00365 \endcode 00366 00367 use argument objects in conjuction with \ref ArgumentObjectFactories: 00368 \code 00369 namespace vigra { 00370 template <class SrcIterator, class SrcAccessor, 00371 class DestIterator, class DestAccessor, 00372 class ValueType> 00373 inline 00374 int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src, 00375 pair<DestIterator, DestAccessor> dest, 00376 bool eight_neighbors, 00377 ValueType background_value); 00378 00379 template <class SrcIterator, class SrcAccessor, 00380 class DestIterator, class DestAccessor, 00381 class ValueType, class EqualityFunctor> 00382 inline 00383 int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src, 00384 pair<DestIterator, DestAccessor> dest, 00385 bool eight_neighbors, 00386 ValueType background_value, EqualityFunctor equal); 00387 } 00388 \endcode 00389 00390 Return: the number of regions found (= largest region label) 00391 00392 <b> Usage:</b> 00393 00394 <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br> 00395 Namespace: vigra 00396 00397 \code 00398 vigra::BImage src(w,h); 00399 vigra::IImage labels(w,h); 00400 00401 // threshold at 128 00402 vigra::transformImage(srcImageRange(src), destImage(src), 00403 vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>( 00404 128, 256, 0, 255)); 00405 00406 // find 4-connected regions of foreground (= white pixels) only 00407 vigra::labelImageWithBackground(srcImageRange(src), destImage(labels), 00408 false, 0); 00409 \endcode 00410 00411 <b> Required Interface:</b> 00412 00413 \code 00414 SrcImageIterator src_upperleft, src_lowerright; 00415 DestImageIterator dest_upperleft; 00416 00417 SrcAccessor src_accessor; 00418 DestAccessor dest_accessor; 00419 00420 SrcAccessor::value_type u = src_accessor(src_upperleft); 00421 ValueType background_value; 00422 00423 u == u // first form 00424 u == background_value // first form 00425 00426 EqualityFunctor equal; // second form 00427 equal(u, u) // second form 00428 equal(u, background_value) // second form 00429 00430 int i; 00431 dest_accessor.set(i, dest_upperleft); 00432 \endcode 00433 00434 */ 00435 template <class SrcIterator, class SrcAccessor, 00436 class DestIterator, class DestAccessor, 00437 class ValueType, class EqualityFunctor> 00438 int labelImageWithBackground(SrcIterator upperlefts, 00439 SrcIterator lowerrights, SrcAccessor sa, 00440 DestIterator upperleftd, DestAccessor da, 00441 bool eight_neighbors, 00442 ValueType background_value, EqualityFunctor equal) 00443 { 00444 int w = lowerrights.x - upperlefts.x; 00445 int h = lowerrights.y - upperlefts.y; 00446 int x,y,i; 00447 00448 static const Diff2D neighbor[] = { 00449 Diff2D(-1,0), // left 00450 Diff2D(-1,-1), // topleft 00451 Diff2D(0,-1), // top 00452 Diff2D(1,-1) // topright 00453 }; 00454 00455 static const int left = 0, /* unused: topleft = 1,*/ top = 2, topright = 3; 00456 int step = eight_neighbors ? 1 : 2; 00457 00458 SrcIterator ys(upperlefts); 00459 SrcIterator xs(ys); 00460 00461 // temporary image to store region labels 00462 IImage labelimage(w, h); 00463 IImage::ScanOrderIterator label = labelimage.begin(); 00464 IImage::Iterator yt = labelimage.upperLeft(); 00465 IImage::Iterator xt(yt); 00466 00467 // pass 1: scan image from upper left to lower right 00468 // find connected components 00469 00470 for(y = 0; y != h; ++y, ++ys.y, ++yt.y) 00471 { 00472 xs = ys; 00473 xt = yt; 00474 00475 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top); 00476 00477 for(x = 0; x != w; ++x, ++xs.x, ++xt.x) 00478 { 00479 if(equal(sa(xs), background_value)) 00480 { 00481 *xt = -1; 00482 } 00483 else 00484 { 00485 int beginNeighbor = (x == 0) ? top : left; 00486 if(x == w-1 && endNeighbor == topright) endNeighbor = top; 00487 00488 for(i=beginNeighbor; i<=endNeighbor; i+=step) 00489 { 00490 if(equal(sa(xs), sa(xs, neighbor[i]))) 00491 { 00492 int neighborLabel = xt[neighbor[i]]; 00493 00494 for(int j=i+2; j<=endNeighbor; j+=step) 00495 { 00496 if(equal(sa(xs), sa(xs, neighbor[j]))) 00497 { 00498 int neighborLabel1 = xt[neighbor[j]]; 00499 00500 if(neighborLabel != neighborLabel1) 00501 { 00502 // find roots of the region trees 00503 while(neighborLabel != label[neighborLabel]) 00504 { 00505 neighborLabel = label[neighborLabel]; 00506 } 00507 while(neighborLabel1 != label[neighborLabel1]) 00508 { 00509 neighborLabel1 = label[neighborLabel1]; 00510 } 00511 00512 // merge the trees 00513 if(neighborLabel1 < neighborLabel) 00514 { 00515 label[neighborLabel] = neighborLabel1; 00516 neighborLabel = neighborLabel1; 00517 } 00518 else if(neighborLabel < neighborLabel1) 00519 { 00520 label[neighborLabel1] = neighborLabel; 00521 } 00522 } 00523 break; 00524 } 00525 } 00526 *xt = neighborLabel; 00527 break; 00528 } 00529 00530 } 00531 if(i > endNeighbor) 00532 { 00533 // new region 00534 // The initial label of a new region equals the 00535 // scan order address of it's first pixel. 00536 // This is essential for correct operation of the algorithm. 00537 *xt = x + y*w; 00538 } 00539 } 00540 } 00541 } 00542 00543 // pass 2: assign contiguous labels to the regions 00544 DestIterator yd(upperleftd); 00545 00546 int count = 0; 00547 i = 0; 00548 for(y=0; y != h; ++y, ++yd.y) 00549 { 00550 DestIterator xd(yd); 00551 for(x = 0; x != w; ++x, ++xd.x, ++i) 00552 { 00553 if(label[i] == -1) continue; 00554 00555 if(label[i] == i) 00556 { 00557 label[i] = count++; 00558 } 00559 else 00560 { 00561 label[i] = label[label[i]]; 00562 } 00563 da.set(label[i]+1, xd); 00564 } 00565 } 00566 00567 return count; 00568 } 00569 template <class SrcIterator, class SrcAccessor, 00570 class DestIterator, class DestAccessor, 00571 class ValueType, class EqualityFunctor> 00572 inline 00573 int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src, 00574 pair<DestIterator, DestAccessor> dest, 00575 bool eight_neighbors, 00576 ValueType background_value, EqualityFunctor equal) 00577 { 00578 return labelImageWithBackground(src.first, src.second, src.third, 00579 dest.first, dest.second, 00580 eight_neighbors, background_value, equal); 00581 } 00582 00583 template <class SrcIterator, class SrcAccessor, 00584 class DestIterator, class DestAccessor, 00585 class ValueType> 00586 inline 00587 int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src, 00588 pair<DestIterator, DestAccessor> dest, 00589 bool eight_neighbors, 00590 ValueType background_value) 00591 { 00592 return labelImageWithBackground(src.first, src.second, src.third, 00593 dest.first, dest.second, 00594 eight_neighbors, background_value, 00595 std::equal_to<typename SrcAccessor::value_type>()); 00596 } 00597 00598 template <class SrcIterator, class SrcAccessor, 00599 class DestIterator, class DestAccessor, 00600 class ValueType> 00601 inline 00602 int labelImageWithBackground(SrcIterator upperlefts, 00603 SrcIterator lowerrights, SrcAccessor sa, 00604 DestIterator upperleftd, DestAccessor da, 00605 bool eight_neighbors, 00606 ValueType background_value) 00607 { 00608 return labelImageWithBackground(upperlefts, lowerrights, sa, 00609 upperleftd, da, 00610 eight_neighbors, background_value, 00611 std::equal_to<typename SrcAccessor::value_type>()); 00612 } 00613 00614 /********************************************************/ 00615 /* */ 00616 /* regionImageToCrackEdgeImage */ 00617 /* */ 00618 /********************************************************/ 00619 00620 /** \brief Transform a labeled image into a crack edge image. 00621 00622 This algorithm inserts border pixels (so called "crack edges" 00623 between regions in a labeled image like this (<TT>a</TT> and 00624 <TT>c</TT> are the original labels, and <TT>0</TT> is the value of 00625 <TT>edge_marker</TT> and denotes the inserted edges): 00626 00627 \code 00628 original image insert zero- and one-cells 00629 00630 a 0 c c c 00631 a c c a 0 0 0 c 00632 a a c => a a a 0 c 00633 a a a a a a 0 0 00634 a a a a a 00635 \endcode 00636 00637 The algorithm assumes that the original labeled image contains 00638 no background. Therefore, it is suitable as a post-processing 00639 operation of \ref labelImage() or \ref seededRegionGrowing(). 00640 00641 The destination image must be twice the size of the original 00642 (precisely, <TT>(2*w-1)</TT> by <TT>(2*h-1)</TT> pixels). The 00643 source value type (<TT>SrcAccessor::value-type</TT>) must be 00644 equality-comparable. 00645 00646 <b> Declarations:</b> 00647 00648 pass arguments explicitly: 00649 \code 00650 namespace vigra { 00651 template <class SrcIterator, class SrcAccessor, 00652 class DestIterator, class DestAccessor, class DestValue> 00653 void regionImageToCrackEdgeImage( 00654 SrcIterator sul, SrcIterator slr, SrcAccessor sa, 00655 DestIterator dul, DestAccessor da, 00656 DestValue edge_marker) 00657 } 00658 \endcode 00659 00660 use argument objects in conjuction with \ref ArgumentObjectFactories: 00661 \code 00662 namespace vigra { 00663 template <class SrcIterator, class SrcAccessor, 00664 class DestIterator, class DestAccessor, class DestValue> 00665 inline 00666 void regionImageToCrackEdgeImage( 00667 triple<SrcIterator, SrcIterator, SrcAccessor> src, 00668 pair<DestIterator, DestAccessor> dest, 00669 DestValue edge_marker) 00670 } 00671 \endcode 00672 00673 <b> Usage:</b> 00674 00675 <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br> 00676 Namespace: vigra 00677 00678 \code 00679 vigra::BImage src(w,h); 00680 vigra::IImage labels(w,h); 00681 vigra::IImage cellgrid(2*w-1, 2*h-1); 00682 00683 // threshold at 128 00684 vigra::transformImage(srcImageRange(src), destImage(src), 00685 vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>( 00686 128, 256, 0, 255)); 00687 00688 // find 4-connected regions 00689 vigra::labelImage(srcImageRange(src), destImage(labels), false); 00690 00691 // create cell grid image, mark edges with 0 00692 vigra::regionImageToCrackEdgeImage(srcImageRange(labels), destImage(cellgrid), 0); 00693 \endcode 00694 00695 <b> Required Interface:</b> 00696 00697 \code 00698 ImageIterator src_upperleft, src_lowerright; 00699 ImageIterator dest_upperleft; 00700 00701 SrcAccessor src_accessor; 00702 DestAccessor dest_accessor; 00703 00704 SrcAccessor::value_type u = src_accessor(src_upperleft); 00705 00706 u != u 00707 00708 DestValue edge_marker; 00709 dest_accessor.set(edge_marker, dest_upperleft); 00710 \endcode 00711 00712 <b> Preconditions:</b> 00713 00714 The destination image must have twice the size of the source: 00715 \code 00716 w_dest = 2 * w_src - 1 00717 h_dest = 2 * h_src - 1 00718 \endcode 00719 */ 00720 template <class SrcIterator, class SrcAccessor, 00721 class DestIterator, class DestAccessor, class DestValue> 00722 void regionImageToCrackEdgeImage( 00723 SrcIterator sul, SrcIterator slr, SrcAccessor sa, 00724 DestIterator dul, DestAccessor da, 00725 DestValue edge_marker) 00726 { 00727 int w = slr.x - sul.x; 00728 int h = slr.y - sul.y; 00729 int x,y; 00730 00731 static const Diff2D right(1,0); 00732 static const Diff2D left(-1,0); 00733 static const Diff2D bottomright(1,1); 00734 static const Diff2D bottom(0,1); 00735 static const Diff2D top(0,-1); 00736 00737 SrcIterator iy = sul; 00738 DestIterator dy = dul; 00739 00740 for(y=0; y<h-1; ++y, ++iy.y, dy.y+=2) 00741 { 00742 SrcIterator ix = iy; 00743 DestIterator dx = dy; 00744 00745 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2) 00746 { 00747 da.set(sa(ix), dx); 00748 da.set(sa(ix), dx, bottomright); 00749 00750 if(sa(ix, right) != sa(ix)) 00751 { 00752 da.set(edge_marker, dx, right); 00753 } 00754 else 00755 { 00756 da.set(sa(ix), dx, right); 00757 } 00758 if(sa(ix, bottom) != sa(ix)) 00759 { 00760 da.set(edge_marker, dx, bottom); 00761 } 00762 else 00763 { 00764 da.set(sa(ix), dx, bottom); 00765 } 00766 00767 } 00768 00769 da.set(sa(ix), dx); 00770 if(sa(ix, bottom) != sa(ix)) 00771 { 00772 da.set(edge_marker, dx, bottom); 00773 } 00774 else 00775 { 00776 da.set(sa(ix), dx, bottom); 00777 } 00778 } 00779 00780 SrcIterator ix = iy; 00781 DestIterator dx = dy; 00782 00783 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2) 00784 { 00785 da.set(sa(ix), dx); 00786 if(sa(ix, right) != sa(ix)) 00787 { 00788 da.set(edge_marker, dx, right); 00789 } 00790 else 00791 { 00792 da.set(sa(ix), dx, right); 00793 } 00794 } 00795 da.set(sa(ix), dx); 00796 00797 dy = dul + Diff2D(1,1); 00798 00799 // find missing 0-cells 00800 for(y=0; y<h-1; ++y, dy.y+=2) 00801 { 00802 DestIterator dx = dy; 00803 00804 for(x=0; x<w-1; ++x, dx.x+=2) 00805 { 00806 static const Diff2D dist[] = {right, top, left, bottom }; 00807 00808 int i; 00809 for(i=0; i<4; ++i) 00810 { 00811 if(da(dx, dist[i]) == edge_marker) break; 00812 } 00813 00814 if(i < 4) da.set(edge_marker, dx); 00815 } 00816 } 00817 } 00818 00819 template <class SrcIterator, class SrcAccessor, 00820 class DestIterator, class DestAccessor, class DestValue> 00821 inline 00822 void regionImageToCrackEdgeImage( 00823 triple<SrcIterator, SrcIterator, SrcAccessor> src, 00824 pair<DestIterator, DestAccessor> dest, 00825 DestValue edge_marker) 00826 { 00827 regionImageToCrackEdgeImage(src.first, src.second, src.third, 00828 dest.first, dest.second, 00829 edge_marker); 00830 } 00831 00832 /********************************************************/ 00833 /* */ 00834 /* regionImageToEdgeImage */ 00835 /* */ 00836 /********************************************************/ 00837 00838 /** \brief Transform a labeled image into an edge image. 00839 00840 This algorithm marks all pixels with the given <TT>edge_marker</TT> 00841 which belong to a different region (label) than their right or lower 00842 neighbors: 00843 00844 \code 00845 original image edges 00846 (assuming edge_marker == 1) 00847 00848 a c c 1 1 * 00849 a a c => * 1 1 00850 a a a * * * 00851 \endcode 00852 00853 The non-edge pixels of the destination image will not be touched. 00854 The source value type (<TT>SrcAccessor::value-type</TT>) must be 00855 equality-comparable. 00856 00857 <b> Declarations:</b> 00858 00859 pass arguments explicitly: 00860 \code 00861 namespace vigra { 00862 template <class SrcIterator, class SrcAccessor, 00863 class DestIterator, class DestAccessor, class DestValue> 00864 void regionImageToEdgeImage( 00865 SrcIterator sul, SrcIterator slr, SrcAccessor sa, 00866 DestIterator dul, DestAccessor da, 00867 DestValue edge_marker) 00868 } 00869 \endcode 00870 00871 use argument objects in conjuction with \ref ArgumentObjectFactories: 00872 \code 00873 namespace vigra { 00874 template <class SrcIterator, class SrcAccessor, 00875 class DestIterator, class DestAccessor, class DestValue> 00876 inline 00877 void regionImageToEdgeImage( 00878 triple<SrcIterator, SrcIterator, SrcAccessor> src, 00879 pair<DestIterator, DestAccessor> dest, 00880 DestValue edge_marker) 00881 } 00882 \endcode 00883 00884 <b> Usage:</b> 00885 00886 <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br> 00887 Namespace: vigra 00888 00889 \code 00890 vigra::BImage src(w,h); 00891 vigra::IImage labels(w,h); 00892 vigra::IImage edges(w, h); 00893 edges = 255; // init background (non-edge) to 255 00894 00895 // threshold at 128 00896 vigra::transformImage(srcImageRange(src), destImage(src), 00897 vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>( 00898 128, 256, 0, 255)); 00899 00900 // find 4-connected regions 00901 vigra::labelImage(srcImageRange(src), destImage(labels), false); 00902 00903 // create edge image, mark edges with 0 00904 vigra::regionImageToEdgeImage(srcImageRange(labels), destImage(edges), 0); 00905 \endcode 00906 00907 <b> Required Interface:</b> 00908 00909 \code 00910 ImageIterator src_upperleft, src_lowerright; 00911 ImageIterator dest_upperleft; 00912 00913 SrcAccessor src_accessor; 00914 DestAccessor dest_accessor; 00915 00916 SrcAccessor::value_type u = src_accessor(src_upperleft); 00917 00918 u != u 00919 00920 DestValue edge_marker; 00921 dest_accessor.set(edge_marker, dest_upperleft); 00922 \endcode 00923 00924 */ 00925 template <class SrcIterator, class SrcAccessor, 00926 class DestIterator, class DestAccessor, class DestValue> 00927 void regionImageToEdgeImage( 00928 SrcIterator sul, SrcIterator slr, SrcAccessor sa, 00929 DestIterator dul, DestAccessor da, 00930 DestValue edge_marker) 00931 { 00932 int w = slr.x - sul.x; 00933 int h = slr.y - sul.y; 00934 int x,y; 00935 00936 static const Diff2D right(1,0); 00937 static const Diff2D left(-1,0); 00938 static const Diff2D bottomright(1,1); 00939 static const Diff2D bottom(0,1); 00940 static const Diff2D top(0,-1); 00941 00942 SrcIterator iy = sul; 00943 DestIterator dy = dul; 00944 00945 for(y=0; y<h-1; ++y, ++iy.y, ++dy.y) 00946 { 00947 SrcIterator ix = iy; 00948 DestIterator dx = dy; 00949 00950 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x) 00951 { 00952 if(sa(ix, right) != sa(ix)) 00953 { 00954 da.set(edge_marker, dx); 00955 } 00956 if(sa(ix, bottom) != sa(ix)) 00957 { 00958 da.set(edge_marker, dx); 00959 } 00960 } 00961 00962 if(sa(ix, bottom) != sa(ix)) 00963 { 00964 da.set(edge_marker, dx); 00965 } 00966 } 00967 00968 SrcIterator ix = iy; 00969 DestIterator dx = dy; 00970 00971 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x) 00972 { 00973 if(sa(ix, right) != sa(ix)) 00974 { 00975 da.set(edge_marker, dx); 00976 } 00977 } 00978 } 00979 00980 template <class SrcIterator, class SrcAccessor, 00981 class DestIterator, class DestAccessor, class DestValue> 00982 inline 00983 void regionImageToEdgeImage( 00984 triple<SrcIterator, SrcIterator, SrcAccessor> src, 00985 pair<DestIterator, DestAccessor> dest, 00986 DestValue edge_marker) 00987 { 00988 regionImageToEdgeImage(src.first, src.second, src.third, 00989 dest.first, dest.second, 00990 edge_marker); 00991 } 00992 00993 //@} 00994 00995 } // namespace vigra 00996 00997 #endif // VIGRA_LABELIMAGE_HXX
© Ullrich Köthe (koethe@informatik.uni-hamburg.de) |
html generated using doxygen and Python
|