# Patent

## Title
Apparatus for creating a navigation map

## Abstract

To display a navigation map for a navigation device more accurately and realistically and with less memory capacity, roads, railroad lines, rivers, lakes, and similar cartographic parameters are composed not of straight lines but of Cornu spirals. A Cornu spiral is defined by its curvature and its length.

## Background
BACKGROUND OF THE INVENTION
The present invention relates to the field of navigation systems, and in particular to a vehicle navigation system that stores map data using Cornu spiral data.
Conventional navigation systems typically represent roads and rivers to be displayed on a navigation system display unit as straight lines. However, this type of simplified cartographic reproduction has a number of disadvantages. For example, roads and rivers are not straight lines. As a result, a navigation map displayed on the navigation system display unit does not accurately represent the features of roads and rivers. In an attempt to more accurately represent roads and rivers, the number of straight line segments used to define the roads and rivers can be increased. However, this leads to a large increase in the amount of data that must be stored to accurately represent features such as roads, rivers and railroad lines.
Therefore, there is a need for a navigation system that accurately models and displays information indicative of features such as for example roads and rivers without requiring large amounts of memory.
SUMMARY OF THE INVENTION
Briefly, according to an aspect of the present invention, a vehicle navigation system includes navigation map data memory comprising map data composed of Cornu spirals indicative of cartographic features such as roads, railroad lines, rivers and lakes.
Rather than representing roads, railroad lines, rivers, and similar cartographic parameters by a sequence of straight lines, the present invention specifies that these cartographic parameters are provided as Cornu spirals.
In one embodiment, a vehicle navigation system that receives sensor data from a plurality of sensors, and provides a map image that is presented on a display, includes a navigation map data memory that includes map data indicative of roadways stored in Cornu spiral form. The system also includes a navigation processing unit that receives the sensor data, and requests map data from the navigation map data memory associated with the sensor data, and computes the map image from the map data.
Advantageously, the amount of memory required to store the parameters of the navigation map is reduced, while the accuracy of the navigation map is increased.
These and other objects, features and advantages of the present invention will become more apparent in light of the following detailed description of preferred embodiments thereof, as illustrated in the accompanying drawings.



BRIEF DESCRIPTION OF THE DRAWING
FIG. 1 is a pictorial illustration of a road in Cornu spiral representation;
FIG. 2 is a block diagram illustration of a vehicle navigation system comprising a navigation map memory device that includes map data stored as Cornu spiral representations;
FIG. 3 is a pictorial illustration of the same road illustrated in FIG. 1, but represented by the prior art technique of straight line segments.



DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 is a pictorial illustration of a road 10 in Cornu spiral representation. A Cornu spiral is defined as a curve whose curvature is proportional to its arc length. A Cornu spiral can be calculated by the following formula:

l=Ka2  EQ. 1

where l represents the arc length and K the curvature. In parameter form, the equations of a Cornu spiral can be expressed as coordinates as follows:





  
    
      
        x
        =
        
          a
          ⁢
          
            π
          
          ⁢
          
            
              ∫
              
                τ
                =
                0
              
              t
            
            ⁢
            
              
                cos
                ⁡
                
                  (
                  
                    
                      π
                      2
                    
                    ⁢
                    
                      τ
                      2
                    
                  
                  )
                
              
              ⁢
              
                
              
              ⁢
              
                d
                τ
              
            
          
        
      
    
    
      
        EQ
        .
        
          
        
        ⁢
        2
      
    
  
  
    
      
        
          y
          =
          
            a
            ⁢
            
              π
            
            ⁢
            
              
                ∫
                
                  τ
                  =
                  0
                
                t
              
              ⁢
              
                
                  sin
                  ⁡
                  
                    (
                    
                      
                        π
                        2
                      
                      ⁢
                      
                        τ
                        2
                      
                    
                    )
                  
                
                ⁢
                
                  
                
                ⁢
                
                  d
                  τ
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            with
            ⁢
            
              
            
            ⁢
            t
          
          =
          
            l
            
              a
              ⁢
              
                π
              
            
          
        
      
    
    
      
        EQ
        .
        
          
        
        ⁢
        3
      
    
  




Since these integrals cannot easily be solved, an embodiment of the invention makes use of a Taylor series development, which can be expressed as follows:





  
    
      
        
          
            
              X
              k
            
            ⁡
            
              (
              t
              )
            
          
          =
          
            a
            ⁢
            
              π
            
            ⁢
            
              (
              
                
                  
                    1
                    
                      0
                      !
                    
                  
                  ⁢
                  
                    
                      π
                      0
                    
                    
                      2
                      0
                    
                  
                  ⁢
                  
                    1
                    1
                  
                  ⁢
                  
                    t
                    1
                  
                
                -
                
                  
                    1
                    
                      2
                      !
                    
                  
                  ⁢
                  
                    
                      π
                      2
                    
                    
                      2
                      2
                    
                  
                  ⁢
                  
                    1
                    5
                  
                  ⁢
                  
                    t
                    5
                  
                
                +
                
                  
                    1
                    
                      4
                      !
                    
                  
                  ⁢
                  
                    
                      π
                      4
                    
                    
                      2
                      4
                    
                  
                  ⁢
                  
                    1
                    9
                  
                  ⁢
                  
                    t
                    9
                  
                
                -
                
                  
                    1
                    
                      6
                      !
                    
                  
                  ⁢
                  
                    
                      π
                      6
                    
                    
                      2
                      6
                    
                  
                  ⁢
                  
                    1
                    13
                  
                  ⁢
                  
                    t
                    13
                  
                
                +
                ...
              
              )
            
          
        
        ⁢
        
          

        
        ⁢
        and
      
    
    
      
        EQ
        .
        
          
        
        ⁢
        4
      
    
  
  
    
      
        
          
            Y
            k
          
          ⁡
          
            (
            t
            )
          
        
        =
        
          a
          ⁢
          
            π
          
          ⁢
          
            (
            
              
                
                  1
                  
                    1
                    !
                  
                
                ⁢
                
                  
                    π
                    1
                  
                  
                    2
                    1
                  
                
                ⁢
                
                  1
                  3
                
                ⁢
                
                  t
                  3
                
              
              -
              
                
                  1
                  
                    3
                    !
                  
                
                ⁢
                
                  
                    π
                    3
                  
                  
                    2
                    3
                  
                
                ⁢
                
                  1
                  7
                
                ⁢
                
                  t
                  7
                
              
              +
              
                
                  1
                  
                    5
                    !
                  
                
                ⁢
                
                  
                    π
                    5
                  
                  
                    2
                    5
                  
                
                ⁢
                
                  1
                  11
                
                ⁢
                
                  t
                  11
                
              
              -
              
                
                  1
                  
                    7
                    !
                  
                
                ⁢
                
                  
                    π
                    7
                  
                  
                    2
                    7
                  
                
                ⁢
                
                  1
                  15
                
                ⁢
                
                  t
                  15
                
              
              +
              ...
            
            )
          
        
      
    
    
      
        EQ
        .
        
          
        
        ⁢
        5
      
    
  




The series is truncated after a given term, so that a polynomial remains. The terms of the polynomials are preferably stored in a table.

Since all Cornu spirals are similar, there exists a unit Cornu spiral with parameter value a that is equal to one (i.e., a=1). In a preferred embodiment, the terms of the polynomials of the unit Cornu spiral are stored in a table and the actual Cornu spirals are calculated from these values. The coordinates of the unit Cornu spiral are stored in a table and the actual Cornu spirals are calculated from these values.
Compared to the conventional representation of roads by sequential straight lines, the present inventive provides a number of advantages. For example, the accuracy of the image is substantially increased, because an exact position exists not only at the points where two straight lines join, but rather over the course of the curve. The reproduction of roads, rivers, and the like is much more realistic. In addition, the representation of the indicated cartographic parameters by Cornu spirals requires fewer parameters than the prior art technique of using sequential straight lines. This saves considerable storage space in a navigation device that creates the inventive navigation map.
Because a navigation map with a Cornu spiral representation reproduces the actual pattern of roads and the like much more accurately than a representation with sequential straight lines, locations can be determined much better. Thus, for example, the route of a traveled road, measured by sensors, can be recovered more easily in a navigation map with a Cornu spiral representation, because the parameters can be calculated over the entire course of the curve.
A navigation map in Cornu spiral representation is suited both for navigation and for display. Consequently, a navigation device that creates the inventive navigation map no longer needs two navigation maps, as is the case in prior art systems. That is, in the prior art one of these two navigation maps is used for navigation, while the other is used for display.
Predictive route data describe the future route, for example for the next one to two kilometers. With a representation by Cornu spirals, predictive route data, for example, can be taken directly from the navigation map and are not required to be calculated online, which saves computing time.
In Germany, and also in other countries where geography permits, roads are constructed as Cornu spirals for the sake of higher traffic safety. As a result, the inventive representation of Cornu spirals is thus especially realistic. The quality of this representation approaches that of an aerial photograph.
FIG. 2 is a block diagram illustration of a vehicle navigation system 20 comprising a navigation map memory device 22 that includes map data stored as Cornu spiral representations. The navigation system 20 also includes a navigation processing unit 24 that receives data from a plurality of sensors 26-28 and input commands from a user input interface 30. The components may be connected via a MOST bus. The system 20 also includes a display 32, which is used to display the navigation map and other navigation information. Significantly, the navigation map data memory 22 includes map data stored as Cornu spiral data.
FIG. 3 is a pictorial illustration of the prior art technique for representing the same road as illustrated in FIG. 1. Specifically, a section of a road 40 is represented by five straight lines 41-44 and six points 46-51. In contrast, the same road illustrated in FIG. 1 is represented by two Cornu spirals 62-63 and three points 64-66. Despite using only two Cornu spirals and three points, the inventive representation illustrated in FIG. 1 is more accurate and realistic than the prior art representation with five straight lines and six points as shown in FIG. 3. The six points 46-51 illustrated in FIG. 3 require six x-coordinates and six y-coordinates, for a total of twelve coordinates. In contrast, referring to FIG. 1, the technique of the present invention requires the x- and y-coordinates of three points and the curvature K for the three points 64-66, for a total of nine coordinates.
Although the present invention has been shown and described with respect to several preferred embodiments thereof, various changes, omissions and additions to the form and detail thereof, may be made therein, without departing from the spirit and scope of the invention.

## Claims

1. A vehicle navigation system that receives sensor data from a plurality of sensors, and provides a map image that is presented on a display, the system comprising:
a navigation map data memory that includes map data indicative of roadways stored in Cornu spiral form and data indicative of a unit Cornu spiral; and
a navigation processing unit that receives the sensor data, and requests map data from the navigation map data memory associated with the sensor data, and computes the map image from the map data,
where terms of polynomials of the unit Cornu spiral are stored in the navigation map data memory and the map image is computed using the terms of polynomials of the unit Cornu spiral, where the terms of polynomials are associated with Taylor series expressions indicative of the Cornu spiral, where the Cornu spiral is of the form l=Ka2, where l is indicative of arc length and K is indicative of curvature.

2. A vehicle navigation system that receives sensor data from a plurality of sensors, and provides a map image that is presented on a display, the system comprising:
a navigation map data memory that includes map data indicative of roadways stored in Cornu spiral form and data indicative of a unit Cornu spiral; and
a navigation processing unit that receives the sensor data, and requests map data from the navigation map data memory associated with the sensor data, and computes the map image from the map data,
where terms of polynomials of the unit Cornu spiral are stored in the navigation map data memory and the map image is computed using the terms of polynomials of the unit Cornu spiral, where the terms of polynomials are associated with Taylor series expressions indicative of the Cornu spiral, where the navigation map data memory includes coordinates of the unit Cornu spiral stored in a table, from which the Cornu spirals of the navigation map are derived.

3. A vehicle navigation system that receives sensor data from a plurality of sensors, and provides a map image that is presented on a display, the system comprising:
a navigation map data memory that includes map data indicative of roadways stored in Cornu spiral form and data indicative of a unit Cornu spiral; and
a navigation processing unit that receives the sensor data, and requests map data from the navigation map data memory associated with the sensor data, and computes the map image from the map data,
where terms of polynomials of the unit Cornu spiral are stored in the navigation map data memory and the map image is computed using the terms of polynomials of the unit Cornu spiral, where the terms of polynomials are associated with Taylor series expressions indicative of the Cornu spiral, where the navigation map data memory includes coordinates of the unit Cornu spiral stored in a table, from which the Cornu spirals of the navigation map are derived for roads, railroad lines, rivers, lakes, and similar cartographic parameters defined as Cornu spirals.

4. A vehicle navigation system that receives sensor data from a plurality of sensors, and provides a map image that is presented on a display, the system comprising:
a navigation map data memory that includes map data indicative of roadways stored in Cornu spiral form and data indicative of a unit Cornu spiral; and
means for receiving the sensor data, for requesting map data from the navigation map data memory associated with the sensor data, and for computing the map image from the map data,
where the means for computing computes the map image using Cornu spiral polynomial coefficients stored in the navigation map data memory, and terms of polynomials of the unit Cornu spiral are stored in the navigation map data memory and the map image is computed using the terms of polynomials of the unit Cornu spiral, where the terms of polynomials are associated with Taylor series expressions indicative of the Cornu spiral and the Cornu spiral is of the form l=Ka2, where l is indicative of arc length and K is indicative of curvature.

5. A vehicle navigation system that receives sensor data from a plurality of sensors, and provides a map image that is presented on a display, the system comprising:
a navigation map data memory that includes map data indicative of roadways stored in Cornu spiral form and data indicative of a unit Cornu spiral; and
means for receiving the sensor data, for requesting map data from the navigation map data memory associated with the sensor data, and for computing the map image from the map data,
where the means for computing computes the map image using Cornu spiral polynomial coefficients stored in the navigation map data memory, and terms of polynomials of the unit Cornu spiral are stored in the navigation map data memory and the map image is computed using the terms of polynomials of the unit Cornu spiral, where the terms of polynomials are associated with Taylor series expressions indicative of the Cornu spiral and the navigation map data memory includes coordinates of the unit Cornu spiral stored in a table, from which the Cornu spirals of the navigation map are derived.

6. A vehicle navigation system that receives sensor data from a plurality of sensors, and provides a map image that is presented on a display, the system comprising:
a navigation map data memory that includes map data indicative of roadways stored in Cornu spiral form and data indicative of a unit Cornu spiral; and
means for receiving the sensor data, for requesting map data from the navigation map data memory associated with the sensor data, and for computing the map image from the map data,
where the means for computing computes the map image using Cornu spiral polynomial coefficients stored in the navigation map data memory, and terms of polynomials of the unit Cornu spiral are stored in the navigation map data memory and the map image is computed using the terms of polynomials of the unit Cornu spiral, where the terms of polynomials are associated with Taylor series expressions indicative of the Cornu spiral and the navigation map data memory includes coordinates of the unit Cornu spiral stored in a table, from which the Cornu spirals of the navigation map are derived for roads, railroad lines, rivers, lakes, and similar cartographic parameters defined as Cornu spirals.