{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T08:45:32Z","timestamp":1775551532278,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T00:00:00Z","timestamp":1620086400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T00:00:00Z","timestamp":1620086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014725","name":"Center for Statistics and Applications in Forensic Evidence","doi-asserted-by":"crossref","award":["#70NANB15H176"],"award-info":[{"award-number":["#70NANB15H176"]}],"id":[{"id":"10.13039\/100014725","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Pattern Anal Applic"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recognition of overlapping objects is required in many applications in the field of computer vision. Examples include cell segmentation, bubble detection and bloodstain pattern analysis. This paper presents a method to identify overlapping objects by approximating them with ellipses. The method is intended to be applied to complex-shaped regions which are believed to be composed of one or more overlapping objects. The method has two primary steps. First, a pool of candidate ellipses are generated by applying the Euclidean distance transform on a compressed image and the pool is filtered by an overlaying method. Second, the concave points on the contour of the region of interest are extracted by polygon approximation to divide the contour into segments. Then, the optimal ellipses are selected from among the candidates by choosing a minimal subset that best fits the identified segments. We propose the use of the adjusted Rand index, commonly applied in clustering, to compare the fitting result with ground truth. Through a set of computational and optimization efficiencies, we are able to apply our approach in complex images comprised of a number of overlapped regions. Experimental results on a synthetic data set, two types of cell images and bloodstain patterns show superior accuracy and flexibility of our method in ellipse recognition, relative to other methods.<\/jats:p>","DOI":"10.1007\/s10044-020-00951-z","type":"journal-article","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T04:09:00Z","timestamp":1620101340000},"page":"1193-1206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["Recognition of overlapping elliptical objects in a binary image"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1302-8363","authenticated-orcid":false,"given":"Tong","family":"Zou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianyu","family":"Pan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Taylor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hal","family":"Stern","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"951_CR1","doi-asserted-by":"crossref","unstructured":"Panagiotakis C, Argyros AA (2018) Cell segmentation via region-based ellipse fitting. In: 2018 25th IEEE International conference on image processing (ICIP). IEEE, pp 2426\u20132430","DOI":"10.1109\/ICIP.2018.8451852"},{"key":"951_CR2","doi-asserted-by":"crossref","unstructured":"Guo X, Yu H, Rossetti B, Teodoro G, Brat D, Kong J (2018) Clumped nuclei segmentation with adjacent point match and local shape-based intensity analysis in fluorescence microscopy images. In: 2018 40th Annual international conference of the IEEE Engineering in Medicine and Biology Society (EMBC). IEEE, pp 3410\u20133413","DOI":"10.1109\/EMBC.2018.8512961"},{"issue":"11","key":"951_CR3","doi-asserted-by":"publisher","first-page":"2434","DOI":"10.1016\/j.patcog.2009.04.003","volume":"42","author":"X Bai","year":"2009","unstructured":"Bai X, Sun C, Zhou F (2009) Splitting touching cells based on concave points and ellipse fitting. Pattern Recognit 42(11):2434\u20132446","journal-title":"Pattern Recognit"},{"key":"951_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.patcog.2016.03.030","volume":"58","author":"A Gharipour","year":"2016","unstructured":"Gharipour A, Liew AWC (2016) Segmentation of cell nuclei in fluorescence microscopy images: an integrated framework using level set segmentation and touching-cell splitting. Pattern Recognit 58:1\u201311","journal-title":"Pattern Recognit"},{"issue":"12","key":"951_CR5","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1016\/j.patrec.2012.03.027","volume":"33","author":"WH Zhang","year":"2012","unstructured":"Zhang WH, Jiang X, Liu YM (2012) A method for recognizing overlapping elliptical bubbles in bubble image. Pattern Recognit Lett 33(12):1543\u20131548","journal-title":"Pattern Recognit Lett"},{"key":"951_CR6","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.patrec.2017.11.024","volume":"101","author":"M De Langlard","year":"2018","unstructured":"De Langlard M, Al-Saddik H, Charton S, Debayle J, Lamadie F (2018) An efficiency improved recognition algorithm for highly overlapping ellipses: application to dense bubbly flows. Pattern Recognit Lett 101:88\u201395","journal-title":"Pattern Recognit Lett"},{"issue":"1","key":"951_CR7","doi-asserted-by":"publisher","first-page":"213","DOI":"10.4149\/cai_2018_1_213","volume":"37","author":"T W\u00f3jtowicz","year":"2018","unstructured":"W\u00f3jtowicz T, Bu\u0142ka D (2018) Ellipse detection in forensic blood stain images analysis. Comput Inform 37(1):213\u2013228","journal-title":"Comput Inform"},{"issue":"1","key":"951_CR8","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1109\/TSMC.1979.4310076","volume":"9","author":"N Otsu","year":"1979","unstructured":"Otsu N (1979) A threshold selection method from gray-level histograms. IEEE Trans Syst Man Cybern 9(1):62\u201366","journal-title":"IEEE Trans Syst Man Cybern"},{"issue":"12","key":"951_CR9","doi-asserted-by":"publisher","first-page":"5942","DOI":"10.1109\/TIP.2015.2492828","volume":"24","author":"S Zafari","year":"2015","unstructured":"Zafari S, Eerola T, Sampo J, K\u00e4lvi\u00e4inen H, Haario H (2015) Segmentation of overlapping elliptical objects in silhouette images. IEEE Trans Image Process 24(12):5942\u20135952","journal-title":"IEEE Trans Image Process"},{"key":"951_CR10","unstructured":"Talbot H, Appleton B (2002) Elliptical distance transforms and the object splitting problem. In: Proceedings of ISMM2002, pp 229\u2013240"},{"key":"951_CR11","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1109\/TC.1978.1675191","volume":"8","author":"S Tsuji","year":"1978","unstructured":"Tsuji S, Matsumoto F (1978) Detection of ellipses by a modified Hough transformation. IEEE Trans Comput 8:777\u2013781","journal-title":"IEEE Trans Comput"},{"issue":"1","key":"951_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0262-8856(89)90017-6","volume":"7","author":"H Yuen","year":"1989","unstructured":"Yuen H, Illingworth J, Kittler J (1989) Detecting partially occluded ellipses using the Hough transform. Image Vis Comput 7(1):31\u201337","journal-title":"Image Vis Comput"},{"key":"951_CR13","doi-asserted-by":"crossref","unstructured":"McLaughlin RA (1996) Randomized Hough transform: better ellipse detection. In: Proceedings of digital processing applications (TENCON\u201996), vol\u00a01. IEEE, pp 409\u2013414","DOI":"10.1109\/TENCON.1996.608850"},{"issue":"7","key":"951_CR14","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1109\/34.777377","volume":"21","author":"N Bennett","year":"1999","unstructured":"Bennett N, Burridge R, Saito N (1999) A method to detect and characterize ellipses using the Hough transform. IEEE Trans Pattern Anal Mach Intell 21(7):652\u2013657","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"9","key":"951_CR15","doi-asserted-by":"publisher","first-page":"3204","DOI":"10.1016\/j.patcog.2012.02.014","volume":"45","author":"DK Prasad","year":"2012","unstructured":"Prasad DK, Leung MK, Cho SY (2012) Edge curvature and convexity based ellipse detection method. Pattern Recognit 45(9):3204\u20133221","journal-title":"Pattern Recognit"},{"issue":"3","key":"951_CR16","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1016\/j.patcog.2014.08.027","volume":"48","author":"P Mukhopadhyay","year":"2015","unstructured":"Mukhopadhyay P, Chaudhuri BB (2015) A survey of Hough transform. Pattern Recognit 48(3):993\u20131010","journal-title":"Pattern Recognit"},{"key":"951_CR17","doi-asserted-by":"crossref","unstructured":"Zafari S, Eerola T, Sampo J, K\u00e4lvi\u00e4inen H, Haario H (2017) Comparison of concave point detection methods for overlapping convex objects segmentation. In: Scandinavian conference on image analysis. Springer, Berlin, pp 245\u2013256","DOI":"10.1007\/978-3-319-59129-2_21"},{"key":"951_CR18","doi-asserted-by":"crossref","unstructured":"Zafari S, Eerola T, Sampo J, K\u00e4lvi\u00e4inen H, Haario H (2015) Segmentation of partially overlapping nanoparticles using concave points. In: International symposium on visual computing. Springer, Berlin, pp 187\u2013197","DOI":"10.1007\/978-3-319-27857-5_17"},{"issue":"3","key":"951_CR19","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1016\/j.patcog.2012.09.008","volume":"46","author":"M Farhan","year":"2013","unstructured":"Farhan M, Yli-Harja O, Niemist\u00f6 A (2013) A novel method for splitting clumps of convex objects incorporating image intensity and using rectangular window-based concavity point-pair search. Pattern Recognit 46(3):741\u2013751","journal-title":"Pattern Recognit"},{"key":"951_CR20","doi-asserted-by":"crossref","unstructured":"Zafari S, Eerola T, Sampo J, K\u00e4lvi\u00e4inen H, Haario H (2016) Segmentation of partially overlapping convex objects using branch and bound algorithm. In: Asian conference on computer vision. Springer, Berlin, pp 76\u201390","DOI":"10.1007\/978-3-319-54526-4_6"},{"issue":"5","key":"951_CR21","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1109\/34.765658","volume":"21","author":"A Fitzgibbon","year":"1999","unstructured":"Fitzgibbon A, Pilu M, Fisher RB (1999) Direct least square fitting of ellipses. IEEE Trans Pattern Anal Mach Intell 21(5):476\u2013480","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"951_CR22","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.patcog.2015.11.004","volume":"53","author":"C Panagiotakis","year":"2016","unstructured":"Panagiotakis C, Argyros A (2016) Parameter-free modelling of 2D shapes with ellipses. Pattern Recognit 53:259\u2013275","journal-title":"Pattern Recognit"},{"key":"951_CR23","unstructured":"Chen Q, Yang X, Petriu EM (2004) Watershed segmentation for binary images with different distance transforms. In: Proceedings of the 3rd IEEE international workshop on haptic, audio and visual environments and their applications, pp 111\u2013116"},{"issue":"3","key":"951_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TPAMI.2012.163","volume":"35","author":"C Park","year":"2012","unstructured":"Park C, Huang JZ, Ji JX, Ding Y (2012) Segmentation, inference and classification of partially overlapping nanoparticles. IEEE Trans Pattern Anal Mach Intell 35(3):1\u20131","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"3","key":"951_CR25","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1109\/TBME.2008.2008635","volume":"56","author":"J Cheng","year":"2008","unstructured":"Cheng J, Rajapakse JC et al (2008) Segmentation of clustered nuclei with shape markers and marking function. IEEE Trans Biomed Eng 56(3):741\u2013748","journal-title":"IEEE Trans Biomed Eng"},{"issue":"10","key":"951_CR26","doi-asserted-by":"publisher","first-page":"2600","DOI":"10.1109\/TBME.2010.2060336","volume":"57","author":"C Jung","year":"2010","unstructured":"Jung C, Kim C (2010) Segmenting clustered nuclei using H-minima transform-based marker extraction and contour parameterization. IEEE Trans Biomed Eng 57(10):2600\u20132604","journal-title":"IEEE Trans Biomed Eng"},{"key":"951_CR27","unstructured":"Kapaldo J, Han X, Mery D (2018) Seed-point detection of clumped convex objects by short-range attractive long-range repulsive particle clustering. arXiv preprint arXiv:180404071"},{"issue":"1","key":"951_CR28","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1322432.1322434","volume":"40","author":"R Fabbri","year":"2008","unstructured":"Fabbri R, Costa LDF, Torelli JC, Bruno OM (2008) 2D Euclidean distance transform algorithms: a comparative survey. ACM Comput Surv (CSUR) 40(1):2","journal-title":"ACM Comput Surv (CSUR)"},{"issue":"3","key":"951_CR29","first-page":"3888","volume":"3","author":"PR Reddy","year":"2012","unstructured":"Reddy PR, Amarnadh V, Bhaskar M (2012) Evaluation of stopping criterion in contour tracing algorithms. Int J Comput Sci Inf Technol 3(3):3888\u20133894","journal-title":"Int J Comput Sci Inf Technol"},{"issue":"1","key":"951_CR30","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.patcog.2009.06.010","volume":"43","author":"A Carmona-Poyato","year":"2010","unstructured":"Carmona-Poyato A, Madrid-Cuevas FJ, Medina-Carnicer R, Mu\u00f1oz-Salinas R (2010) Polygonal approximation of digital planar curves through break point suppression. Pattern Recognit 43(1):14\u201325","journal-title":"Pattern Recognit"},{"key":"951_CR31","volume-title":"Introduction to operations research","author":"FS Hillier","year":"1980","unstructured":"Hillier FS, Lieberman GJ (1980) Introduction to operations research. Holden-Day, Inc., San Francisco"},{"issue":"6","key":"951_CR32","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1016\/1049-9652(92)90072-6","volume":"54","author":"JC Mullikin","year":"1992","unstructured":"Mullikin JC (1992) The vector distance transform in two and three dimensions. CVGIP Graph Models Image Process 54(6):526\u2013535","journal-title":"CVGIP Graph Models Image Process"},{"key":"951_CR33","volume-title":"MATLAB version 9.7.0.1247435 (R2019b)","author":"The Math Works, Inc.","year":"2019","unstructured":"The Math Works, Inc. (2019) MATLAB version 9.7.0.1247435 (R2019b). The Math Works, Inc., 2019"},{"issue":"1","key":"951_CR34","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","volume":"2","author":"L Hubert","year":"1985","unstructured":"Hubert L, Arabie P (1985) Comparing partitions. J Classif 2(1):193\u2013218","journal-title":"J Classif"},{"issue":"336","key":"951_CR35","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1080\/01621459.1971.10482356","volume":"66","author":"WM Rand","year":"1971","unstructured":"Rand WM (1971) Objective criteria for the evaluation of clustering methods. J Am Stat Assoc 66(336):846\u2013850","journal-title":"J Am Stat Assoc"},{"issue":"Oct","key":"951_CR36","first-page":"2837","volume":"11","author":"NX Vinh","year":"2010","unstructured":"Vinh NX, Epps J, Bailey J (2010) Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance. J Mach Learn Res 11(Oct):2837\u20132854","journal-title":"J Mach Learn Res"},{"key":"951_CR37","doi-asserted-by":"crossref","unstructured":"Coelho LP, Shariff A, Murphy RF (2009) Nuclear segmentation in microscope cell images: a hand-segmented dataset and comparison of algorithms. In: 2009 IEEE International symposium on biomedical imaging: from nano to macro. IEEE, pp 518\u2013521","DOI":"10.1109\/ISBI.2009.5193098"},{"issue":"7","key":"951_CR38","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1016\/j.media.2012.05.012","volume":"16","author":"JP Bergeest","year":"2012","unstructured":"Bergeest JP, Rohr K (2012) Efficient globally optimal segmentation of cells in fluorescence microscopy images using level sets and convex energy functionals. Med Image Anal 16(7):1436\u20131444","journal-title":"Med Image Anal"},{"key":"951_CR39","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.forsciint.2017.05.022","volume":"277","author":"RM Arthur","year":"2017","unstructured":"Arthur RM, Humburg PJ, Hoogenboom J, Baiker M, Taylor MC, de Bruin KG (2017) An image-processing methodology for extracting bloodstain pattern features. Forensic Sci Int 277:122\u2013132","journal-title":"Forensic Sci Int"},{"key":"951_CR40","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.forsciint.2018.05.019","volume":"289","author":"R Arthur","year":"2018","unstructured":"Arthur R, Hoogenboom J, Baiker M, Taylor M, de Bruin K (2018) An automated approach to the classification of impact spatter and cast-off bloodstain patterns. Forensic Sci Int 289:310\u2013319","journal-title":"Forensic Sci Int"},{"key":"951_CR41","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/j.dib.2018.02.070","volume":"18","author":"D Attinger","year":"2018","unstructured":"Attinger D, Liu Y, Bybee T, De Brabanter K (2018) A data set of bloodstain patterns for teaching and research in bloodstain pattern analysis: impact beating spatters. Data Brief 18:648\u2013654","journal-title":"Data Brief"}],"container-title":["Pattern Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10044-020-00951-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10044-020-00951-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10044-020-00951-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,31]],"date-time":"2021-07-31T15:15:24Z","timestamp":1627744524000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10044-020-00951-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,4]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["951"],"URL":"https:\/\/doi.org\/10.1007\/s10044-020-00951-z","relation":{},"ISSN":["1433-7541","1433-755X"],"issn-type":[{"value":"1433-7541","type":"print"},{"value":"1433-755X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,4]]},"assertion":[{"value":"7 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that there is no conflict of interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}