Title of Invention

"AN APPARATUS FOR VARIABLE LENGTH CODING INPUT SYMBOLS TO GENERATE BIT PATTERNS"

Abstract

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. 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.

Full Text

1. Field of the Invention The present invention relates to apparatus for variable length coding input symbols to generate bit patterns. 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, 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 considerably vary 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 that 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, Further another object of the present Invention is to provide a variable length decoding apparatus for performing the variable length decoding. STATEMENT OF THE INVENTION Accordingly, the present invention relates to an apparatus for variable length coding input symbols to generate bit patterns, the apparatus comprising: (a) a statistical analyzer (504) for analyzing the occurrence statistics of the input symbols with respect to previous frames in a manner such as herein described. (b) A mapping relationship resetter (506) for resetting a mapping relationship based on the analyzed occurrence statistics of the symbols; and (c) A variable length coding unit for variable length coding a current frame based on the reset mapping relationship and optionally a scene change detector (510). 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 PI of an i-th symbol 81 in N of symbols using W previous frames In accordance with (Equation Removed) where I is a predetermined positive number Indicating a symbols number, q(t) is the number of occurrences of the symbol ti 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, based on the occurrence statistics P, of the symbols at such that P,,^ Pi 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 includes 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 includes 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 symbols with respect to previous frames of a current frame, (c) resetting a mapping relationship based on the analyzed occurrence statistics of the input symbols, and (d) replacing the decoded symbols with symbols corresponding to the reset mapping relationship in the current frame. To achieve one of the above objects of the invention, there is provided an apparatus for variable length decoding input bit patterns which have been variable length coded. The apparatus includes a variable length decoder for variable length decoding the input bit patterns using a default variable length coding table to obtain decoded symbols, a statistical analyzer for analyzing the occurrence statistics of the decoded symbols with respect to previous frames of a current frame, a mapping relationship resetter for resetting a mapping relationship between symbols and bit patterns based on the analyzed occurance statistics of the input symbols, and a symbol replacer for replacing the decoded symbols with symbols corresponding lo the reset mapping relationship in the current frame. To achieve one of the input bit patterns using a default variable length coding table to obtain decoded symbols, a statistical analyzer for analyzing the occurrence statistics of the decoded symbols with respect to previous frames of a current frame the above objects of the invention, there is provided a digital image decoding apparatus using variable length decoding. The apparatus includes a variable length decoding unit including a variable length decoder for variable length decoding, a mapping relationship resetter for resetting a mapping relationship between symbols and bit patterns based on the analyzed occurrence statistics of the input symbols, and a symbol replacer for replacing the decoded symbols with symbols corresponding to the reset mapping relationship in the current frame. BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS The above objects and advantages of the present invention will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which: FICi. 1 is a block diagram of a conventional variable length coding apparatus; FIG. 2 is a block diagram of a variable length coding apparatus according to an embodiment of the present invention; FIGS. 3 A and 3B are flowcharts showing the main steps of a variable length coding method according to an embodiment of the present invention; FIGS. 4A through 4E are graphs for comparing a variable length coding method of the present invention and a conventional variable length coding method based on the number of bits per frame during coding; FIG. 5 is a block diagram of a variable length decoding apparatus according to an embodiment of the present invention; and FIG. o(a) through FIG 6(c) are the block diagrams of the scene change detectors according to first, second and third embodiments of the present application respectively. DETAILED DESCRIPTION OF THE INVENTION Hereinafter, embodiments of the present invention will be described in detail with reference to the attached drawings. Referring to FIG. 2, a variable length coding apparatus according to the present invention includes a statistical analyzer 202, a mapping relationship resetting unit 204, a scene change detector 208 and a variable length coding (VLC) unit 210. The mapping relationship resetting unit 204 includes a mapper 205 and a symbol replacer 206. In the operation of such apparatus, when representing a symbol number by i, a predetermined positive number, the statistical analyzer 202 receives a symbol in step 302 and calculates the occurrence statistics of the input symbol a, with respect to previous frames in step 304. When representing the number of occurrences of the symbol a, in a t-th frame by c1(t) and representing a predetermined positive integer indicating a window size such as the number of frames, which is used for the calculation of the occurrence statistics of symbols, by W, the statistical analyzer 202 calculates the occurrence statistics P, of each symbol a, in W previous frames in accordance with (Equation Removed) Thus, the occurrence statistics P, of an i-th symbol among N kinds of symbols in W previous frames are obtained. In the above embodiment, the occurrence statistics of each symbol are calculated based on symbols which are obtained from a plurality of previous image frames, but the present invention is not restricted thereto. The occurrence statistics of each symbol may be calculated based on only symbols which are obtained from the previous image, or based on symbols which are obtained from all previous images. Next, the mapper 205 reorders the symbols based on the occurrence probability Pi of each symbol ai which is output from the statistical analyzer 202 and sets a mapping relationship of (Equation Removed) based on the reordered relationship in step 306. In an embodiment of the present invention, the symbols are reordered such that P1 ≥P,.+1, when i' Meanwhile, in a variable length coding method according to the present invention, occurrence probabilities obtained with respect to previous image frames cannot be used for a current image frame when the previous frames and the current frame are not correlated. In other words, it is necessary to detect whether the current image frame is similar to the previous image frames. Accordingly, the scene change detector 208 compares a current frame scene with previous frame scenes and detects whether they are similar, in step 320. In an embodiment of the present invention, the scene change detector 208 outputs a control signal SCENE_CHANGE as a logic "low" level when a current frame scene is similar to a previous frame scene, and outputs a control signal SCENE_CHANGE as a logic "high" level when a current frame scene is not similar to a previous frame scene. During the detection of scene change, it is preferable to determine that a scene is changed when the ratio of occurrences of an intra macroblock in the previous image frame is equal to or more than a predetermined threshold. Alternatively, it is possible to determine that a scene is changed when 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 more than a predetermined number of bits. Alternatively, it is possible to determine that a scene is changed when the sum of absolute difference (SAD) between a current image frame and a motion compensated image frame is equal to or more than a predetermined value. Then, when a "low" level control signal SCENE_CHANGE is input from the scene change detector 208, this indicates that a scene has not changed, and thus, in step 30, the VLC unit 210 performs variable length coding on the replaced symbols, that is, symbols ai obtained based on the reset mapping relationship, using the default VLC table 212 for the current frame. On the other hand, when a "high" level control signal SCENE_CHANGE is input from the scene change detector 208, this indicates that a scene has changed, and thus, in step 322, the VLC unit 210 performs variable length coding on the input symbols a, using the default VLC table 212 and mapping relationship for the current frame, instead of performing variable length coding on the current frame based on the reset mapping relationship. After performing variable length coding with respect to the current frame, it is determined whether the current frame is the last frame in step 324. When it is determined that the current frame is not the last one in step 324, the next frame is selected in step 326, and the steps 302 through 324 are repeated. For a clearer understanding of the present invention, the operation of an apparatus according to the present invention will be described with a simple example. First, it is assumed that variable length coding is performed using a VLC table such as Table 1. Table 1 (Table Removed) In addition, it is assumed that the occurrence probabilities of symbols obtained after coding an arbitrary image frame are as follows. Table 2 (Table Removed) According to a variable length coding method of the present invention, the mapping table between symbols and bit patterns is generated depending on probabilities. Table 3 (Table Removed) For example, a symbol a2) whose occurrence probability is smallest, is mapped to a bit pattern of four bits, i.e., 0001. A symbol a3, whose occurrence probability is largest, is mapped to a bit pattern of a single bit, i.e., 1. An average bit rate per symbol, for symbols that are variable length coded based on the mapping table shown in Table 3, is ∑PiSi = 0.2 x 1 + 0.3 x 2 + 0.1 * 3 + 0.4 x 4 = 2.7 bits/symbol. On the other hand, the average bit rate per symbol, for symbols that are variable length coded according to the present invention, is ∑PjSm(i)=0.2x3+0.3x2+0.1x4+0.4x1 =2.0 bits/symbol. Accordingly, the present invention reduces the number of generated bits by 0.7 bits/symbol. In other words, the present invention reduces the number of generated bits, even while using a VLC table which is used in variable length coding. In addition, according to a variable length coding method of the present invention, variable length coding is stably performed regardless of changes in the statistical characteristics or coding parameters of an image, since the variable length coding is performed considering the statistical characteristics of symbols of an image frame. Simulations were performed to estimate the performance of a variable length coding method of the present invention. Five kinds of test sequence, which have a QCIF frame format of 176x144 pixels and are composed of 100 frames, were used in the simulations. A fixed quantization step size was used. As the results of the simulations, FIGS. 4A through 4E show graphs for comparing a variable length coding method of the present invention and a conventional variable length coding method based on the number of bits per frame during coding. FIGS. 4A through 4E show the variation of bits per frame with respect to quantization step size when "News", "Silent", "Container ship","Foreman" and "Hall Objects", each of which has a QCIF frame format of 176x144 pixels and is composed of 100 frames, were used as test sequences. For other test conditions, common test conditions defined in H.26L were used. Referring to FIGS. 4A through 4D, as the quantization step size becomes smaller, a very large performance gain is achieved in a variable length coding method of the present invention compared to a variable length coding method according to the Telenor H.26L proposal. According to the present invention, to improve variable length coding efficiency, a mapping relationship between symbols and bit patterns is adaptively changed in a variable length codeword table based on the results of partially measuring symbol probabilities, without changing a VLC table. According to the results of a simulation in which a method of the present invention was applied to macroblock (MB) mode information, the reduction of MB mode bit rate was about 50%. As described above, according to a variable length coding method of the present invention, the number of bits to be generated can be reduced by dynamically varying a mapping relationship. A variable length coding method of the present invention can be applied to H.261, H.263, MPEG-1, MPEG-2 and MPEG-4, which use variable length coding, and to H.26L proposals which uses universal variable length coding (UVLC). Bit patterns, which have been variable length coded by a variable length coding method according to the present invention, are transmitted to a transmission channel. The transmitted bit patterns can be decoded by a variable length decoder according to an embodiment of the present invention. FIG. 5 is a block diagram of a variable length decoding apparatus according to an embodiment of the present invention. Referring to FIG. 5, the variable length decoding apparatus includes a variable length decoder 502, a statistical analyzer 504, a mapping relationship resetter 506, a symbol replacer 508 and a scene change detector 510. In the operation of the apparatus, the variable length decoder 502 performs variable length decoding on bit patterns in an input bit stream using a default VLC table 503 and outputs decoded symbols. The statistical analyzer 504 analyzes the occurrence statistics of the decoded symbols with respect to previous frames. The mapping relationship resetter 506 resets the mapping relationship between input symbols and bit patterns based on the analyzed occurrence statistics. Since the reset mapping relationship is determined based on the occurrence statistics of symbols, the reset mapping relationship is the same as that used during coding, which is performed by a variable length coding method according to an embodiment of the present invention as described with reference to FIGS. 2, 3A and 3B, if errors in the input bit patterns are not large. In other words, even if an encoding apparatus, which has encoded an image using a variable length coding method of the present invention, does not transmit information on the mapping relationship to a decoding apparatus, the decoding apparatus can obtain the mapping relationship used during the encoding by decoding a bit stream transmitted from the encoding apparatus. Then, the symbol replacer 508 replaces the decoded symbols with symbols corresponding to the reset mapping relationship in a current frame and outputs symbol data. Finally, the bit patterns, which have been coded by a variable length coding method according to the present invention, which dynamically varies a mapping relationship to reduce the number of bits that are generated, are successfully variable length decoded. In the above embodiment of the present invention, the reset mapping relationship is applied to all the bit patterns during the variable length decoding. In another case, the variable length decoding apparatus according to the above embodiment of the present invention may also include a scene change detector 510 in order to decode bit patterns which have been coded by a variable length coding apparatus, which includes the scene change detector 208 as described with reference to FIG. 2. The scene change detector 510 compares a previous frame scene and a current frame scene using the decoded symbols which are output from the variable length decoder 502 to detect whether they are similar. Then, the scene Change detector 510 outputs a "low" control signal when they are not similar and a "high" control signal when they are similar. In response to the "low" control signal, the symbol replacer 508 does not perform symbol replacement and outputs the decoded symbols received from the variable length decoder 502 as symbol data. Alternatively, in response to the "high" control signal, the symbol replacer 508 replaces the decoded symbols received from the variable length decoder 502 with symbols corresponding to the reset mapping relationship and outputs the replaced symbols as symbol data. In accordance with a first embodiment of the present application, which is shown explicitly in fig 6(a), wherein the scene change detector 510 comprises measuring means ameasuring circuit (60) for measuring the ratio of occurrences of an intra macroblock in a frame immediately before the current frame and determining means a processor(602) for determining that the scene is changed if the ratio of occurrences of an intra macroblock is equal to or greater than a predetermined threshold, and, if not, determining that the scene is not changed. In accordance with a second embodiment of the present application, which is shown explicitly in fig 6(b) , wherein the scene change detector comprises a Counting means (a digital counter)603 for counting the first number of bits, which are generated by performing mapping between symbols and bit patterns with respect to the current image frame based on a default mapping table and counting the second number of bits, which are generated by performing mapping between symbols and bit patterns with respect to the current image frame based on the reset mapping relationship and determining means(a processor)(602)for calculating a difference between the first number of bits and the second number of bits, determining that the scene is changed if the difference is equal to or greater than a predetermined value, and, if not, determining that the scene is not changed. In accordance with a third embodiment of the present application, which is shown explicitly in fig 6(c), wherein the scene change detector comprises sum of absolute difference (SAD) measuring means an adder and a subtractorcircuits (604) for measuring the SAD between the current image frame and a motion compensated image frame and determining means a processor (602)for determining that the scene is changed if the SAD is equal to or greater than a predetermined value, and, otherwise, determining that the scene is not changed. Such variable length coding apparatus may be included in a digital image decoding apparatus using variable length decoding. Variable length coding and decoding methods according to the present invention can be made into programs which can be executed in a computer. The programs may be stored in a magnetic receding medium such as a floppy disc or a hard disk or an optical recording medium such as CD-ROM or DVD, or may be transmitted through a carrier wave medium such as the Internet. Morever, program codes and code segments constructing the programs can be easily inferred by computer programmers in the art. As described above, a variable length coding method according to the present invention dynamically varies the mapping relationship between input symbols and bit patterns based on the characteristics of an image, thereby reducing the amount of bits to be generated. WE CLAIM: 1. An apparatus for variable length coding input symbols to generate bit patterns, the apparatus comprising: (a) a statistical analyzer (504) for analyzing the occurrence statistics of the input symbols with respect to previous frames in a manner such as herein described; (b) a mapping relationship resetter (506) for resetting a mapping relationship based on the analyzed occurrence statistics of the symbols; and (c) a variable length coding unit (502) for variable length coding a current frame based on the reset mapping relationship and optionally a scene change detector (510). 2. An apparatus as claimed in claim 1, wherein the statistical analyzer (504) analyzes the occurrence statistics of symbols using only symbols that are obtained from a frame immediately before the current frame and more particularly from all the previous frames. 3. An apparatus as claimed in claim 1, wherein the scene change detector (510) detects whether the scene of each of the previous frames is similar to the scene of the current frame, outputs a first logic level as a control signal when they are not similar, and outputs a second logic level as a control signal when they are similar, wherein the variable length coding unit (502) performs variable length coding on the current frame using a default variable length coding table and the mapping relationship, in response to the first logic level control signal, and performs variable length coding on the current frame using the reset mapping relationship, in response to the second logic level control signal. 4. An apparatus as claimed in claim 3, wherein the scene change detector comprises: a measuring circuit (601) for measuring the ratio of occurrences of an intra macroblock in a frame immediately before the current frame; and a processor (602) for determining that the scene is changed if the ratio of occurrences of an intra macroblock is equal to or greater than a predetermined threshold, and, if not, determining that the scene is not changed. 5. An apparatus as claimed in claim 3, wherein the scene change detector comprises: a digital counter (603) for counting the first number of bits, which are generated by performing mapping between symbols and bit patterns with respect to the current image frame based on a default mapping table and counting the second number of bits, which are generated by performing mapping between symbols and bit patterns with respect to the current image frame based on the reset mapping relationship; and a processor (602) for calculating a difference between the first number of bits and the second number of bits, determining that the scene is changed if the difference is equal to or greater than a predetermined value, and, if not, determining that the scene is not changed. 6. An apparatus as claimed in claim 3, wherein the scene change detector comprises: an adder and a subtracter circuit (604) for measuring a sum of absolute difference (SAD) between the current image frame and a motion compensated image frame; and a processor (602) for determining that the scene is changed if the SAD is equal to or greater than a predetermined value, and, otherwise, determining that the scene is not changed. 7. An apparatus for variable length coding input symbols to generate bit patterns substantially as herein described with reference to the accompanying drawings.

Documents:

688-del-2000-abstract.pdf

688-del-2000-claims.pdf

688-del-2000-correspondence-others.pdf

688-del-2000-correspondence-po.pdf

688-del-2000-description (complete).pdf

688-del-2000-drawings.pdf

688-del-2000-form-1.pdf

688-del-2000-form-13.pdf

688-del-2000-form-19.pdf

688-del-2000-form-2.pdf

688-del-2000-form-3.pdf

688-del-2000-form-4.pdf

688-del-2000-form-5.pdf

688-del-2000-gpa.pdf

688-del-2000-petition-137.pdf