Hybrid domain processing of multi-dimensional transformed data

Details Hybrid domain processing of multi-dimensional transformed data Hybrid domain processing of multi-dimensional transformed data

2000-06-07

2004-01-06

Ingberg, Todd (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S401000

Reexamination Certificate

active

06675185

ABSTRACT:

DESCRIPTION
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to transform coding of digital data, specifically to processing of transformed data and, more particularly, to a shift and/or merge of two-dimensional transformed data using hybrid domain processing which increases the speed of, for example, processing of color images printed by color printers. The invention implements an efficient method for two-dimensional merging and shifting of JPEG (Joint Photographic Experts Group) images compressed with the Discrete Cosine Transform (DCT) domain. Since each dimension is handled separately, the shift or merge amounts are independent for the two axes. The invention provides fast shifting of the basic 8×8 DCT blocks contained in baseline JPEG compressed images to create JPEG images on a new grid.
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, a video clip, etc. The transform function is usually chosen to reflect some quality of the phenomenon being coded; for example, in coding of 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 compressed, 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 a video compression (Part 2 of the standard). 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. 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 Federal Bureau of Investigation (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”. Since the present invention works on multi-dimensional transformed data after taking the inverse transform on less than the total dimension, we are defining a new term, “hybrid domain”, to indicate that the orthogonal axis/axes is still transformed. To simplify notation, we will describe the invention for two dimensional transform data. Unless the context makes another meaning clear, the term “transform domain” will refer to the full multi-dimensional 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 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
r
  (2)
The process of quantization followed by de-quantization (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 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 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 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

Affiliated with

Also associated with

Rating

Hybrid domain processing of multi-dimensional transformed 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 Hybrid domain processing of multi-dimensional transformed data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid domain processing of multi-dimensional transformed data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3259859