SORT: Simple Online and Realtime Tracking

この記事では、2016年に発表され、現在のMultiple Object Tracking（MOT）に影響を与えているSORT（Simple Online and Realtime Tracking）について解説します。

SORTは、論文と実装が、それぞれArXivとGitHubに公開されています。

SORTは、動画の各フレームから検出された複数の物体のバウンディングボックス（bbox）を用いてトラッキングを行うTracking-by-Detectionと呼ばれるフレームワークを採用しています。SORTの特徴としては、その名前が示すようにシンプルかつ高速なことです。

当時の背景としては、MHT（Multiple Hypothesis Tracking）やJPDA（Joint Probabilistic Data Association）のようにData Associationに工夫を凝らした手法が、MOTベンチマークの上位を占めていました。MHTは、性能が高いもののリアルタイム性に課題があり、JPDAは、リアルタイム性があるものの性能面に課題がありました。

Tracker

ここでは、SORTの本体であるTrackerについて見てゆきます。

SORTでは、リアルタイム性を重視しており、トラッキングのための構成要素として、カルマンフィルタとハンガリアンアルゴリズムを組み合わせています。

トラッキング処理は、以下の3つのステップで構成されています。

• 第1ステップの予測では、カルマンフィルタにより、既存のトラック毎に、bboxの予測が行われます。
• 第2ステップのData Associationでは、カルマンフィルタによって予測されたbboxと、観測値である検出されたbboxとの間で、IoU（intersection-over-union）を用いたコスト行列が作成され、ハンガリアンアルゴリズを用いてトラックと観測値の割り当てが行われます。
• 第3ステップの更新では、カルマンフィルタにより、割り当てられたトラックと観測値のペアを用いて、各トラックの更新が行われます。また、既存のトラックに割り当てられなかった観測値（検出されたbbox）を用いて、新しいトラックが生成されます。更に、所定の回数更新が行われていないトラックが削除されます。

リアルタイム性を重視したSORTでは、JPDAよりも約8倍高速であり、高性能なプロセッサを用いなくてもリアルタイム性を確保することが容易になっています。

Detector

ここでは、SORTへ入力するデータを生成するDetectorについて見てゆきます。トラッキングのための構成要素をシンプルにすると、性能の劣化が心配になるところですが、どうなのでしょうか？

SORTでは、CNN（Convolutional Neural Network）ベースの物体検出モデルによって検出された物体のbboxを入力としています。論文によると、物体検出のフレームワークには、Faster Region CNN（以下、Faster R-CNN）が使用されています。

ACF（Aggregate Channel Filter）、CNNにZFを用いたFaster R-CNN（ZF）、及びCNNにVGG16を用いたFaster R-CNN（VGG16）の3種類のDetectorの性能比較結果から、Detectorの検出品質がトラッキング性能に大きな影響を与えていることが分かったとしています。ACFとFaster R-CNN（VGG16）との性能比較では、トラッキング性能の評価指標であるMOTAは、それぞれ15.1%と34.0%です。このことが、論文のアブストラクトに記載されたDetector変更による最大18.9%のトラッキング性能の向上に対応しています。

CNNベースの物体検出モデルによって検出されたデータを入力として用いることにより、シンプルなTrackerでありながらも、MHTと同等の性能を達成したことの影響は大きいと考えられます。

注意：実装としては、検出されたbboxのファイルが事前に作成されており、Detectorも含めてリアルタイム性を確保している訳ではありません。

Issues of SORT

ここでは、SORTの課題について見てゆきます。

SORT論文のトラッキング性能の評価指標を他の方式と比較すると、IDが以前のトラックと異なるIDにスイッチするIDスイッチが、SOTA（State-of-the-Art）の方式よりも良くないことが分かります。

論文には、物体の外観特徴を使用しないこと、短期および長期のオクルージョンに関する課題に対応しないことが記載されています。また、以下の2つの理由により、速いタイミングでトラックを削除する設計となっています。

• 等速モデルでは真のダイナミクスの予測には不十分
• 物体に対する再識別（re-identification）がSORTのトラッキング手法で扱える範囲を超えている

具体的には、2フレーム連続して更新されなかったトラックは削除されます。この結果、オクルージョン等によって既存のトラックに対応する物体のbboxが2フレーム連続して検出されなかった後、再び検出されたbboxに対しては、新たなIDを持つトラックが生成されることになり、IDスイッチが発生します。

SORTでは、物体の外観特徴を使用しないため、長期のオクルージョンに対応することが難しいのは分かるのですが、短期のオクルージョンにも対応しない設計になっている理由が疑問でした。

その理由として、SORTのシンプルなアルゴリズムではトラックを削除する条件は一つだけなので、Detectorからの誤検出に対応するために、結果的に短期のオクルージョンに対応できなくなったと推測しています。

まとめ

この記事では、2016年に発表され、現在のMOTに影響を与えているSORTについて解説しました。

MOT分野におけるSORTの貢献としては、以下の3つが大きいと考えています。

• 検出品質がトラッキング性能のキーファクタとして識別され、MOT分野においてCNNベースの物体検出モデルの有効性が示されていること。
• カルマンフィルタとハンガリアンアルゴリズムに基づく実用的なトラッキングアプローチが提案されていること。
• コードがオープンソース化されていること。