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