A combination of RANSAC and DBSCAN methods for solving the multiple geometrical object detection problem

  • PDF / 1,979,792 Bytes
  • 18 Pages / 439.37 x 666.142 pts Page_size
  • 81 Downloads / 222 Views

DOWNLOAD

REPORT


A combination of RANSAC and DBSCAN methods for solving the multiple geometrical object detection problem Rudolf Scitovski1

· Snježana Majstorovi´c1

· Kristian Sabo1

Received: 1 August 2019 / Accepted: 5 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract In this paper we consider the multiple geometrical object detection problem. On the basis of the set 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 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. Keywords RANSAC · DBSCAN · Multiple line detection problem · Multiple circle detection problem · Multiple ellipse detection problem · The most appropriate partition · Modified k-means

1 Introduction We observe the problem of recognizing multiple geometrical objects in the plane not known in advance, which we will later refer to as the MGD problem. In the literature, the following MGD problems are well-known: the multiple line detection problem [5,13,27,39], the multiple circle

B

Rudolf Scitovski [email protected] Snježana Majstorovi´c [email protected] Kristian Sabo [email protected]

1

Department of Mathematics, University of Osijek, Trg Ljudevita Gaja 6, 31 000 Osijek, Croatia

123

Journal of Global Optimization

detection problem [1,13,26,28], the multiple ellipse detection problem [1,7,14,16,23,30], the multiple generalized circle detection problem [29], the multiple segment detection problem [3,36], etc. MGD problems appear in numerous applications. Let us mention some: computer vision and image processing [5,13], medicine, robotics, object detection, and other industrial applications [5,23], crop row detection in agriculture, [38,39] etc. When we talk about solving the MGD problem, we need to differentiate between the geometrical object detection problem based on data without noise and the geometrical object detection problem based on noisy data. The first case often uses methods based on the Hough Transform (see [1,13,17]), and a center-based clusteri