JPH0896147A - 縮退のない曲線および曲面平滑化方法 - Google Patents

Abstract

(57)【要約】 【課題】 曲線長の減少なしに区分線形図形を平滑化す
る。 【解決の手段】 図形を規定する各頂点にたいし、頂点
近傍を選択する（４２０）。第一ベクトル変位は、第一
ベクトル平均に第一スケール・ファクタを掛けることに
より各頂点について決定する。頂点の第一位置は、第一
変位ベクトルの方向および大きさにより移動させられた
場合に得られる位置である。第二ベクトル変位が、同じ
プロセスにより決定される。第二スケール・ファクタは
第一スケール・ファクタとは符号が反対であり、負のも
のは正のものよりも大きい。頂点の第二位置は、第二変
位ベクトルの方向および大きさにより移動させられた場
合に得られる位置である。第二位置内の全ての頂点によ
り規定されるような図形が特定の平滑基準内にある場
合、そのアルゴリズムは修了し、違う場合は、各頂点に
たいする第一ベクトルを決定する工程から繰り返す。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は曲線長あるいは表面
積を減少することのない曲線あるいは曲面平滑化処理方
法およびシステムに関し、特に、コンピュータ・グラフ
ィックスおよび画像処理における曲線平滑化あるいは曲
面平滑化の分野に関するものである。

【０００２】

【従来の技術】本発明において、曲線および曲面は単に
「図形」とし、多角曲線および多面曲面は「区分的線形
図形」とそれぞれ称する。

【０００３】多くの出願、特に科学的データの視覚化に
おいて、また、他の多数の処置における中間工程とし
て、二次元および三次元曲線の多角形曲面近似および曲
面の多面曲面近似などがルーチン作業により決定されて
いる。こうした区分的線形近似方法の元来の問題は、得
られる区分的線形図形が切子面として見えることであ
る。この切子面を減少させるには、平滑化処理が使用さ
れる。

【０００４】また、平滑化処理は、曲線や曲面デザイン
に関するコンピュータ・グラフィックスや幾何学モデリ
ング学等において使用されている。細分割曲面は連続し
た多面曲面の限定したものとして作られる。初期骨格多
面曲面で開始して、次の多面曲面は現在の曲面の全ての
面を細分割し、その細分割曲面に多面曲面平滑化工程を
適用することにより求められる。この曲面処理方法によ
る主な問題は、この限定曲面の大きさが初期骨格曲面よ
りかなり小さくなることである。細分割曲線は同様に規
定され、同じ問題に直面する。

【０００５】輪郭線追跡および等曲面制作アルゴリズム
は、これらの区分的線形近似を作る従来例のアルゴリズ
ムである。一般的に、平滑曲線と曲面の区分的線形近似
を演算するアルゴリズムは、オリジナルな曲線あるいは
曲面がどのように描かれているかにより異なる。最も共
通する説明の中では、曲線や曲面はパラメータ方程式あ
るいは暗黙方程式により分析論的に説明可能である。

【０００６】従来技術は暗黙曲線や曲面（つまり、暗黙
方程式により定義されたもの）は特に近似させるのが難
しいことを認識している。暗黙曲線や曲面の各点は方程
式を解くことにより決定される。あるいは、パラメータ
曲線の各点は一組のパラメータ方程式における一つのパ
ラメータ変数（パラメータ曲面は二つの変数によって定
義される）の値を置換することにより容易に得られる。

【０００７】暗黙およびパラメータ曲線および曲面は関
数により定義される。関数は分析方程式あるいは数値表
として表示させることが可能である。関数を数値表で定
義する時は、補間法により中間値を決定する必要があ
る。境界線追跡あるいは輪郭線追跡アルゴリズムは、数
値表により規定される二次元のパラメータ曲線あるいは
曲面の例を生成する。これらは、画像領域の境界曲線と
してデジタル画像から引き出した曲線である。数値表
は、その画像領域の境界を追跡する際に訪れたピクセル
の境界頂点の連続した座標として作られ、対象とする平
滑な曲線の多角形近似を構成する。輪郭線追跡アルゴリ
ズムにおける技術的な説明は、１９７３年までに公知技
術に記載された。

【０００８】等曲面作成アルゴリズムは、定義関数が通
常の三次元格子を獲得する数値表からの暗黙曲面の区分
的線形近似を演算する。いわゆるマーチング・キューブ
・アルゴリズムが最も広く知られている等曲面形成アル
ゴリズムの一つであるが、従来例には互いに近接したア
ルゴリズムの大きな一族が存在する。それらは関数値の
格子によって定義される容積をどのようにモザイク合わ
せするか、また既存の表数値間に関数値をどのように補
間するかという点に実質的な相違がある。

【０００９】こうした近似アルゴリズムのほとんどに存
在する主な問題は、対象とする曲線あるいは曲面が平滑
であっても得られた区分的線形図形が切子面的に見える
ことである。これは、打ち切りプロセスあるいは補間プ
ロセスによっては、対象の曲線あるいは曲面上の点の位
置が高い精度で確定し得ないことに原因がある。図１、
図２は、切子面問題を示す平滑曲線および平滑曲面の区
分的線形近似の従来例である。平滑曲線近似アルゴリズ
ムは平滑曲線１１０の切子面になった区分的線形近似１
２０を作る。

【００１０】従来例は曲面に関する平滑化問題（視覚的
平滑化および幾何学的平滑化）を解決するための二つの
方法を提供している。視覚的平滑化は、曲面を変えるこ
となく区分的線形曲面が平滑に見えるようにするイルミ
ネーションのバリエーションを使用している。（この技
術は曲線に対しては存在しない。）幾何学的平滑化は実
際の平滑化を行うため曲線あるいは曲面の幾何学的配列
を修正するものである。

【００１１】視覚的平滑化では、異なったイルミネーシ
ョン・モデルと面シェーディング・アルゴリズムを使用
して視覚的な平滑化効果を作ることが可能である。それ
らのアルゴリズムでは、入射面の表面垂線の加重平均と
して多面曲面の頂点での表面垂線を定義し、複数の頂点
における演算して得た表面垂線を使用し、垂線−ベクト
ル補間シェーディングとして知られてもいる、いわゆる
Phongシェーディング法を使用する曲面の平滑シェーデ
ィングを作るアルゴリズムもある。これらの方式の使用
では、曲面幾何学配列は修正されないが、平滑化したよ
うに見えるようになる。

【００１２】視覚的平滑化法は、曲面近似が他の目的、
例えば、識別あるいは登録用に曲線あるいは曲面上の高
曲率の点あるいは他の幾何学的に不変な特徴を位置付け
るため、また、曲線長、曲面の面積、閉じた曲線により
取り囲まれた面積、あるいは閉じた曲面により囲まれた
体積等を測定するという目的により決定される時には使
用されない。こうした場合には、多面曲面の幾何学的配
列は後に行われる演算で正確な結果が得られるように修
正されなければならない。

【００１３】ほとんどの従来例の幾何学的平滑処理方法
はいくつかの問題に直面している。その最も重要なもの
は縮退問題である。すなわち、何度も反復して行うと、
図形は図心に向かって収束してしまう。図３は、ほとん
どの従来技術の平滑化アルゴリズムが曲線の処理の際に
生じる縮退問題を示しており、図４は曲面の処理の際の
同様な問題を示している。縮退区分的線形曲線平滑化ア
ルゴリズムは平滑化したものを生成するが、区分的線形
曲線２１０に適用すると小さくなった区分的線形曲線２
２０となる。同様に、縮退区分的線形曲面平滑化アルゴ
リズムは平滑化したものを生成するが、区分的線形曲面
２３０に適用すると小さくなった区分的線形曲面２４０
となる。

【００１４】幾何学的平滑処理において、曲線は元来線
形配列なので平滑多角形曲線は平滑多面曲面より単純で
ある。閉じた曲線では、各頂点はその配列において丁度
二つの近傍を有し、先行する一方と追従する他方があ
り、この事はフーリエ分析の適応を可能とする。いわゆ
るフーリエ記述子（曲線の正接角対弧の長さのフーリエ
級数展開における係数の使用）が連続曲線の複数分解表
示を提供する。曲線を平滑化するためには、そのフーリ
エ級数を切り捨てることで十分である。しかし、その結
果は多角形曲線ではなく、解析方程式により定義された
平滑なパラメータ曲線である。新たな多角形曲線を得る
ためには、新たな連続曲線、オリジナル曲線の切り捨て
られたフーリエ級数、を一定間隔でサンプリングする。
フーリエ記述子は１９６０年代初期までさかのぼり、以
来コンピュータ分野で画像認識の複数解析の形状記述子
として広範囲に使用されている。実際には、この連続プ
ロセスは頂点座標の数列の不連続フーリエ変換を演算
し、高度数に関する変換係数をゼロに設定し、得られた
数列をもどし変換することにより近似される。

【００１５】曲線平滑化にたいするフーリエ記述子の方
法は縮退の問題を有さないが、関数のフーリエ級数を切
り捨てることが不必要な頻度の高い不安材料となること
が従来技術において熟知されている。この問題はGibbs
現象として従来技術において知られている。多面曲線を
平滑化するためのこの方法には、他に二つの重要な問題
がある。第一は、演算費用がかかることである。高速フ
ーリエ変換アルゴリズムを使用しても、数学的演算の数
は ｎlog(ｎ)（ｎは頂点の数である）のオーダである。
線形アルゴリズムは、ｎオーダ数学的演算において必要
であり、特に頂点の数が多い曲面に対してより望まし
い。フーリエ記述子の方法の第二の問題は、任意の位相
的タイプの曲面に展開できず、直交領域について定義し
た二つの変数のベクトル関数でパラメータ化可能な曲面
についてのみである。そして、その場合でも、結果は使
用した特定のパラメータ表示に影響される。曲線の場
合、本来のオーダは標準的なパラメータ表示、弧長パラ
メータ表示等を決めるが、曲面の場合にはこうした事は
ない。

【００１６】幾何学的平滑化パラメータ表示曲線の最も
普及している線形技術（演算の数は区分的線形図形の
面、エッジ、頂点に比例）は、いわゆるガウス・フィル
タ処理法である。連続した場合では、ガウス・フィルタ
処理は、ガウス核で曲線をパラメータ表示するベクトル
関数を巻き込むことにより行われる。また、ガウス・フ
ィルタ処理は、矩形変域について定義した二つの変数の
関数によりパラメータ表示可能であるそれらの曲面に展
開するが、全般的な曲面にたいする巻き込みの有効な概
念さえもないので任意の位相タイプの曲面には展開しな
い。画像は二つの変数の関数のグラフとしてモデル化さ
せるので、ガウス・フィルタ処理はこのように画像に適
用する。しかし、ガウス・フィルタ処理は縮退を生み出
すという欠点を有することが広く知られている。

【００１７】■■■この問題にたいするいくつかの帰納
法的解決が提案されており、最近ではOliensisがこの問
題に関するすぐれた分析と洗練された解決方法を提供し
ている。度数変域におけるフィルタ処理後の曲線を捜す
ことにより、また、巻き込みのフーリエ変換はこの二つ
のファクタのフーリエ変換の所産であるので、Oliensis
は縮退問題がガウス核のフーリエ変換、ガウス関数その
ものがローパス・フィルタを構成しないという事の結果
であることを示した。ゼロ度数を除き、全ての度数は減
衰する。理想的なローパス・フィルタは空間変域におい
て無限の支持を有するので、その問題を解決することが
難しいが、Oliensisはその問題を解決するローパス・フ
ィルタ核を定義することを続けた。すなわち、この核を
有する曲線の巻き込みは縮退なしで平滑化が得られる。
この方法による主な問題は、任意の位相タイプの曲面に
展開しない、すなわち、矩形の格子により定義される近
傍である曲面にのみ適用するということである。これは
概ね二つの理由による。第一に、ほとんどコンパクトで
はあるが、その核の支持の大部分は、平滑効果を得るた
めに現在の頂点からかなり離れて展開しなくてはならな
い。そして、第二は、複数の頂点のリストおよび面のリ
ストとした多面曲面の通常の表示に基づき、特別な目的
のデータ構造を構築せずに所定の頂点から離れた頂点に
接近することは非常に困難である。さらに、全体的な曲
面にたいして近傍構造は頂点から頂点に変化するので、
各頂点にたいして異なった核を考えなくてはならず、こ
れはかなりの記憶容量を消費する。数学的演算の数とい
う点から、およびこの全ての情報をエンコードするため
必要な記憶容量という点からみて、この全ては実用的で
はない。

【００１８】コンピュータ・グラフィックスおよび幾何
学的モデリング学において、曲面平滑処理は曲面整形と
も呼ばれており、通常、パッチ・ワーク的技術に関連し
たものである。この構成では、曲面整形は初めの多面曲
面の各平面が平滑なパラメータ・パッチにより置き換え
られる平滑曲面補間法問題の役を割当られている。この
グループにおけるアルゴリズムは補間曲面を生成するの
で、縮退の問題にはぶつからないが、骨格多面体から高
い曲率変化のかなりの部分が得られた曲面に残ることに
なる。すなわち、骨格多面曲面を平滑化する問題は未解
決である。その意味では、これらの方法は上述した視覚
平滑法に似ている。さらに、得られた曲面は多面形では
なく、したがって、他の幾何学的平滑アルゴリズムとは
比較できない。最新の曲面整形は多面曲面についての全
体的な非線形最小化問題として、曲面の頂点あるいは面
の数に比例した幾つかの自由度を有して公式化されてい
る。これらのアルゴリズムのいくつかは同様に補間曲面
を生成するが、演算コストが極めて高いものとなり、他
は縮退を発生させてしまう。

【００１９】加重平均法は、多角形曲線および多面曲面
にたいするガウス平滑化の最も単純な近似法である。加
重平均法では、各頂点の新たな位置、および、その第一
オーダ近傍（それらの頂点はエッジあるいは面を現在の
頂点と共有する）の現在位置が頂点の現在位置の加重平
均として算出される。加重平均法は上記した公知例に関
して幾つかの利点を有するが、縮退を生み出す。第一の
利点は、矩形変域について定義した関数によりパラメー
タ化可能なものだけではなく、任意の位相タイプの多角
形曲線および多面曲面に適用することである。第二の利
点は、曲線あるいは曲面のエッジあるいは面のリスト内
で第一オーダ近傍が暗黙に定義されるので、近傍構造を
エンコードするため記憶部を必要としないことである。
第三の利点は、演算の回数が頂点および面の総数の線形
関数であることである。

【００２０】

【発明が解決しようとする課題】本発明の目的は、全て
の区分的線形曲線あるいは曲面の平滑化処理に一般的に
適用可能なシステムおよび方法を提供することである。

【００２１】本発明の別の目的は、平滑な曲線あるいは
曲面の区分的線形近似の平滑化処理に一般的に適用可能
なシステムおよび方法を提供することである。

【００２２】本発明の別の目的は、曲線長（曲面面積）
の減少がなく区分的線形曲線（曲面）を平滑化するシス
テムおよび方法を提供することである。

【００２３】本発明の別の目的は、コンピュータ画像を
生成する際に、曲線長（曲面面積）の減少がなく区分的
線形曲線（曲面）を平滑化するシステムおよび方法を提
供することである。

【００２４】

【課題を解決するための手段】本発明は、図形を規定す
る頂点の一を修正することにより区分的線形曲線（曲
面）を平滑化処理するための新規なシステムおよび方法
である。本発明は、かなり多くの回数反復して適用して
も、縮退を防ぎながら平滑化効果を生み出す。本発明は
一般的かつ任意の多角形曲線、多面曲面、さらには任意
の寸法の多形体に適用する。本発明は曲率の関数として
ローパス・フィルタ効果を作る。本発明によれば、必要
な工程数は曲線あるいは曲面の頂点、エッジ、あるいは
面の数に比例するので、最小の演算コストを得られる。
本発明が必要とする頂点の近傍についての情報を表示し
たりエンコードするための記憶容量は最小である。

【００２５】本発明による方法は、区分線形図形を規定
する一組の頂点を判定することから開始する。通常、こ
れら複数の頂点は曲線（曲面）の区分的線形近似を規定
する。そして、図形を規定する各頂点にたいして、その
頂点近くの頂点近傍を選択する。一以上の第一ベクトル
をその頂点とその近傍の各々の間で規定する。第一ベク
トル平均は、第一ベクトルをベクトル平均することによ
り各頂点に対して決定する。第一ベクトル変位は、第一
ベクトル平均に第一スケール・ファクタを掛けることに
より各頂点について決定する。頂点の第一位置は、第一
変位ベクトルの方向および大きさにより移動させられた
場合に得られる位置である。この点で、第二ベクトル平
均が、同じプロセスによりその近傍の各々および各頂点
間で決定される。第二ベクトル平均は全ての第二ベクト
ルのベクトル平均をとることにより決定する。そして、
第二ベクトル変位は第二ベクトル平均と第二スケール・
ファクタを掛けることにより決定する。この第二スケー
ル・ファクタは第一スケール・ファクタとは符号が反対
である。負のスケール・ファクタは正のスケール・ファ
クタより大きさが大である。次に各頂点の第二位置を決
定する。頂点の第二位置は、第二変位ベクトルの方向お
よび大きさにより移動させられた場合に得られる位置で
ある。その第二位置内の全ての頂点により規定されるよ
うな図形が特定の平滑基準内にある場合、そのアルゴリ
ズムは修了する。違う場合は、この方法は各頂点にたい
する第一ベクトルを決定する工程から繰り返す。

【００２６】本発明による方法はコンピュータ・システ
ム上で走行可能であり、この区分的線形曲線および曲面
から平滑な画像を生成できる。望ましい実施例では、第
一（第二）ベクトル平均は第一（第二）ベクトルを加重
して決定する。さらに望ましい実施例では、加重値は全
て正であり、和が値１となる。

【００２７】

【発明の実施の形態】図５は本発明の望ましい実施例を
実行するコンピュータ・システム３００を示すブロック
図である。望ましい実施例は一以上のアプリケーション
・プログラム３０２を有する。アプリケーション・プロ
グラムの一つのタイプとして、コンパイラ３０５があ
り、オプチマイザ３０６を有する。このコンパイラ３０
５とオプティマイザ３０６は、ソース・プログラム（他
のアプリケーション・プログラム３０２と同様）を最適
化された実施可能なコードに変換するように作られてい
る。さらに一般的には、そのソース・プログラムは最適
化されたフォームに変換され、さらに実施可能なコード
に変換される。コンパイラ３０５とオプティマイザ３０
６はハードウェア・ユニット３１２を有するコンピュー
タ・プラットフォーム３０４に影響を及ぼす。このシス
テムを走行するアプリケーション・プログラム３０２の
一つは本発明の方法４００である。

【００２８】ハードウェア・ユニット３１２は一個以上
の中央処理ユニット（ＣＰＵ）３１６、ランダム・アク
セス・メモリ（ＲＡＭ）３１４、入力／出力インターフ
ェース３１８を有する。マイクロ・インストラクション
・コード３１０、たとえば縮小インストラクション・セ
ット、をプラットフォーム３０４に入れることも可能で
ある。種々の周辺装置、たとえば画像インターフェース
あるいはターミナル３２６、データ記憶装置３３０、印
刷装置３３４をプラットフォーム３０４に接続可能であ
る。オペレーティング・システム３０８は、コンピュー
タ・システム３００の種々の構成要素の操作を調和させ
る。これと同様なコンピュータ・システム３００の例は
ＩＢＭ ＲＩＳＣシステム／６０００（ＩＢＭ社の商
標）がある。コンピュータ業界の技術者は多くの同様な
コンピュータ・システム３００を熟知していることは容
易に理解される。

【００２９】図６はコンピュータ・システム３００によ
り走行させられる平滑化アルゴリズム４００の工程を示
すフローチャートである。図７および図８は区分的線形
曲線５１０、および区分的線形曲面５４０をそれぞれ示
す図であり、各図形を規定するパーツを示している。ス
テップ４１０において、平滑化する入力した区分的線形
図形４０５の頂点Ｖの集合＝｛ｖi：ｉ＝１、２、…、
ｎv｝を決定する。二次元曲線について、頂点５２０は
二次元ベクトルｖi＝（ｘi、ｙi）であり、同様に曲面
については三次元曲線であり、頂点５５０は三次元ベク
トルｖi＝（ｘi，ｙi，ｚi）である。区分的線形曲線５
１０を表示する望ましい手段は一対のリストＣ＝｛Ｖ，
Ｅ｝であり、頂点Ｖのリストは上記したとおりであり、
エッジＥのリストは、Ｅ＝｛ｅk：ｋ＝１、２、…、ｎ
E｝であり、各エッジ５３０ｅk＝（ｉk1、ｉk2）は一対
の異なった頂点の指標（ｉは頂点ｖiの指標）である。
区分的線形曲面５４０を表示する望ましい手段は一対の
リストＳ＝｛Ｖ，Ｆ｝であり、頂点Ｖのリストは上記し
たとおりであり、面Ｆのリストは、Ｆ＝｛ｆk：ｋ＝
１、２、…、ｎF｝であり、各面５６０ｆk＝（ｉk1、
…、ｉknfk）は一続きの頂点の非反復指標であり、それ
自体平坦である必要のない閉じた三次元多角形を示して
いる。あるケースでは、頂点ｎfkの数は面によって変化
し、それ以外のケースでは全ての面は同じ数の頂点を有
する。三角形曲面が最も一般的であり、全ての面は三角
ｆk＝（ｉk1、ｉk2、ｉk3）である。

【００３０】ステップ４２０では、頂点の近傍を入力し
た区分的線形図形４０５を表示する各頂点ｖiについて
決定する。図９は区分的線形曲面６０５の頂点６１０の
典型的な近傍を示す図である。頂点６１０ｖiの近傍を
表示する望ましい手段は頂点の指標の集合ｉ*による。
指標ｊが近傍ｉ*に属するなら、ｖjはｖiの近傍である
と言える。図９において、頂点６１０の近傍は頂点６１
２、６１４、６１６、６１８、６２０、６２２、６２４
である。どの頂点もそれ自身の近傍とはならないが、他
にそれ以上の規制はその近傍には課せられない。特に、
頂点ｖiが頂点ｖjの近傍ではなく頂点ｖjが頂点ｖiの近
傍であることを可能とする。前記の状態、つまり、常
に、頂点ｖjが頂点ｖiの近傍であり、またｖiがｖjの近
傍であるなら、近傍構造は対称である。また、頂点ｖi
の近傍ｉ*が空集合も可能である。図形４０５にたいす
る近傍構造は全ての近傍｛ｉ*：ｉ＝１，２，…、ｎv｝
の族として規定される。近傍構造の望ましい選択は、一
つのエッジ（あるいは面）を共有する頂点ｖiとｖjの各
対にたいし、ｖjをｖiの近傍としｖiをｖjの近傍とする
第一オーダ近傍構造である。この第一オーダ近傍構造は
対称である。図１０は区分的線形曲面６２５の頂点６３
０の第一オーダ近傍を示す図である。図１０において、
頂点６３０の第一オーダ近傍は頂点６３０とエッジ６５
０あるいは面６６０を共有する頂点６３２、６３４，６
３６，６３８，６４０である。

【００３１】ステップ４３０では、負のスケール・ファ
クタの大きさは正のスケール・ファクタの大きさより大
きい反対の符号の第一スケール・ファクタと第二スケー
ル・ファクタが規定される。望ましい実施例では、第一
スケール・ファクタλは正であり、第二スケール・ファ
クタμは負である（つまり、０＜λ＜−μ）。説明を容
易にするために、この制限のない実施例は本出願の残り
を通じて実施される。

【００３２】平滑化コア４３５はステップ４４０、４５
０、４６０、４７０、４７５から成る。平滑化コアは、
平滑基準４８０が満たされるまである回数おこなわれ
る。望ましい実施例では、スケール・ファクタは、一回
の反復からつぎの平滑化コアに変化することが許されて
いる。別の望ましい実施例では、スケール・ファクタ
は、区分的線形図形の頂点から頂点に変化することが許
されている。さらに、別の望ましい実施例では、スケー
ル・ファクタは、一回の反復からつぎの平滑化コアに、
また区分的線形図形の頂点から頂点に変化する。

【００３３】ステップ４４０では、第一ベクトル平均お
よび第一ベクトル変位を区分的線形図形の全ての頂点に
たいして決定する。図１１は、現在位置におけるその全
ての頂点を有する区分的線形図形７０５の一頂点の第一
ベクトル平均７２６および第一ベクトル変位７２８を示
す図である。頂点ｖiの近傍ｉ*が空なら、頂点ｖiの第
一ベクトル平均７２６Δｖiはゼロ・ベクトルに等しく
設定する。他の場合では、頂点ｖiの第一ベクトル平均
７２６Δｖiは、頂点ｖiの現在位置７１０から近傍頂点
ｖjの現在位置に延伸する第一ベクトル７１２、７１
４、７１６、７１８、７２０、７２２、７２４ｖj−ｖi
の平均として決定する。頂点ｖiの第一ベクトル変位７
２８λΔｖiは第一ベクトル平均７２６Δｖiに第一スケ
ール・ファクタλを掛けることにより決定する。

【００３４】これに関連して、ベクトル平均７２６は第
一ベクトル（上記のもの）のベクトル和を近傍ｉ*のベ
クトル数で割ることにより決定する。別の実施例では、
ベクトル平均７２６は単にベクトルの和である。

【００３５】ステップ４５０では、第一頂点位置を区分
的線形図形の全ての頂点について決定する。図１１は頂
点ｖiの第一頂点位置７３０も示している。頂点ｖiの第
一頂点位置７３０ｖi’＝ｖi＋λΔｖiは、その現在位
置７１０から頂点を第一変位ベクトル７２８λΔｖiの
そばに移動することにより決定する。頂点の近傍が空な
ら、第一ベクトル変位はゼロであり、その頂点の第一位
置はその現在位置に等しい。

【００３６】ステップ４６０では、第二ベクトル平均お
よび第二ベクトル変位を区分的線形図形の全ての頂点に
ついて決定する。図１２は区分的線形図形７３５の一頂
点の第二ベクトル平均７５６および第二ベクトル変位７
５８を示す図である。頂点７４０ｖiの近傍ｉ*が空な
ら、頂点ｖiの第二ベクトル平均７５６Δｖi’はゼロ・
ベクトルに等しく設定する。他の場合では、頂点ｖiの
第二ベクトル平均７５６Δｖi’は、頂点ｖiの第一位置
７４０から近傍頂点ｖjの第一位置に延伸する第二ベク
トル７４２、７４４、７４６、７４８、７５０、７５
２、７５４ｖj’−ｖi’の平均として決定する。頂点ｖ
iの第二ベクトル変位７５８μΔｖi’は第二ベクトル平
均７５６Δｖi’に第二スケール・ファクタμを掛ける
ことにより決定する。

【００３７】前記のように、ベクトル平均７５６は第二
ベクトル（上記のもの）のベクトル和を近傍ｉ*のベク
トル数で割ることにより決定する。別の実施例では、ベ
クトル平均７５６は単にベクトルの和である。

【００３８】スケール・ファクタは反対の符号なので、
第一ベクトル変位７２８と第二ベクトル変位７５８は、
ほぼ反対方向である。この方法では、頂点（７１０、７
４０）はその最終位置を介して前後に移動し、それゆ
え、全体的に平滑化した図形７３５は縮退しない。

【００３９】さらに、本発明はＮ次元の対象物や多形体
に適用可能である。これはＮ次元空間における近傍およ
び近傍頂点／ベクトルを規定することにより行われる。

【００４０】ステップ４７０では、第二頂点位置が区分
的線形図形の全ての頂点に対して決められる。図１２は
頂点ｖiの第二頂点位置７６０も示している。頂点ｖiの
第二頂点位置７６０ｖi”＝ｖi’＋μΔｖi’は、その
第一位置７４０から頂点を第二変位ベクトル７５８μΔ
ｖi’のそばに移動することにより決定する。頂点の近
傍が空なら、第二ベクトル変位はゼロであり、第二位置
はその現在位置に等しい。

【００４１】一つの頂点に近傍を割り当てない場合、頂
点位置は平滑化アルゴリズム４００を通じて変化しな
い。これと同様に複数の頂点は曲面あるいは曲線平滑化
における輪郭条件として、あるいは規制として使用する
ことができる。

【００４２】ステップ４７５において、各頂点の現在位
置を各々の第二位置として確立する。

【００４３】ステップ４８０において、平滑基準を評価
する。平滑基準が不満足なら、このアルゴリズム・ルー
プを平滑化コア４３５のはじめに戻す。他の場合、この
アルゴリズムはステップ４９０で終了し、得られた平滑
化処理図形を出力する。

【００４４】図１４は、平滑基準を満たさない区分的線
形図形９６０と満たす図形９７０を示す図である。

【００４５】望ましい実施例では、頂点ｖiの第一（第
二）ベクトル平均は、それぞれ近傍加重値ｗijにより加
重された第一（第二）ベクトルｖj−ｖiの加重平均とし
て決定する。これは加重値の和によって割ることも、割
らないことも可能である。より望ましい実施例では、近
傍加重値は全て正で、各頂点についておこなわれ、その
全ての近傍加重値の和は値１に等しい。図１３は、第一
ベクトル８３２、８３４、８３６、８３８、８４０、８
４２、８４４がベクトル８１２、８１４、８１６、８１
８、８２０、８２２、８２４の加重により決定される頂
点８１０ｖiの近傍を示す図である。別の実施例では、
加重値は平滑化コア４３５の反復から反復へ到るさいに
変えることができる。

【００４６】望ましい実施例では、平滑基準４８０は平
滑化コア４３５がある回数Ｎ実行された時に満たされ
る。図１５は、この望ましい平滑基準を組み込むために
修正した図６のフローチャートを示す。（図６と同じ機
能を有するステップは同じ番号をつけてある。）平滑化
コアの反復回数Ｎは、第一回目を行う前に決める（ステ
ップ１０１０）。反復回数がその値Ｎに達するとこのア
ルゴリズムは終了する（ステップ１０２０）。

【００４７】さらに望ましい実施例では、第一スケール
・ファクタλ、第二スケール・ファクタμ（ステップ４
３０）、および反復回数Ｎはローパス・フィルタ・パラ
メータの関数として演算される。図１７はローパス・フ
ィルタ変換関数１０５０およびローパス・フィルタ・パ
ラメータを示す図である。ローパス・フィルタ・パラメ
ータはパス・バンド曲率１０６０ｋPB、パス・バンド・
リップル１０７０ｋPB、ストップ・バンド曲率１０８０
ｋSB、ストップ・バンド・リップル１０９０ｋSB等であ
る。ローパス・フィルタ・パラメータは以下の規制［１
００］、［１１０］、［１２０］を満たさなければなら
ない。

【００４８】 ０＜ｋPB＜ｋSB ［１００］ ０＜δPB ［１１０］ ０＜δSB ［１２０］

【００４９】図１８は、この望ましい平滑基準を組み込
むために修正した図１５のフローチャートを示す。図６
および図１５のフローチャートと同じ機能を示すものは
同じ番号で示してある。ステップ１１１０では、パス・
バンド曲率およびパス・バンド・リップルが規定され
る。ステップ１１３０では、ストップ・バンド曲率およ
びストップ・バンド・リップルが規定される。ステップ
１１５０では、第一スケール・ファクタ、第二スケール
・ファクタ、および反復の回数をローパス・フィルタ・
パラメータの関数として演算する。第一スケール・ファ
クタλ、第二スケール・ファクタμ、および反復の回数
Ｎは、以下に示す等式および不等式［２００］、［２１
０］、［２２０］、［２３０］、［２４０］、［２５
０］の系の解答としてローパス・フィルタ・パラメータ
から演算する。

【００５０】

【数２】

【００５１】この系が一以上の解答を導くなら、演算時
間を最小にするＮの最小値に対応した解答が選択され
る。これら等式の導出の詳細な説明は付録を参照のこ
と。

【００５２】望ましい実施例では、本発明は区分的線形
図形の画像を生成するために使用することができる。図
１９は、コンピュータ端末１３１０に表示された区分的
線形図形の画像１３２０を示す図である。

【００５３】本発明の原理を組み込んだ他の実施例が可
能であり、また、上記記述は単にこの原理の説明であ
り、なんら制限するものではない。たとえば、本発明の
適応は、等曲面構造アルゴリズムにより生成されるもの
のように平滑な曲線および曲面の区分的線形近似の平滑
化、対象認識システム内の予備的処理ステップとしての
曲線および曲面の平滑化、薬品設計システムにおける分
子の曲面の平滑化、およびコンピュータ支援幾何学的設
計システムにおける設計した曲線や曲面の平滑化等を含
む。もちろん、これらに限定されるものではない。

【００５４】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００５５】（１）ａ．区分的線形図形を描き表す複数
の頂点の集合を決定するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
傍は、頂点がその近傍に含まれないように頂点の集合か
らゼロ以上の近傍頂点の小集合からなり、 ｃ．反対の符号の第一、第二スケール・ファクタを記述
するステップで、負のスケール・ファクタの大きさは正
のスケール・ファクタより大きく、 ｄ．各頂点に対する第一ベクトル変位を決定するステッ
プで、該第一ベクトル変位は第一スケール・ファクタと
第一ベクトル平均を掛けたものであり、第一ベクトル平
均は全てのゼロ以上の近傍ベクトルの平均であり、各近
傍ベクトルは頂点からその近傍頂点の各々にいたるもの
であり、全ての頂点はそれぞれ現在位置にあり、 ｅ．各頂点の第一位置を決定するステップで、該第一位
置は現在の位置からの第一ベクトル変位により移動した
頂点の位置であり、 ｆ．各頂点に対する第二ベクトル変位を決定するステッ
プで、該第二ベクトル変位は第二スケール・ファクタと
第二ベクトル平均を掛けたものであり、第二ベクトル平
均は全てのゼロ以上の第二近傍ベクトルの平均であり、
各第二近傍ベクトルは頂点からその近傍頂点の各々にい
たるものであり、全ての頂点はそれぞれ第一位置にあ
り、 ｇ．各頂点の第二位置を決定するステップで、該第二位
置はそれらの第一位置からの第二ベクトル変位により移
動した頂点の位置であり、 ｈ．その各々の第二位置として各頂点の現在位置を確立
するステップと、 ｉ．それらの第二位置における頂点により規定される図
形が平滑基準を満たしていないなら、平滑基準が満たさ
れるまでステップｄからｉを繰り返すステップを含むこ
とを特徴とする区分的線形図形を平滑化するための方
法。 （２）近傍ベクトルは複数の近傍頂点から頂点への方向
にあり、正のスケール・ファクタは負のスケール・ファ
クタより大きさが大きいことを特徴とする上記（１）に
記載の平滑化方法。 （３）上記図形は曲線であることを特徴とする上記
（１）に記載の平滑化方法。 （４）上記図形は曲面であることを特徴とする上記
（１）に記載の平滑化方法。 （５）ベクトル平均はベ
クトルの和であることを特徴とする上記（１）に記載の
平滑化方法。 （６）上記スケール・ファクタは反復従属であることを
特徴とする上記（１）に記載の平滑化方法。 （７）上記スケール・ファクタは頂点従属であることを
特徴とする上記（１）に記載の平滑化方法。 （８）上記スケール・ファクタは反復従属および頂点従
属であることを特徴とする上記（１）に記載の平滑化方
法。 （９）ａ．区分的線形図形を描き表す一個以上の頂点の
集合を決定するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
傍は、頂点がその近傍に含まれないように頂点の集合か
らゼロ以上の近傍頂点の小集合からなり、 ｃ．反対の符号の第一、第二スケール・ファクタを記述
するステップで、負のスケール・ファクタの大きさは正
のスケール・ファクタより大きく、 ｄ．各頂点に対する第一ベクトル変位を決定するステッ
プで、該第一ベクトル変位は第一スケール・ファクタと
第一ベクトル平均を掛けたものであり、第一ベクトル平
均は全てのゼロ以上の近傍ベクトルの加重平均であり、
各近傍ベクトルは頂点からその近傍頂点の各々にいたる
ベクトルであり、かつ、その各々の近傍加重値により加
重され、全ての頂点はそれぞれの現在位置にあり、 ｅ．各頂点の第一位置を決定するステップで、該第一位
置は現在の位置からの第一ベクトル変位により移動した
頂点の位置であり、 ｆ．各頂点に対する第二ベクトル変位を決定するステッ
プで、該第二ベクトル変位は第二スケール・ファクタと
第二ベクトル平均を掛けたものであり、第二ベクトル平
均は全てのゼロ以上の第二近傍ベクトルの加重平均であ
り、各第二近傍ベクトルは頂点からその近傍頂点の各々
にいたるものであり、全ての頂点はそれぞれの第一位置
にあり、 ｇ．各頂点の第二位置を決定するステップで、該第二位
置はそれらの第一位置からの第二ベクトル変位により移
動した頂点の位置であり、 ｈ．それらの第二位置における頂点により規定される図
形が平滑基準を満たしていないなら、その各々の第二位
置として各頂点の現在位置を確立し、かつ平滑基準が満
たされるまでステップｄからｈを繰り返すステップを含
む区分的線形図形を平滑化するための方法。 （１０）上記全ての近傍加重値は、各近傍における近傍
加重値の全ての和が値１となる近傍加重値を有する正の
数であることを特徴とする上記（９）に記載の平滑化方
法。 （１１）上記平滑基準を満たす頂点は、画像インターフ
ェースに表示される平滑化された図形の画像を規定する
ことを特徴とする上記（９）に記載の平滑化方法。 （１２）上記区分的線形図形は任意の寸法の多形体であ
ることを特徴とする上記（９）に記載の平滑化方法。 （１３）上記加重値は全てのステップを通じて予め特定
し、かつ一定に維持することを特徴とする上記（９）に
記載の平滑化方法。 （１４）上記加重値は一以上の反復の際に変更すること
を特徴とする上記（９）に記載の平滑化方法。 （１５）上記加重平均は和であることを特徴とする上記
（９）に記載の平滑化方法。 （１６）ａ．区分的線形図形を描き表す複数の頂点の集
合を決定するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
傍は、頂点がその近傍に含まれないように頂点の集合か
らゼロ以上の近傍頂点の小集合からなり、 ｃ．反対の符号の第一、第二スケール・ファクタを記述
するステップで、負のスケール・ファクタの大きさは正
のスケール・ファクタより大きく、 ｄ．反復回数を書くステップと、 ｅ．各頂点に対する第一ベクトル変位を決定するステッ
プで、該第一ベクトル変位は第一スケール・ファクタと
第一ベクトル平均を掛けたものであり、第一ベクトル平
均は全てのゼロ以上の近傍ベクトルの平均であり、各近
傍ベクトルは頂点からその近傍頂点の各々にいたるベク
トルであり、かつ、全ての頂点はそれぞれの現在位置に
あり、 ｆ．各頂点の第一位置を決定するステップで、該第一位
置は現在の位置からの第一ベクトル変位により移動した
頂点の位置であり、 ｇ．各頂点に対する第二ベクトル変位を決定するステッ
プで、該第二ベクトル変位は第二スケール・ファクタと
第二ベクトル平均を掛けたものであり、第二ベクトル平
均は全てのゼロ以上の第二近傍ベクトルの加重平均であ
り、各第二近傍ベクトルは頂点からその近傍頂点の各々
にいたるものであり、全ての頂点はそれぞれ第一位置に
あり、 ｈ．各頂点の第二位置を決定するステップで、該第二位
置はそれらの第一位置からの第二ベクトル変位により移
動した頂点の位置であり、 ｉ．その各々の第二位置として各頂点の現在位置を確立
するステップと、 ｊ．ステップｅからｉが実行された回数が上記反復回数
より少ないなら、上記平滑基準が満たされるまでステッ
プｄからｉを繰り返すステップと、を含むことを特徴と
する区分的線形図形を平滑化するための方法。 （１７）ａ．区分的線形図形を描き表す複数の頂点の集
合を決定するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
傍は、頂点がその近傍に含まれないように頂点の集合か
らゼロ以上の近傍頂点の小集合からなり、 ｃ．パス・バンド曲率ｋPB、パス・バンド・リップルδ
PB、ストップ・バンド曲率ｋSB、およびストップ・バン
ド・リップルδSBを記述するステップで、それぞれ０＜
ｋPB＜ｋSB、０＜δPB、０＜δSBの関係があり、 ｄ．下記の等式および不等式を解くことにより、第一ス
ケール・ファクタλ、第二スケール・ファクタμ、反復
回数Ｎを演算するステップで、下記の等式および不等式
の系が一以上の解答を導くなら、演算時間を最小にする
Ｎの最小値に対応した解答が選択され、

【数３】 ｅ．各頂点に対する第一ベクトル変位を決定するステッ
プで、該第一ベクトル変位は第一スケール・ファクタと
第一ベクトル平均を掛けたものであり、第一ベクトル平
均は全てのゼロ以上の近傍ベクトルの平均であり、各近
傍ベクトルは頂点からその近傍頂点の各々にいたるベク
トルであり、かつ、全ての頂点はそれぞれ現在位置にあ
り、 ｆ．各頂点の第一位置を決定するステップで、該第一位
置は現在の位置からの第一ベクトル変位により移動した
頂点の位置であり、 ｇ．各頂点に対する第二ベクトル変位を決定するステッ
プで、該第二ベクトル変位は第二スケール・ファクタと
第二ベクトル平均を掛けたものであり、第二ベクトル平
均は全てのゼロ以上の第二近傍ベクトルの平均であり、
各第二近傍ベクトルは頂点からその近傍頂点の各々にい
たるものであり、全ての頂点はそれぞれ第一位置にあ
り、 ｈ．各頂点の第二位置を決定するステップで、該第二位
置はそれらの第一位置からの第二ベクトル変位により移
動した頂点の位置であり、 ｉ．その各々の第二位置として各頂点の現在位置を確立
するステップと、 ｊ．ステップｅからｉが実行された回数が上記反復回数
より少ないなら、上記ステップｅからｊを繰り返すステ
ップと、を含むことを特徴とする区分的線形図形を平滑
化するための方法。 （１８）区分的線形図形を平滑化するシステムにおい
て、 Ａ．オペレーティング・システム、メモリ、中央処理装
置を有するコンピュータ、および画像インターフェース
と、 Ｂ．上記中央処理装置により実行される区分的線形図形
を平滑化するアプリケーション・プログラムとから構成
され、該アプリケーション・プログラムは ａ．区分的線形図形を描き表す複数の頂点の集合を決定
するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
傍は、頂点がその近傍に含まれないように頂点の集合か
らゼロ以上の近傍頂点の小集合からなり、 ｃ．反対の符号の第一、第二スケール・ファクタを記述
するステップで、負のスケール・ファクタの大きさは正
のスケール・ファクタより大きく、 ｄ．各頂点に対する第一ベクトル変位を決定するステッ
プで、該第一ベクトル変位は第一スケール・ファクタと
第一ベクトル平均を掛けたものであり、第一ベクトル平
均は全てのゼロ以上の近傍ベクトルの平均であり、各近
傍ベクトルは頂点からその近傍頂点の各々にいたるもの
であり、全ての頂点はそれぞれ現在位置にあり、 ｅ．各頂点の第一位置を決定するステップで、該第一位
置は現在の位置からの第一ベクトル変位により移動した
頂点の位置であり、 ｆ．各頂点に対する第二ベクトル変位を決定するステッ
プで、該第二ベクトル変位は第二スケール・ファクタと
第二ベクトル平均を掛けたものであり、第二ベクトル平
均は全てのゼロ以上の第二近傍ベクトルの平均であり、
各第二近傍ベクトルは頂点からその近傍頂点の各々にい
たるものであり、全ての頂点はそれぞれの第一位置にあ
り、 ｇ．各頂点の第二位置を決定するステップで、該第二位
置はそれらの第一位置からの第二ベクトル変位により移
動した頂点の位置であり、 ｈ．その各々の第二位置として各頂点の現在位置を確立
するステップと、 ｉ．それらの第二位置における頂点により規定される図
形が平滑基準を満たしていないなら、平滑基準が満たさ
れるまでステップｄからｉを繰り返すステップを含み、 よって現在位置にある複数の頂点を有する区分的線形図
形を上記画像インターフェースに送ることを特徴とする
システム。

【００５６】付録：ローパス・フィルタ・パラメータお
よび、第一スケール・ファクタ、第二スケール・ファク
タ、平滑化コアの反復数等に関する等式を決定するた
め、対応の頂点の初めの位置の関数として、また、第一
スケール・ファクタ、第二スケール・ファクタ、平滑化
コアの反復数等の関数として図形の頂点の最終位置にた
いする解析式を見つける必要がある。

【００５７】二次元図形について、Ｘを頂点ｖiの現在
位置の座標（ｘi，ｙi）に等しいｉ次の行を有する行列
ｎV×２とする。三次元図形について、Ｘを頂点ｖiの現
在位置の座標（ｘi，ｙi，ｚi）に等しいｉ次の行を有
する行列ｎV×３とする。Ｘ’およびＸ”を同様にし
て、頂点の第一位置および第二位置の座標をそれぞれ有
する行列とする。ＸNを同様にして、平滑化コア４３５
をＮ回実行した後、このアルゴリズムが停止する時の頂
点の現在位置の座標を有する行列とする。

【００５８】行列ＸおよびＸ’間の関係は、 Ｘ’＝
（Ｉ−λＫ）Ｘ の行列の形に表すことができる。同式
において、λは第一スケール・ファクタ、Ｋはｎv×ｎv
行列の平方、Ｋ＝Ｉ−Ｗ、Ｉはｎv×ｎv単位行列、Ｗは
以下に定義する成分｛ｗij：ｉ，ｊ＝１、２、…、ｎ
v｝を有するｎv×ｎv行列の平方である。

【００５９】各指数ｉ＝１、２、…、ｎv、指数ｊ＝
１、２、…、ｎvについては、頂点ｖjが頂点ｖiの近傍
でないなら、成分ｗijは０に等しい。他は、頂点ｖiの
近傍ｉ*が｜ｉ*｜成分を有するなら、頂点ｖiの各近傍
ｖjについては、ｗijはｖiの近傍の数の逆数１／｜ｉ*
｜に等しい。

【００６０】同様に、行列Ｘ’およびＸ”間の関係は、
Ｘ’＝（Ｉ−μＫ）Ｘ の行列の形に表すことができ
る。同式において、μは第二スケール・ファクタ、Ｋは
上記の行列と同じである。

【００６１】行列Ｉ−λＫとＩ−μＫは互いに交換可能
であるので、平滑化コア４３５がＮ回実行される前後の
頂点の位置間の関係は、 ＸN＝（（Ｉ−μＫ）（Ｉ−λＫ））NＸ の行列の形に
表すことができる。

【００６２】近傍構造が対称である時、上記のように定
義した行列Ｋは全て実数の負ではない固有値、および、
ｎv次元空間の各々の基数を形成する左右固有ベクトル
の集合を有する。０≦ｋ1≦ｋ2≦…≦ｋnvを行列Ｋの固
有値とし、ｆ（ｋ）を次の式によって定義する一変数ｋ
の多項式とする。 ｆ（ｋ）＝（１−λｋ）（１−μｋ）

【００６３】一変数の多項式は平方行列で数値を求める
ことができる。特に、行列（（１−λｋ）（１−μ
ｋ））Nは行列Ｋの多項式ｆ（ｋ）Nとして表すことがで
きる。ｕ1、ｕ2、…、ｕnvが、それぞれ固有値ｋ1、ｋ
2、…、ｋnvと関連のある行列Ｋの線形独立単位長右固
有ベクトルの集合なら、ｕ1、ｕ2、…、ｕnvも固有値ｆ
（ｋ1）N、…、ｆ（ｋnv）Nと関連した行列ｆ（ｋ）Nの
右固有ベクトルである。さらに、ｕ1、ｕ2、…、ｕnvが
ｎv次元空間の基底を構成するので、行列Ｘの各列ベク
トルｘ（区分的線形図形の頂点の第一、第二、あるいは
第三座標のベクトル）は基底ベクトルの線形結合として
固有の方法で次のように表すことができる。

【００６４】ｘ＝ξ1ｕ1＋ … ＋ξnvｕnv ここで、ξ1 …ξnvは一定であり、そして、 ｆ（Ｋ）Nｘ＝ｆ（ｋ1）N ξ1ｕ1＋ … ＋ｆ（ｋn）Nξ
nvｕnv

【００６５】図１６は多項式ｆ（ｋ）のグラフを示す図
である。図１７はローパス・フィルタの変換関数１０５
０を示すグラフ図である。図１７に示した変換関数１０
５０はｆ（ｋ）Nのグラフである。多項式ｆ（ｋ）のグ
ラフ１０１５は１０２５ｋ＝１／λ＞０および１０３０
ｋ＝１／μ＜０での根を有する逆さまな放物線である。
多項式ｆ（ｋ）の値は１／μ＜ｋ＜１／λにたいしては
正であり、ｋ＜１／μおよびｋ＞１／λにたいしては負
である。さらに、１０４０ｋ＝０にたいして１０４５ｆ
（ｋ）＝１であり、また望ましい実施例ではμ＋λ＜０
なので、ｋの別の値があり、それを１０４２ｋPBとしｆ
（ｋPB）＝１とする。ｋPBの値は、 ｋPB＝１／λ＋１／μ＝μ＋λ／μλ＞０

【００６６】関数ｆ（ｋ）Nのグラフ１０５０は、関連
の範囲、つまり１０６５ｋ＝０から１０８５ｋ＝１／λ
で通常のローパス・フィルタ図形を表示する。パス・バ
ンド域は１０６５ｋ＝０から１０６０ｋ＝ｋPBに展開す
る。パス・バンド域におけるｋの値について、ｆ（ｋ）
Nは値１０７５より上でほとんど変化しない。変化域は
１０６０ｋ＝ｋPBから１０８５ｋ＝１／λに展開する。
ストップ・バンド域は１０８０ｋ＝ｋPBから１０８５ｋ
＝１／λに展開する。ストップ・バンド域のｋの値につ
いては、ｆ（ｋ）NはＮが増大するにつれ０に収束す
る。

【００６７】行列Ｋの固有値に関して、数ｆ（ｋi）の
大きさが１よりかなり小さいなら、つまり、ｋiがスト
ップ・バンド曲率ｋSBより大きい時、ｆ（ｋi）NはＮが
大なら０に極めて近づく。ｆ（ｋi）の大きさが１に近
いなら、つまり、ｋiがパス・バンド曲率ｋPBより大き
くない時、ｆ（ｋi）NはＮが大なら０に近づく。

【００６８】第一スケール・ファクタλ、第二スケール
・ファクタμ、パス・バンド曲率ｋPBの関数としての反
復数Ｎ、パス・バンド・リップルｋPB、ストップ・バン
ド曲率ｋSB、ストップ・バンド・リップルδ等を決定す
るため、上記説明に基づきこれらパラメータが［１１
０］、［１２０］、［２００］、［２１０］、［２２
０］、［２３０］の等式および不等式を満たさなければ
ならない。不等式［２４０］は、変換関数がパス・バン
ド域におけるパス・バンド・リップルにプラス１（１＋
δPB）より大きくてはならないという事に対応する。こ
れは変換関数ｆ（ｋ）Nが、パス・バンド域の中間点１
０６７で、その最大値 （（λ−μ）2／−４λμ）N を得ることによる。不等式［２５０］は、変換関数がス
トップ・バンド域においてストップ・バンド・リップル
より大きくてはならないという事を確立する。これは、
変換関数がストップ・バンド曲率のストップ・バンド域
におけるその最大値を得ることによる。

【００６９】

【発明の効果】本発明は、かなり多くの回数反復して適
用しても、縮退を防ぎながら平滑化効果を生み出す。本
発明は一般的かつ任意の多角形曲線、多面曲面、さらに
は任意の寸法の多形体に適用する。本発明は曲率の関数
としてローパス・フィルタ効果を作る。本発明によれ
ば、必要な工程数は曲線あるいは曲面の頂点、エッジ、
あるいは面の数に比例するので、最小の演算コストを得
られる。本発明が必要とする頂点の近傍についての情報
を表示したりエンコードするための記憶容量は最小であ
る。

【図面の簡単な説明】

【図１】平滑曲線の区分的近似の従来技術の例を示す
図。

【図２】平滑曲面の区分的近似の従来技術の例を示す
図。

【図３】曲線の縮退問題の従来技術の例を示す図。

【図４】曲面の縮退問題の従来技術の例を示す図。

【図５】本発明の方法を実行する通常のコンピュータ・
システムのブロック図。

【図６】本発明の平滑化処理アルゴリズムの工程を示す
フローチャート。

【図７】区分的線形曲線を示し、その形状を規定するパ
ーツを示す図。

【図８】区分的線形曲面を示し、その形状を規定するパ
ーツを示す図。

【図９】区分的線形曲面の頂点の典型的な近傍を示す
図。

【図１０】区分的線形曲面の頂点の典型的な第一オーダ
の近傍を示す図。

【図１１】一区分的線形図形の第一頂点の第一ベクトル
平均および第一ベクトル変位を示す図。

【図１２】一区分的線形図形の第二頂点の第二ベクトル
平均および第二ベクトル変位を示す図。

【図１３】近傍ベクトルに加重する望ましい実施例を示
すベクトル図。

【図１４】平滑基準を満たさない区分的線形図形９６０
と満たす図形９７０を示す図

【図１５】平滑基準の望ましい実施例における本発明の
平滑化アルゴリズムのステップを示すフローチャート。

【図１６】平滑化コアの曲率ローパス・フィルタ変換関
数および曲率ローパス・フィルタ・パラメータを示す
図。

【図１７】全アルゴリズムの曲率ローパス・フィルタ変
換関数および曲率ローパス・フィルタ・パラメータを示
す図。

【図１８】平滑基準のより望ましい実施例における本発
明の平滑化アルゴリズムのステップを示すフローチャー
ト。

【図１９】本発明によるコンピュータ画像ディスプレイ
で生成した区分的線形画像の図。

【符号の説明】

１１０ 平滑曲線 １２０ 区分的線形近似 １３０ 平滑曲面 １４０ 区分的線形近似 ２１０ 区分的線形曲線 ２２０ 縮退した区分的線形曲線 ２３０ 区分的線形曲面 ２４０ 縮退した区分的線形曲面 ３００ コンピュータ・システム ３０２ アプリケーション・プログラム ３０４ コンピュータ・プラットフォーム ３０５ コンパイラ ３０６ オプティマイザ ３０８ オペレーティング・システム ３１０ マイクロ・インストラクション・コード ３１２ ハードウェア・ユニット ４００ 平滑化アルゴリズム ５１０ 区分的線形曲線 ５２０ 頂点 ５３０ エッジ ５４０ 区分的線形曲面 ５５０ 頂点 ５６０ 面

Claims (18)

【特許請求の範囲】
1. 【請求項１】ａ．区分的線形図形を描き表す複数の頂点
   の集合を決定するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
   傍は、頂点がその近傍に含まれないように頂点の集合か
   らゼロ以上の近傍頂点の小集合からなり、 ｃ．反対の符号の第一、第二スケール・ファクタを記述
   するステップで、負のスケール・ファクタの大きさは正
   のスケール・ファクタより大きく、 ｄ．各頂点に対する第一ベクトル変位を決定するステッ
   プで、該第一ベクトル変位は第一スケール・ファクタと
   第一ベクトル平均を掛けたものであり、第一ベクトル平
   均は全てのゼロ以上の近傍ベクトルの平均であり、各近
   傍ベクトルは頂点からその近傍頂点の各々にいたるもの
   であり、全ての頂点はそれぞれ現在位置にあり、 ｅ．各頂点の第一位置を決定するステップで、該第一位
   置は現在の位置からの第一ベクトル変位により移動した
   頂点の位置であり、 ｆ．各頂点に対する第二ベクトル変位を決定するステッ
   プで、該第二ベクトル変位は第二スケール・ファクタと
   第二ベクトル平均を掛けたものであり、第二ベクトル平
   均は全てのゼロ以上の第二近傍ベクトルの平均であり、
   各第二近傍ベクトルは頂点からその近傍頂点の各々にい
   たるものであり、全ての頂点はそれぞれの第一位置にあ
   り、 ｇ．各頂点の第二位置を決定するステップで、該第二位
   置はそれらの第一位置からの第二ベクトル変位により移
   動した頂点の位置であり、 ｈ．その各々の第二位置として各頂点の現在位置を確立
   するステップと、 ｉ．それらの第二位置における頂点により規定される図
   形が平滑基準を満たしていないなら、平滑基準が満たさ
   れるまでステップｄからｉを繰り返すステップを含むこ
   とを特徴とする区分的線形図形を平滑化するための方
   法。
2. 【請求項２】上記近傍ベクトルは複数の近傍頂点から頂
   点への方向にあり、正のスケール・ファクタは負のスケ
   ール・ファクタより大きさが大きいことを特徴とする請
   求項１に記載の平滑化方法。
3. 【請求項３】上記図形は曲線であることを特徴とする請
   求項１に記載の平滑化方法。
4. 【請求項４】上記図形は曲面であることを特徴とする請
   求項１に記載の平滑化方法。
5. 【請求項５】上記ベクトル平均はベクトルの和であるこ
   とを特徴とする請求項１に記載の平滑化方法。
6. 【請求項６】上記スケール・ファクタは反復従属である
   ことを特徴とする請求項１に記載の平滑化方法。
7. 【請求項７】上記スケール・ファクタは頂点従属である
   ことを特徴とする請求項１に記載の平滑化方法。
8. 【請求項８】上記スケール・ファクタは反復従属および
   頂点従属であることを特徴とする請求項１に記載の平滑
   化方法。
9. 【請求項９】ａ．区分的線形図形を描き表す一個以上の
   頂点の集合を決定するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
   傍は、頂点がその近傍に含まれないように頂点の集合か
   らゼロ以上の近傍頂点の小集合からなり、 ｃ．反対の符号の第一、第二スケール・ファクタを記述
   するステップで、負のスケール・ファクタの大きさは正
   のスケール・ファクタより大きく、 ｄ．各頂点に対する第一ベクトル変位を決定するステッ
   プで、該第一ベクトル変位は第一スケール・ファクタと
   第一ベクトル平均を掛けたものであり、第一ベクトル平
   均は全てのゼロ以上の近傍ベクトルの加重平均であり、
   各近傍ベクトルは頂点からその近傍頂点の各々にいたる
   ベクトルであり、かつ、その各々の近傍加重により加重
   され、全ての頂点はそれぞれの現在位置にあり、 ｅ．各頂点の第一位置を決定するステップで、該第一位
   置は現在の位置からの第一ベクトル変位により移動した
   頂点の位置であり、 ｆ．各頂点に対する第二ベクトル変位を決定するステッ
   プで、該第二ベクトル変位は第二スケール・ファクタと
   第二ベクトル平均を掛けたものであり、第二ベクトル平
   均は全てのゼロ以上の第二近傍ベクトルの加重平均であ
   り、各第二近傍ベクトルは頂点からその近傍頂点の各々
   にいたるものであり、全ての頂点はそれぞれの第一位置
   にあり、 ｇ．各頂点の第二位置を決定するステップで、該第二位
   置はそれらの第一位置からの第二ベクトル変位により移
   動した頂点の位置であり、 ｈ．それらの第二位置における頂点により規定される図
   形が平滑基準を満たしていないなら、その各々の第二位
   置として各頂点の現在位置を確立し、かつ平滑基準が満
   たされるまでステップｄからｈを繰り返すステップを含
   む区分的線形図形を平滑化するための方法。
10. 【請求項１０】上記全ての近傍加重値は、各近傍におけ
    る近傍加重値の全ての和が値１となる近傍加重値を有す
    る正の数であることを特徴とする請求項９に記載の平滑
    化方法。
11. 【請求項１１】上記平滑基準を満たす頂点は、画像イン
    ターフェースに表示される平滑化された図形の画像を規
    定することを特徴とする請求項９に記載の平滑化方法。
12. 【請求項１２】上記区分的線形図形は任意の寸法の多形
    体であることを特徴とする請求項９に記載の平滑化方
    法。
13. 【請求項１３】上記加重値は全てのステップを通じて予
    め特定し、かつ一定に維持することを特徴とする請求項
    ９に記載の平滑化方法。
14. 【請求項１４】上記加重値は一以上の反復の際に変更す
    ることを特徴とする請求項９に記載の平滑化方法。
15. 【請求項１５】上記加重平均は和であることを特徴とす
    る請求項９に記載の平滑化方法。
16. 【請求項１６】ａ．区分的線形図形を描き表す複数の頂
    点の集合を決定するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
    傍は、頂点がその近傍に含まれないように頂点の集合か
    らゼロ以上の近傍頂点の小集合からなり、 ｃ．反対の符号の第一、第二スケール・ファクタを記述
    するステップで、負のスケール・ファクタの大きさは正
    のスケール・ファクタより大きく、 ｄ．反復回数を書くステップと、 ｅ．各頂点に対する第一ベクトル変位を決定するステッ
    プで、該第一ベクトル変位は第一スケール・ファクタと
    第一ベクトル平均を掛けたものであり、第一ベクトル平
    均は全てのゼロ以上の近傍ベクトルの平均であり、各近
    傍ベクトルは頂点からその近傍頂点の各々にいたるベク
    トルであり、かつ、全ての頂点はそれぞれの現在位置に
    あり、 ｆ．各頂点の第一位置を決定するステップで、該第一位
    置は現在の位置からの第一ベクトル変位により移動した
    頂点の位置であり、 ｇ．各頂点に対する第二ベクトル変位を決定するステッ
    プで、該第二ベクトル変位は第二スケール・ファクタと
    第二ベクトル平均を掛けたものであり、第二ベクトル平
    均は全てのゼロ以上の第二近傍ベクトルの加重平均であ
    り、各第二近傍ベクトルは頂点からその近傍頂点の各々
    にいたるものであり、全ての頂点はそれぞれの第一位置
    にあり、 ｈ．各頂点の第二位置を決定するステップで、該第二位
    置はそれらの第一位置からの第二ベクトル変位により移
    動した頂点の位置であり、 ｉ．その各々の第二位置として各頂点の現在位置を確立
    するステップと、 ｊ．ステップｅからｉが実行された回数が上記反復回数
    より少ないなら、上記平滑基準が満たされるまでステッ
    プｄからｉを繰り返すステップと、を含むことを特徴と
    する区分的線形図形を平滑化するための方法。
17. 【請求項１７】ａ．区分的線形図形を描き表す複数の頂
    点の集合を決定するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
    傍は、頂点がその近傍に含まれないように頂点の集合か
    らゼロ以上の近傍頂点の小集合からなり、 ｃ．パス・バンド曲率ｋPB、パス・バンド・リップルδ
    PB、ストップ・バンド曲率ｋSB、およびストップ・バン
    ド・リップルδSBを記述するステップで、それぞれ０＜
    ｋPB＜ｋSB、０＜δPB、０＜δSBの関係があり、 ｄ．下記の等式および不等式を解くことにより、第一ス
    ケール・ファクタλ、第二スケール・ファクタμ、反復
    回数Ｎを演算するステップで、前記等式および不等式の
    系が一以上の解答を導くなら、演算時間を最小にするＮ
    の最小値に対応した解答が選択され、 【数１】 ｅ．各頂点に対する第一ベクトル変位を決定するステッ
    プで、該第一ベクトル変位は第一スケール・ファクタと
    第一ベクトル平均を掛けたものであり、第一ベクトル平
    均は全てのゼロ以上の近傍ベクトルの平均であり、各近
    傍ベクトルは頂点からその近傍頂点の各々にいたるベク
    トルであり、かつ、全ての頂点はそれぞれの現在位置に
    あり、 ｆ．各頂点の第一位置を決定するステップで、該第一位
    置は現在の位置からの第一ベクトル変位により移動した
    頂点の位置であり、 ｇ．各頂点に対する第二ベクトル変位を決定するステッ
    プで、該第二ベクトル変位は第二スケール・ファクタと
    第二ベクトル平均を掛けたものであり、第二ベクトル平
    均は全てのゼロ以上の第二近傍ベクトルの平均であり、
    各第二近傍ベクトルは頂点からその近傍頂点の各々にい
    たるものであり、全ての頂点はそれぞれの第一位置にあ
    り、 ｈ．各頂点の第二位置を決定するステップで、該第二位
    置はそれらの第一位置からの第二ベクトル変位により移
    動した頂点の位置であり、 ｉ．その各々の第二位置として各頂点の現在位置を確立
    するステップと、 ｊ．ステップｅからｉが実行された回数が上記反復回数
    より少ないなら、上記ステップｅからｊを繰り返すステ
    ップと、を含むことを特徴とする区分的線形図形を平滑
    化するための方法。
18. 【請求項１８】区分的線形図形を平滑化するシステムに
    おいて、 Ａ．オペレーティング・システム、メモリ、中央処理装
    置を有するコンピュータ、および画像インターフェース
    と、 Ｂ．上記中央処理装置により実行される区分的線形図形
    を平滑化するアプリケーション・プログラムとから構成
    され、該アプリケーション・プログラムは ａ．区分的線形図形を描き表す複数の頂点の集合を決定
    するステップと、 ｂ．各頂点に関連した近傍を決定するステップで、各近
    傍は、頂点がその近傍に含まれないように頂点の集合か
    らゼロ以上の近傍頂点の小集合からなり、 ｃ．反対の符号の第一、第二スケール・ファクタを記述
    するステップで、負のスケール・ファクタの大きさは正
    のスケール・ファクタより大きく、 ｄ．各頂点に対する第一ベクトル変位を決定するステッ
    プで、該第一ベクトル変位は第一スケール・ファクタと
    第一ベクトル平均を掛けたものであり、第一ベクトル平
    均は全てのゼロ以上の近傍ベクトルの平均であり、各近
    傍ベクトルは頂点からその近傍頂点の各々にいたるもの
    であり、全ての頂点はそれぞれの現在位置にあり、 ｅ．各頂点の第一位置を決定するステップで、該第一位
    置は現在の位置からの第一ベクトル変位により移動した
    頂点の位置であり、 ｆ．各頂点に対する第二ベクトル変位を決定するステッ
    プで、該第二ベクトル変位は第二スケール・ファクタと
    第二ベクトル平均を掛けたものであり、第二ベクトル平
    均は全てのゼロ以上の第二近傍ベクトルの平均であり、
    各第二近傍ベクトルは頂点からその近傍頂点の各々にい
    たるものであり、全ての頂点はそれぞれの第一位置にあ
    り、 ｇ．各頂点の第二位置を決定するステップで、該第二位
    置はそれらの第一位置からの第二ベクトル変位により移
    動した頂点の位置であり、 ｈ．その各々の第二位置として各頂点の現在位置を確立
    するステップと、 ｉ．それらの第二位置における頂点により規定される図
    形が平滑基準を満たしていないなら、平滑基準が満たさ
    れるまでステップｄからｉを繰り返すステップを含み、 よって現在位置にある複数の頂点を有する区分的線形図
    形を上記画像インターフェースに送ることを特徴とする
    区分的線形図形を平滑化するシステム。