(57)【特許請求の範囲】
【請求項１】
入力された画像データから、前記画像データ中に含まれるオブジェクト領域を抽出するために画像データをセグメント化する方法において、
素領域分割手段により、前記画像データを素領域に分割し、
素領域抽出手段により、前記分割された素領域から互いに隣接する素領域を抽出し、
素領域記述量導出手段により、前記抽出された各素領域の領域記述量を導出し、
併合後領域記述量導出手段により、前記抽出された各素領域が併合された際の併合後の領域記述量を導出し、
比較手段により、前記抽出された素領域の領域記述量と前記併合後の領域記述量とを比較し、
領域類似度導出手段により、前記各素領域の領域間特徴量の類似度を導出し、
併合判定手段により、前記比較結果および前記領域類似度に基づいて素領域を併合するか否かを判定する、
を有することを特徴とする画像データをセグメント化する方法。
【請求項２】
前記素領域抽出手段は、あらかじめ定めた特定の数の素領域を抽出することを特徴とする請求項１に記載の方法。
【請求項３】
前記素領域抽出手段は、３個以上の素領域を抽出することを特徴とする請求項２に記載の方法。
【請求項４】
前記領域記述量は色情報記述量および境界記述量の少なくとも１つを含むことを特徴とする請求項１−３のいずれか１項に記載の方法。
【請求項５】
前記境界記述量は領域の境界長であることを特徴とする請求項４に記載の方法。
【請求項６】
入力された画像データから、前記画像データ中に含まれるオブジェクト領域を抽出するために画像データをセグメント化する装置において、
前記画像データを素領域に分割する素領域分割手段と、
前記素領域分割手段で分割された素領域から互いに隣接する素領域を抽出する素領域抽出手段と、
前記抽出された各素領域の領域記述量を導出する素領域記述量導出手段と、
前記抽出された各素領域が併合された際の併合後の領域記述量を導出する併合後領域記述量導出手段と、
前記抽出された素領域の領域記述量と前記併合後の領域記述量とを比較する比較手段と、
前記各素領域の領域間特徴量の類似度を導出する領域類似度導出手段と、
前記比較結果および前記領域類似度に基づいて素領域を併合するか否かを判定する併合判定手段と、
を有することを特徴とする画像データをセグメント化する装置。
【請求項７】
前記素領域抽出手段は、あらかじめ定めた特定の数の素領域を抽出することを特徴とする請求項６に記載の装置。
【請求項８】
前記素領域抽出手段は、３個以上の素領域を抽出することを特徴とする請求項７に記載の装置。
【請求項９】
前記領域記述量は色情報記述量および境界記述量の少なくとも１つを含むことを特徴とする請求項６−８のいずれか１項に記載の装置。
【請求項１０】
前記境界記述量は領域の境界長であることを特徴とする請求項９に記載の装置。
【請求項１１】
コンピュータを、
画像データを素領域に分割する素領域分割手段と、
前記素領域分割手段で分割された素領域から互いに隣接する素領域を抽出する素領域抽出手段と、
前記抽出された各素領域の領域記述量を導出する素領域記述量導出手段と、
前記抽出された各素領域が併合された際の併合後の領域記述量を導出する併合後領域記述量導出手段と、
前記抽出された素領域の領域記述量と前記併合後の領域記述量とを比較する比較手段と、
前記各素領域の領域間特徴量の類似度を導出する領域類似度導出手段と、
前記比較結果および前記領域類似度に基づいて素領域を併合するか否かを判定する併合判定手段と、
を有する画像データセグメント化装置として機能させるためのプログラム。
【請求項１２】
前記素領域抽出手段は、あらかじめ定めた特定の数の素領域を抽出することを特徴とする請求項１１に記載のプログラム。
【請求項１３】
前記素領域抽出手段は、３個以上の素領域を抽出することを特徴とする請求項１２に記載のプログラム。
【請求項１４】
前記領域記述量は色情報記述量および境界記述量の少なくとも１つを含むことを特徴とする請求項１１−１３のいずれか１項に記載のプログラム。
【請求項１５】
前記境界記述量は領域の境界長であることを特徴とする請求項１４に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オブジェクトに基づく画像検索で利用するために画像内のカラーリージョンをセグメント化する方法に関する。特に、本発明は多次元画像をカラーリージョンに分割し、カラーおよび境界分析を実行して、多次元画像をセグメント化し、あるいは、多次元画像をカラーリージョンにセグメント化する。
【背景技術】
【０００２】
以下の非特許文献１−５は、本発明に関連するすべての主題に関する有用な背景的情報を提供するものであり、本明細書と一体のものとして参考文献として引用する。
【０００３】
【非特許文献１】J. Shi and J. Malik, "Normalized Cuts and Image Segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), August 2000, pp.888-905
【非特許文献２】W. Y. Ma and B. S. Manjunath, "Edge Flow: A Framework of Boundary Detection and Image Segmentation", Proc. IEEE International Conference on Computer Vision and Pattern Recognition, June 1997, pp.744-49
【非特許文献３】J. Z. Wang et al., "Unsupervised Multiresolution Segmentation of Images with Low Depth of Field", IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.23, No.1, January 2001, pp.85-90
【非特許文献４】K. Hirata, S. Mukherjea, W. S. Li and Y. Hara, "Integrating Image Matching and Classification for Multimedia Retrieval on the Web", IEEE International Conference on Multimedia Computing and Systems, June 1999
【非特許文献５】K. Hirata, S. Mukherjea, W. S. Li, Y. Okamura and Y. Hara, "Facilitating Object-based Navigation Through Multimedia Web Databases", Theory and Practice of Object Systems, Vol.4(4), pp.261-83 (1998)。
【０００４】
次に、本発明を理解するための適当な基礎を提供するために、いくつかの主題について説明する。
【０００５】
画像検索(image retrieval)は、ブロードバンド・インターネットの世界で重要な話題の１つである。コンピュータは、大量のビデオデータおよび写真データを、蓄積された画像データとして記憶している。しかしながら、蓄積画像データは、通常、キーワードがないか又は非常に少数のキーワードとともに記憶されている。さらに、蓄積画像データは通常適切には分類されていない。ほとんどのユーザは、蓄積画像データを分類するのに時間をかけたり、適切なキーワードを蓄積画像データに割り当てたりしようとはしないからである。
【０００６】
多くの場合、ユーザは、蓄積画像に含まれるオブジェクトを、問合せの題目として使用しようとする。例えば、ユーザは、「私の息子がビーチで写っている写真をすべて見出せ」というような問い合わせで、蓄積画像データに含まれるいくつかの画像を検索しようとする。この問合せにおいて、蓄積画像データ内でのオブジェクト（私の息子）の位置およびサイズは重要ではない。海岸での写真で、かつ、ユーザの息子を含むすべての蓄積画像が検索されなければならない。この種の探索は、画像全体の類似度を評価することでは達成されない。システムは、要求されたオブジェクトを画像から抽出し、そのオブジェクトを単位として用いて類似度を評価しなければならない。有効な画像検索のためには、画像セグメント化および属性割当てが、画像マッチングの目的のために設計されなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
セグメント化（セグメンテーション）は、多くの画像処理アプリケーションにおいて最も重要なオペレーションの１つである。数多くの技術が提案されている。Malik et al.は、テクスチャと輪郭の特徴を統合し、正規化カット(normalized cut)アルゴリズムに基づいて画像をリージョンに分割している。W. Y. Ma et al.は、エッジフローに基づいて境界を検出している。Ma et al.は、また、強度／カラーおよびテクスチャの不連続性を統合して画像をセグメント化している。これらのアルゴリズムは、テクスチャ領域および非テクスチャ領域の両方を含む画像から境界を検出するように作用する。しかし、これらのアルゴリズムは、オブジェクトに基づく画像検索のために画像をセグメント化するようには設計されていない。例えば、各領域の形状と位置情報は、画像をセグメント化する際には考慮に入れられているが、索引付け段階では考慮されていない。
【０００８】
画像を分割する際に、J. Wang et al.は、被写界深度を利用して前景と背景とを区別するアルゴリズムを適用している。このアルゴリズムは、明瞭な前景オブジェクトを抽出するためには有効である。しかし、オブジェクトが蓄積画像の前景または背景のいずれに位置するかを判断するのは困難なことが多く、こうした対象に対して適用できない。
【課題を解決するための手段】
【０００９】
本発明は、上記の状況に鑑み、従来技術の上記の課題および限界を克服するためになされたものである。
【００１０】
本発明による画像データをセグメント化する方法は、入力された画像データから、前記画像データ中に含まれるオブジェクト領域を抽出するために画像データをセグメント化する方法であって、素領域分割手段により、前記画像データを素領域に分割し、素領域抽出手段により、前記分割された素領域から互いに隣接する素領域を抽出し、素領域記述量導出手段により、前記抽出された各素領域の領域記述量を導出し、併合後領域記述量導出手段により、前記抽出された各素領域が併合された際の併合後の領域記述量を導出し、比較手段により、前記抽出された素領域の領域記述量と前記併合後の領域記述量とを比較し、領域類似度導出手段により、前記各素領域の領域間特徴量の類似度を導出し、併合判定手段により、前記比較結果および前記領域類似度に基づいて素領域を併合するか否かを判定する、を有することを特徴とする。
【００１１】
本発明による画像データをセグメント化する装置は、入力された画像データから、前記画像データ中に含まれるオブジェクト領域を抽出するために画像データをセグメント化する装置であって、前記画像データを素領域に分割する素領域分割手段と、前記素領域分割手段で分割された素領域から互いに隣接する素領域を抽出する素領域抽出手段と、前記抽出された各素領域の領域記述量を導出する素領域記述量導出手段と、前記抽出された各素領域が併合された際の併合後の領域記述量を導出する併合後領域記述量導出手段と、前記抽出された素領域の領域記述量と前記併合後の領域記述量とを比較する比較手段と、前記各素領域の領域間特徴量の類似度を導出する領域類似度導出手段と、前記比較結果および前記領域類似度に基づいて素領域を併合するか否かを判定する併合判定手段と、を有することを特徴とする。
【００１２】
本発明によるコンピュータプログラムは、コンピュータを、画像データを素領域に分割する素領域分割手段と、前記素領域分割手段で分割された素領域から互いに隣接する素領域を抽出する素領域抽出手段と、前記抽出された各素領域の領域記述量を導出する素領域記述量導出手段と、前記抽出された各素領域が併合された際の併合後の領域記述量を導出する併合後領域記述量導出手段と、前記抽出された素領域の領域記述量と前記併合後の領域記述量とを比較する比較手段と、前記各素領域の領域間特徴量の類似度を導出する領域類似度導出手段と、前記比較結果および前記領域類似度に基づいて素領域を併合するか否かを判定する併合判定手段と、を有する画像データセグメント化装置として機能させることを特徴とする。
【００１５】
添付図面は、本発明のさまざまな側面を例示しており、明細書の記載とともに、本発明のさまざまな側面、利点および原理を説明することに資するものである。
【発明を実施するための最良の形態】
【００１６】
本発明のさまざまな側面について説明する前に、本発明の理解を容易にするとともにさまざまな用語の意味を明らかにするために、従来技術に関していくつかの事項について述べる。
【００１７】
本明細書において、「コンピュータシステム」という用語は、可能な限り最広義の意味を包含し、スタンドアローンプロセッサ、ネットワーク接続されたプロセッサ、メインフレームプロセッサ、および、クライアント／サーバ関係にあるプロセッサを含むが、これらには限定されない。「コンピュータシステム」という用語は、少なくともメモリおよびプロセッサを含むものと理解されるべきである。一般に、メモリは、あるときに、実行可能プログラムコードの少なくとも一部を記憶し、プロセッサは、その実行可能プログラムコードに含まれる１つまたは複数の命令を実行することになる。
【００１８】
理解されるように、「所定のオペレーション」という用語、「コンピュータシステムソフトウェア」という用語、および「実行可能コード」という用語は、本明細書の目的のためには実質的に同じものを意味する。メモリおよびプロセッサが物理的に同じ場所に位置することは、本発明の実施に必要なわけではない。すなわち、プロセッサとメモリは、異なる物理的装置にあることや、地理的に異なる位置にあることさえもあり得ると予想される。
【００１９】
当業者には理解されるように、本明細書において、「媒体」あるいは「コンピュータ可読媒体」は、ディスケット、テープ、コンパクトディスク、集積回路、カートリッジ、通信回線を通じてのリモート伝送、または、コンピュータにより使用可能なその他の同様の媒体（メディア）を含む。例えば、コンピュータシステムソフトウェアを配布するため、サプライヤ（供給者）は、ディスケットを提供することも可能であり、あるいは、衛星伝送を通じて、直接電話回線を通じて、またはインターネットを通じて、何らかの形で所定のオペレーションを実行する命令を送信することも可能である。
【００２０】
コンピュータシステムソフトウェアは、ディスケットに「書き込まれる」ことも、集積回路に「記憶される」ことも、通信回線で「伝送される」ことも可能であるが、理解されるように、本明細書の目的のためには、コンピュータ使用可能媒体は、所定のオペレーションを実行するための命令は「保持される」ということにする。すなわち、「保持する」という用語は、所定のオペレーションを実行するための命令がコンピュータ使用可能媒体と関係する上記およびそれらと同等の方法を包含することを意図している。
【００２１】
したがって、簡単のため、「プログラム製品」という用語は、本明細書では、任意の形式で所定のオペレーションを実行するための命令を保持する、上で定義されるようなコンピュータ使用可能媒体を指示するために使用される。
【００２２】
以下、添付図面を参照して、本発明のさまざまな側面の詳細な説明を行う。
【００２３】
一般的な画像を分割することには様々な手法がある。索引付けアルゴリズムは、画像検索用に設計されなければならない。以下は、オブジェクトに基づく画像検索のための領域分割の要件である。これらの要件は、オブジェクトに基づく画像検索のためのものであるが、他の多くのタイプのアプリケーションにも有効である。
【００２４】
１．１画像内に多数のリージョンを有することを避けること。画像内に含まれるすべてのオブジェクトを抽出し管理するのは困難であり非実際的である。リージョンの総数は大きくすべきではない。いくつかの小さいオブジェクトが１画像内にあるとき、それらの一部は、画像特徴量に基づいてグループ化されるべきである。
【００２５】
２．抽出されたリージョンは単純に記述されること。抽出されたリージョンは検索問合せとして使用されるため、各リージョンの記述は単純であるべきである。例えば、Ｔシャツ上の複雑なロゴマークは、Ｔシャツと一緒に扱われるべきである。他方、単純なロゴマークはそれ自体として抽出されるべきである。
【００２６】
３．テクスチャ領域の抽出。一般的な画像は、テクスチャ領域および非テクスチャ領域を含む。システムは、テクスチャに基づくエッジを、オブジェクト境界領域から区別しなければならない。縞模様のシャツ、彩色された床面、シマウマなどは、１つのリージョン内で抽出されるべきである。
【００２７】
４．分離した領域のグループ化。一般的な画像では、画像内のオブジェクトは互いに重なり合って写っている。このため１つのオブジェクトが複数の領域に分かれていることもある。この際の複数領域に分かれたオブジェクトの各領域は、それ自体ではオブジェクトを表さない。同一オブジェクトの分離した領域は、１つのオブジェクトとして認識されるべきである。
【００２８】
上記の要求を実行するため、本発明は、多次元画像を互いに素(disjoint)なリージョンに分割し、領域の特徴量に基づく画像分析と、領域の輪郭情報に基づく画像分析と統合する。本発明は、テクスチャの係数および位置とともに、色分布に基づいて領域間の距離を定義する。階層的クラスタ分析を適用することによって、視覚的特徴量の観点から均質な領域がリージョンとして抽出される。このプロセスを通じて、本発明は、分離した領域を１つのリージョンとしてグループ化することができる。本発明はまた、テクスチャ領域を１つのリージョンに分割することができる。他方、本発明は、リージョンの境界を輪郭とみなす。本発明は、輪郭の複雑さおよび密度を評価し、それに従ってリージョンをグループ化する。本発明は、オブジェクト間の境界の形状とセグメント化したときの共感記述を含むことができる。好ましくは、本発明は、オブジェクトマッチングに適合するように修正された、ＭＰＥＧ−７標準のビジュアル記述子を使用する。
【００２９】
領域内視覚的特徴量に基づく画像分析と領域の輪郭情報に基づく画像分析は相補的なアプローチである。本発明は、テクスチャのあるリージョンおよびテクスチャのないリージョンを、同じフレームワーク内で処理する。オブジェクトの境界を、網目等のテクスチャに基づくエッジから区別するため、本発明は、カラーリージョンの全記述長を評価する。これはまた、カラーリージョンの記述を単純に保つためにも有効である。例えば、複雑なロゴマークは、この種の分析アプローチによって、Ｔシャツとグループ化することができる。
【００３０】
本発明は、リージョンデータ値を各リージョンに割り当てる。リージョンデータ値は、キーワード、タグ、識別子名などであることが可能である。例えば、地下鉄の駅の多次元画像は、地下鉄車両に対応するいくつかのリージョンを有し、それらのリージョンには「電車」というキーワードが割り当てられることが可能である。本発明はまた、リージョンデータ値として、視覚的特徴量インジケータをリージョンに割り当てることも可能である。視覚的特徴量は、主に、ＭＰＥＧ−７標準から選択されている。カラーリージョンはさまざまなシェイプおよびサイズを有するため、視覚的特徴量の一部は任意のシェイプおよびサイズに適合するように修正される。
【００３１】
ドミナントカラー記述子（ＤＣＤ：Dominant Color Descriptor）は、ＭＰＥＧ−７  ＸＭ８．０標準に記載されている。好ましくは、１つのリージョン内のカラー数はたかだか２である。というのは、セグメント化されたリージョンはカラー特徴に関する性質を示すためである。好ましくは、本発明は、１個または２個のドミナントカラーと、各リージョンごとのそれらの割合とを使用する。本発明は１リージョン内でたかだか２個のカラーしか使用しないため、本発明は、カラーリージョン間の距離を計算するために、ＭＰＥＧ−７  ＸＭ８．０に記載されている基準とは異なる基準を使用する。リージョンＲ1（ドミナントカラー１：カラーｃ１１，面積比ｐ１１，ドミナントカラー２：カラーｃ１２，面積比ｐ１２（＝１−ｐ１１））とリージョンＲ2（ドミナントカラー１：カラーｃ２１，面積比ｐ２１，ドミナントカラー２：カラーｃ２２，面積比ｐ２２（＝１−ｐ２１））の間の距離ＤＣＤ（Ｒ1，Ｒ2）は式（１）によって定義される。
DCD(R1,R2)=min[c_d(c11,c12,c21,c22,p11,p12,p21,p22),
c_d(c11,c12,c22,c21,p11,p12,p22,p21)]      式（１）
式（１）において、関数c_d()は、次のように式（２）によって定義される。
c_d(a1,a2,a3,a4,p1,p2,p3,p4)=
d(a1,a3)*min(p1,p3)+d(a2,a4)*min(p2,p4)+
d(a2,a3)*max(0,p3-p1)+d(a1,a4)*max(0,p1-p3)          式（２）
式（２）において、関数ｄ（ｃｎ，ｃｍ）は、ＣＩＥ  Ｌｕｖ色空間上のカラーｃｎとカラーｃｍの間の色距離として定義される。図１に、ドミナントカラーに基づく距離の定義を示す。
【００３２】
カラーレイアウト記述子（ＣＬＤ：Color Layout Descriptor）は、ＭＰＥＧ−７  ＸＭ８．０標準に記載されている。カラーリージョンの任意のシェイプに適用するため、本発明はまず、カラーリージョンの平均を計算する。カラーリージョンの境界ボックスが正方形となるように拡張され、非リージョン領域は平均カラーで充填される。充填プロセスの後、本発明は、カラーレイアウト記述子を抽出する。本発明は、類似度ＣＬＤ（Ｒ1，Ｒ2）を計算するために、係数のＬ２ノルムを適用する。ただし、Ｌ２ノルムは２乗に基づく距離である。
【００３３】
形状記述子(Shape Descriptor)について、本発明は、ピクセルの正方形ブロックとなるように、カラーリージョンの境界ボックスを拡張する。本発明は、画像を８×８ピクセルブロックに分割し、ピクセルブロック内の有効なピクセルの数をカウントする。次に、本発明は、１６次元の特徴ベクトル（すなわち、すべての行および列についての（有効ピクセル数）／（全ピクセル数））を得るために、各行および各列についてすべてのピクセルをカウントする。特徴ベクトルの値は、［０〜２５５］に正規化される。類似度距離を計算するため、本発明は、各値のＬ１ノルムを適用する。ただし、Ｌ１ノルムは絶対値に基づく距離である。
【００３４】
エッジヒストグラム記述子(Edge Histogram Descriptor)は、ＭＰＥＧ−７  ＸＭ７．０標準に記載されている。本発明は、ＭＰＥＧ−７  ＸＭ７．０標準に記載されている方法に基づいてエッジヒストグラム値を計算する。本発明は、カラーリージョンの任意のシェイプに適合するように、アルゴリズムを修正する。図２Ａ〜図２Ｆに、エッジヒストグラムを抽出するアルゴリズムの結果を例示する。まず、アルゴリズムは、入力画像からサイズが８×８ピクセルのピクセルブロックを抽出する。次に、アルゴリズムは、５個のエッジ強度、すなわち、es_vertical、es_horizontal、es_diagonal45、es_diagonal135およびes_nondirectionを計算する。アルゴリズムは次に、式（３）を用いてエッジヒストグラムを評価する。
max(es_vertical,es_horizontal,es_diagonal45,
es_diagonal135,es_nondirection) > Th                式（３）
式（３）が真と評価される場合、エッジの方向がカウントされる。換言すれば、特定のエッジ上のピクセルの総数がカウントされる。式（３）が真と評価されない場合、このピクセルブロックはエッジを有しておらず、カウントされるべきではない。５次元エッジヒストグラムを抽出するために、すべてのピクセルブロックに対するエッジ強度およびエッジヒストグラムが計算される。類似度距離を計算するため、本発明は、各ビンのＬ１ノルムの和を使用する。
【００３５】
通常、テクスチャは、テクスチャ安定な領域を用いて評価されるべきである。というのは、カラーリージョンの境界付近は周辺の領域の影響を受け、カラーリージョンの内部とは異なるタイプのテクスチャを有するからである。テクスチャ係数（例えば、ウェーブレット係数）を計算する際には、境界付近の特徴の効果が通常含められる。カラーリージョン内部のテクスチャを評価するため、システムは、境界領域の効果を除去しなければならない。テクスチャ係数を計算する際に境界からｎピクセル深度のピクセルを使用することは、境界の効果を低減する１つの方法である。ウェーブレット係数を計算するため、本発明は、蓄積画像にＮレベルウェーブレット変換を適用して、各ピクセルごとに３×Ｎ個の係数を得る。境界効果を低減するため、本発明は、エッジ部分を使用しない（すなわち、＋４ピクセル深度より下）。最後に、本発明は、ベクトルのＬ２ノルムを用いて、類似度距離を計算する。
【００３６】
図３には、本発明が要約して記載されている。Ｓ３００で、リージョン抽出が入力画像に対して実行される。一般に、画像は、ＲＧＢ（赤青緑）強度値マトリクスとして入力されるが、他のタイプの入力マトリクスも同様に使用可能である。リージョン抽出は、カラー値に基づく。Ｓ３１０で、入力画像の境界分析に基づく併合作用が実行される。併合作用は、境界線の形状分析に基づく。Ｓ３２０で、階層的クラスタ分析によりリージョンの併合を行う。階層的クラスタ分析によるリージョンの併合の後、Ｓ３３０で、入力画像は、境界分析に基づく別のリージョン併合処理を受ける。この境界分析では、境界線の複雑度、密度および領域記述長が分析される。次に、Ｓ３４０で、入力画像内の小孤立領域が併合される。この併合作用は、より大きいカラーリージョンに対する小リージョンの関係に基づく。最後に、Ｓ３５０で、視覚的特徴量（例えば、ドミナントカラー、カラーレイアウト、ウェーブレット、エッジヒストグラム、シェイプ）が計算され、入力画像の各リージョンごとに割り当てられる。
【００３７】
次に、本発明についてさらに詳細に説明する。好ましくは、本発明は、ＲＧＢ強度値マトリクスとして入力されるフルカラー原画像を含む画像を処理する。ＹＩＱ、ＣＭＹ（シアン・マゼンタ・黄）、衛星画像、グレイスケール画像あるいはその他の多次元画像も、色距離を適当に定義することによって、同様に使用可能である。例えば、グレイスケール画像の場合、本発明は、色距離を評価するために、明度差を評価する。
【００３８】
図４において、本発明は、原入力画像からカラーリージョンを抽出する。原入力画像から、本発明は、領域成長法を適用することによって、カラーリージョンのセットＺ1を抽出する。まず、メジアンフィルタを適用して、ピクセルのスパイクノイズの効果を低減する。好ましくは、本発明は、２×２メジアンフィルタを適用する。本発明は、原入力画像に比べて半分のサイズの画像を処理する。次に、カラー値が粗量子化される。カラー値の量子化は、画像のカラー品質を実質的に劣化させることのない階調数にて実行される。カラー値量子化の後、領域成長法を適用することによって、カラーリージョンが抽出される。まず、量子化されたカラー値に基づいて、同一又は非常に類似した画素値をもつ隣接ピクセルがリージョンにグループ化される。一般に、このグループ化により、過度にセグメント化されたリージョンが生成される。カラーリージョンが非常に小さいリージョンである場合、近傍リージョンとの色距離を計算し、その色距離がしきい値より小さい場合、その非常に小さいリージョンを最も近い色距離のリージョンに併合する。色距離を決定しリージョンのサイズを判定するためのしきい値は、あらかじめ規定される。それらのしきい値は、画像全体のリージョンサイズの分布および色分布に基づいて導出することも可能である。例えば、色分析のちらばりを平均と標準偏差で表した場合、平均から３シグマが、小さいと判定される（シグマは、標準偏差である）。
【００３９】
図５を参照すると、カラーリージョンの抽出後、カラーリージョンは境界分析に基づいて併合される。隣接するすべての可能なリージョン対の境界の複雑さが計算され、リージョン対の境界が十分に複雑であり、かつ、これらのリージョン間の色距離がしきい値より小さい場合、それらは１リージョンに併合される。
【００４０】
まず、Thresholdcolor が計算される。これは、入力画像内のカラーの分布を評価することによる色距離のしきい値である。例えば、本発明は、近傍リージョンのすべての色距離を評価し、色距離の平均および標準偏差を計算する。本発明は、平均から２シグマの値を抽出することによって、しきい値を決定する。これを行うことにより、本発明は、カラーの分布に基づいてしきい値を指定することができる。これにより類似のカラーを含む画像については、より小さい値がしきい値として用いられる。多様なカラーを含む画像については、より大きい値がしきい値に用いられる。次に、前にカラーリージョンの抽出中に生成されたセグメント化マトリクスＺ1から境界線が抽出される。境界線は、カラーリージョンのエッジをたどることによって指定される。境界線が抽出された後、すべての可能なＲ1，Ｒ2∈Ｚ1についてComplexity(R1, R2)が計算される。図６Ａ〜図６Ｃは、本発明によって考慮されるComplexity()の定義を示す。境界がいくつもの曲線部分を有するとき、複雑さの程度は高い。境界が単純（例えば、直線）であるとき、複雑さの程度は低い。本発明はComplexity(R1, R2)を計算するが、これは、カラーリージョンＲ1とカラーリージョンＲ2の間の複雑さを表すとともに、他方のリージョンへの連結性に基づいている。Complexity(R1, R2)の計算は、式（４）に示される。
Complexity(R1,R2)=[Complexity(R1→R2)+Complexity(R2→R1)]/2    式（４）
式（４）において、関数Complexity(R1→R2)はさらに式（５）によって定義される。
Complexity(R1→R2)
=BoundaryRnumber(R1→R2)/BoundaryNumber(R1→R2)         式（５）
式（５）において、関数BoundaryNumber(R1→R2)は、カラーリージョンＲ2に接するカラーリージョンＲ1の境界ピクセルの数である。式（５）において、関数BoundaryRnumber(R1→R2)は、カラーリージョンＲ1の境界ピクセルのRPB(R1→R2)の数の和である。関数RPB(R1→R2)は、各境界上で、カラーリージョンＲ1に隣接するカラーリージョンＲ2のピクセルの数である。
【００４１】
図６Ａ〜図６Ｃは、RPB(R1→R2)の定義を示す。図６Ａ〜図６Ｃに示されているように、RPB(R1→R2)は、境界がすべて図６Ａに示されるように直線であるときのみ、境界ピクセルの数に等しい。RPB(R1→R2)は、図６Ｂや図６Ｃでは境界ピクセルの数より大きい。このＲＰＢ値に基づいて、Complexity(R1, R2)が計算される。関数Complexity(R1, R2)は、境界が複雑であるときには大きい値を返す。複雑な境界は、図７Ａに例示されている。関数Complexity(R1, R2)は、境界が単純であるときには小さい値を返す。単純な境界は、図７Ｂに例示されている。
【００４２】
次に、カラーリージョンＲ1とカラーリージョンＲ2は、式（６）が真と評価される場合に併合される。そうでない場合、これらのカラーリージョンは併合されない。
Complexity(R1,R2) > Thresholdcomplex かつ
Distancecolor(R1,R2) < Thresholdcolor                    式（６）
一般に、Thresholdcomplexの値は１と４の間にある。しかし、Thresholdcomplexの値は、平均値および標準偏差に基づいて定義することも可能である。カラー値が徐々に変化するカラーリージョンは通常、シャープな境界をもたない。複雑度を用いた処理によりカラーリージョンの併合は、擬似境界により生成された領域を併合し、新たなセグメント化マトリクスＺ2を生成する。
【００４３】
図８において、本発明は、階層的クラスタ分析に基づいてカラーリージョンを併合する。カラーリージョンが併合されるかどうかを判定するためのしきい値は、カラーリージョン間の特徴量距離の分布に基づいて計算される。本発明は、まず階層的クラスタ分析最小距離法を使用した後、階層的クラスタ分析最長距離法を適用する。「階層的クラスタ分析最小距離法」および「階層的クラスタ分析最長距離法」は、データを分類するための公知の方法である。これらの方法を実行するため、システムは、すべてのリージョン対の距離を計算し、カテゴリの数まで、または、すべてのリージョン間距離がしきい値より小さくなるまで、最近対からリージョンを併合する。相違点は、新たに生成されるリージョンと他のリージョンとの間の新たな距離をどのように定義するかである。この方法では、分離したリージョンを１リージョンとして併合することが可能である。システムは、すべての可能なリージョン対の特徴量距離を計算し、リージョン併合を実行する。旧セグメント化マトリクスＺ2から、新たなセグメント化マトリクスＺ3が生成される。新たなセグメント化マトリクスＺ3におけるカラーリージョンの一部は、３個以上のセグメント化領域を有することも可能である。
【００４４】
まず、すべてのカラーリージョンＲ1，Ｒ2∈Ｚ2についてDistanceregion(R1,R2)が計算される。式（７）で、カラーリージョンの位置、カラー値およびテクスチャ値が評価される。
Distanceregion(R1,R2) 
=α・Distancelocation(R1,R2) + β・Distancecolor(R1,R2) +
γ・Distancetexture(R1,R2)                                  式（７）
アルファ（α）、ベータ（β）およびガンマ（γ）は統合のために用いられる。これらの値は、前もって指定されることも可能であり、あるいは、これらの値は、Distancelocation(R1,R2)、Distancecolor(R1,R2)およびDistancetexture(R1,R2)の分布の比較に基づいて指定されてもよい。式（８）はさらに、式（７）で用いられるDistancelocation(R1,R2)の一例を定義する。
Distancelocation(R1,R2)=((YR2/Ymax-YR1/Ymax)2+(XR2/Xmax-XR1/Xmax)2)0.5     式（８）
式（８）において、値（ＸR1，ＹR1）は、カラーリージョンＲ1の重心と定義され、値（ＸR2，ＹR2）は、カラーリージョンＲ2の重心と定義される。値（Ｘmax，Ｙmax）は、画像のサイズと定義される。Distancecolor(R1,R2)は、Ｌｕｖ色空間に基づくカラーリージョンのカラー値の距離と定義される。Distancetexture(R1,R2)は、ウェーブレット係数に基づくベクトルのＬ２ノルムと定義される。６次元特徴ベクトルが使用され、ＤＣ部分は使用されない。有効ピクセル一致係数の平均および標準偏差も同様に使用される。前述のように、本発明は、境界効果を避けるため、＋ｎピクセルの深度のエッジ部分をマスクする。
【００４５】
次に、リージョン併合のしきい値Threshold_NNregionが計算され、この計算は、Distanceregionの分布に基づく。本発明は、すべてのDistanceregionを計算し、Distanceregionの平均および標準偏差を計算する。例えば、Threshold_NNregion値は、平均から２シグマとすることが可能である。
【００４６】
次に、式（７）を用いてすべてのカラーリージョン対のリージョン特徴距離を計算する。本発明は、計算されたリージョン特徴距離に基づいて最小距離法を実行する。その後、本発明は、すべてのカラーリージョン対のリージョン特徴距離がThreshold_NNregionより小さくなるまで、Ｚ2のカラーリージョンを併合する。この新たなマトリクスをＺ2-1で表す。本発明は、式（７）を用いてＺ2-1のすべてのカラーリージョン対のリージョン特徴距離に基づいて、新たなしきい値Threshold_FNregionを計算する。例えば、このしきい値は、平均から約１．５シグマとすることが可能である。本発明は、計算された距離に基づいて最長距離法を実行する。その後、本発明は、すべてのカラー対の距離が値Threshold_FNregionより小さくなるまでカラーリージョンＺ2-1を併合する。この新たなマトリクスをＺ3で表す。
【００４７】
図９〜図１１において、本発明は、境界分析に基づいてセグメント化マトリクスＺ3に対してリージョン併合を実行する。まず、すべてのカラーリージョンＲ1，Ｒ2∈Ｚ3についてDistanceregion(R1,R2)が計算され、カラーリージョンを併合するためのしきい値Thresholdregionも同様に計算される。次に、本発明は、すべての可能なカラーリージョンＲ1，Ｒ2∈Ｚ3についてComplexity(R1,R2)を計算した後、しきい値Thresholdregionを用いてカラーリージョンを併合する。こうして、新たなセグメント化マトリクスＺ4-1が生成される。
【００４８】
次に、本発明は、すべての調整リージョンR1, R2, R3, R4∈Ｚ4-1について境界記述低減比(boundary description reduction ratio) BDRR(R1,R2,R3,R4)およびカラー記述低減比(color description reduction ratio) CDRR(R1,R2,R3,R4)を計算する。式（９）は、境界記述低減比の計算を示す。
BDRR(R1,R2,R3,R4)
=DLB(R1+R2+R3+R4)/(DLB(R1)+DLB(R2)+DLB(R3)+DLB(R4))    式（９）
式（１０）は、カラー記述低減比の計算を示す。
CDRR(R1,R2,R3,R4)
=CDL(R1+R2+R3+R4)/(CDL(R1)+CDL(R2)+CDL(R3)+CDL(R4))    式（１０）
ＤＬＢは、境界の記述長を表す。現在のところ、本発明は、全境界長を使用する。ＣＤＬは、カラー記述長を表す。本発明は、リージョン内のカラーの分布を使用する。
【００４９】
次に、本発明は、式（１１）が真と評価され、かつ、リージョン特徴距離がThresholdregionより小さい場合に、連続するカラーリージョンＲ1，Ｒ2，Ｒ3，Ｒ4を１リージョンに併合する。
BDRR(R1,R2,R3,R4)+α・CDRR(R1,R2,R3,R4) < ThresholdDESCRIPTION    式（１１）
Thresholdregionは、あらかじめ定義されることが可能であり、あるいは、Distanceregionの分布から計算されることも可能であり、あるいは、前もって指定されることも可能である。連続するカラーリージョンとは、少なくとも他の１つの領域と互いに隣接するリージョンという。たとえば、カラーリージョンＡ、Ｂ、Ｃ、Ｄがあったとき、カラーリージョンＡがカラーリージョンＢ、ＣまたはＤの少なくともいずれか１つの領域と隣接し、同様に、カラーリージョンＢもＡ、ＣまたはＤの少なくとも１つのカラーリージョンと隣接し、カラーリージョンＣがＡ、ＢまたはＤの少なくとも１つと隣接し、カラーリージョンＤがＡ、ＢまたはＣの少なくとも１つと隣接することをいう。すなわち、いずれのカラーリージョンも、他のカラーリージョンのうちの１つのカラーリージョンと隣接しなければならない。カラーリージョンのこの併合の結果として新たなセグメント化マトリクスＺ4-2が生成される。
【００５０】
次に、本発明は、すべての調整リージョンＲ1，Ｒ2，Ｒ3∈Ｚ4-2について境界記述低減比BDRR(R1,R2,R3)およびカラー記述低減比CDRR(R1,R2,R3)を計算する。式（１２）は、この境界記述低減比の計算を示す。
BDRR(R1,R2,R3)=DLB(R1+R2+R3)/(DLB(R1)+DLB(R2)+DLB(R3))    式（１２）
式（１３）は、このカラー記述低減比の計算を示す。
CDRR(R1,R2,R3)=CDL(R1+R2+R3)/(CDL(R1)+CDL(R2)+CDL(R3))   式（１３）
ＤＬＢは、境界の記述長を表す。現在のところ、本発明は、全境界長を使用する。ＣＤＬは、カラー記述長を表す。本発明は、リージョン内のカラーの分布を使用する。
【００５１】
次に、本発明は、式（１４）が真と評価され、かつ、リージョン特徴距離がThresholdregionより小さい場合に、カラーリージョンＲ1，Ｒ2，Ｒ3を１リージョンに併合する。
BDRR(R1,R2,R3)+α・CDRR(R1,R2,R3) < ThresholdDESCRIPTION    式（１４）
カラーリージョンのこの併合の結果として新たなセグメント化マトリクスＺ4-3が生成される。
【００５２】
次に、本発明は、すべての調整リージョンＲ1，Ｒ2∈Ｚ4-3について境界記述低減比BDRR(R1,R2)およびカラー記述低減比CDRR(R1,R2)を計算する。式（１５）は、この境界記述低減比の計算を示す。
BDRR(R1,R2)=DLB(R1+R2)/(DLB(R1)+DLB(R2))          式（１５）
式（１６）は、このカラー記述低減比の計算を示す。
CDRR(R1,R2)=CDL(R1+R2)/(CDL(R1)+CDL(R2))          式（１６）
ＤＬＢは、境界の記述長を表す。現在のところ、本発明は、全境界長を使用する。ＣＤＬは、カラー記述長を表す。本発明は、リージョン内のカラーの分布を使用する。
【００５３】
次に、本発明は、式（１７）が真と評価され、かつ、リージョン特徴距離がThresholdregionより小さい場合に、カラーリージョンＲ1，Ｒ2を１リージョンに併合する。
BDRR(R1,R2)+α・CDRR(R1,R2) < ThresholdDESCRIPTION    式（１７）
カラーリージョンのこの併合の結果として新たなセグメント化マトリクスＺ4-4が生成される。カラーリージョン併合により、本発明は、図１２に示すようにテクスチャ領域を１リージョンに併合する。次に、本発明は、すべてのカラーリージョンＲ1，Ｒ2∈Ｚ4-4についてDistanceregion(R1,R2)を計算するとともに、カラーリージョンを併合するためのしきい値Thresholdregionを決定する。
【００５４】
式（１８）において、本発明は、すべての可能なカラーリージョンＲ1，Ｒ2∈Ｚ4-4について密度比ＤｅｎｓｉｔｙＲａｔｉｏ（Ｒ1，Ｒ2）を計算する。
【００５５】
DensityRatio(R1,R2)=(DensityRatio(R1→R2)+DensityRatio(R2→R1))/2  式（１８）
関数DensityRatio(R1→R2)はさらに式（１９）によって定義される。
DensityRatio(R1→R2)=
HighdenseBnumber(R1→R2)/BoundaryNumber(R1→R2)      式（１９）
式（１９）において、関数BoundaryNumber(R1→R2)は、カラーリージョンＲ2に接するカラーリージョンＲ1の境界ピクセルの数と定義される。関数HighdenseBnumber(R1→R2)は、カラーリージョンＲ2に接するカラーリージョンＲ1の高密度境界ピクセルの数と定義される。図１３Ａ〜図１３Ｂに示すように、高密度境界ピクセルは、そのピクセルを包囲する局所ウィンドウ内の境界ピクセルの総数がしきい値より大きいような境界ピクセルである。
【００５６】
次に、本発明は、式（２０）および式（２１）が真と評価される場合に、カラーリージョンＲ1，Ｒ2∈Ｚ4-4を併合する。
DensityRatio(R1,R2) > Thresholddensity              式（２０）
Distanceregion(R1,R2) < Thresholdregion              式（２１）
Thresholddensityは、境界密度の分布を計算することによって指定されることも可能であり、あるいは、前もって指定されることも可能である。DensityRatioは、２つの指定されたリージョン間の境界領域がどのくらい混雑しているかを評価する。境界が混雑した領域に存在する境界線は、あまり重要でない傾向がある。本発明は、評価される境界ピクセルの周りの境界ピクセル数を計算することによって、境界混雑領域にある境界ピクセルを判定する。Ｒ1とＲ2の間の境界は、Ｒ1とＲ2の間のすべての境界ピクセルから、境界混雑領域内の境界ピクセルのピクセル数と、境界混雑領域内の境界ピクセルの割合とを決定するために評価される。併合されるカラーリージョンは、新たなセグメント化マトリクスＺ4-5を生成する。
【００５７】
次に、本発明は、式（１５）および式（１６）に基づいて、すべての調整リージョンＲ1，Ｒ2∈Ｚ4-5について境界記述低減比ＢＤＲＲ（Ｒ1，Ｒ2）およびカラー記述低減比ＣＤＲＲ（Ｒ1，Ｒ2）を計算する。カラー記述低減比ＣＤＲＲ（Ｒ1，Ｒ2）の計算は式（１６）に基づく。この場合も、ＤＬＢは、境界の記述長を表す。現在のところ、本発明は、全境界長を使用する。ＣＤＬは、カラー記述長を表す。本発明は、リージョン内のカラーの分布を使用する。次に、本発明は、式（１７）が真と評価され、かつ、リージョン特徴距離がThresholdregionより小さい場合に、カラーリージョンＲ1，Ｒ2を１リージョンに併合し、カラーリージョンのこの併合の結果として新たなセグメント化マトリクスＺ4-6が生成される。
【００５８】
図１４Ａ〜図１４Ｂに、小さい孤立カラーリージョンが例示されている。これらの小さいカラーリージョンは、１つのカラーリージョンによって包囲されており、包囲しているカラーリージョンに併合される。これにより、セグメント化マトリクスＺ5が生成され、これは、オブジェクト問合せに使用されることが可能である。
【００５９】
本発明のもう１つの実施例では、多次元画像をセグメント化するコンピュータソフトウェア製品が提供される。このコンピュータソフトウェア製品は、コンピュータシステムが所定のオペレーションを実行することを可能にするソフトウェア命令を含む。コンピュータシステムは、単純なＰＣ互換システム、コンピュータネットワーク、あるいはマルチノード分散システムであることが可能である。コンピュータ可読媒体が、ソフトウェア命令を保持する。コンピュータシステムは、コンピュータ可読媒体上に記憶されたソフトウェア命令を格納することができるメモリも有する。コンピュータ可読媒体上に保持される所定のオペレーションは、前段落までに記載された本発明を実現化する。所定のオペレーションは、コンピュータシステムに入力される多次元画像からカラーリージョンを抽出することと、すべてのカラーリージョン対の境界の複雑さを計算することとを含む。次に、所定のオペレーションは、カラーリージョン対の境界複雑さの値が所定の境界複雑さしきい値より大きく、かつ、リージョン対の色距離が所定の距離しきい値より小さい場合に、リージョン対を併合する。次に、所定のオペレーションは、階層的クラスタ分析を用いてカラーリージョンを併合するようにコンピュータシステムを動作させ、カラーリージョンはさらに、コンピュータシステムによって、上で説明したように、境界分析を用いて併合される。所定のオペレーションは、カラーリージョンが小さく、かつ、別のカラーリージョンによって包囲されているかどうかを判定するようにコンピュータシステムを動作させる。その判定が真である場合、所定のオペレーションは、小さいカラーリージョンを、包囲しているカラーリージョンに併合するようにコンピュータシステムを動作させる。最後に、上で説明したように、リージョンデータが、各カラーリージョンに割り当てられる。
【００６０】
本発明のさまざまな側面についての以上の記載は、例示および説明の目的で提示されている。さまざまな変更および変形が、以上の記載に鑑みて可能であり、また、本発明の実施からも得られる可能性がある。当業者が本発明をさまざまな実施例において利用することができるように、考えられる個々の利用法に適したさまざまな変更例とともに説明するために、本発明の原理とその実際的適用について記載した。このため、ここには、本発明のいくつかの側面についてしか具体的に記載されていないが、明らかなように、本発明の技術的範囲を離れることなく、本発明にさまざまの変形を行うことが可能である。さらに、頭字語は、単に明細書の読みやすさを高めるためにのみ使用されているのであって、用語の一般性を狭めることは意図されておらず、特許請求の範囲をここに記載された実施例に制限するように解釈されてはならない。
【図面の簡単な説明】
【００６１】
【図１】２つのカラーリージョン間の色距離に対するドミナントカラー記述子を示す図である。
【図２】エッジヒストグラム抽出プロセスと、エッジヒストグラム抽出に用いられるフィルタを示す図である。
【図３】本発明の例示的なプロセスフローを示す図である。
【図４】入力画像からのカラーリージョンの抽出のための例示的なプロセスフローを示す図である。
【図５】抽出されたカラーリージョンの境界分析に基づいてカラーリージョン併合を実行するための例示的なプロセスフローを示す図である。
【図６】２つの隣接するカラーリージョンに対するさまざまな複雑さの値を示す図である。
【図７】単純および複雑な境界を示す図である。
【図８】階層的分析に基づくカラーリージョン成長のための例示的なプロセスフローを示す図である。
【図９】カラーリージョンの境界分析に基づいてカラーリージョン併合を実行するための例示的なプロセスフローを示す図である。
【図１０】カラーリージョンの境界分析に基づいてカラーリージョン併合を実行するための例示的なプロセスフローを示す図である。
【図１１】カラーリージョンの境界分析に基づいてカラーリージョン併合を実行するための例示的なプロセスフローを示す図である。
【図１２】カラーリージョンの境界分析に基づくカラーリージョン併合の効果を示す図である
【図１３】境界密度分析後の画像内の境界の簡約を例示する図である。
【図１４】画像からの孤立小領域の簡約を例示する図である。
【図１】
0004539668.tif 000002
【図２】
0004539668.tif 000003
【図３】
0004539668.tif 000004
【図４】
0004539668.tif 000005
【図５】
0004539668.tif 000006
【図６】
0004539668.tif 000007
【図７】
0004539668.tif 000008
【図８】
0004539668.tif 000009
【図９】
0004539668.tif 000010
【図１０】
0004539668.tif 000011
【図１１】
0004539668.tif 000012
【図１２】
0004539668.tif 000013
【図１３】
0004539668.tif 000014
【図１４】
0004539668.tif 000015