Outline of overall GPS algorithm
--------------------------------

Input: Set S = {s1..sn} of 2D polylines

S represents a set of GPS tracks that covers all pathways (roads,
trails) within an aerial image.  Any given point in any polyline in S
may contain GPS errors.  

Output: Set Q = {q1..qm} of polylines (m<=n) and graph G.

Q represents the complete, corrected network of pathways with
duplicates and GPS anomalies eliminated.  Each line segment of any
member of Q does not intersect any line segment of any other member of
Q.

G represents the network of polylines where each edge is in one to
one correspondece with a polyline of Q.

Algorithm:

1 - Compute intersection points

U = union of all line segments in S

I = resulting points from line intersection algorithm run on L 
      |U| = u, |I| = i, running time = O(u log u + i log u) using
      O(u) space.  Due to Bentley & Ottmann [1979]. 

2 - Identify "relevant" intersection points in I

Relevant vertices are those that actually represent pathway junctions.

The key problem here is that any path that is a duplicate of other
paths (traces the same pathway) will be likely to intersect with the
other path(s) in places that are meaningless.

The question: when is a segment a unique trail and when is it a duplicate?

First idea to determine relevant intersection points:

What we really are trying to do is detect (and throw out) correlated
intersection points.  The idea is similar to the Correlated Reference
Period in the LRU-k algorithm.  Thus, we define a CRP, but in terms of
points, or Euclidean distance.  So, any intersection point that occurs
within the CRP distance of any other intersection point is considered
irrelevant (except for the first and last points in a series of
correlated points).  

The CRP, actually it should be Correlated Reference Distance, could be
a certain number of points, or a threshold distance, or (best) a
combination of the two.

Another problem - intersection point may be far from actual pathway
intersection.

3 - Eliminate "stand still" GPS anomalies

Look for small incidence angles among a series of points that have a
certain number of irrelevant intersection points among them.  Delete
all points between first and last relevant intersection point.  Could
also add caveat that all such points should lie within a certain area
(have a maximum size for bounding box of all points).

Problem - standstills will likely be at pathway junctions and
therefore intersect with both useful and useless segments.

180 degree problem... when stand stills are at viewpoints (out and
back tracks).

Duplicate points -- eliminate them clearly, but they might be useful
in identifying standstill areas.

Only detect standstill intersections within each si -- no need to use
entire union of all members of S.  (standstill intersections cannot be
with other tracks).

Replace all points deleted in a standstill by the geometric average
(the center) of them.  This is undoubtedly the actual point where the
gps unit was "standing."  

--Add this 'center' point to the list of relevent intersections since
  most likely the gps stopped at a point of interest (ie a real
  intersection, or a turn around point).


4 - Classify S into a graph, G

In graph G:

Edges are polylines where each polyline is a portion of a member of S,
  or an entire member of S.

Vertices are:

    * all relevant intersection points in I
    * all starting and ending points to any polyline in set S

5 - Eliminate edges in graph that are duplicates

Examine each pair of vertices for which there exists two or more edges
between them.  Compute shape similarity distance (Frechet, Hausdorff,
etc) between the polylines of each edge in the pair.  If any are
similar, mark them as a "kill" set of edges which should be reduced to
a single edge.

Also make a kill set any edges whose polylines intersect (perhaps a
few times, maybe just once?)

6 - Correct all edges using Snakes Algorithm

Run first pass snakes correcting algorithm

While there are segments to split (by some criteria) do
   Split any necessary segments
   Run snakes correcting algorithm on those segments
   
7 - Reduce kill sets

For each kill set we must choose one edge whose correction or
representation of the trail is "best."  Must develop a metric to
determine this.

First round ideas: 
* average image intensity value of corrected points
* average image intensity along entire segment
* average distance moved (corrected) per point

All measures must be averages per point since number of points in each
segment could vary.

Delete all edges but one in every kill set, adjust graph and then
output.

Done.


------------------------------------

Possible changes to Snakes Algorithm

different energy minimization algorithm
any new energy terms?
new metric for internal energy
"give up" factor with back-tracking to handle non-existing image features
---- perhaps based on frechet (or whatever) distance between the last
10 points you've corrected and the original 10 points