(57)【特許請求の範囲】
【請求項１】
データ処理装置が複数の入力データの各々が属するクラスを決定するデータ処理方法であって、
計算手段が、入力データと複数の代表データの各々との距離を計算する計算工程と、
選択手段が、複数の距離計算方法から、前記入力データに基づいて距離計算方法を選択する選択工程と、
帰属手段が、前記選択工程で選択された距離計算方法を用いて前記計算工程で計算された前記複数の代表データの各々との距離に基づいて、当該複数の代表データの１つの属するクラスに前記入力データを帰属させる帰属工程と、を有することを特徴とするデータ処理方法。
【請求項２】
前記帰属工程では、前記帰属手段が前記複数の代表データの各々との距離のうち最短の距離が得られた代表データの属するクラスに前記入力データを帰属させることを特徴とする請求項１に記載のデータ処理方法。
【請求項３】
前記計算工程では、前記計算手段が前記入力データと複数の代表データの各々との距離を前記複数の距離計算方法のそれぞれを用いて計算し、
前記選択工程では、前記選択手段が、前記複数の距離計算方法のそれぞれを用いて算出された前記入力データと複数の代表データの各々との距離に基づいて、前記複数の距離計算方法のうちの１つを選択することを特徴とする請求項１に記載のデータ処理方法。
【請求項４】
前記計算工程では、前記計算手段が前記入力データと代表データとの距離を、複数の部分距離を統合することにより算出し、
前記複数の距離計算方法は、前記複数の部分距離の少なくとも一つに関する計算方法がそれぞれ異なっていることを特徴とする請求項１に記載のデータ処理方法。
【請求項５】
前記入力データは座標と特徴量から構成され、
前記計算工程では、前記計算手段が前記入力データと代表データとの距離を、前記座標の距離と前記特徴量の距離とを統合して前記距離を算出し、
前記複数の距離計算方法は、前記特徴量の距離の計算方法がそれぞれ異なり、前記座標の距離の計算方法は共通であることを特徴とする請求項４に記載のデータ処理方法。
【請求項６】
前記計算工程では、前記計算手段が前記複数の距離計算方法のそれぞれを用いて得られた距離を正規化し、
前記選択工程では、前記選択手段が、正規化された距離に基づいて距離計算方法を選択することを特徴とする請求項３に記載のデータ処理方法。
【請求項７】
前記選択工程では、前記選択手段が、それぞれの距離計算方法で算出された前記入力データと複数の代表データの各々との距離の分布の広がりに基づいて、距離計算方法を選択することを特徴とする請求項３に記載のデータ処理方法。
【請求項８】
前記選択工程では、前記選択手段が、前記分布の広がりとして、前記複数の代表データについて算出された複数の距離の最大値と最小値の差を用いることを特徴とする請求項７に記載のデータ処理方法。
【請求項９】
前記選択工程では、前記選択手段が、前記分布の広がりとして、前記複数の代表データについて算出された複数の距離の分散を用いることを特徴とする請求項７に記載のデータ処理方法。
【請求項１０】
解析手段が、所定の領域内の入力データを解析する解析工程をさらに有し、
前記選択工程では、前記選択手段が前記解析工程による解析の結果に基づいて使用する距離計算方法を選択し、
前記計算工程では、前記計算手段が前記選択工程で選択された距離計算方法を用いて入力データと複数の代表データの各々との距離を計算することを特徴とする請求項１に記載のデータ処理方法。
【請求項１１】
前記所定の領域とは、前記入力データを含む所定の大きさの領域であり、
前記解析工程では、前記解析手段が前記所定の領域内のすべての入力データについて解析を行うことを特徴とする請求項１０に記載のデータ処理方法。
【請求項１２】
前記代表データは、前記所定の領域内から選択された入力データであり、
前記解析工程では、前記解析手段が前記代表データについて解析を行うことを特徴とする請求項１０に記載のデータ処理方法。
【請求項１３】
前記解析工程では、前記解析手段が前記所定の領域内の入力データの統計量を算出することを特徴とする請求項１０乃至１２のいずれか１項に記載のデータ処理方法。
【請求項１４】
前記入力データは複数の成分から構成されており、前記統計量とは、前記所定の領域内のデータ間での各成分の差分の違いであることを特徴とする請求項１３に記載のデータ処理方法。
【請求項１５】
前記入力データは複数の成分から構成されており、前記統計量とは、前記所定の領域内のデータの各成分の分散の違いであることを特徴とする請求項１３に記載のデータ処理方法。
【請求項１６】
コンピュータに請求項１乃至１５のいずれか１項に記載のデータ処理方法の各工程を実行させるためのプログラム。
【請求項１７】
複数の入力データの各々が属するクラスを決定するデータ処理装置であって、
入力データと複数の代表データの各々との距離を計算する計算手段と、
前記入力データに基づいて距離計算方法を選択する選択手段と、
前記選択手段により選択された距離計算方法を用いて前記計算手段により計算された前記複数の代表データの各々との距離に基づいて、当該複数の代表データの１つの属するクラスに前記入力データを帰属させる帰属手段と、を備えることを特徴とするデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ処理方法及びデータ処理装置に関する
【背景技術】
【０００２】
近年、画像を色やテクスチャ、座標など属性が類似した複数の領域に分割する技術が注目されている。分割された領域はスーパーピクセルと呼ばれ、分割領域単位で符号化処理、画像処理、及び画像認識処理を実行できるため、様々な画像処理装置における応用が可能である。
【０００３】
従来、画像の領域分割に関して様々な手法が提案されている。特に、画素をクラスタリングすることによって画像を領域に分ける手法が多く提案されている。この手法は、色やテクスチャ、座標を要素にもつデータを要素間の距離に基づいてクラスタリングする。クラスタリングでは、各クラスタの代表データを求め、入力データを最近傍の代表データに割り当てる。このとき、入力データと複数の代表候補データの距離を計算して最近傍代表データを探索する。クラスタリングを用いた領域分割の先行技術として特許文献１、非特許文献１、２などが挙げられる。
【０００４】
非特許文献１では、ＳＬＩＣ（Simple Linear Iterative Clustering）と呼ばれるクラスタリング手法を用いて領域分割する方法が提案されている。ＳＬＩＣは、Ｋ−ｍｅａｎｓクラスタリングの最近傍代表データの探索範囲を画像中の局所領域に限定したものである。通常、入力データと各クラスの代表データとの距離計算にはユークリッド距離（Ｌ２距離）を用いるが、ユークリッド距離以外を用いる手法も提案されている。例えば、特許文献１では、データの各要素の重み付き距離を用いる手法が提案されている。また、非特許文献２では、Ｌ１距離とＬ∞距離の線形和を距離とする手法が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３６１１００６号公報
【非特許文献】
【０００６】
【非特許文献１】Radhakrishna Achanta, et al., “SLIC Superpixels Compared to State-of-the-Art Superpixel Methods,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, No. 11, pp.2274-2282, Nov.2012.
【非特許文献２】“Algorithmic Transformations in the Implementation of K-means Clustering on Reconfigurable Hardware”, Proceeding of International Symposium on Field Programmable Gate Arrays, pp. 103-110, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
先に述べたように、クラスタリングは画像の領域分割においてよく用いられる技術である。領域分割では、色やテクスチャの特性が異なる領域が分割されていることが重要である。そのため、クラスタリングにおいては、入力データと色やテクスチャの特性が類似した領域内の代表候補データとの距離は小さく、逆に入力データと色やテクスチャの特性が異なる領域内の代表候補データとの距離は大きいことが好ましい。
【０００８】
非特許文献１の方式では、色距離と座標距離の線形和を総合的な距離とする。非特許文献１において、色距離と座標距離はいずれもユークリッド距離である。しかし、色距離の計算にユークリッド距離を用いると、色の特性が異なる領域同士であっても色距離がそれほど大きくならない場合がある。例えば、領域同士で少数の色成分のみが大きく異なり、他の多数の色成分の違いが小さい場合である。この場合、多数の色成分の違いが小さいために色距離全体としてはそれほど大きくならないため、そのような領域間では境界精度が劣化するという課題がある。
【０００９】
特許文献１の方式では、距離の算出においてすべての要素（色成分）に異なる重みを設定することが可能であるため、ユークリッド距離を使用するよりも境界精度が向上する場合があると考えられる。また、非特許文献２の方式では、Ｌ１距離及びＬ∞距離というユークリッド距離とは特性の異なる距離計算方法を使用するため、ユークリッド距離を使用するよりも境界精度が向上する場合があると考えられる。しかし、これらの方式はいずれも入力データの特性を考慮しておらず、入力データに関わらず重みあるいは線形和の係数が固定されているため、処理対象の画像によっては境界精度が劣化する場合があるという課題がある。
【００１０】
本発明は上述した課題に鑑みてなされたものであり、入力データに応じて適切なクラスタリングを行えるようにすることを目的とする。
【課題を解決するための手段】
【００１１】
上記課題を解決するための本発明の一態様によるデータ処理方法は、
データ処理装置が複数の入力データの各々が属するクラスを決定するデータ処理方法であって、
計算手段が、入力データと複数の代表データの各々との距離を計算する計算工程と、
選択手段が、複数の距離計算方法から、前記入力データに基づいて距離計算方法を選択する選択工程と、
帰属手段が、前記選択工程で選択された距離計算方法を用いて前記計算工程で計算された前記複数の代表データの各々との距離に基づいて、当該複数の代表データの１つの属するクラスに前記入力データを帰属させる帰属工程と、を有する。
【発明の効果】
【００１２】
本発明によれば、入力データの特性に応じて代表候補データとの距離計算方法を変更することにより、入力データに応じた精度の高いクラスタリングが可能となる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施形態のクラスタリング方法を示すフローチャート。
【図２】最近傍代表データの探索範囲を説明する図。
【図３】入力データと代表候補データの色成分の例を示す図。
【図４】データ処理装置の構成を示すブロック図。
【図５】第２の実施形態の距離計算方法の選択方法を示すフローチャート。
【図６】第２の実施形態の最近傍データ探索方法を示すフローチャート。
【図７】第３の実施形態の距離計算方法の選択方法を示すフローチャート。
【発明を実施するための形態】
【００１４】
以下、添付の図面を参照して本発明の好適な実施形態について説明する。なお、本実施形態では、本発明によるクラスタリング方法を用いて画像を領域分割する例について説明する。
【００１５】
［第１の実施形態］
＜データ処理装置の構成例＞
図４は、第１実施形態によるクラスタリング方法を実現可能なデータ処理装置の一構成例を示すブロック図である。以下では、図１のフローチャート等を参照して説明される各処理をＣＰＵにより実現する構成を説明するが、処理の一部が専用のハードウエアにより実現されてもよことは言うまでもない。
【００１６】
データ保存部４０１は、たとえばハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＣＤ−ＲやＤＶＤ、メモリーカード、ＣＦカード、スマートメディア、ＳＤカード、メモリスティック、ｘＤピクチャーカード、ＵＳＢメモリ等で構成される。データ保存部４０１にはクラスタリング（あるいは領域分割）の対象となる画像が保存されるが、画像の他にも、プログラムやその他のデータを保存することも可能である。なお、後述するＲＡＭ４０６の一部をデータ保存部４０１として用いるようにしても良い。またあるいは、後述する通信部４０２により接続した先の機器の記憶装置を通信部４０２を介して利用することによりデータ保存部４０１が構成されても良い。表示部４０３は、領域分割処理前、領域分割処理後の画像を表示、あるいはＧＵＩ等の画像を表示する装置で、一般的にはＣＲＴや液晶ディスプレイなどが用いられる。あるいは、ケーブル等で接続された装置外部のディスプレイ装置を表示部４０３として用いても構わない。
【００１７】
ＣＰＵ４０４は本実施形態に係る主要な処理を実行すると共に本装置全体の動作を制御する。ＲＯＭ４０５とＲＡＭ４０６は、その処理に必要なプログラム、データ、作業領域などをＣＰＵ４０４に提供する。後述する処理に必要なプログラムがデータ保存部４０１に格納されている場合や、ＲＯＭ４０５に格納されている場合には、一旦、ＲＡＭ４０６に読み込まれてから実行される。また通信部４０２を経由してデータ処理装置が外部記憶装置からプログラムを受信する場合には、一旦、データ保存部４０１に記録した後にＲＡＭ４０６に読み込まれるか、通信部４０２からＲＡＭ４０６に直接読み込まれてから実行される。
【００１８】
ＣＰＵ４０４は、データ保存部４０１に格納されている処理対象の画像をＲＡＭ４０６に書き込んだ後、ＲＡＭ４０６から画像を読み出してクラスタリング処理を実行する。代表候補データ等の処理途中のデータは、ＣＰＵ４０４によりＲＡＭ４０６に書き込まれ、必要に応じて読み出される。そして、クラスタリング処理結果をＲＡＭ４０６に書き込む。あるいは、表示部４０３に表示する。またあるいは、通信部４０２を介して外部装置に送信する。なお、図４においては、ＣＰＵが１つ（ＣＰＵ４０４）だけである構成だが、これを複数設けるような構成にしても良いことは明らかである。
【００１９】
通信部４０２は、機器間の通信を行うための通信Ｉ／Ｆとして機能する。この通信Ｉ／Ｆには例えば、公知のローカルエリアネットワーク、ＵＳＢ、ＩＥＥＥ１２８４、ＩＥＥＥ１３９４、電話回線などの有線など、各種の通信方式をもちいることができる。あるいは、通信Ｉ／Ｆには、赤外線（ＩｒＤＡ）、ＩＥＥＥ８０２．１１ａ、ＩＥＥＥ８０２．１１ｂ、ＩＥＥＥ８０２．１１ｇ、ＩＥＥＥ８０２．１１ｎ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、ＵＷＢ（Ｕｌｔｒａ  Ｗｉｄｅ  Ｂａｎｄ）等の無線通信方式が用いられても良い。
【００２０】
なお、図４ではデータ保存部４０１や表示部４０３が全て１つのデータ処理装置内に含まれているが、これに限られるものではない。すなわち、これらの構成が公知の通信方式による通信路で接続され、全体としてこのような構成となっているのであっても構わない。なお、システム構成については、上記以外にも様々な構成要素が存在するが、本発明の主眼ではないのでその説明は省略する。以下、図４に示したデータ処理装置が処理する内容について説明する。フローチャート中の各ステップはＣＰＵ４０４の動作を示す。
【００２１】
＜領域分割のためのクラスタリング＞
図１は本実施形態におけるクラスタリング方法を示すフローチャートである。本実施形態のクラスタリング方法は、入力データセットに含まれる複数の入力データの各々が属するクラスを、代表データとの距離に基づいて決定する。以下では、入力データセットとして画像を、入力データとしてその画像を構成する画素を扱う。まず、クラスタリング対象のデータについて説明する。［数１］は第ｉ番目の入力データを示す。入力データは画像中の画素と対応するピクセルデータであり、５次元のベクトルである。
【数１】
0006418841.tif 000002
ｘｉ，１、ｘｉ，２は二次元の座標空間上の位置であり、画像の縦方向と横方向の座標値を意味する。ｘｉ，３、ｘｉ，４、ｘｉ，５は三次元の色特徴である。
【００２２】
ステップＳ１０１では、ＣＰＵ４０４は、代表データを初期化して生成する。具体的には、図２に示したクラスタリング処理対象の画像２０１を座標空間上のブロックに分割し、各ブロック２０３の中に１個の代表データ２０５を配置する。ブロック２０３内の入力データをランダムに選択し、選択した入力データの座標と色特徴のベクトルを、クラスを代表する代表データのベクトルとする。［数２］は第ｊ番目の代表データを示す。
【数２】
0006418841.tif 000003
ｃｊ，１、ｃｊ，２は二次元の座標空間上の位置であり、画像の縦方向と横方向の座標値を意味する。ｃｊ，３、ｃｊ，４、ｃｊ，５は三次元の色特徴である。
【００２３】
ステップＳ１０２では、最大繰り返し回数を設定し、繰り返し計算のループが開始される。ステップＳ１０３では、入力データのループが開始される。ＣＰＵ４０４は、画像の中の入力データＸｉの順番ｉを制御しながら、ステップＳ１０４からステップＳ１０６までの処理を繰り返して全ての入力データをクラスタリングする。ステップＳ１０４では、ＣＰＵ４０４は、探索範囲を設定する。より具体的には、入力データの座標位置によって代表候補データの探索範囲（たとえば、図２の探索範囲２０２）を設定する。なお、入力データの代表候補データとは、該当入力データを割り当てる（帰属させる）代表データの候補であり、設定された探索範囲内の代表データである。
【００２４】
本実施形態では、探索範囲２０２として５×５のブロック２０３の範囲、すなわち探索範囲２０２が幅と高さ方向にそれぞれ５個の代表データを有する例について説明する。注目入力データ２０６が入っているブロック２０４を中心に、最近傍代表データの探索範囲２０２を設定する。この場合、探索範囲２０２は５×５個の座標近傍の代表データである。図２に示した例では、探索範囲２０２の代表データは縦方向インデックスが５から９までであり、縦方向インデックスが６から１０までである。本実施形態では、注目入力データ２０６を含め、ブロック２０４の範囲に入っている全ての入力データの探索範囲２０２は同じとなる。なお、入力データの位置と探索範囲の代表候補データの関係は最初に固定され、繰り返し処理によって代表データが更新されることで代表データの位置が変わっても、代表データのインデックスは変わらない。
【００２５】
ステップＳ１０５では、最近傍代表データの探索が行われる。入力データの最近傍代表データとは、該当入力データとの距離が最短な代表データ、即ち、距離空間上一番近い代表データである。ステップＳ１０５の探索処理の詳細については、図１の右側のフローチャートの参照により後述する。ステップＳ１０６では、ＣＰＵ４０４は、最近傍代表データの探索結果（ステップＳ１０５）に基づいて、入力データを上述した最近傍代表データに帰属させる。ステップＳ１０７では、ＣＰＵ４０４は、全ての入力データを処理したかどうかを判定する。全ての入力データを処理したと判定された場合は、ＣＰＵ４０４は入力データループを終了し、処理はステップＳ１０８に進む。未処理の入力データが存在する場合は、処理はステップＳ１０４に戻り、次の入力データについて上述した処理を開始する。
【００２６】
ステップＳ１０８では、ＣＰＵ４０４は、各代表データに対して、帰属させた入力データのベクトルの平均ベクトルを計算する。その平均ベクトルを該当代表データの新しいベクトルＣｊとし、代表データを更新する。ステップＳ１０９では、ＣＰＵ４０４は、最大繰り返し回数を超えるかどうか、又はクラスタリングの結果が収束するかどうかといった終了条件を満足するか否かを判定する。終了条件が満たされた場合は、ＣＰＵ４０４は、繰り返し計算を終了する。終了条件が満たされていない場合は、処理はステップＳ１０３に戻り、ＣＰＵ４０４は、次の繰り返し計算を開始する。クラスタリング処理が終了すると、クラスタリング処理の結果が領域分割の結果として出力される。
【００２７】
＜最近傍代表データ探索＞
次に、ステップＳ１０５において実行される最近某代表データ探索の処理について図１の右側のフローチャートを参照して説明する。以下、ステップＳ１２１〜Ｓ１２７では、第ｉ番目の入力データＸｉに対して、距離が最短である代表データが代表候補データの中から探索される。まず、ステップＳ１２１〜Ｓ１２５では、入力データと複数の代表候補データの各々との距離が複数の距離計算方法を用いて計算される。そして、ステップＳ１２６では、複数の距離計算方法を用いて算出された距離に基づいて複数の距離計算方法のうちの１つが選択される。こうして、入力データに応じた距離計算方法の選択が行われることになる。ステップＳ１２７では、選択された距離計算方法により算出された距離に基づいて最近傍代表データを決定する。
【００２８】
各ステップにおける処理内容を説明する前に、本実施形態における入力データと代表候補データとの距離計算方法について説明する。［数３］は第ｉ番目の入力データと、第ｊ番目の代表候補データとの距離計算式である。
【数３】
0006418841.tif 000004
【００２９】
ｉ番目の入力データと代表候補データとの距離は、複数の部分距離が統合されたものであり、本実施形態では、座標空間上の距離と色空間上の距離が統合される。［数３］において、Ｄｓは座標空間上の距離（部分距離）であり、Ｄｃは色空間上の距離（部分距離）である。Ｗは座標空間上の距離に対する重みである。本実施形態では、［数３］が示すように、入力データと代表候補データとの距離は、ＤｓとＤｃの線形結合により算出される。以降では、このように複数の部分距離から算出される距離のことを総合距離と呼ぶ。
【００３０】
本実施形態によるクラスタリング方法では、複数の距離計算方法の中から、入力データに応じて使用する距離計算方法を選択する。また、複数の部分距離から総合距離を算出する場合、それらのうちの少なくとも一つの部分距離に対して距離計算方法を選択する。本実施形態では、座標空間上の距離Ｄｓの距離計算方法としてユークリッド距離（Ｌ２距離）の一種類を使用する。また、色空間上の距離Ｄｃの距離計算方法としてマンハッタン距離（Ｌ１距離）とチェビシェフ距離（Ｌ∞距離）の二種類を使用する。
【００３１】
［数４］はＬ２距離によるＤｓの計算式である。また、[数５]および［数６］はそれぞれＬ１距離、Ｌ∞距離によるＤｃの計算式である。
【数４】
0006418841.tif 000005
【数５】
0006418841.tif 000006
【数６】
0006418841.tif 000007
なお、Ｈ１，Ｈ∞はそれぞれＬ１距離、Ｌ∞距離を正規化するための係数である。
【００３２】
これらの距離計算方法を使用する理由について説明する。まず、座標空間上の距離にはユークリッド距離（Ｌ２距離）が使用される。領域分割において、座標空間上の距離は画像上での画素と代表候補データとの直線距離を示すことが好ましいからである。一方、色空間上の距離については、マンハッタン距離（Ｌ１距離）とチェビシェフ距離（Ｌ∞距離）から選択された距離が用いられる。領域分割では、入力データと色の特性が類似した領域内にある代表候補データとの色距離は小さく、逆に色の特性が異なる領域内にある代表候補データとの色距離は大きいことが好ましい。色の特性が異なる領域間では、少数の色成分のみが大きく異なる場合と、多数の色成分が同程度に異なる場合がある。
【００３３】
［数７］はＬｐ距離（ｐ＝１，２、．．．，∞）によるＤｃの計算式である。
【数７】
0006418841.tif 000008
［数７］に示されるように、Ｌｐ距離では、ｐの値が小さい場合は、各成分の指数の値が小さいため、Ｄｃの値は各成分の差の平均値に近くなる。逆に、ｐの値が大きい場合は、Ｄｃの値は各成分のうち、差の大きい少数の成分による影響が大きくなる。
【００３４】
したがって、
・少数の色成分のみが大きく異なる場合にはｐの値が大きいＬｐ距離を使用し、
・多数の色成分が同程度に異なる場合にはｐの値が小さいＬｐ距離を使用する、
ことにより、一つのＬｐ距離を使用するよりも入力データと色の特性が類似した領域内の代表候補データとの色距離と、色の特性が異なる領域内の代表候補データとの色距離の差が大きくなる。本実施形態では特に、ｐ＝１及びｐ＝∞として、［数５］および［数６］に示した距離計算方法を使用する。ただし、Ｌｐ距離はｐの値により値の範囲が異なるため、Ｌｐ距離を正規化する。本実施形態では、各Ｌｐ距離の最大値が同じ値となるように正規化する。すなわち、Ｌ１距離の最大値は２５５×３であり、Ｌ∞距離の最大値は２５５であるため、Ｈ１＝１、Ｈ∞＝３とする。
【００３５】
図３は入力データと代表候補データの色成分（Ｌａｂ色空間で表される色成分）の例を示す図である。図３を用いて、色距離の計算方法としてＬ１距離、Ｌ∞距離を選択する効果について説明する。図３（ａ）は領域間で少数の色成分のみが大きく異なる場合の例であり（Ｌ成分のみが大きく異なる）、図３（ｂ）はすべての色成分が同程度に異なる場合の例である。図３（ａ）において、入力データ３０１と色の特性が類似した領域内の代表候補データ３０２、色の特性が異なる代表候補データ３０３との色距離は、Ｌ１距離及びＬ∞距離それぞれに対して以下のようになる。
【００３６】
・入力データ３０１と代表候補データ３０２との色距離
−Ｌ１距離：４０（＝｜150−130｜＋｜100−90｜＋｜120−110｜）
−Ｌ∞距離：２０（＝ｍａｘ（｜150−130｜、｜100−90｜、｜120−110｜））
・入力データ３０１と代表候補データ３０３との色距離
−Ｌ１距離：１５０（＝｜150−10｜＋｜100−90｜＋｜120−120｜）
−Ｌ∞距離：１４０（＝ｍａｘ（｜150−10｜、｜100−90｜、｜120−120｜））
【００３７】
したがって、代表候補データ３０２、３０３との正規化された色距離の差はＬ１距離では１１０、Ｌ∞距離では１２０×３＝３６０となる。すなわち、少数の色成分のみが異なる場合にはＬ∞距離を選択することにより、色の特性が類似した領域内の代表候補データとの色距離と、色の特性が異なる領域内の代表候補データとの色距離との差が大きくなることが分かる。
【００３８】
一方、図３（ｂ）において、入力データ３０４と色の特性が類似した領域内の代表候補データ３０５、色の特性が異なる代表候補データ３０６との色距離は、Ｌ１距離及びＬ∞距離それぞれに対して以下のようになる。
・入力データ３０４と代表候補データ３０５との色距離
−Ｌ１距離：４０（＝｜150−130｜＋｜100−90｜＋｜120−110｜）
−Ｌ∞距離：２０（＝ｍａｘ（｜150−130｜、｜100−90｜、｜120−110｜））
・入力データ３０４と代表候補データ３０６との色距離
−Ｌ１距離：１４０（＝｜150−100｜＋｜100−60｜＋｜120−70｜）
−Ｌ∞距離：５０（＝ｍａｘ（｜150−100｜、｜100−60｜、｜120−70｜））。
【００３９】
図３（ａ）の場合と同様に正規化して比較すると、代表候補データ３０５、３０６との色距離の差はＬ１距離では１００、Ｌ∞距離では３０×３＝９０となる。すべての色成分が同程度に異なる場合にはＬ１距離を選択することにより、色の特性が類似した領域内の代表候補データとの色距離と、色の特性が異なる領域内の代表候補データとの色距離との差が大きくなることが分かる。
【００４０】
以下、図１のステップＳ１２１〜Ｓ１２７における処理内容について説明する。ステップＳ１２１では距離計算方法のループが開始される。ＣＰＵ４０４は、距離計算方法の順番ｋを制御し、ステップＳ１２２からステップＳ１２４までを全ての距離計算方法を用いて処理する。本実施形態では、Ｄｃの算出に、［数５］を使用する場合と［数６］を使用する場合の二種類の距離計算方法を使用する。なお、Ｄｓの算出にはいずれの場合も［数４］が用いられる。
【００４１】
ステップＳ１２２では、代表候補データのループが開始される。ＣＰＵ４０４は、代表候補データＣｊの順番ｊを制御し、全ての代表候補データを探索する。ステップＳ１２３では、入力データと複数の代表データの各々との間の距離が計算される。すなわち、ＣＰＵ４０４は、第ｉ番目の入力データと第ｊ番目の代表候補データとの総合距離を第ｋ番目の距離計算方法を用いて算出する。ステップＳ１２４では、ＣＰＵ４０４は、全ての代表候補データとの距離計算が完了したかどうかを判定する。全ての代表ｊ候補データについて距離計算が完了したと判定された場合は、処理はステップＳ１２５に進み、ＣＰＵ４０４は、代表候補データのループを終了する。一方、未処理の代表データがあると判定された場合は、処理はステップＳ１２３に戻り、ＣＰＵ４０４は、次の代表候補データとの総合距離を計算する。
【００４２】
ステップＳ１２５では、全ての距離計算方法を用いた処理が完了したかどうかを判定する。全ての距離計算方法を用いた処理が完了したと判定された場合は、処理はステップＳ１２６に進み、距離計算方法のループが終了する。一方、未処理の距離計算方法が存在すると判定された場合は、処理はステップＳ１２２に戻り、ＣＰＵ４０４は、次の距離計算方法を用いて入力データと代表候補データとの総合距離を算出する。
【００４３】
ステップＳ１２６では、次のステップＳ１２７において使用する距離計算方法を選択する。本実施形態では、Ｄｃに対して［数５］を含む距離計算方法または［数６］を含む距離計算方法のいずれを用いて算出した距離計算結果を使用するかを選択することで距離計算方法の選択を行っている。換言すれば、部分距離Ｄｃとして、［数５］または［数６］のいずれの計算方法を用いて得られた結果を採用するかが選択される。なお、Ｄｓの距離計算方法は［数４］に示した一種類であるため、距離計算結果の選択はしない。前述したように、[数５]と[数６]のうち、色の特性が類似した領域内の代表候補データとの色距離と、色の特性が異なる領域内の代表候補データとの色距離の差が大きくなる距離計算方法を選択することが好ましい。そのため、本実施形態では、それぞれの距離計算結果のうち、代表候補データ間の分布の広がりが大きい方の距離計算結果を選択する。
【００４４】
式（８）は、本実施形態における、代表候補データ間の色距離の広がりＲを算出する計算式である。
【数８】
0006418841.tif 000009
Ｓｉは、第ｉ番目の入力データに対する代表候補データの集合を示す。
【００４５】
ステップＳ１２６において、ＣＰＵ４０４は各距離計算方法によって得られた距離計算結果について［数８］のＲを算出し、Ｒが最大となる距離計算結果を提供した距離計算方法を選択する。ステップＳ１２７では、ＣＰＵ４０４は、ステップＳ１２６において選択した距離計算方法により算出された距離（［数３］により算出された距離）のうち、最短の距離となる代表候補データを、入力データＸｉを帰属させるべき最近傍代表データに決定する。
【００４６】
以上説明したように、第１実施形態のクラスタリング方法によれば、入力データと代表候補データとの総合距離を複数の距離計算方法を用いて計算した後に、代表候補データ間での広がりが大きい距離計算結果が選択される。したがって、例えば、入力データに関わらず固定された距離計算方法が使用される場合よりも、色の特性が類似した領域内の代表候補データとの距離と、色の特性が異なる代表候補データとの距離の差が大きくなるため、領域分割の境界精度が向上する。
【００４７】
なお、第１の実施形態では、入力データが座標と特徴量から構成され、入力データと代表データの距離（総合距離）を、座標の距離と特徴量の距離という２つの部分距離を統合することで算出した。ここで、複数の距離計算式が適用されるのは特徴量による部分距離であり、座標による部分距離の計算方法は複数の距離計算方法において共通であった。しかしながら、複数の距離計算方法はこれに限られるものではない。たとえば、座標の距離にも複数の計算方法が適用されてもよい。また、複数の距離計算式が適用されるさらに別の部分距離が総合距離に含まれるようにしてもよい。複数の部分距離を統合することにより総合距離を算出する距離計算方法において、複数の部分距離の少なくとも一つに対する計算方法が異なる複数の距離計算方法であればよい。なお、複数の計算方法が適用可能な部分距離が複数存在する場合には、それぞれの部分距離に関して分布の広がりが大きい計算方法（たとえばＲが最大となる計算方法）が選択される。
【００４８】
［第２の実施形態］
第１の実施形態では、複数種類の距離計算方法を用いた距離計算結果から適切な距離計算方法を特定した。第２の実施形態では、入力データの統計量に基づいて（たとえば、所定範囲内の入力データの統計量に基づいて）、使用する距離計算方法を選択する。なお、第２実施形態によるデータ処理装置の構成は第１の実施形態（図４）と同様である。また、第２実施形態によるクラスタリング処理の全体的な流れでは図１に示されるフローチャートにおいて、ステップＳ１０２以降の処理に先立って距離計算方法の選択が実行される。図５は第２の実施形態における距離計算方法の選択方法を示すフローチャートである。フローチャート中の各ステップはＣＰＵ４０４の動作を示しており、本実施形態ではステップＳ１０１の前に実行されるものとする。
【００４９】
ステップＳ５０１では、ＣＰＵ４０４は、距離計算方法を選択する単位となる距離選択領域と、その距離選択領域における距離計算方法の選択のために使用する参照領域を設定する。同じ距離選択領域内の入力データに対しては同じ距離計算方法を使用する。本実施形態では、距離選択領域内の入力データに対する代表候補データの値に影響を与える入力データの統計量を基に距離計算方法を選択するために、代表候補データが含まれる領域を参照領域として設定する。したがって、図２に示した例では、ブロック２０４が距離選択領域であり、探索範囲２０２（距離選択領域（ブロック２０４）を中心とした５×５ブロックの範囲）が参照領域である。
【００５０】
ステップＳ５０２では、距離選択領域のループが開始される。ＣＰＵ４０４は、距離選択領域の順番ｒを制御し、ステップＳ５０３からステップＳ５０５までを繰返すことにより、全ての距離選択領域に対して距離計算方法を選択する。ステップＳ５０３では、ＣＰＵ４０４は、第ｒ番目の距離選択領域に対する参照領域内の入力データを解析して統計量を算出する。具体的には、参照領域内の入力データ間の色ベクトルの差分の大きさが特定の成分に偏っている度合いを算出する。［数９］は、本実施形態における上記統計量を算出する計算式の一例である。
【００５１】
【数９】
0006418841.tif 000010
ここで、Ｉｒは第ｒ番目の参照領域に含まれる入力データの集合を示す。また、Ｖ（Ｘｍ，Ｘｎ）は、［数１０］により算出される。
【数１０】
0006418841.tif 000011
【００５２】
［数１０］において、｜ｘｍ，ｕ−ｘｎ，ｕ｜は第ｕ番目の色成分の差分であり、｜ｘｍ，ｖ−ｘｎ，ｖ｜は第ｖ番目の色成分の差分である。各色成分の差分の違いの総和を計算することにより、Ｖ（Ｘｍ，Ｘｎ）の値は、２つの入力データ間で一部の色成分のみが大きく異なる場合には大きな値となり、逆に多数の色成分が同程度に異なる場合には小さな値となる。
【００５３】
多数の色成分が同程度に異なる場合の例として、（Ｘｍ，３，Ｘｍ，４，Ｘｍ，５）＝（１５０，１００，１２０）、（Ｘｎ，３，Ｘｎ，４，Ｘｎ，５）＝（１００，６０，７０）の場合、Ｖ（Ｘｍ，Ｘｎ）＝２０（＝||150−100|−|100−60||＋||150−100|−|120−70||＋||100−60|−|120−70||））となる。また、一部の色成分のみが大きく異なる場合の例として、（Ｘｍ，３，Ｘｍ，４，Ｘｍ，５）＝（１５０，１００，１２０）、（Ｘｎ，３，Ｘｎ，４，Ｘｎ，５）＝（１０，９０，１２０）の場合、Ｖ（Ｘｍ，Ｘｎ）＝２８０（＝||150−10|−|100−90||＋||150−10|−|120−120||＋||100−90|−|120−120||）となる。
【００５４】
ステップＳ５０４では、ＣＰＵ４０４は、ステップＳ５０３において計算したＶの値を基に距離計算方法を選択する。ここで、Ｖの値が大きければ参照領域内の入力データは一部の色成分のみが大きく異なり、逆にＶの値が小さければ参照領域内の入力データは多数の色成分が同程度に異なるといえる。そのため、前者の場合にはＬ∞距離が選択され、後者の場合にはＬ１距離が選択される。本実施形態では、Ｖの値と閾値Ｔｈの比較結果を基に色距離の計算方法が選択される。具体的には、ＣＰＵ４０４は、Ｖ≧Ｔｈの場合にはＬ∞距離を選択し、Ｖ＜Ｔｈの場合にはＬ１距離を選択する。そして、選択した距離計算方法を距離選択領域の番号ｒと関連付けてＲＡＭ４０６に格納する。ステップＳ５０５では、ＣＰＵ４０４は、すべての距離選択領域に対して距離計算方法を選択したかどうかを判定する。すべての距離選択領域に対して距離計算方法が選択された場合は距離計算方法の選択処理を終了する。未処理の距離選択領域がある場合は、処理はステップＳ５０３に戻り、ＣＰＵ４０４は、次の距離選択領域に対して距離計算方法を選択する。
【００５５】
以上の処理により各距離選択領域の距離計算方法を選択した後、ステップＳ１０１〜Ｓ１０９により入力データを順次クラスタリングする。ただし、第２実施形態では使用する距離計算方法が選択されているので、第１の実施形態とはステップＳ１０５における最近某代表データ探索処理が異なる。図６は第２の実施形態における最近傍データ探索方法を示すフローチャートである。
【００５６】
ステップＳ６０１では、ＣＰＵ４０４は、ステップＳ５０４によりＲＡＭ４０６に格納した各距離選択領域に対する距離計算方法に従って第ｉ番目の入力データに対して使用する距離計算方法を設定する。具体的には、ＣＰＵ４０４は、入力データの座標情報ｘｉ，１、ｘｉ，２を基に、入力データが属する距離選択領域を判定し、その距離選択領域に対してステップＳ５０４で選択された距離計算方法を設定する。ステップＳ１２２〜Ｓ１２４では、ＣＰＵ４０４は、ステップＳ６０１で設定された距離計算方法を用いて、第１の実施形態と同様に第ｉ番目の入力データと代表候補データとの距離を計算する。そして、ステップＳ１２７において、ＣＰＵ４０４は、算出された距離のうち最短の距離である代表候補データを第ｉ番目の入力データに対する再近傍代表データに決定する。
【００５７】
以上説明したように、第２の実施形態によれば、参照領域内の入力データの統計量を基に、距離選択領域内の入力データに対して使用する距離計算方法が選択される。所定の領域内の入力データの特性に応じて距離計算方法を選択することにより、１つの距離計算方法を使用するよりも領域分割の境界精度が向上する。また、距離計算方法を決定してから距離を計算するので、第１の実施形態よりも距離計算に関わる計算量は減少する。
【００５８】
［第３の実施形態］
第２の実施形態では、所定の領域内の入力データ全てを用いて統計量を算出し、算出された統計量に基づいて距離計算方法を選択したが、これに限られるものではない。所定の領域内の入力データから選択された入力データを用いて統計量を算出し、これに基づいて距離計算方法を選択するようにしてもよい。たとえば、各距離選択領域（ブロック）から所定数の入力データ（たとえば、１画素おき、１ラインおき）を選択して統計量の算出に用いるようにしてもよい。以下、第３の実施形態では、所定の領域内の代表データ（代表候補データ）を基に使用する距離計算方法を選択する例を説明する。
【００５９】
図７は第３実施形態における距離計算方法の選択方法を示すフローチャートである。フローチャート中の各ステップはＣＰＵ４０４の動作を示している。本処理は、代表データを設定した後、すなわち、図１（ａ）のステップＳ１０２とステップＳ１０３の間に実行される。つまり、各繰返しループの最初に、前回の繰返しループにおいて生成した代表データを用いて距離計算方法を選択する。
【００６０】
図７に示される処理は、第２実施形態の距離計算方法の選択（図５）と同様であるが、ステップＳ７０１における統計量の算出方法が異なる。すなわち、ステップＳ７０１では、第ｒ番目の距離選択領域に対する参照領域内の代表データを解析して統計量を算出する。［数１１］は、第３の実施形態における統計量を算出する式である。
【数１１】
0006418841.tif 000012
Ｓｒは第ｒ番目の参照領域に含まれる代表データの集合を示す。なお、Ｖ（Ｃｍ，Ｃｎ）は式［数１０］と同じ計算式により算出される。また、その他の処理は、第１、第２実施形態と同様である。
【００６１】
以上説明したように、第３の実施形態によれば、参照領域内の代表データの統計量を基に、距離選択領域内の入力データに対して使用する距離計算方法が選択される。入力データよりも数の少ない代表データを用いることにより、第２の実施形態に比べて計算量を少なくすることができる。
【００６２】
［他の実施形態］
第１の実施形態では、代表候補データ間の距離計算結果の分布の広がりをＤｃの距離計算結果の最大値と最小値との差により算出する（［数８］）としたが、これに限られるものではない。たとえば、距離計算結果の分散に基づいて分布の広がりを判定してもよい。あるいは、四分位範囲のように、上位及び下位の距離計算結果を除いた上での最大値と最小値の差としてもよい。
【００６３】
また、第１の実施形態では、繰返し計算のループ毎に距離計算結果を選択するとしたが、これに限る訳ではない。例えば、一つの処理対象のブロック（ブロック２０４）について最初のＬ回（Ｌ≧１）のループにおいてのみ距離計算結果を選択し、当該ブロックの以降の繰返し計算のループではＬ回目のループにおいて選択した距離計算方法を使用するようにしてもよい。
【００６４】
また、第１の実施形態では、異なる距離計算方法の最大値が同じ値になるように正規化するとしたが、正規化の方法はこれに限られるものではない。たとえば、学習用の画像セットを用意し、それらの画像セットに対して最も境界精度が良くなるように正規化してもよい。
【００６５】
第２、第３の実施形態では、参照領域内の入力データ（第２の実施形態ではすべての入力データ、第３の実施形態では代表データ）間の色ベクトルの差分の大きさが特定の成分に偏っている度合いを［数９］〜［数１１］により算出した。しかしながら、統計量の算出方法はこれに限られるものではない。例えば、［数１０］における差の代わりに比を用いてもよい。あるいは、参照領域内のデータの各成分の分散を算出し、各成分の分散の差もしくは比を統計量としてもよい。
【００６６】
また、第２、第３の実施形態では、参照領域内の入力データ（第２の実施形態ではすべての入力データ、第３の実施形態では代表データ）のすべての組み合わせに対して各成分の差分の違いを算出するとしたが、これに限られるものではない。たとえば、参照領域内の入力データの平均を算出し、その平均と参照領域内の各データとの比較により各成分の差分の違いを算出してもよい。あるいは、参照領域内の１つまたは複数の入力データあるいは代表データを選択し、選択したデータと参照領域内の各入力データとの比較により各成分の差分の違いを算出してもよい。
【００６７】
また、第２、第３の実施形態では、距離選択領域と参照領域は異なる領域であるとしたが、同じ領域であっても良い。
【００６８】
また、第１〜第３の実施形態では、Ｌ１距離とＬ∞距離のうちから使用する距離計算方法を選択するとしたが、これに限る訳ではなく、他のＬｐ（ｐ＝１，２，．．．，∞）距離を選択できるようにしてもよい。また、使用するＬｐ距離の数は２種類に限る訳ではなく、任意の数であってもよい。なお、Ｌｐ距離を計算する際には、［数５］、［数６］と同様に、正規化のための係数Ｈｐが乗算される。係数Ｈｐの値は、たとえば、使用するすべてのＬｐ距離の最大値が同じ値となるように設定される。
【００６９】
Ｑ種類（Ｑ≧２）のＬｐ距離を使用する場合の例について説明する。第１の実施形態では、Ｑ種類のＬｐ距離のうち、［数８］によって算出されるＲの値が最大となる距離計算方法を選択すればよい（ステップＳ１２６）。第２、第３の実施形態では、Ｑ−１個の閾値Ｔｈｑ（ｑ＝１，２，．．．，Ｑ−１）を用いて、［数９］あるいは［数１０］により算出されるＶの値が大きい程、ｐの値が大きいＬｐ距離が選択されるようにすればよい。
【００７０】
なお、第１〜第３の実施形態では、最大値が同じ値となるようにＬｐ距離を正規化するとしたが、これに限る訳ではなく、前回の繰返しループにおいて算出された各Ｌｐ距離の最大値が同じ値となるように正規化してもよい。
【００７１】
また、第１〜第３の実施形態では、Ｌｐ距離を使用するとしたが、これ以外の距離計算方法を使用しても良い。［数１２］は各成分の差に重み係数を掛けて足し合わせることにより第ｉ番目の入力データと、第ｊ番目の代表候補データとの色距離を算出する計算式である。
【数１２】
0006418841.tif 000013
ａ３，ａ４，ａ５は各成分に対する重み係数である。
【００７２】
そして、複数の重み係数ａ３，ａ４，ａ５のセットを距離計算方法の候補として用意し、第１〜第３の実施形態において説明した選択方法により選択することにより、入力データに応じた距離計算式が選択されることになる。なお、Ｌｐ距離を使用する場合と同様に、それぞれの重みセットを用いた場合の距離の最大値が同じ値となるような重み係数を使用する。
【００７３】
また、第１〜第３の実施形態では、入力データの座標はＸｉ，１，Ｘｉ，２の二次元であるとしたが、これに限る訳ではなく、任意の次元の座標であっても良い。例えば、三次元の画像データであってもよい。
【００７４】
また、第１〜第３の実施形態では、入力データの特徴量はＸｉ，３，Ｘｉ，４，Ｘｉ，５という三次元の色特徴であるとしたがこれに限られるものではない。たとえば、特徴量としてテクスチャ特徴を用いてもよいし、テクスチャ特徴と色特徴を複合した特徴量を用いてもよい。したがって、特徴量の次元も三次元に限定される訳でなく、任意の次元であって良い。また、第１〜第３の実施形態では、探索範囲２０２は幅と高さがそれぞれ５個の代表データの例について説明したが、探索範囲の幅は５個の代表データに限定される訳でなく、任意の探索範囲であっても良い。
【００７５】
以上のような、各実施形態によれば、入力データの特性に応じて代表候補データとの距離計算方法を変更することにより、領域分割の境界精度が向上することが可能となる。
【００７６】
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）をネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムコードを読み出して実行する処理である。この場合、そのプログラム、及び該プログラムを記憶した記憶媒体は本発明を構成することになる。
【符号の説明】
【００７７】
２０１：画像、２０２：探索範囲、２０３、２０４：ブロック、２０５：代表データ、２０６：注目入力データ、４０１：データ保存部、４０２：通信部、４０３：表示部、４０４：ＣＰＵ、４０５：ＲＯＭ、４０６：ＲＡＭ
【図１】
0006418841.tif 000014
【図２】
0006418841.tif 000015
【図３】
0006418841.tif 000016
【図４】
0006418841.tif 000017
【図５】
0006418841.tif 000018
【図６】
0006418841.tif 000019
【図７】
0006418841.tif 000020