» About     » Archive     » Submit     » Authors     » Search     » Random     » Specials     » Statistics     » Forum     » Facebook     » RSS Feed     Updates Daily

No. 1770: Empirical

First | Previous | 2014-03-24 | Next | Latest


First | Previous | 2014-03-24 | Next | Latest

Strip by: Alien@System

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

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.