Rad HAZU, Matematičke znanosti, Vol. 23 (2019), 123-140.

A FAST AND EFFICIENT METHOD FOR SOLVING THE MULTIPLE LINE DETECTION PROBLEM

Rudolf Scitovski, Una Radojičić and Kristian Sabo

Abstract.   In this paper, we consider the multiple line detection problem on the basis of a data points set coming from a number of lines not known in advance. A new and efficient method is proposed, which is based upon center-based clustering, and it solves this problem quickly and precisely. The method has been tested on 100 randomly generated data sets. In comparison to the incremental algorithm, the method gives significantly better results. Also, in order to identify a partition with the most appropriate number of clusters, a new index has been proposed for the case of a cluster whose lines are cluster-centers. The index can also be generalized for other geometrical objects.

2010 Mathematics Subject Classification.   65K05, 90C26, 90C27, 90C56, 90C57, 05E05.

Key words and phrases.   Location, multiple line detection problem, center-based clustering, number of clusters, globally optimal partition.

DOI: https://doi.org/10.21857/yvjrdcqq8y

References:

1. A. M. Bagirov, J. Ugon and H. Mirzayeva, Nonsmooth nonconvex optimization approach to clusterwise linear regression problems, European J. Oper. Res. 229 (2013), 132-142.
   MathSciNet     CrossRef

2. A. M. Bagirov, J. Ugon and D. Webb, Fast modified global k-means algorithm for incremental cluster construction, Pattern Recognition 44 (2011), 866-876.
   CrossRef

3. M. Barni and R. Gualtieri, A new possibilistic clustering algorithm for line detection in real world imagery, Pattern Recognition 32 (1999), 1897-1909.
   CrossRef

4. R. Duda, P. Hart and D. Stork, Pattern Classification, Wiley, 2001.
   MathSciNet

5. L. A. Fernandes and M. M. Oliveira, Real-time line detection through an improved Hough transform voting scheme, Pattern Recognition 41 (2008), 299-314.
   CrossRef

6. C. Fernández, V. Moreno, B. Curto and J. A. Vicente, Clustering and line detection in laser range measurements, Robotics and Autonomous Systems 58 (2010), 720-726.
   CrossRef

7. R. Grbić, E. K. Nyarko and R. Scitovski, A modification of the DIRECT method for Lipschitz global optimization for a symmetric function, J. Global Optim. 57 (2013), 1193-1212.
   MathSciNet     CrossRef

8. D. R. Jones, C. D. Perttunen and B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl. 79 (1993), 157-181.
   MathSciNet     CrossRef

9. J. Kogan, Introduction to Clustering Large and High-dimensional Data, Cambridge University Press, New York, 2007.
   MathSciNet

10. V. Leemans and M.-F. Destain, Line cluster detection using a variant of the Hough transform for culture row localisation, Image and Vision Computing 24 (2006), 541-550.
    CrossRef

11. A. Manzanera, T. P. Nguyen and X. Xu, Line and circle detection using dense one-toone Hough transforms on greyscale images, EURASIP Journal on Image and Video Processing 2016, Article number: 46 (2016).
    CrossRef

12. T. Marošević, The Hausdorff distance between some sets of points, Math. Commun. 23 (2018), 247-257.
    MathSciNet

13. P. Mukhopadhyay and B. B. Chaudhuri, A survey of Hough transform, Pattern Recognition 48 (2015), 993-1010.
    CrossRef

14. Y. Nievergelt, Total least squares: state-of-the-art regression in numerical analysis, SIAM Rev. 36 (1994), 258-264.
    MathSciNet     CrossRef

15. K. Sabo and R. Scitovski, An approach to cluster separability in a partition, Inform. Sci. 305 (2015), 208-218.
    MathSciNet     CrossRef

16. K. Sabo, R. Scitovski and I. Vazler, One-dimensional center-based l₁-clustering method, Optim. Lett. 7 (2013), 5-22.
    MathSciNet     CrossRef

17. R. Scitovski, A new global optimization method for a symmetric Lipschitz continuous function and application to searching for a globally optimal partition of a onedimensional set, J. Global Optim. 68 (2017), 713-727.
    MathSciNet     CrossRef

18. R. Scitovski and S. Scitovski, A fast partitioning algorithm and its application to earthquake investigation, Computers & Geosciences 59 (2013), 124-131.
    CrossRef

19. H. Späth, Algorithm 48: a fast algorithm for clusterwise linear regression, Computing 29 (1982), 175-181.
    CrossRef

20. H. Späth, Cluster-Formation und Analyse, R. Oldenbourg Verlag, München, 1983.

21. J. C. R. Thomas, A new clustering algorithm based on k-means using a line segment as prototype, in: CIARP, 2011, Lecture Notes in Comput. Sci. 7042, pp. 638-645.
    CrossRef

22. H.-H. Trinh, D.-N. Kim and K.-H. Jo, Facet-based multiple building analysis for robot intelligence, Appl. Math. Comput. 205 (2008), 537-549.
    CrossRef

23. L. Vendramin, R. J. G. B. Campello and E. R. Hruschka, 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, 2009, pp. 733-744.

24. I. Vidović, D. Bajer and R. Scitovski, A new fusion algorithm for fuzzy clustering, Croat. Oper. Res. Rev. CRORR 5 (2014), 149-159.
    MathSciNet     CrossRef

25. I. Vidović and R. Scitovski, Center-based clustering for line detection and application to crop rows detection, Computers and Electronics in Agriculture 109 (2014), 212-220.
    CrossRef