(57)【要約】コンピュータ化された画像処理において、特に画像合成に関してランク−１格子が使用されるシステムと技術が記載されている。これらには、ランク−１格子の選択のためのシステムと技術、ランク−１格子上でのラスタライゼーション、ランク−１格子によるアンチエイリアシング、およびランク−１格子による適応的改良およびフィルタ処理が含まれる。
2009501966.tif 000002
【特許請求の範囲】
【請求項１】
合成画像を生成するように作動可能であるデジタル処理システムにおいて、
その改良方法は、生成されるべき合成画像における点に対応する最大化した最小距離関数（ｍａｘ−ｍｉｎ−ｄｉｓｔ格子）に従ってランク−１格子を選択する段階、
前記選択されたランク−１格子に従って画素値を計算する段階、および、
前記計算された画素値に基づいて表示制御電子出力信号を生成することであって、前記電子出力信号は、ディスプレイスクリーン上で前記合成画像の表示を可能とするように作動可能である段階とを含む、改良方法。
【請求項２】
単位正方形上でｍａｘ−ｍｉｎ−ｄｉｓｔ格子を捜索し、数値積分のために得られた格子点を適用する段階をさらに備える、請求項１に記載の改良方法。
【請求項３】
領域サイズを補正するために２つのスケーリング係数によって、前記単位正方形に伴う平方ユークリッドノルムを修正する段階をさらに備える、請求項２に記載の改良方法。
【請求項４】
線形変換によって、前記単位正方形に伴う平方ユークリッドノルムを修正する段階をさらに備える、請求項２に記載の改良方法。
【請求項５】
重み付けしたノルムを利用する段階をさらに備える、請求項２に記載の改良方法。
【請求項６】
ディスプレイスクリーン全体に対応するサンプル画素へ格子を利用する段階をさらに備え、前記利用する段階が、所与のｍａｘ−ｍｉｎ−ｄｉｓｔ格子についての有効なシフトを決定する段階を備え、有効の場合は、前記シフトした格子について、ディスプレイスクリーンの区分ごとに等しい数の格子点が存在することを意味するように規定されている、請求項１に記載の改良方法。
【請求項７】
前記有効なシフトを決定する段階が、（１）全ての可能なシフトに関して反復し、画素あたりの格子点の数をカウントする段階、（２）前記カウントの１つが前記最初の画素における格子点の数と等しくない場合は、中止し、次の格子シフトに切り換える段階、および（３）有効なシフトが見つかった場合は停止する段階、を備える、請求項６に記載の改良方法。
【請求項８】
前記単位正方形上のｍａｘ−ｍｉｎ−ｄｉｓｔ格子を捜索する際に２次元のスペクトルテストを利用する段階をさらに備える、請求項２に記載の改良方法。
【請求項９】
２を超える次元におけるスペクトルテストに関して、ユークリッドステップを適用する段階をさらに備える、請求項８に記載の改良方法。
【請求項１０】
所定の基準に従って所与の格子についての基底を選択する段階をさらに備え、前記所定の基準は、前記基底ベクトルができるだけ短くなるように決定されている、請求項１に記載の改良方法。
【請求項１１】
前記基底を選択する段階が基底縮小法を利用する段階を備える、請求項１０に記載の改良方法。
【請求項１２】
前記基底を選択する段階が、２次元におけるミンコフスキー縮小基底を決定する段階を備える、請求項１１に記載の改良方法。
【請求項１３】
２次元におけるミンコフスキー縮小基底を決定する段階が、最短非ゼロ格子ベクトルを第１に決定し、前記第１に決定した最短非ゼロ格子ベクトルに一次独立である、次に短い格子ベクトルを次いで決定する段階を含む、請求項１２に記載の改良方法。
【請求項１４】
さらに、前記次に短いベクトルの距離が最大化される、請求項１３に記載の改良方法。
【請求項１５】
最大化した最小距離によって、２次元においてコロボフ格子を決定する段階をさらに備える、請求項１４に記載の改良方法。
【請求項１６】
ディスプレイスクリーンに対応する画素の行列からラスタ表示が形成されるコンピュータグラフィックスディスプレイシステムにおいて、ラスタライザが、仮想スクリーン空間における２次元頂点をディスプレイスクリーン上の画素へと変換するものであり、その改良方法は、格子点またはランク−１の最大化された最小距離（ｍａｘ−ｍｉｎ−ｄｉｓｔ）格子のセルの上で、ラスタライゼーションが実行され、かつ、
前記ラスタライゼーションが、直交座標における点ｐを前記ランク−１格子の基底に変換し、次いで前記変換された点に該当する格子セルを決定する段階を備え、それにより、前記直交座標を格子座標に変換する、改良方法。
【請求項１７】
ディスプレイスクリーンに対応する画素の行列からラスタ表示が形成されるコンピュータグラフィックスディスプレイシステムにおいて、ラスタライザが、仮想スクリーン空間における２次元頂点をディスプレイスクリーン上の画素へと変換するものであり、その改良方法は、格子点またはランク−１の最大化された最小距離（ｍａｘ−ｍｉｎ−ｄｉｓｔ）格子のセルの上で、ラスタライゼーションが実行される段階である、改良方法。
【請求項１８】
前記ラスタライゼーションが、線分の端点を形成する第１および第２の点のそれぞれについて、前記変換および決定し、次いでデジタル微分解析機（ＤＤＡ）を端点の格子座標に適用して、前記ランク−１格子における線分をラスタライズすることを実行する段階をさらに備える、請求項１６に記載の改良方法。
【請求項１９】
前記ラスタライゼーションが、前記ランク−１格子において、一式の頂点と辺によって与えられる凸多角形をラスタライズし、クロウのアルゴリズムを利用して前記多角形を充填する画素を決定し、クロウのアルゴリズムが、前記ランク−１格子の基底によって結合された座標系において実行されるようにする段階をさらに備える、請求項１８に記載の改良方法。
【請求項２０】
前記ラスタライゼーションが、線についてのブレゼンハムのアルゴリズム、および多角形についてのｙ−ｘラスタライゼーションアルゴリズムを利用し、その後、アンチエイリアシングする段階をさらに備え、前記アンチエイリアシングが、前記格子セルをその短い方の対角線に沿って２つの三角形に分割し、それにより解像度を２倍にする段階を備える、請求項１６に記載の改良方法。
【請求項２１】
最初に、従来のラスタライジングハードウェアの矩形格子のずれに対応して、合成されるべき情景を格子基底に変換し、その後、ラスタライゼーションが従来通りグラフィックスハードウェア上で実行され、その後前記ラスタライズされた情景を表示するため、前記得られた画像が、前記画素基底へと戻して変換される、請求項１６に記載の改良方法。
【請求項２２】
前記表示が格子セルの行列として表され、単一の画像要素がランク−１格子点のドロネー三角形分割によって生じたセルとして表される、請求項１６に記載の改良方法。
【請求項２３】
前記表示が格子セルの行列として表され、単一画像要素がボロノイセルによって生じたセルとして表される、請求項１６に記載の改良方法。
【請求項２４】
前記ラスタ表示が、最大化した最小距離によって選択されたランク−１格子として表される、請求項２２に記載の改良方法。
【請求項２５】
前記ディスプレイスクリーンが、各格子セルの中央に配列された複数の点光源を備え、前記ランク−１格子が最大最小距離によって選択される、請求項２４に記載の改良方法。
【請求項２６】
前記ディスプレイスクリーンが、多数の画像要素をカバーする複数の面光源を備える、請求項２５に記載の改良方法。
【請求項２７】
複数の面光源を備えるディスプレイスクリーンの解像度が、前記格子セルをその短い方の対角線に沿って分割することにより増加し、それにより、エイリアシングアーチファクトを減少させる、請求項２６に記載の改良方法。
【請求項２８】
ボロノイ図を利用して、セルを各格子点を中心とする実質的に６角形のセルに仕切る段階をさらに備える、請求項２７に記載の改良方法。
【請求項２９】
複数の感光センサー素子を有するデジタルカメラにおいて、その改良方法は、
前記感光センサー素子が、ドロネー三角形分割またはボロノイ図のいずれかによって生じたランク−１格子セルレイアウトに従って配列されることである、改良方法。
【請求項３０】
複数の光生成または光反射素子を有するデジタルプロジェクタにおいて、その改良方法は、
前記光生成または光反射素子が、ドロネー三角形分割またはボロノイ図のいずれかによって生じたランク−１格子セルレイアウトに従って配列される段階である、改良方法。
【請求項３１】
複数の光生成または光反射素子を有する３次元ディスプレイシステムにおいて、この改良方法は、
前記光生成または光反射素子が、ドロネー三角形分割またはボロノイ図のいずれかによって生じたランク−１格子セルレイアウトに従って配列されることである、改良方法。
【請求項３２】
画像要素（画素）を有するディスプレイデバイスにおいて、その改良方法は、
前記画素が少なくとも１つのランク−１格子に従って配列されることである、改良方法。
【請求項３３】
画像要素（画素）を有するディスプレイデバイスにおいて、その改良方法は、
前記画素が、それぞれが同数の格子セルを有するｋモジュールのディスプレイを備えるタイル張りしたランク−１格子に従って配列され、かつ、
各ディスプレイモジュールについての前記セルの数が、２のべき乗として選択されることで、単一のセルが、デマルチプレクサによってアドレス指定されることができ、かつ、
モジュールの数ｋが、２のべき乗として選択されることで、単一のモジュールが、デマルチプレクサによってアドレス指定されることができることである、改良方法。
【請求項３４】
前記ディスプレイデバイスが、２ｎ−基底の画像を生成および格納するための２ｎディスプレイデバイスとして構成され、画像のテクスチャの手順が格納されることができ、各テクスチャが、２のべき乗であるように選択された画像の数を表す段階を更に含む、請求項３３に記載の改良方法。
【請求項３５】
複数の感光性の、光生成または光反射素子を有するデジタル画像デバイスまたはディスプレイデバイスにおいて、その改良方法は、
前記感光性の、光生成または光反射素子が、ランク−１格子、ランク−１格子のボロノイ図のドロネー三角形分割、のサンプルによって生じた選択されたレイアウトに従って配列されることである、改良方法。
【請求項３６】
最大−最小距離関数に従ってレイアウトを選択する段階をさらに備える、請求項３５に記載の改良方法。
【請求項３７】
重み付けした最大−最小距離関数を利用して、レイアウトを選択する段階をさらに備える、請求項３５に記載の改良方法。
【請求項３８】
ＭＩＰマップを利用してレイアウトを選択する段階をさらに備える、請求項３５に記載の改良方法。
【請求項３９】
ランク−１格子上で画像ピラミッドを利用してレイアウトを選択する段階をさらに備える、請求項３５に記載の改良方法。
【請求項４０】
ランク−１格子を使用してアンチエイリアシング関数を適用し、仮想の無限大チェッカーボードをレンダリングする設定の中で、最大最小距離格子を、モンテカルロまたは準モンテカルロ点集合へのそれらの収束について比較する段階をさらに備える、請求項１に記載の改善。
【請求項４１】
ランク−１格子を使用してアンチエイリアシング関数を適用する段階をさらに備える、請求項１に記載の改良方法。
【請求項４２】
画像を合成するためのコンピュータグラフィックスシステムにおいて、この改良方法は、
ランク−１格子を利用してアンチエイリアシング法を適用し、前記アンチエイリアシング法が、ランク−１格子による適応的改良を備える段階であって、前記アンチエイリアシング法は、
第一に、対応する信号を初期サンプリングパターンによって低解像度でサンプリングし、ここで前記初期サンプリングパターンが、ディスプレイスクリーン全体にスケーリングされた選択された最大最小距離ランク−１格子を備える段階、
前記初期サンプリングパターンを使用して、レンダリングされるべき画像の初期近似を計算する段階、
サンプリング点が改良される必要があり得る画像の各画素についての改良テストを評価し、前記評価が、各格子点について改良基準を評価する段階を備えることで、前記改良基準が前記格子基底において評価される段階、
および、その後、所定の基準に従って前記サンプリングパターンを適応的に改良する段階を備える、改良方法。
【請求項４３】
前記画像の初期近似が、格子点バッファにおいて計算され、かつ、前記改良パターンが、前記初期サンプルパターンの格子セル構造を利用して、第２の最大最小距離ランク−１格子として選択され、さらに、
前記改良パターンが、任意のサンプリング点ｘ１に対応する前記格子セル｛ｘ１＋Λ｝内で最大最小ランク−１格子Ｌ（ｍ，ａ）を決定することによって認識され、前記第２のランク−１格子が、ずれた基底の格子Ｌ（ｍ，ａ）において決定される、請求項４２に記載の改良方法。
【請求項４４】
パラメータが初期化法によってあらかじめ計算されている、前記初期サンプリングパターン、スクリーン解像度にスケーリングされていない前記初期ｍａｘ−ｍｉｎ−ｄｉｓｔ格子、および前記改良パターンを、入力引数として利用する段階、
その後、前記初期サンプリングパターンの各点についての第１の反復において、仮想の光線を情景に発射することによって、点バッファにおける強度値を格納する段階、
その後、各サンプリング点についての第２の反復において、前記選択された改良基準を評価し、得られた値が所定の閾値を超える場合は新たなサンプルを生成し、これらのサンプルを前記初期サンプリングパターンのコピーに加える段階、
その後、前記初期最大最小距離ランク−１格子の全ての点に関して反復した後、前記改良したサンプリングパターンが使用されて、画像空間中の最終画像が算出される段階を備え、第１のレベルの改良を実行する段階をさらに備える、請求項４２に記載の改良方法。
【請求項４５】
前記選択された改良基準を評価する段階が、前記改良ジオメトリに属する点の値に、点バッファからそのｘ座標を介してアクセスする段階を備え、その後、局所変動、ｓｕｐ／ｉｎｆ、および階調基準を適用する、請求項４４に記載の改良方法。
【請求項４６】
画像において複数の各画素のそれぞれについて各画素値を生成することによって合成画像を生成するためのコンピュータグラフィックスシステムにおいて、前記画素値が、仮想カメラの画像面に記録された情景における点を表すものであり、前記コンピュータグラフィックスシステムが、一式のサンプリング点を生成するように構成されたサンプリング点生成器を備え、前記コンピュータグラフィックスシステムが、仮想カメラの画像面の各画素からシミュレートされた光線が発射される選択されたレイトレーシング法を使用して、画像についての前記画素値を生成するように構成されており、この改良方法は、
生成されるべき前記合成画像における点に対応する最大化した最小距離関数（ｍａｘ−ｍｉｎ−ｄｉｓｔ格子）に従ってランク−１格子を選択する段階、
前記選択されたランク−１格子に従って画素値を計算する段階、および、
前記計算された画素値に基づいて、表示制御電子出力信号を生成する段階を備え、ここで、前記電子出力信号が、前記合成画像の表示を可能とするように作動可能であり、
ここで、前記選択されたランク−１格子に従って選択されたサンプリングパターンが、もとにある関数に対してフィルタ処理効果を有することにより、高周波が除去されて、エイリアシングアーチファクトが弱められる、改良方法。
【請求項４７】
前記選択されたランク−１格子に従って前記画素値を計算する段階が前記サンプリング点の使用を含み、
前記表示制御電子出力信号の生成が再構成フィルタの使用を含み、さらに、
各サンプリング点について、前記仮想カメラから前記情景中の表面に前記光線が衝突する点までの前記光線の長さに依存して再構成フィルタを選択し、異方性で深度適応的なフィルタ処理を可能とする段階、および、
Ｂ−スプライン再構成フィルタを利用する段階をさらに備える、請求項４６に記載の改良方法。
【請求項４８】
Ｂ−スプライン再構成フィルタを利用する段階が、連続するＢ−スプラインフィルタ間の補間をさらに備えることでフィルタカーネル間の滑らかな遷移を提供する、請求項４７に記載の改良方法。
【請求項４９】
前記表示制御電子出力信号の生成が、異なる色の多数の副画素を備えるディスプレイデバイス上で画像の表示を制御するように適合していることで、３倍の水平表示解像度を可能とし、かつ、
前記選択されたランク−１格子に従った画素値の計算が、副画素ベースのフィルタ処理法を適用することを備えて個別の副画素の輝度値を選択し、前記フィルタ処理法が、重み付けしたノルムを利用することを備えることで前記ディスプレイデバイスを３倍の水平解像度に補正し、前記フィルタ処理法が、さらに、
重み付けした色値を蓄積するためのアキュムレーションバッファ、および前記フィルタ重みを蓄積するための付加バッファを使用する段階を備え、ここで両方のバッファが、前記３倍の水平解像度で初期化される、請求項４８に記載の改良方法。
【請求項５０】
合成画像を生成するように作動可能なデジタル処理システムにおいて、この改良方法は、
生成されるべき前記合成画像における点に対応する最大化した最小距離関数（ｍａｘ−ｍｉｎ−ｄｉｓｔ格子）に従ってランク−１格子を選択する段階、
前記選択されたランク−１格子に従って画素値を計算する段階、
前記選択されたランク−１格子によって規定されたラスタライゼーションスキームに従って、生成されるべき合成画像のための画素レイアウトを構成することであって、前記格子点の数が２のべき乗であるように選択される段階、および、
前記計算された画素値に基づいて、表示制御電子出力信号を生成することであって、前記電子出力信号が、前記合成画像の表示を可能とするように作動可能である段階を備える、改良方法。
【請求項５１】
合成画像を生成するように作動可能であるデジタル処理システムにおいて、
生成されるべき前記合成画像の点に対応して、最大化した最小距離関数（ｍａｘ−ｍｉｎ−ｄｉｓｔ格子）に従ってランク−１格子を選択する工程と、
前記選択されたランク−１格子に従って画素値を計算する工程と、
前記選択されたランク−１格子によって規定されたラスタライゼーションスキームに従って、生成されるべき合成画像のための画素レイアウトを構成する工程であって、前記格子点の数が、２のべき乗であるとして選択される工程と、
前記計算された画素値に基づいて、表示制御電子出力信号を生成する工程であって、ここで前記電子出力信号が、前記合成画像の表示を可能とするように作動可能である工程と、
を備える表示制御信号生成方法。
【請求項５２】
合成画像の生成を可能とするように適合されたデジタル処理システムにおいて作動可能であるソフトウェアコード製品であって、前記デジタル処理システムを可能として表示制御信号を生成するために、前記ソフトウェアコード製品が、デジタル記憶媒体に収容されており、
生成されるべき合成画像の点に対応して、最大化した最小距離関数（ｍａｘ−ｍｉｎ−ｄｉｓｔ格子）に従ってランク−１格子を選択するための第１のソフトウェアコード手段と、
前記選択されたランク−１格子に従って画素値を計算するための第２のソフトウェアコード手段と、
前記選択されたランク−１格子によって規定されたラスタライゼーションスキームに従って、生成されるべき合成画像のための画素レイアウトを構成するための第３のソフトウェアコード手段であって、ここで前記格子点の数が２のべき乗であるとして選択される手段と、
前記計算された画素値に基づいて表示制御電子出力信号を生成するための第４のソフトウェアコード手段であって、ここで前記電子出力信号が前記合成画像の表示を可能とするように作動可能である手段とを備えるソフトウェアコード製品。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
本出願は、２００５年６月２３日出願の米国仮特許出願第６０／６９３，２３２号の利益を主張し、その全体が参照によって本明細書に一体化される。
【０００２】
コンピュータプログラム付属書への参照
ソースコードリストを本明細書と共に提出する。その全体が本明細書に一体化されている。ソースコードリストは、本明細書中「付属書」と呼び、「１．１．１」や「１．１．１．１」の形式の参照番号で確認される章にまとめている。
【０００３】
技術分野
本発明は、概ね、動画および他の用途のための、デジタル演算システムにおける、およびデジタル演算システムによる画像合成のための方法とシステムに関し、特に、ランク−１格子による画像合成のための方法、システム、機器、コンピュータソフトウェア、およびディスプレイ技術に関する。
【背景技術】
【０００４】
先行技術の説明
画像合成の使用は、動画ならびに他の商業的および科学的用途においてますます重要かつ広範になってきた。合成画像は、通常、画像要素すなわち画素と呼ばれる２次元配列のデジタル値を表す。従って、２次元の関数と通常みなされている。
【０００５】
画像合成は、情景から合成画像を作製するプロセスである。一般事項として、デジタル画像は、ラスタライゼーションによって生成される。また、３次元情景の写実的画像の場合は、レイトレーシングによって生成される。両方のアプローチは、元の関数を画素基底へと投影することで各画素について適切な色を決定することを目的とする。元の関数が離散した表現であることによって、以下記載のようにエイリアシングという問題が生じる。
【０００６】
特に、単一の画素の強度を算出するには、画素領域上で積分関数を必要とする。この積分は、しばしば非常に複雑で解析的に解くことができないため、解に対して数値的手法が必要である。そのような手法には、モンテカルロ法および準モンテカルロ法が含まれ得る。しかし、このような用途に使用される通常の数値的手法には、それ自体の制限と付随する問題とがある。
【０００７】
コンピュータグラフィックスに使用される他の演算的アプローチは、格子理論である。例えば、コンピュータグラフィックスに通常使用されるアキュミュレーションバッファは、レギュラーグリッドの構造を利用している。さらに、効率的なラスタライゼーション法は、このようなグリッドを利用して設計されてきた。特定の公知のサンプリング法は、フィボナッチ格子を採用しており、これはランク−１格子のタイプである。
【０００８】
迅速および効率的に生成され得て、画像合成および他のコンピュータグラフィックス用途の要請に容易に適合するランク−１格子を使用する方法、システム、機器、およびコンピュータソフトウェアを提供することが所望される。
【０００９】
アンチエイリアシング、ラスタライゼーション、および他のコンピュータグラフィックス機能に、ランク−１格子の効率的な適用を可能とする方法、システム、機器、およびソフトウェアを提供することも所望される。
【００１０】
発明の要旨
発明の局面は、特に画像合成の関連において、コンピュータ化された画像処理においてランク−１格子が使用される多くの技術を提供する。
【００１１】
発明の第一の局面は、画像合成に使用するランク−１格子を選択するために使用される技術に関する。多くの格子選択技術を記載し、その中には、最大化した最小距離によって２次元におけるコロボフ格子を捜索する技術が含まれ、準モンテカルロ理論で使用される
2009501966.tif 000003
−一様点集合の意味での最大限の一様性をそれにより達成している。さらに記載しているのは、格子基底の捜索のための技術、およびシフトしたランク−１格子の（ｔ，ｍ，ｓ）−ｎｅｔｓ（ネット）への関係を解析するための技術である。
【００１２】
発明の別の局面は、ランク−１格子を使用して画像画素レイアウトを構成し、ラスタライゼーションスキームのベースとして画素レイアウトを使用するための技術を提供する。記載したラスタライゼーションスキームは、従来のラスタディスプレイを使用して実行され得る。さらに、ランク−１格子の構成を直接利用するラスタライゼーションスキームに基づく新たなディスプレイ技術を本明細書に記載する。
【００１３】
発明の別の局面は、ランク−１格子によるアンチエイリアシングのための技術を提供する。そこでは他のモンテカルロおよび準モンテカルロ点集合への収束に関して最大最小距離格子が比較される。エイリアシングの問題は、画素によって変わる。従って、発明の局面の記載には、ランク−１格子による適応的改良が含まれる。さらに、レイトレーシング環境における深度適応的フィルタ処理用スキームを記載している。
【００１４】
詳細な説明
本発明は、動画の表示または他の動的表示のため等の画像の、ランク−１格子を使用する画像の生成と合成に関する。本明細書中に記載の技術は、画像中の各画素について画素値が生成されるコンピュータグラフィックスシステムの一部として実施される。画素値は、シミュレートしたカメラの画面上に記録された情景における点を表す。コンピュータグラフィックスシステムは、選択された方法を使用して、画像についての画素値を生成するように構成されている。
【００１５】
次の検討では、そのような技術に従った方法、構成、システム、および表示技術を記載する。記載の方法とシステムが、独立構成で、またはネットワークを介して、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）、Ｌｉｎｕｘ、またはＵｎｉｘ（登録商標）のような通常のオペレーティングシステムに従って動作（またはエミュレート）するパーソナルコンピュータ（ＰＣ）や、同等の機器のような通常のコンピュータ装置を使用して、ソフトウェア、ハードウェア、または、ソフトウェアとハードウェアの組み合わせにおいて実施され得るということが当業者によって理解されよう。従って、以下および特許請求の範囲に記載の種々の処理手段および演算手段は、ソフトウェアおよび／あるいは、適切に構成されたデジタル処理機器または機器のネットワークのハードウェア要素において実施されることができる。処理は、特別用途のハードウェアまたは再構成可能なハードウェアを使用して、逐次にまたは並列的に実行されることが可能である。
【００１６】
発明に従った方法、機器、またはソフトウェア製品、図１に例示で図示するものなど（例えばネットワークシステム１００）は、単独型、ネットワーク型であろうと、通常のＰＣ１０２、ラップトップ１０４、ハンドヘルドコンピュータまたはモバイルコンピュータ１０６を含む携帯型または固定型であろうと、あるいはサーバー１１０およびストレージ１１２を含むこととなり得るインターネットまたは他のネットワーク１０８を介しようと、いずれかの広範な通常の演算機器およびシステム上で動作することができる。
【００１７】
通常のコンピュータソフトウェアおよびハードウェア実務に照らして、発明に従って構成されたソフトウェアアプリケーションが、例えば図２に示すようなＰＣ１０２の内部で動作することができる。ここでプログラム指令は、ＣＤＲＯＭ１１６、磁気ディスク、または他のストレージ１２０から読み取られて、ＲＡＭ１１４にロードされ、ＣＰＵ１１８によって実行されることが可能である。通常のキーボード、スキャナ、マウス、または他の要素１０３を含む何らかの公知の機器または手段によって、データはシステムに入力されることが可能である。
【００１８】
本検討は、次のセクションに分けられる。
１．導入
２．ランク−１格子の選択
３．ランク−１格子上のラスタライゼーション
４．ランク−１格子によるアンチエイリアシング
５．ランク−１格子による適用的改良とフィルタ処理
６．結論
【００１９】
このようなセクション見出しは、次の検討の体系付けと明瞭性を提供するために使用されることに言及しておく。発明の範囲を規定または別に限定するような見出しの使用は意図していない。
【００２０】
１．導入
合成画像とは、画像要素すなわち「画素」と呼ばれ、それによって２次元の関数とみなされ得る２次元配列のデジタル値を意味する。本明細書で使用される用語「画像合成」は、情景から合成画像を作製するプロセスを意味する。
【００２１】
一般に、デジタル画像は、「ラスタライゼーション」として公知のプロセスによって生成される。または３次元情景の写実的画像の場合は、「レイトレーシング」として公知のプロセスによって生成される。両方のアプローチは、元の関数を画素基底へと投影することで各画素について適切な色を決定することを目的とする。元の関数が離散した表現であることによって、以下記載のようにエイリアシングという問題が生じる。
【００２２】
単一の画素Ｐの強度Ｉ（ｘ）の算出には、画素領域に関する次の積分が必要となる。
2009501966.tif 000004
【００２３】
典型的には、この積分は非常に複雑であり、解析的に解くことができない。従って、数値的手法が使用されなければならない。積分は、不連続である可能性が非常に高いため、標準的なテンソル積求積法は、特に高次元において功を奏しない。元の関数の平方積分性（ｓｑｕａｒｅ  ｉｎｔｅｇｒａｂｉｌｉｔｙ）によって、このような積分をいわゆる「モンテカルロ法」を用いて次元とは無関係に算出することができる。このアプローチは、積分
2009501966.tif 000005
を概算するための確率理論を使用する。ここで、Ｉｓ＝［０，１）Ｓは、ｓ次元単位立方体を表す。上記の積分の推定は、確率変数Ｙの構築に基づく。確率変数Ｙは、いわゆる「推定量」と言われ、その期待値
2009501966.tif 000006
は、所望の積分に対応する。なんらかの確率変数Ｘについて、
確率密度関数
2009501966.tif 000007
として
2009501966.tif 000008
を選択することで、所望の結果として、
2009501966.tif 000009
が得られる。ｎの独立同一確率分布の（ｉ．ｉ．ｄ．）変数Ｙｉを考慮すると、中心極限定理によれば、総和
2009501966.tif 000010
が、大きいｎについて分布した
2009501966.tif 000011
に漸近的になるとする。すると、３σ則
2009501966.tif 000012
は、積分１．２についての計算方法を
2009501966.tif 000013
によって提供する。
このことは、モンテカルロ法が、ランダムサンプリングと平均によって数値積分を実行することを意味する。３σ則によれば、近似誤差は、
2009501966.tif 000014
未満であり、大きいｎついては高確率で、収束率は
2009501966.tif 000015
である。
ｔＹをＹの1つの実現（ｒｅａｌｉｚａｔｉｏｎ）ｙｉについてされた時間とする。モンテカルロアルゴリズムの計算コスト
2009501966.tif 000016
が、推定量の分散に依存するので、主要部の分離や、または効率を向上するためのジッタ処理等の様々な分散低減法が存在する。被積分関数の滑らかさまたは次元についての仮定が無いため、モンテカルロアルゴリズムは、標準的なテンソル積求積法の問題を克服する。しかし、この方法は、遅い収束のみを有し、コンピュータ上で実数の乱数がどのようにしても存在しない。モンテカルロ法の誤差限界について重要なサンプリング点の独立は、収束のためには必要ではないという事実を、準モンテカルロ法は利用する。その代わり、サンプリングパターンの一様な分布は重要な要因を表す。独立性、予測不可能性、および一様性が、単位区間上の実数乱数についての特性である一方、いわゆる準モンテカルロ点は、最初の２つの特性を放棄することによって決定論的に生成される。このような決定論的点は、実数乱数について可能なものよりはるかに一様である。このような構成の例は、ハマーズリー点集合または（ｔ，ｍ，ｓ）−ｎｅｔｓであり、これらは、以下に記載のように根基反転とランク−１格子に基づいている。
【００２４】
このような点集合は、単位立方体を一様に区分するという特性を共に有する。このような一様性は、次のように数式化されてきた。
定義１
2009501966.tif 000017
を任意の確率空間とし、
2009501966.tif 000018
を
2009501966.tif 000019
の空ではない部分集合とする。
2009501966.tif 000020
の場合、Ｘのｎ要素の点集合Ｐｎは、
2009501966.tif 000021
−一様と呼ばれる。
ここで、
2009501966.tif 000022
の場合は、
2009501966.tif 000023
であり、他の場合はゼロである。
既知の
2009501966.tif 000024
−一様な点集合の例には、根基反転ベース、デカルト積中点法からの点、およびランク−１格子が含まれる。確率空間
2009501966.tif 000025
を使用して、この定義は、コンピュータグラフィックスについても適用される。ここで、
2009501966.tif 000026
は、ボレル集合に対応し、λｓは、ｓ次元ルベーグ測度に対応する。
【００２５】
準モンテカルロ法は、原理的には、モンテカルロ法に似ているように見えるが、数値積分についての決定論的点を使用する。このことは、積分１．２が次の
2009501966.tif 000027
ように近似していることを意味する。
2009501966.tif 000028
−一様性によって、Ｌ２上の決定論的誤差限界は、次のように得ることができる。
定理１
2009501966.tif 000029
を任意の確率空間とし、
2009501966.tif 000030
をＸの区分とし、ここで
2009501966.tif 000031
について
2009501966.tif 000032
であるとする。すると、任意の
2009501966.tif 000033
−一様点集合
2009501966.tif 000034
およびＸ上の任意の関数ｆについて、
2009501966.tif 000035
を得る。
【００２６】
上記の検討は、単一の画素の強度に適用される。同時に全画素を算出すること
2009501966.tif 000036
は、積分近似問題であり、典型的には、パラメータ積分へと一般化することで対処されている。確率場についてのモンテカルロ法の一般化によって、いわゆる「従属（ｄｅｐｅｎｄｅｎｔ）テストの方法」がもたらされる。全体の関数は、次のように推定され、
2009501966.tif 000037
計算上のコストは、
2009501966.tif 000038
である。準モンテカルロ法を考慮すると、定理１は、パラメータ積分へと一般化されてきた。
定理２
2009501966.tif 000039
を任意の確率空間とし、
2009501966.tif 000040
をＸの区分とし、ここで
2009501966.tif 000041
について
2009501966.tif 000042
であるとする。すると、任意の
2009501966.tif 000043
−一様点集合
2009501966.tif 000044
およびＸ上の任意の関数ｆについて、
2009501966.tif 000045
を得る。
格子Ｌは、
2009501966.tif 000046
における離散部分集合である。
2009501966.tif 000047
これは、加法と減法のもとで閉じている。例えば、規則的な軸平行グリッドは、１つのタイプの単純な格子を表す。
2009501966.tif 000048
における各格子（ｌａｔｔｉｃｅ）は、
2009501966.tif 000049
として、
2009501966.tif 000050
の全整数一次結合を考慮することで、一式の一次独立ベクトル
2009501966.tif 000051
から生成されることが可能である。
2009501966.tif 000052
ベクトル
2009501966.tif 000053
は、格子の１つの基底である。これらは格子を生成するので、生成作用素ベクトルとも言われている。基底ベクトルの数ｓからＬの次元が得られる。
【００２７】
基底の行列式の絶対値は、正確に言えば、列ベクトルが
2009501966.tif 000054
によって形成されている「生成作用素」行列Ｂは、ｓ次元の体積の基本平行六面体に対応し、
2009501966.tif 000055
これは、基底ベクトルと原点によって結合されている。基本平行六面体
2009501966.tif 000056
によって、同じ体積かつ方向の格子セルへと分割され得る。
2009501966.tif 000057
基底は、特定の格子について固有ではないが、その行列式
2009501966.tif 000058
は、不変量を表す。これは、対応する基底行列の行列式が格子行列式に等しい場合、一式の一次独立ベクトルは、格子Ｌを生成することを意味する。
【００２８】
列ベクトル（Ｂ−１）Ｔは、双対（ｄｕａｌ）または極性（ｐｏｌａｒ）格子Ｌの基底を構築する。これは、
2009501966.tif 000059
によって定義される。
2009501966.tif 000060
の行列式は、Ｌの行列式の逆数から現れる。次の双対格子
2009501966.tif 000061
の解釈は、以下に記載のスペクトルテストに有用である。双対格子
2009501966.tif 000062
における各点ｈは、以下の特性を保持するように一式の（ｓ−１）次元の超平面
2009501966.tif 000063
を規定する。Ｌにおける各点は超平面の１つの上に存在し、各超平面は、Ｌの少なくとも１つの点を含み、このような超平面は平行であって等距離であり、そのような距離は、
2009501966.tif 000064
に等しい、という特性である。
図３Ａは、双対格子点
2009501966.tif 000065
の一群の超平面を含むフィボナッチ格子２００を示し、図３Ｂは、その双対格子２１０を示す。
【００２９】
格子理論における典型的な問題は、以下に記載する最接近点問題および最短ベクトル問題である。最接近問題は、例えば、変調と量子化の両方に格子が適用される通信理論において生じる。最短ベクトル問題は、例えば、乱数生成作用素の質を評価するために使用されてきた。この問題の他の応用は暗号化において見られる。以下に記載の別の問題は、格子規定縮小および格子基底について関連する捜索という問題である。他の格子問題には、接吻数を決定することまたはボロノイ関連（Ｖｏｒｏｎｏｉ−ｒｅｌｅｖａｎｔ）ベクトルを見つけることが含まれる。
【００３０】
２．画像合成に使用するランク−１格子の選択
本発明の局面は、画像合成においてランク−１格子を使用する技術を提供する。図４は、本発明に従った方法２２０を図示するフローチャートである。工程２２１において、生成されるべき合成画像の画素に対応する最大化した最小距離関数に応じて、ランク−１格子が選択される。工程２２２において、選択されたランク−１格子に応じて画素値が計算される。工程２２３において、計算された画素値に基づいて、表示制御電子出力信号が生成される。
【００３１】
次に、特にランク−１格子を選択するための技術について格子を詳細に説明する。そのような技術には、最大化した最小距離による２次元コロボフ格子の捜索のための技術が含まれ、これにより、
2009501966.tif 000066
−一様点集合という意味での最大の一様性を達成している。
【００３２】
本明細書に記載の発明の別の局面に従ったランク−１格子の応用の中には、「格子基底」、すなわち、選択されたランク−１格子によって規定された部分空間を生成し得る一式の一次独立のベクトルを必要とするものもある。従って次の検討には、格子基底の捜索のための技術が含まれる。さらに、シフトしたランク−１格子（ｓｈｉｆｔｅｄ  ｒａｎｋ−１  ｌａｔｔｉｃｅ）の（ｔ，ｍ，ｓ）−ｎｅｔｓとの関連を分析している。
【００３３】
2009501966.tif 000067
における格子Ｌの「ランク」は、Ｌを生成するために必要なベクトルの最小数と規定される。１つだけのｓ次元生成作用素ベクトル
2009501966.tif 000068
を仮定すると、
2009501966.tif 000069
は、ｓ次元格子を記載する。このようにして、この格子は「ランク−１−格子」として既知である。
【００３４】
「コロボフ格子」は、ｓ次元ランク−１格子の一例を提供する。その生成作用素ベクトルは、形態
2009501966.tif 000070
を有している。ｎは点の数であり、コロボフ格子が、タプル（ｎ，ａ）すなわち
2009501966.tif 000071
によって一意的に決定されるということである。
それによって、ｍｏｄ１演算は、1周期パターンとなる単位正方形へ格子を制限する。このことは、ランク−１格子が原点に対象な点であることを意味する。このような格子の１つの利点は、ｓ次元空間を充填するため継ぎ目無くタイル張りされることが可能な点、および非常に迅速に生成され得る点である。
【００３５】
２次元コロボフ格子を表す「フィボナッチ格子」は、ランク−１格子の別の例である。フィボナッチ数列Ｆｋ：＝Ｆｋ−１＋Ｆｋ−２、Ｆ２：＝Ｆ１：＝１とする、に基づいて、点の数が、
2009501966.tif 000072
と設定され、生成作用素ベクトルがｇ＝（１，Ｆｋ−１）と規定される。
【００３６】
図５は、ｎ＝Ｆ９＝３４点および生成作用素ベクトル
2009501966.tif 000073
を有する単位正方形上のフィボナッチ格子２３０を示す。ランク−１格子の質は、整数生成作用素ベクトル
2009501966.tif 000074
によって大きく影響される。コロボフ形態の格子は、２次元の他の格子とあまり異ならないが、生成作用素ベクトルの選択を１つのパラメータへ減少させる。そのため、このような格子は、所定の特性を有する２次元格子についての捜索に関する本検討において特に興味深い。
【００３７】
以下に詳細に記載するように、ランク−１格子は、アンチエイリアシングおよびラスタライゼーションに関連して適用される。本検討は、どういう種類のランク−１格子を使用すべきかに関しての問題を扱う。
【００３８】
ランク−１格子の生成作用素ベクトル
2009501966.tif 000075
は、得られる点集合が低食い違いであるように選択され得る。その場合、この点集合の成分は、「優良格子点」と呼ばれる。例えば、ｓ＝２についてのフィボナッチ格子、およびその生成作用素ベクトルがコロボフ形態である格子は低食い違いのものである。しかし、優良格子点についての明白な構成はほとんど存在しない。
【００３９】
上述のように、ランク−１格子は、
2009501966.tif 000076
−一様な点集合である。ランク−１格子のこのような特性は、基本平行六面体によって生じたＩｓの区分
2009501966.tif 000077
を考慮することによって理解が可能である。この意味においての最大一様性は、全サンプル点Ｐｎ間で、相互の最小距離
（数７５）
2009501966.tif 000078
を最大化することによって達成され得る。それによって、単位円環面上でユークリッドノルムが計算される。
【００４０】
従って、ランク−１格子は、いわゆる「ｍａｘ−ｍｉｎ−ｄｉｓｔ−特性」を特徴とし、本明細書中コロボフ形態
2009501966.tif 000079
で使用されており、捜索によって特定される。コロボフ形態の格子は、タプル（ｎ，ａ）によって一意的に決定されるため、このことは、固定した数の点ｎについての捜索が、２つの格子点間の最小距離が単位円環上で最大に達するような
2009501966.tif 000080
について行われることを意味する。２つの格子点間の最小距離が増大するにつれ、得られる格子は、六方格子にさらに近づき、それによって、点集合の一様な分布が増加する。
【００４１】
図６Ａは、ａ＝８かつｎ＝１であるＬ（８，１）についてのコロボフ格子２４０を示す。図６Ｂは、ａ＝８かつｎ＝５であるＬ（８，５）についてのコロボフ格子２５０を示す。図６Ａ格子２４０について、点は、単位正方形の対角線上に存在する一方で、図６Ｂ格子２４０に示すｍａｘ−ｍｉｎ−ｄｉｓｔ格子の点は、さらに一様に分布している。
【００４２】
２つの格子点間の最小距離を計算するタスクは、格子理論の周知の問題に関連している。「最接近点問題」は、所与の格子Ｌおよび所与の入力点
2009501966.tif 000081
について
2009501966.tif 000082
となるようなベクトル
2009501966.tif 000083
を見つけることにある。
格子Ｌにおける最小距離を計算することは、最接近点問題の簡単な修正によって達成され得る、Ｌにおける最短ベクトルの決定に対応する。そのため、ベクトルｖ≠０のみが考慮される。そして、原点に対する最接近点が、最短ベクトルすなわちＬにおける最小距離を生じる。最接近点捜索法は、規則的構造を有しない格子について文献中に記載されてきた。しかし、ランク−１格子が特別な構造を提供し、低次元について考慮されるだけであるため、そこに存在する方法はランク−１格子に対しては適切ではない。以下の検討において、周期的かつ規則的構造およびこのような格子の適用の両方を利用する、格子捜索についてのいくつかのアプローチを記載する。
【００４３】
では、単位正方形上のランク−１格子についての捜索のための技術を記載する。付属書のセクション２．１．１は、所与の
2009501966.tif 000084
について、全ての可能な格子
2009501966.tif 000085
を考慮する単位正方形上での基本的捜索のためのコードリストを記載する。ａ＞ｎについての値は、これらは、剰余演算によって格子
2009501966.tif 000086
を生み出すため考慮される必要はない。さらに、ｎ＞３を仮定すると、単位正方形の２つの対角線上に格子点が存在するため、ａ＝１およびａ＝ｎ−１は捜索から除かれる。ａ＝０は、原点へと崩壊する格子を生じるであろう。従って、同様に無視される。
【００４４】
ｍａｘ−ｍｉｎ−ｄｉｓｔ格子についてのパラメータａの選択は、一意的ではなく、すなわち、同一の最大最小距離となるいくつかの可能性が存在する。従って、集合
2009501966.tif 000087
が、それまでに求めた集合
2009501966.tif 000088
を格納するために使用される。
【００４５】
各格子について、アルゴリズムは、最短ベクトルの長さを全格子点
2009501966.tif 000089
に関して繰り返すことで決定する。式２．３に従うと、格子は、単位円環面上で規定されているが、§２．１．１コードリストにおける全計算は、浮動小数点の不正確さによる丸め誤差を回避するため整数計算にて実行される。このことは、本検討が［０，１）２の代わりに［０，ｎ）２上の整数格子
ｘｉ＝（ｉ，ａ・ｉ  ｍｏｄ  ｎ）                            （２．４）
に主眼を置いていることを意味する。
【００４６】
剰余演算のため、格子Ｌ（ｎ，ａ）⊂［０，ｎ）２は周期的である。最短ベクトルを求めるため、次に格子点
2009501966.tif 000090
から原点までの距離が計算される。単位円環上の計算は、ｉ＞ｎ−ｉまたはａ・ｉ＞ｎ−ａ・ｉ  ｍｏｄ  ｎの場合、異なる象限からの点
2009501966.tif 000091
を考慮することが必要である。
2009501966.tif 000092
【００４７】
図７は、格子Ｌ（５，２）についての上記技術を図示するグラフ２６０を示す。点
2009501966.tif 000093
の原点への距離を算出するため、周期性により、点（０，５）が新たな原点として取られる。新たな原点を使用することは、点（０，０）における第一象限の原点に対する点
2009501966.tif 000094
のユークリッドノルムの計算に対応する。
【００４８】
原点までの格子点
2009501966.tif 000095
の距離は、平方ユークリッドノルム
2009501966.tif 000096
によって算出される。平方とその総和の両方は、計算中に整数オーバーフローを生じることがあるが、次のように処理される。
・変数についてのデータタイプは、特にタプル（ｎ，ａ）については正整数型（ＵＩＮＴ）であるように、また、ユークリッドノルム計算に含まれる実体については符号無し倍長精度整数型（ＵＬＬＩＮＴ）であるように、いずれか選択される。
・
2009501966.tif 000097
の場合は、ｘｊ２についての整数オーバーフローが生じるであろう。
・
2009501966.tif 000098
が、２つの要素の総和について当てはまり、
2009501966.tif 000099
であるので、
2009501966.tif 000100
の場合は、オーバーフローが明らかである。
最後の２つの場合において、§２．２．１コードは、次の格子点へと進む。式２．４における乗算ａ・ｉｍｏｄｎも、オーバーフローに関して問題がある可能性がある。従って、繰り返し計算される増量総和
2009501966.tif 000101
へと分解され、
2009501966.tif 000102
によって剰余演算が内部ｆｏｒループの各繰り返しにおいて適用される。
一旦最短ベクトルが求められると、その長さが、それまでの最大最小距離ｍａｘｍｉｎｄｉｓｔを有するベクトルの長さと比較され、関連するパラメータａを可能であれば記憶する。しかし、新たなｍａｘｍｉｎｄｉｓｔが、§２．２．１コードリストにおけるｍｉｎｄｉｓｔについての初期値であるＭＡＸ＿ＵＬＬＩＮＴにならないことを確実にするため、ブーリアンフラグｎｏＯｖｅｒｆｌｏｗが最初に真に設定されるまでこれはなされない。新たなｍａｘｍｉｎｄｉｓｔが古いもの以上かどうかによって、ベクトル
2009501966.tif 000103
は、新たな値を格納する前にクリアされる。
【００４９】
§２．２．１コードリストの複雑度は、Ｏ（ｎ２）であり、これでは、格子捜索が大きなｎについて実行されるとき非常に遅いことがわかる。従って、捜索領域を制約することが望ましい。まず、検討がなされるａの数をさらに減らすことが可能である。
2009501966.tif 000104
が捜索問題に対して有効な解である場合は、対称のため同じｍａｘ−ｍｉｎ−ｄｉｓｔを有する
2009501966.tif 000105
も有効な解である。従って、ａの範囲を２からｎ／２とすれば充分である。
【００５０】
さらに、「球の詰め込み」問題であるため、最短ベクトルの長さを決定するためには、全格子点に関して繰り返す必要はない。「球の詰め込み」は、全部または一部を互いに接しつつ重ならない球または２次元においては円の配置を求めることを意味する。この場合、円は、格子点を中心としており、その半径は、互いにちょうど接触するように選択される。これは、ｒ＝ｍｉｎｄｉｓｔ／２によって達成される。従って、最大最小距離を求めることは、球の詰め込み問題なのである。球の詰め込みに関しては、（２次元における）基本平行六面体の体積に対する球の体積の比率を最大化する必要がある。
2009501966.tif 000106
ここで、Ｂは基底行列である。六方格子が、
2009501966.tif 000107
における球の詰め込み問題を解決するので、最も大きい最大最小距離がこのようなタイプの格子において達成される。従って、原点の周囲で半径ｌを有する円の外側である格子点を検討する必要はない。ここでｌは、六方格子における２点間の距離である。この量は、次のようにして評価することができる。
【００５１】
各格子セルすなわち基本平行六面体は、２つの正三角形に分割される。格子は、ｎ２の面積に渡る。従って各ｎ格子セル（各点について１つ）は、
2009501966.tif 000108
の面積を有する。従って、正三角形の面積Ａはｎ／２である。このようにして、求める量である三角形の辺の長さｌを計算することができる。
2009501966.tif 000109
【００５２】
図８Ａおよび８Ｂは、上述のプロセスを要約した1対の図である。図８Ａは、六方格子の基本平行六面体２７０を示す。図８Ｂに示すように、基本平行六面体の半分は、正三角形２８０を表す。ｈは三角形の高さを示す。ｌは、１つの三角形辺の長さを表す。
【００５３】
こうして、§２．２．１コードリストの外側ｆｏｒループが、
2009501966.tif 000110
で停止され得る。組み合わせて、基本捜索アルゴリズムの複雑度がＯ（ｎ２）から
2009501966.tif 000111
へと減らされた。
【００５４】
これまでは、Ｌ（ｎ，ａ）における最小距離の最大化を別として、格子パラメータａに条件が課されなかった。ｎとａが互いに素である（これらの最大公約数が１であることを意味する）ことを要すると、すなわち、
ｇｃｄ（ｎ，ａ）＝１
であるとすると、得られる格子点は、各座標軸上で等距離に階層化するであろう。従って、最小距離は、
2009501966.tif 000112
に制限され得る。しかし、この条件は、所与の
2009501966.tif 000113
についての最大最小距離格子を求めることに関して制約を表す。
【００５５】
ｎによっては、基本捜索アルゴリズムが非常に膨大な数のｍａｘ−ｍｉｎ−ｄｉｓｔ格子を生じるものもある。可能な格子の数を減らすために、§２．２．１コードリストは、第２の最短ベクトルの距離も最大化されるように拡張されている。この場合、第３の最短ベクトルは、なんら改善をもたらさないことを考慮している。
【００５６】
今度は重み付けしたノルムの使用を検討する。これまでの点の検討は、単位正方形上のｍａｘ−ｍｉｎ−ｄｉｓｔ格子についての捜索に主眼を置いてきた。得られる格子点は、例えば、１つの象限上で数値積分に共されてよい。以下にさらに記載する技術において、格子は、通常正方形的スケーリングではないコンピュータスクリーン全体を覆って使用される。しかし、単に
2009501966.tif 000114
を矩形領域にスケーリングすると、
2009501966.tif 000115
−一様に関して点の一様な分布とはならない可能性がある。非一様分布を図９Ａ−Ｃに示す。図９Ａは、単位正方形に選択された、ｎ＝７８６４３２点を有する格子を図示するグラフ２９０を示す。図９Ｂは、実際の領域にスケーリングされた、単位正方形における格子を図示するグラフ３００を示す。図９Ｃは、実際の領域における格子を図示するグラフ３１０を示す。
【００５７】
従って、原点までの格子点の距離を計算する場合に、実際の領域の大きさを考慮する必要がある。そのため、ユークリッド・ノルムが、重み付けノルムに取って代えられる。従って、記載の方法が、あたかも単位正方形上で実行されるが、領域サイズを補正するため２つの倍率で修正された平方ユークリッドノルム
2009501966.tif 000116
を有している。このような倍率は、ｘ−解像度（Ｒｅｓｏｌｕｔｉｏｎ）およびｙ−解像度の両方を、これらの最大公約数（ｇｃｄ）で割ることで得られる。
2009501966.tif 000117
倍率の導入は、基本捜索アルゴリズムにわずかな修正しかもたらさない。付属書の§２．１．２は、実際の領域サイズを考慮した拡張された捜索を含むコードリストを示す。§２．１．２コードリストは、任意の領域サイズ上での捜索と上記の改善とを包含する。§２．１．２コードリストにおけるドットは、§２．１．１コードリストの改変されていない部分を表す。
【００５８】
上述のように、記載の格子の１つの使用は、ディスプレイスクリーン全体をサンプリングすることである。ｘＲｅｓ×ｙＲｅｓのスクリーン解像度で格子点の数ｎ＝ｘＲｅｓ・ｙＲｅｓを仮定すると、各画素をサンプリングしていない状況、すなわち、なんらサンプリングされないままの画素が存在する状況に遭遇する可能性がある。図１０Ａは、この状況を図示するグラフ３２０を示す。図１０Ａにおいて、格子
2009501966.tif 000118
が［０，５）２にスケーリングされ、スクリーンを解像度５×５でサンプリングしている。画素（０，１）が欠けている一方で画素（０，０）は２つのサンプルを含む。
【００５９】
同様に、
2009501966.tif 000119
として、格子点の数がｎ＝ｘＲｅｓ・ｙＲｅｓ・αと設定されると、画素当たり同数のサンプルが常には達成されないであろう。さらに一般的には、区間
2009501966.tif 000120
ごとに、同数の点
2009501966.tif 000121
を得ることが望ましい。ここで、ｘＲｅｓおよびｙＲｅｓはスクリーン解像度とする。
【００６０】
この問題に対しては、多くの解が存在する。解は、一般に全体の格子の有効なシフトについての捜索を有する。ここで、「有効」とは、シフトした格子について、上記の式で記載している区間ごとに同数の格子点が存在することを意味である。丸め誤差を回避するためには、［０，１）２の代わりに［０，ｎ）２上で再度計算が実行されよう。
【００６１】
格子が周期性であることより、最大限１画素幅のシフトを考慮すると充分であり、基本平行六面体において捜索するよりも容易である。捜索領域（すなわち１画素）は、格子点の低次元投影を見ることで離散化される。このようなことが、各座標軸を等しく階層化する意味で完全である場合は、２つの格子点間の距離は、それぞれ、ｘ軸上でｘＲｅｓ／ｎ、ｙ軸上でｙＲｅｓ／ｎである。このことは、１画素内において、
2009501966.tif 000122
投影された格子点がｘ軸上に、および
2009501966.tif 000123
投影された格子点がｙ軸上に存在することを意味する。このような投影による離散化は、図１０Ａグラフ３２０の左下隅の小グリッドによってハイライト表示しており、検討されるべきシフトを表している。次に、３つの重要な捜索戦略を検討する。
【００６２】
所与のｍａｘ−ｍｉｎ−ｄｉｓｔ格子Ｌ（ｎ，ａ）について理想的には有効なシフト
2009501966.tif 000124
が求められる。そのため、全ての可能なシフトが繰り返し処理され、画素あたりの格子点の数がカウントされる。その後、画素（０，０）における点の数が、他のカウント入力と比較される。これらの１つが第一の画素の格子点の数と等しくない場合は、すぐに比較が中止されることがあり、次の格子シフトへ切り替えがなされる。手順は、有効なシフトが見つかれば即停止し、［０，ｎ）２上でシフトを戻す。付属書の§２．１．３は、所与の格子についての捜索シフトのコードリストを示す。
【００６３】
図１０Ｂは、グラフ３３０を示し、ここで
2009501966.tif 000125
のシフトが、
格子Ｌ（２５，７）に加えられた後、［０，１）２から［０，５）２へとスケーリングされた。このシフトが加えられた後、正確に画素あたり１つの格子点が存在する。しかし、格子シフトは、非常に少ないｎについてしか見つけることができず、ｎが大きくなるにつれ、有効なシフトが存在するであろう確率が小さくなる。図１１は、有効なシフトが見つかった最大最小距離格子のいくつかとその元になるスクリーン解像度を列挙する表３４０を示す。
【００６４】
このように、捜索するための異なる方法が必要である。１つの可能性は、まず、少なくとも１つの有効なシフトを含むことになる格子に対するａの集合を捜索し、次に、このような候補間でｍａｘ−ｍｉｎ−ｄｉｓｔ捜索を実行する。しかし、所与の
2009501966.tif 000126
について最もｍａｘ−ｍｉｎ−ｄｉｓｔ格子
2009501966.tif 000127
に近似する格子
2009501966.tif 000128
を捜索するので、次の戦略が極めて良いことがわかった。第一のステップにおいて、ａのリスト
2009501966.tif 000129
がＬ（ｎ，ａ）における最小距離に関してヒープソートを使用してソートされる。その後、ソートされたリストが降順で渡され、シフト捜索が各ａについて実行される。それによって有効なシフトを有する最初のａが所望の結果を生じる。この捜索戦略の実行は、付属書の§２．１．４に記載のコードリストに組み込まれている。
【００６５】
§２．１．４コードリストにおいて、画素あたりの格子点の数が再度カウントされる。１つの画素が、ｎ／（ｘＲｅｓ．ｙＲｅｓ）点を超えて保持すると、処理は、次の格子シフトへとすぐに切り替わることができる。この場合、１の画素は、ｎ／（ｘＲｅｓ．ｙＲｅｓ）サンプルまでは確実に含まないであろうからである。§２．１．４コードリストのドットは、前のコードリストと変わらない部分を表す。
【００６６】
３つの入れ子ｆｏｒループのため、§２．１．４コードリストは、Ｏ（ｎ３）の複雑度を有し、大きいｎについては非常に遅い。しかし、シフトの捜索は、ループ（１）および（２）を交換することでかなり短縮することができる。その意味は、捜索領域を異なる順序で通過するということである。これは、少なくとも１つのシフトのｙ成分が、全ての検討した場合においてゼロであるという所見に基づいている。図１２は、§２．１．４コードリストから得られる格子をリストする表３５０を示す。図１２表において、最初のシフトが見つかった後にシフト捜索を停止しないことで非ゼロｙ成分を有するシフトが得られた。ループ（１）と（２）を切り替えたにもかかわらず、格子Ｌ（４１９４３０４，１８２１８３）を計算するのに、Ｉｎｔｅｌ  Ｐｅｎｔｉｕｍ（登録商標）４，２．８ＧＨｚで概ね５日かかった。
【００６７】
画素あたり同数の格子を達成しているが、得られた格子の大部分は最大最小距離特性を満足しないであろうことを念頭に置くべきであるが、可能な限り良く近似するであろう。
【００６８】
次に、ランク−１格子の選択において、いわゆる「スペクトルテスト」の使用を検討する。「スペクトルテスト」は、タプル（ａ，ｃ，ｍ，Ｘ０）および漸化式
2009501966.tif 000130
によって規定される線形合同法乱数生成器の質を評価する。ここで、
2009501966.tif 000131
は、法であり、
2009501966.tif 000132
は、乗数であり、
2009501966.tif 000133
は、増分であり、
2009501966.tif 000134
は、開始値である。０と１との間の数は、
2009501966.tif 000135
によって与えられる。
【００６９】
全てのｔ＞０について、周期ｍの数列
2009501966.tif 000136
に基づいて、スペクトルテストは、全ｍ点の集合
2009501966.tif 000137
を解析する。これは、連続して重複するｔ−タプルの｛ｕ０，ｕ１，．．．｝によって形成され、それにより全ての可能な開始値を考慮する。理論を単純化するため、スペクトルテストは、ｃ≠０で全周期ｍの線形合同数列が存在すること、またはｍが素でありｃ＝０で周期長がｍ−１であること、のいずれかを仮定する。常にｍ点が存在することを確実とするため、後者の場合には点集合に原点が追加される。これは、Ｘ０＝０は開始値として除外されなければならないからである。ここで、上記の点集合は、
2009501966.tif 000138
と記載することができる。
点集合Ｌｔによって生成されたパターンが格子構造を有することがわかるであろう。ｔ＝２かつｃ＝０についての集合は、２次元コロボフ格子を生じる。一般に、ｃ＝０についてのＬｔは、生成作用素ベクトル（１，ａ，ａ２，．．．，ａｔ−１）ｍｏｄｍを有するランク−１格子によって生成された点集合に対応する。２次元において格子点は、多くの異なる一群から選択され得る少数の平行線によって囲まれ得る。高次元において、複数群の線は、複数群の超平面に一般化される。スペクトルテストの目標は、超平面間の最大距離の逆数として定義されるｔ次元の精度ｖｔを、全点を取り囲む全複数群の平行な（ｔ−１）次元超平面を考慮して決定することである。次の検討において、式２．１７の格子へ双対である格子の最短ベクトルの長さに、ｖｔが対応することが得られるであろう。このことは、スペクトルテストが、ｍａｘ−ｍｉｎ−ｄｉｓｔ格子の捜索に適用され得ることを意味する。
【００７０】
線形合同乱数生成器のパラメータｃは、Ｌｔの全要素の相対距離が維持されるようにシフトをもたらすのみであるため、スペクトルテストになんら影響しない。このことは、漸化式
2009501966.tif 000139
を分解すると理解できる。ここで、γ＝（１＋ａ＋．．．＋ａｔ−１）ｃは一定である。従って、ｃ＝０と設定することができ、このことは、格子をコロボフ形式で直接扱うことを意味する。
【００７１】
捜索しているのは２次元のｍａｘ−ｍｉｎ−ｄｉｓｔ格子であるため、２次元の点集合
2009501966.tif 000140
を検討し、Ｌ２の点を囲む平行直線の全群を考慮して、ｖ２すなわち線間の最大距離の逆数を計算することで充分である。まず、式２．１８に隠されているｍｏｄｍ−演算が
2009501966.tif 000141
と記載することでｍｏｄ１に置換される。
次に、集合Ｌ２を周期的に拡張することにより、すなわち
2009501966.tif 000142
全体を２次元超立方体のコピー
2009501966.tif 000143
で覆うことで、ｍｏｄ１−演算が処理される。これを、図１３のグラフ３００に図示する。ここで点集合
2009501966.tif 000144
が周期的に拡張され、ここで、周期的に拡張された格子が等距離の平行線の一群で覆われる。集合２．２１は、
2009501966.tif 000145
であるので、（ｘ，ｋ１，ｋ２）を（ｘ＋ｋ１ｍ，０，ｋ２−ａｋ１）に変更することによりさらに単純化され得、これにより変数ｋ１をゼロに設定する。このようにすることで、上記の点集合を
2009501966.tif 000146
によって記述されるようにすることができる。
集合２．２２は、
2009501966.tif 000147
を満たす元の集合２．１９のｍ点を含むことが理解されるであろう。
今度は、
2009501966.tif 000148
の全点を覆う複数群の線間で隣接する平行線間の最大距離を求めることが望まれる。このような一群を、含まれる線全てに垂直な非ゼロベクトルｕ＝（ｕ１，ｕ２）で規定することができる。そして、特定の線上の点の集合は、
2009501966.tif 000149
によって記述することができ、ここでｑは、各線についての固有の定数である。線は、原点を通る線の１つと等距離であるため、今度は
2009501966.tif 000150
が、一群の全ての線を規定するようにｕの長さを調節することが可能である。このことは、ｑ＝１について、原点から線への最小距離として隣接する線間の距離を計算することができることを意味する。すなわち、
2009501966.tif 000151
コーシーの不等式によると、
2009501966.tif 000152
ｊ＝１，２に対して、ｘｊ＝ｕｊ／（ｕ１２＋ｕ２２）は、
2009501966.tif 000153
のため、式２．２５において最小を生じる。
従って、隣接線間の距離は、
2009501966.tif 000154
である。
2009501966.tif 000155
が最小の場合、距離は最大に達する。この理由によって、２次元的精度ｖ２は、点集合２．２２の全要素を覆う一群の超平面
2009501966.tif 000156
を規定する最短ベクトル
2009501966.tif 000157
の長さに対応する。このようなベクトル
2009501966.tif 000158
は、次の条件を満足しなければならない。すなわち、
2009501966.tif 000159
逆に、条件４を充足する任意の非ゼロ整数ベクトル
2009501966.tif 000160
を考慮すると、対応する一群の線は、
2009501966.tif 000161
の全要素を覆うであろう。というのは、全整数ｙ１，ｙ２について内積
2009501966.tif 000162
が整数となるからである。従って、スペクトルテストは、最小値
2009501966.tif 000163
を求める必要がある。ここで、ｕ１＝ｍｘ１−ａｘ２およびｕ２＝ｘ２は、
2009501966.tif 000164
であるため、基本合同式のパラメトリックおよび一般解である。
【００７２】
最小値
2009501966.tif 000165
を求めるため、この問題は、全非ゼロ整数ベクトル（ｘ１，ｘ２）に関して、２次形式
2009501966.tif 000166
を最小化するさらに一般的な問題として定式化される。ここで、
2009501966.tif 000167
は任意の非特異行列である。ｗ１１＝ｍ，ｗ１２＝０，ｗ２１＝−ａおよびｗ１２＝１は、式２．２８の特別の形態を生じる。
【００７３】
付属書のセクション２．１．５に２次元精度ｖ２の値を決定する方法のコードリストを記載する。これには「ユークリッドステップ」が包含されており、これは高次元に関する２次元スペクトルテストの単純化を表し、縮小２値２次形式（ｒｅｄｕｃｅｄ  ｂｉｎａｒｙ  ｑｕａｄｒａｔｉｃ  ｆｏｒｍ）の「ガウスの概念」に基づいている。合同式ｕ１＋ａｕ２≡０に対する全整数解が、整数ｘ１，ｘ２について、ｗ１１−ａｗ１２＝ｗ２１＋ａｗ２２≡０およびｄｅｔ（Ｗ）＝ｍとなるような行列Ｗであるとして、ｕ１＝ｘ１ｗ１１＋ｘ２ｗ２１およびｕ２＝ｘ１ｗ１２＋ｘ２ｗ２２の形式を取ることを証明することができる。さらに、Ｗが条件
2009501966.tif 000168
を満足する場合、（ｕ１，ｕ２）＝（ｗ１１，ｗ１２）は、ｕ２１＋ｕ２２を、全非ゼロ整数解に関して最小化する。
【００７４】
§２．１．５コードリストにおける方法は、上述のように、式２．２９に示す２次形式を、（ｗ１１，ｗ１２）がｕ２１＋ｕ２２の最小解を表すまで縮小することで、このような考慮を利用している。
【００７５】
ｖ２は、
2009501966.tif 000169
の全要素を覆う一群の線を規定する最短ベクトルの長さであるため、および条件２により、２次元精度は、
2009501966.tif 000170
における、すなわち、
2009501966.tif 000171
に双対である格子において、最短ベクトルの長さとみなすこともできる。すなわち、
2009501966.tif 000172
である。
2009501966.tif 000173
における各点ｕは、
2009501966.tif 000174
における各点が線のうちの１つの上にあるように、平行で等距離の一式の線を規定するため、最短ベクトル
2009501966.tif 000175
は、最大距離を有する線群を規定する。
2009501966.tif 000176
を１つおきに選択することで、線は互いにさらに接近することとなる。次いで、一群の中から２つの隣接する線が選択され、それぞれの１つの格子点は、第１の線上に一方の固定した点
2009501966.tif 000177
があり、
2009501966.tif 000178
に最接近している第２の線上に他方の点
2009501966.tif 000179
があるようにされている。そして、
2009501966.tif 000180
および
2009501966.tif 000181
間の距離は、２つの隣接する線間の距離が増加するにつれて減少する。従って、
2009501966.tif 000182
における最短ベクトルも、
2009501966.tif 000183
における最短ベクトルを示す。実際のところ、ｖ２すなわち
2009501966.tif 000184
における最短ベクトルの長さは、何らかの倍率によっては
2009501966.tif 000185
における最短ベクトルの長さと等しい。このことは、
2009501966.tif 000186
の基底Ｂおよび
2009501966.tif 000187
の基底
2009501966.tif 000188
を考慮することで証明できる。
2009501966.tif 000189
を、
2009501966.tif 000190
のミンコフスキー縮小基底であるとする。すると、（Ｂ−１）Ｔの列ベクトルは、双対格子
2009501966.tif 000191
の基底を表す。ここで、
2009501966.tif 000192
がＢの行列式とすると、
2009501966.tif 000193
の基底行列の逆は、
2009501966.tif 000194
によって計算できる。
従って、
2009501966.tif 000195
の基底行列は、
2009501966.tif 000196
である。
双対格子の基底ベクトルの長さを計算すると、
2009501966.tif 000197
と
2009501966.tif 000198
の違いは１／ｍの係数によるだけであることがわかる
2009501966.tif 000199
。
双対格子の基底ベクトルは、
2009501966.tif 000200
の両方を±９０°回転することから得られ、
2009501966.tif 000201
これは、双対格子の格子点間の相対距離が
2009501966.tif 000202
のものに対応することを意味する。
2009501966.tif 000203
が、
2009501966.tif 000204
における最短ベクトルであり、
2009501966.tif 000205
も
2009501966.tif 000206
において同様である。
逆に、双対格子
2009501966.tif 000207
において最短ベクトルを求める場合は、その長さは、ｍで乗算した
2009501966.tif 000208
における最短ベクトルの長さを生じる。この事実は、§２．１．１コードリストで記載したように、単位正方形上でのｍａｘ−ｍｉｎ−ｄｉｓｔ格子の捜索に利用される。全格子点に関して繰り返して最小距離を計算する代わりに、２次元スペクトルテストが適用される。［０，ｍ）２が計算されるので、２次元精度は、求められていた量を提供する。他の基本捜索法は、付属書の§２．１．６に記載のコードリストに示すように変わりはない。
【００７６】
スペクトルテストは、ｖ２を決定するために数サイクルを必要とするのみであるので、§２．１．１法が上述の最適化を組み込む場合であっても、§２．１．６コードリストに記載の方法は§２．１．１に記載の方法よりもはるかに速い。しかし、§２．１．５の方法を使用することで、§２．１．６の方法は単位正方形に制約される。
【００７７】
次に格子についての基底を捜索する方法を記載する。以上までにおいては、発明の記載は、格子捜索のための方法に重点を置いてきた。次にさらに詳細に記載するように、発明の局面には、ランク−１格子上のラスタライゼーションと適応的サンプリングが含まれる。従って、所与の格子について良好な基底を選択することが必要である。所与の基準に従って格子基底を決定するプロセスは、「縮小」と呼ばれる。本目的のため、基底ベクトルができる限り短い場合が有利であり、合理的に六方格子セルが得られる。しかし、一般的事項として、２つの最短ベクトルを単純に選択することが可能である。これらは、必ずしも基底を形成しないからである。
【００７８】
この問題は、次のように定式化されてきた。行ベクトルである基底
2009501966.tif 000209
は、
2009501966.tif 000210
が、全ての
2009501966.tif 000211
について、および全ての
2009501966.tif 000212
について該当する場合は、「エルミート縮小（Ｈｅｒｍｉｔｅ  ｒｅｄｕｃｅｄ）」されていると言われる。この意味は、同一の格子の全生成行列の対応する数列が辞書式の順序であるリストにおいて数列
2009501966.tif 000213
が、最初の要素である場合、生成行列Ｇが縮小されるということである。このように縮小された基底において、最初の基底ベクトルは、最短非ゼロ格子ベクトルに一致する。エルミート縮小基底は各格子について存在するが、明確な構成は既知ではない。
【００７９】
ここで記載している基底捜索においては、それほど厳密ではない縮小基準が使用される。基底
2009501966.tif 000214
が、
１．ｇ１がＬにおける最短非ゼロベクトルであり、
２．
2009501966.tif 000215
について、（ｇ１，．．．，ｇｉ）がＬの基底に拡張され得るようなＬにおいてｇｉが最短ベクトルである場合に、この基準に従って縮小される。
このようないわゆる「ミンコフスキー縮小基底」は、常に最短非ゼロ格子ベクトルを含む。
【００８０】
使用され得るさらに他の縮小方法が存在し、それには「Ｋｏｒｋｉｎｅ−Ｚｏｌｏｔａｒｅｆｆ縮小」および「ＬＬＬ−縮小」が含まれる。縮小法の選択は、根本的な問題に依存する。ミンコフスキー縮小基底を求める問題はＮＰ困難であるが、本目的のためには、２次元の場合に制限されており、ランク−１格子の特別な構造を利用することができることから、この縮小を使用することで充分である。
【００８１】
２次元において、ミンコフスキー縮小基底を求めるには、最短非ゼロ格子ベクトル
2009501966.tif 000216
について捜索が最初に実行される。その後、次の基底ベクトル
2009501966.tif 000217
が、
2009501966.tif 000218
に一次独立である、Ｌにおいて２番目に最短の格子ベクトルを捜索することで決定される。このようなことが、基本捜索法を修正することで行われ得る。所与の格子Ｌ（ｎ，ａ）について、上述の式２．５のようにｍｉｎｄｉｓｔ（ｘｉ）を計算するため、全格子点
2009501966.tif 000219
が繰り返される。最短ベクトルと第２最短ベクトルの両方の長さが、必要であれば基底ベクトルを更新するためにチェックされる。しかし、第２基底ベクトルを更新する前に、これが、ミンコフスキー縮小基底の条件が保持されるように第１基底ベクトルに一次独立であることを確認する必要がある。２つの２次元基底ベクトルの行列式の簡単な計算は、整数オーバーフローを生じることがあるため、このテストについては特別な注意が払われる必要がある。定義により、２つのベクトル
2009501966.tif 000220
は、
ｘ＝λ・ｙ
となるスカラーλ≠０が存在するとき、一次従属である。
換言すれば、これは、一方のベクトルが他方の倍数である場合は一次従属であるという意味である。このことは、
2009501966.tif 000221
に対して、２つの得られるベクトル
2009501966.tif 000222
が等しく、さらに、ｓｇｎ（ｘ１）＝ｓｇｎ（ｙ１）およびｓｇｎ（ｘ２）＝ｓｇｎ（ｙ２）またはｓｇｎ（ｘ１）≠ｓｇｎ（ｙ１）およびｓｇｎ（ｘ２）≠ｓｇｎ（ｙ２）である場合に該当する。
【００８２】
付属書のセクション２．２．１には、２つの基底ベクトルの一次独立性をチェックするコードリストを記載している。ベクトル成分の符号が含まれていない場合は、§２．２．１コードリストは、例えば、一次従属としてベクトル（１，１）および（１，−１）を取るであろう。図１４は、格子Ｌ（２５，７）と基底捜索アルゴリズムから得られた２つの基底ベクトルを図示するグラフ３７０を示す。図１５に示すように、
2009501966.tif 000223
である。
【００８３】
付属書のセクション２．２．２は、捜索がミンコフスキー縮小基底について行われたコードリストを示す。計算は、常に［０，ｎ）２上で実行され、そのため基底ベクトルも［０，ｎ）２上で得ることを記憶に留めておくべきである。シフトした格子に関しては、基底捜索アルゴリズムは、同じように適用され得る。これは、シフトは、全格子の平行移動（ｔｒａｎｓｌａｔｉｏｎ）を表すだけであり、基底に影響しないためである。
【００８４】
次に、ランク−１格子に関連して（０，ｍ，２）−ｎｅｔｓの使用を記載する。発明の本説明は、スクリーン全体をセクションにおいてサンプリングする点に関して、シフトした格子についての１つの動機を既に記載してきた。図１０Ｂグラフ３３０の格子を近づいて見てみる。図１５は、図１０Ｂのグリッド構造の改良を図示するグラフ３８０を示し、
2009501966.tif 000224
だけシフトされた格子
2009501966.tif 000225
を示す。格子点は、低次元投影において精細なグリッド構造を完全に充填する。これは、このような線上に別の格子点を有しないｘ軸およびｙ軸に投影された中空格子点によって示される。さらに、各区分
2009501966.tif 000226
も、正確に１つの格子点を含む。従って、格子は、階層化とラテンハイパーキューブサンプリング点の両方の特徴を有する。
【００８５】
これは、（０，ｍ，２）−またはさらに一般的に（ｔ，ｍ，ｓ）によって定式化できる。基本区間は、
2009501966.tif 000227
によって規定される。ここで
2009501966.tif 000228
は次元であり、
2009501966.tif 000229
は、基底を表し、
2009501966.tif 000230
は整数である。Ｅの体積は、
2009501966.tif 000231
によって与えられる。
２つの整数
2009501966.tif 000232
について、体積
2009501966.tif 000233
の各基本区間が正確にｂｔ点を含む場合、ｓ次元におけるｂｍ点の有限の点集合は、基底ｂにおける（ｔ，ｍ，ｓ）−ｎｅｔと呼ばれる。比較的小さいｔの値によってさらに良好な一様な分布が確保されるため、ｔは優良性パラメータと呼ばれる。
【００８６】
このような定義に留意し、図１５グラフ３８０に示す格子は、各要素の体積ｂｔ−ｍ＝５０−２＝１／２５が正確に１つの格子点を含むので、基底５における（０，２，２）−ｎｅｔを表す。このような観測は、格子
2009501966.tif 000234
についての全ての可能なシフトの捜索をすることとなり、基底２における（０，ｍ，２）−ｎｅｔについてこれらをテストする。すなわち、各基本区間の体積２−ｍ＝１／ｎが、正確に１点を含むかをチェックする。検討された格子は、条件ｇｃｄ（ｎ、ａ）＝１を充足する必要があると考えられよう。そうでなければ、完全な１次元投影を得ることが可能ではないであろうからである。しかし、上述の格子はいずれも基底２における（０，ｍ，２）−ｎｅｔではないことが判明した。ということは（０，ｍ，２）−ｎｅｔｓは、ランク−１格子をシフトすることでは簡単には求めることができないことを意味する。それでもなお、基底ｂが素であり、シフトした格子Ｌ（ｂ２，ａ）についてｇｃｄ（ｂ２，ａ）＝１の場合は、図１５グラフ３８０に示す格子についての場合が該当するように、ｍ＝２についての（０，ｍ，２）−ｎｅｔｓが容易に得られる。これは、このとき必然的に１つの格子点のみを含む体積１／ｂ２の３つの異なる基本区間の
2009501966.tif 000235
が存在するからである。図１６は、基底ｂにおけるいくつかの（０，２，２）−ｎｅｔｓをさらにリストする表３９０を示す。
【００８７】
３．ランク−１格子上のラスタライゼーション
ラスタディスプレイは、通常、スクリーン全体を表現する画像要素（画素）のマトリクスから形成される。画像を正確にレンダリングするために、ラスタライザは、適切な色を画素の集合へ割り当てることで、直交グリッド上で頂点によって記述される、線、三角形、または円のような数学的理想的プリミティブを近似する。ラスタライザは、スクリーン空間における２次元頂点をスクリーン上の画素へと変換する。現在のアプローチにおいては、画素は通常、整数ラスタ（ｉｎｔｅｇｒａｌ  ｒａｓｔｅｒ）［０，．．．，ＲｅｓＸ）×［０，．．．，ＲｅｓＹ）上の正方形として表現される。
【００８８】
本局面は、ランク−１格子に基づくラスタライゼーション技術に関する。この方法によると、ラスタライゼーションは、矩形グリッド上ではなくランク−１格子の格子セル上で実行される。すなわち、画素レイアウトがランク−１格子によって構成される。図１７は、発明のこの局面に従った方法４００のフローチャートである。
【００８９】
工程４０１において、ランク−１格子は、生成されるべき合成画像における点に対応する最大化した最小距離関数に従って選択される。工程４０２において、直交座標における点ｐが、ランク−１格子の基底へと変換される。工程４０３において、変換された点が該当する格子セルが決定される。工程４０４において、直交座標が、ランク−１格子座標へと変換される。工程４０５において、ランク−１格子座標が、画像をラスタライズするために使用される。
【００９０】
次の検討において、線についてのスキャン変換技術であるデジタル微分解析機（ＤＤＡ）に関連して、および凸多角形についてのラスタライゼーション技術であるクロウのアルゴリズムに関連して、ラスタライゼーション技術を記載する。記載の技術は、従来のラスタディスプレイで実行することができる。さらに、以下に記載のように、この技術は、ディスプレイ技術の新たな概念のベースを形成もする。
【００９１】
線についてのスキャン変換技術は、２次元ラスタ上に引かれた理想的直線を最もよく近似するような画素の座標を算出することに基づいている。線は、典型的には、始点、終点、幅によって、および別のスタイル特性によって特徴付けられる。本検討は、１画素の幅を有し、別の特性がなく、アンチエイリアシングがない線に主眼を置く。
【００９２】
線をスキャン変換する最も簡単な技術は、関数
2009501966.tif 000236
のテイラー級数展開に基づくデジタル微分解析機（ＤＤＡ）である。
【００９３】
ラスタライゼーションが整数格子上で実行されるので、線の端点は整数座標と考えられる。所与の対の（整数）点Ｐ０＝（ｘ０，ｙ０）およびＰ１＝（ｘ１，ｙ１）について、直線は、
2009501966.tif 000237
によって明確に記述することができる。
式３．１を使用して、線上の点（ｔ＋τ，Ｐ（ｔ＋τ））は、その先行点（ｔ，Ｐ（ｔ））から増分的に計算することができる。
2009501966.tif 000238
その始点から終端へと増分的に線を引くため、ラスタライゼーションプロセスは、ｎステップに離散化されなければならない。ここでｎ＝ｍａｘ｛｜ｘ１−ｘ０｜，｜ｙ１−ｙ０｜｝である。これは、理想的線を近似する画素座標が
2009501966.tif 000239
によって増分的に算出されることを意味する。例えば、｜Δｘ｜＞｜Δｙ｜の場合、ｎ＝｜ｘ１−ｘ０｜である。従って、ｘｉは、各ステップにおいて±１だけ増加し、一方で、ｙｉは、割合
2009501966.tif 000240
だけ増加する。座標を計算した後、理想的線に最も近い画素
2009501966.tif 000241
が着色される。視覚化のため、画素は、２つの隣接する格子線によって形成されたセルの中央におけるサンプルと解釈される。図１８Ａは、画素（２，２）がラスタグリッド上で強調されているグラフ４１０を示す。図１８Ｂは、整数端点（０，０）と（３，１）を有する線のラスタライゼーションを説明するグラフ４２０を示す。ラスタライゼーションプロセスは、ｎ＝３、ｄｘ＝３およびｄｙ＝１であるので、連続的に画素
2009501966.tif 000242
を強調する。付属書のセクション３．１．１に、ＤＤＡについてのソースコードリストを記載する。
【００９４】
上記の検討において、従来のラスタディスプレイに関してＤＤＡを記載してきた。発明の局面に従って、ラスタライゼーションが実行される基底を変更することにより、ラスタライゼーション技術はランク−１格子に変換される。このように変更することは、ラスタライザが、直交座標系から対応するランク−１格子の基底によって形成された座標系へと切り換わることを意味する。従って、発明の局面に従って、ラスタライゼーションプロセスが、画素上でこれ以上動作するのではなく、格子セル上で動作することが理解されるであろう。
【００９５】
視覚化のために、各格子セルは、ミンコフスキー縮小格子基底によって結合された基本平行六面体の中央におけるサンプルと解釈される。各セル（ｘ，ｙ）は、格子座標において、すなわち、格子基底によって形成された座標系においてアドレス指定される。格子座標の使用は、図１９Ａおよび図１９Ｂに図示する。図１９Ａは、格子グリッド上で格子セル（０，２）の強調を図示するグラフ４３０を示す。図１９Ｂは、ｍａｘ−ｍｉｎ−ｄｉｓｔ格子Ｌ（５７６，１５５）上で（１，３）から（７，１４）へ延びる線のラスタライゼーションを図示するグラフ４４０を示す。図１９Ｂにおける強調された（影付きの）格子セルは、スキャン変換された線を表す。
【００９６】
できるだけ簡単にかつラスタライゼーションが実行される格子を独立して線を特定するため、スキャン変換技術は、その端点が単位正方形上の直交座標で与えられると仮定する。格子座標は、このような点を格子基底に変換することで、および変換された点が該当する格子セルを決定することで得られる。このような２つの格子セルの座標が、次に線の始点と終点を規定する。付属書のセクション３．１．２に、ランク−１格子上でのＤＤＡラスタライゼーションのためのソースコードリストを記載している。図２０は、表４５０を示し、この表は、図１９Ｂにおける（１，３）から（７，１４）に至る線のラスタライゼーションのための§３．１．２コードリストによって実行された単一のステップを記載する。図２０表４５０の最終行には、理想的線を近似する格子セルが含まれる。
【００９７】
図１９Ｂにおいて、理想的線は、点
2009501966.tif 000243
によってもともとは規定される。格子座標における変換は、
2009501966.tif 000244
を生じる。
2009501966.tif 000245
が、格子セル（１，３）内に存在し、
2009501966.tif 000246
が、（７，１４）内に存在するので、線は、始点（１，３）と終点（７，１４）によって認識される。
【００９８】
直交座標における点（ｘ，ｙ）と、
2009501966.tif 000247
を有する格子基底
2009501966.tif 000248
を仮定すると、
2009501966.tif 000249
であり、ここで、（ｕ，ｖ）は、格子基底における点（ｘ，ｙ）の座標を表す。基底行列
2009501966.tif 000250
は特異ではないので、座標（ｕ，ｖ）は、
2009501966.tif 000251
の結果である。
これは、付属書セクション３．１．３に記載のコードリストにおいてインプリメントされる。同リストは、さらにシフトした格子の座標系への変換を取り扱う。格子シフトは、基底に影響を与えることなく全体の格子を平行移動するだけであるので、シフトベクトル
2009501966.tif 000252
も、格子基底へと変換される。次に、変換されたシフトは、（ｕ，ｖ）へと適用される。格子座標中の点（ｕ，ｖ）が属する格子セル（ｃｘ，ｃｙ）は、その成分の端数を切り捨てること、すなわち
2009501966.tif 000253
で算出される。
この技術は、付属書のセクション３．１．４に記載のコードリストにおいてインプリメントされるｄｅｔｅｒｍｉｎｅＬａｔｔｉｃｅＣｅｌｌと呼ばれる方法と同じである。線の始点と終点の両方が一旦格子座標へ変換されると、ラスタライゼーションが上述の§３．１．１コードリストと同様に実現される。唯一の違いは、線上の次の点（ｘｉ＋１，ｙｉ＋１）の算出にある。
2009501966.tif 000254
の代わりに、
2009501966.tif 000255
が計算される。分母は変化することが無いので、分子（ｎｏｍｉｎａｔｏｒ）のみが各ステップで累算されなければならない。除算は、強調されるべき格子セルを決定するために実行されるのみである。このようにして、切り捨て誤差の蓄積を回避することができる。｜Δｙ｜＞｜Δｘ｜を仮定すると、ｎ＝｜Δｙ｜ということになる。
2009501966.tif 000256
その場合、ｙｉは、各ステップにおいてちょうどｓｇｎ（Δｙ）だけ増分されなければならない。それ故、上記アルゴリズムにおいて、ｙｎｏｍはｙ０によって、ｙｄｅｎｏｍは１によって初期化される。同じことが
2009501966.tif 000257
の場合に当てはまる。
図１９Ｂグラフ３９０に示す線へ§３．１．２コードを適用することで、Δｘ＝７−１＝６；Δｙ＝１４−３＝１１；ｎ＝ｍａｘ｛６，１１｝＝１１，ｘｎｏｍ＝１・１１＝１１，ｘｄｅｎｏｍ＝１１，ｙｎｏｍ＝３およびｙｄｅｎｏｍ＝１を得る。
【００９９】
基本平行六面体の中央として格子セルを表現することにより、０．５が§３．１．２コードにおいてｘｉ＋１とｙｉ＋１の両方に加えられる。すなわち、
2009501966.tif 000258
である。理想的線に最も近似する格子セルの座標は、§３．１．１に記載のコードに類似して、すなわち
2009501966.tif 000259
によって認識される。
【０１００】
次に、格子基底ラスタライゼーション技術をクロウのアルゴリズムに関して記載する。一式の頂点と辺で与えられた多角形を充填する画素を求めることで多角形はラスタライズされる。クロウのアルゴリズムは、頂点が整合が取れた順序であり、変換されるべき多角形が凸であることを仮定している。しかし、各多角形は、凸多角形に分解できるので、この要件は制限を呈しない。
【０１０１】
クロウのアルゴリズムは、水平走査線と垂直走査線の両方におけるコヒーレンスを活用する。水平走査線を底部から頂部まで繰り返し、アルゴリズムは、各走査線においていずれの画素が多角形の内部であるかを、水平コヒーレンスについての増分ジョルダンテスト（ｉｎｃｒｅｍｅｎｔａｌ  Ｊｏｒｄａｎ  ｔｅｓｔ）によって決定する。ジョルダンテストは、多角形の内部からの任意の光線は、多角形の辺に奇数回交差するというジョルダン曲線定理に基づいている。凸多角形のみが考慮されるので、現在の左辺と右辺上に点ＶｓｃａｎＬｅｆｔおよびＶｓｃａｎＲｉｇｈｔによって境界が成された、走査線当たり唯一の区間が存在する。このような点が、ＤＤＡアプローチにより垂直コヒーレンスを利用することで求められる。
【０１０２】
この技術は、最小ｙ値を有する頂点ｂｏｔを求めることで開始される。いまだ考慮されていない頂点が存在する限り、アルゴリズムは、適切な左辺Ｖｌｅｆｔ→ＶｎｅｘｔＬｅｆｔおよび右辺Ｖｒｉｇｈｔ→ＶｎｅｘｔＲｉｇｈｔを決定することで進行する。ここで開始において、Ｖｌｅｆｔ＝Ｖｒｉｇｈｔ＝ｂｏｔである。上方に走査する間、このような辺が現状の走査線に渡っており、かつ適切な区間が引かれたかがチェックされる。標準画素表示のためのクロウのアルゴリズムを、付属書の§３．２．１のコードリストに記載する。そこでは、頂点が反時計回りの順であることを仮定している。図２１は、§３．２．１コードリストに使用された変数の説明を記載する表４２０を示す。
【０１０３】
ランク−１格子上の凸多角形をラスタライズするために、上述と同じアプローチが使用される。これは、直交座標系ではなく、特定のランク−１格子Ｌ（ｎ，ａ）の基底によって結合された座標系の中で、アルゴリズが実行されるということを意味する。従って、Ｌ（ｎ，ａ）のミンコフスキー縮小基底の第１の基底ベクトルｂ１が水平座標軸に対応し、第２の基底ベクトルｂ２が垂直座標軸に対応する。ラスタライゼーションアルゴリズムは、頂点の配列とこの配列のサイズとを引数として取る。
【０１０４】
§３．１．２に記載のコードリストによると、反時計回りの順であるべき頂点は、直交座標系で正方形上で与えられていると仮定している。このような頂点を格子基底に変換した後、§３．２．１のコードリストと同じ方法で、１つの例外に至るまでラスタライゼーションをインプリメントすることができる。すなわち基本的ラスタライゼーションアルゴリズムは§３．２．４におけるコードリストに示したのと同じままである。最小ｙ−値を有する頂点ｂｏｔを求めた後、アクティブな辺Ｖｌｅｆｔ→ＶｎｅｘｔＬｅｆｔおよびＶｒｉｇｈｔ→ＶｎｅｘｔＲｉｇｈｔを維持することで、アルゴリズムは上方に走査する。頂点が反時計回りの順であるという仮定によって、ＶｎｅｘｔＬｅｆｔおよびＶｎｅｘｔＲｉｇｈｔの指数（ｉｎｄｉｃｅｓ）が、ｌｉ＝（ｌｉ＋ｎ−１）ｍｏｄｎおよびｒｉ＝（ｒｉ＋１）ｍｏｄｎによって計算される。しかし、頂点は、元々直交座標系の単位正方形上で特定されるので、この順序は、格子基底において変更する可能性がある。直交座標変換後、なお頂点が整合が取れたままの順序であるとしても、現状の多角形区間を引くとき、確実に
2009501966.tif 000260
とするため、ＶｓｃａｎＬｅｆｔおよびＶｓｃａｎＲｉｇｈｔを交換する必要があり得る。これは、付属書のセクション３．２．２に記載のコードリスト中、
ｌｘ＝ｃｅｉｌ（ｌ．ｍ．Ｘ）；
ｒｘ＝ｃｅｉｌ（ｒ．ｍ．Ｘ）；
が、
ｌｘ＝ｌ．ｍ＿Ｘ＜ｒ．ｍ＿Ｘ？ｃｅｉｌ（ｌ．ｍ＿Ｘ）：ｃｅｉｌ（ｒ．ｍ＿Ｘ）；
ｒｘ＝ｌ．ｍ＿Ｘ＜ｒ．ｍ＿Ｘ？ｃｅｉｌ（ｒ．ｍ＿Ｘ）：ｃｅｉｌ（ｌ．ｍ＿Ｘ）；
に変更されなければならないことを意味する。さらに、ｄｒａｗＰｉｘｅｌ（ｘ，ｙ）ではなくｄｒａｗＬａｔｔｉｃｅＣｅｌｌ（ｘ，ｙ）を呼ぶ必要がある。
【０１０５】
図２２は、単位正方形上で
2009501966.tif 000261
によって規定された多角形のグラフ４７０を示す。格子Ｌ（５７６，１５５）の基底へ変換した後、多角形は、
2009501966.tif 000262
によって特定される。図２３Ａおよび２３Ｂは、さらに高解像度でレンダリングされた同一の多角形を表示するグラフ４８０および４９０を示す。
【０１０６】
ランク−１格子上でのラスタライゼーションの原理は、この章で例としてＤＤＡとクロウのアルゴリズムを考慮して記載してきたが、他のラスタライゼーションアルゴリズムにも適用することができ、例えば、線についてのブレゼンハムアルゴリズムや多角形についてのｙ−ｘラスタライゼーションアルゴリズムのようなものである。このようなラスタライゼーションアプローチの１つの欠点は、ほぼ垂直である辺やある程度水平である辺は、格子セルの形状のため非常にギザギザに見えるということである。そのような問題に対する１つの可能な解決は、従来のラスタディスプレイでなされたアンチエイリアシングにある。基本平行六面体を近くで見ると他の可能性が見えてくる。格子セルをその短い方の対角線に沿って（すなわち２つの三角形へ）分割することでドロネー三角形分割を使用し、全体の解像度を２倍とすることができ、それによりかなり滑らかな辺となる。これを図２４に示し、ここでこのアプローチが図２３Ａに示す多角形に適用されたグラフ５００を示す。
【０１０７】
上述のように、記載の技術は新たなディスプレイ技術のための基礎を提供する。最初のコンピュータモニターは、ディスプレイ上の指定された点間の経路に直接沿って電子ビームを動かすことで画像を作製した。従って、このようなベクトルディスプレイは、鮮明で滑らかな線を作製することができた。しかし、ワイヤフレームを描くのみで複雑度が限定された情景を表示できたのみであった。オシロスコープのような科学機器に通常使用されるものさえ、ラスタディスプレイに置き換わってきた。そのようなディスプレイは、このラスタ上の正方形として表現される画素の矩形グリッドで通常構成される。ベクトルディスプレイと比較すると、画像は走査線アルゴリズムによって作製される。さらに、画素は、個別にアドレス指定がなされ、ＣＲＴディスプレイの場合は、個別の赤色、緑色、および青色の燐によって着色がさなれ得る。
【０１０８】
矩形グリッド上でラスタライズする代わりに、ラスタライゼーションは上述のように格子点上で実行することができる。この方法は、ソフトウェアソリューションによって従来のラスタディスプレイ上でシミュレートすることができるが、次の方法で現在のグラフィックスハードウェア上で実行することさえできる。ラスタライザが、矩形格子上で動作できるだけであるので、情景は、第一のステップにおいて格子基底に変換されなければならず、これは、実際には矩形格子のねじれに対応する。このようなフレームの変更の後、グラフィックスハードウェア上で通常どおりラスタライゼーションを実行することができる。ラスタライズされた情景を表示するため、得られた画像は、画素基底に変換し直されなければならない。このような手順によれば、あたかもラスタライゼーションがランク−１格子上で直接に実行されたかのような同一の結果を生じる。
【０１０９】
このような考慮に基づいて、我々は、新たな概念のディスプレイ技術を導入する。正方形画素の行列ではなく、ラスタディスプレイは格子セルの行列と考えられ、すなわち、単一の画像要素は、ランク−１格子点のドロネー三角形分割（すなわちボロノイ図）によって得られたセルとして表現される。このことは、最大化された最小距離によって選択されたランク−１格子としてラスタディスプレイが概念化されているということを意味する。従って、画素の数が増大すると、画像要素は六角形グリッドに近似する。ランク−１格子によって画素レイアウトを構成することで、以下に記載のように、従来の矩形グリッドのように比較的小さい波動ベクトルを特徴とするランク−１格子のフィルタ特性を、ディスプレイは利用する。従って、周波数が増大するにつれフーリエ係数が減少する関数は、特別に良好な方法で近似することができる。任意数ｎの点、正確には格子セルについてランク−１格子が利用可能であるので、画素の数は自由に選択され得る。図２５は、２５６格子セルから構成されるディスプレイモジュールのレイアウト５１０を図示する。
【０１１０】
この概念は、技術的に様々な方法で実行することができる。第１の実施には、点光源のディスプレイが含まれ、例えば、図２５の小さい黒ドットで示した、各格子セルの中央に配列されているＲＧＢ−ＬＥＤである。ランク−１格子が最大最小距離によって選択されるので、ＲＧＢ−ＬＥＤは、最適な方法でスクリーン上に分布している。第２の実施には、単一の画素要素をカバーする面光源のディスプレイが構成されている。これは、薄膜トランジスタ（ＴＦＴ）ディスプレイおよび液晶ディスプレイ（ＬＣＤ）技術をそれぞれ産み出し、これらは、例えば有機発光ダイオード（ＯＬＥＤ）によって実現することができる。
【０１１１】
上述のように、ランク−１格子ディスプレイの全体の解像度は、格子セルをその短い方の対角線で分割することで２倍にすることができ、それにより、図２４グラフ５００に示すようにエイリアシングアーチファクトを減少させる。この原理は、面光源のレイアウトを適合することでハードウェアにおいて直接実現される。これを、モノクロディスプレイ５２０およびカラーディスプレイ５３０について図２６Ａおよび２６Ｂに示す。
【０１１２】
以上までは、ランク−１格子のドロネー三角形分割によって生じたセルによって画素レイアウトは決定されてきた。
2009501966.tif 000263
におけるドロネー三角形分割へ双対であるボロノイ線図によって、
2009501966.tif 000264
が、各格子点を集中としたほぼ六角形セルに区切られ得る。図２７は、最大最小距離ランク−１格子Ｌ（６４，１９）のボロノイ図５４０を示す。この意味で画素レイアウトを構成すると、実質的に六角形画素格子となる。例えば、自然の原理として、複眼中の個眼または網膜中の視覚センサーはこのように配列されている。六角形画素の概念は、六角形画像処理の関連で既に研究されてきており、例えば、ＳｍａｒｔＳｌａｂＬＥＤパネルに使用されている。
【０１１３】
記載の画素レイアウトの１つの長所は、曲線状の物体を滑らかに表示することである。これは、全ての隣接体が互いから一様な距離を有する、すなわち整合性が取れて接続されているという事実に基づく。このような画素レイアウトにより、ディスプレイに使用される基本色の数に画素の数を適合することで、カラーディスプレイが簡単に実現できる。これは、画素の総数が
画素の数・カラーセル
によって計算されるということを意味する。
【０１１４】
図２８Ａは、モノクロディスプレイ用の六角形画素のための面光源のレイアウト５５０を示す。図２８Ｂは、カラーディスプレイ用の六角形画素のための面光源のレイアウト５６０を示す。
【０１１５】
第３の実施において、センサーすなわち電荷結合素子（ＣＣＤ）カメラのフォトサイトのレイアウトが、ドロネー三角形分割またはボロノイ図のいずれかで得られたランク−１格子セルの形態を取る。
【０１１６】
第４の実施において、ランク−１格子パターンは、プロジェクタ技術に使用される。例として、デジタルライトプロセッシング（ＤＬＰ）集積回路のヒンジ付け微小ミラーは、このような様式で配列されている。
【０１１７】
第５の実施において、記載したパターンは、ディスプレイレイアウトとパララックスバリアの両方を実現するため、３Ｄモードが可能である３Ｄディスプレイに関して適用することができる。例えば、シャープＬＬ−１５１−３Ｄモニター、およびｗｗｗ．ｓｈａｒｐｓｙｓｔｅｍｓ．ｃｏｍに開示された他のモニターである。
【０１１８】
ランク−１格子は、継ぎ目無くタイル張りされ得るため、それぞれが同数の格子セルを有するｋモジュールのディスプレイを構成することが可能である。図２９Ａおよび図２９Ｂは、発明のこの局面に従ったディスプレイ５７０および５８０を示す。「２ｎディスプレイ」において、ディスプレイモジュールについてのセルの数は、２のべき乗であるように選択される。このようなタイプのディスプレイモジュールは、デマルチプレクサによって単一のセルが簡単にアドレス指定されるという長所を有する。モジュールの数ｋが同様に２のべき乗へ設定された場合、単一のモジュールは同じように制御され得る。図３０は、発明のこの局面に従ったシステム５９０の図である。同じレイアウトで同じ数の格子セルの小モジュールを製作することで、所望の解像度のディスプレイへ簡単に組み立てることができ、このようなディスプレイは、経済的に製造されることが可能である。
【０１１９】
さらに一般的には、２ｎディスプレイの概念は、コンピュータ技術の全局面に完全に適合する。メモリレイアウト、キャッシュライン、アドレス指定等の利用である。このスキームに従った画像の記憶は、２ｎディスプレイの利点から同様に恩恵を受ける「２ｎ画像」の概念へと導かれる。従って
2009501966.tif 000265
メモリ要件は、ページング（メモリ配置）に理想的に適合する。別の例として、２０．．．２ｎ画像として一連のテクスチャを記憶することによっては非常に効率的に実行できるＭｉｐＭａｐｐｉｎｇを当然にサポートする。
【０１２０】
図３１は、いくつかの２ｎディスプレイモジュールおよび画像についてのパラメータをそれぞれ列挙する表６００を示す。列挙されたサイズは、最大最小距離ランク−１格子がそれに従って選択された単一のモジュールについて提案された解像度を表す。
【０１２１】
４．ランク−１格子によるアンチエイリアシング
図３２は、ランク−１格子によるアンチエイリアシングについての発明の別の局面に従った方法６１０のフローチャートを示す。ステップ６１１において、ランク−１格子は、生成されるべき合成画像の点に対応する最大最小距離関数に従って選択される。ステップ６１２において、選択されたランク−１格子は、モンテカルロまたは準モンテカルロのいずれかの点集合へのその収束に関して比較される。ステップ６１３において、この比較の結果に基づいてアンチエイリアシング関数が適用される。次の検討では、方法についての理論的基礎を発展させ、アンチエイリアシングに関する本発明の別の局面を記載する。
【０１２２】
図３３は、無限大のチェッカーボードの合成された画像６２０を示す。これは、ランク−１格子についての技術を発展させ説明するために使用されてきた。無限大の「現実の」チェッカーボードを仮定すると、理想的には、水平線においてハーフグレーへと平均化される、滑らかで連続的な画像が認められるであろう。しかし、コンピュータによって生成された合成画像はデジタル信号である。コンピュータは、有限の精度の離散値を記憶することができるのみであるため、コンピュータ生成画像は必然的に離散的であるはずでもある。従って、画像を生成する際、典型的に非周期性であり不連続である信号が、デジタル信号に変換されなければならない。
【０１２３】
チェッカーボードの画像を生成するため、元の信号をサンプリングする必要がある。連続から離散へのこのような遷移によって生成物（アーチフアクト）が生じることがある。例えば、ジャギーやモアレパターンの形態である。このような影響は「エイリアス」として知られている。連続信号ａを表示する一般のプロセスは、特定の位置においてａのサンプルを集めることで開始される。すなわち、サンプルパターンｓはａで乗算される。得られた信号ｂは、サンプリング位置においてスパイクを有するゼロ値関数からなる。元の信号を復元するため、ｂは、再構成フィルタｒに畳み込まれ、信号ｃ＝ｂ＊ｒを得る。ディスプレイ上で信号を再生するため得られた信号ｃは、フレームバッファメモリ域を反映する一式のサンプルでリサンプリングされる。最終的に、ディスプレイ再構成フィルタを有するｒの畳み込みが、実際に表示される信号を与える。実際に、サンプリングされた信号ｂは、各単一の画素について直接再構成され、それにより、リサンプリングステップが省略される。
【０１２４】
次の検討では、エイリアシングに関する信号処理理論の概説から始める。概説の後、ランク−１格子によるアンチエイリアシングの説明が続く。これには、テストパターンの収束の比較が含まれる。次に、ランク−１格子による適応的サンプリングの方法を説明する。さらに、ランク−１格子のフィルタ特性を説明し、レイトレーシング環境における深度適応的フィルタ処理のための方法を提供する。以下に記載のように、この方法は、カメラと対象の間の距離に応じて適切な再構成フィルタを自動的に選択する技術を提供する。最後に、ＲＧＢ−デシメーションと呼ばれるフィルタ処理技術を取り入れるＣｌｅａｒ−Ｔｙｐｅ技術によって、パターン付けされたディスプレイ上でランク−１格子によるアンチエイリアシングが試される。
【０１２５】
１次元連続信号の理想的サンプリングおよび再構成を以下に検討する。２次元の場合は、１次元の場合と非常に類似し、その複雑度のみが異なる。「理想的サンプリングと再構成」とは、連続帯域制限信号が一様にサンプリングされ、元の信号が最終的に再取得されるように再構成されるという意味である。
【０１２６】
理想的サンプリングと再構成は、次の式
2009501966.tif 000266
に要約することができ、ここで、それぞれ、ｆは元の信号または関数であり、ｓは一様なサンプリング関数、およびｒは再構成フィルタである。既述のように、信号ｆは、帯域制限されている必要がある。この要件の理由は、一様にサンプリングされた信号のフーリエ変換が、周波数空間で周期性となるからである。関数ｆは、
2009501966.tif 000267
の場合は、帯域制限されるべきと言われる。ここで、Ｆ（ω）は、ｆ（ｘ）のフーリエ変換である。これは、ｆのスペクトル
2009501966.tif 000268
が有限台を有するという意味である。周波数ω０は、ｆについてのカットオフ周波数と呼ばれる。ω０＝∞の場合は、関数ｆは帯域制限されない。
【０１２７】
第１のステップにおいて関数ｆは、次の式
2009501966.tif 000269
に与えられるように、シャー関数によって一様にサンプリングされる。サンプリングは、ｆとシャー関数を乗算することによりなされる。
2009501966.tif 000270
ｆｓ（ｘ）のフーリエ変換を計算するため、畳み込み定理に従って、ｆ（ｘ）およびｓ（ｘ）のフーリエ変換は、周波数空間に畳み込まれなければならない。
2009501966.tif 000271
畳み込み積分を計算すると、
2009501966.tif 000272
を得る。
従って、ｆｓ（ｘ）のフーリエ変換は、繰り返し周期１／Δｘを有するｆ（ｘ）のスペクトルの周期的繰り返しである。
2009501966.tif 000273
の場合は、Ｆ（ω）のコピーは重ならないであろう。従って、
2009501966.tif 000274
に対して
Ｆ（ω）＝ΔｘＦｓ（ω）が成り立つ。しかし、
2009501966.tif 000275
の場合は、Ｆ（ω）の周期的繰り返しは、重なり累積するであろう。ｆ（ｘ）をその離散サンプルから再構成するためには、Ｆ（ω）の周期的繰り返しのため、逆フーリエ変換
2009501966.tif 000276
を行うことは充分ではない。
2009501966.tif 000277
は、
2009501966.tif 000278
における以外はゼロである信号となるであろう。従って、Ｆ（ω）のセンターコピーは、隔離される必要がある。
2009501966.tif 000279
の場合、
2009501966.tif 000280
について
2009501966.tif 000281
であるため、Ｆ（ω）は、Ｆｓ（ω）をボックススペクトル
2009501966.tif 000282
で乗算することで復元することができる。
周波数空間において、再構成は、
2009501966.tif 000283
によって実行される。
ボックススペクトルの逆フーリエ変換がｓｉｎｃ−関数となり、ｆｓ（ｘ）をｓｉｎｃ−関数
2009501966.tif 000284
で畳み込むことで時間空間のｆ（ｘ）が再構成される。
しかし、これは、
2009501966.tif 000285
の場合のみに有効である。サンプリング周波数が低すぎる場合、すなわち
2009501966.tif 000286
の場合は、ボックスフィルタ処理がＦ（ω）ではなくω’≠０についてＦ（ω）＋Ｆ（ω’）を除去するであろう。これはＦ（ω）がそのサンプルから復元不可能となる「エイリアス」と言われるなんらかの別のエネルギーが、Ｆ（ω）に加えられていることを意味する。このような考慮がシャノンのサンプリング定理に要約されている。
定理３（１次元一様サンプリング定理）
連続関数ｆは、カットオフ周波数ω０でｆが帯域制限され、かつ
2009501966.tif 000287
の場合、サンプリング周波数
2009501966.tif 000288
でその一様サンプルから完全に再構成することができる。
簡単には、定理は、帯域制限された関数ｆは、ω０のスペクトルにおいてサンプリング周波数が最大周波数ω０の少なくとも２倍高い場合、その一様サンプルから完全に再構成されることを記述している。ω０は「ナイキスト周波数」としても既知である。本明細書において、用語「アンダーサンプリング」は、ナイキスト周波数未満のサンプリングのことである。信号が、ナイキスト周波数を超えてサンプリングされる場合は「オーバーサンプリングされる」と言う。再構成フィルタは、時間空間で計算されるか周波数空間で計算されるかに依存する。時間空間においては、正確にサンプリングした信号をｓｉｎｃ−関数で畳み込む必要がある。一方で、周波数空間においては、Ｆｓ（ω）をボックススペクトルで乗算する必要がある。
【０１２８】
サンプリング定理が充足される場合でも、再構成された信号中に生成物が生じる場合がある。例えば
2009501966.tif 000289
を周波数空間において使用された再構成フィルタとすると、ω０を超えるエネルギーが総計Ｆ（ω）となるので、明らかにＦｓ（ω）・Ｒ（ω）≠Ｆ（ω）である。このような場合、使用される用語は「再構成エラー」である。不適切なサンプリング率によるエイリアシングに対して拙劣な再構成フィルタであるからである。
【０１２９】
しかし、コンピュータグラフィックスで使用される関数については通常該当しないが、サンプリング定理は連続関数を扱うことを考慮する必要がある。このことを、チェッカーボードをレンダリングする簡単な例によって実証する。
【０１３０】
図３３に表示されたチェッカーボード画像６２０は、各画素の中央に配置された１つのサンプルおよび５１２×５１２の解像度で一様にサンプリングされた。従って、サンプルパターンは、図３５Ａに示した格子６７０のような規則的グリッドを表す。サンプリング定理の点では、これは、ｐが２画素間の空間を表すとして、１／ｐのサンプリング周波数を有することを意味する。サンプリング定理を満たすため、１／ｐは、信号におけるカットオフ周波数の２倍高い必要がある。しかし、チェッカーボードは、多くの明瞭な辺を提供するので、信号空間においてコンパクトな台を伴う信号を有するが、これは周波数空間において同時にコンパクトな台を有することができないという問題が生じる。これは、信号が帯域制限されることができず、周波数がますます高くなるということを意味する。従って直接表現できない周波数＞１／ｐが存在し、これが図３３に示すようにエイリアシスとなる。次の検討において、アンチエイリアシングについてのさまざまな技術を、異なるサンプリングとフィルタ処理スキームを比較することで説明する。
【０１３１】
上述のように、有限幅の信号は通常、コンピュータグラフィックスで扱われる必要があるので、大半の場合
2009501966.tif 000290
を特徴とする。合成画像を生成するには、各画素について単一の色を何とか決定する必要がある。ｆ（ｘ）をできるだけ正確に再構成するための１つのアプローチは、画素ｘｐに現れている全ての多角形片の面積を解析的に算出し、得られる面積比に従ってそれらの色を平均化することである。しかし、このアプローチは、計算が高価であり、また場合によっては、現れている面積の解析的表現の欠如により不可能であることがわかっている。従って代替のアプローチは、数値解を使用することである。これは、画素あたりのサンプリング点の数Ｎを選択し、これらのサンプルからｘｐにおける多角形片の面積を推定することでなされ得る。サンプルは、画素あたり１回よりも高い周波数で取られるので、本明細書では記載したサンプリングを「スーパーサンプリング」と言う。１つの通常のスーパーサンプリングスキームは、各画素内でサンプリングパターンとしてｎ×ｎグリッドを使用し、サンプルを比例的に重み付けることで１つの値に平均化することである。これは、「画素積分（ｐｉｘｅｌ  ｉｎｔｅｇｒａｌ）」と記載することができる。
2009501966.tif 000291
この場合、サンプリング関数
2009501966.tif 000292
は、微細な一様グリッドを表し、再構成フィルタ
2009501966.tif 000293
は、各サンプルを等しく１／Ｎで重み付ける。
【０１３２】
１次元の場合をつぶさに見ると、スーパーサンプリング中に生じていることが明らかになる。
2009501966.tif 000294
を、各画素の中央において１つのサンプルを取るサンプリング関数とし、ｐは画素中央間の距離であるとする。サンプリング定理によると、周波数
2009501966.tif 000295
を超える任意のエネルギーは、再構成された信号において適切に表現できず、そのためエイリアシングとなる。画素あたりＮサンプルを取ることは、サンプリング周波数Ｎ／ｐとしてサンプリング関数
2009501966.tif 000296
を適用することを意味する。サンプリング定理によると、新たなナイキスト周波数は、
2009501966.tif 000297
である。各画素に１色が表示できるので、スーパーサンプリングされた信号を、カットオフ周波数
2009501966.tif 000298
を有する完全ローパスフィルタ
2009501966.tif 000299
で再構成する必要がある。画素レートで再構成された信号をリサンプリングする前に、新たなエイリアシングを防ぐためローパスフィルタが適用される。画素ラスタに対して正確に帯域制限された信号を得るために、カットオフ周波数
2009501966.tif 000300
を有してローパスフィルタＧ（ω）が選択される。このようにして得られた信号を画素レートでリサンプリングし、ディスプレイ再構成フィルタで復元することが可能である。既述のように、画像関数が画素レートでのみサンプリングされる場合、
2009501966.tif 000301
を上回る任意のエネルギーは、エイリアシスとなる。その後の再構成とローパスフィルタ処理を伴って、サンプリング周波数
2009501966.tif 000302
でスーパーサンプリングする効果は、
2009501966.tif 000303
を下回る任意のエネルギーでは、エイリアシスとなることが防がれるということである。従って、以前はエイリアシングに寄与していた範囲
2009501966.tif 000304
からのエネルギーが、スーパーサンプリングされた画像において正確に処理された。構成により
2009501966.tif 000305
であるので、再構成フィルタ
2009501966.tif 000306
は、通常、実際には適用されない。それに代えて、ローパスフィルタが単独で配置される。時間空間における完全な再構成フィルタは、無限の台を有するｓｉｎｃ−関数によって与えられる点に留意することは重要である。従って、我々は、新たな再構成誤差を導入し得る、ボックス−、ガウス−、または打ち切り（ｔｒｕｎｃａｔｅｄ）ｓｉｎｃ−フィルタのような近似を扱わなければならない。
【０１３３】
今までは、画素積分を解くため古典的なテンソル積アプローチが使用されてきた。各画素は、ｎ×ｎグリッドでサンプリングされる。そのようなサンプルパターンをさらに良く見極めると、ｎ×ｎサンプリング点がｎのみのように挙動する傾向にある。図３４に示すサンプリンググリッド６３０は、１６点ではなく、各水平走査線に１つ、４点のみでサンプリングすれば充分であったことを示す。上述のスーパーサンプリング法の別の欠点は、レンダリング時間がｎに関して２次式的に増加するという点である。あるいは、サンプリング点は、各画素においてランダムに配置され得る。このアプローチは、「確率論的スーパーサンプリング（ｓｔｏｃｈａｓｔｉｃ  ｓｕｐｅｒ  ｓａｍｐｌｉｎｇ）」として既知である。次の章では、１つの可能性のあるランダムサンプリングパターンを分析する。これは、独立同一確率分布の（ｉ．ｉ．ｄ．）（疑似）乱数に基づく。
【０１３４】
そのようなランダムサンプリングパターンの１つの重要な特性は、高度に構造化されたエイリアシングアーチファクトがノイズに変わるという点である。人間の目は、エイリアシングよりノイズに対して敏感ではないので、得られる画像は、いまだ誤差を含んでいるにもかかわらず、より良く見えるであろう。ノイズが低周波のものである場合は、さらに構造化されたアーチファクトとなるので注意が払われなければならない。積分のためにｉ．ｉ．ｄ．乱数を使用することで、各画素色の期待値が算出される。従って、我々は、上述のパラメトリックモンテカルロ法によって画素積分を全画素について同時に評価する。ランダムサンプリング分布に加えて、次の章では、２つの準モンテカルロ点集合、すなわちＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点およびランク−１格子も提供する。これらは、アンチエイリアシングのために特に有用である。さらに以下では、このようなサンプリングパターンが使用されて、図３３のチェッカーボード６２０のアンチエイリアシングされた画像を算出し、以下に導入した誤差ノルムに従ってこれらの収束を比較する。
【０１３５】
既述のように、境界縁、テクスチャ不連続等は、レンダリングされるべき合成画像において高周波を生じる。従って、通常、帯域制限されていない信号を扱う必要がある。入力データをプリフィルタ処理することで、帯域制限された信号を得ることができる。このように、上述のようなサンプリング定理は、単純な方法で実行することができる。しかし、複雑な形状、テクスチャ、シェーディングモデル、モーションブラー、等は、プリフィルタ処理がほぼ不可能となる。従って、通常のレンダリングシステムは、スーパーサンプリングによってエイリアシングアーチファクトを減少させる。
【０１３６】
本明細書で使用された基本的テストパターンは、各画素内に１またはｎ×ｍサンプルを有する規則的グリッドによって与えられる。このようなサンプリングパターンは既に詳細に上述してきた。サンプリング理論は一様格子に基づいているからである。各画素の中央の１つのサンプルを取ることは、一般にエイリアシングを導入する。また、画素あたりｎ×ｎグリッドを使用しても、帯域制限されていない信号の場合はエイリアシングを回避することができない。しかし、このサンプリングスキームは、付属書のセクション４．２．１に記載のコードリストに示すようにインプリメントしやすい。さらに、グラフィックスハードウェアにおいては、同時に各画素を統合するアキュミュレーションバッファによって効率的に実現されやすい。しかし、ｎ点は、各次元において必要とされ、テンソル積求積法の複雑度は、２次元の場合のサンプル数に２次式的に増大する。換言すると、サンプルの数および収束率は次元に依存し、これは「次元の呪い」として知られている。
【０１３７】
「ジッタードグリッド」サンプリングは、モンテカルロ推定量の変動を減少させる１つの技術である。この技術には、ｓ＝２について、同サイズのｎ層（サブ領域）へ単位立方体を分解し、各サブ領域内の１つのランダムなサンプルを取ることが含まれる。この技術の例を、図３５Ａおよび図３５Ｂに示す格子６４０と６５０に図示する。そのような目的のため、層の数ｎは、因数分解されなければならない。これは、任意に選択したｎが、
2009501966.tif 000307
の完全な除算を生じるという意味である。層化することにより、純粋にランダムなサンプルについて起こり得るように、サンプルは一箇所に集まることができない。従って、全体の単位立方体に渡ってサンプルの一様な分布が改善される。付属書のセクション４．２．２に、単位立方体内でｎ×ｍサンプルを有するパターンを生成するソースコードを記載する。さらに、ジッタ処理は、エイリアシングアーチファクトをノイズと交換するが、これは１次元の場合に容易に見られる。
【０１３８】
Ｌａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点集合は、基底ｂ＝２において（０，ｍ，２）−ｎｅｔを形成する。これは上述のように、この点集合が、低食い違いのｎ＝２ｍ点の点集合からなり、体積２−ｍの各基本区間が正確に１つの点を含むことを意味する。このサンプルパターンは、基底ｂ＝２における（０，１）−列であるＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ根基逆関数に基づいている。ｔ＞０については、無限点列は、基底ｂにおける（ｔ，ｓ）−列と規定され、
2009501966.tif 000308
の場合は、ベクトル
2009501966.tif 000309
は、（ｔ，ｍ，ｓ）−ｎｅｔを形成する。Ｌａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ根基逆関数は、付属書のセクション４．２．３に記載のコードリストによって計算される。成分ｉ／ｂｍを、基底ｂにおける（ｔ，ｓ）列の最初のｂｍ点に加えることで、（ｔ，ｍ，ｓ＋１）−ｎｅｔが生じる。我々の場合、ｎ＝２ｍとして成分１／ｎを加えることで、Ｌａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ根基逆関数から（０，ｍ，２）−ｎｅｔが拡張される。これを、付属書のセクション４．２．４に記載のコードリストに示す。
【０１３９】
別の準モンテカルロサンプリングパターンとして、上述のｍａｘ−ｍｉｎ−ｄｉｓｔ格子が適用される。層化に対して、ｎの因数分解が必要な場合は、ランク−１格子は任意数の点について生成され得るためサンプリングレートに制限が無い。画素サンプリングとスクリーン全体のサンプリングの両方に関心があるため、上述のシフトした格子の使用もなされる。格子パラメータとして、上記の格子捜索技術から結果が使用される。付属書のセクション４．２．５に記載のコードリストは、ｍａｘ−ｍｉｎ−ｄｉｓｔ格子とシフトした格子の両方を作製する。ｍａｘ−ｍｉｎ−ｄｉｓｔ格子の場合、ｘとｙ−解像度についてパラメータは１に設定されなければならない。さらに、ｓｈｉｆｔＸとｓｈｉｆｔＹはゼロでなければならない。
【０１４０】
これまでモンテカルロと準モンテカルロ積分を記載してきた。これら２つの技術の組み合わせによって、いわゆる乱列化準モンテカルロ積分が得られる。この技術は、全ての２乗可積分関数についてバイアスの無い推定値を提供し、従来の準モンテカルロ積分とほぼ同様に速い。乱数スクランブルは、ランダム化された点集合がそのネット特性を維持し、一様に［０，１）Ｓ上に分布するような方法で（ｔ，ｍ，ｓ）−ｎｅｔをランダム化する。２次元の場合、単位正方形は、１つの座標軸についてｂの等体積に分割される。これらの体積は、各レベルの反復で１つのランダム順列と置換される。その後、分割と順列ステップが、ｘ−およびｙ−座標軸について実施されている全手順とともに各体積について再帰的に繰り返される。付属書のセクション４．２．３は、説明した技術を効率的にインプリメントするコードリストを記載する。パラメータｒが乱数整数によって与えられ、点集合は、ＸＯＲ−演算によってランダム化される。ランダム化されたＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点集合が、付属書のセクション４．２．６のコードリストに記載のコードリストによって生成される。コードリスト§４．２．５の格子パターンは、各格子点に１を法とするランダムシフトを単に加えることでランダム化される。すなわち、
2009501966.tif 000310
である。付属書のセクション４．２．７は、説明した演算を実行するためのコードリストを記載する。さらに以下に、このようなサンプリングパターンが、それらの収束に関して比較される。
【０１４１】
テストパターンの収束を解析するために、２つの誤差ノルム、すなわちＬｐ−およびＨ１−ノルムが使用される。グレースケール画像ｆ（ｘ，ｙ）のＬｐ−ノルムは、次の
2009501966.tif 000311
ようにして計算される。例えば、ｐ＝１は、１−ノルムを生じる。
2009501966.tif 000312
ｐ＝２は、Ｌ２ノルム（ユークリッドノルム）を生じる。
2009501966.tif 000313
そして、Ｐ＝∞は、無限大ノルムを生じる。
2009501966.tif 000314
微分（ｄｅｒｉｖａｔｉｖｅｓ）のエネルギーを加えることでＨ１−Ｓｏｂｏｌｅｖノルムには、さらにノイズおよび画像の縁が考慮される。
2009501966.tif 000315
対応するテスト画像へ収束した基準画像の誤差ノルムを算出することで評価がなされる。その後、ｘ軸上にサンプルの数を、ｙ軸上に画素ノルムを有して得られた値が誤差グラフにプロットされる。
【０１４２】
次に、それらの収束に関して上記したテストパターンの比較を行う。サンプリングパターンはそれぞれ、画素ごとに、方形スクリーンの全体に適用される。テスト情景は、図３３に示すような無限に拡張するチェッカーホードからなる。これは簡単なレイキャスターから生成される。サンプルパターンに従って、各画素についてｎ個の光線がカメラから発射され、最も近い交点が決定される。無限平面で表現されたチェッカーボードと光線の交点が存在する場合は、ヒットポイントのｘ−およびｚ−座標を追加することでが色が決定される。２を法とする総計がゼロである場合は、色値として０．７５が返され、その他の場合は０．２５が返される。ボックスフィルタは、本例全体に渡って再構成フィルタとしている。このフィルタは、ｓｉｎｃ関数の粗近似であるだけであるので、上述の時間空間における理想的再構成フィルタであるにしても、再生誤差が導入され得る点に留意すべきである。
【０１４３】
上記したように、テストパターンは誤差グラフによって比較される。画素あたりのサンプリング点の数の増加について、テスト画像に対する基準画像の誤差ノルムが計算される。その後、得られる値は誤差グラフに図示され、こうしてｘ−軸上にサンプルの数が、ｙ−軸上に誤差ノルムが表示される。両軸は、指数目盛である。各画素あたり２５６×２５６サンプルを有するジッタを受けたグリッドサンプリングパターンを適用することで、基準画像が算出された。画像は、なおエイリアシングアーチファクトを含んでいる。このことは、再構成フィルタの選択によって幾分かは説明される。しかし他方で、画素あたりのサンプルの数をなお増加することによっては、状況は大きく変わらないであろう。基準画像は、こうして不正確な画像へと収束される。これは、積分が解析的に実施されたとしても間違った積分が計算されてきたという事実による。
【０１４４】
チェッカーボードの水平線の方に歩くと、チェッカーボードの単一のセルが徐々に小さくなる。従って、多数のセルが水平線近くの１つの画素に含まれる。画素に関して積分すると、結果はハーフグレーであると予測される。しかし、白と黒の、正確にはダークグレーとライトグレーのセルは、１つの画素において必ずしも同じ面積（ａｒｅａ）をカバーしないため、１つの色が他の色に勝る可能性がある。異なるテストパターンを比較する場合、このような考慮に留意を保つことが重要である。
【０１４５】
第１に、テストパターンは、一様、ジッタを受けた格子、ｍａｘ−ｍｉｎ−ｄｉｓｔ格子、ランダム化された格子、Ｌａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ、およびランダム化されたＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒを含む各画素について適用される。各画素について、ｎ個の光線がカメラからスクリーンへと発射され、得られる色値がボックスフィルタによって平均化される。その後、ランダム化されたサンプリングパターンは、各画素について再作製されなければならない。Ｈ１誤差ノルムのカーブを見ると、一様なグリッドが、最も悪い結果を提供することがわかった。チェッカーボードセルの縁は、画像信号に高周波数を導入するので、チェッカーボードは帯域制限されていない。さらに、サンプリングについて規則的パターンが使用される場合は、信号における構成は、サンプリング点における構成と組み合わされる。このことは、エイリアシングアーチファクトとそれによる高い誤差ノルムを説明する。サンプルの数を増加すると、上述のようにエイリアシングを弱めるだけである。
【０１４６】
ジッタを受けたサンプリングは、さらに良好な結果を生み出す。これは、そのフーリエ変換を検討することによって説明することができる。微小な「クリアゾーン」を周囲に有して原点にスパイクが存在する。従って高周波は弱められる。さらに、攪乱されたエイリアシングアーチファクトは、通常はノイズに変化する。ｍａｘ−ｍｉｎ−ｄｉｓｔ格子についての初期誤差ノルムは、一様でジッタを受けたグリッドの値にほぼ等しいにもかからず、誤差は、サンプルの数が増加すると非常に速く減少する。Ｌａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒサンプリングパターンの誤差曲線とｍａｘ−ｍｉｎ−ｄｉｓｔ格子がほぼ一致して、同一の値に収束する点も見ることができる。このような２つの点集合は、低食い違いを有するという重要な特性を共有する。実際、それらの食い違いは、より良好に一様に分布したサンプリング点を有し、規則的かつジッタを受けたグリッドの食い違いよりもさらに小さい。
【０１４７】
しかし、ｍａｘ−ｍｉｎ−ｄｉｓｔ格子についてｇｃｄ（ｎ，ａ）＝１が該当する点に注意することが重要である。このような種類の格子と、ｎがａと互いに素では必ずしもない（すなわちｇｃｄ（ｎ，ａ）＝１が捜索アルゴリズムにおいてチェックされない）格子を比較することで、後者がより悪い結果を提供することがわかる。これは、互いに素の特性が、格子点の完全な低次元投影を確実とし、これによりラテンハイパーキューブ特性を提供するという事実のためである可能性がある。
【０１４８】
次に乱列化準モンテカルロ点を考えると、ランダム化した格子とランダム化したＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒサンプリングパターンの両方が、これらの決定論的初期誤差よりも小さい初期誤差を有することが理解されるであろう。しかし、誤差曲線がすぐにほとんど一致することがわかってきた。また、両方のランダム化した点集合は、それらの誤差ノルムに関して非常に類似して挙動する。しかし、ランダム化したＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点が、ランダム化したｍａｘ−ｍｉｎ−ｄｉｓｔ格子よりもわずかに良好な結果に到達することがわかってきた。決定論的な、およびランダム化した点集合は、それらの収束に関してほとんど違いが無いにもかかわらず、これらのパターンによって生成された画像は、特に比較的小さいサンプリングレート（＜３２）について外観に関して互いに区別される。
2009501966.tif 000316
に対して、決定論的および乱列化準モンテカルロサンプリングパターンは、同じ結果を提供する。すなわち、これらは同一の画像に収束する。
【０１４９】
次に、（ランダム化した）ｍａｘ−ｍｉｎ−ｄｉｓｔ格子およびＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点が、全体の方形スクリーン（ｘＲｅｓ＝ｙＲｅｓ）上で使用される。すなわち、これらのサンプリングパターンが、［０，１）２から［０，ｘＲｅｓ）×［０，ｙＲｅｓ）へとスケーリングされる。画素あたり特定の数ｎのサンプルを得るため、サンプリング点の数は、ｘＲｅｓ・ｙＲｅｓ・ｎと選択されなければならない。テスト画像は、上記のスキームに類似して作製される。各画素についてのサンプリング方法が呼び出されてその方法の中でサンプリング点について繰り返す代わりに、全サンプリング点が一度繰り返されて、各点についていずれの画素に属するかが決定される。これに関して、１つのバッファが色値を蓄積し、別のバッファが各画素についてヒットの数を格納する。全サンプリング点を処理した後、これら２つのバッファは、ボックス再構成フィルタに関して各画素について色値を平均するために使用される。
【０１５０】
画素あたりの１つのサンプリングパターンを有する誤差グラフを、スクリーン全体についての誤差グラフと比較すると、後者の全体の誤差が前者をはるかに凌ぎ、また比較的高いレベルで収束するということがわかるであろう。決定論的サンプリングパターンが、画素基底に適用されると、隣接する画素が同じようにサンプリングされる。ｍａｘ−ｍｉｎ−ｄｉｓｔ格子のランダム化は、各画素内での格子パターンのランダムシフトをもたらす。パターン自体は、同じままである。すなわち各画素は、同じではあるがランダムにシフトした格子でサンプリングされる。全体のスクリーンについて１つのパターンを使用することで、このような関連性は消失する。従って各画素は、一様に画素を必ずしもカバーするわけではない異なる点によってサンプリングされる。これにより、特に低サンプリングレートについて画像は非常にノイジーとなる。画素あたりに適用された、ランダム化されたＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点を考慮すると、選択されたランダム化によって点のネット構造が保たれていることは覚えておくべきである。従って、隣接する画素は、さらに一様にサンプリングされる。ランダム化されたＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点が、スクリーン全体にスケーリングされた場合は、これは、もはや当てはまらない。これは、非常にノイジーとなる縁において通常顕著である。
【０１５１】
スクリーン全体をサンプリングしても、画素あたりのサンプリング点の数ｎは、なお興味あるものである。各画素内にｎサンプルを得るためには、ｘＲｅｓ・ｙＲｅｓ・ｎサンプルが生成されるべきである点は既述してきた。ｎ＝２ｍ点についてのＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒパターンが、基底ｂ＝２において（０，ｍ，２）−ｎｅｔを表すので、スクリーン解像度は、２のべき乗として選択されなければならない。サンプリング点の数が、ｎ＝１についてｘＲｅｓ・ｙＲｅｓ・ｎ＝２ｍに等しい場合は、各画素は、体積
2009501966.tif 000317
の基本区間として取られ得る。ｎ＞１について、各画素は、体積
2009501966.tif 000318
のｎ個の基本区間を含む。従って、各画素は同数の点によってサンプリングされる。しかしこのことは、上述の、図３９Ａおよび３９Ｂに示したグラフ７２０および７３０に図示したｍａｘ−ｍｉｎ−ｄｉｓｔ格子については該当する必要はない。これらの図は、グラフ７２０においてはｍａｘ−ｍｉｎ−ｄｉｓｔ格子Ｌ（２６２１４４，５４９）で、グラフ７３０においてはシフト（２５９，０）でシフトした格子Ｌ（２６２１４４，５４９）で、カバーされた５１２×５１２の解像度の最初の５×５画素のスクリーンを示す。２点を含む画素や１点のみを含む画素もあるので、合計５１２・５１２点に対して全くサンプリングされていない画素が存在するはずである。従って、ｘＲｅｓ×ｙＲｅｓの解像度についてのｘＲｅｓ・ｘＲｅｓ・ｎサンプリング点は、画素あたり平均ｎ個の点が存在することのみを意味する。このことは、上述のように画素あたり同数の格子点を確保するシフトした格子について捜索するモチベーションを提供する。付属書のセクション２．１．４におけるコードリストによって生成された有効なシフト
2009501966.tif 000319
を伴う格子Ｌ（２６２１４４，３７３０３）について得られるチェッカーボードを比較すると、シフトした格子は、純粋なｍａｘ−ｍｉｎ−ｄｉｓｔ格子よりも優れているように見える。しかしシフトした格子は、ｘＲｅｓ・ｙＲｅｓ・１サンプリング点の数について遜色があるのみであるにしても、純粋なｍａｘ−ｍｉｎ−ｄｉｓｔ格子よりもはるかに収束が悪いということがわかってきた。従って、シフトした格子Ｌ（１０４８５７６，１０２３５）で生成されたチェッカーボードは、スクリーン全体をｍａｘ−ｍｉｎ−ｄｉｓｔ格子Ｌ（１０４８８５７６，３３９１９）でサンプリングすることで生成されたものよりも多くのエイリアシングアーチファクトを含む。これは、シフトした格子が、最大最小距離という点で理想的ではないという事実に基づいている可能性がある。というのは、上述のように、そのｍｉｎ−ｄｉｓｔが最大限の可能な最小距離とおそらくは等しくない有効なシフトを提供する最初の格子が選ばれているからである。従って、純粋なｍａｘ−ｍｉｎ−ｄｉｓｔ格子のみが比較のために使用された。
【０１５２】
スクリーン全体をサンプリングする場合、決定論的およびランダム化したサンプリングパターンの誤差曲線は、ランダム化したｍａｘ−ｍｉｎ−ｄｉｓｔ格子の初期値を別として、完全に一致するということに気付いてきた。ランダムシフトは、格子セル内で効果を有するのみである（すなわち、シフトは基本平行六面体に有効に含まれる）ので、全格子に対してわずかな寄与をするのみであり、従って画素へほんの微小なレベルのノイズを生じる。しかし、上記したようにともかく画像は非常にノイジーであるため、ランダム化による別のノイズはほとんど注目されない。
【０１５３】
比較的低いサンプリングレートにおいて、ｍａｘ−ｍｉｎ−ｄｉｓｔ格子は、Ｌａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点よりもさらに多くのエイリアシングを生じる。ランク−１格子は、実際に一様であるため、すなわち規則的であるか、またはＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点と比較してある程度周期的なサンプリングパターンであるため、パターンにおける構造が、水平線近くの高周波を規則的にサンプリングすることができ、そのためエイリアシングとして現れる新たな構造が生成される。従って、Ｌａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点は、限界においてｍａｘ−ｍｉｎ−ｄｉｓｔ格子よりもわずかに良好なアンチエイリアシングを行う。
【０１５４】
今までのところ、テストパターンの収束は、Ｈ１−ノルムによって評価されてきた。Ｌ２−ノルムが、代わりに選択されることも可能であった。Ｌ２−ノルムは、非常に類似する結果を提供するが、縁のエネルギーを反映しないため低い誤差レベルにおいてである。結局、テストパターンは基準画像に収束するが、これは実際には間違った積分の数値的近似を表す。しかし、理想的な再構成フィルタを使用しない点が考慮されなければならない。Ｌａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒおびｍａｘ−ｍｉｎ−ｄｉｓｔ格子サンプリングパターンは、最速の収束レートを示し前者は後者を凌ぐ。
【０１５５】
５．ランク−１格子による適応的改良とフィルタ処理
次に、ランク−１格子による適応的改良とフィルタ処理のための技術を記載する。図４０は、発明のこの局面に従った方法７４０のフローチャートを示す。ステップ７４１において、生成されるべき合成画像における点に対応してランク−１格子が最大化した最小距離関数に従って選択される。ステップ７４２において、格子がディスプレイスクリーン全体にスケーリングがなされる。ステップ７４３において、初期サンプリングパターンとして格子を使用して低解像度で画像がサンプリングされる。ステップ７４４において、レンダリングされるべき画像の初期近似が、初期サンプリングパターンを使用して算出される。ステップ７４５において、改良基準が格子基底において評価されるように各格子点について改良基準が評価される。ステップ７４６において、サンプリング点が改良される必要があり得る画像の各画素について、改良テストを評価するため評価の結果が使用される。ステップ７４７において、サンプリングパターンが所定の基準に従って適応的に改良される。
【０１５６】
直前の検討において、スクリーン全体をサンプリングすることで、画像合成のため最大最小距離を提供するランク−１格子が使用された。得られる画像を考慮すると、単一の画素がライトグレーまたはダークグレーのチェッカーボードセルで完全にカバーされる大きな領域が、カメラの近傍には存在し、その一方で水平性線近傍には多数のチェッカーボードセルが１つの画素内に該当していることに気付くことができる。一般化すると、一定であるかまたはゆっくり変化する値を含むコンピュータグラフィックスに多くの信号が存在する。その結果、そのような領域においては、少数のサンプルを使用するだけでレンダリングされるべき画像の良好な近似を得ることができる。他方、チェッカーボードの水平線近傍の場合と同様、領域によっては明瞭な縁と値の変化を特徴とするものもある。そのような複雑な領域においては、エイリアシングを制限するためサンプリングレートが増加されなければならない。これは、対応する信号をなんらかの基準に従って「適応的に改良した」「初期サンプリングパターン」によって、低解像度で第１にサンプリングすることで達成され得る。
【０１５７】
比較的高いサンプリングレートを必要とする複雑な領域を決定するためには、近傍のサンプルの集合、いわゆる「改良テストジオメトリ」が、信号の局部帯域幅を典型的には推定しようとするなんらかの改良テストに関して評価される。一般的には、改良テストは、画像空間および物体空間基準に分かれ得る。画像ベースの改良テストは、画像の局部強度値に基づく。最も簡単な形態で改良テストジオメトリのサンプルの強度が比較される。別のテストにおいて、差がユーザー規定の閾値を超える場合は、微小正方形を形成する４個のサンプルの最大および最小強度値が比較され、改良が示唆される。別のテストには、例えば、局部コントラストや強度統計が含まれる。また、なんらかの物体ベースの改良テストが存在し、それには、光線が特定の物体を交差するときや、全情景を包含するボックスの境界付けを行うとき、各サンプルの特徴付けを行うことにより、情景中の物体についての別の情報が含まれている。改良テストが、さらにサンプルが必要であると示唆する場合は、アルゴリズムは、新たなサンプリング点を生成することでサンプリングパターンを改良する。新たなサンプルを配置するいくつかの方法が開発されており、そのうち最も簡単なものは、ランダム改良パターンにある。通常、試験と改良のこのサイクルは、所定の基準に合うまで繰り返される。
【０１５８】
本発明の局面は、ランク−１格子が展開されることによる、適応的改良のための方法を提供する。初期サンプリングパターンとして、最大最小距離ランク−１格子がスクリーン全体にスケーリングされる。通常、レンダリングされるべき画像の初期近似は、第１のパスにおいて、初期サンプリングパターンによって算出される。その後、サンプリング点がおそらく改良される必要のある各画素について、改良テストが評価される。我々は、スクリーン全体をサンプリングするため、任意の画素（ｘ，ｙ）について、いずれの格子点が属するかを直接言及することはできない。従って改良基準は、各画素については各格子点について以外には適用されない。すなわち、対応する基準は格子基底において評価される。従って、第１のレンダリングパスには、格子点バッファにおける画像の計算がある。これは、各サンプリング点について光線をカメラから情景中に発射した結果が、バッファの対応する場所に格納されるという意味である。
【０１５９】
ｎをサンプリング点の数とし、サイズｎのフロートアレイとして点バッファを選択すると、サンプリング点
2009501966.tif 000320
についての得られた値は、位置ｂｕｆ［ｉ］に格納され、これにより逆に添字ｉによる任意の格子点
2009501966.tif 000321
に関する強度を特定しやすくなる。付属書のセクション４．３．２に記載のコードリストに使用された３つの可能性のある改良基準は、次の比較を備える。
・格子セル｛ｘ＋Λ｝（セクション１．２参照）のコーナーによって形成された、区間Ａ＝［ａ１，ｂ１）×［ａ２，ｂ２）についての関数ｆ（ｘ１，ｘ２）の局部変動
2009501966.tif 000322
・格子セル｛ｘ＋Λ｝のコーナーについて関数の上限と下限の差
2009501966.tif 000323
または
・中心差によって算出された勾配（階調）
2009501966.tif 000324
、正確には閾値Ｔに対する
2009501966.tif 000325
ノルム。
【０１６０】
任意のサンプリング点ｘｉについて改良テストがサンプリングパターンの改良を指示すること（すなわち改良テストが所定の閾値を超えること）を仮定すると、改良パターンは、初期サンプリングパターンの格子セル構造を利用することで、別の最大最小距離ランク−１格子として選択される。これは、ｘｉに属する格子セル｛ｘｉ＋Λ｝内で最大最小ランク−１格子Ｌ（ｍ，ａ）を決定することによって、改良パターンが特定されることを意味する。従って、ｍは初期サンプリングパターンに加えられた追加のサンプルの数を表す。これを、図４１の格子７５０に示す。改良パターンが、初期サンプリングパターン（すなわち初期ランク−１格子）の基底に依存するので、格子Ｌ（ｍ，ａ）は、ずれた（ｓｈｅａｒｅｄ）基底において捜索されなければならない。
【０１６１】
従って、付属書２．１．２に記載のコードリストに類似して、重み付けしたノルムによって実際の領域を捕捉することで［０，ｍ）２上で捜索がなされる。そのため、上述のように、格子点
2009501966.tif 000326
は、原点への距離を算出する前に、初期最大最小ランク−１格子の基底
2009501966.tif 000327
に変換されなければならない。任意の点（ｘ，ｙ）について変換は、
2009501966.tif 000328
によって与えられる。従って、点（ｘ，ｙ）の重み付けしたノルムは、
2009501966.tif 000329
によって算出される。
2009501966.tif 000330
は、上述の結果を生じる矩形領域を捕捉する。
【０１６２】
基底ベクトルは負の値も取り得るため、§２．１．２の重み付けしたノルムを、上記式のさらに一般化した重み付けしたノルムと交換することは充分ではない。オーバーフローテストにも影響するので、アルゴリズムは、代わりに倍長精度整数型（ｌｏｎｇ  ｌｏｎｇ  ｉｎｔｅｇｅｒｓ）に適合しなければならない。しかし、正方形が計算されているので、ｕとｖの絶対値が取られ得る。従って、オーバーフローテストにおけるＭＡＸＯＰのみが、
2009501966.tif 000331
に設定されなければならない。これは、付属書のセクション４．３．１に記載のコードリストに示す。
【０１６３】
上述の改良基準は、改良ｍａｘ−ｍｉｎ−ｄｉｓｔ格子の配置の仕方を示唆する。３つの場合全ては、実際のところ帰納的（ｒｅｃｕｒｓｉｖｅ）コロボフフィルタを共通に有するので、アンカー点ｘｉと一致するとき添字ｊ＝０を有する格子点は放棄される。最初の２つの場合においては、改良テストジオメトリには、対応するサンプリング点ｘｉに固定された格子セル｛ｘｉ＋Λ｝の４個のコーナーがある。従って、改良パターンは、図４１の格子７５０に示すように、正確にその格子セルの内部に配置される。勾配（階調）基準を使用して、改良テストジオメトリは、
2009501966.tif 000332
によって与えられる。これは、点ｘｉについて図４２に示す改良ジオメトリ７６０に示されている。ここで、改良パターンは、改良パターンの格子点がｘを中心とするように点
2009501966.tif 000333
に固定されている。勾配基準のための改良ｍａｘ−ｍｉｎ−ｄｉｓｔ格子の配置は、図４３の格子７７０に示す。この原理の１つの特別な場合は、いわゆる「
2009501966.tif 000334
サンプリングスキーム」によって表される。これは、係数
2009501966.tif 000335
でスケーリングされ、
2009501966.tif 000336
の角度だけ回転させた一様な格子の階層を利用するものである。このサンプリング技術が、物体空間において再帰的に動作するので、画像空間における点サンプルの繰り返し計算に適応されてきた。
【０１６４】
付属書のセクション４．３．２は、１つのレベルの改良についてランク−１格子による適応的改良のため記載された方法をインプリメントするコードリストを示す。引数として、初期サンプリングパターン、初期ｍａｘ−ｍｉｎ−ｄｉｓｔ格子（スクリーン解像度に合わされていない格子）、および改良パターン（ｒｅｆＬａｔｔｉｃｅ）を採用する。これらのパラメータは、初期化法によって事前に計算されている。初期サンプリングパターンの各点についての第１のループにおいて、光線を情景に発射することにより強度値が点バッファに格納される。各サンプリング点についての第２のパスにおいて、選択された改良基準が評価され、得られた値が所定の閾値を超える場合は新たなサンプルを生成する。このようなサンプルが初期サンプリングパターンのコピーに追加される。１つのレベルの改良のみが考慮されるので、比較的粗なレベルで既に作製されてきたサンプルを除外するためには、特別の配慮がなされなくてもよい。初期最大最小距離ランク−１格子の全点に渡って繰り返した後、改良されたサンプリングパターンは、画像空間における最終画像を算出するために使用される。
【０１６５】
改良基準を評価するため、改良ジオメトリに属する点の値が、点バッファからそのｘ座標を介してアクセスされる。これにより、付属書のセクション４．３．１．１、４．３．１．２、および４．３．１．３に示すソースコードインプリメンテーションが生じる。ここで
2009501966.tif 000337
は、実際のサンプリング点を表し、（ｂ１ｘ，ｂ１ｙ）および（ｂ２ｘ，ｂ２ｙ）は、初期ｍａｘ−ｍｉｎ−ｄｉｓｔ格子の基底ベクトルである。
【０１６６】
格子点
2009501966.tif 000338
についての対応する基準がサンプリングパターンの改良を示唆するときは、新たなサンプルが
2009501966.tif 000339
によって生成される。ここで、初期サンプリングパターンは、Ｌ（ｎ，ａ）を特徴とし、改良パターンは、
2009501966.tif 000340
によって与えられる。改良パターンを
2009501966.tif 000341
（勾配基準）に集中させる場合は、
2009501966.tif 000342
であり、それ以外の場合は、ｓ１＝０およびｓ２＝０である。これは、付属書のセクション４．３．１．４に記載のコードリストによってインプリメントされる。付属書のセクション４．３．２には、本明細書に記載の適応的改良技術を例示するコードリストを記載している。
【０１６７】
チェッカーボード情景が、３個の異なる強度値｛０．２５，０．７５，１．０｝のみを特徴とするので、Ｔ＝０．２５の閾値は、良好な選択を表す。アプローチの結果を見ると、新たなエイリアシングアーチファクトが水平線に現れていることがわかってきた。これは、チェッカーボードの水平線近傍の場合と同様、情景の「複雑な」領域に継ぎ目無くタイル張りする改良パターンの規則的構造によって説明することができる。このようなエイリアシング効果を制限する１つの可能性は、初期サンプリングパターンの格子セル内に改良パターンの格子点をランダムにシフトすることにある。従って隣接する格子セルは、同一のサンプリングパターンによってそれ以上には改良されない。例えば画像は、スクリーン全体にスケーリングされたｍａｘ−ｍｉｎ−ｄｉｓｔ格子Ｌ（２０９７１５２，１９３２９３）を使用して計算されてきた。初期サンプリングパターンとして格子Ｌ（１０４８５７６，３３９１３）および格子Ｌ（１０４８５７６，３３９１３）内でランダムにシフトされた格子Ｌ（１１，４）を採用して、§４．３．２コードリストが画像に適用された。改良テストとして、変動基準が適用された。改良の後、初期パターンは、６７９４５２によって総数１７２８０２８サンプリング点に拡張された。各画素は、画素あたり最大４８サンプルで平均６．６点にてサンプリングされた。サンプリングレートは、値の変化がシャープな領域のみで増加するので、改良された画像の質は、同時に比較的少数のサンプリング点を使用することにより改善された。しかし、改良パターンがランダムにシフトされなかった場合は、得られた画像に新たなエイリアシングアーチファクトが現れたであろうことに注意すべきである。
【０１６８】
上述のように、エイリアシングは、ナイキストレートを下回って信号をサンプリングした結果である。サンプリングの後、信号は再構成され媒体（ＴＦＴ、ＣＲＴ等）に投影される。再構成誤差は、信号が不正確にそのサンプルから復元されている場合に生じる。既に検討してきたように、時間空間における理想的な再構成フィルタは、ｓｉｎｃ−関数によって与えられる。しかし、この関数は無限台を有する。従って近似はボックス様であり、実際には代わりにガウスまたは三角フィルタが使用される。
【０１６９】
以上までは、一様サンプリングに重点を置いて検討してきた。非一様サンプルによるアンチエイリアシングも検討されているので、非一様な再構成も考慮する必要がある。関数法、変形法、反復法を含むいくつかのアプローチが使用されてきた。最も簡単なアプローチは、適切な再構成フィルタのコピーを、一様サンプリングされた信号の場合とちょうど同じく、再サンプル点に関して配置することである。これは局部フィルタ処理と言われている。フィルタはいくつかの基準について設計されている。まず第一に、フィルタは信号スペクトルの中央のコピーをあまり弱めてはいけない。他方でフィルタは、スペクトルのレプリカから追加のエネルギーの影響をできる限り減少させなければならない。さらに再構成フィルタは正規化、すなわち、
2009501966.tif 000343
されなければならない。ここでｐ（ｘ）はフィルタ関数である。換言すれば、各サンプルは、全フィルタ応答の総計が１となるフィルタによって重み付けされている。これは、重み付けした積分が実行されることを意味している。文献においては、非一様キュービックＢ−スプライン、ガウスの差分、およびＭｉｔｃｈｅｌｌ  ａｎｄ  Ｎｅｔｒａｖａｌｉフィルタのようないくつかのフィルタが提案されてきた。
【０１７０】
次の検討は、ランク−１格子のフーリエ変換に基づいて、そのような格子がサンプリングされるべき信号上でフィルタとして働くことを示す。距離パラメータによって適切なＢスプラインフィルタを自動的に選択する方法が提供される。最後に、Ｃｌｅａｒ  Ｔｙｐｅ技術によるＴＦＴ−スクリーン上でのアンチエイリアシングを検討する。
【０１７１】
合成画像を生成する場合、各画素について色値が決定されなければならない。これは、画素積分を計算することでなされる。上記でわかるように、パラメトリック積分が実行される。
2009501966.tif 000344
ここで、ｇ（ｙ）は画像関数を特定し、ｙは画像における画素をパラメータ化する。
【０１７２】
Ｅを、周波数の増加に従ってそのフーリエ係数が減少する一式の関数とする。
2009501966.tif 000345
がランク−１格子によって積分される場合は、このサンプリングパターンは、元にある関数上でフィルタ効果を有する（すなわち高周波をフィルタ処理する。）。これは、数値的に積分する場合に微小な誤差限界が存在することを意味する。積分誤差は、
2009501966.tif 000346
によって表現することができる。この誤差は、
2009501966.tif 000347
のフーリエ級数展開を使用して明確に計算することができる。ここで
2009501966.tif 000348
は、
2009501966.tif 000349
において評価されたｆのフーリエ係数を表す。式４．１２にｆ（ｘ，ｙ）のフーリエ級数展開を挿入することで、
2009501966.tif 000350
が導かれる。これについて今のところノルムを無視している。
2009501966.tif 000351
のフーリエ級数展開が完全に収束する
2009501966.tif 000352
という仮定のもとで、式４．１３における総和の順序は、次の
2009501966.tif 000353
のように変更することができる。こうして我々が格子を扱っているという事実を利用することができる。
2009501966.tif 000354
の場合は、
2009501966.tif 000355
であり、なんらかの整数ｋについて
2009501966.tif 000356
であることを思い出すと、式４．１４中の総和について
2009501966.tif 000357
である。従って、積分誤差は、
2009501966.tif 000358
として算出される。誤差は、双対格子
2009501966.tif 000359
の点において評価されると、ｆ（ｘ，ｙ）のフーリエ係数のみに依存すると理解されよう。フーリエ級数係数が
2009501966.tif 000360
の増加に伴って減少する、すなわち
2009501966.tif 000361
の場合は、誤差は、
2009501966.tif 000362
で限界とされる。従って、格子は良好なフーリエ特性によりフィルタとして作用する。Ｂ−スプライン再構成フィルタと組み合わせると、エイリアシングアーチファクトはかなり弱められる。１つの実施例において、テスト関数Ｚ
2009501966.tif 000363
が、スクリーン全体にスケーリングされたｍａｘ−ｍｉｎ−ｄｉｓｔ格子Ｌ（１０４８５７６，３３９１９）によってサンプリングされた。再構成フィルタとして増加する次数（ｄｅｇｒｅｅ）
2009501966.tif 000364
のＢ−スプラインフィルタＢｄが使用された。
【０１７３】
第１の画像において関数は、１／２半径（ｒａｄｉｕｓ）のボックスフィルタに対応する、次数０のＢ−スプラインフィルタによって再構成された。第２、第３、および第４の画像において、フィルタＢ１、Ｂ２、およびＢ３が適用された。Ｂ１は、画素半径１の三角フィルタであり、Ｂ２は、半径３／２の２次Ｂ−スプラインフィルタに対応する。Ｂ３は、２画素（半径）の台を有する３次Ｂ−スプラインフィルタである。従って、これら全てのフィルタは、コンパクトな台を有するという特性を共有する。台によって１つのサンプリング点は、数画素に影響することがある。対応する重み付けを総和すると１となり、これは、１つのサンプリング点のエネルギーが完全にそれらの画素間に分散されているという意味である。次数が上がるにつれ、それに応じて−スプラインフィルタの台が上がり、エイリアシングアーチファクトがますます抑制される。しかし、フィルタ処理カーネルの台が増大すると画像にぼやけが導入されもすることにも注意すべきである。
【０１７４】
図３３の一様にサンプリングされたチェッカーボードを見ると、エイリアシングアーチファクトが水平線近傍でさらに明確になってくることがわかるであろう。光線のチェッカーボードとのヒットポイントがカメラから遠ざかるにつれて、さらに多くのチェッカーボードセルが単一の画素をカバーする。換言すれば、信号周波数が水平線に向かって増大する。上述のように、サンプリングレートを増大することで完全にアーチファクチトを除去することは可能ではない。というのは、一方では、信号は、典型的には帯域制限されておらず、他方には、間違った積分が計算されている可能があるからである。時間空間において理想的再構成フィルタは無限台を有するので、ポストエイリアシングを減少するためには、三角、ガウス、またはＢ−スプラインのような、ｓｉｎｃ−関数を近似する適切なフィルタを注意深く選択する必要がある。
【０１７５】
先行するアプローチにおいては、いずれのフィルタを選択すべきかについての決定は、レンダリングの前になされてきた。すなわち、同一の再構成フィルタが各画素に適用されてきた。上述のように、カメラの距離が遠くなるにつれ、ｓｉｎｃ−フィルタへの近似がさらに良好になるはずである。例えば、ｒ＞０．５画素半径のガウス−フィルタを選択することでエイリアシングアーチファクトが減少しても、同時に、全画像はぼやけるであろう。この問題は、可能性のあるエイリアシングのレベルへフィルタ選択を適合することで解決することができる。これは、各サンプリング点について、フィルタ処理の必要度に応じて（すなわち、カメラからヒットポイントまでの光線の長に応じて）再構成フィルタが選択されることを意味する。従って、１つの画素は、異なるフィルタによって影響されることがある。再構成フィルタとして、次数ｋのベーシス（ｂａｓｉｓ）Ｂ−スプライン関数が選択される。すなわちＣｏｘ−ｄｅ−Ｂｏｏｒ帰納式
2009501966.tif 000365
によって与えられた、最大の多項式の次数ｄ＝ｋ−１のベーシスＢ−スプライン関数が選択される。元の定義において、パラメータｉは、ノット列の要素ｔｉの添字を特定する。我々は、ｔｉ＝ｉを設定するので、実際には一様Ｂ−スプラインを使用する。最終章で記載するように、このようなフィルタ関数は、コンパクトな台ｓｕｐｐＮｉ，ｋ＝［ｉ，ｉ＋ｋ）を有し、影響を及ぼす画素間に１つのサンプリング点の寄与を完全に分配する。さらにこれらは、最大の連続性を有し、すなわちＣｋ−２連続である。Ｂ−スプライン関数は、付属書のセクション４．４．１に記載のコードリストに例示するように簡単な方法でインプリメントすることができる。
【０１７６】
各画素の中央にフィルタカーネルを固定することが望ましいため、上記プロセス中のパラメータｉは、
2009501966.tif 000366
に設定され、それにより台を［ｉ，ｉ＋ｋ）から［−ｋ／２，ｋ／２）へシフトする。１つのサンプリング点（ｘ，ｙ）の重みを半径方向の２次元フィルタカーネルによって計算するため、Ｂ−スプラインベーシス関数が、
2009501966.tif 000367
について呼び出される。ここで、
2009501966.tif 000368
が整数グリッド上の画素をパラメータ化する。すなわち（ｍ＋０．５，ｎ＋０．５）は、画素中央のことである。サンプリング点（ｘ，ｙ）の重みｗについて、これは、
2009501966.tif 000369
を意味する。ここで、ｋは、特定される余地がある唯一のパラメータである。テスト情景の画像が、発射光線
2009501966.tif 000370
によって合成されると、パラメータλは、光線起点から平面（すなわちチェッカーボード）へその方向に沿った距離を測定する。ここで、Ｏは、光線起点であり、
2009501966.tif 000371
は、正規化された光線方向である。従って光線−平面交差から得られるこのパラメータｔは、次数（ｄｅｇｒｅｅ）、正確には選択すべきＢ−スプラインの次数（ｏｒｄｅｒ）についての測度として使用され得る。付属書のセクション４．４．２は、本検討に従ったソースコードを記載する。
【０１７７】
Ｂ−スプライン次数の選択についての１つの単純な経験則は、ｄ（λ）＝λ・ｌｏｇ（λ）・ｋとして
2009501966.tif 000372
によって与えられ、これをｋ＝０．０２５について図４４のグラフ７８０に示す。この決定関数を適用することで、カメラ近くで鮮明で同時に水平線近くでぼやけている画像が得られる。これは、ｓｉｎｃ関数へのフィルタカーネルの近似が、ｔの増加につれフィルタサポートの増加によっても改善するからである。付属書のセクション４．３．３は、上述のようにスクリーン全体のサンプリングを仮定した、本検討に従ったフィルタ処理スキームについてのソースコードを提供する。ソースコードは、全サンプリング点に関して繰り返され、各点についてカメラからスクリーンへ１つの光線を発射する。光線がチェッカーボードと交差する場合は、サンプリング点の重みが式４．１８に従って計算され、ヒットポイントの重み付けされた色がアキュミュレーションバッファ（ａｃｃＢｕｆｆｅｒ）に蓄積される。第２のバッファ（ｃｏｕｎｔＢｕｆｆｅｒ）は、重みを蓄積するのみである。各画素についての最終的な色を算出するため、重み付けされた色値の総計が、最終的にフィルタ重みの総計で除算される。
【０１７８】
上記のアルゴリズムにおける可変オフセットは、対応するサンプリング点（ｘ，ｙ）がその台（サポート）に存在する可能性がある画素を決定するために使用される。半径方向の２次元フィルタカーネルの場合は、サンプル（ｘ，ｙ）は、
2009501966.tif 000373
として、サンプルが属する画素
2009501966.tif 000374
の周囲の隣接する
2009501966.tif 000375
における全画素に影響することがある。これを、図４５のグラフ７９０に示し、ここで、中央の正方形は、１−画素と１．５−画素半径の両方のフィルタカーネルについてのサンプルによって影響される可能性がある１組の画素を規定する。
【０１７９】
上述してきたようにフィルタカーネルの次数は、その台のサイズを決定し、レンダリングアルゴリズムの動作時間に大きく影響する。従って我々は、特定の定数（付属書のセクション４．４．３のコードリストで７に設定されている）で次数を固定した。しかし、この定数およびＢ−スプライン次数の計算の両方は、レンダリングされるべき情景に依存する。
【０１８０】
記載のフィルタ処理スキームの１つの欠点は、フィルタカーネル間で滑らかな遷移が存在しないという点である。これは、フィルタ次数を表す異なる領域が互いに鮮明に分離されている場合に特に顕著である。滑らかな遷移を達成するため、次数ｄとｄ＋１の連続するフィルタの重みが線形的に補間される。すなわち、
2009501966.tif 000376
である。
2009501966.tif 000377
として、補間パラメータ
2009501966.tif 000378
は、次数ｄのＢ−スプラインが選択される閾値λｄへのλの接近度についての情報を提供する。γが増加すると、λがλｄ＋１に近づくため、同時にｗｄの影響が減少することでｗｄ＋１の影響も増加する。次数０と１のＢ−スプライン間の補間について、図４６におけるグラフ８００にこれを示す。付属書のセクション４．４．４のコードリストは、式４．１９および４．２０に従ったフィルタカーネル間の補間を取り込むことで、セクション４．４．３に記載のコードリストの適応的フィルタ処理スキームを拡張している。サンプル（ｘ，ｙ）が存在する台における画素の近傍を決定するため、可変オフセットが再び使用される。我々は、台の半径に関して大きさが異なる次数ｄとｄ＋１の２つのフィルタカーネル間で補間するので、近傍
2009501966.tif 000379
を考慮しなければならない。２つのフィルタカーネルの半径間の差が、ちょうど
2009501966.tif 000380
に等しいので。従って、近傍
2009501966.tif 000381
に関して繰り返すと充分であり、これは、付属書のセクション４．４．４に記載のコードリストで２つの入れ子のｆｏｒループによって達成される。２つのｆｏｒループ内のｉｆ−ｅｌｓｅ文は、異なるサイズのフィルタカーネルを考慮している。
2009501966.tif 000382
の場合は、サンプリング点（ｘ，ｙ）の重みｗは、ｗｄ＋１で与えられ、一方でｔ＜＝ｒｄの場合は、ｗｄとｗｄ＋１の間で補間が必要である。
【０１８１】
チェッカーボード画像に戻って、１つのサンプリング点の寄与が１を超えていないこと、すなわち１に対する１つのサンプル総計についての重みを確認するため、各ヒットポイントにおける色がハーフグレーに設定される。その後、付属書のセクション４．４．４および４．４．３に記載の両方のコードリストは、水平線でぼやけている一様なグレーの無限面となるはずである。
【０１８２】
ここで、ＣｌｅａｒＴｙｐｅ技術が本発明に関連するため検討する。画像が単一の正方形を表すと考えられるＣＲＴディスプレイに対して、ＴＦＴ（薄膜トランジスタ）またはＬＣＤ（液晶表示）ディスプレイの単一画素は、３つの分かれた「副画素」、赤、緑、および青のものから構成される。人の目は、このような三重子を１画素として認識する。ＣｌｅａｒＴｙｐｅ技術は、水平スクリーン解像度を３倍とするため、そのように直接アドレス可能な副画素を利用する。これは、水平線輝度解像度が、副画素解像度すなわち３倍の水平線スクリーン解像度によって与えられることを意味する。しかし、各副画素は、輝度源を表すのみではなく、その色によっても特徴付けられる。従って輝度解像度は、異なる色チャンネル上で３倍化される。「従来の」画像合成は、各画素についての光が、スクリーン上の単一のスポットから発する（すなわち３つの色、赤、緑、および青が重なり合う）ことを想定しているが、ＣｌｅａｒＴｙｐｅは、アンチエイリアシングについての異なる構造を考慮に入れる。ＣｌｅａｒＴｙｐｅは、ＬＣＤスクリーンのようなパターン付けされたディスプレイ上で文字の可読性を改善するため、アンチエイリアシングについての技術として導入された。同様の技術は、ビデオディスプレイの有効水平解像度を２倍とするため、ＡｐｐｌｅＩＩパーソナルコンピュータにおいて既に使用されていた。しかしＣｌｅａｒＴｙｐｅに対して、この副画素技術は、２つの副画素（すなわち緑と紫のもの）の１つの単一画素を構成した。
【０１８３】
従来は、画素は、「オン」または「オフ」のいずれかであり、図４７Ａに示す線部分８１０であるように、このことが傾斜のついた線がすっかりギザギザに見える理由である。標準的なアンチエイリアシング手順では、このような縁をぼやかすようにする。ＣｌｅａｒＴｙｐｅは、図４７Ｂに示す線部分８２０に示すように、隣接画素の一部を使用することで副画素構造を利用し、副画素の既存のパターンを拡張する。しかし、副画素の色を無視すると、色の不均衡による色縁が生じることとなる。ＣｌｅａｒＴｙｐｅは、知覚エラーメトリックによる色誤差と空間解像度の間のトレードオフをバランスさせる。これは、個別の副画素の輝度値を選択するため、フィルタ処理技術は人の視覚系のモデルをベースとして発展していることを意味する。得られる９個のフィルタ（入力と副画素色の組み合わせごとに１つ）は、ＴＦＴまたはＬＣＤディスプレイ上で再構成するとき知覚した誤差を最小化する。実時間インプリメンテーションを達成するため、９フィルタ法は、さらに簡単化されて、いわゆる「ＲＧＢデシメーション」が生まれている。入力画像の各色チャンネルをローパスフィルタによって前フィルタ処理した後、同一色の副画素の空間的場所にサンプルが取られる。すなわち副画素の変位を考慮してサンプリング（変位サンプリング）が実施される。ＲＧＢデシメーションの原理を、図４８に明示する。同図は、各出力副画素に集中した１画素幅ボックスフィルタを備えるローパスフィルタ８３０を図示する。ＬＣＤやＴＦＴディスプレイの中には、Ｒ−Ｇ−ＢではなくＢ−Ｇ−Ｒで副画素を配列するものもあるので、このアルゴリズムをインプリメントすると、ディスプレイ装置のＲＧＢ順序付けを処理する必要がある。さらに、我々は、ＣＲＴディスプレイが、副画素レベルでアドレス可能ではないことに留意しなければならない。従って、ＣｌｅａｒＴｙｐｅ技術は、ＴＦＴまたはＬＣＤディスプレイ上でのみ有効である。ＣｌｅａｒＴｙｐｅがアンチエイリアシングの局面を取り込んでいるため、それでもＣＲＴディスプレイの画質をわずかに改善もする。
【０１８４】
次のコードリストは、元々はフォントレンダリングの強調のため、スクリーン全体をサンプリングすることでチェッカーボードをレンダリングするために設計されており、ＣｌｅａｒＴｙｐｅ技術をインプリメントする。これは、サンプリング点の数が、少なくとも３・ｎｕｍ・ＲｅｓＸ・ＲｅｓＹでなければならないことを意味する。ここで、ｎｕｍは、副画素あたりの所望数のサンプルを表す。適切なｍａｘ−ｍｉｎ−ｄｉｓｔサンプリングパターンを生成するため、我々は、３倍水平解像度について重み付けしたノルムを用いて説明しなければならない。これは、付属書のセクション２．１．２に記載したコードリストでインプリメントされる。深度適応的フィルタ処理について最後のセクションに記載したように、クリアタイプレンダリングアルゴリズムは、重み付けした色値を累積するアキュミュレーションバッファ（ｔｍｐＢｕｆｆｅｒ）、およびフィルタ重みを累積するための付加バッファ（ｃｏｕｎｔＢｕｆｆｅｒ）を利用する。両方のバッファは、３倍水平解像度で初期化される。このような２つのバッファによって、チェッカーボードは副画素解像度でレンダリングされる。このようにして、ＴＦＴまたはＬＣＤスクリーンの各画素の赤および緑の副画素値が同じ場所において算出され、その後これらは表示される。このことは、赤と緑の副画素値をあたかも緑の副画素として同一場所に表示するかのように算出する、標準的アンチエイリアシングには当てはまらない。その結果、赤と青成分がそれぞれ右と左に画素の３分の１シフトするのでぼやけが生じる。フィルタは、各出力副画素に固定されている５個の副画素幅のボックスフィルタ
（数３７８）
2009501966.tif 000383
からの結果を重み付ける。局部色バランスをなお維持しつつサイドの副画素のエネルギーを減少するため、このフィルタはＲＧＢデシメーションについて選択された。ＲＧＢデシメーションの実施の後、各画素にその３つの副画素の色を割り当てることにより我々は画素解像度に戻る。換言すれば、ＴＦＴディスプレイは、このステップで副画素レベルで直接アドレス指定される。これは、最後の入れ子のｆｏｒループでなされる。
【０１８５】
無限大チェッカーボード画像へＣｌｅａｒＴｙｐｅアルゴリズムを適用する際に、フィルタ処理技術がチェッカーボード画像に見られる色エイリアシングを抑制し、滑らかな縁を生成することがわかった。ＣｌｅａｒＴｙｐｅは水平解像度の増大のみをするので、水平線の縁の近くでは、ほぼ垂直のものよりもさらに滑らかに見えることがわかった。しかし、信号周波数がカメラからの距離の増加に伴い増大するので、水平解像度を３倍化することでは、水平線近くのエイリアシングアーチファクトを補正することができない。
【０１８６】
図４９−５１は、無限大チェッカーボード画像をレンダリングするために使用される格子をいくつか例示する一連の図を示す。図４９は、
2009501966.tif 000384
であり、
2009501966.tif 000385
である一式の格子８４０を示す。図５０は、５１２×５１２にスケーリングされ、
2009501966.tif 000386
である一式の格子８５０を示す。図５１は、ＲｅｓＸ×ＲｅｓＹの解像度として、ｇｃｄ（ｎ，ａ）＝１である一式の格子８６０を示す。
【０１８７】
６．結論
２次元ランク−１格子に関して本明細書に発明の様々な局面を記載してきた。しかし、発明の範囲をこのような特別な場合に限定する意図はない。例えば、本明細書中に記載の技術は、ｓ次元（ｓ＞２）における最大最小距離ランク−１格子についての捜索に拡張されてよい。さらに、本明細書中に記載のスペクトルテストは、任意の領域における最大最小距離ランク−１格子の捜索をする目的のため単位正方形以外の領域に拡張されてよい。アンチエイリアシングに関して、格子の規則的構造による特定画像の水平線におけるエイリアシングを回避するため、ディスプレイスクリーン全体をサンプリングするためのいくつかの格子の使用に、記載した技術は拡張されてよい。本明細書に記載した適応的改良アルゴリズムは、いくつかのレベルの改良に拡張されてよい。また、特に水平線特定画像におけるＢ−スプラインフィルタにより生じたぼやけを制するため、適応的フィルタ処理方法に異法性フィルタ処理が含まれることがある。
【０１８８】
前述の記載には、当業者が発明の実施を可能とする詳細が含まれ、説明は本質的に例示的であり、その多くの修正および改変が、このような教示の利益を有する当業者に明白であると認識されるべきである。従って、本明細書の発明は、本明細書に添付の特許請求の範囲によってのみ規定され、特許請求の範囲は先行技術によって許容される限り広く解釈されることを意図している。
2009501966.tif 000387
2009501966.tif 000388
2009501966.tif 000389
2009501966.tif 000390
2009501966.tif 000391
2009501966.tif 000392
2009501966.tif 000393
2009501966.tif 000394
2009501966.tif 000395
2009501966.tif 000396
2009501966.tif 000397
2009501966.tif 000398
2009501966.tif 000399
2009501966.tif 000400
2009501966.tif 000401
2009501966.tif 000402
2009501966.tif 000403
【図面の簡単な説明】
【０１８９】
【図１】本発明が実施され得る通常のデジタル処理システムの概略図である。
【図２】本発明が実施され得る通常のパーソナルコンピュータ、または同様の計算装置の概略図である。
【図３】図３Ａは、フィボナッチ格子およびその双対格子をそれぞれ図示する一組のグラフである。図３Ｂは、フィボナッチ格子およびその双対格子をそれぞれ図示する一組のグラフである。
【図４】本発明の第一の局面に従った全体の方法を図示するフローチャートである。
【図５】フィボナッチ格子Ｌ（３４，２１）の図である。
【図６】図６Ａは、コロボフ格子Ｌ（８，１）を示す。図６Ｂは、コロボフ格子Ｌ（８，５）を示す。
【図７】点（２，４）から格子Ｌ（５，２）についての原点への距離の算出を図示するグラフである。
【図８】図８Ａは、六角形格子の基本平行六面体を示す。図８Ｂは、基本平行六面体の半分を表す正三角形を示す。
【図９】図９Ａは、単位正方形において選択された格子を図示する。図９Ｂは、実際の面積にスケーリングされた単位正方形において選択された格子を図示する。図９Ｃは、実際の面積において選択された格子を図示する。
【図１０】図１０Ａは、画素あたり正確に１つの格子点を正確に得るため、シフトする前のスケーリングされたサンプリング格子を示す。図１０Ｂは、画素あたり正確に１つの格子点を正確に得るため、シフトした後のスケーリングされたサンプリング格子を示す。
【図１１】有効なシフトを有するｍａｘ−ｍｉｎ−ｄｉｓｔ格子を記載する表を示す。
【図１２】有効なシフトの条件下で捜索技術に従って生成された格子を記載する表を示す。
【図１３】等距離平行線群で覆われた周期的に拡張された格子のグラフを示す。
【図１４】そのミンコフスキー縮小基底を有する格子を図示するグラフを示す。
【図１５】基底５における（０，２，２）−ｎｅｔを図示するグラフを示す。
【図１６】基底ｂにおけるいくつかの（０，２，２）−ｎｅｔｓについての格子パラメータを記載する表を示す。
【図１７】発明の別の局面に従ったランク−１格子を使用するラスタライゼーション法のフローチャートを示す。
【図１８】図１８Ａは、画素の強調とラスタグリッド上の線を図示するグラフである。図１８Ｂは、画素の強調とラスタグリッド上の線を図示するグラフである。
【図１９】図１９Ａは、画素の強調と格子グリッド上の線を図示するグラフである。図１９Ｂは、画素の強調と格子グリッド上の線を図示するグラフである。
【図２０】格子グリッド上の線のラスタライゼーションにおいて実施された単一のステップを記載する表である。
【図２１】凸多角形についてのクロウのラスタライゼーションアルゴリズムに使用された変数を記載する表である。
【図２２】２４×２４の解像度で格子Ｌ（５７６，１５５）上でラスタライズされた多角形を図示するグラフである。
【図２３】図２３Ａは、異なる解像度における格子グリッド上のラスタライゼーションを示す図である。図２３Ｂは、異なる解像度における格子グリッド上のラスタライゼーションを示す図である。
【図２４】格子のセルを２つの三角形に分割することで、多角形のスムーシングを説明する図である。
【図２５】最大最小距離格子を使用して構築されたラスタディスプレイを示す。
【図２６】図２６Ａは、モノクロディスプレイ用の面光源のレイアウトを示す。図２６Ｂは、ランク−１格子によるアンチエイリアシングのためのシステムにおけるカラーディスプレイのためのレイアウトを示す。
【図２７】最大最小ランク−１格子Ｌ（６４，１９）のボロノイ図を示す。
【図２８】図２８Ａは、モノクロディスプレイにおける六角形画素用の面光源のレイアウトを示す。図２８Ｂは、カラーディスプレイ用のレイアウトを示す。
【図２９】図２９Ａは、２５６個のセルをそれぞれ含む、４個のモジュールを備えるディスプレイの図を示す。図２９Ｂは、２５６個のセルをそれぞれ含む、４個のモジュールを備えるディスプレイの図を示す。図３１Ａは、個別のモジュールの正方形レイアウトを示す。図３１Ｂは、矩形レイアウトを示す。
【図３０】ディスプレイモジュールがデマルチプレクサによってアドレス指定されるシステムの図を示す。
【図３１】２ｎディスプレイと画像のためのパラメータを記載する表を示す。
【図３２】発明の別の局面に従ったランク−１格子によるアンチエイリアシングのための方法のフローチャートを示す。
【図３３】ランク−１格子によるアンチエイリアシングを図示するために使用された無限大チェッカーボードの画像を示す。
【図３４】４×４グリッドを有する画素サンプルの図を示す。
【図３５】図３５Ａは、一様な４×４パターンを示す。図３５Ｂは、各４×４層で１つのランダムサンプルを有してジッタを受けたグリッドを示す。
【図３６】図３６Ａは、別のノイズを有する元の周波数の再構成を図示するグラフである。図３６Ｂは、ノイズのみの復元を図示するグラフである。
【図３７】ｎ＝２４点に対するＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点集合を示す。図３８Ｂは、ランダム化したＬａｒｃｈｅｒ−Ｐｉｌｌｉｃｈｓｈａｍｍｅｒ点集合を示す。
【図３８】図３８Ａは、ｎ＝１６およびａ＝３についてのｍａｘ−ｍｉｎ−ｄｉｓｔ格子を示す。図３８Ｂは、同一のパラメータを有するランダム化した格子を示す。
【図３９】図３９Ａは、ｍａｘ−ｍｉｎ−ｄｉｓｔ格子Ｌ（２５２１４４，５４９）によって覆われた５１２×５１２の解像度を有するスクリーンの最初の５×５画素を示すグラフである。図３９Ｂは、シフト（２５９，０）でシフトした格子を示す。
【図４０】発明の別の局面に従ったランク−１格子による適応的改良のための方法を示す。
【図４１】格子Ｌ（１０４８５７６，３３９１９）のずれた基底において決定されたｍａｘ−ｍｉｎ−ｄｉｓｔ格子Ｌ（８，５）を示す。
【図４２】勾配基準の改良ジオメトリを示す。
【図４３】勾配基準についての改良ｍａｘ−ｍｉｎ−ｄｉｓｔ格子の配置図を示す。
【図４４】Ｂ−スプライン次数についての決定関数のグラフを示す。
【図４５】１画素半径と１．５画素半径の両方の台についてのサンプリング点の影響を説明する図を示す。
【図４６】ｄ＝０について次数ｄおよびｄ＋１の連続Ｂ−スプラインフィルタ間の補間を説明するグラフを示す。
【図４７】図４７Ａは、副画素構成を知らずに傾斜対角線をレンダリングする図を示す。図４７Ｂは、水平解像度を３倍化した後のレンダリングを示す。
【図４８】１画素幅ボックスフィルタを使用すＲＧＢデシメーションの図を示す。
【図４９】無限大チェッカーボード画像をレンダリングするために使用された格子を説明する図である。
【図５０】無限大チェッカーボード画像をレンダリングするために使用された格子を説明する図である。
【図５１】無限大チェッカーボード画像をレンダリングするために使用された格子を説明する図である。
【図１】
2009501966.tif 000404
【図２】
2009501966.tif 000405
【図３】
2009501966.tif 000406
【図４】
2009501966.tif 000407
【図５】
2009501966.tif 000408
【図６】
2009501966.tif 000409
【図７】
2009501966.tif 000410
【図８】
2009501966.tif 000411
【図９】
2009501966.tif 000412
【図１０】
2009501966.tif 000413
【図１１】
2009501966.tif 000414
【図１２】
2009501966.tif 000415
【図１３】
2009501966.tif 000416
【図１４】
2009501966.tif 000417
【図１５】
2009501966.tif 000418
【図１６】
2009501966.tif 000419
【図１７】
2009501966.tif 000420
【図１８】
2009501966.tif 000421
【図１９】
2009501966.tif 000422
【図２０】
2009501966.tif 000423
【図２１】
2009501966.tif 000424
【図２２】
2009501966.tif 000425
【図２３】
2009501966.tif 000426
【図２４】
2009501966.tif 000427
【図２５】
2009501966.tif 000428
【図２６】
2009501966.tif 000429
【図２７】
2009501966.tif 000430
【図２８】
2009501966.tif 000431
【図２９】
2009501966.tif 000432
【図３０】
2009501966.tif 000433
【図３１】
2009501966.tif 000434
【図３２】
2009501966.tif 000435
【図３３】
2009501966.tif 000436
【図３４】
2009501966.tif 000437
【図３５】
2009501966.tif 000438
【図３６】
2009501966.tif 000439
【図３７】
2009501966.tif 000440
【図３８】
2009501966.tif 000441
【図３９】
2009501966.tif 000442
【図４０】
2009501966.tif 000443
【図４１】
2009501966.tif 000444
【図４２】
2009501966.tif 000445
【図４３】
2009501966.tif 000446
【図４４】
2009501966.tif 000447
【図４５】
2009501966.tif 000448
【図４６】
2009501966.tif 000449
【図４７】
2009501966.tif 000450
【図４８】
2009501966.tif 000451
【図４９】
2009501966.tif 000452
【図５０】
2009501966.tif 000453
【図５１】
2009501966.tif 000454