Top > Search of Japanese Patents > APPARATUS, METHOD AND PROGRAM FOR SEGMENTATION OF ANALYTIC CURVED SURFACE AND RECORDING MEDIUM

APPARATUS, METHOD AND PROGRAM FOR SEGMENTATION OF ANALYTIC CURVED SURFACE AND RECORDING MEDIUM meetings achieved

Patent code P08A014170
File No. 104-P2006-219-JP01
Posted date Dec 25, 2008
Application number P2007-015473
Publication number P2007-241996A
Patent number P4568843
Date of filing Jan 25, 2007
Date of publication of application Sep 20, 2007
Date of registration Aug 20, 2010
Priority data
  • P2006-035719 (Feb 13, 2006) JP
Inventor
  • (In Japanese)金井 理
  • (In Japanese)岸浪 建史
  • (In Japanese)溝口 知広
  • (In Japanese)伊達 宏昭
Applicant
  • (In Japanese)国立大学法人北海道大学
Title APPARATUS, METHOD AND PROGRAM FOR SEGMENTATION OF ANALYTIC CURVED SURFACE AND RECORDING MEDIUM meetings achieved
Abstract PROBLEM TO BE SOLVED: To extract regions equivalent to one analytic curved surface (planer, cylindrical, a conical, spherical and toric surface regions) and their boundaries as feature edge lines and to further and automatically recognize fillet surface regions, linear extrusion regions and surface regions of revolution.
SOLUTION: Mesh data is input, main curvature is calculated from the input mesh model data to the apex which is not the sharp apex, seed regions constituted of coupling apex set which can be considered as being belonging to one certain analytic curved surface is generated based on the calculated main curvature, analytic curved surface regions are extracted by extending the seed regions and thus, boundary lines of the plurality of curved surface regions extracted as the characteristic edge, fillet surface regions, linear extrusion surface regions or the revolution surface regions are recognized and solid model data is generated by information about the feature edge lines extracted by the feature edge line extraction processing and information of the curved surface area recognized by face curved surface recognition processing.
Outline of related art and contending technology (In Japanese)


近年、工業用高エネルギーX線CTスキャナにより機械部品をスキャンすることでその機械部品の3次元(3D)のメッシュモデルを自動的に取得できるようになってきており、工業製品開発に多く用いられるようになってきている。この高エネルギーX線CTスキャナは、複雑な形状の工業製品の内部構造の3次元画像データを迅速に、非破壊で取得するのに利用される。



今日、得られた3次元スキャン画像データは容易に3次元メッシュモデルデータに変換可能である。例えば、非特許文献1に記載されたマーチングキューブ法がよく知られている。3次元スキャンメッシュモデルが工業製品の修理、レプリカ作成、解析あるいは検査に利用されるとき、その用途に応じてメッシュモデルを望ましい領域群に効果的に分割することが必要である。



工業製品の表面は主に解析曲面、例えば、平面、円筒面、球面、円錐面そしてトーラスの組み合わせによって構成されている。したがって、メッシュモデルから引き出される単純な解析曲面によって近似できる領域群を抽出することが必要である。この領域分割はメッシュモデルに対する特徴認識を可能にし、パラメータによるメッシュ変形、メッシュスムージング、FEMメッシュ生成、立体モデル作成の前処理に重要な役割をする。



シャープエッジによって分けられる領域を抽出する方法について、多数の方法が提案されている。しかしながら、メッシュモデルから解析曲面によって近似できる領域を抽出する方法はほとんど提案されていない。また、提案された方法にあっては、ノイズの多いメッシュモデルからの領域抽出の正確さ、また抽出された解析曲面の応用範囲は実用性の面で不十分である。



関連する公知技術は以下のようなものである。メッシュ分割、メッシュ特徴抽出と再メッシュ分割のようなメッシュ応用技術で利用される基本技術の1つにメッシュ曲率推定法がある。この方法のアプローチには、非特許文献5,6,7がある。



非特許文献5では、メッシュ曲率推定法は2つのグループに分けられている。1つは、離散的表現における微分幾何演算のために閉鎖形状を形成することで曲率を推定するものである。他の1つは、メッシュ頂点ごとの周りに比較的高度の曲面を局所的にフィットし、この曲面を解析することで曲率を推定するものである。過去の非特許文献3,4,5では、後者の推定方法はノイズの多いメッシュモデルに対してより良い結果をもたらすとされている。



メッシュ分割は、メッシュモデルを用途に応じて望ましい領域に分割するという技術である。メッシュ分割には多数の取り組みが提案されているが、大きく分けて3つのグループに分けることができる。



第1のグループは、メッシュモデル上のシャープエッジによって分けられる領域を抽出するものである。このグループでは、ウォータシェッド法(Watershed method)をベースとする取り組みが良く研究されている。非特許文献8,9,10である。このウェータシェッド法のアルゴリズムは、最初は2次元画像の分割のために提案されたものであり、マンガンその他(Mangan et al.)による非特許文献8ではそれをメッシュ分割に拡張した。このウォータシェッド法のアルゴリズムは、各頂点に対するメッシュ曲率のような特徴量を割り当て、局所的な極小値を発見する。続いて、各局所的な極小値の周りに隣接する頂点群を最急峻降下アルゴリズムを用いてクラスタ分けすれば、シャープエッジは隣接するクラスタ間の境界に現われる。サンその他(Sun et al.)による非特許文献9では、ノイズの多いスキャンメッシュデータに対するローバストな頂点特徴量計算法を用いるアルゴリズムを改善している。ラズダンその他(Razdan et al.)の非特許文献10では、ソリッドモデルから切り出されるメッシュモデルに対するアルゴリズムを改善している。これらの方法は、メッシュモデルをシャープエッジによって分離される領域に分割することができる。しかしながら、スムーズエッジにより分離される領域群(円筒面にスムーズに接続される平面)を抽出することはできない。また、それゆえに、分割された領域ごとの幾何学面を正しく同定することもできない。



第2のグループは、単純な自由形状面により近似される領域群を抽出するものである。このグループでは、非特許文献3,11,12で領域拡大法(Region growing method)による取り組みが研究されている。最初、ベスルその他(Besl et al.)による非特許文献11において、高さ領域データに対する領域拡大法が提案された。近年、ビエラその他(Vieira et all.)による非特許文献3で、この方法がレーザスキャナによるノイズの多い3次元メッシュモデルに対して拡張されている。このアルゴリズムでは、最初にメッシュ曲率を推定し、メッシュ曲率の符号を用いて領域候補群を作り出す。そして、自由形状曲面に繰り返しフィットし、隣接する頂点群を追加することで最終的な領域群を抽出する。この方法によれば、ノイズの多いメッシュモデルから自由形状曲面領域を抽出し、多種の曲面を分離抽出することができる。しかしながら、この方法は、解析曲面とその幾何変数によって近似される領域群を抽出することは目的としていない。



最後のグループは、単純な解析曲面にて近似される領域群を抽出するものである。ゲルファンドその他(Gelfand et al.)による非特許文献13は、メッシュ頂点とその法線ベクトルを固有値解析に基づく方法を提案している。しかしながら、この方法は、平面、円筒面そして球面による近似できる領域群のみを抽出する。



ウーその他(Wu et al.)の非特許文献14は、ロイドのクラスタリングアルゴリズム(Lloyd’s clustering algorithm)に基づく方法を提案している。それによると、上の3曲面に加えて自由形状曲線上を転がる転動球により近似されるフィレット領域群が抽出される。しかしながら、この方法は、ノイズの多いメッシュモデルではどの程度有効なものか不明であり、また分割領域の内部領域を如何に同定するかも不明である。加えて、曲面フィッティングとクラスタリングを繰り返すために処理時間が比較的遅い。



メッシュモデルデータからソリッドモデルを生成することを目的としたメッシュモデルのセグメンテーション法として、ベンコーその他(Benko et al.)による非特許文献4では、工業部品のリバースエンジニアリングのための直接セグメンテーション法が提案されている。その方法では、最初に局所的に平面をフィッティングすることによってシャープエッジの近傍における三角形群を除去してから、入力されたメッシュを領域群に分割する。次に、法線ベクトルや主曲率のような指標に基づき各領域ごとに三角形群と曲面群との幾何的適合性をテストする。こうして、分割領域群を、単純な解析曲面(平面、円筒面、球面、円錐面、トーラス面)、線形押し出し面、回転面により近似される。しかしながら、この方法では、ソリッドモデル生成に適した解析曲面領域、線形押し出し面領域、回転面領域を抽出できるが、領域抽出の精度が低く、簡単な形状にしか適用できないといった問題点があった。



このように、メッシュモデルを設計・製造に有効に利用するために、メッシュモデルからソリッドモデルを自動で生成する手法の開発が望まれている。しかし現状では、この初期段階である測定メッシュモデルから適切に領域抽出するセグメンテーション手法が不十分であり、複雑形状に適用できるものはなく、ユーザによる多くのマニュアル操作を必要としていた。加えて、機械部品は解析曲面で構成される部分が多く、形状変更などの容易性を考えた場合、その形状が解析曲面でパラメトリックに表現されることが望ましいが、それに答える技術はない。















Field of industrial application (In Japanese)


本発明は、メッシュモデルデータから解析曲面フィッティングに基づき解析曲面のセグメンテーションを行う解析曲面セグメンテーション装置、方法、プログラム及び記録媒体に関する。

Scope of claims (In Japanese)
【請求項1】
 
入力された若しくは記憶装置から読出されたメッシュモデルデータを受け付けるメッシュデータ受付手段と、
前記メッシュモデルデータからメッシュモデルの各頂点の主曲率を計算し、最大主曲率の値が閾値より大きな頂点をシャープ頂点として除外するメッシュ主曲率算出手段と、
前記シャープ頂点ではない頂点の主曲率をもとに、ある1つの解析曲面に属しているとみなせる連結頂点集合からなるシード領域を生成するシード領域生成手段と、
前記シード領域生成手段が生成したシード領域内の頂点に基づき、各解析曲面を定義する幾何パラメータを決定し、前記シード領域に解析曲面をフィッティングする解析曲面フィッティング手段と、
前記シード領域生成手段が生成したシード領域に隣接する頂点のうち、前記解析曲面フィッティング手段がフィッティングした解析曲面に対する位置と法線の誤差が閾値よりも小さい頂点を当該シード領域に追加してシード領域を拡大して、拡大したシード領域を表わす解析曲面領域を抽出する解析曲面領域抽出手段と、
前記解析曲面領域抽出手段が抽出した複数の連結した解析曲面領域それぞれについて、フィレット面領域、線形押し出し面領域又は回転面領域を認識する解析曲面領域認識手段と、
前記解析曲面領域抽出手段の抽出した解析曲面と前記解析曲面領域認識手段が認識したフィレット面領域、線形押し出し面領域及び回転面領域との認識結果を出力するデータ出力手段とを備え、
前記メッシュ主曲率算出手段は、曲率評価範囲を決定するパラメータの第1の値を各頂点に接続する稜線の平均長さの2倍に設定して各頂点の主曲率を算出し、前記各頂点のうちその最大主曲率の値が閾値より大きな頂点をシャープ頂点と分類し、当該シャープ頂点でない頂点に対して、前記曲率評価範囲を決定するパラメータの第2の値を各頂点に接続する稜線の平均長さの5倍に設定し、主曲率を算出する2パス演算を実行し、
前記シード領域生成手段は、前記メッシュ主曲率算出手段が算出したシャープ頂点を除いた各頂点の主曲率値を比較し、各頂点に対してそれが平面、円筒面、円錐面、球面、その他の面のうちのどれに属するかを識別するラベルを割り当て、割り当てたラベルに基づき、同じラベルを持つ連結頂点集合をシード領域として抽出することを特徴とする解析曲面セグメンテーション装置。

【請求項2】
 
前記シード領域生成手段は、前記その他の面に属するラベルが割り当て頂点に対して、横軸を主曲率、縦軸をその主曲率の値を持つ頂点数としたヒストグラムを作成し、ある主曲率値を持つ頂点数が閾値より大きければ、それらの頂点群にトーラス面のラベルを割り当てることを特徴とする請求項1に記載の解析曲面セグメンテーション装置。

【請求項3】
 
前記解析曲面フィッティング手段は、
円筒・円錐面については、まず、シード領域内の頂点の法線とガウス球との交点群に平面をフィッティングし、この平面の法線を軸方向として算出し、
円筒面については、シード領域内の頂点を、軸方向を法線に持ち原点を通る平面に投影し、投影面上で円弧をフィッティングし、その円弧の中心と軸上の任意点を求め、
円錐面については、円錐の頂点とメッシュの各頂点とを結ぶベクトルがメッシュの各頂点の法線と直交するという条件から、その頂点を最小2乗法を用いて算出し、最後に、軸方向とメッシュ頂点の法線のなす角度の平均値から頂角を求めることを特徴とする請求項1又は2に記載の解析曲面セグメンテーション装置。

【請求項4】
 
入力された若しくは記憶装置から読出されたメッシュモデルデータを受け付けるステップと、
前記メッシュモデルデータからメッシュモデルの各頂点の主曲率を計算し、最大主曲率の値が閾値より大きな頂点をシャープ頂点として除外するメッシュ主曲率算出ステップと、
前記シャープ頂点ではない頂点の主曲率をもとに、ある1つの解析曲面に属しているとみなせる連結頂点集合からなるシード領域を生成するシード領域生成ステップと、
前記シード領域生成ステップで生成したシード領域内の頂点に基づき、各解析曲面を定義する幾何パラメータを決定し、前記シード領域に解析曲面をフィッティングする解析曲面フィッティングステップと、
前記シード領域生成ステップで生成したシード領域に隣接する頂点のうち、前記解析曲面フィッティングステップでフィッティングした解析曲面に対する位置と法線の誤差が閾値よりも小さい頂点を当該シード領域に追加してシード領域を拡大して、拡大したシード領域を表わす解析曲面領域を抽出する解析曲面領域抽出ステップと、
前記解析曲面領域抽出ステップで抽出した複数の連結した解析曲面領域それぞれについて、フィレット面領域、線形押し出し面領域又は回転面領域を認識する解析曲面領域認識ステップと、
前記解析曲面領域抽出ステップで抽出した解析曲面と前記解析曲面領域認識ステップで認識したフィレット面領域、線形押し出し面領域及び回転面領域との認識結果を出力するデータ出力ステップとを有し、
前記メッシュ主曲率算出ステップにおいては、曲率評価範囲を決定するパラメータの第1の値を各頂点に接続する稜線の平均長さの2倍に設定して各頂点の主曲率を算出し、前記各頂点のうちその最大主曲率の値が閾値より大きな頂点をシャープ頂点と分類し、当該シャープ頂点でない頂点に対して、前記曲率評価範囲を決定するパラメータの第2の値を各頂点に接続する稜線の平均長さの5倍に設定して主曲率を算出し、
前記シード領域生成ステップにおいては、前記メッシュ主曲率算出ステップで算出したシャープ頂点を除いた各頂点の主曲率値を比較し、各頂点に対してそれが平面、円筒面、円錐面、球面、その他の面のうちのどれに属するかを識別するラベルを割り当て、割り当てたラベルに基づき、同じラベルを持つ連結頂点集合をシード領域として抽出することを特徴とする解析曲面セグメンテーション方法。

【請求項5】
 
前記シード領域生成ステップでは、前記その他の面に属するラベルが割り当てられた頂点に対して、横軸を主曲率、縦軸をその主曲率の値を持つ頂点数としたヒストグラムを作成し、ある主曲率値を持つ頂点数が閾値より大きければ、それらの頂点群にトーラス面のラベルを割り当てることを特徴とする請求項4に記載の解析曲面セグメンテーション方法

【請求項6】
 
前記解析曲面フィッティングステップでは、
円筒・円錐面については、まず、シード領域内の頂点の法線とガウス球との交点群に平面をフィッティングし、この平面の法線を軸方向として算出し、
円筒面については、シード領域内の頂点を、軸方向を法線に持ち原点を通る平面に投影し、投影面上で円弧をフィッティングし、その中心と軸上の任意点を求め、
円錐面については、円錐の頂点とメッシュの各頂点とを結ぶベクトルがメッシュの各頂点の法線と直交するという条件から、その頂点を最小2乗法を用いて算出し、最後に、軸方向とメッシュ頂点の法線のなす角度の平均値から頂角を求めることを特徴とする請求項4又は5に記載の解析曲面セグメンテーション方法。

【請求項7】
 
入力された若しくは記憶装置から読出されたメッシュモデルデータを受け付けるステップと、
前記メッシュモデルデータからメッシュモデルの各頂点の主曲率を計算し、最大主曲率の値が閾値より大きな頂点をシャープ頂点として除外するメッシュ主曲率算出ステップと、
前記シャープ頂点ではない頂点の主曲率をもとに、ある1つの解析曲面に属しているとみなせる連結頂点集合からなるシード領域を生成するシード領域生成ステップと、
前記シード領域生成ステップで生成したシード領域内の頂点に基づき、各解析曲面を定義する幾何パラメータを決定し、前記シード領域に解析曲面をフィッティングする解析曲面フィッティングステップと、
前記シード領域生成ステップで生成したシード領域に隣接する頂点のうち、前記解析曲面フィッティングステップでフィッティングした解析曲面に対する位置と法線の誤差が閾値よりも小さい頂点を当該シード領域に追加してシード領域を拡大して、拡大したシード領域を表わす解析曲面領域を抽出する解析曲面領域抽出ステップと、
前記解析曲面領域抽出ステップで抽出した複数の連結した解析曲面領域それぞれについて、フィレット面領域、線形押し出し面領域又は回転面領域を認識する解析曲面領域認識ステップと、
前記解析曲面領域抽出ステップで抽出した解析曲面と前記解析曲面領域認識ステップで認識したフィレット面領域、線形押し出し面領域及び回転面領域との認識結果を出力するデータ出力ステップとをコンピュータに実行させる解析曲面セグメンテーションプログラムであって、
前記メッシュ主曲率算出ステップでは、曲率評価範囲を決定するパラメータの第1の値を各頂点に接続する稜線の平均長さの2倍に設定して各頂点の主曲率を算出し、前記各頂点のうちその最大主曲率の値が閾値より大きな頂点をシャープ頂点と分類し、当該シャープ頂点でない頂点に対して、前記曲率評価範囲を決定するパラメータの第2の値を各頂点に接続する稜線の平均長さの5倍に設定して主曲率を算出し、
前記シード領域生成ステップでは、前記メッシュ主曲率算出ステップで算出したシャープ頂点を除いた各頂点の主曲率値を比較し、各頂点に対してそれが平面、円筒面、円錐面、球面、その他の面のうちのどれに属するかを識別するラベルを割り当て、割り当てたラベルに基づき、同じラベルを持つ連結頂点集合をシード領域として抽出することを特徴とする解析曲面セグメンテーションプログラム。

【請求項8】
 
前記シード領域生成ステップでは、前記コンピュータに、前記その他の面に属するラベルが割り当てられた頂点に対して、横軸を主曲率、縦軸をその主曲率の値を持つ頂点数としたヒストグラムを作成し、ある主曲率値を持つ頂点数が閾値より大きければ、それらの頂点群にトーラス面のラベルを割り当てさせることを特徴とする請求項7に記載の解析曲面セグメンテーションプログラム

【請求項9】
 
前記解析曲面フィッティングステップでは、前記コンピュータに、
円筒・円錐面については、まず、シード領域内の頂点の法線とガウス球との交点群に平面をフィッティングし、この平面の法線を軸方向として算出し、
円筒面については、シード領域内の頂点を、軸方向を法線に持ち原点を通る平面に投影し、投影面上で円弧をフィッティングし、その中心と軸上の任意点を求め、
円錐面については、円錐の頂点とメッシュの各頂点とを結ぶベクトルがメッシュの各頂点の法線と直交するという条件から、その頂点を最小2乗法を用いて算出し、最後に、軸方向とメッシュ頂点の法線のなす角度の平均値から頂角を求めさせることを特徴とする請求項7又は8に記載の解析曲面セグメンテーションプログラム

【請求項10】
 
入力された若しくは記憶装置から読出されたメッシュモデルデータを受け付けるステップと、
前記メッシュモデルデータからメッシュモデルの各頂点の主曲率を計算し、最大主曲率の値が閾値より大きな頂点をシャープ頂点として除外するメッシュ主曲率算出ステップと、
前記シャープ頂点ではない頂点の主曲率をもとに、ある1つの解析曲面に属しているとみなせる連結頂点集合からなるシード領域を生成するシード領域生成ステップと、
前記シード領域生成ステップで生成したシード領域内の頂点に基づき、各解析曲面を定義する幾何パラメータを決定し、前記シード領域に解析曲面をフィッティングする解析曲面フィッティングステップと、
前記シード領域生成ステップで生成したシード領域に隣接する頂点のうち、前記解析曲面フィッティングステップでフィッティングした解析曲面に対する位置と法線の誤差が閾値よりも小さい頂点を当該シード領域に追加してシード領域を拡大して、拡大したシード領域を表わす解析曲面領域を抽出する解析曲面領域抽出ステップと、
前記解析曲面領域抽出ステップで抽出した複数の連結した解析曲面領域それぞれについて、フィレット面領域、線形押し出し面領域又は回転面領域を認識する解析曲面領域認識ステップと、
前記解析曲面領域抽出ステップで抽出した解析曲面と前記解析曲面領域認識ステップで認識したフィレット面領域、線形押し出し面領域及び回転面領域との認識結果を出力するデータ出力ステップとを有し、
前記メッシュ主曲率算出ステップでは、曲率評価範囲を決定するパラメータの第1の値を各頂点に接続する稜線の平均長さの2倍に設定して各頂点の主曲率を算出し、前記各頂点のうちその最大主曲率の値が閾値より大きな頂点をシャープ頂点と分類し、当該シャープ頂点でない頂点に対して、前記曲率評価範囲を決定するパラメータの第2の値を各頂点に接続する稜線の平均長さの5倍に設定して主曲率を算出し、
前記シード領域生成ステップでは、前記メッシュ主曲率算出ステップで算出したシャープ頂点を除いた各頂点の主曲率値を比較し、各頂点に対してそれが平面、円筒面、円錐面、球面、その他の面のうちのどれに属するかを識別するラベルを割り当て、割り当てたラベルに基づき、同じラベルを持つ連結頂点集合をシード領域として抽出する解析曲面セグメンテーションプログラムを記録したコンピュータ読取り可能な記録媒体。

【請求項11】
 
前記シード領域生成ステップでは、前記その他の面に属するラベルが割り当てられた頂点に対して、横軸を主曲率、縦軸をその主曲率の値を持つ頂点数としたヒストグラムを作成し、ある主曲率値を持つ頂点数が閾値より大きければ、それらの頂点群にトーラス面のラベルを割り当てることを特徴とする請求項10に記載の解析曲面セグメンテーションプログラムを記録したコンピュータ読取り可能な記録媒体。

【請求項12】
 
前記解析曲面フィッティングステップでは、
円筒・円錐面については、まず、シード領域内の頂点の法線とガウス球との交点群に平面をフィッティングし、この平面の法線を軸方向として算出し、
円筒面については、シード領域内の頂点を、軸方向を法線に持ち原点を通る平面に投影し、投影面上で円弧をフィッティングし、その中心と軸上の任意点を求め、
円錐面については、円錐の頂点とメッシュの各頂点とを結ぶベクトルがメッシュの各頂点の法線と直交するという条件から、その頂点を最小2乗法を用いて算出し、最後に、軸方向とメッシュ頂点の法線のなす角度の平均値から頂角を求めることを特徴とする請求項10又は11に記載の解析曲面セグメンテーションプログラムを記録したコンピュータ読取り可能な記録媒体。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2007015473thum.jpg
State of application right Registered
Reference ( R and D project ) (In Japanese)形状の対称性・規則性の自動認識システム
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close