DEIM Forum 2016 F3-5

記号列化した人流データからの特徴抽出と可視化
宮城 優里†

大西 正輝††

渡辺知恵美†††

伊藤 貴之†

高塚正浩††††† お茶の水女子大学大学院人間文化創成科学研究科 〒 112–8610 東京都文京区大塚 2 丁目 1 番 1 号†† 産業技術総合研究所人工知能研究センター 〒 305–8560 茨城県つくば市梅園 1 丁目 1 番 1 号††† 筑波大学システム情報系情報工学域 〒 305–8573 茨城県つくば市天王台 1 丁目 1 番 1 号†††† シドニー大学情報工学部 オーストラリア連邦ニューサウスウェールズ州 2006
E-mail: †{miyagi.yuri,itot}@is.ocha.ac.jp, ††onishi@ni.aist.go.jp, †††chiemi@cs.tsukuba.ac.jp,††††masa.takatsuka@sydney.edu.au
あらまし

カメラで記録した映像データから人の歩行パターンや場所ごとの特徴を発見することで交通，防災，マーケティングなど多様な分野に役立つ情報を得ることが出来る．しかし，大量に蓄積した人流データの効率的な分析は未だ課題が多く，特にデータの圧縮とマイニングについては検討の余地がある．本論文では，SAX(Symbolic AggregateApproximation) を拡張した UniversalSAX とランレングス符号化によって人流データを記号列化し，各地での滞在時間や交通量などの特徴を抽出して可視化する手法について報告する．新たな試みとしては，人流の非類似度計算に重み付きレーベンシュタイン距離を導入した点，可視化機能を 2 段階に拡張し各地の流量などの概要表示，並びに具体的な歩行経路などの詳細表示を実装した点が挙げられる．
キーワード

人流，可視化

1. は じ め にる手法は既に多数発表されている．藪下ら [3] は規定の通路が存在しない場所で人流データを取得，分類したのちに主要な歩監視カメラで記録された映像から歩行者の行動パターンを見行経路を要約可視化する手法を提案している．問題点として動つけることにより，様々な分野で役立つ情報を得ることができ線の分類基準が通過地点のみであり，時間帯や歩行速度に関する．特に交通，防災，マーケティングとの関連が深く，具体的るパターンが読み取れないことがあげられる．深田ら [4] は小には混雑の原因究明やより良い避難経路の策定，商品陳列の改樽市内で観光客の歩行経路を記録し，歩行速度や各地での滞在良などが可能となる．しかし，蓄積された映像は膨大となるた時間を分析することで，人の集まりやすい場所をミクロスケーめ，人流の全体像把握や重要な現象の発見を効率よく進めるのルで特定した．データの取得に GPS を用いている点が本手法は困難な場合が多い．計算機を用いた人流解析の手法は開発途と異なっており，より広範囲での観測に適している反面，室内上にあり，特に大規模な人流情報の圧縮とマイニングについてでの適用が難しいという課題がある．福手らによる研究 [5] で検討する必要がある．

は，スペクトラルクラスタリングを用いて人流を構成する動線

我々は人流情報の圧縮・マイニング・可視化に関する手法を群を分類し，ThemeRiver と呼ばれる手法によって流量の時間提案している [1]．この手法ではまず UniversalSAX [2] を適用

変化を可視化している．Wang ら [6] は道路上に多数のセンサし，人流データを記号列化して圧縮する．これらの記号列からを設置して様々な車両の通過情報を集計し，それらの特徴を抽自然言語処理手法によって特徴的な情報を抽出して可視化する．

出している．GPS などと異なって通過点を離散的にしか把握

本報告では主に特徴抽出および可視化に関する進展について述できないこれらのデータに対処する解析，可視化手法を提案しべる．特徴抽出に関しては，各要素からの抽出結果を客観的にている．これらの手法では取得したデータに対する圧縮を行っ比較するために行う歩行経路間の非類似度計算に重み付きレーていない点に改善の余地がある．

ベンシュタイン距離を導入した．これにより，条件を柔軟に変木實ら [7] は大規模な空間時系列データの高速な検索を実現

更しながらの歩行経路分類や検索に応用できる可能性を示す．

する I-Tree を提案し，シミュレーションによって生成した人流可視化については，各地の通過人数などを表示する概要表示機

データおよび実測した微気象データを使用して類似検索に関す能と，特定の地点に絞って具体的な歩行経路を表示するなどのる実験を行っている．SAX を用いてのデータの記号列化とい詳細表示機能にわけて実装した．これらの機能を用いて，注目う点で本研究と類似しているが，データの可視化には着手してすべき場所の発見と人流の特徴の把握を短時間で行えるようにいない．矢田ら [8] は RFID によって買い物客の歩行動線を記なったことを報告する．

録し, 文字列化した上で行動パターン分析を行った. この研究で2. 関 連 研 究は, 売り場ごとの滞在時間が分析されておらず, さらにユーザの関心に沿って提示内容を変更できる可視化機能が実装されてい本章では人流やその他の動線データ解析の手法について簡単ない点で本手法と異なる. 動線データを構成する時空間情報をに紹介する．時空間情報を実数値のまま扱って分類，可視化す文字列化する手法として [9] や [10] が挙げられる．[9] は元の空salSAX [2] を用いる．UniversalSAX は，時系列データを記号列に変換する手法 SAX(Symbolic Aggregate Approximation)を，多次元データにも適用できるように拡張した手法の 1 つである．他の拡張手法と比較して，特定の軸の値が反映されなくなるなどの情報欠落や，要素間の距離関係の崩れが発生しにくいという特長がある．UniversalSAX のアルゴリズムは概ね次のようになっている．
（ 1 ） 多次元空間 (本研究では x，y の 2 次元) に領域分割を適用し，各領域間の距離表を作成する．
（ 2 ） 各領域に対して記号を割り当てることで，実数値座標から記号への変換が可能になる．
図 1 人流データの記号列化の流れ

この変換を用いて，多次元時系列データ全体を記号列に変換する．ユーザは以下の 4 つのパラメータを指定し，分割の細かさ間の距離関係を維持しつつ文字列変換し圧縮した上で分類している．動線のパターンだけではなく絶対的な場所も考慮した分を決めることができる．
記号列化するデータの次元数
各軸を量子化する際の分割数使用する記号の種類数
領域を強制分割する際の閾値は文脈自由文法を用いた手法で，ノイズを含む動線データからd2ka2bのモチーフ検出を実現している．これらの研究では，取得した記号の割り当ては空間充填曲線の一種であるヒルベルト曲線動線をすべて可視化するため，データの増加に伴って注目すべに基づいた配置となっている．まず d 次元空間を各軸 2k 区分

き動線や場所を見つけにくくなる傾向がある．この点に関し，の格子状に分割し，すべてのブロックを一筆書きで通過するヒ

本手法では人流データを変換してできる文字列から何らかの特ルベルト曲線を作成する．各ブロックには線が通過した順番に徴のある動線を抽出し，その特徴を強調表示するように可視化

番号を振る．さらにこのブロックの集合を再度 a 個の領域に分している．

割し，値の小さいブロックを含む領域から順に記号を割り当て類という点に特徴があり，異なる状況下で取得された 4 種類のデータをデバイスごとに自動分類することに成功している．[10]る．それぞれの領域が何個のブロックで構成されるかはデータ

3. 処理手順の流れの分布に依存する．混雑して多くの人が通った所など，たくさ

本章では提案手法の処理手順について述べる．3. 1 節ではカんの要素が含まれている場所ほど通過点の情報を細かく区別すメラで取得できる人流データの形式，3. 2 節では人流データのるために領域の面積を小さくする．反対に，要素数が少ない場

文字列化による圧縮，3. 3 節では文字列を対象としたアルゴリ

所では 1 つの領域の面積が極端に大きくなってしまう場合があズムによる人流データの特徴抽出，3. 4 節では動線形状とそれる．閾値 2b を設定することで，面積が一定値を超えた領域をらがもつ特徴の可視化について説明する．(なお，3. 1 節と 3.

強制的に分割することも可能とする．この時，領域分割の結果

2 節での処理は [1] で報告した内容と同一である．)に加えて領域間の距離表を保存でき，距離計算の際には参照で

3. 1 人流データの取得
モーションキャプチャデバイス Xtion を用いて，次のような形式の人流データを記録する．

••
•

時刻 t
歩行者の識別子 ID
座標値 (x，y)

きるため処理が高速化する．
続いて人流データを記号列に変換する．まずはじめに Xtion
によって取得した人流データの座標にアフィン変換を適用し，視野の中央を原点座標とする．これによって領域全体とカメラの視野を一致させ，広範囲の座標値が同一記号に変換されることを避ける．その上で，領域分割に従って多次元時系列の人流Xtion ではマイクロ秒単位で歩行者の頭部座標と各時刻のフデータを記号列に変換し，撮影された人数と同数の記号列を生レーム情報を記録する．各歩行者には固有の識別子が割り当て成する．続いて本手法では，生成された記号列にランレングスられる．頭部座標は 3 次元で取得可能だが，歩行中に高さの変符号化を適用することで，データ量を圧縮する．ランレングス化はないものとみなし，床平面上での位置を表す 2 次元座標系

符号化は可逆圧縮であり，特に同じ記号が連続で出現しているを使用する．

部分 (歩行者が立ち止まっている部分) ほど圧縮率が高くなる．

この人流データを構成する各時刻のフレーム情報の集合から，これらの処理により歩行者の各々について，経由地点を記号の同じ識別子を有する点を時系列順に連結することで，各歩行者種類，それぞれの場所での滞在時間を記号の連続出現回数としの経路を取得できる．て取得できる．

3. 2 人流データの記号列化

3. 3 歩行経路の特徴抽出とそれらの比較

続いて本手法では，「データ量の削減」「特徴抽出をしやすい形

3.2 節での処理によって得られた記号列の特徴を調べることへの変形」という 2 つの目的のため，実数値座標の集合で表現で，人流の性質を把握する．例えば，ランレングス符号の中でされた歩行経路を記号列に変換する (図 1)．変換には Univer-

連続出現回数が多い記号を調べることで，滞留が起きている場

図3

図 2 レーベンシュタイン距離 (LD) の計算例

所や各地点での平均滞在時間を取得できる．
続いて, 歩行経路を要約/検索するために, 各歩行経路の特徴抽出結果を比較する. 現時点で比較処理として行っているのは,通過地点に 焦点を当てての歩行経路間の非類似度の計算である. 記号列どうしの非類似度の定義として，レーベンシュタイン距離 (LD) を採用している．ある記号列 s1 を別の記号列 s2とのレーベンシュタイン距離 D(s1, s2) を測る場合，s1 に対して 1 文字の挿入，削除，置換の３種類の操作をそれぞれ何回行

各操作のコスト計算は d(a, b) とする．
拡張したレーベンシュタイン距離の操作として記号どうしの入れ替えを含める場合もあるが，本研究ではとりいれていない．
そのため同じ場所を通過した場合でも向きが反対のものは別々の経路として区別されるが，移動方向が異なることにより行動の意図も異なっていると考えられるため問題にはならない．まとめると，歩行経路の性質のうち非類似度に反映されるのは次のものになる

必要な操作の回数が少ないほど非類似度の値が低下し，s1 と s2•••は似た記号列とみなされる．具体的には，いずれかの操作を 1

このように歩行経路間の非類似度を計算することで，指定し回行う場合のコストを 1 とし，s1 を s2 に変換し終わるまでのた経路の検索や似た歩行経路をグループ化しての経路要約に応コストの合計を求める．変換の過程が複数存在する場合は，動用できる．重み付きレーベンシュタイン距離では挿入，削除，的計画法に基づいたアルゴリズムによって最もコストの低い方置換のコストを独立に変更することが出来るため，どのような法を特定しそのコストを D とする (図 2)．s1 と s2 の長さが異条件に焦点を当てて検索や分類を行なうかが調整できる．例えなる場合でも計算可能で，s1 の長さを m，s2 の長さを n とおば，行動範囲の広さでグループ分けしたい場合は挿入と削除のくと計算時間は O(mn) である．

コストを重くして，文字数の異なる記号列間の非類似度を大きうことで s2 に変換できるかを調べる．変換が完了するまでにしかし，LD の計算ですべての操作コストが一様に 1 と定義されていることは，任意の 2 つの記号がどの程度異なるかが通過地点の違い
歩行範囲の違い
歩行する向きの違い

くすれば良い．

3. 4 歩行経路の可視化

考慮されないという点で問題となる．例えば “mine” と “nine”

最後に，記号列化した人流データを，その特徴を強調しながの非類似度と，“mine” と “fine” の非類似度を比較する．発音ら可視化する．3.2 節で作成した領域分割結果を参照し，各領に着目すると後者の 2 つの記号列の違いが大きいように感じら域の中心座標を 1 つのノードとし，各ノード間を線で結ぶことれるが，D(“mine”, “nine”) と D(“mine”, “fine”) はどちらもで歩行経路を表す．大まかには目的の異なる２通りの可視化が1 文字目の置換による 1 であり直感的でない．そこで挿入，削行える．1 つはすべての場所についての人流の概要を表示する

除，変換の各コストを柔軟に変更し，記号の相違の程度を反映ことで，もう 1 つは限定的な地点での詳細な情報を表示するこ

させる重み付きレーベンシュタイン距離 [11] を使用する．本研とである．まず概要表示を行って注目すべき場所を見つけ，そ究では記号どうしの違いの程度は 2 つの領域間の距離にあたるの後その場所についての詳細を表示させることを想定している．

ため，3.2 節で作成した距離表を参照する．2 つの領域 r1 と r2

概要表示としての機能は以下の通りである．の非類似度を d(r1, r2) とおくと，d(r1, r2) は距離表を参照するだけで取得できる．図 3 はそれぞれの操作のコスト計算を図••

滞留表示
2 領域間の流量表示示したものである．例えば “abxd” を “abd” に変換する場合

滞留表示では，各場所での混雑度や歩行者がスムーズに移動(‘x’ の削除) の場合や逆に “abd” を “abxd” に変える場合 (‘x’

しているかを示すため各ノードに円を描く．円の大きさは通過の挿入)，コスト c は次のように計算する．

人数を示す．色は黄色から赤に変化し，平均滞在時間が長いほ

c = |d(b, x) + d(x, d) − d(b, d)|

ど赤くなる．似た機能として，2 つの領域間の歩行者の累計人“abx” と “abxd” のように最後の記号の挿入，又は削除の場

数も可視化でき，線の太さで人数を表す．

合は c = d(x, d) とする．記号 ‘a’ を ‘b’ に変換する際のコスト

これらの機能を使い，歩行者の大まかな分布を示すことで，より詳しく調べるべき場所を絞り込む．ユーザはノード x を選
び，x に関する以下の情報を見ることが出来る．

••

行きやすい場所の組合せ
歩行経路のアニメーション

x を通った歩行者は，他にどのような場所を通りやすいかを可視化する．x を含んでいる記号列を検索し，それらの記号列はx の他にどのような記号を含んでいるかを調べる．この結果をもとに，x を通過した歩行者がその前後に通過した領域に 2 つの半円を描写する．1 つの領域について，x とその領域のどちらを先に通ったかを区別し，x に行った後その場所へ行った場
合は明るい緑，反対にその領域を経由してから x に来た場合は暗い緑の半円で表す．該当する歩行者が多かった領域の半円ほど半径を大きくする．このような情報は，店舗である商品を購入した買い物客が同時に何を買いやすいかの推測や，展示会において来場者が関心を持ちやすそうな展示をまとめて配置するなどのレイアウト考案に活用できる．
さらに，ユーザは具体的な歩行経路のアニメーションを観察することができる．2 領域間を結ぶ線を各歩行者が通った順に描画する．これによって歩行者がどこから来たのか，どのような順番でどこを通ったのかを細かく知ることが出来る．ユーザ
図 4 (上)Xtion の視野 (下) 滞留表示結果は表示する歩行経路の条件を指定でき，具体的には選択した領域を通過したものか，そこから出発したものか，そこに到着したものの 3 種類から選択できる．
表示するべき歩行経路がいくつあるかによって，線の密度を変更する．歩行者が少ない場所では，個別の歩行経路を比較できるように線間隔を離して描写する．反対に多いところは密集させ，細い線の集合が太い一本の帯としてみえるようにする．
これによって大量の線が絡み合って見辛くなることを避ける．
個人の動きを確認することは難しくなるが，集団的な動きの特徴を見落とす可能性は少なくなる．線の色づけは歩行者がその場所を通過した時間を反映している．撮影していた時間帯の中で，早く来た歩行者は赤く，遅く来た歩行者は青く表示される．
特定の場所における歩行者数の変化の度合いや特に混雑していた時間帯の特定などが可能になる．

図 5 歩行者が選択地点を通過した前後に立ち寄りやすい場所の表示

表示する線をさらに絞り込む機能として，経路検索機能がある．歩行経路を表す記号列をキーワードとして入力すると，右上にかけての領域では，黄色からオレンジの大きな円が多くキーワードと記録されていた歩行経路すべてとの非類似度計算なっており，多くの人々がスムーズに通過した歩行ルートにあを行なう．キーワードとの非類似度が閾値以下のものを検索結たることがわかる．反対に左端，上端の展示物前の付近は赤い果として返し，表示する．閾値を低くするほど完全一致検索に円が多くなっており，展示物をよく見るために足を止めた人が近づき，高くした場合は曖昧検索となる．

多かったことが読み取れる．中でも，左上隅の円は半径が大きこのように人流の特徴を明示するような可視化を行うことで，長期間にわたって取得した人流データの特徴を効率良く理解することができる．

4. 展示会における人流分析の一例
我々はある展示会場で取得した人流データを可視化した．部

く，その場所の展示物は特に人を集めたことがわかる．
続いて，滞留表示機能により異なる性質の人流パターンが可視化された以下の２カ所を選択し，それぞれの詳細な情報を可視化した．

••

展示物付近 (滞留発生地点)
下端の出入口 (スムーズな歩行ルートの一部)

屋の左端から上端にかけて展示物があり，出入り口は下と右上

図 5 は展示物付近を経由した歩行者が，その前後に通過しての 2 カ所がある (図 4 上) ．データは 8 時間分延べ人数 5,531いた領域を示している．暗いグリーンの半円が多くの領域に描

人分の動線を含む．まず人流データの概要を理解するため，滞写されていることから，右の入り口からも下の入り口からも人留を表示し歩行者の多かった場所を調べた (図 4 下)．下部からが来ていたことがわかる．一方，明るいグリーンの半円は選択

図 8 歩行経路検索結果 (白:入力 赤:検索結果)
図 6 展示物付近を通過した歩行者の動線可視化結果

記号化前のデータがおよそ 669MB だったのに対し，可視化に使用したデータは 62KB の記号列データと 53KB の領域情報のみだった．このことから，人流の特徴を残しながらデータを軽量化することに成功し，さらに短時間で人流の特徴を把握できる手法を開発できたと考える．

5. まとめと今後の課題
本報告では，大規模人流データを記号列化により圧縮した上で，記号列を対象としたアルゴリズムによる検索や分類を適用することで，人流データにおける特徴的な動きを抽出し可視化する手法を提案した．この手法によれば，大規模人流データへの高速な処理が実現し，かつ重要な要素を素早く発見することが可能になると考えられる．
図 7 下端の入り口を通過した歩行者の動線可視化結果

今後の課題としては以下のような点が挙げられる．

域を経由したのち下に向かう歩行者が多かったことを示してい•••る．つまり，一方の入り口から入り展示物を見て別の出口から

現時点の処理では，可視化画面に表示する歩行経路は記号列向かう動きだけでなく，下の入り口から入って引き返す人も一化した実データのみとなっており，表示する動線が多すぎると定数いたことがわかる．

可視化結果が煩雑になってしまうことがある．類似経路の検索した領域より下のエリアに集中しているが，これは選択した領歩行経路の要約結果の可視化
経路検索機能の拡張
ユーザによる領域形状の指定

次に，具体的な歩行ルートを可視化し各時間帯での歩行者の機能などを使い，動線をグループ化したのち平均的な歩行経路人数を調べた (図 6)．展示物付近は赤から紫までの色がまんべを算出するなどの要約を行えるようにすることを検討していんなく確認でき，人が絶えなかったことがわかる．その中でも，る．要約結果は個別の線ではなく領域の塗りつぶしなどで表現

14 時から 15 時までを表す青の線が太く描写されており，朝やし，多数の歩行経路を描写する際も可能な限りシンプルな画

夕方よりも真昼の方が，人出が多かったことが分かる．

像を生成することを目指したい．このような可視化について

次に展示物から遠い，スムーズに歩行者が移動していた場所について可視化した．下端の入り口を通過した歩行者の歩行は，Continuous Parallel Coordinates [12] を参考にする予定である．

ルートを可視化すると (図 7)，展示物のあるエリアよりも典型

経路検索機能についても，ユーザが指定できる条件の幅を増的ルート上 (図 4 上) の方が，多くの線が描写されている．そやしたい．ユーザによる検索条件指定によって非類似度計算時

こで具体的に，展示物の方に行かず 2 つの出入り口を結んだのコストを変更し，重点を置く要素を変更しながらの検索が“UVTQJK” というルートを検索すると (図 8) 類似した歩行パ行えるようにすることを検討中である．操作についても，キーターンが実在し，展示物を素通りした人が一定数いたことが確

ワード検索に加えて任意の曲線をスケッチしそれと似た経路を認された．

検索できるようにする予定である．領域分割は現在４つのパラ

このように，記号列化した人流データからいくつかの行動パメータで細かさを指定できるが，具体的に境界線の形状や位置ターンを抽出することができた. データの記号列化により，時を指定することはできない．障害物やブースなどがあらかじめ刻や歩行経路に関する情報の粒度は粗くなっている．一方で，わかっている場合はユーザによる属性指定と具体的な領域の形状指定が行えるようにしたい．

文献[1] 宮城, 大西, 渡辺, 伊藤, 記号化による人流データの圧縮 と可視化 , 第 18 回画像の認識・理解シンポジウム, SS5-9, 2015.
[2] 大西, 渡辺, Universal SAX:空間充填曲線を利用した SAX の多次元時系列データへの適用 ，日本データベース学会論文誌，Vol. 11，No. 1，pp. 43-48, 2012．
[3] H. Yabushita，T. Itoh， Summarization and Visualizationof Pedestrian Tracking Data , 15th International Conference on Information Visualisation (IV2011), pages. 537-542,
2011．
[4] 深田, 奥野, 大津, 橋本, 観光歩行行動データに対する GIS を用いた 3 次元可視化手法の提案 , 観光と情報, Vol. 8, No. 1,pp. 51-66, 2013．
[5] A. Fukute, M. Onishi, T. Itoh, A Linked Visualization ofTrajectory and Flow Quantity to Support Analysis of People Flow , 17th International Conference on Information
Visualisation (IV2013), pp. 561-567, 2013．
[6] Z. Wang, T. Ye, M. Lu, X. Yuan, H. Qu, J. Yuan, Q.
Wu, ”Visual Exploration of Sparse Traﬃc Trajectory Data”,
IEEE Transactions on Visualization and Computer Graphics, Vol. 20, No. 12, 2014．
[7] 木實, 石塚, 岩井, 宮崎, 瀬崎, 戸辺, ”I-Tree：センシングデータの統合検索を支援する空間時系列索引機構”, 情報処理学会論文
誌:データベース, Vol. 4, No. 1, pp. 26-39, 2011．
[8] 矢田, スーパーマーケットにおける顧客動線分析と文字列解析 , 統計数理, Vol. 56, No. 2, pp. 199-213, 2008.
[9] N. H. Thach, E. Suzuki, A Symbolic Representation for
Trajectory Data , The Japanese Society Artificial Intelligence, 1A2-2, 2010．
[10] T. Oates, A. P. Boedihardjo, J. Lin, C. Chen, S. Frankenstein, S. Gandhi, Motif Discovory in Spatial Trajectories
using Grammar Inference , ACM International Conferenceon Information & Knowledge Management (CIKM 2013),
pp. 1465-1468, 2013．
[11] 鑓水, 語形間距離の計算における「重みづけ」 , 明海日本語,
Vol. 18, pp. 179-194, November 2013.
[12] J. Heinrich, D. Weiskopf,
Continuous Parallel Coordinates , IEEE Transactions on Visualization and Computer
Graphics, Vol. 15, No. 6, pp. 1531-1538, 2009.