Apparatus for encoding a television signal to be transmitted

The present invention relates to the field of television signal encoding. In particular, the invention relates to an encoding algorithm, encoder and decoder enabling transmission of broadcast quality television signals in the form of an embedded code.

In the television studio there is a continuing trend towards the replacement of analogue, composite picture handling by digital manipulation of separate luminance and chrominance components. This is performed at the internationally agreed rate of 166Mbit/s , with a further 50Mbit/s representing the redundant picture blanking. A full television "package" however must also comprise audio channels, teletext, synchronisation and control signals which further elevate the source rate. Independently digitisation of the European telecommunications networks is taking place based upon a binary hierarchy which stretches from the trunk rate of 140Mbit.s to the rate of a single telephone conversation. So if the broadcaster wishes to convey pictures between studios, to radio transmitters or perhaps directly to the home using these links he is faced with the task of converting his source rate to confirm to one of the levels in the telecoms multiplex hierarchy. In particular he will wish to use the most economical level which allows him to achieve adequate quality reproduction.

The broadcaster can however identify two distinct levels of reproduction fidelity required from a coding algorithm, these are "contribution" quality for interstudio traffic and "distribution" quality for traffic destined for the home. Each suggests a coding algorithm optimised for different criteria and each a quite different transmission rate. Contribution material should be of studio resolution and of such numerical fidelity that it can withstand post processing, for example by standards conversion, chromakey or multiple passes through the same coding algorithm. We might aim for a transmission rate of 68Mbit/s for this. Distribution material (and perhaps news contribution from remote locations) need not be post-processed, but instead conveyed directly to the viewer. Here we can be sure that successive codes will not be encountered and so we are free to exploit the psychovisual redundancy present in the images and aim for a channel rate of 34Mbit/s . This rate is emerging as a popular choice for the proposed exchange of pictures within Europe.

A consequence of having two separate levels of compression is the need to consider transcodability or the ability to convert between levels with the minimum of processing and minimum signal degradation The very least objective of this conversion should be the avoidance of an intermediate reconstruction and recoding operation. Most previous proposals for 34Mbit/s coding, e.g. Westerkamp, D., "Adaptive Intra-\Interframe DPCM Coding for Transmission of Colour TV Signals with 34Mbit\s", <u style="single">Proc. IEEE Int. Zurich Seminar on Digital Comm.,</u> March, 1984,39-45, decimate the luminance signal by 3\4 or 2\3 prior to encoding. Since it is not generally possible to interpolate coded symbols, conversion to the contribution standard will require decoding and recoding. Interpolation by these ratios is clumsy and may even have to be performed in a future home receiver if the manufacturer has sought to be compatible with other broadcast standards. It is an object of the present invention to overcome the above disadvantages and provide an embedded code procedure with improved transcodability.

It is a further object of the invention to provide a fixed rate embedded code whereby the distribution compression is a subset of the contribution coding.

The present invention is set out in the claims and provides an encoding algorithm to enable adaptive interpolation of samples of a television signal at a decoder by the generation of a parameter for each interpolated sample site, the parameter being indicative of the best of the available interpolation schemes at that sample site and enabling feature detection.

The present invention further provides an encoding algorithm to enable adaptive interpolation and adaptive prediction of samples of a television signal at a decoder by the generation of a parameter for each interpolated sample site and of a prediction error signal for each predicted sample site, the parameter being indicative of the best of the available interpolation schemes at that sample site, and the predictor to be used at a particular predicted sample site being determined by the values of the parameter for the surrounding interpolated sample sites.

The present invention still further provides an encoder implementing an encoding algorithm to enable adaptive interpolation and adaptive prediction of samples of a television signal at a decoder by the generation of a parameter for each interpolated sample site and of a prediction error signal for each predicted sample site, the parameter being indicative of the best of the available interpolation schemes at that sample site, and the predictor to be used at a particular predicted sample site being determined by the values of the parameter for the surrounding interpolated sample sites.

The present invention yet further provides a decoder for adaptively interpolating and adaptively predicting samples of a television signal, the decoder receiving a parameter for each interpolated sample site and a prediction error for each predicted sample site, the predictor used by the decoder for a particular predicted sample site being determined by the values of the parameter for the surrounding interpolated sample sites, and the interpolation scheme used by the decoder at a particular interpolated sample site being determined by the value of the parameter for that interpolated sample site.

A preferred emdodiment of the invention is arranged to operate in a system where, contained within a trunk multiplex is a channel of 68Mbit/s capacity, partly carrying the distribution signal and partly additional features such as a secondary luminance error signal, increased chrominance bandwidth or perhaps studio-specific information such as a chromakey keyin signal. To convert between contribution and distribution it is only necessary to demultiplex one 34Mbit/s data steam, and to convert to contribution, no effort is required since the distribution code is already compatible. The embedded approach requires only one code at the studio and permits greater flexibility of routing in a network, because rate conversion can be performed under network control at any remote location.

Let us examine the requirements of a coding algorithm to suit the distribution level of an embedded code for 34Mbit\s :

To avoid multiple decimation\interpolation by difficult factors we must choose a sampling rate whose sample sites correspond exactly to those at the studio rate, i.e. ratios 1, 1\2, 1\3..... are allowed. For colour components studio sampling yields a bandwidth well in excess of the eye's requirement and reduction of 1\2 or 1\4 can be tolerated. For luminance however, nothing but full site retention is permissible since reduction by 1\2 would result in unacceptably "soft" or severely movement-impaired pictures.

Robustness of the coded format to transmission error is important in a signal destined for distribution over many paths. Forward error correction can be applied, but if the errors are correlated, cannot be relied upon to protect an algorithm otherwise prone to chronic disintegration. It has, for example, been popular to adapt the predictor of a predictive coder to better exploit local picture statistics, according to previously received pels, often in the region of edges. While achieving a coding gain under error free conditions, the presence of an error can case a divergence of predictor choice at coder and decoder resulting in catastrophic failure. Even if this is arrested by periodic updating using a fixed intrafield predictor, the viewer would notice a temporary disturbing picture loss. Adapting a predictor according to control data which is transmitted as an overhead prevents total breakdown due to an error and was the approach adopted in Buley, H. and Stenger, L. 1985. "Inter\Intraframe Coding of Colour TV Signals for Transmission at the Third Level of the Digital Hierarchy", <u style="single">Proc. IEEE</u>, 73, 4, 765-772; For our distribution algorithm we would require rapid recovery from an error, which also implies rapid settling at the receiver after switch-on when no previously received pels are available.

The coding advantages which may be obtained by exploiting the inadequacies of the human eye to perceive certain types of impairment cannot be ignored in a low-rate distribution compression algorithm.

In a distribution situation, the ratio of decoders to encoders will be high, the former perhaps being paid for by the consumer. The ratio of decoder to encoder complexity should therefore be low.

Features and advantages of the present invention will become apparent from the following description of preferred embodiments thereof, given by way of example, with reference to the accompanying drawings in which: <ul id="ul0001" list-style="none"><li>Figure 1 illustrates adaptive interpolation according to a preferred encoding algorithm embodying the invention, in which</li><li>Figure 1(a) shows the structure of the set of samples to be predicted according to the preferred encoding algorithm,</li><li>Figure 1(b)(c) and (d) show 2-dimensional repeat spectra which limit the bandwidth which can be preserved free from aliassing using intrafield interpolation to areas which tesellate about the repeat centres shown, the shaded areas represent the maximum bandwidth which can be preserved using a possible fixed interpolate and horizontal and vertical switched interpolators,</li><li>Figure 1(e) shows the combined bandwidth available using switched horizontal and vertical interpolators, and</li><li>Figure 1(f) shows the response of a practical cross-shaped prefilter;</li><li>Figure 2 shows the structure of a simple cross filter suitable for use in the adaptive interpolation of the preferred encoding algorithm for N=2, M=1 (h_n, v_m) = coefficients of horizontal and vertical prototypes;</li><li>Figure 3 shows a picture of boats used to illustrate the action of the preferred encoding algorithm;</li><li>Figure 4 shows the pattern of the two Laplacian descriptors generated for the boat picture of Figure 3 according to the preferred encoding algorithm (the temporal interpolation state is suppressed);</li><li>Figure 5 illustrates adaptive prediction according to the preferred encoding algorithm and shows the points in the boat picture of Figure 3 where the logical function (9) leads to the selection of a vertically orientated predictor;</li><li>Figure 6 shows the generalised form of a visual model suitable for use in the interpolative coding according to the preferred encoding algorithm;</li><li>Figure 7 shows a block diagram of a luminance encoder suitable for implementing the preferred encoding algorithm; and</li><li>Figure 8 shows a block diagram of a luminance decoder suitable for decoding signals encoded according to the preferred encoding algorithm.</li></ul>

In a preferred embodiment of the invention the encoding algorithm is applied to television signals to be transmitted in DPCM form. DPCM is well known in the art and is described, for example, in the Westerkamp article mentioned above.

Before describing in detail the preferred encoding algorithm according to the present invention it will first be summarised.

Source luminance samples are split into two groups according to a grid with a 2 frame structure (see Fig. 1) which separates alternate samples with a line and frame offset. One group is to form an interpolated set, but in order to obtain a higher spatiotemporal resolution than fixed interpolation would permit, a 3-state interplator selection signal is retained at each site. Redundancy is removed from this selection signal and it is conveyed to the receiver. Values of this 3-state selector act as a descriptor at sites surrounding a sample to be predicted (the other group), and control selection of one of a set of 3 dimensional prediction functions, ranging from purely temporal in static areas to contour-adaptive in moving areas. Since the predictor choice is explicitly defined by the descriptors, recovery from channel errors is assured. Prediction error is quantised and coded for transmission.

A third stage in the coding is used to check the quality of the interpolated samples reproduced at the receiver. This is done by locally decoding the transmitted signal at the coder and applying the error signal to a visual model in the manner of an interpolative coding process. The model attempts to locate interpolated samples which have not been reconstructed well enough subjectively, in the context of their surroundings. These are adjusted by the transmission of an error signal which is sufficient to ensure that the model's fidelity criterion is met at the receiver. As with most coders which attempt to exploit subjective criteria, the complexity bias is very much towards the encoder.

Fig. 1(a) shows the structure of the set of samples to be predicted, for convenience nether the interlaced fields nor the true vertical sample spacing is shown. The interpolated set of samples resides between the samples shown. In static areas of the picture, full source resolution can be reconstructed by temporal interpolation.<maths id="math0001"><img file="EP0258367B1_D0001.tif" /></maths>

To ensure that this interpolator will be selected for such areas it is necessary to determine reliably at the source, which samples belong to moving and which to static regions. This segmentation is however, made difficult by two factors, one is that these decisions must be made on a very localised basis (i.e. at every interpolated sample site) and the other is that noise present in the source video results in a wide probablility density function of frame-to-frame differences in static areas. For this reason, attempting to segment by thresholding frame differences is an unacceptable solution. A better approach is to average the modulus of many such differences in a locality in order to reduce the variance of the probability density function due to noise. Thresholding then becomes more reliable. In the context of this coding technique two frames are available at the source for movement detection, one before and one after that currently being coded. The method used involves thresholding a motion indicator µ which is defined over these two frames and a spatial neighbourhood A. For example if the sample to be interpolated is S₁₀ then locality A={S₂₀, S₁₀, S₀₀, S₁₁, S₁₋₁} and<maths id="math0002"><img file="EP0258367B1_D0002.tif" /></maths> where<maths id="math0003"><img file="EP0258367B1_D0003.tif" /></maths>

Application of simple temporal interpolation when µ is greater than some threshold can produce noticeable noise reduction in static areas of noisy source material.

In moving areas this interpolator is not acceptable and intrafield interpolation must be performed. Fig. 1b shows that the 2 dimensional aliased spectra restrict the bandwidth which can be preserved using intrafield interpolation to areas which tessellate about the centres shown. Probably the best that can be obtained is the band shaded in the figure however pictures prefiltered to this extent are unacceptably degraded, so that the difference between static and moving resolution is disturbing. Now consider the bands in (c) and (d) which also tessellate about the alias centres, each preserves half of the source bandwidth but together they can reproduce 3\4 of the source spectrum if switching is performed on a local basis. Studies of the 2 dimensional Fourier spectra of typical images and their edge-orientation histograms suggest that the resulting cross shape (e) should preserve the very large majority of spectral components which are also at or near the horizontal and vertical. There is also some evidence that the eye's resolution is similarly anisotropic. The cross itself, of course, does not tessellate about the alias centres, and since it is derived from a non-linear process, would be meaninglessly represented in such a diagram. One point does arise from this however and that is the need for cross-shaped prefiltering. If not applied, spectral/components in the corners would alias into the low frequency quadrant and become objectionable causing moire patterning in texture and jagged diagonal edges.

Cross-shaped prefilters can be conveniently designed from prototype horizontal and vertical lowpass filters in the following way: <ul id="ul0002" list-style="none"><li>(i) for prototypes<maths id="math0004"><img file="EP0258367B1_D0004.tif" /></maths></li><li>(ii) form separable 2D lowpass filter<maths id="math0005" num="(4)"><math display="block"><mrow><msub><mrow><mtext>F(Z</mtext></mrow><mrow><mtext>h</mtext></mrow></msub><msub><mrow><mtext>, Z</mtext></mrow><mrow><mtext>v</mtext></mrow></msub><msub><mrow><mtext>) = H(Z</mtext></mrow><mrow><mtext>h</mtext></mrow></msub><msub><mrow><mtext>) . V(Z</mtext></mrow><mrow><mtext>v</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0258367B1_D0005.tif" /></maths></li><li>(iii) "modulate" passband to corners of 2D Nyquist interval<maths id="math0006"><img file="EP0258367B1_D0006.tif" /></maths></li><li>(iv) invert filter so that passhand becomes stopband<maths id="math0007"><math display="block"><mrow><msub><mrow><mtext>F˝(Z</mtext></mrow><mrow><mtext>h</mtext></mrow></msub><msub><mrow><mtext>, Z</mtext></mrow><mrow><mtext>v</mtext></mrow></msub><msub><mrow><mtext>) = 1 - F′(Z</mtext></mrow><mrow><mtext>h</mtext></mrow></msub><msub><mrow><mtext>, Z</mtext></mrow><mrow><mtext>v</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0258367B1_D0007.tif" /></maths></li><li>(v) observe that this has the almost separable structure<maths id="math0008"><img file="EP0258367B1_D0008.tif" /></maths></li></ul>

The additional "1" can be individually accounted for and the filter has an essentially separable structure, fig. 2. This is important, since practical filters are large, an excessive amount of hardware would be required to build a non-separable structure. For clarity fig. 2 does not show exploitation of filter symmetry this further simplifies the hardware. So that the filter is only applied in moving areas of the picture it is adapted in the manner mentioned in E. Dubds "The Sampling and Reconstruction of Time-Varying Imagery with Application in Video Systems" (Proc. IEEE, 73, 4, 502-522 1985). The adaption of the cross-filter is arranged so that for a picture or picture area of low movement, where µ is low and temporal interpolation will apply, no cross-filtering is applied and as movement increases and µ increases over a threshold, or series of thresholds, cross-filtering is applied to a greater extent, in a non-linear fashion, until for high µ, where spatial switched horizontal and vertical filtering will apply, the cross-filter is fully operational. The simplest forms of switched horizontal and vertical interplators are:<maths id="math0009"><img file="EP0258367B1_D0009.tif" /></maths>

These have been used by Sabatier, J., et al, 1982 "Coding System for 34Mbit\s Digital Transmission of Colour Television:, Commutation &amp; Transmission, 1, 69-82; and by G. Reitmeier and R. Dischert "A Multiplexed Nyquist Region Approach for High Quality 2:1:1 Digital Video", Proc. 13th Int. TV Symp., Montreux, 1983, 400-408, both authors reporting good results although neither used prefiltering (in the latter case reduction of aliasing with additional interpolators is suggested). We have found that higher order classical Newtonian midpoint interpolation outperforms these interpolators but for our purpose interpolators (7) will be used in the following discussions. To determine which interpolator is better in moving areas, we compute the error resulting from application of each, |S_ij - I<maths id="math0010"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>H</mtext></mrow><mrow><mtext>ij</mtext></mrow></mfrac></mrow></math><img file="EP0258367B1_D0010.tif" /></maths>| and |S_ij - I<maths id="math0011"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>v</mtext></mrow><mrow><mtext>ij</mtext></mrow></mfrac></mrow></math><img file="EP0258367B1_D0011.tif" /></maths>| and select the lower. To code this information we could simply assign a binary state to each choice, however the same information can be conveyed by signalling whether the better interpolation is higher or lower than (I<maths id="math0012"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>H</mtext></mrow><mrow><mtext>ij</mtext></mrow></mfrac></mrow></math><img file="EP0258367B1_D0012.tif" /></maths> + I<maths id="math0013"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>v</mtext></mrow><mrow><mtext>ij</mtext></mrow></mfrac></mrow></math><img file="EP0258367B1_D0013.tif" /></maths>)/2 since surrounding samples are available at the receiver (allbeit with some quantisation error) the interpolator yielding the higher or lower output can be selected. In other words for the interpolators (7) we retain the sign of:<maths id="math0014"><math display="block"><mrow><msub><mrow><mtext>(S</mtext></mrow><mrow><mtext>i-ij</mtext></mrow></msub><msub><mrow><mtext> + S</mtext></mrow><mrow><mtext>i+ij</mtext></mrow></msub><msub><mrow><mtext> + S</mtext></mrow><mrow><mtext>ij-i</mtext></mrow></msub><msub><mrow><mtext> + S</mtext></mrow><mrow><mtext>ij+i</mtext></mrow></msub><msub><mrow><mtext>) - 4S</mtext></mrow><mrow><mtext>ij</mtext></mrow></msub></mrow></math><img file="EP0258367B1_D0014.tif" /></maths> which is the familiar form of the discrete Laplacian operator.

In many low activity picture regions there is no significant difference between one interpolator and another so we are free to choose one which increases the run-length of similar choices. An algorithm has been developed which optimally positions the end of runs amongst these "don't care" choices to minimise some function of interpolation error. This is performed with a single forward and backward pass of each picture line and is real-time implementable.

An algorithm for the optimal positioning of the ends of runs in the 3-state

descriptor segmentation

Consider the situation where we wish to fit the best of three interpolation functions to samples along a scan line and wish to choose the best functions in regions of arbitrary choice, so that choice run-lengths are maximised and entropy minimised. <ul id="ul0003" list-style="none"><li>(i) At each sample compute some function of the error resulting from application of each interpolator I^H, I^V, I^T (here for example f(E) = E²)<maths id="math0015"><math display="block"><mrow><msup><mrow><mtext>f(E</mtext></mrow><mrow><mtext>H</mtext></mrow></msup><msup><mrow><mtext>) = (S-I</mtext></mrow><mrow><mtext>H</mtext></mrow></msup><msup><mrow><mtext>)²  f(E</mtext></mrow><mrow><mtext>V</mtext></mrow></msup><msup><mrow><mtext>) = (S-I</mtext></mrow><mrow><mtext>V</mtext></mrow></msup><msup><mrow><mtext>)²  f(E</mtext></mrow><mrow><mtext>T</mtext></mrow></msup><msup><mrow><mtext>) = (S-I</mtext></mrow><mrow><mtext>T</mtext></mrow></msup><mtext>)²</mtext></mrow></math><img file="EP0258367B1_D0015.tif" /></maths></li><li>(ii) Is one interpolator significantly better than either of the others? i.e. is the difference greater than some threshold T? If "yes" this sample must be replaced by the best interpolation function. If "no" compute the penalty in applying the previous significant choice for each of the functions and accumulate this discrepancy.</li></ul>

example

<tables id="tabl0001" num="0001"><img file="EP0258367B1_D0016.tif" /></tables><ul id="ul0004" list-style="none"><li>(iii) Determine the minimum value of the Σ′s for each function. In the example, this means that if a significant I^V interpolation is found to follow our run of undefined choices the optimum partition is between samples 22 &amp; 23 and if a significant I^T interpolation follows the optimum partition is between samples. It may be convenient to implement this algorithm in 2 passes of the line, one forward and one in reverse.</li><li>(iv) In general this algorithm can be extended to cover any function f, any number of interpolations and a variable value of T (say determined by the masking function).</li></ul>

The resulting 3-state signal is run-length coded for transmission. An example showing just the 2 Laplacian states in fig. 4. The value of the conversion from simple direct interpolator switching is now apparent in the ability of the Laplacian zero crossings to convey information about significant picture edges. It is interesting to note the similarly between this and Marr's "primal sketch" model in human vision (Marr and Hildreth "Theory of Edge Detection" Proc. R. Soc. Lond. B, 1980, 207, 187-217). The value of this new interpolator switching signal as a feature detector makes feasible an encoding system where temporal interpolation is dispensed with entirely. Any loss in picture quality is counterbalanced by the savings that would be made by dispensing with frame memories. An example of such an encoding system could use a 2-dimensional intrafield coder with 2-state logical descriptors for 68Mbit\s transmission of studio quality TV, or at a higher rate for HDTV transmission.

The 3-state descriptor is transmitted to the decoder in advance of the surrounding predicted samples, this provides a sketch of the locality describing static areas and edges in moving areas. This description is now able to control the adaption of the predictive coding process - notice that descriptors are available for the future and the past. Let us examine the causal neighborhood of elements just prior to the coding of S₀₀ : (P_ij : previously predicted and reconstructed pels, D_ij : values of the 3-state descriptor)<img file="EP0258367B1_D0017.tif" />

Because the descriptors have only 3 states we can express any locality as a logical function in 3-state variables and use this function to select one of a large number of predictors. For example if interpolations surrounding S₀₀ are all temporal, then we apply a purely temporal prediction. As an example of spatial prediction consider the logical expression:<maths id="math0016"><math display="block"><mrow><mtext>(D₁₂ = D₀₁ = D₁₀ = D₀₋₁ ≠ D₋₁₂ = D₋₂₁ = D₋₁₀ = D₋₂₋₁)</mtext></mrow></math><img file="EP0258367B1_D0018.tif" /></maths> or<maths id="math0017"><math display="block"><mrow><mtext>D₁₂ = D₂₁ = D₁₀ = D₂₋₁ ≠ D₋₁₂ = D₀₁ = D₋₁₀ = D₀₋₁)</mtext></mrow></math><img file="EP0258367B1_D0019.tif" /></maths> which determines a vertical edge and applies at points indicated in fig. 5. At first sight it may appear that prediction by this process is upset by the striations in Laplacian descriptors due to artificial extensions of run-lengths. This is not so since runs are only extended in low activity regions. The previous sample prediction suggested by a horizontal striation will be as good as (if not better than) any other in these regions. The ruggedness of the technique to channel errors comes from the fact that the predictors are explicitly chosen by a particular logical function and not recursively dependent on previously received predictive samples. Recovery from corruption of either descriptor information or prediction information is guaranteed.

The prediction function applied for a particular logical function is designed by assessing the covariance of the predicted sample location with previous samples in the neighbourhood where the logical function applies, over a set of image sequences. In principle any, size of neighbourhood may be used and logical functions can be stored in a ROM or minimised and programmed into a PLA.

Also in principle it is possible to include logical functions of descriptors from other frames, this makes possible motion compensated predicition. Movement-compensated prediction is possible if the descriptor signal can be tracked from frame-to-frame in real-time. The strength of the system to recovery from errors is preserved. This is not the case in recursively adaptive movement-compensation schemes which have been published. The size of ROM necessary to contain the complete set of possible predictors may however be impractical.

It may be seen that the logical "=" in (9), which corresponds to an exclusive-NOR function, is actually performing the same operation as Marr's (see above) AND-gate model of human edge orientation detection (his fig. 9).

Histograms of interpolation error, even due to 2 dimensional interpolation alone, show a remarkably high concentration about zero despite the fact that an open-loop process has been employed so far. Most of the interpolation errors which are present occur where the localised samples are simultaneously changing their slope in two dimensions, because our interpolators cannot respond to second-differences. These will also tend to be regions where visual masking is operating.

Our adaptive interpolator can therefore form a very good basis for an interpolative receiver-model coding strategy (J. Limb "Picture Coding: The Use of a Viewer Model in Source Encoding", BSTJ, 52, 8, 1271-1302, 1973). To realise this we locally decode the transmitted symbols to reconstruct a received picture at the encoder and compute the coding error due to both interpolated and predicted components. This error at the interpolated pels is "viewed" in the context of the background picture itself by a visual model which attempts to detect visible picture impairment. If an offending interpolation is found, a differential term is generated and coded to improve the subjective reproduction of that pel in the receiver. This improved interpolation is also incorporated back into the visual model because its quality has a bearing on the visibility of future interpolation errors.

Visual models for detecting coding impairments generally account for three main aspects of vision: spatio-temporal filtering; luminance intensity thresholds; and masking. Fig. 6 shows such a model, where the visual filter may be considered to contain a non-linearity which accounts for changes in background luminance. A general model may well be unnecessarily complex to characterise the distortions due to a specific coding algorithm however. A first attempt at this was made by Limb (see above) whose visual model was a simple linear lowpass filter, an advantage of the linearity assumption being that the two filters of fig. 6 can be reduced to one, processing only the coding error.

Limb proposed a "free-running" interpolative coding method, which although not real-time implementable, produced a saving in coding entropy of some 20% over previous-element DPCM for the same subjective quality. He does however report similar performance with his "grid" algorithm, where samples are alternately predictively coded and interpolated in one dimension. This latter approach overcomes some of the implementabiliy problems inherent in the former. Netravali (A. netravali "Interpolative Picture Coding Using a Subjective Criterion", 1977 IEEE Trans. Comm., 25, 5, 503-508) made significant improvements to the "free-running" approach by using better interpolation, by incorporating masking into the visual model and by adapting the visual filter spread with his masking function. This resulted in a reduction in coding entropy by almost 40% over subjectively identical DPCM with his test images. The justification for adapting the visual filter was that it has been shown that the visibility of errors is lower if the spectral band of the background and errors are close to each other. In other words, in low activity areas high frequency error noise would be more visible suggesting that the filter should have a small spread and conversely for high activity regions. A consequence of the use of a single filter operating on the error is that masking effects must be determined directly from the background and not as in fig. 6. Netravali's masking function however, incorporates a weighted spread of signal slopes in a 3x3 neighbourhood which may itself be thought of as an approximation to visual filtering.

Although details of the visual model of the coder have yet to be determined, it should be noted that the interpolation is 3 dimensional and significantly better than has been used before, a "grid" structure is used which makes for easier implementation of the visual filter and masking effects can be exploited temporally as well as spatially because previous-frame source samples are available. Adapting a (one dimensional) visual filter to encompass large spreads (Netravali's best used 3, 5, 7, 11 elements) does cause some implementational difficulties because of the need to consider the effect of adjusting an interpolated pel dependent on the visibility of future interpolation errors. A true minimum for the number of interpolated elements requiring adjustment can only be found by iterative analysis of the whole scan line which is impractical. To illustrate the problem consider a one dimensional filter containing the following 7 error terms:<maths id="math0018"><math display="block"><mrow><mtext>ε (P₃₀) ε (I₂₀) ε (P₁₀) ε (I₀₀) ε (P₋₁₀) ε (I₋₂₀) ε (P₋₃₀)</mtext></mrow></math><img file="EP0258367B1_D0020.tif" /></maths>

If the filter is adapted to have spread 3 (low activity areas) the advantage of a "grid" algorithm is felt and it is only necessary to consider the adjustment of I₀₀ in the context of ε(P₁₀), ε(I₀₀) and ε(P₋₁₀). In "free-running" algorithms there is no regular structure of predicted pels and it would be necessary to consider adjusting any or all of the terms in the filter. Now assume that our filter is adapted to include the 7 terms above, a decision has been made whether to adjust I₂₀ and a decision on I₀₀ is required. This will involve some parallel considerations of the potential adjustment of I₋₂₀ two conditions are fairly clear: <ul id="ul0005" list-style="none"><li>A if interpolative error at I₀₀ is acceptable with I₋₂₀ interpolated: do not adjust I₀₀.</li><li>B if interpolative error at I₀₀ is not acceptable even if I₋₂₀ were adjusted: adjust I₀₀.    The difficulty is how to treat case C:</li><li>C the interpolative error at I₀₀ is acceptable only if I₋₂₀ is adjusted.</li></ul>

Since visibility of ε(I₋₂₀) depends upon ε(I₋₄₀) it will be necessary to adopt some suboptimal decision for case C, the simplest and safest being to choose to adjust I₀₀.

Practicality constraints will either limit the visual filter to 7 terms or otherwise simplify the criteria for the adjustment decision. The filter must be one dimensional with respect of ε(I) terms but can easily include ε(P) terms in a 2 dimensional neighbourhood. There is a further exploitation of our 3-state descriptor signal concerning coding of the quantised adjustment error signal. At interpolated points requiring adjustment we have already reconstructed what is most probably the best of the three functions available, the inferior interpolations however are very likely to act as a pointer showing in which direction the adjustment applies. Because this considerably influences the probability distribution of quantiser states it can be used in the assignment of entropy codes to these states.

A coding algorithm has been described for the transmission of distribution quality broadcast television at 34Mbit/s which can form the basis of an embedded code for providing a numerically higher fidelity at 68Mbit/s . The technique is a hybrid of interpolative and predictive coding both of which are explicitly controlled by a 3-state descriptor signal, transmitted in place of alternate source samples. This ensures a rapid recovery from the effects of channel errors. The channel capacity expended on this descriptor is justified by exploiting it in three ways, first it defines adaptive interpolation of the omitted samples, second it controls inter\intraframe-contour adaptive prediction and third it is used to control assignment of entropy codes to quantised errors which are used to adjust subjectively inadequate interpolated pels. An important aspect of the algorithm is that when channel capacity is insufficient to convey the highest quality reproduction, a model of the human visual system is used to partition available capacity for minimum subjective distortion.

Any form of coding may be applied to the descriptor, predictive error, or interpolative error.

An efficient form of transmitting the interpolation error is to interleave it with the prediction error. A spare state in the quantiser can be assigned to the signalling of this.

Provision is made for the occasional transmission of PCM words to eradicate "frozen" errors is static areas.

Chrominance coding is performed by a decimation operation to a reduced density sample pattern and coded using either pure predictive and interpolative coding using the luminance descriptors to control the process.

The addition of any form of enhancing data to make the system achieve a rate of 68Mbit\s or any other higher rate is allowed for. This is fundamental to the embedded structure for which this code is designed.

A diagram of the luminance coder implementing the preferred encoding algorithm is shown in fig. 7 (F denotes a frame delay). The decoder however is simpler than most adaptive DPCM decoders because of the explicit nature of the control function - this is important for distribution applications. Implementation is also eased because the predictive loop and frame delays are only operating on half of the input samples.

This latter feature makes the encoding system according to the present invention particularly attractive as a method of encoding high definition television signals.

In the preferred encoder the fill level of the output buffer is used to partly control the crossfilter adaption. This ensures that when a picture contains only small amounts of movement, full resolution can be retained in these areas. Emergency control to prevent rate-buffer overflow is also provided by changing the adaptive quantiser at coder and decoder to have a coarser structure. This too is controlled by the rate buffer fill-level.

A diagram of a luminance decoder suitable for use with the preferred encoding algorithm is shown in fig. 8.

Although described for a particular transmission rate and sampling structure this encoding algorithm can be used with any which permits use of switched interpolation. Any interpolation function may be used, in fact classical Newtonian midpoint interpolation has been shown to improve performance over a simple two-term average. These are of the general form:<maths id="math0019"><math display="block"><mrow><msup><mrow><mtext>∇</mtext></mrow><mrow><mtext>n</mtext></mrow></msup><mtext>S½ = O</mtext></mrow></math><img file="EP0258367B1_D0021.tif" /></maths> For linear interpolation this yields (n=2):<maths id="math0020"><math display="block"><mrow><msub><mrow><mtext>I</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> = (S</mtext></mrow><mrow><mtext>i-1</mtext></mrow></msub><msub><mrow><mtext> + S</mtext></mrow><mrow><mtext>i+1</mtext></mrow></msub><mtext>)/2</mtext></mrow></math><img file="EP0258367B1_D0022.tif" /></maths> (as described) And for higher orders (eg. n=4)<maths id="math0021"><math display="block"><mrow><msub><mrow><mtext>I</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> = (-S</mtext></mrow><mrow><mtext>i-3</mtext></mrow></msub><msub><mrow><mtext> + 9S</mtext></mrow><mrow><mtext>i-1</mtext></mrow></msub><msub><mrow><mtext> + 9S</mtext></mrow><mrow><mtext>i+1</mtext></mrow></msub><msub><mrow><mtext> - S</mtext></mrow><mrow><mtext>i+3</mtext></mrow></msub></mrow></math><img file="EP0258367B1_D0023.tif" /></maths>

This system permits retention of all source sampling sites (no decimation) and therefore allows a distribution quality signal to be embedded in a contribution quality signal at a higher rate and with higher numerical fidelity.

The above described system has a number of features listed below. It is considered that each of the features is novel and all combinations and subcombinations are also novel in relation to the transmission and\or reception of digital signals representing television pictures: <ul id="ul0006" list-style="none"><li>(a) The combination of a non-stationary line quincunx subsampling structure with the switched interpolation and filtering;</li><li>(b) The use of this cross-shaped filtering with switched interpolation;</li><li>(c) The transformation which permits use of any interpolator switching signal as a feature detector (here Laplacian edge detector);</li><li>(d) The use of this edge detection signal, transmitted as an overhead, to control a prediction in a robust way;</li><li>(e) The use of a read-only-memory to implement this prediction adaption ( this structure alone has significant advantages in the implementation o this and similar algorithms for coding HDTV signals where coding speed is vital);</li><li>(f) The use of a visual model in this interpolative coding technique and its control by the rate buffer fill-level;</li><li>(g) The algorithm for optimal positioning of the 3-state descriptor segmentation;</li><li>(h) The algorithm is able to detect still picture areas using the motion detector described. In such regions the temporal interpolation results in noise reduction;</li><li>(i) The descriptors can be used to recognise predictable picture areas by a simple logical function, this can be used to adapt between different entropy code word allocation in a robust way.</li></ul>

The entropy code allocation in (i) should not be confused with entropy code allocation in the interpolative coding part of the algorithm, which is based upon interpolation values obtained from the three possible interpolators at the receiver. This is described in the text.