Index
Simple Online and Realtime Tracking / SORT とは
物体追跡 / Object Tracking のアルゴリズムのひとつ.
- 物体追跡 #まとめ編
複数の物体を追跡する Multiple Object Tracking (MOT) のアルゴリズムのひとつ.
この手法の注目点は、オンライン・リアルタイムでの実行を想定しているため、
高速で高精度なアルゴリズムであること.
このアルゴリズムでは、
物体検出 / Object Detection は別のアルゴリズムの利用を想定している.
- 物体検出 / Object Detection #まとめ編
物体追跡のアルゴリズムの中でも、重要なアイディアとして、
- カルマンフィルター / Kalman Filter
- Hungarian Algorithm
がある.
アルゴリズム
このアルゴリズムは、以下の流れで処理が進む.
- Detection / 物体の検出
- Propagating / 物体の状態を次のフレームに伝える
- Associating / 新しく検出した物体を、既存の追跡しているオブジェクトに関連付ける
- Managing / 追跡している物体の管理 (登録・更新・削除)
すでに、何らかの方法で、物体の座標が検出されたと考える.
検出した Bound Box (BB)
Propagating
「検出した物体」に対して、どのような情報 (State / 状態) を保有して、
次のフレームの「追跡している物体」に情報を渡すかを考える.
まず、各フレームごとに、「追跡している物体」がもっている状態について定義する.
検出した物体が、すでに追跡している物体だった場合
(これは、Associating で判断する)、
検出した物体の情報から、カルマンフィルターを利用して、
状態 を予測する.
- カルマンフィルター
また、検出した物体が、まだ追跡していない物体だった場合、
線形速度モデル (Linear Velocity Model) を使用して、状態 を予測する.
Associating
「検出した物体」を既存の「追跡している物体」に割り当てるために
「検出した物体」の BB (領域) と「追跡している物体」の BB (領域) の
重なり具合の指標として Intersection over Union / IoU を利用する.
Minimum IoU を設定し、この閾値以下となる「検出した物体」は関連付けられないようにする.
各「検出した物体」と各「追跡している物体」の IoU を計算後、
「検出した物体」と「追跡している物体」の割り当てを
Hungarian Algorithm を利用して決定する.
- Hungarian Algorithm
Managing
新しい物体の登録や、古い (動画に写っていない) 物体を管理するために、
新しい ID を作成したり、古い ID を削除するルールが必要.
新しい物体の登録
Minimum IoU 以下の「検出した物体」を新しい物体として登録する.
登録された「検出した物体」は、速度 (変化量) が の状態で初期化されている.
また、この時点では速度 (変化量) が観測されていないため、
カルマンフィルターでの予測で利用する速度 (変化量) の共分散は大きな値で初期化される.
さらに、新しく「追跡された物体」は、誤検出を防ぐために、
カルマンフィルターで利用する情報が溜まるまでは、新しく検出した情報を利用する必要がある.
古い物体の削除
「追跡している物体」が、ある回数フレーム () の間に検出されなければ、
その物体の追跡を終了する.
以下の 2 つの理由から、 は 1 に設定されている.
- Constant Velocity Model (Linear Velocity Model) は、予測の精度が良くない.
- 離れたフレームの物体の再識別に失敗する (異なる物体に再識別する) 恐れがある.
応用アルゴリズム
- SORT #まとめ編
参考
- Simple Online and Realtime Tracking
- [2016]
- Abstract
- 1 INTRODUCTION
- 3 METHODOLOGY
- 3.2 Estimation Model
- 3.3 Data Association
- 3.4 Creation and Deletion of Track Identities
- arxiv.org
A New Approach to Linear Filtering and Prediction Problems
- [1960] カルマンフィルター / Kalman Filter について
- http://www.unitedthc.com/DSP/Kalman1960.pdf
The Hungarian method for the assignment problem
- [1955] Hungarian Algorithm について
- https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf