[Object tracking] DeepSort 이해하기

Sort의 한계

Occulusion(폐색) :  객체가 어떤 상황에 의해 가려지는 현상. Tracking의 문제에서는 사물이 사라져서 다음 프레임에서는 다른 ID값을 가지게 됨

ID Switching : 비슷한 위치에서 움직이는 다양한 객체가 있을때 ID 가 서로 뒤바뀌어 추적이 어려운 상황. DeepSort는 Deep Appearance Descriptor으로 Re-identification(ReID) 모델을 적용하여 해결

 

DeepSort 특징

다중 객체 추적을 위한 방법이다.

딥러닝의 feature extractor와 Kalman filter 기반 tracking algorithm을 결합한다.

Kalman filter는 Detection 중 발생하는 Noise를 처리하는데 도움을 주고, 영상에서의 Tracking은 선형성(물체가 순간적으로 사라지거나 나타나지 않음)을 나타내기 때문에 영상 Tracking에서 적합하고 형태가 변경되거나 다른 각도에서 볼때, 가려져서 안보일때(occlusions)와 같은 시나리오를 대처할 수 있음

Appearance updates : 조도 변화나 occlusion으로 인한 외형의 변화를 다루기 위해 각 track의 apperance feature들을 업데이트

Track management : 특정 프레임 이상 감지되지 않는 track을 제거, 동일한 객체일 가능성이 높은 track 병합

활용 분야 : 감시, 로봇 공학, 자율 주행 등

 

DeepSort를 이해하기 위한 주요 개념

Detection

비디오(연속된 프레임)에서 객체의 위치를 파악하는 검출기로, 외부의 Object detection model에 의존하여 검출된 객체의 위치를 알고리즘에 인계하는 것이다.

이 검출기는 모든 객체 감지 알고리즘(YOLO, Faster R-CNN, SSD)을 사용할 수 있다.

Feature Extraction

감지된 각 객체에서 고차원 특징 세트를 추출하여 객체의 외관을 표현하는데 사용한다.

deep appearance descriptor network는 (ImageNet 또는 COCO와 같은 데이터로)CNN을 통해 학습되어 서로 다른 객체와 클래스를 구분하는 Pre-trained universal weights와 같은 개념이다.

deep appearance descriptor network는 감지된 객체에 대해 feature를 설명할 수 있는 (128 또는 256 차원과 같이)고정된 길이의 feature vector를 출력한다.

DeepSort는 feature vector를 활용함으로써 Sort와 비교하여 외관에 대한 유사성 정보도 고려할 수 있게 되었고, 폐색, 조명, 배경, 포즈 등의 변화에 더 강건할 수 있게된다.

 Track

 DeepSort에서 시간 경과에 따른 감지된 객체의 궤적을 의미한다. 각 track은 고유 track ID와 연결되며 track이 나타내는 객체의 위치, 크기 및 동작에 대한 정보를 포함한다

나는 개인적으로 코드상에서 이 track의 개념을 track들이 모여있는 집합(list)로 이해했다.

Tracking

Kalman filter 기반 추적 알고리즘을 의미한다. 감지된 객체의 특징을 사용하여 시간에 따라 각 객체를 추적한다.

Data association

여러 객체를 추적하기 위해 필요하다. 공간과 시간에서 객체의 모양과 근접성을 기반으로 기존 track에 감지된 객체를 할당한다.

이해를 위해 "할당 문제"에 대해 학습이 필요하다. Sort에서부터 이 문제를 해결하기 위해 Hungarian algorithm을 사용했다.

Kalman filter

객체의 현 상태와 측정값을 기반으로 미래 상태를 예측하는 수학적 모델이다.

Bounding Box 요소로 데이터를 처리한다.

이미지 내의 감지된 객체의 위치를 나타내며 [x, y, a, h, vx, vy, va, vh] 를 가짐
x, y : bounding box의 중심좌표
a : 가로 대 세로의 비율
vx, vy, va, vh : 각 요소의 속도

 

State space model

시간에 따라 변하는 상태 변수들, 이와 관련된 측정값들로 모델링한다.
상태 변수 : 객체의 위치, 속도, 크기, 방향 등

 

Prediction step

State space model을 사용하여 현재 상태와 제어 입력을 기반으로 미래 상태 예측
상태 변수가 시간에 따라 어떻게 변화하는지를 설명하는 방정식의 집합으로 표현

 

Mesurement step

예측된 상태와 측정값을 사용하여 실제 상태를 추정(State estimate = Kalman filter의 출력)
새로운 측정값이 나올때마다 업데이트한다
시스템을 제어하거나 현재 상태를 기반으로 의사 결정을 내리는 데 사용한다

 

Covariance matrix

상태 추정 벡터(객체 위치의 x, y 좌표, x, y 방향의 속도)의 서로 다른 요소 간의 관계와 각 요소의 가변성을 설명하는 정사각형 행렬이다. 상태 추정치의 불확실성을 나타내는 Kalman filtering의 핵심 개념으로, 새로운 측정값이 추가될 때마다 업데이트된다. Kalman filter의 gain을 제어하고 측정값과 비교해서 예측된 상태에 얼마나 많은 가중치를 부여할지 결정하는데 사용한다. 측정 상태 및 예측된 상태와 관련된 불확실성을 기반으로 상태 추정치를 조정한다.

대각선 요소

• 상태 추정 벡터에서 해당 요소의 분산
• 측정 노이즈로 인해 객체의 위치가 불확실한 경우 위치와 관련된 공분산 행렬의 대각선 요소가 커짐
• 객체의 속도를 알 수 없는 경우 속도와 관련된 대각선 요소가 커짐

비대각선 요소

• 서로 다른 요소 간의 공분산
• 위치와 속도 불확실성 사이의 상관관계를 설명

Predicted state estimate 는 예측한 값(예측 모델)이고, Measurement는 실제 측정 값(측정 모델)이다. Kalman filter는 이렇게 두 모델을 가지고 '더 잘 추측'하기 위해 상태를 업데이트한다.

Hungarian algorithm

Assignment problem

최적의 매칭을 찾는 알고리즘이다.
다수의 공급처와 수요처가 존재하고 수송비용이 모두 다를때, 총 수송비용의 합이 최소가 되는 최적해를 찾는 것이 바로 할당 문제이다. 이때 한 공급처에서 반드시 한 수요처로만 수송이 이루어져야 함

 

기존 track에 감지된 객체를 효율적으로 할당하기 위해 사용하는 알고리즘 (= 감지된 객체가 어떤 track에 할당되어야하는가?)

Kalman filter에서 이전 프레임에서 발견된 개체와 다음 프레임에서 발견된 개체가 동일하다는 판별 표준을 제공
감지된 객체를 기존 track에 할당할 수 없는 경우 새로운 track 생성할 수 있도록 함
특정 프레임 동안 track에 감지된 객체가 할당되지 않으면 track을 제거할 수 있도록 함
비용 함수를 기반으로 감지된 객체와 기존 track 간의 최적 할당을 찾아서 Data association 문제 처리
비용 함수는 감지된 객체의 Bounding box 크기 및 aspect ratio와 같은 기타 특성뿐 아니라 감지된 객체의 특징 벡터와 기존 track 사이의 거리를 고려해서 할당의 비용을 최소화하는 것을 목표로 함

 

IOU (Intersection over Union)

겹치는 영역에 대한 수치화를 할 수 있다. 예측된 bounding box를 Ground truth와 비교할때 처럼, 비교하고 싶은 대상이 얼마나 유사한지를 알고 싶을때 사용한다.

Mahalanobis distance

평균과의 거리가 표준편차의 몇 배인지 나태내는 값
어떤 값이 얼마나 일어나기 힘든(이상한) 값인지를 수치화하는 한 방법
예를 들어 1년 내내 매일 매일 차가 "정확히" 20대만 지나갔는데 어느날 보니 차가 21대가 지나간다면, 굉장히 일어나기 힘든 경우이며, 이 경우 Mahalanobis distance는 굉장히 큰 값을 가질 것임
혹은, 차가 10대, 다음 날은 30대, 또 다른 날은 24대, ... 이와 같이 들쑥 날쑥한 경우에 21대가 지나간다면 전혀 이상한 일이 아니며, 이 경우 Mahalanobis distance는 굉장히 작은 값이 나올 것임
Mahalanobis distance는 어떤 데이터가 가짜 데이터인지, 아니면 진짜 데이터인지를 구분하는 용도로 주로 사용됨.
특이 케이스를 mahalanobis distance 로 처리하고 정상적인 것으로 판단되는 데이터들만 이용해서 평균을 구할때 사용할 수 있음

DeepSort에서

새로 감지된 객체의 feature vector와 기존 track feature 사이의 유사성을 측정하는데 사용됨.
그 다음 track에 감지된 객체를 할당하는데 사용됨.
DeepSort는 먼저 유클리드 거리를 사용하여 유사성을 계산할 수 있는 새로운 공간에 특징 벡터를 매핑하는 메트릭 함수를 학습함.
그런 다음 Mahalanobis 거리는 특징 벡터의 통계적 속성을 고려하여 이 유클리드 거리를 보다 의미 있는 거리 메트릭으로 변환 시 사용됨
DeepSort는 Mahalanobis 거리를 사용하여 특징 벡터 간의 공분산을 모델링할 수 있으므로 데이터의 기본 분포를 더 잘 추출함.
이를 통해 모양 및 조명 조건의 변화에 ​​더욱 강력해지고 복잡한 장면에서 객체를 추적하는 기능이 향상됨

 

DeepSort의 전체 Tracking Pipeline

입력
    - 객체가 감지된 프레임
    - 감지된 객체의 feature vector
출력
    - 시간에 따른 "감지된 객체"의 track

 Detection

• 프레임에서 객체를 감지
• Bounding Box로 출력

Feature extraction

• 감지된 각 객체에 대해 feature extraction을 수행하여 feature vector 집합 추출
• 이것을 위해 deep appearance descriptor network를 사용

Track initialization

• 감지된 각 객체에 대해 새로운 track을 생성하는 초기화 수행
• 감지된 객체의 Bounding box의 위치와 크기를 사용하여 track state 초기화, track ID 할당

Data association

• Hungarian algorithm으로 계산된 비용을 기반으로 가장 가능성이 높은 감지된 객체와 기존 track을 연결

Track update

• 할당된 감지 객체를 기반으로 기존 track을 업데이트
  • track 상태(위치 및 속도)는 할당된 감지 객체에 따라 업데이트
  • track 수명(track이 마지막으로 업데이트된 이후의 프레임 수) 증가
  • 여러 프레임 동안 "감지된 객체"가 할당되지 않는 track은 손실로 간주하고 제거

• Track management
  • 손실된 track 제거
  • 일치하지 않는 감지된 객체에 대해 새로운 track을 생성하여 관리

 

 

 

 

 

 

 

REFERENCE

ChatGPT

https://gngsn.tistory.com/94

DeepSORT, 제대로 이해하기

https://wansook0316.github.io/ds/dl/2021/03/14/computer-vision-17-DeepSort.html

[Computer Vision] 17: Deep Sort | 완숙의 에그머니🍳

https://medium.com/france-school-of-ai/tracking-par-computer-vision-90e5111cbb86

Tracking par Computer Vision

https://www.intechopen.com/chapters/70142

Vehicle Tracking Using Video Surveillance

https://zhuanlan.zhihu.com/p/133678626

Deep SORT多目标跟踪算法代码解析(上)

https://github.com/nwojke/deep_sort/blob/master/deep_sort/linear_assignment.py

GitHub - nwojke/deep_sort: Simple Online Realtime Tracking with a Deep Association Metric