(57)【要約】【課題】画像データから抽出した特徴ベクトルのクラスタリングによる分類に際し、好ましい分類の程度を指定するパラメータの入力を要さずに、入力された画像データ自体からその画像データに合わせた最適な分類の程度を特定して分類を行う。【解決手段】原画像から、段階的に解像度の異なる複数の低解像度画像を導出し、解像度が最も低い最低解像度画像から、２つ以上のクラスターの初期代表ベクトルを求める。これらの初期代表ベクトルを利用して、実画像空間における画像領域の分類と特徴ベクトル空間における分類の対応関係に基づいて、実画像空間における情報を反映した代表ベクトルを増やしながら、各低解像度画像における特徴ベクトルの最適な分類を順次求めていき、最終的には原画像の各画素から抽出された特徴ベクトルの最適な分類を求める。【選択図】          図１１
2004258750.tif 000002
【特許請求の範囲】
【請求項１】
原画像から、段階的に解像度の異なる複数の複数画素からなる低解像度画像を導出する工程と、
前記複数の低解像度画像のうち解像度が最も低い最低解像度画像から、２つ以上の代表ベクトルの、各成分の初期値を求める工程と、
解像度が次に低い画像を現在画像として、該現在画像の各画素から特徴ベクトルを抽出する工程と、
該特徴ベクトルの各々を特徴ベクトル空間に写像する工程と、
前記特徴ベクトル空間において、前記特徴ベクトルを、前記代表ベクトルの各々が代表するクラスターに分類する工程と、
前記クラスターの各々に属する前記特徴ベクトルに対応する画素の、前記現在画像上における分布に基づいて、前記現在画像を画像領域に分割する工程と、
前記クラスターの中から選択した１つの選択クラスターに対応する前記画像領域を特定する工程と、
該特定により複数の画像領域が特定された場合に行う工程であって、該複数の画像領域の中から選択した複数の選択画像領域の各々から１つの仮代表ベクトルを抽出し、前記特徴ベクトル空間において、前記複数の選択画像領域に属する画素に対応する前記特徴ベクトルを、前記仮代表ベクトルの各々が代表する仮クラスターに再分類し、前記選択画像領域と前記仮クラスターの間の対応関係に基づく１つまたは複数の仮クラスター群を特定し、前記仮クラスター群の各々を代表するベクトルを、前記選択クラスターを代表する前記代表ベクトルに代えて新たな代表ベクトルとする工程と、
全ての前記クラスターについて、前記画像領域を特定する工程と前記複数の画像領域が特定された場合に行う工程を繰り返す工程と、
前記原画像が前記現在画像とされ、前記原画像の各画素から抽出された特徴ベクトルを分類する最終的な代表ベクトルが求められるまで、前記特徴ベクトルを抽出する工程から前記繰り返す工程を繰り返す工程を含むことを特徴とする画像の特徴ベクトルのクラスタリング方法。
【請求項２】
前記１つまたは複数の仮クラスター群の特定が、
当該仮クラスターを代表する前記仮代表ベクトルの抽出元である前記選択画像領域中の画素に対応する前記特徴ベクトルを全て含み、かつ他の前記選択画像領域中の画素に対応する前記特徴ベクトルを含まない仮クラスターがある場合には、該仮クラスターを１つの仮クラスター群として特定する第１の工程と、
前記第１の工程において特定された前記仮クラスター群のいずれにも属していない前記仮クラスターが残っている場合には、該残りの仮クラスターからなる群を１つの仮クラスター群として特定する第２の工程により行われることを特徴とする請求項１記載のクラスタリング方法。
【請求項３】
前記１つまたは複数の仮クラスター群の特定が、
当該仮クラスターを代表する前記仮代表ベクトルの抽出元である前記選択画像領域中の画素に対応する前記特徴ベクトルを全て含み、かつ他の前記選択画像領域中の画素に対応する前記特徴ベクトルを含まない仮クラスターがある場合には、該仮クラスターを１つの仮クラスター群として特定する第１の工程と、
相互においてのみ当該仮クラスターを代表する前記仮代表ベクトルの抽出元である前記選択画像領域中の画素に対応する前記特徴ベクトルを交換している、複数の仮クラスターがある場合には、該複数の仮クラスターからなる群を１つの仮クラスター群として特定する第２の工程と、
前記第１の工程および前記第２の工程において特定された前記仮クラスター群のいずれにも属していない前記仮クラスターが残っている場合には、該残りの仮クラスターからなる群を１つの仮クラスター群として特定する第３の工程により行われることを特徴とする請求項１記載のクラスタリング方法。
【請求項４】
前記仮クラスターへの再分類後、前記１つまたは複数の仮クラスター群の特定前において、
前記仮クラスターの各々について、該仮クラスターに属する前記特徴ベクトルの総数に対し、該仮クラスターに属する対応の特徴ベクトルの数の割合が所定割合より少ない選択画像領域がある場合は、該選択画像領域に対応する前記特徴ベクトルを該仮クラスターから除外することを特徴とする請求項２または３記載のクラスタリング方法。
【請求項５】
前記クラスターに分類する工程と、前記現在画像を画像領域に分割する工程の間に、
前記クラスターの各々に含まれる前記特徴ベクトルに基づいて、前記代表ベクトルを更新する工程をさらに含むことを特徴とする請求項１から４いずれか１項記載のクラスタリング方法。
【請求項６】
前記クラスターに分類する工程と、前記現在画像を画像領域に分割する工程の間に、
前記クラスターの各々に含まれる前記特徴ベクトルに基づいて、前記代表ベクトルを更新する工程と、
前記更新された代表ベクトルに基づいて前記クラスターを更新する工程をさらに含むことを特徴とする請求項１から４いずれか１項記載のクラスタリング方法。
【請求項７】
前記現在画像を画像領域に分割する工程と、前記画像領域を特定する工程の間に、
微小領域を非微小領域に統合することにより、前記画像領域を更新する工程をさらに含むことを特徴とする請求項１から６いずれか１項記載のクラスタリング方法。
【請求項８】
前記複数の選択画像領域が、前記複数の画像領域の中から、構成画素数の多いものを順に複数選択したものであることを特徴とする請求項１から７いずれか１項記載のクラスタリング方法。
【請求項９】
前記初期値を求める工程が、
ｎ個の画素からなる前記最低解像度画像から、１つの原代表ベクトルを導出する工程と、
前記ｎ個の画素の各々から抽出されたｎ個の特徴ベクトルと、前記原代表ベクトルとの、前記特徴ベクトル空間における距離を求め、最大距離を示す特徴ベクトルを代表ベクトル候補とするとともに、最も高い候補順位を付ける工程と、
残りの特徴ベクトルの各々と、前記原代表ベクトルおよび前記代表ベクトル候補のうち該特徴ベクトルに最も近いものとの、前記特徴ベクトル空間における距離を求め、最大距離を示す特徴ベクトルを前記代表ベクトル候補に追加するとともに、次に高い候補順位を付ける工程と、
前記次に高い候補順位を付ける工程を繰り返す工程と、
前記候補順位に従って、前記代表ベクトル候補のうちの上位２つ以上の前記特徴ベクトルの各成分の値を、前記代表ベクトルの各成分の前記初期値とする工程を含むことを特徴とする請求項１から８いずれか１項記載のクラスタリング方法。
【請求項１０】
原画像から、段階的に解像度の異なる複数の複数画素からなる低解像度画像を導出する手段と、
前記複数の低解像度画像のうち解像度が最も低い最低解像度画像から、２つ以上の代表ベクトルの、各成分の初期値を求める手段と、
解像度が次に低い画像を現在画像として、該現在画像の各画素から特徴ベクトルを抽出する手段と、
該特徴ベクトルの各々を特徴ベクトル空間に写像する手段と、
前記特徴ベクトル空間において、前記特徴ベクトルを、前記代表ベクトルの各々が代表するクラスターに分類する手段と、
前記クラスターの各々に属する前記特徴ベクトルに対応する画素の、前記現在画像上における分布に基づいて、前記現在画像を画像領域に分割する手段と、
前記クラスターの中から選択した１つの選択クラスターに対応する前記画像領域を特定する手段と、
該特定により複数の画像領域が特定された場合に動作する手段であって、該複数の画像領域の中から選択した複数の選択画像領域の各々から１つの仮代表ベクトルを抽出し、前記特徴ベクトル空間において、前記複数の選択画像領域に属する画素に対応する前記特徴ベクトルを、前記仮代表ベクトルの各々が代表する仮クラスターに再分類し、前記選択画像領域と前記仮クラスターの間の対応関係に基づく１つまたは複数の仮クラスター群を特定し、前記仮クラスター群の各々を代表するベクトルを、前記選択クラスターを代表する前記代表ベクトルに代えて新たな代表ベクトルとする手段と、
全ての前記クラスターについて、前記画像領域を特定する手段と前記複数の画像領域が特定された場合に動作する手段を繰返し動作させる手段と、
前記原画像が前記現在画像とされ、前記原画像の各画素から抽出された特徴ベクトルを分類する最終的な代表ベクトルが求められるまで、前記特徴ベクトルを抽出する手段から前記繰返し動作させる手段を繰返し動作させる手段を備えていることを特徴とする画像の特徴ベクトルのクラスタリング装置。
【請求項１１】
前記１つまたは複数の仮クラスター群の特定を、
当該仮クラスターを代表する前記仮代表ベクトルの抽出元である前記選択画像領域中の画素に対応する前記特徴ベクトルを全て含み、かつ他の前記選択画像領域中の画素に対応する前記特徴ベクトルを含まない仮クラスターがある場合には、該仮クラスターを１つの仮クラスター群として特定する第１の手段と、
前記第１の手段が特定した前記仮クラスター群のいずれにも属していない前記仮クラスターが残っている場合には、該残りの仮クラスターからなる群を１つの仮クラスター群として特定する第２の手段により行うことを特徴とする請求項１０記載のクラスタリング装置。
【請求項１２】
前記１つまたは複数の仮クラスター群の特定を、
当該仮クラスターを代表する前記仮代表ベクトルの抽出元である前記選択画像領域中の画素に対応する前記特徴ベクトルを全て含み、かつ他の前記選択画像領域中の画素に対応する前記特徴ベクトルを含まない仮クラスターがある場合には、該仮クラスターを１つの仮クラスター群として特定する第１の手段と、
相互においてのみ当該仮クラスターを代表する前記仮代表ベクトルの抽出元である前記選択画像領域中の画素に対応する前記特徴ベクトルを交換している、複数の仮クラスターがある場合には、該複数の仮クラスターからなる群を１つの仮クラスター群として特定する第２の手段と、
前記第１の手段および前記第２の手段が特定した前記仮クラスター群のいずれにも属していない前記仮クラスターが残っている場合には、該残りの仮クラスターからなる群を１つの仮クラスター群として特定する第３の手段により行うことを特徴とする請求項１０記載のクラスタリング装置。
【請求項１３】
前記複数の画像領域が特定された場合に動作する手段が、前記仮クラスターへの再分類後、前記１つまたは複数の仮クラスター群の特定前において、前記仮クラスターの各々について、該仮クラスターに属する前記特徴ベクトルの総数に対し、該仮クラスターに属する対応の特徴ベクトルの数の割合が所定割合より少ない選択画像領域がある場合は、該選択画像領域に対応する前記特徴ベクトルを該仮クラスターから除外することを特徴とする請求項１１または１２記載のクラスタリング装置。
【請求項１４】
前記クラスターの各々に含まれる前記特徴ベクトルに基づいて、前記代表ベクトルを更新する手段をさらに備えていることを特徴とする請求項１０から１３いずれか１項記載のクラスタリング装置。
【請求項１５】
前記クラスターの各々に含まれる前記特徴ベクトルに基づいて、前記代表ベクトルを更新する手段と、
前記更新された代表ベクトルに基づいて前記クラスターを更新する手段をさらに備えていることを特徴とする請求項１０から１３いずれか１項記載のクラスタリング装置。
【請求項１６】
微小領域を非微小領域に統合することにより、前記現在画像を画像領域に分割する手段が規定した前記画像領域を更新する手段をさらに備えていることを特徴とする請求項１０から１５いずれか１項記載のクラスタリング装置。
【請求項１７】
前記複数の選択画像領域が、前記複数の画像領域の中から、構成画素数の多いものを順に複数選択したものであることを特徴とする請求項１０から１６いずれか１項記載のクラスタリング装置。
【請求項１８】
前記初期値を求める手段が、
ｎ個の画素からなる前記最低解像度画像から、１つの原代表ベクトルを導出する手段と、
前記ｎ個の画素の各々から抽出されたｎ個の特徴ベクトルと、前記原代表ベクトルとの、前記特徴ベクトル空間における距離を求め、最大距離を示す特徴ベクトルを代表ベクトル候補とするとともに、最も高い候補順位を付ける手段と、
残りの特徴ベクトルの各々と、前記原代表ベクトルおよび前記代表ベクトル候補のうち該特徴ベクトルに最も近いものとの、前記特徴ベクトル空間における距離を求め、最大距離を示す特徴ベクトルを前記代表ベクトル候補に追加するとともに、次に高い候補順位を付ける手段と、
前記次に高い候補順位を付ける手段を繰返し動作させる手段と、
前記候補順位に従って、前記代表ベクトル候補のうちの上位２つ以上の前記特徴ベクトルの各成分の値を、前記代表ベクトルの各成分の前記初期値とする手段を備えていることを特徴とする請求項１０から１７いずれか１項記載のクラスタリング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像から抽出した複数の特徴ベクトルを分類する方法および装置に関し、特に、領域分割処理等のために、特徴ベクトル空間におけるクラスタリングの手法を用いて、１枚の原画像の各画素から抽出した特徴ベクトルを、互いに類似したもの同士が属する複数のクラスターに分類する方法および装置に関する。
【０００２】
【従来の技術】
観測データや画像データの特徴が該特徴を表すｎ個のパラメータを成分とする特徴ベクトルとして表現できる場合のデータ分類手法として、複数の特徴ベクトルをｎ次元の特徴ベクトル空間に写像して、該特徴ベクトル空間における分布をもとにこれらの特徴ベクトルを複数のクラスターに分類する、いわゆるクラスタリングの手法が従来から知られている。クラスターとは、文字通り、特徴ベクトル空間における特徴ベクトルの「塊」であり、特徴ベクトル空間におけるユークリッド距離等を指標として、互いに近い特徴ベクトルが同一のクラスターに分類される。すなわち、同一のクラスターに属する特徴ベクトルは、互いに類似した特徴を表しているものである。
【０００３】
通常、クラスタリング処理に際しては、どの程度まで分類を行うかを示す一定値のパラメータを、処理開始に先立って指定しなくてはならない。たとえば、最終的なクラスターの個数や、クラスター中心と該クラスターに属する特徴ベクトル間の許容可能な最大距離が、かかるパラメータとして指定され得る。クラスターの個数等を固定しない自己収束形のアルゴリズムを使用する場合であっても、クラスターの拡がりに関するパラメータやクラスター間の距離に関するパラメータ等、どの程度まで分類を行うかを示す何らかの一定値のパラメータを指定する必要性は解消されない（たとえば、非特許文献１参照）。
【０００４】
【非特許文献１】
長尾真著、「画像認識論」、初版、コロナ社、昭和５８年２月１５日
、ｐ．１２０−１２６
【０００５】
【発明が解決しようとする課題】
クラスタリング処理に際してどの程度まで分類を行うべきかは、データの内容に強く依存する。とりわけ、多様性の高い画像データを対象とする場合には、適当な分類の程度は、各画像データによって大きく異なる。たとえば、１枚の画像を、該画像に含まれる「空」、「海」、「建物」等の撮影対象要素に対応する領域（以下、「オブジェクト領域」と呼ぶ）に分割する領域分割処理を行うために、該画像の各画素から抽出した特徴ベクトルをクラスタリング処理により分類する場合等には、各画像に含まれる撮影対象要素の数は多様であり、どの程度まで分類を行うべきかの画一的な基準を定めることは不可能である。すなわち、撮影対象要素として「空」と「海」のみを含む画像であれば、２つのオブジェクト領域に分割できればよいのであるから、分類の程度は粗くて足りるが、さらに「建物」、「木」、「土」等の多くの撮影対象要素を含む画像については、より細かい分類が必要である。この場合に、前者の画像に合わせた画一的な分類の程度の基準を採用すれば、後者の画像については十分な分類が行えないこととなり、後者の画像に合わせた画一的な基準を採用すれば、実際には「空」と「海」しか撮影されていない前者の画像を不必要に多くのオブジェクト領域に分割することとなる。
【０００６】
したがって、領域分割等を目的とする画像データを対象としたクラスタリング処理においては、分類対象としていかなる画像データが入力されても、その画像データ自体から該画像データに最適な分類の程度を特定し、安定した分類性能を実現する手法が強く望まれる。
【０００７】
本発明は、かかる事情に鑑み、好ましい分類の程度を指定するパラメータの入力を要さずに、１枚の原画像を表す入力された画像データ自体から最適な分類の程度を特定して、該原画像の各画素から抽出した特徴ベクトルの分類を行うクラスタリング方法および装置を提供することを目的とするものである。
【０００８】
【課題を解決するための手段】
すなわち、本発明に係る画像の特徴ベクトルのクラスタリング方法は、原画像から、段階的に解像度の異なる複数の複数画素からなる低解像度画像を導出する工程と、上記の複数の低解像度画像のうち解像度が最も低い最低解像度画像から、２つ以上の代表ベクトルの、各成分の初期値を求める工程と、解像度が次に低い画像を現在画像として、該現在画像の各画素から特徴ベクトルを抽出する工程と、該特徴ベクトルの各々を特徴ベクトル空間に写像する工程と、特徴ベクトル空間において、上記の特徴ベクトルを、上記の代表ベクトルの各々が代表するクラスターに分類する工程と、上記のクラスターの各々に属する特徴ベクトルに対応する画素の、現在画像上における分布に基づいて、現在画像を画像領域に分割する工程と、上記のクラスターの中から選択した１つの選択クラスターに対応する画像領域を特定する工程と、該特定により複数の画像領域が特定された場合に行う工程であって、該複数の画像領域の中から選択した複数の選択画像領域の各々から１つの仮代表ベクトルを抽出し、特徴ベクトル空間において、上記の複数の選択画像領域に属する画素に対応する特徴ベクトルを、上記の仮代表ベクトルの各々が代表する仮クラスターに再分類し、選択画像領域と仮クラスターの間の対応関係に基づく１つまたは複数の仮クラスター群を特定し、該仮クラスター群の各々を代表するベクトルを、上記の選択クラスターを代表する代表ベクトルに代えて新たな代表ベクトルとする工程と、全てのクラスターについて、上記の画像領域を特定する工程と上記の複数の画像領域が特定された場合に行う工程を繰り返す工程と、原画像が現在画像とされ、原画像の各画素から抽出された特徴ベクトルを分類する最終的な代表ベクトルが求められるまで、上記の特徴ベクトルを抽出する工程から上記の繰り返す工程を繰り返す工程を含むことを特徴とする方法である。
【０００９】
また、本発明に係る画像の特徴ベクトルのクラスタリング装置は、原画像から、段階的に解像度の異なる複数の複数画素からなる低解像度画像を導出する手段と、上記の複数の低解像度画像のうち解像度が最も低い最低解像度画像から、２つ以上の代表ベクトルの、各成分の初期値を求める手段と、解像度が次に低い画像を現在画像として、該現在画像の各画素から特徴ベクトルを抽出する手段と、該特徴ベクトルの各々を特徴ベクトル空間に写像する手段と、特徴ベクトル空間において、上記の特徴ベクトルを、上記の代表ベクトルの各々が代表するクラスターに分類する手段と、上記のクラスターの各々に属する特徴ベクトルに対応する画素の、現在画像上における分布に基づいて、現在画像を画像領域に分割する手段と、上記のクラスターの中から選択した１つの選択クラスターに対応する画像領域を特定する手段と、該特定により複数の画像領域が特定された場合に動作する手段であって、該複数の画像領域の中から選択した複数の選択画像領域の各々から１つの仮代表ベクトルを抽出し、特徴ベクトル空間において、上記の複数の選択画像領域に属する画素に対応する特徴ベクトルを、上記の仮代表ベクトルの各々が代表する仮クラスターに再分類し、選択画像領域と仮クラスターの間の対応関係に基づく１つまたは複数の仮クラスター群を特定し、該仮クラスター群の各々を代表するベクトルを、上記の選択クラスターを代表する代表ベクトルに代えて新たな代表ベクトルとする手段と、全てのクラスターについて、上記の画像領域を特定する手段と上記の複数の画像領域が特定された場合に動作する手段を繰返し動作させる手段と、原画像が現在画像とされ、原画像の各画素から抽出された特徴ベクトルを分類する最終的な代表ベクトルが求められるまで、上記の特徴ベクトルを抽出する手段から上記の繰返し動作させる手段を繰返し動作させる手段を備えていることを特徴とする装置である。
【００１０】
ここで、本発明において「低解像度画像」とは、原画像よりも画素数の少ない複数画素からなる画像であって、原画像を基として、ガウシアンピラミッド、線形補間、スプライン補間、ウェーブレット変換等を利用した画像縮小処理により順次求められるものを指す。画像の縦方向と横方向に対して、異なる縮小率を適用してもよい。
【００１１】
また、本発明において「特徴ベクトル」とは、画像の各画素から抽出されるベクトルであって、当該画像の特徴を示す複数のパラメータ（以下、「特徴量」と呼ぶ）を成分とするベクトルを指す。特徴ベクトルの成分である特徴量としては、たとえば色の特徴、輝度の特徴、テクスチャーの特徴、奥行情報、該画像に含まれるエッジの特徴等を示す特徴量が使用され得る。また、「特徴ベクトル空間」とは、上記の特徴ベクトルの各成分を座標とする空間を指す。たとえば、特徴ベクトルがＹＣＣ表色系における各画素の輝度成分および２つの色差成分を成分とするベクトルである場合には、３次元のＹＣＣ表色系空間が特徴ベクトル空間となる。
【００１２】
さらに、本発明において「代表ベクトル」とは、特徴ベクトル空間において規定される各クラスターを代表するベクトルを指し、クラスターごとに１つの代表ベクトルが割り当てられる。
【００１３】
また、本発明において「画像領域」とは、実画像空間、すなわち低解像度画像または原画像自体の上で、特徴ベクトル空間において同一クラスターに属する特徴ベクトルに対応する画素が形成する島状の各領域を指す。実画像空間においては、同じような特徴を有する領域が互いに分離して複数存在することもあるので、特徴ベクトル空間における１つのクラスターが、２つ以上の画像領域に対応することもある。クラスタリング処理が最適な分類の程度で行われれば、原画像における画像領域は、「空」、「海」、「建物」等の各撮影対象要素に対応するオブジェクト領域となる。
【００１４】
さらに、本発明において「仮代表ベクトル」とは、各選択画像領域の特徴を代表する、特徴ベクトルと同次元の１つのベクトルを指し、たとえば、各選択画像領域に属する画素に対応する特徴ベクトルの各成分の平均値を成分とするベクトル等を使用することができる。
【００１５】
また、本発明において「選択画像領域と仮クラスターの間の対応関係に基づく１つまたは複数の仮クラスター群を特定する」とは、実画像空間において互いに分離されている選択画像領域が、特徴ベクトル空間においても互いに分離できるものであるか否かに基づき、特徴ベクトル空間においても互いに分離される選択画像領域の群に対応する仮クラスターの群を特定することを指す。すなわち、本発明は、実画像空間において互いに集合して１つの画像領域を形成する画素に対応する特徴ベクトルは、特徴ベクトル空間においても１つのクラスターを形成する可能性が高いことに鑑み、１つのクラスターに対応する画像領域が実画像空間において分離して複数存在する場合には、該画像領域の中から選択した複数の選択画像領域を区別することが適当か否かを特徴ベクトル空間において調べ、適当である場合にはそれらを区別するように代表ベクトルを置き換えるものである。
【００１６】
また、上記の１つまたは複数の仮クラスター群の特定は、当該仮クラスターを代表する仮代表ベクトルの抽出元である選択画像領域中の画素に対応する特徴ベクトルを全て含み、かつ他の選択画像領域中の画素に対応する特徴ベクトルを含まない仮クラスターがある場合には、該仮クラスターを１つの仮クラスター群として特定し、さらに、そのように特定された仮クラスター群のいずれにも属していない仮クラスターが残っている場合には、該残りの仮クラスターからなる群を１つの仮クラスター群として特定するものであってもよい。あるいは、上記の１つまたは複数の仮クラスター群の特定は、当該仮クラスターを代表する仮代表ベクトルの抽出元である選択画像領域中の画素に対応する特徴ベクトルを全て含み、かつ他の選択画像領域中の画素に対応する特徴ベクトルを含まない仮クラスターがある場合には、該仮クラスターを１つの仮クラスター群として特定し、さらに、相互においてのみ当該仮クラスターを代表する仮代表ベクトルの抽出元である選択画像領域中の画素に対応する特徴ベクトルを交換している、複数の仮クラスターがある場合には、該複数の仮クラスターからなる群を１つの仮クラスター群として特定し、さらに、そのように特定された仮クラスター群のいずれにも属していない仮クラスターが残っている場合には、該残りの仮クラスターからなる群を１つの仮クラスター群として特定するものであってもよい。これらの場合において、仮クラスターへの再分類の後、仮クラスター群の特定前に、仮クラスターの各々について、該仮クラスターに属する特徴ベクトルの総数に対し、該仮クラスターに属する対応の特徴ベクトルの数の割合が所定割合より少ない選択画像領域がある場合は、該選択画像領域に対応する特徴ベクトルを該仮クラスターから除外してもよい。
【００１７】
ここで、「相互においてのみ当該仮クラスターを代表する仮代表ベクトルの抽出元である選択画像領域中の画素に対応する特徴ベクトルを交換している複数の仮クラスター」とは、当該複数の仮クラスターの各々が、いずれの選択画像領域に由来する特徴ベクトルを含んでいるかのパターンが同一であり、かつ、それらの選択画像領域に由来する特徴ベクトルが、他の仮クラスターには含まれていないことを指す。
【００１８】
また、上記の本発明に係るクラスタリング方法または装置は、分類されたクラスターの各々に含まれる特徴ベクトルに基づいて、代表ベクトルを更新する工程または手段をさらに含むものであってもよい。さらに、これに加えて、更新された代表ベクトルに基づいてクラスターを更新する工程または手段をさらに含むものであってもよい。
【００１９】
ここで、「代表ベクトルを更新する」とは、分類により規定されたクラスターをより適切に代表するベクトルを、新たな代表ベクトルとすることであって、たとえば、規定された各クラスターに属する特徴ベクトルの重心を示すベクトルを、もとの代表ベクトルに代えて、新たな代表ベクトルとすること等を指す。また、「クラスターを更新する」とは、上記のように更新された代表ベクトルに基づいてクラスタリングによる分類をし直すことであって、たとえば、各特徴ベクトルを、特徴ベクトル空間におけるユークリッド距離が最も近い新たな代表ベクトルが代表するクラスターに分類し直すこと等を指す。
【００２０】
また、上記の本発明に係るクラスタリング方法または装置は、微小領域を非微小領域に統合することにより、画像領域を更新する工程または手段をさらに含むものであってもよい。
【００２１】
ここで、「微小領域」とは、画像領域のうち、現在画像をなす画素数の所定割合（たとえば１／１０００程度）より少ない数の画素からなる、いわゆるノイズと考えられるような領域を指す。一方、「非微小領域」とは、画像領域のうち、微小領域でないものを指す。
【００２２】
また、上記の複数の選択画像領域は、上記の複数の画像領域の中から、構成画素数の多いものを順に複数選択したものであってもよい。
【００２３】
また、上記の代表ベクトルの各成分の初期値を求めるに際しては、ｎ個の画素からなる最低解像度画像から、１つの原代表ベクトルを導出し、該ｎ個の画素の各々から抽出されたｎ個の特徴ベクトルと、原代表ベクトルとの、特徴ベクトル空間における距離を求め、最大距離を示す特徴ベクトルを代表ベクトル候補とするとともに、最も高い候補順位を付け、残りの特徴ベクトルの各々と、原代表ベクトルおよび上記の代表ベクトル候補のうち該特徴ベクトルに最も近いものとの、特徴ベクトル空間における距離を求め、最大距離を示す特徴ベクトルを代表ベクトル候補に追加するとともに、次に高い候補順位を付け、かかる次に高い候補順位を付ける処理を繰り返し、該候補順位に従って、上記の代表ベクトル候補のうちの上位２つ以上の特徴ベクトルの各成分の値を、上記の初期値としてもよい。
【００２４】
ここで、特徴ベクトル空間における「距離」とは、典型的には特徴ベクトル空間における２つのベクトル間のユークリッド距離を指すが、特徴ベクトル空間における２つのベクトルの近接度合いを適当に表す指標であれば、ユークリッド距離に限られないものとする。
【００２５】
また、「原代表ベクトル」とは、最低解像度画像を代表する１つのベクトルであって、たとえば最低解像度画像の各画素から抽出される特徴ベクトルの各成分の平均値を成分とするベクトル等が使用され得る。
【００２６】
【発明の効果】
本発明に係る画像の特徴ベクトルのクラスタリング方法および装置は、入力された原画像自体から導出した最低解像度画像に基づいて代表ベクトルの各成分の初期値を求め、これらの初期値を利用して、解像度が次に低い画像における特徴ベクトルの最適な分類を順次求めていき、最終的には原画像の各画素から抽出した特徴ベクトルの分類を求めるものであるので、好ましい分類の程度を指定するパラメータの入力を要さずに、原画像の内容に応じた最適な分類の程度により、原画像の各画素から抽出した特徴ベクトルの分類を行うことができる。したがって、いかなる原画像が入力されても、安定した分類性能を実現することができ、様々な撮影対象要素を含む多数の画像に対して、連続して領域分割処理を施す場合等に極めて有効である。
【００２７】
また、本発明に係るクラスタリング方法または装置は、上記のとおり、各低解像度画像または原画像における特徴ベクトルの最適な分類を求めるにあたり、実画像空間において互いに集合して１つの画像領域を形成する画素に対応する特徴ベクトルは、特徴ベクトル空間においても１つのクラスターを形成する可能性が高いことに鑑み、実画像空間における選択画像領域と特徴ベクトル空間における仮クラスターとの対応関係に基づいて、新たな代表ベクトルを追加していくものである。したがって、本発明に係るクラスタリング方法および装置は、実画像空間における情報を反映しながら最適な分類のための代表ベクトルを求めていくので、１枚の原画像の実画像空間を、該原画像に含まれる「空」、「海」、「建物」等の撮影対象要素に対応するオブジェクト領域に分割する領域分割処理等への応用に特に適している。
【００２８】
さらに、本発明に係る画像の特徴ベクトルのクラスタリング方法および装置は、低解像度化された画像すなわち特徴ベクトル数を減じた画像において順次分類処理を行っていくものであるため、従来のクラスタリング処理と比較して、計算量が過大となることもない。
【００２９】
【発明の実施の形態】
以下、図面により、本発明の例示的な実施形態を詳細に説明する。
【００３０】
図１は、本発明の１つの実施形態であるクラスタリング処理の手順を示したフローチャートである。このクラスタリング処理は、最終的には原画像の各画素から抽出した特徴ベクトルを、複数のクラスターに分類することを目的とするものであり、原画像を「空」、「海」、「建物」等の撮影対象要素に対応する複数の画像領域に分割する領域分割処理等に利用できる。なお、本実施形態では、原画像は１０２４×１０２４画素のデジタル写真画像であるとし、特徴ベクトルは、ＹＣＣ表色系で表された輝度成分および２つの色差成分を成分とする３次元のベクトルであるとする。
【００３１】
原画像が入力されると、まず図１のステップ１０において、段階的に解像度の異なる複数の低解像度画像が導出される。本実施形態では、図２に示すように、原画像から出発して、縦横の画素数をそれぞれ２分の１とした低解像度画像を順次求めていき、最終的には第９低解像度画像すなわち画素数２×２の低解像度画像まで求めるものとする。この画素数２×２の低解像度画像が、本実施形態における最低解像度画像である。
【００３２】
これらの各低解像度画像を求めるための画像縮小処理の手法としてはいかなる手法を用いてもよいが、本実施形態ではガウシアンピラミッドによる縮小処理を用いるものとする。ガウシアンピラミッドによる縮小処理とは、縮小対象の画像にガウシアンフィルターを適用していわばぼやかした画像を導出するステップと、そのようにぼやかした画像の画素を１つおきに拾って縦横の画素数をそれぞれ２分の１とした画像を導出するステップを順次繰り返して、段階的に解像度の異なる低解像度画像を導出していく処理である。使用されるガウシアンフィルターは、たとえばフィルターの大きさが５×５であれば、図３のようになる。なお、画像端の処理に関しては、たとえば図３に示した５×５の大きさのフィルターを使用する場合には、縮小対象の画像の各辺に２行分または２列分の適当な画素値を有する画素を便宜的に追加することにより、もとの縮小対象の画像と同じ大きさのぼやかした画像を導出することができる。追加する画素の「適当な画素値」としては、ゼロ値や、画像端の画素値を繰り返した値等が使用され得る。
【００３３】
低解像度画像の導出が終了すると、次に、図１のステップ１２において、最低解像度画像（２×２画素）を基に、２つ以上の初期代表ベクトル、すなわち代表ベクトルの各成分の初期値が導出される。この初期代表ベクトル導出処理を、以下、図４のフローチャートならびに図５の概念図に沿って詳細に説明する。
【００３４】
まず、図４のステップ４０において、最低解像度画像から１つの原代表ベクトルが導出される。本実施形態では、最低解像度画像をなす４つの画素から抽出した特徴ベクトルの各成分の平均値を成分とする１つのベクトルを、原代表ベクトルとする。たとえば、図５の（ａ）に示した特徴ベクトル空間において、４つのベクトルＯＢ１、ＯＢ２、ＯＢ３およびＯＢ４が最低解像度画像をなす４つの画素から抽出された特徴ベクトルであるとすると、原代表ベクトルはＯＡのようになる。なお、特徴ベクトルＯＢ１、ＯＢ２、ＯＢ３およびＯＢ４のそれぞれの抽出元の画素は、図２に示すとおりである。
【００３５】
次に、図４のステップ４２において、上記の４つの特徴ベクトルの各々と、原代表ベクトルとの距離を算出する。本実施形態では、この距離は特徴ベクトル空間におけるユークリッド距離であるとする。図５の（ａ）の例では、算出される距離はそれぞれｄ１、ｄ２、ｄ３およびｄ４である。
【００３６】
続いて、ステップ４４において、ステップ４２で算出した距離のうち最大の距離を示す特徴ベクトルを、候補順位第１位の代表ベクトル候補とする。図５の（ａ）の例では、距離ｄ１、ｄ２、ｄ３およびｄ４のうち最大距離はｄ１であり、したがって最大距離を示す特徴ベクトルはベクトルＯＢ２であるので、ベクトルＯＢ２が、候補順位第１位の代表ベクトル候補すなわち第１代表ベクトル候補とされる。
【００３７】
次に、ステップ４６において、残りの特徴ベクトルすなわち３つのベクトルＯＢ１、ＯＢ３およびＯＢ４の各々と、原代表ベクトルＯＡおよび代表ベクトル候補ＯＢ２のうちその特徴ベクトルとの距離が最も近いものとの距離が特定される。この例では、図５の（ｂ）に示すように、ベクトルＯＢ４については、代表ベクトル候補ＯＢ２との距離の方が原代表ベクトルＯＡとの距離よりも小さいため、図示のように距離ｄ１’が特定される。ベクトルＯＢ１およびＯＢ３については、原代表ベクトルＯＡとの距離の方が代表ベクトル候補ＯＢ２との距離よりも小さいため、距離ｄ２’およびｄ３’が特定される。
【００３８】
続いて、ステップ４８において、ステップ４６で算出した距離のうち最大の距離を示す特徴ベクトルを、次に高い候補順位の代表ベクトル候補とする。図５の（ｂ）の例では、最大距離ｄ１’を示す特徴ベクトルはベクトルＯＢ４であるので、ベクトルＯＢ４が、候補順位第２位の第２代表ベクトル候補とされる。
【００３９】
次に、ステップ５０において、まだ候補順位を付けていない特徴ベクトルがあるか否かが確認される。ここでは、まだ特徴ベクトルＯＢ１およびＯＢ３に候補順位が付けられていないので、処理はステップ４６に戻る。ここで再び行われるステップ４６では、図５の（ｃ）に示すように、ベクトルＯＢ１およびＯＢ３のいずれについても、原代表ベクトルＯＡおよび代表ベクトル候補ＯＢ２ならびにＯＢ４のうちもっとも距離が近いベクトルは原代表ベクトルＯＡであるので、図示のように原代表ベクトルＯＡとの距離ｄ１’’およびｄ２’’が特定される。続くステップ４８においては、距離ｄ１’’の方がｄ２’’よりも大きいので、特徴ベクトルＯＢ１が候補順位第３位の第３代表ベクトル候補とされる。
【００４０】
このようにして、４つ全ての特徴ベクトルに候補順位が付けられるまで、図４のステップ４６からステップ５０が繰り返され、最終的には各特徴ベクトルがＯＢ２、ＯＢ４、ＯＢ１、ＯＢ３の順に代表ベクトル候補に追加され、候補順位第１位から第４位が付けられることとなる。
【００４１】
続いて、図４のステップ５２において、代表ベクトル候補に追加された際の上記の最大距離の変化量が最大であった特徴ベクトルの候補順位が、第２位以下であるか否かが確認される。図５に沿って上記に説明したとおり、この例では、特徴ベクトルＯＢ２が第１代表ベクトル候補として代表ベクトル候補に追加された際には、最大距離はｄ１からｄ１’に変化しており、次に特徴ベクトルＯＢ４が代表ベクトル候補に追加された際には、最大距離はｄ１’からｄ１’’に変化している。この最大距離の変化の様子を図示すると、図６のようになる。すなわち、この例では、最大距離の変化量は、候補順位第３位の特徴ベクトルＯＢ１が代表ベクトル候補に追加されたときが最大であるので、図１の処理はステップ５４へと進み、候補順位第３位までの特徴ベクトル、すなわちベクトルＯＢ２、ＯＢ４およびＯＢ１の３つが、初期代表ベクトルＯＲ１、ＯＲ２およびＯＲ３とされる。一方、仮にステップ５２で確認された候補順位が第１位の候補順位である場合には、図１の処理はステップ５６へと進み、候補順位第２位の特徴ベクトルまでが初期代表ベクトルＯＲ１およびＯＲ２とされる。
【００４２】
ここで、本実施形態では、上記のとおり特徴ベクトル空間における最大距離の変化量を基準として初期代表ベクトルを選択したが、平均距離の変化量等を基準としてもよい。あるいは、最低解像度画像では画素数は相当に減じられているので（本実施形態では４画素）、最低解像度画像の各画素から抽出した特徴ベクトルの全てを初期代表ベクトルとしてもよい。要するに、外部からの何らかのパラメータの入力を要さずに、原画像から導出した最低解像度画像自体から、所定の処理により該原画像に応じた２つ以上の初期代表ベクトルを求めるものであれば、本発明の範囲に属するものである。
【００４３】
図１に戻り、続いてステップ１４において、解像度が次に低い画像、すなわち画素数４×４の第８低解像度画像が現在画像とされ、該現在画像における分類処理が開始される。以下、図７から図１０も参照しながら、画素数４×４の現在画像における分類処理について順を追って説明する。
【００４４】
まず、図１のステップ１６において、現在画像をなす１６個の画素の各々から、ＹＣＣ表色系における輝度成分および２つの色差成分を成分とする特徴ベクトルが抽出され、それらの１６個の特徴ベクトルが、特徴ベクトル空間すなわちＹＣＣ表色系空間に写像される。
【００４５】
続いて、ステップ１８において、上記の１６個の特徴ベクトルを、各代表ベクトルが代表するクラスターに分類する。現在の代表ベクトルは、最低解像度画像から導出した初期代表ベクトルＯＲ１、ＯＲ２およびＯＲ３であるので、これらに代表される３つのクラスターに１６個の特徴ベクトルを分類する。本実施形態では、特徴ベクトル空間におけるユークリッド距離を基準として、距離が最も近い代表ベクトルが代表するクラスターに、各特徴ベクトルを分類するものとする。
【００４６】
次に、ステップ２０において、上記のクラスターによる特徴ベクトルの分類に従って、現在画像を画像領域に分割する。図７を用いて説明すると、図７の（ａ）は図２に示したものと同一の最低解像度画像を示している。図７の（ｂ）は４×４画素の現在画像であり、各画素から抽出された特徴ベクトルが、前のステップ１６において代表ベクトルＯＲ１、ＯＲ２およびＯＲ３が代表するクラスターのいずれに分類されたかが示されている。本実施形態では、この現在画像に対し、ラスター走査や領域拡張等の手法により、実画像空間において互いに分離した島状の各領域をなす画素に同一のラベルを付けるラベリング処理を施す。すると、図７の（ｃ）に示すように、各画素に０から３のラベルが付けられる。これらのラベルに基づいて、図７の（ｄ）に示すように、４つの画像領域６０、６２、６４および６６を規定する。ここで、画像領域６０および６６をなす各画素から抽出された特徴ベクトルは、特徴ベクトル空間においては代表ベクトルＯＲ３が代表する１つのクラスターに属しているが、実画像空間では、これらの画素は図示のように画像領域６４によって隔てられているので、別個の画像領域６０および６６を構成する。
【００４７】
続いて、図１のステップ２２において、３つのクラスターの中から選択された１つの選択クラスターに対応する画像領域が特定され、ステップ２４において、特定された画像領域が複数であるか否かが確認される。この例では、図７の（ｄ）に示すとおり、選択クラスターが代表ベクトルＯＲ１またはＯＲ２に代表されるクラスターであるときは、対応する画像領域は画像領域６２または６４の１つしかないので、図１の処理は後述するステップ３６に進むが、選択クラスターが代表ベクトルＯＲ３に代表されるクラスターであるときは、対応する画像領域が２つ（すなわち、画像領域６０と６６）あるので、ステップ２６から３４の処理へと進む。以下、これらのステップ２６から３４の処理を説明する。
【００４８】
まず、ステップ２６において、ステップ２２で特定された複数の画像領域の中から、複数の選択画像領域が選択される。本実施形態では、選択画像領域として、構成画素数の多い順から２つの画像領域を選択するものとする。ここでは、特定された画像領域はもともと画像領域６０と６６の２つであるので、これら双方が選択画像領域として選択される。なお、図８の（ａ）は、特徴ベクトル空間における、画像領域６０および６６に属する画素に対応する特徴ベクトルの分布、および現在の選択クラスターの代表ベクトルＯＲ３を示した図である。
【００４９】
続いて、ステップ２８において、選択画像領域６０および６６から、各々１つの仮代表ベクトルが抽出される。本実施形態では、仮代表ベクトルとして、各選択画像領域に属する画素に対応する特徴ベクトルの各成分の平均値を成分とするベクトルを使用するものとする。以下、選択画像領域６０および６６から抽出された仮代表ベクトルを、それぞれベクトルＯＴ１およびＯＴ２とする。
【００５０】
次に、ステップ３０において、選択画像領域６０および６６に属する画素に対応する特徴ベクトルが、上記のステップ２８で抽出された各仮代表ベクトルＯＴ１およびＯＴ２が代表する仮クラスターＣ１およびＣ２に再分類される。本実施形態では、ステップ１８における分類と同様に、特徴ベクトル空間におけるユークリッド距離を基準として、距離が最も近い仮代表ベクトルが代表する仮クラスターに、各特徴ベクトルを分類するものとする。ここでは、仮クラスターへの再分類は図８の（ｂ）に実線で示すようになる。
【００５１】
続いて、ステップ３２において、選択画像領域６０および６６と仮クラスターＣ１およびＣ２の対応関係に基づいて、仮クラスター群を特定する。本実施形態では、このステップ３２は、図９のフローチャートに示す処理により行うものとする。
【００５２】
図９に示した処理は、仮クラスターの各々について、その仮クラスターが、該仮クラスターを代表する仮代表ベクトルの抽出元である選択画像領域中の画素に対応する特徴ベクトルを全て含み、かつ他の選択画像領域中の画素に対応する特徴ベクトルを含まない仮クラスターであるか否かを調べ（ステップ７０）、そのような仮クラスターである場合には、その１つの仮クラスターが各々１つの仮クラスター群を構成するものとし（ステップ７２）、さらにまだ残っている仮クラスターがある場合には（ステップ７４）、それらの残りの仮クラスターをまとめて別の１つの仮クラスター群とする（ステップ７６）ものである。本実施形態では、ステップ２６において構成画素数の多い順から２つの画像領域を選択画像領域として選択することとしているので、図９に示した処理は、言いかえれば、２つの選択画像領域の各々に属する画素と、２つの仮クラスターの各々に属する特徴ベクトルとの間に、完全な対応関係がある場合には、２つの仮クラスターが各々１つ、すなわち合計２つの仮クラスター群を構成するものとし、かかる完全な対応関係がない場合には、２つの仮クラスターがまとめて１つの仮クラスター群のみを構成するものとする処理である。ここでは、図８の（ｂ）に示すように、画像領域６０中の画素に対応する特徴ベクトルは全て仮クラスターＣ１に属しており、かつ、画像領域６６中の画素に対応する特徴ベクトルは全て仮クラスターＣ２に属している。すなわち、上記の完全な対応関係があるので、図８の（ｂ）に破線で示すように、仮クラスターＣ１およびＣ２は、各々１つの仮クラスター群を構成するものとされる。
【００５３】
その後、図１のステップ３４において、現在の選択クラスターを代表する代表ベクトルＯＲ３に代えて、各仮クラスター群を代表するベクトルが新たな代表ベクトルとされる。ここでは、仮クラスターＣ１およびＣ２が各々１つの仮クラスター群を構成することとされたので、上記の仮代表ベクトルＯＴ１およびＯＴ２を、各仮クラスター群を代表するベクトルとして採用し、代表ベクトルＯＲ３に代わる新たな代表ベクトルとするものとする。
【００５４】
ここで、上記のステップ３２および３４の意義について説明する。図２に示した原画像と図７の（ｄ）を比較すると、現在画像の画像領域６０に属する各画素は、主に原画像における空の部分の特徴が圧縮された画素であり、画像領域６６に属する各画素は、主に原画像における水の部分の特徴が圧縮された画素であることが分かる。空の部分と水の部分は共に青みを帯びた色をしており、それらの特徴の差は、たとえば空の部分の特徴と草原の部分の特徴との差に比べれば小さいが、やはり空の部分の画素と水の部分の画素とをそれぞれ多数集めて特徴ベクトルを抽出した場合、特徴ベクトル空間においても徐々に空の部分と水の部分が区別されてくるものと考えられる。一方、空の部分と水の部分のように特徴が比較的類似しているが異なる撮影対象要素に対応する部分は、実画像空間においては、画素数が少ない低解像度画像ではぼやけて一繋がりの画像領域を形成してしまう傾向があるが、画像が高解像度化されて（すなわち画素数が増えて）各撮影対象要素の輪郭が徐々にはっきりしてくると、互いに分離した画像領域を形成し始める。上記の例では、最低解像度画像から４×４画素の現在画像に進んだ際に、画像領域６０および６６が実画像空間において分離した。そこで、画像領域６０および６６の各々から仮代表ベクトルを抽出して仮クラスターへの再分類を行ってみると、特徴ベクトル空間においても、主に空の部分の特徴が圧縮された画像領域６０の画素と、主に水の部分の特徴が圧縮された画像領域６６の画素とが、完全に分離された。そこで、実画像空間における情報をクラスタリング処理に反映するため、仮代表ベクトルＯＴ１およびＯＴ２を代表ベクトルＯＲ３に代わる新たな代表ベクトルとした。
【００５５】
一方、上記の例とは異なるが、仮に、２つの選択画像領域に属する各画素に対応する特徴ベクトルの分布が図１０の（ａ）のようであったとすると、仮代表ベクトルＯＴ１およびＯＴ２による仮クラスターＣ１およびＣ２への再分類は、図１０の（ｂ）に実線で示すようになる。この場合、各仮クラスターには２つの選択画像領域に由来する特徴ベクトルが混在しており、２つの選択画像領域の各々に属する画素と、２つの仮クラスターの各々に属する特徴ベクトルとの間には、上記のような完全な対応関係がない。このような事態は、たとえば、原画像に水の部分が複数存在し、２つの選択画像領域が実画像空間において分離した領域であるが、共に水の部分に対応する場合等に生じるものであり、かかる場合には仮クラスターＣ１に属する特徴ベクトルと仮クラスターＣ２に属する特徴ベクトルが分別されるようなクラスタリング処理を行うことは適切でない。したがって、図９に示した処理に従うと、図１０の（ｂ）に破線で示すように、仮クラスターＣ１およびＣ２は、まとめて１つの仮クラスター群を構成する。この場合、当該仮クラスター群を代表するベクトルとして、もとの選択クラスターの代表ベクトルＯＲ３を採用するものとする。すなわち、図１のステップ３４以降でも、もとの代表ベクトルＯＲ３が引続き代表ベクトルとして使用されることになる。
【００５６】
以上のステップ２６から３４の処理が終了すると、図１のステップ３６において、まだ対応する画像領域を特定していないクラスターがあるか否かが確認され、すべてのクラスターについてステップ２２から３６の処理が繰り返される。
【００５７】
その後、ステップ３８へと進み、現在画像が原画像であるか否かが確認される。ここでは、現段階での原画像は４×４画素の第８低解像度画像であるので、図１に示す処理はステップ１４へと戻り、原画像が現在画像とされ、原画像の各画素から抽出された特徴ベクトルを分類する最終的な代表ベクトルが求められるまで、ステップ１４から３８の処理が繰り返される。
【００５８】
以上説明した実施形態によれば、入力された原画像自体から導出した画素数２×２の最低解像度画像に基づいて２つ以上の初期代表ベクトルが求められ、これらの初期代表ベクトルを利用して解像度が次に低い画像における特徴ベクトルの最適な分類を順次求めていくことにより、最終的には原画像の各画素から抽出した特徴ベクトルの分類が求められるので、外部からのパラメータの入力を要さずに、原画像の内容に応じた最適な分類の程度により分類を行うことができる。したがって、いかなる原画像が入力されても、安定した分類性能を実現することができる。
【００５９】
また、上記の実施形態によれば、各低解像度画像または原画像において、実画像空間における情報を反映しながら最適な分類のための代表ベクトルが順次求められていくので、領域分割処理等への応用に特に適している。
【００６０】
次に、上記の実施形態の変更例について、図１１および１２を参照しながら説明する。この変更例における処理は、図１のステップ２６において構成画素数の多い順から５つの画像領域（画像領域の数が２つから４つであるときは全ての画像領域）が選択画像領域とされる点、およびステップ３２において図９に示した処理に代えて図１２に示した処理が行われる点を除けば、上記の実施形態における処理と同様である。
【００６１】
この変更例の説明のため、ある低解像度画像において一繋がりであった画像領域が、解像度が次に低い画像に進んだ際に実画像空間において５つ以上の画像領域に分離し、画像領域ＩからＶの５つが選択画像領域として選択されたとする。これらの選択画像領域ＩからＶに属する画素に対応する特徴ベクトルの特徴ベクトル空間における分布、これらの選択画像領域から抽出された仮代表ベクトルＯＴＩからＯＴＶの分布、およびこれらの仮代表ベクトルが代表する仮クラスターＣＩからＣＶによる分類は、図１１に示すとおりであるとする。
【００６２】
ここで、図１２に示す処理を行うと、まずステップ８０において、仮クラスターＣＩからＣＶの各々について、その仮クラスターが、該仮クラスターを代表する仮代表ベクトルの抽出元である選択画像領域中の画素に対応する特徴ベクトルを全て含み、かつ他の選択画像領域中の画素に対応する特徴ベクトルを含まない仮クラスターであるか否かが調べられる。図１１の例では、仮クラスターＣＩが、抽出元である選択画像領域Ｉ中の画素に対応する特徴ベクトルを全て含み、かつ他の選択画像領域ＩＩからＶ中の画素に対応する特徴ベクトルを含まないものであるので、図１１の処理はステップ８２へと進み、この仮クラスターＣＩが、単独で１つの仮クラスター群を構成するものとされる。
【００６３】
続いて、ステップ８４において、残りの仮クラスターＣＩＩからＣＶについて、相互においてのみ、該仮クラスターを代表する仮代表ベクトルの抽出元である選択画像領域中の画素に対応する特徴ベクトルを交換している複数の仮クラスターがあるか否かが確認される。図１１の例では、仮クラスターＣＩＩとＣＩＩＩが、共に選択画像領域ＩＩおよびＩＩＩに由来する特徴ベクトルのみを含んでおり、そのパターンが同一である。加えて、選択画像領域ＩＩおよびＩＩＩに由来する特徴ベクトルは、他の仮クラスターＣＩ、ＣＩＶおよびＣＶのいずれにも含まれていない。したがって、仮クラスターＣＩＩとＣＩＩＩは、相互においてのみ、該仮クラスターを代表する仮代表ベクトルＯＴＩＩおよびＯＴＩＩＩの抽出元である選択画像領域ＩＩおよびＩＩＩ中の画素に対応する特徴ベクトルを交換している複数の仮クラスターに相当し、ステップ８６において、仮クラスターＣＩＩとＣＩＩＩからなる群が、１つの仮クラスター群として特定される。仮クラスターＣＩＶとＣＶの組についても、同様のことが言える。
【００６４】
最後に、ステップ８８において、まだ仮クラスター群のいずれにも属していない仮クラスターが残っているか否かが確認され、残っている場合には、ステップ９０において、それらの残りの仮クラスターをまとめてさらに１つの仮クラスター群を特定する。図１１の例では、もう残っている仮クラスターはないので、さらなる仮クラスター群の特定はせずに、図１２に示した処理は終了する。
【００６５】
以上の処理により、図１１に破線で示すような３つの仮クラスター群が特定される。このような状態は、たとえば、選択画像領域ＩからＶのうち、領域Ｉが山の部分、領域ＩＩおよびＩＩＩが道や川の部分を隔てて実画像空間において分離された２つの草原の部分、領域ＩＶおよびＶが実画像空間において互いに分離された２つの樹木の部分に相当する場合等に生じる。
【００６６】
ここで、図８から１０を用いて説明した上記の実施形態においては、２つの仮クラスターのいずれかに、異なる選択画像領域に由来する特徴ベクトルが１つでも混在している場合には、２つの仮クラスターは１つの仮クラスター群に属するものとされ、代表ベクトルが増やされない。上記に詳述した４×４画素程度の低解像度画像を現在画像として扱っている初期の段階ではそのような処理は好ましいが、現在画像の解像度が次第に大きくなると、大半の特徴ベクトルが各選択画像領域に対応する仮クラスターに分類されているのに、異なる選択画像領域に由来する特徴ベクトルが数個混在しているだけで２つの仮クラスターを異なる仮クラスター群に分類しないこととしたのでは、代表ベクトルの数が有効に増えていかず、最適な分類の程度によるクラスタリング処理ができない場合がある。同様の事態は、図１１および１２を用いて説明した変更例においても生じ得る。かかる事態を防ぐため、上記の実施形態および変更例においては、図１のステップ３０とステップ３２の間に、仮クラスターの各々について、該仮クラスターに属する特徴ベクトルの総数に対し、該仮クラスターに属する対応の特徴ベクトルの数の割合が所定割合より少ない選択画像領域がある場合は、該選択画像領域に対応する特徴ベクトルを該仮クラスターから除外するステップがさらに含まれていてもよい。この「所定割合」としては、たとえば５％程度の値が採用され得る。
【００６７】
また、分類結果の一層の適正化のために、図１のステップ１８とステップ２０の間に、各クラスターに含まれる特徴ベクトルに基づいて、各代表ベクトルをより適切なものに更新するステップが含まれていてもよい。たとえば、各クラスターに属する特徴ベクトルの重心を示すベクトル等が、新たな代表ベクトルとして採用され得る。これに加えて、更新された代表ベクトルに基づいて、ユークリッド距離等を基準として特徴ベクトルの分類をし直し、クラスターを更新するステップがさらに含まれていてもよい。
【００６８】
さらに、現在画像をなす画素数の所定割合（たとえば１／１０００程度）より少ない数の画素からなる、いわゆるノイズと考えられるような画像領域を排除するために、図１のステップ２０とステップ２２の間に、微小領域を非微小領域に統合することにより、ステップ２０で規定された画像領域を更新する工程がさらに含まれていてもよい。統合の手法としては、たとえば、微小領域と境界を接する隣接画像領域を特定し、接する境界の長さが最も長い隣接画像領域にその微小領域を統合する処理を、より小さい微小領域から順に施す手法や、やはり微小領域と境界を接する隣接画像領域を特定し、該微小領域および全ての隣接画像領域から各々１つの特徴ベクトルを抽出し、特徴ベクトル空間における特徴ベクトル間の距離が最も短い隣接画像領域にその微小領域を統合する処理を、より小さい微小領域から順に施す手法が挙げられる。
【００６９】
なお、上記の実施形態および変更例では、複数の画像領域の中から、構成画素数の多いものを順に複数選択して選択画像領域としたが、選択画像領域の選択の仕方はこれに限られず、特定された複数の画像領域の全てを選択画像領域とする形態等も本発明の範囲に属するものとする。
【００７０】
また、上記の実施形態および変更例では、ＹＣＣ表色系で表された輝度成分および２つの色差成分を成分とする３次元のベクトルを特徴ベクトルとしたが、特徴ベクトルの各成分はこれらに限られず、特徴ベクトルの次元も３に限られない。
【００７１】
さらに、上記の実施形態および変更例では、説明の便宜上、原画像を１０２４×１０２４画素からなる正方形の画像としたが、縦横の画素数が異なる原画像に対しても本発明を適用できることは言うまでもない。各低解像度画像も、正方形画像に限られない。さらに、最低解像度画像の画素数も４画素に限られず、原画像の画素数より少ない複数画素であれば、いかなる画素数であってもよい。
【００７２】
また、上記の実施形態および変更例は、領域分割等の対象である対象画像自体を原画像とし、対象画像の各画素から抽出した特徴ベクトルの分類を目的とするものであったが、対象画像に予め画像縮小処理を施した縮小画像を原画像とし、縮小画像の各画素から抽出した特徴ベクトルの分類を行う形態等も、本発明の範囲に属する。この場合、縮小画像の各画素から抽出した特徴ベクトルの分類を行った後、該縮小画像にあらためて画像拡大処理を施すこと等により、上記の実施形態および変更例と同様、分類結果を対象画像の領域分割処理等に利用することができる。
【００７３】
なお、本発明の上記およびその他の実施形態によるクラスタリング処理は、コンピュータ・プログラムにより実行することもできる。また、上記の説明は、説明の便宜上、方法に関して行ったが、上記の各ステップを行う手段を備えた装置も、本発明の範囲に属するものとする。
【００７４】
以上、本発明の実施形態および変更例について詳細に述べたが、これらは例示的なものに過ぎず、本発明の技術的範囲は、本明細書中の特許請求の範囲のみによって定められるべきものであることは言うまでもない。
【図面の簡単な説明】
【図１】本発明の１つの実施形態であるクラスタリング処理の手順を示したフローチャート
【図２】図１の実施形態における、各低解像度画像の導出方法を示した概念図
【図３】各低解像度画像の導出に使用するガウシアンフィルターの例を示した図
【図４】図１の実施形態における、初期代表ベクトルの導出工程を詳細に示したフローチャート
【図５】図４に示した初期代表ベクトルの導出工程の各段階を示した概念図
【図６】図４に示した初期代表ベクトルの導出工程において、初期代表ベクトルの選択の基準となる最大距離の変化を示した棒グラフ
【図７】図１の実施形態における、現在画像の画像領域への分割手法を示した概念図
【図８】図１の実施形態における、仮クラスター群の特定手法を示した概念図
【図９】図１の実施形態における、仮クラスター群の特定手法を示したフローチャート
【図１０】図１の実施形態における、仮クラスター群の特定手法を示した概念図
【図１１】図１の実施形態の変更例における、仮クラスター群の特定手法を示した概念図
【図１２】図１１の変更例における、仮クラスター群の特定手法を示したフローチャート
【図１】
2004258750.tif 000003
【図２】
2004258750.tif 000004
【図３】
2004258750.tif 000005
【図４】
2004258750.tif 000006
【図５】
2004258750.tif 000007
【図６】
2004258750.tif 000008
【図７】
2004258750.tif 000009
【図８】
2004258750.tif 000010
【図９】
2004258750.tif 000011
【図１０】
2004258750.tif 000012
【図１１】
2004258750.tif 000013
【図１２】
2004258750.tif 000014