20200530 SIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRIC 논문 분석 (Deep SORT)

작성자 : 윤나라

 

트래킹은 단순한 object detection을 넘어 객체들 각각을 구별할 수 있도록 identification 하는 것입니다. objectory 추적 등 다양한 분야에 쓰일 수 있습니다. 이 트래킹 알고리즘 중 가장 많이 쓰이는 것이 SORT 알고리즘인데, 여기에 deep cosine metric을 적용하여 좀 더 성능을 향상시킨 deep sort에 관해 알아보고자 합니다.

 

 

 

 

 

ABSTRACT

SORT는 단순하고, 효과적인 알고리즘에 집중한 multiple object tracking에 대한 실용주의적 접근이다. 이 논문에서는 SORT의 성능을 향상시키기 위해 appearance information을 통합시킨다. 이 확장 덕분에, 우리는 더 긴 기간 occlusion 된 물체를 추적할 수 있고, 효과적으로 identity switches의 개수를 줄일 수 있다. 원래의 프레임워크에서, 우리는 computational complexity를 offline pre-training stage에 배치하여 large-scale person re-identification dataset에서 deep association metric을 학습한다.

온라인 오프라인 학습

- 오프라인 학습: 시스템이 점진적으로 학습할 수 없다. 가용한 데이터를 모두 사용해 훈련시켜야 한다. 시간과 자원을 많이 소모하기 때문에 오프라인에서 가동된다. 시스템을 훈련시키고 적용하면 더 이상의 학습 없이 실행이 된다. 따라서 새로운 데이터에 대해 학습을 하려면 전체 데이터를 사용하여 시스템의 새로운 버전을 만들어 처음부터 다시 훈련해야 한다.

-  온라인 학습: 미니배치라 부르는 작음 묶음 단위로 주입하여 시스템을 훈련시킨다. 연속적으로 데이터를 받고 빠른 변화에 스스로 적응해야 하는 시스템이 적합하다.

 

 

 

online을 적용한 동안에, 우리는 visual appearance space에서 nearest neighbor queries를 사용하여 measurement-to-track association을 세웠다. 실험 평가 결과, 우리의 확장이 identity switch의 수를 45%까지 감소시켜, 높은 프레임률로 전반적인 경쟁적 성능을 달성하는 것으로 나타났다.

 

 

 

 

1. INTRODUCTION

최근의 object detection의 진보로 인해, tracking-by-detection은 multiple object tracking에서 leading paradigm이 되었다. 이 패러다임에서, object trajectory는 보통 전체 video batch들을 한번에 처리하는 global optimization problem이 있었다. 그러나 이 batch processing때문에, 이 방법은 target identity 각 time step에서 이용가능해야 하는 online scenario에서 적용될 수 없다.

SORT는 이미지 공간에서 Kalman filtering을 수행하고 bounding box overlap을 측정하는 association metric과 함께 Hungarian method를 사용하여 frame-by-frame data association을 수행하는 더 간단한 framework이다. 이 간단한 접근은 높은 프레임율로 수행을 성취하게 한다.

MOT 챌린지 데이터 세트[13]에서 최첨단 사람 검출기[14]가 있는 SORT는 표준 검출기의 MHT보다 평균적으로 높은 순위를 차지한다. 이것은 전체적인 추적 결과에 대한 물체 검출기 성능의 영향을 강조할 뿐만 아니라 실무자의 관점에서 볼 때 중요한 통찰력이기도 하다.

SORT는 tracking precision와 accuracy면에서 전반적으로 양호한 성능을 달성하면서도 상대적으로 높은 수의 identity switches를 반환한다. 이는 employed association metric는 state estimation uncertainty이 낮을 때만 정확하기 때문이다.

따라서 SORT는 일반적으로 정면 카메라 장면에 나타나기 때문에 occlusion을 추적하는 데 결함이 있다. 우리는 이 문제를 motion과 appearance information를 결합한, 좀 더 정보에 입각한 메트릭으로 대체함으로써 극복한다.

 

 

 

2. SORT WITH DEEP ASSOCIATION METRIC

우리는 반복적인 Kalman 필터링과 프레임별 데이터 연관성을 가진 전통적인 단일 가설 추적 방법을 채택한다. 다음 절에서는 이 시스템의 핵심 구성 요소에 대해 자세히 설명한다.

• 칼만 필터 : 잡음이 포함된 측정치를 바탕으로 상태를 추정하는 재귀 필터. 예측, 업데이트의 두단계로 이루어짐. 예측 단계에서 현재 상태 변수의 값과 정확도를 예측하고, 실제 측정값이 들어오면 업데이트 단계에서 차이를 반영해 현재의 상태 변수를 업데이트 한다.

 

 

2.1 Track Handling and State Estimation

Track handling과 Kalman filtering framework는 대부분 SORT 알고리즘의 원래 공식과 비슷하다.

우리는 1)”카메라가 보정되지 않은 상태”와 2)”이용할 수 있는 ego-motion information”이 없는 매우 일반적인 tracking 시나리오를 가정한다.

그러므로 우리의 tracking 시나리오는, 바운딩 박스 중앙 좌표(-2개), aspect ratio (가로세로비율-1개), height(-1개), 그리고 영상 좌표(xywh-4개)에서의 respective velocities를 포함한 8차원 state space에서 정의된다.

순서대로 바운딩 박스 중앙 좌표값 두개, 가로세로 비율값 하나, height 하나, 이미지 좌표에서 상대속도 값

우리는 등속 운동과 선형 관측 모델을 가진 표준 칼만 필터를 사용하며, 여기서 바운딩 좌표를 물체 상태의 직접 관측으로 삼는다. 각 트랙 k에 대해 우리는 마지막으로 성공한 Measurement Association ak 이후의 프레임 수를 계산한다.  이 카운터는 칼만 필터 예측 중에 증가하며, 트랙이 측정과 연관되었을 때 0으로 재설정된다. 사전 정의된 최대 age인 Amax를 초과하는 트랙은 scene을 떠난 것으로 간주되어 트랙 set에서 삭제된다. 기존 트랙과 연결할 수 없는 각 detection마다 새로운 트랙 가설이 시작된다. 이 새로운 트랙은 처음 세 개의 프레임 동안 잠정적인 것으로 분류된다. 이 기간 동안 각 단계마다 성공적인 측정 연관성을 기대한다. 첫 번째 세 프레임 내에서 측정과 성공적으로 연결되지 않은 트랙은 삭제된다.

 

 

2.2  Assignment Problem (할당 문제 : 근본적인 조합 최적화 문제)

예측된 칼만 states와 새로 도착한 측정 사이의 연관성을 해결하는 전통적인 방법은 헝가리안 알고리즘을 사용하는 것이다.

이 문제 공식에 있어, 우리는 두 가지 적절한 측정지표의 조합을 통해 움직임과 appearance information을 통합한다.

 

(1) 움직임 정보를 통합하기 위해, 예측된 Kalman states와 새로 도착한 측정치 사이의 (제곱된) 마할라노비스 거리를 사용한다.

여기서 우리는 i번째 트랙 분포에서 measurement space로의 projection을 (yi, Si)로, j번째 바운딩 박스 검출을 dj로 나타낸다.

마할라노비스 거리는 state estimation uncertainty의 측정을 detection이 평균 track location으로부터 얼마만큼의 표준편차가 떨어져 있는지를 계산함으로써 고려한다. 또한, 이 측정지표를 사용하면 inverse X^2 분포에서 계산한 95% 신뢰 구간에서 마할라노비스 거리를 임계값화하여, 예상할 수 없는 연관성을 배제할 수 있다. 우리는 이 decision을 밑의 지표로 표시한다.

i번째 track과 j번째 detection 사이의 연관성이 인정된다면 지표는 1로 평가된다. 4차원 측정 공간의 경우 해당 마할라노비스 임계값은 t(1)=9.4877이다. 마할라노비스 거리는 움직임의 불확실성이 낮을 때 적절한 연관성 측정지표가 되지만, 우리의 image-space problem formulation에서는, 칼만 필터링 프레임워크에서 얻은 예측 상태 분포는 객체 위치에 대한 대략적인 추정치만 제공한다.

특히, 설명되지 않은 카메라 동작은 영상 평면에 급속한 변위를 일으킬 수 있어, 마할라노비스 거리는 발생을 추적하기 위한 다소 형식적이지 않은 측정지표가 된다. 그러므로 우리는 두번째의 측정지표를 assignment problem에 통합시켰다.

 

(2) 각각의 바운딩 박스 디텍션 dj에 대해, 우리는 절대값이 1인 appearance descriptor인 rj를 계산했다.

또한 각 트랙 k에 대한 appearance descriptor 마지막 100개를 가지는 갤러리인 Rk를 보관한다.

그렇게 되면, 우리의 두번째 측정지표는 appearance space에서 i번째 track과 j번째 detection 사이의 제일 작은 cosine distance를 측정한다.

다시 말해, 우리는 측정 지표에 따라 연관성이 허용되는지 여부를 나타나는 이진 변수를 소개한다.

그리고 우리는 나눠진 training dataset에서 이 indicator에 대해 적절한 임계값을 찾았다. 실제로 우리는 사전에 훈련된 CNN을 바운딩 박스 appearance descriptor들을 계산하는데 적용했다. 이 네트워크의 구조는 Section 2.4에 설명되었다.

두 지표가 결합하면, 두 지표가 서로 다른 assignment 문제를 처리함으로써 상호 보완된다.

먼저, 마할라노비스 거리는 단기 예측에 특히 유용한 움직임에 기초하여 가능한 물체 위치에 대한 정보를 제공한다.

반면에 코사인 거리는 동작이 덜 discriminative 한 경우 장기간의 occlusion 후 동일성을 recover하는데 특히 유용한 appearance 정보를 고려한다.

Association problem을 작성하기 위해 가중합계를 사용하여 두 측정지표를 결합한다.

여기서 두 측정지표의 gating 영역 내에 있다면 연관성이 인정된다고 한다.

결합된 연관성 cost에서 각 측정지표의 영향력은 하이퍼파라미터 람다에 의해 control 될 수 있다. 우리의 실험 동안에서 우리는 상당한 카메라 움직임이 있을 때 람다=0으로 정하는 것이 합리적인 결정이라고 밝혀냈다. 람다가 0일때는 appearance 정보만 연관성 cost term에 사용된다.

그러나 마할라노비스는 여전히, 칼만 필터에 의해 추론되는 가능한 물체 위치에 기초하여 실행 불가능한 할당을 무시하는 데 사용된다.

 

 

2.3  Matching Cascade

Global assignment 문제에서 측정-추적 연관성을 해결하기보다는, 우리는 일련의 하위 문제를 해결하는 cascade를 도입했다. 이 접근방식에 동기를 부여하기위해, 다음 상황을 고려하였다.

물체가 더 긴 시간 동안 occlude되면, 뒤따라오는 칼만 필터 예측은 object location과 관련된 불확실성을 증가시킨다. 결과적으로, 확률 질량은 state space에서 퍼져 나가고, 관측 가능성은 덜 정점을 찍게 된다. 직관적으로, 연관성 측정지표는 measurement-to-track distance를 증가시킴으로써 이러한 확률 질량의 확산을 설명해야 한다.

반대로, 두 트랙이 동일한 탐지를 위해 경쟁할 때, 마할라노비스 거리는 더 큰 불확실성을 선호한다. 왜냐하면, 그것은 투사된 트랙 평균을 향한 어떠한 검출이든 표준 편차 거리를 효과적으로 감소시키기 때문이다. 이는 트랙 파편화와 불안정한 트랙으로 이어질 수 있기 때문에 바람직하지 못한 행동이다.

따라서, 우리는 연관 가능성 확산의 개념을 인코딩하기위해 더 자주 보이는 물체에 우선순위를 부여하는 매칭 계단식(matching cascade)을 도입한다.

Listing 1은 우리의 일치 알고리즘을 요약한다. 입력으로 우리는 최대 연령 Amax뿐만 아니라 트랙 T와 검출 D 지수 세트를 제공한다.

라인 1과 라인 2에서는 관련 비용 매트릭스와 허용된 연관성 매트릭스를 계산한다. 그리고 나서 우리는 나이가 증가하는 트랙에 대한 선형 할당 문제를 해결하기 위해 트랙 나이 n을 반복한다.

라인 6에서는, 마지막 n개 프레임에서 detection과 연관되지 않은 트랙 Tn의 부분집합을 선택한다.

라인 7에서, 우리는 Tn안의 트랙과 match되지 않은 detection U 사이의 linear assignment를 해결한다.

8번과 9번 라인에서는 일치된, 일치되지 않은 detection 세트를 업데이트하고, 11번 라인에서 완료한 후 반환한다.

이 matching cascade는 더 적은 나이의 track들, 즉 최근에 더 많이 본 트랙에 우선 순위를 부여한다는 점에 유의해야한다.

최종 matching stage에서, 우리는 확인되지 않고 일치되지 않은 age n = 1의 트랙들의 집합에 대한 원래 SORT 알고리즘[12]에서 제안된 대로 union association을 통해 교차점을 운영한다. 이는 갑작스러운 appearance change들을 설명하는데 도움을 준다. 예를 들어, static scene geometry의 partial occlusion, 그리고 잘못된 초기화에 대한 견고성을 증가시킨다.

 

 

2.4 Deep Appearance Descriptor

추가 측정 지표 학습 없이 간단한 nearest neighbor queries를 사용함으로써, 우리의 방법을 성공적으로 적용하려면 실제 actual online tracking application전에 offline에서 well-discriminating feature embedding이 잘 훈련되어야 한다. 이를 위해 우리는 1,261명의 보행자의 11만 개 이상의 이미지를 포함하는 대규모 re-identification dataset(MARS)에 대해 훈련된 CNN을 사용하고 있으며, 이는 people tracking context의 deep metric learning에 적합하다.

우리 네트워크의 CNN 아키텍처는 표 1에 나와 있다.

요약하면, 우리는 두 개의 convolutional layer와 여섯 개의 residual 블록을 가진 넓은 residual network를 사용한다.

차원 128의 global feature map은 dense layer 10에서 계산된다. Final batch와 L2 정규화는 feature들을 unit hypersphere이 우리의 cosine appearance metric과 compatible 할 수 있도록 project한다. 네트워크는 총 2,800,864개의 매개변수를 가지고 있으며, 32개의 경계 상자의 1개의 forward pass는 Nvidia GeForce GTX 1050 모바일 GPU에서 약 30ms가 걸린다.  그러므로 이 네트워크는 현대의 GPU를 이용할 수 있다면 online tracking에 적합하다.

트레이닝 절차의 세부 사항은 본 문서의 범위를 벗어나지만, GitHub 저장소 1에 기능 생성에 사용할 수 있는 스크립트와 함께 사전 교육된 모델을 제공한다.

 

 

 

4. CONCLUSION

우리는 사전 훈련된 association metric을 통해 appearance information을 통합한 SORT에 대한 확장을 제시했다. 이 연장선상에서 우리는 더 오랜 기간 동안 occlusion 상태를 추적할 수 있어 SORT가 최첨단 온라인 추적 알고리즘의 강력한 경쟁자로 자리매김하고 있다. 알고리즘은 실시간 구현과 실행이 간단하다.