Segmentation and skeletonization on arbitrary graphs using multiscale morphology and active contours. (English) Zbl 1314.68354
Breuß, Michael (ed.) et al., Innovations for shape analysis. Models and algorithms. Heidelberg: Springer (ISBN 978-3-642-34140-3/hbk; 978-3-642-34141-0/ebook). Mathematics and Visualization, 53-75 (2013).
Summary: In this chapter, we focus on formulating and implementing on abstract domains such as arbitrary graphs popular methods and techniques developed for image analysis, in particular multiscale morphology and active contours. To this goal, we extend existing work on graph morphology to multiscale dilation and erosion and implement them recursively using level sets of functions defined on the graph’s nodes. We propose approximations to the calculation of the gradient and the divergence of vector functions defined on graphs and use these approximations to apply the technique of geodesic active contours for object detection on graphs via segmentation. Finally, using these novel ideas, we propose a method for multiscale shape skeletonization on arbitrary graphs.
For the entire collection see [Zbl 1311.68009].
For the entire collection see [Zbl 1311.68009].
MSC:
| 68U10 | Computing methodologies for image processing |
| 05C90 | Applications of graph theory |
| 68T45 | Machine vision and scene understanding |
References:
| [1] | Alvarez, L.; Guichard, F.; Lions, PL; Morel, JM, Axioms and fundamental equations of image processing, Arch. Ration. Mech., 123, 2, 199-257 (1993) · Zbl 0788.68153 · doi:10.1007/BF00375127 |
| [2] | Arcelli, C.; Sanniti di Baja, G.; Serino, L., Distance-driven skeletonization in voxel images, IEEE Trans. Pattern Anal. Mach. Intell., 33, 4, 709-720 (2011) |
| [3] | Aslan, C.; Erdem, A.; Erdem, E.; Tari, S., Disconnected skeleton: shape at its absolute scale, IEEE Trans. Pattern Anal. Mach. Intell., 30, 12, 2188-2203 (2008) · doi:10.1109/TPAMI.2007.70842 |
| [4] | Bensoussan, A.; Menaldi, J., Difference equations on weighted graphs, J. Convex Anal., 12, 1, 13-44 (2005) · Zbl 1068.05039 |
| [5] | Blum, H.: A transformation for extracting new descriptors of shape. In: Proceedings of a Symposium on Models for the Perception of Speech and Visual Forms, Boston, Nov. 1964. MIT, Cambridge MA (1967) |
| [6] | Borgefors, G.; Nyström, I.; Siddiqi, K.; Pizer, S., Sanniti di Baja, G.: Discrete skeletons from distance transforms in 2D and 3D, Medial Representations: Mathematics (2008), Dordrecht: Algorithms and Applications. Springer, Dordrecht · Zbl 1151.00014 |
| [7] | Boykov, Y.; Kolmogorov, V., An experimental comparison of Min-Cut/Max-Flow Algorithms for energy minimization in vision, IEEE Trans. Pattern Anal. Mach. Intell., 26, 9, 1124-1137 (2004) · doi:10.1109/TPAMI.2004.60 |
| [8] | Boykov, Y.; Veksler, O.; Zabih, R., Fast approximate energy minimization via graph cuts, IEEE Trans. Pattern Anal. Mach. Intell., 23, 11, 1222-1239 (2001) · doi:10.1109/34.969114 |
| [9] | Breuß, M.; Weickert, J., A shock-capturing algorithm for the differential equations of Dilation and Erosion, J. Math. Imaging Vis., 25, 187-201 (2006) · Zbl 1478.94015 · doi:10.1007/s10851-006-9696-7 |
| [10] | Breuß, M.; Weickert, J., Highly accurate schemes for PDE-based morphology with general convex structuring elements, Int. J. Comput. Vis., 92, 2, 132-145 (2011) · Zbl 1235.68249 · doi:10.1007/s11263-010-0366-2 |
| [11] | Brockett, RW; Maragos, P., Evolution equations for continuous-scale morphological filtering, IEEE Trans. Signal Process., 42, 12, 3377-3386 (1994) · doi:10.1109/78.340774 |
| [12] | Caselles, V.; Catte, F.; Coll, T.; Dibos, F., A geometric model for active contours in image processing, Numerische Mathematik, 66, 1, 1-31 (1993) · Zbl 0804.68159 · doi:10.1007/BF01385685 |
| [13] | Caselles, V.; Kimmel, R.; Sapiro, G., Geodesic active contours, Int. J. Comput. Vis., 22, 1, 61-79 (1997) · Zbl 0894.68131 · doi:10.1023/A:1007979827043 |
| [14] | Chung, S.-Y.; Berenstein, CA, Omega-Harmonic functions and inverse conductivity problems on networks, SIAM J. Appl. Math., 65, 1200-1226 (2005) · Zbl 1068.05040 · doi:10.1137/S0036139903432743 |
| [15] | Cootes, TF; Edwards, GJ; Taylor, CJ, Active appearance models, IEEE Trans. Pattern Anal. Mach. Intell., 23, 6, 681-685 (2001) · doi:10.1109/34.927467 |
| [16] | Couprie, C.; Grady, L.; Najman, L.; Talbot, H., Power watershed: a unifying graph-based optimization framework, IEEE Trans. Pattern Anal. Mach. Intell., 33, 7, 1384-1399 (2011) · doi:10.1109/TPAMI.2010.200 |
| [17] | Cousty, J., Najman, L., Serra, J.: Some morphological operators in graph spaces. In: Proceedings of the International Symposium on Mathematical Morphology. Lecture Notes in Computer Science, 5720. Springer, Berlin/New York (2009) · Zbl 1252.68330 |
| [18] | Hassouna, MS; Farag, AA, Variational curve skeletons using gradient vector flow, IEEE Trans. Pattern Anal. Mach. Intell., 31, 12, 2257-2274 (2009) · doi:10.1109/TPAMI.2008.271 |
| [19] | Heijmans, H. J.A. M., Morphological Image Operators (1994), Boston: Academic, Boston · Zbl 0869.68119 |
| [20] | Heijmans, H. J.A. M.; Nacken, P.; Toet, A.; Vincent, L., Graph morphology, J. Vis. Commun. Image Represent., 3, 1, 24-38 (1992) · doi:10.1016/1047-3203(92)90028-R |
| [21] | Heijmans, H. J.A. M.; Vincent, L.; Dougherty, ER, Graph morphology in image analysis, Mathematical Morphology in Image Processing (1993), New York: Marcel Dekker, New York |
| [22] | Kass, M.; Witkin, A.; Terzopoulos, D., Snakes: active contour models, Int. J. Comput. Vis., 1, 4, 321-331 (1988) · doi:10.1007/BF00133570 |
| [23] | Kimia, B.; Tannenbaum, A.; Zucker, S., On the evolution of curves via a function of curvature, I. The classical case. J. Math. Anal. Appl., 163, 438-458 (1992) · Zbl 0771.53003 · doi:10.1016/0022-247X(92)90260-K |
| [24] | Komodakis, N.; Paragios, N.; Tziritas, G., MRF energy minimization and beyond via dual decomposition, IEEE Trans. Pattern Anal. Mach. Intell., 33, 531-552 (2011) · doi:10.1109/TPAMI.2010.108 |
| [25] | Kresch, R.; Malah, D., Skeleton-based morphological coding of binary images, IEEE Trans. Image Process., 7, 10, 1387-1399 (1998) · Zbl 0948.68202 · doi:10.1109/83.718480 |
| [26] | Lantuejoul, C.; Haralick, RM; Simon, JC, Skeletonization in quantitative metallography, Issues of Digital Image Processing (1980), Groningen: Sijthoff and Noordhoff, Groningen |
| [27] | Malladi, R.; Sethian, JA; Vemuri, BC, A Fast Level Set based Algorithm for Topology-Independent Shape Modeling, J. Math. Imaging Vis., 6, 269-289 (1996) · Zbl 1490.68251 · doi:10.1007/BF00119843 |
| [28] | Maragos, P., Pattern spectrum and multiscale shape representation, IEEE Trans. Pattern Anal. Mach. Intell., 11, 701-716 (1989) · Zbl 0676.68050 · doi:10.1109/34.192465 |
| [29] | Maragos, P.; Schafer, RW, Morphological skeleton representation and coding of binary images, IEEE Trans. Acoust. Speech Signal Process., 34, 1228-1244 (1986) · doi:10.1109/TASSP.1986.1164959 |
| [30] | Matheron, G., Random Sets and Integral Geometry (1975), New York: Wiley, New York · Zbl 0321.60009 |
| [31] | McInerney, T., Terzopoulos, D.: Topologically adaptable snakes. In: Proceedings of the Int’l Conference on Computer Vision, pp. 840-845 (1995) |
| [32] | Osher, S.; Sethian, JA, Fronts propagating with curvature dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79, 12-49 (1988) · Zbl 0659.65132 · doi:10.1016/0021-9991(88)90002-2 |
| [33] | Pizer, SM; Siddiqi, K.; Székely, G.; Damon, JN; Zucker, SW, Multiscale medial loci and their properties, Int. J. Comput. Vis., 55, 2-3, 155-179 (2003) · Zbl 1477.68409 · doi:10.1023/A:1026135101267 |
| [34] | Rosenfeld, A.; Kak, AC, Digital Picture Processing: Vol I and II (1982), New York/London/Paris: Academic, New York/London/Paris |
| [35] | Sapiro, G.; Kimmel, R.; Shaked, D.; Kimia, B.; Bruckstein, A., Implementing continuous-scale morphology via curve evolution, Pattern Recognit., 26, 9, 1363-1372 (1993) · doi:10.1016/0031-3203(93)90142-J |
| [36] | Serra, J., Image Analysis and Mathematical Morphology (1982), London/New York: Academic, London/New York · Zbl 0565.92001 |
| [37] | Serra, J. (ed.): Image Analysis and Mathematical Morphology. Volume 2: Theoretical Advances. Academic, London/New York (1988) |
| [38] | Siddiqi, K.; Buix, S.; Tannenbaum, A.; Zucker, W., Hamilton-Jacobi skeletons. Int. J. Comput. Vis., 48, 3, 215-231 (2002) · Zbl 1012.68757 · doi:10.1023/A:1016376116653 |
| [39] | Ta, V.-T.; Elmoataz, A.; Lézoray, O., Nonlocal PDEs-based morphology on weighted graphs for image and data processing, IEEE Trans. Image Process., 20, 6, 1504-1516 (2011) · Zbl 1372.35317 · doi:10.1109/TIP.2010.2101610 |
| [40] | Tari, S.: Hierarchical shape decomposition via level sets. In: Proceedings of the International Symposium on Mathematical Morphology. Lecture Notes in Computer Science, 5720. Springer, Berlin/New York (2009) · Zbl 1252.94023 |
| [41] | Vincent, L., Graphs and mathematical morphology, Signal Process., 16, 4, 365-388 (1989) · doi:10.1016/0165-1684(89)90031-5 |
| [42] | Yedidia, JS; Freeman, WT; Weiss, Y., Constructing free energy approximations and generalized belief propagation algorithms, IEEE Trans. Inf. Theory, 51, 7, 2282-2312 (2005) · Zbl 1283.94023 · doi:10.1109/TIT.2005.850085 |
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.
