Patent Description:
A map or navigation database may contain attributes about roads or vehicle paths, including a number of lanes of vehicle traffic. The number of lanes may be used to generate a navigation command. The navigation command or the number of lanes may be sent to a user (e.g. to a user's mobile device) or to a vehicle.

The number of lanes for the road or vehicle path may be determined based on top-down images of the road or path. For example, satellite imagery of roads and paths may be manually reviewed to count the number of lanes present. Additionally or alternatively, images taken from street level may be reviewed to count the number of lanes. Manual counting of vehicle lanes may be time consuming and limited by the resolution of the reviewed images. In some cases, machine learning may be applied to the images to count the lanes.

<NPL>) discloses an approach for automatically computing the number and location of driving lanes on a road by using a Gaussian mixture model to model the distribution of GPS traces across multiple traffic lanes.

The invention is defined by the set of appended claims.

Exemplary embodiments of the present invention are described herein with reference to the following drawings.

The number of lanes present on a road or vehicle path is determined from location data. Location data from vehicles or uses traversing the road or vehicle path are used to determine the number of lanes. The location data are a measurement of a position. For example, a global positioning system (GPS) or global navigation satellite system (GNSS) may be used to measure a location of a user or vehicle traversing the road or path.

Vehicles traversing a road or path may remain in a lane, resulting in gaps between vehicles in different lanes. Accordingly, location data recorded by the vehicle or a user traversing the path may be confined to one lane of the road or path. Where location data from multiple vehicles is collected, the location data may be denser (e.g. more location data per linear or two-dimensional space) within a lane than between lanes. A difference in density may be more pronounced where vehicles maintain "lane discipline" and remain in a lane.

The location data may be collected from multiple vehicles or users traversing a path. The location data may include a coordinate or registration of the vehicle or user. For example, the location data may include a latitude, a longitude, a height, or other information. Additionally or alternatively, the location data may include a registration relative to the road or path. For example, the location data may include a length along a path, a lateral distance from a centerline of the path, and a height above the path. In some cases, the registration may be determined by matching the location data to a map.

The location data, including the coordinates or registration, are grouped into one or more clusters. The number of clusters of the location data may be a count of the number of lanes on the road or path. In some cases, a density-based clustering method may be applied to the location data. For example, the density-based spatial clustering of applications with noise (DBSCAN) clustering method may be used.

While the clustering method may be expected to create clusters corresponding to the number of lanes, error in the measurement of the vehicle or user location reduces the difference in density between the lane and the space between lanes on the road or path. Though a vehicle may be traveling in a single lane for the length of the road or path, errors in measurement of the location of the vehicle may indicate the vehicle was traveling in between lanes or in multiple lanes. In particular, errors in the lateral position of the vehicle or user relative to the path may obscure any difference in location data density between lanes. In some cases, location measurements from GPS systems may have errors between <NUM> and <NUM> meters. Errors may be caused by weak signals received from positioning satellites (e.g. due to trees, tunnels, or tall buildings attenuating or reflecting positioning signals).

Applying a clustering method to the location data including the error may result in clusters that do not correspond to lanes on the road or path. For example, a clustering method may group a location point of the location data into one cluster based on a distance between the location point and neighboring location points of the location data. Due to location data errors and a lack of definition between lanes (e.g. similar location data density across the road or path), the clustering method may group the location data into clusters that are perpendicular to the road or path.

Pre-processing the location data before clustering may improve the correspondence between a number of clusters and a number of lanes on a road or path. For example, projecting the location data points onto a line that is perpendicular to a center line of the road or path and eliminating outlier location data may make it more likely that a clustering method applied to the processed location data results in a number of clusters that accurately counts a number of lanes on the road or path. For curved roads or paths, the path may be approximated by one or more linear segments, each location point of the location data may be matched to one of the segments, and the location data may be projected onto lines perpendicular to each linear segment. The number of clusters (and number of lanes) for each segment may be collected and the number of lanes for the whole curved path may be determined as the most common number of lanes for the segments.

<FIG> illustrates an example system for collecting location data. One or more vehicles <NUM> are connected to a server <NUM> though a network <NUM>. The vehicles <NUM> may be directly connected to the server <NUM> or through an associated mobile device <NUM> or another intermediary. The mobile devices <NUM> and vehicles <NUM> may include a position sensor <NUM> configured to measure a position of the mobile device <NUM> or vehicle <NUM>. The server <NUM> may be connected to a database <NUM>. Additional, different, or fewer components may be included.

The mobile device <NUM> may be a standalone mobile device, such as a smartphone, or a device integrated with a vehicle <NUM>. The mobile device <NUM> may include or be in communication with a positioning sensor <NUM>. The mobile device may be configured to store location information generated by the positioning sensor <NUM>. In some cases, the mobile device may send the location information to the server <NUM>. The mobile device may include an application, such as a mapping or navigation application. In some cases, the application may receive the location information. The mobile device <NUM> may receive mapping or navigation information from the server <NUM>. The application may use the received mapping or navigation information. For example, the application may use a navigation command sent by the server and received by the mobile device <NUM> to display navigation information on the mobile device <NUM>.

The vehicle <NUM> may be any kind of machine that transports good or people. For example, the vehicle may be a motor vehicle (e.g. a car or a truck,) an aircraft (e.g. an airplane, helicopter, or a drone), a watercraft (e.g. a boat or hovercraft), or another kind of vehicle. The vehicle <NUM> may contain or be in communication with a positioning sensor <NUM>. The vehicle <NUM> may be configured to send location information generated by the positioning sensor to the server <NUM> or to the mobile device <NUM>. In some cases, the mobile device <NUM> may receive the location information from the vehicle <NUM> and send the location information to the server <NUM>.

The vehicles <NUM> and mobile devices <NUM> may communicate with the server <NUM> through the network <NUM>. The network may be one of a variety of types of wireless networks. Example wireless networks include cellular networks, the family of protocols known as Wi-Fi or IEEE <NUM>, the family of protocols known as Bluetooth, or another protocol. The cellular technologies may be analog advanced mobile phone system (AMPS), the global system for mobile communication (GSM), third generation partnership project (3GPP), code division multiple access (CDMA), personal handy-phone system (PHS), and <NUM> or long-term evolution (LTE) standards, <NUM>, DSRC (dedicated short-range communication), or another protocol.

The database <NUM> may be a geographic database. The geographic database may store information including maps and location data generated by the position sensors <NUM>. The geographic database may be configured to send information such as map information to the server <NUM>. Information stored in the database <NUM> may be updated by the server <NUM>.

The server <NUM> may be configured to receive location data or location information generated by position sensors <NUM> from the mobile devices <NUM> and the vehicle <NUM> through the network <NUM>. The server <NUM> may be configured to process the location information to update a map or to generate a mapping or navigation command. For example, the server <NUM> may be configured to determine a number of lanes of path based on the received location information and to update a map stored in the database <NUM> based on the number of lanes. In another example, the server is configured to determine a navigation command for the mobile device <NUM> or the vehicle <NUM> based on the received location information. The navigation command may be an autonomous driving command instructing the mobile device <NUM> or the vehicle <NUM> to take an action. The navigation command may include a route for the mobile device <NUM> or vehicle <NUM>.

The position sensor <NUM> may generate location data including one or more measurements of the position sensor at a point in time. The location data may be generated by receiving GNSS or GPS signals and comparing the GNSS or GPS signals to a clock to determine the absolute or relative position of the vehicle <NUM> and/or mobile device <NUM>. The location data may be generated by receiving radio signals or wireless signals (e.g., cellular signals, the family of protocols known as Wi-Fi or IEEE <NUM>, the family of protocols known as Bluetooth, or another protocol) and comparing the signals to a prestored pattern of signals (e.g., a radio map). The mobile device <NUM> may act as the position sensor <NUM> for determining the position, or the mobile device <NUM> and the position sensor <NUM> may be separate devices. Additionally or alternatively, the vehicle <NUM> may act as the position sensor <NUM> for determining the position, or the vehicle <NUM> and the position sensor <NUM> may be separate devices.

The location data may describe a geographic location, for example with a longitude value and a latitude value. In addition, the location data may include a height or altitude. Additionally or alternatively, the location data may include a heading. The location data may be collected over time and include timestamps. In some examples, the location data is collected at a predetermined time interval (e.g., every second, every <NUM> milliseconds, or another interval). In some examples, the location data is collected in response to movement by the position sensor <NUM> (e.g., the sensor reports location information when the position sensor <NUM> moves a threshold distance). The predetermined time interval for generating the location data may be specified by an application or by the user. The interval for providing the location data from the mobile device <NUM> to the server <NUM> may be may the same or different than the interval for collecting the location data. The interval may be specified by an application or by the user.

The mobile device <NUM> may transmit the location data to the server <NUM> so that the server <NUM> may provide a service to the mobile device according to the location data. For example, the mobile device <NUM> or vehicle <NUM> may send location data to the server <NUM> and the server <NUM> may return a location-based service to the mobile device <NUM> or vehicle <NUM>, such as a navigation command. In some cases, the navigation command may include a route, a position of the mobile device <NUM> or vehicle <NUM> on a map, or an autonomous driving command.

<FIG> illustrates an example path <NUM> with location data <NUM>. The location data may be projected along a projection vector <NUM> to an aggregation axis <NUM> that is perpendicular to a centerline <NUM> of the path <NUM>. The centerline <NUM> may be centered between the path boundaries <NUM>.

The path <NUM> is a road or other path traversed by a vehicle or user. For example, the path <NUM> may be a path suitable for a pedestrian, a drone, a boat, a bike, a vehicle, or a handicapped user. The path <NUM> may be divided into one or more lane to guide traffic along the path <NUM>. Vehicle or user traffic may flow in one or both directions along the path <NUM>. For example, the path <NUM> may be a two-lane road accommodating one lane of vehicle traffic in either direction along the path <NUM>. In another example, the path may be a multi-lane highway accommodating multiple lanes of traffic in either direction. Though the path <NUM> shown includes three lanes, any number of lanes may be present on the path <NUM>. The number of lanes on the path <NUM> may be not be known or no number of lanes may be associated with the path <NUM>.

The location data <NUM> are a measurement of a position of a vehicle traversing the path <NUM>. In some cases, a positioning sensor of the vehicle or of a user device may measure the position or location of the user or vehicle traversing the path <NUM>. The location data <NUM> include one or more location measurements from one or more users or vehicles traversing the path <NUM>. For example, a vehicle may record multiple measurements of the location of the vehicle at different points during traversal of the path. A positioning sensor may measure the location. For example, the positioning sensor may use GPS or GNSS to measure a location of the vehicle or the user. The positioning sensor may be a part of a vehicle or of a user device. The user device may be a mobile device such as a cell phone.

The projection vector <NUM> represents the path of a portion of the location data <NUM> as the data <NUM> is projected onto the aggregation axis <NUM>. Each measurement of the location data <NUM> are projected along a vector <NUM> onto the axis <NUM>. The projection vector <NUM> follows the course of the path <NUM>. In some cases, the projection vector <NUM> may be parallel to a centerline <NUM> or boundary <NUM> of the path <NUM>. In some other cases, the projection vector <NUM> may remain proportionally between the boundaries of the path <NUM>. For example, the vector <NUM> may remain at a distance of one quarter of the width of the path <NUM> away from one of the boundaries as the path <NUM> narrows from one end to another. In still other cases, the vector <NUM> may be perpendicular to the aggregation axis <NUM>.

The aggregation axis <NUM> is defined as perpendicular to a centerline <NUM> of the path <NUM>. The aggregation axis <NUM> is a line on which the location data <NUM> is projected. By projecting the location data <NUM> onto the aggregation axis <NUM>, information about the position of the location data <NUM> along the length of the path <NUM> may be removed and information about the position of the location data <NUM> along a width of the path <NUM> may be preserved. The information in the location data <NUM> along the length of the path <NUM> may be removed because every point of the location data <NUM> shares the position of the aggregation axis along the length of the path <NUM>. The aggregation axis <NUM> may be defined at a start, end, or other position along the path <NUM> or a segment of the path <NUM>. Multiple aggregation axes <NUM> may be defined for a path <NUM>. For example, where the path <NUM> has a curve, the path may be broken into segments and an aggregation axis <NUM> defined for each segment of the path <NUM>.

The centerline <NUM> may be defined as being in the middle of the path boundaries <NUM>. For example, the centerline may divide in half a width of the path <NUM>. Additionally or alternatively, the location of the centerline <NUM> may be predefined and the boundaries <NUM> defined relative to the centerline <NUM>. For example, the boundaries <NUM> may be located at a predefined distance from the centerline <NUM>. In some cases, the centerline <NUM> may be an estimate of the center of the path <NUM> or a geometric reference line for the path. For example, the centerline <NUM> may occupy an estimated position that differs in position from a geometric center of the path <NUM>. In another example, the centerline <NUM> may be a geometric reference line corresponding to a course or position of the path <NUM>. The geometric reference line may generally indicate the position of the path <NUM> but not precisely or perfectly indicate an exact boundary, position, center, or other geometric or geographic attribute of the path <NUM>.

The path boundaries <NUM> may indicate an edge of the path <NUM>. For example, the boundaries <NUM> may be located at the width of the path <NUM>. Location data <NUM> outside of the boundaries <NUM> may be ignored or excluded from determining a number of lanes of the path <NUM>. In some cases, the positions of the path boundaries <NUM> may not be known. For example, only the centerline <NUM> of the path <NUM> is known but not the path boundaries <NUM>.

<FIG> illustrates an example projection of location data <NUM>. When projected onto the aggregation axis <NUM> perpendicular to the center line <NUM>, the location data <NUM> may become projected location data <NUM>.

According to the invention the projected location data <NUM> lie along the aggregation axis <NUM>. In other examples useful for understanding the invention, outlier location data points of the location data <NUM> may be removed from the location data <NUM> prior to the location data <NUM> being projected on the aggregation axis <NUM> to form projected location data <NUM>. Removing outlier data points may improve the efficiency and accuracy of clustering the projected location data <NUM>.

<FIG> illustrates an example clustering of projected location data <NUM>. The projected location data <NUM> may lie on an aggregation axis <NUM> that is perpendicular to a centerline <NUM> of a path. The projected location data <NUM>, aggregation axis <NUM> and centerline <NUM> may be the projected location data <NUM>, aggregation axis <NUM>, and centerline <NUM> of <FIG>. The projected location data <NUM> may be grouped into one or more clusters <NUM>.

The clusters <NUM> may be formed by applying a clustering method to the projected location data <NUM>. For example, a density-based clustering method such as DBSCAN may be used. DBSCAN groups points of the location data into clusters by defining core points, reachable points, and outliers. Alternatively, a hierarchical density clustering method such as HDBSCAN may be used. For DBSCAN, a first location data point of the projected location data <NUM> may be a core point if a minimum number of other location points are within a predetermined distance (e.g. a "neighborhood") of the core point. Every location data point in the neighborhood of the first point are directly reachable from the first point. A second location data point may be a reachable point if a path may be constructed from the second point to the first point using only other points that are directly reachable from the first point (e.g. all the location data points on the path are core points). A point may be an outlier point if it is not reachable from any other points. A core point may form a cluster <NUM> with the other points that are reachable from (e.g. in the neighborhood of) the core point. By changing the value of cluster criteria such as the distance of the neighborhood and the minimum number of other location points required to define a core point, different arrangements, and numbers of clusters <NUM> may be formed from the same projected location data <NUM>. The different arrangements or sets of clusters created according to different cluster criteria may be evaluated by determining a degree of overlap between the clusters <NUM>. Clusters with minimal overlap may more accurately reflect or correspond to the number of lanes on the path.

<FIG> illustrate fitting a curved path <NUM> with linear segments 401a-d. Aggregation axes 407a-d may be defined for each segment 401a-d upon which location data <NUM> may be projected. The path <NUM> may be the path <NUM> from <FIG> or path <NUM> from <FIG>. The aggregation axes 407a-d may be the aggregation axis <NUM> from <FIG> or <NUM> from <FIG>. The location data <NUM> may be the location data <NUM> or projected location data <NUM> from <FIG> or the projected location data <NUM> from <FIG>.

The path <NUM> may have a bend or curved geometry. Because of the curve, it may be computationally expensive to project the location data <NUM> onto an aggregation axis <NUM> of the path <NUM>. Instead, the path <NUM> (and the location data <NUM>) may have segments 401a-d fitted to it.

In some cases, the path <NUM> may be a straight line and have segments 401a-d fitted to it. For example, the path <NUM> may represent a straight section of highway with an on ramp that merges into a lane. Because the path <NUM> may have different widths and lanes along the length of the path <NUM>, it may be advantageous to break the straight path <NUM> into linear segments 401a-d and to determine the number of lanes present over each section. For example, breaking a path into segments 401a-d may allow for each segment to be analyzed in parallel.

The segments 401a-d may be fitted to the path <NUM>. The segments 401a-d may be linear segments approximating a curvature of the path <NUM>. The segments 401a-d may be continuous over the length of the path <NUM>. The segments 401a-d may have a uniform length or different lengths. A centerline of each respective segment 401a-d. may represent the segments 401a-d.

The segments 401a-d may be fitted to the curvature of the path <NUM> using any technique. For example, one or more points on the segment <NUM> a-d may be aligned on the path. A first end of the segment 401a may correspond or have the same location as a first end of the path <NUM>. Additionally or alternatively, a midpoint or other point on the segment 401a-d may lie on the path <NUM> and the segment 401a-d may be oriented to be tangent to the path <NUM> at the point lying on the path <NUM>. Combinations of the above techniques may be used to fit the segments 401a-d to the path <NUM>. The segments 401a-d may serve as a centerline for the path <NUM>.

The aggregation axes 407a-d may be defined for each segment 401a-d of the path <NUM>. The aggregation axes 407a-d may be determined to be perpendicular to the path segments 401a. For example, the aggregation axis 407a may be perpendicular to the path segment <NUM>.

The location data <NUM> may be divided and associated with one of the segments 401a-d. For example, location data points of the location data <NUM> lying on either side of the segment 401a will be associated with segment 401a, but not any of the other segments. The location data <NUM> associated with each segment 401a-d may be grouped into clusters for each segment. The number of clusters for each segment 401a-d may represent a number of lanes for that segment 401a-d. The most popular number of lanes for the segments 401a-d may be chosen as a number of lanes for the entire path <NUM>. For example, segment 401a may be determined to have two lanes while segments 401b-d may be determined to have three lanes. In this case, the path <NUM> may be determined to have three lanes because the majority of segments 401a-d were determined to have three lanes. In another example, an average is taken of the number of lanes determined for the segments 401a-d.

<FIG> illustrates an example flowchart for estimating a number of lanes. Additional, different, or fewer acts may be provided. For example, acts S103 and S105 may not be performed. The acts may be performed in any order. For example, acts S117-S121 may be performed after acts S123 and S125. In some cases, acts S109 and S111 may be alternatives. In some other cases, both act S109 and act Sill are performed. The acts of <FIG> may be performed by the server <NUM> in communication with the geographic database <NUM>.

In act S101, location data is received. The communication interface <NUM> of the server <NUM> or the receiver <NUM> of the lane count estimator <NUM> may receive the location data. The location data indicate the position of one or more vehicles or users traversing a path. For example, the location data may be collected by a position sensor of a vehicle <NUM> or a mobile device <NUM> of the user. The location data include a plurality of location points. The location points may be individual measurements of the location of a vehicle or a user. A positioning sensor may measure the location. The positioning sensor may be in communication with or a part of a vehicle or a mobile device of a user. In some cases, the location data includes only vehicles, users, or mobile devices moving in a similar direction. For example, the location data may only include positions of vehicles or users traversing the path in the same or similar direction (e.g. east to west, north to south, left to right). Multiple sets of location data may be received for each direction of travel on the path. In some other cases, the location data includes position information from vehicles, mobile devices, and users traveling in more than one direction. Subsets of the location data may be formed that each contain vehicles, mobile devices, or users traveling in the same or a similar direction of travel along the path.

In act S103, one or more path segments are fitted to the path. The server <NUM> may be configured to receive the path from the database <NUM> and fit the path segments to the path. Additionally or alternatively, the vehicle path processor <NUM> may be configured to fit the path segments to the path. The segments may be linear segments. Together, the path segments may form a linear approximation of the path. The segments may be continuous. In some cases, a geometry (e.g. a curvature) of the path (or of a centerline of the path) may be defined based on one or more shape points. The one or more path segments may be fit to the path by connecting the shape points. In this way, the path segments may follow the geometry of the path or of a centerline of the path. Each path segment may have an aggregation axis.

In act S105, location data is matched to the path segments. The server <NUM> may be configured to match the location data received by the communication interface <NUM> to the path segments via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the vehicle path processor <NUM> may be configured to match the data to the segments. When the path is divided into segments or approximated by path segments, the location data for the path may also be divided. Location points of the location data may be matched to a path segment. For example, a distance between the location point and the one or path segments may be determined. The location point may be matched to the nearest path segment. By matching the location points to the segments, a subset of the location data may be associated with each path segment. The subset of location data may include only those vehicles, users, or mobile devices traversing the path in the same or a similar direction of travel.

According to the invention, in act S107, the location data are projected onto an aggregation axis. The server <NUM> may be configured to project the location data received by the communication interface <NUM> onto an aggregation axis via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the aggregator <NUM> may be configured to project the data. The aggregation axis is defined as perpendicular to a centerline of the path or path segment. The aggregation axis may extend indefinitely or have a defined length. For example, the aggregation axis may extend to the width of the path. In some other cases useful for understanding the invention, location points outside the width or boundary of the path may be excluded or removed from the location data. The location data are projected along a projection vector that is perpendicular to the aggregation axis. In some cases, projecting the location data may involve moving a location data point to the aggregation axis. In some other cases, projecting the location data modifying the information associated with location points of the location data such that the location point is not registered long a length of the path and retains only information about a position of the location point along a width of the path. In still other cases, location data corresponding to only one direction of travel may be projected onto the aggregation axis. For example, a subset of location data including vehicles, users, or mobile devices traversing the path in the same or a similar direction of travel may be projected onto the aggregation axis.

In act S109, a centroid of location data may be determined. The server <NUM> may be configured to determine the centroid of the data received by the communication interface <NUM> via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the statistics processor <NUM> may be configured to determine the centroid. In some cases, the location data may contain multiple measurements of a vehicle or user traversing the path. These may be considered to be from the same "trace" of the vehicle or user. In some cases, the location points measuring the position of the same user or vehicle multiple times may be termed "vehicle-common" or "user-common. " The centroid of the vehicle-common or user-common location data may be found. The centroid may be a point at a geometric center of the vehicle-common or user-common location points.

In act S111, the vehicle-common or user-common location points may be projected onto a line that is perpendicular to a centerline of a path or path segment. The server <NUM> may be configured to project the vehicle-common or user-common location data via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the aggregator <NUM> may be configured to project the vehicle-common or user-common location data onto a line. In some cases, the vehicle-common or user-common location points may be projected onto the line in a manner similar to act S107. A mean or average position of the vehicle-common or user-common location data as projected onto the line may be determined.

In act S113, a representative point of the vehicle-common or user-common location data is chosen. The server <NUM> may be configured to choose the representative point via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the location data processor <NUM> may be configured to determine the representative point. In some cases, the representative point is chosen based on the centroid determined in act S109. For example, the representative point may be a location point of the vehicle-common or user-common location data that is closest to the centroid. In some other cases, the representative point is chosen based on the mean or average position determined in act S111. For example, the representative point may be a location point of the vehicle-common or user-common location data (as projected on the line) that is closest to the mean or average position.

In act S115, the location points of the vehicle-common or user-common location data other than the representative point may be removed. The server <NUM> may be configured to remove the non-representative vehicle-common or user-common location points via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the location data processor <NUM> may be configured to remove the location points of the vehicle-common or user-common location data other than the representative point. By choosing a representative point and discarding the rest of the location data generated by a particular vehicle or user, the accuracy and efficiency of the clustering may be improved. For example, having fewer location points to group into clusters may reduce the time needed to create the cluster. In another example, keeping only the representative point may prevent potentially erroneous location points from being clustered, thereby improving a correspondence between a number of clusters determined for the path and the number of lanes on the path. Also, a slow-moving vehicle, user, or mobile device will contribute more to the density as compared to a faster moving vehicle, user, or mobile device on the same path. Choosing a representative point may ensure that only one point per vehicle, user, or mobile device contributes to the density of the total points.

In act S117, a standard deviation may be determined for the location data as projected onto the aggregation axis. The server <NUM> may be configured to determine the standard deviation via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the statistics processor <NUM> may be configured to determine the standard deviation. The standard deviation may be determined for the lateral positions of the location points on the aggregation axis. The standard deviation may be found my finding a mean position of the location data on the aggregation axis, finding a difference between each location point and the mean, squaring the differences, adding the differences together, dividing by one less than a number (e.g. a count) of the location points, and taking the square root of the result. Where the standard deviation is smaller than the typical width of a single lane road, it may be determined that the path has only a single lane. In this case, it may not be necessary to cluster the location data to determine the number of lanes.

In act S119, a linear range is determined along the aggregation axis. The server <NUM> may be configured to determine the linear range via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the statistics processor <NUM> may be configured to determine the linear range. A width of the linear range may be based on the mean and the standard deviation determined for the location data as projected on the aggregation axis. In some cases, the linear range may extend to a distance of a multiple of a standard deviation beyond the mean. For example, the linear range may extend <NUM> standard deviations beyond the mean.

In act S121, an outlier subset of the location data may be removed. The server <NUM> may be configured to remove outlier location data via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the location data processor <NUM> may be configured to remove outliers. The outlier subset may be those location points of the location data outside of the linear range. The remaining location points after removal of the outlier subset may be a remainder. Removing the outlier points may help improve the efficiency and accuracy of clustering.

In act S123, a density of the location data along the aggregation axis may be determined. The server <NUM> may be configured to determine the density via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the statistics processor <NUM> may be configured to determine the density. The density may be a measure of the number of location points per unit length along the aggregation line. Determining the linear density along the aggregation axis may help identify regions of lower density. Such low-density regions may correspond to gaps between lanes.

In act S125, location data is removed based on the density. The server <NUM> may be configured to remove location points based on the density via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the location data processor <NUM> may be configured to remove location data based on the density. For example, a threshold minimum density may be specified. Location points residing in sections of the aggregation axis having a density below the threshold may be removed. Because low-density may indicate a gap between vehicles or users traveling in a lane, the location data may be removed from lower-density areas because the location points in such areas may be erroneous. For example, the location data points between lanes may be due to an error in the positioning system or due to a vehicle or user changing lanes. In another example, a method like Local Outlier Factor (LOF) can be used.

In act S127, the location data are grouped into clusters. The server <NUM> may be configured to group the location data into clusters via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the aggregator <NUM> may be configured to group the location data into clusters. The location data may be the remaining data after location data points were removed in one or more of acts S115, S121, and S125. The location data as projected onto the aggregation axis may be grouped into clusters. Where there are multiple aggregation axes, for example where the path has been broken into path segments, the location data on each aggregation axis may be grouped into clusters. The location data may be clustered by applying a clustering method to the location data. For example, DBSCAN or HDBSCAN may be used.

Multiple sets of clusters may be generated according to different cluster criteria. For example, with DBSCAN, different clustering scenarios are possible by changing the cluster criteria for a core point: the size (distance) of a neighborhood and the minimum number of points in the neighborhood. Creating different sets of clusters based on different cluster criteria may allow for more accurate determination of the number of lanes on the path. In some cases, the multiple clusters may be displayed on a display <NUM> or input device such as a personal computer or terminal <NUM>. In some other cases, the cluster criteria may be selected based on input from an input device <NUM>, <NUM>.

In act S129, a degree of overlap of the clusters is determined. The server <NUM> may be configured to determine a measure of overlap between the clusters via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the statistics processor <NUM> may be configured to determine a measure of overlap between the clusters. Cluster overlap may be measured by determining a silhouette coefficient. The overlap may be determined for each set of clusters from act S127 according to different cluster criteria.

In act S131, a silhouette coefficient is determined. The server <NUM> may be configured to determine the silhouette coefficient via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the statistics processor <NUM> may be configured to determine the silhouette coefficient. The silhouette coefficient may take into account a measure of the distance between a location point and every other location point in the same cluster and also a measure of the distance between the location point and other location points in other clusters. The clusters have little overlap and are very distinct when the silhouette coefficient approaches <NUM>, and more overlap when the silhouette coefficient approaches -<NUM>. The silhouette coefficient may be determined for each set of clusters grouped according to different cluster criteria.

In act S133, a grouping or set of clusters is chosen based on minimizing overlap between clusters. For example, a set of clusters having a highest overall silhouette coefficient for the location points may be chosen. The server <NUM> may be configured to choose the grouping or set of clusters via instructions stored in the memory <NUM> and executed by the processor <NUM>. Additionally or alternatively, the geographic data processor <NUM> may be configured to choose the grouping or set of clusters. In some cases, the grouping or set of clusters may be chosen based on input from an input device <NUM>, <NUM>.

In act S135, a number of lanes is determined for the path based on the number of clusters. For example, where three clusters are formed from the location data, the path may be determined to have three lanes. The server <NUM> may be configured to determine the number of lanes via instructions stored in the memory <NUM> and executed by the processor <NUM>. The server <NUM> may update the database <NUM> with the number of lanes for the path. Additionally or alternatively, the geographic data processor <NUM> may be configured to determine the number of lanes. Where the path has been split into segments, the number of lanes for the whole path including all the segments may be based on a number of clusters formed by a majority of the segments. For example, where a majority of the segments have location data grouped into five lanes, the whole path may be determined to have five lanes. Where there is no majority, the number of lanes may be chosen based on an average number of lanes or based on another method.

<FIG> illustrates another example system for collecting location data. The system may include one or more positioning sensors <NUM> in communication with a mobile device <NUM> and vehicle <NUM> traversing a path <NUM>.

The positioning sensor <NUM> may be in communication with or a part of the mobile device <NUM> or the vehicle <NUM>. The positioning sensor <NUM> may measure a location of the vehicle <NUM> or the mobile device <NUM> as the vehicle <NUM> or the mobile device <NUM> traverse the path <NUM>. The positioning sensor <NUM> may generate location information including multiple measurements of the location of the vehicle <NUM> or the mobile device <NUM>. The measurements may be location points indicating the measured positions of the vehicle <NUM> or the mobile device <NUM>. The positioning sensor <NUM> may send the location information including one or more location points to the mobile device <NUM> or the vehicle <NUM>.

The mobile device <NUM> may receive a stream of location information from the positioning sensor <NUM>. For example, the positioning sensor <NUM> may periodically measure the location of the mobile device <NUM> as it traverses the path <NUM>. The mobile device <NUM> may send the location information to the server <NUM> of <FIG>. The mobile device <NUM>. may belong to or be associated with a user.

The vehicle <NUM> may receive a stream of location information from the positioning sensor <NUM>. For example, the positioning sensor <NUM> may periodically measure the location of the vehicle <NUM> as it traverses the path <NUM>. The vehicle <NUM> may send the location information to the server <NUM> of <FIG>.

The path <NUM> is a path traversed by the mobile device <NUM> or the vehicle <NUM>. The database <NUM> of <FIG> may store information about the path. For example, the path may have a number of lanes of traffic and the number of lanes may be stored in the database <NUM>. The server <NUM> may be configured to determine the number of lanes of traffic on the path <NUM> based on location information generated by position sensors <NUM> on the path <NUM>. For example, location information from both vehicles <NUM> shown may be used by the server <NUM> to determine that there are two lanes of traffic on the path. The path may have more or fewer lanes of traffic.

<FIG> illustrates a further example system for collecting location data. The system may include a mobile device <NUM>, for example, as described in <FIG> and <FIG>. The Mobile device <NUM> may include a processor <NUM>, an input device <NUM>, a communication interface <NUM>, a network interface <NUM>, a memory <NUM>, a display <NUM>, and a position circuitry <NUM>. Different or fewer components may be present. For example, the mobile device <NUM> may not include position circuitry <NUM>. In another example, the network interface is part of the communication interface <NUM>.

The processor <NUM> may be a general processor or application specific integrated circuit. The processor <NUM> may retrieve or receive instructions stored in the memory <NUM> and execute the instructions.

The input device <NUM> may be used for interacting with the mobile device <NUM> or to change settings of the mobile device <NUM>. For example, the input device <NUM> may be used to interact with an application of the mobile device <NUM>, such as a mapping or navigation application. In another example, the input device <NUM> may be used to specify a setting of the position circuitry <NUM>. The input device <NUM> may be used to specify the interval at which the position circuitry measures a location of the mobile device <NUM>.

The communication interface <NUM> may provide for the exchange of information between the mobile device <NUM> and outside systems. For example, the communication interface <NUM> may form a connection to one or more position sensors or other sensors that are external to the mobile device <NUM>. In another example, the communication interface may form a connection between the mobile device and a vehicle. In this way, the mobile device may send and receive data to the sensors and vehicles external to the mobile device. For example, the mobile device may receive location information from a position sensor that is part of the vehicle.

The network interface <NUM> may form a connection to the network <NUM>. For example, the network interface <NUM> may be coupled with antennas for transmitting and receiving data. In some cases, the network interface <NUM> forms a connection to the network <NUM>. In this way, the network interface <NUM> may allow for the exchange of data between the mobile device <NUM> and the server <NUM> or the database <NUM>. In some cases, the network interface <NUM> may be a part of the communication interface <NUM>.

The memory <NUM> may be a volatile memory or a non-volatile memory. The memory <NUM> may include one or more of a read only memory (ROM), random access memory (RAM), a flash memory, an electronic erasable program read only memory (EEPROM), or other type of memory. The memory <NUM> may be removable from the mobile device <NUM>, such as a secure digital (SD) memory card. The memory <NUM> may store instructions to cause the processor <NUM> to perform one or more acts. The memory may be configured to store location information from the position circuitry <NUM> or a positioning sensor.

The display <NUM> may be a liquid crystal display (LCD) panel, light emitting diode (LED) screen, thin film transistor screen, or another type of display. An output interface of the display <NUM> may also include audio capabilities, or speakers. The display <NUM> may indicate a status or other information about the mobile device <NUM>, the positioning circuitry <NUM>, or a positioning sensor in communication with the mobile device <NUM>. The display <NUM> may display mapping or navigation information. For example, a navigation or mapping application on the mobile device <NUM> may use the display to present mapping or navigation information.

The position circuitry <NUM> may be a positioning sensor. For example, the position circuitry may use GPS or GNSS to measure its location. In some cases, the position circuitry <NUM> may be remote from the mobile device <NUM>. The position circuitry <NUM> may communicate with the processor <NUM> directly or through one or more intermediaries. For example, the position circuitry may communicate with the processor <NUM> of the mobile device <NUM> through the communication interface <NUM>. The position circuitry <NUM> may measure a location of the mobile device <NUM>. In some cases, the position circuitry <NUM> measures the location of the mobile device <NUM> periodically or at a predetermined interval. The position circuitry <NUM> may be configured to send the measured location to the mobile device <NUM>, for example to the processor <NUM>. The location information generated by the position circuitry <NUM> may be sent to the server <NUM>.

<FIG> illustrates an example server <NUM>. The server <NUM> may be the server <NUM> of <FIG>. The server <NUM> may include a processor <NUM>, a memory <NUM>, a communication interface <NUM>, and an input device <NUM>. The server <NUM> may be in communication with a database <NUM>.

The memory <NUM> may be a volatile memory or a non-volatile memory. The memory <NUM> may include one or more of a read only memory (ROM), random access memory (RAM), a flash memory, an electronic erasable program read only memory (EEPROM), or other type of memory. The memory <NUM> may be removable from the server <NUM>, such as a secure digital (SD) memory card. The memory <NUM> may store instructions to cause the processor <NUM> to perform one or more acts. The memory may be configured to store location information from the position circuitry <NUM> or a positioning sensor.

The communication interface <NUM> may provide a connection between the server <NUM> and the network <NUM>. In some cases, the communication interface <NUM> may facilitate the receipt of the location information from the mobile device <NUM> or the vehicle <NUM>.

The input device <NUM> may be a keyboard, terminal, or personal computer. The input device may be used to enter or modify settings of the server <NUM>. For example, the setting may include one or more cluster criteria. In another example, the settings including selection of a particular path for which a number of lanes is to be determined. In some cases, the input device may be used to select one or more location information preprocessing steps, such as density-based location data removal, standard deviation-based location data removal, or vehicle-common or user-common location data removal.

The database <NUM> may be directly connected to the server <NUM> or accessible though a network <NUM>. For example, the server <NUM> may communicate with the database <NUM> through the communication interface <NUM>. In some cases, the database may be stored in the memory <NUM>. The database <NUM> may be configured to store location information.

<FIG> illustrates an example system for assigning a number of lanes on a path. The system may include a lane count estimator <NUM>. The lane count estimator may include a receiver <NUM>, a location data processor <NUM>, a statistics processor <NUM>, a vehicle path processor <NUM>, an aggregator <NUM>, and a geographic data processor. More, different, or fewer components may be provided. The lane count estimator <NUM> may be implemented by the server <NUM> of <FIG> and <FIG> or by another computing device remote to the mobile device <NUM> and vehicle <NUM>.

The receiver <NUM> be configured for digital or analog communication with one or more position sensors. For example, the receiver <NUM> may be configured to receive location information from one or more position sensors through the network <NUM>. The receiver may be implemented by or a part of the communication interface <NUM> of the server <NUM>. The receiver <NUM> may include one or more amplifiers, digital to analog converters, or analog to digital converters. The location data received by the receiver may include a plurality of location points recorded by one or more vehicles or mobile devices.

The location data processor <NUM> may be implemented by the processor <NUM> based on instructions stored in the memory <NUM> of the server <NUM>. The location data processor <NUM> may be configured to remove a portion of the location data. For example, the location data processor may be configured to remove a number of location data points in the location data that were generated by the same vehicle, user, or mobile device. The location data points generated by the same vehicle, user, or mobile device may be referred to as vehicle-common or user-common because each of the location points is associated with a common vehicle, user, or mobile device. The location data processor <NUM> may be configured to determine a representative point of the vehicle-common or user-common location points and to remove the rest of the vehicle-common or user-common location points (e.g. those location points not selected as the representative point) from the location data. The location data processor <NUM> may be configured to select the representative point based on a centroid of the vehicle-common or user-common location points. For example, the representative point may be the vehicle-common or user-common location point closest to the centroid. Additionally or alternatively, where the vehicle-common or user-common location points are projected on a line perpendicular to a centerline of the path, the representative point may be the vehicle-common or user-common location point closest to a mean of the vehicle-common or user-common location points. Where the location data includes multiple sets of vehicle-common or user-common location points (e.g. a plurality of vehicles each having generated more than one location point along the path), the selection of the representative point and removal of the non-selected points may be repeated for each set of vehicle-common or user-common location points.

The location data processor <NUM> may be configured to perform standard deviation-based outlier removal on the location data. The outliers may be the portion of the location data removed by the location data processor <NUM>. A linear range may be defined (e.g. by the statistic processor <NUM>) for the location data projected onto the aggregation axis. The linear range may be based on a standard deviation and/or the mean of the location data. The location data processor <NUM> may be configured to remove the location points that lie outside of the linear range from the location data. The location points that lie outside of the linear range may be referred to as an outlier subset of location data.

The location data processor <NUM> may be configured to perform density-based outlier removal on the location data. The outliers may be the portion of the location data removed by the location data processor <NUM>. A minimum threshold density may be defined below which location data is to be excluded. Removing location points lying in less dense areas may more clearly define the lanes present on the path after grouping the location data into clusters. The location data processor <NUM> may be configured to remove those location points residing in a linear space having below the minimum threshold density. The density may be defined as a minimum number of location points per unit distance. For example, the minimum threshold density may be <NUM> location point per meter. Where a location data point is more than <NUM> meters from its nearest neighboring location data points (e.g. the location point is the only location point located on a section of the aggregation axis longer than <NUM> meter, or the distance from the nearest neighbor to the right of the location data point to the nearest neighbor to the left of the location data point is greater than <NUM> meter), the location data processor <NUM> may be configured to remove the location point.

The location data processor <NUM> is configured to select a grouping or arrangement of clusters of the location data based on a degree of overlap determined for the clusters. Where multiple arrangements or sets of clusters of the location data have been generated based on multiple cluster criteria, the location data processor <NUM> selects an arrangement or set of clusters with the least or minimal overlap between clusters. Minimizing cluster overlap may improve correspondence between a number of clusters and a number of lanes for the path.

The statistics processor <NUM> may be implemented by the processor <NUM> based on instructions stored in the memory <NUM> of the server <NUM>. The statistics processor <NUM> may be configured to determine one or more mathematical quantities of the location data. For example, the statistics processor <NUM> may be configured to determine a mathematical quantity such as a standard deviation of the location information. In some cases, the statistics processor <NUM> may determine a standard deviation of the location data as projected on the aggregation axis. In some cases, the statistics processor <NUM> may be configured to determine a mean or average lateral position of the location data as projected on the aggregation axis. Based on the standard deviation and/or the mean, the statistics processor <NUM> may configured to determine a linear range on the aggregation axis. For example, the linear range may extend at a width of one standard deviation on either side of the mean. In another example, the linear range extends <NUM> standard deviations on either side of the mean. Other multiples of the standard deviation may be used to define the linear range. The width of the linear range may correspond to a width of the path. For example, the linear range may be chosen to be smaller than the width of the path. Location data points located outside of the linear range may be removed or discarded from the location data prior to grouping into clusters.

The statistics processor <NUM> may be configured to determine a mathematical quantity such as a mean of vehicle-common or user-common location points as projected onto a line perpendicular to the centerline of the path. The mean may be used by the location data processor to pick a representative point.

The statistics processor <NUM> may be configured to determine a mathematical quantity such as a centroid of vehicle-common or user-common location points. The centroid may be defined as a point that minimizes the sum of squared distances between the centroid and the vehicle-common or user-common location points (for a particular vehicle, user, or mobile device). The centroid may be determined for each set of vehicle-common or user-common location points where the location data includes multiple location points from multiple, vehicles, users, or mobile devices.

The statistics processor <NUM> may be configured to determine a mathematical quantity such as a density of the location points as projected on the aggregation axis. The density may be defined as a number of location points per linear unit of distance along the aggregation axis. The density may be defined for subsections of the aggregation axis. In some cases, the density may be determined for each span of <NUM> meters along the aggregation axis. For example, where a span of the aggregation axis is <NUM> meters wide and includes <NUM> location points, the density on the subsection of the aggregation axis may be determined to be <NUM> points per meter. Spans of the aggregation axis having below a threshold density may be removed from the location data.

The statistics processor <NUM> may be configured to determine a mathematical quantity such as a degree of overlap between clusters of location data. The degree of overlap may be measured or indicated by a silhouette coefficient or another measure. The degree of cluster overlap may be determined for each set or arrangement of clusters when multiple sets or arrangements of clusters have been generated according to multiple cluster criteria.

The vehicle path processor <NUM> may be implemented by the processor <NUM> based on instructions stored in the memory <NUM> of the server <NUM>. The vehicle path processor <NUM> may be configured to linearize a curve of a path. For example, the vehicle path processor <NUM> may fit one or more linear path segments to the path. The path segments may be fit to a centerline or other part of the path. An optimal fit may reduce any deviation by the path segments from the path. Together, the one or more path segments may form a linear approximation of the path. When the path has been approximated, segmented into, or otherwise represented by path segments, the vehicle path processor <NUM> may be configured to match subsets of the location data to the segments. In some cases, a location point of the location data may be matched to whichever path segment is closest to the location point. Each location point of the location data may be matched to a single path segment so that a non-overlapping subset of the location data is associated with each path segment (e.g. each location point is only associated with a single path segment).

The aggregator <NUM> may be implemented by the processor <NUM> based on instructions stored in the memory <NUM> of the server <NUM>. The aggregator <NUM> may be configured to project the location points of the location data onto the aggregation axis. The aggregation axis may be defined as a line perpendicular to a centerline of the path. The aggregator <NUM> may be configured to project only those location points that remain in the location data. In some cases, location points removed because of density, standard deviation, or in the process of defining a representative point may not be projected. For example, only location points that are not part of the outlier subset of location data may be projected. In some cases, the aggregator <NUM> may be configured to project the vehicle-common or user-common location points onto a line perpendicular to the centerline of the path.

The aggregator <NUM> may be configured to group the location points projected onto the aggregation axis into one or more clusters. The aggregator <NUM> may use a clustering method such as DBSCAN or HDBSCAN to cluster the location data. The aggregator <NUM> may be configured to generate multiple sets or arrangements of clusters by varying cluster criteria. For example, the neighborhood distance and minimum number of points in a core point neighborhood may be varied by the aggregator <NUM> to obtain different set or arrangements of clusters. Changing the clustering criteria may result in different location points being grouped into different clusters. In some cases, the cluster criteria may be changed or selected based on input from an input device <NUM>, <NUM>. The aggregator <NUM> may be configured to perform clustering for each path segment on the subset of location points associated with each path segment.

The geographic data processor <NUM> may be implemented by the processor <NUM> based on instructions stored in the memory <NUM> of the server <NUM>. The geographic data processor <NUM> may be configured to determine a number of lanes present on a path segment. The number of lanes may range from a single lane to <NUM> or more lanes. Additionally or alternatively, the orientation of the lanes may be determined. For example, a direction of travel of vehicles, users, or mobile devices contributing to the location data may be used as a direction of travel for the lanes. The geographic data processor <NUM> may determine the number of lanes based on the number of clusters of location data for the path. For example, where the location data for a path is grouped into three clusters, the geographic data processor <NUM> may determine that the path has <NUM> lanes. The geographic data processor <NUM> may update a record of the path stored in the database <NUM> with the number of lanes. When multiple cluster sets or arrangements have been generated for a path, the geographic data processor <NUM> may use the cluster set or arrangement with the least amount of overlap. The geographic data processor <NUM> may be configured to determine a number of lanes for each path segment of a path. The number of lanes for the whole path may be determined based on the number of lanes for each segment. A "majority vote" of the number of lanes for the path segments may be used to determine the number of lanes for the whole path. For example, where there are five path segments and three segments have been determined to have two lanes, the geographic data processor <NUM> may determine that the whole path has two lanes.

<FIG> illustrates an example geographic database. The geographic database <NUM> may contain at least one road segment database record <NUM> (also referred to as "entity" or "entry") for each road segment in a particular geographic region. The geographic database <NUM> may also include a node database record <NUM> (or "entity" or "entry") for each node in a particular geographic region. The terms "nodes" and "segments" represent only one terminology for describing these physical geographic features, and other terminology for describing these features is intended to be encompassed within the scope of these concepts. The geographic database <NUM> may also include location fingerprint data for specific locations in a particular geographic region.

The geographic database <NUM> may include other kinds of data <NUM>. The other kinds of data <NUM> may represent other kinds of geographic features or anything else. The other kinds of data may include point of interest (POI) data. For example, the POI data may include POI records comprising a type (e.g., the type of POI, such as restaurant, hotel, city hall, police station, historical marker, ATM, golf course, etc.), location of the POI, a phone number, hours of operation, etc..

The geographic database <NUM> also includes indexes <NUM>. The indexes <NUM> may include various types of indexes that relate the different types of data to each other or that relate to other aspects of the data contained in the geographic database <NUM>. For example, the indexes <NUM> may relate the nodes in the node data records <NUM> with the end points of a road segment in the road segment data records <NUM>.

The geographic database <NUM> may also include other attributes of or about roads such as, for example, geographic coordinates, physical geographic features (e.g., lakes, rivers, railroads, municipalities, etc.) street names, address ranges, speed limits, turn restrictions at intersections, and/or other navigation related attributes (e.g., one or more of the road segments is part of a highway or toll way, the location of stop signs and/or stoplights along the road segments), as well as POIs, such as gasoline stations, hotels, restaurants, museums, stadiums, offices, automobile dealerships, auto repair shops, buildings, stores, parks, municipal facilities, other businesses, etc. The geographic database <NUM> may also contain one or more node data record(s) <NUM> which may be associated with attributes (e.g., about the intersections) such as, for example, geographic coordinates, street names, address ranges, speed limits, turn restrictions at intersections, and other navigation related attributes, as well as POIs such as, for example, gasoline stations, hotels, restaurants, museums, stadiums, offices, automobile dealerships, auto repair shops, buildings, stores, parks, etc. The geographic data <NUM> may additionally or alternatively include other data records such as, for example, POI data records, topographical data records, cartographic data records, routing data, and maneuver data. Other contents of the database <NUM> may include temperature, altitude or elevation, lighting, sound or noise level, humidity, atmospheric pressure, wind speed, the presence of magnetic fields, electromagnetic interference, or radio- and micro-waves, cell tower and wi-fi information, such as available cell tower and wi-fi access points, and attributes pertaining to specific approaches to a specific location.

The geographic database <NUM> may include historical traffic speed data for one or more road segments. The geographic database <NUM> may also include traffic attributes for one or more road segments. A traffic attribute may indicate that a road segment has a high probability of traffic congestion.

<FIG> shows some of the components of a road segment data record <NUM> contained in the geographic database <NUM> according to one embodiment. The road segment data record <NUM> may include a segment ID <NUM>(<NUM>) by which the data record can be identified in the geographic database <NUM>. Each road segment data record <NUM> may have associated information (such as "attributes", "fields", etc.) that describes features of the represented road segment. The road segment data record <NUM> may include data <NUM>(<NUM>) that indicate the restrictions, if any, on the direction of vehicular travel permitted on the represented road segment. The road segment data record <NUM> may include data <NUM>(<NUM>) that indicate a speed limit or speed category (i.e., the maximum permitted vehicular speed of travel) on the represented road segment. The road segment data record <NUM> may also include classification data <NUM>(<NUM>) indicating whether the represented road segment is part of a controlled access road (such as an expressway), a ramp to a controlled access road, a bridge, a tunnel, a toll road, a ferry, and so on. The road segment data record may include location fingerprint data, for example a set of sensor data for a particular location.

The geographic database <NUM> may include road segment data records <NUM> (or data entities) that describe features such as road objects <NUM>(<NUM>). The road objects <NUM>(<NUM>) may be stored according to location boundaries or vertices. The road objects <NUM>(<NUM>) may be stored as a field or record using a scale of values such as from <NUM> to <NUM> for type or size. The road objects <NUM>(<NUM>) may be stored using categories such as low, medium, or high. Additional schema may be used to describe the road objects <NUM>(<NUM>). The attribute data may be stored in relation to a link / segment <NUM>, a node <NUM>, a strand of links, a location fingerprint, an area, or a region. The geographic database <NUM> may store information or settings for display preferences. The geographic database <NUM> may be coupled to a display. The display may be configured to display the roadway network and data entities using different colors or schemes.

The road segment data record <NUM> may include a lane count <NUM>(<NUM>) for the road segment. The lane count <NUM>(<NUM>) may be a numerical value indicating the number of lanes of the road segment. The lane count <NUM>(<NUM>) may indicate the number of lanes for the whole width of the road segment or for one direction of travel along the road segment. In some cases, the road segment data record <NUM> includes a lane count <NUM>(<NUM>) for each direction of travel along the road segment.

The road segment data record <NUM> also includes data <NUM>(<NUM>) providing the geographic coordinates (e.g., the latitude and longitude) of the end points of the represented road segment. In one embodiment, the data <NUM>(<NUM>) are references to the node data records <NUM> that represent the nodes corresponding to the end points of the represented road segment.

The road segment data record <NUM> may also include or be associated with other data <NUM>(<NUM>) that refer to various other attributes of the represented road segment. The various attributes associated with a road segment may be included in a single road segment record or may be included in more than one type of record which cross-references to each other. For example, the road segment data record <NUM> may include data identifying what turn restrictions exist at each of the nodes which correspond to intersections at the ends of the road portion represented by the road segment, the name, or names by which the represented road segment is identified, the street address ranges along the represented road segment, and so on.

<FIG> also shows some of the components of a node data record <NUM> that may be contained in the geographic database <NUM>. Each of the node data records <NUM> may have associated information (such as "attributes", "fields", etc.) that allows identification of the road segment(s) that connect to it and/or its geographic position (e.g., its latitude and longitude coordinates). The node data records <NUM>(<NUM>) and <NUM>(<NUM>) include the latitude and longitude coordinates <NUM>(<NUM>)(<NUM>) and <NUM>(<NUM>)(<NUM>) for their node. The node data records <NUM>(<NUM>) and <NUM>(<NUM>) may also include other data <NUM>(<NUM>)(<NUM>) and <NUM>(<NUM>)(<NUM>) that refer to various other attributes of the nodes.

The geographic database <NUM> may be maintained by a content provider (e.g., a map developer). By way of example, the map developer may collect geographic data to generate and enhance the geographic database <NUM>. The map developer may obtain data from sources, such as businesses, municipalities, or respective geographic authorities. In addition, the map developer may employ field personnel to travel throughout a geographic region to observe features and/or record information about the roadway. Remote sensing, such as aerial or satellite photography, may be used.

The geographic database <NUM> and the data stored within the geographic database <NUM> may be licensed or delivered on-demand. Other navigational services or traffic server providers may access the location fingerprint data, traffic data and/or the lane line object data stored in the geographic database <NUM>.

The mobile device <NUM>, server <NUM>, or processors <NUM>, <NUM> may include a general processor, digital signal processor, an application specific integrated circuit (ASIC), field programmable gate array (FPGA), analog circuit, digital circuit, combinations thereof, or other now known or later developed processor. The mobile device <NUM>, server <NUM>, or processors <NUM>, <NUM> may be a single device or combinations of devices, such as associated with a network, distributed processing, or cloud computing.

The memory <NUM>, <NUM> may be a volatile memory or a non-volatile memory. The memory <NUM>, <NUM> may include one or more of a read only memory (ROM), random access memory (RAM), a flash memory, an electronic erasable program read only memory (EEPROM), or other type of memory. The memory <NUM>, <NUM> may be removable from the mobile device <NUM> or server <NUM>, such as a secure digital (SD) memory card.

The communication interface <NUM>, <NUM> may include any operable connection. An operable connection may be one in which signals, physical communications, and/or logical communications may be sent and/or received. An operable connection may include a physical interface, an electrical interface, and/or a data interface. The communication interface <NUM>, <NUM> provides for wireless and/or wired communications in any now known or later developed format.

The databases <NUM> may include geographic data used for traffic and/or navigation-related applications. The geographic data may include data representing a road network or system including road segment data and node data. The road segment data represent roads, and the node data represent the ends or intersections of the roads. The road segment data and the node data indicate the location of the roads and intersections as well as various attributes of the roads and intersections. Other formats than road segments and nodes may be used for the geographic data. The geographic data may include structured cartographic data or pedestrian routes.

The databases may also include other attributes of or about the roads such as, for example, geographic coordinates, street names, address ranges, speed limits, turn restrictions at intersections, and/or other navigation related attributes (e.g., one or more of the road segments is part of a highway or toll way, the location of stop signs and/or stoplights along the road segments), as well as points of interest (POIs), such as gasoline stations, hotels, restaurants, museums, stadiums, offices, automobile dealerships, auto repair shops, buildings, stores, parks, etc. The databases may also contain one or more node data record(s) which may be associated with attributes (e.g., about the intersections) such as, for example, geographic coordinates, street names, address ranges, speed limits, turn restrictions at intersections, and other navigation related attributes, as well as POIs such as, for example, gasoline stations, hotels, restaurants, museums, stadiums, offices, automobile dealerships, auto repair shops, buildings, stores, parks, etc. The geographic data may additionally or alternatively include other data records such as, for example, POI data records, topographical data records, cartographic data records, routing data, and maneuver data.

The databases may include historical traffic speed data for one or more road segments. The databases may also include traffic attributes for one or more road segments. A traffic attribute may indicate that a road segment has a high probability of traffic congestion.

The input device <NUM>, <NUM> may be one or more buttons, keypad, keyboard, mouse, stylus pen, trackball, rocker switch, touch pad, voice recognition circuit, or other device or component for inputting data to the mobile device <NUM> or server <NUM>. The input device <NUM>, <NUM> and display <NUM> may be combined as a touch screen, which may be capacitive or resistive. The display <NUM> may be a liquid crystal display (LCD) panel, light emitting diode (LED) screen, thin film transistor screen, or another type of display. The output interface of the display <NUM> may also include audio capabilities, or speakers. In an embodiment, the input device <NUM>, <NUM> may involve a device having velocity detecting abilities.

The positioning circuitry <NUM> or a position sensor may include suitable sensing devices that measure the traveling distance, speed, direction, and so on, of the vehicle <NUM> or mobile device <NUM>. The positioning system may also include a receiver and correlation chip to obtain a GPS signal. Alternatively or additionally, the one or more detectors or sensors may include an accelerometer and/or a magnetic sensor built or embedded into or within the interior of the vehicle <NUM> or mobile device <NUM>. The accelerometer is operable to detect, recognize, or measure the rate of change of translational and/or rotational movement of the vehicle <NUM> or mobile device <NUM>. The magnetic sensor, or a compass, is configured to generate data indicative of a heading of the vehicle <NUM> or mobile device <NUM>. Data from the accelerometer and the magnetic sensor may indicate orientation of the vehicle <NUM> or mobile device <NUM>. The vehicle <NUM> or mobile device <NUM> receive location data from the positioning system. The location data indicates the location of the vehicle <NUM> or mobile device <NUM>.

The positioning circuitry <NUM> or a position sensor may include a Global Positioning System (GPS), Global Navigation Satellite System (GLONASS), or a cellular or similar position sensor for providing location data. The positioning system may utilize GPS-type technology, a dead reckoning-type system, cellular location, or combinations of these or other systems. The positioning circuitry <NUM> or a position sensor may include suitable sensing devices that measure the traveling distance, speed, direction, and so on, of the vehicle <NUM> or mobile device <NUM>. The positioning system may also include a receiver and correlation chip to obtain a GPS signal. The vehicle <NUM> or mobile device <NUM> receives location data from the positioning system. The location data indicates the location of the vehicle <NUM> or mobile device <NUM>.

The positioning circuitry <NUM> or a position sensor may also include gyroscopes, accelerometers, magnetometers, or any other device for tracking or determining movement of a mobile device. The gyroscope is operable to detect, recognize, or measure the current orientation, or changes in orientation, of a mobile device. Gyroscope orientation change detection may operate as a measure of yaw, pitch, or roll of the mobile device.

In accordance with various embodiments of the present disclosure, the methods described herein are implemented by software programs executable by a computer system. Alternatively, virtual computer system processing can be constructed to implement one or more of the methods or functionalities as described herein.

As used in this application, the term 'circuitry' or 'circuit' refers to all of the following: (a)hardware-only circuit implementations (such as implementations in only analog and/or digital circuitry) and (b) to combinations of circuits and software (and/or firmware), such as (as applicable): (i) to a combination of processor(s) or (ii) to portions of processor(s)/software (including digital signal processor(s)), software, and memory(ies) that work together to cause an apparatus, such as a mobile phone or server, to perform various functions) and (c) to circuits, such as a microprocessor(s) or a portion of a microprocessor(s), that require software or firmware for operation, even if the software or firmware is not physically present.

This definition of 'circuitry' applies to all uses of this term in this application, including in any claims.

Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and anyone or more processors of any kind of digital computer. Generally, a processor receives instructions and data from a read only memory or a random-access memory or both. Generally, a computer also includes, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio player, a Global Positioning System (GPS) receiver, to name just a few. Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media, and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. In an embodiment, a vehicle may be considered a mobile device, or the mobile device may be integrated into a vehicle.

The term "computer-readable medium" includes a single medium or multiple media, such as a centralized or distributed database, and/or associated caches and servers that store one or more sets of instructions. The term "computer-readable medium" shall also include any medium that is capable of storing, encoding, or carrying a set of instructions for execution by a processor or that cause a computer system to perform any one or more of the methods or operations disclosed herein.

In a particular non-limiting, exemplary embodiment, the computer-readable medium can include a solid-state memory such as a memory card or other package that houses one or more non-volatile read-only memories. Further, the computer-readable medium can be a random-access memory or other volatile re-writable memory. Additionally, the computer-readable medium can include a magneto-optical or optical medium, such as a disk or tapes or other storage device to capture carrier wave signals such as a signal communicated over a transmission medium. A digital file attachment to an e-mail or other self-contained information archive or set of archives may be considered a distribution medium that is a tangible storage medium. Accordingly, the disclosure is considered to include any one or more of a computer-readable medium or a distribution medium and other equivalents and successor media, in which data or instructions may be stored. These examples may be collectively referred to as a non-transitory computer readable medium.

While this specification contains many specifics, these should not be construed as limitations on the scope of the invention or of what may be claimed, but rather as descriptions of features specific to particular embodiments of the invention. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a sub-combination or variation of a sub-combination.

Similarly, while operations are depicted in the drawings and described herein in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments.

One or more embodiments of the disclosure may be referred to herein, individually and/or collectively, by the term "invention" merely for convenience and without intending to voluntarily limit the scope of this application to any particular invention or inventive concept. Moreover, although specific embodiments have been illustrated and described herein, it should be appreciated that any subsequent arrangement designed to achieve the same or similar purpose may be substituted for the specific embodiments shown. This disclosure is intended to cover any and all subsequent adaptations or variations of various embodiments. Combinations of the above embodiments, and other embodiments not specifically described herein, are apparent to those of skill in the art upon reviewing the description.

The Abstract of the Disclosure is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. In addition, in the foregoing Detailed Description, various features may be grouped together or described in a single embodiment for the purpose of streamlining the disclosure. This disclosure is not to be interpreted as reflecting an intention that the claimed embodiments require more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive subject matter may be directed to less than all of the features of any of the disclosed embodiments. The invention is defined by the set of appended claims.

Claim 1:
A computer-implemented method for assigning a number of vehicle lanes on a vehicle path (<NUM>), the method comprising:
receiving location data (<NUM>) including a plurality of location points from one or more vehicles, wherein the plurality of location points corresponds to a plurality of positions along the vehicle path;
projecting each location point of the plurality of location points, along a projection vector that follows the course of the path, on to an aggregation axis (<NUM>) perpendicular to a centerline (<NUM>) of the vehicle path;
for each of a plurality of clustering criteria, grouping the plurality of location points as projected (<NUM>, <NUM>) onto the aggregation axis into a respective set of one or more clusters (<NUM>) according to the respective clustering criterion and determining a degree of overlap between the one or more clusters of the respective set;
selecting a grouping according to a clustering criterion of the plurality of clustering criteria which resulted in a lowest degree of overlap between the one or more clusters; and
determining the number of vehicle lanes of the vehicle path based on a count of the one or more clusters of the selected grouping.