# Interested Keyframe Extraction of Commodity Video Based on Adaptive Clustering Annotation
## 3 Keyframe Extraction by Adaptive Clustering Annotation Facing
### Personalized Keyframe Adaptive Clustering Based on Frame-to-Frame Difference
#### 3.2.2 Adaptive Clustering of Differential Frames  
In order to improve annotation efficiency, we propose an Adaptive Cluster Based on Distance (ACBD) to cluster the set of differential frames and select the class center for user annotation. The ACBD algorithm uses Euclidean distance to measure the similarity between images and divides the categories through dynamic threshold to achieve accurate clustering of images. Assume that the set to be clustered is a differential frame set, as \(\Psi_{d}=\{X_{1},X_{2},\ldots,X_{L}\}\). The ACBD algorithm is completed in four steps: (1) Obtain the initial classes--that is, calculate the similarity of the images and group \(L\) images into \(L-1\) classes. (2) Remove noise. (3) Combine related categories and delete abnormal images by intraclass difference. (4) According to the number of samples of every class, dynamically adjust the cluster threshold to optimize the clustering results. The details are shown as follows. (1) Obtain the initial classes. We transform the image \(X_{i}\) to row vector, as \(x_{i}=[x_{i,1},x_{i,2},\ldots,x_{i,(w\times h)}]\), and the Euclidean distance between any two frames is shown in Formula (4). \[dis(X_{m},X_{l})=\sqrt{\sum_{i=1}^{w\times h}(x_{m,i}-X_{l,i})^{2}}, \tag{4}\]  
\[m\in\{1,2,\ldots,L\},l\in\{1,2,\ldots,L\}\]  
Thus, we can obtain the image distance matrix of \(\Psi_{d}\) represented by \(Dis(\Psi_{d})\). \[Dis(\Psi_{d})= \begin{bmatrix}0&dis(X_{1},X_{2})&\cdots&dis(X_{1},X_{L})\\ dis(X_{2},X_{1})&0&\cdots&dis(X_{2},X_{L})\\ \vdots&\vdots&\ddots&\vdots\\ dis(X_{L},X_{1})&dis(X_{L},X_{2})&\cdots&0\end{bmatrix} \]  
Afterwards, we calculate the mean of \(Dis(\Psi_{d})\) by Formula (5). \[E=\frac{\sum_{j=i+1}^{L}\sum_{l=1}^{L}dis(X_{i},X_{j})}{C_{L}^{2}} \tag{5}\]  
\[dis(X_{p},X_{q})<K \tag{6}\]  
For each image, we gather its similar images into a group. According to Formula (6) in which \(K\) equals \(E\) for the first time, we group \(\Psi_{d}\) into \(L-1\) classes denoted as \(A=\{A_{1},A_{2},\ldots,A_{L-1}\}\). For example, the clustering result of image \(i\) is represented as \(A_{i}=\{A_{i,1},A_{i,2},\ldots,A_{i,p}\},i=1,2,\ldots,L-1\). \(A_{i,p}\) represents that the image \(p\) is similar to the image \(i\). (2) Remove noise. Firstly, we calculate the number of elements in \(A_{i}\) denoted as \(a_{i}\) and set the threshold \(\beta\) to divide noise. If \(a_{i}<\beta\), it means that images in \(A_{i}\) are quite different from most other images and the number of elements in it is not enough to be considered a separate cluster, so we determine \(A_{i}\) as a noise and delete it. Besides, for \(A_{i,q},q=1,2,\ldots,p\) we seek similar elements in \(A_{i}\) and count them denoted as \(Count_{q}\) to delete \(A_{i,q}\) if \(Count_{q}\) is less than \(\beta\). (3) Merge categories based on associated images: We assume that sets with the same elements describe the same class, and therefore merge the intersecting sets. For example, a sample belongs to \(A_{i}\) and \(A_{j}\), so we merge them to a category. And the result is denoted as \(A^{\prime}=\{A^{\prime}_{1},A^{\prime}_{2},A^{\prime}_{3},\ldots,A^{\prime}_{m}\}\). (4) Optimize cluster based on dynamical cluster threshold. In Formula (6), \(K\) is usually unable to accurately cluster different clusters, so we have to update \(K\) to improve accuracy. For this, we count the number of elements in \(A^{\prime}_{t},t=1,2,\ldots,m\) denoted as \(Num_{t}\) and we set a threshold \(\mu\) to change Formula (6) into Formula (7) so as to recalculate \(A\) and redo step (2) and step (3) if \(\frac{Num_{t}}{L}>\theta,t=1,2,\ldots,m\). \(\theta\) is a decimal representing the percentage of each category in the video. \[dis(A_{p},A_{q})<\mu K \tag{7}\]  
Finally, we can obtain the result until \(K\) stops changing or the number of iteration \(\varepsilon\) is reached. After clustering, we calculate \(\eta\) and \(G\) to separate images into containing local features, containing global features, and containing distorted information.