Ulllted States Patent [19]
`Fall et al.
`
`US005991515A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,991,515
`Nov. 23, 1999
`
`[54] METHOD AND APPARATUS FOR
`COMPRESSING AND DECOMPRESSING
`DATA PRIOR TO DISPLAY
`
`5/1993 Inui ....................................... .. 358/296
`5,208,676
`8/1993 Yamada
`~
`5,241,397
`
`5,270,728 12/1993 Lund et a1 5,272,768 12/1993 Bauman et a1.
`
`
`
`Nicholas JI Inventors: Richard NI Fall, Palo Foskett Mt View Davin C Wong
`
`
`
`5,295,233
`
`
`
`Sugiura ................................. .. 3/1994 Ota ........................................ .. 395/115
`
`’
`
`'
`
`’ ,
`
`'
`
`’
`
`5,299,292
`
`3/1994 Kadowaki et al
`
`395/108
`
`Berkeley> an of Cahf-
`
`_
`[73] Asslgneei Adobe Systems Incorporated, San
`Jose, Cahf-
`
`[21] APPL NO‘ 08/893’065
`
`[22] Filed:
`
`Jul- 15’ 1997
`
`_
`_
`Related [15- Appllcatloll Data
`
`[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-
`N°~ 5,539,865
`[51] Int. Cl? ......................... .. B41B 15/00, H04N 1/387;
`H04N 1/40; G06K 9/36
`[52] US. Cl. ........................ .. 395/114; 395/117; 395/115;
`395/116; 395/112; 395/111; 358/450; 358/444;
`382/232; 382/233
`_
`[58] Field of Search ................................... .. 395/114, 115,
`395/116, 110, 111, 112, 108, 117; 382/232,
`233, 235, 358/450, 444, 540, 426, 261.3,
`264’ 432’ 433
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`_
`$322552?’ """"""""""""""
`
`. . . .. 358/296
`5,347,368
`9/1994 Mochizuki . . . . . . . . .
`395/108
`5,354,135 10/1994 Sakagami et a1.
`. . . .. 395/115
`5,355,441 10/1994 Kawai et a1. . . . . . . .
`395/110
`5,374,943 12/1994 Lehmann et a1.
`5,377,312 12/1994 Kobayashi ............................ .. 395/116
`FOREIGN PATENT DOCUMENTS
`
`0320014A2 6/1989 European Pat. on. .
`0475601A2 3/1992 European Pat. Off. .
`0475601A3 3/1992 European Pat. on. .
`
`OTHER PUBLICATIONS
`_
`“
`_
`Fred MlIltZef, lntegratlng Image IIIIO Computers fOr Pllb
`lishing” IEEE/IEICE Global Telecommunications Conf.
`1987, Nov. 15—18, 1987, Japan pp. 19.6.1—19.6.4.
`Okada, er a1-, “Adaptive Coding for Text and Dithered
`Continuous—Tone Images”, Fujitsu Scienti?c & Technical
`Journah vol- 23, NO- 2, 1981191199118 101—109
`Primary Examiner_EdWaI-d L~ C0165
`Assistant Examiner—TWyler Lamb
`Attorney) Agent) Or Firm_pish & Richardson p_C_
`
`ABSTRACT
`[57]
`Amethod 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
`
`5,151,949
`
`9/1992 Miyta . . . . . . . . . . . . . . .
`
`. . . . .. 382/56
`
`Pnmmg or dlsPlaY
`
`5,199,803
`5,207,517
`
`400/121
`4/1993 ShimiZu et a1. .
`5/1993 Ito ......................................... .. 395/110
`
`14 Claims, 23 Drawing Sheets
`
`1O \
`
`12
`
`A
`/14
`
`COMPUTER <——->
`
`V PRINTER
`
`16
`
`V
`
`CRT
`
`18
`
`,2
`\ T
`
`TEXT
`
`G
`
`l
`
`COMPUTER
`
`<———>
`
`12
`
`7
`
`OTHER
`
`R 7
`
`2O
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 001
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 1 0f 23
`
`5,991,515
`
`99 I
`
`12
`
`COMPUTER
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 002
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 2 0f 23
`
`5,991,515
`
`mowwwoomm
`
`
`
`, #965
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 003
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 3 0f 23
`
`5,991,515
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 004
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 4 0f 23
`
`5,991,515
`
`m3
`
`mzmuw
`
`S22E25
`
`mmw
`
`662mm
`
`wow
`
`wow
`
`cow
`
`omw kmuoomo
`
`
`
`omw . houoowa
`
`
`
`wow CQwwEQEQQ
`
`
`
`,. mEmcm
`
`vow :QwwmEEoO
`
`
`....wE.mcm_
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 005
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 5 0f 23
`
`5,991,515
`
`m;
`
`m;
`
`on
`
`B 033
`
`cow
`
`wow
`
`6:02:00
`
`
`
`
`
`Ema 66mm CQmwwEEQO
`
`I 99%
`
`NN
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 006
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 6 0f 23
`
`5,991,515
`
`420
`
`424-1
`
`424-2
`
`424-3
`
`424-4
`
`424-5
`
`424-6
`
`424-7
`
`w H
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 007
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 7 0f 23
`
`5,991,515
`
`I
`450
`lderci'iyeafosrcan /
`_
`Processmg
`
`Provide Scan
`Line Position
`' Data to the
`D ecompressor
`
`452 /
`
`V
`Retrieve Object /454
`Descriptor From
`Memory
`
`455
`
`457
`
`Retrieve Next
`Object
`
`Does
`bject Intersec Yes
`the Scan
`Line?
`
`-
`-
`458
`sltgzgrlsllét'isg of /
`-
`9
`Objects
`
`456
`Any More
`Objects to
`Process?
`
`462
`/
`Pass Object
`Entry Information
`to the
`Appropriate
`Decoder
`
`461
`/
`
`460
`
`Determine Object
`.
`.
`<-— Data Type for <— 5222:? ‘Fits;
`Each Entry in List
`p
`
`466
`/
`
`Retrieve and
`Decompress Data
`for the Object
`from Memory
`
`Has
`
`Partially
`I ecoded'7
`
`464
`
`465
`
`Retrieve State
`I nfo rm ation
`
`Has
`Object Been Compietly
`Decompressed ?
`
`No
`
`Store State
`Information
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 008
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 8 0f 23
`
`5,991,515
`
`42
`
`Rasterize and Compress
`Input Data of a Page Based
`Upon Rasterized Object
`Types and Store
`
`l
`
`Decompress Based upon
`Compression Algorithm and
`Display
`
`44
`
`46
`
`Another Page?
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 009
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 9 0f 23
`
`5,991,515
`
`52
`
`44
`
`69
`
`Yes 70
`
`Set Compression
`Level to Lowest
`Level
`t
`Represent All
`/
`Bands as
`Compressed Form
`of Whitespace
`l
`Create and Empty
`Collector Per
`Band
`
`Display List
`Storage
`Exhausted?
`
`No
`
`Retrieve Input
`Object
`t
`Store Type and
`Bounding Box of
`Input Object in
`Collector for Bands
`Spanned by Object
`l
`Add Input Object
`to Display List
`I
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 010
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 10 0f 23
`
`5,991,515
`
`Select a Band,
`Having Display List
`Entries
`
`72
`/
`
`ls Band A Data in
`Compressed State?
`
`44
`
`Is an Uncompressed
`Band Buffer
`Available?
`
`Decompress Band Data
`Into Uncompressed Band
`Buffer
`
`Rasterize Display List
`Entries of Band A Into /
`Uncompressed Band
`B ff
`77
`u er
`Set A = The Band ID of /
`r—————@<i Band in Uncompressed
`80
`Band Buffer
`Attempt to /
`Compress Band A
`Data
`
`Compressed
`Data Fits?
`
`All Display Lists
`with Entries
`Processed?
`
`At End of
`Page?
`
`88
`
`79. 4%
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 011
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 11 0f 23
`
`5,991,515
`
`44
`
`92
`
`Failure
`
`93
`
`90
`
`Higher Level of
`Compression
`Available?
`
`94
`Advance to Next Higher /
`Compression Level
`
`96
`
`Any Compressed
`Bands Not at Current
`Compression Level?
`
`Select a Band "B" at a
`Lower Compression
`Level
`
`98
`
`1
`
`Decompress Band B into
`Uncompressed Band
`Buffer
`
`l
`
`Attempt to Compress
`Band B Data at Current
`Compression Level
`
`100
`
`102
`
`104
`
`Compressed Band
`B Fits?
`
`1 08
`
`Yes
`Policy to
`Recompress All
`Bands?
`
`Yes
`
`4a
`
`106
`/
`
`Recompress Band B
`at Previous Lower
`Compression Level
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 012
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 12 0f 23
`
`5,991,515
`
`112
`
`113+
`
`115 ->
`
`117 —->
`
`119 —>
`
`112
`
`121 —>
`
`123 —>
`
`125 —>
`
`W 4d
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 013
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 13 0f 23
`
`5,991,515
`
`0.6: 02m 2 H2.
`
`B950
`25
`
`mm?
`
`s .2 tap
`
`All
`
`N:
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 014
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`32f0414|.eehS
`
`5,991,515
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 015
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 15 0f 23
`
`5,991,515
`
`66
`
`New Object Can
`Combine Easily With
`Object Of Same Type?
`
`.
`.
`136
`cmgg'g‘cet'g'ke /
`1
`
`Yes
`
`Enough Storage In
`Collector To Add
`Object's Info?
`
`146
`
`142
`Force Object
`Combinations To /
`Free Storage
`
`144
`Add Object Type /
`And BBox Info To
`Collector
`
`79- 5
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 016
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 16 0f 23
`
`5,991,515
`
`148 @
`
`136
`
`150
`
`Retrieve Bounding
`Box Coordinates
`of New Object and
`Stored Object
`i
`Replace Any BBox
`Coordinates of Stored Object
`152
`with Corresponding BBox
`/
`Coordinates of New Object if
`Conditions Met
`
`154
`
`142
`
`@1 56
`
`158
`
`Compute the Cost of
`Combining Collected Objects
`with Other Collected Objects
`of the Same Type.
`i
`Select Bounding Box
`Coordinates of the Object Pair
`Having the Smallest Cost of
`Combination
`i
`Replace the Two Selected
`162
`Objects with a New Combined
`Object Having the Same Type /
`and Each BBox Coordinate
`from One of the Two Objects
`
`160
`
`More Combinations
`Possible?
`
`Desired Number of
`Combinations
`done?
`
`164
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 017
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 17 0f 23
`
`5,991,515
`
`180
`
`Using Collected Object Data, Find a
`Set of Non-intersecting Rectangular
`Regions that Covers All Objects in
`Band
`
`182
`
`80
`/
`
`Assign Each Region an Empty Set of
`Types and Set Each Region's
`"Marked" Flag to False
`
`184
`
`L
`'= 0
`
`I
`
`i = i + 1
`
`186
`N0
`
`i < Nomber of
`Objects ll'l
`Band
`
`LYes
`
`188
`For the Set of Regions Covering
`Object (i), Add the Type of Object /
`(i) to Each Region and Set Each
`Region's Marked Flag to "True"
`
`194
`Assign the Best
`Compression Algorithm to /
`Each Region Based on the
`Type of Each Region and
`Other Factors
`
`5
`Combine Any Eligible
`Regions Based on Criteria
`
`196
`
`7 ' 5
`‘9’
`
`200
`
`198
`Attempt to Compress Band
`Data from Regions into /
`Compressed Band Buffer
`According to Assigned
`Algorithms
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 018
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 18 0f 23
`
`5,991,515
`
`202
`
`203
`
`204
`
`\y ‘[212 ALGORITHM TABLE
`f ALG Entry 1 (LZW) Parameters 1)
`201 KP 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]
`
`$769 (7e
`
`Text
`
`lmaqe
`
`No
`Yes
`
`No
`No
`
`No
`
`No
`
`No
`
`Yes
`
`Yes
`
`No
`
`No
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`INDEXING TABLE
`Graphic
`208 209
`
`205
`
`21 1
`
`No
`
`(N
`
`Algor?tm Assigned)
`No (Q = 0, CR = 2.0, ALG Entry 1) )}207a
`
`/ (Q = 2, CR = 5.0, ALG Entry 3)
`(Q = 4, CR = 10.0, ALG Entry 5
`
`207
`
`Yes (Q = 0, CR = 2.0, ALG Entry 1)
`2130
`(Q = 0, CR = 3.0, ALG Entry 3)
`(Q = 4, CR = 3.0, ALG Entry 6)
`No (Q = 0, CR = 4.0, ALG Entry 2)
`é (Q = 1, CR = 7.0, ALG Entry 4)
`213
`(Q = 3, CR = 9.0, ALG Entry 5)
`Yes (Q = 0, CR = 2.0, ALG Entry 1)
`(Q = 3, CR = 5.0, ALG Entry 5)
`(Q = 5, OR = 5.0, ALG Entry 6)
`Yes (Q = 0, CR = 2.0, ALG Entry 6)
`(Q = 2, OR = 2.5, ALG Entry 2)
`(Q = 3, CR = 5.0, ALG Entry 7)
`No (Q = 0, CR = 2.0, ALG Entry 6)
`(Q = 1, CR = 3.0, ALG Entry 5) 2075
`(Q = 4, CR = 4.5, ALG Entry 2)
`213
`Yes (Q = 0. CR = 1.5, ALG Entry 5)
`(Q = 2, CR = 2.0, ALG Entry 4)
`
`3759 8%
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 019
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 19 0f 23
`
`5,991,515
`
`210
`
`Create Array of All X Coordinates that /212
`Describe Left or Right Edges of
`Bounding Boxes in Band
`
`I
`
`Sort Array of X Coordinates in Order of 214
`Increasing X and Remove Duplicate /
`Values: nX = Number of Values in
`Resulting Array
`
`I
`
`Create Array of All Y Coordinates that /216
`Describe Top or Bottom Edges of
`Bounding Boxes in Band
`
`I
`
`Sort Array of Y Coordinates in Order of 218
`Increasing Y and Remove Duplicate /
`Values: nY = Number of Values in
`Resulting Array
`
`I
`
`220
`Divide Band into (nX-1) (nY-1) /
`Rectangular Regions
`
`223
`
`221
`REGION DATA STRUCTURE /
`222\ Master Flag
`224
`Slave Flag /
`226\ Marked Flag 228
`X Index __/
`230\ Y Index
`232
`Object Types /
`
`.
`
`749' q“
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 020
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 20 of 23
`
`5,991,515
`
`For Each Row of Regions,
`Combine Adjacent Regions
`Having the Same
`Compression Algorithm
`
`Combine Pairs of Non-
`
`Empty Regions with Empty
`Regions separating the Pair
`if Hardware Constraints
`
`Violated on that Row of
`
`Regions
`
`.
`Hardware Constraints
`Still Violated in a Row?
`
`Combine Vertically Adjacent
`Regions When Possible and
`Cost Within Limits
`
`Force
`
`Combinations of
`Addmonm
`Regions Within
`Row
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 021
`
`

`
`U.S. Patent
`
`N0v.23, 1999
`
`Sheet 21 of 23
`
`5,991,515
`
`Designate and Mark
`Lower Left Region as
`Master and Rest of
`
`Regions in Group as
`Slaves
`
`Augment the Object
`Type of the Master with
`All the Object Types of
`the Slave Tiles
`
`Mark Master with the
`Boundaries of Set of
`
`Slaves
`
`Cause All Slaves to Point
`to Master
`
`Read Attributes for a
`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
`
`‘ nother Region
`in Region
`Buffer?
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 022
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 22 of 23
`
`5,991,515
`
`290
`
`Load a Number of Regions
`Descriptors into
`Decompression Buffer
`
`296
`
`Determine Regions Crossed
`By Next Scan Line
`
`298
`
`Scan Line Pointer at a
`Region?
`
`Output Background Pixels to
`Display Until Scan Line Pointer
`Points to Start of Region or
`End of scan Line
`
`Get Decompression State for
`Region
`
`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?
`
`Completed Any
`
`yes
`
`Load Additional Region
`
`Regions? I Descriptors
`
`312
`
`Pointer at End of Page?
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 023
`
`

`
`U.S. Patent
`
`Nov. 23, 1999
`
`32f0324|.eehS
`
`5,991,515
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 024
`
`

`
`7
`7
`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 May 5, 1997, which is a continuation of
`US. 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 US. Pat. No.
`5,539,865.
`
`5
`
`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
`image or “visual representation” onto a sheet of paper or 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 number of 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. When display-
`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 liigh-resolution representations with more
`realistic attributes has become more prominent. For
`example, using a laser printer capable of printing black—and—
`Wliite images at a resolution of 600 dots per inch (dpi), a
`typical displayed page requires about 3.8xl05 bytes of
`memory. When printing a page of color pixels, for example,
`having 8 bits of color per pixel, the memory requirement
`
`.
`
`2
`l2l><l05 bytes of memory. With such
`increases to about
`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 bitmap is 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 methods of 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 always result 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 wl1icl1 is used to store
`compressed data objects of varying types may become full.
`If more objects remain to be processed for a given page, then
`the compression ratio 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 process is
`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.
`SUMMARY OF THE INVENTION
`
`The present invention provides a method and apparatus
`for compressing and deconipressing display data. The
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 025
`
`

`
`7
`7
`5 991 515
`
`3
`present invention compresses multiple types of data objects
`using compression mechanisms that 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 sent directly
`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 gaphics 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 compression ratio 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 be initiated prior to 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 compress the 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 background data 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.
`
`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
`become apparent to 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
`
`5
`
`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. 2b;
`FIG. 2d is a diagrammatic illustration of a page of objects,
`the page being divided into bands;
`FIG. 26 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 fiow 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. 4b 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;
`is a diagrammatic illustration of the band of
`FIG.
`objects of FIG. 46 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. Sb 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;
`
`Veritas Techs. LLC
`Exhibit 1007
`Page 026
`
`

`
`7
`7
`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
`
`invention is well—suited for reducing the
`The present
`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.
`Anumber of 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 o , as well as
`a “pixel map” having more information for eaca 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
`1']1lC1’OpI'OC€SSOI',
`3. 1'l'1CI1'lOfy bus, random IICCCSS I1'1CI1'lOI'y
`(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 embodiment of 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.
`
`/
`
`_
`
`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), which is typically operated as a raster
`device. Other types of displays include LCD screens, 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 text character can include associated information which
`specify how the character is to be displayed, such as
`positional coordinates, size, font, etc.
`A well known page description language for specifying
`objects and related information is the PostScript® language
`by Adobe Systems, Inc. of San Jose, Calif. The ob_ject can,
`for example, include a bitmap describing a text character, or
`the object can reference or point to stored character outlines
`which describe the shape of a character and include other
`rasterizing information, such as font and size. Awell-known
`character outline format is the Type 1® format, by Adobe
`Systems, Inc. In addition, objects such as graphical shapes
`can be stored as graphic primitives, which are basic shape
`objects used to form more complex graphical sha