Abstract:
One embodiment of the present invention provides a computer-based system that automatically characterizes a video. During operation, the system extracts feature vectors from sampled frames in the video. Next, the system uses the extracted feature vectors for successive sampled frames in the video to define a curve. The system then determines a set of invariants for the curve. Next, the system using the set of invariants to characterize the video. The system can then use the characterization of the video to perform various operations, such as classifying the video with respect to other videos or detecting duplicates of the video.

Description:
RELATED APPLICATION 
     The subject matter of this application is related to the subject matter in a co-pending non-provisional application by the same inventor as the instant application entitled, “Method and Apparatus for Automatically Summarizing Video,” having Ser. No. 11/454,386, and filing date 15 Jun. 2006 . 
     BACKGROUND 
     1. Field of the Invention 
     The present invention relates computer-based techniques for manipulating video data. More specifically, the present invention relates to a computer-based technique for automatically characterizing a video using “curve invariants,” wherein the curve invariants are associated with a curve defined by features for successive sampled frames in the video. 
     2. Related Art 
     The recent proliferation of high-bandwidth Internet connections and associated developments in content-distribution technologies presently make it possible for millions of users to efficiently access video content on the Internet. These developments have led to a tremendous increase in the amount of video content that is being downloaded from the Internet. Internet users routinely view video clips from numerous web sites and portals to obtain various types of information and entertainment. At the same time, a number of video-sharing web sites have been recently launched, which are dedicated to sharing and distributing video clips. Some of these video-sharing web sites are being accessed by millions users each day. 
     In order to access large numbers of video clips, it is advantageous for the users to be able to characterize the video clips to facilitate classifying the video clips (for example by genre) or to detect duplicate video clips (which is useful for detecting copyright violations). Unfortunately, no mechanisms are presently available to automatically characterize and classify videos. Hence, users must manually characterize and classify videos, which is an extremely labor-intensive proposition for the millions of video clips which are accessible through the Internet. 
     Hence, what is needed is a method and an apparatus for automatically characterizing a video without the above-described problems. 
     SUMMARY 
     One embodiment of the present invention provides a computer-based system that automatically characterizes a video. During operation, the system extracts feature vectors from sampled frames in the video. Next, the system uses the extracted feature vectors for successive sampled frames in the video to define a curve. The system then determines a set of invariants for the curve. Next, the system using the set of invariants to characterize the video. The system can then use the characterization of the video to perform various operations, such as classifying the video with respect to other videos or detecting duplicates of the video. 
     In a variation on this embodiment, extracting a feature vector for a sampled frame in the video involves producing a color histogram for the sampled frame. 
     In a variation on this embodiment, prior to using the feature vectors to define a curve, the system maps the feature vectors from a higher-dimensional space to a lower-dimensional space. This mapping can involve using a multi-dimensional scaling (MDS) technique, or a principal component analysis (PCA) technique. 
     In a variation on this embodiment, the invariants for the curve include knot invariants. 
     In a further variation, the knot invariants include Vassiliev invariants. 
     In a further variation, the curve is a closed curve. In this variation, determining the set of invariants involves using a Gauss integral formulation of Vassiliev knot invariants to calculate a writhe of the closed curve. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         FIG. 1  presents a flow diagram illustrating the process of characterizing a video in accordance with an embodiment of the present invention. 
         FIG. 2  illustrates a system for characterizing a video in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the claims. 
     The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, volatile memory, non-volatile memory, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs), DVDs (digital versatile discs or digital video discs), or other media capable of storing computer readable media now known or later developed. 
     Characterizing a Video 
       FIG. 1  presents a flow diagram illustrating the process of characterizing a video in accordance with an embodiment of the present invention. This system starts by receiving the video  102 , which is comprised of a number of image frames. 
     Next, a sampling mechanism  108  samples frames from video  102 . For example, sampling mechanism  108  may sample every 30 th  frame. 
     These sampled frames feed into feature-extraction mechanism  110 , which extracts a “feature” for each sampled frame. For example, in one embodiment of the present invention, feature-extraction mechanism  110  partitions a frame into a 4×6 array of tiles and the system extracts color histogram features for each of these tiles. The histogram provides 8 bits for each color, making the total feature vector length 4×6×8×8×8=12288. (Note that the terms “feature” and “feature vector” are used interchangeably throughout this specification.) 
     Although this disclosure describes an implementation which uses features associated with tiles, the present invention is not limited to using features associated with tiles. In general, the present invention can be used with any type of image feature. For example, the present invention can be used with DCT coefficients for images. (For more information in DCT coefficients for images, please see, R. C. Reininger and J. D. Gibson, “Distributions of the Two-Dimensional DCT Coefficients for Images,”  IEEE Transactions on Communications COM -31, 6 (1983), pp. 835-839, which is hereby incorporated by reference.) In another example, image features can be Gabor Wavelets. (For more information on Gabor Wavelets for images, please see, T. S. Lee, “Image Representation Using 2D Gabor Wavelets,”  IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 18. no. 10, pp. 959-971, 1996, which is hereby incorporated by reference.) In yet another example, image features can be local features defined in terms of points-of-interest and associated descriptors. (For more information these types of local features, please see C. Schmid, G. Dorko, S. Lazebnik, K. Mikolajczyk, and J. Ponce, “Pattern Recognition with Local Invariant Features,”  Handbook of Pattern Recognition and Computer Vision,  3 rd edition , C. H. Chen and P. S. P Wang editors, World Scientific Publishing Co., 2005, which is hereby incorporated by reference.) 
     Next, a mapping mechanism  112  maps the features from a higher-dimensional space to a lower dimensional space to produce a set of dimension-reduced features. For example, in one embodiment of the present invention, the system maps the color histogram feature vectors described above into feature vectors in a three-dimensional space. As mentioned above, this mapping can involve using a number of different techniques, such as the multi-dimensional scaling (MDS) technique, or the principal component analysis (PCA) technique. For a further description of the MDS technique, please see T. Cox and M. Cox, “Multidimensional Scaling,” 2 nd  Ed., Chapman &amp; Hall/CRC, 2001, which is hereby incorporated by reference. For a further description of the PCA technique, please see the Wikipedia entry for “PCA technique” retrieved from the Wikipedia web site on 7 Aug. 2006, which is hereby incorporated by reference. 
     Next, a curve-defining mechanism  116  uses the features for successive sampled frames in the video to define a closed curve  118 . This can involve linking the features for successive sampled frames, either using line segments or interpolated curves. Next, the system closes the curve by linking the feature for the last sampled frame to the feature for the first sampled frame. At this point, the video is effectively modeled as a closed curve which evolves over time through a multi-dimensional space. 
     Then system then uses an invariant-determining mechanism  120  to determine a set of invariants  122  for the closed curve. One embodiment of the present invention uses a Gauss integral formulation of Vassiliev knot invariants to calculate a “writhe” of the closed curve. For example, see P. Røgen and B. Fain, “Automatic Classification of Protein Structure by Using Gauss Integrals,”  Proceedings of the National Academy of Sciences,  7 Jan. 2003, vol. 100, No. 1, pp. 119-124 (hereinafter referred to as “Røgen”), which is hereby incorporated by reference. 
     A “writhe” as “a property of a 2-dimensional representation of a knot or link.” More specifically, the writhe of a knot or line “is the total number of positive crossings minus the total number of negative crossings. Crossings are classed as positive or negative by assigning an orientation to the knot. That is, a direction is assigned to the knot at a point and this direction is followed all the way around the knot. If as you travel along the knot and cross over a crossing, the strand underneath goes from right to left, the crossing is positive; if the lower strand goes from left to right, the crossing is negative” (see the definition of “writhe” in Wikipedia). 
     One embodiment of the present invention calculates the writhe of the closed curve using the technique described in Røgen. More specifically, Appendix A of Røgen states that “the writhe, Wr, of a space curve, γ, may be calculated by using the Gauss integral 
     
       
         
           
             
               Wr 
               ⁡ 
               
                 ( 
                 γ 
                 ) 
               
             
             = 
             
               
                 1 
                 
                   4 
                   ⁢ 
                   π 
                 
               
               ⁢ 
               
                 
                   ∫ 
                   
                     γ 
                     × 
                     
                       γ 
                       ⁢ 
                       \ 
                       ⁢ 
                       D 
                     
                   
                 
                 ⁢ 
                 
                   
                     ∫ 
                     
                         
                     
                   
                   ⁢ 
                   
                     
                       ω 
                       ⁡ 
                       
                         ( 
                         
                           
                             T 
                             1 
                           
                           , 
                           
                             t 
                             2 
                           
                         
                         ) 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ⅆ 
                       
                         t 
                         1 
                       
                     
                     ⁢ 
                     
                       ⅆ 
                       
                         t 
                         2 
                       
                     
                   
                 
               
             
           
         
       
     
     where w(t 1 , t 2 )=[γ′(t 1 ), γ(t 1 )−γ(t 2 ), γ′(t 2 )]|γ(t 1 )−γ(t 2 )| 3 , where D is the diagonal of γ×γ, and [γ′(t 1 ), γ(t 1 )−γ(t 2 ), γ′(t 2 )] is the triple scalar product. As ω(t 1 , t 2 )=ω(t 2 ,t 1 ), the writhe may be calculated as an integral over a 2-simplex, namely 
     
       
         
           
             
               
                 I 
                 
                   ( 
                   
                     1 
                     , 
                     2 
                   
                   ) 
                 
               
               ⁡ 
               
                 ( 
                 γ 
                 ) 
               
             
             = 
             
               
                 Wr 
                 ⁡ 
                 
                   ( 
                   γ 
                   ) 
                 
               
               = 
               
                 
                   1 
                   
                     2 
                     ⁢ 
                     π 
                   
                 
                 ⁢ 
                 
                   
                     ∫ 
                     
                       0 
                       ⁢ 
                       
                           
                       
                       &lt; 
                       
                         t 
                         1 
                       
                       &lt; 
                       
                         t 
                         2 
                       
                       &lt; 
                       L 
                     
                   
                   ⁢ 
                   
                     ∫ 
                     
                       
                         ω 
                         ⁡ 
                         
                           ( 
                           
                             
                               t 
                               1 
                             
                             , 
                             
                               t 
                               2 
                             
                           
                           ) 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ⅆ 
                         
                           t 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           ⅆ 
                           
                             t 
                             2 
                           
                         
                         . 
                       
                     
                   
                 
               
             
           
         
       
     
     For a polygonal curve μ the natural definition of writhe is, 
                   I     (     1   ,   2     )       ⁡     (   μ   )       =       Wr   ⁡     (   μ   )       =       ∑     0   &lt;     i   1     &lt;     i   2     &lt;   N               ⁢           ⁢     W   ⁡     (       i   1     ,     i   2       )             ,         
with
 
               W   ⁡     (       i   1     ,     i   2       )       =       1     2   ⁢   π       ⁢       ∫       i   1     =           ⁢     t   1           i   1     +   1       ⁢       ∫       i   2     =     t   2           i   2     +   1       ⁢       w   ⁡     (       t   1     ,     t   2       )       ⁢           ⁢     ⅆ     t   1       ⁢     ⅆ     t   2                     
where W(i 1 , i 2 ) is the contribution to writhe coming from the i 1 th and the i 2 th line segments, which equals the probability from an arbitrary direction to see the i 1 th and the i 2 th line segment cross, multiplied by the sign of this crossing. Therefore, geometrically writhe is still the signed average number of crossings averaged over the observer&#39;s position located in all space directions. The unsigned average number of crossings seen from all directions, known as the average crossing number, is
 
     
       
         
           
             
               
                 
                   
                     
                       I 
                       
                          
                         
                           1 
                           , 
                           2 
                         
                          
                       
                     
                     ⁡ 
                     
                       ( 
                       μ 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         0 
                         &lt; 
                         
                           i 
                           1 
                         
                         &lt; 
                         
                           i 
                           2 
                         
                         &lt; 
                         N 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                          
                         
                           W 
                           ⁡ 
                           
                             ( 
                             
                               
                                 i 
                                 1 
                               
                               , 
                               
                                 i 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   A 
                   ) 
                 
               
             
           
         
       
     
     A whole family of structural measures containing, e.g., 
                       I            1   ,   3          ⁢     (     2   ,   4     )         ⁡     (   μ   )       =       ∑     0   &lt;     i   1     &lt;     i   2     &lt;     i   3     &lt;       i   4     ⁢   N                 ⁢           ⁢            W   ⁡     (       i   1     ⁢     i   3       )            ⁢     W   ⁡     (       i   2     ,     i   4       )                   (   B   )               
and
 
                       I       (     1   ,   5     )     ⁢     (     2   ,   4     )     ⁢     (     3   ,   6     )         ⁡     (   μ   )       =       ∑     0   &lt;     i   1     &lt;     i   2     &lt;     i   3     &lt;     i   4     &lt;     i   5     &lt;     i   6     &lt;   N               ⁢           ⁢       W   ⁡     (       i   1     ,     i   5       )       ⁢     W   ⁡     (       i   2     ,     i   4       )       ⁢     W   ⁡     (       i   3     ,     i   6       )                   (   C   )               
may be constructed by using writhe and average crossing number as the basic building blocks.” These measures are inspired by integral formulas for the Vassiliev knot invariants (see X. S. Lin and Z. Wang, “Integral Geometry of Plane Curves and Knot invariants,”  Journal of Differential Geometry,  44 (1996), pp. 74-95). The invariants from the above equations form a natural progression of descriptors of curves, much as moments of inertia and their correlations describe solids. Furthermore, note that there is a notion of “order” to these descriptors. For example, the above equations (A), (B) and (C) are first, second and third order descriptors, respectively. Such descriptors can be used to form the set of invariants  122 .
 
     After the set of invariants  122  is determined, the set of invariants  122  can be used to perform a number of different operations. For example, a duplicate detector  123  can attempt to match the set of invariants with similarly computed invariants for other videos in an attempt to detect duplicate video, which can be useful for detecting copyright violations. 
     In another example, the set of invariants  122  can be fed into a classifier  124 , which can be used to classify the video with respect to other videos. Note that there exist a large number of well-known classification techniques and any one of these classification techniques may be used to classify video  102 . 
     In one embodiment of the present invention, classifier  124  classifies videos into different “genres.” This classification into genres can be accomplished using any one of a number of well-known classification techniques. For example, a nearest-neighbor classification technique can be used to cluster videos into genres. (For more details on nearest-neighbor classifiers, please see D. B. Skalak, “Prototype Selection for Composite Nearest Neighbor Classifiers,” Ph.D. thesis, Department of Computer Science, University of Massachusetts, 1996, which is hereby incorporated by reference.) In another example, support-vector machine (SVM) classifiers can be used to classify videos into genres. (For more details on SVM classifiers, please see R. Santiago-Mozos, J. M. Leiva-Murillo, F. Perez-Cruz, and A. Artes-Rodriguez, “Supervised-PCA and SVM Classifiers for Object Detection in Infrared Images,”  IEEE Conference on Advanced Video and Signal Based Surveillance , which is hereby incorporated by reference.) In yet another example, a Gaussian-Mixture model can be used the classify videos into genres. (For more details on using a Gaussian-Mixture model, please see H. Permuter, J. M. Francos and I. H. Jermyn, “A Study of Gaussian Mixture Models of Colour and Texture Features for Image Classification and Segmentation,”  Pattern Recognition,  2005, which is hereby incorporated by reference.) 
     System 
       FIG. 2  illustrates a computer-based system for characterizing a video in accordance with an embodiment of the present invention. This computer-based system operates within a computer system  200 , which can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance. 
     As is illustrated in  FIG. 2 , computer system  200  includes a number of software modules that implement: sampling mechanism  108 , feature-extraction mechanism  110 , mapping mechanism  112 , curve-defining mechanism  116 , invariant-determining mechanism  120 , duplicate detector  123  and classifier  124 . These mechanisms operate collectively to produce a signature, which comprises the set of invariants  122  of the curve which is defined by successive sampled frames in video  102 . 
     The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.