[MOT] SORT 논문 리뷰

본 글은 다 물체 추적 (MOT, Multi-Object Tracking) 분야의 실용적인 기법으로 2017년에 제안된 SORT 알고리즘 논문 [1]에 대해 정리한다.

SORT 알고리즘에 기반한 다양한 논문들이 있어, 해당 논문을 리뷰하기 전에 먼저 정리하는 글을 작성한다.

 

SORT 알고리즘이란

Simple Online and Realtime Tracking의 약자로, 간단한 온라인 추적 프레임워크이다. 온라인 실시간 응용 분야에서 객체들을 효율적으로 연관짓는 것에 주요 초점을 둔 다물체 추적 분야의 실용적인 접근 방법 중 하나이다.

 

SORT 의 특징 정리

• SORT는 Online and Realtime으로 사용가능하며 논문에서 벤치마크 테스트로 제시한 성능은 260Hz으로 매우 빠르다.
• 객체 추적에서 검출 요소 중 appearance feature는 사용하지 않고 오직 bounding box의 위치와 크기만을 사용한다.
• Tracking-by-Detection Framework 에 기반하여 제안된 추적 알고리즘이므로 추적 성능은 검출기(Detector)의 성능에 크게 영향을 받는다. (검출기가 성능이 좋으면 추적도 잘 된다)

 

SORT 의 작동 방식

• 영상 프레임 간 객체의 변위는 선형 속도를 가진다고 근사하였으며, 객체의 상태를 Kalman Filter를 통해 예측/보정한다.
• Hungarian algorithm을 이용하여 Detector가 검출한 모든 객체와 추적하고 있는 특정 객체에 대해 Kalman Filter으로부터 예상한 객체의 중첩도 (IOU)를 계산한다. 최소 중첩도 (IOU_min)보다 낮은 객체는 해당 추적에 할당하지 않는다.(추적하고 있는 물체가 아니라고 판단한다)
• 최소 중첩도 (IOU_min)를 넘지 못한 객체는 새로 추적할 객체로 식별한다.
• 객체가 검출되지 않더라도 Kalman Filter를 통해서 객체의 위치를 예측하며, 일정 시간 (T_lost) 이상 검출되지 않는다면 추적을 중지한다.

SORT 알고리즘의 작동 방식 [2]

 

 

SORT 의 성능 분석

2017년 당시, 제안된 논문과 관련 분야의 추적기의 벤치마크 테스트를 한 결과이다.

MOTA(Multi-Object Tracking Accracy)와 Speed 가 클 수록 좋은 성능을 낸다.

논문에 따르면 여타 알고리즘은 일반적으로 속도 혹은 정확도를 희생하였으나 SORT 알고리즘은 속도 및 정확도 측면에서 최고의 성능을 발휘한다고 한다.

벤치마크 성능 결과

 

 

축약어 해설은 다음과 같다.

• MOTA ( ↑, Multi-Object Tracking Accuracy) 다물체 추적 정확도
• MOTP ( ↑ , Multi-Object Tracking Precision) 다물체 추적 정밀도
• FAF ( ↓ , number of False Alarms per Frame) 프레임 당 불일치 알림 숫자
• MT ( ↑ , number of Mostly Tracked trajectories) 대부분 추적된 궤적 숫자, 예를 들면 물체가  있는 동안 적어도 80%이상의 같은 라벨을 가짐
• ML ( ↑ , number of mostly Lost trajectories) 대부분 망실한 궤적 숫자, 예를 들면 물체가 있는 동안 적어도 20% 동안 추적되지 못하는 경우
• FP ( ↑ , number of false detections) 검출 실패 숫자
• FN ( ↑ , number of missed detections) 오검출 숫자
• ID sw ( ↑ , number of times an ID switches to a different previously tracked object) 직전에 추적했던 다른 객체와 ID가 교체된 숫자
• Frag ( ↑ , number of fragmentations where a track is interrupted by miss detection) 오검츨에 의해 추적이 방해받은 파편 숫자

윗 방향 화살표는 해당 지표는 높을 수록 좋은 성능을 내는 것을 나타낸다.

 

---

 

부연설명

IOU (Inter-section over Unit) 이란?

자카드 지수 (Jaccard Index)라고도 부르며, 두 표본 집단 간의 유사도를 측정하는 방법 중 하나이다.

두 표본의 크기에 대해서 중첩된 면적의 비율을 나타내며 다음과 같이 계산한다.

$$J(A,B) = \frac{ \left| A \cap B \right| }{ \left| A \cup B \right| } $$

Concept Image of Inter-section over Union (IOU)

 

칼만 필터 (Kalman Filter) 란?

칼만 필터란 수학적으로 모델링한 시스템에 대해서 상태를 예측하고, 잡음이 포함된 측정치를 바탕으로 보정하는 재귀 필터(Recursive Filter)이다. 시스템의 상태와 계측치의 잡음 정도를 가우시안 확률 분포로 표현하여 사용한다.

칼만 필터는 예측 (Prediction)과 추정 (Estimation) 과정으로 구성되어있으며, 알고리즘을 간단히 서술하면 다음과 같다.

1. [상태의 예측] 수학적으로 모델링 된 시스템 모델에 대해서 직전 상태로부터 다음 시간의 상태를 예측(계산)한다.
2. 시스템 모델이 가지는 잡음과 계측치의 잡음은 가우시안 모델로 가정하고, 이 잡음의 정도를 알고 있다고 하자. 이때 이러한 잡음 정도를 고려하여 계측치를 얼마나 반영할지 나타내는 칼만 이득을 계산한다.
3. [상태의 추정] 계측된 상태를 기반으로 칼만 이득을 반영하여 추정 상태를 계산한다.

 

헝가리안 알고리즘 (Hungarian Algorithm) 이란?

헝가리안 알고리즘은 혼합 정수 알고리즘 (Combinatorial optimization algorithm) 으로, 다항 시간 내에 할당 문제를 푸는 방법이다.

자세한 설명은 어떤 분의 아래의 글을 참고하면 좋을 것 같다.

[7] Hungarian Algorithm, https://blog.naver.com/worb1605/221298986596

---

 

Reference

[1] Alex Bewley, Zongyuan Ge, Lionel Ott, Fabio Ramos, Ben Upcroft, Simple Online and Realtime Tracking(SORT), 2016, https://arxiv.org/pdf/1602.00763

[2] 김경훈, 허준호, 강석주, CPU 환경에서의 실시간 동작을 위한 딥러닝 기반 다중 객체추적시스템, 2022 https://www.kibme.org/resources/journal/20200414104021807.pdf

[3] 양수진, 정인화, 강동화, 백형부, SORT와 DeepSORT의 혼합을 이용한 실시간 다중객체 추적, https://ki-it.com/xml/30742/30742.pdf

[4] Wikipedia, Jaccard index, https://en.wikipedia.org/wiki/Jaccard_index

[5] Adrian Rosebrock, Intersection over Union (IoU) for object detection, https://pyimagesearch.com/2016/11/07/intersection-over-union-iou-for-object-detection/

[6] Wikipedia, Hungarian algorithm, https://en.wikipedia.org/wiki/Hungarian_algorithm

[7] Hungarian Algorithm, https://blog.naver.com/worb1605/221298986596

 

*** EOF ***