2. Description of Background Art In flash photography, the"red-eye effect"is a well known problem. The"red-eye effect"is at least one red dot appearing in the pupil of an eye image. One conventional technique to reduce the red-eye effect is to use a pre-flash light emission technique. In the pre-flash light emission technique, when a shutter release button is pressed, a pre-flash is fired. When the pre-flash strikes a subject\'s eyes, the pupils of the subject\'s eyes shrink in response to the bright light. Subsequently, within a short time, the primary flash fires before the pupils revert to normal size. Thereby, the red dots of the pupils are reduced due to the smaller size of the pupils. For a description of a suitable pre-flash light emission technique, see for example, U. S. Patent 4,285,588 to Kodak.

One drawback to the pre-flash light emission technique is the picture taken is not that desired because of a time delay between the desired shutter release time and the time of actual shutter release. Another drawback to the pre- flash light emission technique is the pre-flash distorts the intended picture by, for example, shrinking the

subject\'s pupils. Still another drawback to the pre-flash light emission technique is when the subject is not looking at the camera, the subject\'s eyes do not react to the pre- flash, and conventional technique does not prevent red-eye.

Thus what is needed is an apparatus and method that eliminates the red-eye effect but does not distort the subject image.

Disclosure of Invention The present invention includes a computer implemented method for identifying and correcting red-eyes. The method includes the acts of determining the presence of a red colored region (620); determining whether an eye image surrounds the red colored region (410,420,430,440,450, and 630); and replacing the color of the red colored region with a color of a region that immediately surrounds the red colored region (510,520,530, and 640).

The present invention further includes a computer system (100) adapted for locating and modifying a red-eye in a first image, the system including: a storage medium (102) for storing the first image (110) that includes a red dot and at least one eye image; a red dot detector (104) coupled to the storage medium for receiving the first image from the storage medium and for detecting the presence of the red dot within the first image and for identifying the red dot; an eye detector (106) coupled to the red dot detector for receiving the identified red dot from the red dot detector (104) and for determining whether the red dot is positioned within an eye image and for outputting the location of the red dot positioned within the eye image; and a red-eye remover (108) coupled to the eye detector for receiving the location of the red dot positioned within the

eye image and for replacing the color of the red dot positioned within the eye image with the color of the region that immediately surrounds the red dot.

Brief Description of the Drawings These and other more detailed and specific objects and features of the present invention are more fully disclosed in the following specification, reference being had to the accompanying drawings, in which: FIG. 1A depicts in block diagram form an exemplary embodiment of red-eye correction device 100; FIG. 1B depicts in block diagram form an exemplary embodiment of eye detector 106 of red-eye correction device 100; FIG. 1C depicts in block diagram form an exemplary embodiment of red-eye remover 108 of red-eye correction device 100; FIG. 2 depicts an exemplary image 110 having multiple red dots 202-1 to 202-5; FIG. 3A depicts a suitable process 300 to identify red dots; FIG. 3B depicts a suitable process to determine whether a red area is circular; FIG. 4 depicts a suitable process 400 to determine whether a red dot is spatially enclosed within an eye image; FIG. 5 depicts a suitable process 500, in accordance with an embodiment of the present invention; and FIG. 6 depicts a suitable process 600, in accordance with an embodiment of the present invention.

Detailed Description of the Preferred Embodiments

Embodiments of the present invention can be used in conjunction with any image recording device, such as a camera (e. g., digital or non-digital), or in an environment that processes still images (e. g., photo development minilabs or internet based photo processing services).

Additionally, embodiments of the present invention can be used in conjunction with any video recording device, as video may be a series of still images.

In accordance with embodiments of the present invention, at least an apparatus and process are disclosed herein that locate a red dot within an eye image and replace the red dot with the color of the pupil or iris that encapsulates the red dot. Hereafter"red-eye"means a red dot located within an eye image. Thereby, the red-eye effect is corrected without need for an image distorting pre-flash.

FIG. 1A depicts in block diagram form an exemplary embodiment of red-eye correction device 100. Red-eye correction device 100 can be implemented in hardware, software, and/or firmware. Red-eye correction device 100 includes a storage medium 102, red dot detector device 104, eye detector 106, and red-eye remover 108.

Suitable implementations of storage medium 102 are a random access memory (RAM), magnetic or optical storage medium, or allocated memory space. For example, when the red-eye correction device 100 is used in conjunction with a camera, an exemplary storage medium 102 is a flash memory such as the Iomega Click or the IBM microdisk. Storage medium 102 stores an image 110, which, in this embodiment, is represented in conventional red-green-blue (RGB) format.

In this example, the image 110 represents a still image that includes at least one red-eye. Herein, image 110 is

also an image represented by the image 110 unless otherwise stated. FIG. 2 depicts an example image 200, represented by the image 110, that includes multiple red dots 202-1 to 202-5.

The storage medium 102 is coupled to provide the image 110 to red dot detector device 104. Red dot detector device 104 detects all red colored approximately circular shaped regions ("red dots") in image 110. An exemplary approach to identify red dots in image 110 is provided as process 300 of FIG. 3A.

In action 310 of process 300, an area A having N red pixels is identified by using a classical component algorithm whereby all pixels of area A, {(xl, yl), (x2, y2), ..., (xn, yn)}, such that each pixel (xi, yi) is an"8- neighbor"of at least another pixel (xj, yj) of area A. Two pixels (xi, yi) and (xj, yj) are"8-neighbors"if |xi-xj|< =l and |yi-yj|< =l. The area A is built by starting from a red pixel (xl, yl) and using a classical connected component algorithm to build the area A which contains (xl, yl).

In action 320, the red dot detector device 104 determines if the shape of the area A of red pixels is circular. One suitable technique to determine whether the area A is circular is shown in FIG. 3B.

In action 320-1 of FIG. 3B, red dot detector device 104 determines the centroid (xg, yg) of area A using a conventional calculation such as: xg = 1/N * (xl+x2+... +xN) and yg = 1/N * (yl+y2+... +yN).

In action 320-2, red dot detector device 104 encloses the area A with bounding box B to determine the compacity C and excentricity E of the area A. The compacity C of area A is defined as the ratio of the number of pixels N and the

area of the bounding box B, areaB, as further defined in the following equation: C = N/areaB, where areaB = H*L, where H = yr-yl+1, L = xr-xl+1, where (xl, yl) are the upper left hand coordinates of the bounding box B and are obtained by xl = min (xl, x2... xN) and yl = min (yl, y2... yN); and (xr, yr) are the lower right hand coordinates of the bounding box B and are obtained by xr = max (xl, x2... xN) and = max (yl, y2... yN); The excentricity E of the area A is defined as the ratio of the short side of bounding box B with the ratio of the long side of bounding box B. The following equation defines the excentricity E: E = min (H, L)/max (H, L).

In action 320-3, the red dot detector device 104 uses the compacity C and excentricity E to determine if the area A is circular. In this embodiment, if any of the following conditions are true, area A is circular: i. (N < minpixel) OR ii. (N > minpixel) and (N < maxpixel) and (C > mincompact) and (E > minexcentricity) where minpixel is a threshold under which the area A is too small and therefore is accepted as red dot. A typical value of minpixel is 20;

maxpixel is a threshold above which the area A is rejected as red dot because it is too big. For example, maxpixel can be fixed to the quarter or full size of the image; mincompact is a threshold under which the area A is rejected because it is too compact. Setting mincompact to 0 cancels this test. Setting mincompact to 1.0 makes the red dot detector device 104 very selective about the compacity; and minexcentricity is a threshold under which the area A is rejected because it is too elongated.

Setting minexcentricity to 0 cancels this test.

Setting minexcentricity to 1.0 makes the red dot detector device 104 very selective about the excentricy.

For a 10 cm by 14.9 cm photograph that includes one or several persons, typically, minpixel = 40, maxpixel = 1000, mincompact = 0.3, and minexcentricity = 0. 3.

The red dot detector device 104 then identifies all red dots in image 110 to the eye detector 106. An exemplary manner to identify each red dot is to identify the coordinates of each pixel within a red dot, as well as the following proprerties of the red dot: 1) compacity C, 2) excentricity E, 3) centroid (xg, yg), and 4) radius rd of the minimum circle which englobes the red dot. The radius rd is the largest distance linking the centroid (xg, yg) to each point (xi, yi) within the red dot and is further defined in the following equation: rd = max (d ( (xg, yg), (xi, yi))), I = 1 to N where the function d () is the euclidean distance between two points.

Thus with respect to the example of FIG. 2, red dot detector device 104 identifies red dots 202-1 to 202-5 to eye detector 106.

Eye detector 106 detects whether each red dot identified by the red dot detector device 104 is spatially enclosed within an eye image. One suitable approach performed by eye detector 106 to determine whether a red dot is spatially enclosed within an eye image is described with respect to process 400 of FIG. 4. Process 400 is repeated for each red dot.

In action 410 of process 400, the eye detector 106 extends a ray from the centroid (xg, yg) to determine whether a first homogeneously colored circular region encapsulates the red dot. In one embodiment, the first homogeneously colored circular region corresponds to the pupil. For example, referring to the image 200 of FIG. 2, region 220 corresponds to a first homogeneously colored circular region. If a first homogeneously colored circular region encapsulates the red dot, then in action 420, the eye detector 106 locates the center of the first homogeneously colored circular region (x*, y*). For example, referring to the image 200 of FIG. 2, point 225 corresponds to the center of the first homogeneously colored circular region. Otherwise, the eye detector 106 determines that the red dot is not a"red-eye".

In action 430, the eye detector 106 determines whether to locate a second homogeneously colored circular region.

In this embodiment, the eye detector 106 locates a second homogeneously colored circular region by examining the size of the red dot. If the size of the red dot is sufficiently small, the eye detector 106 presumes that the first homogeneously colored circular region does not correspond

to a pupil image because the pupil will not be resolved.

The eye detector 106 identifies the first homogeneously colored circular region as an iris and proceeds to action 450. Otherwise, if the size of the red dot is sufficiently large such as in the example of FIG. 2, the eye detector 106 identifies the first homogeneously colored circular region as a pupil and proceeds to action 440.

In action 440, the eye detector 106 seeks a second homogeneously colored circular region by extending a second ray from the center (x*, y*) of the first homogeneously colored circular region. The second homogeneously colored circular region corresponds to an iris. For example, referring to the image 200 of FIG. 2, region 230 corresponds to a second homogeneously colored circular region. If such second homogeneously colored circular region is located, then action 450 follows.

In action 450, the eye detector 106 extends the second ray from the center (x*, y*) of the first homogeneously colored circular region or from the edge of the first homogeneously colored circular region (action 440) to locate a region that is brighter than the homogeneously colored region outmost from the red dot (e. g., first homogeneously colored circular region or second homogeneously colored circular region) ("middle region").

The brighter region corresponds to the sclera. For example, referring to the image 200 of FIG. 2, region 240 corresponds to the brighter region. If the region that surrounds the middle region is brighter than the middle region, then in action 460, eye detector 106 identifies the red dot as a"red-eye".

Otherwise, if the region that surrounds the middle region is not brighter than the middle region, then eye

detector 106 determines that the red dot is not a"red- eye".

FIG. 1B depicts in block diagram form an exemplary embodiment of eye detector 106 of red-eye correction device 100. Eye detector 106 includes first homogeneous region detector 152 that performs the actions 410,420, and 430 of process 400; second homogeneous region detector 154 that performs action 440 of process 400; and brightness detector 156 that performs action 450 of process 400.

Numerous alternatives to process 400 are available.

For example, one alternative to process 400 is described in U. S. Patent No. 5,164,992 to Massachusetts Institute of Technology, which is incorporated by reference herein in its entirety.

After repeating process 400 for all red dots within image 110, the eye detector 106 identifies all red-eyes within the image 110 to the red-eye remover 108. A suitable manner that eye detector 106 identifies red-eyes to the red-eye remover 108 is by providing : 1) the coordinates of each pixel within a red-eye, 2) the center coordinates (x*, y*) of the first homogeneously colored circular region (e. g., pupil or an iris), and 3) a ray r* defining the radius of the first homogeneously colored circular region. The red-eye remover 108 further receives the image 110 from the storage medium 102.

FIG. 5 depicts a suitable process 500 performed by the red-eye remover 108 for correcting the color of each red- eye. In action 510 of process 500, the red-eye remover 108 determines the color of the first homogeneously colored circular region (i. e., pupil or iris). One suitable technique to determine the color of the first homogeneously colored circular region that surrounds a red-eye is as

follows. The red-eye remover 108 determines the mean color of all pixels within the first homogeneously colored circular region. In this embodiment, the mean color is determined in terms of colors red, green, and blue (RGB).

In action 520, the red-eye remover 108 replaces the red, green, and blue color components of the red-eye in image 110 with the respective mean red, green, and blue colors of the first homogeneously colored circular region. Hereafter "modified image"means the image 110 having the red-eyes modified by action 520. In action 530, the red-eye remover 108 stores the modified version of image 110 to the storage medium 102.

FIG. 1C depicts in block diagram form an exemplary embodiment of red-eye remover 108 of red-eye correction device 100. Red-eye remover 108 includes a color detector 170 that performs action 510 of process 500; and color replacer 172 that performs actions 520 and 530 of process 500.

Suitable process Accordingly, a suitable process in accordance with an embodiment of the present invention is represented in FIG.

6 as process 600. In action 610 of process 600, a digital image 110 is available in RGB format. In action 620, red dots within the digital image are detected and identified.

In action 630, each red dot is examined to determine whether it is a red-eye. An exemplary action 630 is process 400 or its alternate described earlier. In action 640, the color of each red-eye in image 110 is replaced with the mean color of the first homogeneously colored circular region (i. e., iris or pupil). An exemplary action 640 is process 500 described earlier.

Modifications The above description is included to illustrate the operation of the preferred embodiments and is not meant to limit the scope of the invention. For example, non-red colored-eye image distortions can be modified. The scope of the invention is to be limited only by the following claims. From the above discussion, many variations will be apparent to one skilled in the art that would yet be encompassed by the spirit and scope of the present invention.

What is claimed is: