(57)【特許請求の範囲】
【請求項１】
画像中における検索対象画像要素となるオブジェクトを検索キーとして，そのオブジェクトに類似するオブジェクトを持つ画像を検索する類似画像検索システムにおいて，
予め検索対象の画像からオブジェクトを抽出し，該オブジェクトの画像中の位置情報と特徴量情報とをデータベースに格納して管理するオブジェクト格納手段と，
例示画像を表示し，その画像上でユーザが検索したい領域をユーザに直接指定させる検索領域指定手段と，
上記検索領域指定手段によって指定された検索領域を入力として，該検索領域の位置情報と上記データベースに格納されているオブジェクトの画像中の位置情報との比較により上記検索領域に含まれるオブジェクト集合を検索し，そのオブジェクト集合を検索キーに選択するオブジェクト検索手段と，
上記オブジェクト検索手段によって選択された検索キーを用いて類似画像の検索を行う類似画像検索手段とを備える
ことを特徴とする類似画像検索システム。
【請求項２】
請求項１記載の類似画像検索システムにおいて，
上記検索領域指定手段は，ユーザが検索したくない領域をユーザに直接指定させる手段を持ち，
上記オブジェクト検索手段は，上記検索領域指定手段によって指定された検索したくない領域に含まれるオブジェクト集合を上記オブジェクト格納手段から検索し，選択されている検索キーから除く手段を持つ
ことを特徴とする類似画像検索システム。
【請求項３】
請求項１または請求項２記載の類似画像検索システムにおいて，
上記検索領域指定手段および上記オブジェクト検索手段は，検索領域の指定およびオブジェクトの検索の処理を繰り返す機能を持ち，ユーザに対し検索キーの選択または排除を何度も試行させる
ことを特徴とする類似画像検索システム。
【請求項４】
請求項１ないし請求項３のいずれかに記載の類似画像検索システムにおいて，
検索キーとして不適切なオブジェクトに関する条件を管理し，上記検索領域指定手段および上記オブジェクト検索手段によって得られたオブジェクト集合を入力とし，条件を満たすものを上記オブジェクト集合から除くオブジェクトフィルタリング手段を備える
ことを特徴とする類似画像検索システム。
【請求項５】
請求項１ないし請求項４のいずれかに記載の類似画像検索システムにおいて，
上記類似画像検索手段は，上記選択された検索キーの集合を入力として，その部分集合を生成する部分集合生成手段を備え，
この部分集合生成手段によって生成された部分集合に対し，個々の部分集合内の類似検索は，各部分集合に含まれる検索キーから算出される複数組の特徴量によって類似検索されるオブジェクトを少なくとも一つ含むような画像を検索するか，または複数組の特徴量のそれぞれに類似検索されるオブジェクトをすべて含むような画像を検索することによって行い，部分集合間では上記各部分集合の検索結果の和集合または積集合をとるように画像を検索する
ことを特徴とする類似画像検索システム。
【請求項６】
請求項５記載の類似画像検索システムにおいて，
上記類似画像検索手段は，オブジェクトの画像データおよびオブジェクトの状態の特徴量およびそれらから算出される統計量を入力として，オブジェクトの集合を所定の類似基準に従って分類する検索キークラスタリング手段を備え，
上記選択された検索キーの集合を該検索キークラスタリング手段によって複数のクラスタに分類し，それぞれのクラスタを一つの単位として上記部分集合生成手段における部分集合の生成を行う
ことを特徴とする類似画像検索システム。
【請求項７】
請求項５または請求項６記載の類似画像検索システムにおいて，
上記類似画像検索手段は，検索キーとして不適切なオブジェクトの集合の条件を管理し，上記部分集合生成手段によって生成される部分集合を入力として，上記オブジェクト集合条件によって不適切な部分集合を除いた集合を出力とする部分集合フィルタリング手段を備え，
この出力されたオブジェクトの部分集合に対して上記類似画像検索を行う
ことを特徴とする類似画像検索システム。
【請求項８】
請求項１ないし請求項７のいずれかに記載の類似画像検索システムにおいて，
上記検索領域指定手段と上記オブジェクト検索手段，またはこれらと上記オブジェクトフィルタリング手段によって選択されたオブジェクト集合を，検索領域を指定した画像上において，検索領域に重ねて表示する検索キー表示手段を備える
ことを特徴とする類似画像検索システム。
【請求項９】
請求項５，請求項６または請求項７記載の類似画像検索システムにおいて，
上記部分集合生成手段によって生成された部分集合，またはこの部分集合からさらに上記部分集合フィルタリング手段によって不適切な部分集合を除いた部分集合を入力として，検索領域を指定した画像上において，一つまたは複数の部分集合に含まれるオブジェクトを検索領域に重ねて表示する検索キー表示手段を備える
ことを特徴とする類似画像検索システム。
【請求項１０】
請求項８または請求項９記載の類似画像検索システムにおいて，
上記検索キー表示手段によって検索領域を指定した画像上に表示されるオブジェクトまたはオブジェクト集合を入力とし，オブジェクトの個数または特徴量に関する条件に変換するフィルタリング条件生成手段を持ち，
生成されたフィルタリング条件を，上記検索領域指定手段および上記オブジェクト検索手段によって得られたオブジェクト集合から検索キーとして不適切なオブジェクトを取り除く，または上記オブジェクト集合から生成される部分集合から不適切な部分集合を取り除くための条件とする
ことを特徴とする類似画像検索システム。
【請求項１１】
画像中における検索対象画像要素となるオブジェクトを検索キーとして，そのオブジェクトに類似するオブジェクトを持つ画像を検索する類似画像検索システムにおける計算機による類似画像検索方法において，
上記計算機が，
予め検索対象の画像からオブジェクトを抽出し，該オブジェクトの画像中の位置情報と特徴量情報とをデータベースに格納して管理する第１の過程と，
例示画像を表示し，その画像上でユーザが検索したい領域をユーザに直接指定させ，検索領域を入力する第２の過程と，
上記第２の過程によって得られた検索領域の位置情報と上記データベースに格納されているオブジェクトの画像中の位置情報との比較により，上記データベースから上記検索領域に含まれるオブジェクト集合を検索し，そのオブジェクト集合を検索キーに選択する第３の過程と，
上記第３の過程によって選択された検索キーを用いて類似画像の検索を行う第４の過程とを有する
ことを特徴とする類似画像検索方法。
【請求項１２】
画像中における検索対象画像要素となるオブジェクトを検索キーとして，そのオブジェクトに類似するオブジェクトを持つ画像を検索する類似画像検索システムを計算機によって実現するためのプログラムを記録した計算機読み取り可能な記録媒体であって，
例示画像を表示し，その画像上でユーザが検索したい領域をユーザに直接指定させ，検索領域を入力する処理と，
入力した検索領域をもとに，予め検索対象の画像から抽出されたオブジェクトの画像中の位置情報と特徴量情報とを格納するデータベースから，上記検索領域の位置情報と上記データベースに格納されているオブジェクトの画像中の位置情報とを比較することにより，上記検索領域に含まれるオブジェクト集合を検索し，そのオブジェクト集合を検索キーに選択する処理と，
選択された検索キーを用いて類似画像の検索を行う処理とを
計算機に実行させるプログラムを記録した
ことを特徴とする類似画像検索プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，類似画像検索システムに関し，特に画像の部分的な特徴量をキーとして類似画像を検索するシステムにおける検索条件の生成および表示方法の技術に関するものである。
【０００２】
【従来の技術】
まず，部分画による類似検索について説明する。図１０に，一般的な従来の部分画による類似検索の処理の流れを示す。まず，ステップＳ１００では，例示画像中の検索したい領域をユーザに指定させ，画像中の検索領域を検索キーとして入力する。領域の指定方法には大きく分けて二つあるが，それぞれについては後で述べる。次に，ステップＳ１０１では，選んだ検索領域の色分布などを多次元ベクトルで算出する。算出した結果をこの領域の特徴量と呼ぶ。この特徴量を検索キーとして，次のステップＳ１０２，Ｓ１０３では，データベース内の検索対象である画像の部分領域の特徴量との類似度計算を行い，類似度の高い順に画像を出力する。
【０００３】
類似度計算は，特徴量である多次元ベクトル間の距離として算出され，代表的な距離計算法としてはユークリッド距離がある。これは，二つのベクトルｖ＝｛ｖ1 ，ｖ2 ｝，ｕ＝｛ｕ1 ，ｕ2 ｝の距離を，
distance（ｖ，ｕ）＝（Σi （ｖi −ｕi ）2 ）1/2 
のように算出するものである。
【０００４】
また，データベースに格納する特徴量を求めるための部分領域のとり方には，画像を均等な矩形領域に分割するもの（Columbia大学のVisualseek），エッジの強さにより部分領域に分けるもの（ＮＴＴ社の ExSight：情報処理学会研究報告，97-DBS-113, Vol.97, No.64, pp.155-160, 1997 ）などがある。
【０００５】
次に，従来の類似画像検索システムにおける検索領域の指定方法について説明する。これまでの画像検索システムでは，Informix社のＶＩＲに見られるように，検索のキーを与える手段として画像の部分領域を矩形などの形状で選択するものがある。選択された領域から検索キーとなる特徴量を算出し，これを検索キーとして特徴量の類似する画像を検索する。このような検索キーの指定方法を，領域指定法と呼ぶ。
【０００６】
また，ＮＴＴ社の ExSightは，事前に画像からオブジェクトを抽出しデータベースに格納することを特徴とする類似画像検索システムであり，画像中の一つのオブジェクトをユーザが選び，そのオブジェクトを検索キーとして類似する画像を検索する。さらに ExSightでは，複数のオブジェクトを組み合わせた検索も可能で，複数個の検索キーを用いて検索を行い，それぞれの類似検索の結果の積集合をとることで，複数個のオブジェクトのそれぞれに類似するものが同時に含まれる画像の検索を行うことができる。このような検索条件の指定方法を，オブジェクト指定法と呼ぶ。また，複数の検索キーの組合せを検索条件と呼ぶ。
【０００７】
以上に挙げた方法では，ユーザの指定した領域およびオブジェクトが一つの検索キーに対応する。オブジェクト指定法においては複数の検索キーを指定する場合には，それぞれに対応するオブジェクトを一つ一つ選択する必要がある。
【０００８】
【発明が解決しようとする課題】
図１１は従来技術の問題点を説明するための図であって，図１１（イ）は指定された検索領域，図１１（ロ）は領域指定法の場合に選択されたキー，図１１（ハ）はオブジェクト指定法の場合のキーを示す。
【０００９】
前述したInformix社のＶＩＲでとられている検索領域を単純に矩形で指定する方法は，ユーザの指定方法は直観的で分かりやすいが，図１１（ロ）に示されるように検索したい対象以外にも，背景領域も検索キーとして選ばれてしまうため，背景の影響を受けやすい。これは検索精度を悪くする原因となる。
【００１０】
また，ＮＴＴ社の ExSightは，事前に画像中のオブジェクトをデータベースに格納しておき，ユーザは検索領域を指定する代わりにオブジェクトを選ぶことで，背景を含まない検索キーを指定することができる。しかし，データベースには，有意なオブジェクトとともにそうでないオブジェクトも多く格納されているため，例えば図１１（ハ）に示されるように，指定したオブジェクトが必ずしもユーザが指定したかった領域と一致しているとは限らない。双方にギャップがある場合には，ユーザに対し，ユーザが指定したかった領域が選べていないような違和感を与えてしまう。
【００１１】
図１２のような顔の絵を例にとると，この顔はヒゲの部分で上下に分かれているので， ExSight等のオブジェクト抽出法によりオブジェクトを抽出した場合，二つの顔オブジェクトＡ，ＣとヒゲオブジェクトＢとして抽出される。これは顔に関する特別な知識を使わない限り，現状の画像処理で一つにまとめることは難しい。このとき，顔を検索キーに選ぼうとすると上記の三つのオブジェクトの中から選ばなければならないため，ユーザ要求との不一致が生じる。
【００１２】
また，オブジェクトの選び方に複数の候補がある場合，どのオブジェクトによって検索するべきかはユーザが指示しなければならず，さらに，オブジェクトの組合せで検索する場合には，その組合せの候補もユーザが指示しなければならない。そのため，検索条件を指定するまでのユーザの負担が大きい。図１２を例に挙げると，三つのオブジェクトに対しては７通りの選び方（Ａ，Ｂ，Ｃ，ＡＢ，ＡＣ，ＢＣ，ＡＢＣ）が存在する。
【００１３】
以上に挙げた方法は，どれも検索キーを一つ一つ指定していかなければならないので，複数の検索キーからなる検索条件を作る場合には，ユーザの負担が大きくなる。
【００１４】
本発明の目的は，領域指定法，オブジェクト指定法それぞれの欠点を解決し，ユーザにとって直観的で負担の少ない手順で検索条件を指示することができ，同時に類似検索は背景の影響を受けないオブジェクトに基づく検索条件によって行われるようにすることである。
【００１５】
【課題を解決するための手段】
本発明は，上に述べた課題を解決するものである。図１に，この本発明の構成図を示す。
【００１６】
第１の発明は，検索キーを選択するための手段として，予め検索対象の画像からオブジェクトを抽出し，データベースに格納，管理するオブジェクト格納部１３と，例示画像１０を表示し，その画像上でユーザが検索したい領域をユーザに直接指定させる検索領域指定部１２１と，この検索領域指定部１２１によって指定された検索領域を入力として，オブジェクト格納部１３から上記領域に含まれるオブジェクト集合を検索し，検索キーに選択するオブジェクト検索部１２２とを持つことを特徴とする。
【００１７】
さらに，第２の発明は，検索領域指定部１２１において，ユーザが検索したくない領域を，ユーザに直接指定させることにより，オブジェクト検索部１２２において，検索したくない領域に含まれるオブジェクト集合をオブジェクト格納部１３から検索し，選択されている検索キーから除く手段を持つことを特徴とする。
【００１８】
さらにまた，第３の発明は，上記第１および第２の発明の検索キー選択方法を繰り返すことにより，ユーザが検索キーの選択，および排除を何度も試行できるようにしたことを特徴とする。
【００１９】
第４の発明は，上記第１〜第３の発明の検索キー選択方法において検索キーとして不適切なオブジェクトに関する条件を，オブジェクト条件保持部１４に保持して管理し，上記検索キー選択方法により得られたオブジェクト集合を入力とし，条件を満たすものをオブジェクト集合から除くオブジェクトフィルタリング部１２３を持つことを特徴とする。
【００２２】
第５の発明は，画像中で指定された検索領域について上記第１〜第４の発明の検索キー選択方法によって選択された検索キーの集合を入力とし，その部分集合すべてを数えあげる部分集合生成部１７１を持ち，この部分集合生成部１７１によって生成された部分集合に対し，個々の部分集合内の類似検索は，各部分集合に含まれる検索キーから算出される複数組の特徴量によって類似検索されるオブジェクトを少なくとも一つ含むような画像を検索するか，または複数組の特徴量のそれぞれに類似検索されるオブジェクトをすべて含むような画像を検索することによって行い，部分集合間では部分集合の検索結果の和集合または積集合をとるように画像を検索する手段を持つことを特徴とする。
【００２３】
第６の発明は，上記第１〜第４の発明の検索キー選択方法により選択された検索キーのオブジェクトの集合を分類するための類似基準として与えられた条件を，クラスタリング条件保持部２０に保持して管理し，オブジェクトの画像データおよびオブジェクトの色，形，配置等の特徴量およびそれらから算出される統計量を入力として，オブジェクトの集合を類似基準に従って分類する検索キークラスタリング手段１７５を持ち，それぞれのクラスタを一つの単位として，第５の発明における部分集合生成部１７１の処理を行い，出力されるオブジェクトの部分集合に対して上記類似画像検索を行えるようにしたことを特徴とする。
【００２４】
第７の発明は，検索キーとして不適切なオブジェクトの集合の条件を，部分集合条件保持部１８に保持して管理し，部分集合生成部１７１によって生成される部分集合を入力とし，上記オブジェクト集合条件によって不適切な部分集合を除いた集合を出力とする部分集合フィルタリング部１７２を持ち，この出力されたオブジェクトの部分集合によって，上記第５の発明における類似画像検索を行うことを特徴とする。また，この部分集合フィルタリング部１７２は，上記第６の発明を利用する場合には，クラスタを一つの単位として，不適切な部分集合の除去を行う。
【００２５】
第８の発明は，検索領域を指定した例示画像１０上において，第１〜第４の発明の検索キー選択方法によって選択されたオブジェクト集合のオブジェクトを，検索領域に重ねて表示する検索キー表示部１６を持つことを特徴とする。
【００２６】
第９の発明は，検索領域を指定した例示画像１０上において，第５〜第７の発明において得られた部分集合を入力として，一つまたは複数の部分集合に含まれるオブジェクトを検索領域に重ねて表示する検索キー表示部１６を持つことを特徴とする。
【００２７】
第１０の発明は，上記第８または第９の発明において，表示されるオブジェクトまたはオブジェクト集合を入力とし，オブジェクトの個数，特徴量に関する条件に変換し，上記第４の発明におけるオブジェクトフィルタリング部１２３または第７の発明における部分集合フィルタリング部１７２が使用するオブジェクト条件保持部１４または部分集合条件保持部１８の条件に設定，追加することを特徴とする。
【００２８】
本発明の作用は，以下のとおりである。
上記第１の発明によれば，ユーザは検索キーを指定する場合には，例示画像１０上で直接領域を囲むだけで済み，その検索領域の類似検索はその領域に含まれるオブジェクトの集合により行われるので，背景に影響されずに類似検索を行うことができる。
【００２９】
また，第２の発明または第３の発明のうち一つまたは複数を，第１の発明と組み合わせることにより，複数の検索領域を選択したり，離れた領域を検索領域として指定したり，中空きの領域を指定することができる。
【００３０】
従来のオブジェクト指定法と比べ，ユーザは画像上で直接検索領域を指定できるので直観的な指定ができる。また，検索領域を条件にしてオブジェクト集合を一括して検索キーに選択するので，ユーザはオブジェクトを意識する必要がなくなる。さらに，第４の発明を組み合わせることにより，オブジェクトを選び過ぎないようにオブジェクトフィルタリング部１２３に適切な条件を与えておくことで，例えば面積の小さいオブジェクトをオブジェクト選択から外すことができる。
【００３１】
従来の領域指定法と比べると，背景に依存しない特徴量を検索キーに使えるので，より正確な検索条件によって類似画像検索を実施できる。
【００３２】
複数の検索キーを使った類似画像検索の場合，指定した検索キーのうちどれか一つに類似する画像を検索する方法を用いることができる。例えば図１０の例の場合，顔に対応するオブジェクトとしてＡまたはＣの二つを検索キーに選んで，どちらかに似たオブジェクトを持つような検索を行うことができる。また，指定した検索キーのすべてに類似する画像を検索する方法を用いることもでき，例えば図１０の例の場合には，顔に対応するオブジェクトとしてＡ（顔のオブジェクト）とＢ（ヒゲのオブジェクト）を検索キーに選び，それぞれに類似するオブジェクトを両方含むような検索を行うこともできる。意味的に言い換えるとヒゲを生えている顔を探す類似検索になる。
【００３３】
第５の発明は，複数の検索キーを使った類似検索において，可能性のあるオブジェクトの組合せをシステム側で自動的に生成し類似検索を実行することで，オブジェクト指定法で問題となっていた検索キーの組合せの指定を不要にする。例えば図１２の例において，顔に対応するオブジェクトの集合として，ユーザが領域を指定し，検索キーとしてＡ，Ｂ，Ｃが選択されたとする。このとき，本発明により，集合｛Ａ，Ｂ，Ｃ｝から得られる空でない部分集合｛Ａ｝，｛Ｂ｝，｛Ｃ｝，｛Ａ，Ｂ｝，｛Ａ，Ｃ｝，｛Ｂ，Ｃ｝，｛Ａ，Ｂ，Ｃ｝による類似検索に置き換えることで，洩れのない検索を実施することができる。
【００３４】
さらに，第６の発明によれば，オブジェクトの集合をクラスタリング条件として与えられた類似基準に従って分類することで，検索に有効なクラスタを一単位とした部分集合を生成することができる。
【００３５】
さらに，第７の発明を適用することで，上記の部分集合において不要な組合せを除いた類似検索に置き換えることができる。例えば，先ほどの例で二つ以上のオブジェクトの組合せとして検索したい場合を考える。部分集合の条件として要素数が１のとき，ｔｒｕｅになる条件を部分集合フィルタリング部１７２に持たせておくことで，先ほど生成した部分集合のうちこの条件を満たすものを除いた｛Ａ，Ｂ｝，｛Ａ，Ｃ｝，｛Ｂ，Ｃ｝，｛Ａ，Ｂ，Ｃ｝によって類似検索を行うようになる。また，第６の発明におけるクラスタを一単位として効率的に検索対象となる部分集合を絞り込むこともできる。
【００３６】
第８および第９の発明によれば，上記第１，第２，第３，第４，第５，第６および第７の発明によって，検索の行われるオブジェクトの集合を，ユーザが例示画像１０上で指定した領域上に重ねて表示することで，類似検索のキーとなっているオブジェクトの集合をユーザが把握することを可能にする。さらに，第１０の発明を組み合わせることで，表示されているオブジェクトまたはオブジェクト集合を入力として，ユーザが検索に不適切なオブジェクトまたはオブジェクト集合の条件を生成し，オブジェクト条件保持部１４または部分集合条件保持部１８の条件に設定または追加することができる。これにより，以降の類似検索において不要なオブジェクトまたはオブジェクトの組合せを省くことができる。
【００３７】
以上の各処理手段は，計算機とソフトウェア・プログラムによって実現することができる。以上の各処理手段を実現するためのプログラムは，計算機が読み取り可能な可搬媒体メモリ，半導体メモリ，ハードディスクなどの適当な記録媒体に格納することができる。
【００３８】
【発明の実施の形態】
以下，図１に示す本発明の構成について，具体的な実施の形態に従ってさらに詳しく説明する。
【００３９】
図１において，例示画像１０は，検索キーを指定するための画像である。フィルタリング条件生成部１１は，例示画像１０上に表示されるオブジェクトまたはオブジェクト集合を入力とし，オブジェクトの個数，特徴量に関する条件に変換して，オブジェクト条件保持部１４または部分集合条件保持部１８に設定，追加する手段である。
【００４０】
検索キー選択部１２は，例示画像１０上で指定された検索領域から検索キーを選択するもので，検索領域指定部１２１，オブジェクト検索部１２２，オブジェクトフィルタリング部１２３からなる。検索領域指定部１２１は，例示画像１０を表示し，その画像上でユーザが検索したい領域をユーザに直接指定させる手段である。オブジェクト検索部１２２は，検索領域指定部１２１によって指定された検索領域を入力として，オブジェクト格納部１３から検索領域に含まれるオブジェクト集合を検索し，それを検索キーに選択する手段である。オブジェクトフィルタリング部１２３は，オブジェクト検索部１２２が検索したオブジェクト集合を入力とし，オブジェクト条件保持部１４が保持する条件を満たすものをオブジェクト集合から除く手段である。
【００４１】
オブジェクト格納部１３は，予め検索対象の画像から抽出されたオブジェクトをデータベースに格納して管理するものである。オブジェクト条件保持部１４は，オブジェクトフィルタリング部１２３が使用する条件を，システム開発者，管理者もしくはユーザの設定により，またはフィルタリング条件生成部１１の設定により保持するものである。
【００４２】
オブジェクト集合１５は，検索キー選択部１２によって選択された検索キーとなるオブジェクトの集合であり，類似画像検索部１７の入力となる。検索キー表示部１６は，オブジェクト集合１５または後述する検索キーの部分集合１７３を，例示画像１０上において指定された検索領域に重ねて表示する手段である。
【００４３】
類似画像検索部１７は，オブジェクト集合１５の検索キーを用いて類似画像の検索を行うものであり，部分集合生成部１７１，部分集合フィルタリング部１７２，類似検索エンジン１７４からなる。
【００４４】
部分集合生成部１７１は，オブジェクト集合１５を入力とし，その検索キーの部分集合のすべてを生成する手段である。部分集合フィルタリング部１７２は，部分集合生成部１７１が生成した部分集合について，部分集合条件保持部１８が保持する条件を満たすものを部分集合から取り除く手段である。検索キーの部分集合１７３は，部分集合フィルタリング部１７２の出力であり，類似検索エンジン１７４が類似検索をするときに用いる検索キー群である。類似検索エンジン１７４は，画像中の部分的な領域の色，形等の状態に関する特徴量を示す検索キーの部分集合１７３をもとに，それらと類似するオブジェクトを含む画像を検索するものである。この類似検索エンジン１７４が行う個々の検索キーをもとにした類似画像の検索自体は，従来のオブジェクト指定法で行っていた処理と同様である。
【００４５】
検索キークラスタリング部１７５は，オブジェクトの画像データおよび色，形，配置等の特徴量およびそれらから算出される統計量により，オブジェクトの集合を類似基準に従って分類する手段である。
【００４６】
部分集合条件保持部１８は，部分集合フィルタリング部１７２が使用する条件を，システム開発者，管理者もしくはユーザの設定により，またはフィルタリング条件生成部１１の設定により保持するものである。検索結果画像１９は，類似画像検索部１７によって検索された結果の画像である。
【００４７】
クラスタリング条件保持部２０は，検索キークラスタリング部１７５が類似基準として使用するクラスタリング条件を，システム開発者，管理者もしくはユーザの設定により保持するものである。
【００４８】
以下，上記各処理手段の機能について具体例に従って説明する。
〔検索領域の指定〕
例示画像１０上での領域指定を矩形で指定する場合の例を，図２に示す。検索領域指定部１２により，複数の矩形を指定する場合，検索したい領域かそうでないかを同時に指定することにより，離れた領域を同時に検索領域に指定したり，中空きの領域を検索領域に指定することができる。
【００４９】
図２（イ）は，例示画像１０上で一つの検索領域を指定した場合であり，この場合には，一つの検索領域に含まれるオブジェクト集合が検索キーの対象となる。図２（ロ）は，例示画像上で二つの検索領域を指定した場合であり，この二つの検索領域に含まれるオブジェクト集合が検索キーの対象となる。また，図２（ハ）は，ユーザが二つの検索領域を指定し，内側の矩形領域は検索したくない領域に指定した場合である。この場合，中空きの領域が検索領域として指定されたことになる。
【００５０】
〔オブジェクトの検索〕
例示画像１０上で矩形で検索領域が指定された場合の，オブジェクト検索部１２２によるオブジェクトの検索は，指定された矩形と，オブジェクト格納部１３のデータベースに格納されているオブジェクトの外接矩形との包含関係を調べることにより，検索領域の内部に含まれる外接矩形を持つオブジェクトを選択することで実施される。
【００５１】
例示画像１０内に含まれるオブジェクト集合として，図３を例に考える。それぞれのオブジェクトの外接矩形を左上，右下の座標を並べて次のように表す。
【００５２】
オブジェクトａ：２０，２０，８０，１００
オブジェクトｂ：２５，７０，７５，１１０
オブジェクトｃ：３０，７５，７０，１２０
このとき，検索領域が（１０，１０，１００，１００）の場合には，オブジェクトａのみが選択され，検索領域が（１０，１０，１００，１１０）の場合には，オブジェクトａ，ｂが選択される。
【００５３】
〔複数の検索領域の選択〕
検索キー選択部１２において，複数の検索領域を連続して選択した場合の複数の検索領域によって選ばれるオブジェクト集合について，図３の例示画像１０を例にとり図４に従って説明する。
【００５４】
検索領域（１０，１０，１００，１３０）を選び，次に検索領域（２５，５０，８０，１２０）を検索したくない領域に指定したとする。この検索領域を指定した結果を図４（イ）に示す。図４（ロ）に示すように，最初の領域指定により，オブジェクトａ，ｂ，ｃが選択され，検索条件とするオブジェクト集合の中に入れる。次の領域指定によりオブジェクトｂが選択され，最初に選択されたオブジェクト集合から除かれる（図４（ハ））。よって，この二つの検索領域により，最終的に検索条件となるオブジェクト集合内にａ，ｃが残り，図４（ニ）に示すようにオブジェクトａ，ｃが選択されることになる。
【００５５】
〔オブジェクトのフィルタリング〕
オブジェクトフィルタリング部１２３の機能について説明する。例えば，検索領域により選択されるオブジェクトのうち，オブジェクトの面積が小さいものを除くため，オブジェクト条件として「getPixelArea（オブジェクト）≦２００」の条件をフィルタリング条件生成部１１によって生成し，この条件をオブジェクト条件保持部１４に持たせておく。これはオブジェクトの面積をピクセル数で見たときに，２００ピクセルより小さい場合にｔｒｕｅとなる条件である。選択されているオブジェクト集合を｛Ａ，Ｂ，Ｃ｝とし，
Ａのピクセル数＝３００
Ｂのピクセル数＝２００
Ｃのピクセル数＝１５０
とすると，オブジェクトＢ，Ｃは上記の条件を成立させるためオブジェクト集合から除かれる。結果として，｛Ａ｝がオブジェクト集合として残る。
【００５６】
〔検索キー選択部の処理の流れ〕
検索キー選択部１２において，複数の検索領域を連続して選択するときの処理の流れを，図５に示す。
【００５７】
ステップＳ１１では，まず検索条件として使われるオブジェクト集合を保持する変数をresultSet とし，ある検索領域に含まれるオブジェクト集合を保持する変数をcurrentSetとし，変数resultSet を空集合に初期化する。
【００５８】
次に，領域指定が終了するまで，以下のステップＳ１３〜Ｓ１８による領域指定を続ける（ステップＳ１２）。まず，ステップＳ１３では，検索領域指定部１２１によって，ユーザの入力により検索領域を指定する。すでにオブジェクトが選択されている場合には，新しく指定した領域を加えるのか除くのかをユーザからの入力により指定する。
【００５９】
ステップＳ１４では，オブジェクト検索部１２２によって，検索領域に包含されるようなオブジェクトを，オブジェクト格納部１３から取り出し，currentSetに代入する。
【００６０】
ステップＳ１５の判定により，検索領域の指定が「加える」である場合，ステップＳ１６を実行し，検索領域の指定が「除く」である場合，ステップＳ１７を実行する。ステップＳ１６では，resultSet とcurrentSetのそれぞれに含まれるオブジェクトの和集合をとり，resultSet に入れる。ステップＳ１７では，resultSet 内のオブジェクトのうち，currentSetに含まれるものを取り除く。
【００６１】
次に，ステップＳ１８では，オブジェクトフィルタリング部１２３によって，オブジェクト条件保持部１４にオブジェクトに関する条件が設定されている場合，resultSet の各オブジェクトに対して，条件を満たすかどうかをテストし，満たす場合にはresultSet から取り除く。
【００６２】
以上のステップＳ１３〜Ｓ１８を繰り返し，領域指定が終了したならば，ステップＳ１９へ進み，resultSet に入っているオブジェクトを，選択されたオブジェクト集合１５とする。
【００６３】
〔第１の類似検索の例〕
検索キー選択部１２によって検索キーとして選択されたオブジェクトをａ，ｂとする。それぞれをキーに類似画像検索した結果が，次のようになる場合を考える。
【００６４】
ａ：ＡＢＣＤ
ｂ：ＡＤＥＦ
ＡＢＣＤは，ａをキーに類似検索した結果の画像を類似度順に並べたものとする。
【００６５】
第１の類似検索の例では，それぞれの結果集合のＯＲ（論理和）集合をとり，適当な基準でソートした結果を返す。ソートする基準には，例えばそれぞれの類似検索における類似度順にソートするなどの方法がある。上記の場合には，例えば次のような結果が得られる。
【００６６】
ａ or ｂ：ＡＢＣＤＥＦ
〔第２の類似検索の例〕
第２の類似検索の例を説明する。上記第１の類似検索の例と同じ例を用いると，第２の類似検索では，それぞれの結果集合のＡＮＤ（論理積）集合をとり，適当な基準でソートした結果を返す。ソートする基準には，例えばそれぞれの類似検索における類似度順にソートするなどの方法がある。上記の場合には，例えば次のような結果が得られる。
【００６７】
ａ and  ｂ：ＡＤ
〔部分集合の生成〕
前述した第１および第２の類似検索の例で説明したように，各検索キーについての検索結果について，ＯＲ集合またはＡＮＤ集合をとる検索でもよいが，検索漏れを少なくするために，検索キーの部分集合を作り，これについて次のように検索結果を求めてもよい。このための部分集合生成部１７１の機能について説明する。図３の例示画像１０から検索キーとしてａ，ｂ，ｃが選択されたとする。部分集合生成部１７１は，この検索キーの集合から，次の７個の部分集合を作り，各部分集合の類似検索を実施し，その結果をまとめる。
【００６８】
｛ａ｝
｛ｂ｝
｛ｃ｝
｛ａ，ｂ｝
｛ａ，ｃ｝
｛ｂ，ｃ｝
｛ａ，ｂ，ｃ｝
複数の類似検索は自動的に行われるので，ユーザは洩れのない類似検索を少ない手順で実施することができる。
【００６９】
〔部分集合のフィルタリング〕
部分集合フィルタリング部１７２の機能について説明する。これは，部分集合生成部１７１において，ユーザが予めフィルタリング条件生成部１１により不要な検索キーの組合せの条件を与え，部分集合条件保持部１８に格納しておいたときに，生成する部分集合を制限するものである。
【００７０】
前述した部分集合の生成と同じ例を用いて説明する。例えば，不要な組合せの条件として，「キーの個数が２でない場合にｔｒｕｅ」という条件を与えると，このとき，この条件を満たす組合せは除かれて，次の三つの部分集合によって，類似検索が行われる。
【００７１】
｛ａ，ｂ｝
｛ａ，ｃ｝
｛ｂ，ｃ｝
〔類似画像検索部の処理の流れ〕
類似画像検索部１７の処理の流れを，図６に示す。
【００７２】
ステップＳ２１では，入力となるオブジェクト集合１５を保持する集合型変数をinputSet，検索結果を保持するリスト型変数をresult，検索に含まない部分集合の条件を保持する集合型変数をnogoodConditionSet，検索すべきキーの組合せを保持する集合型変数をcandidateSetとし，resultの初期値を空リストとする。そして，部分集合生成部１７１により，inputSetの集合の空集合でない部分集合をすべて列挙し，これをcandidateSetに入れる。
【００７３】
ステップＳ２２では，部分集合フィルタリング部１７２によって，nogoodConditionSetに条件が設定されているかどうかを調べ，条件が設定されていれば，candidateSetの各部分集合に対してnogoodConditionSetの条件を適用する。もし，nogoodConditionSetの条件を満たす部分集合があれば，その部分集合をcandidateSetから取り除く。
【００７４】
次に，candidateSetの保持するすべての部分集合に対し，類似検索エンジン１７４を用いてステップＳ２３〜Ｓ２９の類似検索を行う。まず，ステップＳ２３では，candidateSetの保持する未処理の部分集合を一つ取り出す。ステップＳ２４では，この部分集合内の各検索キーについて類似検索を実行し，類似オブジェクトＩＤと類似度，およびそれを含む画像ＩＤの組（画像ＩＤ，類似オブジェクトＩＤ，類似度）の結果リストを作る。ステップＳ２４の処理を部分集合内のすべての検索キーについて繰り返す（ステップＳ２５）。
【００７５】
一つの部分集合のすべての検索キーについての類似検索が終了したならば，ステップＳ２６では，同じ画像に含まれるオブジェクトの組を得るために，それぞれの結果リストに共通して現れる画像ＩＤの集合を求める（ＡＮＤ処理）。ステップＳ２７では，結果リスト内のすべての組に対し，ステップＳ２６で求めた共通画像ＩＤを持つ組を取り出し，resultに追加する。
【００７６】
以上のステップＳ２３〜Ｓ２７を，candidateSetの保持する全部分集合について実行したならば（ステップＳ２８），次のステップＳ２９へ進み。result内の組を類似度でソートする。この結果を検索結果画像１９とする。
【００７７】
上記の処理では，オブジェクトの部分集合の検索を，部分集合内ではＡＮＤ検索，部分集合間ではＯＲ検索を実施する場合について述べたが，部分集合内でＯＲ検索，部分集合間でＡＮＤ検索を行うような実施も可能である。
【００７８】
なお，後述する「検索キーの部分集合の切り替え表示」に対応して，切り替え表示された部分集合の検索キーを用いた検索結果を，それぞれの切り替え表示ごとに検索結果画像１９として出力してもよい。
【００７９】
〔検索キーのクラスタリング〕
部分集合生成部１７１において検索キーの部分集合を作る際に，すべての部分集合を作るのではなく，真に検索に有効な部分集合を作り出すために，検索キークラスタリング部１７５を設けてもよい。以下，検索キークラスタリング部１７５の機能について説明する。図７のような画像全体で検索する場合を例に取り上げる。図７（Ａ）に示す画像中には，検索キーとして５つのオブジェクトａ，ｂ，ｃ，ｄ，ｅが存在するとする。また，これらのオブジェクトの色特徴量は，次のようなベクトル値をとるものとする。
【００８０】
オブジェクトａ：（０，２５５，０）
オブジェクトｂ：（２５５，０，０）
オブジェクトｃ：（２５０，０，０）
オブジェクトｄ：（２５３，０，０）
オブジェクトｅ：（１２０，６０，０）
また，クラスタリング条件保持部２０に，次のようなクラスタリング条件が保持されているとする。
『クラスタリング条件：オブジェクト数が５以上のときに，オブジェクトの色特徴量のユークリッド距離を求めて，閾値１０を基準に距離が１０以内のオブジェクトを一つのグループに分類する。』
図７（Ａ）に示す５つのオブジェクトが検索キーとして選択されたとき，上記のクラスタリング条件が有効になり，検索キーのクラスタリングが行われる。計算した上記５つのオブジェクトのユークリッド距離を図８に示す。図８に示すそれぞれの距離が１０以下のオブジェクト対をグルーピングしていくと，次の３つのグループに分類される。
【００８１】
グループＧ１＝｛ａ｝
グループＧ２＝｛ｂ，ｃ，ｄ｝
グループＧ３＝｛ｅ｝
次に，これらのグループを単位に部分集合を生成する。
【００８２】
｛Ｇ１｝
｛Ｇ２｝
｛Ｇ３｝
｛Ｇ１，Ｇ２｝
｛Ｇ１，Ｇ３｝
｛Ｇ２，Ｇ３｝
｛Ｇ１，Ｇ２，Ｇ３｝
次に，フィルタリング条件が設定されていれば，部分集合フィルタリング部１７２により，部分集合に対し照合が行われ，不適切な部分集合は取り除かれる。グループ単位で照合が行われるか，あるいはグループ内のオブジェクトに対し照合が行われるかは，部分集合条件保持部１８に保持されているフィルタリング条件に依存する。例えば「オブジェクト数が１のものは取り除く」という条件が設定されている場合には，グループＧ１，Ｇ３が除かれる。
【００８３】
以上の過程によって，次のような５組の検索キーの部分集合が得られる。
｛｛ｂ，ｃ，ｄ｝｝
｛｛ａ｝，｛ｂ，ｃ，ｄ｝｝
｛｛ａ｝，｛ｅ｝｝
｛｛ｂ，ｃ，ｄ｝，｛ｅ｝｝
｛｛ａ｝，｛ｂ，ｃ，ｄ｝｛ｅ｝｝
この部分集合に対して，ＡＮＤ検索またはＯＲ検索による類似画像検索が行われる。ここでは，オブジェクトの色特徴量に基づくクラスタリングの例を取り上げたが，同様にオブジェクトの形に関する分類，面積に関する分類，位置に関する分類などを用いることもできる。
【００８４】
〔検索キーの表示〕
検索キー表示部１６による検索キーの表示機能について説明する。これは，前述した検索キー選択部１２によって選択されたオブジェクト集合１５を，ユーザが例示画像１０上で指定した検索領域上に重ねて表示するものである。
【００８５】
図９は，この選択されたオブジェクト集合の表示例を示している。ここでは，顔のオブジェクトａとヒゲのオブジェクトｂの二つのオブジェクトが選択されているので，それをこの例では外接矩形に内接する楕円として表示している。別の処理方法としては，矩形やオブジェクトの輪郭などを表示するなどが考えられる。
【００８６】
〔検索キーの部分集合の切り替え表示〕
検索キー表示部１６により検索キーの部分集合１７３を表示することもできる。例えば，前述した部分集合のフィルタリングの例では，フィルタリングの結果，三つの部分集合が存在するので，３通りの表示を切替えることができる。部分集合は，類似検索の最小単位を表し，ユーザはこの機能によりそれを確認することができる。なお，表示するオブジェクトは，類似検索エンジン１７４による類似検索後に行うこともできる。
【００８７】
〔フィルタリング条件の生成〕
フィルタリング条件生成部１１の機能について説明する。これは，検索キー表示部１６で表示したオブジェクトまたはオブジェクト集合について，検索条件を入力し，それをオブジェクト条件保持部１４または部分集合条件保持部１８の条件に設定または追加するものである。例えば，上記部分集合の生成の説明で用いた例を使うと，部分集合ａを表示し，これを使って，要素数が１のときにｔｒｕｅとなる条件を入力する。これを部分集合条件保持部１８に設定することにより，次回の検索より，部分集合フィルタリング部１７２によって，要素数が１の部分集合の生成が抑制されるようになる。
【００８８】
【発明の効果】
以上説明したように，本発明によれば，ユーザは検索キーを指定するためには，画像上で直接領域を囲むだけで済む。また，複数の領域を選択し，それらの間の論理演算として和（検索領域を加える）と差（検索領域を削る）を指定することで，離れた領域を検索領域として指定したり，中空きの領域を指定することができる。
【００８９】
従来のオブジェクト指定法と比べ，ユーザは画像上で直接検索領域を指定できるので直観的な指定ができる。また，検索領域を条件にしてオブジェクト集合を一括して検索キーに選択するので，ユーザはオブジェクトを意識する必要がなくなる。また，オブジェクトを選び過ぎないようにオブジェクトフィルタリング手段に適切な条件を与えておくことで，例えば面積の小さいオブジェクトをオブジェクト選択から外すことができる。
【００９０】
従来の領域指定法と比べると，類似検索に参照される特徴量は背景に依存しない検索を行うことができる。
【００９１】
また，本発明によれば，従来のオブジェクト指定法でユーザに委ねられていたオブジェクトおよびオブジェクトの組合せの多様性をシステム側で扱えるようにし，必要な組合せは自動的に生成して検索することが可能になるので，オブジェクト指定法で問題となっていたキー指定のユーザの負担はなくなる。
【００９２】
また，本発明によれば，生成された検索条件をユーザが把握することが可能となり，どのようなオブジェクトの組合せによって検索が行われるかを知ることができる。不要な組合せが見つかった場合には，部分集合フィルタリング部がフィルタリングに使用する条件に追加することにより，以降の検索においては不要なオブジェクトの組合せを抑制することができる。
【図面の簡単な説明】
【図１】本発明の構成図である。
【図２】本発明による検索領域の指定方法の例を示す図である。
【図３】検索領域とオブジェクト集合の選択の例を示す図である。
【図４】複数の検索領域によって選ばれるオブジェクト集合の例を示す図である。
【図５】検索キー選択部において複数の検索領域を連続して選択するときの処理の流れを示す図である。
【図６】類似画像検索部の処理の流れを示す図である。
【図７】検索キーのクラスタリングを説明するための図である。
【図８】クラスタリングのためのユークリッド距離の計算結果の例を示す図である。
【図９】選択されたオブジェクト集合の表示例を示す図である。
【図１０】一般的な従来の部分画による類似検索の処理の流れを示す図である。
【図１１】従来技術の問題点説明図である。
【図１２】検索したい領域とオブジェクトが一致しない例を示す図である。
【符号の説明】
１０    例示画像
１１    フィルタリング条件生成部
１２    検索キー選択部
１２１  検索領域指定部
１２２  オブジェクト検索部
１２３  オブジェクトフィルタリング部
１３    オブジェクト格納部
１４    オブジェクト条件保持部
１５    オブジェクト集合
１６    検索キー表示部
１７    類似画像検索部
１７１  部分集合生成部
１７２  部分集合フィルタリング部
１７３  検索キーの部分集合
１７４  類似検索エンジン
１７５  検索キークラスタリング部
１８    部分集合条件保持部
１９    検索結果画像
２０    クラスタリング条件保持部
【図１】
0003683758.tif 000002
【図２】
0003683758.tif 000003
【図３】
0003683758.tif 000004
【図４】
0003683758.tif 000005
【図５】
0003683758.tif 000006
【図６】
0003683758.tif 000007
【図７】
0003683758.tif 000008
【図８】
0003683758.tif 000009
【図９】
0003683758.tif 000010
【図１０】
0003683758.tif 000011
【図１１】
0003683758.tif 000012
【図１２】
0003683758.tif 000013