α × SC「群れとスーパーコンピュータに関するシンポジウム」
京都大学 学術情報メディアセンター

2022/09/01

動的モード分解による群れの運動分析
高見利也

6767

@@

大分大学理工学部

本日の内容• 集団運動と運動分析に関連する問題と興味• 群知能、群れの運動、人や動物の運動予測• 映像の分析と機械学習• 物体認識、三次元CNN、など• 動的モード分解による時空間分割• 特異値分解の計算量、再構成誤差の利用
2

そもそもの研究動機
集団運動に対する興味• 群知能：協力して探索すると、効率が良くなる→

バイオ・インスパイアード・コンピューティング• 集合知：たくさん集まったら、賢くなる？
• 創発？：集団の論理、群れの意志の発現なのか？？
• 単に集合するだけではなく、個体間に相互作用が必要→

集団の中では何が起きているのか？
3

The Seventh Starling
ムクドリの群れの分析
Andrea Cavagna• Cavagna and co-workers
measured ocks of starlings
with stereoscopic cameras.
A. Cavagna, et al., Animal Behav.76, pp.217-236 (2008);
ibid. pp.237-248 (2008).

• Cavagna and Giardina foundthat each bird interacts onlywith surrounding 7 birds.
A. Cavagna and I. Giardina, Signi cance 5, pp.62-66 (2008).

4fi

fl

64

june2008

fl

Artificial Life and Emergence
多数→多様、複雑→創発

Downloaded from http://rsta.royalsocietypublishing.org/ on January 23, 2018

(a)

(b)

(c)

(d)

• 5,000,000 boids simulation
on a GPU accelarator• statistical properties ofocking• emergence of collective
intelligence?

Takashi Ikegami

Figure1. Snapshots of swarming
The total numberof boids inpp.446-450
each panel is (a) 2048, (b)16 384, (c) 131 072 andY. Mototake and T.
Ikegami,Proc.behaviour.
SWARM
2015,
(2015).
(d) 524 288, respectively. Some flocks are composed of a very large number of boids with narrow filament patterns. TheT. Ikegami and Y.following
Mototake,Phil.
Trans.
Soc.
20160351(2017).
Srep =A375,0.01 and Sali =0.05, and W att = 0.002,
W rep = 0.008
parameters wereused in thesimulation: SR.
att = 0.05,

and W ali = 0.06, measured in a dimensionless unit. The interaction ranges, with a three-dimensional circular sector of their
5angles towards the front, are π /2, π /2 and π /3, respectively. The initial velocity of each boid is set at random, and the densityof the total number of boids is kept constant at 16 384 (number per cubic unit). The minimum and the maximum speed are set

Boidモデル

C.W. Reynolds, Flocks, Herds, and Schools:
A Distributed Behavioral Model (1987)

Craig W. Reynolds
separationalignment

cohesion• 人工的に群れを作る：
Separation
Alignment
Cohesion• これら三力の大きさを調整する
ことで、さまざまな群れの性質を再現→

コンピュータグラフィックスの分野で応用（映画制作など）
6

全体を時空間分割
小集団に分割して、詳細な分析をしたい• 集団の運動を分析• 力学的解析• 個体間相互作用の推定• 集団内の情報伝達• 小集団間の相互作用• ・・・→

群れの自動分割7

機械学習による運動の分析
自動運転、自動採点、・・・• 車載映像の分析• 危険回避、自動ブレーキ• 歩行者の行動推定• スポーツの採点競技：体操、フィギュアスケート、etc• 技の自動判定・採点• ペア競技でのシンクロ度
自動採点システム (富士通、東京オリンピック)
8

例1：三次元CNNによる映像分析
自動運転に向けた歩行者の行動予測のために• タスク：映像内の歩行者が、この後、道を渡るかどうかを推定
横断の意図あり横断の意図なし

映像開始時は歩道にいたが（横断中でない）

映像開始時から終了まで、途中から横断を始めた場合ずっと歩道にいた場合

9

車載カメラ映像の分析
３D CNNを用いて歩行者の横断意図の推定を実施

JAADデータセット

直後の横断に関して、◆ ３４６本の車載映像からなるデータセット 7割程度の正答率
で意図の推測◆ １つの動画は５〜１０秒程度が可能◆ 歩行者についてのラベル付けが行われている

横断中かどうかについてラベル付けされている
10

例2：ペア競技でのシンクロ度診断
骨格推定(OpenPose)、動的時間伸縮法(DTW)• 映像に映る運動が同期しているかどうかを判定する試み• 例えば、ペア競技では・・・
・アーティスティック・スイミング・フィギュア・スケート・バトン・トワーリングなどの採点項目に「シンクロ度」

アーティスティック・スイミング• 一部の競技で、採用が進んでいるものの、シンクロ度なども含めた完全自動化はまだ
11

バトン・トワーリング

映像に映る運動の分析
腕の運動の同期分析• 骨格推定(OpenPose)： https://github.com/CMU-Perceptual-Computing-Lab/openpose
Realtime multi-person keypoint detection library• (右図) 腕の関節の角度を取得• 動的時間伸縮法(Dynamic Time Warping)：
二つの時系列間の距離を計算→ 時間のずれ
シンクロ度の診断• 動的計画法(Dynamic Programming)により、計算量は O(N 2) [N は時系列の長さ]12機械学習による手法の問題点
なんでも深層学習がはやりだが・・・• 未知の運動に対して無力• 教師あり学習による方法では、学習用のデータが必要
すでに知られている運動を分類する場合には有効• 計算量がそれなりに大きい• 画像サイズによっては、リアルタイムの物体認識が難しい• 骨格推定の OpenPose は、わりと重い処理

13

集団運動を分析する手法の検討
機械学習によらない方法• 要件：
・未知の運動も含めて分析
・全体の時系列を時間・空間方向に分割できる
・ビデオ映像に対してもそのまま適用できると便利• 動的モード分解(Dynamic Mode Decomposition)の活用
14動的モード分解
時間発展演算子の線形近似、時系列の特異値分解
P. J. Schmid, "Dynamic mode decomposition of numerical and experimental data," J. Fluid Mech. 656, 5-28 (2010).

• 時系列データ： Y = {y0, y1, …, yτ−1}、 Y′ = {y1, y2, …, yτ}[n × τ 次元]

21 τ−1• 線形近似： Y′ ≈ FY、 F = argmin ∑ yt+1 − F̃yt
F̃∈ n× n τ t=0†+−1 †+−1 †Y=UΣV
Y=VΣU
F=Y′Y=Y′VΣU
特異値分解：、により•[compact SVD： U は n × r 次元、Σ は r × r 次元、V は τ × r 次元 (ただし、r は F のランク)]

††−1̂
F=UFU
=UY′V
Σ
n×nF(次元)を変換した(r × r 次元)の•固有値 λj、固有ベクトル φj を使って時系列 {yt} を表現• V (τ × r 次元) = {v0, v1, …, vr−1}：DMDモード σj の時間パターン

￼￼

￼

￼

￼

𝒞𝒞• U (n × r 次元) = {u0, u1, …, ur−1}：DMDモード σj の空間パターン

15動的モード分解
n 次元ベクトル

時系列Y=

≈・・・

[n × τ 次元]・・・

F[n × n 次元]

yt・・・

Y′ ≈ FY[n × τ 次元]

y1 y2 y3 . . . yτ

時間モード vj† ：[τ 次元行ベクトル]

Y の特異値分解(SVD)V†・・・

y0 y1 y2 . . . yτ−1=

U×̲

Σ

＿×
[τ × τ 次元]

Y[n × τ 次元]×yt+1

y0 y1 y2 . . . yτ−1Y′ =y0 y1 y2 . . . yτ

線形演算子の定義[n × n 次元][n × τ 次元]

対角要素 σj ：￼￼DMDモードの値(増幅率)
空間モード uj ：[n 次元列ベクトル]16

動的モード分解による時空間分割
同様の運動をしている集団毎にグルーピングする
1. 空間方向の分割：空間モードを利用してクラスタリング• 空間モードの意味：データ{yt}によって異なることに注意[速度場などの量]：場の空間パターン[粒子や個体毎の力学変数]：特定モード集団への個体の寄与[二次元画像]：特定の振動モードにある二次元領域

2. 時間方向の分割：Time-Shifted DMD (2019, Inomata-Takami)• 時系列の再構成誤差に注目して、時間方向の分割指針を与える
・Y. Inomata and T. Takami, "Analysis of the Collective Behavior of Boids,"
in Proc. Tra c and Granular Flow, pp.373-379 (2020).
・猪股能成, 高見利也「動的モード分解を用いた集団運動変化点の検出」
交通流と自己駆動粒子シンポジウム論文集26-20 (2020).

ffi

17

1. 空間方向の分割

時間モード vj† ：[τ 次元行ベクトル]n 次元ベクトル・・・

y0 y1 y2 . . . yτ−1[n × τ 次元]=U×̲

[n × n 次元]Σ[τ × r 次元]

V†×[τ × τ 次元]

対角要素 σj ：DMDモードの値(増幅率)

空間モード uj ：[n 次元列ベクトル]• 空間モード {uj} を、空間分割のための指針として利用：

特定の運動モードにある空間のパターンを表す→ いくつかのモードに属する領域をまとめて、小グループに分割(比較的単純なクラスタリングの手法が使える)• 粒子数(群れの個体数)を N、物理量の個数を k とすると、空間次元 n = Nk は、それなりに大きな数になる。
18

位置座標と速度ベクトルを使うだけで、k = 6

DMDの計算量・計算時間について主要な計算は、特異値分解• 問題点：画像・映像を対象にすると次元が大きくなってしまう[Full High-vision 映像 n = 2048 × 1024 = 2 × 106 ]2O(nτ)
行列()の特異値分解(SVD)の計算量：
n×
τ
n>
τ
•

n = 8192 の場合
τ = 1024 の場合
τ = 512 の場合

n = 4096 の場合

n = 2048 の場合

τ = 256 の場合

時系列の長さ τ

空間次元の大きさ npython コード "scipy.linalg.svd" の計算時間 (intel core i7 4 core)19𝜱

2. 時間方向の分割
Time-Shifted DMD (TS-DMD) → データをスライドさせながら実行【１回目】赤枠のデータ(時間幅 Δ)のみでDMDを実行
モードの計算・データの再構成を行い、誤差を計算
123…

…

入力 1-16.15-13.93-8.92-7.17-6.96

-6.18

-2.00

2.57

4.07

入力 2-27.45-24.07-16.47

5.63

5.44

4.69

1.57

3.13

0.57

入力

26.73

23.87

17.42-6.33

-6.14

-5.43

-1.76

0.25

0.05

誤差：R(t) = yt − F̃t−Δ,t yt−1

モードの計算

動的モード

…

1

再構成

23…

入力 1-16.15????

入力 2-27.45????

入力26.73????

短い時系列に対する繰り返し計算：計算量の爆発をおさえて、分割点をより詳細に求める
20線形演算子

演算子と誤差・・・

誤差の増加 = 不連続点

≈y1 y2 y3 . . . yτF[n × n 次元]Y′• 演算子 F の線形近似：

Y′ ≈ FY ⟺F ≈ Y′Y + = Y′VΣ−1U †・・・

×y0 y1 y2 . . . yτ−1

YF ≈ Y′Y +・・・

=×y1 y2 y3 . . . yτ

VY′×

Σ

[τ × τ 次元]＿×[r × τ 次元][n × τ 次元]• 再構成誤差： R(t) = yt − F̃t−Δ,t yt−1

￼￼￼￼￼

￼

時刻 t − Δ から時刻 t の時系列から求めた演算子
21U†̲[n × n 次元]

Boidの運動に対するTS-DMD
時系列データに対する再構成誤差• 運動形態が変化する時系列：
(a)

(b)

• あまり変化のない時系列：(c)

全体の時系列に対する再構成誤差

TS-DMDによる再構成誤差

まとめ• 運動分析というテーマの紹介• 車載カメラ映像の分析、スポーツの自動採点、etc• 群れの分析手法として、動的モード分解を利用• 時系列データの時空間分割• 動的モード分解の計算量• 再構成誤差の応用(TS-DMD)• 本当は、時間と空間を融合した手法が必要
23

ご清聴ありがとうございました。
• スライドの元になったデータは、大分大学 理工学部
xReality・知的解析研究室の学生の研究による：• 車載映像の3DCNNによる分析：大山勇人(M2)• ペア競技のシンクロ度診断：原ゆう奈(M1)• Time-Shifted DMD：猪股能成(NEC)• この研究は、科研費 基盤(C) 21K11789「統計モデルと数理モデルを融合した集団運動時系列分
析手法の開発」による支援を受けています。
24