Top > Search of Japanese Patents > (In Japanese)類似画像検索装置 > Specification

Specification :(In Japanese)類似画像検索装置

Country (In Japanese)日本国特許庁(JP)
Gazette (In Japanese)特許公報(B2)
Patent Number P5322111
Date of registration Jul 26, 2013
Date of issue Oct 23, 2013
Title of the invention, or title of the device (In Japanese)類似画像検索装置
IPC (International Patent Classification) G06F  17/30        (2006.01)
G06T   1/00        (2006.01)
FI (File Index) G06F 17/30 210D
G06F 17/30 350C
G06F 17/30 170B
G06T 1/00 200E
Number of claims or invention 1
Total pages 19
Application Number P2009-540010
Date of filing Oct 23, 2008
International application number PCT/JP2008/069193
International publication number WO2009/060722
Date of international publication May 14, 2009
Application number of the priority 2007288796
Priority date Nov 6, 2007
Claim of priority (country) (In Japanese)日本国(JP)
Date of request for substantive examination Sep 27, 2011
Patentee, or owner of utility model right (In Japanese)【識別番号】504173471
【氏名又は名称】国立大学法人北海道大学
Inventor, or creator of device (In Japanese)【氏名】長谷山 美紀
Representative (In Japanese)【識別番号】100083806、【弁理士】、【氏名又は名称】三好 秀和
【識別番号】100101247、【弁理士】、【氏名又は名称】高橋 俊一
Examiner (In Japanese)【審査官】田中 幸雄
Document or reference (In Japanese)小川貴弘ほか,凸射影法を持ちた静止画像中に存在する輝度値消失領域の復元に関する考察 拘束条件に用いる局所画像の分類に関する検討,映像情報メディア学会技術報告,日本,(社)映像情報メディア学会,2006年10月,Vol.30 No.55,83-86頁
多田昌裕ほか,MILを用いた視覚的印象の分析・学習と画像自動分類への応用,情報処理学会研究報告,日本,社団法人情報処理学会,2006年 3月16日,Vol.2006 No.25,13-18頁
Field of search G06F 17/30
G06T 1/00
Scope of claims (In Japanese)【請求項1】
クエリ画像に類似する画像を検索する類似画像検索装置であって、
複数の画像データと、前記画像データに関連するキーワードがそれぞれ関連づけられて記憶された画像データベースと、
前記画像データを読み出して、前記画像データのそれぞれに、前記キーワードの適合を示す指標である適合値を付与するとともに、前記適合値に基づいて、前記複数の画像データを複数のクラスタに分類し、各クラスタについて、このクラスタに属する画像データの画像特徴量およびキーワードの適合値を連結して生成されるベクトルを表現する基底に対応する固有ベクトルを算出するクラスタ分類部と、
前記固有ベクトルが張る非線形固有空間を、凸射影法の拘束条件に導入し、クエリ画像データの既知の画像特徴量のベクトルとの類似度を示す指標が最大となる前記非線形固有空間のクラスタを、クエリ画像データの属する最適クラスタとして選択し、
前記クエリ画像データのクラスタの前記非線形固有空間を用いて前記クエリ画像データに前記適合値を付与する最適クラスタ抽出部と、
前記最適クラスタによって選択されたクラスタに属する前記画像データの中から、前記適合値の類似度を示す指標が最も高い画像データを、類似画像として出力する類似画像抽出部
とを備えることを特徴とする類似画像検索装置。
Detailed description of the invention (In Japanese)【技術分野】
【0001】
本発明は、クエリ画像に類似する画像を検索する類似画像検索装置に関する。
【背景技術】
【0002】
近年のブロードバンド通信の普及や記録媒体の大容量化、さらにディジタルカメラやイメージスキャナ等の普及に伴い、個人のユーザが扱う画像の量が増加している。これに伴って、効果的な画像検索手法の必要性が向上している。
【0003】
従来の画像検索手法として、画像に付与されたキーワード等の意味的特徴に基づく検索法が挙げられる。その他、データベース管理および情報検索の分野において多くの手法が提案されている。
【0004】
例えば、画像にキーワードを付与して、ユーザがキーワードを入力することにより、所望の画像を検索する方法がある。しかし、この方法では、画像に対してユーザがキーワード等を付与する必要があった。従って、その正確さによって検索性能が大きく変化するという問題が存在した。
【0005】
この問題を解決するために、画像のキーワードを自動的に付与する技術が期待されている。この方法の一つとして、画像データを取得したWebデータを解析して、キーワードを取得する方法がある(例えば、特許文献1参照。)。この特許文献1に記載の方法は、Webから取得した画像にキーワードを付与する場合に限られ、汎用的なものではない。
【0006】
また、近年クエリ画像(検索要求画像)としてサンプル画像を入力し、それに類似する画像を提示する手法(Content-Based Image Retrieval: CBIR) が種々提案されている(例えば、非特許文献1参照。)。非特許文献1等に記載の手法は、画像ごとに、色、テクスチャ、形状等の低いレベルの画像特徴量を算出する。そこで、非特許文献1等に記載の手法は、画像ごとの画像特徴量間で算出される距離を、画像間の距離とみなすことで、類似画像の検索を行う。すなわち、非特許文献1等に記載の手法は、ユーザが入力するクエリ画像と、画像特徴量が最も類似する画像を、類似画像として提示する。

【特許文献1】特開2006-277169号公報
【非特許文献1】A. A. Goodrum, “Image information retrieval: An overview of currtent research、” Inf. Sci., vol.3, pp.63-66, 2000.
【発明の開示】
【0007】
しかしながら、単純に画像特徴量間において類似度を求める方法は、低いレベルの画像特徴量と、実際の意味的特徴との相関を考慮していないため、検索精度に限界が存在した。
【0008】
また、従来の方法は、画像特徴量より限られた数のキーワードを画像に対応付けるのみである。従って従来の方法は、明確な一つの意味を持たない画像や、被写体が一種類ではない画像において精度良く検索を行うことが困難である。
【0009】
従って本発明の目的は、画像の意味内容を考慮して、クエリ画像に類似する画像を高精度に検出する類似画像検索装置を提供することである。
【0010】
上記課題を解決するために、本発明の第1の特徴は、クエリ画像に類似する画像を検索する類似画像検索装置に関する。即ち、本発明の第1の特徴に係る類似画像検索装置は、複数の画像データと、画像データに関連するキーワードがそれぞれ関連づけられて記憶された画像データベースと、画像データを読み出して、画像データのそれぞれに、キーワードの適合を示す指標である適合値を付与するとともに、適合値に基づいて、複数の画像データを複数のクラスタに分類し、各クラスタについて、このクラスタに属する画像データの画像特徴量およびキーワードの適合値を連結して生成されるベクトルを表現する基底に対応する固有ベクトルを算出するクラスタ分類部と、固有ベクトルが張る非線形固有空間を、凸射影法の拘束条件に導入し、クエリ画像データの既知の画像特徴量のベクトルとの類似度を示す指標が最大となる前線形固有空間のクラスタを、クエリ画像データの属する最適クラスタとして選択し、クエリ画像データのクラスタの非線形固有空間を用いてクエリ画像データに適合値を付与する最適クラスタ抽出部と、最適クラスタによって選択されたクラスタに属する画像データの中から、適合値の類似度を示す指標が最も高い画像データを、類似画像として出力する類似画像抽出部とを備える。
【0011】
本発明によれば、画像の意味内容を考慮して、クエリ画像に類似する画像を高精度に検出する類似画像検索装置を提供することができる。
【図面の簡単な説明】
【0012】
【図1】図1は、本発明の最良の実施の形態に係る類似画像検索装置の機能ブロック図である。
【図2】図2は、本発明の最良の実施の形態に係る類似画像検索装置のハードウェア構成図である。
【図3】図3は、本発明の最良の実施の形態に係る類似画像検索装置において用いられる凸射影法における反復を説明する図である。
【図4】図4は、本発明の最良の実施の形態に係る類似画像検索装置による類似画像検索処理の結果の一例を説明する図である。

【発明を実施するための最良の形態】
【0013】
次に、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。
【0014】
(最良の実施の形態)
本発明の最良の実施の形態に係る類似画像検索装置1は、クエリ画像に類似する画像を検索する。
【0015】
本発明の最良の実施の形態に係る類似画像検索装置1は、凸射影法を用いることで、各キーワードがクエリ画像にどの程度適合するかを表す指標(以降、適合値と呼ぶ) を推定し、その結果に基づいて類似画像を検索する。本発明の最良の実施の形態に係る類似画像検索装置1は、キーワードが付与されているデータベース中の画像から、以下の2つの新規要素を含む凸射影法を用いることで、クエリ画像に対して適合値の推定を可能とする。第1に、本発明の最良の実施の形態に係る類似画像検索装置1は、データベース中の画像を、適合値に基づいて分類し、各クラスタ毎に算出される画像特徴量および適合値の非線形固有空間を、凸射影法の拘束条件に導入する。このとき用いられる非線形固有空間は、画像特徴量と適合値との相関を表現可能である。従って、類似画像検索装置1は、クエリ画像の画像特徴量のみから全てのキーワードの適合値を算出することが可能となる。第2に、本発明の最良の実施の形態に係る類似画像検索装置1は、凸射影法の収束誤差に注目することで、クエリ画像の属するクラスタを選択する。これにより、類似画像検索装置1は、クエリ画像と類似した画像を含むクラスタの適応的選択が可能となる。従って、類似画像検索装置1は、最適なクラスタによりクエリ画像の適合値を算出することが可能となる。
【0016】
以上のようにして、本発明の最良の実施の形態に係る類似画像検索装置1は、クエリ画像に対して、各キーワードの適合値を推定することが可能となる。類似画像検索装置1は、データベース中の画像との適合値の距離を求めることで、高精度に類似画像の検索を行うことが可能となる。
【0017】
(類似画像検索装置のハードウェア構成)
図2に示すように、本発明の最良の実施の形態に係る類似画像検索装置1において、中央処理制御装置101、ROM(Read Only Memory)102、RAM(Random Access Memory)103及び入出力インタフェース109が、バス110を介して接続されている。入出力インタフェース109には、入力装置104、表示装置105、通信制御装置106、記憶装置107及びリムーバブルディスク108が接続されている。
【0018】
中央処理制御装置101は、入力装置104からの入力信号に基づいてROM102から類似画像検索装置1を起動するためのブートプログラムを読み出して実行し、更に記憶装置107に記憶されたオペレーティングシステムを読み出す。更に中央処理制御装置101は、入力装置104や通信制御装置106などの入力信号に基づいて、各種装置の制御を行ったり、RAM103や記憶装置107などに記憶されたプログラム及びデータを読み出してRAM103にロードするとともに、RAM103から読み出されたプログラムのコマンドに基づいて、データの計算又は加工など、後述する一連の処理を実現する処理装置である。
【0019】
入力装置104は、操作者が各種の操作を入力するキーボード、マウスなどの入力デバイスにより構成されており、操作者の操作に基づいて入力信号を作成し、入出力インタフェース109及びバス110を介して中央処理制御装置101に送信される。表示装置105は、CRT(Cathode Ray Tube)ディスプレイや液晶ディスプレイなどであり、中央処理制御装置101からバス110及び入出力インタフェース109を介して表示装置105において表示させる出力信号を受信し、例えば中央処理制御装置101の処理結果などを表示する装置である。通信制御装置106は、LANカードやモデムなどの装置であり、類似画像検索装置1をインターネットやLANなどの通信ネットワークに接続する装置である。通信制御装置106を介して通信ネットワークと送受信したデータは入力信号又は出力信号として、入出力インタフェース109及びバス110を介して中央処理制御装置101に送受信される。
【0020】
記憶装置107は半導体記憶装置や磁気ディスク装置であって、中央処理制御装置101で実行されるプログラムやデータが記憶されている。リムーバブルディスク108は、光ディスクやフレキシブルディスクのことであり、ディスクドライブによって読み書きされた信号は、入出力インタフェース109及びバス110を介して中央処理制御装置101に送受信される。
【0021】
本発明の最良の実施の形態に係る類似画像検索装置1の記憶装置107には、類似画像検索プログラムが記憶されるとともに、画像データベース21およびクエリ画像データ22が記憶される。又、類似画像検索プログラムが類似画像検索装置1の中央処理制御装置101に読み込まれ実行されることによって、クラスタ分類部11、最適クラスタ抽出部12および類似画像抽出部13が類似画像検索装置1に実装される。
【0022】
(類似画像検索装置の機能ブロック)
図1に示すように、本発明の最良の実施の形態に係る類似画像検索装置1は、画像データベース21、クラスタ分類部11、最適クラスタ抽出部12および類似画像抽出部13を備えている。
【0023】
画像データベース21には、複数の画像データと、画像データに関連するキーワードがそれぞれ関連づけられて記憶される。
【0024】
クラスタ分類部11は、画像データベース21から、画像データを読み出して、画像データのそれぞれに、キーワードの適合を示す指標である適合値を付与する。さらにクラスタ分類部11は、適合値に基づいて、複数の画像データを複数のクラスタに分類する。クラスタ分類部11は、図1に示すように、画像データのそれぞれに付与された適合値に基づいて、各画像データを第1クラスタC1、第2クラスタC2・・・第KクラスタCKに分類する。
【0025】
最適クラスタ抽出部12は、クエリ画像データ22に適合値を付与するとともに、複数のクラスタから、各クラスタを用いた際に凸射影法で生じる誤差が最小になるように、クエリ画像データ22の属するクラスタを選択する。図1に示すように、最適クラスタ抽出部12は、クエリ画像データ22の適合値24を算出する。最適クラスタ抽出部12は、クラスタ分類部11によって生成された第1クラスタC1、第2クラスタC2・・・第KクラスタCKの各クラスタのうち、クエリ画像データ22の適合値24の属するクラスタを決定し、最適クラスタ25として出力する。
【0026】
類似画像抽出部13は、最適クラスタ抽出部12によって選択されたクラスタに属する画像データの中から、適合値の距離が小さな画像データを、類似画像データ23a、23b、23c・・・・として出力する。類似画像抽出部13は、最適クラスタ25に属する画像データを、クエリ画像データ22に類似する画像データ23a、23b、23c・・・・として出力する。
【0027】
(凸射影法)
ここで、本発明の最良の実施の形態で用いられる凸射影法を説明する。
【0028】
凸射影法は、Youla、Webbらによって非線形の画像復元法として用いられた。凸射影法は、原画像f ∈ H (H はヒルベルト空間を表す) に関する既知の特徴から、原画像を推定する手法である。今、原画像のn 種類の特徴をn 個の閉凸集合Ck (k = 1、 2、 ・ ・ ・ 、 n) で表したとき、それらの共通部分
【数1】
JP0005322111B2_000002t.gif
は閉凸集合となり、原画像fを含む。
【数2】
JP0005322111B2_000003t.gif

【0029】
したがって、任意のf0より
【数3】
JP0005322111B2_000004t.gif
に含まれる
【数4】
JP0005322111B2_000005t.gif

を探索することは、原画像を近似した結果を得ることが可能とする。ただし、一般に
【数5】
JP0005322111B2_000006t.gif

は非線形で構造が複雑であるため、容易に記述することはできない。
【0030】
したがって、そのような場合、
【数6】
JP0005322111B2_000007t.gif
を満たす閉凸集合
【数7】
JP0005322111B2_000008t.gif
への射影要素Pkを用いて、類似画像検索装置1は、
【数8】
JP0005322111B2_000009t.gif
を算出する。
【0031】
具体的には、図3に示されるように
【数9】
JP0005322111B2_000010t.gif
が繰り返し処理により
【数10】
JP0005322111B2_000011t.gif
に含まれる
【数11】
JP0005322111B2_000012t.gif
へ収束する性質を用いて、任意のf0から原画像を近似した結果が得られる。
【0032】
(凸射影法を用いた類似画像検索法の概要)
上述した凸射影法を用いることで、クエリ画像に対して各キーワードの適合値を算出し、その結果に基づいて類似画像を検索する方法の概要が説明される。本発明の最良の実施の形態に係る類似画像検索装置1は、データベース中の画像に対して、あらかじめキーワードの適合値に基づいた分類を行う。さらに、類似画像検索装置1は、得られる分類結果から以下の2つの新規要素を含む凸射影法を用いることで、クエリ画像に対し、全てのキーワードの適合値を推定する。
【0033】
(i)各クラスタ毎に算出される画像特徴量およびキーワードの適合値に関する非線形固有空間の、凸射影法の拘束条件への導入
(ii)凸射影法の収束誤差に注目した、クエリ画像が属するクラスタの適応的選択
(i)において用いられる非線形固有空間は、画像特徴量とキーワードの適合値との相関を表現可能である。したがって、これを用いることで、クエリ画像の画像特徴量のみから各キーワードの適合値の推定が期待できる。さらに、(ii) を用いることで、クエリ画像と類似した画像を含むクラスタが決定され、適合値の算出に用いるクラスタの適応的選択が可能となる。以上のようにして得られる適合値を用いることで、本発明の最良の実施の形態では、データベース中よりクエリ画像に類似する画像の検索が可能となる。
【0034】
(各クラスタの非線形固有空間の算出)
ここでは、画像データベース中に存在する画像データに対してキーワードの適合値に基づく分類を行い、得られる各クラスタ毎に非線形固有空間の算出を行う処理が詳述される。この処理は、図1のクラスタ分類部11に対応する。
【0035】
ここで、画像データベース中に存在するN枚の画像をfi (i=1、 2、・・・ 、 N)とし、これらの画像に付与された全てのキーワードがL個であるとする。本発明の最良の実施の形態においては、類似画像検索装置1は、まず、各画像fiに対して各要素が1または0であるベクトル
【数12】
JP0005322111B2_000013t.gif
を算出する。このとき、
【数13】
JP0005322111B2_000014t.gif
は、画像fiがl 番目のキーワードを含む場合に1、含まない場合に0となる。さらに、類似画像検索装置1が、得られる各ベクトル
【数14】
JP0005322111B2_000015t.gif
に対して、
【数15】
JP0005322111B2_000016t.gif
を算出することで、各要素に各キーワードの適合値を含むベクトルxiを算出する。本発明の最良の実施の形態では、以上のベクトルxi を各画像fiの意味的特徴を含む特徴ベクトルとみなし、類似画像検索装置1は、これを次式のC が最小となるように、K 個のクラスタに分類する。
【数16】
JP0005322111B2_000017t.gif
ただし、s(i、 j) は画像fi とfj が同一クラスタに属する場合に1、異なるクラスタに属する場合に0となる。ここで、||xi|| = 1および||xj|| = 1であることに注目すると、式(5)は、
【数17】
JP0005322111B2_000018t.gif
となる。式(6)において、
【数18】
JP0005322111B2_000019t.gif
は、画像fi およびfj が同一のキーワードを持つ割合が高くなる程、1に近付き、同一のキーワードを持たない場合に0となる。したがって、指標Cは、同一のクラスタに属する画像間で、同一のキーワードを含む割合が高い場合に小さな値となる。従って、これを最小化することで、類似画像検索装置1は、キーワードの適合値に基づいた分類を行うことが可能となる。
【0036】
以上のようにして、類似画像検索装置1は、画像データベース中に存在する画像の分類が可能となる。具体的な分類処理としては、類似画像検索装置1は、最初に全ての画像をK個のクラスタへランダムに分類する。さらに、類似画像検索装置1は、任意の2つの画像に対して属するクラスタを交換した結果、式(6)が低くなる場合、これを新たなクラスタ配置として用いる。この処理を繰り返すことによって、類似画像検索装置1は、順次山登り的に最適なクラスタ配置を求めることが可能となる。
【0037】
次に、本発明の最良の実施の形態に係る類似画像検索装置1は、各クラスタに属する画像から、その画像特徴量およびキーワードの適合値に関する非線形固有空間を算出する。まず本発明の最良の実施の形態に係る類似画像検索装置1は、クラスタk(k = 1、 2、 ・ ・ ・ 、K) に含まれるMk枚の画像
【数19】
JP0005322111B2_000020t.gif
に対して、各画像をB×B 個のブロックに分割し、各ブロックに対してビン数がQ の色ヒストグラムを算出する。さらに、類似画像検索装置1は、全てのブロックで算出される色ヒストグラムを順に並べたベクトル
【数20】
JP0005322111B2_000021t.gif
を求め、これを非線形写像
【数21】
JP0005322111B2_000022t.gif
により高次元特徴空間へ写像した
【数22】
JP0005322111B2_000023t.gif
を得る。尚、
【数23】
JP0005322111B2_000024t.gif
は、非常に高次元であり、これらを直接算出することは困難である。この問題を解決する計算技法として、カーネルトリックが存在する。この計算法では、任意のx、y (∈ RQB2) が与えられたとき、φ(x)、φ(y) (∈ F) の内積
【数24】
JP0005322111B2_000025t.gif
が、次式に示されるように、カーネル関数κ によってx、y から算出される。
【数25】
JP0005322111B2_000026t.gif
尚、カーネル関数κ(x、 y) には、Mercer の条件を満たす関数が用いられ、本文では次式のガウシアンカーネルを利用する。
【数26】
JP0005322111B2_000027t.gif
さらに、本発明の最良の実施の形態は、クラスタk に属する画像fiの適合値のベクトルxi
【数27】
JP0005322111B2_000028t.gif
で表し、
【数28】
JP0005322111B2_000029t.gif
および
【数29】
JP0005322111B2_000030t.gif
から次式のベクトル
【数30】
JP0005322111B2_000031t.gif
を定義する。
【数31】
JP0005322111B2_000032t.gif
ここで、上式のベクトル
【数32】
JP0005322111B2_000033t.gif
より、
【数33】
JP0005322111B2_000034t.gif
を定義すると、Ξk は、以下の特異値分解の式を満たす。
【数34】
JP0005322111B2_000035t.gif
このとき、Hk は、Mk ×Mk の中心化行列である。また、
【数35】
JP0005322111B2_000036t.gif
および
【数36】
JP0005322111B2_000037t.gif
はそれぞれ、
【数37】
JP0005322111B2_000038t.gif
および
【数38】
JP0005322111B2_000039t.gif
を共分散行列とするDk 次元の固有ベクトル行列である。Λk はこれらの固有値行列である。式(10) で得られるUk を用いることで、本発明の最良の実施の形態に係る類似画像検索装置1は、その固有ベクトル
【数39】
JP0005322111B2_000040t.gif
によって張られる非線形固有空間へ、
【数40】
JP0005322111B2_000041t.gif
と同一次元の任意のベクトルを射影することが可能となる。ただし、行列Uk は、各列
【数41】
JP0005322111B2_000042t.gif
が高次元であり、直接算出することはできない。そこで、本発明の最良の実施の形態に係る類似画像検索装置1は、カーネルトリックを用いてこの問題を解決するため、特異値分解の式(10) から、
【数42】
JP0005322111B2_000043t.gif
を導出し、これを用いることで射影を可能とする。
【0038】
以上のようにして、本発明の最良の実施の形態においては、データベース中の画像を分類し、各クラスタについて非線形固有空間を算出することが可能となる。
【0039】
(凸射影法を用いた類似画像検索)
上述した処理によって得られる非線形固有空間を拘束条件に導入した凸射影法を用いることで、類似画像検索装置1は、画像特徴量のみが既知であるクエリ画像に対し、各キーワードの適合値を推定する。さらに、得られる適合値を用いることで、類似画像検索装置1は、データベース中よりクエリ画像に類似する画像の検索を可能とする。この処理は、図1の最適クラスタ抽出部12に対応する。
【0040】
本発明の最良の実施の形態に係る類似画像検索装置1は、まず、データベース中の画像fi のベクトルyi と同様に、クエリ画像f に対してy を算出する。また、データベース中の画像fi のベクトルxi と同様に、クエリ画像f の適合値が未知であるベクトルをx とし、zは次式のように定義される。
【数43】
JP0005322111B2_000044t.gif
さらに、本発明の最良の実施の形態に係る類似画像検索装置1は、ベクトルz に対して以下の2つの拘束条件を満たす
【数44】
JP0005322111B2_000045t.gif
を算出することで、未知のベクトルx の推定を行う。
【0041】
[拘束条件1]
ベクトルy は、クエリ画像から直接算のベクトルであり、変化しない。
【0042】
[拘束条件2]
高次元特徴空間においてベクトル
【数45】
JP0005322111B2_000046t.gif
は、クラスタkの固有ベクトル
【数46】
JP0005322111B2_000047t.gif
によって張られる固有空間内に存在し、次式を満たす。
【数47】
JP0005322111B2_000048t.gif
ただし、上式は、式(13) より次式のように変形される。
【数48】
JP0005322111B2_000049t.gif

【0043】
本発明の最良の実施の形態では、以上の2つの拘束条件を満たす閉凸集合をそれぞれC1、C2 とし、類似画像検索装置1は、z を初期ベクトルとして凸射影法により収束する
【数49】
JP0005322111B2_000050t.gif
を推定結果として出力する。ここで、[拘束条件1] に注目して
【数50】
JP0005322111B2_000051t.gif
とおくと、式(16) は
【数51】
JP0005322111B2_000052t.gif
と変形される。ただし、
【数52】
JP0005322111B2_000053t.gif
および、
【数53】
JP0005322111B2_000054t.gif
であり、式(17) の
【数54】
JP0005322111B2_000055t.gif
は次式で与えられる。
【数55】
JP0005322111B2_000056t.gif
したがって、ベクトル
【数56】
JP0005322111B2_000057t.gif
は、以下の
【数57】
JP0005322111B2_000058t.gif
の算出を繰り返すことで求められることが可能となる。
【数58】
JP0005322111B2_000059t.gif

【0044】
以上のようにして、本発明の最良の実施の形態に係る類似画像検索装置1は、ベクトル
【数59】
JP0005322111B2_000060t.gif
を算出することが可能となり、クエリ画像に対してl 番目のキーワードの適合値
【数60】
JP0005322111B2_000061t.gif
を得ることができる。
【0045】
ここで、本発明の最良の実施の形態の[拘束条件2] において用いられる非線形固有空間に注目すると、この固有空間は、高次元特徴空間に存在する同一次元の部分空間の中で、同一のクラスタに属するベクトル
【数61】
JP0005322111B2_000062t.gif
を最小二乗近似する。したがって、ベクトルz が属するクラスタが既知である場合、本発明の最良の実施の形態に係る類似画像検索装置1は、その非線形固有空間を用いて
【数62】
JP0005322111B2_000063t.gif
を推定し、キーワードの適合値を精度良く算出することが可能となる。ただし、本発明の最良の実施の形態において、クエリ画像の各キーワードの適合値は未知であるため、類似画像検索装置1は、属するクラスタを式(6) に基づいて決定することではできない。そこで、この問題を解決するため、本発明の最良の実施の形態では、凸射影法により既知のベクトルy において収束する以下の二乗誤差
【数63】
JP0005322111B2_000064t.gif
に注目し、類似画像検索装置1は、これを最小とするクラスタをクエリ画像が属するクラスタとして選択する。尚、式(22)中の
【数64】
JP0005322111B2_000065t.gif
は、
【数65】
JP0005322111B2_000066t.gif
を満たす。さらに、ガウシアンカーネルの式(8) より、
【数66】
JP0005322111B2_000067t.gif
であることから、式(22) の
【数67】
JP0005322111B2_000068t.gif
は、次式のように変形される。
【数68】
JP0005322111B2_000069t.gif

【0046】
このようにして算出される指標
【数69】
JP0005322111B2_000070t.gif
は、凸射影法の拘束条件より、クエリ画像のベクトル
【数70】
JP0005322111B2_000071t.gif
とクラスタk の非線形固有空間との最小距離となる。したがって、本発明の最良の実施の形態では上記指標を用いることで、類似画像検索装置1は、クエリ画像と類似した画像を含むクラスタの適応的選択を行うことが可能となる。
【0047】
最後に本発明の最良の実施の形態では、類似画像検索装置1は、選択されたクラスタを用いて得られるベクトル
【数71】
JP0005322111B2_000072t.gif
の要素をクエリ画像の最終的なキーワードの適合値とする。
【0048】
以上のようにして、本発明の最良の実施の形態に係る類似画像検索装置1は、クエリ画像に対してキーワードの適合値を算出することが可能となる。さらに、本発明の最良の実施の形態に係る類似画像検索装置1は、適合値のベクトル
【数72】
JP0005322111B2_000073t.gif
を用い、同一のクラスタに属するデータベース中の画像の中から、以下の指標Siを最小とする画像を順にクエリ画像に類似する画像として出力する。
【数73】
JP0005322111B2_000074t.gif
これにより、本発明の最良の実施の形態に係る類似画像検索装置1は、キーワードの適合値に基づいた画像の検索を行うことが可能となり、画像の内容に基づいた類似画像の検索が実現される。
【0049】
(効果)
次に、本発明の最良の実施の形態に係る類似画像検索装置1の性能を評価するため実験が示される。
【0050】
実験には5000枚の画像データベースが、用いられる。尚、各画像は30~40 個のキーワードが付与されている。画像データベース中に存在する全てのキーワードの総数は4847 個である。具体的には、本実験において類似画像検索装置1は、画像データベースから、図4に示すクエリ画像Q1に類似する画像を検索する。クエリ画像Q1は、赤く紅葉したもみじの葉(図4中において、赤は白抜き表示)の画像である。
【0051】
これらの画像に対して、類似画像検索装置1は、キーワードの適合値に基づいた分類を行い、25 個のクラスタを生成する。さらに、図4は、クエリ画像Q1に対して、凸射影法により類似画像の検索を行った結果を示す。尚、図4は、クエリ画像Q1に対して式(27) で算出される距離が小さな上位9件の検索結果を示している。この検索結果のうち、類似画像G9は、黄色いいちょうの葉(図4中において、黄色はハッチング表示)が含まれている。
【0052】
この結果より、本発明の最良の実施の形態に係る類似画像検索装置1ではクエリ画像に対して、内容が類似する画像の検索が可能であることが、確認される。
【0053】
従来の画像内容に基づく検索方法は、クエリ画像に対して画像特徴量が最も類似する画像を検索する。したがって、これらの手法では低いレベルの画像特徴量と、実際の意味的特徴間における相関を用いることが困難なため、検索精度に限界が存在する。例えば、画像の色情報を用いることにより、同じ紅葉を示す画像でも、赤く紅葉したものと、黄色く紅葉したものは、類似画像でないと判断されてしまう。このように、従来の検索方法では、クエリ画像と同一の内容を含む、すなわち、紅葉の画像であるにも関わらず、画像特徴量が大きく異なるため、類似画像として検索することが困難である。
【0054】
これに対して、本発明の最良の実施の形態に係る類似画像検索装置1は、クエリ画像の画像特徴量から、凸射影法によりキーワードの適合値の推定を可能とする。さらに、得られるキーワードの適合値を用いてデータベース中の画像間との距離を算出することで、類似画像検索装置1は、画像特徴が大きく異なる画像についても、同一の内容を含む場合には、それらを類似画像として検索することが可能となる。したがって、本発明の最良の実施の形態に係る類似画像検索装置1は、図4に示されるように、内容が類似する画像を検索することができる。
【0055】
このように、本発明の最良の実施の形態に係る類似画像検索装置1は、凸射影法を用いた画像内容に基づく類似画像検索方法を実現した。本発明の最良の実施の形態に係る類似画像検索装置1は、データベース中に存在する画像を分類し、各クラスタの画像特徴量およびキーワードの適合値について算出される非線形固有空間を、凸射影法の拘束条件に導入した。その結果、類似画像検索装置1は、画像特徴量のみが既知であるクエリ画像に対して、凸射影法によりキーワードの適合値を算出することが可能となった。
【0056】
さらに、本発明の最良の実施の形態に係る類似画像検索装置1は、凸射影法により収束する誤差を最小とするクラスタを適応的に選択することで、クエリ画像と類似した画像を含むクラスタから適合値を算出することが可能となった。
【0057】
以上のようにして得られるキーワードの適合値を用いることで、本発明の最良の実施の形態に係る類似画像検索装置1は、クエリ画像と類似した内容を含む画像の検索が可能となった。
【0058】
(その他の実施の形態)
上記のように、本発明の最良の実施の形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなる。
【0059】
例えば、本発明の最良の実施の形態に記載した類似画像検索装置は、図1に示すように一つのハードウェア上に構成されても良いし、その機能や処理数に応じて複数のハードウェア上に構成されても良い。又、既存の情報システム上に実現されても良い。
【0060】
本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。従って、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
Drawing
(In Japanese)【図1】
0
(In Japanese)【図2】
1
(In Japanese)【図3】
2
(In Japanese)【図4】
3