Abstract:
Systems and methods for generating a visual vocabulary build a plurality of visual words via unsupervised learning on set of features of a given type; decompose one or more visual words to a collection of lower-dimensional buckets; generate labeled image representations based on the collection of lower dimensional buckets and labeled images, wherein labels associated with an image are associated with a respective representation of the image; and iteratively select a sub-collection of buckets from the collection of lower-dimensional buckets based on the labeled image representations, wherein bucket selection during any iteration after an initial iteration is based at least in part on feedback from previously selected buckets.

Description:
BACKGROUND 
       [0001]    1. Field 
         [0002]    The present disclosure relates to visual analysis of images. 
         [0003]    2. Background 
         [0004]    In the field of image analysis, images are often analyzed based on visual features. The features include shapes, colors, and textures. The features in the image can be detected and the content of the image can be guessed from the detected features. However, image analysis can be very computationally expensive. 
       SUMMARY 
       [0005]    In one embodiment, a method for building a visual vocabulary comprises building a plurality of visual words in a generative vocabulary via unsupervised learning on set of features of a given type; decomposing one or more visual words to a collection of lower-dimensional buckets; and iteratively selecting a sub-collection of buckets from the collection of lower-dimensional buckets, wherein the selection during any iteration after an initial iteration is based at least in part on feedback from previously selected buckets. 
         [0006]    In one embodiment, a system for building a visual vocabulary comprises one or more processors; and one or more computer-readable media coupled to the one or more processors, the one or more computer-readable media storing instructions that, when executed by the one or more processors, cause the system to perform operations comprising building visual words in a first generative vocabulary via unsupervised learning on a set of features of a first type of feature; building visual words in a second generative vocabulary via unsupervised learning on a set of features of a second type of feature; decomposing one or more visual words in the first generative vocabulary to a first collection of lower-dimensional buckets; decomposing one or more visual words in the second generative vocabulary to a second collection of lower-dimensional buckets; combining the first and second collections of lower-dimensional buckets from the first and second generative vocabularies respectively to generate a collection of buckets; and selecting a sub-collection of buckets from the collection of buckets based on semantic labels associated with training images and based on which buckets in the collection of buckets are most discriminative of the semantic labels. 
         [0007]    In one embodiment, one or more computer-readable media store instructions that, when executed by one or more computing devices, cause the computing devices to perform operations comprising clustering features from one or more images in a multi-dimensional space to form first feature clusters, wherein the features and the first feature clusters are defined in a higher-dimensional space; projecting the features into a lower-dimensional space to form lower-dimensional features, and generating buckets based on the lower-dimensional features. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]      FIG. 1  illustrates an example embodiment of a method for generating a visual vocabulary. 
           [0009]      FIG. 2  illustrates an example embodiment of feature clusters and lower-dimensional buckets. 
           [0010]      FIG. 3  illustrates an example embodiment of a method for adjusting the boundaries of a bucket. 
           [0011]      FIG. 4  illustrates an example embodiment of a method for generating a visual vocabulary. 
           [0012]      FIG. 5  illustrates an example embodiment of a method for generating a visual vocabulary. 
           [0013]      FIG. 6  illustrates an example embodiment of a method for encoding an image with a vocabulary. 
           [0014]      FIG. 7  illustrates an example embodiment of a feature that is encoded according to a vocabulary. 
           [0015]      FIG. 8  illustrates an example embodiment of the most discriminative buckets of a set of clusters. 
           [0016]      FIG. 9  illustrates an example embodiment of a set of discriminative buckets. 
           [0017]      FIG. 10  is a block diagram that illustrates the selection of bucket functions based on bucket values. 
           [0018]      FIG. 11  includes tables that illustrate example embodiments of one-against-all partitions. 
           [0019]      FIG. 12  illustrates an example embodiment of a method for selecting a subset of buckets. 
           [0020]      FIG. 13  illustrates an example embodiment of a method for generating a visual vocabulary. 
           [0021]      FIG. 14  illustrates an example embodiment of a method for generating a visual vocabulary. 
           [0022]      FIG. 15  is a block diagram that illustrates an example embodiment of a system for generating a visual vocabulary. 
           [0023]      FIG. 16A  is a block diagram that illustrates an example embodiment of a system for generating a visual vocabulary. 
           [0024]      FIG. 16B  is a block diagram that illustrates an example embodiment of a system for generating a visual vocabulary. 
           [0025]      FIG. 17  illustrates an example embodiment of an image that is encoded according to different vocabularies. 
       
    
    
     DESCRIPTION 
       [0026]    The following disclosure describes certain explanatory embodiments. Additionally, the explanatory embodiments may include several novel features, and a particular feature may not be essential to practice the systems and methods described herein. 
         [0027]      FIG. 1  illustrates an example embodiment of a method for generating a visual vocabulary. First, in block  110 , the features in a set of features (e.g., a training set (not shown in  FIG. 1 )) are clustered in the original dimensional space of the features. The clusters in the original dimensional space are then decomposed into lower-dimensional buckets in block  120 . A visual word in the original dimensional space may include the area that is defined by one or more clusters (e.g., the space of a cluster in the original dimensional space may define a visual word in a first vocabulary), and a generative visual vocabulary includes a plurality of the visual words in the original dimensional space. Also, a visual word in the original dimensional space may be decomposed into a set of buckets, and a bucket may define a visual word in the lower-dimensional space (e.g., a word in a second vocabulary). Next, in block  130 , respective bucket functions (e.g., functions that map features to buckets) are defined for the buckets, and then the buckets may be ranked, for example based on their purity and/or their ability to discriminate between clusters and/or features. 
         [0028]    Then in block  140 , training images, which include respective labels (e.g., semantic labels), are encoded based on the buckets. Thus, the features in the training images are described by the buckets. Next, in block  150 , buckets that are discriminative of the labels are selected. For example, the buckets that are most discriminative of a label are selected. Finally, in block  160 , the bucket functions that correspond to the selected buckets are added to a visual vocabulary. Thus, in the embodiment shown in  FIG. 1 , the selected buckets are Ψ 11 , Ψ 12 , Ψ 14 , and Ψ 1J  though other buckets denoted by the ellipses may also be selected (note that herein a bucket may be represented by the symbol “Ψ”). Bucket Ψ 13  is not selected since bucket Ψ 13  is determined to be less discriminative of features. Accordingly, the respective bucket functions that correspond to buckets Ψ 11 , Ψ 12 , Ψ 14  and Ψ 1J  are added to the visual vocabulary. 
         [0029]    Therefore, the method may generate a discriminative visual vocabulary from a generative visual vocabulary and may select the scalar features that are most discriminative of one or more labels to define visual words. Since each bucket may be associated with a scalar feature, the process of encoding an image could be performed very fast in a one-dimensional space. Also, the method may learn a discriminative vocabulary for multiple types of features and may combine the advantages of generative and discriminative models, as well as fast scalar visual words. 
         [0030]    The operations performed in blocks  110 - 160  will be described in more details below. Also, let X={X 1 , X 2 , . . . , X N } denote a set of N training images. Each image is represented by a bag of features 
         [0000]    
       
         
           
             
               
                 X 
                 i 
               
               = 
               
                 
                   { 
                   
                     
                       
                         x 
                         
                           
                             i 
                              
                             
                                 
                             
                              
                             1 
                           
                           , 
                         
                         s 
                       
                        
                       
                         x 
                         
                           
                             i 
                              
                             
                                 
                             
                              
                             2 
                           
                           , 
                         
                         s 
                       
                        
                       … 
                     
                      
                     
                         
                     
                     , 
                     
                       x 
                       
                         i 
                          
                         
                             
                         
                          
                         
                           J 
                           i 
                           s 
                         
                       
                       s 
                     
                   
                   } 
                 
                 
                   s 
                   = 
                   1 
                 
                 S 
               
             
             , 
           
         
       
     
         [0000]    where J i   s  denotes the number of the features of type s extracted from the image X i , S is the total number of feature types, and each x ij   s  is a d s  dimensional feature vector. Let y i εY denote the label of the image X i , where Y={1, . . . , C} denotes the label set. The method may generate a visual vocabulary based on the training set so that an image can be represented by a fixed-length vector that is created by encoding the features in the image according to the visual vocabulary. 
         [0031]    For sake of simplicity in some of the description, only one feature type (e.g., color, texture, brightness, shape, SIFT feature, CHoG feature) is used, which eliminates the subscript for feature type (i.e., “s”). Also, Z represents the set of labeled feature examples and can be generated by labeling each feature in the image with the corresponding label. The feature examples are indexed with l, which indexes over all images and image features so that z l =x ij   s  and y i =y i , where y is an image label. Thus, the example set of labeled features is given by Z={z l , y l } l=1   L . This set is used in the systems and methods discussed herein. In some embodiments, certain features in X i  may be individually labeled, instead of assigning one or more labels for the entire image to all the features in the image. In these embodiments, y l =y ij , where y ij  is the label for the j-th feature of image i. 
         [0032]      FIG. 2  illustrates an example embodiment of feature clusters  220 A-D and lower-dimensional buckets  210 A-B. In this example, the feature clusters  220 A-D are shown in two-dimensional space, though in other embodiments the features and feature clusters  220 A-D may include more or fewer dimensions. Also, though the buckets  210 A-B are defined in one-dimension (i.e., in the x or y dimension), in other embodiments the buckets may be defined in two or more dimensions. To form the buckets, the feature clusters  220 A-D are decomposed into lower-dimensional space.  FIG. 2  shows a two-dimensional first cluster  220 A that is decomposed to form two one-dimensional buckets: a first bucket  210 A (defined in the x dimension) and a second bucket  210 B (defined in the y dimension). The first bucket  210 A and the second bucket  210 B do not have any common dimension(s), though in other embodiments the buckets may have common dimensions. 
         [0033]    For example, to generate buckets given a set of low-level features (of the same type) z l   s , the features are clustered (e.g., via K-means clustering) in the d s -dimensional feature space. This generates K s  clusters {Ω k   s } k=1   K   s , which have respective cluster centers ∂ k   s . Each cluster (“Ω”) is decomposed into J s (≦d s ) one-dimensional buckets, where each bucket is defined by a respective bucket function, 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       b 
                       
                         k 
                         , 
                         j 
                       
                       s 
                     
                      
                     
                       ( 
                       
                         
                           z 
                           
                             l 
                             , 
                             j 
                           
                           s 
                         
                         , 
                         
                           θ 
                           
                             k 
                             , 
                             j 
                           
                           s 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                             , 
                           
                         
                         
                           
                             
                               if 
                                
                               
                                   
                               
                                
                               
                                  
                                 
                                   
                                     z 
                                     
                                       l 
                                       , 
                                       j 
                                     
                                     s 
                                   
                                   - 
                                   
                                     ∂ 
                                     
                                       k 
                                       , 
                                       j 
                                     
                                     s 
                                   
                                 
                                  
                               
                             
                             &lt; 
                             
                               θ 
                               
                                 k 
                                 , 
                                 j 
                               
                               s 
                             
                           
                         
                       
                       
                         
                           
                             0 
                             , 
                           
                         
                         
                           
                             otherwise 
                             , 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     b 
                      
                     
                         
                     
                      
                     1 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    for jε{1, . . . , d s }.  FIG. 2  shows an example that decomposes a two-dimensional first cluster  220 A into two one-dimensional buckets  210 A-B, which are obtained by projecting the original samples (the two-dimensional features and the first cluster  220 A) onto the x and y axes, respectively. The width of each bucket θ k,j   s  may be optimized by minimizing a purity measure τ k,j   s  of the correspondence between the cluster assignment of the training features and the bucket assignments of the training features. 
         [0034]    In some embodiments the purity measure is generated according to the following: Let |Ω k   s | be the number of samples in the cluster Ω k   s . The total number of samples falling in a bucket is given by 
         [0000]    
       
         
           
             
               N 
               b 
             
             = 
             
               
                 ∑ 
                 
                   l 
                   = 
                   1 
                 
                 
                   L 
                   s 
                 
               
                
               
                 
                   
                     b 
                     
                       k 
                       , 
                       j 
                     
                     s 
                   
                    
                   
                     ( 
                     
                       
                         z 
                         l 
                         s 
                       
                       , 
                       
                         θ 
                         
                           k 
                           , 
                           j 
                         
                         s 
                       
                     
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
         [0000]    The number of samples falling in both the cluster Ω k   s  and the bucket is given by 
         [0000]    
       
         
           
             
               N 
               
                 Ω 
                 , 
                 b 
               
             
             = 
             
               
                 ∑ 
                 
                   
                     z 
                     l 
                     s 
                   
                   ∈ 
                   
                     Ω 
                     k 
                     s 
                   
                 
               
                
               
                   
               
                
               
                 
                   
                     b 
                     
                       k 
                       , 
                       j 
                     
                     s 
                   
                    
                   
                     ( 
                     
                       
                         z 
                         
                           l 
                           , 
                         
                         s 
                       
                        
                       
                         θ 
                         
                           k 
                           , 
                           j 
                         
                         s 
                       
                     
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
         [0000]    The purity measure is generated according to 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       τ 
                       
                         k 
                         , 
                         j 
                       
                       s 
                     
                     = 
                     
                       
                         η 
                          
                         
                             
                         
                          
                         
                           
                             N 
                             
                               Ω 
                               , 
                               b 
                             
                           
                           
                              
                             
                               Ω 
                               k 
                               s 
                             
                              
                           
                         
                       
                       + 
                       
                         
                           ( 
                           
                             1 
                             - 
                             η 
                           
                           ) 
                         
                          
                         
                           
                             N 
                             
                               Ω 
                               , 
                               b 
                             
                           
                           
                             N 
                             b 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   
                     b 
                      
                     
                         
                     
                      
                     2 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    where ηε [ 0,1] is a regularization parameter. Also, τ k,j   s  is a function of the bucket width θ k,j   s  and the bucket center ∂ k,j   s . Thus, the optimal bucket width may be found by maximizing τ k,j   s  with respect to θ k,j   s  and ∂ k,j   s . 
         [0035]    In some embodiments the bucket width is generated by an iterative method.  FIG. 3  illustrates an example embodiment of a method for adjusting the boundaries of a bucket. The method begins in block  391  by choosing the right partition boundary b right    340 A of a bucket  310 A in the x dimension  300 A. The right partition boundary b right    340 A may be chosen as a fixed percentage of the total number of samples (features) in the set of samples or it may be chosen at random. Next, the left partition boundary b left    330 A is selected. This can be selected by evaluating a clustering quality measure, and the method may select the left partition boundary b left    330 A that maximizes the clustering quality of the bucket (which may also be referred to herein as the “bucket purity”). Some consideration for the size of the bucket partition may be made so that the partition is sufficiently large, and in some embodiments the bucket purity measure inherently considers the partition size. Once the initial best left partition boundary b left    330 A is selected in block  391 , in block  392  the left partition boundary  330 B is fixed and the right partition boundary b right    340 B is varied in the x dimension  300 B such that the optimal bucket  310 B is found using the bucket purity measure. Once the initial best right partition boundary b right    340 B is found, the method may repeat blocks  391  and  392  for a specified number of iterations or until the boundaries no longer change. The left partition boundary b left  and right partition boundary b right  can then be converted to the bucket width θ k,j   s  and the bucket center ∂ k,j   s . 
         [0036]    In some embodiments the bucket center ∂ k,j   s  is given as the projection of the cluster center, and the appropriate bucket width θ k,j   s  for a bucket centered at ∂ k,j   s  is determined. In these embodiments, the method above may be simplified when the bucket width is selected such that the bucket purity is maximized. In these embodiments no iterative determination of the left partition boundary b left  and then the right partition boundary b right  is necessary, as the left and right partition boundaries are selected by varying the bucket width θ k,j   s  (which may be determined by iterative methods). 
         [0037]    Also, bucket purity measures may be formed from contingency-table-based measures. The table below shows an example contingency table that includes three clusters Ω and three buckets Ψ. The number of samples (features) in cluster i is given by a i , the number of samples in bucket partition j is given by b j , the number of samples shared by cluster i and bucket partition j is given by n ij , and the total number of samples is given by N. 
         [0000]    
       
         
               
             
               
               
               
               
               
             
           
               
                   
               
               
                 Ψ 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Ω 
                 n 11   
                 n 12   
                 n 13   
                 a 1   
               
               
                   
                 n 21   
                 n 22   
                 n 23   
                 a 2   
               
               
                   
                 n 31   
                 n 32   
                 n 33   
                 a 3   
               
               
                   
                 b 1   
                 b 2   
                 b 3   
                 N 
               
               
                   
               
             
          
         
       
     
         [0038]    Some embodiments have only two partitions for each bucket: (1) inside the bucket, and (2) not inside the bucket. Thus, in  FIG. 2 , the features in the first cluster  220 A would be “inside” the first bucket  210 A, and the features in the second cluster  220 B would be “not inside” (or “outside”) the first bucket  210 A. However, in some embodiments there could be other partitioning schemes involving more than two partitions. Also, in some embodiments only two clusters are used to evaluate the purity of a bucket. For example, one cluster could represent a cluster of interest while the second cluster could represent all other clusters. However, in some embodiments more than two clusters are used to evaluate the purity of a bucket. 
         [0039]    Some embodiments of the measure of bucket purity include clustering quality measures such as the Rand Index, Mutual Information, and variants of these measures that account for results obtained by random, such as the Adjusted Rand Index and Adjusted Mutual Information. These measures can take on various forms, as described in WO/2012/054399, by Bradley Denney and Anoop Korattikara-Balan, and in WO/2012/054352, by Bradley Denney and Anoop Korattikara-Balan, which are incorporated by reference. 
         [0040]    After the boundaries of the buckets are determined, θ k,j   s  and ∂ k,j   s  will have been determined, and the respective bucket functions, which map features to the respective buckets, can be defined: 
         [0000]    
       
         
           
             
               
                 b 
                 
                   k 
                   , 
                   j 
                 
                 s 
               
                
               
                 ( 
                 
                   
                     z 
                     
                       l 
                       , 
                       j 
                     
                     s 
                   
                   , 
                   
                     θ 
                     
                       k 
                       , 
                       j 
                     
                     s 
                   
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       1 
                       , 
                     
                   
                   
                     
                       
                         if 
                          
                         
                             
                         
                          
                         
                            
                           
                             
                               z 
                               
                                 l 
                                 , 
                                 j 
                               
                               s 
                             
                             - 
                             
                               ∂ 
                               
                                 k 
                                 , 
                                 j 
                               
                               s 
                             
                           
                            
                         
                       
                       &lt; 
                       
                         θ 
                         
                           k 
                           , 
                           j 
                         
                         s 
                       
                     
                   
                 
                 
                   
                     
                       0 
                       , 
                     
                   
                   
                     
                       otherwise 
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0041]    In some embodiments, the buckets are ranked in a decreasing order according to their corresponding purity τ k,j   s (θ k,j   s ) values, and the top J s (≦d s ) buckets may be selected (e.g., embodiments where the total number of buckets is too great, to save computing resources, to reduce computational complexity, etc.). In some embodiments all of the buckets are used. Thus for the feature type s, K s ×J s  buckets (e.g., total number of clusters x total number of selected dimensions) can be generated. The total number of buckets for all S feature types is B=Σ s=1   S K s ×J s . The buckets are used to define words in an intermediate visual vocabulary V I . 
         [0042]      FIG. 4  illustrates an example embodiment of a method for generating a visual vocabulary (e.g., an intermediate visual vocabulary). For purposes of explanation, the embodiment shown in  FIG. 4  describes only a single feature type, though other embodiments may include more feature types. To use multiple feature types, the embodiment shown in  FIG. 4  may be repeated for the different feature types, and then the results can be combined to form a vocabulary. Also, other embodiments of this method and the other methods described herein may omit blocks, add blocks, change the order of the blocks, combine blocks, and/or divide blocks into multiple blocks. Additionally, the methods described herein may be implemented by the systems and devices described herein. 
         [0043]    The flow in  FIG. 4  begins in block  400 . Next, in block  410 , cluster 1  403 A, cluster 2  403 B, . . . , and cluster K  403 C are generated based on a training set of features  401  (samples), which may be labeled or unlabeled. The training set of features may be retrieved from a computer-readable medium and clustered by a computing device that implements one or more clustering methods. Thus, K clusters are generated in block  410 , and the clusters are generated based at least on the visual similarity of the features (and in some embodiments the clusters are based on only the visual similarity of the features). Next, in blocks  420 A-C, for each of the K clusters  403 A-C, J corresponding buckets  405 A-C are generated based on the respective cluster (e.g., J may be equal to the number of the dimensions of the features). Also, blocks  420 A-C may be performed serially or in parallel. The flow proceeds to block  430 , where the buckets are aggregated to generate an intermediate vocabulary V I    407 , which includes all the buckets  405 A-C. The intermediate vocabulary V I    407  may be used to encode an image (e.g., describe one or more feature in an image with the words in the vocabulary). 
         [0044]      FIG. 5  illustrates an example embodiment of a method for generating a visual vocabulary (e.g., an intermediate visual vocabulary). In block  510 , the features in a training set  501  are clustered in their native dimensional space to form five clusters  503 A-E. Though  FIG. 5  shows three dimensions, other embodiments may operate in a dimensional space that has more or fewer dimensions. Next, in blocks  520 A-C, respective corresponding buckets are generated for the clusters  501 A-E (though blocks corresponding to clusters  503 C-D are not shown). Thus, buckets Ψ 11 , Ψ 12 , and Ψ 1J  are formed for cluster  503 A; buckets Ψ 21 , Ψ 22 , and Ψ 2J  are formed for cluster  503 B; . . . ; and buckets Ψ K1 , Ψ K2  and Ψ KJ  are formed for cluster  503 E. Generating the buckets includes decomposing the respective cluster into lower dimensions. For example, cluster  503 A is decomposed into the three dimensions (e.g., by projecting the cluster  503 A into each dimension), and a respective one-dimensional bucket is formed for each dimension. The buckets are then added to an intermediate vocabulary  507 . The intermediate vocabulary includes multiple buckets for each dimension. For example, buckets Ψ 12 , Ψ 22 , and Ψ K2  are all defined in the same dimension. 
         [0045]      FIG. 6  illustrates an example embodiment of a method for encoding an image with a vocabulary. In this example embodiment, a labeled image X, which includes multiple types of features {z 1   s , . . . , z M     s     s } s=1   S , is encoded with the intermediate vocabulary V i  to obtain an intermediate representation μ in the form of a B-dimensional vector, 
         [0000]      μ=[μ 1,1   1 , . . . ,μ k,j   s , . . . ,μ K     s     ,J     s     S   ], k= 1 , . . . ,K   s   ; j= 1 , . . . ,J   s   ; s= 1 , . . . ,S,   (1c) where
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       μ 
                       
                         k 
                         , 
                         j 
                       
                       s 
                     
                     = 
                     
                       
                         1 
                         
                           M 
                           s 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             
                               z 
                               l 
                               s 
                             
                             ∈ 
                             
                               X 
                               I 
                             
                           
                         
                          
                         
                           
                             b 
                             
                               k 
                               , 
                               j 
                             
                             s 
                           
                            
                           
                             ( 
                             
                               
                                 z 
                                 l 
                                 s 
                               
                               , 
                               
                                 θ 
                                 
                                   k 
                                   , 
                                   j 
                                 
                                 s 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   
                     1 
                      
                     d 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    and where S is the number of the types of features, K s  is the number of clusters for a type of feature, J s  is the number of buckets for a type of feature, and M s  is the total number of features of type s extracted from the labeled image X. 
         [0046]    The flow starts in block  610 , where a labeled image X  601  is received (e.g., retrieved from a computer-readable medium). The image X  601  may be labeled with one or more semantic labels. Next, in blocks  620 A-B, the features 1, . . . , S are extracted (and the blocks  620 A-B may be performed in parallel, serially, or a combination of in parallel and serially). Flow then proceeds to blocks  630 A-B. In this embodiment the features include different types of features, and each type of feature has its own corresponding intermediate vocabulary. In blocks  630 A-B, the features (features 1, . . . , S) are encoded based on the respective corresponding intermediate vocabularies  607 A-B of their type of feature to generate respective intermediate representations for the features  609 A-B. Next, in block  640 , the labels and the intermediate representations for the features  609 A-B are merged to generate a joint intermediate representation μ for image X  611  that includes the labels. 
         [0047]    Also,  FIG. 7  illustrates an example embodiment of a feature that is encoded according to a vocabulary. An image feature  703  is extracted from an image X  701 , which includes several features. In block  730 , an intermediate representation μ  709  is generated based on the feature  703  and the corresponding intermediate vocabulary  707 , for example by encoding the feature  703  based on the intermediate vocabulary  707  that corresponds to the same type of feature as the first feature  703 . In block  730 , the feature  703  is projected into the respective dimensions of the buckets in the intermediate vocabulary  707 , and the respective buckets that the projections of the feature  703  map to (e.g., fall into) in each dimension are determined. In the example embodiment shown, the projections of the feature  703  fall into buckets Ψ 11 , Ψ 12 , Ψ 1J , Ψ 21 , Ψ 2J , and Ψ K2 . Also, the projections of the feature  703  do not fall into (or fall outside of) buckets Ψ 22 , Ψ K1 , and Ψ KJ . The mappings to the buckets are then described in an intermediate representation μ  709  of the feature  703 . The intermediate representation μ  709  represents each bucket mapping with a binary value, where 1 indicates that the feature falls into (maps to the inside of) the respective bucket and 0 indicates that the feature falls outside (maps to the outside of) the respective bucket. The binary value may be represented by a single bit in a computing system, which may allow a computing system to store the intermediate representation μ  709  using fewer bits than are required to store the feature itself. Also, some embodiments may use values other than 1 and 0 to represent the mappings to the buckets, for example integer values (e.g., 1 to 10, 0 to 100). 
         [0048]    After an intermediate representation μ has been generated for one or more images (e.g., the images in a training set), the most discriminative buckets can be determined.  FIG. 8  illustrates an example embodiment of the most discriminative buckets of a set of clusters. Also, the embodiment shown in  FIG. 8  has been simplified for purposes of explanation and includes only a few clusters, three dimensions, and a significant difference between the discriminability of one dimension (d3) and the other two dimensions (d1 and d2). Other embodiments may include more clusters, more dimensions, and more complex relationships of the clusters in different dimensions. 
         [0049]    The three clusters  830 A-C in the set of clusters are formed in a three-dimensional space that has dimensions d1, d2, and d3. However, two of the dimensions, d1 and d2, are not very discriminative of the clusters  830 A-C. This is illustrated by the projections  835  of the clusters  830 A-C onto the two-dimensional space defined by d1 and d2. As shown by the projections  835 , in the two-dimensional space of d1 and d2 the clusters  830 A-C overlap so much that discriminating between the clusters using only dimension d1, dimension d2, or both is very difficult. Thus, buckets Ψ 11 , Ψ 12 , Ω 21 , and Ψ 22  do not efficiently discriminate between the clusters  830 A-C. However, in dimension d3 the clusters  830 A-C do not overlap much. Therefore, dimension d3 may be used to more efficiently discriminate between the clusters  830 A-C, and buckets Ψ 31 , Ψ 32 , and Ψ 33  more efficiently discriminate between the clusters  830 A-C than buckets Ψ 11 , Ψ 12 , Ψ 21 , and Ψ 22 . 
         [0050]      FIG. 9  illustrates an example embodiment of a set of discriminative buckets.  FIG. 9  illustrates four clusters of features (cluster A, cluster B, cluster C, and cluster D) that are defined in a two-dimensional space  900 . Each cluster is projected onto each of the two dimensions, and eight buckets (buckets 1-8) are generated based on the eight projections. A new feature could be mapped to a cluster by mapping the new feature to each of the eight buckets and then determining, based on the mappings to the eight buckets, which cluster the new feature maps to. However, mapping the new feature to eight buckets would generate bucket information that is not necessary to discriminate whether or not the feature falls in a particular bucket. The presence of unnecessary information in the mapping to the eight buckets is illustrated in table  920 , which shows that only three buckets, buckets 1, 6, and 7, are necessary to map a feature to a cluster. Thus, it may be possible to determine a set of discriminative buckets that allow a feature&#39;s corresponding cluster to be determined without mapping the feature to all of the buckets. Also, the discriminative buckets allow the mapping of a feature to any of the clusters (e.g., no cluster is excluded from the mapping such that a feature cannot possibly be mapped to the cluster). Furthermore, if each cluster is a word in a visual vocabulary (e.g., a visual vocabulary in an original dimensional space), each word may be defined/represented by a set of buckets and bucket values. Also, in some embodiments, each bucket may itself be considered to be a word in a visual vocabulary (e.g., a visual vocabulary in a lower-dimensional space). 
         [0051]      FIG. 10  is a block diagram that illustrates the selection of buckets based on bucket values. In block  1010 , the respective bucket values (the values contained in respective buckets) of intermediate representations μ of labeled images  1001  are analyzed to determine which buckets are most discriminative of label q  1003 . Next, in block  1020  the bucket functions  1005  of the most discriminative buckets of label q  1003  are added to a second vocabulary D I    1007 . Furthermore, a respective classifier may be trained for each bucket, and the classifiers may be added to a third vocabulary D h . Thus, the bucket functions in the second vocabulary D I    1007  are selected based on the bucket values in the intermediate representations of labeled images  1001 . 
         [0052]    In some embodiments, the buckets are selected via AdaBoost. Additionally, a classifier h t (x) may be trained to indicate if a label applies to a feature. For example, a bucket value μ k,j   s  may be input to a classifier h t (x) that outputs a label score (e.g., classification score) that indicates the probability of a label applying to a feature. Also, training a classifier h t (x) may include determining a respective weight for the classifier. In a set of N training examples Z={x n ,y n } n=1   N , where x n  is a d dimensional vector and y n ε{1, −1}, AdaBoost iteratively learns a sequence of weak classifiers h t (x)(t=1, . . . , T) from the training examples with respect to a distribution w n   (t)  of the examples for each iteration t. A strong classifier is created by a linear combination of the T weak classifiers, 
         [0000]        H ( x )=[Σ t=1   T   h   t ( x )]−θ b .  (1)
 
         [0053]    The classification of a sample x (e.g., a visual feature) is obtained by 
         [0000]        ŷ ( x )=sign[ H ( x )]. 
         [0054]    In order to perform feature selection with AdaBoost, a stump classifier may be used as a weak classifier h t (•), and an element μ k,j   s  of the intermediate representation μ may be used as an input to the stump classifier. In some embodiments, each stump classifier is associated with a bucket defined on a single dimension of a feature vector x n . Also, the domain of a bucket may be based on the i-th element (the i-th dimension) of the feature vector x n  (i.e., based on ƒ i (x n )=x ni ). In some embodiments, the bucket&#39;s domain is based on a more complicated function ƒ i , which considers multiple dimensions of the feature vector. Thus, the best weak classifier h t (•) may be determined by finding the best corresponding intermediate representation element, which corresponds to choosing the best corresponding bucket(s) b k,j   s  (since the representation is a vector, every element corresponds to a bucket, and finding the best element may be equivalent to finding the best bucket), for example based on the bucket values. Also, a best bucket (e.g., element) in an intermediate image representation may be determined by finding the best weak classifier. 
         [0055]    Additionally, when selecting a bucket function and/or training a classifier (e.g., a classifier based on the bucket function), some embodiments attempt to minimize the following weighted least square error, 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                     = 
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                           
                       
                        
                       
                         
                           
                             w 
                             j 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   h 
                                   m 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       f 
                                       i 
                                     
                                      
                                     
                                       ( 
                                       
                                         x 
                                         j 
                                       
                                       ) 
                                     
                                   
                                   ) 
                                 
                               
                               - 
                               
                                 y 
                                 j 
                               
                             
                             ) 
                           
                         
                         2 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       h 
                       t 
                     
                      
                     
                       ( 
                       
                         
                           f 
                           i 
                         
                          
                         
                           ( 
                           
                             x 
                             j 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               v 
                               i 
                             
                             , 
                           
                         
                         
                           
                             
                               if 
                                
                               
                                   
                               
                                
                               
                                 f 
                                 i 
                               
                             
                             ≥ 
                             
                               θ 
                               i 
                             
                           
                         
                       
                       
                         
                           
                             
                               u 
                               i 
                             
                             , 
                           
                         
                         
                           
                             otherwise 
                             , 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       v 
                       i 
                     
                     = 
                     
                       
                         
                           W 
                           + 
                           r 
                         
                         - 
                         
                           W 
                           - 
                           r 
                         
                       
                       
                         
                           W 
                           + 
                           r 
                         
                         + 
                         
                           W 
                           - 
                           r 
                         
                       
                     
                   
                   , 
                   
                     
                       v 
                       i 
                     
                     ∈ 
                     
                       [ 
                       
                         
                           - 
                           1 
                         
                         , 
                         1 
                       
                       ] 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       u 
                       i 
                     
                     = 
                     
                       
                         
                           W 
                           + 
                           l 
                         
                         - 
                         
                           W 
                           - 
                           l 
                         
                       
                       
                         
                           W 
                           + 
                           l 
                         
                         + 
                         
                           W 
                           - 
                           l 
                         
                       
                     
                   
                   , 
                   
                     
                       u 
                       i 
                     
                     ∈ 
                     
                       [ 
                       
                         
                           - 
                           1 
                         
                         , 
                         1 
                       
                       ] 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       W 
                       + 
                       r 
                     
                     = 
                     
                       
                         ∑ 
                         
                           
                             
                               j 
                               : 
                               
                                 ( 
                                 
                                   
                                     y 
                                     j 
                                   
                                   = 
                                   1 
                                 
                                 ) 
                               
                             
                             &amp; 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   f 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   
                                     x 
                                     j 
                                   
                                   ) 
                                 
                               
                               ≥ 
                               
                                 θ 
                                 i 
                               
                             
                             ) 
                           
                         
                       
                        
                       
                           
                       
                        
                       
                         w 
                         j 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       W 
                       - 
                       r 
                     
                     = 
                     
                       
                         ∑ 
                         
                           
                             
                               j 
                               : 
                               
                                 ( 
                                 
                                   
                                     y 
                                     j 
                                   
                                   = 
                                   
                                     - 
                                     1 
                                   
                                 
                                 ) 
                               
                             
                             &amp; 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   f 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   
                                     x 
                                     j 
                                   
                                   ) 
                                 
                               
                               ≥ 
                               
                                 θ 
                                 i 
                               
                             
                             ) 
                           
                         
                       
                        
                       
                           
                       
                        
                       
                         w 
                         j 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       W 
                       + 
                       l 
                     
                     = 
                     
                       
                         ∑ 
                         
                           
                             
                               j 
                               : 
                               
                                 ( 
                                 
                                   
                                     y 
                                     j 
                                   
                                   = 
                                   1 
                                 
                                 ) 
                               
                             
                             &amp; 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   f 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   
                                     x 
                                     j 
                                   
                                   ) 
                                 
                               
                               &lt; 
                               
                                 θ 
                                 i 
                               
                             
                             ) 
                           
                         
                       
                        
                       
                           
                       
                        
                       
                         w 
                         j 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 and 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     W 
                     - 
                     l 
                   
                   = 
                   
                     
                       ∑ 
                       
                         
                           
                             j 
                             : 
                             
                               ( 
                               
                                 
                                   y 
                                   j 
                                 
                                 = 
                                 
                                   - 
                                   1 
                                 
                               
                               ) 
                             
                           
                           &amp; 
                         
                          
                         
                           ( 
                           
                             
                               
                                 f 
                                 i 
                               
                                
                               
                                 ( 
                                 
                                   x 
                                   j 
                                 
                                 ) 
                               
                             
                             &lt; 
                             
                               θ 
                               i 
                             
                           
                           ) 
                         
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         w 
                         j 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0056]    In each iteration, the optimal parameters of h t (x) and θ i , together with the best scalar feature ƒ * , can be determined by minimizing the error of equation (2): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       f 
                       * 
                     
                     = 
                     
                       
                         
                           arg 
                            
                           
                               
                           
                            
                           min 
                         
                         
                           
                             f 
                             i 
                           
                           ∈ 
                           F 
                         
                       
                        
                       
                           
                       
                        
                       
                         E 
                          
                         
                           ( 
                           
                             f 
                             i 
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where F={ƒ i } i=1   d  is the feature set. Next, the weight distribution is updated for the following iteration by 
         [0000]        w   j   ←w   j ·exp(− y   j ·ƒ * ( x   j ))  (11)
 
         [0057]    Let ω=Σ j   N w j , and w j  is further normalized to be a distribution by 
         [0000]    
       
         
           
             
               
                 
                   
                     w 
                     j 
                   
                   ← 
                   
                     
                       1 
                       ω 
                     
                      
                     
                       
                         w 
                         j 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0058]    In some embodiments each label is associated with one or more stump classifiers, which each may be evaluated in a one-dimensional space. This may significantly reduce the computational complexity of the evaluation. For example, from a training set (Z={z l , y l } l=1   L ) of labeled images, C (one for each label) binary one-against-all partitions {G k } k=1   C  are generated, where each one is for a binary classification task (e.g., a binary classification operation that defines which are positive samples and negative samples for training a binary classifier) for a label. In the k-th task G k , only the k-th label is considered to be positive (e.g., assigned a positive weight), and other labels are considered to be negative (e.g., assigned a negative weight). Each sample (image feature) is associated with a weight w kl  in each task, k=1, . . . , C and l=1, . . . , L. Let N k   +  and N k   −  be the number of positive and negative samples in the k-th task, respectively. Their corresponding weights W k ={w kl } l=1   L  are initialized to 1/N k   +  and 1/N k   − , respectively. In each task G k  these embodiments attempt to train a label classifier H k . 
         [0059]      FIG. 11  includes tables that illustrate example embodiments of one-against-all partitions. The first table  1110  and the second table  1120  show images 1 through N (samples) and their respective bucket values that were generated based on the intermediate vocabulary (note that the bucket values of the embodiments shown in  FIG. 11  are not normalized). For example, for image 3, the bucket values that were generated when image 3 was encoded with the intermediate vocabulary are [141, 7, 5, 24, 87, 612, . . . 34]. Also, each of the images listed in the first table  1110  and the second table  1120  have been assigned one or more labels. For example, in the first table  1110 , images 1-4 have been assigned label A  1111 , and the other images in the first table  1110  have been assigned other labels  1113 . Also, assuming that the first table  1110  and the second table  1120  both relate to the same images, then at least some of the images have been assigned multiple labels. For example, image 6 would have been assigned both label W and label B. 
         [0060]    In the first table  1110 , in a one-against-all partition, only the label A  1111  is considered positive  1115 , and the other labels  1113  are considered negative  1117 . In the second table  1120 , in a one-against-all partition, only the label B  1121  is considered positive  1125 , and the other labels (not shown) are considered negative  1127 . In some embodiments, an image may be associated with more than one label and thus may be included in more than one positive partition. For example, image 1 is associated with both label A  1111  and label B  1121 . Therefore, image 1 is considered positive in both of the one-against-all partitions illustrated by the first table  1110  and the second table  1120 . In some embodiments, each image (sample) is associated with only one label and, accordingly, is included in only one positive partition. The one-against-all partitions may be used to train classifiers for each label. 
         [0061]    In some embodiments to select buckets and to train classifiers the systems and methods perform the following: 
         [0000]    1. Do for t=1, . . . , T: (for each of the T weak-classifiers, where T is the selected number of classifiers): 
         [0062]    1.1 Do for k=1, . . . , C: (for each label): 
         [0063]    (i) Train a weak classifier h k,t  for the task G k  by minimizing equation (2) with the weight distribution W k  associated with the task. 
         [0064]    (ii) Add h k,t  to the k-th label classifier H k ={h k,1 , . . . , h k,t-1 }. 
         [0065]    (iii) Apply h k,t  to equations (11)-(12) to update the weight distribution W k . 
         [0000]    2. Concatenate all the generated weak classifiers to generate a visual vocabulary D h ={h k,t } for k=1, . . . , C and for t=1, . . . , T.
 
3. Output a first visual vocabulary D h  that includes T×C classifiers {h k,t }. Also, a corresponding second visual vocabulary D I  may include up to T×C bucket functions (which can be arranged into a |D I |×1 dimensional array that may have fewer than T×C bucket functions if duplicates are removed) that correspond to the buckets selected as inputs for the classifiers. For example, if the total number of labels C is 2; if buckets 1, 3, 8, 22, 54, and 101 are the most discriminative of label 1; and if buckets 2, 5, 8, 67, 101, and 192 are the most discriminative of label 2, then the respective classifiers that correspond to buckets 1, 2, 3, 5, 8, 22, 54, 67, 101, and 192 are added to the first visual vocabulary D h , and the bucket functions that correspond to buckets 1, 2, 3, 5, 8, 22, 54, 67, 101, and 192 are added to the second visual vocabulary D I . Note that some embodiments may remove duplicate buckets and/or remove duplicate classifiers.
 
         [0066]    Then given a set of features {z m } m=1   M  extracted from an image X I , the features can be encoded with the first vocabulary D h  into a T×C dimensional vector with elements obtained by 
         [0000]    
       
         
           
             
               
                 f 
                 
                   k 
                   , 
                   t 
                 
               
               = 
               
                 
                   1 
                   M 
                 
                  
                 
                   
                     ∑ 
                     
                       m 
                       = 
                       1 
                     
                     M 
                   
                    
                   
                       
                   
                    
                   
                     
                       h 
                       
                         k 
                         , 
                         t 
                       
                     
                      
                     
                       ( 
                       
                         z 
                         m 
                       
                       ) 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where k=1, . . . , C, t=1, . . . , T, and M is the total number of features, which may then be used to determine the labels that apply to the image. Also, the features can be encoded with the second vocabulary D I  into a |D I ×1 dimensional array with elements obtained by 
         [0000]    
       
         
           
             
               
                 μ 
                 k 
               
               = 
               
                 
                   1 
                   M 
                 
                  
                 
                   
                     ∑ 
                     
                       m 
                       = 
                       1 
                     
                     M 
                   
                    
                   
                       
                   
                    
                   
                     
                       b 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           z 
                           m 
                         
                         , 
                         
                           θ 
                           k 
                         
                       
                       ) 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where k=1, . . . , |D I |. 
         [0067]    The embodiments described above may be extended to handle multiple types of features. For the sake of simplicity, let z l   s =x ij   s  and y l   s =y i . A composite training set {Z s } s=1   S , where Z s ={z l   s , y l   s } represents a single type of feature, can be generated. C binary one-against-all partitions {G k } k=1   C  are generated, with G k ={G k   s } s=1   S  taking the multiple types of features into account. Each subset G k   s  is associated with an independent weight distribution W k   s ={w kl   s } l=1   L     s   , in which positive samples and negative samples are respectively initialized to 1/N k   s,+  and 1/N k   s,− . A label classifier H k  is trained for each task G k . 
         [0068]    In some embodiments the systems and methods perform the following: 
         [0000]    1. Do for t=1, . . . , T: (for each of the T weak-classifiers, where T is the selected number of classifiers): 
         [0069]    1.1 Do for k=1, . . . , C: (for each label):
       i) Do for s=1, . . . , S (for each feature type):
           a. Train a weak classifier h k,t   s  for the task G k   s , by minimizing equation (2) with the weight distribution W k   s  associated with the task. Let E s  be the error produced by h k,t   s .   
           ii) Find s*=argmin s  E s .   iii) Apply h k,t   s*  to equations (11)-(12) to update the corresponding weight distribution   iv) Generate an image-level weight distribution from W k   s* ,       
 
         [0000]    
       
         
           
             
               
                 π 
                 i 
               
               = 
               
                 
                   ∑ 
                   
                     
                       z 
                       kl 
                       
                         s 
                         * 
                       
                     
                     ∈ 
                     
                       X 
                       i 
                     
                   
                 
                  
                 
                     
                 
                  
                 
                   w 
                   kl 
                   
                     s 
                     * 
                   
                 
               
             
             , 
             
               
 
             
              
             
               i 
               = 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             N 
             , 
           
         
       
       
         
           
              where π i  is the weight for the image X i , evaluated based on a current optimal feature type s*. 
             v) Update the weight distributions for other feature types s≠s* by propagating π i :
           a. Do for i=1, . . . , N:
               1) Do, for s=1, . . . , S and where s≠s*:
                   A) compute   
                   
               
         
           
         
       
     
         [0000]    
       
         
           
             
               ω 
               S 
             
             = 
             
               
                 ∑ 
                 
                   
                     z 
                     kl 
                     s 
                   
                   ∈ 
                   
                     X 
                     i 
                   
                 
               
                
               
                   
               
                
               
                 w 
                 kl 
                 S 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     
                       
                          for the image X i ; 
                         B) Update the weights 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    
       
         
           
             
               w 
               kl 
               S 
             
             = 
             
               
                 
                   π 
                   i 
                 
                 
                   ω 
                   s 
                 
               
                
               
                 w 
                 kl 
                 S 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     
                       
                          for z lk   s εX i . 
                       
                     
                   
                 
               
             
             vi) Set s t =s* and h k   s     t   =h k,t   s* , and add h k,t   s     t    to the k-th category classifier, H k ={h k,1   s     1   , . . . , h k,t   s     t   }.
 
2. Concatenate all the generated weak classifiers to generate a visual vocabulary D h ={h k,t   s     t   }, k=1, . . . , C; t=1, . . . , T.
 
3. Output: the visual vocabulary D h  that includes T×C classifiers {h k,t   s     t   } and/or a second visual vocabulary D I  that includes ≦T×C bucket functions.
 
           
         
       
     
         [0081]    In these embodiments various types of features are given the same significance. However, in some circumstances these embodiments may over-select certain types of features, so that other types of features are ignored. This may dramatically increase the chance of over-fitting. Assume a prior distribution of the significance {p s } s=1   S  for the S feature types. Some embodiments include a sampling mechanism to select which type of features to minimize in each iteration, instead of searching for all the types of features. In these embodiments the systems and methods perform the following: 
         [0000]    1. Do for t=1, . . . , T: 
         [0082]    1.1 Do for k=1, . . . , C:
       i) Randomly select a feature type s* at a sampling rate of {p s } s=1   s .   ii) Train a weak classifier h k,t   s*  for the task G k   s*  by minimizing equation (2) with the weight distribution W k   s*  associated with the task.   iii) Apply h k,t   s*  to equations (11)(12) to update its corresponding weight distribution W k   s* .   iv) Generate an image-level weight distribution from W k   s* ,       
 
         [0000]    
       
         
           
             
               
                 π 
                 i 
               
               = 
               
                 
                   ∑ 
                   
                     
                       z 
                       kl 
                       
                         s 
                         * 
                       
                     
                     ∈ 
                     
                       X 
                       i 
                     
                   
                 
                  
                 
                     
                 
                  
                 
                   w 
                   kl 
                   
                     s 
                     * 
                   
                 
               
             
             , 
             
               
 
             
              
             
               i 
               = 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             N 
             , 
           
         
       
       
         
           
              where π i  is the weight for the image X i  evaluated based on the current optimal feature type s*. 
             v) Update the weight distributions for other feature types s≠s* by propagating π i :
           a. Do for i=1, . . . , N:
               1) Do for s=1, . . . S, where s≠s*:
                   A) Compute   
                   
               
         
           
         
       
     
         [0000]    
       
         
           
             
               ω 
               S 
             
             = 
             
               
                 ∑ 
                 
                   
                     z 
                     kl 
                     s 
                   
                   ∈ 
                   
                     X 
                     i 
                   
                 
               
                
               
                   
               
                
               
                 w 
                 kl 
                 S 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     
                       
                          for the image X i ; 
                         B) Update the weights, 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    
       
         
           
             
               
                 w 
                 kl 
                 S 
               
               = 
               
                 
                   
                     π 
                     i 
                   
                   
                     ω 
                     s 
                   
                 
                  
                 
                   w 
                   kl 
                   S 
                 
               
             
             , 
           
         
       
       
         
           
             
               
                 
                   
                     
                       
                          for z kl   s εX i . 
                       
                     
                   
                 
               
             
             vii) Set s t =s* and h k,t   s     t   =h k,t   s* , and add h k,t   s     t    to the k-th category classifier H k ={h k,1   s     1   , . . . , h k,t   s     t   }.
 
2. Concatenate all the generated weak classifiers to generate a visual vocabulary D h ={h k,t   s     t   }, k=1, . . . , C; t=1, . . . , T.
 
3. Output the visual vocabulary D h  that includes T×C classifiers {h k,t   s     t   } and/or a second visual vocabulary D I  that includes ≦T×C bucket functions.
 
           
         
       
     
         [0093]    Thus, multiple sets of features {z 1   s , . . . , z M     s     s } s=1   S  in an image can be encoded with the first visual vocabulary D h  to generate a T×C dimensional vector with elements obtained according to 
         [0000]    
       
         
           
             
               
                 f 
                 
                   k 
                   , 
                   t 
                 
               
               = 
               
                 
                   1 
                   
                     M 
                     
                       s 
                       t 
                     
                   
                 
                  
                 
                   
                     ∑ 
                     
                       m 
                       = 
                       1 
                     
                     
                       M 
                       
                         s 
                         t 
                       
                     
                   
                    
                   
                       
                   
                    
                   
                     
                       h 
                       
                         k 
                         , 
                         t 
                       
                       
                         s 
                         t 
                       
                     
                      
                     
                       ( 
                       
                         z 
                         m 
                         
                           s 
                           t 
                         
                       
                       ) 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where k=1, . . . , C and t=1, . . . , T. Also, the features can be encoded with the second vocabulary D I  into a |D I |×1 dimensional array. 
         [0094]    Therefore, some embodiments of the systems and methods described herein select a subset of buckets from the intermediate vocabulary V I  that most efficiently classify the C labels of the training samples, and train classifiers for the labels that use bucket values as respective inputs. 
         [0095]      FIG. 12  illustrates an example embodiment of a method for selecting a subset of buckets. The flow starts in block  1200 , where a bucket index list  1215  is emptied, a weight distribution W  1255  of the intermediate representations  1235  is initialized (e.g., the intermediate representation of each image is assigned a weight), a bucket list  1245  is populated with all B buckets, a label count k is set to 0, and a bucket count t is set to 0. Also, a total number of labels C is determined (for example, by counting all of the labels associated with the labeled intermediate representations  1235 ), and a total number of buckets per label T is determined (for example, in various embodiments, based on received user input, based on a desired vocabulary length, based on a statistical analysis of vocabulary length, based on discriminative effectiveness, based on heuristic techniques, etc.). C and T are assumed to be greater than zero. 
         [0096]    Next, flow proceeds to block  1210 , where it is determined (e.g., by a computing device) if all labels have been considered. If yes (k=C), the flow proceeds to block  1290 . If not (k&lt;C), the flow proceeds to block  1220 , which happens at least the first time the flow reaches block  1210 . In block  1220 , it is determined if bucket selection for the current label is finished. If yes (t=T), then the flow proceeds to block  1280 . If not (t&lt;T), then the flow proceeds to block  1230 , which happens at least the first time the flow reaches block  1220 . 
         [0097]    In block  1230 , based on the labeled intermediate representations  1235 , the optimal bucket u ij*  for the current label c is selected from the bucket list  1245 , for example based on equation (2) using the weight distribution W  1255 . Next, in block  1240 , the index j* of the selected bucket u ij*  is added to the bucket index list  1215 . In some embodiments the index j* is added only if it is not already included in the bucket index list  1215 . The flow then proceeds to block  1250 , where a weak classifier h t  (u ij* ) is trained for the label t and the selected bucket j*, for example for the task G k  by minimizing equation (2) with the weight distribution W k  associated with the task. The weak classifier h t  (u ij* ) is added to a set of classifiers  1217 . 
         [0098]    Then in block  1260 , the weight distribution W  1255  is updated, for example based on equations (11)-(12). Thus, the weight distribution W  1255  of the intermediate representations  1235  may be different for any subsequent iterations of blocks  1230 - 1260 . 
         [0099]    Next, in block  1270 , t is incremented (t=t+1), and flow then returns to block  1220 . If, in block  1220 , bucket selection for the current label k is determined to be finished (t=T), the flow proceeds to block  1280 , where k is incremented (k=k+1) and t is reset to 0 (t=0). The flow then returns to block  1210 . If in block  1210  all labels are determined to have been considered (k=C), then the flow proceeds to block  1290 , where one or more vocabularies are generated based on the buckets listed in the bucket index list  1215  (e.g., the associated bucket functions of the buckets indicated by the bucket index list  1215  are added to a vocabulary D I ) and/or on the classifiers in the set of classifiers  1217  (e.g., the classifiers are added to a vocabulary D h ). 
         [0100]      FIG. 13  illustrates an example embodiment of a method for generating a visual vocabulary. The blocks shown, block  1300 - 1340 , may be performed for each s=1, . . . , S (where S is the total number of feature types). In block  1300 , features are extracted from images (either labeled or unlabeled). The features have d dimensions. Next, in block  1305 , the features are clustered in d-dimensional space. For example, some embodiments perform K-means clustering on the extracted features {z l   s } l=1   L     s    to get K s  cluster centers {∂ k   s } k=1   K     s   , each of which has d s  dimensions. The flow then proceeds to block  1310 , where lower-dimensional buckets Ψ are generated based on the clusters of features. Bucket generation may include determining the respective widths of the buckets. Next, in block  1315 , an intermediate vocabulary V I  is generated from the buckets. For example, in some embodiments, for k=1, . . . , K s , J s  buckets Ψ k   s  are selected using equations (b1)-(b2), the selected buckets Ψ s ={Ψ k   s } k=1   K     s    are grouped, and all the bucket functions of the selected buckets are added to an intermediate visual vocabulary V I ={Ψ s } s=1   S . 
         [0101]    The flow then moves to block  1320 , where labeled training images X i  are encoded based on the intermediate vocabulary V I  to generate intermediate representations μ i , for example using equations (1c)-(1d). Then, in block  1325 , an intermediate training set Z={μ i ,y i } i=1   N  is generated from the intermediate representations μ i  and the labels y i . For each image i, Z includes the respective image labels y i  and the respective intermediate representations p i . Next, in block  1330 , a visual vocabulary D h ={h k,t }, k=1, . . . , C; t=1, . . . , T is generated based on Z, for example by training weak classifiers h k,t  based on Z, and the visual vocabulary D h  includes T×C weak classifiers. Each weak classifier h k,t  generates a label score and is associated with a respective bucket (e.g., an output of the associated bucket function b(z,θ) is used as an input to the weak classifier h k,t ). Flow then moves to block  1335 , where a second visual vocabulary D I , which is a subset of the intermediate vocabulary V I , is generated by selecting the buckets functions that are associated with the weak classifiers in D h  and removing duplicates. Finally, in block  1340 , two visual vocabularies, D I  and D h , are output. 
         [0102]    Multiple sets of features {z 1   s , . . . , z M     s     s } s=1   S  extracted from an image X can be encoded with D I  to get a |D I ×1 dimensional representation {circumflex over (μ)}t. Then {circumflex over (μ)} can be further encoded with D h  to get a representation in the form of a T×C dimensional vector, [h 1,1 ({circumflex over (μ)}), . . . , h k,t  ({circumflex over (μ)}), . . . , h c,T ({circumflex over (μ)})], k=1, . . . , C; t=1, . . . , T. Both of the representations can be used to classify an image X. For example, {circumflex over (μ)} may be used for a fast comparison of features/images, and [h 1,1 ({circumflex over (μ)}), . . . , h k,t ({circumflex over (μ)}), . . . , h C,T ({circumflex over (μ)})] can be used to determine which labels apply to the encoded features/images. 
         [0103]      FIG. 14  illustrates an example embodiment of a method for generating a visual vocabulary. The flow starts in block  1400 , where clusters are generated based on a set of features (e.g., features extracted from a set of images). Next, in block  1405 , buckets and corresponding bucket functions are generated based on the clusters, and, in block  1410 , an intermediate vocabulary is generated based on the buckets and the bucket functions. In some embodiments, blocks  1400 - 1410  are performed as illustrated by  FIG. 4 . The flow then proceeds to block  1415 , where respective intermediate representations for labeled images are generated based on the intermediate vocabulary, for example as illustrated by  FIG. 6 . The flow then moves to block  1420 , where the buckets that are discriminative of the labels are selected and where classifiers are trained for the labels, and then, in block  1425 , a visual vocabulary is generated based on the selected buckets and/or the trained classifiers. In some embodiments blocks  1420 - 1425  are performed as illustrated by  FIG. 12 ,  FIG. 13 , or a combination of both. 
         [0104]      FIG. 15  is a block diagram that illustrates an example embodiment of a system  1500  for generating a visual vocabulary. The system includes a vocabulary generation device  1510  and an object storage device  1520 , both of which include one or more computing devices (e.g., a desktop computer, a server, a PDA, a laptop, a tablet, a smart phone). The vocabulary generation device  1510  includes one or more processors (CPU)  1511 , I/O interfaces  1512 , and storage/RAM  1513 . The CPU  1511  includes one or more central processing units (e.g., microprocessors) and is configured to read and perform computer-executable instructions, such as instructions stored in the modules. The computer-executable instructions may include those for the performance of the methods described herein. The I/O interfaces  1512  provide communication interfaces to input and output devices, which may include a keyboard, a display, a mouse, a printing device, a touch screen, a light pen, an optical storage device, a scanner, a microphone, a camera, a drive, and a network (either wired or wireless). 
         [0105]    Storage/RAM  1513  includes one or more computer readable and/or writable media, and may include, for example, a magnetic disk (e.g., a floppy disk, a hard disk), an optical disc (e.g., a CD, a DVD, a Blu-ray), a magneto-optical disk, a magnetic tape, semiconductor memory (e.g., a non-volatile memory card, flash memory, a solid state drive, SRAM, DRAM), an EPROM, an EEPROM, etc. Storage/RAM  1513  may store computer-readable data and/or computer-executable instructions. The components of the vocabulary generation device  1510  communicate via a bus. 
         [0106]    The vocabulary generation device  1510  also includes a clustering module  1514 , a bucket generation module  1516 , and a bucket selection module  1518 . Modules may include logic, computer-readable data, and/or computer-executable instructions and may be implemented in software (e.g., Assembly, C, C++, C#, Java, BASIC, Perl, Visual Basic), firmware, and/or hardware, and modules are stored on one or more computer-readable media. In some embodiments, the vocabulary generation device  1510  includes additional or less modules, the modules are combined into fewer modules, or the modules are divided into more modules. Though the computing device or computing devices that execute a module actually perform the operations, for purposes of description a module may be described as performing one or more operations. The clustering module  1514  includes computer-executable instructions that may be executed to cause the vocabulary generation device  1510  to generate feature clusters in a native dimensional space based on one or more sets of features and/or form generative visual vocabularies from the sets of features. The bucket generation module  1516  includes computer-executable instructions that may be executed to cause the vocabulary generation device  1510  to generate buckets and respective bucket functions based on the feature clusters and generate an intermediate vocabulary from the buckets. Also, the bucket selection module  1518  includes computer-executable instructions that may be executed to cause the vocabulary generation device  1510  to encode labeled images according to the intermediate vocabulary; determine the buckets that are discriminative of the labels; train classifiers for the buckets and labels; and/or generate one or more revised vocabularies (e.g., D I  and D h ) based on the classifiers, the buckets, and/or the bucket functions. Therefore, the clustering module  1514 , the bucket generation module  1516 , and/or the bucket selection module  1518  may be executed by the vocabulary generation device  1510  to cause the vocabulary generation device  1510  to perform the methods described herein. 
         [0107]    The object storage device  1520  includes a CPU  1522 , storage/RAM  1523 , and I/O interfaces  1524 . The object storage device also includes feature/image storage  1521 . Feature/image storage  1521  includes a computer-readable medium that stores features, images, and/or labels thereon. The members of the object storage device  1520  communicate via a bus. The vocabulary generation device  1510  may retrieve features and images from the feature/image storage  1521  in the object storage device  1520  via a network  1530 . 
         [0108]      FIG. 16A  is a block diagram that illustrates an example embodiment of a system  1600 A for generating a visual vocabulary. The system  1600 A includes a clustering device  1610 , an object storage device  1620 , and a bucket selection device  1640 . The clustering device  1610  includes a CPU  1611 , I/O interfaces  1612 , a clustering module  1613 , and storage/RAM  1614 . When executed, the clustering module  1613  generates feature clusters based on one or more sets of features and/or forms generative visual vocabularies based on the sets of features. The object storage device  1620  includes a CPU  1622 , I/O interfaces  1624 , feature/image storage  1621 , and storage/RAM  1623 . The bucket selection device  1640  includes a CPU  1641 , I/O interfaces  1642 , storage/RAM  1643 , and a bucket selection/generation module  1644 , which combines the instruction in the bucket selection module  1518  and the bucket generation module  1516  shown in  FIG. 15 . The components of each of the devices communicate via a respective bus. In the embodiment shown in  FIG. 16A , the clustering device  1610  generates feature clusters using the clustering module  1613 , and the bucket selection device  1640  generates revised visual vocabularies using the bucket selection/generation module  1644 . The bucket selection device  1640 , the clustering device  1610 , and the object storage device  1620  communicate via a network  1630  to collectively access the features and/or images in the feature/image storage  1621 , cluster the features, generate buckets from the clusters, select the buckets that are discriminative of labels, and train classifiers. Thus, in this embodiment, different devices may store the features/images, cluster the features, generate the buckets, select the discriminative buckets, and train classifiers. 
         [0109]      FIG. 16B  is a block diagram that illustrates an example embodiment of a system  1600 B for generating a visual vocabulary. The system includes a vocabulary generation device  1650  that includes a CPU  1651 , I/O interfaces  1652 , feature/image storage  1653 , a clustering module  1654 , storage/RAM  1655 , and a bucket selection/generation module  1656 . The members of the vocabulary generation device  1650  communicate via a bus. Therefore, in the embodiment shown in  FIG. 16B , one computing device stores the features/images, clusters features, composes generative vocabularies, generates bucket functions, generates intermediate vocabularies, encodes labeled images based on intermediate vocabularies, determines buckets that are discriminative of labels, trains classifiers, and generates revised visual vocabularies. However, other embodiments may organize the components differently than the example embodiments shown in  FIG. 15 ,  FIG. 16A , and  FIG. 16B . 
         [0110]      FIG. 17  illustrates an example embodiment of an image  1701  that is encoded (e.g., described) according to different vocabularies, a first vocabulary IJ /   1715  and a second vocabulary D h    1717 . The image  1701  may be encoded according to the first vocabulary D I    1715  (which includes bucket functions for J buckets) to generate a coded representation μ  1725 , which represents the features in the image as bucket values a fixed-length vector. 
         [0111]    Also, the image  1701  may be encoded according to the second vocabulary D h    1717  (which includes classifiers trained for respective labels) to generate label scores  1727 . The label scores  1727  may be used to determine the labels  1730  (e.g., “dog”, “car”, “tree”) to apply to the image  1701 . For example, the scores for a label may indicate a probability that the associated label applies to the image. When determining if a label applies to the image  1701 , the associated scores may be summed, examined against respective thresholds, and/or used as inputs to other functions. 
         [0112]    The above described devices, systems, and methods can be implemented by supplying one or more computer-readable media having stored thereon computer-executable instructions for realizing the above described operations to one or more computing devices that are configured to read the computer-executable instructions and execute them. In this case, the systems and/or devices perform the operations of the above-described embodiments when implementing the computer-executable instructions. Also, an operating system on the one or more systems and/or devices may implement the operations of the above described embodiments. Thus, the computer-executable instructions and/or the one or more computer-readable media that store the computer-executable instructions thereon constitute an embodiment. 
         [0113]    Any applicable computer-readable medium (e.g., a magnetic disk (including a floppy disk, a hard disk), an optical disc (including a CD, a DVD, a Blu-ray disc), a magneto-optical disk, a magnetic tape, and a solid state memory (including flash memory, DRAM, SRAM, a solid state drive)) can be employed as a computer-readable medium for the computer-executable instructions. The computer-executable instructions may be stored on a computer-readable medium provided on a function-extension board inserted into the device or on a function-extension unit connected to the device, and a CPU provided on the function-extension board or unit may implement the operations of the above-described embodiments. 
         [0114]    The scope of the claims is not limited to the above-described explanatory embodiments and includes various modifications and equivalent arrangements.