SPECIAL ISSUE: New Trends in Artificial Vision and Artificial Intelligence; Edited by M. De Gregorio and M. FrucciNo Access

A GRAPH-BASED ALGORITHM FOR CLUSTER DETECTION

PASQUALE FOGGIA

Dipartimento di Informatica e Sistemistica, Università di Napoli Federico II, Via Claudio, 21, Napoli, NA I-80125, Italy

Search for more papers by this author

GENNARO PERCANNELLA

Dipartimento di Ingegneria dell'Informazione ed Ingegneria Elettrica, Università di Salerno, Fisciano, SA I-84084, Italy

Search for more papers by this author

CARLO SANSONE

Dipartimento di Informatica e Sistemistica, Università di Napoli Federico II, Via Claudio, 21, Napoli, NA I-80125, Italy

Search for more papers by this author

, and

MARIO VENTO

Dipartimento di Ingegneria dell'Informazione ed Ingegneria Elettrica, Università di Salerno, Fisciano, SA I-84084, Italy

Search for more papers by this author

https://doi.org/10.1142/S0218001408006557Cited by:13 (Source: Crossref)

Abstract

In some Computer Vision applications there is the need for grouping, in one or more clusters, only a part of the whole dataset. This happens, for example, when samples of interest for the application at hand are present together with several noisy samples.

In this paper we present a graph-based algorithm for cluster detection that is particularly suited for detecting clusters of any size and shape, without the need of specifying either the actual number of clusters or the other parameters.

The algorithm has been tested on data coming from two different computer vision applications. A comparison with other four state-of-the-art graph-based algorithms was also provided, demonstrating the effectiveness of the proposed approach.

Keywords:

References

K.-H. Anders and M. Sester, Parameter-free cluster detection in spatial databases and its application to typification, Proc. IAPRS CongressXXXIII (2000) pp. 75–82. Google Scholar
J. C. Bezdek , Pattern Recognition with Fuzzy Objective Function Algorithms ( Plenum Press , NY , 1981 ) . Crossref, Google Scholar
U. Brandes, M. Gaertler and D. Wagner, Experiments on graph clustering algorithms, Proc. 11th Euro. Symp. Algorithms (ESA '03)2832, Lecture Notes in Computer Science (Springer-Verlag, 2003) pp. 568–579. Google Scholar
H. D. Chenget al., Patt. Recogn. 36, 2967 (2003), DOI: 10.1016/S0031-3203(03)00192-4. Crossref, Web of Science, Google Scholar
M. De Santoet al., Patt. Anal. Appl. 7(4), 447 (2005). Crossref, Web of Science, Google Scholar
P. Foggia, G. Percannella, C. Sansone and M. Vento, A graph-based clustering method and its applications, in eds. F. Mele, G. Ramella, S. Santillo and F. Ventriglia, Lecture Notes in Computer Science, Vol. 4729 (Springer-Verlag, Berlin, 2007), pp. 277–287 . Google Scholar
M. Gaertler, Clustering with spectral methods, Master's thesis, Universitat Konstanz (2002) . Google Scholar
E. Horowitz and S. Sahni , Fundamentals of Computer Algorithms ( Computer Science Press , 1978 ) . Google Scholar
A. K. Jain and R. C. Dubes , Algorithms for Clustering Data ( Prentice-Hall, Inc. , Upper Saddle River, NJ, USA , 1988 ) . Google Scholar
A. K. Jain, M. N. Murty and P. J. Flynn, ACM Comput. Surv. 31(3), 264 (1999), DOI: 10.1145/331499.331504. Crossref, Web of Science, Google Scholar
P. Juszczak, Learning to recognise. A study on one-class classification and active learning, Ph.D. thesis, Delft University of Technology, ISBN: 978-90-9020684-4 (2006) . Google Scholar
R. Kannan, S. Vampala and A. Vetta, Foundations of Computer Science 367 (2000). Google Scholar
T. Kohonen , Self-Organizing Maps ( Springer-Verlag , Heidelberg, Germany , 1995 ) . Crossref, Google Scholar
P. Sajda, C. Spence and J. Pearson, IEEE Trans. Med. Imag. 21(3), 239 (2002), DOI: 10.1109/42.996342. Crossref, Web of Science, Google Scholar
J. Shi and J. Malik, IEEE Trans. Patt. Anal. Mach. Intell. 22(8), 888 (2000). Crossref, Web of Science, Google Scholar
S. M. van Dongen, Graph clustering by flow simulation, Ph.D. thesis, University of Utrecht (2000) . Google Scholar
Z. Wu and R. Leahy, IEEE Trans. PAMI 15(11), 1101 (1993). Crossref, Google Scholar
C. Zahn, IEEE Trans. Comput. C 20, 68 (1971). Web of Science, Google Scholar

Vol. 22, No. 05

Metrics

Downloaded 88 times

History

Keywords

PDF download

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

A GRAPH-BASED ALGORITHM FOR CLUSTER DETECTION

Abstract

Recommended