Abstract:
A method of localizing landmark points and fitting appearance based models to image data. Image products are computed efficiently which improves the computational cost and improves performance of fitting algorithms for such models.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    Here, relevant background material is presented and the relation to prior art explained. The technical details of the invention is presented in the following section Detailed Description and in the research paper [?]. 
         [0002]    Shape and appearance models can be applied to solve many different problems either by using the fitted model itself or using the model to locate landmark points in images. The most successful applications to this day are the analysis of medical images and images of faces, cf. e.g. [?] for examples. Early work like e.g. the active shape models [?] modeled only the variations in shape. This work was later extended so that the models also include the variations of the appearance (i.e. the image color) as well as the shape, the active appearance models [?] (AAM). 
         [0003]    The building of such a model is done offline on a training set of annotated objects. In the online event of a new image containing an object of the modeled category, the model parameters have to be found by fitting the model to the image data. It is in this part that the contribution of the invention lies, by proposing an algorithm that drastically improves the computational cost of this fitting. There are several methods to chose from when performing this fitting. Many of them, most notably the robust simultaneous inverse compositional algorithm introduced in [?], involves the computation of a hessian matrix at each step of the optimization. 
         [0004]    In the following section the invention, a way to speed up the computation of certain types of image inner products where the images are in a linear space, is introduced. This type of inner product is used e.g. in the computation of the hessian mentioned above. The computation of this hessian is the most expensive step of this iterative procedure and therefore the invention has considerable impact in reducing the computational load of systems and applications for image analysis and recognition. Under normal model assumptions the difference is a factor  9  to a factor  650  for the hessian computation and a factor  3  to a factor  7  of the actual model fitting, depending on image size. 
         [0005]    The issue of computational efficiency has been addressed previously in the literature, see for instance [?]. The efficiency enhancement described in this reference is only achieved at a considerable loss in fitting performance [?]. The present invention gives a similar speedup, while maintaining fitting accuracy. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0006]      FIG. 1  shows an example of a shape and appearance representation for a face model, including landmark points. 
           [0007]      FIG. 2  shows an example of a system or device for obtaining images, analyzing, and responding to results from the landmark localization. 
       
    
    
     ACTIVE APPEARANCE MODELS 
       [0008]    Active appearance models (AAMs) [?, ?] are linear shape and appearance models that model a specific visual phenomenon. AAMs have successfully been applied to face modeling with applications such as face synthesis, face recognition [?, ?] and even facial action recognition [?] and medical image analysis with application such as diagnostics and aiding measurement. 
         [0009]    In the AAM framework the shape is modeled as a base shape s 0  with a linear combination of shape modes S i  as 
         [0000]    
       
         
           
             
               
                 
                   
                     S 
                     = 
                     
                       
                         S 
                         0 
                       
                       + 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           m 
                         
                          
                         
                           
                             p 
                             i 
                           
                            
                           
                             s 
                             i 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where p i  are the shape coefficients and the shape s is represented as the 2D coordinates of the v vertices of a model mesh as S=(x 1 , y 1 , . . . , x v , y v ), cf.  FIG. 1 . We will use p to denote the vector of p i . 
         [0010]    The appearance is modeled completely analogous as a base appearance image A 0  together with a linear combination of appearance modes A i  as 
         [0000]    
       
         
           
             
               
                 
                   
                     A 
                     = 
                     
                       
                         A 
                         0 
                       
                       + 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           
                             λ 
                             i 
                           
                            
                           
                             A 
                             i 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where λ i  are the appearance coefficients and an appearance image is given by the set of pixels inside the same model mesh as above. We will use λ to denote the vector of λ i . The shape and appearance modes are found using Principal Component Analysis (PCA) on aligned training data. 
         [0011]    To be able to fit a model instance into an image additional parameters q are needed to describe scaling, rotation and translation. Setting 
         [0000]    
       
         
           
             
               r 
               = 
               
                 ( 
                 
                   
                     
                       q 
                     
                   
                   
                     
                       p 
                     
                   
                 
                 ) 
               
             
             , 
           
         
       
     
         [0000]    the warp W(r) is the piecewise affine warp from the base mesh S 0  to the current AAM shape under r. Thus I(W(r)) is an image on S 0  in which the pixel intensities are taken from the image I according to the warp W(r). 
         [0012]    Simultaneous Inverse Compositional Image Alignment Algorithm 
         [0013]    The simultaneous inverse compositional image alignment algorithm (SICIA) [?] is an algorithm for fitting the AAM to an input image I simultaneously with regards to appearance and shape. Inverse compositional signifies how the warp parameters r are updated. 
         [0014]    The overall goal of the algorithm is to minimize the difference between the synthesized image of the model and the image I as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             n 
                           
                            
                           
                             
                               λ 
                               i 
                             
                              
                             
                               A 
                               i 
                             
                           
                         
                         - 
                         
                           I 
                            
                           
                             ( 
                             
                               W 
                                
                               
                                 ( 
                                 r 
                                 ) 
                               
                             
                             ) 
                           
                         
                       
                       ] 
                     
                     2 
                   
                   , 
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where λ 0 =1 (note the summation limits). In the inverse compositional formulation the minimization of equation (3) is carried out by iteratively minimizing 
         [0000]    
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           n 
                         
                          
                         
                           
                             ( 
                             
                               
                                 λ 
                                 i 
                               
                               + 
                               
                                 Δλ 
                                 i 
                               
                             
                             ) 
                           
                            
                           
                             
                               A 
                               i 
                             
                              
                             
                               ( 
                               
                                 W 
                                  
                                 
                                   ( 
                                   
                                     Δ 
                                      
                                     
                                         
                                     
                                      
                                     r 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                       - 
                       
                         I 
                          
                         
                           ( 
                           
                             W 
                              
                             
                               ( 
                               r 
                               ) 
                             
                           
                           ) 
                         
                       
                     
                     ] 
                   
                   2 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    simultaneously with respect to both λ and r. Note that the update of the warp is calculated on s 0  and not on the present AAM instance. The new parameters r k+1  are then given as a composition of the warp update Δr k  and the present r k  so that 
         [0000]        W ( r   k+1 )← W ( r   k )∘ W (Δ r   k ) −1 .  (5)
 
         [0015]    This means the gradient of the warp is constant [?]. The appearance parameters are updated by λ k+1 ←λ k +Δλ k . Performing a first order Taylor expansion on expression (4) gives 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         E 
                         + 
                         
                           
                             ( 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 n 
                               
                                
                               
                                 
                                   λ 
                                   i 
                                 
                                  
                                 
                                   ∇ 
                                   
                                     A 
                                     i 
                                   
                                 
                               
                             
                             ) 
                           
                            
                           
                             
                               ∂ 
                               W 
                             
                             
                               ∂ 
                               r 
                             
                           
                            
                           Δ 
                            
                           
                               
                           
                            
                           r 
                         
                         + 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             n 
                           
                            
                           
                             
                               A 
                               i 
                             
                              
                             
                               Δλ 
                               i 
                             
                           
                         
                       
                       ] 
                     
                     2 
                   
                   , 
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the error image is 
         [0000]    
       
         
           
             
               
                 
                   E 
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         n 
                       
                        
                       
                         
                           λ 
                           i 
                         
                          
                         
                           A 
                           i 
                         
                       
                     
                     - 
                     
                       
                         I 
                          
                         
                           ( 
                           
                             W 
                              
                             
                               ( 
                               r 
                               ) 
                             
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    For notational convenience set 
         [0000]    
       
         
           
             t 
             = 
             
               
                 
                   ( 
                   
                     
                       
                         r 
                       
                     
                     
                       
                         λ 
                       
                     
                   
                   ) 
                 
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 Δ 
                  
                 
                     
                 
                  
                 t 
               
               = 
               
                 
                   ( 
                   
                     
                       
                         
                           Δ 
                            
                           
                               
                           
                            
                           r 
                         
                       
                     
                     
                       
                         Δλ 
                       
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0000]    Also define the steepest descent images as 
         [0000]    
       
         
           
             
               
                 
                   
                     SD 
                     Σ 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             ( 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 n 
                               
                                
                               
                                 
                                   λ 
                                   i 
                                 
                                  
                                 
                                   ∇ 
                                   
                                     A 
                                     i 
                                   
                                 
                               
                             
                             ) 
                           
                            
                           
                             
                               ∂ 
                               W 
                             
                             
                               ∂ 
                               
                                 r 
                                 1 
                               
                             
                           
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           
                             ( 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 n 
                               
                                
                               
                                 
                                   λ 
                                   i 
                                 
                                  
                                 
                                   ∇ 
                                   
                                     A 
                                     i 
                                   
                                 
                               
                             
                             ) 
                           
                            
                           
                             
                               ∂ 
                               W 
                             
                             
                               ∂ 
                               
                                 r 
                                 
                                   m 
                                   + 
                                   4 
                                 
                               
                             
                           
                         
                         , 
                         
                           A 
                           1 
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           A 
                           n 
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0016]    The +4 comes from the fact that in a 2D case one needs 4 parameters in q. Using these reformulations (6) can be expressed as 
         [0000]      [E−SD Σ Δt] 2 ,  (9)
 
         [0000]      which is minimized by 
         [0000]      Δt=−H −1 SD Σ   T E,  (10)
 
         [0000]    where the hessian is given by 
         [0000]      H=SD Σ   T SD Σ .  (11)
 
       DETAILED DESCRIPTION 
       [0017]    In a preferred embodiment of the invention, a method for image model fitting and landmark localization is presented, the method comprising the steps of; —computation of the hessian matrix using the space defined by the image model to pre-compute the image inner products, —fitting the appearance model to image data, —storing the final model and landmark points for further use. 
         [0018]    Yet another embodiment of the present invention, a computer program stored in a computer readable storage medium and executed in a computational unit for image model fitting and landmark localization comprising the steps of: —computation of the hessian matrix using the space defined by the image model to pre-compute the image inner products, —fitting the appearance model to image data, —storing the final model and landmark points for further use. 
         [0019]    In another embodiment of the present invention, a system for image model fitting and landmark localization containing a computer program for image model fitting and landmark localization comprising the steps of: —computation of the hessian matrix using the space defined by the image model to pre-compute the image inner products, —fitting the appearance model to image data, —storing the final model and landmark points for further use. 
         [0020]    In another embodiment of the present invention a system or device is used for obtaining images, analyzing, and responding to results from the landmark localization, as may be seen in  FIG. 2 . Such a system may include at least one image acquisition device  101  and a computational device  100 . 
         [0021]    The above mentioned and described embodiments are only given as examples and should not be limiting to the present invention. Other solutions, uses, objectives, and functions within the scope of the invention as claimed in the below described patent claims should be apparent for the person skilled in the art. 
         [0022]    Below follows a detailed description of the invention. 
         [0023]    Linear Space Inner Product 
         [0024]    In this section we will detail a method of efficiently computing image inner products and show how this improves the computation of the hessian matrix in (11). 
         [0025]    Formulating Inner Products using Linear Projections 
         [0026]    Assume that the image I, represented as a vector, can be expressed as a linear combination of g appearance images A i  just as in equation (2). The inner product I b   T I c  of two such images I b  and I c  is an operation taking as many multiplications to complete as there are elements (pixels) in the vector (image). If we rewrite the inner product using the appearance image representation it becomes 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       0 
                     
                     g 
                   
                    
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       g 
                     
                      
                     
                       
                         λ 
                         
                           b 
                           , 
                           i 
                         
                       
                        
                       
                         λ 
                         
                           c 
                           , 
                           j 
                         
                       
                        
                       
                         a 
                         
                           i 
                           , 
                           j 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the scalar a i,j =A i   T A j . The computations of all a i,j  can be done offline since they are fixed once the appearance images A i  are chosen. Assuming that we have obtained the coefficients λ b,i  and λ c,i  the inner product can be computed using 2g 2  multiplications instead of as many multiplications as there are pixels. 
         [0027]    Linear Space Inner Product (LSIP) Applied to AAM 
         [0028]    In one hessian calculation (n+m+4) 2  number of scalar products are performed while λ stay constant. This means that the hessian calculation is very suited to be performed using the LSIP. 
         [0029]    Studying equations (8) and (11), one sees that the hessian will have four distinct areas computation-wise. 
         [0030]    The Upper Left Quadrant. 
         [0031]    Here each hessian element is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ij 
                       ul 
                     
                     = 
                     
                       
                         
                           ( 
                           
                             
                               ( 
                               
                                 
                                   ∑ 
                                   
                                     k 
                                     = 
                                     0 
                                   
                                   n 
                                 
                                  
                                 
                                   
                                     λ 
                                     k 
                                   
                                    
                                   
                                     ∇ 
                                     
                                       A 
                                       k 
                                     
                                   
                                 
                               
                               ) 
                             
                              
                             
                               
                                 ∂ 
                                 W 
                               
                               
                                 ∂ 
                                 
                                   r 
                                   i 
                                 
                               
                             
                           
                           ) 
                         
                         T 
                       
                        
                       
                         ( 
                         
                           
                             ( 
                             
                               
                                 ∑ 
                                 
                                   l 
                                   = 
                                   0 
                                 
                                 n 
                               
                                
                               
                                 
                                   λ 
                                   l 
                                 
                                  
                                 
                                   ∇ 
                                   
                                     A 
                                     l 
                                   
                                 
                               
                             
                             ) 
                           
                            
                           
                             
                               ∂ 
                               W 
                             
                             
                               ∂ 
                               
                                 r 
                                 j 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0000]    with i,jε[1,m+4]. Analogously to Section 2(′)@ we rewrite 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ij 
                       ul 
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         n 
                       
                        
                       
                         
                           ∑ 
                           
                             l 
                             = 
                             0 
                           
                           n 
                         
                          
                         
                           
                             λ 
                             k 
                           
                            
                           
                             λ 
                             l 
                           
                            
                           
                             h 
                             kl 
                             
                               ul 
                               , 
                               i 
                               , 
                               j 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where 
         [0000]    
       
         
           
             
               h 
               kl 
               
                 ul 
                 , 
                 i 
                 , 
                 j 
               
             
             = 
             
               
                 
                   ( 
                   
                     
                       ∇ 
                       
                         A 
                         k 
                       
                     
                      
                     
                       
                         ∂ 
                         W 
                       
                       
                         ∂ 
                         
                           r 
                           i 
                         
                       
                     
                   
                   ) 
                 
                 T 
               
                
               
                 
                   ( 
                   
                     
                       ∇ 
                       
                         A 
                         l 
                       
                     
                      
                     
                       
                         ∂ 
                         W 
                       
                       
                         ∂ 
                         
                           r 
                           j 
                         
                       
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0000]    Moving one multiplication outside and limiting the inner summation limit gives 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ij 
                       ul 
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         n 
                       
                        
                       
                         
                           ∑ 
                           
                             l 
                             = 
                             k 
                           
                           n 
                         
                          
                         
                           
                             λ 
                             kl 
                           
                            
                           
                             h 
                             kl 
                             
                               ul 
                               , 
                               i 
                               , 
                               j 
                             
                           
                         
                       
                     
                   
                   , 
                   
                       
                   
                    
                   
                     
                       λ 
                       kl 
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 λ 
                                 k 
                               
                                
                               
                                 λ 
                                 l 
                               
                             
                           
                           
                             
                               
                                 if 
                                  
                                 
                                     
                                 
                                  
                                 i 
                               
                               = 
                               j 
                             
                           
                         
                         
                           
                             
                               2 
                                
                               
                                   
                               
                                
                               
                                 λ 
                                 k 
                               
                                
                               
                                 λ 
                                 l 
                               
                             
                           
                           
                             
                               
                                 if 
                                  
                                 
                                     
                                 
                                  
                                 i 
                               
                               ≠ 
                               
                                 j 
                                 . 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0032]    The Lower Left and Upper Right Quadrant. 
         [0033]    The upper right and lower left quadrants are symmetrical and therefore only the upper right quadrant will be described. The hessian elements are given by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ij 
                       ur 
                     
                     = 
                     
                       
                         
                           ( 
                           
                             
                               ( 
                               
                                 
                                   ∑ 
                                   
                                     k 
                                     = 
                                     0 
                                   
                                   n 
                                 
                                  
                                 
                                   
                                     λ 
                                     k 
                                   
                                    
                                   
                                     ∇ 
                                     
                                       A 
                                       k 
                                     
                                   
                                 
                               
                               ) 
                             
                              
                             
                               
                                 ∂ 
                                 W 
                               
                               
                                 ∂ 
                                 
                                   r 
                                   i 
                                 
                               
                             
                           
                           ) 
                         
                         T 
                       
                        
                       
                         A 
                         j 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
         [0000]    with iε[1,m+4], jε[m+5, n+m+4]. This can be transformed into 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ij 
                       ur 
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         n 
                       
                        
                       
                         
                           λ 
                           k 
                         
                          
                         
                           h 
                           k 
                           
                             ur 
                             , 
                             i 
                             , 
                             j 
                           
                         
                       
                     
                   
                   , 
                   
                       
                   
                    
                   
                     
                       h 
                       kl 
                       
                         ur 
                         , 
                         i 
                         , 
                         j 
                       
                     
                     = 
                     
                       
                         
                           ( 
                           
                             
                               ∇ 
                               
                                 A 
                                 k 
                               
                             
                              
                             
                               
                                 ∂ 
                                 W 
                               
                               
                                 ∂ 
                                 
                                   r 
                                   i 
                                 
                               
                             
                           
                           ) 
                         
                         T 
                       
                        
                       
                         
                           A 
                           j 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0034]    The Lower Right Quadrant. 
         [0035]    This is simply the scalar products of the appearance images. This quadrant is therefore the identity matrix. 
         [0036]    Theoretical Gain of Using the Linear Space Inner Product 
         [0037]    Table 1 summarizes the time complexity of one iteration of SICIA [?]. The left column is the calculation performed and a reference to the corresponding equation (s). The first row is the computation of the error image including warping of input image and the image composite with a model appearance instance. The second step is the calculation of the steepest descent images and the third row is the scalar product of the steepest descent images and the error image. The fourth and main step is the calculation of the hessian and its inverse. 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Summary of the time complexity for one iteration of SICIA. 
               
             
          
           
               
                   
                 Calculation 
                 SICIA-Original 
                 SICIA-LSIP 
               
               
                   
                   
               
               
                   
                 E,  (7)   
                 O((n + m + 4)N 
                 O((n + m + 4)N 
               
               
                   
                 SD Σ ,  (8)   
                 O((n + m + 4)N 
                 O((n + m + 4)N 
               
               
                   
                 SD Σ E,  (10)   
                 O((n + m + 4)N 
                 O((n + m + 4)N 
               
               
                   
                 H −1 ,  (10) ,  (11)   
                 O((n + m + 4) 2 N + 
                 O((m + 4) 2 (n/2) 2  + 
               
               
                   
                   
                 (n + m + 4) 3 ) 
                 (n + m + 4) 3 ) 
               
               
                   
                 Total 
                 O((n + m + 4) 2 N + 
                 O((m + 4) 2 (n/2) 2  + 
               
               
                   
                   
                 (n + m) 3 ) 
                 (n + m) 3  + 
               
               
                   
                   
                   
                 4(n + m + 4)N) 
               
               
                   
                   
               
             
          
         
       
     
         [0038]    The overwhelmingly largest time consumer for the original SICIA is the construction of the hessian. The computational cost is O((n+m+4) 2 N) where N is the size of the image. With the LSIP this task is converted to O((m+4) 2  (n/2) 2 ). 
         [0039]    We have described the underlying method used for the present invention together with a list of embodiments. Possible application areas for the above described invention range from object recognition, face recognition, facial expression analysis, object part analysis to image synthesis and computer graphics.