オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

【動画像処理】Simple Online and Realtime Tracking / SORT #アルゴリズム編

Index

Simple Online and Realtime Tracking / SORT とは

物体追跡 / Object Tracking のアルゴリズムのひとつ.

複数の物体を追跡する Multiple Object Tracking (MOT) のアルゴリズムのひとつ.

この手法の注目点は、オンライン・リアルタイムでの実行を想定しているため、
高速で高精度なアルゴリズムであること.



このアルゴリズムでは、
物体検出 / Object Detection は別のアルゴリズムの利用を想定している.

物体追跡のアルゴリズムの中でも、重要なアイディアとして、

  • カルマンフィルター / Kalman Filter
  • Hungarian Algorithm

がある.

アルゴリズム

このアルゴリズムは、以下の流れで処理が進む.

  1. Detection / 物体の検出
  2. Propagating / 物体の状態を次のフレームに伝える
  3. Associating / 新しく検出した物体を、既存の追跡しているオブジェクトに関連付ける
  4. Managing / 追跡している物体の管理 (登録・更新・削除)

ここでは、物体検出については触れない.
すでに、何らかの方法で、物体の座標が検出されたと考える.



検出した Bound Box (BB)

Propagating

「検出した物体」に対して、どのような情報 (State / 状態) を保有して、
次のフレームの「追跡している物体」に情報を渡すかを考える.

まず、各フレームごとに、「追跡している物体」がもっている状態について定義する.

 X\ =\ (u,\ v,\ s,\ r,\ \dot{u},\ \dot{v},\ \dot{s})^{T}


  •  u,\ v は BB の中心座標
  •  s は BB の面積  s\ =\ w\ \times h
  •  r は BB のアスペクト比  r\ =\ \displaystyle \frac{w}{h}
  •  \dot{u},\ \dot{v},\ \dot{s} は単位時間あたりの変化量


検出した物体が、すでに追跡している物体だった場合
(これは、Associating で判断する)、
検出した物体の情報から、カルマンフィルターを利用して、
状態  X_{t+1} を予測する.

また、検出した物体が、まだ追跡していない物体だった場合、
線形速度モデル (Linear Velocity Model) を使用して、状態  X_{t+1} を予測する.

Associating

「検出した物体」を既存の「追跡している物体」に割り当てるために
「検出した物体」の BB (領域) と「追跡している物体」の BB (領域) の
重なり具合の指標として Intersection over Union / IoU を利用する.

ひとつの「追跡している物体」に複数の「検出した物体」が関連付けられることを防ぐために、
Minimum IoU を設定し、この閾値以下となる「検出した物体」は関連付けられないようにする.



各「検出した物体」と各「追跡している物体」の IoU を計算後、
「検出した物体」と「追跡している物体」の割り当てを
Hungarian Algorithm を利用して決定する.

Managing

新しい物体の登録や、古い (動画に写っていない) 物体を管理するために、
新しい ID を作成したり、古い ID を削除するルールが必要.

新しい物体の登録

Minimum IoU 以下の「検出した物体」を新しい物体として登録する.
登録された「検出した物体」は、速度 (変化量) が  0 の状態で初期化されている.

 X\ =\ (u,\ v,\ s,\ r,\ 0,\ 0,\ 0)^{T}



また、この時点では速度 (変化量) が観測されていないため、
カルマンフィルターでの予測で利用する速度 (変化量) の共分散は大きな値で初期化される.

さらに、新しく「追跡された物体」は、誤検出を防ぐために、
カルマンフィルターで利用する情報が溜まるまでは、新しく検出した情報を利用する必要がある.

古い物体の削除

「追跡している物体」が、ある回数フレーム ( T_{Lost}) の間に検出されなければ、
その物体の追跡を終了する.

以下の 2 つの理由から、 T_{Lost} は 1 に設定されている.

  1. Constant Velocity Model (Linear Velocity Model) は、予測の精度が良くない.
  2. 離れたフレームの物体の再識別に失敗する (異なる物体に再識別する) 恐れがある.

応用アルゴリズム

参考

  • 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

論文の構成メモ
  • Section2: 従来のMOT の追跡の分野について
  • Section3: 追跡アルゴリズム
  • Section4: 実験・検証
  • Section5: まとめと将来性



Web サイト