# US 2020/0401817 A1 · Determining weights of points of a point cloud based on geometric features > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0401817 A1 - Document ID: US20200401817A1 - Status: Published application - Kind: A1 - Application number: 16/910,742 - Filed: 2020-06-24 - Published: 2020-12-24 - Earliest claimed: 2019-06-24 - Assignees: Deepmap Inc. - Applicants: DeepMap Inc. - Inventors: Derik Schroeter - Web page: https://patentgrep.com/patent/US20200401817A1 ## CPC - G06T 7/33: using feature-based methods - G01C 21/30: Map- or contour-matching - G01S 7/4808: {Evaluating distance, position or velocity data} - G01S 17/89: for mapping or imaging - G06F 18/23: Clustering techniques - G06T 7/10: Segmentation; Edge detection (motion-based segmentation G06T7/215) - G06T 7/50: Depth or shape recovery - G06T 7/70: Determining position or orientation of objects or cameras (camera calibration G06T7/80) - G06T 7/74: {involving reference images or patches} - G06V 10/762: using clustering, e.g. of similar faces in social networks - G06V 20/56: exterior to a vehicle by using sensors mounted on the vehicle - G08G 1/0112: {from the vehicle, e.g. floating car data [FCD]} - G01C 21/3822: {Road feature data, e.g. slope data} - G06F 2218/08: Feature extraction - G06T 2207/10028: Range image; Depth image; 3D point clouds - G06T 2207/30252: Vehicle exterior; Vicinity of vehicle - G08G 1/16: Anti-collision systems (road vehicle drive control systems for predicting or avoiding probable or impending collision otherwise than by control of a particular sub-unit B60W30/08) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - 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) - G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) ## Abstract According to one or more embodiments, operations may comprise obtaining a first point cloud. The operations also comprise performing segmentation of the first point cloud, the segmentation generating one or more clusters of points of the point cloud. The operations also comprise determining, for each respective cluster of the plurality of clusters, a respective geometric feature of a corresponding object that corresponds to the respective cluster. The operations also comprise obtaining a second point cloud. The operations also comprise assigning a plurality of weights that comprises assigning a respective weight to each respective cluster based on the respective geometric feature that corresponds to the respective cluster. The operations also comprise obtaining a second point cloud and aligning the first point cloud with the second point cloud based on the plurality of weights. ## Claims ### Claim 1 A method, comprising: obtaining a first point cloud; performing segmentation of the first point cloud, the segmentation generating a plurality of clusters of points of the first point cloud; determining, for each respective cluster of the plurality of clusters, a respective geometric feature of a corresponding object that corresponds to the respective cluster; assigning a plurality of weights that comprises assigning a respective weight to each respective cluster based on the respective geometric feature that corresponds to the respective cluster; obtaining a second point cloud; and aligning, based on the plurality of weights, the first point cloud with the second point cloud. ### Claim 2 (depends on 1) The method of claim 1, wherein the first point cloud is obtained from a LIDAR scan and the second point cloud is obtained from HD map data, further comprising determining a location of a vehicle based on the aligning the first point cloud with the second point cloud. ### Claim 3 (depends on 1) The method of claim 1, wherein the first point cloud is obtained from a first LIDAR scan and the second point cloud is obtained from a second LIDAR scan, further comprising generating an HD map based on the aligning the first point cloud with the second point cloud. ### Claim 4 (depends on 1) The method of claim 1, wherein the first point cloud is obtained from a LIDAR scan and the second point cloud HD map data, further comprising updating an HD map based on the aligning the first point cloud with the second point cloud. ### Claim 5 (depends on 1) The method of claim 1, wherein assigning the plurality of weights includes adjusting relative numbers of points of two or more clusters with respect to each other. ### Claim 6 (depends on 5) The method of claim 5, wherein adjusting the relative number of points includes removing points from at least one of the two or more clusters. ### Claim 7 (depends on 1) The method of claim 1, wherein assigning the plurality of weights includes assigning different priorities to points of different clusters such that alignment operations favor points given higher priority over points given lower priority. ### Claim 8 (depends on 1) The method of claim 1, wherein determining the respective geometric feature comprises: determining a measure of spread of points along a plurality of axes; and comparing the measure of spread along a first axis with a measure of spread along a second axis to determine a shape of the corresponding object that corresponds to the respective cluster. ### Claim 9 (depends on 8) The method of claim 8, wherein the first axis is normal to a horizontal plane and the second axis is parallel to the horizontal plane, wherein determining the shape of the corresponding object that corresponds to the respective cluster comprises determining whether a ratio of the measure of spread along the first axis and the measure of spread along the second axis exceeds a threshold value. ### Claim 10 (depends on 9) The method of claim 9, further comprising: selecting one or more respective clusters having a ratio of the measure of spread along the first axis and the measure of spread along the second axis that exceeds a threshold value; assigning higher weights to points of one or more selected clusters; and assigning lower weights to points outside of one or more selected clusters. ### Claim 11 One or more non-transitory computer readable storage media storing instructions that, in response to being executed by one or more processors, cause a system to perform operations, the operations comprising: obtaining a first point cloud; performing segmentation of the first point cloud, the segmentation generating a plurality of clusters of points of the first point cloud; determining, for each respective cluster of the plurality of clusters, a respective geometric feature of a corresponding object that corresponds to the respective cluster; assigning a plurality of weights that comprises assigning a respective weight to each respective cluster based on the respective geometric feature that corresponds to the respective cluster; obtaining a second point cloud; and aligning, based on the plurality of weights, the first point cloud with the second point cloud. ### Claim 12 (depends on 11) The one or more non-transitory computer readable storage media of claim 11, wherein the first point cloud is obtained from a LIDAR scan and the second point cloud is obtained from HD map data, and wherein the operations further comprise determining a location of a vehicle based on the aligning the first point cloud with the second point cloud. ### Claim 13 (depends on 11) The one or more non-transitory computer readable storage media of claim 11, wherein the first point cloud is obtained from a first LIDAR scan and the second point cloud is obtained from a second LIDAR scan, and wherein the operations further comprise generating an HD map based on the aligning the first point cloud with the second point cloud. ### Claim 14 (depends on 11) The one or more non-transitory computer readable storage media of claim 11, wherein the first point cloud is obtained from a LIDAR scan and the second point cloud HD map data, and wherein the operations further comprise updating an HD map based on the aligning the first point cloud with the second point cloud. ### Claim 15 (depends on 11) The one or more non-transitory computer readable storage media of claim 11, wherein assigning the plurality of weights includes adjusting relative numbers of points of two or more clusters with respect to each other. ### Claim 16 (depends on 15) The one or more non-transitory computer readable storage media of claim 15, wherein adjusting the relative number of points includes removing points from at least one of the two or more clusters. ### Claim 17 (depends on 11) The one or more non-transitory computer readable storage media of claim 11, wherein assigning the plurality of weights includes assigning different priorities to points of different clusters such that alignment operations favor points given higher priority over points given lower priority. ### Claim 18 (depends on 11) The one or more non-transitory computer readable storage media of claim 11, wherein determining the respective geometric feature comprises: determining a measure of spread of points along a plurality of axes; and comparing the measure of spread along a first axis with a measure of spread along a second axis to determine a shape of the corresponding object that corresponds to the respective cluster. ### Claim 19 (depends on 18) The one or more non-transitory computer readable storage media of claim 18, wherein the first axis is normal to a horizontal plane and the second axis is parallel to the horizontal plane, wherein determining the shape of the corresponding object that corresponds to the respective cluster comprises determining whether a ratio of the measure of spread along the first axis and the measure of spread along the second axis exceeds a threshold value. ### Claim 20 (depends on 19) The one or more non-transitory computer readable storage media of claim 19, wherein the operations further comprise: selecting one or more respective clusters having a ratio of the measure of spread along the first axis and the measure of spread along the second axis that exceeds a threshold value; assigning higher weights to points of one or more selected clusters; and assigning lower weights to points outside of one or more selected clusters. ### Claim 21 A system comprising: one or more processors; and one or more non-transitory computer readable storage media storing instructions that, in response to being executed by the one or more processors, cause the system to perform operations, the operations comprising: obtaining a first point cloud; performing segmentation of the first point cloud, the segmentation generating a plurality of clusters of points of the first point cloud; determining, for each respective cluster of the plurality of clusters, a respective geometric feature of a corresponding object that corresponds to the respective cluster; assigning a plurality of weights that comprises assigning a respective weight to each respective cluster based on the respective geometric feature that corresponds to the respective cluster; obtaining a second point cloud; and aligning, based on the plurality of weights, the first point cloud with the second point cloud. ### Claim 22 (depends on 21) The system of claim 21, wherein the first point cloud is obtained from a LIDAR scan and the second point cloud is obtained from HD map data, and wherein the operations further comprise determining a location of a vehicle based on the aligning the first point cloud with the second point cloud. ### Claim 23 (depends on 21) The system of claim 21, wherein the first point cloud is obtained from a first LIDAR scan and the second point cloud is obtained from a second LIDAR scan, and wherein the operations further comprise generating an HD map based on the aligning the first point cloud with the second point cloud. ### Claim 24 (depends on 21) The system of claim 21, wherein the first point cloud is obtained from a LIDAR scan and the second point cloud HD map data, and wherein the operations further comprise updating an HD map based on the aligning the first point cloud with the second point cloud. ### Claim 25 (depends on 21) The system of claim 21, wherein assigning the plurality of weights includes adjusting relative numbers of points of two or more clusters with respect to each other. ### Claim 26 (depends on 25) The system of claim 25, wherein adjusting the relative number of points includes removing points from at least one of the two or more clusters. ### Claim 27 (depends on 21) The system of claim 21, wherein assigning the plurality of weights includes assigning different priorities to points of different clusters such that alignment operations favor points given higher priority over points given lower priority. ### Claim 28 (depends on 21) The system of claim 21, wherein determining the respective geometric feature comprises: determining a measure of spread of points along a plurality of axes; and comparing the measure of spread along a first axis with a measure of spread along a second axis to determine a shape of the corresponding object that corresponds to the respective cluster. ### Claim 29 (depends on 28) The system of claim 28, wherein the first axis is normal to a horizontal plane and the second axis is parallel to the horizontal plane, wherein determining the shape of the corresponding object that corresponds to the respective cluster comprises determining whether a ratio of the measure of spread along the first axis and the measure of spread along the second axis exceeds a threshold value. ### Claim 30 (depends on 29) The system of claim 29, wherein the operations further comprise: selecting one or more respective clusters having a ratio of the measure of spread along the first axis and the measure of spread along the second axis that exceeds a threshold value; assigning higher weights to points of one or more selected clusters; and assigning lower weights to points outside of one or more selected clusters.