Reconstruction of a sampled "signal"

In a number of recent discussions pertaining to aliasing in digital camera systems, I have paraphrased the Shannon-Nyquist sampling theorem thus (I will cast the paraphrase in terms of working with an electrical waveform):


When we first hear this it may be hard to swallow. For example, how can the "reconstructing organ", even in theory, precisely determine what the voltage is at all the (infinite number of) points of the waveform between the sample points? Then, if we accept that this is theoretically possible, how can the "reconstructing organ" actually do that?

We will find that this story plays out well in the situation of a "signal" such as an electrical waveform (and audio waveform for example).

In a digital camera, we are also interested in completely describing a continuous "variable" through a finite number of samples. Here, the "variable" is the color of an image, which of course varies two-dimensionally across the image. The finite number of samples that we "deliver" are the colors of the pixels of the delivers digital image.

When we now look to find, in our overall digital chain, the equivalent of a certain critical feature of the reconstructing organ that we learned to appreciate in our work with an electrical waveform, we are unable to locate it. In fact, there is a a pivotal difference between the waveform and image cases (in actual practice) that influences how a digital system must be designed and how it will behave.

In this series of notes, I will take you through this story.

Reconstruction of a waveform from samples - a human simulation

I like to explain how reconstruction of a waveform can work through an exercise in which we simulate the workings of a sampled system using human actors.

The system being simulated seeks to transport electrical waveforms containing components at frequencies no higher than 3800 Hz. Aware of the "rules" of Messrs. Shannon and Nyquist, we will sample the waveform at a rate of 8000 samples per second (8000 Hz). That is, a sample will be taken every 125 us.

Adam will play the role of the "sending" (or perhaps "recording") end of the system. I give him the waveform to be processed as a curve drawn on graph paper. The horizontal axis represents time and the vertical axis voltage. I take care that this waveform would only contain frequency components below 4000 Hz, the Nyquist frequency" for our sampling rate of 8000 Hz. That is, if we were to analyze the waveform by Fourier analysis, we would find in it only components whose frequency was less than 4000 Hz.

Adam begins his work by drawing vertical lines on the graph paper at intervals of (according to the time scale) 125 us. These lines represent the sampling instants.

Adam then notes the points at which the waveform intersects these lines and records on his log sheet the voltages at each of those intersections. These are of course the sample values (which are in terms of voltage).

Hen writes then in regular decimal form to some degree of precision. Note now that this system had now become digital. (Sampling by itself does not make the representation digital; it only makes it discrete. If we left the samples just as voltages on some bus, the system would not be digital.) As a result, we have introduced an imperfection into our execution of the process, the fact that the numbers Adam writes do not precisely correspond to the voltage of the waveform at the sample instant. For example if he writes for one sample "0.986 (V)", the actual voltage of the waveform at that instant might be:

0.98587321641079226 . . . V.

Although this situation (the matter of "quantizing error") is of great concern in the design and performance of any digital system, it is not related to the actual topic of this note, so I will mostly ignore it from here on.

After Adam has done this for the span of "time" represented by the entire sheet of graph paper I gave him, he passes his log sheet to Becky, who will play the role of the "receiving" (or "playback") end of the system. It will be her task to (hopefully) reconstruct the entire original waveform from only the list of sample values on the log sheet.

Note that Becky knows the sample rate that was used at Adam's end.

She works on a sheet of graph paper such as we had at Adam's end. She draws vertical lines at intervals of 125 us. At each line, she placed a point whose height corresponds to the value on the log sheet of the sample at that instant.

To finish her work, Becky must now "draw a smooth curve" through these points. We would hope that this would be a duplicate of the original waveform (except for the small discrepancies caused by quantization).

But Becky could draw any number of "smooth" curves through that set of points. Which one should she draw?

Well, I instruct her to draw any curve she likes but that it must be one that contains (if we were to analyze it by Fourier analysis) only frequencies below 4000 Hz. That is because we know that indeed the original waveform (whose twin we seek to make her) did not contain any frequencies below 4000 Hz.

Now how could Becky actually follow this restriction? Well, this is just a story, so we will presume she somehow could. (Perhaps she is Cherokee, and her grandmother, of the fictional Fourier clan, taught her to do it.)

Well, it turns out that there is only one curve that passes through that set of points and contains only frequencies below 4000 Hz. And that is a precise and complete duplicate of the original waveform.

Wow!

In part 2 of this series, we will see how Becky's supernatural ability is actually performed in an electrical system. You will be astounded by how simple it is!

[to be continued]

Hi Doug,

Doug Kerr said:

....In part 2 of this series, we will see how Becky's supernatural ability is actually performed in an electrical system. You will be astounded by how simple it is!

[to be continued]

Click to expand...

So the plot thickens then, eh? I can't wait for the part 2. Thanks for making this info more accessible to all.

I had hoped to have Part 2 of this series ready by now, but I have decided to take a slightly different (and hopefully better) approach, which requires me to develop some illustrations (a slightly tedious process). And of course, there are some other events on the day's agenda. So I ask the readers' patience.

Best regards,

Doug

Part 2

"Machine reconstruction"

In part 1 of this series, I illustrated the conceptual premise of reconstructing a "waveform" from a set of samples, using human actors (one of whom, needed to have some supernatural abilities). Now we will move top a more "mechanical" outlook, not requiring anything supernatural.

We will follow the action on this figure:



Again, our premise will be a system with a sampling rate of 8000 Hz. We will work with a test signal (seen in line a) that is a sine wave (single frequency waveform) with a frequency of 3600 Hz. Note that this is safely below the Nyquist frequency for our sampling rate, 4000 Hz, so we should not expect to have any aliasing.

On line b we see the samples taken of this waveform. Do not think of them as being represented by numbers; just think of them as electrical pulses (which in fact they are as they are taken).

If we step back and look at this series of pulses, it would seem as if they portray a waveform such as we see in magenta on line c. And in fact they do.

This waveform is a 4000 Hz sine wave whose amplitude varies at a rate of 400 complete cycles of variation per second, the "envelope" also being sinusoidal in shape.. That is, it is a 4000 Hz sine wave amplitude modulated by a 400 Hz sine wave.

If we analyze this waveform through Fourier analysis, we find that it comprises two different components, one with a frequency of 3600 Hz and one with a frequency of 4400 Hz. We could in effect "decompose" the waveform we drew on line c into those two separate waveforms (as we see on line d and e).

Note that this smells a lot like aliasing. But we know there is no aliasing of the form we have so far been thinking of, since the input waveform here is all below the Nyquist frequency.

But it is a type of aliasing, "working in the other direction". It has a special name in one case where we will be specially concerned with it, but I will disclose that later. Just as in a radio system where certain notions apply both to the transmitting and receiving antennas, here the concept of aliasing can really visit us at both the "sending" and "receiving" ends.

Now we know that the waveform we seek (a duplicate of the original one on line a) will not have any components in it above the Nyquist frequency (400Hz) - we were obligated to assure that. So we slip into the chain a low pass filter that cuts off at the Nyquist frequency (4000 Hz). Poof! The component seen on line e is gone, leaving only the one on line d. We regard it with self-satisfaction on line f - it is our delivered, reconstructed waveform, identical to the original waveform on line a.

So now we can imagine that an actual "electrical' reconstruction organ will end up with a low pass filter with cutoff at the Nyquist frequency.

But how in fact do we get from line b to line c - to get the magenta waveform we will feed into the filter?

In fact, the waveform seen on line c never really happens - it is just our interpretation of the series of samples on line b.

If we in fact just feed that series of samples (remember, they are electrical pulses) into the low-pass filter, the waveform on line f will come out! (There is a lovely proof of that, but it is a bit to complicated for me to burden either of us with just now.)

So the low-pass filter is the reconstruction organ (and is in fact called the reconstruction filter).

Make it more concrete, please

We can see the overall situation in a more concrete form in this figure, which gives the block diagram of an electrical, but totally useless, system (just suitable for the "lecture room table").



We see the samples being taken by a little sampling gate- a switch that closes briefly at the sampling rate (under control of the sampling clock). The samples are a train of electrical pulses, the voltage of each being the sample value.

As I discussed just above, we feed them into our reconstruction filter. And Voilà! What comes out is a copy of the original waveform.

Except for one thing - its amplitude is greatly less. Why? Well, the sampling pulses are very narrow in time. Thus they each contain a very small amount of energy; on an ongoing bases, they collectively contain, collectively, only a small fraction of the power in the original waveform And a low-amplitude waveform is all that amount of power can make.

In fact, in one sense, it would be ideal if the sampling pulses had zero time width. But of course then they wouldn't each contain any energy at all - they wouldn't exist. So we don't dare think of exactly that!

In any case, we handily rescale the waveform to its proper amplitude with an amplifier.

Now, make it digital

This demonstration system is in no way digital. it is discrete (the information is conveyed by a finite number of samples at regular intervals), but it is not digital. The voltages of the samples are not passed on in digital form - not as decimal numbers, or binary numbers). They are just voltage, and each one can have any value we can imagine (over some range). They are an analog representation of discrete data.

But of course in real life we almost always use sampling as the "outer" layer of a digital system. We get a little insight in that in this figure:



Here, we start by sampling the waveform as before. Now, though, we present each sample to a digital-to-analog converter, which develops a digital (presumably binary) representation of the voltage.

Those binary words are transmitted in some appropriate format to the "receiving end". There a digital-to-analog converter creates a voltage pulse from each words, its voltage being as described by the binary number.

The train of these pulses is a proxy for the original train of sample pulses. We feed them into the reconstruction filter, with the same result as before.

Now, because of quantizing error, the reconstructed pulses are not identical in voltage to the original pulses. Thus the reconstructed waveform will not be identical to the original waveform. But this is no deficiency in the concept of sampling and reconstruction.

After all, the Shannon-Nyquist theorem does not imply that, from the set of sample values, made inaccurate by quantization error, we can completely and perfectly reconstruct the original waveform. Garbage in, garbage out.

A caution

Please do not try and relate this view of reconstruction to the case we are really interested in: the sampling of an image in a digital camera. It doesn't actually apply. We'll see why in part 3.

[to be continued]

Part 3

In digital photography

How that we have learned about the reconstruction of a "signal" from samples in the context of a digital audio system, we move to our real interest: digital photography.

We will assume a monochrome camera, both to avert the need to deal with the special complications of a CFA system, and to make our variable "one dimensional" (in the mathematical sense); that is, at each point its value is just illuminance (rather than three color coordinate values).

But we will also assume only a "one dimensional" variation (in the geometric sense) - we will think only in terms of an illuminance variation along a horizontal track.

We will also consider the situation in which the digital image is presented on a display pixel-for-pixel - each pixel of the image is mapped onto a pixel of the display.

We can follow the action on this figure.



We assume that the sensel pitch (in either horizontal or vertical direction) is 10 um. Thus the sampling rate along a vertical or horizontal track is 100 cy/mm, and the Nyquist frequency is 50 cy/mm.

We assume a test illuminance profile along a horizontal track that is sinusoidal with a spatial frequency of 45 cy/mm (well below the Nyquist frequency). Such a simple sinusoidal profile might come, for example, from a test chart of the sinusoidal type (as is used in MTF measurement). We see that profile in line a. Note that, unlike our illustrative electrical waveform, this has only positive values (there being no such thing as a negative illuminance value) - its is what a mathematician would call a "raised cosine" function.

In line b we have taken samples of the illuminance profile from the photodetectors along the track of interest. Here, we can imagine that these are actually handled as digital values (developed by an analog-to-digital converter).

We assume that there is no tonal mapping or the like, and so the sample values become (with proper attention to scaling) the values of the pixels along the track in the delivered image. We show that in line c just to be clear about it.

We now (on line d) jump to the display. Here the scale is of course larger - we assume that the pixel pitch of the display is 0.2 mm (5 px/mm).

We assume here that the display has "sharp-edged" pixels - that is, what lights up are little squares, with uniform luminance across any given one.

Then, what we see on line d is the profile of screen luminance along the track of interest.

On line e, I just repeat the original image illuminance profile for comparison; we might hope that what appears on the screen will be just like that.

But clearly it isn't. Assuming that every horizontal track of our "test pattern" is the same, essentially what we see on the screen is a pattern of very fine light and dark stripes, somewhat emulating the pattern of the test pattern, except that their frequency is 50 cy/mm (in terms of the scale at the sensor), not 45 cy/mm, and the amplitude of the modulation (the "contrast ratio") varies substantially as we go along the track (in a pattern that will repeat). Essentially, we will have a moiré pattern in the visible image.

What has happened here? We were careful to have the only component of the original illuminance profile below the Nyquist limit.

Well let's do a system bed check. Where is the reconstruction filter in this model?

Well, there isn't one. And we can see from the figure in part 2 what that means. In terms of that figure, here we get to see the purple "waveform" rather than the blue one.

If there were a reconstruction filter here, what would it be like? Well, for one thing, in the cleanest model, the face of the display would not light up little squares, but rather little points. Then, in front of it would be an optical low pass filter whose cutoff frequency would be the Nyquist frequency (which, considering the scaling at the display, would be 2.5 cy/mm).

But we've already heard in another article that making an optical filter with a reasonable low pass response is very difficult. So we don't do it.

But couldn't we do something in the display driver or something? No. The input to the display is discrete, so all it can do is make points of light (which are like the reconstructed sample pulses in the electrical case). The reconstruction filter has to be after that (in front of the display face).

So we just have an incomplete implementation. And the artifacts that it delivers are described as display aliasing ("the disease that is never spoken of").

What does that mean in practice? Well, it means that although with a sampling rate at the sensor of 100 cy/mm, we should be able to without difficulty capture by samples and reconstruct an illuminance pattern with a frequency (at the sensor), of 45 cy/mm, when we try to look at it on our display, we will have a moiré pattern.

Now, as we drop the frequency of the pattern, we find that the magnitude of the phenomenon diminishes fairly rapidly. We might find that at a luminance profile frequency of about 33 cy/mm (on the sensor), the phenomenon has diminished so it isn't troublesome.

Said another way, if the camera was actually able to deliver a resolution of 45 cy/mm, we still couldn't take advantage of that, because of display aliasing. The highest useful resolution might be 33 cy/mm.

This phenomenon was first studied by RCA engineer Raymond D. Kell during early work on television in 1934. It might seem that in (analog) television, there is no sampling involved. But there is in the vertical track direction, since of course the scanning of the image is done with discrete (almost) horizontal lines - it is discrete (sampled)by the scan line structure in the vertical direction.

The ratio of the practically usable resolution (in the face of display aliasing) to the Nyquist frequency of the system is called the Kell factor. For my example above, the Kell factor would be 0.66 (30/50), about the typical value found by Kell in the systems he studied. Today, for various reasons, a higher Kell factor (often about 0.75) is attained.

Of course, when the image is not displayed "pixel-for-pixel" (with up- or down-sampling involved before we get to the display proper), the matter becomes more complex.

*******

Well, that perhaps rather shocking denouement brings to a close this particular series. I hope you have found it interesting.

Best regards,

Doug

Doug Kerr said:

Well, that perhaps rather shocking denouement brings to a close this particular series. I hope you have found it interesting.

Click to expand...

Certainly. Thank you.

Jerome Marot said:

Certainly. Thank you.

Click to expand...

+1. Thanks Doug.

Cem, Jerome,

Thanks.

Best regards,

Doug