(57)【特許請求の範囲】
【請求項１】
情報ごとに特徴量を管理する特徴量管理手段と、
前記特徴量管理手段に管理されている特徴量の中で類似する特徴量との関連付けを前記特徴量ごとに保持する特徴量関連付け手段と、
前記特徴量管理手段に管理されている特徴量の空間インデックスを管理する空間インデックス管理手段と、
第一の特徴量と類似する特徴量の検索要求に応じ、前記空間インデックスにおいて第一の特徴量が属する部分空間を判定する部分空間判定手段と、
前記部分空間に属する前記第一の特徴量以外の第二の特徴量と、該第二の特徴量と前記特徴量関連付け手段によって関連付けられている第三の特徴量とについて前記第一の特徴量との類似度を算出し、算出された類似度と所定の閾値との比較に基づいて前記第一の特徴量と類似する特徴量を判定する類似判定手段とを有する情報管理装置であって、
前記類似判定手段は、
前記特徴量関連付け手段による関連付けに基づいて再帰的に特徴量を取得し、前記第一の特徴量と取得された特徴量との類似度を算出し、算出された類似度と所定の閾値との比較に応じて前記第一の特徴量と類似する特徴量を判定し、
前記特徴量関連付け手段による関連付けに基づく再帰的な処理の過程において、一回に取得される特徴量の中で前記第一の特徴量と類似すると判定される特徴量が無いとき、前記再帰的な処理が所定回数行われたとき、一回に取得される特徴量の中で前記第一の特徴量と類似すると判定される特徴量が無いことが所定回数生じたとき、又は一回に取得される特徴量の中で前記第一の特徴量と類似すると判定される特徴量が無いことが所定回数連続したときは、前記再帰的な処理を終了させることを特徴とする情報管理装置。
【請求項２】
新たな特徴量を前記特徴量管理手段に登録するときに、前記特徴量管理手段において管理されている特徴量の中で前記新たな特徴量と類似する特徴量を前記類似判定手段を用いて判定し、類似すると判定された特徴量と前記新たな特徴量との関連付けを前記特徴量関連付け手段に保持させることを特徴とする請求項１記載の情報管理装置。
【請求項３】
情報ごとに特徴量を管理する特徴量管理手段と、前記特徴量管理手段に管理されている特徴量の中で類似する特徴量との関連付けを前記特徴量ごとに保持する特徴量関連付け手段と、前記特徴量管理手段に管理されている特徴量の空間インデックスを管理する空間インデックス管理手段とを有するコンピュータが実行する情報管理方法であって、
第一の特徴量と類似する特徴量の検索要求に応じ、前記空間インデックスにおいて第一の特徴量が属する部分空間を判定する部分空間判定手順と、
前記部分空間に属する前記第一の特徴量以外の第二の特徴量と、該第二の特徴量と前記特徴量関連付け手段によって関連付けられている第三の特徴量とについて前記第一の特徴量との類似度を算出し、算出された類似度と所定の閾値との比較に基づいて前記第一の特徴量と類似する特徴量を判定する類似判定手順とを有し、
前記類似判定手順は、
前記特徴量関連付け手段による関連付けに基づいて再帰的に特徴量を取得し、前記第一の特徴量と取得された特徴量との類似度を算出し、算出された類似度と所定の閾値との比較に応じて前記第一の特徴量と類似する特徴量を判定し、
前記特徴量関連付け手段による関連付けに基づく再帰的な処理の過程において、一回に取得される特徴量の中で前記第一の特徴量と類似すると判定される特徴量が無いとき、前記再帰的な処理が所定回数行われたとき、一回に取得される特徴量の中で前記第一の特徴量と類似すると判定される特徴量が無いことが所定回数生じたとき、又は一回に取得される特徴量の中で前記第一の特徴量と類似すると判定される特徴量が無いことが所定回数連続したときは、前記再帰的な処理を終了させることを特徴とする情報管理方法。
【請求項４】
新たな特徴量を前記特徴量管理手段に登録するときに、前記特徴量管理手段において管理されている特徴量の中で前記新たな特徴量と類似する特徴量を前記類似判定手順を用いて判定し、類似すると判定された特徴量と前記新たな特徴量との関連付けを前記特徴量関連付け手段に保持させることを特徴とする請求項３記載の情報管理方法。
【請求項５】
請求項３又は４記載の情報管理方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報管理装置、情報管理方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、特定の画像を検索条件とし、当該画像に類似する画像を画像データベースから検索する類似画像検索の技術が提案され、製品として実現されている。
【０００３】
一般に、類似画像検索技術では、画像を解析して得られた画像の特徴を示す情報である特徴量を画像登録時に画像と同時に登録する。類似する画像の検索時には、特徴量の類似度を算出し、類似度が所定の閾値より大きい特徴量と対応づけられた画像を類似する画像として検索する。
【０００４】
特徴量の抽出方法として、例えば特許文献１では、人間が受ける類似感覚に適合した類似画像を検索できるようにするため、人間の感覚に即した特徴量を自動的に抽出可能とする特徴量抽出技術が提案されている。
【０００５】
このような特徴量を用いた類似画像検索技術では、特徴量自体は画像登録時に抽出して保管しておき、検索時には画像を参照せずに特徴量のみを用いて検索を行うことができるため、比較的高速に類似画像情報の検索を実行することができる。
【０００６】
但し、上述のような類似画像検索技術では、検索時に登録されている全ての画像の特徴量との類似度を逐一計算することになるため、登録画像数が増加するとともに検索処理速度が低下するという問題があった。
【０００７】
そこで、特許文献２には、画像の登録時に画像データベースから予め当該画像と類似する画像のリストを検索し、保持しておき、検索時には当該リストを用いて類似する画像を検索する技術が提案されている。斯かる技術によれば、検索時における類似度の算出処理が不要となるため、登録画像数が増加した場合であっても類似画像の検索処理を高速化することができる。
【特許文献１】特開２０００−１８７７３１号公報
【特許文献２】特開２００７−８０２１０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献２に記載された技術では、予め蓄積された画像に類似する画像を高速に検索することは可能であるが、蓄積されていない画像に類似する画像の検索については対象とされていない。
【０００９】
本発明は、上記の点に鑑みてなされたものであって、類似する情報の検索を適切に高速化することのできる情報管理装置、情報管理方法、及びプログラムの提供を目的とする。
【課題を解決するための手段】
【００１０】
そこで上記課題を解決するため、本発明は、情報ごとに特徴量を管理する特徴量管理手段と、前記特徴量管理手段に管理されている特徴量の中で類似する特徴量との関連付けを前記特徴量ごとに保持する特徴量関連付け手段と、前記特徴量管理手段に管理されている特徴量の空間インデックスを管理する空間インデックス管理手段と、第一の特徴量と類似する特徴量の検索要求に応じ、前記空間インデックスにおいて第一の特徴量が属する部分空間を判定する部分空間判定手段と、前記部分空間に属する前記第一の特徴量以外の第二の特徴量と、該第二の特徴量と前記特徴量関連付け手段によって関連付けられている第三の特徴量とについて前記第一の特徴量との類似度を算出し、算出された類似度と所定の閾値との比較に基づいて前記第一の特徴量と類似する特徴量を判定する類似判定手段とを有することを特徴とする。
【００１１】
このような情報管理装置では、類似する情報の検索を適切に高速化することができる。
【発明の効果】
【００１２】
本発明によれば、類似する情報の検索を適切に高速化することのできる情報管理装置、情報管理方法、及びプログラムを提供することができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面に基づいて本発明の実施の形態を説明する。本実施の形態では情報として画像情報を登録し、画像情報に類似する画像を検索する類似画像検索処理に本発明を適用した例について説明する。なお、扱う情報は画像情報に限られるものではなく、特徴量を比較することにより類似情報を検索するものであればあらゆる情報を対象とすることができる。例えば、文書データ、音声データ、動画データ、情報を解析して出力された解析データなどの管理に本発明を適用するように構成してもよい。
【００１４】
図１は、本発明の実施の形態における情報管理装置の機能構成例を示す図である。同図において、情報管理装置１００は、検索条件の入力や検索結果の表示を行うユーザＩ／Ｆ２０１を備えた複数のクライアントＰＣ（Personal Computer）２００ａ、２００ｂ（以下、単にクライアントＰＣという。）と、インターネット又はＬＡＮ（Local Area Network）等のネットワーク（有線又は無線の別は問わない。）を介して接続されている。
【００１５】
情報管理装置１００は、主要なハードウェアとして、ハードディスクドライブ（ＨＤＤ：Hard Disk Drive）１２０を備えている。また、主要なソフトウェアプログラムとして、入出力制御部１０１と、特徴量抽出部１０２と、登録部１０３と、削除部１０４と、検索部１０５と、類似度算出部１０６と、インデックス生成部１０７とを備えている。これら各部は、ＲＡＭ１１０上にロードされ、非図示のＣＰＵにその機能を実現するための処理を実行させる。
【００１６】
ＨＤＤ１２０は、画像データ記憶部１２１と、メタデータＤＢ（Data Base）１２２と、特徴量ＤＢ１２３と、類似情報リストＤＢ１２４と、特徴量インデックス１２５とを格納する記憶手段である。なお、記憶手段はＨＤＤに限られるものではなく、光ディスク、メモリカードなどの一般的に利用されているあらゆる記憶手段により構成することができる。
【００１７】
画像データ記憶部１２１は、画像データそのものを格納する記憶部である。格納する方法としては、ＯＳ（Operating System）が提供するファイルシステム上に格納する方法、画像データを格納する画像データベース上に格納する方法などの一般的に利用されているあらゆる方法を適用することができる。
【００１８】
メタデータＤＢ１２２は、画像データの属性を表すメタデータを格納する記憶部である。図２は、メタデータＤＢのデータ構造の一例を示す図である。同図に示されるように、メタデータＤＢ１２２は、画像ＩＤと、画像データのメタデータの一例である画像ファイル名とを対応づけて格納している。
【００１９】
なお、メタデータは画像ファイル名に限られるものではなく、画像データの属性を表すものであればあらゆる情報をメタデータとして格納することができる。
【００２０】
画像ファイル名は、画像データ記憶部１２１のいずれの位置に画像が保存されているかを識別するために利用される。なお、画像データを外部システムに記憶し、画像ファイル名に当該外部システムを識別する情報を含めるように構成してもよい。例えば、画像データをインターネット上の外部サーバに保存し、画像ファイル名をＵＲＬ（Uniform Resource Locator）で表すことにより、外部システムに保存されている画像情報を管理できるように構成してもよい。
【００２１】
特徴量ＤＢ１２３は、画像データ記憶部１２１に記憶されている画像の特徴量を格納する記憶部である。図３は、特徴量ＤＢのデータ構造の一例を示す図である。同図に示されるように、特徴量ＤＢ１２３は、画像ＩＤと、画像の特徴量とを対応づけて格納している。
【００２２】
画像の特徴量としては、例えば、画像のカラーヒストグラムなどのベクトルデータが利用できる。同図では、画像ＩＤ＝１で識別される画像の特徴量のベクトルデータが[a1,a2,…,an]、画像ＩＤ＝２で識別される画像の特徴量のベクトルデータが[b1,b2,…,bn]（ｎは整数）で表された例が示されている。なお、画像の特徴量としては、色合い、色の分布、構図、模様などの一般的に利用されているあらゆる特徴量を保存することができる。なお、特徴量は必ずしも元となる情報（本実施の形態では画像）と異なる形式でなくてもよい。元となる情報によって類似度の判定が可能であれば、元となる情報そのものを特徴量として扱ってもよい。
【００２３】
類似情報リストＤＢ１２４は、画像データ記憶部１２１に記憶されている各画像について、特徴量が類似すると判断された類似情報を格納するものである。図４は、類似情報リストＤＢ１２４のデータ構造の一例を示す図である。同図に示されるように、類似情報リストＤＢ１２４は、画像ＩＤと、類似する画像の画像ＩＤである類似画像ＩＤおよび類似度の組を少なくとも１つ含む類似情報リストとを対応づけて格納している。類似度の算出方法については後述する。
【００２４】
図５は、類似情報リストＤＢ１２４のデータ構造の別の一例を示す図である。同図に示す例では、類似情報リストＤＢ１２４は、画像ＩＤと、類似画像ＩＤと、類似度とを対応づけて格納している。このように構成しても、１つの画像に対して複数の類似情報を格納することができる。
【００２５】
なお、この場合は、同一の画像ＩＤに対応づけられている類似画像ＩＤと類似度との組を少なくとも１つ含む情報が、本実施の形態における類似情報リストに相当する。例えば、図５に示す例では、画像ＩＤ＝１に対応づけられた類似情報リストは、類似画像ＩＤおよび類似度がそれぞれ２と０．１０との組、および、１０と０．１１との組を含む情報である。
【００２６】
類似情報リストＤＢ１２４に事前に類似情報を登録しておくことにより、検索時に特徴量の類似度を算出して類似情報を検索する必要がなくなり、検索処理の高速化を実現することが可能となる。
【００２７】
特徴量インデックス１２５は、特徴量ＤＢ１２３に含まれる特徴量を分類する空間インデックスである。特徴量の分類は、特徴量のベクトル空間（特徴量空間）を分割することによって行われる。例えば、図６は、ＶＰ−ｔｒｅｅによる特徴量空間の分割例を示す図である。
【００２８】
図６では、特徴量空間３００を２次元で表現している（なお、実際には、多次元となる）。同図において、各点は特徴量を示す。円弧は、特徴量空間３００が分割される境界線を示す。特徴量空間３００の分割は、特徴量の数が２分されるように行われる。例えば、円弧Ａ１によって、特徴量空間３００が二つの部分空間に二分されている。また、円弧Ａ１によって分割された一方の部分空間は、円弧Ａ２によって二分されている。斯かる分割が繰り返されることにより、図６に示されるような部分空間が形成される。なお、特徴量空間３００において、二つの特徴量の類似度は、当該二つの特徴量の距離に相当する。
【００２９】
図６に示される各部分空間及び特徴量の関係は、木構造（２分木）によって表現することができる。この木構造を表現する情報が特徴量インデックス１２５に相当する。
【００３０】
図７は、特徴量インデックスの構成例を示す図である。同図において、ノードＮｎ（ｎは正の整数）は特徴量空間を示し、ノードＥｎ（ｎは正の整数）は、特徴量を示す。例えば、ノードＮ１が図６における特徴量空間３００であるとすれば、ノードＮ２及びＮ３は、円弧Ａ１によって分割される部分空間を示す。また、ノードＮ４及びＮ５は、円弧Ａ２によって分割される部分空間を示す。但し、図７は、図６に完全には対応していない。
【００３１】
斯かる木構造において部分空間に対応するノードの中で、末端のノードは最小単位の部分空間となる。すなわち、最小単位の部分空間とは、一つの部分空間のみを含む部分空間をいう。図示されるように、特徴量を示すノードＥｎは、最小単位の部分空間のノードに属する。なお、以下において、単に「部分空間」というとき、最小単位の部分空間を意味することとする。
【００３２】
このような情報によって構成される特徴量インデックス１２５によれば、木構造をたどることにより、或る特徴量が属する部分空間を探索する際の計算量を減少させることができる。これは、一般的な二分木探索と同じ原理である。
【００３３】
入出力制御部１０１は、クライアントＰＣを介して利用者により指示された画像の登録・検索の入力処理、および、検索結果などをクライアントＰＣに出力する処理の制御を行う。
【００３４】
特徴量抽出部１０２は、画像データよりその特徴量を抽出する。特徴量を抽出する方法としては、色のヒストグラムを特徴量として抽出する特許文献１の方法などの、従来から用いられているあらゆる方法を適用することができる。なお、元となる情報をそのまま特徴量として扱う場合、特徴量抽出部１０２は不要である。
【００３５】
登録部１０３は、画像データの登録要求に応じ、画像データ記憶部１２１、メタデータＤＢ１２２、特徴量ＤＢ１２３、類似度情報リストＤＢ１２４、及び特徴量インデックス１２５に対するデータの登録処理を実行する。
【００３６】
削除部１０４は、画像データの削除要求に応じ、画像データ記憶部１２１、メタデータＤＢ１２２、特徴量ＤＢ１２３、類似情報リストＤＢ１２４、及び特徴量インデックス１２５よりデータを削除する処理を実行する。
【００３７】
類似度算出部１０６は、特徴量抽出部１０２が抽出した登録する情報の特徴量と、特徴量ＤＢに登録されている既存の情報の特徴量とを比較し、両者の類似する度合いを示す類似度を算出する。
【００３８】
例えば、類似度算出部１０６は、比較する特徴量のベクトルデータを｛a1,a2,…,an｝および｛b1,b2,…,bn｝とすると、以下の（１）式により類似度Ｓを算出する。
【００３９】
Ｓ＝Σ|ai−bi|  ・・・（１）
上記の類似度Ｓは、特徴量のベクトルデータの各成分の差の絶対値の和により算出されるため、類似度Ｓが小さいほど両者は類似していることを意味する。
【００４０】
ベクトルデータの各要素は、一般に浮動小数点の形式で表現されている。また、画像データの特徴量としてのベクトルデータは、一般に１００次元〜２００次元のデータであり、データサイズとしては、１．５ｋバイト〜２．０ｋバイトとなる。したがって、（１）式で表される類似度算出処理は、高負荷のかかる演算処理となる。
【００４１】
インデックス生成部１０７は、画像データの登録時に、当該画像データの特徴量に基づいて、特徴量インデックス１２５を更新する。
【００４２】
検索部１０５は、主に、特徴量インデックス１２５及び類似情報リストＤＢ１２４を用いて検索の種（検索条件）とされた画像データの特徴量に類似する特徴量を検索する。また、検索部１０５は、必要に応じ、検索された特徴量に係る画像データに関するデータを画像データ記憶部１２１及びメタデータＤＢ１２２等より検索する。
【００４３】
以下、情報管理装置１００の処理手順について説明する。最初に、類似画像の検索処理について説明する。当該検索処理については、まず、図８を用いて概念的に説明する。
【００４４】
図８は、類似画像の検索処理を概念的に説明するための図である。図８において、４００によって示される矩形は、特徴量インデックス１２５における特徴量空間を２次元空間上に表現したものである。なお、図８では、図６と異なり部分空間が直線によって分割されているが、これは、便宜的なものである。図８において、点Ｓは、検索条件として与えられる（検索の種となる）画像データ（以下、「種画像」という。）の特徴量（以下、「特徴量Ｓ」という。）を示す。特徴量Ｓ以外の点は、既に、特徴量インデックス１２５において部分空間に分類されている特徴量を示す。点Ｓを中心とした実線の円ｃ１は、検索条件として与えられる類似度（以下「類似条件」という。）によって形成される検索円である。すなわち、図８では、検索円ｃ１内に含まれる特徴量を探し出す（検索する）例を説明する。なお、例えば、特徴量空間４００の幅を「１．０」、高さを「１．０」とした場合、類似条件として指定されうる値は、０より大きく１．０より小さい値である。例えば、「０．２」が類似条件として与えられた場合、検索円ｃ１は、０．２を半径とする円となる。
【００４５】
検索円ｃ１内に含まれる特徴量を検索する場合、情報管理装置１００は、まず、特徴量Ｓが属する部分空間４０１を特徴量インデックス１２５を用いて特定する。続いて、情報管理装置１００は、部分空間４０１に含まれる特徴量４０１ａ、４０１ｂ、及び４０１ｃ（以下、総称する場合「特徴量４０１」という。）のそれぞれについて特徴量Ｓとの類似度（距離）を算出し、検索円ｃ１内に存在するか否かを判定する。つまり、算出された類似度と、検索条件として与えられる類似度とを用いて、特徴量４０１のそれぞれについて検索円ｃ１内に存在するか否かを判定する。情報管理装置１００は、検索円ｃ１内に存在する特徴量（図中では、特徴量４０１ｂ）に対応する画像ＩＤ及び類似度を検索結果として保持する。
【００４６】
ところで、特徴量Ｓが属する部分空間４０１は、特徴量インデックス１２５に基づいて高速に特定されうるが、検索円ｃ１の範囲は、部分空間４０１以外の部分空間に跨るものである。したがって、部分空間４０１以外の部分空間にも、検索円ｃ１内に含まれる（すなわち、検索条件に合致する）特徴量は存在しうる。よって、この時点における検索結果には、検索漏れが存在する可能性が高い。そこで、情報管理装置１００は、次のような処理を行うことにより、出来るだけ少ない計算量によって、他の部分空間に属する特徴量の中から検索円ｃ１に含まれる特徴量を検索する。
【００４７】
まず、情報管理装置１００は、特徴量４０１のそれぞれについて、類似情報リストＤＢ１２４の類似情報リストに含まれている特徴量を取得する。この処理は、図中において特徴量４０１のそれぞれを中心とした破線の円に含まれる特徴量を取得することに相当する。したがって、特徴量４０２ａ、４０２ｂ、４０２ｃ、４０２ｄ、及び４０２ｅ（以下、総称する場合「特徴量４０２」という。）が取得される。なお、情報管理装置１００は、類似情報リストに含まれている全ての特徴量を取得せずに、関連づけられている類似度が、検索条件として与えられた類似度（本実施の形態においては０．２）以下の特徴量のみを取得する構成としても良い。かかる構成を採用することにより、処理速度の高速化を量ることができる。
【００４８】
情報管理装置１００は、特徴量４０２のそれぞれについて特徴量Ｓとの類似度を算出し、検索円ｃ１内に存在するか否かを判定する。情報管理装置１００は、検索円ｃ１内に存在する特徴量（図中では、特徴量４０２ｂ）に対応する画像ＩＤ及び類似度を検索結果として保持する。
【００４９】
続いて、情報管理装置１００は、特徴量４０２のそれぞれについても類似情報リストＤＢ１２４の類似情報リストに含まれている特徴量を取得する。したがって、図中において、特徴量４０２のそれぞれを中心とした一点鎖線の円に含まれる特徴量４０３ａ、４０３ｂ、４０３ｃ、４０３ｄ、４０３ｅ、及び４０３ｆ（以下、総称する場合「特徴量４０３」という。）が取得される。情報管理装置１００は、特徴量４０３のそれぞれについて特徴量Ｓとの類似度を算出し、検索円ｃ１内に存在するか否かを判定する。情報管理装置１００は、検索円ｃ１内に存在する特徴量（図中では、特徴量４０３ｃ）に対応する画像ＩＤ及び類似度を検索結果として保持する。
【００５０】
続いて、情報管理装置１００は、特徴量４０３のそれぞれについても類似情報リストＤＢ１２４の類似情報リストに含まれている特徴量を取得する。したがって、図中において、特徴量４０３のそれぞれを中心とした点線の円に含まれる特徴量４０４ａ、４０４ｂ、４０４ｃ、及び４０４ｄ（以下、総称する場合「特徴量４０４」という。）が取得される。情報管理装置１００は、特徴量４０４のそれぞれについて特徴量Ｓとの類似度を算出し、検索円ｃ１内に存在するか否かを判定する。ここで、特徴量４０４の中で、検索円ｃ１内に存在する特徴量は存在しないため、情報管理装置１００は、類似画像の検索処理を終了させる。したがって、図８の例では、特徴量４０１ｂ、特徴量４０２ｂ、及び特徴量４０３ｃに対応する画像ＩＤ及び類似度が検索結果として出力される。
【００５１】
このように、類似情報リストを用いて再帰的に取得される特徴量を類似の判定対象とすることにより、部分領域４０１以外の部分領域であって、部分領域に近接する部分領域に含まれる特徴量についても類似の判定対象とすることができる。したがって、検索処理を高速化させつつ検索漏れの数を低減させることができる。
【００５２】
以下、フローチャートを用いて処理内容について具体的に説明する。図９は、類似画像の検索処理を説明するためのフローチャートである。
【００５３】
ステップＳ１０１において、入出力制御部１０１は、種画像と類似条件とをクライアントＰＣより受信する。種画像と類似条件とは、例えば、クライアントＰＣにおいてユーザＩ／Ｆ２０１を介して利用者によって指定又は入力される。なお、ここで指定される種画像は、情報管理装置１００に登録されていないものであってもよい。また、類似条件は、クライアントＰＣより受信されるのではなく、情報管理装置１００のＨＤＤ１２０内に予め設定されていてもよい。
【００５４】
続いて、特徴量抽出部１０６は、種画像の特徴量を種画像より抽出する（種画像の特徴量を種画像に基づいて生成する）（Ｓ１０２）。続いて、検索部１０５は、特徴量インデックス１２５において特徴量Ｓが分類される（属する）部分空間を特徴量インデックス１２５を用いて特定する（特徴量Ｓがいずれの部分空間に属するのかを判定する）（Ｓ１０３）。
【００５５】
続いて、検索部１０５は、特定された部分空間に関連付けられている画像ＩＤを特徴量インデックス１２５より取得し、当該画像ＩＤに対応付けられている特徴量を特徴量ＤＢ１２３より取得し、取得された特徴量及びその画像ＩＤによって対象特徴量集合（特徴量Ｓとの類似の判定対象とされる特徴量及び画像ＩＤの集合）を初期化する（Ｓ１０４）。
【００５６】
続いて、類似度算出部１０６は、対象特徴量集合に含まれている全ての特徴量について、特徴量Ｓとの類似度（距離）を算出する（Ｓ１０５）。続いて検索部１０５は、算出された類似度が、類似条件に指定された類似度以下であるか否かを判定する（Ｓ１０６）。類似条件を満たす特徴量が存在する場合（Ｓ１０６でＹｅｓ）、検索部１０５は、類似条件を満たす特徴量に係る画像ＩＤ及び類似度を検索結果に追加する（Ｓ１０７）。
【００５７】
続いて、検索部１０５は、対象特徴量集合を探索済特徴量集合として退避する（Ｓ１０８）。探索済特徴量集合は、特徴量Ｓとの類似度の判定が既に行われた特徴量及び画像ＩＤの集合である。続いて、検索部１０５は、探索済特徴量集合に含まれる各特徴量に対応する類似情報リストを各特徴量の画像ＩＤに基づいて類似情報リストＤＢ１２４より取得し、取得された類似情報リストに含まれている類似画像ＩＤ（画像ＩＤ）に対応する特徴量を特徴量ＤＢ１２３より取得し、取得された特徴量とその画像ＩＤとによって対象特徴量集合を更新する（Ｓ１０９）。
【００５８】
続いて、検索部１０５は、対象特徴量集合における重複を除去する（Ｓ１１０）。すなわち、複数の類似情報リストに含まれている特徴量が存在する場合、対象特徴量集合には、同一の特徴量が二つ以上存在するからである。当該重複が除去されることにより、同一の特徴量について、重複して特徴量Ｓとの類似度の算出が行われるといった無駄の発生が回避される。
【００５９】
続いて、検索部１０５は、対象特徴量集合から探索済特徴量集合に含まれる特徴量及びその画像ＩＤを除去する（Ｓ１１１）。これによって、既に特徴量Ｓとの類似度の算出が行われた特徴量について、再度類似度の算出が行われるといった無駄の発生が回避される。
【００６０】
続いて、新たな対象特徴量集合に基づいて、ステップＳ１０５以降の処理が実行される。すなわち、類似情報リストに含まれている特徴量について、再帰的に類似度の算出及び、類似条件を満たすか否かの判定等が行われる。
【００６１】
再帰的に処理が行われる過程において、対象特徴量集合内に含まれる特徴量の中で、類似条件を満たす特徴量が存在しない状況が発生した場合（Ｓ１０６でＮｏ）、検索部１０５は、ループ処理（再帰処理）を抜ける。
【００６２】
但し、ループ処理の終了条件はこれだけに限定されない。例えば、ステップＳ１０７〜Ｓ１１１を一回だけ行った後、ループを抜けるようにしてもよい。この場合、特徴量Ｓと同じ部分空間に属する特徴量と、その特徴量に類似する特徴量とが類似の判定対象となる。また、単純に繰り返し（再帰）の回数が予め設定された値に到達したときにループ処理を抜けるようにしてもよい。この場合、検索結果に漏れが生じる可能性が高くなるが高速に検索することが可能である。また、類似条件（検索円）内の特徴量が存在しない状況が、予め指定された回数に到達したとき、又は所定回数連続したときにループ処理を抜けるようにしてもよい。そうすることにより、検索漏れの可能性を低減させることができるとともに、検索に対して一定の高速性を保つことができる。
【００６３】
続いて、検索部１０５は、検索結果に含まれている画像ＩＤに対応する画像ファイル名をメタデータＤＢ１２２より取得する（Ｓ１１２）。続いて、検索部１０５は、取得した画像ファイル名に対応する画像データを画像データ記憶部１２１より取得し、取得された画像データを類似度に基づいてソートする（Ｓ１１３）。なお、外部システムに保存されている画像データの場合は、外部システムから画像ファイル名に対応する画像データを取得する。続いて、入出力制御部１０１は、取得された画像データをクライアントＰＣのユーザＩ／Ｆ２０１に送信する（Ｓ１１４）。クライアントＰＣのユーザＩ／Ｆ２０１は、受信した画像データを表示装置に表示させる。なお、ステップＳ１１４において、画像データの代わりにメタデータ（画像ファイル名）の一覧を送信するようにしてもよい。この場合、メタデータの一覧がクライアントＰＣにおいて表示される。当該一覧において選択された画像データを入出力制御部１０１がクライアントＰＣに送信するように送信するようにしてもよい。
【００６４】
上述したように、本実施の形態における情報管理装置１００によれば、空間インデックスにおいて種画像が属する部分空間を特定し、その部分空間に属する特徴量及びその特徴量に類似する特徴量が種画像との類似度の算出対象とされる。したがって、特徴量ＤＢ１２３に登録されている全ての特徴量を類似度の算出対象とする場合に比べて、著しく計算量を減少させることができる。計算量の減少の程度は、蓄積されている特徴量及び特徴量の次元数に応じて異なるが、画像データの特徴量が一般的に１００次元から２００次元となることに鑑みれば、その程度は著しい。したがって、情報管理装置１００によれば、未登録の種画像の類似画像検索処理を高速化させることができる。
【００６５】
また、類似情報リストに基づいて再帰的に取得される特徴量についても、類似度が算出され、類似条件を満たしているか否かが判定される。したがって、類似条件（検索円）が複数の部分領域に跨る場合であっても、検索漏れの数を低減させることができる。
【００６６】
なお、空間インデックス（特徴量インデックス１２５）の形式は、所定のものに限定されない。上記において示したＶＰ−ｔｒｅｅ以外に、Ｒ−ｔｒｅｅに基づくもの、Ｍ−ｔｒｅｅに基づくもの等、公知における各種の空間インデックスを適用することができる。
【００６７】
すなわち、いずれかの形式の空間インデックスにおいて、種画像の特徴量が分類される部分空間が特定されれば、その後はその部分空間に含まれる特徴量及びその特徴量の類似情報リストに含まれる特徴量について類似度の算出を行い、当該類似度が類似条件を満たすか否かを判定等すればよい。
【００６８】
但し、Ｍ−ｔｒｅｅによる場合、部分空間に重複が生じるような空間インデックスが形成される。したがって、この場合、種画像の特徴量が分類される部分空間が複数存在しうるが、複数の部分空間について、図９において説明した処理を実行すればよい。なお、特徴量のインデックス方式については、特開２０００−１１２９７３等に詳しい。
【００６９】
次に、画像情報の登録時の処理手順について説明する。図１０は、画像情報の登録処理を説明するためのフローチャートである。
【００７０】
まず、入出力制御部１０１は、クライアントＰＣより登録画像ファイルとそのメタデータ（ファイル名等）を受信する（Ｓ２０１）。登録画像ファイルは、例えば、クライアントＰＣにおいてユーザＩ／Ｆ２０１を介して利用者によって指定又は選択される。続いて、登録部１０３は、登録画像ファイルを画像データ記憶部１２１に保存すると共に、登録画像ファイルの画像ＩＤと画像ファイル名とを対応づけてメタデータＤＢ１２２に登録する（Ｓ２０２）。
【００７１】
続いて、特徴量抽出部１０２は、登録画像ファイルより画像データ（登録画像）を読込み（Ｓ２０３）、登録画像の特徴量を抽出（生成）する（Ｓ２０４）。抽出した特徴量は、上述のようにベクトルデータとして出力される。続いて、インデックス生成部１０７は、登録画像ファイルの画像ＩＤを、登録画像の特徴量に基づいて特徴量インデックス１２５に登録する（Ｓ２０５）。
【００７２】
続いて、情報管理装置１００は、登録画像について類似画像検索処理を実行する（Ｓ２０６）。当該検索処理は、図９において説明した通りである。但し、ここでは、登録画像が種画像とされ、また、予めＨＤＤ１２０内に設定されている類似度（例えば、０．３等）が類似条件とされる。
【００７３】
続いて、登録部１０３は、類似画像検索処理で出力された画像ＩＤ（類似画像ＩＤ）と類似度との集合を類似情報リストとして類似情報リストＤＢ１２４に登録する（Ｓ２０７）。続いて、情報管理装置１００は、既に登録されている画像ファイルに対する類似情報リストの更新処理を実行する（Ｓ２０８）。類似情報リストの更新処理の詳細については後述する。
【００７４】
続いて、登録部１０３は、ステップＳ２０４で特徴量抽出部１０２が抽出した特徴量を特徴量ＤＢ１２３に登録し（Ｓ２０９）、登録処理を終了する。
【００７５】
このように、本実施の形態では、類似情報リストの作成においても全ての特徴量との比較を行わず、図９において説明した類似画像検索処理によって類似画像を検索する。したがって、登録処理における処理負荷を軽減することが出来ると共に、類似情報リストの作成を伴う登録処理を高速化することができる。
【００７６】
なお、上述の例では画像情報の登録と同時に類似画像を検索及び類似情報リストの登録を行っているが、検索処理を実行する前であれば、図１０の処理が完了した後に類似画像の検索及び類似情報リスト登録処理を実行してもよい。
【００７７】
次に、図１０のステップＳ２０８における類似情報リスト更新処理の詳細について説明する。新規に登録した画像情報と、それに対する類似情報（既存の情報）は互いに類似する情報である。従って、既存の情報についての類似情報リストに、新規に登録した画像情報を追加する必要がある。この処理を行うのが類似情報リスト更新処理である。
【００７８】
図１１は、類似情報リスト更新処理を説明するためのフローチャートである。
【００７９】
まず、検索部１０５は、登録画像の類似情報リストから類似画像ＩＤを取得する（Ｓ３０１）。続いて、検索部１０５は、取得した類似画像ＩＤに対応する類似情報リストを類似情報リストＤＢ１２４から取得する（Ｓ３０２）。続いて、登録部１０３は、取得した類似情報リストに、登録する画像の画像ＩＤと、ステップＳ２０６において出力された類似度とを対応づけた類似情報を追加する（Ｓ３０３）。
【００８０】
続いて、検索部１０５は、登録画像の類似情報リスト内の全てのデータを処理したか否かを判断し（Ｓ３０４）、全てのデータを処理していない場合は（Ｓ３０４でＮｏ）、次の類似画像ＩＤを取得して処理を繰り返す（Ｓ３０１）。
【００８１】
全てのデータを処理した場合（Ｓ３０４でＹｅｓ）、類似情報リスト更新処理を終了する。
【００８２】
次に、情報管理装置１００による情報の削除処理について説明する。図１２は、削除処理を説明するためのフローチャートである。
【００８３】
まず、入出力制御部１０１は、削除の前提として、メタデータＤＢ１２２に登録されている画像ファイル名の一覧をクライアントＰＣのユーザＩ／Ｆ２０１に表示させ（Ｓ４０１）、利用者による削除する画像の選択を受付ける（Ｓ４０２）。
【００８４】
続いて、検索部１０５は、利用者により選択された画像の類似情報リストを類似情報リストＤＢ１２４から取得する（Ｓ４０３）。
【００８５】
続いて、検索部１０５は、類似情報リスト削除処理を実行する（Ｓ４０４）。類似情報リスト削除処理の詳細については後述する。
【００８６】
続いて、削除部１０４は、削除画像の画像ファイルを画像データ記憶部１２１より削除すると共にメタデータをメタデータＤＢ１２２から削除し（Ｓ４０５）、削除画像の特徴量を特徴量ＤＢ１２３から削除し（Ｓ４０６）、削除画像の類似情報リストを類似情報リストＤＢ１２４から削除する（Ｓ４０７）。
【００８７】
続いて、削除部１０４は、特徴量インデックス１２５より、削除画像の画像ＩＤを削除し（Ｓ４０８）、削除処理を終了する。
【００８８】
次に、ステップＳ４０４における類似情報リスト削除処理の詳細について説明する。図１３は、類似情報リスト削除処理を説明するためのフローチャートである。
【００８９】
まず、検索部１０５は、類似情報リストから類似画像ＩＤを取得する（Ｓ５０１）。続いて、検索部１０５は、取得した類似画像ＩＤに対応する類似情報リストを類似情報リストＤＢ１２４から取得する（Ｓ５０２）。続いて、削除部１０４は、取得した類似情報リストから、削除画像ＩＤと一致する類似情報ＩＤを有する類似情報を削除する（Ｓ５０３）。続いて、検索部１０５は、削除画像の類似情報リスト内の全てのデータを処理したか否かを判断し（Ｓ５０４）、全てのデータを処理していない場合は（Ｓ５０４でＮｏ）、次の類似画像ＩＤを取得して処理を繰り返す（Ｓ５０１）。
【００９０】
全てのデータを処理した場合（Ｓ５０４でＹｅｓ）、類似情報リスト削除処理を終了する。
【００９１】
削除処理において、類似情報リスト１２４及び特徴量インデックス１２５より削除画像に関する情報が削除されることにより、後の類似画像検索処理において画像データ記憶部１２１に画像ファイルが存在しない画像データが検索されるといった不整合の発生を防止することができる。
【００９２】
なお、本実施の形態において、類似情報リストＤＢ１２４は、特徴量関連付け手段の一例であり、特徴量インデックス１２５は、空間インデックス管理手段の一例であり、検索部１０５によるステップＳ１０３は、部分空間判定手段の一例であり、検索部１０５によるステップＳ１０５〜Ｓ１１１は、類似判定手段の一例である。
【００９３】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【図面の簡単な説明】
【００９４】
【図１】本発明の実施の形態における情報管理装置の機能構成例を示す図である。
【図２】メタデータＤＢのデータ構造の一例を示す図である。
【図３】特徴量ＤＢのデータ構造の一例を示す図である。
【図４】類似情報リストＤＢのデータ構造の一例を示す図である。
【図５】類似情報リストＤＢのデータ構造の別の一例を示す図である。
【図６】ＶＰ−ｔｒｅｅによる特徴量空間の分割例を示す図である。
【図７】特徴量インデックスの構成例を示す図である
【図８】類似画像の検索処理を概念的に説明するための図である。
【図９】類似画像の検索処理を説明するためのフローチャートである。
【図１０】画像情報の登録処理を説明するためのフローチャートである。
【図１１】類似情報リスト更新処理を説明するためのフローチャートである。
【図１２】削除処理を説明するためのフローチャートである。
【図１３】類似情報リスト削除処理を説明するためのフローチャートである。
【符号の説明】
【００９５】
１００      情報管理装置
１０１      入出力制御部
１０２      特徴量抽出部
１０３      登録部
１０４      削除部
１０５      検索部
１０６      類似度算出部
１０７      インデックス生成部
１２０      ＨＤＤ
１２１      画像データ記憶部
１２２      メタデータＤＢ
１２３      特徴量ＤＢ
１２４      類似情報リストＤＢ
１２５      特徴量インデックス
２００ａ、２００ｂ  クライアントＰＣ
２０１      ユーザＩ／Ｆ
【図１】
0005151394.tif 000002
【図２】
0005151394.tif 000003
【図３】
0005151394.tif 000004
【図４】
0005151394.tif 000005
【図５】
0005151394.tif 000006
【図６】
0005151394.tif 000007
【図７】
0005151394.tif 000008
【図８】
0005151394.tif 000009
【図９】
0005151394.tif 000010
【図１０】
0005151394.tif 000011
【図１１】
0005151394.tif 000012
【図１２】
0005151394.tif 000013
【図１３】
0005151394.tif 000014