【物体追跡】Multi Object trackingの解説【MOT】

はじめに

こんにちは。はんぺんです。
Multi Object trackingについて調べることになったので、メモがてら記事にします。
今回は”SIMPLE ONLINE AND REALTIME TRACKING”の論文のアルゴリズムをベースにした解説で、ほぼほぼ論文紹介になります。

Multi Object trackingの概要

Multi object trackingは動画内の複数の特定の物体を追跡する技術で、対象としては人、ボール、車など多岐に渡ります。
例えば人の追跡だと、ある動画のフレームの中から人の特定を行い、IDの割り当てを行います。
もしその人が画像から消えるとIDの割り当てが終わり、新しく画像に人が入ってきたら新たにIDを付与するといった運びです。
特に技術的に難しいのは、人々へのIDの割り当てをすることで、例えば人が他の人や障害物の後ろに隠れたり、再び現れた時にどのようにIDを切り替えるかというところです。

https://www.youtube.com/watch?v=SKXk6uB8348&t=10s
Multiple object tracking with kalman tracker and sort

こちらがこのアルゴリズムを用いて生成されたMOTの動画になります。
動画から分かるように、人にはIDが割り振られており、トラッキングが正常に行われている間は同じIDが割り当て続けられますが、人同士が重なったりすると、他人とIDが入れ替わったりと、トラッキングが失敗してしますこともあります。

こちらの論文では、現在のフレーム以後のフレーム情報は用いることのできない、Onlineでの処理に対応したアルゴリズムを提案しており、特徴としては検出器にFasterRCNNを用い、カルマンフィルターとハンガリアンアルゴリズムにより検出した物体のID割り当てを行っていることです。
下図は精度と推論速度を表したグラフになりますが、従来のアルゴリズムと比較して、精度と推論速度の双方においても高い水準を示しています。

アルゴリズム

以下の要素技術を用いてMulti object trackingがなされています。

• 物体の検出

• 物体の推測

• 検出済み物体トラックへの割り当て

• トラックの作成と削除

では１つずつ見ていきましょう。

検出の検出

まずは動画のあるフレーム内から、対象物体の検出を行う必要います。
下図のように、ある動画のフレームの中に対象物体である人間が入ってきたら、検出が行われます。
緑色が検出した時に生成されるBounding Box（以下、Bbox）になります。

本論文では検出にはFaster RCNNが使用されており、これは２段階で検出を行います。
まず１段階目として特徴量の抽出で、物体が存在していると思われる範囲を見つけ、２段階目に行うのは、その物体が何であるかの分類です。
バックボーンである特徴抽出のためのネットワークは任意のものが使用でき、推論の速さと精度のトレードオフを、要件に合わせてうまく調整する必要があります。

物体の推測

次に、検出した物体の動きの推測を行います。

上記の図で緑は検出されたBbox、赤色はカルマンフィルターで予測されたBboxで、もし前述のFasterRCNNで検出を行うことができなくても、Bboxの補完が行えます。

先ほど検出した対象物体が、次のフレームでどこに位置しているかの予測を行います。
例えば、人の検出であるとすると”等速であること”と”対象物体の動きが他の物体の動きに依存しないこと”を仮定し、以下を状態とします。

x = [u, v, s, r, \dot{u}, \dot{v}, \dot{s}]^{T}

u: 水平方向の位置
v: 垂直方向の位置
s: 大きさ
r: アスペクト比

sは対象物体を検出した際に生成される、対象物体を覆う矩形のBboxの大きさで、rはそのアスペクト比を示し、論文ではこのアスペクト比は変化しないと仮定が置かれております。
物体が検出されて検出済みの物体に割り当てるために、カルマンフィルターによってBboxの状態が更新されます。
もしあるフレームで物体が検出されない場合は、線形のモデルとして対象物体の位置が予測されます。

余談ですが、この論文をベースに改良された論文のSIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRICにおいては、カルマンフィルターで予測されたBboxと検出したBboxの距離から、そのBboxを採用するかどうかを判定するアルゴリズムが追加されています。

検出済み物体トラックへの割り当て

検出した物体を検出済みの物体へ割り当てる際に、現在のフレームにおける物体のBboxの位置の予測を行います。
下図で緑のBboxは前フレームでの物体の位置で、青は最新のフレームで検出しされたBboxになります。
この時、緑のBboxと青のBboxの重なってる面積の割合がIOUであり、この値を元に割り当てが行われます。

具体的には、まず検出済みのBboxと、新たに検出したBboxとのIOU（intersaection-over-union）の算出を行います。
IOUは２つのBboxを結合した時の面積で、重なっている部分面積を割った値になります。

出典：http://kenbo.hatenablog.com/entry/2018/04/27/124749

そして算出したIOUを以って割り当てをハンガリアンアルゴリズムを用いて行います。
ハンガリアンアルゴリズムは割り当て問題を解くアルゴリズムで、今回はBboxのIOUを最大化するように割り当てを行います。

IOUには閾値が設けられており、閾値を下回るIOUを示すBboxは割り当てられません。
動画の中で物体が物陰に隠れて一時的に見えなくなること(Occlusion)がありますが、IOUによる算出によって割り当てをうまいこと処理できます。

トラックの作成と削除

対象物体がフレーム中に入ってきたり出て行ったりする時、ユニークなIDが作成・削除されます。
トラックを作成するためには、検出済みの物体のBboxと新たに検出された物体のBboxのIOUが閾値以上であることが必要です。

False positiveの低減のための工夫があります。
対象物体が一定期間(T_lost)検知されなかった場合、そのIDを破棄するという機構です。
これにより、長い期間トラッカーを保持することがなくなり、対象物体を検出できないという事によるエラーを低減することができます。
T_lostは実装では1に設定されており、この理由としては、等速モデルの予測が実際の動的な動きに対して正確ではないことが挙げられます。

評価

評価指標

Multi object trackingを１つの評価指標のみで評価するのは困難であり、評価には９つの指標が使用されます。

MOTA: Multi-object tracking accuracy
誤検出(FP)と見逃し(FN)とIDの変更の観点からの精度指標

MOTP: Multi-object tracking precision
BboxのIOUの正解と予測の観点からの精度

FAF: number of false alarms per frame.
フレームあたりの誤検出の割合

MT: number of mostly tracked trajectories.
トラックの正解ラベルに対して、８０％以上の追跡を行えた割合

ML: number of mostly lost trajectories.
トラックの正解ラベルに対して、2０％以下の追跡しか行えなかった割合

FP: number of false detections.
誤検出数

FN: number of missed detections.
見逃し数

ID sw
IDの割り当て失敗回数

Frag
見逃しによってトラックが細切れになってしまった数

他のOnlineの手法と比較して、包括的な精度指標であるMOTAの値が最も高くなっています。
また、同一トラックの中で検出がうまくできない割合を示すMLの値も、他と比べて非常に低く抑えられています。
これは、カルマンフィルターで検出できなかったフレームの補完を行なっていることが功をそうしていると考えられます。

感想

非常にシンプルなアルゴリズムで実行速度が早く、かつ精度も高い水準を示していることに驚いた。
Multi Object Trackingは他のモデルやアルゴリズムの集約によって１つのモデルとして機能するので、包括的な知識とアイディア、そして実装力が必要で非常に難しい分野であることは間違いないが、非常にチャレンジングで面白い分野であると思った。

参考

Simple Online and Realtime Tracking with a Deep Association Metricar
SIMPLE ONLINE AND REALTIME TRACKING