Technique for Reducing Transmission Error Propagation in an Adaptively Predicted DPCM Video Encoder

The present invention relates generally to digital encoding of pictorial information and, in particular, to a technique for encoding a video signal using adaptively predicted differential pulse code modulation wherein propagation of transmission errors is reduced at the receiver by intentionally introducing a "leak" in the predictors used in the system.

In U.S. Pat. No. 2,905,756 issued to R. E. Graham on Sept. 22, 1959, a method and apparatus for reducing the bandwidth needed to transmit a television or other pictorial information signal is disclosed wherein the difference between the original signal and a prediction thereof is quantized and encoded. The prediction is formed adaptively by analyzing each of several possible predictions in light of previously encoded data and selecting the one prediction that should produce the best result. Each of the possible predictions is also formed by reference to previously encoded information available at both the transmitter and receiver, thus eliminating any need to encode predictor selection data.

Adaptive or switched predictor differential pulse code modulation (DPCM) systems of the type suggested by Graham are extremely sensitive to errors which may occur during transmission of the encoded information between the transmitter and receiver, since the effect of any transmission error is cumulative and propagates so as to contaminate all succeeding information until correction is achieved through additional processing logic. Error accumulation occurs because only the differences between each prediction and the original signal are encoded, and the pictorial information is decoded by summing all of the differences in an integrator or adder. To reduce propagation of transmission errors, some prior art systems incorporate check characters in the encoded data, and upon detection of an error, use various correlation techniques to locate the point of occurrence of the error and correct it. Because redundant information must be added to the signal, some additional bandwidth is required in the transmission medium and the receiver must be outfitted with error detection and correction logic, which can be costly.

In another approach designed to avoid the propagation of transmission errors, it has been found advantageous to intentionally introduce an attenuation or "leak" in the predictors used in both the encoder and decoder so that the predictions statistically tend to converge toward a preselected constant value. The technique works well for certain fixed predictor DPCM systems because the error in an erroneously decoded picture element eventually decays to zero in future picture elements instead of propagating indefinitely. The technique does not work as well in adaptive predictor DPCM systems, because the erroneously decoded intensity value may also affect the predictor selection rule. In this event, the decoder and the encoder use different rules to process future picture elements causing distortion in the received picture.

In view of the foregoing, it is the broad object of the present invention to improve the encoding of pictorial information so as to reduce the propagation of errors that may occur in the transmission medium between transmitter and receiver. Specific objects are to reduce error propagation in an adaptively predicted DPCM system without undue distortion of the reconstructed picture and without adding significantly to the bandwidth required for transmission or the logic needed for error detection and correction.

The foregoing and additional objects are achieved in an adaptively predicted DPCM encoding technique arranged in accordance with the present invention by introducing a leak in the predictor which is a function of the local characteristics in the area of the picture being encoded. This technique reduces error propagation and yet does not significantly distort the picture if no transmission errors occur. Conceptually, the technique can be viewed as introducing a leak not only in the predicted value but also in the predictor function so that the encoder and decoder each make a prediction having a value partly influenced by the optimum switched predictor and also by a fixed predictor using intensity values for pels in the neighborhood of the presently processed element.

A full appreciation of the features and advantages of the present invention will be obtained by consideration of the following detailed description, when read in light of the accompanying drawings in which:

FIG. 1 is a block diagram of an adaptively predicted DPCM encoder constructed in accordance with the principles of the present invention;

FIG. 2 is a more detailed block diagram of the encoder of FIG. 1; and

FIG. 3 is a block diagram of a decoder for use with the encoder of FIGS. 1 or 2.

FIG. 1 is a block diagram of a predictive DPCM encoder constructed in accordance with the principles of the present invention. The encoder includes an analog-to-digital converter 100 which receives an input signal in analog form on line 101 and converts the signal to a series of samples on line 102. The input signal can be obtained by scanning a picture or other visual information along a series of generally parallel scan lines and converting the picture intensity information to electrical form. The samples generated by converter 100 represent the intensities x.sub.i,j at a plurality of picture element (pel) locations within the picture, where the subscripts indicate the specific location corresponding to each sample. The first subscript i represents the horizontal position of the picture element along a given scan line, and the second subscript j refers to the vertical position or particular scan line on which the pel is located. For reference purposes, the picture element presently being processed is referred to as the i,j.sup.th pel, the preceeding pel is the (i-1,j).sup.th pel, and so on. In a typical encoder, the sampling and scanning rates are adjusted to achieve about 256 samples per line and the same number of lines per frame. Where the input video information is already available in digital form, as for example, at the output of a computer or other processing apparatus, A/D converter 100 is not required.

At the heart of the encoder of FIG. 1 is an adaptive or switched predictor circuit 105 which forms a prediction p.sub.i,j on line 106, of the value of each input intensity sample x.sub.i,j. Ideally, each prediction is an exact replica of the true value x.sub.i,j then present on line 102. However, due to predictor processing limitations and the non-stationary nature of the input signal, prediction errors generally occur. These errors designated e.sub.i,j are formed in a subtractor circuit 107 and applied to a quantizer 108 which provides the encoder output e.sub.i,j on line 109. Quantizer 108 usually has a nonlinear input/output characteristic so as to further compress the error signal before transmission to a remote location. Each intensity prediction p.sub.i,j output from predictor 105 is generated adaptively using information derived from previous outputs from the encoder. For this purpose, each quantized error value e.sub.i,j is combined with the previously formed prediction p.sub.i,j in an adder circuit 110 to generate a reconstructed version y.sub.i,j of the input signal x.sub.i,j. These reconstructed values are then input to a delay elment 111 (typically a tapped delay line) arranged to store reconstructed intensity values for a plurality of picture elements in the neighborhood or vicinity of the picture element being processed. These neighborhood values are coupled to a predictor logic circuit 113 which, generally speaking, combines various ones of the previous values to yield several predicted values, and then selects the optimum prediction which best represents the input signal value. The output of predictor logic 113, designated x.sub.i,j, is then applied to a leak circuit 114 which "distorts" the predicted value in the manner explained below, to reduce the effects of transmission error propagation. The output of circuit 114 is thus the final prediction p.sub.i,j used to form the error signal e.sub.i,j, while the output x.sub.i,j of predictor logic 113 is an intermediate prediction.

In prior art predictive encoders of the type described above, the leak introduced in circuit 114 was strictly and solely predetermined by knowledge of fixed encoder characteristics such as the total range of possible intensity values, such that the output of leak circuit 114 was the only variable which influenced the predicted value x.sub.i,j generated by logic 113. In accordance with the present invention, leak circuit 114 also receives inputs (on lines 115) from delay element 111, such that the leak used to form the predicted value p.sub.i,j is influenced by and a mathematical function of certain ones of the stored reconstructed values of pels in the neighborhood of the element being processed.

The present invention will be better appreciated by considering a prior art "leaky" predictor found in an adaptive DPCM type described by Graham and others in more detail. In such predictors, the intermediate prediction x.sub.i,j output from logic 113 is given by:

where Q is the total number of possible predictions and q=1, 2. . . Q. The best prediction is chosen adaptively, according to a decision rule which is a function of previous reconstructed values (y). The encoder and decoder both use the same decision rule to switch between and select the optimum prediction, but the decoder decision may be contaminated by transmission errors which distort the values e.sub.i,j and thus lead to distortion in (y) as well.

In one simple example used by Graham, two possible predictions are given by: ##EQU1## The first prediction F.sub.1 is seen to be derived from the reconstructed intensity of the pel immediately above the present pel and the second prediction F.sub.2 is derived from the reconstructed intensity of the pel immediately to the left of the pel being processed. Selection of the best prediction is made according to a contour sensitive rule which searches for picture edges. Thus, F.sub.1 is selected if: ##EQU2## and F.sub.2 is selected otherwise. This selection rule assumes that there is a continuim of intensity values in most pictures, and that if an edge exists (with the accompanying discontinuity in intensity), a prediction should not be made using picture elements which lie across the edge. It is to be understood that other more sophisticated combinations of neighboring pels can be used to form predictions, and that different combinations of additional reconstructed pel intensity values can be used to select the best prediction.

As stated previously, adaptive prediction generally results in more accurate coding of the image, but a serious problem arising from adaptation is the response of the system to transmission or channel errors. The effect of an error propagates over a larger area of the picture when an adaptive predictor is used than when a fixed predictor is used. Increased propagation occurs because transmission errors not only (i) contaminate the values of the elements used by the receiver in forming the different predictions but can also (ii) cause an error in the receiver's choice of the best prediction. The second effect is potentially more grievous, since the transmitter and receiver then use different choices for the prediction function, a result that, once started, can propagate.

The fixed "leak" used in the prior art reduces the effect of transmission errors by attenuating the predictor output by a constant .alpha.,(0.ltoreq..alpha..ltoreq.1) and by adding a constant bias term so that p.sub.i,j assumes the form:

where .eta. is a constant in the range of possible intensity values, and is usually preselected as the mean value of the highest and lowest values attainable by x.sub.i,j.

Specifically, if the picture intensities can range between 0 and 255 levels of brightness, .eta. can be chosen as 128; other choices may, however, give better subjective results, depending upon context and system non-linearities.

Analysis of the fixed leak specified in equation (4) reveals that the prediction p.sub.i,j can be viewed as a weighted combination of locally inferred and globally given knowledge of the input signal, since multiplication by .alpha.<1 decreases the effect on the prediction p.sub.i,j of the intermediate prediction x.sub.i,j and the bias term causes the output to tend toward the constant .eta.. The error e.sub.i,j which is transmitted to the receiver is the quantized version of the error term having the form:

which can be rewritten as:

Equation (6) consists of a first DPCM term (x.sub.i,j -x.sub.i,j) which represents the difference between the value of one sample of the input signal and the corresponding predicted value for that sample and a second PCM term [x.sub.i,j -.eta.] which is proportional only to the input signal itself. As .alpha. varies from 1 to zero, the significance of the first term is decreased, while the second term becomes more important. This kind of attenuation of the predicted value x.sub.i,j trades error propagation with transmission rate. For .alpha..apprxeq.1, the system is essentially DPCM having a low rate but large susceptability to error. Conversely, for small .alpha., the system approaches a PCM arrangement wherein a high transmission rate is needed but in which an error in one PCM value will not affect the value of succeeding samples. It should also be noted that this fixed leak technique does not address the problem of the selection of the best prediction, and therefore is a remedy only for the first problem (i) noted above.

In accordance with the present invention, the effect of transmission error propagation in an adaptively predicted DPCM encoder is further reduced by arranging circuit 114 so as to introduce a leak in the prediction x.sub.i,j which is a function of reconstructed intensity values (y) of pels in the neighborhood of the pel being processed. This technique is equivalent to attenuating (or leaking) the criteria or rule used to select the best prediction as well as the predicted value itself. With this arrangement, the intermediate prediction x.sub.i,j output from logic 113 is first modified to yield a prediction

where F(y) is a fixed predictor. The modified prediction x'.sub.i,j is then leaked according to equation (4) as in prior art encoding techniques, to yield the prediction p.sub.i,j. A reasonable choice for F(y) is the mean of all of the possible predictions for the presently processed sample. For the example given above,

indicating that the reconstructed intensity values for pels in the vicinity of the presently processed pel are used in selection of the best prediction.

It is to be noted from equation (7) that as .beta. varies from one to zero, the encoder changes from fully adaptive DPCM to non-adaptive DPCM. The smaller the value of .beta., the closer the predictor is to being fixed, thereby reducing the effect (ii above) of error propagation due to use of the wrong predictor. However, with a fully fixed predictor, the advantages in fidelity gained through a switched predictor are lost.

Equation (7) may be combined with equation (4) to yield the following expression for the output of predictor 105:

From equation (9), it is seen that a prediction derived in accordance with the technique of the present invention is a function of (1) the switched predictor x.sub.i,j of the type used by Graham and others, (2) the local intensity F(y) in the neighborhood of the (i,j).sup.th pel, and (3) a constant (1-.alpha.).eta. having a value derived from knowledge of the range of picture intensity values.

A more detailed circuit diagram of one embodiment of the encoder of FIG. 1 is shown in FIG. 2 wherein elements identical to those in FIG. 1 bear the same numerical designations. In this embodiment, delay element 111 consists of three serially connected delay circuits 201, 202 and 203. Circuits 201 and 203 each provide a delay equal to one sample interval, while circuit 202 provides a delay L-1 equivalent to the time needed to scan one complete line of picture information, less one sample interval. With this arrangement, the output y.sub.i-1,j-1 of circuit 203 is the intensity of the picture element on the previous scan line which is immediately to the left of the present pel, assuming scanning from left to right. The output y.sub.i,j-1 from circuit 202 is the intensity of the picture element immediately above the present pel, and the output y.sub.i-1,j from circuit 201 is the intensity for the pel to the left of the present pel on the same scan line.

Still using the Graham type predictive encoder described by equations (2) and (3), the differences specified in equation (3) are formed by applying the outputs of circuits 201 and 203 to a first subtractor 210 and applying the outputs of circuits 202 and 203 to a second subtractor 211. The magnitudes of the differences formed by the subtractors are compared in a comparator 215, which provides a high output when the output from subtractor 210 exceeds the output from subtractor 211 and a low output otherwise. With the output of comparator 215 high, the inequality of equation (3) is not satisfied, and the second prediction F.sub.2 is selected by enabling AND gate 220 to pass the output y.sub.i,j-1 from circuit 202 to OR gate 230. When the output of comparator 215 is low, the inequality of equation (3) is satisfied and the F.sub.1 prediction is selected. In this case, the output of inverter 216 is high, enabling AND gate 221 to pass the output y.sub.i-1,j from circuit 201 to OR gate 230. The output of this OR gate is x.sub.i,j, the intermediate prediction which corresponds to the output of a prior art encoder of the type described by Graham.

In accordance with the invention, leak circuit 114 responds to both the output from OR gate 230 and inputs received from delay element 111. If equation (8) is used to derive local intensity values for pels in the neighborhood of the pel being processed, circuit 114 may include an averager circuit 245 comprising an adder 240 for receiving the outputs y.sub.i-1,j and y.sub.i,j-1 from delay circuits 201 and 202 and a multiplexer 241 for multiplying the sum by the factor of one-half to yield the local average value F(y).

The output of multiplier 241, corresponding to a "fixed" prediction, and the output from OR gate 230, corresponding to a "switched" prediction, are applied to a first attenuator or leak stage 255 consisting of multipliers 250 and 251. In this circuit, x.sub.i,j is attenuated by a factor .beta. while F(y) is attenuated by a factor 1-.beta.. The outputs of multipliers 250 and 251 are then combined in an adder 252 to yield x'.sub.i,j, as in equation (7). This value is next attenuated in a second stage 265 by multiplying x'.sub.i,j by a factor .alpha. in a multiplier 260. The product of the preselected constant .eta. and the factor (1-.alpha.) is concurrently formed in multiplier 261, and the outputs of multipliers 260 and 261 combined in an adder 262 to yield the desired prediction p.sub.i,j in accordance with equation (9). This prediction is applied to both adder 110 and subtractor 107 as in FIG. 1.

A decoder constructed in accordance with the present invention is shown in block diagram form in FIG. 3. The encoded error signal e.sub.i,j received on line 301 is applied to one input of an adder 302 which receives a second input p.sub.i,j from predictor 305 which is identical to predictor 105 of FIG. 1. This output of adder 302 is the reconstructed version y.sub.i,j of the input signal, which is applied to the input of predictor 305 and to a digital-to-analog converter 300 which performs the complementary function of converter 100 of FIG. 1. The output of converter 300 is the recovered video signal which may be applied to a desired display or utilization device.

Predictor 305, like predictor 105, includes delay element 311, predictor logic 313 and a leak circuit 314, all identical to the corresponding circuits in FIG. 1. Leak circuit 314 receives inputs from delay circuit 311 on lines 315 and is arranged to provide an output in accordance with equation (9). Further description of the decoder is not necessary, as those skilled in the art will appreciate the similar nature of the receiver and transmitter in DPCM systems.

The advantages of the present invention were confirmed in simulations using various test photographs, and some of the results obtained are described and depicted in applicants' article entitled "Reduction of Transmission Error Propagation in Adaptive Prediction DPCM Pictures" which appeared in the July-August 1979 issue of the Bell System Technical Journal beginning at page 1413. FIG. 1 in that article depicts the effect of a 10.sup.-4 channel bit error probability on a picture being processed using the adaptive coding technique described by Graham. When a fixed predictor leak is introduced in the processing in accordance with equation (4), the distortion due to transmission error propagation improves somewhat as shown in FIG. 3. However, significant errors still exist as shown in FIG. 4 of that article. When the present invention is used with values of .alpha.=15/16, .beta.=3/4 and .eta.=128, the received picture is as shown in FIG. 5; the significant decrease in transmission error propagation is seen clearly by comparison of FIG. 6 with FIG. 4. For different values of .alpha. and .beta., the received picture is shown in FIG. 7, and FIG. 8 again shows the almost total elimination of distortion due to transmission error propagation. The effects of the present invention on quantization noise are depicted in FIGS. 9-12 of the BSTJ article. These figures indicate that in the absence of transmission errors, the distortion introduced by processing in accordance with equation (9) is not harmful to picture fidelity. In this regard, the quantizing noise shown in FIGS. 10 and 11, which correspond to the values of .alpha. and .beta. used to derive the pictures of FIGS. 5 and 7, respectively, are no worse than the quantizing noise shown in FIG. 9 for adaptive prediction without any leak, and FIG. 10 for prediction leak only.