Romeil Sandhu dot com

Distance is one of those ideas that we or (at least I) have taken for granted. This basic question arises in many fields like that of image processing and has become a major part of my PhD research. In particular, we have introduce a new distrubtion metric that arises from prediction theory. But before going into this, I’ve written a short introduction to those that are not familar to how one really defines a “distance” between two points.

I’ve found one of the more tangible examples is path planning by GPS. Of course, you may all know how many miles it roughly takes you to go from your home to your favourite restaurant. The more interesting question is how exactly does GPS compute the mileage?  The obvious answer here is the miles that it takes you while traveling on a road or other legal pathways (e.g., not through the local shopping mall).  It takes me 7.6 miles to go from Georgia Tech to my temporary favorite, Panera Bread.  For fun, here’s a quick view of the path.

View Larger Map

Ok so with that trivial example, the next question that begs to ask is well what if it isn’t distance between two points in a city, but between two cities in different continents? Better yet, what if you decided to fly a plane rather than drive — then you can fly right over that shopping mall!  However, if you have ever flown in an airplane and have seen a flight of path that is being displayed, you realize that the path is not a straight line, but rather it resembles an arc (even assuming times where turbulence is being avoided).  Realizing that airlines what to be the most efficient, it would seem that a straight line would be better?? The short answer is no. In fact, the arc pathway that is taken is the shortest distance possible between the two cities. Below is flight path (in red) from Atlanta Hartsfield Airport to this year’s Computer Vision and Pattern Regconition Conference (CVPR) sight in San Francisco.  Note, the black line is a straight line for reference.

The question is why? Well, it has to do with the surface that we live — the earth or better yet, a sphere! Tthe shortest distance between any two points that live on a sphere can be characterized by great circles or arcs.  In differential geometry, this shortest distance is known as a geodesic.  The first inclination is then why do our GPS compute distance via miles traveled on roads, doesn’t it make more sense to compute the arc between your home and that favorite restaurant of yours?  First lets assume that the resturant is in San Franciso and you are in Atlanta.  Then the answer is yes and no.   If you had a plane, and were flying by plane, then yes.  This is because you can assume that the surface that you travel on has no restrictions except that it is a sphere.  Now if you are traveling by road, then you can think of your surface as not really being a sphere.  The buildings and restricted legal pathways make the surface on which you compute distance an entirely different one!  Thus, the GPS computes this distance, in which is interestingly referred to as the “taxicab distance” or “taxicab geometry.” The arguement of “shortest path” for path planning by GPS is beyond our present discussion. If you are interested though, the area has been studied in many control problems. Here’s a link to the webpage of Evdokia Nikolova, who gave an excellent seminar here at Georgia Tech.

Now lets take what we have learned a step further.  Say that I have a set of data points that characterize  specific object p and another set of points that characterize object q, what is the distance between these p and q?  The first question that you may ask is what surface do these points lie on.  If they live in the Euclidean world, then the answer is simple.  Its the distance that we have learned since we were little, and one that Shaq has once used to describe his skills as an athlete:

Shaq:  I’m like the pythagorean theorem. Not too many people know the answer to my game.

Unfortunately, to the shagrin of Shaq, this distance,which is also known as the Euclidean distance, only answer’s the problem for linearly related points or those points that live on a Euclidean surface.  If these points were derived from a probability space (e.g., p and q now represent probability density functions) the answer is not so simple.  In fact, this now leads us to a new class of distance metrics that try to measure the similarity between two probability density functions.

In computer vision and segmentation, being able to characterize an image through statistical measures has recently grabbed many people’s attention.  Segmentation, which is a low level vision task, is the idea of being able partition a certain object from that background.  You can imagine now that in the above examples, p now represents an object we would like to grab in an image while q is the background.  Interestingly, the ability to quanitify the distance between the two probability measures plays a major role on how effective one’s segmentation algorithm is.  This has become a major research of mine, where it has been my joy to work with Tryphon Georgiou to introduce a new way of characterizing distance in the area of imaging and perhaps, even in your everday life! Please check out my project’s page for more details.