천천히 꾸준히

SORT 논문을 학습중에 헝가리안 알고리즘이란 것을 쓴다는데... 도대체 이건 또 뭔지 알아보려고합니다.. 

Hungarian Algorithm이란?

헝가리안 알고리즘이라는 것은 assignment problem을 해결하는 최적의 솔루션(optimal solution) 입니다. 

그럼 먼저 assignment problem이 뭔지?,

그리고 어떻게 헝가리안 알고리즘이 사용하는지? 

알아보겠습니다.

assignment problem이란?

직역하면 할당 문제입니다.
어떻게 하면 가장 효과적으로 할당할 것이냐의 문제인데,
예를 들면, 회사에서 외주를 맡겨야 할 일이 3개가 있다고 한다면(식당, 보안, 환경관리)
해당 일들을 3개의 업체에 맡겨야 하는데 어떻게 맡기는것이 가장 효과적인가 하는 문제입니다.

아래는 각 업체별 업무에 따른 가격이 나와있습니다.

Optimal Solution (Hungarian algorithm)

위와 같은 상황에서 어떻게 하면 회사는 가장 저렴한 가격으로 각각의 업무를 부여할 수 있을까요?

이것을 해결하는 방법은 다음과 같은 절차를 따릅니다.  

1. 행에 대해서 가장 작은 값으로 뺀다

    -> 이 이유는 A업체에 각각에 비용에 3을 빼더라도 환경관리가 가장 싸고, 보안관리가 가장 비싸다는 내용 자체의 변화는 없기 때문입니다. 동일하게 행에 해당하는 B,C 업체도 동일하게 진행해줍니다.   

2. 열에 대해서 가장 작은값으로 뺀다.

이유는 동일합니다. 식당일은 1을 빼더라도 A,C업체가 가장 싸고 B업체가 비싼것에는 차이가 없기 때문입니다.

이렇게 얻은 행렬에서 0의 값을 가지는 업체-업무 쌍만 알게된다면 가장적은 비용으로 모든 업무를 처리해 낼 수 있을것입니다. 단 여기서 값에 해당하는 모든 행과 열은 0 이상의 값이여야 최적화를 할 수 있습니다. 

3. 모두가 0이되는 행과 열을(minimum-size vertex cover) 제외하고 가장 작은 값을 찾아 모든 행에 빼줍니다.

4. 음수가 되는 행렬의 원소를 음이 아닌수로 만들어 줍니다. 

최종적으로 A업체 - 식당, B업체 - 환경관리, C업체 - 보안관리가 최적의 선택이라는 결과가 나옵니다.

이 같은 알고리즘이 바로 헝가리안 알고리즘입니다. 

reference

https://gazelle-and-cs.tistory.com/29

이번에는 SORT논문에 대해서 학습한 내용을 적어보려고 합니다.  

Abstract

- the main focus is to associate object efficiently for online and realtime application

- Using rudimentary combination (kalman filter, hungarian algorithm)

- detection quality is identified as a key factor influencing tracking performence

- very fast 

Introduction

- lean implementation of tracking by detection

- because of just using the previous and the current frame, so this work is efficient

- nowdays benchmark are shown that we make the track more simple and more well it can perform

- because the detection quality is a key factor of tracking quality

- MOT problem can be viewed as a data association problem

- nowdays many tracker are using various methods  

- a resurgence of mature data association

- the only tracker is also the top ranked tracker, suggesting that the dectection quality could be holding back the other trackers

- occam's razor -> only the bbox poisition and size are used for motion estimation and data association

- this work focuses on efficient and reliable handling of the common frame to frame associations

- CNN + Kalman filter and hungarian algorim <- this formulation of tracking facilitates both efficiency and reliability

tracking을 두가지 분류로 나눌수 있다. 

online tracking vs offline tracking 

- offline tracking : betch based tracking 

tracking by detection vs detection by tracking

METHODOLOGY

 1.detection

 2.propagating object states into future frames

 3.associating current detection with existing objects

 4.managing the lifespan of tracked objects

Estimation model

used a linear constant velocity model which is independent of other objects and camera motion

u : horizontal pixel of the center of the target

v : vertical pixel of the center of the target

s : scale of the target's bounding box

r : aspect ratio of the target' bounding box -> aspect ration is considered to be constant

when a detection is associated to a target -> the detected bbox is used to update the target state where the velocity components are solved optimally via a kalman filter framework

if no detection is associated to the target, its state is simply predicted without correction using the linear velocity model

Data association

- The assignment cost matrix is then computed as the intersection-over-union (IOU) distance between each detection and wall predicted bounding boxes from the existing targets.

- The assignment is solved optimally using the Hungarian Algorithm.

- A minimum IOU is imposed to reject assignments where the detection to target overlap is less than IOUmin.

Creation and Deletion of Track Identities

- For creating trackers, we consider any detection with an overlap less than IOUmin to signify the existence of an untracked object.

- Tracks are terminated if they are not detected for Tlost frame

CONCLUSION

- Tracking quality is highly dependent on detection performance and by capitalising on resent developments in detection

- SORT achieves best in class performance with respect to both speed and accuracy

추가 공부 해야할것

- kalman filter : 센서의 노이즈를 잡기위한 재귀필터

- humgarian algorithm : assignment problem 을 해결하기 위한 optimal solution

- Occam's Razor : 문제를 해결하기 위한 2가지의 방법이 있을때, 좀 더 쉽고 간단한 방법을 선택하는것

단어 정리

• pragmatic: 실용적인, 실용주의의, 현실적인
• rudimentary: 기초적인, 초보적인, 기본적인
• lean implementation: 간결한 실행, 미약한 구현
• resurgence: 부활, 재생, 되살아남
• hypothesis tracking: 가설 추적, 가설 추론
• could be holding back: 지연시킬 수 있다, 방해하고 있을 수 있다
• explicit: 명시적인, 분명한
• myriad: 무수히 많은, 수많은
• robust: 견고한, 강건한, 튼튼한
• leverage: 영향력을 행사하다, 활용하다
• pragmatic: 실용적인, 실용주의의, 현실적인
• impractical: 비현실적인, 실현불가능한

추가로 궁금한점 왜 kalman filter에서 linear하게 문제를 바라봤을까? 가속도나 다른방법으로는?? 

reference

https://arxiv.org/pdf/1602.00763.pdf

https://github.com/abewley/sort