Abstract:
Disclosed herein is a method of detecting a shot transition of a moving picture video, comprising the steps of: extracting a color histogram of three adjacent frames in order on time series; obtaining a difference of the color histogram between the three adjacent frames and then detecting a shot transition candidate interval by concurrently using arrangement characteristics of the difference of the color histogram; and examining a distribution of a macro block type within the shot transition candidate interval and verifying whether a shot transition is present or not within the shot transition candidate interval.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates generally to a method for automatically detecting a transition of video shot, and more particularly to a method of minimizing a false alarm occurring in the algorithm for automatically detecting a transition of video shot, by using multi-level color histogram comparisons.  
           [0003]    2. Description of the Prior Art  
           [0004]    A non-linear video search and browsing employs a shot segmentation method. A term “shot” is referred to a sequence of video stream obtained, without any interruption, by a single camera. A video is configured by an interconnection of a number of shots and a variety of edition effects are used to interconnect the shots.  
           [0005]    The edition effects used for a video edition generally include an abrupt shot transition and a gradual shot transition. The gradual shot transition includes a fade, a dissolve, a wipe, etc. The abrupt shot transition is also referred to as a hard cut.  
           [0006]    Based on results of various researches, it is reported that a shot segmentation method using a global color distribution provides a satisfactory outcome. In addition, for accomplishing a fast and precise algorithm, a video codec using a bi-directional compression, such as a MPEG (Moving Picture Expert Group), tries to detect a more precise shot transition by modeling a type distribution characteristic of macro blocks in a shot transition interval.  
           [0007]    Typically, difference of color distribution between adjacent frames is very large in positions where the hard cut occurs. So, the hard cut is detected by using such a property.  
           [0008]    On the other hand, for accomplishing a faster detection of shot transition, the information on the color histogram is extracted in predetermined several frame intervals without being extracted in each frame. In addition, in a video coding scheme such as the MPEG, the information on the color histogram is extracted by the unit of I frame which is encoded independently and then is used for the shot segmentation algorithm.  
           [0009]    Recently, for accomplishing a more faster shot segmentation algorithm, the color histogram is extracted from a reduced image such as a DC image, or sub-sampled image and then is used as input of the shot segmentation algorithm. In addition, it is known that there is no significant difference between the color histogram extracted from such a DC image or a sub-sampled image and the color histogram extracted from an original image.  
           [0010]    In the meantime, a recent shot segmentation algorithm detects not only whether a shot transition actually occurred but also a precise position where the shot transition occurred in a shot transition candidate interval obtained by performing a color histogram comparison, by using macro block type information or motion vector information.  
           [0011]    Existing shot transition detecting algorithms use a color histogram between two adjacent frames or two frames apart by a specific time interval from each other as an important input of the shot segmentation.  
           [0012]    However, a relative significant difference of image between two adjacent frames or two frames apart by a specific time interval from each other appears not only at a shot transition point but also a camera flash, a fast motion interval of a large object, a fast camera motion interval, etc, cause occurrence of erroneous detection. In addition, such an erroneous detection of the shot segmentation will not be easily removed due to a difficulty in a distinction between the erroneous detection and a distribution characteristic of the macro block type at the shot transition point. For example, the camera flash appears frequently in interview scenes, the fast motion of the large object frequently appears in sports videos, and the fast camera motion also frequently appears regardless of a genre, especially, in the sports videos, such as a golf video. Therefore, in a shot segmentation, there exists a need for an algorithm that is capable of minimizing the erroneous detection of the shot occurred by such a camera flash or occurred in a scene on which an object moving in a high speed appears.  
           [0013]    In other words, in order to reduce a probability of the erroneous detection, the color histogram comparison method or the macro block type distribution analysis method should be applied more precisely. However, the macro block type distribution analysis method is different for each moving picture encoder and is varied depending on encoding input parameters. Accordingly, if the encoding input parameters are significantly adjusted, another erroneous detection or miss detection may be generated. This invites a difficulty of improvement in an entire performance of the shot segmentation.  
           [0014]    On the other hand, the shot, which was detected by the automatic shot transition algorithm as described above, is representative as a key frame and the shot is provided to users in the form of story board, or is used as a means of moving to a desired scene or as a basic input of an algorithm such as a shot clustering. Therefore, the automatic shot transition algorithm requires a high level of accuracy.  
         SUMMARY OF THE INVENTION  
         [0015]    Accordingly, the present invention has been made keeping in mind the above needs or problems occurring in the prior art, and an object of the present invention is to provide a shot transition detecting method which is capable of increasing an accuracy of a shot segmentation, by providing more precise method of detecting a shot transition by using a multi-level color histogram comparison method.  
           [0016]    In order to accomplish the above object, the present invention provides a shot transition detecting method comprising the steps of: extracting a color histogram of three frames in order on time series; obtaining a difference of the color histogram between the three frames and then detecting a shot transition candidate interval by concurrently using arrangement characteristics of the difference of the color histogram; and examining a distribution of a macro block type within the shot transition candidate interval and verifying whether a shot transition is present or not within the shot transition candidate interval.  
           [0017]    Preferably, said step of detecting a shot transition candidate interval includes generating a histogram difference vector consisting of a histogram difference between three frames; and determining whether a concerned interval is the shot transition candidate interval by using a characteristic of each element value of the histogram difference vector.  
           [0018]    Preferably, said step of verifying whether a shot transition is present or not includes verifying whether a shot transition is present or not by concurrently using characteristics of the macro block type of a P frame and the macro block type of a B frame within a concerned interval. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0019]    The above and other objects, features and other advantages of the present invention will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings, in which:  
         [0020]    [0020]FIG. 1 is a view for illustrating an example of a MPEG video sequence;  
         [0021]    [0021]FIG. 2 is a schematized view for explaining a multicolor histogram comparison method according to the present invention;  
         [0022]    [0022]FIG. 3 is a flowchart for explaining a shot transition detecting method according to the present invention;  
         [0023]    [0023]FIG. 4 is a view for illustrating rates of intra-coded blocks at a point where a hard cut is generated;  
         [0024]    [0024]FIG. 5 is a view showing a distribution of a macro block type when the hard cut is generated; and  
         [0025]    [0025]FIG. 6 is a view for explaining a relationship between a forward prediction and a gradual shot variation in a MPEG video sequence.  
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0026]    Hereinafter, the present invention will be in detail described through embodiments with reference to the accompanying drawings.  
         [0027]    [0027]FIG. 1 is a view for illustrating a structure of a video sequence compressed by the MPEG.  
         [0028]    Typically, GOP (Group Of Picture) means a frame sequence from an I frame to next I frame. There exist a P frame and a B frame in addition to the I frame in a MPEG compression method. The P frame is coded by using a forwarding prediction and the B frame is coded by concurrently using the forward prediction and a backward prediction. An anchor frame is a basis frame for motion prediction and compensation. The anchor frame for the P frame is an immediately previous I frame or P frame and the anchor frame for the B frame is an immediately previous and next I frame and/or P frame.  
         [0029]    In the shot transition detecting method of the moving picture video according to the present invention, the shot transition is detected with the I frame as a predetermined unit.  
         [0030]    [0030]FIG. 2 is a schematized view for explaining a multi-level color histogram comparison method for minimizing an erroneous detection of the shot transition, according to the present invention.  
         [0031]    In the following description, I k  (k= . . . , j−2, j−1, j, . . . ) means a k-th I frame.  
         [0032]    A more robust shot segmentation engine is implemented by obtaining a color histogram difference D 1  between an I j−2  frame and an I j−1  frame, a color histogram difference D 2  between an I j  frame and an I j−1  frame, and a color histogram difference D 3  between an I j  frame and an I j−2  frame, and concurrently using these color histogram differences D 1 , D 2  and D 3 . More particularly, it is checked whether these color histogram differences D 1 , D 2  and D 3  satisfy color histogram difference (CHD) condition of the shot transition. If satisfied, the shot transition is considered to have been generated.  
         [0033]    Now, an application example of a comparison between the color histograms in the present invention will be in detail described.  
         [0034]    Typically, when the shot transition is generated due to a hard cut between the I j−2  frame and the I j−1  frame, D 1  shows a relatively large value and D 2  shows a relatively small value. If both of D 1  and D 2  show a large value, it is commonly considered as a phenomenon exhibited by fast camera motion or fast object motion and, therefore, an erroneous detection will be significantly reduced.  
         [0035]    However, although both of D 1  and D 2  show a large value, there exists a shot transition due to the hard cut. This is a case in which a first portion of a new shot begins with the fast object motion or the fast camera motion. At this point, there is a need to separate a case that both of D 1  and D 2  are large due to the shot transition and a case that both of D 1  and D 2  are large due to the fast object motion and the fast camera motion. D 3  is used for accomplishing such a separation.  
         [0036]    Typically, a ratio D 1 /D 3  in the shot transition due to the hard cut appears larger than that in the shot transition due to the fast object motion and the fast camera motion.  
         [0037]    On the other hand, in case of an instantaneous camera flash, both of D 1  and D 2  are relatively very large while D 3  is relatively very small. This case may be considered as the instantaneous camera flash since it is not the hard cut.  
         [0038]    By using the comparison of the color histogram as described above, the erroneous detection due to the camera flash can be reduced. In other words, when D 1  and D 2  for the color histogram are used or D 1 , D 2  and D 3  are concurrently used, the erroneous detection in a hard cut detecting algorithm can be minimized.  
         [0039]    On the other hand, in the gradual shot transition method including a fade, a dissolve, a wipe, etc, D 1 +D 2  appears in theory almost similar to D 3 . However, D 1 +D 2  is not equal in reality to D 3  due to used different color spaces (including RGB, YCrCb, HSV, etc.) and quantization methods. But, as a relationship of τ 1 &lt;(D 1 +D 2 )/D 3 &lt;τ u  is satisfied, if τ 1  and τ u  are properly set, the erroneous detection of the gradual shot transition can be reduced. Here, τ 1  and τ u  mean threshold values.  
         [0040]    [0040]FIG. 3 is a shot segmentation algorithm to which the shot transition detecting method of the present invention is applied.  
         [0041]    Referring to FIG. 3, the shot transition detecting method of the present invention consists generally of a first step of preparation ( 301  to  304 ), a second step of detecting candidates ( 305  to  308 ), and a third step of verifying the candidates ( 309  to  311 ).  
         [0042]    In the first step of preparation ( 301  to  304 ), a color histogram for two successive I frames I j−2  and I j−1  is extracted. In the second step of detecting the candidates ( 305  to  308 ), a color histogram for a current I frame I j  is extracted ( 306 ), histogram difference vectors D 1 , D 2  and D 3  for consisting of three color histogram differences are obtained ( 307 ), and it is checked whether each of these vectors satisfies the color histogram difference (CHD) condition ( 308 ).  
         [0043]    In the step ( 307 ), CHistDiff(I j−2 , I j−1 ) is a function for obtaining the color histogram difference D 1  between I j−2  frame and I j−1  frame, CHistDiff(I j−1 , I j ) is a function for obtaining the color histogram difference D 2  between I j−1  frame and I j frame, and CHistDiff(I j−2 , I j ) is a function for obtaining the color histogram difference D 3  between I j−2  frame and I j  frame.  
         [0044]    The color histogram difference (CHD) condition with respect to the shot transition in the present invention is as follows:  
         [0045]    [Hard Cut Condition] 
         [0046]    1. D 1 &gt;τ 1  &amp;&amp; D 2 &lt;τ 2  (High Probability)  
         [0047]    2. D 1 &gt;τ 3  &amp;&amp; D 2 &gt;τ 3  &amp;&amp; D 1 /D 3 &gt;τ 4  &amp;&amp; D 3 &gt;τ 5  (Low Probability)  
         [0048]    [Gradual Transition Condition] 
         [0049]    1. D 1 &gt;τ 6  &amp;&amp; D 2 &lt;τ 6  &amp;&amp; D 3 &lt;τ 7  (High Probability)  
         [0050]    2. D 1 &gt;τ 6  &amp;&amp; D 2 &gt;τ 6  &amp;&amp; τ 8 &lt;(D 1 +D 2 )/D 3 &lt;τ 9  (Low Probability)  
         [0051]    [Shot Non-transition Condition ] 
         [0052]    Do not Satisfy [Hard Cut Condition] &amp;&amp; [Gradual Transition Condition] Where, τ x  is a prescribed threshold value. By adjusting this threshold value, shot segmentation performance can be improved.  
         [0053]    If the histogram difference vectors D 1 , D 2  and D 3  satisfy the color histogram difference (CHD) condition, the step of verifying the candidates (below  309 ) is performed for a concerned interval (I j−2 , I j−1 ). If not so, the procedure returns to the step ( 305 ) for performing the shot transition detecting algorithm for next interval.  
         [0054]    Now, the third step of verifying the candidates ( 309  to  312 ) will be described.  
         [0055]    In the step of verifying the candidates, MBTCond(I j−2 , I j−1 ) is a function whose input is macro block type information for the P frame and the B frame between I j−2  and I j−1  and whose output is macro block type characteristic vector MBT(m 0 ,m 1  . . . m n ).  
         [0056]    In the step ( 309 ), the macro block type characteristic vector can be obtained by using macro block type distribution of the P frame and the B frame in an input interval (I j−2 , I j−1 ). In next step ( 310 ), it is checked whether the macro block type characteristic vector satisfies macro block type distribution condition for the shot detection. If so, it is indicated that the shot transition is generated in the input interval (I j−2 , I j−1 ). If necessary, a precise shot transition position is recorded ( 311 ). In next step ( 312 ), it is checked whether the I frame is further present or not. If so, the procedure returns to the step ( 305 ) for performing the shot transition detecting algorithm for next interval. If not so, the procedure is terminated.  
         [0057]    However, in the step ( 310 ), if the macro block type characteristic vector does not satisfy the macro block type distribution condition for the shot detection, it is considered that the shot transition is not generated in the input interval (I j−2 , I j−1 ) is indicated. Next, the procedure returns to the step ( 305 ) for performing the shot transition detecting algorithm for next interval.  
         [0058]    FIGS.  4  to  6  are views for explaining an algorithm of the third step of verifying the candidates.  
         [0059]    Generally, a peak appears in rates of intra-coded blocks of P frame within an interval in which a hard cut is generated. A reference pattern for clearly distinguishing the hard cut generating interval from other common intervals is modeled to appear in B frames between a concerned peak and the P frame or the I frame previous to the concerned peak.  
         [0060]    For example referring FIG. 4, it is assumed that four P frames P 1 , P 2 , P 3  and P 4  are present within a concerned GOP and a peak above a predetermined threshold value is generated in the frame P 3 . Since this case may be a case that a hard cut is generated in a subinterval P 2 -P 3 , the reference pattern of the B frame for the subinterval P 2 -P 3  is checked.  
         [0061]    [0061]FIG. 5 is a schematized view showing a coding feature of B frames in the hard cut generating subinterval with a reference of an extreme number of macro blocks in one anchor frame of two adjacent anchor frames, where a dark frame indicates a shot boundary point. That is, arrows directed from B frames point to one anchor frame referred in extreme numbers, of the two adjacent anchor frames.  
         [0062]    Referring to FIG. 5, in each of four cases, arrows directed from B frames placed at both sides of the shot boundary point indicate a respectively opposite anchor frame referring an extreme number of macro blocks.  
         [0063]    The presence of such a reference pattern gives the verification that the shot transition has been present.  
         [0064]    [0064]FIG. 6 is a schematized view showing a characteristic of FMBR (=M fwd /(M fwd +M bwd )(M fwd : the number of forward reference macro block, M bwd : the number of backward reference macro block) of the B frame adjacent to an anchor frame within an interval in which a fade or a dissolve is generated and a characteristic of FMBR within an interval in which a fade or a dissolve is not generated.  
         [0065]    [0065]FIG. 6 shows that FMBR is largely swung during above a prescribed period in B frames adjacent to an anchor frame in a shot transition interval using the fade or the dissolve and such a characteristic does not appear in otherwise intervals. In addition, since a characteristic macro block type distribution appears in the shot transition using a wipe or a special effect, such a distribution can be used to detect the shot transition.  
         [0066]    In the third step of verifying the candidates, only hard cut condition for the macro block type can be checked in an interval to which the information on the type of the shot transition using the histogram vector described earlier is provided as an additional input and which is determined to be the hard cut by the condition of the color histogram, and only gradual variation condition can be checked in an interval which is determined to be the gradual shot transition.  
         [0067]    On the other hand, by using an adaptable method in which a threshold value of the macro block type condition is loosely adjusted in a case of high probability in the condition of the color histogram and the threshold value is strictly adjusted in a case of low probability in the condition of the color histogram, the performance of the entire shot transition detecting algorithm can be enhanced.  
         [0068]    As described above, the present invention can reduce the erroneous detection of the shot transition due to the instantaneous camera flash, the fast object motion, and the fast camera motion through the comparison in multi-step between the color histograms.  
         [0069]    In addition, although the present invention further requires an additional process, i.e., color histogram comparison operation, when viewed from the entire segmentation engine, since the increased amount of process is extremely slight, the present invention can contribute to the improvement of performance of the shot transition detecting algorithm.  
         [0070]    In addition, when the shot transition detecting method of the present invention is used, the performance of a key frame interface such as a story board can be enhanced by constructing a fast and precise shot segmentation engine, the satisfaction of user for non-linear browsing is raised, and a basis on which a higher level of shot clustering engine is constructed can be provided.  
         [0071]    Although the preferred embodiments of the present invention have been disclosed for illustrative purposes, those skilled in the art will appreciate that various modifications, additions and substitutions are possible, without departing from the scope and spirit of the invention as disclosed in the accompanying claims.