DeepSORT: SORT with a Deep Association Metric
この記事では、2017年に発表され、現在の多物体追跡（Multiple Object Tracking）に影響を与えているDeepSORTについて解説します。
DeepSORTの論文Simple Online and Realtime Tracking with a Deep Association MetricはArXivに公開されており、実装deep_sortはGitHubに公開されています。
Overview
関連記事で紹介しているSORT（Simple Online and Realtime Tracking）は、2016年に発表されたリアルタイム性を重視した多物体追跡の方法です。ただし、SORTは、そのアルゴリズムをシンプルに保つため、物体の外観特徴（Appearance Feature）を使用しておらず、短期および長期のオクルージョンに関する課題にも対応しない設計です。このため、SORTの課題は、オクルージョンなどによって、トラックのID（Identity）が変化するIDスイッチが発生しやすい点です。
上記のSORTの課題を改善するために2017年に発表された方法が、DeepSORT（Simple Online and Realtime Tracking with a Deep Association Metric）です。DeepSORTでは、深層学習（Deep Learning）モデルが出力する外観特徴量からコスト行列を作成し、そのコスト行列を用いてデータアソシエーション（Data Association）を行います。この結果、IDスイッチを45%削減することに成功しています。
なお、DeepSORT論文の第二著者は、SORT論文の筆頭著者です。
DeepSORT
DeepSORTでは、物体検出モデルによって検出されたバウンディングボックス領域に対して深層学習モデルを用いて外観特徴量を出力します。深層学習モデルからの外観特徴量は、トラックに保存されている外観特徴量とのコサイン距離を要素とするコスト行列に変換され、データアソシエーションに利用されます。データアソシエーションには、マッチングカスケード（Matching Cascade）と呼ばれるアルゴリズムが採用されています。マッチングカスケードでは、検出とのマッチングを直近で更新されたトラックから順番に行います。データアソシエーションによって対応する検出が得られたトラックには、対応する検出の外観特徴量とカルマンフィルタによって更新された状態推定値が保存されます。
Core Components of DeepSORT
ここでは、DeepSORTのコアコンポーネントを見てゆきます。
論文には、以下の4つコアコンポーネントが示されています。
- Track Handling and State Estimation
- Assignment Problem
- Matching Cascade
- Deep Appearance Descriptor
SORTとの違いを交え、上記の順に詳細を見ていきましょう。
Track Handling and State Estimation
SORTとDeepSORTでは、トラックの取り扱いが異なります。トラックを削除する条件が、SORTでは1種類ですが、DeepSORTでは2種類に増えています。
SORTでは、2フレーム連続してアサインメントがなかったトラックは削除されます。
DeepSORTでは、最初の3フレームの間、トラックは暫定（Tentative）として扱われ、この間にアサインメントが成功しなかったトラックは削除されます。この条件が追加されたことにより、単発的な誤検出によって生成されたトラックを削除できます。上記で削除されなかったトラックに対しては、最後のアサインメントからのフレーム数が設定されたフレーム数 Amax を超えるまで、トラックは削除されません。なお、論文内の実験では Amax は30フレームに設定されています。これにより、オクルージョン等の影響が30フレーム以内であれば、対応するトラックが削除されていないため、IDスイッチが発生する可能性を低くできます。
なお、DeepSORTでは、状態ベクトルの一部がSORTから変更されていますが、カルマンフィルタを用いて状態推定を行うフレームワークに変化はありません。
Assignment Problem
割り当て問題への対応は、SORTとDeepSORTの違いが大きな部分です。最初に、コスト行列の作成方法を見てゆきます。
SORTでは、IoU（intersection-over-union）を用いてコスト行列を作成します。
DeepSORTでは、外観特徴ベクトルのコサイン距離とレーダでよく用いられるマハラノビス距離を組み合わせて、コスト行列を作成することができます。但し、実験では、コサイン距離とマハラノビス距離の重みが、それぞれ1と0に設定されており、コサイン距離のみを用いてコスト行列を作成していることになります。
次に、DeepSORTのコサイン距離の詳細を見てゆきます。
検出されたそれぞれのバウンディングボックスに対応する外観特徴ベクトルは、後述するDeep Appearance Descriptorを用いて生成されます。ここで、j番目の検出に対応する外観特徴ベクトルをrjと表すことにします。トラックは、アサインメントされた検出に対応する外観特徴ベクトルを新しい方から最大100個保存しています。ここで、i番目のトラックのk番目の外観特徴ベクトルをrk(i)と表すことにします。
i番目のトラックとj番目の検出のコサイン距離d(i, j)は、以下ように定義されています。
d(i, j) = min{1 – rjTrk(i) | rk(i) ∈ {rk(i)}k=1Lk}
すなわち、コサイン距離d(i, j)は、i番目のトラックが保存している外観特徴ベクトルの中から、最小のコサイン距離が選択されています。
また、DeepSORTには、SORTにはなかったゲート行列が追加されています。
ゲートも、マハラノビス距離と同様にレーダでよく用いられる方法です。基本的には、スレッショルドを用いてその値がゲート内かゲート外かを判定します。ゲート外と判定された場合、アサインメントの対象から外します。コスト行列では、マハラノビス距離の重みが0に設定されていますが、ゲート行列では、コサイン距離とマハラノビス距離の両方の結果が用いられています。
Matching Cascade
前述のように、DeepSORTでは、最初の3フレームを生き残ったトラックは、最後のアサインメントからのフレーム数が最大フレーム数 Amax 以下であれば削除されません。このため、最後のアサインメントからのフレーム数の異なるトラックが混在する可能性があります。
マッチングカスケードは、最後のアサインメントからのフレーム数が小さいトラックから順番にアサインメントを行うことにより、上記の状況に対応します。
論文では、コスト行列にマハラノビス距離を組み合わせる場合の課題が述べられていますが、論文中の実験では、コサイン距離だけを用いてコスト行列が作成されています。コサイン距離だけを用いるコスト行列に対するマッチングカスケードの効果が、気になるところです。
Deep Appearance Descriptor
DeepSORTでは、Assignment Problemに記載したように、検出されたそれぞれのバウンディングボックスに対応する外観特徴ベクトルを使用します。
上記外観特徴ベクトルを生成するのが、Deep Appearance Descriptorです。Deepの名前から想像できるようにCNN（Convolutional Neural Network）が用いられています。
まとめ
この記事では、2017年に発表され、現在の多物体追跡に影響を与えているDeepSORTについて解説しました。
DeepSORTは、外観情報を統合することによりSORTのパフォーマンスを向上させています。具体的には、物体検出モデルによって検出されたバウンディングボックス領域に対して、深層学習モデルを用いて外観特徴量を出力します。深層学習モデルからの外観特徴量はコスト行列に変換され、そのコスト行列を用いてデータアソシエーション（検出とトラックの関連付け）を行います。この結果、SORTの課題であるオクルージョンなどによるIDスイッチの数を効果的に削減しています。
