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