(57)【要約】【課題】  ノイズを取り除くと共に実物の元の形状の特徴を表すポリゴン頂点が平滑化されないようにし、且つ、フィルタリング処理に用いられる数学演算式の繰り返し演算を自動的に停止させることを可能にしたアダプティブ・スムージング・フィルタリング装置を提供する。【解決手段】  実物の３次元物体をモデリングして得られた３Ｄモデルに含まれているノイズをフィルタリング処理によって除去し、且つ、フィルタリング処理後の前記３Ｄモデルは、平滑な表面が得られると共に、前記実物の３次元物体の形状を忠実に保つことを可能にしたアダプティブ・スムージング・フィルタリング装置であって、前記ノイズを除去するため、熱拡散方程式の数値繰り返し式に基づいて演算する第１の手段と、曲率を熱エネルギーとして、熱伝導係数を決定する第２の手段と、熱エネルギー分布が熱平衡状態に達した時点で、前記フィルタリング処理の結果を決定する第３の手段とを備える。【選択図】  図１
2005216219.tif 000002
【特許請求の範囲】
【請求項１】
実物の３次元物体をモデリングして得られた３Ｄモデルに含まれているノイズをフィルタリング処理によって除去し、且つ、フィルタリング処理後の前記３Ｄモデルは、平滑な表面が得られると共に、前記実物の３次元物体の形状を忠実に保つことを可能にしたアダプティブ・スムージング・フィルタリング装置であって、
前記ノイズを除去するため、熱拡散方程式（Diffusion  Heat  Equation）の数値繰り返し式に基づいて演算する第１の手段と、
曲率を熱エネルギーとして、熱伝導係数を決定する第２の手段と、
熱エネルギー分布が熱平衡状態に達した時点で、前記フィルタリング処理の結果を決定する第３の手段と、
を備えることを特徴とするアダプティブ・スムージング・フィルタリング装置。
【請求項２】
前記３Ｄモデルは、前記実物の３次元物体の形状に近づける、複数の三角ポリゴン・パッチから構成される３Ｄポリゴン・モデルであり、
前記第１の手段を用いて前記ノイズを除去する演算過程において、前記３Ｄポリゴン・モデルのポリゴン頂点の位置を温度とみなし、また、前記ポリゴン頂点の曲率を熱エネルギーとみなす請求項１に記載のアダプティブ・スムージング・フィルタリング装置。
【請求項３】
前記熱拡散方程式として、表面熱拡散方程式（Thin  Plate  Heat  Equation）の数値繰り返し式（Numerical  Iteration  Formula）を用い、
前記表面熱拡散方程式の数値繰り返し式に基づいて、熱エネルギー拡散を算出する熱エネルギー拡散算出手段を備え、
前記熱エネルギー拡散算出手段は、
次の繰り返し式を用いて、瞬間熱エネルギー拡散を算出する第４の手段と、
2005216219.tif 000012
（ただし、ｗ（ｋ１，ｋ２）は熱伝導係数で、∇2cは平均曲率フロー演算子（mean  curvature  flow  operator）で、ＭｔとＭｔ+１はそれぞれｔ回目及びｔ+１回目の繰り返し演算後のポリゴン頂点を表す。）
ポリゴンの法線ベクトル方向に沿って、ポリゴン頂点を新たな位置に移動させる第５の手段とから構成される請求項２に記載のアダプティブ・スムージング・フィルタリング装置。
【請求項４】
前記第２の手段は、
各ポリゴン頂点の互いに垂直する２つの曲率の値を決定する手段と、
各ポリゴン頂点を特徴頂点と非特徴頂点に分類する頂点分類手段と、
各ポリゴン頂点の分類によって当該ポリゴン頂点の熱伝導係数を決定する手段とから構成される請求項３に記載のアダプティブ・スムージング・フィルタリング装置。
【請求項５】
前記第５の手段は、
ポリゴン頂点の平均曲率とポリゴン頂点の熱伝導係数との積をオフセット・ベクトルとする手段と、
法線ベクトル方向に沿って拡散熱エネルギのオフセット・ベクトルを算出する手段と、
スタート・ベクトルに前記オフセット・ベクトルを足したものをポリゴン頂点の新たな位置とする手段とから構成される請求項３に記載のアダプティブ・スムージング・フィルタリング装置。
【請求項６】
さらに、前記頂点分類手段は、
各ポリゴン頂点の最大曲率値の実数系における順番によって、全てのポリゴン頂点を２つの正規分布領域に分ける正規分布領域分け手段と、
前記正規分布領域分け手段で分けられた２つの正規分布領域の分散（variance）の重畳程度によって、２つの領域に分けるか、または、１つの領域を維持するかを決定する領域決定手段と、
前記領域決定手段で２つの領域に分けると決定された場合に、ベイズ分類法を用いて判別境界線（Discriminant  Boundary  Line）を見つけ、前記判別境界線の両側にそれぞれ１つの領域を形成し、左側の領域に入るポリゴン頂点を非特徴頂点と分類し、右側の領域に入るポリゴン頂点を特徴頂点と分類する領域分け手段と、
前記領域決定手段で１つの領域を維持すると決定された場合に、全てのポリゴン頂点の熱伝導係数を１（つまり、完全熱導体）に設定する熱導体設定手段と、
前記領域分け手段で２つの領域に分けた後に、非特徴頂点と分類されたポリゴン頂点の熱伝導係数を１に設定し、また、特徴頂点と分類されたポリゴン頂点の熱伝導係数を０と１の間の値（つまり、熱半導体）に設定する熱半導体設定手段から構成される請求項４に記載のアダプティブ・スムージング・フィルタリング装置。
【請求項７】
前記正規分布領域分け手段は、k-mean演算法を採用する手段を更に含む請求項６に記載のアダプティブ・スムージング・フィルタリング装置。
【請求項８】
前記熱半導体設定手段は、更に
2005216219.tif 000013
（ただし、ｗ(ｋ１,ｋ２)はポリゴン頂点の熱伝導係数で、Ｔはベイズ分類法の最適な判別境界線の閾値で、ｋ１はポリゴン頂点の最大曲率値で、ｋ２はポリゴン頂点の最小曲率値である。）を計算基礎とする手段を含む請求項６に記載のアダプティブ・スムージング・フィルタリング装置。
【請求項９】
実物の３次元物体をモデリングして得られた３Ｄポリゴン・モデルに含まれているノイズをフィルタリング処理によって除去し、且つ、フィルタリング処理後の前記３Ｄポリゴン・モデルは、平滑な表面が得られると共に、前記実物の３次元物体の形状を忠実に保つことを可能にしたアダプティブ・スムージング・フィルタリング方法であって、
前記ノイズを除去するため、熱拡散方程式（Diffusion  Heat  Equation）の数値繰り返し式に基づいて演算する第１のステップと、
ポリゴン頂点の位置を温度とみなし、ポリゴン頂点の曲率を熱エネルギーとみなし、繰り返し式の中の熱エネルギー分布を分析することによって、ポリゴン頂点の熱伝導係数を決定する第２のステップと、
各繰り返し演算後にポリゴン頂点の新たな位置を決定する第３のステップと、
繰り返し演算の停止のタイミングを決定し、平滑化されたポリゴン・モデルを得る第４のステップと、
を含むことを特徴とするアダプティブ・スムージング・フィルタリング方法。
【請求項１０】
前記第４のステップにおいて、ポリゴン頂点が非特徴頂点に属する場合に、２つの曲率の値の総和を熱エネルギーとし、また、ポリゴン頂点が特徴頂点に属する場合に、最小の曲率の値を熱エネルギーとするようにポリゴン頂点の熱エネルギーを算出し、また、平衡熱エネルギー値を設定し、ポリゴン頂点の熱エネルギー或いは熱エネルギーの変化が前記平衡熱エネルギー値より小さい時に、繰り返し演算を停止するようにする請求項９に記載のアダプティブ・スムージング・フィルタリング方法。
【請求項１１】
実物の３次元物体を３Ｄスキャナでスキャンニングして得られた３Ｄポリゴン・モデルのノイズを除去し、且つ、平滑な表面が得られると共に前記実物の３次元物体の形状を忠実に保つことを可能にしたアダプティブ・スムージング・フィルタリング装置を制御するコンピュータに、
前記３Ｄポリゴン・モデルを入力とする第１のステップと、
入力された前記３Ｄポリゴン・モデルのポリゴン頂点の曲率を算出する第２のステップと、
算出されたポリゴン頂点の曲率の分布を算出する第３のステップと、
ポリゴン頂点の属性を分類する第４のステップと、
分類されたポリゴン頂点の属性によって、ポリゴン頂点の熱伝導係数を算出する第５のステップと、
ポリゴン頂点の新たな位置を計算する第６のステップと、
第１のステップから第５のステップまでの繰り返し演算を停止するタイミングを算出する第７のステップと、
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノイズを含んでいる３Ｄポリゴン・メッシュ・モデルを平滑化（スムージング化）するためのアダプティブ・スムージング・フィルタリング装置及びフィルタリング方法に関するものである。
【背景技術】
【０００２】
一般的に、３次元ポリゴン・メッシュ・モデル（３Ｄ  polygon  meshes、３Ｄポリゴン・モデルとも称する）の平滑化問題は、実物の３次元物体の形状データを収集する際に発生する。例えば、３次元レーザ・スキャナを用いて、実物の３次元物体の表面３次元座標データを取得する際に、通常、得られたポリゴン頂点（polygon  vertex、単に頂点とも称する）にノイズを含んでいるので、３Ｄポリゴン・モデルの表面がギザギザになっている現象が生じてしまう。そのために、ノイズ頂点（単にノイズとも称する）を取り除く有効な処理方法が必要になる。このような処理方法によって、処理後の３Ｄポリゴン・モデルの形状は実物の３次元物体の形状と一致するようになる。
【０００３】
一般的に、フィルタを用いることによって、３Ｄポリゴン・モデルの平滑化問題が解決される。このフィルタの設計ポイントとしては、３次元空間におけるポリゴン頂点の位置を調整し直すことである。従来、ポリゴン頂点の位置を調整する方法としては、ポリゴンの法線ベクトル方向（normal  direction）に沿って、ポリゴン頂点を移動させ、移動後のポリゴン頂点の位置と実物の３次元物体上の位置とを一致させるようにしている。換言すれば、良質のフィルタは、異なるポリゴン頂点に対して正確な移動をさせることによって、３Ｄポリゴン・モデルのギザギザな表面を引き起こすポリゴン頂点が平滑化されると共に、実物の元の形状の細部を表すポリゴン頂点（例えば、エッジ頂点（edge  vertex）やコーナー頂点（corner  vertex））が保留される。
【０００４】
フィルタの設計には、ポリゴン頂点の移動量を決定するための数学演算式が必要になる。例えば、従来の演算式は、ガウス演算子（Gaussian  operator）を用いることで高周波ノイズ信号をフィルタリングすることによって、３Ｄポリゴン・モデルを平滑化する。その具体的な方法としては、各頂点及びその周りの頂点のガウス平均値を該頂点の新たな位置とする。この方法は、ノイズ頂点を取り除くのに非常に有効であるが、実物の元の形状の細部を表す頂点も平滑化されてしまう問題が生じる。例えば、元々は直角でつながった２つの平面はこのような方法によって直角がなくなり、円弧（つまり、全体的に見れば緩い曲面）で２つの平面がつながるようになる。
【０００５】
３Ｄポリゴン・モデルの平滑化処理の過程において、実物の元の形状を表すポリゴン頂点を残すために、フィルタに用いられる数学演算式としての微分方程式の数値表示式を解くこと、及び予め設定されたいくつかの条件を満たすようにすることによって、ポリゴン頂点を逐次移動する。例えば、ポリゴンの曲率変化に関する微分方程式を用いることによって、ポリゴン頂点の属性を決定するようにし、曲率変化の大きいポリゴン頂点を緩やかに移動させ、逆に、曲率変化の小さいポリゴン頂点を速やかに移動させるようにする。従って、微分方程式の数値表示式を解くための繰り返し過程において、実物の元の形状の細部を表すポリゴン頂点が繰り返し過程の進行に伴って平滑化されないようにすると共に、ノイズに属するポリゴン頂点（つまり、ノイズ頂点）は繰り返し過程の進行に伴って平滑化されるようにすることができる。
【０００６】
例えば、非特許文献１に記載され、コブベルトらに提唱された『離散フェアリング技術（discrete  fairing  technique）』がある。コブベルトらは表面熱エネルギー関数（Thin  plate  energy  function）と一緒にアンブレラ・アルゴリズム（umbrella  algorithm）を用いて繰り返し式を導いて、彼らのフィルタを設計した。しかしながら、彼らは、繰り返しプロセスの中で、各頂点の移動に固定の重み係数を使用した。よく知られているように、フィルタリング処理に基づいた、３Ｄポリゴン・モデルの平滑化処理は、局所微細構造も与えられた３Ｄポリゴン・モデルに含まれているノイズも強く依存する。したがって、上述したように、ポリゴン頂点のタイプと異なるポリゴン頂点の異なる重み係数とを考慮せずに設計されたスムージング・アルゴリズムは、不要な切子面（facet）を生成してしまうといった問題があった。
【非特許文献１】エル・コベルト（L.  Kobbelt）,エス・カンパグナ（S.  Campagna）,ティー・ボーダッツ（T.  Vorsatz）,エイチ・ピィー・セイデル（H.P.Seidel）共著、「インターラクティブ・マルチリゾルーション・モデリング・オン・アービタリー・メッシュ」（‘Interactive  multiresolution  modeling  on  arbitrary  meshes’）、エスアイジーグラフ９８  コンファランス  プロシーイング（SIGGRAPH’98  Conference  Proceeings）、ｐ.105−114,1998年
【発明の開示】
【発明が解決しようとする課題】
【０００７】
このように、上述したスムージング・フィルタの設計方法は、大まかに等方性拡散（Isotropic  Diffusion）方法（図１１（Ａ）参照）と異方性拡散（Anisotropic  Diffusion）方法（図１１（Ｂ）参照）とに分けることができる。ガウス演算子を採用するフィルタの設計方法は、等方性拡散方法に分類される。一方、ポリゴンの曲率変化を演算子としたフィルタの設計方法は、異方性拡散方法に分類される。この２種類の方法に次の共通な欠点が存在する。
【０００８】
つまり、まず、実物の元の形状を再現することができない。ノイズを取り除くと共に、実物の元の形状の特徴を表すポリゴン頂点（特徴頂点とも称する）も同時に平滑化されてしまうといった問題が生じる。次に、フィルタに用いられる数学演算式の繰り返し演算を停止させるタイミングが分からないので、過度の繰り返し演算によって、３Ｄポリゴン・モデルに表現される実物の形状は歪んだり、変形してしまうといった問題が生じる。
【０００９】
従って、一番望ましいフィルタの設計方法として、まず、ノイズを取り除くと共に、実物の元の形状の特徴を表すポリゴン頂点は平滑化されないようにすることである。次に、フィルタに用いられる数学演算式の繰り返し演算を停止させるタイミングを自動的に知ることができることである。つまり、理想なフィルタの設計方法は、人工知能型のデータ分析をする演算法を有するもので、該演算法は、繰り返しステップ毎に、ポリゴン頂点毎に行う処理は、等方性拡散或いは異方性拡散のどれかが分かるので、繰り返し過程の進行に伴って、実物の元の形状の細部を表すポリゴン頂点を安定な状態にしたまま、また、同時に、ノイズを発生するポリゴン頂点を平滑化される状態にすることができる。ここで、このような人工知能型のフィルタをアダプティブ・フィルタと称する。
【００１０】
本発明は、上述のような事情よりなされたものであり、本発明の目的は、ノイズを取り除くと共に実物の元の形状の特徴を表すポリゴン頂点が平滑化されないようにし、且つ、フィルタリング処理に用いられる数学演算式の繰り返し演算を自動的に停止させることを可能にしたアダプティブ・スムージング・フィルタリング装置及びフィルタリング方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明は、ノイズを含んでいる３Ｄポリゴン・メッシュ・モデルを平滑化するためのアダプティブ・スムージング・フィルタリング装置に関し、本発明の上記目的は、実物の３次元物体をモデリングして得られた３Ｄモデルに含まれているノイズをフィルタリング処理によって除去し、且つ、フィルタリング処理後の前記３Ｄモデルは、平滑な表面が得られると共に、前記実物の３次元物体の形状を忠実に保つことを可能にしたアダプティブ・スムージング・フィルタリング装置であって、前記ノイズを除去するため、熱拡散方程式（Diffusion  Heat  Equation）の数値繰り返し式に基づいて演算する第１の手段と、曲率を熱エネルギーとして、熱伝導係数を決定する第２の手段と、熱エネルギー分布が熱平衡状態に達した時点で、前記フィルタリング処理の結果を決定する第３の手段とを備えることにより、或いは、前記３Ｄモデルは、前記実物の３次元物体の形状に近づける、複数の三角ポリゴン・パッチから構成される３Ｄポリゴン・モデルであり、前記第１の手段を用いて前記ノイズを除去する演算過程において、前記３Ｄポリゴン・モデルのポリゴン頂点の位置を温度とみなし、また、前記ポリゴン頂点の曲率を熱エネルギーとみなすようにすることにより、或いは、前記熱拡散方程式として、表面熱拡散方程式（Thin  Plate  Heat  Equation）の数値繰り返し式（Numerical  Iteration  Formula）を用い、前記表面熱拡散方程式の数値繰り返し式に基づいて、熱エネルギー拡散を算出する熱エネルギー拡散算出手段を備え、前記熱エネルギー拡散算出手段は、次の繰り返し式を用いて、瞬間熱エネルギー拡散を算出する第４の手段と、
2005216219.tif 000003
（ただし、ｗ（ｋ１，ｋ２）は熱伝導係数で、∇2cは平均曲率フロー演算子（mean  curvature  flow  operator）で、ＭｔとＭｔ+１はそれぞれｔ回目及びｔ+１回目の繰り返し演算後のポリゴン頂点を表す。）
ポリゴンの法線ベクトル方向に沿って、ポリゴン頂点を新たな位置に移動させる第５の手段とから構成されるようにすることにより、或いは、前記第２の手段は、各ポリゴン頂点の互いに垂直する２つの曲率の値を決定する手段と、各ポリゴン頂点を特徴頂点と非特徴頂点に分類する頂点分類手段と、各ポリゴン頂点の分類によって当該ポリゴン頂点の熱伝導係数を決定する手段とから構成されるようにすることにより、或いは、前記第５の手段は、ポリゴン頂点の平均曲率とポリゴン頂点の熱伝導係数との積をオフセット・ベクトルとする手段と、法線ベクトル方向に沿って拡散熱エネルギのオフセット・ベクトルを算出する手段と、スタート・ベクトルに前記オフセット・ベクトルを足したものをポリゴン頂点の新たな位置とする手段とから構成されるようにすることにより、或いは、さらに、前記頂点分類手段は、各ポリゴン頂点の最大曲率値の実数系における順番によって、全てのポリゴン頂点を２つの正規分布領域に分ける正規分布領域分け手段と、前記正規分布領域分け手段で分けられた２つの正規分布領域の分散（variance）の重畳程度によって、２つの領域に分けるか、または、１つの領域を維持するかを決定する領域決定手段と、前記領域決定手段で２つの領域に分けると決定された場合に、ベイズ分類法を用いて判別境界線（Discriminant  Boundary  Line）を見つけ、前記判別境界線の両側にそれぞれ１つの領域を形成し、左側の領域に入るポリゴン頂点を非特徴頂点と分類し、右側の領域に入るポリゴン頂点を特徴頂点と分類する領域分け手段と、前記領域決定手段で１つの領域を維持すると決定された場合に、全てのポリゴン頂点の熱伝導係数を１（つまり、完全熱導体）に設定する熱導体設定手段と、前記領域分け手段で２つの領域に分けた後に、非特徴頂点と分類されたポリゴン頂点の熱伝導係数を１に設定し、また、特徴頂点と分類されたポリゴン頂点の熱伝導係数を０と１の間の値（つまり、熱半導体）に設定する熱半導体設定手段から構成されるようにすることにより、或いは、前記正規分布領域分け手段は、k-mean演算法を採用する手段を更に含むことにより、或いは、前記熱半導体設定手段は、更に
2005216219.tif 000004
（ただし、ｗ(ｋ１,ｋ２)はポリゴン頂点の熱伝導係数で、Ｔはベイズ分類法の最適な判別境界線の閾値で、ｋ１はポリゴン頂点の最大曲率値で、ｋ２はポリゴン頂点の最小曲率値である。）を計算基礎とする手段を含むことによって効果的に達成される。
【００１２】
また、本発明は、ノイズを含んでいる３Ｄポリゴン・メッシュ・モデルを平滑化するためのアダプティブ・スムージング・フィルタリング方法に関し、本発明の上記目的は、実物の３次元物体をモデリングして得られた３Ｄポリゴン・モデルに含まれているノイズをフィルタリング処理によって除去し、且つ、フィルタリング処理後の前記３Ｄポリゴン・モデルは、平滑な表面が得られると共に、前記実物の３次元物体の形状を忠実に保つことを可能にしたアダプティブ・スムージング・フィルタリング方法であって、前記ノイズを除去するため、熱拡散方程式（Diffusion  Heat  Equation）の数値繰り返し式に基づいて演算する第１のステップと、ポリゴン頂点の位置を温度とみなし、ポリゴン頂点の曲率を熱エネルギーとみなし、繰り返し式の中の熱エネルギー分布を分析することによって、ポリゴン頂点の熱伝導係数を決定する第２のステップと、各繰り返し演算後にポリゴン頂点の新たな位置を決定する第３のステップと、繰り返し演算の停止のタイミングを決定し、平滑化されたポリゴン・モデルを得る第４のステップとを含むことにより、或いは、前記第４のステップにおいて、ポリゴン頂点が非特徴頂点に属する場合に、２つの曲率の値の総和を熱エネルギーとし、また、ポリゴン頂点が特徴頂点に属する場合に、最小の曲率の値を熱エネルギーとするようにポリゴン頂点の熱エネルギーを算出し、また、平衡熱エネルギー値を設定し、ポリゴン頂点の熱エネルギー或いは熱エネルギーの変化が前記平衡熱エネルギー値より小さい時に、繰り返し演算を停止するようにすることによって効果的に達成される。
【００１３】
更に、本発明は、ノイズを含んでいる３Ｄポリゴン・メッシュ・モデルを平滑化するためのアダプティブ・スムージング・フィルタリング・プログラムに関し、本発明の上記目的は、実物の３次元物体を３Ｄスキャナでスキャンニングして得られた３Ｄポリゴン・モデルのノイズを除去し、且つ、平滑な表面が得られると共に前記実物の３次元物体の形状を忠実に保つことを可能にしたアダプティブ・スムージング・フィルタリング装置を制御するコンピュータに、前記３Ｄポリゴン・モデルを入力とする第１のステップと、入力された前記３Ｄポリゴン・モデルのポリゴン頂点の曲率を算出する第２のステップと、算出されたポリゴン頂点の曲率の分布を算出する第３のステップと、ポリゴン頂点の属性を分類する第４のステップと、分類されたポリゴン頂点の属性によって、ポリゴン頂点の熱伝導係数を算出する第５のステップと、ポリゴン頂点の新たな位置を計算する第６のステップと、第１のステップから第５のステップまでの繰り返し演算を停止するタイミングを算出する第７のステップとを実行させることによって効果的に達成される。
【発明の効果】
【００１４】
本発明によれば、ノイズを含んでいる３Ｄポリゴン・メッシュ・モデルを平滑化する際に、ノイズを有効に取り除くと共に実物の３次元物体のコーナーとエッジを損なわずに保存することができたといった優れた効果を奏する。
【発明を実施するための最良の形態】
【００１５】
本発明は、アダプティブ・スムージング・フィルタの設計方法に属する。本発明は、ノイズを含む３Ｄポリゴン・モデルのポリゴン頂点の位置を温度とみなし、また、ポリゴン頂点の曲率を熱エネルギーとみなし、さらに、ポリゴン頂点の熱エネルギー分布をエントロピー（entropy）とみなす。熱エネルギーの流動は、表面熱拡散方程式（Thin  Plate  Heat  Equation）によってコントロールされるので、熱エネルギーの流動が熱平衡状態に達した時点で、３Ｄポリゴン・モデルが平滑化されたとみなすことができる。表面熱拡散方程式の中に、熱伝導係数が存在するので、異なる熱伝導係数は異なる熱エネルギーの流動速度を有する。例えば、熱導体の中に熱エネルギーは速やかに流動することができるが、熱絶縁体の中に熱エネルギーは流動することができない。本発明は、統計学上のベイズ判別分析（Bayesian  Discriminant  Analysis）法を用いて、ポリゴン頂点の熱伝導係数の範囲を推定することによって、繰り返し演算毎に各ポリゴン頂点に等方性拡散または異方性拡散のいずれかを採用することを自動的に決定する。
【００１６】
以下、本発明の実施の形態を図面を参照して説明する。
【００１７】
まず、本発明のアダプティブ・スムージング・フィルタ（以下、アダプティブ拡散フィルタとも称する）に入力されたノイズを含んでいる３Ｄポリゴン・メッシュ・モデルは、例えば、３次元レーザ・スキャナを用いて実物の３次元物体をモデリングして得られたものである。また、３次元レーザ・スキャナに限らず、ほかの３次元デジタイザーを用いて得られた３Ｄポリゴン・メッシュ・モデルであれば、本発明を適用することができる。つまり、本発明は、ノイズを含んでいる３Ｄポリゴン・メッシュ・モデルを平滑化するためのフィルタ及びフィルタリング方法に関するものである。
【００１８】
図１は、本発明のアダプティブ拡散フィルタを用いて、３Ｄポリゴン・モデルを平滑化するためのフローチャートである。図１に示されるように、まず、平滑化の対象であるノイズを含む３Ｄポリゴン・モデルを本発明のアダプティブ拡散フィルタの入力とする（ステップＳ１００）。次に、各ポリゴン頂点の曲率及び曲率分布（つまり、熱エネルギー分布）を算出する（ステップＳ１１０）。具体的に、ポリゴン頂点の位置及び該ポリゴン頂点とその周りのポリゴン頂点から構成されるポリゴンに基づいて、当該ポリゴン頂点の２つの曲率ｋ１とｋ２を下記の式によって算出する（図２を参照）。
【００１９】
【数１】
2005216219.tif 000005
ここで、Ｎ１(ｉ)はポリゴン頂点ｘｉを囲む周りのポリゴン頂点（以下、ポリゴン頂点ｘｉの近隣ポリゴン頂点とも称する）で、♯fはポリゴン頂点ｘｉを囲むポリゴンで、θｊはポリゴン頂点ｘｉを囲むポリゴンのポリゴン頂点ｘｉにおける角度である。
【００２０】
本発明において、ポリゴン頂点の曲率を熱エネルギーとみなすので、上記数１によって算出された３Ｄポリゴン・モデルの全てのポリゴンの２つの曲率（ｋ１とｋ２）を図３の３Ｄポリゴン・モデル曲率分布図で表現し、つまり、図３はポリゴン頂点の熱エネルギー分布図になる。図３の横軸は最大曲率方向の曲率値（つまり、最大曲率ｋ１）を示し、その縦軸は最小曲率方向の曲率値（つまり、最小曲率ｋ２）を示す。図３において、あるポリゴン頂点の熱エネルギーが少ない、または、ポリゴン頂点が座標原点に偏る時に、非特徴ポリゴン（つまり、実物の３次元物体の形状特徴を表すポリゴンではなく、ノイズを表すポリゴンである）上にある頂点（つまり、非特徴頂点或いはノイズ頂点）と判断される。一方、あるポリゴン頂点の熱エネルギーが大きい、または、ポリゴン頂点が座標原点に離れる時に、特徴ポリゴン（つまり、実物の３次元物体の形状特徴を表すポリゴン）上にある頂点（つまり、特徴頂点）と判断される。
【００２１】
次に、各ポリゴン頂点の分類を決定する（ステップＳ１２０）。つまり、各ポリゴン頂点を特徴頂点または非特徴頂点のどちらかに強制分類する。本発明において、ポリゴン頂点の分類には、ベイズ分類（Bayesian  Classification）法を採用する。ここで、ポリゴン頂点を特徴頂点と非特徴頂点に分類するために、ノイズを含む３Ｄポリゴン・モデルの特徴頂点及び非特徴頂点が最大曲率軸に沿って正規分布されることを前提とする。ベイズ分類法の式は次のようになる。
【００２２】
【数２】
2005216219.tif 000006
ここで、ｘは最適分類閾値で、ｗ１とｗ２は２つの分類で、μ１とμ２は２つの分類のそれぞれの平均値で、σ１とσ２は２つの分類のそれぞれの標準偏差である。
【００２３】
そして、最適分類閾値ｘは次の式によって算出される。
【００２４】
【数３】
2005216219.tif 000007
上記の最適分類閾値ｘによって、ポリゴン頂点を次のように分類する。ただし、ｋ１はポリゴン頂点の最大曲率値で、ｋ２はポリゴン頂点の最小曲率値である。
【００２５】
まず、あるポリゴン頂点に｜ｋ１｜＞ｘと｜ｋ２｜＞ｘが成立し、且つ、該ポリゴン頂点に少なくとも３つの近隣ポリゴン頂点の｜ｋ１｜＞ｘが成立した場合に、該ポリゴン頂点をコーナー頂点（特徴頂点に属する）と分類する。
【００２６】
次に、あるポリゴン頂点に｜ｋ１｜＞ｘが成立し、且つ、該ポリゴン頂点に少なくとも２つの近隣ポリゴン頂点の｜ｋ１｜＞ｘが成立した場合に、該ポリゴン頂点をエッジ頂点（特徴頂点に属する）と分類する。
【００２７】
最後に、特徴頂点（つまり、コーナー頂点とエッジ頂点）と分類されないポリゴン頂点
を非特徴頂点と分類する。
【００２８】
上記のような分類アルゴリズムによって分類された一例を図４に示す。図４（Ａ）はノイズを含む３Ｄポリゴン・モデルであるFandiskモデルを示し、図４（Ｂ）は、図４（Ａ）のポリゴン・モデルに対し、ポリゴン頂点分類された結果を示し、図中の黒色の部分は分類された特徴頂点を表す。
【００２９】
つまり、図５に示されるように、ベイズ分類法は、分類１（非特徴頂点）と分類２（特徴頂点）のそれぞれの正規分布（Normal  Distribution）曲線の交点を通る直線を分類線とする。分類線の右側に入るポリゴン頂点は特徴頂点（分類２）に属し、分類線の左側に入るポリゴン頂点は非特徴頂点（分類１）に属するように分類される。
【００３０】
次に、上記のように分類されたポリゴン頂点の分類によって、ポリゴン頂点の熱伝導係数を図６のような曲率マップ（curvature  map）に基づいて決定する（ステップＳ１３０）。図６の曲率マップ（つまり、熱伝導係数分布図）において、横軸は最大曲率方向の曲率値（つまり、最大曲率ｋ１）を示し、その縦軸は最小曲率方向の曲率値（つまり、最小曲率ｋ２）を示す。図６に示されるように、曲率マップの真中に正方形領域８０１が存在し、その正方形領域８０１の４つの辺８０２は、図５に示される分類線を意味し、あるポリゴン頂点の最大曲率値も最小曲率値も正方形領域８０１に入る場合に、当該ポリゴン頂点の熱伝導係数を１とする。また、図６に示されるように、曲率マップの４つのコーナーにそれぞれ小さい正方形領域８０３が存在し、あるポリゴン頂点の最大曲率値も最小曲率値もこの正方形領域８０３に入る場合に、当該ポリゴン頂点の熱伝導係数を０とする。また、あるポリゴン頂点の最大曲率値も最小曲率値も図６の曲率マップのほかの領域（つまり、正方形領域８０１と４つの正方形領域８０２を除いた図６の曲率マップのほかの領域）に入る場合に、当該ポリゴン頂点の熱伝導係数を０と１の間の値とする。つまり、１＜当該ポリゴン頂点の熱伝導係数＜０が成立する。正方形領域８０１に近づくポリゴン頂点に大きい熱伝導係数を与え、逆に、正方形領域８０１に離れるポリゴン頂点に小さい熱伝導係数を与えるようにする。
【００３１】
上述した説明によれば、図６の正方形領域８０１の４つの辺８０２は、繰り返し処理ステップの進行に伴って少しずつ移動していくことが良く分かる。例えば、ポリゴン・モデルの全ての頂点を２つの分類に分けることができない場合、つまり、全てのポリゴン頂点を同じ分類として処理する場合に、正方形領域８０１は図６の曲率マップの全領域を占領してしまう。その際、全てのポリゴン頂点の熱伝導係数は１になり、すなわち、この場合の繰り返し動作は等方性フィルタリング動作になる訳である。従って、本発明のフィルタ及びフィルタリング方法は、熱エネルギーの拡散ステップに伴って絶えずにポリゴン頂点の熱伝導係数の値を変えていくフィルタ設計方法である。例えば、図３（Ａ）は１回目の繰り返し演算時に使う、既に決定された１枚目の曲率マップ（つまり、図６に示された図）の分布図である。図３（Ｂ）は５回目の繰り返し演算時に使う曲率分布図で、また、図３（Ｃ）は最終繰り返し演算（ちなみに、１６回目の繰り返し演算）時に使う曲率分布図である。
【００３２】
本発明では、このように繰り返し演算において、曲率分布図と曲率マップを繰り返し計算することによって、繰り返し演算毎の重み係数（つまり、熱伝導係数）を決定し、非特徴頂点に属するポリゴン頂点の熱エネルギーを速やかに拡散させると共に、特徴頂点に属するポリゴン頂点の熱エネルギーを緩やかに拡散させることによって、熱エネルギーの拡散が平衡状態に達した時点は、３Ｄポリゴン・モデルが平滑化された状態に達し、実物の３次元物体の形状を忠実に再現した３Ｄポリゴン・モデルが得られた訳である。
【００３３】
次に、得られたポリゴン頂点の熱伝導係数とポリゴン頂点の現在位置を表面熱拡散方程式（Double  Degenerated  Heat  Equation）の数値繰り返し式に代入し（ステップＳ１４０）、各ポリゴン頂点の新たな位置が得られる（ステップＳ１５０）。
【００３４】
具体的に、本発明では、熱伝達理論に基づいて、双方向曲率マッピング関数（bi-directional  curvature  mapping  function）ｗ(ｋ１,ｋ２)を使用している。ｋ１とｋ２はそれぞれポリゴン頂点の最大曲率と最小曲率である。｜ｋ１｜≧｜ｋ２｜が成立することを前提とする。双方向曲率マッピングの重み関数ｗ(ｋ１,ｋ２)は次の式によって表される。
【００３５】
【数４】
2005216219.tif 000008
ここで、Ｔは上記ステップＳ１２０で説明した、ベイズ分類法によって得られた最適分類閾値である。ちなみに、図６は最適分類閾値Ｔ＝５の時の双方向曲率マップである。つまり、上記数４の重み関数ｗ(ｋ１,ｋ２)は、ポリゴン頂点の熱伝導係数である。
【００３６】
上記数４の双方向曲率マッピングの重み関数ｗ(ｋ１,ｋ２)に加えて、本発明では、下記数５の異方性表面熱拡散方程式（Double  Degenerated  Heat  Equation）の数値繰り返し式を用いて、図７に示されるように、熱エネルギーの拡散（つまり、フィルタリング処理）を行なう。つまり、数５の繰り返し演算によって、ポリゴン頂点の新たな位置が得られる訳である。
【００３７】
【数５】
2005216219.tif 000009
ここで、∇2cは平均曲率フロー演算子（mean  curvature  flow  operator）で、ｗ(ｋ１,ｋ２)は重み関数で、つまり、ポリゴン頂点の熱伝導係数である。ＭｔとＭｔ+１はそれぞれｔ回目及びｔ+１回目の繰り返し演算後のポリゴン頂点を表す。
【００３８】
また、ｘｉはポリゴン頂点で、κiHはポリゴン頂点ｘｉの平均曲率で、
2005216219.tif 000010
はポリゴン頂点ｘｉの単位法線ベクトルである。
【００３９】
次に、３Ｄポリゴン・モデルの全てのポリゴン頂点が既に収束したかを判断する（ステップＳ１６０）。全てのポリゴン頂点が既に収束した場合には、平滑化された３Ｄポリゴン・モデルが得られて、本発明による、３Ｄポリゴン・モデルの平滑化処理が完了する（ステップＳ１８０）。一方、まだ収束していないポリゴン頂点が存在する場合には、収束していないポリゴン頂点のみの曲率及び熱エネルギー分布を算出し（ステップＳ１７０）、前記ステップＳ１２０に戻り、ステップＳ１２０〜ステップＳ１６０の処理を繰り返す。
【００４０】
ここで、ポリゴン頂点が既に収束したとは、ポリゴン頂点の熱エネルギーが熱平衡状態に達したことになる。まだ収束していないポリゴン頂点とは、そのポリゴン頂点の熱エネルギーがまだ熱平衡状態に達していないことになるので、ステップＳ１２０〜ステップＳ１７０の処理を繰り返すことによって、ポリゴン頂点の熱エネルギー拡散をしていく訳である。ポリゴン頂点の熱エネルギーが熱平衡状態に達した時に、当該ポリゴン頂点の位置
は、次の繰り返し演算によっても変っていない訳で、本発明では、各ポリゴン頂点に対し、収束テストを行なうことによって、各ポリゴン頂点が熱平衡状態に達しているかどうかを判断する。
【００４１】
本発明の収束テストでは、各ポリゴン頂点のトータル曲率（total  curvature）を算出し、そして、算出されたトータル曲率を用いて非特徴頂点の収束を判断する。一方、各ポリゴン頂点の最小曲率を用いて特徴頂点の収束を判断する。ｐ回目の繰り返し演算におけるポリゴン頂点に対する収束テストに適用される関数は次のようになる。
【００４２】
【数６】
2005216219.tif 000011
ここで、上付き文字ｐはｐ回目の繰り返し演算を表し、また、ポリゴン頂点のトータル曲率tcは｜ｋ１｜＋｜ｋ２｜によって算出される。{Ｆ}は特徴頂点の集合で、εは事前に設定した閾値である。ポリゴン頂点は上記収束テストをパスした時に、そのポリゴン頂点は収束した、或いは、熱平衡状態に達したと判断される。全てのポリゴン頂点が熱平衡状態に達した時点で、３Ｄポリゴン・モデルの平滑化処理は完了する。
【００４３】
なお、上述した本発明の一連の処理（つまり、ステップＳ１００からステップＳ１８０までの処理）をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウエアに組み込まれているコンピュータ（例えば、ＣＰＵ内蔵の３次元レーザ・スキャナ）、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナル・コンピュータなどに、ネットワークや記録媒体からインストールされることができる。
【００４４】
ここで、異なる３Ｄポリゴン・モデルに対し、上述した本発明のアダプティブ・スムージング・フィルタを適用した平滑化結果をそれぞれ図８、図９及び図１０に示す。また、図８及び図９では、本発明のアダプティブ拡散フィルタと比較するために、従来の等方性拡散フィルタと従来の異方性拡散フィルタを適用した平滑化結果も一緒に示している。
【００４５】
具体的に、図８（Ａ）は、実物の３次元物体を示す図である。図８（Ｂ）は、図８（Ａ）の実物の３次元物体をモデルリングして得られた、ノイズを含む３Ｄポリゴン・モデルを示す図である。図８（Ｃ）は、従来の等方性拡散フィルタ（Isotropic  Diffusion  Filter）を用いて、図８（Ｂ）の３Ｄポリゴン・モデルを平滑化した結果を示す図である。図８（Ｄ）は、従来の異方性拡散フィルタ（Anisotropic  Diffusion  Filter）を用いて、図８（Ｂ）の３Ｄポリゴン・モデルを平滑化した結果を示す図である。図８（Ｅ）は、本発明のアダプティブ拡散フィルタ（Adaptive  Diffusion  Filter）を用いて、図８（Ｂ）の３Ｄポリゴン・モデルを平滑化した結果を示す図である。図８から分かるように、本発明のアダプティブ拡散フィルタを適用して平滑化された３Ｄポリゴン・モデルは、実物の３次元物体のコーナーとエッジを損なわずに保存することができた。一方、従来の等方性拡散フィルタを適用して平滑化された３Ｄポリゴン・モデルは、コーナーもエッジも損なわずに保存することができなくて、ノイズを平滑化すると共に有用なデータも同時に失ったことが良く分かる。また、従来の異方性拡散フィルタを適用して平滑化された３Ｄポリゴン・モデルは、エッジを損なわずに保存することができたが、コーナーを損なわずに保存することができなかったことも良く分かる。
【００４６】
また、図９（Ａ）は、オリジナルのFandiskモデル（つまり、実物の３次元物体）を示す図である。図９（Ｂ）は、図９（Ａ）のFandiskモデルに０．３％のガウス・ノイズ（Gaussian  noise）を加えた結果（つまり、ノイズを含む３Ｄポリゴン・モデル）を示す図である。図９（Ｃ）は、従来の等方性拡散フィルタを用いて、図９（Ｂ）のFandiskモデルを平滑化した結果を示す図である。図９（Ｄ）は、従来の異方性拡散フィルタを用いて、図９（Ｂ）のFandiskモデルを平滑化した結果を示す図である。図９（Ｅ）は、本発明のアダプティブ拡散フィルタを用いて、図９（Ｂ）のFandiskモデルを平滑化した結果を示す図である。
【００４７】
更に、図１０（Ａ）は、ゴルフのクラブヘッドの金型のオリジナル３Ｄモデル（つまり、実物の３次元物体）を示す図である。図１０（Ｂ）は、図１０（Ａ）のモデルに１％のガウス・ノイズを加えた結果（つまり、つまり、ノイズを含む３Ｄポリゴン・モデル）を示す図である。図１０（Ｃ）は、本発明のアダプティブ拡散フィルタを用いて、図１０（Ｂ）のモデルを平滑化した結果を示す図である。
【００４８】
なお、上述した実施例では、ベイズ分類法を用いてポリゴン頂点を分類したが、本発明はそれに限定されることがなく、例えば、Ｋ−mean法を用いてポリゴン頂点を分類することもできる。この場合には、ポリゴン頂点の最大曲率のＫ−meanを用いて分類する。本発明では、ポリゴン頂点を２種類に分けるので、Ｋ−mean法のＫは２になる。
【図面の簡単な説明】
【００４９】
【図１】本発明のアダプティブ拡散フィルタを用いて３Ｄポリゴン・モデルを平滑化するためのフローチャートである。
【図２】数１を説明するための模式図である。
【図３】図３（Ａ）は、図８（Ｂ）のノイズを含む３Ｄポリゴン・モデルの最初の曲率分布図である。図３（Ｂ）は、本発明のアダプティブ拡散フィルタによる５回の繰り返し演算を行った後の３Ｄポリゴン・モデルの曲率分布図である。図３（Ｃ）は、本発明のアダプティブ拡散フィルタによる１６回の繰り返し演算を行った後の３Ｄポリゴン・モデルの曲率分布図である。
【図４】本発明において、ポリゴン頂点の分類結果の一例を示す図である。
【図５】本発明においてポリゴン頂点の分類を決定するための最適分類閾値を説明するための模式図である。
【図６】本発明においてポリゴン頂点の分類とその熱エネルギーに基づいて得られた熱伝導係数分布図（つまり、曲率マップ）である。
【図７】本発明に用いられる異方性表面熱拡散方程式（Double  Degenerated  Heat  Equation）を説明するための模式図である。
【図８】図８（Ａ）は、実物の３次元物体を示す図である。図８（Ｂ）は、図８（Ａ）の実物の３次元物体をモデルリングして得られた、ノイズを含む３Ｄポリゴン・モデルを示す図である。図８（Ｃ）は、従来の等方性拡散フィルタ（Isotropic  Diffusion  Filter）を用いて、図８（Ｂ）の３Ｄポリゴン・モデルを平滑化した結果を示す図である。図８（Ｄ）は、従来の異方性拡散フィルタ（Anisotropic  Diffusion  Filter）を用いて、図８（Ｂ）の３Ｄポリゴン・モデルを平滑化した結果を示す図である。図８（Ｅ）は、本発明のアダプティブ拡散フィルタ（Adaptive  Diffusion  Filter）を用いて、図８（Ｂ）の３Ｄポリゴン・モデルを平滑化した結果を示す図である。
【図９】図９（Ａ）は、オリジナルのFandiskモデル（つまり、実物の３次元物体）を示す図である。図９（Ｂ）は、図９（Ａ）のFandiskモデルに０．３％のガウス・ノイズ（Gaussian  noise）を加えた結果（つまり、ノイズを含む３Ｄポリゴン・モデル）を示す図である。図９（Ｃ）は、従来の等方性拡散フィルタを用いて、図９（Ｂ）のFandiskモデルを平滑化した結果を示す図である。図９（Ｄ）は、従来の異方性拡散フィルタを用いて、図９（Ｂ）のFandiskモデルを平滑化した結果を示す図である。図９（Ｅ）は、本発明のアダプティブ拡散フィルタを用いて、図９（Ｂ）のFandiskモデルを平滑化した結果を示す図である。
【図１０】図１０（Ａ）は、ゴルフのクラブヘッドの金型のオリジナル３Ｄモデル（つまり、実物の３次元物体）を示す図である。図１０（Ｂ）は、図１０（Ａ）のモデルに１％のガウス・ノイズを加えた結果（つまり、つまり、ノイズを含む３Ｄポリゴン・モデル）を示す図である。図１０（Ｃ）は、本発明のアダプティブ拡散フィルタを用いて、図１０（Ｂ）のモデルを平滑化した結果を示す図である。
【図１１】図１１（Ａ）は従来の等方性拡散フィルタを説明するための模式図である。図１１（Ｂ）は従来の異方性拡散フィルタを説明するための模式図である。
【図１】
2005216219.tif 000014
【図２】
2005216219.tif 000015
【図３】
2005216219.tif 000016
【図４】
2005216219.tif 000017
【図５】
2005216219.tif 000018
【図６】
2005216219.tif 000019
【図７】
2005216219.tif 000020
【図８】
2005216219.tif 000021
【図９】
2005216219.tif 000022
【図１０】
2005216219.tif 000023
【図１１】
2005216219.tif 000024