New Automatic Clustering Method Based on the Dissemination of Binary Trees Applied to Video Segmentation

(*) Corresponding author

Authors' affiliations

DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)


In order to manage the growing amount of video information efficiently, a video scene segmentation method is necessary. Many advanced video applications such as video on demand and digital library indexation also require the scene detection to organize the video content. In this paper we use clustering techniques in the video processing field to discover the video scene segmentation. Data clustering is a useful technique for the discovery of interesting data distributions and trends in the underlying data. The concentrated effort of the research community in the last few years resulted in many approaches for data clustering that progressed the field quickly in a few years. However, it remains more work to be done on non-parametric clustering techniques on large databases of high dimensionality. Through this feature, we have developed a novel method of non-parametric clustering based on the dissemination of binary trees structures on spatial representation of data. To assess the performance of this method, we compared with conventional clustering methods. We also showed its applications and advantages on video scene segmentation.
Copyright © 2013 Praise Worthy Prize - All rights reserved.


Clustering Algorithms; Trees of Dissemination; Density Based Clustering; Criteria of Validation; Dissimilarity Matrix; K-Means; Video Scene Segmentation

Full Text:



H. Zhang, A. Kankanhalli, S.W. Smoliar, Automatic partitioning of full-motion video. Multimedia Syst. 1, 1 (1993), 10–28.

R. Zabih, J. Miller, K.A. Mai, feature-based algorithm for detecting and classifying production effects. Multimedia Syst. 7, 2 (1999), 119–128.

Min Li. Research and Implementation of the Key Technology of Network Video Retrieval and Content Extraction. International Review on Computers and Software Vol. 7 N. 6 (Part A) (2012) pp. 2911-2914

A. Chergui, W.Sabbar, A. Bekkhoucha, Segmentation de la vidéo par regroupement non supervisé à l’aide de distance basée sur les points d’intérêts. Sixiéme conférence sur les systémes intelligents : Théories et Applications SITA’10. (2010).

A. Chergui, W. Sabbar, A. Bekkhoucha. Video scene segmentation using the shot transition detection by local characterization of the points of interest. In The Sixth International Conference : Sciences of Electronics, Technologies of Information And Telecommunications (SETIT). Sousse Tunisia (2012), pp. 404–411.

W. Sabbar, A. Chergui, A. Bekkhoucha. Détection automatique des plans de vidéo. In Première Journée de l’Informatique Décisionnelle (JID’10) El Jadida (2010).

W. Sabbar, A. Chergui, A. Bekkhoucha. Extraction automatique de résumé de vidéo basée sur les plans. In 5éme Conference Internationale en Recherche Operationnelle CIRO’10. Marrakech (2010).

S. Hadi, R. Beg, S. Rizvi An Intelligent Tree Based Clustering Method for Large Multi Dimensional Data. International Review on Computers and Software Vol. 4. n. 6 (2009) pp. 648-651

C. T. Zahn. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Trans. Comput. 20, 1 (Jan. 1971), pp 68–86.

B. Everitt, S. Landau, M. Leese. Cluster analysis, 4th edition. London: Arnold, 2001.

P. Hansen, B. Jaumard,. Cluster analysis and mathematical programming.Math. Program. 79 (1997), 191–215.

A. Jain, M. Murty, P. Flynn. Data clustering : a review. ACM computing surveys (CSUR) 31, 3 (1999), pp 264–323.

E. Barbu, P. Héroux, E.Trupin. Classification non supérvisée hiérarchique incrémentale basée sur le calcul de dissimilarités. In 12-èmes Rencontres de la Société Francophone de Classification Montréal : UQÃM (2005), pp 300–304.

P. Sneath, R. Sokal. Numerical Taxonomy. The Principles and Practice of Numerical Classification. Freeman, 1973.

D. Wunsch, R. Xu. Clustering. The Book Depository, 2008.

P.S. Bradley, U.M. Fayyad, C. Reina. Scaling clustering algorithms to large databases. In KDD, R. Agrawal, P. E. Stolorz, and G. Piatetsky-Shapiro, Eds., AAAI Press, (1998), pp. 9–15.

J. Han, R. CLARANS: A method for clustering objects for spatial data mining. Knowledge and Data Engineering, IEEE Transactions , (2002), pp 1003 – 1016..

J. Sander, M. Ester, H.P. Kriegel. X. Xu. Density-based clustering in spatial databases : The algorithm gdbscan and its applications. Data Min. Knowl. Discov. 2, 2 (1998), pp 169–194.

E. Forgy, Cluster analysis of multivariate data : efficiency versus interpretability of classifications. Biometrics 21 (1965), 768–780.

G. Karypis, E.H. Han, V. Kumar. Chameleon: Hierarchical clustering using dynamic modeling. IEEE Computer 32, 8 (1999), 68–75.

A. K. Jain, R. C. Dubes. Algorithms for Clustering Data. Prentice-Hall, 1988.

L. Hubert, P. Arabie. Comparing partitions. Journal of classification 2, 1 (1985), pp 193–218.

W. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association 66, 336 (1971), pp 846–850.

P. Jaccard. Étude comparative de la distribution florale dans une portion des alpes et des jura. Bulletin de la Société Vaudoise des Sciences Naturelles 37 (1901), pp 547–579.

E. B. Fowlkes, C. L Mallows. A method for comparing two hierarchical clustering. Journal of the American Statistical Association 78, 383 (1983), pp 553–569.

L. A. Goodman, W. H. Kruskal. Measures of Association for Cross Classifications. Springer Verlag, New York, 1979.

C. Harris, M. Stephens. A combined corner and edge detector. Fourth Alvey Vision Conference 1 (1988), pp 147–151.

D. Lowe, Object recognition from local scale-invariant features. In International Conference on Computer Vision (1999), pp. 1150–1157.

H. Bay, T. Tuytelaars, L. J. V. Gool. Surf : Speeded up robust features. In Computer Vision - ECCV 2006, 9th European Conference on Computer Vision, Graz, Austria, May 7-13, 2006, Proceedings, Part I (2006), A. Leonardis, H. Bischof, andA. Pinz, Eds., vol. 3951 of Lecture Notes in Computer Science, Springer, pp. 404–417.

E. Rosten, T. Drummond. Machine learning for high-speed corner detection. European Conference on Computer Vision 1 (2006), pp 430–443.


  • There are currently no refbacks.

Please send any question about this web site to
Copyright © 2005-2023 Praise Worthy Prize