Method for generating representations of polylines using piecewise fitted geometric primitives
View Patent ↗A method for generating a representation of a polyline formed by a sequence of points determines an overcomplete set of geometric primitives that redundantly fit overlapping sections of the polyline. The overcomplete fitting is performed such that the set includes one or more types of geometric primitives, each fitted to a section of the polyline formed by a subset of the sequence of points. The method determines a local cost of each geometric primitive based on a combination of a fitting error and an encoding cost of the geometric primitive, and determines a join cost of each successive pair of adjacent primitives. Next, the method determines a combination of the geometric primitives forming a connected path along a length of the polyline such that a sum of the local costs of the geometric primitives and the join costs of adjacent primitives in the combination is optimized.
1. A method for generating a representation of a polyline formed by a sequence of points, comprising:
determining, using a processor in communication with a non-volatile computer-readable memory, an overcomplete set of geometric primitives that redundantly fit overlapping sections of the polyline, such that the overcomplete set of geometric primitives includes multiple types of geometric primitives, and geometric primitives of the multiple types are fitted to at least one section of the polyline formed by a subset of the sequence of points;
determining, using the processor, a local cost of each geometric primitive in the overcomplete set of geometric primitives based on a combination of a fitting error between the geometric primitive and the section of the polyline and an encoding cost of the geometric primitive, wherein the encoding cost of the geometric primitive is a function of a number of bits required to store the geometric primitive in the non-volatile computer-readable memory, wherein at least one geometric primitive has an encoding cost that is different from an encoding cost of another geometric primitive in the overcomplete set of geometric primitives;
determining, using the processor, join costs of pairs of adjacent geometric primitives in the overcomplete set of geometric primitives based on a geometric quality of a join between a pair of adjacent geometric primitives and an encoding cost of a location of the join;
determining, using the processor, a combination of the geometric primitives forming a connected path along a length of the polyline such that a sum of the local costs of the geometric primitives and the join costs of the pairs of adjacent geometric primitives in the combination is optimized; and
storing, using the processor, the optimized combination of the geometric primitives into the non-volatile computer-readable memory, wherein the method results in an efficiency of memory utilization of the non-volatile computer-readable memory.
2. The method of claim 1 , wherein the points represent geographical coordinates.
3. The method of claim 1 , wherein the types of geometric primitives in the overcomplete set of geometric primitives include a line segment, a circular arc, and a clothoid.
4. The method of claim 3 , further comprising:
determining the local cost of the circular arc of a radius r and a center at a point c according to
Σ
i
λ
(
x
i
-
c
2
-
r
)
2
︸
distortion
+
(
1
-
λ
)
(
2
k
+
L
s
(
r
)
)
︸
rate
+
j
,
where 1>λ>0, x i is an ith polyline point fitted by the circular arc, k is a number of bits required for quantizing a coordinate, L s (r) is a number of bits required for quantizing the radius, and j is the join cost of the join to a next geometric primitive, wherein a notation ∥x i −c∥ 2 represents a Euclidean norm of a difference x i −c.
5. The method of claim 3 , further comprising:
determining the local cost of a path formed by a combination of line segments and circular arcs according to
λ
err
∑
i
[
d
(
x
i
)
]
2
︸
distortion
+
λ
line
n
lines
+
λ
arc
n
arcs
+
∑
k
j
k
,
where x i is the ith point on the polyline, d(x i ) is a distance between the point x i and the path, n lines is a number of line segments in the path, n arcs is a number of circular arcs in the path, parameters λ arc >0 and λ line >0 represent the relative encoding costs of a circular arc and a line segment, respectively, a parameter λ err >0 represents a trade-off between the fitting error and the encoding cost, and j k is a join cost of the join between the kth pair of adjacent geometric primitives in the path.
6. The method of claim 1 , further comprising:
determining a sum of the local costs and the join costs for each combination using dynamic programming (DP).
7. The method of claim 6 , further comprising:
constructing a discrete graph in which each join is represented by a weighted edge and each geometric primitive is represented by a weighted node;
adding to the graph a starting node connected to nodes that represent geometric primitives that have an endpoint neighboring the beginning of the polyline;
adding to the graph a final node connected to nodes that represent geometric primitives that have an endpoint neighboring the ending of the polyline; and
determining a minimal cost path from the starting node to the final node to produce the optimized combination of the geometric primitives.
8. The method of claim 1 , further comprising:
using the optimized combination of the geometric primitives, and
refitting the optimized combination of the geometric primitives to the polyline.
9. The method of claim 8 , wherein the refitting provides for one of maintaining true intersections of the polyline, preventing false intersections in the optimized combination of the geometric primitives, or both.
10. The method of claim 1 , wherein at least one geometric primitive has at least one endpoint not on the polyline.
11. The method of claim 1 , wherein at least one endpoint of at least one geometric primitive does not coincide with the points in the sequence of points.
12. The method of claim 1 , further comprising:
generating a representation of a set of polylines, wherein an optimized combination of geometric primitives is determined for each polyline in the set.
13. The method of claim 1 , further comprising:
acquiring a set of polylines,
generating a representation of the acquired set of polylines, wherein the generating includes:
preprocessing the acquired set of polylines by chaining together polylines that meet at their endpoints into longer polylines, to obtain a set of polyline chains, each consisting of one or more polylines from the acquired set of polylines, and
generating a representation of each polyline chain in the set of polyline chains using the steps of the method of claim 1 .
14. The method of claim 1 , further comprising:
acquiring a set of polylines that includes multiple polylines of a single geographical feature,
preprocessing the multiple polylines of the single geographical feature by linking them together into a polyline chain, and
generating a representation of the polyline chain using the steps of the method of claim 1 .
15. The method of claim 12 , wherein two or more polylines from the set of polylines intersect in an intersection point, wherein an optimized combination of geometric primitives is determined for each polyline, and using the optimized combinations of the geometric primitives, and
modifying at least one of the optimized combinations of geometric primitives, such that the connected paths representing the two or more polylines intersect at a single point.
16. The method of claim 1 , further comprising:
using the optimized combination of the geometric primitives, and
sampling the optimized combination of the geometric primitives to produce a new polyline that approximates the polyline.
17. The method of claim 1 , further comprising:
superimposing a discrete grid on a space; and
generating only geometric primitives that have endpoints or control points on the discrete grid to limit a number of encoding bits.
18. A system for generating a representation of a polyline formed by a sequence of points, comprising:
a non-volatile computer-readable memory for storing geometric primitives;
a processor, coupled to the non-volatile computer-readable memory, that is configured to:
determine, using the processor, an overcomplete set of geometric primitives that redundantly fit overlapping sections of the polyline, such that the overcomplete set of geometric primitives includes multiple types of geometric primitives, and geometric primitives of the multiple types are fitted to at least one section of the polyline formed by a subset of the sequence of points;
determine, using the processor, a local cost of each geometric primitive based on a combination of a fitting error between a geometric primitive and a section of the polyline and an encoding cost of the geometric primitive, wherein the encoding cost of the geometric primitive is a function of a number of bits required to store the geometric primitive in the non-volatile computer-readable memory, wherein at least one geometric primitive has an encoding cost that is different from an encoding cost of another geometric primitive in the overcomplete set of geometric primitives;
determine, using the processor, a join cost of each successive pair of adjacent geometric primitives;
determine, using the processor, a combination of the geometric primitives forming a connected path along a length of the polyline such that a sum of the local costs and the join costs of the geometric primitives in the combination is optimized; and
store, using the processor, the optimized combination of the geometric primitives into the non-volatile computer-readable memory, wherein the method results in an efficiency of memory utilization of the non-volatile computer-readable memory.
19. A non-transitory computer-readable storage medium embodied thereon a program executable by a processor for performing a method, the method includes generating a representation of a polyline formed by a sequence of points, the method comprising:
determining, using the processor in communication with the non-transitory computer-readable storage medium, an overcomplete set of geometric primitives that redundantly fit overlapping sections of the polyline, such that the overcomplete set of geometric primitives includes multiple types of geometric primitives, and geometric primitives of the multiple types are fitted to at least one section of the polyline formed by a subset of the sequence of points;
determining, using the processor, a local cost of each geometric primitive in the overcomplete set of geometric primitives based on a combination of a fitting error between the geometric primitive and the section of the polyline and an encoding cost of the geometric primitive, wherein the encoding cost of the geometric primitive is a function of a number of bits required to store the geometric primitive in the non-transitory computer-readable storage medium, wherein at least one geometric primitive has an encoding cost that is different from an encoding cost of another geometric primitive in the overcomplete set of geometric primitives, and wherein the fitting error is determined as a sum of squared distances between points of the polyline and the geometric primitive;
determining, using the processor, join costs of pairs of adjacent geometric primitives in the overcomplete set of geometric primitives based on a geometric quality of a join between a pair of adjacent geometric primitives and an encoding cost of a location of the join;
determining, using the processor, a combination of the geometric primitives forming a connected path along a length of the polyline such that a sum of the local costs of the geometric primitives and the join costs of the pairs of adjacent geometric primitives in the combination is optimized;
using the optimized combination of the geometric primitives, and refitting the optimized combination of the geometric primitives to the polyline; and
storing, using the processor, the optimized combination of the geometric primitives into the non-transitory computer-readable storage medium, wherein the system results in an efficiency of utilization of the non-transitory computer-readable storage medium.