In recent years tremendous development of the information, computer and communication technologies made humans impossible to process all available and appearing data themselves. Especially, this is true for video content, e.g. every minute 300-500 hours of video (by different sources) are uploaded to YouTube, additionally, users watch over a billion hours every day. Video summarization is a process of selecting some specific subset of keyframes (still images) or keyshots (small sequences of frames) from a video stream which preserves the main idea of video [1]. A summary should keep important frames of the initial video that creates the core summarization challenge -the same frames may be important and unimportant at the same time for different users, making in such a way the summary of video to be a quite subjective term.
A lot of researches [2][3][4][5] distinguish all summarization methods into two classes: unsupervised [6][7][8] and supervised [9][10][11][12]. A brief description of some known methods is below. Some researchers [13][14][15] used self-organizing maps or close approaches. Hierarchical Growing Cell Structures (GCS) methods are proposed in [13,14] as an extension of the Kohonen's Self-Organizing Maps (SOM) that allows to build a flexible structure without knowing the number of classes a priori. A graphical user interface to investigate the construction of two-dimensional SOM is proposed in [15]. Unfortunately, these researches don't contain significant modeling results using at least a dataset of medium size.
One of the most popular summarization approach is VSUMM [7,16]. The authors proposed the method based on the extraction of color features from video frames and unsupervised classification. Additionally, a new measure to compare automatic and user-defined summaries (Comparison of User Summaries, CUS) was presented.
The variety of other video summarizing methods, based on generative adversarial networks [17], long short-term memory networks [11,12], attention-based [18,19] and deep learning approaches [20], using of text annotations both with visual features [21], fuzzy-based incremental clustering [22] were proposed before.
Paper [8] describes the idea to generate video summaries in online mode immediately without seeing the entire video in quasi real time. This method includes the building of the dictionary via group sparse coding for some initial video frames, following by the reconstruction attempt of unseen frames. If reconstruction error is significant enough, a dictionary is updated and the current frame is added to summary.
Ideas proposed in [23] extend dictionary learning with the prediction of interestingness using global camera motion analysis and colorfulness. This approach seems not to be designed for online processing but focused on real time processing mainly.
The implementations of the abovementioned approaches [8] and [23] seem not to be available, as well as test videos for [8].
The contributions of the paper include:
video summarization method based on the self-organizing maps, that can work in online mode (without seeing the whole video) in real time; new three-stage matching of two sets of frames, that includes both keypoint and raw image pixels comparison; selection of the keyframes based on Kohonen's SOM clustering stability; we performed the quality assessment of the proposed online summary generation method using the dataset, which was created by volunteers in online fashion also.
Problem statement 3
Kohonen's self-organizing map (SOM) [24] is one of the most popular neural network unsupervised clustering approaches. This type of network preserves the topology between input and output values and allows to map multidimensional input into lowdimensional (typically 1D or 2D) outputs.
The important property of the Kohonen network is that it is capable of online data processing when input samples come one by one followed by immediate clustering (classification) decision.
Training of Kohonen SOM network implies the update of all weights after the processing of each training sample one by one (online training) and may be done according to stages below. Let n be the quantity of outputs (known a priori) and we denote the quantity of features as m .
1. Initializing of weights for each neuron with the small random weights.
2. Selection for input features vector x .
3. Train the features vector while error for it is bigger than training epsilon (0.0001):
3.1 Find the closest (Best Matching Unit, BMU) neuron in terms of some dis- tance, e.g. Euclidean.
3.2 Update weights ij w for all n neurons according to (1): 4. Repeat step 2 for all features vector increasing t each time. One of the most important parameters to be set up for the usage of the SOM is the size of a one-dimensional or two-dimensional map. In this work, we used a onedimensional map with 20 possible clusters to reach the required real time performance. Our experiments showed that the bigger quantity of clusters requires more training time, the lesser quantity doesn't catch the difference between frames well enough. The successful choice of this parameter allows to balance the quality and the performance of the method being proposed.
The training stage of the SOM continues until all clusters are trained and the quantity of already processed feature vectors is less than 1000.
The selection of features is an important step to represent the specific properties of each frame. The best choice from our point of view is such features, which can be calculated quickly and/or in parallel to preserve real-time processing. We selected the common color features, obtained from floating non-intersection windowing of an image. Averaged R, G and B color components in range [0;1] are used as features from the single window.
We used square windows with size 16 w or 32 w in experiments and rescaled images accordingly to preserve the same length of features vector. The processing of building a feature vector for the entire image was performed in two parallel independent threads and merged at the end.
The selection of keyframes
We will define the keyframe as a frame that varies slightly during some quantity T of previously examined frames in a video stream. We define the quantitative measure of the variability in the two-step procedure. The first step includes the clustering of a frame by SOM. So, we cluster the video stream frame by frame, counting the quantity of frames Q , belonging to the same cluster in a row. When this quantity becomes bigger than the predefined threshold 0 T , we consider this part of a video stream as stable enough and select keyframe candidate from the middle with index 2 /
, where i -is the number of the frame being processed.
At the next step we compare keyframe candidate * k with previously added frame in order to avoid the addition of the very similar, belonging to the same cluster but having some frame with another cluster in between accidently. If
where ) , (
-is the CIEDE2000 difference between two colors [25]. We claim images to be similar if , where 1.5 is the just noticeable difference (JND) for this metric according to [26].
So, we present the entire scheme of the suggested summarization method in Fig. 1. We denote as 42 0 T the quantity of frames, required to be classified as the same class in a row with SOM.
In order to check the quality of summarizing with the suggested approach we need to compare two sets of images, the first one contains images from our automatic summary, the second (ground truth or etalon) one contains images, proposed by humans.
We implemented the match between two sets in three consecutive stages. The first stage includes the rough estimate of match candidate images with Fast Retina Keypoint (FREAK, [27]) descriptor. FREAK is built on FAST keypoint detector [28] and requires initial threshold t to be set up as a required difference between a central pixel and surrounding to identify central pixel as a corner. The bigger value t leads to the less quantity of keypoint being detected. We found 20 t to be a good default value for experiments.
FREAK descriptors contain 512 bits, we compare them in cascades 128 bits each as proposed in [27]. A comparison of chains requires another threshold 0 F , which allows some differences to appear, as the same bit arrays even for close images is the rare case. If corresponding bit chains in descriptors have more differences compared to the threshold, descriptors are considered being different and comparison stops. In our experiments we found threshold 32 0 F to be the good choice (25% bit values may differ between descriptors).
We suggest that two images probably match if the overall quantity of matched descriptors between them is greater than the quantity of non-matched.
When the list of matching candidates is ready, we compare each pair of candidates using comparison (2). We perform these comparisons on feature vectors, built on full size images with window size 32 w . The impact of different 0 F values on the matching results is shown in Fig. 2. The first row contains some frames from the user summary. Three rows below contain some frames from an automatic summary and a corresponding 0 F value (24, 32 or 40). As one can see from Fig. 2, we have one successful match for 24 0 F , three correct matches for 32 0 F . In the last case when 40 0 F we have five matches, one of which is absolutely false (third frame) and one is quite subjective to make the decision about the match (last frame). The last stage is independent of the previous ones and is used for the frames, for which FREAK descriptor is not effective enough. We process the closest (in the scope of Manhattan distance between frame numbers) frames from automatic and user summaries, which were not matched before. Some frames may be skipped earlier because they contain not enough FREAK descriptors. We analyze them with searching the difference between average R, G and B values of the entire full size image. Images are assumed to be similar if the average difference of all three R, G and B is less than 20.
We will estimate the quality of the suggested approach with measuring the CUS values like it was suggested in [7] and F1 scores, like it is described in detail in [18] and applied in [11,12] and others.
A CUS (accuracy) and E CUS (error) metrics are proposed in [7]:
where mAS n is the quantity of matching keyframes from automatic summary, mAS n is the quantity of non-matching keyframes from automatic summary, US n is the total quantity of keyframes from user summary.
, where P is the precision, F is the recall, calculated on the true positives (quantity of matched frames), false positives (quantity of frames which are present if automatic summary but absent in user one), false negatives (quantity of frames which are present in user summary but missing in automatic).
SumMe [10] and TVSum [6] are the most popular datasets in video summarizing, but not suitable for us. They have importance assigned to each frame as a result of the user summary performed on the entire video. This is convenient to build etalon summaries from this user summaries just solving 0/1 knapsack problem for a fixed length of the summary, typically 15%. In our case we make the decision in online mode, so we don't know the final length naturally. Despite we could extend out an automatic summary to make the required length, criteria of frame selection in batch and online modes are very different. So, we used dataset, gathered from Open Video dataset by [7,16], that contains 50 color videos in MPEG-1 format (30 fps, 352x240 pixels) approximately 75 minutes in total.
User summaries were generated by 2 volunteers in online mode. We asked them to select important (from their point of view, no explanations required) frames while looking video-sequences without sound. The modification of previously selected summary frames was not allowed. Users made the decision about the importance of the frame without knowing the content of the entire video.
The specific of human behavior, called chronological bias, is described in [6]. The authors say that humans sometimes claim frames that appear earlier to be more important just because of chronologically, regardless of frame content. This effect leads to the selection of very close frames as important ones. To avoid the influence of chronological bias, we apply the elimination of duplicates in user summaries applying matching of frames, described above.
After we compared automatic summaries using the proposed approach with user summaries, created by volunteers in online mode and cleaned from duplicates, we got such average values:
. Feature vector of length 210 was built on the size of images that two times less than original ones.
We have recalculated these scores for OV [16,29], DT [30] and VSUMM [7] methods using our matching approach, results are presented in Table 1 and they are close to ones, shown in [7]. As one can see, our approach has much bigger E CUS value compared to the same value for our user summaries, created in online mode ( 38 , 0
). That means, that the rules for creation of user summaries (online without seeing the entire video or the selection of keyframes after watching entire video) matters. The total duration of the 50 videos [16] from Open Video dataset is about 75 minutes, we built the summary for all videos in 17 minutes. The average length of the summary is 0.3% of the entire video. One-dimensional map with 20 clusters was used.
We used SumMe [10] dataset to evaluate the processing speed. The duration of 25 videos from the SumMe dataset is approximately 70 minutes, time of processing, the quantity of keyframes in summary and length of the features vector are shown in Table 2.
First column contains the name of video and its duration in minutes and seconds. Values in the second column were calculated for the frames with size two times less, than original, in the third column -three times less. Values in the last column were calculated with specific downscaling factor for each video that limits the quantity of features (maximum allowed width of the frame is 200, height is 140). The empty value in the last column means that the result of processing corresponds to one of the values from previous columns.
Values in the last column in Table 2 show the ratio between the best processing time and the total time of a video. The processing of four videos (Air_Force_One, Eiffel Tower, Notre_Dame and Scuba) didn't satisfy real time requirement. The length of the summary decreases significantly with decreasing of feature vector length for one video (Bearpark_climbing). We tested also the performance of the proposed online summarization method on the two long movies. First one contains 260222 frames and lasts 3 hrs. 00 min. 53 sec. (10853 seconds in total), the second one has 203882 frames and lasts 2 hrs. 21 min. and 43 sec. (8503 seconds in total).
The online summarization of the first movie took 3800 seconds for 336 features per frame, the length of the summary was 705 frames. Second video required 2209 seconds to build summary containing 585 frames using 252 features per frame.
We proposed an approach to generate the video summary in the form of keyframes, which are still images. It is based on the clustering of separate frames in online mode without the analysis of the whole video using Kohonen's self-organized maps. The frame from the video stream is selected as a summary frame if some quantity of frames 2 / 0 T after it and before were classified as the same cluster. The proposed method was tested on Open Video dataset and the performance is tested on SumMe dataset. We showed that the quality is comparable to some batch video summarization methods, and the performance combined with the flexibility in the selection of the quantity of frame features allows achieving real time processing in most cases. The quality of the suggested method is better compared to the user summary created in online mode.
The investigation of the dependency of quality and performance on the size of SOM map may be the topic of future research.