Abstract
Representing an image through a tree structure as provided with a morphological hierarchy enables efficient image analysis and processing methods operating directly on the tree structure. Max-tree and min-tree can be built with efficient algorithms but they only focus on brighter and darker components of the image respectively. Conversely, the Tree-of-Shapes is a self-complementary image representation that provides access to all regional extrema of the image (both brighter and darker components), but its computation is more time-consuming. In this paper, we introduce a new, simple and efficient tree structure called median-tree. It relies on a median image that is straightforwardly constructed by subtracting the median pixel value from an image to decompose it into positive and negative parts. The median tree can then be obtained by applying the efficient max-tree algorithms available in the literature on this median image. We show through theoretical and experimental studies that the median-tree offers similar characteristics to the Tree-of-Shapes, but comes with a considerably lower construction complexity.
References
[1] Christophe Berger, Thierry Géraud, Roland Levillain, Nicolas Widynski, Anthony Baillard, and Emmanuel Bertin. “Effective component tree computation with application to pattern recognition in astronomical imaging.” In: IEEE International Conference on Image Processing. 2007, pp. 41–44.10.1109/ICIP.2007.4379949Search in Google Scholar
[2] Petra Bosilj, Ewa Kijak, and Sébastien Lefèvre. “Partition and inclusion hierarchies of images: A comprehensive survey.” In: Journal of Imaging 4.2 (2018), pp. 1–31.10.3390/jimaging4020033Search in Google Scholar
[3] Edwin Carlinet, Sébastien Crozet, and Thierry Géraud. “The tree of shapes turned into a max-tree: a simple and efficient linear algorithm.” In: IEEE International Conference on Image Processing. 2018, pp. 1488–1492.10.1109/ICIP.2018.8451180Search in Google Scholar
[4] Edwin Carlinet and Thierry Géraud. “A comparative review of component tree computation algorithms.” In: IEEE Transactions on Image Processing 23.9 (2014), pp. 3885–3895.10.1109/TIP.2014.2336551Search in Google Scholar
[5] Edwin Carlinet and Thierry Géraud. “MToS: A tree of shapes for multivariate images.” In: IEEE Transactions on Image Processing 24.12 (2015), pp. 5330–5342.10.1109/TIP.2015.2480599Search in Google Scholar
[6] Vicent Caselles and Pascal Monasse. Geometric description of images as topographic maps. Springer, 2009.10.1007/978-3-642-04611-7Search in Google Scholar
[7] Bertrand Charpentier and Thomas Bonald. “Tree sampling divergence: an information-theoretic metric for hierarchical graph clustering.” In: International Joint Conference on Artificial Intelligence (IJCAI). 2019, pp. 2067–2073.10.24963/ijcai.2019/286Search in Google Scholar
[8] Mauro Dalla Mura, Jón Atli Benediktsson, Björn Waske, and Lorenzo Bruzzone. “Morphological attribute profiles for the analysis of very high resolution images.” In: IEEE Transactions on Geoscience and Remote Sensing 48.10 (2010), pp. 3747–3762.10.1109/TGRS.2010.2048116Search in Google Scholar
[9] Thierry Géraud. “Ruminations on Tarjan’s Union-Find algorithm and connected operators.” In: Mathematical Morphology: 40 Years On. Springer, 2005, pp. 105–116.10.1007/1-4020-3443-1_11Search in Google Scholar
[10] Thierry Géraud, Edwin Carlinet, Sébastien Crozet, and Laurent Najman. “A quasi-linear algorithm to compute the tree of shapes of nD images.” In: International symposium on mathematical morphology and its applications to signal and image processing. Springer. 2013, pp. 98–110.10.1007/978-3-642-38294-9_9Search in Google Scholar
[11] Henk Heijmans and Renato Keshet. “First steps towards a self-dual morphology.” In: International Conference on Image Processing. 2000, pp. 934–937.10.1109/ICIP.2000.899870Search in Google Scholar
[12] Earl J Isaac and Richard C Singleton. “Sorting by address calculation.” In: Journal of the ACM (JACM) 3.3 (1956), pp. 169– 174.10.1145/320831.320834Search in Google Scholar
[13] ISPRS 2D semantic labeling contest - Potsdam. http://www2.isprs.org/commissions/comm3/wg4/2d-sem-label-potsdam.html. (Visited on 04/29/2020).Search in Google Scholar
[14] Ronald Jones. “Component trees for image filtering and segmentation.” In: IEEE Workshop on Nonlinear Signal and Image Processing. 1997.Search in Google Scholar
[15] Fernand Meyer. “First departure algorithms and image decompositions into peaks and wells.” In: IEEE Journal of Selected Topics in Signal Processing 6.7 (2012), pp. 795–808.10.1109/JSTSP.2012.2210994Search in Google Scholar
[16] Pascal Monasse. “A Root-to-Leaf Algorithm Computing the Tree of Shapes of an Image.” In: International Workshop on Reproducible Research in Pattern Recognition. Springer. 2018, pp. 43–54.10.1007/978-3-030-23987-9_3Search in Google Scholar
[17] Pascal Monasse and Frédéric Guichard. “Scale-space from a level lines tree.” In: Journal of Visual Communication and Image Representation 11.2 (2000), pp. 224–236.10.1006/jvci.1999.0441Search in Google Scholar
[18] Benjamin Perret, Giovanni Chierchia, Jean Cousty, Silvio Guimarães, Yukiko Kenmochi, and Laurent Najman. “Higra: Hierarchical graph analysis.” In: SoftwareX 10 (2019), p. 100335.10.1016/j.softx.2019.100335Search in Google Scholar
[19] Philippe Salembier, Sergi Liesegang, and Carlos López-Martínez. “Ship detection in SAR images based on maxtree representation and graph signal processing.” In: IEEE Transactions on Geoscience and Remote Sensing 57.5 (2018), pp. 2709–2724.10.1109/TGRS.2018.2876603Search in Google Scholar
[20] Philippe Salembier, Albert Oliveras, and Luis Garrido. “Antiextensive connected operators for image and sequence processing.” In: IEEE Transactions on Image Processing 7.4 (1998), pp. 555–570.10.1109/83.663500Search in Google Scholar
[21] Pierre Soille. “Beyond self-duality in morphological image analysis.” In: Image and Vision Computing 23.2 (2005), pp. 249–257.10.1016/j.imavis.2004.06.002Search in Google Scholar
[22] Pierre Soille. Morphological image analysis: principles and applications. Springer Science & Business Media, 2013.Search in Google Scholar
[23] Yuqing Song and Aidong Zhang. “Monotonic tree.” In: International Conference on Discrete Geometry for Computer Imagery. Springer. 2002, pp. 114–123.10.1007/3-540-45986-3_10Search in Google Scholar
[24] Alla Vichik, Renato Keshet, and David Malah. “A general framework for tree-based morphology and its applications to self-dual filtering.” In: Image and Vision Computing 28.10 (2010), pp. 1443–1451.10.1016/j.imavis.2009.08.008Search in Google Scholar
[25] Yongchao Xu, Thierry Géraud, and Laurent Najman. “Connected filtering on tree-based shape-spaces.” In: IEEE transactions on pattern analysis and machine intelligence 38.6 (2015), pp. 1126–1140.10.1109/TPAMI.2015.2441070Search in Google Scholar
© 2021 Behzad Mirmahboub et al., published by De Gruyter
This work is licensed under the Creative Commons Attribution 4.0 International License.
