Image and Multimedia Data Science Laboratory (IMSCIENCE)
Image and Multimedia Data Science Laboratory (IMScience)
 
PUC Minas

Design differential Image Foresting Transform for dynamic weight functions

Abstract

Image segmentation aims to simulate the human ability to distinguish significant regions in images and is used in several tasks, such as image editing [8, 9] and medical image analysis [18, 22]. The IFT is a framework that simplifies several image analysis approaches. The IFT presents a computationally efficient algorithm, which calculates an optimum-path forest in a graph from an initial set of seeds. Among the methods used for image segmentation, the IFT stands out for presenting a structure that unifies several segmentation methodologies based on similar concepts. In addition to having several applications in image segmentation [3, 5, 17, 21], its applications also involve border tracking [2, 11], skeletonization [13], clustering [7, 20], and pixel classification [19]. Due to the generalization of its operators, several cost functions were proposed considering different characteristics that best suit each task. However, segmentation methods based on seed competition, such as the IFT, tend to be sensitive to the set of seeds used. Therefore, the choice of seed quantity and position can be decisive for a good result. Due to this limitation, some works have been exploring different iterative approaches, which recalculates the position of the seeds [1, 15, 21] or selects the most relevant ones [4, 5]. Both interactive and iterative segmentation requires multiple segmentations to obtain the final result, which increases the time for the algorithm execution, reducing its efficiency.

In [14] the authors proposed the Differential Image Foresting Transform (DIFT) to calculate multiple sequential IFTs using the previous forest to calculate the next iteration, rather than restarting the process from the beginning. However, the DIFT is limited to Monotonically Incremental (MI) functions. Later, it was possible to do the same with non-monotonic incremental functions (NMI) based on roots, whose proposal was called General DIFT (GDIFT) [10]. In recent years, several works have explored the dynamic cost functions [4, 5, 16], which use tree characteristics to calculate the weights of the arcs, with their use called Dynamic Trees (DT) [6]. The DT functions proved to be able to incorporate object information and proved to be more effective than other approaches [6,12]. Despite the recent IFT-based approaches having looked to iteration a way to make better seed choices, the DT functions with such methods would have a higher computational cost, due to the lack of approaches to perform this computation more efficiently. Therefore, tasks that require a greater computational effort, as is also the case of 3D image segmentation, may become unfeasible without a more efficient solution. Although DIFT and GDIFT present an important step towards the efficient application of iterative and interactive methods based on IFT, their operators are restricted to MI and root-based NMI functions. This limitation prevents its use with more robust operators [6, 12]. Therefore, making time expensive IFT segmentation methods with DT functions for several interactions or iterations, since it needs to compute the whole forest at each iteration/interaction.

Iterative segmentation

Example

In this work, we proposes a differential solution using DT functions. This solution can allow more efficient computation in iterative and iterative algorithms based on IFT using the DT functions. Furthermore, this solution can motivate IFT-based segmentation strategies with new DT functions, as well as provide guidelines for creating differentials for these functions.

Major goals

In this context, our major goal is to advance the state-of-the-art in functions taking into account the differential image foresting transform:

Contact

Caso tenha interesse neste projeto, por favor, preenche este formulário indicando Design differential Image Foresting Transform:

Reference

  1. Alexandre, E.B., Chowdhury, A.S., Falcão, A.X., Miranda, P.A.V.: IFT-SLIC: A general framework for superpixel generation based on simple linear iterative clustering and image foresting transform. In: 2015 28th SIBGRAPI Conference on Graphics, Patterns and Images. pp. 337–344. IEEE (2015)

  2. Bejar, H.H.C., Cappabianco, F.A.M., Miranda, P.A.V.: Efficient image segmentation in graphs with localized curvilinear features. In: Battiato, S., Gallo, G., Schettini, R., Stanco, F. (eds.) Image Analysis and Processing - ICIAP 2017. pp. 718–728. Springer International Publishing, Cham (2017)

  3. Belém, F., Guimarães, S.J.F., Falcão, A.X.: Superpixel segmentation by object-based iterative spanning forest. In: Vera-Rodriguez, R., Fierrez, J., Morales, A.(eds.) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. pp. 334–341. Springer International Publishing, Cham (2019)

  4. Belém, F.C., Guimarães, S.J.F., Falcão, A.X.: Superpixel segmentation using dynamic and iterative spanning forest. IEEE Signal Processing Letters 27, 1440–1444 (2020). https://doi.org/10.1109/LSP.2020.3015433

  5. Borlido Barcelos, I., Belém, F., Miranda, P., Falcão, A.X., do Patrocínio, Z.K.G., Guimarães, S.J.F.: Towards interactive image segmentation by dynamic and iterative spanning forest. In: Lindblad, J., Malmberg, F., Sladoje, N. (eds.) Discrete Geometry and Mathematical Morphology. pp. 351–364. Springer International Publishing, Cham (2021)

  6. Bragantini, J., Martins, S.B., Castelo-Fernandez, C., Falcão, A.X.: Graph-based image segmentation using dynamic trees. In: Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. pp. 470–478. Springer International Publishing, Cham (2019)

  7. Cappabianco, F.A., Falcao, A.X., Yasuda, C.L., Udupa, J.K.: Brain tissue mr-image segmentation via optimum-path forest clustering. Computer Vision and Image Understanding 116(10), 1047–1059 (2012). https://doi.org/https://doi.org/10.1016/j.cviu.2012.06.002, https://www.sciencedirect.com/science/article/pii/S1077314212000999

  8. Cheng, M.M., Hou, Q.B., Zhang, S.H., Rosin, P.L.: Intelligent visual media processing: When graphics meets vision. Journal of Computer Science and Technology 32(1), 110–121 (2017)

  9. Cheng, M.M., Zhang, F.L., Mitra, N.J., Huang, X., Hu, S.M.: Repfinder: finding approximately repeated scene elements for image editing. ACM Transactions on Graphics (TOG) 29(4), 1–8 (2010)

  10. Condori, M.A., Cappabianco, F.A., Falcão, A.X., Miranda, P.A.: An extension of the differential image foresting transform and its application to superpixel generation. Journal of Visual Communication and Image Representation 71, 102748 (2020). https://doi.org/https://doi.org/10.1016/j.jvcir.2019.102748, https://www.sciencedirect.com/science/article/pii/S1047320319303694

  11. Condori, M.A., Mansilla, L.A., Miranda, P.A.: Bandeirantes: A graph-based approach for curve tracing and boundary tracking. In: International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing. pp. 95–106. Springer, Cham (2017). https://doi.org/https://doi.org/10.1007/978-3-319-57240-6 8

  12. Falcão, A., Bragantini, J.: The role of optimum connectivity in image segmentation: Can the algorithm learn object information during the process? In: Discrete Geometry for Computer Imagery. pp. 180–194. Springer International Publishing, Cham (2019)

  13. Falcão, A.X., Feng, C., Kustra, J., Telea, A.: Multiscale 2d medial axes and 3d surface skeletons by the image foresting transform. Skeletonization: Theory, Methods and Applications p. 43 (2017)

  14. Falcão, A.X., Bergo, F.: Interactive volume segmentation with differential image foresting transforms. IEEE Transactions on Medical Imaging 23(9), 1100–1108 (Sep 2004). https://doi.org/10.1109/TMI.2004.829335

  15. Galvão, F.L., Falcão, A.X., Chowdhury, A.S.: Risf: recursive iterative spanning forest for superpixel segmentation. In: 2018 31st SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI). pp. 408–415. IEEE (2018)

  16. Jerônimo, C., Belém, F., Carneiro, S.A., Patrocínio, Z.K.G., Najman, L., Falcão, A., Guimarães, S.J.F.: Graph-based supervoxel computation from iterative spanning forest. In: Lindblad, J., Malmberg, F., Sladoje, N. (eds.) Discrete Geometry and Mathematical Morphology. pp. 404–415. Springer International Publishing, Cham (2021)

  17. Leon, L.M., Ciesielski, K.C., Miranda, P.A.: Efficient hierarchical multi-object segmentation in layered graphs. Mathematical Morphology-Theory and Applications 5(1), 21–42 (2021)

  18. Merjulah, R., Chandra, J.: Segmentation technique for medical image processing: A survey. In: 2017 International Conference on Inventive Computing and Informatics (ICICI). pp. 1055–1061. IEEE (2017). https://doi.org/10.1109/ICICI.2017.8365301

  19. Papa, J.P., Falcao, A.X., Suzuki, C.T.: Supervised pattern classification based on optimum-path forest. International Journal of Imaging Systems and Technology 19(2), 120–131 (2009)

  20. Rocha, L.M., Cappabianco, F.A., Falcão, A.X.: Data clustering as an optimum-path forest problem with applications in image analysis. International Journal of Imaging Systems and Technology 19(2), 50–68 (2009)

  21. Vargas-Mu ̃noz, J.E., Chowdhury, A.S., Alexandre, E.B., Galvão, F.L., Vechiatto Miranda, P.A., Falcão, A.X.: An iterative spanning forest framework for superpixel segmentation. IEEE Transactions on Image Processing 28(7), 3477–3489 (July 2019). https://doi.org/10.1109/TIP.2019.2897941

  22. Wang, G., Zuluaga, M.A., Li, W., Pratt, R., Patel, P.A., Aertsen, M., Doel, T., David, A.L., Deprest, J., Ourselin, S., et al.: Deepigeos: a deep interactive geodesic framework for medical image segmentation. IEEE transactions on pattern analysis and machine intelligence 41(7), 1559–1572 (2018)