Abstract:
In an embodiment, the present invention relates to a method for semantic analysis of digital multimedia. In an embodiment of the invention, low level features are extracted representative of one or more concepts. A discriminative classifier is trained using these low level features. A collective annotation model is built based on the discriminative classifiers. In various embodiments of the invention, the frame work is totally generic and can be applied with any number of low-level features or discriminative classifiers. Further, the analysis makes no domain specific assumptions, and can be applied to activity analysis or other scenarios without modification. The framework admits the inclusion of a broad class of potential functions, hence enabling multi-modal analysis and the fusion of heterogeneous information sources.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to a method for automatic annotation of digital media. 
         [0003]    2. Description of Related Art 
         [0004]    Substantial current multimedia analysis research focuses on information retrieval for video content. Companies such as Yahoo! and Google are extending their text-based search capabilities to video data. The applicability of these systems for content indexing is often limited to video with available time-aligned text, or relies on the link structure and text of web pages containing the videos. Video retrieval has also been the focus of the highly successful TRECVID workshops (P. Over, T. Ianeva, W. Kraaij, A. Smeaton, TRECVID 2005“An Overview”,  Proc. TRECVID  2005, http://www.nlpir.nist.gove/projects/tvpubs/tv5.papers/tv5overview.pdf last visited Nov. 1, 2006). In the TRECVID evaluations, the use of visual information is emphasized, however extracting semantics from visual data in the absence of textual descriptors remains a major open problem. 
         [0005]    Recent work to address this semantic gap has been concentrated on ontology-based approaches to semantic feature extraction. (A. Hauptmann. Towards a large scale concept ontology for broadcast video, in  Proc. Of the Third Conf. on Image and Video Retrieval ser. Lecture Notes in Computer Science, vol. 3115. Springer, pp. 674-675, 2004 and L. Hollink, M. Worring, and G. Schreiber, Building a visual ontology for video retrieval in  MULTIMEDIA &#39; 05 : Proceedings of the  13 th annual ACM international conference on Multimedia . ACM Press, 2005). In the ontology-based approaches, a “basis” set of binary classifiers are built to determine if a video shot exhibits a specific semantic feature. These classification outputs are combined statistically to provide higher-level analysis and enhance indexing and retrieval. Many of these approaches operate at the shot-level following an initial segmentation. This is desirable for computational efficiency, dynamic analysis of local sets of frames, and for extraction of semantic features that exhibit some temporal duration. 
         [0006]    Manual tags are now proliferating on various shared video and image data sites such as Flickr and You Tube. While this information is of tremendous value for video indexing, including for refining and training automatic systems, it also exhibits a number of shortcomings. For example, lengthy videos can have tags that apply only to a small (sometimes unidentified) portion of the video. Also, the classic problems of polysemy and synonymy described in the text categorization context are inherited in aggregating tag data for multimedia categorization (M. W. Berry, S. T. Dumais, and G. W. O&#39;Brien, “Using linear algebra for intelligent information retrieval”,  SIAM Review  37(4):573-595, 1995). 
       SUMMARY OF THE INVENTION 
       [0007]    The goal to detect semantic attributes or concepts in clips of video via analysis of a single keyframe or set of frames. The proposed methods integrate high performance discriminative single concept detectors in a random field model for collective multiple concept detection. Furthermore, a generic framework is provided for semantic media classification capable of capturing arbitrary complex dependencies between the semantic concepts. 
         [0008]    Although, the system described herein have been tested with video frames, the system is broadly applicable to other types of multimedia content. 
         [0009]    In an embodiment of the invention, semi-automatic interfaces for identifying concepts are enabled. For example, given a collection of photos or videos, the invention can recommend a set of concepts as a rank list for a user to select from. This list could come from other users&#39; tags, or a pre-existing collection of tagged data. In aggregating tagged data (e.g. Flickr), the invention can help cluster similar tags or help resolve ambiguities in the tags (e.g., polysemy). 
         [0010]    The problem addressed here is the automatic annotation of segmented video using a set of binary attributes. These attributes are referred to as concepts, and the more general problem as concept detection. The system is able to detect the presence/absence of a set of concepts by exploiting concept interdependence. 
         [0011]    In an embodiment of the invention, a method of identifying concept(s) in digital multimedia includes extracting low level features representative of the one or more concept which are used to train a discriminative classifier for each concept, where the discriminative classifier(s) are combined to build a collective annotation model. Further, a set of interaction potentials is defined to identify related concepts in the multimedia. Using the collective annotation model and the interaction potentials the concept(s) can be identified. 
         [0012]    This summary is not intended to be a complete description of, or limit the scope of, the invention. Alternative and additional features and aspects of the invention can be obtained from a review of the specification, the figures, and the claims. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0013]    Preferred embodiments of the present invention will be described in detail based on the following figures, wherein: 
           [0014]      FIG. 1A  shows an example of graphical models used for detecting four concepts where the model depicts independent classification; 
           [0015]      FIG. 1B  shows an example of graphical models used for detecting four concepts where the model depicts collective classification; 
           [0016]      FIG. 2A  shows experimental results comparing various system variants for the ‘5 concept ’ graph; 
           [0017]      FIG. 2B  shows experimental results comparing various system variants for the ‘11 concept’ graph; 
           [0018]      FIG. 3  illustrates a block diagram for training the semantic analysis model to determine whether the concept(s) are present on a labeled set of media in accordance with the present invention; and 
           [0019]      FIG. 4  illustrates a block diagram for testing the semantic analysis invention for detecting trained concepts using media in accordance with the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0020]    To supply consistent and reliable annotations for indexing or metadata creation, a semiautomatic approach is required. Manual annotation is not feasible on the scale of legacy assets, let alone for the ever increasing amounts of newly produced content. Automatic techniques that are scalable can accommodate the quantity of the data, but the quality of automatic annotations is not sufficient. Several requirements can be identified for the analysis components of an ideal media annotation system: 
         [0021]    the ability to integrate heterogeneous modalities in a common framework. 
         [0022]    the ability to supply a confidence measure or ranking associated with annotations, where such measures can be time-varying. 
         [0023]    a fully automatic mode for annotating either archival data, or data for which tag information, text transcripts, or web page link structure is absent. 
         [0024]    a semi-automatic mode, for manually revising automatic results as needed, leveraging confidence measures. 
         [0025]    the ability to reconcile or cluster tags used to denote similar concepts by different users, leveraging label rankings and co-occurrence. 
       Definitions 
       [0026]    A ‘tag’ or an ‘annotation’ is used to describe text that is manually or otherwise associated with multimedia data though not generated with an embodiment of the invention. However, a tag or an annotation may be aggregated or reclassified with an embodiment of the invention. 
         [0027]    A ‘concept’ is used to describe text associated with multimedia data that is semi-automatically or automatically generated with an embodiment of the invention. 
         [0028]    A‘confidence measure’ is derived from the probability of encountering a concept as specified by the model. 
         [0029]    A ‘ranking’ is derived form the confidence measure. 
       2.1 Feature Extractions 
       [0030]    In the first processing step, low-level feature data can be extracted. In our case, the source video is segmented according to shots, and keyframes are identified within each shot. The keyframes are processed to extract low-level feature data. This data may include visual features such as color histograms, texture or edge features, motion analysis or face detection output. If time-aligned text data is present, standard low-level text features such as word counts or tf/idf features can also be included. The specific set of features used is not critical. In the multi-modality case, early or late fusion approaches can be used to construct the single concept classifiers (C. Snoek, M. Worring, and A. W. Smeulders. Early versus late fusion in semantic video analysis.  Proceedings of the  13 th Annual ACM international Conference on Multimedia . ACM Press, New York, N.Y., 399-402, 2005). 
       2.2 Independent Concept Detection 
       [0031]    In the second step, a discriminative classifier is trained for each concept using a labeled training act of low-level features. For some time, Support Vector Machines (SVM) have been the preferred classifer. The output of each SVM is transformed to a probability using a logistic mapping, and this provides a baseline system for independent concept detection. 
         [0032]    In the experiments below, the publicly available low-level features (see J. van Gemert, J.-M. Geusebroek, C. Veenman, C. Snoek, and A. Smeulders. Robust Seene Categorization by Learning Image Statistics in Context. To appear,  Proceedings of IEEE CVPR,  2006) and SVM outputs provided by the Media Mill team are utilized (C. Snoek, M. Worring, J. van Gemert, J.-M. Geusebroek, and A. Smeulders. “The Challenge Problem for Automated Detection of 101 Semantic Concepts in Multimedia”,  Proceedings of ACM Multimedia,  2006). These SVM outputs are highly optimized using a computationally intensive grid search for classification parameters on a per concept basis. As such, these outputs represent an extremely competitive baseline system that outperformed all of our systems submitted in the 2005 evaluation in the experiments below. 
         [0033]    The graphical model corresponding to this approach appears in  FIG. 1A . Graphical models corresponding to the collective annotation methods presented herein appear in  FIG. 1B . Probabilistically, if the i th  concept in the concept set C is denoted by the binary random variable Y i then 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                     
                      
                     Y 
                      
                     
                        
                       X 
                       ) 
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         i 
                         ∈ 
                         C 
                       
                       
                           
                       
                     
                      
                     
                         
                     
                      
                     
                       P 
                       ( 
                       
                         
                           Y 
                           i 
                         
                          
                         
                            
                           X 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     1 
                     ) 
                   
                 
               
             
           
         
       
     
       2.3 Modeling Concept Co-occurrence 
       [0034]    A collective annotation model can be based on the single concept discriminative models described in the previous section. Our first approach extends the discriminative random field (DRF) model of Kumar and Hebert (S. Kumar and M. Hebert. It is noted, that the term “based on” as used herein, means “based at least in part on”, unless otherwise specified. Discriminative Fields for Modeling Spatial Dependencies in Natural Images,  Advances in Neural Information Processing Systems, NIPS  16, 2004). This model combines discriminative single concept classifiers with pairwise concept co-occurrence features representing contextual information. In their work, the goal is to perform binary classification of pixel blocks in images as either “natural” or “man-made.” For the per-block classification, they use logistic regression. The random field incorporates spatial dependencies. More specifically, they model the probability of the (collective) vector of binary labels Y given the low-level image data X as 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                     
                      
                     Y 
                      
                     
                        
                       X 
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       
                         Z 
                          
                         
                           ( 
                           X 
                           ) 
                         
                       
                     
                      
                     
                       exp 
                       [ 
                       
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               S 
                             
                           
                            
                           
                             
                               A 
                               i 
                             
                              
                             
                               ( 
                               
                                 
                                   Y 
                                   i 
                                 
                                 , 
                                 X 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               S 
                             
                           
                            
                           
                             
                               ∑ 
                               
                                 j 
                                 ∈ 
                                 
                                   N 
                                   i 
                                 
                               
                             
                              
                             
                               
                                 I 
                                 ij 
                               
                                
                               
                                 ( 
                                 
                                   
                                     Y 
                                     i 
                                   
                                   , 
                                   
                                     Y 
                                     j 
                                   
                                   , 
                                   X 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     2 
                     ) 
                   
                 
               
             
           
         
       
     
         [0035]    The terms A i  are the association potential (or unary or node potentials) which are local discriminative classifiers for each spatial location i in the set S. I ij  is the term representing the interaction between the spatial locations, i, j. N i  is the set of neighbors of not i in the graph. 
         [0036]    This approach can be adapted to collective semantic concept detection. Rather than collectively classify adjacent spatial locations in a still image, related semantic concepts in a video clip can be collectively detected. Specifically, the SVM classifiers trained independently for each concept can be used for the association terms in equation (2). Each SVM output can be mapped to the corresponding probability P D (Yi=1|X) (see J. Platt, “Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods”, in  Advances in Large Margin Classifiers , A. Smola, P. Bartlett, B. Scholkopf, D. Schuurmans, Eds. MIT Press, 1999). The subscript D can be used to associate this probability with the single concept classifiers in contract to the collective models presented below. The association term for concept Y i  can be set according to equation (3). 
         [0000]        A   i ( Y   i   ,X )= v   i    log (P D ( Y   i =1| X ))  equation (3) 
         [0037]    In the absence of interaction terms (i.e., I ij =0), equation (2) reverts to the per-concept SVM models. The scalar weights p i  are determined in training as described below. 
         [0038]    Concepts which are related can be identified next, i.e. which concepts are connected by an edge in our graph. For this, a chi-squared test using the ground truth labeling of our training set can be used. Each concept can be connected to the five other concepts to which it has the most statistically significant relationships. The resulting graph defines the neighborhoods N i  for each concept Y i . This is currently done without thresholding and may not be optimal. However, learning optimal graphs in the general case is NP-hard. Nonetheless, evaluating other heuristics and approximation schemes for graph induction is both critical to the success of these methods and a promising area for future work. Many other approaches can be used in this step without limiting the invention. 
         [0039]    The interaction potential of Kumar and Herbert were inspired by longstanding work in image analysis using Markov random fields (S. Kumar and M. Hebert. Discriminative Fields for Modeling Spatial Dependencies in Natural Images.  Advances in Neural Information Processing Systems, NIPS  16, 2004). In contrast, the interaction potentials used are defined building on recent work in text categorization (N. Ghamrawi, and A. McCallum, “Collective multi-label classification”,  Proceedings of the  14 th ACM international Conference on information and Knowledge Management CIKM &#39; 05, ACM Press, New York. N.Y., pp. 195-200, 2005). Equation (2) can be rewritten to clarify our notation as equation (4). 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                     
                      
                     Y 
                      
                     
                        
                       X 
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       
                         Z 
                          
                         
                           ( 
                           X 
                           ) 
                         
                       
                     
                      
                     
                       exp 
                       [ 
                       
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               S 
                             
                           
                            
                           
                             
                               v 
                               i 
                             
                              
                             
                               log 
                                
                               
                                 ( 
                                 
                                   
                                     P 
                                     D 
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         Y 
                                         i 
                                       
                                       , 
                                       X 
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               S 
                             
                           
                            
                           
                             
                               ∑ 
                               
                                 j 
                                 ∈ 
                                 
                                   N 
                                   i 
                                 
                               
                             
                              
                             
                               
                                 ∑ 
                                 
                                   k 
                                   ∈ 
                                   
                                     K 
                                     i 
                                   
                                 
                               
                                
                               
                                 
                                   λ 
                                   ij 
                                   k 
                                 
                                  
                                 
                                   
                                     f 
                                     ij 
                                     k 
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         Y 
                                         i 
                                       
                                       , 
                                       
                                         Y 
                                         j 
                                       
                                       , 
                                       X 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     4 
                     ) 
                   
                 
               
             
           
         
       
     
         [0040]    The notation P D  can be used to distinguish the probability mapped from the single concept SVM output from the corresponding marginal probability of the joint model. Comparing equation (4) to equation (2), it is noted that the interaction term is the linear form: 
         [0000]    
       
         
           
             
               
                 
                   
                     I 
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           k 
                           ∈ 
                           K 
                         
                       
                        
                       
                         
                           λ 
                           ij 
                           k 
                         
                          
                         
                           
                             f 
                             ij 
                             k 
                           
                            
                           
                             ( 
                             
                               
                                 Y 
                                 i 
                               
                               , 
                               
                                 Y 
                                 j 
                               
                               , 
                               X 
                             
                             ) 
                           
                         
                       
                     
                     = 
                     
                       
                         A 
                         ij 
                         T 
                       
                        
                       
                         
                           F 
                           ij 
                         
                          
                         
                           ( 
                           
                             
                               Y 
                               i 
                             
                             , 
                             
                               Y 
                               j 
                             
                             , 
                             X 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     5 
                     ) 
                   
                 
               
             
           
         
       
     
         [0041]    It is noted that equation (4) can be rewritten compactly using vectors as equation (6). 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                     
                      
                     Y 
                      
                     
                        
                       X 
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       
                         Z 
                          
                         
                           ( 
                           X 
                           ) 
                         
                       
                     
                      
                     
                       exp 
                       [ 
                       
                         
                           
                             V 
                             T 
                           
                            
                           
                             
                               P 
                               D 
                             
                              
                             
                               ( 
                               X 
                               ) 
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               C 
                             
                           
                            
                           
                             
                               ∑ 
                               
                                 j 
                                 ∈ 
                                 
                                   N 
                                   i 
                                 
                               
                             
                              
                             
                               
                                 A 
                                 ij 
                                 T 
                               
                                
                               
                                 
                                   F 
                                   ij 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       Y 
                                       i 
                                     
                                     , 
                                     
                                       Y 
                                       j 
                                     
                                     , 
                                     X 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     6 
                     ) 
                   
                 
               
             
           
         
       
     
         [0042]    In equation (6), the i th  elements of V and P D (X) are p i  and log(P(Y i |X)), respectively. Likewise, the k th  elements of A ij  and F ij (Y i , Y j , X) are λ ij   (k)  and ƒ ij   (k) (Y i Y j X), respectively. This form shows that the random field model is simple a log-linear classifier. For maximum likelihood model training, the gradients of the log-likelihood thus take a standard form. 
       2.3.1 The ‘CML+1’ model 
       [0043]    The details of the interaction potential functions for two models are as follows. The first model, denoted ‘CML+1’, captures inter-concept co-occurrence. These features are defined for each pair of concepts Y i , Y j  that are connected in our graph (i.e. not for all pairs). Thus, the indexed family of interaction potential functions is given by equations (7A)-(7D). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         0 
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               Y 
                               i 
                             
                             = 
                             
                               
                                 Y 
                                 j 
                               
                               = 
                               0 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       7 
                        
                       A 
                     
                     ) 
                   
                 
               
             
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         1 
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 Y 
                                 i 
                               
                               = 
                               1 
                             
                             , 
                             
                               
                                 Y 
                                 j 
                               
                               = 
                               0 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       7 
                        
                       B 
                     
                     ) 
                   
                 
               
             
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         2 
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 Y 
                                 i 
                               
                               = 
                               0 
                             
                             , 
                             
                               
                                 Y 
                                 j 
                               
                               = 
                               1 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       7 
                        
                       C 
                     
                     ) 
                   
                 
               
             
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         3 
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               Y 
                               i 
                             
                             = 
                             
                               
                                 Y 
                                 j 
                               
                               = 
                               1 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       7 
                        
                       D 
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0044]    By modeling the four possible combinations separately, all types of inter-concept co-occurrence within the model can be captured. For this model the index set for the interaction potentials is simply κ={0, 1, 2, 3}. This interaction model adds discriminatively trained association potentials to a previously proposed method for text categorization (see N. Ghamrawi, and A. McCallum. Collective multi-label classification.  Proceedings of the  14 th ACM international Conference on information and Knowledge Management CIKM &#39; 05. ACM Press, New York, N.Y., pp. 195-200, 2005). 
         [0045]    As shown in  FIG. 3 , in an embodiment of the invention the SVM&#39;s are trained as to whether a concept is present using a labeled set of media, the media are input at step  300 . Next, the low level features are extracted at step  310 . At step  320  the initial conditions are set. At step the initial conditions are incremented. At step  340  the discriminative classifier is trained with the set of low level features. At step  350  the SVM&#39;s are optimized based on the low level features. At step  360  the procedures iterated until the SVM&#39;s have been trained for all concepts. At step  370  interaction potentials are defined. At step  370  a collective annotation model is built. 
         [0046]    As shown in  FIG. 4 , the trained SVM&#39;s, which can be generated in an embodiment of the invention as shown in  FIG. 3 , are used on a different media set to determine if concepts are present in the media set. The media are input at step  400 . Next, the SVM&#39;s are applied at step  410 . At step  420  the collective annotation model is built. At step  430  the probability that the concept is detected can be determined. 
       2.3.2 The ‘CMLT+1’ model 
       [0047]    A second model to capture concept-feature co-occurrence can be defined. First, the low level features X can be quantized across the training set using k-means or any other vector quantization technique. This discrete representation can be denoted for the low-level features as Q(X)ε{0, . . ., Q}. For this model, denoted ‘CMLT+1’, the interaction potentials can be defined by equations (8A)-(8D). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         
                           q 
                           , 
                           0 
                         
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                               
                              
                             
                               
                                 
                                   Y 
                                   i 
                                 
                                 = 
                                 
                                   
                                     Y 
                                     j 
                                   
                                   = 
                                   0 
                                 
                               
                               , 
                               
                                 
                                   Q 
                                    
                                   
                                     ( 
                                     X 
                                     ) 
                                   
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                               
                              
                             otherwise 
                           
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       8 
                        
                       A 
                     
                     ) 
                   
                 
               
             
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         
                           q 
                           , 
                           1 
                         
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                               
                              
                             
                               
                                 
                                   Y 
                                   i 
                                 
                                 = 
                                 1 
                               
                               , 
                               
                                 
                                   Y 
                                   j 
                                 
                                 = 
                                 0 
                               
                               , 
                               
                                 
                                   Q 
                                    
                                   
                                     ( 
                                     X 
                                     ) 
                                   
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                               
                              
                             otherwise 
                           
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       8 
                        
                       B 
                     
                     ) 
                   
                 
               
             
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         
                           q 
                           , 
                           2 
                         
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                               
                              
                             
                               
                                 
                                   Y 
                                   i 
                                 
                                 = 
                                 0 
                               
                               , 
                               
                                 
                                   Y 
                                   j 
                                 
                                 = 
                                 1 
                               
                               , 
                               
                                 
                                   Q 
                                    
                                   
                                     ( 
                                     X 
                                     ) 
                                   
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                               
                              
                             otherwise 
                           
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       8 
                        
                       C 
                     
                     ) 
                   
                 
               
             
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         
                           q 
                           , 
                           3 
                         
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                               
                              
                             
                               
                                 
                                   Y 
                                   i 
                                 
                                 = 
                                 
                                   
                                     Y 
                                     j 
                                   
                                   = 
                                   1 
                                 
                               
                               , 
                               
                                 
                                   Q 
                                    
                                   
                                     ( 
                                     X 
                                     ) 
                                   
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                               
                              
                             otherwise 
                           
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       8 
                        
                       D 
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0048]    The index set for the interaction potentials is κ={i,q):0≦i≦3,0≦q≦Q}. 
       EXAMPLE 1 
       [0049]    The TRECVID 2005 development data are used for the high-level concept detection task. The training and test sets each include more than 6000 video shots from various broadcast news sources collected in 2004. the 5 concept graph and 11 concept graph are also used for comparison to the results in R. Yan, M.-Y. Chen, A. Hauptmann, “Mining Relationships Between Concepts using Probabilistic Graphical Models”,  Proc. IEEE ICME,  2006. 
         [0050]    5 concept graph: car, face, person, text, walking/running 
         [0051]    11 concept graph: building, car, face, maps, outdoor, person, sports, studio, text, urban, walking/running. 
         [0052]    For comparison purposes, we outline that the system of Yan et al. (see R. Yan, M.-Y. Chen, A. Hauptmann, “Mining Relationships Between Concepts using Probabilistic Graphical Models”,  Proc. IEEE ICME,  2006) uses the following conditional random field (among several other probabilistic models): 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                     
                      
                     Y 
                      
                     
                        
                       X 
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       
                         Z 
                          
                         
                           ( 
                           X 
                           ) 
                         
                       
                     
                      
                     
                       exp 
                       [ 
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 C 
                               
                             
                              
                             
                               
                                 ( 
                                 
                                   
                                     α 
                                     i 
                                   
                                   + 
                                   
                                     
                                       V 
                                       i 
                                       T 
                                     
                                      
                                     X 
                                   
                                 
                                 ) 
                               
                                
                               
                                 Y 
                                 i 
                               
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 C 
                               
                             
                              
                             
                               
                                 ∑ 
                                 
                                   j 
                                   ∈ 
                                   
                                     N 
                                     i 
                                   
                                 
                               
                                
                               
                                 
                                   λ 
                                   ij 
                                 
                                  
                                 
                                   Y 
                                   i 
                                 
                               
                             
                           
                         
                         , 
                         
                           Y 
                           j 
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     9 
                     ) 
                   
                 
               
             
           
         
       
     
         [0053]    The systems are trained to maximize the likelihood of the training set to fit parameters. The log-likelihood is 
         [0000]    
       
         
           
             
               
                 
                   
                     l 
                      
                     
                       ( 
                       D 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         d 
                         ∈ 
                         D 
                       
                     
                      
                     
                       [ 
                       
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               C 
                             
                           
                            
                           
                             
                               v 
                               i 
                             
                              
                             log 
                              
                             
                               ( 
                             
                              
                             
                               
                                 P 
                                 D 
                               
                                
                               
                                 ( 
                                 
                                   
                                     Y 
                                     
                                       ( 
                                       d 
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       X 
                                       
                                         ( 
                                         d 
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               C 
                             
                           
                            
                           
                             
                               ∑ 
                               
                                 j 
                                 ∈ 
                                 
                                   N 
                                   i 
                                 
                               
                             
                              
                             
                               
                                 ∑ 
                                 
                                   k 
                                   ∈ 
                                   
                                     K 
                                     i 
                                   
                                 
                               
                                
                               
                                 
                                   λ 
                                   ij 
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                  
                                 
                                   
                                     f 
                                     ij 
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         Y 
                                         
                                           ( 
                                           d 
                                           ) 
                                         
                                       
                                       , 
                                       
                                         X 
                                         
                                           ( 
                                           d 
                                           ) 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                         
                         - 
                         
                           log 
                            
                           
                             ( 
                             
                               Z 
                                
                               
                                 ( 
                                 
                                   X 
                                   
                                     ( 
                                     d 
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                             ) 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     10 
                     ) 
                   
                 
               
             
           
         
       
     
         [0054]    This gives the gradient equations (11) and (12). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                        
                       l 
                     
                     
                        
                       
                         v 
                         i 
                       
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         d 
                         ∈ 
                         D 
                       
                     
                      
                     
                       [ 
                       
                         
                           log 
                            
                           
                             ( 
                           
                            
                           
                             
                               P 
                               D 
                             
                              
                             
                               ( 
                               
                                 
                                   Y 
                                   
                                     ( 
                                     d 
                                     ) 
                                   
                                 
                                  
                                 
                                    
                                   
                                     X 
                                     
                                       ( 
                                       d 
                                       ) 
                                     
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                         - 
                         
                           
                             ∑ 
                             
                               γ 
                               i 
                             
                           
                            
                           
                             log 
                             ( 
                             
                               
                                 
                                   P 
                                   D 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       Y 
                                       i 
                                     
                                      
                                     
                                        
                                       
                                         X 
                                         
                                           ( 
                                           d 
                                           ) 
                                         
                                       
                                       ) 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 P 
                                 ( 
                                 
                                   
                                     Y 
                                     i 
                                   
                                    
                                   
                                      
                                     
                                       X 
                                       
                                         ( 
                                         d 
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                                 ] 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     11 
                     ) 
                   
                 
               
             
             
               
                 
                   
                     
                        
                       l 
                     
                     
                        
                       
                         λ 
                         ij 
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         d 
                         ∈ 
                         D 
                       
                     
                      
                     
                       [ 
                       
                         
                           
                             f 
                             ij 
                             
                               ( 
                               k 
                               ) 
                             
                           
                            
                           
                             ( 
                             
                               
                                 Y 
                                 i 
                                 
                                   ( 
                                   d 
                                   ) 
                                 
                               
                               , 
                               
                                 Y 
                                 j 
                                 
                                   ( 
                                   d 
                                   ) 
                                 
                               
                               , 
                               
                                 X 
                                 
                                   ( 
                                   d 
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                         - 
                         
                           
                             ∑ 
                             
                               
                                 γ 
                                 i 
                               
                                
                               
                                 Y 
                                 j 
                               
                             
                           
                            
                           
                             
                               
                                 f 
                                 ij 
                                 
                                   ( 
                                   k 
                                   ) 
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     Y 
                                     i 
                                     
                                       ( 
                                       d 
                                       ) 
                                     
                                   
                                   , 
                                   
                                     Y 
                                     j 
                                     
                                       ( 
                                       d 
                                       ) 
                                     
                                   
                                   , 
                                   
                                     X 
                                     
                                       ( 
                                       d 
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               P 
                               ( 
                               
                                 
                                   Y 
                                   i 
                                 
                                 , 
                                 
                                   
                                     Y 
                                     j 
                                   
                                    
                                   
                                      
                                     
                                       X 
                                       
                                         ( 
                                         d 
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ] 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     12 
                     ) 
                   
                 
               
             
           
         
       
     
         [0055]    Here Y (d)  denoted the ground truth for training sample X (d) . Also, Y, (d) .Y j   (d)  denote the true values for concepts i, j ε C for sample X (d)  while Yi, Yj denote binary variables of integration. As demonstrated in (R. Malouf, “A comparison of algorithms for maximum entropy parameter estimation”,  Proceeding of the  6 th Conference on Natural Language Learning—Volume  20  International Conference On Computational Linguistics Association for Computational Linguistics, Morristown, N.J., 1-7, 2002) limited memory conjugate gradient methods greatly accelerate training maximum entropy and log-linear classifiers. The Broyden-Fletcher-Goldfarb-Shanno (BFGS) minimization routine can be used for maximum likelihood model training. 
         [0056]    Exhaustive inference can also be used, which entails evaluating P (Y|X) for each observed Y, and marginalizing to compute P (X i |X) ‘for all’ i ε C. This is generally prohibitive due to the exponential growth in concept combinations with the number of concepts. In the present context, the number of observed combination is much smaller. For example, fewer than 200 combinations in the experiments are observed using the 11 concept graph (as opposed to 2048 possible combinations). 
         [0057]    The first experimental baseline, denoted ‘CMU’, shows the results using equation (9) (R. Yan, M.-Y. Chen, A. Hauptmann, “Mining Relationships Between Concepts using Probabilistic Graphical Models”,  Proc. IEEE ICME,  2006). The second experimental baseline, denoted ‘SVM’, shows the results of using the discriminative ‘SVM’ outputs for independent concept detection (C. Snoek, M. Worring, J. van Gemert, M.-M. Geusebroek, and A. Smeulders, “The Challenge Problem for Automated Detection of 101 Semantic Concepts in Multimedia”,  Proceedings of ACM Multimedia,  2006). The experimental results for the ‘5 concepts’ graph are summarized in  FIG. 2A . The experimental results for the ‘11 concept’ graph are summarized in  FIG. 2B . The performance measure is mean average precision (MAP) which averages precision at each level of recall for each concept, and then computes the mean (of the average precisions) over the set of concepts. 
         [0058]    To isolate the contributions of the discriminative per-label classifiers, the interaction potential of equation (13) can be used in the ‘CMU’ system, to build the ‘CML’ system with equation (4). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       f 
                       ij 
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               Y 
                               i 
                             
                             = 
                             
                               
                                 Y 
                                 j 
                               
                               = 
                               1 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     13 
                     ) 
                   
                 
               
             
           
         
       
     
         [0059]    For this case there is a single feature for each stage (Yi, Yj), and the summation over κ degenerates to a single term. The ‘CML’ system (0.6002) does slightly better than ‘SVM’ system (0.5977) and the ‘CMU’ system (0.5882) for the 5 concept graph. It also outperforms both systems on the 11 concept graph (‘CMU’=0.5211, ‘SVM’=0.4975, ‘CML’=0.5262). 
         [0060]    Next, the more complete indexed family of interaction potential functions is given by equations (7A)-(7D) to equation (4) to form the system denoted ‘CML+1’. This system accounts for different types of inter-concept relationships and performs at the highest level of all systems in both cases with MAP of 0.6233 and 0.5307 for the ‘5 concept’ and ‘11 concept’ graphs, respectively. 
         [0061]    The final systems test the value of the concept-feature co-occurrence interaction potentials. The ‘CMLT’ model combines the discriminative association potentials with simple interaction (analogous to CML): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       f 
                       ij 
                       
                         ( 
                         q 
                         ) 
                       
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           i 
                         
                         , 
                         
                           Y 
                           j 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                               
                              
                             
                               
                                 
                                   Y 
                                   i 
                                 
                                 = 
                                 
                                   
                                     Y 
                                     j 
                                   
                                   = 
                                   1 
                                 
                               
                               , 
                               
                                 
                                   Q 
                                    
                                   
                                     ( 
                                     X 
                                     ) 
                                   
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                               
                              
                             otherwise 
                           
                         
                       
                     
                   
                 
               
               
                 
                   equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     14 
                     ) 
                   
                 
               
             
           
         
       
     
         [0062]    This system outperforms the SVM baseline for both graphs, but the CMU baseline does better for the 11 concept graph. The ‘CMLT’ system has MAP of 0.6009 and 0.5136 for the 5 and 11 concept graphs, respectively. The ‘CMLT+1’ system uses the more complete interaction potential functions of (8). This system outperforms ‘CMLT’, but in both cases is worse than ‘CML+1’. The ‘CMLT+1’ system has MAP of 0.6122 and 0.5184 for the 5 and 11 concept graphs, respectively. This can be due to the coarse quantization and relatively uninformative low-level features used (k-means to 126 classes), and expect that more sophisticated quantization will yield further improvements. 
         [0063]    Example embodiments of the methods, systems, and components of the present invention have been described herein. As noted elsewhere, these example embodiments have been described for illustrative purposes only, are not limiting. Other embodiments are possible and are covered by the invention. Such embodiments will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. 
         [0064]    Thus, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.