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

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 2 of 21
`
`US007088855B1
`
`(12) United States Patent
`Vide
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,088,855 B1
`Aug. 8, 2006
`
`(54) METHOD AND SYSTEM FOR REMOVAL OF
`RED EYE EFFECTS
`
`(76) Inventor: Adolfo Pinheiro Vide, 21 Chemin
`Polisi. Donneville 31450 Montgiscard
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 415 davs.
`(b) by
`ayS
`(21) Appl. No.: 09/767,331
`
`(22) Filed:
`
`Jan. 22, 2001
`
`(51) Int. Cl.
`(2006.01)
`G06K 9/00
`(2006.01)
`G06K 9/40
`52) U.S. Cl. ....................................... 382/167; 38.2/275
`(58) Field of Classification Search ................ 382/115,
`382/117, 162, 167, 275: 396/158, 155; 348/370,
`348/576; 358/500, 509, 518, 527, 530
`See application file for complete search history.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,285,588 A
`8, 1981 Mir ............................ 396,158
`4,315,024 A
`2, 1982 Abelson
`4,315,204 A
`2, 1982 Sievers et al. ................ 322/28
`4,978,989 A * 12/1990 Nakano et al. .....
`... 396,88
`5,130,789 A * 7/1992 Dobbs et al. ............... 358,500
`5,748,764 A * 5/1998 Benati et al. ............... 382,117
`5.990,901 A * 11/1999 Lawton et al. .............. 345,581
`5.990,973 A * 11/1999 Sakamoto ................... 348,576
`
`w - J.
`
`Injo et al. ...
`
`- - -
`
`6,009,209 A * 12/1999 Acker et al. ................ 382,275
`6,016,354 A *
`1/2000 Lin et al. .......
`... 382,117
`6,285.410 B1* 9/2001 Marni .......
`... 348,576
`3.36. R. 1838.
`East - - - - -
`- - - is: t
`6,690,822 B1* 2/2004 Chen et al. ....
`... 382,162
`6,718,051 B1 * 4/2004 Eschbach ...
`... 38.2/117
`6,728.401 B1
`4/2004 Hardeberg .................. 382, 167
`ardeberg
`* cited by examiner
`Primary Examiner Andrew W. Johns
`Assistant Examiner—Amir Alavi
`(74) Attorney, Agent, or Firm Berkeley Law &
`Technology Group
`
`(57)
`
`ABSTRACT
`
`A method of performing red eye correction in an image
`including storing a high resolution image on a server com
`9.
`g a hig
`9.
`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 system is also described and claimed.
`
`76 Claims, 7 Drawing Sheets
`
`
`
`
`
`MPUTE WICE
`
`20 -
`CLENT COMPUTER
`
`205
`USERINTERFACE
`(X,Y)
`
`RED EYE AREA
`PROCESSOR
`
`230
`(X,Y,D)RED EYEcoRRECTION
`PROCESSOR
`
`
`
`
`
`
`
`
`
`
`
`
`
`-
`
`
`
`(X,Y,D)
`MEMORY FOR CRCE L'RED EYE CORRECTION
`POSION AND SE
`PROCESSOR
`
`250 eYD) it- MEMORY FOR HEG
`
`235
`
`RESOLUTION
`GA MAGE
`
`SERVER COMPUTER
`240 N-1
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 3 of 21
`
`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 1 of 7
`
`US 7,088,855 B1
`
`11 O
`
`
`
`13O
`
`FG. 1
`(PRIOR ART)
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 4 of 21
`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 4 of 21
`
`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 2 of 7
`
`US 7,088,855 B1
`
`Igems:
`zo_._.UmmmOQw>mcum8.56
`
`304m8$0532
`
`maga—4565
`
`20:.30mmm
`
`moEmmPEmum:
`
`(mad.m>m0mm
`
`mOmmMQOmm
`
`0mm
`
`
`
`1NTERNET
`
`{if I
`
`
`
`IQ:mo;$92M:
`
`
`
`mw¢§._<._._o_o
`
`zo_._.30mum
`
`zo_._.ummmoow>m0mm8.»..53050m0...EOSEE
`
`
`
`
`mammmoomn..mwwmoz<zoEmon.
`
`
`N.wE
`
`\\|/8m
`
`
`
`mmHDmEoumm>mmm
`
`mwm0mm
`
`iENHHLN!
`
`
`
`
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 5 of 21
`
`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 3 of 7
`
`US 7,088,855 B1
`
`
`
`X
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 6 of 21
`
`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 4 of 7
`
`US 7,088,855 B1
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 7 of 21
`
`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet S of 7
`
`US 7,088,855 B1
`
`
`
`DAMETER
`
`Dmax
`
`FG. 5
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 8 of 21
`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 8 of 21
`
`U.S. Patent
`
`02
`
`6
`
`US 7,088,855 B1
`
`a25E.8ea0.8mm.2uru3853232.2:;BEE+x.nxA5::52msnu:
`
`Emmzou535:2.
`
`«no.wm
`
`95mm;mom
`
`vn
`
`
`
`6_h.ntEhmumPEuEozéoz.3nmamop%mumRmm3
`anusouxnvuxaeta7:82u5.5%scramu55mmt3u.553mobu5.5%MSoon.So
`
`
`
`«\hv3Tx.“35.55".u.59».a»S“BaEEou:3aa.»xmasEEuu“5»
`
`ens
`
`
`
`HIEon>o.fins
`
`S.».§3<E.Ecu._._..:.mum
`
`ms
`
`0{ill}
`
`wmmmow
`
`22223dxa8533$3_
`
`
`
`mcmEEEE.55:m<”Sioux
`
`E.x:
`
`Euum
`
`cow
`
`H+onnime
`
`~on>nnz<cuxa
`
`53m
`
`“mm
`
`ozmoo
`
`
`
` 6oz.52AESEmm;
`
`
`
` .BAa$832.3memm»
`
`cwm
`
`m.0:
`
`
`
`
`
`
`
`
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 9 of 21
`
`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 7 Of 7
`
`US 7,088,855 B1
`
`AOO
`
`BEGIN
`RECEIVE AS INPUT CIRCLE
`PARAMETERS X, Y AND RAD
`
`
`
`75
`
`740
`
`35
`
`UU - W*V & RAD*RAD 2
`
`45
`OBTAIN THE (R, G, B) COLOR
`WALUES FOR THE PXELAT
`LOCATION (X+U, Y+V)
`
`750
`
`Ric G AND R v B
`
`
`
`
`
`755
`
`MODIFY RACCORDING TO
`EQUATIONS 2 AND 3
`
`FG. 7
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 10 of 21
`
`US 7,088,855 B1
`
`1.
`METHOD AND SYSTEM FOR REMOVAL OF
`RED EYE EFFECTS
`
`FIELD OF THE INVENTION
`
`The present invention relates to apparatus and method
`ologies for red eye removal in photographs.
`
`BACKGROUND OF THE INVENTION
`
`2
`There is thus provided in accordance with a preferred
`embodiment of the present invention a method of perform
`ing red eye correction in an image including partially
`automatically 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
`processor 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 pre
`ferred embodiment of the present invention a method of
`performing red eye correction in an image including storing
`a high resolution image on a server computer, 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.
`There is additionally provided in accordance with a
`preferred embodiment of the present invention a method of
`performing red eye correction in an image including dis
`playing an image on a display device, receiving from a user
`an indication 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 pre
`ferred embodiment of the present invention a method of
`performing red eye correction in an image including storing
`a high resolution 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 perform
`ing red eye correction in an image including a server
`memory storing a high resolution image on a server com
`puter, 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 reso
`lution image, a client user 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 resolution 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 carrying out red eye correction on the
`low resolution image only within the area, by the client
`computer, and a client transmitter transmitting parameters of
`the area from the client computer to the server computer.
`
`Red eye removal in photographs is well known in the
`patent literature. The following U.S. patents are believed to
`represent the current state of the art:
`U.S. Pat. No. 4,285,588 August 1981 Mir... 396/158
`U.S. Pat. No. 4,315,024 February 1982 Abelson. .. 514/400
`U.S. Pat. No. 4,978,989 December 1990 Nakano et al. . . .
`396/088
`U.S. Pat. No. 5,130,789 July 1992 Dobbs et al.... 358/500
`U.S. Pat. No. 5,748,764 May 1998 Benati et al.... 382/117
`U.S. Pat. No. 5,990,901 November 1999 Lawton et al. . . .
`345/.429
`U.S. Pat. No. 5,990,973 November 1999 Sakamoto . . .
`34.8/576
`U.S. Pat. No. 6,009,209 December 1999 Acker et al. . . .
`382/275
`U.S. Pat. No. 6,016,354 January 2000 Lin et al.... 382/117
`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
`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 of the area affected by red eye increases with increased
`dilation 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
`the flash picture. Both methods of red eye 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 red eye artifact in a photograph.
`An area 110 corresponding to the iris of an eye, of blue
`coloration, 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 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 red eye in
`humans, but as yellow eye in dogs and cats, and as green eye
`in Some other animals. Photographers and image composi
`tors commonly touch up their images and remove red eye
`flash effects from eyes.
`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.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`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.
`
`65
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 11 of 21
`
`US 7,088,855 B1
`
`4
`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
`dimensional 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 R indicating 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. Red eye 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 identified 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 here
`inbelow 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 digital image on the fly. Transmission of low
`resolution image data is ideal for Internet applications, since
`bandwidth is constrained.
`Server computer 240 also contains a red eye correction
`processor 245, which can be used to perform on server
`computer 240 the red eye 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
`
`3
`There is yet further provided in accordance with a pre
`ferred 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 auto
`matically 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
`preferred 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
`resolution 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.
`
`10
`
`15
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`25
`
`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 red eye
`removal system operating over the Internet, in accordance
`with a preferred embodiment of the present invention;
`FIG. 3 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:
`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
`circumference of a red eye area as a function of diameter, in
`accordance with a preferred embodiment of the present
`invention;
`FIG. 6 is a simplified flowchart of an algorithm for
`determining 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
`correcting red eye, in accordance with a preferred embodi
`ment of the present invention.
`
`LIST OF APPENDICES
`
`Appendix A is a listing of a software function for per
`forming red eye correction in accordance with a preferred
`embodiment of the present invention.
`
`DETAILED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`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
`
`65
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 12 of 21
`
`US 7,088,855 B1
`
`6
`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, ly), 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 embodi
`ment 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. Reposi
`tioning 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 condition
`ally resized by increasing its diameter, as described herein
`below. 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 expan
`sion, 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 even
`tually 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 mini
`mum 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 photo
`graph 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 hereinabove 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 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
`
`5
`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.
`Specifically, 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
`resolution-independent form, thus obviating the need to
`rescale the circle on server computer 240. Resolution
`independent parameters are generally floating point num
`bers, typically based on a scale in which the image dimen
`sions are 1.0x1.0. Thus it may be appreciated that
`resolution-independent parameters are effectively percent
`ages of image width and image height. Alternatively, reso
`lution-independent parameters 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 when
`ever the user Subsequently accesses the digital images.
`Bandwidth usage is minimized, since server computer only
`transmits low resolution image data to client computer 200,
`and client computer 200 only transmits the circle position
`and size parameters 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
`2R>3G+12, RB--12
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`(1)
`
`to identify pixels affected by red eye (“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
`correspond to a red eye pixel.
`An advantage of Equation 1, as opposed to a simpler
`criterion such as RaG and Rab, 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
`R>G and RZB, but fail to satisfy Equation 1. If such colors
`
`55
`
`60
`
`65
`
`

`

`Case 1:20-cv-03128-ER Document 1-2 Filed 04/20/20 Page 13 of 21
`
`US 7,088,855 B1
`
`10
`
`15
`
`7
`periphery includes at least a threshold percentage of red eye
`pixels generally expand to larger circles, using the algorithm
`described hereinabove, and eventually 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 circum
`ference from containing Sufficient red eye pixels to over
`come 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
`invention 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 RZ-G
`and Ra-B, is preferably corrected by modifying R to R',
`where R' is given by
`
`8
`The counter is used as an index to an array SHIFTITI, which
`stores horizontal shifts used as illustrated in FIG. 4 and
`described hereinbelow.
`At step 606 a loop on T is entered, and variables are
`initialized as indicated. The term SHIFTT in the initial
`ization of X takes values SHIFTO=0, SHIFT1=2, SHIFT
`|2=-2, SHIFT3–4, SHIFT4)=-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 periph
`ery of the circle with parameters (X, Y, D) is calculated and
`stored in the variable BESTFIT. At steps 615, 618 and 621
`a determination is made whether shifting the circle up one
`pixel unit can increase the percentage of red eye pixels
`within its periphery. 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 for a rightward shift. After
`completing step 648, the best unit pixel directional move
`ment (DX, DY), from among the four directions North,
`West, South and East, is known.
`At step 651, the values of X and Y are incremented by DX
`and DY, respectively. At step 654, a determination is made
`as to whether DX and DY still have their original values
`DX=0 and DY=0, that were set in step 609. If so, then this
`indicates that pixel location (X,Y) is a better center point for
`the circle than any of the four neighboring locations (X,
`Y-1), (X-1, Y), (X, Y+1) and (X, Y+1). In this case, the
`diameter, D, is increased by one pixel unit at step 657.
`At steps 660 and 663, a determination is made as to
`whether the percentage of red eye pixels in the periphery of
`the circle with parameters (X, Y, D) exceeds the minimum
`of (4D)% and 70%. The 70% threshold corresponds to the
`upper segment 510 in the graph of FIG. 5, and the (4D)%
`threshold corresponds to the lower segment 520 in the graph.
`If BESTFIT exceeds the (4D)% threshold or the 70%
`threshold, then control returns to step 609 for another
`iteration within the second loop. Otherwise, the second loop
`is exited, and control goes to step 666 where the counter T
`is incremented.
`At step 669 a determination is made as to whether T-5
`and Dk6. The condition DC6 means that the circle did not
`expand beyond a diameter of five pixel units during the
`iterations of the second loop. Such is the case, for example,
`when the initial circle is positioned like circle 310 (FIG. 3)
`within white flash area 130 (FIG. 1). In this