Field of the Invention
The present invention provides a video decoder having efficient implementation of Reverse Variable Length Decoding (RVLD), which is fully compliant to video codec standard.
Background of the Invention
Encoder standards efficiently represent video image sequences as compactly coded data. Further, these standards describe decoding (reconstruction) process by which encoded bit streams are mapped from compressed data to the raw video signal data suitable for video display.
The video decoding process is generally the inverse of the video encoding process and is employed to reconstruct a motion picture sequence from a compressed and encoded bitstream. Generally, video bitstream data is decoded according to syntax defined by the encoder standards. The decoder must first identify the beginning of a coded picture, identify the type of picture, and then decode each individual macroblock within a particular picture.
Generally, encoded video data is received in a rate or a video buffer verifier (VBV). The data is retrieved from the channel buffer by a decoder or reconstruction device for performing the decoding. Decoders, such as MPEG decoder, perform inverse scanning to remove any zig zag ordering and inverse quantization to de-quantize the data. Where frame or field DCTs are involved, decoding process utilizes frame and field Inverse Discrete Cosine Transforms (IDCTs) to decode the respective frame and field DCTs, and converts the encoded video signal from the frequency domain to the time domain to produce reconstructed raw video signal data.
Decoder also performs motion compensation using transmitted motion vectors to reconstruct temporally compressed pictures. Decoder examines motion vector data, determines the respective reference block in the reference picture, and accesses the reference block from the frame buffer. After the decoder has Huffman decoded all the macroblocks, the resultant coefficient data is then inverse quantized and operated on by an IDCT process to transform macroblock data from a frequency domain to data in
space domain. Frames may need to be re-ordered before they are displayed in accordance with their display order instead of their coding order. After the frames are re-ordered, they may then be displayed on an appropriate device.
Figure 1 shows a block diagram of a typical video decoding system, as is known in the art. Shown in the figure are an Input Compressed Bit-stream 10, a header decoder 11, a Huffman decoder 12, a Quantizer & Compensator Block 13 and an output buffer 14. The header decoder 11 receives a compressed bit-stream 10 that consists of video and audio data. The data elements received from the output of header decoder 11 are Huffman decoded i.e. variable length decoding (VLD/RVLD) is performed and are reordered to produce a set of quantized coefficients. Although Huffman decoder 12 is used, however, other decoders that perform variable length decoding can be used. The variable length decoded data is rescaled/de-quantized (Q"1), inverse transformed (IDCT) and motion compensated by Quantizer & Compensator Block 13. The motion compensation is performed using the header information decoded from the bit-stream (and the decoded motion vectors), to produce an output frame. In alternative embodiments, variation of the aforesaid video decoder can be used. Further in alternate embodiments, the Quantizer & Compensator Block 13 can be split as different blocks.
The Huffman coded data i.e. Reversible Variable Length Codes (RVLC) are designed such that they can be instantaneously decoded both in forward and reverse directions. A part of a bit-stream, which cannot be decoded in the forward direction due to the presence of errors, can often be decoded in the backward direction. This is illustrated in the figure 2. Therefore number of discarded bits can be reduced, enabling an improvement in quality. RVLC is applied only to Texture Information.
Initially decoding in the forward direction is performed. If no errors are detected, the bit-stream is assumed to be valid and the decoding process is finished for that Video Packet (VP). If an error is detected, two-way decoding is applied. If an error is detected in the forward decoding, the decoder resynchronizes at the next suitable resynchronization point (vop_start_code or resync_marker) and starts Huffman-decoding in the backward direction, till it gets an error point in the backward direction. With the help of information gathered in the forward and backward
direction, decoder adopts one of the four strategies (described in the following part of the description) to determine the macroblocks to be decoded / discarded.
The following strategies for determining which bits (and hence MBs) to discard are used. These strategies are described using the figures along with the following definitions
An error-point is detected if —
(1) An illegal RVLC is found where an illegal RVLC is defined as follows:
• A codeword whose pattern is not listed in the RVLC table (e.g. 169 codeword
patterns and escape codes).
• Escape coding is used (i.e., a legal codeword is not available in the RVLC
table) and the decoded value for LEVEL is zero.
• The second escape code is incorrect (e.g. codeword is not "00000" or "00001"
for forward decoding, and/or is not "00001" for backward decoding).
• There is a decoded value of FLC part using escape codes (e.g. LAST, RUN,
LEVEL) in the RVLC table.
• An incorrect number of stuffing bits for byte alignment (e.g. eight or more Is
follow 0 at the last part of a Video packet (VP), or the remaining bit pattern is
not "0111..." after decoding process is finished).
(2) More than 64 DCT coefficients are decoded in a block.
Strategy-1: L1+L2 < L and N1+N2 < N
Macroblocks (MBs) of f_mb (Ll-T) from the beginning and MBs of b_mb(L2-T) from the end are decoded while the MBs of the darker portion as shown in figure 3 are discarded.
Strategy-2: L1+L2 < L and N1+N2 >= N
MBs of (N-N2-1) from the beginning and MBs of (N-N1-1) from the end are decoded while the MBs of the darker portion as shown in figure 4 are discarded.
Strategy-3; L1+L2 >= L and N1+N2 < N
MBs of N-b_mb(L2) from the beginning and MBs of N-fjnb(Ll) from the end are decoded while the MBs of the darker portion as shown in figure 5 are discarded.
Strategy-4; L1+L2 >= L and N1+N2 >= N
MBs of min {(N-b_mb(L2)), (N-N2-1)} from the beginning and MBs of min{(N-f_mb(Ll)), (N-N1-1)} from the end are decoded while the MBs of the darker portion as shown in figure 6 are discarded.
where
L - Total number of bits for DCT coefficients part in a VP.
N - Total number of macroblocks (MBs) in a VP.
LI - Number of bits which can be decoded in a forward decoding.
L2 - Number of bits which can be decoded in a backward decoding.
Nl - Number of MBs which can be completely decoded in a forward decoding.
(0 <= Nl<= (N-l))
N2 - Number of MBs which can be completely decoded in a backward decoding.
(0<=N2<=(N-1))
f_mb(S) - Number of decoded MBs when S bits can be decoded in a forward
direction. (Equal to or more than one bit can be decoded in a MB, f_mb(S) counter is
up.)
b_mb(S) - Number of decoded MBs when S bits can be decoded in a backward
direction.
T - Threshold (90bits is used now).
When RVLD is performed in the reverse direction, Huffman-decoded information is kept in a buffer and the corresponding MB index in a separate buffer. When the Huffman decoding in the reverse direction ends, then the possible "strategy" is finalized based on the decoded information. Once the "Strategy" is finalized, decoding (IDCT, motion-compensation, etc) is done on Huffman decoded code words.
The following abbreviations stand for
MB_NUMBER: Total number of 16x16 MBs in the frame
rvld_codes_backward [MB_NUMBER][6][64]\ Array used for storing RVLD output
rvld_index_backward[MB_NUMBER][6J: Array used for storing the index of last non
zero DCT coefficient in the 8x8 block.
Total size required for the two buffers is 75.4 KB for QCIF resolution and 301.6 KB
for GIF resolution.
The problem with the existing approach is now illustrated with the help of the following example. Assuming error occurs in (Nl+1) MB while forward decoding, backward decoding is done from the end of the video packet. While backward decoding, RVLD output is stored in rvld_codes_backward array for every MB, till the error occurs at (N-N2-1) MB. The index of the last non-zero DCT coefficient is stored in rvld_index_backward for every MB. The MBs to be concealed are determined. Rest of the MBs are considered correct and undergo IDCT, motion compensation (for predicted or P blocks) and are finally written to the output buffer.
RVLD output and index of last non-zero coefficient for all the completely decoded MBs have to be stored in the array. Since number of MBs in a video packet can be as large as MB_NUMBER, the memory has to be allocated for all of them.
In the proposed approach complete decoding of a MB (RVLD, then Inverse Discrete Cosine Transform (IDCT), Motion-compensation etc) is performed in the reverse direction and the decoded data is kept in the output buffer. At the end of decoding, the possible "strategy" is finalized based on the decoded information. Once the "Strategy" is finalized, number of MBs to be concealed is determined.
The challenge in this proposed approach is to determine the point up to which complete-decoding in backward direction is to be performed because the strategy for identifying backward decodable point can only be finalized once the error-point is identified in the backward direction. If decoding is done till error point is reached, lot of irrelevant computation will be done causing cycle-count to shoot-up. Also backward decoding should not be terminated before the decodable point is reached as
it will cause loss of relevant data and the output will not be in conformance with the video encoder standard.
Object & Summary of the Invention
To eliminate the above-mentioned drawbacks, it is an object of the present invention to minimize/eliminate the buffer requirement while keeping low computation-cost for RVLD implementation.
To achieve the aforesaid object, the instant invention provides an video decoder
comprising:
an encoded bit stream;
a header decoder for receiving said encoded bit stream;
a variable length decoder connected to said header decoder receiving the
header decoded data;
a quantizer and compensator connected to said variable length decoder
during backward decoding for performing inverse quantization,
transformation and motion compensation of said variable length decoded
data wherein while backward decoding variable length decoding, said
inverse quantization, transformation and motion compensation of said
header decoded data is done consecutively to provide complete decoded
data till a first point in the backward direction such that said first point is
either the error point or a point before the end point of the macroblock
containing error detected in the forward direction and
said output buffer connected to said quantizer and compensator for storing
complete decoded data;
thereby eliminating the use of intermediate buffer for storing variable length decoded
data during backward decoding and reducing the number of computations.
The said variable length decoder is Huffman decoder.
The said variable length decoder performs variable length decoding of said first point being a point before the end point of the macroblock containing error detected in the forward direction till the error point is reached.
The said point before the end point of the macroblock containing error is computed by subtracting one and the macroblocks decoded in forward direction from the total number of macroblocks in the video packet.
The invention further illustrates a method of decoding video data comprising the steps of:
receiving an encoded bit stream;
header decoding of said encoded bit stream;
- performing variable length decoding of said header decoded data;
- performing said variable length decoding, said inverse quantization,
transformation and motion compensation of said header decoded data
consecutively till a first point in the backward direction such that said first
point is either the error point or a point before the end point of the
macroblock containing error detected in the forward direction and
- storing said decoded data in the output buffer thereby eliminating the step
of intermediate storage of variable length decoded data during backward
decoding and reducing the number of computations.
Brief Description of the Accompanying Drawings
Figure 1 shows the diagram of a conventional video decoder.
Figure 2 illustrates Reversible Variable Length Codes being decoded in forward and backward direction.
Figure 3 illustrates strategy 1. Figure 4 illustrates strategy 2. Figure 5 illustrates strategy 3. Figure 6 illustrates strategy 4. Figure 7 illustrates the video packet showing the novel point.
Detailed description of the Invention
Before describing in detail the embodiments that are in accordance with the present invention, it should be observed that the embodiments reside primarily in combinations of method steps and apparatus components related to a video decoder and RVLC. Accordingly, the apparatus components and method steps have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiment of the present invention so as not to obscure the disclosure with details that will be readily _ apparent to those of ordinary skill in the art having the benefit of the description herein.
It will be appreciated that the embodiments of the invention described herein may be comprised of one or more conventional processors and unique stored program instructions that control the one or more processors to implement, in conjunction with certain non-processor circuits, some, most, or all of the functions of decoders described herein. The non-processor circuits may include, but are not limited to. a radio receiver, a radio transmitter, signal drivers, clock circuits, power source circuits, and user input devices. As such, these functions may be interpreted as steps of a method to perform decoding. Alternatively, some or all functions could be implemented by a state machine that has no stored program instructions, or in one or more application specific integrated circuits (ASICs), in which each function or some combinations of certain of the functions are implemented as custom logic. Of course, a combination of the two approaches could be used. Thus, methods and means for these functions have been described herein. Further, it is expected that one of ordinary skill, notwithstanding possibly significant effort and many design choices motivated by, for example, available time, current technology, and economic considerations, when guided by the concepts and principles disclosed herein will be readily capable of generating such software instructions and programs and ICs with minimal experimentation.
The instant invention rather than storing RVLD output into the buffers, decodes them fully after doing RVLD till a special point. The complete decoding involves IDCT, motion-compensation and writing into output buffer. On analyzing the four strategies, the maximum numbers of MBs, which can be considered for complete decoding, are
(N-N1-1). To minimize the decoding effort in backward decoding, MBs are fully decoded (IDCT, motion-compensation and store into output buffer) only till (N-N1-l)th MB or the error block, whichever occurs first. However, if error does not occur at (N-Nl-l)th MB, only RVLD (IDCT, motion- compensation and write to output buffer is *not* performed after (N-Nl-l)th MB) is continued till the error occurs, to find the error point which is used for deciding the strategies and finding the MB's to be concealed.
Figure 7 shows the diagram illustrating different points referred to while decoding a picture frame in accordance with the invention. Point A marks the point from which discarded data starts while point B indicates upto, which point RVLD is performed in forward direction due to presence of error point. Point C points to end of RVLD in the backward direction due to presence of error point. Point D is the novel point till which complete decoding namely, RVLD, inverse quantization, IDCT and motion-compensation is done in the backward direction to get L2, N2. Point E indicates the end of discarded data. The point D coincides with point E in most strategies.
The following table 1 presents the strategy distribution in the RVLD case:
(Table Removed)
Table 1
1. Max increase in MCPS = 2.14%
2. From "Strategy" distribution, it can be noted that all the four test vectors use
all the cases (Strategy-1 to Strategy-4).
3. Results show that deviation in cycle count occurs only in strategy-1 which is expected because of "T" (=90) bits of threshold (T=90bit is chosen in the standard)
The proposed method presents a good trade-off between data-memory and MCPS. Moreover, the choice of decoding up to (N-N1-1) macroblock in the backward direction gives increase in computation only in stategy-1 as per theoretical assumption. Results prove the analysis of choosing (N-Nl-l)th block in the backward direction without any compute overhead.
In strategy 2, there are no processing overheads involved, since (N-N1-1) blocks are always considered.
By definition,
f-Mb(Ll) > Nl
N-f-mb(Ll) < N-N1 —(I) Also,f_mb(LJ)=Nl+x These A' blocks can have maximum 1 non-skipped MB.
In strategy 3,
N1+N2