(57)【特許請求の範囲】
【請求項１】
フィルタ関数を用いて、１つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、
前記エッジに対して少なくとも前記フィルタ関数のフットプリントの範囲にわたる有限な長さを有する直線のライン・サンプルを定めるステップと、
前記フィルタ関数と前記ライン・サンプルから前記エッジからの異なる複数の距離における前記フィルタ関数の累積積分である累進的畳み込みを導き出すステップと、
前記不連続画像における所定位置で画素を選択するステップと、
該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、
前記選択された画素に対応する前記連続画像中の１点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、
前記測定距離における累進的畳み込みを前記エッジとの距離と位置関係を評価して重み付きカバーレージ値を生成するステップと、
前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、
を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法。
【請求項２】
前記エッジが可視であることを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項３】
前記選択された画素が前記エッジからの所定の距離の範囲内に在ることを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項４】
前記所定の距離が前記ライン・サンプルの長さ以下であることを特徴とする請求項３に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項５】
前記ライン・サンプルが前記画素のほぼ中心を通り、前記エッジにほぼ垂直であることを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項６】
前記フィルタ関数がガウス関数であることを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項７】
前記累進的畳み込みが連続関数によって定義されることを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項８】
前記累進的畳み込みの値が有限数の距離についてテーブルに格納されることを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項９】
前記連続画像が第１および第２のエッジを含み、
前記選択された画素に対応する前記連続画像中の１点から前記第１および第２のエッジまでの、第１および第２の距離を測定するステップと、
前記測定された第１および第２の距離における前記累進的畳み込みを評価して、第１および第２の重み付きカバーレージ値を生成するステップと、
前記第１および第２の重み付きカバーレージ値の差を前記画素と関連付けて、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、
を更に有することを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１０】
前記連続画像中の前記エッジが第２のオブジェクトと相互に作用する第１のオブジェクトから結果として生じ、前記選択された画素が前記第１のオブジェクトの第１のデプス情報と、前記第２のオブジェクトの第２のデプス情報とを持ち、
相互に作用する前記ライン・サンプルのセクションを測定するステップと、
前記セクションの前記デプス情報に基づいてセクションを選択的に保持し、廃棄するステップと、
を更に有することを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１１】
塞ぐことにより前記第１および第２のオブジェクトが相互に作用することを特徴とする請求項１０に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１２】
交わることにより前記第１および第２のオブジェクトが相互に作用することを特徴とする請求項１０に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１３】
第１のライン・サンプルと第２のライン・サンプルとを定めるステップと、
前記フィルタ関数と前記第１のライン・サンプルとから第１の累進的畳み込みを導き出すステップと、
前記フィルタ関数と前記第２のライン・サンプルとから第２の累進的畳み込みを導き出すステップと、
前記不連続画像における所定位置で画素を選択するステップと、
前記選択された画素に関して前記第１および第２のライン・サンプルの方向付けを行うステップと、
前記選択された画素に対応する前記連続画像中の１点から、前記方向づけられた第１と第２のライン・サンプルに沿う前記エッジまでの第１および第２の距離を測定するステップと、
前記第１のライン・サンプルの前記第１の累進的畳み込みと、前記測定された第１および第２の距離における前記第２のライン・サンプルの前記第２の累進的畳み込みとを評価し、第１の重み付きカバーレージ値と第２の重み付きカバーレージ値とを生成するステップと、
前記第１および第２のライン・サンプルの重み付けを行うステップと、
前記第１および第２のライン・サンプルの前記重み付けに従って前記第１および第２の重み付きカバーレージ値をブレンドするステップと、
前記ブレンドされた重み付きカバーレージ値を前記画素と関連付け、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、
を更に有することを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１４】
前記第１のライン・サンプルが前記第２のライン・サンプルに対して垂直であることを特徴とする請求項１３に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１５】
前記エッジに関して前記第１および第２のライン・サンプルの方向に従って前記第１および第２のライン・サンプルが評価され、重み付けが行われることを特徴とする請求項１３に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１６】
前記重み付けが前記エッジから導き出された正規化されたベクトルを用いることを特徴とする請求項１５に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１７】
前記第１および第２のライン・サンプルの長さが前記不連続画像の画素間の距離の２倍であり、さらに、前記エッジ距離の値が前記ライン・サンプルの端点において生成されることを特徴とする請求項１３に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１８】
画素の列と行を選択するステップと、
画素の前記列と行と整列した前記連続画像の全範囲にわたるラインを選択するステップと、
前記連続画像の全範囲にわたる前記ラインについてセグメント情報を生成するステップと、
前記連続画像の全範囲にわたる前記ラインについて可視セグメントを測定するステップと、
画素の前記列と行中の画素を選択するステップと、
前記画素における前記フィルタ関数のフットプリントの範囲内で前記可視セグメントから前記画素についてライン・サンプルを生成するステップと、
を更に有することを特徴とするに請求項１３に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項１９】
前記エッジが曲線であり、
前記曲線に対してタンジェントを測定するステップと、
前記ライン・サンプルを前記タンジェントに対して垂直に方向づけるステップと、
を更に有することを特徴とするに請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【請求項２０】
前記連続画像の低い分解能の画像を生成するステップと、
前記低い分解能の画像に対してエッジ検出オペレータを適用して前記エッジを生成するステップと、
前記エッジに対して垂直に前記ライン・サンプルを方向づけるステップと、
を更に有することを特徴とする請求項１に記載のライン・サンプルによるアンチエイリアシング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般に画像処理に関し、特に連続画像のサンプリング時に生じるエイリアシングの影響の除去を行うライン・サンプルによるアンチエイリアシング方法に関する。
【０００２】
【従来の技術】
画像作成用の多種多様のコンピュータ・アプリケーションが存在する。これらのアプリケーションにはゲーム、グラフィック・デザイン、アニメーション、シミュレーション、視覚化、モデリングなどが含まれる。これらのアプリケーションでは作成された画像は可能な限りリアルであるほうがよい。
【０００３】
コンピュータ・グラフィックスでは、作成画像は連続画像の不連続(個別)サンプルの規則的な配列として表される。この“不連続画像”はある一定の有限のレートでの連続画像のサンプリングの結果生じたものである。個々のサンプル・ポイントは画素と呼ばれる。画素がサンプリング・ポイントであって不連続画像における矩形領域ではないことを記憶しておくことには批判的である。
【０００４】
サンプリング・レートが有限であることに起因して、連続画像中に存在する高周波は不正確な低周波となってしまう(alias)ことがある。エッジのような連続画像中のある共通の特徴は、無限に高い周波数を含むので、どのような有限サンプリング・レートでも結果的にどうしてもエイリアシングが発生してしまう。コンピュータ生成画像では、エイリアシングは画像オブジェクトの階段状の輪郭(すなわちいわゆる“ジャギー(jaggy)”)として現れる。エイリアシングによる他の影響として、モアレ図形と細かな細部の分裂(break up)が生じる場合もある。
【０００５】
アンチエイリアシングを利用して不連続画像の外観が改善される。アンチエイリアシングは、ある周波数限定フィルタを用いる連続画像の畳み込み計算とサンプリングによって達成される。画素は連続画像のフィルタされたバージョンのサンプルである。従来技術において畳み込みのサンプルを計算するために使用される２つの一般的方法として、エリア・サンプリングとポイント・サンプリングが存在する。
【０００６】
エリア・サンプリングによるアンチエイリアシング
エリア・サンプリングによるアンチ・エイリアシンでは、処理されたがまだ連続している形の連続画像を使用して、アンチエイリアシングフィルタ関数とこの連続画像の畳み込みとの正確な計算が行われる。この畳み込みはサンプル化され、不連続画像の画素を測定する間使用する値が生成される。一般に、フィルタ関数とは半径Ｒを有するガウスフィルタである。この半径によって“フットプリント(footprint)”すなわちフィルタの“サポート(support)”が定義される。
【０００７】
エリア・サンプリングで用いられる連続画像の処理された形は通常、各画素の周りに在るフィルタ・フットプリントの中で目に見える１セットのポリゴンである。不都合なことに、多くの場合連続画像は、互いに塞いだり交わることがある幾何学的オブジェクトを含む３次元場面の記述によって定義される。これらの塞ぎ(occlusion)と交わり(intersection)によって、連続画像を効率的に処理してエリア・サンプリングに適した形に変えることは困難になる。というのは複雑な形状は単純なオブジェクトの相互作用から結果として生じる場合もあるからである。
【０００８】
ポイント・サンプリングによるアンチエイリアシング
ポイント・サンプリングによるアンチエイリアシングでは、画素の近傍で複数のサンプル・ロケーションが用いられる。連続画像は画素位置に対応するポイントにおいて評価され、その結果得られる値は、フィルタ関数と連続画像との畳み込みを近似させる試みの中で何らかの重み付け関数に従って合成される。ポイント・サンプリングは、その実施の単純さと容易さのためにアンチエイリアシングに用いられる最も一般的な方法である。３次元場面のエリア・サンプリングに存在する塞ぎ問題はポイント・サンプリングによって単純化されるが正しい解が得られるまでの時間のかかる収束に難点がある。一般に、Ｎ個のポイント・サンプルには１／Ｎの精度で画素値の計算が必要となる。ポイント・サンプルの位置は互いに離れていて繋がりがないので、細かい細部についてはサンプリング時に全く無視することができる。したがって、これらの無視された細部が不連続画像に貢献することはあり得ない。
【０００９】
ポイント・サンプリング法とエリア・サンプリングとの組み合わせ
エリア・サンプリング法とポイント・サンプリング法とはレンダリング・システムにおいて組み合わされて用いられることが多い。エリア・サンプリングは、テクスチャ・マップのような２次元サンプル化画像に効率的に適用することができ、一方、ポイント・サンプリングは、ポリゴンのエッジとの交わりのアンチエイリアシングを行うために用いるのが一般的である。ポイント・サンプリングを用いて、ある画素のフィルタ・フットプリント内に在るポリゴンの重み付きカバーレージ値(ＷＣＶ:weighted coverage value)が生成される。次いでこれらの値はその画素と関連付けられる。ＷＣＶとは、１つの画素のカラーに対するそのポリゴンのカラー貢献度の重み付けを行う画素における、アンチエイリアシング・フィルタとポリゴンの可視部分との畳み込みの結果を表す値である。エリア・サンプリング法を用いて、その画素と関連付けられたポリゴンのカラーが作成される。次いで、ＷＣＶとその画素と関連付けられたカラーとが組み合わされて、不連続画像の画素の最終カラーが作成される。
【００１０】
その他のアンチエイリアシング法
Maxは、“アンチエイリアシング走査線データ”(ＩＥＥＥコンピュータ・グラフィックス＆アプリケーション１０(１)：１８−３０、１９９０年１月)の中で１つの混成的方法について記載している。彼の示す混成的方法は、スーパー・サンプリングを用いて１つの方向のアンチエイリアシングを行いながら、エリア・サンプリングを近似することによりもう一方の方向に連続してアンチエイリアシングを行うものである。連続方向にほぼ平行なエッジのアンチエイリアシングは、連続方向にほぼ垂直なエッジに対するアンチエイリアシングと比べると効率的なものではない。
【００１１】
【発明が解決しようとする課題】
以上のように、従来技術のエリア・サンプリングおよびポイント・サンプリングのアンチエイリアシング法には多数の欠点と問題点が存在し、従って不連続画像の生成中、メモリの大幅な増加や描画速度の低下を伴わない改善されたアンチエイリアシング法に対する要望があった。
【００１２】
本発明は、フィルタ関数を用いて、エッジを含む連続画像からサンプル化されたアンチエイリアシングされた不連続画像を生成するライン・サンプルによるアンチエイリアシング方法を提供することを目的とするものである。この方法によってライン・サンプルが定義される。上記フィルタ関数とライン・サンプルとから累進的畳み込みが導き出される。不連続画像の所定位置で画素が選択され、ライン・サンプルが選択された画素に関して方向づけが行われる。
【００１３】
選択された画素に対応する連続画像中の１点から上記方向づけられたライン・サンプルに沿ったエッジまでの距離が測定される。上記累進的畳み込みはこの測定距離で評価され、重み付きカバーレージ値が生成され、この重み付きカバーレージ値が画素と関連付けられて不連続画像中の画素のアンチエイリアシングが行われる。
【００１４】
【課題を解決するための手段】
上記の目的に鑑み、この発明は、フィルタ関数を用いて、１つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、前記エッジに対して少なくとも前記フィルタ関数のフットプリントの範囲にわたる有限な長さを有する直線のライン・サンプルを定めるステップと、前記フィルタ関数と前記ライン・サンプルから前記エッジからの異なる複数の距離における前記フィルタ関数の累積積分である累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、前記選択された画素に対応する前記連続画像中の１点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、前記測定距離における累進的畳み込みを前記エッジとの距離と位置関係を評価して重み付きカバーレージ値を生成するステップと、前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法にある。
【００１５】
また、前記エッジが可視であることを特徴とする。
【００１６】
また、前記選択された画素が前記エッジからの所定の距離の範囲内に在ることを特徴とする。
【００１７】
また、前記所定の距離が前記ライン・サンプルの長さ以下であることを特徴とする。
【００１９】
また、前記ライン・サンプルが前記画素のほぼ中心を通り、前記エッジにほぼ垂直であることを特徴とする。
【００２１】
また、前記フィルタ関数がガウス関数であることを特徴とする。
【００２３】
また、前記累進的畳み込みが連続関数によって定義されることを特徴とする。
【００２４】
また、前記累進的畳み込みの値が有限数の距離についてテーブルに格納されることを特徴とする。
【００２５】
また、前記連続画像が第１および第２のエッジを含み、前記選択された画素に対応する前記連続画像中の１点から前記第１および第２のエッジまでの、第１および第２の距離を測定するステップと、前記測定された第１および第２の距離における前記累進的畳み込みを評価して、第１および第２の重み付きカバーレージ値を生成するステップと、前記第１および第２の重み付きカバーレージ値の差を前記画素と関連付けて、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする。
【００２６】
また、前記連続画像中の前記エッジが第２のオブジェクトと相互に作用する第１のオブジェクトから結果として生じ、前記選択された画素が前記第１のオブジェクトの第１のデプス情報と、前記第２のオブジェクトの第２のデプス情報とを持ち、相互に作用する前記ライン・サンプルのセクションを測定するステップと、前記セクションの前記デプス情報に基づいてセクションを選択的に保持し、廃棄するステップと、を更に有することを特徴とする。
【００２７】
また、塞ぐことにより前記第１および第２のオブジェクトが相互に作用することを特徴とする。
【００２８】
また、交わることにより前記第１および第２のオブジェクトが相互に作用することを特徴とする。
【００２９】
また、第１のライン・サンプルと第２のライン・サンプルとを定義するステップと、前記フィルタ関数と前記第１のライン・サンプルとから第１の累進的畳み込みを導き出すステップと、前記フィルタ関数と前記第２のライン・サンプルとから第２の累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、前記選択された画素に関して前記第１および第２のライン・サンプルの方向付けを行うステップと、前記選択された画素に対応する前記連続画像中の１点から、前記方向づけられた第１と第２のライン・サンプルに沿う前記エッジまでの第１および第２の距離を測定するステップと、前記第１のライン・サンプルの前記第１の累進的畳み込みと、前記測定された第１および第２の距離における前記第２のライン・サンプルの前記第２の累進的畳み込みとを評価し、第１の重み付きカバーレージ値と第２の重み付きカバーレージ値とを生成するステップと、前記第１および第２のライン・サンプルの重み付けを行うステップと、前記第１および第２のライン・サンプルの前記重み付けに従って前記第１および第２の重み付きカバーレージ値をブレンドするステップと、前記ブレンドされた重み付きカバーレージ値を前記画素と関連付け、前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を更に有することを特徴とする。
【００３０】
また、前記第１のライン・サンプルが前記第２のライン・サンプルに対して垂直であることを特徴とする。
【００３１】
また、前記エッジに関して前記第１および第２のライン・サンプルの方向に従って前記第１および第２のライン・サンプルが評価され、重み付けが行われることを特徴とする。
【００３２】
また、前記重み付けが前記エッジから導き出された正規化されたベクトルを用いることを特徴とする。
【００３３】
また、前記第１および第２のライン・サンプルの長さが前記不連続画像の画素間の距離の２倍であり、さらに、前記エッジ距離の値が前記ライン・サンプルの端点において生成されることを特徴とする。
【００３４】
また、画素の列と行を選択するステップと、画素の前記列と行と整列した前記連続画像の全範囲にわたるラインを選択するステップと、前記連続画像の全範囲にわたる前記ラインについてセグメント情報を生成するステップと、前記連続画像の全範囲にわたる前記ラインについて可視セグメントを測定するステップと、画素の前記列と行中の画素を選択するステップと、前記画素における前記フィルタ関数のフットプリントの範囲内で前記可視セグメントから前記画素についてライン・サンプルを生成するステップと、を更に有することを特徴とする。
【００３５】
また、前記エッジが曲線であり、前記曲線に対してタンジェントを測定するステップと、前記ライン・サンプルを前記タンジェントに対して垂直に方向づけるステップと、を更に有することを特徴とする。
【００３６】
また、前記連続画像の低い分解能の画像を生成するステップと、前記低い分解能の画像に対してエッジ検出オペレータを適用して前記エッジを生成するステップと、前記エッジに対して垂直に前記ライン・サンプルを方向づけるステップと、を更に有することを特徴する。
【００３７】
本発明の１つの局面では、アンチエイリアシングは可視エッジについてしか行われず、さらに該エッジから所定の距離内にある画素についてのみ検討がされる。例えば、上記所定距離をライン・サンプルの長さ以下の距離とする。
【００３８】
本発明の別の局面では、このライン・サンプルは、直線で、画素の中心を通りエッジに対してほぼ垂直である。
【００３９】
本発明のさらに別の局面では、フィルタ関数はガウス関数であり、累進的畳み込みは様々な距離のフィルタ関数の累積積分である。累進的畳み込みは連続関数によって定義することができる。あるいは、累進的畳み込みの値は有限数の距離用のテーブルに格納される。
【００４０】
本発明の別の局面では、複数のライン・サンプルが各画素について定義され、各ライン・サンプルの重み付きカバーレージ値が組み合わされて、画素と関連付けられた組み合わされた重み付きカバーレージ値が生成される。
【００４１】
【発明の実施の形態】
本発明はライン・サンプルを用いて、重み付きカバーレージ値(ＷＣＶ)を生成する改善された方法を提供するものであり、このカバーレージ値を利用して不連続画像のアンチエイリアシングを行うことが可能となる。ＷＣＶとは、ある画素のカラーに対するそのポリゴンのカラー貢献度の重み付けを行う画素における、アンチエイリアシング・フィルタとポリゴンの可視部分の畳み込みの結果を示す値である。
【００４２】
本発明によるライン・サンプリングは、効率と精度に関して従来技術によるエリア・サンプリング法とポイント・サンプリング法との中間に位置するものである。本発明のライン・サンプリング法を用いて形状情報(すなわちエッジ、塞ぎおよび交わり)からＷＣＶの計算を行うことができ、さらにシェード情報(すなわち従来技術におけるようなカラーとテクスチャ)のエリア・サンプリング法と本発明のライン・サンプリング法とを組み合わせることができる。このようにして、本発明による高品質のアンチエイリアシングされた画像の生成が可能となる。
【００４３】
ライン・サンプリングの根拠となる基本的な洞察は以下の特性によるものである。すなわち、エッジと、少なくとも、該エッジにほぼ垂直な方向を持つフィルタのフットプリントの範囲にわたるライン・サンプルとの交わりが与えられれば、有限フィルタと直線エッジの畳み込みを効率的にかつ正確に測定することが可能である。さらに、エリア・サンプルで行うよりもライン・サンプルで行う塞ぎと交わりの測定のほうがはるかに簡単である。このことは事実である。というのは、これらの相互作用(塞ぎと交わり)によって複雑さの少ない基本構造(primitive)が作成されるからである。さらに、塞ぎの問題は１回の計算によって１つのライン・サンプルの広い部分について解決することが可能となる。上記の特性によって、ライン・サンプリングに対する、ポイント・サンプリングより良好な収束と、エリア・サンプリングと同様の精度がしかも安い計算コストで得られる。
【００４４】
ライン・サンプルによる畳み込みの効率的計算には、所望のフィルタ関数から累進的畳み込み(ＰＣ:progressive convolution)を導き出す必要がある。この所望のフィルタ関数が半径方向に左右対称である場合には、１回のＰＣですべてのライン・サンプル方向について充分である。所望のフィルタ関数が半径方向に左右対称でない場合には、生じ得るライン・サンプル方向の各々について、あるいは、十分な数の別個の方向でＰＣを測定して、他の中間方向で補間が可能となるようにしなければならない。本発明によるＰＣの測定が図１と図２に示されている。
【００４５】
図１に図示のように、斜線で示される内部を持つグラフィック・オブジェクト１０４のエッジ１０１からの異なる距離(例えば、−１．５、−０．８、０．０、＋０．８、＋１．５)で画素１００が配置されている。画素の中心を通るフィルタ関数(図１の(ｆ)参照)のフットプリントは円１０２によって示される。フットプリントはフィルタ関数の“サポート”(すなわちフィルタ関数がノンゼロ値を有する領域)である。
【００４６】
図１の(ｆ)のグラフ１０３はフィルタによって生成された値を表すガウスフィルタ関数の一例であり、画素からの距離(Ｄ)を示すｘ軸と、該関数の強度(ｉ)を示すｙ軸とを有する。本発明では他のフィルタ関数も使用できることを理解されたい。
【００４７】
画素とエッジは相手からの異なる複数の距離で図示されている。直線分１０５は本発明によるライン・サンプルを表す。好ましくは、該ライン・サンプルは画素の中心を通る直線で、ライン・サンプルの方向がエッジ１０１に対して垂直になるように選択され、ライン・サンプル１０５の長さは少なくともフットプリント１０２の直径の範囲にわたることが望ましい。
【００４８】
ライン・サンプルは他の線形構成(例えば円、ベジエ曲線など)を持つものであってもよいと理解されたい。ライン・サンプルは他の位置、長さおよび方向を持つものであってもよいと理解されたい。ライン・サンプルの配置は、計算上好都合な場合には画素の中心から外れて画素の近くであってもよい。
【００４９】
図２はフィルタ関数１０３から導き出されたＰＣ２００を示す図である。オブジェクトの外側に在る画素の距離は負の数で、オブジェクトのエッジ上の画素の距離はゼロで、オブジェクト内部の画素の距離は正の数で示される。これらの距離はｘ軸２０１に沿って示される。ＰＣの重み付きカバーレージ(ＷＣＶ:weighted coverage value)の値はｙ軸２０２に沿って示される。ＷＣＶは０．０から１．０の範囲にある。例えば、画素がエッジ上に配置されている場合、ＰＣのＷＣＶは０．５となり、エッジ１０１によるフィルタ・フットプリント１０２のカバーレージの二分の１を示す。フィルタ・フットプリントが完全にオブジェクトの内部に配置されているとき、最大のカバーレージが存在し、フィルタ・フットプリントが完全にオブジェクトの外側にあるときカバーレージは存在しない。画素がエッジから離れて移動するにつれてＰＣ２００の値は０．５からゼロへ減少し、画素が反対方向に移動するにつれて０．５から１へ増加する。最大のカバーレージは図１ｆの曲線１０３の下の面積を表す。本質的に本発明による累進的畳み込みは、エッジからの様々な距離でのフィルタ関数の累積積分を表す。
【００５０】
エッジ１０１と一緒に畳み込まれたフィルタ１０３から導き出されるＰＣ２００を効率的に評価することができる。フィルタが単純な場合、ＰＣ２００は必要な時に関数的に評価することができる。フィルタが複雑なとき、エッジからの様々な距離でサブセットのＰＣ２００の値を予め計算し、中間距離で補間を行うためにテーブルにこの値を格納することができる。表形式で、ＰＣは距離によって索引化(indexed)され、中間値の補間を行うことが可能となる。図２のＰＣ２００ではすべての可能な距離、すなわち−∞から＋∞までのＷＣＶが示されているとはいえ、実際の利用時にはＷＣＶは非常に狭い範囲の距離(すなわち−２．０から＋２．０)にわたってしか変動しないと理解すべきである。この場合１単位は画素間の間隔に等しい。
【００５１】
フィルタが半径方向に非対称である場合、各ライン・サンプル方向についてＰＣを生成することができる。しかし、実際問題として、最も一般的に使用されているフィルタは単純な構造を持ち、半径方向に左右対称である。これによってテーブルの必要性がなくなりすべてのライン・サンプル方向について単一のＰＣで充分である。
【００５２】
図３の(ａ)〜(ｆ)は、本発明によるライン・サンプルを用いてどのように効率的にかつ正確に、所望のフィルタについてあるＰＣとオブジェクトとの所望の畳み込みの測定を行うことができるかを示す図である。オブジェクト３００はエッジａ、ｂ３０１〜３０２を持つ。ライン・サンプル３０３はエッジａ、ｂ３０１−３０２の間に配置される画素３０４の中心を通る。ライン・サンプル３０３は端点ｅ１(３０５)とｅ２(３０６)を持つ。所望の畳み込みは画素３０４におけるオブジェクト３００のＷＣＶである。ライン・サンプル３０３はフィルタ・フットプリント３０９の範囲にわたる。図示のように、ライン・サンプル３０３は複数のエッジにほぼ垂直に方向づけられる。距離ｄ１(３０７)とｄ２(３０８)は画素とライン・サンプル３０３に沿うエッジａとｂの間の相対的距離をそれぞれ示す。
【００５３】
図３の(ｂ)のグラフ３１０は、ライン・サンプル３０３とオブジェクト３００の交わりのセグメント情報を示す。ライン・サンプルに沿ったエッジの交わりの相対位置によって、２つの距離ｄ１とｄ２により境界が設けられるライン・サンプル上でセグメント３２０の測定が行われる。図３の(ｄ)に図示のフィルタ・フットプリント３０９とオブジェクト３００の内部との正確な畳み込みは、図３の(ｅ)に図示のようなエッジｂとフィルタの畳み込みと、図３の(ｆ)に図示のようなエッジａとフィルタの畳み込みとの差と考えることができる。図３の(ｃ)に図示のようにこの差はｄ２とｄ１で評価されるＰＣ３３０の値の間の差３３１に等しい。この差は、まさに画素３０４におけるオブジェクト３００のＷＣＶである。
【００５４】
図３に図示の方法の３つ以上のエッジへの拡張は当業者には自明である。
【００５５】
いくつかのポリゴンが部分的に塞いだり互いに交わるとき、複数のポリゴンの塞ぎと交わりによって非常に複雑な形状の生成を行うことが可能となる。これは三角形のような単純なポリゴンについても当てはまる。従来技術によるエリア・サンプルに対するものではなく、ライン・サンプルに対するアンチエイリアシングの畳み込みを行うことを決めることによって、図４の(ａ)〜(ｃ)に図示のような塞ぎの問題、ならびに、図５の(ａ)〜(ｃ)に図示のような交わりの問題は著しく単純化される。
【００５６】
図４の(ａ)では、ポリゴンａ(４０１)がポリゴンｂ(４０２)を部分的に塞いでいる。図４の(ｂ)は、ポリゴンａ、ｂに対応するセグメントのライン・サンプル４０４についてのサンプル・デプス情報(Ｚ)４０３を図示するものである。ライン・サンプルがａとｂの双方にオーバーラップする場合塞ぎが生じる。ライン・サンプル上のすべての点におけるデプス情報を比較すること、各点における最少のデプスを持つセグメントについての情報のみを保持することおよび各点における最大のデプスを持つセグメントについての情報を廃棄することにより上記塞ぎの問題を解決することができる。ライン・サンプルに沿って、セグメントのセクション全体について塞ぎを効率的に解決することができる。このような塞ぎによって、既存のセグメントが切りつめられたり、分割(ｓｐｌｉｔ)される場合もある。図４の(ｃ)はライン・サンプル４０４に沿ったａとｂの塞ぎの結果を図示するものである。図４の(ｂ)でのセクション４０５全体の塞ぎは、ラインセグメントの一部の選択的保持と廃棄により図４の(ｃ)の残り部分４０６を残しながら解決されている。
【００５７】
図５の(ａ)は、互いに交わるポリゴンａ(５０１)とｂ(５０２)とを図示するものである。図５の(ｂ)は、ポリゴンａとｂに対応するセグメントのライン・サンプル５０４に沿ってデプス情報(Ｚ)５０３を示す図である。２つのポリゴンの交わりは、対応するセグメントに対するデプス情報中の対応する交点５０５を結果として生み出す。この交わりを配置し利用することにより、上述のようなデプス情報に基づく選択的保持と廃棄によりａとｂの相互の塞ぎの問題を解決することができる。また以上のようにセグメントの交わりによって、既存のセグメントが切りつめたり分割される場合もある。この交わりと塞ぎの結果が図５の(ｃ)に図示されている。
【００５８】
ライン・サンプリングによって、ポイント・サンプリングよりもさらに正確な、アンチエイリアシング・フィルタ畳み込みの測定が行われる。例えば、Ｎ個のポイント・サンプルによって、ほぼ１／Ｎに比例する精度が提供される。ライン・サンプルとエッジが互いにほぼ垂直に方向づけられたとき、エッジに対して垂直に方向づけられたライン・サンプルによって、完全な精度で、また、妥当な正確さでそのエッジについての畳み込み計算が行われる。
【００５９】
ライン・サンプルとエッジが互いに平行に方向づけられている場合、ライン・サンプルは図６の(ａ)と(ｂ)に図示のように単一ポイント・サンプルとして機能する。図６の(ａ)では、ライン・サンプル６００は画素６０３の中心を通り、オブジェクト６０２のエッジ６０１に平行に方向づけられる。ここで、ライン・サンプルとオブジェクトの間にはカバーレージが存在しない(ＷＣＶ＝０)。エッジの位置のわずかな変化(すなわち、オブジェクトがライン・サンプルをカバーするとすぐに生じる変化)によって、カバーレージのない状態から最大のカバーレージ(ＷＣＶ＝１)への図６の(ｂ)に示すような外観の急激な変化が生じる。
【００６０】
上記の理由のために、異なる方向を持つ複数のライン・サンプルを取ってその結果として生じるＷＣＶを組み合わせるか、連続画像中のエッジ方向に依存するライン・サンプルの方向を選択するかのいずれかを行うことが有利である。
【００６１】
複数のラインを用いることは個々のライン・サンプルの貢献度に重み付けを行う方法を必要とする。１つの方法によって等しく貢献度の重み付けが行われ、ライン・サンプルから得られた値が平均化されて最終結果が生成される。以下に説明するように、下にある連続画像のエッジのサンプリングを行うためにライン・サンプルがどのように良好に方向づけられているかを示す何らかの測定値に基づき、ライン・サンプルの重み付けを行うことにより畳み込みのさらに良好な近似値が生成される。
【００６２】
互いに垂直な２つのライン・サンプルを用いていずれの方向のエッジについても十分な精度で畳み込みの測定を行うことが可能である。その場合、いくつかの基準に基づいて各サンプルの貢献度についての重み付けを測定することができる。各エッジの相対方向とそのエッジと交わるライン・サンプルについて考慮することができる。各ライン・サンプルと交わるエッジの数を係数とすることができる。ライン・サンプルの可視セグメントの分散あるいは他の統計的測定値を利用することが可能となる。
【００６３】
図７の(ａ)で、画素７０９についての２つのライン・サンプル７０１と７０２は互いに垂直に設けられる。ライン・サンプル７０１はオブジェクト７００と部分的に交わり、ライン・サンプル７０２は完全にオブジェクトの外側に存在する。オブジェクト７００に対応する、ライン・サンプル７０１と７０２についてのセグメント情報がそれぞれグラフ７０４と７０５に示されている。図７の(ｂ)では、オブジェクト７００はライン・サンプル７０１と７０２に関連して移動している。ライン・サンプル７０２は完全にオブジェクト７００の内部に存在し、ライン・サンプル７０１の大部分はオブジェクト７００と交わっている。
【００６４】
それぞれのセグメント情報がグラフ７０６と７０７に示されている。エッジに対するライン・サンプルの垂直方向による、エッジ７０８の正確なアンチエイリアシングがライン・サンプル７０１によって行われる。ライン・サンプル７０１と７０２によって、画素７０９におけるオブジェクト７００の２つのＷＣＶの計算が行われる。ライン・サンプル７０１によってさらに正確にエッジ７０８のアンチエイリアシングが行われるので、ライン・サンプル７０１から計算されたＷＣＶのほうが、ライン・サンプル７０２によって計算されたＷＣＶより、画素７０９におけるオブジェクト７００の２つの組み合わされたＷＣＶに対する貢献度が大きくなる。
【００６５】
図８に図示のように、ライン・サンプル８０３に沿うサンプルの重み付けに影響を与えるエッジへの考慮は“可視”エッジのみに限定するのが有効である。可視エッジ８０１は、(同じカラーからなる)別のポリゴンに(例えば該カラーの点で)一致しないポリゴンのエッジによって、あるいは塞ぎや交わりによって生成されるエッジである。同じカラーからなる２つのポリゴンが合わさった場合に生じるエッジ８０２は、作成された画像の中で目に見える可能性が少ない。したがって、エッジと交わるライン・サンプルの重み付けに該エッジが影響を与えないようにするために、このエッジ８０２は“非可視”のものとして処理したほうがよい。例えば、複数の隣接するポリゴンからなるオブジェクトは、結果に影響を与えるポリゴン間の内部エッジを持たないシルエット・エッジの方向に従ってアンチエイリアシングが行われる、オブジェクトのシルエット形成エッジを備えているほうがよい。
【００６６】
図９は、別のポリゴンｂ９０２を部分的に塞ぐポリゴンａ９０１を示す図である。ポリゴンａ９０１のエッジ９０３はポリゴンｂ９０２のエッジに一致することはない。エッジ９０３は不連続画像の中で可視であり、アンチエイリアシング計算に影響を与えるはずである。したがって、エッジ９０３を可視エッジとして処理し、ライン・サンプル９０４を用いてサンプルの重み付けの計算を行うほうがよい。
【００６７】
図１０の(ａ)は、オブジェクト１０００のエッジ１００３の近辺で２つの垂直な軸整列しているライン・サンプル１００１と１００２に対してどのように重み付けの測定を行うことができるかを示す図である。この図では、エッジ１００３の方向はライン・サンプル１００１−１００２のいずれにも垂直ではない。エッジ１００３に沿って進むベクトル計算を行うことができる。図１０の(ｂ)は、水平成分Ｖｘ１００５と垂直成分Ｖｙ１００６とを持つ、エッジ１００３についてのエッジ・ベクトル１００４を図示するものである。
【００６８】
この方法によって、ライン・サンプルのいずれかと交わる各可視エッジの正規化されたベクトル(Ｖｎｘ，Ｖｎｙ)がまず測定される。次いで、成分(Ｖｎｘ，Ｖｎｙ)を持つ正規化されたエッジ・ベクトルについて、垂直サンプルの総重み付けにＶｎｘ2を加算し、水平サンプルの総重み付けにＶｎｙ2を加算する。成分の値の二乗を用いて任意のエッジの貢献度の総和が１に等しく保たれる。関連するエッジの貢献度のすべてに重み付けが行われた後、垂直および水平のライン・サンプルの相対的重み付けを測定することができ、これらの相対的重み付けを用いて２つのライン・サンプルのＷＣＶのブレンディング(blending)が行われる。このブレンディングは１次ブレンディング関数、三次ブレンディング関数あるいはさらに大きな重み付けを行ったＷＣＶの選択のような任意の適切なブレンディング関数を利用することができる。
【００６９】
図１１の(ａ)に図示のように、従来型のラスタ化法を用いて２つの垂直な軸整列ライン・サンプルについてのライン・サンプル評価のスピード・アップを図ることが可能である。図１１の(ａ)では、ライン・サンプル１１０２と１１０３を持つ画素グリッド１１００の画素１１０１においてサンプリングを行うことが望ましい。一般に選択される、画素間の距離に等しい半径を持つアンチエイリアシング・フィルタを使用するとき、ポイント・サンプリングに現在利用される高速ラスタ化法を用いて、ちょうど画素グリッド位置上に在るライン・サンプルの端点１１０９におけるエッジ距離の値を生成することができる。１つのライン・サンプルの端点と１つのエッジのエッジ距離の値は、ライン・サンプルの端点とそのエッジ間の最短距離として定義される。
【００７０】
図１１の(ｂ)に図示のように、ライン・サンプル１１０２と１１０３を表すために“黒丸”の画素１１０４が用いられ“白丸”の画素１１０５は使用されない。Pineda算術を用いてライン・サンプルの端点における画像中のポリゴンについてエッジ距離の値を効率的に生成することができる。Pineda"ポリゴン・ラスタ化のための並列アルゴリズム”(ＳＩＧＧＲＡＰＨの会報、コンピュータ・グラフィックス、Ｖｏｌ．２２．  ＮＯ．４、ｐｐ．１７−２０、１９８８)を参照されたい。これらのエッジ距離の値は直線的に変動するので、ライン・サンプルの端点におけるエッジ距離の値のみが与えられれば、初等幾何学的方法あるいは代数的方法(例えば類似三角形)を用いて、ライン・サンプルのセグメントを効率的に生成することができる。セグメントは、エッジ距離の値がすべて正の場合ライン・サンプルの一部となる。
【００７１】
従来の走査線ラスタ化法を用いて、不連続画像中の画素の列と行全体についてライン・サンプルの生成を行うことができる。これらの手法を用いて連続画像全体にわたるライン上のすべての可視セグメントを生成することができる。次いで、画素のフィルタ・フットプリント内の可視セグメント部分を考慮することにより、連続画像全体にわたるラインと同じ方向で、１つの画素についてライン・サンプルが生成される。
【００７２】
下にある連続画像中のエッジに関する情報が分かっている場合には、正確な方向を持つ１画素当たりの単一ライン・サンプルで、その画像のサンプリングを行う画素のＷＣＶの適切な生成を行うのに十分である。その連続画像自体からエッジ情報を得ることができる。例えば図１２に図示のように、多くのオブジェクト１２００(フォントなど)を境界曲線１２０１によって指定することができる。曲線１２０３のタンジェント(正接:tangent)情報１２０２はこの曲線についての記述から計算することができる。ライン・サンプル１２０５はタンジェント１２０２の方向に対して垂直に方向づけられている。
【００７３】
図１３に示される代替方法では、連続画像１３０１から低い分解能のポイント・サンプル化画像１３０２が生成される。低い分解能の画像１３０２はエッジ情報１３０３を生成するエッジ検出オペレータで処理される。検出されたエッジ情報１３０３は適切なライン・サンプル１３０４の方向を示す。次いで適切に方向づけられたライン・サンプルがその連続画像に適用されてＷＣＶが生成され、このＷＣＶはアンチエイリアシングされた不連続画像１３０５を生成するために用いられる。
【００７４】
以上、いくつかの異なる応用例の推奨する実施の形態とその様々な改変例という点から本発明について説明してきたが、図面による上述の説明に基づいて、特に本発明の柔軟性と適応性を考慮すると本発明の範囲内で他の改変を行うことが可能であることは当業者には明白であろう。本発明の実際の範囲は以下の請求項に記載されている。
【００７５】
【発明の効果】
以上のようにこの発明によれば、フィルタ関数を用いて、１つのエッジを含む連続画像から生成される不連続画像のアンチエイリアシングを行うための方法であって、前記エッジに対して少なくとも前記フィルタ関数のフットプリントの範囲にわたる有限な長さを有する直線のライン・サンプルを定めるステップと、前記フィルタ関数と前記ライン・サンプルから前記エッジからの異なる複数の距離における前記フィルタ関数の累積積分である累進的畳み込みを導き出すステップと、前記不連続画像における所定位置で画素を選択するステップと、該選択された画素に関して前記ライン・サンプルの方向づけを行うステップと、前記選択された画素に対応する前記連続画像中の１点から前記方向づけられたライン・サンプルに沿って前記エッジまでの距離を測定するステップと、前記測定距離における累進的畳み込みを前記エッジとの距離と位置関係を評価して重み付きカバーレージ値を生成するステップと、前記重み付きカバーレージ値を前記画素と関連付けて前記不連続画像中の前記画素のアンチエイリアシングを行うステップと、を備えたことを特徴とするライン・サンプルによるアンチエイリアシング方法としたので、不連続画像の生成中、メモリの大幅な増加や描画速度の低下を伴わない改善されたアンチエイリアシング法が提供できる。
【図面の簡単な説明】
【図１】  この発明によるライン・サンプルによるアンチエイリアシング方法におけるグラフィックオブジェクトのエッジまでの様々な距離における画素の中心を通るライン・サンプルのフィルタ・フットプリントおよびフィルタ関数を示す図である。
【図２】  この発明における累進的畳み込みを示す図である。
【図３】  この発明における２つのエッジと交わるライン・サンプル、セグメント情報、累進的畳み込みの２つの評価値の差、２つのカバーレージ評価値間の差を示す図である。
【図４】  オブジェクトを塞ぐライン・サンプリングを示す図である。
【図５】  この発明におけるオブジェクトと交わるライン・サンプリングを示す図である。
【図６】  エッジに対して平行方向のライン・サンプルを示す図である。
【図７】  ２本の直交ライン・サンプルを使用するライン・サンプリングを示す図である。
【図８】  ライン・サンプルされた隣接オブジェクトの可視および非可視エッジを示す図である。
【図９】  ライン・サンプルされた相互に塞ぎあうオブジェクトの可視および非可視エッジを示す図である。
【図１０】  正規化されたエッジに従うライン・サンプリングを行うための重み付け用複数ライン・サンプルを示す図である。
【図１１】  画素グリッド位置におけるライン・サンプリング用データ生成を示す図である。
【図１２】  タンジェント方向に垂直な方向を持つ境界曲線のライン・サンプリングを示す図である。
【図１３】  低い分解能の画像とエッジ検出を用いるライン・サンプリングを示す図である。
【符号の説明】
１００，３０４、６０３，７０９，１１０１，１１０４，１１０５  画素、１０１，６０１，７０８，９０３，１００３  エッジ、１０２  フットプリント、１０３  フィルタ関数、１０４  グラフィック・オブジェクト、１０５，３０３，４０４，５０４、６００，７０１，７０２，８０３，９０４，１００１，１００２，１１０２，１１０３，１２０５，１３０４  ライン・サンプル、２００，３３０  累進的畳み込み(ＰＣ)、３００，６０２，７００，１０００，１２００オブジェクト、３０１  エッジａ、３０２  エッジｂ、３０９  フィルタ・フットプリント、３２０  セグメント、４０１，５０１，９０１  ポリゴンａ、４０２、５０２，９０２  ポリゴンｂ、４０３，５０３  サンプル・デプス情報(Ｚ)。
【図１】
0004597322.tif 000002
【図２】
0004597322.tif 000003
【図３】
0004597322.tif 000004
【図４】
0004597322.tif 000005
【図５】
0004597322.tif 000006
【図６】
0004597322.tif 000007
【図７】
0004597322.tif 000008
【図８】
0004597322.tif 000009
【図９】
0004597322.tif 000010
【図１０】
0004597322.tif 000011
【図１１】
0004597322.tif 000012
【図１２】
0004597322.tif 000013
【図１３】
0004597322.tif 000014