Picture Coding Using Pseudo- Random Noise *

Lawrence G. Roberts **


yellow rule

Summary

In order to transmit television pictures over a digital channel, it is necessary to send a binary code which represents the intensity level at each point in the picture. For good picture quality using standard PCM transmission, at least six bits are required at each sample point, since the eye is very sensitive to the small intensity steps introduced by quantization. However, by simply adding some noise to the signal before it is quantized and subtracting the same noise at the receiver, the quantization steps can be broken up and the source rate reduced to three bits per sample. Pseudo-random number generators can be synchronized at the transmitter and receiver to provide the identical "noise" which makes the process possible. Thus, with the addition of only a small amount of equipment, the efficiency of a PCM channel can be doubled.

I. Introduction

IN an attempt to reduce the bandwidth required to transmit PCM (Pulse Code Modulated) television, a simple but effective coding technique has been developed which eliminates the contours and intensity steps characteristic of coarsely quantized pictures.1    In the systems to be considered, an input picture is scanned and at regular sampling intervals a quantity related to the intensity level is coded and sent over a binary channel to a receiver for decoding and display. Each sample is treated as an independent event and coded into a fixed length binary number. Thus, the process requires no memory.

In order to study the visual effects of various methods of coding and decoding, promising techniques were simulated on the TX-2 computer at Lincoln Laboratory, using a facsimile scanner to provide the computer with scanned data. The processed pictures were displayed on the computer scope and photographed to provide a visual evaluation of the coding schemes.

The result of this study was the development of a method using synchronized pseudo-random number generators at the transmitter and receiver, one to add noise to the signal before it is quantized and the other to sub- tract the same noise after the re-conversion to an analog signal. The effect of this process, which uses a standard PCM data link, is to break up the regular steps of digital coding into something resembling additive noise. Thus, when viewed from the terminals, the channel becomes very similar to an analog channel. Pictures so transmitted seem to be more acceptable to people than pictures made using standard PCM without noise.

Thus, when viewed from the terminals, the channel becomes very similar to an analog channel. Pictures so transmitted seem to be more acceptable to people than pictures made using standard PCM without noise. In fact, where it takes from six to seven PCM bits per sample to obtain good pictures, it takes only three to four bits when the dual pseudo-random generators are added. This result agrees with statistical measurements and other experimental work on picture transmission which have shown that it should not be necessary to send more than the equivalent of one to three bits to represent each intensity sample in a picture.2-8   These figures are derived by using codings which take advantage of the redundancy between adjacent elements in pictures. The process developed here does not utilize the picture redundancy directly, rather it presents the data in such a way that the viewer's eye can best take advantage of the redundancy.

A. Test Setup

In order to try out various picture-processing procedures, a facsimile scanner was connected directly to the TX-2 computer9  at Lincoln Laboratory. This arrangement permitted direct read-in of still pictures in digital form. The core memory of the TX-2 was capable of storing several pictures so that versatile processing could be accomplished easily. After processing, the pictures were displayed on the computer's display scope. Polaroid pictures were taken of the scope face to produce the finished picture. This procedure produced pictures of good quality and allowed maximum flexibility in the process.

The facsimile scanner was a modified commercial machine first used by Youngblood.6   It consisted of a drum, 4.25 inches in circumference, rotating at 90 rpm, moving slowly down a 96 turn per inch worm screw. The picture on the drum moved spirally past the scanner at 6.37 inches per second and, at 96 samples per inch, it had a data rate of 614 samples per second.

The scanner consisted of a light source focused on the drum face and a photo multiplier output fed through a cathode-follower to a analog-digital converter. The signal developed by a high contrast picture was about one volt peak-to-peak and, being about half of the analog-digital converter's ten-bit range, produced a nine-bit output.

Resolution was limited by the spacing of the worm screw, requiring one hundredth of an inch spacing of the scan lines. The spot looked at by the photo multiplier was smaller than the scan line spacing so no additional blurring is evident. The photo multiplier was operated well within its dynamic range. Thus the output signal was linear with respect to reflectance.

As indicated in Fig. 1, a sync pulse was sent to the computer once per revolution, and was used to start the sampling pulse burst for the next line. This pulse occurred at the top of the picture. The computer's interval timer was used to send sample pulses to the analog-digital converter at intervals of 1.63 msec for 340 samples, thus scanning 3.5 inches around the drum. The computer then waits for the next sync pulse to scan the adjacent line. The complete scanning of a 340 X 340 picture with nine- bit intensity samples takes about four minutes. The motor could have been speeded up, but for the limited amount of data scanned, this step was not worthwhile.



Fig. 1 - Equipment arrangement for transducing pictorials into andout of a digital computer.

After scanning a complete picture and determining the maximum and minimum intensity levels, the data was compressed to eight bits between these extremes. This step insured that all pictures had the same dynamic range, no matter what their original contrast. All the processing was done with eight bits until the picture was ready for display. In order to produce an intensity modulated picture on the computer display scope, each point was intensified several times, and the light from these intensifications integrated on the camera film. In displaying six bit's worth of intensity information, each point of the 340 X 340 raster was intensified between zero and sixty- three times. Using this method of time modulation to obtain sixty-four intensity levels took about two minutes per picture and, since seven-bit pictures looked no better than six, all the eight-bit data were reduced to six bits for display.

Thus, from the reflectance of the original picture to the light output of the display scope, a linear relationship was established with six-bit precision at each point in the 340 X 340 pictures. The only non-linearity was in the Polaroid film, and this effect appeared to be small. The result was that good quality still pictures could be processed, and samples produced every two minutes.

B. Channel Model

The system to be considered is one in which the transmission link has been specified as a binary channel with a fixed capacity of n bits per sample, and the input delivers an analog voltage for each picture sample. The scanning rate and sampling density determine the actual data rate, but we are concerned only with the most efficient means of coding independent samples into one of the 2n levels and reproducing the analog signal as closely as possible from that level. For the sake of convenience, we will say that the input is between Zero and One. Furthermore, since pictures are so variable, we will assume that all inputs are equiprobable. Our problem is to design the operation of the coder and decoder with these con- straints.

The standard procedure for coding is to present the signal directly to a quantizer which, in this case, would divide the interval from Zero to One into 2n equal sections and assign a code to each section. At the receiver each code would be remapped into a voltage equal to the mean value of the section originating the code. This process produces pictures which have visible steps in intensity unless at least six bits per sample are used. Pictures made with this type of channel are shown in Fig. 2. It is fairly evident that these pictures could stand improvement, and to accomplish this, a compressor and an expandor could be inserted as shown in Fig. 3, so as to modify the analog signal before quantizing and after re-conversion to analog. There is the possibility that this compensation, if properly designed, could smooth out the steps.

Whatever the channel is like between the scanner and the display, its input-output characteristic can be examined in terms of a probability distribution p(y I x) where x is the input and y is the output of the channel. Pictures were taken of this transfer characteristic for the channel processes programmed, plotting probability as intensity on the x-y plane. These plots are shown along with the gray scale they produce on the pages with pictures and are labeled "two-bit gray scale." In the bottom right quarter of these pictures is the p(y I x) distribution where the input, x, increases upward and the output, y, increases to the right. These probability plots include any compression used, and the plot in the lower left quarter of the gray scale pictures shows this input compression, with the input increasing upward and the compressed input increasing to the right. For straight PCM the probability distribution is a uniform staircase. This appears in Fig. 2 at the lower right corner.



Six-Bit Original

Four Bit

Three Bit

Two Bit

Two-Bit Gray Scale


From "Playboy:" Copyright © 1960 by HMH Publishing Co., Inc.
Fig. 2 - Straight PCM pictures without compensation.




Fig. 3 - Block diagram of a digital-picture channel.


C. Power Law Companding

Since the human eye is more sensitive to variations to the input as possible. Thus, the mean square-error in dark areas than it is to variations in bright areas, the can be defined as errors in a uniform channel are not properly balanced. A channel should concentrate most of the errors at high intensities and produce smaller errors in the black regions. Due to the Difficulty of changing the channel process, the easiest way to compensate for the eye is to transform the signal before and- after the channel in such a way as to make a uniform channel optimum.

The eye's ability to discriminate small changes in intensity can be estimated from Steven's power law.10   For a point source this law says that the eye perceives brightness as the square root of intensity. Therefore, if we wish a small absolute error to be seen just as distinctly at any intensity level, the signal should be compressed before the addition of noise and expanded afterward. This process is called companding. If we designate the actual input as x, the input to the channel as x', the output of the channel as y', and the final output as y, then the "second-order compensation" used was



In normal pictures the improvement produced by companding is worth about one-bit per sample since it approximately halves the number of levels necessary for adequate reproduction. In an analog system, a simple nonlinear amplifier could accomplish this compensation. During the following development, compensation before and after the channel will be assumed and included in the pictures shown.

II. ERROR ANALYSIS

In order to evaluate the relative merits of various channels, it is helpful to develop a numerical basis of comparison. The mutual information between the input and output is a measure of how efficiently we use the channel, but it does not indicate very well how the picture is affected subjectively. A measure like mean-square-error indicates more clearly how the picture differs from what we want it to look like. It has been shown that the mean- square-error for a digital memoryless channel has a mini- mum value depending on the channel capacity and that many methods of coding are capable of achieving this minimum, some resulting in better pictures than others. For this reason, the mean-square-error will be divided into two components which are suitable for separating channel processes and effectively predict the quality of the resultant pictures.

A. Mean-Square Error

Since correction for nonlinearity is introduced outside of the channel, the channel should have a linear transfer characteristic which would make the output as similar to the input as possible. Thus, the mean square-error can be defined as



Assuming a flat distribution for the input, so that p(x)constant, allows us to write



where A is a normalization constant,



defined so as to make the minimum mean square error equal to one :


B. Variance

One of the important measures of picture quality is the amount of apparent noise. This can be measured by the variance in intensity in a portion of the picture which was of constant intensity at the input. The variance should be measured from the mean value of the output rather than from the input intensity. Thus, a noise measure V is defined as the variance of the output averaged over all inputs.


The normalizer Afor the mean square error, is used here also to maintain the same units. The mean value of the output is defined as


C. Deviation

The second measure of picture quality is a measure of the deviation of the mean output yx from the input. This quality is orthogonal in form to the variance V and measures the tonal quality of the picture. Call the deviation D and define it so that


In terms of the input and output, the deviation of the mean has the form


For a straight PCM channel all the error is caused by D since there is no noise. This is the only case where the minimum error, E = 1, is strictly achieved.

Since we cannot escape from some minimum total error E, the main difference between channels is in the relative amounts V and D. As will be demonstrated, the human observer is much more annoyed by tonal errors than bynoise because of the eye's ability to average out noise. Thus, the best pictures result when D is reduced and V increased, without increasing E too much.

III. CHANNEL PROCESSES

In discussing channel processes, a probability graph will be shown for the binary channel. These graphs show p(y I x) in the vertical dimension against the input x and the output y. A shaded area represents a constant probability over the area and a wall indicates that all or most of the probability is concentrated at a particular output. The process of coding and decoding, indicated by en- closing the signal to be quantized in brackets, is assumed to split the range between Zero and One into 2n equal sections, assign a code to each section, transmit and receive the code, and then convert it to the average value of the section originating it. Any signal over One receives the code for One and any negative signal receives the code for Zero. Thus the signal receives standard PCM transmission over a n-bit channel. The probability is shown in Fig. 4 (next page).

A. Straight PCM

Process: y = {x}.

Deviation: D = 1.

Variance: V = 0.

M. S. Error: E = 1.

B. Transmitter Noise

The following processes create improved pictures by trading noise for tonal scale, or, in terms of the error functions, reducing D while increasing V. As explained previously, noise tends to be more acceptable than quantization steps.

If we produce a flat distribution of random noise with amplitude of 2-n or one level, and add this to the input before it is coded, a particular intensity can result in different outputs at different times. In Fig. 5 the wedges pictured show the probability of one output, not a spread of outputs. Averaging in the y direction, the transfer curve becomes a diagonal except at the edges. For example, an input of 1/2 would result in an output of 5/8 half of the time and 3/8 the other half of the time with a two-bit channel. Thus, the average intensity of an area in a picture would be reproduced correctly, but with more noise. Also, since no averaging has been done, the definition is not reduced.

y{x + r},      -2-n-1 r < 2 -n-1

D = 2-n

V = 2(1 - 2-n)

E = 1 + (1 - 2-n)

For channel capacities n above three bits the average output intensity becomes equal everywhere to the input, thus reducing D to zero. At this point the noise factor V is equal to two, and the mean-square-error is double that of straight PCM. However, since the smooth areas of pictures processed with this channel have the correct average intensity and are void of steps, the pictures represent an improvement in spite of the noise. Examples of pictures made with one level of transmitter noise appear in Fig. 6 and should be compared with those without noise in Fig. 2. As can be seen from the gray scale in Fig. 6, quantization in the output picture is apparent in the form of quantized noise rather than contours. The pin cushion effect produced tends to be annoying at low bit rates.

C. Pseudo-Random Noise

If, before quantizing, we add to our signal a continuum of noise with an amplitude of one level, we are able to reduce the tonal error D to zero, but at the cost of in- creasing the total mean-square-error to twice its minimum value. To achieve minimum total error, it is necessary to produce an output equal to the mean of the input set causing the code word, at every time interval. When adding noise at the transmitter, the input set is not known precisely from the code sent, unless the noise is also known. By using pseudo-random noise, the receiver can generate the same "noise" used for coding and thus accurately predict the input set. The picture need not suffer from the lack of a perfectly random noise source if the source used does not repeat within several frames and generates noise which appears random. It takes practically no information to keep two pseudo-random number generators in synchronization, and they need generate only one number per sample.

If we add "noise" to the input signal before coding and subtract the same "noise" from the decoded signal, we have an output which is exactly the mean value of the inputs which would have caused the code word. The situation is similar to jiggling a grating in front of your eyes as opposed to holding it still. By moving it you can see everything but not clearly.

Adding noise to a signal, quantizing, and subtracting the same noise from the quantized signal has the same effect as clipping the input signal one-half level at the top and bottom and adding a level of noise. The clipping becomes unimportant as the amplitude of a level becomes small and the main effect is that of adding noise to the signal. The amplitude of the resultant noise is one level. It is not the same "noise" which was added to the signal at the transmitter but it has the same distribution. Thus, the effects of the quantizing have been completely trans- formed into noise error V and, except for the clipping, the picture appears as if it had been sent over an analog channel with one level of additive noise. The effect of the clipping has been investigated and appears to affect picture quality very little.1

Fig.4 - Conditional probability of output y given input x for linear PCM.

Fig. 5 - Conditional probability of output y given input x for linear PCM with one level of noise added to input signal.

Four Bit

Three Bit

Two Bit

Two-Bit Gray Scale


From " Playboy: " Copyright © 1960 by HMH Publishing Co., Inc.
Fig. 6 - Transmitter noise pictures.


The pseudo-random channel has the following properties :

y = {x + r} -r -2-n-1 r < 2-n-1
D = 2-n
V = 1
E =1 + 2-n.

As indicated in Fig. 7, an input level of, say, 1/2 will produce all outputs between 3/8 and 5/8 with equal probability over this two-bit channel. By this method a smooth gray scale is produced over a digital channel since the eye tends to average out the noise. This effect of reduced brightness discrimination for small areas is dis- cussed in many references11 and is easily seen by comparing the pictures and gray scale in Fig. 8 with the preceding pictures. More pictures processed with the pseudo-random noise process are presented in Figs. 9 and 10 (pp. 152-153).

Fig. 7 - Conditional probability of output
y given input x for linear PCM with one level of noise
added to input and identical noise subtracted from output.


Four Bit

Three Bit

Two Bit

Two-Bit Gray Scale
From "Playboy." Copyright © 1960 by HMH Publishing Co., Inc.
Fig. 8 - Pseudo-random noise pictures.



Six-Bit Original

Psudo-Random

Straight PCM
Three Bits

Psudo-Random

Straight PCM
Two Bits
From "Playboy." Copyright © 1960 by HMH Publishing Co., Inc.
Fig. 9 - Pseudo-random and straight PCM pictures with compensation.

D. Pseudo-Random System

A television system using pseudo-random noise is not difficult to instrument. The quantizer required for transmitting good pictures is a three-bit, or eight level, device instead of the six-bit device needed for straight PCM. This change represents a considerable saving. One problem with the pseudo-random channel is the random number generator. Simple generators, however, can be realized with a shift register and some elementary logic circuitry .The output of such a circuit can be made effectively random for present purposes. Two generators, one at the transmitter the other at the receiver can be synchronized by anyone of a number of methods.

There is some question if the pseudo-random pattern should be synchronized with the frame rate or not. It is my feeling that a random pattern would tend to average out the noise in time as well as in space if it were non- synchronous to the frame rate. However, in an experiment carried out at Bell Telephone Laboratories by James and Mounts12 it was found that it was better to synchronize the noise to the frame rate. Otherwise, the ~oise tended to "migrate." This experiment used a 135-line television system with a four-bit PCM channel and successfully demonstrated the advantage of adding and subtracting noise.

If we assume that a 525-line system will behave the same as the 135-line system, we can restart the random number generators each full raster and save sending extra sync pulses. As shown in Fig. 11, the rest of the system is the same as a standard PCM system but with only eight levels. Four bits of the number generator can be decoded to create an analog voltage with a range of one quantizer level. Second order compensation is included in the system flow diagram and should also compensate for any other nonlinearities in the system so as to maintain maximum efficiency. The expandor can be part of a contrast control circuit since the operation is similar.


Six-Bit Original

Three-Bit Pseudo-Random

Two-Bit
From "Playboy." Copyright © 1960 by HMH Publishing Co., Inc.
Fig. 10 - Pseudo-random pictures with second-order compensation.

E. Psychological Effects

By taking advantage of subjective aspects of vision, it is possible to improve the appearance of digitally- transmitted pictures without a corresponding increase in data rate.


Fig. 11 - Block diagram of a TV transmission system using pseudorandom coding.

In the system investigated here, two such avenues were tapped. First, the intensity scale was compressed so that most of the error was introduced in bright areas rather than dark areas. An improvement results because the eye responds more nearly to percentage error rather than to absolute error. Thus, the magnitude of noise introduced was made roughly proportional to the amplitude of the signal by nonlinear amplification in the channel.

Second, the type of error introduced was changed from quantization steps to additive noise. The eye can detect very small changes in intensity if there are large areas to compare. Such is often the case in quantized pictures. A large area of slowly varying intensity is fairly common in pictures and may happen to be quantized into two levels. A person will easily detect and be annoyed by the contour produced. However, if an error of the same magnitude is broken up and distributed as noise throughout the area, a person will not notice it, since he now has an area of only one or two dots to compare with the average intensity.

IV. Conclusion

Previous experiments with bandwidth reduction on digital television signals have been shown reductions in the source rate from six or seven bits per sample for straight PCM, to values between one arid three bits. However, except for differential PCM,5 the equipment needed for these reductions is complex and costly, since a high-speed memory is required and the source rate fluctuates in time. The process described here requires no memory, operates at a constant source rate, and can be encoded and decoded with a minimum of equipment. In fact, since the analog-to-digital conversion need be accomplished only with three-bit accuracy instead of six, the total equipment may well be less complex than that required for a straight PCM channel.

The use of pseudo-random noise which is synchronized at the transmitter and receiver provides an efficient method of breaking up the objectionable "staircase effect" typical of PCM. In so doing, noise very similar to that found in analog channels is introduced. Compared to quantizing contours, such noise is easily tolerated by the eye. The fact that the eye tends to average out noise in local areas is used to advantage, since the average of an area is the precise intensity wanted. Thus without considering more than a single point at a time, the redundancy of nearby picture elements is utilized. However, as can be seen from the fairly complicated picture in Fig. 10, the noise does not blur detail greatly. Thus the source rate can remain constant and still reproduce all pictures with the same quality.

From the pictures produced with this pseudo-random process, it seems that three bits per sample would be sufficient for most television requirements, whereas four bits could be used for more demanding applications. The improvement effected with this system is easily come by and can halve the bandwidth or power needed for PCM transmission as compared to linear PCM.

The improvement obtained with this pseudo-random process is purely subjective since the information content of the transmitted pictures is identical with that of equivalent bit rate, standard PCM pictures. Several pictures have been processed with a computer to obtain samples for comparison. These pictures demonstrate that "distributed" quantizing noise is considerably more pleasing to the eye than quantizing contours.

ACKNOWLEDGMENT

The author is indebted to Prof. P. Elias for his valuable suggestions and criticisms in his capacity of thesis super- visor, to J. Cunningham for his assistance in constructing the facsimile scanner, and to W. A. Clark and the TX-2 staff for their cooperation in the use of the computer.

yellow rule

* Received by the PGIT, July 28,1961. This work is based on an S.M. thesis to the Dept. of Elec. Engrg., Mass. Inst. Tech., Cam- bridge, February, 1961) and was performed in part at Lincoln Lab., Mass. Inst. Tech., a center for research operated by M.I.T. with the joint support of the U. S. Army, Navy, and Air Force, and in part at Research Lab. of Electronics, which is supported in part by the U. S. Army Signal Corps, the AF Office of Scientific Research, and the Office of Naval Research.

** Research Lab. of Electronics and Lincoln Lab., Mass. Inst. Tech., Cambridge, Mass.

  1. L. G. Roberts, "PGM Television Bandwidth Reduction Using Pseudo-Random Noise," S.M. thesis, Mass. Inst. Tech., Cambridge; February, 1961.
  2. W. F. Schreiber, "The measurement of third-order probability distributions of television signals," IRE TRANS. ON INFORMATION THEORY, vol. IT-2, pp. 94-105; September, 1956.
  3. E. R. Kretzmer, "Statistics of television signals," Bell Sys. Tech. J., vol. 31, pp. 751-763; July, 1952.
  4. E. R. Kretzmer, "Reduced alphabet representation of tele- vision signals," 1956 IRE NATIONAL CONVENTION RECORD, pt. 4, pp.140-147.
  5. R. E. Graham, "Communication theory applied to television coding," Acta Electronics, vol. 2, pp. 333-343; 1957-1958.
  6. W. A. Young blood, "Estimation of the Channel Capacity Re- quired for Picture Transmission," Sc.D. thesis, Mass. Inst. Tech., Cambridge; 1958.
  7. J. E. Cunningham, "A Study of Some Methods of Picture Cod- ing," M.S. thesis, Mass. Inst. Tech., Cambridge; 1959.
  8. C. W. Harrison, "Experiments with Linear Prediction in Television," Bell Sys. Tech,. J., vol. 31, pp. 764-783; July, 1952.
  9. J. M. Frankovich and H. P. Peterson, "A functional description of the I,incoln TX-2 computer," Proc. Western Joint Computer Conf., vol. x, pp. 146-155; February, 1957.
  10. S.S. Stevens, "The psychophysology of vision," in "Sensory Communication," W. Rosenblith, Ed., M.I.T. Press, Cambridge, and John Wiley and Sons, New York, N.Y., p. 13; 1961.
  11. II S. H. Bartley, "The psychophysics of sensory function," in "Handbook of Experimental Psychology," S. S. Stevens, Ed., John Wiley and Sons, New York, N. Y., pp. 952-960; 1951.
  12. 12 D. B. James and F. W. Mounts, "Elimination of Quantizating Contours by Noise Addition and Subtraction," Bell Labs., private communication; April, 1961.


yellow rule

Home || Contact Dr. Roberts

Copyright 2001 Dr. Lawrence G. Roberts

Contact webmaster