Error reduction in transformed digital data

Details Error reduction in transformed digital data Error reduction in transformed digital data

1998-11-04

2002-05-21

Au, Amelia M. (Department: 2623)

Image analysis

Image compression or coding

Transform coding

C375S240170, C375S240180

Reexamination Certificate

active

06393155

ABSTRACT:

CROSS REFERENCES
The present application is related to the following applications even dated herewith: Ser. No. 09/186,247, entitled, “Reduced-error processing of transformed digital data,” by inventors M. Bright et al., and Ser. No. 09/186,245, entitled, “Transform-domain correction of real-domain errors,” by inventors J. Mitchell et al., which are incorporated herein in entirety by reference.
FIELD OF THE INVENTION
This invention relates to transform coding of digital data, specifically to real domain processing of transform data. More particularly, this invention relates to reduced-error digital processing of inverse transformed data.
BACKGROUND OF THE INVENTION
Transform coding is the name given to a wide family of techniques for data coding, in which each block of data to be coded is transformed by some mathematical function prior to further processing. A block of data may be a part of a data object being coded, or may be the entire object. The data generally represent some phenomenon, which may be for example a spectral or spectrum analysis, an image, an audio clip, a video clip, etc. The transform function is usually chosen to reflect some quality of the phenomenon being coded; for example, in coding of audio, still images and motion pictures, the Fourier transform or Discrete Cosine Transform (DCT) can be used to analyze the data into frequency terms or coefficients. Given the phenomenon being coded, there is generally a concentration of the information into a few frequency coefficients. Therefore, the transformed data can often be more economically encoded or compressed than the original data. This means that transform coding can be used to compress certain types of data to minimize storage space or transmission time over a communication link.
An example of transform coding in use is found in the Joint Photographic Experts Group (JPEG) international standard for still image compression, as defined by ITU-T Rec. T.81 (1992)|ISO/IEC 10918-1:1994, Information technology—Digital compression and coding of continuous-tone still images, Part 1: Requirements and Guidelines. Another example is the Moving Pictures Experts Group (MPEG) international standard for motion picture compression, defined by ISO/IEC 11172:1993, Information Technology—Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbits/s. This MPEG-1 standard defines systems for both video compression (Part 2 of the standard) and audio compression (Part 3). A more recent MPEG video standard (MPEG-2) is defined by ITU-T Rec. H.262|ISO/IEC 13818-2: 1996 Information Technology—Generic Coding of moving pictures and associated audio—Part 2: video. A newer audio standard is ISO/IEC 13818-3: 1996 Information Technology—Generic Coding of moving pictures and associated audio—Part 3: audio. All three image international data compression standards use the DCT on 8×8 blocks of samples to achieve image compression. DCT compression of images is used herein to give illustrations of the general concepts put forward below; a complete explanation can be found in Chapter 4 “The Discrete Cosine Transform (DCT)” in W. B. Pennebaker and J. L. Mitchell, JPEG: Still Image Data Compression Standard, Van Nostrand Reinhold: New York, (1993).
Wavelet coding is another form of transform coding. Special localized basis functions allow wavelet coding to preserve edges and small details. For compression the transformed data is usually quantized. Wavelet coding is used for fingerprint identification by the FBI. Wavelet coding is a subset of the more general subband coding technique. Subband coding uses filter banks to decompose the data into particular bands. Compression is achieved by quantizing the lower frequency bands more finely than the higher frequency bands while sampling the lower frequency bands more coarsely than the higher frequency bands. A summary of wavelet, DCT, and other transform coding is given in Chapter 5 “Compression Algorithms for Diffuse Data” in Roy Hoffman, Data Compression in Digital Systems, Chapman and Hall: New York, (1997).
In any technology and for any phenomenon represented by digital data, the data before a transformation is performed are referred to as being “in the real domain”. After a transformation is performed, the new data are often called “transform data” or “transform coefficients”, and referred to as being “in the transform domain”. The function used to take data from the real domain to the transform domain is called the “forward transform”. The mathematical inverse of the forward transform, which takes data from the transform domain to the real domain, is called the respective “inverse transform”.
In general, the forward transform will produce real-valued data, not necessarily integers. To achieve data compression, the transform coefficients are converted to integers by the process of quantization. Suppose that (&lgr;
i
) is a set of real-valued transform coefficients resulting from the forward transform of one unit of data. Note that one unit of data may be a one-dimensional or two-dimensional block of data samples or even the entire data. The “quantization values” (q
i
) are parameters to the encoding process. The “quantized transform coefficients” or “transform-coded data” are the sequence of values (a
i
) defined by the quantization function Q:
a
i
=
Q
⁡
(
λ
i
)
=
⌊
λ
i
q
i
+
0.5
⌋
(
1
)
where └x┘ means, as usual, the greatest integer less than or equal to x. The resulting integers are then passed on for possible further encoding or compression before being stored or transmitted. To decode the data, the quantized coefficients are multiplied by the quantization values to give new “dequantized coefficients” (&lgr;
i
′) given by
&lgr;′
i
=q
i
a
i
.  (2)
The process of quantization followed by dequantization (also called inverse quantization) can thus be described as “rounding to the nearest multiple of q
i
”. The quantization values are chosen so that the loss of information in the quantization step is within some specified bound. For example, for audio or image data, one quantization level is usually the smallest change in data that can be perceived. It is quantization that allows transform coding to achieve good data compression ratios. A good choice of transform allows quantization values to be chosen which will significantly cut down the amount of data to be encoded. For example, the DCT is chosen for image compression because the frequency components which result produce almost independent responses from the human visual system. This means that the coefficients relating to those components to which the visual system is less sensitive, namely the high-frequency components, may be quantized using large quantization values without perceptible loss of image quality. Coefficients relating to components to which the visual system is more sensitive, namely the low-frequency components, are quantized using smaller quantization values.
The inverse transform also generally produces non-integer data. Usually the decoded data are required to be in integer form. For example, systems for the playback of audio data or the display of image data generally accept input in the form of integers. For this reason, a transform decoder generally includes a step that converts the non-integer data from the inverse transform to integer data, either by truncation or by rounding to the nearest integer. There is also often a limit on the range of the integer data output from the decoding process in order that the data may be stored in a given number of bits. For this reason the decoder also often includes a “clipping” stage that ensures that the output data are in an acceptable range. If the acceptable range is [a,b], then all values less than a are changed to a, and all values greater than b are changed to b.
These rounding and clipping processes are often considered an integral part of the decoder, and it is these which are the cause of inaccuracies in decoded data and in part

Affiliated with

Also associated with

Rating

Error reduction in transformed digital data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Error reduction in transformed digital data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error reduction in transformed digital data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2862471