Mining map data to predict turn restrictions

Patent metadata

Field	Value
Publication number	US-12429355-B2
Application number	US-202318119199-A
Country	US
Kind code	B2
Filing date	Mar 8, 2023
Priority date	Mar 8, 2023
Publication date	Sep 30, 2025
Grant date	Sep 30, 2025

Abstract

Disclosed herein is a system for mining map data to automatically identify and/or predict turn restrictions. The systems uses street-level imagery to recognize and locate posted signs (e.g., physical signs, electronic signs) that signal, or are in some way related to, a turn restriction at an intersection. Then, the techniques use a cascade of machine learning models to accurately predict whether the recognized and located signs impose the turn restriction at the intersection. Consequently, the human effort required to identify turn restrictions is greatly decreased, if not completely eliminated. Furthermore, electronic maps can more efficiently be expanded and/or updated which improves the experience for vehicle drivers that reply upon the electronic maps for directions from original locations to destination locations.

First claim

What is claimed is:

1. A method for mining map data to automatically predict a turn restriction, the method comprising:
accessing, by at least one processing unit, the map data that includes street geometry and a plurality of images;
identifying an intersection, in the street geometry, that includes at least three navigable edges;
defining a turn maneuver from a first navigable edge included in the intersection onto a second navigable edge included in the intersection;
identifying a first turn maneuver image amongst the plurality of images that provides a first perspective from an approach to the intersection on the first navigable edge;
identifying a second turn maneuver image amongst the plurality of images that provides a second perspective from within the intersection;
recognizing, in the first turn maneuver image and the second turn maneuver image, a plurality of signs related to the turn restriction being imposed on the turn maneuver;
providing, as first input parameters, the plurality of signs to a first machine learning model, the first machine learning model trained to output a score for each sign of the plurality of signs, the score indicating a level of confidence that a corresponding sign imposes the turn restriction on the turn maneuver;
identifying a plurality of intersection images amongst the plurality of images;
determining, with respect to a baseline location associated with the intersection, a location for each sign of the plurality of signs using the plurality of intersection images; and
providing, as second input parameters, the location for each sign of the plurality of signs and the score for the sign to a second machine learning model, the second machine learning model trained to adjust the score for the sign based on the location for the sign and to output a prediction regarding whether the turn restriction is imposed on the turn maneuver based on the adjusted scores for the plurality of signs.

2. The method of claim 1 , wherein the first machine learning model comprises a first gradient-boosted decision tree (GBDT) model and the second machine learning model comprises a second GBDT model.

3. The method of claim 2 , wherein the first GBDT model is trained to determine the score for each sign of the plurality of signs based on:
a first prediction of whether the sign, when considered alone, imposes the turn restriction; and
a second prediction based on whether the plurality of signs, when considered as an aggregate, impose the turn restriction.

4. The method of claim 2 , wherein the second GBDT model is trained to adjust the score based on:
a first prediction of whether the location of an individual sign, when considered alone, imposes the turn restriction; and
a second prediction based on whether the locations of the plurality of signs, when considered as an aggregate, impose the turn restriction.

5. The method of claim 1 , further comprising:
accessing Global Positioning System (GPS) traces from vehicles that drive through the intersection; and
validating the prediction of whether the turn restriction is imposed based on the GPS traces.

6. The method of claim 1 , wherein recognizing the plurality of signs related to the turn restriction being imposed on the turn maneuver comprises implementing bounding box recognition that identifies a portion of an image that contains a sign and considers at least one of: a shape of the sign, a color of the sign, a shape of a graphic illustrated on the sign, a color of a graphic illustrated on the sign, or a word written on the sign.

7. The method of claim 1 , wherein determining the location for each sign of the plurality of signs comprises:
identifying a common point on the sign for at least two images; and
using camera geometry and linear algebra to determine the location for the sign.

8. The method of claim 1 , wherein recognizing the plurality of signs related to the turn restriction being imposed on the turn maneuver is limited to a set of predefined signs such that other signs not included in the set of predefined signs are not recognized.

9. The method of claim 1 , further comprising updating the map data with the prediction regarding whether the turn restriction is imposed on the turn maneuver.

10. A system for mining map data to automatically predict a turn restriction, the system comprising:
a processing unit; and
a computer-readable storage medium having computer-executable instructions stored thereupon, which, when executed by the processing unit, cause the processing unit to perform operations comprising:
accessing the map data that includes street geometry and a plurality of images;
identifying an intersection, in the street geometry, that includes at least three navigable edges;
defining a turn maneuver from a first navigable edge included in the intersection onto a second navigable edge included in the intersection;
identifying a first turn maneuver image amongst the plurality of images that provides a first perspective from an approach to the intersection on the first navigable edge;
identifying a second turn maneuver image amongst the plurality of images that provides a second perspective from within the intersection;
recognizing, in the first turn maneuver image and the second turn maneuver image, a plurality of signs related to the turn restriction being imposed on the turn maneuver;
providing, as first input parameters, the plurality of signs to a first machine learning model, the first machine learning model trained to output a score for each sign of the plurality of signs, the score indicating a level of confidence that a corresponding sign imposes the turn restriction on the turn maneuver;
identifying a plurality of intersection images amongst the plurality of images;
determining, with respect to a baseline location associated with the intersection, a location for each sign of the plurality of signs using the plurality of intersection images; and
providing, as second input parameters, the location for each sign of the plurality of signs and the score for the sign to a second machine learning model, the second machine learning model trained to adjust the score for the sign based on the location for the sign and to output a prediction regarding whether the turn restriction is imposed on the turn maneuver based on the adjusted scores for the plurality of signs.

11. The system of claim 10 , wherein the first machine learning model comprises a first gradient-boosted decision tree (GBDT) model and the second machine learning model comprises a second GBDT model.

12. The system of claim 11 , wherein the first GBDT model is trained to determine the score for each sign of the plurality of signs based on:
a first prediction of whether the sign, when considered alone, imposes the turn restriction; and
a second prediction based on whether the plurality of signs, when considered as an aggregate, impose the turn restriction.

13. The system of claim 11 , wherein the second GBDT model is trained to adjust the score based on:
a first prediction of whether the location of an individual sign, when considered alone, imposes the turn restriction; and
a second prediction based on whether the locations of the plurality of signs, when considered as an aggregate, impose the turn restriction.

14. The system of claim 10 , wherein the operations further comprise:
accessing Global Positioning System (GPS) traces from vehicles that drive through the intersection; and
validating the prediction of whether the turn restriction is imposed based on the GPS traces.

15. The system of claim 10 , wherein recognizing the pl

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Webber Ivan
• Marin Marius Alexandru
• Tamazyan Albert
• Tan Ming

Classifications

• G01C21/3815

  Road data · CPC title

• G06V20/182

  Network patterns, e.g. roads or rivers · CPC title

• G06V20/176

  Urban or other man-made structures · CPC title

• G06V10/70 Primary

  using pattern recognition or machine learning (optical pattern recognition or electronic computations therefor G06V10/88) · CPC title

• G06N20/20

  Ensemble learning · CPC title