Illlllllllllll|lll|||||||||Illlllllllllllllllllllllllllll||||||l|l|llll||||
`US005504842A
`
`United States Patent
`
`[191
`
`[11] Patent Number:
`
`5,504,842
`
`Gentile
`
`[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_ Genfi]e,Athe1-ton, C3111-'_
`
`[73] Assignee:
`
`é;11(i)fI)e Systems, Inc., Mountain View,
`
`[21] Appl. No.: 467,792
`
`[22] Filed;
`
`Jun_ 6, 1995
`
`0475601A3
`
`3/1992 European Pat. Ofl‘.
`
`.
`
`OTHER PUBLICATIONS
`
`Fred Mintzer, “Integrating Image Into Computers for Pub-
`lishing” IEEE/IEICE 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, N0. 2, 1987, Japan, pp. 101-110.
`
`Primary Examiner—Raymond J. Bayerl
`Assistant Examz'rzer—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. Cl.6 ................................................... .. G06K 15/00
`
`[52] US‘ Cl‘
`" 395/114; 395/115
`[58] Field of Search ................................... .. 395/115, 114,
`395/110: 101: 116; 353/296: 2989 400/121
`
`[56]
`
`9/1992
`
`5,150,454
`
`References Cited
`U_S_ PATENT Docmt/IENTS
`Sasaki et
`...........................
`et a1.
`............................ 395/114
`Istlgmuzu et 31'
`'
`400/121
`358/296
`5/1993
`5:208:676
`8/1993 Yamada ................................... 353/295
`5,241,397
`5,270,723 12/1993 Land et at _
`5,272,768 12/1993 Bauman et al.
`........................ 395/110
`5,276,780
`1/1994
`
`3/1994 Ota ........................................ .. 395/115
`5,295,233
`5,299,292
`3/1994 Kadowaki fit 31-
`-
`5,347,368
`9/1994 Mochizuki
`............................ .. 358/296
`5’354’135 10/1994 Sakagami et a1’ '
`5,355,441
`10/1994 Kawai et al.
`........................... 395/115
`5,374,943 12/1994 Lehmann et al. .
`5,377,312 12/1994 Kobayashi.
`FOREIGN PATENT DOCUMENTS
`
`[57]
`
`ABSTRACT
`
`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 diiferent algorithms for com-
`pressing data associated with corresponding different repre-
`sentaltipint tytrlpesd and (tiheir combinations. 1? p(r(;cedssotrif)i]s
`coup e
`o
`e a a an program memories or a 1 en
`-
`separate data for gach of a
`of regions containing
`Collectively the page representation, with the data for each
`region corresponding to the portion of the page representa-
`fi°“ °°“tai¥“’d in Eh? ’°gi°’F (b)fdetem‘i“i“g the types °f
`r_ePTeS°ntat10I1s ar{
`eundanes 0 each _type_of representa-
`tion and
`combinations ofttypes contained in each region;
`(0) rastenzmg and compressmg the data associated wlth 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 decom ressing the
`read data and transmittin the decom; ressedpdata to the
`.
`3
`_
`.
`g
`P
`Pm“ deme f°r P““““g-
`
`0320014A2
`
`6/1989 European Pat. Off.
`
`.
`
`23 Claims, 8 Drawing Sheets
`
`i'ACTDflS AND rowMl BTIMATE
`--3-j——j-:—
`
`,,
`
` \ M
`Ina
`HST FDR REGIO
`ieaasazmD UN
`__;c_'v
`COMPRSS RAYTERIZED DATAWITH
`CURRENT COMPRESSION
`COMPRESSION SCHEME BASED cm
`FNTORS AND
`CURRENI COMPRBSION FACIURS
`REVISE B'l1M/\TE
`
`REVISco
`
`E CDMPREESION SCHEME BASED on CURRENT \,
`MFRESIQN FACIORSAND REVISE FSIIMATE
`
`
`
`
`
`
`ozcowxas DATA FOR REGION 11
`RECOMPRES wrn-1 COMPRESSION SCHEME
`BASED on CURRENTCOMPRESSION FACIORS
`
`
`
`I
`REVISE COMPRESSION SCHEME
`
`} war: on CURRENT COMPRESSION
`I mcroizs /wt) REVISE mime
`Oracle 1016
` Oracle 1016
`
`

`
`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 1 of 8
`
`5,504,842
`
`I6
`_______ __;:___________,
`OUTPUT-DATA GENERATOR
`
`
`
`
` VISUAL-
`
`OUTPUT
`DEVICE
`
`
`VISUAL
`INFORMATION
`SOURCE
`
`INPUT PAGE DESCRIPTION DATA
`
`S6
`
`
`
`
`
`ASSIGN DATA TO REGIONISI
`
`
`I
`
`COMPRESS AND STORE DATA
`
`
`
`FOR EACH REGION: READ COMPRESSED
`DATA, DECOMPRESS IT, AND TRANSMIT
`THE DECOMPRESSED DATA TO THE
`VISUAL OUTPUT DEVICE
`
`
`
`58
`
`78
`
`
`
`80
`
`

`
`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 2 of 8
`
`5,504,842
`
`Kiiscufifi in Eon 3?8“'ColiTS‘pace§7"the ClE‘basecTEeflor spices afi’
`mathematically related to the CIE 1931 (XYZ)-space, which is based on a model of
`human color perception.
`To render_ CIE-based colors on a device. a Poetsciipt
`ll11:.[PT'::.LmL|3f oszmtert frqm_the spesitled C1E:based_cclor 5518529 to 1be_d evwa
`na 've
`or 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.C|E—based color specification
`
`‘éTé’*°4.asea“‘°"”°ooior°'°i;"5';”"“°-°”°"oo.r....e,c""”“il..?‘
`_
`vice is
`_
`iy on
`I5
`is
`e
`_scope_of this manual (see the bibliogra hyl. The algorithm has many parameters.
`indiidmg_ai10pficnal. full mine cfmens n
`or lockup table. __ __
`
`4%: “
`
`OW9'0'9'0'9'0'o'¢'o'o‘¢'o'o'¢'¢'o'¢'€
`‘€0229292929292029iofofofoiofoiofofofé
`
`'.V.V.VV92920.9
`
`

`
`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 3 of 8
`
`5,504,842
`
`58
`K.
`
`‘iii’
`SELECT FIRST OBJECT-
`DESCRIPTION COMMAND
`
`82
`
`II4
`
`SELECT NEXT
`COMMAND
`
`II2
`
`)2‘;
`
`ANOTHER
`COMMAND
`7
`
`/\/O
`
`
`
`E .
`.
`.
`is R
`
`DOES
`
`OBJECT DESCRIBED
`
`
`BY THE COMMAND INTERSECT
`REGION I
`
`
`7
`
`
`
`DETERMINE PRIMITIVE ELEMENTS, BOUNDING
`BOX (BBOX), AND REPRESENTATION
`TYPE FOR COMMAND FOR REGION I
`
`UPDATE THE DISPLAY UST, AND BBOX
`OF THE SAME TYPE FOR REGION I
`
`II8
`
`
`
`"6 3-R
`-
`-
`is 3
`0REGION
`
`
`
`I
`BBOXES
`INTERSECT
`7
`
`
`
`
`
`Vi-'5
`
`DIVIDED REGIONAL BBOXES INTO
`NON-INTERSECTING BBOXES
`
`Fig. 4
`
`

`
`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 4 of 8
`
`5,504,842
`
`
`
`
`‘.''i-':'-‘-'''
`
`
`
`I
`
`'1, .1"
`‘Q
`
`
`
`
`
`J
`I
`
`134
`
`/,l36
`
`
`
`
` L‘\\\‘\\.\\!
`
`4
`'
`' J’ J’ 4' J J‘
`4
`4 .
`
`bD\\\\\\\\V
`x\\\\\\\\\V
`
`Jjfj
`.
`
`

`
`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 5 of 3
`
`5,504,842
`
`
`
`
`
`140
`
`LIST x AND Y
`COORDINATES AND
`ORDER THE _ Y
`COORDINATES
`
`
`
`
`
` SELECT NEXT T\X/O
`LOWEST Y COORDINATES
`
`‘I42
`AND ORDER
`THE X COORDINATES
`
`
`
`SELECT NEXT "N/O
`LOWEST X COORDINATES
`FOR TEST BOX
`
`
`
`
`
`
`
`
`
`
`IS
`TEST BOX IN A
`BBOX
`7
`
`
`
`
`
`
`
`IDENTIFY TYPES) OF
`REPRESENTATION AND
`STORE COORDINATES OF TEST
`BOX AND REPRESENTATION
`TYPEISI
`
`

`
`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 6 of 8
`
`5,504,842
`
`@
`
`SELECT COMPRESSION SCHEME
`BASED ON COMPRESSION
`FACTORS AND row AN ESTIMATE
`
`'50
`
`/
`
`If?
`
`RASTERIZE DISPLAY
`LIST FOR REGION i
`
`
`
`REVISE COMPRESSION
`SCHEME BASED ON
`CURRENT COMPRESSION
`FACTORS AND
`REVISE ESTIMATE
`
`
`
`COMPRESS RASTERIZED DATA WITH
`COMPRESSION SCHEME BASED ON
`CURRENT COMPRESSION FACTORS
`
`
`
`
`
`
`
`
`/V0
`
`UPDATE
`
`OR REPIQOCESS
`
`PROGRESS
`ADEQUATE
`? .
`
`
`
`REP/?OCE$$
`
`REVISE COMPRESSION SCHEME BASED ON CURRENT
`COMPRESSION FACTORS AND REVISE ESTIMATE
`
`
`
`/V0
`
`k
`
`I
`
`
`
`
`I80
`
`
`FOR REGION k IS
`
`COMPRESSED, SHOULD IT
`BE REPROCESSED
`
`
`
`
`DECOMPRESS DATA FOR REGION k
`RECOMPRESS WITH COMPRESSION SCHEME
`BASED ON CURRENT COMPRESSION FACTORS
`
`
`
`
`
`
`
`
`REVISE COMPRESSION SCHEME
`BASED ON CURRENT COMPRESSION
`FACTORS AND REVISE ESTIMATE
`
`UPD/I TE
`
`

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

`
`U.S. Patent
`
`Apr. 2, 1996
`
`Sheet 8 of 8
`
`5,504,842
`
`VISUAL
`INFORMATION
`
`,2
`
`SOURCE
`M
`OESCRIPI/I/E
`COMM/WDS
`
`II: _‘_‘:_'_T_‘_It ._. :_“__‘_
`
`I OUTPUT-DATA
`I
`
`COMMAND
`
`I54
`
`_‘_T_‘_T.: I _‘_‘__‘_“_‘_'_:‘_C_ TE‘: :_“_'_|‘ I
`
`I 0
`
`J
`
`16'
`
`16
`
`I
`
`I
`.
`
`1
`
`'
`
`I
`
`i
`I
`I
`I
`
`WORKING MEMORY : >/
`TYPES
`LISTS
`NON-INTERS. BBOXES - PROCESS
`BY REGION
`RASTER GENERATOR
`UNCOMPRESSED
`
`I
`MEMORY
`64
`BY REGION
`
`DISPIAY
`
`REGIONAL BBOXES
`
`DISTILLING
`
`'
`
`'
`
`
`
`I
`
`I96
`
`- - _ _ _
`
`
`
`- _
`
`- ' -
`
`20
`
`.'
`
`_____,.____
`
`vIsuAL-
`
`I
`
`Is
`
`I
`
`'
`I
`
`'66
`
`206
`
`I
`I
`l
`E
`I
`E
`5
`I
`I
`I
`I
`I
`I65
`;
`I
`I
`-L _ _ — _ _ _ ._.
`I
`I
`I
`COMPRESSION :
`I
`OUTPUT
`:
`I
`uI\IIr
`.
`. CONTROLLER I
`:
`:
`I
`'
`CONSULTANT ,
`.
`.
`I
`,
`.
`I
`I
`I
`I
`'
`COMPRESSED
`:
`'
`,
`I
`MEMORY
`I
`I
`I
`1
`BY REGION
`I
`I
`I
`I
`_ — _ - 1 - -
`— - _ _ — -'‘ - _ _ - ‘ . . ' - _ _ - _ - _ - - " — — _ ' — - E
`- -
`I
`'
`OUTPUT
`I
`.-204
`I
`I
`I CONTROLLER I
`;
`i
`Ijgiiif
`'\
`I
`-(I6 K202
`Ir--mfi _—___1
`I
`gtgfigg
`I ____ -_:_________ _-£.-_23,°
`I
`I""“' "" "'
`OUTPUT
`
`I
`I
`I
`I
`I
`I
`:
`I
`I
`|_
`
`I
`.
`CONTROLLER
`,
`.
`|
`2 ]\2
`_ _ . _ .. .. .,. _ _ _ _ _ _ I
`I
`I...._-:L _ _ _ . _ _ _ __II
`I..-____t _ _ _ _ __l
`I
`210,-I
`COMPRESSED ;_ _ _ ,I DECOMPRESSION ;
`I
`:
`:
`MEMORY
`.
`:
`UNIT
`.
`I
`I
`2I4 ——————————— -—I
`————— "-1"---“ I
`:
`I'IRI’cE§IIIIp}eIa§§I:'I$I
`;
`I
`.' "O‘U{,[,}‘":
`ICONTROLLERI‘""" ‘ ‘1
`MEMORY
`I‘ “““““ ‘ ‘
`‘I
`|- — — — — — — — — — J
`— — _ _ _ . ~ . . . _ _ _ I
`I
`
`2 I 6
`
`

`
`5,504,842
`
`1
`METHOD AND APPARATUS FOR
`PROCESSING DATA FOR A
`VISUAL-OUTPUT DEVICE WITH REDUCED
`BUFFER MEMORY REQUIRENIENTS
`
`This is a division of copending application Ser. No.
`07/974,204, filed on Nov. 10, 1992.
`BACKGROUND OF THE INVENTION
`
`l.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 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 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 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
`
`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 diiferent 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 commands 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
`
`

`
`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 transrr1it—
`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, inforrna-
`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
`
`

`
`5
`
`6
`
`5,504,842
`
`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 P0stScript 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 command”
`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, runlength 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 diiferent 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
`
`30
`
`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,
`
`

`
`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-
`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 representation type is assigned to each bounding
`box based on the associated primitive element type. In the
`preferred embodiment, the representation type is one of 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 lower left and upper r