[Tracking] 딥러닝 DNN 기반 트래킹 정리(1편 SORT 알고리즘)

[Background] Tracking-by-Detection

• 논문에 대해 살펴보기 전에 tracking이 이루어지는 단계를 살펴보자.
• 여러가지 물체를 한 카메라에서 동시에 추적하는 Multiple object Tracking(MOT) 문제에서 tracking-by-detection 방식이 가장 흔히 사용되고 있는 방식이다.
  • tracking-by-detection 방식이란?object detection 단계는 흔히 활용되는 yolo나 centerNet등이 사용된다.
  • data association 단계는 detection에서 찾은 object들이 이전의 frame의 object와 같은 object인지 찾는 단계이다. SORT가 대표적인 IOU 방식 기반의 data association 알고리즘이다.
  • 그림에서와 같이 object detection과 data association의 2 stage 방식으로 최종의 final trajectory를 얻는 방식을 의미한다.

https://www.researchgate.net/figure/Tracking-by-detection-paradigm-Firstly-an-independent-detector-is-applied-to-all_fig1_268987905(이미지 출처)

 

SORT 알고리즘

SORT

sort 는 simple online realtime tracking 의 약자로 실시간 트래킹이 가능한 대표적인 접근 방식이다.
SORT 를 이해해 두면 아래 소개할 다른 로직들을 이해하는데 큰 도움이 되는 baseline 격이다.

 

SORT의 간단하므로 260 Hz의 속도로 업데이트되며, 이 속도는 다른 SOTA 모델에 비해서 20배 이상 빠릅니다.

SORT는 detector로 Faster Region CNN detection framework을 사용하고
motion estimation을 위해 kalman filter를 사용하고 data association을 위한 정보로 현 프레임에서 detector 가 구한 BBox와 tracking 된 object bbox 사이의 IOU 를 사용한다.

Fig 1. IOU

서로 다른 프레임 사이에서 object 들간의 best match 를 찾기 위해 IOU 값을 metric으로 hungarian algorithm을 이용해 best match 를 찾는다.

 

 

SORT의 플로우를 diagram으로 그리면 아래와 같다.

Fig 2. SORT flow diagram

 

 

Baseline Tracker와 SORT를 비교한 그래프입니다.

 

SORT를 개발하기 위해 저자들이 기여한 내용을 정리하면 다음과 같습니다.

1. CNN Detector를 최대한 활용해서 MOT를 수행
2. Kalman Filter와 Hugarian Algorithm을 사용한 실용적인 추적 방식을 제안하며, MOT Banchmark로 SORT를 평가합니다.
3. Code Open Source로 제공

선행 연구

전통적으로 MOT는 MHT (multiple hypothesis tracking) 또는 JPDA (joint probabilistic data association) Filter를 사용해서 수행했습니다. 하지만 이런 접근 방식은 복잡했기 때문에 실시간으로 사용되기 어려웠습니다.

Appearance 모델을 사용해서 MOT을 해결하려고 한 시도도 많습니다. Appearance 모델이란, 특정 객체를 잘 표현하는 강건한 Feature를 추출하고 이를 통해 통계적인 방법을 사용해서 탐지를 수행하는 추적 기법입니다.

Appearance 모델 외에도 객체의 움직임을 고려하여 탐지 결과의 연관성을 찾으려는 시도도 있었습니다.

Hungarian Algorithm을 2-stage 방식에 적용하여 MOT를 수행한 사례도 존재합니다. 우선, 인접한 Frame에서 탐지 결과를 연관지어 경로를 생성합니다. 생성된 경로들은 서로 연관돼서 폐색에 의해 생성되지 못한 경로를 메꿉니다. SORT는 1-stage 방식을 사용한다는 점에서 차이가 존재합니다.

 

SORT의 구조와 작동 원리

CPU 환경에서의 실시간 동작을 위한 딥러닝 기반 다중 객체추적시스템, 김경훈 et al., 2020–03–03

 

위 이미지는 Online Tracker의 구조를 간단하게 그린 내용입니다. 위 그림을 한 번 보고 아래 글을 읽으면 이해하기 수월하실 겁니다. SORT의 구조와 작동 원리를 설명하기 위해 4개의 섹션으로 나누어 설명하겠습니다.

 

(1) Detection

CNN 기반 Detector를 최대한 활용하기 위해서 SORT는 Faster R-CNN Framework를 사용합니다. Faster R-CNN은 2-stage로 구성되는데, 첫 번째 stage에서는 이미지 속 Feature를 추출하고 영역 제안을 수행합니다. 두 번째 stage에서는 제안 된 영역을 바탕으로 classification을 수행합니다. SORT는 Faster R-CNN 중에서 ZF와 (Faster R-CNN by Zeiler and Fergus) VGG16을 (Faster R-CNN by Simonyan and Zisserman) 사용합니다. 두 모델은 PASCAL VOC challenge로 학습된 pretrained parameter를 사용합니다. SORT는 보행자만을 추적하므로, 보행자 이외에 다른 모든 클래스는 무시합니다. 그리고 보행자를 탐지한 결과의 Accuracy가 50%보다 클 경우만 Tracking Framework한테 전달합니다.

실험을 통해서 Faster R-CNN과 ACF를 비교할 때 Detection 결과가 Tracking 결과에 큰 영향을 미친다는 것을 알 수 있습니다. 위 테이블에서 볼 수 있듯이 Detection 결과가 가장 좋았던 Faster R-CNN(VGG-16)이 가장 좋은 Tracking 결과를 낸 것을 확인할 수 있습니다.

(2) Estimation Model

현재 Frame에서 추적하는 객체의 정보를 다음 Frame으로 전파하기 위해 사용되는 모델에 관하여 설명하겠습니다. SORT는 Frame 간 객체의 위치를 Linear Constant Velocity Model을 사용하여 추정합니다. 이때 Linear Constant Velocity Model은 객체가 등속 운동을 한다고 가정하며, 이것은 다른 객체들 또는 카메라의 움직임과는 독립적으로 수행됩니다. 추적하려는 객체는 아래와 같이 모델링 합니다.

u와 v는 객체의 중심 x, y 좌표를 의미합니다. s와 r은 각각 Bounding box의 넓이와 비율을 의미합니다. 이때 유의할 점은, r은 상수라는 점입니다. 탐지 결과가 추적하려는 객체와 연관되면, 탐지된 Bounding box는 추적하려는 객체의 상태를 업데이트하는 데 사용됩니다. 이때, 속도와 관련된 부분은 Kalman Filter를 사용하여 최적화됩니다. 만약, 추적하려는 객체가 탐지된 결과와 연관되지 않았다면, Linear Constant Velocity Model을 사용하여 추적하는 객체의 위치를 업데이트합니다.

(3) Data Association

현재 Frame에서 탐지한 결과와 추적하는 객체를 연관 짓기 위해서 Assignment Cost Matrix가 계산됩니다. 이때 탐지 된 결과와 추적하려는 객체의 예측한 Bounding box 사이에 IoU Distance를 계산합니다. 최종적인 Assignment은 Hungarian Algorithm에 의해서 Optimally하게 구해집니다. 추가적으로 IoUₘᵢₙ 보다 IoU 점수가 낮게 계산 된 경우, Assignment에서 배제합니다.

IoU Distance를 사용했을 때의 장점은 지나가는 다른 물체에 의해 발생하는 Short Term Occlusion에 (폐색) 강건했다는 점입니다.

(4) Creation and Deletion of Track Identities

추적하려는 객체가 이미지에 처음 들어오면, 유일한 ID를 부여해야 합니다. 반대로 추적하던 객체가 이미지 밖으로 나가면 ID를 삭제해야 합니다. IoUₘᵢₙ보다 작은 IoU를 갖는 탐지 결과는 Untracked 객체가 있는 것을 의미합니다. Tracker의 속도는 처음에는 0으로 초기화됩니다. 추가적으로 Tracker는 처음에 관찰 기간을 (Probationary Period ) 거치게 됩니다. 처음 초기화된 Tracker는 객체에 관한 정보가 많이 없으므로, False Positive 추적을 방지하기 위해 충분한 데이터를 수집할 때 까지 관찰 기간을 수행합니다.

추적 되는 객체는 Tₗₒₛₜ Frame 동안 탐지 되지 않으면 제거됩니다. 이것은 추적 되는 객체의 수가 늘어나는 것과 Localization Error를 생성하는 걸 방지합니다. 이때 Tₗₒₛₜ는 1로 설정이 됩니다.

 

실험

SORT의 추적 성능을 평가하기 위해서 MOT Benchmark Database를 사용합니다. 이 Database는 움직이는 카메라와 고정된 위치의 카메라에 대한 두 가지 영상을 갖고 있습니다. Kalman Filter Convariance, IoUₘᵢₙ, 그리고 Tₗₒₛₜ를 튜닝하기 위해서 “Learning to Track: Online Multi-Object Trakcing by Decision Making” 논문에서 사용한 Training/Validataion Split을 사용합니다. 그리고 탐지를 위한 모델은 Faster R-CNN(VGG16)을 사용합니다.

(1) Metrics

MOT 성능은 지표 하나만으로는 평가하기 제한됩니다. 그래서 Evaluation Metrics와 Standard MOT Metrics를 사용해서 평가합니다.

(2) Performance Evaluation

추적 성능은 확인하기 위해 MOT Benchmark Test Server를 사용했습니다. 아래 표는 SORT와 다른 Baseline Tracker와 성능을 비교한 내용입니다.

SORT는 Online Tracker 중에서 가장 높은 MOTA 점수를 획득했습니다. NOMT는SOTA 모델로 상당히 복잡하며, 추적할 때 미래의 Frame을 사용합니다. 그럼에도 불구하고 SORT는 NOMT와 비교가 될 정도입니다. 그리고 Number of Lost Targets을 의미하는 ML은 가장 낮게 나왔습니다.

(3) Runtime

MOT를 위한 Tracker를 개발할 때 주로 추적의 정확도를 올리는 일에 집중합니다. 실행 속도와 정확도는 Trade-off 관계에 있음에도 불구하고, 속도를 희생하면서 정확도를 올리는 경우가 많습니다. 하지만 SORT는 속도가 빠르면서 정확도가 높은 Tracker입니다. 논문 리뷰 초반부에 등장했던 정확도와 속도를 그린 그래프를 보면, SORT는 우측 상단 쪽에 위치하는 걸 볼 수 있습니다. Intel i7 2.5 GHz Single Core와 16 GB 메모리 시스템에서 SORT는 260 Hz로 (FPS) 실행됩니다.

 

결론

논문에서는 Frame-to-Frame 예측과 연관에 집중하는 간단한 Online Tracking Framework를 제안합니다. 저자는 추적의 성능은 탐지 성능에 큰 영향을 준다는 것을 보였으며, 최근에 개발된 Detector를 활용해서 SOTA 추적 성능을 보였습니다. 그리고 SORT는 다른 Tracker와 다르게 속도와 정확도 모두 잡은 모델입니다. SORT의 간단함은 Tracker Baseline이 되기에 적합합니다. 새로운 방식은 SORT가 해결하지 못한 Long Term 폐색으로 부터 (occlusion) 발생한 문제를 해결하기 위해 re-identification에 집중할 것으로 예상됩니다.

 

---

단점:

1. object에 occlusion 이 발생

2. image frame 밖으로 나갔다가 다시 들어오는 경우(re-entering)

3. object의 외향적 특징이 변하는 변한 경우(different view point)

4. ID switching(동일 instance의 tracking id 값이 바뀌는 것)

- Identity Switches : IOU기반으로 매칭을 하기 때문에 물체의 방향이 바뀌는 등의 경우에, 같은 물체인지 잘 인식하지 못한다.

 

 

출처

• Simple Online and Realtime Tracking, Bewley et al., 2017–07–07
• Getting Started With Multi-Object Tracking: Part1 , Achleshwar, 2020–12–28
• CPU 환경에서의 실시간 동작을 위한 딥러닝 기반 다중 객체추적시스템, 김경훈 et al., 2020–03–03