(57)【要約】  類似画像検索装置１は、複数の画像データが記憶された画像データベース２１と、画像データを読み出して、画像データのそれぞれに適合値を付与するとともに、適合値に基づいて、複数の画像データを複数のクラスタに分類するクラスタ分類部１１と、クエリ画像データに適合値を付与するとともに、複数のクラスタから、各クラスタを用いた際に凸射影法で生じる誤差が最小になるように、クエリ画像データの属するクラスタを選択する最適クラスタ抽出部１２と、最適クラスタによって選択されたクラスタに属する画像データの中から、適合値の距離が小さな画像データを、類似画像として出力する類似画像抽出部１３とを備える。
2009060722.tif 000002
【特許請求の範囲】
【請求項１】
クエリ画像に類似する画像を検索する類似画像検索装置であって、
複数の画像データと、前記画像データに関連するキーワードがそれぞれ関連づけられて記憶された画像データベースと、
前記画像データを読み出して、前記画像データのそれぞれに、前記キーワードの適合を示す指標である適合値を付与するとともに、前記適合値に基づいて、前記複数の画像データを複数のクラスタに分類するクラスタ分類部と、
クエリ画像データに前記適合値を付与するとともに、前記複数のクラスタから、前記各クラスタを用いた際に凸射影法で生じる誤差が最小になるように、前記クエリ画像データの属するクラスタを選択する最適クラスタ抽出部と、
前記最適クラスタによって選択されたクラスタに属する前記画像データの中から、前記適合値の距離が小さな画像データを、類似画像として出力する類似画像抽出部
とを備えることを特徴とする類似画像検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリ画像に類似する画像を検索する類似画像検索装置に関する。
【背景技術】
【０００２】
近年のブロードバンド通信の普及や記録媒体の大容量化、さらにディジタルカメラやイメージスキャナ等の普及に伴い、個人のユーザが扱う画像の量が増加している。これに伴って、効果的な画像検索手法の必要性が向上している。【０００３】
従来の画像検索手法として、画像に付与されたキーワード等の意味的特徴に基づく検索法が挙げられる。その他、データベース管理および情報検索の分野において多くの手法が提案されている。【０００４】
例えば、画像にキーワードを付与して、ユーザがキーワードを入力することにより、所望の画像を検索する方法がある。しかし、この方法では、画像に対してユーザがキーワード等を付与する必要があった。従って、その正確さによって検索性能が大きく変化するという問題が存在した。【０００５】
この問題を解決するために、画像のキーワードを自動的に付与する技術が期待されている。この方法の一つとして、画像データを取得したＷｅｂデータを解析して、キーワードを取得する方法がある（例えば、特許文献１参照。）。この特許文献１に記載の方法は、Ｗｅｂから取得した画像にキーワードを付与する場合に限られ、汎用的なものではない。【０００６】
また、近年クエリ画像（検索要求画像）としてサンプル画像を入力し、それに類似する画像を提示する手法(Content-Based Image Retrieval: CBIR) が種々提案されている（例えば、非特許文献１参照。）。非特許文献１等に記載の手法は、画像ごとに、色、テクスチャ、形状等の低いレベルの画像特徴量を算出する。そこで、非特許文献１等に記載の手法は、画像ごとの画像特徴量間で算出される距離を、画像間の距離とみなすことで、類似画像の検索を行う。すなわち、非特許文献１等に記載の手法は、ユーザが入力するクエリ画像と、画像特徴量が最も類似する画像を、類似画像として提示する。
【特許文献１】特開２００６−２７７１６９号公報
【非特許文献１】A. A. Goodrum, “Image information retrieval: An overview of currtent research、” Inf. Sci., vol.3, pp.63−66, 2000.
【発明の開示】
【０００７】
しかしながら、単純に画像特徴量間において類似度を求める方法は、低いレベルの画像特徴量と、実際の意味的特徴との相関を考慮していないため、検索精度に限界が存在した。
【０００８】
また、従来の方法は、画像特徴量より限られた数のキーワードを画像に対応付けるのみである。従って従来の方法は、明確な一つの意味を持たない画像や、被写体が一種類ではない画像において精度良く検索を行うことが困難である。
【０００９】
従って本発明の目的は、画像の意味内容を考慮して、クエリ画像に類似する画像を高精度に検出する類似画像検索装置を提供することである。
【００１０】
上記課題を解決するために、本発明の第１の特徴は、クエリ画像に類似する画像を検索する類似画像検索装置に関する。即ち、本発明の第１の特徴に係る類似画像検索装置は、複数の画像データと、画像データに関連するキーワードがそれぞれ関連づけられて記憶された画像データベースと、画像データを読み出して、画像データのそれぞれに、キーワードの適合を示す指標である適合値を付与するとともに、適合値に基づいて、複数の画像データを複数のクラスタに分類するクラスタ分類部と、クエリ画像データに適合値を付与するとともに、複数のクラスタから、各クラスタを用いた際に凸射影法で生じる誤差が最小になるように、クエリ画像データの属するクラスタを選択する最適クラスタ抽出部と、最適クラスタによって選択されたクラスタに属する画像データの中から、適合値の距離が小さな画像データを、類似画像として出力する類似画像抽出部とを備える。
【００１１】
本発明によれば、画像の意味内容を考慮して、クエリ画像に類似する画像を高精度に検出する類似画像検索装置を提供することができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、本発明の最良の実施の形態に係る類似画像検索装置の機能ブロック図である。
【図２】図２は、本発明の最良の実施の形態に係る類似画像検索装置のハードウェア構成図である。
【図３】図３は、本発明の最良の実施の形態に係る類似画像検索装置において用いられる凸射影法における反復を説明する図である。
【図４】図４は、本発明の最良の実施の形態に係る類似画像検索装置による類似画像検索処理の結果の一例を説明する図である。
【発明を実施するための最良の形態】
【００１３】
次に、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。【００１４】
（最良の実施の形態）
本発明の最良の実施の形態に係る類似画像検索装置１は、クエリ画像に類似する画像を検索する。【００１５】
本発明の最良の実施の形態に係る類似画像検索装置１は、凸射影法を用いることで、各キーワードがクエリ画像にどの程度適合するかを表す指標(以降、適合値と呼ぶ) を推定し、その結果に基づいて類似画像を検索する。本発明の最良の実施の形態に係る類似画像検索装置１は、キーワードが付与されているデータベース中の画像から、以下の２つの新規要素を含む凸射影法を用いることで、クエリ画像に対して適合値の推定を可能とする。第１に、本発明の最良の実施の形態に係る類似画像検索装置１は、データベース中の画像を、適合値に基づいて分類し、各クラスタ毎に算出される画像特徴量および適合値の非線形固有空間を、凸射影法の拘束条件に導入する。このとき用いられる非線形固有空間は、画像特徴量と適合値との相関を表現可能である。従って、類似画像検索装置１は、クエリ画像の画像特徴量のみから全てのキーワードの適合値を算出することが可能となる。第２に、本発明の最良の実施の形態に係る類似画像検索装置１は、凸射影法の収束誤差に注目することで、クエリ画像の属するクラスタを選択する。これにより、類似画像検索装置１は、クエリ画像と類似した画像を含むクラスタの適応的選択が可能となる。従って、類似画像検索装置１は、最適なクラスタによりクエリ画像の適合値を算出することが可能となる。【００１６】
以上のようにして、本発明の最良の実施の形態に係る類似画像検索装置１は、クエリ画像に対して、各キーワードの適合値を推定することが可能となる。類似画像検索装置１は、データベース中の画像との適合値の距離を求めることで、高精度に類似画像の検索を行うことが可能となる。【００１７】
（類似画像検索装置のハードウェア構成）
図２に示すように、本発明の最良の実施の形態に係る類似画像検索装置１において、中央処理制御装置１０１、ＲＯＭ（Read Only Memory）１０２、ＲＡＭ（Random Access Memory）１０３及び入出力インタフェース１０９が、バス１１０を介して接続されている。入出力インタフェース１０９には、入力装置１０４、表示装置１０５、通信制御装置１０６、記憶装置１０７及びリムーバブルディスク１０８が接続されている。【００１８】
中央処理制御装置１０１は、入力装置１０４からの入力信号に基づいてＲＯＭ１０２から類似画像検索装置１を起動するためのブートプログラムを読み出して実行し、更に記憶装置１０７に記憶されたオペレーティングシステムを読み出す。更に中央処理制御装置１０１は、入力装置１０４や通信制御装置１０６などの入力信号に基づいて、各種装置の制御を行ったり、ＲＡＭ１０３や記憶装置１０７などに記憶されたプログラム及びデータを読み出してＲＡＭ１０３にロードするとともに、ＲＡＭ１０３から読み出されたプログラムのコマンドに基づいて、データの計算又は加工など、後述する一連の処理を実現する処理装置である。【００１９】
入力装置１０４は、操作者が各種の操作を入力するキーボード、マウスなどの入力デバイスにより構成されており、操作者の操作に基づいて入力信号を作成し、入出力インタフェース１０９及びバス１１０を介して中央処理制御装置１０１に送信される。表示装置１０５は、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどであり、中央処理制御装置１０１からバス１１０及び入出力インタフェース１０９を介して表示装置１０５において表示させる出力信号を受信し、例えば中央処理制御装置１０１の処理結果などを表示する装置である。通信制御装置１０６は、ＬＡＮカードやモデムなどの装置であり、類似画像検索装置１をインターネットやＬＡＮなどの通信ネットワークに接続する装置である。通信制御装置１０６を介して通信ネットワークと送受信したデータは入力信号又は出力信号として、入出力インタフェース１０９及びバス１１０を介して中央処理制御装置１０１に送受信される。【００２０】
記憶装置１０７は半導体記憶装置や磁気ディスク装置であって、中央処理制御装置１０１で実行されるプログラムやデータが記憶されている。リムーバブルディスク１０８は、光ディスクやフレキシブルディスクのことであり、ディスクドライブによって読み書きされた信号は、入出力インタフェース１０９及びバス１１０を介して中央処理制御装置１０１に送受信される。【００２１】
本発明の最良の実施の形態に係る類似画像検索装置１の記憶装置１０７には、類似画像検索プログラムが記憶されるとともに、画像データベース２１およびクエリ画像データ２２が記憶される。又、類似画像検索プログラムが類似画像検索装置１の中央処理制御装置１０１に読み込まれ実行されることによって、クラスタ分類部１１、最適クラスタ抽出部１２および類似画像抽出部１３が類似画像検索装置１に実装される。【００２２】
（類似画像検索装置の機能ブロック）
図１に示すように、本発明の最良の実施の形態に係る類似画像検索装置１は、画像データベース２１、クラスタ分類部１１、最適クラスタ抽出部１２および類似画像抽出部１３を備えている。【００２３】
画像データベース２１には、複数の画像データと、画像データに関連するキーワードがそれぞれ関連づけられて記憶される。【００２４】
クラスタ分類部１１は、画像データベース２１から、画像データを読み出して、画像データのそれぞれに、キーワードの適合を示す指標である適合値を付与する。さらにクラスタ分類部１１は、適合値に基づいて、複数の画像データを複数のクラスタに分類する。クラスタ分類部１１は、図１に示すように、画像データのそれぞれに付与された適合値に基づいて、各画像データを第１クラスタＣ１、第２クラスタＣ２・・・第ＫクラスタＣＫに分類する。【００２５】
最適クラスタ抽出部１２は、クエリ画像データ２２に適合値を付与するとともに、複数のクラスタから、各クラスタを用いた際に凸射影法で生じる誤差が最小になるように、クエリ画像データ２２の属するクラスタを選択する。図１に示すように、最適クラスタ抽出部１２は、クエリ画像データ２２の適合値２４を算出する。最適クラスタ抽出部１２は、クラスタ分類部１１によって生成された第１クラスタＣ１、第２クラスタＣ２・・・第ＫクラスタＣＫの各クラスタのうち、クエリ画像データ２２の適合値２４の属するクラスタを決定し、最適クラスタ２５として出力する。【００２６】
類似画像抽出部１３は、最適クラスタ抽出部１２によって選択されたクラスタに属する画像データの中から、適合値の距離が小さな画像データを、類似画像データ２３ａ、２３ｂ、２３ｃ・・・・として出力する。類似画像抽出部１３は、最適クラスタ２５に属する画像データを、クエリ画像データ２２に類似する画像データ２３ａ、２３ｂ、２３ｃ・・・・として出力する。【００２７】
（凸射影法）
ここで、本発明の最良の実施の形態で用いられる凸射影法を説明する。【００２８】
凸射影法は、Ｙｏｕｌａ、Ｗｅｂｂらによって非線形の画像復元法として用いられた。凸射影法は、原画像f ∈ H (H はヒルベルト空間を表す) に関する既知の特徴から、原画像を推定する手法である。今、原画像のn 種類の特徴をn 個の閉凸集合Ck (k = 1、 2、 ・ ・ ・ 、 n) で表したとき、それらの共通部分
【数１】
2009060722.tif 000003
は閉凸集合となり、原画像fを含む。
【数２】
2009060722.tif 000004
【００２９】
したがって、任意のf0より
【数３】
2009060722.tif 000005
に含まれる
【数４】
2009060722.tif 000006
を探索することは、原画像を近似した結果を得ることが可能とする。ただし、一般に
【数５】
2009060722.tif 000007
は非線形で構造が複雑であるため、容易に記述することはできない。【００３０】
したがって、そのような場合、
【数６】
2009060722.tif 000008
を満たす閉凸集合
【数７】
2009060722.tif 000009
への射影要素Pkを用いて、類似画像検索装置１は、
【数８】
2009060722.tif 000010
を算出する。【００３１】
具体的には、図３に示されるように
【数９】
2009060722.tif 000011
が繰り返し処理により
【数１０】
2009060722.tif 000012
に含まれる
【数１１】
2009060722.tif 000013
へ収束する性質を用いて、任意のf0から原画像を近似した結果が得られる。【００３２】
（凸射影法を用いた類似画像検索法の概要）
上述した凸射影法を用いることで、クエリ画像に対して各キーワードの適合値を算出し、その結果に基づいて類似画像を検索する方法の概要が説明される。本発明の最良の実施の形態に係る類似画像検索装置１は、データベース中の画像に対して、あらかじめキーワードの適合値に基づいた分類を行う。さらに、類似画像検索装置１は、得られる分類結果から以下の２つの新規要素を含む凸射影法を用いることで、クエリ画像に対し、全てのキーワードの適合値を推定する。【００３３】
(i)各クラスタ毎に算出される画像特徴量およびキーワードの適合値に関する非線形固有空間の、凸射影法の拘束条件への導入
(ii)凸射影法の収束誤差に注目した、クエリ画像が属するクラスタの適応的選択
(i)において用いられる非線形固有空間は、画像特徴量とキーワードの適合値との相関を表現可能である。したがって、これを用いることで、クエリ画像の画像特徴量のみから各キーワードの適合値の推定が期待できる。さらに、(ii) を用いることで、クエリ画像と類似した画像を含むクラスタが決定され、適合値の算出に用いるクラスタの適応的選択が可能となる。以上のようにして得られる適合値を用いることで、本発明の最良の実施の形態では、データベース中よりクエリ画像に類似する画像の検索が可能となる。【００３４】
（各クラスタの非線形固有空間の算出）
ここでは、画像データベース中に存在する画像データに対してキーワードの適合値に基づく分類を行い、得られる各クラスタ毎に非線形固有空間の算出を行う処理が詳述される。この処理は、図１のクラスタ分類部１１に対応する。【００３５】
ここで、画像データベース中に存在するＮ枚の画像をfi (i=1、 2、・・・ 、 N)とし、これらの画像に付与された全てのキーワードがＬ個であるとする。本発明の最良の実施の形態においては、類似画像検索装置１は、まず、各画像fiに対して各要素が１または０であるベクトル
【数１２】
2009060722.tif 000014
を算出する。このとき、
【数１３】
2009060722.tif 000015
は、画像ｆｉがl 番目のキーワードを含む場合に１、含まない場合に０となる。さらに、類似画像検索装置１が、得られる各ベクトル
【数１４】
2009060722.tif 000016
に対して、
【数１５】
2009060722.tif 000017
を算出することで、各要素に各キーワードの適合値を含むベクトルxiを算出する。本発明の最良の実施の形態では、以上のベクトルxi を各画像fiの意味的特徴を含む特徴ベクトルとみなし、類似画像検索装置１は、これを次式のＣ が最小となるように、Ｋ 個のクラスタに分類する。
【数１６】
2009060722.tif 000018
ただし、s(i、 j) は画像fi とfj が同一クラスタに属する場合に１、異なるクラスタに属する場合に０となる。ここで、||xi|| = 1および||xj|| = 1であることに注目すると、式（５）は、
【数１７】
2009060722.tif 000019
となる。式（６）において、
【数１８】
2009060722.tif 000020
は、画像fi およびfj が同一のキーワードを持つ割合が高くなる程、１に近付き、同一のキーワードを持たない場合に０となる。したがって、指標Ｃは、同一のクラスタに属する画像間で、同一のキーワードを含む割合が高い場合に小さな値となる。従って、これを最小化することで、類似画像検索装置１は、キーワードの適合値に基づいた分類を行うことが可能となる。【００３６】
以上のようにして、類似画像検索装置１は、画像データベース中に存在する画像の分類が可能となる。具体的な分類処理としては、類似画像検索装置１は、最初に全ての画像をK個のクラスタへランダムに分類する。さらに、類似画像検索装置１は、任意の２つの画像に対して属するクラスタを交換した結果、式（６）が低くなる場合、これを新たなクラスタ配置として用いる。この処理を繰り返すことによって、類似画像検索装置１は、順次山登り的に最適なクラスタ配置を求めることが可能となる。【００３７】
次に、本発明の最良の実施の形態に係る類似画像検索装置１は、各クラスタに属する画像から、その画像特徴量およびキーワードの適合値に関する非線形固有空間を算出する。まず本発明の最良の実施の形態に係る類似画像検索装置１は、クラスタk(k = 1、 2、 ・ ・ ・ 、K) に含まれるMk枚の画像
【数１９】
2009060722.tif 000021
に対して、各画像をB×B 個のブロックに分割し、各ブロックに対してビン数がQ の色ヒストグラムを算出する。さらに、類似画像検索装置１は、全てのブロックで算出される色ヒストグラムを順に並べたベクトル
【数２０】
2009060722.tif 000022
を求め、これを非線形写像
【数２１】
2009060722.tif 000023
により高次元特徴空間へ写像した
【数２２】
2009060722.tif 000024
を得る。尚、
【数２３】
2009060722.tif 000025
は、非常に高次元であり、これらを直接算出することは困難である。この問題を解決する計算技法として、カーネルトリックが存在する。この計算法では、任意のx、y (∈ RQB2) が与えられたとき、φ(x)、φ(y) (∈ F) の内積
【数２４】
2009060722.tif 000026
が、次式に示されるように、カーネル関数κ によってx、y から算出される。
【数２５】
2009060722.tif 000027
尚、カーネル関数κ(x、 y) には、Mercer の条件を満たす関数が用いられ、本文では次式のガウシアンカーネルを利用する。
【数２６】
2009060722.tif 000028
さらに、本発明の最良の実施の形態は、クラスタk に属する画像fiの適合値のベクトルxiを
【数２７】
2009060722.tif 000029
で表し、
【数２８】
2009060722.tif 000030
および
【数２９】
2009060722.tif 000031
から次式のベクトル
【数３０】
2009060722.tif 000032
を定義する。
【数３１】
2009060722.tif 000033
ここで、上式のベクトル
【数３２】
2009060722.tif 000034
より、
【数３３】
2009060722.tif 000035
を定義すると、Ξk は、以下の特異値分解の式を満たす。
【数３４】
2009060722.tif 000036
このとき、Hk は、Mk ×Mk の中心化行列である。また、
【数３５】
2009060722.tif 000037
および
【数３６】
2009060722.tif 000038
はそれぞれ、
【数３７】
2009060722.tif 000039
および
【数３８】
2009060722.tif 000040
を共分散行列とするDk 次元の固有ベクトル行列である。Λk はこれらの固有値行列である。式(10) で得られるUk を用いることで、本発明の最良の実施の形態に係る類似画像検索装置１は、その固有ベクトル
【数３９】
2009060722.tif 000041
によって張られる非線形固有空間へ、
【数４０】
2009060722.tif 000042
と同一次元の任意のベクトルを射影することが可能となる。ただし、行列Uk は、各列
【数４１】
2009060722.tif 000043
が高次元であり、直接算出することはできない。そこで、本発明の最良の実施の形態に係る類似画像検索装置１は、カーネルトリックを用いてこの問題を解決するため、特異値分解の式(10) から、
【数４２】
2009060722.tif 000044
を導出し、これを用いることで射影を可能とする。【００３８】
以上のようにして、本発明の最良の実施の形態は、データベース中の画像を分類し、各クラスタについて非線形非線形固有空間を算出することが可能となる。【００３９】
（凸射影法を用いた類似画像検索）
上述した処理によって得られる非線形固有空間を拘束条件に導入した凸射影法を用いることで、類似画像検索装置１は、画像特徴量のみが既知であるクエリ画像に対し、各キーワードの適合値を推定する。さらに、得られる適合値を用いることで、類似画像検索装置１は、データベース中よりクエリ画像に類似する画像の検索を可能とする。この処理は、図１の最適クラスタ抽出部１２に対応する。【００４０】
本発明の最良の実施の形態に係る類似画像検索装置１は、まず、データベース中の画像fi のベクトルyi と同様に、クエリ画像f に対してy を算出する。また、データベース中の画像fi のベクトルxi と同様に、クエリ画像f の適合値が未知であるベクトルをx とし、zは次式のように定義される。
【数４３】
2009060722.tif 000045
さらに、本発明の最良の実施の形態に係る類似画像検索装置１は、ベクトルz に対して以下の２つの拘束条件を満たす
【数４４】
2009060722.tif 000046
を算出することで、未知のベクトルx の推定を行う。【００４１】
[拘束条件1]
ベクトルy は、クエリ画像から直接算のベクトルであり、変化しない。【００４２】
[拘束条件2]
高次元特徴空間においてベクトル
【数４５】
2009060722.tif 000047
は、クラスタkの固有ベクトル
【数４６】
2009060722.tif 000048
によって張られる固有空間内に存在し、次式を満たす。
【数４７】
2009060722.tif 000049
ただし、上式は、式(13) より次式のように変形される。
【数４８】
2009060722.tif 000050
【００４３】
本発明の最良の実施の形態では、以上の２つの拘束条件を満たす閉凸集合をそれぞれC1、C2 とし、類似画像検索装置１は、z を初期ベクトルとして凸射影法により収束する
【数４９】
2009060722.tif 000051
を推定結果として出力する。ここで、[拘束条件1] に注目して
【数５０】
2009060722.tif 000052
とおくと、式(16) は
【数５１】
2009060722.tif 000053
と変形される。ただし、
【数５２】
2009060722.tif 000054
および、
【数５３】
2009060722.tif 000055
であり、式(17) の
【数５４】
2009060722.tif 000056
は次式で与えられる。
【数５５】
2009060722.tif 000057
したがって、ベクトル
【数５６】
2009060722.tif 000058
は、以下の
【数５７】
2009060722.tif 000059
の算出を繰り返すことで求められることが可能となる。
【数５８】
2009060722.tif 000060
【００４４】
以上のようにして、本発明の最良の実施の形態に係る類似画像検索装置１は、ベクトル
【数５９】
2009060722.tif 000061
を算出することが可能となり、クエリ画像に対してl 番目のキーワードの適合値
【数６０】
2009060722.tif 000062
を得ることができる。【００４５】
ここで、本発明の最良の実施の形態の[拘束条件2] において用いられる非線形固有空間に注目すると、この固有空間は、高次元特徴空間に存在する同一次元の部分空間の中で、同一のクラスタに属するベクトル
【数６１】
2009060722.tif 000063
を最小二乗近似する。したがって、ベクトルz が属するクラスタが既知である場合、本発明の最良の実施の形態に係る類似画像検索装置１は、その非線形固有空間を用いて
【数６２】
2009060722.tif 000064
を推定し、キーワードの適合値を精度良く算出することが可能となる。ただし、本発明の最良の実施の形態において、クエリ画像の各キーワードの適合値は未知であるため、類似画像検索装置１は、属するクラスタを式(6) に基づいて決定することではできない。そこで、この問題を解決するため、本発明の最良の実施の形態では、凸射影法により既知のベクトルy において収束する以下の二乗誤差
【数６３】
2009060722.tif 000065
に注目し、類似画像検索装置１は、これを最小とするクラスタをクエリ画像が属するクラスタとして選択する。尚、式（２２）中の
【数６４】
2009060722.tif 000066
は、
【数６５】
2009060722.tif 000067
を満たす。さらに、ガウシアンカーネルの式(8) より、
【数６６】
2009060722.tif 000068
であることから、式(22) の
【数６７】
2009060722.tif 000069
は、次式のように変形される。
【数６８】
2009060722.tif 000070
【００４６】
このようにして算出される指標
【数６９】
2009060722.tif 000071
は、凸射影法の拘束条件より、クエリ画像のベクトル
【数７０】
2009060722.tif 000072
とクラスタk の非線形固有空間との最小距離となる。したがって、本発明の最良の実施の形態では上記指標を用いることで、類似画像検索装置１は、クエリ画像と類似した画像を含むクラスタの適応的選択を行うことが可能となる。【００４７】
最後に本発明の最良の実施の形態では、類似画像検索装置１は、選択されたクラスタを用いて得られるベクトル
【数７１】
2009060722.tif 000073
の要素をクエリ画像の最終的なキーワードの適合値とする。【００４８】
以上のようにして、本発明の最良の実施の形態に係る類似画像検索装置１は、クエリ画像に対してキーワードの適合値を算出することが可能となる。さらに、本発明の最良の実施の形態に係る類似画像検索装置１は、適合値のベクトル
【数７２】
2009060722.tif 000074
を用い、同一のクラスタに属するデータベース中の画像の中から、以下の指標Siを最小とする画像を順にクエリ画像に類似する画像として出力する。
【数７３】
2009060722.tif 000075
これにより、本発明の最良の実施の形態に係る類似画像検索装置１は、キーワードの適合値に基づいた画像の検索を行うことが可能となり、画像の内容に基づいた類似画像の検索が実現される。【００４９】
（効果）
次に、本発明の最良の実施の形態に係る類似画像検索装置１の性能を評価するため実験が示される。【００５０】
実験には５０００枚の画像データベースが、用いられる。尚、各画像は30〜40 個のキーワードが付与されている。画像データベース中に存在する全てのキーワードの総数は4847 個である。具体的には、本実験において類似画像検索装置１は、画像データベースから、図４に示すクエリ画像Ｑ１に類似する画像を検索する。クエリ画像Ｑ１は、赤く紅葉したもみじの葉（図４中において、赤は白抜き表示）の画像である。【００５１】
これらの画像に対して、類似画像検索装置１は、キーワードの適合値に基づいた分類を行い、25 個のクラスタを生成する。さらに、図４は、クエリ画像Ｑ１に対して、凸射影法により類似画像の検索を行った結果を示す。尚、図４は、クエリ画像Ｑ１に対して式(27) で算出される距離が小さな上位９件の検索結果を示している。この検索結果のうち、類似画像Ｇ９は、黄色いいちょうの葉（図４中において、黄色はハッチング表示）が含まれている。【００５２】
この結果より、本発明の最良の実施の形態に係る類似画像検索装置１ではクエリ画像に対して、内容が類似する画像の検索が可能であることが、確認される。【００５３】
従来の画像内容に基づく検索方法は、クエリ画像に対して画像特徴量が最も類似する画像を検索する。したがって、これらの手法では低いレベルの画像特徴量と、実際の意味的特徴間における相関を用いることが困難なため、検索精度に限界が存在する。例えば、画像の色情報を用いることにより、同じ紅葉を示す画像でも、赤く紅葉したものと、黄色く紅葉したものは、類似画像でないと判断されてしまう。このように、従来の検索方法では、クエリ画像と同一の内容を含む、すなわち、紅葉の画像であるにも関わらず、画像特徴量が大きく異なるため、類似画像として検索することが困難である。【００５４】
これに対して、本発明の最良の実施の形態に係る類似画像検索装置１は、クエリ画像の画像特徴量から、凸射影法によりキーワードの適合値の推定を可能とする。さらに、得られるキーワードの適合値を用いてデータベース中の画像間との距離を算出することで、類似画像検索装置１は、画像特徴が大きく異なる画像についても、同一の内容を含む場合には、それらを類似画像として検索することが可能となる。したがって、本発明の最良の実施の形態に係る類似画像検索装置１は、図４に示されるように、内容が類似する画像を検索することができる。【００５５】
このように、本発明の最良の実施の形態に係る類似画像検索装置１は、凸射影法を用いた画像内容に基づく類似画像検索方法を実現した。本発明の最良の実施の形態に係る類似画像検索装置１は、データベース中に存在する画像を分類し、各クラスタの画像特徴量およびキーワードの適合値について算出される非線形固有空間を、凸射影法の拘束条件に導入した。その結果、類似画像検索装置１は、画像特徴量のみが既知であるクエリ画像に対して、凸射影法によりキーワードの適合値を算出することが可能となった。【００５６】
さらに、本発明の最良の実施の形態に係る類似画像検索装置１は、凸射影法により収束する誤差を最小とするクラスタを適応的に選択することで、クエリ画像と類似した画像を含むクラスタから適合値を算出することが可能となった。【００５７】
以上のようにして得られるキーワードの適合値を用いることで、本発明の最良の実施の形態に係る類似画像検索装置１は、クエリ画像と類似した内容を含む画像の検索が可能となった。【００５８】
（その他の実施の形態）
上記のように、本発明の最良の実施の形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなる。【００５９】
例えば、本発明の最良の実施の形態に記載した類似画像検索装置は、図１に示すように一つのハードウェア上に構成されても良いし、その機能や処理数に応じて複数のハードウェア上に構成されても良い。又、既存の情報システム上に実現されても良い。【００６０】
本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。従って、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図１】
2009060722.tif 000076
【図２】
2009060722.tif 000077
【図３】
2009060722.tif 000078
【図４】
2009060722.tif 000079
【国際調査報告】
2009060722.tif 000080
2009060722.tif 000081
2009060722.tif 000082
2009060722.tif 000083