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