Navigation system with map matching mechanism and method of operation thereof

Patent metadata

Field	Value
Publication number	US-9595209-B2
Application number	US-201113324533-A
Country	US
Kind code	B2
Filing date	Dec 13, 2011
Priority date	Dec 13, 2011
Publication date	Mar 14, 2017
Grant date	Mar 14, 2017

Abstract

A method of operation of a navigation system includes: receiving a current position for locating a device; adding a new edge from a road topology map to a topological tree based on the current position; removing an old edge from the topological tree based on the current position; determining a matched edge of the topological tree based on the current position and the topological tree; and calculating an adjusted location based on the matched edge for displaying on the device.

First claim

What is claimed is:

1. A method of operation of a navigation system comprising:
receiving a current position for locating a device;
adding a new edge from a road topology map to a topological tree based on an edge of the road topology map corresponding to the current position, wherein:
the road topology map is for representing segments of real-world vehicle pathways,
the topological tree is for dynamically representing a set of edges in the road topology map corresponding to the current position;

removing an old edge outside of a termination condition with no descendant edges within the termination condition from the topological tree based on the current position;
determining a matched edge of the topological tree based on the current position and the topological tree; and
calculating with a control unit an adjusted location based on the matched edge for mapping the current position to the adjusted location on the matched edge.

2. The method as claimed in claim 1 wherein removing the old edge includes removing the old edge when the old edge is outside of a locator error range.

3. The method as claimed in claim 1 wherein adding the new edge includes adding the new edge based on a density of edges in the road topology map near the current position.

4. The method as claimed in claim 1 further comprising:
determining a device speed at the current position; and

wherein:
adding the new edge includes adding the new edge more frequently when the device speed changes compared to when the device speed has not changed.

5. The method as claimed in claim 1 further comprising:
generating a travel route based on the adjusted location when a locator signal strength is low; and

wherein:
displaying the adjusted location includes displaying the travel route on the first device.

6. A method of operation of a navigation system comprising:
receiving a current position for locating a device;
adding a new edge having shape points from a road topology map to a topological tree based on an edge of the road topology map corresponding to the current position, wherein:
the road topology map is for representing segments of real-world vehicle pathways,
the topological tree is for dynamically representing a set of edges in the road topology map corresponding to the current position;

removing an old edge outside of a termination condition with no descendant edges within the termination condition from the topological tree based on the current position;
determining a matched edge of the topological tree based on the current position and the topological tree; and
calculating with a control unit an adjusted location based on the matched edge for mapping the current position to the adjusted location on the matched edge.

7. The method as claimed in claim 6 further comprising:
determining a device speed at the current position; and

wherein:
determining the matched edge includes determining whether the matched edge is reachable within a time difference from a last matched edge given a device speed.

8. The method as claimed in claim 6 wherein determining the matched edge includes determining whether the matched edge is a child edge, a sibling edge, or a grandchild edge of the last matched edge.

9. The method as claimed in claim 6 wherein determining the matched edge includes calculating an edge score for the matched edge based on the distance between the current position and the matched edge.

10. The method as claimed in claim 6 further comprising:
determining a device heading corresponding to the current position; and

wherein:
determining the matched edge includes calculating the edge score based on a difference of an edge heading of the matched edge and the device heading.

11. A navigation system comprising:
a storage unit including memory and configured to provide access to software;
a control unit including at least one processor, coupled to the storage unit, configured to execute the software to:
receive a current position for locating a device;
add a new edge from a road topology map to a topological tree based on an edge of the road topology map corresponding to the current position, wherein:
the road topology map is for representing segments of real-world vehicle pathways,
the topological tree is for dynamically representing a set of edges in the road topology map corresponding to the current position;

remove an old edge outside of a termination condition with no descendant edges within the termination condition from the topological tree based on the current position;
determine a matched edge of the topological tree based on the current position and the topological tree; and
calculate an adjusted location based on the matched edge for mapping the current position to the adjusted location on the matched edge.

12. The system as claimed in claim 11 wherein the control unit is configured to further execute the software to remove the old edge based on a locator error range.

13. The system as claimed in claim 11 wherein the control unit is configured to further execute the software to add the new edge based on a density of edges in the road topology map near the current position.

14. The system as claimed in claim 11 wherein the control unit is configured to further execute the software to:
determine a device speed at the current position; and
add the new edge more frequently when the device speed changes compared to when the device speed has not changed.

15. The system as claimed in claim 11 wherein the control unit is configured to further execute the software to:
generate a travel route based on the adjusted location when a locator signal strength is low; and
display the travel route on the first device.

16. The system as claimed in claim 11 wherein the control unit is configured to further execute the software to add the new edge having shape points.

17. The system as claimed in claim 16 wherein the control unit is configured to further execute the software to:
determine a device speed at the current position; and
determine whether the matched edge is reachable within a time difference from a last matched edge given the device speed.

18. The system as claimed in claim 16 wherein the control unit is configured to further execute the software to determine whether the matched edge is a child edge, a sibling edge, or a grandchild edge of the last matched edge.

19. The system as claimed in claim 16 wherein the control unit is configured to further execute the software to calculate an edge score for the matched edge based on the distance between the current position and the matched edge.

20. The system as claimed in claim 16 wherein the control unit is configured to further execute the software to:
determine a device heading corresponding to the current position; and
calculate the edge score based on a difference of an edge heading of the matched edge and the device heading.

Assignees

• Lu Chunhua
• Telenav Inc

Inventors

• Lu Chunhua

Classifications

• G01C21/30

  Map- or contour-matching · CPC title

• G09B29/106 Primary

  using electronic means · CPC title