# Patent

## Title
System and method for detecting feature points of face

## Abstract

Disclosed are a system and a method for detecting feature points of a face. The system for detecting feature points of a face include: a training unit configured to divide each of a plurality of facial images into segments of a predetermined size, and generate an eigen-codebook representing a correlation between a feature vector of each of the divided segments and location of a predetermined feature point in the facial image; and a detection unit configured to detect a facial area from a target image, divide the facial area into segments of a predetermined size, detect a feature vector of each of the divided segments of the facial area, and detect a location of a feature point in the facial area by using the detected feature vector and the eigen-codebook.

## Background
CROSS-REFERENCE TO RELATED APPLICATION
This application claims priority to and the benefit of Korean Patent Application No. 10-2015-0119387, filed on Aug. 25, 2015, the disclosure of which is incorporated herein by reference in its entirety.
BACKGROUND
1. Field
The present disclosure relates to technology for detecting feature points of a face.
2. Discussion of Related Art
With image processing technology being developed, a technology of recognizing a face from a target image has been commercialized. In order to recognize a face, generally, facial feature points need to be detected and the detecting of feature points of a face is generally implemented using a method of comparing patterns of a target image and a facial image for training. However, the conventional technology has inconvenience that local patterns corresponding to facial feature points need to be individually extracted, and in this case, a great amount of time is taken for extracting the local patterns, and a storage space is wasted with the local patterns being stored. In addition, the detecting of facial feature points needs to use a separate pattern searching algorithm, which has a great complexity of computation used in detecting feature points. Further, the conventional pattern search is implemented using a method of comparing pixel values of images, and in this case, the accuracy in detecting feature points may be lowered depending on change in brightness of the image and illumination of a surrounding environment.
SUMMARY
The present disclosure is directed to technology for rapidly and accurately detecting the location of a feature point in a facial area of a target image.
According to an aspect of the present disclosure, there is provided a system for detecting a feature point of a face, the system including a training unit and a detection unit. The training unit may be configured to divide each of a plurality of facial images into segments of a predetermined size, and generate an eigen-codebook representing a correlation between a feature vector of each of the divided segments and location of a predetermined feature point in the facial image. The detection unit may be configured to detect a facial area from a target image, divide the facial area into segments of a predetermined size, detect a feature vector of each of the divided segments of the facial area, and detect a location of a feature point in the facial area by using the detected feature vector and the eigen-codebook.
The training unit may be configured to obtain Ms=[h1s, . . . , hns] by applying a predetermined feature point detection algorithm to each segment of the facial image, obtain MEs=[haves, he1s, . . . , hePss] by applying Principal Component Analysis (PCA) algorithm to the Ms, and generate the eigen-codebook by using the Ms and the MEs, wherein hns may be data of a feature vector of a segment s of a nth facial image, M may be a matrix, haves may be an average among data h1s . . . and hns, hePss may represent a piece of eigen data obtained by applying the PCA algorithm to data h1s . . . and hns, and when a piece of eigen data heis has an eigen value of λeis, λe1s> . . . >λePs, and Ps may be a total number of data he1s . . . and hePss.
The training unit may be configured to calculate Cs that represents a correlation between the Ms and the MEs and satisfies Ms·Cs=MEs, and generate the eigen-codebook by using the Cs,
wherein · represents a matrix multiplication.
The training unit may be configured to calculate a direction vector Vs,k from a center of the segment s of the nth facial image to a predetermined feature point k of the facial image, the direction vector Vs,k satisfying Vs,k=[v1s,k, . . . , vns,k]ε2×n, and to calculate VEDVs,k by using VEDVs,k=Vs,k·Cs, wherein the eigen-codebook may include the VEDVs,k.
The detection unit may be configured to obtain hs by applying a predetermined feature point detection algorithm to each segment of the facial area, obtain cis by representing the hs as a combination of values of the MEs by using




  
    h
    s
  
  ≈
  
    
      h
      ave
      s
    
    +
    
      
        ∑
        
          i
          =
          1
        
        
          P
          s
        
      
      ⁢
      
        
      
      ⁢
      
        
          c
          i
          s
        
        ⁢
        
          h
          ei
          s
        
      
    
  




and cis=hs−haves, heis in which a, b is an inner product of a and b, and detect the location of the feature point of the facial area by using the cis.

The detection unit may be configured to represent a direction vector vs,k from a center of the segment s of the facial area to the feature point k as a combination of values of the VEDVs,k by using




  
    
      v
      
        s
        ,
        k
      
    
    =
    
      
        v
        ave
        
          s
          ,
          k
        
      
      +
      
        
          ∑
          
            i
            =
            1
          
          
            P
            s
          
        
        ⁢
        
          
        
        ⁢
        
          
            c
            i
            s
          
          ⁢
          
            v
            ei
            
              s
              ,
              k
            
          
        
      
    
  
  ,




and detect the location of the feature point of the facial area by using the vs,k.

The detection unit may be configured to detect the location of the feature point of the facial area by determining a location coordinate of the feature point k at which the summation of the distances between the coordinate and the direction vectors from centers of the respective segments of the facial area to the feature point k.
According to another aspect of the present disclosure, there is provided a method for detecting a feature point of a face, the method including: dividing, by a training unit, each of a plurality of facial images into segments of a predetermined size; generating, by the training unit, an eigen-codebook representing a correlation between a feature vector of each of the divided segments and location of a predetermined feature point in the facial image; detecting, by a detection unit, a facial area from a target image; dividing, by the detection unit, the facial area into segments of a predetermined size; detecting, by the detection unit, a feature vector of each of the divided segments of the facial area; and detecting, by the detection unit, a location of a feature point in the facial area by using the detected feature vector and the eigen-codebook.
The generating of the eigen-codebook may include: obtaining Ms=[h1s, . . . , hss] by applying a predetermined feature point detection algorithm to each segment of the facial image; obtaining MEs=[haves, he1s, . . . , hePss] by applying the Principal Component Analysis (PCA) algorithm to the Ms; and generating the eigen-codebook by using the Ms and the MEs, wherein hns may be data of a feature vector of a segment s of a nth facial image, M may be a matrix, haves may be an average among data h1s . . . and hns, hePss may represent a piece of eigen data obtained by applying the PCA algorithm to data h1s . . . and hns, and when a piece of eigen data heis has an eigen value of λeis, λe1s> . . . >λePs, and Ps may be a total number of data he1s . . . and hePss.
The generating of the eigen-codebook by using the Ms and the MEs may include: calculating Cs that represents a correlation between the Ms and the MEs and satisfies Ms·Cs=MEs in which · represents a matrix multiplication; and generating the eigen-codebook by using the Cs.
The generating of the eigen-codebook by using the Cs may include: calculating a direction vector Vs,k from a center of the segment s of the nth facial image to a predetermined feature point k of the facial image, the direction vector Vs,k satisfying Vs,k=[v1s,k, . . . , vns,k]ε2×n; and calculating VEDVs,k by using VEDVs,k=Vs,k·Cs, wherein the eigen-codebook may include the VEDVs,k.
The detecting of a location of a feature point may include: obtaining hs by applying a predetermined feature point detection algorithm to each segment of the facial area; obtaining cis by representing the hs as a combination of values of the MEs by using




  
    h
    s
  
  ≈
  
    
      h
      ave
      s
    
    +
    
      
        ∑
        
          i
          =
          1
        
        
          P
          s
        
      
      ⁢
      
        
      
      ⁢
      
        
          c
          i
          s
        
        ⁢
        
          h
          ei
          s
        
      
    
  




and cis=hs−haves, heis in which a, b is an inner product of a and b; and detecting the location of the feature point of the facial area by using the cis.

The detecting of the location of the feature point of the facial area by using the cis may include: representing a direction vector vx,k from a center of the segment s of the facial area to the feature point k as a combination of values of the VEDVs,k by using




  
    
      v
      
        s
        ,
        k
      
    
    =
    
      
        v
        ave
        
          s
          ,
          k
        
      
      +
      
        
          ∑
          
            i
            =
            1
          
          
            P
            s
          
        
        ⁢
        
          
        
        ⁢
        
          
            c
            i
            s
          
          ⁢
          
            v
            ei
            
              s
              ,
              k
            
          
        
      
    
  
  ;




and detecting the location of the feature point of the facial area by using the vx,k.

In the detecting of the location of the feature point of the facial area by using the vs,k, the location of the feature point of the facial area may be detected by determining a location coordinate of the feature point k at which the summation of the distances between the coordinate and the direction vectors from centers of the respective segments of the facial area to the feature point k.
As is apparent from the above, according to exemplary embodiments of the present disclosure, statistical inference based on a plurality of training facial images is used instead of extracting local patterns at one point of a face, and thus the location of a feature point in a facial area of a target image can be rapidly and accurately detected. In addition, according to exemplary embodiments of the present disclosure, a pre-trained eigen-codebook is used, thereby minimizing the computational complexity in detecting a feature point and also minimizing the size of a storage, compared with the conventional technology using a pattern searching algorithm. Further, the facial feature point detection according to exemplary embodiments of the present disclosure can be easily implemented on low-performance hardware, such as a mobile application.



BRIEF DESCRIPTION OF THE DRAWINGS
The above and other objects, features and advantages of the present disclosure will become more apparent to those of ordinary skill in the art by describing in detail exemplary embodiments thereof with reference to the accompanying drawings, in which:
FIG. 1 is a block diagram illustrating a detailed configuration of a system for detecting feature points of a face according to an exemplary embodiment of the present disclosure;
FIG. 2 is a diagram illustrating a process of generating an eigen-codebook in a training unit according to an exemplary embodiment of the present disclosure;
FIG. 3 is a diagram illustrating a process of detecting a facial area and dividing the detected facial area into segments each having a predetermined size in a detection unit according to an exemplary embodiment of the present disclosure;
FIG. 4 is a diagram illustrating a process of obtaining a direction vector from a center of a segment of the facial area to a feature point according to an exemplary embodiment of the present disclosure;
FIG. 5 is a diagram illustrating a process of determining location coordinates of the feature point in the detection unit according to an exemplary embodiment of the present disclosure; and
FIG. 6 is a flowchart showing a method for detecting facial feature points of a face according to an exemplary embodiment of the present disclosure.



DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS
Exemplary embodiments of the present disclosure will be described in detail below with reference to the accompanying drawings. The following description is intended to provide a general understanding of the method, apparatus and/or system described in the specification, but it is illustrative in purpose only and should not be construed as limiting the present disclosure.
In describing the present disclosure, detailed descriptions that are well-known but are likely to obscure the subject matter of the present disclosure will be omitted in order to avoid redundancy. The terminology used herein is defined in consideration of its function in the present disclosure, and may vary with an intention of a user and an operator or custom. Accordingly, the definition of the terms should be determined based on overall contents of the specification. The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the present inventive concept. As used herein, the singular forms “a,” “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.
FIG. 1 is a block diagram illustrating a detailed configuration of a system for detecting facial feature points 100 according to an exemplary embodiment of the present disclosure. Referring to FIG. 1, the facial feature point detecting system 100 according to an exemplary embodiment of the present disclosure includes a training unit 102 and a detection unit 104.
The training unit 102 is a module configured to generate an eigen-codebook based on a plurality of facial images. According to exemplary embodiments of the present disclosure, the eigen-codebook is a set of a plurality of pieces of information representing correlations between a feature vector of each segment of a facial image and location of a predetermined feature point in the facial image. The detection unit 104, which will be described below, may rapidly and accurately detect the location of a feature point in a facial area of a target image by using the eigen-codebook. In addition, the facial image is an image for training used to generate the eigen-codebook, and may include a facial area of a human. The facial image, for example, may be an image obtained by applying Adaboost algorithm to an input image such that areas except for a facial area are removed. The training unit 102 may generate the eigen-codebook by using a plurality of facial images including facial areas of unspecified individuals. For example, in order to generate an eigen-codebook, 100 to 150 facial images may be used, but the number of facial images used to generate an eigen-codebook is not limited thereto.
Referring to FIG. 2, a process of generating an eigen-codebook in the training unit 102 is described in detail. First, the training unit 102 may divide each of a plurality of facial images into segments each having a predetermined size. For example, the training unit 102 may adjust a size of the facial image to 72×72 pixels, and divide the facial image into 9×9 grids, so that 81 segments are obtained. The segment may be provided in the form of a quadrangle as an example, but the shape and number of segments in the facial image are not limited thereto.
Then, the training unit 102 may calculate a feature vector by applying a predetermined feature point detection algorithm to each segment of the facial image. The feature point detection algorithm may be Histogram of Oriented Gradients (HOG), Scale Invariant Feature Transform (SIFT), and Speeded Up Robust Features (SURF), etc. However, the feature point detection algorithm is not limited thereto. For convenience sake of description, the training unit 102 is assumed to use the HOG algorithm in calculating a feature vector. The HOG algorithm is a histogram characterized in the distribution of gradients and edge directions. The training unit 102 may calculate a feature vector of each segment of the facial image by using the HOG algorithm. The HOG algorithm, using edge direction information, is less sensitive to the brightness of an image and the change of illumination of a surrounding environment. When it is assumed that n facial images exist, hns is a piece of data regarding a feature vector at a segment s of a nth facial image (for example, histogram data). When Ms refers to a set of data h1s . . . and hns obtained by applying the feature point detection algorithm to each segment of the facial image, the Ms is represented as Equation below.

Ms=[h1s, . . . , hns],  [Equation]

herein, M is a matrix, and histogram data of feature vectors of a nth facial image may be included in each column of the Ms.
Then, the training unit 102 may obtain MEs by applying Principal Component Analysis (PCA) algorithm to Ms. The PCA algorithm is a linear recognition algorithm using statistical information of a second moment. The training unit 102 may obtain eigen-features by using the PCA algorithm. A process of obtaining MEs by applying the PCA algorithm to Ms is sequentially described as follows:
(1) Obtain an average haves among h1s . . . and hns 
(2) Subtract the average haves from each of h1s . . . and hns 
(3) Generate a covariance matrix
(4) Obtain eigen values and eigen vectors by using the covariance matrix
(5) Obtain eigen data (or eigen histograms) (he1s . . . and hePss).
The MEs may be represented as Equation below.

MEs=[haves,he1s, . . . , hePss]  [Equation]

herein, haves represents an average among h1s . . . and hns, and hePss represents a piece of eigen data (an eigen histogram) obtained by applying the PCA algorithm to h1s . . . and hns. When a piece of eigen data heis has an eigen value of λeis, λe1s> . . . >λePs, and Ps is a total number of data he1s . . . and hePss. That is, when the feature vectors are analyzed, a greatest distribution is shown in a direction of he1s. Ps is the number of eigen data used when generating an eigen-codebook among h1s . . . and hns, and the Ps may vary with an energy preserving level shown in FIG. 1. The energy preserving level may be expressed as Equation below. A denominator of the energy preserving level is a summation of the squares of eigen values, and a numerator of the energy preserving level is a summation of the squares of eigen values corresponding to principal components desired to be used. In this case, D=n−1.




  
    
      
        
          
            ∑
            
              d
              =
              1
            
            
              P
              s
            
          
          ⁢
          
            
          
          ⁢
          
            
              λ
              ed
              s
            
            2
          
        
        
          
            ∑
            
              d
              =
              1
            
            D
          
          ⁢
          
            
          
          ⁢
          
            
              λ
              ed
              s
            
            2
          
        
      
    
    
      
        [
        Equation
        ]
      
    
  




When it is assumed that a piece of data hns having a smaller eigen value is close to noise and all of h1s . . . and hns corresponding to respective eigen values are used, the energy preserving level is 100%. When data hns is removed one by one starting from a hns having the smallest eigen value, the energy preserving level gradually decreases. That is, depending on a degree to which noise is removed in generating an eigen-codebook, Ps may be varied. The Ps may be appropriately set in consideration of the number of facial images, the number of segments of the facial image, and the number of predetermined feature points in the facial image.
Each column vector of MEs may be provided as a linear combination of column vectors of Ms as shown in Equation below. That is, each principal component may be represented as a linear combination of histogram data of feature vectors.

Ms·Cs=MEs  [Equation]

herein, · represents a matrix multiplication. The Cs is a coefficient matrix, and represents a correlation between the Ms and the MEs. For example, Cs may be calculated as Equation below.

Cs=(MHOGsT·MHOGs)−1MHOGsT·MEHOGs,  [Equation]

herein, Cs εn×(Ps+1), and R is a real number, and T is a transposed matrix. Although Cs is calculated using the above Equation as an example, the method of calculating Cs is not limited thereto.
Thereafter, the training unit 102 may calculate eigen directional vectors with respect to predetermined feature points in a facial image respectively by using the Cs. The feature points may be a portion that is able to represent characteristics of a face, for example, corners of a mouth, eyes, a nose, a mouth. The training unit 102 may calculate a direction vector Vs,k from a center of a segment s of a nth facial image to a predetermined feature point k in the facial image as shown in Equation below, and may calculate an eigen directional vector VEDVs,k by using the Vs,k. Herein, R represents a real number.

Vs,k=[v1s,k, . . . , vns,k]ε2×n  [Equation]

The training unit 102 may calculate the eigen directional vector VEDVs,k by using Equation below.

VEDVs,k=Vs,k·Cs  [Equation]

As described above, the training unit 102 may acquire direction vectors corresponding to respective column vectors (principal components) of MEs. That is, the training unit 102 may represent a correlation between a feature vector of each segment of a facial image and location of a predetermined feature point in the facial image by using the Cs.
The eigen-codebook may include the VEDVs,k.
The process of generating the eigen-codebook in the training unit 102 may be performed as a pre-processing before a feature point detection process of the detection unit 104. According to exemplary embodiments of the present disclosure, only feature vectors of predetermined segments are used without performing a pre-alignment having a high complexity. Accordingly, the time taken to detect a feature point of a face is minimized. In addition, unlike the conventional technology in which a feature vector is extracted using a pixel value, the system and method for detecting feature points of a face according to exemplary embodiments of the present disclosure may extract a feature vector of a facial image by using the HOG algorithm, ensuring a low sensitivity to the changes of a lighting and a person's posture and improving accuracy in detecting the location of a feature point.
The detection unit 104 detects the location of a feature point in a facial area of a target image by using the eigen-codebook generated by the training unit 102. Here, the target image may be an image whose feature points are to be detected, and may include a facial area of a human. Although the target image may be a captured image or photo of a facial area of a human or a computer graphic including a facial area of a human, the type of the target image is not limited thereto.
Referring to FIGS. 3 to 5, a process of detecting the location of a feature point of a facial area of a target image in the detection unit 104 is described in detail. First, referring to FIG. 3, the detection unit 104 may detect a facial area from a target image. The detection unit 104 may detect a facial area from a target image by using the Adaboost algorithm as an example, but the method of detecting a facial area from a target image in the detection unit 104 is not limited thereto. In FIG. 3, a facial area detected by the detection unit 104 is illustrated as a quadrangle. Then, the detection unit 104 may divide the facial area into predetermined sizes. The detection unit 104 may adjust a size of the facial area to 72×72 pixels, and divide the facial area into 9×9 grids, so that 81 segments are obtained. However, the shape and number of segments of a facial area are not limited thereto.
Referring to FIG. 4, the detection unit 104 may detect a feature vector of each segment of the facial area. The detection unit 104 may calculate a feature vector by applying a predetermined feature point detection algorithm to each segment of the facial area. For example, the detection unit 104 may calculate a feature vector by applying the HOG algorithm to each segment of the facial area. However, the method of calculating a feature vector in the detection unit 104 is not limited thereto, and the detection unit 104 may calculate a feature vector by using various algorithms, such as SIFT and SURF. In FIG. 4, a feature vector of a segment s is represented using hs. The hs may be represented as a linear combination of values of the MEs of the eigen-codebook as shown in Equation below. For example, the detection unit 104 may obtain cis by projecting hs onto an HOG space. As described in the previous training process of the training unit 102, principal components of a statistical histogram and principal components of a direction vector are obtained from histogram data of feature vectors, and histogram data of a certain feature vector is represented, using the principal component of a histogram, with a minimum error as shown in Equation below. Herein, ≈ may be indicated as =.




  
    
      
        
          
            h
            s
          
          ≈
          
            
              h
              ave
              s
            
            +
            
              
                ∑
                
                  i
                  =
                  1
                
                
                  P
                  s
                
              
              ⁢
              
                
              
              ⁢
              
                
                  c
                  i
                  s
                
                ⁢
                
                  h
                  ei
                  s
                
              
            
          
        
        ,
      
    
    
      
        [
        Equation
        ]
      
    
  




herein, principal components except for haves, that is, h1s to hePss are orthogonal to each other. Accordingly, cis is easily obtained by an inner product of a value of hs minus haves and each principal component, which is expressed as Equation below.

cis=hs−haves,heis,  [Equation]

herein, a, b represents an inner product of a and b.
In addition, the detection unit 104 may represent a direction vector vs,k from a segment s of a facial area to a feature point k as a linear combination of values of the VEDVx,k by using Equation below.




  
    
      
        
          v
          
            s
            ,
            k
          
        
        =
        
          
            v
            ave
            
              s
              ,
              k
            
          
          +
          
            
              ∑
              
                i
                =
                1
              
              
                P
                s
              
            
            ⁢
            
              
            
            ⁢
            
              
                c
                i
                s
              
              ⁢
              
                v
                ei
                
                  s
                  ,
                  k
                
              
            
          
        
      
    
    
      
        [
        Equation
        ]
      
    
  




In this process, the detection unit 104 may obtain a direction vector vs,k from a center of a segment s of a facial area to a feature point k. The detection unit 104, which has information regarding the location of the center of the segment s, may obtain location coordinates (x, y) of the feature point k by using the location information and the direction vector vs,k. That is, the detection unit 104 adds the direction vector vs,k to the coordinates of the center of the segment s, and determines location coordinates of an end point of the added direction vector vx,k as location coordinates (x, y) of the feature point k.
In addition, referring to FIG. 5, the detection unit 104 may determine a location coordinate of the feature point k at which the summation of the distances between the coordinate and the direction vectors from centers of the respective segments of the facial area to the feature point k.
In this process, the detection unit 104 calculates direction vectors from the centers of the respective segments of the facial area to the feature point k, and by using the sizes of the calculated direction vectors, determines the final location coordinates of the feature point k. The respective direction vectors shown in FIG. 5 are not guaranteed to meet at one point. Thus, according to exemplary embodiments of the present to disclosure, the detection unit 104 calculates coordinates at which sizes of the respective direction vectors of FIG. 5 are smallest as the optimum solution of the location coordinates (x, y) of the feature point k, and determines the coordinates as the final location coordinates of the feature point k. The location coordinates (x, y) of the feature point k are calculated using Equation below.




  
    
      
        
          argmin
          
            x
            ,
            y
          
        
        ⁢
        
          
        
        ⁢
        
          
            ∑
            
              s
              =
              1
            
            S
          
          ⁢
          
            
          
          ⁢
          
            
              w
              s
              2
            
            ⁢
            
              
                
                
                  
                    
                      a
                      s
                    
                    ⁢
                    x
                  
                  +
                  
                    
                      b
                      s
                    
                    ⁢
                    y
                  
                  +
                  
                    c
                    s
                  
                
                
              
              2
            
          
        
      
    
    
      
        [
        Equation
        ]
      
    
  




herein, (as, bs, cs) represents a coefficient that satisfies asx+bsy+cs=0 at as2+bs2=1, and S is the number of segments of a facial area. In this case, a weight ws is given to the size of each direction vector, and the ws is calculated through Equation below.




  
    
      
        
          
            w
            s
          
          =
          
            
              w
              s
              s
            
            ·
            
              e
              
                -
                
                  
                    d
                    2
                  
                  
                    L
                    2
                  
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            w
            s
            s
          
          =
          
            〈
            
              
                h
                s
              
              ,
              
                
                  h
                  ave
                  s
                
                +
                
                  
                    ∑
                    
                      i
                      =
                      1
                    
                    
                      P
                      s
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      c
                      i
                      s
                    
                    ⁢
                    
                      h
                      ei
                      s
                    
                  
                
              
            
            〉
          
        
      
    
    
      
        [
        Equation
        ]
      
    
  




That is, ws is calculated by multiplying a similarity between a feature vector hs and principal component representations of feature vectors obtained through an inner product by a value that exponentially decreases in consideration of a distance between a feature point of a facial area and a segment. Herein, d represents a distance between a center of a segment s and a feature point, and L represents a half length of a quadrangle representing a segment.
In this case, ws may be defined according to an eigen value of MEs as shown in Equation below.




  
    
      
        
          w
          s
        
        =
        
          {
          
            
              
                
                  
                    w
                    s
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                          
                            c
                            ej
                            s
                          
                          
                        
                      
                      <
                      
                        2.5
                        ⁢
                        
                          
                        
                        ⁢
                        
                          λ
                          ej
                          s
                        
                        ⁢
                        
                          
                        
                        ⁢
                        for
                        ⁢
                        
                          
                        
                        ⁢
                        j
                      
                    
                    =
                    
                      1
                      ⁢
                      
                        
                      
                      ⁢
                      ...
                      ⁢
                      
                        
                      
                      ⁢
                      
                        P
                        s
                      
                    
                  
                
              
              
                
                  0
                
                
                  otherwise
                
              
            
            .
          
        
      
    
    
      
        [
        Equation
        ]
      
    
  




The above Equation is provided to consider occlusion of at least one portion of a target image, in which eigen values (λe1s, . . . , λePss) of MEs are used. Herein, cejs (or cis) is a projection coefficient obtained by projecting hs onto an eigen HOG space. The detection unit 104 may use the weight ws as it is if each projection coefficient (a principal component coefficient) exists within a range of 2.5 times of a square of an eigen value, and if not, the weight ws regarded as 0 and is not reflected on calculation of location coordinates (x, y) of the feature point k. That is, the above Equation is provided to determine whether a feature vector is present in the existing feature vector principal component space. The coefficient is illustrated as 2.5, but the present disclosure is not limited thereto. For example, the coefficient may be 2.3 or any other number.
According to exemplary embodiments of the present disclosure, statistical inference based on a plurality of facial images for training is used instead of extracting local patterns at one point of a face, so that the location of a feature point in a facial area of a target image can be rapidly and accurately detected. In addition, according to exemplary embodiments of the present disclosure, a pre-trained eigen-codebook is used, thereby minimizing the computational complexity in detecting a feature point and taking a minimized storage, compared with the conventional technology using a pattern searching algorithm. Further, the facial feature point detection according to exemplary embodiments of the present disclosure can be easily implemented on low-performance hardware, such as a mobile application.
That is, the method of detecting a facial feature point according to exemplary embodiments of the present disclosure can significantly reduce the total time taken to detect facial feature points and significantly reducing the required storage while having a small difference in the accuracy of detecting facial feature points, compared to when using the conventional search algorithm, such as approximate nearest-neighbor search (ANNS) and nearest neighbor search (NNS).
The above modules of the system for detecting facial feature points 100 may be implemented with hardware. For example, the system for detecting facial feature points 100 may be implemented or included in a computing apparatus. The computing apparatus may include at least one processor and a computer-readable storage medium such as a memory that is accessible by the processor. The computer-readable storage medium may be disposed inside or outside the processor, and may be connected with the processor using well known means. A computer executable instruction for controlling the computing apparatus may be stored in the computer-readable storage medium. The processor may execute an instruction stored in the computer-readable storage medium. When the instruction is executed by the processor, the instruction may allow the processor to perform an operation according to an example embodiment. In addition, the computing apparatus may further include an interface device configured to support input/output and/or communication between the computing apparatus and at least one external device, and may be connected with an external device (for example, a device in which a system that provides a service or solution and records log data regarding a system connection is implemented). Furthermore, the computing apparatus may further include various different components (for example, an input device and/or an output device), and the interface device may provide an interface for the components. Examples of the input device include a pointing device such as a mouse, a keyboard, a touch sensing input device, and a voice input device, such as a microphone. Examples of the output device include a display device, a printer, a speaker, and/or a network card. Thus, the training unit 102 and the detection unit 104 of the system for detecting facial feature points 100 may be implemented as hardware of the above-described computing apparatus.
FIG. 6 is a flowchart showing a method for detecting facial feature points according to an exemplary embodiment of the present disclosure. In the flowchart shown in FIG. 6, the method is illustrated as being divided into a plurality of operations. However, at least one of the operations may be performed in a changed order, concurrently performed in combination with other operations, omitted, sub-divided, or one or more additional operations which are not illustrated in the diagram may be performed.
First, the training unit 102 divides each of a plurality of facial images into segments of a predetermined size (S602). For example, the training unit 102 may adjust a size of each facial image to 72×72 pixels, and divide the facial image into 9×9 grids, so that 81 segments are obtained.
Then, the training unit 102 generates an eigen-codebook representing a correlation between a feature vector of each segment of the facial image and location of a predetermined feature point in the facial image (S604). The method of generating the eigen-codebook in the training unit 102 has been described above in detail, and detailed description thereof will be omitted.
Then, the detection unit 104 detects a facial area from a target image (S606). For example, the detection unit 104 may detect a facial area from a target image by using the Adaboost algorithm.
Then, the detection unit 104 divides the facial area into segments of a predetermined size (S608).
Then, the detection unit 104 detects a feature vector of each segment of the facial area (S610). The detection unit 104 may calculate a feature vector by applying the HOG algorithm to each segment of the facial area.
Finally, the detection unit 104 detects the location of a feature point of the facial area by using the detected feature vector and the eigen-codebook (S612). Since the method of detecting the location of the feature point of the facial area by using the eigen-codebook has been described above, detailed description thereof will be omitted.
It will be apparent to those skilled in the art that various modifications can be made to the above-described exemplary embodiments of the present disclosure without departing from the spirit or scope of the disclosure. Thus, it is intended that the present disclosure covers all such modifications provided they come within the scope of the appended claims and their equivalents.

## Claims

1. A system for detecting a feature point of a face, the system comprising:
a training unit implemented in a computing apparatus configured to divide each of a plurality of facial images into segments of a predetermined size, and generate an eigen-codebook representing a correlation between a feature vector of each of the divided segments and location of a predetermined feature point in the facial image; and
a detection unit implemented in a computing apparatus configured to detect a facial area from a target image, divide the facial area into segments of a predetermined size, detect a feature vector of each of the divided segments of the facial area, and detect a location of a feature point in the facial area by using the detected feature vector and the eigen-codebook,
wherein the training unit is configured to obtain Ms=[h1s, . . . , hns] by applying a predetermined feature point detection algorithm to each segment of the facial image, obtain MEs=[haves, he1s, . . . , hePss] by applying Principal Component Analysis (PCA) algorithm to the Ms, and generate the eigen-codebook by using the Ms and the MEs, wherein hns is data of a feature vector of a segment s of a nth facial image, M is a matrix, haves may be an average among data h1s . . . and hns, hePss may represent a piece of eigen data obtained by applying the PCA algorithm to data h1s . . . and hns, and when a piece of eigen data heis has an eigen value of λeis, λe1s> . . . >λePs, and Ps is a total number of data he1s . . . and hePss.

2. The system of claim 1, wherein the training unit is configured to calculate Cs that represents a correlation between the Ms and the MEs and satisfies Ms·Cs=MEs, and generate the eigen-codebook by using the Cs,
wherein · represents a matrix multiplication.

3. The system of claim 2, wherein the training unit is configured to calculate a direction vector Vs,k from a center of the segment s of the nth facial image to a predetermined feature point k of the facial image, the direction vector Vs,k satisfying Vs,k=[v1s,k, . . . , vns,k]ε2×n, and to calculate VEDVs,k by using VEDVs,k=Vs,k·Cs, wherein the eigen-codebook includes the VEDVs,k.

4. The system of claim 3, wherein the detection unit is configured to obtain hs by applying a predetermined feature point detection algorithm to each segment of the facial area, obtain cis by representing the hs as a combination of values of the MEs by using




  
    h
    s
  
  ≈
  
    
      h
      ave
      s
    
    +
    
      
        ∑
        
          i
          =
          1
        
        
          P
          s
        
      
      ⁢
      
        
      
      ⁢
      
        
          c
          i
          s
        
        ⁢
        
          h
          ei
          s
        
      
    
  




and cis=hs−haves, heis in which a, b is an inner product of a and b; and detecting the location of the feature point of the facial area by using the cis.

5. The system of claim 4, wherein the detection unit is configured to represent a direction vector vs,k from a center of the segment s of the facial area to the feature point k as a combination of values of the vEDVs,k by using




  
    
      v
      
        s
        ,
        k
      
    
    =
    
      
        v
        ave
        
          s
          ,
          k
        
      
      +
      
        
          ∑
          
            i
            =
            1
          
          
            P
            s
          
        
        ⁢
        
          
        
        ⁢
        
          
            c
            i
            s
          
          ⁢
          
            v
            ei
            
              s
              ,
              k
            
          
        
      
    
  
  ,




and detect the location of the feature point of the facial area by using the vs,k.

6. The system of claim 5, wherein the detection unit is configured to detect the location of the feature point of the facial area by determining a location coordinate of the feature point k at which the summation of the distances between the coordinate and the direction vectors from centers of the respective segments of the facial area to the feature point k.

7. A method for detecting a feature point of a face, the method comprising:
dividing, by a training unit, each of a plurality of facial images into segments of a predetermined size;
generating, by the training unit, an eigen-codebook representing a correlation between a feature vector of each of the divided segments and location of a predetermined feature point in the facial image;
detecting, by a detection unit, a facial area from a target image;
dividing, by the detection unit, the facial area into segments of a predetermined size;
detecting, by the detection unit, a feature vector of each of the divided segments of the facial area; and
detecting, by the detection unit, a location of a feature point in the facial area by using the detected feature vector and the eigen-codebook;
wherein the generating of the eigen-codebook comprises:
obtaining Ms=[h1s, . . . , hns] by applying a predetermined feature point detection algorithm to each segment of the facial image;
obtaining MEs=[haves, he1s, . . . , hePss] by applying Principal Component Analysis (PCA) algorithm to the Ms; and
generating the eigen-codebook by using the Ms and the MEs,
wherein hns is data of a feature vector of a segment s of a nth facial image, M is a matrix, haves is an average among data h1s . . . and hns, hePss represents a piece of eigen data obtained by applying the PCA algorithm to data h1s . . . and hns, and when a piece of eigen data heis has an eigen value of λeis, λe1s> . . . >λePs, and Ps is a total number of data he1s . . . and hePss.

8. The method of claim 7, wherein the generating of the eigen-codebook by using Ms and the MEs comprises:
calculating Cs that represents a correlation between the Ms and the MEs and satisfies Ms·Cs=MEs in which · represents a matrix multiplication; and
generating the eigen-codebook by using the Cs.

9. The method of claim 8, wherein the generating of the eigen-codebook by using the Cs comprises:
calculating a direction vector Vs,k from a center of the segment s of the nth facial image to a predetermined feature point k of the facial image, the direction vector Vs,k satisfying Vs,k=[v1s,k, . . . , vns,k]ε2×n, and
calculating VEDVs,k by using VEDVs,k=Vs,k·Cs, wherein the eigen-codebook includes the VEDVs,k.

10. The method of claim 9, wherein the detecting of a location of a feature point comprises:
obtaining hs by applying a predetermined feature point detection algorithm to each segment of the facial area;
obtaining cis by representing the hs as a combination of values of the MEs by using





  
    h
    s
  
  ≈
  
    
      h
      ave
      s
    
    +
    
      
        ∑
        
          i
          =
          1
        
        
          P
          s
        
      
      ⁢
      
        
      
      ⁢
      
        
          c
          i
          s
        
        ⁢
        
          h
          ei
          s
        
      
    
  




and cis=hs−haves, heis in which a, b is an inner product of a and b; and
detecting the location of the feature point of the facial area by using the cis.

11. The method of claim 10, wherein the detecting of the location of the feature point of the facial area by using the cis comprises:
representing a direction vector vs,k from a center of the segment s of the facial area to the feature point k as a combination of values of the VEDVs,k by using





  
    
      v
      
        s
        ,
        k
      
    
    =
    
      
        v
        ave
        
          s
          ,
          k
        
      
      +
      
        
          ∑
          
            i
            =
            1
          
          
            P
            s
          
        
        ⁢
        
          
        
        ⁢
        
          
            c
            i
            s
          
          ⁢
          
            v
            ei
            
              s
              ,
              k
            
          
        
      
    
  
  ;




and
detecting the location of the feature point of the facial area by using the vs,k.

12. The method of claim 11, wherein in the detecting of the location of the feature point of the facial area by using the vs,k, the location of the feature point of the facial area is detected by determining a location coordinate of the feature point k at which the summation of the distances between the coordinate and the direction vectors from centers of the respective segments of the facial area to the feature point k.