(57)【要約】【課題】色の特徴を精度良く表すことが可能なカラーヒストグラムを生成する装置ないし手法を提供する。【解決手段】色空間データベースと、ヒストグラム生成部２とを備えている。色空間データベースは、色空間に属するデータ群をクラスタリングすることにより生成された複数の部分空間の情報を備えている。ヒストグラム生成部２は、入力画像におけるピクセルがどの部分空間に属するかを判定し、これに基づいてヒストグラムを生成する。色空間データベースは、例えば、ルックアップテーブル４である。ルックアップテーブル４では、入力画像において用いられている色空間に属するデータと、そのデータが属するべき部分空間とが対応させられている。ルックアップテーブル４を用いた場合は、入力画像におけるピクセルのデータを用いて、ルックアップテーブル４を参照することによって、当該ピクセルが属する部分空間を決定することができる。【選択図】図１
2010072682.tif 000002
【特許請求の範囲】
【請求項１】
色空間データベースと、ヒストグラム生成部とを備えており、
前記色空間データベースは、色空間に属するデータ群をクラスタリングすることにより生成された複数の部分空間の情報を備えており、
前記ヒストグラム生成部は、入力画像におけるピクセルがどの前記部分空間に属するかを判定し、これに基づいてヒストグラムを生成する構成となっている
ことを特徴とするカラーヒストグラム生成装置。
【請求項２】
前記色空間データベースは、生成された前記各部分空間における中心データをさらに有しており、
前記ヒストグラム生成部は、
前記入力画像におけるピクセルと、前記各部分空間における前記中心データとの距離を算出する処理と、
前記ピクセルに最も近い中心データが属する部分空間に前記ピクセルを属させる処理と
を行う構成となっている
請求項１に記載のカラーヒストグラム生成装置。
【請求項３】
前記色空間データベースは、前記入力画像において用いられている色空間に属するデータと、そのデータが属するべき前記部分空間とが対応させられたルックアップテーブルであり、
前記ヒストグラム生成部は、前記入力画像におけるピクセルのデータを用いて、前記ルックアップテーブルを参照することによって、当該ピクセルが属する前記部分空間を決定する構成となっている
請求項１又は２に記載のカラーヒストグラム生成装置。
【請求項４】
前記色空間データベースにおける前記部分空間は、生成された各部分空間の中心点と、他の部分空間の中心点との間における距離の最小値が一定となるように構成されている
請求項１〜３のいずれか１項に記載のカラーヒストグラム生成装置。
【請求項５】
前記色空間データベースにおける前記各部分空間は、各部分空間に属するデータと各部分空間の中心点との距離の最大値が一定となるように生成されている
請求項１〜４のいずれか１項に記載のカラーヒストグラム生成装置。
【請求項６】
前記色空間データベースにおける前記複数の部分空間は、さらに、無彩色用の部分空間を備えており、
前記無彩色用の部分空間は、前記色空間に属するデータ群のうち、無彩色のデータ群をクラスタリングすることにより生成されていることを特徴とする請求項１〜５のいずれか１項に記載のカラーヒストグラム生成装置。
【請求項７】
さらに、部分空間生成部を備えており、
前記色空間データベースにおける前記部分空間は、前記部分空間生成部により生成されている
請求項１〜６のいずれか１項に記載のカラーヒストグラム生成装置。
【請求項８】
前記部分空間生成部がクラスタリングする前記データ群は、前記色空間における格子点である
請求項１〜７のいずれか１項に記載のカラーヒストグラム生成装置。
【請求項９】
前記部分空間生成部がクラスタリングする前記データ群は、前記色空間から抽出された代表点である
請求項７のいずれか１項に記載のカラーヒストグラム生成装置。
【請求項１０】
色空間に属するデータ群をクラスタリングすることにより生成された複数の部分空間の情報を備えた色空間データベースを用意するステップと；
入力画像におけるピクセルがどの前記部分空間に属するかを判定し、これに基づいてヒストグラムを生成するステップと
を備えることを特徴とするカラーヒストグラム生成方法。
【請求項１１】
請求項１０に記載のステップをコンピュータに実行させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カラーヒストグラムを生成するための技術に関するものである。より詳しくは、本発明は、画像の特徴を表すためのカラーヒストグラムを生成する技術に関するものである。
【背景技術】
【０００２】
画像どうしの類似度を判定するために、画像から特徴量を抽出し、特徴量どうしを比較する手法が知られている。特徴量は、一般に多次元ベクトルデータとして取得できるので、ベクトルデータ間の距離を用いて類似度を判定することができる。
【０００３】
画像の特徴量の一種として、カラーヒストグラムが知られている（下記特許文献１参照）。カラーヒストグラムを生成するための代表的な手法は以下の通りである。
・色空間を分割して、部分空間（いわゆるビン）を得る。
・入力画像を構成する各ピクセルが、どのビンに属するかを判別する。
・各ビンに属するピクセル数を、ピクセル総数で正規化する。
【０００４】
このようにして得られた、ビン毎のピクセル数が、カラーヒストグラムとなる。このカラーヒストグラムは、画像における色の特徴を表していると考えられるので、カラーヒストグラムを用いることにより、色を基準として、画像間の類似関係を判別できる。
【特許文献１】特開２００６−１５５６１９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、従来、色空間を分割する手法としては、分離直線や分離曲線で空間を分割する方法が用いられている。例えば、前記特許文献１の技術では、色空間として、ＨＳＶ空間における双六角錘モデルが用いられている。この空間を、基本的に明度を基準として分割することで、部分空間（すなわちビン）を生成している。
【０００６】
しかしながら、このように空間を分割すると、部分空間どうしの間における色の差にばらつきが出てしまう。すなわち、隣接する部分空間どうしの間で、比較的に色が似ている場合と、似ていない場合ができてしまう。例えば、あるピクセルとあるピクセルとは、感覚的には色が似ているにも関わらず、これらが違うビンに属してしまうことがある。逆に、感覚的には互いに色が相当に異なるピクセルであっても、同じビンに属することがある。
【０００７】
すなわち、従来の技術においては、生成されたカラーヒストグラムによって色の特徴を精度良く表すことについて、改良の余地がある。
【０００８】
本発明は、前記の状況に鑑みてなされたものである。本発明の目的の一つは、色の特徴を精度良く表すことが可能なカラーヒストグラムを生成する装置ないし手法を提供することである。
【課題を解決するための手段】
【０００９】
本発明は、以下のいずれかの項目に記載の構成とされている。
【００１０】
（項目１）
色空間データベースと、ヒストグラム生成部とを備えており、
前記色空間データベースは、色空間に属するデータ群をクラスタリングすることにより生成された複数の部分空間の情報を備えており、
前記ヒストグラム生成部は、入力画像におけるピクセルがどの前記部分空間に属するかを判定し、これに基づいてヒストグラムを生成する構成となっている
ことを特徴とするカラーヒストグラム生成装置。
【００１１】
この項目の発明においては、クラスタリングを用いて、複数の部分空間が生成されている。ここで、クラスタリングは、色空間を構成するデータ群を対象として行われる。したがって、この装置では、色空間に対して分割線を引くのではなく、クラスタリングによって、部分空間を形成することができる。
【００１２】
さらに、ヒストグラム生成部によって、入力画像における各ピクセルがどの部分空間に属するかを判断し、ヒストグラムを生成することができる。
【００１３】
この装置では、色空間におけるデータ群のクラスタリングにより部分空間を形成している。このため、生成されたヒストグラムは、色の特徴を精度良く表現することが可能である。
【００１４】
（項目２）
前記色空間データベースは、生成された前記各部分空間における中心データをさらに有しており、
前記ヒストグラム生成部は、
前記入力画像におけるピクセルと、前記各部分空間における前記中心データとの距離を算出する処理と、
前記ピクセルに最も近い中心データが属する部分空間に前記ピクセルを属させる処理と
を行う構成となっている
項目１に記載のカラーヒストグラム生成装置。
【００１５】
ここで、「部分空間にピクセルを属させる」ということは、その部分空間（いわゆるビン）に含まれるべきピクセルの数としてカウントするということである。
【００１６】
（項目３）
前記色空間データベースは、前記入力画像において用いられている色空間に属するデータと、そのデータが属するべき前記部分空間とが対応させられたルックアップテーブルであり、
前記ヒストグラム生成部は、前記入力画像におけるピクセルのデータを用いて、前記ルックアップテーブルを参照することによって、当該ピクセルが属する前記部分空間を決定する構成となっている
項目１又は２に記載のカラーヒストグラム生成装置。
【００１７】
ルックアップテーブルを用いることにより、カラーヒストグラムを高速に生成することが可能になる。ピクセルのデータとルックアップテーブルのデータが異なるときは、ピクセルのデータに最も近いルックアップテーブルのデータに基づいて部分空間を決定することができる。
【００１８】
（項目４）
前記色空間データベースにおける前記部分空間は、生成された各部分空間の中心点と、他の部分空間の中心点との間における距離の最小値が一定となるように構成されている
項目１〜３のいずれか１項に記載のカラーヒストグラム生成装置。
【００１９】
このようにクラスタリングを行うことにより、カラーヒストグラムの精度（画像から受ける感覚的な特徴とカラーヒストグラムとが整合すること）を一層向上させることができる。
【００２０】
（項目５）
前記色空間データベースにおける前記各部分空間は、各部分空間に属するデータと各部分空間の中心点との距離の最大値が一定となるように生成されている
項目１〜４のいずれか１項に記載のカラーヒストグラム生成装置。
【００２１】
このようにクラスタリングを行うことにより、カラーヒストグラムの精度を一層向上させることができる。
【００２２】
（項目６）
前記色空間データベースにおける前記複数の部分空間は、さらに、無彩色用の部分空間を備えており、
前記無彩色用の部分空間は、前記色空間に属するデータ群のうち、無彩色のデータ群をクラスタリングすることにより生成されている
ことを特徴とする項目１〜５のいずれか１項に記載のカラーヒストグラム生成装置。
【００２３】
この項目の発明では、一部の部分空間が無彩色用のものとなっている。
【００２４】
（項目７）
さらに、部分空間生成部を備えており、
前記色空間データベースにおける前記部分空間は、前記部分空間生成部により生成されている
項目１〜６のいずれか１項に記載のカラーヒストグラム生成装置。
【００２５】
（項目８）
前記部分空間生成部がクラスタリングする前記データ群は、前記色空間における格子点である
項目１〜７のいずれか１項に記載のカラーヒストグラム生成装置。
【００２６】
格子点とは、整数値で構成されるデータという意味である。格子点をクラスタリングの対象とすることにより、クラスタリングのための計算コストを低く抑えることができる。
【００２７】
（項目９）
前記部分空間生成部がクラスタリングする前記データ群は、前記色空間から抽出された代表点である
項目１〜７のいずれか１項に記載のカラーヒストグラム生成装置。
【００２８】
色空間におけるデータを適宜間引いてクラスタリングを行うことも可能である。どの程度間引くかについては、求められるクラスタリングの精度と計算コストとに鑑みて決定することができる。色空間から抽出された代表点を用いてクラスタリングを行うことにより、クラスタリングのための計算コストをさらに低く抑えることができる。
【００２９】
（項目１０）
色空間に属するデータ群をクラスタリングすることにより生成された複数の部分空間の情報を備えた色空間データベースを用意するステップと；
入力画像におけるピクセルがどの前記部分空間に属するかを判定し、これに基づいてヒストグラムを生成するステップと
を備えることを特徴とするカラーヒストグラム生成方法。
【００３０】
（項目１１）
項目１０に記載のステップをコンピュータに実行させることを特徴とするコンピュータプログラム。
【００３１】
このコンピュータプログラムは、適宜な記録媒体（例えばＣＤ−ＲＯＭやＤＶＤディスクのような光学的な記録媒体、ハードディスクやフレキシブルディスクのような磁気的記録媒体、あるいはＭＯディスクのような光磁気記録媒体）に格納することができる。このコンピュータプログラムは、インターネットなどの通信回線を介して伝送されることができる。
【発明の効果】
【００３２】
本発明によれば、色の特徴を精度良く表すことが可能なカラーヒストグラムを生成する装置ないし手法を提供することができる。
【発明を実施するための最良の形態】
【００３３】
（第１実施形態の装置構成）
本発明の第１実施形態に係るカラーヒストグラム生成装置を、添付の図面に基づいて説明する。
【００３４】
本実施形態のカラーヒストグラム生成装置は、部分空間生成部１と、ヒストグラム生成部２と、ルックアップテーブル生成部３とを主要な構成として備えている（図１参照）。
【００３５】
部分空間生成部１は、色空間に属するデータ群をクラスタリングすることにより、複数の部分空間を生成する構成となっている。
【００３６】
ヒストグラム生成部２は、入力画像におけるピクセルがどの部分空間に属するかを判定し、これに基づいてヒストグラムを生成する構成となっている。
【００３７】
ルックアップテーブル生成部３は、入力画像の色空間に属するデータと、そのデータが属する部分空間とを対応させるためのルックアップテーブル４を生成する構成となっている。ルックアップテーブル４は、本発明における色空間データベースの一例に対応している。
【００３８】
本実施形態におけるヒストグラム生成部２は、入力画像におけるピクセルのデータを用いて、ルックアップテーブル４を参照することによって、当該ピクセルが属する部分空間を決定する構成となっている。
【００３９】
本実施形態の装置における具体的な動作を、以下において詳しく説明する。
【００４０】
（第１実施形態の動作）
本実施形態におけるカラーヒストグラムの生成方法を、図２〜図８をさらに参照しながら説明する。
【００４１】
（全体的な手順）
まず、全体的な手順を図２に基づいて説明する。その後、個別の処理について、さらに詳しい手順を説明する。
【００４２】
（図２のステップＳＡ−１）
まず、部分空間生成部１により色空間に属するデータ群をクラスタリングする。これにより、複数の部分空間を生成することができる。
【００４３】
本実施形態では、ヒストグラムを生成する前に、色空間に属するデータ群に対して、クラスタリングを行う。このクラスタリングにより、複数の部分空間を生成できる。この実施形態では、入力画像のピクセルとは関係なく、色空間に属するデータ群を対象としてクラスタリングを行っている。本実施形態では、色空間に対して分割線を引くのではなく、クラスタリングによって、部分空間を形成することができる。
【００４４】
（図２のステップＳＡ−２及びＳＡ−３）
ついで、ヒストグラム生成部２により、入力画像におけるピクセルがどの部分空間に属するかを判定する。これに基づいてヒストグラムを生成して出力することができる。この装置では、色空間におけるデータ群のクラスタリングにより部分空間を形成している。このため、生成されたヒストグラムは、色の特徴を精度良く表現することが可能である。
【００４５】
（部分空間の生成手順）
次に、前記した部分空間の生成手順を、図３を参照しながら、さらに詳しく説明する。
【００４６】
（図３のステップＳＢ−１）
この実施形態では、画像がＲＧＢで取得されることを前提として説明する。もちろん、ＲＧＢ以外の色空間を用いたデータを扱うことも可能である。
【００４７】
まず、すべてのRGBの組み合わせのデータを、以下のように、擬似的に生成する。このデータはあくまでクラスタリングのために用意されるデータであり、現実の入力画像のデータではない。
（Ｒ，Ｇ，Ｂ）＝(0, 0, 0)〜(255, 255, 255)
【００４８】
これにより、２５６×２５６×２５６の数のデータが生成される。このようにこの実施形態では、格子点のデータを選択している。格子点とは、整数値で表されるデータである。格子点のデータを用いることにより、後述する計算を高速に行うことが可能になる。ただし、格子点のデータを使うことは必須ではなく、適宜のデータを用いることは可能である。
【００４９】
また、本実施形態において、全ての格子点を使う必要はなく、適宜に間引くことが可能である。間引く（すなわち代表点を使う）ことによって、計算量をさらに減らすことができる。
【００５０】
次に、ＲＧＢの色空間をLa*b*に変換する。La*b*は、RGBに比べて、人間の色感覚をより適正に表現していると言われているからである。ただし、クラスタリングにおいて用いる色空間は、La*b*に限定されず、他の色空間（例えばＨＳＶ、Lu*v*など）を用いることができる。この実施形態では、後述するルックアップテーブルを生成するために、変換したLa*b*のデータと、元のRGBのデータとの間に紐付けを行っておく。つまり、一方のデータから他方のデータを参照可能としておく。
【００５１】
（図３のステップＳＢ−２）
ついで、La*b*の空間上で、上記した格子点の全データをクラスタリングし、クラスタを求める。クラスタリングの手法はNearest Neighbor法やk-mean法など一般的なクラスタリング手法を利用できる。クラスタリングの詳しい実装例については後述する。なお、クラスタリングするときの距離の計算は、La*b*の空間でのユークリッド距離を利用してもよいし、各色空間で定義されている色差式を利用してもよい。どちらの場合も、この明細書では距離として表現する。
【００５２】
クラスタリングにより、均等に空間が分割される。生成された各クラスタにより、部分空間（いわゆるビン）が形成される。
【００５３】
（図３のステップＳＢ−３）
ついで、部分空間生成部１は、各クラスタの中心データを算出する。各クラスタの中心データは、各ビンを代表する色（代表色）となる。各クラスタの中心を算出する方法は、従来から用いられている方法を利用できる。
【００５４】
La*b*の色空間６を複数のクラスタ７に分割した状況を図４に模式的に示す。La*b*の色空間６は図示のようないびつな形状となっている。各クラスタ７は円で表されている。各クラスタ７の中心点（中心データ）８が代表色となる。
【００５５】
この実施形態において、各ビンは、クラスタ７の中心点８の間を線で区切った部分空間となる。ただし、この実施形態では、実際に線を定義することで部分空間を形成しているのではない。ピクセルを、それに最も近い中心点を持つクラスタに属させることによって、このような擬似的な境界を持つビンを把握できる。
【００５６】
（図３のステップＳＢ−４）
一方、ルックアップテーブル生成部３は、色空間に属するデータと、そのデータが属する部分空間とを対応させるルックアップテーブルを生成する。具体的には、まず、La*b*空間の各データが、どのクラスタに属するかを判定する。この判定は、La*b*空間内の各データについて、クラスタ中心との距離が最も近いクラスタに属させることにより行うことができる。その上で、各クラスタのビン番号と、それに属すLa*b*空間の色に紐づいているRGBの値とのすべての組み合わせについて、ルックアップテーブル４を作成する。
【００５７】
ルックアップテーブル４の例を図５に示す。ここでは、ＲＧＢのそれぞれの値に対して、ビン番号が割り当てられている。
【００５８】
（クラスタリングの実装例）
次に、前記したクラスタリングの実装例を、図６をさらに参照しながら説明する。
【００５９】
（図６のステップＳＣ−１）
先ず、クラスタリングを開始するに当たり初期クラスタを生成する。つまり各初期クラスタの中心点を最初に決定する。この中心点は色空間からランダムに選択しても良いが、色空間の３次元空間上で格子上の点を初期クラスタの中心とすることで、効率良く部分空間を生成することができる。なお、無彩色の部分空間を生成する場合には無彩色の初期クラスタ(a, bが0でＬのみが0以外の値を持つクラスタ)を複数生成する。
【００６０】
（図６のステップＳＣ−２）
次ぎに、La*b*色空間における一つの点を対象点として選択する。ただし、対象点は、色空間から抽出された代表点であってもよい。代表点を使うことにより、クラスタリングのための計算コストを低く抑えることができる。
【００６１】
（図６のステップＳＣ−３）
つぎに、各クラスタに対象点を追加した場合の評価指標を計算する。評価指標の計算は、例えば以下のように行うことができる。
【００６２】
（１Ａ）いずれか一つのクラスタ（初期クラスタ）に対象点を追加したと仮定し、クラスタの中心（中心データ）を求める。中心としては、例えば、クラスタを構成する全ての点の平均を用いることができる。あるいは、クラスタ内の他の点との距離の総和が最も小さくなる点を中心としても良い。なお、無彩色の部分空間（後述）の場合には中心点を算出する時にL(La*b*の輝度)のみで算出しa,b(La*b*のa,b)の値は０とする。
【００６３】
（２Ａ）ついで、すべてのクラスタについて、その半径を求める。半径を求めるには、例えば、クラスタの中心点と、クラスタ内に属するすべての点との間の距離を求める。求めた距離の最大値を半径とすることができる。
【００６４】
（３Ａ）ついで、全クラスタについて、半径の平均μa、分散σaを算出する。
【００６５】
（４Ａ）各クラスタの中心ごとに、他のクラスタの中心までの距離を求める。そして、距離の最小値を、隣接するクラスタとの間の距離とする。さらに、この距離の平均μb、分散σbを算出する。
【００６６】
（５Ａ）さらに、評価指標Pを、例えば以下の式により算出する。
Ｐ=k1・μa＋k2・σa＋k3・μb＋ｋ4・σb
ここで、k1〜4は重み付け係数である。
【００６７】
各クラスタに対象点を追加したと仮定し、それぞれの場合について、評価指標Ｐを算出する。
【００６８】
（図６のステップＳＣ−４）
前記した評価指標Pが最小となるクラスタに対象点を追加する。
【００６９】
（図６のステップＳＣ−５）
色空間中に残りの点があれば、ステップＳＣ−２に戻り、前記した処理を繰り返す。全ての点について処理が終わると、次のステップＳＣ−６に進む。
【００７０】
（図６のステップＳＣ−６）
クラスタリングの結果は初期クラスタに依存するので、上記手順を行っても最適な部分集合が生成されるとは限らない。そこで以下のような繰り返しの操作を行う。
【００７１】
（１Ｂ）部分空間を生成するためのすべての点（サンプル集合）を決定する。この点としては、色空間内のすべての整数値でもよい。ただし、適当な間隔のサンプリングによりサンプル集合を抽出して使うこともできる。
【００７２】
（２Ｂ）初期クラスタ（中心点）を決定する。ランダムに決定しても良いし、格子状に決定してもよい。なお、無彩色の部分空間を生成する場合には無彩色の初期クラスタ(a, bが必ず0でＬが任意の値を持つクラスタ)を複数決定する。
【００７３】
（３Ｂ）サンプル集合について、前記したステップＳＣ−２〜ＳＣ−５を実施する。
【００７４】
（４Ｂ）このステップ（３Ｂ）が終了した時点で、終了前のクラスタに含まれる点と、終了後のクラスタに含まれる点を比較する。両クラスタに含まれる点が同じであれば終了とする。クラスタに含まれる点が違う場合は、当該クラスタの中心をクラスタの開始点として、再度、サンプル集合について、ステップ（３Ｂ）に戻って処理を繰り返す。
【００７５】
前記したクラスタリングの実装例によれば、生成された各部分空間の中心点とその中心点から他の部分空間の中心点との距離の最小値が一定となるように、部分空間が生成されることになる。
【００７６】
このようにクラスタリングを行うことにより、カラーヒストグラムの精度（画像から受ける感覚的な特徴とカラーヒストグラムとが整合すること）を一層向上させることができる。
【００７７】
さらに、前記したクラスタリングの実装例によれば、生成された各部分空間において、その部分空間に属するデータと中心点との距離の最大値が一定となるように、部分空間が生成されることになる。
【００７８】
この点でも、この実装例では、カラーヒストグラムの精度を一層向上させることができる。
【００７９】
（ヒストグラムの生成手順）
次に、ヒストグラム生成部２を用いたヒストグラムの生成手順を、図７をさらに参照しながら説明する。
【００８０】
（図７のステップＳＤ−１）
まず、入力画像を取得する。入力画像とは、例えば、画像検索のために入力されたクエリ画像である。ただし、クエリ画像に限らず、カラーヒストグラムを生成する必要がある画像であれば、どのような用途に用いられるものであってもよい。本実施形態の入力画像は、ＲＧＢの色空間で表現されているものとする。一般に、ＲＧＢで表される画像が多いためである。ただし、原理的には、入力画像を表現する色空間には特に制約はない。
【００８１】
（図７のステップＳＤ−２）
入力画像におけるピクセルのデータは、この実施形態では、前記したように、ＲＧＢで表現されている。本実施形態では、入力データに最も近いＲＧＢの値を、ルックアップテーブル４から選択する。入力データとルックアップテーブルのデータとの距離は、例えばユークリッド距離を用いて算出できる。
【００８２】
ついで、該当するデータが見つかった場合は、ルックアップテーブル４に示されたビン番号に、当該ピクセルを属させる。つまり、そのビン番号のデータ数を増加させる。
【００８３】
この処理を、入力画像における各ピクセルについて行う。
【００８４】
（図７のステップＳＤ−３）
入力画像における全てのピクセルについて、どのビンに属するかを判定した後、各ビンのピクセル数を、総ピクセル数で正規化する。その後、得られたカラーヒストグラムを出力することができる。このカラーヒストグラムは、画像の特徴量を示すデータとして利用することができる。
【００８５】
本実施形態では、前記したように、色空間に属するデータについてクラスタリングを行っている。そして、生成されたクラスタに、入力画像のピクセルを配分することで、カラーヒストグラムを生成している。このため、この実施形態では、人間の感覚に沿ったカラーヒストグラムを精度良く生成することが可能になっている。
【００８６】
また、本実施形態では、色空間データベースとしてルックアップテーブル４を用いたので、カラーヒストグラムを高速に生成することが可能になる。
【００８７】
なお、前記実施形態では、ルックアップテーブル４を生成し、これを用いてヒストグラムを生成している。しかしながら、ルックアップテーブルの生成や使用は省略することができる。すなわち、入力画像における各ピクセルと、各クラスタの中心データとを比較することにより、ピクセルが属すべきビンを決定することができる。一般には、最も近い中心データを有するビン（クラスタ）に、当該ピクセルを属させる。すなわち、色空間データベースとしては、色空間に属するデータ群へのクラスタリングで生成された複数の部分空間の情報を有していればよい。この情報を用いて、入力画像のピクセルと部分空間とを対応させることにより、ヒストグラムを生成することができる。
【００８８】
また、前記した実施形態では、クラスタリングにおいて、前記した評価式を用いた。しかしながら、簡便に行う場合は、以下の手法も可能である。
【００８９】
すなわち、色空間における各対象点から各クラスタの中心点までの距離（距離としては、色空間で定義される色差式を利用しても良い）を求める。そして、最も近いクラスタへ対象点を加えることができる。
【００９０】
また、前記した実施形態では、色空間データベースを生成する段階から説明している。しかしながら、生成した色空間データベースを再利用することは可能である。したがって、既に生成された色空間データベースを用意し、これを用いてヒストグラムを生成することができる。
【００９１】
（第２実施形態）
次に、第２実施形態におけるカラーヒストグラムの生成方法を、図９に基づいて説明する。なお、第２実施形態の説明においては、前記した第１実施形態と共通する要素については、同一符号を用いることにより、説明の煩雑を避ける。
【００９２】
第１実施形態では、ヒストグラムを生成する際に、入力画像のピクセルに最も近い中心を持つクラスタに当該ピクセルを属させていた。これに対して、第２実施形態では、一つのクラスタにピクセルを割り当てるのではなく、重み付けを行った上で、複数のピクセルに重みを割り当てる。
【００９３】
（図９のステップＳＥ−１）
入力画像を左上から右下へ１画素ずつスキャンし、対象ピクセルを選択する。
【００９４】
（図９のステップＳＥ−２）
対象ピクセルが含まれるビンを決定する。この処理は、第１実施形態の手法を用いて行うことができる。
【００９５】
（図９のステップＳＥ−３）
すべてのビンに、対象ピクセルとの類似度を加える。類似度Ｓは、例えば以下の式で計算できる。
Ｓ＝1 - ｄ（Ci, S）/ M
ここで、
Ci：ｉ番目のクラスタの中心データ、
S：対象ピクセルのデータ
d()：色差式（距離）
M：色差の最大値
である。全てのクラスタについてこの計算を行うことで、各ピクセルと各ビンとの類似度を、全てのビンに対して加算することができる。
【００９６】
（図９のステップＳＥ−４）
全てのピクセルの処理が終われば終了とする。そうでなければステップＳＥ−１に戻る。
【００９７】
（図９のステップＳＥ−５）
すべてビンにおけるカウントを画素数で割ることで正規化する。
【００９８】
第２実施形態では、各ピクセルに類似するすべてのビンに、類似度の重みをカウントすることができ、ヒストグラムの精度をさらに向上させることができる。
【００９９】
なお、第２実施形態における前記した処理において、ルックアップテーブルを用いることができる。すなわち、色空間を構成するデータと、各ビンとの類似度とを事前に計算し、ルックアップテーブル（図示せず）を生成することができる。そして、入力画像に近いデータを基準として、ルックアップテーブルを参照し、類似度を得ることができる。これにより、入力画像におけるカラーヒストグラムの生成を高速に行うことができる。
【０１００】
前記した各実施形態の動作は、コンピュータに適宜のコンピュータソフトウエアを組み込むことにより実施することができる。
【０１０１】
なお、本発明の内容は、前記実施形態に限定されるものではない。本発明は、特許請求の範囲に記載された範囲内において、具体的な構成に対して種々の変更を加えうるものである。
【０１０２】
例えば、前記した各構成要素は、機能ブロックとして存在していればよく、独立したハードウエアとして存在しなくても良い。また、実装方法としては、ハードウエアを用いてもコンピュータソフトウエアを用いても良い。さらに、本発明における一つの機能要素が複数の機能要素の集合によって実現されても良く、本発明における複数の機能要素が一つの機能要素により実現されても良い。
【０１０３】
また、機能要素は、物理的に離間した位置に配置されていてもよい。この場合、機能要素どうしがネットワークにより接続されていても良い。グリッドコンピューティングにより機能を実現し、あるいは機能要素を構成することも可能である。
【図面の簡単な説明】
【０１０４】
【図１】本発明の第１実施形態に係るカラーヒストグラム生成装置の基本的な構成を示すブロック図である。
【図２】本発明の第１実施形態に係るカラーヒストグラム生成方法の全体的な流れを概略的に説明するためのフローチャートである。
【図３】第１実施形態における部分空間の生成方法を説明するためのフローチャートである。
【図４】第１実施形態において生成される部分空間の一例を示す説明図である。
【図５】第１実施形態におけるルックアップテーブル（一部分）の一例を示す説明図である。
【図６】第１実施形態におけるクラスタリングの実装例を説明するためのフローチャートである。
【図７】入力画像についてのカラーヒストグラムを生成する手順を説明するためのフローチャートである。
【図８】生成されたカラーヒストグラムの一例を示す説明図である。
【図９】第２実施形態におけるカラーヒストグラムの生成方法を説明するためのフローチャートである。
【符号の説明】
【０１０５】
１  部分空間生成部
２  ヒストグラム生成部
３  ルックアップテーブル生成部
４  ルックアップテーブル（色空間データベース）
６  色空間
７  クラスタ
８  クラスタの中心（部分空間の中心データ）
【図１】
2010072682.tif 000003
【図２】
2010072682.tif 000004
【図３】
2010072682.tif 000005
【図４】
2010072682.tif 000006
【図５】
2010072682.tif 000007
【図６】
2010072682.tif 000008
【図７】
2010072682.tif 000009
【図９】
2010072682.tif 000010
【図８】
2010072682.tif 000011
【手続補正書】
【提出日】平成20年9月29日(2008.9.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項８
【補正方法】変更
【補正の内容】
【請求項８】
前記部分空間生成部がクラスタリングする前記データ群は、前記色空間における格子点である
請求項７に記載のカラーヒストグラム生成装置。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９
【補正方法】変更
【補正の内容】
【請求項９】
前記部分空間生成部がクラスタリングする前記データ群は、前記色空間から抽出された代表点である
請求項７に記載のカラーヒストグラム生成装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
（項目８）
前記部分空間生成部がクラスタリングする前記データ群は、前記色空間における格子点である
項目７に記載のカラーヒストグラム生成装置。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
（項目９）
前記部分空間生成部がクラスタリングする前記データ群は、前記色空間から抽出された代表点である
項目７に記載のカラーヒストグラム生成装置。