zbMATH — the first resource for mathematics

Vector-based morphological operations on polygons using straight skeletons for digital pathology. (English) Zbl 07118261
Couprie, Michel (ed.) et al., Discrete geometry for computer imagery. 21st IAPR international conference, DGCI 2019, Marne-la-Vallée, France, March 26–28, 2019, Proceedings. Cham: Springer (ISBN 978-3-030-14084-7/pbk; 978-3-030-14085-4/ebook). Lecture Notes in Computer Science 11414, 249-261 (2019).
Summary: In this work we present an efficient implementation of vector-based mathematical morphology operators applied to simple polygons by performing wavefront propagation and computing polygon straight skeletons. In Digital Pathology (DP), the slide scanner generates important volume of images from tissues called Whole Slide Image (WSI). The main goal of the DP is to detect the biological stained structures in order to quantify the tissue pathology, such as lesions or cancerous regions. We propose the use of Adapted Straight Skeletons on polygons as an efficient technique in time and memory, to improve image segmentation and image analysis. Thanks to the use of polygons instead of bitmaps to store segmentation results, the performance of straight skeletons depends only on the polygon control points. These straight skeletons can be applied in order to perform fast morphological operations such as dilation, erosion, closing, opening, skeletonizing. When combined, these operations offer different interesting outcomes: (i) multiple disjoint-segmented shapes can be linked together to create a joint skeleton, (ii) the topological structure of segmentation can be extracted as a straight skeleton. Then, it can be used as features for structural and spatial tissue analysis.
For the entire collection see [Zbl 1420.68008].
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI
[1] Aggarwal, A., Guibas, L.J., Saxe, J., Shor, P.W.: A linear-time algorithm for computing the Voronoï diagram of a convex polygon. Discrete Comput. Geom. 4(6), 591-604 (1989) · Zbl 0696.68045
[2] Aichholzer, O., Alberts, D., Aurenhammer, F., Gartner, B.: Straight skeletons of simple polygons. In: Proceedings of 4th International Symposium of LIESMARS, pp. 114-124 (1995)
[3] Aichholzer, O., Aurenhammer, F.: Straight skeleton for general polygonal figures in the plane. In: Samoilenko, A.M. (ed.) Voronoï’s Impact on Modern Science, vol. 2, pp. 7-21. Institute of Mathematics of the National Academy of Sciences of Ukraine (1998) · Zbl 0955.52001
[4] Attali, D., Lachaud, J.O.: Delaunay conforming iso-surface, skeleton extraction and noise removal. Comput. Geom. 19(2), 175-189 (2001) · Zbl 0985.68082
[5] Attali, D., Montanvert, A.: Modeling noise for a better simplification of skeletons. In: Proceedings of 3rd IEEE ICIP, vol. 3, pp. 13-16, September 1996
[6] Biedl, T., Held, M., Huber, S., Kaaser, D., Palfrader, P.: A simple algorithm for computing positively weighted straight skeletons of monotone polygons. Inf. Process. Lett. 115(2), 243-247 (2015) · Zbl 1302.68277
[7] Biedl, T., Held, M., Huber, S., Kaaser, D., Palfrader, P.: Weighted straight skeletons in the plane. Comput. Geom. 48(2), 120-133 (2015) · Zbl 1307.05092
[8] Blum, H.: A transformation for extracting new descriptors of shape. In: Wathen-Dunn, W. (ed.) Models for the Perception of Speech and Visual Form, pp. 362-380. MIT Press, Cambridge (1967)
[9] Cacciola, F.: 2D straight skeleton and polygon offsetting. In: CGAL User and Reference Manual, 4.10.1 edn. CGAL Editorial Board (2017)
[10] Davies, E., Plummer, A.: Thinning algorithms: a critique and a new methodology. Pattern Recognit. 14(1), 53-63 (1981)
[11] Debled-Rennesson, I., Feschet, F., Rouyer-Degli, J.: Optimal blurred segments decomposition of noisy shapes in linear time. Comput. Graph. 30(1), 30-36 (2006) · Zbl 1118.68724
[12] Eder, G., Held, M.: Computing positively weighted straight skeletons of simple polygons based on a bisector arrangement. Inf. Process. Lett. 132, 28-32 (2018) · Zbl 1427.68334
[13] Eppstein, D., Erickson, J.: Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions. Discrete Comput. Geom. 22(4), 569-582 (1999) · Zbl 0946.68147
[14] Ge, Y., Fitzpatrick, J.M.: On the generation of skeletons from discrete euclidean distance maps. IEEE Trans. Pattern Anal. Mach. Intell. 18, 1055-1066 (1996)
[15] Guo, Z., Hall, R.W.: Parallel thinning with two-subiteration algorithms. Commun. ACM 32(3), 359-373 (1989)
[16] Hesselink, W.H., Roerdink, J.B.T.M.: Euclidean skeletons of digital image and volume data in linear time by the integer medial axis transform. IEEE Trans. Pattern Anal. Mach. Intell. 30(12), 2204-2217 (2008)
[17] Huang, C.H., Veillard, A., Roux, L., Lomenie, N., Racoceanu, D.: Time efficient sparse analysis of histopathological whole slide images. Comput. Med. Imaging Graph. 35(7), 579-591 (2011)
[18] Huber, S., Held, M.: A fast straight-skeleton algorithm based on generalized motorcycle graphs. Int. J. Comput. Geom. Appl. 22(5), 471-498 (2012) · Zbl 1267.68167
[19] Kelly, T.: Unwritten procedural modeling with the straight skeleton. Ph.D. thesis, University of Glasgow (2013)
[20] Kimmel, R., Shaked, D., Kiryati, N., Bruckstein, A.M.: Skeletonization via distance maps and level sets. Comput. Vis. Image Underst. 62(3), 382-391 (1995)
[21] Ogniewicz, R., Kübler, O.: Hierarchic Voronoï skeletons. Pattern Recognit. 28(3), 343-359 (1995)
[22] Pudney, C.: Distance-ordered homotopic thinning. Comput. Vis. Image Underst. 72(3), 404-413 (1998)
[23] Remy, E., Thiel, E.: Exact medial axis with euclidean distance. Image Vis. Comput. 23(2), 167-175 (2005)
[24] Serra, J.: Image Analysis and Mathematical Morphology. Academic Press Inc., Orlando (1983)
[25] Siddiqi, K., Bouix, S., Tannenbaum, A., Zucker, S.W.: Hamilton-jacobi skeletons. Int. J. Comput. Vis. 48(3), 215-231 (2002) · Zbl 1012.68757
[26] Talbot, H.: Euclidean skeletons and conditional bisectors. In: 1992 Visual Communications and Image Processing, pp. 862-876 (1992)
[27] Vincent, L.M.: Efficient computation of various types of skeletons. In: Proceedings of SPIE, vol. 1445, pp. 1445-1445-15 (1991)
[28] Vizilter, Y.V., Pyt’ev, Y.P., Chulichkov, A.I., Mestetskiy, L.M.: Morphological image analysis for computer vision applications. In: Favorskaya, M.N., Jain, L.C. (eds.) Computer Vision in Control Systems-1. ISRL, vol. 73, pp. 9-58. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-10653-3_2
[29] Wein, R., Baram, A., Flato, E., Fogel, E., Hemmer, M., Morr, S.: 2D minkowski sums. In: CGAL User and Reference Manual, 4.10.1 edn. CGAL Editorial Board (2017)
[30] Zhang, T.Y., Suen, C.Y.: A fast parallel algorithm for thinning digital patterns. Commun. ACM 27(3), 236-239 (1984)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.