BACKGROUND OF THE INVENTION

This specification describes a picture coding technique based on adaptive subsampling and linear interpolation. The term "slope coding" will be used as a generic name for the technique.

The advent of high-definition television (HDTV) signals has led to a considerable amount of research into ways of reducing the bandwidth of such a transmitted HDTV signal without compromising the picture quality thereof unacceptably.

SUMMARY OF THE INVENTION

The invention is defined in the appended claims to which reference should now be made.

In an embodiment of the invention a video signal is coded by transmitting only selected samples, the samples to be transmitted being selected by determining whether omission of that sample and transmission of the next sample would cause any regenerated samples to differ from the corresponding actual input sample by more than a threshold value. The values transmitted may not be the actual values of the corresponding input samples but are preferably values defining the ends of "best-fit" straight lines chosen to minimise the mean square error. The threshold may be adaptively dependent upon picture content.

A substantial reduction in the bandwidth requirement can be achieved in this way. The video signal is particularly suitable for transmission in analogue form, with an indication of the positions of the transmitted samples being transmitted digitally in the signal multiplex.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will be described in more detail by way of example with reference to the accompanying drawings, in which:-

Figure 1 is a waveform diagram illustrating the principle of operation of a system embodying the invention;

Figure 2 is a waveform diagram illustrating the sample selection process;

Figure 3 is a waveform diagram illustrating a modification using "best-fit" straight lines;

Figure 4 illustrates the lower bound for the signalling rate plotted against the proportion of samples transmitted for two types of bit rate reduction coding of the SPI signal;

Figure 5 illustrates the variation of the threshold T upon mean signal level and slope;

Figure 6 is an enlarged diagram based on Figure 3 illustrating the use of "best-fit" straight lines;

Figure 7 is a block circuit diagram of a slope coder embodying the invention; and

Figure 8 is a block circuit diagram of a best-fit slope parameter generator used in the slope coder of Figure 7.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The coder operates on a sampled picture signal. It selects some of the samples using a method which is described below. The selected samples are transmitted, together with a sample-position indicator (SPI) signal which indicates where in the picture the transmitted samples have come from.

The decoder calculates values for each missing sample by linear interpolation between the last sample transmitted and the next to be transmitted, in the current line of the picture, as illustrated in Figure 1. The straight lines in the diagram illustrate the interpolation process and do not show the exact shape of the decoded analogue waveform.

For simplicity, only the luminance component is considered. The input signal is coverted into digital form at a high enough sampling rate to give a full-resolution picture. Adaptive

subsampling is then carried out by the coder on the digital signal. This process gives rise to an auxiliary data signal which, possibly following a bit-rate reduction process, is transmitted to the decoder. The samples resulting from the adaptive subsampling process will emerge at an irregular rate. They are, therefore, written into a buffer store so that they can be read out at a regular rate for conversion back into analogue form for transmission. A feedback control path is normally necessary between the buffer store and the subsampling process to prevent buffer overflow or underflow.

The coder uses the following method to select which samples to transmit. It transmits the first sample in each line. The samples following it are considered in turn. A sample is only transmitted If a decision not to do so, and to transmit the next sample instead, would result in one or more of the decoder's reconstructed sample values differing from the corresponding input sample value by more than a certain threshold, T, see Figure 2. Thus, the process ensures that the decoded sample values never differ from the input by more than T.

To achieve this, while minimizing the number of transmitted samples, the following procedure is adopted. Each new input sample is considered in turn as a potential transmitted sample. If the resulting Interpolated signal, between the previously transmitted sample and the current sample, fails to meet the threshold criterion, the sample immediately before the current sample is transmitted and the process begins again. The value of T is controlled by feedback from the coder's buffer store.

Using this technique, it is possible to achieve broadcast- quality decoded pictures with a sample rate reduction factor of about 4. Using this value, the SPI signal requires an additional data rate corresponding to about 0.5 bits (or fewer) per input sample.

In principle, the coder ^' has to calculate for each transmitted field a suitable value of T to produce the required sample rate. This value will vary with the source material. One approach to this problem is to use a transmission buffer and to control the value of T by feedback based on the buffer occupancy. Another is

to base the value for the current field on that used in the previous field, code the current field, and then remove a few samples from, or add a few samples to, the coded signal to produce the correct sample rate. POSSIBLE ^' APPLICATIONS

If used for digital YUV bit-rate reduction, a total luminance bit rate corresponding to 2.5 bits per sample could probably be achieved using slope coding. This compares well with the best of broadcast-quality adaptive dpcm systems, which require about 3 bits per sample.

The technique also has possibilities for hybrid systems In which the samples are converted to analogue form for transmission and the SPI signal sent in digital form. A sample rate reduction factor of 4 should enable an analogue HDTV signal, for example, to be transmitted in one 27 MHz fm channel, leaving capacity for a small signalling overhead which could be used for the SPI signal if its data rate requirement could be made sufficiently small. ADDITIONAL BENEFITS

One of the main advantages of slope coding is that the decoder can be very simple, particularly if one bit per input sample is available for the SPI signal. Another advantage particularly important in an all-digital implementation, is that, provided the SPI signal is rugged, the effect of transmission errors is very limited in extent. POSSIBLE REFINEMENTS AND VARIATIONS

There are many possible variations on the use of a simple threshold as the criterion for deciding which samples to transmit. For example, the coder could instead use the mean, or even the accumulated, energy of the error between the input and decoded picture signal.

In the slope coding system described the digital data rate required to indicate the positions of the transmitted samples is rather high. The basic data rate is equivalent to one bit per input sample. The value of each bit is 1 if and only if the corresponding sample (or an approximation to the corresponding sample) Is transmitted. In a slope coding system in which only a moderate degree of bit-rate or bandwidth reduction is required, the

SPI signal could be transmitted in this form, as a fixed-rate signal multiplexed together with the transmitted samples. SPI BIT RATE REDUCTION

In a slope coding system in which a greater degree of bit-rate or bandwidth reduction is required, an additional data rate corresponding to one bit per input sample may be an unacceptably high overhead. Furthermore, as the transmitted sample rate is reduced, the information content of the SPI signal also goes down, because it is increasingly likely to take a value of 0 rather than 1. This reduction in information content can be exploited by transmitting a bit-rate-reduced version of the SPI signal. The bit- rate reduction can be carried out in several ways, of which the following are examples: Method 1 Entropy coding

One way to reduce the data rate is to "entropy code" the data signal. In practice, this would have to be done on groups of data bits.

In this the SPI signal is divided into blocks of M consecutive bits. The non-uniform probability distribution of each of the 2 possible bit-patterns is exploited by assigning to the patterns a variable-length binary code, so that short codes are assigned to highly probable patterns and longer codes to less probable patterns. This can be done by a variety of well-known techniques such as that described by Huffman in "A method for the construction of minimum- redundancy codes", Proc. IRE, September 1952, pp. 1098-1101. Both the complexity and efficiency of this method will increase with M; it is suggested that a value of M approximately equal to the average bandwidth reduction factor would be a reasonable compromise. With this method, as with any others involving variable-length coding, a transmission buffer will be required to smooth out the data rate. The relationship between the feedback from this buffer and the feedback from the transmitted-sample buffer will depend on the multiplexing method and on whether the samples are transmitted in analogue or In digital form. If no use is made of correlation between data bits (apart from the fact that they occur in pairs) and an average proportion p of input samples are -transmitted, then a lower bound on the signalling rate per input sample is:

H = -(l-p/2).[q log ₂ q+(l-q)log ₂ (l-q)] where q = ? ^/2 . l-p/2

This lower bound is plotted in Figure 4 as a function of p.

Very similar results are obtained if the run lengths of line segments are entropy coded. This indicates that there is not much correlation between pairs of data bits. However, a lower theoretical signalling rate can be obtained if the line-to-line correlation of run lengths Is exploited. Figure 4 also shows this lower bound, which is the measured entropy of run lengths conditional on the run length in the previous television line directly above the first sample in the current line segment.

Method 2 Run-length coding

In an alternative coding method the SPI signal can be considered as a series of runs of (possibly zero) O's followed by a 1. The length of each run forms a new signal which can take any value between 0 and some maximum run-length. This new signal can be entropy coded as in Method 1. The degree of bit-rate reduction that can be achieved is about the same in each method. Method 3 Conditional run-length coding

This run-length signal can be entropy coded, but with one of several different variable-length codes being used on each occasion, the choice being determined by the SPI signal in the previous field or line. For example, there might be one variable-length code for each possible length of the run occupied by the sample immediately above (or above and to the right of) the first sample in the run being coded. Thus, the correlation between run-lengths on adjacent field-lines is exploited. Method 4 Run-length coding using fixed-length codes

This method is the same as Method 2 except that a fixed-length code of M hits is used to describe the length of each run. This will not be as efficient as Method 2, but it has one advantage over all the ^' methods involving variable-length coding. There is a fixed relationship between the instantaneous transmitted sample rate and the instantaneous bit rate of the transmitted SPI signal, so that M SPI bits can be packaged together with each transmitted

sample. There is then no need for independent buffer stores for the two kinds of signal. The chosen value of M limits the maximum run-length and this may bring about- a slight penalty in the degree of bandwidth compression that can be achieved. For a hybrid system in which each analogue sample occupies the same channel capacity as two bits of digital data, and for which an overall bandwidth compression factor of 4 is sought, it has been found that M=5 is a fairly sharp optimum.

The two curves given in Figure 4 are useful in providing lower bounds for the signalling rate at two levels of complexity. However, in a simulation of the slope coding system, a simpler coding method was used for the data signal. This was fixed-length code for the run lengths of line segments. The length of this code needs to be chosen carefully, as it determines the maximum run length. For example, if a 4-bit code is used, the maximum run length is 16. At low values of p, limiting the maximum- run length can have a significant effect on the value of p for a given picture quality. It was found that, around p = 0.17 and making the assumptions about transmission of colour difference signals given below, a code length of 5 bits is quite a sharp optimum. This gives a signalling rate equivalent to 2.5p bits per input sample. Adaptive threshold value

A significant further sample rate saving can be achieved by adapting 'the threshold value according to the size of the interpolated slope (which serves as a measure of picture activity) and also according to the mean level of the picture signal in the area being coded. The average transmitted sample rate for a given subjective picture quality can be improved by about 12% by increasing the value of the threshold T according to some measure of picture activity and according to the mean signal level. This can be done because quantization noise is less visible in active areas and also in dark or bright areas of the picture. An effective and readily available measure of activity is the magnitude of the interpolated slope. ^*

Figure 5 shows how, in one example, the value of T depends on the slope magnitude and mean level. The function defined in Figure 5 at zero slope values has high points at black B and white W

and a minimum at a mid-grey G. The function with slope from this grey point is to increase up to a maximum M. The maximum of these two functions is selected at any point.

Further savings can be made in an all-digital implementation if the transmitted samples are themselves coded using simple dpcm, entropy coding, or a combination of two. REDUCTION OF NOISE EFFECTS

The subjective effects of noise on the decoded picture can be disturbing if slope coding has been used on a noisy source picture. To reduce these effects, and to reduce the sample rate still further, the coder can calculate a "best fit" straight line Instead of interpolating between actual sample values, as illustrated In Figure 3.

The transmitted samples are now the end points of each best-fit line segment, .and this is shown more clearly in Figure 6, which is an enlarged diagram based on Figure 3 showing two such straight line sections in full lines. At the end of the first line section the coder starts a new line from the next sample position. It follows that the transmitted samples occur in pairs, although the system could be arranged to transmit single samples in extremely detailed areas of the picture.

In this improvement the decoded samples are derived from a minimum-mean-square-error best-fit straight line approximating the corresponding input samples. Thus, each straight line segment is independent of those on either side and, in general, two samples are transmitted for each line segment.

There are two strategies for dealing with line segments that are one sample long. The first strategy is as follows: If the best-fit straight line through samples y _n > _n + _] _ ^an d ^v _n +2 deviates from the input signal by more than the threshold T, then sample y _n is transmitted and the slope coding process begins afresh with sample y _n+ι • ^ ^e second strategy is to disallow such single- sample segments, as follows: If the best-fit line through , y _n+ n and y _n+ 2 deviates from the Input by more than T, then samples y _n and y _n+ ; _j _ are transmitted and the process begins afresh with y _n+2 .

The second strategy is less efficient than the first but has

the advantage that the benefits of Method 4 above still apply, the only difference being that each package consists of two samples and M SPI bits. One possible way of using Method 4 in conjunction with the first strategy is to make M an even number and to represent a run length of 1 by an M/2-bit code which is not a prefix of any of the other codes. For example, M=4, code 00 signals a single-sample segment, and run lengths of 3 to 14 are signalled by codes 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110 and 1111. Then, each transmitted package consists of two SPI bits and one sample.

It may also be possible to reduce the effects of noise by performing some pre-processing on the source and/or post-processing on the decoded picture. Examples of such processes are noise reduction, filtering and changing the degree of gamma correction applied to the signal. OTHER DIMENSIONAL CODING

The slope coding technique can be used in the vertical or the temporal dimension instead of in the horizontal dimension as described above. That is, instead of comparing with preceding samples on the same line, the comparison may be with corresponding lines on preceding lines on fields respectively. There are indications that, for a given sample rate reduction factor, coding in the temporal dimension produces decoded pictures that are superior to those resulting from coding in the horizontal dimension, particularly in respect of behaviour in the presence of noise on the source.

The technique can also be extended to two and three dimensions, where the indications are that further savings could be made. COLOUR DIFFERENCE SIGNALS

The colour difference (Cr and Cb) component signals can each be slope-coded independently of the luminance. However, this is expensive in channel capacity. One problem is that, with slope coding, there is little to be gained from an initial 2:1 horizontal subsampling of the colour difference components. However, three other methods of reducing the channel capacity occupied by the colour difference signals can be considered:

(i) The Cr and Cb signals could each be vertically filtered, 2:1 subsampled and transmitted on alternate lines.

(ii) In general, the positions of transmitted Cr or Cb samples will coincide with the positions of transmitted luminance samples. The same data signal could therefore be used for both luminance and colour difference. Clearly, the colour difference signals would have to be included in the transmitted-sample selection process. However, experience has shown that the penalty in terms of unnecessary transmitted luminance samples is very low.

(iii) Preliminary experiments have indicated that forcing the slope to zero, and therefore transmitting only one colour difference sample for each line segment, gives acceptable results.

Taking these three techniques together, it may be assumed that the colour difference signals will occupy an analogue transmission channel capacity equal to half of that occupied by the luminance signal, and will add nothing to the digital ^' data rate.

Bearing the above considerations in mind, one can postulate a "package" on which each line segment is described by two luminance samples, one colour difference sample and 5 bits of data. In order to transmit this package in a DBS channel, a proportion p = 0.17 of input luminance samples can be transmitted. CIRCUITRY

Figure 6 gives a block diagram of one possible Implementation of a slope coder, for the particular technique described above. The incoming signal, Y, is written into a shift register containing N elements, where N is the maximum line-segment length. At a given moment, a line segment n samples long is being tested to see if the "best-fit" estimate obeys the threshold criterion. The "best-fit" estimate v- of the samples y. contained in the shift register are derived, via coefficients c-(n), from the mean value and gradient parameter which are calculated from the input samples in the generator of best-fit slope parameters. The resulting error values e. are individually compared with the threshold T, under the control of the control signal generator ^* which ensures that only the errors corresponding to the n most recent samples are tested. The generator of best-fit slope parameters also provides the SPI signal, which may then go through a bit-rate reduction

process as described above and the transmitted samples corresponding to the start and end of each best-fit line segment. A block diagram of the generator of best-fit slope parameters is given in Figure 7.

The decoder is much simpler than the coder. There is no loop and no need to calculate the best-fit slope parameters.

In addition to the basic coder and decoder, a slope coding system, like any other technique involving adaptive subsampling, requires buffer stores and associated feedback control circuits.