DEIM Forum 2016 P1-6

時空間を横断した出現パタンに基づく高速な映像検索
劉健全†

西村 祥治†

荒木 拓也†† 日本電気株式会社グリーンプラットフォーム研究所 〒 211–8666 神奈川県川崎市中原区下沼部 1753
E-mail: †{j-liu@ct, s-nishimura@bk, t-araki@dc}.jp.nec.com
あらまし

本論文では，防犯カメラが撮影した映像から，同一人物がいつ・どこで現れたか（出現パタン）による検索技術を紹介する．本稿で紹介する技術は，カメラ映像から「顔」を抽出し，顔の類似性から同一人物とみなせる出現を抽出することで高速な映像検索を実現する．これにより，複数の事件現場に共通して現れた不審者の特定など，検索対象の顔が不明なため従来困難であった犯罪捜査・予防を実現する．このような検索を行なうためには既存技術
では，すべてのシーンの出現に対して「同一人物とみなせるほど顔が類似しているかどうか」を確認する必要がある．
これをすべての人に対して行わなければならないため，膨大な数の照合が必要となり，非常に長い時間が必要となる問題が生じる．これに対して，我々は独自のツリー状のデータ構造を用い，お互いに類似したデータを索引することにより，高速な映像検索を実現した．評価実験により提案技術は既存技術より１００倍程度の高速化が可能であることを検証した．また，デモにより高速化の様子を示す．
キーワード

類似検索，映像検索，データ索引，出現パタン，類似分類

1. は じ め にる．本稿は，このような課題に着目し，時空間を横断した出現パタンに基づいた高速な映像検索技術を提案する．本提案技術

近年，ショッピングモール，ビル，駅，公共施設など至るとは，映像に写り込んだ人物の顔特徴の類似性から同一人物であころに防犯カメラが設置されるようになってきた．従来より，ることを特定し，その人物が異なる時間と空間で頻繁に現れる防犯カメラは，警備や捜査といったパブリックセーフティの用パタンに基づき，出現頻度の高い人物を不審者の対象として高途として利用されている．その際，映像の確認や解析は，主に速に検索して見出す．本技術の主な着眼点としては，同一人物人手によって行なわれている．しかしながら，昨今，防犯用途が異なる時間と空間を横断した頻繁な出現にある．例えば，駅の普及によりカメラの設置台数は急激に増加し，カメラから集や観光地等でターゲットを探しているスリのような人物は，異まる映像データも増大している．2020 年には，防犯カメラがなる時間に不自然に頻繁に現れるという特徴を持っている．ま撮影した映像が 5.6 ZB に達し，ビッグデータ全体の 42%を占た，複数の放火事件現場に共通して現れた人物も，放火犯などめると予測される [1]．このため，人手による解析が困難になっの不審者として疑わしい可能性がある．なぜならば，普通の人てきている．例えば，複数箇所に設置されたカメラの映像を対はそもそも異なる放火事件の現場を訪れることは考えにくいか

象に，人の目による確認作業では多くの時間が必要あるため，らである．

同じ場所に何度も出現する，あるいは複数の場所に出現する人物などの検索をおこなうのは，非常に困難である．

本論文では，このような観点において，防犯カメラが撮影した映像から，同一人物がいつ・どこで現れたかを出現パタンとこのような人的資源の限界を克服するため，映像に写った人して扱う．これにより，複数の事件現場に共通して現れた不審物，車両，物体をリアルタイムに自動的に解析する技術が開発者の特定など，検索対象が不明であるため従来困難であった犯されてきた [2]．例えば，最新の顔認識技術は，他人許容率が罪捜査・予防を実現する．

0.1%の時，誤照合率が 2-4%という高い精度で人物を識別可能

この実現に向けて 2 つの重要な課題を解決しなければならなである [3]．映像監視に関する研究が過去 20 年に渡って行なわ

い．1 つ目は，別のシーンに現れた人物が同一人物とみなせるれてきた [4] が，多くの既存技術は典型的な映像解析，例えば，かどうかを高精度で判断することにある．2 つ目は，十分に顔物体の発見，認識，追跡，および行動分析に留まり，大量の防が似ている人物を同一人物のグループに高速に振り分けること

犯カメラを横断した映像検索技術は今なお欠けている [5]．そこにある．前者に関しては，顔照合の速度と精度が世界一（注 1） とで，我々は大量の防犯カメラ向けの映像検索技術に着目し，指R（注 2）
認められた顔認証技術の NeoFace⃝を用いることで，顔定した顔の人物を高速に検索できる映像検索システム [6], [7] をが十分に似ているかどうかを判断できる．しかしながら，後者開発した．

に関しては，既存技術では，図 1 に示すように顔照合を全てのしかしながら，パブリックセーフティの用途にある警備や捜シーンに映っている全ての人に対して行わなければならないた

査では，必ずしも検索対象を指定できるとは限らない．すなわ
ち，不審者の対象となりうる候補を自動的に発見し，いかに結（注 1）：http://www.nist.gov/customcf/get_pdf.cfm?pub_id=905968

果を高速に絞り込むことは依然困難な研究課題として残ってい（注 2）：http://www.nec.co.jp/soft/neoface/product/neoface.html

め，膨大な数の照合が必要となり，計算量が非常に高い問題が異なる時間 (時間軸) に頻繁に現れる特徴を時空間を横断した生じる．

出現パタンと呼ぶ．例えば，犯罪予防の用途において，駅や観光地等でターゲットを探しているスリとして疑われる人物は，不自然に頻繁に現れるという特徴を持っている．また，迅速な犯罪捜査の用途において，複数の放火事件現場に共通して現れた人物は，放火犯等の不審者として疑わしい可能性がある．これらの不審人物が持つ共通点は，複数の防犯カメラ (空間軸) に

図 1

既存技術での課題: あるシーンに映っている人が他のシーンに映っているか調べるには，大量の照合が必要

現れ，異なる時間 (時間軸) に頻繁に現れる特徴である．
そして，前述の出現パタンに基づいて，同一人物とみなせる出現を抽出し，同一人物の出現頻度でランキングすることで，このような計算量が問題でなければ，N 対 N 照合を要す
るシーケンシャルスキャン，クラスタリング技術である DB-

SCAN [8], [9] と階層的クラスタリング [10] を用いることで，同一人物のグループ振り分けを実現できる．しかし，これらの既存技術は，いずれも O(N 2 ) 以上の計算量を必要とし，クラスタリング技術がオフラインのアプローチであるため，リアルタイムな映像監視にとっては実用性が低い．よって，本研究では，先行研究 [11], [12] で提案した独自のツリー状のデータ構造を用い，お互いに類似したデータをリアルタイムで動的に索引付けすることにより，高速な映像検索を実現する．

本論文が対象とした映像検索を実現した．その高速な実現については，4. で改めて紹介する．

[検索の入力] 本稿の映像検索は，検索対象が不明であるた
め，検索の入力はないが，検索を実現するには，前述で仮定した出現パタンにより不明人物をグループに振り分け，ランキングを行う．

[検索の出力] 検索後に，時空間を横断した出現パタンを持つ人物の出現頻度順でランキングした人物の上位 K 件の一覧を結果として出力する．

3. 関 連 研 究

本論文は以下の通りで構成される．2 章で我々の着眼点と問題設定を述べる．3 章で関連研究を紹介する．そして，4 章で我々独自の手法を提案し，5 章において評価実験を用いて提案手法の有効性と効率性を示す．最後に，開発した映像検索のデモシステムを紹介し，全体と今後の課題についてまとめる．

本章は，これまで説明した映像検索問題を解くことが可能な既存技術を紹介する．解決可能な手段は，概ね 2 通りある．N対 N の全件照合において同一人物に同じ番号 (ID) を振って，異なる ID の人物グループに分けるというシーケンシャルスキャン法 (以降 SeqScan 法) がその 1 つである．もう 1 つは，既存

2. 問 題 設 定のクラスタリング技術を適応し，蓄積した映像から抽出した人

本章は，本論文が対象とした映像検索に関する問題設定を述べる．まず，検索に用いられる映像の属性情報と人物の特徴情物を異なるクラスタに振り分けるというクラスタリング法 (以降 Cluster 法) になる．これらにより，同一人物のグループに振り分けたあと，同一人物の頻度順で人物をランキングする．

報は以下である．

[映像の時空間情報] 時間情報は，防犯カメラが撮影した時刻である．この時刻は，属性として映像の各フレームに付与される．空間情報は，防犯カメラが設置した場所の位置情報を用いる．多くの場合は位置情報はカメラ ID と紐付いているので，本稿では，簡単にカメラ ID を用いて映像のユニーク性を識別

上位 K 件を結果として出力する．以下に，この 2 通りの既存技術を述べる．

SeqScan 法 では，リアルタイムに映像から人物の顔を抽出し，顔を特徴量化する．抽出された顔の特徴量に顔 ID を付与する．最初の 1 つめは，ID を 1 とする．次に入ってくる顔の特徴量を既に ID を付与した顔の特徴量と照合する．指定したする．

[人物の特徴情報] 本稿では，映像から抽出される顔の特徴量を人物の特徴情報として用いる．顔の抽出および照合は，顔R⃝認証技術 NeoFaceにより行う．顔の照合では，2 つ顔の類似度合いを表すスコア ([0, 1] 区間にある実数) を算出する．
次に，本稿で対象とした映像検索と，前述の時空間を横断した出現パタンについて説明する．

[映像検索] 従来の映像検索は，目的人物の画像をとして与えられた人物の顔などの特徴を用いて，該当人物が映った目的の映像を探し出し，検索対象が明確な検索である．一方，本研究では，防犯カメラが撮影した監視映像による犯罪予防・迅速な捜査の実現を目的としているため，検索対象とする人物はクエリの発行時には不明である．

[出現パタン] 本稿では，複数の防犯カメラ (空間軸) に現れ，スコアのしきい値を超えた場合は，該当顔と十分に類似すると判断し，同じ ID を付与する．この照合を繰り返しおこなうことにより，全ての顔が同じ ID を持つ同一人物のグループに分類される．そして，グループごとにおいて，同一人物を時間軸と空間軸で出現パタンとしてまとめる．最後に，各グループの出現頻度順でランキングする．

SeqScan 法は，同一人物を判定しながら，番号を振ることが可能であるため，リアルタイムまたはオフラインに対応できる．
しかしながら，ID を振るためにかかる特徴量間の照合の数が膨大になり，計算量 O(N 2 ) がかかる．長時間の映像検索にはスケールしない問題が生じる．

Cluster 法 では，特徴量の抽出およびグループのランキングを SeqScan 法と同様に処理するが，全ての顔を同一人物のグループに振り分ける部分のみは，既存のクラスタリング技術を適応することで実現する．例えば，密度に基づくクラスタリン

Algorithm 1: GroupBy( Threshold δ, SimTree T )グ手法の DBSCAN [8], [9] と，階層的なクラスタリング手法のInput: δ, specifing the minimum similarity of two data.

Agglomerative アルゴリズム [10] が挙げられる．しかしながら，

Input: SimTree T , built by BuildIndex [12] algorithm.

DBSCAN 法は O(N 2 )，Agglomerative 法は O(N 3 ) の計算量

Output: G, a list of groups constructed by this algorithm.

がかかり，いずれも実用的ではない．しかも，クラスタリング

1

処理では，対象となる全データをためてからクラスタリングを2行わなければならないため，オフライン解析のみ対応できる．
本研究が応用の目的とした迅速な犯罪捜査とリアルタイムな

3
45

begin
Queue Q ← ∅ ;foreach Node e ∈ T doif e.δ >= δ thenQ.inqueue(e) ;分析による犯罪予防にとって，Cluster 法は実用ではないため，実験では SeqScan 法との比較により評価を実施した．

4. 提 案 手 法
本章は，先行研究 [11], [12] で提案した独自のツリー状のデー

6SimTree T 2 ← ∅ ;7while Q is not empty do

8Node e ← Q.dequeue() ;9foreach Data d ∈ e do

10

タ構造を用い，お互いに類似したデータをリアルタイムで動的11に索引することにより，独自の高速な映像検索手法について紹12介する．

13

先行研究 [11], [12] では，従来の映像検索を高速化するため14if SimilaritySearch(d, δ, T 2) =| ∅ [12] thenG.insertToExistingGroup(d) ;else
G.insertToNewGroup(d) ;T 2.insertData(d) ;に，図 2 に示した独自のツリー状のデータ構造を提案した．この独自の木構造を類似度木と呼ぶ．類似度木の構築または性能

15

return G ;評価については，先行研究 [12] で紹介したため，本稿では，その特徴と独自性について簡単に説明する．

タ間の類似度が δ 以上であるものを同一グループに振り分ける処理を示す．行 2 から 5 において，既に構築された類似度木 Tを辿り，類似度が δ 以上のノードを切り出してキュー Q に入れておく．そして，行 6 から 14 において，キューに入ったノードを取り出し，ノードに保存される全てのデータを 1 個ずつ新しい類似度木 T 2 に挿入する．データの挿入するたびに，類似検索をかけて，該当データと類似したデータが存在するかどうかを検査する．存在する場合は，既存グループに振り分け，存在しない場合は，新規グループに振り分ける．最後 (行 15) に，振り分けられたグループをアルゴリズムの結果として返す．

図 2 独自のツリー状のデータ構造 (類似度木)

最終的に，本稿で限定した映像検索をおこなうたびに，アルゴリズム 1 を呼び出し，振り分けられたグループごとに時空間類似度木では，データを類似度に基づ木構造で管理する．図を横断した出現パタンの頻度順で人物をランキングする．

2 に示したように，下の層になるほどお互いに類似したデータ

また，アルゴリズム 1 により抽出されるグループは，従が集まり，上の層になるほどお互いに異なったデータになるよ

来の結果と比べ近似結果となるが，理想の場合は計算量がうにデータを配置する．この類似度木を用いることにより，おO(M log(M )) に近づくため，本稿で限定した映像検索を高速

互いに類似したデータを抽出する際には，抽出したい類似の程に実現できる．ここでは，M がデータベースに入った人物のユ度によって，下の層からデータを取り出すことで，容易にデーニーク数を仮定する．

タのグループを再構築できる．
また，類似度木はリアルタイムで構築することができる．デー5. 実験と評価

タを挿入するたびに木構造を更新し，前記の性質を常に保つよ

本章では，実データおよび模擬データを用いて，本稿で提案うに動作する．木構造の更新にかかる時間は極めて小さいため，した映像検索の性能を評価した．評価実験は，メモリ 11GB と大量の防犯カメラ映像から得られる大規模な顔情報をリアルタ

R
R
E5504 @ 2.00GHz の CPU を持つマシン環境
Xeon⃝Intel⃝

イムに挿入することが可能になる．これにより，防犯カメラがにおいて， Ubuntu 12.10 の OS 上で実施した．表 1 に記載し撮影した直後のデータについても即時に検索可能になる．

た実験データにより，しきい値 δ = 0.8 をデフォルト値として次に，類似度木を用いたデータのリアルタイムな類似分類を実現するアルゴリズムを提案し，その詳細について説明する．
アルゴリズム 1 では，抽出したい類似度合いのしきい値 δ を指定し，リアルタイムに構築された類似度木 T を用いて，デー映像検索の速度と，結果の再現率と精度を評価した．

5. 1 データセット
本実験では，模擬データと実データの 2 種類データを用いて実証実験を実施した．

表 1 実験データセット
名前

サイズ

ところ，7 人の「不審者役」は全員，この 20 人の中に含まれて模擬データ のべ 15 分の模擬撮影映像から得た 1 万件の顔特徴量
実データと思われる上位 20 人を抽出し，公的機関に確認してもらったのべ 24 時間のカメラ映像から得た 100 万件の顔特徴量

いた．
実データを用いた実験においても，本提案技術は，24 時間の映像を検索する時間を従来の SeqScan 法でかかる約 1 時間から模擬データは，エキストラを用いて，複数カメラで重要施設10 秒まで大幅に短縮した．公的機関を介した検証結果により，の周辺に撮影した模擬映像から得た 1 万件の顔特徴量である．

検索結果の再現率は，100%に達したと言える．不審者役 7 人

模擬データにおいて，既知の不審者役を演じた 1 人が，特定のの顔が知らされてないため，検索結果の精度は評価しなかった．

場所をうろうろする行動を意図的におこなった．
実データは，海外の特定地域の公的機関の協力を得て，実際の街角の防犯カメラ映像のべ 24 時間を用いて，100 万件の顔（注 3）特徴量を抽出した

6. ま と め
本稿では，防犯カメラが撮影した映像から，同一人物がいつ・．実データにおいて，我々に知らされてどこで現れたかという出現パタンに基づき，独自のツリー状のいなかった 7 人の「不審者役」が，公的機関によって動員され，データ構造を用いた類似データの索引により，検索対象が不明

彼らは複数箇所の対象エリアを頻繁に訪れるなど，不審な行動な映像検索を高速に実現した．評価実験により提案技術が既存を意図的におこなった．また，不審者役の顔，人数を伏せた状技術より 100 倍程度の高速化であることを検証した．

態で評価をおこなった．

今後の課題として，映像以外の実データを用いてさらに実証

5. 2 評 価 結 果実験を実施することと，近似検索アルゴリズムを改善して正確模擬データを用いて，本稿で提案した映像検索技術で解析しかつ高速な映像検索手法を検討することにあると考えられる．

たところ，不審者役を演じた 1 人は，上位 10 人の検索結果の中に含まれ，1 位にランクされた．検索結果の再現率は 100%に達し，Top@1 の検索精度も 100%に達したことが分かった．図

3 は，模擬データにおいてデモシステムが実行した映像検索の結果を示した画面である．

図3

模擬データにおいて映像検索を実行したデモシステムの画面．既存技術 SeqScan 法の実行速度より 100 倍向上．

図 3 は，本稿で提案した技術と既存技術の SeqScan 法を実装したデモシステムを紹介する．左側は，既存技術の SeqScan法を用いて実行した検索結果を示す．右側は，本提案技術を用いて実行した検索結果を示す．既存技術と同様に，提案技術は不審者役を演じた 1 人を検索結果の 1 位にランクした．既存技術を用いた検索でかかった 37 秒と比べ，提案技術はわずかの0.369 秒で完了し，実効速度を 100 倍向上した．
また，実データを用いても，同様な結果を得ることができた．
本稿で提案した映像検索技術で解析したところ，同じ場所に長時間滞在したり，頻繁に現れたりする “不審” な人物の検索を，わずか 10 秒という短時間で完了させた．検索結果で「怪しい」（注 3）：http://jpn.nec.com/press/201511/20151111_02.html

文献[1] John Gantz and David Reinsel. The Digital Universe
in 2020: Big Data, Bigger Digital Shadows, and Biggest
Growth in the Far East. IDC Technical Report, Dec. 2012.
[2] Mubarak Shah, Omar Javed, and Khurram Shafique. Automated visual surveillance in realistic scenarios. IEEE Transactions on Multimedia, 14(1):30–39, 2007.
[3] 越仲孝文, 大網亮磨, 細見格, 今岡仁. 音声・映像認識連携への取り組み : 1．音声・映像情報の構造化と検索. 情報処理,
52(1):71–78, Jan. 2011.
[4] Tomi Räty. Survey on contemporary remote surveillancesystems for public safety. IEEE Transactions on Systems,Man, and Cybernetics, Part C: Applications and Reviews,
40(5):493–515, 2010.
[5] Weiming Hu, Dan Xie, Zhouyu Fu, Wenrong Zeng,
and Stephen J. Maybank. Semantic-based surveillance
video retrieval. IEEE Transactions on Image Processing,16(4):1168–1181, 2007.
[6] 西村祥治, 劉健全, 藤森偉恭, 荒木 拓也. Wally: 映像検索システ
ムを対象としたスケーラブルな分散データストア. In 第 5 回デー
タ工学と情報マネジメントに関するフォーラム (DEIM2013),pages P4–1, 2013 年 3 月 3 日–3 月 5 日.
[7] Jianquan Liu, Shoji Nishimura, and Takuya Araki. Wally:
A scalable distributed automated video surveillance systemwith rich search functionalities. In Proceedings of the 22nd
ACM MM, pages 729–730, 2014.
[8] Martin Ester, Hans peter Kriegel, Jrg S, and Xiaowei Xu.
A density-based algorithm for discovering clusters in large
spatial databases with noise. In Proceedings of the 2nd ACM
SIGKDD, pages 226–231, 1996.
[9] Junhao Gan and Yufei Tao. Dbscan revisited: Mis-claim,un-fixability, and approximation. In Proceedings of the 36th
ACM SIGMOD, pages 519–530, 2015.
[10] Jiawei Han, Micheline Kamber, and Jian Pei. Data Mining:
Concepts and Techniques, chapter 7: Cluster Analysis. 3rdedition, 2011.
[11] 劉健全, 西村祥治, 荒木 拓也. 類似度の階層関係に基づく木構造索引を用いた効率的な類似検索. In 第 5 回データ工学と情報マネジメントに関するフォーラム (DEIM2013), pages A9–1,2013 年 3 月 3 日–3 月 5 日.
[12] 劉健全, 西村祥治, 荒木拓也, 中村 祐一. 類似度の階層関係を用いた類似検索の高速化とその応用. 電子情報通信学会技術研究報
告, 115(315):123–128, November 2015.