(57)【特許請求の範囲】
【請求項１】
オブジェクトを複数の多角形からなる多角形メッシュとして扱い画像処理を行なう画像処理装置であって、
多角形メッシュを記述する隣接グラフを入力する隣接グラフ入力部と、
エッジで結ばれる各画像領域が持つ属性値を比較して比較結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングする隣接グラフ評価部と、
ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、画像領域同士を統計的処理アルゴリズムに基づいて統合すべきか否かを評価し、画像領域の統合処理を行なう画像領域統合処理部と、
を具備することを特徴とする画像処理装置。
【請求項２】
画像領域の統合処理をした結果として残された微細な領域を処理する微小領域処理部をさらに備える、
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記隣接グラフ入力部は、多角形メッシュを構成する個々の多角形をノードとして扱い、隣接する多角形同士が接する辺に相当するエッジを用いて対応するノード間を結んで記述される隣接グラフを入力する、
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記隣接グラフ評価部は、隣接グラフのエッジで結ばれる各画像領域が持つ属性値の相違をエッジの重み値として与えて、重み値の小さい順にソーティングを行なう、
ことを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記隣接グラフ評価部は、画像領域が持つ属性値として、画像領域の面積（画像領域に含まれる多角形メッシュの平均面積）、法線方向、又は色（画像領域内のＲＧＢのうち少なくとも１成分についての平均色）若しくはその他の画素属性情報を用いる、
ことを特徴とする請求項４に記載の画像処理装置。
【請求項６】
前記画像領域統合処理部は、画像領域を構成する多角形の面積における集中不均衡現象から導き出される判断式に基づいて、隣接グラフのエッジで結ばれる画像領域同士を統合すべきかどうかを判断する、
ことを特徴とする請求項１に記載の画像処理装置。
【請求項７】
前記画像領域統合処理部は、隣接グラフのエッジで結ばれる２つの画像領域Ｒk及びＲlに関して以下の統計的アルゴリズムに基づく判断式を満たすときに、画像領域Ｒk及びＲlを統合すべきと判定する（但し、画像領域Ｒkは面積Ｓkを持つとともにｎk個の多角形で構成され、画像領域Ｒlは面積Ｓlを持つとともにｎl個の多角形で構成されるとし、Ａは多角形の最大面積とし、Ｑはセグメンテーションの粗さを制御するためのパラメータとする）、
ことを特徴とする請求項１に記載の画像処理装置。
【数１】
0004780106.tif 000014
【請求項８】
前記判断式中のパラメータＱを設定するパラメータ設定手段をさらに備える、
ことを特徴とする請求項７に記載の画像処理装置。
【請求項９】
所望のセグメンテーションの粗さが得られるようなパラメータＱの値を前記パラメータ設定手段に与えるセグメンテーション粗さ制御手段をさらに備える、
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１０】
前記セグメンテーション粗さ制御手段は、所望するセグメンテーションの粗さが外部から与えられたときに、当該粗さに相当するパラメータＱの値に変換して前記パラメータ設定手段に与える、
ことを特徴とする請求項９に記載の画像処理装置。
【請求項１１】
隣接グラフの各ノードは対応する画像領域の面積及び多角形の個数に関するノード統計情報を保持するノード統計情報保持部をさらに備え、
前記画像領域統合処理部は、画像領域の統合を実行したときには、統合して新たに生成された画像領域の面積及び多角形の個数を算出して前記ノード統計情報の更新処理を行なう、
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１２】
前記隣接グラフ評価部は、統合処理された画像領域とその隣接画像領域を結ぶエッジの重み因子を更新されたノード統計情報に基づいて再計算して、重み値に基づいて隣接グラフ中のエッジを再ソーティングし、
前記画像領域統合処理部は、前記統計的処理アルゴリズムに基づいて統合すべき画像領域のペアがなくなるまで画像領域の統合とノード統計情報の更新を繰り返し行なう、
ことを特徴とする請求項１１に記載の画像処理装置。
【請求項１３】
前記画像領域統合処理部は、画像領域の統合を行なったときに、新たに生成された画像領域の境界近辺の多角形からなるクラストのみを残して、画像領域の面積及び多角形の個数を算出して前記ノード統計部の更新処理を行ない、クラストを用いて以降の画像領域の統合についての成否判断を行なう、
ことを特徴とする請求項１１に記載の画像処理装置。
【請求項１４】
前記画像領域統合処理部は、統合して新たに生成された画像領域の全周に渡る境界近辺の多角形をクラストとして残す、
ことを特徴とする請求項１３に記載の画像処理装置。
【請求項１５】
前記画像領域統合処理部は、統合しようとする各画像領域が接する境界近辺の多角形をクラストとして残し、
該統合処理を行なったときに、前記隣接グラフ評価部は隣接グラフの再評価を行なう、
ことを特徴とする請求項１３に記載の画像処理装置。
【請求項１６】
オブジェクトを複数の多角形からなる多角形メッシュとして扱い画像処理を行なうための処理をコンピュータ上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、前記コンピュータに対し、
多角形メッシュを記述する隣接グラフを入力する隣接グラフ入力手順と、
エッジで結ばれる各画像領域が持つ属性値を比較して比較結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングする隣接グラフ評価手順と、
ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、画像領域同士を統計的処理アルゴリズムに基づいて統合すべきか否かを評価し、画像領域の統合処理を行なう画像領域統合処理手順と、
を実行させることを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、膨大なデータを取り扱う情報処理装置に係り、個々を知覚できない多数のノードからなる生のデータをセグメントと呼ばれる知覚可能な少数の単位に成長させる情報処理装置に関する。【０００２】
具体的には、本発明は、物理的なオブジェクトの２次元的イメージを生成し表示するための画像処理装置及び画像処理方法、並びにコンピュータ・プログラムに係り、特に、オブジェクトを微細なポリゴンなどの多数のノードの集合体すなわちセグメントとして扱い、オブジェクトの２次元的イメージ処理などを行なう画像処理装置及び画像処理方法、並びにコンピュータ・プログラムに関する。【０００３】
さらに詳しくは、本発明は、画像領域の分割や、分割した領域の統合（ｍｅｒｇｅ）などの処理を行ない、多角形メッシュを適当な粗さに調整するメッシュ・セグメンテーション処理を行なう画像処理装置及び画像処理方法、並びにコンピュータ・プログラムに係り、例えば２次元又は３次元のコンピュータ・グラフィックスを利用するアプリケーションに応じてプログレッシブなメッシュ・セグメンテーション処理を行なう画像処理装置及び画像処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００４】
コンピュータ上では、テキスト形式の文書ファイル以外に、音声、画像、自然言語などさまざまなメディアをデジタル化して、数学的に取り扱うことにより、情報の編集・加工、蓄積、管理、伝達、共有といった、より高度で多岐にわたるデータ処理を行なうことが可能となっている。例えば、コンピュータを用いて画像に対し変形や色の変更、画質向上、再符号化などのデジタル・イメージ処理を行なう画像処理技術は広範に普及している。この画像処理技術には、風景写真の中で美観を損ねる電柱などの物体を除去する特殊効果や、人間の顔から動物の顔へ滑らかに変化させるモーフィングなども含まれる。また、人工衛星から送られてくる写真映像の処理や、ＣＴスキャナで読み込まれた診断画像の処理など、画像処理技術は科学や医療などの各種専門分野にも適用されている。【０００５】
例えば、２次元又は３次元の物理オブジェクトのイメージを生成し表示する画像処理技術は「コンピュータ・グラフィックス（ＣＧ）」と呼ばれ、脚光を浴びている。この種のグラフィック・システムは、一般に、フロントエンドとしてのジオメトリ・サブシステムと、バックエンドとしてのラスタ・サブシステムで構成される。このうち、ジオメトリ・サブシステムでは、オブジェクトを多数の微細なポリゴン（通常は３角形）の集合体すなわち多角形メッシュとして扱い、ポリゴンを定義する各頂点について、座標変換や、クリッピング、光源計算といった幾何学計算を行なう。【０００６】
ここで、元のオブジェクトを領域分割したメッシュの粗さは、処理負荷や画質に大きく影響する。元のオブジェクトをより微細な画像領域に領域分割すると、処理対象とする頂点の個数もこれに比例して増大するので、処理量も増大する。また、多角形のサイズを大きくすると、最終的な成果物としての画像は粗くなる。このため、画像領域の分割や、分割した領域の統合（ｍｅｒｇｅ）などの処理を行ない、ＣＧを利用するアプリケーションに応じて多角形メッシュを適当な粗さに調整するというメッシュ・セグメンテーション処理が必要となる。【０００７】
メッシュ・セグメンテーションは、生（ｒａｗ）のデータを「セグメント（ｓｅｇｍｅｎｔ）」と呼ばれる知覚可能な少数の単位に成長させるための基本的な手法である。メッシュ・セグメンテーションは、１９７０代におけるコンピュータ画像処理の初期から研究が始められたが（例えば、非特許文献１を参照のこと）、いまだ活発な分野である。当初より、メッシュ・セグメンテーションは、カラー・イメージ、動画像、距離画像（ｄｅｐｔｈ  ｉｍａｇｅ若しくはｒａｎｇｅ  ｉｍａｇｅとして知られる）、３次元立体データ、３次元メッシュなどを取り扱っている。メッシュ・セグメンテーション処理で粗さの異なる複数の多角形メッシュ（セグメント）を作成することにより、階層化セグメンテーションを実現することができる。また、階層的なメッシュ・セグメンテーションをプログレッシブすなわち滑らかに行なうことにより、画像を利用するアプリケーションの幅は広がる。【０００８】
例えば、ファジーな画像クラスタリング及び画像切断方法を利用した階層化メッシュ分解を行なうメッシュ・セグメンテーション処理について提案がなされている（例えば、非特許文献２を参照のこと）。【０００９】
メッシュ・セグメンテーションは、基本的には、隣接する画像領域間の類似度に基づいて処理される。例えば、入力映像の色信号を所定の色空間に変換して、入力映像の色画素がこの色空間で占める位置に応じて入力映像を複数の領域に分割する初期映像分割を行ない、分割された領域間の水平的な隣接関係及び垂直的な包含関係に応じて分割された領域を複数のレイヤに分け、各レイヤ内において隣接する領域をグルーピングしてレイヤ毎に形成された領域グループ間の垂直的な包含関係を抽出して領域を構造化し、各領域間の水平的な関係及び領域グループ間の垂直的な包含関係に応じて各領域間の結合順位を決定し、決定された結合順位に基づいて隣接領域間の結合の成否を評価して、評価された領域が実質的に同一の映像特性を有する領域であると判断されれば領域の結合を行なうことができる（例えば、特許文献１を参照のこと）。【００１０】
しかしながら、従来のメッシュ・セグメンテーション処理では主として、領域成長（ｒｅｇｉｏｎ  ｇｒｏｗｉｎｇ）、又は階層的／反復的／光学的（ｈｉｅｒａｒｃｉｃａｌ／ｉｔｅｒａｔｉｖｅ／ｓｐｅｃｔｒａｌ）なクラスタリングを行なう。すなわち配列を用いた代数演算を繰り返し行なうため、処理速度が遅い。例えば、４００個程度のポリゴンを処理するのに１〜５７秒の時間を要するため、粗さの異なる複数のメッシュ・セグメンテーションをプログレッシブに生成することは難しい。また、システムにスケーラビリティがなく、ポリゴン数が増えると、処理時間は著しく増大してしまう。このため、パーソナル・コンピュータ（ＰＣ）のような一般的な計算機で処理することは困難であり、また、実時間性が要求されるインタラクティブなアプリケーションに適用することはできない。また、元のオブジェクトに関するオリジナルの情報が失われる、多数のパラメータ値を調整しなければならない、といった問題もある。【００１１】
【特許文献１】特開２００１−４３３８０号公報
【非特許文献１】Ａ．Ｒｏｓｅｎｆｅｌｄ，“Ｐｉｃｔｕｒｅ  ｐｒｏｃｅｓｓｉｎｇ  ｂｙ  ｃｏｍｐｕｔｅｒ”（Ａｃａｄｅｍｉｃ  Ｐｒｅｓｓ，１９６９）
【非特許文献２】Ｓａｇｉ  Ｋａｔｚ  ａｎｄ  Ａｙｅｌｌｅｔ  Ｔａｌ，“Ｈｉｅｒａｒｃｈｉｃａｌ  ｍｅｓｈ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｕｓｉｎｇ  ｆｕｚｚｙ  ｃｌｕｓｔｅｒｉｎｇ  ａｎｄ  ｃｏｔｓ．”（Ｉｎ  Ｐｒｏｃ．  ＳＩＧＧＲＡＰＨ（２００３）．ＡＣＭ  Ｔｒａｎｓ．ｏｎＧｒａｐｈｉｃｓ２２，３（２００３），３８２−３９１）
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、個々を知覚できない多数の微小なノードからなる生のデータをセグメントと呼ばれる知覚可能な少数の単位に成長させることができる、優れた情報処理装置及び情報処理方法、並びにコンピュータ・プログラムを提供することにある。【００１３】
本発明のさらになる目的は、物理的なオブジェクトを多数の微細なノードの集合体（すなわちセグメント）として扱い、ノード同士の統合処理によってセグメントを成長させることで、オブジェクトの２次元的イメージを処理することができる、優れた画像処理装置及び画像処理方法、並びにコンピュータ・プログラムを提供することにある。【００１４】
本発明のさらなる目的は、画像領域の分割や、分割した領域の統合（ｍｅｒｇｅ）などの処理を行なって領域を成長させ、多角形メッシュを適当な粗さに調整するメッシュ・セグメンテーション処理を好適に行なうことができる、優れた画像処理装置及び画像処理方法、並びにコンピュータ・プログラムを提供することにある。【００１５】
本発明のさらなる目的は、２次元又は３次元のコンピュータ・グラフィックスを利用するアプリケーションに応じてプログレッシブなメッシュ・セグメンテーション処理を高速且つ高い精度で行なうことができる、優れた画像処理装置及び画像処理方法、並びにコンピュータ・プログラムを提供することにある。
【課題を解決するための手段】
【００１６】
本発明は、上記課題を参酌してなされたものであり、その第１の側面は、それぞれ属性値を持つ複数のノードでトポロジが形成されたデータを取り扱う情報処理装置であって、
前記トポロジ上で隣接するノード同士がそれぞれ持つ属性値に基づいてノード間を結ぶエッジの重み因子を求め、重み因子に基づいてエッジをソーティングするトポロジ評価部と、
該ソーティングされた順に従って、エッジで結ばれるノードのペアを取り出して、該ノード同士を統合すべきか否かを所定の統計的処理アルゴリズムに基づいて評価し、ノード領域の統合処理を行なうノード統合処理部と、
を具備することを特徴とする情報処理装置である。【００１７】
本発明の第１の側面によれば、隣接するノード同士を統合すべきか否かを統計的処理アルゴリズムに基づいて判断し、ノードの統合を繰り返し実行していくことにより、個々を知覚できない多数のノードからなる生のデータから、セグメントと呼ばれる知覚可能な少数の単位に成長させることができる。ここで言う統計的処理アルゴリズムでは、例えば各ノードがそれぞれ持つ属性情報における集中不均衡（ｃｏｎｃｅｎｔｒａｔｉｏｎ  ｉｎ−ｅｑｕａｌｉｔｙ）現象から導き出される判断式に基づいて、隣接するノード同士が類似するか、言い換えればノードを統合することができるかどうかを判別する。【００１８】
このような統計的処理アルゴリズムに基づくノードの統合処理は、各ノードが持つ属性情報を統計処理するという簡素な計算で構成されることから高速化が可能である。例えば、パーソナル・コンピュータなどの一般的な計算機を用いて毎秒百万個の多角形を処理することができる。また、判断式に含まれるパラメータ値を調整することによって、ノード同士を統合する基準を自在に設定して、所望する粗さのセグメントまで成長させることができ、システムはスケーラビリティを持つ。【００１９】
したがって、本発明の第１の側面によれば、生のデータを構成する複数のノードのトポロジを入力値とし、ノードの統合処理を統計的処理アルゴリズムに従って再帰的に行なっていく（すなわち、ｍｅｓｈ  ｇｒｏｗｉｎｇを行なう）ことで、任意の粗さのセグメントを生成することができる。また、統計的処理アルゴリズムに基づく判断式のパラメータ値を変更することで、粗さの異なる複数のセグメントを円滑に生成することができる。【００２０】
また、本発明の第２の側面は、オブジェクトを複数の多角形からなる多角形メッシュとして扱い画像処理を行なう画像処理装置であって、
多角形メッシュを記述する隣接グラフを入力する隣接グラフ入力部と、
エッジで結ばれる各画像領域が持つ属性値を比較して比較結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングする隣接グラフ評価部と、
ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、画像領域同士を統計的処理アルゴリズムに基づいて統合すべきか否かを評価し、画像領域の統合処理を行なう画像領域統合処理部と、
を具備することを特徴とする画像処理装置である。この画像処理装置は、画像領域の統合処理をした結果として残された微細な領域を処理する微小領域処理部をさらに備えることができる。【００２１】
本発明の第２の側面は、２次元又は３次元の物理オブジェクトの２次元的イメージを生成し表示するための画像処理装置に関する。コンピュータ・グラフィックスの分野では、通常、処理対象となるオブジェクトを多数の微細なポリゴン（通常は３角形）の集合体すなわち多角形メッシュとして扱い、画像処理を行なう。多角形メッシュの粗さは、処理負荷や画質に大きく影響するため、画像領域の分割や、分割した領域の統合（ｍｅｒｇｅ）などの処理を行ない、３ＤＣＧを利用するアプリケーションに応じて多角形メッシュを適当な粗さに調整するというメッシュ・セグメンテーション処理が必要となる。また、メッシュ・セグメンテーションをプログレッシブすなわち滑らかに行なうことにより、画像を利用するアプリケーションの幅は広がる。【００２２】
ところが、従来の手法で、処理速度が遅く、一般的な計算機ではプログレッシブなメッシュ・セグメンテーション処理の実現が困難であるとともに、インタラクティブなアプリケーションに適用することはできない。【００２３】
これに対し、本発明の第２の側面では、隣接する画像領域を統合すべきか否かを統計的処理アルゴリズムに基づいて判断していくことにより、３次元オブジェクトを分割した微小な多数の多角形から、画像領域の統合を繰り返し実行して、所望する粗さからなる多角形メッシュを生成するようにしている。ここで言う統計的処理アルゴリズムでは、例えば画像領域を構成する多角形の面積における集中不均衡現象から導き出される判断式に基づいて、隣接する画像領域同士が類似するか、言い換えれば画像領域を統合することができるかどうかを判別する。【００２４】
このような統計的処理アルゴリズムに基づく画像領域の統合処理は、多角形の面積を統計処理するという簡素な計算で構成されることから高速化が可能である。例えば、パーソナル・コンピュータなどの一般的な計算機を用いて毎秒百万個の多角形を処理することができる。また、判断式に含まれるパラメータ値を調整することによって、画像領域同士を統合する基準を自在に設定して、所望する粗さの多角形メッシュを生成することができ、システムはスケーラビリティを持つ。【００２５】
したがって、本発明によれば、処理対象とする物理オブジェクトを分割した微小な多数の多角形の集合を入力値とし、多角形メッシュからなる画像領域の統合処理を統計的処理アルゴリズムに従って行なっていく（すなわち、ｍｅｓｈ  ｇｒｏｗｉｎｇを行なう）ことで、任意の粗さの多角形メッシュを生成することができる。また、統計的処理アルゴリズムに基づく判断式のパラメータ値を変更することで、粗さの異なる複数の多角形メッシュを円滑に生成することができる。すなわち、プログレッシブなメッシュ・セグメンテーションを実現できる、さまざまなインタラクティブなアプリケーションに適用することができる。【００２６】
本発明に係るメッシュ・セグメンテーションのアプリケーションとして、例えば、パラメタリゼーション及びテクスチャ・マッピング、画像変形（ｍｏｒｐｈｉｎｇ）、多解像度モデリング、画像編集、画像圧縮、アニメーション、並びに形状マッチングなどを挙げることができる。【００２７】
画像処理の分野では一般に、画像領域としての多角形メッシュを、その構成要素となる複数の多角形間の関係を記述した隣接グラフ（Ｉｎｃｉｄｅｎｃｅ  Ｇｒａｐｈ）の形式で表現する。本発明に係るメッシュ・セグメンテーション方法では、多角形メッシュを構成する個々の多角形をノードとして扱い、隣接する多角形同士が接する辺に相当するエッジを用いて対応するノード間を結んで記述される隣接グラフを入力に用いる。【００２８】
そして、本発明の第２の側面に係るメッシュ・セグメンテーション方法では、まず、入力された隣接グラフの各エッジを評価してソーティングを行なう。エッジの評価は、具体的には、エッジで結ばれる各画像領域が持つ属性値を比較して比較結果に基づいて重み因子をエッジに付与する。ここで言う画像領域は、最小単位である多角形と、複数の多角形を統合した多角形メッシュとして構成される画像領域を含む。【００２９】
ここで言う属性値として、例えば、画像領域が持つ面積（画像領域に統合された各多角形メッシュが持つ平均面積）を用い、エッジで結ばれる画像領域間の面積の相違をエッジの重み値として与えることができる。この場合、画像領域間の面積の差が小さいほど重み値は小さくなり、後続の画像統合処理では処理順位が高くなる。あるいは、画像領域を構成する多角形の面積の他に、画像領域の法線方向、色などの画素属性情報（ＲＧＢのうち少なくとも１成分についての画像領域内の平均色）（但し、テクスチャを持つ多角形メッシュの場合）を用いてエッジの重みを与えることができる。【００３０】
本発明の第２の側面に係るメッシュ・セグメンテーション方法では、画像領域を構成する多角形の面積における集中不均衡現象から導き出される判断式に基づいて、エッジで結ばれる画像領域同士を統合すべきかどうかを判断するが、具体的には、エッジで結ばれる２つの画像領域Ｒk及びＲlに関して以下の統計的アルゴリズムに基づく判断式を満たすときに、画像領域Ｒk及びＲlを統合すべきと判定する。但し、下式において、画像領域Ｒkは面積Ｓkを持つとともにｎk個の多角形で構成され、画像領域Ｒlは面積Ｓlを持つとともにｎl個の多角形で構成されるとし、Ａは多角形の最大面積とし、Ｑはセグメンテーションの粗さを制御するためのパラメータとする。【００３１】
【数１】
0004780106.tif 000002
【００３２】
上記の統計的処理アルゴリズムに基づく判断式は、セグメンテーションの粗さを制御するためのパラメータＱを含んでいるので、所望のセグメンテーションの粗さが得られるようなパラメータＱの値を外部から与えることができる。また、所望するセグメンテーションの粗さや分割した画像領域の個数が外部から要求されたときに、該当するパラメータＱの値に変換してシステムに与えるようにしてもよい。このような柔軟なパラメータＱの設定を行なうことにより、プログレッシブなメッシュ・セグメンテーションを実現することができ、さまざまなインタラクティブ・アプリケーションに適用し易くなる。【００３３】
初期状態のノードは、隣接グラフ中の最小単位の多角形であるが、画像の統合処理が進むと、ノードは複数の多角形からできた多角形メッシュで構成される画像領域に成長する。ノードすなわち画像領域の統合の成否を統計的処理アルゴリズムに基づく判断式により判定するために必要な情報として、各ノードについての面積及び多角形の個数が計算され、ノード統計情報として保持される。また、画像領域の統合を実行したときには、統合して新たに生成された画像領域の面積及び多角形の個数を算出して、ノード統計情報の更新処理が行なわれる。【００３４】
ここで、画像領域の統合が進むと、成長した画像領域はその面積が巨大であるとともに、多角形の個数も大きな値となる。このような場合、隣接する画像領域との統合の正否を判断する上では、境界に近い多角形の情報がより重要であるにも拘らず、画像領域の中央部から余分な影響を受けるという結果に陥る。すなわち、統計的処理アルゴリズムに基づく上記の判断式では正確な境界判定を行なえなくなる。【００３５】
そこで、画像領域の統合を行なったときに、新たに生成された画像領域の「外皮（Ｃｒｕｓｔ）」に相当する領域境界近辺の多角形のみを残して、以降の画像領域の統合についての成否判断を行なうようにしてもよい。この場合、統合して新たに生成される画像領域全体ではなく、“Ｃｒｕｓｔ”に相当する領域についての面積及び多角形の個数を算出してノード統計情報の更新処理を行なう。【００３６】
「外皮」として、例えば統合して新たに生成された画像領域の全周に渡る境界近辺の多角形すなわち“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”のみを残して、以降の画像領域統合処理を行なうようにすることができる。この“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”を残す際に発生するノード統計情報の更新処理は比較的計算量が少なく、且つ以降の画像領域の統合についての成否判断を正確にすることができる。【００３７】
あるいは、「外皮」として、統合しようとする各画像領域が接する境界近辺の多角形すなわち“Ｂｏｒｄｅｒ  Ｃｒｕｓｔ”のみを残して、以降の画像領域統合処理を行なうようにしてもよい。このＢｏｒｄｅｒ  Ｃｒｕｓｔを用いることにより、Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔを用いた場合よりもより正確に以降の画像領域の統合についての成否判断を行なうことができる。但し、Ｂｏｒｄｅｒ  Ｃｒｕｓｔを用いる場合には、ノード統計情報だけではなく、隣接グラフも更新しなければならないので、その計算量は膨大となる。【００３８】
また、本発明の第３の側面は、それぞれ属性値を持つ複数のノードでトポロジが形成されたデータを取り扱うための処理をコンピュータ上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、前記コンピュータに対し、
前記トポロジ上で隣接するノード同士がそれぞれ持つ属性値に基づいてノード間を結ぶエッジの重み因子を求め、重み因子に基づいてエッジをソーティングするトポロジ評価手順と、
該ソーティングされた順に従って、エッジで結ばれるノードのペアを取り出して、該ノード同士を統合すべきか否かを所定の統計的処理アルゴリズムに基づいて評価し、ノード領域の統合処理を行なうノード統合処理手順と、
を実行させることを特徴とするコンピュータ・プログラムである。【００３９】
また、本発明の第４の側面は、オブジェクトを複数の多角形からなる多角形メッシュとして扱い画像処理を行なうための処理をコンピュータ上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、前記コンピュータに対し、
多角形メッシュを記述する隣接グラフを入力する隣接グラフ入力手順と、
エッジで結ばれる各画像領域が持つ属性値を比較して比較結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングする隣接グラフ評価手順と、
ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、画像領域同士を統計的処理アルゴリズムに基づいて統合すべきか否かを評価し、画像領域の統合処理を行なう画像領域統合処理手順と、
を実行させることを特徴とするコンピュータ・プログラムである。【００４０】
本発明の第３及び第４の各側面に係るコンピュータ・プログラムは、コンピュータ・システム上で所定の処理を実現するようにコンピュータ可読形式で記述されたコンピュータ・プログラムを定義したものである。換言すれば、本発明の第３及び第４の各側面に係るコンピュータ・プログラムをコンピュータ・システムにインストールすることによって、コンピュータ・システム上では協働的作用が発揮され、本発明の第１の側面に係る情報処理装置、及び第２の側面に係る画像処理装置と同様の作用効果をそれぞれ得ることができる。
【発明の効果】
【００４１】
本発明によれば、個々を知覚できない多数の微小なノードからなる生のデータをセグメントと呼ばれる知覚可能な少数の単位に成長させることができる、優れた情報処理装置及び情報処理方法、並びにコンピュータ・プログラムを提供することができる。【００４２】
また、本発明によれば、２次元又は３次元オブジェクトを多数の微細なポリゴン（通常は３角形）の集合体すなわち多角形メッシュとして扱い、その２次元的イメージを処理する際に、多角形メッシュを適当な粗さに調整するメッシュ・セグメンテーション処理を好適に行なうことができる。すなわち、コンピュータ・グラフィックスを利用するアプリケーションに応じてプログレッシブなメッシュ・セグメンテーション処理を高速且つ高い精度で行なうことができる。【００４３】
本発明に係る画像処理装置は、統計的処理アルゴリズムに基づいて高速な画像領域の統合処理を行なうことができ、一般的な計算機上でもプログレッシブなメッシュ・セグメンテーション処理を実現可能である。【００４４】
また、本発明に係るメッシュ・セグメンテーション処理は、判断式に含まれるパラメータ値を調整することにより、画像領域同士を統合する基準を自在に設定して、所望する粗さの多角形メッシュを生成することができる。また、システムはスケーラビリティを持ち、パラメタリゼーション及びテクスチャ・マッピング、画像変形（ｍｏｒｐｈｉｎｇ）、多解像度モデリング、画像編集、画像圧縮、アニメーション、並びに形状マッチングなど、さまざまなインタラクティブ・アプリケーションに適用することができる。【００４５】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施形態や添付する図面に基づくより詳細な説明によって明らかになるであろう。
【図面の簡単な説明】
【００４６】
【図１】図１は、本発明の一実施形態に係る画像処理装置の機能的構成を模式的に示した図である。
【図２】図２は、隣接グラフを例示した図である。
【図３】図３は、隣接グラフを例示した図である。
【図４】図４は、エッジの評価を行なう処理方法を説明するための図である。
【図５】図５は、メッシュ・セグメンテーション処理を行なうための処理手順の一例を示したフローチャートである。
【図６】図６は、スライド・バーを用いてユーザが多スケールのパラメータＱを設定したときにインタラクティブに得られるセグメンテーション結果の例を示した図である。
【図７】図７は、画像領域の統合処理が進んだ様子を示した図である。
【図８】図８は、統合して新たに生成された画像領域の全周に渡る境界近辺の多角形すなわち“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”のみを残した様子を示した図である。
【図９】図９は、“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”のみを残したメッシュ・セグメンテーション処理を行なうための処理手順を示したフローチャートである。
【図１０】図１０は、統合しようとする各画像領域が接する境界近辺の多角形すなわち“Ｂｏｒｄｅｒ  Ｃｒｕｓｔ”のみを残した様子を示した図である。
【図１１】図１１は、“Ｂｏｒｄｅｒ  Ｃｒｕｓｔ”のみを残したメッシュ・セグメンテーション処理を行なうための処理手順を示したフローチャートである。
【図１２】図１２は、隣接する画像領域Ｒi及びＲjからＢｏｒｄｅｒ  Ｃｒｕｓｔを取り出す様子を示した図である。
【図１３】図１３は、“Ｂｏｒｄｅｒ  Ｃｒｕｓｔ”のみを残したメッシュ・セグメンテーション処理を行なった際の、隣接グラフを更新する処理を説明するための図である。
【図１４】図１４は、メッシュ・セグメンテーション時に、スライド・バーの操作を介してＱ値を設定して分割する画像領域数を調整する様子を示した図である。
【図１５】図１５は、メッシュ・セグメンテーション時に、スライド・バーの操作を介してＱ値を設定して分割する画像領域数を調整する様子を示した図である。
【図１６】図１６は、メッシュ・セグメンテーション時に、スライド・バーの操作を介してＱ値を設定して分割する画像領域数を調整する様子を示した図である。
【図１７】図１７は、本発明の一実施形態に係る情報処理装置の機能的構成を模式的に示した図である。
【図１８】図１８は、隣接するノード同士を統合して新たなノードを生成する様子を模式的に示した図である。
【図１９】図１９は、図１７に示した情報処理装置によってセグメンテーション処理を行なう手順を示したフローチャートである。
【符号の説明】
【００４７】
１…画像情報入力部
２…隣接グラフ評価部
３…画像領域統合処理部
４…微小領域処理部
５…パラメータ設定部
１０…画像処理装置
５０…情報処理装置
５１…ノード入力部
５２…トポロジ評価部
５３…統合処理部
５４…微小ノード処理部
５５…パラメータ設定部
【発明を実施するための最良の形態】
【００４８】
以下、図面を参照しながら本発明の実施形態について詳解する。【００４９】
本発明は、個々を知覚できない多数の微小なノードによってトポロジが形成された生のデータを扱う情報処理装置に関するものであり、各ノードが持つ属性情報に対して所定の統計的処理アルゴリズムを施すことによって、隣接するノード同士を統合すべきか否かを統計的処理アルゴリズムに基づいて判断し、ノードの統合を繰り返し実行していくことにより、個々を知覚できない多数のノードから、セグメントと呼ばれる知覚可能な少数の単位に成長させるように構成されている。【００５０】
図１７には、本発明の一実施形態に係る情報処理装置の機能的構成を模式的に示している。図示の情報処理装置５０は、複数のノードによってトポロジが形成されている生のデータを処理対象として入力するノード入力部５１と、トポロジ上で隣接するノード同士を結んでいる各エッジを評価してソーティングを行なうトポロジ評価部５２と、ソーティングされた順にしたがってエッジで結ばれるノードのペアを取り出し、これらを統計的処理アルゴリズムに基づいて評価して統合処理を行なう統合処理部５３と、ノードの統合処理をした結果として十分な大きさのセグメンテーションに成長せずに残された微細のノードを処理する微小ノード処理部５４を備えている。【００５１】
この種の画像処理装置１０は、専用のハードウェア装置としてデザインしてもよいが、パーソナル・コンピュータ（ＰＣ）などの一般的な計算機システム上で各機能モジュール５１〜５４に相当する処理を実行するアプリケーション・プログラムを起動するという形態で実現することも可能である。一般的な計算機システムは、例えばプロセッサに米インテル社のＰｅｎｔｉｕｍ（登録商標）IV（１．６ＧＨｚ）を使用し、１ＧＢのＲＡＭで構成されるメイン・メモリを備える。また、アプリケーション・プログラムは、オペレーティング・システム（ＯＳ）で提供されるＡＰＩ（アプリケーション・プログラミング・インターフェース）を利用して、Ｃ++言語でコーディングすることができる。【００５２】
ノード入力部５１に入力される処理対象データは、複数のノードによってトポロジが形成されている。トポロジは、複数のノードと、ノード間を結ぶエッジで構成され、各ノードは属性情報を持っている。また、統合処理部５３によってノード同士の統合が行なわれると、新たなノードに関する属性情報が算出される。【００５３】
トポロジ評価部５２では、入力されたデータに含まれる隣接ノード間を結ぶエッジを評価してソーティングを行なう。エッジの評価は、具体的には、エッジで結ばれる各ノードが持つ属性値を比較して比較結果に基づいて重み因子をエッジに付与し、重み値に基づいてトポロジ中のエッジをソーティングする。エッジに与えられる重み値は、当該エッジで結ばれる画像領域間の類似度の指標となる。【００５４】
ノードが面積を持つ場合には、その属性情報として面積（当該ノードに統合された元のすべてのノードの面積の平均値）を用い、エッジで結ばれるノード間の面積の相違をエッジの重み値として与えて、重み値の小さい順（ｉｎｃｒｅａｓｉｎｇ  ｏｒｄｅｒ）にソーティングを行なう。この場合、ノード間の面積の差が小さいほど重み値は小さくなり、後続の統合処理では処理順位が高くなる。あるいはノードが属性情報として色を持つ場合、画素属性情報（ＲＧＢのうちの少なくとも１成分の平均色）を用いてエッジの重み値を評価することができる。【００５５】
続いて、統合処理部５３では、ソーティングされた順に従ってエッジを挟むノードのペアを取り出し、統合処理を行なってセグメンテーションを成長させる。エッジには、エッジで結ばれる画像領域間の類似度の指標となる重みが与えられるので、重みが小さい順に統合処理を行なうことは、類似するノード間の統合処理を優先的に実行することに相当する。【００５６】
統合処理部５３では、ノードのペアに対し、統計的処理アルゴリズムに基づいて、統合すべきかどうかを判断する。具体的には、隣接するノードｆ（ｉ）及びｆ（ｊ）がそれぞれ属性値として持つ統計情報Ｓｔａｔｓ．ｆ（ｉ）及びＳｔａｔｓ．ｆ（ｊ）に関して以下の統計的アルゴリズムに基づく判断式（Ｐｒｅｄｉｃａｔｅ）を満たすときに、ノードｆ（ｉ）及びｆ（ｊ）を統合すべきと判定する。但し、下式において、ノードｆ（ｉ）はＮ（ｉ）個のノードを含むとともにノードｆ（ｊ）はＮ（ｊ）個のノードを含み、関数ｂ（ｘ）はｂ（ｘ）＝（ｌｏｇｘ）／Ｑ＋（Ｋ／ｘ）であり、Ｋは定数、Ｑはノードを統合して成長したセグメンテーションの粗さを制御するためのパラメータとする。【００５７】
【数２】
0004780106.tif 000003
【００５８】
上記の判断式は、画像領域を構成する多角形の面積において現れる現象である、統計的な集中不均衡（ｓｔａｔｉｓｔｉｃａｌ  ｃｏｎｃｅｎｔｒａｔｉｏｎ  ｉｎｅｑｕａｌｉｔｙ）から導き出されるものである。この現象は、統計学の分野では、中心極限定理（ｃｅｎｔｒａｌ  ｌｉｍｉｔ  ｔｈｅｏｒｅｍ）として一般的である。中心極限定理は、標本平均と真の平均との誤差を規定するもので、標本の分布がいかなる分布であっても、その誤差はサンプル数を大きくすると近似的に正規分布に従う。【００５９】
上式の右辺のＱはセグメンテーションの粗さを制御するためのパラメータである。Ｑを大きくとると右辺の値が小さくなり、判断式を満たすのが困難となる結果、ノードの統合が抑制される。逆に、Ｑを小さい値にすると右辺の値が大きくなり、判断式を容易に満たすようになるので、ノードの統合すなわちセグメンテーションの成長が促進される。【００６０】
図１８には、ｉ番目のノードＶｉとｊ番目のノードとＶｊを統合の判断式（ｍｅｒｇｉｎｇ  Ｐｒｅｄｉｃａｔｅ）に基づいて統合処理して、新たなノードＶ’が生成される様子を模式的に示している。【００６１】
各ノードＶｉ及びＶｊは、ノードに含まれるノードの個数Ｎｉ及びＮｊ、識別情報ＩＤｉ及びＩＤｊといった一般情報部と、属性情報を格納するメディア（データ）部で構成される。初期状態のノードは、自身しか持たないからノードの個数Ｎは１であるが、統合して得られるＶ’のノード数Ｎ’はＮｉ＋Ｎｊとなる。また、新しい識別情報ＩＤ’は、Ｕｎｉｏｎ−Ｆｉｎｄデータ構造を持つ互いに素な集合を用いて、元の識別情報ＩＤｉ及びＩＤｊから生成される。また、メディア部の属性情報は、各ノードＶｉ及びＶｊの属性情報から統計的演算を基に求められる。例えば、ノードが持つ色情報が属性情報である場合には、各ノードＶｉ及びＶｊの平均色が新しいノードの属性情報となる。あるいは、ノードが持つ面積が属性情報である場合には、各ノードＶｉ及びＶｊの平均面積が新しいノードの属性情報となる。Ｕｎｉｏｎ−Ｆｉｎｄアルゴリズムに関しては、例えば、Ｒ．Ｅ．Ｔａｒｊａｎ著“Ａ  ｃｌａｓｓ  ｏｆ  ａｌｇｏｒｉｔｈｍｓ  ｗｈｉｃｈ  ｒｅｑｕｉｒｅ  ｎｏｎｌｉｎｅａｒ  ｔｉｍｅ  ｔｏ  ｍａｉｎｔａｉｎ  ｄｉｓｊｏｉｎｔ  ｓｅｔｓ．”（Ｊ．Ｃｏｍｐｕｔ．Ｓｙｓｔ．Ｓｃｉ．，１８（２）：１１０−１２７，１９７９）を参照されたい。【００６２】
最後に、微小ノード処理部５４は、ノードの統合処理をした結果として十分な大きさのセグメンテーションに成長することなく残された微細なノイズを処理する。例えば、大きなセグメンテーションに成長したノードの間あるいは内部に、統合されないまま残された微小なノイズを、判断式を満たすか否かに変わらず、隣接するいずれかのセグメンテーションに統合し、処理結果の見栄えを良くする。【００６３】
図１９には、図１７に示した情報処理装置２０上で実行されるセグメンテーション処理の手順をフローチャートの形式で示している。【００６４】
まず、ノード入力部５１において、処理対象となる生のデータを入力する（ステップＳ２１）。生のデータは、トポロジを形成するノードからなる。ノード入力部５１は、入力されたデータのトポロジをスキャンして、各ノードＶｉに識別情報ＩＤｉを付与するとともに、その識別情報及びノードのメディア部に格納されている属性情報をノード統計情報に登録するといった初期化処理を行なう。【００６５】
次いで、トポロジ評価部５２では、隣接するノード同士を結ぶ各エッジを評価してソーティングを行なう（ステップＳ３２）。具体的には、エッジで結ばれるノード間の属性情報の相違をエッジの重み値として与えて、重み値の小さい順（ｉｎｃｒｅａｓｉｎｇ  ｏｒｄｅｒ）にソーティングを行なう。【００６６】
続いて、パラメータ設定部５５を介して、セグメンテーションの粗さをコントロールするためのパラメータＱを設定する（ステップＳ３３）。【００６７】
統合処理部５３では、ソーティングされた順に従ってエッジで結ばれているノードのペアを取り出す（ステップＳ３４）。そして、これらのノードが統計的アルゴリズムに基づく判断式を満たすかどうかに基づいて統合処理を行なう（ステップＳ３５）。ここで用いる判断式は、画像領域を構成する多角形の面積において現れる現象である、統計的な集中不均衡から導き出されるものであり（前述）、ステップＳ３３で設定されたパラメータＱを用いる。【００６８】
統合処理部３は、ノード同士を統合したときには、新しいノードＶ’を生成して、このノードを識別するための新たなＩＤ’を与え、統合により新たに生成されたノードの属性情報を算出して、ノード統計情報の更新処理を行なう（ステップＳ３６）。【００６９】
続いて、統合処理部５３は、ノードの更新処理を行なう（ステップＳ３７）。すなわち、隣接ノード間の各エッジの重み因子を再計算して、重み値の大きさによりエッジを再ソーティングする。そして、ステップＳ３４に復帰して、ソーティングされた順に従ってエッジで結ばれるノードのペアを取り出し、統計的処理アルゴリズムに基づくノードの統合処理を繰り返し行なう。【００７０】
このようなノードの統合と、統合に伴うノード統計情報の更新処理を再帰的に繰り返していくと、やがてパラメータＱで閾値が設定される判断式を満たすノードの組み合わせが見つからなくなる。すなわち、トポロジ中に未処理のエッジがなくなると（ステップＳ３４のＮｏ）、微小領域処理部５４は、十分な大きさのセグメンテーションに成長することなく残された微細なノードを処理する（ステップＳ３８）。例えば、大きなセグメンテーションの間あるいは内部に、統合されないまま残された微小なノードを、判断式を満たすか否かに変わらず、隣接するいずれかのセグメンテーションに統合し、処理結果の見栄えを良くする。【００７１】
本発明は、２次元又は３次元オブジェクトの２次元的イメージを生成し表示するための画像処理装置に適用することができる。コンピュータ・グラフィックスの分野では、通常、処理対象となる２次元又は３次元の物理オブジェクトを多数の微細なポリゴン（通常は３角形）の集合体すなわち多角形メッシュとして扱い、画像処理を行なう。多角形メッシュの粗さは、処理負荷や画質に大きく影響する。このため、画像領域の分割や、分割した領域の統合（ｍｅｒｇｅ）などの処理を行ない、コンピュータ・グラフィックスを利用するアプリケーションに応じて多角形メッシュを適当な粗さに調整するというメッシュ・セグメンテーション処理が必要となる。メッシュ・セグメンテーションをプログレッシブすなわち滑らかに行なうことにより、画像を利用するアプリケーションの幅は広がる。【００７２】
本発明に係るメッシュ・セグメンテーションでは、統計的処理アルゴリズムを用いて隣接する画像領域を統合すべきか否かを判断していくことにより、３次元オブジェクトを分割した微小な多数の多角形から、画像領域の統合を繰り返し実行して、所望する粗さからなる多角形メッシュを生成する。統計的処理アルゴリズムでは、画像領域としての多角形メッシュにおける面積の集中不均衡（ｃｏｎｃｅｎｔｒａｔｉｏｎ  ｉｎ−ｅｑｕａｌｉｔｙ）現象から導き出される判断式に基づいて、隣接する画像領域同士を統合することができるかどうかを判別する。【００７３】
このような統計的処理アルゴリズムに基づく画像領域の統合処理は、多角形の面積を統計処理するという簡素な計算で構成されることから、高速化が可能である。例えば、パーソナル・コンピュータなどの一般的な計算機を用いて毎秒百万個の多角形を処理することができる。また、判断式に含まれるパラメータ値を調整することによって、画像領域同士を統合する基準を自在に設定して、所望する粗さの多角形メッシュを生成することができ、システムはスケーラビリティを持つ。【００７４】
図１には、本発明の一実施形態に係る画像処理装置の機能的構成を模式的に示している。図示の画像処理装置１０は、処理対象となる３次元画像情報を隣接グラフの形式で入力する画像情報入力部１と、入力した隣接グラフの各エッジを評価してソーティングを行なう隣接グラフ評価部２と、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、これらを統計的処理アルゴリズムに基づいて評価して統合処理（ｍｅｓｈ  ｇｒｏｗｉｎｇ）を行なう画像領域統合処理部３と、画像領域の統合処理をした結果として残された微細な領域を処理する微小領域処理部４を備えている。【００７５】
この種の画像処理装置１０は、専用のハードウェア装置としてデザインしてもよいが、パーソナル・コンピュータ（ＰＣ）などの一般的な計算機システム上で各機能モジュール１〜４に相当する処理を実行するアプリケーション・プログラムを起動するという形態で実現することも可能である。一般的な計算機システムは、例えばプロセッサに米インテル社のＰｅｎｔｉｕｍ（登録商標）IV（１．６ＧＨｚ）を使用し、１ＧＢのＲＡＭで構成されるメイン・メモリを備える。また、アプリケーション・プログラムは、例えばＯｐｅｎＧＬで提供されるＡＰＩ（アプリケーション・プログラミング・インターフェース）を利用して、Ｃ++言語でコーディングすることができる。【００７６】
画像処理の分野では、画像領域としての多角形メッシュを、その構成要素となる複数の多角形間の関係を記述した隣接グラフ（Ｉｎｃｉｄｅｎｃｅ  Ｇｒａｐｈ若しくはＲｅｇｉｏｎ  Ａｄｊａｃｅｎｔ  Ｇｒａｐｈ（ＲＡＧ））の形式で表現することは一般的に行なわれている。隣接グラフの具体的な記述方法は幾つか挙げられる。隣接グラフは、複数のノードと、ノード間を結ぶエッジで構成されるが、ノード及びエッジに何を扱うかはさまざまである。例えば、多角形をノードとすると、その辺又は頂点をエッジにすることができる。あるいは、多角形の辺をノードとした場合、頂点又は多角形をエッジにすることができる。あるいは、頂点をノードとした場合、多角形の辺又は多角形をエッジにすることができる。【００７７】
本実施形態に係る画像処理装置１では、多角形をノードとし、多角形の辺をエッジとして構成される隣接グラフを扱う。すなわち、画像情報入力部１は、多角形メッシュを構成する個々の多角形をノードとし、隣接する多角形同士が接する辺に相当するエッジを用いて対応するノード間を結んで記述される隣接グラフを入力データとする。【００７８】
ここで、隣接グラフの作成方法について説明しておく。【００７９】
まず、対象とする画像領域に属する各多角形ＴiをノードＮiに関連付ける。そして、ノードＮiとノードＮj間において、双方に対応する多角形Ｔi及びＴjに属する唯一の辺があれば、両ノード間を結ぶエッジｅijとして生成する。【００８０】
隣接グラフは、エッジの端点に従って多角形のソーティングを行なうことによって、頂点及び面のインデックス配列から直接的に構築することができる。個々の多角形に属する辺すなわちエッジは、多角形メッシュすなわち画像領域の境界となるエッジ（Ｂｏｕｎｄａｒｙ  ｅｄｇｅ）と、多角形メッシュではなく多角形メッシュ内の隣接する他の多角形と接するエッジ（Ｉｎｔｅｒｉｏｒ  Ｅｄｇｅ）に分けられる。画像領域の境界に当たるエッジは１つの多角形にしか属さないので、境界以外（すなわち画像領域の内側の）エッジのみを処理対象にする。この処理には、頂点及び面のインデックス配列があれば十分であり、ｈａｌｆ−ｅｄｇｅ、ｑｕａｄ−ｅｄｇｅといった複雑な隣接データ構造は必要でない。【００８１】
図２には、最も単純な隣接グラフの例を示している。同図左に示す多角形メッシュは、辺すなわちエッジｅijで接する２つの３角形Ｔi及びＴjで構成される。この多角形メッシュを記述した隣接グラフは、同図右に示すように、各３角形Ｔi及びＴjに相当する２つのノードＮi及びＮjと、両ノードを結ぶエッジｅijで構成される。【００８２】
また、図３には、少し複雑な隣接グラフの構成例を示している。同図左に示す多角形メッシュは、７個の３角形Ｔ1〜Ｔ7で構成され、Ｔ1はＴ2と接し、Ｔ2はＴ1、Ｔ3、Ｔ4と接し、Ｔ3はＴ2及びＴ6と接し、Ｔ4はＴ2及びＴ5と接し、Ｔ5はＴ4及びＴ6と接し、Ｔ6はＴ3、Ｔ5、Ｔ7と接している。この多角形メッシュを記述した隣接グラフは、同図右に示すように、隣接する双方の３角形に属する辺すなわちエッジによってそれぞれの３角形に相当するノード間を結んで構成される。【００８３】
なお、ノードは、初期状態では多角形メッシュの最小単位の多角形である。あるいは、２次元イメージにおける個々のピクセルや、３次元の立体イメージであればボクセル（ｖｏｘｅｌ）が１つのノードである。画像の統合処理が進むと、ノードは複数の多角形（あるいは、ピクセル又はボクセル）からなる多角形メッシュで構成される画像領域に成長する。画像処理装置１内では、各ノードＮiに関して、一意に識別するための識別情報ｉｄ（Ｎi）と、該当する画像領域（最初は１つの多角形）が持つ面積ａｒｅａ（Ｎi）と、該当する画像領域すなわち多角形メッシュを構成する多角形の個数ｎ（Ｎi）（初期値は１）を、「ノード統計情報」として保持している。各ノードが面積及び多角形の個数を保持するのは、ノードすなわち画像領域の統合の成否を統計的処理アルゴリズムに基づく判断式により判定処理するために必要な情報だからである。【００８４】
隣接グラフ評価部２では、入力された隣接グラフの各エッジを評価してソーティングを行なう。エッジの評価は、具体的には、エッジで結ばれる各画像領域が持つ属性値を比較して比較結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングする。ここで言う画像領域は、最小単位である多角形と、複数の多角形を統合した多角形メッシュとして構成される画像領域を含む。【００８５】
属性値として例えば画像領域が持つ面積（画像領域に統合されたすべての多角形の面積の平均値）を用い、エッジで結ばれる画像領域間の面積の相違をエッジの重み値として与えて、重み値の小さい順（ｉｎｃｒｅａｓｉｎｇ  ｏｒｄｅｒ）にソーティングを行なう。この場合、画像領域間の面積の差が小さいほど重み値は小さくなり、後続の画像統合処理では処理順位が高くなる。【００８６】
図４には、エッジの評価を行なう処理方法を図解している。ここでは、エッジｅijで接する２つの３角形Ｔi及びＴjを想定し、その隣接グラフは、同図右に示すように、各３角形Ｔi及びＴjに相当する２つのノードＮi及びＮjと、両ノードを結ぶエッジｅijで構成される。ここで、多角形Ｐの面積を求める関数ａｒｅａ（Ｐ）が定義されているとすると、エッジｅijの重み値Ｗ（ｅij）は下式によって計算される。【００８７】
【数３】
0004780106.tif 000004
【００８８】
あるいは、画像領域を構成する多角形の面積の他に、画像領域の法線方向、色などの画素属性情報（ＲＧＢのうちの少なくとも１成分の平均色）（但し、テクスチャを持つ多角形メッシュの場合）といった、隣接する頂点が持つさまざまな属性値の差分を用いてエッジの重みを与えることができる。【００８９】
例えば、幅ｗで高さｈからなるＲＧＢカラー画像において、ｉ行ｊ列目の画素のノードをＶi,jとし、その識別情報をＲｅｇＩＤ（Ｖi,j）＝ｉ×ｗ＋ｊとおく。内側の各画素は４つの隣接ノードを持つことになり、エッジの総数ｍは２ｗｈ−ｗ−ｈとなる。そして、ノードＶi,jとＶi’,j’間の重み因子は、例えば以下の式で表すことができる。【００９０】
【数４】
0004780106.tif 000005
【００９１】
画像領域統合処理部３では、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、統合処理（ｍｅｓｈ  ｇｒｏｗｉｎｇ）を行なう。エッジには、エッジで結ばれる画像領域間の類似度の指標となる重みが与えられるので、重みが小さい順に統合処理を行なうことは、類似する画像領域間の統合処理を優先的に実行することに相当する。【００９２】
画像領域統合処理部３では、ソーティングされた順に従って取り出されたエッジで結ばれる画像領域のペアに対し、統計的処理アルゴリズムに基づいて、統合すべきかどうかを判断する。【００９３】
具体的には、エッジの重みが上式（３）に示したように面積情報を基に算出される場合には、エッジで結ばれる２つの画像領域Ｒk及びＲlに関して、以下の統計的アルゴリズムに基づく判断式（Ｐｒｅｄｉｃａｔｅ）を満たすときに、画像領域Ｒk及びＲlを統合すべきと判定する。但し、下式において、画像領域Ｒkは面積Ｓkを持つとともにｎk個の多角形で構成され、画像領域Ｒlは面積Ｓlを持つとともにｎl個の多角形で構成されるものとする。また、Ａは多角形の最大面積とし、Ｑはセグメンテーションの粗さを制御するためのパラメータとする。【００９４】
【数５】
0004780106.tif 000006
【００９５】
上記の判断式は、画像領域を構成する多角形の面積において現れる現象である、統計的な集中不均衡から導き出されるものである。この現象は、統計学の分野では、中心極限定理として一般的である（母集団が任意の分布であるとしても、その母集団からの標本の大きさを増大するならば、標本平均の分布はやがて正規分布へと収束する）。【００９６】
上式の右辺のＱはセグメンテーションの粗さを制御するためのパラメータである。Ｑを大きくとると右辺の値が小さくなり、判断式を満たすのが困難となる結果、画像領域の統合が抑制される。逆に、Ｑを小さい値にすると右辺の値が大きくなり、判断式を容易に満たすようになるので、画像領域の統合が促進され、より粗いメッシュ・セグメンテーション結果を得ることができる。【００９７】
あるいは、エッジの重みが上式（４）に示したようにＲＧＢ色情報を基に算出される場合には、エッジで結ばれる隣接ノードＶi,j及びＶi’,j’に関して、以下の統計的アルゴリズムに基づく判断式（Ｐｒｅｄｉｃａｔｅ）を満たすときにノードを統合すべきと判定する。【００９８】
【数６】
0004780106.tif 000007
【００９９】
但し、上式中の関数ｂ（ｘ）は以下の通りである。【０１００】
【数７】
0004780106.tif 000008
【０１０１】
上式中で、ｎi,j並びにｎi’,j’は該当するノードに含まれる画素数である。また、Ｑはセグメンテーションの粗さを制御するためのパラメータとなる。【０１０２】
ノードは、初期状態では多角形メッシュの最小単位の多角形であるが、画像領域の統合処理が進むと、複数の多角形からなる多角形メッシュで構成される画像領域に成長する。ノード統計情報では、各ノードＮiに関して、一意に識別するための識別情報ｉｄ（Ｎi）と、該当する画像領域（最初は１つの多角形）が持つ面積ａｒｅａ（Ｎi）と、該当する画像領域すなわち多角形メッシュを構成する多角形の個数ｎ（Ｎi）（初期値は１）などを保持するレコードが設けられている。そして、画像領域統合処理部３は、ノード同士を統合したときには、新しいノードを識別するための新たなｉｄが与え、統合により新たに生成された画像領域の面積及び多角形の個数を算出して、ノード統計情報の更新処理を行なう。新たな識別情報の生成には、Ｕｎｉｏｎ−Ｆｉｎｄアルゴリズムを用いることができる（前述）。【０１０３】
微小領域処理部４は、画像領域の統合処理をした結果として残された微細な領域を処理する。例えば、大きな画像領域の間あるいは内部に、統合されないまま残された微小な多角形メッシュを、判断式を満たすか否かに変わらず、隣接するいずれかの画像領域に統合し、処理結果の見栄えを良くする。ここで言う微小領域は、例えばメッシュ表面全体に対して数パーセント未満の面積しかない多角形メッシュである。【０１０４】
図５には、本実施形態に係る画像処理装置１０において、メッシュ・セグメンテーション処理を行なうための処理手順の一例をフローチャートの形式で示している。【０１０５】
まず、画像情報入力部１において、処理対象となる３次元オブジェクトの画像情報を入力する（ステップＳ１）。本実施形態では、画像情報は、多角形をノードとし、多角形の辺をエッジとして構成される隣接グラフの形式で記述される（前述並びに図３を参照のこと）。【０１０６】
画像情報入力部１は、入力された隣接グラフをスキャンして、各ノードＮiに識別情報ｉｄ（Ｎi）を付与するとともに、相当する多角形の面積を求め、ノード毎の識別情報、面積、及び多角形の個数（初期値は１）をノード統計情報に登録（初期化）する。ノード統計情報を初期化する擬似プログラム・コードを以下に示しておく。但し、ｉｄ（）は引数で示されるノードの識別情報を格納する配列であり、ａｒｅａ（）は引数で示される識別情報のノードの面積を格納する配列であり、ｎ（）は引数で示される識別情報のノードを構成する多角形の個数を格納する配列である。【０１０７】
【数８】
0004780106.tif 000009
【０１０８】
隣接グラフからｉ番目に取り出されたノードＮiに関し、識別情報ｉｄ（Ｎi）にｉを代入し、ノードＮiの面積ａｒｅａ（ｉ）に該当する多角形の面積ａｒｅａ（Ｔi）を代入し、多角形の個数ｎ（ｉ）に初期値１を代入する。【０１０９】
次いで、隣接グラフ評価部２では、入力された隣接グラフの各エッジを評価してソーティングを行なう（ステップＳ２）。具体的には、エッジで結ばれる画像領域間の面積の相違をエッジの重み値として与えて、重み値の小さい順にソーティングを行なう。画像領域間の面積の差が小さいほど重み値は小さくなり、後続の画像統合処理では処理順位が高くなる。【０１１０】
続いて、パラメータ設定部５からセグメンテーションの粗さをコントロールするためのパラメータＱを設定する（ステップＳ３）。【０１１１】
画像領域統合処理部３では、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出す（ステップＳ４）。そして、これらの画像領域が統計的アルゴリズムに基づく判断式を満たすかどうかに基づいて統合処理を行なう（ステップＳ５）。ここで用いる判断式は、画像領域を構成する多角形の面積において現れる現象である、統計的な集中不均衡から導き出されるものであり（前述）、ステップＳ３で設定されたパラメータＱを用いる。【０１１２】
ノード統計情報では、各ノードＮiに関して、一意に識別するための識別情報ｉｄ（Ｎi）と、該当する画像領域（最初は１つの多角形）が持つ面積ａｒｅａ（Ｎi）と、該当する画像領域すなわち多角形メッシュを構成する多角形の個数ｎ（Ｎi）（初期値は１）などを保持するレコードが設けられている（前述）。画像領域統合処理部３は、画像領域同士を統合したときには、新しいノードを生成して、このノードを識別するための新たなｉｄを与え、統合により新たに生成された画像領域の面積及び多角形の個数を算出して、ノード統計情報の更新処理を行なう（ステップＳ６）。【０１１３】
画像領域を統合し、その後にノード統計情報を更新する擬似プログラム・コードを以下に示しておく。但し、Ｍｅｒｇｅ（）は、引数で示される各画像領域を統合処理する関数である。【０１１４】
【数９】
0004780106.tif 000010
【０１１５】
まず、Ｍｅｒｇｅ関数の引数で示されるノードＮi及びＮjの統合処理を行なう。そして、各ノードＮi及びＮjに対し同じ新規の識別情報ｉｄ´（Ｎi）＝ｉｄ´（Ｎj）を与えることで、両画像領域が統合され、新しいノードが生成されたことを示す。本実施形態では、新しいノードの識別情報としてＮi又はＮjいずれか一方の旧識別情報を用いる。新しいノードに識別情報を与える際に、Ｒｏｂｅｒｔ  Ｅｎｄｒｅ  Ｔａｒｊａｎが考案したＵｎｉｏｎ−Ｆｉｎｄアルゴリズム（前述）を使用することができる。【０１１６】
続いて、新しいノードの面積ａｒｅａ（ｉｄ´（Ｎi））に元の各画像領域の面積の和ａｒｅａ（Ｎi）＋ａｒｅａ（Ｎj）を代入するとともに、新しいノードの多角形の個数ｎ（ｉｄ´（Ｎi））に元の各画像領域の多角形の個数の和ｎ（ｉｄ（Ｎi））＋ｎ（ｉｄ（Ｎj））を代入する。そして、元の各ノードＮi及びＮjに対し新規の識別情報ｉｄ´（Ｎi）及びｉｄ´（Ｎj）をそれぞれ与えることで、ノード統計情報の更新処理を終える。【０１１７】
そして、隣接グラフ中のすべてのエッジについて処理を終えると（ステップＳ４）、微小領域処理部４は、画像領域の統合処理をした結果として残された微細な領域を処理する（ステップＳ７）。例えば、大きな画像領域の間あるいは内部に、統合されないまま残された微小な多角形メッシュを、判断式を満たすか否かに変わらず、隣接するいずれかの画像領域に統合し、処理結果の見栄えを良くする。ここで言う微小領域は、例えばメッシュ表面全体に対して数パーセント未満の面積しかない多角形メッシュである。【０１１８】
上述したような統計的処理アルゴリズムに基づく画像領域の統合処理は、多角形の面積を統計処理するという簡素な計算で構成されることから高速化が可能である。例えば、一般的な計算機システム（前述）を用いて毎秒百万個程度の多角形を処理することができる。また、判断式に含まれるパラメータ値Ｑを調整することによって、画像領域同士を統合する基準を自在に設定して、所望する粗さの多角形メッシュを生成することができ、システムはスケーラビリティを持つ。【０１１９】
ユーザは、例えばパラメータ設定部５を介してインタラクティブにＱの値を設定することができる。例えば、表示画面上にスライド・バーを用意して、このバー上でＱの入力を行なうようにすることができる。図６には、スライド・バーを用いてユーザが多スケールのパラメータＱを設定したときにインタラクティブに得られるセグメンテーション結果の例を示している。異なるＱを入力すると、画像領域統合処理部３及び微小領域処理部４は、繰り返し処理を行なう必要があるが、その処理時間にはほぼ線形性がある。Ｑを大きくとると右辺の値が小さくなり、判断式を満たすのが困難となる結果、画像領域の統合が抑制される。逆に、Ｑを小さい値にすると右辺の値が大きくなり、判断式を容易に満たすようになるので、画像領域の統合が促進され、より粗いメッシュ・セグメンテーション結果を得ることができる。【０１２０】
ほとんどのメッシュがスキャンされるか又は概ね再メッシュ化されるので、多角形の面積を統計的アルゴリズムに従って処理するだけで高い精度のセグメンテーションを行なうことができる、という点を十分理解されたい。すなわち、メッシュは、法線や曲率といった表面の特性を、暗に多角形の面積に符号化している。前処理段階では、任意のメッシュがこのような条件に適合するように再メッシュ化するようにしてもよい。【０１２１】
ところで、画像領域の統合が進むと（図７を参照のこと）、成長した画像領域はその面積が巨大であるとともに、多角形の個数も大きな値となる。このような場合、隣接する画像領域との統合の正否を判断する上では、境界に近い多角形の情報がより重要であるにも拘らず、画像領域の中央部から余分な影響を受けるという結果に陥る。すなわち、統計的処理アルゴリズムに基づく上記の判断式では正確な境界判定を行なえなくなるという問題がある。【０１２２】
そこで、画像領域の統合を行なったときに、新たに生成された画像領域の「外皮（Ｃｒｕｓｔ）」に相当する領域境界近辺の多角形のみを残して、以降の画像領域の統合についての成否判断を行なうようにしてもよい。この場合、統合して新たに生成される画像領域全体ではなく、“Ｃｒｕｓｔ”に相当する領域についての面積及び多角形の個数を算出してノード統計情報の更新処理を行なう。【０１２３】
「外皮」として、例えば図８に示すように、統合して新たに生成された画像領域の全周に渡る境界近辺の多角形すなわち“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”のみを残して、以降の画像領域統合処理を行なうようにすることができる。この“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”を残す際に発生するノード統計情報の更新処理は比較的計算量が少なく、且つ以降の画像領域の統合についての成否判断を正確にすることができる。【０１２４】
図９には、“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”のみを残したメッシュ・セグメンテーション処理を行なうための処理手順をフローチャートの形式で示している。【０１２５】
まず、画像情報入力部１において、処理対象となる３次元オブジェクトの画像情報を入力する（ステップＳ１１）。画像情報は、多角形をノードとし、多角形の辺をエッジとして構成される隣接グラフの形式で記述される（前述並びに図３を参照のこと）。【０１２６】
画像情報入力部１は、入力された隣接グラフをスキャンして、各ノードＮiに識別情報ｉｄ（Ｎi）を付与するとともに、相当する多角形の面積を求め、ノード毎の識別情報、面積、及び多角形の個数（初期値は１）をノード統計情報に登録（初期化）する。ノード統計情報の初期化処理は図５で説明した場合と同様なので、ここでは説明を省略する。【０１２７】
次いで、隣接グラフ評価部２では、入力された隣接グラフの各エッジを評価してソーティングを行なう（ステップＳ１２）。具体的には、エッジで結ばれる画像領域間の面積の相違をエッジの重み値として与えて、重み値の小さい順にソーティングを行なう。【０１２８】
続いて、パラメータ設定部５を介して、セグメンテーションの粗さをコントロールするためのパラメータＱを設定する（ステップＳ１３）。【０１２９】
画像領域統合処理部３では、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出す（ステップＳ１４）。そして、これらの画像領域が統計的アルゴリズムに基づく判断式を満たすかどうかに基づいて統合処理を行なう（ステップＳ１５）。ここで用いる判断式は、画像領域を構成する多角形の面積において現れる現象である、統計的な集中不均衡から導き出されるものであり（前述）、ステップＳ１３で設定されたパラメータＱを用いる。【０１３０】
画像領域統合処理部３は、画像領域同士を統合したときには、新しいノードを生成して、このノードを識別するための新たなｉｄを与え、統合により新たに生成された画像領域の面積及び多角形の個数を算出して、ノード統計情報の更新処理を行なう（ステップＳ１６）。【０１３１】
“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”のみを残して画像領域を統合し、その後にノード統計情報を更新する擬似プログラム・コードを以下に示しておく。但し、Ｍｅｒｇｅ（）は引数で示される各画像領域を統合処理する関数、Ｅｘｔｒａｃｔ（）は引数で示される識別情報に対応する画像領域を抽出する関数、Ｃｒｅａｔｅ  Ｃｒｕｓｔ（）は引数で示される複数の領域の“Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔ”のみを残す処理を行なうための関数である。【０１３２】
【数１０】
0004780106.tif 000011
【０１３３】
まず、Ｍｅｒｇｅ関数の引数で示されるノードＮi及びＮjの統合処理を行なう。そして、各ノードＮi及びＮjに対応する画像領域Ｒi及びＲjを、それぞれ関数Ｅｘｔｒａｃｔを用いて取り出す。但し、画像領域Ｒiは同じノード識別情報ｉｄ（Ｎi）を持つすべてのノードＮlとする（すなわち、Ｒi＝｛Ｎl｜ｉｄ（Ｎl）＝ｉｄ（Ｎi）｝）。【０１３４】
次いで、関数Ｃｒｅａｔｅ  Ｃｒｕｓｔを用いて、これらの画像領域の和集合Ｒi∪Ｒｊに対するＣｉｒｃｌｅ  Ｃｒｕｓｔを生成する。この処理は、画像領域に対しｍｏｒｐｈｏｌｏｇｙなどの処理を適用することで実現する。【０１３５】
そして、得られた画像領域Ｃｒｕｓｔ（Ｒi∪Ｒj）について、面積ａｒｅａ（Ｃｒｕｓｔ（Ｒi∪Ｒj））と、領域を構成する多角形の数ｎ（Ｃｒｕｓｔ（Ｒi∪Ｒj））を求める。【０１３６】
次いで、元の各ノードＮi及びＮjに対し同じ新規の識別情報ｉｄ´（Ｎi）＝ｉｄ´（Ｎj）を与えることで、両画像領域が統合され、新しいノードが生成されたことを示す。新しいノードに識別情報を与える際に、Ｒｏｂｅｒｔ  Ｅｎｄｒｅ  Ｔａｒｊａｎが考案したＵｎｉｏｎ−Ｆｉｎｄアルゴリズム（前述）を使用することができる。【０１３７】
続いて、新しいノードの面積ａｒｅａ（ｉｄ´（Ｎi））に、先に求めたａｒｅａ（Ｃｒｕｓｔ（Ｒi∪Ｒｊ））を代入する。また、新しいノードの多角形の個数ｎ（ｉｄ´（Ｎi））にｎ（Ｃｒｕｓｔ（Ｒi∪Ｒj））を代入する。そして、各ノードＮi及びＮjに対し新規の識別情報ｉｄ´（Ｎi）及びｉｄ´（Ｎj）をそれぞれ与えることで、ノード統計情報の更新処理を終える。【０１３８】
そして、隣接グラフ中のすべてのエッジについて処理を終えると（ステップＳ１４）、微小領域処理部４は、画像領域の統合処理をした結果として残された微細な領域を処理する（ステップＳ１７）。例えば、大きな画像領域の間あるいは内部に、統合されないまま残された微小な多角形メッシュを、判断式を満たすか否かに変わらず、隣接するいずれかの画像領域に統合し、処理結果の見栄えを良くする。ここで言う微小領域は、例えばメッシュ表面全体に対して数パーセント未満の面積しかない多角形メッシュである。【０１３９】
また、「外皮」として、図１０に示すように、統合しようとする各画像領域が接する境界近辺の多角形すなわち“Ｂｏｒｄｅｒ  Ｃｒｕｓｔ”のみを残して、以降の画像領域統合処理を行なうようにしてもよい。このＢｏｒｄｅｒ  Ｃｒｕｓｔを用いることにより、Ｃｉｒｃｕｌａｒ  Ｃｒｕｓｔを用いた場合よりもより正確に以降の画像領域の統合についての成否判断を行なうことができる。但し、Ｂｏｒｄｅｒ  Ｃｒｕｓｔを用いる場合には、ノード統計情報だけではなく、隣接グラフも更新しなければならないので、その計算量は膨大となる。【０１４０】
図１１には、“Ｂｏｒｄｅｒ  Ｃｒｕｓｔ”のみを残したメッシュ・セグメンテーション処理を行なうための処理手順をフローチャートの形式で示している。【０１４１】
まず、画像情報入力部１において、処理対象となる３次元オブジェクトの画像情報を入力する（ステップＳ２１）。画像情報は、多角形をノードとし、多角形の辺をエッジとして構成される隣接グラフの形式で記述される（前述並びに図３を参照のこと）。【０１４２】
画像情報入力部１は、入力された隣接グラフをスキャンして、各ノードＮiに識別情報ｉｄ（Ｎi）を付与するとともに、相当する多角形の面積を求め、ノード毎の識別情報、面積、及び多角形の個数（初期値は１）をノード統計情報に登録（初期化）する。ノード統計情報の初期化処理は図５で説明した場合と同様なので、ここでは説明を省略する。【０１４３】
次いで、隣接グラフ評価部２では、入力された隣接グラフの各エッジを評価してソーティングを行なう（ステップＳ２２）。具体的には、エッジで結ばれる画像領域間の面積の相違をエッジの重み値として与えて、重み値の小さい順（ｉｎｃｒｅａｓｉｎｇ  ｏｒｄｅｒ）にソーティングを行なう。【０１４４】
続いて、パラメータ設定部５を介して、セグメンテーションの粗さをコントロールするためのパラメータＱを設定する（ステップＳ２３）。【０１４５】
画像領域統合処理部３では、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出す（ステップＳ２４）。そして、これらの画像領域が統計的アルゴリズムに基づく判断式を満たすかどうかに基づいて統合処理を行なう（ステップＳ２５）。ここで用いる判断式は、画像領域を構成する多角形の面積において現れる現象である、統計的な集中不均衡から導き出されるものであり（前述）、ステップＳ２３で設定されたパラメータＱを用いる。【０１４６】
画像領域統合処理部３は、画像領域同士を統合したときには、新しいノードを生成して、このノードを識別するための新たなｉｄを与え、統合により新たに生成された画像領域の面積及び多角形の個数を算出して、ノード統計情報の更新処理を行なう（ステップＳ２６）。【０１４７】
“Ｂｏｒｄｅｒ  Ｃｒｕｓｔ”のみを残して画像領域を統合し、その後にノード統計情報を更新する擬似プログラム・コードを以下に示しておく。但し、Ｍｅｒｇｅ（）は引数で示される各画像領域を統合処理する関数、Ｅｘｔｒａｃｔ  Ｂｏｕｎｄａｒｙ（）は引数で示される識別情報に対応する各画像領域間の境界を抽出する関数、Ｃｒｅａｔｅ  Ｃｒｕｓｔ（）は引数で示される複数の領域の“Ｂｏｒｄｅｒ  Ｃｒｕｓｔ”のみを残す処理を行なうための関数である。【０１４８】
【数１１】
0004780106.tif 000012
【０１４９】
まず、Ｍｅｒｇｅ関数の引数で示されるノードＮi及びＮjの統合処理を行なう。そして、ノードＮiの画像領域ＲiのうちノードＮjの画像領域に接する境界と、ノードＮjの画像領域ＲjのうちノードＮiの画像領域に接する境界を、それぞれ関数Ｅｘｔｒａｃｔ  Ｂｏｕｎｄａｒｙを用いて取り出す。【０１５０】
次いで、関数Ｃｒｅａｔｅ  Ｃｒｕｓｔを用いて、これらの画像領域の和集合Ｒi∪ＲjについてのＢｏｒｄｅｒ  Ｃｒｕｓｔを生成する。この処理は、一方の画像領域Ｒiから画像領域Ｒjと接する境界部分から一定の幅（画素数）の領域Ｂiを切り取るとともに、他方の画像領域Ｒjから画像領域Ｒiと接する境界部分から一定の幅（画素数）の領域Ｂjを切り取り、これら切り取られた画像領域の和集合Ｂi∪Ｂjを生成することに相当する（図１２を参照のこと）。【０１５１】
そして、得られた画像領域Ｂi∪Ｂjについて、面積ａｒｅａ（Ｂi∪Ｂj）と、領域を構成する多角形の数ｎ（Ｂi∪Ｂj）を求める。【０１５２】
次いで、各ノードＮi及びＮjに対し同じ新規の識別情報ｉｄ´（Ｎi）＝ｉｄ´（Ｎj）を与えることで、両画像領域が統合され、新しいノードが生成されたことを示す。新しいノードに識別情報を与える際に、Ｒｏｂｅｒｔ  Ｅｎｄｒｅ  Ｔａｒｊａｎが考案したＵｎｉｏｎ−Ｆｉｎｄアルゴリズム（前述）を使用することができる。【０１５３】
続いて、新しいノードの面積ａｒｅａ（ｉｄ´（Ｎi））に、先に求めたａｒｅａ（Ｂi∪Ｂj）を代入する。また、新しいノードの多角形の個数ｎ（ｉｄ´（Ｎi））にｎ（Ｂi∪Ｂj）を代入する。そして、各ノードＮi及びＮjに対し新規の識別情報ｉｄ´（Ｎi）及びｉｄ´（Ｎj）をそれぞれ与えることで、ノード統計情報の更新処理を終える。【０１５４】
続いて、画像領域統合処理部３は、隣接グラフの更新処理を行なう（ステップＳ２７）。すなわち、隣接グラフに含まれるエッジの重み因子を再計算して、重み値の大きさによりエッジを再ソーティングする。そして、ステップＳ２４に復帰して、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、統計的処理アルゴリズムに基づく画像領域の統合処理を繰り返し行なう。【０１５５】
まず、Ｂｏｒｄｅｒ  Ｃｒｕｓｔを生成する処理対象となった画像領域Ｒi及びＲjのそれぞれに隣接するすべての画像領域Ｒlの識別情報ｉｄ（Ｎl）を探索する。そして、見つけ出された画像領域に相当するノードＮlと各処理対象ノードＮiとＮjとのエッジｅil、ｅjlがあれば、これらの重みを再計算する。【０１５６】
図１３には、隣接グラフを更新する様子を図解している。図示の例ではＢｏｒｄｅｒ  Ｃｒｕｓｔを生成する処理対象となった画像領域Ｒi及びＲjのそれぞれに隣接する画像領域として、Ｒiに隣接するＲl、及びＲjに隣接するＲkが発見されたとする。この場合、以下の式に基づいて各エッジｅil及びｅjkの各重みＷ（ｅil）及びＷ（ｅjk）を計算する。【０１５７】
【数１２】
0004780106.tif 000013
【０１５８】
このような画像領域の統合と、統合に伴うノード統計情報の更新処理を再帰的に繰り返していくと、やがてパラメータＱで閾値が設定される判断式を満たす画像領域の組み合わせが見つからなくなる。すなわち、隣接グラフ中に未処理のエッジがなくなると（ステップＳ２４のＮｏ）、微小領域処理部４は、画像領域の統合処理をした結果として残された微細な領域を処理する（ステップＳ２８）。例えば、大きな画像領域の間あるいは内部に、統合されないまま残された微小な多角形メッシュを、判断式を満たすか否かに変わらず、隣接するいずれかの画像領域に統合し、処理結果の見栄えを良くする。ここで言う微小領域は、例えばメッシュ表面全体に対して数パーセント未満の面積しかない多角形メッシュである。【０１５９】
なお、画像領域統合処理部３で使用する判断式（前述）は、セグメンテーションの粗さを制御するためのパラメータＱを含んでいるので、所望のセグメンテーションの粗さが得られるようなパラメータＱの値をパラメータ設定部５から与えることができる。また、ユーザから所望するセグメンテーションの粗さが与えられたときに、パラメータ設定部５は、該当するパラメータＱの値に変換してシステムに与えるようにしてもよい。ユーザは、メッシュ・セグメンテーションを行なう際に画像領域数を与えることができるとともに、統計的処理アルゴリズムに基づく画像領域の統合処理は高速であることから、画像領域数を動的すなわち自在に変更することができる。このような柔軟なパラメータＱの設定を行なうことにより、プログレッシブなメッシュ・セグメンテーションを実現することができ、さまざまなインタラクティブ・アプリケーションに適用し易くなる。【０１６０】
例えば、Ｑをある省略時値に設定してメッシュ・セグメンテーション処理を行なった結果を画面表示すると、元の３次元オブジェクトがＮ個の画像領域に分割されていたとする。この処理結果に対し、ユーザから「Ｍ個の領域に分割した結果が欲しい」という反応があった場合には、パラメータ設定部５は、画像領域がＭ個になるようなＱの値を求め、これを画像領域統合処理部３に与えて、メッシュ・セグメンテーション処理を再実行する。勿論、逐次的に変換処理を演算するのではなく、Ｑ値への変換早見表を用意しておいてもよい。【０１６１】
本実施形態に係る画像処理装置１０によれば、パラメータ設定部５により複数のＱを連続して入力することにより、プログレッシブなメッシュ・セグメンテーションを行なうとともに、階層化セグメンテーションを実現することができる。統計的処理アルゴリズムに基づく画像領域の統合処理は高速であることから、メッシュ・セグメンテーションを行なう際に、ユーザは、画像領域数を動的すなわち自在に変更することができる。【０１６２】
本発明者は、階層化セグメンテーションの１つのアプリケーションとして、画像検索（ｓｈａｐｅ  ｍａｔｃｈｉｎｇ）を考えている。例えば、セグメント化された画像領域毎にキーワードを設けて、画像検索を行なうことができる（例えば、“Ｍｏｄｅｌｉｎｇ  ｂｙ  ｅｘａｍｐｌｅ”（Ｉｎ  Ｐｒｏｃ．ＳＩＧＧＲＡＰＨ（２００４）  Ｖｏｌ．２３，  Ｉｓｓｕｅ３，ｐｐ．６５２−６６３）を参照のこと）。【０１６３】
本発明によれば、メッシュ・セグメンテーションの階層毎にキーワードの付与を行なうことで、元の３次元オブジェクトのイメージに対し、階層構造のキーワード情報を構築することができる。このような場合、同じ３次元オブジェクトに対して検索すなわちｓｈａｐｅ  ｍａｔｃｈｉｎｇを適用しても、階層毎に異なる検索結果を得ることができる。あるいは、所望の検索結果が得られるようにパラメータ設定部５においてＱの値を制御することができる。【０１６４】
ここで重要なのは、統計的処理アルゴリズムに基づく画像領域の統合処理は高速であることから、メッシュ・セグメンテーションを行なう際に画像領域数を動的すなわち自在に変更することができる、という点である。すなわち、ユーザは、検索結果に応じて、パラメータ設定部５を介してＱ値を再設定するという操作だけですぐにパーツ数を自由に変えることが可能であり、それによって検索結果の類似度コントロールを自在に操作することができる。【０１６５】
画面上にスライド・バーを設け、ユーザがスライダを移動した位置に応じてパラメータ設定部５がＱ値を読み取るという実現形態が考えられる（前述）。図１４〜図１６には、メッシュ・セグメンテーション時に、スライド・バーの操作を介してＱ値を設定して分割する画像領域数を調整する様子を示している。図１４に示すように、紙面左側のスライド・バー上で比較的高いＱ値を設定すると、画像領域の統合は抑制され、画像領域数は多い、すなわち小さなセグメントが多くなる。同図では、紙面右上に表示されているように、統合された領域数は１１６である。他方、図１５並びに図１６に示すように、スライド・バー上で比較的高いＱ値を設定すると、画像領域の統合は促進され、画像領域数は少ない、すなわち比較的大きなセグメントが多くなる。同図では、紙面右上に表示されているように、統合された領域数は１０である。統計的処理アルゴリズムに基づく画像領域の統合処理は高速であることから、このようなスライド・バーの操作に応じて、システムはすぐに画像領域数の異なるメッシュ・セグメンテーション結果を求め、ユーザに提示することができる。すなわち、ユーザは、画像領域数を動的すなわち自在に変更することができる。
【産業上の利用可能性】
【０１６６】
以上、特定の実施形態を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施形態の修正や代用を成し得ることは自明である。【０１６７】
本発明に係るメッシュ・セグメンテーション処理は、画像領域同士を統合する基準を自在に設定して、所望する粗さの多角形メッシュを生成することができ、システムはスケーラビリティを持ち、パラメタリゼーション及びテクスチャ・マッピング、画像変形（ｍｏｒｐｈｉｎｇ）、多解像度モデリング、画像編集、画像圧縮、アニメーション、並びに形状マッチングなど、さまざまなインタラクティブ・アプリケーションに適用することができる。【０１６８】
要するに、例示という形態で本発明を開示してきたのであり、本明細書の記載内容を限定的に解釈するべきではない。本発明の要旨を判断するためには、請求の範囲の記載を参酌すべきである。
【図１】
0004780106.tif 000015
【図２】
0004780106.tif 000016
【図３】
0004780106.tif 000017
【図４】
0004780106.tif 000018
【図５】
0004780106.tif 000019
【図９】
0004780106.tif 000020
【図１１】
0004780106.tif 000021
【図１２】
0004780106.tif 000022
【図１３】
0004780106.tif 000023
【図１７】
0004780106.tif 000024
【図１８】
0004780106.tif 000025
【図１９】
0004780106.tif 000026
【図６】
0004780106.tif 000027
【図７】
0004780106.tif 000028
【図８】
0004780106.tif 000029
【図１０】
0004780106.tif 000030
【図１４】
0004780106.tif 000031
【図１５】
0004780106.tif 000032
【図１６】
0004780106.tif 000033