村林 昇 2010年 博士(システムズ・マネジメント)
動画像を対象にした画像検索性能の改善に関する研究

1. はじめに

近年、ブロードバンドネットワークが急速に発展している.また,高性能なプ ロセッサやメモリなどの低価格化に伴い汎用PCも高性能なものが手軽に入手で きるようになった.さらに,パーソナルビデオカメラレコーダやハードディス クレコーダを初めとするデジタル家電の急速な発展により大量の動画像コンテ ンツも汎用PCに取り込むことが容易になり,汎用PCを動画像編集やストレージ として利用する機会も増加している.このような背景を考えた場合に,画像検 索の性能をできるだけ向上させ,画質変化に耐性があり大規模データにも対応 可能な検索技術を開発することが重要となる.

以上のような観点から,本研究では,ここ数年重要になっているWWWを介する動 画像を対象にした画像検索性能の改善に関する研究を行った.本研究は以下で 示す,1)動画像の検索精度の改善,2)動画像の検索速度の改善,3)多種類の特 徴量を用いた画像検索性能の改善,の3つの内容から構成する.

2. 動画像を対象にした画像検索研究の動向と課題

動画像の検索精度に関する研究動向

これまでの研究では,主に研究に用いるために特別に用意され,かつ画質が校 正され標準化された画像データベースを用いて研究が行われている.このよう な研究は,異なる研究環境で行われた実験データを比較評価できる利点が存在 する.しかし,個人が撮影した様々な撮影条件での画質が校正されていないビ デオ画像に対しては十分対応していない.それらの研究においては 表2.1に示す課題が存在する.

表2.1 動画像の検索精度を悪化させる要因

検索精度を悪化させる要因

    主な項目

撮影条件の違い

天候,陰影,撮影アングル

撮影機器の画像特性の違い

デバイス,信号処理方式の違い

本論文の第3章では,従来手法におけるこれらの課題を改善するために,グループに基づいた画像検索法を提案する.

動画像の検索速度に関する研究動向

従来の研究は線形探索で問題であった検索処理の負荷を低減し検索時間を改善しているが,ブロードバンドネットワークが整備され高性能PCが普及した今日においては表2.2に示す課題が存在する.

表2.2 動画像の検索速度に関する研究の課題

検索速度に関する課題

    主な項目

検索データの大規模化

WWWなどの検索データの増加

検索対象画像の改変

WWWにおける多様な画像の存在

本論文の第4章,第5章では,これら従来の研究における課題を改善するため,100年規模の大規模で多彩な動画像コンテンツにも対応可能なTiny LSH法,直交Tiny LSH法とDirect-mapped cacheを用いた高速検索手法をそれぞれ提案している.

3. 動画像の検索精度の改善

インターネット上には様々な観光や旅行案内に関連したテキスト情報と対応する多彩な画像が存在することに着目し,そのインターネット上の画像(Web画像)を利用した動画像にアノテーションの付与を行うシステムを提案した[1]

 従来の画像検索手法では,画質の違いにより画像特徴が異なることから,動画像と類似したWeb画像を十分な精度で検索することは難しい.この課題に対処するため,画像グループの類似度に基づいた画像検索手法(グループ法)を提案した.提案するグループ法の特徴は,1)wavelet変換に基づく画像特徴(wavelet特徴)とSIFT特徴を組み合わせて用いること,2)検索対象のビデオ画像とWeb画像において,関係する画像に基づいたグループ処理および画像グループ間の類似度に基づいた画像グループの選択を行うことである.第1の特徴は天候の変化など様々な撮影環境下での検索対象の画像間における,同一対象の画像であっても画質の違いによる画像特徴が異なることに対応することを目的とし,第2の特徴は画像特徴量による検索処理とは別の観点に基づいた検索性能のさらなる改善を目的とする.

グループ法に基づいた画像検索

(1) wavelet特徴とSIFT特徴の組み合わせ

本研究では、従来手法の色特徴では検索性能が出ないことに対処するため,wavelet特徴とSIFT特徴による画像間距離を各々dw,dsとした場合,次式による画像間距離dwsを新たに定義して用いた.
   dws = k・ds + (1−k)・dw         (1)

k (0≦k≦1) は重み係数でチューニングして最適値を設定した.

(2) 画像グループの類似度に基づく画像検索

提案する検索手法の概要を図3.1に示す.はじめに,観光地ごとに観光名所に基づいて動画像グループ(図3.1[1])とWeb画像グループ(図3.1[2])を作成する.前記(1)式の画像間距離を用いて検索対象の動画像グループとWeb画像グループごとに最小画像間距離の総和に基づいて最類似のWeb画像グループを選択する(図3.1[3]).選択したWeb画像グループの中で,上記の最小画像間距離に対応するWeb画像を動画像と対応する画像として選択する(図3.1[4]).

図3.1 グループ法による画像検索アルゴリズム

 

実験結果

実際に撮影した動画像20枚(5地域×4枚)とWeb画像1210枚(242地域×5枚)で実験を行った.各特徴量による実験結果を表3.1に示す.wavelet特徴とSIFT特徴を組み合わせてグループ処理を適用した場合が最も検索性能が良いことが分った.またその場合,動画像グループに対応するすべてのWeb画像グループを正しく検索することができた.

表3.1 各特徴量による実験結果

4. 動画像の検索速度の改善

YouTubeに代表される動画像投稿サイトには、違法な複製動画像が大量に存在し,今後も増加することが考えられる.このような複製動画像は著作権を侵害し,ビジネスチャンス発展の弊害になっている.このような背景から,この研究では類似動画像に対して検索性能が良く高速検索が可能なTiny LSH法に基づいた大規模動画像の検索手法を提案する.

Tiny LSHによる類似動画像の高速検索

(1) RGB色空間に基づいた画像特徴量

 1秒ごとの動画像に対して,4×3の領域分割を行い,各領域の RGB平均値を計算し,値に応じてビットシフト処理したデータを画像特徴量とした.

(2) Tiny LSHとDirect-Mapped Cacheの組み合わせ

 生成したRGB特徴量に対してハッシュ関数を適用し高速検索を行うために,SPAMフィルタに適用されたポインタ処理手法を組み合わせた.

(3) 提案手法による高速動画像検索の原理

 原ビデオと検索対象のビデオ断片に対して,上記で説明した画像特徴量とTiny LSH処理を行い図4.1に示す原理図に基づいて検索を行う.

     図4.1  提案手法による高速動画像検索の原理

実験結果

性能評価を行うために,原動画像と複製動画像を真似た検索用動画像として30分のテレビドラマコンテンツを177話分,総時間88.5時間のテストデータを用意した. 原動画像として,720×480画素,800kbps,30fps,複製動画像は原動画像の画面中央648×432を抜き出し,その後360×240にスケーリングした後320kbps,12fps,MPEG2で再エンコードした.性能評価は,複製動画像を30秒〜180秒の動画像断片に処理し,各動画像断片が原動画像と対応する位置で検出できるか実験した.

 実験の結果,180秒の複製動画像の断片を88.5時間分の原動画像から0.1秒以内に正解率95%で検索することができた.(図4.2,図4.3)

 図4.2 LSHポインタ探索範囲 V.S. 正解率特性

 図4.3 LSHポインタ探索範 V.S. 検索時間

提案手法の必要メモリ量

 評価データに基づいて,大規模動画像での検索処理を見積もったところ,136年分の動画像コンテンツの検索にも対応できることが分かった.(図4.4)

図4.4 提案手法のメモリ占有量の見積もり

提案手法と従来手法の性能比較

 ハッシュ関数を用いた従来手法と提案手法である の比較で主たるポイントは検索時間である.そこでハッシュを用いた代表的な従来手法であるチェイン法を用いて作成したシステムと提案手法によるシステムとの性能比較を行った.(図4.5

 従来手法では,ハッシュ値の衝突のために 136年の大規模データには対応できないことが分かる。

 図4.5 提案手法と従来手法の性能比較

6. 結論

 大量の動画像が扱い易くなった背景から,画像検索性能の改善を目的に研究を行い,以下の成果を出すことができた.

参考文献

[1] Noboru Murabayashi, Setsuya Kurahashi, Kenichi Yoshida: Group-Based Image Retrieval Method for Video Annotation. Proc. SAINT 2008: pp.126-132

[2] 村林昇、倉橋節也、吉田健一、「ビデオ画像へのアノテーションのためのグループに基づいた画像検索手法」 人工知能学会論文誌,vol.24,No.2,pp203-213 (2009-01)

[3] Kenichi Yoshida, Noboru Murabayashi: Tiny LSH for Content-based Copied Video Detection. Proc. SAINT 2008: pp.89-95

[4] 村林昇、吉田健一、「Tiny LSH とDirect-Mapped Cacheによるビデオクリップの高速検索手法」、信学技報,vol.109, No.21, IE2009-1, pp.1-6, 2009