The Mean of Multi-Object Trajectories

1. 문제 정의 (Problem Definition)

• 배경: 다중 객체 추정 (Multi-object estimation) 은 노이즈가 포함된 센서 측정값으로부터 알려지지 않고 시간에 따라 변하는 개수의 객체들의 궤적을 추정하는 작업입니다.
• 핵심 문제: 기존 통계학에서 '평균 (Mean)'은 데이터 포인트의 합을 개수로 나눈 값으로 정의되지만, **궤적 (Trajectories)**이나 **다중 객체 궤적 (Multi-object trajectories)**의 경우 이 정의가 적용되지 않습니다.
  • 궤적은 길이가 다르고 (fragmented), 시작과 종료 시점이 다르며, 객체의 수 (cardinality) 가 변할 수 있기 때문에 단순한 덧셈 연산이 정의되지 않습니다.
  • 기존 분산 다중 객체 추적 (Distributed Multi-Object Tracking) 기술들은 주로 밀도 함수 (density) 의 평균이나 트랙 간 일치 (Track-to-Track) 를 기반으로 하지만, 궤적 자체의 기하학적 평균을 구하는 체계적인 방법론은 부재했습니다.
• 목표: 다양한 센서 노드에서 생성된 다중 객체 궤적들의 '평균 궤적'과 '평균 다중 객체 궤적'을 수학적으로 정의하고, 이를 효율적으로 계산하는 알고리즘을 개발하여 분산 추적 시스템에서의 합의 (Consensus) 를 달성하는 것입니다.

2. 방법론 (Methodology)

이 논문은 프레셰 평균 (Fréchet Mean) 개념과 최적 서브 패턴 할당 (OSPA, Optimal Sub-Pattern Assignment) 기반 거리 측정을 결합하여 문제를 해결합니다.

가. 수학적 형식화 (Formulation)

• 프레셰 평균 (Fréchet Mean): 유클리드 공간의 산술 평균을 임의의 거리 공간 (Metric Space) 으로 확장한 개념입니다. 입력 궤적들과의 거리 제곱합 (또는 거리 합) 을 최소화하는 궤적을 '평균 궤적'으로 정의합니다.
  • $\hat{v} = \arg \min_{u} \sum_{n} d(u, v^{(n)})$
• 거리 측정 (Metrics):
  • 궤적 거리: OSPA 기반의 궤적 거리 ($d_T$) 를 사용하여, 궤적 간의 상태 오차와 존재/부재 (cardinality) 오차를 동시에 고려합니다.
  • 다중 객체 궤적 거리: OSPA(2) 메트릭을 사용하여, 다중 객체 궤적 집합 간의 거리를 정의합니다. 이는 개별 궤적 간의 매칭 (assignment) 과 개체 수 차이에 대한 페널티를 포함합니다.

나. 계산 알고리즘 (Algorithms)

두 가지 주요 알고리즘을 제안하여 평균 궤적을 계산합니다.

1. 탐욕적 탐색 (Greedy Search):

   • 원리: 궤적의 존재 여부 (Existence history, $\gamma$) 와 상태 (States, $x$) 를 분리하여 최적화 문제를 변환합니다.
   • 과정:
     • 초기화: 모든 입력 궤적의 존재 구간을 합집합하여 초기 궤적 생성.
     • 반복: 각 시간 단계 $k$에서 궤적의 존재 여부 ($\gamma_k$) 를 0 또는 1 로 변경하여 비용 함수가 감소하는지 확인.
     • 상태 계산: 존재하는 시간 단계에서 입력 궤적들의 상태에 대한 가중 평균 (또는 중앙값) 을 계산하여 평균 궤적의 상태를 결정.
   • 특징: 온라인 적용에 적합하며 계산 비용이 매우 낮음.

2. 기브스 샘플링 (Gibbs Sampling):

   • 원리: 확률적 최적화 기법으로, 비용 함수의 최소값에 해당하는 분포에서 샘플을 추출하여 전역 최적해 (Global Optimum) 에 수렴하도록 설계.
   • 도전 과제: 궤적 집합의 순열 (Permutation) 공간에서 샘플링하는 것은 복잡함.
   • 해결: 반복 삽입 (Repeated Insertion) 기법을 사용하여 순열 벡터를 효율적으로 샘플링하는 변환 (Reparameterization) 을 도입.
   • 특징: 탐욕적 탐색보다 계산 비용이 높지만, 전역 최적해에 더 가까운 결과를 제공하며 수렴성이 이론적으로 보장됨.

3. 주요 기여 (Key Contributions)

1. 평균 궤적 및 평균 다중 객체 궤적의 정의: OSPA 기반 거리 측정을 사용하여 궤적과 다중 객체 궤적에 대한 프레셰 평균을 최초로 수학적으로 정립함.
2. 효율적인 계산 알고리즘 개발:
   • 탐욕적 탐색 (Greedy Search) 기반 알고리즘을 통해 실시간 적용 가능한 고속 계산 방법 제시.
   • 기브스 샘플링 기반 알고리즘을 통해 근사 최적해 (Near-optimal solution) 를 제공하는 정밀 계산 방법 제시.
3. 분산 다중 객체 추적에서의 합의 (Consensus) 달성: 제안된 평균 기법이 분산 네트워크 환경에서 노드 간 정보 융합 (Fusion) 을 위한 합의 메커니즘으로 작용함을 증명.

4. 실험 결과 (Experimental Results)

• 실험 설정:
  • 20 개의 서로 다른 길이를 가진 실제 궤적 (Ground Truth) 을 시뮬레이션.
  • 8 개의 이종 센서 노드 (Range-Rate-Bearing, Bearing-Range, Position 등) 가 서로 다른 추적 필터 (TO-MHT, LMB, GLMB) 를 사용하여 불완전한 궤적 추정치를 생성.
  • 제안된 방법 (FM) 과 기존 방법 (DBSCAN-T, Track Consensus - TC) 을 비교.
• 성능 지표: OSPA(2) 메트릭 (위치 오차, 개체 수 오차, 궤적 분열/연결 오류를 종합 평가).
• 결과 분석:
  • 정확도: 제안된 FM (Fréchet Mean) 기반 합의 알고리즘이 DBSCAN-T 와 TC 보다 OSPA(2) 오차를 획기적으로 감소시킴 (약 1012m vs 3849m).
  • 특징:
    • FM 은 배치 (Batch) 기반 (다중 스캔) 처리이므로 궤적의 시작/종료 시점과 분열 (Fragmentation) 문제를 효과적으로 해결.
    • 기존 TC 는 궤적 전환 (Track Switching) 에 취약하고, DBSCAN-T 는 궤적 시작/종료 지연 및 단일 클러스터 생성으로 인한 오차가 큼.
  • 효율성:
    • 탐욕적 탐색 (Greedy) 은 기브스 샘플링 (Gibbs) 과 거의 유사한 정확도를 유지하면서 실행 시간이 수백 배 빠름 (약 20~150 초 vs 1000 초 이상).
    • 1 차 프레셰 평균 (FM(1), 중앙값 기반) 이 2 차 (FM(2), 평균값 기반) 보다 잡음에 더 강건하여 성능이 약간 우수함.

5. 의의 및 결론 (Significance and Conclusion)

• 이론적 의의: 다중 객체 추정 분야에서 '평균'이라는 개념을 궤적과 다중 객체 집합에 대해 엄밀하게 정의하고, 이를 계산 가능한 알고리즘으로 구현했다는 점에서 중요한 이정표입니다.
• 실용적 의의:
  • 저비용 센서 네트워크와 같은 대규모 분산 시스템에서 노드 간 정보 융합을 위한 강력한 도구로 활용 가능.
  • 제안된 탐욕적 탐색 알고리즘은 실시간 분산 추적 시스템에 적용하기에 충분히 빠르면서도 기존 최첨단 기술 (SOTA) 보다 월등히 높은 정확도를 제공합니다.
  • 불확실성 (Uncertainty) 이 포함된 궤적 (확률 분포) 에 대해서도 적용 가능함을 시연 (Jeffrey's Divergence 기반).
• 향후 전망: 시야각이 불명확하거나 공통되지 않은 (Non-common FOV) 복잡한 추적 시나리오로 확장할 수 있는 잠재력을 가지고 있습니다.

요약하자면, 이 논문은 다중 객체 궤적의 평균을 정의하고 계산하는 새로운 프레임워크를 제시하여, 분산 추적 시스템의 정확도와 효율성을 비약적으로 향상시켰습니다.