Abstract
Component-graphs are defined as the generalization of component-trees to images taking their values in partially ordered sets. Similarly to component-trees, component-graphs are a lossless image model, and can allow for the development of various image processing approaches (antiextensive filtering, segmentation by node selection). However, component-graphs are not trees, but directed acyclic graphs. This induces a structural complexity associated to a higher combinatorial cost. These properties make the handling of component-graphs a non-trivial task. We propose a preliminary discussion on a new way of building and manipulating component-graphs, with the purpose of reaching reasonable space and time costs. Tackling these complexity issues is indeed required for actually involving component-graphs in efficient image processing approaches.
This work was partly funded by the French program Investissement d’Avenir run by the Agence Nationale pour la Recherche (Grant reference ANR-11-INBS-0006).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
These two variants, called \(\dot{\varTheta }\)- and \({\ddot{\varTheta }}\)-component-graphs, rely on sets of nodes defined as subsets of \(\varTheta \). A \({\ddot{\varTheta }}\)-component graph only contains nodes that are necessary to model I in a lossless way, while the \(\dot{\varTheta }\)-component-graph contains nodes with maximal values for a given support.
- 2.
The image where each flat zone (i.e. maximal connected region of constant value) is replaced by a single point, and where the adjacency relation between these flat zones is inherited from \(\smallfrown \) (i.e. two flat zones are adjacent iff one point of the first is adjacent to one point of the second).
- 3.
In digital imaging, we have \(\mid \smallfrown \mid \ = {\mathcal {O}} (|\varOmega |)\) (e.g. with 4-, 8-, 6- and 26-adjacencies on \({\mathbb {Z}}^2\) and \({\mathbb {Z}}^3\), we have \(\mid \smallfrown \mid \ \simeq k.|\varOmega |\), with \(k = 2\), 4, 3 and 13, respectively), and this generally still holds for the induced flat zone images. Under such hypotheses, the detection of leaves can be performed in linear time \({\mathcal {O}}(|\varOmega |)\) with respect to the size of the image. For the sake of concision, we will assume, from now on, that we have indeed \(\mid \smallfrown \mid \ = {\mathcal {O}} (|\varOmega |)\).
- 4.
By convention, we define a supplementary node \(K_\top \) for handling the cases when the considered value v is greater than (or non-comparable with) the value I(x) associated to x, in order to define \(\kappa \) on the whole Cartesian set \(\varLambda \times V\). This does not induce any algorithmic nor structural issue.
- 5.
Actually, it is surjective iff \(\kappa ^{-1}(\{K_\top \}) \ne \emptyset \). If \(\kappa ^{-1}(\{K_\top \}) = \emptyset \), we can simply define \(\kappa : \varLambda \times V \rightarrow \varTheta \), and then the surjectivity property still holds.
- 6.
The exact upper bound of \(\gamma \) is actually \((|\varOmega |-1)^2 / 4|\varOmega |\), and is reached when \(|\varLambda |= (|\varOmega |+1)/2\).
- 7.
The adjacency relation \(\smallfrown _L\) is indeed a subset of the Cartesian product \(\varLambda \times \varLambda \); so it would be sufficient to define the function \(\sigma :\ \smallfrown _L\ \rightarrow 2^V\). However, such notation is unusual and probably confusing for many readers; then, we prefer to define, without loss of correctness, \(\sigma : \varLambda \times \varLambda \rightarrow 2^V\), with useless empty values for the couples \((x_1,x_2) \in \varLambda \times \varLambda \) such that \(x_1 \not \smallfrown _\varLambda x_2\).
- 8.
Actually, half of these borders, due to the symmetry of the configurations, see Property 14.
- 9.
For instance, for a digital images in \({\mathbb {Z}}^3\) (resp. \({\mathbb {Z}}^2\)) of size \(|\varOmega | = N^3\) (resp. \(N^2\)), we may expect a space cost of \({\mathcal {O}}(N^2)\) (resp. \({\mathcal {O}}(N^1)\)), i.e. \(\delta = 2/3\) (resp. \(\delta = 1/2\)).
- 10.
A sufficient condition is to model \((V,\leqslant )\) as an intermediate data-structure of space cost \({\mathcal {O}}(|V|^2)\).
References
Salembier, P., Wilkinson, M.H.F.: Connected operators: a review of region-based morphological image processing techniques. IEEE Signal Process. Mag. 26, 136–157 (2009)
Salembier, P., Oliveras, A., Garrido, L.: Anti-extensive connected operators for image and sequence processing. IEEE Trans. Image Process. 7, 555–570 (1998)
Monasse, P., Guichard, F.: Scale-space from a level lines tree. J. Vis. Commun. Image Represent. 11, 224–236 (2000)
Salembier, P., Garrido, L.: Binary partition tree as an efficient representation for image processing, segmentation and information retrieval. IEEE Trans. Image Process. 9, 561–576 (2000)
Passat, N., Naegel, B.: An extension of component-trees to partial orders. In: ICIP, 3981–3984. (2009)
Passat, N., Naegel, B.: Component-trees and multivalued images: structural properties. J. Math. Imaging Vis. 49, 37–50 (2014)
Kurtz, C., Naegel, B., Passat, N.: Connected filtering based on multivalued component-trees. IEEE Trans. Image Process. 23, 5152–5164 (2014)
Naegel, B., Passat, N.: Towards connected filtering based on component-graphs. In: Hendriks, C.L.L., Borgefors, G., Strand, R. (eds.) ISMM 2013. LNCS, vol. 7883, pp. 353–364. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38294-9_30
Naegel, B., Passat, N.: Colour image filtering with component-graphs. In: ICPR, pp. 1621–1626 (2014)
Carlinet, E., Géraud, T.: MToS: a tree of shapes for multivariate images. IEEE Trans. Image Process. 24, 5330–5342 (2015)
Xu, Y., Géraud, T., Najman, L.: Connected filtering on tree-based shape-spaces. IEEE Trans. Pattern Anal. Mach. Intell. 38, 1126–1140 (2016)
Grossiord, É., Naegel, B., Talbot, H., Passat, N., Najman, L.: Shape-based analysis on component-graphs for multivalued image processing. In: Benediktsson, J.A., Chanussot, J., Najman, L., Talbot, H. (eds.) ISMM 2015. LNCS, vol. 9082, pp. 446–457. Springer, Cham (2015). doi:10.1007/978-3-319-18720-4_38
Perret, B., Cousty, J., Tankyevych, O., Talbot, H., Passat, N.: Directed connected operators: asymmetric hierarchies for image filtering and segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 37, 1162–1176 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Passat, N., Naegel, B., Kurtz, C. (2017). Implicit Component-Graph: A Discussion. In: Angulo, J., Velasco-Forero, S., Meyer, F. (eds) Mathematical Morphology and Its Applications to Signal and Image Processing. ISMM 2017. Lecture Notes in Computer Science(), vol 10225. Springer, Cham. https://doi.org/10.1007/978-3-319-57240-6_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-57240-6_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-57239-0
Online ISBN: 978-3-319-57240-6
eBook Packages: Computer ScienceComputer Science (R0)