United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,638,498
`
`Tyler et al.
`
`[45] Date of Patent:
`
`Jun. 10, 1997
`
`US005638498A
`
`[54] METHOD AND APPARATUS FOR
`REDUCING STORAGE REQUIREMENTS
`FOR DISPLAY DATA
`
`[75]
`
`Inventors: William B. Tyler, Carmel; Nicholas J.
`Foskett, Mountain View; Soon Y.
`Kong, Cupertino; Richard N. Fall,
`Palo Alto; Ronald S. Gentile. Atherton.
`all of Calif.
`
`[73] Assignee: Adobe Systems Incorporated. San
`Jose, Calif.
`
`[21] Appl. No.: 484,344
`
`[22] Filed:
`
`Jun. 7, 1995
`
`Related US. Application Data
`
`[63] Continuation-impart of Ser. No. 974,204, Nov. 10, 1992.
`
`Int. Cl.6 ..................................................... G06K 15/00
`[51]
`
`[52] US. Cl.
`..
`.. 395/117; 395/115
`
`[53] Field of Search ..................................... 395/114, 112,
`395/115, 116, 117, 509, 520, 521, 523;
`382/232, 233, 235, 236; 358/450, 444,
`540, 426, 261.3, 261.4, 432, 433
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`............................. 358/41
`7/1991 Sasaki et a1.
`5,034,804
`..... 395/114
`9/1992 Wood et a1.
`5,150,454
`9/1992 ijata .................. 382/56
`5,151,949
`4/1993 Shimizu et a].
`..... 400/121
`5,199,803
`5/1993 Ito ....................... 400/121
`5,207,517
`5/1993 Inui ..................... 358/296
`5,208,676
`8/1993 Yamada ........... 358/296
`5,241,397
`5,270,728 12/1993 Lundetal. .......... 346/1.1
`5,272,768
`12/1993 Bauman et a1.
`..... 395/110
`1/1994 Sugiura ............... 395/116
`5,276,780
`
`3/1994 Ota .......................... 395/115
`5,295,233
`
`3/1994 Kadowaki et a1.
`..... 395/108
`5,299,292
`
`.............................. 358/296
`5,347,368
`9/1994 Mochizuki
`
`
`
`
`...................... 400/124
`10/1994 Sakagami et al.
`5,354,135
`10/1994 Kawai et a1. ........... 395/115
`5,355,441
`
`.
`.......... 347/9
`12/1994 Lehmann et al.
`5,374,943
`5,377,312 12/1994 Kobayashi
`.............................. 395/116
`
`FOREIGN PATENT DOCUMENTS
`
`0320014A2
`0475601A2
`0475601A3
`
`6/1989 European Pat. 01f. ........... 15/72
`
`3/1992 European Pat. 01f.
`.
`.. 15fl2
`3/1992 European Pat. 01f.
`................... 15/72
`
`OTHER PUBLICATIONS
`
`Okada, Yoshiyuki et al., “Adaptive Coding for Text and
`Dithered Continuous—Tone Images,”, Fujitsu Sci. Tech, Jun.
`1987, pp. 101—109.
`Mintzer, Fred, “Integrating Image Into Computers for Pub-
`lishing, ” IEEE, Conference Record vol. 2, Nov. 15—18,
`1987, pp. 19.61—19.64.
`
`Primary Examiner—Arthur G. Evans
`Attorney, Agent, or Firm—Fish & Richardson RC.
`
`[57]
`
`ABSTRACT
`
`A method and apparatus for reducing storage requirements
`for display data on a computer system. Data objects to be
`displayed are organized into display lists and each data
`object includes an object type, such as text, graphic, and
`image. The data objects are rasterized into an uncompressed
`band buffer and divided into non-intersecting bitmap regions
`each identified with one or more object types. Each non-
`empty region is assigned a compression algorithm depen-
`dent upon the type of the region and specified compression
`constraints. The regions are combined with each other into
`larger regions if appropriate, and each region is compressed
`using its assigned compression algorithm into a compressed
`band buffer, thus reducing the required storage space for the
`data objects. The compressed data is decompressed in scan
`line order with a selected decompression algorithm corre-
`sponding to the assigned compression algorithms to produce
`uncompressed output data. The uncompressed output data is
`supplied to an output display device for display.
`
`60 Claims, 18 Drawing Sheets
`
`
`
`Commvault Ex. 1032
`Commvault v. Realtime
`US Patent No. 9,054,728
`
`Page 1
`
`Page 1
`
`Commvault Ex. 1032
`Commvault v. Realtime
`US Patent No. 9,054,728
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 1 of 18
`
`5,638,498
`
`
`
`
`GQE’EPQTEQ «AMA.
`
`
`
`
`Page2
`
`u?%ER 3/
`
`3 <
`
`3
`
`
`
`”9
`
`}m~wm*}
`
`figzzra I;
`
`Page 2
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 2 of 18
`
`5,638,498
`
`
`IIllnlllllll.Illl'lnlnl'llullllll‘llll.lull
`
`m8&5
`
`Page 3 -
`
`45.66
`
`memmmoomm
`
`mMPDmEOO
`
`m;
`
`Page 3
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 3 of 18
`
`5,638,498
`
`40
`
`\
`
`figure 3
`
`® 42
`
`RASTERIZE AND
`
`COMPRESS INPUT
`
`DATA OF A PAGE
`BASED UPON
`
`DISPLAY
`
`RASTERIZED OBJECT
`
`TYPESANDSTORE
`
`DECOMPRESS
`
`BASED UPON
`COMPRESSION
`ALGORITHM AND
`
`44
`
`46
`
`YES
`
`ANOTHER
`
`PAGE?
`
`48
`
`NO
`
`@ 49
`
`Page 4
`
`Page 4
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 4 of 18
`
`5,638,498
`
`52
`
`® figure 4a
`
`SET COMPRESSION
`LEVEL TO LOWEST
`
`LEVEL
`
`54
`
`/ 44
`
` REPRESENT ALL BANDS
`
`AS COMPRESSED FORM
`OF WHITESPACE
`
`' CREATE AN EMPTY
`
`COLLECTOR PER BAND
`
`58 @
`
`I
`
`69
`
`_____,
`
`END OF
`PAGE?
`
`60
`YES
`
`YES
`
`DISPLAY
`LIST EMPTY? ‘
`
`O
`7
`
`NO
`
`
` DISPLAY
`LIST STORAGE
`
`EXHAUSTED?
`
`NO
`
`RETRIEVE INPUT
`OBJECT
`
`I
`54
`
`STORE TYPE AND
`BOUNDING BOX OF INPUT
`
`
`
`OBJECT IN COLLECTOR
`FOR BANDS SPANNED BY
`OBJECT
`
`ADD INPUT OBJECT
`TO DISPLAY LIST
`
`68
`
`Page 5
`
`Page 5
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 5 of 18
`
`5,638,498
`
`0
`
`4“
`,/’
`
`72
`
`IS AN
`
`UNCOMPRESSED
`
`75
`
`NO
`
`
`
`SELECT A BAND, "A",
`HAVING DISPLAY LIST
`
`
`
`
`ENTRIES
`
`BAND BUFFER
`
`AVAILABLE?
`
`74
`
`S BAND A DATA I
`
`COMPRESSED
`
`
`
`
`DECOMPRESS
`STATE?
`BAND DATA INTO
`
`NO
`UNCOMPRESSED
`BAND BUFFER
`
`
`
`
`RASTERIZE DISPLAY LIST
`
`ENTRIES OF BAND A
`
`78
`
`mo UNCOMPRESSED
`BAND BUFFER
`
`77
`SET A = THE BAND ID
`OF BAND IN
`UNCOMPRESSED
`
`
`
`ATTEMPT TO
`COMPRESS
`BAND A DATA
`
`so
`
`
`BAND BUFFER
`
`COMPRESSED
`DATA FITS?
`
`82
`
`No
`
`YES
`
`84
`
`NO
`
`
`ALL DISPLAY
`LISTS WITH
`
`
`ENTRIES
`PROCESSED?
`
`
`86
`
`YES
`AT END OF
`PAGE?
`
`NO
`
`YES
`
`@ 88
`
`FIGURE 43
`
`Page 6
`
`Page 6
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 6 of 18
`
`.
`
`5,638,498
`
`“\
`
`e
`
`figure 4c
`
`
`
`90
`
`92
`
`NO
`
`FAILURE
`
`
`
`HI HER LEVEL
`G
`OF COMPRESSION
`
`
`AVAILABLE?
`
`YES
`ADVANCE TO NEXT @
`
`
`HIGHER COMPRESSION
`LEVEL
`
`94
`
`93
`
`
`
`ANY
`COMPRESSED BANDS
`
`
`NOT AT CURRENT
`
`
`COMPRESSION
`LEVEL ?
`
`
`YES
`
`
`
`
`SELECT A BAND“B"AT A
`LOWER COMPRESSION
`LEVEL
`
`
`98
`
`DECOMPRESS BAND B
`INTO UNCOMPRESSED
`BAND BUFFER
`
`ATTEMPT TO
`
`COMPRESS BAND B
`DATA AT CURRENT
`
`100
`
`102
`
`106
`-
`
`COMPRESSION LEVEL ' ECOMPRESS
`BAND B AT PREVIOUS
`
`LOWER
`COMPRESSION
`LEVEL
`
`NO COMPRESSED
`BAND B FITS?
`
`104
`
`YES 108
`
`
`POLICY TO
`RECOMPRESS
`
`
`ALL BANDS?
`
`
`YES
`
`Page 7
`
`Page 7
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 7 of 18
`
`5,638,498
`
`9%;
`
`
`
`Page 8
`
`Page 8
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 8 of 18
`
`5,638,498
`
`9m;02mw_“x2.
`
`m?EDUNR
`
`Page 9
`
`Page 9
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 9 of 18
`
`5,638,498
`
`
`
`Page 10
`
`Page 10
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 10 of 18
`
`5,638,498
`
`66 \.
`
`figure 5
`
`130 134
`
`EW OBJEC
`
`
`
`
`CAN COMBINE
`
`
`
`EASILY WITH
`
`
`
`OBJECT OF SAME
`
`TYPE?
`
`
`
`136
`
`COMBINE LIKE
`
`OBJECTS
`
`
`
`
`
`ENOUGH
`
`YES
`STORAGE IN
`
`COLLECTOR TO ADD
`
`OBJECT'S INFO?
`
`
`
`
`
`
`COMBINATIONS TO
`
`FREE STORAGE
`
`FORCE OBJECT
`
`
`
`ADD OBJECT TYPE
`
`AND BBOX INFO TO
`
`COLLECTOR
`
`146
`
`Page 11
`
`Page 11
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 11 of 18
`
`5,638,498
`
`150
`
`
`RETRIEVE
`BOUNDING BOX
`
`
`COORDINATES OF
`
`
`NEW OBJECT AND
`
`
`STORED OBJECT
`
`152
`
`
`
`REPLACE ANY BBOX
`COORDINATES OF STORED
`
`
`OBJECT WITH CORRESPONDING
`
`
`BBOX COORDINATES OF NEW
`
`
`OBJECT IF CONDITIONS MET
`
`
`
`156
`
`
`
`COMPUTE THE COST OF
`COMBINING COLLECTED
`OBJECTS WITH OTHER
`
`COLLECTED OBJECTS OF THE
`SAME TYPE
`
`
`
`
`158
`
`
`
`
`
`SELECT BOUNDING BOX
`COORDINATES OF THE OBJECT PAIR
`
`
`HAVING THE SMALLEST COST OF
`
`COMBINATION
`
`160
`
`REPLACE THE TWO SELECTED
`OBJECTS WITH A NEw COMBINED
`OBJECT HAVING THE SAME TYPE
`AND EACH BBOX COORDINATE
`
`FROM ONE OF THE TWO OBJECTS
`
`162
`
`168
`
`YES
`164
`
`DESIRED
`
`MORE
`NUMBER OF
`
`COMBINATIONS
`
`
`POSSIBLE?
`COMBINATIONS
`
`
`
`DONE?
`
`
`NO
`
`166
`
`Page 12
`
`Page 12
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 12 of 18
`
`5,638,498
`
`®
`
`
`
`
`
`
`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
`
`
`186
`
`figure 8
`
`182
`
`184
`
`[80
`
`i < NUMBER OF
`
`NO
`
`
`OBJECTS IN
`BAND?
`
`
`
`FOR THE SET OF REGIONS
`COVERING OBJECT(i),
`
`
`ADD THE TYPE OF
`
`
`
`
`OBJECTII) TO EACH
`REGION AND SET EACH
`REGION'S MARKED FLAG
`TO "TRUE"
`
`188
`
`194
`
`196
`
`ASSIGN THE BEST
`COMPRESSION
`
`ALGORITHM TO EACH
`
`REGION BASED ON THE
`
`TYPE OF EACH REGION
`
`AND OTHER FACTORS
`CRITERIA
`
`COMBINE ANY ELIGIBLE
`REGIONS BASED ON
`
`'200
`
`198
`
`
`
`
`
`ATTEMPT TO COMPRESS BAND
`
`DATA FROM REGIONS INTO
`
`COMPRESSED BAND BUFFER
`ACCORDING TO ASSIGNED
`ALGORITHMS
`
`
`
`
`
`
`
`Page 13
`
`Page 13
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 13 0f 18
`
`5,638,498
`
`202 1
`
`212
`
`203 ALGORITHM TABLE {204
`'(
`201 NALG ENTRY 1M) [PARAMETERS1] 2
`
`[PARAMETERSZ]
`ALG ENTRY2 (DOT-BASED)
`ALG ENTRY 3 (LZW)
`[PARAMETERsa]
`ALG ENTRY4 (DOT-BASED)
`[PARAMETERS4]
`ALG ENTRY 5 (W AND DPCM)
`[PARAMETERss]
`ALG ENTRY e (sz AND DPCM)
`[PARAMETERSS]
`ALG ENTRY 7 (PDR)
`[PARAMETERS7]
`
`figure 8a
`
`TEXT IMAGE GRAPHIC
`
`/205
`INDEXING TABLE
`( o ALG94THM ASSIGNED) 2"
`
`208
`
`209
`
`N0
`
`NO
`
`N0
`
`YES
`
`NO
`
`NO
`
`NO
`
`YES
`
`NO
`
`NO
`
`0 = 0, CR = 2.0, ALG ENTRY 1)
`NO
`2133 /(Q = 2, CR = 5.0, ALG ENTRY 3)
`213”
`(Q = 4, OR = 10.0, ALG ENTRY 5)
`
`207a
`
`YES/(Q=0,CR=2.0,ALGENTRY1) } 207
`
`213a
`
`(Q = 0, CR = 3.0, ALG ENTRY 3)
`(Q = 4. CR = 3.0, ALG ENTRY 5)
`YES NS/AQ = 0, OR = 4.0, ALG ENTRY 2)
`213 ____J(Q = 1, CR = 7.0, ALG ENTRY 4)
`\—-(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, CR = 6.0, ALG ENTRY 6)
`
`NO
`
`YES
`
`YES
`
`YES
`
`YEs
`
`NO
`213
`
`YES
`
`YES
`
`YES
`
`.
`
`(0 = 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 s)
`(Q = 1, CR = 3.0, ALG ENTRY 5)
`(o = 4. CR = 4.5, ALG ENTRY 2)
`
`(0 = 0, CR = 1.5. ALG ENTRY 5)
`(Q = 2, CR = 2.0, ALG ENTRY 4)
`
`2071’
`
`figure 85
`
`'
`
`Page 14
`
`Page 14
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 14 of 18
`
`5,638,498
`
`CREATE ARRAY OF ALL X
`COORDINATES THAT DESCRIBE
`LEFT OR RIGHT EDGES OF
`BOUNDING BOXES IN BAND
`
`
`
`SORT ARRAY OF X COORDINATES
`IN ORDER OF INCREASING X AND
`REMOVE DUPLICATE VALUES;
`nX = NUMBER OF VALUES IN
`RESULTING ARRAY
`
`
`CREATE ARRAY OF ALL Y
`COORDINATES THAT DESCRIBE
`TOP OR BOTTOM EDGES OF
`
`BOUNDING BOXES IN BAND
`
`
`
`SORT ARRAY OF Y COORDINATES
`IN ORDER OF INCREASING Y AND
`REMOVE DUPLICATE VALUES;
`nY = NUMBER OF VALUES IN
`RESULTING ARRAY
`
`
`
`DIVIDE BAND INTO (nX-1)(nY-1)
`RECTANGULAR REGIONS
`
`182.
`
`/
`
`2
`
`12
`
`figure 9
`
`214
`
`276
`
`218
`
`220
`
`@
`
`221 -\
`
`REGIQN DATA STRUCTURE
`
`222 \MASTER FLAG
`SLAVE FLAG—/ 224
`'226 «.MARKED FLAG
`
`x INDEXv- 228
`230 VY INDEX
`OBJECT TYPES/ 232
`
`figure 9a
`
`Page 15
`
`Page 15
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 15 of 18
`
`5,638,498
`
`240
`
`® 196
`
`I
`
`FOR EACH ROW OF REGIONS,
`COMBINE ADJACENT REGIONS
`HAVING THE SAME COMPRESSION
`
`ALGORITHM
`
`242
`
`COMBINE PAIRS OF NON-EMPTY
`
`REGIONS WITH EMPW REGIONS
`
`REGIONS
`
`SEPARATING THE PAIR IF
`
`HARDWARE CONSTRAINTS
`
`VIOLATED ON THAT ROW OF
`
`246
`
`
` HARDWARE
`CONSTRAINTS
`
`
`STILL VIOLATED
`IN A ROW?
`
`
`YES
`
`NO
`
`COMBINE VERTICALLY
`
`LIMITS
`
`ADJACENT REGIONS WHEN
`POSSIBLE AND COST WITHIN
`
`@ 2”
`
`figure 1 0
`
`248
`
`FORCE
`
`COMBINATIONS OF
`ADDITIONAL
`REGIONS WITHIN
`
`ROW
`
`250
`
`Page 16
`
`Page 16
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 16 of 18
`
`5,638,498
`
`260
`
`
`
`
`
`
`
`
`
`266
`
`
`
`figure 11
`
`242
`
`274
`
`
`DESIGNATE AND MARK
`LOWER LEFI' REGION AS
` 262
`MASTER AND REST OF
`REGIONS IN GROUP AS
`
`SLAVES
`x
`
`
`
`
`AUGMENT THE OBJECT
`TYPE OF THE MASTER
`WITH ALL THE OBJECT
`
` 264
`TYPES OF THE SLAVE
`
`TILES
`
`
`
`MARK MASTER WITH
`THE BOUNDARIES OF
`SET OF SLAVES
`
`
`TO MASTER
` READ ATTRIBUTES FOR A
`
`
`USING ATTRIBUTES
`
`
`
`CAUSE ALL
`SLAVES TO POINT
`
`
`268
`
`NON-EMPTY REGION
`FROM REGION BUFFER
`
` CREATE REGION DESCRIPTOR
`
`FOR NON-EMPTY REGION
`
`277
`
`
`
`
`ATTEMPT TO COMPRESS
`ON-EMPTY REGION FROM
`
`
`UNCOMPRESSED BAND
`BUFFER SPECIFIED BY
`
`ATTRIBUTES
`BUFFER?
`
`
` ANOTHER
`REGION IN REGION
`
`
`YES
`
`Page 17
`
`Page 17
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 17 of 18
`
`5,638,498
`
`290
`
`figure 13
`
`
`
`LOAD A NUMBER OF REGIONS
`DESCRIPTORS INTO
`DECOMPRESSION BUFFER
`
`
`292
`
`/ 46
`
`DETERMINE REGIONS
`CROSSED BY NEXT
`SCAN LINE
`
`296
`
`300
`
`
`
`
`OUTPUT BACKGROUND
`PIXELS TO DISPLAY
`298
`UNTIL SCAN LINE
`
`
`
`SCAN LINE
`
`
`POINTER POINTS TO
`POINTER AT A
`
`
`START OF REGION OR
`
`REGION?
`
`
`END OF SCAN LINE
`
`
`POINTER AT
`
`START OF
`
`YES
`REGION?
`
`NO
`
`GET DECOMPRESSION
`STATE FOR REGION
`
`302‘
`
`DECOMPRESS AND
`OUTPUT REGION DATA
`UNTIL SCAN LINE
`POINTER POINTS TO
`
`END OF REGION
`
`306
`
`'OINTER AT END
`OF SCAN LINE?
`
`YES
`
`31 2
`
`COMPLETED
`
`LOAD ADDITIONAL
`
`ANY REGIONS?REGIONDESCRIPTORS
`
`NO
`
`POINTER AT
`END OF PAGE?
`
`314
`YES
`
`_
`31 6
`
`Page 18
`
`Page 18
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 18 of 18
`
`5,638,498
`
`vmm
`
`SQsaw
`
`Page 19
`
`Page 19
`
`

`

`1
`METHOD AND APPARATUS FOR
`
`REDUCING STORAGE REQUIREMENTS
`FOR DISPLAY DATA
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation-impart of co-pending
`parent patent application 07/974,204. filed Nov. 10. 1992 on
`behalf of Ronald S. Gentile. entitled, “Method and Appara-
`tus for Processing Data for a Visual-Output Device with
`Reduced Buffer Memory Requirements,” assigned to the
`assignee of this present application, and which is incorpo-
`rated by reference herein.
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates generally to the display of
`data by output devices, and more particularly to a method
`and apparatus for reducing memory storage requirements
`when displaying data 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.”
`A printer 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 anumber. of image
`types. including text, graphics, photographic images, etc.
`Data of these types can be efliciently 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 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`4s
`
`50
`
`55
`
`65
`
`i63&498
`
`2
`
`typical displayed page requires about 3.8><106 bytes of
`memory. When printing a page of color pixels, for example,
`having 8 bits per color per pixel, the memory requirement
`increases to about 121x106 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 noticeable 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 the print engine, monitor, or other output
`display device.
`A problem with the compression method of the prior art
`occurs when dilferent 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.
`
`SUMMARY OF THE INVENTION
`
`The present invention provides a method and apparatus
`for storing display data with reduced storage requirements.
`The present invention compresses multiple types of data
`objects using compression mechanisms that are optimized
`for each type of object according to user constraints. The
`compressed objects are then decompressed using a related
`decompression mechanism and sent to the output display
`device for 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 also depends on the size of the avail-
`able memory to store the compressed data and overall page
`
`Page 20
`
`Page 20
`
`

`

`5,638,498
`
`3
`analysis. The compressor produces compressed bitmap
`regions and stores the compressed bitmap regions in digital
`read/write memory associated with an output device. A
`decompressor then decompresses the compressed bitmap
`regions with a selected decompression mechanism deter-
`mined by the selected compression mechanisms. The
`decompression mechanism for a particular compressed bit-
`map region is dependent upon the compression mechanism
`used to compress the bitmap region. The decompressor 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 compressor
`according to the assigned compression algorithms. The
`decompressor decompresses one page at a time by deter-
`mining where an output scan line intersects regions on that
`scan line and decompressing the compressed regions when
`the scan line intersects the regions. The decompressor out—
`puts background data to the output device when the scan line
`does not intersect the compressed regions.
`In another aspect of the present invention, a method for
`providing a digital output with selective object compression
`and decompression includes steps of receiving output data
`having a type and compressing the output data with a
`selected compression algorithm chosen from a set of com~
`pression algorithms to produce compressed output data. The
`selected compression algorithm for the output data is depen-
`dent upon the type of the output data and meets a user’s
`specified constraints for compression. The compressed out-
`put data is stored in digital read/write memory and is
`decompressed with a selected decompression algorithm to
`produce uncompressed output data. The decompression
`algorithm is chosen from a set of decompression algorithms
`and is dependent upon the compression algorithm used to
`compress the compressed data. The uncompressed output
`data is then supplied to an output display device.
`The output data is stored as objects in display lists
`including an object type and an object location on a page of
`data. The display lists correspond to multiple bands into
`which the page is organized. The objects of one of the
`display lists are rasterized as bitmap objects in an uncom-
`pressed band and stored in an uncompressed band buffer.
`The band is partitioned into non-intersecting bitmap regions,
`where each bitmap region has at least one type correspond-
`ing to the type(s) of the object(s) which the region covers,
`or an empty type if no object is covered. A compression
`method is assigned to each region based on the types of the
`regions and any user constraints that include the compres-
`sion ratio of the compression method and visual quality of
`the data after being compressed and decompressed. Adjacent
`regions and regions which include empty regions between
`them. and having the same assigned compression method.
`are preferably combined into larger regions. The non-empty
`regions of the uncompressed band are then compressed and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`stored in a compressed band buffer of the digital read/write
`memory. This step includes checking if the compressed
`regions fit in the compressed band butfer when compressed.
`If the band doesn’t fit when compressed. previously-
`compressed bands are decompressed and recompressed to
`provide more storage space for the compressed band.
`Another band of the page is then rasterized and compressed.
`Once all the bands of the page are compressed, a page of
`compressed data is decompressed in scan line order and
`supplied to the output device. Background display data is
`provided to the output device for portions of the page that
`are not included by compressed regions.
`An advantage of the present invention is that object data
`is compressed with compression mechanisms suited for each
`type of object included in display data. This allows much
`greater optimization of compression in that a compression
`mechanism can be chosen for each object type that provides
`the optimal tradeoiiC between image quality and level of
`compression. This permits a dramatic reduction in memory
`space requirements with minimal loss of image quality. In
`addition, only areas of a page that include object display data
`are compressed, so that ‘Whitespace” or background areas
`do not have to be compressed and stored in memory. This
`allows an even greater reduction in memory space require-
`ments for the display data. With less memory requirements
`for storing displayed data, the cost to produce an output
`display device can be drastically decreased.
`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
`
`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. 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. 4b is a flow diagram illustrating the second portion
`of the rasterize and compress input data step of FIG. 3;
`FIG. 40 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;
`
`Page 21
`
`Page 21
`
`

`

`5,638,498
`
`5
`
`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;
`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 OF THE
`PREFERRED EMBODIMENT
`
`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.
`A number 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 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 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
`AF-compatible or Apple Macintosh personal computer),
`workstations (such as a SUN or Hewlett-Packard
`workstation). etc. Computers 12 typically each include a
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`45
`
`50
`
`55
`
`65
`
`6
`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 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
`16, and the printer can perform the rasterization process.
`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 Mountain View, Calif. The object
`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 includes other rasterizing information, such as font and
`size. A well-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
`shapes. From the objects, the computer 12 or output device
`16, 18 or 20 can rasterize a bitmap and either send the
`