The team investigates a plane crash and the shooting of the forest ranger who discovered the crash. Charlie uses a deconvolution algorithm to identify a smudged fingerprint, allowing them to identify the technician who tampered with the plane's software.
A convolution is means of creating a new function h from two other functions f and g. For discrete functions we write h(n)=(f *g)(n)=&Sigmaif(i)g(i-n). Usually convolutions involve functions that take on non-zero values a finite number of times, since the sum would often be undefined otherwise. For such functions the the convolution evaluated at n tells us how much f overlaps with the translation of g by n. Convolutions can also be done with continuous functions, where we trade the sum for an integral. In this case h(x)=(f *g)(x)=&int-&infin&infin f(t)g(t-x) dt.
The exercise hints at two basic properties of convolutions: they are commutative and associative with scalar multiplication. Convolutions are also associative, and the addition of functions distributes over convolutions.
Convolutions are frequently used in image processing. This is done by letting f represent the image data and letting g take on non-zero values only in a square centered at the origin. A square matrix is then used to represent g. For instance, the image below is shown before and after convolution with the matrix given below.
-1 | -1 | -1 |
-1 | 8 | -1 |
-1 | -1 | -1 |
0 | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 0 |
Deconvolution involves finding f when we know g and h. This is a frequent problem in signal processing where h is the information we recieve from a device(like the Hubble telescope alluded to in the episode) and g is a distortion introduced to the original signal f. Often the exact form of gis unknown, but we know what kind of distortion it is. For example, if you look at a blurry picture you can often tell that the camera was moved while the picture was being taken, but you might not be able to tell exactly how much it was moved or in what direction. Finding the original signal is very difficult, and is usually done using one of several varieties of computer algorithms.