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