CROSS REFERENCE TO RELATED APPLICATIONS

This application is a continuation-in-part of Ser. No. 09/823,139 now U.S. Pat. No. 6,751,348 B2 Filed Mar. 29, 2001 titled â€œAutomated Detection of Pornographic Imagesâ€ .

FIELD OF THE INVENTION

The present invention relates to digital image processing, and more particularly to a method and apparatus for detecting and correcting red-eye defects in a digital image thereby reducing or eliminating the need for user intervention.

BRIEF DESCRIPTION OF THE PRIOR ART

As is well known, photographing a person in a relatively dark environment requires the use of a photographic flash to avoid under-exposure. However, a known artifact of such images is the appearance of a strong red circle instead of the eyes, also termed as â€œred-eyeâ€ . There are three main reasons for this artifact: 1) the proximity of the flash bulb to the lens; 2) the fact that if flash was needed, most likely the light was dim, and therefore the pupils of the eyes are naturally dilated. In addition, the physiology and anatomy of the eye, as illustrated in

FIG. 1

plays an important role. 3) The fact that the eyes include a transparent lens 100 and medium 102 (Vitreous humor), and therefore light can penetrate and be reflected easily. Moreover, in the case of a light color iris 104, such as blue or green eyes, the red-eye effect, because of the transparent nature of light iris, is even more exaggerated than merely on the pupil 106, and manifest itself on the whole Iris 104. Physiologically, as the amount of light entering the eye diminishes, such as in a dark room or at night, the iris dilator muscle, which runs radially through the iris like spokes on a wheel, pulls away from the center, causing the pupil to â€œdilateâ€ and allowing more light to reach the retina. When too much light is entering the eye, the iris sphincter muscle, which encircles the pupil, pulls toward the center, causing the pupil to â€œconstrictâ€ , allowing less light to reach the retina.

Red-eye effect happens when the internal blood vessels of the eye located inside the eyeball in the retina region or the middle or vascular tunic retro-reflect their red color. This is probably the most common defect in pictures processed from amateur and consumer photography. Redeye is a less noticeable artifact for professional photographers who usually implement a lighting system where the lens and the flash are distant to each other either by using a bracket to displace the flash or by using an external remote lighting system.

With the advance of image processing technologies, it is now possible to digitize an image and store the digitized image in a computer system. This is typically done either using a digital camera to capture the image digitally, or using a scanner that converts the image into digital form. The digital image includes data representing image pixels arranged in a grid format. The data of the digital image are then stored in the computer. The digital image can be retrieved for display and can also be digitally altered in the computer. Note that almost all modern photographic printing machines, including those that are based on traditional negative to silver-halide paper, or otherwise termed analog printing, now digitize an image prior to printing. As red-eye defects are the most common picture defect in consumer photography it is important for photofinishers to make corrections automatically to pictures prior to printing. Further, given the volumes of pictures processed by large photofinishers it is very important that any means for correcting red-eye defects is both fast and accurate.

In addition to storing images on a desktop computer, many users are now looking for alternative means to use and share digital images with friends and family. This may involve sending pictures by e-mail or carrying or these digital assets on removable media or on a hand-held PDA or state-of-art mobile phone. Again, it is of increasing importance for many consumers to have an automatic means of correcting red-eye defects without having to load their pictures onto a desktop computer. Such means must be efficient in terms of computing resources and must still be fast enough on low-end embedded appliances to be practically unnoticeable to an end user.

Several prior art techniques have been proposed to reduce the red-eye effect. A common prior art approach, in the pre-capture stage, is to use multiple flashes in the camera to contract the pupils before a final flash is used to expose and capture the image. However, disadvantages are associated with this prior art approach. Physiologically, the response time to the detection of bright light, in the parasympathic pathways in the pupillary light reflex which provides the command and response of the iris sphincter muscle can take up to a full second before the eye constricts to a daylight pupil size. Therefore, the one disadvantage is the delay between the time when the first flashlight appears and the time when the picture is actually taken. This means the picture is taken at least one second after the exposure button has been pressed. This Eliminates the notion of a decisive moment as detected by the photographer. The subjects may move away from the posed positions before the image is captured. In addition, this technique is inefficient energy wise, with the need for multiple flashes for a single image. It also creates much attention to the photographer, and the photographic process will no longer have any element of surprise to it. Further, this prior art approach cannot solve the red-eye problem in photographs that have already been taken.

A good example of a recent prior art in this field is U.S. Pat. No. 6,134,339 to Luo. Because images can now be captured as or converted into digital images, it is thus possible to correct the red-eye problem in an image digitally. Some prior art schemes have been proposed to correct the red-eye problem digitally.

One such prior art approach as cited in U.S. Pat. No. 6,278,491 to Wang et. al., which is well known to those skilled in the art requires the user to precisely locate the center of a pupil so that a black circle is placed over the red-eye region. One disadvantage is that it cannot automatically detect the red eyes, but rather requires the user intervention to precisely locate the positions of the red pupils. Another disadvantage of this prior art approach is that the red-eye region is often not a circular region. This may cause portions of the red-eye region not to be covered by the black circle. In addition, the black circle may not be able to cover the peripheral area such as the pink ring of the red-eye region. Several related prior art techniques which require user intervention to locate the region of an image where a red-eye defect is located are described by U.S. Pat. No. 6,009,209 to Acker, Bien and Lawton, U.S. Pat. No. 6,016,354 to Lin, et al. and U.S. Pat. No. 6,204,858 to Gupta.

Another public knowledge prior art scheme simply provides the user with means for manually painting over the red eyes digitally. The disadvantage of this prior art scheme is that some kind of painting skill is needed for the user to paint over the red eyes. Another disadvantage is that the correction of the red-eye is not done automatically, but rather manually. Moreover, replacing the red pupil with a complete black circle may also cover the glint in the pupil, which is always there in the case of a flash picture. This glint, as small as it may be, gives a very important and necessary vitality to the eyes. Thus, the result of this type of correction is often quite noticeable and undesirable, and sometimes destroys the natural appearance of the eyes in the image.

Several recent patents such as U.S. Pat. No. 6,009,209 to Acker, Bien and Lawton and U.S. Pat. No. 6,204,858 B1 to Gupta have sought to improve on the manual correction of eye defects by adding semi-automated mechanisms to analyze the areas around an eye and simulate the colors, regional transitions and â€œglintâ€ of the eye. However these techniques are dependent of the eye region being large enough to partition into a number of distinct regions and will only work in a subset of cases. Further, they requite the user to manually select a region around the eye.

Another prior art patent U.S. Pat. No. 5,432,863 to Benati, Gray and Cosgrove describes a user-interactive method for the detection of objects in an image that have the color characteristics of red-eye. This method automatically detects candidate red-eye pixels based on shape, coloration and brightness. However it should be understood that there could be many features in an image, which may be mistaken for red-eye defects. For example, red Christmas tree decorations, cherries or other fruit, clothing with bright red patterns, and so on. Thus prior art methods such as this required user interaction to verify a defect before it could be corrected.

More recently U.S. Pat. No. 6,252,976 to Schildkraut and Gray and U.S. Pat. No. 6,278,491 to Wang and Zhang describe several approaches eliminating user intervention and detecting red-eye defects in a completely automatic manner. These techniques share a common approach of firstly detecting the face regions of persons in a digital image, secondly detecting the eye region in each face and finally determining if red-eye defects exist in the subject's eyes. Both patents adopt quite complex, and thus resource intensive, image processing techniques to detect face and eye regions in an image and subsequently verify the presence of red-eye defects. Further, there are some disadvantages to this approach when two, or more, facial regions overlap or are in close proximity to one another, particularly when a technique is weighted heavily to detect balanced eye-pairs.

In addition to the aforementioned disadvantages, U.S. Pat. No. 6,252,976 to Schildkraut and Gray employ a complex procedure to detect faces and balanced eye-pairs from a skin-map of the image. This task requires several partitioning and re-scaling operations. Significant additional processing of a potential face region of the image then follows in order to determine if a matching pair of eyes is present. Finally, the image pixels in the detected eye regions go through a complex scoring process to determine if a red-eye defect is present. Further, this prior art patent does not propose a means of correcting a red-eye defect after it is detected.

U.S. Pat. No. 6,278,491 to Wang and Zhang makes extensive use of neural network technology in the detection algorithms. Such techniques are well known and are optimized for implementation as a dedicated hardware solution, e.g. as a dedicated ASIC (application specific integrated circuit). Typically, the implementation of a neural network on a conventional computer will require significant memory and computing power. In addition, this patent requires multiple re-scaling and rotations of the original digital images, both tasks increasing significantly the requirements for both computing power and memory storage. Further, Wang and Zhang do not propose a detailed technique for correcting any red-eye defects but only suggest replacing the color of an identified defect pixel with a predetermined color. This step, in turn, suggests that user intervention will be required in any practical embodiment of the invention described in this patent.

Given the above considerations there is need and scope for significant improvements in the automation of both the detection and the correction of red-eye defects in digital images. In particular, there is an obvious need to find a solution that does not require the detailed and recursive processing steps described in these patents in order to detect and locate with a very high degree of probability red-eye defects in a digital image. This is particularly the case for applications where large batches of images must be constantly processed in real time, or in handheld digital appliances such as personal digital assistants or mobile phones where real-time processing of an image must be achieved with limited computing resources.

SUMMARY OF THE INVENTION

The objective of the present invention is to provide an improved means of detecting red-eye defects in digital images thereby reducing or eliminating the need for human intervention

Another objective of this invention is to provide means of correcting such defects to restore the natural color of the eye without requiring human intervention.

A further objective of the present invention is to provide a means for detecting and correcting red-eye defects in digital images, in real time in a digital camera prior to saving the images on in the camera memory.

Yet a further objective of the present invention is to provide a means for activating the needed detection inside digital camera as part of the acquisition process with a trigger that relates to the camera operation such as the existence of flash and the distance of the subject photographed.

An additional objective of the present invention is to provide a means for detecting and correcting red-eye defects in digital images prior to display on a personal digital assistant (PDA), mobile phone, digital camera or similar hand-held digital appliance.

Another objective of the invention is to provide a means of detecting and correcting red-eye defects in large batches of digital images in real-time by implementing a computationally efficient method of performing the above tasks.

The present invention describes an improved means for (i) detecting and (ii) correcting the red-eye defect in a digital image. The detection step comprises the main sub-steps of (a) converting the image into Lab color space; (b) identifying and labeling the potential red-eye segments in the image using a single raster-scan of the image; (c) rejecting potential red-eye segments which have a shape, size, compactness or contrast ratio which are incompatible with a red-eye defect or that are not adjacent to skin patches. Any remaining segments have a very high probability to be red-eye defects and are passed for correction. The correction step comprises the main sub-steps of (a) calculating the histogram of the a component of a segment and its bounding region; (b) calculating the 70% value of the a component in this region; (c) pixels with a value of a greater than this 70% value are truncated to the 70% value; (d) the corrected image is converted from Lab color space back to the original image format.

An advantage of the present invention is to provide a means of correcting red-eye defects which operates uniformly on both pixels which are members of a defect and its bounding region thus avoiding the need to determine individually if pixels in the neighborhood of said defect are members of the defect and to subsequently apply correcting algorithms to such pixels on an individual basis.

An additional advantage in this context is that color artifacts due to the misclassification of the membership of pixels in a defect are avoided, which means that the process of correcting the red eye also acts as a buffer for potential misdetection of pixels.

An advantage of the present invention is that it provides an accurate and automated method of detecting red-eye artifacts in photographs.

A further advantage of the present invention is that it automatically corrects any red-eye defects without requiring human intervention.

Yet another advantage of this invention is that it describes a method of correcting and restoring red eye images to their natural color.

An advantage of the present invention is that it reduces the requirement for recursive image analysis on the entire image performing segmentation and labeling operations in a single raster-scan of the entire image.

A further advantage of the present invention is that it is not limited in its detection of red-eye defects by requirements for clearly defined skin regions matching a human face.

Yet a further advantage of this invention is that it does not require matching symmetrical eye-pairs. Thus it provides for improved detection of defects when face regions are in close proximity (cheek-to-cheek) or are overlapping as may often occur in-group pictures.

A further advantage of the present invention is that it is sufficiently fast and accurate to allow individual images in a batch to be analyzed and corrected in real-time prior to printing.

Yet a further advantage of the present image is that it has a sufficiently low requirement for computing power and memory resources to allow it to be implemented inside digital cameras as part of the processing post-acquisition step.

Yet a further advantage of the present image is that it has a sufficiently low requirement for computing power and memory resources to allow it to be implemented as a computer program on a hand-held personal digital assistant (PDA), mobile phone or other digital appliance suitable for picture display.

An additional advantage in this context is that the invention is sufficiently fast to allow automatic correction of images prior to display especially for appliances that do not provide a screen pointer to allow the selection of a red-eye region for correction.

Yet a further advantage of the present invention is that the red-eye detection and correction process in a digital camera can be activated only when needed based on the acquisition information.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1

illustrates the structure of the human eye with a view to explaining the origin of the red-eye phenomenon in photography;

FIG. 2(a) is a flowchart illustrating the main steps of the detection phase of this invention during which red-eye segments are discovered in the image without user intervention;

FIG. 2(b) is a flowchart illustrating the main steps in the color correction process that is applied to the red-eye segments;

FIG. 3(a) is a diagrammatic representation of the current pixel and the 4-neighbourhood pixels used by the labeling algorithm;

FIG. 3(b) is a flowchart describing the implementation of a single-pass labeling algorithm used in the preferred embodiment to discover and mark potential red-eye segments;

FIG. 4

is a diagrammatic representation of a potential red-eye segment and its bounding region;

FIG. 5

illustrates the process of eliminating potential red-eye defects on the basis of their size;

FIG. 6

illustrates the process of eliminating potential red-eye defects on the basis of excessive segment elongation;

FIG. 7

illustrates the process of eliminating potential red-eye defects on the basis of non-compactness;

FIG. 8

illustrates the process of eliminating potential red-eye defects that do not lie in a region where a sufficient density of skin pixels are present;

FIG. 9

illustrates the process of eliminating potential red-eye defects that do not have a sufficiently high internal contrast level;

FIG. 10

illustrates a typical photographic image featuring a number of typical image components that are almost identical in shape and color to typical red-eye defects; and

FIGS. 11(a), 11(b) and 11(c) illustrate some examples of potential red-eye segments derived from the components of the image in FIG. 10.

DETAILED DESCRIPTION OF THE INVENTION

Briefly, the present invention includes a method and apparatus to (i) detect red-eye defects in a digital image without requiring user intervention and (ii) correct these defects by restoring the original eye color without requiring user intervention.

The detection step comprises the following main sub-steps: (a) the image is converted into Lab color space, whereas an Lab color space, also denoted by L*a*b* in technical publications is a well defined close to uniform Luminance chrominance color space, whereas the â€œLâ€ axis denotes luminance, the â€œaâ€ axis denotes red-green colors and the â€œbâ€ axis denotes the blue-yellow data; (b) the image is segmented and red pixels with the correct luminosity to match red-eye defects are labeled; (c) connected segments are labeled in a single raster-scan of the image; (d) segments with inappropriate areas (too large or too small) are rejected; (e) elongated segments are rejected; (f) non-compact segments are eliminated; (g) segments which are not located in the vicinity of skin patches are eliminated; (h) segments with low contrast are eliminated. At the end of this elimination process any remaining red segments in the image have a very high probability of being red-eye defects.

The correction step comprises the following main steps: (a) a bounding box is defined around the segment and the histogram of the â€œaâ€ component (the red-green axis one of the 3 color components in Lab space) for this box is computed; (b) the 70% value of the â€œaâ€ component is calculated; (c) pixels with a value of the â€œaâ€ component greater that the 70% value are limited to that value; (d) the corrected image is now converted back from Lab color space into its original color space or file format. By limiting the â€œaâ€ component to its 70% value we reduce the red components but retain the other fundamental color components of the eye. Thus, in most instances, the red-eye defect is not only removed, but in fact the eye color is corrected to a color very close to its natural appearance.

In order to identify red eye areas in the image, specific characteristics must be extracted. Red eyes are image areas characterized by:

- a reddish tone;
- a round shape;
- an area that is relatively small with respect to the whole image area;
- compactness, i.e., they do not contain large holes;
- they are located in the neighborhood of skin patches;

Red-eye segments may additionally be characterized by:

- the presence of whitish pixels, associated with the sclera of the eye around the cornea, in close proximity to the segment
- the existence of a relatively high local variation in contrast across the segment
- the existence of a distinctive step increase in the local histogram of the red-color component of the image.

In the following description of a preferred embodiment of the present invention it is assumed that the invention is implemented as a computer program on a standard desktop PC. However, as will be apparent to those skilled in the art, the same invention could equally well be implemented as a client-server application to operate over a networked computer environment, or as an electronic sub-system in a dedicated photo-finishing apparatus. Similarly, we will assume that the digital image is available on the hard disk of the desktop computer in a common file format known as RGB bitmap. However it will be apparent to those skilled in the art that the image data may equally well be stored on some removable digital media such as CD or compact flash memory card, or located on a remote computer or data store and available to the desktop computer over a computer network. It will also be apparent that the image may be stored in a multitude of differing digital data formats.

The present invention can be separated into two main functional steps. The first step is the process of detecting and labeling any potential red-eye segments in a digital image. The second step is the process of correcting the color of any such segments to remove the excessive redness while preserving the original color of the eye segment.

FIG. 2(a) describes the first of these steps. Each step described in the FIG. 2(a) overview of the detection process is further expanded in the following figures. Thus FIG. 3(a) and 3(b) describe step 203 in greater detail;

FIG. 5

describes step 204;

FIG. 6

describes step 205;

FIG. 7

describes step 206;

FIG. 8

describes step 207; and

FIG. 9

describes step 208. Finally step 209, being the second step, or correction process of the invention is described in more detail in FIG. 2(b).

Returning to FIG. 2(a) we now continue with our description of the detection process. The image to be processed is assumed to be available in a standard file format such as JPEG, TIFF or RGB bitmap. To facilitate the subsequent image processing algorithms that are applied to the image it is firstly converted into the Lab color space 201. This color space stores the data for each pixel in the image as a triplet of values, the luminance â€œLâ€ , and the â€œaâ€ and â€œbâ€ chrominance components. This color space will be well known to those familiar in the art of image processing, however a short explanation is included to facilitate the remainder of this description. The luminance component â€œLâ€ , is a measure of the brightness of an image pixel, the â€œaâ€ component measures the red/green color of a pixel and the â€œbâ€ component measures its yellow/blue color.

As most images must be converted to RGB in order to display the image on a computer monitor our preferred embodiment makes a conversion of an RGB image into Lab color space, using look-up tables in order to speed-up the algorithm. It is assumed that images in other formats such as JPEG or TIFF have been de-compressed or converted into RGB prior to this step. The conversion of image data between different file formats is well known to those skilled in the art.

From this point on, a color pixel f(i,j) will be identified by a color triple, [L(i,j), a(i,j), b(i,j)] where i,j are the horizontal and vertical co-ordinates of the pixel in the image and â€œLâ€ represents the luminosity component. The larger the â€œLâ€ value, the brighter the respective color. The â€œaâ€ and â€œbâ€ values represent the color components which are independent of â€œLâ€ , i.e., they define the color tone of a pixel. The â€œaâ€ axis goes from green to red tones: large negative values of â€œaâ€ indicate greenish colors, which turn reddish as â€œaâ€ increases. The â€œbâ€ axis goes from yellow to blue.

The next step is to categorize pixels as being red enough to be members of a potential red-eye segment 202. This is easily achieved by setting a threshold on the â€œaâ€ and â€œLâ€ components of a pixel. Thus if the conditions â€œaâ€ >â€œa_REDâ€ and â€œLâ€ >â€œL_REDâ€ are met, then a pixel is sufficiently red to be a potential member of a potential red-eye segment. We have found useful values of â€œa_REDâ€ and â€œL_REDâ€ to be+17 and+40 respectively. Note that the â€œaâ€ component covers values from âˆ’500 up to +500. Negative values indicate green tones while positive values indicate red tones. The value of +17 for the threshold was heuristically determined such that no red eyes in the test database are missed. The additional luminosity constraint used in the decision step is useful in order to avoid dark pixels, the color of which is barely perceivable by the human eye, to be labeled as â€œredâ€ .

Now it is necessary to group these â€œredâ€ pixels into connected segments 203. Identification of connected segments in the binary image is achieved by applying a standard labeling algorithm that works in a single raster-scan of the image using a label correspondence look-up table. Labeling is a well-known technique in image processing. All techniques described in textbooks are 100% accurate, the choice between then being made with respect to other criteria, mainly the processing time.

In order to expand our description of step 203 we must now refer to the detailed flowchart of the algorithm used in our preferred embodiment given in FIG. 3(b). A description of this algorithm is now given, although, as will be understood by those skilled in the art, there are many similar algorithms that may be used to achieve the same goal of labeling all connected segments in an image. Thus it is to be understood that the following description is not intended to limit the scope of the present invention being one of many labeling algorithms that are well known to those skilled in the art.

FIG. 3(a) shows a diagrammatic representation of a neighborhood with four pixels 302, containing three upper pixels and a pixel to the left of the current pixel 301. This 4-pixel neighborhood is used in the labeling algorithm as implemented in the preferred embodiment. A look-up table, LUT, is defined to hold correspondence labels. The labeling algorithm as described in FIG. 3(b) begins by loading the image, initializing the LUT and the current pixel pointer 321. It then begins recursive iteration through all the pixels of an image. The image is raster-scanned from top-left to bottom-right. If a pixel satisfies membership criteria for a segment 322, i.e., if it is sufficiently â€œredâ€ , then the algorithm checks for other â€œredâ€ pixels in the 4-pixel neighborhood 323. If there are no other â€œredâ€ pixels, then the current pixel is assigned membership of the current label 324. The LUT is then updated and the current label value is incremented 326. If there are other â€œredâ€ pixels in the 4-pixel neighborhood then the current pixel is given membership in the segment with the lowest label value and the LUT is updated accordingly 325. After the current pixel has been labeled as part of a â€œredâ€ segment 324 or 325, or has been categorized as â€œnon-redâ€ during step 322, a test is then performed to determine if it is the last pixel in the image 327. If the current pixel is the last pixel in the image then a final update of the LUT is performed 328. Otherwise the next image pixel is obtained by incrementing the current pixel pointer 331 and returning to step 322 and is processed in the same manner 322-327. Once the final image pixel is processed and the final LUT completed 328, all of the pixels with segment membership are sorted into a labeled-segment table of potential red-eye segments 329. We may now proceed to begin eliminating these potential red-eye segments based on a range of segment attributes 330.

A representation of a typical segment is given in FIG. 4 and is comprised of three regions: there are â€œredâ€ pixels, p_red401 which are contiguous and delimit the extremities of the segment; there are â€œnon-redâ€ pixels, p_norm402 and the entire segment is surrounded by a â€œboundingâ€ region 403 which is useful in performing several of the subsequent image processing steps we describe in this preferred embodiment. Note that this diagram is for descriptive purposes only and the sizes of both the actual segment and the â€œboundingâ€ region are typically somewhat larger than are shown here.

Note that the processing time requested by a labeling algorithm actually depends upon the number of distinct segments present in the binary image being labeled. The algorithm described in this preferred embodiment is the fastest on average. It completes the labeling of all segments within a single raster scan of the image, by using a label correspondence LUT.

At this point we have a set of potential red-eye segments for the image however, as will be apparent to those skilled in the art, most of the segments identified in this initial stage of the detection process will not be due to red-eye defects. The next stage of our detection process is to eliminate those segments that do not satisfy a range of other characteristics and criteria normally associated with a segment that is a valid red-eye defect. We now present a description of the elimination process covering a range of 5 key criteria and described in

FIGS. 5-9

and corresponding to steps 204-208 in FIG. 2(a). Note that, although the 5 main criteria presented in this description of the preferred embodiment are quite comprehensive, it is not the intention to limit the scope of the invention solely to these particular criteria. As will be understood by those skilled in the art, additional filtering criteria may provide improved results in certain particular instances. Thus other embodiments of the present invention may incorporate refinements on the criteria described below or additional filtering criteria not described in the present preferred embodiment.

The first criteria we apply is to eliminate segments of an inappropriate size for a red-eye segment, i.e., segments that are too small, or too large. This elimination step corresponds to step 204 in FIG. 2(a) and is described in detail by FIG. 5. We begin this step by getting a list of pixels, described by their i,j co-ordinates, that are members of a particular segment 501. The segment area is determined by obtaining the maximum and minimum i (vertical) and j (horizontal) co-ordinates of its member pixelsâ€”this can be better understood by referring to the representation of a typical segment, S_k, in FIG. 4. The area of the segment is then calculated as A_k=Î£p_RED, or in words the effective area of the potential red-eye segment is the sum of the confirmed â€œredâ€ pixels (i.e. p_RED) in that segment 502.

Only segments S_kwith the area A_kbetween given limits A_MAXâ‰§A_kâ‰§A_MINare further inspected. Now red-eye defect segments can be quite small, but it is generally unproductive to process segments below a certain minimum number of â€œredâ€ pixels as such defects are not particularly noticeable and do not have sufficient detail to benefit from additional processing. For a standard digital image a suitable lower threshold for the area, A_MIN, is of the order of 20-50 pixels. Thus any segments of a size less than A_MIN503 are immediately eliminated from the LUT 506. Experiments have led to the conclusion that the area occupied by the red pupil of an eye is normally less than 0.1% of the total area of a standard photograph. This sets the threshold for the first upper limit on segment area, A_MAX1504. Any segments that survived elimination at steps 503 and 504 are next marked as valid red-eye segments 508 on the basis of segment size. However, in certain instances, for example close-up portraits, the upper size limit may be as large as 0.5% of the total area, but the red pupil should now have a distinct surrounding region of whitish color, being the cornea of the eye. Thus any segments that failed the size test under 504 are given a second size test and if A_k=A_MAX2505 then the â€œboundingâ€ region of the segment is tested for the presence of any whitish pixels 507. If there are sufficient whitish pixels the segment is validated on the basis of segment size 508, otherwise the segment is rejected 506 and the next potential red-eye segment is loaded from the LUT. Any red segments of an area greater than A_MAX2are unlikely to be due to red-eye defects and can be discarded 506. Finally when there are no more potential red-eye segments left in the LUT 509 testing can begin on the remaining valid segments in order to eliminate segments that are too elongated to be valid red-eye segments 510.

Elimination of elongated segments (FIG. 2(a) step 205) is described in detail by the flowchart in FIG. 6. For each segment S_k, the variances Î»_k_MAXand Î»_k_MINalong the principal axes are computed. We note that the variance Î» of a set of 1-D (one dimensional) samples x_iwith i Îµ[1 . . . N] is computed according with the formula $Î» = \frac{1}{N} â ¢ \sqrt{{âˆ‘}_{i = 1}^{N} â ¢ â€ƒ â ¢ {(x_{i} - \overline{x})}^{2}}$
where $\overline{x} = \frac{1}{N} â ¢ {âˆ‘}_{i = 1}^{N} â ¢ â€ƒ â ¢ x_{i}$
is the mean. These variances, Î»_k_MINand Î»_k_MAXare obtained from the eigenvalues of the covariance matrix Ck given by the matrix formula (i,j are the horizontal and vertical co-ordinates of a pixel in the image, said pixel being a member of segment Sk, the k^thsegment remaining in the LUT of potential red-eye segments): $C_{k} = \frac{1}{A_{k}} â ¢ \underset{i, j) âˆˆ S_{k}}{âˆ‘} â ¢ â€ƒ â ¢ {[ij]}^{T} Â\cdot [ij] - {[\overline{ij}]}^{T} Â\cdot [\overline{ij}]$
where T denotes the matrix transpose operator, and: $\overline{i} = \frac{1}{A_{k}} â ¢ \underset{(i, j) âˆˆ S_{k}}{âˆ‘} â ¢ â€ƒ â ¢ i; â€ƒ â ¢ \overline{j} = \frac{1}{A_{k}} â ¢ \underset{(i, j) âˆˆ S_{k}}{âˆ‘} â ¢ â€ƒ â ¢ j$

The test process is as follows: the next surviving potential red-eye segment is loaded 601 and the covariance matrix, Ck, for this segment is calculated 602. The maximum and minimum variances along the principle axes of this segment are next calculated from the eigenvalues of Ck 603, a procedure well known to those skilled in the art. The aspect ratio R_kof segment Sk is then computed as 604: $R_{k} = \frac{{Î»}_{k_{MIN}}}{{Î»}_{k_{MAX}}}$

Segments that are too elongated 605 to be red-eye defects, i.e., segments with
R_kâ‰¦R_MAX

with RMAX being a pre-defined threshold, are exempted from further processing 606, as they are unlikely to represent red eyes. Non-elongated shapes have the ratio Rk close to unity. A useful criteria for segments with Ak=AMAX1 is to eliminate all segments having Rk<0.2. For larger segments, those having area A_MAX1=A_k=A_MAX2, the criteria Rk<0.5 is used to eliminate potential red-eye candidates.

The remaining segments that are sufficiently rounded are marked as valid for the elongation criteria 607 and are retained for the next stage of testing. When all surviving segments have been tested 608 then testing of all surviving segments for non-compactness will commence 609.

The elimination process for non-compact segments 206 is described in detail by FIG. 7. Firstly a surviving segment is loaded into memory from the LUT 701. The segment fill factor F_kis computed as 702: $F_{k} = \frac{A_{k}}{(i_{k_{MAX}} - i_{k_{MIN}}) â ¢ (j_{k_{MAX}} - j_{k_{MIN}})}$

- where i_k_MAX, i_k_MIN, j_k_MAXand j_k_MINrepresent the minimum and maximum coordinates of pixels within the segment S_k. All segments with F_kâ‰¦F_MINare eliminated 703, 705. In practice we have found that ratio of the segment area to minimal bounding box area, must be higher than 0.5 for a segment to be sufficiently compact to be a potential red-eye defect. Segments that pass this test for compactness are marked as such 704 and retained. When all remaining segments have been tested 706 then the next test, for the presence of skin pixels, is initiated 707.

Before describing the next elimination step, which employs a test for skin color pixels, it is useful to mention that the detection technique used in this embodiment of the present invention is the same as known techniques described in the prior-art section. This technique involves the matching of the a and b components of the Lab color value of a pixel to a set of 32 skin color prototypes while ensuring that the luminance component, L, remains greater than a lower threshold value. The skin prototypes are derived from a large database of sample images but once the 32 prototype colors are determined they remain static. In practice this technique is both fast and accurate. The technique has been documented in detail in the parent U.S. patent application Ser. No. 09/823,139.

The procedure to eliminate segments that are not located in the neighborhood of skin patches 207 is described in more detail in reference to

FIG. 8

as follows: firstly a potential red-eye segment is loaded into memory 801; a bounding region delimited by corners (i_k[min]âˆ’d,j_k[min]âˆ’d) and (i_k[max]+d, j_k[max]+d), where d is a pre-defined quantity is defined around the potential red-eye segment 802; each pixel within this bounding region is now tested to determine if it is a skin pixel 803. A pixel is classified as â€œskinâ€ if the minimum Euclidean distance in Lab coordinates to one of the pre-determined skin-prototypes is lower than a given threshold. This â€œskin pixelâ€ decision is taken based on the use of skin prototypes as in U.S. patent application Ser. No. 09/823,139. If the skin-pixel ratio, Ek, in the bounding box is lower than a pre-defined limit, E_MIN, 804 then the segment Sk is eliminated 805, 806. Otherwise the segment Sk is validated for the skin-pixel test 807. When all surviving potential red-eye segments have been tested 808 the next test criteria for internal contrast 208 is initiated 809. This step 208 of FIG. 2(a) is described in detail by FIG. 9.

The final test step in this embodiment is the elimination of the surviving segments having low internal contrast. The contrast Ck within the a segment Sk is defined by the ratio: $C_{k} = \frac{L_{k_{MAX}} - L_{k_{MIN}}}{L_{k_{MAX}} + L_{k_{MIN}}}$

where L_k_MINand L_k_MAXare the minimum and maximum values of the luminosity, or L component within the bounding box for the segment Sk. As before one of the surviving segments is loaded from the LUT 901 and the maximum and minimum values of the luminance are calculated 902, 903 by iterating through the pixels of this segment and its bounding region. The internal contrast of the segment is then calculated 904. Only segments Sk with Ck>Cmin, where Cmin is a pre-determined limit for internal contrast in a segment, are retained 905. Segments that fail this test are eliminated 906 as potential red-eye segments. Any segments that remain after completing this final elimination test are marked as valid 907. The algorithm continues to check each segment remaining in the LUT 908 until all segments have been tested. The segments which are retained in the LUT and thus have survived all of the elimination steps 204-208 are now passed on to the color correction stage of the process 209, 909.

The correction procedure 209, 909 for red-eye labeled segments is described in FIG. 2(b) and works as follows. Firstly, one of the surviving segments is loaded from the LUT 221 and its bounding box is defined. A typical red-eye segment 404 and its bounding box 403 is illustrated in FIG. 4. The histogram of the â€œaâ€ color component, ha, is computed within the bounding box 222. Then, the cumulative histogram Ha is computed as: $H_{a} â ¢ (i) = {âˆ‘}_{j = a_{MIN}}^{i} â ¢ â€ƒ â ¢ h_{a} â ¢ (j)$
where h_a(j) is the value of the histogram of the â€œaâ€ color component at a particular value of â€œaâ€ =j; the cumulative histogram is formed by summing from â€œa_minâ€ up to the current value of â€œaâ€ =i. Based on the cumulative histogram, the a_0.7value is computed 223. The a_0.7is the value of the â€œaâ€ component which superiorly delimits 70% of the â€œaâ€ histogram, i.e.:
H_a(a_0.7)=0.7
Then, the â€œaâ€ values of pixels within the bounding box are limited to a_0.7224, 225, 226:
aâ€²(i,j)=a(i,j) if a(i,j)=<a0.7;
aâ€²(i,j)=a0.7 otherwise
âˆ€(i,j)âˆˆS_k
When all the pixels in a particular segment have been corrected in this manner 227 the next red-eye segment is loaded from the LUT 228 unless all segments have been corrected. The same procedure is then applied to each segment. When all red-eye segments have been corrected, the altered portions of the image are converted back to the original image format. This back translation Laâ€²bâ†’Râ€²Gâ€²Bâ€² is performed for all pixels that had their a component altered by the color correction scheme 229.

Note that there are several advantages to this color correction scheme:

Firstly, by modifying the â€œaâ€ components of all pixels in the bounding box, there are no artifacts due to misclassification of red pixels.

Secondly, noticeable red reduction will only be achieved if the segment's bounding box contains a reddish and a non-reddish population of pixels, i.e., the ha histogram has non-zero values in a larger interval. This is the common situation for real red-eye areas, characterized by red tones in the vicinity of the pupil and tones other than red in the remainder. In the opposite case, i.e., where there are only red pixels in the segment and the histogram is consequently very narrow, the lower and upper limits of the a component are both close to the a_0.7value: a_min^Ëœa_0.7^Ëœa_max. In this case, the color correction to limit the redness of the area described above has practically no visible effect.

Thirdly, and in contrast to other techniques described to correct red-eye defects, our approach retains the non-red colors of the pixels. Thus in applying this technique to an image the eye defect is not only corrected but is actually restored to a color which is close to the natural coloration of the eye.

In

FIG. 10

we illustrate the operation of the invention on a typical digital image. There are several components of this image which will be determined as being potential red-eye segments. For example a group of cherries, or similar fruit 1010 will produce a potential red-eye segment as shown in area 1000 of FIG. 11(a). However such a segment will be eliminated because of non-compactness of the segment. The mouth and lips 1020, 1030 are another component of this image, which will often be determined to be a potential red-eye segment. In most cases the mouth and lips are somewhat elongated 1020 leading to a potential red-eye segment 1002 similar to FIG. 11(b). In such cases the segment will be quickly eliminated due to its elongation. However in some instances, particularly in the case of children, the mouth and lip region 1030 is quite round in appearance leading to a segment of the form illustrated in area 1004 of FIG. 11(c). In such cases the segment will be eliminated because the internal contrast of a mouth region is significantly lower than that of an eye region. Other components of this image include a large red ball 1040, which is eliminated due to its size; and a red spotted pattern 1050 on the woman's blouse which will be eliminated due to the low internal contrast of this potential red-eye segment.

Alternative Embodiment

In an alternative embodiment, the correction scheme as defined above can be applied in conjunction with other detection algorithms as the ones defined above.

In particular, the aforementioned technology can be implemented as an interactive system whereas between the detection and correction stages, a user interaction is required to approve that the detected regions are truly red-eye ones. Such system can be utilized in production such as a custom printing, high volume printing facility or even on a digital camera. In both cases, the user may be notified of the existence of suspected red-eye regions. Such notification can be visually, by highlighting the suspected regions, or even with a unique sound or signal. The camera user, or the print operator can then decide based on the visual display of correction proposed by the system, if the correction should be applied or rejected.

In yet another alternative embodiment, in the case of using this process for digital cameras, the process will only be activated as needed. The main criteria for activating the detection is only when a flash was needed. A secondary criteria in the case that the camera has an automatic focusing mechanism is if the subject matter is close enough to the camera, for example 20 ft. or less. In this scenario an interactive stage may be added to notify the user that a red-eye artifact was detected, and the user may take action to tell the camera to apply a correction algorithm similar to the one described above, to eliminate the artifact.

Conclusion Ramifications and Scope

Accordingly, the reader can see that the above invention provides an efficient way to automatically detect and correct red-eye artifacts from digital images.

In particular, this invention has the advantages of being efficient enough in terms of computational needs to be embedded in electronic devices that require real time processing such as digital camera, hand held display devices, cellular phones etc. In addition, due to its efficiency, this invention can be implemented as part of a large volume system such as a commercial photographic printing facility.

The simple means of which the red-eye is being corrected enables a powerful solution which maintains all surrounding colors while affecting only the affected are, thus enabling a close restoration of the original scene.

Although the description above contains many specificities, these should not be construed as limiting the scope of the invention but as merely providing illustrations of some of the presently preferred embodiments of this invention. Various other embodiments and ramifications will be apparent and possible within it's scope for those skilled in the art.

It should be further understood that the programs, processes and methods described herein are not related or limited to any particular type of computer apparatus, unless indicated otherwise. Various types of general purpose or specialized computer apparatus may be used with or perform operations in accordance with the invention described herein. Further, elements of the illustrated embodiment shown in software may be implemented in hardware and vice versa.

In view of the many possible embodiments to which the principles of our invention may be applied it should be recognized that the embodiments described herein with respect to the drawings and figures is only illustrative and should not be taken as limiting the scope of the invention.

Thus the scope of the invention should be determined by the appended claims and their legal equivalents as covering all such alterations and modifications that fall within the true scope and spirit of the invention, rather than by the examples given.