Point Cloud 를 군집화해보자 - Clustering : K-means, DBSCAN

Point Cloud 에서 Object 혹은 Ground 를 찾아내는 과제에서는 다음과 같은 Clustering 알고리즘이 다양하게 사용되고 있습니다. 

Object 는 보통 바닥과 이어져 있기 때문에 바닥면을 찾고, 

해당 바닥면을 제거하면 object 가 따로 따로 떨어지게 되어서 object clustering 을 하게 될 때 장점도 있습니다. 

Segmentation 과 Clustering 의 차이점

Segmentation

큰 그룹을 같은 특성을 가지는 작은 그룹으로 분할하는 것. 

- 모든 포인트들에 대해서 Classification 을 진행하는 것. 

 

Clustering

비슷한 애들끼리 뭉치는 것. (Identify hidden patterns or structures in the data and group)

- Unsupervised Learning

 

Segmentation 이 Top-down approach 라면, Clustering 은 Bottom-up approach 라고 할 수 있습니다. 

 

K-means clustering

거리 기반의 Clustering 알고리즘

 

K-means Clustering 은 다음과 같은 단계로 수행됩니다. 

 

1. Initialization : 랜덤하게 Cluster 의 중심을 선정합니다. 

2. 두 가지 단계를 반복적으로 수행합니다. 

  2-1. Assignment : 가장 가까운 점을 할당받습니다. 

  2-2. Refit : Cluster 의 질량 중심을 기준으로 새로운 Center 를 지정합니다. 

따라서 이 과정은 EM (Expectation Minimization: 업데이트하고 - 평균값 찾고 - 업데이트하고 .... ) 알고리즘의 일종인 Coordinate Descent (두 축에 대한 minimization) 로 수행됩니다. 

 

 - 센터의 위치를 찾고, 점들을 그룹화하기

 - 점들을 그룹화하고, 센터의 위치 찾기

 

이런 Optimization 은 항상 수렴한다는 것이 증명되어 있지만, 이 수렴값이 Global 하게 최적의 해라고 할 수는 없습니다. 다만, Local 에 빠지더라도 반드시 수렴은 합니다. 

 

K-means Clustering 의 장단점

장점

 

1. 알고리즘이 간단합니다. 

2. 데이터셋의 크기에 크게 구애받지 않습니다. 

3. 빨리 수렴합니다. 

 

단점

 

1. K 를 알 수 없는 문제가 많습니다. 

2. Outlier 에 민감합니다. 

3. Local Minima 에 빠질 확률이 있습니다. 

좌 : 잘못 분류한 경우 / 우 : K 를 잘못 준 경우

DBSCAN

밀도 기반의 Clustering 알고리즘 : Density-based Spatial Clustering of Applications with Noise

 

거리를 기반으로 하는 (Distance-based) 클러스터링 방법들이 여러 약점이 있었기 때문에, 밀도를 기반으로 하는 (Density-based) 클러스터링 방법들이 출현했습니다. 

 

밀도 기반 Clustering 은 밀도가 높은 포인트끼리 군집화하는 방법입니다. 이때 밀도란 특정 radius r 내부의 점의 갯수 (구 안의 점의 갯수)를 의미합니다. 

 

DBSCAN 은 포인트를 3 가지 종류로 구분합니다. 

 

1. Core 포인트 : "구 안의 n 개의 점" 조건을 만족하는 점들

2. Border 포인트 : 내 구에는 n 개의 점이 없기는 하지만, 나는 다른 core 의 구 안에 들어감

3. Noise 포인트 : 나는 core 포인트도 아니고, border 포인트도 아님 

 

DBSCAN Example Code

 

Open3d 를 활용한 DBSCAN 예제입니다. (코드 출처 : 수업 자료)

ply_point_cloud = o3d.data.PCDPointCloud()
pcd = o3d.io.read_point_cloud(ply_point_cloud.path)

labels = np.array(pcd.cluster_dbscan(eps = 0.02, min_points = 10, print_progress = True))

eps (float) : 직경 (radius)

min_points (int) : 구 안의 점 개수 

 

따라서 코드에서는 2cm 이내에 10개의 점이 있으면 그 점이 core 점이라고 정의하고 있습니다. 

 

---

위 내용은 경희대학교 소프트웨어융합학과 황효석 교수님의 2023년 <3D데이터처리> 수업 내용을 요약한 것입니다.