(57)【特許請求の範囲】
【請求項１】
入力画像に対する構図データを生成する構図データ生成装置であって、
前記入力画像を所定のブロック数に分割し、分割された全ブロックを、各ブロックの画像特徴に基づいて複数のクラスタに分類し、分類された各クラスタに含まれる各ブロックに対して、各クラスタ単位に同一のフラグを付与するクラスタ分類手段と、
前記クラスタ分類手段により分類された各クラスタの画像特徴を平均した中心特徴と、前記各ブロックの画像特徴との類似度を算出する類似度算出手段と、
前記クラスタ分類手段により得られたフラグと、前記類似度算出手段により得られた類似度とに基づいて、前記各ブロックに実数値を割り当て、前記構図データを生成する構図データ生成手段とを有することを特徴とする構図データ生成装置。
【請求項２】
前記構図データ生成手段により得られる構図データの集合を、前記構図データの類似度に基づいてクラスタリングする構図データクラスタリング手段と、
前記構図データクラスタリング手段により得られる構図グループに含まれる構図データに基づいて主要構図データを生成する主要構図データ生成手段とを有することを特徴とする請求項１に記載の構図データ生成装置。
【請求項３】
前記構図データクラスタリング手段は、
前記クラスタリングにより得られる複数の構図グループのうち、各構図グループに含まれる要素数が予め設定された値以下の構図グループを切り捨てることを特徴とする請求項２に記載の構図データ生成装置。
【請求項４】
前記主要構図データ生成手段により得られる複数の構図テンプレートと、検索対象画像との類似度を比較し、比較果として選択された構図テンプレートに対応する構図グループに含まれる画像データを用いて、前記検索対象画像に対応する類似画像を検索する検索手段を有することを特徴とする請求項２又は３に記載の構図データ生成装置。
【請求項５】
コンピュータを、請求項１乃至４の何れか１項に記載の構図データ生成装置として機能させることを特徴とする構図データ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構図データ生成装置及び構図データ生成プログラムに係り、特に画像検索等に用いられる画像の構図データを効率的かつ高精度に生成するための構図データ生成装置及び構図データ生成プログラムに関する。
【背景技術】
【０００２】
従来では、マルチメディア技術の発展に伴い、画像処理に対する要求も高まっている。例えば、複数の画像から所定の画像に類似する画像を検索する場合には、大量の画像にアクセスし、類似性を判断する処理が必要になる。このため、画像検索技術においては、正確性及び高速性が重要なポイントになっている。
【０００３】
このような画像検索技術としては、様々な装置及び方法が提案されている。例えば、従来では、既に格納されている複数の画像から、入力画像に類似する画像を概念的に検索する手法が提案されている（例えば、特許文献１参照）。特許文献１に示されている装置は、ベクトル作成辞書を用いて、検索対象の複数の画像から検索対象図面ベクトル群を作成すると共に、入力画像から入力図面ベクトルを作成し、検索対象図面ベクトル群と入力図面ベクトルとの間のベクトル演算値を計算し、ベクトル演算値に基づいて検索対象の複数の画像を検索し、入力画像に類似する画像を抽出する。
【０００４】
また、従来では、入力画像の自己相関波形を抽出し、その自己相関波形の傾向が変化する接合点を抽出し、接合点によって分割される自己相関波形の各区分領域を関数で近似し、関数の種類を示す符号、及び区分領域の形状を示すパラメータを用いて、入力画像の特徴情報を生成し、入力画像の特徴情報、及び検索対象の画像の特徴情報に基づいて類似度を計算し、類似度に従って類似画像を抽出する装置が提案されている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−２４５０８７号公報
【特許文献２】特開２００６−１８５３６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述した特許文献１及び２に示す画像検索装置では、検索対象の画像と入力画像との間で、ベクトル演算値等の類似度を計算し、検索対象の画像毎の計算結果に基づいて、複数の画像から入力画像に類似する画像を抽出する。
【０００７】
しかしながら、検索対象の画像は、大容量であるのが通常である。このため、上述した特許文献１及び２の画像検索装置では、大容量の画像毎に、ベクトル演算値等の類似度の計算を行う必要が生じる。そのため、従来の画像検索装置では、類似画像を検索するのに時間がかかり、計算コストが膨大になるという問題があった。
【０００８】
したがって、例えば、画像検索装置等に利用される検索対象である複数の画像から、入力画像に類似する画像を検索する場合には、複数の画像に対して予め所定の条件で分類しておき、入力画像と同一又は類似（関連）する１又は複数の分類に属する画像のみを用いて検索するが好ましい。これにより、入力画像に類似する画像を検索する場合には、計算コストを削減して高速検索を実現することができるからである。
【０００９】
本発明は、上述した問題点に鑑みなされたものであり、画像検索等に用いられる画像の構図データを効率的かつ高精度に生成するための構図データ生成装置及び構図データ生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本件発明は、以下の特徴を有する課題を解決するための手段を採用している。
【００１１】
本発明は、入力画像に対する構図データを生成する構図データ生成装置であって、前記入力画像を所定のブロック数に分割し、分割された全ブロックを、各ブロックの画像特徴に基づいて複数のクラスタに分類し、分類された各クラスタに含まれる各ブロックに対して、各クラスタ単位に同一のフラグを付与するクラスタ分類手段と、前記クラスタ分類手段により分類された各クラスタの画像特徴を平均した中心特徴と、前記各ブロックの画像特徴との類似度を算出する類似度算出手段と、前記クラスタ分類手段により得られたフラグと、前記類似度算出手段により得られた類似度とに基づいて、前記各ブロックに実数値を割り当て、前記構図データを生成する構図データ生成手段とを有することを特徴とする。
【００１２】
また本発明は、コンピュータを、上述した構図データ生成装置として機能させることを特徴とする構図データ生成プログラムである。
【発明の効果】
【００１３】
本発明によれば、画像検索等に用いられる画像の構図データを効率的かつ高精度に生成することができる。
【図面の簡単な説明】
【００１４】
【図１】本実施形態における構図データ生成装置の機能構成の一例を示す図である。
【図２】分類したクラスタ例を示す図である。
【図３】本実施形態における実数値の設定方法を示す図である。
【図４】構図データクラスタリングの一例を示す図である。
【図５】構図グループと、主要構図データとの関係を説明するための図である。
【図６】構図サブグループの一例を示す図である。
【図７】本実施形態における検索例を示す図である。
【図８】本実施形態における構図データ生成処理の一例を示すフローチャート（その１）である。
【図９】本実施形態における構図データ生成処理の一例を示すフローチャート（その２）である。
【図１０】本実施形態における検索処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１５】
＜本発明について＞
本発明は、例えば予め取得した大量の画像データに対し、画像データ毎に所定のブロック領域単位で表現された構図データを抽出する。
【００１６】
具体的には、本発明は、例えば１枚の画像データを所定のブロック数に分割し、画像上の全ブロックを、各ブロックの画像特徴に基づき複数のクラスタに分類し、各クラスタ単位の画像特徴と各ブロックの画像特徴との類似度等に基づいて、各ブロックに実数値を割り当て、画像の構図データを生成する。
【００１７】
なお、本発明は、上述した構図データ集合をクラスタリングして構図グループを生成し、生成された構図グループから主要構図（構図テンプレート）を生成する機能を有していてもよい。更に、本発明は、構図テンプレートや構図グループを用いて検索対象画像に対する類似画像を検索する機能を有していてもよい。
【００１８】
以下に、上述したような特徴を有する本発明における構図データ生成装置及び構図データ生成プログラムを好適に実施した形態について、図面を用いて詳細に説明する。
【００１９】
＜構図データ生成装置：機能構成例＞
図１は、本実施形態における構図データ生成装置の機能構成の一例を示す図である。図１に示す構図データ生成装置１０は、入力手段１１と、出力手段１２と、蓄積手段１３と、クラスタ分類手段１４と、類似度算出手段１５と、構図データ生成手段１６と、構図データクラスタリング手段１７と、主要構図データ生成手段１８と、検索手段１９と、送受信手段２０と、制御手段２１とを有するよう構成されている。
【００２０】
入力手段１１は、例えばユーザ等からのクラスタ分類指示、類似度算出指示、構図データ生成指示、構図データクラスタリング指示、主要構図データ生成指示、検索指示、送受信指示等の構図データ生成における各入力を受け付ける。なお、入力手段１１は、例えばキーボードや、マウス等のポインティングデバイス、マイク等の音声入力機能等を有する。
【００２１】
出力手段１２は、入力手段１１により入力された指示内容や、各指示内容に基づいて生成された制御データや構図データ生成結果や検索結果、各種処理経過等の内容を表示したり、音声等を出力する。なお、出力手段１２は、ディスプレイ等の画面表示機能やスピーカ等の音声出力機能等を有する。
【００２２】
蓄積手段１３は、本実施形態における構図データ生成を行うための基となる画像データや、クラスタリングされた画像データ、類似度を算出するための数式等の各種パラメータ、構図データ、構図データをクラスタリングするための各種パラメータ、構図グループ、主要構図データ（構図テンプレート）、検索対象画像、検索結果等、本実施形態における構図データ生成において必要な各種情報等を蓄積する。
【００２３】
なお、蓄積手段１３は、送受信手段２０を介して通信ネットワーク等に接続される外部装置等から取得される本実施形態で使用可能な画像データや構図データ、各種パラメータ等を蓄積する。また、蓄積手段３３は、本実施形態における構図データ生成処理等において、上述した各種データを読み出したり、書き込んだりすることができる。
【００２４】
クラスタ分類手段１４は、構図データ生成を行う基となる複数の画像を、所定の数又は大きさのブロック毎に分類し、その分類した領域の画像特徴から１又は複数のクラスタに分類する。また、クラスタ分類手段１４は、分類された画像に対し、同一のクラスタに属するブロック領域に同一のフラグ（例えば、−１，０，１等）を付与する。
【００２５】
なお、フラグは、例えば整数であることが好ましいが、自然数や小数点を含む数値等であってもよい。更にフラグは、例えば、各ブロックに含まれる各画素のＲＧＢ値に基づいて設定されてもよいが、本発明においてはこれに限定されるものではない。クラスタ分類手段１４における具体的な分類手法については、後述する。
【００２６】
類似度算出手段１５は、各クラスタにおいて、所属するブロック領域の画像特徴を平均し、クラスタの中心特徴を求める。また、類似度算出手段１５は、求めた中心特徴と、クラスタの分類結果とに基づいて、予め設定された算出手法等を用いて類似度を算出する。なお、類似度算出手段１５における具体的な類似度算出手法については、後述する。
【００２７】
構図データ生成手段１６は、各ブロックに付与されているフラグと、類似度算出手段１５において算出された類似度とに基づいて各ブロックにおけるフラグの値を実数値に変換する。なお、実数値への変換手法としては、例えば、フラグの値と類似度の値を乗算してもよく、また他の四則を用いて算出したり、所定の数式の変数部にフラグの値と類似度を代入して算出してもよく、また実数値が−１〜１の範囲内になるように値を調整してもよいが、本発明においてはこれに限定されるものではない。
【００２８】
また、構図データ生成手段１６は、各ブロック領域に割り当てられた実数値を含む画像の構図データを出力する。なお、構図データ生成手段１６における具体的な構図データ生成例については、後述する。
【００２９】
構図データクラスタリング手段１７は、構図データ生成手段１６により生成された構図データの各画像の集合を、構図データの類似度に基づいてクラスタリングして構図グループを生成する。なお、構図データクラスタリング手段１７における具体的な構図データのクラスタリング手法については、後述する。
【００３０】
主要構図データ生成手段１８は、構図データクラスタリング手段１７で得られたクラスタリング結果（構図グループ）のうち、要素数（例えば、画像数等）が予め設定された値以下の構図グループを切り捨てる。なお、切り捨てる条件としては、上述した要素数に限定されるものではなく、例えば構図グループの数により設定してもよい。この場合には、例えばグループ毎に含まれる要素数の多い順に構図グループを並べ、上位の所定数の構図グループ（例えば、１０グループ）よりも下位の構図グループを切り捨てる等の処理を行うことができる。
【００３１】
また、主要構図データ生成手段１８は、切り捨てられずに残った各構図グループにおいて、所属するグループに含まれる要素（例えば、画像）の平均構図データを求める。更に、主要構図データ生成手段１８は、各構図グループの平均構図データを主要構図データ（構図テンプレート）として出力する。
【００３２】
検索手段１９は、上述した構図テンプレートや構図グループを用いて検索対象画像に対する類似画像を検索する。具体的には、検索手段１９は、入力される検索対象画像に対して、上述したようにクラスタ分類やフラグを付与し、既に生成されている各構図テンプレートと比較して、類似性の高い１又は複数の構図テンプレートを選択する。その後、検索手段１９は、検索対象画像と、選択された構図テンプレートに対応する構図グループに含まれる１又は複数の画像群との比較を行い、類似性の高い１又は複数の画像を検索結果として出力する。なお、検索手段１９は、構図データ生成装置１０内に構成されていなくてもよく、例えば外部装置（画像検索装置）として設けられていてもよい。
【００３３】
送受信手段２０は、インターネット等に代表される通信ネットワークを介して構図データ生成装置１０内の各種画像や主要構図データ、検索結果等を外部装置等に送信する。また、送受信手段２０は、通信ネットワークに接続された外部装置等から、構図データを生成する複数の画像データは、検索対象画像、その他の各種データ等を受信する。つまり、送受信手段２０は、送受信可能な各種データを、他の装置に送信したり、他の装置から各種データを受信するための通信インタフェースである。
【００３４】
制御手段２１は、構図データ生成装置１０における各機能構成全体の制御を行う。具体的には、制御手段２１は、入力手段１１により入力されたユーザ等からの入力情報に基づいて、基となる複数の画像データ（原画像データ）のクラスタ分類を行ったり、類似度算出を行ったり、構図データを生成したり、構図データクラスタリングを行ったり、主要構図データを生成したり、類似画像を検索する等、本実施形態における構図データ生成において必要となる各種を制御する。
【００３５】
上述したように本実施形態によれば、画像の構図に基づいて効率的に高精度な構図データ生成を実現することができる。
【００３６】
＜クラスタ分類手段１４における具体的な分類手法＞
ここで、上述したクラスタ分類手段１４における具体的な分類手法について説明する。クラスタ分類手段１４では、上述したように構図データ生成を行う基となる複数の画像を、所定の数又は大きさのブロック毎に分類する。
【００３７】
本実施形態では、各画像に対して、例えばＭ×Ｎ個のブロックに分類する。なお、分類する個数については、これに限定されるものではなく、例えば画像中の解像度や画像サイズ、装置の処理性能等に応じて任意に設定することができる。
【００３８】
次に、クラスタ分類手段１４は、分類したブロック領域毎に画像特徴を取得する。なお、本実施形態における画像特徴の例としては、例えば、色特徴やモノクロ特徴（テクスチャ特徴）等を用いることができるが、本発明においてはこれに限定されるものではない。
【００３９】
ここで、上述した色特徴の例としては、例えば各ブロックにより得られるＲＧＢ平均値ベクトル（ｒ，ｇ，ｂ）や色相ヒストグラム（ｈ１，ｈ２，・・・，ｈＫ）（なお、Ｋはブロック数を示し、ｈ１〜ｈＫは各ブロックの色相を示す）等を用いることができる。
【００４０】
また、モノクロ特徴（テクスチャ特徴）の例としては、例えば各ブロックにより得られる平均輝度値（ｍ）やエッジ量（ｅ）、エッジ方向ヒストグラム（ｄ１，ｄ２，・・・，ｄＬ）（なお、Ｌはブロック数を示し、ｄ１〜ｄＬは各ブロックのエッジ方向を示す）等を用いることができる。
【００４１】
更に、本実施形態では、上述した例に限定されるものではなく、例えば複数の画像特徴を組み合わせることもできる。例えば、色特徴とテクスチャ特徴とを組み合せた場合には、例えばＲＧＢ平均値ベクトルとエッジ量とを組み合わせて（ｒ，ｇ，ｂ，ｅ）としたり、色相ヒストグラムとエッジ方向ヒストグラムとを組み合わせて（ｈ１，ｈ２，・・・，ｈＫ，ｄ１，ｄ２，・・・，ｄＬ）とし、得られた画像特徴に基づいて、１又は複数のクラスタに分類することができる。
【００４２】
また、クラスタ分類手段１４は、上述したように同一のクラスタに属するブロック領域に同一のフラグを付与する。ここで、図２は、分類したクラスタ例を示す図である。
【００４３】
図２に示す例において、クラスタ分類手段１４は、基となる画像（原画像）３０を、例えば４×４（Ｍ＝Ｎ＝４）個のブロック３１に分割する。なお、この分割数は、本実施形態において分類される複数の画像の全てにおいて同一であることが好ましいが、本発明においてはこの限りではなく、例えば、相対的に比例関係にある分割数（例えば、２×２、４×４、１６×１６等）であってもよい。その場合には、全てのブロックは、複数の画像のうち最も分割数の少ないブロックに分割されたブロック数（例えば、２×２、４×４、１６×１６の３つの画像が存在する場合には、２×２）に合わせて画像特徴を抽出する。
【００４４】
図２の例では、各ブロック３１に対して、色特徴を取得し、その色特徴から２つのクラスタ３２−１，３２−２に分類されている（なお、図２において、模様が異なるブロック領域が、それぞれ同一のクラスタを意味するものとし、以降の図についても同様とする）。
【００４５】
クラスタ分類手段１４では、各クラスタ（ブロック領域）に対して、それぞれ異なるフラグを付与する。なお、フラグの値として、図２の例では、クラスタ３２−１の各ブロックには「１」を付与し、クラスタ３２−２に各ブロックには「−１」を付与する。なお、本発明においてはこれに限定されるものではなく、例えば、上述とは逆にクラスタ３２−１には「−１」、クラスタ３２−２には「１」をそれぞれ付与してもよい。また、本発明におけるフラグの値については、これに限定されるものではない。つまり、クラスタ分類手段１４では、同一のクラスタに属する各ブロックでは同一で、各クラスタ間では異なるフラグが付与される。
【００４６】
＜類似度算出手段１５における具体的な類似度算出手法＞
次に、上述した類似算出手段１５における具体的な類似算出手法について説明する。類似度算出手段１５は、上述したクラスタ分類手段１４により得られる複数の画像に対する各クラスタにおいて、所属するブロック領域の画像特徴を平均し、クラスタの中心特徴を求める。なお、中心特徴とは、例えば同一のクラスタに含まれる各ブロックの色特徴等を平均したものであるが、本発明においてはこれに限定されるものではない。
【００４７】
ここで、類似度算出手段１５は、クラスタ分類手段１４によるクラスタ分類の結果、クラスタ数が１である場合に、各ブロック領域に対して、各ブロックの画像特徴と、当該クラスタの中心特徴との距離Ｄを求め、例えば以下に示す式（１）で与えられる類似度Ｓを計算する。
Ｓ＝１−（Ｄ／Ｄｍａｘ）  ・・・（１）
なお、上述した式（１）において、ＤｍａｘはＤの取り得る最大値を示す。
【００４８】
また、類似度算出手段１５は、クラスタ分類手段１４によるクラスタ分類の結果、クラスタ数が２である場合に、各ブロック領域について、自分が属するクラスタの中心特徴との距離Ｄ１と、属さない方のクラスタの中心特徴との距離Ｄ２を計算し、例えば以下に示す式（２）で与えられる類似度Ｓを計算する。
Ｓ＝１−（Ｄ１／Ｄ２）  ・・・（２）
なお、上述の例では、クラスタが１又は２の場合について説明したが、本発明においてはこれに限定されるものではなく、例えばクラスタが３つ以上の場合にも上述と同様にクラスタ数に応じて予め設定された数式等を用いて類似度を計算することができる。なお上述した数式については、これに限定されるものではない。
【００４９】
＜構図データ生成手段１６における具体的な構図データ生成例＞
次に、上述した構図データ生成手段１６における具体的な構図データ生成例について説明する。構図データ生成手段１６は、例えば、各ブロックに付与されているフラグ（例えば、整数フラグ「１」、「−１」）に、計算済みの類似度Ｓを乗算して実数値に変換する。
【００５０】
ここで、図３は、本実施形態における実数値の設定方法を示す図である。なお、説明の便宜上、図３に示すクラスタ構成は、上述した図２と同様のものとする。
【００５１】
本実施形態では、図３（ａ）に示すように、クラスタ３２−１及びクラスタ３２−２が存在する場合、まず上述したように類似度算出手段１５が、クラスタ３２−１に対してフラグ「１」のブロック群の中心特徴Ｃ１、及び、クラスタ３２−２に対してフラグ「−１」のブロック群の中心特徴Ｃ−１を算出する。また、類似度算出手段１５は、各ブロックの画像特徴Ｃ１からの距離、及びＣ−１からの距離に基づいて、類似度Ｓを算出する。
【００５２】
次に、構図データ生成手段１６は、フラグの数値に上述した類似度Ｓを乗算して、図３（ｂ）に示すように各ブロックを実数値に変換する。構図データ生成手段１６は、このようにして各ブロック領域に割り当てられた実数値を含む画像の構図データを出力する。なお、これらのデータは、蓄積手段１３に蓄積されてもよく、外部装置に出力してもよい。
【００５３】
＜構図データクラスタリング手段１７における具体的な構図データのクラスタリング手法＞
次に、構図データクラスタリング手段１７における具体的な構図データのクラスタリング手法について説明する。図４は、構図データクラスタリングの一例を示す図である。
【００５４】
本実施形態では、蓄積手段１３に蓄積されている基となる複数の画像（原画像）に上述した処理を施し、構図データを生成する。次に、構図データクラスタリング手段１７は、生成した構図データの集合を構図データ毎の類似度ＳＳの値に基づいて、類似性の高い構図データを有する画像がグループ化されるようにをクラスタリングし、１又は複数の構図グループを生成する。
【００５５】
ここで、例えば、２つの構図データであるＢ１＝（ｂ１（１，１），・・・，ｂ１（Ｍ，Ｎ））と、Ｂ２＝（ｂ２（１，１），・・・，ｂ２（Ｍ，Ｎ））（なお、（ｉ，ｊ）はブロック位置を示し、各ｂ１（ｉ，ｊ），ｂ２（ｉ，ｊ）は実数値を示す）との類似度ＳＳ（Ｂ１，Ｂ２）は、例えば以下に示す式（３）のように定義することができる。
【００５６】
【数１】
0005572120.tif 000002
ここで、構図データクラスタリング手段１７は、図４に示す全体の構図データの集合４０から、上述した類似度ＳＳ等によりクラスタリングされた構図グループ４１のうち、例えば要素数（画像数）が予め設定された値よりも少ない場合には、その構図グループを切り捨てる。また、構図データクラスタリング手段１７は、切り捨てられずに残った各構図グループ４１−１〜４１−ｎにおいて、その構図グループ毎に所属する要素の平均構図データを求め、各クラスタの平均構図データを主要構図データ（構図テンプレート）４２−１〜４２−ｎとして出力する。
【００５７】
ここで、図５は、構図グループと、主要構図データとの関係を説明するための図である。図５の例では、構図グループ４１−１〜４１−５等を有し、更に構図グループ４１−１〜４１−５に対応する構図テンプレート４２−１〜４２−５が示されているが、本発明におけるグループ数についてはこれに限定されるものではない。
【００５８】
なお、図５の例において、構図テンプレート４２−１は、クラスタ数が１の場合を示し、構図テンプレート４２−２〜４２−５は、クラスタ数が２の場合を示しているが、本発明においてはこれに限定されるものではなく、例えばクラスタ数が３つ以上存在する構図テンプレートがあってもよい。
【００５９】
更に、本実施形態では、例えば１つの構図グループの中でも更に細分化した構図サブグループを生成してもよい。図６は、構図サブグループの一例を示す図である。
【００６０】
図６に示すように、１つの構図グループ４１の中に複数の構図サブグループ（図６の例では、構図サブグループ４３−１，４３−２）を形成しておく。これらの構図サブグループは、例えば、構図テンプレートに含まれるクラスタ毎の画像特徴のばらつき度合いやクラスタ同士の分離度合い等によって、構図グループを細分化して構図サブグループを生成することができる。なお、細分化される構図サブグループは、各構図サブグループ間の関連性に基づいて、ツリー状に構成されていてもよい。これにより、検索に用いられる構図グループをサブグループ単位に細分化し、更にツリーに対応させて優先度等を設定することで、より効率的な検索を実現することができる。
【００６１】
上述したように、本実施形態では、構図データや構図テンプレートを生成しておくことで、実際に画像検索を行う際、画像の構図に基づいて効率的に高精度な構図データ生成を実現することができる。具体的には、本実施形態によれば、例えば、ウェブ上や画像サーバ等の大容量記憶媒体内等に存在する大量の画像データを、構図データや典型的な構図データ（構図テンプレート）に基づいて事前分類することにより、検索対象である画像の枚数を制限することができるため、検索を高速化することができる。
【００６２】
また、本実施形態では、このような検索装置に適用される構図テンプレートを人手でなく、構図データ生成装置により自動でセットすることが可能となり、更に構図テンプレートに含まれる各領域（各クラスタ）の画像特徴のばらつき度合いや領域同士の分離度合いを検索等に反映させることが可能となる。
【００６３】
＜検索手段１９における検索例＞
次に、検索手段１９における検索例について説明する。図７は、本実施形態における検索例を示す図である。図７に示す例において、検索手段１９は、検索対象画像５０を入力すると、蓄積手段１３に蓄積されている複数の画像の中から、検索対象画像５０に類似する画像を検索するため、まず上述したように所定の数又は大きさのブロックに分割する。なお、ブロック数は、例えば構図テンプレート４２に含まれるブロック数であることが好ましい。また、検索手段１９は、分割したブロックに対して所定のブロック数に基づいて、構図データを生成する。
【００６４】
なお、これらの処理は、上述するクラスタ分類手段１４や構図データ生成手段１６における処理と同様である。そのため、検索手段１９は、クラスタ分類手段１４や構図データ生成手段１６を用いて、検索対象画像５０から構図データ５１を生成してもよい。つまり、クラスタ分類手段１４は、検索手段１９から得られる検索対象画像に対してクラスタ分類を行う機能等を有し、構図データ生成手段１６は、検索対象画像に対する構図データを生成し、検索手段１９に出力する機能等を有する。
【００６５】
次に、検索手段１９は、検索対象画像の構図データと、各構図テンプレートとに基づいて類似度（構図類似度）を計算する。なお、ここでの類似度の計算手法については、例えば、クラスタに含まれる全てのブロックのうち、フラグ（実数値）が同じ値となるブロック領域の割合を用いて類似度を算出することができる。
【００６６】
また、検索手段１９は、類似度が最大になる構図テンプレートを特定する（例えば、図７の例では、構図テンプレート４２−４）。なお、類似度に基づくテンプレートの特定方法については、これに限定されるものではなく、例えば計算した類似度が閾値以上となる複数の構図テンプレートを特定してもよい（例えば、図７の例では、構図テンプレート４２−４，４２−２等）。
【００６７】
次に、検索手段１９は、上述にて得られた構図テンプレートに対応する構図グループ（例えば、図７の例では、構図グループ４１−４）に含まれる画像（構図データ）群を用いて、検索対象画像と色特徴等による類似度検索を行い、類似度の高い所定数の画像を検索結果として出力する。なお、構図グループに含まれる各画像との類似度検索については、例えば上述したように、画像中の各ブロックに設定した実数値等を含む構図データに基づいて類似度を判断することができる。
【００６８】
つまり、本実施形態では、例えば、検索対象画像についても各ブロックに付与したフラグを実数値に変換し、変換した実数値と、構図テンプレートや構図グループに含まれる各画像に付与された各ブロックにおける実数値とを比較することで、値の近いブロックの数に応じて類似構図テンプレートや類似画像を取得することができる。これにより、構図テンプレートに含まれる各領域（各クラスタ）の画像特徴のばらつき度合いや領域同士の分離度合いを検索等に反映させることが可能となる。
【００６９】
なお、上述した検索手段１９は、構図データ生成装置１０に設けられていなくてもよく別体に設けられていてもよい。また、上述した検索手段１９における検索手法は、例えば、本出願人により出願された特願２０１０−１８３７９１号（出願日：平成２２年８月１９日）に示されている技術を用いることもできる。
【００７０】
＜実行プログラム＞
ここで、上述した構図データ生成装置１０は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等の揮発性の記憶媒体、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）等の不揮発性の記憶媒体、マウスやキーボード、ポインティングデバイス等の入力装置、画像やデータを表示する表示装置、並びに外部と通信するためのインタフェース装置を備えたコンピュータによって構成することができる。
【００７１】
したがって、構図データ生成装置１０が有する上述した各機能は、これらの機能を記述したプログラムをＣＰＵに実行させることによりそれぞれ実現可能となる。また、これらのプログラムは、磁気ディスク（フロッピィーディスク、ハードディスク等）、光ディスク（Ｃ，Ｄ−ＲＯＭ、ＤＶＤ等）、半導体メモリ等の記録媒体に格納して頒布することもできる。
【００７２】
つまり、上述した各構成における処理をコンピュータに実行させるための実行プログラム（構図データ生成プログラム）を生成し、例えば汎用のパーソナルコンピュータやサーバ等にそのプログラムをインストールすることにより、構図データ生成処理を実現することができる。なお、本発明における実行プログラムによる処理については、例えば上述した各処理を実現することができる。
【００７３】
＜構図データ生成処理：構図データ生成＞
次に、上述した実行プログラム（構図データ生成プログラム）により実行される構図データ生成処理の具体例についてフローチャートを用いて説明する。
【００７４】
図８は、本実施形態における構図データ生成処理の一例を示すフローチャート（その１）である。なお、図８の例では、本実施形態における構図データの生成処理を示している。図８において、まず、入力される画像Ｉを所定数（例えば、Ｍ×Ｎ）のブロックに分割し（Ｓ０１）、Ｍ×Ｎに分割した全ブロック領域をその領域の画像特徴の類似度に基づいて、例えば、１クラスタ又は２クラスタに分類する（Ｓ０２）。
【００７５】
次に、同一のクラスタに属するブロック領域に同一のフラグ（例えば、−１又は１）を設定する（Ｓ０３）。なお、Ｓ０２の処理において、１クラスタに分類された場合、Ｓ０３の処理では後段の処理の容易性の観点から「１」を設定することが好ましい。
【００７６】
次に、クラスタ毎に、自分が属するブロック領域の画像特徴を平均し、クラスタの中心特徴を求める（Ｓ０４）。次に、クラスタ数が１であるか否かを判断し、（Ｓ０５）、クラスタ数が１である場合（Ｓ０５において、ＹＥＳ）、各ブロック領域に対して、その画像特徴とクラスタ中心特徴との距離Ｄを求め、所定の数式等により類似度Ｓを取得する（Ｓ０６）。なお、Ｓ０６の処理で取得する類似度Ｓは、例えば上述した式（１）を用いて算出することができる。
【００７７】
また、Ｓ０５の処理において、クラスタ数が１でない場合（Ｓ０５において、ＮＯ）、クラスタ数が２と判断し、各ブロック領域に対して、自分が属するクラスタの中心特徴との距離Ｄ１と、属さない方のクラスタの中心特徴との距離Ｄ２とを計算し、所定の数式等により類似度Ｓを取得する（Ｓ０７）。なお、Ｓ０７の処理で取得する類似度Ｓは、例えば上述した式（２）を用いて算出することができる。
【００７８】
Ｓ０６又はＳ０７の処理の終了後、各ブロック領域に対して、Ｓ０３の処理により既に設定されているフラグ（例えば、整数フラグ「１」又は「−１」）に、Ｓ０６又はＳ０７の処理により取得済みの類似度Ｓを乗算して実数値に変換する（Ｓ０８）。また、上述したＳ０８の処理により得られた結果から各ブロック領域に割り当てられた実数値を含む画像の構図データを出力する（Ｓ０９）。なお、この構図データは、蓄積手段１３等に蓄積される。また、上述の処理は、学習データとして複数の画像に対して実施される。
【００７９】
＜構図データ生成処理：構図テンプレート生成処理＞
図９は、本実施形態における構図データ生成処理の一例を示すフローチャート（その２）である。なお、図９の例では、上述した図９に示す処理により生成された構図データから、更に構図テンプレートを生成するまでの処理を示している。
【００８０】
図９において、まず、蓄積手段１３等から構図データの集合を類似度ＳＳに基づいてクラスタリングし、構図グループを生成する（Ｓ１１）。なお、Ｓ１１の処理では、例えば２つの構図データであるＢ１とＢ２との類似度ＳＳ（Ｂ１，Ｂ２）について、上述した式（３）等を用いて算出され、全ての構図データにおいて、上述の手法で得られた類似度が近い構図データ同士をグループ化して構図グループを生成する。
【００８１】
次に、Ｓ１１で生成した構図グループのうち、要素数（例えば、画像数）の少ない設定値以下の構図グループを切り捨てる（Ｓ１２）。これにより、構図テンプレートの枚数を制限することができ、検索処理における検索対象画像と構図テンプレートとの比較を迅速に行うことができる。
【００８２】
また、Ｓ１２の処理の後、残った構図グループに対して、自分が属する要素の平均構図データを取得し（Ｓ１３）、各クラスタの平均構図データを本データベースの構図テンプレート（主要構図データ）として出力する（Ｓ１４）。
【００８３】
＜構図データ生成処理：検索処理＞
次に、検索処理について説明する。なお、検索処理は、本実施形態における構図データ生成処理に含めてもよく、また独立したシステム又はソフトウェアとして構成されていてもよい。
【００８４】
図１０は、本実施形態における検索処理の一例を示すフローチャートである。図１０に示す例において、検索処理では、複数の構図テンプレートを読み出す（Ｓ２１）。次に、検索処理では、検索対象画像である画像Ｑを入力し（Ｓ２２）、画像ＱをＭ×Ｎに分割した各ブロックにフラグを付与する（Ｓ２３）。  
【００８５】
次に、検索処理では、画像Ｑのフラグと、Ｓ２１の処理により読み出した構図テンプレートのフラグとを用いて、画像Ｑと各構図テンプレートとの間の類似度（構図類似度）を算出し（Ｓ２４）、例えば、類似度が予め設定された閾値以上となる構図テンプレートを特定する（Ｓ２５）。  
【００８６】
また、検索処理では、画像Ｑを入力すると共に、Ｓ２５の処理により特定された構図テンプレートに含まれる構図グループに属する複数の画像Ｉを抽出する（Ｓ２６）。次に、検索処理では、画像ＱとＳ２６の処理により得られた複数の画像Ｉとの間の類似度を計算する（Ｓ２７）。このとき、検索処理では、例えば画像Ｑ及び複数の画像Ｉに対し、各画像を構成する所定画素毎のＲＧＢ値に基づいて、特徴量をそれぞれ計算し、両特徴量に基づいて類似度を計算することができるが、本発明においてはこれに限定されるものではない。  
【００８７】
次に、検索処理では、構図グループに属する全ての画像Ｉについて、処理が完了したか否かを判断し（Ｓ２８）、処理が完了していないと判断した場合（Ｓ２８において、ＮＯ）、Ｓ２７に戻り、次の画像について処理を行って、類似度を計算する。また、検索処理では、Ｓ２８の処理において、処理が完了したと判断した場合（Ｓ２８において、ＹＥＳ）、類似度が高い所定数の画像を検索結果として出力する（Ｓ２９）。
【００８８】
上述したように本発明によれば、画像の構図に基づいて効率的に高精度な構図データ生成を実現することができる。具体的には、本発明によれば、例えば、ウェブ上や大容量記憶媒体内等に存在する大量の画像データを、典型的な構図データ（構図テンプレート）に基づいて事前分類することにより検索を高速化することができる。また、構図テンプレートを人手でなく自動でセットすることが可能となり、更に構図テンプレートに含まれる各領域（各クラスタ）の画像特徴のばらつき度合いや領域同士の分離度合いを検索等に反映させることが可能となる。
【００８９】
以上本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形、変更が可能である。
【符号の説明】
【００９０】
１０  構図データ生成装置
１１  入力手段
１２  出力手段
１３  蓄積手段
１４  クラスタ分類手段
１５  類似度算出手段
１６  構図データ生成手段
１７  構図データクラスタリング手段
１８  主要構図データ生成手段
１９  検索手段
２０  送受信手段
２１  制御手段
３０  画像（原画像）
３１  ブロック
３２  クラスタ
４０  集合
４１  構図グループ
４２  主要構図データ（構図テンプレート）
５０  検索対象画像
５１  構図データ
【図１】
0005572120.tif 000003
【図４】
0005572120.tif 000004
【図５】
0005572120.tif 000005
【図６】
0005572120.tif 000006
【図８】
0005572120.tif 000007
【図９】
0005572120.tif 000008
【図１０】
0005572120.tif 000009
【図２】
0005572120.tif 000010
【図３】
0005572120.tif 000011
【図７】
0005572120.tif 000012