Abstract:
A method is provided to automatically determine “exciting” segments from a video. The method includes calculating image features of each frame in the video, determining a difference for each pair of adjacent frames, calculating a sum of differences for each group of frames in the video, and selecting a number of the groups with high sums as exciting segments of the video. The differences between pairs of adjacent frames are used as a criterion for measuring a degree of “excitement” for determining the highlights in the video.

Description:
FIELD OF INVENTION 
       [0001]    This invention relates to a method that automatically selects exciting segments from a video. 
       DESCRIPTION OF RELATED ART 
       [0002]    When a video is received, a user may wish to preview “exciting” segments from the video. Thus, what is needed is a method to automatically determine exciting segments from a given video. 
       SUMMARY 
       [0003]    In one embodiment of the invention, a method is provided to automatically determine “exciting” segments from a video. The method includes determining a difference for each pair of adjacent frames. The differences between pairs of adjacent frames are used as a criterion for measuring a degree of “excitement” for determining the highlights in the video. The method further includes calculating a sum of differences for each group of frames in the video, and selecting a number of groups with high sums as the exciting segments of the video. 
         [0004]    In one embodiment, the differences between pairs of adjacent frames are based on an image feature that is the histogram mapping the number of pixels that fall into bins of various feature values, and the feature value of a pixel is based on the color component values of the pixel. In one embodiment, two of the selected groups are combined to form a new selected group when they overlap. In another embodiment, two of the selected groups are combined to form a new selected group when they are closer than a threshold interval and the image feature difference between the last frame of the preceding group and the first frame of the subsequent group is smaller than a threshold image feature difference. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]      FIGS. 1A and 1B  are a flowchart of a method to automatically determine highlight clips from a video in one embodiment of the invention. 
           [0006]      FIG. 2  is a graph of the difference between each frame and a preceding frame in a video in one embodiment of the invention. 
           [0007]      FIG. 3  is another graph of the difference between each frame and a preceding frame in another video in one embodiment of the invention. 
       
    
    
       [0008]    Use of the same reference numbers in different figures indicates similar or identical elements. 
       DETAILED DESCRIPTION OF THE INVENTION 
       [0009]      FIGS. 1A and 1B  are a flowchart of a method  100  for automatically determining exciting segments in a video in one embodiment of the invention. Method  100  is implemented as software executed by a processor in a computer. Alternatively, method  100  may be implemented as software executed by a processor in a video player, completely in hardware, or other techniques known to one skilled in the art. As an example, assume the video has a length of N seconds. The user may be asked to provide a maximum length of M (≦N) seconds for the exciting segments or otherwise a default value is used. 
         [0010]    In general, the exciting segments should not be too short or otherwise they will give an overly choppy visual impression. The user may be asked to provide a minimum unit length (minThre) for the exciting segments or otherwise a default value is used. 
         [0011]    In step  102  ( FIG. 1A ), the processor reads the content of an i th  frame of the video where “i” is an integer initialized at 1. Typically the video is read from a nonvolatile memory such as a disk drive, an optical disk, or a memory card. 
         [0012]    In step  104 , the processor calculates an image feature feature[i] that characterizes the current frame. Image feature feature[i] is a histogram of the distribution of a characteristic value y of each pixel in the frame. In one embodiment, characteristic value y is a 9-bit binary number that contains the three most significant bits of the red, the green, and the blue 8-bit color components of the pixels. 
         [0013]    The processor generates the characteristic value y as follows: 
         [0000]        y =(( b&gt;&gt; 5)&lt;&lt;6)+(( g&gt;&gt; 5)&lt;&lt;3)+( r&gt;&gt; 5), or  (1.0) 
         [0000]      y=b8b7b6g8g7g6r8r7r6,  (1.1) 
         [0000]    where “r” is the red color component of the pixel, “g” is the green color component of the pixel, “b” is the blue color component of the pixel, “&gt;&gt;” is an arithmetic right shift operation, “&lt;&lt;” is an arithmetic left shift operation, b 8 , b 7 , and b 6  are the most significant bits of the blue color component, g 8 , g 7 , and g 6  are the most significant bits of the green color component, and r 8 , r 7 , and r 6  are the most significant bits of the red color component. The processor next generates the image feature feature[i] as follows: 
         [0000]      feature[i]={f[0],f[1], . . . , f[511]},  (2.0) 
         [0000]    where f[k] is the number of pixels with characteristic value y value of k 
         [0014]    In step  106 , the processor calculates an image feature difference Diff[i] between the current frame and a preceding frame as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           Diff 
                            
                           
                             [ 
                             i 
                             ] 
                           
                         
                         = 
                           
                          
                         
                            
                           
                             
                               feature 
                                
                               
                                 [ 
                                 i 
                                 ] 
                               
                             
                             - 
                             
                               feature 
                                
                               
                                 [ 
                                 
                                   i 
                                   - 
                                   1 
                                 
                                 ] 
                               
                             
                           
                            
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                            
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 0 
                               
                               511 
                             
                              
                             
                                
                               
                                 
                                   
                                     feature 
                                      
                                     
                                       [ 
                                       i 
                                       ] 
                                     
                                   
                                   · 
                                   
                                     f 
                                      
                                     
                                       [ 
                                       k 
                                       ] 
                                     
                                   
                                 
                                 - 
                                 
                                   
                                     feature 
                                      
                                     
                                       [ 
                                       
                                         i 
                                         - 
                                         1 
                                       
                                       ] 
                                     
                                   
                                   · 
                                   
                                     f 
                                      
                                     
                                       [ 
                                       k 
                                       ] 
                                     
                                   
                                 
                               
                                
                             
                           
                         
                         , 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3.0 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where feature[i] is the histogram of the current frame, feature[i−1] is the histogram of the preceding frame, feature[i]·f[k] is the number of pixels with y value of k in the current frame, and feature[i−1]·f[k] is the number of pixels with y value of k in the preceding frame. Note that Dif[ 1 ] is defined as 0 if there is no preceding frame. 
         [0015]    Referring to  FIG. 2 , an exemplary graph  200  shows a plot  202  of the image feature difference Diff[i] along a sequence of frames in one video. Similarly,  FIG. 3  shows another exemplary graph  300  with a plot  302  of the image feature difference Diff[i] along a sequence of frames in another video. 
         [0016]    Referring back to  FIG. 1A , in step  108 , the processor determines if it has processed the last frame in the video. If not, then the processor increments integer i and proceeds to step  102 . When the processor determines it has processed the last frame in the video, the processor proceeds to step  110 . 
         [0017]    In step  110 , the processor reads the image feature difference Diff[i] values for all the frames in an i th  group of frames where “i” is an integer initialized to 1 (remember from above that Diff[ 1 ] is defined as 0 if there is no preceding frame). The group starts at the i th  frame in the video and includes a minimum number (minF) of frames. The processor determines the minimum number of frames from the user provided or default minimum unit time length (minThre) and the frame rate of the video. 
         [0018]    In step  112 , the processor determines the sum of all the image feature difference Diff[i] values for the frames in the current group as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       Unit 
                        
                       
                         [ 
                         i 
                         ] 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           i 
                         
                         
                           i 
                           + 
                           
                             min 
                              
                             
                                 
                             
                              
                             F 
                           
                         
                       
                        
                       
                         Diff 
                          
                         
                           [ 
                           j 
                           ] 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4.0 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Unit[i] is the sum of all the feature image difference Diff[j] in the i th  group. 
         [0019]    In step  114 , the processor determines if it has processed the last group of frames in the video. If not, then the processor increments integer i and proceeds to step  110 . When the processor determines it has processed the last group of frames in the video, the processor proceeds to step  116 . 
         [0020]    In step  116  ( FIG. 1B ), the processor ranks the sums Unit[i] of the groups of frames from high to low. From the ranking, the processor selects a set of groups that have a comparatively high degree of “excitement.” For example, in  FIG. 2 , boxes  204 ,  206 , and  208  identify three groups having the highest Unit[i] values. Similarly, in  FIG. 3 , boxes  304 ,  306 ,  308 , and  310  identify four selected groups having the highest Unit[i] values. 
         [0021]    Referring back to  FIG. 1B , in step  118 , the processor adds groups of frames one at a time to an exciting segment list based on high to low ranking determined in step  116 . 
         [0022]    In step  120 , the processor determines if the newly added group overlaps the preceding group in the exciting segment list. If so, then step  120  is followed by step  122 . When the adjacent groups do not overlap, then step  120  is followed by step  124 . Note that this step is not performed for the first group since it does not have a preceding group. 
         [0023]    In step  122 , the processor combines the two groups to form a new group, and replaces the two groups in the exciting segment list with the new group. For example, referring to  FIG. 3 , the processor combines groups  304  and  306  to form a new group. Step  122  is followed by step  124 . 
         [0024]    In step  124 , the processor determines if the newly added group and the preceding group in the exciting segment list are separated by an interval less than a predetermined interval threshold, and have an image difference Diff between the last image in the preceding group and the first image in the newly added group less than a predetermined image difference threshold. If so, then step  124  is followed by step  126 . When the adjacent groups do not meet the two criteria, then step  124  is followed by step  128 . Note that this step is not performed for the first group since it does not have a preceding group. 
         [0025]    In step  126 , the processor combines the two groups and includes the frames between the two groups to form a new group, and replaces the two groups in the exciting segment list with the new group. For example, referring to  FIG. 3 , the processor combines groups  306  and  308  to form a new group. Step  126  is followed by step  128 . 
         [0026]    In step  128 , the processor determines if the total length of the exciting segments in the exciting segment list is greater than the user provided or default length M. If not, then step  128  is followed by step  118  where another group is added to the exciting segment list and the above steps are repeated. When the length of the exciting segment formed by the group of frames in the exciting segment list is greater than the user provided or default length M, the process may optionally revert to the previous exciting segment list, and step  128  is then followed by step  130 . 
         [0027]    In step  130 , the processor displays the result to the user. The processor can automatically play back one or more of the exciting segments in the excitement segment list. Alternatively, the processor can display thumbnails of the exciting segments and play back one of the exciting segment selected by the user. 
         [0028]    Various other adaptations and combinations of features of the embodiments disclosed are within the scope of the invention. As described above, there are other ways to measure image feature differences between adjacent frames that accurately reflect the variability of frame contents. For example, the image feature difference can be defined as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       Diff 
                        
                       
                         [ 
                         k 
                         ] 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         W 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             1 
                           
                           H 
                         
                          
                         
                            
                           
                             
                               color 
                                
                               
                                 ( 
                                 
                                   
                                     p 
                                     k 
                                   
                                    
                                   
                                     ( 
                                     
                                       i 
                                       , 
                                       j 
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                             - 
                             
                               color 
                               ( 
                               
                                 
                                   p 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     i 
                                     , 
                                     j 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                            
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   5.0 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where W and H are the width and the height of video frame, color is the vector (r,g,b) mad eup of the components of a pixel, color(p k (i, j)) is the color of the pixel located (i,j) on the k th  frame, and color(p k-1 (i, j)) is the color of the pixel located (i,j) on the preceding k−1 th  frame. In equation 5.0, the characteristic value of each pixel is simply the color of the pixel. Numerous embodiments are encompassed by the following claims.