KR-20260063577-A - METHOD AND APPARATUS FOR CLUSTERING POINT CLOUD DATA FROM LiDAR

KR20260063577AKR 20260063577 AKR20260063577 AKR 20260063577AKR-20260063577-A

Abstract

A clustering method and apparatus for point cloud data of LiDAR are disclosed. The clustering method may include the steps of: acquiring point cloud data of LiDAR; assigning a grid-based index to each of the points included in the point cloud data; and performing density-based clustering of the point cloud data based on the grid-based index.

Inventors

이승은
이상호
안성모

Assignees

서울과학기술대학교 산학협력단

Dates

Publication Date: 20260507
Application Date: 20241030

Claims (5)

Step of acquiring point cloud data from LiDAR; A step of assigning a grid-based index to each of the points included in the above point cloud data; and A step of density-based clustering of the point cloud data based on the grid-based index above. A clustering method including
In paragraph 1, The above-mentioned density-based clustering step is, A step of selecting an arbitrary center point among the points included in the above point cloud data; A step of identifying eight points adjacent to the arbitrary center point using the grid-based index; A step of measuring the distance between the arbitrary center point and each of the eight points; A step of identifying the number of points among the above eight points whose measured distance is less than or equal to a threshold distance; If the number of identified points exceeds a threshold number, a step of forming a group including points whose distance is less than or equal to the threshold distance and the arbitrary center point; and A step of clustering the interior of the above group; A clustering method including
In paragraph 2, The above-mentioned density-based clustering step is, If the number of identified points is less than or equal to a threshold number, a step of selecting another point among the points included in the point group data as an arbitrary center point; A clustering method that further includes
In paragraph 2, The above-mentioned density-based clustering step is, A step of checking whether a center point included in the above group is also included in another group; and If a center point included in the above group is also included in another group, the step of merging the above group and the other group A clustering method that further includes
An input unit for acquiring point cloud data of LiDAR; and A processor that assigns a grid-based index to each point included in the above point cloud data and performs density-based clustering of the point cloud data based on the grid-based index. A clustering device including

Description

Method and apparatus for clustering point cloud data of LiDAR The present invention relates to a clustering method and apparatus for LiDAR point cloud data, and more specifically, to a method and apparatus for reducing the computational complexity of clustering for LiDAR point cloud data. LiDAR sensors, which are one of the sensors used in vehicles, recognize the surrounding environment in three dimensions based on point cloud data obtained through light and plan the vehicle's driving path. Point cloud data obtained from LiDAR sensors recognizes objects through advanced clustering technology, and through this, autonomous vehicles perform safe and efficient autonomous driving by avoiding obstacles that may pose a risk while driving. Conventional clustering methods for LiDAR point cloud data measure the distance between an arbitrary center point and other points included in the point cloud data, and if the number of points within a certain distance from the center point exceeds a certain number, they form a group of points within a certain distance from the center point. However, in order to identify points within a certain distance from the center point, the distance between a single point included in the point cloud data and all points excluding that point must be calculated, so N² operations must be performed for N data points, resulting in a high computational complexity required for clustering. As the computational complexity of an algorithm increases, the hardware performance required for computation and the amount of computation consumed also increase; therefore, there is a demand for a method that can reduce computational complexity compared to conventional clustering methods. FIG. 1 is a drawing illustrating a clustering device according to an embodiment of the present invention. FIG. 2 is an example of a hardware configuration of a clustering device according to an embodiment of the present invention. FIG. 3 is an example of a clustering process according to an embodiment of the present invention. FIG. 4 is an example of the range in which a lidar used in an embodiment of the present invention emits light. FIG. 5 is an example of a process for assigning a grid-based index according to an embodiment of the present invention. FIG. 6 is an example of a clustering accelerator according to an embodiment of the present invention. FIG. 7 is an example of a clustering result according to an embodiment of the present invention. FIG. 8 is a flowchart illustrating a clustering method for point cloud data of a lidar according to an embodiment of the present invention. Figure 9 is a flowchart illustrating a density-based clustering process using the grid of Figure 8. Figure 10 is a flowchart illustrating the internal group clustering process of Figure 9. Hereinafter, embodiments are described in detail with reference to the attached drawings. However, various modifications may be made to the embodiments, and thus the scope of the patent application is not limited or restricted by these embodiments. It should be understood that all modifications, equivalents, and substitutions to the embodiments are included within the scope of the rights. The terms used in the embodiments are for illustrative purposes only and should not be interpreted as intended to be limiting. Singular expressions include plural expressions unless the context clearly indicates otherwise. In this specification, terms such as "comprising" or "having" are intended to indicate the existence of the features, numbers, steps, actions, components, parts, or combinations thereof described in the specification, and should be understood as not precluding the existence or addition of one or more other features, numbers, steps, actions, components, parts, or combinations thereof. In addition, when describing with reference to the attached drawings, identical components are assigned the same reference numeral regardless of drawing symbols, and redundant descriptions thereof are omitted. In describing the embodiments, if it is determined that a detailed description of related prior art could unnecessarily obscure the essence of the embodiments, such detailed description is omitted. Hereinafter, embodiments of the present invention will be described in detail with reference to the attached drawings. FIG. 1 is a drawing illustrating a clustering device according to an embodiment of the present invention. A clustering device (100) according to one embodiment of the present invention may include an input unit (110), a processor (120), and an output unit (130) as shown in FIG. 1. The input unit (110) can receive point cloud data generated by the LiDAR (101) through wired or wireless communication. The input unit (110) can transmit the received point cloud data to the processor (120). The processor (120) can assign a grid-based index to each of the points included in the point cloud data. And, the processor (120) can density-based cluster the point cloud data bas