オムライスの備忘録

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

【深層学習】DeepSORT #アルゴリズム編

Index

DeepSORT とは

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

物体追跡のアルゴリズムである Simple Online and Realtime Tracking / SORT は、
複数の物体を追跡するシンプルで効率的なアルゴリズムである.

この手法では、「外観(見た目)の情報」を「検出した物体」と「追跡している物体」の
割り当て」の指標に組み込むことで、SORT のパフォーマンスを向上させる.

この工夫を追加することで、長い期間のオクルージョンがあっても物体を追跡することが
できるようになり、ID の切り替え回数も減らすことができる.

また、元のアルゴリズムの考えに基づき、計算コストをオフラインの学習段階に
集中させ、個人を識別するために、大規模なデータセットで学習する.

Deep Simple Online and Realtime Tracking : Deep SORT

Simple Online and Realtime Tracking / SORT とは

物体追跡のアルゴリズム.
カルマンフィルターを利用する.

改善点

SORT 同様、 カルマンフィルターを利用して次フレームの追跡している物体の位置を
予測し、物体を追跡する.

次の点で改善を図る.

  • State / 状態
  • Assignment / 割り当て
  • Deep Appearance Descriptor
  • Matching Cascade

State / 状態

SORT では、「追跡している物体」が保有する情報 (State / 状態) として、以下のような形式だった.

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



しかし、以下のように変更する.

 X\ =\ (u,\ v,\ r,\ h,\ \dot{x},\ \dot{y},\ \dot{r},\ \dot{h})^{T}



  • 変更点
    •  s (面積) の撤廃
    •  h (高さ) の追加 (変化量も)
    •  r (アスペクト) の変化量を追加
    • (座標の表記も変わっている)

追跡の管理について

各「追跡している物体」に、最後に「関連付けられ」てからのカウンターを所持させる.
このカウンターは、カルマンフィルターで予測できた場合は、0 にリセットする.

また、「検出した物体」に「関連付けられ」ない場合は、+1 する.
このカウントが、事前に設定した値  A_{max} を超えた場合、フレームから外れたとみなす.

また、「関連付けられ」なかった物体は、新しい物体として登録される.

しかし、新しく登録された物体は、3 フレームの間は、暫定的な扱いになり、
その間に、「検出された物体」と正常に「関連付けられ」なければ、削除される.

Assignment / 割り当て

SORT では、前のフレームで予測した「追跡している物体」
次のフレームで新しく「検出した物体」との関連度を IoU で計算し、
Hungarian Algorithm で割り当てを行なっていた.

この仕組みに、以下の 2 つの新しい指標を追加することで、
「動きの情報」「外観(見た目)の情報」を取り入れる.

  • マハラノビス距離 / Mahalanobis Distance (動きの情報)
  • Appearance Descriptor (外観(見た目)の情報)

マハラノビス距離 / Mahalanobis Distance

「追跡してる物体」の動きの情報を取り入れるために、
「追跡してる物体」のカルマンフィルターが持つ、平均と共分散の情報を
新しく「検出した物体」と照らし合わせて、マハラノビス距離を計算する.

 d^{(1)} (i,\ j)\ =\ (d_{j} - y_{i})^{T} S_{i}^{-1} (d_{j} - y_{i})


 i 番目の「追跡している物体」の位置の分布を  (y_{i},\ S_{i}) で表し、
 j 番目の新しく「検出した物体」の BB の位置を  d_{j} で表す.

マハラノビス距離は、新しく「検出した物体」と「追跡している物体」の
今まで位置情報の平均とどれだけ離れているかを考慮できる.



しかし、マハラノビス距離だけでは、「追跡している物体」の「動きの情報」のみを
考慮しているので、予測不能なカメラの動きなどには対応できない.

Appearance Descriptor

その問題の対応のために、画像から「外観(見た目)の情報」を取り入れる.

そこで、外観記述子 / Appearance Descriptorという考えを導入する.

新しく「検出した物体」 d_{j} ことに、 | r_{j} | = 1 を満たす
外観記述子 / Appearance Descriptor  r_{j} を計算する.

さらに、各「追跡している物体」 i は、直近 100 ( L_{k}) フレーム分の
外観記述子 / Appearance Descriptor の集合  R_{i}\ =\ \displaystyle \{ r_{k}^{(i)} \}_{k=1}^{L_{k}} を準備する.


そして、この新しく「検出した物体」と「追跡している物体」の
外観記述子 / Appearance Descriptor のコサイン類似度を指標にする.

 d^{(2)} (i, j)\ =\ \min \{ 1\ -\ r_{j}^{T} r_{k}^{(i)}\ |\ r_{k}^{(i)}\ \in\ R_{i} \}



関連度の計算

新しく「検出した物体」を「追跡している物体」に
関連付けるために 2 つの指標を導入した.

マハラノビス距離は、短期間の予測に役立ち、「動きの情報」に
基づいて物体の位置に関する情報を提供する.

外観記述子 / Appearance Descriptor を用いたコサイン類似度は、
「動きの情報」の識別性が低い場合 (長いフレームで見えない等)、
「外観(見た目)の情報」を考慮することができる.

それらの 2 つを加重和として計算することで、関連度を表す指標として利用する.

 c_{ij}\ =\ \lambda\ d^{(1)} (i, j)\ +\ (1\ -\ \lambda)\ d^{(2)} (i, j)

Deep Appearance Descriptor

「Assignment / 割り当て」のために、
「検出した物体」もしくは「追跡している物体」から
外観記述子 / Appearance Descriptor を取得 (=特徴量を抽出) した.

この特徴量ベクトルを取得するため、事前に学習された CNN のモデルを利用する.

学習データとタスク

1,261 人の歩行者が映る 1,100,000 件程度の大規模な画像データセットを利用する.

歩行者の入力画像に対し、出力したベクトルを距離学習によってニューラルネットワークを最適化する.

ネットワークアーキテクチャ

2 つの畳み込み層と 6 の残差ブロックを持つ ResNet を利用する.


最終的には、128 次元の特徴量ベクトルとして出力される.

Matching Cascade

これは、「検出した物体」と「追跡している物体」を割り当てるための、細かなルールと処理の流れのこと.

Matching (割り当ての) Cascade (流れ)



  1. 「追跡している物体」 T_n\ ;\ 1,\ \cdots,\ N と「検出した物体」 D_m,\ ;\ 1,\ \cdots,\ M の準備
  2. 関連度の計算
  3. 閾値処理
  4. 「追跡している物体」の選択  T_{n}\ \leftarrow\ \{ i \in T\ |\ a_i = n\}
    • 古いものから
  5. 関連度と閾値からマッチング
  6. 「検出した物体」の一覧から削除
  7. 注意点

    物体が長い期間、何かに隠れてしまった (Occlusion) 場合、その後のカルマンフィルターの
    物体の位置の予測の不確実性が高まってしまうという問題がある.

    そのために、マハラノビス距離の許容の閾値を大きくする必要がある.

    検証

    Multi Object Tracking 16 / MOT16 を使用.

    実装

    参考

    • Simple Online and Realtime Tracking with a Deep Association Metric
      • [2017]
      • Abstract
      • 2 SORT WITH DEEP ASSOCIATION METRIC
        • 2.1 Track Handling and State Estimation
        • 2.2 Assignment Problem
        • 2.3 Matching Cascade
        • 2.4 Deep Appearance Descriptor
      • arxiv.org

    Web サイト