(57)【要約】【課題】対象物品の計測メッシュからユークリッド対称性認識を行うユークリッド対称性認識システムを提供する。【解決手段】本発明は、計測メッシュに対してメッシュ各頂点の主曲率を計算し、メッシュ各頂点の主曲率を用いて、平面領域の境界近傍にある頂点集合を特徴領域として抽出し、特徴領域群から形状が一致するシード特徴領域ペアを抽出し、ＩＣＰ法とRegion Growing法により同一の変換パラメータでマッピング可能な頂点ペアを逐次的に各シード特徴領域に追加することで特徴領域ペアを拡大し、互いにユークリッド対称な領域ペアとそれらの変換パラメータを抽出し、ユークリッド対称な領域ペアから平面反射、回転若しくは平行移動で表現できる領域ペアを見出し、当該領域ペアと共に対称性を表現するシステムを特徴とする。【選択図】図２
2010014541.tif 000002
【特許請求の範囲】
【請求項１】
計測メッシュデータと必要な各種のデータを記憶するデータ記憶部と、
前記データ記憶部の計測メッシュデータに対してメッシュ各頂点の主曲率を計算するメッシュ主曲率算出部と、
前記計測メッシュデータのメッシュ各頂点の主曲率を用いて、平面領域の境界近傍にある頂点集合を特徴領域として抽出する特徴領域抽出部と、
前記特徴領域群から、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するシード特徴領域ペア抽出部と、
ＩＣＰ法とRegion Growing法により同一の変換パラメータでマッピング可能な頂点ペアを逐次的に各シード特徴領域に追加することで特徴領域ペアをそれぞれ反復的に拡大し、互いにユークリッド対称な領域ペアとそれらの変換パラメータを抽出するユークリッド対称領域ペア抽出部と、
前記ユークリッド対称な領域ペアとそれらの変換パラメータを評価し、単一平面反射、２−ｆｏｌｄ回転若しくは単一平行移動で表現できる領域ペアを見出し、当該領域ペアと共に対称性を表示する対称性表示部とを備えたことを特徴とするユークリッド対称性認識システム。
【請求項２】
前記シード特徴領域ペア抽出部は、
前記各特徴領域ペアの頂点数を比較する頂点数比較部と、
前記頂点数の比較にて所定の範囲内にある特徴領域ペアについて、重心・主軸一致によるマッチングとその精度を評価するマッチング評価部と、
ＩＣＰ法によりマッチングし、その精度を評価して所定の範囲内にある特徴領域ペアについてシード特徴領域ペアとして抽出するシード特徴領域ペア決定部とを有することを特徴とする請求項１に記載のユークリッド対称性認識システム。
【請求項３】
メッシュ各頂点の主曲率を計算するステップと、
前記メッシュ各頂点の主曲率を用いて、平面領域の境界近傍にある頂点集合を特徴領域として抽出するステップと、
特徴領域群に対して、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するステップと、
ＩＣＰ法とRegion Growing法を組み合わせて、同一の変換パラメータでマッピング可能な頂点ペアを逐次的に各シード特徴領域に追加することで領域ペアをそれぞれ反復的に拡大し、互いにユークリッド対称な領域ペアとそれらの変換パラメータを抽出するステップと、
前記ステップにて抽出した変換パラメータを評価し、単一平面反射、２−ｆｏｌｄ回転若しくは単一平行移動の対称性表現できる領域ペアを見出し、当該領域ペアと共に対称性を表示するステップとを有することを特徴とするユークリッド対称性認識方法。
【請求項４】
前記特徴領域群に対して、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するステップでは、
前記各特徴領域ペアの頂点数を比較するステップと、
前記頂点数の比較にて所定の範囲内にある特徴領域ペアについて、重心・主軸一致によるマッチングとその精度を評価するステップと、
ＩＣＰ法によりマッチングし、その精度を評価して所定の範囲内にある特徴領域ペアについてシード特徴領域ペアとして抽出するステップとを有することを特徴とする請求項３に記載のユークリッド対称性認識方法。
【請求項５】
メッシュ各頂点の主曲率を計算するステップと、
前記メッシュ各頂点の主曲率を用いて、平面領域の境界近傍にある頂点集合を特徴領域として抽出するステップと、
特徴領域群に対して、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するステップと、
ＩＣＰ法とRegion Growing法を組み合わせて、同一の変換パラメータでマッピング可能な頂点ペアを逐次的に各シード特徴領域に追加することで領域ペアをそれぞれ反復的に拡大し、互いにユークリッド対称な領域ペアとそれらの変換パラメータを抽出するステップと、
前記ステップにて抽出した変換パラメータを評価し、単一平面反射、２−ｆｏｌｄ回転若しくは単一平行移動の対称性表現できる領域ペアを見出し、当該領域ペアと共に対称性を表示するステップとをコンピュータに実行させることを特徴とするユークリッド対称性認識プログラム。
【請求項６】
前記特徴領域群に対して、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するステップでは、
前記各特徴領域ペアの頂点数を比較するステップと、
前記頂点数の比較にて所定の範囲内にある特徴領域ペアについて、重心・主軸一致によるマッチングとその精度を評価するステップと、
ＩＣＰ法によりマッチングし、その精度を評価して所定の範囲内にある特徴領域ペアについてシード特徴領域ペアとして抽出するステップとをコンピュータに実行させることを特徴とする請求項５に記載のユークリッド対称性認識プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計測メッシュから対象物のユークリッド対称性を自動認識するユークリッド対称性認識システム、方法及びプログラムに関する。
【背景技術】
【０００２】
近年、産業用高エネルギＸ線ＣＴ計測器の発達により、機械部品のような対象物品の計測メッシュが入手可能となり、製品開発の様々なプロセスで利用されるようになっている。ＣＡＤシステム上で機械部品の形状を定義する際には、その機能の観点から、部分ソリッドをコピーし、これを平行移動、回転、平面反射の組み合わせから成る変換により配置し定義することが多い。そのため、計測メッシュ上からこのような対称性を認識することで、対称性を反映させたコンパクトな定義を持つＣＡＤモデルが生成でき、製品開発の様々なプロセスでより有効に利用することができる。
【０００３】
近年の代表的な計測メッシュの対称性認識手法として、まず、非特許文献１に記載されているボクセル化と投票に基づくPodolakらの手法が挙げられる。このPodolakらの手法は平面反射対称性の認識のみを目的としており、平行移動や回転を含む対称性は認識できない。
【０００４】
これに対してMitraらは、非特許文献２にて、各頂点における主曲率・主方向算出と投票に基づく、平行移動、回転平面反射の任意の組み合わせから成る対称性を認識する手法を提案している。しかしながらこの手法では、主曲率・主方向を頂点毎に計算しているため、計測ノイズに対してロバストに認識することができないといった問題点があり、さらにそれらが一意に定義できない平面領域を多く含むメッシュからは対称性の認識ができないといった問題点がある。
【０００５】
これらの従来技術とは別に、Rusinkiewiczらの論文である非特許文献３に記載されているようなＩＣＰ（Iterative Closest Point)法が知られている。また、溝口氏らの論文である非特許文献４に記載されているようなRegion Growing法（領域拡大法）も知られている。
【非特許文献１】Podolak, J. et al., 2006, "A planar-reflective symmetry transform for 3D shapes" ACM TOG, 25(3), pp. 549-559.
【非特許文献２】Mitra, N. J. et al., 2006, "Partial and approximate symmetry detection for 3D geometry" ACM TOG, 25(3), pp. 560-568.
【非特許文献３】Rusinkiewicz, S. et al., 2007, "Efficient variants of the ＩＣＰ algorithm" proc. of 3DIM, pp. 145-152.
【非特許文献４】Mizoguchi, T. et al., 2007, "Quasi-optimal mesh segmentation via region growing/merging" proc. of ASME/DETC, 35171.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、上記従来技術の問題点に鑑み、非特許文献３に記載されているＩＣＰ法と非特許文献４に記載されているRegion Growing法を組み合わせて得た、平面領域を多く含む機械部品のような対象物品の計測メッシュから、測定ノイズに対してロバスト（robust）に計測メッシュのユークリッド対称性認識が行えるユークリッド対称性認識システム、方法及びプログラムを提供することを目的とする。
【０００７】
尚、本出願において計測メッシュのユークリッド対称性認識とは、平行移動、回転、平面反射の任意の組み合わせからなる変換によって互いに一致するメッシュ上の部分領域ペアとその変換パラメータとを計測メッシュから抽出することを意味する。
【課題を解決するための手段】
【０００８】
本発明の特徴は、計測メッシュデータと必要な各種のデータを記憶するデータ記憶部と、前記データ記憶部の計測メッシュデータに対してメッシュ各頂点の主曲率を計算するメッシュ主曲率算出部と、前記計測メッシュデータのメッシュ各頂点の主曲率を用いて、平面領域の境界近傍にある頂点集合を特徴領域として抽出する特徴領域抽出部と、前記特徴領域群から、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するシード特徴領域ペア抽出部と、ＩＣＰ法とRegion Growing法により同一の変換パラメータでマッピング可能な頂点ペアを逐次的に各シード特徴領域に追加することで特徴領域ペアをそれぞれ反復的に拡大し、互いにユークリッド対称な領域ペアとそれらの変換パラメータを抽出するユークリッド対称領域ペア抽出部と、前記ユークリッド対称な領域ペアとそれらの変換パラメータを評価し、単一平面反射、２−ｆｏｌｄ回転若しくは単一平行移動で表現できる領域ペアを見出し、当該領域ペアと共に対称性を表示する対称性表示部とを備えたユークリッド対称性認識システムである。
【０００９】
上記発明のユークリッド対称性認識システムでは、前記シード特徴領域ペア抽出部は、前記各特徴領域ペアの頂点数を比較する頂点数比較部と、前記頂点数の比較にて所定の範囲内にある特徴領域ペアについて、重心・主軸一致によるマッチングとその精度を評価するマッチング評価部と、ＩＣＰ法によりマッチングし、その精度を評価して所定の範囲内にある特徴領域ペアについてシード特徴領域ペアとして抽出するシード特徴領域ペア決定部とを有するものとすることができる。
【００１０】
本発明の別の特徴は、メッシュ各頂点の主曲率を計算するステップと、前記メッシュ各頂点の主曲率を用いて、平面領域の境界近傍にある頂点集合を特徴領域として抽出するステップと、特徴領域群に対して、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するステップと、ＩＣＰ法とRegion Growing法を組み合わせて、同一の変換パラメータでマッピング可能な頂点ペアを逐次的に各シード特徴領域に追加することで領域ペアをそれぞれ反復的に拡大し、互いにユークリッド対称な領域ペアとそれらの変換パラメータを抽出するステップと、前記ステップにて抽出した変換パラメータを評価し、単一平面反射、２−ｆｏｌｄ回転若しくは単一平行移動の対称性表現できる領域ペアを見出し、当該領域ペアと共に対称性を表示するステップとを有するユークリッド対称性認識方法である。
【００１１】
上記発明のユークリッド対称性認識方法では、前記特徴領域群に対して、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するステップは、前記各特徴領域ペアの頂点数を比較するステップと、前記頂点数の比較にて所定の範囲内にある特徴領域ペアについて、重心・主軸一致によるマッチングとその精度を評価するステップと、ＩＣＰ法によりマッチングし、その精度を評価して所定の範囲内にある特徴領域ペアについてシード特徴領域ペアとして抽出するステップとを有するものとすることができる。
【００１２】
本発明のさらに別の特徴は、メッシュ各頂点の主曲率を計算するステップと、前記メッシュ各頂点の主曲率を用いて、平面領域の境界近傍にある頂点集合を特徴領域として抽出するステップと、特徴領域群に対して、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するステップと、ＩＣＰ法とRegion Growing法を組み合わせて、同一の変換パラメータでマッピング可能な頂点ペアを逐次的に各シード特徴領域に追加することで領域ペアをそれぞれ反復的に拡大し、互いにユークリッド対称な領域ペアとそれらの変換パラメータを抽出するステップと、前記ステップにて抽出した変換パラメータを評価し、単一平面反射、２−ｆｏｌｄ回転若しくは単一平行移動の対称性表現できる領域ペアを見出し、当該領域ペアと共に対称性を表示するステップとをコンピュータに実行させるユークリッド対称性認識プログラムである。
【００１３】
上記発明のユークリッド対称性認識プログラムでは、前記特徴領域群に対して、形状が一致する特徴領域ペアをシード特徴領域ペアとして抽出するステップは、前記各特徴領域ペアの頂点数を比較するステップと、前記頂点数の比較にて所定の範囲内にある特徴領域ペアについて、重心・主軸一致によるマッチングとその精度を評価するステップと、ＩＣＰ法によりマッチングし、その精度を評価して所定の範囲内にある特徴領域ペアについてシード特徴領域ペアとして抽出するステップとをコンピュータに実行させるものとすることができる。
【発明の効果】
【００１４】
本発明のユークリッド対称性認識システム、方法及びプログラムによれば、対象物品の計測メッシュから平行移動、回転、平面反射の対称性を精度よく認識することができ、しかも平面領域を多く含む計測メッシュからのユークリッド対称性認識ができ、その上に、測定ノイズに対してロバストで、平行移動量に依存しない安定した認識ができ、さらに最大限大きな対称領域ペアを抽出して対称性と共に表現できる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施の形態を図に基づいて詳説する。
【００１６】
先ず、非特許文献３に記載されているＩＣＰ法について説明する。計測データペア〈X、Y〉のマッチングを行う手法として広く用いられている。この手法では、対応点の探索と変換パラメータの計算を反復的に行うことにより、点x'i∈X'とその対応点yc(i)∈Yとの点間距離の二乗和を最小化するよう、xiを
【数１】
2010014541.tif 000003
【００１７】
のようにx'iに変換するパラメータ
【数２】
2010014541.tif 000004
【００１８】
を求めることができる。尚、本明細書中では、ベクトルや行列について、符号に下線を施すことによりベクトルであることを示すことがある。
【００１９】
領域ペアをマッチングさせるための変換パラメータを求める際に、このＩＣＰ法を利用することは有効な手段ではあるが、このＩＣＰ法では、マッチングさせる領域ペアが単一の平面をサンプリングした領域である場合には適切に変換パラメータを計算することが困難である。
【００２０】
これを解決したのが本発明のユークリッド対称性認識システム、方法及びプログラムである。図１には、本発明の１つの実施の形態のユークリッド対称性認識システム１００を示している。本システム１００はコンピュータシステムにより構成されていて、ＨＭＩとしてキーボード２１、マウスその他のポインティングデバイス２２、ディスプレイ２３が接続されている。本システム１００内にソフトウェアとして組み込まれたユークリッド対称性認識プログラムは、機能毎に区別して表示すると、外部とのデータの送受信、上記ＨＭＩとの信号の送受信を行う入出力制御部１、計測メッシュデータその他の演算処理データを記憶するデータ記憶部２、後述するＳｔｅｐ１の処理を行うメッシュ主曲率算出部３と特徴領域抽出部４、Ｓｔｅｐ２の処理を行うシード特徴領域ペア抽出部５、Ｓｔｅｐ３の処理を行うＩＣＰ処理部６と領域拡大処理部７、Ｓｔｅｐ４のユークリッド対称性を認識するユークリッド対称性認識処理部８、そしてこれらの演算処理を総合的に制御する演算制御処理部９から構成されている。
【００２１】
そして、シード特徴領域ペア抽出部５は、各特徴領域ペアの頂点数を比較する頂点数比較部５１と、頂点数の比較にて所定の範囲内にある特徴領域ペアについて、重心・主軸一致によるマッチングとその精度を評価するマッチング評価部５２と、ＩＣＰ法によりマッチングし、その精度を評価して所定の範囲内にある特徴領域ペアについてシード特徴領域ペアとして抽出するシード特徴領域ペア決定部５３とを有している。
【００２２】
次に、上記の実施の形態のユークリッド対称性認識システムによるユークリッド対称性認識方法について説明する。図２に示すように、まず、メッシュ各頂点の主曲率を計算し、これを利用して平面領域の境界近傍にある頂点集合を特徴領域（feature region）として抽出する(Ｓｔｅｐ１)。
【００２３】
次に、各特徴領域ペアに対して、後述するＳｔｅｐ２−１：頂点数比較、Ｓｔｅｐ２−２：重心・主軸一致によるマッチングとその精度評価、Ｓｔｅｐ２−３：ＩＣＰ法によるマッチングとその精度評価、の３つの手順を実行し、その形状がおおよそ一致する特徴領域ペアをシード特徴領域ペア（pair of seed feature regions）として抽出する（Ｓｔｅｐ２）。
【００２４】
次に、ＩＣＰ法と非特許文献４に記載されているRegion Growing法を組み合わせた手法を用いて、同一の変換パラメータでマッピング可能な頂点ペアを逐次的に各シード特徴領域に追加することで領域ペアをそれぞれ反復的に拡大し、互いにユークリッド対称な領域ペアとそれらの変換パラメータを抽出する（Ｓｔｅｐ３）。
【００２５】
最後に、Ｓｔｅｐ３で抽出した変換パラメータを評価し、単一平面反射、２−ｆｏｌｄ回転、単一平行移動で表現できるものは、それらを利用した陽な対称性表現に変換する（Ｓｔｅｐ４）。
【００２６】
Ｓｔｅｐ１の主曲率計算に基づく特徴領域の抽出処理は、図３のフローチャート、図４の説明図を用いて説明する。まず、各メッシュ頂点viの主曲率（max curvature）を計算し（Ｓｔｅｐ１−１）、求めた主曲率に基づき、シャープ頂点(sharp vertex)と非シャープ頂点（non-sharp vertex）を分類する（Ｓｔｅｐ１−２）。これには、非特許文献４に記載され、また本願発明者らによる先の出願、特願２００７−０１５４７３に記載された方法を用いる。
【００２７】
すなわち、ノイズの多いメッシュモデル上のメッシュ曲率を算出するために、最初に、各頂点xiの周りの頂点群N(i)に対して（１）式で表わされる二次多項式曲面h(u,v)をフィッティングする。
【数３】
2010014541.tif 000005
【００２８】
ここで、N(i)は各頂点xiに対して位相的に連結されている頂点群（該頂点xiも含む）であり、（２）式を満たす隣接頂点群である。
【数４】
2010014541.tif 000006
【００２９】
ここで、li,avgは頂点群N(i)に含まれるエッジ集合の平均エッジ長さであり、Wは曲面フィットのサイズを特定する変数である。Wは経験的に３．０とするのが好ましい。
【００３０】
このフィッティングにて、頂点xiにおける二次多項式曲面h(u,v)の主曲率ki,max，ki,minを算出する。
【００３１】
続いて、頂点xiの最大曲率ki,maxが（３）式を満たすなら、その頂点はシャープ頂点であると分類する。
【数５】
2010014541.tif 000007
【００３２】
閾値thsharpは対象物品の形状や計測メッシュの解像度に応じて設定されるべきものであるが、１０．０に設定すると計測メッシュモデルに対して良い結果が得られる。
【００３３】
図４（ｂ）には、これを利用してシャープ頂点、非シャープ頂点（sharp vertical, non-sharp verticle）に分類した結果を示している。この図４（ｂ）では、シャープ頂点群は濃い色にて非シャープ頂点と区別してある。
【００３４】
次に、図４（ｃ）のように、シャープ頂点を要素として含まない、位相的に連結された非シャープ頂点集合を初期領域IRjとして抽出する（Ｓｔｅｐ１−３）。また、抽出された初期領域IRjに対して最小二乗平面をフィットし、その平均誤差eiを計算する。この誤差eiがトレランスτplalavg以下であれば、図４（ｄ）のようにIRjを平面領域PRkとして抽出する（Ｓｔｅｐ１−４）。ここで、lavgはメッシュの平均稜線長である。通常τpla＝０．５に設定するのが好ましい。
【００３５】
次に図４（ｅ）のように、抽出された平面領域PRk内の、位相的に連結された領域境界頂点集合をBRlとして抽出する（Ｓｔｅｐ１−５）。そして最後に、図４（ｆ）のように、各領域境界頂点集合BRlからあるユークリッド距離Wlavg内にあり、平面領域PRk内にはない頂点集合を特徴領域
【数６】
2010014541.tif 000008
【００３６】
として抽出する（Ｓｔｅｐ１−６）。通常W＝１０．０〜２０．０に設定するのが好ましい。この例では、W＝１０．０を用いている。
【００３７】
Ｓｔｅｐ２のシード特徴領域ペアの抽出処理を、図５のフローチャートと図６の説明図を用いて説明する。この処理の目的は、ある変換のもとで形状がほぼ一致する特徴領域ペアを抽出することである。そのために、すべての特徴領域ペア〈FRi,FRj〉に対して、以下の手順でその形状類似度を評価し、シード特徴領域ペアを生成する。平面反射対称性をも認識するため、各特徴領域FRiと鏡像の関係にあるFRirefを含めたペア〈FRiref,FRj〉をも処理の対象とするが、これらは〈FRi,FRj〉と同様の手法で扱えるため、説明は特徴領域ペア〈FRi,FRj〉のみに限定する。
【００３８】
Ｓｔｅｐ２−１では、頂点数比較を行う。そのために、特徴領域ペア〈FRi,FRj〉の頂点数｜FRi｜、｜FRj｜を比較し、これが、1.0-α/100＜｜FRi｜/｜FRj｜＜1.0+α/100を満たすならば、次のＳｔｅｐ２−２に進み、そうでなければ処理を終了する（Ｓｔｅｐ２−１Ａ）。通常、α＝１０．０〜１５．０に設定するが、この例ではα＝１５．０に設定している。
【００３９】
Ｓｔｅｐ２−２では、重心・主軸一致と平均最近点間距離を評価する。重心biをbjに、主軸AiをAjに一致させるための変換パラメータ
【数７】
2010014541.tif 000009
【００４０】
を計算し、これを利用して特徴領域FRi内の各頂点vi,kを
【数８】
2010014541.tif 000010
【００４１】
と変換し、これにより特徴領域FRiを特徴領域FRjにマッチングする。ここで、
【数９】
2010014541.tif 000011
【００４２】
であり、特徴領域FRi内の頂点vi,kに対して、
【数１０】
2010014541.tif 000012
【００４３】
のように変換する。そして、主軸AiとAjを一致させる回転行列Rijを計算し、その後、重心bjの周りに各頂点を次のように回転させることを意味している。
【数１１】
2010014541.tif 000013
【００４４】
さらに、形状類似度を評価するため、ランダムに選択されたβ（％）の各v"i,kに対して、FRjの中からv"i,kとの点間距離が最小となる頂点vj,c(k)を見つけ、その点間距離eij,kpcaを計算する。（ここで、アンダーラインを付けていない符号v"i,kは頂点ベクトルv"i,kの頂点名である。）通常、β＝５．０に設定するのが好ましい。また、c(k)はv"i,kの特徴領域FRj内にある最近点vi,c(k)のインデックスである。最後に、平均点間距離eijpcaを計算し、これがトレランスτpcalavg以下であれば、Ｓｔｅｐ２−３に進み、そうでなければ処理を終了する。通常τpca＝３．０に設定するのが好ましい。
【００４５】
Ｓｔｅｐ２−３では、ＩＣＰ法によるマッチングと精度評価を行う。ここではＩＣＰ法を用いて特徴領域FR'jをFRjにマッチングし、Ｓｔｅｐ２−２の処理と同様に平均点間距離eijicpを計算する。ここで平均点間距離eijicpがトレランスτicplavg以下であれば、〈FRi,FRj〉をシード特徴領域ペア〈FRiseed,FRjseed〉として抽出する。通常τicp＝１．０に設定するのが好ましい。
【００４６】
図６には抽出されたシード特徴領域ペアの例を示している。図４（ｆ）に示す抽出された１５の特徴領域群の中から、図６（ａ）は、平行移動と回転のペア、図６（ｂ）は平行移動と回転と平面反射のペア、図６（ｃ）は平行移動と回転と平面反射のペア、図６（ｄ）は平行移動と回転のペア、図６（ｅ）は平行移動と回転と平面反射のペア、図６（ｆ）は平行移動と回転、さらに平行移動と回転と平面反射のペアを示している。１つの特徴領域に対して複数のペアが抽出され得るので、抽出されるペア数はさらに多数に上る。
【００４７】
この後、Ｓｔｅｐ３のＩＣＰ法とRegion Growing法の組み合わせによるユークリッド対称性認識の処理に移行する。このＳｔｅｐ３の処理を、図７のフローチャートと図８の説明図を用いて説明する。抽出したすべてのシード特徴領域ペア
【数１２】
2010014541.tif 000014
【００４８】
を初期ユークリッド対称領域ペア、
【数１３】
2010014541.tif 000015
【００４９】
にまず設定し、以下の手順でそれぞれの領域SRi10，SRi20を反復的に拡大し、最終的なユークリッド対称領域ペアとその変換パラメータを抽出する。
【００５０】
そのために、Ｓｔｅｐ３−１において、初期変換パラメータの計算と初期マッチングを行う。この処理は、Ｓｔｅｐ２−２の処理と同様の処理であり、領域SRi10，SRi20に対して初期変換パラメータ
【数１４】
2010014541.tif 000016
【００５１】
を計算し、これをもとに頂点を
【数１５】
2010014541.tif 000017
【００５２】
と更新し、初期マッチングを行う。ここで、この処理の繰り返しを表す変数itrを、itr＝０に初期化する。
【００５３】
続く、Ｓｔｅｐ３−２では、変換パラメータの計算とマッチングの処理を行う。そのために、ＩＣＰ法を用いて
【数１６】
2010014541.tif 000018
【００５４】
を領域SRi20にマッチングする変換パラメータ
【数１７】
2010014541.tif 000019
【００５５】
を計算し、これをもとに頂点を
【数１８】
2010014541.tif 000020
【００５６】
と更新し、これよりマッチングを行う。
【００５７】
次のＳｔｅｐ３−３では、領域拡大処理を行う。この領域拡大は図８を用いて説明する。図８（ａ）において、v"il,kitr+1とvi2,c(k)0はシード特徴領域内にあり、次の変換にてv"il,kitr+1はvi2,c(k)0にマッチしている。
【数１９】
2010014541.tif 000021
【００５８】
次に、図８（ｂ）に示すように、新たにすべての可能なペア
【数２０】
2010014541.tif 000022
【００５９】
を生成する。各ペアは、
v"il,kitr+1を含むその１近傍隣接頂点集合
【数２１】
2010014541.tif 000023
【００６０】
と、vi2,c(k)0を含むその１近傍頂点集合
【数２２】
2010014541.tif 000024
【００６１】
のうちから選択されたものである。この図８の例では、４８ペアが生成される。
【００６２】
各頂点間距離ei,sを計算し、その頂点間距離ei,sが閾値τaddlavg以下であれば、図８（ｃ）に示すように、そのv"i1,sitr+1をSR"i10に、vi2,c(s)0をSRi20にそれぞれ追加する。そしてこの処理を、条件を満たす頂点が存在しなくなるまで続け、拡大された領域SR"i1itr+1とSRi2itr+1を抽出する。通常τadd＝１．０に設定するのが好ましい。
【００６３】
Ｓｔｅｐ３−４にて終了条件を判断する。もし、｜SR"i1itr+1｜＞｜SR"i1itr｜であれば、itr←itr+1と更新し、Ｓｔｅｐ３−２に戻る。そうでなければ、〈SRi1itr,SRi2itr〉をユークリッド対称領域ペアとして抽出し（Ｓｔｅｐ３−５）、さらに、
【数２３】
2010014541.tif 000025
【００６４】
から最終変換パラメータを
【数２４】
2010014541.tif 000026
【００６５】
として抽出し、このＳｔｅｐ３全体の処理を終了する（Ｓｔｅｐ３−６）。
【００６６】
続くＳｔｅｐ４では、コンパクトな対称性表現の抽出を行う。この手順を図９のフローチャートを用いて説明する。Ｓｔｅｐ３で抽出された数２４式の最終変換パラメータを単一平面反射、２−ｆｏｌｄ回転、単一平行移動といった対称性を表す陽な表現に変換する。
【００６７】
Ｓｔｅｐ４−１，２にて、単一平面反射対称性を判断する。単一平面反射の場合、対称領域ペア〈SRi1itr,SRi2itr〉内の各点ペア
【数２５】
2010014541.tif 000027
【００６８】
の中点はその反射平面上に分布する。そこでこの中点集合に対し最小二乗平面をフィットし、次に領域SRi1itr内の各点vi1,sitrをこの平面に対して反射させ、反射後の点vi1,srefと対応点vi2,c(s)0との平均点間距離eirefを計算する。この平均点間距離eirefが閾値threflavg以下であれば、単一平面反射対称性であると判定し、反射平面を抽出する。ここで、全てthref＝１．０に設定する。
【００６９】
同様にＳｔｅｐ４−３，４の２−ｆｏｌｄ回転の場合は、その中点に最小二乗直線をフィットし、その軸周りの回転後の平均点間距離を評価し判定を行い、２−ｆｏｌｄ回転軸を抽出する。
【００７０】
Ｓｔｅｐ４−５，６の単一平行移動の場合は、対応点間を結ぶベクトルの平均ベクトルを計算し、そのベクトルに沿った平行移動後の平均点間距離を評価し判定を行い、平行移動ベクトルを抽出する。
【００７１】
［実施例］
実験結果は図１０に示している。図１０は、頂点数約１２万の、コンロッドのＸ線ＣＴ計測メッシュに対する実験結果を示している。このモデルからは１５個の特徴領域が抽出され、平行移動、回転、平面反射の組み合わせから成る２０個のユークリッド対称性が認識できた。これらのうち、図１０（ｂ）、図１０（ｄ）に示す２つの大局的な単一平面反射対称性が認識できた。また、２つの反射平面の法線ベクトル間角度が約８９．７ｄｅｇであったことから、本発明方法により、高精度に対称性が認識できることが確認できた。計算時間は、Ｃｏｒｅ２ Ｄｕｏ ２．４ＧＨｚ ＣＰＵで約９８秒であった。
【図面の簡単な説明】
【００７２】
【図１】本発明の１つの実施の形態のユークリッド対称性認識システムのブロック図。
【図２】上記実施の形態のユークリッド対称性認識システムによるユークリッド対称性認識処理のフローチャート。
【図３】上記実施の形態のユークリッド対称性認識処理における特徴領域抽出処理のフローチャート。
【図４】上記実施の形態のユークリッド対称性認識処理における特徴領域抽出処理の説明図。
【図５】上記実施の形態のユークリッド対称性認識処理におけるシード特徴領域ペア抽出処理のフローチャート。
【図６】上記実施の形態のユークリッド対称性認識処理におけるシード特徴領域ペア抽出処理の説明図。
【図７】上記実施の形態のユークリッド対称性認識処理におけるユークリッド対称領域ペア抽出処理のフローチャート。
【図８】上記実施の形態のユークリッド対称性認識処理におけるユークリッド対称領域ペア抽出処理の説明図。
【図９】上記実施の形態のユークリッド対称性認識処理における対称性表現処理のフローチャート。
【図１０】本発明の実施例の説明図。
【符号の説明】
【００７３】
１  入出力制御部
２  データ記憶部
３  メッシュ主曲率算出部
４  特徴領域抽出部
５  シード特徴領域ペア抽出部
６  ＩＣＰ処理部
７  領域拡大処理部
８  ユークリッド対称性認識処理部
９  演算制御部
５１  頂点数比較部
５２  マッチング評価部
５３  シード特徴領域ペア決定部
１００  ユークリッド対称性認識システム
【図１】
2010014541.tif 000028
【図２】
2010014541.tif 000029
【図３】
2010014541.tif 000030
【図４】
2010014541.tif 000031
【図５】
2010014541.tif 000032
【図６】
2010014541.tif 000033
【図７】
2010014541.tif 000034
【図８】
2010014541.tif 000035
【図９】
2010014541.tif 000036
【図１０】
2010014541.tif 000037