Abstract
In this paper we consider the multiple geometrical object detection problem. On the basis of the set \(\mathcal {A}\) containing data points coming from and scattered among a number of geometrical objects not known in advance, we should reconstruct or detect those geometrical objects. A new efficient method for solving this problem based on the popular RANSAC method using parameters from the DBSCAN method is proposed. Thereby, instead of using classical indexes for recognizing the most appropriate partition, we use parameters from the DBSCAN method which define the necessary conditions proven to be far more efficient. Especially, the method is applied to solving multiple circle detection problem. In this case, we give both the conditions for the existence of the best circle as a representative of the data set and the explicit formulas for the parameters of the best circle. In the illustrative example, we consider the multiple circle detection problem for the data point set \(\mathcal {A}\) coming from 5 intersected circles not known in advance. The method is tested on numerous artificial data sets and it has shown high efficiency. The comparison of the proposed method with other well-known methods of circle detection in real-world images also indicates a significant advantage of our method.
Similar content being viewed by others
Notes
All evaluations were done on the basis of our own Mathematica-modules freely available at: https://www.mathos.unios.hr/images/homepages/scitowsk/DBRAN.rar, and were performed on the computer with a 2.90 GHz Intel(R) Core(TM)i7-75000 CPU with 16GB of RAM.
References
Akinlar, C., Topal, C.: EDCircles: a real-time circle detector with a false detection control. Pattern Recogn. 46, 725–740 (2013)
Bagirov, A.M., Ugon, J., Mirzayeva, H.: Nonsmooth nonconvex optimization approach to clusterwise linear regression problems. Eur. J. Oper. Res. 229, 132–142 (2013)
Brüntjen, K., Späth, H.: Incomplete total least squares. Numer. Math. 81, 521–538 (1999)
Ester, M., Kriegel, H., Sander, J.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, pp. 226–231 (1996)
Fernández, C., Moreno, V., Curto, B., Vicente, J.A.: Clustering and line detection in laser range measurements. Robot. Auton. Syst. 58, 720–726 (2010)
Fischler, M., Bolles, R.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 381–395 (1981)
Grbić, R., Grahovac, D., Scitovski, R.: A method for solving the multiple ellipses detection problem. Pattern Recogn. 60, 824–834 (2016)
Grbić, R., Nyarko, E.K., Scitovski, R.: A modification of the DIRECT method for Lipschitz global optimization for a symmetric function. J. Global Optim. 57, 1193–1212 (2013)
Horst, R., Tuy, H.: Global Optimization: Deterministic Approach. Springer (1996), 3rd, revised and enlarged edition
Jones, D.R.: The DIRECT global optimization algorithm. In: Floudas, C.A., Pardalos, P.M. (eds.) The Encyclopedia of Optimization, pp. 431–440. Kluwer Academic Publishers, Dordrect (2001)
Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79, 157–181 (1993)
Kvasov, D.E., Sergeyev, Y.D.: Multidimensional global optimization algorithm based on adaptive diagonal curves. Comput. Math. Math. Phys. 43, 40–56 (2003)
Manzanera, A., Nguyen, T.P., Xu, X.: Line and circle detection using dense one-to-one Hough transforms on greyscale images. EURASIP J. Image Video Process. (2016). https://doi.org/10.1186/s13640-016-0149-y
Marošević, T., Scitovski, R.: Multiple ellipse fitting by center-based clustering. Croat. Oper. Res. Rev. 6, 43–53 (2015)
Morales-Esteban, A., Martínez-Álvarez, F., Scitovski, S., Scitovski, R.: A fast partitioning algorithm using adaptive Mahalanobis clustering with application to seismic zoning. Comput. Geosci. 73, 132–141 (2014)
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 Recogn. 44, 55–69 (2011)
Mukhopadhyay, P., Chaudhuri, B.B.: A survey of Hough transform. Pattern Recogn. 48, 993–1010 (2015)
Nievergelt, Y.: A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres. Numer. Math. 91, 257–303 (2002)
Paulavičius, R., Sergeyev, Y.D., Kvasov, D.E., Žilinskas, J.: Globally-biased BIRECT algorithm with local accelerators for expensive global optimization. Expert Syst. Appl. 144, 113052 (2020). https://doi.org/10.1016/j.eswa.2019.113052
Paulavičius, R., Sergeyev, Y.D., Kvasov, D.E., Žilinskas, J.: Globally-biased DISIMPL algorithm for expensive global optimization. J. Global Optim. 59, 545–567 (2014)
Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, New York (2014)
Paulavičius, R., Žilinskas, J.: Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints. Optim. Lett. 10, 237–246 (2016)
Prasad, D.K., Leung, M.K.H., Quek, C.: ElliFit: an unconstrained, non-iterative, least squares based geometric Ellipse Fitting method. Pattern Recogn. 46, 1449–1465 (2013)
Radojičić, U., Scitovski, R., Sabo, K.: A fast and efficient method for solving the multiple closed curve detection problem. In: Marsico, M.D., di Baja, G.S., Fred, A. (eds.) Proceedings of the 8th International Conference on Pattern Recognition Applications and Methods—Volume 1: ICPRAM, Prague, Czech Republic, pp. 269–276. ISBN: 978-989-758-351-3 (2019)
Rousseeuw, P.J., Hubert, M.: Robust statistics for outlier detection. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 1, 73–79 (2011)
Scitovski, R., Marošević, T.: Multiple circle detection based on center-based clustering. Pattern Recogn. Lett. 52, 9–16 (2014)
Scitovski, R., Radojičić, U., Sabo, K.: A fast and efficient method for solving the multiple line detection problem. Rad HAZU Matematičke znanosti 23, 123–140 (2019)
Scitovski, R., Sabo, K.: Application of the DIRECT algorithm to searching for an optimal \(k\)-partition of the set A and its application to the multiple circle detection problem. J. Global Optim. 74(1), 63–77 (2019)
Scitovski, R., Sabo, K.: A combination of k-means and DBSCAN algorithm for solving the multiple generalized circle detection problem. Adv. Data Anal. Classif. (2020a). https://doi.org/10.1007/s11634-020-00385-9
Scitovski, R., Sabo, K.: DBSCAN-like clustering method for various data densities. Pattern Anal. Appl. 23, 541–554 (2020b). https://doi.org/10.1007/s10044-019-00809-z
Scitovski, R., Scitovski, S.: A fast partitioning algorithm and its application to earthquake investigation. Comput. Geosci. 59, 124–131 (2013)
Sergeyev, Y.D., Kvasov, D.E.: A deterministic global optimization using smooth diagonal auxiliary functions. Commun. Nonlinear Sci. Numer. Simul. 21, 99–111 (2015)
Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer Briefs in Optimization. Springer, Heidelberg (2013)
Späth, H.: Algorithm 48: a fast algorithm for clusterwise linear regression. Computing 29, 17–181 (1981)
Späth, H.: Cluster-Formation und Analyse. R. Oldenburg Verlag, München (1983)
Thomas, J.C.R.: A new clustering algorithm based on k-means using a line segment as prototype. In: Martin, C.S., Kim, S.-W. (eds.) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, pp. 638–645. Springer, Berlin (2011)
Vendramin, L., Campello, R.J.G.B., Hruschka, E.R.: On the comparison of relative clustering validity criteria. In: Proceedings of the SIAM International Conference on Data Mining, SDM 2009, April 30–May 2, 2009, Sparks, Nevada, USA, SIAM, pp. 733–744 (2009)
Vidović, I., Cupec, R., Hocenski, E.: Crop row detection by global energy minimization. Pattern Recogn. 55, 68–86 (2016)
Vidović, I., Scitovski, R.: Center-based clustering for line detection and application to crop rows detection. Comput. Electron. Agric. 109, 212–220 (2014)
Viswanath, P., Babu, V.S.: Rough-DBSCAN: a fast hybrid density based clustering method for large data sets. Pattern Recogn. Lett. 30, 1477–1488 (2009)
Wilcox, R.: Introduction to Robust Estimation and Hypothesis Testing, 3rd edn. Academic Press, Boston (2012)
Wolfram Research, Inc.: Mathematica, Wolfram Research, Inc., Champaign (2020), version 11.0 edition
Acknowledgements
The author would like to thank the referees and the journal editors for their careful reading of the paper and insightful comments that helped us improve the paper. Especially, the authors would like to thank Mrs. Katarina Moržan for significantly improving English of this paper. This work was supported by the Croatian Science Foundation through research Grants IP-2016-06-6545 and IP-2016-06-8350.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Scitovski, R., Majstorović, S. & Sabo, K. A combination of RANSAC and DBSCAN methods for solving the multiple geometrical object detection problem. J Glob Optim 79, 669–686 (2021). https://doi.org/10.1007/s10898-020-00950-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-020-00950-8