+

WO1996039682A1 - Classification par blocs pour acelerer la compression des donnees d'images - Google Patents

Classification par blocs pour acelerer la compression des donnees d'images Download PDF

Info

Publication number
WO1996039682A1
WO1996039682A1 PCT/US1996/008489 US9608489W WO9639682A1 WO 1996039682 A1 WO1996039682 A1 WO 1996039682A1 US 9608489 W US9608489 W US 9608489W WO 9639682 A1 WO9639682 A1 WO 9639682A1
Authority
WO
WIPO (PCT)
Prior art keywords
color
partitioned
image data
blocks
block
Prior art date
Application number
PCT/US1996/008489
Other languages
English (en)
Inventor
Hungviet H. Nguyen
Riaz A. Moledina
Kok S. Chen
Original Assignee
Apple Computer, Inc.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Apple Computer, Inc. filed Critical Apple Computer, Inc.
Priority to AU62514/96A priority Critical patent/AU6251496A/en
Publication of WO1996039682A1 publication Critical patent/WO1996039682A1/fr

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding

Definitions

  • the present invention relates generally to compression and decompression of digitized image data. More particularly, the invention relates to encoding variant color image data during compression of the image data.
  • Digitized images displayed on scanners, monitors and printers are typically quantized on a pixel-by-pixel basis and stored in memory as pixel maps, more commonly referred to as pixmaps.
  • a pixmap is a two-dimensional array of picture elements mapped to locations of the digitized image.
  • each pixel is typically stored in memory as a set of color coordinates which define the pixel's color location in a given color space. For example, a pixel is typically represented by its red, green and blue color component values, or by its cyan, magenta and yellow color component values.
  • the fidelity of the color reproduction is a function of the accuracy with which each color component is represented.
  • the Fourier Transform transforms the input space into one which is spanned by complex exponentials.
  • the Principal Component Transform transforms the input space into one which is spanned by the eigenvectors associated with the input data. Although the Principal Component Transform is preferred, the amount of computation required to perform compression is practically prohibitive.
  • the Discrete Cosine Transform was developed to avoid the prohibitive computation of the Principal Component Transform.
  • the basis functions of the Discrete Cosine Transform are cosines of various frequencies. For photographic images, this transform has been determined to yield results closer to that of the Principal Component Transform than any transform other than the Principal Component Transform itself.
  • the Discrete Cosine Transform in combination with entropy-preserving compression techniques, evolved into the industry standard (Joint Photographic Experts Group) JPEG compression, as described in "Graphics File Formats",
  • the present invention provides a method in accordance with independent claim 1 and an apparatus in accordance with independent claim 11. Further advantageous features, aspects and details of the invention are set forth in the dependent claims, the following description and the drawings. The claims are to be understood as a first non-limiting approach of defining the invention in general terms.
  • exemplary embodiments relate to a method and apparatus for processing a frame of image data by partitioning the frame of image data into a plurality of partitioned blocks of pixels; identifying each partitioned block as being color variant, color invariant, or clear (such as is the case with a totally white page); storing color values of at least some of said pixels; and storing information which identifies each partitioned block as being color variant, color invariant or clear.
  • the frame of image data can be compressed by retrieving the information which identifies each partitioned block as being color variant, color invariant or clear, and controlling a retrieval of said color values in response to said retrieved information.
  • enhanced processing speed can be realized with reduced memory requirements. More particularly, when the retrieved information identifies a given partitioned block as being clear, the partitioned block can be immediately compressed without examining any color values associated with that block. Further, when the retrieved information identifies a given partitioned block as being color invariant, then only a single pixel of the partitioned block need be examined to determine a color value associated with all pixels of the color invariant block. Only when the retrieved information identifies a given partitioned block as being color variant are color values for all pixels of that block retrieved. As a result, compression speed can be significantly increased since the color values for each pixel in clear blocks need not be retrieved.
  • compression speed can be further enhanced by retrieving the information associated with a plurality of the partitioned blocks in groups. For an entire group of blocks (for example, four partitioned blocks in a four block group), wherein all partitioned blocks are determined to be clear, no color values for the pixels in any of the partitioned blocks of the group need be retrieved, thereby significantly enhancing processing speed. Similarly, where all partitioned blocks in the group are color invariant, then only a single pixel value for each partitioned block within the group need be retrieved to compress the four block group. Only when any partitioned block of the group includes color variant data are color values associated with more than a single pixel specifically retrieved.
  • Figure 1 illustrates a printing control system which incorporates an exemplary embodiment of the present invention
  • Figures 2a-2g represent exemplary blocks of image data which can be processed in accordance with exemplary embodiments of the present invention.
  • Figures 3a-3g represent exemplary embodiments of image data which can be compressed in accordance with exemplary embodiments wherein each partitioned block includes 8 consecutive blocks;
  • Figures 4a-4d illustrate an exemplary format for encoding color invariant image data;
  • Figures 5a-5e illustrate exemplary formats for encoding color variant image data
  • Figure 6 illustrates an exemplary embodiment of a compression /decompression coprocessor for use in accordance with the present invention
  • Figure 7 illustrates an exemplary format for storing color data in memory
  • Figure 8 illustrates an exemplary embodiment of hardware for decompressing data
  • Figure 9 illustrates an exemplary embodiment of a selector included within the Figure 8 hardware.
  • Figure 1 illustrates an exemplary embodiment of an apparatus for processing a frame of image data such that the image data can be encoded for compression in accordance with an exemplary embodiment of the present invention.
  • image data corresponds to data obtained from an image that can be quantized (for example, digitized) for storage in a pixmap and subsequently compressed.
  • Image data that is compressed in accordance with exemplary embodiments of the present invention can be digitized image data captured through any instrumentation, such as a video camera.
  • Image data as referenced herein encompasses scanned data as well as non-scanned data.
  • Non-scanned data typically includes character glyphs and graphical data, such as hand-sketched or computer generated graphics.
  • image data processed in accordance with exemplary embodiments of the present invention can also include any combination of scanned and non-scanned data.
  • a frame of quantized image data corresponds to a preselected group of digitized data, such as the data associated with a display screen or a printed sheet.
  • image data is obtained from or reproduced using a scanner device, a monitor or a printing device.
  • the image data can merely be processed for transfer between two locations (for example, between two computers).
  • exemplary embodiments of the present invention can be applied to the processing of image data for reproduction using any visual medium.
  • the image will typically be reproduced on conventional size paper such as letter size, A4, B5 and legal size.
  • the present invention can be applied to images of any size which are reproduced in any format.
  • Figure 1 illustrates a printing system 100 which incorporates features of the present invention.
  • the Figure 1 printing system includes a color laser engine 102, such as any commercially available color laser marking engine.
  • a color laser engine 102 such as any commercially available color laser marking engine.
  • color includes use of multiple colors (such as red, green and blue), as well as grey-scale printing using varying shades of gray.
  • an incoming frame of data is directed by a processor, represented as printing system controller 106 having associated memory 104, to a compression /decompression coprocessor 108 (CDC).
  • the printing system controller 106 partitions a frame of quantized image data into partitioned blocks.
  • the compressor /decompression coprocessor 108 constitutes an exemplary apparatus for processing a frame of image data by compressing the image data within each of the partitioned blocks. More particularly, the coprocessor 108 includes a processor for prequantizing image data by selectively eliminating bits used to represent at least one color component of each pixel for the frame of image data and for encoding the remaining bits of the prequantized data to compress the prequantized data.
  • a frame buffer stores the incoming frame of image data in portions (for example, on a row-by-row basis), for sequential processing. As each portion of the frame is compressed, another portion is fetched by the printing system controller. As a result, an entire frame of image data is only stored in the print system 100 after it has been compressed in a manner to be described in accordance with exemplary embodiments of the present invention.
  • the printing system controller 106 can be a reduced instruction set computer (RISC) such as the 33 Megahertz 29030 processor available from Advanced Micro Devices.
  • RISC reduced instruction set computer
  • the printing system controller 106 pre-processes an incoming frame of image data to: (a) scale the image data to a desired resolution; (b) partition the image data into partitioned blocks of a predetermined size; (c) resample the image data to ensure its alignment with the partitions; (d) filter the image data to ensure that each partitioned block contains no more than a predetermined number of color variations; and (e) create a side information buffer with information acquired during the pre-processing that can be used to enhance performance during subsequent processing.
  • the compressing of image data includes an initial step of classifying each partitioned block based on whether the partitioned block is determined to be color variant or determined to be color invariant. This step of classifying can be implemented by comparing the pixels within a given partitioned block to one another during the pre-processing to determine whether a given partitioned block is color variant or color invariant. Once having classified each partitioned block as being either color variant or color invariant, the compression /decompression co-processor 108 can be used to further compress the data.
  • each partitioned block can be performed by the printing system controller 106 as part of the pre-processing (for example, classification information can be stored in the side information buffer), or can be performed by the compression /decompression coprocessor 108.
  • the compression/ decompression coprocessor compresses the image data included in the partitioned blocks of pixels to substantially reduce the memory requirements required to store a frame of image data.
  • the compression/decompression coprocessor compresses the image data within each partitioned block by representing a block which is determined to include color variations with less color fidelity than a block which is determined not to include color variations.
  • thecompression/ decompression coprocessor uses memory (that is, any specified memory) for storing the compressed image data as a representation of the original image.
  • the compressed image data can be immediately transmitted from the printing system 100 as it is compressed, for external buffering and decompression.
  • a decompression engine is included within the compression /decompression coprocessor for use during the compression process. Recall that an entire frame of uncompressed image data is not stored in the printing system 100 at any given time; rather the entire frame is stored and compressed in sequentially processed portions.
  • the decompression engine is provided within the compression /decompression coprocessor to accommodate a situation where newly received image data is to be superimposed on portions of the frame which have been earlier compressed. In this situation, the earlier compressed portion of the frame is retrieved, decompressed and returned to the frame buffer. The decompressed data which has been returned to the frame buffer is then overlaid with the newly received image data, after which the superimposed image data is recompressed.
  • the compression /decompression coprocesssor 108 can, for example, be formed as a monolithic application specific integrated circuit (that is, an ASIC chip). However, those skilled in the art will appreciate that the processing implemented by the coprocessor 108 can be performed by the same processor used to implement the functions of the controller 106. Alternately, the compression/decompression functions can be implemented with any or all other functions of the Figure 1 system in a single ASIC using a single processor. Further, those skilled in the art will appreciate that the compression and decompression functions of the Figure 1 system can be implemented in software or hardware. In the exemplary Figure 1 embodiment, the compression functions are implemented using software and hardware, while the decompression functions are primarily implemented in hardware.
  • the video interface device can, for example, be formed as a separate ASIC chip having a decompression processor to support decompression and half ⁇ toning. Alternately, a single processor can be used to implement the functions of the controller 106, the coprocessor 108 and video interface device 112.
  • the video interface device provides high quality reproduction of the original image from its compressed format.
  • the Figure 1 system further includes an input /output (I/O) communications device 114.
  • the input/output communications device can include, for example, built-in networking support as well as parallel /serial I/O ports. Further, the I/O communications device can include additional memory as well as memory expansion ports. Any conventional I/O communications features can be used in accordance with the present invention, such that the I/O communications device need not be described in detail.
  • the data format of uncompressed image data will be described. Afterward, pre ⁇ processing of the uncompressed image data will be discussed. Further, exemplary data formats of compressed image data will be discussed.
  • a frame of image data associated with an original image has a given width and length.
  • the number of pixels in a given row of a scan line across the width of the frame is set in a horizontal total pixel count register.
  • the value set in the horizontal total pixel count register is divisible by 4.
  • the number of pixels is set in a vertical total pixel count register.
  • the value set in the vertical total pixel count register of exemplary embodiments is divisible by 4.
  • the user can also set the number of bits used to represent each color component for a given pixel to 1, 4 or 8 bits. For example, if the user selects 4 color components to define a pixel, with each color component being represented by 8 bits, then each pixel would be represented as a 32-bit word (that is, 8 bits for each of the cyan, magenta, yellow and black color components).
  • the color of a pixel can be represented by any number of color components, including 1, 3 or 4 color components.
  • a four color component representation includes cyan, magenta, yellow and black color components.
  • the color of a pixel is defined by the magnitude of a single color component (such as black).
  • the color components used can be cyan, magenta and yellow color components.
  • the 4 color components mentioned above can be used to define the color of a given pixel.
  • exemplary embodiments of the present invention are directed to compressing this data in a manner which ensures the integrity of color fidelity in the decompressed image.
  • uncompressed image data which is received for storage in the frame buffer is preprocessed to optimize the compression process.
  • the preprocessing includes: (a) scaling a frame of digitized image data to ensure that each partitioned block will have the same number of pixels; (b) partitioning the frame into blocks having a predetermined number of pixels; (c) resampling the image data to account for misalignment between the frame of image data and partitioned blocks; (d) filtering to reduce the number of color variations within each partitioned block to a predetermined number; and (e) creating a side information buffer to enhance subsequent performance during compression.
  • Scaling Scaling is implemented by the printing system controller 106 of Figure 1 to ensure that an input image has a resolution which will match the selected size of partitioned blocks. For example, where a partitioned block is selected to include a 4-by-4 array of pixels, the incoming frame of image data is scaled to ensure that the number of pixels in each row and in each column is a multiple of 4.
  • the scaling can be implemented in any known fashion.
  • scaling can be implemented using pixel replication as described by Dale A. Schumacher in chapter 4 ("Fast Anamorphic Image Scaling") of the book entitled Graphic Gems II; Arvo, James; San Diego: Academic Press, Inc. 1991. It may be that a frame of image data has been generated at a resolution of 72 dots per inch.
  • the image data can be scaled up to 150 dots per inch for subsequent transfer to the compression /decompression coprocessor.
  • any scaling techniques can be used in accordance with exemplary embodiments of the present invention. Such scaling techniques can be used to either scale up or scale down an input frame of image data to any user selected resolution.
  • each frame of image data is partitioned into blocks formed as 4-by-4 pixel arrays.
  • the exact block size can be set by the user as a block size field stored in a register.
  • the partitioned blocks can have any number of pixels, and that the blocks can be of any desired shape. It is only preferable that the blocks are capable of being tiled in non-overlapping fashion to encompass the entire image.
  • the shape of each partitioned area need not be square, but can be rectangular, cross-shaped, or shaped as described in "Tilings and Patterns, an Introduction", by W. H. Freeman, New York, 1989, ISBN 0-7167-1998-3.
  • partitioning is not limited to a single shape, but can be a combination of shapes.
  • non-tiled and /or non-overlapped blocks can be used at some possible expense to the compressed buffer size and /or the integrity of the compressed data relative to the original image.
  • a frame of image data is repositioned when the center of a 4-by-4 pixel block does not align with the center of a partitioned block. For example, it is possible that an incoming frame of image data is already at the desired resolution, such that scaling of the data is not necessary. However, the image data may not be aligned with the preselected partitions of the memory where the uncompressed is stored (for example, the frame buffer).
  • the image data may be such that the first partitioned block of pixels in the frame buffer is only half full of data (that is, either the first two rows or the first two columns of a 4-by-4 partitioned block contain no image data).
  • the image data included within the pixel block is resampled such that the center of the resampled data is repositioned in alignment with the center of a partitioned block.
  • This repositioning can be achieved by any conventional resampling technique. For example, resampling can be achieved using spatial filtering, nearest neighbor filtering, bi-linear interpolation, bi- cubic interpolation and so forth.
  • the compressing of image data includes the step of classifying each partitioned block as color variant or color invariant.
  • the image data is processed to ensure that no partitioned block includes greater than a predetermined number of color variations.
  • processing can be achieved in any number of ways.
  • each partitioned block is limited to at most two different colors. The two colors which are retained can be those deemed furthest from one another in a given color space.
  • each partitioned block can be limited to any number of colors (for example, 7 or more colors).
  • each partitioned block is limited to two colors and where a given block includes the colors red, blue and light blue
  • the light blue pixels can be converted to blue.
  • color averaging of the pixels can be used to determine a single averaged color for all pixels within the partitioned block.
  • a previously multi-color partitioned block can be subsequently treated as a color invariant block (that is, a single color block) during the compression process.
  • the first two colors detected in each partitioned block can be selected as the two colors to which all pixels in that block will be mapped.
  • the color of the first pixel examined can be selected as the first color, and the color of each subsequent pixel can be compared against that of the first pixel.
  • the color deemed furthest from the first color in a given color space can be selected as the second color, and each pixel in block can be mapped to one of these two colors.
  • the pre-processing can also include the creation of a side information buffer.
  • the side information buffer can be used to store any characteristics of the pre-processed data which can be used to enhance the efficiency of subsequent compression or decompression processing.
  • the printing system controller 106 can store information which identifies each partitioned block as color variant, color invariant or clear (that is, totally white). Such information can be encoded for each partitioned block as a 2-bit value in the side information buffer.
  • each pixel of each partitioned block is examined to classify each partitioned block as color variant, color invariant and if desired, clear.
  • the detection and classification of the partitioned blocks as being color variant, color invariant or clear can be performed while the color values are being stored in a frame buffer prior to image data compression.
  • a color value for each pixel can be stored in the memory 104 of Figure 1 at a location used to store at least a subset of the frame of image data during pre-processing.
  • the exemplary 2-bit index can be stored in a location of the side information buffer, which can also be included in the memory 104, to identify whether the partitioned block was color variant, color invariant or clear.
  • the side information buffer can be used to identify that the partitioned block, and all pixels included therein, were clear, such that no color values need be fetched from the memory 104 for that partitioned block.
  • a single color value for the entire partitioned block could be stored in the memory 104 at this time, rather than storing a color value for each pixel.
  • a color value is stored for each pixel value in the memory 104, and a subsequent compression of that color value information is performed by the compression /decompression coprocessor 108.
  • the plurality of partitioned blocks of pixels included in a frame of image data can be grouped into subsets of N partitioned blocks.
  • N can be set to 4, such that 4 partitioned blocks of pixels are grouped together for compression.
  • the compression /decompression coprocessor accesses the side information buffer of memory 104 as each partitioned block in a group of partitioned blocks is accessed. Referring to Figure 2A, the first group of 4 partitioned blocks stored in the memory 104 is examined first.
  • exemplary embodiments provide a side information buffer which is separately addressable by the compression/ decompression coprocessor (that is, separate from portions of the memory which include color value information).
  • the compressor/decompressor can independently examine the information in the side information buffer associated with these 4 blocks.
  • the information in the side information buffer is examined sequentially for each partitioned block in a group currently under consideration. As each block within the group is examined, the compression/decompression coprocessor 108 determines whether the block is clear, color invariant or color variant. In the case of Figure 2a, the side information buffer would identify each of the four partitioned blocks included in the first group as being clear. As a result, the compression /decompression coprocessor would use the information from the side information buffer to encode these four partitioned blocks as clear, and would not access any of the color value information which may or may not have been stored in connection with these partitioned blocks within memory 104.
  • processing speed of partitioned blocks encoded in the side information table as being clear is significantly enhanced since the color values for each of the 16 pixels included in partitioned blocks of this first group need not be retrieved.
  • the compression /decompression coprocessor controls a retrieval of color values from the memory 104 prior to compression of the image data.
  • Figure 2b illustrates a group of four partitioned blocks which are color invariant.
  • the compression/ decompression coprocessor 108 first retrieves information stored in the side information buffer associated with each of the four partitioned blocks of Figure 2b. Because the 2-bit value in the side information buffer for each of the four partitioned blocks will identify each of the four partitioned blocks as being color invariant, the compression/ decompression coprocessor can control a retrieval of only a single color value associated with, for example, the upper-most left hand pixel in the first partitioned block. This color value can then be used to encode a color value for all pixels included of the four block groups.
  • Figure 2c illustrates a group of four partitioned blocks wherein three of the four blocks are clear, and the second of the four blocks is color invariant.
  • information which identifies each of the partitioned blocks as being either color variant, color invariant or clear is retrieved from the side information buffer. This information identifies the second of the four blocks as being color invariant.
  • the compression /decompression coprocessor 108 retrieves a color value for at least one pixel in each of the four partitioned blocks. A color value associated with the at least one pixel for each partitioned block can then be used by the compression/ decompression coprocessor 108 to compress the color for each of these partitioned blocks using the compressed data format for color invariant blocks.
  • Figures 2d-2g illustrate groups of partitioned blocks wherein at least one partitioned block includes color variant data. If during retrieval of information from the side information buffer for each of the partitioned blocks, any one of the partitioned blocks is sequentially determined to be color variant, then the compression /decompression coprocessor retrieves the color value for each pixel included in the partitioned block. The image data for that partitioned block is then compressed using a compressed data format for color variant blocks to be described.
  • Figures 2d-2g illustrate different exemplary possibilities which can occur during retrieval of groups of four partitioned blocks.
  • all four blocks are determined to be color variant such that the color values for each pixel in all four blocks must be retrieved from the memory 104 prior to compression.
  • Figure 2e illustrates a group of four partitioned blocks wherein the third block is determined to be color variant.
  • the compression /decompression coprocessor retrieves color values for all pixels in the groups of partitioned blocks since the exemplary embodiment is configured to process all blocks of a group in similar fashion.
  • Figure 2f illustrates a situation where three of the four partitioned blocks in the group are clear. However, because the third partitioned block is color variant, pixel values for all four partitioned blocks would be retrieved from the memory 104.
  • color invariant blocks are detected until the fourth block in the group is examined. Because the fourth block is color variant, the compression /decompression coprocessor 108 would retrieve color values for all pixels in the group of partitioned blocks as described previously.
  • partitioned blocks can be grouped in any user-specified manner to accommodate a particular type of input image which is to be processed. For example, where the user knows in advance that frames of image data to be processed represent pages which are, for the most part, all white (i.e., clear), processing speed can be enhanced by grouping larger number of partitioned blocks to be processed by the compression / decompression coprocessor.
  • Figures 3a-3g illustrate groups of eight partitioned blocks.
  • Figure 3a illustrates a situation where all of the eight partitioned blocks are determined to be clear based on information in the side information table.
  • the compression /decompression coprocessor can compress a group of eight partitioned blocks without retrieving any information from the memory 104 other than information included in the side information buffer.
  • Figure 3b illustrates a situation where all eight blocks included in the group are color invariant.
  • Figure 3c illustrates a situation where all of the blocks are either clear or color invariant.
  • the compression /decompression coprocessor 108 can compress the image data included in this group of eight partitioned blocks by merely examining the color values for a reduced number of pixels (for example, the first row of pixels) in each partitioned block.
  • At least one block in the group of eight partitioned blocks includes variant color data.
  • the compression /decompression coprocessor retrieves color values for all pixels in each of the partitioned blocks when compressing these groups of partitioned blocks.
  • exemplary embodiments can significantly enhance the processing speed of a frame of image data.
  • Exemplary embodiments exploits statistical facts, such as: (1) the burst read of four consecutive partitioned blocks incurs a relatively slight penalty relative to random fetches; and (2) for a given image or textual page, there is a relatively high probability that the same data or data of similar type will repeat itself over an area.
  • Exemplary embodiments exploit these statistical facts using a side information buffer as described previously, such that the compression /decompression coprocessor 108 need not scan and /or retrieve the entire frame buffer of raw image data.
  • the added processing required to scan the side information buffer in accordance with exemplary embodiments of the present invention does not incur significant performance penalty. Rather the compression /decompression coprocessor can be configured to always look ahead to the next group of consecutive partitioned blocks to be processed while compression of the current group is being performed. In accordance with exemplary embodiments, the compression/decompression coprocessor can thus be maintained busy for a sufficiently long enough period of time to impose minimum performance constraints on the overall compression process.
  • any specified blocks can be specifically identified during the preprocessing and used to enhance the speed of the compression process.
  • blocks determined to have certain color characteristics, such as saturated colors can be identified during the pre- processing and afforded a unique encoding in the side information buffer.
  • processing of the specified blocks can be enhanced during compression.
  • the side information buffer has been described as a separately addressable portion of the memory 104 ( Figure 1), the side information buffer can, of course, be formed as a separate memory altogether.
  • the side information buffer can be formed in any one of the components illustrated in Figure 1, the only limitation being that the side information table must be accessible to receive the classification information of each partitioned block as the color values for each partitioned block as the color values for each partitioned block are examined during pre-processing, and must also be accessible during the compression process.
  • a compressed data format (CD) is used whereby a single data word represents an entire partitioned block of pixels.
  • a single data word of up to 32 bits can be used to reconstruct what was previously described by the sixteen 32- bit words of a 4-by-4 pixel array, without creating noticeable color degradation of the decompressed image regardless of whether the image includes scanned images, non-scanned images or any combination of the two.
  • the location of compressed data in memory of the compression /decompression coprocessor is defined by a compression data pointer register. Because exemplary embodiments described herein are directed to the use of memory space having 32-bit word locations, words of up to 32 bits can be specified as a user-defined compressed data width field.
  • a "compressed data word" is used to represent a compressed data block, and all such compressed data blocks are stored back-to-back in memory, regardless of the specified compressed data width, to maximize the use of memory.
  • two different word formats are used for compressed data: (1) a compressed data format for partitioned blocks determined to be color variant; and (2) a compressed data format for partitioned blocks determined to be color invariant.
  • Color variant blocks are encoded with high edge acuity and reduced color fidelity, while color invariant blocks are encoded with high color fidelity.
  • the most significant bit in both the color variant data block and the color invariant data block referred to as the select (S) bit, identifies the compressed block as being either color variant or color invariant (that is, non-variant).
  • a non-variance compressed data block is used to encode the pixels in a partitioned block where all pixels have the same color (see Figure 4d).
  • the user can specify the number of bits used to describe each color component of the single color associated with the color invariant block of pixels.
  • the number of bits used to define each color component in conjunction with the number of color components selected by the user to represent each pixel, will define the bits of a non-variance compressed data block.
  • the number of bits used to describe the color of a color invariant block must be at least one bit less than the total number of bits available to describe each compressed data block of pixels (that is, 31 in the above example) to account for the select bit.
  • the user can select any of three different sets of color components; that is, (1) cyan, magenta, yellow and black; (2) cyan, magenta and yellow; or (3) a single color component.
  • three different types of non-variance compressed data blocks can be used, as illustrated in Figures 4a, 4b and 4c.
  • a different number of bits can be used to represent the color components without exceeding the 31 bit limit of the exemplary embodiment.
  • any number of bits can be used to represent the black component of Figure 4c.
  • the Figure 4c format can also be used where only the yellow, magenta or cyan color component has been selected to represent non- variant blocks.
  • any number of bits for example, 7-bits
  • the total word length, including the select bit would be 29-bits.
  • a color variant compressed data block used to represent partitioned blocks that include pixels of various colors, is illustrated in Figure 5a.
  • An alternate embodiment of a color variant compressed data block is illustrated in Figure 5b.
  • These data formats include: (1) a predetermined number of indexed color locations; and (2) a mask for mapping each pixel of the partitioned, color variant block to one of the indexed colors.
  • each partitioned block is pre-processed to include at most two different colors; the two colors for a given data block are, in an exemplary embodiment, represented in the compressed data blocks of Figures 5a and 5b as 6-bit color indices for a first color (CO) and a second color (Cl).
  • the 6-bit values for CO and Cl, included within the variance compressed data block serve as indices for searching a variance color look-up table.
  • the variance color look-up table stores a plurality of 32-bit color values in 64 locations, with a specific location being addressed by the values of CO and Cl.
  • the first entry in the variance color look ⁇ up table can correspond to white and the last entry can correspond to black. All data entries in between correspond to various colors ranging from white to black, (that is, colors having varying amounts of the cyan, magenta, yellow and black color components).
  • the color variant compressed data block includes: a single bit location for the select bit; a 6-bit location for the color CO; a 6-bit location for the color Cl; and a 16-bit mask wherein each bit corresponds to one pixel of the 4-by-4 block.
  • Figure 5b illustrates the use of a compressed mask which serves as an index to a compression mask look-up table where a complete mask is stored.
  • a compressed mask will be referenced herein as a mask index.
  • the compression mask look-up table which is pointed to by a mask base register, is included in memory.
  • the 16 bit mask obtained from a 4-by-4 partitioned block can be used to index the compression mask look-up table which, in an exemplary embodiment, is a 64k entry table.
  • each location in the mask look ⁇ up table stores two compressed masks, such that the table is actually configured in memory as a 32k-entry-by-32 bit table (note that multiple non-compressed masks can be mapped to the same compressed mask, if desired).
  • the mask base register points to a Ik decompression mask look-up table, which in an exemplary implementation, is actually configured as a 512 entry memory wherein each entry includes two decompressed masks.
  • Figure 5c illustrates an exemplary embodiment of a 16 bit mask.
  • the numbers shown in each of the Figure 5c bit locations illustrate the manner by which the 16-bit mask maps to pixel locations of the 4-by-4 partitioned block illustrated in Figure 5d.
  • the 16 bit mask With the data format of Figure 5a, the 16 bit mask is stored, in its entirety, within the compressed data block. However, with the data format of Figure 5b, the 16 bit mask is stored in the compression mask look-up table pointed to by the mask base register and addressed by the mask index included in the compressed data block.
  • Figure 5e illustrates an example wherein the binary values of a 16 bit mask in a color variant compressed data block map either the color CO or the color Cl to each of the pixel locations of the 4-by-4 partitioned block.
  • a value of 0 at any given location of the 16-bit mask can be considered to correspond to the color CO
  • a 1 at any of the 16-bit locations in the 16-bit mask can be considered to correspond to the color Cl.
  • a 16-bit mask having the binary values illustrated in the left hand side of Figure 5e will map the colors CO and Cl to the pixel locations shown in the right hand side of Figure 5e.
  • the CO and Cl values can, in an exemplary embodiment, also be stored as compressed values within the compressed data block of Figures 5a and 5b.
  • an additional encoding table can be provided to expand the compressed CO and Cl values to an address for the variance color look-up table.
  • color invariant compressed data blocks can use the 29-bit data block to represent a single color and thereby preserve high color fidelity.
  • the exemplary color variant compressed data blocks use an exemplary 6-bit color index (that is, CO or Cl) to select a 32-bit color value from a 64 entry variance color look-up table. Because only 6-bits are used to represent a color, all colors extant throughout the world must be represented by the 64 colors included in the variance color look-up table. As described previously, color fidelity of color variant blocks is therefore sacrificed to preserve high edge acuity and reduce memory requirements. Recall that high edge acuity is obtained by encoding each of 16 pixels in a block with one of at least two different colors is used to define edges in the image.
  • acuity can be preserved in partitioned blocks which include edge information
  • high color fidelity can be preserved in partitioned blocks which are color invariant (that is, blocks which do not include edge information).
  • color fidelity of color variant data blocks could easily be improved by increasing the number of bits used for each color index CO and Cl (thereby increasing the number of 32-bit color entries included in the variance color look-up table)
  • an increased width of the color variant data block would sacrifice processing speed to such an extent that real-time processing of an incoming data stream could become prohibited.
  • a goal of exemplary embodiments described herein is to optimize color fidelity of decompressed images generated from color variant data blocks while keeping the overall width of color variant data blocks (for example 29- bits) comparable to that of color invariant data blocks.
  • a method and apparatus are provided for encoding the seemingly infinite array of different colors using only the 64 entries of the variance color look-up table.
  • the 64 entries are chosen in a manner which optimizes color fidelity of an image that is reproduced from the color variant compressed data blocks.
  • Figure 4a illustrates uncompressed image data representing at least one color component of a monochrome or color image for an exemplary pixel of a pixmap.
  • each of four color components used to represent the pixel can be encoded with 8-bits.
  • 8 bits are used to represent each of cyan (C), magenta (M), yellow (Y) and black (K) color components, such that a total of thirty-two bits are used to represent a single pixel of color data.
  • the color variant compressed data blocks of Figures 5a and 5b represent each pixel in a partitioned block of pixels (for example, 16 pixels) with one of two 6-bit color indices. All colors known to exist are therefore reduced to one of sixty-four 32-bit color entries stored in the variance color look-up table so that a decompressed 32-bit representation of color can be obtained for each pixel using the 6-bit index. In other words, the original 32-bits used to represent the color of each pixel in an input stream of image data are reduced to a 6-bit representation.
  • Figure 4a illustrates a 32-bit color as having four 8-bit components
  • the 32-bits can be used to represent single color components (for example, grey scale images, or images formed of different shades of the same color).
  • the 32-bits can be separated among the designated color components, in any desired manner. For example, a greater (fewer) number of bits can be used to represent a fewer (greater) number of color components.
  • CMYK values are shown, those skilled in the art will appreciate that any known color space can be used (for example, RGB values).
  • the encoded color indices are obtained from an exemplary 512 entry C0/C1 encoding table that is addressed by a 9-bit value.
  • the 9-bit value used to address the C0/C1 encoding table is, in an exemplary embodiment, obtained from the 32-bit color value of the pixel by first dropping the four least significant bits of the cyan, magenta and yellow color components, leaving 20 bits. A predetermined combination of 9-bits is then selected from among these 20-bits.
  • the 9-bits selected can be varied (that is, programmed) as desired based on any user specified criteria.
  • Figures 5a represents a means for compressing the quantized image data within each partitioned block, and can, in an exemplary embodiment, be included as a hardware device in the compression /decompression coprocessor 108 of Figure 1.
  • the 32-bits of the image data for the single pixel shown in Figure 4a are illustrated as input values Y0-Y7, M0-M7, C0-C7 and K0-K7, corresponding to each of the yellow, magenta, cyan and black color components, respectively.
  • These 32 bits are supplied as the input to a means, such as a selector 502, for prequantizing at least one color component of the image data by selectively eliminating predetermined bits used to represent at least one color component of a single pixel.
  • the selector 502 can be a 20-bit-to- 9-bit barrel shifter which receives inputs from 20 predetermined bit locations of the 32-bit image data. These 20 predetermined bit locations can be fixed in advance by the user, and reconfigured as desired. In the exemplary Figure 5a embodiment, the 20 selected bit locations include the four most significant bits used to represent each of the yellow, magenta and cyan color components. By also retaining the 8-bits of the black color component in the exemplary embodiment illustrated, all 256 shades of grey can be retained and used to control the black toner of a monochrome printer.
  • the resultant bit locations received by the barrel shifter 502 are illustrated in Figure 4b, wherein portions of the color pixel lost after this initial compression are shaded.
  • the barrel shifter further prequantizes the image data by reducing the 20 selected bits to a 9-bit value.
  • the 9-bits which are selected can, for example, be the three most significant bits for black, and the two most significant bits for each of the cyan, magenta and yellow color components.
  • any combination of the bits can be used, such as the first, fourth and last bit of the black color component, and the first and fourth remaining bits of the cyan, magenta and yellow color components, or any other combination of bits.
  • the hardware barrel shifter thus functions as an interconnected matrix that can be altered by the user as desired (for example, on a page-by-page basis), or in response to any user selected criteria.
  • software or any combination of hardware and software can be used to implement the selection process.
  • the 32-bit image data is thus selectively prequantized to encode the 32-bit input for each pixel as a 9-bit value.
  • This prequantization achieves a seventy-two percent reduction in going from a 32-bit color pixel to a 9-bit color pixel.
  • the remaining 9-bits of prequantized image data are encoded to further compress the image data.
  • the 9-bit output of the barrel shifter is used to address the C0/C1 encoding table 504 of Figure 5a which, in an exemplary embodiment, includes 512 entries. Each 9-bit address to the C0/C1 encoding table produces a 6-bit output which can be used as a color index.
  • a color index can be generated for each pixel.
  • a partitioned block includes 16 pixels
  • 16 color indices can be generated from which CO and Cl can be selected.
  • CO and Cl can be selected using any technique described herein.
  • the first two colors detected in a partitioned block can be selected for use in generating CO and Cl via the two- level compression described herein, with either CO or Cl being used to represent the color of all pixels included in the partitioned block.
  • the encoding of a 6-bit color index from a 9-bit value involves mapping each of the 9-bit values to one of the 64 colors in the variance color look-up table, represented as variance color look-up table 506 of Figure 5a. This mapping can be achieved in any known fashion.
  • empirical data can be acquired to identify the most visually pleasing color representation to be stored in the variance color look-up table based on colors expected to be present in the input image data.
  • the colors stored in the variance color look-up table can thus be selected wholly independent of the original 32-bit colors values included in pixels of the incoming image data.
  • a color stored in the variance color look-up table can be a color located in the CMYK color space midway between two colors which are expected to be received by the selector 502.
  • the variance color look-up table if only a limited number of colors are known in advance to be included in the original image data, then these colors can be stored in the variance color look-up table. For example, if the image data to be processed is known in advance to be limited to red, green and brown, then 31 shades for each of red, green and brown can be stored in the variance color look-up table and all of the 9-bit values can be mapped to one of these colors. Alternately, only dominant colors known in advance to be included in the image data can be stored in the variance color look-up table, and all 9-bit values mapped to one of the stored values.
  • Figure 5b illustrates an alternate embodiment wherein the first and second steps of prequantization described with respect to Figure 5a are implemented by directly selecting a set number of bits (for example, 9-bits to be consistent with the Figure 5a example).
  • the set number of bits is then encoded to compress the prequantized data into a color index (for example, a 6-bit color index) used to address the variance color look-up table.
  • the flexibility associated with exemplary embodiments described herein can be exploited such that the dominant colors included within any frame of image data are dynamically identified on a page-by-page basis. Based on this identification, the selector, the C0/C1 encoding table and/or the variance color look-up table can be modified. Alternately, a different C0/C1 encoding table and/or variance color look-up table can be selected for compression based on the dominant colors identified. In other words, the colors that best represent a given frame can be used in conjunction with the compression of image data associated with that frame.
  • Figure 5c illustrates an exemplary embodiment where the prequantization of Figure 5b results in a user-configured selection of 1-bit of cyan and all 8-bits of black.
  • a two level color encoding in accordance with exemplary embodiments provides a relatively high level of color fidelity for partitioned blocks of image data which include edge information. Further, a two level color encoding which includes a single encoding table (that is, the exemplary 512 entry C0/C1 encoding table), provides high speed compression suitable for real-time processing.
  • Exemplary embodiments of the present invention therefore provide the user a high degree of flexibility by allowing for the arbitrary selection of many combinations of C,M,Y and K image data.
  • the selector can be used to quickly reduce the input-image data in a manner which does not inhibit adaptability to any user-specific criteria. Further, the selector generates an output (the exemplary 9-bit value) that can address an encoding table, the output of the encoding table being an index which represents a color that may have no relationship to the original 32-bit color data.
  • an output the exemplary 9-bit value
  • the output of the encoding table being an index which represents a color that may have no relationship to the original 32-bit color data.
  • exemplary embodiments of the present invention for compressing color variant data can, if desired, be used in connection with compression of any image data in any format.
  • exemplary embodiments of the invention as described with respect to color variant data blocks can equally be used for color invariant data blocks to reduce the data required to represent a single color invariant data block.
  • exemplary embodiments of compressing color variant image data in accordance with exemplary embodiments can be used for any environment including printing, video display and so forth.
  • Figure 6 illustrates a more detailed diagram of the exemplary compression/ decompression coprocessor 108.
  • the compression/decompression coprocessor 108 is interfaced to the system bus 110 via a bus interface unit 402.
  • the compression/decompression coprocessor 108 includes a compression engine 404 and a decompression engine 406.
  • the decompression engine 406 is used during the compression process. Recall that an entire frame of image data is not stored and processed at a single time, but rather is processed sequentially through the decompressed data frame buffer.
  • the decompression engine of the compression/decompression coprocessor accommodates a situation where newly received image data is to be superimposed on portions of the frame which have been earlier compressed. In this situation, the earlier data is decompressed, and placed back into a frame buffer where it is overlaid with the incoming decompressed data. The later portion of the frame is therefore superimposed on the earlier processed data.
  • a scratch pad and data path block 410 is also provided and includes, among other features, resources such as registers and look-up tables used during operation of the compression /decompression coprocessor.
  • the scratch pad and data path block 410 includes an input/output first- in, first-out (I/O FIFO) buffer 412 for buffering information of the compression/decompression coprocessor.
  • a decompression data frame buffer 414 (DD frame buffer) is also included, and is a double-buffered memory (as are most of the internal buffers). As one buffer of the DD frame buffer becomes full, the compression/ decompression coprocessor can access data from that buffer while the bus interface unit 402 begins to fetch and load incoming image data to the other buffer.
  • the look-up tables 416 of the scratch pad and data path block 410 include the 64-entry variance color look-up table and the C0/C1 encoding look-up table.
  • the variance color look-up table stores the limited range of colors used to describe partitioned blocks which are determined to be color variant (recall that a compression technique of the present invention encodes color variant blocks with reduced color fidelity).
  • the C0/C1 encoding look-up table includes encoded values for CO and Cl.
  • the compression and decompression mask look-up tables are also stored in memory 104 ( Figure 1). As will be apparent to those skilled in the art, all of these tables can be included in a single memory, or can be stored in separate memories.
  • a barrel shifter assembly /disassembly unit 418 is also included in the scratch pad and data path block.
  • the number of bits in a compressed data word can be less than the number of bit locations allocated to each word in memory.
  • 29 bits are used to represent a partitioned block in compressed form, while exemplary words in memory are 32 bits.
  • the compressed data words are loaded one next to the other in memory (that is, all 32 bits of each word location in memory are used to store compressed image data). Therefore, to provide accurate read-out of compressed data, barrel shifting is used to shift a compressed data word in memory before each field of that word is extracted.
  • An address generator unit 420 is also included in the scratch pad and data path block. The address generator accesses locations of the various registers and look-up tables included within the compression /decompression coprocessor.
  • the control registers 422 include an identification (ID) register for storing system revision and identification information.
  • ID identification
  • a vector table pointer register is accessed to identify the locations in memory where compressed and decompressed image data is stored for a given row of partitioned blocks.
  • a separate plane in memory is used for each of the cyan, magenta, yellow and black color components, as illustrated in Figure 7.
  • the vector register table includes a cyan pointer register, a magenta pointer register, a yellow pointer register and a black pointer register.
  • the vector register table also includes a side information pointer register and a compressed data pointer register. Each color component is represented by 8-bits which identify one of up to 256 values for each color component.
  • the mask base register and the C0/C1 encoding select register are accessed. These registers map the original 32-bit color in a color variant partitioned block of each pixel to colors included in the reduced color look-up table (that is, the exemplary 64 entry variance color look-up table).
  • the horizontal total pixel count register, and the vertical total pixel count register which store values representing the total number of pixels in each row and in each column, respectively of an incoming frame of image data, are also included in the registers 422.
  • a vertical offset register can also be included to store an address offset between vertically adjacent pixels in an image to accommodate use of a one-dimensional memory for storing a two- dimensional image.
  • Other registers are included for interrupt, enable and acknowledgement, command, operation status, and test functions.
  • the compression operation is implemented using both hardware and software.
  • the decompression functions of an exemplary embodiment are primarily implemented in hardware.
  • the decompressor functions implemented in an exemplary compression/ decompression coprocessor are, for the most part, identical to those of the video interface device 112 ( Figure 1).
  • Figure 8 which illustrates exemplary hardware processing included within the video interface device, will therefore be used to describe the exemplary hardware decompression of the compression /decompression coprocessor.
  • decompression is initiated by fetching compressed data in the form of compressed data blocks from memory locations identified by a compressed data pointer register.
  • the compressed data blocks are loaded into the compressed data input first-in first-out memory 602, non-variance data being loaded from locations identified by the vector table pointer register to accommodate the use of different color planes in memory.
  • compressed data blocks can span word boundaries of memory, two compressed data blocks (that is, two data words) are loaded into a 64-bit register 604 and barrel shifted to the right by an amount indicated by the specified width of a compressed data word before each color field is extracted.
  • a field extraction unit 606 then extracts each color field of the compressed data word.
  • the compressed data block is of the non-variance type, then up to the four color components previously mentioned are extracted. If the compressed data block is of the variance type, then the mask is extracted along with the CO and Cl values. Color fields which are less than 8- bits wide are replicated to an 8-bit width to provide, for four color printing, a 32-bit compressed data block.
  • mask look-up is performed if a mask compression mode had been selected. If mask look-up is required, the Ik entry decompression mask look-up table 608 is searched using the compressed mask look-up index.
  • a color look-up for the colors CO and Cl is performed using the variance color look-up table, if required.
  • CO and Cl are 0-extended to a full six bits before searching the variance color look ⁇ up table 610.
  • the 6-bit input to the variance color look-up table 610 is selected by a selector 612, which in accordance with an exemplary embodiment corresponds to the multiplexers and row and column counters of Figure 9.
  • a 2-to-l multiplexer 702 receives both a non- compressed 16-bit mask from the compressed data block, or a 16-bit output from the mask look-up table.
  • a mode select input 704 to the multiplexer 702 identifies whether a compressed mask has been used so that the appropriate input to the multiplexer 702 can be selected and output to a 16-to-l multiplexer 706.
  • the output from the multiplexer 706 is selected by the bits from the row and column counters used to identify a given row and column in a partitioned block of pixels.
  • the row and column counters are labelled counters 708 and 710 in Figure 9, respectively.
  • the output from the multiplexer 706 corresponds to a single pixel within a partitioned block of pixels, and identifies whether the color associated with the pixel is CO or Cl.
  • the output from the multiplexer 706 is used as a select input to a 2-to-l multiplexer 712 for selecting either the 6-bit index for identifying the color CO or the 6-bit index for identifying the color Cl.
  • the selected 6-bit output from the multiplexer 712 is used as a look-up address for the variance color look-up table 610 of Figure 8, and thereby produces a 32-bit color output corresponding to the decompressed color CO or Cl.
  • the 32-bit output from the variance color look-up table is supplied to a multiplexer 614.
  • the multiplexer 614 also receives a 32-bit input directly from the field extraction unit to accommodate decompressed data blocks of the non- variance type.
  • a select line 616 to the multiplexer 614 corresponds to the select bit which identifies whether the partitioned block of pixels is of the variance type or the non- variance type. Depending on the binary state of this select bit, either the 32-bit data output directly from the field extraction unit 606 is selected or, in the case of a variance type block, a 32-bit output from the variance color look-up table 610 is selected. This process is repeated for each pixel of a partitioned block.
  • Figure 8 also illustrates the supply of address and data information to each of the look-up table 608, the variance color table 610, a threshold matrix 622 and a video modulation look-up table 622.
  • address and data lines are used to store data in these tables and to read data therefrom during testing, if desired.
  • aspects of features provided in the exemplary Figure 8 embodiment such as grey component removal 618, threshold matrix 620 and video modulation look-up table are not necessary to understanding the present invention. For more detail regarding exemplary embodiments of these features, as well as a more detailed discussion of operation of the Figure 8 embodiment, reference is made to the aforementioned commonly assigned U.S. Application Serial No. 08/397,372.
  • the video interface device can be used for decompressing data such that it can be output to, for example, a display or printer.
  • Features included in the video interface device for decompressing the image data duplicate features included within the decompression engine of the compression/ decompression coprocessor 108. Any additional features of the video interface device which do not duplicate structure and function of the compression /decompression coprocessor are outside the scope of the present invention and need not be described in detail. Rather attention is directed to the aforementioned commonly assigned U.S. Application Serial No. 08/397,372 for a more detailed discussion of an exemplary video interface device suitable for use with the exemplary embodiments of the present invention.
  • partitioned blocks described above can be of any dimension. Further, the partitioning can be adaptive and dynamic, even within a given frame of image data, with the only requirement being that dimensional information be made known to the decompression process.
  • Exact dimensions of compressed and decompressed data blocks can also be modified as desired by the user, and the 29-bit value for compressed data blocks is by way of example only. Further, the compressed data and decompressed data block size need not remain fixed, but could be varied from block-to-block. Encoded variant and invariant block sizes can also be different from one another.
  • the color palette can be dynamically assigned as long as the update information is part of the compressed data storage or stream.
  • variant blocks as described in the exemplary embodiment above are encoded as a 1-bit mask with two sub-palettes of a larger color palette, those skilled in the art will appreciate that masks of any size can be used. For example, a mask of 3-bits for each pixel can be used, with each 3-bits pointing to a palette or sub-palette of eight color values.
  • invariant blocks need not correspond to blocks where all pixels have the same value. Rather, blocks with pixels that fall within an acceptable range can be mapped into an invariant color block, using a value that represents the entire block, with no visible degradation.
  • the variant and non-variant select indicator bit for each block need not be specifically encoded.
  • the selector bit can be further compressed.
  • the selector bit can be encoded in run length fashion.
  • known compression techniques can be used in conjunction with the compression techniques of the present invention. For example, two successive non-variant blocks can be encoded using a repeat flag, without having to encode the full information for the second and successive blocks. Further, where successive non-variant blocks differ only slightly from a preceding non-variant block, the known compression technique of delta modulation can be used to further compress the data. This use of such known compression techniques in accordance with the present invention is by way of illustration only, and any number of known compression techniques can be used in accordance with the present invention to improve compression. Further, while compression has been described with respect to all components of a given pixel at one time, those skilled in the art will appreciate that the color components can be compressed separately.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Compression Of Band Width Or Redundancy In Fax (AREA)

Abstract

L'invention concerne des systèmes et des procédés qui s'appliquent à la compression de données d'images et, partant, à la vitesse de compression, au rapport de compression (c'est-à-dire à la réduction des besoins en mémoire) et à la perceptibilté de l'image décomprimée, même lorsque les données d'images sont comprimées sans ségrégation en composantes balayées et non balayées par scanner. A titre d'exemple, on décrit des variantes qui permettent d'obtenir une perceptibilité améliorée indépendemment du type d'image: monochrome (avec diverses valeurs de l'échelle des gris) ou en couleur. De plus, la perceptibilité améliorée est obtenue d'une manière permettant de comprimer en temps réel des données d'images incluant les images balayées et/ou non balayées.
PCT/US1996/008489 1995-06-05 1996-06-03 Classification par blocs pour acelerer la compression des donnees d'images WO1996039682A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU62514/96A AU6251496A (en) 1995-06-05 1996-06-03 Block classification for accelerating image data compression

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US46262695A 1995-06-05 1995-06-05
US08/462,626 1995-06-05

Publications (1)

Publication Number Publication Date
WO1996039682A1 true WO1996039682A1 (fr) 1996-12-12

Family

ID=23837137

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1996/008489 WO1996039682A1 (fr) 1995-06-05 1996-06-03 Classification par blocs pour acelerer la compression des donnees d'images

Country Status (2)

Country Link
AU (1) AU6251496A (fr)
WO (1) WO1996039682A1 (fr)

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001035340A1 (fr) * 1999-11-09 2001-05-17 Creo Products, Inc. Systeme et procede destine a la compression d'image
EP1189170A1 (fr) * 2000-09-12 2002-03-20 Pace Micro Technology Ltd Compression de données d'images en trame de points
US7075681B1 (en) 1999-11-09 2006-07-11 Kodak Graphic Communications Canada Company System and method for reducing the data volume of images
AU2007249103B2 (en) * 2007-12-05 2011-05-12 Canon Kabushiki Kaisha Document analysis method
US8532374B2 (en) 2007-12-05 2013-09-10 Canon Kabushiki Kaisha Colour document layout analysis with multi-level decomposition
WO2014158203A1 (fr) * 2013-03-28 2014-10-02 Intuit Inc. Procédé et système pour créer des images optimisées pour l'identification et l'extraction de données
CN112073726A (zh) * 2020-09-11 2020-12-11 Oppo广东移动通信有限公司 压缩方法及装置、计算机可读存储介质及电子设备

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS59219071A (ja) * 1983-05-26 1984-12-10 Fujitsu Ltd 画像符号化伝送方式
JPS6097777A (ja) * 1983-11-01 1985-05-31 Nec Corp フアクシミリ装置
EP0402016A2 (fr) * 1989-06-01 1990-12-12 AT&T Corp. Codage/décodage pour la décomposition et la recomposition d'une image haute-résolution
JPH0342969A (ja) * 1989-07-10 1991-02-25 Canon Inc カラー画像情報符号化方式
WO1994006098A1 (fr) * 1992-09-01 1994-03-17 Apple Computer, Inc. Pretraitement et post-traitement ameliores pour une quantification de vecteurs

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS59219071A (ja) * 1983-05-26 1984-12-10 Fujitsu Ltd 画像符号化伝送方式
JPS6097777A (ja) * 1983-11-01 1985-05-31 Nec Corp フアクシミリ装置
EP0402016A2 (fr) * 1989-06-01 1990-12-12 AT&T Corp. Codage/décodage pour la décomposition et la recomposition d'une image haute-résolution
JPH0342969A (ja) * 1989-07-10 1991-02-25 Canon Inc カラー画像情報符号化方式
WO1994006098A1 (fr) * 1992-09-01 1994-03-17 Apple Computer, Inc. Pretraitement et post-traitement ameliores pour une quantification de vecteurs

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
CHADDHA N ET AL: "Text segmentation in mixed-mode images", CONFERENCE RECORD OF THE TWENTY-EIGHTH ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS AND COMPUTERS (CAT. NO.94CH34546), PROCEEDINGS OF 1994 28TH ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS AND COMPUTERS, PACIFIC GROVE, CA, USA, 31 OCT.-2 NOV. 1994, ISBN 0-8186-6405-3, 1994, LOS ALAMITOS, CA, USA, IEEE COMPUT. SOC. PRESS, USA, pages 1356 - 1361 vol.2, XP000533866 *
PATENT ABSTRACTS OF JAPAN vol. 009, no. 089 (E - 309) 18 April 1985 (1985-04-18) *
PATENT ABSTRACTS OF JAPAN vol. 009, no. 248 (E - 347) 4 October 1985 (1985-10-04) *
PATENT ABSTRACTS OF JAPAN vol. 015, no. 179 (E - 1064) 8 May 1991 (1991-05-08) *

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001035340A1 (fr) * 1999-11-09 2001-05-17 Creo Products, Inc. Systeme et procede destine a la compression d'image
US7075681B1 (en) 1999-11-09 2006-07-11 Kodak Graphic Communications Canada Company System and method for reducing the data volume of images
EP1189170A1 (fr) * 2000-09-12 2002-03-20 Pace Micro Technology Ltd Compression de données d'images en trame de points
AU2007249103B2 (en) * 2007-12-05 2011-05-12 Canon Kabushiki Kaisha Document analysis method
US8532374B2 (en) 2007-12-05 2013-09-10 Canon Kabushiki Kaisha Colour document layout analysis with multi-level decomposition
WO2014158203A1 (fr) * 2013-03-28 2014-10-02 Intuit Inc. Procédé et système pour créer des images optimisées pour l'identification et l'extraction de données
US8923619B2 (en) 2013-03-28 2014-12-30 Intuit Inc. Method and system for creating optimized images for data identification and extraction
CN112073726A (zh) * 2020-09-11 2020-12-11 Oppo广东移动通信有限公司 压缩方法及装置、计算机可读存储介质及电子设备

Also Published As

Publication number Publication date
AU6251496A (en) 1996-12-24

Similar Documents

Publication Publication Date Title
US6115496A (en) Method and apparatus for accelerating image data compression
US5805735A (en) Method and apparatus for compression of digitized image data using variable color fidelity
US6016360A (en) Method and apparatus for encoding color image data
US5930387A (en) Method and apparatus for encoding color image data using dynamic color matching
US5768481A (en) Method and apparatus for compression of digitized image data using a dynamic band recompression scheme
US5917962A (en) Method and apparatus for partitioning an image
EP2481206B1 (fr) Appareil de traitement d'image et procédé de traitement associé
EP0235456B1 (fr) Appareil et méthode de traitement d'image utilisant des blocs de données comprimées
US5838333A (en) Image processing device and image processing method
EP0671845A2 (fr) Procédé de compression et de décompression d'images multidimensionnelles
WO1994000949B1 (fr) Compression et decompression video effectuees au moyen de la selection et de la subdivision de blocs
US6744919B2 (en) Classification of blocks for compression based on number of distinct colors
US6130630A (en) Apparatus and method for compressing Huffman encoded data
US4953104A (en) Page buffer for an electronic gray-scale color printer
US7075681B1 (en) System and method for reducing the data volume of images
JP2830690B2 (ja) 画像処理装置
WO1996039682A1 (fr) Classification par blocs pour acelerer la compression des donnees d'images
EP0683599A1 (fr) Appareil et procédé de traitement d'images
JPH0772839A (ja) カラービデオディスプレイ装置
JP3514050B2 (ja) 画像処理装置
US6917704B2 (en) Image processing method, image processing apparatus and image processing system
EP1289271A2 (fr) Identification de la couleur prédominante dans des images numériques
JP3781843B2 (ja) バイナリイメージを無損失事前圧縮する方法
JP3211545B2 (ja) 画像処理装置
US5751858A (en) Moving picture coding apparatus

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AL AM AT AU AZ BB BG BR BY CA CH CN CZ DE DK EE ES FI GB GE HU IL IS JP KE KG KP KR KZ LK LR LS LT LU LV MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK TJ TM TR TT UA UG UZ VN AM AZ BY KG KZ MD RU TJ TM

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): KE LS MW SD SZ UG AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE BF BJ CF CG CI CM GA GN

121 Ep: the epo has been informed by wipo that ep was designated in this application
REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: CA

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载