多人数トラッキング論文解説　Deep Affinity Network for Multiple Object Trackingを読む

#はじめに
最近MOT(Multi Object Tracking)に取り組んでいて論文を読んでいたので、その一つを取り上げて解説をしていこうと思います。

とりあげる論文は[Deep Affinity Network for Multiple Object Tracking](https://arxiv.org/abs/1810.11780)[^1]というものです。
[^1]: Sun, S., AKHTAR, N., Song, H., Mian, A. S., & Shah, M. (2019). Deep Affinity Network for Multiple Object Tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(9), 1–1. https://doi.org/10.1109/tpami.2019.2929520
また、ざっと検索したところMOTに関する日本語記事はそれほど多くありませんでした。あまり馴染みのない方もいると思うので、タスクの概略から振り返っていきましょう。

#MOTとは
簡単に言うとフレーム内に複数人物がいた場合にその人を区別してトラッキングをしようというタスクです。
![図1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/fd194c12-87c6-de07-c826-509c342c900a.png)

参考文献[^2]より改変して使用
  
[^2]: Ciaparrone, G., Sánchez, F. L., Tabik, S., Troiano, L., Tagliaferri, R., & Herrera, F. (2019). Deep Learning in Video Multi-Object Tracking: A Survey. 1–38. Retrieved from http://arxiv.org/abs/1907.12740
  
上図のように動画の連続した２フレームをinputとして、最初にSSDなりYOLOなりで人物の検出を行います。検出された人物には適当なidが割り当てられ、（図では1854,1855）そしてこのidは同一人物なら同じidが割り振られていなけれいけません。特にonlineなMOTでは動画を逐次読み込み,
過去と現在フレームのみを利用して検出されたbounding boxにidを割り振ることになります(未来の情報は使えない)。
したがって普通のTrackingに加え、フレーム間や人物の関連付けといった手法が必要になる難しさが存在します。例えばbounding boxで切り抜かれた画像をCNNで特徴抽出し、フレーム間で人物同士のsimirarityを算出。その後ハンガリアン法などで最適な紐付けを求めるなどの手法が考えられます。（フレーム間のperson Reidentificationですね）

ちなみにMOTの精度ですが、当然最初のdetectorの精度に大きく依存します。そのためMOTの代表的なベンチマークである[MOTChallenge](https://motchallenge.net/)などではあらかじめフレーム内のbounding box座標が共通で与えられており、associationの精度だけを評価したりします。

# Deep  Affinity Network for Multiple Object Tracking 
さて本題の論文解説に移りたいと思います。この論文の主眼は、これまでMOTにおいて難しかったフレームを跨いだidの復元を実現しているところにあります。
例えば先の図はフレーム間で同じ人物が同数問題なく検出されていましたが、もし人が混雑していれば前フレームで検出した人が隠れてしまうかもしれません。するとdetectorでの検出が困難になり、trackingが外れてしまいます。もしその後のフレームで隠れてた人が現れても、その人は新規検出と見なされて、別のidが割り当てられてしまうことになるでしょう。このようにMOTは一旦occlusionなどでTrackingが外れるようなことがあるととても難しくなってしまいます。
しかし、連続したフレームだけの関連付けをとるのではなく、隠れる前の人の特徴をどこかに保存しておいて、新しいdetectionが入った時、そことの関連付けを計算することができればこの問題を解決できるのでは？というのがこの論文のkeyになっています。

ではフレーム間の人の関連付けをどのように定式化するかというと、次図のようなassociation matrixを作ってあげます。
![スクリーンショット 2019-11-01 16.46.50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/28030f8b-8e7c-e6ca-5791-86df4525f3a5.png)
論文Fig2[^1]より
  
図の上2つの写真は異なるフレーム間（1と30）での人物の検出結果です。Frame1ではidが1,2,3,4に該当する人が検出されており、Frame30ではid 1,2,3,5に該当する人物が検出されています。ここで行をframe1で検出されたid 列をframe30で検出されたidとして、同一人物なら1、そうでなければ0とすると図cのような行列が作れますね。idのxは検出していないそれ以外のidです（行列を固定長にするためにつけるdummy id となります）。
さらに人物のフレーム間の出入りを表現するためUn-identifiedと呼ばれるidを行、列ともに追加すると図(d)のような行列が出来、これをassociation Matrixにすればフレーム間の人物の対応が表現できます。
(Frame1ではid4が検出されていますが、frame30ではid4に該当する人がいないため,行列の(4,un-identifed)のところに1が立っていますね)

このassociation Matrixが今回のネットワークの出力であり、Ground Truthになります。
　
##DAN
それではネットワークを見ていきましょう。モデル名は論文通りDAN(Deep Affinity Network)とします。下図がネットワークの概略です。
![network.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/cc87d6ea-777f-317c-7f6b-7ff50187cfd1.png)
著者githubページより[^3]
 
[^3]: https://github.com/shijieS/SST

まず入力となるフレーム画像をpretrainされたVGGとその後にさらに繋げたExtension CNNに通します。そうして各スケールに抽象化されたFeature map（ここではVGGの16層目,23層目,36層目,...の出力）を取り出します。それに対しもう一度CNNをかけ、検出した人のbounding boxの中心位置に該当するピクセルのみを取り出し、チャネル方向に繋げ、検出人物のFeature Vectorを作成します。図ではVGGの16層目の出力に1x1の60チャネルのconvolutionをかけて、中心ピクセルを取り出すことで1人あたり60のfeature vectorが得られています。それを23層目や36層目のfeatuer vectorと結合させることで最終的に1人あたり、520個のfeature vectorが得られます。
 ここでフレームでdetectされた人数がN人だとすると１フレームから520xNのfeature Vectorが得られるわけですが、フレームで検出される人数は一定とは限らないので最大人数Nmax(論文では80)を決めておき、足りない部分を0パディングすることで、全てのフレームから520xNmaxの固定長Feature Vectorを取得するようにします。
  

さてやりたいことは各フレームから得られたFeature Vector同士の関連性を見ることなので、nフレーム後のフレームでも520xNmaxのFeature Vectorを作成し、考えられる全ての組み合わせで結合し、並べることによって　(1040 x Nmax x Nmax)の３次元行列を作成します。
(補足　520個のfeature vectorはそのフレームで検出された人物一人の特徴を表しているわけですが、nフレーム後のどのfeature vectorと同一人物かわかりません。そのため、すべての組み合わせを作るため１人のfeature vector 520個をとりあえずnフレーム後の全てのfeature vecと結合させて 1040 x Nmax、そしてそれがさらに人数分なので 1040 x Nmax x Nmax になります。 )

そしてこの1040 x Nmax x Nmaxの行列にConvolutionを掛け、(1 x Nmax x Nmax)の行列にしてしまえば先のasscociation Matrixと対応づけられるようになります。(pixelの位置関係がとても大事なのでconvlutionのフィルタは1x1でなければならないのもpointです。)

対応付けられると言っても一工夫必要で、それはまだUn-identifiedが表現できていないからです。
そのため、行、列それぞれに一行づつ追加してあげる必要がありますが、同時に追加してあげて(Nmax+1) x (Nmax+1)の行列にするのではなく、行、列を独立に追加してあげた(Nmax+1) x Nmax,Nmax x (Nmax+1)の行列をそれぞれ作るそうです。(このほうがloss 計算時に便利なようです)

こうして作られた行列$M_{1}$,$M_{2}$にそれぞれrow-wise softmaxとcolumin-wise softmaxをかけて対応する人物への確率分布$A_{1}$,$A_{2}$にすることでいよいよground truth（$L_{t-n,t}$）とのLossが計算できるようになります。
Loss関数は次のようになります。
![スクリーンショット 2019-11-01 18.18.28.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/6bb4d133-ef9e-25fd-e057-88d464ec63b7.png)
細かい記号の意味などは省略しますが、ground truth行列と予測行列が一致するように、そして$A_{1}$,$A_{2}$が一致するようなLossになっています。$A_{1}$,$A_{2}$が一致するということはフレームt-nからみたフレームtの対応関係と、フレームtからみたフレームt-nの対応関係というforward/backwardの整合性が取れていることを意味します。また最後の$L_{a}$ですがこれは非最大値を抑制すると書いてありました。対応してない値はちゃんと0になるように、対応してる値は1にと確信度を上げるお気持ちでしょうか。


##Tracking 
DANを用いた具体的なTracking手順について説明します。onlineでTrackingするので、ペアとなるフレームを同時にネットワークに流し込むのではなく、取得したフレームから順にfeature vectorを作成、保存し、あらかじめ保存していた過去のフレームとのfeature vectorからassociation matrixを作っていきます。
また直前の１フレームのみで関連付けを推定しただけではidの復元などはできませんので、直近30フレームを利用しsimirarityの和をとります。
(この際、離れているフレームではやはり推論の信頼性が低下するのでsimirarityに若干のpenaltyを課しているようです。)
simirarityを計算した後は、MOTではお馴染みハンガリアン法(Hungarian algorithm)で最適なidの割り当てを決定することになります。以下の図がTrackingしている様子になります。

![スクリーンショット 2019-11-03 0.36.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/5c40fce9-fb31-97d9-1730-58d1918b9ddb.png)
論文Fig4[^1]より


上のScene6ではocclusionによりTrackingか切れているのにも関わらず、その後のフレームではまた元のidでTrackingが行われています。
下のScene7では異なるidに変わってしまったのにちゃんと復元できていることが確認できます。これはすごい!!

##結果
MOT17ベンチマークの結果が以下になります。
![スクリーンショット 2019-11-03 1.27.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/88279564-7dea-9424-9984-eabd6c4bd8ae.png)
論文Table6[^1]より

発表当時はSOTAを達成しています。ちなみにMOTチャレンジは15,16,17,19と複数あり、しかもpublicとprivate(detectorを自前で用意するか否か)で別れています。全ての結果を載せている論文は多くないため純粋な比較がしづらい部分があるので残念です。

##まとめ
今回はMOTに関する論文を取り上げてみました。この分野は論文を読んでいると、person Reidentification,時系列処理、optical flow, kalman filterなどたくさんのアプローチがあり、楽しさと同時に難しい分野だと感じています。今回の論文はCNNのみのEnd to Endなネットワークで、直感的にも理解しやすいMatrixに落としこんでいるのはいいですね。

ちなみにこの論文ですが、親切なことに[実装コード](https://github.com/shijieS/SST)、学習済みモデルが公開されており、すぐに試すことができます。READMEの手順にしたがっていけばgoogle collaboratory上でも動かせました。
またpytorchのtorchvisionで提供されているdetectorを使ったりすれば手軽に自分の用意した動画で試したり出来ます。
是非動かしてみてください！