DeepSORT : SIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRIC 논문 공부

DeepSort 논문의 전체 스토리 및 읽으면서 새롭게 공부한 내용들을 정리함

(논문 링크 : https://arxiv.org/abs/1703.07402)

 

1. Introduction

원래 MOT를 위한 SORT 라는 알고리즘이 있었다.

SORT 알고리즘은 image space에 Kalman filtering을 적용하고, hungarian method를 수행하여 data association을 수행.

 

그렇다면 Kalman filtering은 무엇인가? 🤔

Kalman filter는 1960년 NASA의 루돌프 칼만이 개발한 알고리즘으로, 시스템이 선형적이고 가우시안 분포를 따를 때 사용할 수 있는 localization 예측 알고리즘이다. 1) object의 state (위치, 속도 등)을 예측하는 motion model과 2) 실제 state의 측정값을 나타내는 measurement model 두 가지가 존재하는데, 각각 모델이 Gaussian 분포를 따른다고 가정한다.

결과적으로는 1) motion model에 의해 예측된 Gaussian of next state 와 2) measurement에 의해 실제로 측정된 Gaussian of real (but noisy) state  사이의 곱으로 state가 계속 업데이트 된다. 

 

하지만 SORT 알고리즘은 잦은 identity switch를 발생시키고, occlusion에 취약하다는 단점이 있었다. DeepSORT는 기존의 association metric을 motion 과 appearance information이 결합된 more informed metric으로 교체하여 robustness를 향상시켰다고 한다.

 

2. SORT with deep association metric

Section 초반에 이런 말이 있다. "We adopt a conventional single hypothesis tracking methodology with recursive Kalman filtering and frame-by-frame data association."

그렇다면 Single hypothesis tracking 은 무엇인가? 🤔

hypothesis는 object의 state (position, velocity)에 대한 예측함수이다. single hypothesis  tracking이란 모든 frame 마다 object의 위치에 대해서 단 하나의 예측이 존재한다는 뜻이다. (multiple hypothesis tracking은 여러개의 state를 동시에 예측한다.) 이 hypothesis 는 매 frame 마다 object 의 변하는 state들을 사용하여 Recursive Kalman filter 등을 사용하여 update 된다. -- 예측을 확률적으로 할지언정 single estimate이 존재한다는 것이 핵심인 듯 하다...

 

DeepSORT는 motion information과 appearnace information 각각을 반영하는 metric을 융합한 알고리즘이다. "Into this problem formulation we integrate motion and appearance information through combination of two appropriate metrics."

그렇다면 Appearance information 은 무엇인가? 🤔

👉 여기서 appearance information은 CNN을 통과시켜 얻은 feature를 의미한다.

 

2.2 Assignment problem

DeepSORT가 association을 풀기 위해 사용하는 첫번째 metric은 Mahalanobis distance이다. Motion model이 예측한 state 가 $(y_i, S_i)$ 이고 (Gaussian형태로 예측하기 때문에 각각 평균과 분산이다), 해당 frame에 실제로 detect된 bounding box가 $d_j$ 라고 했을때 motion information을 반영한 첫번째 다음과 같다.

하지만 위의 metric은 ID switches 및 occlusion에 취약하다고 하다. 이에 DeepSORT는 appearnace information을 반영한 두번째 metric을 제시한다. 이 metric은 object들 사이의 appearance descriptor $r$ 사이의 similarity를 측정한다.
(appearance descriptor $r$은 그냥 CNN feature vector이다.) 이전에 등장했던 100개의 $r$들을 R이라고 하는 gallery 안에다 저장해두는데, 새로운 detection의 descriptor $r_j$와 가장 cosine similarity가 높은 track $r_k^{(i)}$ 를 match 시킨다.

결과적으로는 두 metric을 결합한 값을 association problem의 cost function으로 사용한다.

각각의 metric이 서로 상보적이고 각각의 효과가 있다고 한다.
Mahalanobis distance는 short-term prediction에 효과적이고
Cosine similarity는 long-term occlusion을 회복하는데 효과적이다. 카메라 모션이 격할때도 좋다고 한다.

 

2.3 Matching Cascade

DeepSORT는 기존의 measurement-to-track association를 대체하는 matchin cascade 기법을 제시한다. 

Motivation : 기존의 Kalman filter prediction을 이용하는 방법의 경우 여러 tracks (Kalman prediction)이 하나의 detection을 두고 경쟁하는 경우 variance (uncertainty)가 더 큰 track이 선택되게 된다. (아래 distance 공식 참고)

하지만 이렇게 distance 보다는 uncertainty에 의존하여 association을 풀다보면 잦은 ID switch나 track fragmentation이 발생하게 된다. 이를 해결하기 위해 나온 methodology가 Matching cascade 이다. 

 

이게 Matching cascade 알고리즘인데 논문 설명이 워낙 부실하여 이것만 보고 이해하기는 쉽지 않다. 🤔
그나마 (https://pajamacoder.tistory.com/56) 여기에 설명이 잘 되어있으니 참고하면 좋을 것 같다. .😢

간략히 설명하자면 위의 hybrid cost function을 사용해서 hungarian algorithm (line 7)을 푼다음,

match가 성공한 object에 대해서 kalman filter를 update하고 (line 8)

unmatch된 object들은 IoU matching으로 넘어간다고 한다 (line 9)

이 IoU matching은 원래 SORT에서 수행하던 것으로 IoU를 cost 로 hungarian을 돌리는 듯 하다 (아마도..?)

여기서도 match가 안된 object들은 30 frame 동안 tentative 한 상태로 track에 저장한다고 한다 (아마도 위의 U..?)