STATEMENT OF COPYRIGHTED MATERIAL

[0001] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the PTO patent file or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND OF THE INVENTION

Field of the Invention

[0002] This invention relates generally to digital map updating techniques, and more particularly toward realigning and/or attributing road networks using probe data images without actual matching to probe data.

Related Art

[0003] Personal navigation devices 10 like that shown for example in Figure 1 utilize digital maps combined with accurate positioning data from GPS or other data streams. These devices have been developed for many useful applications. The effectiveness of such navigation systems is inherently dependent upon the accuracy and completeness of the information as provided in the form of digital maps and associated features and attribute data. Typically, the navigation system 10 includes a display screen 12 or graphic user interface that portrays a network of streets 14.

[0004] A traveler having access to a GPS-enabled navigation device 10 may then be generally located on the digital map close to or with regard to a particular road 14 or segment thereof. Some GPS-enabled navigation devices 10, like several models manufactured by TomTom N.V. (www.tomtom.com), may be also configured as probes to generate probe data points at regular intervals. Such probe data points comprise a sequence of discrete positions recorded at intervals of, for example, five seconds and appropriately time stamped. Of course, other suitable devices may be used to generate probe data points including for example handheld devices, mobile phones, PDAs, mobile mapping vehicles, and the like. [0005] It is thus known to take probe data inputs from low-cost positioning systems and handheld devices for the purpose of incrementally creating and/or updating digital maps. The input to be processed typically consists of recorded GPS traces in the form of a standard ASCII stream, which is supported by almost all existing GPS devices. The output may be a trace line in the form of a directed graph with nodes and edges, or links, associated with travel time information. The probe data, which creates the nodes or probe positions at regular intervals, can be transmitted to a collection service or other map making or data analysis service via wireless (e.g., cellular) transmission, internet uploads, or by other convenient methods. Internet uploads may be synchronized to occur in conjunction with digital map upgrades which many users obtain as part of a subscription service. Through the collection of probe data, road geometries can be inferred and other features and attributes derived by appropriate algorithms.

[0006] Digital maps are frequently composed as a mosaic of geo-coded image tiles which, when arranged side-by-side create a bird's eye mosaic (BEM) of a particular surface of interest, such as a section of land on the earth. An exemplary tile is generally indicated at 16 in Figure 2 and may represent either a non-rectified or an ortho-rectified area of land. The particular size or scale of a tile 16 can vary from one digital map to the next, but, as shown in Figure 2, frequently comprises an area sufficient to contain a modest number of roads 14 and road segments when depicting an urban area for example. Thus, the tile 16 shown in Figure 2 would be merely one of many tiles which together make up a digital map of the type contained in a digital map database.

[0007] Probe traces collected over time can be grouped according to those which match to a common tile 16 and then overlaid for interpretation and re-alignment exercises. Using various mathematic and statistical techniques, road geometries can be inferred, speed profiles computed, changes in road networks detected, comparisons made between two road networks, and the like. A typical collection of probe data collected from a plurality of probes traversing a particular tile section over an extended period of time may contain billions of discreet data points, each time stamped. Plotting these massive amounts of data onto a digital map can lead to interpretation mistakes and in any event has proven to be a cumbersome task.

[0008] There exists a need for new and improved techniques for re-aligning and attributing road networks contained in outdated, unreliable digital maps based on newer, more reliable source data. SUMMARY OF THE INVENTION

[0009] A method is provided for realigning a road network in an unreliable digital map based on reliable external data using rigid body manipulation techniques. A digital map is provided. The digital map presents a road network corresponding to a network of roads in reality. A rigid body model is created from the digital map. The rigid body model comprises a mesh of adjoining triangles each having edges interconnected by nodes. A road element in the road network is represented as a segmented series of road edges. The road edges coincide with selected triangle edges in the mesh, with the road edges being joined end-to-end at triangle notes. An external data source is provided. The external data source represents reliable vehicle position probability densities correlated to the digital map. The vehicle position probability densities represent a proportional image force tending to attract the road element. A shape retention force is assigned to each node in the triangular mesh which connects two or more road segments, and applies only to those edges which coincide with road segments. The shape retention force resists the image force. Edges in the triangle mesh that do not coincide with a road edge are defined as a spring. A spring force is established for each spring. Springs and road edges are realigned relative to the external data source by iteratively balancing the image forces and the shape retention forces as a function of the spring forces until local optimums are reached throughout the digital map. Thus, triangular edges coinciding with the road edges are moved to a more accurate new shape from an inaccurate original shape.

[0010] By methods of this invention, realignment of road database content can be easily made on the input, for example, from a community of navigation device users or by other means of providing reliable external source data. Thus, complete but outdated road networks can be updated with newer, more reliable data without the need to match existing road networks to probe data or other cumbersome techniques.

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] These and other features and advantages of the present invention will become more readily appreciated when considered in connection with the following detailed description and appended drawings, wherein:

[0012] Figure 1 is an exemplary view of a portable navigation system according to one embodiment of the subject invention including a display screen for presenting map data information; [0013] Figure 2 is an exemplary view of a tile as may form part of a mosaic in a digital map of the type contained in databases and used for navigation purposes;

[0014] Figure 3 is an exemplary data flow diagram depicting how probe source data is grouped, compared and integrated with a digital map database according to one embodiment of this invention;

[0015] Figures 4 A and 4B schematically depict the process of filling up probability density arrays according to this invention and emphasizing the incremental nature of the preferred process. Figure 4A depicts the creation of new digital map content whereas Figure 4B illustrates a scenario in which existing digital map content is updated based on probe data;

[0016] Figure 5 is a view of the tile as shown in Figure 2 and superimposed with raw probe data in the form of discreet, time-stamped probe positions collected from a plurality of probes traversing the tile over some definable time period;

[0017] Figure 6 is a statistical raster image of the tile of Figure 5 wherein the raw probe data has been processed according to the techniques of this invention so as to graphically represent road existence probabilities in gray scale format;

[0018] Figure 7 depicts a pixilated object referred to herein as a "brush" which represents probability density of vehicle position and comprises an array of values representing

Gaussian probability distribution;

[0019] Figure 8 depicts five exemplary brushes showing variation in the degree to which positional distribution may be focused, the leftmost brush corresponding generally to the brush of Figure 7 and representing a more focused positional distribution and smaller deviation, with each of the next successive brushes representing larger and larger uncertainties of the position and thus increasingly higher positional deviations;

[0020] Figure 9 depicts a calculated Bezier curve extending between two probe traces, with the ends of the curve represented by raw probe points such that their positional accuracy is higher than the region in between;

[0021] Figure 1OA is a simplified representation of a section of a digital map containing unreliable or outdated road network information;

[0022] Figure 1OB is a view as in Figure 1OA but showing the creation of a rigid body model from the digital map comprising a mesh of adjoining triangles, with road network elements coinciding with selected triangle edges; [0023] Figure 1OC is a visual presentation of the probability density for vehicles traveling the road network of Figure 1OA as depicted in raster image format according to the principles of this invention;

[0024] Figure 11 is a simplified, enlarged raster type image shown in pixelated format and stationed alongside is a single road edge or segment from a road element;

[0025] Figure 12 is a simplified view showing two road edges adjoined at a common node and wherein an original inaccurate shape is shown in broken lines for one segment;

[0026] Figure 13 is a view of a single road edge extending between two nodes and graphically depicting the manner in which spring forces are applied to the nodes in the form of cumulative effects or forces coming from all other springs connected or attached to each node; and

[0027] Figure 14 is an example of actual probe data results graphically presented so as to display estimated probability densities in raster image format and showing the result of road network realignment according to this invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

[0028] Referring to the Figures, wherein like numerals indicate like or corresponding parts throughout the several views, this invention pertains to digital maps as used by navigation systems, as well as other map applications which may include those viewable through internet enabled computers, PDAs and the like.

[0029] Figure 3 depicts, in schematic form, one example of how the subject invention may be implemented in a real- life digital map editing process. A probe data source 18 represents a collection of probe data from a plurality of probes, wherein each probe develops a respective probe trace comprising a sequence of discreet, time-stamped probe positions which are capable of being plotted relative to a particular digital map containing tiles 16 like that shown in Figure 2. A first step in the process 20 groups the probe data per tile in the digital database. For example, all probe traces which traverse a particular tile 16 are grouped together for further analysis. Tile data is received from a tile database 22 which, of course, is associated with a suitable metadata catalog 24 to provide accuracy, position, source, currency and other data relevant to features in each particular tile. From the grouped probe traces, appropriate curves can be calculated using any suitable technique. This step is represented at function block 26. For example, internal metadata may enable the application of Bezier curves for the tile as depicted at 28. A Bezier curve is well known in the field of mathematics and numerical analysis. Generally stated, a Bezier curve is a parametric curve useful to describe or control velocity over time of an object moving from one point to the next. Tile contents can then be calculated at function block 28 in terms of position, altitude, etc. Metadata is stored at function block 32. This may include tile pixel values such as position, altitude, speed and the like. From this, a final image can be created for each tile at 34 which is then used to update the tile database 22.

[0030] According to this invention, probability density arrays contain cumulative values that can be summed up out of all probe traces traversing through a tile. This mathematical edition operation is incremental by its nature. Depending on the circumstances, probability density arrays may indicate the need to create new road segments in a particular tile, or to update some feature or attribute of an existing road segment. Figure 4A shows a somewhat simplified flow diagram of that in Figure 3 where new arrays are created as metadata for a particular tile due to the previous absence of an associated road in the existing tile database 22. Figure 4B is similar to Figure 4A, except existing metadata arrays are loaded from storage and then updated using the newly processed probe data before being stored at function block 32. Comparison of Figures 4A and 4B help to illustrate that the process does not differ much between creation and updating scenarios. Processing time per probe traces may be practically the same in each scenario. It linearly depends on the number of probes to be processed in a particular update cycle.

[0031] Figure 5 shows the tile 16 of Figure 2 with superimposed raw probe data although analysis of this type of probe data is more typically done on the metadata arrays directly. Nevertheless, for human beings serving as digital map editors, it is often helpful to perceive data in image format. According to this invention, methods are provided whereby raw probe data can be converted to visualizable data to assist human editors at interpreting the images. To visualize a probability density array, it is necessary to apply smart normalization. In other words, positional probability density arrays can be visualized by normalizing contents of the array, such as with a formula according to the following:

where:

B = brightness factor (i.e., the brightness of pixel in image)

P = cumulative probability density in the array of summed probe traces

7 _ r (&max-log _t (P _max ))

Pmax = max value in the array £ _ gimiκ-6min

b min = V25 = 5 (brightness max and min)

0 079

S =— (single probe contribution)

[0032] By applying these techniques, it is possible to create a representation of readable probe data, taking into account proper probability models, so that database editors can more easily interpret confidence in position of road center lines as they exist in reality.

[0033] Directly applying these techniques, therefore, it is possible to convert the raw probe data as presented in Figure 5 in the form of a raster image representing, by way of brightness variations, road existence probabilities and thereby achieve from this raw probe data the image shown in Figure 6. Thus, by summing the grouped probe traces into arrays, vehicle position probability densities can be estimated and then converted to a brightness factor B. This brightness factor can then be used to create a proportional gray scale brightness and applied to the tile 16 so that the tile 16 depicts the estimated road existence probabilities as a raster image.

[0034] Turning now to Figures 7-9, the step of estimating vehicle position probability density is described in greater detail with regard to the development of a pixilated brush representing an array of probe trace values in a Gaussian probability distribution. In other words, the brush pixel size is used to proportionally reflect the calculated positional uncertainty. For estimating probability density of vehicle position, and eventually road positions, a simple array is used where values are summed up based on Gaussian probability density of car position represented by a single probe trace. For all probe traces traversing the array, values are summed up again.

[0035] To represent probability density of vehicle position, an object may be used called a brush, as shown in Figures 7 and 8. The brush is actually an array of values representing Gaussian probability distribution. Each value in the brush is a number between 0 and 1 representing Gaussian probability. All pixels of that brush are summed up to 1. The smaller the brush size, the more focused its positional distribution. In other words, a smaller brush size reflects a smaller deviation in the probability density. Conversely, the larger the brush size, the greater uncertainty of position that exists. Figure 8 shows a series of probability distribution brushes. The left hand most brush is the smallest and most focused. The brush on the far right hand side is the largest brush representing the highest positional deviation. The intervening brushes represent progressively greater uncertainty moving from left toward the right.

[0036] The probability density array thus contains cumulative values of brushes which are rendered, i.e., summed up, along the trace the vehicle was following. Depending on various factors like speed and positional accuracy, the certainty of estimated position is either lower or higher. Thus, considering an example where two traces of vehicles are moving at different speeds along the same road segment, it will be noted that the low speed vehicle entails high position uncertainty while the high speed vehicle moves in a more predictable way. Figure 9 shows a curve represented by raw probe points at each end. Thus, positional accuracy in the ends or nodes is higher than in the intervening region. When all probe traces are rendered into a probability density array, a cumulative road position probability density can be derived.

[0037] This invention aims to realign road networks so that they fit into an image generated out of community input probe data or from some other reliable external data source. The method of this invention comprises, generally, modeling a road network 14 as a planar rigid body built of a mesh of adjoining triangles, which may be derived from aerial triangulation techniques or by other suitable methods. The triangle edges are treated, in varying degrees, like springs. That is, each triangle edge in the entire mesh is thought of as having a certain elastic property. Road elements coincide with some of the triangle edges but are treated with unique elastic qualities. Using the probe statistical image methods described above, the probability of real road existence is represented as an external image force field applied to the rigid body model created for the road network. Then, iterative recalculations are made of all forces (internal spring forces and external image forces) until balance is reached thus representing a local optimum. This approach effectively utilizes a complete road network which may be outdated and thus unreliable in the current time frame. Incomplete, statistical road network information, such as may be represented by probe data is used to update the outdated map information. This invention provides a reliable, repeatable and accurate method by which the old, unreliable network can be fit into the newer but incomplete probe data without requiring a match of the road network to the probe data. Therefore, the subject invention represents an approach which has many advantages over prior techniques, and which does not require the difficult, time consuming step of matching probe data or other external source data to the old road network. [0038] Turning now to Figures lOA-C, a simplified road network 14' is shown in Figure 1OA. According to the techniques of this invention, a rigid body model is created, as shown in Figure 1OB, so that as a result there are numerous triangle edges adjoining one another in a mesh-like irregular grid. This rigid body model can be created by any available technique, including but not limited to aerial triangulation methods which incorporate local topography. Road elements in the road network 14' become integrated with the triangle mesh, with each road element comprising a segmented series of road edges in the mesh. The road edges coincide with selected triangle edges in the mesh as shown in Figure 1OB. These road edges are joined end-to-end at triangle nodes.

[0039] Using the statistical probe image techniques referred to earlier, probe data collected from the network of roads in reality used to create a reliable vehicle position probability density as shown in Figure 1OC. The vehicle position probability densities represented in this manner can be taken to represent a proportional image force or energy field which generates gradient force depending on the difference in pixel brightness.

[0040] Figure 11, for example, presents an enlarged view of a portion of a digital map which includes vehicle position probability densities presented as raster images 36. The pixelated nature of the images is represented by the grid- like pattern of cells. An exemplary road edge 38 extends between nodes 40, 42. Normally, the road edge 38 would be strung end-to-end with other road edges to make up a road element 14, 14' in a road network. According to this approach, the statistical probe image 36 is used as an external energy field which generates gradient force depending on the difference of pixel brightness in the neighborhood of a particular road network node. As shown in Figure 11, the force applied to the node 42 is a cumulative force composed from eight directional gradient forces referencing from each of the adjacent, surrounding pixels. Thus, for calculating image force, each node 40, 42 is considered one at a time based on these neighboring gradient forces. The image force normalization vectors, when properly summed, determine force directions. Therefore, the vehicle position probability densities represented by the statistical probe images 36 proportionally attract the nodes 40, 42 of the road elements 38.

[0041] An objective of this invention is to align the road network with the reliable external data. The alignment process is the result of a simulation of rigid body behavior when various forces are applied to the triangle mesh. The forces are the result of an energetic model of rigid body behavior during the process of matching the model (existing digital map) to the statistical image 36. The forces include the image energy described above, together with a shape energy or shape memory energy shown, for example, in Figure 12. Thus, one of the internal forces applied to the rigid body model is a force responsible for preserving original shape of the road network. In Figure 12, road edges 44, 46 are shown. They are joined end- to-end by a common node 48, normally forming part of a much larger road network 14, 14'. Road edge 44 extends between node 48 and node 50. Road edge 46 extends between node 48 and node 52. Shape retention forces preserve the original shape of certain road elements. This is particularly useful in road and road network situations, wherein road curvature or other geometrical relationships may be important to preserve during the realignment process. If such original shape constraints are not observed, it could happen that the road changes unacceptably from a leftward turn into a rightward turn or some other unintended distortion is introduced. To prevent such results, the shape force or shape retention force is used.

[0042] The shape force is applied to each node 48 connecting two or more road segments 44, 46, and is proportional to the angular difference between the current shape and original shape of every road segment pair 44, 46 in the node 48. In Figure 12, the original shape of road edge 46 is shown by broken line and its current shape in solid. The angular difference is a result of forces Fl and F2, where force Fl reacts through node 50 and force F2 reacts through node 52. Applying each of these forces Fl, F2 proportionally to node 48, which connects the two road edges 44, 46, the resulting shape retention force F is derived. By this technique, the original, desired shape of certain road geometries can be maintained. For the sake of clarity, it is restated that the shape retention force is applied only between elements 44, 46 representing road segments and not to other triangle edges which may exist in mesh of the rigid body model.

[0043] Another type of internal force applied to the rigid body model is a spring force. The spring force is represented by the letter "I", for example, in Figure 13 within a free body diagram which may be applicable to any triangle edge in the rigid body model, but of course not to a road edge or a boundary edge. This spring force is proportional to the difference between an edge's current length or new length after realignment and its original or rest length. Thus, in the example of Figure 13, a spring 54 is shown extending between nodes 56 and 58. The spring force resulting from the realignment process causes force F3 to act in a tensile mode against node 56 and another tensile force F4 acting in the opposite direction against node 58. The resulting spring force I is shown. Thus, spring forces I are applied to the nodes 56, 58 and are cumulative forces coming from all springs attached to the nodes 56, 58. [0044] Using these realignment principles, in which an iterative balancing of the image forces and shape retention forces are recalculated, as a function of the spring forces I, outdated road networks can be more accurately aligned based on reliable external source data. As shown in the example of Figure 14, the broken lines overlying statistical image data represent the old, unreliable road networks which have been moved or realigned to the solid lines as shown which represent their new or current locations. By such means, it is possible to fit complete but old road networks into newer but incomplete probe data using statistical probe images as the input. One particular advantage of this technique is that it does not require a matching of the road network to the probe data as demanded by prior art techniques.

[0045] As a result of the rigid body modeling procedure, numerous triangle edges are created. All of these triangle edges can be modeled as springs (i.e., having particular properties like spring factor, damping etc.) and nodes which connect the springs. However, if all of the triangle edges are treated as elastic link, it is preferable to distinguish at least three spring types: road spring, interconnecting spring, and border spring. The road spring is equivalent to the road edge defined earlier (Figure 12), and represents a road segment from original database. An interconnecting spring is equivalent to the spring link described above (Figure 13), and is created during triangulation and connecting road springs (or other interconnecting springs). A border spring is yet another class or type of spring or edge feature having certain unique qualities in the context of presumed elastic specifications or damping factors. A border spring is a spring created during triangulation and located at the edge of a tile 16. It has special meaning of keeping whole network in a rectangular tile form. Naturally, other spring types may be created, as needed, without detracting from the basic concepts of this invention.

[0046] The foregoing invention has been described in accordance with the relevant legal standards, thus the description is exemplary rather than limiting in nature. Variations and modifications to the disclosed embodiment may become apparent to those skilled in the art and fall within the scope of the invention.