Abstract:
A method segments a video. Audio frames of the video are classified with labels. Dominant labels are assigned to successive time intervals of consecutive labels. A semantic description is constructed for sliding time windows of the successive time intervals, in which the sliding time windows overlap in time, and the semantic description for each time window is a transition matrix determined from the dominant labels of the time intervals. A marker is determined from the transition matrices, in which a frequency of occurrence of the marker is between a low frequency threshold and a high frequency threshold. Then, the video is segmented at the locations of the markers.

Description:
FIELD OF THE INVENTION 
       [0001]    This invention relates generally to segmenting videos, and more particularly to segmenting videos according to audio signals. 
       BACKGROUND OF THE INVENTION 
       [0002]    Segmenting videos is an important task in many video summarization, retrieval and browsing applications. As used herein, a video includes video content containing visual information (pixels), and audio content containing audio information (acoustic signals). The video content and the audio content are synchronized. The content can be unscripted or scripted. 
         [0003]    Unscripted content, such as content acquired from surveillance and sport events, can be segmented by identifying highlights. A highlight is any portion of the video that contains an unusual or interesting event. Because the highlights can capture the essence of the video, segments of the video containing just highlights can provide a summary of the video. For example, in a video of a sporting event, a summary can include scoring opportunities. 
         [0004]    Scripted content, such as news and drama, is usually structured as a sequence of scenes. One can get an essence of the content by viewing representative scenes or portions thereof. Hence, table of contents (ToC) based video browsing provides a summarization of scripted content. For instance, a news video composed of a sequence of news stories can be summarized or browsed using a key-frame representation for each portion in a story. For extraction of the ToC, segmentation is often used. 
         [0005]    Video segmentation based on the visual content is known. Typically, low-level features, such as color intensities and motion, are used. However, such segmentation can be complex and time consuming because the underlying data set (pixels) is large and complex. Accurate visual segmentation is usually genre specific and not applicable to any type of content. Correct feature selection can be critical for a successful visual segmentation. 
         [0006]    Videos can also be segmented using the audio content. Low-level acoustic features are extracted from the audio content. The low-level features typically represent periodicity, randomness and spectral characteristics of the audio content. Correlations with known data can then determine optimal thresholds for scene segmentation. 
         [0007]    Most audio content can be classified into small number of audio classes, e.g., speech, music, silence, applause and cheering. 
         [0008]      FIG. 1  shows one typical prior art audio classification method  100 . Audio content  101  is the input to the method  100 . The audio content  101  can be part of a video  103 . The audio content can be synchronized with video content  104 . Audio features  111  are extracted  110  from relatively short frames  102  of the audio content  101 , e.g., the frames are about ten milliseconds. The audio features  111  can have a number of different forms, e.g., modified discrete cosine transforms (MDCTs) or mel-frequency cepstral coefficients (MFCC). 
         [0009]    As also shown in  FIG. 2 , the audio features  111  in each frame are classified with a label to generate a sequence of consecutive labels  121  by a classifier  200 . Each label represents one of the audio classes, e.g., applause, cheering, music, speech, and silence. The classifier  200  has a set of trained classes  210 , e.g., applause, cheering, music, speech, and silence. Each class is modeled by, e.g., a Gaussian mixture model (GMM). The parameters of the GMMs are determined from low-level features extracted from training data  211 . The audio features  111  can be classified by determining  220  a likelihood that the GMMs of the audio features  111  in the content correspond to the GMMs for each trained class. Thus, the labels  121  can be considered time series data that represent a low-low-level temporally evolution of a semantic interpretation of the audio content. 
       SUMMARY OF THE INVENTION 
       [0010]    A method segments a video. Audio frames of the video are classified with labels. Dominant labels are assigned to successive time intervals of consecutive labels. 
         [0011]    A semantic description is constructed for sliding time windows of the successive time intervals, in which the sliding time windows overlap in time, and the semantic description for each time window is a transition matrix determined from the dominant labels of the time intervals. 
         [0012]    A marker is determined from the transition matrices, in which a frequency of occurrence of the marker is between a low frequency threshold and a high frequency threshold. Then, the video is segmented at the locations of the markers 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0013]      FIG. 1  is a flow diagram of a prior art audio classification method; 
           [0014]      FIG. 2  is a block diagram of a prior art audio classifier; 
           [0015]      FIG. 3A  is a flow diagram of an audio segmentation method according to an embodiment of the invention; 
           [0016]      FIG. 3B  is a block diagram of audio content time portions; 
           [0017]      FIGS. 4A and 4B  are examples of an audio semantic description according to an embodiment of the invention; 
           [0018]      FIG. 5  is a timing diagram of unscripted audio scenes boundaries according to an embodiment of the invention; and 
           [0019]      FIG. 6  is a timing diagram of scripted audio scenes boundaries according to an embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0020]    As shown on  FIGS. 3A and 3B , embodiments of our invention provide a method  300  for segmenting video based on audio content  301 . A sequence of consecutive labels l  321  of classified frame of audio content is input to the method. 
         [0021]    We first classify the frames as described above with labels l  311 . Then, we assign a dominant label L  321  to consecutive labels in time intervals  302 . The time intervals are substantially longer than the frames. The dominant label is the most frequently occurring label in the consecutive frames during a one second time interval. 
         [0022]    The dominant labels L  321  are used to construct  400  a semantic description  401  of the audio content of the video. The semantic description  401  can include transition matrices  440  and histograms  430 . The semantic description can be determined for the whole audio content  301  as well as for each time-overlapping window  303 , as shown on  FIG. 3B . That is, each window includes the dominant labels L  321  of the consecutive intervals  302 . The windows are substantially longer, e.g., thirty seconds, than the intervals, and the windows overlap each other in time, e.g., the windows move forward in time by one second. Histograms  430  can be determined from the transition matrices. The total number of labels L  321  is equal to the number of transitions, when self transitions are allowed such as: music→music. 
         [0023]    The semantic description  401  is used to detect  610  a marker  620 , e.g., music that serves to mark a scene transition in a sitcom video. Typically, the marker  620  indicates the start of a new scene or news segment. Usually, markers are present in scripted videos. Examples of scripted content are news, drama, sitcoms, how-to shows, talk shows, etc. In such shows, a scene transition often consists of a slow dissolve accompanied by a characteristic phrase of music. It is this very short piece of music that we call a special transition marker or source. 
         [0024]    If we find a marker, then we use the marker  620  to determine  630  a transition difference  640  for the marker. We determine the transition difference  640  at every time instant t 0  where the marker occurs, as described below. 
         [0025]    After determining  630  the transition difference  640 , we compare  650  the transition difference  640  with a first threshold Th 1 . If the transition difference is greater than the threshold Th 1  and the transition differences is also a local maximum, the corresponding time t 0  indicates a (segmentation) boundary  350 . 
         [0026]    If the marker  620  is not found, which is usually the case for unscripted content, we determine  510  a semantic difference  530  at every time instant t 0  and compare  520  the semantic difference  530  with a second threshold Th 2 . If the semantic difference  530  is greater than the threshold Th 2  and the semantic difference is also a local maximum, the time t 0  indicated the boundary  350 . In either case, the boundaries  350  can be used to segment the video. 
         [0027]    Semantic Description 
         [0028]    As shown on  FIGS. 4A and 4B  for the embodiments of our invention, we use two types of semantic descriptors. The first semantic descriptor includes histograms H(i)  430  for classes i=1, . . . , M. The second semantic descriptor is a transition matrix T(i, j)  440  from class i to class j. Self transitions (i=j) are permitted. The matrices and histograms can be determined for each time window  303 , and for the entire audio content  301 . 
         [0029]    In the preferred embodiment, the values in the histograms and matrices are normalized. As stated above, the histograms H can be derived from the transition matrices T. Therefore generally in the formulations below, the symbol H can be substituted for the symbol T. 
         [0030]    Scene Segmentation 
         [0031]    After studying hours of video with different content such as news, drama, situation comedies, talk show, music TV, and so on, we determine that scene changes can be generalized into two types. 
         [0032]    A first type occurs when the semantic descriptor changes substantially. For this type of content, we use the semantic difference  530  to detect scene boundaries. The second type is indicated by the marker  620 . 
         [0033]    Detecting Semantic Differences 
         [0034]    As shown on  FIG. 5 , we can determine  510  the semantic difference Diff semantic    530  for a window t b  before the time instant t 0  and a window t a  after the time t 0  as 
         [0000]    
       
         
           
             
               
                 Diff 
                 semantic 
               
               = 
               
                 
                   1 
                   2 
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     M 
                   
                    
                   
                     
                       
                         [ 
                         
                           
                             
                               T 
                               a 
                             
                              
                             
                               ( 
                               
                                 i 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               T 
                               b 
                             
                              
                             
                               ( 
                               
                                 i 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                         
                         ] 
                       
                       2 
                     
                     
                       
                         T 
                          
                         
                           ( 
                           
                             i 
                             , 
                             j 
                           
                           ) 
                         
                       
                       + 
                       
                         T 
                          
                         
                           ( 
                           
                             i 
                             , 
                             j 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where T a (i, j) and T b (i, j) are the transition matrices for windows t a  and t b . If Diff semantic  is greater than a threshold Th 2    550 , and also a local maximum  560 , then the time t 0  indicates a boundary  350 . 
         [0035]    Detecting Markers 
         [0036]    The marker is a single label m of the class that occurs throughout the video at a moderate frequency, neither too high nor too low. The marker can be determined from either the transition matrix or the histogram for the entire content. Therefore, the marker satisfies the following frequency constraint, Fr low &lt;T(m,j)&lt;Fr high , where Fr low  is a low frequency threshold, and Fr high  is a high frequency threshold. If the label is relatively frequently occurring, then the corresponding class is probably an integral part of the audio content and cannot be effective as a marker. Similarly, if the label occurs relatively infrequently, it also cannot be effective as a marker. In one embodiment, Fr high  is about one in three, and Fr low  is about one in a hundred. 
         [0037]    As an additional requirement, the label m associated with the marker should be moderately dispersed throughout the video. That is to say, the markers should not all be clumped together around a very small number of time instances. Similarly, the markers should also not be spread out so much that they occur at a large number of separated time instances. This constraint can be expressed as 
         [0000]    
       
         
           
             
               
                 
                   α 
                   1 
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       ≠ 
                       j 
                     
                     
                         
                     
                   
                    
                   
                     T 
                      
                     
                       ( 
                       
                         i 
                         , 
                         j 
                       
                       ) 
                     
                   
                 
               
               &gt; 
               
                 T 
                  
                 
                   ( 
                   
                     m 
                     , 
                     m 
                   
                   ) 
                 
               
               &gt; 
               
                 
                   α 
                   2 
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       ≠ 
                       j 
                     
                     
                         
                     
                   
                    
                   
                     T 
                      
                     
                       ( 
                       
                         i 
                         , 
                         j 
                       
                       ) 
                     
                   
                 
               
             
             , 
             
               where 
                
               
                   
               
                
               
                 
                   ∑ 
                   
                     i 
                     ≠ 
                     j 
                   
                   
                       
                   
                 
                  
                 
                   T 
                    
                   
                     ( 
                     
                       i 
                       , 
                       j 
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    counts all transitions non self transitions, i.e., i≠j, T(m, m) counts self transitions for the marker label, α 1  is maximum dispersion coefficient, and α 2  is minimum dispersion coefficient. In one embodiment, we select α 1 =5.0, and α 2 =1.5. 
         [0038]    After determining a marker m, we can determine a transition matrix T m  for a time period t m , associated with the marker, see  FIG. 6 . In one embodiment, t m  is 0.5 second. 
         [0039]    In one embodiment, the markers can be used as approximate boundaries. A more accurate estimate of the boundaries can be obtained by measuring the transition difference for the time spans t b  before the current time instant t 0  and for the time spans t a  after the timer t 0  for time span t c : 
         [0000]    
       
         
           
             
               
                 Diff 
                 transition 
               
               = 
               
                 
                   
                     
                       T 
                       m 
                     
                      
                     
                       ( 
                       
                         
                           i 
                           m 
                         
                         , 
                         j 
                       
                       ) 
                     
                   
                   × 
                   
                     t 
                     m 
                   
                 
                 
                   
                     
                       
                         T 
                         b 
                       
                        
                       
                         ( 
                         
                           
                             i 
                             m 
                           
                           , 
                           j 
                         
                         ) 
                       
                     
                     × 
                     
                       t 
                       b 
                     
                   
                   + 
                   
                     
                       
                         T 
                         a 
                       
                        
                       
                         ( 
                         
                           
                             i 
                             m 
                           
                           , 
                           j 
                         
                         ) 
                       
                     
                     × 
                     
                       t 
                       a 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where T a , T b , and T m  are the transition matrices for time periods t a , t b , and t m , respectively. When Diff transition  is greater than the threshold Th 1 , and also is a local maximum, the corresponding time t 0  is a boundary. Essentially, this attempts to locate the center of a clump of markers that are substantially temporally adjacent. 
         [0040]    Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.