Detecting Landmines
One of the nastiest aspects of the modern world is the existence of anti-personnel landmines. When detonated, these unpleasant devices jump up into the air and kill anyone close by. They are typically triggered by trip-wires attached to the detonators. If someone catches their foot on a trip-wire, the mine is detonated and the person dies. To make things even worse, landmines are typically hidden in dense foliage and thin nylon fishing line is used to make the trip-wires almost invisible. One way to detect landmines is to look for the trip-wires themselves. However, foliage usually hides the trip-wires well and leaf stems can even resemble a trip-wire. Any detection algorithm must work quickly, detect trip-wires when they exist and not get confused by leaves. An example of the problem that such an algorithm has to face is given in the figure below in which some trip-wires are hidden in an artificial jungle.
Three trip-wires are hidden in this image.
Can you find them?
In order to detect the trip-wires, we must find a quick way of finding partly obscured straight lines in an image. Fortunately, just such a method exists; it is the Radon Transform. For the problem of finding the trip-wires we don’t need to find the inverse, instead we can apply the Radon Transform directly to the image. As we saw when we looked at the Radon Transform of the square, the Radon Transform is good at finding straight lines. This is just what we need to detect the trip-wires. Of course life isn’t quite as simple as this for real images of trip-wires, and some extra work has to be done to detect them. In order to apply the Radon Transform the image must first be pre-processed to enhance any edges. Following the application of the transform to the enhanced image, a threshold must then be applied to the resulting values to distinguish between true straight lines caused by trip-wires (corresponding to large values of R) and false lines caused by short leaf stems (for which R is not quite as large). Following a sequence of calibration calculations and analytical estimates with a number of different images, it is possible to derive a fast algorithm which detects the trip-wires by first filtering the image, applying the Radon Transform, applying a threshold, and then applying the inverse Radon Transform. The result of applying this method to the previous image is given below in which the three detected trip-wires are highlighted.
Note how the method has not only detected the trip-wires, but, from the width of the lines, an indication is given of the reliability of the calculation.
Truly, as advertised earlier, by finding the landmines, math saves lives!
