[Computer Vision] FPS(Farthest Point Sampling)에 대하여

이 글에서는 FPS가 무엇인지 간단하게 설명하고, Computer Vision에서 언제 어떻게 쓰이는지 예시와 함께 다룰 예정입니다. (본인 공부 및 기록용)😁

FPS(Farthest Point Sampling)란?

FPS(Farthest Point Sampling) 알고리즘은 컴퓨터 그래픽스 및 컴퓨터 비전 분야에서 자주 사용되는 기법으로, 포인트 클라우드에서 가장 멀리 떨어진 포인트들을 순차적으로 선택하는 방식입니다.

FPS는 Greedy 알고리즘의 일종으로, 이전 선택된 포인트와의 거리를 기준으로 그 순간의 최적 선택을 합니다. 이는 미래의 선택을 고려하지 않고, 항상 현재 상태에서 가장 멀리 있는 포인트를 선택하는 방식입니다. 비록 단순한 방식이지만, 효율적이고 효과적인 결과를 만들어내는 것으로 잘 알려져 있습니다.

대규모 데이터 셋에서 대표적인 포인트를 선택하여 원본 데이터의 중요한 특성을 유지하면서도 계산 비용을 줄이는 데 활용됩니다. 쉽게 말해, 입력 데이터 셋에서 중요한 포인트들만 선택하여 적은 수의 포인트로도 원본 데이터를 효과적으로 대표하는 것이 목적입니다. 이러한 알고리즘은 특히 3D 지오메트리 처리, 포인트 클라우드 처리, 표면 재구성 등 다양한 응용 분야에서 널리 사용됩니다.

FPS 알고리즘 동작 과정. 시간복잡도 : O(nk), n: 입력 포인트 수, k: 선택할 포인트 수

a. 선택된 포인트 집합 초기화: 처음에는 선택된 포인트가 없는 빈 상태에서 시작합니다.

b. 임의의 첫 포인트 선택: 포인트 클라우드에서 임의의 포인트 하나를 선택하고 이를 선택된 포인트 집합에 추가합니다.

c. 거리를 계산: 남아 있는 모든 포인트들과 선택된 포인트들 사이의 거리를 계산합니다.

d. 가장 먼 포인트 선택: 선택되지 않은 포인트 중에서 선택된 포인트들과의 거리가 가장 먼 포인트를 찾아 선택된 포인트 집합에 추가합니다.

e. 반복: c ~ d 단계를 반복하여 필요한 만큼의 포인트를 선택합니다.

FPS에서 고른 point들이 Keypoint가 되는 이유

Keypoint란?

Keypoint는 보통 데이터나 이미지에서 중요한 특징을 나타내는 포인트를 의미합니다. 3D 포인트 클라우드에서도 마찬가지로, keypoint는 중요한 구조적 정보나 형상을 표현하는 포인트입니다. Keypoint들은 원본 데이터에서 전체적인 형태나 구조를 잘 표현할 수 있는 작은 부분 집합입니다.

FPS 알고리즘에서 왜 Keypoint가 되는가?

FPS에서 선택된 포인트들이 keypoint로 간주되는 이유는 이 포인트들이 원본 데이터의 중요한 특징을 보존할 수 있기 때문입니다. FPS는 선택된 포인트들 간의 최대 거리를 유지하여 고르게 분포된 대표적인 포인트를 선택합니다. 이를 통해 전체 데이터에서 중요한 부분을 잘 나타낼 수 있는 포인트들을 고르게 추출하게 됩니다.

1. 고르게 분포된 대표성

FPS는 기존에 선택된 포인트들과 가장 멀리 떨어진 포인트를 반복적으로 선택합니다. 이 과정에서 전체 포인트 클라우드 데이터에서 중복되지 않는 정보를 가진 포인트들을 선택하는 것이며, 이는 전체 데이터를 적은 수의 포인트로도 잘 대표할 수 있도록 합니다.

중요한 구조적 정보를 포함: 각 선택된 포인트는 서로 다른 영역의 정보를 제공하므로, 전체 데이터를 적은 수의 포인트로 잘 요약할 수 있습니다.

2. 정보 보존

FPS는 공간적 분포를 최대한 유지하면서 대표적인 포인트들을 선택하기 때문에, 원본 데이터의 형상이나 주요 구조는 최대한 보존됩니다. 이 때문에 선택된 포인트들이 원본 포인트 클라우드에서 중요한 Keypoint로 여겨집니다.

예를 들어, 특정 물체의 모서리, 굴곡, 평평한 부분 등의 구조적 특성은 FPS로 선택된 포인트들에 의해 잘 표현될 수 있습니다.

3. 중요한 특징 선택

FPS는 선택된 포인트들이 서로 멀리 떨어져 있는 것을 보장합니다. 이 말은, 중요한 특징이 있는 곳들이 대표 포인트로 선택될 가능성이 크다는 의미입니다. 특정 지역의 포인트들이 밀집되어 있다면, 그 중 가장 먼 포인트를 선택하는 방식으로 특정 특징을 강조할 수 있습니다.

모서리, 구석, 곡선 같은 정보는 더 많은 포인트를 필요로 하므로, 이러한 특징들이 FPS 알고리즘에서 자연스럽게 선택되는 경향이 있습니다.

FPS의 응용 분야

FPS는 3D 데이터 처리와 관련된 다양한 분야에서 활용될 수 있습니다. 특히 표면 재구성(surface reconstruction)에서 중요한 역할을 합니다. 원본 포인트 클라우드에서 필요한 만큼의 포인트를 선택하여 복잡한 표면을 적절히 재구성할 수 있습니다. 또한 포인트 클라우드 압축(point cloud compression)에서도, FPS를 통해 데이터의 크기를 줄이면서도 그 안의 중요한 구조적 정보를 보존할 수 있습니다.

예시 응용 분야:

• 3D 스캔 데이터의 단순화: 복잡한 3D 스캔 데이터에서 중요한 포인트들만을 선택하여 후속 처리를 가볍게 만듭니다.

• 로봇 공학: 로봇이 인식하는 환경 데이터를 압축하거나 단순화할 때 사용됩니다.

• AR/VR: 실시간으로 대규모 3D 데이터를 처리하는 과정에서 FPS를 통해 계산량을 줄이고 성능을 향상시킵니다.

결론

FPS 알고리즘은 대규모 포인트 클라우드 데이터 처리에서 대표 포인트를 선택하는 효율적이고 직관적인 방법입니다. 이 알고리즘은 중요한 정보를 보존하면서도 계산 비용을 크게 줄일 수 있기 때문에, 다양한 응용 분야에서 핵심적인 역할을 수행합니다. 간단한 구현과 강력한 성능 덕분에, FPS는 많은 3D 처리 및 분석 알고리즘의 필수적인 전처리 도구로 자리 잡고 있습니다.