Actas de congresos
Automatic Image Segmentation By Tree Pruning
Registro en:
Journal Of Mathematical Imaging And Vision. , v. 29, n. 02/03/15, p. 141 - 162, 2007.
9249907
10.1007/s10851-007-0035-4
2-s2.0-37449024900
Autor
Bergo F.P.G.
Falcao A.X.
Miranda P.A.V.
Rocha L.M.
Institución
Resumen
The Image Foresting Transform (IFT) is a tool for the design of image processing operators based on connectivity, which reduces image processing problems into an optimum-path forest problem in a graph derived from the image. A new image operator is presented, which solves segmentation by pruning trees of the forest. An IFT is applied to create an optimum-path forest whose roots are seed pixels, selected inside a desired object. In this forest, object and background are connected by optimum paths (leaking paths), which cross the object's boundary through its "most weakly connected" parts (leaking pixels). These leaking pixels are automatically identified and their subtrees are eliminated, such that the remaining forest defines the object. Tree pruning runs in linear time, is extensible to multidimensional images, is free of ad hoc parameters, and requires only internal seeds, with little interference from the heterogeneity of the background. These aspects favor solutions for automatic segmentation. We present a formal definition of the obtained objects, algorithms, sufficient conditions for tree pruning, and two applications involving automatic segmentation: 3D MR-image segmentation of the human brain and image segmentation of license plates. Given that its most competitive approach is the watershed transform by markers, we also include a comparative analysis between them. © 2007 Springer Science+Business Media, LLC. 29 02/03/15 141 162 Audigier, R., Lotufo, R.A., Falcão, A.X., 3D visualization to assist iterative object definition from medical images (2006) Comput. Med. Imaging Graph., 30, pp. 217-230. , 4 Beucher, S., Meyer, F., The morphological approach to segmentation: The watershed transformation (1993) Mathematical Morphology in Image Processing, pp. 433-481. , Marcel Dekker New York Boykov, Y.Y., Jolly, M.-P., Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images (2001) International Conference on Computer Vision (ICCV), 1, pp. 105-112 Cohen, L.D., On active contour models and balloons (1991) Comput. Vis. Graph. Image Process. Image Underst., 53, pp. 211-218. , 2 Collins, D.L., Zijdenbos, A.P., Kollokian, V., Sled, J.G., Kabani, N.J., Holmes, C.J., Evans, A.C., Design and construction of a realistic digital brain phantom (1998) IEEE Trans. Med. Imaging, 17, pp. 463-468. , 3 Cootes, T., Edwards, G., Taylor, C.J., Active appearance models (1998) European Conference on Computer Vision (ECCV), 2, pp. 484-498 Cootes, T., Taylor, C., Cooper, D., Graham, J., Active shape models-their training and application (1995) Comput. Vis. Image Underst., 61, pp. 38-59. , 1 Duda, R.O., Hart, P.E., Stork, D.G., (2000) Pattern Classification, , Wiley-Interscience New York Falcão, A.X., Bergo, F.P.G., Interactive volume segmentation with differential image foresting transforms (2004) IEEE Trans. Med. Imaging, 23, pp. 1100-1108. , 9 Falcão, A.X., Bergo, F.P.G., Miranda, P.A.V., Image segmentation by tree pruning (2004) XVII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI) October 2004, pp. 65-71. , IEEE New York Falcão, A.X., Costa, L.F., Da Cunha, B.S., Multiscale skeletons by image foresting transform and its applications to neuromorphometry (2002) Pattern Recognit., 35, pp. 1571-1582. , 7 Falcão, A.X., Da Cunha, B.S., Lotufo, R.A., Design of connected operators using the image foresting transform (2001) Proc. of SPIE on Medical Imaging, 4322, pp. 468-479 Falcão, A.X., Stolfi, J., Lotufo, R.A., The image foresting transform: Theory, algorithms, and applications (2004) IEEE Trans. Pattern Anal. Mach. Intell., 26, pp. 19-29. , 1 Falcão, A.X., Udupa, J.K., Miyazawa, F.K., An ultra-fast user-steered image segmentation paradigm: Live-wire-on-the-fly (2000) IEEE Trans. Med. Imaging, 19, pp. 55-62. , 1 Falcão, A.X., Udupa, J.K., Samarasekera, S., Sharma, S., Hirsch, B.E., Lotufo, R.A., User-steered image segmentation paradigms: Live-wire and live-lane (1998) Graph. Models Image Process., 60, pp. 233-260. , 4 Ford, L., Fulkerson, D., (1962) Flows in Networks, , Princeton University Press Princeton Frackowiak, R.S.J., Friston, K.J., Frith, C., Dolan, R., Price, C.J., Zeki, S., Ashburner, J., Penny, W.D., (2003) Human Brain Function, , 2 Academic Press New York Grau, V., Mewes, A.U.J., Alcaniz, M., Kikinis, R., Warfield, S.K., Improved watershed transform for medical image segmentation using prior information (2004) IEEE Trans. Med. Imaging, 23, pp. 447-458. , 4 Haykin, S., (1998) Neural Networks: A Comprehensive Foundation, , Prentice-Hall New York Kass, M., Witkin, A., Terzopoulos, D., Snakes: Active contour models (1987) Int. J. Comput. Vis., 1, pp. 321-331 Kolmogorov, V., Zabih, R., What energy functions can be minimized via graph cuts (2004) IEEE Trans. Pattern Anal. Mach. Intell., 26, pp. 147-159. , 2 Kuncheva, L.I., (2004) Combining Pattern Classifiers: Methods and Algorithms, , Wiley-Interscience New York Lotufo, R.A., Falcão, A.X., The ordered queue and the optimality of the watershed approaches (2000) Mathematical Morphology and Its Applications to Image and Signal Processing, Vol. 18, pp. 341-350. , Kluwer Dordrecht Lotufo, R.A., Falcão, A.X., Zampirolli, F., IFT-Watershed from gray-scale marker (2002) Proc. of XV Brazilian Symp. on Computer Graphics and Image Processing, pp. 146-152. , October 2002 IEEE New York Miranda, P.A.V., Bergo, F.P.G., Rocha, L.M., Falcão, A.X., Tree-pruning: A new algorithm and its comparative analysis with the watershed transform for automatic image segmentation (2006) XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), , October 2006 IEEE New York Nyul, L.G., Falcão, A.X., Udupa, J.K., Fuzzy-connected 3D image segmentation at interactive speeds (2003) Graph. Models, 64, pp. 259-281. , 5 Roerdink, J.B.T.M., Meijster, A., The watershed transform: Definitions, algorithms and parallelization strategies (2000) Fundam. Inform., 41, pp. 187-228 Saha, P.K., Udupa, J.K., Relative fuzzy connectedness among multiple objects: Theory, algorithms, and applications in image segmentation (2001) Comput. Vis. Image Underst., 82, pp. 42-56 Shi, J., Malik, J., Normalized cuts and image segmentation (2000) IEEE Trans. Pattern Anal. Mach. Intell., 22, pp. 888-905. , 8 Torres, R.S., Falcão, A.X., Contour salience descriptors for effective image retrieval and analysis (2007) Image Vis. Comput., 25, pp. 3-13. , 1 Torres, R.S., Falcão, A.X., Costa, L.F., A graph-based approach for multiscale shape analysis (2004) Pattern Recognit., 37, pp. 1163-1174. , 6 Udupa, J.K., Samarasekera, S., Fuzzy connectedness and object definition: Theory, algorithms, and applications in image segmentation (1996) Graph. Models Image Process., 58, pp. 246-261 Vincent, L., Soille, P., Watersheds in digital spaces: An efficient algorithm based on immersion simulations (1991) IEEE Trans. Pattern Anal. Mach. Intell., 13 (6) Viola, P., Jones, M., Rapid object detection using a boosted cascade of simple features (2001) Int. Conf. on Computer Vision and Pattern Recognition (CVPR), 1, pp. I511-I518 Wang, S., Siskind, J.M., Image segmentation with minimum mean cut (2001) Int. Conf. on Computer Vision (ICCV), 1, pp. 517-525 Zheng, D., Zhao, Y., Wang, J., An efficient method of license plate location (2005) Pattern Recognit. Lett., 26, pp. 2431-2438