llllllllllllll|l|lll|||||l|llllllllllllllllllllIlllllllllllllllllllllllllll
`USOOSSO4842A
`
`[191
`United States Patent
`
`Gentile
`
`[11] Patent Number:
`
`5,504,842
`
`[45] Date of Patent:
`
`Apr. 2, 1996
`
`[54] METHOD AND APPARATUS FOR
`PROCESSING DATA FOR A
`VISUAL-OUTPUT DEVICE WITH REDUCED
`BUFFER MEMORY REQUIREMENTS
`
`[75]
`
`Inventor; Ronald S. Gentile, Atherton’ Calij
`
`[73] Ass1gnee: Adobe Systems, Inc., Mountain View,
`Cahf.
`
`[21] Appl. No.: 467,792
`
`[22] Filed:
`
`Jun. 6, 1995
`
`0475601A3
`
`3/1992 European Pat. on. .
`
`OTHER PUBLICATIONS
`
`Fred Mintzer, “Integrating Image Into Computers for Pub—
`lishing” IEEE/IEICE Global Telecommunications Conf.
`1987, Nov. 15, 1987, Japan pp. 740—743, XPl2797.
`Okada, et 31., “Adaptive Coding for Text and Dithered
`Continuous—Tone Images”, Fujitsu Scientific & Technical
`Journal, vol. 23, No. 2, 1987, Japan, pp. 101—110.
`
`Primary Examiner—Raymond J. Bayerl
`Assistant Examiner—Steven P. Sax
`
`Related US. Application Data
`
`Attomey, Agent, or Firm—Edward B. Anderson
`
`[62] Division of Ser. No. 974,204, Nov. 10, 1992.
`[51]
`Int. le’ ..................................................... G06K 15/00
`[52] US. Cl. ............................................. 395/114; 395/115
`[58] Field of Search ..................................... 395/115, 114,
`395/110, 101, 116; 353/296, 298; 400/121
`_
`References Clted
`U.S. PATENT DOCUMENTS
`
`[56]
`
`5,034,804
`........................... 358/296
`7/1991 Sasaki et a1.
`5,150,454
`............................ 395/114
`9/1992 Wood et a1.
`gfléggggg
`‘53:: 133“” et al'
`'
`400/121
`5,208,676
`5,1993 Inui":IIII
`358/296
`
`5:241:397
`8/1993 Yamada ................................... 358/296
`5,270,728 12/1993 Lund et a1.
`_
`5,272,768 12/1993 Bauman et al.
`........................ 395/110
`
`5,276,780
`1/1994
`395/116
`3/1994 Ota .......................................... 395/115
`5,295,233
`53999292
`3/1994 Kadowaki 6t 31-
`-
`5,347,368
`9/1994 Mochizuld .............................. 358/296
`2,325,412:
`igflggi 15:23:21: a1.
`'
`395,115
`5:374:943 12,1994 Lehmann et a1"""""""""""
`5,377,312 12/1994 Kobayashi.
`FOREIGN PATENT DOCUMENTS
`
`ABSTRACT
`[57]
`A two-dimensional page representation to be printed has a
`combination of text, graphic and image representation types.
`A data memory stores data representative of the page
`representation. A program memory stores program instruc-
`tions including a plurality of different algorithms for com-
`pressing data associated with corresponding different repre-
`sentation types and their combinations. A processor is
`coupled to the data and program memories for (a) identify—
`ing separate data for each of a plurality of regions containing
`collectively the page representation, With the data for each
`region corresponding to the portion of the page representa-
`tron contained in that region; (b) deterrmnmg the types of
`representations and boundafies 0f eaCh type 0f rtSPERM"
`tion and the combinations of types contained in each region;
`(C) rasterizing and compressing the data associated with the
`determined types of representations for each region with
`algorithms based on selected compression factors; ((1) stor—
`ing sequentially the compressed data for each region; and (e)
`when needed for printing, sequentially for each region,
`reading the corresponding stored data, decompressing the
`read data, and trahsmittmg the decompressed data to the
`Prlm 019““ for Pnnung-
`
`0320014A2
`
`6/1989 European Pat. Off.
`
`.
`
`23 Claims, 8 Drawing Sheets
`
`75
`
`
`
`
`
`
`
`
`_. 3,1. M if“ e
`WEREE DISPLAY \
`
`1725
`
`us! FDR REGION 1
`"2
`REVISE CDMERBSION
`SCHEME BASED ON
`E
`:m
`
`
`CURRENT COMPRESSION
`compass Mullen DATAwrm
`FACfORS AND
`COMPRESSION SCHEME BASED oN
`
`cunRENr COMPRBSION FAUURS
`REVISE B‘HMATE
`
`
`
`
`
`
`
`
`REVISE COMPRESSION SCHEME BASED ON CURRENT
`CDMPRESIQN FACIORSAND REVISE EsnMA‘rE
`
`
`
`
`
`
`Is
`FOR REGION 11
`coMPnasED. SHOULD rr
`
`
`DECQMFRBS DATA FOR REGION 11
`RECOMPRESS WITH COMPRESSION SCHEME
`
`
`BASED ON CURRENTCOMPRESSION FACIORS
`
`
`REVISE COMPRESSION SCHEME
`i
`l BASED on CURRENT COMPRESSION
`. mack: mo REVISE BTIMA‘IE
` Commvault Ex. 1031
`US Patent No. 9,054,728
`
`Commvault v. Realtime
`
`Page 1
`
`Page 1
`
`Commvault Ex. 1031
`Commvault v. Realtime
`US Patent No. 9,054,728
`
`

`

`US. Patent
`
`Apr. 2, 1996
`
`Sheet 1 of 8
`
`5,504,842
`
`
`VISUAL
`INFORMATION
`
`SOURCE
`
`
`
`
`
`VISUAL-
`OUTPUT
`
`
`DEVICE
`
`
`VISUAL OUTPUT DEVICE
`
`FOR EACH REGION: READ COMPRESSED
`DATA, DECOMPRESS IT, AND TRANSMIT
`THE DECOMPRESSED DATA TO THE
`
`Page 2
`
`Page 2
`
`

`

`US. Patent
`
`Apr. 2, 1996
`
`Sheet 2 of 8
`
`5,504,842
`
`misoui‘sfi in Won W'ColcfS‘paoeme CIE—basemor s’pfies afi—
`mathematioally related to the CIE 1931 (XYZ)-spaoe, which is based on a model of
`human color perception.
`To render CIE-based colors on a device. a PoetScn'pt
`interpreteLmust convert frqmthe spnifled ClEbaseLoolor sum to they evia'e.
`native color space, taking into account the known properties of the device. The goal
`of this process is to produce output that accurately reproducesthe requested CIE-
`based color values as perceived by a human observer.CIE-based color specifimtion
`and-rendering are-supported-only by-tevel Zimplementafionsfi‘he conversion from
`CIE-based oolortodevioe isoomplem thetheory on which itis based is beyond the
`aoope of this manual (see the bibliography . The algorithm has many parameters.
`msludinmomiqnai. full line dimembn
`or loom: table.
`
`92.7{92:9
`
`-4745- —
`
`9‘91
`v 0
`9'9'9292
`W9292929,
`V
`A
`9'9929
`9'9292
`.7929
`V
`0
`
`7.7..V29.9292
`W992929
`9'99292
`V.'.V29292
`'79
`
`Page 3
`
`Page 3
`
`

`

`US. Patent
`
`Apr. 2, 1996
`
`Sheet 3 of 8
`
`5,504,842
`
`58
`
`K
`
`@3
`SELECI' FIRST OBJECT-
`
`DESCRIPTION COMMAND
`
`
`
`-E_-
`
`H4
`
`SELECT NEXT
`COMMAND
`
`I I2
`
`momma
`
`COMMAND
`
`DOES
`
`OBJECT DESCRIBED
`
`BY THE COMMAND INTERSECI'
`
`REGION I
`7
`
`
`
`
`
`
`DETERMINE PRIMITIVE ELEMENTS, BOUNDING
`BOX (BBOX), AND REPRESENTATION
`TYPE FOR COMMAND FOR REGION 1'
`
`
`
`UPDATE THE DISPLAY LIST, AND BBOX
`OF THE SAME TYPE FOR REGION I
`
`I 18
`
`II6
`
`\
`
`R
`
`
`DO
`EGION i BBOXES
`
`INTERSECT
`
`
`
`9
`
`YES
`
`DIVIDED REGIONAL BBOXES INTO
`NON-INTERSECI'ING BBOXES
`
`Fig. 4
`
`Page 4
`
`Page 4
`
`

`

`US. Patent
`
`Apr. 2, 1996
`
`Sheet 4 of 8
`
`5,504,842
`
`
`
`
`
`
`, ‘I.'i'.'fi.l -'
`
`
`
`'I:"I:"m I
`
`
`
`
`
`
`RI
`
`134
`
`[/136
`a —____.._.__
`
`
`
`
`
`
`Y
`
`
`*L““““\l_"In”, ’44
`FgE
`
`‘su~~
`g
`‘~
`
`‘——
`-
`-
`_K“\
`\W_WIIIln"
`L‘l“=\‘\““m—”WWII“
`.
`
`III"—E umwn‘\\V I'.‘— .3714"n”lA I
`
`
`
`0
`
`_._._._*..___..*.____
`
`___.__*_._.__
`
`Page 5
`
`Page 5
`
`

`

`US. Patent
`
`Apr. 2, 1996
`
`Sheet 5 of 8
`
`5,504,842
`
`COORDINATES AND
`ORDER THE . Y
`COORDINATES
`
`140
`
` LIST x AND Y
`
`
`
` SELECT NEXT TWO
`
`LOWEST Y COORDINATES
`
`‘142
`AND ORDER
`
`
`THE X COORDINATES
`
`
`
` SELECT NEXT TWO
`
`
`LOWEST X COORDINATES
`FOR TEST BOX
`
`
`
`
`IS
`TEST BOX IN A
`
`BBOX
`
`
`7
`
`
`
`
` IDENTIFY TYPEISI OF
`
`
`
`REPRESENTATION AND
`STORE COORDINATES OF TEST
`BOX AND REPRESENTATION
`TYPEISI
`
`
`
`
`
`Page 6
`
`Page 6
`
`

`

`US. Patent
`
`Apr. 2, 1996
`
`Sheet 6 of 8
`
`5,504,842
`
`%
`
` SELECT COMPRESSION SCHEME
`
`BASED ON COMPRESSION
`
`
`FACTORS AND FORM AN ESTIMATE
`
`
`
`160
`
`2
`
`I135
`
`I6I
`
`RASTERIZE DISPLAY
`LIST FOR REGION i
`
`
`
`
`
`REVISE COMPRESSION
`SCHEME BASED ON
`
`COMPRESS RASTERIZED DATA WITH
`CURRENT COMPRESSION
`
`FACTORS AND
`COMPRESSION SCHEME BASED ON
`CURRENT COMPRESSION FACTORS
`REVISE ESTIMATE
`
`
`
`
`UPDATE
`
`
`
`UPD/‘I TE
`PROGRESS
`OR REPROCESS
`ADEQUATE
`
`? I
`
`
`
`
`REPROCESS
`
`
`
`
`
`REVISE COMPRESSION SCHEME BASED ON CURRENT
`COMPRESSION FACTORS AND REVISE ESTIMATE
`
`I
`k=k+I
`
`
`
`
`
`I78
`
`kSR
`YES
`
`A/O
`
`
`
`180
`
`
`FOR REGION k IS
`
`COMPRESSED, SHOULD IT
`
`BE REPROCESSED
`
`
`
`
`
`DECOMPRESS DATA FOR REGION k
`RECOMPRESS WITH COMPRESSION SCHEME
`
`
`
`BASED ON CURRENT COMPRESSION FACTORS
`
`FACTORS AND REVISE ESTIMATE
`
`REVISE COMPRESSION SCHEME
`BASED ON CURRENT COMPRESSION
`
`
`
` REPROCESS
`
`Page 7
`
`Page 7
`
`

`

`US. Patent
`
`Apr. 2, 1996
`
`Sheet 7 of 8
`
`5,504,842
`
`READ COMPRESSED DATA FOR
`REGION i FROM COMPRESSED
`MEMORY; DECOMPRESS THE
`DATA; AND WRITE IT IN
`UNCOMPRESSED MEMORY
`
`RASTER OUTPUT DEVICE
`
`READ DATA FROM
`UNCOMPRESSED MEMORY
`AND TRANSMIT IT TO THE
`
`I92
`
`Page 8
`
`Page 8
`
`

`

`US. Patent
`
`Apr. 2, 1996
`
`Sheet 8 of 8
`
`5,504,842
`
`VISUAL
`INFORMATION
`
`I2
`
`SOURCE
`
`DESCRIPT/I/E
`
`IO
`
`I
`
`COM/WINDS
`
`I6'
`
`16
`
`I OUTPUT-DATA
`I
`
`I
`
`COMMAND
`
`I54
`
`I
`
`I96
`
`EASTER
`
`20
`
`
`
`'66
`
`.21". ___: ___ :_—__‘_____4 TE“: :_‘_'_‘|
`I; 17.17.::: ___ r::.
`I
`I GENERATOR
`RECEIVER
`156
`I58
`1
`I
`I
`:
`WORKING MEMORY - ./
`1
`I
`I
`DISPIAY
`REGIONAL BBOXES
`I
`'
`DISTILLING
`i
`I
`TYPES
`LISTS
`NON—INTERS. BBOXES I PROCESS
`;
`I
`I
`1
`BY REGION
`I
`I
`I
`I
`I
`I
`I
`I65
`I
`;
`RASTER GENERATOR
`I
`I
`.L _______
`I
`I
`I
`I
`|
`OUTPUT
`:
`UNCOMPRESSED
`COMPRESSION :
`I
`
`. CONTROLLER I
`MEMORY
`164
`UNIT
`I
`I
`BY REG'ON
`:
`I
`CONSULTANT :
`I
`
`158
`I
`i
`I
`I
`I
`'
`I
`COMPRESSED
`:
`I
`1
`I
`MEMORY
`I
`I
`I
`.
`BY REGION
`:
`I
`:
`I
`I______ ___-.I _____________. _________________________I
`.
`'
`I
`'
`OUTPUT
`I
`I
`.
`I
`1.99'YT'1‘3ELF'3:
`DAT/I
`I
`\
`2
`WM“
`:16. E202
`:
`OUTPUT
`'L ______I___________ K303 _ZEO
`DEVICE
`______ i ______
`I
`I
`,
`I
`INPUT
`p.208
`0TH; I
`I
`I
`:
`CONTROLLER
`.
`I
`212
`I
`I
`______ 1- ______ I
`|
`I... .. - :L _________ I
`I
`I
`I— _____ t ______ l
`I
`I
`:
`2] O COMPRESSED L- _ _ ,I DECOMPRESSION:
`I
`2I 6
`I
`I
`:
`MEMORY
`.
`:
`UNIT
`.
`I
`I
`I
`:
`2I4 ————————————— I
`——————— 1' ----- I
`I
`l
`r"“"-“*:“"I
`'I\ ------------- I
`I
`I
`OUTPUT
`\I' UNCOMPRESSED ; __________ .I
`'
`I
`L
`I
`.CONTROLLER. ““““ 1
`MEMORY
`I
`:
`L__________.___‘:_'_"_”_"_'_' _______________ I
`
`l
`
`I
`.
`
`'
`
`I
`
`-
`
`I 8
`
`I
`
`|
`
`I-2o4
`
`I
`
`Fig.
`
`1 O
`
`Page 9
`
`Page 9
`
`

`

`5,504,842
`
`1
`METHOD AND APPARATUS FOR
`PROCESSING DATA FOR A
`VISUAL-OUTPUT DEVICE WITH REDUCED
`BUFFER lVIEMORY REQUIREMENTS
`
`This is a division of copending application Ser. No.
`07/974,204, filed on Nov. 10, 1992.
`BACKGROUND OF THE INVENTION
`
`1.Field of the Invention
`
`This invention relates to a method and apparatus for
`processing data representative of a visual representation,
`typically including a combination of text, graphics, and
`images, that is to be output to a visual-output device, such
`as a screen display or print device. More particularly it
`relates to such a method and apparatus in which a data
`memory,
`referred to herein functionally as a “bufier
`memory”, has reduced capacity requirements resulting from
`the selective compression of data.
`2. Related Art
`
`The preferred embodiment of, and preferred method of
`practicing the present invention is directed to printers that
`form a raster image typically connected indirectly over a
`network, or directly to a computer for printing documents
`created on the computer. The invention is realizable for other
`forms of output devices as well, such as a video display
`generated on a CRT monitor or an LCD. Thus, the device
`creating the actual visual representation is referred to as a
`“visual—output device”. The visual area within which the
`visual representation exists is referred to as a “page”,
`regardless of its actual form. The complete visual represen-
`tation is referred to as a “page representation”. A separately
`defined part of a page representation is referred to as an
`“object”.
`One of the significant cost elements in a conventional
`printer is a buffer memory, also referred to as a frame buffer,
`for storing raster data defining the page representation.
`Conventional printer configurations employ buffer memo-
`ries that are capable of storing all of the raster data required
`to define each pixel on a page. An extensive amount of
`memory capacity is therefore typically required. A black-
`and—white representation for a 8.5 inchxll inch sheet of
`paper at a pixel density of 300 dpi (dots or pixels per inch)
`requires in excess of 1 MByte (1 nrillion 8—bit bytes)of
`memory. Higher spatial and tonal resolutions, color priming
`and larger paper sizes require even more memory. A con-
`tinuous tone, four-color representation at a pixel density of
`600 dpi for the same sized page requires about 135 MBytes
`of memory. Since the printer costs rise with memory size, it
`is desirable to provide printers with reduced memory
`requirements.
`A memory device known by the proprietary name of
`“Memory Miser” produced by Advanced Micro Devices of
`Santa Clara, Calif, stores data in a resident memory by
`applying a compression algorithm to all of the data input.
`When required for output it is decompressed based on the
`reverse of the compression algorithm and output. If used in
`a printer, such a device would reduce the amount of memory
`required. However, the memory would need to be at least
`large enough to store the most complex page representation
`in order to be able to process any page that is input. This
`printer would have little flexibility in processing the variety
`of page representations possible with present day printers.
`SUMMARY OF THE INVENTION
`
`The present invention provides a method for using, and an
`apparatus permitting a reduced—size memory. Further,
`it
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`provides a method and apparatus that can accommodate a
`variety of page representation characteristics and data pro-
`cessing objectives.
`The invention is directed generally to an apparatus and a
`method for processing data representative of a page repre—
`sentation for output to a visual-output device, such as the
`electro-mechanical printing apparatus (also referred to as the
`print device), of a printer. The method begins with the step
`of receiving data that defines a page representation. A
`plurality of regions of the page are selected, which regions
`contain at least a portion of the page representation. In one
`aspect of the invention, separate data for each such region is
`identified corresponding to the portion of the page repre-
`sentation contained in that region. Data identified for at least
`one of the regions is then compressed, using at least one
`compression algorithm and stored. For producing the page
`representation after storing the compressed data, the com—
`pressed data is decompressed and transmitted to the visual-
`output device.
`In another aspect of the invention, at least one compres—
`sion factor and a plurality of compression algorithms are
`provided. The compression factor has a determinable value
`that is related to a reference value. A compression algorithm
`is then chosen based on the relationship of the determined
`value of the compression factor to the reference value.
`More specifically, the preferred embodiment of the inven-
`tion is an apparatus for printing a two-dimensional page
`representation composed potentially of text, graphic and
`image objects (object representations) individually, and in
`combination. A print device is responsive to raster data for
`printing a page containing the page representation. An input
`device, such as a personal computer or workstation, is used
`for inputting data defining the page representation. A pro-
`gram memory stores program instructions including a plu-
`rality of different algorithms for compressing the data asso-
`ciated with corresponding different representation types and
`their combinations. The selection of compression algorithms
`is based in part on balancing the compression factors of
`compression ratio, computational complexity, and visual
`quality. A processor is coupled to the input device, print
`device, program memory and a data memory for executing
`the stored program instructions.
`The processor is responsive to the data input in the form
`of descriptive cormnands for identifying data for each of a
`plurality of ordered regions or bands containing collectively
`at least a portion, and preferably, all of the page represen~
`tation. The data for each region corresponds to the portion of
`the page representation contained in that region. Some
`regions may not contain data. The descriptive commands,
`which are not necessarily band limited, are converted into
`lists of primitive elements selected from a set of primitive
`elements. Each primitive element represents at least a por—
`tion of an object representation. These lists are referred to as
`display lists. There is preferably a display list for each
`region, although the display list could be for the entire page,
`or for other defined regions.
`The types (and combinations of types) of representations
`and boundaries (referred to as bounding boxes) of each type
`contained in each region are determined. The display list
`data associated with the determined types of representations
`for each region is rasterized into an uncompressed band and
`then compressed using algorithms corresponding to the
`analysis of certain compression factors. Rasterizing refers
`generally to the conversion of high-level descriptive com-
`mands into rasters. Data associated with primitive elements
`is often already in raster form. However, for purposes of this
`
`Page 10
`
`Page 10
`
`

`

`3
`
`4
`
`5,504,842
`
`discussion, rasterizing refers to the conversion of display list
`data for a region into raster form without regard for whether
`or not the data associated with the corresponding primitive
`elements is already in raster form.
`The compression factors may, and preferably do include
`compression goals specifying target visual quality, compres-
`sion ratio, and computational complexity. Compression ratio
`refers generally to the bytes of memory required to hold the
`compressed data relative to the bytes of memory required to
`hold the same data uncompressed. Additionally considered
`are such factors as the type of representation, content of
`individual bounding boxes, overall content of the page
`representation, estimated versus actual compression being
`achieved, and the number of passes or attempts made at
`compressing the data. Other factors may also be used, and
`some of these factors may not be used in all situations. For
`example, the factors could be prioritized so that some are
`given more weight than others. As an extension of this, in
`.certain situations some factors could be given no weight at
`all relative to other factors.
`
`Some of these factors inherently have values that are
`readily determined. Others relate to characteristics or fea-
`tures the state of which is determined and a value assigned
`accordingly. For instance, the three representation types of
`text, graphics and images could be assigned arbitrary respec-
`tive identifier values 1, 2, and 3.
`
`An algorithm, generally speaking, refers to a particular
`algorithm or combination of algorithms with particular
`parameter values. Thus, a change in parameter values results
`in a change in the algorithm.
`The compressed data is stored sequentially by region. In
`the preferred embodiment, when required for printing, data
`for a region is read and decompressed. Depending on the
`system configuration, the compressed data may be transmit-
`ted to an external printer or stored pending requirement of
`the data by the print device. The data is then transmitted to
`the print device for printing. Producing data (display lists-
`)for each region and defining the regions to conform to the
`sequential output of raster data to an output device mini-
`mizes the number of times the data is decompressed, data
`added, and then recompressed. During this overall process
`“data” defining the page representation takes the form of
`descriptive commands, display lists and associated informa-
`tion, and raster data.
`
`Data representative of the page representation is thus
`compressed and held in memory until such time as it is
`required by the print device for printing, or until the content
`of a region is changed. The data for the regions are swapped
`in and out of the compressed—data memory using the
`selected compression and corresponding decompression
`algorithms,
`thereby reducing substantially the buffer
`memory requirements. This and other features and advan—
`tages of the present invention will be apparent from the
`following detailed description of the preferred embodiment
`of the invention and as illustrated in the accompanying
`drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of an apparatus made according
`to and for practicing the method of the invention.
`FIG. 2 is an illustration of a page having different types
`of two-dimensional representations.
`FIG. 3 is a flow diagram summarizing a method of
`practicing the invention.
`
`FIG. 4 is a flow diagram of step 58 of the diagram of FIG.
`
`3.
`
`FIG. 5 illustrates visually the development of non-inter-
`secting bounding boxes from bounding boxes of different
`representation types that overlap according to the method of
`the diagram of FIG. 4.
`FIG. 6 is a simplified graphic example of overlapping
`bounding boxes with identifying coordinates used in the
`method of the diagram of FIG. 4.
`FIG. 7 is a flow diagram illustrating the development of
`non—intersecting bounding boxes corresponding to step 122
`in FIG. 4.
`
`10
`
`FIG. 8 is a flow diagram of step 78 of the diagram of FIG.
`
`FIG. 9 is a flow diagram of step 80 of the diagram of FIG.
`
`15
`
`3
`
`3.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`FIG. 10 is a functional block diagram corresponding to
`the apparatus of FIG. 1.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT AND METHOD
`
`Referring initially to FIG. 1, a generalized visual—repre-
`sentation-generating system made according to the present
`invention is shown generally at 10. It includes a visual
`information source 12 connected via a communication link
`14 to an output-data generator 16. Generator 16 is connected
`to a visual-output device 18 via a communication link 20. As
`will be seen, various embodiments are realizable from this
`general structure. Output data generator 16 can be resident
`within a host unit including source 12, can be resident within
`an output unit including visual-output device 18, or can be
`functionally split between a host unit and an output unit.
`In the typical instance when data generator 16 and output
`device 18 comprise a laser or other raster printer, informa—
`tion source 12 is a conventional work station or other
`computer-based system, such as anApple Macintosh or IBM
`PC. The term print device is also used herein as an example
`of a visual-output device. In the preferred embodiment, this
`term applies to the electro-mechanical apparatus responsive
`to raster data for producing a printed page. Generator 16
`could also be incorporated in a computer or workstation,
`such as a computer—based system as has just been men—
`tioned, programmed to function as described herein, for
`controlling a raster display or printing device, as has also
`been mentioned. Further, as is discussed with reference to
`FIG. 10, a host unit could generate and output the com—
`pressed data and an output unit could receive the com—
`pressed data, decompress it and transmit it to a resident
`visual-output device.
`The preferred embodiment of the invention is thus
`directed to the printing of two-dimensional pixel represen—
`tations. The general concepts are equally applicable to three
`(or more) dimensional representations to the extent they are
`realizable in the system of FIG. 1.
`Generator 16 includes an input/output controller 22
`coupled to communication links 14 and 20. A conventional
`CPU (central processing unit) or processor 24 is coupled to
`controller 22, as well as to a read/write or random access
`memory (RAM) 26, used partially as a buffer memory, for
`storing data, and a read only memory (ROM) 28 for storing
`program instructions and fixed information, such as nonva—
`riable data and compression and decompression algorithms,
`as is discussed in further detail with reference to FIGS. 3, 5,
`and 7—10. Any of a variety of conventional CPU’s may be
`
`Page11
`
`Page 11
`
`

`

`5
`
`6
`
`1504342
`
`used, depending on the actual application. Further, other
`forms of hardware that accomplish the same functions can
`be used.
`
`FIG. 2 illustrates a page 30 having a page representation
`34 that could be defined by data input by the input device
`using a conventional page-description language, such as the
`language available from Adobe Systems
`Incorporated
`known by the name PostScript. In the printer environment,
`as a PostScript file is created on source 12 (FIG. 1), objects
`can be created in any arbitrary order or fashion on a page.
`The objects are defined by one or more descriptive com-
`mands. As used herein, then, an “object-defining comman ”
`is the command or collection of commands that define an
`object.
`Different compression schemes have been found to be
`preferable for the different representation types of text,
`graphics, and images. For instance, the human eye is often
`less sensitive to changes in images than to degradations in
`something as well defined as text. Thus, technically lossy
`compression schemes such as JPEG, when used at reduced
`levels of compression for images, can be visually lossless.
`Further, by the nature of graphics objects, some otherwise
`lossy schemes may be usable without compromising spatial
`resolution. The LZW technique has been found to work well
`on text, mnlength coding is effective for graphics and
`text/graphics combinations, and the JPEG technique is use-
`ful for images. It is therefore advantageous to identify the
`different types of objects in a page representation.
`Continuing to refer to FIG. 2, page 30 has defined
`boundaries represented by border line 32. The boundaries
`thus represent the maximum area within which page repre-
`sentation 34 is to be produced. Page representation 34
`includes the following objects on a background of a single
`color. A title or main heading 36 is formed of text in different
`colors (represented by the different tones). A subheading 38
`identifies a text representation 40; a subheading 42 identifies
`a graphics representation 44; and a subheading 46 identifies
`an image representation 48. These subheadings are text
`representations in relatively large fonts and, along with text
`representation 40, are all a single color different than the
`background color. Text representation 40 is in a reduced
`font. Graphics representation 44 has grid identifiers 50 in the
`form of alphanumeric characters (text), and a bar chart
`section 52 composed of bars of different colors. Image
`representation 48 is simply an array of pixels of varying
`colors.
`
`Page representation 34 incorporates separate examples of
`large and small text, graphics, and image representations or
`objects. In a more complex page representation various of
`the different objects could overlap. That is, they could be
`printed at least partially on a common area. The preferred
`method of the present invention is designed to take such
`overlapping areas into consideration, as is discussed in
`greater detail below.
`A generalized flow diagram chart of a process or method
`54 according to the invention is provided in FIG. 3. Pro-
`cessor 24 of FIG. 1 executes instructions to function as an
`interpreter that recognizes the PostScript descriptive com-
`mands input as page data from source 12, as is provided by
`step 56in the flow diagram of FIG. 3. In the general method
`of the invention, the page description data is divided into at
`least one, and preferably R different data regions at step 58.
`The regions can be determined in advance, as is the case
`with the preferred embodiment and therefore be determined
`arbitrarily with reference to a particular page representation.
`They could also be determined dynamically for each page
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`representation. Referring to FIG. 2, an example of a dynamic
`determination would be to divide the page into separate
`regions corresponding to title heading 36, text subheading
`38, text section 40, graphics subheading 42, each of grid
`identifiers 50, bar chart section 52, image subheading 46 and
`image section 48. In the preferred embodiment of the
`invention, however, in which raster data is produced for
`printing a page, the page area is divided into a plurality of
`fixed regions in the form of parallel bands. The bands are
`chosen and ordered to correspond to the generation of raster -
`data for output to a print device, and is therefore related to
`the resolution and scan order of the output device.
`Referring again to FIG. 2, page 30 is shown for purposes
`of illustration divided into sixteen bands 60—75. When it is
`
`time to print, data for band 60 is read out and decompressed
`first and the data progresses sequentially through the bands
`until data for the last band 75 is output. These bands each
`correspond to multiple raster “scans” of the page and
`provide for ordering the data in a way that will make the data
`readily available for printing. An actual
`letter-size page
`having a resolution of 300 dpi may be divided into about 20
`to 40 bands.
`
`As has been mentioned, the present invention provides for
`a reduction in the amount of memory required through the
`use of compression techniques, as is represented by step 78
`in FIG. 3. By compressing a rasterized version of the
`descriptive data of the page representation, according to the
`preferred embodiment, and decompressing it as needed by
`the printer or display, the amount of RAM needed may be
`drastically reduced.
`This memory reduction is achieved by storing in the
`working RAM a compressed representation of what
`is
`conventionally stored uncompressed in a frame buffer. Ras~
`ter data is created for one region at a time and stored
`uncompressed in RAM 26. This data is then compressed and
`re-stored in RAM 26 until needed. The data for all the
`regions is ultimately processed in this way until data for
`essentially all the regions is compressed and stored. In the
`preferred embodiment of the present invention, as data for
`each region is requested for output (printing), it is decom—
`pressed and output to the output device (print device), as
`represented by step 80 in FIG. 3.
`By compressing the data for the regions in the reverse
`order required for output to the output device, the compres-
`sion/decompression cycle of the last region may be avoided,
`since it can simply be rasterized and output directly. Also,
`depending on the circumstances, the decompression algo-
`rithm typically is, but may not be exactly the reverse of the
`compression algorithm. When the output (page printing)is
`completed, process 54 ends for that page.
`The following description of this process is directed to
`processing data for a single page. It will be understood that
`multiple pages may also be processed at a time using a
`similar system, so that different ones of the steps take place
`simultaneously for various regions of the same or different
`pages.
`
`Step 58 is shown in further detail by the flow diagram of
`FIG. 4. High level descriptive (such as PostScript)com—
`mands are input into data generator 16 from a source 12 as
`shown in FIG. 1. As has been described, these commands
`define, usually in no particular order, where text, graphics,
`and image objects appear. Some of the commands do not
`define a particular object. These commands may be directed
`to identifying locations on a page, what color to use, and the
`like. Text typically includes definitions of font and character
`size, as well as character identifiers and other information,
`
`Page 12
`
`Page 12
`
`

`

`7
`
`8
`
`5,504,842
`
`such as the color of the text. Graphics are defined by area
`fills and strokes of arbitrary color, and images are usually
`provided by bit or byte patterns.
`Referring again to FIG. 4, the first object—defining com-
`mand is selected at step 82. The intersection of the object
`defined by the command with each of the R regions (band-
`s)is then determined, as shown generally at 84. Iterative loop
`step 86 symbolizes the sequential determinations made for
`each region. When the first region is selected, a determina-
`tion is made at 88 as to whether the object described by the
`command intersects the region. If there is no intersection,
`the next region is selected at step 86 and the determination
`repeated for that region.
`If there is an intersection, primitive elements, collectively
`referred to as a display list, are generated for the portion of
`the object in the region at step 90. Primitive elements are
`basic object portions or “building blocks” that, when com—
`bined, form a new definition of an object. Character masks
`are used to define text. Geometric shapes, such as trapezoids
`and run arrays (bit patterns) are both graphics primitive
`elements. Because of the random color and intensity
`changes, images are defined by the actual image descrip-
`tions. In some instances, these primitive elements are stored
`in the display list indirectly via pointers. Preferably, a single
`display list
`is generated for each region. As has been
`mentioned, it would also be possible to have a single display
`list for a page with allocation of data to a region taking place
`as raster data for the region is stored prior to compressing.
`Each high level input object-defining command implicitly
`has a corresponding representation type, such as text, graph-
`ics or image. Other ways of classifying the object-defining
`commands may also be used.
`In this embodiment,
`the
`primitive element has an associated representation type
`corresponding to this implicit type. A bounding box is also
`determined for each region in which a portion of an object
`exists. A representatio