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

NYTimes article on gPhone

Yesterday (Oct, 8, 07) NYTimes Business Section had an interesting but relatively negative article about the rumored GPhone project at Google (see "For Google Advertising and Phones Go Together" http://www.nytimes.com/2007/10/08/business/media/08googlephone.html ). It is a bit strange that it is taking Google 2 years to develop a Linux based OS and programs for cells. Apple does not have Google's resources and iPhone has been doing relatively well; also setting the bar pretty high up there :-)

But one should not under estimate G either. As more computing and entertainment is moved to the third screen (i.e. mobile devices), ubiquitous computing is becoming more and more a reality -- and Google does/should understand that space.

Second, it is not exactly true that G doesn't make hardware. They do, but not for the consumer market. They do not have to either! if Apple can make a phone so can Dell, and HP does have a smart phone already. A carefully crafted strategic alliance -- the type that Yahoo! is famous for -- is a viable option. Incidentally, Y's Internet apps are supposed to be very well done.

Moreover, the article only mentions mobile Ads. That may not be the only reason. Pushing other applications like, Google apps and streaming video from G's YouTube, plus long range plays such as peer to peer networking communication or creating an ultra-mobile computing device (one that can hook up to power, a keyboard and a large display) can also be in the long term cards.

Lets not be naive though. As a stand alone device, power and a small display will still be issues for a while.

From a competitive stand point, I have never owned a Windows mobile device. But if their OS is anything like Vista, a "well done" Linux based cell will be a welcome entry. Not sure where that will leave Symbian, Palm OS and other players in that space.

Coincidentally, today Google bought a finish mobile social network http://www.techcrunch.com/2007/10/09/google-buys-social-mobile-startup-jaiku/ :-) If I was Yahoo! I would approach Twitter…

Peace, E

--
Esfandiar Bandari, PhD, MBA
http://www.linkedin.com/in/ebandari