| Title:
|
The adaptation of the $k$-means algorithm to solving the multiple ellipses detection problem by using an initial approximation obtained by the DIRECT global optimization algorithm (English) |
| Author:
|
Scitovski, Rudolf |
| Author:
|
Sabo, Kristian |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
64 |
| Issue:
|
6 |
| Year:
|
2019 |
| Pages:
|
663-678 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
multiple ellipses detection problem |
| Keyword:
|
globally optimal $k$-partition |
| Keyword:
|
Lipschitz continuous function |
| Keyword:
|
DIRECT |
| Keyword:
|
$k$-means |
| MSC:
|
05E05 |
| MSC:
|
65K05 |
| MSC:
|
90C26 |
| MSC:
|
90C27 |
| MSC:
|
90C56 |
| MSC:
|
90C57 |
| idZBL:
|
07144732 |
| idMR:
|
MR4042432 |
| DOI:
|
10.21136/AM.2019.0262-18 |
| . |
| Date available:
|
2019-12-09T11:48:17Z |
| Last updated:
|
2022-01-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147927 |
| . |
| Reference:
|
[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. Zbl 0991.68127, 10.1016/S0031-3203(00)00152-7 |
| Reference:
|
[2] Akinlar, C., Topal, C.: EDCircles: A real-time circle detector with a false detection control.Pattern Recognition 46 (2013), 725-740. 10.1016/j.patcog.2012.09.020 |
| Reference:
|
[3] Bagirov, A. M., Ugon, J., Webb, D.: Fast modified global $k$-means algorithm for incremental cluster construction.Pattern Recognition 44 (2011), 866-876. Zbl 1213.68514, 10.1016/j.patcog.2010.10.018 |
| Reference:
|
[4] Finkel, D. E., Kelley, C. T.: Additive scaling and the DIRECT algorithm.J. Glob. Optim. 36 (2006), 597-608. Zbl 1142.90488, MR 2269299, 10.1007/s10898-006-9029-9 |
| Reference:
|
[5] Gander, W., Golub, G. H., Strebel, R.: Least-squares fitting of circles and ellipses.BIT 34 (1994), 558-578. Zbl 0817.65008, MR 1430909, 10.1007/BF01934268 |
| Reference:
|
[6] Grbić, R., Grahovac, D., Scitovski, R.: A method for solving the multiple ellipses detection problem.Pattern Recognition 60 (2016), 824-834. 10.1016/j.patcog.2016.06.031 |
| Reference:
|
[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. Zbl 1279.65076, MR 3121789, 10.1007/s10898-012-0020-3 |
| Reference:
|
[8] Jones, D. R., Perttunen, C. D., Stuckman, B. E.: Lipschitzian optimization without the Lipschitz constant.J. Optim. Theory Appl. 79 (1993), 157-181. Zbl 0796.49032, MR 1246501, 10.1007/BF00941892 |
| Reference:
|
[9] Kogan, J.: Introduction to Clustering Large and High-Dimensional Data.Cambridge University Press, Cambridge (2007). Zbl 1183.62106, MR 2297007 |
| Reference:
|
[10] Marošević, T., Scitovski, R.: Multiple ellipse fitting by center-based clustering.Croat. Oper. Res. Rev. (CRORR) 6 (2015), 43-53. Zbl 1359.62256, MR 3349995, 10.17535/crorr.2015.0004 |
| Reference:
|
[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. 10.1016/j.cageo.2014.09.003 |
| Reference:
|
[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. Zbl 1207.68301, 10.1016/j.patcog.2010.07.024 |
| Reference:
|
[13] Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization.SpringerBriefs in Optimization, Springer, New York (2014). Zbl 1401.90017, MR 3136389, 10.1007/978-1-4614-9093-7 |
| Reference:
|
[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. Zbl 1264.68205, 10.1016/j.patcog.2012.11.007 |
| Reference:
|
[15] Sabo, K., Scitovski, R.: Interpretation and optimization of the $k$-means algorithm.Appl. Math., Praha 59 (2014), 391-406. Zbl 1340.68112, MR 3233551, 10.1007/s10492-014-0063-5 |
| Reference:
|
[16] Sabo, K., Scitovski, R., Vazler, I.: One-dimensional center-based $l_1$-clustering method.Optim. Lett. 7 (2013), 5-22. Zbl 1283.90034, MR 3017090, 10.1007/s11590-011-0389-9 |
| Reference:
|
[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. Zbl 1377.65067, MR 3671698, 10.1007/s10898-017-0510-4 |
| Reference:
|
[18] Scitovski, R., Marošević, T.: Multiple circle detection based on center-based clustering.Pattern Recognit. Lett. 52 (2014), 9-16. 10.1016/j.patrec.2014.09.010 |
| Reference:
|
[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. Zbl 07069294, MR 3943615, 10.1007/s10898-019-00743-8 |
| Reference:
|
[20] Scitovski, R., Scitovski, S.: A fast partitioning algorithm and its application to earthquake investigation.Comput. Geosci. 59 (2013), 124-131. 10.1016/j.cageo.2013.06.010 |
| Reference:
|
[21] Späth, H.: Cluster-Formation und -Analyse. Theorie, FORTRAN-Programme und Beispiele.R. Oldenbourg Verlag, München (1983). Zbl 0536.62048 |
| Reference:
|
[22] Theodoridis, S., Koutroumbas, K.: Pattern Recognition.Academic Press, Amsterdam (2009). Zbl 1093.68103, 10.1016/B978-0-12-369531-4.X5000-8 |
| . |
