Video coder providing implicit or explicit prediction for image coding and intra coding of video

A predictive video coder performs gradient prediction based on previous blocks of image data. For a new block of image data, the prediction determines a horizontal gradient and a vertical gradient from a block diagonally above the new block (vertically above a previous horizontally adjacent block). Based on these gradients, the encoder predicts image information based on image information of either the horizontally adjacent block or a block vertically adjacent to the new block. The encoder determines a residual that is transmitted in an output bitstream. The decoder performs the identical gradient prediction and predicts image information without need for overhead information. The decoder computes the actual information based on the predicted information and the residual from the bitstream.

BACKGROUND OF THE INVENTION 
A variety of protocols for communication, storage and retrieval of video 
images are known. Invariably, the protocols are developed with a 
particular emphasis on reducing signal bandwidth. With a reduction of 
signal bandwidth, storage devices are able to store more images and 
communications systems can send more images at a given communication rate. 
Reduction in signal bandwidth increases the overall capacity of the system 
using the signal. 
However, bandwidth reduction may be associated with particular 
disadvantages. For instance, certain known coding systems are lossy, they 
introduce errors which may affect the perceptual quality of the decoded 
image. Others may achieve significant bandwidth reduction for certain 
types of images but may not achieve any bandwidth reduction for others. 
Accordingly, the selection of coding schemes must be carefully considered. 
Accordingly, there is a need in the art for an image coding scheme that 
reduces signal bandwidth without introducing perceptually significant 
errors. 
SUMMARY OF THE INVENTION 
The disadvantages of the prior art are alleviated to a great extent by a 
predictive coding scheme in which a new block of image data is predicted 
from three blocks of image data that preceded the new block. For this new 
block, an encoder examines image data of blocks that are horizontally and 
vertically adjacent to the new block. The encoder compares the image data 
of each of the two adjacent blocks to image data of a third block 
positioned horizontally adjacent to the vertically adjacent block 
(diagonally above the new block). From these comparisons, a horizontal and 
a vertical gradient is determined. Based on the values of the gradients, 
the encoder predicts the image data of the new block to be the image data 
of the horizontally or vertically adjacent block most similar to it. The 
encoder then determines a residual difference between the predicted value 
of the image data and the actual value of the image data for the new block 
and encodes the residual. A decoder performs an inverse prediction, 
predicting image data for the new block based upon horizontal and vertical 
gradients and adding the residual thereto to reconstruct the actual image 
data of the new block. This process is lossless. 
The implicit video encoder of the present invention is particularly suited 
to code highly textured images. In flat areas, the performance advantages 
are more modest. Other video coding schemes, such as those employing 
explicit coding, may be more efficient when coding these flat image areas. 
Accordingly, the present invention includes an embodiment wherein an 
encoder may select among the implicit coder of the present invention and 
other coding schemes to achieve the highest coding efficiency possible.

DETAILED DESCRIPTION 
FIG. 1(a) shows an encoder 100 constructed in accordance with a first 
embodiment of the present invention. An analog image signal is presented 
to the encoder 100. The image signal is sampled and converted to a digital 
signal by an analog to digital ("A/D") converter 110 using techniques 
known in the art. The A/D converter 110 generates a digital image signal 
for a plurality of pixels of the image. Alternatively, the image signal 
may be presented to the encoder as a digital image signal; in this case, 
the A/D converter 110 is omitted. 
The digital image signal is input to a processing circuit 120. The 
processing circuit 120 may perform a host of functions. Typically, the 
processing circuit 120 filters the image data and breaks the image data 
into a luminance signal component and two chrominance signal components. 
Additionally, the processing circuit 120 groups image data into blocks of 
data. Where the digital input signal represents information for a 
plurality of pixels in a scanning direction, the digital output of the 
processing circuit 120 represents blocks of pixels, for example, data may 
be blocked into 8 pixel by 8 pixel arrays of image data. The processing 
circuit 120 outputs image data on a macroblock basis. A macroblock 
typically consists of four blocks of luminance data and two blocks of 
chrominance data. The processing circuit 120 may also perform additional 
functions, such as filtering, to suit individual design criteria. 
The output of the processing circuit 120 is input to a transform circuit 
130. The transform circuit 130 performs a transformation of the image 
data, such as discrete cosine transform ("DCT") coding or sub-band coding, 
from the pixel domain to a domain of coefficients. A block of pixels is 
transformed to an equivalently sized block of coefficients. Coefficients 
output by DCT coding generally include a single DC coefficient; the 
remainder are AC coefficients, some of which are non-zero. Similarly, 
coefficients output by sub-band coding represent image characteristics at 
a variety of frequencies; typically, many coefficients from sub-band 
coding are very small. The transform circuit 130 outputs blocks of 
coefficients. 
A quantizer 140 scales the signals generated by the transform circuit 130 
according to a constant or variable scalar value (Q.sub.p). The quantizer 
140 reduces bandwidth of the image signal by reducing a number of 
quantization levels available for encoding the signal. The quantization 
process is lossy. Many small coefficients input to the quantizer 140 are 
divided down and truncated to zero. The scaled signal is output from the 
quantizer 140. 
The prediction circuit 150 performs gradient prediction analysis to predict 
scaled DC coefficients of each block. The prediction circuit 150 may pass 
scaled AC coefficients or, alternatively, may predict AC coefficients of 
the block. In a preferred mode of operation, the prediction circuit 150 
selects between modes of predicting or passing AC coefficients; in this 
case, the prediction circuit 150 generates an AC prediction flag to 
identify a mode of operation. The prediction circuit 150 outputs a DC 
residual signal, AC signals (representing either AC coefficients or AC 
residuals) and an AC prediction flag. 
A variable length coder 160 encodes the output of the prediction circuit 
150. The variable length coder 160 typically is a Huffman encoder that 
performs run length coding on the scaled signals. A bitstream output from 
the variable length coder 160 may be transmitted, stored, or put to other 
uses as are known in the art. 
In the encoder 100, the prediction circuit 150 and the quantizer 140 
perform functions which are mutually independent. Accordingly, their order 
of operation is largely immaterial. Although FIG. 1 illustrates output of 
the quantizer 140 as an input to the prediction circuit 150, the circuits 
may be reversed in order. The output of the prediction circuit 150 may be 
input to the quantizer 140. 
A decoder 200, shown in FIG. 1(b), performs operations that undo the 
encoding operation described above. A variable length decoder 260 analyzes 
the bitstream using a complementary process to recover a scaled signal. If 
a Huffman encoder were used by the encoder 160, a Huffman decoder 260 is 
used. 
A reconstruction circuit 250 performs the identical gradient analysis 
performed in the prediction circuit 150. The DC residual signal is 
identified and added to a predicted coefficient to obtain a DC 
coefficient. Optionally, the reconstruction circuit 250 may identify the 
AC prediction flag and, on the status of that flag, interprets the AC 
information as either AC coefficient information or AC residual 
information. In the event that AC residual information is present, the 
reconstruction circuit 250 adds the residual signals to corresponding 
predicted signals to obtain AC coefficients. The reconstruction circuit 
250 outputs coefficient signals. 
A scalar circuit 240 multiplies the recovered signal by the same scalar 
used as a basis for division in the quantizer 140. Of course, those 
coefficients divided down to zero are not recovered. 
An inverse transformation circuit 230 performs the inverse transformation 
applied by the transform circuit 130 of encoder 100. If a DCT 
transformation were performed, an inverse DCT transformation is applied. 
So, too, with sub-band coding. The inverse transformation circuit 230 
transforms the coefficient information back to the pixel domain. 
A processing circuit 220 combines luminance and chrominance signals and may 
perform such optional features as are desired in particular application. 
The processing circuit 220 outputs digital signals of pixels ready to be 
displayed. At this point the signals are fit for display on a digital 
monitor. If necessary to fit a particular application, the signals may be 
converted by a digital to analog converter 210 for display on an analog 
display. 
FIG. 2 illustrates the structure of data as it is processed by the 
prediction circuit. The data output from the transform circuit represents 
a plurality of blocks organized into macroblocks. Each macroblock is 
populated typically by four blocks representing luminance components of 
the macroblock and two blocks representing chrominance components of the 
macroblock. 
Each block represents coefficients of the spatial area from which the block 
was derived. When a DCT transform is applied, a DC coefficient of DC.sub.X 
of the block is provided at the origin of the block, at the upper left 
corner. AC coefficients are provided throughout the block with the most 
significant coefficients being provided horizontally on the row occupied 
by the DC coefficient and vertically on a column occupied by the DC 
coefficient. 
FIG. 3 shows a detailed block diagram of the prediction circuit 150. The 
quantizer 140 generates scaled DC and AC coefficients. The DC coefficient 
may be scaled (DC=DC/Q.sub.p, typically Q.sub.p =8) and is input to a DC 
coefficient predictor 300. The DC coefficient predictor performs a 
gradient analysis. 
For any block X, the DC coefficient predictor 300 maintains in memory data 
of a block A horizontally adjacent to block X, block C vertically adjacent 
to block X and a block B, that is, a block horizontally adjacent to block 
C and vertically adjacent to block A, shown in FIG. 2. The DC coefficient 
predictor compares a DC coefficient of block A (DC.sub.A) with a DC 
coefficient of block B (DC.sub.B). The difference between the DC 
coefficients of block A and block B is a vertical gradient. The DC 
coefficient predictor 300 also compares a DC coefficient of block C 
(DC.sub.C) with the DC coefficient of block B (DC.sub.B). The difference 
between the coefficients of block C and block B is a horizontal gradient. 
The block associated with the highest gradient from block B is used as a 
basis of prediction. If the vertical gradient is greater than the 
horizontal gradient, it is expected that block A will have high 
correlation with block X, so the DC coefficient predictor 300 employs 
horizontal prediction in which it uses block A as a basis for prediction 
of block X. If the horizontal gradient is greater than the vertical 
gradient, so the DC coefficient predictor 300 employs vertical prediction 
in which it uses block C as a basis for prediction of block X. The DC 
coefficient predictor 300 outputs the DC coefficient of the block used for 
prediction (DC.sub.A or DC.sub.C) to a subtractor 310. The DC coefficient 
predictor 300 also generates a hor/vert signal 320 indicating whether 
horizontal prediction or vertical prediction is performed. 
The subtractor 310 subtracts the DC coefficient generated by the DC 
coefficient predictor 300 from the DC coefficient of block X to obtain a 
DC residual signal for block X. The DC residual may be output from the 
prediction circuit 150 to the variable length encoder 160. 
The process described above is employed to predict coefficients of blocks 
at the interior of the image to be coded. However, when predicting 
coefficients at the start of a new row of a video object plane, the 
previous block for prediction is the last block of the line above under 
the normal process. Typically, there is little correlation between these 
blocks. 
Assume that block Y in FIG. 2 is at the starting edge of a video object 
plane. No block is horizontally adjacent to block Y in the scanning 
direction. Although, image data of a final block in the row above is 
available to be used as the "horizontally adjacent" block, it is not used 
for prediction. Instead, the DC coefficient predictor 300 artificially 
sets the DC coefficient values for a horizontally adjacent block and a 
block above the horizontally adjacent block to a half strength signal. If 
the DC coefficients are represented by an 8 bit word, the DC coefficient 
of these ghost blocks is set to 128. The DC coefficient predictor 300 then 
performs gradient prediction according to the process described above. 
As noted above, the prediction circuit 150 may pass AC coefficients without 
prediction. However, in a preferred embodiment, the prediction circuit 150 
uses the gradient analysis to predict AC coefficients. 
When the prediction circuit 150 predicts AC coefficients, only some of the 
AC coefficients may exhibit high correlation between blocks. In the case 
of DCT transform coding and horizontal prediction, the only AC 
coefficients that are likely to exhibit sufficiently high correlation to 
merit prediction analysis are those in the same column as the DC 
coefficient (shaded in block A). Accordingly, for each AC coefficient of 
block X in the same column as the DC coefficient (AC.sub.X (0,1) to 
AC.sub.X (0,n)), an AC coefficient predictor 330 generates a prediction 
corresponding to the colocated AC coefficient from block A (AC.sub.A (0,1) 
to AC.sub.A (0,n)). The predicted AC coefficient is subtracted from the 
actual AC coefficient of block X at a subtractor 340 to obtain an AC 
prediction residual signal. 
In the case of DCT transform coding and vertical prediction, the only AC 
coefficients that are likely to exhibit sufficiently high correlation to 
merit prediction analysis are those in the same row as the DC coefficient 
(shaded in block C). For each AC coefficient of block X in the same row as 
the DC coefficient(AC.sub.X (1,0) to AC.sub.X (n,0), the AC coefficient 
predictor 330 generates a prediction corresponding to the colocated AC 
coefficient of block C (AC.sub.C (1,0) to AC.sub.C (n,0)). The predicted 
AC coefficient is subtracted from the actual AC coefficient of block X at 
the subtractor 340 to obtain an AC prediction residual signal. The AC 
coefficient predictor is toggled between a horizontal prediction mode and 
a vertical prediction mode by the hor/vert signal 320. Gradient prediction 
of AC coefficients other than those described above need not be performed. 
While correlation of AC coefficients between blocks may occur, it does not 
occur always. Accordingly, prediction of AC coefficients does not always 
lead to bandwidth efficiencies. Accordingly, in a preferred embodiment, 
the prediction circuit 140 permits selection of modes of operation between 
a mode wherein AC coefficient prediction is performed and a second mode 
wherein AC coefficient prediction is not performed. In this latter case, 
AC coefficients from the transform circuit pass through the prediction 
circuit without change. 
Once the residuals are known, an AC prediction analyzer 350 compares the 
bandwidth that would be consumed by transmitting the AC residual signals 
of the macroblock with the bandwidth that would be consumed by 
transmitting the AC coefficients of the macroblock without prediction. The 
prediction analyzer 350 selects the transmission mode that consumes 
relatively less bandwidth. The prediction analyzer 350 generates an AC 
prediction flag signal 360 to indicate its selection. 
Prediction is performed based on "like kind" blocks. When identifying 
blocks for prediction of a block of luminance data, only adjacent blocks 
of luminance data are considered. Any intervening blocks of chrominance 
data are ignored for prediction purposes. When predicting coefficients of 
the chrominance blocks, only like kind chrominance signals are considered 
for prediction. When predicting data for a block of C.sub.r data, one type 
of chrominance signal, adjacent blocks of C.sub.r data are considered but 
intervening blocks of luminance and second type chrominance signal C.sub.b 
data are ignored. Similarly, when predicting data for a block of C.sub.b 
data, a second type of chrominance signal, adjacent blocks of C.sub.b data 
are considered but intervening blocks of luminance and C.sub.r data are 
ignored. 
The prediction circuit 150 may output a DC residual signal, signals 
representing either AC coefficients or AC residuals and an AC prediction 
flag signal. 
An inverse prediction operation is performed in the reconstruction circuit 
250, shown in FIG. 4. For every block X, a DC coefficient predictor 400 
maintains in memory data of an adjacent block A prior to block X, data of 
an adjacent block C above block X and data of a block B prior to block C, 
the block above block X. The DC coefficient predictor 400 compares a DC 
coefficient of block A with a DC coefficient of block B to determine the 
vertical gradient. Further, the DC coefficient predictor 400 compares a DC 
coefficient of block C with the DC coefficient of block B to determine the 
horizontal gradient. If the horizontal gradient is greater than the 
vertical gradient, the DC coefficient predictor 400 generates the DC 
coefficient of block C as a basis for prediction. Otherwise, the DC 
coefficient predictor 400 generates the DC coefficient of block A. The DC 
coefficient predictor 400 also generates a hor/vert signal 420 identifying 
whether horizontal or vertical prediction is used. 
The reconstruction circuit 250 identifies the DC residual signal from the 
input bitstream. An adder 410 adds the DC residual to the DC coefficient 
generated by the DC coefficient predictor 400. The adder 410 outputs the 
DC coefficient of block X. 
In a preferred embodiment, the reconstruction circuit 250 identifies the AC 
prediction flag 360 from the input bitstream. If the AC prediction flag 
360 indicates that AC prediction was used, the reconstruction circuit 
identifies the AC residual signals from the input bitstream and engages an 
AC coefficient predictor 430. A hor/vert signal 420 from the DC 
coefficient predictor identified whether block A or block C is used as a 
basis for prediction. In response, the AC coefficient predictor 430 
generates signals corresponding to the AC coefficients of block A or block 
C in the same manner as the AC coefficient predictor 330 of the predictor 
140. An adder 440 adds predicted AC coefficients to corresponding 
residuals and outputs reconstructed AC coefficients. 
If the AC prediction flag indicates that AC prediction was not used, the 
reconstruction circuit 250 identifies the AC coefficient signals from the 
bitstream. No arithmetic operations are necessary to reconstruct the AC 
coefficients. 
Refinements of the DC prediction may be achieved in a preferred embodiment 
by inducing contribution of some of the perceptually significant AC 
coefficients from the block of prediction to the DC coefficient of block 
X. For 10 example, where block A is used as a basis of prediction, the 
predicted DC coefficient of block X may be set as: 
EQU DC.sub.X =DC.sub.A +(4Q.sub.p /3)*(AC.sub.02A -AC.sub.01A /4) 
where Q.sub.p is the scaling factor of the quantities and AC.sub.02A and 
AC.sub.01A are AC coefficients of block A generated by a DCT transform. 
Similarly, when block C is used as a basis for prediction, the predicted DC 
coefficient of block X may be set as: 
EQU DC.sub.X =DC.sub.C +(4Q.sub.p /3)*(AC.sub.20C -AC.sub.10C /4) 
where Q.sub.p is the scaling factor of the quantities and AC.sub.20C and 
AC.sub.10C are AC coefficients of block C generated by a DCT transform. 
The prediction and reconstruction process described herein is termed an 
"implicit" method because no overhead signals are required to identify 
which of the blocks are used for prediction. In operation, coefficient 
values of blocks A, B and C are known at both the encoder 100 and the 
decoder 200. Thus, the decoder 200 can reconstruct the prediction 
operation of the encoder 100 without additional signaling. In an 
embodiment where the prediction circuit did not select between modes of AC 
prediction, the AC prediction and reconstruction is purely implicit. With 
the addition of an AC prediction flag in a second embodiment, the 
prediction process is no longer purely implicit. 
The encoding/decoding operation of the prediction and reconstruction 
circuit may also be performed in software by a programmed micro processor 
or digital signal processor. 
FIG. 5 illustrates the operation of the software implemented prediction 
circuit. The processor compares the DC coefficient of block A to the DC 
coefficient of block B to determine the vertical gradient (Step 1000). The 
processor also compares the DC coefficient of block C to the DC 
coefficient of block B to determine the horizontal gradient (Step 1010). 
The processor determines whether the vertical gradient is larger than the 
horizontal gradient. (Step 1020). If so, the processor defines the DC 
residual of block X to be the actual DC coefficient of block X less the DC 
coefficient of block A (Step 1030). If not, the processor defines the DC 
residual of block X to be the actual DC coefficient of block X less the DC 
coefficient of block C (Step 1040). 
In the event the processor also performs AC prediction, the processor 
operates as shown in FIG. 6. Steps 1000-1040 occur as discussed above with 
respect to FIG. 5. When the vertical gradient is larger than the 
horizontal gradient, the AC coefficients from block A that are in the same 
column as the DC coefficient are used as a basis for predicting the 
corresponding AC coefficients of block X. Accordingly, for each such AC 
coefficient AC.sub.X (0,1) through AC.sub.X (0,n), block X, the processor 
computes an AC residual set to the actual AC coefficient in block X less 
the corresponding AC coefficient in block A (AC.sub.A (0,1) through 
AC.sub.A (0,n) (Step 1035). 
When block C is used as a basis of prediction, the AC coefficients in the 
same row of the DC coefficients may exhibit correlation between blocks. 
Accordingly, for each AC coefficient AC(i) in the row of block X, the 
processor computes a residual (i) set to the actual AC coefficient in 
block X less the corresponding AC coefficient in block C (Step 1045). 
The processor also determines whether bandwidth savings are achieved by 
predicting the AC coefficients. Once all prediction is done for a 
macroblock, the processor determines whether less bandwidth is occupied by 
the encoded coefficients or the residuals (Step 1050). If the residuals 
occupy less bandwidth, the processor outputs the residuals (Step 1060). 
Otherwise, the processor outputs the coefficients (Step 1070). 
The gradient prediction method of the present invention provides 
significant advantages in that it provides automatic adaptivity to scene 
contents. However, the gradient prediction method is sometimes over 
responsive when coding flat areas with low detail or when coding very 
large, very uniform areas with only a few local variations. Other known 
coding schemes may provide better performance on these occasions than the 
gradient prediction method. Accordingly, in a preferred embodiment, the 
prediction circuit of the present invention is used in tandem with other 
known prediction circuits, shown in FIG. 7(a). Each of the prediction 
circuits receives scaled coefficients from the quantizer 140 and performs 
their respective prediction analyses. A prediction analyzer 180 selects 
the one of the prediction circuits that yields the best compression 
performance. 
In one preferred embodiment, an explicit prediction circuit 170 is provided 
in parallel with the gradient prediction circuit 150. The explicit 
prediction circuit employs a prediction scheme, such as the known "Annex 
I" technique, that provides overhead information in addition to a 
prediction signal identifying a specific prediction direction. The Annex I 
technique is described in a paper entitled "Intra Prediction (T9/T10) and 
DC/AC Prediction Results," authored by T. K. Tan and S. M. Shen (July, 
1996). Both the gradient prediction circuit 150 and the explicit 
prediction circuit 170 output prediction signals to a prediction analyzer 
180. The prediction analyzer 180 selects the prediction circuit that 
yields the greatest overall compression. In the case of the explicit 
prediction circuit 170, however, the prediction analyzer 180 considers 
both the prediction signal and the overhead signal in its efficiency 
computation. The prediction analyzer 180 also generates a signal 
identifying which of the prediction techniques was used. 
In this embodiment, the decoder 200 also possesses an explicit prediction 
circuit 270 in parallel with the gradient prediction circuit 250, shown in 
FIG. 7(b). A prediction analyzer 280 receives a decoded bitstream from the 
variable length coder 260. The prediction analyzer 280 determines from the 
identifying signal generated by the prediction analyzer 180 whether 
gradient prediction or explicit prediction was used at the encoder 100. 
Based upon that determination, the prediction analyzer 280 forwards the 
residual coefficient information to either the gradient predictor 250 or 
the explicit predictor 270. When the coefficient information is provided 
to the gradient predictor 250, the gradient predictor 250 performs the 
inverse operation applied by the gradient predictor 150 of the encoder. 
The gradient predictor 250 then forwards coefficient information to the 
scaler circuit 240. When the prediction circuit provides the prediction 
information to the explicit predictor 270, the explicit predictor 270 
performs an inverse operation of the explicit predictor 170 of the encoder 
100. The explicit predictor then provides coefficient information to the 
scaler circuit 240 for further processing. 
The present invention provides a bandwidth efficient scheme for video 
coding that provides adaptivity to changing video contents. In image areas 
having significant texture or other gradients, the gradient prediction 
mode may prove to be particularly efficient. However, for flat image 
areas, the coder may enter the explicit prediction mode because it may 
prove to possess a coding advantage in these areas. Thus, the coder 
possess two modes of operation that complement each other. At the time of 
this writing, the complementary coding scheme is adopted into the MPEG-4 
Video Verification Model and is being considered for the MPEG-4 video 
standard.