Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-08-02
2003-12-23
Johns, Andrew W. (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
C341S067000, C341S107000
Reexamination Certificate
active
06668094
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a variable length coding method, and more particularly, to a variable length coding method for reducing the number of bits generated by dynamically varying the mapping between symbols and bit patterns depending on the occurrence statistics of symbols of an input image. The present invention also relates to a variable length coding apparatus for performing the variable length coding method. The present invention also relates to a variable length decoding method for decoding a bit pattern which has been coded by the variable length coding method. The present invention also relates to a variable length decoding apparatus for performing the variable length decoding method. The present invention is based on Korean Application No. 99-31672 which is incorporated herein by reference.
2. Description of the Related Art
Standardized video CODECs adopt a variable length coding (VLC) technique to obtain high coding efficiency.
FIG. 1
shows a block diagram of a conventional variable length coding apparatus. Referring to
FIG. 1
, a VLC unit
10
receives a symbol and performs variable length coding based on a VLC table
12
. In the VLC table
12
, each symbol is mapped onto a bit pattern of a different length based on average symbol statistics of usual test patterns.
However, the symbol statistics vary considerably depending on a video sequence and coding parameters. Accordingly, in a conventional variable length coding technology, it sometimes happens that a large number of bits is allocated to a symbol even if the symbol appears frequently. This causes a problem of decreasing the efficiency of compression of bits by variable length coding.
To solve this problem, a conventional method prepares a plurality of VLC tables and selectively uses one among the prepared VLC tables. However, this method is disadvantageous in that it is difficult to sort a sequence characteristic and in that the efficiency of bit compression may be decreased because the characteristics of occurrence probabilities of symbols vary with coding parameters even with respect to the same sequence.
SUMMARY OF THE INVENTION
To solve the above problem, an object of the present invention is to provide a variable length coding method capable of efficiently reducing a bit rate by taking into account the occurrence statistics of symbols in an input image.
Another object of the present invention is to provide a variable length coding apparatus for performing this method.
Yet another object of the present invention is to provide a variable length decoding method for decoding a bit pattern which has been coded by the variable length coding method.
A further object of the present invention is to provide a variable length decoding apparatus for performing the variable length decoding.
To achieve one of the above objects of the invention, there is provided a method of variable length coding input symbols to generate bit patterns. The method includes the steps of (a) analyzing the occurrence statistics of symbols with respect to previous frames, (b) resetting a mapping relationship based on the analyzed occurrence statistics of symbols, and (c) variable length coding a current frame based on the reset mapping relationship.
It is preferable that the step (a) includes the step of calculating the occurrence statistics P
i
of an i-th symbol a
i
in N of symbols using W previous frames in accordance with
P
i
=
∑
t
=
n
-
1
n
-
W
c
i
(
t
)
∑
j
=
0
N
-
1
∑
t
=
n
-
1
n
-
W
c
j
(
t
)
where i is a predetermined positive number indicating a symbol number, c
i
(t) is the number of occurrences of the symbol a
i
in a t-th frame, and W is a predetermined positive integer indicating the number of frames used for analyzing the occurrence statistics of symbols.
Preferably, the step (a) analyzes the occurrence statistics of symbols using only symbols that are obtained from a frame immediately before the current frame.
Alternatively, the step (a) may analyze the occurrence statistics of symbols using symbols that are obtained from all the previous frames.
It is preferable that the step (b) includes the steps of reordering the symbols a
i
based on the occurrence statistics P
i
of the symbols a
i
, such that P
i′
≧P
i′+1
if i′≦i′+1, where i′ is a new number of a symbol a
i
, and resetting the mapping relationship such that
m
(
i
)=
i
′ based on the reordered relationship.
The variable length coding method further includes the step (c-1) for detecting whether the scene of each of the previous frames is similar to the scene of the current frame before the step (c). The current frame is variable length coded using a default variable length coding table and the mapping relationship when it is determined that the scene of a previous frame is not similar to the scene of the current frame in the step (c-1). The step (c) is performed when it is determined that the scene of a previous frame is similar to the scene of the current frame in the step (c-1).
The step (c-1) preferably includes the steps of (d-1) checking to find whether the ratio of occurrences of an intra macroblock in a frame immediately before the current frame is equal to or greater than a predetermined threshold, and (d-2) determining that the scene is changed if the ratio of occurrences of an intra macroblock in a frame immediately before the current frame is equal to or greater than the predetermined threshold, and, if not, determining that the scene is not changed.
Alternatively, the step (c-1) may include the steps of (e-1) checking to find whether the difference between the number of bits, which are generated by performing the mapping between a symbol and a bit pattern in a current image frame according to the method described above, and the number of bits, which are generated by using a default variable length coding definition, is equal to or greater than a predetermined number of bits; and (e-2) determining that the scene is changed if the difference is equal to or greater than the predetermined number of bits in the step (e-1) and, if not, determining that the scene is not changed.
Alternatively, the step (c-1) may include the steps of (f-1) measuring the sum of absolute difference (SAD) between a current image frame and a motion compensated image frame; and (f-2) determining that the scene is changed if the SAD is equal to or greater than a predetermined value in the step (f-1), and, otherwise, determining that the scene is not changed.
To achieve one of the above objects of the invention, there is provided an apparatus of variable length coding input symbols to generate bit patterns. The apparatus includes a statistical analyzer for analyzing the occurrence statistics of the input symbols with respect to previous frames, a mapping relationship resetter for resetting a mapping relationship based on the analyzed occurrence statistics of the symbols, and a variable length coding unit for variable length coding a current frame based on the reset mapping relationship.
To achieve one of the above objects of the invention, there is provided a digital image coding method to which variable length coding for generating bit patterns by variable length coding input symbols is applied. The method includes the steps of (a) analyzing the occurrence statistics of symbols with respect to previous frames, (b) resetting a mapping relationship based on the analyzed occurrence statistics of symbols, and (c) variable length coding a current frame based on the reset mapping relationship.
To achieve one of the above objects of the invention, there is provided a method of variable length decoding input bit patterns which have been variable length coded. The method includes the steps of (a) variable length decoding the input bit patterns using a default variable length coding table to obtain decoded symbols, (b) analyzing the occurrence statistics of the decoded symbol
Choi Byung-sun
Lee Yung-lyul
Yoo Kook-yeol
Alavi Amir
Johns Andrew W.
Samsung Electronics Co,. Ltd.
LandOfFree
Variable length coding method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Variable length coding method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable length coding method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3133763