Fast Point Feature Histogram(FPFH) descriptor가 무엇일까요?

이 게시물은 장형기님의 SLAM 기술 면접 100선에 대한 제 나름대로의 답을 정리한 것입니다.

FPFH 정의

• 3차원 포인트 클라우드 데이터에서 각 점의 기하학적 특징을 설명하는 descriptor

  • 기존의 PFH(Point Feature Histrogram) descriptor의 계산 속도를 크게 향상시킨 버전

  • 로봇 공학, 자율 주행, 3D 모델링 등 다양한 분야에서 객체 인식, registration, 장면 이해 등에서 역할

FPFH 기본 원리

• 핵심 아이디어: 한 점을 둘러싼 이웃 점들의 기하학적 관계를 수치화하여 해당 점의 고유한 특징으로 삼음

  1단계 SPFH(Simplified Point Feature Histogram) 계산

  • 이웃 탐색

    기준이 되는 쿼리 포인트 $p_q$에 대해, 주어진 반경 $r$ 내에 있는 모든 이웃 점들의 집합 $k$를 찾음

  • 좌표계 정의 및 특징 값 계산

    $P_q$와 이웃 점 중 하나인 $P_k$ 사이의 관계를 정의하기 위해, 두 점의 법선 벡터($n_q,n_k$)를 이용하여
    상대적인 위치와 방향을 나타내는 국소 좌표계, Darboux Frame을 설정

    1. 두 점 중 어느 것을 기준으로 할지 정하기 위해, $p_q$와 $p_k$를 잇는 직선과 각 점의 법선 벡터가
       이루는 각도를 계산하여 더 작은 각도를 갖는 점을 Source, 다른 하나를 target으로 설정

    2. Source를 원점으로 하는 Darboux frame을 다음과 같이 정의

       • $u = n_s$ ( normal vector = source와 수직 방향)
         $v = (p_t-p_s) \times u$(normal vector와 target,source를 잇는 vector와 수직인 방향)
         $w = u\times v$(위에서 두한 두 축과 수직인 방향)

    3. $uvw$좌표계를 기준으로, 타겟 포인트의 법선 벡터 $n_t$의 방향을 설명하는 세가지 각도
       특징을 계산

    • $\alpha = v \bullet n_t$

      $\phi = {u\bullet(p_t-p_s)\over||p_t-p_s||}$

      $\theta = arctan(w\bull n_t, u \bull n_t)$

  • SPFH 히스토그램 생성

    쿼리 포인트 $p_q$의 모든 이웃 점 $p_k$에 대해 (alpha,phi,theta) 삼중항을 구함
    이 값들을 각각 여러 구간으로 나누어 해당 구간에 투표함으로써 3개의 1차원 히스토그램을 만듭니다.
    이

    2단계 최종 FPFH 계산
    SPFH는 계산이 빠르지만, 쿼리 포인트 주변의 기하학적 정보를 충분히 담지 못할 수 있음
    FPFH는 이를 보완하기 위해 이웃들의 정보를 추가로 활용

  • 이웃의 SPFH 집계

    쿼리 포인트 $p_q$의 최종 FPFH를 계산하기 위해, 다시 반경 r 내의 이웃 점 집합 $k$를 찾습니다.
    

  • 가중 합산을 통한 최종 히스토그램 생생

    $p_q$의 FPFH는 자신의 SPFH와 모든 이웃 점($p_k$)들의 SPFH를 가중 합산하여 계산
    이때 가중치는 쿼리 포인트 $p_q$와 이웃 점 $p_k$ 사이의 거리에 반비례하는 값을 주로 사용.

    최종 식은 다음과 같음

    $FPFH(p_q) = SPFH(p_q)+{1\over k}\Sigma^{k}_{i=1}{1 \over w_{k_i}}SPFH(p_{k_i})$

    ---

    FPFH의 장점

  1. 계산 속도가 빠름

     이전 버전인 PFH가 이웃 수의 제곱에 비례하는 계산 시간을 가졌던 반면, FPFH는 이웃끼리의 관계 계산을 생략하여 이웃 수에 정비례하는 시간으로 계산을 끝냅니다. 이 덕분에 실시간 처리가 필요한 분야에 널리 사용될 수 있습니다.

  2. 회전 및 이동에 강건

     FPFH는 점들의 절대 좌표가 아닌, 점들 사이의 상대적인 기하학적 관계를 기반으로 계산되기 때문에
     포인트 클라우드 전체가 회전하거나 이동하더라도 FPFH 값은 거의 변하지 않아, 객체 인식이나 정합에서 안정적인 성능을 보입니다.

  3. Noise 및 밀도 변화에 대한 비교적 높은 안정성
     이웃 점들의 정보를 평균 내기 때문에 일부 점에 noise가 끼거나 포인트의 밀도가 약간 변하더라도 특징 값이 급격하게 변하지 않습니다.

  ---

  FPFH의 단점

  1. 정확도 감소

     속도를 위해 이웃과 이웃 사이의 모든 관계를 계산하는 과정을 포기. 이는 필연적으로 PFH가 담고 있던 미세한 기하학적 정보의 손실로 이어집니다. 매우 복잡하고 정교한 구조를 구분해야 하는 경우, FPFH의 표현력이 부족할 수 있습니다.

  2. Normal vector의 품질에 대한 높은 의존성
     FPFH는 각 점의 표면 방향을 나타내는 normal vector를 기반으로 모든 각도 계산을 시작. 만약 이 초기 vector 추정이 부정확하다면 완전히 틀린 값이 도출되어 잘못된 descriptor를 만들 수 있습니다.

  3. 파라미터 튜닝에 대한 민감성

     이웃을 어디까지 정의할지를 결정하는 탐색 반경'r' 값에 영향을 많이 받습니다.
     'r'이 너무 작을 경우 주변 정보가 너무 부족하여 변별력이 떨어지고 노이즈에 취약해집니다.
     반면 'r'이 너무 크면 다른 객체의 정보까지 침법하여 오히려 성능이 저하됩니다.
     이 때문에 적절한 반경을 찾는 것이 매우 중요합니다.

     ---

     place recognition할 때 많이 쓰이는 FPFH descriptor를 알아보았습니다.
     안써봐서 모르겠지만 한 번 loop closing이나 위치 initialization할 때 사용해보고 싶네요.
     어느 정도 정확할지 살펴보겠습니다.