Application of the hough transform to modeling the horizontal component of road geometry and computing heading and curvature

• US 6,732,046 B1
• Filed: 10/03/2001
• Issued: 05/04/2004
• Est. Priority Date: 10/03/2001
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Joshi, Rajashri
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Donnelly, Arthur D.
• Application Number:
  US09/970,265
• Time in Patent Office: 944 Days
• Field of Search: 701/208, 701/200, 701/201, 701/203, 701/206, 707/102, 707/103, 707/104, 340/988, 340/990, 345/442, 345/443
• US Class Current: 701/208
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 20/56 exterior to a vehicle by using sensors mounted on the vehicle
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The Hough Transform is used to identify the circular arcs and straight line segments that coincide with the horizontal curves of roads. The Hough Transform uses data indicating positions along the roads as an input in order to identify the circular arcs and straight line segments that coincide with the roads. Data indicating the circular arcs and straight line segments are stored in a geographic database and are used to represent the roads. Radius of curvature of the road is obtained as a by product of this representation. Because the Hough Transform yields a closed form representation of road segments, the heading at any point along a road can be computed by computing the tangent to the closed form representation. Thus, heading can be accurately obtained at any point along a road.

Claims

1. A method of representing the horizontal component of roads in a geographic database comprising:

providing data indicating a plurality of locations along a road;

using the data as an input to a Hough Transform to determine circular arcs and straight line segments that coincide with the road; and

storing data that define said arcs and line segments to represent the horizontal component of the road in the geographic database.

2. The method of claim 1 wherein said data indicating a plurality of locations along a road are obtained using a positioning system located in a vehicle that travels along the road.

3. The method of claim 2 wherein said vehicle is a probe vehicle.

4. The method of claim 2 wherein said vehicle is operated by a geographic database developer.

5. The method of claim 1 wherein the data that define said circular arcs comprise center points and radii.

6. The method of claim 1 wherein the data that define said line segments comprise slope and intercept.

7. The method of claim 1 wherein the data that define said circular arcs further comprise data that indicate end points of the arcs.

8. The method of claim 1 wherein the data that define said line segments further comprise data that indicates the end points of the segments.

9. The method of claim 1 wherein said data indicating a plurality of locations along a road are obtained by digitizing photographs or maps.

10. The method of claim 1 wherein the geographic database is used by an adaptive cruise control system in an automobile.

11. The method of claim 1 wherein the geographic database is used by an adaptive lighting control system in an automobile.

12. The method of claim 1 further comprising:

determining a value of the curvature at locations along the road using the data that define said circular arcs and straight line segments.

13. The method of claim 1 further comprising:

determining a value of the heading at locations along the road using the data that define said circular arcs and straight line segments.

14. A geographic database formed according to the process of claim 1.