A computer program product for redeye detection

The invention relates generally to the field of digital image processing and, more particular to a method for detecting redeye in digital images.

When flash illumination is used for the capture of an image sometimes the pupils of people in the image appear red. This is caused by light from the flash unit entering the pupil, multiply reflecting off the retina, and finally exiting back through the pupil. Because light is partially absorbed by capillaries in the retina the pupil appears red in the image. This phenomena is referred to as "redeye." The probability of redeye being observed increases the closer the flash unit is to the optical axis of the lens. Therefore, redeye is commonly observed in images captured by a small camera with an integral flash unit.

Commonly assigned US-A-5,432,863 describes a user-interactive method for the detection of objects in an image that have the color characteristic of redeye. This method automatically detects candidate redeye pixels based on shape coloration and brightness.

Although the presently known method of detecting redeye is satisfactory, it is not without drawbacks. The method of US-A-5,432,863 does not determine whether the candidate pixels are located in a face or are part of a human eye.

Consequently, a need exists for detecting redeye that overcomes the above-described drawbacks.

The present invention is directed to overcoming one or more of the problems set forth above. Briefly summarized, according to one aspect of the present invention, the invention resides in a computer program product for detecting eye color defects of a subject in an image due to flash illumination, comprising : a computer readable storage medium having a computer program stored thereon for performing the steps of: (a) detecting skin colored regions in a digital image; (b) searching the skin colored regions for groups of pixels with color characteristic of redeye defect; and (c) correcting color of the pixels based on a location of redeye defect found in step (b).

It is an object of the present invention to provide a method for automatically detecting redeye defects.

It is an object of the present invention to provide a method for determining whether candidate redeye defects are part of the human face.

It is also an object of the present invention to provide a method for determining whether candidate redeye defects are part of the human eye.

These and other aspects, objects, features and advantages of the present invention will be more clearly understood and appreciated from a review of the following detailed description of the preferred embodiments and appended claims, and by reference to the accompanying drawings. <ul id="ul0001" list-style="none" compact="compact"><li>Fig. 1 is a diagram illustrating redeye;</li><li>Fig. 2 is an overview flowchart of the software program of the present invention;</li><li>Fig. 3 is a detailed flowchart of the continuous skin colored region determination portion of Fig. 2;</li><li>Fig. 4 is a binary representation of Fig. 1 illustrating skin-colored regions;</li><li>Fig. 5 is a detailed viewed of the individual continuos colored regions of Fig. 4;</li><li>Fig. 6 is a diagram of ellipses fitted to the views of Fig. 5;</li><li>Fig. 7 illustrates resized candidate face regions;</li><li>Fig. 8 is a diagram of resized ellipses corresponding to the candidate face regions fitted to Fig. 7;</li><li>Fig. 9 is a detailed flowchart of the candidate redeye determination portion of Fig. 2;</li><li>Fig. 10 illustrates the candidate redeye defects of Fig. 7;</li><li>Fig. 11 is a detailed flowchart of the eye detection portion of Fig. 2;</li><li>Fig. 12 illustrates an eye template, and zone map; and</li><li>Fig. 13 illustrates scoring functions of the present invention.</li></ul>

In the following description, the present invention will be described in the preferred embodiment as a software program. Those skilled in the art will readily recognize that the equivalent of such software may also be constructed in hardware.

Fig. 1 is a grayscale image 10 of a color image illustrating two pairs of redeyes 20.

Referring to Fig. 2, there is illustrated an overview flowchart of the present invention. A color digital image is input to the software program residing on a computer system, such computer systems being well known in the art. The code values of the digital image are preferably proportional to the log of the amount of exposure of the film used to capture the image by the original scene S2. The program begins by identifying all separate continuous skin colored regions in the image S4.

Referring to Fig. 3, there is illustrated a detail flowchart of step S4 in Fig. 2. First, the red, green, and blue values of the color image are converted into <i>LST</i> color space S4a using the relations:<maths id="math0001" num=""><math display="block"><mrow><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><mtext mathvariant="italic">L</mtext><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>√3</mtext></mrow></mfrac><mtext> (</mtext><mtext mathvariant="italic">R</mtext><mtext> + </mtext><mtext mathvariant="italic">G</mtext><mtext> + </mtext><mtext mathvariant="italic">B</mtext><mtext>)</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext mathvariant="italic">S</mtext><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>√2</mtext></mrow></mfrac><mtext> (</mtext><mtext mathvariant="italic">R</mtext><mtext> - </mtext><mtext mathvariant="italic">B</mtext><mtext>)</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext mathvariant="italic">T</mtext><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>√6</mtext></mrow></mfrac><mtext> (</mtext><mtext mathvariant="italic">R</mtext><mtext> + </mtext><mtext mathvariant="italic">B</mtext><mtext> - 2</mtext><mtext mathvariant="italic">G</mtext><mtext>)</mtext></mrow></mtd></mtr></mtable></mrow></mtd></mtr></mtable></mrow></math><img file="EP0899686A2_D0001.tif" /></maths> where <i>R</i>, <i>G,</i> and <i>B</i>, are the red, green, and blue code value of a pixel in the color image, respectively.

The next step is to build a three-dimensional histogram. In order to reduce the size of the histogram, first, the <i>L</i>, <i>S</i>, and <i>T</i> code values are quantized by dividing them by 8.0 x sqrt(3), 2.0, and 2.0, respectively S4b. These quantized code values are referred to as <i>L</i><img file="EP0899686A2_D0002.tif" />, <i>S</i><img file="EP0899686A2_D0002.tif" />, and <i>T</i><img file="EP0899686A2_D0002.tif" />. Each combination of <i>L</i><img file="EP0899686A2_D0002.tif" />, <i>S</i><img file="EP0899686A2_D0002.tif" />, and <i>T</i><img file="EP0899686A2_D0002.tif" /> values is referred to as a "bin" of the histogram. The value of the histogram <i>H</i>(<i>L</i><img file="EP0899686A2_D0002.tif" />, <i>S</i><img file="EP0899686A2_D0002.tif" />, <i>T</i><img file="EP0899686A2_D0002.tif" />) S4c is equal to the number of pixels in the image that have quantized code values of <i>L</i><img file="EP0899686A2_D0002.tif" />, <i>S</i><img file="EP0899686A2_D0002.tif" />, and <i>T</i><img file="EP0899686A2_D0002.tif" />. An alternative way of stating this is that the histogram tell us the number of pixels in the image that fall into each bin. This number is referred to as the value of the bin.

The histogram is smoothed S4d by replacing the value of each bin by a weighted average of the value of that bin and the values of immediate neighboring bins. Next, the peak values in the histogram are found S4e and each bin in the histogram is assigned S4f the peak value that is located closest to it. Finally, since each pixel in the color image has been assigned to a bin of the histogram and each bin has been assigned to a peak, a peak is assigned to each pixel in the color image S4g. The single band image in which a pixel's code value is equal to the number of the peak that it was assigned to is referred to as the segmented image.

Continuous regions in the segmented image that have the same code value are likely to correspond to an object or part of an object in the color image. A unique number (label) is assigned to all such regions in the segmented image S4h. The numbers are sequentially assigned starting with 1 for the region with the greatest number of pixels. The single band image in which code values correspond to the label of the region that the pixel belongs to is called the labeled image.

The program then decides which of the continuous regions in the segmented image corresponds to a region in the color image that has a color that is typical of human skin. The average <i>L</i>, <i>S</i>, and <i>T</i> code values of each region is calculated and, based on this, each region is assigned a score <i>P</i>_<i>skin</i> S4i. A high value of <i>P</i>_<i>skin</i> indicates that the region is of a color that is typical of human skin. Alternatively, a low number indicates that the color of the region is atypical of skin. Regions for which <i>P</i>_<i>skin</i> exceeds a threshold <i>T</i>_<i>skin</i> of 0.10 are referred to as skin-colored regions S4j.

One final step is necessary to associate each face in the color image with a single skin colored region. The process described above will often result in a single face being associated with more that one skin colored region because due to complexion, shadows, and etc., the color of the face is not uniform. Two skin colored regions are merged into a single skin colored region if two conditions are satisfied S4k. The first condition requires that the two regions be inter-connected. A pixel in region <i>i</i> has a connection to region <i>j</i> if a pixel belonging to region <i>j</i> is one of the eight nearest neighbor pixels. A function <i>Q(i</i>, <i>j)</i> is calculated which is proportional to the number of connections between pixels of region <i>i</i> and <i>j</i>. The function is normalized so that <i>Q(i</i>, <i>i)</i> is equal to 1.0. If <i>Q(i</i>, <i>j)</i> exceeds the threshold <i>MinMergerFraction</i> regions <i>i</i> and <i>j</i> will be merged into a single region if the second condition is also satisfied, for example a threshold of 0.005 may be used. The second condition is that the distance between the colors of the regions <i>i</i> and <i>j</i> given by<maths id="math0002" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">color</mtext></mrow></msub><mtext> = ((</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> + (</mtext><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> + (</mtext><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>½</mtext></mrow></msup></mrow></math><img file="EP0899686A2_D0003.tif" /></maths> must be less than <i>MaxMergeColorDistance</i> which is set equal to 40.0.

The process of merging skin colored regions begins with the smallest region which, if the two conditions are satisfied, is merged with a larger region. If region <i>i</i> is merged with larger region <i>j</i> it may then happen that region <i>j</i> gets merged with an even larger region <i>k</i>. When this occurs regions <i>i</i>, <i>j</i>, and <i>k</i> are merged into a single region. Note that regions <i>i</i> and <i>k</i> may be merged together even though the above two conditions are not satisfied for these two regions. They are merged because of their mutual connection to region <i>j</i>.

The result of skin color detection is a map of the skin colored regions in the color image S41. Areas that are not skin colored are given a code value of zero. The separate continuous skin colored regions are numbered consecutively in order of decreasing region size beginning with the number 1. Fig. 4 shows a map of the skin colored regions in Fig. 1.

Referring to Fig. 2, and as illustrated in Fig. 5, a sub-map of each skin colored region is formed by cutting out from the skin map (Fig. 4) the smallest rectangular section that contains all of that skin region S6. For example, skin region 30b in Fig. 5 corresponds to skin region 30a in Fig. 4. Fig. 5 shows the map of each separate continuous skin colored regions as an individual sub-map. The column and row of the skin map that correspond to the top left corner of the sub-map are referred to as <i>Col</i>_{<i>cutout</i>} and <i>Row</i>_{<i>cutout</i>}, respectively. In the sub-map code values of 255 (white) indicates that the pixel is located at a position at which skin color is present. A code value of 0 (black) indicates the absence of skin color.

Referring to Fig. 2, and as illustrated in Fig. 6, in the next step an ellipse 35 is fitted S8 to the individual skin color sub-maps found in step S6 (Fig. 5). A method of fitting an ellipse to a binary image is described in <u>Computer and Robot Vision, Volume I,</u> by Robert M. Haralick and Linda G. Shapiro, Addison-Wesley (1992), pp. 639-658. A human face is approximately elliptical. Therefore, if the skin color sub-map is of a human face, then the ellipse should fit the skin color map well and the minor axis of the ellipse should approximately equal the width of the face. A measure of the fit of an ellipse to the skin color sub-map is given by<maths id="math0003" num=""><math display="block"><mrow><mtext mathvariant="italic">Fit</mtext><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mfenced open="(" close=")"><mrow><mtext>2 - </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">out</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">N</mtext></mrow></mfrac><mtext> - </mtext><mfrac><mrow><mtext mathvariant="italic">A</mtext><mtext>-</mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">in</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">A</mtext></mrow></mfrac></mrow></mfenced></mrow></math><img file="EP0899686A2_D0004.tif" /></maths> where <i>N</i> is the number of skin colored pixels (code value 255) in the map, <i>N</i>_<i>out</i> is the number of skin colored pixels that fall outside the ellipse, <i>N</i>_<i>in</i> is the number of skin colored pixels that are inside the ellipse, and <i>A</i> is the number of pixels in the ellipse. <i>A</i> is also referred to as the area of the ellipse. If all of the skin colored pixels are in the ellipse and the number of skin colored pixels equals the area of the ellipse then <i>Fit</i> is equal to one and the fit is perfect. When skin colored pixels fall outside of the ellipse or the area of the ellipse is greater than the number of skin colored pixels inside it then the value of <i>Fit</i> is diminished. If the value of <i>Fit</i> is less than a predetermined value <i>MinEllipseFit</i> which is set equal to 0.70 then we conclude that the skin colored region is not a face and we do not process it further S10.

Another indication of whether the skin color sub-map is of a face is the aspect ratio of the ellipse <i>AspectRatio</i> which is given by<maths id="math0004" num=""><math display="block"><mrow><mtext mathvariant="italic">AspectRatio</mtext><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">major</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">minor</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0899686A2_D0005.tif" /></maths> where <i>D</i>_<i>major</i> is the major axis of the ellipse and <i>D</i>_<i>minor</i> is the minor axis in pixels. If <i>AspectRatio</i> is greater than <i>MaxAspectRatio</i> which is set equal to 3.0 the skin colored region corresponds to an object in the image that is too long and thin to be a face. The program determines that the skin colored region is not a face and does not process it further S10.

If the skin sub-map has an acceptable degree of fit to an ellipse and the ellipse has an acceptable aspect ratio, the map potentially indicates the position of a face. Next, we calculate a resize factor <i>S</i>_{<i>prescale</i>} which is given by the following equation<maths id="math0005" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext mathvariant="italic">prescale</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">AimEyeDistance x FaceWidthEyeDistanceRatio</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">minor</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0899686A2_D0006.tif" /></maths> where <i>AimEyeDistance</i> which is set equal to 75 pixels is the desired distance between eyes, and <i>FaceWidthEyeDistanceRatio</i> which is set equal to 2.0 is the ratio between the width and eye distance for a typical face. If <i>S</i>_{<i>prescale</i>} is less than <i>MinPrescale</i> 0.10 or greater than <i>MaxPrescale</i> 1.50 the skin colored region is not processed further S10. The next step is to cut-out from the color image a sub-color-image that corresponds exactly to the location of the sub-map S12. If the minor axis of the ellipse is approximately equal to the width of the face then the distance between the eyes in the face should be close to <i>AimEyeDistance</i>. Fig. 7 shows the sub-color-images 40 after they have been resized in this manner. It is instructive to note that Fig. 7 is illustrated as a gray scale drawing, although the actual image is a color image. Fig. 8 shows the ellipses 50 that correspond to each of these sub-color-images that have also been resized S14. In practice, it is desirable to add extra rows and columns to the edges of the resized sub-color-images and sub-maps so that when these images are processed further an out-of-bounds pixel is not addressed. The top and bottom of the images are padded with <i>Pad</i> rows and the left and right side with <i>Pad</i> columns.

Now that skin colored regions that have the shape of a face have been identified, the location of candidate redeyes need to be identified S16, which is illustrated in detail in Fig. 9. Now referring to Fig. 9, the sub-color-images 40 are processed so as to identify small red features. The program begins by defining a new single band image S16a with pixel values X given by<maths id="math0006" num=""><math display="block"><mrow><mtext mathvariant="italic">X</mtext><mtext> = </mtext><mtext mathvariant="italic">R</mtext><mtext> - </mtext><mtext mathvariant="italic">Max(G</mtext><mtext>, </mtext><mtext mathvariant="italic">B)</mtext></mrow></math><img file="EP0899686A2_D0007.tif" /></maths> where <i>R</i>, <i>G</i>, and <i>B</i>, are the red, green, and blue code value of the sub-color-image, respectively.

Redeyes in the new image will appear as small elliptical areas of high code value possibly with a small low code value region in the middle that is due to glint in the pupil. The affect of glint is removed by performing a gray scale morphological closing S16b using a <i>W</i>_<i>close</i> x <i>W</i>_<i>close</i> kernel, for example a 3 x 3 kernal although other sizes may also be used. Gray scale morphological operations are disclosed in <u>Image Analysis and Mathematical Morphology Volume 1</u>, by Jean Serra, Academic Press (1982), pp. 424-478. Next, the small regions of high code value are removed by a gray scale morphological opening operation using a <i>W</i>_<i>open</i> x <i>W</i>_<i>open</i> kernel, for example a 5 x 5 kernal although other sizes may also be used S16c. The opened image is then subtracted from the closed image in order to form a residual image S16d. This image shows what was in the opened image, but not in the closed image. Namely, small regions of high code value which correspond to small red features in the sub-color-image. Next, the residual image is smoothed S16e with a linear filter having the kernel shown below. <tables id="tabl0001" num="0001"><table frame="all"><tgroup cols="3" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="52.50mm" /><colspec colnum="2" colname="col2" colwidth="52.50mm" /><colspec colnum="3" colname="col3" colwidth="52.50mm" /><tbody valign="top"><row><entry namest="col1" nameend="col1" align="right">1</entry><entry namest="col2" nameend="col2" align="right">2</entry><entry namest="col3" nameend="col3" align="right">1</entry></row><row><entry namest="col1" nameend="col1" align="right">2</entry><entry namest="col2" nameend="col2" align="right">4</entry><entry namest="col3" nameend="col3" align="right">2</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="right">1</entry><entry namest="col2" nameend="col2" align="right">2</entry><entry namest="col3" nameend="col3" align="right">1</entry></row></tbody></tgroup></table></tables> For each pixel in the smoothed residual image, a 7x7 window centered at that pixel is examined. If the code value of that pixel exceeds the threshold <i>Tpeak</i> which is set equal to 5 and is greater than or equal to the code value of all the other pixels in the window, that pixel is classified as a peak S16f. Fig. 10 shows the peaks 37 for all of the sub-color-images in Fig. 7. After all the peaks in the smoothed residual image have been found the individual peaks are examined S16g. First, if a pixel has been classified as a peak and a neighboring pixel that is west, north-west, north, or north-east of this pixel has also been classified as a peak, the peak is eliminated S16h.

A pixel that has been classified as a peak is a candidate redeye pixel. It is possible however that the location of the peak coincides with glint in the pupil and not the red defect. For this reason, pixels within a distance <i>GlintRadius</i> equal to 2 from the peak are examined S16i. The candidate redeye pixel is moved to the nearby pixel with the highest color <i>score P</i>_<i>color</i> which will be defined below.

Next, the candidate redeye pixel is used as a seed to grow a continuous region of pixels of simular color. If the number of pixels in the region is less than <i>MinSize</i> or greater than <i>MaxSize</i> the region is not of a size that is characteristic of a redeye defect and the candidate redeye pixel is eliminated S16j.

The result of the above processing is a map of candidate redeye pixels for each sub-color-image S16k. The ellipses in Fig. 8 are approximate maps of the region in the corresponding sub-color-images in Fig. 7 that have been identified as potentially being a face. Therefore, only the candidate redeye pixels that fall inside of the ellipse are considered in the next phase eye detection which is outlined in Fig. 11.

Referring back to Fig. 2, the purpose of eye detection is to determine whether the candidate redeye pixels are indeed part of an eye. The eye detection procedure requires a monotone version of the color image S18. The green band of the color image is used after the contrast is increased by transforming the green pixel code values using the equation<maths id="math0007" num=""><math display="block"><mrow><mtext mathvariant="italic">G</mtext><mtext> = 255</mtext><msup><mrow><mfenced open="(" close=")"><mrow><mfrac><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>255</mtext></mrow></mfrac></mrow></mfenced></mrow><mrow><mtext>γ</mtext></mrow></msup></mrow></math><img file="EP0899686A2_D0008.tif" /></maths> where <i>G</i> is the code value of the green band and γ is a parameter which is set equal to 2.0. This monocolor version of the color image will be referred to as the luminance image.

The eye detection procedure S20 in Fig. 2 is based on the process of template matching. It facilitates understanding to note that any image of an eye can be used a the template. The top image 60 in Fig. 12 shows a left-eye template. The bottom image 70 shows a division of the template into zones. Zone 1 is the eyebrow region. Zones 2 and 3 are the left and right sides of the eye, respectively. Zone 4 includes the pupil and iris. Zone 0 is not used. The eye template was taken from an image in which the distance between the eyes is <i>TemplateEyeDistance</i> equal to 306 pixels and the tilt of the two eyes is close to zero. As discussed above, a pair of redeyes in the resized color sub-images should be approximately a distance <i>AimEyeDistance</i> (75 pixels) apart. Therefore, in order for the template to be of the proper size to match an eye is must be resized by a factor of<maths id="math0008" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>= </mtext><mfrac><mrow><mtext mathvariant="italic">AimEyeDistance</mtext></mrow><mrow><mtext mathvariant="italic">TemplateEyeDistance</mtext></mrow></mfrac></mrow></math><img file="EP0899686A2_D0009.tif" /></maths>

In practice, the estimation of the face width from the minor axis of the ellipse will not always be accurate. Also, the eyes may be tilted. For this reason starting with the original left-eye template and the zone map, a collection of left-eye, right-eye (mirror image of left-eye), and zone maps are generated that span a range of sizes and orientations S22. The original eye template and zone map are resized from a factor of <i>S</i>_<i>0</i><i> x Narrow</i> to <i>S</i>₀<i>x Wide</i> in increments of <i>SStep</i>. Preferred values of <i>Narrow</i>, <i>Wide</i>, and <i>Sstep</i> are 1.5, 0.50, and 0.05, respectively. In order to accommodate tilt for each resize factor, a series of tilted templates and zone maps are generated that range from -<i>MaxTilt</i> degrees (clock-wise tilt) to <i>MaxTilt</i> degrees in increments of <i>TStep</i> degrees S22. The preferred value of MaxTilt is 30 degrees and of <i>TStep</i> is 2.0 degrees.

Referring to Fig. 11, a detailed flowchart of step S20 of Fig. 2 is shown. A pair of candidate redeye pixels are considered that hypothetically belong to a left and right redeye pair S20a. The scale of the eye relative to the original eye template is related to the distance S20b between the candidate redeye pixel pair by the equation<maths id="math0009" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext mathvariant="italic">pair</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext>((</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">p</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">-R</mtext></mrow><mrow><mtext mathvariant="italic">p</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> + (</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">-R</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>1/2</mtext></mrow></msup></mrow><mrow><mtext mathvariant="italic">TemplateEyeDistance</mtext></mrow></mfrac></mrow></math><img file="EP0899686A2_D0010.tif" /></maths> where <i>L</i>_<i>p</i>(<i>R</i>_<i>p</i>) is the column of the left (right) candidate redeye pixel, <i>L</i>_<i>l</i>(<i>R</i>_<i>l</i>) is the row of the left (right) candidate redeye pixel. (The column numbers begin with 1 and increase from left to right. The row numbers begin with 1 and increase from top to bottom.) The tilt S20b between the candidate redeye pixels is given by<maths id="math0010" num=""><math display="block"><mrow><mtext mathvariant="italic">Tilt</mtext><msup><mrow><mtext> = tan</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mfenced open="(" close=")"><mrow><mfrac><mrow><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>-</mtext><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext mathvariant="italic">p</mtext></mrow></msub><mtext>-</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">p</mtext></mrow></msub></mrow></mfrac></mrow></mfenced></mrow></math><img file="EP0899686A2_D0011.tif" /></maths>

As discussed above, an ensemble of eye templates and zone map templates were made that span a range of resize factors from <i>S</i>₀<i>x Narrow</i> to <i>S</i>₀<i>x Wide</i> with resolution <i>SStep</i> and with a tilt from -<i>MaxTilt</i> degrees to <i>MaxTilt</i> degrees with a resolution <i>TStep</i>. The left-eye template, right-eye template, and zone map that most closely match the value of <i>S</i>_<i>pair</i> and <i>Tilt</i> for the pair of candidate redeye pixels is used in the correlation step that follows. If <i>S</i>_<i>pair</i> or <i>Tilt</i> are outside of this range, this pair is not processed further S20c.

After an eye template has been selected the next step is to determine if the region around the redeye pixel matches an eye. This is done by performing a correlation of the left-eye template with a region around the left candidate redeye pixel and the right-eye template with a region around the right candidate redeye pixel of the luminance image S20d. One step of the correlation process is to match up pixels of the template and luminance image and calculate the product of their code values. The center of the template images corresponds to the center of the eye. Since the candidate redeye pixels are close, but not necessarily at the center of an eye, we perform the correlation several times with the center of the template matched to all of the pixels within a square that extends a distance <i>LookAround</i> equal to 3 about the candidate redeye pixel. The correlation is performed separately for zones 1 through 4 of the template (see Fig. 12). These correlations are referred to as <i>Cz1</i>, <i>Cz2</i>, <i>Cz3</i>, and <i>Cz4</i>. In addition, an overall correlation is calculated for a region that consists of the sum of zones 1 through 4. This overall correlation is referred to as <i>C</i>. The pixel in the square around the candidate redeye pixel with the highest value of the overall correlation <i>C</i> is the best guess of the center of an eye which contains the candidate redeye pixel. This pixel is referred to as the eye-center pixel. Both the left and right candidate redeye pixels have an associated eye-center pixel.

The correlation process is now explained in detail. The template image is denoted by the function Φ (<i>p</i>,<i>l</i>) where <i>p</i> is the column number and <i>l</i> is the row number. The number of columns and rows in the template is <i>w</i> and <i>h</i>, respectively. The center of the eye template is approximately the location of the center of the eye. A zone of the template is correlated with the luminance image which we denote by Γ(<i>p</i>, <i>l</i>) at column <i>p</i>_o and row <i>l</i>_o by calculating the product Π given by.<maths id="math0011" num=""><math display="block"><mrow><mtext>Π = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext></mrow></msub></mrow></mfrac><apply><sum /><lowlimit><mtext mathvariant="italic">p</mtext><mtext>∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><apply><sum /><lowlimit><mtext>/∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><mtext>Γ(</mtext><mtext mathvariant="italic">p</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">p</mtext></mrow><mrow><mtext mathvariant="italic">o</mtext></mrow></msub><mtext>-</mtext><mtext mathvariant="italic">w</mtext><msub><mrow><mtext>/2-1,/+/</mtext></mrow><mrow><mtext mathvariant="italic">o</mtext></mrow></msub><mtext>-</mtext><mtext mathvariant="italic">h</mtext><mtext>/2-1)Φ(</mtext><mtext mathvariant="italic">p,l</mtext><mtext>)</mtext></mrow></apply></mrow></apply></mrow></math><img file="EP0899686A2_D0012.tif" /></maths> where <i>p</i> ∈ <i>Z</i> means that column <i>p</i> is in zone <i>Z</i>, <i>l</i> ∈ Z means that row <i>l</i> is in zone <i>Z</i>, and <i>N</i>_<i>z</i> is the number of pixels in the zone. The mean code value of the template in zone <i>Z</i> given by<maths id="math0012" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext>Φ</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext></mrow></msub></mrow></mfrac><apply><sum /><lowlimit><mtext mathvariant="italic">p</mtext><mtext>∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><apply><sum /><lowlimit><mtext>/∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><mtext>Φ(</mtext><mtext mathvariant="italic">p,l</mtext><mtext>)</mtext></mrow></apply></mrow></apply></mrow></math><img file="EP0899686A2_D0013.tif" /></maths> is also calculated. In addition, the standard deviation of the template in zone Z is calculated according to the equation.<maths id="math0013" num=""><math display="block"><mrow><msub><mrow><mtext>σ</mtext></mrow><mrow><mtext>Φ</mtext></mrow></msub><mtext> = </mtext><msup><mrow><mfenced open="(" close=")"><mrow><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext mathvariant="italic">N</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext></mrow></msub></mrow></mfrac><apply><sum /><lowlimit><mtext mathvariant="italic">p</mtext><mtext>∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><apply><sum /><lowlimit><mtext>/∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><mtext>(Φ(</mtext><mtext mathvariant="italic">p,l</mtext><mtext>)-</mtext><mtext mathvariant="italic">M</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>Φ</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow></apply></mrow></apply></mrow></mfenced></mrow><mrow><mtext>1/2</mtext></mrow></msup></mrow></math><img file="EP0899686A2_D0014.tif" /></maths> Similarly, we calculate the mean code value of the luminance image in zone <i>Z</i> using the equation<maths id="math0014" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext>Γ</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext></mrow></msub></mrow></mfrac><apply><sum /><lowlimit><mtext mathvariant="italic">p</mtext><mtext>∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><apply><sum /><lowlimit><mtext>/∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><mtext>Γ(</mtext><mtext mathvariant="italic">p</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">p</mtext></mrow><mrow><mtext mathvariant="italic">o</mtext></mrow></msub><mtext>-</mtext><mtext mathvariant="italic">w</mtext><msub><mrow><mtext>/2-1,/+/</mtext></mrow><mrow><mtext mathvariant="italic">o</mtext></mrow></msub><mtext>-</mtext><mtext mathvariant="italic">h</mtext><mtext>/2-1)</mtext></mrow></apply></mrow></apply></mrow></math><img file="EP0899686A2_D0015.tif" /></maths> and the standard deviation using the following equation<maths id="math0015" num=""><math display="block"><mrow><msub><mrow><mtext>σ</mtext></mrow><mrow><mtext>Γ</mtext></mrow></msub><mtext> = </mtext><msup><mrow><mfenced open="(" close=")"><mrow><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext mathvariant="italic">N</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">Z</mtext></mrow></msub></mrow></mfrac><apply><sum /><lowlimit><mtext mathvariant="italic">p</mtext><mtext>∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><apply><sum /><lowlimit><mtext>/∈</mtext><mtext mathvariant="italic">z</mtext></lowlimit><uplimit /><mrow><mtext>(Γ(</mtext><mtext mathvariant="italic">p</mtext><mtext>+</mtext><mtext mathvariant="italic">p</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">o</mtext></mrow></msub><mtext>-</mtext><mtext mathvariant="italic">w</mtext><mtext>/2-1,/+1</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">o</mtext></mrow></msub><mtext>-</mtext><mtext mathvariant="italic">h</mtext><mtext>/2-1)-</mtext><mtext mathvariant="italic">M</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>Γ</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow></apply></mrow></apply></mrow></mfenced></mrow><mrow><mtext>1/2</mtext></mrow></msup></mrow></math><img file="EP0899686A2_D0016.tif" /></maths>

Using the quantities defined above the correlation of the luminance image with the template in zone <i>Z</i> is given by the relation<maths id="math0016" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext>Π-</mtext><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext>Φ</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext>Γ</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext>σ</mtext></mrow><mrow><mtext>Φ</mtext></mrow></msub><msub><mrow><mtext>σ</mtext></mrow><mrow><mtext>Γ</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0899686A2_D0017.tif" /></maths> If the code values of the image and the template are exactly the same in zone <i>Z</i> then <i>C</i>_<i>z</i> is equal to 1.0. If the image and the template are completely uncorrelated then <i>C</i>_<i>z</i> will be equal to zero.

The values of <i>C</i>, <i>C</i>_<i>z1</i>, <i>C</i>_<i>z2</i>, <i>C</i>_<i>z3</i>, and <i>C</i>_<i>z4</i> for the eye-center pixels are used in the calculation of a score that is a measure of the likelihood that the pair of candidate redeye pixels are part of a redeye defect in the sub-color-image S20e. Each of the correlations are used as a variable in an associated scoring function that ranges from 0.0 to 1.0. For example, the scoring function associated with the overall correlation <i>C</i> which we refer to as <i>pC(C)</i> is 0.0 if the value of <i>C</i> for an eye-center pixel indicates that it is very unlikely that the pixel actually is located at the center of an eye. On the other hand, if the value of <i>C</i> is in a range that is typical of the correlation of the template with an eye then <i>pC(C)</i> is 1.0. Otherwise <i>pC(C)</i> takes on an intermediate value. The scoring function <i>pC(C)</i> and other scoring functions described below are shown in Fig. 13.

Scores are defined based on these scoring functions which will be combined later into an overall score for a candidate redeye pair. The following equation defines a score <i>P</i>_<i>corr</i> related to the overall correlation <i>C</i> as simply<maths id="math0017" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">corr</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">pC</mtext><mtext>(</mtext><mtext mathvariant="italic">C</mtext><mtext>)</mtext></mrow></math><img file="EP0899686A2_D0018.tif" /></maths> The score <i>P</i>_<i>zone</i> associated with the zone correlations is a weighted average of the zone correlation scoring functions. It has been found that the correlation in zone 4 (the pupil) is a much more reliable indicator of the presence of an eye than the other zones. For this reason it is given more weight than other zones. Typical we set the weight <i>W</i> equal to 6.0. <i>P</i>_<i>zone</i> is given by<maths id="math0018" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">zone</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">pC</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>1</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext>Z1</mtext></mrow></msub><mtext>)+</mtext><msub><mrow><mtext mathvariant="italic">pC</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>2</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>2</mtext></mrow></msub><mtext>)+</mtext><msub><mrow><mtext mathvariant="italic">pC</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>3</mtext></mrow></msub><mtext>)+</mtext><msub><mrow><mtext mathvariant="italic">WpC</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>4</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>4</mtext></mrow></msub><mtext>)</mtext></mrow><mrow><mtext mathvariant="italic">W</mtext><mtext>+3</mtext></mrow></mfrac></mrow></math><img file="EP0899686A2_D0019.tif" /></maths>

It has been found that the standard deviation of the luminance image σ_Γ that was calculated in the process of calculating the overall correlation <i>C</i> is a good indicator if the feature in the luminance image centered at the eye-center pixel is actually an eye. For instance, if σ_Γ is very low than the feature is of too low contrast to be an eye. With this in mind we define a score associated with σ_Γ by<maths id="math0019" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">sigma</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">pSigma</mtext><msub><mrow><mtext>(σ</mtext></mrow><mrow><mtext>Γ</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0899686A2_D0020.tif" /></maths>

Finally, the color of the candidate redeye pixel must be indicative of a real redeye defect. For this calculation the red, green, and blue, code values of the candidate redeye pixel is convert into luminance (<i>Lum</i>), hue (<i>Hue</i>), and saturation (<i>Sat</i>) values. Luminance is calculated as follows<maths id="math0020" num=""><math display="block"><mrow><mtext mathvariant="italic">Lum</mtext><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">Max</mtext><mtext>(</mtext><mtext mathvariant="italic">R</mtext><mtext>,</mtext><mtext mathvariant="italic">G</mtext><mtext>,</mtext><mtext mathvariant="italic">B</mtext><mtext>) + </mtext><mtext mathvariant="italic">Min</mtext><mtext>(</mtext><mtext mathvariant="italic">R</mtext><mtext>,</mtext><mtext mathvariant="italic">G</mtext><mtext>,</mtext><mtext mathvariant="italic">B</mtext><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac></mrow></math><img file="EP0899686A2_D0021.tif" /></maths> The value of <i>Lum</i> for a pixel ranges from zero to the highest possible code value. The saturation given by<maths id="math0021" num=""><math display="block"><mrow><mtext mathvariant="italic">Sat</mtext><mtext> = 100 </mtext><mfrac><mrow><mtext mathvariant="italic">Max</mtext><mtext>(</mtext><mtext mathvariant="italic">R</mtext><mtext>,</mtext><mtext mathvariant="italic">G</mtext><mtext>,</mtext><mtext mathvariant="italic">B</mtext><mtext>) - </mtext><mtext mathvariant="italic">Min</mtext><mtext>(</mtext><mtext mathvariant="italic">R</mtext><mtext>,</mtext><mtext mathvariant="italic">G</mtext><mtext>,</mtext><mtext mathvariant="italic">B</mtext><mtext>)</mtext></mrow><mrow><mtext mathvariant="italic">Max</mtext><mtext>(</mtext><mtext mathvariant="italic">R</mtext><mtext>,</mtext><mtext mathvariant="italic">G</mtext><mtext>,</mtext><mtext mathvariant="italic">B</mtext><mtext>)</mtext></mrow></mfrac></mrow></math><img file="EP0899686A2_D0022.tif" /></maths> is a value ranging from 0 to 100. The hue is defined as in <u>Computer Graphics Principles and Practice 2nd ed.</u>, Addison-Wesley Publishing Company, page 592, except the color red is shifted to a hue angle of 120 degrees. The value of <i>Hue</i> may range from 0 to 360 degrees. The score that is related to the color of the candidate redeye pixel is defined by<maths id="math0022" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">color</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">pL</mtext><mtext>(</mtext><mtext mathvariant="italic">Lum</mtext><mtext>)</mtext><mtext mathvariant="italic">pH</mtext><mtext>(</mtext><mtext mathvariant="italic">Hue</mtext><mtext>)</mtext><mtext mathvariant="italic">pS</mtext><mtext>(</mtext><mtext mathvariant="italic">Sat</mtext><mtext>)</mtext></mrow></math><img file="EP0899686A2_D0023.tif" /></maths>

The result is a score <i>P</i>_<i>eye</i> which indicates the likelihood that a candidate redeye pixel is actually part of a redeye defect in the image. This score is defined by<maths id="math0023" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">eye</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">corr</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">zone</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">sigma</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">color</mtext></mrow></msub></mrow></math><img file="EP0899686A2_D0024.tif" /></maths> Its value is in the range of 0.0 to 1.0. The figure of merit <i>P</i>_<i>eye</i> is calculated for both the left and the right candidate redeye pixels in a pair. The average of these two values is given by<maths id="math0024" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">pair</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">eye</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">Left</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">eye</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">Right</mtext></mrow></msup></mrow><mrow><mtext>2</mtext></mrow></mfrac></mrow></math><img file="EP0899686A2_D0025.tif" /></maths> The pair of candidate redeye pixels for which <i>P</i>_<i>pair</i> is the largest is referred to as the best pair of candidate redeye pixels S20f. If <i>P</i>_<i>pair</i> exceeds the threshold <i>MinEyeScore</i> equal to 0.05, then the program processes further. Otherwise, the program concludes that a pair of redeyes is not present in the sub-color-image S20g.

It is important to minimize the possibility that the best pair of candidate redeye pixels that are <i>not</i> part of a pair of eyes with a redeye defect in the color image be incorrectly classified. One method of confirming that a pair of redeyes has indeed been located is to use the fact that a human face is approximately symmetric about a line that bisects the face S24 in Fig. 2. In order to do this, the sub-color-image is rotated so that the tilt of a line connecting the best pair of candidate redeye pixels is equal to zero. Next, an image centered at the midpoint between the eyes is cut-out of the sub-color-image. This image has a width of 1.5 times the distance between the candidate redeye pixels and a height equal to a quarter of its width. This image is in turn cut in half. The left half-image we refer to as <i>E</i>^<i>x</i>_<i>left</i><i>(p,l)</i> and the right half-image by <i>E</i>^<i>x</i>_<i>right</i><i>(p,l)</i> where the superscript <i>x</i> refers to a band of the color image. For example, <i>E</i>^<i>r</i>_<i>left</i><i>(p,l)</i> refers to the red band of the image. The columns in the right half-image are inverted (the first column becomes the last column, etc.) so that it becomes a mirror image of itself. A correlation of <i>E</i>^<i>x</i>_<i>left</i><i>(p,l)</i> and <i>E</i>^<i>x</i>_<i>right</i><i>(p,l)</i> is performed by first calculating the sum of products<maths id="math0025" num=""><math display="block"><mrow><msup><mrow><mtext>Π</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msup><msub><mrow><mtext mathvariant="italic"> </mtext></mrow><mrow><mtext mathvariant="italic">sym</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext mathvariant="italic">N</mtext></mrow></mfrac><apply><sum /><lowlimit><mtext mathvariant="italic">p</mtext></lowlimit><uplimit /><mrow><apply><sum /><lowlimit><mtext mathvariant="italic">l</mtext></lowlimit><uplimit /><mrow><msup><mrow><mtext mathvariant="italic">E</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msup><mtext mathvariant="italic">left</mtext><mtext>(</mtext><mtext mathvariant="italic">p</mtext><mtext>,</mtext><mtext mathvariant="italic">l</mtext><mtext>)</mtext><msup><mrow><mtext mathvariant="italic">E</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msup><mtext mathvariant="italic">right</mtext><mtext>(</mtext><mtext mathvariant="italic">p</mtext><mtext>,</mtext><mtext mathvariant="italic">l</mtext><mtext>)</mtext></mrow></apply></mrow></apply></mrow></math><img file="EP0899686A2_D0026.tif" /></maths> where the summations over <i>p</i> and <i>l</i> are over all of the columns and rows in the half- images, respectively, and <i>N</i> is the number of pixels in the half-images. The correlation is given by<maths id="math0026" num=""><math display="block"><mrow><msup><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msup><msub><mrow><mtext mathvariant="italic"> </mtext></mrow><mrow><mtext mathvariant="italic">sym</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msubsup><mrow><mtext>Π</mtext></mrow><mrow><mtext mathvariant="italic">sym</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msubsup><mtext>-</mtext><msubsup><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">left</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msubsup><msubsup><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">right</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msubsup></mrow><mrow><msubsup><mrow><mtext>σ</mtext></mrow><mrow><mtext mathvariant="italic">left</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msubsup><msubsup><mrow><mtext>σ</mtext></mrow><mrow><mtext mathvariant="italic">right</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msubsup></mrow></mfrac></mrow></math><img file="EP0899686A2_D0027.tif" /></maths> where <i>M</i>^<i>x</i>_<i>left</i> and <i>M</i>^<i>x</i>_<i>right</i> are the mean code values of band <i>x</i> of the half-images and σ^<i>x</i>_<i>left</i> and σ^<i>x</i>_<i>right</i> are the standard deviations. A score <i>P</i>_<i>sym</i> is defined based on a symmetry scoring function <i>pSym(C</i>^<i>x</i>_<i>sym</i><i>)</i> by<maths id="math0027" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">sym</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">pSym</mtext><mtext>(</mtext><msup><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">r</mtext></mrow></msup><mtext mathvariant="italic">sym</mtext><mtext>)</mtext><mtext mathvariant="italic">pSym</mtext><mtext>(</mtext><msup><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">g</mtext></mrow></msup><mtext mathvariant="italic">sym</mtext><mtext>)</mtext><mtext mathvariant="italic">pSym</mtext><mtext>(</mtext><msup><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msup><mtext mathvariant="italic">sym</mtext><mtext>)</mtext></mrow></math><img file="EP0899686A2_D0028.tif" /></maths>

The final score <i>P</i> is simply the product of <i>P</i>_<i>sym</i> and <i>P</i>_<i>pair</i>.<maths id="math0028" num=""><math display="block"><mrow><mtext mathvariant="italic">P</mtext><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">sym</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">pair</mtext></mrow></msub></mrow></math><img file="EP0899686A2_D0029.tif" /></maths> If this score which may range between 0.0 and 1.0 exceeds a threshold <i>MinScore</i> which is set equal to 0.05 S26, then the candidate redeye pixel pair is assumed to mark the location of a pair of redeye defects in the resized sub-color-image.

Finally, the positions of the left and right redeye defects in the original color image are calculated based on the position of the left and right candidate redeye pixels in the resized sub-color-image using the relations<maths id="math0029" num=""><math display="block"><mrow><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><mtext mathvariant="italic">p</mtext><mtext>' = </mtext><mfrac><mrow><mtext mathvariant="italic">p</mtext><mtext>-</mtext><mtext mathvariant="italic">Pad</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext mathvariant="italic">prescale</mtext></mrow></msub></mrow></mfrac><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">Col</mtext></mrow><mrow><mtext mathvariant="italic">cutout</mtext></mrow></msub><mtext> -1</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext mathvariant="italic">l</mtext><mtext>' = </mtext><mfrac><mrow><mtext mathvariant="italic">l</mtext><mtext>-</mtext><mtext mathvariant="italic">Pad</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext mathvariant="italic">prescale</mtext></mrow></msub></mrow></mfrac><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">Row</mtext></mrow><mrow><mtext mathvariant="italic">cutout</mtext></mrow></msub><mtext> -1</mtext></mrow></mtd></mtr></mtable></mrow></mtd></mtr></mtable></mrow></math><img file="EP0899686A2_D0030.tif" /></maths> where <i>p</i> and <i>l</i> are the column and row of the left candidate redeye pixel in the resized sub-color-image and <i>p</i><img file="EP0899686A2_D0002.tif" /> and <i>l</i><img file="EP0899686A2_D0002.tif" /> are the corresponding positions in the original color image S28.

It sometimes happens that two different skin colored regions after being fitted to an ellipse will overlap or be very close together. This may result in the same redeye pair being found twice or the detection of two redeye pairs that are too close together for both to be truly a pair of redeyes. For this reason, after all the redeye pairs in the color image have been located it is determined if any two pairs have redeye locations less than <i>MinInterpairEyeDistance</i> equal to 20 pixels apart. If this is the case the pair with the lower score is eliminated S30.