Alternative block orders for better prediction

Details Alternative block orders for better prediction Alternative block orders for better prediction

2000-08-09

2004-04-20

Kelley, Chris (Department: 2613)

Pulse or digital communications

Bandwidth reduction or expansion

Television or motion video signal

C375S240120, C375S240240

Reexamination Certificate

active

06724818

ABSTRACT:

FIELD OF THE INVENTION
The present invention is related to compression of digital video signals and, more particularly, to a method and apparatus for employing alternative block scanning orders in order to improve the efficiency of the compression.
BACKGROUND OF THE INVENTION
Recent developments in communication systems and signal compression technology have made point-to-point video communication a technical possibility. The various applications of point-to-point video communication may be classified according to the amount of bandwidth available for transmission of the video signals. For example, commercially available videoconferencing systems using dedicated lines have a few hundred kbps (kilobits per second) of bandwidth available for signal transmission. In contrast, a personal communication device such as a videotelephone using ordinary telephone lines or wireless channels only has about 20 kbps of bandwidth available. Therefore, some compression of the video signals is necessary for transmission using such personal communication devices.
In general, video signal compression refers to the art of more or less transparently minimizing the amount of bandwidth required to transmit the information in the video signal. Compression is made possible by virtue of a high degree of redundancy both within each image frame and between consecutive image frames of the video signal. In other words, one image frame may differ only slightly from the preceding image frame(s), or one portion of an image frame may differ only slightly from another portion of the same image frame. The redundancy allows certain portions of an image frame to be extrapolated or predicted based on the preceding image frames or the preceding portions within the same image frame. Consequently, the amount of information in the video signal that actually needs to be transmitted may be substantially reduced.
A number of encoding standards, such as ITU-T Recommendation H.263 and ISO Standard MPEG-4, have been developed to help standardize the transmission of video signals over low bandwidth media. Under such standards, each frame of the video signal is divided into smaller regions called macroblocks. For example, referring to
FIG. 1
, each frame
10
of a QCIF (Quarter Common Interface Format) image is divided into 9×11 macroblocks
12
, each consisting of 16×16=256 pixels. In present standards, each macroblock is coded in units of 8×8 pixel blocks, or 4×8 pixel blocks in some interlaced modes. The block size is normally determined from the size of transform which is 8×8 DCT (Discrete Cosine Transform) in most cases. However, in the work towards future standards, the usage of smaller blocks like 4×4 pixels and other transforms like 4×4 Hadamard transform has been suggested. Since the effect of different block scanning orders is better visualized using 4×4 pixel blocks, this case will be used as an example in
FIG. 1
, where it is shown that each macroblock
12
defines an area of 4×4 blocks
14
, each block consisting of 4×4 =16 pixels
16
.
In most encoding schemes, the macroblocks
12
are encoded one macroblock at a time beginning from left to right within each image frame
10
. Similarly, the blocks
14
are encoded one block at a time beginning from left to right within each macroblock
12
. For clarity purposes, the encoding, or scanning, order of the blocks
14
in the macroblock
12
is numbered
1
-
16
in ascending order.
This block scanning order, however, does not take into account the availability (or lack thereof) of neighboring macroblocks for prediction purposes. As mentioned previously, the high degree of content redundancy within an image frame and between consecutive image frames allows a block to be extrapolated or predicted based on the surrounding or neighboring blocks. More specifically, the redundancy allows for prediction of pixels or of DCT coefficients or other transform coefficients that are used in the encoding scheme to represent the color and luminance of the pixels in the blocks. The motion of the pixels may also be predicted based on this redundancy. In general, the larger the amount of information that can be used for prediction, the more accurate the prediction of the pixels in a block will be, and hence the residual prediction error will be smaller and cheaper to encode, resulting in higher compression ratio and higher quality of the transmitted video.
With inter-coding schemes, prediction is based on the entire previously encoded image frames. With intra-coding schemes, however, only the previously encoded macroblocks within the same image frame or within the same segment of a segmented image frame are available, e.g., those macroblocks that are located above or to the left of the same row of the macroblock currently being encoded. However, not all macroblocks have the same number of neighboring macroblocks. Indeed, in some cases there are no blocks available above or to the left of the macroblock being encoded. For these macroblocks, therefore, it is desirable to be able to adjust the block scanning order so as to maximize the prediction utility of any previously encoded macroblocks that may be available.
Some prior art methods, such as that which appears to be disclosed in European patent No. EP-836328, adapt the scanning order of the DCT coefficients after detecting the image edges within the picture. Other prior art methods, such as that which appears to be disclosed in U.S. Pat. No. 4,951,157 and Japanese Patent No. 01177786, try to reduce the block boundary effects by using certain symmetrical scanning orders.
Yet other prior art methods, such as that which is described in a proposed addition Annex V of ITU-T Recommendation H.263, use a fixed, modified scanning order for motion vectors for all blocks when a certain data partitioned slice mode is used.
However, these prior art methods fail to maximize the prediction utility of any previously encoded blocks that may be available by adjusting the scanning order of the blocks.
A more complete appreciation of the present invention and the scope thereof can be obtained from the accompanying drawings (which are briefly summarized below), the following detailed description of the presently-preferred embodiments of the invention, and the appended claims.
SUMMARY OF THE INVENTION
The present invention is directed to a method or an apparatus for maximizing the prediction utility of previously encoded macroblocks by adjusting the scanning order of the blocks within a macroblock to be encoded. Where no previously encoded blocks are available above the macroblock being encoded, the alternative scanning orders allow for maximum utility of previously encoded blocks located to the left of the macroblock being encoded. Where no previously encoded blocks are available either above or to the left of the macroblock being encoded, the alternative scanning orders allow for maximum utility of information from blocks that are presently being encoded in the same macroblock. The particular scanning order used may be signaled implicitly based on the location of the macroblock being encoded, or it may be signaled explicitly by code words within the bitstream containing the encoded block information. In the case where the scanning order is to be signaled explicitly by a code word, the optimal scanning order may be chosen from among one or more scanning orders for any particular picture and macroblock.
In one aspect, the invention is related to a method for improving coding efficiency in a video signal encoding protocol. The method comprises dividing a video signal into a plurality of macroblocks to be encoded, each macroblock containing a plurality of blocks, determining a block scanning order for each of the macroblocks to be encoded based on any previously encoded macroblocks adjacent thereto, and encoding the plurality of macroblocks in accordance with the determined block scanning order.
In another aspect, the invention is related to a system for encoding a video signal. The s

Affiliated with

Also associated with

Rating

Alternative block orders for better prediction does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Alternative block orders for better prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alternative block orders for better prediction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3227411