United States Patent 15
`Gentile
`
`
`(11) Patent Number:
`[45] Date of Patent:
`
`5,504,842
`Apr. 2, 1996
`
`CNCAAEATA
`
`US005504842A
`
`[54] METHOD AND APPARATUS FOR
`PROCESSING DATA FOR A
`VISUAL-OUTPUT DEVICE WITH REDUCED
`BUFFER MEMORY REQUIREMENTS
`
`[75]
`
`Inventor: Ronald S. Gentile, Atherton, Calif.
`
`[73] Assignee: Adobe Systems, Inc., Mountain View,
`Calif.
`
`[21] Appl. No.: 467,792
`[22] Filed:
`Jun.6, 1995
`
`Related U.S. Application Data
`
`[56]
`
`[62] Division of Ser. No. 974,204, Nov. 10, 1992.
`6
`[ST] Ute Cae nacaseeecccosesecenssesssnsesssees GO6K 15/00
`[52] U.S. CD,
`aeescsesseecsecceseecensonssenneenscenseess 395/114; 395/115
`(58] Field of Search oeeccsscsesssesesseessees 395/115, 114,
`395/110, 101, 116; 358/296, 298; 400/121
`.
`References Cited
`U.S. PATENT DOCUMENTS
`;
`7/1991 Sasaki et al. woesseceseseenseee 358/296
`5,034,804
`9/1992 Wood CE AL, eeeeeesseceeessesnneee 395/114
`5,150,454
`aore si1003 Shimizu et al. .
`400/121
`
`5208676
`511993 Inui“ee
`™ 358/296
`
`8/1993 Yamadavncnnnnnninneannee 358/296
`5,241,397
`5,270,728 12/1993 Lund et al.
`.
`vssscsssssesssscseeee 395/110
`5,272,768 12/1993 Bauman et al.
`
`.- 395/116
`5,276,780
`1/1994 Sugiwa .....
`3/1994 Ota on.eecsecssesssesesesseussnsesssersnense 395/115
`5,295,233
`5,299,292
`3/1994 Kadowakiet al..
`Peete 9/1994 Mochizuki
`seteeesenececssanseneseneoeeee 358/296
`aacat voioo4 pakagamsct al. .
`395/115
`5,374,943 12/1994 Lehmann eal.
`5,377,312 12/1994 Kobayashi .
`FOREIGN PATENT DOCUMENTS
`
`0475601A3
`
`3/1992 European Pat. Off. .
`
`OTHER PUBLICATIONS
`
`Fred Mintzer, “Integrating Image Into Computers for Pub-
`lishing” TEEE/TEICE Global Telecommunications Conf.
`1987, Nov. 15, 1987, Japan pp. 740-743, XP12797.
`Okada, et al., “Adaptive Coding for Text and Dithered
`Continuous—Tone Images”, Fujitsu Scientific & Technical
`Journal, vol. 23, No. 2, 1987, Japan, pp. 101-110.
`
`Primary Examiner—RaymondJ. Bayerl
`Assistant Examiner—Steven P. Sax
`Attorney, Agent, or Firm—Edward B. Anderson
`
`ABSTRACT
`[57]
`A two-dimensional page representation to be printed has a
`combinationoftext, 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
`T@8ion correspondingto the portion of the page representa-
`tion contained in that region; (b) determining the types of
`T€Ptesentations
`and boundaries of each type of representa-
`tion and the combinations of types contained in eachregion;
` (c) rasterizing and compressing the data associated with the
`determined types of representations for each region with
`algorithms based on selected compression factors; (d) stor-
`ing sequentially the compressed data for each region; and(e)
`when needed for printing, sequentially for each region,
`-Tading the corresponding stored data, decompressing the
`read data, and transmitting the decompressed data to the
`print device for printing.
`
`0320014A2
`
`6/1989 European Pat. Off..
`
`23 Claims, 8 Drawing Sheets
`
`
`SELECT COMPRESSION SCHEME
`FACTORS AND FORMAN ESTIMATE
`
`
`jet
`NN
`(3)
`I
`Ao
`a te
`
`
`
`RASTERIZE DISPLAY
`
`V2
`[162
`UST FOR REGION } 167
`
`REVISE COMPRESSION
`
`‘SCHEME BASED ON
`‘CURRENT COMPRESSION:
`COMPRESS RASTERIZED DATAWITH
`
`FACTORS
`COMPRESSION SCHEME BASED ON
`CURRENT COMPRESSION FACTORS
`REVISE ESTIMATE
`
`
`
`
`
`
`
` DECOMPRESS DATA FOR REGION
`y,
`
`
` | BASED©ONCURRENTNTCOMPRESSION
`o
`REVISE COMPRESSION SCHEME
` Commvault Ex. 1031
`US Patent No. 9,054,728
`
`REVISE COMPRESSION SCHEME BASED ON CURRENT
`COMPRESSION FACTORSAND REVISE ESTIMATE
`
`
`
`
`
`
`RECOMPRESS WITH
`SCHEME
`RESSION
`BASE
`‘ON CURRENTCOMPRESSION FACTORS
`Ai
`+5
`‘PROGRESS
`DEQUAT!
`
`1
`
`Commvault v. Realtime
`
`Page1
`
`Page 1
`
`Commvault Ex. 1031
`Commvault v. Realtime
`US Patent No. 9,054,728
`
`

`

`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 1 of 8
`
`5,504,842
`
`10 -—~,
`
`we
`OUTPUT-DATA GENERATOR
`
`VISUAL
`INFORMATION
`SOURCE
`
`CONTROLLERS
`VISUAL OUTPUT DEVICE
`
`FOR EACH REGION: READ COMPRESSED
`DATA, DECOMPRESSIT, AND TRANSMIT
`THE DECOMPRESSED DATA TO THE
`
`Page 2
`
`Page 2
`
`

`

`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 2 of 8
`
`5,504,842
`
`Asdiscussed in section 4.8"ColdrSpaces.”the CIEbasedcolor spaces are
`mathematically related to the CIE 1931 (XYZ)-space, which is based on a modelof
`human color perception.
`To render CIE-based colors ona device, a PostScript
`interpretermust convert fromthe specified ClE-based_color s pace to thedevice's.
`native color space, taking into account the known properties of the device. The goal
`of this process is to produce output that accurately reproduces the requested CiE-
`based color values as perceived by a human observer.ClE-based color specification
`and-rendering are-stipportec-only by-tevel 2-implementations-The conversion from
`CIE-based color to device is complex, the theory on which it is based is beyond the
`scope of this manual (see the bibliography). The algorithm has many parameters,
`inciuding_anoptional, full three dimension
`lor lookup table,
`
`7, ?
`
`xKXXKKKMWY
`MXXXKXKRY
`XY)SOK1X
`
`Page 3
`
`Page 3
`
`

`

`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 3 of 8
`
`5,504,842
`
`(START)
`SELECT FIRST OBJECT-
`
`58
`
`\
`
`DESCRIPTION COMMAND|~82
`
`114
`
`SELECT NEXT
`COMMAND
`
`112
`
`
`
`?
`
`
`
`DOES
`
`OBJECT DESCRIBED
`BY THE COMMANDINTERSECT
`REGIONi
`
`
`
`DETERMINE PRIMITIVE ELEMENTS, BOUNDING
`BOX (BBOX], AND REPRESENTATION
`TYPE FOR COMMANDFORREGION i
`
`UPDATE THE DISPLAYLIST, AND BBOX
`OF THE SAME TYPE FOR REGION i
`
`
`
`118
`
`YES
`
`Page 4
`
`
`DO
`REGION i BBOXES
`INTERSECT
`?
`
`
`
`
`YES
`
`
`
`
`DIVIDED REGIONAL BBOXES INTO
`NON-NTERSECTING BBOXES
`
`Page 4
`
`

`

`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 4 of 8
`
`5,504,842
`
`PREHTN j
`
`
`
`
`
`
`
`as
`V7} SALA oi
`
`5
`
`4————~-—————~~—
`
`134
`
`‘
`
`136
`
`(5.5)
`
`g— ——-—+-~-
`
`4
`
`3
`
`2
`
`Y
`
`eta ea
`OE IO TEA
`cj
`td
`di
`(—
`CheeEESSS
`OSS5SEEET
`
`a
`PSSSOSOPSToToT
`ta]
`RISSASSSS2PRASSer tOEo
`
`+ SRRES a
`
`(6,3)
`
`Page 5
`
`Page 5
`
`

`

`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 5 of 8
`
`5,504,842
`
`COORDINATES AND
`ORDER THE Y
`COORDINATES
`
`LOWEST Y COORDINATES
`
`‘142
`AND ORDER
`
`
`THE X COORDINATES
`
`
` LIST X AND Y
`
`
`
` SELECT NEXT TWO
`
` SELECT NEXT TWO
`
`LOWEST X COORDINATES
`FOR TEST BOX
`
`
`
`
` IDENTIFY TYPE(S) OF
`
`
`REPRESENTATION AND
`STORE COORDINATES OF TEST
`BOX AND REPRESENTATION
`TYPE(S}
`
`
`
`Page 6
`
`Page 6
`
`

`

`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 6 of 8
`
`5,504,842
`
`CART)
` wo
`
`
`
`SELECT COMPRESSION SCHEME
`BASED ON COMPRESSION
`FACTORS AND FORM AN ESTIMATE
`
`
` RASTERIZE DISPLAY
`
`LIST FOR REGION i
`
`REVISE COMPRESSION
`
`
`SCHEME BASED ON
`
`
`
`COMPRESS RASTERIZED DATA WITH
`CURRENT COMPRESSION
`
`COMPRESSION SCHEME BASED ON
`FACTORS AND
`CURRENT COMPRESSION FACTORS
`
`REVISE ESTIMATE
`
`
` PROGRESS
`? .
`
`
`
`
`
`
`
`ADEQUATE
`
`REVISE COMPRESSION SCHEME BASED ON CURRENT
`COMPRESSION FACTORS AND REVISE ESTIMATE
`
`NO
`
`
`
`
`
`DECOMPRESS DATA FOR REGION k
`
`RECOMPRESS WITH COMPRESSION SCHEME
`
`
`
`BASED ON CURRENT COMPRESSION FACTORS
`
`
`
`
`
`FOR REGION k IS
`
`COMPRESSED, SHOULD IT
`BE REPROCESSED
`
`180
`
`
`
`
`REVISE COMPRESSION SCHEME
`BASED ON CURRENT COMPRESSION
`FACTORS AND REVISE ESTIMATE
`
`
`
`176
`
`Page 7
`
`Page 7
`
`

`

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

`

`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 8 of 8
`
`5,504,842
`
`VISUAL
`INFORMATION
`
`ID
`
`10
`
`! QUTPUT-DATA
`bi
`
`COMMAND|_-154
`
`|
`1
`
`J
`SOURCE
`47]DESCRIPTIVE
`COMMANDS
`16
`16
`reTOTTIITITITITATLIIIa£- -(-TTII
`|
`| GENERATOR
`RECEIVER
`ie
`158
`|
`|
`WORKING MEMORY | v
`"|
`DISPLAY DISTILLING|;||__REGIONAL BBOXES
`
`
`
`
`I! TYPES|_USTS|NONANTERS. BBOXES | PROCESS |
`!
`BY REGION
`‘|
`!
`RASTER GENERATOR
`1
`|
`165
`14
`!
`UNCOMPRESSED
`|
`|
`COMPRESSION]
`
`MEMORY
`164
`"|
`UNIT
`BY REGION
`CONSULTANT|! !
`|
`ty
`oo
`COMPRESSED
`!
`7
`MEMORY
`|
`|
`BY REGION
`W------b----d.-...--T0Jono eee eee eee ene eee eeerm
`|
`|
`OUTPUT
`|
`.--204
`|
`RASTER
`|_-20
`he
`|
`|ONTRONER
`|
`DATA
`Ip VSUAL 1‘e
`!
`Noe Nea
`||OUTPUT LoPe2 200
`DEVICE|. ____Le Y...---
`|
`'
`|
`INPUT
`208
`our |
`|
`|
`CONTROLLER
`:
`|
`212
`|
`cts Tocrcfccn
`|
`;
`r — x meee eee ee I
`|
`rv — em me v —_—— = | = t
`|
`!
`|
`319.1 COMPRESSED | ___,: DECOMPRESSION! !
`qt. MEMORY
`;
`UNIT
`|
`316
`'
`NE
`{
`|
`TT mm Pf
`eee recei !
`i
`.
`t
`il
`helalcisieteteiatstataie
`| ponnt---4-,
`"1 UNCOMPRESSED| $
`!
`|! OUTPUT
`+
`| CONTROLLER ~~~ ~~ +
`MEMORY
`|
`:
`Loe |
`Fig. 10
`
`bo ee
`t
`
`!
`
`|_|
`OUTPUT
`'|
`1| CONTROLLER |"!
`;
`|
`\
`i
`
`196
`
`
`
`1!
`;
`
`t
`'
`
`!
`
`|
`
`Page 9
`
`Page 9
`
`

`

`5,504,842
`
`1
`METHOD AND APPARATUS FOR
`PROCESSING DATA FOR A
`VISUAL-OUTPUT DEVICE WITH REDUCED
`BUFFER MEMORY 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 “buffer
`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 inventionis 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-
`ties 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 inchx11 inch sheet of
`paperat a pixel density of 300 dpi (dots or pixels per inch)
`requires in excess of 1 MByte (1 million 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 enoughto store the most complex page representation
`in order to be able to process any page that is input. This
`printer would havelittle flexibility in processing the variety
`of page representations possible with present day printers.
`SUMMARY OF THE INVENTION
`
`The present invention provides a methodfor using, and an
`apparatus permitting a reduced-size memory. Further,
`it
`
`10
`
`20
`
`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
`aspectof the invention, separate data for each such region is
`identified corresponding to the portion of the page repre-
`sentation containedin 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
`tepresentation 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.
`Morespecifically, the preferred embodimentof 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 commandsfor 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 correspondsto 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 combinationsof 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 regionis 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-
`mandsinto rasters. Data associated with primitive elements
`is often already in raster form. However,for purposesof this
`
`Page 10
`
`Page 10
`
`

`

`5,504,842
`
`3
`discussion,rasterizing refers to the conversion ofdisplay 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. Compressionratio
`refers generally to the bytes of memory required to hold the
`compresseddatarelative 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
`someof these factors may not be used inall situations. For
`example, the factors could be prioritized so that some are
`given more weight than others. As an extension ofthis, in
`certain situations some factors could be given no weightat
`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 beassigned 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 numberof 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.
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`4
`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.
`
`FIG.8 is a flow diagram ofstep 78 ofthe diagram of FIG.
`
`FIG.9 is a flow diagram ofstep 80 of the diagram of FIG.
`
`3
`
`3
`
`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 an Apple 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 forstoring
`program instructions and fixed information, such as nonva-
`triable 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
`
`Page 11
`
`Page 11
`
`

`

`5,504,842
`
`5
`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
`knownby 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 usedherein, then, an “object-defining command”
`is the commandor 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 eyeis 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, runlength coding is effective for graphics and
`text/graphics combinations, and the JPEG techniqueis 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 pagerepre-
`sentation 34 is to be produced. Page representation 34
`includes the following objects on a background ofa single
`color. A title or main heading 36 is formedoftextin different
`colors (represented by the different tones). A subheading 38
`identifies a text representation 40; a subheading 42identifies
`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 commonarea. 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-
`mandsinput as page data from source 12, as is provided by
`step 56 in 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
`
`25
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`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 ofraster -
`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. Whenitis
`timeto 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.
`
`Ashas 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 embodimentof 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 shownin 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
`
`

`

`5,504,842
`
`7
`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-
`mandis 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. Whenthefirst 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 elementsare 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 highlevel input object-defining command implicitly
`has a corresponding representation type, such as text, graph-
`ics or image. Other waysof 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 representation type is assigned to each bounding
`box based on the associated primitive element type. In the
`preferred embodiment, the representation type is oneof the
`three preferred types of text, graphics and image.
`A bounding box is a defined area containing an object or
`object portion in the region. In an X-Y coordinate system, a
`bounding box is preferably a rectangle defined by the
`coordinates of the lowerleft and upper right corners. Other
`definitions for bounding boxes, such as trapezoids, could
`also be used. Thereis thus potentially a single bounding box
`for each representation type in each region, referred to as a
`regional bounding box, As is discussed below, as an object
`is added to a region, the regional bounding box of th