Library Subscription: Guest
Begell Digital Portal Begell Digital Library eBooks Journals References & Proceedings Research Collections
Journal of Automation and Information Sciences
SJR: 0.232 SNIP: 0.464 CiteScore™: 0.27

ISSN Print: 1064-2315
ISSN Online: 2163-9337

Volume 51, 2019 Volume 50, 2018 Volume 49, 2017 Volume 48, 2016 Volume 47, 2015 Volume 46, 2014 Volume 45, 2013 Volume 44, 2012 Volume 43, 2011 Volume 42, 2010 Volume 41, 2009 Volume 40, 2008 Volume 39, 2007 Volume 38, 2006 Volume 37, 2005 Volume 36, 2004 Volume 35, 2003 Volume 34, 2002 Volume 33, 2001 Volume 32, 2000 Volume 31, 1999 Volume 30, 1998 Volume 29, 1997 Volume 28, 1996

Journal of Automation and Information Sciences

DOI: 10.1615/JAutomatInfScien.v51.i3.30
pages 26-35

Hybrid Approach to Clustering Various Lengths Video

Sergey V. Mashtalir
Kharkov National University of Radio and Electronics, Kharkov
Mikhail І. Stolbovoi
Kharkov National University of Radio and Electronics, Kharkov
Sergey V. Yakovlev
N.E. Zhukovskiy National Aerospace University "Kharkov Aviation Institute", Kharkov


A significant increase in the amount of data to be analyzed and processed requires the introduction of new efficient tools and methods for their collection and storage. This task is especially important when analyzing multimedia in particular video data due to their great redundancy. One of the ways to reduce the amount of information processed is clustering/segmentation of video sequences to isolate parts that are homogeneous in content. This raises the problem of choosing the required number of clusters as an information source. The article is devoted to the development of a hybrid clustering method for analyzing video sequences of various lengths. The method saves the advantages and eliminates the disadvantages of agglomerative hierarchical and fuzzy clusterings. To determine the similarity between segments of video sequences, the Levenshtein metric is used, which allows one to calculate the distances between multidimensional sequences of different lengths. The criterion for the clustering process completion as a whole, and, accordingly, the result quality is determined by the Dunn index. The proposed hybrid approach to clustering video sequences is computationally simple to implement and allows solving the multidimensional time series analysis problems of arbitrary nature in the case when it is difficult to determine in advance the necessary number of clusters for splitting and under conditions of uncertainty about their possible overlap, i.e. in the case where the clustering result is the cover construction, and not data partitioning (exact cover construction).


  1. Basharat A., Zhai Y., Shah M., Content based video matching using spatiotemporal volumes, Computer Vision and Image Understanding, 2008, 110, 360-377, DOI: 10.1016/j.cviu.2007.09.016.

  2. Patel B.V., Meshram B.B., Content based video retrieval, The International Journal of Multimedia & Its Applications (IJMA), 2012, 4, No. 5, 77-98, DOI: 10.5121/iju.2012.3202.

  3. Mashtalir S., Mikhnova O., Detecting significant changes in image sequences, Multimedia Forensics and Security, Springer, Cham, 2017, 161-191, DOI: 10.512l/iju.2012.3202.

  4. Petersohn C., Temporal video segmentation, Jorg Vogt Verlag, 2010.

  5. Dhiman P., Dhanda M., Video segmentation using FCM algorithm, International Journal of Engineering Trends and Technology (IJETT), 2016, 36, No. 2, 106-110, DOI: 10.14445/22315381/IJETT-V36P220.

  6. Kobylin O., Mashtalir S., Stolbovyi M., Video clustering via multidimensional time-series analysis, Proceedings of the 9th International Conference on Information Management and Engineering, 2017, Spain, Barcelona, 60-63, DOI: 10.1145/3149572.3149599.

  7. Kaufman L., Rousseeuw P. J., Finding groups in data: An introduction to cluster analysis, Wiley, 2009.

  8. Everitt B., Landau S., Leese M., Cluster analysis, Wiley, 2011.

  9. Dunn J.C., A Fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters, Journal of Cybernetics and Systems Analysis, 1973, 3, No. 3, 32-57, DOI: 10.1080/01969727308546046.

  10. Hulianytskyi L., Malyshko S., Big data in information analytical system "NEWSCAPE", Proc. IEEE First Int. Conf. on Data Stream Mining & Processing (23-27 August 2016, Lviv, Ukraine), 2016, 382-386, DOI: 10.15407/usim.2017.05.086.

  11. Hulianytskyi L., Riasna I., Formalization and classification of combinatorial optimization problems, Springer Optimization Methods and Applications, 2017, 130, 239-250, DOI: 10.1007/978-3-319- 68640-0_11.

  12. Hulianytskyi L., Riasna I., Automatic classification method based on a fuzzy similarity relation, Cybernetics and Systems Analysis, 2016, 52, No. 1, 30-37, DOI: 10.1007/s10559-016-9796-3.

  13. Abonyi J., Feil B., Cluster analysis for data mining and system identification, Birkhauser, Basel, 2007.

  14. Liao T.W., Clustering of time series data, Pattern Recognition, 2005, 38, No. 11, 1857-1874, DOI: 10.1016/j.patcog.2005.01.025.

  15. Aggarwal C.C., Reddy C.K., Data clustering: algorithms and applications, CRC Press, Boca Raton, 2014.

  16. Bogucharsky S.I., Kagramanyan A.G., Mashtalir S.V., Hierarchical agglomerative clustering of images in large databases, Systemy obrobky informatsii, 2014, No. 8, 93-97.

  17. Berndt D.J., Clifford S., Using dynamic time warping to find patterns in time series, Proc. of the 3rd International Conference on Knowledge Discovery and Data Mining (AAAIWS '94), 1994, 359-370.

  18. Keogh E.J., Pazzani M.J., Scaling up dynamic time warping to massive datasets, European Conference on Principles of Data Mining and Knowledge Discovery, 1999, 1-11, DOI: 10.1007/978- 3-540-48247-5_1.

  19. Chu S., Keogh E., Hart D., Pazzani M., Iterative deepening dynamic time warping for time series, Proc. 2nd SIAM International Conference on Data Mining (SDM-02), 2002, DOI: 10.1137/ 1.9781611972726.12.

  20. Keogh E.J., Pazzani M.I., Scaling up dynamic time warping for data mining applications, Proc. of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000, 285-289, DOI:

  21. Keogh E.J., Pazzani M.J., Derivative dynamic time warping, Proc. of the First SIAM International Conference on Data Mining (SDM'2001), 2001.

  22. Mashtalir S.V., Stolbovyi M.I., Yakovlev S.V., Video sequences clustering by the k-harmonic means, Cybernetics and Systems Analysis, 2019, 55, No 1, 295-307, DOI: 10.1007/s10559-019-00124-9.

  23. Mashtalir S., Mashtalir V., Stolbovyi M., Video shot boundary detection via sequential clustering, International Journal of Information Theories and Applications, 2017, 24, No. 1, 50-59, DOI: 10.5815/ijisa.2017.11.02.

  24. Hu Z., Mashtalir S.V., Tyshchenko O.K., Stolbovyi M.I., Clustering matrix sequences based on the iterative dynamic time deformation procedure, International Journal of Intelligent Systems and Applications, 2018, 10, No. 7, 66-73, DOI: 10.5815/ijisa.2018.07.07.

  25. Hu Z., Mashtalir S.V., Tyshchenko O.K., Stolbovyi M.I., Video shots' matching via various length of multidimensional time sequences, International Journal of Intelligent Systems and Applications, 2018, 9, No. 11, 10-16, DOI: 10.5815/ijisa.2017.11.02.

  26. Levenshtein V., Binary codes capable of correcting deletions, insertions and reversals, Dokl. Akad. Nauk SSSR, 1965, 163, No. 4, 845-848.

  27. Mashtalir V.P., Yakovlev S.V., Point-set methods of clusterization of standard information, Cybernetics and Systems Analysis, 2001, 37, No. 3, 295-307, DOI: 10.1023/A:1011985908177.

  28. Gerasin S.N., Shlyakhov V.V., Yakovlev S.V., Set coverings and tolerance relation, Cybernetics and Systems Analysis, 2008, 43, No. 3, 333-340, DOI: 10.1007/s10559-008-9007-y.

  29. Mashtalir V.P., Shlyakhov V.V., Yakovlev S.V., Group structures on quotient sets in classification problems, Cybernetics and Systems Analysis, 2014, 50, No. 4, 507-518, DOI: 10.1007/ s10559-014- 9639-z.