(57)【要約】  画像データベース５１の複数の画像データのそれぞれについて、画像全体の特徴量を算出するとともに、画像データのエッジを検出し、検出されたエッジ部分の特徴量を算出する特徴量算出部１１と、画像全体における特徴量に基づいて、複数の画像データを複数のクラスタに分類する第１のクラスタリング部１２と、エッジ部分の特徴量に基づいて、第１のクラスタリング部１２によって分類された複数のクラスタを、更に複数のクラスタに分類する第２のクラスタリング部１３と、複数の画像データのそれぞれについて画像の構図から被写体を構成する画素を決定し、第２のクラスタリング部１３によって分類された複数のクラスタを、被写体を構成する画素に基づいて統合するクラスタ統合部１４を備える。
2009072466.tif 000002
【特許請求の範囲】
【請求項１】
複数の画像データを、類似した画像毎に分類する画像分類装置であって、
複数の画像データが記憶された画像データベースと、
前記複数の画像データのそれぞれについて、画像全体の特徴量を算出するとともに、前記画像データのエッジを検出し、検出されたエッジ部分の特徴量を算出する特徴量算出部と、
前記画像全体における特徴量に基づいて、前記複数の画像データを複数のクラスタに分類する第１のクラスタリング部と、
前記エッジ部分の前記特徴量に基づいて、前記第１のクラスタリング部によって分類された複数のクラスタを、更に複数のクラスタに分類する第２のクラスタリング部と、
前記複数の画像データのそれぞれについて画像の構図から被写体を構成する画素を決定し、前記第２のクラスタリング部によって分類された複数のクラスタを、前記被写体を構成する画素に基づいて統合するクラスタ統合部
とを備える画像分類装置。
【請求項２】
前記複数の画像データについてそれぞれのサムネイルを任意に配置し、前記画像データの前記画像全体の特徴量、前記エッジ部分の特徴量、前記被写体を構成する画素の特徴量および前記クラスタ統合部１４により決定された前記画像データのクラスタに基づいて、前記各サムネイルの座標を更新して表示するとともに、前記各サムネイルの移動量を計算し、前記各サムネイルの移動量が０に収束するまで、座標を更新して表示する処理を繰り返す表示部
を更に備える請求項１に記載の画像分類装置。
【請求項３】
前記特徴量算出部は、前記複数の画像データのそれぞれについて、前記画像データにおける輝度値に基づいて、前記画像全体における色コリログラムを算出し、他の画像データの画像全体との色コリログラムの距離を、前記画像全体の特徴量として算出するとともに、前記エッジ部分における色コリログラムを算出し、他の画像データのエッジ部分との色コリログラムの距離を、前記エッジ部分の特徴量として算出する
請求項１に記載の画像分類装置。
【請求項４】
前記第１のクラスタリング部は、前記画像全体における特徴量に基づいて、全ての前記クラスタによるクラスタリング誤差が閾値内になるように、前記クラスタの数と、前記クラスタに属する画像データを決定する
請求項１に記載の画像分類装置。
【請求項５】
前記第２のクラスタリング部は、前記エッジ部分の前記特徴量に基づいて、前記第１のクラスタリング部によって分類された各クラスタのクラスタ内誤差が閾値内になるように、前記クラスタの数と、前記クラスタに属する画像データを決定する
請求項１に記載の画像分類装置。
【請求項６】
前記クラスタ統合部は、前記画像データに任意の境界線を設け、前記境界線によって得られる第１の領域と第２の領域における色ヒストグラム間の距離を算出し、前記境界線を動かすことによって前記色ヒストグラム間の距離が大きく変化する境界線を、構図を決定するための境界線とし、該境界線外を構成する画素の代表色との色差が閾値よりも大きな画素を、前記被写体を構成している画素とする
請求項１に記載の画像分類装置。
【請求項７】
前記クラスタ統合部は更に、前記被写体を構成する画素の色コリログラムと色ヒストグラムを算出し、算出された色コリログラムと色ヒストグラムに基づいて、前記第２のクラスタリング部によって分類された複数のクラスタのうち、任意の２つのクラスタの非類似度が、閾値よりも高くなるまで、クラスタの統合を繰り返す
請求項６に記載の画像分類装置。
【請求項８】
クエリ画像データの特徴ベクトルを算出するクエリ画像特徴量算出部と、
前記クエリ画像データの前記特徴ベクトルに基づいて、前記クラスタ統合部により生成されたクラスタから、前記クエリ画像データの所属するクラスタを決定するクラスタ決定部
とを備える請求項１に記載の画像分類装置。
【請求項９】
前記特徴ベクトルは、画像全体における色コリログラムと、エッジ部分の色コリログラムと、被写体領域の色ヒストグラムと色コリログラムをパラメータとして有し、
前記クエリ画像特徴量算出部は、前記クエリ画像データの前記画像全体における色コリログラムと、前記クエリ画像データの前記エッジ部分の色コリログラムと、前記クエリ画像データの前記被写体領域の色ヒストグラムと色コリログラムを算出して、前記クエリ画像データの特徴ベクトルを算出する
請求項８に記載の画像分類装置。
【請求項１０】
前記クラスタ決定部は、前記クラスタ統合部により生成された各クラスタに属する画像データの特徴ベクトルの平均を算出し、前記クエリ画像データの特徴ベクトルとの距離を最小とするクラスタをクエリ画像の所属クラスタとする
請求項９に記載の画像分類装置。
【請求項１１】
複数の画像データを、類似した画像毎に分類する画像分類プログラムであって、
コンピュータを、
画像データベースに記憶された複数の画像データのそれぞれについて、画像全体の特徴量を算出するとともに、前記画像データのエッジを検出し、検出されたエッジ部分の特徴量を算出する特徴量算出手段と、
前記画像全体における特徴量に基づいて、前記複数の画像データを複数のクラスタに分類する第１のクラスタリング手段と、
前記エッジ部分の前記特徴量に基づいて、前記第１のクラスタリング手段によって分類された複数のクラスタを、更に複数のクラスタに分類する第２のクラスタリング手段と、
前記複数の画像データのそれぞれについて画像の構図から被写体を構成する画素を決定し、前記第２のクラスタリング手段によって分類された複数のクラスタを、前記被写体を構成する画素に基づいて統合するクラスタ統合手段
として機能させる画像分類プログラム。
【請求項１２】
前記複数の画像データについてそれぞれのサムネイルを任意に配置し、前記画像データの前記画像全体の特徴量、前記エッジ部分の特徴量および前記被写体を構成する画素の特徴量に基づいて、前記各サムネイルの座標を更新して表示するとともに、前記各サムネイルの移動量を計算し、前記各サムネイルの移動量が０に収束するまで、座標を更新して表示する処理を繰り返す表示手段
として、更に前記コンピュータを機能させる請求項１１に記載の画像分類プログラム。
【請求項１３】
前記特徴量算出手段は、前記複数の画像データのそれぞれについて、前記画像データにおける輝度値に基づいて、前記画像全体における色コリログラムを算出し、他の画像データの画像全体との色コリログラムの距離を、前記画像全体の特徴量として算出するとともに、前記エッジ部分における色コリログラムを算出し、他の画像データのエッジ部分との色コリログラムの距離を、前記エッジ部分の特徴量として算出する
請求項１１に記載の画像分類プログラム。
【請求項１４】
前記第１のクラスタリング手段は、前記画像全体における特徴量に基づいて、全ての前記クラスタによるクラスタリング誤差が閾値内になるように、前記クラスタの数と、前記クラスタに属する画像データを決定する
請求項１１に記載の画像分類プログラム。
【請求項１５】
前記第２のクラスタリング手段は、前記エッジ部分の前記特徴量に基づいて、前記第１のクラスタリング手段によって分類された各クラスタのクラスタ内誤差が閾値内になるように、前記クラスタの数と、前記クラスタに属する画像データを決定する
請求項１１に記載の画像分類プログラム。
【請求項１６】
前記クラスタ統合手段は、前記画像データに任意の境界線を設け、前記境界線によって得られる第１の領域と第２の領域における色ヒストグラム間の距離を算出し、前記境界線を動かすことによって前記色ヒストグラム間の距離が大きく変化する境界線を、構図を決定するための境界線とし、該境界線外を構成する画素の代表色との色差が閾値よりも大きな画素を、前記被写体を構成している画素とする
請求項１１に記載の画像分類プログラム。
【請求項１７】
前記クラスタ統合手段は更に、前記被写体を構成する画素の色コリログラムと色ヒストグラムを算出し、算出された色コリログラムと色ヒストグラムに基づいて、前記第２のクラスタリング手段によって分類された複数のクラスタのうち、任意の２つのクラスタの非類似度が、閾値よりも高くなるまで、クラスタの統合を繰り返す
請求項１６に記載の画像分類プログラム。
【請求項１８】
クエリ画像データの特徴ベクトルを算出するクエリ画像特徴量算出手段と、
前記クエリ画像データの前記特徴ベクトルに基づいて、前記クラスタ統合手段により生成されたクラスタから、前記クエリ画像データの所属するクラスタを決定するクラスタ決定手段
として、更に前記コンピュータを機能させる請求項１１に記載の画像分類プログラム。
【請求項１９】
前記特徴ベクトルは、画像全体における色コリログラムと、エッジ部分の色コリログラムと、被写体領域の色ヒストグラムと色コリログラムをパラメータとして有し、
前記クエリ画像特徴量算出手段は、前記クエリ画像データの前記画像全体における色コリログラムと、前記クエリ画像データの前記エッジ部分の色コリログラムと、前記クエリ画像データの前記被写体領域の色ヒストグラムと色コリログラムを算出して、前記クエリ画像データの特徴ベクトルを算出する
請求項１８に記載の画像分類プログラム。
【請求項２０】
前記クラスタ決定手段は、前記クラスタ統合手段により生成された各クラスタに属する画像データの特徴ベクトルの平均を算出し、前記クエリ画像データの特徴ベクトルとの距離を最小とするクラスタをクエリ画像の所属クラスタとする
請求項１９に記載の画像分類プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の画像データを、分類する画像分類装置および画像分類プログラムに関する。
【背景技術】
【０００２】
近年、ディジタルカメラやイメージスキャナの普及、及び記録媒体の大容量化に伴い、ユーザが保持するディジタル画像の数は、急速に増加している。このような状況において、蓄積された大量の画像群から所望の画像を効率的に閲覧するために、画像検索技術の必要性が高まっている。代表的な検索手法として、ユーザの保持する検索要求画像（クエリ画像）とデータベース中に存在する画像との類似度に基づく手法がある（例えば、非特許文献１および非特許文献２参照）。これらの方法を用いることで、ユーザは、所望の画像をデータベースから取得することができる。【０００３】
また、クエリ画像に類似する画像を検索する方法として、クエリ画像と他の画像データとの画像間距離を計算して、画像間距離の小さいものから順に類似画像として抽出する画像検索装置がある（例えば、特許文献１参照）。上記特許文献１においては、クエリ画像を保持していなくとも、ユーザがクエリ画像を描画することにより、ユーザは、所望の画像を検索することができる。【０００４】
【特許文献１】特開２０００−１４８７９５号公報
【非特許文献１】M.J. Swain and D.H. Ballard, “Color indexing,” Int. J. Comput. Vision, vol.7, no.1, pp.11−32, 1991.
【非特許文献１】中川俊昭、原武史、藤田広志、“局所的なパターンマッチングによる画像検索法、” 信学論(D-II) , vol.J85-D-II, no.1, pp.149−152, Jan. 2002.
【発明の開示】
【０００５】
しかしながら、上記に記載した方法は、ユーザがクエリ画像を保持していることを前提としている。従って、クエリ画像を保持していない場合や、検索要求が不明確である場合、ユーザは、検索することが困難となる。特許文献１においては、ユーザがクエリ画像を描画するので、ユーザが上手く描画できない場合には、ユーザが所望の画像を検索することが困難になってしまう。また、ユーザが所望の画像が明確でない場合には、特許文献１に記載の方法を適用することはできない。
【０００６】
このような場合、サムネイル表示を用いてユーザにデータベース中に存在する全ての画像を提示することで、ユーザの画像検索作業が補助されていた。しかしながら、近年のデータベースの大規模化に伴い、データベース中に存在する全ての画像を一画面に表示することができなくなっている。その結果、サムネイル表示により画像検索の補助することは困難となっている。
【０００７】
したがって、データベース中に存在する画像を自動で分類し、ユーザに分類結果を効果的に提示する技術が必要となる。すなわち、データベース中の画像を事前に類似した画像群に分類し、その分類結果を提示することで、ユーザはデータベースに含まれる画像を直観的に把握することができる。これにより、クエリ画像を保持していない場合や明確な検索意図が存在しない場合にも、ユーザが効率的に画像の検索することのできる技術が期待されている。
【０００８】
従って本発明の目的は、複数の画像データを類似した画像毎に分類する画像分類装置および画像分類プログラムを提供することである。
【０００９】
上記課題を解決するために、本発明の第１の特徴は、複数の画像データを、類似した画像毎に分類する画像分類装置に関する。即ち本発明の第１の特徴に係る画像分類装置は、複数の画像データが記憶された画像データベースと、複数の画像データのそれぞれについて、画像全体の特徴量を算出するとともに、画像データのエッジを検出し、検出されたエッジ部分の特徴量を算出する特徴量算出部と、画像全体における特徴量に基づいて、複数の画像データを複数のクラスタに分類する第１のクラスタリング部と、エッジ部分の特徴量に基づいて、第１のクラスタリング部によって分類された複数のクラスタを、更に複数のクラスタに分類する第２のクラスタリング部と、複数の画像データのそれぞれについて画像の構図から被写体を構成する画素を決定し、第２のクラスタリング部によって分類された複数のクラスタを、被写体を構成する画素に基づいて統合するクラスタ統合部とを備える。
【００１０】
このような第１の特徴に係る画像分類装置によれば、画像中の色とその分布に着目し、多段階に処理することで、高精度な画像の分類を実現することができる。具体的には、画像全体の特徴量に基づいて第１のクラスタリング部によるクラスタリングをした後、精度を上げるために、画像中の重要な特徴であるエッジに着目して、第２のクラスタリング部によるクラスタリング処理する。さらに、過分割による影響を抑制するため、画像データ中の被写体から得られた特徴量に基づいて、クラスタを統合する。本発明の第１の特徴に係る画像分類装置は、まず画像全体の特徴量に基づいて大まかに分類する。次に、画像を特徴付けるエッジ部分に注目して、更に階層的に詳細に分類する。更に、各分類により過分割されたクラスタを、被写体の特徴に基づいて、被写体ごとに統合する。最後に被写体に基づいてクラスタを統合することにより、ユーザの検索キーワードに合致しやすいクラスタを生成できる。
【００１１】
ここで、複数の画像データについてそれぞれのサムネイルを任意に配置し、画像データの画像全体の特徴量、エッジ部分の特徴量、被写体を構成する画素の特徴量およびクラスタ統合部１４により決定された画像データのクラスタに基づいて、各サムネイルの座標を更新して表示するとともに、各サムネイルの移動量を計算し、各サムネイルの移動量が０に収束するまで、座標を更新して表示する処理を繰り返す表示部を備えても良い。
【００１２】
このような画像分類装置によれば、画像データベース中の画像データを直観的に把握することができるので、クエリ画像を保持していない場合や、明確な検索意図が存在しない場合においても、所望する画像データを検索することが可能となる。
【００１３】
ここで、特徴量算出部は、複数の画像データのそれぞれについて、画像データにおける輝度値に基づいて、画像全体における色コリログラムを算出し、他の画像データの画像全体との色コリログラムの距離を、画像全体の特徴量として算出するとともに、エッジ部分における色コリログラムを算出し、他の画像データのエッジ部分との色コリログラムの距離を、エッジ部分の特徴量として算出する。
【００１４】
これによれば、画像データ中の色の量だけではなく、空間的な分布も考慮して、画像データの特徴量を算出することができる。
【００１５】
また、第１のクラスタリング部は、画像全体における特徴量に基づいて、全てのクラスタによるクラスタリング誤差が閾値内になるように、クラスタの数と、クラスタに属する画像データを決定する。第２のクラスタリング部は、エッジ部分の特徴量に基づいて、第１のクラスタリング部によって分類された各クラスタのクラスタ内誤差が閾値内になるように、クラスタの数と、クラスタに属する画像データを決定する。
【００１６】
このように、多段階にクラスタリングすることにより、高精度のクラスタリングを実行することができる。
【００１７】
クラスタ統合部は、画像データに任意の境界線を設け、境界線によって得られる第１の領域と第２の領域における色ヒストグラム間の距離を算出し、境界線を動かすことによって色ヒストグラム間の距離が大きく変化する境界線を、構図を決定するための境界線とし、該境界線外を構成する画素の代表色との色差が閾値よりも大きな画素を、被写体を構成している画素とする。ここで、クラスタ統合部は更に、被写体を構成する画素の色コリログラムと色ヒストグラムを算出し、算出された色コリログラムと色ヒストグラムに基づいて、第２のクラスタリング部によって分類された複数のクラスタのうち、任意の２つのクラスタの非類似度が、閾値よりも高くなるまで、クラスタの統合を繰り返す。
【００１８】
このように、被写体における特徴量が類似しているクラスタを統合することにより、過分割を抑制し、ユーザに把握させやすい画像分類を実現することができる。
【００１９】
クエリ画像データの特徴ベクトルを算出するクエリ画像特徴量算出部と、クエリ画像データの特徴ベクトルに基づいて、クラスタ統合部により生成されたクラスタから、クエリ画像データの所属するクラスタを決定するクラスタ決定部とを備えても良い。
【００２０】
このような画像分類装置によれば、複数の画像データから、類似する画像を抽出することができる。
【００２１】
具体的には、特徴ベクトルは、画像全体における色コリログラムと、エッジ部分の色コリログラムと、被写体領域の色ヒストグラムと色コリログラムをパラメータとして有する。ここで、クエリ画像特徴量算出部は、クエリ画像データの画像全体における色コリログラムと、クエリ画像データのエッジ部分の色コリログラムと、クエリ画像データの被写体領域の色ヒストグラムと色コリログラムを算出して、クエリ画像データの特徴ベクトルを算出する。また、クラスタ決定部は、クラスタ統合部により生成された各クラスタに属する画像データの特徴ベクトルの平均を算出し、クエリ画像データの特徴ベクトルとの距離を最小とするクラスタをクエリ画像の所属クラスタとする。
【００２２】
本発明の第２の特徴は、複数の画像データを、類似した画像毎に分類する画像分類プログラムに関する。即ち本発明の第２の特徴に係る画像分類プログラムは、コンピュータを、画像データベースに記憶された複数の画像データのそれぞれについて、画像全体の特徴量を算出するとともに、画像データのエッジを検出し、検出されたエッジ部分の特徴量を算出する特徴量算出手段と、画像全体における特徴量に基づいて、複数の画像データを複数のクラスタに分類する第１のクラスタリング手段と、エッジ部分の特徴量に基づいて、第１のクラスタリング手段によって分類された複数のクラスタを、更に複数のクラスタに分類する第２のクラスタリング手段と、複数の画像データのそれぞれについて画像の構図から被写体を構成する画素を決定し、第２のクラスタリング手段によって分類された複数のクラスタを、被写体を構成する画素に基づいて統合するクラスタ統合手段として機能させる。
【００２３】
ここで、複数の画像データについてそれぞれのサムネイルを任意に配置し、画像データの画像全体の特徴量、エッジ部分の特徴量および被写体を構成する画素の特徴量に基づいて、各サムネイルの座標を更新して表示するとともに、各サムネイルの移動量を計算し、各サムネイルの移動量が０に収束するまで、座標を更新して表示する処理を繰り返す表示手段として、更にコンピュータを機能させても良い。
【００２４】
特徴量算出手段は、複数の画像データのそれぞれについて、画像データにおける輝度値に基づいて、画像全体における色コリログラムを算出し、他の画像データの画像全体との色コリログラムの距離を、画像全体の特徴量として算出するとともに、エッジ部分における色色コリログラムを算出し、他の画像データのエッジ部分との色コリログラムの距離を、エッジ部分の特徴量として算出しても良い。ここでは、色コリログラムに基づいて特徴量を算出する場合について説明するが、色コリログラムと色ヒストグラムを用いて特徴量を算出しても良い。
【００２５】
第１のクラスタリング手段は、画像全体における特徴量に基づいて、全てのクラスタによるクラスタリング誤差が閾値内になるように、クラスタの数と、クラスタに属する画像データを決定しても良い。第２のクラスタリング手段は、エッジ部分の特徴量に基づいて、第１のクラスタリング手段によって分類された各クラスタのクラスタ内誤差が閾値内になるように、クラスタの数と、クラスタに属する画像データを決定しても良い。
【００２６】
クラスタ統合手段は、画像データに任意の境界線を設け、境界線によって得られる第１の領域と第２の領域における色ヒストグラム間の距離を算出し、境界線を動かすことによって色ヒストグラム間の距離が大きく変化する境界線を、構図を決定するための境界線とし、該境界線外を構成する画素の代表色との色差が閾値よりも大きな画素を、被写体を構成している画素としても良い。ここで、クラスタ統合手段は更に、被写体を構成する画素の色コリログラムと色ヒストグラムを算出し、算出された色コリログラムと色ヒストグラムに基づいて、第２のクラスタリング手段によって分類された複数のクラスタのうち、任意の２つのクラスタの非類似度が、閾値よりも高くなるまで、クラスタの統合を繰り返しても良い。
【００２７】
また、クエリ画像データの特徴ベクトルを算出するクエリ画像特徴量算出手段と、クエリ画像データの特徴ベクトルに基づいて、クラスタ統合手段により生成されたクラスタから、クエリ画像データの所属するクラスタを決定するクラスタ決定手段として、更にコンピュータを機能させても良い。
【００２８】
ここで、特徴ベクトルは、画像全体における色コリログラムと、エッジ部分の色コリログラムと、被写体領域の色ヒストグラムと色コリログラムをパラメータとして有し、クエリ画像特徴量算出手段は、クエリ画像データの画像全体における色コリログラムと、クエリ画像データのエッジ部分の色コリログラムと、クエリ画像データの被写体領域の色ヒストグラムと色コリログラムを算出して、クエリ画像データの特徴ベクトルを算出しても良い。
【００２９】
クラスタ決定手段は、クラスタ統合手段により生成された各クラスタに属する画像データの特徴ベクトルの平均を算出し、クエリ画像データの特徴ベクトルとの距離を最小とするクラスタをクエリ画像の所属クラスタとしても良い。
【００３０】
本発明によれば、複数の画像データを類似した画像毎に分類する画像分類装置および画像分類プログラムを提供することができる。
【図面の簡単な説明】
【００３１】
【図１】図１は、本発明の最良の実施の形態に係る画像分類装置の機能ブロック図である。
【図２】図２は、本発明の最良の実施の形態に係る画像分類方法の概略を説明する図である。
【図３】図３は、本発明の最良の実施の形態に係る画像分類装置のハードウェア構成図である。
【図４】図４は、本発明の最良の実施の形態に係る画像分類装置の特徴量算出処理を説明するフローチャートである。
【図５Ａ】図５Ａは、本発明の最良の実施の形態に係る画像分類装置に用いられる色ヒストグラムと色コリログラムを説明する図である。（その１）
【図５Ｂ】図５Ｂは、本発明の最良の実施の形態に係る画像分類装置に用いられる色ヒストグラムと色コリログラムを説明する図である。（その２）
【図６】図６は、本発明の最良の実施の形態に係る画像分類装置において、第１のクラスタリング部と第２のクラスタリング部によるクラスタ分割を説明する図である。
【図７】図７は、本発明の最良の実施の形態に係る画像分類装置の第１のクラスタリング処理を説明するフローチャートである。
【図８】図８は、本発明の最良の実施の形態に係る画像分類装置の第２のクラスタリング処理を説明するフローチャートである。
【図９】図９は、本発明の最良の実施の形態に係る画像分類装置の第２のクラスタリング部において、Sobelフィルタによるエッジ強度の定義に用いられる画素の位置を説明する図である。
【図１０】図１０は、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合処理を説明するフローチャートである。
【図１１Ａ】図１１Ａは、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合部における構図を説明する図である。（その１）
【図１１Ｂ】図１１Ｂは、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合部における構図を説明する図である。（その２）
【図１１Ｃ】図１１Ｃは、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合部における構図を説明する図である。（その３）
【図１１Ｄ】図１１Ｄは、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合部における構図を説明する図である。（その４）
【図１２Ａ】図１２Ａは、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合部における境界線Ｌ１を説明する図である。
【図１２Ｂ】図１２Ｂは、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合部における境界線Ｌ２を説明する図である。
【図１２Ｃ】図１２Ｃは、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合部における境界線Ｌ３を説明する図である。
【図１２Ｄ】図１２Ｄは、本発明の最良の実施の形態に係る画像分類装置のクラスタ統合部における境界線Ｌ４を説明する図である。
【図１３】図１３は、本発明の最良の実施の形態に係る画像分類装置の表示処理を説明するフローチャートである。
【図１４】図１４は、本発明の最良の実施の形態に係る画像分類装置の表示部における透視変換を説明する図である。
【図１５】図１５は、本発明の最良の実施の形態に係る画像分類装置の表示部によって表示される初期画面の一例である。
【図１６】図１６は、本発明の最良の実施の形態に係る画像分類装置の表示部によって表示される結果画面の一例である。
【図１７Ａ】図１７Ａは、本発明の最良の実施の形態に係る画像分類装置の表示部におけるサムネイルの移動を説明する図である。（その１）
【図１７Ｂ】図１７Ｂは、本発明の最良の実施の形態に係る画像分類装置の表示部におけるサムネイルの移動を説明する図である。（その２）
【図１７Ｃ】図１７Ｃは、本発明の最良の実施の形態に係る画像分類装置の表示部におけるサムネイルの移動を説明する図である。（その３）
【図１８】図１８は、本発明の変形例に係る画像分類装置の機能ブロック図である。
【図１９】図１９は、本発明の変形例に係る画像分類方法の概略を説明する図である。
【図２０】図２０は、本発明の変形例に係る画像分類装置のクエリ画像特徴量算出処理を説明するフローチャートである。
【図２１】図２１は、本発明の変形例に係る画像分類装置の所属クラスタ決定処理を説明するフローチャートである。
【図２２】図２２は、本発明の変形例に係る画像分類装置の表示部によって表示される結果画面の一例である。
【発明を実施するための最良の形態】
【００３２】
次に、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。【００３３】
（最良の実施の形態）
本発明の最良の実施の形態に係る画像分類装置１は、複数の画像データを、類似した画像毎に分類する。本発明の最良の実施の形態に係る画像分類装置１は、画像データベース５１中に存在する画像データを類似した画像毎に分類し、得られる分類結果に基づいて画像を検索する。さらに、画像分類装置１は、分類、検索の結果を３次元空間上で可視化を行い、提示する。分類・検索結果を３次元空間上に配置することで、画像分類装置１は、空間的な距離により画像間の類似性を理解することが可能なユーザインターフェースを実現することができる。【００３４】
（画像分類装置の概要）
図２を参照して、本発明の最良の実施の形態に係る画像分類装置１の処理の概要を説明する。【００３５】
まず、ステップＳ１において、記憶装置１０７から、画像データベース５１の画像データが読み出される。次に、ステップＳ２において、ステップＳ１で読み出された画像データベースの各画像データについて、特徴量が算出される。この特徴量は、画像全体の画素から算出した特徴量と、画像におけるエッジ部分の画素から算出した特徴量を含む。【００３６】
次にステップＳ３ないしステップＳ５において、画像分類装置１は、抽出された特徴量に基づいて多段階にクラスタリングする。このとき画像分類装置１は、色や構造などに基づいて、画像を分類する。具体的には、ステップＳ３において画像分類装置１は、画像全体の色分布に係る特徴量に基づいて、複数の画像データを、複数のクラスタに分割する。更にステップＳ４において画像分類装置１は、画像のエッジ部分の色分布に係る特徴量に基づいて、ステップＳ３で分類されたクラスタを、更に分割する。ステップＳ５において画像分類装置１は、被写体部の色分布と、色の出現頻度に基づいて、ステップＳ４において過剰に分割されたクラスタを統合する。【００３７】
ステップＳ６において画像分類装置１は、画像データベース５１の各画像が分類された結果を、表示装置１０５に表示する。この際、各画像の特徴量と、ステップＳ３ないしステップＳ５の処理によるクラスタリング結果を用いて、画像分類装置１は、３次元空間上で分類結果を可視化する。【００３８】
本発明の最良の実施の形態に係る画像分類装置１の分類部１０は、画像中の色の分布に着目し、色コリログラムを用いてK-means法によるクラスタリングをする（ステップＳ３）。このとき得られる分類結果について画像分類装置１は、画像中のさらに詳細な色分布を考慮するため、エッジ画素を対象として算出した色コリログラムを用い、各クラスタを分割する（ステップＳ４）。ここで、エッジ画素とは、Sobelフィルタで取得したエッジであって、被写体のエッジとは限らない。このとき、過分割の影響を抑制するため、画像分類装置１は、被写体から得られた色ヒストグラムと色コリログラムを用いてクラスタの再統合処理を加える（ステップＳ５）。これらの各処理において特徴量間の距離を算出する際には、色コリログラム間の２次形式距離が用いられる。これにより得られる各画像の特徴量と所属するクラスタ情報を用いて、画像分類装置１は、表示部２０において、分類結果を３次元空間上で可視化する（ステップＳ６）。
ここで、ステップＳ３およびステップＳ４においては、色コリログラムのみを用いて処理する場合について説明したが、色ヒストグラムだけを用いても良いし、色コリログラムと色ヒストグラムを用いても良い【００３９】
（画像分類装置のハードウェア構成）
図３に示すように、本発明の最良の実施の形態に係る画像分類装置１は、中央処理制御装置１０１、ＲＯＭ（Read Only Memory）１０２、ＲＡＭ（Random Access Memory）１０３及び入出力インタフェース１０９を備える。これらは、バス１１０を介して接続されている。入出力インタフェース１０９には、入力装置１０４、表示装置１０５、通信制御装置１０６、記憶装置１０７及びリムーバブルディスク１０８が接続されている。【００４０】
中央処理制御装置１０１は、入力装置１０４からの入力信号に基づいてＲＯＭ１０２から画像分類装置１を起動するためのブートプログラムを読み出して実行する。中央処理制御装置１０１は、更に記憶装置１０７に記憶されたオペレーティングシステムを読み出す。更に中央処理制御装置１０１は、入力装置１０４や通信制御装置１０６などの入力信号に基づいて、各種装置の制御を行ったり、ＲＡＭ１０３や記憶装置１０７などに記憶されたプログラム及びデータを読み出してＲＡＭ１０３にロードする。また、中央処理制御装置１０１は、ＲＡＭ１０３から読み出されたプログラムのコマンドに基づいて、データの計算又は加工など、後述する一連の処理を実現する処理装置である。【００４１】
入力装置１０４は、操作者が各種の操作を入力するキーボード、マウスなどの入力デバイスにより構成されている。入力装置１０４は、操作者の操作に基づいて入力信号を作成し、入出力インタフェース１０９及びバス１１０を介して中央処理制御装置１０１に送信する。表示装置１０５は、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどである。表示装置１０５は、中央処理制御装置１０１からバス１１０及び入出力インタフェース１０９を介して表示装置１０５において表示させる出力信号を受信し、例えば中央処理制御装置１０１の処理結果などを表示する装置である。通信制御装置１０６は、ＬＡＮカードやモデムなどの装置である。通信制御装置０６は、画像分類装置１をインターネットやＬＡＮなどの通信ネットワークに接続する装置である。通信制御装置１０６を介して通信ネットワークと送受信したデータは入力信号又は出力信号として、入出力インタフェース１０９及びバス１１０を介して中央処理制御装置１０１に送受信される。【００４２】
記憶装置１０７は半導体記憶装置や磁気ディスク装置である。記憶装置１０７には、中央処理制御装置１０１で実行されるプログラムやデータが記憶されている。リムーバブルディスク１０８は、光ディスクやフレキシブルディスクのことである。ディスクドライブによって読み書きされた信号は、入出力インタフェース１０９及びバス１１０を介して中央処理制御装置１０１に送受信される。【００４３】
本発明の最良の実施の形態に係る画像分類装置１の記憶装置１０７には、画像分類プログラムが記憶されるとともに、画像データベース５１が記憶される。又、画像分類プログラムが画像分類装置１の中央処理制御装置１０１に読み込まれ実行されることによって、分類部１０および表示部２０が、画像分類装置１に実装される。【００４４】
（画像分類装置の機能ブロック）
図１に示すように、本発明の最良の実施の形態に係る画像分類装置１は、画像データベース５１、分類部１０および表示部２０を備える。分類部１０は、特徴量算出部１１、第１のクラスタリング部１２、第２のクラスタリング部１３およびクラスタ統合部１４を備える。【００４５】
画像データベース５１には、複数の画像データが記憶される。この画像データベースに記憶される画像データは、本発明の最良の実施の形態に係る画像分類装置１によって分類される対象となる。画像データデータベース５１には、各画像データについて、後述する処理によって算出される特徴量や、クラスタの識別子を含むクラスタの情報などが関連づけられても良い。【００４６】
特徴量算出部１１は、画像データベース５１に記憶された複数の画像データのそれぞれについて、画像全体の特徴量を算出する。さらに特徴量算出部１１は、画像データのエッジを検出し、検出されたエッジ部分の特徴量を算出する。ここで、特徴量算出部１１は、複数の画像データのそれぞれについて、画像データにおける輝度値に基づいて、色コリログラムを算出する。特徴量算出部１１は、他の画像データとの色コリログラムの距離を、特徴量として算出する。画像全体の画素から算出した特徴量は、画像におけるエッジ部分の画素から算出した特徴量と、画像全体の画素のうち、エッジ部分と排他な画素から算出した特徴量と、を加算することによって、算出されても良い。
ここで、本発明の特徴量算出部１１は、各画像データの色コリログラムに基づいて算出する場合について説明するが、色ヒストグラムを用いても良いし、色ヒストグラムと色コリログラムの二つを用いても良い。【００４７】
第１のクラスタリング部１２は、画像全体における特徴量に基づいて、複数の画像データを複数のクラスタに分類する。第１のクラスタリング部１２は、画像全体における特徴量に基づいて、全てのクラスタによるクラスタリング誤差が閾値内になるように、クラスタの数と、クラスタに属する画像データを決定する。【００４８】
第２のクラスタリング部１３は、エッジ部分の特徴量に基づいて、第１のクラスタリング部１２によって分類された複数のクラスタを、更に複数のクラスタに分類する。第２のクラスタリング部１３は、エッジ部分の特徴量に基づいて、第１のクラスタリング部１２によって分類された各クラスタのクラスタ内誤差が閾値内になるように、クラスタの数と、クラスタに属する画像データを決定する。【００４９】
クラスタ統合部１４は、複数の画像データのそれぞれについて画像の構図から被写体を構成する画素を決定し、第２のクラスタリング部１３によって分類された複数のクラスタを、被写体を構成する画素に基づいて統合する。クラスタ統合部１４は、画像データに任意の境界線を設け、境界線によって得られる第１の領域と第２の領域における色ヒストグラム間の距離を算出する。クラスタ統合部１４は、境界線を動かすことによって色ヒストグラム間の距離が大きく変化する境界線を、構図を決定するための境界線とする。ここでクラスタ統合部１４は、この境界線外を構成する画素の代表色との色差が閾値よりも大きな画素を、被写体を構成している画素とする。クラスタ統合部１４は更に、被写体を構成する画素の色コリログラムと色ヒストグラムを算出する。クラスタ統合部１４は、算出された色コリログラムと色ヒストグラムに基づいて、第２のクラスタリング部１３によって分類された複数のクラスタのうち、任意の２つのクラスタの非類似度が、閾値よりも高くなるまで、クラスタの統合を繰り返す。【００５０】
表示部２０は、分類部１０に依って分類された画像データを、表示装置１０５に可視的に表示する。表示部２０は、複数の画像データについてそれぞれのサムネイルを任意に配置する。更に表示部２０は、画像全体の特徴量、エッジ部分の特徴量、被写体を構成する画素の特徴量およびクラスタ統合部１４により決定された画像データのクラスタに基づいて、各サムネイルの座標を更新して表示するとともに、各サムネイルの移動量を計算する。表示部２０は、各サムネイルの移動量が０に収束するまで、座標を更新して表示する処理を繰り返す。表示部２０は、画像全体の色コリログラム、エッジ部分の色コリログラムおよび被写体領域における色コリログラムから、各画像データ間の距離を定義する。表示部２０は、この各画像データ間の距離に基づいて、サムネイルを移動させながら、表示装置１０５に表示する。本発明の最良の実施の形態においては、色コリログラムに基づいて各画像データ間の距離を算出する場合について説明するが、色ヒストグラムを用いても良いし、色ヒストグラムと色コリログラムの二つを用いても良い。【００５１】
（特徴量算出部）
本発明の最良の実施の形態に係る画像分類装置１は、カラー画像を分類の対象とし、画像中の色に基づく特徴を用いて画像を自動的に分類する。画像中の色を表現する特徴として、一般に色ヒストグラムが用いられる。しかしながら、色ヒストグラムを用いた場合、画像中の色の空間的な分布については考慮することができない。そこで、本発明の最良の実施の形態に係る画像分類装置１は、画像中の色の分布について考慮することが可能な特徴として、色コリログラムに着目する。色ヒストグラムに代えて、この色コリログラムを用いることで、色の空間的な分布の差異が考慮され、高精度な画像の自動分類が実現される。本発明の最良の実施の形態においては、色コリログラムに基づいて分類する場合について説明するが、色ヒストグラムを用いても良いし、色ヒストグラムと色コリログラムの二つを用いても良い。【００５２】
図４を参照して、特徴部算出部１１の処理について詳述する。図４に示す例では、色ヒストグラムおよび色コリログラムに基づいて特徴量を算出する場合について説明する。色コリログラムのみ用いて特徴量を算出する場合は、ステップＳ１０２ないしステップＳ１０４およびステップＳ１０７は割愛されても良い。
図４において、ステップＳ１０２ないしステップＳ１０４の処理は、各画像データの色ヒストグラムを算出する処理である。ステップＳ１０５ないしステップＳ１０７の処理は、各画像データの色コリログラムを算出する処理である。ステップＳ１０８およびステップＳ１０９は、ステップＳ１０４およびステップＳ１０５において取得された各画像データの色ヒストグラムおよび色コリログラムに基づいて、各画像データ間の色コリログラムおよび色ヒストグラムの距離を算出する。【００５３】
まず、特徴量算出部１１は、ステップＳ１０１ないしステップＳ１０７において、画像データベース５１に格納された各画像データについて、色ヒストグラムおよび色コリログラムを算出する。【００５４】
具体的には、ステップＳ１０１において、特徴量算出部１１は、画像データの各画素の輝度値を量子化する。ここでは、輝度値を基準に以下の処理を実行する場合について説明するが、ＲＧＢの各画素の値に基づいて処理されても良い。次にステップＳ１０２において、特徴量算出部１１は、ヒストグラムのビンに対して、画像データの各画素に対応する画素値の値に投票する。ステップＳ１０３において、特徴量算出部１１は、ステップＳ１０２で取得したヒストグラムを正規化し、総和を１とする。ステップＳ１０４において、特徴量算出部１１は、ステップＳ１０３により算出された値を、この画像データの色ヒストグラムとして取得する。【００５５】
次にステップＳ１０５において、特徴量算出部１１は、コリログラムのビンに対して、画像データの各画素に対応する画素値の値に投票する。ステップＳ１０６において、特徴量算出部１１は、ステップＳ１０５で取得したコリログラムを正規化し、総和を１とする。ステップＳ１０７において、特徴量算出部１１は、ステップＳ１０６により算出された値を、この画像データの色コリログラムとして取得する。【００５６】
次に、ステップＳ１０８において、特徴部算出部１１は、各画像データの色ヒストグラム間の２次形式距離を算出し、画像データベース５１に記憶する。更に、ステップＳ１０９において、特徴部算出部１１各画像データの色コリログラム間の２次形式距離を算出し、画像データベース５１に記憶する。例えば、画像データベース５１に、５０の画像データが格納されている場合、色ヒストグラム間の２次元形式距離および色コリログラム間の２次元形式距離は、それぞれ５０×４９／２個である。【００５７】
以下で、色ヒストグラム、及び色コリログラムの定義について説明する。
１．色ヒストグラム
色ヒストグラムは画像中に特定の色が出現する確率の分布により定義される。画像Iにおける各画素の色はc1, ・ ・ ・ , cm のｍ階調に量子化されているものとし、各画素p = (x, y) ∈ Iに対してI(p) をその画素の色とする。また、Ic = {p|I(p) = c} とする。このとき、画像Iの色ci に対する色ヒストグラムhci(I)は、次式により定義される。
【数１】
2009072466.tif 000003
このとき、Pr[p ∈ Ici ] は、画像I において色がci となる画素pの確率を示す。このようにして定義される色ヒストグラムを特徴として用いることで、画像中の色に着目した画像分類が可能となる。【００５８】
２．色コリログラム
色ヒストグラムが画像中に特定の色が出現する確率の分布として定義されるのに対し、色コリログラムは画像中の一定距離離れた画素間における特定の色の共起確率の分布として定義される。このことから、図５Ａおよび図５Ｂに示すように、色ヒストグラムと色コリログラムは異なる特徴を表す。具体的には、図５Ａに示すように、大きい円が一つだけある画像についても、図５Ｂに示すように小さい円が多数含まれている画像についても、同じ色ヒストグラムを有する。しかし、色コリログラムで表すことにより、図５Ａおよび図５Ｂの画像それぞれの特徴を示すことができる。【００５９】
以降、色コリログラムの定義について説明する。
画像I における各画素の色はc1, ・ ・ ・ , cm のｍ階調に量子化されているものとし、各画素p = (x, y) ∈ I に対してI(p) をその画素の色とする。また、Ic = {p|I(p) = c} とする。このとき、画像I の色ci，cj，距離k に対する色コリログラム
【数２】
2009072466.tif 000004
は、次式により定義される。
【数３】
2009072466.tif 000005
ここで、式２における２画素間の距離|p1 − p2| は、次式により定義される。
【数４】
2009072466.tif 000006
ただし、最良の実施の形態に係る画像分類装置１では、画素の周辺の局所領域における色の分布を考慮するため、式２を次式に置き換える。
【数５】
2009072466.tif 000007
【００６０】
このように、色コリログラムを特徴として用いることで、本発明の最良の実施の形態において画像分類装置１は、画像中の色の空間的な分布の差異を考慮することができる。また、画像分類装置１は、高精度に画像を自動的に分類することができる。【００６１】
本発明の最良の実施の形態において画像分類装置１は、以上の２つの特徴を分類対象画像より抽出し、各画像データに対するそれらの距離を定義する。さらに画像分類装置１は、定義された距離に基づき画像間の類似度を算出し、得られる類似度に基づいて画像を分類する。本発明の最良の実施の形態に係る画像分類装置１は、画像全体、エッジ、被写体と着目する領域を限定しながら特徴を算出し、多段階に処理することで、より高精度に画像を自動的に分類することができる。【００６２】
次に、特徴間の距離に基づく画像間の類似度の定義を説明する。
本発明の最良の実施の形態に係る画像分類装置１は、複数の画像データにおける、画像から算出した色ヒストグラム間、および色コリログラム間の距離を用いて、画像間の類似度を評価する。色ヒストグラム間の距離尺度としては様々なものが考えられるが、その中でも人間の知覚に近い距離尺度であることが報告されている２次形式距離を用いることで、適切な分類結果を得ることが可能となる。ただし、２次形式距離は色ヒストグラム間の距離として定義されており、そのままでは色コリログラム間の距離尺度としては用いることができない。そこで、本発明の最良の実施の形態に係る画像分類装置１は、色ヒストグラム間の２次形式距離の概念を拡張することで、色コリログラム間の距離を定義する。【００６３】
２つの色ヒストグラム間の２次形式距離は、各ビンの値を要素とするベクトルhi，hj を用いて次式により定義される。
【数６】
2009072466.tif 000008
式５におけるS = [sxy] は色類似度行列と呼ばれ、x 番目とy 番目のビンに対応する色の類似度として
【数７】
2009072466.tif 000009
で定義される。ただし、α は、正定数である。dxy は、x 番目のビンとy 番目のビンに対応する色のL*a*b表色系における色差である。本発明の最良の実施の形態に係る画像分類装置１は、色ヒストグラム間の距離として式５の２次形式距離を用いる。【００６４】
本発明の最良の実施の形態に係る画像分類装置１は、さらにこの色ヒストグラム間の２次形式距離の概念を拡張することで、色コリログラム間の距離尺度を定義する。色ヒストグラムの各ビンが単一の色に対応するのに対し、色コリログラムの各ビンは２つの色の組み合わせに対応する。従って式５における色類似度行列S をそのまま用いることはできない。そこで、本発明の最良の実施の形態に係る画像分類装置１は、 S = [sxy] を次式に示すように変更する。
【数８】
2009072466.tif 000010
【数９】
2009072466.tif 000011
ただし、色コリログラムのx 番目のビンとy 番目のビンは、それぞれ色x1, x2，および色y1, y2 の組み合わせに対応する。本発明の最良の実施の形態においては、色コリログラム間の距離は、各ビンの値を要素とするベクトルci，cj と
【数１０】
2009072466.tif 000012
を用いて次式により定義される。
【数１１】
2009072466.tif 000013
【００６５】
本発明の最良の実施の形態は、２次形式距離を算出する際、以下のように色ヒストグラムを変換することで計算量を削減する。まず、S の固有値分解がS = UΛUT で表される。ただし、Λ はS の固有値を降順に並べた対角行列、U は対応する固有ベクトルを並べた行列である。ここで、Λ の上位l 個の固有値を並べた対角行列Λl と対応する固有ベクトルを並べた行列Ul により、n 次元の色ヒストグラムhi，hj は、次式を用いてl 次元のベクトル
【数１２】
2009072466.tif 000014
に変換される。
【数１３】
2009072466.tif 000015
式１０より算出される
【数１４】
2009072466.tif 000016
を用い、hi，hj のl 次元空間上での距離は、次式により定義される。
【数１５】
2009072466.tif 000017
このとき、式５におけるDh(hi,hj) は、l 次元空間上の距離
【数１６】
2009072466.tif 000018
により近似することが可能である。本発明の最良の実施の形態では、この低次元での２次形式距離を用いて類似画像を分類する。色コリログラム間の２次形式距離の算出の際についても、色ヒストグラム間の２次形式距離算出と同様に、式９を次式で近似することにより、計算量が削減される。
【数１７】
2009072466.tif 000019
ただし、
【数１８】
2009072466.tif 000020
である。【００６６】
本発明の最良の実施の形態においては、画像分類装置１は、
【数１９】
2009072466.tif 000021
を特徴ベクトルとし、距離
【数２０】
2009072466.tif 000022
を用いて画像間の類似度を評価し、画像を分類する。【００６７】
（クラスタ処理部）
第１のクラスタリング部１２、第２のクラスタリング部１３およびクラスタ統合部１４について説明する。
本発明の最良の実施の形態は、画像中の色とその分布に着目し、多段階に処理することで、高精度な画像の自動分類を実現する。まずは画像中の色の分布に着目し、色コリログラム間の２次形式距離に基づくK-means 法により、画像が分類される。具体的には、画像分類装置１は、図６に示すように、画像データベース５１に記憶された画像データ群を、K-means 法により分類し、クラスタＣ１１、Ｃ１２、Ｃ１３およびＣ１４を生成する。【００６８】
しかしながら、K-means 法により得られる分類は、１枚の画像の特徴を１つの色コリログラムのみを用いて表現しているため、画像中のより詳細な特徴については考慮されていない。そのため、この時点では十分な分類精度が得られていない可能性がある。そこで、本発明の最良の実施の形態は、画像中のより詳細な特徴を用いて分類結果の高精度化を図ることで、より高精度な画像の自動分類を実現する。【００６９】
本発明の最良の実施の形態は、より詳細な特徴として、画像中の重要な特徴であるエッジに着目する。画像分類装置１は、画像よりエッジ画素の検出を行い、エッジ画素とその周囲の画素のみから算出された色コリログラムを用いて、既に得られている各クラスタを分割する。ここで、エッジ画素とは、Sobelフィルタで取得したエッジであって、被写体のエッジとは限らない。例えば画像分類装置１は、K-means 法により分割されたクラスタのうち、クラスタ内誤差が所定の閾値Ｔｈより大きいクラスタを更に分割する。図６に示す例では、クラスタ内誤差が所定の閾値Ｔｈより大きいクラスタは、クラスタＣ１１およびＣ１３であるので、画像分類装置１は、クラスタＣ１１を、それぞれクラスタＣ２１およびＣ２２に分割する。さらに画像分類装置１は、クラスタＣ１３を、クラスタＣ２３およびＣ２４に分割する。この結果得られたクラスタＣ２４のクラスタ内誤差が所定の閾値Ｔｈより大きいので、画像分類装置１は、さらにクラスタ２４を分割し、クラスタＣ３１およびクラスタＣ３２に分割する。このように画像分類装置１は、各クラスタのクラスタ内誤差が所定の閾値Ｔｈより小さくなるように、クラスタを分割する。これにより本発明の最良の実施の形態において、画像中のさらに詳細な色分布を考慮し、分類結果の高精度化が可能となる。【００７０】
ただし、このときクラスタを分割することにより過分割が発生してしまう危険性がある。そこで、画像分類装置１は、過分割の影響を抑制するため、被写体から得られた色ヒストグラムと色コリログラムを用いたクラスタの再統合処理を加える。これにより、画像分類装置１は、高精度に類似画像を分類することができる。具体的には、画像分類装置１は、分割結果のクラスタＣ２１、Ｃ２２、Ｃ１２、Ｃ２３、Ｃ３１、Ｃ３２およびＣ１４の７つのクラスタについて、同一の被写体を含むと考えられるクラスタを６つ以下のクラスタに統合する。
以降、各処理について詳細に述べる。【００７１】
（第１のクラスタリング部）
本発明の最良の実施の形態に係る第１のクラスタリング部１２は、Ｎ枚の分類対象画像fi(i = 1, ・ ・ ・ ,N) を複数の集合に分類するため、 K-means 法を用いてクラスタリングを行う。ここで、K-means法によるクラスタリングは、非階層型クラスタリング手法の一種である。【００７２】
図７を参照して、本発明の最良の実施の形態に係る第１のクラスタリング部１２による第１のクラスタリング処理を説明する。【００７３】
ステップＳ２０１において、第１のクラスタリング部１２は、最初にクラスタ数Ｋを１に設定する。次に、ステップＳ２０２において、第１のクラスタリング部１２は、クラスタ数をＫにするクラスタリングを行う。このとき、ステップＳ２０３において、第１のクラスタリング部１２は、全てのクラスタに対するクラスタリング誤差E(k)を算出する。【００７４】
ステップＳ２０４において、第１のクラスタリング部１２は、クラスタ数がＫ＝１の場合、ステップＳ２０５においてＫをインクリメントする。更に、ステップＳ２０２に戻り、第１のクラスタリング部１２は、クラスタ数をＫにするクラスタリングが行われる。【００７５】
一方ステップＳ２０４において、クラスタ数がＫ＝１でない場合、ステップＳ２０６において、第１のクラスタリング部１２は、現在のクラスタ数におけるクラスタリング誤差E(k)と、現在のクラスタ数より一つ少ないクラスタ数におけるクラスタリング誤差E(k-1)との差が、所定の閾値以上である場合、ステップＳ２０５においてＫをインクリメントする。更に、ステップＳ２０２に戻り、第１のクラスタリング部１２は、クラスタ数をＫにするクラスタリングを行う。【００７６】
一方、ステップＳ２０６において、所定の閾値以上でない場合、現在のクラスタ数の状態で、クラスタリング誤差が収束したとして、第１のクラスタリング部１２は、第１のクラスタリング処理を終了する。【００７７】
ここで、第１のクラスタリング部１２の処理を詳述する。
本発明の最良の実施の形態に係る第１のクラスタリング部１２は、K-means 法に用いる特徴ベクトルを生成する。第１のクラスタリング部１２は、各fi について、Ｒ、Ｇ、Ｂの輝度値をそれぞれm 階調に量子化し、距離k1 に対する色コリログラムを算出する。ここで、k1は予め与えられる値である。得られた色コリログラムに対し、式１３を適用することでl 次元ベクトルc’i を算出し、特徴ベクトルとする。以上の処理により得られた特徴ベクトルに対し、K-means 法を適用する。ただし、K-means 法はクラスタリング結果が初期クラスタ、およびクラスタ数により変化する。そこで、本発明の最良の実施の形態においては、クラスタリング結果を評価するため、次式により表されるクラスタリング誤差Ek を用いる。
【数２１】
2009072466.tif 000023
ただし、Ck、及びvk (k = 1, ・ ・ ・ ,K，K はクラスタ数) はk 番目のクラスタとその中心ベクトルを表す。本発明の最良の実施の形態においては、クラスタ数K をK = 1, 2, ・ ・ ・ と変化させる。第１のクラスタリング部１２は、、各クラスタについて初期値をランダムに変更しながらK-means 法をM 回適用する。第１のクラスタリング部１２は、EK の値が最小となる結果をクラスタ数K におけるクラスタリング結果とする。【００７８】
クラスタリングの終了判定には、スクリープロットの概念を用いる。スクリープロットは、主成分分析において主成分数を決定するために用いられ、第一主成分から順に固有値をプロットし、２点間の差分が小さくなる主成分数を採用するものである。本発明の最良の実施の形態においては、主成分数をクラスタ数、固有値をEk に対応づけ、|Ek−Ek-1| < THcl を満たす場合に現在の状態を、最終的なクラスタリング結果とする。【００７９】
（第２のクラスタリング部）
K-means 法を適用することにより得られた分類結果は、画像全体の色の分布に着目したものであるため、画像の詳細な特徴については考慮されていない。よって、異なる被写体を撮像した画像が、同一のクラスタに含まれる可能性がある。そこで、画像分類装置１は、より詳細な特徴を用いて各クラスタを分割することで、分類結果の高精度化を図る。具体的には、画像分類装置１は、画像の詳細な特徴としてエッジに着目し、エッジ画素と、エッジ画素を中心とする周辺の画素との色の関係を考慮することで、より高精度な分類結果を得る。ここで、エッジ画素とは、Sobelフィルタで取得したエッジであって、被写体のエッジとは限らない。また、周辺の画素とは、エッジ画素の座標を（ｘ，ｙ）としたとき、エッジ画素からの距離k2は、
【数２２】
2009072466.tif 000024
を満たす座標（ａ，ｂ）の画素である。ここでk2は、予め与えられるパラメータである。【００８０】
図８を参照して、本発明の最良の実施の形態に係る第２のクラスタリング部１３による第２のクラスタリング処理を説明する。【００８１】
まず、ステップＳ３０１において、第２のクラスタリング部１３は、画像データベース５１に記憶された全ての画像データに対し、Sobelフィルタを適用し、各画像データにおけるエッジ画像を取得する。ステップＳ３０２において、第２のクラスタリング部１３は、各画像データについて、ステップＳ３０１で取得したエッジ画像の色コリログラムを生成する。【００８２】
次に、ステップＳ３０３において、第２のクラスタリング部１３は、第１のクラスタリング部１２によって生成された各クラスタにおいて、クラスタ内誤差Ｅを算出する。このクラスタ内誤差Ｅは、クラスタに属する画像データについて、ステップＳ３０２で生成されたエッジ画像の色コリログラム間の２次形式距離に基づく。この各画像データのエッジ部分における色コリログラム間の２次元形式距離は、画像データベース５１に記憶されることが好ましい。【００８３】
ステップＳ３０４において、第２のクラスタリング部１３は、全てのクラスタにおいて、クラスタ内誤差Ｅが、所定の閾値未満であるか否かを判定する。閾値未満でない場合、ステップＳ３０５において、第２のクラスタリング部１３は、クラスタ内誤差Ｅが閾値未満でないクラスタを抽出する。更に、第２のクラスタリング部１３は、その抽出したクラスタを２つに分割する。この分割においては、エッジ画素の色コリログラム間の２次形式距離に基づいて、Ｋ＝２のK-means法が用いられる。更に、ステップＳ３０３に戻り、第２のクラスタリング部１３は、ステップＳ３０５において分割された後の各クラスタにおいて、クラスタ内誤差Ｅを算出する。第２のクラスタリング部１３は、ステップＳ３０５において、全てのクラスタのクラスタ内誤差Ｅが閾値未満であるかを判断する。【００８４】
全てのクラスタのクラスタ内誤差Ｅが、閾値未満になったと判断されるまで、ステップＳ３０３ないしステップＳ３０５の処理は繰り返される。全てのクラスタのクラスタ内誤差Ｅが、閾値未満になると、第２のクラスタリング処理は終了する。【００８５】
ここで、第２のクラスタリング部１３の処理を詳述する。
まず、Sobel フィルタを用いて各画像におけるエッジ画素を検出する。このとき、画素の３×３近傍の画素値に図９に示す記号を与えると、Sobel フィルタによるエッジ強度es は次式で定義される。
【数２３】
2009072466.tif 000025
しかしながら、本手法はカラー画像を分類対象としているため、式１６および式１７を次式に変更する。
【数２４】
2009072466.tif 000026
ここで、例えば||a − c||はa とc のL*a*b 色空間における色差を表す。【００８６】
本発明の最良の実施の形態においては、このように拡張したSobel フィルタを用いてエッジ画素を検出する。これにより取得されるエッジに着目してK-means 法により得られた各クラスタを分割することで、分類結果の高精度化を図る。エッジに着目するため、前述の拡張されたSobel フィルタにより得られるエッジ画素から距離k2(k2 < k1) に対する色コリログラムを作成する。その後、式１３を用いて算出される特徴ベクトル
【数２５】
2009072466.tif 000027
を用いることで、エッジに着目した処理を可能とする。このようにして得られた特徴ベクトルを用い、各クラスタをK-means 法によりさらに２つのクラスタに分割する。【００８７】
以上の処理を、全てのクラスタについて、次式により得られるクラスタ内の誤差E(Ck) がE(Ck) < THd を満たすまで行う。
【数２６】
2009072466.tif 000028
ただし、nk は、クラスタCk に属する分類対象画像の数を表す。以上の処理により、各クラスタを画像の重要な特徴であるエッジに着目して分割することが可能となる。【００８８】
（クラスタ統合部）
以上の処理により、画像分類装置１は、K-means 法を用いて得た各クラスタを、画像の重要な特徴であるエッジに着目して分割することが可能となる。ただし、これに伴って過分割が行われ、同一の被写体を撮像した画像が複数のクラスタに分割される場合がある。そこで、本発明の最良の実施の形態は、分割された各クラスタを、被写体に着目して統合することで、最終的な分類結果を得る。【００８９】
図１０を参照して、本発明の最良の実施の形態に係るクラスタ統合部１４によるクラスタ統合処理を説明する。
まずクラスタ統合部１４は、画像データベース５１に記憶された全ての画像データについて、ステップＳ４０１ないしステップＳ４０４の処理を実行する。ステップＳ４０１ないしステップＳ４０４の処理では、クラスタ統合部１４は、画像データの構図を決定する。【００９０】
画像データベース５１に記憶された画像データの１つについて、ステップＳ４０１において、クラスタ統合部１４は、任意の境界線を設定して、画像を２つの領域に分割する。次にステップＳ４０２において、クラスタ統合部１４は、ステップＳ４０１で分割された２つの領域のそれぞれについて、各領域に位置する画素についての色ヒストグラムを算出する。【００９１】
次にステップＳ４０３において、クラスタ統合部１４は、２つの領域における色ヒストグラム間の２次元形式距離に基づいて、ステップＳ４０１で設けた境界線が、画像の構図を示すかを判定する。【００９２】
また、ステップＳ４０１ないしステップＳ４０４の処理は、図１２Ａないし図１２Ｄに示すように、境界線の方向を変更して繰り返される。これによりクラスタ統合部１４は、画像データを、境界線内の画素と、境界線外の画素とに分割することができる。【００９３】
全ての画像データについて、ステップＳ４０１ないしステップＳ４０４の処理が終了すると、クラスタ統合部１４は、ステップＳ４０５を処理する。ステップＳ４０５において、クラスタ統合部１４は、境界線内の画素と境界線外の画素との特性に基づいて、被写体を構成する画素を抽出する。【００９４】
更に、クラスタ統合部１４は、ステップＳ４０５で抽出した被写体の画素に基づいて、類似する被写体の画素を有する画像が含まれるクラスタを、統合する。具体的にはクラスタ統合部１４は、複数のクラスタのうち、被写体が類似するクラスタを、１つのクラスタに統合する。この結果得られた各画像データが所属するクラスタの情報は、画像データベース５１に記憶されることが好ましい。【００９５】
ここで、クラスタ統合部１４の処理を詳述する。
最良の実施の形態において、被写体を構成する画素を推定するにあたり、分類対象画像をそのおおまかな色の分布から図１１Ａおよび図１１Ｂに示す２つの構図に大別する。【００９６】
構図１：画像中に被写体が存在する構図（図１１Ａ参照）。例えば、図１１Ｃに示す、中央付近に被写体が撮像されている画像。
構図２：構図１以外の構図(図１１Ｂ参照)。例えば、図１１Ｄに示す、テクスチャ画像等、画像全体を被写体が占める画像。【００９７】
以下で、構図を推定するための特徴量を、色ヒストグラムを用いて定義する。本発明の最良の実施の形態においては、図１２Ａないし図１２Ｄに示す境界線Li (i = 1, ・ ・ ・ , 4) を平行移動することにより、クラスタ統合部１４は、画素数の比がj : 1−j である２つの領域Ai,j,1，Ai,j,2 に、画像を分割する。このとき、j を1/d から(d-1)/dまで1/d ずつ変化させたときの、２つの領域における色ヒストグラム間の２次形式距離の変化は、画像の構図により固有の傾向を示す。そこで、本発明の最良の実施の形態においては、構図の決定に用いる特徴量は、hi,j,1，hi,j,2 間の２次形式距離を用いて次式により算出される
【数２７】
2009072466.tif 000029
を定義する。
【数２８】
2009072466.tif 000030
各構図について、２つの領域における色ヒストグラム間の2 次形式距離の変化が示す傾向、
及び画像の構図（構図1、あるいは構図2）の決定法が、以下に示される。【００９８】
構図１：構図１の画像を２つの領域に分割すると、それぞれの領域の色ヒストグラム間の２次形式距離は、境界線の位置により大きく変化する。そこで、
【数２９】
2009072466.tif 000031
を最大とするi を求め、
【数３０】
2009072466.tif 000032
とする。このとき、
【数３１】
2009072466.tif 000033
である場合にその画像の構図を構図１とする。
構図２：構図１以外の画像を構図２とする。【００９９】
本発明の最良の実施の形態は、構図１の画像から被写体を構成する画素を推定する。一般に、背景は画像の端に接するため、構図１を決定する際に得られた境界線
【数３２】
2009072466.tif 000034
を用い、画像の端に存在する領域である
【数３３】
2009072466.tif 000035
内に含まれる画素のL*a*b 表色系における輝度値のメディアン値を求め、その画像の背景を構成する画素の代表色とする。このとき得られた、背景を構成する画素の代表色との色差が、閾値THobject よりも大きな画素を、画像分類装置１は、被写体を構成している画素であると推定する。一方、構図２の画像については画像全体を１つの被写体とみなし、画像分類装置１は、全画素を被写体を構成する画素であると推定する。【０１００】
これにより得られる被写体を構成する画素に着目してクラスタを統合することで、クラスタの過分割を抑制し、クラスタ統合部１４は、最終的な分類結果を得る。被写体に着目するため、前述のように被写体を構成すると推定された画素から距離k1 に対する色コリログラムを算出する。ところで、色コリログラムは、非常に類似した画像間で高い類似度を示すが、被写体の撮像方向等の影響を受けやすいことが知られている。そこで、最良の実施の形態は、被写体を構成する画素から色ヒストグラムを得、さらに式１０より特徴ベクトルh’i を算出し、色コリログラムによる特徴ベクトルと共に用いてクラスタを統合する。クラスタの統合には、階層的クラスタリングの一手法であるウォード法が用いられる。【０１０１】
ウォード法は、クラスタCk とCl の非類似度S(Ck,Cl) を
【数３４】
2009072466.tif 000036
で定義し、最も非類似度の低い２つのクラスタを逐次統合する手法である。本発明の最良の実施の形態は、色ヒストグラムと色コリログラムを同時に考慮するため、式２３を次式のように変更する。
【数３５】
2009072466.tif 000037
ただし、
【数３６】
2009072466.tif 000038
はそれぞれクラスタCk、及びクラスタCl の色ヒストグラムにおけるクラスタ中心と色コリログラムにおけるクラスタ中心を縦に並べたベクトルであり、A = [aij ] は
【数３７】
2009072466.tif 000039
を満たす行列である。
本発明の最良の実施の形態においては、S(Ck,Cl) の最小値が、閾値TH よりも高い値を示すまで統合処理を繰り返し行う。以上の処理を行うことで、被写体に着目した高精度な類似画像分類が実現可能となる。【０１０２】
クラスタ統合部１４は、以上の処理により得られる各特徴量と、クラスタリング結果を画像ごとに保存しておき、可視化の際に使用する。ただし、保存しておく各特徴量は、可視化の際に特徴量間の距離を算出することを考慮し、式１０および式１３により変換を行った値とする。【０１０３】
（表示部）
分類部１０の処理によって得られた画像の特徴量、及びその分類結果に基づき、本発明の最良の実施の形態に係る画像分類装置１は、画像の分類結果を可視化する。この画像分類結果の可視化は、画像を多次元空間上に配置することで実現可能となる。【０１０４】
図１３を参照して、本発明の最良の実施の形態に係る表示部２０による表示処理が説明される。
まず、ステップＳ５０１において、表示部２０は、画像データベース５１に記憶された各画像データについて、画像全体の色コリログラム、エッジ領域における色コリログラムおよび被写体領域における色ヒストグラムと色コリログラムを算出する。この算出処理は、上述した分類部１０における処理結果値が参照されることが好ましい。各特徴値が算出されると、表示部２０は、ステップＳ５０２において、画像データ間の距離を定義する。【０１０５】
次にステップＳ５０３において、表示部２０は、画像データのサムネイルを、表示装置１０５の画面上に配置する。このとき表示部２０は、ランダムな位置に画像データのサムネイルを表示する。次に、ステップＳ５０４において、表示部２０は、ステップＳ５０２で定義された画像データ間の距離や、分類部１０によって決定されたクラスタに基づいて、画像データのサムネイルの座標を更新する。【０１０６】
ステップＳ５０５において、表示部２０は、座標更新の収束を判定をする。収束していない場合、ステップＳ５０４に戻り、更に画像データのサムネイルの座標を更新する。
一方、ステップＳ５０５において、表示部２０は、表示装置２０が座標更新が収束したと判定する場合、表示処理を終了する。【０１０７】
表示部２０における、ステップＳ５０２の画像データ間の距離の定義を説明する。
まず、表示部２０は、各画像データから特徴ベクトルを作成する。特徴ベクトルの要素としては、表示部２０は、上述した画像全体の色コリログラム、エッジ領域における色コリログラム、被写体領域における色ヒストグラムと色コリログラムの特徴量を用いる。表示部２０は、このようにして求められた画像Ii の特徴ベクトルvi から、式２６に基づき画像間の距離DI (i, j) を算出する。
【数３８】
2009072466.tif 000040
ただし、クラスタCi,Cj はIi ∈ Ci, Ij ∈ Cj を満たすクラスタである。wsame,wother は画像が所属するクラスタに応じた重みである。【０１０８】
このとき本発明の最良の実施の形態において表示部２０は、重みwsame,wother に対して、wsame < wother となる値を割り当てることで同じクラスタに属する画像間の距離を短くする。これにより、分類結果において同じクラスタに所属するとされた画像同士は、近距離に配置される。本発明の最良の実施の形態において表示部２０は、この画像間の距離に基づき画像のサムネイルの座標を更新するとともに、その収束過程をアニメーションで表示することにより、画像分類結果の可視化を実現する。【０１０９】
画像データ間の距離に基づいて画像の座標を移動させていき、収束するまでの過程を可視化することで、ユーザが、分類結果を直感的に把握することが可能となる。本発明の最良の実施の形態において表示部２０は、まず画像を空間上にランダムに配置し、それらが互いに類似した画像毎に集まっていく様子をアニメーションにより可視化する。本発明の最良の実施の形態は、多次元空間として、人間が知覚可能な最大次元である３次元空間を選択する。具体的には、表示部２０は、分類対象画像より算出された特徴の次元を３次元まで削減することで、画像の３次元空間での座標を決定し、３次元空間上に配置する。次に、これを２次元のスクリーン上で表現するため、表示部２０は、図１４に示す透視変換を行い、最終的な出力画像を得る。【０１１０】
本発明の最良の実施の形態に係る表示部２０は、以下のような手順により構成される。
手順１：初期配置
図１５に示すように、表示部２０は、各画像を３次元空間上にランダムに配置し、透視変換することで２次元のスクリーン上に表示する。この際、表示部２０は、各画像を配置する座標には多面体を描画し、その各面に対象画像を描画する。これにより、表示部２０が、画像の３次元上の位置をユーザに分かり易く提示することが可能となる。【０１１１】
手順２：画像の移動
表示部２０は、画像間の距離に基づき各画像の移動量を計算し、各画像の３次元空間上の座標を変更する。このとき、画像Ii の3 次元座標をpi とすると、その移動量
【数３９】
2009072466.tif 000041
は、以下の式に基づき算出される。
【数４０】
2009072466.tif 000042
ただし
【数４１】
2009072466.tif 000043
は、画像Ii の座標pi をmi 移動させたときの、３次元空間上における画像Ii, Ij 間の距離を示す。したがって、画像の移動量
【数４２】
2009072466.tif 000044
は、予め定義した画像間の距離DI (i, j)と実際の３次元空間上の距離
【数４３】
2009072466.tif 000045
の差が最小となるものとして求められる。このようにして求められた画像の移動量
【数４４】
2009072466.tif 000046
に基づき、表示部２０は、次式のように各画像の座標を更新する。
【数４５】
2009072466.tif 000047
【０１１２】
手順３：繰り返し
表示部２０は、手順２を、全ての画像の移動量
【数４６】
2009072466.tif 000048
が０に収束するまで繰り返す。０に収束した時点で、表示装置１０５には、図１６に示す画面が表示される。【０１１３】
図１６においては、もみじを示す絵や、建物を示す絵など、類似した画像のサムネイルが、近く配置されている。一方、類似していない画像のサムネイルが、遠く配置されている。【０１１４】
このような処理により、各画像データのサムネイル間の距離は、予め定義した距離DI (i, j) に近づいていく。類似した画像データのサムネイルが、近距離に配置されることとなる。【０１１５】
ここで、上述した手順２および手順３の処理が詳述される。各画像データのサムネイルの座標は、以下に示す評価関数を最小とする方向に移動する。
【数４７】
2009072466.tif 000049
ここで、簡単のため各画像（画像データのサムネイル）の座標を１次元に限定した例が、図１７Ａに示される。図１７Ａに示すように、各画像間の実際の距離が“７”、“２”であり、予め定義された画像間の距離が“５”，“４”であることが確認される。これらの値を用いて、表示部２０は、画像I2の座標を移動させた時の評価関数を算出し、値が最小となる方向に画像を移動させる。【０１１６】
（１）１ステップ目
画像が左に1移動された場合
f(-1)=|5-6|+|4-3|=2
画像が移動されない場合
f(0)=|5-7|+|4-2|=4
画像が右に1移動された場合
f(1)=|5-8|+|4-1|=6
以上より、画像を左に移動させたときに評価関数が、最小となることが分かる。したがって、この場合画像I2は、左へ移動する。このときの各画像の位置が、図１７Ｂに示される。表示部２０は、この処理を繰り返すことで、各画像を類似した画像の近傍に配置することができる。【０１１７】
（２）２ステップ目
次のステップでは、評価関数は以下のようになる。
画像が左に1移動された場合
f(-1)=|5-5|+|4-4|=0
画像が移動されない場合
f(0)=|5-6|+|4-3|=2
画像が右に1移動された場合
f(1)=|5-7|+|4-2|=4
以上より、画像I2は、左へ移動する。このときの各画像の位置が、図１７Ｃに示される。【０１１８】
（３）３ステップ目
次のステップにおける評価関数は、以下のようになる。
画像が左に1移動された場合
f(-1)=|5-4|+|4-5|=2
画像が移動されない場合
f(0)=|5-5|+|4-4|=0
画像が右に1移動された場合
f(1)=|5-6|+|4-3|=2
このとき、評価関数は画像を移動させないとき最小となる。この時点で評価関数は収束しているので、表示部２０は、画像（画像データのサムネイル）の移動を終了する。以上の処理を全ての画像に関して、表示部２０が評価関数が収束するまで行うことで、画像分類結果の可視化が実現する。【０１１９】
次に、図１５および図１６を説明する。
本発明の最良の実施の形態に係る表示部２０は、まず、図１５に示す初期画面Ｐ２０１を、表示装置１０５に表示する。初期画面Ｐ２０１は、分類過程表示部２０１を備えている。分類過程表示部２０１には、上述した手順１において、画像データのサムネイルをランダムに配置した状態が表示される。この初期画面Ｐ２０１は、各画像データのサムネイルを３次元空間にランダムに配置した後に透視変換を施すことにより得られる画面である。【０１２０】
さらに、手順２および手順３において、画像データのサムネイルが移動する様子が、表示画面１０５に表示される。この様に、自動分類の過程をアニメーションを用いて表示することで、ユーザがデータベースに含まれる画像を直観的に把握することができる。
手順２および手順３が繰り返された結果、移動量が収束すると、図１６に示す結果画面Ｐ２０２が、表示装置１０５に表示される。結果画面Ｐ２０２は、分類結果表示部２０２を備える。分類結果表示部２０２において、類似した画像が近くに表示される。一方、類似しない画像が遠くに表示される。【０１２１】
図１５および図１６に示す画面には、画像データのサムネイルが移動する過程を可視化するための制御ボタンがいくつか設けられている。具体的には、下記のボタンが設けられる。【０１２２】
（１）早送りボタン
このボタンがクリックされると、アニメーションの速度が速くなる。これにより、ユーザが最終的な収束結果を見たい場合には、表示部２０は、それを迅速に提示することができる。
（２）初期状態復元ボタン
このボタンがクリックされると、表示部２０は、分類過程を初期状態に戻すことができる。
（３）マップ表示・非表示ボタン
分類画面右上部に現在位置と視点の方向を示すマップが用意されている。これにより、ユーザは画像を配置した３次元空間上を自由に移動することができる。このボタンがクリックされることで、マップの表示・非表示を切替えることが可能である。
（４）視点変更ボタン
表示部２０は、画像を配置した３次元空間上での移動、および視点の変更を、マウスのドラッグにより行うことができる。その他、ユーザが４つの視点変更ボタンをクリックすることによっても、表示部２０は、予め定めた４つの位置・視点に変更することができる。【０１２３】
図１５に示す初期画面Ｐ２０１において、ユーザは、分類開始・一時停止ボタンをクリックすることで、表示部２０は、分類過程をアニメーションにより再現する。その後、最終的に図１６に示す結果画面Ｐ２０２のように分類対象画像群はそれぞれ類似した画像毎に集まり、表示部２０は、分類結果を表示することができる。ユーザは、分類過程表示部２０１および分類結果表示部２０２において、マウスのドラッグにより自由に３次元空間上での移動、および視点の変更が可能である。ユーザは、自由な視点で分類過程・結果を閲覧することができる。これにより、ユーザは、データベース中の画像を直観的に把握することができる。また、クエリ画像を保持していない場合、あるいは明確な検索意図が存在しない場合においても、ユーザは、所望する画像を検索することが可能となる。【０１２４】
また、表示部２０は、特定の画像と同じクラスタに所属する画像群を表示した結果を示しても良い。このとき、選択した画像データとともに、選択した画像データと同じクラスタに所属する画像データも表示することが好ましい。ユーザは選択した画像データと同じクラスタに所属する画像データから画像を選択できる。ユーザがこのうちの１枚をクリックすることで、ユーザは、新たに画像を選択することができる。【０１２５】
このように、本発明の最良の実施の形態に係る画像分類装置１は、画像の自動分類における分類過程および分類結果をユーザに提示することで、データベース中に含まれる画像を直観的に把握することができる。これによりユーザがクエリ画像を保持していない場合、あるいは明確な検索意図が存在しない場合においても、画像分類装置１は、ユーザの所望する画像を提供することが可能となる。【０１２６】
（効果）
本発明の最良の実施の形態に係る画像分類装置１は、分類結果を表示する際に３次元空間上において可視化する。これにより画像分類装置１は、分類結果を効率的に閲覧させることができる。具体的には、画像分類装置１は、画像間の非類似度に基づいて３次元空間上における距離を決定し、画像のサムネイルを表示装置１０５に配置する。これにより、データベース中の画像のサムネイルが類似画像ごとに集まった状態が、表示装置１０５に表示される。【０１２７】
また、画像分類装置１は、非類似度に基づいて画像間の距離を決定している。従って、ある画像から距離が近ければ近いほど、類似した画像が、表示装置１０５上に配置される。一方、遠ければ遠いほど、似ていない画像が、表示装置１０５上に配置される。これにより分類結果が表示される際、ある画像の周辺においてごく狭い範囲を見た場合には、類似している画像の中でも、特に類似している画像が近傍に配置される。同様に、あまり類似していない画像が遠くに配置されることとなる。また、より多くの画像を含む範囲で見た場合にも、類似している画像が近傍に配置され、似ていない画像が遠くに配置されることとなる。データベース中のすべての画像についてこのような配置が行われるため、ユーザが分類結果を閲覧する際に、画像分類装置１は、直感的に理解しやすく、効率的に閲覧させることができる。【０１２８】
また、本発明の最良の実施の形態に係る画像分類装置１は、段階的にクラスタリング処理をする。これにより画像分類装置１は、画像全体の色の分布だけでなく、画像中のより詳細な特徴を考慮して画像を分類することができる。具体的には、画像全体の色分布に基づいてクラスタリングすることで、画像分類装置１は、画像を、全体的に類似しているものにクラスタリングすることができる。次に、エッジ領域における色分布に基づいてクラスタを分割することで、画像分類装置１は、より高精度にクラスタリングすることができる。さらに、画像中に存在する被写体を推定し、被写体の特徴に基づいてクラスタを再統合することで、画像分類装置１は、画像中のもっとも重要な情報である被写体を考慮して、画像を分類することができる。また、クラスタリングの各段階において、色ヒストグラム、色コリログラム間の距離を算出する際に、距離尺度として２次形式距離を用いることで、画像分類装置１は、より人間の視覚特性に近い分類を実現する。
このように、本発明の実施の形態に係る画像分類装置１は、第１のクラスタリング部１２により、まず画像全体の特徴量に基づいて大まかに分類する。次に画像分類装置１は、第２のクラスタリング部１３により、画像を特徴付けるエッジ部分に注目して、更に階層的に詳細に分類する。更に、第１のクラスタリング部１２および第２のクラスタリング部１３により過分割されたクラスタを、クラスタ統合部１４は、被写体の特徴に基づいて、被写体ごとにクラスタを統合する。最後に被写体に基づいてクラスタを統合することにより、画像分類装置１は、ユーザの検索キーワードに合致しやすいクラスタを生成できる。【０１２９】
（変形例）
本発明の変形例に係る画像分類装置１ａは、最良の実施の形態に係る分類機能を利用することで、クエリ画像を与えた際に自動的に画像を検索することができる。【０１３０】
本発明の変形例に係る画像分類装置１ａは、まず入力されたクエリ画像から特徴量を抽出する。本発明の変形例に係る画像分類装置１のクエリ画像処理部３０は、抽出される特徴量を用いてあらかじめ特徴量の算出と分類が完了しているデータベース中の画像と比較し、クエリ画像が所属するクラスタを決定する。このクエリ画像の特徴量とクラスタリング結果をデータベース中の画像と合わせて用いることで、表示部２０は、3 次元空間上で検索結果を可視化する。【０１３１】
本発明の変形例に係る画像分類装置１ａは、入力されたクエリ画像から特徴量を抽出し、画像データベース５１中の画像と比較することで、クエリ画像に類似した画像を検索する。本発明の変形例に係る画像分類装置１は、入力されたクエリ画像から、画像を分類する際に使用したすべての特徴量を抽出する。そして、事前に特徴量の抽出および分類を完了しているデータベース中の画像と比較を行い、クエリ画像が所属するクラスタを決定する。これにより得られるクエリ画像の特徴量および所属するクラスタを、画像データベース５１中の画像のデータと合わせて用いることで、表示部２０は、検索結果を３次元空間上で可視化する。【０１３２】
図１８を参照して、本発明の変形例に係る画像分類装置１ａを説明する。
本発明の変形例に係る画像分類装置１ａは、図１に示す本発明の最良の実施の形態に係る画像分類装置１と比べて、クエリ画像分類部３０を備えている点が異なる。クエリ画像分類部３０は、クエリ画像特徴量算出部３１と、所属クラスタ決定部３２を備えている。【０１３３】
クエリ画像特徴量算出部３１は、クエリ画像データ５２の特徴ベクトルを算出する。ここで、特徴ベクトルは、画像全体における色コリログラムと、エッジ部分の色コリログラムと、被写体領域の色ヒストグラムと色コリログラムをパラメータとして有するベクトルである。クエリ画像特徴量算出部３１は、クエリ画像データ５２の画像全体における色コリログラムと、クエリ画像データ５２のエッジ部分の色コリログラムと、５２クエリ画像データの被写体領域の色ヒストグラムと色コリログラムを算出して、クエリ画像データ５２の特徴ベクトルを算出する。【０１３４】
クラスタ決定部３２は、クエリ画像データ５２の特徴ベクトルに基づいて、クラスタ統合部１４により生成されたクラスタから、クエリ画像データ５２の所属するクラスタを決定する。クラスタ決定部３２は、クラスタ統合部１４により生成された各クラスタに属する画像データの特徴ベクトルの平均を算出し、クエリ画像データ５２の特徴ベクトルとの距離を最小とするクラスタをクエリ画像の所属クラスタとする。【０１３５】
図１９を参照して、本発明の変形例に係る画像分類装置１ａにおける画像分類処理の概略を説明する。
まずステップＳ２１において、画像分類装置１ａは、クエリ画像データ５２の特徴ベクトルを算出する。更にステップＳ２２において画像データベース２２から各画像データを読み出し、各画像データにおける特徴ベクトルを取得する。【０１３６】
更にステップＳ２３において画像分類装置１ａは、クエリ画像データ５２と、各画像データとの特徴ベクトルの距離を算出する。ステップＳ２４において画像分類装置１ａは、クエリ画像データ５２が所属するクラスタを決定する。このとき、画像分類装置１ａは、ステップＳ２３で算出した距離が最小となるクラスタを、クエリ画像データ５２の所属クラスタとする。【０１３７】
更にステップＳ２５において画像分類装置１ａは、クエリ画像データ５２と、画像データベース５１に記憶された各画像データと、が分類される過程を、表示装置１０５に表示する。【０１３８】
（クエリ画像特徴量算出部）
図２０を参照して、本発明の変形例に係るクエリ画像特徴量算出処理３１が説明される。
まず、ステップＳ６０１において、クエリ画像特徴量算出処理３１は、記憶装置１０７からクエリ画像データ５２を読み出し、ステップＳ６０２において、クエリ画像データ５２の画像全体の色コリログラムを算出する。次にステップＳ６０３において、クエリ画像特徴量算出処理３１は、クエリ画像データ５２のエッジ領域における色コリログラムを算出する。さらにステップＳ６０４において、クエリ画像特徴量算出処理３１は、被写体領域における色コリログラムを算出する。【０１３９】
ステップＳ６０５において、クエリ画像特徴量算出処理３１は、ステップＳ６０２ないしステップＳ６０４の出力から、特徴ベクトルを生成する。【０１４０】
クエリ画像特徴量算出処理３１は、抽出する特徴量として、分類部１０において画像を自動的に分類する際に使用した特徴量を用いる。具体的には、クエリ画像特徴量算出処理３１は、画像全体の色コリログラム、エッジ領域における色コリログラム、被写体領域における色ヒストグラムと色コリログラムを算出する。得られた色ヒストグラム、色コリログラムによる特徴量は、２次形式距離による類似度を算出するため、式１０、式１３により変換される。クエリ画像特徴量算出処理３１は、これにより得られる値を要素とするベクトルを作成し、これを特徴ベクトルvquery とする。【０１４１】
（所属クラスタ決定部）
図２１を参照して、本発明の変形例に係る所属クラスタ決定部３２を説明する。
まず、ステップＳ７０１において、所属クラスタ決定部３２は、画像データベース５２の各画像データから、特徴ベクトルを生成する。更にステップＳ７０２において、所属クラスタ決定部３２は、クラスタ統合部１４によって生成された各クラスタの特徴ベクトルの平均ベクトルを算出する。【０１４２】
次にステップＳ７０３において、所属クラスタ決定部３２は、クエリ画像データ５２の特徴ベクトルと、ステップＳ７０２で算出した各クラスタの特徴ベクトルの平均との距離を算出する。ステップＳ７０４において、所属クラスタ決定部３２は、ステップＳ７０３において算出した特徴ベクトル間の距離を最小とするクラスタを、クエリ画像データ５２の所属するクラスタとする。【０１４３】
所属クラスタ決定部３２は、画像データベース５１中の各画像データに対して、あらかじめ算出されている特徴量を用いて、クエリ画像データ５１の特徴ベクトルと同様の特徴ベクトルを作成する。得られる特徴ベクトルを用いて、各クラスタの特徴ベクトルの平均ベクトルを算出し、得られるベクトルをvi とする。クエリ画像の特徴ベクトルvquery と各クラスタの平均特徴ベクトルvi 間において、次式を用いて距離を算出する。
【数４８】
2009072466.tif 000050
このD(vquery, vi) が最小となる特徴ベクトルvi を持つクラスタをクエリ画像が所属するクラスタとする。【０１４４】
以上の処理により得られるクエリ画像の特徴量と所属するクラスタが、画像データベース５１中の画像の特徴量とクラスタと合わせて保存され、可視化の際に使用される。【０１４５】
（表示部）
本発明の変形例に係る表示部２０ａは、クエリ画像分類部３０において得られたクエリ画像データ５２の特徴量と所属するクラスタの情報を画像データベース５１に追加する。さらに表示部２０ａは、本発明の最良の実施の形態で説明した画像分類装置１と同様に可視化する。【０１４６】
本発明の最良の実施の形態で説明した画像分類装置１の表示部２０は、画像が互いに類似するクラスタごとに集まっていく過程がアニメーションにより表示された。一方、本発明の変形例に係る画像分類装置１ａの表示部２０ａにおいては、クエリ画像データ５２を入力するため、クエリ画像データ５２に注目して可視化する。具体的には、表示部２０ａは、図２２に示すように透視変換の際に常に画面中央にクエリ画像が表示されるようにカメラパラメータを更新する。これにより、画面上ではクエリ画像データ５２に類似した画像が集まる過程が、可視化されることとなる。【０１４７】
表示部２０ａは、例えば、図２２に示す結果画面Ｐ２０３を表示する。この結果画面Ｐ２０３は、本発明の変形例に係る画像分類装置１ａにおいて、クエリ画像データ５２に類似する画像データを抽出した図である。クエリ画像表示部２０４には、クエリ画像データ５２のサムネイルが表示されている。分類結果表示部２０３の中心には、クエリ画像データ５２のサムネイルが表示され、分類結果表示部２０３においては、クエリ画像データ５２に類似する画像のサムネイルが近くに、類似しない画像のサムネイルが遠くに表示されている。類似画像表示部２０５には、分類結果表示部２０３において表示された画像データのうち、クエリ画像データ５２と同じクラスタに属する画像データが、類似画像として表示されている。このとき、同じクラスタに属する画像データのうち、特徴ベクトルの近い画像データのみを表示しても良い。【０１４８】
以上により、クエリ画像データに類似した画像を検索することが可能となる。本発明の変形例に係る画像分類装置１ａは、３次元空間上においてクエリ画像データ５２の周囲に類似した画像を配置することで、ユーザが所望の画像を直感的に検索することを実現した。【０１４９】
（効果）
本発明の変形例に係る画像分類装置１ａは、検索結果を表示する際に３次元空間上において可視化することで、検索結果を効率的に閲覧させることができる。具体的には、画像間の非類似度を３次元空間上における距離とすることで、画像分類装置１ａは、ユーザに検索結果を直感的に理解させることができる。さらに、３次元空間上における距離を、画像の非類似度に基づいて設定することで、画像分類装置１ａは、検索結果として表示されるクエリ画像以外の画像においても類似した画像が近傍に表示されるため、ユーザに、効率的に検索結果を閲覧をさせることが可能となる。【０１５０】
また、本発明の変形例に係る画像分類装置１ａは、検索する際に検索対象データベース中の画像におけるクラスタリング結果を利用することで、少ない計算量での効率的な検索を可能とする。具体的には、検索する際には、まず検索対象の画像データベース５１中の画像において、最良の実施の形態において説明した方法で、特徴量の算出とクラスタリングが完了しているものとする。そして、クエリ画像データ５２が入力された際に、画像分類装置１ａは、画像データベース４１中のクラスタリング結果を利用してクエリ画像のクラスタリングをすることで、効率的な処理を可能とする。【０１５１】
（その他の実施の形態）
上記のように、本発明の最良の実施の形態および変形例によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなる。
例えば、本発明の最良の実施の形態に記載した画像分類装置は、図１に示すように一つのハードウェア上に構成されても良いし、その機能や処理数に応じて複数のハードウェア上に構成されても良い。又、既存の情報システム上に実現されても良い。
本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。従って、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図１】
2009072466.tif 000051
【図２】
2009072466.tif 000052
【図３】
2009072466.tif 000053
【図４】
2009072466.tif 000054
【図５Ａ】
2009072466.tif 000055
【図５Ｂ】
2009072466.tif 000056
【図６】
2009072466.tif 000057
【図７】
2009072466.tif 000058
【図８】
2009072466.tif 000059
【図９】
2009072466.tif 000060
【図１０】
2009072466.tif 000061
【図１１Ａ】
2009072466.tif 000062
【図１１Ｂ】
2009072466.tif 000063
【図１１Ｃ】
2009072466.tif 000064
【図１１Ｄ】
2009072466.tif 000065
【図１２Ａ】
2009072466.tif 000066
【図１２Ｂ】
2009072466.tif 000067
【図１２Ｃ】
2009072466.tif 000068
【図１２Ｄ】
2009072466.tif 000069
【図１３】
2009072466.tif 000070
【図１４】
2009072466.tif 000071
【図１５】
2009072466.tif 000072
【図１６】
2009072466.tif 000073
【図１７Ａ】
2009072466.tif 000074
【図１７Ｂ】
2009072466.tif 000075
【図１７Ｃ】
2009072466.tif 000076
【図１８】
2009072466.tif 000077
【図１９】
2009072466.tif 000078
【図２０】
2009072466.tif 000079
【図２１】
2009072466.tif 000080
【図２２】
2009072466.tif 000081
【国際調査報告】
2009072466.tif 000082
2009072466.tif 000083
2009072466.tif 000084