United States Patent 19
`Delp
`
`54 METHOD AND APPARATUS FOR THE
`EFFICIENT GENERATION OF HIGH
`QUALITY IMAGES IN A COMPUTER
`SYSTEM UTILIZNG AN
`NTERCONNECTED IMAGE STATE TABLE
`75 Inventor: Helen R. Delp, Rochester, Minn.
`73) Assignee: International Business Machines
`Corporation, Armonk, N.Y.
`(21) Appl. No.: 974,866
`22 Filed:
`Nov. 10, 1992
`51) Int. C. ................................................ GO6T 3/OO
`52 U.S. C. ..................................... 395/133; 395/136
`58) Field of Search ................................ 395/133-139,
`395/140, 141, 325; 358/426; 382/56
`References Cited
`U.S. PATENT DOCUMENTS
`5,065,447 11/1991 Barnsley et al. ...................... 382/S6
`5,226,125 7/1993 Balmer et al.....
`... 395/325
`5,245,441 9/1993 Ruben ................................. 358/426
`5,263,136 11/1993 DeAguiar et al. .................. 395/164
`Primary Examiner-Almis R. Jankus
`Attorney, Agent, or Firm-Richard E. Billion; Andrew J.
`Dillon
`ABSTRACT
`57
`A method and apparatus for the efficient generation of
`high quality images in a computer systemisprovided. A
`
`56
`
`USOO542.0967A
`5,420,967
`Patent Number:
`Date of Patent: May 30, 1995
`
`11
`45
`
`user requests that one or more images be generated.
`Representation of each requested image and any exist
`ing images are added to animage table. Representations
`of a group of intermediate images are then added to the
`image table. Each intermediate image corresponds to a
`change of an image state between an existing image and
`a requested image. For example, if a requested image is
`smaller than an existing image, the scaling of the exist
`ing image is a change of image state and will result in
`the addition of the representation of an intermediate
`image to the image table. Note that the intermediate
`image itself is not actually computed or generated at
`this time. After the representation of each intermediate
`image has been added to the image table, image paths
`are built from any existing image to any requested in
`age. An image path includes an existing image, a series
`of one or more intermediate images, and a requested
`image. After a network of all the image paths are built,
`a "cost of computing the image is calculated for each
`image path. After these calculations are complete, an
`optimal image path is selected. The requested image is
`then generated in a manner determined by the optimal
`image path. If more than one image is requested, the
`optimal image path for each requested image is deter
`mined by looking at combinations of image paths so that
`intermediate images generated for one requested image
`can be used by other requested images.
`
`21 Claims, 33 Drawing Sheets
`
`DeCopeSS
`
`30
`
`Correct
`Original
`COO
`
`3.
`
`Scale
`
`Match COO
`tO Display
`
`Convert
`to Display
`
`ROtate
`
`32
`
`33
`
`3.
`
`
`
`300
`
`Akamai Ex. 1008
`Akamai Techs. v. Equil IP Holdings
`IPR2023-00332
`Page 00001
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 1 of 33
`
`5,420,967
`
`Display 170
`
`Computer Systern 100
`System Unit 10
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PrOCeSSOr
`
`Inage AppS
`Image Midware
`Operating System
`Tables
`Matrices
`
`StO?age 150
`ImageS 51
`
`
`
`Keyboard 18O
`
`
`
`Device
`
`F.G.
`
`IPR2023-00332 Page 00002
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 2 of 33
`
`5,420,967
`
`0/Z
`
`---
`
`IIZ
`
`OIZ
`
`==
`
`IZZ
`
`997Z92
`
`[I] DE]
`
`I97
`
`09:2
`
`-
`
`o
`O
`CN
`
`IPR2023-00332 Page 00003
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 3 of 33
`
`5,420,967
`
`099.
`
`0/9.
`
`222
`
`ZI9.
`
`3I e OS
`
`SS9JCill103901
`
`009:
`
`IPR2023-00332 Page 00004
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 4 of 33
`
`5,420,967
`
`ANd-air R7
`GD -2
`S. st s Re 57 i
`Y (RN
`6 al
`-l o
`Y
`i
`2 U Et 22 E. t R | N
`s
`- W. al
`b
`| 2 || G-A-Y, i.
`G 6
`stilyar RN;
`S SA S L 0. AS
`EAAA).
`s NSLSSL
`glisler f;
`N
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`e
`
`N
`
`5
`
`
`
`
`
`IPR2023-00332 Page 00005
`
`

`

`U.S. Patent
`U.S. Patent
`
`May 30, 1995
`May 30, 1995
`
`Sheet 5 of 33
`Sheet 5 of 33
`
`5,420,967
`5,420,967
`
`FIG.4B
`
`Device1
`
`
`
`Decompress
`Device1Device2Device2MatchforCorrectforConverttoConverttoOriginal
`
`
`
`
`\
`
`Feee"
`
`Correct
`
`IPR2023-00332 Page 00006
`
`IPR2023-00332 Page 00006
`
`

`

`U.S. Patent
`U.S. Patent
`
`May 30, 1995
`May 30, 1995
`
`Sheet 6 of 33
`Sheet 6 of 33
`
`5,420,967
`5,420,967
`
`opSildaLaoqaad=2aotAadBOTAAT«=B9TAaM§=—-Z_[eUIBTIO
`
`
`
`
`
`
`02JJ9AU0}02WJBAUO}JO}39910}JOSYDIeW39910)ssasawosag
`0z©ooHe}a.
`
`Ne7He93€30y3129S
`IeO|ieSTcZI
`
`
`
`Q6!
`
`¢zI
`
`I
`
`On
`
`O}—0¢
`
`l@~¢z
`
`IPR2023-00332 Page 00007
`
`IPR2023-00332 Page 00007
`
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 7 of 33
`
`5,420,967
`
`Scale State Table
`
`l
`3
`l
`
`
`
`Rotation State Table
`
`
`
`2
`
`90 degrees CCW
`normal Viewing
`
`FIG. 5B
`
`
`
`520
`Match State Table 510
`Color
`Non-Linear
`Matrix ID
`Table ID
`gama 1.
`Nikon SCanner
`gamma 2.7
`609 monitor
`gamma 2.2
`854 monitor
`
`2
`3
`
`Valid
`Conversion States
`
`1,2
`1,3
`
`FIG.5C
`
`IPR2023-00332 Page 00008
`
`

`

`U.S. Patent
`
`May30, 1995
`
`Sheet 8 of 33
`
`5,420,967
`
`
`
`
`
`
`
`
`
`G60nIZSTS8Z0S60"COSZLOST£S8T8E901ZZ0S60nBHhZSBETOS9LEZOn
`
`Ig‘Sls
`
`G1Xf47eW1010)
`OnI'TS6T"-£S0°0TZ0‘OST9'T828"-26e*-GOE*T-O£L9°2
`
`
`
`
`
`
`q¢old
`
`9SSis
`
`
`
`ajqel93231ed
`
`[9XTd/S9LAG
`Jeault]-uoN
`
`
`
`
`
`Ossa1qe]a3e}$UOTSJaAU0}
`
`
`
`JouzIpa[ge}a3}a[ed|asnjj{p-s0149¢9[qe]JOYYIPcauouauOUT
`
`
`
`
`
`IPR2023-00332 Page 00009
`
`IPR2023-00332 Page 00009
`
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`May30, 1995
`May 30, 1995
`
`Sheet 9 of 33
`Sheet 9 of 33
`
`5,420,967
`5,420,967
`
`FIG.5E-I
`
`1 1 1 2 3 3 2 1 2 3 3 2 1 2 3 3 2 1 2 3
`N My NY N m N NY NY N
`N NY NY N CN NY
`m
`
`J' d
`
`|'
`
`-~—
`e
`
`©co
`
`561
`
`550
`
`g
`Te:
`e g
`ImaTab
`
`s s r c N e g
`11 12 13 14 15 16 17 18 19
`
`IPR2023-00332 Page 00010
`
`compress|rangejcorrectjcorrect
`
`
`
`
`
`ynamicgamma|sigma
`aeestatus
`
`
`|jstate(state|state|state
`
`o
`8.
`nmet
`gu
`le
`O
`
`m O
`
`=© +o
`
`O@=f
`
`U
`Gs
`le
`on
`e
`°o
`O
`oO
`9
`
`
`
`&&
`582583
`
`3.
`581
`
`5645/0
`
`563
`
`562
`
`IPR2023-00332 Page 00010
`
`

`

`USS. Patent
`U.S. Patent
`
`May 30, 1995
`May30, 1995
`
`Sheet 10 of 33
`Sheet 10 of 33
`
`5,420,967
`5,420,967
`
`FIG.SE-2
`
`Y Y Y Y Y
`
`MM MM AN
`
`S a. & S. Q S N & & S ir SN R R R RS g SR S. s
`oneon &
`35 36 37
`38 39 40 4}
`20 21 22 23 24 25
`NN AEN NY 31 32 33 34
`
`IPR2023-00332 Page 00011
`
`IPR2023-00332 Page 00011
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 11 of 33
`
`5,420,967
`
`
`
`Path Inage Sequence
`
`Deterioration
`
`
`
`
`
`
`
`
`
`
`
`
`630
`
`640
`
`IPR2023-00332 Page 00012
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 12 of 33
`
`5,420,967
`
`
`
`
`
`Non-Linear Table
`2
`O
`O
`O
`9
`8
`6
`3
`l
`22
`19
`16
`2
`14
`34 38
`28
`3.
`24
`53
`58
`ls
`49
`4.
`76
`8.
`7.
`62
`67
`105 108
`92
`97
`86
`33 39
`14.
`26
`20
`166 73
`159
`52
`45
`202 2.0
`187
`195
`180
`242 250
`234
`225
`28
`28, 293
`276
`267
`258
`330 340
`321
`302
`3.
`379 389
`359
`369
`3.49
`l30 44
`l2O
`399
`409
`l85 496
`465
`l/l
`452
`543 554
`519
`53
`508
`605 615
`59
`578
`566
`666 679
`628
`653
`640
`732 745
`78
`705
`692
`800 84
`773
`786
`7.59
`872 886
`829
`845
`857
`946 96.
`.96
`93.
`90.
`991 1007 1022 1038
`
`FIG.5H
`
`054 1070
`3, 15
`127 1234
`1503 320
`59 1409
`1482 1500
`1575 1594
`167. 1690
`769 1789
`1870 1890
`1973 1994
`2079 200
`2187. 2209
`2298 2320
`24, 234
`2526 2550
`2644 2668
`2764. 2788
`2887 29.
`302 3037
`3139 365
`3268 3295
`3400 3427
`3535 3562
`367, 3699
`380 3838
`395 3980
`O95
`
`1086 102 18
`167 184 120
`1251 1268 1286
`1338 1356 373
`127 lb 463
`1519 1537 1556
`65 1632 1652
`1710 1730. 1749
`1809 829 850
`191 932 1952
`2015 2036. 2058
`222 2144, 265
`2231, 2253 2275
`2343 2365 2388
`2457 2480 2503
`2573 25972620
`2692 2716 2740
`283 2837 2862
`2956 2961 2986
`3062 3O88 315
`3190 326 322
`3.321 3347 337
`3.454 348 3508
`3589 366 3644
`3726 3754 37.82
`3866 3894 3923
`4008 4057 066
`
`IPR2023-00332 Page 00013
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 13 of 33
`
`5,420,967
`
`Dither Table
`
`0 0 0
`55 5
`555
`6555
`6 555
`6 55 6
`6 55 6
`6 6 5 6
`6 6 5 6
`6 6 6 6
`6 6 6 6
`6 6 6 6
`6 6 6 6
`7 6 6 6
`7 6 6 6
`7 6 6 6
`7 6 6 6
`7 6 6 7
`7 6 6 7
`7 6 6 7
`7 6 6 7
`
`9 9 9
`O
`9 910
`O
`O 9 10
`O
`0 0 10
`O
`0 0 10
`0 0 10
`1010 11
`10 11
`10
`11 11
`
`2
`12
`12
`2
`2
`12
`2
`2
`
`11
`
`11 2
`1 11 12
`2
`2
`2
`2
`212 2
`22 12
`
`31 31 31 31
`31 31 31 31
`3. 31. 3 31
`
`65 63 65 65
`63 63 63 63
`63 63 63 63
`
`3. 31 31 3
`31 31 31 31
`31 31 31 31
`
`FIG.5J
`
`IPR2023-00332 Page 00014
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 14 of 33
`
`5,420,967
`
`Adjacency Matrix of COmputation COStS
`
`
`
`F.G. 6A
`
`IPR2023-00332 Page 00015
`
`

`

`U.S. Patent
`
`May30, 1995
`
`Sheet 15 of 33
`
`5,420,967
`
`
`
`FIG. 6A-2
`
`IPR2023-00332 Page 00016
`
`IPR2023-00332 Page 00016
`
`

`

`U.S. Patent
`U.S. Patent
`
`May 30, 1995
`May30, 1995
`
`Sheet 16 of 33
`Sheet 16 of 33
`
`5,420,967
`5,420,967
`
`
`
`2} |tt
`
` mWworem©mwAMeNM
`
`
`>©Mm+
`
`FIG.6A-3
`FIG. GA-3
`
`IPR2023-00332 Page 00017
`
`IPR2023-00332 Page 00017
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`May 30, 1995
`May30, 1995
`
`Sheet 17 of 33
`Sheet 17 of 33
`
`5,420,967
`5,420,967
`
`
`
`
`
`FIG. 6A-4
`FIG. 6A-4
`
`IPR2023-00332 Page 00018
`
`IPR2023-00332 Page 00018
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 18 of 33
`
`5,420,967
`
`Adjacency Matrix of image deterioration
`
`p={
`
`
`EITT TETITETTIIIIIIIIIL
`
`• TITETTE-TTTTTT TILLLLLLLL
`
`„ETTTTTTTTTTTTT-III-ILL
`•TTTTTTTTTT-III-III-III-L
`
`
`
`•!<nº L^ uo ?º oo on ©
`
`
`
`--ETTTTTTTTTTTTTTT TILL
`
`SETTTTTTTTTTT-II-III-ILL •FETTTTTTTTTTTTTTILLLL
`AFTETTTTTTTTTTTIILILL
`
`
`•FETTTETTTTTTTTTILLLL
`
`s?ETTTTTTTTTTTTTILLLLLL
`=TITTETETTTTTTTTIILIL
`
`•!
`
`! !!
`
`?o FTETTTTTTTTT-EITLLLLLLL
`
`=FTETTTTTTTELITTILLLL
`
`sr
`
`•4
`
`!=! ?a FTTTTTTTTTTTEETILLLL
`
`SITTITETTITEITLIITILL
`?e[TTTTTTTTTTTEFILDELILL
`
`w=!
`
`TTTTTTETTITTEITEITL
`
`
`
`FIG. 6B
`
`IPR2023-00332 Page 00019
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 19 of 33
`
`5,420,967
`
`
`
`TTTTTTTTTTTTIILLEL
`
`FEL
`
`F.G. 6B-2
`
`IPR2023-00332 Page 00020
`
`

`

`U.S. Patent
`U.S. Patent
`
`May30, 1995
`May 30, 1995
`
`Sheet 20 of 33
`Sheet 20 of 33
`
`5,420,967
`5,420,967
`
`2 l
`
`
`
`
`
` mEPittttttyteteitt
`
`40
`41
`
`FIG. 6B-3
`FIG. 6B-3
`
`IPR2023-00332 Page 00021
`
`IPR2023-00332 Page 00021
`
`

`

`U.S. Patent
`U.S. Patent
`
`May 30, 1995
`May 30, 1995
`
`Sheet 21 of 33
`Sheet 21 of 33
`
`5,420,967
`5,420,967
`
`-
`
`- 11
`-
`T
`
`
`
`0
`3 || 0
`
`
`
`-
`
`||
`- 9
`-
`
`
`
`
`
`
`
`-
`
`o
`to
`To
`- 11
`3
`-
`
`
`
`
`
`FIG.6B-4
`FIG. 6B-4
`
`IPR2023-00332 Page 00022
`
`IPR2023-00332 Page 00022
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 22 of 33
`
`5,420,967
`
`Start
`
`100
`
`Create Scale Table
`for all existing and
`requested images
`
`003
`
`Create Match Table
`for all existing and
`requested images
`
`1005
`
`Create ROtation Table
`for all existing and
`requested images
`
`1008
`
`Create ConVersion Table
`for all existing and
`requested images
`
`OO
`
`05
`
`Add existing and
`requested inages
`tO Image Table
`
`RenOve duplicates
`from Image Table
`
`State cominations S-6
`
`1 intermediate
`image exist in Image
`Table
`
`1045
`
`
`
`NO
`Add intenediate
`image to Image Table
`
`
`
`
`
`More
`
`
`
`NO
`GA)
`FG 7A-
`
`IPR2023-00332 Page 00023
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 23 of 33
`
`5,420,967
`
`GA)
`
`ReOve imageS from
`Image Table if
`Conversion state
`not Valid
`
`1047
`
`Create Adjacency
`Matrices for Cost
`and Deterioration
`
`1050
`
`Call Simplify
`SSY Matrix
`routine (Fig. 8)
`
`2000
`
`Assign element in
`adjaCenCy Tatrix
`for each COnnection
`between images after
`Simplification
`
`1060
`
`Call CalCulate
`COSt Subroutine
`(Fig. 9)
`
`3000
`
`Fill in adjacency
`matrix for COSt
`for each assigned
`element
`
`1070
`
`
`
`
`
`Call Cal Culate
`Deterioration
`Subroutine (Fig. 10)
`
`Fill in Deterigration
`adjacency matrix for
`each assigned element
`
`4000
`
`1080
`
`GB)
`
`FIG. 7A-2
`
`IPR2023-00332 Page 00024
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 24 of 33
`
`5,420,967
`
`
`
`00
`
`More
`NO equesteg images
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`More
`existing imageS
`
`Find lowest deterioration
`Value among all paths to
`this requested image
`
`Add entry in Path
`Table for each path
`from existing to
`requested image
`
`Calculate
`deter Oration
`Value along
`each path
`
`
`
`Is
`lOWest deterioration
`Value >tyreshold
`
`Delete all paths to
`requested inage
`that exceed
`deterioration
`threshold
`
`
`
`FIG. 7B
`
`IPR2023-00332 Page 00025
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 25 of 33
`
`5,420,967
`
`200
`
`More
`NO path Combinations
`
`
`
`
`
`
`
`Redundant Steps
`in path cgmbination
`
`
`
`ASSign COSt
`for redundant
`
`Cal Culate COInputation
`COSt for each path
`COmbination
`
`
`
`
`
`
`
`Best
`Path Comination
`
`More
`equesteg images
`
`
`
`Save best
`path CObination
`
`5000
`
`Call Compute
`Image Subroutine
`(Fig. 1)
`
`FIG. 7B-2
`
`IPR2023-00332 Page 00026
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 26 of 33
`
`5,420,967
`
`Simplify Adjacency
`Mat
`S-langes
`existing image
`
`2000
`-
`
`-
`
`-
`
`Slid it Uld
`d US)
`existing image
`
`22
`
`Eliminate elements
`representing images
`SCaled up from Size
`Other than next
`Smallest size
`
`
`
`2003
`
`d
`Eliminate elements
`representing imageS
`SCaled down from Size
`larger than largest
`existing image
`
`200l.
`
`Eliminate elements
`representing images
`Scaled down from Size
`larger than next largest
`Size that doesn't have
`an existing image
`
`FIG. 8
`
`2002
`
`2010
`
`
`
`
`
`
`
`
`
`
`
`
`
`Eliminate elements
`representing imageS
`Scaled Or matched from
`Converted inageS
`
`2005
`
`Eliminate elementS
`representing imageS
`that match from a CO. Of
`State that doesn't have
`an existing image, Of
`to a Color State that
`doesn't have a requested
`image
`
`2008
`
`
`
`Eliminate elementS
`representing imageS
`that rotate from a
`State that doesn't
`have an existing
`image, Of tO a State
`that doesn't have
`a requested flage
`
`2099
`
`IPR2023-00332 Page 00027
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 27 of 33
`
`5,420,967
`
`
`
`Cost = Width
`* Heights
`9,6E-05
`
`CoSt = Width
`* Height of
`Output inage
`it 2.6E-05
`
`COSt = Width
`Height of
`input image it
`2.6E-05
`
`FIG. 9A
`
`IPR2023-00332 Page 00028
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 28 of 33
`
`5,420,967
`
`COSt = Width
`* Height it
`Bytes/pixel it
`3E-05 + 5
`
`CoSt = Width
`* Heightt
`
`Cost = Width
`* Height:
`6E-Ol
`
`3030
`Rotatg Step
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ConVersiOn
`Stgp
`
`FIG. 9B
`
`IPR2023-00332 Page 00029
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 29 of 33
`
`5,420,967
`
`
`
`Calculate
`Deterioration
`Subroutine
`
`
`
`
`
`1005
`
`Element
`tO prgcess
`
`
`
`
`
`Deterioration = 1
`
`FIG. OA
`
`IPR2023-00332 Page 00030
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 30 of 33
`
`5,420,967
`
`
`
`Error -- Step
`not Supported
`
`FIG. OB
`
`IPR2023-00332 Page 00031
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 31 of 33
`
`5,420,967
`
`COInpute Image
`
`stopsis-soo
`
`5010
`
`IS
`image copressed
`
`
`
`YeS
`
`5O15
`DeCOInpreSS Image
`
`
`
`NO
`
`
`
`5020
`COrrect
`original, Col Or
`
`
`
`NO
`
`5025
`
`Yes Perform dynamic
`range, ga? a COrrection,
`and / Or Signa COrrection
`
`
`
`5030
`More
`NO<steps in path
`
`Perfor linear
`transformation
`On image
`
`NO
`
`5080
`Requested
`Mage copressed
`
`o
`
`
`
`NO
`
`5085
`
`GA)
`
`(B)
`FIG. A
`
`(C)
`
`IPR2023-00332 Page 00032
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 32 of 33
`
`5,420,967
`
`
`
`
`
`5095 3G>
`
`5096
`
`5050 <Gs NO
`
`5055
`
`
`
`
`
`5065
`
`
`
`
`
`
`
`bisplay, images
`
`YeS
`
`
`
`Display images
`
`
`
`
`
`
`
`
`
`
`
`506O NO
`
`COnVert
`image to deViCe
`(esolytion
`
`
`
`
`
`rform halftoning
`Pe
`thering, and/or
`(d
`ffusing
`di
`
`
`
`
`
`FIG. IB
`
`IPR2023-00332 Page 00033
`
`

`

`U.S. Patent
`
`May 30, 1995
`
`Sheet 33 of 33
`
`5,420,967
`
`
`
`REQUEST IMAGE
`
`========= D 1024
`Image Height
`========= d. 768
`Image Width
`=========> IBM 8514 Display
`DeVice
`========= > Normal Viewing
`Orientation
`Quality Threshold ========= D 15
`Save Requested Image ====== > Y
`Save Intermediate ImageS == > N
`Display Requested ImageS
`Gama Correction ======== > 1.4
`Signa Correction
`======== > 0
`Dynamic Range Adjust ====== > Y
`
`F6 = Send all requests F10 = Request Another Image
`
`FIG.2
`
`IPR2023-00332 Page 00034
`
`

`

`1.
`
`METHOD AND APPARATUS FOR THE
`EFFICIENT GENERATION OF HIGH QUALITY
`IMAGES IN A COMPUTER SYSTEM UTILIZNG
`AN INTERCONNECTED IMAGE STATE TABLE
`
`5
`
`10
`
`15
`
`5,420,967
`2
`ated. This failure has resulted in a shared hesitancy
`among both users and application developers to fully
`adopt and embrace this new technology.
`SUMMARY OF THE INVENTION
`It is a principle object of the invention to efficiently
`generate high quality images in a computer system.
`These and other objects are accomplished by the
`method and apparatus for the efficient generation of
`high quality images in a computer system disclosed
`herein.
`A method and apparatus for the efficient generation
`of high quality images in a computer systemis disclosed.
`A user requests that one or more images be generated.
`Representation of each requested image and any images
`that already have been generated and stored are added
`to an image table. Representations of a group of inter
`mediate images are then added to the image table. Each
`intermediate image corresponds to a change of an image
`state between an existing image and a requested image.
`For example, if a requested image is smaller than an
`existing image, the scaling of the existing image is a
`change of image state and will result in the addition of
`the representation of an intermediate image to the image
`table. Note that the intermediate image itself is not actu
`ally computed or generated at this time.
`After the representation of each intermediate image
`has been added to the image table, image paths are built
`from any existing image to any requested image. An
`image path includes an existing image, a series of one or
`more intermediate images, and a requested image. After
`a network of all the image paths are built, a "cost' of
`computing the image is calculated for each image path.
`After these calculations are complete, an optimal image
`path is selected. The requested image is then generated
`in a manner determined by the optimal image path. If
`more than one image is requested, the optimal image
`path for each requested image is determined by looking
`at combinations of image paths so that intermediate
`images generated for one requested image can be used
`by other requested images.
`BRIEF DESCRIPTION OF THE DRAWING
`FIG. 1 shows a block diagram of the computer sys
`tem of the invention.
`FIG. 2 shows a prior art method of generating a
`series of images
`FIG.3 shows a simplified representation of the gener
`ation of a series of images using the method of the in
`vention.
`FIGS. 4A-4C show a more detailed representation of
`the generation of a series of images using the method of
`the invention. FIGS. 5A-5J show tables defining pa
`rameters used in practicing of the invention.
`FIGS. 6A-6B show the matrices of image cost and
`deterioration of the invention.
`FIGS. 7A-7B, and 8-11 show the flowcharts of the
`invention.
`FIG. 12 shows an exemplary display screen of the
`invention.
`DESCRIPTION OF THE PREFERRED
`EMBODMENT
`FIG. 1 shows a block diagram of computer system
`100 of the invention. Computer system 100 has display
`170, keyboard 180, and input device 190, each of which
`is connected to system unit 110. System unit 110 con
`
`FIELD OF THE INVENTION
`This invention relates to the data processing field.
`More particularly, this invention relates to the efficient
`generation of high quality images in a computer system.
`BACKGROUND OF THE INVENTION
`General purpose computer systems of yesteryear
`were largely limited to the display of textual informa
`tion. In fact, the early computer displays were incapable
`of displaying anything other than words, or crude
`drawings made from text related symbols commonly
`found on a keyboard, such as “:-)’. While text and silly
`symbols were just fine for some people, many people
`with expressive personalities wanted the ability to dis
`20
`play real graphics on their computer display. Gradu
`ally, computer displays started supporting graphics.
`Early graphics were displayed in what became known
`as "CGA mode” CGA mode divided the computer
`display up into rows of 640 pixels and columns of 200
`25
`pixels. While images displayed in CGA mode were
`relatively easy to generate and display since they did
`not require a tremendous amount of data, the resolution
`of an image displayed in CGA mode was grainy and
`only of marginal quality.
`30
`Users quickly became dissatisfied with the quality of
`CGA mode monitors, and began demanding something
`better. EGA mode increased the resolution of the image
`to 640x350 pixels, but users still weren't very happy.
`When VGA mode increased the resolution to
`35
`640x480 pixels, users started to realize that their com
`puters were now capable of displaying high quality
`images, either still or animated. This realization opened
`up a whole new computer market now commonly (if
`imprecisely) known today as "multimedia”. Images of
`40
`near photographic quality are now finding their way
`onto CD-ROM collections of images relating to a par
`ticular subject matter, and into application programs
`themselves, such as multimedia encyclopedias.
`Technology marched on, and monitors supporting
`SVGA mode (768x1024 pixels) are now commonly
`available. Users have fallen in love with the power and
`pizzazz of multimedia, and want to display as many
`images as possible. The problem is that an SVGA image
`takes up a tremendous amount of storage space, and can
`50
`take a considerable amount of computer processing
`power to generate. It is not uncommon for even high
`powered computers to take several seconds or even
`minutes to generate a single image. Many users find this
`response time unacceptable, since they are used to sub
`55
`second response time commonly achieved in the much
`simpler world of text processing. Storing every image
`the user could possibly want to display on a high speed
`storage medium would be nice in theory, but lacks prac
`ticability due to the multitude of ways a single image
`can be displayed (rotated, scaled, reverse image, etc), to
`the variation in the capabilities of individual displays,
`and to the massive amount of storage required to even
`contemplate such a thing.
`For now, users feel a sense of frustration. They see
`that this amazingly powerful multimedia technology is
`just outside their grasp, due to the inefficient manner in
`which high quality images are currently being gener
`
`IPR2023-00332 Page 00035
`
`

`

`5
`
`5,420,967
`3
`4.
`tains processor 120 connected to memory 140, storage
`color, matched to the color of the display, converted to
`130, and display adapter 160. Processor 120 is suitably
`the resolution of the display, and rotated. Those skilled
`programmed to carry out this invention, as described in
`in the art will appreciate that while it may be possible to
`leave out some of these steps in a particular implementa
`more detail in the flowcharts of FIGS. 7-11. Memory
`140 contains matrices 141, tables 142, operating system
`tion, a high quality image of the desired size and orienta
`143, image midware 144, and one or more image appli
`tion requires these or similar steps. Images 310-314 are
`cations 145. Storage 130 contains existing images 131.
`not temporary images like the prior art, but are instead
`In the preferred embodiment, computer system 100 is
`intermediate images that are not discarded until after
`an IBM PS/2, where processor 120 is an Intel 80486DX
`images 350, 360, and 370 are all created, and may even
`microprocessor. Display adapter 160 is an IBM SVGA
`be optionally saved after this time as well. Requested
`O
`display adapter, and display 170 is an IBM 8515 display.
`image 360 is not created from compressed image 300 as
`Input device 190 is preferably an IBM mouse but may
`in the prior art, but instead is created from intermediate
`also be a track ball, light pen, or other input device.
`image 312. Intermediate image 312 is scaled, matched to
`Storage 130 is preferably a conventional magnetic stor
`the color of the display, converted to the resolution of
`age device, but could also be a read/write optical de
`the display, and rotated. Intermediate images 322-324
`15
`vice, tape device, or other high speed storage device.
`are created in the process of generating requested image
`Operating system 143 is preferably OS/2 2.0 with Pre
`360. Since image 360 has been prepared for a different
`sentation Manager, but could be Microsoft Windows
`device than image 350, intermediate images 313 and 314.
`3.1, or another operating system. Tables 142 are shown
`could not have been used to prepare image 360.
`Requested image 370 is not created from compressed
`in more detail in FIG. 5. Matrices 141 are shown in
`20
`more detail in FIG. 6. Image midware 144 is a software
`image 300 as in the prior art, but instead is created from
`program suitably programmed to cause processor 120
`intermediate image 323. Intermediate image 323 is
`to execute the flowcharts of FIG. 7-11. Image applica
`scaled, converted to the resolution of the display, and
`tions 145 use image midware 144 to generate images
`rotated. Intermediate images 333-334 are created in the
`used by the application program.
`process of generating requested image 370. Although
`25
`Computer system 100 could also be another type of
`image 370 has been prepared for the same device as
`computer system, whetherit be another microcomputer
`image 360, and intermediate image 324 could have been
`such as an Apple Macintosh, a minicomputer such as an
`used to generate image 370 instead of intermediate
`IBM AS/400, or a mainframe computer such as an IBM
`image 323, the preferred embodiment does not use this
`System/390, and still fall within the spirit and scope of
`intermediate image, since scaling an image that has
`30
`this invention. In addition, computer system 100 can be
`already been converted to the resolution of a device
`a microcomputer such as described above, connected to
`yields poor quality. The generation of images 350, 360,
`a larger computer system such as an IBM AS/400. If
`and 370 in the preferred embodiment requires the exe
`connected to a larger system, processor 120 may share
`cution of thirteen highly computational intensive steps,
`responsibilities for executing the flowchart of FIGS.
`five fewer steps than was required in the prior art gener
`35
`7-11 with one or more other processors (not shown)
`ation of images 250, 260 and 270. This reduction of these
`contained in the larger system. Storage 130 and/or
`steps resulted in much faster processing time, without
`sacrificing image quality.
`memory 140 could also be distributed to other systems
`connected to computer system 100.
`FIGS. 4A-4C show a more complex representation
`FIG. 2 shows a prior art method of generating a
`of the generation of a series of images using the method
`40
`series of images. Image 200 is an existing compressed
`of the invention. FIG. 4A shows existing images 0 and
`image. High quality images 250, 260, and 270 are to be
`25, which have already been generated and stored and
`generated from this compressed image. In order togen
`requested images 11, 20, 30, and 40. The remainder of
`erate high quality image 250, image 200 must first be
`the images are representations of intermediate images
`decompressed, corrected to the original color (also
`that could be generated, if chosen as part of an optimal
`45
`known as dynamic range adjust, input gamma correct,
`path, to produce the requested images. Note that the Y
`and/or sigma correct), scaled to the correct size,
`axis of FIG. 4A indicates scaling, the Z axis indicates
`matched to the color of the display (also known as
`rotation, and the X axis indicates the rest of the image
`linear transformation), converted to the resolution of
`operations (correct, match, convert) for two different
`the display (also known as halftoning, dithering, and/or
`devices.
`50
`diffusing), and rotated. After image 250 is generated,
`Each image shown in FIG. 4A represents an image
`temporary images 210-214 are discarded.
`state. As will be described in more detail later, the in
`Generating image 260 again requires that compressed
`vention forms a logical connection between each image
`image 200 be decompressed, scaled to the correct size,
`state that differs from another image state by one opera
`corrected to the original color, matched to the color of
`tion. For example, image 7 is logically connected to
`55
`the display, converted to the resolution of the display,
`image 37, since image 7 could be scaled to image 37 in
`and rotated. The process is repeated to generate image
`one step. It is important to realize at this stage that only
`270. The generation of images 250, 260, and 270 using
`image 0 and image 25 actually exist-the requested
`prior art techniques requires the execution of eighteen
`images have not been generated yet, and the intermedi
`highly computational intensive steps.
`ate images will only be generated if the invention deter
`60
`FIG.3 shows a simplified representation of the gener
`mines that they are in an optimal image path.
`ation of a series of images using the method of the in
`FIG. 4B shows the image states of FIG. 4A after the
`vention. Image 300 is an existing compressed image.
`invention performs a simplification operation on the
`High quality images 350, 360, and 370 are to be gener
`logical connections between the image states. Logical
`ated from this compressed image. In order to generate
`connections determined to be the result of an inefficient
`65
`high quality image 350, image 300 must, like the prior
`operation have been deleted. For example, although it is
`art method described above, first be decompressed,
`true that image 7 could be scaled to image 37 in one
`scaled to the correct size, corrected to the original
`step, this is not an efficient operation. Therefore, the
`
`IPR2023-00332 Page 00036
`
`

`

`15
`
`5,420,967
`6
`5
`blue. The numbers represent the normalized luminance
`connection between images 7 and 37 has been deleted in
`Fig. 4B. This simplification operation will be explained
`of the red, green and blue components of each palette
`entry. FIG. 5J shows a dither table. A dither table is a
`in more detail later when FIG. 8 is discussed.
`FIG. 4C shows the image states of FIG. 4A after the
`kind of nonlinear transformation table that converts
`invention has determined the optimal paths to requested
`linear data to non-linear device compensated data. It
`images 11, 20, 30, and 40. These paths were determined
`has as input a number from 0 to the maximum value for
`by forming combinations of paths from existing images
`R, G, or B linear pixel data-in this example, from 0 to
`to requested images shown in FIG. 4B, and calculating
`4095. Its output ranges from 0 to the maximum input
`a computational cost for each path combination to de
`value to the D/A converters on the display adapter.
`termine the best path combination. The optimal path to
`The difference is that the dither table has not value for
`10
`requested image 11 includes images 0, 1, 2, 3, 6, and 11.
`eachinput value but some number greater than 1, where
`The optimal path to requested image 20 includes images
`the position of the pixel within the image is used to
`2, 12, 14, 15, and 20. The optimal path to requested
`select between the various output values for the same
`image 30 includes images 25 and 30. The optimal path to
`input value. The exemplary table in FIG. 5J shows 4096
`possible input values, ranging from 0 to 4095. The out
`requested image 40 includes images 14, 34, 35, and 40.
`After the optimal paths are established, the invention
`put is one of 4 values for R, 4 values for G, or 4 values
`generates requested images 11, 20, 30, and 40 along the
`for B. The values in this case range from 0 to 31 for R
`optimal paths shown in FIG. 4C. For example, image20
`and B, and 0 to 63 for G, since the display adapter takes
`is generated by scaling intermediate image 2 (resulting
`5 bits for red and blue and 6 bits for green.
`in intermediate image 12), matching the color to the
`FIG.5E shows the image table of the invention. This
`20
`table stores the representation of each existing, re
`second device (resulting in intermediate image 14), con
`quested, and intermediate image. A value of “1” in
`verting to the resolution of the second device (resulting
`column 550 indicates that the image exists. A value of
`in intermediate image 15) and rotating to the orientation
`desired for requested image 20.
`"3” indicates an intermediate image, and a value of "2'
`indicates a requested image. Columns 561-564 refer to
`FIGS. 5A-5 show the tables of the invention. Each
`25
`the specific row in the scale state table (FIG. 5A), the
`of these tables is used by the flowcharts of FIGS. 7-11,
`match state table (F