Comments
Description
Transcript
Web 画像検索技術に関する研究動向 Abstract
2003 年 7 月 11 日 大学院輪講資料 Web 画像検索技術に関する研究動向 A Survey of Searching for Images on the World-Wide Web 相澤研究室 新領域創成科学研究科 基盤情報学専攻 修士 1 年 10392 中平 浩二 Abstract 2 The amount of information on the web is growing rapidly. People use search engines such as Google, and AltaVista to get information they want. But, the performances of search systems which deal with multi-media contents on the WWW are not well. On this paper, I show the anatomy of searching system, and recent studies of searching for Images on WWW. Google や AltaVista、Yahoo!に代表されるテキス ト検索エンジンは、ディレクトリ型検索エンジンと ロボット型検索エンジンに大別される。Yahoo!など のディレクトリ型検索エンジンにおいては、実際に 人間がウェブサイトやウェブページに情報やキー ワードを付加して詳細なカテゴリー別にデータベ ースに登録する。検索者はディレクトリ構造を探す か、キーワード検索によって目的のコンテンツを探 し出す。このディレクトリ型検索の特徴は、人間が コンテンツを選別して登録されるため、検索結果に 現れるコンテンツの質が高いという点が挙げられ る。しかし、WWW 上に数十億サイトものコンテ ンツがある今日において、人間の登録作業には限界 があり、検索結果のコンテンツの全体数が少ない。 さらにアルゴリズムの改善によりロボット検索エ ンジンも検索結果の質やノイズの除去率が飛躍的 に向上している。そのため現在ではロボット型検索 エンジンが主流となっている。ロボット型検索エン ジンではコンテンツの収集からデータベースの構 築まで全てプログラムで行う。精度の向上や処理時 間の短縮のために多くの研究が行われてきた。 1 はじめに 近年インターネット上のコンテンツは爆発的に 増大しており、利用者が自分の望むコンテンツを選 び出すためには検索エンジンの利用が欠かせない。 しかし、書式が統一化された文献資料や一般のデー タベースと違い、Web コンテンツは様々なスタイ ルで記述されており、また頻繁に更新されたり消滅 したりする。このため、Web 検索において精度の 良い検索結果をかつ素早く得るためには様々に工 夫をしなければならない。 1994 年に初の Web 検索エンジン”WWWW”が登 場して以来、テキスト検索をメインとした種々の検 索エンジンが登場し、発展してきた。しかし Web 上の画像等のマルチメディアコンテンツを対象と した検索システムに関しては、まだ試みがそれほど 多くなく、精度が悪かったり処理時間が長かったり しているのが現状である。テキスト検索では直接的 にキーワードをマッチングすれば良いのに対し、画 像検索においては、何かしらの手段によって画像と ワードを対応付けたり、画像をキーとして画像解析 による比較を行ったりしなければならない。従って 上述の問題点が出てくる。そのため、出来るだけこ れらを改善しようと様々なアルゴリズムの提案や 改善が研究されている。 また、画像検索に関してはどのようなインターフ ェースやサービスを提供するかという点も重要な 課題である。 本稿では第２章で Google を中心とした一般の検 索エンジンの構造と用いられているいくつかの技 術について述べ、第３章では様々な画像検索技術に ついて解説する。第４章では Web 画像検索エンジ ンの構造について説明する。 テキスト検索エンジン 2.1 Google のシステム構成 ロボット型検索エンジンの例として、Google の 構成システムを Figure1 に示す。 Figure1. Google Architecture 1 URL Server には収集すべきコンテンツの URL が格納されている。URL Server から URL リスト を受け取った複数の Crawler によって Web ページ が収集される。収集されたコンテンツからリンクさ れている URL を URL Server に格納し、コンテン ツは圧縮され、Repository に格納される。Indexer によりコンテンツの HTML 解析が行われ、word や word の位置情報、フォントサイズ、及び Anchor が抽出される。全ての word とコンテンツには wordID と docID が付けられ、これらのハッシュテ ーブルと、wordID と docID との索引が Barrels に 格納される。検索者がキーワードを入力すると対応 する wordID に変換され、索引を参照し、対応する docID のコンテンツが返される。 あるページの 評価値 を、そのページに存在する発 リンク数で割った数が、それぞれ被リンク先の評価 値に加算されるという関係になっている。すなわち、 単に被リンク数の多寡だけではなくお勧め度の高 いページからのリンクは高く評価する。また同時に、 総リンク数が少ないページからのリンクは高く評 価し、総リンク数が多いページからのリンクは低く 評価する。 評価値は次式を繰り返し適用すること で求められる。 ε R(q) n outdegree(q ) R( p ) はページ p の評価値、 R (q ) はページ q の評 R( p) = + (1 − ε ) ⋅ ∑ 価値を示す。n は対象とするグラフ G(Web ページ をノードとし、Web ページ間のリンクをエッジと し た グ ラ フ ) の ノ ー ド 総 数 (Web ペ ー ジ 数 ) 、 outdegree(q)はページ q からの外向きリンク数であ る。εは減数定数で、0.1∼0.2 の間に設定される。 モデル的には、ユーザが(1−ε)の確率で現在の Web ページを辿り、εの確率で全く無関係な Web ページへ移動することを繰り返したとき、あるペー ジにいる確率がそのページの評価値となる。どこか らもリンクを持たないページの評価値はε/n とな る。Google では検索結果のランク付けにおいては、 この PageRank 法と検索語がコンテンツ中にどの 様な状態で現れているかという情報が組み合わさ れて計算されている。 ランキング手法の別の一つとして HITS がある。 PageRank 法においては事前に WWW 全体での重 要度を計算しておくために、検索質問とは無関係な 値になる。HITS はある特定のトピックに関する WWW グラフからオーソリティとハブを抽出する。 オーソリティとはそれ自身が情報を提供している ページであり、ハブとは多くのオーソリティをリン クするリンク集的なページである。オーソリティと ハブは相互再起的な関係にあり、あるページのオー ソリティスコアはそのページを参照するページの ハブスコアの和であり、ハブスコアはそのページが 参照するページのオーソリティスコアの和となる。 HITS では、文字列検索の結果から得られる比較的 小さな WWW グラフからオーソリティを求めるこ とから、検索質問に関連した重要なページを求める ことが出来る。しかし、HITS を用いても、しばし ば検索質問とあまり適合しないページがランキン グ上位になる事がある。これはトピックリフト問題 と呼ばれる。 2.2 ランキング 検索者が用いるキーワードは一般に１∼２個で あり、データベースからマッチングで選出されるコ ンテンツは時に数十万と大量となる。しかしこの中 には検索者が必要としないものやノイズが大量に 入っている。従って検索者の質問と検索対象の適合 度を計算し、ランク順に検索者に示す必要がある。 これを実現する手法の一つとして Google で用いら れている PageRank 法がある。 PageRank 法はリンク構造を解析することによ り、各々のページのランキングをするものである。 良質なページほど多くのページからリンクされて いるという考えに基づいており、ページＡからペー ジＢへのリンクをページ A によるページ B への支 持投票とみなし、そのページの重要性を判断する。 しかし単に被リンク数のみで評価すれば、故意にミ ラーページから多数のリンクを行う(スパム行為)こ とで評価があがってしまう。従ってこの手法では、 リンク元のページの重要度も評価の対象としてい る。PageRank 法の概念図を Figure2 に示す。 Figure2. Simplified PageRank Caluculation 2 3 間の距離を求める。距離が近いほど、その二つの画 像は色の尺度において類似していると言える。 RGB 尺度の他に HSV 尺度や L*a*b*尺度なども 用いられる。HSV 尺度は色相、彩度、明度で表し たもので、画像の明るさに左右されずに色比較を行 うことが出来る。また、L*a*b*尺度は空間内の任 意の２色間の幾何学距離が、人間の感じる類似度に 合うように調整されている。 画像解析技術 一般の画像データベースを対象とした検索シス テムの研究は非常に多くなされている。しかし、 Web 検索システムとした場合に、大多数の検索者 を満足させるほどの精度や処理時間は実現されて いない。現在サービスが提供されている Web 画像 検索エンジンも精度が悪く、ノイズが入りやすい。 従って Web 画像検索においてはシステム全体とし て、画像解析とテキスト解析を組み合わせたもので なくてはならない。テキスト解析に関する技術は第 ２章で述べた。この章では画像解析に関する技術、 及びそれを利用した、画像データベースに対する一 般画像検索システムの紹介を行う。 3.1 3.1.2 テクスチャ テクスチャ情報は、主に全体画検索に用いられる。 画像に表れている面の構造的配置や周りの環境と の関係を推測する上で重要な情報となる。同時生起 行列やフーリエ変換を用いた手法があるが、近年は ウェーブレット変換を用いるのが主流となってい る。画像を低周波と高周波に分解し、このスペクト ルの比較を行う。 画像特徴量 画像解析には、検索の目的に応じて画像全体を対 象とした全体画検索と、画像内の部分に着目した部 分画検索がある。全体画検索は画像全体の色合いな どに基づいて類似画像を検索するもので、部分画検 索は建物や車といった特定のオブジェクトが含ま れる画像を検索するのに用いられる。各々で用いら れる特徴量の種類を Figure3 に示す。 3.1.3 形状 部分画像検索オブジェクトに対しては形が重要 な特徴量である。オブジェクトの面積や、縦横比、 オブジェクトの面積を外周の事情で割った真円比 などは簡単に決定できる特徴量であり広く用いら れている。また、別の方法として外接円からの差分 距離やエッジベクトルを利用する方法がある。外接 円を用いた方法は、オブジェクトの輪郭と外接円の 距離を適当な次元で区切ってヒストグラムにする。 適当な位置を開始点とすることにより、回転に対応 できる。エッジベクトルを用いた手法では、オブジ ェクトの輪郭に沿ったベクトルの方向と強さをヒ ストグラムにする。 3.2 オブジェクトの認識 3.2.1 グリッド分割法 入力画像を M×N 個の長方形のブロックに分割 し、各ブロックについて特徴量を計算する。画像を キーとして入力すると、キー画像自体もブロックに 分割され、特徴量が計算される。照合では描画され たブロックに対して入力画像の対応する位置のブ ロックと近傍の位置で類似度が計算される。この手 法は誤差が大きく、全体画像に対して同じ位置にあ るオブジェクトしか認識できない。 Figure3. Features used for Content Description 3.1.1 色情報 色は画像検索において最もよく使われる特徴量 であり、その表現にはカラーヒストグラムが主に用 いられる。RGB 色尺度で表現された画像全体、ま たはその一部分に対して、RGB の各色範囲ごとに 画像内の画素値を積算することでヒストグラムを 作成できる。実際には RGB の 256 階調を用いると 人間にとって近い色でも別の色と判別されるため、 16 次元ほどに次元縮退が行われる。正規化された ヒストグラムの重なりなどによってヒストグラム 3.2.2 色情報に基づく領域の抽出 近似した色どうしを結合し、画像を色に基づいた 領域に分ける。クリップアートのような色合いのは っきりした画像には向いているが、自然画像を対象 とした抽出方法は確立されていない。 3 3.2.3 閾値の全域調整 閾値を画像ごとで調節しないと領域の過分割や 過統合が起こってしまう。そこで Figure4 に示すよ うに、閾値を段階的に変えていき、その都度現れる エッジによりオブジェクトを抽出する手法が提案 されている。冗長なオブジェクトが含まれるが、有 意義なオブジェクトを多く抽出できる。 Figure5. Example of QBIC 3.4.2 VisualSEEk 画像内の部分領域に着目した検索を行える。特に 複数の領域を指定し、それらの相対的な位置関係に 着目した検索が行える。VisualSEEk の検索インタ ーフェースを Figure6 に示す。 Figure4. Object Extraction by varying Edge 3.3 検索インターフェース 各画像から自動的に抽出した特徴はすべて視覚 特徴であるため、画像解析を用いた検索システム の殆どは、検索者が画像の色、形状などの視覚的画 像特徴を直接入力したり、スケッチや画像を入力し たりして検索するインタフェースを提供している。 しかし、これらの手法は視覚的にクエリに近いもの を検索するので、狭いカテゴリ内の画像を対象にし た小規模の画像データベースでは有効な手法では あるが、Web 上の画像検索のような雑多な画像群 から検索にはあまり有効ではなく、用途が限られる ているのが現状である。 Figure6. Example of VisualSEEk 3.4.3 ExSight 前述の閾値の全域調整を用い、オブジェクトを抽 出し、C-tree により高速照合を可能としている。検 索者はキー画像としてオブジェクトを指定できる。 ExSight の検索インターフェースを Figure7 に示 す。 3.4 画像解析検索システムの例 3.4.1 QBIC QBIC は制止画、及び動画を対象として研究され、 その後商用化された。色とレイアウトに基づく検索 を可能としている。オブジェクトの切り出しに関し ては、クリップアートのような色合いがはっきりし、 背景との分離が容易な画像を対象としている。 QBIC の検索インターフェースを Figure5 に示す。 Figure7. Example of ExSight 4 4 コンテンツへのリンクを URL Buffer へ渡す。 Spider3 のプロセスを Figure9 に示す。 Web 画像検索エンジン 画像検索に関する研究自体は 1970 年代から盛ん に行われているが、WWW 上の画像を対象とした 検索システムの試みはそれほど多くない。検索機能 やインデキシング機能、ランキング機能がテキスト 検索と比べて格段に難しく、今日においても精度や 検索数、処理速度が芳しくない。現在最も使われて いる画像検索エンジンは Google の”ImageSearch” であろう。この GoogleImageSearch はキーワード 入力型の検索エンジンで、テキスト情報を利用した 自動索引付けによる画像検索システムである。一般 の Web コンテンツは画像とテキストで構成されて いるため同じコンテンツ内のテキストの情報が画 像への索引付けに利用しやすい。この技術に関して は 4.2 で述べる。 4.1 Figure9. Spider3 processes each image/video Spider3 は Spider2 から受け取った URL リストを 元に画像データの収集を行い、画像の色ヒストグラ ム、及び画像サイズやファイル名などといった情報 を抽出し、さらにアイコンを作成すし、オリジナル データと共にサーバ内に格納する。アイコン画像は 検索に対する出力結果として用いる。 画像検索エンジンのシステム構成 キーワード入力及び画像入力に対応した、テキス ト解析及び画像の内容解析に基づく画像検索シス テム(CBIR)を実現した”WebSEEk”の構成について 述べる。 WebSEEk の特徴は以下の通りである。 ・ 画像解析を用いた検索 ・ フィードバックを用いた検索インターフェー ス ・ 画像入力による検索 ・ 画像のセミオート分類 4.1.2 画像のセミオート分類 WebSEEk ではテキスト処理技術を用いて画像 の自動分類とインデキシングを行っている。HTML コンテンツを解析し、以下の文字列を抽出する。 <img src=URL alt=[alt text]> <a href=URL>[hyperlink text]</a> URL 文字列、alt text、hyperlink text を単語ごと に分解する。例えば URL=http://server/animals/d omestic-beasts/dog37.jpg なら”animals”,”domesti c”,”beasts”,”dog”が抽出される。これらの単語は自 動分類に用いられるが、キーワード検索のマッチン グにも利用される。システムは各画像に ID を割り 振り、単語→画像の索引付けを行う。これらの単語 の一部をキー言語とし、カテゴライズ化する。キー 単語に索引付けられた画像はそのカテゴリに分類 されることとなる。キー単語を選出するための抽出 された単語の出現頻度によるヒストグラムを作成 する。出現頻度が少ない単語はキー単語にしても検 索者がそのキーワードを用いるとは考えられにく く、意味がない。また、出現頻度は高くても、例え ば”image”や”small”といった画像情報を示す単語 はクラスタリングに用いるキー単語としては不適 切である。また、”rock”のように、２種類の意味を 持つ単語もキー単語には不適切である。出現頻度の 高い単語の内、キー単語としてふさわしいものを人 間が選別し、それらを用いて Figure10 の様な分類 ツリーを作成する。 4.1.1 Crawling WebSEEk の画像収集過程を Figure8 に示す。 Figure8. Image and video gathering process Spider1 は URL Buffer 上の URL リストを元に、 WWW から HTML コンテンツを収集する。Spider2 は HTML コンテンツ上にある画像の URL や画像 へのリンクを抽出し、Spider3 に渡し、また HTML 5 Figure11. Search results manipulation process 検索者が画像 A を入力し、画像集合 B が得られた とする。その中から検索者は最も目的の画像に近い と思われる画像 B を選択し、最も目的の画像から 遠いと思われる画像 C を選択する。すると画像 B を中心にヒストグラム距離計算が行われ、新たな画 像集合が得られ、さらに画像 C とヒストグラム距 離が近いものが削除され、新たな画像集合 D が得 られる。また、別のフィードバックシステムとして、 検索結果の画像集合 B に対し、別の画像 E を入力 することで、画像 E に対する結果である画像集合 F と画像集合 B との和、差、積の画像集合を返して 貰うことが出来る。 Figure10. Portion of image subject taxonomy ツリー上のキー単語に索引付けられた画像も分類 ツリー上に割り当てられる。複数のキー単語に索引 付けられている場合は、URL、alt text などのどこ から抽出された単語かによって重み付けをし、最も 重要度が高い単語の位置にクラスタリングされる。 4.1.3 検索インターフェース WebSEEk における検索は、キーワードによる入 力と画像入力による検索、及びディレクトリ型検索 がサポートされている。ディレクトリ型検索では 4. 1.2 での分類ツリーを検索者が辿っていくことによ り検索する。テキスト検索では、キーワードが入力 されると、単語と画像の索引ハッシュから対象の画 像が選択され、そのアイコンが表示される。キーワ ードに加え、画像の種類やサイズ、Subject も指定 できる。Subject 指定により分類ツリー上のあるカ テゴリ内のみで検索が行える。 検索において画像が入力された場合は、データベ ース内の画像とヒストグラムの比較を行い、ヒスト グラム間の距離が短い順に検索結果として返され る。色ヒストグラムには HSV 表色系を用いている。 ヒストグラム間の距離は以下の式を用いて求めら れている。 4.2 他の Web 画像検索技術 キーワード検索における画像のラベリング手法 がいくつか提案されている。一つは img タグにお ける alt オプションなどのメタ情報の利用である。 画像に対する説明が直接付加されているため、検索 結果の質は高くなる。しかし結果数はとても少なく なる。また別の手法として、HTML コンテンツに おける img タグから近距離にあるテキストを解析 する手法がある。画像から近いテキストは画像と深 い関わりがあるという考えに基づいている。テキス トの含まれる単語の重み付けには、img タグとの距 離を用いるものや、一定距離内のテキストでの単語 ごとの頻度を解析するものがある。前者は距離が近 いほど、後者は頻度が高いほど重み付けが強くなる。 これらの手法は ImageGoogle でも採用されている。 d q , t = (h q − h t ) t A (h q − h t ) ここで A は荷重行列であり、h t と h q は検索画像と 対象画像のヒストグラムである。検索結果に対し、 検索者はフィードバックが行える。このシステムを Figure11 に示す。 6 5 5.1 メラ”や”ノート PC”といったカテゴリ指定の検索 には不向きである。従って、Web 画像検索におい て、検索者がどんな画像を求めているかをシステム が把握し、かつ質の良い検索を実現するためにはテ キスト解析と画像解析技術をうまく組み合わせる 必要がある。また、単一データベースに対する検索 とは異なり、Web 上の画像検索のような雑多な画 像群に対しては、検索結果のランキングにおいて単 に特徴量ベクトルの距離でランク付けすればいい というものでもない。 もう一つの課題はインターフェースである。Web 上ならではこその可能なサービスは無数にあるだ ろう。 以上のように、Web 画像検索にはまだまだ多く の研究の余地が残っている。 画像検索に関するその他の技術 画像のクラスタリング キー画像に対し、データベース内の全ての画像の ヒストグラムとの距離計算をすれば、データベース 内の画像数が膨大な数の時は計算量も膨大なもの となってしまう。そこで画像データベースをあらか じめクラスタリングしておき、キー画像に近いクラ スタ内のみで計算を行えばよい。 5.1.1 教師付き学習 画像データベース内からいくつかをサンプルと して選択し、人間がこれらをクラスタリングする。 画像の特徴量をいくつか抽出し、クラスタを目的変 数、特徴量を説明変数として回帰解析を行う。一度 回帰式が定まれば、今後データベース内に追加され る画像はすぐにクラスタリングできる。 参考文献 5.1.2 SOM 教師無し学習の手法としてよく用いられる。多次 元の特徴量を持つデータを１次元、あるいは２次元 上に自立的に分類していくニューラルネットワー クである。視覚的に分類状況が分かるが、初めに適 当な特徴量を選択する必要がある。 5.2 [1] John R. Smith and Shin-Fu Chang, “Searching for Images and Video on the World-Wide Web” ,Center for Telecommunication Research Technical Report #459-96-25, Aug 19, 1996 [2] Sergey Brin and Lawrence page, “The Anatomy of a Large-Scale Hypertextual Web Search Engine ”, [http://www-db.stanford.edu/~backrub/google.ht ml], Oct 1, 1998 ユーザーの利用履歴の利用 検索者が入力したキーや検索結果の中から実際 に検索者が選択した履歴などを蓄積し、それを解析 し、学習していくことで検索結果の質を高めること が出来る。 5.3 [3] Larry Page, Sergey Brin, R. Motwani, T. Winograd, “The PageRank Citation Ranking: Bringing Order to the Web”, [http://citeseer.nj. nec.com/page98pagerank.html], Jan 29, 1998 既存の検索エンジンの利用 ImageGoogle などの既存の検索エンジンを利用 し、得られた結果を解析し、精度を上げたり、他の 画像のクラスタリングに用いたりしようとする考 えも提案されている。 ６ [4] 串間 和彦, 赤間 浩樹, 他, “色や形状等の表層 的特徴量にもとづく画像内容検索技術”, 情報処理 学会論文誌 TOD1, Feb. 1999 まとめと課題 [5] 原田 昌紀, “WWW サーチエンジンの作り方”, 情報処理 41 巻 11 号 pp.1281-1283, Nov. 2000 本稿ではテキスト解析エンジンと Web 画像解析 エンジンの構造について述べ、画像解析に関する技 術と研究について述べた。 現在サービスを提供している Web 画像検索エン ジンはその殆どがテキスト解析のみによるもので あるが、テキスト解析のみによるものではノイズの 混入率が高く、結果数も少ない。また、色や形など の条件を付加して要求することも出来ない。また、 画像解析のみの検索では、同じ色合いや形の画像の 検索には向いているが、テキスト解析とは逆に”カ [6] 串間 和彦, 赤間 浩樹, 他, “オブジェクトに基 づく高速画像検索システム:ExSight”, 情報処理学 会論文誌 Vol.40, No.2, 1999 [7] Teuvo Kohonen, Jussi Hynninen, Jari Kan gas, Jorma Laaksonen, “ SOM PAK: The SelfOrganizing Map Program Package“, [http://cite seer.nj.nec.com/kohonen96som.html], 1996 7 [8] Keiji Yanai, “An Experiment on Generic “Image Classification Using Web Images”, IEEE Pacific Rim Conference on Multimedia, 2002 [9] 相良 直樹, 砂山 渡, 谷内田 正彦, “HTML テ キ スト の重要 文を 用いた 画像 ラベリ ング 手法 ”, The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 2003 [10] Yong Rui, Thomas S. Huang, “IMAGE RETRIEVAL: PAST, PRESENT, AND FUTURE”, [http://citeseer.nj.nec.com/192987.html], 1997 [11] 福島 俊一, “WWW 情報検索技術と評価の問 題” 情報処理 41 巻 8 号 pp.912-916, Aug. 2000 [12] 風間 一洋, 原田 昌紀, 佐藤 進也, “ハイパー リンクとアンカーテキストを利用した情報検索と ランキングの一手法”, 研究報告 「デジタル・ドキ ュメント」 アブストラクト No.024 – 003, Jul 28, 2000 [13] Google http://www.google.com/ [14] QBIC http://wwwqbic.almaden.ibm.com/ [15] ImageGoogle http://image.google.com/ 8