Point Cloud Descriptor (2) : FPFH, 3DSC, SHOT, NARF

FPFH (Fast Point Feature Histogram)

 

이전 포스팅 (https://zzziito.tistory.com/46) 에서 소개했던 PFH 에서 문제가 되는 부분이 여러 개 있었습니다. 

우선 PFH 는 특정 포인트와 그 Vicinity 에 대해서 Quadreplet 을 만들기 때문에 \(O(nk^{2})\) 의 시간 복잡도를 가지게 됩니다. 즉, 프로세싱 시간이 굉장히 깁니다. 

 

따라서 이런 높은 시간복잡도 문제를 해결하기 위해서 PFH 의 개선된 버전으로 FPFH 가 고안되었습니다. 새로 도입된 여러 장치들 덕분에 FPFH 의 시간복잡도는 \(O(nk)\) 로 한층 낮아졌습니다. 이렇게 낮아진 시간복잡도의 가장 큰 원인은, FPFH 는 fully-interconnect 되어 있지 않다는 것입니다. 

 

PFH 의 경우, 주변 점들을 모두 계산하는 (fully-interconnect) 방식이었지만 FPFH 는 그렇게 하지 않습니다. 

 

SPFH (Simplified Point Feature Histogram)

 

FPFH 를 설명하기에 SPFH 에 대해서 설명할 필요가 있습니다. 

 

SPFH 에서는 모든 포인트들이 "자신과 직접적으로 연결된 포인트" 들만 가지고 SPFH 를 만듭니다. 또한 기존의 PFH 에서는 4가지 값을 쓰는 Quadreplet 이었지만, SPFH 에서는 세 가지 값 (\(\alpha , \pi , \theta \)) 의 Triplet 을 사용하는 것도 변화된 부분입니다. (d가 빠짐)

 

 

따라서 q 에 대한 FPFH 는, 실제 q 에 대한 SPFH + 주변 점들의 SPFH 의 가중 평균 으로서 만들어집니다. 

FPFH (Fast Point Feature Histogram)

FPFH 는 PFH 처럼 모든 점들 사이의 Quadreplet 을 다 구하지 않고, SPFH 를 구함으로써 히스토그램 수를 대폭 줄였습니. 

 

또한 Caching 을 통해서 이미 구해놓은 값들을 다 저장해 놓고 다시 구하지 않음으로써 연산량을 줄였고, 포인트들을 미리 정렬 해 놓음으로써 주변 점들을 찾는 데 드는 시간을 줄였습니다. 

 

3DSC (3D Shape Context)

 

2D Shape Context

 

2D Shape Context

 

2D 에서 Shape Context 는 점과 그 이웃하는 점들로 만들어지는 Local Descriptor 입니다. 따라서 Shape Context 도 모든 포인트마다 생성됩니다. 

3DSC 의 경우, 2D 에서처럼 구획을 나눠 각 구획에 들어있는 점의 갯수를 세어 Descriptor 를 만드는 Shape Context 방식을 3차원으로 확장한 것입니다. 

 

 "구의 north pole" 은 포인트의 normal vector 의 방향으로 지정되는데, 따라서 3DSC 는 in-plane rotation 에 invariant 하지 않다는 단점이 있습니다. 즉, normal 방향을 축으로 회전을 할 경우 같은 포인트에서 Descriptor 가 다르게 나올 수 있다는 것입니다. 

 

그래서 이런 단점을 보완하기 위해서 SHOT 이 등장했습니다. 

 

SHOT (Signature of Histogram OrienTation)

 

SHOT 은 3DSC 의 개선 버전입니다. 개선된 부분은 다음과 같습니다. 

 

1. in-plane rotation 에 대해서도 invariant 하도록 변경했습니다. 

normal 방향으로 회전하면 Shape Context 의 기준 좌표계도 같이 회전하도록 개선했습니다. 이때 회전 여부 및 방향은 Eigen Decomposition 을 통해서 알게 됩니다. 

 

2. 3DSC 의 경우 구획 안의 포인트의 갯수를 Descriptor 로 만들었는데, SHOT 은 갯수가 아닌 포인트들의 관계를 이용하여 Descriptor 를 만들었습니다. 

 

NARF (Normal Aligned Radial Feature)

 

NARF 의 경우, Point Cloud 가 아닌 Depth Image 에 대한 Descriptor 를 만듭니다. 따라서 이는 2차원 상에서의 프로세싱입니다. 

이와 같이 Star 패턴을 이용해서 방사형 줄 단위로 밝기값을 이용해서 Descriptor 를 만들게 됩니다. 

 

---

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