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