(57)【要約】【課題】  連立１次方程式を解くことなく、なめらかな曲線や曲面を構築できる適切な数のデータを求められるようにすることである。【解決手段】  点列pkを平滑化するB-スプライン曲線b(t)に点列pkをあてはめる方法において、点列pkを高速フーリエ変換して、点列pkの離散的フーリエ変換P*(u)を計算する過程、ナイキスト周波数εを用いて点列の離散的フーリエ変換P*(u)のデータを2ε倍に削減して低周波成分G*(u’ ; u’ = u/ 2ε)だけを抽出する過程、低周波成分G*(u’)に係数関数C(u’)を掛けて、制御点列qkの離散的フーリエ変換Q*(u’)を計算する過程、および制御点列qkの離散的フーリエ変換Q*(u’)を高速フーリエ逆変換して、制御点列qkを計算する過程を有することを特徴とする。【選択図】図１０
2005258640.tif 000002
【特許請求の範囲】
【請求項１】
点列pkを平滑化するB-スプライン曲線b(t)に点列pkをあてはめる方法において、
点列pkを高速フーリエ変換して、点列pkの離散的フーリエ変換P*(u)を計算する過程、ナイキスト周波数εを用いて点列の離散的フーリエ変換P*(u)のデータを2ε倍に削減して低周波成分G*(u’ ; u’ = u/ 2ε)だけを抽出する過程、低周波成分G*(u’)に係数関数C(u’)を掛けて、制御点列qkの離散的フーリエ変換Q*(u’)を計算する過程、および制御点列qkの離散的フーリエ変換Q*(u’)を高速フーリエ逆変換して、制御点列qkを計算する過程を有することを特徴とする自由曲線へのあてはめ方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、CADやCG（コンピュータグラフィックス）のモデリング、また測定データ点列を平滑化する曲線・曲面へのあてはめなど、自由曲線・自由曲面の構築方法に関する。
【背景技術】
【０００２】
CADやCGのモデリングでは、自由曲線・自由曲面が使われる。また、近年、測定データを平滑化してなめらかな曲線や曲面を作る場合にも、自由曲線・自由曲面へのあてはめが行われる。これら自由曲線・自由曲面の代表的なものに、B-スプライン曲線・B-スプライン曲面がある。B-スプライン曲線を与えられた点列で平滑化するには、制御点（コントロールポイントともいう）を計算しなければならないが、このため連立1次方程式を解かねばならない。この解き方については、非特許文献１のp142〜145が参考になる。それでは制御点の重みを全て1にしているので、NURBS曲線をB-スプライン曲線と読み替えることができる。
【０００３】
また、B-スプライン曲面を与えられた点列で平滑化するには、連立1次方程式を2回にわたって解かなければならない。この解き方については、非特許文献１のp160〜162が参考になる。これも、制御点の重みを全て1にしているので、NURBS曲面をB-スプライン曲面と読み替えることができる。
【０００４】
以上のように、B-スプライン曲線においてもB-スプライン曲面においても、図１の（ケースＡ）のように、連立1次方程式を解く必要があり、プログラムが複雑になるという問題がある。
【０００５】
また、測定データを内挿してなめらかな曲線や曲面を作る場合には、ノイズがのった測定データそのものを内挿するのは好ましくない。このため、測定データをまず高速フーリエ変換し、空間周波数領域で高周波成分をカットし、この後に高速フーリエ逆変換して、高周波成分の除去された測定データを求める。続いて、これを内挿してB-スプライン曲線やB-スプライン曲面を求めるが、この時には連立1次方程式を解かなければならない。
【０００６】
よって、この過程では、図２の（ケースＢ）のように、高速フーリエ変換、高周波成分カット、高速フーリエ逆変換、連立1次方程式の解の計算という4つのステップが必要になる。このうち、高速フーリエ変換と高速フーリエ逆変換は、プログラムが専用パッケージ化されているため簡単にプログラムを組むことができるし、高周波成分カットもプログラムとしてはとても簡単である。これに対し、連立1次方程式を解くことは、プログラム的には複雑である。
【０００７】
結局、(ケースA)、(ケースB)ともに、連立1次方程式を解くことがプログラムを複雑化し、処理を遅くしている。
【０００８】
一方、先の特許出願に係る特許文献１では、図３の（ケースＣ）のように、点列pkを高速フーリエ変換して点列の離散的フーリエ変換P*(u)を計算し、P*(u)に係数関数C(u)を掛けて制御点列qkの離散的フーリエ変換Q*(u)を計算し、Q*(u)を高速フーリエ逆変換して制御点列qkを計算するため、（ケースＡ，Ｂ）のように連立1次方程式を解く必要がない。また、カットオフ周波数εを用いて、これ以上の高周波成分をフーリエ変換面で除去すれば、なめらかな曲線や曲面を構築できる。ところが、この方法では、制御点の数が点列の数と同じである。一般に、データ点列をなめらかな曲線・曲面にあてはめるとデータ量が削減されるが、この方法ではそれに対応できない。
【特許文献１】特願２００３−３２４９３２
【非特許文献１】三浦曜、望月一正著「CAD・CG技術者のための実践NURBS」工業調査会刊、2001年発行
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、本発明の課題は、連立１次方程式を解くことなく、なめらかな曲線や曲面を構築できる適切な数のデータを求められるようにすることである。
【課題を解決するための手段】
【００１０】
B-スプライン曲線・B-スプライン曲面の制御点を連立1次方程式を解かないで求めるには、図４の（ケースＡ’）に示すように、点列を高速フーリエ変換し、空間周波数領域において係数関数との掛け算を行い、高速フーリエ逆変換することにより、制御点を求める。高速フーリエ変換、高速フーリエ逆変換ともに、プログラムは専用パッケージとなっており、簡単にプログラムを組むことができる。また、高速フーリエ変換と高速フーリエ逆変換は、専用のDSP（Digital Signal Processor）またはDSP内臓CPU（MMX系CPU）を用いた積和演算で処理されるため非常に高速であり、係数関数との掛け算の演算時間も他の演算に比べると無視できるほどに小さいため、結局、連立1次方程式を用いた方法に比べると高速化が可能である。
【００１１】
また、自由曲線・自由曲面の高周波ノイズ除去においては、図５の（ケースＢ’）に示すように、連立1次方程式を解くステップの代わりに、係数関数との掛け算処理を用いることにより簡単にプログラムを組むことができるのはもちろん、処理時間も大幅に短縮される。
【００１２】
また、制御点数の削減については、図６の（ケースＣ’）に示すように、データ削除部において、ケースCのカットオフ周波数εをナイキスト周波数とすれば、高周波成分がカットされるだけでなく、データ数も2ε（ε< 0.5）倍に削減されるので、これを離散的逆フーリエ変換して制御点を求めれば、制御点数が2ε倍に削減される。
【００１３】
具体的に記載すると、本発明にかかる自由曲線へのあてはめ方法は、点列pkを平滑化するB-スプライン曲線b(t)に点列pkをあてはめる方法において、点列pkを高速フーリエ変換して、点列pkの離散的フーリエ変換P*(u)を計算する過程、ナイキスト周波数εを用いて点列の離散的フーリエ変換P*(u)のデータを2ε倍に削減して低周波成分G*(u’ ; u’ = u/ 2ε)だけを抽出する過程、低周波成分G*(u’)に係数関数C(u’)を掛けて、制御点列qkの離散的フーリエ変換Q*(u’)を計算する過程、および制御点列qkの離散的フーリエ変換Q*(u’)を高速フーリエ逆変換して、制御点列qkを計算する過程を有することを特徴とする。
【発明の効果】
【００１４】
点列を平滑化してB-スプライン曲線を構築する際、連立1次方程式を解く代わりに、高速フーリエ変換、係数関数との掛け算、高速フーリエ逆変換を使うことにより、プログラムが簡単になり、また高速フーリエ変換、高速フーリエ逆変換の専用パッケージが使えるので、高速化ができる。さらには、ナイキスト周波数を用いて、制御点数を削減できるため、データの取り扱いが簡単になる。
【発明を実施するための最良の形態】
【００１５】
まず、特許文献１（特願２００３−３２４９３２）で示した上述のケースCの方法について述べる。
【００１６】
点列pkを通るB-スプライン曲線をパラメータtを用いてp(t) と表現すると、それは次式で与えられる。
【００１７】
【数１】
2005258640.tif 000003
【００１８】
B-スプライン曲線p(t) は、制御点qkを用いて次式で表現できる。
【００１９】
【数２】
2005258640.tif 000004
【００２０】
ここに、Nk , M (t) は位数M、次数m = M-1 のB-スプライン基底関数である。また、Nは測定データの数である。
【００２１】
さて、B-スプライン曲線 p(t) のフーリエ積分をP(u)，点列pkの離散的フーリエ変換をP*(u)，制御点qkの離散的フーリエ変換をQ*(u)とする。ただし、uを空間周波数とする。また、点列pkの離散的フーリエ変換P*(u)と制御点qkの離散的フーリエ変換Q*(u)を求めるにあたっては、離散的フーリエ変換の性質から、点列pkと制御点列qkはともに周期性を持ち、N個ごとに繰り返しているものと考える。
【００２２】
式(2)のB-スプライン基底関数N0,M(t)のフーリエ積分は，フーリエ変換の記号をFとして、次式で表される。
【００２３】
【数３】
2005258640.tif 000005
【００２４】
ここに、sinc(u)は下記の通りである。
【００２５】
【数４】
2005258640.tif 000006
【００２６】
式(2)をみると, B-スプライン曲線 p(t) がN0,M (t) とqkのたたみこみの形式になっているので、p(t)のフーリエ積分P(u) は，N0,M (t)のフーリエ積分F[N0,M(t)]とqkの離散的フーリエ変換Q*(u)との積の形になる。よって、式(3)を用いて、次式が得られる。
【００２７】
【数５】
2005258640.tif 000007
【００２８】
また、p(t) の離散的フーリエ変換P*(u)は、式(2)およびB-スプライン基底関数Nk , M (t) の周期性、離散的フーリエ変換Q*(u)の周期性を用いて、次式で表される。
【００２９】
【数６】
2005258640.tif 000008
【００３０】
ここに、C’ m (u)は、次数mの時の係数関数である。
よって、
【００３１】
【数７】
2005258640.tif 000009
【００３２】
として、新しい係数関数C m (u)を用いて、次式が得られる。
【００３３】
【数８】
2005258640.tif 000010
【００３４】
新しい係数関数C m (u)  と次数mとの関係を下記表1に示す。
【００３５】
【表１】
2005258640.tif 000011
【００３６】
なお、点列pkの離散的フーリエ変換は、高速フーリエ変換を用いて求めることができる。高速フーリエ変換の記号をFFTとすると、次式で表される。
【００３７】
【数９】
2005258640.tif 000012
【００３８】
制御点の離散的フーリエ変換Q*(u)を離散的フーリエ逆変換すると、制御点qk が求まる。高速フーリエ逆変換の記号をIFFTとすると、それは次式で表される。
【００３９】
【数１０】
2005258640.tif 000013
【００４０】
これを式(2)に代入して、B-スプライン曲線p(t)を求めることができる。
【００４１】
実際の計算手順（点列pkを内挿するB-スプライン曲線p(t)を構築する方法）を、最もよく使われるm = 3次のB-スプライン曲線の場合でみると図７のようになる。
【００４２】
点列pkを内挿するB-スプライン曲線p(t)の高周波ノイズを除去する方法も、最もよく使われるm = 3次のB-スプライン曲線の場合でみると、図８のようになる。
【００４３】
次に、本発明の手法について述べる。本発明では、N個の点列pkを内挿するB-スプライン曲線p(t)を求めるのではなく、点列pkを平滑化するB-スプライン曲線b(t)を求める。そして、カットオフ周波数ε（ε< 0.5）をナイキスト周波数（最大周波数)として、制御点列q k の数をN’ = 2εNに削減する。
【００４４】
本発明の方法では、図９に示すように、pkの離散的フーリエ変換P* (u)の低周波成分P* (u ; |u|≦ε) を新しい変数u’ = u/ 2εを用いて、P* (u ; |u|≦ε) =  G* (u’ ; |u’|≦0.5)と置き換える。これより、P* (u)の高周波成分P* (u; |u|＞ε) は自動的に無視される。
【００４５】
そして、B-スプライン曲線の制御点q* k (N’個) の離散的フーリエ変換Q* (u’) を次式で求める。
【００４６】
【数１１】
2005258640.tif 000014
【００４７】
上式右辺に2εを掛けるのは、離散的フーリエ変換P* (u)を求めたときはデータ数Nであったのに、q* k を求めるためのQ* (u’)の離散的フーリエ変換はデータ数がN’ に削減されているため、その比率N’/N=2εをゲインとしてかけなければならないからである。そして、制御点q* kは次式で求まる。
【００４８】
【数１２】
2005258640.tif 000015
【００４９】
これより、図１０に示す平滑化されたB-スプライン曲線b(t)は次式で求めることができる。
【数１３】
2005258640.tif 000016
【００５０】
ここで、図１１に、点列 pkを平滑化するB-スプライン曲線b(t)の制御点qkの求め方を具体的手順を示す。なお、m = 3次とする。
【００５１】
なお、以上の説明はB-スプライン曲線に関して述べたが、容易にB-スプライン曲面に対しても拡張できる。
【００５２】
なお、図１２は元データの一例を示し、図１３ないし図１５は元データに基づくB-スプライン曲線へのあてはめ例を示す。Ｎ＝６４点の元データは、カットオフ周波数ε（ε< 0.5）の数値に応じ減少していることがわかる。
【産業上の利用可能性】
【００５３】
CAD、CGのモデリングや測定データの曲面へのあてはめなどにおいて、与えられた点列の高周波ノイズを除去しながら、B-スプライン曲面にあてはめる用途に使うことができる。
【図面の簡単な説明】
【００５４】
【図１】従来技術の（ケースＡ）による自由曲線・自由曲面の構築方法のフローチャート図である。
【図２】従来技術の（ケースＢ）による自由曲線・自由曲面の高周波ノイズ除去方法のフローチャート図である。
【図３】（ケースＣ）によるＢ-スプライン曲線の制御点算出のフローチャートである図である。
【図４】先行技術の（ケースＡ’）による自由曲線・自由曲面の構築方法のフローチャート図である。
【図５】先行技術の（ケースＢ’）による自由曲線・自由曲面の高周波ノイズ除去方法のフローチャート図である。
【図６】（ケースＣ’）によるＢ-スプライン曲線の制御点算出のフローチャートである図である。
【図７】点列pkを内挿するB-スプライン曲線p(t)を構築する方法の計算手順の説明図でのデータ流れのフローチャート図である。
【図８】点列pkを内挿するB-スプライン曲線p(t)の高周波ノイズを除去する方法の計算手順の説明図である。
【図９】本発明による低周波成分G*(u’)の求め方の説明図である。
【図１０】本発明による点列を平滑化するＢ-スプライン曲線の説明図である。
【図１１】本発明による点列pkを内挿するB-スプライン曲線p(t)を構築する方法の計算手順の説明図でのデータ流れのフローチャート図である。
【図１２】本発明によるＢ-スプライン曲線へのあてはめ例のための元データの説明図である。
【図１３】本発明によるＢ-スプライン曲線へのあてはめ例の説明図である。
【図１４】本発明によるＢ-スプライン曲線へのあてはめ例の説明図である。
【図１５】本発明によるＢ-スプライン曲線へのあてはめ例の説明図である。
【符号の説明】
【００５５】
pk   点列
b(t)   B-スプライン曲線
P*(u)   点列の離散的フーリエ変換
ε   ナイキスト周波数
G*(u’)  低周波成分
C(u’)   係数関数
qk   制御点列
Q*(u’)  制御点の離散的フーリエ変換
【図１】
2005258640.tif 000017
【図２】
2005258640.tif 000018
【図３】
2005258640.tif 000019
【図４】
2005258640.tif 000020
【図５】
2005258640.tif 000021
【図６】
2005258640.tif 000022
【図７】
2005258640.tif 000023
【図８】
2005258640.tif 000024
【図９】
2005258640.tif 000025
【図１０】
2005258640.tif 000026
【図１１】
2005258640.tif 000027
【図１２】
2005258640.tif 000028
【図１３】
2005258640.tif 000029
【図１４】
2005258640.tif 000030
【図１５】
2005258640.tif 000031