Reconstruction of Quantized DPCM or PCM Signals

1. Field of the Invention

The present invention relates generally to reconstruction of signals that were encoded using pulse code modulation (PCM) or differential pulse code modulation (DPCM) techniques and, in particular, to reconstruction of such signals which have been quantized.

2. Description of the Prior Art

In most communication systems that employ any type of digital encoding (e.g., pulse code modulation (PCM) and differential pulse code modulation (DPCM) systems), samples of the signal being processed are quantized before being encoded and transmitted to the receiver. Quantizers in PCM encoders assign a particular one of `N` representative values to each sample, depending upon which of a corresponding `N` mutually exclusive quantization levels brackets that sample value. In a DPCM encoder, the quantizer assigns a representative value to the prediction error formed by subtracting a predicted version of each sample from its true value. To increase transmission efficiency, the representative values output from the quantizer are typically encoded with unique code words, such that more frequently occurring representative values are encoded with shorter words. At the receiver, each code word is decoded by assigning the appropriate representative value (hereafter sometimes referred to as "normal representative value") to the quantized quantity i.e., sample value in PCM or error value in DPCM. As stated previously, the normal representative value for each received code word is typically selected within the range defined by the upper and lower limits of the particular encoder quantization level into which the quantized quantity fell. The selection of quantizer representative values has traditionally been determined by considerations of minimum mean-square quantization error.

From the foregoing description, it is seen that in conventional PCM systems, no use is made of the spatial or temporal correlation of neighboring samples, either at the transmitter for coding, or at the receiver for reproduction. In DPCM systems, previously transmitted values are typically used for coding at the transmitter. However, little or no use of correlation has been made at the receiver for reproduction. This essentially "wastes" information available at the receiver and results in a larger reconstruction error. In addition, use has not been made of the fact that the range of quantizer input values defined by the upper and lower limits of the different quantizer levels is a known quantizer characteristic.

The present invention uses the correlation between the present PCM or DPCM quantized sample and its past (and, if desired, future) neighbors, the normal representative value, as well as information regarding the quantizer characteristics (i.e., the upper and lower limits of the different quantizer levels) for generating a more accurate reconstructed value, either at the receiver or at the transmitter. This in effect "reassigns" the normal representative value, based upon previously wasted information.

More specifically, the reconstructed value is determined by (1) selecting a set of samples which are temporally or spatially related to the present sample, (2) determining the range in which an "improved" reconstructed value of the present must lie, based upon knowledge of the quantizer characteristics, and (3) locating the improved reconstructed value within the range, as a function of reconstructed values of the present sample and the selected related samples, which were calculated using normal representative values.

The present invention can be used only at the receiver, to allow more accurate recovery of the original sample value with no additional information transmission. It can also be used at the transmitter in a DPCM encoding system to improve the reconstructed values of neighboring samples used in predicting the value of the present sample. The technique can reduce mean square reconstruction error, at the expense of somewhat increased processing and storage, the costs of which have been considerably reduced of late.

The present invention will be more readily appreciated by reference to the following detailed description when read in light of the accompanying drawing in which:

FIG. 1 is a block diagram of a conventional DPCM transmitter and a receiver constructed in accordance with the present invention to provide improved reconstruction of encoded samples;

FIG. 2 illustrates the locations of elements (pels) in a picture that may be processed by the apparatus of FIG. 1; and

FIG. 3 illustrates one possible arrangement of quantization levels in the quantizer of FIG. 1.

The present invention will first be described as used in the receiver of a DPCM video transmission system, although it is to be understood that a PCM encoder/decoder could also be used, and that the present technique is applicable to other signals (such as speech) which exhibit high temporal or spatial correlation. In a basic DPCM system, as shown in FIG. 1, a prediction p of the value I.sub.X of the "present" sample applied on input line 101 is made in predictor 104 from previously reconstructed sample values. For this purpose, predictor 104 typically includes a memory or delay element and combinational logic, not shown but well known in the art. The input samples may be derived by scanning a picture (FIG. 2) along a series of generally parallel scan lines such as "previous" scan line 201, "present" scan line 202 and "next" line 203, and sampling the resulting intensity signal, so that each sample represents the intensity at a particular picture element (pel) location. Notationally, the intensity of presently processed pel (X) on line 202 is I.sub.X, the intensity of the previous pel (A) is I.sub.A, and so on.

Using one specific arrangement for predictor 104 the intensity I.sub.X of pel X may be predicted using the reconstructed intensity value I.sub.A of the preceding picture element (A) on the same scan line. The hat symbol " " denotes that an intensity value has been reconstructed from a previously quantized value, and thus will include quantization error. The predictor output is combined with the next error value output from quantizer 105 to form the reconstructed value I.sub.X for pel (X), which is input to predictor 104. Predictor 104 may alternatively be arranged to average the reconstructed values of pels I.sub.A and I.sub.D on the present and previous scan lines, respectively, to obtain the prediction for I.sub.X, or other combinations of pels A, B, C and D which have already been processed may be used to form the prediction.

In any event, a prediction error value e is obtained in subtractor 106 by forming the difference between the predicted value p output from predictor 104 and the actual intensity value I.sub.X of pel X. The error value is then quantized by a quantizer 105 which determines into which one of a set of mutually exclusive discrete amplitude levels the error value falls. Quantizer 105 generates a representative value e.sub.r for each of the quantized levels, and encoder 110 is arranged to generate a unique code word indicative of each representative level. Thus, if so-called "previous element" prediction is used, the code word generated in encoder 110 represents the quantized value I.sub.X -I.sub.A. If other predictors are used, the code represents the quantized difference between I.sub.X and p, the predicted value output from predictor 104. Code words which represent different quantizer representative values are typically binary words of either fixed or variable length, with shorter words representing more frequently occurring values.

Quantizer 105 can be better understood by reference to FIG. 3. As shown therein, the prediction error value "e" output from subtractor 106 may fall within one of a series of N mutually exclusive levels such as levels e.sub.1, e.sub.2, e.sub.3 and e.sub.4. Each level includes a range of error values having a lower limit e.sub.rL and an upper limit e.sub.rU ; thus level e.sub.1 includes values between e.sub.1L and e.sub.1U while level 302 includes values between e.sub.2L and e.sub.2U. Generally, if each pel can have an intensity value between 0 and I.sub.max, then the error e may have a value between -I.sub.max and +I.sub.max. For each of the different quantizer levels, quantizer 105 produces a unique representative value e.sub.r. For example, the representative value for level e.sub.1 is e.sub.r1, the representative value for level e.sub.2 is e.sub.r2, and so on. Encoder 110 is arranged to provide a code word which is recognized at the receiver as being associated with a particular representative value.

The receiver portion of the DPCM system of FIG. 1 includes a decoder 151, a conventional DPCM decoder 150 as well as additional processing circuitry for deriving an improved reconstructed version of the original signal in accordance with the present invention. Decoder 151 is arranged to recognize each incoming code word and generates the corresponding normal representative value e.sub.r which is applied to one input of adder 152 within DPCM decoder 150. The second adder input is derived from a predictor 154 which corresponds to predictor 104 in the transmitter portion of the system and which produces a prediction p of each incoming sample based upon previously processed samples. The output of adder 152 is the reconstructed value I.sub.X =p+e.sub.r of the original input sample.

The operation thus far described is conventional, and may be summarized by an example assuming previous element prediction. Thus, when the intensity of the present pel X is applied on input line 101, its predicted value is I.sub.A (the reconstructed value of the previous pel) and the error value e applied at the input of quantizer 105 is I.sub.X -I.sub.A. If this value is within level e.sub.1 in FIG. 3, the quantizer output is e.sub.r1, and a code word indicative of that value is coded by encoder 110 and applied to channel 103. The error value e.sub.r1 is also combined in adder 107 with the output of predictor 104 to yield the reconstructed value I.sub.X of the present sample, which is used to predict the value of the next sample corresponding to pel F.

At the receiver, the incoming code word is interpreted as being associated with representative value e.sub.r1, and that value is applied to one input of adder 152, the other input of which the predicted value p, which in this example is I.sub.A, the reconstructed value of the previous sample. The adder output I.sub.X =e.sub.r1 +I.sub.A is the conventional reconstructed value of the present sample, and is made available on line 155 as well as being applied to predictor 154 for use in processing subsequent samples.

The present invention takes advantage of the fact that the output e.sub.r from decoder 151 implicitly carries with it information that the error value e quantized in the transmitter was within a particular quantizer level, and that e.sub.r can thus have a value in the range between e.sub.rL and e.sub.rU determined by the quantizer characteristics. This means that the reconstructed value I.sub.X must lie in the range between (p+e.sub.rL) and (p+e.sub.rU). It also takes advantage of the fact that information as to an appropriate position within this range can be determined from previously processed samples spatially or temporally related to the present pel, such as pels A-D. Furthermore, by including suitable delay in RAM 165 (described below) information regarding subsequently processed samples F-I can also be used.

One specific technique for computing an improved reconstructed intensity value I.sub.X ' for pel X in accordance with the present invention is as follows:

(1) A set of picture elements such as pels A-D and F-I in FIG. 2 which neighbor the presently processed element X is selected.

(2) The range in which the improved reconstructed value must lie, namely between (p+e.sub.rL) and (p+e.sub.rU) is determined from knowledge of the encoder quantizer characteristics.

(3) The improved reconstructed value for pel X is then assigned within the range, as a function of the normal reconstructed values for pel X and the surrounding pels A-D and F-I, (as computed in the conventional DPCM receiver 150 of FIG. 3).

The actual assignment of I.sub.X ' within the range can be determined by defining variables n and m as the number of surrounding picture elements having normal reconstructed values less than and more than the normal reconstructed value (p+e.sub.r) of pel X, respectively. Then, the new reconstructed value I.sub.X ' for pel X is computed as ##EQU1##

From Equation (1), it is seen that the reconstructed value I.sub.X ' is a weighted average calculated using at least one of the endpoints of the range (p+e.sub.rL) to (p+erU) of the quantizer level which brackets the normal reconstructed value (p+e.sub.r). The weights are determined by the values of m and n, which are derived from the relationship of the surrounding picture elements to (p+e.sub.r). Since the improved reconstructed value is assured to be within the range (p+e.sub.1) to (p+e.sub.2), the filtering action performed by Equation (1) does not blur picture edges significantly. If desired, it is possible to select a subset of the surrounding picture elements which have characteristics similar to pel X in computation of n and m, to insure that the averaging does not produce any noticeable artifact.

If the values of n and m are close, and the values change only slightly from sample to sample, the reconstruction derived using Equation (1) may show jumps from sample to sample. This provides a dithering effect that may in fact improve picture quality. However, other reconstruction weighting strategies that do not result in such sudden jumps can be used, in lieu of the relationship of Equation (1). For example, the reconstructed intensity value I.sub.X ' may be computed as in Equations (2) or (3) below: ##EQU2##

The improved reconstructed value specified in Equation (1) is generated within a postprocessor designated generally at 190 by first applying the decoded normal representative value e.sub.r (output from decoder 151) and the reconstructed intensity value I.sub.X =p+e.sub.r to a range calculation circuit 160 which includes a read-only memory (ROM) 161 and an arithmetic computation circuit 162. ROM 161 acts as a simple look-up table, and outputs the lower and upper limits e.sub.rL and e.sub.rU of the quantizing level which includes e.sub.r as its normal representative level. Arithmetic computation circuit 162 can then easily compute, for each pel, the upper and lower limits of I.sub.X ', namely, (p+e.sub.rL) and (p+e.sub.rU) and store these values along with I.sub.X '=p+e.sub.r in a random access memory 165.

When the reconstructed intensity values for selected surrounding pels have been entered in RAM 165, intensity estimator 170 computes the improved reconstructed value in accordance with Equation (1), or alternatively, Equations (2) or (3). Address logic 171 is arranged to obtain from RAM 165 the reconstructed intensity value I.sub.X for the presently processed pel (line 180) and the reconstructed value (such as I.sub.A) for each of the selected series of surrounding pels (line 181). The values are compared in comparator 182, and used to advance m register 183 or n register 184, depending on whether the reconstructed value of the neighboring pel exceeds I.sub.X. When all selected neighboring pels have been processed, the contents of registers 183 and 184 are applied to arithmetic computation circuit 185, which receives the values of (p+e.sub.rL) and (p+e.sub.rU) from RAM 165 and computes I.sub.X ' in accordance with Equation (1). Registers 183 and 184 and address logic 171 are then cleared for the next computation cycle.

Computer simulations performed to evaluate the present invention used two still frames each of which included an array of 256.times.256 pels each having an intensity value represented by an 8-bit word. Two predictors, A (previous elements), A+(D/2) (Planar, two dimensional) were used in combination with three symmetric, even level quantizers Q.sub.1, Q.sub.2 and Q.sub.3. The positive decision levels for the quantizers were: ##EQU3##

The mean absolute reconstruction error (i.e., the magnitude of the difference between the original and the reconstructed intensity value) was calculated for both pictures using both conventional DPCM and the improved reconstruction technique of the present invention. Three cases were considered, depending on the number of neighboring pels used. Case 1 used two neighbors, A, and F (FIG. 2); Case 2 used four neighbors, A, F, C, H; and Case 3 used all eight neighbors, A-D and F-I. The table below shows the mean absolute reconstruction error for the various cases.

It is noted that use of information derived from a larger number of neighboring pels improves the performance of the postprocessing technique of the present invention. Larger improvements in mean absolute error are obtained for quantizers that have coarse inner levels. Thus, when quantizers Q.sub.1 or Q.sub.3 were used, we obtained about 20 percent improvement over the standard DPCM. Although the mean absolute error does not show improvement with quantizer Q.sub.2, the subjective quality of the picture was improved considerably, due to improved reconstruction of the low contrast areas as well as edges.

It is noted that quantizers for intraframe predictive coders usually contain fine inner levels to reduce the visible granular noise in flat areas. However, if only a small number of levels can be used, then one has to trade off granular noise for other distortions such as edge busyness. The present invention enables use of a quantizer with coarse inner levels so that better edge reproduction is possible, since granular noise would be mitigated to a large extent.

While the technique described above relates to postprocessing at a receiver to obtain better reconstruction, it is also possible to use the technique for preprocessng at a transmitter which includes a DPCM encoder. This is because, in DPCM systems, reconstructed values used for prediction are processed in circuitry (within box 120) identical to the DPCM decoder 150 found in the receiver. It is therefore possible to use a preprocessor 191 (identical to postprocessor 190) to derive an improved reconstruction for each sample and then use this improved reconstructed value (on line 192) for prediction in lieu of the output of predictor 104. However, only previously transmitted value can be used for improved reconstruction at the transmitter. Thus, for an intraframe predictor, information derived from pels A-D can be used. If a frame memory is provided to allow processing of pels in the previous frame (e.g., pels F, G and H), then even more substantial improvement is possible.

Various modifications and adaptations of the present invention may be made by those skilled in the art. For this reason, it is intended that the invention be limited only by the appended claims. For example, as stated previously, while the processing of a DPCM encoded video signal was described as an example, the present invention could be used with an audio, video or other temporal or spatially correlated signal processed using PCM or DPCM techniques. The invention can be implemented in general purpose hardware under software control or numerous other hardware arrangements which will be well known to those skilled in the art.