e
`United States Patent 19
`Tyler et al.
`
`US005638498A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,638,498
`Jun. 10, 1997
`
`[54] METHOD AND APPARATUS FOR
`REDUCING STORAGE REQUIREMENTS
`FOR DISPLAY DATA
`
`[75]
`
`Inventors: William B. Tyler, Carmel; Nicholas Jj.
`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 U.S. Application Data
`
`10/1994 Sakagami et al. 00...esses 400/124
`5,354,135
`
`.....
`10/1994 Kawai et al.
`5,355,441
`.
`12/1994 Lehmann et al.
`5,374,943
`..ssccscscssssesssssssoeee 395/116
`5,377,312 12/1994 Kobayashi
`FOREIGN PATENT DOCUMENTS
`0320014A2
`6/1989 European Pat. Off,
`...sssssssssecsse 15/72
`
`.
`. 15/72
`0475601A2
`3/1992 European Pat. Off.
`3/1992 European Pat. Off. wu.see 15/72
`0475601A3
`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, ” IERE, Conference Record vol. 2, Nov. 15-18,
`1987, pp. 19.6.1~19.6.4.
`
`Primary Examiner—Arthur G. Evans
`Attorney, Agent, or Firm—Fish & Richardson P.C.
`[63] Continuation-in-part of Ser. No. 974,204, Nov. 10, 1992.
`[57]
`ABSTRACT
`[SA]
`Tint. C18 occccccccccccccssscssccsassessesenresrecsessssesee G06K 15/00
`
`.
`.
`[52] U.S. Cl.
`..
`.. 395/117; 395/115
`
`method and apparatus for reducing storage requirements
`[58] Field of Search wssssnsnmnemnes 395/114, 112,
`for display data on a computer system. Data objects to be
`395/115. 116. 117, 509, 520, 521, 523:
`displayed are organized into display lists and each data
`382/232 233 35 236: 358/450. 444.
`object includes an object type, such as text, graphic, and
`540 426 261 3 261 4 432 433
`EI image. The data objects are rasterized into an uncompressed
`Cited
`band buffer and divided into non-intersecting bitmap regions
`Cite
`each identified with one or more object types. Each non-
`eferences
`U.S. PATENT DOCUMENTS
`empty region is assigned a compression algorithm depen-
`358/41
`7/1991 Sasaki et al.
`dent upon the type of the region and specified compression
`9/1992 Wood etal. ..........,395/114
`constraints. The regions are combined with each other into
`9/1992 Miyata ssossssscsssrssaessssesseneseen 382/56
`larger regionsif appropriate, and each region is compressed
`4/1993 Shimizu et ab.
`....secssscsseseseeseeee 400/121
`usingits assigned compression algorithm into a compressed
`5,199,803
`
`5,207,517—S/V993 Tt ressrcsssssesssssesssecesocenseneseeesees 400/121 band buffer, thus reducing the required storage space for the
`5,208,676
`5/1993 Inti .....seccssssssoessoesenssenseecennessees 358/296
`data objects. The compressed data is decompressed in scan
`5,241,397
`8/1993 Yarmada ......sscssesssssveesessnseersnones 358/296
`line order with a selected decompression algorithm corre-
`
`5,270,728 12/1993 Lund et ab. sssseseesesseeessneoseseee 346/1.1_snonding to the assigned compression algorithms to produce
`5,272,768
`12/1993 Bauman et al.
`svssesssreresresnn 395/110
`uncompressed output data. The uncompressed output data is
`5295233
`3/1994 Oten segnts
` SUPPlied to an ouput display device for display
`.........scssssseee 395/108
`3/1994 Kadowaki etal.
`5,299,292
`5,347,368
`9/1994 Mochizuki
`..........ssscssssseneeenee 358/296
`60 Claims, 18 Drawing Sheets
`
`56
`[6]
`
`R
`
`5.034.804
`5150454
`
` 5,151,949
`
`BBmmnng
`
`US Patent No. 9,054,728
`
`Commvault Ex. 1032
`Commvault v. Realtime
`
`Page1
`
`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
`
`COMPUTER
`
`Imag,
`
`
` LeOTHERso
`
`Page 2
`
`Page 2
`
`

`

`U.S. Patent
`
`rc
`
`Jun. 10, 1997
`
`Sheet 2 of 18
`
`5,638,498
`
`_weeeeeeeeaeeeeeeree
`
`WIDIG
`
`HOSSA0OUd
`
`HALNdNOO
`
`ct
`
`
`
`vzanh,
`
`gani,
`
`Page3 -
`
`Page 3
`
`
`

`

`US. Patent
`
`Jun.10, 1997
`
`Sheet 3 of 18
`
`5,638,498
`
`to
`
`\
`
`Figure 3
`
`Curt) #
`
`RASTERIZE AND
`COMPRESSINPUT
`DATA OF A PAGE
`BASED UPON
`RASTERIZED OBJECT
`TYPES AND STORE
`
`DISPLAY
`
`DECOMPRESS
`BASED UPON
`COMPRESSION
`ALGORITHM AND
`
`44
`
`46
`
`YES
`
`ANOTHER
`
`PAGE?
`
`48
`
`NO
`
`Cone)
`
`Page 4
`
`Page 4
`
`

`

`5,638,498
`
`US. Patent
`
`Jun. 10, 1997
`
`Sheet 4 of 18
`
`
`
`SET COMPRESSION
`LEVEL TO LOWEST
`LEVEL
`
`REPRESENT ALL BANDS
`AS COMPRESSED FORM
`OF WHITESPACE
`
`69
`
`
`
`CREATE AN EMPTY 58(done”)
`
`COLLECTOR PER BAND
`
`0
`60
`a END OF7_YES DISPLAY X~"
`
`
`PAGE?
`LIST EMPTY? ,
`
`YES
`
`NO
`
`DISPLAY
`LIST STORAGE
`EXHAUSTED?
`
`
`
`OF
`
`RETRIEVE INPUT
`OBJECT
`
`|
`64
`
`STORE TYPE AND
`BOUNDING BOX OF INPUT
`OBJECT IN COLLECTOR
`FOR BANDS SPANNED BY
`
`OBJECT
`
`ADD INPUT OBJECT
`TO DISPLAYLIST
`
`68
`
`Page 5
`
`Page 5
`
`

`

`US. Patent
`
`Jun. 10, 1997
`Cn)
`
`Sheet 5 of 18
`Avo
`
`5,638,498
`
`
`
`74
`
`
`
`NO
`
`75
`
` IS AN
`SELECT A BAND, "A",
`72
`HAVING DISPLAYLIST
`
`
`
`UNCOMPRESSED
`
`
`ENTRIES
`
`BAND BUFFER
`
`AVAILABLE?
`
`S BAND A DATA!
`
`
`
`
`COMPRESSED
`
`
`STATE?
`DECOMPRESS
`BAND DATA INTO
`UNCOMPRESSED
`BAND BUFFER
`
`NO
`
`
`
`RASTERIZE DISPLAY LIST
`ENTRIES OF BAND A
`INTO UNCOMPRESSED
`BAND BUFFER
`
`78
`
`ATTEMPT TO
`COMPRESS
`BAND A DATA
`
`80
`
`82
`
`
`
`77
`SET A= THE BANDID
`OF BAND IN
`UNCOMPRESSED
`
`BAND BUFFER
`
`
`
`COMPRESSED\_NO
`DATA FITS?
`
`YES
`
`NO
`
` 84
`
`
`
`
`
`
`
`ALL DISPLAY
`LISTS WITH
`ENTRIES
`PROCESSED?
`
`86
`
`YES
`AT END OF
`PAGE?
`
`YES
`
`NO
`
`88
`
`FIGURE 4B
`
`Page 6
`
`Page 6
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`ON
`
`C#
`
`Sheet 6 of 18
`|
`5,638,498
`Figure 4c
`
` 90
`
`
`
`HIGHER LEVEL
`OF COMPRESSION
`
`
`
`AVAILABLE?
`
`NO
`
`YES
`
`ADVANCE TO NEXT
`HIGHER COMPRESSION
`
` LEVEL
`
`94
`
`92
`
`FAILURE
`
`93
`
`
`
`ANY
`
`
`COMPRESSED BANDS
`
`
`NOT AT CURRENT
`COMPRESSION
`
`LEVEL ?
`YES
`
`
`
`SELECT A BANDBATA
`LOWER COMPRESSION
`
`LEVEL
`
`98
`
`DECOMPRESS BAND B
`INTO UNCOMPRESSED
`BAND BUFFER
`
`100
`
`102
`
`106
`
`RECOMPRESS
`BAND B AT
`PREVIOUS
`
`LOWER
`COMPRESSION
`LEVEL
`
`ATTEMPT TO
`COMPRESS BAND B
`DATA AT CURRENT
`COMPRESSION LEVEL
`
`NO <Ompressepy
`BAND B FITS?
`
`194
`
`YES 108
`
`YES
`POLICY TOPX,
`
`
`RECOMPRESS
`
`ALL BANDS?
`
`Page 7
`
`Page 7
`
`

`

`US. Patent
`
`Jun. 10, 1997
`
`Sheet 7 of 18
`
`5,638,498
`
`cetAO Or YON AE SRR ODO AA A A
`
`Page 8
`
`Page 8
`
`

`

`U.S. Patent
`
`Jun. 10, 1997
`
`Sheet 8 of 18
`
`aayOseSixo]
`
`APAANDIA
`
`5,638,498
`
`Page 9
`
`Page 9
`
`

`

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

`

`US.
`
`Patent
`
`Jun. 10, 1997
`
`Sheet 10 of 18
`
`5,638,498
`
`66
`
`Ne
`
`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?
`
`
`
`
`
`FORCE OBJECT
`COMBINATIONS TO
`FREE STORAGE
`
`
`
`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
`
`
`
`REPLACE ANY BBOX
`COORDINATES OF STORED
`
`
`OBJECT WITH CORRESPONDING
`
`
`BBOX COORDINATES OF NEW
`
`OBJECT IF CONDITIONS MET
`
`
`
`
`152
`
`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
`FROM ONE OF THE TWO OBJECTS
`
`REPLACE THE TWO SELECTED
`OBJECTS WITH A NEW COMBINED
`OBJECT HAVING THE SAME TYPE
`AND EACH BBOX COORDINATE
`
`160
`
`162
`
`168
`YES
`164
`
`
`DESIRED
`MORE
`NUMBER OF
`
`COMBINATIONS
`
`
`POSSIBLE?
`COMBINATIONS
`
`
`
`DONE?
`
`
`NO
`
`166
`
`Page 12
`
`Page 12
`
`

`

`USS. Patent
`
`Jun. 10, 1997
`Gay
`
`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
`NO
`
`
`i < NUMBER OF
`OBJECTS IN
`BAND?
`
`188
`
`
`
`
`
`
`
`
`
`FOR THE SET OF REGIONS
`COVERING OBJECTI(),
`ADD THE TYPE OF
`OBJECT(i) TO EACH
`REGION AND SET EACH
`REGION'S MARKED FLAG
`TO "TRUE"
`
`194
`
`Figure 8
`
`2
`
`182
`
`184
`
`ASSIGN THE BEST
`COMPRESSION
`ALGORITHM TO EACH
`REGION BASED ON THE
`TYPE OF EACH REGION
`
`AND OTHER FACTORS
`CRITERIA
`
`
`
`
`196
`
`COMBINE ANY ELIGIBLE
`REGIONS BASED ON
`
`198
`
`200
`
`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 of 18
`
`5,638,498
`
`212
`202 ~~
`203. ALGORITHMTABLE904
`
`201 <7ALG ENTRY 1 Caw [PARAMETERS3]
`ALG ENTRY 2 (DCT-BASED)
`[PARAMETERS2]
`ALG ENTRY 3 (LZW)
`[PARAMETERSS]
`ALG ENTRY 4 (DCT-BASED)
`[PARAMETERS4]
`ALG ENTRY 5 (LZW AND DPCM)
`[PARAMETERSS]
`ALG ENTRY 6 (LZW AND DPCM)
`[PARAMETERS6]
`ALG ENTRY 7 (PDR)
`[PARAMETERS7]
`
`Figure Sa
`
`ys
`INDEXING TABLE
`,208
`209
`TEXT IMAGE GRAPHIC
`(NO ALGORITHM ASSIGNED)
`NO
`NO
`NO
`YES
`NO
`NOAa = 0, CR = 2.0, ALG ENTRY1)
`213a
`Q=2,CR=5.0, ALG ENTRY 3)
`(
`213b ~~"(Q = 4, CR = 10.0, ALG ENTRY5
` YES/
`(Q=0,CR=2.0, ALG ENTRY1)
`NO
`NO
`
`213c° (Q=0,CR=3.0, ALG ENTRY 3)|997
`(Q =4, CR = 8.0, ALG ENTRY6)
`NO7 = 0, CR = 4.0, ALG ENTRY2)
`213 (GQ = 1, CR = 7.0, ALG ENTRY 4)
`“——»(Q = 3, CR = 9.0, ALG ENTRY 5)
`YES
`(Q=0,CR=2.0, ALG ENTRY1)
`(Q =3, CR =5.0, ALG ENTRY 5)
`(Q=5, CR = 6.0, ALG ENTRY6)
`(Q=0,CR=2.0, ALG ENTRY6)
`(Q = 2, CR = 2.5, ALG ENTRY2)
`(Q =3, CR =5.0, ALG ENTRY7)
`,(Q=0,CR=2.0, ALG ENTRY6)
`(Q=1,CR=3.0, ALG ENTRY 5)
`(Q = 4, CR = 4.5, ALG ENTRY2)
`(Q=0,CR=1.5,ALGENTRY5)
`(Q = 2, CR = 2.0, ALG ENTRY4)
`
`211
`
`+207a
`
`)
`
`p-207b
`
`NO
`
`YES
`
`YES
`
`NO
`
`NO
`
`YES
`
`YES
`
`,
`
`YES
`
`YES
`
`NO
`213
`
`YES
`
`YES
`
`YES
`
`Figure 8b
`
`Page 14
`
`Page 14
`
`

`

`USS. Patent
`
`Jun. 10, 1997
`
`Sheet 14 of 18
`
`5,638,498
`
`CREATE ARRAYOFALL X
`COORDINATES THAT DESCRIBE
`LEFT OR RIGHT EDGES OF
`BOUNDING BOXESIN BAND
`
`SORT ARRAY OF X COORDINATES
`IN ORDER OF INCREASING X AND
`REMOVE DUPLICATE VALUES;
`nX = NUMBER OF VALUESIN
`RESULTING ARRAY
`
`
`
`
`
`
`CREATE ARRAY OFALL Y
`COORDINATES THAT DESCRIBE
`
`TOP OR BOTTOM EDGESOF
`
`BOUNDING BOXESIN BAND
`
`
`
`SORT ARRAY OF Y COORDINATES
`IN ORDER OF INCREASING Y AND
`REMOVE DUPLICATE VALUES;
`nY = NUMBEROF VALUESIN
`RESULTING ARRAY
`
`DIVIDE BANDINTO (nxX-1)(nY-1)
`RECTANGULAR REGIONS
`
`wv 182
`
`212
`
`Figure 9
`
`214
`
`216
`
`218
`
`220
`
`eay™
`
`221 os REGION DATA STRUCTURE
`222 ~.MASTER FLAG
`224
`SLAVE FLAG—~
`‘226 ~~MARKED FLAG
`X INDEX 228
`230 —Y INDEX
`OBJECT TYPES 232
`
`Figure 9a
`
`Page 15
`
`Page 15
`
`

`

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

`

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

`

`U.S. Patent
`
`Jun. 10, 1997
`
`Sheet 17 of 18
`
`5,638,498
`
`290
`
`
`
`LOAD A NUMBER OF REGIONS
`DESCRIPTORS INTO
`
`DECOMPRESSION BUFFER
`
`Figure 13
`292 Wz 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 ATA
`START OF REGION OR
`
`
`
`REGION?
`
`
`END OF SCANLINE
`
`
`
`302
` POINTER AT
`
`
`YES
`
`
`GET DECOMPRESSION
`STATE FOR REGION
`
`START OF
`REGION?
`
`
`
`DECOMPRESS AND
`OUTPUT REGION DATA
`UNTIL SCAN LINE
`POINTER POINTS TO
`END OF REGION
`
`306
`
`NO
`
`POINTER AT END
`OF SCANLINE?
`
`YES
`
`312
`
`COMPLETED
`
`LOAD ADDITIONAL
`
`—_——14
`ANY REGIONS?——«’DESCRIPTORS
`NO
`POINTER AT
`YES
`316
`END OF PAGE?
`
`Page 18
`
`Page 18
`
`

`

`U.S. Patent
`
`Sheet 18 of 18
`
`5,638,498
`
`Jun. 10, 1997
`
`veyainbiiy,
`
`vee
`
`Page 19
`
`Page 19
`
`

`

`5,638,498
`
`1
`METHOD AND APPARATUS FOR
`REDUCING STORAGE REQUIREMENTS
`FOR DISPLAY DATA
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation-in-part of co-pending
`parentpatent 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-
`tated 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.
`Manyoutput 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 mapsare 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 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
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`2
`typical displayed page requires about 3.8x10° bytes of
`memory. Whenprinting a page of color pixels, for example,
`having 8 bits per color per pixel, the memory requirement
`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
`requirementsfor 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 thelike, 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 bitmapis 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 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.
`
`SUMMARYOF 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
`imagedata, 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 backgrounddata in the bandare rasterized and divided
`into non-intersecting bitmap regions which cover the band.
`The regions are designated aseither empty regions covering
`no objects, or non-empty regions covering objects. The
`bitmap regions can be combinedinto 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 backgrounddata to the output device whenthe scanline
`does not intersect the compressed regions.
`Tn 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.
`Thebandis partitioned into non-intersecting bitmap regions,
`where each bitmap region hasat 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 combinedinto larger regions. The non-empty
`regions of the uncompressed band are then compressed and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`30
`
`55
`
`60
`
`65
`
`4
`stored in a compressed band buffer of the digital read/write
`memory. This step includes checking if the compressed
`regionsfit in the compressed band buffer 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 bandof 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 datais
`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 tradeoff 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
`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. 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.4bis 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.4dis 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. de 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
`Tequirements when storing data of different types for a
`variety of purposes.
`A number ofterms 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. Takencollectively, 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,
`tefers to the arrangementof 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 requirementsin 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
`
`30
`
`35
`
`40
`
`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.).
`Tn 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
`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
`bitmap to a memory cache or other storage area that is
`accessible for display or store the bitmap for later use.
`The process of the present invention, as described below,
`provides a technique for manipulating bitmaps derived from
`objects so that les