よりオクルージョンなどにロバストになったトラッキングアルゴリズム「OC-SORT」を解説！

はじめに
　2022年3月にカーネギー大学や香港大学の研究チームが、よりオクルージョンしてしまう物体（重なりあってみえなくなってしまう物体）や非線形的な動きをする物体のトラッキングをよりロバストに行うことを可能にした OC-SORT（Observation-Centric SORT）を発表しました。

※特に断りがない限り、以下の図は当該論文中からの引用となります。

概要

　Multi-object Tracking（MOT）は近年進歩しています。その多くは、SORTとよばれる手法を改良したものであり、基本的にはカルマンフィルターを利用して、検出した物体同士の関連性を推定します。
　SORT は高いトラッキング性能をもたらしていますが、物体が①短期間では線形的な動きをとると想定し、②継続的な観察を必要とする、という特徴があります。
　こうした特徴は、通常のトラッキングではとくに問題となりませんが、物体がオクルージョンしたときや、非線形的な動きをしたときに弱く、また高いフレームレートを必要とするという問題が指摘されてきました。
　今回の OC-SORT は「motion modeling」型のトラッキングモデルです。「motion modeling」とは、それまでの物体の動きから物体の動きを予測するモデルのことで、このことで別の物体で遮蔽されたとしても物体を正しくトラッキングすることが可能となります。特に「Observation-Centric SORT」として、物体が見えなくなったときや、物体が見えなくなった間での線形的な「motion model」によるエラーの低減時の「観測（observation）」の役割を強調しています。

SORTの限界

①動きをおおよそ線形的なものであると想定しても、高いフレームレートは多少のノイズに敏感に反応してしまう。
②オクルージョンや非線形的な動きによって新しい物体とそれまでの物体をマッチできないと、ノイズが蓄積されてしまう
③SORTは推定中心のアルゴリズムのため、「Observation」情報が補助的にしか使われない。（近年の物体検出モデルの性能向上から「Observation」情報からより情報を引き出してもよいはず。）

Observation-Centric SORT （OC-SORT）の特徴

① Observation-centric Online Smoothing（OOS）の開発：カルマンフィルターのエラーを軽減する
② Observation-Centric Momentum (OCM) の開発：tracklets の方向の一貫性をコストマトリックスに組み込むことで、tracklets と observations のマッチングを改善する
③ Observation-Centric Recovery (OCR) の開発：オクルージョンでトラッキングできなくなった物体を再び紐づける

論文の貢献まとめ

（1）分析的および経験的に、SORTの3つの制限を明らかにした。
　⇒①状態ノイズに敏感であり、②時間の経過に伴うエラーの蓄積があり、③推定中心であること。
（2）OOS、OCM、OCRの3つのイノベーションにより、オクルージョンと非線形運動の下でのロバストな追跡のためのOC-SORTを提案した。
（3）OC-SORTは、最新のMOTベンチマークでSOATのパフォーマンスを実現した。

実験結果

・MOT17⇒63.2HOTA
・MOT20⇒62.1HOTA
⇒発表されている論文のなかでは一番精度がよい

詳細

開発背景

　Multi Object Tracking （MOT）は近年進歩してきました。それらの多くは SORT とよばれるカルマンフィルターを利用したアルゴリズムを採用したものです。カルマンフィルターは線形的な動きを想定しているため、高いフレームレートが必要となります。（移動そのものを細かくみると線形的な動きとみなせるためです。）そのため、オクルージョンや非線形的な動きに弱く、低いフレームレートではトラッキングを失敗する傾向にあります。
　今回の研究チームは、それらを踏まえ、オクルージョンや、非線形的な動きをする物体に対して頑強なマルチオブジェクトトラッキングメソッドを「motion model」ベースで開発することになりました。

これまでの研究

Motion Model

　モーションモデルは、ベイズ推定を使用して、事後推定を最大化することによって次の状態を予測します。
　最も古典的なモーションモデルの1つであるカルマンフィルター（KF）は、典型的な予測更新サイクルに従う再帰ベイズフィルターです。真の状態は観測されていないマルコフ過程であると想定され、測定値は隠れマルコフモデルの観測となります。
　線形運動の仮定がKFを制限することから、1次および3次のテイラー近似で非線形運動を処理するためにExtendedKFやUnscentedKFのようなアルゴリズムが提案されています。（ただし、これらはKFによって想定されたガウス事前分布の近似に依然依存しています。）
　一方、粒子フィルターは、サンプリングベースの事後推定によって非線形運動を処理しますが、指数関数的な計算順序が必要です。ベイズ推定では、フィルタリングは過去のデータのみを使用し、平滑化（スムージング）は過去と将来の両方のデータを推定に使用します。固定ラグスムーザーと固定間隔スムーザーは、軌道全体を構築した後の時系列データフィッティングを改善するために研究されています。

Multi-object Tracking

　従来、マルチオブジェクトトラッキングは、共同確率的関連付けなどの確率的観点からアプローチされてきました。一方、最近の動画などに対するオブジェクトトラッキングは通常、オブジェクト検出によって行われます。
　 SORTは、深い検出器からの観測を前提として、カルマンフィルターを採用しています。ニューラルネットワークを利用した視覚的表現の進歩は、DeepSORTにつながりました。DeepSORT は、SORTのフレームワークでオブジェクトの関連付けに深い視覚的表現を利用します。
　外観ベースのオブジェクトマッチングも人気がありますが、多くの場合、特にシーンが混雑していてオブジェクトが粗く表現されている場合（バウンディングボックスなど）、またはオブジェクトの外観を区別できない場合は不十分とされています。
　最近、トランスフォーマーがMOT で使用され、視覚情報と軌跡の両方がエンコードされた深い表現を学習しています。これらの方法は良好な結果を示す場合もありますが、多くの場合、特にオンライントラッキングやオクルージョン下ではまだ不十分であり、モーションベースのマルチオブジェクトトラッキングに大幅な改善の余地があります。

SORTの再考

SORTについて

　カルマンフィルター（KF）は、時間領域で離散化された動的システムの線形推定量です。KFは、前の時間ステップでの推定値と現在の計測値のみを用いて、次のステップの値を保持しています。

　カルマンフィルターは、2つの変数、状態の事後状態推定xと事後推定共分散行列Pを維持します。 アクティブな制御が送信されないオブジェクト追跡のタスクでは、状態遷移モデルF、観測モデルH、プロセスノイズQ、観測ノイズRなどの他のパラメーターを使用してKFのプロセスは以下のように記述されます。

x = [u, v, s, r, u˙, v,˙ s˙]*T
(u, v) ：物体の中心座標
ｓ：バウンディングボックスの大きさ
ｒ：バウンディングボックスの縦横比
u˙, v,˙ s˙ ：関連する時間微分

z = [u, v, w, h, c]*T ：観測値
(u, v) ：物体の中心座標
w, h：幅と高さ
c ：物体の信頼度

ある観察値 zt があたえられたとき、以下のように更新されます。

問題は、何も観察されないときで（例えば、オクルージョンなどで物体がさえぎられているとき）、このときはそのままではKFは使えないことになります。シンプルな解決方法としては、前の値を持ち越して、次の値に対しても利用するという事です。 ただし、このメカニズムがMOTで問題を引き起こす可能性があることがわかります。

SORTは線形移動を想定しているので、移動モデルは以下のようになります。

そのため、以下のような式になります。

このような式である SORT は、物体同士が重ならず、高いフレームレートの場合は問題なく動くことが知られています。

SORTの限界

ノイズの影響

ノイズを踏まえて推定された中心点は、以下のようになります。

このとき、ノイズが与える影響は、物体の推定移動速度の計算式が以下のようになるため、

推定速度のノイズは以下のようになります。

連続するフレーム間での推定速度は、例えば△t=1のとき、ノイズを最大化します。それだけではなく、物体が小さい時などは推定速度が大きくずれることがあります。通常の推定であればそこまで大きな問題にはなりませんが、物体が存在しない場合に大きな問題となります。

時間的エラー倍率

　（５）の式からわかるように、位置予測は各時間に独立していることがわかります。これは物体検出という観点からは好ましいですが、それ以前の位置の情報がその後の時間に影響をあたえるという意味ではあまり好ましいとは言えません。
　通常では、そこまでおおきな問題にはなりませんが、物体が存在しない場合には、予測値を次の予測時に持ち込むため、大きなずれを生じさせる危険性があります。

時間的なエラー倍率は、以下のような式で計算できます。

そのため、エラーを踏まえた位置情報は以下のようになります。

KFのエラーは時間に対して累乗的に蓄積することを意味します。

推定中心

　推定中心であることで、実際の値とは異なる場合が生じます。
「状態推定」と「観測」の主な違いは、各フレームのオブジェクト検出器による観測がi.i.d（ノイズδz〜N（0、σ02））の影響を受けると想定できることです。

Observation-Centric SORT（OC-SORT）

　上記の SORT の限界を踏まえたうえで、Observation-Centric SORT(OC-SORT) が提案されました。観測地を利用して、物体移動のモーメンタムを導入することで、ノイズを減らし、よりオクルージョンや非線形移動にたいして頑強にすることを目的としています。

Observation-centric Online Smoothing (OOS)

　観測値の仮想軌道を経由した「オンラインスムージング」によって物体の位置を補正します。

Zt1：トラッキングが失われる前の最後の観測値
Zt2：再関連付けをトリガーする観測値

　この仮想軌跡を利用することで、エラーの蓄積を抑制することができます。最終的に、以下のように予測値を想定することができます。（この方法は、現在の時間の情報を用い、前の情報を変更しないベイジアンスムージングとは異なる点がポイントです。）

このプロセスを、「オンラインスムージング」と論文では呼びます。

Observation-Centric Momentum (OCM)

　線形的な動き以外を想定する必要があるため、モーメンタムを動きの想定に加えます。

N：トラック
M：検出値
X：推定値（X∈R**N×7）
Z：観測値（Z∈R**M×5）
V：２つの過去の観測値から計算された既存のトラックの方向（V∈R**N）
CioU：ネガティブペアワイズIoU
Cv：トラック方向と、過去の観測値のトラックと新しい観測値からなる方向の一貫性を計算したもの
λ：重み

　推定状態でのエラーの蓄積を回避するために、方向計算にトラックに関連付けられた観測値を使用していますが、どちらの2つの観測値を選択するかについてはまだ選択の余地があるとしています。（軌道は通常、短い時間間隔内の近似によってのみ線形であるため、線形近似の崩壊を回避するために、時間差を大きくしすぎないようにする必要があります。 これには、実際にはトレードオフが必要と考えられます。） 線形運動モデルでは、ノイズスケールは2つの観測点の時間差に比例するという結果に論文では達しています。

Observation-Centric Recovery (OCR)

　一般的に、壊れたトラック（ a broken track）は通常、観測損失（信頼性の低い検出器またはオクルージョン）または非線形運動に起因しています。
　観測中心トラッキングという観点からみると、失われたターゲットを回復するためにSORTを非線形に拡張することの最も穏やかな方法は追跡されなくなる場所をチェックすることです。直感的な観点からは、これは事前の軌道がないオブジェクトを再識別することに似ているといえます。その位置は、前回の存在の位置を平均とし、その失われた時間に対して分散が増加するガウス分布に従うと考えることができます。
　時間の経過に伴う伝播によって歪められた推定値ではなく、観測値を信頼するために、Observation-Centric Recovery (OCR)という手法をとります。OCR では、通常の関連付け段階の後、トラックがまだ追跡されていない場合は、このトラックの最後の観測値を新しいタイムステップの観測値に関連付けようとします。このプロセスはヒューリスティックでローカルであり、オブジェクトが停止したり、妥当な時間間隔で閉塞されたりした場合を処理できることにポイントがあります。

実験

　以下の条件で精度実験が行われました。

●データセット
MOT17 ：歩行者トラッキング（移動が線形に近い）
MOT20 ：歩行者トラッキング（移動が線形に近い）
KITTI ：低いフレームレート（10FPS）で歩行者と車をトラッキングする
DanceTrack：非線形的に動く人のトラッキング。また物体同士が近く、オクルージョンがしばしば起き、交差もよく観測される。

●利用した物体検出モデル
①　YOLOX⇒MOT17、MOT20、DanceTrack
②　PermaTrack⇒KITTI

●ハイパーパラメータの設定
・λ：0.2
・検出信頼度の閾値
　0.4：MOT20
　0.6：その他
・IoU閾値：0.3

●メトリック
　HOTA：物体検出と関連の精度をバランスよく計測する指標

MOT17に対する結果（各自で物体検出の結果が異なる場合がある）

　基本的に現在のSOTAとされるByteTrack（同様の物体検出の結果を利用）を上回った。

MOT20に対する結果（各自で物体検出の結果が異なる場合がある）

　基本的に現在のSOTAとされるByteTrack（同様の物体検出の結果を利用）を上回った。

MOT17に対する結果（同様の物体検出の結果を利用）

　HOTAでは最もよい結果となっている。

MOT20に対する結果（同様の物体検出の結果を利用）

　HOTA以外も基本的に最もよい結果となっている。

DancTrackに対する結果（同様の物体検出の結果を利用）

　最もよい精度を出した。オクルージョンなどに対して有効であることが示されているとも言える。

KITTIに対する結果（各自で物体検出の結果が異なる場合がある）

　歩行者に対しては、最もよい結果を出している。

アブレーション実験の結果

基本的に、OOS、OSM、OCRをすべて利用した方が良い結果になるが、OCRに関しては用いない方がよくなる指標もある。

OOS内での軌道仮説に対するアブレーション実験の結果

Constant Speed/Acceleration が最も良い結果となっています。

OCMにおける方向を予測する際に利用する時間に対するアブレーション実験の結果

MOT17では、△t=3 がよく、DanceTrackでは△t=6 が良い結果となっています。
∆tが大きいと、線形運動の仮定の下でノイズに対するロバスト性が向上すると考えられますが、一方である程度の値（ bottleneck ）まではパフォーマンスを改善させますが、それ以上に値をあげるとパフォーマンスの悪化をもたらします。これは、線形運動の近似をより長い時間間隔で維持するという課題に起因する可能性があることが指摘されています。

後処理としての補間に対するアブレーション実験の結果

GPR（Gaussian Process Regression）が良い結果をだせていないことなどから、今後よりよい非線形的な移動予測に対する研究が進められるべきであると研究チームは提案しています。

OC-SORTの限界

①フレームレートが低い場合やオブジェクトの動きが速い場合、正確に一致させることが難しい。
　IoUと軌道方向の一貫性のみを使用してオブジェクトを一致させることが難しい。
⇨中心距離や外観の類似性などの他の手がかりを追加すると、解決することができることが実証されています。

②ガウス過程の試みが失敗すると、SORTを非線形オブジェクトモーションに完全に拡張することが難しい。
　非線形オブジェクトモーションの基本的な拡張なしで、従来のカルマンフィルターに基づいて構築されているため、ガウス過程の試みが失敗すると、SORTを非線形オブジェクトモーションに完全に拡張することが難しい。

まとめ

　オクルージョンなどで物体が検出できない場合に対してより正確にトラッキングを可能とする OC-SORT について解説しました。現実世界では、複雑に人々が行きかう場所でのトラッキングなどを正確に行うことが求められるようになっているため、今後こうしたよりロバストなトラッキングアルゴリズムの開発が求められています。