# US 2024/0202218 A1 · Method, apparatus, and system for providing linear feature detection of cartographic features

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0202218 A1
- Document ID: US20240202218A1
- Status: Published application
- Kind: A1
- Application number: 18/081,346
- Filed: 2022-12-14
- Published: 2024-06-20
- Earliest claimed: 2022-12-14
- Assignees: HERE Global B.V.
- Applicants: HERE Global B.V.
- Inventors: Qi MAO; Zhenhua ZHANG
- Web page: https://patentgrep.com/patent/US20240202218A1

## CPC

- G06F 16/29: Geographical information databases
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 18/213: Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
- G06F 18/231: Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
- G06F 18/24: Classification techniques
- G06V 10/426: Graphical representations
- G06V 10/457: {by analysing connectivity, e.g. edge linking, connected component analysis or slices}
- G06V 10/82: using neural networks
- G06V 20/588: {Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

An approach is provided for linear feature detection of cartographic features. The approach, for example, involves receiving a plurality of linear feature detections that represent one or more linear features of a geographic environment and are detected using at least one sensor. The approach also involves clustering the plurality of linear feature detections into at least one cluster and determining that the at least one cluster forms a polygon. The approach further involves cutting the polygon at one or more cut locations to form a plurality of sub-clusters of the plurality of linear feature detections. The approach further involves extracting respective centerlines for the plurality of sub-clusters and connecting the respective centerlines at the one or more cut locations to generate a network graph of the one or more linear features.

## Claims

### Claim 1

A method comprising:
receiving a plurality of linear feature detections, wherein the plurality of linear features detections represents one or more linear features of a geographic environment that are detected using at least one sensor;
clustering the plurality of linear feature detections into at least one cluster;
determining that the at least one cluster forms a polygon;
cutting the polygon at one or more cut locations to form a plurality of sub-clusters of the plurality of linear feature detections;
extracting respective centerlines for the plurality of sub-clusters;
connecting the respective centerlines at the one or more cut locations to generate a network graph of the one or more linear features; and
providing the network graph as an output.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
performing a recursive cutting of the plurality of sub-clusters at one or more other cut locations based on determining that the plurality of sub-clusters forms respective polygons,
wherein the extracting and the connecting of the respective centerlines is based on the recursive cutting.

### Claim 3 (depends on 2)

The method of claim 2, wherein the recursive cutting is performed all at once.

### Claim 4 (depends on 2)

The method of claim 2, wherein the recursive cutting is performed such that one cut is performed per a recursive step.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
designating a linear feature detection pair comprising two of the plurality of linear feature detections; and
performing a classification of the linear feature detection pair as a must-link pair or a cannot-link pair,
wherein the clustering of the plurality of linear feature detections is based on the classification.

### Claim 6 (depends on 5)

The method of claim 5, wherein the classification is based on whether the linear feature detection pair intersect, an intersecting length, or a combination thereof.

### Claim 7 (depends on 5)

The method of claim 5, wherein the classification is based an angle formed between the linear feature detection pair.

### Claim 8 (depends on 5)

The method of claim 5, wherein the clustering of the plurality of linear feature detections is based on the linear feature detection pair being classified as the must-link pair.

### Claim 9 (depends on 1)

The method of claim 1, wherein the cutting is performed with a designated buffer length applied at the one or more cut locations.

### Claim 10 (depends on 1)

The method of claim 1, wherein the one or more linear features includes one or more lane markings.

### Claim 11

An apparatus comprising:
at least one processor; and
at least one memory including computer program code for one or more programs,
the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,
receive a plurality of linear feature detections, wherein the plurality of linear features detections represents one or more linear features of a geographic environment that are detected using at least one sensor;
designate one or more linear feature detection pairs comprising two different linear feature detections of the plurality of linear feature detections;
perform a classification of one or more linear feature detection pairs into a must-link category or a cannot-link category;
cluster the plurality of linear feature detections into at least one cluster based on the classification; and
generate a network graph of the one or more linear features based on the clustering.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the classification is based on whether the linear feature detection pair intersect, an intersecting length, or a combination thereof.

### Claim 13 (depends on 11)

The apparatus of claim 11, wherein the classification is based an angle formed between the linear feature detection pair.

### Claim 14 (depends on 11)

The apparatus of claim 11, wherein the apparatus is further caused to:
determine that the at least one cluster forms a polygon;
cut the polygon at one or more cut locations to form a plurality of sub-clusters of the plurality of linear feature detections;
extract respective centerlines for the plurality of sub-clusters; and
connect the respective centerlines at the one or more cut locations to generate the network graph.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the apparatus is further caused to:
perform a recursive cutting of the plurality of sub-clusters at one or more other cut locations based on determining that the plurality of sub-clusters from respective polygons,
wherein the extracting and the connecting of the respective centerlines is based on the recursive cutting.

### Claim 16

A non-transitory computer-readable storage medium, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:
receiving a plurality of linear feature detections, wherein the plurality of linear features detections represents one or more linear features of a geographic environment that are detected using at least one sensor;
clustering the plurality of linear feature detections into at least one cluster;
determining that the at least one cluster forms a polygon;
cutting the polygon at one or more cut locations to form a plurality of sub-clusters of the plurality of linear feature detections;
extracting respective centerlines for the plurality of sub-clusters;
connecting the respective centerlines at the one or more cut locations to generate a network graph of the one or more linear features; and
providing the network graph as an output.

### Claim 17 (depends on 16)

The non-transitory computer-readable storage medium of claim 16, wherein the apparatus is caused to further perform:
performing a recursive cutting of the plurality of sub-clusters at one or more other cut locations based on determining that the plurality of sub-clusters from respective polygons,
wherein the extracting and the connecting of the respective centerlines is based on the recursive cutting.

### Claim 18 (depends on 17)

The non-transitory computer-readable storage medium of claim 17, wherein the recursive cutting is performed all at once.

### Claim 19 (depends on 17)

The non-transitory computer-readable storage medium of claim 17, wherein the recursive cutting is performed such that one cut is performed per a recursive step.

### Claim 20 (depends on 16)

The non-transitory computer-readable storage medium of claim 16, wherein the apparatus is caused to further perform:
designating a linear feature detection pair comprising two of the plurality of linear feature detections; and
performing a classification of the linear feature detection pair as a must-link pair or a cannot-link pair,
wherein the clustering of the plurality of linear feature detections is based on the classification.
