Search
Login
📷

Simple Online and Realtime Tracking with a Deep Association Metric

Created
2022/06/25
Editor
Tags
Vision
논문명 : SIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRIC 저자 : Nicolai Wojke†, Alex Bewley, Dietrich Paulus†

Abstract

SORT(Simple Online and Realtime Tracking)는 단순하면서도 효율적이고 실용적인 알고리즘으로 다중 객체를 추적합니다. 해당 논문에서는 SORT의 성능을 높이기 위해서 외형 정보(Appearance Information)를 통합시킵니다. 이러한 모델의 개선은 객체가 장애물에 가려지는 시간이 길어져도 객체를 추적할 수 있고, 효과적으로 identity switch를 줄여나갈 수 있습니다. 우리는 기존 모델의 프레임워크에서 computational complexity를 offline 사전 학습단계에 배치하여, 대용량의 사람 재식별 데이터셋에 대하여 deep association metric을 학습합니다.
online을 적용하는 동안에, 시각적 형상이 있는 공간에서 NN(Nearest Neighbor,근접 이웃) query를 이용하여 measurement-to-track association을 세웠습니다. 실험평가에서는 우리의 확장이 identity switch를 45%를 감소시켰고, 높은 프레임률로 전반적인 경쟁적 성능을 보였습니다.
identity switch :
deep association metric :

0. FlowChart

SORT

SORT

DeepSORT

1. Introduction

객체 탐지에서 최근의 행보로 인해, tracking-by-detection은 다중객체추적을 이끄는 패러다임이 되었습니다. 이 패러다임에서, 객체의 trajectory(궤도)들은 보통 video batch 전체를 한번에 처리하는 global optimization 문제가 있었습니다. 그러나 이러한 batch 처리방식 때문에 flow network formulation과 확률적 그래프 모델과 같은 방식은 target의 identity에 대해 각 time step마다 확인이 가능해야 했고, 이에 따라 online 상에서 적용이 불가능하다는 단점이 있습니다.
SORT는 이미지 공간 상에서 Kalman filtering을 수행하고, Bounding box의 overlap을 측정하는 association metric과 함께 Hungarian method를 사용하여 frame-by-frame data association을 수행하는 더욱 단순한 프레임워크입니다. 이렇게 단순한 접근은 높은 프레임률로 유리한 성능을 보여줍니다.
MOT challenge dataset에서, sota의 성능을 보이는 사람 검출기 SORT는 표준 검출기의 MHT보다 평균적으로 높은 순위를 차지하고 있습니다. 이것은 전반적인 추적 결과에서 물체 검출기 성능의 영향력을 강조할 뿐 아니라, 전문가의 입장에서 봤을 때 굉장히 중요한 통찰력이기도 합니다.
SORT는 tracking precision과 accuracy 측면에서 전반적으로 좋은 성능을 보이긴 하지만, 상대적으로 많은 identity switch가 발생하는데, 이는 사용된 association metric이 state estimation 불확실성이 낮을 때에만 정확하기 때문입니다.
결론적으로, SORT는 보통 카메라가 정면을 향하는 경우가 많기 때문에 occlusion을 추적하는데 결함이 있습니다. 해당 논문에서는 이러한 이슈를 극복하기 위해 association metric에 움직임과 appearance 정보를 결합하여 좀 더 정보에 입각한 metric으로 대체하였습니다. 특히, 대용량의 사람 재인식 데이터셋에 대하여 보행자를 구별해내도록 훈련된 CNN모델을 사용하였습니다. 이러한 네트워크의 통합을 통해 시스템을 적용하기 쉽고, 효과적이고, online 상에 적용하기 좋게 유지하면서도 misses나 occlusion들에 대한 견고함을 증가시킵니다. 코드와 사전학습 CNN 모델은 개발의 용이성을 위해 공개해두었습니다.

2. Sort With Deep Association Metric

Kalman filtering과 frame별 데이터 연관성을 가진 전통적인 단일 가설 추적 방법을 채택하였습니다. 다음 섹션에서 좀 더 자세하게 설명해보겠습니다.
Kalman filter :

2.1. Track Handling and State Estimation

track handling과 Kalman filtering 프레임워크는 거의 대부분 SORT 알고리즘의 원래 공식과 동일합니다. 카메라는 보정되지 않은, 이용할 수 있는 ego-motion정보가 없는 매우 일반적인 tracking 시나리오를 가정해봅시다. 이러한 상황은 filtering 프레임워크에 대하여 도전적일 수는 있지만, 최근의 다중객체 추적 benchmark에서는 매우 흔한 설정입니다.
ego-motion :
tracking 시나리오는 bounding box의 중심 좌표(u,v)(u,v), 가로세로 비율 γ\gamma, 높이 hh, 그리고 이들에 대하여 영상 좌표계에서의 상대적인 속도값을 포함한 8차원의 state 공간에서 정의됩니다.
(u,v,γ,h,x˙,y˙,γ˙,h˙)(u,v,\gamma,h,\dot{x},\dot{y},\dot{\gamma},\dot{h})
우리는 등속 운동과 선형 관측 모델을 가진 표준 Kalman filter를 사용하고, 객체에 대해 직접적으로 관측하여 나타낸 bounding box의 좌표인 (u,v,γ,h)(u,v,\gamma,h)를 사용합니다.
각 track인 k에 대해 가장 마지막으로 성공한 measurement association, aka_k 이후의 frame 수를 계산합니다. 이 카운터는 Kalman filter 예측 동안 증가되고 track에서 다시 measurement association이 발생하면 0으로 리셋됩니다. 사전에 정의된 최대 age, AmaxA_{max}를 초과하는 track은 scene을 떠났다고 간주되어 track set에서 삭제됩니다. 새로운 track 가설의 경우, 기존의 트랙과 연관지어질 수 없다고 판단하고 각 detection마다 초기화된 새로운 track을 생성합니다. 이 새로운 track들은 첫 3 프레임동안 잠정적 상태(tentative)로 분류됩니다. 이 시간동안 각 단계마다 measurement와의 성공적인 association을 기대하는데, 성공적으로 measurement와 연결되지 않은 track들은 삭제됩니다.

2.2. Assignment Problem

예측된 Kalman states와 새롭게 도착한 measurement 사이의 연관성을 해결하기 위한 전통적인 방식은 Hungarian algorithm을 사용하는 것입니다. 해당 공식 안에서, 우리는 두가지의 적절한 metrics을 결합하여 움직임과 외형 정보를 통합합니다.
assignment problem :
Hungarian algorithm :
움직임에 대한 정보를 통합하기 위해 예측된 Kalman states와 새롭게 도착한 measurement 사이의 (제곱) Mahalanobis 거리를 사용합니다.
djd_j : j번째 bounding box detection
yiy_i : i번째 track 분포에서 평균 값
SiS_i : i번째 track 분포에서의 공분산 행렬
Mahalanobis 거리 :
마할라노비스 거리는 state estimation 불확실성을 측정하고 고려하기 위해 표준편차(detection이 평균 track의 위치로부터 얼마나 떨어져 있는지)를 측정합니다. 게다가, 이 측정지표를 사용하면 역 χ2\chi^2분포에서 계산된 95%의 신뢰구간을 이용하여 마할라노비스 거리를 thresholding하여, 가망없는 연관을 배제시킬 수도 있습니다. 이러한 decision을 수식으로 나타내면 다음과 같습니다.
마할라노비스 거리는 움직임에 대한 불확실성이 낮을 때 적절한 연관성 측정지표가 될 수 있지만, 우리의 image-space problem formulation에서는 Kalman filtering에서 구해진 예측 상태분포를 통해 객체 위치에 대한 대략적인 추정치만 제공합니다. 특히, 설명되지 않은 카메라의 움직임은 영상 평면에 급격한 변화를 야기할 수 있기 때문에, 마할라노비스 거리는 occlusion을 추적하는데 다소 비형식적인 측정지표가 될 수 있습니다. 그러므로, 두번째 metric을 assignment problem에 할당시켰습니다.
각각의 bounding box detection인 djd_j에 대하여 우리는 ∣∣rj∣∣=1||r_j||=1인 appearance descriptor, rjr_j를 계산하였습니다. 또한, 각 트랙 k에 대하여 마지막 100개의 appearance descriptor를 가지는 갤러리인 RkR_k를 보관하였습니다.
그러면, 우리의 두번째 metric은 appearance space에서 i번째 track과 j번째 detection 사이의 가장 작은 코사인 거리를 측정합니다.
코사인 거리에 대해서도 연관성이 허용되는지 여부를 확인하는 이진 변수를 사용합니다.
그리고 분리된 훈련 데이터셋에 대하여 이 indicator를 위한 적절한 threshold 값을 찾았습니다. 실제로 사전 훈련된 CNN을 이용하여 bounding box의 appearance descriptor를 계산하였습니다. 이 네트워크의 구조는 2.4.절에 설명되어 있습니다.
두 지표를 결합하면, 두 metric은 서로 다른 assignment 문제를 처리하면서 상호보완을 이룹니다. 먼저, 마할라노비스 거리는 단기 예측에 특히 유용한 움직임에 기반하여 물체의 가능한 위치 정보를 제공합니다. 반면에 코사인 거리는 동작이 별반 다르지 않을 때 장기간의 occlusion 이후 물체에 대한 동일성을 회복하는데 특히 유용한 appearance 정보를 고려합니다. Association 문제를 설계하기 위해 우리는 weighted sum을 이용하여 두 metric을 묶어줍니다.
그리고 여기서 두 metric 모두의 gating 영역 안에 있다면 연관성을 인정합니다.
결합된 연관성 비용에 대하여 각 metric의 영향력은 hyperparameter인 λ\lambda를 통해 조절할 수 있습니다. 실험을 진행하면서 카메라의 움직임이 상당할 경우 λ=0\lambda =0로 설정하는 것이 합리적이라는 결정을 내렸습니다. 이때는 연관성 비용 수식에서 오직 appearance 정보만을 사용하게 되는데, 마할라노비스는 여전히 Kalman filter에 의해 추론된 가능한 물체 위치에 기반하여 실행불가능한 assignment를 무시하는데 사용됩니다.

2.3. Matching Cascade

Global assignment 문제에서 measurement와 tracking 사이의 연관성을 해결하기보다는, 일련의 하위 문제들을 해결하는 cascade를 도입했습니다. 다음과 같은 상황을 고려해봅시다.
객체가 더욱 긴 시간동안 가려지게 되면, 뒤이은 Kalman filter는 물체의 위치에 대한 불확실성을 증가시킵니다. 결과적으로, 확률질량은 state space에서 퍼지는 모양을 가지게 되고 관측 가능성은 덜 뾰족해집니다. 직관적으로, association metric은 measurement-to-track distance를 증가시킴으로써 퍼진 확률 질량을 설명해야 합니다.
반대로 두개의 track이 동일한 detection에 대해 경쟁을 할 때에는, 마할라노비스 거리는 더 큰 불확실성을 선호하는데, 이는 어떠한 detection이든 해당 track의 평균에 대한 표준편차 거리를 효과적으로 감소시켜주기 때문입니다. 그런데, 이는 트랙의 분열과 불안정한 트랙의 증가를 야기할 수 있기 때문에 바람직하지 않은 행동입니다. 따라서, 연관 가능성 확산의 개념을 인코딩하기 위해 더 자주 보이는 물체에게 우선순위를 부여하는 matching cascade를 도입합니다.
input으로 track set T, detection index들을 뜻하는 D, 최대 나이인 AmaxA_{max}가 제공됩니다.
1,2 : 관련 비용 matrix와 gate(허용된 연관성) matrix를 계산합니다. 그 후 track의 나이가 증가하면서 발생하는 선형 할당 문제를 해결하기 위해 track의 나이 n을 반복합니다.
6 : 가장 마지막 n번째 프레임에서의 detection과 연관되지 않은 track TnT_n의 부분집합을 선택합니다.
7 : track TnT_n과 매칭되지 않은 detection U 사이의 선형 assignment를 해결합니다.
8, 9 : matching set과 matching 되지 않은 detection을 업데이트하는데, 완료 후 11번째 라인에서 반환해줄 예정입니다.
위와 같은 matching cascade 기법은 더 적은 나이, 즉 최근에 더 많이 발견된 track들에게 우선순위를 부여한다는 것을 유의해야 합니다.
마지막 matching 단계에서는 확인되지도, 매칭되지도 않은 age n=1인 track 집합에 대하여 원래 SORT 알고리즘에서 제시된 것과 같이 union association을 통해 교차점을 운영합니다. 이는 갑작스러운 외형 변화(예를 들면 정적인 장면의 부분적인 occlusion)를 설명하거나, 잘못된 초기화에 대해서 견고함을 증가시키는데 도움이 됩니다.

2.4. Deep Appearance Descriptor

추가적인 metric 학습 없이 간단한 Nearest Neighbor 방식을 사용함으로써, 논문에서 제시한 방식을 성공적으로 적용하기 위해서는 실제 online tracking application 전에 offline 상에서 잘 정의된 feature embedding이 잘 훈련되어야 할 필요가 있습니다. 이를 위해 1,261명의 보행자의 1,100,000장의 이미지를 포함하는 대용량 사람 재인식 데이터셋(MARS)에 대해 훈련된 CNN을 사용하고 있고, 이는 people tracking context에서 deep metric을 학습하는데 적절합니다.
논문에서 제시하는 CNN 구조는 다음과 같습니다.
요약하자면, 2개의 convolutional layer와 6개의 residual block을 가진 넓은 residual network를 사용합니다.
128차원의 global feature map의 경우 10번째 dense layer에서 계산됩니다. final batch와 l2l_2 정규화는 특징들을 unit hypersphere에 영사시켜 cosine appearance metric과 비교가 가능하게 합니다. 2,800,864개의 parameter를 가지고 있고 Nvidia GeForce GTX 1050 mobile GPU를 사용할 때, 32개의 bounding box에 대하여 1번의 forward pass를 적용할 경우 30ms를 소요됩니다. 따라서, 이 네트워크는 현대의 GPU가 주어진다면 online tracking에 적절합니다.
학습절차에 대한 디테일은 해당 논문의 범위에서 벗어났지만, GitHub에서 사전학습된 모델을 제공하고 있습니다.

3. Experiments

MOT16 benchmark에 대하여 우리의 tracker의 성능을 평가합니다. 이 benchmark는 7개의 도전적인 test sequences에 대해 추적 성능을 평가하는데, 움직이는 카메라의 정면 촬영 장면과 위에서 아래로 감시하는 설정 또한 포함하고 있습니다. 그들은 훌륭한 성능을 제공하기 위해 public, private 데이터셋을 모아 Faster RCNN을 훈련시켰습니다. 동등한 비교를 위해, 똑같은 detection에 대해 SORT를 재학습시켰습니다.
test sequence에 대한 평가에서 λ=0,Amax=30\lambda =0, A_{max}=30 프레임으로 설정했습니다. detection의 경우 0.3이라는 confidence score에 대한 threshold를 설정하였습니다. 우리의 모델에서 남은 파라미터의 경우 benchmark에서 제공되는 분리된 훈련 sequence에서 발견할 수 있습니다. 평가 metric은 다음과 같습니다.
MOTA(Multi-object tracking accuracy) : false positive, false negative, identity switch 측면에서의 전반적인 tracking accuracy
MOTP(Multi-object tracking precision) : ground-truth와 기록된 위치 사이의 bounding box overlap 측면에서의 전반적인 tracking accuracy
MT(Mostly Tracked) : 생명주기의 최소 80%는 동일한 라벨을 가지고 있는 ground-truth track의 비율
ML(Mostly Lost) : 생명주기의 최대 20%만 추적된 ground-truth track의 비율
ID(Identity Switches) : ground-truth track의 기록된 identity switch 횟수
FM(Fragmentation) : missing detection에 의해 track이 방해를 받은 횟수
우리의 모델인 Deep SORT는 성공적으로 identity switch 수를 감소시켰습니다. SORT와 비교했을 때, id switch의 경우 1423에서 781로 약 45%가 감소하였습니다. occlusion이나 miss로부터 객체의 identity를 유지하기 위해 track 분열의 경우 미세하게 증가하였습니다. MT는 상당한 증가를, ML은 감소를 보였습니다. 전반적으로, appearance 정보의 결합으로 물체의 가려짐에서도 성공적으로 identity를 유지할 수 있었습니다.
우리의 방식은 또한 다른 online tracking 프레임워크에 대하여 강력한 경쟁자이기도 합니다. 특히, 우리의 접근 방식은 모든 online 방식 중에서 경쟁력있는 MOTA score, track fragmentation, false negative를 유지하면서도, 가장 적은 identity switch를 반환합니다. 기록된 tracking accuracy는 많은 양의 false positive로 인해 대부분 손상됩니다. MOTA score에 대한 전반적인 영향력이 주어졌을 때, detection에 큰 confidence threshold를 사용하는 것은 잠재적으로 큰 마진에 의해 우리 알고리즘의 기록된 성능을 증가시킬 수 있습니다. 그러나, tracking output을 시각적으로 점검하는 것은 이러한 false positives들이 대부분 정적인 장면에서 고립된 detector 응답들로부터 생성된다는 것을 보여줍니다. 상대적으로 큰 track의 최대 허용 나이 때문에 종종 물체에 대한 trajectory에 더 흔하게 사용됩니다. 동시에, 우리는 잘못된 알림으로부터 자주 track jumping이 발생하지 않았습니다. 대신에, 기록된 객체의 위치에서 상대적으로 안정적이고 변화가 없는 track들을 주로 생성해냈습니다. 우리의 실험은 feature를 생성하는데 걸리는 시간의 거의 절반인 20Hz가 소요됐습니다. 따라서, 현대의 GPU가 주어졌을 때 시스템의 계산이 효율적이고 실시간에서 작동할수 있습니다.

4. Conclusion

해당 논문에서는 사전 훈련된 association metric을 통해 외형 정보를 통합한 SORT에 대한 확장을 제시했습니다. 이를 통해, 더 오랫동안 방해물에 가려져 있어도 추적할 수 있게 되면서, SORT를 온라인 추적 알고리즘에서 SOTA(State Of The Art : 사전 학습된 현재 최고 수준의 신경망)수준의 강력한 경쟁자로 자리매김하고 있습니다. 알고리즘은 실행이 간편하고, 실시간 구현이 가능합니다.

Reference

SIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRIC https://arxiv.org/pdf/1703.07402.pdf

적용 및 코드

코드
Made with