개요

레이더 시스템에서 탐지된 물체의 위치를 정확하게 추적하기 위해서는 수집된 연속적인 측정 데이터를 바탕으로 물체의 궤적을 추정하고, 각 측정을 특정 물체의 궤적과 연관시키는 과정이 필요하다. 이와 같은 데이터 연관 및 추적 알고리즘은 다중 물체 추적(Multiple Target Tracking, MTT) 문제의 핵심이다. MTT는 주로 군사, 항공 교통 관제, 자율 주행 등에서 중요하게 다뤄지며, 그 핵심은 다음과 같이 정리할 수 있다:

  1. 데이터 연관 (Data Association): 새로운 측정값을 기존의 추적 궤적에 연관시키는 과정이다.
  2. 추적 필터링 (Tracking Filtering): 기존의 추적 궤적을 업데이트하거나 새로운 궤적을 생성하여 물체의 움직임을 추정하는 과정이다.

이 두 과정은 상호 의존적인 관계를 가지며, 성공적인 추적 시스템의 성능은 이 두 과정을 어떻게 설계하고 결합하느냐에 달려 있다.

데이터 연관의 기본 개념

데이터 연관은 연속된 시간 프레임에서 수집된 측정값을 이용해 어떤 측정값이 어떤 물체에 해당하는지 결정하는 문제이다. 데이터 연관 알고리즘은 수집된 측정값이 다른 물체로부터 혼동되지 않도록 보장하는 것을 목표로 한다. 특히, 다중 물체가 근접하거나 빠르게 이동하는 상황에서는 이 문제가 매우 복잡해질 수 있다.

레이더 시스템에서는 일반적으로 측정값이 물체의 위치와 속도에 대한 정보를 제공한다. 이를 수학적으로 다음과 같이 표현할 수 있다:

\mathbf{z}_k = [x_k, y_k, \dot{x}_k, \dot{y}_k]^T

여기서, \mathbf{z}_kk-번째 측정값을 나타내며, x_k, y_k는 위치, \dot{x}_k, \dot{y}_k는 속도를 의미한다.

연관 가설의 구성

데이터 연관 문제는 특정한 시간 k에서 측정값 \mathbf{z}_k가 어느 물체 j에 속하는지 결정하는 것이다. 이를 위해 여러 가지 연관 가설이 존재하며, 주로 다음과 같은 세 가지 방법이 사용된다:

  1. 확률적 데이터 연관 (Probabilistic Data Association, PDA): 확률론적 접근법을 사용하여 각 측정값이 특정 추적 궤적에 속할 확률을 계산한다. 이러한 방법은 노이즈가 존재하거나 다수의 물체가 근접해 있는 상황에서도 적절한 추적 성능을 보장할 수 있다.

  2. 전역 데이터 연관 (Global Nearest Neighbor, GNN): 전역 최적화 기법을 통해 특정 시간에서의 모든 측정값과 모든 궤적 간의 연관을 한 번에 해결한다. 헝가리안 알고리즘과 같은 최적화 기법이 주로 사용된다.

  3. 다중 가설 추적 (Multiple Hypothesis Tracking, MHT): 모든 가능한 연관 가설을 생성하고, 각 가설에 대한 확률을 추정하여 가장 가능성이 높은 가설을 선택하는 방법이다. 이 방법은 매우 복잡하지만, 다중 물체 간의 복잡한 연관 문제를 해결하는 데 유리하다.

확률적 데이터 연관의 수학적 모델

확률적 데이터 연관은 측정값 \mathbf{z}_k와 추적 궤적 \mathbf{t}_j 간의 연관 확률 P(\mathbf{z}_k \mid \mathbf{t}_j)를 계산하는 것이다. 이때, 다음과 같은 가우시안 분포를 가정한다:

P(\mathbf{z}_k \mid \mathbf{t}_j) = \frac{1}{(2\pi)^{n/2}|\mathbf{S}_j|^{1/2}} \exp\left(-\frac{1}{2} (\mathbf{z}_k - \hat{\mathbf{z}}_j)^T \mathbf{S}_j^{-1} (\mathbf{z}_k - \hat{\mathbf{z}}_j)\right)

여기서: - \hat{\mathbf{z}}_j는 추정된 측정값, - \mathbf{S}_j는 오차 공분산 행렬, - n은 측정값의 차원이다.

전역 데이터 연관의 최적화 문제

GNN에서는 헝가리안 알고리즘을 통해 최적의 연관을 찾는다. 여기서 비용 행렬 \mathbf{C}는 각 측정값과 각 궤적 간의 연관 비용을 나타내며, 최적화 문제는 다음과 같이 표현된다:

\min \sum_{i=1}^{M} \sum_{j=1}^{N} c_{ij} x_{ij}

여기서: - c_{ij}는 측정값 i와 궤적 j 간의 연관 비용, - x_{ij}는 이진 변수로, x_{ij} = 1이면 측정값 i가 궤적 j와 연관됨을 의미한다.

이 문제는 전형적인 선형 할당 문제로서, 효율적인 알고리즘을 통해 해결할 수 있다.

다중 가설 추적 (Multiple Hypothesis Tracking, MHT)

MHT는 데이터 연관 문제를 해결하는 매우 강력한 방법으로, 모든 가능한 연관 가설을 생성하고 이를 바탕으로 시간에 따라 확률적으로 추적 궤적을 관리한다. MHT는 다음과 같은 과정으로 작동한다:

  1. 가설 생성: 새롭게 수집된 측정값을 바탕으로 각 궤적에 대해 가능한 모든 연관 가설을 생성한다. 예를 들어, 하나의 새로운 측정값은 기존 궤적 중 하나에 연관되거나, 새로운 궤적을 형성하는 가설을 만들 수 있다.

  2. 가설 평가: 생성된 각 가설에 대해 확률을 계산하여 가장 가능성이 높은 가설을 선택하거나, 모든 가설을 일정 기간 유지한 후 시간에 따른 확률 변화에 따라 가설을 제거한다.

  3. 가설 갱신: 시간 프레임이 진행됨에 따라 이전 시간 프레임의 가설을 확장하고, 새로운 측정값을 바탕으로 기존 가설을 갱신하여 추적을 지속한다.

수학적 모델

MHT의 수학적 모델을 설명하기 위해 가설 집합 \mathcal{H}을 정의하자. 이 집합은 시간 k에서의 가능한 가설을 포함하며, 각 가설 \mathcal{H}_j는 특정 궤적에 대한 일련의 연관 정보로 구성된다. 각 가설의 확률 P(\mathcal{H}_j \mid \mathbf{Z}_{1:k})는 베이즈 정리에 의해 다음과 같이 갱신된다:

P(\mathcal{H}_j \mid \mathbf{Z}_{1:k}) = \frac{P(\mathbf{z}_k \mid \mathcal{H}_j) P(\mathcal{H}_j \mid \mathbf{Z}_{1:k-1})}{\sum_{i} P(\mathbf{z}_k \mid \mathcal{H}_i) P(\mathcal{H}_i \mid \mathbf{Z}_{1:k-1})}

여기서: - \mathbf{Z}_{1:k}는 시간 1부터 k까지의 모든 측정값을 의미하며, - P(\mathbf{z}_k \mid \mathcal{H}_j)는 측정값 \mathbf{z}_k가 가설 \mathcal{H}_j에 의해 설명될 확률이다.

MHT는 모든 가설을 추적하고 유지해야 하므로, 가설의 수가 기하급수적으로 증가하는 문제점이 있다. 이를 해결하기 위해 특정 가설의 확률이 낮아지면 가설을 제거하거나, 확률이 유사한 가설을 병합하는 방법을 사용한다.

연관 알고리즘의 성능 평가

연관 알고리즘의 성능은 여러 지표를 통해 평가할 수 있다. 특히, 다중 물체 추적에서는 다음과 같은 평가 지표가 사용된다:

  1. 추적 성공률 (Tracking Success Rate): 실제 물체의 궤적과 추정된 궤적이 얼마나 잘 일치하는지를 평가하는 지표이다. 추적 성공률이 높을수록 연관 알고리즘이 정확하게 동작한다고 할 수 있다.

  2. 오류 비율 (Error Rate): 잘못된 연관으로 인해 발생하는 오류의 빈도를 측정한다. 이는 잘못된 측정값을 기존 궤적에 연관시키거나, 새로운 궤적을 생성하지 못해 발생하는 문제를 포함한다.

  3. 실시간 처리 성능: 연관 알고리즘이 실제 시스템에서 실시간으로 처리 가능한지 여부를 평가한다. 특히, 다중 물체가 존재하는 상황에서 연관 가설이 기하급수적으로 증가하는 MHT와 같은 알고리즘은 실시간 처리 성능이 중요한 요소로 작용한다.

칼만 필터를 활용한 추적 필터링

데이터 연관 후에는 각 궤적을 업데이트하기 위해 필터링을 수행해야 한다. 가장 일반적인 방법은 칼만 필터(Kalman Filter)와 확장 칼만 필터(Extended Kalman Filter, EKF)를 활용하는 것이다. 칼만 필터는 다음과 같은 두 가지 단계로 구성된다:

  1. 예측 단계 (Prediction Step): 이전 상태 \mathbf{x}_{k-1}와 시스템 모델을 사용하여 현재 시간 k에서의 상태를 예측한다.
\mathbf{x}_{k|k-1} = \mathbf{F} \mathbf{x}_{k-1} + \mathbf{u}_{k-1}
\mathbf{P}_{k|k-1} = \mathbf{F} \mathbf{P}_{k-1} \mathbf{F}^T + \mathbf{Q}

여기서: - \mathbf{x}_{k|k-1}는 시간 k에서의 예측된 상태 벡터, - \mathbf{F}는 상태 전이 행렬, - \mathbf{u}_{k-1}는 제어 입력 벡터, - \mathbf{P}_{k|k-1}는 상태 오차 공분산 행렬의 예측 값, - \mathbf{Q}는 시스템 노이즈 공분산 행렬이다.

  1. 갱신 단계 (Update Step): 새로운 측정값 \mathbf{z}_k를 바탕으로 상태를 업데이트한다.
\mathbf{K}_k = \mathbf{P}_{k|k-1} \mathbf{H}^T (\mathbf{H} \mathbf{P}_{k|k-1} \mathbf{H}^T + \mathbf{R})^{-1}
\mathbf{x}_k = \mathbf{x}_{k|k-1} + \mathbf{K}_k (\mathbf{z}_k - \mathbf{H} \mathbf{x}_{k|k-1})
\mathbf{P}_k = (\mathbf{I} - \mathbf{K}_k \mathbf{H}) \mathbf{P}_{k|k-1}

여기서: - \mathbf{K}_k는 칼만 이득(Kalman Gain), - \mathbf{H}는 관측 행렬, - \mathbf{R}는 측정 노이즈 공분산 행렬이다.

칼만 필터 확장의 필요성: 비선형 시스템의 처리

기본적인 칼만 필터는 시스템의 동역학과 관측 모델이 선형인 경우에만 최적의 성능을 보장한다. 그러나 실제 레이더 데이터 처리에서 물체의 운동은 비선형적인 경우가 많으며, 특히 자율 주행 차량, 항공기, 미사일 등의 비행 궤적을 추적하는 경우 비선형 모델을 고려해야 한다. 이를 해결하기 위해 확장 칼만 필터 (Extended Kalman Filter, EKF)비선형 필터 (Unscented Kalman Filter, UKF)와 같은 방법이 사용된다.

확장 칼만 필터 (Extended Kalman Filter, EKF)

EKF는 기본적인 칼만 필터를 비선형 시스템에 적용할 수 있도록 확장한 필터링 기법이다. EKF에서는 시스템 모델과 관측 모델을 비선형 함수로 가정하며, 이 함수들을 선형화하여 필터링을 수행한다.

  1. 비선형 상태 및 관측 모델: 시스템 모델은 다음과 같은 비선형 함수로 표현된다:
\mathbf{x}_k = \mathbf{f}(\mathbf{x}_{k-1}, \mathbf{u}_{k-1}) + \mathbf{w}_{k-1}
\mathbf{z}_k = \mathbf{h}(\mathbf{x}_k) + \mathbf{v}_k

여기서: - \mathbf{f}(\cdot)는 비선형 상태 전이 함수, - \mathbf{h}(\cdot)는 비선형 관측 함수, - \mathbf{w}_{k-1}\mathbf{v}_k는 각각 프로세스 및 측정 노이즈이다.

  1. 선형화: 예측과 갱신 단계에서 비선형 함수를 테일러 급수를 이용해 선형화한다. 이때, 선형화는 함수의 야코비 행렬 (Jacobian Matrix)을 사용한다.

예측 단계:

\mathbf{F}_k = \frac{\partial \mathbf{f}}{\partial \mathbf{x}} \bigg|_{\mathbf{x} = \mathbf{x}_{k-1}}

갱신 단계:

\mathbf{H}_k = \frac{\partial \mathbf{h}}{\partial \mathbf{x}} \bigg|_{\mathbf{x} = \mathbf{x}_{k|k-1}}
  1. EKF 예측 및 갱신 수식: EKF의 예측 및 갱신 수식은 칼만 필터와 유사하지만, 선형화된 모델을 사용한다.

예측 단계:

\mathbf{x}_{k|k-1} = \mathbf{f}(\mathbf{x}_{k-1}, \mathbf{u}_{k-1})
\mathbf{P}_{k|k-1} = \mathbf{F}_k \mathbf{P}_{k-1} \mathbf{F}_k^T + \mathbf{Q}

갱신 단계:

\mathbf{K}_k = \mathbf{P}_{k|k-1} \mathbf{H}_k^T (\mathbf{H}_k \mathbf{P}_{k|k-1} \mathbf{H}_k^T + \mathbf{R})^{-1}
\mathbf{x}_k = \mathbf{x}_{k|k-1} + \mathbf{K}_k (\mathbf{z}_k - \mathbf{h}(\mathbf{x}_{k|k-1}))
\mathbf{P}_k = (\mathbf{I} - \mathbf{K}_k \mathbf{H}_k) \mathbf{P}_{k|k-1}

비선형 필터 (Unscented Kalman Filter, UKF)

UKF는 비선형 필터링에서 선형화를 피하고, 확률 분포를 비선형 변환을 통해 직접 처리하는 방식으로 작동한다. 이는 EKF의 한계, 즉 비선형 함수의 잘못된 선형화로 인한 부정확한 결과를 보완하는 방법이다.

  1. 시그마 포인트 (Sigma Points): UKF는 상태의 확률 분포를 시그마 포인트라고 불리는 특정한 점 집합으로 근사한다. 시그마 포인트는 상태의 평균과 공분산을 바탕으로 선정되며, 이를 통해 비선형 변환을 직접 적용한다.

  2. 시그마 포인트의 변환: 각 시그마 포인트를 비선형 함수 \mathbf{f}에 통과시키고, 결과를 바탕으로 새로운 평균과 공분산을 계산한다.

시그마 포인트 변환:

\mathbf{X}_{k|k-1} = \mathbf{f}(\mathbf{X}_{k-1})
  1. UKF 수식: UKF의 예측 및 갱신 단계는 각 시그마 포인트에 대해 별도로 계산된 평균과 공분산을 사용한다. 이를 통해 비선형성의 영향을 직접 반영할 수 있다.

레이더 시스템에서의 데이터 연관 및 추적 적용 예제

실제 레이더 시스템에서 추적 알고리즘은 다음과 같은 시나리오에 적용될 수 있다:

  1. 다중 비행체 추적: 공항 주변의 다수의 항공기를 추적할 때, 레이더 시스템은 각 항공기의 위치를 지속적으로 감시하고, 각 측정값을 특정 항공기에 연관시키며 궤적을 관리해야 한다. 항공기의 이동 패턴이 복잡하고 다양한 방향으로 이동할 수 있어, MHT와 같은 고급 연관 알고리즘이 필요할 수 있다.

  2. 자율 주행 차량의 물체 추적: 자율 주행 차량은 주변 환경의 차량, 보행자, 장애물 등을 실시간으로 추적해야 한다. 이 경우, EKF나 UKF와 같은 비선형 필터링이 자주 사용되며, 각 물체를 정확히 추적하기 위해 PDA와 같은 확률적 데이터 연관 기법이 적용될 수 있다.

  3. 군사적 응용: 군사 레이더 시스템에서는 미사일 및 기타 비행 물체를 추적해야 하며, 특히 여러 물체가 교차하거나 혼잡한 환경에서 비행하는 경우 정확한 추적이 요구된다. 이때 MHT는 매우 복잡한 데이터 연관 시나리오를 처리할 수 있어 활용 가치가 높다.