KR20050041761A - Method of detecting shot change frames - Google Patents

Abstract

The present invention relates to image processing, and more particularly, to a method of detecting a shot change frame, the method comprising: acquiring a characteristic change amount between two adjacent frames according to a plurality of shot change frame detection parameters in a training video; Setting a threshold for maximizing the number of shot change frames each time, generating a binary classification tree using a plurality of shot change frame detection parameters and thresholds set for each detection parameter, and using the generated binary classification tree. And detecting a shot change frame in the video.

Description

Method of detecting shot change frames}

The present invention relates to an image processing technique, and more particularly, to a shot switching frame detection method for detecting a frame in which a shot is switched in a video.

Until recently, movies including movies and personal videos were mainly watched through VTRs and TVs. However, with the development of electrical and electronic technology, not only DVRs, PVRs, computers, but also mobile phones can be viewed. Accordingly, recently, detection technologies for quickly and easily detecting desired screen information are increasing so that a user can conveniently search and enjoy a video.

Among the currently proposed detection techniques, there is a technique of detecting only key frames in the entire video. In general, a frame refers to basic screen information constituting an entire video, and a shot refers to a set of frames from one camera operation to another camera. Usually, two adjacent frames within a shot have high similarity in the content, pixel brightness, and histogram characteristics, whereas the two adjacent frames in which the shot is switched have different contents, and the brightness, histogram, different. The proposed key frame detection technology detects and displays the frame in which the shot is converted by using a single characteristic such as pixel brightness difference or histogram characteristic change between two adjacent frames so that the user can know the entire contents of the video quickly. It is a technique to do.

Here, the pixel brightness comparison method between two adjacent frames has a fixed background, and the detection performance is remarkably high when applied to a moving picture obtained when the camera moves little or moves slowly. On the other hand, the histogram comparison method between two adjacent frames has a high detection performance when applied to a moving image obtained when an object or a camera moves or rotates quickly. However, if the pixel brightness comparison between two adjacent frames is applied to an object or a movie obtained when the camera moves or rotates quickly, the histogram comparison between two adjacent frames may have a fixed background and the camera may move or move slowly. When applied to a video obtained at the time of shot conversion frame detection performance is significantly reduced.

Therefore, conventionally, when using the proposed key frame detection techniques to detect a frame in which the shot is converted in the video produced by a variety of camera shooting and editing methods, a problem that the user is unreliable in the detection performance has occurred .

The present invention has been proposed in the background as described above, and when a shot change frame is detected in a video produced by various camera shooting and editing methods using the proposed key frame detection techniques, the user has no confidence in the detection performance. It is an object of the present invention to provide a method for detecting a shot switchover frame.

According to an aspect of the present invention, there is provided a method of detecting a shot change frame according to an aspect of the present invention, including: acquiring a characteristic change amount between two adjacent frames according to a plurality of shot change frame detection parameters in a training video; Receiving a threshold for maximizing the number of shot change frames per parameter, generating a binary classification tree using a plurality of shot change frame detection parameters and thresholds set for each detection parameter, and using the generated binary classification tree And detecting a shot change frame in the corresponding video.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art can easily understand and reproduce the present invention.

FIG. 1 illustrates a process of detecting a shot change frame in a video according to the present invention, and FIG. 2 illustrates a shot change frame that is not detected for each shot change frame detection parameter and a frame incorrectly determined as shot change in a video according to the present invention. 3 is a graph illustrating an example, and FIG. 3 illustrates a binary classification tree according to a temporary embodiment of the present invention. Hereinafter, a description will be given with reference to FIGS. 1 to 3.

Referring to FIG. 1, first, in order to detect a shot change frame in an arbitrary video, an amount of change in characteristics between two adjacent frames according to a plurality of shot change frame detection parameters in a training video must be obtained (S10). In a preferred embodiment of the present invention, the plurality of shot switching frame detection parameters are characterized by a feature variable (LPD) relating to the difference in the overall area pixel brightness between two adjacent frames, and a feature variable (IHD) relating to the difference in the whole area pixel brightness histogram. And a feature variable LHL for local region pixel brightness histogram differences, a feature variable HHD for full region color histogram differences, and a feature variable LLR for similarity of entire region blocks using brightness components.

The feature variable (LPD) related to the full-area pixel brightness difference is excellent in detection performance when applied to a moving image obtained when the background is fixed and the camera is almost unmoving or moving slowly, and is calculated based on Equation 1 below.

Here, N and M represent the horizontal and vertical size of the image, Is the brightness value at the point of the mth frame.

The feature variable (IHD) for the full-area pixel brightness histogram difference, the feature variable (LHL) for the local-area pixel brightness histogram difference, and the feature variable (HHD) for the full-area color histogram difference are the brightness or The color distribution is obtained and then the two adjacent histogram distributions are compared. This method shows stable performance for camera rotation, tilt and pan, and fast movement of objects. However, since the histogram-based technique uses only the brightness / color distribution of the frame, location information disappears. Therefore, if the histogram distribution is similar between two frames, the shot may be missed. In order to solve this problem, a local histogram method is used, which divides an entire frame into a predetermined number of equal blocks, and compares the histogram distribution between blocks of adjacent frames corresponding to each block to obtain similarity. . Therefore, the histogram method shows excellent performance in the case of cuts in which the brightness / color distribution changes. The feature variable IHD related to the full area pixel brightness histogram difference is calculated based on Equation 2 below, and the feature variable LHL related to the local area pixel brightness histogram difference is calculated based on Equation 3 below.

here, Represents the histogram of the m-th frame, B is the maximum brightness value.

Where | BS | is the number of pixels in the block.

In the present embodiment, the feature variable LHL related to the local area pixel brightness histogram difference is equally divided into 16 blocks to measure the similarity between blocks. Of these measured similarities, eight blocks with low similarity are used to detect the scene turning point. Here, the eight excluded upper blocks are for removing the movement of the partially occurring object.

The feature variable (LLR) related to the similarity of the whole area block using the brightness component is a block-based method of measuring similarity by dividing adjacent frames into predetermined blocks and using a similarity ratio between adjacent blocks. Since this method is applied in units of blocks, it is less sensitive to movement. In addition, an object of arbitrary shape is excellent for changing cuts. The implementation divides a frame so that it is not duplicated in the same block units. The average and the variance are calculated for each block, and similarity with neighboring blocks of a block corresponding to an adjacent frame is examined to obtain a similarity function of the block having the highest similarity. At this time, if the result of the similarity function is greater than a predetermined threshold value, the weight is set to 1, and if it is less than that, the weight is set to 0 to check the similarity for the entire frame. The feature variable LLR related to the similarity of the entire area block using the brightness component is calculated based on Equation 4 below.

here, and Denotes the mean and variance of the i th block

After acquiring a feature change amount between two adjacent frames in the training video for each of the five shot change frame detection parameters described above, a threshold value for each detection parameter should be set (S12). In the present embodiment, the threshold is set through the experiment using the training video, the training video used is the Matrix (The Matrix) and the Mission Impossible (The Mission Impossible). Each training video is 15 frames per second and the video size is 320 × 240. The two learning videos do not include various editing techniques, but consist only of camera movement (pan, tilt, zoom) and editing by cut. In the present embodiment, the total frames of the two learning videos and the number of shot turning points generated are obtained through direct confirmation, and the results are shown in Table 1 below. Here, SC (Shot Change) represents a shot change point, and NSC (No Shot Change) represents a frame that is not a shot change point.

Sequence type Total number of frames SC NSC matrix 2167 48 2119 mission Impossible 2429 30 2399

Subsequently, in the present embodiment, it is preferable to set a threshold value so that the number of frames other than the shot change is maximized when the binary classification is performed for each shot change frame detection parameter. 2A to 2E, the LPD threshold is 0.051, the HHD threshold is 0.154, the IHD threshold is 0.162, the LLR threshold is 2.2, and the LHL threshold is 0.17, as shown in FIGS. 2A to 2E. Is set to. In the present embodiment, a recall index, a precision index, and an evaluation index (EI) used for evaluating detection performance of each shot switching frame detection parameter are defined as shown in Equation 5 below.

precision =

EI = (recall + precision) / 2

Here, S _C is the total number of shot turning points present in the training video. S _M is the number of shot change points that are not detected (MD: Missed Detection) in each shot change frame detection parameter, and S _F is the number of frames that are falsely determined as a shot change point (FA). The closer to EI, the better the performance.

matrix LPD IHD LHL HHD LLR S _C S _M S _F S _M S _F S _M S _F S _M S _F S _M S _F 48 4 48 3 39 3 34 3 25 3 37 re./pr. 92 50 94 55 94 59 94 66 94 56 EI 71 74.5 76.5 80 75

Mission Impossible LPD IHD LHL HHD LLR S _C S _M S _F S _M S _F S _M S _F S _M S _F S _M S _F 30 0 6 One 5 0 4 One 8 0 One re./pr. 100 83 97 86 100 88 97 79 100 97 EI 92 91.5 94 88 99

In Table 2, threshold values were experimentally set to maximize the value of EI for each shot switching frame detection parameter. In the case of the "matrix", the feature variable (HHD) for the difference of adjacent full-area color histograms relative to EI performs the best, while the feature variable (LPD) for the difference in full-area pixel brightness between two adjacent frames performs the best. It can be seen that the fall. In addition, the Mission Impossible has a good performance in terms of the LLR of the similarity of the entire area block using the brightness component, whereas the HHD of the HDS of the full area color histogram is poor. As you can see, Mission Impossible is the best of the two training videos. However, the matrix does not perform well with a single technique.

Referring to FIG. 2, it is possible to identify shot change frames that are not detected for each shot change frame detection parameter and frames incorrectly determined as shot change on two learning videos. Looking at each shot transition frame detection parameter, the shot transition points A and C were correctly found by HHD and LHL, but according to the detection parameters, LPD generated a shot transition frame that was not detected in C, and IHD changed from D and F to shot transition. An incorrectly determined frame has occurred. The LLR then generates a frame that is incorrectly determined to be a shot transition at E.

In this way, when the detection methods are executed independently for the same sequence, the results are different according to each performance. However, when several features are applied at the same time, the relationship between the methods is shown. have. For example, when two IHD and LLRs are applied at the same time, A, C, D, and F are detected as shot transitions by the IHD. On the other hand, the LLR detects shot transitions at A, C, and E. In other words, if IHD is applied first and then LLR is applied using both methods, the shot transition points A and C will be accurately found.

Thereafter, if a threshold is set for each shot change frame detection parameter, an optimal binary classification tree for finding a shot change frame should be generated using the shot change frame detection parameter and the threshold set for each shot change frame detection parameter (S14).

In the present embodiment, it is preferable that the shot change frame detection parameter and the threshold value are set sequentially in each binary classification tree so that the number of frames other than the shot result shot change is maximized.

Referring to Fig. 3, the first binary classification includes an LHL capable of classifying 2058 frames other than shot transitions. At this time, the threshold value is 0.165. According to this threshold, the number of shot change frames is detected as zero. Subsequently, other 109 frames other than 2058 which are not shot transition frames are used again to determine whether they are shot transition frames using other shot transition frame detection parameters. For this determination, shot transition frame detection parameters and thresholds are set in the next binary classification branch so that the number of frames other than the classification result shot transition is maximized. In this embodiment, LLR is used. The threshold for the LLR is set to 1.791 and it is determined that the number of frames not exceeding this threshold is 26. In the following binary classification branch, HHD is used for 83 frames except 26 out of 109. The threshold for this HHD is set to 0.075. Of the remaining 83 frames, the number of frames not exceeding 0.075, that is, not shot transition is determined to be seven. Next, in the binary classification branch, 76 frames other than 7 out of 83 frames are judged as shot change frames using the remaining feature parameters, and the number of shot change frames is determined to be 48, and the number of nsc frames is Although finally judged as 28, since the sc class is superior according to the majority rule, the number of 76 frames is classified as sc class. The generation of the binary classification tree is generated as a maximum binary classification tree until no impurities occur or a stopping criterion is satisfied.

When the optimal binary classification tree for finding the shot change frame is generated using the threshold set for each shot change frame detection parameter, the shot change frame is detected from an arbitrary video having no known shot change frame (S14).

Table 5 uses the matrix as a learning video, acquires the feature change for each shot transition frame detection parameter in the mission impossible, and uses the binary classification tree classified as shown in FIG. Statistics (Table 5a) and classification results (Table 5b) are shown.

Classification result by shot change frame detection parameter Forecast result Number of frames according to classification Response Prob N Correct Node One NSC 0.957 2324 1.0 2324 2 NSC 0.029 70 1.0 70 3 - 0 0 0 0 4 SC 0.014 35 0.857 35

Actual classification frame class Expected Classified Frame Class Number of frames according to classification SC NSC SC 30 0 30 NSC 5 2394 2394 sum 35 2394 2429 accuracy 1.000 0.998 Overall accuracy 0.999

Table 6 shows a drop-case method using a matrix as a learning video, using a binary classification tree classified as shown in FIG. The statistics by node (Table 6a) and classification results (Table 6b) are shown.

Classification result by shot change frame detection parameter Forecast result Number of frames according to classification Response Prob N Correct Node One NSC 0.859 2331 1.0 2331 2 NSC 0.127 345 0.991 345 3 - 0 0 0 0 4 SC 0.015 41 0.829 41

Actual classification frame class Expected Classified Frame Class Number of frames according to classification SC NSC SC 34 3 37 NSC 7 2672 2679 sum 41 2675 2716 accuracy 0.919 0.997 Overall accuracy 0.958

Tables 5a and 6a show data collected at each final node by dropping test sample data one by one into the binary classification tree of FIG. 3. Four categories are analyzed to classify the information collected by each node statistically. Firstly, "Response" represents a prediction class of data collected for each node. The second "Prob (probability)" represents the frequency of occurrence of data collected at each node of the entire data sample. The third item "N" refers to the number of samples collected at each node, and the last item "Correct" measures class purity when the collected data are divided by class. Looking at each item using Table 5a above, the number (N) collected in node 1 is 2324, and 2324 of the results belong to nsc class, indicating that "Correct" is 1.0. Thus, "Response" of node 1 indicates that it predicts with class nsc. Further, "Prob" is that 2324 of the total number of frames in 2429 are classified at node 1, and a result of 0.957 was calculated. The number N collected at node 2 is 70, "Correct" is 1.0, and is also predicted by the class nsc. Node 3 indicates that the class is unpredictable because there are zero collected, while the remaining node 4 has 35 collected and predicted as sc with an accuracy of 0.857.

Tables 5b and 6b summarize the results classified by Tables 5a and 6a by shot class (sc) frame and non-shot transition (nsc) frame class. The classification accuracy (Correct) for each frame of shot transition (sc) and non-shot transition (nsc) was calculated. Therefore, in the case of mission impossible, the frame class classification capability of the shot transition (sc) frame and the non-shot transition (nsc) is 1.0 and 0.998, respectively, and the overall accuracy is 0.999. Documentary images of 0.919, 0.997, and 0.958 were calculated. This is higher than the classification probability of 89.6% and 98.7%, respectively, of the shot transition (sc) frame and the non-shot transition (nsc) frame class, which are the cross-validation results. Thus, it can be seen that the binary classification tree detects shot transition points well even for sample sequences that do not intervene in the tree generation process. Through the above experiment, the results of the single feature and the performance of the proposed method are compared in Table 7.

Classification result by shot change frame detection parameter Binary classification result division recall precision EI recall precision EI matrix HHD 94 66 80 100 63 81.5 mission Impossible LLR 100 97 98.5 100 99 99.5 documentary LHL 100 86 93 92 99 95.5

In Table 7, it can be seen that the average performance improvement of 2% for EI. However, in the case of the Mission Impossible, the performance of the EI is similar, but the precision proposed in the present invention is improved in the case of precision.

As described above, in the present invention, by using a plurality of shot change frame detection parameters and generating a binary classification tree so as to be easily applied to any video, various camera shooting and editing methods using existing key frame detection techniques are proposed. When the shot change frame is detected in the video produced by the user, the user can have a reliable effect on the detection performance.

Although the present invention has been described with reference to the accompanying drawings, it will be apparent to those skilled in the art that many various obvious modifications are possible without departing from the scope of the invention from this description. Therefore, it should be interpreted by the claims described to include many such variations.

1 illustrates a process of detecting a shot change frame in a video according to the present invention.

2 is a graph illustrating an example of a shot change frame that is not detected for each shot change frame detection parameter and a frame that is incorrectly determined as shot change in a video according to the present invention.

3 illustrates a binary classification tree according to a temporary embodiment of the present invention.

Claims (3)

Acquiring a characteristic change amount between two adjacent frames according to a plurality of shot change frame detection parameters in the training video; Setting a threshold to maximize the number of shot change frames for each shot change frame detection parameter; Generating a binary classification tree using the plurality of shot change frame detection parameters and thresholds set for each detection parameter; Detecting a shot change frame in the test video by using the generated binary classification tree; Shot switching frame detection method comprising a. The method of claim 1, wherein acquiring a feature change amount between two adjacent frames according to the plurality of shot change frame detection parameters comprises: A feature variable (LPD) for the total area pixel brightness difference between two adjacent frames, a feature variable (IHD) for the total area pixel brightness histogram difference, a feature variable (LHL) for the local area pixel brightness histogram difference, and global color And a plurality of shot change frame detection parameters including a feature variable (HHD) related to the histogram difference and a feature variable (LLR) related to the similarity of global blocks using brightness components. The method of claim 1 or 2, wherein the step of generating a binary classification tree: And a shot change frame detection parameter and a threshold value are set sequentially in each binary classification tree so that the number of frames other than the classification result shot change is maximized.