The parameter-Newton iteration for the second-order cone linear complementarity problem

1.   Introduction

Video summarization, the task of concussing the original video to a summary, can fully catch the eye-catching video information. Since the 1990s, video summarization technology has gained considerable domestic and international attention. It has made significant contribution in quickly understanding the video information, which is an efficient tool for fast browsing and retrieval of videos ^[1].

Key-frame extraction is an indispensable assistant for static video summarization technology that characterizes the principal video contents with representative frames extraction in order to provide a convenient method to quickly and comprehensively grasp video information. The prevailing assumption is that the goal is to extract video summary accurately and automatically. Key frame extraction methods can be divided into three categories: shot based, content based and cluster based ^[2]. Currently, some shot based techniques are developed in the area of computer vision and image processing ^[3]. Huang C. extracts representative frames from each shot by computing the frame image difference in saliency and edge map features ^[4]. Mehmood I. analyzes the difference between frame images in a shot by modeling an auditory and perceptual attention feature ^[5]. Song G. H. computes the color difference in one shot by employing the average histogram method ^[6]. It is common for shot based methods to segment the original video into several shots at first. However, the shot segmentation process is computationally expensive. Content based methods can avoid this problem. Rachida H. proposes MSKVS, a content-based method, to measure the inter-frame distance by time and visual features. MSKVS guarantees superior performance over other content-based methods ^[7]. Gianluigi C. conducts experiment on six new and sport competition videos by employing his content-based method. Experimental results demonstrate that his method can effectively extract key frames ^[8]. Generally, these content-based methods analyze the video content by extracting color, texture or motion feature. A limiting factor of content-based methods is that the computational cost is incurred in the process of frame image features ^[9]. This limitation encourages the development of cluster-based methods. Cluster based techniques work by clustering together the similar frames and extracting one representative frame of each class. They avoid shot segmentation error of shot based methods, decrease inter-frame difference analysis frequency of content-based methods, and can be well-suited to key frame extraction in related fields ^[10,11,12].

Numerous limitations have been posed to encourage the development of cluster-based key-frame extraction algorithms ^[13]. The prevailing steps are cluster data, aggregate video frames into multiple clusters, and extract representative frame to compose a video summarization ^[14]. The cluster-based key-frame extraction not only avoids shot segmentation error and complexity, but also decreases the inter-frame difference analysis frequency. There are also many other problems of the cluster-based methods, such as extracting single image feature cannot fully represent frame image, manually determining the number of clusters and the initial cluster center caused a low degree of automation, the extracted key frame cannot represent the original videos. Therefore, this paper aims to improve the accuracy and the automation of key-frame extraction. In this paper, a novel cluster based key frame extraction approach is proposed. The benefits of this approach are as follows:

1) A video content analysis method is proposed to improve the representative of video feature data by using three visual features: color, texture and information complexity.

2) We develop a threshold optimization method to avoid manual selection of clustering threshold. This method can improve the automation of cluster-based key frame extraction.

3) We utilize the fusion of the frame density, inter-cluster distance and intra-cluster distance to filter the key frame candidates and employ the max weight factor parameter to further refine key frame candidates. This method is favorable to improve the frame representation and the overall fidelity.

The rest of this paper is organized as follows. Section 2 describes the details of cluster-based methods. In section 3, we present the implementation of feature extraction method. Section 4 provides a detailed description of the proposed cluster based key frame extraction method. In section 5, we explore the performance of the proposed approach. Finally, the major work is discussed and wrapped up in Section 6.

2.   Related work

It is quite common for cluster-based methods to transform the frame image into data points in feature space and cluster these data points to extract key frames. It is similar to the clustering algorithm, which gathers similar elements together, and takes the cluster center as the representative of clusters. Recently, some cluster-based key frame extraction methods have been proposed in literature ^[15,16].

The basic cluster-based methods can be categorized into two: automatic and semi-automatic cluster-based methods ^[17]. In general, semi-automatic cluster-based method requires manual determination the initial cluster centers and the number of clusters. Setting the number of clusters in advance may affect key frames extraction results ^[14]. It is more reasonable to determine the number of clusters according to different video contents in clustering process. Therefore, the automatic key frame extraction technology is more practical. Among the automatic cluster schemes, Kuanar extracts the color and texture features and propose an automated method of video key frame extraction using dynamic Delaunay graph clustering ^[10]. In ^[11], a fused key frame extraction framework is proposed. This method generates video summaries by combining sparse selection and agglomerative hierarchical clustering method based on mutual information. It extracts candidate key frames by an improved MIAHC algorithm caused the fidelity and operation efficiency are improved. In ^[12], the authors propose the coarse clustering and fine clustering key frame extraction. The traditional spectral clustering method with simple histogram features is used to remove most of the redundant frames. Then, the image classification method based on SIFT feature sparse coding is used to perform fine clustering for each time period. In ^[19], Liu and his colleges propose a key frame extraction method combining k-means algorithm and hierarchical clustering algorithm. They obtain initial clusters by employing the improved hierarchical clustering algorithm. Then they use the k-means algorithm to optimize the initial clusters to obtain the optimal clusters. In ^[20], the authors proposed a novel cluster-based algorithm, which is inspired by the idea of high-density peak search clustering algorithm. This method gathers similar frames into classes by integrating the important attributes of the video. In ^[21], the proposed cluster-based method combines image information entropy and uses a density clustering algorithm to extract key frames in gesture videos. In cluster-based key frame extraction, calculation method of clustering threshold has a great impact on the fidelity and compression rate of key frames. The core idea behind such automatic cluster-based methods is to set a favorable threshold. In literature, researchers usually receive the threshold by defining formula or by setting fixed value. Kuanar S. K. computes the cluster threshold by employing formula $2\left( {1{\text{ - }}\varepsilon } \right)$ ^[10]. Jeong D. J. selects 0.0001 as the cluster threshold ^[12]. The other researchers compute cluster threshold by a self-defined formula ^[11,19]. In representative frame extraction, some cluster-based techniques take the cluster centers or centroids as the representative frames of each class. In ^[10], the author selects the frames which are closest to the cluster centroids as the representative frames. In ^[19,20], the authors directly extract cluster centers as the representative frames.

In general, those cluster-based methods may remain redundant because the clustering threshold setting influences optimal key frame extraction. Also, these methods evaluate the representative of the frames in one cluster by a single image feature. However, a single image feature cannot be able to fully characterize the frame content and complexity. In a more reasonable way, optimal threshold and feature fusion should be computed in cluster-based key frame extraction.

3.   Materials and method

In this section, we provide a detailed description of the proposed OTMW method which includes feature extraction and key frame extraction. At first, the color, texture, and information complexity features are computed to express video content. Then, an optimization function is developed to compute the optimal clustering threshold. Next, the frame density, inter-distance and intra-distance are computed and fused as the clustering weight factor. Finally, a Max Weigh method is proposed to extract the cluster representative frame. The proposed approach is summarized in figure 1.

3.1.   Feature extraction

In this section, we describe the proposed video content analysis method which distinguishes frames by computing feature data ^[22]. We extract the color, texture and information complexity features to discriminate different frame images. The video frame feature data is construct by

where C, T and E represent the color, texture and information complexity, respectively.

3.1.1.   Color feature

We take the color feature as one feature to characterize the difference of frame images. We compute the first color moment, second color moment and third color moment in H, S, and V channels to construct the color feature data vectors of frame images. The first color moment reflects the brightness difference, which is calculated by

where the parameters $w$ and $h$ are the pixel width and height, ${f_i}({x_p}, {y_q})$ is the pixel value in position $({x_p}, {y_q})$, and $1 \leqslant p \leqslant w, 1 \leqslant q \leqslant h$. The second color moment reflects the color distribution range, which is compute by

The third color moment represents the color distribution symmetry, which is computed by

where ${C_m}$, ${C_v}$ and ${C_s}$ include first moment mean, second moment variance and third moment slope three parameters, respectively.

3.1.2.   Texture feature

We take the texture feature as another feature to characterize the difference of frame images in image surface structural organization information\cite{r23}. We compute the mean of angular second moment, contrast, correlation and homogeneity texture features in 0, 45, 90 and 135 directions to construct video frame texture feature data vectors. The angular second moment characterizes the thickness and gray distribution uniformity of images, and it can be calculated by

The contrast characterizes the groove depth and clarity of images, it can be calculated by

The correlation characterizes the local gray similarity in row or column direction, it can be calculated by

The homogenization characterizes the local gray level uniformity of images, it can be calculated by

3.1.3.   Information complexity feature

We take the information complexity as the last feature to characterize the difference of frame images in aggregated and spatial feature. Information entropy proposed by Shannon is a holistic perspective information complexity measuring method ^[24]. It can characterize the image aggregated and spatial features. Larger image information entropy and greater internal non-uniformity degree commonly occur together in higher diversity level. The two-dimensional information entropy $E{f_i}$ can be calculated by

where $Cf$ is the occurrence probability of each gray level in $i$-th frame image.

3.2.   Clustering for key frame extraction

In this section, we describe the proposed cluster based key frame extraction method, which develops a new optimization function to compute the optimal threshold.

3.2.1.   Threshold optimization

We narrow the search interval of optimal threshold by computing the function values of trial points. In cluster-based method, the fidelity ^[8] and ratio ^[7] are negatively and positively correlated with the threshold, respectively. Therefore, we infer that the quality of key frames is optimal when fidelity and ratio are infinitely close. We introduce a new parameter FR to characterize this relationship and to obtain the optimal key frames. The distance between frame ${x^{(i)}}$ and frame ${x^{(j)}}$ is compute by

where $(i, j) \in [1, 2, ..., m]$.

The average distance is computed by

The threshold is defined as

where $\varepsilon$ is a variable factor, $st{d_{ij}}$ is the standard deviation of ${d_{ij}}$. We define the new parameter FR as

The threshold optimization function is defined as

Giving a, b(a < b, $a = {d_c}{\text{ - }}3 \times st{d_{ij}}$, $b = {d_c}{\text{ + }}3 \times st{d_{ij}}$) and c. We compute threshold change factor c and compute $f(a)$, $f(b)$ and $f(c)$. We change c by comparing the $f(a)$, $f(b)$ and $f(c)$. When $f(c) < 0$, Fidelity is less than Ratio. Therefore, we change c to increases Fidelity and decrease Ratio. When $f(c) \geqslant 0$, Fidelity is more than Ratio. We change c to decrease Fidelity and increase Ratio. If $f(c){\text{ = }}f(a){\text{ = }}f(b)$ in consecutive three times and $\left( {b - a} \right) \leqslant 0.001$, we compute the optimal cluster threshold by $\partial {\text{ = }}\frac{{a + b}}{2}$. The calculation process is Algorithm1.

3.2.2.   Initial cluster centers and the number of clusters

In this section, we compute the initial cluster centers and the number of clusters by clustering the data of FFV. Frame Feature Vector data sets $FFV = \left\{ {{x^{\left( 1 \right)}}, {x^{\left( 2 \right)}}, \cdots , {x^{\left( m \right)}}} \right\}$ is a 14-dimensional video frame feature data, which includes color, texture and information entropy features.

The density of the sample frame i in video stream is defined as:

The distance of the j-th frame image from the i-th frame image in the same cluster is defined as:

where i and j are in the same cluster.

The distance between the i-th frame element and the element j of another cluster is defined as:

where i is a frame in one cluster, j is the elements of the cluster center that has completed the clustering.

According Eq. (17), $\varphi i$ may contain multiple elements. The product of ${\rho _i}$, ${\eta _i}^{ - 1}$ and ${\varphi _i}$ weight factor is defined as the weighted product:

Initial cluster center and cluster number k are directly related to $\omega \left( x \right)$, the solution is shown in Algorithm 2. Firstly, the density of samples is calculated using Eq. (15), and then the maximum density frame is selected as the first initial clustering center ${\mu ^{\left( 1 \right)}}$. The distance between frames is computed and set as the first initial cluster center. Then the frames are classified with a less than t distance into the first cluster, and these frames are removed from D. The ${\omega _i}$ of D is also calculated using Eq. (18), and the second initial cluster center ${\mu ^{\left( 2 \right)}}$ is obtained by calculating the maximum of $\omega \left( x \right)$. Similarity, the samples that satisfies the same condition are classified as the second, three and k cluster, and are removed from D. Finally, all samples are assigned to cluster, and the initial cluster centers ${\mu }^{\left(1\right)}, {\mu }^{\left(2\right)}, \cdots , {\mu }^{\left(k\right)}$ and the number of k are obtained. Clustering process is shown in Figure 3.

3.2.3.   Key frame extraction

In this section, we classify frame images into k clusters $C = \{ {C_1}, {C_2}, ..., {C_k}\}$ and extract representative frames from this clusters. The error square sum criterion function is used as the criterion function. The frame images are classified into different clusters by employing Algorithm 3. Giving the cluster $C = {C_1}, {C_2}, \cdots , {C_k}$, the specific steps are as follows:

Step1: Calculate frame ${\rho _i}$, ${\eta _i}$ and ${\varphi _i}$ in cluster C₁ by Eq. (13), (14) and (15).

Step2: Compute maximum weight factor by Eq. (17) and select key-frame ${f_1}$ from cluster C₁.

Step3: Similarly, the key-frame ${f_k}$ can be obtained by the computing of maximum weight factor in Eq. (17).

Step4: Repeat Step3 until all cluster representative frames are selected.

Step5: Key-frames $f = {f_1}, {f_2}, \cdots , {f_k}$ are extracted. Video summarization is generated.

4.   Results and discussion

In this section, we turn to an empirical study on the proposed OTMW method in key frame extraction tasks and compare it with state-of-the-art cluster-based key frame extraction methods such as HVM ^[25], ACSC ^[26], RGPH ^[27] and FCME ^[28]. We report improved performance across open video dataset. We conduct a set of experiments by using surveillance, documentary, lecture on TV and phone recording four different video datasets. These videos are publicly shared on https://open-video.org/. In this section, we take Hcil2000_01 video as an example to report the performance of OTMW method. Here Hcil2000_01 is a random video of open video dataset.

4.1.   Optimization of threshold

The parameters of Hcil2000_01 video in threshold optimization is shown in table 1. In Hcil2000_01 video, the average distance ${d_c}$ and standard deviation $st{d_{ij}}$ of ${d_{ij}}$ are 2.3107 and 0.2259, respectively. Therefore, the parameters a = 1.6442, b = 2.9993. The variable interval of parameter c is [1.6442, 2.9993]. The parameter c is computed by c = a + 0.618*(b-a) = 2.481652. In sixth iteration, the f(a) = f(b) = f(c) = 0.0063. The calculation of parameter c is changed to c = a + 0.382*(b-a) in subsequent iterations. As shown in table 1, the value of f(a) = f(b) = f(c) = 0.0063 are not change in the next two iterations. However, b-a = 0.122156 > 0.001. Finally, b-a = 0.000509 < 0.001 in 13th iteration. Therefore, the optimal threshold ${\rm{\tilde n}} = \frac{{a + b}}{2} = 1.644709$.

4.2.   Extraction of key frames

The key frames are extracted by employing OTMW method across open video dataset. The key frames of Hcil2000_01 video is shown in figure 3. The fidelity and ratio results are shown in table 2. Nf represents the number of frames, Nrf represents the number of key frames. The fidelity measures of different videos are changed from 93 to 98 with an average of 96.12. The ratio measures are changed from 95 to 98 with an average of 97.13. The key frames are consistent with artificial judgment.

4.3.   Comparison with several state-of-the-art methods

We compare OTMW with state-of-the-art cluster-based algorithm in term of the fidelity and ratio measure performance. In experimental, the number of clusters of semi-automatic cluster-based methods are same as OTMW method. The results of fidelity and ratio are shown in figure 4 and table 3. HVM method with an average fidelity of 83.75 and an average ratio of 95.59. ACSC with an average fidelity of 85.75 and an average ratio of 94.79. The average fidelity of RGPH and FCME are 85.61 and 85.38. The proposed OTMW method with an average fidelity of 96.24 and with an average ratio of 97.15. OTMW method achieves a 10.63–12.49 fidelity improvement over other cluster-based methods. The fluctuations of ratio measure of different videos are shown in figure 5. OTMW method with a ratio variance of 0.73. The ratio variance of HVM and ACSC cluster-based methods are 22.11 and 11.12. They are 15 and 30 times larger than OTMW, respectively. OTMW method achieves a 1.56–2.24 ratio improvement over other cluster-based methods and has a small fluctuation.

4.3.1.   Extraction of key frames on various datasets

To assess the performance of OTMW method, we consider key frame extraction tasks on surveillance, documentary, lecture on TV and phone recording datasets. The HVM method achieves an average fidelity of 82.42, 86.90, 84.36 and 81.22, respectively. It achieves an average ratio of 95.76, 92.73, 94.767 and 99.05. ACSC method achieves an average fidelity of 88.40, 84.07, 81.02 and 89.57. It achieves an average ratio of 92.19, 97.37, 97.42 and 92.13. The average fidelities of FCME method are 86.39, 83.77, 85.51 and 87.62. The average ratios of RGPH method are 86.39, 83.18, 85.94 and 86.45. OTMW method achieves an average fidelity of 97.07, 94.40, 95.87 and 97.54 and an average ratio of 96.43, 97.83, 97.01 and 98.37. The fidelity measures on various datasets are shown in figure 6. OTMW method achieves a 9.91-11.66 fidelity and 0.91-2.77 ratio improvement over HVM, ACSC, FCME, RGPH.

5.   Conclusion

In this paper, an innovative cluster based key frame extraction method is presented for multi-type videos. This method analyzes the video content by extracting the color, texture and information complexity features. The threshold optimization function is constrained by fidelity and ratio measures. It avoids the dependence on a fixed threshold problem in traditional cluster-based method by computing the optimal threshold. The parameters density ${\rho _i}$, inter-distance ${\eta _i}$, intra-distance ${\varphi _i}$ and weight factor ${\omega _i}$ are used to compute the initial cluster centers and the number of clusters, extract representative frames from k clusters. The method shows promising result on different video datasets. Meanwhile, OTMW achieves competitive and even better fidelity and ratio measure performance when compared with several state-of-the-art cluster-based methods. Overall, we found that OTMW well suited to process key frame extraction problem in the field of static video summarization. However, whether the proposed method also applies in the real-life production and life environment is subject to be verified. In the future, we will explore to apply our proposed method for real-time video surveillance. In addition, we will investigate how to integrate the proposed method into the camera client and how to apply it to daily production and life.

Acknowledgments

The subject is sponsored by the National Natural Science Foundation of P. R. China (No. 61872196, No. 61872194, No. 61902196, No. 62102194 and No. 62102196), Scientific and Technological Support Project of Jiangsu Province (No. BE2019740, No. BK20200753 and No. 20KJB520001), Major Natural Science Research Projects in Colleges and Universities of Jiangsu Province (No. 18KJA520008), Major Natural Science Research Projects in Colleges and Universities of Anhui Province (No.KJ2019ZD20), Six Talent Peaks Project of Jiangsu Province (No. RJFW-111), Postgraduate Research and Practice Innovation Program of Jiangsu Province (No. KYCX19_0909, No. KYCX19_0911, No. KYCX20_0759, No. KYCX21_0787, No. KYCX21_0788 and No. KYCX21_0799).

Conflict of interest

The authors declare there is no conflict of interest.