Abstract:
Methods and systems are provided for selecting features that will be used to recognize faces. Three-dimensional models are used to synthesize a database of virtual face images. The virtual face images cover wide appearance variations, different poses, different lighting conditions and expression changes. A joint boosting algorithm is used to identify discriminative features by selecting features from the plurality of virtual images such that the identified discriminative features are independent of the other images included in the database.

Description:
BACKGROUND  
       [0001]     Face recognition computer algorithms are used to identify or verify individuals. Each person has characteristics that are useful during the recognition process. A fundamental challenge in face recognition lies in identifying the facial features that are important for the identification of faces. For example, if three faces have a feature that is very similar, such as nose length, it is difficult to use that feature to distinguish the faces. In contrast, if the same three faces have different eye colors, eye color is a feature that can be used to reliably distinguish the faces.  
         [0002]     Typically recognition modules are trained by analyzing a few samples of each face. Samples of the same face may have appearance variations due to variations resulting from varying lighting/illumination conditions, different head poses and different facial expressions. A small number of samples per face cannot capture the wide range of variations that are likely to exist when face recognition algorithms are utilized.  
         [0003]     A typical approach to capture discriminative facial features is Bayesian face recognition. In this algorithm, differences images are calculated between training images. With this kind of transformation, a face recognition problem is converted to a binary classification problem by predicting whether the differences images are from the same individual. However, this algorithm is not capable of large scale training. Moreover, this kind of transformation is not invertible, therefore facial information is lost to some extent.  
       SUMMARY  
       [0004]     Methods and systems are provided for selecting features that will be used to recognize faces. Three-dimensional models are used to synthesize a database of realistic face images which cover wide appearance variations, different poses, different lighting conditions and expression changes. A joint boosting algorithm is used to identify discriminative features by selecting features from the plurality of virtual images such that the identified discriminative features can be generalized to other database.  
         [0005]     These and other advantages will become apparent from the following detailed description when taken in conjunction with the drawings. A more complete understanding of the present invention and the advantages thereof may be acquired by referring to the following description in consideration of the accompanying drawings, in which like reference numbers indicate like features. The invention is being described in terms of exemplary embodiments. Numerous other embodiments, modifications and variations within the scope and spirit of the appended claims will occur to persons of ordinary skill in the art from a review of this disclosure. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]      FIG. 1  illustrates an exemplary computer system in which embodiments of the invention may be implemented.  
         [0007]      FIG. 2  illustrates a method of selecting facial features used to recognize faces with a face recognition module, in accordance with an embodiment of the invention.  
         [0008]      FIG. 3  shows three-dimensional face models collected from a three-dimensional laser-scanner.  
         [0009]      FIG. 4  shows a plurality of virtual facial images that have different poses, illumination and expressions, in accordance with an embodiment of the invention.  
         [0010]      FIG. 5  shows a joint boosting feature selection algorithm for face recognition, in accordance with an embodiment of the invention.  
         [0011]      FIG. 6  shows a proposed joint boosting algorithm, in accordance with an embodiment of the invention. 
     
    
     DETAILED DESCRIPTION  
       [0000]     Exemplary Operating Environment  
         [0012]      FIG. 1  is a functional block diagram of an example of a conventional general-purpose digital computing environment that can be used in connection with various input devices. In  FIG. 1 , a computer  100  includes a processing unit  110 , a system memory  120 , and a system bus  130  that couples various system components including the system memory to the processing unit  110 . The system bus  130  may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The system memory  120  includes read only memory (ROM)  140  and random access memory (RAM)  150 .  
         [0013]     A basic input/output system  160  (BIOS), containing the basic routines that help to transfer information between elements within the computer  100 , such as during start-up, is stored in the ROM  140 . The computer  100  also includes a hard disk drive  170  for reading from and writing to a hard disk (not shown), a magnetic disk drive  180  for reading from or writing to a removable magnetic disk  190 , and an optical disk drive  191  for reading from or writing to a removable optical disk  192  such as a CD ROM or other optical media. The hard disk drive  170 , magnetic disk drive  180 , and optical disk drive  191  are connected to the system bus  130  by a hard disk drive interface  192 , a magnetic disk drive interface  193 , and an optical disk drive interface  194 , respectively. The drives and their associated computer-readable media provide nonvolatile storage of computer readable instructions, data structures, program modules and other data for the personal computer  100 . It will be appreciated by those skilled in the art that other types of computer readable media that can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, Bernoulli cartridges, random access memories (RAMs), read only memories (ROMs), and the like, may also be used in the example operating environment.  
         [0014]     A number of program modules can be stored on the hard disk drive  170 , magnetic disk  190 , optical disk  192 , ROM  140  or RAM  150 , including an operating system  195 , one or more application programs  196 , other program modules  197 , and program data  198 . A user can enter commands and information into the computer  100  through input devices such as a keyboard  101  and pointing device  102 . Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner or the like. These and other input devices are often connected to the processing unit  110  through a serial port interface  106  that is coupled to the system bus, but may be connected by other interfaces, such as a parallel port, game port or a universal serial bus (USB). The illustrated computer  100  includes an optional PCMCIA interface  103  that may connect at least one embodiment of an input device according to the present invention to the computer  100 . Further still, these devices may be coupled directly to the system bus  130  via an appropriate interface (not shown). A monitor  107  or other type of display device is also connected to the system bus  130  via an interface, such as a video adapter  108 . In addition to the monitor, personal computers typically include other peripheral output devices (not shown), such as speakers and printers.  
         [0015]     The computer  100  can operate in a networked environment using logical connections to one or more remote computers, such as a remote computer  109 . The remote computer  109  can be a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer  100 , although only a memory storage device  111  has been illustrated in  FIG. 1 . The logical connections depicted in  FIG. 1  include a local area network (LAN)  112  and a wide area network (WAN)  113 . Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.  
         [0016]     When used in a LAN networking environment, the computer  100  is connected to the local network  112  through a network interface or adapter  114 . When used in a WAN networking environment, the personal computer  100  typically includes a modem  115  or other means for establishing a communications over the wide area network  113 , such as the Internet. The modem  115 , which may be internal or external, is connected to the system bus  130  via the serial port interface  106 . In a networked environment, program modules depicted relative to the personal computer  100 , or portions thereof, may be stored in the remote memory storage device.  
         [0017]     It will be appreciated that the network connections shown are illustrative and other techniques for establishing a communications link between the computers can be used. The existence of any of various well-known protocols such as TCP/IP, Ethernet, FTP, HTTP, Bluetooth, IEEE 802.11x and the like is presumed, and the system can be operated in a client-server configuration to permit a user to retrieve web pages from a web-based server. Any of various conventional web browsers can be used to display and manipulate data on web pages.  
         [0018]     In one embodiment, a pen digitizer  165  and accompanying pen or stylus  166  are provided in order to digitally capture freehand input. Although a direct connection between the pen digitizer  165  and the processing unit  110  is shown, in practice, the pen digitizer  165  may be coupled to the processing unit  110  via a serial port, parallel port or other interface and the system bus  130  as known in the art. Furthermore, although the digitizer  165  is shown apart from the monitor  107 , it is preferred that the usable input area of the digitizer  165  be co-extensive with the display area of the monitor  107 . Further still, the digitizer  165  may be integrated in the monitor  107 , or may exist as a separate device overlaying or otherwise appended to the monitor  107 .  
       DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS  
       [0019]      FIG. 2  illustrates a method of selecting facial features used to recognize faces with a face recognition module, in accordance with an embodiment of the invention. First, in step  202  three-dimensional face models are collected for a group of individuals. The three-dimensional face models may be created with a three-dimensional laser-scanner. In one embodiment of the invention, the group of face models are collected from at least one hundred individuals.  FIG. 3  shows the three-dimensional face models. Column  302  shows three-dimensional mesh facial structures. Column  304  shows facial textures and column  306  shows the facial textures applies to the three dimensional mesh facial structures shown in column  302 .  
         [0020]     In step  204  a plurality of virtual images are created from the three-dimensional face models for each of the faces to create a dataset. The virtual images may represent a variety of different poses, illumination, expressions and conditions that may vary between images. In one embodiment of the invention, at least five hundred virtual images are created for each of the faces. In another embodiment of the invention, at least six hundred virtual images are created for each of the faces.  FIG. 4  shows a plurality of virtual facial images that have different poses, illumination and expressions, in accordance with an embodiment of the invention. Virtual images  402   a - 402   d  are created from the same three-dimensional face model. And, virtual images  404   a - 404   d  are created from a different three-dimensional face model.  
         [0021]     Discriminative features are identified by selecting features from the plurality of virtual images such that the identified discriminative features are independent of the dataset in step  206 . Selecting features that are independent of the dataset allows for selecting features once using the synthetic face database, and the selected features can be generalized to recognize faces of other face databases. Moreover, training is reduced by eliminating the requirement of computing difference images. Mathematical algorithms are described below for selecting the discriminative features in accordance with various aspects of the invention.  
         [0022]     In step  208  weights may be assigned to the identified discriminative features based on classification strengths of the features. Larger weight values may be assigned to features that are stronger classifiers. The weights may be used by algorithms that create a candidate list of matches by comparing features of an unknown facial image to features of images in the dataset. Finally, in step  210  the identified discriminative features of an unknown facial image are analyzed. The unknown facial image may be an image that is not part of the dataset. The discriminative features of the unknown facial image are compared to discriminative features of the virtual images to create a candidate list of matches.  
         [0023]     Face recognition boosting algorithms combine the performance of several weak classifiers to produce accurate algorithms. Classifiers are features that are used to identify faces. During training, training samples are re-weighted according to resulting training error and weak classifiers trained later are forced to focus on the harder examples with higher weights. Boosting procedures are formulated as an additive model fitting problem 
 
 F ( x )=Σ t=1   T ƒ t ( x )  (equation 1) 
 
 where f ƒ t (x) is a weak leaner. 
 
         [0024]     For joint boosting face recognition, assume the sample points are given as {x i ,y i } i=1  where x i ∈R d  is a training sample, y i ∈{1,2,3, . . . , C} is a class label, and each individual c∈{1,2, . . . , C} has n c  samples. Instead of directly processing the raw data, we map the input samples into the feature space with projection functions φ j ∈Φ: R d →R, j=1, 2, . . . , M. An ultimate goal is to select a subset of discriminative features {φ j (x)} which effectively separate each class from all the others.  
         [0025]     Algorithms and procedures that are designed to solve face recognition problems must solve a problem that can be characterized as a multi-class classification problem, where each class contains the images of one individual. The recognition task is actually to discriminate images of one class from images of other classes. Therefore a face recognition problem can be straightforwardly formulated as multiple one-versus-the- rest binary classification problems, which can be formulated as a greedy feature selection process by fitting the following C additive models (c=1, 2, . . . , C) 
 
 F   c ( x )=Σ t=1   T ƒ j     t       c     c ( x|w   t   c ),  (equation 2) 
 
         [0026]     where each row represents one boosting model for each person based on an individual one-versus-the-rest training set. One limitation with this formulation is that it may generate an overwhelming number of features given the large number of training persons. In addition, the model may over fit to each individual, thus generalized to other datasets is limited.  
         [0027]     As faces have the same facial structure, the selected dominant features for different people may share the same properties. In one embodiment of the invention, in order to capture both the common properties and the individual characteristics using only a manageable small set of features, we propose a new joint boosting method. The method uses an assumption that we can find a set of optimal features which are the same for all individuals, i.e. we assume, 
 
j t   1 =j t   2 = . . . j t   c =j t   (equation 3) 
 
         [0028]     Based on this assumption, we developed a joint boosting feature selection algorithm for face recognition, as shown in  FIG. 5 .  
         [0029]     The selection of features in accordance with an embodiment of the invention is provided below. Suppose w(x) is the weight of a sample x. For any class c, the weighted distribution of positive samples on feature φ j (x) is defined as 
 
 h   j   c,+ ( x|w )= p (φ j ( x )| y=c )* w ( x|y=c )/ W   j   c,+ ,   (equation 4) 
 
 and that of the negative samples is 
 
 h   j   c,− ( x|w )= p (φ j ( x )| y≠c )* w ( x|c )/ W   j   c,− ,   (equation 5) 
 
 where W j   c,+  and W j   c,−  are the normalization factors, and h j   c,+ (x|w) and h j   c,− (x|w) are distributions. Here we use w to denote w(x). The weak classifier is defined as  
                 f   j   c     ⁡     (     x   |   w     )       =         f   c     ⁡     (         ϕ   j     ⁡     (   x   )       |   w     )       =       1   2     ⁢     log   ⁡     (           h   j     c   ,   +       ⁡     (     x   |   w     )       +   ɛ           h   j     c   ,   -       ⁡     (     x   |   w     )       +   ɛ       )                   (     equation   ⁢           ⁢   6     )             
 
 where c is the class label, T is the number of features to be selected, φ j     t       c    is the t th  feature selected for the c th  boosting model, and w t   c  is the assigned weight for the c th  boosting model at the t th -step. 
 
         [0030]     To evaluate the performance of feature φ j  in the c th  model at the t th  step, we define the cost function G t   c  (j) on the weak classifier ƒ j   c (x|w t   c ) as 
 
 G   t   c ( j )=∫ x∈X   G (ƒ j   c ( x|w   t   c )| y,w   t   c ) dx=∫   x∈X   g ( h   j   c,+ ( x|w   t   c ), h   j   c,− ( x|w   t   c )) dx   (equation 7) 
 
 where function g(r(x),s(x)) is the measure of the classification error of logistic classifier defined on the weighted distributions r(x) and s(x). 
 
         [0031]     Therefore, for each model c, a best feature for the t th -step is selected by 
 
 j   t   c =arg min j   G   t   c ( j )  (equation 8) 
 
         [0032]     All the feature selection procedures for the C different boosting models F c (x) can be combined into a joint procedure, which is called joint boosting. A best feature for the t th -step of joint model is selected by 
 
 j   t =arg min j Σ c=1   C   G   t   c ( j )  (equation 9) 
 
         [0033]     Finally,  FIG. 6  shows a proposed joint boosting algorithm, in accordance with an embodiment of the invention.  
         [0034]     Bayesian error may be used to measure the cost of equation 7. This cost function has low computational cost. For a binary classification problem for the classes ω 1  and  ω   2 , the Bayesian error is defined as: 
 
 R=p (error)=∫ x∈X   p (error| x ) dx=∫   x∈X min[ p ( x|ω   1 ), p ( x|   2 )] dx   (equation 10) 
 
         [0035]     Substituting the probability distributions p(w|  ω   1 ) and p(w|  ω   2 ) with weighted distribution defined in equations 3 and 4, we have 
 
 R (ƒ t,j   c ( x ))=∫ x∈X min[ h   j   c,+ ( x|w   t   c ), h   j   c− ( x|w   t   c )] dx   (equation 11) 
 
 Therefore, based on equation 11, Bayesian cost for equation 7 may be defined as 
 
 BE ( r,s )=∫ x∈X min[ r ( x ), s ( x )] dx   (equation 12) 
 
         [0036]     Evaluating equations 6 and 11 directly may not be straightforward. In one embodiment of the invention, K-bins histograms are used to discretize the distribution of the weighted distributions by partitioning the region [min(φ j (x)),max(φ j (x))] into several disjoint bins X j   1 ,X j   2 , . . . , X j   K . We define  
                 h     t   ,   j       c   ,   +       ⁡     (   k   )       =       ∑           ϕ   j     ⁡     (     x   i     )       ⋐       X   i   k     ⋀     y   i         =   c       ⁢         w     t   ,   i       /     W     t   ,   j       c   ,   +         ⁢     
     ⁢   and               (     equation   ⁢           ⁢   13     )                   h     t   ,   j       c   ,   -       ⁡     (   k   )       =       ∑         ϕ   j     ⁡     (     x   i     )       ⋐         X   i   k     ⋀     y   i       ≠   c         ⁢       w     t   ,   i       /     W     t   ,   j       c   ,   -                   (     equation   ⁢           ⁢   14     )             
 
         [0037]     where k∈{1,2, . . . , K}, W t,j   c,+  and W t,j   c,−  are the normalization factors and h t,j   c,+ (k) and h t,j   c,− (k) are the distributions on a discrete set k∈{1,2, . . . , K}.  
         [0038]     Using equation 13, h t,j   c,+ (k) becomes a loop-up-table function for h j   c,+ (x|w t   c ). Therefore, we have 
 
 h   j   c,+ ( x|w   t   c )≈ h   t,j   c,+ ( k ),  (equation 15) 
 
 where φ j (x)∈X k , and when K→∞, 
 
 h   j   c,− ( x|w   t   c )≈ h   t,j   c,− ( k )  (equation 16) 
 
         [0039]     Therefore, h t,j   c,+ (k) can be regarded as the discrete version of distribution h j   c,+ (x|w t   c ), and similarly h t,j   c,− (k) becomes the discrete version of distribution h j   c,− (x|w t   c ).  
         [0040]     Substituting equations 13 and 14 for equation 6, the LUT weak classifier can be defined as:  
                       f     t   ,   j     c     ⁡     (   k   )       =       1   2     ⁢     log   ⁡     (           h     t   ,   j       c   ,   +       ⁡     (   k   )       +   ɛ           h     t   ,   j       c   ,   -       ⁡     (   k   )       +   ɛ       )                     =       1   2     ⁢     log   (           ∑           ϕ   j     ⁡     (     x   i     )       ⋐       X   i   k     ⋀     y   i         =   c       ⁢       w     t   ,   i       /     W     t   ,   j     +         +   ɛ           ∑         ϕ   j     ⁡     (     x   i     )       ⋐         X   i   k     ⋀     y   i       ≠   c         ⁢       w     t   ,   i       /     W     t   ,   j     -         +   ɛ       )                     (     equation   ⁢           ⁢   17     )             
 
         [0041]     A discrete version of equation 11 may be defined as: 
 
 R (ƒ t,j   c ( k ))= D   BE ( h   t,j   c,+ ( k ), h   t,j   c,− ( k ))=Σ k≈1   K min( h   t,j   c,+ ( k ), h   t,j   c,− ( k ))  (equation 18) 
 
         [0042]     Similarly, based on a JSBoost algorithm that is proposed based on symmetric Jensen-Shannon divergence (SJS), which is defined as follows:  
                 SJS   ⁡     (     r   ,   s     )       =     ∫       [             r   ⁢     (   x   )     ⁢   log   ⁢       2   ⁢     r   ⁡     (   x   )             r   ⁡     (   x   )       +     s   ⁡     (   x   )             +                 s   ⁡     (   x   )       ⁢   log   ⁢       2   ⁢     s   ⁡     (   x   )             r   ⁡     (   x   )       +     s   ⁡     (   x   )                   ]     ⁢     ⅆ   x           ,           (     equation   ⁢           ⁢   19     )             
 
 where r(x) and s(x) are two distribution functions, a discrete version of symmetric Jensen-Shannon divergence for weak classifier ƒ t,j   c (x) is as follows:  
                     SJS   ⁡     (       f     t   ,   j     c     ⁡     (   k   )       )       =       D   sjs     ⁡     (         h     t   ,   j       c   ,   +       ⁡     (   k   )       ,       h     t   ,   j       c   ,   -       ⁡     (   k   )         )                   =       ∑     k   =   1     K     ⁢     {                 h     t   ,   j       c   ,   +       ⁡     (   k   )       ⁢       2   ⁢       h     t   ,   j       c   ,   +       ⁡     (   k   )               h     t   ,   j       c   ,   +       ⁡     (   k   )       +       h     t   ,   j       c   ,   -       ⁡     (   k   )             +                   h     t   ,   j       c   ,   -       ⁡     (   k   )       ⁢       2   ⁢       h     t   ,   j       c   ,   -       ⁡     (   k   )               h     t   ,   j       c   ,   +       ⁡     (   k   )       +       h     t   ,   j       c   ,   -       ⁡     (   k   )                   }                     (     equation   ⁢           ⁢   20     )             
 
         [0043]     Aspects of the invention may be used with a variety of software and hardware applications that use facial recognition. Exemplary applications include security applications, archiving photographs, access control and identification applications.  
         [0044]     The present invention has been described in terms of exemplary embodiments. Numerous other embodiments, modifications and variations within the scope and spirit of the appended claims will occur to persons of ordinary skill in the art from a review of this disclosure.