US5479587A — Page printer having adaptive data compression for…

Claim 1

Independent Claim 224 words

In a peripheral unit that converts an input data flow to a page-arranged output, said peripheral unit including random access memory with allocated memory space for storing only a portion of said page-arranged output, a processor and control memory containing a plurality of data compression procedures, each said procedure exhibiting a speed of compression performance characteristic, a method for compressing portions of said input data flow for storage in said random access memory, said method comprising the steps of: allocating portions of said input data flow for storage in said random access memory; determining when an insufficient amount of said random access memory is available for allocation to said input data flow portions; employing a first data compression procedure upon a said input data flow portion to produce a compressed data portion, said first data compression procedure generally accomplishing data compression in less time than other data compression procedures available in said peripheral unit; testing a compression level of said compressed data portion against a compression threshold to determine if said compression level exceeds said threshold, and if not, employing another data compression procedure and repeating said testing in relation to a threshold, whereby a compression procedure is found that enables the compression level of said input data flow portion to exceed a said threshold and is employed to compress said data flow portion.

Claim 2

Dependent Claim 224 words

In a peripheral unit that converts an input data flow to a page-arranged output, said peripheral unit including random access memory with allocated memory space for storing only a portion of said page-arranged output, a processor and control memory containing a plurality of data compression procedures, each said procedure exhibiting a speed of compression performance characteristic, a method for compressing portions of said input data flow for storage in said random access memory, said method comprising the steps of: allocating portions of said input data flow for storage in said random access memory; determining when an insufficient amount of said random access memory is available for allocation to said input data flow portions; employing a first data compression procedure upon a said input data flow portion to produce a compressed data portion, said first data compression procedure generally accomplishing data compression in less time than other data compression procedures available in said peripheral unit; testing a compression level of said compressed data portion against a compression threshold to determine if said compression level exceeds said threshold, and if not, employing another data compression procedure and repeating said testing in relation to a threshold, whereby a compression procedure is found that enables the compression level of said input data flow portion to exceed a said threshold and is employed to compress said data flow portion.

Claim 3

Dependent Claim 72 words

The method as recited in claim 1 wherein said data compression procedures comprise ones which compress data in a lossless manner and at least another which compresses data in a lossy manner, data compressed in a lossless manner being decompressible with no loss of data and data compressed in a lossy manner being decompressible only with loss of data, a said lossless compression procedure being employed first before said lossy compression procedure.

Claim 4

Dependent Claim 85 words

The method as recited in claim 2 wherein one said lossless compression procedure is a Lempel/Ziv/Welch (LZW) compression procedure, said procedure building a table of received data strings and assigning a code to each said string, the method further comprising: limiting the number of string entries in said table to less than a maximum required to obtain optimum data compression, so as to limit a code length required to identify a said string, thereby enabling compression and decompression actions to occur at a faster rate.

Claim 5

Dependent Claim 70 words

The method as recited in claim 1 wherein subsequent to said allocating step but prior to said determining step, the method comprises an additional step of: determining if any said data portion exceeds a predetermined data size, and if so, further determining if allocatable memory remaining within said random access memory is less than a predetermined level, and if both determinations are affirmative, subjecting said data portion to data compression.

Claim 6

Dependent Claim 20 words

The method as recited in claim 4 wherein said data compression is accomplished by use of a lossless compression procedure.

Claim 7

Dependent Claim 42 words

The method as recited in claim 5 further comprising the steps of: storing said data portion in random access memory after it has been data compressed; and adjusting said predetermined level by subtracting therefrom memory space taken by said stored data portion.

Claim 8

Dependent Claim 96 words

The method as recited in claim 1 wherein said peripheral unit includes a print engine that, when operative, runs at a constant speed, said method comprising the additional steps of: calculating a complexity factor for data portions within a page and determining if said complexity factor indicates that too great a time will be required to convert said data portions to a raster video format in relation to said print engine speed; and upon such a determination, subjecting at least one data portion to immediate conversion to a raster video format and performing data compression thereon.

Claim 9

Dependent Claim 51 words

The method as recited in claim 7, wherein if at any time subsequent to said conversion and compression of said one data portion, it is determined that remaining data portions can be acted upon without causing a memory out indication, said remaining data portions are converted to raster video without compression.

Claim 10

Dependent Claim 47 words

The method of claim 1 wherein a said image data includes font data, the method comprising the further step of: automatically applying a lossless compression technique to said font data if a font represented by said font is at least equal in size to a predetermined level.

Claim 11

Dependent Claim 38 words

The method of claim 9 wherein, if said font size is not equal to said predetermined level, applying said lossless compression technique only in the event random access memory for storing said image data is insufficient in capacity.

Claim 12

Independent Claim 116 words

A method for data compressing a raster pixel image, comprising the steps of: a. performing run-length encoding for data segments in an initial raster row of said image and outputting, for each run of a data segment in said row, a run length command indicating a run count and an identification of the run data segment; and b. for data segments in a subsequent row of said image, comparing whether said data segments are the same as or different from data segments in an immediately previous raster row; and c. issuing commands which identify for said subsequent raster row, which of said data segments exhibit said "same" condition and further indicate said different said data segments.

Claim 13

Independent Claim 116 words

A method for data compressing a raster pixel image, comprising the steps of: a. performing run-length encoding for data segments in an initial raster row of said image and outputting, for each run of a data segment in said row, a run length command indicating a run count and an identification of the run data segment; and b. for data segments in a subsequent row of said image, comparing whether said data segments are the same as or different from data segments in an immediately previous raster row; and c. issuing commands which identify for said subsequent raster row, which of said data segments exhibit said "same" condition and further indicate said different said data segments.

Claim 14

Dependent Claim 46 words

The method as recited in claim 11 wherein step(b) further identifies a presence of a run of data segments in a said subsequent raster row and outputs a run command comprising a count and an identity of the data segment that is repeated in said run.

Claim 15

Dependent Claim 36 words

The method as recited in claim 12 wherein said further identification of a run of a data segment only occurs after a different data segment is determined and before a same data segment is next detected.

Claim 16

Dependent Claim 24 words

The method as recited in claim 13 wherein run length encoding may span from raster row to raster row until a said run ends.

Claim 17

Dependent Claim 42 words

The method as recited in claim 11 wherein said command issued in step c includes a count of the number of same data segments, followed by a count of and an identity of different data segments that follow said same data segments.

Claim 18

Dependent Claim 48 words

The method as recited in claim 11 further comprising the step of: eliminating any commands issued for a raster row if said row is found to be identical to an immediately adjacent row; and issuing a repeat row command that causes said immediately adjacent row to be repeated.

Claim 19

Dependent Claim 47 words

The method as recited in claim 11, further comprising the steps of: inserting an end of row command when a run of zeros is sensed at an end of a row; and upon decompression, padding with zeros any row that ends prior to a predetermined row length.

Claim 20

Independent Claim 157 words

A method for data compressing a raster-arranged pixel image, comprising the steps of: a. providing a first table of data segment patterns indicative of an image comprised of clustered bit patterns and of an image comprised of dispersed bit patterns; b. comparing data segments of an image to said data segment patterns in said first table to determine a classification of said image, said classification comprising clustered or dispersed; c. compressing said image by reducing each n×n bit block of said pixel image to an n-bit data segment and accompanying said compressed image by a classification indicator; and d. decompressing said image by employing said n-bit data segment to access a stored n×n pixel matrix from a pair of matrix tables in accordance with said classification indicator, one said tables including n×n-bit images classified as clustered and another said table including n×n-bit images classified as dispersed, each said table addresses in accordance with said n-bit data segment.

Claim 21

Independent Claim 157 words

A method for data compressing a raster-arranged pixel image, comprising the steps of: a. providing a first table of data segment patterns indicative of an image comprised of clustered bit patterns and of an image comprised of dispersed bit patterns; b. comparing data segments of an image to said data segment patterns in said first table to determine a classification of said image, said classification comprising clustered or dispersed; c. compressing said image by reducing each n×n bit block of said pixel image to an n-bit data segment and accompanying said compressed image by a classification indicator; and d. decompressing said image by employing said n-bit data segment to access a stored n×n pixel matrix from a pair of matrix tables in accordance with said classification indicator, one said tables including n×n-bit images classified as clustered and another said table including n×n-bit images classified as dispersed, each said table addresses in accordance with said n-bit data segment.

Claim 22

Dependent Claim 78 words

The method as recited in claim 18 wherein said image is classified as either clustered or dispersed by assigning a first value to any data segment of said image that matches a clustered data segment pattern in said first table and assigning a second value to any data segment that matches a dispersed data segment pattern in said first table, said classification determined by combining said first and second values and comparing said combined values to a threshold.

Claim 23

Dependent Claim 28 words

The method as recited in claim 19 wherein said first values are positive numbers and said second values are negative numbers, said threshold being a neutral value therebetween.

Claim 24

Dependent Claim 202 words

In a peripheral unit for converting an input data flow to a page--arranged output, said peripheral unit having insufficient random access memory allocated to store an entire video raster image of said page arranged output, a method for converting said input data flow to a page intermediate form that includes a plurality of image strips that make up said page arranged output, each image strip including image processing commands that enable subsequent conversion of each said image strip to a raster video form, said method comprising: a. establishing a threshold value of data segments in an image strip; b. determining (1) if a number of data segments in an image strip exceeds said threshold value, and (2) if remaining memory in said random access memory is less than a predetermined level and if said determinations 1 and 2 are affirmative; c. converting said image strip immediately to raster video and attempting a compression thereof; d. storing in said random access memory, compressed raster video that results from step c; e. adjusting said threshold value to a smaller value to account for remaining random access memory in said random access memory; and f. repeating steps a-e for remaining image strip of said page.

Claim 25

Dependent Claim 202 words

In a peripheral unit for converting an input data flow to a page--arranged output, said peripheral unit having insufficient random access memory allocated to store an entire video raster image of said page arranged output, a method for converting said input data flow to a page intermediate form that includes a plurality of image strips that make up said page arranged output, each image strip including image processing commands that enable subsequent conversion of each said image strip to a raster video form, said method comprising: a. establishing a threshold value of data segments in an image strip; b. determining (1) if a number of data segments in an image strip exceeds said threshold value, and (2) if remaining memory in said random access memory is less than a predetermined level and if said determinations 1 and 2 are affirmative; c. converting said image strip immediately to raster video and attempting a compression thereof; d. storing in said random access memory, compressed raster video that results from step c; e. adjusting said threshold value to a smaller value to account for remaining random access memory in said random access memory; and f. repeating steps a-e for remaining image strip of said page.

Claim 26

Dependent Claim 41 words

The method as recited in claim 21 wherein step (c) employs a compression action that examines blocks of raster data and performs compression actions that take into account both vertical and horizontal data redundancies in each said block of raster data.

Claim 27

Dependent Claim 46 words

The method as recited in claim 22 wherein said compression action comprises the steps of: providing output commands which indicate vertical redundancies existing between succeeding rows of a block of raster data and further providing commands indicative of horizontal data redundancy occurring in a said row.

Claim 28

Dependent Claim 41 words

A method as in claim 21 where the strip complexity can be empirically determined by measurement with a system timer, and this result used to ascertain whether to pre-rasterized the strip when the complexity prediction is within the uncertain complexity window.

Claim 29

Dependent Claim 144 words

In a peripheral unit that converts an input data flow to a page-arranged output, said data flow including data describing an image, a said image comprised of a set of subimages, each subimage further comprised of a video raster bit map and a descriptor having a field that identifies where said video raster bit map is stored, a method for compressing data representing a said image and subimages, comprising: selecting a group of descriptors that represent a subset of said set of subimages; attempting to compress, through the use of a first compression technique, the video raster bit map associated with each said selected descriptor; comparing against a threshold, a level of compression of said subset of subimages achieved through said compression attempt and if said threshold is at least equalled, employing said first compression technique to data compress all subimages comprising said image.

Claim 30

Dependent Claim 144 words

In a peripheral unit that converts an input data flow to a page-arranged output, said data flow including data describing an image, a said image comprised of a set of subimages, each subimage further comprised of a video raster bit map and a descriptor having a field that identifies where said video raster bit map is stored, a method for compressing data representing a said image and subimages, comprising: selecting a group of descriptors that represent a subset of said set of subimages; attempting to compress, through the use of a first compression technique, the video raster bit map associated with each said selected descriptor; comparing against a threshold, a level of compression of said subset of subimages achieved through said compression attempt and if said threshold is at least equalled, employing said first compression technique to data compress all subimages comprising said image.

Claim 31

Dependent Claim 80 words

The method as recited in claim 25 wherein each said descriptor has fields reserved for indicating facts regarding an associated video raster bit map, said method further comprising: employing a second compression technique upon said subset of subimages in the event said level of compression is not equalled and again comparing an achieved level of compression against a threshold and employing said second compression technique for all subimages of said image in the event said threshold is at least equaled.

Claim 32

Dependent Claim 36 words

The method as recited in claim 26 wherein said facts in each said descriptor are employed during decompression of said image, said facts indicating the method of compression employed to compress said video raster bit maps.

Claim 33

Dependent Claim 16 words

The method as recited in claim 27 wherein at least said first compression method is lossless.

Claim 34

Dependent Claim 68 words

The method as recited in claim 28 wherein said peripheral unit includes random access-memory (RAM) whose capacity is insufficient to store an entire page of said page-arranged output, said method comprising the further steps of: determining, subsequent to application of a said compression technique, whether sufficient space is available in said RAM to store a compressed image and, if not; applying a lossy compression technique to said subimages.

Claim 35

Dependent Claim 64 words

The method as recited in claim 29 wherein, as part of said lossy compression technique, said image is classified as either dispersed or clustered by comparison of video raster bit maps of at least some said subset of subimages to a table of entries that define bit patterns comprising clustered and dispersed bit arrangements, said classification employed during decompression of said lossy compressed image.

Claim 36

Dependent Claim 42 words

The method as recited in claim 29, wherein said lossy compression technique is employed for said image only if a prior applied lossless compression technique did not exceed a level of compression of said image that is available from said lossy technique.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1998-12-25	1999-06-26	1999-12-26	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2002-12-25	2003-06-26	2003-12-26	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2006-12-25	2007-06-26	2007-12-26	$7700.00	Window Closed / Lapsed

Page printer having adaptive data compression for memory minimization

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag