Introduction to digital signal processing with Prof. Bruckheimer

June 4th, 2004  |  Tags:  |  3 Comments

A common cliché of procedural crime dramas and spy movies involves recovering precise visual information (e.g. a license plate number) from a blurry photograph or videotape. Usually this technique is introduced by having a hard-boiled detective asking the bespectacled computer operator to “enhance that.” Invariably the computer speedily obliges after some typing and clicking. Who knew it was that easy to violate the Nyquist theorem?

note to Nyquist-savvy readers: Ordinarily, I put explanations that I assume some people won’t need in notes like this; the typographical conceit is designed to prevent these explanations from intruding on the main text. In this case, though, the “explanation” is on the meta-level — the rest of this post is an explanation of the Nyquist theorem. If you’re familiar with the Nyquist theorem, chuckle at the previous paragraph and skip the rest of this entry. The continual presence of this “feature” in television (most recently, last night, in some show Andrea and I were watching) irritates me so much that it has inspired me to write this up; mea culpa if it’s patently obvious even to folks who don’t know the Nyquist theorem.

Unfortunately, it’s not easy to have an “enhance” feature. In fact, it’s impossible. Not “impossible,” as in “‘impossible’ until the next release of Microsoft Windows descends from the sky to the platform in front of the golden calf, enabling all good things.” Not “impossible” as in “intractable, but computable if you had the age of the universe to wait for a result.” Rather, it’s “impossible” as in impossible.

The Nyquist theorem has to do with sampling analog signals into the digital domain. Basically, it states that, to reproduce a signal with a maximum frequency n, you’ll need at least 2n samples per second. A corollary to this is that, if you sample at rate 2n, you will not be able to recover anything that is more detailed than a sine wave with a frequency of n.

The above figure shows two sine waves. The red wave has a frequency of three times that of the green wave; it is also out of phase with regard to the green wave. This may not look much like a blurry traffic camera photo, but it’s the same principle — the Nyquist theorem applies whenever we sample discrete values (like a computer image or an audio file) from an analog data source (like light or sound waves) or continuous function (like the sine wave).

Let’s say that the green wave corresponds to the blurry photo and the red wave corresponds to the actual scene (presumably including the license number). Say also that we’ve taken five samples (corresponding to the tic marks on the x-axis). Notice that, at these points, the two waves have the same values. That means that, as far as our discrete representation knows, the scene could correspond to either the green wave or the red wave. By sampling, we’ve created an approximation of the initial source. In the case of digital music, like CDs, this works because the sampling is high-resolution enough to reproduce all of the frequencies that a good microphone can capture. In the case of the blurry traffic photo, on the other hand, this doesn’t work — there are infinitely many “precise images” that correspond to any one blurry approximation!

Therefore, if the “CSI” gang manages to get an indictment based on an “enhanced” license plate image, someone on the “Law & Order” side will likely manage to create reasonable doubt — since, for all we know, that blurry image corresponded to someone else’s plate.

I’m currently listening to Signore! Cos E Quel Stuppore? – Susanna, Conte, Contessa, Figaro from the album “Mozart: Le Nozze Di Figaro – Karajan” by Wolfgang Amadeus Mozart (1756-1791)