1. 概要

画像の領域・空間情報を統合して表現するためには、グラフというデータ構造 を用いた表現が有効である。本研究では階層化属性付き関係グラフを用いて、 画像の構造や数値情報を統合して表現する。またグラフマッチングの高速化に ついても研究を進めている。

2. 階層化属性付き関係グラフの画像検索への応用

グラフ構造というデータ構造は、画像の空間的な情報(画像構造)と画像の領域 に関する情報とを統合して記述できるという点で、非常に強力な画像表現モデ ルとなる。ただしこのような優れた能力にもかかわらず、これまでの研究でグ ラフ構造がそれほど用いられてこなかったのは、このグラフ構造を扱うための 計算量が大きくなることが主要な原因であったと考える。そこで本研究では、 まずグラフ構造を画像検索用インデックスとして用いるための方法について検 討し、また特に画像検索で重要となる類似度の計算方法の高速化について研究 を進める。主要な検討課題は以下の通りである。

  1. 画像特徴から画像表現モデル(グラフ構造)への構造化 さまざまな画像処理アルゴリズムによって得られた画像特徴をグラフ構造に構 造化するための方法や、数値情報とシンボル情報を統一的に記述するための方 法について考える必要がある。
  2. 類似度計算方法(グラフマッチング) 2個のグラフ構造 の間で距離を計算するアルゴリズムをグラフマッチングと呼ぶ。この距離を非 類似度とみなすことで類似画像検索が可能となるが、よい結果を得るためには 適切な距離計算法を定義する必要がある。
  3. グラフマッチングの高速化 グラフ構造を画像表現モデ ルとして利用する際の最大の障壁は、グラフマッチングに大きな計算コストが 要求されるという点にある。この問題は原理的にはNP完全問題であると言われ ているので、すべての場合において高速な計算法を発見することは不可能であ るにしても、ヒューリスティックな知識を活用したり近似解を求めたりする方 法で計算を高速化する余地はまだまだ大きいはずである。

本研究では、従来の属性付き関係グラフの考え方を発展させ、「階層化属性付 き関係グラフ」という画像表現モデルを提案する。この画像表現モデルでは、 画像の空間情報と領域情報とを統合して記述することができ、またシンボル情 報と属性値としての数値情報との両者を統一的に記述可能である。したがって 高度で強力な類似度の計算が可能となり、特に画像内容を重視するような高度 な検索用途への応用を目指す。このような個々の課題に関してモデルを洗練さ せていくことで、超高速の検索用途には向かないにしろ、グラフ構造を汎用性 のある画像表現モデルとして位置付けていこうと考えている。

3. 関連するトピック

群化

画像の空間的情報は画像の領域情報に比べて記述が難しい。それは、要素間の 関係という概念が漠然としており、明確に定義できないことが主要な原因であ ると言える。そのような際に、要素のまとまりをグルーピングする方法が群化 である。この群化にはいくつかの方法が提案されているが、中でも最も有名な 方法は、「ゲシュタルト心理学」で定性的に述べられた要素間の関係を計算論 的にモデル化して用いる方法である。他にも仮想エネルギーを用いた方法など が提案されている。これらを用いて、認知科学的により妥当な「関係」の構築 方法についても検討していきたい。

4. 参考文献(全リスト

  1. 北本 朝展, "領域・空間情報を表現するグラフ構造を用いた類似画像検索", 東京大学工学系研究科電子工学専攻博士論文, 1997年03月 [ 概要 ]
  2. Asanobu KITAMOTO, "Similarity Retrieval of Natural Images by Integrating Spatial and Shape Information", 東京大学工学系研究科電子工学専攻修士論文, 1994年03月 (in English) [ 概要 ]
  3. 北本 朝展, 高木 幹雄, "類似画像検索への応用を目的とした階層化属性付きグラフマッチングの高速化", 画像の認識・理解シンポジウム (MIRU'96), Vol. II, pp. 331-336, 1996年07月 [ 概要 ] [ PDF ]
  4. Asanobu KITAMOTO, Mikio TAKAGI, "Retrieval of Satellite Cloud Imagery Based on Subjective Similarity", Proceedings of the 9th Scandinavian Conference on Image Analysis (SCIA'95), pp. 449-456, 1995年06月 (in English) [ 概要 ] [ PDF ]