1770: Empirical

|< < Prev Comic #1770 (March 24, 2014)

Empirical

Made by: Alien@System

Explanation

Readers expecting this comic to be xkcd: Empirical's dialogue in Liz and Jon's word balloons may be disappointed (or pleasantly surprised), but the base strip is actually the one in which a flag-bearing mouse declares the house to be the property of mice, much more famous for the meme in which the flag is changed and the mouse is part of some other group.

And so it is with this comic. Forum user x-viila (author name, anyone?) used filtered back projection to produce an image showing us the flag -- and the mouse carrying it, and Jon -- but the thought bubble was completely gone, so if you don't recognize the symbol, you're still in the dark.

The author's notes go a bit into tomography. You may find it an interesting read.

This explanation is incomplete. Specifically, what the symbol on the flag is. If you can edit this page to complete the explanation, please do!

The author writes:

After my previous submissions, I thought I'd try my hands on a meme. Of course, I had to give it a little twist. Hem.

Computer tomography is one of the most powerful diagnosis tools available to modern medicine, as it allows you to create a cross-section of the human body without having to cut it open, which most patients do prefer. Of course, for most doctors, and especially the patients a tomography is, like every advanced piece of technology, basically a magic box: You put the human in and get the cross-section out. What happens 'under the hood', so to speak, is a piece of quite ingenious mathematics.

Looking through the human body has been possible since Röntgen and his discovery of the invisble radiation which anglophone countries choose to call X-rays despite that fact that we know them so well nowadays that the X is hardly appropriate[1]. The problem is that we can get only integrated information when we shoot a single X-ray image - the rays travel through the body, being absorbed with different strength from different materials and the resulting brightness depends on the overall absorbtion along the path. That is useful when we have single solids surrounded by weakly absorbing materials, since in that case a silhouette is usually enough to make out the important details, like a bone fracture.

But what if we want to look at, say, the nasal cavity? It is surrounded by bone, so a single image doesn't tell us much. Mathematics comes to the rescue. Instead of one photograph, we need a lot, from different angles. In fact, it is best if we rotate the whole X-ray source and camera around the body once and get the absorption image for every angle. The result looks pretty much like what we see above, just monochrome. It displays the amount of leftover radiation dependent on the rotation angle and tangential distance to the centre. It doesn't look very useful, but all the information we need is in there.

To get a handle on the maths, we make some assumptions that we usually make anyway. The first is the pixellation, that we can describe our cross-section as a lattice of small squares that have a constant absorption each. That might not be very accurate, but if we choose our resolution fine enough, we get a usable result. The second is the exponential decay, which linearises our problem. We assume that the outgoing intensity of a ray passing through a voxel is the incoming intensity, multiplied by e to the power of minus the absorption strength times the length of the path through the material. If we do that for the whole image, we arrive at the simple conclusion that the negative logarithm of the ratio of incoming to outgoing radiation is equal to the sum of all absorption that happened inside.

And that, in a purely mathematical sense, solves our problem: Every pixel in our output image describes one linear equation, with the absorption constants of the voxels being the variables for which we have to solve, and the lengths of the paths through the voxels being the parameters, which we can calculate beforehand, since they're only dependent on the input and output geometry, not the actual contents. There is just a tiny problem remaining: If we have an output image with M×N pixels and want a cross-section with n×m pixels, we have nm independent variables and have to invert a nm×NM-dimensional matrix. And that might not actually have a solution, since our pixellation assumption could not be good enough.

It is somewhat easier to find a solution, or at least something close to a solution using an iterative process. We guess an image that might be the solution, put it through our tomography, look at the result and how it differs from our actual output, and adjust our guess accordingly. Mathematically formulated, for every point in our n×m target space, we define a scalar χ2 (chi square) as the squared length of the difference vector between the output vector and the result of the transformation from target to output space with the nm×NM transformation matrix. By deriving χ2 with respect to every independent variable for our current point in target space, we find the gradient, the direction we have to move along to change χ2 fastest. By calling the distance we move along our gradient l, we can break the dependency of χ2 on nm variables down to a dependency on only a single variable l. The result will be a polynomial of second degree with rather large coefficients, but the important thing is that we can find the minimum of that polynomial exactly, which can be translated back to a point in the target space which has a lower χ2 than the point we started from.

The advantage of that algorithm is that we can feed it to a computer, which can handle the multitude of multiplications for us. As a starting point, we choose a uniformly grey picture and then let our algorithm run over it. With every iteration, we get closer to the solution, and the contours of the image become less and less blurry, until we can finally find out which faction I made Mouse a fervent believer of.

Original strip: 2011-11-19.

[1] There are other ways to use tomography than Röntgen imaging, but the process remains mostly the same. The most prominent alternative is PET, Positron Emission Tomography, which allows us to take images of a body's activity.

Transcript

{A pattern of coloured sine waves on a green diamond background}