Abstract:
A method for removing red eyes includes (1) identifying potential red eye pixels in a low resolution image (hereafter “LR red eye pixels”), (2) grouping contiguous LR red eye pixels into red eye regions (herafter “LR red eye regions”); determining working areas around the LR red eye regions (hereafter “LR working areas”), (3) determining classifiers from the LR working areas, (4) retrieving working areas from a high resolution image that correspond to the LR working areas (hereafter “HR working areas”), (5) applying the classifiers to the HR working areas to identify potential red eye pixels (hereafter “HR red eye pixels”), (6) grouping contiguous HR red eye pixels into red eye regions (hereafter “HR red eye regions”), (7) determining some of the HR red eye regions as the red eyes, and (8) replacing the HR red eye pixels in the red eyes with black pixels.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application is related to U.S. application Ser. No. 10/826,108, attorney docket no. ARC-P135 US, entitled “AUTOMATIC RED EYE REMOVAL,” filed Apr. 16, 2004, which is commonly assigned and incorporated by reference in its entirety. 
     
    
     FIELD OF INVENTION  
       [0002]     This invention relates to a method for red eye removal in photographs and images.  
       DESCRIPTION OF RELATED ART  
       [0003]     The pupil is an opening that lets light into the eye. Since most of the light entering the eye does not escape, the pupil appears black. In dim light, the pupil expands to allow more light to enter the eye. In bright light, the pupil contracts to allow less light to enter the eye.  
         [0004]     “Red eye” is a phenomenon where a person&#39;s pupils appear red in a photograph taken with a flash. Red eye comes from light reflecting off of the blood vessels in the retinas (on the back interior of the eyeballs).  
         [0005]     Some cameras have a “red eye reduction” feature. In these cameras, the flash goes off twice—once right before the picture is taken, and then again to actually take the picture. The first flash causes people&#39;s pupils to contract, thereby reducing red eye significantly.  
         [0006]     Some photography software have a “red eye removal” feature. These software require the user to identify the red eye, usually by dragging a rectangular box around the red eye with a mouse, and then remove red eye from the specified area. Others software, such as those available from Pixology of Guildford, England, and FotoNation of San Francisco, Calif., require little or no user intervention and the software identifies the red eye automatically.  
         [0007]     In addition, there are literatures that describe methods for red eye removal. Of particular interest is U.S. Patent Application Publication 2002/0176623, filed Mar. 29, 2002 (“Steinberg”). Steinberg describes a 3-step process: (1) search candidate areas by color constraints; (2) eliminate candidates with shape and other criteria; and (3) output the results for user interactive verification of the red eye candidates. However, this process has been widely used and is processing common sense.  
         [0008]     For example, in an article by de la Escalera et al., a process for detecting road traffic signs is disclosed. de la Escalera et al., “Road Traffic Sign Detection and Classification,” IEEE Trans. on Industrial Electronics, Vol. 44, No. 6, December 1997. de la Escalera et al. discloses two steps: (1) localize the sign in the image depending on the color and the form; and (2) recognize the sign through a neural network.  
         [0009]     In another example, in an article by Yang et al., a process for face detection is disclosed. “Detecting Faces in Images; A Survey,” Yang et al., IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 24, No. 1, January 2002. Yang et al. states, “Most of [software] utilize global features such as skin color, size, and shape to find face candidates, and then verify these candidates using local, detailed features such as eye brows, nose, and hair. A typical approach begins with the detection of skin-like regions. Next, skin-like pixels are grouped together using connected component analysis or clustering algorithms. If the shape of a connected region has an elliptic or oval shape, it becomes a face candidate. Finally, local features are used for verification.” Id. at p. 40. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]      FIG. 1  illustrates an image with red eye in one embodiment of the invention.  
         [0011]      FIG. 2  is a flowchart of a method for red eye removal in one embodiment of the invention.  
         [0012]      FIGS. 3, 4 , and  5  illustrate how a red eye region is determined to be a substantially round pupil with red eye in one embodiment of the invention.  
         [0013]      FIG. 6  illustrates how a red eye region is determined to be too close to another red eye region in one embodiment of the invention.  
         [0014]      FIGS. 7 and 8  illustrate how a red eye region is determined to be proximate to a facial region in one embodiment of the invention.  
         [0015]      FIGS. 9 and 10  illustrate how a red eye region is determined to be proximate to a white of an eye in one embodiment of the invention.  
         [0016]      FIG. 11  is a flowchart of a method for red eye removal in another embodiment of the invention.  
         [0017]      FIGS. 12 and 13  illustrate a low resolution image from which working areas around red eye regions are identified in one embodiment of the invention.  
         [0018]      FIGS. 14 and 15  illustrate histograms used to determine probabilities for Bayesian classifiers in one embodiment of the invention. 
     
    
       [0019]     Use of the same reference numbers in different figures indicates similar or identical elements.  
       SUMMARY  
       [0020]     In one embodiment of the invention, a method for removing red eyes includes (1) identifying potential red eye pixels in a low resolution image generated from a high resolution image (hereafter “LR red eye pixels”), (2) grouping contiguous LR red eye pixels into red eye regions (herafter “LR red eye regions”); determining working areas around the LR red eye regions (hereafter “LR working areas”), (3) determining classifiers from the LR working areas, (4) retrieving working areas from the high resolution image that correspond to the LR working areas (hereafter “HR working areas”), (5) applying the classifiers to the HR working areas to identify potential red eye pixels (hereafter “HR red eye pixels”), (6) grouping contiguous HR red eye pixels into red eye regions (hereafter “HR red eye regions”), (7) determining some of the HR red eye regions as the red eyes, and (8) replacing the HR red eye pixels in the red eyes with black pixels. By doing some of the processing involved in red eye removal on the low resolution image, the number of computational steps is reduced and the required memory used in these computational steps is also reduced.  
       DETAILED DESCRIPTION  
       [0021]      FIG. 1  illustrates an image  10  of a person  12  having pupils  14 , eyes  16 , scleras  18 , and face  20  in one embodiment of the invention. In a phenomenon called “red eye,” pupils  14  appear red when light reflects off of the blood vessels in back interior of the eyeballs. It has been experimentally determined that a red eye typically consists of pixels that are purple-red or orange-red.  
         [0022]      FIG. 2  is a flowchart of a method  100  for automatically removing red eye from image  10  in one embodiment of the invention. Method  100  does not require the user to designate an area from which the red eye is removed. Method  100  involves low computational complexity and may be implemented in software executed by a computer or firmware embedded into a digital camera, printer, scanner, or mobile phone.  
         [0023]     In step  102 , the software determines a weighted purple-red value of each pixel in image  10 . The weighted purple-red value represents the likelihood that a pixel is a purple-red pixel that forms part of a red eye. In one embodiment for the rgb (red, green, and blue) color space, the weighted purple-red value of a pixel is determined from its red, green, and blue color values, and its luminance as follows:  
                 f   1     =           c   1     (   1   )       ⁢   r     +       c   2     (   1   )       ⁢   g     +       c   3     (   1   )       ⁢   b       Y       ,           (   1   )             
 
 where ƒ 1  is the weighted purple-red value, r is the red color value, g is the green color value, b is the blue color value, c 1   (1)  is a weight given to the red color value, c 2   (1)  is a weight given to the green color value, c 3   (1)  is a weight given to the blue color value, and Y is the luminance calculated as Y=a 1 r+a 2 g+a 3 b. Note that the weighted red value is independent of luminance change. In one embodiment, c 1   (1)  is 0.5, c 2   (1)  is 0.5, c 3   (1)  is −1, and 
 
 Y=0.299r+0.587g+0.114b. In other words, equation (1) can be rewritten as:  
               f   1     =         r   +   b   -     2   ⁢   g         2   ⁢   Y       .             (   2   )             
 
         [0024]     In one embodiment for the YCrCb (luminance, red chrominance, and blue chrominance) color space, the weighted purple-red value of a pixel is determined as follows:  
                 f   1     =         1.41514   ⁢     (     Cr   -   128     )       +     1.23014   ⁢     (     Cb   -   128     )         Y       ,           (   3   )             
 
 where Cr is the red chrominance, Cb is the blue chrominance, and Y is the luminance. 
 
         [0025]     In step  104 , the software selects the pixels in image  10  that have weight purple-red values greater than a threshold as red eye pixels. In one embodiment, this threshold is 0.5.  
         [0026]     In step  106 , the software determines a weighted orange-red value of each pixel in image  10 . The weighted orange-red value represents the likelihood that a pixel is an orange-red pixel that forms part of a red eye. In one embodiment, the weighted orange-red value for a pixel is determined from its red, green, and blue color values as follows:  
                 f   2     =           c   1     (   2   )       ⁢   r     +       c   2     (   2   )       ⁢   g     +       c   3     (   2   )       ⁢   b       Y       ,           (   4   )             
 
 where ƒ 2  is the weighted orange-red value, c 1   (2)  is a weight given to the red color value, c 2   (2)  is a weight given to the green color value, and c 3   (2)  is a weight given to the blue color value. As noted above, the weighted red value is independent of luminance change. In one embodiment, c 1   (2)  is 0.6667, c 2   (2)  is 0.3333, c 3   (2)  is −1.0. In other words, equation (4) can be rewritten as:  
               f   2     =           2   ⁢   r     +   g   -     3   ⁢   b         3   ⁢   Y       .             (   5   )             
 
         [0027]     In one embodiment for the YCrCb color space, the weighted orange-red value of a pixel is determined as follows:  
               f   2     =           0.69662   ⁢     (     Cr   -   128     )       -     1.88671   ⁢     (     Cb   -   128     )         Y     .             (   6   )             
 
         [0028]     In step  108 , the software selects the pixels in image  10  that have weighted orange-red values greater than another threshold as red eye pixels. In one embodiment, this threshold is 0.5.  
         [0029]     In step  110 , the software groups contiguous red eye pixels into red eye regions. Red eye pixels hereafter refer to the purple-red and orange-red pixels selected in steps  104  and  108 . A red eye region can contain purple-red pixels, orange-red pixels, or a combination thereof.  FIG. 3  illustrates a group of red eye pixels  202  (only a few are labeled) that form a red eye region  204 . Although not illustrated, it is understood that other pixels surround red eye pixels  202 .  
         [0030]     In step  112 , the software determines if each red eye region is a substantially round pupil. In step  114 , the software rejects the red eye pixels in each red eye region that is not a substantially round pupil. Steps  112  and  114  are illustrated in reference to red eye region  204  in  FIGS. 3 and 4  but in actuality are repeated for each red eye region.  
         [0031]     First, the software determines the geometric center  206  of red eye region  204 . The software then determines the distance D max  from geometric center  206  to the farthest red eye pixel  202 F. Distance D max  is used to set a range of radii of circles where the weighted red values of corresponding pixels located on two adjacent circles are compared. This is illustrated in reference to  FIG. 4 .  
         [0032]     The software first determines the sum of the weighted red values of the pixels located at a first circle having a radius R i  as follows:  
                 S   ⁡     (     R   i     )       =       ∑     0   ≤   θ   &lt;   360       ⁢           ⁢     Max   ⁡     (         f   1     ⁡     (       R   i     ,   θ     )       ,       f   2     ⁡     (       R   i     ,   θ     )         )           ,           (   7   )             
 
 where S(R i ) is the sum of the first circle, Max(ƒ1,ƒ2) is a function that outputs the greater of a weighted purple-red value ƒ 1  and a weighted orange-red value ƒ 2 , and R i  and θ are the polar coordinates of a pixel. 
 
         [0033]     The software then determines the sum of the weight red values of the pixels located at an adjacent second circle having a radius R i+1 .  
                 S   ⁡     (     R     i   +   1       )       =       ∑     0   ≤   θ   &lt;   360       ⁢           ⁢     Max   ⁡     (         f   1     ⁡     (       R     i   +   1       ,   θ     )       ,       f   2     ⁡     (       R     i   +   1       ,   θ     )         )           ,           (   8   )             
 
 where S(R i+1 ) is the sum of the second adjacent circle. In one embodiment, the radius R i+1  is radius R i  incremented by 1 pixel, and angles θ consists 0 to 360° increased at 4° increments (e.g., 0, 4, 8 . . . 356). 
 
         [0034]     The software then determines the difference between the two sums: S(R i )−S(R i+1 ). If the absolute value of the difference is small, then there has not been a change in the red color between the pixels on the adjacent circles, which indicates that the image has not transitioned from a pupil having red eye to the eye (e.g., from pupil  14  to eye  16 ). If the difference is positive, then there has been a decrease in the red color between the pixels on the adjacent circles, which may indicate that the image has transitioned from a pupil having red eye to the eye.  
         [0035]     In one embodiment, this process is repeated for radii ranging from 0.5*D max  to 1.5*D max  where the radius is incremented at 1 pixel between adjacent circles. After the process is completed for these radii, the software selects the radius of the circle that generates the largest difference with its adjacent circle as the radius of a pupil (hereafter “R pupil ”) having red eye region  204 .  
         [0036]     Referring to  FIG. 5 , the software then determines a first ratio between (1) the number of red eye pixels located within a circle  222  having radius of R pupil  and (2) the area of circle  222  in pixels as follows:  
                 R   1     =       N     R   pupil         A     R   pupil           ,           (   9   )             
 
 where R 1  is the first ratio, N R     pupil    is the number of red eye pixels within a circle having radius R pupil , and A R     pupil    is the area of the circle in the number of pixels. 
 
         [0037]     The software also determines a second ratio between (1) the number of red eye pixels located within a ring  224  having an inner radius of R pupil  and an outer radius of D max  and (2) the area of ring  224  in pixels as follows:  
                 R   2     =       N       R   pupil     /     D   max           A       R   pupil     /     D   max             ,           (   10   )             
 
 where R 2  is the second ratio, N R     pupil    is the number of red eye pixels within a ring having an inner radius R pupil  and an outer radius D max , and A R     pupil     /D     max    is the area of the circle in the number of pixels. 
 
         [0038]     The software then determines a difference between the first ratio and the second ratio: R 1 -R 2 . A large difference indicates that red eye region  204  is probably a pupil with red eye. If the difference is less than a threshold, the software then rejects the red eye pixels in red eye region  204  as candidates for red eye removal. In one embodiment, the threshold is 30% (i.e., 0.3).  
         [0039]     In step  116 , the software determines if each remaining red eye region is too close to another red eye region. In step  118 , the software rejects red eye pixels in each red eye region that is too close to another red eye region. Steps  116  and  118  are illustrated in reference to red eye regions  204  and  242  in  FIG. 6  but in actuality are repeated for each red eye region.  
         [0040]     The software determines a distance D pupil  between the geometric centers of red eye regions  204  and  242 . The software then determines if distance D pupil  is within a range that makes red eye regions  204  and  242  too close. In one embodiment, red eye regions are too close if they are within 10*R pupil  to 14*R pupil  of each other. The software thus rejects the red eye pixels in red eye regions  204  and  242  as candidates for red eye removal if they are too close to each other.  
         [0041]     In step  120 , the software determines if each remaining red eye region is proximate to a facial region (e.g., face  20  in  FIG. 1 ). In step  122 , the software rejects the red eye pixels in each red eye region that is not proximate to a facial region. Steps  120  and  122  are illustrated in reference to red eye region  204  in  FIGS. 7 and 8  but in actuality are repeated for each red eye region.  
         [0042]     The software first generates a histogram  262  of the pixels located in a ring  264  about geometric center  206 . The function of histogram  262  is simply the number of pixels that has a particular color (e.g., a particular combination of Y,Cr,Cb color values). In one embodiment, ring  262  has an inner radius of 4*R pupil  and an outer radius of 9*R pupil . The software then selects the most common color  266  in histogram  262  and compares it to a range of threshold skin color values. If color  266  is within the range of threshold skin color values, then red eye region  204  is probably a pupil with red eye that is proximate to a facial region. In one embodiment, the threshold skin color values are expressed in HSV (hue, saturation, value) color space as—80&lt;H&lt;50, 5&lt;S&lt;80, and 20&lt;V&lt;80. Thus, the software first converts the most common color  266  into HSV color space and then compares it with the threshold skin color values. If color  266  is not within the range of threshold skin color values, the software rejects the pixels in red eye region  204  as candidates for red eye removal. In order to remove the luminance change, the luminance (Y) of the image within the circle having radius 9*R pupil  will be normalized to [0,255] before the software generates histogram  262  and compare color  266  to the range of threshold skin color values. This is because without the normalization, any luminance change will introduce a color cast (i.e., unwanted color effect) into the HSV color space.  
         [0043]     In step  124 , the software determines if each remaining red eye region is proximate to a sclera of an eye (e.g., sclera  18  in  FIG. 1 ). In step  126 , the software rejects the red eye pixels in each red eye region that is not proximate to a sclera of an eye. Steps  124  and  126  are illustrated in reference to red eye region  204  in  FIGS. 9 and 10  but in actuality are repeated for each red eye region.  
         [0044]     The software generates a luminance histogram  282  of the pixels located in a ring  284  about geometric center  206 . In one embodiment, ring  284  has an inner radius of 2*R pupil  and an outer radius of 5*R pupil  . From histogram  282 , the software determines a ratio between (1) the number of pixels having the brightest color  288  in ring  284  and (2) the number of red eye pixels in a circle  286  having a radius of R pupil  as follows:  
                 R   sclera     =       N   brightest       N     R   pupil           ,           (   11   )             
 
 where R sclera  is the ratio and N brightest  is the number of pixels having the brightest color in ring  284 . 
 
         [0045]     If the ratio is greater than a sclera threshold, then red eye region  204  is probably a pupil with red eye proximate to the sclera. If the ratio is less than the threshold, then the software rejects the red eye pixels in red eye region  204 . In one embodiment, the sclera threshold is 82% (e.g., 0.82).  
         [0046]     In step  128 , the software replaces the remaining red eye pixels with black pixels to remove the red eye.  
         [0047]      FIG. 11  is a flowchart of a method  1100  for automatically removing red eye from image  10  in one embodiment of the invention. Method  1100  may be implemented in software executed by a computer or firmware embedded into a digital camera, printer, scanner, or mobile phone. Method  1100  is well suited for a portable device because it uses less computational steps and less random access memory (RAM) than method  100  described above.  
         [0048]     In step  1102 , the software generates a low resolution image  10 A ( FIG. 12 ) from image  10 . Alternatively the software receives low resolution image  10 A generated by another component. For example, a digital camera may have built-in hardware or software that generates a preview image from the high resolution image captured by the camera.  
         [0049]     In step  1104 , the software performs steps  102  to  110 ,  116 , and  118  described above to low resolution image  10 A instead of image  10  at full resolution. This saves the computational steps that would otherwise be performed for all the pixels in image  10 . Furthermore, this saves the RAM that would otherwise be required for performing the computational steps for all the pixels in image  10 .  
         [0050]     Specifically, in steps  102  and  104 , the software selects pixels in low resolution image  10 A that have weighted purple-red values greater than a threshold as red eye pixels (also referred to as “LR red eye pixels”). In steps  106  and  108 , the software selects pixels in image  10 A that have weighted orange-red values greater than another threshold as red eye pixels (also referred to as “LR red eye pixels”). The thresholds for steps  104  and  108  are selected so they are less discriminatory in order to capture all red eye pixels and some non-red eye pixels. At step  110 , the software groups contiguous red eye pixels in image  10 A into red eye regions (also referred to as “LR red eye regions”).  
         [0051]     In step  1106 , the software determines working areas around the red eye regions in low resolution image  10 A (also referred to as “LR working area”). Each LR working area is centered at the corresponding red eye region. Each LR working area has a width of twice the maximum width (W max ) of the corresponding red eye region, and a height of twice the maximum height (H max ) of the corresponding red eye region. For simplicity, only one LR working area  1202  and one red eye region  1204  has been labeled in  FIG. 12 .  
         [0052]     The software then uses the selected red eye pixels and the non-red eye pixels in each LR working area to train a Bayesian classifier for that LR working area. The Bayesian classifier is later used to determine red eye pixels in a corresponding working area in image  10  (also referred to as “HR working area”). The Bayesian classifier for a LR working area is defined as follows: 
 
 P ( x, y )= P ( x|y ) P ( y )= P ( y|x ) P ( x ),  (12)
 
 wherein P(x) is the probability of a pixel taking a weighted red value of x, P(y) is the probability of a pixel being a red eye pixel (i.e., P(y)=1) or a non-red eye pixel (i.e., P(y)=0), P(x,y) is the joint probability that a pixel taking a weighted red value of x and a red-eye pixel value of y, and P(x|y) is the conditional probability that a pixel taking a weighted red value of x for a given a red-eye pixel value of y. In one embodiment, the weighted red value of a pixel is the greater of the purple-red value and the orange-red value of that pixel. 
 
         [0053]     From Equation 12, the probability for a pixel taking a weighted red value of x when that pixel is a red eye pixel can be calculated as follows: 
 
 P ( x,y= 1)= P ( x|y= 1) P ( y= 1)= P ( y= 1 |x ) P ( x )  (13)
 
 which can be rewritten as:  
               P   ⁡     (     y   =     1   ❘   x       )       =           P   ⁡     (       x   ❘   y     =   1     )       ⁢     P   ⁡     (     y   =   1     )           P   ⁡     (   x   )         .             (   14   )             
 
         [0054]     From Equation 12, the probability for a pixel taking a weighted red value of x when that pixel is a non-red eye pixel x can be calculated as follows: 
 
 P ( x,y= 0)= P ( x|y= 0) P (0)= P ( y= 0 |x ) P ( x ),  (15)
 
 which can be rewritten as:  
               P   ⁡     (     y   =     0   ❘   x       )       =           P   ⁡     (       x   ❘   y     =   0     )       ⁢     P   ⁡     (     y   =   0     )           P   ⁡     (   x   )         .             (   16   )             
 
         [0055]     In one embodiment of the invention, a pixel is assumed to be a red eye pixel when P(y=1|x)&gt;P(y=0|x). This can be rewritten from Equations 14 and 16 as follows:  
                     P   ⁡     (       x   ❘   y     =   1     )       ⁢     P   ⁡     (     y   =   1     )           P   ⁡     (   x   )         &gt;         P   ⁡     (       x   ❘   y     =   0     )       ⁢     P   ⁡     (     y   =   0     )           P   ⁡     (   x   )           ,           (   17   )             
 
 which can be rewritten as: 
 
 P ( x|y= 1) P ( y= 1)&gt; P ( x|y= 0) P ( y= 0).  (18)
 
         [0056]     Thus, the software trains the Bayesian classifiers for the LR working areas by determining probabilities P(x|y=1), P(y=1), P(x|y=0), and P(y=0) for each LR working area.  
         [0057]     Probability P(x|y=1) can be determined from a histogram of the red eye pixels in the LR working area as shown in  FIG. 14 . For a given weighted red value x, P(x|y=1) is equal to the number of pixels in the bin for the weighted red value x divided by the total number of red eye pixels in the LR working area. Similarly, probability P(x|y=1) can be determined from a histogram of the non-red eye pixels as shown in  FIG. 15 . For a given weighted red value x, P(x|y=0) is equal to the number of pixels in the bin for the weighted red value x divided by the total number of non-red eye pixels in the LR working area.  
         [0058]     Probability P(y=1) is the total number of red eye pixels divided by the total number of pixels in the LR working area. Similarly, probability P(y=0) is the total number of non-red eye pixels divided by the total number of pixels in the LR working area.  
         [0059]     In step  1108 , the software retrieves HR working areas in image  10  that correspond to LR working areas in low resolution image  10 A.  
         [0060]     In step  1110 , the software determines the weighted red values of the pixels in each of the HR working area. As discussed above, the weighted red value is the greater of the purple-red value and the orange-red value of that pixel in one embodiment of the invention. From the weighted red values and the determined probabilities for each LR working area, the software applies Equation 18 to identify (e.g., flag) the red eye pixels in the corresponding HR working area (also referred to as “HR red eye pixels”). The software then groups contiguous red eye pixels in the HR working areas search area into red eye regions.  
         [0061]     In step  1112 , the software performs steps  112 ,  114 , and  120  to  128  described above. Specifically, in steps  112  and  114 , the software rejects red eye regions that are not round. In steps  120  and  122 , the software rejects red eye regions that are not proximate to a facial region within their HR working areas. In steps  124  and  126 , the software rejects red eye regions that are not proximate to a sclera of an eye within their working areas. In step  128 , the software replaces the red eye pixels in the remaining red eye regions with black pixels.  
         [0062]     Various other adaptations and combinations of features of the embodiments disclosed are within the scope of the invention. Numerous embodiments are encompassed by the following claims.