Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-10-03
2004-05-04
Black, Thomas G. (Department: 3663)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S206000, C707S793000, C707S793000, C345S442000
Reexamination Certificate
active
06732046
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to geographic databases and, more particularly, the present invention relates to a new way to represent roads in geographic databases and methods for forming such representations.
Geographic databases have many uses. Geographic databases are used in navigation systems to display maps and provide route calculation and guidance. Geographic databases are also used by Internet sites to provide navigation-related features and services.
In many conventional geographic databases, a linearly extending geographic feature, such as a road, a river, or a state or municipal boundary, is represented using a series of discrete points. For example, in the case of roads, each road segment is represented by two nodes that represent the end points of the road segment, and optionally by one or more shape points that represent points along the road segment between the two nodes. Data that define each of these points (e.g., latitude, longitude, and optionally altitude) are stored in the geographic database to represent the road segment.
Although this way of representing roads and other linearly extending geographic features works well for many applications, there is room for improvement. One area in which there exists a need for improvement relates to the amount of data needed to accurately represent a road. If a road is curved, a large number of shape points may be needed to accurately represent the actual shape of the road. Storing large numbers of shape points increases the overall size of the geographic database thereby increasing the cost of the data storage medium. Increasing the overall size of the geographic database may also require that systems that use the geographic database have faster and more powerful processors or more memory.
Accordingly, there is a need for a space efficient model for representing and storing the geometry of linearly extending geographic features, in particular roads.
SUMMARY OF THE INVENTION
To address these and other objectives, the present invention provides a use of the Hough Transform to identify the circular arcs and straight line segments that coincide with the horizontal component of roads. The Hough Transform uses data indicating positions along the roads as an input in order to identify the circular arcs and line segments that coincide with the roads. Data describing the circular arcs and line segments are stored in a geographic database and are used to represent the roads.
The data, indicating the horizontal component of positions along roads, which are provided as an input to the Hough Transform, may be obtained from a positioning system located in a vehicle that is driven along roads, or alternatively, the data may be obtained from other sources such as by digitizing paper maps or imagery.
The use of circular arcs and line segments to represent the horizontal component of roads may be advantageous for certain applications that require an accurate representation of road geometry. Such a representation may be a space efficient way to represent roads with a high level of accuracy, because the representation directly exploits the circular arc spline design of roads.
REFERENCES:
patent: 3069654 (1962-12-01), Hough
patent: 5172317 (1992-12-01), Asanuma et al.
patent: 5233527 (1993-08-01), Shinnosuke
patent: 5243524 (1993-09-01), Ishida et al.
patent: 6029173 (2000-02-01), Meek et al.
patent: 6265991 (2001-07-01), Nishiwaki et al.
patent: 6266442 (2001-07-01), Laumeyer et al.
Innes, J.D., The Engineering or Roads (4 pages) (2001), http://www.unb.ca/web/transpo/mynet/mtu74.htm.
Air Force Joint Pamphlet, Planning and Design of Roads, Airfield, and Heliports in the Theater of Operations—Road Design, Field Manual No. 5-430-00-1, No. 32-8013, vol. 1 (1994) http://www.adtdl.army.mil/cgi-bin/atdl.dll/fm/5-430-00-1/CH9.htm.
Fisher, Robert B., “Feature Space Transmission for line detection,” Available in Cvonline Compendium of Computer Vision, (2001) http://www.dai.ed.ac.uk/cVouline.
Vandegrift, C.J., et al., Unit 7: Route Surveying, LS/LSIT Video Exam preparation course workbook, Caltrans Geometronics (1993).
Black Thomas G.
Donnelly Arthur D.
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corp.
LandOfFree
Application of the hough transform to modeling the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Application of the hough transform to modeling the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Application of the hough transform to modeling the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3189676