Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1995-08-07
2001-06-26
Chang, Joh (Department: 2623)
Image analysis
Image compression or coding
Adaptive coding
C382S246000, C341S065000, C341S107000, C358S426010
Reexamination Certificate
active
06252992
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an encoding apparatus and method. More particularly, the invention relates to an encoding apparatus and method for performing variable-length coding.
2. Description of the Related Art
Huffman coding is widely known as a data compression method using variable-length coding. With Huffman coding, short code words are allocated, in accordance with the probability distribution of a symbol, in the order of symbol probability, thereby shortening average code length.
A problem encountered with this technique is that since code words are assigned in accordance with the probability distribution of a symbol, coding efficiency declines if there is a change in the symbol probability distribution. In order to overcome this drawback, dynamic Huffman coding has been proposed in literature such as “D. Knuth, “Dynamic Huffman Coding”, Journal of Algorithm, Vol. 6, No. 2, pp. 163~180, June, 1985”. However, according to dynamic Huffman coding, Huffman codes are reconstructed by computing an occurrence probability whenever a code is entered. As a consequence, a large amount of hardware (or computation) is required.
SUMMARY OF THE INVENTION
An object of the present invention is to solve the foregoing problem and provide an encoding apparatus and method wherein a decline in the efficiency of encoding of data in which symbol probability distribution (occurrence probability) varies dynamically is prevented by a simple arrangement or through simple processing.
According to a preferred embodiment of the present invention, the foregoing object is attained by providing an encoding apparatus comprising evaluating means for obtaining local occurrence probabilities of entered symbols, and assigning means for assigning short code words in conformity with the order of the occurrence probabilities obtained by the evaluating means.
Further, the foregoing object is attained by providing an encoding apparatus comprising first converting means for converting entered symbols to code IDs numbered in order of increasing code length, replacing means for replacing the code IDs, which have been outputted by the first converting means, in accordance with a replacement table, and second converting means for converting code IDs, which have been outputted by the replacing means, to code words arrayed in order of increasing code length; wherein the replacement table is updated, in units of a prescribed number of symbols, in conformity with generation frequency of symbols in the past.
Further, the foregoing object is attained by providing an encoding apparatus comprising evaluating means for obtaining local occurrence probabilities of entered symbols, and replacing means which, if ranking of occurrence probabilities obtained by the evaluating means changes, replaces the symbols in conformity with the changed ranking.
Further, the foregoing object is attained by providing an encoding method comprising an evaluation step of obtaining local occurrence probabilities of entered symbols, and an assigning step of assigning short code words in conformity with the order of the occurrence probabilities obtained at the evaluating step.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.
REFERENCES:
patent: 4355306 (1982-10-01), Mitchell
patent: 4420771 (1983-12-01), Pirsch
patent: 4578704 (1986-03-01), Gharavi
patent: 4700175 (1987-10-01), Bledsoe
patent: 4799242 (1989-01-01), Vermeulen
patent: 4862167 (1989-08-01), Copeland, III
patent: 4990910 (1991-02-01), Takishima et al.
patent: 5045852 (1991-09-01), Mitchell et al.
patent: 5182528 (1993-01-01), Zuta
patent: 5319682 (1994-06-01), Clark
patent: 5465173 (1995-11-01), Ishikawa et al.
patent: 5488616 (1996-01-01), Takishima et al.
patent: 5524170 (1996-06-01), Matsuo et al.
Huang et al., Windowed Huffman coding algorithm with size adaptation, Apr. 1993, pp. 109-113, IEEE.*
“Dynamic Huffman Coding”, D. Knuth, Journal of Algorithms, vol. 6, No. 2 pp. 163-180, Jun. 1985.
Canon Kabushiki Kaisha
Chang Joh
Fitzpatrick ,Cella, Harper & Scinto
Johnson Timothy M.
LandOfFree
Variable length coding 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable length coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2468726