[Overview] Multipe Object Tracking 이란 (1)

1. Multiple Object Tracking (MOT) Overview

Object Tracking?

비디오 또는 스트리밍 형태로 연속적인 프레임들이 주어질 때, 물체를 추적(Track)하는 Task다. Multiple Object Tracking 과 Visual Tracking 이렇게 크게 2 분류로 나뉜다. 전자는 bounding box를 이용하여 여러 객체들을 추적하는 것인 반면, 후자는 하나의 객체만 추적하는데, 대신에 instance segmentation처럼 mask 까지 예측하면서 추적한다. 이 글에서는 MOT의 기본적인 내용들에 대해 자세히 풀어보겠다.

MOT Overview

• 모델의 구조는 일반적으로 Detector 와 Tracker 이렇게 2가지로 구성한다.
• Detector 는 흔히 아는 YOLO 시리즈나, Faster R-CNN 시리즈 모델들을 사용할 수 있다. 최신 SOTA 논문들을 들여다보면 YOLOv4, YOLOv5, 또는 YOLOX 를 주로 사용하는 추세다. Detector 를 사용하면 객체들의 bounding box 를 얻을 수 있다. 이 bounding box들을 Tracker 모델에 넘겨주면, Tracker 에서는 이전에 찾았던 객체들의 bounding box와 새로 받은 bounding box 를 이용해서 추적한다.
• (심화) RPN + Siamese 구조를 사용하는 모델들도 있고, Transformer 기반으로 만든 모델들도 있다.
• Tracker 는 그럼 어떻게 추적을 할까? 일반적으로 assignment 알고리즘을 사용한다. 여기서 Hungarian 알고리즘이나, Bipartite 알고리즘 등이 쓰인다. 그럼 할당을 할 때 기준이 되는 cost가 있을텐데, 이는 밑에서 다시 알아보자
• (심화) JDE 나 FairMOT, CSTrack 과 같이 Detector 와 Tracker 를 합친 unified network 형태의 모델들도 있다.
• Tracker 의 역할은 크게 2가지로 나누면, motion 또는 appearance 중에 뭘 기준으로 객체를 추적할 것인지로 구분할 수 있다. 쉽게 풀어보면, motion 은 이전 프레임의 위치에서 얼만큼 이동했는지를 기준으로 파악하는 것이고, appearance 는 같은 특징을 보이는 물체가 이전 프레임에서 어디로 갔는지를 보는 것이다.

---

💡 본 글에서는 Tracking 의 가장 기본이 되는 SORT 와 DeepSORT 에 대해 설명하고, 나아가 Re-ID 모델에 대해서 살펴보고자 한다.

2. Kalman Filter

칼만 필터

(Kalman filter)는 잡음(noise)이 포함되어 있는 측정치를 바탕으로 선형 역학계의 상태를 추정하는 재귀 필터로, 루돌프 칼만이 개발하였다. 칼만 필터는 컴퓨터 비전, 로봇 공학, 등의 여러 분야에 사용된다. (위키피디아 참고)

칼만 필터는 예측과 업데이트로 이뤄진다. 노이즈에도 robust 하다는 특징이 있고, 연산이 빨라서 (보통 matrix 기반으로 이뤄짐) 실제 상황에서도 쓰기 용이하다.

Kalman Filter Example

위 그림을 이해하는 것을 목표로 하고 설명해보겠다.


첫 번째 프레임에서 자동차를 처음 찾았다고 가정해보자. 이때 위치와 속도가 $(x, v)$라고 가정하자. 단순하게 생각했을 때, 다음 프레임에서 자동차의 위치는 $\hat{x} = (x+v)$ 라고 예측할 수 있겠다. 그런데 Detector 의 결과상, 두 번째 프레임에선 $y$ 라는 위치로 측정했다고 하자 . 두 값이 같으면 정말 좋겠지만, 측정의 불확실성, 객체의 이동의 불확실성 등의 원인으로 그런 일은 매우 드문 경우일 것이다.


이렇게 예측과 측정을 점 대 점으로 고려할 때 생기는 문제를 해결하기 위해 칼만 필터에서는 예측을 할 때 가우시안 확률 분포를 이용한다. 이 정도 범위에는 있겠지 ~ 하고 예측하는 것이다. $\hat{x}, y$를 각각 평균으로 하는 가우시안 분포가 위 그림처럼 생겼다고 하자. 두 분포의 차이가 적을수록 확실한 측정 및 예측이 되는 것이고, 차이가 클수록 불확실성이 커지는 것이다. 이 과정에서 mahalanobis distance 를 이용한다. 이 distance 는 평균과의 거리가 표준 편차의 몇 배인지를 나타낸다. 클수록 확률 분포상 이상한 값이라 볼 수 있겠다. 만약 예측 범위내에서 측정값이 있다면 측정 값으로 상태를 업데이트한다.


실제로 칼만 필터를 MOT에서 사용할 땐 $(x,y,w,h,vx,vy,vw,vh)$ 를 사용한다. Detector 에서 얻은 bounding box를 알고 있으므로, box 의 좌표, 가로, 세로 값과 각각 값들의 속도 또한 알 수 있다. (속도의 경우, 이전 프레임들과 현재 프레임들을 비교해서 차이를 통해 구할 수 있겠다.)


아래 예시에서 조금 더 알아보자.

Person - initial state

**(짱구는 못말려 극장판 유튜브에서 캡처했습니다)**
이미지 프레임에서 다음과 같이 짱구를 찾고, 짱구의 state를 정의한다면 위와 같이 할 수 있을 것이다. 처음 (400, 180) 은 bouding box의 중심이고, 다음 (60, 60)은 bounding box 의 w,h 값이다. 다음 (10, 5, 0, 0)은 bounding box 의 x, y 축 방향으로 속도 및 w, h 변화율이다. 이 상태에 따르면, 다음 짱구의 위치는 (410, 185) 일 것이다.
그러나 실제로는 이렇게 등속으로 움직이지 않을뿐더러, bounding box가 다음 프레임에서도 매우 정확하게 찾아낸다는 보장도 없다. 따라서 위에서 설명했듯이 확률 분포를 이용하여 다음에는 어디쯤에 있을 것이다 방식으로 예측하는 것이다.

Person - Prediction, Measurement

빨간색 박스가 칼만필터로 Prediction 한 다음 bounding box고, 파랑색과 빨간색 박스가 실제 Measurement 라고 하자. 여기서 Mahalonobis distance 로 빨강 - 파랑 과 빨강 - 초록 에 대한 cost를 구한다면, cost가 최소가 되도록 다음 state를 파랑색 박스로 업데이트한다.

---

3. SORT

그렇다면 bounding box를 활용할 수 있는 다른 방법은 없을까? SORT는 칼만 필터와 bounding box의 IOU를 이용하여 객체들을 추적하는 알고리즘이다.

IOU

IOU란, Intersection Over Union 의 약자로, 두 bounding box 영역의 합집합이 분모, 교집합이 분자로 두고 계산한다. 값이 1에 가까울수록 두 box가 겹치는 영역이 크다.

Tracking Flow

SORT 의 흐름도를 정리하면 위와 같다.

SORT의 흐름만 잘 이해해도, 추후에 서술할 DeepSORT 는 쉽게 이해할 수 있다. 우선 용어를 정리해보자.

Track

논문들에서는 Tracklet 이란 단어로 쓰기도 한다. 한 객체마다 하나의 Track을 갖는다. 프레임상에서 변화가 생긴다면 (움직이거나 갑자기 사라지는) 새로운 프레임에서 얻은 정보들을 넣어서 이 Track을 업데이트한다. 실제 implementation 기준으로, track 은 다음 property 들을 가진다.

• mean, covariance : Kalman filter 연산을 하기 위한 값들이다.
• state :
  • Tentative : detection 의 결과를 기준으로 객체가 있는 것은 찾았는데, 실제로 추적할 대상인지 확실치 않은 상태다. 트랙킹할 후보 정도로 보면 된다.
  • Confirmed : 객체가 프레임 상에 있는 것이 분명한 상태다.
  • Lost : 객체가 프레임 상에서 더 이상 보이지 않은 상태다.
• initial hit :
  • Tentative state 에서 Confirmed state 로 넘어가기 위해 필요한 최소 detection 횟수다.
• age :
  • Lost가 되고 나서 몇 프레임이 지났는지 나타내는 값이다.

이제 Track 에 대해서도 알아보았으니 SORT 알고리즘을 본격적으로 알아보자.


SORT algorithm

1. 우선 Track들이 갖고 있는 가장 마지막 bounding box 들에 대해 칼만 필터를 이용해서 다음 상태를 예측한다.
2. 그러고 나서, Detector 에서 찾은 객체들의 bounding box들과 1의 결과로 나온 box들에 대해 IOU를 기준으로 matching 한다. 모든 box들을 두고 global 한 관점에서 비용이 최소가 되도록 매칭한다.
3. 이 때, flowchart 에는 없지만 칼만 필터 예측값과 측정값의 차이가 매우 큰 경우에는 매칭하지 않는다.
4. 매칭된 detector 의 bounding box들은 각각의 짝이 되는 track의 새로운 정보로 업데이트 된다.
5. 매칭되지 않은 detector 의 bounding box는 새로운 트랙을 생성한다. 상태는 Tentative 다.
6. 매칭되지 않은 트랙은 다음과 같이 처리한다.
   1. Confirmed 상태인 트랙 → lost로 전환
   2. lost 인 트랙 → age 가 특정 기준을 넘으면 해당 트랙을 삭제하고, 아니면 age 값을 늘린다.
   3. Tentative 상태인 트랙 → 바로 삭제

위에서 보았던 짱구 그림에 SORT를 적용해보자면, Kalman Filter로 예측한 다음 bounding box 를 기준으로, Detector에서 찾은 파랑색 박스와 초록색 박스와 IOU cost 값도 구한다. 파랑색과 IOU 가 높으므로, 빨강 - 파랑으로 매칭하는 것이 빨강 - 초록으로 매칭하는 것보다 cost가 낮다.

위 과정을 지속적으로 반복하면서 여러 객체들에 대해 추적할 수 있다. 딥러닝 기반이 아니고 알고리즘만으로 해결하지만, 그래도 괜찮은 성능을 보여주고 무엇보다 속도가 빠르다. SORT는 앞서 Overview 에서 보았던 Tracker 중에서 motion based 에 해당한다.

그런데, MOT 에서 가장 까다로운 부분이 바로 ID switch 다. 두 객체가 서로 교차하면서 지나갈 때 IOU를 기준으로 매칭하기가 애매하고, 이때 객체의 ID 값이 바뀌게 되는 경우가 빈번하다.

ID Switch

맨 왼쪽에 있는 자전거를 세우고 있는 아저씨가 계속 뒤로 밀리는 장면이다. 자전거 타고 있는 세 사람에 대해 Track 이 3개 있다고 가정해보자. (색을 달리하였다.)


두 번째 프레임까지는 잘 잡아내지만, 중간에 회색바를 잡으며 타고 있는 아저씨와 완전히 겹치게 되는 순간이 존재한다. 이때도 IOU 와 Kalman Filter만 사용해서 잘 잡아낼 수 있을까? 아쉽게도 SORT 는 이런 문제에 매우 취약하고, 세 번째 프레임처럼 Track이 추적하는 대상이 바뀌어버리는, 즉 ID switch 문제가 생겨버린다. 네 번째 프레임 다음으로, 화면상 맨 앞쪽에 있는 아저씨와 뒤로 밀리고 있는 아저씨와도 (x,y) 위치가 완전히 겹치는 순간이 올 것이고 역시 ID switch가 일어날 수 있다.

SORT 는 이처럼 ID switch 에 취약한 문제가 있다. 어떻게 이를 해결할 수 있을까?

---

• 영상 출처) https://youtu.be/MRpWmI7mWqE
• 내용 출처) SORT 논문 & Kalman Filter 위키피디아 및 설명 블로그