(57)【要約】【課題】  異なるＣＡＤシステム間で交換されたＣＡＤデータの中に存在する傷を自動的に修復できるようにした、ＣＡＤシステム間で交換されたデータの修復方法を提供する。【解決手段】  異なるＣＡＤシステム間で交換された２次元ＣＡＤデータの中に存在する傷を自動的に修復する、ＣＡＤシステム間で交換されたデータの修復方法であって、前記２次元ＣＡＤデータに表される２次元画像上の傷の部分ＷＲを範囲指定するステップと、範囲指定された前記傷の部分ＷＲを適度に広げた領域Ｗ＋を指定するステップと、前記領域Ｗ＋から前記傷の部分ＷＲを引いた領域ＷＬに対して、ＣＳＲＢＦ法を用いて、関数データを求めるステップと、求められた前記関数データを用いて、前記傷の部分ＷＲの補間を行い、前記領域Ｗ＋を修復するステップとを有するようにする。【選択図】  図８
2005190045.tif 000002
【特許請求の範囲】
【請求項１】
異なるＣＡＤシステム間で交換された２次元ＣＡＤデータの中に存在する傷を自動的に修復する、ＣＡＤシステム間で交換されたデータの修復方法であって、
前記２次元ＣＡＤデータに表される２次元画像上の傷の部分ＷＲを範囲指定するステップと、
範囲指定された前記傷の部分ＷＲを適度に広げた領域Ｗ＋を指定するステップと、
前記領域Ｗ＋から前記傷の部分ＷＲを引いた領域ＷＬに対して、ＣＳＲＢＦ法を用いて、関数データを求めるステップと、
求められた前記関数データを用いて、前記傷の部分ＷＲの補間を行い、前記領域Ｗ＋を修復するステップと、
を有することを特徴とするＣＡＤシステム間で交換されたデータの修復方法。
【請求項２】
異なるＣＡＤシステム間で交換された２次元ＣＡＤデータの中に存在する傷を自動的に修復する、ＣＡＤシステム間で交換されたデータの修復方法であって、
前記２次元ＣＡＤデータに表される２次元画像上の傷の部分を範囲指定する第１のステップと、
前記範囲指定された傷の部分の範囲内の所定の点を決定する第２のステップと、
前記第２のステップで決定された前記傷の部分の所定の点を中心に隣接する所定の周辺領域部分を特定する第３のステップと、
前記第３のステップで特定された前記所定の周辺領域部分に対して、ＣＳＲＢＦ法を用いて、関数データを求める第４のステップと、
前記第４のステップで求められた前記関数データを用いて、前記傷の部分の所定の点を補間して、前記傷の部分の所定の点の修復を行う第５のステップと、
傷の部分の次の所定の点を決定する第６のステップと、
前記第６のステップで決定された前記傷の部分の次の所定の点を中心に隣接する所定の周辺領域部分を特定する第７のステップと、
前記第７のステップで特定された前記所定の周辺領域部分に対して、ＣＳＲＢＦ法を用いて、関数データを求める第８のステップと、
前記第８のステップで求められた前記関数データを用いて、前記傷の部分の次の所定の点を補間して、前記傷の部分の次の所定の点の修復を行う第９のステップと、
前記第１のステップで範囲指定された前記傷の部分の全ての傷の修復が終了するまでに、前記第９のステップで修復された前記傷の部分の次の所定の点を傷の部分の所定の点とし、前記第６のステップに戻る第１０のステップと、
を有し、
前記第７のステップで特定された前記所定の周辺領域部分は、傷の部分の所定の点を含むようになっており、
前記第９のステップにおいて、前記傷の部分の次の所定の点の修復の際には、傷の部分の所定の点の修復後のデータを用いるようにすることを特徴とするＣＡＤシステム間で交換されたデータの修復方法。
【請求項３】
異なるＣＡＤシステム間で交換された３次元ＣＡＤデータの中に存在する傷を自動的に修復する、ＣＡＤシステム間で交換されたデータの修復方法であって、
前記３次元ＣＡＤデータに表される３次元画像上の多角形の傷の部分で境界になり得る全ての境界辺を見つけ出し、得られた境界辺から閉折線を構成する、傷の輪郭抽出ステップと、
前記閉折線で表される多角形の傷を三角形分割して縫い合わせて修復を行う、輪郭の縫い合わせステップと、
前記輪郭の縫い合わせステップで得られた三角形分割による傷部分に対し、所定のアルゴリズムで表面の再構成を行い、スムージングをする、スムージングステップと、
を有し、
前記所定のアルゴリズムは、
前記輪郭の縫い合わせステップで得られた各三角形に対し、傷内部の詳細な点データを求めるステップと、
傷の部分ＷＲを適度に広げた領域をＷ＋とし、前記Ｗ＋から前記傷の部分ＷＲを引いた領域をＷＬとするステップと、
領域ＷＬに対して、ＣＳＲＢＦ法を用いて、関数データを求めるステップと、
求められた関数データを用いて、前記傷内部の詳細な点データで補間を行い、前記領域ＷＬの修復をするステップと、
を有することを特徴とするＣＡＤシステム間で交換されたデータの修復方法。
【請求項４】
前記ＣＳＲＢＦ法における基底関数は、
2005190045.tif 000016
但し、ｒ（Ｐｉ，Ｐｊ）は、複数の離散点の中の任意の２点ＰｉとＰｊの距離
ｒ０は、初期値として与える任意の点Ｐｉを中心とした半径
と定義され、そのときの関数データは、
2005190045.tif 000017
但し、λｉ（ｉ＝１，２，．．．，Ｎ）は点Ｐｉにおける基底関数の係数
λＮ＋１，λＮ＋２，λＮ＋３，λＮ＋４は１次項の係数
で表わされる関数により与えられ、
前記係数λｉ，λＮ＋１，λＮ＋２，λＮ＋３，λＮ＋４の計算は、補間行列を対角化する高速アルゴリズムを用いて行い、
前記高速アルゴリズムは、
前記複数の離散点が含まれる初期データから１つの点がリストに加えられ、前記リストに加えられた点は前記初期データから除かれる第１ステップと、
前記第１ステップで加えられた点に対する近傍点が、前記初期データの中から検索されて前記リストに加えられ、前記リストに加えられた点は前記初期データから除かれる第２ステップと、
前記第２ステップで加えられた点に対する近傍点が、前記初期データの中から検索されて前記リストに加えられ、前記リストに加えられた点は前記初期データから除かれる第３ステップと、
前記リストに加えられる点が無くなったら、前記初期データに残っている離散点から１つの点が前記リストに加えられ、前記リストに加えられた点は前記初期データから除かれる第４ステップと、
前記初期データに離散点がすべて無くなるまで、これらの前記第１ステップから前記第４ステップが繰り返され、バンド性を持つ対角行列が作成される第５ステップと、
を有する請求項１乃至請求項３の何れかに記載のＣＡＤシステム間で交換されたデータの修復方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異なったＣＡＤシステム間に交換されたＣＡＤデータの不具合（つまり、傷）を修復できる、データの修復方法に関するものである。
【背景技術】
【０００２】
ＣＡＤデータ交換とは、異なるＣＡＤシステム間で、２次元または３次元のＣＡＤデータを交換することをいう。異なったＣＡＤシステム間のデータの交換は古くからの課題であり、従来、共通のデータ交換規格として、例えば、ＩＧＥＳ（Initial  Graphics  Exchange  Specification）（いくつかのバージョンは米国標準になっている）やＩＳＯ（国際標準化機関）のＣＡＤデータ交換規格としてのＳＴＥＰ（ＩＳＯ１０３０３）が定められている。
【０００３】
しかし、実際、ＣＡＤデータ交換時において、特にソリッドとなると、幾何変換の誤差問題や位相表現の不一致が問題となり、さらにフィーチャー単位の情報まで双方向に完全保証するためには、実質的に形状生成履歴までを含んで内部表現が全く同一という条件がつく（非特許文献１参照）。
【非特許文献１】「デジタルプロセスのためのＣＡＥ」,日本機械学会講習会教材,Ｎｏ.９８−２２,1998年3月
【発明の開示】
【発明が解決しようとする課題】
【０００４】
それ故に、データ交換されたＣＡＤデータからメッシュを作成する場合に、しばしば要素間のつながりがなくなったりするといった問題が生じる。また、解析に不用な穴の存在でメッシュの作成が困難であったり、或いは、無用にメッシュが細かくなりすぎるといった問題も生じる。
【０００５】
従来、ＣＡＤシステム分野では、ＣＡＤデータ交換によって生じたＣＡＤデータの不具合、より具体的に、つまり、異なるＣＡＤシステム間でデータ間の授受を行った際の構造形状の完全なる復元ができないことによる修正、また、ＣＡＤは通常ＣＡＭにつながる形で開発されており、解析に必要な情報に比べて格段に細かいため、例えば解析に不用な細かい穴を埋めるなどの修正は、全て人手での手作業の修正となり、あるいは、クローニングのアプローチが利用される場合、クローニングのアプローチでは、小さな傷についてでさえも冗長な作業が強いられ、計算コストがかかるといった問題がある。
【０００６】
なお、以下では、異なるＣＡＤシステム間で交換されたＣＡＤデータの中に修復すべき部分（つまり、上述したような不都合な部分）を傷と定義する。
【０００７】
本発明は、上述のような事情よりなされたものであり、本発明の目的は、異なるＣＡＤシステム間で交換されたＣＡＤデータの中に存在する傷を自動的に修復できるようにした、ＣＡＤシステム間で交換されたデータの修復方法を提供することにある。
【課題を解決するための手段】
【０００８】
本発明は、ＣＡＤシステム間で交換されたデータの修復方法に関し、本発明の上記目的は、異なるＣＡＤシステム間で交換された２次元ＣＡＤデータの中に存在する傷を自動的に修復する、ＣＡＤシステム間で交換されたデータの修復方法であって、前記２次元ＣＡＤデータに表される２次元画像上の傷の部分ＷＲを範囲指定するステップと、範囲指定された前記傷の部分ＷＲを適度に広げた領域Ｗ＋を指定するステップと、前記領域Ｗ＋から前記傷の部分ＷＲを引いた領域ＷＬに対して、ＣＳＲＢＦ法を用いて、関数データを求めるステップと、求められた前記関数データを用いて、前記傷の部分ＷＲの補間を行い、前記領域Ｗ＋を修復するステップとを有するようにすることによって達成される。
【０００９】
また、本発明の上記目的は、異なるＣＡＤシステム間で交換された２次元ＣＡＤデータの中に存在する傷を自動的に修復する、ＣＡＤシステム間で交換されたデータの修復方法であって、前記２次元ＣＡＤデータに表される２次元画像上の傷の部分を範囲指定する第１のステップと、前記範囲指定された傷の部分の範囲内の所定の点を決定する第２のステップと、前記第２のステップで決定された前記傷の部分の所定の点を中心に隣接する所定の周辺領域部分を特定する第３のステップと、前記第３のステップで特定された前記所定の周辺領域部分に対して、ＣＳＲＢＦ法を用いて、関数データを求める第４のステップと、前記第４のステップで求められた前記関数データを用いて、前記傷の部分の所定の点を補間して、前記傷の部分の所定の点の修復を行う第５のステップと、傷の部分の次の所定の点を決定する第６のステップと、前記第６のステップで決定された前記傷の部分の次の所定の点を中心に隣接する所定の周辺領域部分を特定する第７のステップと、前記第７のステップで特定された前記所定の周辺領域部分に対して、ＣＳＲＢＦ法を用いて、関数データを求める第８のステップと、前記第８のステップで求められた前記関数データを用いて、前記傷の部分の次の所定の点を補間して、前記傷の部分の次の所定の点の修復を行う第９のステップと、前記第１のステップで範囲指定された前記傷の部分の全ての傷の修復が終了するまでに、前記第９のステップで修復された前記傷の部分の次の所定の点を傷の部分の所定の点とし、前記第６のステップに戻る第１０のステップとを有し、前記第７のステップで特定された前記所定の周辺領域部分は、傷の部分の所定の点を含むようになっており、前記第９のステップにおいて、前記傷の部分の次の所定の点の修復の際には、傷の部分の所定の点の修復後のデータを用いるようにすることによって達成される。
【００１０】
また、本発明の上記目的は、異なるＣＡＤシステム間で交換された３次元ＣＡＤデータの中に存在する傷を自動的に修復する、ＣＡＤシステム間で交換されたデータの修復方法であって、前記３次元ＣＡＤデータに表される３次元画像上の多角形の傷の部分で境界になり得る全ての境界辺を見つけ出し、得られた境界辺から閉折線を構成する、傷の輪郭抽出ステップと、前記閉折線で表される多角形の傷を三角形分割して縫い合わせて修復を行う、輪郭の縫い合わせステップと、前記輪郭の縫い合わせステップで得られた三角形分割による傷部分に対し、所定のアルゴリズムで表面の再構成を行い、スムージングをする、スムージングステップとを有し、前記所定のアルゴリズムは、前記輪郭の縫い合わせステップで得られた各三角形に対し、傷内部の詳細な点データを求めるステップと、傷の部分ＷＲを適度に広げた領域をＷ＋とし、前記Ｗ＋から前記傷の部分ＷＲを引いた領域をＷＬとするステップと、領域ＷＬに対して、ＣＳＲＢＦ法を用いて、関数データを求めるステップと、求められた関数データを用いて、前記傷内部の詳細な点データで補間を行い、前記領域ＷＬの修復をするステップとを有するようにすることによって達成される。
【００１１】
さらに、本発明の上記目的は、前記ＣＳＲＢＦ法における基底関数は、
2005190045.tif 000003
但し、ｒ（Ｐｉ，Ｐｊ）は、複数の離散点の中の任意の２点ＰｉとＰｊの距離
ｒ０は、初期値として与える任意の点Ｐｉを中心とした半径
と定義され、そのときの関数データは、
2005190045.tif 000004
但し、λｉ（ｉ＝１，２，．．．，Ｎ）は点Ｐｉにおける基底関数の係数
λＮ＋１，λＮ＋２，λＮ＋３，λＮ＋４は１次項の係数
で表わされる関数により与えられ、前記係数λｉ，λＮ＋１，λＮ＋２，λＮ＋３，λＮ＋４の計算は、補間行列を対角化する高速アルゴリズムを用いて行い、前記高速アルゴリズムは、前記複数の離散点が含まれる初期データから１つの点がリストに加えられ、前記リストに加えられた点は前記初期データから除かれる第１ステップと、前記第１ステップで加えられた点に対する近傍点が、前記初期データの中から検索されて前記リストに加えられ、前記リストに加えられた点は前記初期データから除かれる第２ステップと、前記第２ステップで加えられた点に対する近傍点が、前記初期データの中から検索されて前記リストに加えられ、前記リストに加えられた点は前記初期データから除かれる第３ステップと、前記リストに加えられる点が無くなったら、前記初期データに残っている離散点から１つの点が前記リストに加えられ、前記リストに加えられた点は前記初期データから除かれる第４ステップと、前記初期データに離散点がすべて無くなるまで、これらの前記第１ステップから前記第４ステップが繰り返され、バンド性を持つ対角行列が作成される第５ステップとを有するようにすることによって達成される。
【発明の効果】
【００１２】
本発明に係るＣＡＤシステム間で交換されたデータの修復方法によれば、異なるＣＡＤシステム間でデータ間の授受を行った際の構造形状の完全なる復元ができないことに起因した傷を修復することができる。
【００１３】
また、本発明によれば、ＣＡＤデータの中に存在する、ＣＡＭ解析に不用な細かい穴を埋めるといった修正を自動的に行うこともできる。つまり、こういった不用な細かい穴を傷とし、本発明を適用すればいい訳である。
【００１４】
更に、本発明によれば、例えば、これまで自動車の衝突解析モデルの開発に約３ケ月を要したが、１ケ月程の短縮が得られるという優れた効果を奏する。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施の形態を図面を参照して説明する。
【００１６】
本発明に係るＣＡＤシステム間で交換されたデータの修復方法では、ＣＳＲＢＦ（compactly  supported  radial  basis  functions）技術及びＬＣＳＲＢＦ（local  compactly  supported  radial  basis  functions）技術を使用することによって、ＣＡＤデータに表される構造を部分に分け、解析に不適な形状を探し出しスムーズな形状となるよう修正することを最大の特徴としている。
【００１７】
本発明では、ＣＡＤシステム分野に生じた上述のような従来問題を画像の修復技術で解決することに主眼を置く。
【００１８】
本発明で用いられるＣＳＲＢＦ技術とは、物体の表面を再構成する技術のうちの１つであり、離散点（ｘ，ｙ，ｚ）から陰関数ｆ（ｘ，ｙ，ｚ）を生成するものである。ＣＳＲＢＦ法における基底関数は、以下のように定義される。即ち、
【００１９】
【数１】
2005190045.tif 000005
但し、ｒ（Ｐｉ，Ｐｊ）は、複数の離散点の中の任意の２点ＰｉとＰｊの距離で、ｒ０は、初期値として与える任意の点Ｐｉを中心とした半径である。そして、任意の点Ｐｉを中心とした半径ｒ０の球に対し、その球内のすべての離散点について、中心Ｐｉとの距離を求める。このとき、関数データは、以下のように表わされる関数により与えられる。
【００２０】
【数２】
2005190045.tif 000006
但し、λｉ（ｉ＝１，２，．．．，Ｎ）は点Ｐｉにおける基底関数の係数で、λＮ＋１，λＮ＋２，λＮ＋３，λＮ＋４は１次項の係数である。本発明で用いられるＣＳＲＢＦ法は、この関数を用いて表面再構成を行うものである。
【００２１】
なお、関数データとは、具体的には、上記ｆ（ｘ，ｙ，ｚ）の関数が格納されている画像データのことである。これは、上記の関数のみが格納されたデータであっても、他の情報が含まれるものであっても構わない。
【００２２】
上記のように与えられた関数のうち、スプライン係数λｉ，λＮ＋１，λＮ＋２，λＮ＋３，λＮ＋４の計算において、本発明で用いられるＣＳＲＢＦ法では、計算上構成される補間行列（ＳＬＡＥ行列）を、八分木に基づいたバンド性を持つ対角行列に作り替えるための高速アルゴリズムを用いる。これは、多くの離散点が存在する場合でも、コンピュータにおける計算量を減らすために行われるものである。なお、スプライン係数をすべて重ね合わせると、すべての点を通る滑らかな関数系が作成できる。
【００２３】
以下に、本発明で用いられるＣＳＲＢＦ法において、対角化するための高速アルゴリズムの流れを図１を用いて詳細に説明する。先ず、複数の離散点が含まれる初期データ（input  list）から１つの点がリスト（output  list）に加えられ（ステップ２１）、リストに加えられた点は初期データから削除される（ステップ２２）。そして、加えられた点に対する近傍点が、初期データの中から検索される（ステップ２３）。近傍点が有れば（ステップ２４）、再度ステップ２１に戻り、その点がリストに加えられ、リストに加えられた点は初期データから削除される（ステップ２２）。そして、加えられた点に対する近傍点が、初期データの中から再度検索される（ステップ２３）。加えられた点に対する近傍点が初期データからなくなるまでステップ２１〜ステップ２４が繰り返され、近傍点がなくなると（ステップ２４）、初期データにまだ離散点が残っているかチェックし（ステップ２５）、残っていれば再度ステップ２１に戻り、その点のうちの１つがリストに加えられる。そして、同様にリストに加えられた点は初期データから削除され（ステップ２２）、加えられた点に対する近傍点が、初期データの中から再度検索される（ステップ２３）。このように、初期データに離散点がなくなるまでステップ２１〜ステップ２５が繰り返される。これにより、バンド性を持つ対角行列（帯行列）が生成される。この高速アルゴリズムを用い、新しく並び替えた行列を計算することにより、係数λｉ，λＮ＋１，λＮ＋２，λＮ＋３，λＮ＋４の計算時間を削減できる。上述のようなアルゴリズムを実現するプログラムは、例えば図２に示すようなものになる。
【００２４】
上記の高速アルゴリズムを、例えば、立方体内に｛１，２，３，４，５，６｝の６個の離散点がある画像に適用した場合について説明する。この６個の点それぞれに対し、任意の半径ｒ０の球内における近傍点が、次のように与えられているとする。
【００２５】
点１の近傍点：１，３，６
点２の近傍点：２，５
点３の近傍点：１，３，４
点４の近傍点：３，４
点５の近傍点：２，５
点６の近傍点：１，６
このような６個の離散点に対し、本発明で用いられるＣＳＲＢＦ法の高速アルゴリズムを適用すると、図３に示すように、離散点列は｛１，３，６，４，２，５｝というように並び替えられ、これから図４のようなバンド性を有する対角行列（ＳＬＡＥ行列）が生成される。なお、図４中の×は、２点間の距離を示す。このような高速アルゴリズムを用いることで、ＣＳＲＢＦ法で必要なパラメータを高速に計算することが可能となる。したがって、本発明で用いられるＣＳＲＢＦ法による関数計算を非常に高速に行えるようになる。
【００２６】
なお、基底関数における半径ｒ０が大きい場合、その任意の点Ｐｉを中心とした半径ｒ０の球に、殆どの点が含まれてしまう。したがって、この場合には並び替える前の行列に比べて対角行列のために多くの記憶空間を作らなければならなくなる。しかしながら、半径ｒ０を小さくすれば、記憶空間の少ない最良の結果となった行列が利用できるようになる。半径ｒ０は、高精度な画像が短時間に生成可能なように、経験的に決定すれば良い。
【００２７】
また、関数ｆ（ｘ，ｙ，ｚ）は、３次元画像を対象とした表記であるが、２次元画像の場合には、ｚ＝０であり、関数はｆ（ｘ，ｙ）で与えられる。さらに、画像の色情報は、関数の値で与えられる。例えば、ｆ（１０，２０）＝３０であった場合、ｘ座標が１０、ｙ座標が２０の点は、３０という色情報を有する点であることを示す。
【００２８】
さらに、離散点とは、格子状に分布する点であっても離散的に分布する点であっても構わない。例えば、原画像が１６０×１２０ピクセルの画像の場合、画像全体で関数を作成する場合には、離散点は１９２００個になるが、後に説明する前処理を行った場合には、これよりも少ない個数になる。例えば１０％の点しか使わない場合、離散点は１９２０個になる。なお、１９２０個の離散点は格子状に並んでいても構わないが、後に説明するように、特徴点を抽出するようにした場合には、特徴点に沿って不規則に存在する。
【００２９】
なお、上述した、本発明で用いられるＣＳＲＢＦ法の３次元画像を対象とした関数ｆ（ｘ，ｙ，ｚ）、また、２次元画像を対象とした関数ｆ（ｘ，ｙ）（つまり、ｚ＝０であるため、ｆ（ｘ，ｙ，ｚ）＝ｆ（ｘ，ｙ）になる）を以下のように単に関数ｆ(Ｐ)と記す。
【００３０】
まず、本発明の第１実施例のＣＡＤシステム間で交換されたデータの修復方法について説明する。本発明の第１実施例は、異なるＣＡＤシステム間で交換された２次元ＣＡＤデータ上の傷の修復方法に関するものである。なお、本実施例において、２次元ＣＡＤデータは、色の変化が滑らかな２次元画像を表している。
【００３１】
また、本発明でいう傷は、異なるＣＡＤシステム間で交換されたＣＡＤデータ上の不都合な部分を意味し、つまり、例えば、異なるＣＡＤシステム間でデータ間の授受を行った際に交換されたＣＡＤデータの中の構造形状の完全なる復元ができない部分（即ち、その部分のデータは失われている）、また、ＣＡＤデータの中に存在するＣＡＭ解析に不用な細かい穴を傷として考えることができる。
【００３２】
本発明の第１実施例のＣＡＤシステム間で交換されたデータの修復方法の手順は次のようになる。
【００３３】
まず、２次元ＣＡＤデータに表される２次元画像上の傷がついている部分をＷＲで表すとする。傷の部分ＷＲを少しだけ広げた領域をＷ＋とし、Ｗ＋からＷＲを引いた領域をＷＬで表す。このとき、領域Ｗ＋及び傷の部分ＷＲは、ユーザーが初期値として与える必要が生じるが、これについては、例えばAdobe（登録商標）Photoshop（登録商標）GUI  interface（登録商標）、Photopaint（登録商標）やGimp（登録商標）等の画像処理ソフトウェアのいわゆる選択ツールを用いることで、簡単に領域Ｗ＋及び傷の部分ＷＲの範囲を指定して決めることができる。領域Ｗ＋及び傷の部分ＷＲが決まれば、領域ＷＬも確定する。
【００３４】
次に、確定された領域ＷＬについて上述のＣＳＲＢＦ法を適用して２次元ＣＡＤデータ（２次元画像）の修復を行う。つまり、領域ＷＬにＣＳＲＢＦ法を適用して関数ｆ(Ｐ)を求め、傷のついた部分を連続的に滑らかに補間して修復を行う。
【００３５】
以上の修復方法の手順をまとめると、次のようになる。
ステップ１
２次元画像上（２次元ＣＡＤデータ上）の傷の部分ＷＲ、及び傷の部分ＷＲを少し広げた領域Ｗ＋を決める。
ステップ２
領域Ｗ＋から傷の部分ＷＲを引いた領域である、領域ＷＬに対して上述したＣＳＲＢＦ法を適用し、関数ｆ(Ｐ)を求める。
ステップ３
求められた関数ｆ(Ｐ)を用いて、傷の部分ＷＲの補間を行い、領域Ｗ＋を修復する。
【００３６】
上記のステップ１〜ステップ３を有する、本発明の第１実施例のＣＡＤシステム間で交換されたデータの修復方法は、色の変化が比較的滑らかに起こるような２次元ＣＡＤデータ（２次元画像）上の傷の修復に対して有効である。その理由とは、本発明の第１実施例のＣＡＤシステム間で交換されたデータの修復方法に使用されるＣＳＲＢＦ法が、２次元ＣＡＤデータ（２次元画像）上の離散点から滑らかな関数ｆ(Ｐ)を求めて、表面再構成を行なっているためである。
【００３７】
なお、本発明の第１実施例のＣＡＤシステム間で交換されたデータの修復方法とは、傷全体を一度に修復するものであり、特定された傷の領域の周辺から傷の部分を修正することが可能である。また、本発明では、傷の部分ＷＲを囲む所定の周辺領域である領域ＷＬが関数表現されていることから、短時間で高精度に傷の部分ＷＲの修復が可能となる。
【００３８】
一方、テクスチャ模様のように色の変化がシャープに起こるような２次元画像を表している２次元ＣＡＤデータ上の傷に対し、本発明の第１実施例のＣＡＤシステム間で交換されたデータの修復方法を適用する場合には、滑らかな関数表示を行うＣＳＲＢＦ法をそのまま用いることになり、２次元画像のエッジがボケた感じになり、精度の面で適さないといった問題が生じる。
【００３９】
次に、本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法について説明する。本発明の第２実施例は、ＣＳＲＢＦ法を局所的に繰り返して用いるＬＣＳＲＢＦ（local  compactly  supported  radial  basis  functions）法を用い、異なるＣＡＤシステム間で交換された２次元ＣＡＤデータ上の傷の修復方法に関するものである。なお、本実施例において、２次元ＣＡＤデータは、テクスチャ模様のように色の変化がシャープに起こるような２次元画像を表している。
【００４０】
従って、本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法を使用すれば、上記の問題が解決される。これは、本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法に用いられるＬＣＳＲＢＦ法とは、ＣＳＲＢＦ法を局所的に用いて関数表現を行うものである。ＬＣＳＲＢＦ法において、定式化で用いる基底関数と方程式はＣＳＲＢＦ法の場合と同じであるが、適用方法が異なる。ＬＣＳＲＢＦ法は、原物をより忠実に再現するために、画像の滑らかさを重視するＣＳＲＢＦ法とは異なり、１つ前のステップでＣＳＲＢＦ法を用いて得られた結果を取り入れて再構成を行うことを特徴としている。
【００４１】
ここでは、本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法を用いて、例えば、２次元ＣＡＤデータが表した画像サイズが１２８×１２８ピクセルのテクスチャ模様上に、左下から右上への直線的な傷が１本ある場合の修復手順を考える。直線的な傷が始まる左下のピクセルを‘傷の始点’（つまり、‘傷の1番目の点’）、始点の隣りのピクセルを‘傷の２番目の点’、この２番目の点の隣りのピクセルを‘３番目の点’とし、これを繰り返して傷が終わる右上のピクセルを‘傷の終点’（つまり、‘傷の１２８番目の点’）とする。こうしたとき、テクスチャ模様上の直線的な傷を、始点から終点までの各点毎に、次のような手順で修復する。
【００４２】
まず、‘傷の始点’（つまり、‘傷の1番目の点’）の修復を‘傷の始点’の周囲の少数点からＣＳＲＢＦ法を用いて求めた関数ｆ(Ｐ)を用いて行う。次に、修復された‘傷の1番目の点’の次の点である‘傷の２番目の点’について、‘傷の２番目の点’の周囲の少数点を求め、これらの点を用いてＣＳＲＢＦ法を用い、新たな関数ｆ(Ｐ)を作成して修復をする。なお、‘傷の２番目の点’を修復する際には、その周囲点である‘傷の１番目の点’は修復後の値を用いる。
【００４３】
このようにして、修復された‘傷のＬ番目の点’（２≦Ｌ≦１２７）の次の点である‘傷のＬ＋１番目の点’について、‘傷のＬ＋１番目の点’の周囲の少数点を求め、これらの点を用いてＣＳＲＢＦ法を用い、新たな関数ｆ(Ｐ)を作成して修復をする。なお、‘傷のＬ＋１番目の点’を修復する際には、その周囲点である‘傷のＬ番目の点’は修復後の値を用いる。これを‘傷の終点’まで繰り返す。
【００４４】
なお、傷の各点を修復する際に用いる周囲の少数点には、修復する点を中心とする半径ｔ＝Ｍ／Ｎ内にあるピクセルで半分以上含まれるものを採用することが好ましい。ここで、Ｎ_ｔは画像サイズを示す（本例ではＮ_ｔ＝１２８）。また、Ｍは１からＮ_ｔの値を初期値としてユーザーが与えるものである。ここでは多数のテクスチャ模様上の傷の修復に対し、様々なＭを用いて数値計算を行った結果、計算コストと得られる画像精度の両方を満たす値としてＭ＝３を用いている。
【００４５】
上述したように、ＬＣＳＲＢＦ法を用いる本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法は、傷の始点から傷の終点までに傷の点毎にＣＳＲＢＦ法を繰り返して用い、‘傷の２番目の点’以降は、その前の点の修復結果を反映させていることが最大の特徴である。このようなＬＣＳＲＢＦ法を用いることで、ＣＳＲＢＦ法では困難であるテクスチャ模様上の傷の修復が精度よく行えるようになる。
【００４６】
本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法の修復手順は次のようになる。
ステップ１０
２次元画像上（２次元ＣＡＤデータ上）の傷の部分を範囲指定する。
ステップ１１
まず、範囲指定された傷の部分の範囲内の所定の点を決定する。例えば、傷の部分の範囲内の最端部の点を傷の部分の所定の点として決定する。決定された傷の部分の所定の点を中心に隣接する所定の周辺領域部分を特定し、特定されたこの周辺領域部分に対してＣＳＲＢＦ法を用いて関数ｆ(Ｐ)を生成する。そして、この周辺領域部分に対する生成された関数ｆ(Ｐ)を用いて、傷の部分の所定の点を補間して傷の修復を行う。
ステップ１２
次に、傷の部分の次の所定の点を決定する。例えば、傷の部分の所定の点の隣の点を傷の部分の次の所定の点として決定する。傷の部分の所定の点と同様に隣接する所定の周辺領域部分を特定する。そして、特定されたこの周辺領域部分に対してＣＳＲＢＦ法を用いて関数ｆ(Ｐ)を生成し、生成された関数ｆ(Ｐ)を用いて、傷の部分の次の所定の点を補間して傷の修復を行う。なお、傷の部分の次の所定の点における修復の際には、傷の部分の所定の点の修復後のデータを用いるようにする。
ステップ１３
範囲指定された傷の部分のすべての傷の修復が終了するまでに、修復された傷の部分の次の所定の点を傷の部分の所定の点とし、上記ステップ１２を繰り返す。
【００４７】
上記ステップ１０〜ステップ１３を有する、本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法によれば、テクスチャ模様のように色の変化がシャープに起こるような画像の傷の修復に対しても、高精度の修復が可能となる。
【００４８】
最後に、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法について説明する。本発明の第３実施例は、異なるＣＡＤシステム間で交換された３次元ＣＡＤデータ上の傷の修復方法に関するものである。なお、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法は、３次元ＣＡＤデータ（３次元画像）上の多角形の傷の修復に対して有効である。
【００４９】
本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法は、３次元ＣＡＤデータ（３次元画像）上の多角形の傷を傷の輪郭抽出、輪郭の縫い合わせ、空間スペースマッピング法に基づくスムージング法といった３つの段階に分けて行うことを特徴としている。各段階での手順は次の通りである。
＜１＞傷の輪郭抽出
傷の輪郭抽出とは、３次元ＣＡＤデータ（３次元画像）上の多角形の傷の輪郭を全て見つけ出すことを意味し、その手順は次のようになる。
ステップ１００
３次元ＣＡＤデータ（３次元画像）上の多角形の傷の部分で境界になり得る全ての辺（境界辺）を見つけ出す。
ステップ１０１
上記ステップ１００で得られた境界辺から閉じた折線を下記ステップ１０２〜ステップ１０４に示された手順に沿って構成する。
ステップ１０２
まず、上記ステップ１００で得られた全ての境界辺の中から１つの境界辺ｅ１を選ぶ。このとき、境界辺ｅ１の始点をｖ１、終点をｖ２とする。
ステップ１０３
次に、ｖ２を始点とするような境界辺を見つけてｅ２とし、境界辺ｅ２の終点をｖ３とする。
ステップ１０４
この手順を頂点ｖ１に戻るまで繰り返し、１つの閉折線を構成する。
【００５０】
このとき、それぞれの境界辺は１つの閉折線にだけ含まれるとする。従って、同じ境界辺を重複して２つ以上の閉折線に用いることはできない。ここでは、有限個の頂点において得られた閉折線が交わることはあり得るし、閉折線の組み立ては複数考えられる。
ステップ１０５
上記ステップ１０２〜ステップ１０４で得られた閉折線の中で交点を持つものは、交点で結合して１つの閉折線に作りなおす。交点がなくなるまで本ステップを繰り返して行う。
【００５１】
具体的な例として、例えば、図５（Ａ）に示されるように、上記の傷の輪郭抽出段階のステップ１００〜ステップ１０４において、２つの閉折線Ｌ１＝(ｖ１,ｖ２,…,ｖｎ),Ｌ２＝(ｗ１,ｗ２,…,ｗｍ)が構成されたとする。閉折線Ｌ１とＬ２は２つの交点を持ち、そのうち１つは、閉折線Ｌ１で頂点ｖp1、閉折線Ｌ２で頂点ｗp2なっている。このとき、図５（Ｂ）に示されるように、この交点において上記ステップ１０５より、Ｌ１とＬ２を結合し、１つの閉折線が構成される。このように閉折線を交点において結合することで自己交差を含む１つの閉折線を作成することができ、交点を１つ減らすことが可能である。
＜２＞輪郭の縫い合わせ
輪郭の縫い合わせ段階では、閉折線で表される多角形の傷を三角形分割して縫い合わせて修復を行う。傷の輪郭抽出段階において、閉折線Ｌ＝(ｖ１,ｖ２,…,ｖｎ)が得られたとする。このとき、閉折線Ｌ上には結び目がないとする。ここでは、次の３つの条件を満たすように閉折線Ｌをｎ−２個の三角形に分割する。Ｔは閉折線Ｌの三角形分割とする。
条件１：
三角形分割Ｔの頂点は閉折線Ｌの頂点である。
条件２：
Ｔの辺は適当な共通部分を持つ。つまり、どの２つの三角形も重なることはないが、ある頂点かある辺で隣接することはあり得る。
条件３：
Ｔの境界はＬに一致する。
【００５２】
上記３つの条件において考えられる三角形分割の数は莫大にある。例えばｎ個の点ｖ１,ｖ２,…,ｖｎがあるとき、ｍ＝ｎ−２本の対角線に対し２ｍ＋１(２ｍ＋１)／(ｍ＋２)!,ｍ≧１個の三角形分割の可能性がある。このような膨大な数の中から最適な三角形分割を選ぶ必要が生じるが、そのためのアルゴリズムはアプローチが悪いと計算コストが上り、さほど多くない点データの計算でさえも行うことはできなくなってしまう。
【００５３】
そこで、最適な三角形分割を得るために、１９９２年にCormenらが提案した作業全体を部分的に分けて検証を行うためのアルゴリズムを用いた。この手法を用いて、例えば、ある閉折線に対して得られた１つの三角形分割(Ｔ1n)を、１つの三角形（△1kn）で繋ぐように２つの三角形分割の部分(Ｔ1k,Ｔkn)に分け、分かれたそれぞれの三角形分割Ｔ1k,Ｔknが最適なものかどうかを調べる。実際に、ここでは、三角形△1knの法線ベクトルを
2005190045.tif 000007
、辺ｖ１,ｖｋを含み三角形△1knに隣接する面の法線ベクトルを
2005190045.tif 000008
、辺ｖｋ,ｖｎを含み三角形△1knに隣接する面の法線ベクトルを
2005190045.tif 000009
、辺ｖｎ,ｖ１を含み三角形△1knに隣接する面の法線ベクトルを
2005190045.tif 000010
としたとき、ベクトル
2005190045.tif 000011
その周囲のベクトル
2005190045.tif 000012
とのスカラー乗法の和を最小にするものを最適な三角形分割としている。つまり、隣るようなＴ1nを見つけている。
【００５４】
この手法は、得られた三角形の集合が２つ以上の三角形分割に含まれるとき、その面集合における検証が反復されるのをできる限り避けるように作られているため、計算時間を削減することができる。実際に、多角形の傷を三角形分割して再構成した結果を図６に示す。図６（Ａ）は、原画像を示しており、図６（Ｂ）は、最適な三角形分割によって再構成した結果を示している。
＜３＞空間スペースマッピング法に基づくスムージング法
上記の傷の輪郭抽出段階及び輪郭の縫い合わせ段階で行った、３次元ＣＡＤデータ（３次元画像）上についた多角形の傷の修復結果は、断面的であり、原物とは程遠い。実際の物体は滑らかで、修復部分が図６（Ｂ）に示されるように、上記の傷の輪郭抽出段階及び輪郭の縫い合わせ段階で得られたような角ばったものでは不十分である。
【００５５】
そこで、上記輪郭の縫い合わせ段階で得られた三角形分割による傷部分に対し、次のような手順で表面の再構成を行い、スムージングをする。ここでは、本発明の第１実施例のＣＡＤシステム間で交換されたデータの修復方法と同様に、傷の部分をＷＲ、傷の部分ＷＲを少し広げた領域をＷ＋、Ｗ＋からＷＲを引いた領域をＷＬとする。
【００５６】
空間スペースマッピング法に基づくスムージング法の手順は次のようになる。
ステップ２００
輪郭の縫い合わせ段階で得られた各三角形に対し、下記ステップ２０１〜ステップ２０３によって傷内部の詳細な点データを求める。
ステップ２０１
オリジナル物体を三角形分割したときの三角形の平均サイズを求める。
ステップ２０２
傷部分における三角形で平均サイズよりも大きい場合は、その三角形の重心に１つ点を補い、その重心とその三角形の３頂点を結んで３つの領域（つまり、３つの新たな三角形）に分ける。
ステップ２０３
新たに形成された三角形についてもステップ２０２を適用する。平均サイズよりも大きい三角形がなくなるまで、ステップ２０２を繰り返す。
ステップ２０４
領域ＷＬに対してＣＳＲＢＦ法を適用し、関数ｆ(Ｐ)を求める。
ステップ２０５
求められた関数ｆ(Ｐ)を用いて、上記ステップ２０１〜ステップ２０３で得られた傷内部の詳細な点データで補間を行い、領域ＷＲの修復をする。この際、領域ＷＲの各点における高さ成分
2005190045.tif 000013
については、逆写像関数
2005190045.tif 000014
で再構成点
2005190045.tif 000015
を求めている。
【００５７】
なお、ＣＳＲＢＦ法は与えられた点データから滑らかな関数化を行い、画像再構成を行う手法であるため、本発明の画像表面のスムージングに適している。
【００５８】
図７は、３次元ＣＡＤデータ（３次元画像）上に１６個の穴がある場合の傷の修復問題に対し、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法を適用した結果である。
【００５９】
図７（Ａ）は、本発明を適用する前に１６個の穴があいている原画像である。図７（Ａ）の左図と右図は、異なる角度から見た原画像です。図７（Ｂ）の左図は、輪郭の縫い合わせ段階で多角形の傷を三角形分割した結果を示している。図７（Ｂ）の右図は、空間スペースマッピング法に基づくスムージング法段階で、上記ステップ２０１〜ステップ２０３によって求められた三角形傷内部の詳細な点データの結果を示している。図７（Ｃ）は、ＣＳＲＢＦ法を用いてスムージングを行った結果であり、つまり、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法を適用した最終結果である。
【００６０】
本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法を用いると、３次元ＣＡＤデータ上の傷の部分を自動的に見つけ出し、その傷の部分の再構成を行なうことができる。また、図７（Ａ）に示された原画像は、１９４６７個の多角形から構成されており、傷である１６個の穴の部分は３７２本の辺から成っている。図７（Ａ）に示されたような画像上の傷の修復時間は７.３秒で、実用化レベルの速さである。また、図７（Ｃ）の最終的な結果から、精度の面でも十分であることが良く分かる。
【００６１】
図８は、３次元ＣＡＤデータ（３次元画像）上に２１１個の穴がある場合の傷の修復問題に対し、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法を適用した結果である。図８（Ａ）は、本発明を適用する前に２１１個の小さな穴があいている原画像である。図８（Ｂ）は、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法の一部手順を適用した結果である。つまり、図８（Ｂ）は、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法における、傷の輪郭抽出段階と輪郭の縫い合わせ段階の手順だけを行った結果であり、ＣＳＲＢＦ法を用いてスムージングを行なっていない。図８（Ａ）に示されたような画像上の傷の修復時間は３秒で、実用化レベルの速さである。また、図８（Ｂ）の結果から、精度の面でも十分であることが良く分かる。
【００６２】
図７の修復例と図８の修復例を比較すると、次のようなことが分かる。つまり、傷が小さい場合、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法における、傷の輪郭抽出段階と輪郭の縫い合わせ段階の手順だけを行うことによって、良い精度の修復結果が得られる。一方、傷がある程度大きくなると、さらに、ＣＳＲＢＦ法を用いてスムージングを行うことによって、良い精度の修復結果が得られる。
【００６３】
また、ある場合には、視覚化のために、例えば、材料（木、金属など）を表すために、３次元モデルの表面上にある画像が使用されることがある。このような画像はテクスチャ模様の画像と呼ばれる。本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法を使用すれば、このようなテクスチャ模様の画像上の傷を修復することができる。その例を図９に示す。図９（Ａ）は、本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法を適用する前の原画像である。図９（Ｂ）は、本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法を用いて修復された画像である。
【００６４】
更に、別の場合に、例えば、３次元モデルの解析を簡略化するために、３次元モデルの一部の特徴を取り除く必要がある。その際に、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法を用いることによって解決できる。その例を図１０に示す。図１０（Ａ）は、本発明を適用する前のオリジナル３次元モデルを示しており、その３次元モデルの前のプレートの底部の近くに２つの空洞が存在する。該３次元モデルを解析する際に、この２つの空洞を省略することができる。図１０（Ｂ）は、この２つの空洞を選択し、その２つの空洞を取り除くために、切り込みを入れた様子を示している。図１０（Ｃ）は、本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法を適用した後の最終結果を示しており、ここでは、この前のプレートから２つの空洞が取り除かれていることがよく分かる。
【００６５】
なお、本発明のＣＡＤシステム間で交換されたデータの修復方法は、既存の装置に簡単に組み込むこともできるため、レーザースキャナでレーザーが当たる部分に生じる窪みを取り除くためのスムージングとしても効果的である。このように、本発明のＣＡＤシステム間で交換されたデータの修復方法は、交換されたＣＡＤデータ上の傷の修復を高速かつ高精度に行うことができ、適用範囲も広いという利点も備えている。
【図面の簡単な説明】
【００６６】
【図１】本発明で用いられたＣＳＲＢＦ法における高速アルゴリズムの流れを説明するためのフローチャートである。
【図２】本発明で用いられたＣＳＲＢＦ法における高速アルゴリズムを実現するためのプログラムの一例である。
【図３】本発明で用いられたＣＳＲＢＦ法における高速アルゴリズムによって離散点が並び替えられる過程を説明するための図である。
【図４】本発明で用いられたＣＳＲＢＦ法における高速アルゴリズムによって生成されたバンド性を持つ対角行列の一例を表わした図である。
【図５】本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法において、傷の輪郭抽出段階で求められた閉折線の一具体例を示す図である。
【図６】本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法において、輪郭の縫い合わせ段階で得られた一具体例を示す図である。
【図７】本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法を適用した、３次元ＣＡＤデータ上の傷の修復結果を示す図である。
【図８】本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法の一部手順を適用した、３次元ＣＡＤデータ上の傷の修復結果を示す図である。
【図９】本発明の第２実施例のＣＡＤシステム間で交換されたデータの修復方法を適用した、テクスチャ模様の画像上の傷の修復結果を示す図である。
【図１０】本発明の第３実施例のＣＡＤシステム間で交換されたデータの修復方法を用いることによって、必要のない３次元モデルの一部の特徴が取り除かれた結果を示す図である。
【図１】
2005190045.tif 000018
【図２】
2005190045.tif 000019
【図３】
2005190045.tif 000020
【図４】
2005190045.tif 000021
【図５】
2005190045.tif 000022
【図６】
2005190045.tif 000023
【図７】
2005190045.tif 000024
【図８】
2005190045.tif 000025
【図９】
2005190045.tif 000026
【図１０】
2005190045.tif 000027