Article
MSC:
05E05,
65K05,
90C26,
90C27,
90C56,
90C57 | MR 4042432 | Zbl 07144732 | DOI: 10.21136/AM.2019.0262-18
Full entry |
PDF
(1.1 MB)
Feedback
PDF
(1.1 MB)
Feedback
Keywords:
multiple ellipses detection problem; globally optimal $k$-partition; Lipschitz continuous function; DIRECT; $k$-means
multiple ellipses detection problem; globally optimal $k$-partition; Lipschitz continuous function; DIRECT; $k$-means
Summary:
We consider the multiple ellipses detection problem on the basis of a data points set coming from a number of ellipses in the plane not known in advance, whereby an ellipse $E$ is viewed as a Mahalanobis circle with center $S$, radius $r$, and some positive definite matrix $\Sigma $. A very efficient method for solving this problem is proposed. The method uses a modification of the $k$-means algorithm for Mahalanobis-circle centers. The initial approximation consists of the set of circles whose centers are determined by means of a smaller number of iterations of the DIRECT global optimization algorithm. Unlike other methods known from the literature, our method recognizes well not only ellipses with clear edges, but also ellipses with noisy edges. CPU-time necessary for running the corresponding algorithm is very short and this raises hope that, with appropriate software optimization, the algorithm could be run in real time. The method is illustrated and tested on 100 randomly generated data sets.
References:
[1] Ahn, S. J., Rauh, W., Warnecke, H.-J.: Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola. Pattern Recognition 34 (2001), 2283-2303. DOI 10.1016/S0031-3203(00)00152-7 | Zbl 0991.68127
[2] Akinlar, C., Topal, C.: EDCircles: A real-time circle detector with a false detection control. Pattern Recognition 46 (2013), 725-740. DOI 10.1016/j.patcog.2012.09.020
[3] Bagirov, A. M., Ugon, J., Webb, D.: Fast modified global $k$-means algorithm for incremental cluster construction. Pattern Recognition 44 (2011), 866-876. DOI 10.1016/j.patcog.2010.10.018 | Zbl 1213.68514
[4] Finkel, D. E., Kelley, C. T.: Additive scaling and the DIRECT algorithm. J. Glob. Optim. 36 (2006), 597-608. DOI 10.1007/s10898-006-9029-9 | MR 2269299 | Zbl 1142.90488
[5] Gander, W., Golub, G. H., Strebel, R.: Least-squares fitting of circles and ellipses. BIT 34 (1994), 558-578. DOI 10.1007/BF01934268 | MR 1430909 | Zbl 0817.65008
[6] Grbić, R., Grahovac, D., Scitovski, R.: A method for solving the multiple ellipses detection problem. Pattern Recognition 60 (2016), 824-834. DOI 10.1016/j.patcog.2016.06.031
[7] Grbić, R., Nyarko, E. K., Scitovski, R.: A modification of the DIRECT method for Lipschitz global optimization for a symmetric function. J. Glob. Optim. 57 (2013), 1193-1212. DOI 10.1007/s10898-012-0020-3 | MR 3121789 | Zbl 1279.65076
[8] Jones, D. R., Perttunen, C. D., Stuckman, B. E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79 (1993), 157-181. DOI 10.1007/BF00941892 | MR 1246501 | Zbl 0796.49032
[9] Kogan, J.: Introduction to Clustering Large and High-Dimensional Data. Cambridge University Press, Cambridge (2007). MR 2297007 | Zbl 1183.62106
[10] Marošević, T., Scitovski, R.: Multiple ellipse fitting by center-based clustering. Croat. Oper. Res. Rev. (CRORR) 6 (2015), 43-53. DOI 10.17535/crorr.2015.0004 | MR 3349995 | Zbl 1359.62256
[11] Morales-Esteban, A., Martínez-Álvarez, F., Scitovski, S., Scitovski, R.: A fast partitioning algorithm using adaptive Mahalanobis clustering with application to seismic zoning. Computers & Geosciences 73 (2014), 132-141. DOI 10.1016/j.cageo.2014.09.003
[12] Moshtaghi, M., Havens, T. C., Bezdek, J. C., Park, L., Leckie, C., Rajasegarar, S., Keller, J. M., Palaniswami, M.: Clustering ellipses for anomaly detection. Pattern Recognition 44 (2011), 55-69. DOI 10.1016/j.patcog.2010.07.024 | Zbl 1207.68301
[13] Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. SpringerBriefs in Optimization, Springer, New York (2014). DOI 10.1007/978-1-4614-9093-7 | MR 3136389 | Zbl 1401.90017
[14] Prasad, D. K., Leung, M. K. H., Quek, C.: ElliFit: an unconstrained, non-iterative, least squares based geometric ellipse fitting method. Pattern Recognition 46 (2013), 1449-1465. DOI 10.1016/j.patcog.2012.11.007 | Zbl 1264.68205
[15] Sabo, K., Scitovski, R.: Interpretation and optimization of the $k$-means algorithm. Appl. Math., Praha 59 (2014), 391-406. DOI 10.1007/s10492-014-0063-5 | MR 3233551 | Zbl 1340.68112
[16] Sabo, K., Scitovski, R., Vazler, I.: One-dimensional center-based $l_1$-clustering method. Optim. Lett. 7 (2013), 5-22. DOI 10.1007/s11590-011-0389-9 | MR 3017090 | Zbl 1283.90034
[17] Scitovski, R.: A new global optimization method for a symmetric Lipschitz continuous function and the application to searching for a globally optimal partition of a one-dimensional set. J. Glob. Optim. 68 (2017), 713-727. DOI 10.1007/s10898-017-0510-4 | MR 3671698 | Zbl 1377.65067
[18] Scitovski, R., Marošević, T.: Multiple circle detection based on center-based clustering. Pattern Recognit. Lett. 52 (2014), 9-16. DOI 10.1016/j.patrec.2014.09.010
[19] Scitovski, R., Sabo, K.: Application of the DIRECT algorithm to searching for an optimal $k$-partition of the set $\Cal A\subset\Bbb R^n$ and its application to the multiple circle detection problem. J. Glob. Optim. 74 (2019), 63-77. DOI 10.1007/s10898-019-00743-8 | MR 3943615 | Zbl 07069294
[20] Scitovski, R., Scitovski, S.: A fast partitioning algorithm and its application to earthquake investigation. Comput. Geosci. 59 (2013), 124-131. DOI 10.1016/j.cageo.2013.06.010
[21] Späth, H.: Cluster-Formation und -Analyse. Theorie, FORTRAN-Programme und Beispiele. R. Oldenbourg Verlag, München (1983). Zbl 0536.62048
[22] Theodoridis, S., Koutroumbas, K.: Pattern Recognition. Academic Press, Amsterdam (2009). DOI 10.1016/B978-0-12-369531-4.X5000-8 | Zbl 1093.68103
Search
Partner of
