# 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

Rudolf Scitovski; Kristian Sabo

Applications of Mathematics (2019)

- Volume: 64, Issue: 6, page 663-678
- ISSN: 0862-7940

## Access Full Article

top## Abstract

top## How to cite

topScitovski, Rudolf, and Sabo, Kristian. "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." Applications of Mathematics 64.6 (2019): 663-678. <http://eudml.org/doc/294628>.

@article{Scitovski2019,

abstract = {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.},

author = {Scitovski, Rudolf, Sabo, Kristian},

journal = {Applications of Mathematics},

keywords = {multiple ellipses detection problem; globally optimal $k$-partition; Lipschitz continuous function; DIRECT; $k$-means},

language = {eng},

number = {6},

pages = {663-678},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

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},

url = {http://eudml.org/doc/294628},

volume = {64},

year = {2019},

}

TY - JOUR

AU - Scitovski, Rudolf

AU - Sabo, Kristian

TI - 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

JO - Applications of Mathematics

PY - 2019

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 64

IS - 6

SP - 663

EP - 678

AB - 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.

LA - eng

KW - multiple ellipses detection problem; globally optimal $k$-partition; Lipschitz continuous function; DIRECT; $k$-means

UR - http://eudml.org/doc/294628

ER -

## References

top- Ahn, S. J., Rauh, W., Warnecke, H.-J., 10.1016/S0031-3203(00)00152-7, Pattern Recognition 34 (2001), 2283-2303. (2001) Zbl0991.68127DOI10.1016/S0031-3203(00)00152-7
- Akinlar, C., Topal, C., 10.1016/j.patcog.2012.09.020, Pattern Recognition 46 (2013), 725-740. (2013) DOI10.1016/j.patcog.2012.09.020
- Bagirov, A. M., Ugon, J., Webb, D., 10.1016/j.patcog.2010.10.018, Pattern Recognition 44 (2011), 866-876. (2011) Zbl1213.68514DOI10.1016/j.patcog.2010.10.018
- Finkel, D. E., Kelley, C. T., 10.1007/s10898-006-9029-9, J. Glob. Optim. 36 (2006), 597-608. (2006) Zbl1142.90488MR2269299DOI10.1007/s10898-006-9029-9
- Gander, W., Golub, G. H., Strebel, R., 10.1007/BF01934268, BIT 34 (1994), 558-578. (1994) Zbl0817.65008MR1430909DOI10.1007/BF01934268
- Grbić, R., Grahovac, D., Scitovski, R., 10.1016/j.patcog.2016.06.031, Pattern Recognition 60 (2016), 824-834. (2016) DOI10.1016/j.patcog.2016.06.031
- Grbić, R., Nyarko, E. K., Scitovski, R., 10.1007/s10898-012-0020-3, J. Glob. Optim. 57 (2013), 1193-1212. (2013) Zbl1279.65076MR3121789DOI10.1007/s10898-012-0020-3
- Jones, D. R., Perttunen, C. D., Stuckman, B. E., 10.1007/BF00941892, J. Optim. Theory Appl. 79 (1993), 157-181. (1993) Zbl0796.49032MR1246501DOI10.1007/BF00941892
- Kogan, J., Introduction to Clustering Large and High-Dimensional Data, Cambridge University Press, Cambridge (2007). (2007) Zbl1183.62106MR2297007
- Marošević, T., Scitovski, R., 10.17535/crorr.2015.0004, Croat. Oper. Res. Rev. (CRORR) 6 (2015), 43-53. (2015) Zbl1359.62256MR3349995DOI10.17535/crorr.2015.0004
- Morales-Esteban, A., Martínez-Álvarez, F., Scitovski, S., Scitovski, R., 10.1016/j.cageo.2014.09.003, Computers & Geosciences 73 (2014), 132-141. (2014) DOI10.1016/j.cageo.2014.09.003
- Moshtaghi, M., Havens, T. C., Bezdek, J. C., Park, L., Leckie, C., Rajasegarar, S., Keller, J. M., Palaniswami, M., 10.1016/j.patcog.2010.07.024, Pattern Recognition 44 (2011), 55-69. (2011) Zbl1207.68301DOI10.1016/j.patcog.2010.07.024
- Paulavičius, R., Žilinskas, J., 10.1007/978-1-4614-9093-7, SpringerBriefs in Optimization, Springer, New York (2014). (2014) Zbl1401.90017MR3136389DOI10.1007/978-1-4614-9093-7
- Prasad, D. K., Leung, M. K. H., Quek, C., 10.1016/j.patcog.2012.11.007, Pattern Recognition 46 (2013), 1449-1465. (2013) Zbl1264.68205DOI10.1016/j.patcog.2012.11.007
- Sabo, K., Scitovski, R., 10.1007/s10492-014-0063-5, Appl. Math., Praha 59 (2014), 391-406. (2014) Zbl1340.68112MR3233551DOI10.1007/s10492-014-0063-5
- Sabo, K., Scitovski, R., Vazler, I., 10.1007/s11590-011-0389-9, Optim. Lett. 7 (2013), 5-22. (2013) Zbl1283.90034MR3017090DOI10.1007/s11590-011-0389-9
- Scitovski, R., 10.1007/s10898-017-0510-4, J. Glob. Optim. 68 (2017), 713-727. (2017) Zbl1377.65067MR3671698DOI10.1007/s10898-017-0510-4
- Scitovski, R., Marošević, T., 10.1016/j.patrec.2014.09.010, Pattern Recognit. Lett. 52 (2014), 9-16. (2014) DOI10.1016/j.patrec.2014.09.010
- Scitovski, R., Sabo, K., 10.1007/s10898-019-00743-8, J. Glob. Optim. 74 (2019), 63-77. (2019) Zbl07069294MR3943615DOI10.1007/s10898-019-00743-8
- Scitovski, R., Scitovski, S., 10.1016/j.cageo.2013.06.010, Comput. Geosci. 59 (2013), 124-131. (2013) DOI10.1016/j.cageo.2013.06.010
- Späth, H., Cluster-Formation und -Analyse. Theorie, FORTRAN-Programme und Beispiele, R. Oldenbourg Verlag, München (1983). (1983) Zbl0536.62048
- Theodoridis, S., Koutroumbas, K., 10.1016/B978-0-12-369531-4.X5000-8, Academic Press, Amsterdam (2009). (2009) Zbl1093.68103DOI10.1016/B978-0-12-369531-4.X5000-8

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.