# US 11,443,465 B2 · Method, apparatus, and computer program product for generating turn paths through an intersection > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,443,465 B2 - Document ID: US11443465B2 - Status: Granted - Kind: B2 - Application number: 16/827,886 - Filed: 2020-03-24 - Published: 2021-09-30 - Granted: 2022-09-13 - Earliest claimed: 2020-03-24 - Assignees: HERE Global B.V. - Applicants: HERE Global, B.V. - Inventors: Ole Henry Dorum - Web page: https://patentgrep.com/patent/US11443465B2 ## CPC - G01C 21/3819: {Road shape data, e.g. outline of a route} - G06T 11/23: using straight lines or curves - G01C 21/32: Structuring or formatting of map data - G01C 21/3841: {Data obtained from two or more sources, e.g. probe vehicles} - G05D 1/0212: {with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287)} - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES ## Abstract A method is provided for gathering probe data and using the gathered data to create map intersection turn paths. Methods may include: receiving probe data from a plurality of probes passing through an intersection; identifying a turn maneuver of the intersection including an incoming road link and an outgoing road link; generating a curve of the turn maneuver based on a geometry of the intersection and a scaling factor; filtering the probe data based on the generated curve to obtain remaining probe data; fitting a spline to the remaining probe data to generate a turn path representative of the turn maneuver; and providing for guidance of a vehicle based on the spline of the turn path. Embodiments including apparatuses and computer program products for creating map intersection turn paths are also provided. ## Claims ### Claim 1 An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and computer program code configured to, with the processor, cause the apparatus to at least: receive probe data from a plurality of probes passing through an intersection; identify a turn maneuver of the intersection including an incoming road link and an outgoing road link; generate a curve of the turn maneuver based on a geometry of the intersection and a scaling factor; filter the probe data by map-matching the probe data to the generated curve with at least one predetermined tolerance based on a placement and shape of the curve to obtain remaining probe data, wherein the map-matched probe data is the remaining probe data; fit a spline to the remaining probe data to generate a turn path representative of the turn maneuver; and provide for guidance of a vehicle based on the spline of the turn path. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the curve comprises a cubic Bézier curve, wherein causing the apparatus to generate a cubic Bézier curve of the turn maneuver based on a geometry of the intersection and a scaling factor comprises causing the apparatus to: establish a first vertex of a control polygon of the cubic Bézier curve at a point along the incoming road link; establish a second vertex of the control polygon of the cubic Bézier curve at a point along the outgoing road link; identify an approximate intersection center; establish a third vertex of the control polygon of the cubic Bézier curve at a point along a vector from the first vertex to the approximate intersection center based on the scaling factor; and establish a fourth vertex of the control polygon of the cubic Bézier curve at a point along a vector from the second vertex to the approximate intersection center based on the scaling factor. ### Claim 3 (depends on 1) The apparatus of claim 1, wherein causing the apparatus to provide for guidance of the vehicle based on the spline of the turn path comprises causing the apparatus to: provide autonomous vehicle control through the intersection following the spline of the turn path. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein causing the apparatus to fit a spline to the remaining probe data to generate the turn path representative of the turn maneuver comprises causing the apparatus to: create a knot vector for the spline wherein a parametric distance between each knot is inversely proportional to a curvature of the curve. ### Claim 5 (depends on 4) The apparatus of claim 4, wherein causing the apparatus to fit a spline to the remaining probe data to generate the turn path representative of the turn maneuver further comprises causing the apparatus to: assign a parametric B-spline value to each point of remaining probe data based on a projected arc-length location along the curve, wherein each point of remaining probe data is projected onto the curve. ### Claim 6 (depends on 5) The apparatus of claim 5, wherein causing the apparatus to fit a spline to the remaining probe data to generate the turn path representative of the turn maneuver further comprises causing the apparatus to: reduce a change of curvature using a regularization function to smooth a curvature of the spline with a regularization factor. ### Claim 7 (depends on 1) The apparatus of claim 1, wherein the at least one predetermined tolerance is a non-zero meter distance threshold, a non-zero degree heading threshold, or a combination thereof. ### Claim 8 A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code instructions stored therein, the computer-executable program code instructions comprising program code instructions to: receive probe data from a plurality of probes passing through an intersection; identify a turn maneuver of the intersection including an incoming road link and an outgoing road link; generate a curve of the turn maneuver based on a geometry of the intersection and a scaling factor; filter the probe data by map-matching the probe data to the generated curve with at least one predetermined tolerance based on a placement and shape of the curve to obtain remaining probe data, wherein the map-matched probe data is the remaining probe data; fit a spline to the remaining probe data to generate a turn path representative of the turn maneuver; and provide for guidance of a vehicle based on the spline of the turn path. ### Claim 9 (depends on 8) The computer program product of claim 8, wherein the curve comprises a cubic Bézier curve, wherein the program code instructions to generate a cubic Bézier curve of the turn maneuver based on a geometry of the intersection and a scaling factor comprise program code instructions to: establish a first vertex of a control polygon of the cubic Bézier curve at a point along the incoming road link; establish a second vertex of the control polygon of the cubic Bézier curve at a point along the outgoing road link; identify an approximate intersection center; establish a third vertex of the control polygon of the cubic Bézier curve at a point along a vector from the first vertex to the approximate intersection center based on the scaling factor; and establish a fourth vertex of the control polygon of the cubic Bézier curve at a point along a vector from the second vertex to the approximate intersection center based on the scaling factor. ### Claim 10 (depends on 8) The computer program product of claim 8, wherein program code instructions to provide for guidance of the vehicle based on the spline of the turn path comprise program code instructions to: provide autonomous vehicle control through the intersection following the spline of the turn path. ### Claim 11 (depends on 8) The computer program product of claim 8, wherein the program code instructions to fit a spline to the remaining probe data to generate the turn path representative of the turn maneuver comprise program code instructions to: create a knot vector for the spline wherein a parametric distance between each knot is inversely proportional to a curvature of the curve. ### Claim 12 (depends on 11) The computer program product of claim 11, wherein the program code instructions to fit a spline to the remaining probe data to generate the turn path representative of the turn maneuver further comprise program code instructions to: assign a parametric B-spline value to each point of remaining probe data based on a projected arc-length location along the curve, wherein each point of remaining probe data is projected onto the curve. ### Claim 13 (depends on 12) The computer program product of claim 12, wherein the program code instructions to fit a spline to the remaining probe data to generate the turn path representative of the turn maneuver further comprise program code instructions to: reduce a change of curvature using a regularization function to smooth a curvature of the spline with a regularization factor. ### Claim 14 A method comprising: receiving probe data from a plurality of probes passing through an intersection; identifying a turn maneuver of the intersection including an incoming road link and an outgoing road link; generating a curve of the turn maneuver based on a geometry of the intersection and a scaling factor; filtering the probe data by map-matching the probe data to the generated curve with at least one predetermined tolerance based on a placement and shape of the curve to obtain remaining probe data, wherein the map-matched probe data is the remaining probe data; fitting a spline to the remaining probe data to generate a turn path representative of the turn maneuver; and providing for guidance of a vehicle based on the spline of the turn path. ### Claim 15 (depends on 14) The method of claim 14, wherein the curve comprises a cubic Bézier curve, wherein generating a cubic Bézier curve of the turn maneuver based on a geometry of the intersection and a scaling factor comprises: establishing a first vertex of a control polygon of the cubic Bézier curve at a point along the incoming road link; establishing a second vertex of the control polygon of the cubic Bézier curve at a point along the outgoing road link; identifying an approximate intersection center; establishing a third vertex of the control polygon of the cubic Bézier curve at a point along a vector from the first vertex to the approximate intersection center based on the scaling factor; and establishing a fourth vertex of the control polygon of the cubic Bézier curve at a point along a vector from the second vertex to the approximate intersection center based on the scaling factor. ### Claim 16 (depends on 14) The method of claim 14, wherein providing for guidance of the vehicle based on the spline of the turn path comprises: providing autonomous vehicle control through the intersection following the spline of the turn path. ### Claim 17 (depends on 14) The method of claim 14, wherein fitting a spline to the remaining probe data to generate the turn path representative of the turn maneuver comprises: creating a knot vector for the spline wherein a parametric distance between each knot is inversely proportional to a curvature of the curve. ### Claim 18 (depends on 17) The method of claim 17, wherein fitting a spline to the remaining probe data to generate the turn path representative of the turn maneuver further comprises: assigning a parametric B-spline value to each point of remaining probe data based on a projected arc-length location along the curve, wherein each point of remaining probe data is projected onto the curve.