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

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 2 of 18
`
`USO08073250B2
`
`(12) United States Patent
`Vide
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,073,250 B2
`*Dec. 6, 2011
`
`(54)
`
`(75)
`
`(73)
`
`METHOD AND SYSTEM FOR REMOVAL OF
`RED EYE EFFECTS
`
`Inventor: Adolfo Pinheiro Vide, Montgiscard (FR)
`
`Assignee: Intellectual Ventures I LLC,
`Wilmington, DE (US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 773 days.
`This patent is Subject to a terminal dis
`claimer.
`
`(21)
`
`Appl. No.: 11/950,356
`
`(22)
`
`Filed:
`
`Dec. 4, 2007
`
`(65)
`
`Prior Publication Data
`US 2008/O285850 A1
`Nov. 20, 2008
`
`(60)
`
`(51)
`
`(52)
`(58)
`
`Related U.S. Application Data
`Continuation of application No. 1 1/175,551, filed on
`Jul. 5, 2005, now Pat. No. 7,324,689, which is a
`division of application No. 09/767,331, filed on Jan.
`22, 2001, now Pat. No. 7,088,855.
`
`Int. C.
`(2006.01)
`G06K 9/00
`(2006.01)
`G06K 9/40
`U.S. Cl. ....................................................... 382/167
`Field of Classification Search .................. 382/103,
`382/115, 117, 162, 165, 167, 254, 274, 275,
`382/299; 358/1.13, 1.9, 500, 509, 518, 520,
`358/527; 396/155, 158; 348/239, 370, 576,
`34.8/586
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,285,588 A
`8, 1981 Mir
`4,315,024 A
`2f1982 Abelson
`4,315,204 A
`2f1982 Sievers et al.
`4,978,989 A 12/1990 Nakano et al.
`5,130,789 A
`7, 1992 Dobbs et al.
`5,748,764 A
`5/1998 Benati et al.
`5.990,901 A 11/1999 Lawton et al.
`5.990,973 A 11/1999 Sakamoto et al.
`6,009,209 A * 12/1999 Acker et al. .................. 382,275
`6,016,354 A
`1/2000 Lin et al.
`6,285.410 B1* 9/2001 Marni ........................... 348,576
`6,577,751 B2 * 6/2003 Yamamoto .................... 382,117
`6,631.208 B1
`10/2003 Kinjo et al.
`6,690,822 B1
`2/2004 Chen et al.
`6,701,007 B1
`3/2004 Yamaguchi
`6,718,051 B1
`4/2004 Eschbach
`6,728.401 B1
`4/2004 Hardeberg
`6,765,686 B2 * 7/2004 Maruoka ...................... 358,115
`6,788,425 B1
`9, 2004 Ohtsuka et al.
`6,798.903 B2
`9/2004 Takaoka et al.
`(Continued)
`Primary Examiner — Amir Alavi
`(74) Attorney, Agent, or Firm — Perkins Coie LLP
`(57)
`ABSTRACT
`A method of performing red eye correction in an image
`including storing a high resolution image on a server com
`puter, transmitting a low resolution image derived from the
`high resolution image, from the server computer to a client
`computer, displaying the low resolution image on a display
`device connected to the client computer, receiving from a user
`an indication of a selected location within the displayed low
`resolution image, partially automatically defining an outline
`of an area in the low resolution image within which area red
`eye correction is to be carried out, by the client computer,
`based on the user's selected location, carrying out red eye
`correction on the low resolution image only within the area,
`by the client computer, and transmitting parameters of the
`area from the client computer to the server computer. A sys
`tem is also described and claimed.
`31 Claims, 7 Drawing Sheets
`
`
`
`NPUT EVCE
`
`
`
`
`
`
`
`
`
`SLAY
`
`MEMORY FOR OW
`RESOUTION
`GA.MAGE
`
`
`
`235
`MEWORY FOR HGH
`RESOLION
`DIGITAMAGE
`
`250 (X,Y,D)
`MEMORY FOR CRCLE
`POSITION ANDSZE
`
`24s
`RED EYE CORRECTION
`PROCESSOR
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 3 of 18
`
`US 8,073,250 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`6,980,691 B2 * 12, 2005 Nesterov et al. .
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 382,165
`
`6,987.535 B1* 1/2006 Matsugu et al. .............. 348,239
`7,024,035 B1
`4/2006 Enomoto et al.
`7,088,855 B1* 8/2006 Vide ............................. 382, 167
`7,116,820 B2 * 10/2006 Luo et al. ...
`382/167
`7,155,058 B2 * 12/2006 Gaubatz et al. ............... 382, 167
`7,164,496 B2
`1/2007 Tatsumi et al.
`
`
`
`7.324,689 B1* 1/2008 Vide ............................. 382, 167
`ck
`7,764,846 B2
`T/2010 Marchesotti et al. .
`.
`.
`.
`.
`.
`.
`. 382.274
`2001/0022853 A1
`9, 2001 Takaoka
`2002/O122588 A1
`9, 2002 Yamamoto
`ck
`2008/0285850 A1* 11/2008 Vide ............................. 382, 167
`2009/02384.54 A1* 9/2009 Hang et al..................... 382, 167
`
`* cited by examiner
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 4 of 18
`
`U.S. Patent
`
`Dec. 6, 2011
`
`Sheet 1 of 7
`
`US 8,073,250 B2
`
`11 O
`
`
`
`13O
`
`F.G. 1
`(PRIOR ART)
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 5 of 18
`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 5 of 18
`
`U.S. Patent
`
`aD
`
`h
`
`f
`
`US 8,073,250 B2
`
`sI%II”.8308;ImazofiommmooME8:
`8.50
`
` 1mug.565m20:38E2,39mo“.E05:”5380”:6.<mm<m>momm
`
`
`
`
`032“Namg
`
`7W
`
`
`
`IQImo“.>mo_>_m=>_
`
`
`
`NOSE._<._._c_n_
`
`ZO_.S._Ommm
`
`20:85.8NE.SE8.303050me$032
`
`8388;mg9220:58
`
`0mm
`
`N.GE
`
`\/owm
`
`
`
`mmzbmfioomm>mmw
`
`mo<umm._.z_mum:
`
`
`
`mo_>mo._.3n_z_
`
`
`
`mmcbmfioo.2940
`
`
`
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 6 of 18
`
`U.S. Patent
`
`Dec. 6, 2011
`
`Sheet 3 of 7
`
`US 8,073,250 B2
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 7 of 18
`
`U.S. Patent
`
`Dec. 6, 2011
`
`Sheet 4 of 7
`
`US 8,073,250 B2
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 8 of 18
`
`U.S. Patent
`
`Dec. 6, 2011
`
`Sheet 5 of 7
`
`US 8,073,250 B2
`
`
`
`DIAMETER
`
`Dmax
`
`F.G. 5
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 9 of 18
`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 9 of 18
`
`U.S. Patent
`
`1m
`
`0
`
`US 8,073,250 B2
`
`#35:;D‘
`.q1n.6.,m32uy.8.50505025:;EEEw+x.uxW5.5:nz<um.3ESummon
`
`22:23
`
`mummm».00m
`
`moo
`
`mummam.
`
`VV
`
`
`
`(M$1.53A.59:Oz2......5umnEatonoz5.ozE.EmmmAa2.%3momoRmma
`
`«fl3H+x5.2353n59¢aa;x$.23.hauscramE.6.xmaiicbuuE...naixmagEEou“.2.
`
`
`
`f2%mm.03So
`
`7EcE..._._..:mmmEatonnEwanEH.uthan“.2.u55%
`
`auxoauxnduxacuxo
`out...HnEouE..vnE
`
`
`885m3§EEuuthhum
`
`«aurooz<ouxn
`
`._$83Athan
`
`OZmoo
`
`
`
` 6ozhyouA553mm;
`
`m.9”.
`
`
`
`20—556.—..uxEauhuudmmum:<wants—5mg...ban—Em<uZmUmm
`
`
`
`
`
` C;.x:
`
`zauu
`
`com
`
`
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 10 of 18
`
`U.S. Patent
`
`Dec. 6, 2011
`
`Sheet 7 of 7
`
`US 8,073,250 B2
`
`3O
`
`75
`
`700
`
`BFGN
`RECEIVE AS NPJT CRCEE
`PARAMETERS X, Y AND RAD
`705
`
`W = -RAD
`
`O
`
`NO
`
`YES
`Us: -RAD
`
`740
`
`Co-ed
`
`735
`
`U*U + VW & RAD*RAD 2
`
`745
`CBTAIN THE (R, G, B, COLOR
`WALUES FOR THE PIXELAT
`LOCATION (X+U, Y+V)
`
`
`
`750
`
`R> G AND R - B
`
`755
`MODFYR ACCORDNG TO
`EOUAONS2 AND 3
`
`F.G. 7
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 11 of 18
`
`US 8,073,250 B2
`
`1.
`METHOD AND SYSTEM FOR REMOVAL OF
`RED EYE EFFECTS
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`This application is a continuation application of commonly
`assigned U.S. patent application Ser. No. 1 1/175,551 filed on
`Jul. 5, 2005, now U.S. Pat. No. 7,324,689 and entitled
`METHOD AND SYSTEM FORREMOVAL OF RED EYE
`EFFECTS, which is a divisional of U.S. patent application
`Ser. No. 09/767,331 filed Jan. 22, 2001, which issued as U.S.
`Pat. No. 7,088,855 on Aug. 8, 2006, all of which are hereby
`incorporated herein in their entireties by reference.
`
`FIELD OF THE INVENTION
`
`5
`
`10
`
`15
`
`The present invention relates to apparatus and methodolo
`gies for red eye removal in photographs.
`
`2O
`
`BACKGROUND OF THE INVENTION
`
`Redeye removal in photographs is well known in the patent
`literature. The following U.S. patents are believed to repre 25
`sent the current state of the art:
`
`4,285,588
`4,315,204
`4,978,989
`5,130,789
`5,748,764
`5,990,901
`5,990,973
`6,009,209
`6,016,354
`
`August 1981
`February 1982
`December 1990
`July 1992
`May 1998
`November 1999
`November 1999
`December 1999
`January 2000
`
`Mir
`Abelson
`Nakano et al.
`Dobbs et al.
`Benati et al.
`Lawton et al.
`Sakamoto
`Acker et al.
`Lin et al.
`
`396,158
`514,400
`396,088
`358,500
`382,117
`345,429
`348,576
`382,275
`382,117
`
`30
`
`35
`
`When photographs are taken of people using a digital or
`traditional film camera with a flash, a common artifact that
`can appear in the picture is referred to as “red eye.” This 40
`artifact manifests itself as a red coloration within the iris of an
`eye, instead of the natural eye color, and is referred to as a
`“flash effect.
`Redeye is caused by the reflection of light from a flash off
`of the blood vessels of the retinas of a subject’s eyes. The size 45
`of the area affected by red eye increases with increased dila
`tion of the eye.
`One can try to reduce the red eye effect by increasing the
`light level in a room. Alternatively, one can have a subject
`look at a bright light, such as a room lamp, just before taking 50
`the flash picture. Both methods of redeye reduction described
`above cause the pupils of the Subject's eyes to contract,
`thereby reducing the amount of reflective surface.
`Reference is made to FIG. 1, which is a simplified line
`drawing showing a typical redeye artifact in a photograph. An 55
`area 110 corresponding to the iris of an eye, of blue colora
`tion, encompasses a pupil area 120 that exhibits redness.
`Within area 120 there is seen a small white flash area 130,
`which represents reflections of white light from the flash.
`Were it not for the red eye artifact, area 120 would appear 60
`similar in color to area 110, being part of the iris. Instead, the
`artifact gives it a red appearance.
`Interestingly, this flash effect appears as redeye in humans,
`but as yellow eye in dogs and cats, and as green eye in some
`other animals. Photographers and image compositors com- 65
`monly touch up their images and remove red eye flash effects
`from eyes.
`
`2
`Adobe Systems Inc.'s PHOTODELUXE(R) and Microsoft
`Corporation’s PICTURE ITR are digital photo-editing soft
`ware applications that offer semi-automatic red eye removal
`as a feature.
`
`SUMMARY OF THE INVENTION
`
`The present invention seeks to provide apparatus and a
`methodology for red eye removal in photographs, which is
`particularly suitable for Internet applications but may also be
`used for other photographic applications.
`There is thus provided in accordance with a preferred
`embodiment of the present invention a method of performing
`red eye correction in an image including partially automati
`cally defining an outline of an area in an image within which
`area red eye correction is to be carried out, and carrying out
`red eye correction only within the area.
`There is further provided in accordance with a preferred
`embodiment of the present invention a system of performing
`red eye correction in an image including a red eye area pro
`cessor partially automatically defining an outline of an area in
`an image within which area red eye correction is to be carried
`out, and a red eye correction processor carrying out red eye
`correction only within the area.
`There is yet further provided in accordance with a preferred
`embodiment of the present invention a method of performing
`red eye correction in an image including storing a high reso
`lution image on a server computer, transmitting a low reso
`lution image derived from the high resolution image, from the
`server computer to a client computer, displaying the low
`resolution image on a display device connected to the client
`computer, receiving from a user an indication of a selected
`location within the displayed low resolution image, partially
`automatically defining an outline of an area in the low reso
`lution image within which area red eye correction is to be
`carried out, by the client computer, based on the user's
`selected location, carrying out red eye correction on the low
`resolution image only within the area, by the client computer,
`and transmitting parameters of the area from the client com
`puter to the server computer.
`There is additionally provided in accordance with a pre
`ferred embodiment of the present invention a method of per
`forming red eye correction in an image including displaying
`an image on a display device, receiving from a user an indi
`cation of a selected location within the displayed image,
`partially automatically defining an outline of an area in the
`image within which area red eye correction is to be carried
`out, by the client computer, based on the user's selected
`location, carrying out red eye correction on the image only
`within the area, and transmitting parameters of the area to a
`server computer.
`There is moreover provided in accordance with a preferred
`embodiment of the present invention a method of performing
`red eye correction in an image including storing a high reso
`lution image, transmitting a low resolution image derived
`from the high resolution image, to a client computer, and
`receiving from the client computer parameters of an area in
`the low resolution image within which area red eye correction
`is to be carried out.
`There is further provided in accordance with a preferred
`embodiment of the present invention a system for performing
`red eye correction in an image including a server memory
`storing a high resolution image on a server computer, a server
`transmitter transmitting a low resolution image derived from
`the high resolution image, from the server computer to a
`client computer, a client display device connected to the client
`computer displaying the low resolution image, a client user
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 12 of 18
`
`US 8,073,250 B2
`
`4
`DETAILED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`The present invention provides a method and system for
`correction of red eye artifacts within digital images.
`Correction of red eye artifacts involves two primary stages:
`(i) identification of an area of pixel locations within a digital
`image that are affected by red eye artifacts, and (ii) correction
`of pixel color values within the identified area.
`Digital images are generally characterized by a two-di
`mensional array of picture elements, or “pixels. Each pixel
`corresponds to a location (x, y), where X and y are non
`negative integers, and includes a color value. A color value is
`typically a triple (R,G,B), where R, G and B are each 8-bit
`integers; i.e., non-negative integers taking values between 0
`and 255. R, G and B represent three primary additive color
`components, with Rindicating an amount of red, G indicating
`an amount of green, and B indicating an amount of blue.
`(R=0, G=0, B=0) corresponds to black, and (R=255, G=255,
`B-255) corresponds to white. Thus a digital image includes a
`two-dimensional array (R, G, B, 0<=x, y-255) of
`three-dimensional color vectors.
`In a preferred embodiment, the present invention operates
`by displaying a digital image and receiving an input from a
`user to identify a general position within the digital image
`wherein pixels affected by red eye are present. Specifically,
`the user clicks on a pixel location, denoted hereinbelow (Ix,
`Iy), within the image where there is redness in an eye.
`Reference is now made to FIG. 2, which is a simplified
`system diagram for a red eye removal system operating over
`the Internet, in accordance with a preferred embodiment of
`the present invention. Client computer 200 includes a user
`interface 205, which a user employs to view a digital image,
`stored in a client memory 210 and displayed on display device
`215, and to select a pixel location (IX, IY) within the digital
`image by means of input device 220. Input device 220 can be
`a mouse or a keyboard or another suitable device capable of
`selecting a point within a displayed image.
`User interface 205 transmits the coordinates (IX, IY) to red
`eye area processor 225. Redeye area processor 225 calculates
`the position and size parameters (X, Y, D) of a circle, such as
`circle 350 (FIG. 3), that tightly covers the pixels of the digital
`image that are affected by red eye, in the vicinity of the user
`selected location (IX, IY), as described in detail hereinbelow
`with reference to FIGS. 3-6 and Appendix A. Circle position
`and size parameters include the pixel location, (X,Y), of the
`center of the circle and its diameter, D, in pixel units. For
`purposes of clarity and ease of description, a circle is identi
`fied hereinbelow through parameters (X, Y, D), where (X,Y)
`denotes the pixel location of the center of the circle, and D
`denotes the size of its diameter in pixel units.
`A red eye correction processor 230 corrects red eye pixels
`of the digital image that reside within the circle having the
`position and size parameters (X, Y, D), as described herein
`below with reference to Appendix A.
`The digital image stored in memory 210 is preferably a low
`resolution version of a high resolution digital image that is
`stored in a memory 235 on a server computer 240. The low
`resolution digital image is transmitted from server computer
`240 to client computer 200 for storage in memory 210, and is
`suitable for display on display device 215. The low resolution
`digital image may be pre-stored on server computer 240, or
`may be dynamically computed from the high resolution digi
`tal image on the fly. Transmission of low resolution image
`data is ideal for Internet applications, since bandwidth is
`constrained.
`
`3
`interface on the client computer receiving from a user an
`indication of a selected location within the displayed low
`resolution image, a client red eye area processor partially
`automatically defining an outline of an area in the low reso
`lution image within which area red eye correction is to be
`carried out, by the client computer, based on the user's
`selected location, a client red eye correction processor carry
`ing out red eye correction on the low resolution image only
`within the area, by the client computer, and a client transmit
`ter transmitting parameters of the area from the client com
`10
`puter to the server computer.
`There is yet further provided in accordance with a preferred
`embodiment of the present invention a system for performing
`red eye correction in an image including a display device
`displaying an image, a receiver receiving from a user an
`indication of a selected location within the displayed image,
`a red eye area processor partially automatically defining an
`outline of an area in the image within which area red eye
`correction is to be carried out based on the user's selected
`location, a red eye correction processor carrying out red eye
`correction on the image only within the area, and a transmitter
`transmitting parameters of the area to a server computer.
`There is additionally provided in accordance with a pre
`ferred embodiment of the present invention a system for
`performing red eye correction in an image including a
`memory storing a high resolution image, a transmitter trans
`mitting a low resolution image derived from the high resolu
`tion image, to a client computer, a receiver receiving from the
`client computer parameters of an area in the low resolution,
`image within which area red eye correction is to be carried
`out, and a red eye correction processor performing red eye
`correction on the high resolution image, using the parameters
`of the area received from the client computer.
`
`5
`
`15
`
`25
`
`30
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`35
`
`The present invention will be understood and appreciated
`more fully from the following detailed description, taken in
`conjunction with the drawings in which:
`FIG. 1 is a simplified line drawing showing a typical red
`eye artifact in a photograph;
`FIG. 2 is a simplified system diagram for a redeye removal
`system operating over the Internet, in accordance with a pre
`ferred embodiment of the present invention.
`FIG.3 is a simplified line drawing showing stages in deter
`mining the location and size of a red eye removal circle in the
`photograph of FIG.1, in accordance with a preferred embodi
`ment of the present invention;
`FIG. 4 is a simplified line drawing showing another stage in
`determining the location and size of a red eye removal circle
`in the photograph of FIG. 1, in accordance with a preferred
`embodiment of the present invention;
`FIG. 5 is a sketch of the dependency of a threshold circum
`ference of a red eye area as a function of diameter, in accor
`dance with a preferred embodiment of the present invention;
`FIG. 6 is a simplified flowchart of an algorithm for deter
`mining the location and size of a red eye pixel, in accordance
`with a preferred embodiment of the present invention; and
`FIG. 7 is a simplified flowchart of an algorithm for correct
`ingredeye, inaccordance with a preferred embodiment of the
`present invention.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`LIST OF APPENDICES
`
`Appendix A is a listing of a Software function for perform
`ing red eye correction in accordance with a preferred embodi
`ment of the present invention.
`
`65
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 13 of 18
`
`US 8,073,250 B2
`
`6
`An advantage of Equation 1, as opposed to a simpler cri
`terion such as RO-G and R-B, is that it avoids the inclusion of
`skin tone colors in red eye pixels. Many skin tones have a
`reddish tint, and their color values (R,G,B) may satisfy RDG
`and R-B, but fail to satisfy Equation 1. If such colors were to
`be erroneously identified as red eye pixels, then the red eye
`pixels could “leak out of an eye and into the Surrounding
`skin. This would impact the algorithm described hereinbelow
`with reference to FIG. 3, and cause it to err by adjusting skin
`tone pixels.
`Reference is now made to FIG.3, which is a simplified line
`drawing showing stages in determining the location and size
`of a red eye removal circle in the photograph of FIG. 1, in
`accordance with a preferred embodiment of the present
`invention. To find a circular area of pixel locations that tightly
`covers the red eye pixels, the present invention preferably
`initializes a circle 310 having a center at pixel location (Ix,
`Iy), and typically having a diameter of four pixels. Location
`(Ix, Iy) is the location typically selected by the user using a
`mouse pointer 320. In a preferred embodiment the circle is
`automatically iteratively moved and enlarged until it reaches
`the boundaries of the red eye pixels.
`Specifically, in a preferred embodiment of the present
`invention, circle 310 is automatically adjusted by red eye area
`processor 225 for repositioning and resizing. Repositioning
`involves changing the center of circle 310 while keeping its
`diameter fixed, and resizing involves changing the diameter
`of circle 210 while keeping its center fixed. Preferably, circle
`310 is repositioned before being resized. Circle 310 is moved
`in the four directions North, South, East and West. Typically,
`the direction that produces the circle with the most red eye
`pixels on its periphery is selected for repositioning circle 310.
`When the circle is positioned such that no single proposed
`movement improves the number of red eye pixels on its
`periphery, then circle 310 is conditionally resized by increas
`ing its diameter, as described hereinbelow. Typically this
`eventually results in a larger circle 330.
`A condition for increasing the diameter of a circle is based
`on the percentage of red eye pixels in the periphery thereof. If
`the percentage falls below a minimum threshold, as described
`in detail hereinbelow with reference to FIG. 5, then the circle
`is not further expanded. Preferably, the minimum threshold is
`set to approximately 70%. Thus, as long as at least 70% of the
`circumference of the circle contains red eye pixels, the circle
`continues to expand. It may be appreciated that this criterion
`enables proper expansion, notwithstanding that the circle
`overlies the white flash area 130 (FIG. 1), as is the case with
`circle 330.
`Typically in this way, circle 330 eventually expands across
`white flash area 130 to reach circle 340, and eventually to
`reach circle 350. Circle 350 is the final circle, since expanding
`it further produces a circle whose boundary falls within area
`120 (FIG. 1), and contains very few red eye pixels.
`As will be explained hereinbelow, preferably the minimum
`threshold is variable.
`Reference is now made to FIG.4, which is a simplified line
`drawing showing another stage in determining the location
`and size of a red eye removal circle in the photograph of FIG.
`1, in accordance with a preferred embodiment of the present
`invention. Shown in FIG. 4 is an initial circle 410 that lies
`within the white flash area 130 (FIG. 1). Such an initial circle
`can arise when a user positions a mouse pointer 420 within
`flash area 130, thereby selecting an initial location (Ix, Iy)
`within area 130. In this case, the algorithm described herein
`above would not enable circle 410 to expand, since nearly all
`of the pixels on its periphery are white pixels. Should a circle
`having a size below a given threshold no longer expand, the
`
`10
`
`15
`
`25
`
`30
`
`35
`
`5
`Server computer 240 also contains a red eye correction
`processor 245, which can be used to perform on server com
`puter 240 the redeye correction performed by client computer
`200. Preferably, after a user performs red eye correction to the
`low resolution digital image on client computer 200, the
`results may be saved on server computer 240 for subsequent
`access. The client computer need not save the low resolution
`digital image or the circle position and size parameters (X,Y,
`D).
`A unique feature of the present invention is the ability to
`apply red eye correction across multiple resolutions of the
`same digital image. Thus, although circle position and size
`parameters (X, Y, D) are computed by red eye area processor
`225 based on pixel data from the low resolution image, the
`same circle can be scaled to a higher resolution and used to
`apply red eye correction to the high resolution image. Spe
`cifically, client computer 200 transmits the computed circle
`position and size parameters (X,Y, D) to server computer 240
`over the Internet, for storage in a circle position and size
`parameter memory 250, and red eye correction processor 245
`applies red eye correction to the high resolution digital image
`within a scaled version of the computed circle.
`In a preferred embodiment of the present invention, circle
`position and size parameters (X, Y, D) are expressed in reso
`lution-independent form, thus obviating the need to rescale
`the circle on server computer 240. Resolution-independent
`parameters are generally floating point numbers, typically
`based on a scale in which the image dimensions are 1.0x1.0.
`Thus it may be appreciated that resolution-independent
`parameters are effectively percentages of image width and
`image height. Alternatively, resolution-independent param
`eters can be based on a scale in which the Smaller dimension
`of the image is 1.0 and the larger dimension is determined
`based on the image aspect ratio; or vice versa, based on a scale
`in which the larger dimension of the image is 1.0 and the
`Smaller dimension is determined based on the image aspect
`ratio.
`It may be appreciated that the present invention enables
`server computer 240 to provide users with web based image
`editing services. Client computer accesses digital images
`residing on server computer 240, applies red eye correction to
`the images, and saves the results on server computer 240. Red
`eye corrections are then automatically applied whenever the
`user Subsequently accesses the digital images. Bandwidth
`45
`usage is minimized, since server computer only transmits low
`resolution image data to client computer 200, and client com
`puter 200 only transmits the circle position and size param
`eters to server computer 240.
`Identifying Red Eye Pixels
`The present invention preferably operates by finding a
`circular area of pixel locations that tightly covers the pixels of
`the eye affected by red eye. As a preliminary matter, it is
`necessary to identify, typically in terms of (R, G, B) color
`values, pixels whose colors are affected by red eye. The
`present invention preferably uses the criteria
`
`40
`
`50
`
`55
`
`to identify pixels affected by redeye (“red eye pixels'). Thus,
`for example, a pixel with color values (R=100, G=50, B=50)
`has sufficient red to be identified as a red eye pixel, whereas a
`pixel with color values (R=75, G=50, B-50) does not.
`Although red eye pixels are described above according to
`the conditions in Equation 1, it may be appreciated by those
`skilled in the art that other conditions on R, G and B may be
`used to determine whether the color values R, G and B cor
`respond to a red eye pixel.
`
`60
`
`65
`
`

`

`Case 1:20-cv-03128-ER Document 1-3 Filed 04/20/20 Page 14 of 18
`
`US 8,073,250 B2
`
`7
`present invention preferably initializes additional candidate
`circles 430 and 440, obtained by moving circle 410 slightly to
`the left and slightly to the right, respectively. One or more
`candidate circles whose periphery includes at least a thresh
`old percentage of red eye pixels generally expand to larger
`circles, using the algorithm described hereinabove, and even
`tually reach the same circle 350 (FIG. 3).
`Reference is made to FIG. 5, which is a sketch of the
`dependency of a threshold circumference of a red eye area as
`a function of diameter, in accordance with a preferred
`embodiment of the present invention. When initial circle 310
`is positioned within the red eye portion of the eye, because of
`its Small size, noise in the image may prevent its circumfer
`ence from containing Sufficient red eye pixels to overcome the
`minimum threshold percentage of 70%. Some of the red eye
`pixels in the circumference may not be strictly identified as
`red according to Equation 1 hereinabove, because of noise in
`the image or because the image is a low resolution image.
`To overcome this, the present invention tapers the mini
`mum threshold percentage so that below a pre-determined
`diameter, D, the minimum threshold percentage is not a
`constant, but instead varies proportionally with diameter.
`Since the circumference itself varies linearly with diameter,
`D, this induces a quadratically increasing threshold size, for
`values of D between 0 and D,
`and a linearly increasing
`threshold size thereafter, as indicated by respective segments
`510 and 520 in the graph of FIG. 5.
`Correcting Red Eye Pixels
`After a circle, such as circle 350 (FIG. 3) tightly covering
`the red eye pixels, is determined as above, the present inven
`tion preferably corrects the red eye pixels. A pixel with color
`value (R,G,B) with pixel coordinates (x+u, y+v) within the
`circle with parameters (x, y, d), for which RDG and R-B, is
`preferably corrected by modifying R to R', where R is given
`by
`
`5
`
`10
`
`15
`
`25
`
`30
`
`35
`
`8
`pixel coordinates received from user interface 205 (FIG. 2).
`At step 603 a counter. T, is initialized to zero. The counter is
`used as an index to an array SHIFTITI, which stores horizon
`tal shifts used as illustrated in FIG. 4 and described herein
`below.
`At step 606 a loop on T is entered, and variables are ini
`tialized as indicated. The term SHIFTT in the initialization
`of X takes values SHIFTO=0, SHIFT1=2, SHIFT2=-2,
`SHIFT3-4, SHIFT|4–4. Thus in the first pass through the
`loop, when T=0, the circle is not shifted. In the second pass
`through the loop, when T-2, the circle is shifted to the right by
`two pixel units. In the third pass through the loop, when T-3,
`the circle is shifted to the left by two pixel units. In the fourth
`pass through the loop, when T-4, the circle is shifted to the
`right by four pixel units. In the fifth pass through the loop,
`when T-4, the circle is shifted to the right by four pixel units.
`At step 609 a second loop, nested within the first loop, is
`entered, and variables DX and DY are initialized to zero. At
`step 612 the percentage of red eye pixels within the periphery
`of the circle with parameters (X,Y,D) is calculated and stored
`in the variable BESTFIT. At steps 615, 618 and 621 a deter
`mination is made whether shifting the circle up one pixel unit
`can increase the percentage ofred eye pixels within its periph
`ery. If so, DY is set to -1 and the value of BESTFIT is
`increased accordingly. Similarly, at steps 624, 627 and 630 a
`determination is made whether shifting the circle to the left by
`one pixel unit can increase the percentage of red eye pixels
`within its periphery. If so, DX is set to -1 and the value of
`BESTFIT is increased accordingly. Steps 633, 636 and 639
`test for a downward shift of the circle, and steps 642, 645 and
`648 test fo