Sparse Randomized Approximation of Normal Cycles

논문 요약: 희소 확률적 근사를 통한 정규 사이클 (Normal Cycles) 압축

1. 연구 배경 및 문제 정의 (Problem)

• 기하학적 학습의 필요성: 계산 해부학 (Computational Anatomy) 등 다양한 기하학적 학습 응용 분야에서 형태 (Shape) 의 변이를 통계적으로 모델링하기 위해, 이산적인 곡선과 표면으로 표현된 형태 데이터 간의 정밀한 비교가 필요합니다.
• 기존 방법의 한계:
  • 포인트 클라우드 거리 (Chamfer, Hausdorff 등): 기하학적 구조를 반영하지 못하며, 밀집된 대응 관계 (dense correspondences) 를 추출하는 과정에서 편향이 발생할 수 있습니다.
  • Currents 및 Varifolds: 미분 형식 (differential forms) 의 쌍대 공간에 형태를 임베딩하여 매개변수화 없이 형태를 비교할 수 있게 하지만, 1 차 기하 정보 (접선, 법선 벡터 방향) 만을 고려합니다. 따라서 높은 곡률, 분기점, 경계선이 있는 복잡한 형태를 매칭할 때 부정확하거나 원치 않는 특징이 생성될 수 있습니다.
• Normal Cycles 의 도입과 한계:
  • Normal Cycles: Currents 의 일반화로, 단위 법선 번들 (unit normal bundle) 에 대한 적분을 수행하여 곡률 (Curvature) 정보를 포함하는 고차원 표현입니다. 이는 Currents 보다 복잡한 형태의 매칭에 훨씬 효과적입니다.
  • 계산 비용 문제: Normal Cycles 기반의 거리 계산은 메모리 및 계산 복잡도가 매우 높습니다. $M, N$개의 에지를 가진 두 삼각형 표면 간의 거리 계산 복잡도는 $O(MN)$이며, Currents 나 Varifolds 에 비해 3~5 배 이상의 계산 비용이 듭니다. 특히 $10^5$ 이상의 고해상도 데이터에서는 실용적인 적용이 어렵습니다.

2. 제안된 방법론 (Methodology)

이 논문은 Currents 와 Varifolds 에 적용되었던 **희소 확률적 압축 알고리즘 [1]**을 Normal Cycles로 확장하여 대규모 데이터에 적용 가능한 압축 기법을 제시합니다.

• Dirac Delta 분해 (Explicit Dirac Delta Decomposition):
  • 상수 정규 커널 (Constant Normal Kernel, $K_s=1$) 설정 하에, 이산화된 삼각형 표면의 정규 사이클을 Dirac Delta 기저 형태로 명시적으로 분해합니다.
  • 정규 사이클 $N(T)$를 **원통형 성분 (Cylindrical component)**과 **구형 성분 (Spherical component)**으로 나누어 표현합니다.
    • 원통형 성분: 표면의 에지 (edges) 에 해당하는 Dirac Delta 합으로 근사 ($N(T)_{cyl} \approx \sum \delta_{c_j} \gamma_j$).
    • 구형 성분: 표면의 경계 (boundary) 에 해당하는 Dirac Delta 합으로 근사 ($N(T)_{sph} \approx \sum \delta_{x_k} \alpha_k$).
    • 평면 성분 (Planar component): $K_s=1$인 경우 0 이 되어 사라집니다.
• 벡터 값 임베딩 (Vector-valued Embedding):
  • 압축 알고리즘이 스칼라 값 함수의 RKHS(Reproducing Kernel Hilbert Space) 를 가정하므로, 외적 공간 (wedge product space) $\Lambda^2(\mathbb{R}^3 \times \mathbb{R}^3)$의 원소를 $\mathbb{R}^{15}$ 값 함수 공간으로 등거리 동형 사상을 통해 변환합니다.
• RLS (Ridge Leverage Score) 샘플링을 통한 희소 압축:
  • 원본 $n$개의 Dirac Delta 중심점 중 RLS 샘플링을 통해 $m$개의 제어점 ($m \ll n$) 을 선택합니다.
  • 선택된 제어점에 대해 직교 투영 (Orthogonal Projection) 을 수행하여 가중치 $\beta_i$를 계산하고, 희소 근사 $\hat{\mu} = \sum_{i=1}^m \delta_{c_i} \beta_i$를 생성합니다.
  • 이 과정에서 KeOps 라이브러리를 활용하여 커널 연산을 가속화합니다.

3. 주요 기여 (Key Contributions)

1. Normal Cycles 압축 알고리즘의 최초 제안: Currents 와 Varifolds 에만 국한되었던 압축 기법을 곡률 정보를 포함하는 Normal Cycles 로 확장한 최초의 연구입니다.
2. 명시적 분해 유도: 상수 정규 커널 ($K_s=1$) 환경에서 이산화된 표면의 정규 사이클에 대한 명시적인 Dirac Delta 분해식을 유도하여, 기존 압축 알고리즘 [1] 의 적용을 가능하게 했습니다.
3. 이론적 보장: [1] 의 이론적 결과를 적용하여, 압축 오차가 $m$ (압축 크기) 에 대해 지수적으로 감소함을 보장합니다 (가우시안 RBF 커널의 경우).
   • 오차 bound: $\|\mu - \hat{\mu}\|_{W^*}^2 \leq O(m \exp(-\alpha m^{1/d}))$.
4. 계산 효율성 극대화: 압축된 정규 사이클 간의 거리 및 기울기 (gradient) 계산 복잡도를 $O(MN)$에서$O(mn)$으로 줄여, 대규모 데이터 처리를 가능하게 합니다.

4. 실험 결과 (Results)

• 데이터셋: 현대 기하 처리 데이터셋 (Cat, Head, Flamingo, Queen, PumpkinHead 등) 의 고해상도 표면 데이터 (최대 59 만 개의 Dirac Delta 중심점) 를 사용했습니다.
• 압축 오차 감소:
  • RLS 샘플링 기반 압축은 균일 무작위 샘플링보다 훨씬 빠른 오차 감소율을 보였습니다.
  • 원본 데이터의 **0.1% 미만 ($m \ll n$)**만 사용하여도 매우 낮은 상대 오차 (< 0.1%) 를 달성했습니다.
• LDDMM (Large Deformation Diffeomorphic Metric Mapping) 등록 (Registration) 성능:
  • Queen 표면 (34 만 개 중심점): 97% 압축 (10,000 개) 시, 등록 시간 2 시간 42 분 $\rightarrow$ 17 분 (약 9~10 배 속도 향상). Hausdorff 거리 오차는 오히려 약간 개선됨 (0.0442 $\rightarrow$ 0.0298).
  • PumpkinHead 표면 (59 만 개 중심점): 99% 압축 (5,000 개) 시, 등록 시간 5 시간 37 분 $\rightarrow$ 17 분 (약 20 배 속도 향상). 시각적 품질과 Hausdorff 거리 (0.1621 $\rightarrow$ 0.1662) 에서 원본과 거의 유사한 결과를 보였습니다.
• 결론: 압축된 표현을 사용하더라도 하위 작업 (Nonlinear Registration) 의 정확도는 유지되면서 계산 속도가 획기적으로 향상됨을 입증했습니다.

5. 의의 및 결론 (Significance)

• 대규모 기하 데이터 처리 가능: 이론적으로 엄밀한 형태 거리 척도인 Normal Cycles 를 $10^5 \sim 10^6$ 수준의 대규모 해상도 데이터에 실용적으로 적용할 수 있는 길을 열었습니다.
• 하위 작업 가속화: Currents 나 Varifolds 보다 정교한 곡률 정보를 활용하면서도, 기존 Currents 기반 방법과 유사한 수준의 계산 효율성을 달성하여 복잡한 형태 매칭 및 통계적 모델링을 가능하게 합니다.
• 향후 과제: 현재 연구는 상수 정규 커널 ($K_s=1$) 에 국한되어 있으나, 향후 선형 및 가우시안 정규 커널로 확장하여 더 높은 차수의 곡률 정보에 대한 민감도를 높이는 것이 향후 과제로 제시되었습니다.

이 논문은 **기하학적 측정 이론 (Geometric Measure Theory)**의 이론적 엄밀함과 **확률적 알고리즘 (Randomised Algorithms)**의 계산 효율성을 결합하여, 현대 기하 학습 및 의료 영상 분석 분야에서 중요한 진전을 이루었습니다.