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.2902/03/15141162Audigier, 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. , 4Beucher, S., Meyer, F., The morphological approach to segmentation: The watershed transformation (1993) Mathematical Morphology in Image Processing, pp. 433-481. , Marcel Dekker New YorkBoykov, 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-112Cohen, L.D., On active contour models and balloons (1991) Comput. Vis. Graph. Image Process. Image Underst., 53, pp. 211-218. , 2Collins, 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. , 3Cootes, T., Edwards, G., Taylor, C.J., Active appearance models (1998) European Conference on Computer Vision (ECCV), 2, pp. 484-498Cootes, T., Taylor, C., Cooper, D., Graham, J., Active shape models-their training and application (1995) Comput. Vis. Image Underst., 61, pp. 38-59. , 1Duda, R.O., Hart, P.E., Stork, D.G., (2000) Pattern Classification, , Wiley-Interscience New YorkFalcão, A.X., Bergo, F.P.G., Interactive volume segmentation with differential image foresting transforms (2004) IEEE Trans. Med. Imaging, 23, pp. 1100-1108. , 9Falcã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 YorkFalcã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. , 7Falcã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-479Falcã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. , 1Falcã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. , 1Falcã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. , 4Ford, L., Fulkerson, D., (1962) Flows in Networks, , Princeton University Press PrincetonFrackowiak, 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 YorkGrau, 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. , 4Haykin, S., (1998) Neural Networks: A Comprehensive Foundation, , Prentice-Hall New YorkKass, M., Witkin, A., Terzopoulos, D., Snakes: Active contour models (1987) Int. J. Comput. Vis., 1, pp. 321-331Kolmogorov, V., Zabih, R., What energy functions can be minimized via graph cuts (2004) IEEE Trans. Pattern Anal. Mach. Intell., 26, pp. 147-159. , 2Kuncheva, L.I., (2004) Combining Pattern Classifiers: Methods and Algorithms, , Wiley-Interscience New YorkLotufo, 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 DordrechtLotufo, 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 YorkMiranda, 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 YorkNyul, L.G., Falcão, A.X., Udupa, J.K., Fuzzy-connected 3D image segmentation at interactive speeds (2003) Graph. Models, 64, pp. 259-281. , 5Roerdink, J.B.T.M., Meijster, A., The watershed transform: Definitions, algorithms and parallelization strategies (2000) Fundam. Inform., 41, pp. 187-228Saha, 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-56Shi, J., Malik, J., Normalized cuts and image segmentation (2000) IEEE Trans. Pattern Anal. Mach. Intell., 22, pp. 888-905. , 8Torres, R.S., Falcão, A.X., Contour salience descriptors for effective image retrieval and analysis (2007) Image Vis. Comput., 25, pp. 3-13. , 1Torres, R.S., Falcão, A.X., Costa, L.F., A graph-based approach for multiscale shape analysis (2004) Pattern Recognit., 37, pp. 1163-1174. , 6Udupa, J.K., Samarasekera, S., Fuzzy connectedness and object definition: Theory, algorithms, and applications in image segmentation (1996) Graph. Models Image Process., 58, pp. 246-261Vincent, 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-I518Wang, S., Siskind, J.M., Image segmentation with minimum mean cut (2001) Int. Conf. on Computer Vision (ICCV), 1, pp. 517-525Zheng, D., Zhao, Y., Wang, J., An efficient method of license plate location (2005) Pattern Recognit. Lett., 26, pp. 2431-2438