Patent ID: 8369606

Claim:
A system for aligning maps using polyline matching, comprising: a processor to execute the following modules, comprising: a representation module representing a global map and a local map as polyline maps comprising a plurality of line segments; an approximation module identifying one or more approximate matches between the polyline maps; a refinement module determining one or more refined matches from the approximate matches, comprising: an algorithm module applying a greedy algorithm comprising two choices to the approximate matches; and a cost module determining a cost function associated with each of the two choices and choosing the choice with the lowest cost function, wherein the cost function is determined according to the equation: ε=∥ƒ( d 1 , . . . , d k )− g ( d 1 +Δd 1 , . . . , d k +Δd k )∥ 2 +α∥Δd 1 , . . . Δd k ∥ 2 where {d 1 , . . . , d k } represents length of each segment in polylines f(•) is a polyline map M 1 sub , g(•) is polyline map M 2 , ∥ƒ−g∥ 2 is match accuracy, or deviation, between M 2 and M 1 sub , and α∥Δd 1 , . . . Δd k ∥ 2 is overall length perturbation, where α is a regularization parameter controlling tradeoff between match accuracy and length modification Δd i ; and an alignment module aligning the global map and the local map at the one or more refined matches.