# Patent

## Title
System and method for automatic landmark labeling with minimal supervision

## Abstract

A system and method for estimating a set of landmarks for a large image ensemble employs only a small number of manually labeled images from the ensemble and avoids labor-intensive and error-prone object detection, tracking and alignment learning task limitations associated with manual image labeling techniques. A semi-supervised least squares congealing approach is employed to minimize an objective function defined on both labeled and unlabeled images. A shape model is learned on-line to constrain the landmark configuration. A partitioning strategy allows coarse-to-fine landmark estimation.

## Background
CLAIM TO PRIORITY OF PROVISIONAL APPLICATION
This application claims priority under 35 U.S.C. §119(e)(1) of provisional application Ser. No. 61/165,257, filed Mar. 31, 2009, by Yan Tong et al.


STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH & DEVELOPMENT
This invention was made with U.S. Government support under contract numbers 2007-DE-BX-K191 and 2007-MU-CX-K001. The Government may have certain rights in the invention.


BACKGROUND
This invention relates generally to image labeling, and more particularly, to a system and method for implementing automatic landmark labeling for a predetermined object class.
Image labeling for training data is an essential step in many learning-based vision tasks. There are at least two types of prior knowledge represented by image labeling. One is semantic knowledge, such as human IDs for face recognition, or an object's name for content-based image retrieval. The other is geometric/landmark knowledge. The position of an object (face/pedestrian/car) needs to be labeled for all training images, for example, in learning-based object detection. Each training image must be labeled with a set of landmarks which describe the shape of the face for supervised face alignment.
Geometric/landmark knowledge labeling is typically carried out manually. Practical applications, such as object detection, often require thousands of labeled images to achieve sufficient generalization capability. Manual labeling however, is labor-intensive and time-consuming. Furthermore, image labeling is an error-prone process due to labeler error, imperfect description of the objectives, and inconsistencies among different labelers.
Some notable and early work on unsupervised alignment denotes the process as congealing. The underlying idea is to minimize an entropy-based cost function by estimating the warping parameter of an ensemble. More recently, a least squares congealing (LSC) algorithm has been proposed which uses L2 constraints to estimate each warping parameter. These approaches estimate affine warping parameters for each image. The embodiments described herein estimate non-rigid shape deformation described by a large set of landmarks, rather than the relatively simple global affine transformation.
Additional work on unsupervised image alignment has incorporated more general deformation models, though not with the use of a well-defined set of landmarks by including a free-form B-spline deformation model. Bootstrapping algorithms to compute image correspondences and to learn a linear model based on optical flow and the use of an iterative Active Appearance Model (AAM) learning and fitting to estimate the location of mesh vertices, reporting results on images of the same person's face have also been developed. Further work formulates AAM learning as an EM algorithm and extends it to learning parts-based models for flexible objects. Other known techniques include 1) the use of a group-wise objective function to compute non-rigid registration, 2) improvements in manual facial land-mark labeling based on parameterized kernel PCA, 3) an MDL-based cost function for estimating the correspondences for a set of control points, and 4) alignment by tracking the image sequence with an adaptive template.
Generally, one cannot rely upon unsupervised learning methods to locate landmarks on physically meaningful features of an object, such as mouth/eye corners or nose tip on a face; while supervised facial alignment undesirably requires a large number of labeled training images to train a statistical model so that it can generalize and fit unseen images well.
It would be desirable to provide a system and method that automatically provides landmark labeling for a large set of images in a fashion that alleviates the foregoing problems.
BRIEF DESCRIPTION
Briefly, in accordance with one embodiment, a method of determining landmark locations comprises automatically propagating a set of landmark points from a small set of images to a large set of images for a predetermined object class.
According to another embodiment, a vision system is configured to automatically propagate a set of landmark points from a small set of images to a large set of images for a predetermined object class in response to an algorithmic software.



DRAWINGS
These and other features, aspects, and advantages of the present invention will become better understood when the following detailed description is read with reference to the accompanying drawings in which like characters represent like parts throughout the drawings, wherein:
FIG. 1 is a simplified diagram illustrating a vision system configured to automatically propagate a set of landmark points from a small set of images to a large set of images for a predetermined object class in response to an algorithmic software according to one embodiment;
FIG. 2 illustrates exemplary input data and output data for the vision system illustrated in FIG. 1 according to one embodiment;
FIG. 3 illustrates multi-level partitioning according to one embodiment;
FIG. 4 is a set of graphs illustrating a performance comparison for SLSC, SSLSC and partition-based SSLSC in terms of NRMSE of landmarks excluding outliers (%) and SOF (%) according to one embodiment; and
FIG. 5 is a set of graphs illustrating performance analysis by varying partition levels in terms of NRMSE of landmarks and SOF according to one embodiment.



While the above-identified drawing figures set forth alternative embodiments, other embodiments of the present invention are also contemplated, as noted in the discussion. In all cases, this disclosure presents illustrated embodiments of the present invention by way of representation and not limitation. Numerous other modifications and embodiments can be devised by those skilled in the art which fall within the scope and spirit of the principles of this invention.
DETAILED DESCRIPTION
The following preliminary discussion presents a framework to provide a better understanding of the system and method embodiments described thereafter with reference to the Figures that are directed to automatic landmark labeling for a large set of images in a semi-supervised fashion. These embodiments automatically estimate the landmark locations for a full set of images such as, for example, a complete training set of 300 images using manually labeled landmark locations for a few images such as, for example, 10 manually labeled images.
According to one aspect, a semi-supervised least squares congealing (SLSC) method minimizes an objective function defined as the summation of pairwise L2 distances between warped images. Two types of distances are utilized including the distance between the labeled and unlabeled images, and the distance between the unlabeled images. The objective function is iteratively minimized via an inverse warping technique. During the optimization process, estimated landmark locations are constrained according to one embodiment by utilizing shape statistics learned from relatively low-error estimations in an on-line manner, which was found to yield better convergence of landmark position estimates.
Modern work on joint alignment for an image ensemble mainly estimates global affine parameters for each image. The present inventors recognized however that most real-world objects exhibit non-rigid deformation that is not well-modeled by the affine transformation, and that estimating more realistic deformations using a large set of landmarks would provide an important step toward accurately characterizing the shape variation within an object class.
Hierarchical patch-based embodiments that estimate landmark positions are thus described herein. Patches, starting from a whole warped image region treated as the first level patch, are iteratively partitioned into smaller child patches, in which initial landmark locations are obtained from the parent patch and whose refined landmark estimations result in an accurate landmark labeling based on the local patch appearance. Applications in facial images were found by the present inventors to demonstrate that by labeling only 1% to 3% of the ensemble, the landmarks of the remaining images could be accurately estimated.
An automatic image labeling framework according to one embodiment has three main contributions including:
1) a core methodology for (described herein with reference to Equation 1 below) semi-supervised least-squares-based alignment of an image ensemble, described herein using the inverse warping technique;
2) two additional methodologies (described herein with reference to Algorithms 1 and 2 below) for improving landmark estimation via i) a statistical shape model learned on-line to reduce outliers among the ensemble, and ii) patch-based partitioning to improve the precision of landmark estimation; and
3) an end-to-end system for automatic estimation of a set of landmarks in an ensemble of the images for a predetermined object class with very few manually labeled images and described herein with reference to FIGS. 1 and 2.
FIG. 1 is a simplified diagram illustrating a vision system 10 that may be a computer vision system configured to automatically propagate a set of landmark points from a small set of images 14 to a large set of images 16=images 12+images 14 for a predetermined object class in response to an algorithmic software according to one embodiment.
FIG. 2 illustrates exemplary input data 12, 14 and output data 16 for the vision system 10 illustrated in FIG. 1 according to one embodiment.
The embodiments described herein address discovery of non-rigid shape deformation using a specific set of physically defined landmarks enumerated 18 in FIG. 1 and semi-supervised learning in which prior knowledge of landmark location(s) can advantageously be incorporated easily via a few manually labeled examples. Given an ensemble of images 12, 14, where a few manually labeled images 14 have known warping parameters, the embodied SLSC approach estimates the warping parameters of the remaining unlabeled images 12 using the cost function:




  
    
      
        
          
            
              
                ɛ
                ⁡
                
                  (
                  P
                  )
                
              
              =
              
              ⁢
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  K
                
                ⁢
                
                  
                
                ⁢
                
                  
                    ɛ
                    i
                  
                  ⁡
                  
                    (
                    
                      p
                      i
                    
                    )
                  
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  
                    ∑
                    
                      i
                      =
                      1
                    
                    K
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        1
                        -
                        α
                      
                      
                        K
                        -
                        1
                      
                    
                    ⁢
                    
                      
                        ∑
                        
                          
                            j
                            =
                            1
                          
                          ,
                          
                            j
                            ≠
                            i
                          
                        
                        K
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          
                          
                            
                              
                                I
                                j
                              
                              ⁡
                              
                                (
                                
                                  W
                                  ⁡
                                  
                                    (
                                    
                                      x
                                      ;
                                      
                                        p
                                        j
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                            -
                            
                              
                                I
                                i
                              
                              ⁡
                              
                                (
                                
                                  W
                                  ⁡
                                  
                                    (
                                    
                                      x
                                      ;
                                      
                                        p
                                        i
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                          
                          
                        
                        2
                      
                    
                  
                
                +
              
            
          
        
        
          
            
              
              ⁢
              
                
                  
                    ∑
                    
                      i
                      =
                      1
                    
                    K
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      α
                      
                        K
                        ~
                      
                    
                    ⁢
                    
                      
                        ∑
                        
                          n
                          =
                          1
                        
                        
                          K
                          ~
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          
                          
                            
                              
                                
                                  I
                                  ~
                                
                                n
                              
                              ⁡
                              
                                (
                                
                                  W
                                  ⁡
                                  
                                    (
                                    
                                      x
                                      ;
                                      
                                        
                                          p
                                          ~
                                        
                                        n
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                            -
                            
                              
                                I
                                i
                              
                              ⁡
                              
                                (
                                
                                  W
                                  ⁡
                                  
                                    (
                                    
                                      x
                                      ;
                                      
                                        p
                                        i
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                          
                          
                        
                        2
                      
                    
                  
                
                ,
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




where {tilde over (K)} is the number of labeled images Ĩ={Ĩn}nε[1,{tilde over (K)}], and K is the number of unlabeled images I={Ii}iε[1,K], pi is an m-dimensional warping parameter vector to warp Ii to a common mean shape using a warping function W(x;pi), which can be a simple affine warp or a complex non-rigid warp such as the piecewise affine warp. Ii(W(x;pi)) is the corresponding N-dimensional warped image vector. {tilde over (p)}n is the known warping parameter vector for Ĩn. x is a collection of N pixel coordinates within the mean shape. P=[p1, . . . , pK] contains all the warping parameters for I that need to be estimated by minimizing ε(P). Since ε(P) is difficult to optimize directly, εi(pi) is iteratively minimized for each Ii. In the cost function, εi(pi) equals the summation of the pairwise difference between Ii and all the other images in the warped image space. On the one hand, minimizing the 1st term of Eqn. (1) makes the warped image content of the ith unlabeled image similar to that of the other unlabeled images, without regard for the physical meaning of the content. On the other hand, the 2nd term of Eqn. (1) constrains Ii(W(x;pi)) to be similar to those of the labeled images and enforces the physical meaning of the content during alignment. Thus, the labels of Ĩ are propagated to I. Since K>>{tilde over (K)}, a weighting coefficient α can balance the contributions of the two terms in the overall cost.

An inverse warping technique is employed to minimize εi(pi). Warping parameter updates Δpi are first estimated by minimizing the following equation:




  
    
      
        
          
            
              
                
                  ɛ
                  i
                
                ⁡
                
                  (
                  
                    Δ
                    ⁢
                    
                      
                    
                    ⁢
                    
                      p
                      i
                    
                  
                  )
                
              
              =
              
              ⁢
              
                
                  
                    1
                    -
                    α
                  
                  
                    K
                    -
                    1
                  
                
                ⁢
                
                  
                    ∑
                    
                      
                        j
                        =
                        1
                      
                      ,
                      
                        j
                        ≠
                        i
                      
                    
                    K
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                    
                      
                        
                          I
                          j
                        
                        ⁡
                        
                          (
                          
                            W
                            ⁡
                            
                              (
                              
                                
                                  W
                                  ⁡
                                  
                                    (
                                    
                                      x
                                      ;
                                      
                                        Δ
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        
                                          p
                                          i
                                        
                                      
                                    
                                    )
                                  
                                
                                ;
                                
                                  p
                                  j
                                
                              
                              )
                            
                          
                          )
                        
                      
                      -
                    
                  
                
              
            
          
        
        
          
            
              
                
                  
                  ⁢
                  
                    
                      I
                      i
                    
                    ⁡
                    
                      (
                      
                        W
                        ⁡
                        
                          (
                          
                            x
                            ;
                            
                              p
                              i
                            
                          
                          )
                        
                      
                      )
                    
                  
                  
                
                2
              
              +
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  α
                  
                    K
                    ~
                  
                
                ⁢
                
                  
                    ∑
                    
                      n
                      =
                      1
                    
                    
                      K
                      ~
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                    
                      
                        
                          
                            I
                            ~
                          
                          n
                        
                        (
                        
                          
                            W
                            ⁡
                            
                              (
                              
                                
                                  W
                                  ⁡
                                  
                                    (
                                    
                                      x
                                      ;
                                      
                                        Δ
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        
                                          p
                                          i
                                        
                                      
                                    
                                    )
                                  
                                
                                ;
                                
                                  
                                    p
                                    ~
                                  
                                  n
                                
                              
                              )
                            
                          
                          -
                          
                            
                              I
                              i
                            
                            ⁡
                            
                              (
                              
                                W
                                ⁡
                                
                                  (
                                  
                                    x
                                    ;
                                    
                                      p
                                      i
                                    
                                  
                                  )
                                
                              
                              )
                            
                          
                        
                        
                      
                      2
                    
                  
                
              
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




and then update the warping function by:

W(x;pi)←W(x;pi)∘W(x;Δpi)−  (3)

The function εi(Δpi) is nonlinear with respect to Δpi. To support numeric optimization of this function, a first order Taylor expansion is performed on Ij(W(W(x;Δpi);pj) and Ĩn(W(W(x;Δpi);{tilde over (p)}n) to yield:





  
    
      I
      j
    
    ⁡
    
      (
      
        W
        ⁡
        
          (
          
            
              W
              ⁡
              
                (
                
                  x
                  ;
                  
                    Δ
                    ⁢
                    
                      
                    
                    ⁢
                    
                      p
                      i
                    
                  
                
                )
              
            
            ;
            
              p
              j
            
          
          )
        
      
      )
    
  
  ≈
  
    
      
        I
        j
      
      ⁡
      
        (
        
          W
          ⁡
          
            (
            
              x
              ;
              
                p
                j
              
            
            )
          
        
        )
      
    
    +
    
      
        
          ∂
          
            
              I
              j
            
            ⁡
            
              (
              
                W
                ⁡
                
                  (
                  
                    x
                    ;
                    
                      p
                      j
                    
                  
                  )
                
              
              )
            
          
        
        
          ∂
          
            p
            j
          
        
      
      ⁢
      Δ
      ⁢
      
        
      
      ⁢
      
        
          p
          i
        
        .
      
    
  




As a result, Eqn. (2) is simplified to:





  
    
      
        
          
            
              
                1
                -
                α
              
              
                K
                -
                1
              
            
            ⁢
            
              
                ∑
                
                  
                    j
                    =
                    1
                  
                  ,
                  
                    j
                    ≠
                    i
                  
                
                K
              
              ⁢
              
                
              
              ⁢
              
                
                  
                  
                    
                      b
                      j
                    
                    +
                    
                      
                        c
                        j
                      
                      ⁢
                      Δ
                      ⁢
                      
                        
                      
                      ⁢
                      
                        p
                        i
                      
                    
                  
                  
                
                2
              
            
          
          +
          
            
              α
              
                K
                ~
              
            
            ⁢
            
              
                ∑
                
                  n
                  =
                  1
                
                
                  K
                  ~
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                  
                    
                      b
                      n
                    
                    +
                    
                      
                        c
                        n
                      
                      ⁢
                      Δ
                      ⁢
                      
                        
                      
                      ⁢
                      
                        p
                        i
                      
                    
                  
                  
                
                2
              
            
          
        
        ⁢
        
          

        
        ⁢
        where
        ⁢
        
          

        
        ⁢
        
          
            
              b
              j
            
            =
            
              
                
                  I
                  j
                
                ⁡
                
                  (
                  
                    W
                    ⁡
                    
                      (
                      
                        x
                        ;
                        
                          p
                          j
                        
                      
                      )
                    
                  
                  )
                
              
              -
              
                
                  I
                  i
                
                ⁡
                
                  (
                  
                    W
                    ⁡
                    
                      (
                      
                        x
                        ;
                        
                          p
                          i
                        
                      
                      )
                    
                  
                  )
                
              
            
          
          ,
          
            

          
          ⁢
          
            
              c
              j
            
            =
            
              
                ∂
                
                  
                    I
                    j
                  
                  ⁡
                  
                    (
                    
                      W
                      ⁡
                      
                        (
                        
                          x
                          ;
                          
                            p
                            j
                          
                        
                        )
                      
                    
                    )
                  
                
              
              
                ∂
                
                  p
                  j
                
              
            
          
          ,
          
            

          
          ⁢
          
            
              b
              n
            
            =
            
              
                
                  
                    I
                    ~
                  
                  n
                
                ⁡
                
                  (
                  
                    W
                    ⁡
                    
                      (
                      
                        x
                        ;
                        
                          
                            p
                            ~
                          
                          n
                        
                      
                      )
                    
                  
                  )
                
              
              -
              
                
                  I
                  i
                
                ⁡
                
                  (
                  
                    W
                    ⁡
                    
                      (
                      
                        x
                        ;
                        
                          p
                          i
                        
                      
                      )
                    
                  
                  )
                
              
            
          
          ,
          
            

          
          ⁢
          
            
              c
              n
            
            =
            
              
                
                  ∂
                  
                    
                      
                        I
                        ~
                      
                      n
                    
                    ⁡
                    
                      (
                      
                        W
                        ⁡
                        
                          (
                          
                            x
                            ;
                            
                              
                                p
                                ~
                              
                              n
                            
                          
                          )
                        
                      
                      )
                    
                  
                
                
                  ∂
                  
                    
                      p
                      ~
                    
                    n
                  
                
              
              .
            
          
        
      
    
    
      
        (
        4
        )
      
    
  




The least squares solution of Eqn. (4) yields:





  
    
      
        
          
            Δ
            ⁢
            
              
            
            ⁢
            
              p
              i
            
          
          =
          
            -
            
              
                H
                
                  -
                  1
                
              
              [
              
                
                  
                    
                      1
                      -
                      α
                    
                    
                      K
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      ∑
                      
                        
                          j
                          =
                          1
                        
                        ,
                        
                          j
                          ≠
                          i
                        
                      
                      K
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        c
                        j
                        T
                      
                      ⁢
                      
                        b
                        j
                      
                    
                  
                
                +
                
                  
                    α
                    
                      K
                      ~
                    
                  
                  ⁢
                  
                    
                      ∑
                      
                        n
                        =
                        1
                      
                      
                        K
                        ~
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        c
                        n
                        T
                      
                      ⁢
                      
                        b
                        n
                      
                    
                  
                
              
              ]
            
          
        
        ,
        
          

        
        ⁢
        
          with
          ~
        
      
    
    
      
        (
        5
        )
      
    
  
  
    
      
        H
        =
        
          
            
              
                1
                -
                α
              
              
                K
                -
                1
              
            
            ⁢
            
              
                ∑
                
                  
                    j
                    =
                    1
                  
                  ,
                  
                    j
                    ≠
                    i
                  
                
                K
              
              ⁢
              
                
              
              ⁢
              
                
                  c
                  j
                  T
                
                ⁢
                
                  c
                  j
                
              
            
          
          +
          
            
              α
              
                K
                ~
              
            
            ⁢
            
              
                ∑
                
                  n
                  =
                  1
                
                
                  K
                  ~
                
              
              ⁢
              
                
              
              ⁢
              
                
                  c
                  n
                  T
                
                ⁢
                
                  
                    c
                    n
                  
                  .
                
              
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




The computational cost for solving the second term of Eqn. (4) is negligible. Therefore, semi-supervised congealing has a computational cost similar to that of unsupervised congealing. According to one aspect, a shape-constrained SLSC improves the robustness of the congealing process by reducing outliers. According to another aspect, this is extended to a patch-based approach to achieve an accurate estimate of the landmarks by partitioning the mean shape space.
Given the warping parameters for all images {P,{tilde over (P)}}=[p1, . . . , pK, {tilde over (p)}1, . . . , {tilde over (p)}{tilde over (K)}], and their corresponding landmark locations {S,{tilde over (S)}}=[s1, . . . , sK, {tilde over (s)}1, . . . , {tilde over (s)}{tilde over (K)}], where s is a concatenated vector of a set of 2D landmark coordinates s=[x1, y1, x2, y2, . . . , xv, yv]T, there are two ways of mapping between {P,{tilde over (P)}} and {S,{tilde over (S)}}. First, the landmarks si can be obtained from the warping parameter pi via si=W(xs;pi), where xs is a vector containing the coordinates of the target landmarks in the mean shape space. As a result, an incorrect warping parameter, which can result from an outlier in the congealing process, would produce a landmark set that is not a valid shape instance. Second, the warping parameter pi can be obtained given the corresponding landmark pairs (xs and si). Consequently, refining the positions of the landmarks can improve the estimation of the warping parameters. A shape-constrained SLSC (SSLSC) approach described herein integrates the shape constraints with the appearance-based congealing process to improve the robustness of the SLSC.
Given that the objects in the images have the same topological structure, an assumption is made that the shape deformation of si satisfies a Point Distribution Model (PDM). Since only a few labeled images are available, the PDM is learned from both the labeled landmarks and an automatically chosen low-error subset of the estimated landmarks in an online manner. Then, any other poor estimations can be “corrected” through a PCA reconstruction as follows:

ŝi= s+Qz  (7)

where ŝi is the reconstructed shape vector for the ith image; s and Q are the mean shape and the shape basis obtained through the on-line training; and z is the shape parameter vector that is restricted in some range. Finally, a new warping parameter vector {circumflex over (p)}i is computed from the refined landmark positions ŝi such that the outliers of the congealing process are discovered and constrained in a principled way.

The SSLSC is summarized as Algorithm 1 below, where P0 represents the initial warping parameters for I. The labeled landmarks are fully utilized in the sense that they not only contribute for the cost minimization for Eqn. (2), but also provide guidance for shape deformation.










Algorithm 1 Shape-constrained SLSC (SSLSC)















Input: I, Ĩ, P0, {tilde over (P)}, x, and xs


Output: Pt, St, and ε









t ← 0;



Compute {tilde over (s)}i = W (xs; {tilde over (p)}i) for i ∈ [1, {tilde over (K)}];



repeat









for i = 1 to K do









εi(Δpi), pit+1 ← SLSC(I, Ĩ, Pt, {tilde over (P)}, x);









end for



Rank εi (Δp1), . . . , εK (ΔpK) in ascending order and pick the



first KM images;



Compute sit+1 = W (xs; pit+1) for i ε[1, KM];



 s, Q, λ ← PCA on S = [{tilde over (s)}1, . . . , {tilde over (s)}{tilde over (K)}, s1t+1, . . . , sKMt+1]T;



for i = KM + 1 to K do









Reconstruct sit+1 as Eqn. (7);



Compute pit+1 from sit+1;









end for



Pt+1 ← [p1t+1, . . . , pKt+1]; St+1 ← [s1t+1, . . . , sKt+1]T;



 







  
    ɛ
    ←
    
      
        ∑
        
          i
          =
          1
        
        K
      
      ⁢
      
        
          ɛ
          i
        
        ⁡
        
          (
          
            Δ
            ⁢
            
              
            
            ⁢
            
              p
              i
            
          
          )
        
      
    
  
  ;
  
    t
    ←
    
      t
      +
      1.
    
  







 







until Converge









The warping function W(x;pi) can be a simple global affine warp to model rigid transformation, or a piecewise affine warp to model non-rigid transformation. The SSLSC algorithm does not however, perform satisfactorily with direct use of the piecewise affine warp. This difficulty is related to the high dimensionality of the warping parameter pi. Looking at the piecewise affine warp closely, it can be noted that the warping function W is a series of affine transformations, each operating within a small triangular patch. While the patch allows a workspace whose dimension is much smaller than the original space, and thus makes the problem easier to solve, directly applying the SSLSC on the small patches is not reliable due to the poor initialization and limited information encoded in the patch. Based on these observations, a coarse-to-fine partition-based congealing method improves the precision of landmark labeling.

The partitioning strategy is summarized as Algorithm 2 below, where Sinit is the initial guess of the landmark positions for I. In the algorithm, besides the notation mentioned previously, R represents the indices of the patches to be aligned in the current partition level; d represents the index of the patch. Starting from the initial mean shape space x1, the process is conducted by repeatedly partitioning the mean shape space for a selected patch (xk*), which has the maximal congealing error (ε), into multiple child patches. In one embodiment, two equal sized child patches are generated by each partitioning. To enforce a geometrical relationship between the child patches, they are overlapped such that some landmarks reside in both of them. Positions of these landmarks are estimated as averages of the SSLSC results of the two child patches. After the partitioning, the SSLSC is applied on each child patch, independently, to obtain the corresponding landmark positions within the patch itself. The partitioning is stopped when no cost reduction is achieved or the size of the patch is too small. According to one embodiment, the patch reaches its size limit if the number of target landmarks in xd is less than the number of corresponding landmarks required for computing pi. One example of multiple level partitioning is shown in FIG. 3.










Algorithm 2 Landmark Labeling by Partition















Input: I, Ĩ, Sinit, {tilde over (S)}


Output: S









lmin ← minimum number of landmarks in a patch;



d ← 1; R ← {1}; Sinit1 ← Sinit;



Compute x1 and xs1 from {tilde over (S)};



while d < maximum number of patches do









for each r ∈ R do









Calculate Pinitr and {tilde over (P)}r from Sinitr, xsr, {tilde over (S)}, and xsr,



respectively;



Pr, Sr, εr ← SSLSC(I, Ĩ, Pinitr, {tilde over (P)}r, xr, xsr);



if no cost reduction is achieved in r over its parent



patch then









return Sd−2 // return labeling results of last partition



level;









end if









end for



 







  
    
      k
      ⁢
      
        
      
      *
    
    ⁢
    
      
    
    =
    
      
        
          argmax
          ⁢
          
            
          
        
        k
      
      ⁢
      
        ɛ
        k
      
    
  
  ,
  
    
      k
      ∈
      
        [
        
          1
          ,
          d
        
        ]
      
    
    ;
  







 



child patches xd+1, xd+1, xsd+1, xsd+2 ← Partition the k *th patch;



Sinitd+1 ← Sk*; Sinitd+2 ← Sk*; εk* ← 0;



if size(xsd+1) < lmin or size(xsd+1) < lmin then









return Sd;









end if



d ← d + 2; R ← {d + 1, d + 2};









end while










The top-down congealing strategy performs a coarse-to-fine alignment for the entire image ensemble. The congealing in the coarse level partition focuses on aligning the features that are most similar among the image ensemble such as eyes on the face, whereas the other features like nose and mouth are neglected. Hence, the landmark estimation on the larger patches is often coarse and used to provide a good initialization for the latter levels. With the increasing of the partition level, more details of the target object are revealed. As a result, the estimation of the landmarks becomes more and more precise.

The effectiveness of the landmark labeling methods described herein has been demonstrated in one application by automatically annotating 33 specific landmarks around facial features (i.e., eyes, eyebrows, nose, mouth, and contour) for a large image set, given a few labeled images. For this application, 300 images were collected from a known database in which the facial regions were unaligned. Then, 33 landmarks were labeled for each image to establish a ground truth and to enable a quantitative evaluation for the labeling performance.
The 300 labeled images were divided into two non-overlapping sets: a labeled set with {tilde over (K)} images and an unlabeled set with 300−{tilde over (K)} images. The initial value of the jth element of Si was generated for quantitative evaluation by adding a uniformly distributed random noise ηε[−ηmax,ηmax] to the groundtruth value Ŝi,j as follows,




  
    
      
        
          S
          
            i
            ,
            j
          
        
        =
        
          
            
              S
              ^
            
            
              i
              ,
              j
            
          
          +
          
            
              η
              ⁢
              
                
              
              ⁢
              
                ρ
                i
              
            
            
              ρ
              _
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




where ρi is the eye-to-eye pixel distance of Ii, and ρ is the average of ρi for all unlabeled images. By doing so, the level of deviation in the initialization is relative to face size. In practical applications, the initial landmark positions can be obtained from the approximate face location. A 6-parameter affine transformation was employed in the congealing process, and a 72×72 square region, which encloses all the target landmarks, was used as the common mean shape. The warped face region was normalized by subtracting its mean intensity value and then divided by its standard deviation to accommodate illumination changes.

The effectiveness was evaluated using two criteria: (1) Normalized Root Mean Squared Error (NRMSE) of landmarks defined as the RMSE with respect to the ground truth divided by the eye-to-eye distance ρi, and expressed as a percentage; and (2) the Sample “Outliers” Fraction (SOF) defined as the number of images, of which the NRMSE exceeds a threshold (10%), versus the number of unlabeled images. A smaller NRMSE indicates a higher labeling accuracy, and a smaller SOF represents greater robustness.
The effectiveness of using a shape-constrained SLSC is first compared with using SLSC under the effects of varying number of labeled images {tilde over (K)}ε{1,5,10,20,40,80,160} and different noise levels ηmaxε{10,30,50}. FIG. 4 illustrates the performance comparison in terms of NRMSE and SOF in which SLSC is represented by the dashed line, SSLSC is represented by the line with circles, and SSLSC is represented by the line with crosses. The left side graphs are in terms of NRMSE of landmarks excluding outliers (%). The right side graphs are in terms of SOF (%). The results in each row correspond to a noise level (ηmax=10, 30, 50) respectively. Note that, for this result, outliers were excluded from the computation of NRMSE. The results were computed from an average of 5 trials, where {tilde over (K)} images were randomly selected as the labeled set for each trial. Both algorithms were compared under the same conditions. Both algorithms used, for example, the same randomly selected labeled set and the same initialization.
Comparing the results of SLSC and SSLSC in FIG. 4, the shape constraints are effective in reducing the outliers significantly, even when the congealing performance of SLSC is poor due to a high initialization noise level and a small number of labeled images. For example, the SOF decreases from 32% (SLSC) to 23.4% (SSLSC) with {tilde over (K)}=1 and ηmax=50, which is equivalent to removing 26 outliers. Furthermore, an average of 5.2% reduction of SOF is obtained when ηmax=50. Since the shape constraints are not applied on those low-error estimations, there is no improvement in the NRMSE excluding outliers.
FIG. 4 also illustrates the improvement of labeling accuracy by partition-based SSLSC. Similar to the previous results for SSLSC, the performance was evaluated under varying {tilde over (K)} and ηmax values from an average of 5 random trials, as shown in FIG. 4. Comparing the results of SSLSC and partition-based SSLSC in FIG. 4, it is obvious that the partition-based approach further improves both precision and robustness in terms of reducing the NRMSE and SOF. The SOF for example, decreases from 23.4% (SSLSC) to 20.3% (partition-based SSLSC), and the NRMSE decreases from 9.92% (SSLSC) to 9.06% (partition-based SSLSC) with {tilde over (K)}=1 and ηmax=50. In summary, an average of 1% reduction of NRMSE is achieved for all noise levels, and an average of 2% decrease of SOF is obtained for high noise levels (ηmax=30, 50). FIG. 4 illustrates there is no remarkable improvement when {tilde over (K)}>=10, which means that only using 3% ( 10/300) labeled data, the landmarks can be estimated accurately and robustly.
FIG. 5 illustrates the performance improvement across different partition levels when {tilde over (K)}=5 and ηmax=30. The results of level-0 correspond to the initialization, and those of level-1 represent the congealing results on the whole mean shape space by SSLSC. Increasing levels of partition, both the NRMSE and SOF decrease and converge at the last partition level as illustrated in FIG. 5.
In summary explanation, shape deformation of images of a real-world object is often non-rigid due to inter-subject variability, object motion, and camera view point. Automatically estimating non-rigid deformations for an object class is a critical step in characterizing the object and learning statistical models. The system and method embodiments described herein facilitate such a task by automatically producing labeled data sets. Extensive experiments have demonstrated these methods achieve impressive labeling results on facial images with nearly frontal view and moderate changes in expression, useful for many current applications. The invention is not so limited however as these embodiments can be immediately applied to the task of labeling landmarks in images of other classes of objects such as vehicles or pedestrians using the principles described herein.
While only certain features of the invention have been illustrated and described herein, many modifications and changes will occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.

## Claims

1. A method of determining landmark locations, the method comprising automatically propagating a set of landmark points from a small set of images to a large set of images for a predetermined object class, wherein automatically propagating comprises estimating landmark point locations for the large set of images using manually labeled landmark locations for the small set of images, and wherein estimating landmark point locations comprises iteratively partitioning a primary patch region into localized smaller child patch regions, such that initial landmark locations are based on the primary patch region and further such that refined landmark estimations result in accurate landmark labeling based on the resultant local patch appearance.

2. The method according to claim 1, wherein the large set of images is an integer number of images less than about 5,000.

3. The method according to claim 2, wherein the small set of images comprises from about 1% to about 3% of the large set of images.

4. The method according to claim 1, wherein estimating landmark point locations comprises minimizing an objective function defined as the summation of pairwise L2 distances between warped images.

5. The method according to claim 4, wherein minimizing comprises processing the objective function based on semi-supervised least squares congealing.

6. The method according to claim 4, wherein the pairwise L2 distances are selected from the distance between labeled and unlabeled images and the distance between unlabeled images.

7. The method according to claim 4, further comprising constraining the estimated landmark locations in response to shape statistics learned from relatively low-error estimations in an on-line manner.

8. The method according to claim 4, wherein minimizing comprises iteratively minimizing the objective function via inverse warping.

9. A vision system configured to automatically propagate a set of landmark points from a small set of images to a large set of images for a predetermined object class in response to an algorithmic software, wherein the vision system is configured to automatically estimate landmark point locations for the large set of images using manually labeled landmark locations for the small set of images in response to the algorithmic software, and wherein the vision system is configured to iteratively partition a primary patch region into localized smaller child patch regions, such that initial landmark locations are based on the primary patch region and further such that refined landmark estimations result in accurate landmark labeling based on the resultant local patch appearance in response to the algorithmic software.

10. The vision system according to claim 9, wherein the large set of images is an integer number of images less than about 5,000.

11. The vision system according to claim 10, wherein the small set of images comprises from about 1% to about 3% of the large set of images.

12. The vision system according to claim 9, wherein the vision system is configured to estimate the landmark point locations based on minimizing an objective function defined as the summation of pairwise L2 distances between warped images in response to the algorithmic software.

13. The vision system according to claim 12, wherein the vision system is configured to process the objective function based on semi-supervised least squares congealing in response to the algorithmic software.

14. The vision system according to claim 12, wherein the pairwise L2 distances are selected from the distance between labeled and unlabeled images and the distance between unlabeled images.

15. The vision system according to claim 12, wherein the vision system is configured to constrain the estimated landmark locations in response to shape statistics learned from relatively low-error estimations in an on-line manner.

16. The vision system according to claim 12, wherein the vision system is configured to iteratively minimize the objective function via inverse warping in response to the algorithmic software.