Image Segmentation by the Image Foresting Transform

• Paulo A.V. Miranda UNICAMP
• Alexandre X. Falcão UNICAMP

Abstract

The “Image Foresting Transform” (IFT) reduces image processing problems into a minimum-cost path forest problem in a graph derived from the image. We present three new image operators based on the IFT for image segmentation. The first method extends and combines approaches based on fuzzy connectedness, reducing user involvement. The second combines the IFT with graph-cut measures to circumvent problems of the traditional graphcut approaches. The third handles the leaking problem of watershed-based approaches by pruning trees of the forest. The proposed methods run in lineartime, are extensive to multidimensional images, and the last two are also free of “ad-hoc” parameters, and require only internal seeds.

References

Bergo, F., Falcão, A., Miranda, P., and Rocha, L. (2006). Automatic image segmentation by tree pruning. Journal of Mathematical Imaging and Vision. in review.

Boykov, Y. Y. and Jolly, M.-P. (2001). Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In International Conference on Computer Vision (ICCV), volume 1, pages 105–112.

Falcão, A., Miranda, P., and Rocha, A. (2006). A linear-time approach for image segmentation using graph-cut measures. In Advanced Concepts for Intelligent Vision Systems (ACIVS), volume 4179 of LNCS, pages 138–149, Antwerp, Belgium. Springer Berlin / Heidelberg.

Falcão, A. X., Bergo, F. P. G., and Miranda, P. A. V. (2004a). Image segmentation by tree pruning. In XVII SIBGRAPI, pages 65–71. IEEE.

Falcão, A. X., Miranda, P. A. V., Rocha, A., and Bergo, F. G. (2005). Object detection by κ-connected seed competition. In Proc. of XVIII SIBGRAPI, pages 97–104. IEEE.

Falcão, A. X., Stolfi, J., and Lotufo, R. A. (2004b). The image foresting transform: Theory, algorithms, and applications. IEEE Trans. on PAMI, 26(1):19–29.

Frackowiak, R., Friston, K., Frith, C., Dolan, R., Price, C., Zeki, S., Ashburner, J., and Penny, W. (2003). Human Brain Function. Academic Press, 2nd edition.

Miranda, P. (2006). Segmentação de imagens pela transformada imagem-floresta. IC-UNICAMP. [link].

Miranda, P. A. V., Bergo, F. P. G., Rocha, L. M., and Falcão, A. X. (2006). Tree-pruning: A new algorithm and its comparative analysis with the watershed transform for automatic image segmentation. In XIX SIBGRAPI, pages 37–44. IEEE.

Saha, P. K. and Udupa, J. K. (2001). Relative fuzzy connectedness among multiple objects: theory, algorithms, and applications in image segmentation. Computer Vision and Image Understanding, 82:42–56.

Shi, J. and Malik, J. (2000). Normalized cuts and image segmentation. IEEE Trans. on PAMI, 22(8):888–905.

Udupa, J. K. and Samarasekera, S. (1996). Fuzzy connectedness and object definition: theory, algorithms, and applications in image segmentation. Graphical Models and Image Processing, 58:246–261.

Vincent, L. and Soille, P. (1991). Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Trans. on PAMI, 13(6).

Wang, S. and Siskind, J. M. (2001). Image segmentation with minimum mean cut. In Intl. Conf. on Computer Vision (ICCV), volume 1, pages 517–525.