Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity: the case of the Felzenszwalb-Huttenlocher method. (English) Zbl 1469.68158
Math. Morphol., Theory Appl. 2, 55-75 (2017); erratum ibid. 3, 71 (2019).
Summary: This article is a first attempt towards a general theory for hierarchizing non-hierarchical image segmentation method depending on a region-dissimilarity parameter which controls the desired level of simplification: each level of the hierarchy is “as close as possible” to the result that one would obtain with the non-hierarchical method using the corresponding scale as simplification parameter. The introduction of this hierarchization problem in the form of an optimization problem, as well as the proposed tools to tackle it, is an important contribution of the present article. Indeed, with the hierarchized version of a segmentation method, the user can just select the level in the hierarchy, controlling the desired number of regions or can leverage on any of the tools introduced in hierarchical analysis. The main example investigated in this study is the criterion proposed by Felzenszwalb and Huttenlocher for which we show that the results of the hierarchized version of the segmentation method are better than those of the original one with the added property that it satisfies the strong causality and location principles from scale-sets image analysis. An interesting perspective of this work, considering the current trend in computer vision, is obviously, on a specific application, to use learning techniques and train a criterion to choose the correct region.
MSC:
| 68U10 | Computing methodologies for image processing |
Keywords:
scale-set theory; quasi-flat zone hierarchy; minimum spanning tree; hierarchical image segmentation; graph-based methodReferences:
| [1] | Arbelaez, P., Maire, M., Fowlkes, C., Malik, J.: Contour detection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 898-916 (2011). http://doi.ieeecomputersociety.org/10.1109/TPAMI.2010.161; |
| [2] | Beucher, S.: Watershed, hierarchical segmentation and waterfall algorithm. In: J. Serra, P. Soille (eds.) Mathematical Morphology and Its Applications to Image Processing, Computational Imaging and Vision, vol. 2, pp. 69-76. Kluwer (1994); · Zbl 0823.00019 |
| [3] | Cardelino, J., Caselles, V., Bertalmio, M., Randall, G.: A contrario selection of optimal partitions for image segmentation. SIAM Journal on Imaging Sciences 6(3), 1274-1317 (2013); · Zbl 1279.68321 |
| [4] | Couprie, C., Farabet, C., Najman, L., Lecun, Y.: Convolutional nets and watershed cuts for real-time semantic labeling of rgbd video. The Journal of Machine Learning Research 15, 3489-3511 (2014); |
| [5] | Cousty, J., Bertrand, G., Najman, L., Couprie, M.:Watershed cuts: Minimumspanning forests and the drop of water principle. IEEE Transactions on Pattern Analysis and Machine Intelligence 31(8), 1362-1374 (2009); |
| [6] | Cousty, J., Najman, L., Kenmochi, Y., Guimarães, S.: New characterizations of minimumspanning trees and of saliencymaps based on quasi-flat zones. In:Mathematical Morphology and Its Applications to Signal and Image Processing, pp. 205-216. Springer (2015); · Zbl 1445.68286 |
| [7] | Cousty, J., Najman, L., Kenmochi, Y., Guimarães, S.: Hierarchical segmentations with graphs: Quasi-flat zones, minimum spanning trees, and saliency maps. Journal of Mathematical Imaging and Vision (2017). 10.1007/s10851-017-0768-7. URL https://doi.org/10.1007/s10851-017-0768-7; · Zbl 1420.94010 |
| [8] | Cousty, J., Najman, L., Perret, B.: Constructive links between some morphological hierarchies on edge-weighted graphs. In: Proceedings of 11th International SymposiumonMathematical Morphology - ISMM2013, Lecture Notes in Computer Science, vol. 7883, pp. 86-97. Springer (2013); · Zbl 1382.68291 |
| [9] | Felzenszwalb, P.F., Huttenlocher, D.P.: Efficient graph-based image segmentation. International Journal of Computer Vision 59, 167-181 (2004); · Zbl 1477.68505 |
| [10] | Guigues, L., Cocquerez, J.P., Men, H.L.: Scale-sets image analysis. International Journal of Computer Vision 68(3), 289-317 (2006); · Zbl 1477.68508 |
| [11] | Guigues, L., Le Men, H., Cocquerez, J.P.: The hierarchy of the cocoons of a graph and its application to image segmentation. Pattern Recognition Letters 24(8), 1059-1066 (2003); · Zbl 1028.68189 |
| [12] | Guimarães, S.J.F., Cousty, J., Kenmochi, Y., Najman, L.: A hierarchical image segmentation algorithm based on an observation scale. In: SSPR/SPR, pp. 116-125 (2012); |
| [13] | Guimarães, S.J.F., do Patrocínio Jr., Z.K.G., Kenmochi, Y., Cousty, J., Najman, L.: Hierarchical image segmentation relying on a likelihood ratio test. In: V. Murino, E. Puppo (eds.) Image Analysis and Processing - ICIAP 2015 - 18th International Conference, Genoa, Italy, September 7-11, 2015, Proceedings, Part II, Lecture Notes in Computer Science, vol. 9280, pp. 25-35. Springer (2015). 10.1007/978-3-319-23234-8_3. URL http://dx.doi.org/10.1007/978-3-319-23234-8_3; |
| [14] | Haxhimusa, Y., Ion, A., Kropatsch,W.G.: Irregular Pyramid Segmentations with Stochastic Graph Decimation Strategies, pp. 277-286. Springer Berlin Heidelberg (2006); |
| [15] | Haxhimusa, Y., Kropatsch, W.: Hierarchy of partitions with dual graph contraction. In: Pattern Recognition, pp. 338-345. Springer (2003); |
| [16] | Haxhimusa, Y., Kropatsch, W.G.: Segmentation graph hierarchies. In: A.L.N. Fred, T. Caelli, R.P.W. Duin, A.C. Campilho, D. de Ridder (eds.) Structural, Syntactic, and Statistical Pattern Recognition, Joint IAPR International Workshops, SSPR 2004 and SPR 2004, Lisbon, Portugal, August 18-20, 2004 Proceedings, Lecture Notes in Computer Science, vol. 3138, pp. 343-351. Springer (2004). 10.1007/978-3-540-27868-9_36. URL http://dx.doi.org/10.1007/978-3-540-27868-9_36; · Zbl 1104.68615 |
| [17] | Kiran, B.R., Serra, J.: Global-local optimizations by hierarchical cuts and climbing energies. Pattern Recognition 47(1), 12- 24 (2014); · Zbl 1326.68294 |
| [18] | Laurent Najman, M.S.: Geodesic saliency ofwatershed contours and hierarchical segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 18(12), 1163-1173 (1996); |
| [19] | Marfil, R., Molina-Tanco, L., Bandera, A., Rodríguez, J., Sandoval, F.: Pyramid segmentation algorithms revisited. Pattern Recognition 39(8), 1430 - 1451 (2006); · Zbl 1094.68687 |
| [20] | Martin, D.R.: An empirical approach to grouping and segmentation. Ph.D. thesis, EECS Department, University of California, Berkeley (2003). URL http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/5252.html; |
| [21] | Martin, D.R., Fowlkes, C.C., Malik, J.: Learning to detect natural image boundaries using local brightness, color, and texture cues. IEEE Trans. Pattern Anal. Mach. Intell. 26(5), 530-549 (2004). 10.1109/TPAMI.2004.1273918. URL http://dx.doi.org/ 10.1109/TPAMI.2004.1273918; |
| [22] | Meyer, F.: The Dynamics of Minima and Contours, pp. 329-336. Springer US, Boston, MA (1996); · Zbl 0918.68154 |
| [23] | Meyer, F., Maragos, P.: Morphological Scale-Space Representation with Levelings, pp. 187-198. Springer Berlin Heidelberg (1999); |
| [24] | Morris, O.J., Lee, M.J., Constantinides, A.G.: Graph theory for image analysis: an approach based on the shortest spanning tree. Communications, Radar and Signal Processing, IEE Proceedings F 133(2), 146 -152 (1986); |
| [25] | Nacken, P.F.: Image segmentation by connectivity preserving relinking in hierarchical graph structures. Pattern Recognition 28(6), 907 - 920 (1995); |
| [26] | Najman, L.: On the equivalence between hierarchical segmentations and ultrametric watersheds. Journal of Mathematical Imaging and Vision 40, 231-247 (2011); · Zbl 1255.68258 |
| [27] | Nock, R., Nielsen, F.: Statistical region merging. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(11), 1452-1458 (2004); |
| [28] | Pavildis, T.: Structural pattern recognition. Springer-Verlag (1977); · Zbl 0382.68071 |
| [29] | Perret, B., Cousty, J., Ura, J.C.R., Guimarães, S.J.F.: Evaluation of morphological hierarchies for supervised segmentation. In: Mathematical Morphology and Its Applications to Signal and Image Processing, pp. 39-50. Springer International Publishing (2015); · Zbl 1445.68311 |
| [30] | Pont-Tuset, J., Marqués, F.: Measures and meta-measures for the supervised evaluation of image segmentation. In: Computer Vision and Pattern Recognition (CVPR) (2013); |
| [31] | Pont-Tuset, J.,Marques, F.: Supervised evaluation of image segmentation and object proposal techniques. IEEE Transactions on Pattern Analysis and Machine Intelligence (2015). To appear; |
| [32] | Ronse, C.: Ordering partial partitions for image segmentation and filtering: Merging, creating and inflating blocks. Journal of Mathematical Imaging and Vision 49(1), 202-233 (2014); · Zbl 1291.68422 |
| [33] | Salembier, P., Garrido, L.: Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval. Image Processing, IEEE Transactions on 9(4), 561-576 (2000). 10.1109/83.841934; |
| [34] | Serra, J.: A lattice approach to image segmentation. Journal of Mathematical Imaging and Vision 24(1), 83-130 (2006); · Zbl 1478.94082 |
| [35] | Soille, P.: Constrained connectivity for hierarchical image partitioning and simplification. Pattern Analysis and Machine Intelligence, IEEE Transactions on 30(7), 1132-1145 (2008); |
| [36] | de Souza, K.J.F., de Albuquerque Araújo, A., do Patrocínio Jr., Z.K.G., Guimarães, S.J.F.: Graph-based hierarchical video segmentation based on a simple dissimilarity measure. Pattern Recognition Letters 47, 85-92 (2014). 10.1016/j.patrec.2014.02.016. URL http://dx.doi.org/10.1016/j.patrec.2014.02.016; |
| [37] | Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. Journal of the ACM 22(2), 215-225 (1975); · Zbl 0307.68029 |
| [38] | Varas, D., Alfaro, M., Marqués, F.: Multiresolution hierarchy co-clustering for semantic segmentation in sequences with small variations. In: ICCV - International Conference on Computer Vision (2015). URL http://arxiv.org/abs/1510.04842; |
| [39] | Xu, Y., Géraud, T., Najman, L.: Connected filtering on tree-based shape-spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 38(6), 1126-1140 (2016); |
| [40] | Zahn, C.T.: Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Trans. Comput. 20, 68-86 (1971); · Zbl 0264.68040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
