DeepSORT, 제대로 이해하기

 

 

DeepSORT는 가장 널리 사용되고 있는 객체 추적 프레임워크 중 하나로,

SORT(Simple Online and Realtime Tracking)을 보완 확장한 기술입니다. 

 

 

📚  사전 지식

먼저 다룰 사전 지식은 DeepSORT에서 사용되는 기술들입니다.

미리 알면 DeepSORT에서 왜 사용되었는지, 이 기술을 써서 얼마나 더 좋아졌을지를 납득하기 위한 내용들입니다.

DeepSORT를 한 번 훑고 보는 것도 좋고, 순서에 맞게 읽어도 좋습니다.

본인이 이해하기 쉬운 순서가 무엇인지 생각하고 읽는 것을 권장합니다.

 

✔️  Kalman filter

칼만 필터는 간단하게 소개하자면, 이전 프레임에 등장한 개체를 이용하여 다음 프레임의 개체의 위치를 예측하고 측정합니다.

 

위의 그림에서 Predicted state estimate 는 예측한 값(예측 모델)이고, Measurement는 실제 측정 값(측정 모델)입니다.

Kalman filter는 이렇게 두 모델을 가지고 '더 잘 추측'하기 위해 상태를 업데이트해 나아갑니다. 

 

 

Kalman filter를 사용하는 이유는 무엇일까요?

Kalman filter는 Detection 중 발생되는 Noise를 처리하는데 도움을 준다는 점과,

영상에서의 Tracking은 선형성(물체가 순간적으로 사라지거나 나타나지 않음)을 나타내기 때문에 영상 Tracking에서 적합합니다.

 

 

Kalman filter state - Bounding Box

Kalman filter는 Bounding Box 요소로 데이터를 처리합니다.

Bounding Box(bbox)는 이미지 내의 개체를 위치를 나타내며, $[x, y, a, h, vx, vy, va, vh]$를 가집니다.

$(x, y)$는 Bounding Box의 중심 위치를 담고, $a$는 가로-세로 비율, h는 높이를 담습니다.

$vx, vy, va, vh$는 각각 요소들의 속도를 나타냅니다.

 

이 데이터들을 가지고 이미지를 추적하고, 실제 측정된 값들과 비교하며 상태를 업데이트 합니다.

저는 Github Code를 참고 하며 이해를 더했습니다. 주석이 아주 잘 적혀있어서 코드를 같이 보면 이해가 잘되더라구요.

 

 

 

✔️  Hungarian algorithm

그럼 Kalman filter에서 이전 프레임에서 발견된 개체와 다음 프레임에서 발견된 개체가 동일하다는 건 어떻게 판별할 수 있을까요?

DeepSORT에서는 이러한 판별을  표준으로 Hungarian algorithm을 사용합니다.

 

Hungarian algorithm은 최적의 매칭을 찾는 알고리즘으로 할당 문제 (assignment problem)의 해결 방법 중에 하나입니다.

Hungarian algorithm에 대한 설명을 하기 전 할당 문제라는 것을 알아보도록 하겠습니다.

 

 

📌  Assignment Problem

 

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

이해를 돕기 위해 하나의 사례를 가져왔습니다.

 

The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized.

(Wikipedia, "Assignment Problem," https://en.wikipedia.org/wiki/Assignment_problem, Wikimedia Foundation Inc., 2008.)

 

해석해보자면, 하나의 사례로 여러 에이전트와 여러 작업을 들 수 있습니다. 모든 작업을 수행하도록 에이전트를 할당할 수 있으며 에이전트 작업 할당에 따라 일부 비용이 발생할 수 있습니다. 할당의 총 비용이 최소화되도록 각 작업에 최대 한 개의 에이전트를 할당하고 각 에이전트에 최대 한 개의 작업을 할당하여 가능한 한 많은 작업을 수행해야 합니다.

 

이 할당 문제를 해결하고자 나온 것이 바로 Hungarian algorithm입니다.

 

 

📌  Hungarian algorithm

먼저, 할당 문제를 해결하기 위해 입력 값과 출력 값은 다음과 같습니다.

공급처 $I$와 수요처 $J$ 배열과 각 공급처가 각 수요처에 할당되었을 때의 비용 배열이 입력값이 됩니다.

 

예를 들어, Paul, Dave, Chris ($I$)가 청소를 해야하는데 Clean the bathroom, Sweep the floors, Wash the windows($J$)의 업무가 있다고 해봅시다. 이 때, 아래와 같이 표로 나타낼 수 있죠.

 

 

 

 

모든 행과 열에 대해, 그 행/열의 각 요소마다 그 행/열에서 가장 작은 값을 뺍니다.

그 다음 각 다른 요소에 할당되면서 0의 값을 가지는 비용들을 할당하면 가장 적은 비용을 산출해낼 수 있습니다.

 

너무 부분적으로 설명했는데, 더 깊이 알아보고 싶으시면 따로 찾아보시길 추천드립니다.

 

 

✔️  Mahalanobis distance

Mahalanobis distance는 평균과의 거리가 표준 편차의 몇 배인지를 나타내는 값입니다.

이 값은 어떤 값이 얼마나 일어나기 힘든 값인지, 또는 얼마나 이상한 값인지를 수치화하는 한 방법입니다.

 

 

예를 들어 1년 내내 매일 매일 차가 "정확히" 20대만 지나갔는데 어느날 보니 차가 21대가 지나간다면, 

굉장히 일어나기 힘든 경우이며 이상한 경우라는 것을 알 수 있습니다.

이 경우 Mahalanobis distance는 굉장히 큰 값을 가질 것입니다.

 

혹은, 차가 10대, 다음 날은 30대, 또 다른 날은 24대, ... 이와 같이 들쑥 날쑥한 경우에 21대가 지나간다면 전혀 이상한 일이 아니겠죠. 그래서 이 경우 Mahalanobis distance는 굉장히 작은 값이 나올 것입니다.

 

Mahalanobis distance는 어떤 데이터가 가짜 데이터인지, 아니면 진짜 데이터인지를 구분하는 용도로 주로 사용됩니다.

예를 들어 일일 교통량에 대한 평균을 내고자 하는데 어느날 갑자기 정말 이상한 데이터가 들어왔다면,

평균을 내는 것보다는 이것은 특이 케이스로 처리하고 정상적인 것으로 판단되는 데이터들만 이용해서 평균을 구하는 것이 보다 합리적일 수 있습니다. 

 

 

 

✔️  IOU (Intersection over Union)

IOU (Intersection over Union)은 겹치는 영역에 대해 수치화 시킨 값입니다.

겹치는 영역이 커질 수록 IOU 값이 높습니다.

 

아래 그림으로 보면 훨씬 더 잘 이해될 것입니다.

 

 

 

 

 

🔎  SORT

DeepSORT와 한 층 더 가까워졌습니다.

SORT 는 실시간 추적을 위해 object들을 효율적으로 연관지어주는 MOT(Multi Object Tracking)입니다.

이 때 MOT란 다수의 객체들을 추적하기 위해 detection 결과 간 연관(association)을 수행하는 과정입니다.

 

SORT는 Simple Online and Realtime Tracking의 약자인데요.

여기서 나타나는 Online Tracking 방식은 미래 프레임에 대한 정보 없이 과거와 현재 프레임의 객체 detection 정보만을 사용하여 연관 관계에 대한 Tracking을 수행하는 방식입니다.

 

DeepSORT는 SORT를 확장한 개념이므로, 먼저 SORT의 흐름도를 확인하면 DeepSORT를 이해하기 더 쉬울 것 같아 추가했습니다.

SORT의 흐름도는 아래 그림과 같습니다.

 

 

저도 위의 내용을 작성하고 보니까 훨씬 이해가 잘되게 되네요 ... 정리 최고 ..

하나씩 간단히 살펴보겠습니다.

 

✔️  Detections

Better Detection == Better Tracking

 

가장 먼저 Detections은 프레임에서 개체 탐지한 것을 나타냅니다.

이 과정은 대부분 YOLO를 사용합니다.

 

 

 

✔️  Estimation

그 다음  Kalman filter를 통해 개체를 추적하기 위한 측정치를 예측하고 업데이트하는 과정이 진행됩니다.

Kalman filter는 그림에서 보이듯이 예측 값과 실제 측정치를 통해 업데이트하며

다음 프레임의 값과 다시 IOU 값을 측정하는 재귀 필터 형태를 보입니다.

이러한 과정으로 인해 Kalman filter를 재귀 필터라고 합니다. 예측 & 업데이트 과정 재귀

 

 

 

✔️  Data Assosiation

Target Association은 MOT 방법을 기반으로 한 tracking-by-detection의 핵심 단계입니다.

할당에 관한 분기처리로 위에서 살펴보았던 Hungarian algorithm을 사용하면서

IOU을 Metric으로 사용하여 그림에서는 IOU Match라고 나타납니다.

 

이 단계에서는 IOU 유사도를 구한 후, 추적되고 있던 개체와 아닌 개체를 분류합니다.

이 때, 추적되고 있지 않던 개체는 두 가지로 나뉠 수 있는데요. 사라진 개체와 새로 등장한 개체입니다.

이 둘로 처리해주는 것을 확인할 수 있습니다.

또, 추적 중인 개체는 Kalman filter를 통해 다음 개체를 추적하기 위한 측정치를 업데이트합니다.

 

 

 

그런데, SORT에서 어떤 보완점이 필요해서 DeepSORT가 나온 것일까요?

 

 

 

✔️  Limit

Is deep learning really needed here ?

 

- YES.

 

Kalman filter가 뛰어나긴 하지만, 실제 상황에서 발생하는 Occulusion이나 Different View Point, ID switching 에는 불안정합니다.

 

 

📌  Occulusion

개체가 폐색 되었다? 개체가 어떤 상황에 의해 가려지는 현상을 말합니다. 아래의 사진과 같이 다른 사람들에 의해 혼자 걷고 있는 남성의 BBox가 사라진 것(Tracking X)을 확인할 수 있는데요. 이 때, 이 사물의 Tracking을 이어서 할 수 없게 됩니다. 다른 ID값을 가지게 되죠.

 

 

 

📌  ID Switching

ID Switching은 MOT의 특징 중 다양한 개체가 움직일 때, ID의 추적이 변경될 수 있다는 점입니다.

예를 들어 축구 경기를 위에서 관찰하고 있을 때, 선수들의 ID를 추적하는 상황이 제대로 이뤄지지 않는다는 점이 있습니다.

 

이때 개체의 특성을 파악해두면 Id를 구별하는데 효과적이겠죠.

Different View Point 또한 비슷한 맥락으로 이해하실 수 있을 것이라고 생각하고 다음으로 넘어가겠습니다.

 

 

 

👁‍🗨  DeepSORT

이제, 오늘의 핵심인 DeepSORT를 알아보도록 하겠습니다.

사실, 대부분의 내용을 위에서 다뤘기 때문에 핵심 로직만을 남겨두고 있습니다.

 

DeepSORT의 가장 큰 특징은 Deep Appearance Descriptor 으로 Re-identification(ReID) 모델을 적용하여 ID Switching 문제를 해결했다는 점입니다. 또한, Matching Cascade 로직으로 더 정확한 추적을 할 수 있습니다.

 

 

 

SORT WITH DEEP ASSOCIATION METRIC

 

 

간결하게 정리된 이미지와 아래는 조금 더 자세한 로직입니다.

아래의 그림을 보고 글을 계속 읽으시면 더 도움이 될 겁니다!

 

SORT에 다양한 요소가 추가 되었습니다.

 

먼저, Kalman Filter를 가지고 다음 프레임에 대해 연결되는 개체를 예측하고

결과에 따라 Matching Cascade로 개체의 상태를 추출해냅니다.

 

 

✔️  Matching Cascade

 

DeepSORT의 핵심인 Matching Cascade는 아래와 같은 Pseudo code로 확인할 수 있습니다.

이름의 의미를 개인적으로 해석해보았는데요.

Cascade는 폭포수와 비유되는 연쇄적인 작업쯤으로 생각하면, 객체 matching을 위한 연쇄적인 작업 정도로 추측합니다.

 

 

 

해석해보자면 아래와 같습니다.

 

Input.

    $\mathcal{T}$ : Tracks (예측 객체) 객체 배열의 인덱스 배열 - fyi. list(range(len(tracks)))

    $\mathcal{D}$ : 해당 프레임 내 발견 객체(Detection) 배열의 인덱스 - fyi. list(range(len(detections)))

    $A_{max}$ : 최대 Age 값

Cascade.

1. Detections와 Tracks 사이의 cost matrix $C$ 계산

2. Detections와 Tracks 사이에서 cost를 기반으로 threshold를 적용하기 위한 mask matrix $D$ 계산

3. 'Matched' matrix $\mathcal{M}$ ← 공집합으로 초기화

4. 'Unmatched detections' matrix  $\mathcal{U}$ ← Detections 으로 초기화 (매칭 시 제거)

5. 1 부터 $A_{max}$ 까지의 값을 변수 $n$에 할당하며 for Loop
      6. 마지막 $n$ 프레임에서 detection과 associate 되지 않은(age=n인) track들을 부분집합 $\mathcal{T}_n$으로 설정
      7. $\mathcal{T}_n$​의 track과 매칭되지 않은 detection $\mathcal{U}$ 사이의 최소 cost 매칭
      8. mask의 threshold 적용 후 match matrix $\mathcal{M}$에 넣기
      9. 조건에 따라 unmatched matrix $\mathcal{U}$제외

 

 

유사도 행렬 $\mathcal{M}$을 계산하는 방법은 유사도를 계산하기 위해 Motion Model(Mahalanobis distance, $d^{(1)}$)과 Cosine Distance(Appearance Descriptor, $d^{(2)}$)의 가중 평균으로 Cost Matrix (1) 를 구합니다. 이때, Matrix가 너무 커지지 않게 gate matrix를 계산합니다. 

 

$C_{i,j}=λd^{(1)}(i,j)+(1−λ)d^{(2)}(i,j)$  ···(1)

 

 

Cosine Distance는 Bounding box detection에 대해 절대값이 1인 Appearance Descriptor(ReID)입니다.

Kalman filter로 얻는 예측 상태 분포는 객체 위치에 대한 대략적인 추정치만 제공하기 때문에,

Kalman filter만으로는 설명되지 않는 모션들을 위해 Cosine Distance 도입합니다.

 

Assignment problem을 위해 Cost Matrix를 입력값으로 Hungarian algorithm을 사용합니다.

 

 

이 때 Mahalanobis distance($d^{(1)}$)의 값과 Appearance Descriptor($d^{(2)}$) 모델을 이용한다고 했는데요.

실제로는 $d^{(2)}$의 값만을 사용했을 때 ($λ=0$) 더 높은 정확도를 보인다고 합니다.

 

 

 

✔️  IOU Matching

 

위의 과정을 통해 Unmatched Tracks, Unmatched Detections, Matched Tracks 상태 배열로 개체들을 나눕니다.

Matching Cascade를 진행하고 나서 Unmatched Tracks, Unmatched Detections의 상태를 가진 개체들을 정확히 구분하기 위해

IOU Matching을 진행하고, 개체들의 상태에 따라 분기 처리됩니다.

 

IOU Matching을 다시 진행하는 과정을 통해 갑작스러운 appearance change를 구하는데 도움을 줍니다.

또, 부분적인 occlusions문제를 해결하는데 도움을 줍니다.

각 상태에 대해 알아보면 아래와 같습니다.

 

 

✔️  Matching Result

 

Matched Tracks : 계속해서 추적 중인 개체입니다. 이어서 Kalman filter를 Update합니다.

 

Unmatched Detections : 새롭게 등장한 개체입니다. 새로운 Track으로 개체를 정의하지만 Tentitive상태로 구별하였다가 3번 등장할 때 Confirmed로 변경됩니다.

 

Unmatched Tracks : 추적되던 개체를 발견하지 못했을 때입니다. 개체 추적이 안된다면 바로 삭제하는 게 아니고 다시 나타날 가능성이 있기 때문에 tentative 상태를 가지고 time_since_update 변수를 사용해서 상태를 지켜봅니다.

만약, 일정 기간 동안 (time_since_update>max_age) 발견되지 않는다면 Track 에서 제외됩니다. 

다시 등장하게 된다면, time_since_update를 0으로 초기화 시키고 다시 추적 상태로 돌아갑니다.

 

 

✔️  Pros & Cons

장점 

👉🏻 매우 빠른 Object Detector 덕분에 빠르게 추적합니다.
👉🏻 real-time 애플리케이션에 사용할 수 있습니다.
👉🏻 높은 정확도를 보이며, SORT에 비해 ID Swithing이 줄어들었습니다.

단점
👉🏻 CPU와 GPU가 모두 필요합니다.

CPU는 계산이 느리고 실시간 처리에 적합하지 않고, GPU는 자체적으로 구동할 수 없어서 비용과 전력 소비 측면에서 다소 비싸집니다.

👉🏻 feature에 배경 정보가 너무 많아서 Object Detector의 bounding box가 너무 크게 잡힐 때 알고리즘의 효과가 저하됩니다.
👉🏻 어두운 환경에서는 성능이 약간 저하됩니다.

 

 

 

아래 그림은 이해하는데 큰 도움이 되어서 같이 첨부합니다.

 

 

 

 

 

 

 

참고 문헌

 

- SORT Paper : "SIMPLE ONLINE AND REALTIME TRACKING"

- DeepSORT Paper : "SIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRIC"

- Github Source

- Assignment problem Paper : "The Optimal Algorithm for Assignment Problem"

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

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

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

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

- https://darkpgmr.tistory.com/41 : Mahalanobis distance

 

 

 

 

 

 

TMI 작성 후기

캡스톤디자인 프로젝트를 진행하면서 DeepSORT를 사용하여 Object Tracking을 구현해야하는 기회가 생겼습니다. 처음에는 그래도 사용할 기술의 원리는 알아야한다는 마음으로 논문도 읽고 Github 코드들도 참고하며 정리하게 되었는데,,, 좋은 자료들이 많아 다행이었지만, 프랑스어와 중국어 사이트를 만나면서 재차 확인하는 과정이 조금 버거웠던 것 같습니다.

생각보다 길어진 힘든 과정이었지만 새로운 내용을 배우면서 재미를 느꼈습니다. 논문을 읽고 정리하는 것도 꽤나 재미있었는데,  그래서 더 자세히 알아보려고 시간은 배로 들었고 ㅎㅎ 욕심이 커져서 이것저것 알아보고 정리하는데까지 조금 시간이 걸리네요. 덕분에 이번 프로젝트 관련 논문을 작성하는데 큰 도움이 됐고, 새로운 기술에 대해 알게 되면서 견문도 넓어진 것 같아 더 알아보고 싶다는 생각입니다