Clustering observations of objects along roads for navigation-related operations

In one embodiment, a cluster application generates navigation-related data based on observations received from vehicles. In operation, the cluster application computes an oriented distance between two observed object positions based on a heading, where each observed object position is associated with a different one of two observations. The cluster application then generates a cluster that includes the two observations based on the oriented distance. Subsequently, the cluster application computes an object position that is associated with the cluster based on the two observations. The cluster application transmits the object position and at least one characteristic associated with the observations to a update application that generates an update to a road database. Because the cluster application computes the object position based on multiple observations that are likely of a single object, the object position associated with the cluster may be more reliable than the observed object positions.

BACKGROUND

Field of the Various Embodiments

The various embodiments relate generally to navigation subsystems and, more specifically, to clustering observations of objects along roads for navigation-related operations.

Description of the Related Art

Many vehicles include navigation applications that perform navigation-related activities based on satellite navigation devices (e.g., global positioning system devices) and road databases that specify underlying, physical road networks and associated navigation-related data. For example, a road database could include speed limits at different points along each road to enable a navigation subsystem to estimate travel times, etc. However, over time, the navigation-related data may change. For instance, the speed limit associated with a portion of a road may be reduced. Accordingly, in an effort to provide road databases that are up-to-date and accurate, some providers of road databases generate updates that specify changes to navigation-related data.

In one approach to generating updates, providers of road databases rely on real-time observations received from numerous vehicles traveling along roads. Typically, each observation includes one or more characteristics associated with an observed object based on data collected by various sensors. Examples of characteristics associated with an observed sign include an estimated position of the vehicle at the time of the observation, an estimated speed of the vehicle at the time of the observation, and an estimated type of the observed object, to name a few.

One limitation of observations is that the characteristics are dependent on the accuracy of sensors, driving conditions, road conditions, and so forth. Consequently, the characteristics are prone to errors. For example, the estimated position of the vehicle could be inaccurate by as much as 400 meters when an vehicle is moving relatively fast. In another example, a camera included in an vehicle could perform pattern recognition operations on an image to identify a speed limit sign specifying 30 miles per hour. However, if the view of the camera is obscured by another vehicle or the sun is shining brightly, then the camera could incorrectly identify the speed limit sign as specifying 80 miles per hour.

In operation, because observations are not necessarily reliable, the providers of the road databases are oftentimes discouraged from generating updates based on real-time observations. Instead, the providers typically resort to generating updates based on more time consuming data collection operations that produce acceptably reliable data. As a result, the length of time between updates to road databases may be undesirably long. For example, a provider of a road database could provide an update every 6 months. Between updates, the quality of the navigation-related data included in road databases may be degraded, and the associated navigation applications may provide inaccurate navigation information.

As the foregoing illustrates, more effective techniques for generating navigation-related data would be useful.

SUMMARY

One embodiment sets forth a method for generating navigation-related data, The method includes computing a first oriented distance between a first observed object position and a second observed object position based on a first heading, where the first observed object position and the first heading are associated with a first observation received from a first vehicle, and the second observed object position is associated with a second observation received from a second vehicle; generating, based on the first oriented distance, a first cluster that includes the first observation and the second observation; computing an object position associated with the first cluster based on at least the first observation and the second observation; and transmitting the object position and at least one characteristic associated with the first observation to an update application, where the update application generates an update to a road database.

Further embodiments provide, among other things, a system and a computer-readable medium configured to implement the method set forth above.

At least one advantage of the disclosed techniques is that because the cluster is generated based on multiple observations of an object, the characteristics associated with the cluster are typically more accurate than the characteristics associated with each of the individual observations. Further, observations that are likely to be inaccurate are not included in the clusters and, consequently, the clusters include less noise that the observations. As a result, the update application is able to generate acceptably accurate real-time updates to road databases relative to conventional approaches, which are typically based on potentially inaccurate observations and/or which commonly require time consuming data operations that preclude generating updates in real-time.

DETAILED DESCRIPTION

In the following description, numerous specific details are set forth to provide a more thorough understanding of the various embodiments. However, it will be apparent to one of skill in the art that various embodiments may be practiced without one or more of these specific details.

Road Database Update System

FIG. 1illustrates a road database update system100configured to implement one or more aspects of the various embodiments. As shown, the road database update system100includes, without limitation, vehicles120, observation data130, and a compute instance110. In alternate embodiments, the road database update system100may include any number (including zero) of vehicles120and compute instances110. For explanatory purposes, multiple instances of like objects are denoted with reference numbers identifying the object and parenthetical numbers identifying the instance where needed.

Although not shown inFIG. 1, each of the vehicles120may include a navigation application that enables a user to perform navigation-related operations (e.g., viewing maps, generating and viewing directions and travel times, etc.) based on an associated road database and sensor data. The road database specifies underlying, physical road networks and associated navigation-related data. The sensor data provides feedback involving the vehicle120and the surrounding environment that enables the driver to efficiently and safely operate the vehicle120. For instance, the navigation application that is included in the vehicle120(1) enables the driver of the vehicle120(1) to efficiently navigate the vehicle120(1) via a road database and global positioning system (GPS) data received from a satellite navigation device associated with the vehicle120(1).

For each vehicle120, the navigation application and the associated road database are typically stored in memory included in the vehicle120. In alternate embodiments, each navigation application may access any road database in any technically feasible fashion. For instance, a navigation application included in the vehicle120(2) may access a road database via the Internet. However, over time, navigation-related data may change. For instance the speed limit associated with a portion of a road may be reduced. As a result, the road databases may become inaccurate, and associated navigation applications may provide inaccurate navigation information to users. In an effort to provide road databases that are up-to-date and accurate, some providers of road databases generate conventional updates to the road databases that specify changes to navigation-related data based on the sensor data.

In general, each of the vehicles120may include any number and type of sensors (not shown) that generate sensor data. For example, the sensors may include a satellite navigation device, a camera, an odometer, and wheels sensors, to name a few. The satellite navigation device could provide GPS data that specifies the vehicle position and, based on multiple vehicle positions over time, an overall vehicle heading. The camera could perform pattern recognition operations on images received as the automotive170travels along a road in an attempt to identify road signs. The odometer could provide a current speed of the vehicle120. The wheel sensors could provide a current vehicle heading.

As the vehicles120operate, in addition to providing the sensor data to the associated navigation application, the vehicles120may be configured to transmit sensor data to any number of applications as the observation data130. As shown, the observation data130includes, without limitation, any number of observations140. Each of the observations140specifies, without limitation, any number of characteristics associated with an observed object based on the sensor data and a timestamp that specifies the point in time at which the observation140was made.

Examples of characteristics associated with an observed sign include an estimated position of the vehicle120, an estimated heading of the vehicle120, and an estimated type of the observed object, to name a few. For example, the observation140(1) could specify that, traveling north at a speed of 90 miles per hour, the vehicle120identified a speed limit sign specifying 70 miles per hour. As a general matter, the vehicles120generate and transmit the observations140as the sensor data is generated (i.e., in “real-time”).

In one conventional approach to providing accurate navigation-related data, a conventional update application receives the observation data130and generates a conventional update based on all of the observations140included in the observation data130. However, one limitation of the observations140is that the specified characteristics are dependent on the accuracy of sensors, driving conditions, and road conditions, and so forth. Consequently, the characteristics are prone to errors. For example, the estimated position of the vehicle120could be inaccurate by as much as 400 meters when the vehicle120is moving relatively fast. In another example, a camera included in the vehicle120(1) could perform pattern recognition operations on an image to identify a speed limit sign specifying 30 miles per hour. However, if the view of the camera is obscured by the vehicle120(2) or the sun is shining brightly, then the camera could incorrectly identify the speed limit sign as specifying 80 miles per hour.

Because the observations140are not necessarily reliable, the providers of road databases are oftentimes discouraged from generating conventional updates based on the observations140. Instead, the providers typically resort to generating conventional updates based on more time consuming data collection operations that produce acceptably reliable data. As a result, the length of time between conventional updates to road databases may be undesirably long. For example, a provider of a road database could provide a new conventional update every 6 months. Between the conventional updates, the quality of the navigation-related data included in the road databases may be degraded, and associated navigation applications may provide inaccurate navigation information.

Efficiency Generating Accurate Updates to Road Databases

To provide acceptably accurate navigation-related data via updates190without unacceptably increasing the time required to generate the updates190, the road database update system100includes a cluster application150. In general, the cluster application150generates cluster data160based on the observation data130. As shown, the cluster data160includes, without limitation, clusters170and confidence levels172. Each of the clusters170specifies one or more characteristics associated with an observed object based on one or more of the observations140that are likely of the observed object. Further, in various embodiments, each of the observations140is included in at most one of the clusters170. Consequently, in such embodiments, a total number of the clusters170is no greater than the total number of the observations140. Each of the confidence levels172estimates an accuracy of the characteristics specified in an associated cluster170. Further, in various embodiments, a total number of the confidence levels172equals the total number of the clusters170.

In operation, the cluster application150evaluates the observation data130to identify sets of the observations140that are likely of one observed object. As part of evaluating the observation data130, the cluster application150discards any observations140that are inconsistent with physical properties of the vehicles120or with respect to a context of the observation data130. The cluster application150then performs oriented density-based clustering operations to generate the clusters170. In general, and as described in detail in conjunction withFIG. 2, the cluster application150identifies sets of “similar” observations140, where the observations130included in each of the sets specify similar characteristics (e.g., sign type, etc.). For each set of similar observations140, the cluster application performs cluster operations on the observations130based on oriented distances to generate the clusters170. Each oriented distance reflects an estimated travel distance between observed object positions, where the travel distance is consistent with an estimated heading of a road.

In this fashion, the cluster application150ensures that each of the clusters170specifies the observations140that are likely of a single observed object. The cluster application150then determines one or more characteristics specified in the cluster170based on the associated observations140. In particular, the cluster application150computes an object position based on fitting the associated observed object positions to a Gaussian distribution. In alternate embodiments, the cluster application150may generate the clusters170in any technically feasible fashion that reflects that the observations140are received from the vehicles120as the vehicles120travel along roads.

Subsequently, and for each of the clusters170, the cluster application150computes the associated confidence level172based on an amount, frequency, and consistency of the observations140included in the cluster170. Notably, as the number of observations140of an observed object increases, the confidence level172of the cluster170typically increases. In alternate embodiments, the cluster application150may compute the confidence levels172in any technically feasible fashion and based on any amount and type of data. In other alternate embodiments, the cluster application150may not generate the confidence levels172. After the cluster application150generates the cluster data160, the cluster application150transmits the cluster data160to an update application180.

The update application180selects one or more of the clusters170based on the confidence levels172and generates an update170based on the selected clusters170. Because the cluster application150generates the update190based on the cluster data160instead of directly on the observations140, the update application180may generate the update190in real-time while ensuring that the update190provides reliable navigation-related information. Finally, the update application180transmits the update190to navigation applications included in the vehicles120. Notably, the cluster application150and the update application180may be configured to generate and transmit the updates190much more frequently than conventional update applications. Consequently, unlike navigation applications that receive conventional updates, the navigation applications included in the vehicles120are able to perform navigation-related operations based on accurate navigation-related information at any given time.

As shown, the cluster application150and the update application180reside in a memory116that is included in the compute instance110and executes on a processor112that is included in the compute instance110. In alternate embodiments, the road database update system100may include any number of compute instances110, any number of memories116, and any number of processors112that are implemented in any technically feasible fashion. Further, the cluster application150and the update application180may reside in different memories116, execute on different processors112, and/or be associated with different compute instances110.

In various embodiments, the compute instance110may be implemented as a stand-alone chip or as part of a more comprehensive solution that is implemented as an application-specific integrated circuit (ASIC), a system-on-a-chip (SoC), and so forth. Further, the compute instance110, the memory116, and the processor112may be implemented via any number of physical resources located in any number of physical positions. For example, the cluster application150could be included in the compute instance110(1) that is implemented in a laptop, and the update application180could be included in a compute instance110(2) that is implemented in a cloud computing environment or a distributed computing environment.

The processor112may be any instruction execution system, apparatus, or device capable of executing instructions. For example, the processor112could comprise a central processing unit (CPU), a graphics processing unit (GPU), a controller, a microcontroller, a state machine, or any combination thereof. The memory116stores content, such as software applications and data, for use by the processor112. The memory116may be one or more of a readily available memory, such as random access memory (RAM), read only memory (ROM), floppy disk, hard disk, or any other form of digital storage, local or remote.

In some embodiments, a storage (not shown) may supplement or replace the memory116. The storage may include any number and type of external memories that are accessible to the processor112. For example, and without limitation, the storage may include a Secure Digital Card, an external Flash memory, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, cloud storage, a Blu-ray Disc, other tangible storage media, or any suitable combination of the foregoing.

It will be appreciated that the road database update system100shown herein is illustrative and that variations and modifications are possible. The number of compute instances110, the number of cluster applications150, the number of update applications180, the number of road databases, the number of vehicles120, and the connection topology between the various units in road database update system100may be modified as desired. Each of the cluster applications150may be implemented in a stand-alone fashion or integrated in any other application (e.g., the update application180) or device in any technically feasible fashion. Further, the functionality included in the cluster application150and the update application180may be divided across any number of applications that are stored and executed via any number of devices that are located in any number of physical positions. For example, the update application180could be included in the navigation application of the vehicle120, and the cluster application150could transmit the cluster data160directly to the navigation application.

Generating Clusters Based on Oriented Distances

FIG. 2is a more detailed illustration of the cluster application150ofFIG. 1, according to various embodiments. As shown, the cluster application150includes, without limitation, a filtering engine210, a sectoring engine220, a clustering engine230, a cluster positioning engine240, a merging engine250, and a confidence engine260. For explanatory purposes only, the cluster application150is configured to generate the clusters170that correspond to road signs, where each road sign lies along a road. In alternate embodiments, the cluster application150may be configured to generate the clusters170that correspond to any type of observed object.

In operation, the cluster application150receives the observation data130and generates the cluster data160. The observation data130includes, without limitation, any number of observations140, where each of the observations140includes, without limitation, a timestamp202, an vehicle position210, a heading212, a speed214, a sign type216, and a side218. As referred to herein, the timestamp202, the vehicle position210, the heading212, the speed214, the sign type216, and the side218are referred to herein as “characteristics of the observation(s)140.”

In general, each of the characteristics of the observations140may be specified in any technically feasible fashion based on any protocol and format. In alternate embodiments, the observations140may omit one or more of the characteristics of the observations140, and the cluster application150may derive the omitted characteristics in any technically feasible fashion. For example, the observations140could omit the timestamp202, and the cluster application150could compute each of the timestamps220based on the time at which the cluster application150receives the associated observation140. In another example, the observations140could omit the headings212, and the cluster application150could compute each of the headings212based on any number of the observations140previously received from the associated vehicle120.

The timestamp202specifies the time at which the associated vehicle120generated the observation140. The vehicle position210specifies the position of the vehicle120at the time specified by the timestamp202. For example, the vehicle position210could specify an absolute position of the vehicle120in GPS coordinates. The heading212specifies a direction in which the vehicle120is heading at the time specified by the timestamp202. For example, the heading212could be expressed in degrees counterclockwise form a north direction. The speed214specifies the velocity of the vehicle120along the heading212at the time specified by the timestamp202. For example, the speed214could be 90 miles per hour.

The sign type216specifies one or more characteristics that are associated with the observed object. For example, the sign type216could be “speed limit of 70 miles per hour.” For explanatory purposes, as referred to herein, two signs that are mounted together are referred to herein as a single road sign that corresponds to a single observed object. For example, a modification sign that specifies “above sign applies to trucks” could be mounted directly below a primary sign that specifies “speed limit of 30 miles per hour.” The modified sign and the primary sign would, together, be considered a single observed object and the associated sign type216would be “speed limit of 30 miles per hour for trucks.”

As persons skilled in the art will recognize, oftentimes the sensors execute a variety of operations to produce estimated data that is relatively small in size and, consequently, easy to communicate in real-time. Accordingly, the sign type216may include any amount and type of information consistent with the sensors included in the vehicle120. For instance, in some embodiments, a camera included in the vehicle120performs pattern image recognition operations on an image to generate the sign type216. Notably, the sign type216requires significantly less of the memory116to store and significantly less bandwidth to transmit than an image. The side218specifies a side of the associated vehicle120associated with the observation140. For example, if a camera detected the a road sign along the left side of the vehicle120, then the side218would be “left.” In another example, if a camera detected a road sign above the vehicle120, then the side218would be “above.”

The filtering engine210receives the observation data130and performs any number of filtering operations that identify observations140that are likely to be inaccurate. The filtering engine210then removes the identified observations140. The filtering engine210may identify the observations140that are likely to be inaccurate in any technically feasible fashion based on any amount and type of data. In some embodiments, the filtering engine210may include algorithms that identify and remove any observations140that are inconsistent with the physical properties of the vehicles120. For example, the filtering engine210could identify and remove any of the observations140that specify a value of greater than 120 miles per hour for the speed214.

In other or the same embodiments, the filtering engine210identifies and removes any of the observations140that are inconsistent with respect to the observation data130. For instance, suppose that fifty of the observations140(1-50) include approximately the same vehicle positions210, headings212, and sides218; the observations140(1-49) specify a sign type “speed limit of 10 miles per hour;” and the observation140(50) specifies a sign type of “speed limit of 70 miles per hour.” In some embodiments, the filtering engine210would identify the observation140(50) as inconsistent, and remove the observation140(50) from the observation data130.

For each of the remaining observations140included in the observation data130, the sectoring engine220generates a sector (not shown inFIG. 2) based on a mathematical model that relates an observed sign position to the vehicle position210, the heading212, the speed214, and the side218. As is well-known, a sector is a portion of a disk enclosed by two radii and an arc. In particular, the camera lies approximately at the center of the disk, the direction of the sector is based on the heading212and the side218, and the central angle of the sector is based on the speed214. Notably, as the speed214increases, the depth of view of the camera decreases and, consequently, the central angle of the sector decreases. The sectoring engine220then determines the observed sign position based on the sector. In alternate embodiments, the mathematical model may include any number and type of data. For example, the mathematical model could include additional road parameters, such as functional road class, number of lanes, etc.

The clustering engine230receives the observed sign positions, determines sets of “similar” observations140, and performs density-based clustering on each set of similar observations140to generate the clusters170. As shown, each of the clusters170includes, without limitation, the heading212, the sign type216, the side218, an observation list282, an observation count284, a time interval286, and a sign position280. To determine each set of similar observations, the clustering engine230identifies the observations140that share the same sign type216and the same side218, and have headings212that deviate from one another by at most a maximum heading deviation. The clustering engine230may determine the maximum heading deviation in any technically feasible fashion. For example, the clustering engine230could receive the maximum heading deviation via a graphical user interface (GUI).

As persons skilled in the art will recognize, “density-based clustering” refers to techniques that map data based on an evaluation criterion, form clusters of the data included in regions of relatively high density, and identify data in regions of relatively low density as outliers (e.g., noise, etc.). In operation, because each of the observations140is typically reported by the associated vehicle120traveling along a road that coincides with the associated heading212, the clustering engine230performs “oriented” density-based clustering based on the observed sign positions and oriented distances. As referred to herein, an “oriented distance” specifies a distance between observed sign positions in which distances that are along the heading212are weighted less heavily than distances that are perpendicular to the heading212.

For example, suppose that the heading212is north, the observed sign position associated with the observation140(1) is 500 feet north of the observed sign position associated with the observation140(2), and the observed sign position associated with the observation140(3) is 200 feet west of the observed sign position associated with the observation140(2). In such a scenario, the distance between the observation140(1) and the observation140(2) is along the heading212, while the distance between the observation140(1) and the observation140(3) is perpendicular to the heading212. Consequently, the oriented distance between observation140(1) and140(2) is smaller than the oriented distance between the observation140(1) and the observation140(3).

The clustering engine230may implement any type of density-based clustering operations to generate the clusters170. For example, in some embodiments, the clustering engine230performs density-based clustering operations that are modified versions of operations performed as part of the well-known density-based spatial clustering of applications with noise (DBSCAN) algorithm. In alternate embodiments, the clustering engine230may implement any number and type of clustering operations based on any number and type of constraints to generate the clusters170. Further, the clustering engine230may perform any amount of additional operations on the clusters170prior to, during, or subsequent to performing the density-based clustering operations. For instance, the clustering engine230may discard any clusters170that do not include a minimum number of the observations140.

As a result of the oriented density-based clustering, each of the clusters170may be characterized by a rectangular shape that is oriented along a road and defines the observations130that are likely associated with a single road sign. For each of the clusters170, the clustering engine230sets the observation list282to specify the observations140that are included in the region of relatively high density that defines the cluster170. In a complementary fashion, the clustering engine230sets the observation count284to specify the total number of observations140included in the observation list282. The clustering engine230then sets the sign type216and the side218of the cluster170equal to, respectively, the shared sign type216and the shared side218of the observations140included in the observation list282. The clustering engine230may set the heading212in any technically feasible fashion. For example, the clustering engine230could set the heading212to the average of the headings212of the observations140included in the observation list282.

Finally, for each of the clusters170, the clustering engine230sets the time interval286to reflect the earliest timestamp202and the latest timestamp202specified in the observations140included in the observation list282. In this fashion, the clusters170enable the confidence engine260and other applications (e.g., the update application180) to identify any of the clusters170that are associated with out-of-date observations140. For example, if a road sign is replaced at a replacement time, then the time interval286specified in a corresponding cluster170would specify a latest time that is earlier than the replacement time.

For each of the clusters170, the cluster positioning engine240computes the sign position280based on the observed sign positions of the observations140included in the observation list282. More specifically, the cluster positioning engine240fits the observed sign positions into a Gaussian distribution and then sets the sign position280to the median of the Gaussian distribution. In alternate embodiments, the cluster positioning engine240may compute the sign positions280in any technically feasible fashion.

To properly handle various types of unusual cases, the merging engine250could identify any of the clusters170that are likely associated with a single physical or logical sign and merge the identified cluster(s)170into a single target cluster170. As referred to herein, a “logical sign” may comprise any number of physical signs that are considered a single sign for the purposes of navigating a road. For example, a bi-sided road sign is a single logical sign that comprises two physical signs. More precisely, a “bi-sided” road sign corresponds to two physical signs that specify the same information, where the physical signs are observed on different sides of the vehicles170and are oriented in approximately the same direction along the road. If the merging engine250identifies two of the clusters170that are associated with similar headings212, sign types216, and sign positions280, then the merging engine250may attempt to form a target cluster170.

As part of forming the target cluster170, the merging engine250combines the observations lists282of the identified clusters170, sums the observation counts284of the identified clusters170, and sets the side218to bi-sided. The merging engine250may set the sign position280included in the target cluster170in any technically feasible fashion. For instance, in some embodiments, the merging engine250may set the sign position280included in the target cluster170to the average of the sign positions280included in the identified clusters170. In the same or other embodiments, the merging engine250may set a “merged cluster list” that is associated with target cluster170to point to the two identified clusters170. In other embodiments, the merging engine250may discard the two identified clusters170.

Finally, the confidence engine260computes the confidence levels172based on the observation counts284, the sides218, and the consistency of the observations140specified in the observation lists282. More specifically, in some embodiments, the confidence engine260may compute the confidence level172(i) associated with the cluster170(i) based on any of the following criteria:the sum of the observation counts284included in all the clusters270the observation count284included in the cluster270(i)the last time included in the time interval286(i) compared to the last time specified in the time intervals286included in nearby clusters270the total number of the clusters270that include the sign type216equal to bi-sidedthe total number of the observations140specified in the observation list282(i) that include the sign type216equal to bi-sided

In general, as the observation count282(i) increases, the confidence level172(i) increases. Similarly, as the ratio of the observation count282(i) to the sum of the observation counts284included in all the clusters270increases, the confidence level172(i) increases. By contrast, as the difference between a current time and the last time specified in the time interval286(i) increases, the confidence level172(i) decreases. If the sign type216of the cluster170(i) equals bi-sided, then as the number of observations140specified in the observation list282(i) that include the sign type216equal to bi-sided increases, the confidence level172(i) increases.

Further, if the cluster270(i) is the result of merging operations and the sign type216of the cluster270(i) is equal to bi-sided, then the confidence engine260adjusts the confidence level172(i) based on the properties of the associated merged clusters270. In particular, if the sign type216specified in one of the merged clusters270is equal to left and the sign type216specified in the other merged cluster270is equal to right, then the confidence engine260reduces the confidence level172(i). By contrast, if one of the sign types216specified in the merged clusters270is equal to bi-sided, then the confidence engine260sets the confidence level172(i) equal to the confidence level172of the bi-sided merged cluster270.

Note that the techniques described herein are illustrative rather than restrictive, and may be altered without departing from the broader spirit and scope of the contemplated embodiments. Many modifications and variations on the functionality provided by the cluster application150will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. For instance, in some embodiments, the cluster application150may not compute the confidence levels172. In other embodiments, the cluster application150may compute the confidence levels172and then discard any of the clusters170that are associated with the confidence level172that is less than an predetermined minimum confidence.

FIG. 3illustrates examples of the clusters170ofFIG. 2, according to various embodiments. As shown, the three speed limit signs330(1),330(2), and330(3) lie along a right half of a divided road and are visible to the vehicles120traveling in a north east direction along the road. Each of the observations140included in the observation data130is depicted as a small, unfilled circle and the clusters170(1) and170(2) are depicted as unfilled rectangles that surround the observations130included in the associated observation lists282(1) and282(2).

As shown, the cluster170(1) corresponds to a speed limit sign330(1) that is located on the right side of the road and specifies 50 miles per hour. Accordingly, the sign type216(1) and the side218(1) included in the cluster170(1) are, respectively, “speed limit of 50 miles per hour” and “right.” The cluster170(1) is depicted as an unfilled rectangle that is oriented along the road. The observation list282(1) included in the cluster170(1) specifies the observations140that lie within the unfilled rectangle that depicts the cluster170(1). As part of generating the cluster170(1), for each of the observations140, the sectoring engine220generates a sector320. The sector320(1) associated with the observation140(1) that is included in the observation list282(1) is depicted as dotted region, and the speed limit sign330(1) lies within the dotted region.

By contrast, the cluster170(2) corresponds to two speed limit sign330(2) and330(3) that are on, respectively, a left median of the road and the right side of the road. The speed limit signs220(2) and330(3) both specify 80 miles per hour. Accordingly, the sign type216(2) and the side218(2) included in the cluster170(2) are, respectively, “speed limit of 80 miles per hour” and “bi-sided.” Although not shown, the merging engine250generates the cluster170(2) based on the cluster170(3) that corresponds to the speed limit sign330(2) and the cluster170(4) that corresponds to the speed limit sign330(3). The sign type216(3) and the side218(3) included in the cluster170(3) are, respectively, “speed limit of 80 miles per hour” and “left.” The sign type216(4) and the side218(4) included in the cluster170(4) are, respectively, “speed limit of 80 miles per hour” and “right.”

As part of generating the cluster170(2), the merging engine250performs a union operation between the observation list282(3) included in the cluster170(3) and the observation list282(4) included in the cluster170(4) to generate the observation list282(2) included in the cluster170(2). The observation list282(2) specifies the observations140that lie within the unfilled rectangle that depicts the cluster170(2). As part of generating the cluster170(2), for each of the observations140, the sectoring engine220generates a different sector320. For explanatory purposes only, a sector union340of the sectors320associated with the observations140included in the observation list282(2) is depicted as a dotted semi-ellipsoidal region. Both the speed limit sign330(2) and the speed limit sign330(3) lie within the dotted semi-ellipsoidal region. As persons skilled in the art will recognize, the union of the sectors230associated with the observations140included in the observation list282(3) comprise a left half of the dotted semi-ellipsoidal region. By contrast, the union of the sectors230associated with the observations140included in the observation list282(4) comprise a right half of the dotted semi-ellipsoidal region.

FIG. 4is a flow diagram of method steps for generating navigation-related data based on multiple observations, according to various embodiments. Although the method steps are described in conjunction with the systems ofFIGS. 1-3, persons skilled in the art will understand that any system configured to implement the method steps, in any order, falls within the scope of the contemplated embodiments.

As shown, a method400begins at step404, where the cluster application150receives the observation data130. The observation data130includes any number of the observations140received from any number of the vehicles120. The cluster application150may receive the observation data130in any technically feasible fashion. At step406, the filtering engine210identifies and removes inconsistent observations140that are included in the observation data130. For instance, in some embodiments, the filtering engine210could identify and remove any of the observations140that specify a value of greater than 120 miles per hour for the speed214.

At step408, for each of the remaining observations140, the sectoring engine220generates the sector320and determines an observed sign position that lies within the sector320. The sector320reflects a field of view of a camera included in the associated vehicle120. Notably, as the speed214increases, the corresponding field of view narrows. At step410, the cluster engine230performs oriented density-based clustering operations on sets of similar observations140to generate the clusters170. As described previously herein, the observations140included in each set of similar observations140share the same sign type216and the same side218, and have headings212that deviate from one another by at most a maximum heading deviation. At step412, for each of the clusters170, the cluster positioning engine240fits estimated positions of the associated observations130to a Gaussian distribution and sets the sign position280to the median of the Gaussian distribution.

At step414, the merging engine250identifies and merges any of the clusters170that likely correspond to the same physical or logical object. For example, if a logical bi-sided road sign “B” includes a left physical road sign “L” and a right physical road sign “R,” then the merging engine250could merge the cluster170(L) that is associated with the left physical road sign “L” and the cluster170(R) that is associated with the right physical road sign “R” to generate the target cluster170(M).

At step416, for each of the clusters170, the confidence engine260computes the associated confidence level172that reflects a reliability of any number of the characteristics specified in the cluster170. For example, the confidence level172(i) reflects the reliability of the sign position280(i) included in the cluster170(i). At step418, the cluster application150transmits the cluster data160, including the clusters170and the associated confidence levels172, to the update application180. The cluster data160enables the update application180to generate the update190associated with a road database. In alternate embodiments, the cluster application150may transmit any portion of the cluster data160to any number and type of applications.

At step420, the cluster application150determines whether the cluster application150is to finish operating. If, at step420, the cluster application150determines that the cluster application150is to finish operating (e.g., the cluster application150has received a command to exit), then the method400terminates. If, however, at step420, the cluster application150determines that the cluster application150is to continue operating, then the method400returns to step404, where the cluster application150receives new observation data130. Advantageously, the cluster application150may be configured to continually receive new observation data130and generate new cluster data160, thereby enabling the update application180to continually generate accurate updates190.

In sum, the disclosed techniques may be used to generate navigation-related data based on clusters that are derived from real-time observations of road signs. A cluster application includes, without limitation, a filtering engine, a sectoring engine, a clustering engine, a cluster positioning engine, a merging engine, and a confidence engine. In operation, the filtering engine receives observation data that includes real-time observations of road signs received from vehicles traveling along roads. The filtering engine identifies and removes any observations that are likely to be inaccurate from the observation data. For each of the remaining observations, the sectoring engine computes a sector that reflects a field of view of the associated vehicle traveling along the specified heading at the specified speed. The sectoring engine then determines an observed sign position based on the sector.

Subsequently, the clustering engine generates clusters of observations, where each cluster characterizes a different sign. The clustering engine implements an oriented density based clustering algorithm based on oriented distances. The clustering engine computes each oriented distance based on the observed sign positions and the reported headings. More specifically, the clustering engine takes into consideration that observations are typically reported by vehicles traveling along roads that coincide with the reported headings. Consequently, each cluster is typically characterized by a rectangular shape that is oriented along a road. Subsequently, for each cluster, the cluster positioning engine estimates a sign position based on fitting the observed sign positions into a Gaussian distribution. The merging engine then identifies and merges any clusters that are likely associated with a single sign or two signs that likely comprise a bi-sided sign. Finally, for each cluster, the confidence engine generates a confidence level based on the number, consistency, and characteristics of the observations included in the cluster.

At least one advantage of the disclosed approach is that because the clustering engine generates each cluster based on multiple error-prone real-time observations of an associated road sign, the clusters characterize road signs more reliably than the observations characterize the road signs. Further, the confidence levels of the clusters enable providers of road databases to identify clusters that meet a reliability criterion. Consequently, the providers of road databases may generate accurate updates to road databases based on the identified clusters. Notably, because the cluster application operates on real-time observations, providers of road databases may produce updates at a frequency that enables navigation applications to continually provide accurate navigation data.