A Discrete Radon Transform Based on the Area of Cube-Plane Intersection

1. 문제 제기 (Problem)

• 배경: 라돈 변환은 단층 촬영 (tomography), 최적 수송 (optimal transport), 결정학, 기하학적 분석 등 다양한 분야에서 핵심적인 도구로 사용됩니다.
• 현황 및 한계:
  • 기존 이산 라돈 변환 방법들은 주로 2 차원에 국한되거나, 푸리에 보간 (Fourier interpolation) 을 사용하여 아티팩트 (artifacts) 를 발생시키거나, 몬테카를로 (Monte Carlo) 적분을 사용하여 고해상도에서 계산 비용이 매우 높습니다.
  • 볼록한 입체 (voxel) 로 표현된 데이터의 경우, 단순한 중심 투영 (center-projection) 은 정확도가 낮고, 고차원에서의 정확한 교차 면적 계산에 대한 통일된 수식 부재가 문제였습니다.
• 목표: 볼록한 입체 (axis-aligned hypercube) 와 초평면 (hyperplane) 의 교차 면적을 정확하고 효율적으로 계산할 수 있는 해석적으로 정확한 (analytically exact) 이산 라돈 변환을 개발하는 것.

2. 방법론 (Methodology)

A. 하이퍼큐브의 라돈 변환에 대한 닫힌 형식 유도 (Theorem 1)

• 핵심 아이디어: $d$차원 공간에서 축에 정렬된 (axis-aligned) 하이퍼큐브와 임의의 방향 $\theta$를 가진 초평면 $H_\theta(t)$ 사이의 교차 면적 ($d-1$차원 부피) 을 구하는 문제를 해결합니다.
• 수학적 결과:
  • 교차 면적은 **조각별 다항식 (piecewise polynomial)**으로 표현됩니다.
  • 차수 (degree) 는 $d-1$이며, $d-2$번 미분 가능합니다.
  • 공식은 하이퍼큐브의 $2^d$개의 꼭짓점 (vertices) 을 기반으로 한 합 (summation) 형태로 주어지며, 이는 기하학적 삼각분할 (triangulation) 보다 계산적으로 효율적입니다.
  • 정리 1 (Theorem 1): 방향 $\theta$와 거리 $t$에 대한 라돈 변환 $A^\mathbf{a}_\theta(t)$는 다음과 같은 형태로 주어집니다.
    $$A^\mathbf{a}_\theta(t) = \frac{2^{d-\ell} P(\mathbf{a})}{P((\mathbf{a} \circ \theta)^\circ)} \frac{1}{(\ell-1)!} \sum_{k \in \{-1,1\}^\ell} P(k) \left( t + \langle x_k, (\mathbf{a} \circ \theta)^\circ \rangle \right)_+^{\ell-1}$$
    (여기서 $\ell$은 $\theta$의 0 이 아닌 성분의 개수, $P$는 곱, $(\cdot)_+$는 양의 부분 함수 등)

B. 정규화된 변형 (Regularized Variant)

• 문제: 초평면과의 교차 면적 계산은 수치적으로 불안정할 수 있습니다.
• 해결: 초평면 대신 초평면 주변의 얇은 슬랩 (slab, $\epsilon$-neighborhood) 과의 교차 부피를 계산하는 방식으로 변환합니다.
  • 슬랩의 부피는 $d$차원 부피로 계산되며, 이는 $\epsilon \to 0$일 때 원래 면적으로 수렴합니다.
  • 이 접근법은 수치적 안정성을 크게 향상시킵니다.

C. 볼록 인식 (Voxel-aware) 이산 라돈 변환

• 이미지 $F$를 $N^d$개의 볼록 (voxel) 로 구성된 조각별 상수 함수로 모델링합니다.
• 선형성 (linearity) 을 이용하여 전체 이미지의 라돈 변환을 각 볼록의 정확한 교차 면적 (또는 슬랩 부피) 의 가중합으로 계산합니다.
  $$R_\theta[f_F](t) = \sum_{n} F[n] \cdot A^{s/2\mathbf{e}}_\theta(t - s\langle n, \theta \rangle)$$

3. 주요 기여 (Key Contributions)

1. 명시적 수식: $d$차원 하이퍼큐브의 라돈 변환에 대한 닫힌 형식 (closed-form) 조각별 다항식을 최초로 제시했습니다.
2. 정규화 공식: 초평면 대신 슬랩 (slab) 과의 교차 부피를 계산하는 정규화된 라돈 변환 공식을 제안하여 수치적 안정성을 확보했습니다.
3. 효율적인 알고리즘: 위 수식을 기반으로 한 볼록 인식 (voxel-aware) 이산 라돈 변환을 구현하여, 기존 몬테카를로 방법보다 훨씬 빠르고 정확한 계산을 가능하게 했습니다.
4. 다양한 응용 검증: 3D 형태 매칭, 분류, Sliced Wasserstein 거리 및 바리센터 (barycenter) 계산 등 다양한 응용 분야에서 성능을 입증했습니다.

4. 실험 결과 (Results)

A. 3D 형태 매칭 및 분류 (ModelNet10 데이터셋)

• 데이터: Princeton 의 ModelNet10 데이터셋 (욕조, 침대, 의자 등 10 개 클래스) 사용.
• 방법 1: 라돈 형태 매칭 (Radon Shape Matching):
  • 기존 Trace Transform 기반 특징 추출기를 적용.
  • 결과: 3 클래스 (욕조, 의자, 서랍장) 분류에서 71% 정확도 달성 (무작위 추측 33% 대비 우수). 전체 10 클래스에서는 36% 정확도.
• 방법 2: 정규화된 라돈 누적 분포 변환 (NR-CDT):
  • 아핀 변환 (Affine transformation) 에 불변하는 특징을 추출.
  • 결과: 3 클래스 분류에서 93% 이상의 높은 정확도 달성. 10 클래스 전체 데이터셋에서도 47% 정확도로 기존 방법 (36%) 보다 우수.
  • 아핀 변환 테스트: 무작위 아핀 변환이 적용된 객체 분류에서 NR-CDT 는 **99%**의 거의 완벽한 분류 성능을 보인 반면, 기존 라돈 형태 매칭은 42% 에 그쳤습니다. 이는 이론적 불변성 (Theorem 17) 을 잘 반영합니다.

B. Sliced Wasserstein 거리 및 바리센터

• 목적: 경험적 측정 (empirical measure) 을 큐브의 혼합으로 근사하거나, 두 확률 분포의 Sliced Wasserstein 바리센터를 계산.
• 결과: 제안된 라돈 변환을 사용하여 2D 및 3D 에서 클러스터링 및 바리센터 계산이 성공적으로 수행되었으며, 계산된 분포가 목표 분포의 주요 특성을 잘 재현함을 확인했습니다.

C. 계산 효율성 비교 (몬테카를로 vs 제안 방법)

• 4 차원 (d=4) 실험:
  • 제안 방법: 128 개의 각도와 128 개의 반지름에 대한 계산이 1 초 미만 소요.
  • 몬테카를로 방법: 1 개의 각도에 대해 1% 미만의 오차를 얻기 위해 약 5 초 소요 (샘플 수 $N=2^{24}$ 필요).
  • 결론: 제안된 명시적 수식은 고차원 및 고해상도 환경에서 몬테카를로 적분보다 압도적으로 빠르고 정확합니다.

5. 의의 및 결론 (Significance)

이 논문은 고차원 기하학적 데이터 처리를 위한 라돈 변환의 근본적인 한계를 극복했습니다.

1. 정확성: 단순한 근사가 아닌, 볼록 데이터에 대한 수학적으로 정확한 라돈 변환을 제공합니다.
2. 효율성: 고차원 공간에서도 몬테카를로 시뮬레이션 없이 실시간에 가까운 속도로 계산을 가능하게 하여, 고차원 데이터 분석 (예: 4D 이상) 에 적용 가능한 새로운 가능성을 열었습니다.
3. 응용성: 의료 영상, 객체 인식, 최적 수송 문제 등 다양한 분야에서 더 정밀하고 안정적인 알고리즘의 기반이 될 수 있습니다.

요약하자면, 이 연구는 기하학적 교차 면적 계산의 수학적 난제를 해결하고, 이를 실용적이고 효율적인 알고리즘으로 구현하여 컴퓨터 비전 및 수리 모델링 분야의 성능을 획기적으로 향상시켰다는 점에서 큰 의의가 있습니다.