ライン・サンプルによるアンチエイリアシング方法
【課題】 不連続画像の生成中、メモリの大幅な増加や描画速度の低下を伴わない改善されたアンチエイリアシング法を提供する。
【解決手段】 フィルタ関数を用い1つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行う方法であり、ライン・サンプルを定義する工程、フィルタ関数とライン・サンプルから累進的畳み込みを導き出す工程、不連続画像における所定位置で画素を選択する工程、該選択された画素に関してライン・サンプルの方向づけを行う工程、選択された画素に対応する連続画像中の1点から方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定する工程、測定距離における累進的畳み込みを評価して重み付きカバーレージ値を生成する工程、重み付きカバーレージ値を画素と関連付けて不連続画像中の画素のアンチエイリアシングを行う工程とを備える。
【解決手段】 フィルタ関数を用い1つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行う方法であり、ライン・サンプルを定義する工程、フィルタ関数とライン・サンプルから累進的畳み込みを導き出す工程、不連続画像における所定位置で画素を選択する工程、該選択された画素に関してライン・サンプルの方向づけを行う工程、選択された画素に対応する連続画像中の1点から方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定する工程、測定距離における累進的畳み込みを評価して重み付きカバーレージ値を生成する工程、重み付きカバーレージ値を画素と関連付けて不連続画像中の画素のアンチエイリアシングを行う工程とを備える。
【発明の詳細な説明】
【0001】
【発明の属する技術分野】本発明は一般に画像処理に関し、特に連続画像のサンプリング時に生じるエイリアシングの影響の除去を行うライン・サンプルによるアンチエイリアシング方法に関する。
【0002】
【従来の技術】画像作成用の多種多様のコンピュータ・アプリケーションが存在する。これらのアプリケーションにはゲーム、グラフィック・デザイン、アニメーション、シミュレーション、視覚化、モデリングなどが含まれる。これらのアプリケーションでは作成された画像は可能な限りリアルであるほうがよい。
【0003】コンピュータ・グラフィックスでは、作成画像は連続画像の不連続(個別)サンプルの規則的な配列として表される。この“不連続画像”はある一定の有限のレートでの連続画像のサンプリングの結果生じたものである。個々のサンプル・ポイントは画素と呼ばれる。画素がサンプリング・ポイントであって不連続画像における矩形領域ではないことを記憶しておくことには批判的である。
【0004】サンプリング・レートが有限であることに起因して、連続画像中に存在する高周波は不正確な低周波となってしまう(alias)ことがある。エッジのような連続画像中のある共通の特徴は、無限に高い周波数を含むので、どのような有限サンプリング・レートでも結果的にどうしてもエイリアシングが発生してしまう。コンピュータ生成画像では、エイリアシングは画像オブジェクトの階段状の輪郭(すなわちいわゆる“ジャギー(jaggy)”)として現れる。エイリアシングによる他の影響として、モアレ図形と細かな細部の分裂(break up)が生じる場合もある。
【0005】アンチエイリアシングを利用して不連続画像の外観が改善される。アンチエイリアシングは、ある周波数限定フィルタを用いる連続画像の畳み込み計算とサンプリングによって達成される。画素は連続画像のフィルタされたバージョンのサンプルである。従来技術において畳み込みのサンプルを計算するために使用される2つの一般的方法として、エリア・サンプリングとポイント・サンプリングが存在する。
【0006】エリア・サンプリングによるアンチエイリアシングエリア・サンプリングによるアンチ・エイリアシンでは、処理されたがまだ連続している形の連続画像を使用して、アンチエイリアシングフィルタ関数とこの連続画像の畳み込みとの正確な計算が行われる。この畳み込みはサンプル化され、不連続画像の画素を測定する間使用する値が生成される。一般に、フィルタ関数とは半径Rを有するガウスフィルタである。この半径によって“フットプリント(footprint)”すなわちフィルタの“サポート(support)”が定義される。
【0007】エリア・サンプリングで用いられる連続画像の処理された形は通常、各画素の周りに在るフィルタ・フットプリントの中で目に見える1セットのポリゴンである。不都合なことに、多くの場合連続画像は、互いに塞いだり交わることがある幾何学的オブジェクトを含む3次元場面の記述によって定義される。これらの塞ぎ(occlusion)と交わり(intersection)によって、連続画像を効率的に処理してエリア・サンプリングに適した形に変えることは困難になる。というのは複雑な形状は単純なオブジェクトの相互作用から結果として生じる場合もあるからである。
【0008】ポイント・サンプリングによるアンチエイリアシングポイント・サンプリングによるアンチエイリアシングでは、画素の近傍で複数のサンプル・ロケーションが用いられる。連続画像は画素位置に対応するポイントにおいて評価され、その結果得られる値は、フィルタ関数と連続画像との畳み込みを近似させる試みの中で何らかの重み付け関数に従って合成される。ポイント・サンプリングは、その実施の単純さと容易さのためにアンチエイリアシングに用いられる最も一般的な方法である。3次元場面のエリア・サンプリングに存在する塞ぎ問題はポイント・サンプリングによって単純化されるが正しい解が得られるまでの時間のかかる収束に難点がある。一般に、N個のポイント・サンプルには1/Nの精度で画素値の計算が必要となる。ポイント・サンプルの位置は互いに離れていて繋がりがないので、細かい細部についてはサンプリング時に全く無視することができる。したがって、これらの無視された細部が不連続画像に貢献することはあり得ない。
【0009】ポイント・サンプリング法とエリア・サンプリングとの組み合わせエリア・サンプリング法とポイント・サンプリング法とはレンダリング・システムにおいて組み合わされて用いられることが多い。エリア・サンプリングは、テクスチャ・マップのような2次元サンプル化画像に効率的に適用することができ、一方、ポイント・サンプリングは、ポリゴンのエッジとの交わりのアンチエイリアシングを行うために用いるのが一般的である。ポイント・サンプリングを用いて、ある画素のフィルタ・フットプリント内に在るポリゴンの重み付きカバーレージ値(WCV:weighted coverage value)が生成される。次いでこれらの値はその画素と関連付けられる。WCVとは、1つの画素のカラーに対するそのポリゴンのカラー貢献度の重み付けを行う画素における、アンチエイリアシング・フィルタとポリゴンの可視部分との畳み込みの結果を表す値である。エリア・サンプリング法を用いて、その画素と関連付けられたポリゴンのカラーが作成される。次いで、WCVとその画素と関連付けられたカラーとが組み合わされて、不連続画像の画素の最終カラーが作成される。
【0010】その他のアンチエイリアシング法Maxは、“アンチエイリアシング走査線データ”(IEEEコンピュータ・グラフィックス&アプリケーション10(1):18−30、1990年1月)の中で1つの混成的方法について記載している。彼の示す混成的方法は、スーパー・サンプリングを用いて1つの方向のアンチエイリアシングを行いながら、エリア・サンプリングを近似することによりもう一方の方向に連続してアンチエイリアシングを行うものである。連続方向にほぼ平行なエッジのアンチエイリアシングは、連続方向にほぼ垂直なエッジに対するアンチエイリアシングと比べると効率的なものではない。
【0011】
【発明が解決しようとする課題】以上のように、従来技術のエリア・サンプリングおよびポイント・サンプリングのアンチエイリアシング法には多数の欠点と問題点が存在し、従って不連続画像の生成中、メモリの大幅な増加や描画速度の低下を伴わない改善されたアンチエイリアシング法に対する要望があった。
【0012】本発明は、フィルタ関数を用いて、エッジを含む連続画像からサンプル化されたアンチエイリアシングされた不連続画像を生成するライン・サンプルによるアンチエイリアシング方法を提供することを目的とするものである。この方法によってライン・サンプルが定義される。上記フィルタ関数とライン・サンプルとから累進的畳み込みが導き出される。不連続画像の所定位置で画素が選択され、ライン・サンプルが選択された画素に関して方向づけが行われる。
【0013】選択された画素に対応する連続画像中の1点から上記方向づけられたライン・サンプルに沿ったエッジまでの距離が測定される。上記累進的畳み込みはこの測定距離で評価され、重み付きカバーレージ値が生成され、この重み付きカバーレージ値が画素と関連付けられて不連続画像中の画素のアンチエイリアシングが行われる。
【0014】
【課題を解決するための手段】上記の目的に鑑み、この発明は、フィルタ関数を用いて、1つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、ライン・サンプルを定義するステップと、前記フィルタ関数と前記ライン・サンプルから累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、前記選択された画素に対応する前記連続画像中の1点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、前記測定距離における累進的畳み込みを評価して重み付きカバーレージ値を生成するステップと、前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法にある。
【0015】また、前記エッジが可視であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0016】また、前記選択された画素が前記エッジからの所定の距離の範囲内に在ることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0017】また、前記所定の距離が前記ライン・サンプルの長さ以下であることを特徴とする請求項3に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0018】また、前記ライン・サンプルが直線であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0019】また、前記ライン・サンプルが前記画素のほぼ中心を通り、前記エッジにほぼ垂直であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0020】また、前記ライン・サンプルが少なくとも前記フィルタ関数のフットプリントの範囲にわたる有限の長さを有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0021】また、前記フィルタ関数がガウス関数であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0022】また、前記累進的畳み込みが様々な距離における前記フィルタ関数の累積積分であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0023】また、前記累進的畳み込みが連続関数によって定義されることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0024】また、前記累進的畳み込みの値が有限数の距離についてテーブルに格納されることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0025】また、前記連続画像が第1および第2のエッジを含み、前記選択された画素に対応する前記連続画像中の1点から前記第1および第2のエッジまでの、第1および第2の距離を測定するステップと、前記測定された第1および第2の距離における前記累進的畳み込みを評価して、第1および第2の重み付きカバーレージ値を生成するステップと、前記第1および第2の重み付きカバーレージ値の差を前記画素と関連付けて、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0026】また、前記連続画像中の前記エッジが第2のオブジェクトと相互に作用する第1のオブジェクトから結果として生じ、前記選択された画素が前記第1のオブジェクトの第1のデプス情報と、前記第2のオブジェクトの第2のデプス情報とを持ち、相互に作用する前記ライン・サンプルのセクションを測定するステップと、前記セクションの前記デプス情報に基づいてセクションを選択的に保持し、廃棄するステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0027】また、塞ぐことにより前記第1および第2のオブジェクトが相互に作用することを特徴とする請求項13に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0028】また、交わることにより前記第1および第2のオブジェクトが相互に作用することを特徴とする請求項13に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0029】また、第1のライン・サンプルと第2のライン・サンプルとを定義するステップと、前記フィルタ関数と前記第1のライン・サンプルとから第1の累進的畳み込みを導き出すステップと、前記フィルタ関数と前記第2のライン・サンプルとから第2の累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、前記選択された画素に関して前記第1および第2のライン・サンプルの方向付けを行うステップと、前記選択された画素に対応する前記連続画像中の1点から、前記方向づけられた第1と第2のライン・サンプルに沿う前記エッジまでの第1および第2の距離を測定するステップと、前記第1のライン・サンプルの前記第1の累進的畳み込みと、前記測定された第1および第2の距離における前記第2のライン・サンプルの前記第2の累進的畳み込みとを評価し、第1の重み付きカバーレージ値と第2の重み付きカバーレージ値とを生成するステップと、前記第1および第2のライン・サンプルの重み付けを行うステップと、前記第1および第2のライン・サンプルの前記重み付けに従って前記第1および第2の重み付きカバーレージ値をブレンドするステップと、前記ブレンドされた重み付きカバーレージ値を前記画素と関連付け、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0030】また、前記第1のライン・サンプルが前記第2のライン・サンプルに対して垂直であることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0031】また、前記エッジに関して前記第1および第2のライン・サンプルの方向に従って前記第1および第2のライン・サンプルが評価され、重み付けが行われることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0032】また、前記重み付けが前記エッジから導き出された正規化されたベクトルを用いることを特徴とする請求項18に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0033】また、前記第1および第2のライン・サンプルの長さが前記不連続画像の画素間の距離の2倍であり、さらに、前記エッジ距離の値が前記ライン・サンプルの端点において生成されることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0034】また、画素の列と行を選択するステップと、画素の前記列と行と整列した前記連続画像の全範囲にわたるラインを選択するステップと、前記連続画像の全範囲にわたる前記ラインについてセグメント情報を生成するステップと、前記連続画像の全範囲にわたる前記ラインについて可視セグメントを測定するステップと、画素の前記列と行中の画素を選択するステップと、前記画素における前記フィルタ関数のフットプリントの範囲内で前記可視セグメントから前記画素についてライン・サンプルを生成するステップと、を更に有することを特徴とするに請求項16に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0035】また、前記エッジが曲線であり、前記曲線に対してタンジェントを測定するステップと、前記ライン・サンプルを前記タンジェントに対して垂直に方向づけるステップと、を更に有することを特徴とするに請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0036】また、前記連続画像の低い分解能の画像を生成するステップと、前記低い分解能の画像に対してエッジ検出オペレータを適用して前記エッジを生成するステップと、前記エッジに対して垂直に前記ライン・サンプルを方向づけるステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0037】本発明の1つの局面では、アンチエイリアシングは可視エッジについてしか行われず、さらに該エッジから所定の距離内にある画素についてのみ検討がされる。例えば、上記所定距離をライン・サンプルの長さ以下の距離とする。
【0038】本発明の別の局面では、このライン・サンプルは、直線で、画素の中心を通りエッジに対してほぼ垂直である。
【0039】本発明のさらに別の局面では、フィルタ関数はガウス関数であり、累進的畳み込みは様々な距離のフィルタ関数の累積積分である。累進的畳み込みは連続関数によって定義することができる。あるいは、累進的畳み込みの値は有限数の距離用のテーブルに格納される。
【0040】本発明の別の局面では、複数のライン・サンプルが各画素について定義され、各ライン・サンプルの重み付きカバーレージ値が組み合わされて、画素と関連付けられた組み合わされた重み付きカバーレージ値が生成される。
【0041】
【発明の実施の形態】本発明はライン・サンプルを用いて、重み付きカバーレージ値(WCV)を生成する改善された方法を提供するものであり、このカバーレージ値を利用して不連続画像のアンチエイリアシングを行うことが可能となる。WCVとは、ある画素のカラーに対するそのポリゴンのカラー貢献度の重み付けを行う画素における、アンチエイリアシング・フィルタとポリゴンの可視部分の畳み込みの結果を示す値である。
【0042】本発明によるライン・サンプリングは、効率と精度に関して従来技術によるエリア・サンプリング法とポイント・サンプリング法との中間に位置するものである。本発明のライン・サンプリング法を用いて形状情報(すなわちエッジ、塞ぎおよび交わり)からWCVの計算を行うことができ、さらにシェード情報(すなわち従来技術におけるようなカラーとテクスチャ)のエリア・サンプリング法と本発明のライン・サンプリング法とを組み合わせることができる。このようにして、本発明による高品質のアンチエイリアシングされた画像の生成が可能となる。
【0043】ライン・サンプリングの根拠となる基本的な洞察は以下の特性によるものである。すなわち、エッジと、少なくとも、該エッジにほぼ垂直な方向を持つフィルタのフットプリントの範囲にわたるライン・サンプルとの交わりが与えられれば、有限フィルタと直線エッジの畳み込みを効率的にかつ正確に測定することが可能である。さらに、エリア・サンプルで行うよりもライン・サンプルで行う塞ぎと交わりの測定のほうがはるかに簡単である。このことは事実である。というのは、これらの相互作用(塞ぎと交わり)によって複雑さの少ない基本構造(primitive)が作成されるからである。さらに、塞ぎの問題は1回の計算によって1つのライン・サンプルの広い部分について解決することが可能となる。上記の特性によって、ライン・サンプリングに対する、ポイント・サンプリングより良好な収束と、エリア・サンプリングと同様の精度がしかも安い計算コストで得られる。
【0044】ライン・サンプルによる畳み込みの効率的計算には、所望のフィルタ関数から累進的畳み込み(PC:progressive convolution)を導き出す必要がある。この所望のフィルタ関数が半径方向に左右対称である場合には、1回のPCですべてのライン・サンプル方向について充分である。所望のフィルタ関数が半径方向に左右対称でない場合には、生じ得るライン・サンプル方向の各々について、あるいは、十分な数の別個の方向でPCを測定して、他の中間方向で補間が可能となるようにしなければならない。本発明によるPCの測定が図1と図2に示されている。
【0045】図1に図示のように、斜線で示される内部を持つグラフィック・オブジェクト104のエッジ101からの異なる距離(例えば、−1.5、−0.8、0.0、+0.8、+1.5)で画素100が配置されている。画素の中心を通るフィルタ関数(図1の(f)参照)のフットプリントは円102によって示される。フットプリントはフィルタ関数の“サポート”(すなわちフィルタ関数がノンゼロ値を有する領域)である。
【0046】図1の(f)のグラフ103はフィルタによって生成された値を表すガウスフィルタ関数の一例であり、画素からの距離(D)を示すx軸と、該関数の強度(i)を示すy軸とを有する。本発明では他のフィルタ関数も使用できることを理解されたい。
【0047】画素とエッジは相手からの異なる複数の距離で図示されている。直線分105は本発明によるライン・サンプルを表す。好ましくは、該ライン・サンプルは画素の中心を通る直線で、ライン・サンプルの方向がエッジ101に対して垂直になるように選択され、ライン・サンプル105の長さは少なくともフットプリント102の直径の範囲にわたることが望ましい。
【0048】ライン・サンプルは他の線形構成(例えば円、ベジエ曲線など)を持つものであってもよいと理解されたい。ライン・サンプルは他の位置、長さおよび方向を持つものであってもよいと理解されたい。ライン・サンプルの配置は、計算上好都合な場合には画素の中心から外れて画素の近くであってもよい。
【0049】図2はフィルタ関数103から導き出されたPC200を示す図である。オブジェクトの外側に在る画素の距離は負の数で、オブジェクトのエッジ上の画素の距離はゼロで、オブジェクト内部の画素の距離は正の数で示される。これらの距離はx軸201に沿って示される。PCの重み付きカバーレージ(WCV:weighted coverage value)の値はy軸202に沿って示される。WCVは0.0から1.0の範囲にある。例えば、画素がエッジ上に配置されている場合、PCのWCVは0.5となり、エッジ101によるフィルタ・フットプリント102のカバーレージの二分の1を示す。フィルタ・フットプリントが完全にオブジェクトの内部に配置されているとき、最大のカバーレージが存在し、フィルタ・フットプリントが完全にオブジェクトの外側にあるときカバーレージは存在しない。画素がエッジから離れて移動するにつれてPC200の値は0.5からゼロへ減少し、画素が反対方向に移動するにつれて0.5から1へ増加する。最大のカバーレージは図1fの曲線103の下の面積を表す。本質的に本発明による累進的畳み込みは、エッジからの様々な距離でのフィルタ関数の累積積分を表す。
【0050】エッジ101と一緒に畳み込まれたフィルタ103から導き出されるPC200を効率的に評価することができる。フィルタが単純な場合、PC200は必要な時に関数的に評価することができる。フィルタが複雑なとき、エッジからの様々な距離でサブセットのPC200の値を予め計算し、中間距離で補間を行うためにテーブルにこの値を格納することができる。表形式で、PCは距離によって索引化(indexed)され、中間値の補間を行うことが可能となる。図2のPC200ではすべての可能な距離、すなわち−∞から+∞までのWCVが示されているとはいえ、実際の利用時にはWCVは非常に狭い範囲の距離(すなわち−2.0から+2.0)にわたってしか変動しないと理解すべきである。この場合1単位は画素間の間隔に等しい。
【0051】フィルタが半径方向に非対称である場合、各ライン・サンプル方向についてPCを生成することができる。しかし、実際問題として、最も一般的に使用されているフィルタは単純な構造を持ち、半径方向に左右対称である。これによってテーブルの必要性がなくなりすべてのライン・サンプル方向について単一のPCで充分である。
【0052】図3の(a)〜(f)は、本発明によるライン・サンプルを用いてどのように効率的にかつ正確に、所望のフィルタについてあるPCとオブジェクトとの所望の畳み込みの測定を行うことができるかを示す図である。オブジェクト300はエッジa、b301〜302を持つ。ライン・サンプル303はエッジa、b301−302の間に配置される画素304の中心を通る。ライン・サンプル303は端点e1(305)とe2(306)を持つ。所望の畳み込みは画素304におけるオブジェクト300のWCVである。ライン・サンプル303はフィルタ・フットプリント309の範囲にわたる。図示のように、ライン・サンプル303は複数のエッジにほぼ垂直に方向づけられる。距離d1(307)とd2(308)は画素とライン・サンプル303に沿うエッジaとbの間の相対的距離をそれぞれ示す。
【0053】図3の(b)のグラフ310は、ライン・サンプル303とオブジェクト300の交わりのセグメント情報を示す。ライン・サンプルに沿ったエッジの交わりの相対位置によって、2つの距離d1とd2により境界が設けられるライン・サンプル上でセグメント320の測定が行われる。図3の(d)に図示のフィルタ・フットプリント309とオブジェクト300の内部との正確な畳み込みは、図3の(e)に図示のようなエッジbとフィルタの畳み込みと、図3の(f)に図示のようなエッジaとフィルタの畳み込みとの差と考えることができる。図3の(c)に図示のようにこの差はd2とd1で評価されるPC330の値の間の差331に等しい。この差は、まさに画素304におけるオブジェクト300のWCVである。
【0054】図3に図示の方法の3つ以上のエッジへの拡張は当業者には自明である。
【0055】いくつかのポリゴンが部分的に塞いだり互いに交わるとき、複数のポリゴンの塞ぎと交わりによって非常に複雑な形状の生成を行うことが可能となる。これは三角形のような単純なポリゴンについても当てはまる。従来技術によるエリア・サンプルに対するものではなく、ライン・サンプルに対するアンチエイリアシングの畳み込みを行うことを決めることによって、図4の(a)〜(c)に図示のような塞ぎの問題、ならびに、図5の(a)〜(c)に図示のような交わりの問題は著しく単純化される。
【0056】図4の(a)では、ポリゴンa(401)がポリゴンb(402)を部分的に塞いでいる。図4の(b)は、ポリゴンa、bに対応するセグメントのライン・サンプル404についてのサンプル・デプス情報(Z)403を図示するものである。ライン・サンプルがaとbの双方にオーバーラップする場合塞ぎが生じる。ライン・サンプル上のすべての点におけるデプス情報を比較すること、各点における最少のデプスを持つセグメントについての情報のみを保持することおよび各点における最大のデプスを持つセグメントについての情報を廃棄することにより上記塞ぎの問題を解決することができる。ライン・サンプルに沿って、セグメントのセクション全体について塞ぎを効率的に解決することができる。このような塞ぎによって、既存のセグメントが切りつめられたり、分割(split)される場合もある。図4の(c)はライン・サンプル404に沿ったaとbの塞ぎの結果を図示するものである。図4の(b)でのセクション405全体の塞ぎは、ラインセグメントの一部の選択的保持と廃棄により図4の(c)の残り部分406を残しながら解決されている。
【0057】図5の(a)は、互いに交わるポリゴンa(501)とb(502)とを図示するものである。図5の(b)は、ポリゴンaとbに対応するセグメントのライン・サンプル504に沿ってデプス情報(Z)503を示す図である。2つのポリゴンの交わりは、対応するセグメントに対するデプス情報中の対応する交点505を結果として生み出す。この交わりを配置し利用することにより、上述のようなデプス情報に基づく選択的保持と廃棄によりaとbの相互の塞ぎの問題を解決することができる。また以上のようにセグメントの交わりによって、既存のセグメントが切りつめたり分割される場合もある。この交わりと塞ぎの結果が図5の(c)に図示されている。
【0058】ライン・サンプリングによって、ポイント・サンプリングよりもさらに正確な、アンチエイリアシング・フィルタ畳み込みの測定が行われる。例えば、N個のポイント・サンプルによって、ほぼ1/Nに比例する精度が提供される。ライン・サンプルとエッジが互いにほぼ垂直に方向づけられたとき、エッジに対して垂直に方向づけられたライン・サンプルによって、完全な精度で、また、妥当な正確さでそのエッジについての畳み込み計算が行われる。
【0059】ライン・サンプルとエッジが互いに平行に方向づけられている場合、ライン・サンプルは図6の(a)と(b)に図示のように単一ポイント・サンプルとして機能する。図6の(a)では、ライン・サンプル600は画素603の中心を通り、オブジェクト602のエッジ601に平行に方向づけられる。ここで、ライン・サンプルとオブジェクトの間にはカバーレージが存在しない(WCV=0)。エッジの位置のわずかな変化(すなわち、オブジェクトがライン・サンプルをカバーするとすぐに生じる変化)によって、カバーレージのない状態から最大のカバーレージ(WCV=1)への図6の(b)に示すような外観の急激な変化が生じる。
【0060】上記の理由のために、異なる方向を持つ複数のライン・サンプルを取ってその結果として生じるWCVを組み合わせるか、連続画像中のエッジ方向に依存するライン・サンプルの方向を選択するかのいずれかを行うことが有利である。
【0061】複数のラインを用いることは個々のライン・サンプルの貢献度に重み付けを行う方法を必要とする。1つの方法によって等しく貢献度の重み付けが行われ、ライン・サンプルから得られた値が平均化されて最終結果が生成される。以下に説明するように、下にある連続画像のエッジのサンプリングを行うためにライン・サンプルがどのように良好に方向づけられているかを示す何らかの測定値に基づき、ライン・サンプルの重み付けを行うことにより畳み込みのさらに良好な近似値が生成される。
【0062】互いに垂直な2つのライン・サンプルを用いていずれの方向のエッジについても十分な精度で畳み込みの測定を行うことが可能である。その場合、いくつかの基準に基づいて各サンプルの貢献度についての重み付けを測定することができる。各エッジの相対方向とそのエッジと交わるライン・サンプルについて考慮することができる。各ライン・サンプルと交わるエッジの数を係数とすることができる。ライン・サンプルの可視セグメントの分散あるいは他の統計的測定値を利用することが可能となる。
【0063】図7の(a)で、画素709についての2つのライン・サンプル701と702は互いに垂直に設けられる。ライン・サンプル701はオブジェクト700と部分的に交わり、ライン・サンプル702は完全にオブジェクトの外側に存在する。オブジェクト700に対応する、ライン・サンプル701と702についてのセグメント情報がそれぞれグラフ704と705に示されている。図7の(b)では、オブジェクト700はライン・サンプル701と702に関連して移動している。ライン・サンプル702は完全にオブジェクト700の内部に存在し、ライン・サンプル701の大部分はオブジェクト700と交わっている。
【0064】それぞれのセグメント情報がグラフ706と707に示されている。エッジに対するライン・サンプルの垂直方向による、エッジ708の正確なアンチエイリアシングがライン・サンプル701によって行われる。ライン・サンプル701と702によって、画素709におけるオブジェクト700の2つのWCVの計算が行われる。ライン・サンプル701によってさらに正確にエッジ708のアンチエイリアシングが行われるので、ライン・サンプル701から計算されたWCVのほうが、ライン・サンプル702によって計算されたWCVより、画素709におけるオブジェクト700の2つの組み合わされたWCVに対する貢献度が大きくなる。
【0065】図8に図示のように、ライン・サンプル803に沿うサンプルの重み付けに影響を与えるエッジへの考慮は“可視”エッジのみに限定するのが有効である。可視エッジ801は、(同じカラーからなる)別のポリゴンに(例えば該カラーの点で)一致しないポリゴンのエッジによって、あるいは塞ぎや交わりによって生成されるエッジである。同じカラーからなる2つのポリゴンが合わさった場合に生じるエッジ802は、作成された画像の中で目に見える可能性が少ない。したがって、エッジと交わるライン・サンプルの重み付けに該エッジが影響を与えないようにするために、このエッジ802は“非可視”のものとして処理したほうがよい。例えば、複数の隣接するポリゴンからなるオブジェクトは、結果に影響を与えるポリゴン間の内部エッジを持たないシルエット・エッジの方向に従ってアンチエイリアシングが行われる、オブジェクトのシルエット形成エッジを備えているほうがよい。
【0066】図9は、別のポリゴンb902を部分的に塞ぐポリゴンa901を示す図である。ポリゴンa901のエッジ903はポリゴンb902のエッジに一致することはない。エッジ903は不連続画像の中で可視であり、アンチエイリアシング計算に影響を与えるはずである。したがって、エッジ903を可視エッジとして処理し、ライン・サンプル904を用いてサンプルの重み付けの計算を行うほうがよい。
【0067】図10の(a)は、オブジェクト1000のエッジ1003の近辺で2つの垂直な軸整列しているライン・サンプル1001と1002に対してどのように重み付けの測定を行うことができるかを示す図である。この図では、エッジ1003の方向はライン・サンプル1001−1002のいずれにも垂直ではない。エッジ1003に沿って進むベクトル計算を行うことができる。図10の(b)は、水平成分Vx1005と垂直成分Vy1006とを持つ、エッジ1003についてのエッジ・ベクトル1004を図示するものである。
【0068】この方法によって、ライン・サンプルのいずれかと交わる各可視エッジの正規化されたベクトル(Vnx,Vny)がまず測定される。次いで、成分(Vnx,Vny)を持つ正規化されたエッジ・ベクトルについて、垂直サンプルの総重み付けにVnx2を加算し、水平サンプルの総重み付けにVny2を加算する。成分の値の二乗を用いて任意のエッジの貢献度の総和が1に等しく保たれる。関連するエッジの貢献度のすべてに重み付けが行われた後、垂直および水平のライン・サンプルの相対的重み付けを測定することができ、これらの相対的重み付けを用いて2つのライン・サンプルのWCVのブレンディング(blending)が行われる。このブレンディングは1次ブレンディング関数、三次ブレンディング関数あるいはさらに大きな重み付けを行ったWCVの選択のような任意の適切なブレンディング関数を利用することができる。
【0069】図11の(a)に図示のように、従来型のラスタ化法を用いて2つの垂直な軸整列ライン・サンプルについてのライン・サンプル評価のスピード・アップを図ることが可能である。図11の(a)では、ライン・サンプル1102と1103を持つ画素グリッド1100の画素1101においてサンプリングを行うことが望ましい。一般に選択される、画素間の距離に等しい半径を持つアンチエイリアシング・フィルタを使用するとき、ポイント・サンプリングに現在利用される高速ラスタ化法を用いて、ちょうど画素グリッド位置上に在るライン・サンプルの端点1109におけるエッジ距離の値を生成することができる。1つのライン・サンプルの端点と1つのエッジのエッジ距離の値は、ライン・サンプルの端点とそのエッジ間の最短距離として定義される。
【0070】図11の(b)に図示のように、ライン・サンプル1102と1103を表すために“黒丸”の画素1104が用いられ“白丸”の画素1105は使用されない。Pineda算術を用いてライン・サンプルの端点における画像中のポリゴンについてエッジ距離の値を効率的に生成することができる。Pineda"ポリゴン・ラスタ化のための並列アルゴリズム”(SIGGRAPHの会報、コンピュータ・グラフィックス、Vol.22. NO.4、pp.17−20、1988)を参照されたい。これらのエッジ距離の値は直線的に変動するので、ライン・サンプルの端点におけるエッジ距離の値のみが与えられれば、初等幾何学的方法あるいは代数的方法(例えば類似三角形)を用いて、ライン・サンプルのセグメントを効率的に生成することができる。セグメントは、エッジ距離の値がすべて正の場合ライン・サンプルの一部となる。
【0071】従来の走査線ラスタ化法を用いて、不連続画像中の画素の列と行全体についてライン・サンプルの生成を行うことができる。これらの手法を用いて連続画像全体にわたるライン上のすべての可視セグメントを生成することができる。次いで、画素のフィルタ・フットプリント内の可視セグメント部分を考慮することにより、連続画像全体にわたるラインと同じ方向で、1つの画素についてライン・サンプルが生成される。
【0072】下にある連続画像中のエッジに関する情報が分かっている場合には、正確な方向を持つ1画素当たりの単一ライン・サンプルで、その画像のサンプリングを行う画素のWCVの適切な生成を行うのに十分である。その連続画像自体からエッジ情報を得ることができる。例えば図12に図示のように、多くのオブジェクト1200(フォントなど)を境界曲線1201によって指定することができる。曲線1203のタンジェント(正接:tangent)情報1202はこの曲線についての記述から計算することができる。ライン・サンプル1205はタンジェント1202の方向に対して垂直に方向づけられている。
【0073】図13に示される代替方法では、連続画像1301から低い分解能のポイント・サンプル化画像1302が生成される。低い分解能の画像1302はエッジ情報1303を生成するエッジ検出オペレータで処理される。検出されたエッジ情報1303は適切なライン・サンプル1304の方向を示す。次いで適切に方向づけられたライン・サンプルがその連続画像に適用されてWCVが生成され、このWCVはアンチエイリアシングされた不連続画像1305を生成するために用いられる。
【0074】以上、いくつかの異なる応用例の推奨する実施の形態とその様々な改変例という点から本発明について説明してきたが、図面による上述の説明に基づいて、特に本発明の柔軟性と適応性を考慮すると本発明の範囲内で他の改変を行うことが可能であることは当業者には明白であろう。本発明の実際の範囲は以下の請求項に記載されている。
【0075】
【発明の効果】以上のようにこの発明によれば、フィルタ関数を用いて、1つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、ライン・サンプルを定義するステップと、前記フィルタ関数と前記ライン・サンプルから累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、前記選択された画素に対応する前記連続画像中の1点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、前記測定距離における累進的畳み込みを評価して重み付きカバーレージ値を生成するステップと、前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法としたので、不連続画像の生成中、メモリの大幅な増加や描画速度の低下を伴わない改善されたアンチエイリアシング法が提供できる。
【図面の簡単な説明】
【図1】 この発明によるライン・サンプルによるアンチエイリアシング方法におけるグラフィックオブジェクトのエッジまでの様々な距離における画素の中心を通るライン・サンプルのフィルタ・フットプリントおよびフィルタ関数を示す図である。
【図2】 この発明における累進的畳み込みを示す図である。
【図3】 この発明における2つのエッジと交わるライン・サンプル、セグメント情報、累進的畳み込みの2つの評価値の差、2つのカバーレージ評価値間の差を示す図である。
【図4】 オブジェクトを塞ぐライン・サンプリングを示す図である。
【図5】 この発明におけるオブジェクトと交わるライン・サンプリングを示す図である。
【図6】 エッジに対して平行方向のライン・サンプルを示す図である。
【図7】 2本の直交ライン・サンプルを使用するライン・サンプリングを示す図である。
【図8】 ライン・サンプルされた隣接オブジェクトの可視および非可視エッジを示す図である。
【図9】 ライン・サンプルされた相互に塞ぎあうオブジェクトの可視および非可視エッジを示す図である。
【図10】 正規化されたエッジに従うライン・サンプリングを行うための重み付け用複数ライン・サンプルを示す図である。
【図11】 画素グリッド位置におけるライン・サンプリング用データ生成を示す図である。
【図12】 タンジェント方向に垂直な方向を持つ境界曲線のライン・サンプリングを示す図である。
【図13】 低い分解能の画像とエッジ検出を用いるライン・サンプリングを示す図である。
【符号の説明】
100,304、603,709,1101,1104,1105 画素、101,601,708,903,1003 エッジ、102 フットプリント、103 フィルタ関数、104 グラフィック・オブジェクト、105,303,404,504、600,701,702,803,904,1001,1002,1102,1103,1205,1304 ライン・サンプル、200,330 累進的畳み込み(PC)、300,602,700,1000,1200オブジェクト、301 エッジa、302 エッジb、309 フィルタ・フットプリント、320 セグメント、401,501,901 ポリゴンa、402、502,902 ポリゴンb、403,503 サンプル・デプス情報(Z)。
【0001】
【発明の属する技術分野】本発明は一般に画像処理に関し、特に連続画像のサンプリング時に生じるエイリアシングの影響の除去を行うライン・サンプルによるアンチエイリアシング方法に関する。
【0002】
【従来の技術】画像作成用の多種多様のコンピュータ・アプリケーションが存在する。これらのアプリケーションにはゲーム、グラフィック・デザイン、アニメーション、シミュレーション、視覚化、モデリングなどが含まれる。これらのアプリケーションでは作成された画像は可能な限りリアルであるほうがよい。
【0003】コンピュータ・グラフィックスでは、作成画像は連続画像の不連続(個別)サンプルの規則的な配列として表される。この“不連続画像”はある一定の有限のレートでの連続画像のサンプリングの結果生じたものである。個々のサンプル・ポイントは画素と呼ばれる。画素がサンプリング・ポイントであって不連続画像における矩形領域ではないことを記憶しておくことには批判的である。
【0004】サンプリング・レートが有限であることに起因して、連続画像中に存在する高周波は不正確な低周波となってしまう(alias)ことがある。エッジのような連続画像中のある共通の特徴は、無限に高い周波数を含むので、どのような有限サンプリング・レートでも結果的にどうしてもエイリアシングが発生してしまう。コンピュータ生成画像では、エイリアシングは画像オブジェクトの階段状の輪郭(すなわちいわゆる“ジャギー(jaggy)”)として現れる。エイリアシングによる他の影響として、モアレ図形と細かな細部の分裂(break up)が生じる場合もある。
【0005】アンチエイリアシングを利用して不連続画像の外観が改善される。アンチエイリアシングは、ある周波数限定フィルタを用いる連続画像の畳み込み計算とサンプリングによって達成される。画素は連続画像のフィルタされたバージョンのサンプルである。従来技術において畳み込みのサンプルを計算するために使用される2つの一般的方法として、エリア・サンプリングとポイント・サンプリングが存在する。
【0006】エリア・サンプリングによるアンチエイリアシングエリア・サンプリングによるアンチ・エイリアシンでは、処理されたがまだ連続している形の連続画像を使用して、アンチエイリアシングフィルタ関数とこの連続画像の畳み込みとの正確な計算が行われる。この畳み込みはサンプル化され、不連続画像の画素を測定する間使用する値が生成される。一般に、フィルタ関数とは半径Rを有するガウスフィルタである。この半径によって“フットプリント(footprint)”すなわちフィルタの“サポート(support)”が定義される。
【0007】エリア・サンプリングで用いられる連続画像の処理された形は通常、各画素の周りに在るフィルタ・フットプリントの中で目に見える1セットのポリゴンである。不都合なことに、多くの場合連続画像は、互いに塞いだり交わることがある幾何学的オブジェクトを含む3次元場面の記述によって定義される。これらの塞ぎ(occlusion)と交わり(intersection)によって、連続画像を効率的に処理してエリア・サンプリングに適した形に変えることは困難になる。というのは複雑な形状は単純なオブジェクトの相互作用から結果として生じる場合もあるからである。
【0008】ポイント・サンプリングによるアンチエイリアシングポイント・サンプリングによるアンチエイリアシングでは、画素の近傍で複数のサンプル・ロケーションが用いられる。連続画像は画素位置に対応するポイントにおいて評価され、その結果得られる値は、フィルタ関数と連続画像との畳み込みを近似させる試みの中で何らかの重み付け関数に従って合成される。ポイント・サンプリングは、その実施の単純さと容易さのためにアンチエイリアシングに用いられる最も一般的な方法である。3次元場面のエリア・サンプリングに存在する塞ぎ問題はポイント・サンプリングによって単純化されるが正しい解が得られるまでの時間のかかる収束に難点がある。一般に、N個のポイント・サンプルには1/Nの精度で画素値の計算が必要となる。ポイント・サンプルの位置は互いに離れていて繋がりがないので、細かい細部についてはサンプリング時に全く無視することができる。したがって、これらの無視された細部が不連続画像に貢献することはあり得ない。
【0009】ポイント・サンプリング法とエリア・サンプリングとの組み合わせエリア・サンプリング法とポイント・サンプリング法とはレンダリング・システムにおいて組み合わされて用いられることが多い。エリア・サンプリングは、テクスチャ・マップのような2次元サンプル化画像に効率的に適用することができ、一方、ポイント・サンプリングは、ポリゴンのエッジとの交わりのアンチエイリアシングを行うために用いるのが一般的である。ポイント・サンプリングを用いて、ある画素のフィルタ・フットプリント内に在るポリゴンの重み付きカバーレージ値(WCV:weighted coverage value)が生成される。次いでこれらの値はその画素と関連付けられる。WCVとは、1つの画素のカラーに対するそのポリゴンのカラー貢献度の重み付けを行う画素における、アンチエイリアシング・フィルタとポリゴンの可視部分との畳み込みの結果を表す値である。エリア・サンプリング法を用いて、その画素と関連付けられたポリゴンのカラーが作成される。次いで、WCVとその画素と関連付けられたカラーとが組み合わされて、不連続画像の画素の最終カラーが作成される。
【0010】その他のアンチエイリアシング法Maxは、“アンチエイリアシング走査線データ”(IEEEコンピュータ・グラフィックス&アプリケーション10(1):18−30、1990年1月)の中で1つの混成的方法について記載している。彼の示す混成的方法は、スーパー・サンプリングを用いて1つの方向のアンチエイリアシングを行いながら、エリア・サンプリングを近似することによりもう一方の方向に連続してアンチエイリアシングを行うものである。連続方向にほぼ平行なエッジのアンチエイリアシングは、連続方向にほぼ垂直なエッジに対するアンチエイリアシングと比べると効率的なものではない。
【0011】
【発明が解決しようとする課題】以上のように、従来技術のエリア・サンプリングおよびポイント・サンプリングのアンチエイリアシング法には多数の欠点と問題点が存在し、従って不連続画像の生成中、メモリの大幅な増加や描画速度の低下を伴わない改善されたアンチエイリアシング法に対する要望があった。
【0012】本発明は、フィルタ関数を用いて、エッジを含む連続画像からサンプル化されたアンチエイリアシングされた不連続画像を生成するライン・サンプルによるアンチエイリアシング方法を提供することを目的とするものである。この方法によってライン・サンプルが定義される。上記フィルタ関数とライン・サンプルとから累進的畳み込みが導き出される。不連続画像の所定位置で画素が選択され、ライン・サンプルが選択された画素に関して方向づけが行われる。
【0013】選択された画素に対応する連続画像中の1点から上記方向づけられたライン・サンプルに沿ったエッジまでの距離が測定される。上記累進的畳み込みはこの測定距離で評価され、重み付きカバーレージ値が生成され、この重み付きカバーレージ値が画素と関連付けられて不連続画像中の画素のアンチエイリアシングが行われる。
【0014】
【課題を解決するための手段】上記の目的に鑑み、この発明は、フィルタ関数を用いて、1つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、ライン・サンプルを定義するステップと、前記フィルタ関数と前記ライン・サンプルから累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、前記選択された画素に対応する前記連続画像中の1点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、前記測定距離における累進的畳み込みを評価して重み付きカバーレージ値を生成するステップと、前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法にある。
【0015】また、前記エッジが可視であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0016】また、前記選択された画素が前記エッジからの所定の距離の範囲内に在ることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0017】また、前記所定の距離が前記ライン・サンプルの長さ以下であることを特徴とする請求項3に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0018】また、前記ライン・サンプルが直線であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0019】また、前記ライン・サンプルが前記画素のほぼ中心を通り、前記エッジにほぼ垂直であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0020】また、前記ライン・サンプルが少なくとも前記フィルタ関数のフットプリントの範囲にわたる有限の長さを有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0021】また、前記フィルタ関数がガウス関数であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0022】また、前記累進的畳み込みが様々な距離における前記フィルタ関数の累積積分であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0023】また、前記累進的畳み込みが連続関数によって定義されることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0024】また、前記累進的畳み込みの値が有限数の距離についてテーブルに格納されることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0025】また、前記連続画像が第1および第2のエッジを含み、前記選択された画素に対応する前記連続画像中の1点から前記第1および第2のエッジまでの、第1および第2の距離を測定するステップと、前記測定された第1および第2の距離における前記累進的畳み込みを評価して、第1および第2の重み付きカバーレージ値を生成するステップと、前記第1および第2の重み付きカバーレージ値の差を前記画素と関連付けて、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0026】また、前記連続画像中の前記エッジが第2のオブジェクトと相互に作用する第1のオブジェクトから結果として生じ、前記選択された画素が前記第1のオブジェクトの第1のデプス情報と、前記第2のオブジェクトの第2のデプス情報とを持ち、相互に作用する前記ライン・サンプルのセクションを測定するステップと、前記セクションの前記デプス情報に基づいてセクションを選択的に保持し、廃棄するステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0027】また、塞ぐことにより前記第1および第2のオブジェクトが相互に作用することを特徴とする請求項13に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0028】また、交わることにより前記第1および第2のオブジェクトが相互に作用することを特徴とする請求項13に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0029】また、第1のライン・サンプルと第2のライン・サンプルとを定義するステップと、前記フィルタ関数と前記第1のライン・サンプルとから第1の累進的畳み込みを導き出すステップと、前記フィルタ関数と前記第2のライン・サンプルとから第2の累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、前記選択された画素に関して前記第1および第2のライン・サンプルの方向付けを行うステップと、前記選択された画素に対応する前記連続画像中の1点から、前記方向づけられた第1と第2のライン・サンプルに沿う前記エッジまでの第1および第2の距離を測定するステップと、前記第1のライン・サンプルの前記第1の累進的畳み込みと、前記測定された第1および第2の距離における前記第2のライン・サンプルの前記第2の累進的畳み込みとを評価し、第1の重み付きカバーレージ値と第2の重み付きカバーレージ値とを生成するステップと、前記第1および第2のライン・サンプルの重み付けを行うステップと、前記第1および第2のライン・サンプルの前記重み付けに従って前記第1および第2の重み付きカバーレージ値をブレンドするステップと、前記ブレンドされた重み付きカバーレージ値を前記画素と関連付け、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0030】また、前記第1のライン・サンプルが前記第2のライン・サンプルに対して垂直であることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0031】また、前記エッジに関して前記第1および第2のライン・サンプルの方向に従って前記第1および第2のライン・サンプルが評価され、重み付けが行われることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0032】また、前記重み付けが前記エッジから導き出された正規化されたベクトルを用いることを特徴とする請求項18に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0033】また、前記第1および第2のライン・サンプルの長さが前記不連続画像の画素間の距離の2倍であり、さらに、前記エッジ距離の値が前記ライン・サンプルの端点において生成されることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0034】また、画素の列と行を選択するステップと、画素の前記列と行と整列した前記連続画像の全範囲にわたるラインを選択するステップと、前記連続画像の全範囲にわたる前記ラインについてセグメント情報を生成するステップと、前記連続画像の全範囲にわたる前記ラインについて可視セグメントを測定するステップと、画素の前記列と行中の画素を選択するステップと、前記画素における前記フィルタ関数のフットプリントの範囲内で前記可視セグメントから前記画素についてライン・サンプルを生成するステップと、を更に有することを特徴とするに請求項16に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0035】また、前記エッジが曲線であり、前記曲線に対してタンジェントを測定するステップと、前記ライン・サンプルを前記タンジェントに対して垂直に方向づけるステップと、を更に有することを特徴とするに請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0036】また、前記連続画像の低い分解能の画像を生成するステップと、前記低い分解能の画像に対してエッジ検出オペレータを適用して前記エッジを生成するステップと、前記エッジに対して垂直に前記ライン・サンプルを方向づけるステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法にある。
【0037】本発明の1つの局面では、アンチエイリアシングは可視エッジについてしか行われず、さらに該エッジから所定の距離内にある画素についてのみ検討がされる。例えば、上記所定距離をライン・サンプルの長さ以下の距離とする。
【0038】本発明の別の局面では、このライン・サンプルは、直線で、画素の中心を通りエッジに対してほぼ垂直である。
【0039】本発明のさらに別の局面では、フィルタ関数はガウス関数であり、累進的畳み込みは様々な距離のフィルタ関数の累積積分である。累進的畳み込みは連続関数によって定義することができる。あるいは、累進的畳み込みの値は有限数の距離用のテーブルに格納される。
【0040】本発明の別の局面では、複数のライン・サンプルが各画素について定義され、各ライン・サンプルの重み付きカバーレージ値が組み合わされて、画素と関連付けられた組み合わされた重み付きカバーレージ値が生成される。
【0041】
【発明の実施の形態】本発明はライン・サンプルを用いて、重み付きカバーレージ値(WCV)を生成する改善された方法を提供するものであり、このカバーレージ値を利用して不連続画像のアンチエイリアシングを行うことが可能となる。WCVとは、ある画素のカラーに対するそのポリゴンのカラー貢献度の重み付けを行う画素における、アンチエイリアシング・フィルタとポリゴンの可視部分の畳み込みの結果を示す値である。
【0042】本発明によるライン・サンプリングは、効率と精度に関して従来技術によるエリア・サンプリング法とポイント・サンプリング法との中間に位置するものである。本発明のライン・サンプリング法を用いて形状情報(すなわちエッジ、塞ぎおよび交わり)からWCVの計算を行うことができ、さらにシェード情報(すなわち従来技術におけるようなカラーとテクスチャ)のエリア・サンプリング法と本発明のライン・サンプリング法とを組み合わせることができる。このようにして、本発明による高品質のアンチエイリアシングされた画像の生成が可能となる。
【0043】ライン・サンプリングの根拠となる基本的な洞察は以下の特性によるものである。すなわち、エッジと、少なくとも、該エッジにほぼ垂直な方向を持つフィルタのフットプリントの範囲にわたるライン・サンプルとの交わりが与えられれば、有限フィルタと直線エッジの畳み込みを効率的にかつ正確に測定することが可能である。さらに、エリア・サンプルで行うよりもライン・サンプルで行う塞ぎと交わりの測定のほうがはるかに簡単である。このことは事実である。というのは、これらの相互作用(塞ぎと交わり)によって複雑さの少ない基本構造(primitive)が作成されるからである。さらに、塞ぎの問題は1回の計算によって1つのライン・サンプルの広い部分について解決することが可能となる。上記の特性によって、ライン・サンプリングに対する、ポイント・サンプリングより良好な収束と、エリア・サンプリングと同様の精度がしかも安い計算コストで得られる。
【0044】ライン・サンプルによる畳み込みの効率的計算には、所望のフィルタ関数から累進的畳み込み(PC:progressive convolution)を導き出す必要がある。この所望のフィルタ関数が半径方向に左右対称である場合には、1回のPCですべてのライン・サンプル方向について充分である。所望のフィルタ関数が半径方向に左右対称でない場合には、生じ得るライン・サンプル方向の各々について、あるいは、十分な数の別個の方向でPCを測定して、他の中間方向で補間が可能となるようにしなければならない。本発明によるPCの測定が図1と図2に示されている。
【0045】図1に図示のように、斜線で示される内部を持つグラフィック・オブジェクト104のエッジ101からの異なる距離(例えば、−1.5、−0.8、0.0、+0.8、+1.5)で画素100が配置されている。画素の中心を通るフィルタ関数(図1の(f)参照)のフットプリントは円102によって示される。フットプリントはフィルタ関数の“サポート”(すなわちフィルタ関数がノンゼロ値を有する領域)である。
【0046】図1の(f)のグラフ103はフィルタによって生成された値を表すガウスフィルタ関数の一例であり、画素からの距離(D)を示すx軸と、該関数の強度(i)を示すy軸とを有する。本発明では他のフィルタ関数も使用できることを理解されたい。
【0047】画素とエッジは相手からの異なる複数の距離で図示されている。直線分105は本発明によるライン・サンプルを表す。好ましくは、該ライン・サンプルは画素の中心を通る直線で、ライン・サンプルの方向がエッジ101に対して垂直になるように選択され、ライン・サンプル105の長さは少なくともフットプリント102の直径の範囲にわたることが望ましい。
【0048】ライン・サンプルは他の線形構成(例えば円、ベジエ曲線など)を持つものであってもよいと理解されたい。ライン・サンプルは他の位置、長さおよび方向を持つものであってもよいと理解されたい。ライン・サンプルの配置は、計算上好都合な場合には画素の中心から外れて画素の近くであってもよい。
【0049】図2はフィルタ関数103から導き出されたPC200を示す図である。オブジェクトの外側に在る画素の距離は負の数で、オブジェクトのエッジ上の画素の距離はゼロで、オブジェクト内部の画素の距離は正の数で示される。これらの距離はx軸201に沿って示される。PCの重み付きカバーレージ(WCV:weighted coverage value)の値はy軸202に沿って示される。WCVは0.0から1.0の範囲にある。例えば、画素がエッジ上に配置されている場合、PCのWCVは0.5となり、エッジ101によるフィルタ・フットプリント102のカバーレージの二分の1を示す。フィルタ・フットプリントが完全にオブジェクトの内部に配置されているとき、最大のカバーレージが存在し、フィルタ・フットプリントが完全にオブジェクトの外側にあるときカバーレージは存在しない。画素がエッジから離れて移動するにつれてPC200の値は0.5からゼロへ減少し、画素が反対方向に移動するにつれて0.5から1へ増加する。最大のカバーレージは図1fの曲線103の下の面積を表す。本質的に本発明による累進的畳み込みは、エッジからの様々な距離でのフィルタ関数の累積積分を表す。
【0050】エッジ101と一緒に畳み込まれたフィルタ103から導き出されるPC200を効率的に評価することができる。フィルタが単純な場合、PC200は必要な時に関数的に評価することができる。フィルタが複雑なとき、エッジからの様々な距離でサブセットのPC200の値を予め計算し、中間距離で補間を行うためにテーブルにこの値を格納することができる。表形式で、PCは距離によって索引化(indexed)され、中間値の補間を行うことが可能となる。図2のPC200ではすべての可能な距離、すなわち−∞から+∞までのWCVが示されているとはいえ、実際の利用時にはWCVは非常に狭い範囲の距離(すなわち−2.0から+2.0)にわたってしか変動しないと理解すべきである。この場合1単位は画素間の間隔に等しい。
【0051】フィルタが半径方向に非対称である場合、各ライン・サンプル方向についてPCを生成することができる。しかし、実際問題として、最も一般的に使用されているフィルタは単純な構造を持ち、半径方向に左右対称である。これによってテーブルの必要性がなくなりすべてのライン・サンプル方向について単一のPCで充分である。
【0052】図3の(a)〜(f)は、本発明によるライン・サンプルを用いてどのように効率的にかつ正確に、所望のフィルタについてあるPCとオブジェクトとの所望の畳み込みの測定を行うことができるかを示す図である。オブジェクト300はエッジa、b301〜302を持つ。ライン・サンプル303はエッジa、b301−302の間に配置される画素304の中心を通る。ライン・サンプル303は端点e1(305)とe2(306)を持つ。所望の畳み込みは画素304におけるオブジェクト300のWCVである。ライン・サンプル303はフィルタ・フットプリント309の範囲にわたる。図示のように、ライン・サンプル303は複数のエッジにほぼ垂直に方向づけられる。距離d1(307)とd2(308)は画素とライン・サンプル303に沿うエッジaとbの間の相対的距離をそれぞれ示す。
【0053】図3の(b)のグラフ310は、ライン・サンプル303とオブジェクト300の交わりのセグメント情報を示す。ライン・サンプルに沿ったエッジの交わりの相対位置によって、2つの距離d1とd2により境界が設けられるライン・サンプル上でセグメント320の測定が行われる。図3の(d)に図示のフィルタ・フットプリント309とオブジェクト300の内部との正確な畳み込みは、図3の(e)に図示のようなエッジbとフィルタの畳み込みと、図3の(f)に図示のようなエッジaとフィルタの畳み込みとの差と考えることができる。図3の(c)に図示のようにこの差はd2とd1で評価されるPC330の値の間の差331に等しい。この差は、まさに画素304におけるオブジェクト300のWCVである。
【0054】図3に図示の方法の3つ以上のエッジへの拡張は当業者には自明である。
【0055】いくつかのポリゴンが部分的に塞いだり互いに交わるとき、複数のポリゴンの塞ぎと交わりによって非常に複雑な形状の生成を行うことが可能となる。これは三角形のような単純なポリゴンについても当てはまる。従来技術によるエリア・サンプルに対するものではなく、ライン・サンプルに対するアンチエイリアシングの畳み込みを行うことを決めることによって、図4の(a)〜(c)に図示のような塞ぎの問題、ならびに、図5の(a)〜(c)に図示のような交わりの問題は著しく単純化される。
【0056】図4の(a)では、ポリゴンa(401)がポリゴンb(402)を部分的に塞いでいる。図4の(b)は、ポリゴンa、bに対応するセグメントのライン・サンプル404についてのサンプル・デプス情報(Z)403を図示するものである。ライン・サンプルがaとbの双方にオーバーラップする場合塞ぎが生じる。ライン・サンプル上のすべての点におけるデプス情報を比較すること、各点における最少のデプスを持つセグメントについての情報のみを保持することおよび各点における最大のデプスを持つセグメントについての情報を廃棄することにより上記塞ぎの問題を解決することができる。ライン・サンプルに沿って、セグメントのセクション全体について塞ぎを効率的に解決することができる。このような塞ぎによって、既存のセグメントが切りつめられたり、分割(split)される場合もある。図4の(c)はライン・サンプル404に沿ったaとbの塞ぎの結果を図示するものである。図4の(b)でのセクション405全体の塞ぎは、ラインセグメントの一部の選択的保持と廃棄により図4の(c)の残り部分406を残しながら解決されている。
【0057】図5の(a)は、互いに交わるポリゴンa(501)とb(502)とを図示するものである。図5の(b)は、ポリゴンaとbに対応するセグメントのライン・サンプル504に沿ってデプス情報(Z)503を示す図である。2つのポリゴンの交わりは、対応するセグメントに対するデプス情報中の対応する交点505を結果として生み出す。この交わりを配置し利用することにより、上述のようなデプス情報に基づく選択的保持と廃棄によりaとbの相互の塞ぎの問題を解決することができる。また以上のようにセグメントの交わりによって、既存のセグメントが切りつめたり分割される場合もある。この交わりと塞ぎの結果が図5の(c)に図示されている。
【0058】ライン・サンプリングによって、ポイント・サンプリングよりもさらに正確な、アンチエイリアシング・フィルタ畳み込みの測定が行われる。例えば、N個のポイント・サンプルによって、ほぼ1/Nに比例する精度が提供される。ライン・サンプルとエッジが互いにほぼ垂直に方向づけられたとき、エッジに対して垂直に方向づけられたライン・サンプルによって、完全な精度で、また、妥当な正確さでそのエッジについての畳み込み計算が行われる。
【0059】ライン・サンプルとエッジが互いに平行に方向づけられている場合、ライン・サンプルは図6の(a)と(b)に図示のように単一ポイント・サンプルとして機能する。図6の(a)では、ライン・サンプル600は画素603の中心を通り、オブジェクト602のエッジ601に平行に方向づけられる。ここで、ライン・サンプルとオブジェクトの間にはカバーレージが存在しない(WCV=0)。エッジの位置のわずかな変化(すなわち、オブジェクトがライン・サンプルをカバーするとすぐに生じる変化)によって、カバーレージのない状態から最大のカバーレージ(WCV=1)への図6の(b)に示すような外観の急激な変化が生じる。
【0060】上記の理由のために、異なる方向を持つ複数のライン・サンプルを取ってその結果として生じるWCVを組み合わせるか、連続画像中のエッジ方向に依存するライン・サンプルの方向を選択するかのいずれかを行うことが有利である。
【0061】複数のラインを用いることは個々のライン・サンプルの貢献度に重み付けを行う方法を必要とする。1つの方法によって等しく貢献度の重み付けが行われ、ライン・サンプルから得られた値が平均化されて最終結果が生成される。以下に説明するように、下にある連続画像のエッジのサンプリングを行うためにライン・サンプルがどのように良好に方向づけられているかを示す何らかの測定値に基づき、ライン・サンプルの重み付けを行うことにより畳み込みのさらに良好な近似値が生成される。
【0062】互いに垂直な2つのライン・サンプルを用いていずれの方向のエッジについても十分な精度で畳み込みの測定を行うことが可能である。その場合、いくつかの基準に基づいて各サンプルの貢献度についての重み付けを測定することができる。各エッジの相対方向とそのエッジと交わるライン・サンプルについて考慮することができる。各ライン・サンプルと交わるエッジの数を係数とすることができる。ライン・サンプルの可視セグメントの分散あるいは他の統計的測定値を利用することが可能となる。
【0063】図7の(a)で、画素709についての2つのライン・サンプル701と702は互いに垂直に設けられる。ライン・サンプル701はオブジェクト700と部分的に交わり、ライン・サンプル702は完全にオブジェクトの外側に存在する。オブジェクト700に対応する、ライン・サンプル701と702についてのセグメント情報がそれぞれグラフ704と705に示されている。図7の(b)では、オブジェクト700はライン・サンプル701と702に関連して移動している。ライン・サンプル702は完全にオブジェクト700の内部に存在し、ライン・サンプル701の大部分はオブジェクト700と交わっている。
【0064】それぞれのセグメント情報がグラフ706と707に示されている。エッジに対するライン・サンプルの垂直方向による、エッジ708の正確なアンチエイリアシングがライン・サンプル701によって行われる。ライン・サンプル701と702によって、画素709におけるオブジェクト700の2つのWCVの計算が行われる。ライン・サンプル701によってさらに正確にエッジ708のアンチエイリアシングが行われるので、ライン・サンプル701から計算されたWCVのほうが、ライン・サンプル702によって計算されたWCVより、画素709におけるオブジェクト700の2つの組み合わされたWCVに対する貢献度が大きくなる。
【0065】図8に図示のように、ライン・サンプル803に沿うサンプルの重み付けに影響を与えるエッジへの考慮は“可視”エッジのみに限定するのが有効である。可視エッジ801は、(同じカラーからなる)別のポリゴンに(例えば該カラーの点で)一致しないポリゴンのエッジによって、あるいは塞ぎや交わりによって生成されるエッジである。同じカラーからなる2つのポリゴンが合わさった場合に生じるエッジ802は、作成された画像の中で目に見える可能性が少ない。したがって、エッジと交わるライン・サンプルの重み付けに該エッジが影響を与えないようにするために、このエッジ802は“非可視”のものとして処理したほうがよい。例えば、複数の隣接するポリゴンからなるオブジェクトは、結果に影響を与えるポリゴン間の内部エッジを持たないシルエット・エッジの方向に従ってアンチエイリアシングが行われる、オブジェクトのシルエット形成エッジを備えているほうがよい。
【0066】図9は、別のポリゴンb902を部分的に塞ぐポリゴンa901を示す図である。ポリゴンa901のエッジ903はポリゴンb902のエッジに一致することはない。エッジ903は不連続画像の中で可視であり、アンチエイリアシング計算に影響を与えるはずである。したがって、エッジ903を可視エッジとして処理し、ライン・サンプル904を用いてサンプルの重み付けの計算を行うほうがよい。
【0067】図10の(a)は、オブジェクト1000のエッジ1003の近辺で2つの垂直な軸整列しているライン・サンプル1001と1002に対してどのように重み付けの測定を行うことができるかを示す図である。この図では、エッジ1003の方向はライン・サンプル1001−1002のいずれにも垂直ではない。エッジ1003に沿って進むベクトル計算を行うことができる。図10の(b)は、水平成分Vx1005と垂直成分Vy1006とを持つ、エッジ1003についてのエッジ・ベクトル1004を図示するものである。
【0068】この方法によって、ライン・サンプルのいずれかと交わる各可視エッジの正規化されたベクトル(Vnx,Vny)がまず測定される。次いで、成分(Vnx,Vny)を持つ正規化されたエッジ・ベクトルについて、垂直サンプルの総重み付けにVnx2を加算し、水平サンプルの総重み付けにVny2を加算する。成分の値の二乗を用いて任意のエッジの貢献度の総和が1に等しく保たれる。関連するエッジの貢献度のすべてに重み付けが行われた後、垂直および水平のライン・サンプルの相対的重み付けを測定することができ、これらの相対的重み付けを用いて2つのライン・サンプルのWCVのブレンディング(blending)が行われる。このブレンディングは1次ブレンディング関数、三次ブレンディング関数あるいはさらに大きな重み付けを行ったWCVの選択のような任意の適切なブレンディング関数を利用することができる。
【0069】図11の(a)に図示のように、従来型のラスタ化法を用いて2つの垂直な軸整列ライン・サンプルについてのライン・サンプル評価のスピード・アップを図ることが可能である。図11の(a)では、ライン・サンプル1102と1103を持つ画素グリッド1100の画素1101においてサンプリングを行うことが望ましい。一般に選択される、画素間の距離に等しい半径を持つアンチエイリアシング・フィルタを使用するとき、ポイント・サンプリングに現在利用される高速ラスタ化法を用いて、ちょうど画素グリッド位置上に在るライン・サンプルの端点1109におけるエッジ距離の値を生成することができる。1つのライン・サンプルの端点と1つのエッジのエッジ距離の値は、ライン・サンプルの端点とそのエッジ間の最短距離として定義される。
【0070】図11の(b)に図示のように、ライン・サンプル1102と1103を表すために“黒丸”の画素1104が用いられ“白丸”の画素1105は使用されない。Pineda算術を用いてライン・サンプルの端点における画像中のポリゴンについてエッジ距離の値を効率的に生成することができる。Pineda"ポリゴン・ラスタ化のための並列アルゴリズム”(SIGGRAPHの会報、コンピュータ・グラフィックス、Vol.22. NO.4、pp.17−20、1988)を参照されたい。これらのエッジ距離の値は直線的に変動するので、ライン・サンプルの端点におけるエッジ距離の値のみが与えられれば、初等幾何学的方法あるいは代数的方法(例えば類似三角形)を用いて、ライン・サンプルのセグメントを効率的に生成することができる。セグメントは、エッジ距離の値がすべて正の場合ライン・サンプルの一部となる。
【0071】従来の走査線ラスタ化法を用いて、不連続画像中の画素の列と行全体についてライン・サンプルの生成を行うことができる。これらの手法を用いて連続画像全体にわたるライン上のすべての可視セグメントを生成することができる。次いで、画素のフィルタ・フットプリント内の可視セグメント部分を考慮することにより、連続画像全体にわたるラインと同じ方向で、1つの画素についてライン・サンプルが生成される。
【0072】下にある連続画像中のエッジに関する情報が分かっている場合には、正確な方向を持つ1画素当たりの単一ライン・サンプルで、その画像のサンプリングを行う画素のWCVの適切な生成を行うのに十分である。その連続画像自体からエッジ情報を得ることができる。例えば図12に図示のように、多くのオブジェクト1200(フォントなど)を境界曲線1201によって指定することができる。曲線1203のタンジェント(正接:tangent)情報1202はこの曲線についての記述から計算することができる。ライン・サンプル1205はタンジェント1202の方向に対して垂直に方向づけられている。
【0073】図13に示される代替方法では、連続画像1301から低い分解能のポイント・サンプル化画像1302が生成される。低い分解能の画像1302はエッジ情報1303を生成するエッジ検出オペレータで処理される。検出されたエッジ情報1303は適切なライン・サンプル1304の方向を示す。次いで適切に方向づけられたライン・サンプルがその連続画像に適用されてWCVが生成され、このWCVはアンチエイリアシングされた不連続画像1305を生成するために用いられる。
【0074】以上、いくつかの異なる応用例の推奨する実施の形態とその様々な改変例という点から本発明について説明してきたが、図面による上述の説明に基づいて、特に本発明の柔軟性と適応性を考慮すると本発明の範囲内で他の改変を行うことが可能であることは当業者には明白であろう。本発明の実際の範囲は以下の請求項に記載されている。
【0075】
【発明の効果】以上のようにこの発明によれば、フィルタ関数を用いて、1つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、ライン・サンプルを定義するステップと、前記フィルタ関数と前記ライン・サンプルから累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、前記選択された画素に対応する前記連続画像中の1点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、前記測定距離における累進的畳み込みを評価して重み付きカバーレージ値を生成するステップと、前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法としたので、不連続画像の生成中、メモリの大幅な増加や描画速度の低下を伴わない改善されたアンチエイリアシング法が提供できる。
【図面の簡単な説明】
【図1】 この発明によるライン・サンプルによるアンチエイリアシング方法におけるグラフィックオブジェクトのエッジまでの様々な距離における画素の中心を通るライン・サンプルのフィルタ・フットプリントおよびフィルタ関数を示す図である。
【図2】 この発明における累進的畳み込みを示す図である。
【図3】 この発明における2つのエッジと交わるライン・サンプル、セグメント情報、累進的畳み込みの2つの評価値の差、2つのカバーレージ評価値間の差を示す図である。
【図4】 オブジェクトを塞ぐライン・サンプリングを示す図である。
【図5】 この発明におけるオブジェクトと交わるライン・サンプリングを示す図である。
【図6】 エッジに対して平行方向のライン・サンプルを示す図である。
【図7】 2本の直交ライン・サンプルを使用するライン・サンプリングを示す図である。
【図8】 ライン・サンプルされた隣接オブジェクトの可視および非可視エッジを示す図である。
【図9】 ライン・サンプルされた相互に塞ぎあうオブジェクトの可視および非可視エッジを示す図である。
【図10】 正規化されたエッジに従うライン・サンプリングを行うための重み付け用複数ライン・サンプルを示す図である。
【図11】 画素グリッド位置におけるライン・サンプリング用データ生成を示す図である。
【図12】 タンジェント方向に垂直な方向を持つ境界曲線のライン・サンプリングを示す図である。
【図13】 低い分解能の画像とエッジ検出を用いるライン・サンプリングを示す図である。
【符号の説明】
100,304、603,709,1101,1104,1105 画素、101,601,708,903,1003 エッジ、102 フットプリント、103 フィルタ関数、104 グラフィック・オブジェクト、105,303,404,504、600,701,702,803,904,1001,1002,1102,1103,1205,1304 ライン・サンプル、200,330 累進的畳み込み(PC)、300,602,700,1000,1200オブジェクト、301 エッジa、302 エッジb、309 フィルタ・フットプリント、320 セグメント、401,501,901 ポリゴンa、402、502,902 ポリゴンb、403,503 サンプル・デプス情報(Z)。
【特許請求の範囲】
【請求項1】 フィルタ関数を用いて、1つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、ライン・サンプルを定義するステップと、前記フィルタ関数と前記ライン・サンプルから累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、前記選択された画素に対応する前記連続画像中の1点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、前記測定距離における累進的畳み込みを評価して重み付きカバーレージ値を生成するステップと、前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法。
【請求項2】 前記エッジが可視であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項3】 前記選択された画素が前記エッジからの所定の距離の範囲内に在ることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項4】 前記所定の距離が前記ライン・サンプルの長さ以下であることを特徴とする請求項3に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項5】 前記ライン・サンプルが直線であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項6】 前記ライン・サンプルが前記画素のほぼ中心を通り、前記エッジにほぼ垂直であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項7】 前記ライン・サンプルが少なくとも前記フィルタ関数のフットプリントの範囲にわたる有限の長さを有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項8】 前記フィルタ関数がガウス関数であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項9】 前記累進的畳み込みが様々な距離における前記フィルタ関数の累積積分であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項10】 前記累進的畳み込みが連続関数によって定義されることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項11】 前記累進的畳み込みの値が有限数の距離についてテーブルに格納されることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項12】 前記連続画像が第1および第2のエッジを含み、前記選択された画素に対応する前記連続画像中の1点から前記第1および第2のエッジまでの、第1および第2の距離を測定するステップと、前記測定された第1および第2の距離における前記累進的畳み込みを評価して、第1および第2の重み付きカバーレージ値を生成するステップと、前記第1および第2の重み付きカバーレージ値の差を前記画素と関連付けて、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項13】 前記連続画像中の前記エッジが第2のオブジェクトと相互に作用する第1のオブジェクトから結果として生じ、前記選択された画素が前記第1のオブジェクトの第1のデプス情報と、前記第2のオブジェクトの第2のデプス情報とを持ち、相互に作用する前記ライン・サンプルのセクションを測定するステップと、前記セクションの前記デプス情報に基づいてセクションを選択的に保持し、廃棄するステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項14】 塞ぐことにより前記第1および第2のオブジェクトが相互に作用することを特徴とする請求項13に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項15】 交わることにより前記第1および第2のオブジェクトが相互に作用することを特徴とする請求項13に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項16】 第1のライン・サンプルと第2のライン・サンプルとを定義するステップと、前記フィルタ関数と前記第1のライン・サンプルとから第1の累進的畳み込みを導き出すステップと、前記フィルタ関数と前記第2のライン・サンプルとから第2の累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、前記選択された画素に関して前記第1および第2のライン・サンプルの方向付けを行うステップと、前記選択された画素に対応する前記連続画像中の1点から、前記方向づけられた第1と第2のライン・サンプルに沿う前記エッジまでの第1および第2の距離を測定するステップと、前記第1のライン・サンプルの前記第1の累進的畳み込みと、前記測定された第1および第2の距離における前記第2のライン・サンプルの前記第2の累進的畳み込みとを評価し、第1の重み付きカバーレージ値と第2の重み付きカバーレージ値とを生成するステップと、前記第1および第2のライン・サンプルの重み付けを行うステップと、前記第1および第2のライン・サンプルの前記重み付けに従って前記第1および第2の重み付きカバーレージ値をブレンドするステップと、前記ブレンドされた重み付きカバーレージ値を前記画素と関連付け、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項17】 前記第1のライン・サンプルが前記第2のライン・サンプルに対して垂直であることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項18】 前記エッジに関して前記第1および第2のライン・サンプルの方向に従って前記第1および第2のライン・サンプルが評価され、重み付けが行われることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項19】 前記重み付けが前記エッジから導き出された正規化されたベクトルを用いることを特徴とする請求項18に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項20】 前記第1および第2のライン・サンプルの長さが前記不連続画像の画素間の距離の2倍であり、さらに、前記エッジ距離の値が前記ライン・サンプルの端点において生成されることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項21】 画素の列と行を選択するステップと、画素の前記列と行と整列した前記連続画像の全範囲にわたるラインを選択するステップと、前記連続画像の全範囲にわたる前記ラインについてセグメント情報を生成するステップと、前記連続画像の全範囲にわたる前記ラインについて可視セグメントを測定するステップと、画素の前記列と行中の画素を選択するステップと、前記画素における前記フィルタ関数のフットプリントの範囲内で前記可視セグメントから前記画素についてライン・サンプルを生成するステップと、を更に有することを特徴とするに請求項16に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項22】 前記エッジが曲線であり、前記曲線に対してタンジェントを測定するステップと、前記ライン・サンプルを前記タンジェントに対して垂直に方向づけるステップと、を更に有することを特徴とするに請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項23】 前記連続画像の低い分解能の画像を生成するステップと、前記低い分解能の画像に対してエッジ検出オペレータを適用して前記エッジを生成するステップと、前記エッジに対して垂直に前記ライン・サンプルを方向づけるステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項1】 フィルタ関数を用いて、1つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、ライン・サンプルを定義するステップと、前記フィルタ関数と前記ライン・サンプルから累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、前記選択された画素に対応する前記連続画像中の1点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、前記測定距離における累進的畳み込みを評価して重み付きカバーレージ値を生成するステップと、前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法。
【請求項2】 前記エッジが可視であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項3】 前記選択された画素が前記エッジからの所定の距離の範囲内に在ることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項4】 前記所定の距離が前記ライン・サンプルの長さ以下であることを特徴とする請求項3に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項5】 前記ライン・サンプルが直線であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項6】 前記ライン・サンプルが前記画素のほぼ中心を通り、前記エッジにほぼ垂直であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項7】 前記ライン・サンプルが少なくとも前記フィルタ関数のフットプリントの範囲にわたる有限の長さを有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項8】 前記フィルタ関数がガウス関数であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項9】 前記累進的畳み込みが様々な距離における前記フィルタ関数の累積積分であることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項10】 前記累進的畳み込みが連続関数によって定義されることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項11】 前記累進的畳み込みの値が有限数の距離についてテーブルに格納されることを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項12】 前記連続画像が第1および第2のエッジを含み、前記選択された画素に対応する前記連続画像中の1点から前記第1および第2のエッジまでの、第1および第2の距離を測定するステップと、前記測定された第1および第2の距離における前記累進的畳み込みを評価して、第1および第2の重み付きカバーレージ値を生成するステップと、前記第1および第2の重み付きカバーレージ値の差を前記画素と関連付けて、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項13】 前記連続画像中の前記エッジが第2のオブジェクトと相互に作用する第1のオブジェクトから結果として生じ、前記選択された画素が前記第1のオブジェクトの第1のデプス情報と、前記第2のオブジェクトの第2のデプス情報とを持ち、相互に作用する前記ライン・サンプルのセクションを測定するステップと、前記セクションの前記デプス情報に基づいてセクションを選択的に保持し、廃棄するステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項14】 塞ぐことにより前記第1および第2のオブジェクトが相互に作用することを特徴とする請求項13に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項15】 交わることにより前記第1および第2のオブジェクトが相互に作用することを特徴とする請求項13に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項16】 第1のライン・サンプルと第2のライン・サンプルとを定義するステップと、前記フィルタ関数と前記第1のライン・サンプルとから第1の累進的畳み込みを導き出すステップと、前記フィルタ関数と前記第2のライン・サンプルとから第2の累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、前記選択された画素に関して前記第1および第2のライン・サンプルの方向付けを行うステップと、前記選択された画素に対応する前記連続画像中の1点から、前記方向づけられた第1と第2のライン・サンプルに沿う前記エッジまでの第1および第2の距離を測定するステップと、前記第1のライン・サンプルの前記第1の累進的畳み込みと、前記測定された第1および第2の距離における前記第2のライン・サンプルの前記第2の累進的畳み込みとを評価し、第1の重み付きカバーレージ値と第2の重み付きカバーレージ値とを生成するステップと、前記第1および第2のライン・サンプルの重み付けを行うステップと、前記第1および第2のライン・サンプルの前記重み付けに従って前記第1および第2の重み付きカバーレージ値をブレンドするステップと、前記ブレンドされた重み付きカバーレージ値を前記画素と関連付け、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項17】 前記第1のライン・サンプルが前記第2のライン・サンプルに対して垂直であることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項18】 前記エッジに関して前記第1および第2のライン・サンプルの方向に従って前記第1および第2のライン・サンプルが評価され、重み付けが行われることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項19】 前記重み付けが前記エッジから導き出された正規化されたベクトルを用いることを特徴とする請求項18に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項20】 前記第1および第2のライン・サンプルの長さが前記不連続画像の画素間の距離の2倍であり、さらに、前記エッジ距離の値が前記ライン・サンプルの端点において生成されることを特徴とする請求項16に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項21】 画素の列と行を選択するステップと、画素の前記列と行と整列した前記連続画像の全範囲にわたるラインを選択するステップと、前記連続画像の全範囲にわたる前記ラインについてセグメント情報を生成するステップと、前記連続画像の全範囲にわたる前記ラインについて可視セグメントを測定するステップと、画素の前記列と行中の画素を選択するステップと、前記画素における前記フィルタ関数のフットプリントの範囲内で前記可視セグメントから前記画素についてライン・サンプルを生成するステップと、を更に有することを特徴とするに請求項16に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項22】 前記エッジが曲線であり、前記曲線に対してタンジェントを測定するステップと、前記ライン・サンプルを前記タンジェントに対して垂直に方向づけるステップと、を更に有することを特徴とするに請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項23】 前記連続画像の低い分解能の画像を生成するステップと、前記低い分解能の画像に対してエッジ検出オペレータを適用して前記エッジを生成するステップと、前記エッジに対して垂直に前記ライン・サンプルを方向づけるステップと、を更に有することを特徴とする請求項1に記載のライン・サンプルによるアンチエイリアシング方法。
【図1】
【図2】
【図8】
【図9】
【図3】
【図4】
【図5】
【図6】
【図7】
【図10】
【図11】
【図12】
【図13】
【図2】
【図8】
【図9】
【図3】
【図4】
【図5】
【図6】
【図7】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2001−52160(P2001−52160A)
【公開日】平成13年2月23日(2001.2.23)
【国際特許分類】
【出願番号】特願2000−200747(P2000−200747)
【出願日】平成12年7月3日(2000.7.3)
【出願人】(597067574)ミツビシ・エレクトリック・インフォメイション・テクノロジー・センター・アメリカ・インコーポレイテッド (484)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC INFORMATION TECHNOLOGY CENTER AMERICA, INC.
【住所又は居所原語表記】201 BROADWAY, CAMBRIDGE, MASSACHUSETTS 02139, U.S.A.
【公開日】平成13年2月23日(2001.2.23)
【国際特許分類】
【出願日】平成12年7月3日(2000.7.3)
【出願人】(597067574)ミツビシ・エレクトリック・インフォメイション・テクノロジー・センター・アメリカ・インコーポレイテッド (484)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC INFORMATION TECHNOLOGY CENTER AMERICA, INC.
【住所又は居所原語表記】201 BROADWAY, CAMBRIDGE, MASSACHUSETTS 02139, U.S.A.
[ Back to top ]