United States Patent 55
`[11] Patent Number:
`5,991,515
`Fall et al.
`[45] Date of Patent:
`Nov.23, 1999
`
`
`US005991515A
`
`5,208,676
`[54] METHOD AND APPARATUS FOR
`5/1993 IMU ccccisecsecserecreseecserseseenes 358/296
`5,241,397
`COMPRESSING AND DECOMPRESSING.
`8/1993 Yamada oo... sseescssssscecenssenceneeees 358/296
`
`
`DATA PRIOR TO DISPLAY 5,270,728 12/1993 Lund et ab. ooeececeeeee 395/108
`§,272,768 12/1993 Bauman et al. occ 395/110
`5,276,780
`1/1994 Sugiura beneeeeee ceeeesascessessee ceeeeees 395/116
`
`3/1994 Ota crececccescssececsessssecssseeessneseeee 395/115
`5,295,233
`oe 395/108
`5,299,292
`3/1994 Kadowakiet al.
`
`scssesssssssssssseseseeseee 358/296
`5,347,368
`9/1994 Mochizuki
`
`
`10/1994 Sakagamiet al. cscs 395/108
`5,354,135
`..cssesssssseseconn 395/115
`5,355,441
`10/1994 Kawaiet al.
`5,374,943
`12/1994 Lehmanmetal. ....cssccesssessseee 395/110
`5,377,312 12/1994 Kobayashi oo... eee 395/116
`FOREIGN PATENT DOCUMENTS
`0320014A2
`6/1989
`European Pat. Off. .
`0475601A2
`3/1992 European Pat. Off. .
`0475601A3
`3/1992 European Pat. Off. .
`
`[75]
`
`Inventors: Richard N. Fall, Palo Alto; Nicholas J.
`Foskett. Mt. View: Davin C. Won:
`?
`.
`-
`.
`8:
`Berkeley, all of Calif.
`
`;
`[73] Assignee: Adobe Systems Incorporated, San
`Jose, Calif.
`
`[21] Appl. No.: 08/893,065
`[22]
`Filed:
`Jul. 15, 1997
`os
`Related U.S. Application Data
`
`[S51]
`
`[63] Continuation-in-part of application No. 08/851,529, May 5,
`1997, which is a continuation of application No. 08/484,344,
`Jun. 7, 1995, Pat. No. 5,638,498, which is a continuation-
`in-part of application No. 07/974,204, Nov. 10, 1992, Pat.
`No. 5,539,865.
`Int. CScscs B41B 15/00; HO4N 1/387;
`HO4N 1/40; GO6K 9/36
`[52] U.S. Che acccccccscccsssseee 395/114; 395/117; 395/115,
`395/116; 395/112; 395/111; 358/450; 358/444;
`382/232; 382/233
`.
`[58] Field of Search oo. eee 395/114, 115,
`395/116, 110, 111, 112, 108, 117; 382/232,
`233, 235; 358/450, 444, 540, 426, 261.3,
`261.4, 432, 433
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`.
`
`asa bit099 Sasakietal enesont
`
`9/1992 Miyta wcscscusneseenennnanenese 382/56
`5,151,949
`
`.
`w. 400/121
`5,199,803
`4/1993 Shimizu etal.
`5/1993 Tto eeccccceccsesescseecsesescseseecseeesees 395/110
`5,207,517
`
`«
`
`OTHER PUBLICATIONS
`.
`.
`“Integrating Image Into Computers for Pub-
`Fred Mintzer,
`lishing” TEEE/IEICE Global Telecommunications Conf.
`1987, Nov. 15-18, 1987, Japan pp. 19.6.1-19.6.4.
`Okada, et al., “Adaptive Coding for Text and Dithered
`Continuous—Tone Images”, Fujitsu Scientific & Technical
`Journal, vol. 23, No. 2, 1987, Japan, pp. 101-109.
`Primary Examiner—Edward L. Coles
`Assistant Examiner—TIwyler Lamb
`Attorney, Agent, or Firm—Fish & Richardson P.C.
`
`ABSTRACT
`[57]
`A method and apparatus for compressing and decompressing
`display data including methods for predicting compression
`results and correcting compression ratios prior to the com-
`pression of object data. The compressed objects are then
`decompressed using a related decompression mechanism
`and sent directly to a driver in the output display device for
`Printing ordisplay.
`
`14 Claims, 23 Drawing Sheets
`
`10
`
`™
`
`12
`
`COMPUTER
`
`COMPUTER
`
`12
`
`[714
`
`PRINTER
`
`coe|
`
`16
`
`<—<____
`
`
`
`
`
`18
`
`22
`
`Ny
`
`TEXT
`
`
`
`NetApp
`
`Exhibit1005
`
`Page 1
`
`NetApp Exhibit 1005 Page 1
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 1 of 23
`
`5,991,515
`
`Fig.t
`
`PRINTER
`
`COMPUTER
`
`COMPUTER
`
`NetApp
`
`Exhibit1005
`
`Page 2
`
`NetApp Exhibit 1005 Page 2
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 2 of 23
`
`f)s0yndwos
`
`Bxosssooud
`
`=ANIONS
`
`WILIDSIG
`
`5,991,515
`
`NetApp
`
`Exhibit1005
`
`Page 3
`
`NetApp Exhibit 1005 Page 3
`
`

`

`5,991,515
`
`Sheet 3 of 23
`
`Nov. 23, 1999
`
`U.S. Patent
`
`NetApp
`
`Exhibit 1005
`
`Page 4
`
`NetApp Exhibit 1005 Page 4
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 4 of 23
`
`5,991,515
`
`ElLv
`
`ely
`
`a}e1S:
`
`UOHeWUO}U|
`
`a121S
`
`UOHeULOJU] uoissaidwog
`
`a}e1SI
`6e
`
`
`
`
`
`
`
`
`
`
`
`
`NetApp
`
`Exhibit1005
`
`Page 5
`
`uolssaidwog
`
`eulbug
`
`eulbug
`
` auibuy©)uoissasdwog
`
`NetApp Exhibit 1005 Page 5
`
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 5 of 23
`
`5,991,515
`
`CLV
`
`SIEIS
`
`CLVy
`
`UOIEUO}U]
`
`9}E}S
`
`UOIPELUOJU]
`
`6e
`
`LLP
`
`puessojoe4
`
`SJUdINIY90D
`
`joajqeL
`
`uoisseidwos
`
`UOISSeIdWOD
`
`J9}}04)U0D
`
`
`
`B1eqJo}Oe4
`
`J9}01019}U|
`
`NetApp
`
`Exhibit 1005
`
`Page 6
`
`NetApp Exhibit 1005 Page 6
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 6 of 23
`
`5,991,515
`
`420
`
`a
`
`Fig. bd
`
`NetApp
`
`Exhibit1005
`
`Page7
`
`NetApp Exhibit 1005 Page 7
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 7 of 23
`
`5,991,515
`
`. Provide Scan|#52450
`
`identity@Scan
`Line Position
`P cessin
`Data to the
`re
`g
`Decompressor
`
`
`
`
`
`Retrieve Object
`Descriptor From
`Memory
`
`454
`
`
`
`
`455
`Object
`
`Retrieve Next
`Object Intersec\ Yes
`
`458
`
`in
`Li
`Store in List of
`Intersecting
`Objects
`
` Any More
`Objects to
`
`Process?
`
`
`462
`
`Ce
`
`
`Each Entry in List
`from Memory
`
`
`Information
`Fig. Ze
`
`Pass Object
`Entry Information
`to the
`Appropriate
`Decoder
`
`461
`
`460
`
`Determine Object
`Data Typefor
`
`Provide List to
`Decompressor
`
`Retrieve and
`Decompress Data
`for the Object
`
`466
`
`
`464
`Has
`he Object Been Yes
`Partially
`Decoded?
`
`
`
`Store State
`
`470
`
`
`
`
`
`468
`
`
`
`
`
`Has
`
`Object Been Completly
`Decompressed ?
`
`
`©)
`
`Retrieve State
`Information
`
`
`
`
`Any
`Other Objects
`
`
`o Process?
`
`
`
`8)
`
`NetApp
`
`Exhibit1005
`
`Page 8
`
`NetApp Exhibit 1005 Page 8
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 8 of 23
`
`5,991,515
`
`40
`
`“a
`
`42
`
`
`
`
`
`
`
`Rasterize and Compress
`
`Input Data of a Page Based
`Upon Rasterized Object
`Types and Store
`
`44
`
`46
`Decompress Based upon
`
`Compression Algorithm and
`Display
`
`Another Page?
`
`
`
`NetApp
`
`Exhibit1005
`
`Page9
`
`NetApp Exhibit 1005 Page 9
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 9 of 23
`
`5,991,515
`
`Csan”
`
`44
`
`Set Compression
`Level to Lowest
`
`Level
`
`RepresentAll
`Bands as
`Compressed Form
`of Whitespace
`
`69
`Create and Empty|58
`
`
`
`Collector Per E>
`
`60
`
`Band
`
`Yes
`
`70
`
` Display List
`
`Empty?
`
`No
`
`
`Display List
`Storage
`
`
`
`Retrieve Input
`
`Object
`
`
`
`
`Store Type and
`Bounding Box of
`
`Input Object in
`
`Collector for Bands
`
`Spanned by Object
`
`Add Input Object
`
`to Display List
`
`
`
`64
`
`66
`
`88
`
`ig. Fa
`
`NetApp
`
`Exhibit1005
`
`Page 10
`
`NetApp Exhibit 1005 Page 10
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 10 of 23
`
`5,991,515
`
`/
`Cn)
`75
`
`
`
`Select a Band, "A",
`
`Is an Uncompressed
`Having Display List
`
`
`
`Band Buffer
`
`Entries
`
`Available?
`
`
`
`Is Band A Data in
`Compressed State?
`
`
`Decompress Band Data
`
`Into Uncompressed Band
`
`
` Buffer
`
`
`
`Rasterize Display List
`
`Entries of Band A Into
`
`
`
`Uncompressed Band
`Buffer
`
`
`Set A = The BandID of
`
`Band in Uncompressed
`
`Band Buffer
`
`
`
`Compressed
`Data Fits?
`
`
`
`Yes
`86
`
`Attempt to
`Compress Band A
`Data
`
`
`
`77
`
`82
`
`84
`
`No
`
`C83)
`
`All Display Lists
`with Entries
`Processed?
`
`At End of
`
`No
`
`aD
`
`Yes
`
`88
`
`Cdone7)Fig. Ub
`
`NetApp
`
`Exhibit1005
`
`Page 11
`
`NetApp Exhibit 1005 Page 11
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 11 of 23
`
`5,991,515
`
`44
`
`90
`
`Higher Level of
`Compression
`Available?
`
`
`
`92
`
`Failure
`
`93
`
`
`
`
`Advance to Next Higher
`Compression Level
`
`
`
`
`Any Compressed
`Bands Not at Current
`
`‘\
`
`
`
`
`Compression Level?
`Level
`
`Buffer
` Decompress BandBinto
`
` Attempt to Compress
`
`Compression Level
` 104
`
`
`
`Recompress Band B
`Compressed Band
`
`at Previous Lower
`.
`
`Compression Level
`
`
` Select a Band "B" ata
`Lower Compression
`
`Uncompressed Band
`
`Band B Data at Current
`
`.
`B Fits?
`
`Yes
`108
`
`Policy to
`
`RecompressAll
`
`
`Bands?
`
`
`Fig. Fe
`
`NetApp
`
`Exhibit1005
`
`Page 12
`
`NetApp Exhibit 1005 Page 12
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 12 of 23
`
`5,991,515
`
`125
`
`112
`
`113
`
`115
`
`117
`
`119
`
`112
`
`121
`
`123
`
`112
`
`Fig. 4a
`
`NetApp
`
`Exhibit1005
`
`Page 13
`
`NetApp Exhibit 1005 Page 13
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 13 of 23
`
`5,991,515
`
`Fig.Fe
`
`®ian
`
`®£ °
`
`o
`7)
`
`© 8_ ”®_
`
`NetApp
`
`Exhibit1005
`
`Page 14
`
`NetApp Exhibit 1005 Page 14
`
`

`

`Sheet 14 of 23
`
`5,991,515
`
`Nov.23, 1999
`
`U.S. Patent
`
`NetApp
`
`Exhibit 1005
`
`Page 15
`
`NetApp Exhibit 1005 Page 15
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 15 of 23
`
`5,991,515
`
`66
`
`“Ne
`
`
`
`
`
`
`
`New Object Can
`
`Combine Like
`Combine Easily With
`
`Objects
`Object Of Same Type?
`
`136
`
`
`
`Yes
`
`Enough Storage In
`Collector To Add
`Object's Info?
`
`
`
`146
`
`
`Combinations To
`Free Storage
`
` Force Object
`
`Add Object Type
`And BBox Info To
`Collector
`
`NetApp
`
`Exhibit1005
`
`Page 16
`
`NetApp Exhibit 1005 Page 16
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 16 of 23
`
`5,991,515
`
`148
`
`136 Retrieve Bounding
`
`
`
`Box Coordinates
`of New Object and
`Stored Object
`
` 150
`
`
`
`Replace Any BBox
`Coordinates of Stored Object|452
`with Corresponding BBox
`Coordinates of New Objectif
`Conditions Met
`
`156
`
`
`
`Compute the Cost of
`Combining Collected Objects
`
`with Other Collected Objects
`
`of the Same Type.
`
`
`Select Bounding Box
`Coordinates of the Object Pair
`Having the Smallest Cost of
`
`
`Combination
`
`
`
`
`
`
`142
`
`158
`
`
`
`160
`
`Replace the Two Selected
`Objects with a New Combined
`Object Having the Same Type
`and Each BBox Coordinate
`from Oneof the Two Objects
`
`162
`
`
`
` More Combinations
`
`Possible?
`
`
`Desired Number of
`Combinations
`done?
`
`164
`
`NetApp
`
`Exhibit1005
`
`Page 17
`
`NetApp Exhibit 1005 Page 17
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 17 of 23
`
`5,991,515
`
`180
`
`
`
`
`Using Collected Object Data, Find a
`
`Set of Non-intersecting Rectangular
`Regions that Covers All Objects in
`
`Band
`
`Assign Each Region an Empty Set of
`Types and Set Each Region's
`
`"Marked" Flag to False
`
`182
`
`184
`
`80
`
`
`
`i < Numberof
`Objectsin
`
`Band
`
`
`
`
`
`186
`
`No
`
`188
`
`194
`
`196
`
`Combine AnyEligible
`
`
`
`For the Set of Regions Covering
`
`Object(i), Add the Type of Object
`(i) to Each Region and Set Each
` Assign the Best
`Region's Marked Flag to "True"
`
`
`Compression Algorithm to
`Each Region Based on the
`
`
`Type of Each Region and
`Other Factors
`Regions Based on Criteria
`198
`
`200|Attempt to Compress Band
`Data from Regions into
`(Done)
`Compressed Band Buffer
`According to Assigned
`Algorithms
`
`Fig 5
`
`NetApp
`
`Exhibit1005
`
`Page 18
`
`NetApp Exhibit 1005 Page 18
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 18 of 23
`
`5,991,515
`
`202
`
`212
`
`ALGORITHM TABLE
`
`204
`{
`a
`203,
`_7™ ALGEntry 1 (LZW) Parameters1)
`201-~» ALG Entry 2 (DCT - Based) [ Parameters 2]
`ALG Entry 3 (LZW) [ Parameters 3]
`ALG Entry 4 (DCT - Based) [ Parameters 4]
`ALG Entry 5 (LZW and DPCM) [ Parameters 5]
`ALG Entry 6 (LZW and DPCM) [ Parameters 6]
`ALG Entry 7 (PDR) [ Parameters 7]
`
`Fig Sa
`
`Text
`
`No
`
`Image
`No
`
`INDEXING TABLE
`
`205
`
`att
`
`
`
`/
`209
`208
`Graphic
`(N Algor Assigned)
`No
`No No_(Q=0, CR =2.0, ALG Entry 1)
`Yes
`213a-7, (Q = 2, CR = 5.0, ALG Entry 3)
`$2074
`313b” (= 4, CR = 10.0, ALG Entry 5
`Yes
`A(Q = 0, CR= 2.0,ALG Entry 1) \ 207
`
`No
`
`No
`
`213c
`
`No
`
`Yes
`
`No
`
`213
`
`Yes
`
`No
`
`Yes
`
`No
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`No
`
`213%
`Yes
`
`(Q=0, CR = 3.0, ALG Entry 3)
`(Q = 4, CR = 8.0, ALG Entry 6)
`(Q=0,CR=4.0, ALG Entry 2)
`(Q = 1, CR = 7.0, ALG Entry 4)
`(Q = 3, CR = 9.0, ALG Entry 5)
`(Q=0,CR=2.0, ALG Entry 1)
`(Q = 3, CR = 5.0, ALG Entry 5)
`(Q = 5, CR = 6.0, ALG Entry 6)
`(Q=0, CR=2.0, ALG Entry 6)
`Q = 2, CR = 2.5, ALG Entry 2)
`(Q = 3, CR = 5.0, ALG Entry 7)
`—(Q =0, CR = 2.0, ALG Entry 6)
`(Q = 1, CR =3.0, ALG Entry 5)
`(Q = 4, CR = 4.5, ALG Entry 2)
`(Q=0,CR=1.5, ALG Entry 5)
`(Q = 2, CR = 2.0, ALG Entry 4)
`
`$207b
`
`Fig Ut
`
`NetApp
`
`Exhibit1005
`
`Page 19
`
`NetApp Exhibit 1005 Page 19
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 19 of 23
`
`5,991,515
`
`210
`
`Sat)
`Bounding Boxes in Band
`
`Describe Left or Right Edgesof
`
`Create Array of All X Coordinates that
`
`Ue
`
`Fig. G
`
`Sort Array of X Coordinates in Order of|244
`Increasing X and Remove Duplicate
`Values: nX = Number of Valuesin
`Resulting Array
`
`
`
`Create Array of All Y Coordinates that
`Describe Top or Bottom Edgesof
`Bounding Boxes in Band
`
`216
`
`Sort Array of Y Coordinates in Order of|948
`Increasing Y and Remove Duplicate
`Values: nY = Numberof Valuesin
`Resulting Array
`
`Divide Band into (nX-1) (nY-1)
`Rectangular Regions
`
`223
`
`one)
`REGION DATA STRUCTURE
`222— Master Flag
`224
`Slave Flag
`~
`226~ Marked Flag
`228
`230~ v Index
`232
`
`X Index ——~
`
`Object Types ~
`
`220
`
`221
`
`v4
`
`°
`
`Fig. Ga
`
`NetApp
`
`Exhibit1005
`
`Page 20
`
`NetApp Exhibit 1005 Page 20
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 20 of 23
`
`5,991,515
`
`240
`
`For Each Row of Regions,
`Combine Adjacent Regions
`Having the Same
`
`Compression Algorithm
`Regions
`
`Combine Pairs of Non-
`Empty Regions with Empty
`Regions separating the Pair
`if Hardware Constraints
`Violated on that Row of
`
`944
`
`
`
`
`Force
`
`
`Hardware Constraints
`Combinations of
`
`Still Violated in a Row?
`Additional
`
`
`
`
`Regions Within
`Row
`
`No
`
`248
`
`CombineVertically Adjacent
`Regions When Possible and
`
`Cost Within Limits
`
`250
`
`252
`
`Fig. 10
`
`NetApp
`
`Exhibit1005
`
`Page 21
`
`NetApp Exhibit 1005 Page 21
`
`

`

`U.S. Patent
`
`Nov.23, 1999
`
`Sheet 21 of 23
`
`5,991
`
`915
`
`260
`
`
`
`Designate and Mark
`262
`
`LowerLeft Region as
`
`
`Master and Rest of
`
`
`
`
`Regionsin Group as
`Slaves
`
`
`
`
`Augmentthe Object
`264
`
`Type of the Master with
`All the Object Types of
`the Slave Tiles
`
`
`
`
`
`Mark Master with the
`266
`
`Boundaries of Set of
`Slaves
`
`
`
`CauseAll Slaves to Point
`to Master
`
`268
`
`242
`
`274
`
`
`Read Attributes fora
`
`
`Non-Entry Region
`From Region Buffer
`
`
`
`
`Create Region
`Descriptor for Non-
`
`
`Empty Region Using
`
`Attributes
`
`
`
`Attempt to Compress
`Non-Empty Region
`
`
`From Uncompressed
`
`
`Band Buffer Specified
`by Attributes
`
`
`Yes
`
`Another Region
`in Region
`Buffer?
`
`
`
`NetApp
`
`Exhibit1005
`
`Page 22
`
`NetApp Exhibit 1005 Page 22
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 22 of 23
`
`5,991,515
`
`290
`
`Load a Numberof Regions
`Descriptors into
`Decompression Buffer
`
`46
`
`292
`
`296
`
`Determine Regions Crossed
`By Next Scan Line
`Output Background Pixels to|300
`
`298
`Display Until Scan Line Pointer
`
`
`Points to Start of Region or
`
`End of Scan Line
`
`
`No
`
`Scan Line Pointerat a
`Region?
`
`
`
`
`
`
`
`Get Decompression State for
`Region
`
`302
`
`Pointer at Start of
`
`Region?
`
`
`
`Decompress and Output
`
`Region Data Until Scan Line
`Pointer Points to End of
`Region
`
`
`Pointer at End of Scan
`
`Line?
`
`
`Regions? —_
`
`310
`
`Completed Any
`
`Yes
`
`312
`
`Load Additional Region
`
`Descriptors
`
`314
`
`
`Pointer at End of Page?
`
`
`Fig. 13
`
`316
`
`NetApp
`
`Exhibit1005
`
`Page 23
`
`NetApp Exhibit 1005 Page 23
`
`

`

`Sheet 23 of 23
`
`5,991,515
`
`U.S. Patent
`
`Nov.23, 1999
`
`og)‘bE OZE
`
`NetApp
`
`Exhibit1005
`
`Page 24
`
`NetApp Exhibit 1005 Page 24
`
`

`

`5,991,515
`
`1
`METHOD AND APPARATUS FOR
`COMPRESSING AND DECOMPRESSING
`DATA PRIOR TO DISPLAY
`
`This is a continuation-in-part of U.S. application Ser. No.
`08/851,529, filed on May5, 1997, whichis a continuation of
`U.S. application Ser. No. 08/484,344,filed on Jun. 7, 1995
`(which issued as U.S. Pat. No. 5,638,498), which is a
`continuation-in-part of U.S. application Ser. No. 07/974,
`204, filed Nov. 10, 1992 (which issued as U.S. Pat. No.
`5,539,865.
`
`BACKGROUND
`
`The present invention relates generally to the display of
`data by output devices, and more particularly to a method
`and apparatus for compressing and decompressing data prior
`to display on an output display device.
`A computer system can output data to a wide variety of
`output display devices. Output display devices such as laser
`printers, plotters, and other printing devices produce an
`imageor “visual representation” onto a sheet of paperor the
`like, while output display devices such as computer moni-
`tors develop visual representations on a computer screen.
`Many output display devices receive display data in the
`form of a “bitmap” or “pixel map” and generate visual
`representations from the display data. A pixel is a funda-
`mental picture element of a visual representation generated
`by a display device, and a bitmap is a data structure
`including information concerning a numberof pixels of the
`representation. Bitmaps that contain more than on/off infor-
`mation are often referred to as “pixel maps.” As used herein,
`both bitmaps and pixel maps are referred to as “bitmaps.”
`Aprinter can print dots on a piece of paper corresponding
`to the information of a bitmap. Alternatively, a computer
`monitor can illuminate pixels based upon the information of
`the bitmap. A “raster” output device creates a visual repre-
`sentation by displaying the array of pixels arranged in rows
`and columns from the bitmap. Most output devices, other
`than plotters, are raster output devices. Typically, a “page”
`of pixels corresponding to a printed or displayed page is
`received and stored in memory before the pixels are dis-
`played by the output display device.
`A visual representation can contain a number of image
`types, including text, graphics, photographic images, etc.
`Data of these types can be efficiently stored in files with
`other
`image information as high level “objects.” An
`“object”, as referred to herein,
`is the data and attributes
`defining a particular visual representation. The objects can
`be edited or otherwise manipulated using an application
`program (“software”) running on a computer. Whendisplay-
`ing the objects with an output display device such as a
`printer or display screen,
`the objects are typically first
`rasterized (or “rendered”) into bitmaps. The output display
`device stores display bitmap data in memory before display-
`ing the data.
`A problem in the prior art methods of providing bitmaps
`to output display devices is that a large amount of storage
`space is required to store the bitmap before it is displayed.
`The requirements for storage space have become greater as
`the desire for high-resolution representations with more
`realistic attributes has become more prominent. For
`example, using a laser printer capable of printing black-and-
`white images at a resolution of 600 dots per inch (dpi), a
`typical displayed page requires about 3.8x10° bytes of
`memory. Whenprinting a page of color pixels, for example,
`having 8 bits of color per pixel, the memory requirement
`
`2
`increases to about 121x10° bytes of memory. With such
`memory requirements, a significant portion of the cost of
`manufacturing an output display device such as a laser
`printer is the cost of the required memory.
`A method that has been used to reduce the memory
`requirements for displaying high-resolution images involves
`the compression of the bitmap data according to a compres-
`sion method or algorithm. A compression algorithm can
`significantly reduce the space needed to store bitmaps by
`removing information from bitmaps or other objects. Some
`compression algorithms are “lossless”, meaning that they
`compress data and reduce storage requirements with no loss
`of essential information. This type of compression is often
`used with text objects and the like, since text character codes
`often include extra information unrelated to the identity of
`the text characters. Other types of compression algorithms
`are “lossy”, meaning that they compress data with some loss
`of information. These types of compression algorithms are
`typically used with image bitmap data, since the loss of
`information can often be unnoticeable in a high resolution
`image. When the compressed bitmapis to be displayed,it is
`decompressed using a corresponding decompression algo-
`rithm and sent to a print engine, monitor, or other output
`display device.
`A problem with the compression methodsof the prior art
`occurs when different types of objects are to be displayed by
`an output display device. For example, a page of data can
`include text objects such as words or paragraphs, graphics
`objects such as bar charts or geometric shapes, and image
`objects such as a digitized photograph. A compression
`algorithm that is good for text objects may, for example, be
`less than adequate for image objects, and vice versa. For
`example, lossy compression techniques may be adequate for
`image objects in that they can highly compress the image
`object data, but may be less than adequate for text objects,
`where the lost data would be apparent. A lossless compres-
`sion technique is good for text objects, but may not
`adequately compress image objects. Thus, the selection of a
`single compression algorithm will almost alwaysresult in a
`less-than-optimal compression of mixed object types.
`In addition, conventional compression methods compress
`object data based on a compression factor or ratio. The
`compression ratio determines the amount of compression
`required to achieve a particular compression result. The
`compression ratio may be user defined or set based on
`available memory resources. For example, in the processing
`of a page of data, compressed memory whichis usedto store
`compressed data objects of varying types may become full.
`If more objects remain to be processed for a given page, then
`the compressionratio used to originally compress the object
`data may be required to be changed. Thereafter, the data
`stored in compressed memory is required to be decom-
`pressed and recompressed based on the new compression
`ratio, a process referred to as cycling. The cycling processis
`very time consuming.
`The decompression of compressed data objects from
`compressed memory is another time consuming process.
`Conventional decompression methods require the decom-
`pression of object data directly into memory. Accordingly,
`the printing of an image by a printer employing conventional
`decompression methods is slowed by the inability of the
`printer to decompress object data directly to a print engine.
`
`SUMMARYOF THE INVENTION
`
`The present invention provides a method and apparatus
`for compressing and decompressing display data. The
`
`wm
`
`10
`
`15
`
`20
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`NetApp
`
`Exhibit1005
`
`Page 25
`
`NetApp Exhibit 1005 Page 25
`
`

`

`5,991,515
`
`3
`present invention compresses multiple types of data objects
`using compression mechanismsthat are optimized for each
`type of object according to user constraints and which
`include methods for predicting compression results and
`correcting compression ratios prior to the compression of
`object data. The compressed objects are then decompressed
`using a related decompression mechanism and sentdirectly
`to a driver in the output display device for printing or
`display.
`The apparatus of the present invention includes a digital
`output processing system with selective object compression
`and decompression. A rasterizer converts data objects into
`bitmap objects of various types. A compressor compresses
`the bitmap objects with a selected compression mechanism.
`The particular compression mechanism selected is
`dependent, at least in part, on the type of the particular
`bitmap object being compressed. For example, if the bitmap
`object is a text type, a graphics type, or an image type, then
`a compression mechanism best suited to text, graphics, or
`image data, respectively, is selected. The selection of com-
`pression mechanism and compressionratio also depends on
`the size of the available memory to store the compressed
`data and overall page analysis. The compressor analyzes
`data objects prior to compression to determine the suitability
`of the current (user defined or default) compression ratio. In
`the event, the compressed memory is unable to store the
`compressed object data, cycling may beinitiated priorto the
`compression of the current object data. The compression
`mechanism produces compressed bitmap regions and stores
`the compressed bitmap regions in digital read/write com-
`pressed memory associated with an output device.
`A decompressor decompresses the compressed bitmap
`regions with a selected decompression mechanism deter-
`mined by the selected compression mechanism for a given
`region. The decompression mechanism for a particular com-
`pressed bitmap region is dependent upon the compression
`mechanism used to compressthe bitmap region. The decom-
`pression mechanism then supplies the uncompressed bitmap
`regions to an output display device for display. Suitable
`output display devices include printer devices and display
`screens.
`
`The data objects input to the apparatus of the present
`invention are organized into at
`least one page that has
`multiple sections, called “bands.” The bands preferably have
`a display order on the page, and bands of the page are
`displayed by the output display device in the display order.
`The data objects are stored in display lists corresponding to
`the bands of the page. Preferably, the bitmap objects and
`other backgrounddata in the band are rasterized and divided
`into non-intersecting bitmap regions which cover the band.
`The regions are designated as either empty regions covering
`no objects, or non-empty regions covering objects. The
`bitmap regions can be combined into larger regions accord-
`ing to specified constraints. Only the non-empty bitmap
`regions are preferably compressed by the compression
`mechanism according to the assigned compression algo-
`rithms. The decompressor decompresses one page at a time
`by determining where an output scan line intersects regions
`on that scan line and decompressing the compressed regions
`directly to a engine in the output device when the scan line
`intersects the regions. The decompressor outputs back-
`ground data when the scan line does not
`intersect
`the
`compressed regions.
`The present
`invention includes numerous advantages.
`Object data may be pre-screened prior to compression to
`assure that the compression ratio selected will allow for the
`storage of the object data in compressed memory.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`Decompressed object data may be provided directly to a
`print driver in a output display device without requiring
`storage in memory.
`These and other advantages of the present invention will
`becomeapparentto those skilled in the art upon a reading of
`the following specification of the invention and a study of
`the several figures of the drawing.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of a computer system for
`displaying a page having objects of different types in accor-
`dance with the present invention;
`FIG. 2 is a block diagram of an output device suitable for
`use with the present invention;
`FIG. 2a is a block diagram of a digital processor as shown
`in FIG, 2;
`FIG. 2b is a block diagram of the ASIC of FIG. 2 for
`compressing and decompressing object data;
`FIG. 2c is a block diagram of the compressor of FIG. 25;
`FIG. 2d is a diagrammatic illustration of a page of objects,
`the page being divided into bands;
`FIG. 2e is a flow diagram illustrating the process of
`decompressing objects for display by an output device
`according to the present invention;
`FIG. 3 is a flow diagram illustrating the process of
`displaying data with reduced storage requirements accord-
`ing to the present invention;
`FIG. 4a is a flow diagram illustrating the first portion of
`the rasterize and compress input data step of FIG. 3;
`FIG. 45 is a flow diagram illustrating the second portion
`of the rasterize and compress input data step of FIG. 3;
`FIG. 4c is a flow diagram illustrating the third portion of
`the rasterize and compress input data step of FIG. 3;
`FIG. 4d is a diagrammatic illustration of a page of objects,
`the page being divided into bands;
`FIG. 4e is a diagrammatic illustration of a band including
`objects;
`FIG. 4f is a diagrammatic illustration of the band of
`objects of FIG. 4e that has been partitioned into non-
`intersecting regions;
`FIG. 5 is a flow diagram illustrating a step of FIG. 4a in
`which input object type and bounding box information is
`stored in collectors associated with bands;
`FIG. 6 is a flow diagram illustrating a step of FIG. 5 in
`which like objects in a collector are joined;
`FIG. 7 is a flow diagram illustrating a step of FIG. 5 in
`which object combinations in a collector are forced to free
`storage;
`FIG. 8 is a flow diagram illustrating a step of FIG. 4b in
`which a band is compressed;
`FIG. 8a is a table of algorithm entries referenced by the
`process of FIG. 8 to assign algorithms to regions;
`FIG. 8b is a table of indexes into the algorithm table of
`FIG. 8a for assigning algorithms to regions;
`FIG. 9 is a flow diagram illustrating a step of FIG. 8 in
`which non-intersecting rectangular regions are designated in
`the band to be compressed;
`FIG. 9a is a diagrammatic illustration of a data structure
`describing a region of FIG. 9;
`FIG. 10 is a flow diagram illustrating a step of FIG. 8 in
`which eligible regions are combined;
`FIG. 11 is a flow diagram illustrating steps of FIG. 10 in
`which regions are combined;
`
`NetApp
`
`Exhibit1005
`
`Page 26
`
`NetApp Exhibit 1005 Page 26
`
`

`

`5,991,515
`
`5
`FIG. 12 is a flow diagram illustrating a step of FIG. 8 in
`which a band is attempted to be compressed;
`FIG. 13 is a flow diagram illustrating a step of FIG. 3 in
`which the compressed data is decompressed and displayed;
`and
`
`FIG. 13a is a diagrammatic illustration of a band and the
`scanning of the band to decompress data.
`DETAILED DESCRIPTION
`
`The present invention is well-suited for reducing the
`storage space requirements for rasterized data that is to be
`sent
`to an output display device. However,
`the present
`invention can also be used to generally reduce storage
`requirements when storing data of different types for a
`variety of purposes.
`Anumberof terms are used herein to describe images and
`related structures. “Visual representation” refers to the
`image produced by an output device on a sheet of paper,
`display screen, etc. The term “image” is used to describe a
`type of visual representation or “object type.” “Pixel” refers
`to a single picture element of a displayed visual represen-
`tation. Taken collectively, the pixels form the representation.
`“Bitmap” refers to bits stored in digital memory in a data
`structure that represents the pixels. As used herein,“bitmap”
`can refer to both a data structure for outputting black and
`white pixels, where each pixel either is on or off, as well as
`a “pixel map” having more information for each pixel, such
`as for color or gray scale displays. “Raster”, as used herein,
`refers to the arrangement of pixels on an output device that
`creates a visual representation by displaying an array of
`pixels arranged in rows and columns. Raster output devices
`thus include laser printers, computer displays, video
`displays, LCD displays, etc. “Render” and “rasterize” refer
`to the creation of an object bitmap from object primitives,
`such as a character outline or object in a display list. Both
`object primitives and object bitmaps are referred to as
`“objects” herein, where an “object” includes type and loca-
`tion information as well as data describing a visual repre-
`sentation which is to be derived from the object.
`In FIG. 1, a computer system 10 suitable for reducing
`storage requirements in the display of visual representations
`includes one or more digital computers 12, a communica-
`tions bus 14,a printer 16, a display (CRT) 18, or other output
`display device 20. The output of devices 16, 18, or 20 is a
`visual representation on a displayed page 22. Digital com-
`puters 12 can be personal computers (such as an IBM-PC
`AT-compatible or Apple Macintosh personal computer),
`workstations (such as a SUN or Hewlett-Packard
`workstation), etc. Computers 12 typically each include a
`microprocessor, a memory bus, random access memory
`(RAM), read only memory (ROM), peripherals such as input
`devices (keyboard, pointing device, voice recognizer, etc.),
`and storage devices (floppy disk drive, hard disk drive, etc.).
`In an alternate embodimentof the present invention, display
`data can be sent to other memory devices or storage devices
`instead of being sent to output display devices.
`Printer device 16 is an output display device that can
`produce a printed visual representation of a displayed page
`22 on a piece of paper, a transparency, etc. In the present
`embodiment, printer device 16 is a raster device which
`creates the visual representation with a plurality of printed
`dots arranged in rows and columns corresponding to a
`bitmap. That is, a bitmap can be input to the printer device
`16 and the bits of the bitmap can be displayed as pixels.
`Alternatively, higher-level objects can be sent to the printer
`device 16, and the printer can perform the rasterization
`process.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`Display 18 is an output display device that displays visual
`representations on a screen. Display 18 can include a cath-
`ode ray tube (CRT), whichis typically operated as a raster
`device. Other types of displays include LCDscreens, elec-
`troluminescent displays, etc.
`Other output display device 20 is any other form of device
`used to display a visual representation, in either a temporary
`or permanent form. Other output display devices include
`projection devices,plotters, etc.
`To display visual representations on an output display
`device, such as printer device 16, display 18, or other output
`device 20, one or more types of procedures can be imple-
`mented. One procedure is to input data objects, and then
`rasterize bitmaps from the objects. For example, the object
`of a te