Automated detection and correction of eye color defects due to flash illumination.

FIELD OF THE INVENTION

0001The present invention relates to digital detection for eye color defects of a subject in a digital image.

BACKGROUND OF THE INVENTION

0002In color flash photography a phenomenon know as red eye can occur. The term "red eye" refers to a person's photographically reproduced pupil(s) when they appear red instead of their normal black coloration. [This effect also occurs in flash photography of animals, although the characteristic color may not be red.] The reddish colored light is the result of the light produced by the flash reflecting off the eye's layer immediately behind the retina. To prevent this problem two procedures have been used during image capture: (1) increase the ambient light levels or (2) separate the flash from the camera by several inches. The first solution reduces the size of the pupil thus reducing the quantity of light reflected and also lessens the amount of required flash illumination. The second measure prevents the lens from detecting the reflected light since it is confined to a narrow beam directed back towards its source--the flash. Unfortunately the amateur photographer is not always in a position to execute either of the above solutions. In general the amateur uses a flash to account for the location's lack of ambient light. In addition, many point-and-shoot cameras, as well as some SLR's, have the flash located closely to the lens.

0003After the image has been digitally captured it is possible to correct the eye color defects. Commonly assigned U.S. Patent No. 5,130,789 issued July 14, 1992 entitled "Localized Image Recoloring Using Ellipsoid Boundary Function" to Dobbs et al, describes a method by which a region's chroma and luma channels are modified after an operator identifies a region surrounding an eye.

SUMMARY OF THE INVENTION

0004It is an object of this invention to automatically determine a defective colored eye in an image.

0005It is another object of this invention to improve the correction by providing separate corrections for body, border, and glint pixels; and also provide for performing correction at different resolutions than that of detection.

0006One of the preferred methods of the present invention is a method of detecting for eye color defects of a subject in an image due to flash illumination, comprising the steps of: <ul id="ul0001" list-style="none"><li>a) defining a spatial region within which one or more eye color defects may exist, which region includes at least a portion of the subject's head;</li><li>b) sampling pixels within such spatial region for their color content and comparing each such sampled pixel with a plurality of threshold values which are representative of eye color defects to identify possible eye color defective pixels;</li><li>c) segmenting the identified possible eye color defect pixels into one or more spatially contiguous groups;</li><li>d) calculating a first score for each pixel of each segmented group and for each group based upon a plurality of features including group size, group shape, coloration, and brightness to identify eye color defect group candidates;</li><li>e) selecting a seed pixel based on its score from each identified eye color defect group candidate and determining all the neighboring pixels which are within a predetermined score range of their neighboring pixels and those pixels in a group which represent a significant pixel score transition so that the determined transitions identify the outer boundary of a eye color defect group candidate; and</li><li>f) calculating a second score for each pixel for each eye color defect group candidate based on a plurality of features including group size, group shape, coloration, and brightness to determine an eye color defect group.</li></ul>

0007The method used by the present invention maintains the '789 patent criterion of recoloration without destroying the region's luma fluctuation. However, the present invention automatically supplies two of the three inputs necessary to perform the disclosure of the '789 patent. Only the general region of interest is required at the beginning of the present invention as opposed to the more precise region requirements of the '789 patent. Also note that the present invention divides each pupil into three pixel categories: (1) body pixels, (2) border pixels, and (3) glint pixels. Each of these pixel types is treated differently in order to create a more natural appearing correction. Furthermore the image resolution from which the region of interest was obtained does not necessarily need to be the resolution at which the present invention corrects.

ADVANTAGES

0008The present invention is effective to detect eye color defects due to flash illumination and has the advantages of: <ul id="ul0002" list-style="none"><li>(1) minimizing operator intervention,</li><li>(2) achieving more accurate eye color defect corrections than was heretofore possible,</li><li>(3) allowing for eye color defects to be detected at one image resolution while the correction process takes place in another image resolution, and</li><li>(4) sub-dividing the eye color defect pixels into three categories (body, border, and glint) in order to render a more natural appearing eye.</li></ul>

BRIEF DESCRIPTION OF THE DRAWINGS

0009<ul id="ul0003" list-style="none"><li>Figure 1 illustrates a system in which the present invention is embodied;</li><li>Figure 2 illustrates a top level flow diagram of certain aspects of the present invention;</li><li>Figure 3 illustrates a detailed flow diagram of the detection phase of Figure 2;</li><li>Figure 4 illustrates a detailed flow diagram of the fix phase of Figure 2;</li><li>Figure 5 illustrates the hue, lightness, and saturation space which is used in accordance with the present invention;</li><li>Figures 6a-6c illustrate the Hue, Lightness, Saturation trapezoidal scoring used in the First Scoring stage 230 of Figure 3 and in the Second Scoring stage 250 shown in Figure 3;</li><li>Figure 7 illustrates Area trapezoidal scoring used in the present invention;</li><li>Figures 8a and 8b illustrate 45° trapezoidal scoring used in the present invention;</li><li>Figure 9 illustrates an example of the scaling up method shown in the Correcting stage 380 shown in Figure 4;</li><li>Figure 10 illustrates an example of the scaling down method outlined in the Correcting stage 380 of Figure 4; and</li><li>Figure 11 illustrates an example eye color defect whereby each pixel of the eye color defect is deemed as either a: body pixel, border pixel, or glint pixel.</li></ul>

DETAILED DESCRIPTION

0010Referring to Figure 1, the present invention is implemented using a digitizing scanner 10, a control and logic device 24, such as a computer with a display device 26, and an optical disc writer 36. As shown, a strip of film 15, containing one or more frames 18 of developed film, is placed into a scan gate 12 where the strip of film 15 is scanned under direction of control and logic circuitry 30. As each frame 18 is scanned the resultant image data, represented by block 22, is digitized and transmitted to a memory 28 for storage. The computer 24 process the stored data, in a manner to be described, to provide output image data 32 which may be written to an optical disc 34 by the optical disc writer 36 to provide a report as to the characteristics of the anomalies. The digitized scanner 10 is capable of quantizing pixel values into multiple brightness levels in separate red, green, and blue channels. A minimum number of brightness levels would be approximately 64 for an adequate quality image with a typical number being 256. Although the image data 32 has been described as originating from the operation of scanning film, it is well understood that other well known techniques may be used to provide the image data.

0011The computer 24 operates the present invention. Referring now to Figure 2, this invention can be broken down into two distinct phases: (1) the detection phase 200 and (2) the fix phase 300. The detection phase 200 can be broken down into five distinct stages (see Figure 3): (1) identification of eye color defect candidate pixels 210, (2) segmentation 220, (3) first scoring 230, (4) region growth (or pixel score transition identification) 240, and (5) second scoring 250. Each stage of the detection phase 200 accesses the results produced by the previous stage creating a data processing chain. The fix phase 300 can be broken down into two sections (see Figure 4): (1) scaling 370 and (2) correcting 380. The resolution section can in turn be broken down into three stages: (1) lower resolution 310, (2) same resolution 320, and (3) higher resolution 330. The correction section can also be broken down into three stages: (1) glint correction 340, (2) body correction 350, and (3) border correction 360.

0012It is important to note the necessity of this data processing chain. In the case of red eye defects if one were simply to assume that all reddish pixels in an image were defects, then numerous non-red eye pixels would be included with the set of true red eye pixels. Red eye is comprised of both color and spatial cues. To depend on one, but not the other set of cues, will produce incorrect results. It is the building up of clues, produced by each stage in the data processing chain, which allows the present invention to discern between red eye and non-red eye pixels.

0013What makes red eye so noticeable and distracting to a viewer is the concentration of red elements (e.g., pixels on a CRT) surrounded by non-red elements. An elements' coloration is determined by its combination of the red, green, and blue characterizing values. Therefore, one could conclude that the elements which comprise a red eye region contain more red than green or blue. In fact, experimental results show red eye pixels to observe, on average, a 1.7:1 red to maximum (green, blue) intensity ratio in the video gamma metric. By increasing/decreasing this ratio the invention decreases/increases its sensitivity to red.

0014By converting an element's RGB values to HLS (hue, lightness, and saturation) space, see Figure 5, one can derive the kind of red observed in flash illuminated human eyes. The following derived values are those used in an existing implementation, but may be adjusted to modify the sensitivity of the present invention:    700 ≦ Hue ≦ 1010    40 ≦ Luma ≦ 166    65 ≦ Saturation ≦ 256    Therefore the ratio and the 3-dimensional HLS region comprise the criteria used in the first stage of the present invention. Any pixel in the given image which adheres to these criteria is represented as a one in a pre-zeroed out bit map, the color bit map. A bit map is a section of memory which holds ones or zeros. This binary data can represent many things depending on the program which interprets it. In the present invention, the bit maps represent pixels which are eye color defect pixel candidates. Since these maps use only a single bit to represent a piece of data, this data structure can save vast amounts of physical memory. Thus, at the end of this stage only those pixels which pass the above criteria are represented in the color bit map. For a detailed discussion of hue, lightness, and saturation space see Computer Graphics: A Quarterly Report of SIGGRAPH--ACM, Vol. 13, No. 3, Aug. 1979, pp. III - 37 &amp; 38.

0015Up to this stage the present invention has been working on individual pixels; eliminating those which did not meet the Identification of Eye Color Defect Candidate Pixels stage 210 criteria in Figure 3. It is now time to group these pixels into spatially contiguous groups, termed segments.

0016The process begins by raster scanning the color bit map until a non-zeroed bit is encountered. This bit is the seed bit. Once found, the seed bit is set to one in the pre-zeroed marked bit map. Next, the segmentor enters a loop which terminates when no bits are "on" in the marked bit map. The first step of the loop is to zero out the current bit in the color bit map. Next, a function is called which searches (in 8-connected fashion) around the current bit in the color bit map for "on" bits. As "on" bits are found, they are placed into the marked bit map if and only if they are not also "on" in the seed bit map. Once all 8-connected "on" bits have been found, the function returns to the segmentor loop. The next step of the loop is to zero out the current bit in the marked bit map and turn "on" the current bit in the seed bit map. Finally, a function is called which searches the marked bit map for the top left non-zeroed bit. This bit now becomes the current bit and the loop cycles again. Eventually the segmentor loop terminates. At this point each segment is validated based on area and shape. Specifically, there are two criteria, eccentricity and number of pixels. The eccentricity of a segment must be greater than a minimum eccentricity and less than a maximum eccentricity, where 0.0 is perfectly round and 1.0 is maximally elongated (i.e., a line). This range of eccentricity values eliminates linear segment types (i.e., pupils are roundish). See Appendix A for the current equations used to implement an eccentricity value. A segment must contain a predetermined minimum and maximum area (in pixels). A segment with fewer than the minimum number of pixels is generally indistinguishable from other image objects (e.g., a patch of skin). If validated, then this segment is entered into the classmap bit map. The zeroing out of the seed bit map ends this part of the segmentor. Before continuing, it is crucial that the reader understand that only two of the four bit maps, the color and classmap bit maps, could currently contain "on" bits. The color bit map might contain "on" bits which belong to other segments, and the classmap bit map can only contain those segments previously found and the current segment.

0017Lastly, the raster scan of the color bit map continues. When the next non-zeroed bit in the color bit map is encountered it is designated as the seed bit and the process begins anew. This continues until there are no "on" bits in the color bit map.

0018As a segment is classified, two tasks are performed: (1) insertion of the new segment into the classmap bit map and (2) compilation of data on the segment is accumulated. This data includes eccentricity, a measure of a segment's circular nature; the number of pixels contained within the segment (i.e., area); the segment's score; the best pixel score (i.e., the largest pixel score occurring in the segment); the best pixel's coordinates; and the coordinates of the segment's centroid. Each segment found has its corresponding statistics saved so that the following stages may access them.

Scoring

: (see Figure 3)

0019A continuous-weighting approach to scoring a pixel is taken in the present invention. Various criteria (hue, lightness, saturation, and the ratio test) are taken into consideration and based upon them an eye color defect score is given. Scores range from zero to one, inclusive.

0020In the present invention a pixel is scored based on its HLS values and whether or not the pixel passes the ratio criterion (i.e., a bi-value score). Each pixel in an image contains a hue, lightness, and saturation value. Given these values a score for each of these channels can be calculated (score_hue, score_lightness, and score_saturation). These scores are produced based on the information presented in Figures 6a-6c. A score for a given channel value equals the corresponding trapezoidal weighting function for that value. Next read the score off the y-axis. For example, if a given pixel has the following HLS values:    H = 73,    L = 75,    S = 68, then the corresponding scores would be:    score_hue = 0.5    score_lightness = 1.0    score_saturation = 0.032. In pseudo-code, a score is calculated by:    if (value_p < value₁) then    score = 0.0    else if(value_p > value₄) then    score = 0.0    else if(value₁ ≦ value_p < value₂) then    score = (value_p - value₁)/(value₂ - value₁)    else if(value₃ < value_p ≦ value₄) then    score = (value_p - value₄)/(value₃ - value₄);    where value_p is the channel (hue, lightness, or saturation) of the pixel in question, value₁ represents the first point of the trapezoid (h1, l1, or s1), value₂ represents the second point (h2, l2, or s2), value₃ represents the third point (h3, l3, or s3), and value₄ represents the fourth point (h4, l4, or s4). Lastly, these three scores are multiplied together producing a final pixel score ranging from 0.0 to 1.0, inclusive.

0021The purpose for multiplying individual channel scores together is so that if a pixel fails a channel test (falls outside the trapezoidal region), then that pixel will receive an overall score of zero (i.e., not a eye color defect candidate). Also, a very large score in one channel can partially compensate for low--but acceptable--scores in the other channels.

0022A segment's score is determined by calculating the average score of the pixels contained within it.

0023The Region Growth stage 240 is a process for cleaning up segments by eliminating questionable sub-regions which passed the color threshold tests but appear to have unlikely spatial variations.

0024Digital imaging region growth is a method by which pixels are annexed to a region's already existing pixels. This is analogous to the growth of crystals. For a crystal to begin growing, a piece of dust (or some other material) must exist. Then, as a solution is introduced, some of the dissolved particles precipitate out of solution and begin forming the crystal structure. Growth ends when the particles in the solution drop below a certain concentration. In a similar way, the growth of a digital region begins with a supplied seed pixel and ends when the connected pixels no longer meet the defined criteria of similarity. A segment's seed pixel is obtained during the Segmentation stage 220. This pixel is designated as the coordinates of the best pixel in a given segment.

0025To start, the Region Growth stage 240 loops through each segment found in the Segmentation stage 220. As described above, each segment contains a best pixel. This pixel is the seed pixel. The method searches (in an 8-connected pattern) around the current pixel and locates all pixels which have scores that are:    score_{current pixel} - 0.5 ≦ score_{neighboring pixel}    score_{neighboring pixel} ≧ score_{current segment}    Those neighboring pixels which pass one or both of the above two criteria are annexed to the growing region. Only those pixels which were part of the segment, after the Segmentation stage 220, are considered during this stage. This process of annexing pixels continues for each segment until no old segment pixels are left to be verified.

0026Since the resultant segments from this stage may differ from those of the Segmentation stage 220 (i.e., pixels may have been dropped from the segment's make up), new segment statistics and scores are updated 250.

0027At this point there is nothing more to do than assume that the segment with the best score is an eye color defect, termed the primary eye (or primary eye segment). If more than one eye is expected in the image window, then an additional search is conducted for other eye color defects, termed secondary eyes (or secondary eye segments). Based on the primary eye segment's area (or number of pixels) and the 45° criteria, a new score is calculated for the other defective eye segment candidates. [The 45° criteria mandates that the secondary eye must be located somewhere within ± 45° of the horizontal, which runs through the centroid of the primary eye (see Figures 8a and 8b). Any segments which are not in this area are given scores of zero (i.e., are not considered to be secondary eye candidates).] The area score (score_area) is determined based on the triangular weighting function presented in Figure 7. As with the previous scoring methods, the area scores range from 0.0 to 1.0, inclusive. This score_area and the score₄₅ are multiplied to the score of the segment in question, in order to arrive at the segment's new score. The segment with the top remaining score is assumed to be the secondary eye.

0028A very important feature of the present invention centers around the fix phase 300 and its flexibility. By this phase the classmap bit map should contain the eye color defects within the image. Now, the invention must replace each eye color defect with a natural appearing pupil. To accomplish this rendering two important issues must be investigated: (1) scaling 370, and (2) correcting 380.

Scaling:

(see Figure 4, 370).

0029The flexibility alluded to above involves the interdependencies of the detection phase 200 with the fix phase 300. One might wish to perform the detection phase 200 in some image resolution, but perform the fix phase 300 in another. To account for this flexibility, the Scaling section 370, in Figure 4, is subdivided into three sections: (1) fixing at the same resolution 320 as detection, (2) fixing at a higher resolution 330, and (3) fixing at a lower resolution 310. Each of these sections is handled differently. To fix at the same resolution 320 requires no added classmap bit map handling. All that is needed is to correct each pixel which is represented in the classmap bit map (see Correcting below). To fix at higher or lower resolutions requires the creation of a new bit map, the scaledClassMap.

0030The problem when correcting at a higher resolution 330, is that each pixel in the classmap actually has contributions from several pixels at the higher resolution. Some of these pixels may be eye color defect pixels, but others may not. Thus, a refined eye color defect selection process must be performed at the higher resolution.

0031The process of fixing an image at a higher resolution entails the formation of a scaled up version of the classmap bit map. The first step of the process is to pass the scaled version of the original image (the image which the detection phase 200 worked on) to the Identification of Eye Color Defect Candidate Pixels stage 210. This stage returns a scaledColor bit map. Next, each segment contained within the classmap bit map is examined. As each segment is encountered its best pixel's coordinates are scaled up by the appropriate x-/y-scale factors. In theory these coordinates will be at most ± the x-/y-scale factor number of coordinates away from the original coordinates multiplied by their scale factor value, respectively. For example, if an image contained one eye color defect and the present invention correctly detected it, then the classmap bit map shown in the upper left-hand corner of Figure 9 would be the result. Furthermore, if the user requested that the fix phase 300 be performed on the image scaled by 2 (in both the x and y directions), then the scaledColor bit map shown in the lower-right corner of Figure 9 would be the result. Figure 9 depicts the bit located at (4, 2) in the classmap has been designated as the best pixel (see Segmentation 220). When these coordinates are multiplied by the respective scale factors (two for both coordinates in this example), the resulting bit is located at (8, 4)--designated in Figure 9 by a 'X'. Unfortunately this bit location is not classified as a eye color defect candidate in the scaledColor bit map. Therefore, a search is undertaken to find the closest eye color defect candidate in the scaledColor bit map. Once found, this location is used as the seed point for the Segmentation stage 220. Finally the Region Growth stage 240 is invoked and a valid class map bit map, the scaledClassMap, is produced. All that is left now is to correct the pixels in the scaled version of the original image which are categorized as eye color defect pixels in the scaledClassMap bit map (see Correction below). The above outlined methodology does not simply scale up the classmap bit map. If one were to replace every bit in the lower resolution with N (where N equals x-scale factor time y-scale factor) number of bits, then the resulting class map, the scaledClassMap, would over-estimate the true number of pixels contained within the eye color defect.

0032A correction at a lower resolution 310 is opposite to a correction in a higher resolution 330 (i.e., each pixel in the lower resolution image contains information based on multiple pixels from the detect phase 200 image). Some of these detect phase 200 image pixels may be classified as eye color defect pixels while others may be classified as non-eye color defect pixels. The correction process here is substantially simpler than for up-scaling since no region growth refinement is needed to produce a more accurate class map.

0033For every NxM (where <maths id="math0001" num=""><math display="inline"><mrow><mtext>N equals the x-scale factor</mtext></mrow></math><img file="EP0635972A2_D0001.tif" /></maths> and <maths id="math0002" num=""><math display="inline"><mrow><mtext>M equals the y-scale factor</mtext></mrow></math><img file="EP0635972A2_D0002.tif" /></maths> ) grouping of pixels in the original detection phase 190 image, there corresponds a single lower resolution pixel. Since each pixel in the NxM pixel grouping is not guaranteed to be a eye color defect pixel, the corresponding lower resolution pixel may not possess the necessary characteristics to be termed a eye color defect candidate pixel by the detection phase 200. This is a problem. For a program to correct only the parts of a lower resolution pixel which are derived from true eye color defect candidates of the original resolution image, correct each lower resolution pixel by a percentage of the full correction. This percentage can be derived by knowing the number of eye color defect candidates contained within each NxM grouping of original image pixels. Figure 10 shows a classmap bit map and its corresponding scaledClassMap bit map. Again, to simply scale each bit in the classmap by the corresponding x-/y-scale factors to arrive at the scaledClassMap would over-estimate the number of pixels contained within an eye color defect. Furthermore, these pixels would be over corrected.

Correcting:

(see Figure 4, 380).

0034Pupils which exhibit the red eye phenomenon differ from normal pupils in that they are reddish in hue (rather than neutral), and are brighter. Correction is generally accomplished by removing a pixel's chromaticity and darkening its luminance. To perform this task, a given pixel's gamma RGB values are converted to YCC values. [YCC space is a simple translation of RGB space. To transform an image in RGB space to YCC space, multiply each pixel by the following matrix:<maths id="math0003" num=""><img file="EP0635972A2_D0003.tif" /></maths> where R, G, and B represent the gamma-metric red, green, and blue coordinates of a given pixel, and Y, C1, and C2, represent the luminance, chroma-channel 1, and chroma-channel 2 coordinates of the pixel in YCC space. The gamma RGB and the YCC color metrics are described in the KODAK PhotoCD Products: A Planning Guide for Developers, Eastman Kodak Company, 1992 (part no. DCI200R).] Next, both chroma channels are zeroed out (i.e., only the pixel's neutral value is left). At this point, the luminance channel is multiplied by a factor of 0.35 in order to reduce the lightness of the pixel's neutral value. (In general, a red eye has an unusually high luminance value due to the over abundance of light produced by the flash of the camera which illuminates the retina. Thus, upon correction, a reduction of this high luminance value is required. This factor, 0.35, is based upon experimental evidence and other values may result in natural renderings.) Finally, the YCC values are converted back to gamma RGB values, and set as the pixel's values. The above procedure describes Body correction 350. This is the method by which body pixels--pixels which are 8-connected only to eye color defect pixels--are desaturated (see Figure 11). Border correction 360 is performed on border pixels, pixels which are 8-connected to at least one non-eye color defect pixel and to at least one eye color defect pixel. Such pixels are only darkened by a 0.15 factor. Furthermore, those pixels which are considered to be associated with the glints of a eye color defect are sometimes found to contain subtle red hues. Those pixels which: (1) are not eye color defect pixels, (2) are within 40% of the pupil's calculated radius from the pupil's centroid, and (3) have hue values which range from 600 and 1100, inclusive, are termed glint pixels. To perform Glint correction 340, the chroma channels of glint pixels are zeroed out, while their luminance is left unchanged.

0035This invention has been described with reference to correcting "red eye" defects, but those skilled in the art will recognize that it is also applicable for correcting for eye color defects in animals, but that different detection and correction values specific to the subject's defective color should be used. Moreover, although two specific color spaces have been used, others will suggest themselves to those skilled in the art.

PARTS LIST

0036<dl id="dl0001"><dt>10</dt><dd>digitized scanner</dd><dt>12</dt><dd>scan gate</dd><dt>15</dt><dd>film</dd><dt>18</dt><dd>frames</dd><dt>22</dt><dd>block</dd><dt>24</dt><dd>control &amp; logic device (computer)</dd><dt>26</dt><dd>display device</dd><dt>28</dt><dd>memory</dd><dt>30</dt><dd>logic circuitry</dd><dt>32</dt><dd>image data</dd><dt>34</dt><dd>optical disc</dd><dt>36</dt><dd>disc writer</dd><dt>200</dt><dd>detection phase</dd><dt>210</dt><dd>defect candidate pixels</dd><dt>220</dt><dd>segementation stage</dd><dt>230</dt><dd>first scoring stage</dd><dt>240</dt><dd>region growth stage</dd><dt>250</dt><dd>second scoring</dd><dt>300</dt><dd>fix phase</dd><dt>310</dt><dd>lower resolution</dd><dt>320</dt><dd>same resolution</dd><dt>330</dt><dd>higher resolution</dd><dt>340</dt><dd>glint correction</dd><dt>350</dt><dd>body correction</dd><dt>360</dt><dd>border correction</dd><dt>370</dt><dd>scaling logic</dd><dt>380</dt><dd>correcting logic</dd></dl>