Patent Publication Number: US-2015078655-A1

Title: Devices, systems, and methods for large-scale linear discriminant analysis of images

Description:
BACKGROUND 
     1. Technical Field 
     This description generally relates to visual analysis of images. 
     2. Background 
     In the field of image analysis, images are often converted to representations. A representation is often more compact than an image, and comparing representations is often easier than comparing images. Representations can describe various image features, for example scale-invariant feature-transform (SIFT) features, speeded-up robust (SURF) features, local binary patterns (LBP), color histograms (GIST), and histogram-of-oriented-gradients (HOG) features. Representations include Fisher vectors and bag-of-visual features (BOV). However they often produce a very high-dimensional image representation, which makes the image representation difficult to both store and search. 
     SUMMARY 
     In one embodiment a method comprises obtaining a training set of images, wherein the images in the training set of images are each associated with at least one category in a plurality of categories; organizing the images in a training set of images into a category hierarchy based on the training set of images and on the plurality of categories, wherein the category hierarchy identifies each of the categories in the plurality of categories as at least one of a parent category and child category; and generating a subspace map for each parent category based on images associated with respective child categories of the parent category, thereby generating a plurality of subspace maps. 
     In one embodiment, a computing device comprises one or more computer-readable media and one or more processors coupled to the computer-readable media and configured to cause the computing device to perform operations including obtaining a training set of images; assigning the images to a category in a category hierarchy, wherein the category hierarchy identifies each of the categories in the plurality of categories as at least one of a parent category and child category; and generating a subspace map for each parent category based on images assigned to respective child categories of the parent category, thereby generating a plurality of subspace maps. 
     In one embodiment, one or more computer-readable media store instructions that, when executed by one or more computing devices, cause the computer devices to perform operations comprising obtaining a training set of images; assigning the images to a category in a category hierarchy, wherein the category hierarchy identifies each of the categories in the plurality of categories as at least one of a parent category and child category; and generating a subspace map for each parent category based on images assigned to respective child categories of the parent category, thereby generating a plurality of subspace maps. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an example embodiment of the generation of hierarchical subspace maps. 
         FIG. 2  illustrates an example embodiment of a method for generating hierarchical subspace maps. 
         FIG. 3  illustrates an example embodiment of a method for generating hierarchical subspace maps. 
         FIG. 4  illustrates an example embodiment of a flow of operations for generating a subspace map for a category. 
         FIG. 5  illustrates an example embodiment of a method for generating a category hierarchy. 
         FIG. 6  illustrates an example embodiment of a category hierarchy. 
         FIG. 7  illustrates an example embodiment of a method for generating hierarchical subspace maps. 
         FIG. 8  illustrates an embodiment of the encoding of an image based on category subspace maps. 
         FIG. 9  illustrates an example embodiment of a system for generating subspace maps. 
         FIG. 10A  illustrates an example embodiment of a system for generating subspace maps. 
         FIG. 10B  illustrates an example embodiment of a system for generating subspace maps. 
     
    
    
     DESCRIPTION 
     The following disclosure describes certain explanatory embodiments. Other embodiments may include alternatives, equivalents, and modifications. Additionally, the explanatory embodiments may include several novel features, and a particular feature may not be essential to some embodiments of the devices, systems, and methods described herein. 
       FIG. 1  illustrates an example embodiment of the generation of hierarchical subspace maps. A set of training images  101  (“training set”) includes image categories  102  (categories  102 A to  102 X in this example). Each category  102  is associated with one or more images. The categories are organized into a category hierarchy  103 . In some embodiments, every node Z in the category hierarchy  103  is a category  102  found in the training set  101 , and in some embodiments, not every node Z in the category hierarchy  103  is a category  102  found in the training set  101 . 
     Category subspace maps Ψ  105  are then generated for each node Z in the category hierarchy  103 . For a particular node Z i , a category subspace map Ψ  105  is generated based on the images associated with the child nodes of the particular node Z i . Thus, in some embodiments, a respective category subspace map Ψ  105  is generated for each parent node Z (i.e., parent category) in the category hierarchy  103  based on the child nodes (i.e., child categories) of the parent node Z. The category subspace maps Ψ  105  are then added to a collection of category subspace maps  107 . In some embodiments a category subspace map Ψ  105  maps a D-dimensional vector to a lower-dimensional vector. 
     In some embodiments, generating a category subspace map Ψ  105  includes generating a compressed matrix for each node Z, where the compressed matrix has c×c dimensions, and where c is the number of child nodes of the node Z. Thus, for node Z 11 , which has four child nodes, the compressed matrix is a 4×4 dimensional matrix and is generated based on the respective images associated with the four child nodes. Also, for node Z 44 , which has three child nodes, the compressed matrix is a 3×3 dimensional matrix and is generated based on the respective images that are associated with the three child nodes. Then the c−1 most significant eigenvectors are calculated for each of the compressed matrices. For example, for the 4×4 compressed matrix, the three most significant eigenvectors are calculated and are used to generate the category subspace map Ψ  105 . 
       FIG. 2  illustrates an example embodiment of a method for generating hierarchical subspace maps. The blocks of this method and the other methods described herein may be performed by one or more computing devices, for example the systems and devices described herein. Also, although this method and the other methods described herein are each presented in a certain order, some embodiments may perform at least some of the operations in different orders than the presented orders. Examples of possible different orderings include concurrent, overlapping, reordered, simultaneous, incremental, and interleaved orderings. Thus, other embodiments of this method and the other methods described herein may omit blocks, add blocks, change the order of the blocks, combine blocks, or divide blocks into more blocks. 
     The method of  FIG. 2  starts in block  200 , where a training set of images is obtained. Next, in block  210 , the images are assigned to categories in a hierarchy of categories, for example according to the respective category labels that are associated with the images. The flow then moves to block  220 , where, for each parent category in the hierarchy, a subspace map Ψ is generated based on the images of the parent category&#39;s child categories. Finally, in block  230 , the generated subspace maps Ψ are saved on one or more computer-readable media. 
     To generate the subspace maps Ψ in block  220 , some embodiments use linear-discriminant analysis (LDA) or regularized linear-discriminant analysis (R-LDA). LDA is a class-specific technique that uses supervised learning to find a subspace map Ψ of L feature bases, denoted as Ψ=[ψ 1 , . . . , ψ L ], by maximizing the Fisher&#39;s discriminant criterion, which is generally expressed as the ratio of the between- and within-class scatters of training samples (e.g., images). R-LDA attempts to generate a subspace map Ψ by optimizing a regularized version of the Fisher&#39;s discriminant criterion: 
     
       
         
           
             
               
                 
                   
                     Ψ 
                     = 
                     
                       
                         
                           arg 
                            
                           
                               
                           
                            
                           max 
                         
                         Ψ 
                       
                        
                       
                         
                            
                           
                             
                               Ψ 
                               T 
                             
                              
                             
                               S 
                               b 
                             
                              
                             Ψ 
                           
                            
                         
                         
                            
                           
                             
                               η 
                                
                               
                                 ( 
                                 
                                   
                                     Ψ 
                                     T 
                                   
                                    
                                   
                                     S 
                                     b 
                                   
                                    
                                   Ψ 
                                 
                                 ) 
                               
                             
                             + 
                             
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   η 
                                 
                                 ) 
                               
                                
                               
                                 ( 
                                 
                                   
                                     Ψ 
                                     T 
                                   
                                    
                                   
                                     S 
                                     w 
                                   
                                    
                                   Ψ 
                                 
                                 ) 
                               
                             
                           
                            
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     where ηε[0,1] is a regularization parameter, where S b  is a between-class scatter matrix, and where S w  is a within-class scatter matrix. The between-class scatter matrix S b  and the within-class scatter matrix S w  may be calculated according to the following expressions: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           S 
                           b 
                         
                         = 
                           
                          
                         
                           
                             1 
                             N 
                           
                            
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               c 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 
                                   C 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         z 
                                         _ 
                                       
                                       i 
                                     
                                     - 
                                     
                                       z 
                                       _ 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 
                                   ( 
                                   
                                     
                                       
                                         z 
                                         _ 
                                       
                                       i 
                                     
                                     - 
                                     
                                       z 
                                       _ 
                                     
                                   
                                   ) 
                                 
                                 T 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             c 
                           
                            
                           
                             
                               Φ 
                               
                                 b 
                                 , 
                                 i 
                               
                             
                              
                             
                               Φ 
                               
                                 b 
                                 , 
                                 i 
                               
                               T 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                            
                           
                             
                               Φ 
                               b 
                             
                              
                             
                               Φ 
                               b 
                               T 
                             
                           
                         
                         , 
                         
                             
                         
                          
                         and 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       S 
                       w 
                     
                     = 
                     
                       
                         1 
                         N 
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           c 
                         
                          
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               1 
                             
                             
                               c 
                               i 
                             
                           
                            
                           
                             
                               ( 
                               
                                 
                                   z 
                                   ij 
                                 
                                 - 
                                 
                                   
                                     z 
                                     _ 
                                   
                                   i 
                                 
                               
                               ) 
                             
                              
                             
                               
                                 ( 
                                 
                                   
                                     z 
                                     ij 
                                   
                                   - 
                                   
                                     
                                       z 
                                       _ 
                                     
                                     i 
                                   
                                 
                                 ) 
                               
                               T 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     where C i  is the number of samples (e.g., images) in the i-th class, z ij  is the j-th sample (e.g., an image representation in the form of a vector generated at least in part from one or more image features) of the i-th class,  z   i  is the mean of the i-th class,  z  is the mean of the entire training set, 
     
       
         
           
             
               
                 Φ 
                 
                   b 
                   , 
                   i 
                 
               
               = 
               
                 
                   
                     
                       c 
                       i 
                     
                     N 
                   
                 
                  
                 
                   ( 
                   
                     
                       
                         z 
                         _ 
                       
                       i 
                     
                     - 
                     
                       z 
                       _ 
                     
                   
                   ) 
                 
               
             
             , 
           
         
       
     
     and Φ b =[Φ b,1 , . . . , Φ b,C ].
 
In some embodiments, z ij  is a global image feature, such as a Fisher vector, for image j of class i and is generated from a Gaussian mixture model estimated from the SIFT descriptors of all images in the collections of all images in all classes. In other embodiments, z ij  may be a dense sift feature vector for image j of class i. In fact, there are many forms that z ij  may take, whereby z ij  provides a representation of image j of class i.
 
     Also, the dimensionality of Φ b  is D×C, the dimensionality of the between-class scatter matrix Φ b Φ b  is D×D, and D is the dimensionality of the samples (image representations) z ij . When the dimensionality of the samples (image representations) z ij  is high, traditional LDA first applies a PCA operation to reduce the dimensionality of the samples, and then solves a standard LDA problem in the lower-dimensional PCA subspace. But in some cases the dimensionality of the samples (image representations) z ij  is too high to effectively perform PCA, for example when the Fisher-vector representation is a 128,000-dimensional representation. However, R-LDA finds the m (m≦C−1) eigenvectors of a compressed matrix Φ b   T Φ b , which is a matrix of size C×C. The following operations may be performed to generate a subspace map Ψ in block  220 : 
     1) C is set to the number of child categories (child nodes) of the parent category (parent node) for which a subspace map Ψ is being generated. For example, for parent category Z 44 , which has three child categories, C=3. 2) The within-class scatter matrix S, is generated using the image representations (samples) that are associated with the child categories. 3) A compressed matrix Φ b   T Φ b  is generated, and the matrix Φ b  is related to the between-class scatter matrix Φ b Φ b   T . 4) The m (m≦C−1) eigenvectors of the compressed matrix Φ b   T Φ b  that have non-zero eigenvalues, E m =[e 1 , . . . , e m ], are calculated. 5) The first m most significant eigenvectors U m  of the between-class scatter matrix Φ b Φ b   T  and their corresponding eigenvalues Λ m  are calculated based on the m eigenvectors E m  of the compressed matrix Φ b   T Φ b , for example according to U m =Φ b E m  and Λ m =U m   T S b U m . 6) Then the eigenvectors U m  and the eigenvalues Λ m  of the between-class scatter matrix Φ b Φ b   T  are factored to generate a transformation, for example to generate a between-class-scatter subspace transformation H according to H=U m Λ m   −1/2 . 7) The within-class scatter matrix S w  is transformed into the space defined by the eigenvectors U m  of the between-class scatter matrix Φ b Φ b   T , for example by using the between-class-scatter subspace transformation H according to H T S w H, and the eigenvectors P=[p 1 , . . . , p m ] of H T S w H are calculated and sorted in an increasing eigenvalue order. 8) The eigenvectors corresponding to the lowest M (M≦m) eigenvalues in P are selected. P M  and Λ w  respectively denote the selected eigenvectors and their corresponding eigenvalues. 9) The R-LDA subspace map Ψ is generated based on the selected eigenvectors P M  and their respective eigenvalues Λ w , for example according to Ψ=HP M (ηI+(1−η) −1/2 . 
     It should be appreciated that the eigenvalues in this document (e.g., denoted as Λ m  or Λ) are typically represented in diagonal-matrix form, and the set of corresponding eigenvectors are often represented as columns of a matrix where the i-th column contains the eigenvector corresponding to the i-th diagonal element of the eigenvalue matrix. 
     Given an input image representation z (input sample z), its R-LDA-mapped image representation v for a specific subspace map Ψ may be obtained by a linear projection according to 
         v=Ψ   T   z,   (4)
 
     where image representation v is an m-dimensional vector and where the subspace map Ψ effectively maps the input sample (image representation) z from dimensionality D to a lower dimensionality m (m≦C−1). 
     Also, a weight ω may be assigned to each subspace map Ψ. Thus, given an input sample (image representation) z, its corresponding HR-LDA-based image representation V can be obtained by concatenating its projections v ij   T  on each R-LDA subspace map Ψ, for example according to 
         V=[ω   21   ·v   21   T , . . . ,ω lj   ·v   lj   T , . . . ] T ,  (5)
 
     where image representation v lj =Ψ lj   T z, and where ω lj  is a weight that indicates the significance of a corresponding subspace map Ψ lj . Some embodiments set the weight according to the number of training samples included in the category Z lj  that was used to generate the corresponding subspace map T lj . It may reflect the principle that higher-level misclassification should cost more than lower-level misclassification. For example, a misclassification of mammal as bird is more acceptable than a misclassification of mammal as plant. 
     Additionally, some embodiments do not estimate weights. For example, some embodiments consider only the between-class scatters in the hierarchical structure. Some embodiments that consider only the between-class scatters in the hierarchical structure produce the between-class scatter subspace transformation H l+1j . Each training sample z is projected into all the between-class scatter subspaces using the transformations H l+1j  to generate projections b lj , for example according to 
         b   lj   =HT   lj   T   z.   (6)
 
     Some embodiments take only the first m most significant elements in a projection b lj  in order to further reduce dimensionality. A corresponding image representation b for the sample (image representation) z can be obtained by concatenating all the projections b lj  into the between-class scatter subspaces HT lj   T z, for example according to 
         b=[b   21   T   , . . . ,b   lj   T , . . . ] T .  (7)
 
     Also, some embodiments compute the within-class scatter matrix of all the categories by replacing each training sample (image representation) z with its corresponding representation b in equation (3). These embodiments then find the eigenvectors P=[p 1 , . . . , p n ] of the within-class scatter matrix S w  sorted in an increasing eigenvalue order. Let P M  and Λ w  be the first M most significant of the eigenvectors P and their corresponding eigenvalues Λ written in diagonal matrix form, respectively. The embodiments generate the final subspace map Ψ according to Ψ=P M (ηI+(1−η) −1/2 . 
     Also, given an input sample (image representation) z, in some embodiments its corresponding representation v (e.g., HR-LDA-based representation) can be obtained by performing the following: i) generating a representation b using equation (7), and ii) projecting the representation b to the subspace map Ψ according to 
         v=Ψ   T   b.   (8)
 
     Thus, in some embodiments, to generate a subspace map Ψ for a parent node Z that has c child nodes, a compressed matrix Φ b   T Φ b , which is a matrix of size c×c, is generated; the m (m≦c−1) eigenvectors E m  of the compressed matrix Φ b   T Φ b  are calculated; the eigenvectors E m  of the compressed matrix Φ b   T Φ b  are transformed to the space of the between-class scatter matrix Φ b Φ b   T  to find the eigenvectors U m  of the between-class scatter matrix Φ b Φ b   T ; the eigenvalues Λ m  of the between-class scatter matrix Φ b Φ b   T  are calculated using the eigenvectors U m ; the within-class scatter matrix S, is incorporated into the space defined by the eigenvectors U m  of the between-class scatter matrix Φ b Φ b   T  that have non-zero eigenvalues; the eigenvectors P of the within-class scatter matrix S w  in the space defined by the eigenvectors U m  of the between-class scatter matrix Φ b Φ b   T  that have non-zero eigenvalues, as well as the eigenvalues Λ w  (e.g., in diagonal matrix form) of the eigenvectors P, are calculated; and the eigenvectors P of the within-class scatter matrix S w  in the space defined by the eigenvectors U m  of the between-class scatter matrix Φ b Φ b   T  are used to define a subspace map Ψ for the parent node Z. The eigenvectors P that are used to define the subspace map Ψ for the parent node Z may be selected to maximize between-class scatter, minimize within-class scatter, or maximize the ratio of between-class scatter to within-class scatter. 
       FIG. 3  illustrates an example embodiment of a method for generating hierarchical subspace maps Ψ. The flow starts in block  300 , where a training set of images is obtained. Next, in block  310 , the images in the training set are assigned to categories in a category hierarchy. The flow then moves to block  320  where, for each parent category, a compressed matrix Φ b   T Φ b  is generated based on the respective image representations of the parent category&#39;s child categories. Following, in block  330 , the eigenvectors E m  are calculated for each compressed matrix Φ b   T Φ b . 
     The flow then moves to block  340 , where the eigenvectors E m  of each of the compressed matrices Φ b   T Φ b  are transformed to the spaces of the respective between-class scatter matrices Φ b Φ b   T , and the respective eigenvectors U m  and the eigenvalues Λ m  of the between-class scatter matrices Φ b Φ b   T  are calculated. Next, in block  350 , for each between-class scatter matrix Φ b Φ b   T , M eigenvectors are selected, for example to maximize between-class scatter, minimize within-class scatter, or maximize the ratio of between-class scatter to within-class scatter. The operations in block  350  may include incorporating the within-class scatter matrix S w  into the space defined by the eigenvectors U m  and the eigenvalues Λ m  of the between-class scatter matrices Φ b Φ b   T . Thus, the selected M eigenvectors may not be the eigenvectors U m  of the between-class scatter matrices Φ b Φ b   T , but may be other eigenvectors (e.g., the eigenvectors P that incorporate information from the within-class scatter matrix S w ). Finally, in block  360 , for each parent category, a subspace map Ψ is defined based on the selected M eigenvectors. 
       FIG. 4  illustrates an example embodiment of a flow of operations for generating a subspace map Ψ for a category Z. Category Z 21  has five child categories Z 31  to Z 35 , each of which is associated with a respective set of images. To generate a subspace map Ψ for category Z 21 , the image representations of its child categories Z 31  to Z 35  are used as samples z ij  to construct a compressed matrix Φ b   T Φ b    411  and a within-class scatter matrix S w    412 . Because category Z 21  has five child categories Z 31  to Z 35 , the compressed matrix Φ b   T Φ b    411  is a 5×5 dimensional matrix. 
     Next, m eigenvectors E m    413  are calculated for and selected for the compressed matrix Φ b   T Φ b    411 . Because the compressed matrix Φ b   T Φ b    411  is a 5×5 dimensional matrix, in some embodiments m is selected to be fewer than 5 (i.e., m≦4). The eigenvectors E m    413  are then transformed in block  414  to the space of a between-class scatter matrix Φ b Φ b   T  to generate the first m most significant eigenvectors U m    415  of the between-class scatter matrix Φ b Φ b   T  and their corresponding eigenvalues Λ m , for example according to U m =Φ b E m  and Λ m =U m   T S b U m . Then a between-class-scatter-subspace transformation H  416  is generated based on the first m most significant eigenvectors U m    415  of the between-class scatter matrix φ b   T Φ b  and their corresponding eigenvalues Λ m , for example according to H=U m Λ m   −1/2 . 
     Next, in block  417 , the between-class-scatter-subspace transformation H  416  and the within-class scatter matrix S w    412  are used to incorporate the within-class scatter matrix S w    412  into the space defined by the eigenvectors U m    415  and generate M eigenvectors P M  and their corresponding eigenvalues Λ w    418 . The number of M eigenvectors P M    418  may be less than or equal to the number of m eigenvectors E m    413  for the compressed matrix Φ b   T Φ b    411  (M≦m). A category subspace map Ψ  405  for the category Z 21  is then generated based on the between-class-scatter-subspace transformation H  416  and the eigenvectors P M    418  and their corresponding eigenvalues Λ w , for example according to Ψ=HP M (ηI+(1−η) −1/2 . Also, a weight ψ  419  may be calculated for the subspace map Ψ, for example based on the number of images associated with the child categories Z 31  to Z 35  of the category Z 21  or based on the number of child categories of the category Z 21 . 
       FIG. 5  illustrates an example embodiment of a method for generating a category hierarchy. The flow starts in block  500 , where a set of categories, each of which is associated with respective images, is obtained. Next, in block  510 , the set of categories is partitioned into two or more unconsidered child groups of categories. Some embodiments use k-means clustering that is based on a semantic distance, which considers the similarity of the categories based on a category hierarchy (e.g., WordNet). Given two category labels, L x  and L y , the semantic distance d s  (L x , L y ) between them may be defined according to 
         d   s ( L   x   ,L   y )= hc ( L   x   ,L   y ),  (9)
 
     where hc(L x , L y ) is the hierarchical classification cost, and it may be equal to the height of the lowest common ancestor of L x  and L y  in the category hierarchy, divided by the maximum possible height. As a result, for example, the definition of equation (9) may make the distance between bears and dogs closer than the distance between apples and dogs. 
     Some embodiments use k-means clustering based on a sample distance, which considers the similarity of the samples that belong to each category. Let (μ x , Σ x ) and (μ y m Σ y ) be the sample mean and covariance of the categories L x  and L y , respectively. In some embodiments the sample distance is the Mahalanobis distance, 
     
       
         
           
             
               
                 
                   
                     
                       d 
                       m 
                     
                      
                     
                       ( 
                       
                         
                           L 
                           x 
                         
                         , 
                         
                           L 
                           y 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       2 
                     
                      
                     
                       
                         ( 
                         
                           
                             μ 
                             x 
                           
                           - 
                           
                             μ 
                             y 
                           
                         
                         ) 
                       
                       T 
                     
                      
                     
                       
                         ( 
                         
                           
                             Σ 
                             x 
                           
                           + 
                           
                             Σ 
                             y 
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       
                         ( 
                         
                           
                             μ 
                             x 
                           
                           - 
                           
                             μ 
                             y 
                           
                         
                         ) 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     If Σ x =Σ y =I, then the Mahalanobis distance is equivalent to the Euclidean distance d e (L x , L y )=∥μ x −μ y ∥. Also, some embodiments use the Kullback-Leibler (KL) divergence distance and the Bhattycharya distance. In addition, clustering can be performed in an augmented space using a sample space and a category label space. 
     The flow then moves to block  520 , where, for the next group of unconsidered child categories, the operations in block  530  and  540  are performed. In block  530 , it is determined if the number of categories in the child group exceeds a threshold. If yes, then the flow moves to block  540 , where the child group of categories is partitioned into two or more child groups of categories, which are designated as children of the child group of categories considered in block  530 . For example, if the number of categories in child group “A” is determined to exceed the threshold in block  530 , then child group “A” is partitioned into child groups “B” and “C” in block  540 , and child groups “B” and “C” are designated as children of child group “A”. Also, these two or more child groups are identified as unconsidered by block  550 . 
     If in block  530  it is determined that the number of categories in the child group does not exceed a threshold, or after block  540  is performed, then the flow moves to block  550 . In block  550  it is determined if all child groups have been considered. If not, then the flow returns to block  520 , where the next child group is considered. If yes, then the flow proceeds to block  560 , where the hierarchy is output or saved to a computer-readable medium. 
     In some embodiments, every category in the set of categories is designated as a child category but not a parent category. Thus, every category in the set of categories is a node in the lowest level of the hierarchy. Also, categories that are not in the original set of categories may be added to the hierarchy, for example in blocks  510  or  540 . Thus, if the original categories include dog, cat, bird, whale, rodent, bush, tree, vine, grass, and moss, the new categories animal and plant may be added to the hierarchy during the generation of the hierarchy. 
       FIG. 6  illustrates an example embodiment of a category hierarchy. The category in level 1 is a parent category but not a child category. The categories in levels 2-4 are both parent categories and child categories. Finally, the categories in level 5 are child categories but not parent categories. 
       FIG. 7  illustrates an example embodiment of a method for generating hierarchical subspace maps W. The flow starts in block  700 , where a set of categories Z 1 ={Z 1j } j=1   K     1   , each of which is associated with respective images, is obtained. Also, a counter l is set to one (l=1), and a threshold K min  is set. K min  defines the minimal number of categories required to perform a partition. Next, in block  705 , the set of categories is partitioned into two or more groups of child categories of a parent category, and the parent category may be either a new category or a category that is already included in the set of categories. Thus, the set Z l  is partitioned into K l+1  child groups {Z l+1j } j=1   K     l+1   , with each one containing at least two categories of Z l . The flow then moves to block  710 , where a subspace map Ψ l  is generated for the parent group using the K l+1  child groups {Z l+1j } j=1   K     l+1   , for example according to  FIG. 4 . Also, the K l+1  child groups are designated as Z l+1  groups of categories, for example according to Z l+1 ={Z l+1j } j=1   K     l+1   ; all the child categories of Z l+1j  are relabeled with the same label as Z l+1j ; and the counter  1  is incremented (l=l+ 1 ). 
     Next, at least some of the operations in block  715  are performed for the next group of categories. In block  720 , it is determined if the number of categories K l  in the group Z l  exceeds a threshold K min : K l &gt;K min . If not, then the flow proceeds to block  735 . If yes, then the flow proceeds to block  725 , where the group Z l  is partitioned into K l+1  child groups {Z l+1j}     j=1     K     l+1   , each of which contains at least one category of Z l . The flow then moves to block  730 , where a subspace map Ψ l  is generated for the parent group using the K l+1  child groups {Z l+1j } j=1   K     l+1   , for example according to  FIG. 4 . Also, the K l+1  child groups are designated as Z l+1  groups of categories, for example according to Z l+1 ={Z l+1j } j=1   K     l+1   ; all the child categories of Z l+1j  are relabeled with the same label as Z l+1j ; and the counter l is incremented (l=l+1). The flow then moves to block  735 . 
     In block  735  it is determined if all of the groups have been considered. If not, the flow returns to block  715 . If yes, then the flow moves to block  740 , where the generated subspace maps {Ψ lj } l,j , are output. 
       FIG. 8  illustrates an embodiment of the encoding of an image  800  based on category subspace maps Ψ  811 . The image  800  is obtained by an encoding module  818 . Modules include logic, computer-readable data, or computer-executable instructions, and may be implemented in software (e.g., Assembly, C, C++, C#, Java, BASIC, Perl, Visual Basic), hardware (e.g., customized circuitry), or a combination of software and hardware. In some embodiments, the system includes additional or fewer 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 the software instructions in a module perform the operations, for purposes of description a module may be described as performing one or more operations. 
     The encoding module  818  generates an initial representation z of the image  800  (e.g., using feature extraction to generate a Fisher vector, a bag-of-visual words) and calculates the projections of the representation z of the image  800  based on each of the category subspace maps Ψ  811  to generate category-subspace projections v  821 , for example according to equation (4) or equation (8). Then a final image representation V  823  is generated based on the category-subspace projections v  821 , for example according to equation (5). 
       FIG. 9  illustrates an example embodiment of a system for generating subspace maps. The system includes a representation-generation device  910  and an image-storage device  920 . The representation-generation device  910  includes one or more processors (CPU)  911 , I/O interfaces  912 , and storage/memory  913 . The CPU  911  includes one or more central processing units, which include microprocessors (e.g., a single core microprocessor, a multi-core microprocessor) or other circuits, and is configured to read and perform computer-executable instructions, such as instructions stored in storage or in memory (e.g., software in modules that are stored in storage or memory). The computer-executable instructions may include those for the performance of the operations described herein. The I/O interfaces  912  include 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). 
     The storage/memory  913  includes one or more computer-readable or computer-writable storage media. A computer-readable storage medium does not include transitory, propagating signals and is a tangible article of manufacture, 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, magnetic tape, and semiconductor memory (e.g., a non-volatile memory card, flash memory, a solid-state drive, SRAM, DRAM, EPROM, EEPROM). The storage/memory  913  is configured to store computer-readable data or computer-executable instructions. The components of the representation-generation device  910  communicate via a bus. 
     The representation-generation device  910  also includes a hierarchy-generation module  916 , a subspace-generation module  917 , and an encoding module  918 . In some embodiments, the representation-generation device  910  includes additional or fewer modules, the modules are combined into fewer modules, or the modules are divided into more modules. The hierarchy-generation module  916  contains instructions that, when executed, or circuits that, when activated, cause the representation-generation device  910  to obtain a training set of categories and associated images and generate a category hierarchy based in the obtained training set. The subspace-generation module  917  contains instructions that, when executed, or circuits that, when activated, cause the representation-generation device  910  to obtain a training set of categories and associated images, obtain a category hierarchy, and generate respective subspace maps based on the categories. The encoding module  918  contains instructions that, when executed, or circuits that, when activated, cause the representation-generation device  910  to obtain an image representation and encode the image representation based on category subspace maps. 
     The image-storage device  920  includes a CPU  922 , storage/memory  923 , I/O interfaces  924 , and image storage  921 . The image storage  921  includes one or more computer-readable media that are configured to store images. The image-storage device  920  and the representation-generation device  910  communicate via a network  990 . In some embodiments, the image storage device may not store the original images, but instead may store representations of the images. 
       FIG. 10A  illustrates an example embodiment of a system for generating subspace maps. The system includes an image-storage device  1020 , a subspace-generation device  1010 , and a representation-generation device  1040 , which communicate via a network  1090 . The image-storage device  1020  includes one or more CPUs  1022 , I/O interfaces  1024 , storage/memory  1023 , and image storage  1021 . The subspace-generation device  1010  includes one or more CPUs  1011 , I/O interfaces  1012 , storage/memory  1014 , and a subspace-generation module  1013 , which is a combination of the hierarchy-generation module  916  and subspace-generation module  917  in  FIG. 9 . The representation-generation device  1040  includes one or more CPUs  1041 , I/O interfaces  1042 , storage/memory  1043 , and an encoding module  1044 . 
       FIG. 10B  illustrates an example embodiment of a system for generating subspace maps. The system includes a representation-generation device  1050 . The representation-generation device  1050  includes one or more CPUs  1051 , I/O interfaces  1052 , storage/memory  1053 , an image-storage module  1054 , a hierarchy-generation module  1055 , a subspace-generation module  1056 , and an encoding module  1057 . Thus, in this example embodiment of the subspace-generation device  1050 , a single device performs all the operations and stores all the applicable information. 
     The above-described devices, systems, and methods can be implemented by providing one or more computer-readable media that contain computer-executable instructions for realizing the above-described operations to one or more computing devices that are configured to read and execute the computer-executable instructions. Thus, the systems or devices perform the operations of the above-described embodiments when executing the computer-executable instructions. Also, an operating system on the one or more systems or devices may implement at least some of the operations of the above-described embodiments. Therefore, the computer-executable instructions or the one or more computer-readable media that contain the computer-executable instructions constitute an embodiment. 
     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 semiconductor memory (including flash memory, DRAM, SRAM, a solid state drive, EPROM, EEPROM)) can be employed as a computer-readable medium for the computer-executable instructions. The computer-executable instructions may be stored on a computer-readable storage medium that is provided on a function-extension board inserted into a device or on a function-extension unit connected to the device, and a CPU provided on the function-extension board or unit may implement at least some of the operations of the above-described embodiments. 
     The scope of the claims is not limited to the above-described embodiments and includes various modifications and equivalent arrangements. Also, as used herein, the conjunction “or” generally refers to an inclusive “or,” though “or” may refer to an exclusive “or” if expressly indicated or if the context indicates that the “or” must be an exclusive “or.”