Coded data generation or conversion – Digital code to digital code converters – To or from run length limited codes
Reexamination Certificate
2001-03-30
2002-12-10
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from run length limited codes
C341S050000, C382S239000
Reexamination Certificate
active
06492916
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of compression and decompression; more particularly, the present invention relates to having a context model that is capable of generating multiple contexts of which one context is selected for use in coding.
BACKGROUND OF THE INVENTION
Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a facsimile transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to represent the image.
Many different data compression techniques exist in the prior art. Compression techniques can be divided into two broad categories, lossy coding and lossless coding. Lossy coding involves coding that results in the loss of information, such that there is no guarantee of perfect reconstruction of the original data. The goal of lossy compression is that changes to the original data are done in such a way that they are not objectionable or detectable. In lossless compression, all the information is retained and the data is compressed in a manner which allows for perfect reconstruction.
In lossless compression, input symbols or intensity data are converted to output codewords. The input may include image, audio, one-dimensional (e.g., data changing spatially), two-dimensional (e.g., data changing in two spatial directions), or multi-dimensional/multi-spectral data. If the compression is successful, the codewords are represented in fewer bits than the number of bits in the “normal” representation of the input symbols (or intensity data). Lossless coding methods include dictionary methods of coding (e.g., Lempel-Ziv), run length encoding, enumerative coding and entropy coding. In lossless image compression, compression is based on predictions or. contexts, plus coding. The JBIG standard for facsimile compression and DPCM (differential pulse code modulation—an option in the JPEG standard) for continuous-tone images are examples of lossless compression for images. In lossy compression, input symbols or intensity data are quantized prior to conversion to output codewords. Quantization is intended to preserve relevant characteristics of the data while eliminating unimportant characteristics. Prior to quantization, lossy compression system often use a transform to provide energy compaction. JPEG is an example of a lossy coding method for image data.
Reversible transforms (wavelet, component) may be used for both lossy and lossless compression. Irreversible transforms (wavelet, component, discrete cosine) may be used only for lossy.
The new JPEG 2000 decoding standard utilizes transforms and provides a new coding scheme and codestream definition for images. Although JPEG 2000 is a decoding standard, and thus defines what a decoder must do, this definition restricts an encoder especially for lossless compression. Under the JPEG 2000 Standard, each image may be divided into rectangular tiles. If there is more than one tile, the tiling of the image creates tile-components. An image may have multiple components. For example, a color image might have red, green and blue components. Tile-components can be extracted or decoded independently of each other.
After tiling of an image, the tile-components are decomposed into one or more different decomposition levels using a wavelet transformation. These decomposition levels contain a number of subbands populated with coefficients that describe the horizontal and vertical spatial frequency characteristics of the original tile-components. The coefficients provide frequency information about a local area, rather than across the entire image. That is, a small number of coefficients completely describe a single sample. A decomposition level is related to the next decomposition level by a spatial factor of two, such that each successive decomposition level of the subbands has approximately half the horizontal resolution and half the vertical resolution of the previous decomposition level.
Although there are as many coefficients as there are samples, the information content tends to be concentrated in just a few coefficients. Through quantization, the numerical precision of a number of coefficients may be reduced with a disproportionately low introduction of distortion (quantization noise). Additional processing by an entropy coder reduces the number of bits required to represent these quantized coefficients, sometimes significantly compared to the original image.
The individual subbands of a tile-component are further divided into code-blocks. These code-blocks can be grouped into precincts. These rectangular arrays of coefficients can be extracted independently. The individual bit-planes of the coefficients in a code-block are entropy coded with three coding passes. Each of these coding passes collects contextual information about the bit-plane compressed image data.
The bit stream compressed image data created from these coding passes is grouped in layers. Layers are arbitrary groupings of successive coding passes from code-blocks. Although there is great flexibility in layering, the premise is that each successive layer contributes to a higher quality image. Code-blocks of subband coefficients at each resolution level are partitioned into rectangular areas called precincts.
Packets are a fundamental unit of the compressed codestream. A packet contains compressed image data from one layer of a precinct of one resolution level of one tile-component. These packets are placed in a defined order in the codestream.
The codestream relating to a tile, organized in packets, are arranged in one, or more, tile-parts. A tile-part header, comprised of a series of markers and marker segments, or tags, contains information about the various mechanisms and coding styles that are needed to locate, extract, decode, and reconstruct every tile-component. At the beginning of the entire codestream is a main header, comprised of markers and marker segments, that offers similar information as well as information about the original image.
The codestream is optionally wrapped in a file format that allows applications to interpret the meaning of, and other information about, the image. The file format may contain data besides the codestream.
The decoding of a JPEG 2000 codestream is performed by reversing the order of the encoding steps.
FIG. 1
is a block diagram of the JPEG 2000 standard decoding scheme that operates on a compressed image data codestream. Referring to
FIG. 1
, a bitstream initially is received by data ordering block
101
that regroups layers and subband coefficients. Arithmetic coder
102
uses contextual information from previously coded coefficients provided by the bit modeling block
103
about the bit-plane compressed image data, and its internal state, to decode a compressed bit stream.
Next, the codestream is quantized by quantization block
104
, which may be quantizing based on a region of interest (ROI) as indicated by ROI block
105
. After quantization, an inverse wavelet/spatial transform is applied to the coefficients via transform block
107
, followed by DC level shifting and optional component transform block
108
. This results in generation of a reconstructed image.
SUMMARY OF THE INVENTION
A method and apparatus for generating multiple selectable contexts is described. In one embodiment, the method comprises generating two contexts, one of the two contexts for when the current bit being decoded is a zero bit and the other of the two context for when the current bit being decoded is a one bit indicating that a coefficient has become significant, selecting one of the two context to use to decode a bit subsequent to the current bit, wherein selecting the one context is based on the current bit once decoded, and decoding the bit subsequent to the current bit using the one context.
REFERENCES:
patent: 5471207 (1995-11-01), Zandi et al.
patent: 5694128 (1997-12-01), Kim
patent: 5970174 (1999-10-01), Peters
patent: 6222468 (2001-04-01), Alle
Gormish Michael J.
Schwartz Edward L.
Blakely , Sokoloff, Taylor & Zafman LLP
Jean-Pierre Peguy
Ricoh Co. Ltd.
LandOfFree
Method and apparatus for generating multiple selectable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating multiple selectable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating multiple selectable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2935894