[Python] 3차원 영역확장 알고리즘 (3D region growing algorithm)

To Do

✅ Pointcloud 탐색 관련 알고리즘

✅ Region growing 알고리즘 이해

✅ 관련 python 코드 작성

✅ 3D point cloud에 segmentation 적용 결과

 

Point cloud Search(점군 탐색)

 

포인트 클라우드는 unstructured 데이터이다.

포인트는 x, y, z 좌표로 이루어져 있는데, 그 주위의 이웃하는 점(neighbor point)을 특정하는게 그렇게 사소한 작업(trivial task)은 아니다. 점 간의 거리 계산은 포인트 클라우드나 매쉬(mesh) 분석, 노이즈 제거, 면 다듬기(local smoothing), 모델을 표현하기 위한 점 줄이기(decimation) 등등 많은 부분에 필요한 작업이다.

 

포인트 클라우드나 매쉬 탐색에는 다음의 method를 주로 이용하는데,

• KD-Tree
• Octree
• FlannSearch

[ 출처: https://pcl.gitbook.io/tutorial/part-2/part02-chapte02-search ]

다음의 목적으로 활용한다.

1. 한 점과 다른 모든 점과의 거리를 loop 돌릴 수 있지만 효율적이지 못하다.
   몇 백만, 천만 포인트를 갖는 포인트의 경우 절대 해서는 안될 작업이다.
2. 즉, 효율적인 거리 계산(distance calculation)과 이웃 분석(neighborhood anlaysis)에 장점을 갖는다.

이 포스트에서는 일단 KD-Tree만 다뤄보겠다.

 

[ KD-Tree ]

KD-Tree 생각보다 이해하기가 어려웠다.

한글로 이미 작성된 자료들은 너무 어렵게 설명하고 있었고 직관적이지 못하다고 생각해서, 나도 이해하고 나중에 읽는 사람도 도움이 됐으면 해서 그림으로 절차들을 나타내봤다. (참조한 유툽에서 어떤식으로 트리를 만들고 점을 찾아나가는지 꽤 쉽게 설명해주고 있었다)

 

아래 그림에서는,

보라색 점과 가장 가까운 점은 어디가 될까? 그리고 어떻게 효율적으로 찾을까?가 궁극적인 목표이다.

빨간 음영은 x좌표로 구분하면 보라색 점이 어느 영역에 있는지를 나타낸 것이다.

 

이후 과정도 동일한데,

A의 child B로 넘어가서 y좌표를 비교하고, 그 다음 또 child E로 넘어가 x좌표를 비교한다 [그림 2].

그림 1. KD-Tree - parent A와 비교

그림 2. KD-Tree - child와 비교

 

Region growing algorithm

주로 2D 데이터 즉, 이미지에 적용이 많이 되어 왔으나 최근 3D 데이터에 대해서도 적용이 많이 되고 있다.

위키에서는 다음과 같이 정의하고 있다.

Region growing is a simple region-based image segmentation method.
It is also classified as a pixel-based image segmentation method since it involves the selection of initial seed points.

 

https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLII-3-W10/153/2020/isprs-archives-XLII-3-W10-153-2020.pdf

 

이 알고리즘의 적용은 pcl library 설치를 통해서 쓰면 가장 편한데 관련 설치 과정은 다음 포스트에서 다뤄보겠다.

python C++ 바인딩을 github에 올린 사람이 있는데, 설치 과정이 조금 복잡하고 환경마다 빌드가 되고 안되고가 있었기 때문에 Docker를 이용한 환경을 만들어 주었다.

 

Python code

요즘 ChatGPT 이용 많이들 한다. 수월한 코딩 그리고 이해를 위해 한번 이용해봤다.

코드의 기본 골조를 만들기에는 굉장히 좋은 툴이지 않나 싶다. 제안하는 코드 작성 방식은 다음과 같다.

1. Choose a seed point from the point cloud.
2. Initialize an empty region with the seed point.
3. Find the neighboring points of the seed point that satisfy a certain criterion (e.g. similar color).
4. Add the neighboring points to the region.
5. Repeat steps 3 and 4 for all the points in the region.
6. Repeat the process for multiple seed points until all points in the point cloud are assigned to a region.

Numpy, scikit-learn, Open3D package를 사용하라는 문구도 뜬다. processing 관련해서 쓰고 있었던 package였어서 꽤나 정확하다는 생각이 든다 ㅋㅋ

 

일단은 Open3D를 빼고, 관련해서 객체를 만들었고 객체 내 method 작성을 해봤다.

추후 작업하는 모든 부분은 github에 공유할 예정이다.

import numpy as np
from sklearn.neighbors import KDTree

def region_growing(self, seed=(0,0,0), thres=0.1):
        """
        Perform region growing on a 3D point cloud.

        Parameters:
            points (np.array): 3D point cloud.
            seed (tuple): Seed point in the point cloud.
            thres (float): Distance threshold for adding a point to the region.
        
        Returns:
            region (np.array): indices of points in the region.
        """
        kdtree = KDTree(self.points)
        region = [seed]
        
        for idx in region:
            indices = KDTree.query_radius(self.points[idx].reshape(1,-1), return_distance=False, sort_results=True, r=thres)
            for i in indices[0]:
                if i not in region:
                    region.append(i)
        return np.array(region)

음 기본 골조는 짜주지만,

아직 실제로 적용하기에는 부족하다 ㅋㅋㅋㅋ

다음 포스트에서 python-pcl으로 제대로 한번 알아보자.

 

Reference(참조)

1. Neighborhood Analysis, KD-Trees, and Octrees for Meshes and Point Clouds in Python
2. KD-Tree 관련 youtube 영상

Neighborhood Analysis, KD-Trees, and Octrees for Meshes and Point Clouds in Python