担当教員
TA
コンタクト
 
質問や連絡事項などは、TAである廣田のメールアドレス(hirota (at) mma.cs.tsukuba.ac.jp )まで送ってください。
連絡事項
概要
現在,計算機システムによるマルチメディアデータの蓄積が進んでいる. これらの計算機システム群は高速なコンピュータネットワークで接続されている. このような環境では, 蓄積されたマルチメディアデータを対象とした的確な情報獲得のための 方法論が重要である.
本実験では,マルチメディア情報群を対象とした 情報検索の基礎となる技術を習得することを目的とする. WWW上に存在するメディア情報を対象とした検索エンジンを作成し, その検索エンジンをWWW環境で利用できるシステムを構築する. さらに,対象となるメディア情報群それぞれに対する属性群および それらに基づいた類似度の計量方式を設計する. これらの実現を通じて,メディア情報の検索方式の基礎を学習する.
実験の課題
課題1:WWW上におけるメディア情報検索インターフェースの作成
この課題では,メディア情報検索の導入として, WWW上におけるメディア情報検索インタフェースを作成する. WWW上でメディア情報検索を行うためには,以下のものが必要となる.
  1. ユーザが検索キーワードを入力するページ
  2. 検索エンジンを呼び出し,返ってきた検索結果を表示するCGI
  3. 検索エンジン本体
  4. 検索の対象となるデータ群
これらを用いた処理の流れは,次のようになる.
Web
ブラウザ
ー 要求 →
← 結果 ー
WWW
サーバ
ー 起動 →
← 結果 ー
CGI
スクリプト
ー 起動 →
← 結果 ー
検索
エンジン
 
課題1-1:WWW検索エンジンの作成
Sampleを参考にして,PHP・Ruby・Pythonなどの言語を用いて WWW上で動作する情報検索システムを構築せよ. Sample ScriptはPerlで記述されているが,適宜参考にしてよい. また,余力があれば,検索エンジン(Sampleのsearch.plに相当)を改良し, AND検索,OR検索,および特定の属性のみを対象とした 絞り込み検索機能などを実現せよ.
Sample Script
課題1-2:データ登録機能の追加
課題1-1で作成したシステムに検索対象データを登録する機能を追加せよ.
検索エンジンと同様に,WWW上で操作(登録)できるようにすること.
課題2:メディア情報検索システムの構成
この課題では,メディア情報検索の基礎として, メディア情報検索システムの基本設計について実習する. メディア情報検索の基本的な機能の1つとして, 印象や内容によるメディア情報検索を実現する機能が重要である. 印象や内容によるメディア情報検索においては, メディア情報の内容の表現方法,定義方法,検索方法が重要である. メディア情報の検索方法を大別すると,次の2つの方法がある. メディア情報そのものを検索に用いる直接的な方法とは, 例えば画像データのピクセルや音声データの波形の部分的なパターンマッチングなどによる方法である. メディア情報そのものでなくメタデータを用いる間接的な方法とは, 画像データや楽曲データに付与された属性群をメタデータとして利用し, 検索問い合わせとメタデータの類似度を計量することにより検索を行う方法である. 一般にメディア情報を対象とした間接的な検索を可能とするシステムは次の手順で設計する.
  1. 対象となるメディア情報群の設定
  2. メディア情報群を対象とした検索のための属性群の設定
    (メタデータの構造の設定とメディア情報のメタデータの設定)
  3. 属性群を対象とした類似度の計量方式の設定
これにより,メタデータを介してメディア情報どうしの類似度が 計量可能となる. すなわち,検索者から検索キーとしてあるメディア情報が入力されると, 設定された属性群(メタデータ)について類似度を計量し, 検索キーと類似するメディア情報群を類似する順に検索結果として 出力するシステムの実現が可能となる.
設計例:画像データを対象とした類似画像検索システム

WWW上に存在する画像データを対象とした場合の, 類似画像検索を実現するシステムの設計例を示す. ここでは,以下の5つの画像を対象とする.
Image1: img1 Image2: img2 Image3: img3 Image4: img4 Image5: img5
これらの画像を対象として,画像の色情報に着目し, R,G,Bの属性を例えば次のように設定する. これが各メディア情報のメタデータである.
Image ID R G B
Image1 0.2 0.5 0.5
Image2 0.3 0.4 0.7
Image3 0.8 0.5 0.7
Image4 0.5 0.5 0.5
Image5 0.1 0.7 0.4

類似度の計量方式として, ベクトルの内積による類似度を設定する. この類似度計量方式により, 例えば Image1 と Image2 の類似度は ( 0.2 * 0.3 ) + ( 0.5 * 0.4 ) + (0.5 * 0.7 ) = 0.61 と計算できる.一方,Image2 と Image3 の類似度は, ( 0.3 * 0.8 ) + ( 0.4 * 0.5 ) +( 0.7 * 0.7 ) = 0.93 と計量できる.この結果,Image2 は Image1 よりも Image3 により類似していることが計算できる.

以上の例のように,属性群と類似度の計量方式を設定することにより, 画像の類似度を計算することが可能となる. これをシステム化することにより,WWW上の画像データを対象とした 類似画像検索システムを実現することが可能となる.
この例では画像メディア情報の色情報(R,G,B)に着目して 属性を設定したが,画像メディア情報中の出現オブジェクト群, 感性キーワード群などに着目した属性の設定により, 様々な視点によりメディア情報を検索可能なシステムを実現できる. また,音楽メディア情報を対象とした音の高さやテンポなどの 構造要素に着目したり,動画メディア情報を対象とした シーンの変化などに着目した属性を設定することにより, マルチメディア情報を対象としたシステムの実現が可能となる.
適切な属性の設定を行うことにより, マルチメディアデータを対象とした様々な視点からの検索が可能となる. この属性について十分な設計を行うことにより, 興味深いメディア情報検索システムの構築が可能となる.
課題2-1:類似画像検索システムの実現
上に示した例に添って, 画像データを対象とした類似画像検索システムを実装せよ. 課題1で実装したインターフェースを応用することにより, WWW上で画像検索,および検索対象となる画像の新規登録が 行えるシステムを作成せよ. 条件は以下の通りとする.

検索者からの入力 システム内に定義された画像データのいずれか
検索者への出力 入力した画像との類似度が大きい順にソートされた画像データのリスト
課題2-2:メタデータの自動抽出
課題2-1では,メタデータ(各属性群)の値の設定を人間が手動で行った. この課題では,入力された任意の画像に対するメタデータの抽出と設定を自動化することによりシステムの拡張を行う.
画像のRGB値の自動抽出

画像データからRGB値を抽出しやすい画像フォーマットとしてppm形式がある.
(参考資料:画像フォーマット ppm形式の詳細とヒント
各画像フォーマットからppm形式への変換は,xvやconvertで実行できる.
【convertコマンドを使った例】
% ls
sample.jpg
% convert sample.jpg sample.ppm
% ls
sample.jpg sample.ppm
課題:

入力された画像データから,RGB値を自動抽出するモジュールを作成し, 検索対象登録時の属性群の入力を自動化せよ. さらに,それを用いて課題2-1で作成したシステムを拡張し, 任意の画像を検索キーとして入力可能なシステムを実現せよ. 条件は下記の通りとする.

検索対象の数 10以上(5つ以上追加すること)
検索者からの入力 任意の画像ファイルまたはそのURL
検索者への出力 入力した画像との類似度が大きい順にソートされた画像データのリスト
課題2-3:メディア情報検索システムの実現
課題2-1の実現方式に沿って, 対象とするメディア情報群の種類, 検索のための属性群(独自の属性群), および属性群を対象とした類似度計量方式の設定(メタデータの設定) をそれぞれ設計,WWW上で検索, および検索対象となるメディア情報の追加などが行えるシステムを実装せよ. また,余力があれば,設定したメタデータの自動抽出を実現し, 課題2-2を参考にシステムを拡張せよ. 条件は下記の通りとする.

メディア情報の数 10以上
検索者からの入力 メディア情報のファイルまたはその URL
検索者への出力 入力したメディア情報との類似度が大きい順にソートされたメディア情報群のリスト
課題3:メディア情報検索における数理的モデリングの基礎
メディア情報検索において,検索問い合わせに対して検索結果をどのようにランキングするか (或いは,検索問い合わせと各検索対象の間の相関の大きさをどのように計量するか) は重要な課題である. 検索対象となるメディア情報の属性を適切に定義し, それらの間の関係を数学的に計量可能なモデルを設計することにより, 実用的なメディア情報検索システムの構築が可能となる.
Web上のドキュメント集合を対象とした検索エンジン Google が注目を浴びている. Googleでは,PageRankと呼ばれる独自の指標により対象となる各ページの重要度を決定し, それを元に検索結果のランキングを行っている. PageRankの概要を以下に示す. PageRankの特徴はページ間のリンク構造に注目している点にあるが, 被リンク,すなわち「そのページがどのような(どれだけ重要な)ページからリンクされているか」を反映することにより, 高精度なランク付けを実現している.
PageRankの概要
 
WWW上のドキュメント間のリンク構造を有向グラフとみなし, 隣接行列Aを作成する. n個のドキュメントに対して,An次正方行列となる. 行列Aの各要素aijの特徴づけは以下の方針により行われる.
  • aij = 1 (ドキュメントiに,ドキュメントjへのリンクがある場合)
  • aij = 0 (それ以外の場合)
例えば,以下の左図のようなリンクを持ったドキュメント集合を想定した場合, 隣接行列は右図のようになる. Documents and its link.
Matrix A.
次に作成した行列Aを転置し,各列要素をそれぞれ1ノルムで正規化することにより, 推移確率行列Mを得る. Matrix M.
Mを固有値分解し,最大固有値に対応する固有ベクトルxを求める. このxの各要素が, その添字番号に対応するIDを持つドキュメントのPageRankである.
3-1:PageRankの算出
仮想的なドキュメント集合とそれらの間のリンク構造を自由に設定し, 上記に従って実際にPageRankを算出せよ. このとき,ドキュメント数は7つ以上とすること.
ただし,必ずしもWWW上で動作させる必要はない. また,実装環境は自由に設定してよい. (Matlab,Scilab,各種言語向け固有値計算ライブラリなど好きなものを用いてよい)
3-2:Web文書検索システムの構築
課題3-1で計算したPageRankを用いて, WWW上で動作可能な文書検索エンジンを構築せよ. すなわち,課題1-1で作成した検索エンジンを課題3-1のドキュメント集合に適用し, PageRankを元に表示順を決定するように改良せよ. また,余力があれば,検索キーワードと検索対象の関連の大きさなどを考慮したランキング方式を実装せよ.
(参考:"TF-IDF","Latent Semantic Indexing" など)
注意事項
関連科目
参考文献