Abstract:
A method for locating face landmarks (e.g., eyes, nose, etc.) from an image is provided. The method comprises preprocessing an input image for alignment; comparing the aligned input image with a reference image located with face landmarks; calculating distances of pixels and pixel rows of the images; finding a correspondence between pixel rows of the reference image and that of the input image; and using the correspondence and the face landmarks of the reference image to find face landmarks of the aligned input image.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to the field of image recognition and, more particularly, to a method for locating face landmarks of an image by using dynamic programming.  
           [0003]    2. Description of Related Art  
           [0004]    Conventionally, local features are widely utilized for recognition in order to find a location of the face appearing in an image. As known that local features of the face comprise eyes, nose, lips, cheeks, forehead, etc. One or more of such local features of the image are compared with fetched image in order to confirm whether they are the same. As such, an exact representation of each local feature of the face is essential to a successful subsequent recognition of a portion in an image (e.g., the face).  
           [0005]    Typically, there are two approaches for finding face landmarks (e.g., eyes, nose, and lips) from an image of the face. The first one is to use image processing, such as filtering, morphological operation, or threshold operation, to select a number of candidate portions from the face landmarks, and then confirm a portion or all of the candidates as features. The second one employs a graph matching method to represent a face model by a featured graph, wherein nodes are used to represent feature locations, and edges between the nodes are used to represent relative locations of the features. The feature value of each node is obtained by performing the image processing. The model is then shifted around the image, so as to locate the face landmarks by image matching.  
           [0006]    An image processing method is disclosed in U.S. Pat. No. 5,805,475 which first calculates a threshold by a heuristic method or statistics. The threshold is critical to a successful recognition. In the patent, each of the morphological or threshold operation involves a number of threshold determinations. In the case of utilizing the heuristic method, the threshold is required to be amended in response to variability of images as observed. As a result, the implementation is difficult and an efficient recognition of face landmarks in the image is made impossible.  
           [0007]    A graph matching method is disclosed in U.S. Pat. No. 6,222,939 which describes a number of nodes each having a feature value. For comparing with a graph model, it is required to calculate feature values of an image. Although not all pixels are required to calculate, a great number of node locations are required to fetch. In this patent, a two dimensional searching on the image is essential. Also, the feature values for describing the face image are obtained by a complex two-dimensional calculation. Thus, a number of complex calculations and comparisons are required in each process of face landmarks location of an image. This bears a great burden upon the computer system, resulting in a significant decrease of efficiency.  
           [0008]    Therefore, it is desirable to provide a novel method for locating face landmarks in an image to mitigate and/or obviate the aforementioned problems.  
         SUMMARY OF THE INVENTION  
         [0009]    An object of the present invention is to provide a method for locating face landmarks in an image. The invention employs a one dimensional operation twice instead of a searching on a two dimensional matrix so as to reduce the number of operations, increase the image recognition accuracy, efficiently find face landmarks of an input image by comparison, and reduce system load.  
           [0010]    Another object of the present invention is to provide a method for locating face landmarks in an image wherein a correspondence between a reference image and an input image is obtained by comparison without utilizing a heuristic approach. Thus, the invention is highly efficient in practice.  
           [0011]    To achieve the object, the method for locating face landmarks in an image of the present invention comprises the steps of: (a) locating a face region in the input image by means of skin color; (b) finding, from the face region, a plurality of feature regions having different colors from the skin color, so as to align the input image according to the feature regions thereby obtaining an aligned input image; (c) comparing the aligned input image with a reference image labeled with face landmarks by performing a plurality of comparisons between pixel rows R i  (i=1, 2, 3, . . . , m) of the reference image and pixel rows T u  (u=1, 2, 3, . . . , p) of the aligned input image for obtaining m x p distances d(R i , T u ); and (d) in a first matrix formed of nodes (i,u) (i=1, 2, 3, . . . , m; and u=1, 2, 3, . . . , p), associating each node (i,u) with one of the distances d(R i , T u ), and in a path from a starting point (1, 1) to an ending point (p, m) of the first matrix, finding a minimum accumulated value of the distances d(R i , T u ) as a first optimal path, so as to obtain a correspondence between all pixel rows R i  of the reference image and all pixel rows T u  of the input image, thereby using the correspondence and the face landmarks of the reference image to find face landmarks of the aligned input image.  
           [0012]    Other objects, advantages, and novel features of the invention will become more apparent from the detailed description when taken in conjunction with the accompanying drawings. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]    [0013]FIG. 1 is a flow chart illustrating a process of locating face landmarks in an image according to the invention;  
         [0014]    [0014]FIG. 2 is a flow chart illustrating a process of aligning a face region according to the invention;  
         [0015]    [0015]FIG. 3A is a schematic plan view showing a face oblique line in an image;  
         [0016]    [0016]FIG. 3B is an enlarged fragmentary view of FIG. 3A;  
         [0017]    [0017]FIG. 4A shows a reference image graph according to the invention;  
         [0018]    [0018]FIG. 4B shows an input image graph according to the invention;  
         [0019]    [0019]FIG. 5 is a flow chart illustrating a process of comparing the reference image graph with the aligned input image graph for obtaining an image with located face landmarks;  
         [0020]    [0020]FIG. 6 is a plot of a first matrix according to the invention;  
         [0021]    [0021]FIG. 7 is a flow chart illustrating a process of calculating a distance d(R i , T u ) according to the invention;  
         [0022]    [0022]FIG. 8 shows the pixels of the reference image R i  and the input image T u  versus gray level; and  
         [0023]    [0023]FIG. 9 is a plot of a second matrix according to the invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0024]    With reference to FIG. 1, there is shown a flow chart illustrating a process of locating face landmarks in an image in accordance with the invention. An image-processing device fetches an input image  10  from a pictured object (e.g., human face) (step S 101 ). It is found that portions other than the face such as clothes, furniture, background color, and etc. contained in the input image  10  may interfere with a face recognition performed by the image-processing device. Hence, a mean-shift algorithm is adopted by the embodiment. Further, a skin color model is employed to perform a color segment on the input image  10 . As a result, background color is eliminated by performing analysis and matching operations on the skin color model. Therefore, a face region  20  having a color similar with the skin color shown in the input image  10  is obtained (step S 102 ).  
         [0025]    Since the face region  20  may be oblique, an alignment of the input image  10  is required to make the face region  20  straight. At this time, a feature region  30  having a different skin color from that of the face region  20  has to be located therein (step S 103 ). It is known that there are a number of symmetric portions on the face region  20  such as eyes and eyebrows, which are distinct in color from other portions of the face. Therefore, a non-skin color model is employed to locate the feature region  30  of the face region  20 , which may be of eyes or eyebrows. Moreover, a pair of symmetric regions is found from the feature region  30 . A horizontal oblique angle is measured from a straight line between centers of the symmetric regions relative to a horizontal line. The face region  20  is thus rotated by the horizontal oblique angle to be coincidental with the horizontal line, thereby obtaining an aligned input image  40  (step S 104 ). Finally, the aligned input image  40  is compared with a reference image marked in gray level and located with face landmarks for finding a correspondence therebetween, thereby obtaining an image  50  with located face landmarks (step S 105 ). A detail of the comparison step of S 105  will be described hereinafter. Furthermore, the face landmarks described can be eyes, eyebrows, nose, lips, cheeks, forehead, etc.  
         [0026]    With reference to FIG. 2 in conjunction with FIGS. 3A and 3B, there is shown a flow chart illustrating a process of aligning the face region  20  according to the invention. As seen from FIG. 3A, the feature region  30  fetched from the non-skin model is interfered by a personal article (e.g., a pair of eyeglasses) or shaded region. As a result, an extra region in addition to eyes and eyebrows is generated. Therefore, a central point of each feature region  30  is firstly calculated prior to aligning the face region  20  (step S 201 ). Next, two relevant feature regions  30  are grouped as a pair prior to forming a line between central points of every two feature regions  30  (step S 202 ). As a result, a plurality of oblique lines are obtained. Note that only one line  32  from a central point of one eyebrow to that of the other eyebrow is shown in FIG. 3A. It is known that eyes or eyebrows of a person are symmetric. Hence, it is possible of finding a most similar shape from the matched feature regions  30  based on the symmetric features and a possible oblique degree of the face. As a result, both an optimal face oblique line  32  describing the oblique face and an optimal horizontal oblique angle θ of the face relative to a horizontal line  33  are obtained (step S 203 ).  
         [0027]    As shown in FIG. 3B, which gives a partially enlarged view of the FIG. 3A, the image-processing device fetches feature regions  301 ,  302  for calculating central points  311 ,  312 . Furthermore, the oblique line  32  from one central point  311  to the other one  312  is drawn, thereby obtaining an oblique angle θ of the face (i.e., the oblique line  32 ) relative to the horizontal line  33 . Hence, a central moment of inertia (CMI) of the line  32  plotted on X-Y coordinate for each feature region  301 ,  302 may be expressed as:  
           ∑   y                               ∑   x                    [         (     x   -     x   _       )        sin                 θ     -       (     y   -     y   _       )        cos                 θ       ]     2         ,                         
 
         [0028]    where (x,y) is a pixel location in the feature region and ({overscore (x)},{overscore (y)}) is a central point of the feature region. Thus, CMI represents a shape of each feature region. In this regard, a difference between CMIs of the feature regions  301 ,  302  means a difference of the shapes of the feature regions  301 ,  302 .  
         [0029]    Moreover, a minimum difference between CMIs is taken as the optimal face oblique line described in step S 203 . In the embodiment as shown in FIG. 3B, the oblique line  32  passing the central points of the feature regions is the optimal face oblique line  32  which has the minimum CMI. Consequently, the horizontal oblique angle θ is obtained. Next, by rotating the horizontal oblique angle θ clockwise, the face region  20  (i.e., the oblique line  32 ) is caused to be coincidental with the horizontal line  33 ; i.e., the oblique angle θ is reduced to zero (step S 204 ). As a result, an aligned input image  40  is obtained in which the line passing eyes of eyebrows is substantially coincidental with the horizontal line as shown in FIG. 1. Note that in step S 202  of the face region  20  alignment process, it is possible that an excess of lines are drawn due to too many fetched feature regions  30 . This can undesirably increase a load upon system. Hence, preferably only an oblique line less than or equal to a predetermined oblique angle of the face is maintained without calculating and comparing all matched CMIs.  
         [0030]    With reference to FIGS. 4A and 4B, a comparison process depicted in step S 105  is further illustrated. As stated above, the input image  10  (FIG. 1) can be converted into the aligned input image  40  (FIG. 4B) based on the steps S 101  to S 104 . For finding the face landmarks, a locating technique is employed by taking a reference image  60  as a basis. Information about location of the face landmarks is already stored in the reference image  60 . Thus, it is sufficient to find corresponding locations of the face landmarks of the aligned input image  40  and the reference image  60 .  
         [0031]    With reference to FIG. 5 in conjunction with FIG. 6, there is shown a flow chart illustrating a process of finding face landmarks. Firstly, it is assumed that the reference image  60  has a dimension of m rows by n columns and the aligned input image  40  has a dimension of p rows by q columns (step S 501 ). R i  represents a pixel row of the reference image  60 , where i=1, 2, 3, . . . , m. T u  represents a pixel row of the aligned input image  40 , where u=1, 2, 3, . . . , p. By comparing R i  and T u , m×p distances d(R i , T u ) are obtained (step S 502 ). As shown in FIG. 6. in a first matrix M 1  formed of nodes (i,u) (i=1, 2, 3, . . . , m; and u=1, 2, 3, . . . , p), each node (i,u) is associated with a distance d(R i , T u ). The smaller of d(R i , T u ) is, the closer of two nodes are. In a path from starting point (1, 1) to ending point (p, m) of the first matrix M 1 , dynamic programming is utilized to find a minimum accumulated value of distances d(R i , T u ) of nodes taken as an optimal path (step S 503 ), so as to obtain a correspondence between all pixel rows R i  of the reference image  60  and all pixel rows T u  of the aligned input image  40 . The correspondence together with locations of the face landmarks of the reference image  60  are used to find corresponding face landmarks of the aligned input image  40  (step S 504 ). As a result, an image  50  with located face landmarks is obtained as shown in FIG. 1.  
         [0032]    With reference to FIG. 7 in conjunction with FIGS. 8 and 9, a detailed process of calculating each distance d(R i , T u ) depicted in step S 503  is illustrated. For calculating a distance d(R i , T u ) between two pixel rows, it is required to compare pixels between the same. As shown in FIG. 8, a graph of pixels of R i  (obtained in FIG. 4A) and T u  (obtained in FIG. 4B) passing through centers of lips versus gray level is plotted. It is seen that each pixel has a corresponding distinct gray level. For the reference image  60 , each pixel row R i  has a number n of pixels and a gray level r i,j , where j=1,2,3, . . . , n. Furthermore, for the aligned input image  40 , each pixel row T u  has a number q of pixels and a gray level t u,v , where v=1,2,3, . . . , q.  
         [0033]    First, it is to compare the row correspondences between a difference of gray level Δr i,j =r i,j −r i,j−1 , of two adjacent pixels on the pixel row R i  of the reference image  60  and a difference of gray level Δt u,v =t u,v −t u,v−1  of two adjacent pixel on the row T u  of the face region  20  (step S 701 ). As a result, a number (n−1)×(q−1) of distances d(r i,j ,t u,v )=|Δr i,j −Δt u,v | are obtained, where r i,j  (j=1,2,3, . . . ,n) represents a gray level of pixels of pixel row R i , and t u,v  (v=1,2,3, . . . ,q) represents a gray level of pixels of pixel row T u . Likewise, as shown in FIG. 9, in a second matrix M 2  formed of nodes (Δr i,j , Δt u,v )(j=1,2,3 . . . n, and v=1,2,3 . . . q), each node (Δr i,j , Δt u,v ) is associated with a distance d(R i,j , T u,v ) In a path from starting point (Δr i,2 , Δt u,2 ) to ending point (Δr i,n , Δt u,q ) of the second matrix M 2 , the dynamic programming is also utilized to find a minimum accumulated value of distances d(R i,j , T u,v ) of nodes taken as an optimal path (step S 702 ). Furthermore, a correspondence between pixels is obtained in which a minimum accumulated value is taken as a distance d(R i , T u ) of pixel rows R i  and T u .  
         [0034]    In view of the foregoing, it is found that two comparisons are performed between the reference image  60  and the aligned input image  40 . First, there is found an optimal correspondence between pixels from all pixel rows, i.e., the second matrix M 2  shown in FIG. 9. Next, there is found an optimal correspondence between pixel rows from all pairs, i.e., the first matrix M 1  shown in FIG. 6. For finding a corresponding location of one pixel of the reference image  60  in the aligned input image  40 , first, it is to find an optimal corresponding pixel row in the aligned input image  40  based on a result of the first matrix M 1  started from the location of the pixel row. Next, it is to find a pixel corresponding to the optimal pixel row from a result of the second matrix M 2 .  
         [0035]    Thus, the invention employs a one-dimensional operation twice instead of a searching on a two dimensional matrix. Furthermore, a simple difference of gray level in an image is taken as the face landmarks. This has the benefits of quick and simple operation, more efficiency in an image recognition process, and a fast finding in an image having located face landmarks from the input image.  
         [0036]    Although the present invention has been explained in relation to its preferred embodiment, it is to be understood that many other possible modifications and variations can be made without departing from the spirit and scope of the invention as hereinafter claimed.