Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 1 of 28
`Case 1:20-cv-03128—ER Document 1-1 Filed 04/20/20 Page 1 of 28
`
`Exhibit 1
`Exhibit 1
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 2 of 28
`
`(12) United States Patent
`Steinberg
`
`USOO6873743B2
`(10) Patent No.:
`US 6,873,743 B2
`(45) Date of Patent:
`Mar. 29, 2005
`
`5,748,764 A * 5/1998 Benati et al. ............... 382/117
`5,754,676 A 5/1998 Komiya et al. ............. 382/132
`5,765,029 A 6/1998 Schweid et al. .............. 395/61
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`EP
`JP
`WO
`
`........... HO1 L/21/00
`2/2001
`1/126508
`O9237348 A 9/1997 ............. GO6T/7/60
`WOOO/67204
`11/2000 ............. GO6T/7/OO
`OTHER PUBLICATIONS
`Forsyth, David A. et al., “Finding Naked People,” Journal
`Review, 1996.
`Forsyth, David A. et al., “Finding Pictures of Objects in
`Large Collecti
`f Images.” P
`dings, I
`ional
`arge Collections of ImageS, ProceedingS, Internationa
`Workshop on Object Recognition, Cambridge, 1996.
`Flich, Margaret, et al., “Finding Naked People,” Proceed
`ings of 4" European Conference on Computer Vision, 1996.
`Primary Examiner Andrew W. Johns
`ASSistant Examiner Amir Alavi
`(74) Attorney, Agent, or Firm Sawyer Law Group LLP
`(57)
`ABSTRACT
`An automatic, red-eye detection and correction System for
`digital images capable of real-time processing of Images,
`including a red-eye detector module that determines without
`located in an image the portion of the image Surrounding the
`defect is passed to a correction module that de-Saturates the
`red components of the defect while preserving the other
`color characteristics of the defect region. The invention is
`designed to minimize the computational resources required
`to detect and correct red-eye defects and thus is particularly
`Suited to applications requiring real-time processing of large
`Volumes of digital imageS prior to acquisition or printing.
`This System can operate on images Stored on personal
`computers, commercial printers or inside digital cameras as
`part of the acquisition process, or prior to display on
`personal digital assistants, mobile phones and other digital
`imaging appliances.
`
`USC intervention if
`
`red-eye defect exists. If
`
`defect is
`
`(54) METHOD AND APPARATUS FOR THE
`AUTOMATIC REAL-TIME DETECTION AND
`CORRECTION OF RED-EYE DEFECTS IN
`SEESSENGEs OR IN
`
`(75) Inventor: Eran Steinberg, San Francisco, CA
`(US)
`
`(73) Assignee: Fotonation Holdings, LLC,
`Peterborough, NH (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 534 days.
`
`(*) Notice:
`
`(21) Appl. No.: 10/113,871
`1-1.
`(22) Filed:
`Mar. 29, 2002
`65
`Prior Publication Data
`(65)
`
`US 2002/0176623 A1 Nov. 28, 2002
`O
`O
`Related U.S. Application Data
`(63) Continuation-in-part of application No. 09/823,139, filed on
`Mar. 29, 2001, now Pat. No. 6,751,348.
`(51) Int. Cl. ............................. G06K9/40; G06K 9/00
`
`(52) U.S. C. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 382/275; 382/117
`
`(58) Field of Search ................................. 382/115, 117,
`382/162, 164, 165, 167, 168, 171, 172,
`199, 278, 274–277; 358/518, 520, 522;
`348/207, 239, 370, 576
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`
`
`1/1993 Graham et al. ............. 364/526
`5,177,694. A
`5,218,555 A 6/1993 Komai et al. ............... 364/526
`5,329,596. A
`7/1994 Sakou et al. .................. 382/37
`5,432,863 A * 7/1995 Benati et al. ............... 382/167
`5.488.429 A 1/1996 Kojima et al. .............. 34.8/653
`5,633,952. A
`5/1997 Outa et al. .................. 382/165
`5,638,136 A 6/1997 Kojima et al. .............. 34.8/653
`5,678,041 A 10/1997 Baker et al. ................ 395/609
`
`27 Claims, 15 Drawing Sheets
`
`Convert image to LAB Color Space
`
`redpixels
`
`ldentify 8 latel connected segments
`
`Eiiminate segments or basis of area
`
`Eliminate segments on basis of elongation
`
`Eliminate segments on basis of non
`carpactress
`
`Etiminate segments not in the vicinity of skin
`pixels
`
`eliminate segments having a low internai
`contrastratio
`
`Color correction of remaining segments
`
`201
`
`202
`
`203
`
`204
`
`205
`
`208
`
`207
`
`208
`
`203
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 3 of 28
`
`US 6,873,743 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,771,307 A 6/1998 Lu et al - - - - - - - - - - - - - - - - - - - - - 382/116
`5,778,156 A 7/1998 Schweid et al. .............. 396/61
`5,796,869 A 8/1998 Tsuji et al. .......
`... 382/203
`5,805,730 A 9/1998 Yaeger et al. ............... 382/228
`5,813,542 A 9/1998 Cohn ... ................. 209/581
`5,828,779 A 10/1998 Maggioni ...
`... 382/165
`5,832,212 A 11/1998 Cragun et al. ......... 395/188.01
`5.835,722 A 11/1998 Humes .................. 395/200.55
`5,852,823. A 12/1998 De Bonet ...................... 707/6
`RE36,041 E
`1/1999 Turk et al. .................. 382/118
`5,857,014 A
`1/1999 Sumner et al. .......... 379/93.02
`5,872,859 A 2/1999 Gur et al. ................... 382/128
`5,911,043 A 6/1999 Duffy et al. ........... 395/200.33
`5.937,404 A 8/1999 Csaszar et al. ................ 707/9
`5,949,904 A 9/1999 Delp .............
`382/185
`6,009.209 A * 12/1999 Acker et al. ................ 382/275
`6,016,354 A * 1/2000 Linet al. .................... 382/117
`6,041,133 A 3/2000 Califano et al.
`... 382/124
`6,049,821 A 4/2000 Theriault et al. ........... 709/203
`6,065,055 A 5/2000 Hughes et al. .............. 709/229
`
`6,065,056. A 5/2000 Bradshaw et al. .......... 709/229
`6,067,339 A 5/2000 Berger ......................... 386/48
`
`6,115,495 A 9/2000 Tachikawa et al. ......... 382/165
`6,122.400 A 9/2000 Reitmeier ......
`382/168
`6,128,397 A 10/2000 Baluja et al. ............... 382/118
`6,134,339 A * 10/2000 Luo ........................... 382/115
`6,148,092 A 11/2000 Oian et al.
`382/118
`6,182,081. B1
`1/2001 Dietl et al.
`707/102
`6,204.858 B1 * 3/2001 Gupta ........................ 345/600
`6.252,976 B1 * 6/2001 Schildkraut et al.
`382/117
`6,259,801 B1
`7/2001 Wakasu ...................... 382/100
`6,266,664 B1
`7/2001 Russell-Falla et al. ......... 707/5
`6,278.491 B1 * 8/2001 Wang et al. .......
`348/370
`6,286,001 B1
`9/2001 Walker et al. ................. 707/9
`6,407,777 B1
`6/2002 DeLuca ...................... 34.8/576
`6,631,208 B1 * 10/2003 Kinjo et al. .
`382/167
`6.798.903 B2 * 9/2004 Takaoka ..................... 382/167
`2001/0002931 A1
`6/2001 Maes ......................... 382/100
`2002/O126893 A1
`9/2002 Held et al.
`382/167
`2002/0138450 A1
`9/2002 Chen et al. ................. 382/165
`* cited by examiner
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 4 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 1 of 15
`
`US 6,873,743 B2
`
`
`
`F.G.)
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 5 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 2 of 15
`
`US 6,873,743 B2
`
`2O2
`
`203
`
`204
`
`205
`
`206
`
`2O7
`
`208
`
`209
`
`Convert image to LAB Color Space
`
`ldentification of red pixels
`
`ldentify & label Connected segments
`
`Eliminate segments on basis of area
`
`Eliminate segments on basis of elongation
`
`Eliminate segments on basis of non
`Compactness
`
`Eliminate segments not in the vicinity of skin
`pixels
`
`Eliminate segments having a low internal
`Contrast ratio
`
`Color correction of remaining segments
`
`FIG. 2(a)
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 6 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 3 of 15
`
`US 6,873,743 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Get next segment from look-up table
`
`Apply bounding region, calculate
`cumulative histogram for combined
`segment + bounding region
`
`Calculate the 70% histogram value,
`a(0.7)
`
`221
`
`222
`
`223
`
`224
`
`Get next pixel in combined region
`
`225
`
`
`
`is a value greater than a(0.7) 2
`
`226
`
`Seta = a(0.7)
`for this pixel
`
`ls this last pixel for this combined
`segment + bounding region
`Yes
`
`
`
`Yes
`
`Do any segments remain uncorrected?
`
`No
`Back convert image to original format:
`Lab --> RGB
`
`228
`
`229
`
`FIG. 2(b)
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 7 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 4 of 15
`
`US 6,873,743 B2
`
`302
`
`3O2
`
`302
`
`301
`
`FIG. 3(a)
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 8 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 5 of 15
`
`US 6,873,743 B2
`
`Get Image; initialize Labeling LUT,
`Current pixel and pixel neighborhood
`
`321
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`322
`
`Yes
`
`323
`
`Are there othe
`membership pixels in
`neighborhood of
`current pixel?
`
`No
`Set current
`pixel to current
`label;
`
`No
`Update LUT:
`increment
`Current label
`
`324
`
`326
`
`Does current Pixel
`Satisfy segment
`embership criteria?
`
`Set current pixel to belong to
`the segment with lowest label
`value,
`Update LUT accordingly
`
`is current
`pixel the last
`mage pixel
`
`Yes
`
`Final UT
`update
`
`328
`
`Set next image
`pixel to be
`Current pixel
`
`331
`
`329
`
`330
`
`All pixels with segment
`membership are sorted into
`a labeled segment table of
`potential red-eye segments
`
`
`
`Elimination of potential red
`eye segments now begins
`(Figs 5-9)
`FIG. 3(b)
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 9 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 6 of 15
`
`US 6,873,743 B2
`
`H-HHHHH
`NH|| || || ||
`
`
`
`
`
`
`
`
`
`
`
`
`
`s
`
`
`
`s
`
`
`
`
`
`
`
`
`
`
`
`
`
`3.
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 10 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 7 of 15
`
`US 6,873,743 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`501
`
`502
`
`503
`
`Get next segment from look-up table
`
`Calculate segment Area, Ak
`
`Ak < Amin
`
`NO
`
`Ak > Amax1 ?
`
`
`
`
`
`Yes
`Ak > Amax2
`
`... Test for Corneal (white) pixels?
`
`Yes
`
`Validate segment for area, Ak
`
`
`
`Reject this
`Segment
`
`
`
`Yes
`
`
`
`Do any segments remain
`untested?
`No
`
`Begin test of surviving segments for
`elongation (Fig x)
`
`
`
`508
`
`509
`
`510
`
`F.G. 5
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 11 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 8 of 15
`
`US 6,873,743 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`Get next segment from look-up table
`
`Calculate Covariance matrix,
`Ck, for this segment
`
`Calculate the max and min
`variances along the principle
`axes of this segment
`
`601
`
`602
`
`603
`
`Calculate the ratio, Rk, of minto
`aX Wafa Ce
`
`604
`
`ls RK CRmax 7
`
`No
`Validate segment for elongation
`test
`
`Reject this
`segment
`
`Yes
`
`Do any segments remain
`untested?
`No
`Begin test of Surviving segments
`for non-compaction (Fig x)
`
`F.G. 6
`
`605
`
`6O7
`
`608
`
`609
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 12 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 9 of 15
`
`US 6,873,743 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Reject this
`segment
`
`701
`
`702
`
`3
`70
`
`-704
`
`Get next segment from look-up table
`
`Calculate segment fill factor, Fk,
`for this segment
`
`
`
`ls FK C Fmin 2
`
`No
`
`Validate segment for
`Compaction test
`
`Do any segments remain
`untested?
`
`
`
`No
`Begin test of surviving segments
`for presence of skin pixels (Fig x)
`
`
`
`706
`
`707
`
`FIG. 7
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 13 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 10 of 15
`
`US 6,873,743 B2
`
`Get next segment from look-up table
`
`Determine a bounding region
`for this segment
`
`Test if each pixel within the
`bounding region is a skin pixel
`
`
`
`Calculate the ratio, Ek, of skin
`to non-skin pixels within the
`bounding region
`
`Yes
`
`806
`
`Reject this
`Segment
`
`ls Ek < Emin 2
`
`No
`Walidate segment for skin-pixel
`test
`
`8O1
`
`802
`
`803
`
`804
`
`805
`
`807
`
`Yes
`
`Do any segments remain
`untested?
`NO
`Begin test of surviving segments
`for internal contrast levels (Figy)
`
`808
`
`809
`
`FG. 8
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 14 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 11 of 15
`
`US 6,873,743 B2
`
`Get next segment from look-up table
`
`Determine the max value of
`Luminance, Limax, in this segment
`
`Determine the min value of
`Luminance, Limin, in this segment
`
`901
`
`902
`
`903
`
`Calculate the contrast, Ck, of
`this segment
`
`904
`
`is Ck < Cnin
`
`NO
`Validate segment for internal
`Contrast test
`
`906
`
`
`
`Reject this
`segment
`
`
`
`Yes
`
`Do any segments remain
`untested?
`
`Apply Color correction process to all
`surviving segments (Fig Z)
`
`FIG. 9
`
`905
`
`907
`
`908
`
`909
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 15 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 12 of 15
`
`US 6,873,743 B2
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 16 of 28
`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 16 of 28
`
`US. Patent
`
`Mar. 29, 2005
`
`Sheet 13 0f 15
`
`US 6,873,743 B2
`
`IIIIEIEEIIEEIIIIIIIIIIIE""
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 17 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 14 of 15
`
`US 6,873,743 B2
`
`
`
`Hi-H
`
`|
`
`|
`
`|
`
`|
`
`|
`
`|
`
`|
`
`|
`
`|
`
`| | | |
`
`|
`
`|
`
`| | |
`
`|
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 18 of 28
`
`U.S. Patent
`
`Mar. 29, 2005
`
`Sheet 15 of 15
`
`US 6,873,743 B2
`
`
`
`
`
`
`
`| | | |
`
`| |
`
`|
`
`|
`
`|
`
`SN
`| | NN
`
`
`
`H-------H
`|| ||
`
`s
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 19 of 28
`
`US 6,873,743 B2
`
`1
`METHOD AND APPARATUS FOR THE
`AUTOMATIC REAL-TIME DETECTION AND
`CORRECTION OF RED-EYE DEFECTS IN
`BATCHES OF DIGITAL IMAGES OR IN
`HANDHELD APPLIANCES
`
`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 detect
`ing and correcting red-eye defects in a digital image thereby
`reducing or eliminating the need for user intervention.
`
`15
`
`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 flashbulb 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 exagger
`ated 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 usu
`ally 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
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`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 impor
`tance 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 practi
`cally 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 automati
`cally detect the red eyes, but rather requires the user inter
`vention 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 pro
`vides the user with means for manually painting over the red
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 20 of 28
`
`US 6,873,743 B2
`
`3
`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 ana
`lyze 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 pres
`ence of red-eye defects. Further, there are Some disadvan
`tages 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 partition
`ing and re-scaling operations. Significant additional proceSS
`ing 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 opti
`mized for implementation as a dedicated hardware Solution,
`e.g. as a dedicated ASIC (application specific integrated
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`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 con
`Stantly processed in real time, or in handheld digital appli
`ances 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 photo
`graphed.
`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 computa
`tionally 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) identify
`ing 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)
`
`

`

`Case 1:20-cv-03128-ER Document 1-1 Filed 04/20/20 Page 21 of 28
`
`US 6,873,743 B2
`
`S
`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 uni
`formly on both pixels which are members of a defect and its
`bounding region thus avoiding the need to determine indi
`vidually 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 require
`ments 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 inven
`tion 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;
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`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 interven
`tion;
`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 Seg
`ments,
`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 el