Abstract:
An improved method of watermarking picture identification documents (IDs) such as passports, driver&#39;s licenses, identification cards and the like which combines biometric information with digital watermarking to provide an improved secure picture ID document and authentication of same. A facial image—that is part of the identification document—is processed such that particular facial features are extracted from the overall facial image. The extracted features are used to generate a watermark key that is subsequently used to embed a unique watermark into the facial image or other location on the identification document.

Description:
FIELD OF THE INVENTION 
   This invention relates generally to the field of personal identification and in particular to a picture identification apparatus and method which employs digital watermarking of facial features. 
   BACKGROUND OF THE INVENTION 
   The threat of forgery of identity documents is growing at an astounding rate. In the past, only skilled professionals with sophisticated equipment were capable of counterfeiting passports, driver&#39;s licenses, identification cards and financial instruments. Today however, the counterfeiting threat for this wide array identity documents has moved from the professional counterfeiter to the amateur. Sophisticated counterfeiting tools such as scanners, card printers, and image editing software are readily available, and identity document attacks by both criminal and casual counterfeiters are a growing threat. 
   For government-issued citizen identity documents, this counterfeiting and forgery threatens personal, corporate and national security. Reliably confirming the authenticity of an identity document is therefore of critical importance. 
   In recognition of this, a number of states have adopted digital watermarks—covert digital security features—that transform multiple, previously passive elements of driver licenses, such as photo and artwork, into machine-readable elements. (See, e.g., Digimarc Corporation,  Are Your IDs Secure Enough? , February 2005, www.digimarc.com/docs) 
   A digital watermark enhances the security of identity documents by embedding virtually imperceptible digital information within each document. It can, for example, confirm the date of birth on a driver&#39;s license; identify an altered passport; or verify the authenticity of a security badge. When applied as a covert layer of security to identity documents such as driver licenses, digital watermarks enable machine-readable authentication of identification documents. 
   SUMMARY OF THE INVENTION 
   In accordance with the principles of the present invention—an improved method of watermarking picture identification documents (IDs) such as passports, driver&#39;s licenses, identification cards and the like is presented. Advantageously, the present invention combines biometric information with digital watermarking to provide an improved secure picture ID document and authentication of same. 
   According to the principles of the present invention, a facial image—that is part of the identification document—is processed such that particular facial features are extracted from the overall facial image. The extracted features are used to generate a watermark key that is subsequently used to embed a unique watermark into the facial image or other location on the identification document. 
   Advantageously, and in sharp contrast to the prior art, the present invention generates and embeds a watermark that is specific to a particular facial image. As a result, one embodiment of the present invention provides a mechanism by which the identification document is self-authenticating. 
   According to an aspect of the invention, Eigen vectors—generated from original facial images on the identification document—are used as a watermark key for the particular identification document containing the facial image. The watermark key so generated into a wavelet transformed facial image through the use of a joint wavelet compression and authentication watermark. 
   As a result—in a preferred embodiment, the present invention provides solutions to two major challenges to authentication watermarks namely, extractable, short, invariant and robust information that replaces fragile hash functions of the prior art and the ability to embed information that survives quantization-based lossy compression. 
   Additionally, watermarks applied according one embodiment of the present invention may be advantageously embedded at the same time the identification document is created or electronically distributed. 
   Lastly, authentication watermarks applied according to one embodiment of the present invention not only serve to authenticate the identity document and verify the face image(s), but also serve as recovery bits for recovering face values in corrupted identification documents. 
   These and other features and advantages of the present invention will become apparent with reference to the attached drawing and detailed description. 

   
     BRIEF DESCRIPTION OF THE DRAWING 
     A more complete understanding of the present invention may be realized by reference to the accompanying drawing in which: 
       FIG. 1  is a flowchart showing the steps associated with applying a digital watermark to an ID document according to a preferred embodiment of the present invention; 
       FIG. 2  shows facial feature extraction using Eigenfaces according to an embodiment of the present invention; 
       FIG. 3  shows the steps of embedding a watermark into an ID document according to an embodiment of the present invention; 
       FIG. 4  shows the watermark engraving structure employed in an embodiment of the present invention; 
       FIG. 5  shows the steps of detecting a watermark and face ID authentication according to an embodiment of the present invention; and 
       FIG. 6  shows the steps of authentication verification and recovery according to an embodiment of the present invention. 
   

   DETAILED DESCRIPTION 
     FIG. 1  is a flowchart showing particular steps associated with a preferred embodiment of the present invention of embedding a watermark into an identification document. With reference to that  FIG. 1 , facial features are first extracted from a facial image from, for example, an image contained on a picture identification card (Block  110 ). The extracted features are subsequently quantized (Block  120 ), and from these quantized features a watermark bitstream is generated (Block  130 ). Finally, the generated bitstream is “etched”, into a low frequency band of a wavelet image representation. 
   As can be appreciated by those skilled in the art, the particular watermark generated is dependent upon the particular facial features exhibited by the facial image. More specifically, the extracted facial features are used to generate watermark keys unique to the extracted features. As a result, the facial image that is part of a picture identification card advantageously self-authenticates a watermark imposed on the identification card. In this manner, the present invention provides an authentication watermark having a secret key that is unique and invariant for each particular facial image. 
     FIG. 2  shows the relationship between training facial images that are transformed into Eigenfaces as a result of Principle Component Analysis (PCA). Eigenfaces is a well-known principal component analysis based racial recognition technique the details of which were described in a paper authored by M. Turk and A. Pentland entitled “Face Recognition Using Eigenfaces”, which appeared in  Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition  ( CVPR ), at pages 586-591 in June 1991. 
   Although the mathematical underpinnings of Eigenfaces are complex, the entire algorithm is relatively simple and advantageously has a structure which is amenable to streaming. In particular, training images are represented as a set of flattened vectors and assembled together into a single matrix. The Eigen vectors of the matrix are then extracted and stored in a database. 
   The training face images are projected onto a feature space, appropriately called face space, defined by the Eigen vectors. This captures the variation between the set of faces without emphasis on any one facial region like the eyes or nose. The projected face space representation of each training image is also saved to a database. 
   To identify a face, the test image is projected to face space using the saved Eigen vectors. The projected test image is then compared against each saved projected training image to determine similarity. The identity of the person depicted in the test image is assumed to be the same as the person depicted in the training image that is determined to be most similar. 
   For our purposes, the procedure that defines the face space is represented by:
         FUNCTION 1: Create_Eigen_Matrix(ImageList IL, int N, int M)
 
where ImageList IL is a set of N training images, each one having W×H (W: width, H: height) pixels and M is the number of Eigen vectors that need to be generated. The particular procedure proceeds as follows.
   [1] Flatten each image into a WH element by concatenating all of the rows. Let ImageMatrix be the N×WH matrix containing all of the flattened images.   [2] Sum all of the rows of ImageMatrix and divide by N to produce an average flattened image. This WH element vector is represented by ψ.   [3] Subtract the average image ψ from the flattened image in ImageMatrix. Let the new N×WH matrix be represented by φ.   [4] Compute dot products of all possible image pairs. Let L be the new N×N matrix where L[i][j]=dot product of φ [i] and φ [j].   [5] Compute the N Eigen values and corresponding Eigen vectors of L. Pick M Eigen vectors corresponding to the highest Eigen values. Each Eigen vector is N elements long.   [6] Perform a matrix multiplication of each of the selected M Eigen vectors against φ and save the resulting set of 1×WH-sized matrices as a combined M×WH element EigenMatrix in a database. Also, save the average image ψ as well.       

   We now turn to the face space projection function:
         FUNCTION 2: Project_to_FaceSPACE(ImageI).
 
Where Image I is W×H pixels in size.
   [1] We let img be the flattened WH element form of Image.   [2] Load the average image ψ and the EigenMatrix from the database.   [3] Subtract the average image ψ from img to create a new image, img′.   [4] Take the dot product of img′ against each row of EigenMatrix thereby obtaining an M element vector img″.   [5] Let:       

   
     
       
         
           norm 
           = 
           
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   M 
                 
                 ⁢ 
                 
                   
                     
                       img 
                       k 
                     
                     ⁡ 
                     
                       [ 
                       i 
                       ] 
                     
                   
                   × 
                   
                     
                       img 
                       ″ 
                     
                     ⁡ 
                     
                       [ 
                       i 
                       ] 
                     
                   
                 
               
             
             . 
           
         
       
     
       
       
         
           [6] Divide each element of img″ by norm. This is the face space representation of Image 
           [7] Perform a matrix multiplication of each of the selected M Eigen vectors against φ and save the resulting set of 1×WH-sized matrices as a combined M×WH element EigenMatrix in a database. Also, save the average image ψ as well. 
         
       
     
  
   We now note that learning is a matter of projecting all known faces to the face space and saving the projected representations of each person. Accordingly:
         FUNCTION 3: Generate_Eigen_Faces(ImageList IL, int N, int M)
 
Where ImageList IL is a set of N training images where each image is W×H pixels. A person&#39;s name is attached to each image and M is the number of Eigen vectors needed. Consequently, our procedure proceeds as follows:
   [1] Call Create_Eigen_Matrix (ImageList IL, int N, int M)   [2] For each image in ImageList IL, call Project_to_FaceSPACE(Image I), and save the resulting faces in a database.       

   Facial identification then, is a simple matter of projecting the test image to face space and computing a similarity score. Accordingly:
         FUNCTION 4: Generate_Eigen_Vector(Image I n )
 
Where Image I n  is W×H pixels in size. Our Generate_Eigen_Vector (Image I n ) procedure is to find the eigen vectors of the Image I n :
   [1] Load the saved, known projected faces from the database;   [2] proj=Project_to_FaceSPACE(Image I n );   [3] Take the dot product of proj against each known projected face. The resulting dot product is called the “score”.   [4] The known projected face that receives the highest score, is considered the identity of the test image.       

   A thorough discussion of the particular algorithms employed may be found in a paper entitled “The CSU Face Identification Evaluation System: Its Purpose, Features, and Structure,” which appeared in  International Conference on Vision Systems , pp. 304-311, in April, 2003. 
   Once the Eigenfaces E[e 1 , e 2 , . . . , e n ] are established, we may always decompose a face into a projection vector over the Eigenspace v=           I,e         , and V=[v 1 , v 2 , . . . , v n ] is the Eigenvector of the face image over the Eigenfaces.
   Advantageously, and as can be appreciated by those skilled the art, Eigenfaces are basic elements of original faces and the generated Eigen vectors have invariant properties associated with each face. Consequently, when the generated Eigen vectors are used as keys for watermarks applied to an identification document having the original face, its authenticity may be verified from the watermark itself. 
   As noted initially with reference to  FIG. 1 , the present invention performs a facial feature extraction as described above ( FIG. 1-Block   110 ). The facial features so extracted are quantized (Block  120 ) and a watermark bitstream is generated (Block  130 ). Finally, to ensure robustness, the bitstream is etched into a low frequency band of the wavelet image (Block  140 ). 
   In one implementation of the present invention, uniform quantization is satisfactorily performed using only 8-bits. Those skilled in the art will readily appreciate that it may be improved by optimizing quantization while minimizing quantization error. Normally, increasing information rate(s) (payload) for watermarking will result in more watermark bits being embedded, therefore producing a more robust watermark. 
   As noted, to ensure robustness, the watermark bit stream is etched into the low frequency band of the wavelet image. The particular method employed in a current implementation is described in a paper entitled “A Blind Content Based Digital Image Signature”, authored by G. R. Arce and L. Xie, which appeared in  Proceedings of the  2 nd    Annual Fedlab Symposium on ATIRP , February, 1998. 
   With simultaneous reference now to  FIG. 3  and  FIG. 4 , it can be seen where in the process and how the watermark bit sequence is etched into the low-frequency band of the wavelet image representation  340 . A sliding and non-overlapping 3×1 running window  350  is applied through the entire low frequency band of the wavelet decomposed image  340 . At each location, a watermark bit is etched. As shown, elements within the window  350  are denoted as b 1 , b 2 , b 3 , which are the coefficients&#39; value at locations with coordinates (i−1,j),(i,j),(i+1,j). The corresponding sorted, rank ordered coefficients are denoted as b (1) ≦b (2) ≦b (3) . 
   A nonlinear transformation is performed  360  thereby changing the median of these coefficients while keeping the remaining coefficients the same. The modified median is denoted by b′ (2) , which is obtained by the transformation:
 
 b′   (2)   =f (α, b   (1)   ,b   (3)   ,x );
 
where x is the watermark bit to be etched.
 
   The rank-order transformation is advantageously able to engrave signature data into a large number of images while preserving their image quality. Basically, the transformation changes the median of a local area to a value set by its neighbors. 
   Given the coefficients b 1 , b 2 , b 3  and the corresponding order statistics b (1) , b (2) , b (3) , the following is defined: 
             S   α     =     α   ⁢              b     (   1   )            +          b     (   3   )              2             
where α is a tuning parameter with its default value of 0.05. It should be noted that previously it was defined as:
 
             S   α     =     α   ⁢           ⁢         b     (   1   )       +     b     (   3   )         2             
which produces a substantially lower bit rate.
 
   Next, the range of the coefficients (b (1) , b (3) ) is partitioned into M intervals, each interval having a length S α . The boundary of the partitions are denoted as l 0 , l 1 , . . . l M , with l 0 =b (1) , l 1 ,=b (1) +S α , . . . , l M =b (3) , with M being the smallest integer for which MS α &gt;b (3) −b (1) . A region is defined in the interval [l k−1 ,l k ] as R k , then b (2)  is transformed into b′ (2)  as: 
             b     (   2   )     ′     =     {             l   k           case   ⁢           ⁢   A               l     k   -   1             case   ⁢           ⁢   B           ,             
where:
 case A           {k is odd and x=1, or k is even and x=0}; and case B         {k is even and x=1, or k is odd and x=0}. 
Where x is the bit of the watermark being inserted in the location in the window.

   Watermark extraction—which takes place at a receiver or detector—is shown in  FIG. 5  and it comprises an inverted etching process. A 3×1 window  540  is shifted through a received, wavelet transformed image and a sequence with elements B (1) , B (2) , and B (3)  is obtained. 
   A watermark bit associated with the window is extracted as: 
           x   =     arg   ⁢           ⁢       min     x   ∈     (     0   ,   1     )         ⁢              B     (   2   )       -     f   ⁡     (     α   ,     b     (   1   )       ,     b     (   3   )       ,   x     )              .               
where x is the possible value of the watermark sample (within 0,1) and B (1) =b (1) , B (3) =b (3) .
 
   Advantageously, there is no need for the original image to retrieve the watermark as the invariance of rank ordering is utilized to “memorize” a hidden information bit. Shifting the decoding window throughout the entire watermarked image, the entire embedded watermark sequence V′ is obtained. 
   The received image  520  is used to determine the Eigen vector features V of the facial image on the identification document  510  as described previously. Authentication verification is accomplished by comparing the Eigen vector features V with the message bits carried by the watermark  560 . If they fall within a pre-determined threshold, then the document is authentic  570 , else it is declared non-authentic  580 . Advantageously, the threshold may be chosen to maximize the detection accuracy of this authentication process. 
   As can now be readily appreciated by those skilled in the art, a preferred method of the present invention provides a mechanism by which an identification document may be automatically verified and authenticated. Such a process is shown schematically in  FIG. 6 . If an original, authentic identification document  610  is watermarked according to my inventive method, a counterfeit of that document  620  is readily detected. More specifically, if any watermark from the counterfeit is not matched with the intrinsic face image. Eigen vector feature(s), then the counterfeit is detected. Alternatively, the detected watermark may be used to restore the original facial image. 
   While the present invention has been discussed and described using some specific examples, those skilled in the art will recognize that the teachings are not so limited. More specifically, it is understood that the present invention may be used with a variety of watermarks and or embedding methods in virtually any application requiring verifiable authentication and/or correction. Accordingly, it is understood that the present invention should be only limited by the scope of the claims attached hereto.