(57)【特許請求の範囲】
【請求項１】
画像中の複数の領域に対してそれぞれの代表データを設定する代表データ設定手段と、
前記それぞれの代表データとの距離を算出して、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け手段と、を有し、
前記関連付け手段は、前記それぞれの代表データの中から基点となる基点代表データを選択し、処理の対象の画素について、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との関係が所定の条件を満たした場合に、前記所定の条件を満たした他の代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とする画像処理装置。
【請求項２】
前記関連付け手段は、前記基点代表データと前記他の代表データとの距離の短い順に処理を行い、前記所定の条件を満たした段階で処理の対象となる画素を代表データと関連付けることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記複数の領域はインデックスが割り当てられていることを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記関連付け手段は、前記処理の対象の画素を含む領域の位置に基づいて前記基点代表データを選択することを特徴とする請求項１〜３の何れか１項に記載の画像処理装置。
【請求項５】
前記関連付け手段は、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との比が所定の条件を満たした場合に、前記所定の条件を満たした代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とする請求項１〜４の何れか１項に記載の画像処理装置。
【請求項６】
前記距離は、座標空間上の特徴量と、色空間上及びテクスチャ空間上のうち少なくとも１つの特徴量とで構成されていることを特徴とする請求項１〜５の何れか１項に記載の画像処理装置。
【請求項７】
前記関連付け手段は、前記選択した基点代表データと対応する全ての画素と代表データとの関連付けを終了してから、次の基点代表データを選択し、前記次の基点代表データと対応する画素と代表データとの関連付けを行うことを特徴とする請求項１〜６の何れか１項に記載の画像処理装置。
【請求項８】
前記関連付け手段によって関連付けされた画素の集合に基づいて、前記代表データの位置を更新する更新手段を更に有することを特徴とする請求項１〜７の何れか１項に記載の画像処理装置。
【請求項９】
画像中の複数の領域に対してそれぞれの代表データを設定する代表データ設定工程と、
前記それぞれの代表データとの距離を算出して、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け工程と、を有し、
前記関連付け工程においては、前記それぞれの代表データの中から基点となる基点代表データを選択し、処理の対象の画素について、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との関係が所定の条件を満たした場合に、前記所定の条件を満たした他の代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とする画像処理方法。
【請求項１０】
画像中の複数の領域に対してそれぞれの代表データを設定する代表データ設定工程と、
前記それぞれの代表データとの距離を算出して、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け工程と、をコンピュータに実行させ、
前記関連付け工程においては、前記それぞれの代表データの中から基点となる基点代表データを選択し、処理の対象の画素について、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との関係が所定の条件を満たした場合に、前記所定の条件を満たした他の代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に、クラスタリングを行うために用いて好適な画像処理装置、画像処理方法及びプログラムに関する。
【背景技術】
【０００２】
従来、領域毎の色やテクスチャなどの属性が同じになるように画像を複数の領域に分割する技術として領域分割手法が用いられる。このように分割された領域は、分割領域単位で符号化処理、画像処理、画像認識処理等を行うことができるため、様々な画像処理装置において応用することができる。その中でも近年は、組み込みシステムで画像処理を行うことが多くなったため、組み込みシステム向けの高速化した領域分割手法が注目されている。
【０００３】
従来、画像の領域分割に関して様々な手法が提案されている。例えば非特許文献１〜３には、画素をクラスタリングすることによって画像を複数の領域に分割する手法が開示されている。また、領域分割に限らず、クラスタリングを高速化する手法として非特許文献４に記載の手法が提案されている。
【０００４】
非特許文献１に記載の手法は、従来のＫ−Ｍｅａｎｓクラスタリングを行うためのハードウェアを用いて、画像の内容に基づいた写真検索システムに実装する手法であり、距離計算の高速化を並列度の高いハードウェアで実現している。非特許文献２に記載の手法は、ＳＬＩＣというクラスタリングの高速化のアルゴリズムを用い、スーパーピクセルという小領域を生成する手法である。この手法では、最近傍代表データの探索範囲が限定されているため、従来のＫ−Ｍｅａｎｓクラスタリングよりも計算量を少なくしている。
【０００５】
非特許文献３に記載の手法は、非特許文献２に記載のＳＬＩＣというアルゴリズムを改良してＧＰＵを実装する手法であり、最近傍代表データの探索範囲を３×３に限定し、より処理の高速化を図っているものである。また、非特許文献４に記載の手法は、従来のＫ−Ｍｅａｎｓクラスタリングを高速化するため、入力データが属する代表データの情報と代表データ間の距離の情報とを保存し、三角不等式を用いて不要な計算を削減する手法である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Tse-Wei Chen, et al., "Photo Retrieval based on Spatial Layout with Hardware Acceleration for Mobile Devices," IEEE Transactions on Mobile Computing, vol. 10, no. 11. pp. 1646-1660, Nov. 2011.
【非特許文献２】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.
【非特許文献３】C. Y. Ren and I. Reid., "gSLIC: a real-time implementation of SLIC superpixel segmentation," Technical Report University of Oxford, Department of Engineering, 2011.
【非特許文献４】Elkan, C., "Using the triangle inequality to accelerate k-means," Proc. of International Conference on Machine Learning (ICML), pp147-153, Aug. 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
以上のようにクラスタリングは画像認識及び機械学習における不可欠な技術となってきており、クラスタリングアルゴリズムは画像の領域分割においてよく使用されている技術である。このクラスタリングにおいては、各クラスタの代表データを求め、画素（以下、入力データと表記）を代表データに割り当てることがある。この場合、入力データと複数の代表データの候補（以下、代表候補データ）との距離を計算して最近傍に位置する代表データを探索する必要がある。
【０００８】
組み込みシステムにクラスタリングを実装する場合、入力データと代表候補データとの距離を計算するのに必要な計算量により、ハードウェアの並列度や回路規模が変わる。回路規模を削減するためには、クラスタリングのアルゴリズムの軽量化、又は計算量の削減に関する様々な対策が望まれる。
【０００９】
非特許文献１に記載の手法は並列度の高いハードウェアにより高速化を実現しており、非特許文献２及び３に記載の手法はアルゴリズムを高速化させている。しかし、上述した先行技術を利用しても、高解像度の画像データに対して高速にクラスタリングを処理するためには、距離計算の計算量を十分に削減できていないという課題がある。非特許文献４に記載の手法は三角不等式によって不要な計算を削減するが、入力データが属する代表データに関する情報を保存する必要があるため、メモリコストが大きいという課題がある。
【００１０】
本発明は前述の問題点に鑑み、クラスタリングにおける計算量及びメモリコストを削減して、精度良く画像を複数の領域に分割できるようにすることを目的としている。
【課題を解決するための手段】
【００１１】
本発明に係る画像処理装置は、画像中の複数の領域に対してそれぞれの代表データを設定する代表データ設定手段と、前記それぞれの代表データとの距離を算出して、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け手段と、を有し、前記関連付け手段は、前記それぞれの代表データの中から基点となる基点代表データを選択し、処理の対象の画素について、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との関係が所定の条件を満たした場合に、前記所定の条件を満たした他の代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とする。
【発明の効果】
【００１２】
本発明によれば、クラスタリングにおける計算量及びメモリコストを削減して、精度良く画像を複数の領域に分割することができる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
【図２】最近傍代表データの探索範囲を説明するための図である。
【図３】入力データ、基点代表データ及び代表候補データの位置関係を説明するための図である。
【図４】データ処理装置のハードウェア構成例を示すブロック図である。
【図５】第２の実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
【図６】第３の実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
【図７】基点代表データごとに入力データを処理する様子を説明するための図である。
【図８】第４の実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
【図９】最近傍代表データの探索範囲の他の例を説明するための図である。
【発明を実施するための形態】
【００１４】
（第１の実施形態）
以下、図面を参照しながら本発明の実施形態について詳細に説明する。
【００１５】
＜データ処理装置の構成例＞
図４は、本実施形態における信号処理方法を実現可能なデータ処理装置４００のハードウェア構成例を示すブロック図である。
図４において、データ保存部４０２は、画像データを保持する記憶媒体である。データ保存部４０２は、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＣＤ−ＲやＤＶＤ、メモリーカード、ＣＦ（登録商標）カード、スマートメディア、ＳＤカード、メモリスティック、ｘＤピクチャーカード、ＵＳＢメモリ等で構成される。また、データ保存部４０２には、画像データの他にも、プログラムやその他のデータを保存することも可能である。あるいは、後述するＲＡＭ４０７の一部をデータ保存部４０２として用いてもよい。さらに、後述する通信部４０３により接続した先の機器の記憶装置を、通信部４０３を介して利用するというように仮想的に構成するのであってもよい。
【００１６】
表示部４０４は、画像処理を行う前後の画像を表示したり、ＧＵＩ等の画像を表示したりする装置であり、一般的にはＣＲＴや液晶ディスプレイなどが用いられる。あるいは、ケーブル等で接続された外部のディスプレイ装置であっても構わない。
【００１７】
入力部４０１は、ユーザーからの指示や、データを入力する装置であり、キーボードやポインティング装置などである。なお、ポインティング装置としては、マウス、トラックボール、トラックパッド、タブレット等が挙げられる。あるいは、データ処理装置４００を例えば公知のデジタルカメラやプリンタなどの機器に適用する場合には、ボタンやダイヤル等で構成されるのであってもよい。また、キーボードをソフトウェアで構成し、ボタンやダイヤル、あるいは先に挙げたポインティングデバイスを操作して文字を入力するように構成するのであってもよい。また、表示部４０４にタッチパネルを搭載し、表示部４０４と入力部４０１とが同一の装置であってもよい。その場合、タッチパネルを介した入力を入力部４０１の入力として扱う。
【００１８】
ＣＰＵ４０５は、本実施形態に係る主要な処理を実行すると共にデータ処理装置４００全体の動作を制御する。ＲＯＭ４０６及びＲＡＭ４０７は、その処理に必要なプログラム、データ、作業領域などをＣＰＵ４０５に提供する。後述する処理に必要なプログラムがデータ保存部４０２に格納されている場合や、ＲＯＭ４０６に格納されている場合には、ＲＡＭ４０７に一旦書き込まれてから後述する処理が実行される。また、通信部４０３を経由してデータ処理装置４００がプログラムを受信する場合には、データ保存部４０２に一旦記録した後にＲＡＭ４０７に書き込まれるか、通信部４０３からＲＡＭ４０７に直接書き込まれてから処理が実行される。
【００１９】
ＣＰＵ４０５は、ＲＡＭ４０７またはデータ保存部４０２に書き込まれた画像データを読み出して本実施形態に係る画像処理（クラスタリング）を実行し、その処理結果を再びＲＡＭ４０７に書き込む。そして、クラスタリングの処理結果に基づき、ＣＰＵ４０５は画像認識処理を行う。ＣＰＵ４０５により処理された画像認識の処理結果は、ＲＡＭ４０７に保存されるか、通信部４０３を介して外部装置に送信される。
【００２０】
通信部４０３は、機器間の通信を行うためのＩ／Ｆである。Ｉ／Ｆとしては、例えば、公知のローカルエリアネットワーク、ＵＳＢ、ＩＥＥＥ１２８４、ＩＥＥＥ１３９４、電話回線などの有線による通信方式であってもよい。また、赤外線（ＩｒＤＡ）、ＩＥＥＥ８０２．１１ａ、ＩＥＥＥ８０２．１１ｂ、ＩＥＥＥ８０２．１１ｇ、ＩＥＥＥ８０２．１１ｎ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、ＵＷＢ（Ｕｌｔｒａ  ｗｉｄｅ  Ｂａｎｄ）等の無線通信方式であってもよい。
【００２１】
なお、図４に示す例では、入力部４０１、データ保存部４０２、表示部４０４が全て１つの装置内に含まれるような例を示しているが、これらの部分が公知の通信方式による通信路で接続されており、全体としてこのような構成となっていてもよい。また、図４に示す例においては、ＣＰＵが１つだけの構成であるが、ＣＰＵを複数設けるような構成にしてもよい。システム構成については、上記以外にも様々な構成要素が存在してもよいが、本発明の主眼ではないのでその説明は省略する。
【００２２】
＜領域分割のためのクラスタリング＞
図１（ａ）は、本実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
まず、クラスタリング対象のデータについて説明する。以下の式（１）は第ｉ番目の入力データを示す。入力データは画像中の画素と対応する５次元のベクトルであり、第ｉ番目の入力データとは、画像をラスタスキャンして第ｉ番目に読み出された画素に関する情報である。
Ｘi＝（Ｘi,1，Ｘi,2，Ｘi,3，Ｘi,4，Ｘi,5）    ・・・（１）
【００２３】
式（１）中のＸi,1，Ｘi,2は座標空間上の二次元特徴量を表し、それぞれ画像の縦方向、横方向の座標値を意味する。また、Ｘi,3，Ｘi,4，Ｘi,5はそれぞれ色空間上の三次元特徴量を表す。
【００２４】
まず、ステップＳ１０１においては、初期化した代表データを生成する。具体的には、代表データ設定処理として、例えば図２に示した画像２０１を座標空間上のブロックに分割し、各々のブロック２０３の中からそれぞれ１個の入力データを選択し、代表データ２０５に設定する。そして、設定した全ての代表データをインデックス化し、ブロックの処理順又は位置順にインデックス値を割り当てることにより、アクセス順番を制御できるようにする。
【００２５】
図２において、画像２０１の左側の数字及び下側の数字は、それぞれ代表データの縦方向のインデックス、横方向のインデックスである。網点パターンに示すブロック２０４の中の代表データ２０５の縦方向のインデックス及び横方向のインデックスはそれぞれ「７」、「８」である。そして、選択した入力データの座標空間及び色空間の特徴量のベクトルをその代表データのベクトルとする。以下の式（２）は、第ｊ番目の代表データ２０５に対するベクトルＣjを示している。
Ｃj＝（Ｃj,1，Ｃj,2，Ｃj,3，Ｃj,4，Ｃj,5）      ・・・（２）
【００２６】
式（２）中のＣi,1，Ｃi,2は座標空間上の二次元特徴量を表し、それぞれ画像の縦方向、横方向の座標値を意味する。また、Ｃi,3，Ｃi,4，Ｃi,5はそれぞれ色空間上の三次元特徴量を表す。
【００２７】
次のステップＳ１０２においては、最大繰り返し回数を設定し、ステップＳ１０３〜Ｓ１１８までの繰り返し計算のループを開始する。
ステップＳ１０３においては、代表データ間のユークリッド距離（第一の距離）Ｄ（Ｃi，Ｃj）を以下の式（３）により計算し、計算結果をＲＡＭ４０７に保存する。
【００２８】
【数１】
0006573368.tif 000002
【００２９】
続いてステップＳ１０４においては、各入力データに対してループを開始する。画像の中の入力データＸiの順番ｉを制御し、ステップＳ１０５〜Ｓ１１５までの処理を繰り返して全ての入力データをクラスタリングする。
【００３０】
ステップＳ１０５においては、探索範囲を設定する。具体的には、入力データの座標位置によって代表候補データの探索範囲を設定する。ここで、入力データの代表候補データとは、該当する入力データを割り当てる（帰属させる）代表データの候補である。
【００３１】
以下、探索範囲２０２の幅および高さがそれぞれ３個である場合の例について説明する。まず、処理対象の入力データ（以下、注目入力データ）２０６が含まれているブロックを中心に、代表候補データの探索範囲を設定する。この場合、探索範囲は３×３個の座標近傍の代表データを含む領域である。図２に示す例の場合、探索範囲は縦方向インデックスが６〜８までであり、横方向インデックスが７〜９までである。注目入力データ２０６を含め、ブロック２０４の範囲に入っている全ての入力データの探索範囲２０２は同じである。なお、入力データの位置と探索範囲の代表候補データとの関係は最初に固定され、繰り返し処理によって代表データの位置が変わっても、代表データのインデックスは変わらないものとする。
【００３２】
続いてステップＳ１０６において、最近傍代表データを探索する。ここで、入力データの最近傍代表データとは、当該入力データとの距離が最短な代表データ、即ち、距離空間上一番近い代表データである。この処理の詳細については後述する。
【００３３】
次に、ステップＳ１１５において、ステップＳ１０６の処理による最近傍代表データの探索結果に基づいて、入力データを上述した最近傍代表データに帰属させる。そして、ステップＳ１１６において、全ての入力データを処理したかどうかを判定する。この判定の結果、全ての入力データを処理した場合は、ステップＳ１１７に進み、入力データのループを終了する。一方、まだ処理していない入力データがある場合はステップＳ１０４に戻り、次の入力データの処理を開始する。
【００３４】
ステップＳ１１７においては、各代表データに対して、帰属させた入力データのベクトルの平均ベクトルを計算する。そして、その平均ベクトルを該当する代表データの新しいベクトルＣjとし、代表データを更新する。
次に、ステップＳ１１８において、最大繰り返し回数を超えるかどうか、又はクラスタリングの結果が収束したかを判定する。この判定の結果、何れかの条件が成立する場合は、繰り返し計算を終了する。一方、いずれの条件も成立しない場合はステップＳ１０２に戻り、次の繰り返し計算を開始する。以上のように、代表データを繰り返し更新することにより、代表データに関連付けされた画素の集合が領域の分割結果となる。クラスタリングを終了すると、ＣＰＵ４０５は、クラスタリング結果を表示部４０４などに出力する。
【００３５】
＜基点代表データの情報による最近傍代表データの探索＞
次に、ステップＳ１０６の詳細な処理である図１（ｂ）のステップＳ１０７〜Ｓ１１４について説明する。この処理では、上述した探索範囲２０２の中の全ての代表候補データとの距離を計算する。
【００３６】
まず、ステップＳ１０７において、座標空間で第ｉ番目の入力データに対応する基点代表データを決定し、入力データと基点代表データとの距離を算出する。ここで、第ｉ番目の入力データに対応する基点代表データのインデックスをｒ（ｉ）とする。具体的な距離の算出方法は、まず、注目入力データが含まれているブロック（領域）に対応する代表データを基点代表データとする。そして、注目入力データと基点代表データとのユークリッド距離（第二の距離）Ｄ（Ｘi，Ｃr(i)）を以下の式（４）により算出する。
【００３７】
【数２】
0006573368.tif 000003
【００３８】
図２に示す例の場合、基点代表データは縦方向インデックスが「７」であり、横方向インデックスが「８」である。このように注目入力データ２０６を含め、ブロック２０４の範囲に入っている全ての入力データが対応する基点代表データは同じである。なお、入力データの位置と基点代表データとの関係は最初に固定され、繰り返し処理によって代表データの位置が変わっても、基点代表データのインデックスは変わらないものとする。そして、この処理で求めた第二の距離を後述する最短距離に初期設定する。
【００３９】
次にステップＳ１０８において、代表候補データのループを開始する。以下、ステップＳ１０９〜Ｓ１１４において代表候補データＣjの順番ｊを制御し、全ての代表候補データを探索する。
【００４０】
まず、ステップＳ１０９においては、ステップＳ１０３で保存した基点代表データと代表候補データとの距離（第一の距離）をＲＡＭ４０７から読み出し、第一の距離と第二の距離との比Ｒi,jを、以下の式（５）により算出する。この比は、後述する第三の距離を算出するか否かを判定するための所定の条件として用いられる。
【００４１】
【数３】
0006573368.tif 000004
【００４２】
続いてステップＳ１１０において、上述した第一の距離と第二の距離との比Ｒi,jが閾値を超えるかどうかを判定する。この判定の結果、閾値を超える場合は、後述するステップＳ１１１〜Ｓ１１３の処理を省略し、ステップＳ１１４に進む。一方、閾値以下である場合は、ステップＳ１１１に進む。
【００４３】
ステップＳ１１１においては、第ｉ番目の入力データと第ｊ番目の代表候補データとのユークリッド距離（第三の距離）Ｄ（Ｘi，Ｃj）を以下の式（６）により算出する。
【００４４】
【数４】
0006573368.tif 000005
【００４５】
次にステップＳ１１２において、上述した第三の距離が最短距離以上かどうかを判定する。ここで、最短距離については後述する。この判定の結果、第三の距離が最短距離以上である場合は、ステップＳ１１３を省略し、ステップＳ１１４に進む。一方、第三の距離が最短距離未満である場合は、ステップＳ１１３に進む。そして、ステップＳ１１３において、最短距離を上述した第三の距離に更新し、最近傍代表データのベクトルをベクトルＣjに変更する。
【００４６】
ステップＳ１１４においては、全ての代表候補データとの比較が終了したかどうかを判定する。この判定の結果、全ての代表候補データとの比較が終了した場合は、最近傍代表データの探索を終了する。一方、まだ比較を行っていない代表候補データがある場合はステップＳ１０８に戻り、次の代表候補データとの距離の計算を開始する。
【００４７】
＜最近傍代表データの探索の例＞
図３は、図１（ｂ）のステップＳ１０６における最近傍代表データの探索処理の概要を説明するための図である。図３において、点３０２は注目入力データの点３０１に対応する基点代表データの点であり、点３０３〜３１０は、注目入力データに対応する探索範囲の中の代表候補データの点である。この場合、基点代表データが最近傍代表データになる可能性もある。基点代表データの点３０２と代表候補データの点３０３〜３１０との距離（第一の距離）は最近傍代表データの探索処理を行う前にステップＳ１０３で算出されている。
【００４８】
まず、ステップＳ１０７で基点代表データの点３０２と注目入力データの点３０１との距離（第二の距離）３１３を計算し、第２の距離３１３を最短距離に指定することによって初期化し、最近傍代表データを基点代表データに仮指定する。その後、ループ処理により代表候補データの点３０３〜３１０の順番で最近傍代表データを探索することになる。
【００４９】
代表候補データの点３０３について処理を開始する場合、ステップＳ１０９では基点代表データの点３０２と代表候補データの点３０３との間の第一の距離３１１と、上述した第二の距離３１３との比を求める。ここで、Ｓ１１０の判定で上述した比の値が閾値を超えていないと判定されるものとする。この場合には、代表候補データの点３０３と注目入力データの点３０１との距離３１２の計算を省略することができないため、ステップＳ１１１に進む。そして、代表候補データの点３０３と注目入力データの点３０１との第三の距離３１２を算出し、この第三の距離３１２と最短距離である第二の距離との比較によって、最近傍代表データと最短距離とを更新するかどうかを判定する。
【００５０】
次に代表候補データの点３０４について処理を開始する場合も同様に、注目入力データの点３０１との距離計算を省略することができないものとする。この場合も代表候補データの点３０４と注目入力データの点３０１との第三の距離によって、最近傍代表データと最短距離とを更新するかどうかを判定することになる。
【００５１】
次に代表候補データの点３０５について処理を開始する場合、第一の距離３１４と上述した第二の距離３１３との比の値が閾値を超えるものとする。この場合には、代表候補データの点３０５と注目入力データの点３０１との距離３１５の計算を省略することができる。したがって、最近傍代表データと最短距離とを更新する必要がない。
【００５２】
以下、代表候補データの点３０６〜３１０について処理を行う場合も、前述の比が閾値を超える場合には、代表候補データの点３０５と同様に注目入力データの点３０１との距離計算を省略することができ、最近傍代表データと最短距離とを更新する必要がない。
【００５３】
以上のように本実施形態によれば、基点代表データの情報を利用するようにしたので、入力データと一部の代表候補データとの距離の計算を省略することによって処理を高速化することができる。また、本実施形態では、式（４）で説明したように、注目入力データが含まれているブロック（領域）に対応する代表データを基点代表データにする。したがって、従来手法のように注目入力データが対応する基点代表データの情報を保存する必要がないため、メモリコストを削減することができる。
【００５４】
なお、本実施形態では、入力データの座標空間上の特徴量として、式（１）で表されるＸi,1，Ｘi,2という一枚の画像の座標空間の二次元特徴量について説明した。一方、一枚の画像の座標空間の二次元特徴量に限定されるわけでなく、座標空間と複数枚の画像とを処理する時の時系列空間の任意の次元の特徴量でもよい。また、本実施形態では、入力データの特徴量として、座標空間及び色空間の特徴量について説明した。一方、座標空間及び色空間に限定されるわけでなく、座標空間上と、色空間上及びテクスチャ空間上のうち少なくとも１つとの特徴量であってもよい。また、色空間上の特徴量は三次元に限定される訳でなく、任意の次元の特徴量であってもよい。
【００５５】
また、本実施形態においては、探索範囲の幅及び高さがそれぞれ３個の代表データを含む領域の例について説明したが、探索範囲の幅はそれに限定されるわけでなく、任意の探索範囲であってもよい。また、式（３）、式（４）及び式（６）には座標空間と色空間でのユークリッド距離を用いたが、ユークリッド距離に限定されるわけでなく、任意の距離尺度であってもよい。
【００５６】
（第２の実施形態）
以下、本発明の第２の実施形態について、第１の実施形態と異なる部分についてのみを説明する。したがって、本実施形態に係るデータ処理装置の構成等については説明を省略する。
【００５７】
図５は、本実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。なお、図１と同様の処理については同じ符号を付しており、これらの処理の説明は省略する。
図５（ａ）のステップＳ５０１においては、代表データ間のユークリッド距離（第一の距離）を式（３）により計算する。そして、基点代表データを１つ定めた場合に、基点代表データとの距離順によって代表データに順位を付け、計算結果をＲＡＭ４０７に保存する。この順位付けのパターンは、代表データの数だけ存在することになる。
【００５８】
図５（ｂ）のステップＳ１０８においては、代表候補データのループを開始する。本実施形態では、代表候補データＣjの順番ｊを制御し、ステップＳ１０４のループで対象となっている入力データに係る基点代表データの順位付けの情報をＲＡＭ４０７から読み出す。そして、その読み出した情報によって、基点代表データとの距離が短い代表候補データから基点代表データとの距離が長い代表候補データまでという順番で全ての代表候補データを探索する。図５（ｂ）のステップＳ５０２の判定では、上述した第一の距離と第二の距離との比が閾値を超える場合に、代表候補データのループを途中で終了するようにする。
【００５９】
＜最近傍代表データの探索の例＞
本実施形態に係る処理について図３を参照しながら説明する。代表候補データの点３０３〜３１０は、基点代表データの点３０２との距離が短い順に並んでいる。つまり、代表候補データの点３０３と基点代表データの点３０２との距離が一番短く、代表候補データの点３１０と基点代表データの点３０２との距離が一番長い。
【００６０】
まず、ステップＳ１０７で基点代表データの点３０２と注目入力データの点３０１との距離（第二の距離）３１３を計算し、第二の距離３１３を最短距離に指定することによって初期化し、最近傍代表データを基点代表データに指定する。その後、代表候補データの点３０３〜３１０までという距離の短い順で最近傍代表データを探索する。
【００６１】
まず、代表候補データの点３０３について処理を開始し、基点代表データの点３０２と代表候補データの点３０３との間の第一の距離３１１と、上述した第二の距離３１３との比を求める。上述した比の値が閾値を超えていないため、代表候補データの点３０３と注目入力データの点３０１との距離３１２の計算を省略することができない。そこで、代表候補データの点３０３と注目入力データの点３０１との第三の距離３１２によって、最近傍代表データと最短距離とを更新するかどうかを判定する。
【００６２】
次に、代表候補データの点３０４について処理を開始する。この場合も上述した比の値が閾値を超えていないため、注目入力データの点３０１との第三の距離の計算を省略することができない。そして、代表候補データの点３０４と注目入力データの点３０１との第三の距離によって、最近傍代表データと最短距離とを更新するかどうかを判定する。
【００６３】
次に、代表候補データの点３０５について処理を開始する。第一の距離３１４と上述した第二の距離３１３との比の値が閾値を超えるため、代表候補データの点３０５と注目入力データの点３０１との第三の距離３１５の計算を省略することができる。この段階で、代表候補データの点３０６〜３１０と基点代表データの点３０２との第一の距離は、それぞれ代表候補データの点３０５と基点代表データの点３０２との第一の距離３１４よりも長いことが判別できる。したがって、代表候補データの点３０６〜３１０についても、上述した比が閾値を超えることが判別できるため、ループ処理を終了することができる。
【００６４】
以上のように本実施形態によれば、基点代表データと代表候補データとの距離によって順番を制御するようにしたので、ループ処理を途中で終了させることができ、不要な計算を省略することができる。このように第１の実施形態よりもさらに距離計算の回数が減り、処理を高速化することができる。
【００６５】
（第３の実施形態）
以下、本発明の第３の実施形態について、第１の実施形態と異なる部分についてのみを説明する。したがって、本実施形態に係るデータ処理装置の構成等については説明を省略する。
【００６６】
図６は、本実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。なお、図１と同様の処理については同じ符号を付しており、これらの処理の説明は省略する。
まず、図６（ａ）のステップＳ６０１においては、基点代表データのループを開始する。画像の中の基点代表データＣkの順番ｋを制御し、ステップＳ６０２〜Ｓ６０４までの繰り返しにより全ての基点代表データＣkに対応する入力データを処理する。
【００６７】
ステップＳ６０２においては、探索範囲を設定する。具体的には、基点代表データの座標位置によって入力データの代表候補データの探索範囲を設定する。そして、ステップＳ６０３においては、基点代表データＣkと探索範囲の中の代表データとのユークリッド距離（第一の距離）Ｄ（Ｃk，Ｃj）を以下の式（７）により計算し、計算結果をＲＡＭ４０７に保存する。
【００６８】
【数５】
0006573368.tif 000006
【００６９】
図６（ａ）のステップＳ１０４においては、入力データのループを開始する。入力データＸiが対応する基点代表データは上述した基点代表データＣkであり、第ｉ番目の入力データの対応する基点代表データのインデックスｒ（ｉ）はｋである。上述した基点代表データＣkに対応する入力データＸiの順番ｉを制御し、ステップＳ１０５〜Ｓ１１５までの繰り返しにより基点代表データＣkに対応する全ての入力データをクラスタリングする。
【００７０】
図６（ａ）のステップＳ６０４においては、上述した基点代表データＣkに対応する全ての入力データを処理したかどうかを判定する。この判定の結果、基点代表データＣkに対応する全ての入力データを処理した場合は、ステップＳ６０５に進み、入力データループを終了し、そうでない場合はステップＳ１０４に戻り、次の入力データの処理を開始する。具体的には、図７に示すように、基点代表データ７０３に対応するブロック７０１の中の全ての入力データを処理した後に基点代表データ７０４に対応するブロック７０２の中の全ての入力データを処理することになる。ブロック７０２の中の入力データを処理する時は、基点代表データ７０４と探索範囲の中の代表データとの距離のみを保存し、基点代表データ７０３と探索範囲の中の代表データとの距離を保存する必要がない。
【００７１】
図６（ａ）のステップＳ６０５においては、全ての基点代表データについて処理を終了したかどうかを判定する。この判定の結果、全ての基点代表データについて処理が終了した場合は、ステップＳ１１７に進み、入力データループを終了する。一方、まだ処理を行っていない基点代表データがある場合は、ステップＳ６０１に戻り、次の基点代表データの処理を開始する。なお、図６（ｂ）に示す処理は、図１（ｂ）に示す処理と同様である。
【００７２】
以上のように本実施形態によれば、探索範囲の中の代表データとの距離だけを計算して保存するようにしたので、従来手法のように全ての代表データとの距離の計算を不要することができ、処理をより高速化することができる。また、第一の距離の保存量を少なくすることができるため、メモリコストをより削減することができる。
【００７３】
（第４の実施形態）
以下、本発明の第４の実施形態について説明する。本実施形態では、第２の実施形態と第３の実施形態とを組み合わせており、第２または第３の実施形態と異なる部分についてのみを説明する。したがって、本実施形態に係るデータ処理装置の構成等については説明を省略する。
【００７４】
図８は、本実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。なお、図５または図６と同様の処理については同じ符号を付しており、これらの処理の説明は省略する。
図８（ａ）のステップＳ８０３においては、基点代表データＣkと探索範囲の中の代表データとのユークリッド距離（第一の距離）を式（７）で計算して距離の短い順に整列し、計算結果を距離順にＲＡＭ４０７に保存する。本実施形態では、基点代表データのループ処理を行っているため、距離の順序として１つのパターンのみを保存することになる。ステップＳ１０８では、距離の短い順に代表候補データのループを開始する。なお、図８（ｂ）に示す処理は、図５（ｂ）に示す処理と同様である。
【００７５】
以上のように本実施形態によれば、探索範囲の代表候補データのみを対象としてステップＳ５０２の判定を行うようにしたので、より計算を省略することができる。このように第３の実施形態と比べて第三の距離の計算回数が減り、処理をより高速化することができる。また、探索範囲の中の代表データとの第一の距離だけを保存するため、メモリコストをより削減することができる。
【００７６】
（その他の実施形態）
＜探索範囲の幅および高さがそれぞれ偶数個の代表データの例＞
前述した実施形態では、探索範囲の幅および高さがそれぞれ奇数個（３つ）の代表データを含む領域である例について説明した。一方、探索範囲の幅および高さは奇数個の代表データに限定されるわけでなく、探索範囲の幅および高さがそれぞれ偶数個の代表データを含む領域の場合にも同様に適用可能である。
【００７７】
図９は、探索範囲の幅および高さがそれぞれ偶数個の代表データを含む領域に設定した場合の探索範囲を説明するための図である。第１の実施形態で説明したように、まず、図９に示した画像９０１を座標空間上のブロックに分割し、各ブロック９０３の中に１個の代表データ９０５を配置する。そして、注目入力データ９０６に一番近いブロックの角を中心にして、代表候補データの探索範囲９０２を設定する。この場合、探索範囲の代表データは縦方向インデックスが６〜７であり、横方向インデックスが８〜９である。注目入力データ９０６を含め、矩形９０４の範囲に入っている全ての入力データに対して同じ探索範囲９０２となる。なお、探索範囲９０２の幅および高さがそれぞれ２個の代表データを含む領域の例について説明したが、探索範囲の幅は２個の代表データを含む領域に限定されるわけでなく、任意の探索範囲であってもよい。
【００７８】
＜任意の空間上のブロック分割＞
また、前述した実施形態では、入力データを座標空間上のブロックに分割する例について説明したが、座標空間に限定されるわけでなく、入力データを任意の距離空間上のブロックに分割してもよい。
【００７９】
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【００８０】
４０５  ＣＰＵ
【図１】
0006573368.tif 000007
【図２】
0006573368.tif 000008
【図３】
0006573368.tif 000009
【図４】
0006573368.tif 000010
【図５】
0006573368.tif 000011
【図６】
0006573368.tif 000012
【図７】
0006573368.tif 000013
【図８】
0006573368.tif 000014
【図９】
0006573368.tif 000015