Open IkumaUchida opened 2 years ago
本稿では，サッカーの試合映像からボールポゼッションの統計量を自動的に算出する手法を紹介する． ポゼッション統計は，各チームが行った有効なパスの数に基づいて生成されます． 有効なパスとは，ボールがプレイヤーとの間で分岐または合流したイベントとして検出される．パスは，ボールがプレーヤから分離したときに開始されます．パスは，ボールがプレイヤーと合流したときに開始され，パスは終了する． サッカーの試合で有効なパスの数をモデル化するために，最小コストのフローネットワークを使用します．
ボールとプレイヤーは，ネットワークのノードです．
ネットワークの各エッジには，ボールと選手のフレーム間の対応関係から得られるコストが割り当てられています．
ネットワークを通過する総フローは，有効なパスの数を追跡するように最適化されます．
実験結果によると，提案した手法の精度は，類似の手法と比べて少なくとも4%向上した．
実験結果から，本手法が有望かつ効率的であることがわかった．我々は，適切なコスト関数を用いてネットワークフローモデルを最適化した． このコスト関数は，ボールや選手の動きのベクトルを取り入れることで改善できる可能性がある．
また，現在実装されているSVM分類の代わりに，教師なしのチームラベリングを検討しています．
将来的には、クローズショットビデオフレームのボールポゼッション統計の結果を、ロングショットおよびミディアムショットのサッカービデオの結果と統合することを計画しています。また、ロングパス、ドリブル、オフサイド、異なるシュート、プレーブレークなど、ボールポゼッション統計に及ぼす他の状況の影響を、拡張フローネットワークモデルを用いて分析する必要がある。 また、目的関数の最適化とその実装についても、リアルタイムの結果を得るために詳細な検討が必要です。
結論
背景 ・ボール ポゼッションは勝利チームが高い傾向にある。 ・Opta Sports 社は，チームのパスカウントに基づいてボールポゼッションを計算しています [16]。 ・彼らは，試合中にチームが実行した成功したパスの数を手動でカウントする．そして，チームiのポゼッションは次のように計算される． 2f1.png) ・#Valid passes は有効なパスの数 ・同じチームの異なる2人のプレーヤーの間でパスが行われた場合、そのパスは有効とみなす。 ・各チームが成功したパスを数え、（1）を使ってポゼッション統計を生成する。
・ボールポゼッションの統計情報を生成することについては，これまでほとんど注目されていませんでした．
・[23]では，ボールの速度曲線を分析することで，パスイベントを検出しています．ボールの速度曲線における局所的な最小値または最大値は，パスの開始または終了イベントを表します．ボールの速度曲線における局所的な最小値または最大値は，パスの開始または終了イベントを表します．パスが検出されると，ボールに最も近いプレイヤーを使用して，ボールを所有しているチームの情報を取得します．パスイベントに基づいて，映像はタッチングセグメントと呼ばれる一連のセグメントに分割されます．そして，2 つのチームのタッチングセグメントの数を数えて，2 つのチームのポゼッション統計を算出します． このアプローチの大きな限界は，アルゴリズムを動作させるために，サッカーボールと選手の空間座標を入力として提供しなければならないことです． ・パスの誤検出は，速度曲線にわずかな変化がある場合に生じる．
目的 ・サッカービデオからボールポゼッションの統計を自動的に計算することです． ・ 本研究では，パス検出プロセスをグラフ理論の枠組みでマッピングする．ボールのパスイベントを検出するために，最小コストのネットワークモデルを構築します．
・パスの開始イベントでは，ボールとプレイヤーを表す連結されたコンポーネントが互いに分離します． パス終了イベントの場合，ボールとプレイヤーを表す連結成分は，互いに重なり合って1つの連結成分となる．
・最小コストネットワーク(最小費用流問題?)は、2つの連続したフレーム間で、オブジェクト（ボールとプレーヤー）が移動したり、分裂したり、合体したり、現れたり消えたりしているかどうかを検出
・最小コストネットワークは，データアソシエーションに基づくトラッキングフレームワークの下で，視覚的なオブジェクトのトラッキングに応用されている[13, 19]． ・まず，フレーム内のオブジェクトが識別されます． 次に，線形制約のある最適化関数を解くことで，対応するオブジェクトをフレーム間でリンクさせる．
・提案手法のブロック図を図2に示す ・ポゼッション統計の推定は，サッカーボールと選手を検出することから始まる．サッカービデオフレームの前景連結成分を抽出するために，[20]を実装(Yoloとかではない)。⬇︎選手検出アルゴリズム
・サッカー場を表す背景をセグメント化した後[20]，SVMを用いて前景の連結成分にラベルを付ける． クラスは，(1)ボール，(2)チームA，(3)チームB，(4)その他とする． ・分類器には，RBFカーネルを用いたマルチクラスSVM [5]を使用しています．分類には，面積，偏心率，RGBヒストグラムを特徴量として用いています．典型的な検出パイプラインを図3に示す．次節では，ボールパスの検出について説明する．
・図3. ボールと選手の検出（チームラベル付き）．ボールは黄色の四角で表示されています．2つのチームの選手は青と赤の長方形で示されています。
2.1. ボールパスの検出 ・ボールパスイベントの検出には，最小コストネットワークモデルを使用します．
・ ネットワークのエッジを通過するフローの制限を1にすることで、ネットワークを通過するパスやフローは相互に排他的であることが保証されます。 ➡︎最小経路問題
・ここでは，パスイベントを検出するために，選手とボールを表す連結成分を検出する必要があります． これらの連結成分は，前のフレームから現在のフレームに向かってsplit（パス開始の場合）またはmerge（パス終了の場合）します．
・しかし、このようなsplitやmergeのイベントは、ネットワークの1つのエッジでは1つしか処理できません。
・また，突然現れたり消えたりする選手やボールを検出するために，ネットワークに appear と disappear のノードを追加している．
2.1.1 Construction of the network ・連続する2つのフレームで検出されたオブジェクトから、フローネットワークを構築 ➡︎前のフレームのオブジェクトを現在のフレームのオブジェクトに正しく関連付けることである． ・関連付けるべきオブジェクトの数に関する事前の仮定は必要ない
・最小コストのソリューションは、フレーム間のすべてのd個のオブジェクトの正しい関連付けを提供します。
・G = (V, E)は、V個のノードとE個のエッジを持つ有向非環状グラフです。 ・ネットワークのノードは，プレイヤーやボールなどの検出された前景オブジェクトを表している ・連続するフレームLとRについて、各エッジ（u，v）∈E，u∈VL，v∈VR）は、非負のキャパシティt（u，v）≧0を持つ。 ・前のフレームLのノードはVLで表され、現在のフレームRのノードはVRで表される。 ・容量t(u,v)とは別に，各エッジは，(u,v)の単位流量あたりのコストを表す実数値のコストa(u,v)を持つ。 このコストは、uとvの間の対応関係や類似性を表しています。 ・コストは、フレーム間の正しい関連付けのために最小となります。 エッジ(u, v)上にx(u, v)個のフローを送ると、a(u, v)x(u, v)のコストが発生する。
・フローネットワークに追加される2つの頂点は、ソースT+とシンクTです。 ・ソースの頂点はフローを生成し、ターミナルの頂点はフローを消費する。 ・コストフロー問題は、ネットワークのエッジに沿ったコストとフローの積の最小化問題として定式化できる[1]。
前提として、 フローx(u,v)はエッジに対して送るコストつきの流れのこと。つまり必ずエッジ数>=フロー数
・uからwへのすべての流入フローとwからvへのすべての流出フローの差は、フロー要求値b(w)に等しい。 ・フロー要求量は、ソース頂点ではゼロより大きく、ターミナル頂点ではゼロより小さく、すべての中間頂点ではゼロであり、フロー保存制約として知られている。
・最小コストフロー問題の決定変数は、辺(u, v)上のフローであるx(u, v)である。 この問題は、フローによって発生する総コストが最小になるように、d量のフローをソースからターミナルの頂点に送ることである。
＜ここで、検出されたオブジェクトに基づいてフローネットワークを構築する。＞ ・前のフレームLでN1個のオブジェクトが検出され、現在のフレームRでN2個のオブジェクトが検出されたとする。 ➡︎バニラフローネットワークは、（N1＋N2）個のノードを有する。 ・各頂点u∈VLは、各頂点v∈VRと接続されており、uからvに向けられた結果、合計N1N2個のエッジがある。 ・各エッジは、コストa（u，v）と容量t（u，v）＝1を有する。 ・またネットワークには、送信元の頂点T+と送信先の頂点T-が追加される。 ・前フレームのすべての頂点uは、コストa(T+, u)=0、容量t(T+, u)=1のソース頂点T+からの入力エッジを持つ。 ・同様に、現在のフレームのすべての頂点vは、コストa(v, T-)=0、容量t(v, T-)=1で、末端の頂点Tへの出射エッジを持つ。
N1=2、N2=3の単純なフローネットワークを図4に示す。
・上記で提案した基本的なネットワーク・アーキテクチャは、次に述べる理由で拡張する必要があります。1つ目の修正は，プレーヤーやボールがフレームに現れたり消えたりすることによるものである．2つ目の変更点は、接続されているコンポーネントの分割や結合によるものです。これらについては次の通りです。
2.1.2 Appearing and disappearing objects ・選手やボールはフレームの中に現れたり、フレームから消えたりする。 このシナリオを取り入れるために，ネットワークには appear 頂点 A と disappear 頂点 D が導入されている． また、Rに突然物体が現れる可能性を考慮して、RのN2個の頂点はすべてLの出現頂点Aに接続されています。 Aとv∈VRを結ぶこれらの辺は、それぞれ単位容量のコストa(A, v∈VR)を持つ。 ソース頂点から出現頂点への、コストa(T+, A)=0、容量t(T+, A)=｜R｜のエッジは、フロー保存のために追加される（｜R｜はフレームRのノード総数を表す）。
・コストa(T+, A)=0、容量t(T+, A)=｜R｜のエッジは、フロー保存のために追加される（｜R｜はフレームRのノード総数を表す）。 ・辺の容量t(T+, A)は、出現頂点がRへの出射辺の数が｜R｜であることから、｜R｜と設定される。
・同様に、消えた頂点Dは、フレームLのN1個の頂点のそれぞれからのエッジを持つ。 これは、前のフレームLの各オブジェクトが次のフレームで消える可能性があることを意味する。
・ネットワークのフロー保存制約を維持するために、コストがゼロで容量t(A, D)=｜L｜のAからDへのエッジが追加される。 ・消えた頂点にはLから｜L｜個の入力エッジがあるので、エッジt(D, T-)の容量は｜L｜に設定される。 ・ネットワークのフロー保存制約を維持するために、コストがゼロで容量t(A, D)=｜L｜のAからDへのエッジが追加される。 ・このようにして、現れた頂点と消えた頂点を持つ修正されたネットワークを図5に示す。
2.1.3 Splitting and merging of objects ・オブジェクトのsplitとmergeをモデル化するために，ネットワークにはsplit頂点Sとmerge頂点Mが導入されている． ・各分割頂点は，Lの各頂点からの1つの入力エッジと，Rの2つのノードへの2つの出力エッジを持つ． ・Splitノードの各出射エッジは，コストと単位容量がゼロ ・入射辺は、コストa(u, Sv1,v2), v1, v2∈VRを持ち、単位容量を持つ。 ・現在のフレームのN2個のオブジェクトに対して、合計N2C2個の分割頂点が存在することになる。
・同様に、Lの任意の2つの連結されたコンポーネントはマージすることができる。 ・したがって、各マージ頂点は、Lの2つのノードからの2つの入力エッジと、Rの各ノードへの1つの出力エッジを有する。 ・Mの各入力辺は、コストがゼロで単位容量を持つ。 ・出て行く辺は、コストa(Mu1,u2, v), u1, u2∈VLと単位容量を持つ。 ➡︎簡単にするために、一度に2つのオブジェクトしか結合できないと考える。 ・前のフレームのN1個のオブジェクトに対して、合計N1C2個のマージ頂点が存在することになる。
・マージ頂点は、各Mノードが2つの流入エッジと1つの流出エッジを持つため、フロー保存制約に違反します。そこで、Mの各頂点から消失頂点Dへの出射エッジが、ゼロコスト、単位容量で追加される。同様に、出現頂点Aからすべての分割頂点Sへの流入エッジがコストと単位容量ゼロで追加されます。分割頂点とマージ頂点を持つ拡張ネットワークを図6に示す。
・分割頂点とマージ頂点がソリューションの一部である場合、これらの頂点にちょうど2つのユニットが行き来するようにするための制約が必要です。これをエッジカップリング制約と呼ぶ[17]。
エッジカップリングは、分割（またはマージ）頂点を通るフローが0または2のいずれかであることを保証します。
前のフレームと現在のフレームのすべてのオブジェクトがソリューションの一部であることを保証するために、ネットワークのフロー要件dは、d = N1 + N2に設定されています。
・ネットワークのさまざまなタイプのエッジのコストと容量は、表1にまとめられています。エッジのコストの決定については、次のセクションで説明します。
2.1.4 Calculation of association costs
・連続する2つのフレームの連結されたコンポーネント間の正しい関連付けのために、エッジコストを低くしたい。 ・また、ネットワークの全体的なコストを最小化しようとしています。 ・エッジのコストには、色の類似性成分ρ、距離成分δ、角度変位成分θの3つの成分があり、次のように説明します。
・フレームL内の物体uがバウンディングボックスを用いて定義されているとします。 ・uのヒストグラムhuは，物体の赤，緑，青の各チャンネルのヒストグラムを同じ長さで連結して得られます． 連結されたヒストグラムhuは，ビンの数がν個あります． ・ このヒストグラムは，各ビンのカウントを，ヒストグラムの全ビンの合計で割ることで正規化されます． ・フレームLのオブジェクトuとフレームRのオブジェクトvの間の色の類似性成分ρは，以下のようにhuとhvの差として定義される．
・uのバウンディングボックスの中心位置を(ux, uy)とし、uとvの間の距離成分は次のように定義される。 ・cはフレームの幅、rは高さを表しています。当然のことながら、uとvの正しい関連性は、連続する2つのフレーム間の変位が最小でなければならない
・最後に、uとvの間の角度変位は次のように与えられる。 ・オブジェクトの移動方向はフレーム間で一貫していると仮定します。フレーム間の関連付けは、位置ベクトル間の角度のコサインが増加した場合、ペナルティーを受けます。
Association cost uとvの関連付けの総コストは次のように計算されます。 ・λ1とλ1は2つのスケーリング・パラメータ。
Splitting and merging cost ・分割コストを計算するために、前のフレームのオブジェクトが、現在のフレームの2つのオブジェクトに関連付けられます。 u1をv1とv2に関連付けるためのコストは、u1とv1、u1とv2の間の関連付けコストの合計の平均として計算されます。
Appearance and disappearance cost ・オブジェクトが現れると、そのオブジェクトは現在のフレームに存在し、前のフレームには存在しません。 オブジェクトが消えるとき、そのオブジェクトは現在のフレームには存在しないが、前のフレームには存在していた。 なお、出現ノードAと消失ノードDは、バウンディングボックスが定義されていないダミーノードです。 そのため、(A, v)と(u, D)のペアに対してρ, δ, θを計算することはできません。出現・消失コストは、オブジェクトが画像の境界からどれだけ離れているかに基づいて計算します。
・フレームが幅cと高さrを持っている場合、オブジェクトvの出現コストは次のように計算されます。
2.1.5 Solving the cost flow problem using linear programming ・(2)の最小コストフロー問題は、線形計画問題で解くことができます。 ・接続行列は、図7に示すように、各列がフローネットワークのエッジに対応し、各行が頂点に対応する｜V｜×｜E｜のサイズを有する。 エッジの開始点に対応する列のエントリは+1に，エッジの終了点は-1に設定される．残りのエントリはゼロです。図7のΓの最初の列は、図6のエッジ(T+, L1)を表す。
接続行列↓
・ネットワークの接続行列表現では、分割（またはマージ）頂点のエッジを正確に0個または2個選択するという制限はありません。辺の結合制約を強制するために、入射行列を[17]と同様に修正し、隣接行列として知られている。図8の行列Iは、図6に示したネットワークの結合辺入射行列を表しています。結合エッジ入射行列では、スプリット頂点とマージ頂点の流入エッジと流出エッジが1つの列にまとめられています。
・例えば、図7の列4、6、18、30は、図8のIの列4に結合されます。結合された列には4つの非ゼロのエントリがあり、2つの＋1（列4の2行目と4行目）は入力エッジの開始を表し、2つの-1（列4の5行目と7行目）は分割（またはマージ）頂点の出力エッジの終了を表す。分割およびマージの頂点はもはや必要なく、図8の結合エッジ入射行列から削除される。
・結合辺入射行列Iを用いて、最適なマッチを見つけることは、行列の列のコストが最小になるような列のサブセットを見つけることに相当する。これは、次のような整数線形計画（ILP）問題として表すことができます。
・ベクトルbは、サイズ｜V｜×1で、頂点のフロー要求を表す。 ソース頂点でのフロー要求は+dであり、ターミナル頂点でのフロー要求は-dである。他のすべての頂点のフロー要件はゼロである。サイズ｜E｜×1のベクトルxは、係数が対応するエッジを通過したフローの量を表す解ベクトルである。サイズ｜E｜×1のベクトルtは、ネットワークの個々のエッジの容量を表す。
図6の整数線形計画法に基づく解を図9に示す。この問題の最適解x ∗は、線形計画法[1]で求めることができます。ベクトル x ∗ は、ネットワークの各エッジ上の最適なフローを表しています。この解は、ネットワークのフロー要件dとフローキャパシティtのため、unbounded solutionやno solutionのような矛盾した状態になることはない[17]。
2.2. Counting of passes and generation of possession statistics ・非ゼロのエントリxi∈x ∗は、エッジiがソリューションの一部であることを表す。 さて、結合辺入射行列Iの辺のうち、u∈VLとv∈VRを結ぶ辺は、現フレームでオブジェクトuがvに移動したことを示しています。 前フレームの頂点uを現フレームのv1とv2に接続する結合辺が得られたとき、分割イベントが検出される。 Iの9列目の結合辺は、L2とR2、R3を結んでおり、L2がR2、R3に分割されたことを示しています。 同様に、前フレームのu1,u2と現フレームのvを結ぶエッジが見つかれば、マージイベントを示します。 出現（または消失）イベントは、オブジェクトAとv（またはuとD）を接続するエッジを得ることで検出されます。
・ここで、プレーヤーとボールの分割または結合を含む解が得られれば、パスイベントが発生したと言います。私たちは、フレーム間を移動する個々のオブジェクトに固有のIDを保持します。オブジェクトがあるフレームから次のフレームに移動しても、IDは変更されません。新しいオブジェクトが出現したり、2つのオブジェクトが分割または統合されたりすると、新しいidが割り当てられます。前述したように、パスの開始イベントとパスの終了イベントは1つのパスとみなされます。パスは、両方のプレーヤーが同じチームに所属していても、そのIDが異なる場合に有効です。次に、(1)に従って、ボールポゼッションの統計を記録します。ボールポゼッション統計の生成の全体的な手順は、アルゴリズム1にまとめられています。図10は、パス検出処理をフレームシーケンス上で可視化したものです。フレーム45でプレイヤーとボールのスプリットイベントが発生し、フレーム73でマージイベントが発生しています。このスプリットとマージは、赤で示されたチームにとって有効なパスを意味します。
ボールポゼッション統計の生成の全体的な手順は、アルゴリズム1にまとめられています。図10は、フレーム・シーケンス上でのパス検出プロセスを視覚化したものです。フレーム45でプレイヤーとボールのスプリットイベントが発生し，フレーム73でマージイベントが発生しています．このスプリットとマージは、赤で示されたチームにとって有効なパスを意味します。
実験： ・YouTube [6, 7, 8] で公開されているさまざまなサッカー中継のビデオクリップを使って実験を行った。 ・ビデオは，解像度1280x720，フレームレート25/秒のmp4形式でエンコード ・8つのロングショットおよびミディアムショットのビデオクリップの結果を出力 ・ビデオクリップの再生時間は，約8～10分
学習： ・分類器のオフライン学習のために，ビデオフレーム内のボール，チームラベルを付けた選手，その他のオブジェクトを手動でマーク ・学習には，各カテゴリで25000枚の画像を使用
実験結果： ・3回のクロスバリデーションによる分類結果を図11に示す。 ・ボールのクラスが最も高い分類精度であることがわかる。
<アノテーション > ・ 提案手法によるボール所有の統計結果を検証するために，グランドトゥルースを用意． ・クリップの各フレームをタプル{0, A, B}でマークし，AはチームAがボールを所有していることを示す． ・同様に，B はボールがチーム B にあることを示し，0 はボールがどのチームにも支配されていない状況を示す ・各ビデオクリップについて，パスを手動でカウントすることで，所有率の統計を算出しました．
・(6)のλ1とλ2の値を変えた場合の、連続するフレーム間のオブジェクトの関連付けの精度を図12に示す。
Fig.12のプロットでは、実験に使用したλ1=0.87、λ2=0.63の場合に最も高い関連付け精度が得られている。
・(3)の連結されたヒストグラムのビンサイズν=150を実験的に設定した。
．
・表2は，グランドトゥルースデータを用いた我々の手法と，[23]で提案された手法のパスカウントの比較．
・[23]のパスカウントは，既知のボール位置から描かれたボールの速度曲線を解析して生成されている．
・表3は，異なる手法のボールポゼッション統計の比較を示す．
・表4は、パスカウントとポゼッション統計の平均誤差を示しています。誤差は，検出された結果をグランドトゥルース情報と比較して算出されます．
・我々は、ボールの誤検出は、プレーヤーの誤検出よりも、保有統計の計算に大きな影響を与えることを実験的に発見しました。
計算量の解析
・前のフレームにN1個のオブジェクトがあり，現在のフレームにN2個のオブジェクトがある場合，N1＋N2個の頂点とN1N2個の辺を作成する． ・ソースとターミナルの頂点を追加すると、頂点の数が2個、エッジの数がN1 + N2個増える。 ・出現・消失頂点をネットワークに追加すると、頂点数が2個、辺数がN1＋N2＋3個増加します。 ・分割頂点と結合頂点を追加しても、結合辺入射行列Iの行は増えず、列はN1 ×N2 C2 + N2 ×N1 C2だけ増えます。
・結合辺入射行列は、合計z＝（N1＋N2＋2＋2）行、η＝（（N1N2）＋（N1＋N2）＋（N1＋N2＋3）＋（N1×N2 C2＋N2×N1 C2））列を有する。 ・入射行列の列は変数xiを、行は制約を表しています。 ・したがって、ILPには合計η個の変数とz個の制約があることになる。 ・ILP問題を解くことはNP-Completeと考えられます。 ・ここでQ = η(zα2z+1)、xiは0からαの値をとる。 ・cとrはそれぞれ入力画像の幅と高さである。 ・長さψのビデオに本手法を適用した場合のランタイムコンプレックスはO(ψβ(ηQ) z+1)である。
・提案手法は，Intel i5 2.3 GHzプロセッサ，8 GBのRAM，Windows 10オペレーティングシステムを搭載したPC上で，最適化されていないMATLAB R2018aコードを用いて1組のフレームを処理するのに，平均で3.43秒かかる．
1. 概要（基本アイデア）
本稿では，サッカーの試合映像からボールポゼッションの統計量を自動的に算出する手法を紹介する． ポゼッション統計は，各チームが行った有効なパスの数に基づいて生成されます． 有効なパスとは，ボールがプレイヤーとの間で分岐または合流したイベントとして検出される．パスは，ボールがプレーヤから分離したときに開始されます．パスは，ボールがプレイヤーと合流したときに開始され，パスは終了する． サッカーの試合で有効なパスの数をモデル化するために，最小コストのフローネットワークを使用します．
ボールとプレイヤーは，ネットワークのノードです．
ネットワークの各エッジには，ボールと選手のフレーム間の対応関係から得られるコストが割り当てられています．
ネットワークを通過する総フローは，有効なパスの数を追跡するように最適化されます．
実験結果によると，提案した手法の精度は，類似の手法と比べて少なくとも4%向上した．
2. 新規性
実験結果から，本手法が有望かつ効率的であることがわかった．我々は，適切なコスト関数を用いてネットワークフローモデルを最適化した． このコスト関数は，ボールや選手の動きのベクトルを取り入れることで改善できる可能性がある．
また，現在実装されているSVM分類の代わりに，教師なしのチームラベリングを検討しています．
将来的には、クローズショットビデオフレームのボールポゼッション統計の結果を、ロングショットおよびミディアムショットのサッカービデオの結果と統合することを計画しています。また、ロングパス、ドリブル、オフサイド、異なるシュート、プレーブレークなど、ボールポゼッション統計に及ぼす他の状況の影響を、拡張フローネットワークモデルを用いて分析する必要がある。 また、目的関数の最適化とその実装についても、リアルタイムの結果を得るために詳細な検討が必要です。
結論
背景 ・ボール ポゼッションは勝利チームが高い傾向にある。 ・Opta Sports 社は，チームのパスカウントに基づいてボールポゼッションを計算しています [16]。 ・彼らは，試合中にチームが実行した成功したパスの数を手動でカウントする．そして，チームiのポゼッションは次のように計算される．
2f1.png)
・#Valid passes は有効なパスの数
・同じチームの異なる2人のプレーヤーの間でパスが行われた場合、そのパスは有効とみなす。
・各チームが成功したパスを数え、（1）を使ってポゼッション統計を生成する。
・ボールポゼッションの統計情報を生成することについては，これまでほとんど注目されていませんでした．
・[23]では，ボールの速度曲線を分析することで，パスイベントを検出しています．ボールの速度曲線における局所的な最小値または最大値は，パスの開始または終了イベントを表します．ボールの速度曲線における局所的な最小値または最大値は，パスの開始または終了イベントを表します．パスが検出されると，ボールに最も近いプレイヤーを使用して，ボールを所有しているチームの情報を取得します．パスイベントに基づいて，映像はタッチングセグメントと呼ばれる一連のセグメントに分割されます．そして，2 つのチームのタッチングセグメントの数を数えて，2 つのチームのポゼッション統計を算出します． このアプローチの大きな限界は，アルゴリズムを動作させるために，サッカーボールと選手の空間座標を入力として提供しなければならないことです． ・パスの誤検出は，速度曲線にわずかな変化がある場合に生じる．
目的 ・サッカービデオからボールポゼッションの統計を自動的に計算することです． ・ 本研究では，パス検出プロセスをグラフ理論の枠組みでマッピングする．ボールのパスイベントを検出するために，最小コストのネットワークモデルを構築します．
・パスの開始イベントでは，ボールとプレイヤーを表す連結されたコンポーネントが互いに分離します． パス終了イベントの場合，ボールとプレイヤーを表す連結成分は，互いに重なり合って1つの連結成分となる．
・最小コストネットワーク(最小費用流問題?)は、2つの連続したフレーム間で、オブジェクト（ボールとプレーヤー）が移動したり、分裂したり、合体したり、現れたり消えたりしているかどうかを検出
・最小コストネットワークは，データアソシエーションに基づくトラッキングフレームワークの下で，視覚的なオブジェクトのトラッキングに応用されている[13, 19]． ・まず，フレーム内のオブジェクトが識別されます． 次に，線形制約のある最適化関数を解くことで，対応するオブジェクトをフレーム間でリンクさせる．
3. 手法詳細
・提案手法のブロック図を図2に示す
・ポゼッション統計の推定は，サッカーボールと選手を検出することから始まる．サッカービデオフレームの前景連結成分を抽出するために，[20]を実装(Yoloとかではない)。⬇︎選手検出アルゴリズム
・サッカー場を表す背景をセグメント化した後[20]，SVMを用いて前景の連結成分にラベルを付ける． クラスは，(1)ボール，(2)チームA，(3)チームB，(4)その他とする． ・分類器には，RBFカーネルを用いたマルチクラスSVM [5]を使用しています．分類には，面積，偏心率，RGBヒストグラムを特徴量として用いています．典型的な検出パイプラインを図3に示す．次節では，ボールパスの検出について説明する．
・図3. ボールと選手の検出（チームラベル付き）．ボールは黄色の四角で表示されています．2つのチームの選手は青と赤の長方形で示されています。
2.1. ボールパスの検出 ・ボールパスイベントの検出には，最小コストネットワークモデルを使用します．
・ ネットワークのエッジを通過するフローの制限を1にすることで、ネットワークを通過するパスやフローは相互に排他的であることが保証されます。 ➡︎最小経路問題
・ここでは，パスイベントを検出するために，選手とボールを表す連結成分を検出する必要があります． これらの連結成分は，前のフレームから現在のフレームに向かってsplit（パス開始の場合）またはmerge（パス終了の場合）します．
・しかし、このようなsplitやmergeのイベントは、ネットワークの1つのエッジでは1つしか処理できません。
・また，突然現れたり消えたりする選手やボールを検出するために，ネットワークに appear と disappear のノードを追加している．
2.1.1 Construction of the network ・連続する2つのフレームで検出されたオブジェクトから、フローネットワークを構築 ➡︎前のフレームのオブジェクトを現在のフレームのオブジェクトに正しく関連付けることである． ・関連付けるべきオブジェクトの数に関する事前の仮定は必要ない
・最小コストのソリューションは、フレーム間のすべてのd個のオブジェクトの正しい関連付けを提供します。
・G = (V, E)は、V個のノードとE個のエッジを持つ有向非環状グラフです。 ・ネットワークのノードは，プレイヤーやボールなどの検出された前景オブジェクトを表している ・連続するフレームLとRについて、各エッジ（u，v）∈E，u∈VL，v∈VR）は、非負のキャパシティt（u，v）≧0を持つ。 ・前のフレームLのノードはVLで表され、現在のフレームRのノードはVRで表される。 ・容量t(u,v)とは別に，各エッジは，(u,v)の単位流量あたりのコストを表す実数値のコストa(u,v)を持つ。 このコストは、uとvの間の対応関係や類似性を表しています。 ・コストは、フレーム間の正しい関連付けのために最小となります。 エッジ(u, v)上にx(u, v)個のフローを送ると、a(u, v)x(u, v)のコストが発生する。
・フローネットワークに追加される2つの頂点は、ソースT+とシンクTです。 ・ソースの頂点はフローを生成し、ターミナルの頂点はフローを消費する。 ・コストフロー問題は、ネットワークのエッジに沿ったコストとフローの積の最小化問題として定式化できる[1]。
・uからwへのすべての流入フローとwからvへのすべての流出フローの差は、フロー要求値b(w)に等しい。 ・フロー要求量は、ソース頂点ではゼロより大きく、ターミナル頂点ではゼロより小さく、すべての中間頂点ではゼロであり、フロー保存制約として知られている。
・最小コストフロー問題の決定変数は、辺(u, v)上のフローであるx(u, v)である。 この問題は、フローによって発生する総コストが最小になるように、d量のフローをソースからターミナルの頂点に送ることである。
＜ここで、検出されたオブジェクトに基づいてフローネットワークを構築する。＞ ・前のフレームLでN1個のオブジェクトが検出され、現在のフレームRでN2個のオブジェクトが検出されたとする。 ➡︎バニラフローネットワークは、（N1＋N2）個のノードを有する。 ・各頂点u∈VLは、各頂点v∈VRと接続されており、uからvに向けられた結果、合計N1N2個のエッジがある。 ・各エッジは、コストa（u，v）と容量t（u，v）＝1を有する。 ・またネットワークには、送信元の頂点T+と送信先の頂点T-が追加される。 ・前フレームのすべての頂点uは、コストa(T+, u)=0、容量t(T+, u)=1のソース頂点T+からの入力エッジを持つ。 ・同様に、現在のフレームのすべての頂点vは、コストa(v, T-)=0、容量t(v, T-)=1で、末端の頂点Tへの出射エッジを持つ。
N1=2、N2=3の単純なフローネットワークを図4に示す。
・上記で提案した基本的なネットワーク・アーキテクチャは、次に述べる理由で拡張する必要があります。1つ目の修正は，プレーヤーやボールがフレームに現れたり消えたりすることによるものである．2つ目の変更点は、接続されているコンポーネントの分割や結合によるものです。これらについては次の通りです。
2.1.2 Appearing and disappearing objects ・選手やボールはフレームの中に現れたり、フレームから消えたりする。 このシナリオを取り入れるために，ネットワークには appear 頂点 A と disappear 頂点 D が導入されている． また、Rに突然物体が現れる可能性を考慮して、RのN2個の頂点はすべてLの出現頂点Aに接続されています。 Aとv∈VRを結ぶこれらの辺は、それぞれ単位容量のコストa(A, v∈VR)を持つ。 ソース頂点から出現頂点への、コストa(T+, A)=0、容量t(T+, A)=｜R｜のエッジは、フロー保存のために追加される（｜R｜はフレームRのノード総数を表す）。
・コストa(T+, A)=0、容量t(T+, A)=｜R｜のエッジは、フロー保存のために追加される（｜R｜はフレームRのノード総数を表す）。 ・辺の容量t(T+, A)は、出現頂点がRへの出射辺の数が｜R｜であることから、｜R｜と設定される。
・同様に、消えた頂点Dは、フレームLのN1個の頂点のそれぞれからのエッジを持つ。 これは、前のフレームLの各オブジェクトが次のフレームで消える可能性があることを意味する。
・ネットワークのフロー保存制約を維持するために、コストがゼロで容量t(A, D)=｜L｜のAからDへのエッジが追加される。 ・消えた頂点にはLから｜L｜個の入力エッジがあるので、エッジt(D, T-)の容量は｜L｜に設定される。 ・ネットワークのフロー保存制約を維持するために、コストがゼロで容量t(A, D)=｜L｜のAからDへのエッジが追加される。 ・このようにして、現れた頂点と消えた頂点を持つ修正されたネットワークを図5に示す。
2.1.3 Splitting and merging of objects ・オブジェクトのsplitとmergeをモデル化するために，ネットワークにはsplit頂点Sとmerge頂点Mが導入されている． ・各分割頂点は，Lの各頂点からの1つの入力エッジと，Rの2つのノードへの2つの出力エッジを持つ． ・Splitノードの各出射エッジは，コストと単位容量がゼロ ・入射辺は、コストa(u, Sv1,v2), v1, v2∈VRを持ち、単位容量を持つ。 ・現在のフレームのN2個のオブジェクトに対して、合計N2C2個の分割頂点が存在することになる。
・同様に、Lの任意の2つの連結されたコンポーネントはマージすることができる。 ・したがって、各マージ頂点は、Lの2つのノードからの2つの入力エッジと、Rの各ノードへの1つの出力エッジを有する。 ・Mの各入力辺は、コストがゼロで単位容量を持つ。 ・出て行く辺は、コストa(Mu1,u2, v), u1, u2∈VLと単位容量を持つ。 ➡︎簡単にするために、一度に2つのオブジェクトしか結合できないと考える。 ・前のフレームのN1個のオブジェクトに対して、合計N1C2個のマージ頂点が存在することになる。
・マージ頂点は、各Mノードが2つの流入エッジと1つの流出エッジを持つため、フロー保存制約に違反します。そこで、Mの各頂点から消失頂点Dへの出射エッジが、ゼロコスト、単位容量で追加される。同様に、出現頂点Aからすべての分割頂点Sへの流入エッジがコストと単位容量ゼロで追加されます。分割頂点とマージ頂点を持つ拡張ネットワークを図6に示す。
・分割頂点とマージ頂点がソリューションの一部である場合、これらの頂点にちょうど2つのユニットが行き来するようにするための制約が必要です。これをエッジカップリング制約と呼ぶ[17]。
エッジカップリングは、分割（またはマージ）頂点を通るフローが0または2のいずれかであることを保証します。
前のフレームと現在のフレームのすべてのオブジェクトがソリューションの一部であることを保証するために、ネットワークのフロー要件dは、d = N1 + N2に設定されています。
・ネットワークのさまざまなタイプのエッジのコストと容量は、表1にまとめられています。エッジのコストの決定については、次のセクションで説明します。
2.1.4 Calculation of association costs
・連続する2つのフレームの連結されたコンポーネント間の正しい関連付けのために、エッジコストを低くしたい。 ・また、ネットワークの全体的なコストを最小化しようとしています。 ・エッジのコストには、色の類似性成分ρ、距離成分δ、角度変位成分θの3つの成分があり、次のように説明します。
・フレームL内の物体uがバウンディングボックスを用いて定義されているとします。 ・uのヒストグラムhuは，物体の赤，緑，青の各チャンネルのヒストグラムを同じ長さで連結して得られます． 連結されたヒストグラムhuは，ビンの数がν個あります． ・ このヒストグラムは，各ビンのカウントを，ヒストグラムの全ビンの合計で割ることで正規化されます． ・フレームLのオブジェクトuとフレームRのオブジェクトvの間の色の類似性成分ρは，以下のようにhuとhvの差として定義される．
・uのバウンディングボックスの中心位置を(ux, uy)とし、uとvの間の距離成分は次のように定義される。
・cはフレームの幅、rは高さを表しています。当然のことながら、uとvの正しい関連性は、連続する2つのフレーム間の変位が最小でなければならない
・最後に、uとvの間の角度変位は次のように与えられる。
・オブジェクトの移動方向はフレーム間で一貫していると仮定します。フレーム間の関連付けは、位置ベクトル間の角度のコサインが増加した場合、ペナルティーを受けます。
Association cost uとvの関連付けの総コストは次のように計算されます。
・λ1とλ1は2つのスケーリング・パラメータ。
Splitting and merging cost ・分割コストを計算するために、前のフレームのオブジェクトが、現在のフレームの2つのオブジェクトに関連付けられます。 u1をv1とv2に関連付けるためのコストは、u1とv1、u1とv2の間の関連付けコストの合計の平均として計算されます。
Appearance and disappearance cost ・オブジェクトが現れると、そのオブジェクトは現在のフレームに存在し、前のフレームには存在しません。 オブジェクトが消えるとき、そのオブジェクトは現在のフレームには存在しないが、前のフレームには存在していた。 なお、出現ノードAと消失ノードDは、バウンディングボックスが定義されていないダミーノードです。 そのため、(A, v)と(u, D)のペアに対してρ, δ, θを計算することはできません。出現・消失コストは、オブジェクトが画像の境界からどれだけ離れているかに基づいて計算します。
・フレームが幅cと高さrを持っている場合、オブジェクトvの出現コストは次のように計算されます。
2.1.5 Solving the cost flow problem using linear programming ・(2)の最小コストフロー問題は、線形計画問題で解くことができます。 ・接続行列は、図7に示すように、各列がフローネットワークのエッジに対応し、各行が頂点に対応する｜V｜×｜E｜のサイズを有する。 エッジの開始点に対応する列のエントリは+1に，エッジの終了点は-1に設定される．残りのエントリはゼロです。図7のΓの最初の列は、図6のエッジ(T+, L1)を表す。
接続行列↓
・ネットワークの接続行列表現では、分割（またはマージ）頂点のエッジを正確に0個または2個選択するという制限はありません。辺の結合制約を強制するために、入射行列を[17]と同様に修正し、隣接行列として知られている。図8の行列Iは、図6に示したネットワークの結合辺入射行列を表しています。結合エッジ入射行列では、スプリット頂点とマージ頂点の流入エッジと流出エッジが1つの列にまとめられています。
・例えば、図7の列4、6、18、30は、図8のIの列4に結合されます。結合された列には4つの非ゼロのエントリがあり、2つの＋1（列4の2行目と4行目）は入力エッジの開始を表し、2つの-1（列4の5行目と7行目）は分割（またはマージ）頂点の出力エッジの終了を表す。分割およびマージの頂点はもはや必要なく、図8の結合エッジ入射行列から削除される。
・結合辺入射行列Iを用いて、最適なマッチを見つけることは、行列の列のコストが最小になるような列のサブセットを見つけることに相当する。これは、次のような整数線形計画（ILP）問題として表すことができます。
・ベクトルbは、サイズ｜V｜×1で、頂点のフロー要求を表す。 ソース頂点でのフロー要求は+dであり、ターミナル頂点でのフロー要求は-dである。他のすべての頂点のフロー要件はゼロである。サイズ｜E｜×1のベクトルxは、係数が対応するエッジを通過したフローの量を表す解ベクトルである。サイズ｜E｜×1のベクトルtは、ネットワークの個々のエッジの容量を表す。
図6の整数線形計画法に基づく解を図9に示す。この問題の最適解x ∗は、線形計画法[1]で求めることができます。ベクトル x ∗ は、ネットワークの各エッジ上の最適なフローを表しています。この解は、ネットワークのフロー要件dとフローキャパシティtのため、unbounded solutionやno solutionのような矛盾した状態になることはない[17]。
2.2. Counting of passes and generation of possession statistics ・非ゼロのエントリxi∈x ∗は、エッジiがソリューションの一部であることを表す。 さて、結合辺入射行列Iの辺のうち、u∈VLとv∈VRを結ぶ辺は、現フレームでオブジェクトuがvに移動したことを示しています。 前フレームの頂点uを現フレームのv1とv2に接続する結合辺が得られたとき、分割イベントが検出される。 Iの9列目の結合辺は、L2とR2、R3を結んでおり、L2がR2、R3に分割されたことを示しています。 同様に、前フレームのu1,u2と現フレームのvを結ぶエッジが見つかれば、マージイベントを示します。 出現（または消失）イベントは、オブジェクトAとv（またはuとD）を接続するエッジを得ることで検出されます。
・ここで、プレーヤーとボールの分割または結合を含む解が得られれば、パスイベントが発生したと言います。私たちは、フレーム間を移動する個々のオブジェクトに固有のIDを保持します。オブジェクトがあるフレームから次のフレームに移動しても、IDは変更されません。新しいオブジェクトが出現したり、2つのオブジェクトが分割または統合されたりすると、新しいidが割り当てられます。前述したように、パスの開始イベントとパスの終了イベントは1つのパスとみなされます。パスは、両方のプレーヤーが同じチームに所属していても、そのIDが異なる場合に有効です。次に、(1)に従って、ボールポゼッションの統計を記録します。ボールポゼッション統計の生成の全体的な手順は、アルゴリズム1にまとめられています。図10は、パス検出処理をフレームシーケンス上で可視化したものです。フレーム45でプレイヤーとボールのスプリットイベントが発生し、フレーム73でマージイベントが発生しています。このスプリットとマージは、赤で示されたチームにとって有効なパスを意味します。
ボールポゼッション統計の生成の全体的な手順は、アルゴリズム1にまとめられています。図10は、フレーム・シーケンス上でのパス検出プロセスを視覚化したものです。フレーム45でプレイヤーとボールのスプリットイベントが発生し，フレーム73でマージイベントが発生しています．このスプリットとマージは、赤で示されたチームにとって有効なパスを意味します。
4. 結果
実験： ・YouTube [6, 7, 8] で公開されているさまざまなサッカー中継のビデオクリップを使って実験を行った。 ・ビデオは，解像度1280x720，フレームレート25/秒のmp4形式でエンコード ・8つのロングショットおよびミディアムショットのビデオクリップの結果を出力 ・ビデオクリップの再生時間は，約8～10分
学習： ・分類器のオフライン学習のために，ビデオフレーム内のボール，チームラベルを付けた選手，その他のオブジェクトを手動でマーク ・学習には，各カテゴリで25000枚の画像を使用
実験結果： ・3回のクロスバリデーションによる分類結果を図11に示す。
・ボールのクラスが最も高い分類精度であることがわかる。
<アノテーション > ・ 提案手法によるボール所有の統計結果を検証するために，グランドトゥルースを用意． ・クリップの各フレームをタプル{0, A, B}でマークし，AはチームAがボールを所有していることを示す． ・同様に，B はボールがチーム B にあることを示し，0 はボールがどのチームにも支配されていない状況を示す ・各ビデオクリップについて，パスを手動でカウントすることで，所有率の統計を算出しました．
・(6)のλ1とλ2の値を変えた場合の、連続するフレーム間のオブジェクトの関連付けの精度を図12に示す。
Fig.12のプロットでは、実験に使用したλ1=0.87、λ2=0.63の場合に最も高い関連付け精度が得られている。
・(3)の連結されたヒストグラムのビンサイズν=150を実験的に設定した。
．
・表2は，グランドトゥルースデータを用いた我々の手法と，[23]で提案された手法のパスカウントの比較．
・[23]のパスカウントは，既知のボール位置から描かれたボールの速度曲線を解析して生成されている．
・表3は，異なる手法のボールポゼッション統計の比較を示す．
・表4は、パスカウントとポゼッション統計の平均誤差を示しています。誤差は，検出された結果をグランドトゥルース情報と比較して算出されます．
・我々は、ボールの誤検出は、プレーヤーの誤検出よりも、保有統計の計算に大きな影響を与えることを実験的に発見しました。
計算量の解析
・前のフレームにN1個のオブジェクトがあり，現在のフレームにN2個のオブジェクトがある場合，N1＋N2個の頂点とN1N2個の辺を作成する． ・ソースとターミナルの頂点を追加すると、頂点の数が2個、エッジの数がN1 + N2個増える。 ・出現・消失頂点をネットワークに追加すると、頂点数が2個、辺数がN1＋N2＋3個増加します。 ・分割頂点と結合頂点を追加しても、結合辺入射行列Iの行は増えず、列はN1 ×N2 C2 + N2 ×N1 C2だけ増えます。
・結合辺入射行列は、合計z＝（N1＋N2＋2＋2）行、η＝（（N1N2）＋（N1＋N2）＋（N1＋N2＋3）＋（N1×N2 C2＋N2×N1 C2））列を有する。 ・入射行列の列は変数xiを、行は制約を表しています。 ・したがって、ILPには合計η個の変数とz個の制約があることになる。 ・ILP問題を解くことはNP-Completeと考えられます。 ・ここでQ = η(zα2z+1)、xiは0からαの値をとる。 ・cとrはそれぞれ入力画像の幅と高さである。 ・長さψのビデオに本手法を適用した場合のランタイムコンプレックスはO(ψβ(ηQ) z+1)である。
・提案手法は，Intel i5 2.3 GHzプロセッサ，8 GBのRAM，Windows 10オペレーティングシステムを搭載したPC上で，最適化されていないMATLAB R2018aコードを用いて1組のフレームを処理するのに，平均で3.43秒かかる．
5. 論文，コード等へのリンク
6. 感想，コメント
7. bibtex
8. 関連論文