Feasibility study of near-duplicate video retrieval based on clustering techniques
thesisposted on 28.02.2017, 03:05 authored by Wang, Yandan
This thesis studies the feasibility of clustering-based Near-Duplicate Video Retrieval (NDVR), which makes use of clustering techniques to pre-process video dataset into Near Duplicate Video (NDV) groups and conducts NDVR on the representatives of clusters. Content based NDVR has been explored for decades. Traditionally, researchers improve the NDVR performance in terms of accuracy and speed through: i) the video feature representation; ii) matching approach; iii) indexing structure. The proposed clustering-based NDVR approach could increase retrieval speed on one hand and achieves equivalent or even better accuracy compared to non-clustering based NDVR on the other hand. The difference of proposed clustering-based approach from the traditional non-clustering based NDVR is that the unsupervised clustering techniques are considered as the prior dataset process step offline. By such a process, the dataset is well organized into corresponding NDV clusters. It then selects only one video or use cluster centroid (mean vector) to represent the cluster. Instead of comparing the query video to all videos in data collections, it only has to compare to the cluster representatives. All the videos in the cluster will be retrieved when the query video that is compared to the representatives meet the specified threshold. Theoretically, it is impossible to know that the performance of clustering-based NDVR in terms of retrieval accuracy compared to that of non-clustering based approach. Accordingly, this thesis evaluates the performance of clustering-based NDVR compared to that of non-clustering based under the same criteria. The evaluation starts with analyzing the clustering algorithms in literature with illustrations as well as the experimental study on what the impact of incorporating these clustering algorithms to pre-cluster the dataset offline for NDVR. After that, a novel clustering framework based on multiple sequence alignment (MSA) is proposed to process video dataset into NDV clusters, and NDVR is conducted on formed clusters. Compared to the other clustering algorithms in literature, the proposed method caters to the variable length of video sequence representation. Finally, it evaluates the MSA clustering-based NDVR by using ordinal, global, and local features respectively. The empirical results show that incorporating clustering algorithms for enhancing NDVR is promising and feasible.