Pulse or digital communications – Pulse code modulation – Differential
Reexamination Certificate
2000-01-19
2004-02-24
Corrielus, Jean B. (Department: 2631)
Pulse or digital communications
Pulse code modulation
Differential
C375S265000, C382S251000
Reexamination Certificate
active
06697434
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for tracing an optimal quantization path using a Trellis-based adaptive quantizer, and in particular to an improved method for tracing an optimal path using a Trellis-based adaptive quantizer which can accelerate quantization path tracing and simplify computation thereof, by excluding the quantization path tracing after an turning point of distortion and after an optimal quantization level to non-zero at a branch directed to the non-zero node from a zero node.
2. Description of the Background Art
In general, a Trellis-based adaptive quantizer codes coefficients to which image blocks are transformed by transformation methods, such as a discrete cosine transformation (DCT) in a Trellis structure, into a run-length code and entropy constrained code.
FIG. 1
is a concept diagram of data quantization using the Trellis-based adaptive quantizer in the conventional art. Whenever predetermined coefficients C
1
, C
2
, . . . , Ci, . . . , C
64
from a predetermined node at an initial state are quantized one by one, corresponding stages S
1
, S
2
, . . . , S
64
are formed. Here, white circles imply code as ‘0’, Ri denotes a run length (which means the number of code as ‘0’), and black circles imply code of the coefficients Ci to a level (or amplitude) Li.
In the above example, when it is presumed that one image block is divided into 8×8, the number of the coded coefficients is 64 thereby. A solid line indicates a branch for coding the coefficient as non-zero from a predetermined node, and a dotted line indicates a branch for coding the coefficient as zero from a predetermined node.
At this time, the respective stages are defined as an algorithm of performing Huffman coding on a predetermined symbol, a run length and a level. Accordingly, paths between the branches connecting the nodes of the respective stages are defined as a metric. The metric J is represented by the following expression.
J=D+&lgr;·R
Here, R denotes the number of bits used for coding the coefficient (for example, R=64), D denotes distortion between the coefficients of each stage and the coded coefficient (or the absolute value of the subtraction between the coefficients of each stage and the coded coefficient), and &lgr; denotes Lagrange constant.
When the data is quantized by the expression J(n)=D(n)+&lgr;·R(n) in order to obtain a minimum metric J(n) to the n-th stage S(n), the conventional method for tracing the optimal quantization path using the Trellis-based adaptive quantizer adapts only the distortion D, not R(n), computes the metrics for all the paths, selects the metric at the optimal state, and determines the optimal path.
However, the conventional method has a disadvantage in that the optimal path is determined by computing all the metrics in regard to the whole paths or branches. As a result, a system adapted the conventional method codes the data lately and complicatedly, and thereby takes a long time to compute the optimal path tracing.
SUMMARY OF THE INVENTION
Accordingly, it is a primary object of the present invention to provide an improved method for tracing an optimal path using a Trellis-based adaptive quantizer, which can search a quantization interval at a high speed by excluding branches which do not require path tracing in a Trellis structure.
It is another object of the present invention to provide an improved method for tracing an optimal quantization path using a Trellis-based adaptive quantizer which can accelerate quantization path tracing and simplify computation thereof, by excluding the quantization path tracing after a turning point of distortion in the Trellis-based adaptive quantizer and after an optimal quantization level to non-zero at a branch directed to a non-zero node from a zero node.
In order to achieve the above-described objects of the present invention, in a Trellis-based adaptive quantizer codes coefficients to which image blocks are transformed by transformation methods in a Trellis structure into a run-length code and entropy constrained code, a method for tracing an optimal path using the Trellis-based adaptive quantizer comprises, a step for excluding quantization path tracing of branches after a turning point of distortion, on the basis of arrangement of a quantization interval and monotonic increasing characteristics of a code word length, in a Trellis structure of generating one stage whenever the coefficients are quantized one by one from a node, and a step for excluding path tracing after an optimal coding level to non-zero at the branches positioned from zero node to non-zero node, based on independence of the respective stages, when quantizing coefficients to non-zero node from the node.
REFERENCES:
patent: 5329537 (1994-07-01), Alard et al.
patent: 5781569 (1998-07-01), Fossorier et al.
patent: 5844945 (1998-12-01), Nam et al.
patent: 5991341 (1999-11-01), Shin
patent: 6118822 (2000-09-01), Bist
patent: 6128346 (2000-10-01), Suarez et al.
patent: 6249546 (2001-06-01), Bist
patent: 6263312 (2001-07-01), Kolesnik et al.
Corrielus Jean B.
Fleshner & Kim LLP
LG Electronics Inc.
LandOfFree
Method for tracing optimal path using Trellis-based adaptive... 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 for tracing optimal path using Trellis-based adaptive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for tracing optimal path using Trellis-based adaptive... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3348991