Finding Steve Fossett -- a simple approach through elimination !!! :-)

As many people know, the adventurer Steve Fossett, "63, disappeared Sept. 3 after he took off from a western Nevada ranch in a single-engine plane". http://www.washingtonpost.com/wp-dyn/content/article/2007/10/15/AR2007101500361.html?nav=hcmodule.

This post about is an algorithm to reduce the search area on the satellite imagery to consider only those that can be the landing or crash site. Feel free to jump to the Algorithm section - i.e., the punch line!

Ebay and Google Earth's approach: Ebay and Google Earth asked the general public to look over Terrabytes of satellite desert data to locate where Fossett's plane might have landed and crashed. Even a scaled satellite image of Fossett's one-engine plane was provided for people participating in the search.

What was right about this approach was the realization that the plane probably had not landed intact. Consequently, human recognition would be needed to accurately locate the potential plane or even the intact plane. The problem, besides the not-so-easy use of Ebay computers and Google earth data, is that terra bytes of data takes a long time and very many people to search.

Here is an approach I would take, and it is one that Google scientists could implement easily, and still use the public or individuals to look for Fosset's plane.

First it is based on one premise: We have to limit the data size being search!!! And we can limit the search space by using the invariance and distinguishing features of the plane (vs the desert). Moreover, while the plane might have crashed, we can use geometric and photo-metric features to localize the crash site. We can use these constraints either individually or in parallel, and that we can reduce our search space by relaxing some of these photometric and geometric constraints.

Using Photometric Constraints: We know the color of the plane, and for the most part it is quite different from the color of the background desert and its vegetation. Not always but very often. On the other hand, because of the BRDF and the different viewing angles of the satellite and the sun direction, color constancy becomes a major issue. Nonetheless, we can eliminate a large portion of the data using:
a color cube -- not necessarily an RGB color cube, but a YRW(?) or whatever -- and
a semi-normalized intensity model ( this would be like using a spectral angle, but not initially including the data whose total intensity is below a certain threshold).
The important thing to remember here is that by varying the separation thresholds between what the plane might look like after landing (after all it may be completely burned out) and the varying desert, we can include more or less data to be passed to the geometric filter for analysis. See the discussion in the algorithm below to use an ever expanding cone to do so.
Should we get lucky, the very bright white color of the plane will stand out strongly against the dark vegetation or the yellow / brown color of the sand. A color cube and color based segmentation can go a long way to reduce the amount of data.
Using the Geometric Constraints: Not to be surprised, geometric constraints are more stable than the color constraints. Here the constraints to be used are that straight lines stay straights, and parallel lines -- i.e., the wings and parts of the fuselage -- stay parallel regardless of the viewing angle. Moreover, even a broken plane wing will have 3 straight edges with two of them being parallel.

In combination, our geometric and photometric constraints give us the required algorithm to drastically reduce the images used in visual search.

Algorithm: Create an appropriate color cube -- in fact, I would create multiple color cubes, RGB, CHV, JND and others. In one or more of these the color of the plane and parts of the background desert will separate nicely. We can then use a cone with its central axis pointing to the expected color of the plane (normally white). The diameter of the cone can then be varied to increase or decrease the number of pixels that we include in our visual search space, or the area that we pass to the more expensive geometric constraint filter (NB for all we know the plane may have been burned in a fiery crash. That's why we need to take a hierarchical approach in using photometric constraint). Increasing the diameter of the cone, includes more pixel in search.

Using morphology we can quickly look for scattered by adjacent colored area resembling the plane, against the areas that we eliminated earlier. Also we have to morphology to collect small segments closely located to one another. We also need morphology to create a margin around the areas we doing a geometric search in.

Once we have limited the area searched using... well color segmentation... now we process the larger segments using the more expensive geometric constraint. We can use simple edge detector like the Soble operator to search for straight line segments. Eliminate the super short and very long straight line segments (unless they border bright white areas). Then look for parallel lines close to one another -- this is set by the the width of the wing or the fuselage. Look through these areas according to those with higher density (proximity and number) of these segments found close to one another first. Increase or reduce the length of the segments considered; this reduces or increases the amount of data being visually searched respectively.

If you ask me the parallel line invariance is perhaps the most important constraint. The Important thing here is that all the processing is simple and computationally inexpensive.

If processing power allows (specially using parallelism and Ebay's and Google's processing power) we can use subpixel edge detection (and perhaps more refined Hough transform) to find objects with parallel lines. Roads are easily eliminated etc. etc. Even with these luxuries the computational expense is small and the implementation time trivial.


-- Esfandiar Bandari, PhD, MBA
e.bandari@cantab.net, e.bandari@gmail.com
http://www.linkedin.com/in/ebandari