DeepSORT

Object Tracking의 대표적인 논문 중 하나인 DeepSORT에 대해서 다루어보려고 한다. 

 

논문 링크: https://arxiv.org/pdf/1703.07402

 

0. SORT(Simple Online and Realtime Tracking)

---

 

먼저 기반이되는 SORT에 대해서 간단하게 알아보자. SORT는 복수 객체 추적(MOT: Multiple Object Tracking)을 실시간으로 구현하기 위하여 설계된 시스템이다. 프레임마다 등장하는 객체 탐지 결과인 bounding box를 입력으로 받아, 각 객체에 일관된 ID를 부여하여 추적하는 방식을 사용한다. SORT의 구조는 크게 3가지로 볼 수 있다

 

1. 객체 탐지 (Detection)
   • 객체는 매 프레임마다 외부 Classifier(예: Faster R-CNN)로 탐지됨
   • 이때 얻은 bounding box는 (x, y, w, h) 형태로 표현됨
   
   
2. 상태 추정 (State Estimation)  
   • Kalman Filter를 통해 객체의 다음 위치를 예측한다.
   • 위치, 방향, 속도 등을 기반으로 다음 프레임의 bounding box 예측
   
   
3. 데이터 매칭 (Data Association)
   • 예측한 위치와 실제 탐지된 객체 간 매칭을 수행한다.
   • IoU를 기반으로 각 track과 detection의 유사도를 계산한다.
   • 유사도 기반 매칭은 Hungarian Algorithm을 사용하여 해결하였다.

객체 탐지 후 Tracking 과정에서 SORT는 큰 약점을 가진다. 위치 기반으로만 추적하기 때문에 같은 위치에 다른 객체가 오면 구분하지 못한다거나 다른 ID로 인식(ID switch)되는 문제가 생기고, Kalman Filter는 말 그대로 정말 필터이기 때문에 선형성에서 벗어나는 움직임을 잡아내는데 한계를 지닐 수 밖에 없다.

 

 

1. 서론

---

객체 탐지(Object Detection)의 발전과 함께, tracking-by-detection 방식이 다중 객체 추적(MOT)의 주된 패러다임이 되었다. 이 방식에서는, 전체 비디오 시퀀스를 한꺼번에 처리하면서 객체의 이동 경로(trajectory)를 전역적으로 최적화(global optimization)하는 방식으로 추적을 수행한다. flow network 기반 모델이나 probabilitistic graphical models 등이 대표적이다. 그러나 이런 방식은 batch processing을 요구하기 떄문에, 매 프레임마다 객체 ID가 바로 필요한 실시간(online) 시나리오에는 적합하지 않다.

 

보다 전통적인 방식으로는 MHT(Multiple Hypothesis Tracking)과 JPDAF(Joint Prababilistic Data Association Filter)가 있다. 이 방법들은 프레임 단위로 데이터를 결합한다(data association).

• JPDAF : 각 측정값이 특정 tracking 대상에 속할 확률(association liklihood)을 고려하여, 가중 평균값을 구해 단일 상태(state)를 추정한다.
• MHT : 가능한 모든 상태(state)에 대한 추정치를 유지하면서 추적핮만, 계산량 문제 때문에 pruning이 반드시 적용되어야 한다.

이러한 방법들은 최근 tracking-by-detection 방법에서도 다시 조명되고있으며, 좋은 성과들을 보였다. 하지만 이처럼 좋은 성과를 얻기 위해서는 높은 계산량과 구현의 복잡도를 감수해야만 한다.

 

SORT는 그에 반해 훨씬 단순한 프레임워크를 가진다. 이미지 -> Kalman 필터링 -> Hungarian Algorithm -> bounding box IoU기준으로 데이터 연결 ~ 이처럼 간단한 방식이지만, 높은 프레임 속도에서 우수한 성능을 보인다. MOT challenge 데이터 셋과 최신 Object  Detector를 함께 사용한 SORT의 결과 기준으로 MHT보다 평균적으로 더 높은 성능을 보였다. 

 

SORT는 추적 정확도(tracking precision)와 정밀도(precision)면에서 전체적으로 좋은 성능을 보이지만, 앞서 언급한 것처럼 상대적으로 ID switch가 많이 발생한다는 단점이 있다. 이는 SORT에서 사용되는 matching 기준이, 상태 추정이 확실할 때만 정확히 작동하기 때문이다. 결과적으로 SORT는 정면을 바라보는 카메라에서 흔히 발생하는 가려짐(occlusion)문제 상황에서의 추적에 취약하다.

 

연구는 이를 해결하기 위해, 기존의 매칭 기준을 "움직임 정보(motion) + 외형 정보(appearance)"를 함께 활용하는 보다 정교한 매칭 기준으로 대체하였다. 세부적으로, 대규모 person re-Id 데이터셋으로 사람을 구분할 수 있도록 학습된 CNN 모델을 도입하였다. 

 

해당 네트워크의 도입을 통해, 누락(miss)이나 가려짐(occlusion) 상황에서도 ID를 안정적으로 유지할 수 있게 되었고, 동시에 구현도 가단 / 효율적으로 실시간 Online Tracking에도 적용 가능한 구조를 유지할 수 있었다. 

 

 

2. SORT with DEEP Association Metric

---

연구는 MHT와 다르게 가능한 모든 경우의 수를 유지하지 않고 가장 가능성이 높은 하나의 상태(state)만 추적하는 "single hypothesis" 방식을 체택하며, 이 방식은 재귀적인 Kalman 필터링과 프레임 단위의 data association 과정을 포함한다. 

 

Track Handling / State Estimation

Track Handling(추적 관리)와 Kalman 필터링 구조는 기존 SORT 논문의 방식과 대부분 동일하다. 연구는 다음과 같은 일반적인 Tracking 상황을 가정한다.

1. calibration(보정) 되지 않은 카메라
2. 카메라 자체의 움직임(ego-motion) 정보 없음

이러한 조건은 필터링 시스템에 도전 과제가 되지만, 최근의 MOT 벤치마크에서는 가장 일반적인 설정이다. 

 

따라서, 연구의 Tracking state은 8차원 벡터 (u, v, γ, h, ẋ, ẏ, γ̇, ḣ) 로 구성된다. 여기서 각 요소는 다음을 의미한다.

• u, v: 바운딩 박스 중심 좌표
• γ (감마): 종횡비(aspect ratio = width / height)
• h: 바운딩 박스의 높이
• ẋ, ẏ, γ̇, ḣ: 각 항목의 속도(프레임당 변화량)

연구는 정속도(constant velocity) 가정을 기반으로 한 표준 Kalman 필터를 사용한다. 또한 선형 관측 모델(linear observation model)을 적용하며, 이때 (u, v, γ, h) - 중심 좌표, 종횡비, 높이 를 상태의 직접적인 관측값으로 사용한다.

 

각 트랙 k에 대해서, 마지막으로 탐지와 매칭에 성공한 이후의 프레임 수 $a_k$를 카운팅한다. $a_k$는 kalman필터가 예측을 수행할 때마다 1씩 증가하며, 탐지와 매칭이 성공하면 0으로 초기화된다.  $a_k$는 해당  트랙이 얼마나 오래동안 관측되지 않았는지를 나타내느 ㄴ값이 된다. 만약에 어떤 트랙의 $a_k$가 미리 정의된 최대 유지 시간 $A_{\text{max}}$를 초과하면, 해당 트랙은 장면(scene)을 떠난 것으로 간주되어 삭제된다.  

 

기존 트랙과 매칭되지 않은 탐지 결과는 새로운 추정 트랙(track hypothesis)으로 생성된다. 이 트랙들은 처음 3프레임 동안은 "임시(tentative)" 상태로 간주된다. 해당 상태에서 프레임마다 탐지 / 매칭이 성공해야 한다. 만약 이 조건을 충족하지 못하면, 해당 트랙은 삭제된다.

 

Assignment Problem

Kalman 필터로 예측한 상태와 새로운 탐지한 결과를 매칭하는 일반적인 방법은, 할당 문제(assignment problem)를 구성하고 이를 Hugarian Algorithm을 통해 푸는 것이다. 연구에서는 문제의 설정 안에 모션 정보(motion imfo)와 외형정보(apearance info)를 두 가지 지표(metric)를 조합해서 통합하였다. 모션 정보를 반영하기 위해서, 연구는 예측된 Kalman 필터 예측 상태와 새로 탐지한 결과 사이의 Mahalanobis distance를 사용한다. 해당 값은 탐지 결과가 Kalman 필터의 예측 분포에서 얼만큼 떨어져 있는지를 나타낸다. 

Mahalanobis distance
$d^{(1)}(i, j) = (d_j - y_i)^T S_i^{-1} (d_j - y_i)$

• $d_j$ : j번째 탐지 결과
• $y_i$ : Kalman 필터가 예측한 트랙 i의 평균 위치
• $S_i$ : 예측한 위치의 공분산(오차분포)
• $S_i^{-1}$ : 공분산의 역행렬 → 오차를 보정하는 역할

Mahalanobis distance는 공분산 행렬(covariance matrix)을 이용해서, "신뢰도 높은 방향에 작은 페널티" / "신뢰도 낮은 방향에 큰 페널티" 를 준다. 불확실성이 클수록 거리의 값이 작게 계산되고 이는 예측이 부정확해질수록 탐지 범위가 넓어지는 것처럼 작동한다.

• Kalman Filter 신뢰가 높을 때 : 탐지 결과가 예측 위치에 정확히 가까워야 매칭이 된다.
• Kalman Filter 신뢰가 낮을 때 : 탐지 결과가 예측 위치에서 좀 멀어도 매칭이 가능하다.

또한 이 Mahalanobis distance를 이용하면, 거리를 theshold로 설정하여 가능성 낮은 매칭을 사전에 제거할 수 있다. 필터링 여부를 나타내는 지표는 $b^{(1)}_{i,j}$로 정의되고 다음과 같이 결정된다.

• $d^{(1)}(i, j)$  가 임계값 $t^{(1)}$ 이하 : $b^{(1)}_{i,j}$ = 1
• $d^{(1)}(i, j)$  가 임계값 $t^{(1)}$ 이상 : $b^{(1)}_{i,j}$ = 0

연구에서는 95% 신뢰 구간을 넘어가면 후보에서 제외하도록 설정하였다. 예측 상태값이 4차원 이므로, 해당 임계값  $t^{(1)}$ 은 9.4877 이 사용되었다.

 

Mahalanobis distance는 움직임(motion)의 불확실성이 낮을 때에는 적합한 매칭 지표이지만, Kalman 필터링으로 얻은 예측 분포가 객체 위치에 대한 대략적인 추정만 제공하기 때문에 문제가 발생할 수 있다. 특히, 카메라 움직임(ego-motion)을 고려하지 않은 상황에서 이미지 내에서 객체 위치가 급격하게 이동할 수 있어, 이때 mahanobis distance만으로는 가려짐(occulsion)상황으로 인식하고 신뢰할 수 있는 매칭을 기대하기 어렵다 (예: 객체 잠깐 사라짐 -> 탐지 안됨 -> 갑자기 다른 위치?). 따라서 연구에서는 매칭 문제에 두 번째 지표 "appearance"를 추가하였다. 구체적으로는 다음과 같이 동작한다.

1. 각 bounding box detection $d_j$에 대해,
   정규화된 appearance descriptor $r_j(‖r_j‖ = 1)$를 계산한다.
2. 각 트랙 $k$마다,
   과거 $L_k$ = 100개까지 appearance descriptor들을 저장하는 갤러리 $R_k$를 유지한다.
3. i(추적 중인 객체 id)와 j(탐지된 후보)사이의 appearance 거리는
   갤러리 안의 descriptor들과 descriptor $r_j$사이의 최초 코사인 거리(cosine distance)로 측정한다.

appearance distance ( = cosine distance)
$d^{(2)}(i, j) = \min\{ 1 - r_j^T r_k^{(i)} \;|\; r_k^{(i)} \in R_i \}$

• $r_j$: 탐지 j의 appearance descriptor
• $R_i$: 트랙 i의 과거 appearance descriptor 모음
  
  $d^{(2)}(i, j)$ : 트랙 i의 apprearance 기록 중 탐지된 j와 가장 유사한 것(코사인 거리)
  

Kalman 필터 예측만 사용하게 되면, 가려짐(occulusion)등으로 잠시 놓친뒤 다시 나타나더라도 "무엇인지", "누구인지" 모를 수 있다. 이를 위해 "외형이 얼마나 비슷한지"를 보는 appearance descriptor를 추가하여 보강한 것이다.  

 

appearance도 mahalanobis distance와 같이 threshold를 통해 유효 매칭을 필터링하는 과정을 거친다. threshold값은 별도의 학습 데이터셋에서 실험적으로 결정하였다. 실제 구현에서는 appearance descriptor를 계산하는데 pre-train된 CNN모델을 이용하였다.

 

위 두 가지 매칭 지표를 결합하면, 할당 문제(assignment problem)의 서로 다른 측면을 보완할 수 있다. mahalanobis ditance는 모션 정보를 기반으로 객체의 위치를 추정하는 정보를 제공하여 짧은 시간 내 예측(short-term prediction)에 특히 유리하며, cosine distance의 경우 외형 정보를 고려하기 때문에, 장기간 가려짐(long-term occulusion)이 발생한 이후 ID를 복원(recover)하는데 효과를 발휘할 수 있다. 연구에서는 이 두 매칭 지표를 weighted sum 방식으로 결합하였다. 

$c_{i,j} = \lambda d^{(1)}(i,j) + (1-\lambda) d^{(2)}(i,j)$

• $d^{(1)}(i,j)$: mahalanobis distance
• $d^{(2)}(i,j)$: appearance distance
• $\lambda$: 두 거리의 가중치를 조절하는 하이퍼파라미터(weight)

어떤 매칭이 유효(admissible)하다고 판단하려면, 두 distance의 필터링 조건을 만족해야 한다.

 

Matching Cascade

연구는 측정값(탐지 결과)과 트랙 간의 연결을 전역적으로 매칭(global assignment) 문제로 푸는 대신, 여러 subproblem들로 나누어 해결하는 "Cascade 방식"을 도입하였다. 

 

해당 방식을 설명하기 위해 다음 상황을 가정해보자.

• 어떤 객체가 오랜 시간 가려진 후(occlusion) 다시 등장하는 경우 :
  이때 Kalman 필터는 계속해서 예측을 수행하게 되는데, 해당 과정에서 위치의 불확실성(uncertainty)이 점점 증가한다. 그 결과, 예측된 상태의 분포가 더 퍼지게 되고, 관측값과의 매칭 가능성(observation likelyhood)이 덜 뚜렷해지게 된다(less picked). 예시로 좀 더 쉽게 설명해보자면 이전에는 "관측값이 딱 중앙 근처(2~3 픽셀)에 떨어졌을 때"만 높은 확률을 가졌다면, 지금은 20픽셀 넘도록 인정하게 된다는 것이다 -> 이러면 "다른 것도 이 트랙에 끼워 맞추기 쉬어짐"

직관적으로는, 예측이 불확실성과 탐지 범위가 커졌기 때문에 매칭 확률이 낮아질 것이라고 생각이 들 수 있다. 하지만 실제로는, 두 트랙이 하나의 탐지를 두고 경쟁할 때, 불확실성이 큰 트랙이 오히려 선택될 가능성이 높아진다. mahalanobis distance에서는 표준편차 기준의 거리로 계산되기 때문에, 분산이 클수록 거리 값이 작게 나오는 예상과는 반대의 상황이 나오게 된다. 이는 결과적으로 트랙이 자주 끊기게(fragmentation) 만들어 지속적인 tracking에 있어 불안정성을 야기하게 된다.

 

연구에서는 분포가 퍼질수록 매칭이 어려워져야 한다는 개념을 시스템에 반영하기 위해 더 자주 관측된 트랙에 우선순위를 부여하는 "Matching Cascade" 방식을 도입하였다.

▲ Listing 1

위의 Listing 1은 연구가 제안한 매칭 알고리즘의 개요를 보여준다. 입력으로는 다음 세 가지가 주어진다.

• 트랙의 인덱스 집합 $T$
• 탐지 결과의 인덱스 집합 $D$
• 최대 나이 제한 $A_{\text{max}}$ (오랫동안 관측 안 된 트랙을 위한 기준)

1~2번째 줄에서는 다음을 계산한다.

• 매칭 비용 행렬 $C = [c_{i,j}]$
• 유효한 매칭만을 나타내는 이진 행렬 $B = [b_{i,j}]$

그 후, 트랙의 age(마지막 탐지 이후 경과한 프레임 수) $n$에 따라 반복하며, 트랙의 age가 증가하는 순서대로 linear assignment 문제를 풀어간다.

• 6번째 줄에서는 최근 $n$프레임 동안 관측되지 않은 트랙들의 집합 $T_n$을 선택하고
• 7번째 줄에서는 이 $T_n$과 아직 매칭되지 않은 탐지들 $U$ 간의 매칭을 수행한다
• 8~9번째 줄에서는 매칭 결과와 남은 탐지 정보를 업데이트하고,
• 11번째 줄에서 최종 결과를 반환한다.

이 matching cascade 의 핵심은 최근에 관측된 트랙(age가 작은 트랙)이 매칭 우선권을 갖도록 설계되었다는 것이다. 이로써 분포의 퍼짐에 따른 신뢰도 차이를 매칭하는 순서로 반영할 수 있게 된다.

 

Deep Appearance Descriptor

DeepSORT은 추가적인 학습 없이 단순한 nearest neighbor 검색만으로 매칭을 수행하기 때문에, 성공적인 tracking을 위해서는 구별력이 뛰어난 feature embedding을 사전에 오프라인 학습해 두어야 한다. 이를 위해 연구는 대규모 person re-identification 데이터셋(1261명에 대한 110만장 이상의 이미지)을 활용해 학습된 CNN 모델을 활용한다. 해당 데이터는 사람을 tracking 하는 상황에서 deep metric learning이 적용하기에 적합하게 만들어준다.

• deep metric learning : "metric learning"은 두 샘플간의 metric("거리")이 의미를 갖도록 임베딩을 학습하는 것. 학습의 방식에 deep learning을 사용하면 "deep metric learning"이 되는 것이다. 예로 설명해보자면 
  
  • 같은 클래스(예: 같은 사람) → 벡터 공간에서 가까이 위치
  • 다른 클래스(예: 다른 사람) → 멀리 떨어지게
  위와 같은 구조로 학습하는 것을 말한다. 단순한 분류와는 달리, 유사도 기반 추론을 가능하게 해준다.

▲ Table 1.

 

Table 1.은 학습한 CNN의 구조를 요약한 것이다. 간단히 말하자면, 연구에서는 두 개의 Conv 레이어 뒤에 여섯 개의 residual block이 붙은 Wide residual network를 사용한다. 마지막의 dense 10 레이어에서 128 차원의 전역 특징 벡터를 생성하고, 이어지는 batch / $\ell_2$ norm을 통해 해당 벡터를 unit hypersphere(구면 좌표계 같은거라고 보면 될 듯) 위로 투영시켜 cosine distance 기반 ㅐ칭에 적합한 형식으로 만든다. 네트워크는 총 2,800,864개의 파라미터를 가지고 있으며, 32개의 bounding box를 처리하는데 약 30ms 정도 걸린다 (모바일 GTX 1050 기준). 따라서, 상용되는 GPU가 있다면 해당 네트워크는 실시간 온라인 추적에도 충분히 활용될 수 있다.

 

 

3. Experiments

---

연구는 DeepSORT의 성능을 MOT16 benchmark에서 평가하였다. 이 벤치마크는 총 7개의 난이도 높은 테스트로 구성되어 있으며, 카메라가 움직이는 정면 구도 부터 위에서 내려다보는 CCTV 스타일의 구도까지 포함한다. DeepSORT에서는 Yu et al. 의 연구(“Poi:
Multiple object tracking with high performance detection and appearance feature”)가 제공한 탐지 결과를 입력으로 사용하였다 (Yu et al. 연구는 높은 성능을 위해 공개/비공개 데이터셋을 조합하여 Faster R-CNN을 학습시켰다). 공정한 비교를 위해서, 연구는 기존의 SORT 알고리즘도 동일한 탐지 결과를 입력으로 사용해 다시 실험을 진행하였다.

 

테스트 시퀀스에 대한 평가는 다음의 설정을 기반으로 진행되었다.

• $\lambda$ = 0 (appearance 정보만 사용한 매칭)
  - 모션 정보는 무시하고 apearance 정보(cosine distance)만으로 결정하는 것
  - 실험 상 카메라 움직이는 경우가 많아 Kalman 필터 예측이 부정활 것이라 본 듯 ?
• $A_{\text{max}}$ = 30 (트랙 유지 최대 시간)
  - 탐지와 연결되지 않은 트랙을 최대 30 프레임까지 유지하는 것

또한 Yu et al. 연구와 동일하게, 탐지 결과는 confidence score 0.3 이상만 사용하였다. 그 외 파라미터들은 벤치마크에서 제공하는 별도의 학습 시쿼스에서 찾았다.

 

성능의 평가는 다음과 같은 metric을 기준으로 진행되었다.

metric	설명	높을 수록 좋음?
MOTA(Multi-Object Tracking Accuracy)	종합 정확도 (ID, FP, FN 포함)	✅
MOTP(Multi-Object Tracking Precision)	박스 위치 정확도 (IoU 기반)	✅
MT(Mostly Tracked)	전체 생애의 80% 이상 추적된 객체 비율	✅
ML(Mostly Lost)	전체 생애의 20% 이하만 추적된 객체 비율	❌
ID(ID Switch)	ID가 바뀐 횟수	❌
FM(Fragmentation)	트랙이 끊긴 횟수	❌
FP(False Positive)	잘못 탐지된 수	❌
FN(False Negative)	놓친 탐지 수	❌

 

 

이제 실험 결과를 Table 2.를 통해 살펴보자

▲ Table 2.

 

연구의 개선 방식은 ID Switch 수를 효과적으로 줄이는 데 성공했다. 기존 SORT에서는 ID Switch가 1,423회였던 반면, DeepSORT는 781회로 약 45% 감소하였다. 다만, ID를 유지하려다 보니, Fragmentation은 소폭 증가했다. 또한 Mostly Tracked 비율은 눈에 띄게 증가했고, Mostly Lost의 비율은 줄어들었다.

 

결과적으로, appearance 정보를 통합한 것 덕분에 occulusion 상황에서도 동일 객체의 ID를 유지할 수 있게 되었다. 이러한 효과는 추가 자료에 포함된 결과를 통해 확인할 수 있으며, 예시 결과는 Fig 1.에 제시되어 있다.

▲ Fig 1.

 

연구의 방식은 다른 온라인 트래킹 프레임워크들과 비교했을 때에도 강력한 경쟁력을 갖는다. 특히, DeepSORT는 온라인 방식 중 ID Switch 수가 가장 적으면서도, MOTA, Fragmentaion, False Negative 측면에서 경쟁력 있는 수준을 유지한다.

 

측정된 tracking accuracy는 대부분 False Positive(주로 배경 오탐지)가 많기 때문에 낮아진다. 이것이 MOTA에 끼치는 전반적인 영향을 고려했을때, 탐지 결과에 더 높은 confidence threshold를 적용한다면, 연구의 알고리즘 성능 지표는 크게 향상될 수 있다. 실제로 결과를 시각적으로 분석해보면 이러한 False Positive의 대부분은 정적인 배경에서 Detector의 간헐적인 오탐지에서 발생한 것 임을 확인할 수 있다. 또한, 트랙이 자주 false alarm으로 튀는 현상은 발견되지 않았다. 오히려, 자리에 지속적으로 머무는 안정적인 트랙을 생성하는 경향을 보였다.