一般的な２次元空間変換の表現システム及び方法
２次元空間変換を表現するシステム及び方法であり、これは、選択した形状パラメータに従って逆マップしたグリッドデータによって変換を記述する（１１０、１２０）。数値的技術を用いて、各座標のグリッドデータを、出力空間で定義した長方形パッチのアレイに曲面フィッティングする（１３０、１４０）。誤差分析は、より高いメッシュ解像度が曲面フィッティングに必要かを判断する（１５０）。次に、空間変換を長方形曲面パッチのアレイ及び曲面係数のセットによって定義する。これにより、空間変換を曲面多項式の評価によって行うことができ、また、この変換を縮尺の変更やズーミング及びパニング効果に合わせて容易に調節することができる（１６０、１７０、１８０、１９０）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジタル画像データの変換に関し、より詳細にはデジタル画像データの２次元空間変換の表現に関する。
【背景技術】
【０００２】
大抵の画像処理システムは、一部分において空間変換システムとみなすことができる。２次元の（２Ｄ）画像処理では、入力データ（場合によっては３Ｄ）との関係に従って２Ｄ出力空間内の各ピクセルに「カラー」値を割り当てることにより画像が生成される。入力データ空間と出力データ空間に座標系を採り入れることで、この関係は空間マッピングとして都合よく表される。空間マッピングは、画像処理システムの設計（レンズ構成など）に内在していてもよいし、一定の効果を得るように明確に特定されていてもよい。２Ｄの入力画像と出力画像の間、又は２Ｄの入力空間と出力空間の間のマッピングを指す用語である画像ワーピングは、画像キャプチャデバイス及び画像表示デバイスによくみられる収差などの光学的歪みや種々のアーチファクトの補正にしばしば適用される。画像ワーピングの他の用途としては、特殊効果、アニメーション、画像のスティッチング及び一般的な幾何学変換が含まれる。一般に、画像ワーピングは空間変換である必要はないが、ここでは空間マッピングを重要視する。
【０００３】
ハードウェア実装の簡略化を主な目標として、多くの電子画像歪みアルゴリズムや電子画像変換アルゴリズムが設計されている。この目標によって空間変換の複雑さが制限されたり、変換の記述が非現実的になってしまうことが多い。例えば、画像ワーピングによく用いる方法は２パス法である。２パス法に基づいた特定のワーピングシステムとして、ベネットら(Bennett et al.)の米国特許第４，４７２，７３２号に詳述されるアンペックス(Ampex)デバイスがある。この文献に開示される方法はリアルタイム画像処理システムのハードウェア実装に好適で、２Ｄマップを１Ｄフィルタリング又は再サンプリングのみが必要な一連の１Ｄマップに分解する。１Ｄでの再サンプリングは２Ｄでの再サンプリングよりもはるかに簡単で、種々の構造を用いたハードウェアの高最適化を可能にする。しかし、２パス法はボトルネック効果を生じる傾向にある。即ち、中間画像に大きな圧縮が生じ、データが損失してしまう。極端な例では、ある領域が圧縮されて線になってしまう場合など、完全なデータ損失が生じうる。この効果は、適用可能な幾何学変換のタイプを制限してしまう。２パス法に関連する他の問題は中間パスデータの生成を含む。
【０００４】
これらの問題を解決するため、セイア(Sayre)の米国特許第５，１７５，８０８号やウォルバーグら(Wolberg et al.)の米国特許第５，２０４，９４４号に述べられるように２パス法に対して種々の強化が試みられており、これらの方法はピクセル毎の記述(description)(即ちルックアップテーブル）に基づいている。ピクセル毎の記述は大きな記憶領域を要し、更に重要なことに、追加のデータ操作を行うための簡単な手段を許容しない。画像がワープされると、ズーム操作などの第２の変換が必要となる。ピクセル毎の記述では、ズーミングワープのためにグリッド全体を再生成する必要がある。この再生成は、ズーミングが通常使用される機能である場合は特に非効率的となりうる。
【０００５】
空間変換の他のアルゴリズムは、必ずしも２パス法に基づいているわけではないが、回転、線形スケーリング、アフィン、そしてファント(Fant)の米国特許第４，８３５，５３２号、キマタら(Kimata et al.)の米国特許第４，９７５，９７６号、ハンバーグ(Hamburg)の米国特許第５，８０８，６２３号及びレヴィエン(Levien)の米国特許第６，０９７，８５５号に記載のような各変換などの一定のマッピングタイプに限られている。従来技術の方法の中にも物理的なメモリ空間を用いて数学的な座標空間を識別する傾向のものがいくつかあり、これは、ハードウェア実装の際に変換がメモリ構造の構成によって制限されてしまうことを意味する。また、大抵のワーピングアルゴリズムは、独立した変換を画像の種々の部分に適用するための簡単なフォーマットを提供しない。（例えば、円形画像から長方形画像への）トポロジーの変化のような複雑なマッピングでは、種々の領域に独立したマッピングが必要である。
【０００６】
これらの制限は、２Ｄフィルタリングを利用する２Ｄ表現、即ち１パスを用いて取り除くことができる。２Ｄ表現に基づいたシステムの例としては、オーギンクら(Orginc et al.)の米国特許第５，３８４，９１２号のビデオプロセッサ及びディスプレイユニット、並びにフェアチャイルドセミコンダクター社(Fairchild Semiconductor)製造の集積回路ＴＭＣ２３０２Ａがある。しかし、これらの従来技術の方法は２Ｄ変換の制限されたサブセットに基づいているため、一般的な２Ｄマッピングを表現することができない。特に、これらのシステムはいずれも、独立した変換を単一画像の種々の部分に適用する手段を提供しない。
【特許文献１】米国特許第４，４７２，７３２号明細書
【特許文献２】米国特許第５，１７５，８０８号明細書
【特許文献３】米国特許第５，２０４，９４４号明細書
【特許文献４】米国特許第４，８３５，５３２号明細書
【特許文献５】米国特許第４，９７５，９７６号明細書
【特許文献６】米国特許第５，８０８，６２３号明細書
【特許文献７】米国特許第６，０９７，８５５号明細書
【特許文献８】米国特許第５，３８４，９１２号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、１つの態様において、入力ピクセル座標を有する入力画像を出力ピクセル座標を有する出力画像に変換する２次元画像変換を１パスで実施する電子システムを提供する。
【課題を解決するための手段】
【０００８】
このシステムは、
（ａ）ディスプレイの光学構成を記述するレンズパラメータ、投影角、平面スクリーン及び湾曲スクリーンのディスプレイパネル形状、並びにユーザ指定パラメータを含み、前記変換を定義する形状パラメータを得る形状入力インタフェースと、
（ｂ）前記形状入力インタフェースに結合されており、前記出力ピクセル座標を前記入力ピクセル座標上にマップするグリッドデータ変換を生成するグリッド変換発生器と、
（ｃ）前記グリッド変換発生器に結合されており、基本的な形状に従って前記出力ピクセル座標の空間を多数の対応パッチに分割し、出力空間パッチの境界を決定するパッチ形状発生器であって、各パッチは関連するグリッドデータセットを有する、前記パッチ形状発生器と、
（ｄ）前記パッチ形状発生器に結合されており、各パッチの前記グリッドデータセットを曲面係数によって表された曲面関数としてパラメータ化する曲面関数推定器と、
（ｅ）前記曲面関数推定器に結合されて前記曲面係数を記憶する出力インタフェースと、
を含む。
【０００９】
他の態様において、本発明は、入力ピクセル座標を有する入力画像を出力ピクセル座標を有する出力画像に変換する２次元画像変換を１パスで行うために表現する方法を提示する。この方法は、
（ａ）ディスプレイの光学構成を記述するレンズパラメータ、投影角、平面スクリーン及び湾曲スクリーンのディスプレイパネル形状、並びにユーザ指定パラメータを含み、前記変換を定義する形状入力パラメータを得ることと、
（ｂ）前記出力ピクセル座標を前記入力ピクセル座標上にマップするためにグリッドデータ変換を前記形状入力パラメータに基づいて生成することと、
（ｃ）基本的な形状に従って、前記出力ピクセル座標の空間を、各々が関連するグリッドデータセットを有する多数の対応パッチに分割し、出力空間パッチの境界を決定することと、
（ｄ）前記パッチの各々における前記グリッドデータ変換を曲面係数によって表された曲面関数としてパラメータ化することと、
前記曲面係数を記憶することと、
を含む。
【００１０】
本発明の実施の形態の異なる態様及び利点の更なる詳細は、添付の図面と共に下記の説明において明らかになる。
【発明を実施するための最良の形態】
【００１１】
まず、本発明の好適な実施の形態に従って作られたワープシステム１００の例を示す図１を参照する。ワープシステム１００は、形状入力インタフェース１１０、グリッド変換発生器１２０、パッチ形状発生器１３０、曲面関数推定器１４０、誤差分析段階１５０、バウンディングボックス発生器１６０、解像度／ズーム発生器１７０、データ再構成段階１８０及び出力インタフェース１９０を含む。
【００１２】
ワープシステム１００は、（ピクセル毎の）グリッドデータ表現を、効率的なリアルタイムのハードウェア実装により曲面関数表現に変換する。２Ｄ空間変換の適用が必要なシステムはいずれもワープシステム１００を利用することができる。ワープシステム１００は、プロジェクタ、カメラ及び表示デバイスにおける小さな歪みの補正から、キーストーン補正や特殊な広角レンズ補正などの遠近感補正、そして、円形の３６０°画像からの長方形パノラマの形成や、他の長方形から極型のマッピングなどの画像形状の完全な変化に及ぶ用途に使用可能である。
【００１３】
形状入力インタフェース１１０は、少数の形状パラメータに関する変換の記述を得るか又はこれを含んでいる。これらのパラメータは、最高レベルの変換の記述（即ち定義）を提供する。例としては、投影角及びレンズ投射比に関するキーストーン変換の記述、放射状３次多項式関数（ここで、パラメータは４つの多項式係数である）に関するレンズ補正の記述、又は曲率半径に関するディスプレイ曲面の記述がある。少数の形状パラメータに関する閉じた記述が利用できない極端な例では、点の小さなサブセットのマッピングをもたらす数値記述の使用が必要になる場合がある。
【００１４】
グリッド変換発生器１２０は形状入力インタフェース１１０に結合している。グリッド変換発生器１２０は、形状入力インタフェース１１０から得た入力形状パラメータを用いて空間変換のグリッドデータ記述を生成する。この記述は、変換の実施後に対応する形状マッピングを定義し、新しいピクセル位置を提供する。グリッド変換発生器１２０は、逆マッピング変換、即ち出力画像の各ピクセルを入力画像のどこにマッピングしたかを指定する空間変換を用いる。このアプローチは、出力における水平／垂直の走査線内の各出力ピクセルに対してピクセルの処理順に値を割り当てることを確実にする。一方、従来から知られている順方向マッピングは、割り当てられていないピクセルによって出力画像に「穴」を残す場合がある。
【００１５】
ここで図２を参照すると、入力座標空間で入力画像のピクセルＰ’を得るために出力画像の座標空間内のピクセルＰに実施される逆マップとしての一般的な２Ｄ変換のグラフ図が示されている。一般的なワープは、入力座標空間の非整数の位置に点をマップする。ピクセルは、各格子点を取り囲む点線の正方形で示すように、数学上の点としてではなく有限の領域を有するものとしてモデル化されることが多い。よって、出力空間のピクセルＰを正方形ＡＢＣＤとみなし、この正方形を、入力座標空間のＰ’を取り囲む任意の形状ＡＢＣＤにワープする。入力空間では、ピクセルＰ’をピクセル１、２、３及び４と重複するものとみなすことができる。
【００１６】
図２に示すように、入力空間及び出力空間の原点が対応する各画像の左上隅にあると定義し、そこから正のｘが右に向き、正のｙが下に向いている。入力画像及び出力画像は一般に何らかの形態のメモリに記憶されているか又は書き込まれているため、本開示物は入力画像空間及び出力画像空間を入力メモリ空間及び出力メモリ空間と呼ぶことがある。一般に、グリッドデータ記述を以下の公式によって要約することができる。
【００１７】
Ｕ＝Ｆu（Ｘ，Ｙ）
Ｖ＝Ｆv（Ｘ，Ｙ） （１）
【００１８】
これらの式は、座標（Ｘ，Ｙ）を有する出力画像のピクセルが、空間変換Ｆ＝（Ｆu，Ｆv）によって座標（Ｕ，Ｖ）を有する入力画像のピクセルにマップされることを示している。従って、グリッドデータセット関係（又は単にグリッドデータセットと呼ぶ）｛（Ｕi，Ｖi），（Ｘi，Ｙi）｝は出力空間のピクセル｛（Ｘi，Ｙi）｝のセットであり、これらのピクセルは入力空間のピクセル｛（Ｕi，Ｖi）｝に逆マップされる。前述のように、座標｛Ｘ，Ｙ，Ｕ，Ｖ｝は物理的なメモリアドレス空間の座標である。この関係は以下のように表される。
【００１９】
【数１】
【００２０】
空間変換の定義には２つの一般的な従来のアプローチがある。第１に、マッピング（Ｆu，Ｆv）の陽関数形態を識別するか又は構築することができ、これは、空間変換のための明示的な数学モデルを有することを意味する。第２に、グリッドデータセット関係｛（Ｕi，Ｖi），（Ｘi，Ｙi）｝は、出力空間の一部又は全てに関連して識別するか又は構築することができる出力ピクセル位置（Ｘi，Ｙi）に対応する入力ピクセルの位置（Ｕi，Ｖi）をもたらす。図２に示すように、出力位置（Ｘi，Ｙi）は整数値であり、通常は出力メモリ空間の定期的なサンプリングによって構成されるが、マップされた入力ピクセルの位置（Ｕi，Ｖi）は一般に非整数である。この数学モデルは通常は形状入力インタフェース１１０における少数の形状パラメータに関する記述に関連しているのに対し、グリッドデータセットは少数の点に関する数値記述に関連している。数学モデルのアプローチでは、グリッドデータセットを得るためにマッピングを常に評価しうるため、第２のアプローチがより普遍的である。
【００２１】
グリッドデータセット関係モデルは空間変換の「理想的」表現であると考えられている（実際には、グリッドデータはノイズを含む場合があり、その場合は「理想的」自体おおよそである）。しかし、データセット（即ち関数）は画像の領域によって大きく変わるため、この記述は非常に複雑になる場合がある。このような表現に直接的に基づいた画像変換システムは、ソフトウェア又はハードウェアでの実施が難しい。グリッドデータセット｛（Ｘi，Ｙi）｝又はグリッドデータセット関係｛（Ｕi，Ｖi），（Ｘi，Ｙi）｝は出力空間全体に広がり、グリッドデータのコンポーネントは本質的にピクセル毎の表現と同じである。この意味では、２Ｄ空間変換の表現におけるグリッドデータセットの使用は、ピクセル毎の（ルックアップ／変位テーブル）記述を用いるいずれの従来技術においても暗黙の前提である。しかし、ピクセル毎の表現はハードウェア実装には非効率的である。本発明のワープシステム１００は、グリッドデータ（ピクセル毎の）関係表現を曲面関数表現に変換する。
【００２２】
関数表現の前にしばしばなされる簡素化は、２パス処理のためにデータを分離することである。従来から知られているように、分離を用いる主な利点は、対応するハードウェア実装が簡単になることである。スケーリングデータを垂直及び水平のパス（即ちデータセット）に分離することで、１Ｄフィルタリングの使用が可能になる。しかし、これによって画質が犠牲になり、また、全てのマッピングを分離できるわけではない。メモリ空間及び速度における現在の進歩により、効率的な２Ｄフィルタリングを行う１パスが実装可能となった。このような実装の一例はｓｘＴ２チップ（カリフォルニア州サンノゼのシリコンオプティックス社(Silicon Optix Inc.)製造）である。よって、２パス処理の分離から得られた従来技術のハードウェアの利点は、画質及び変換の柔軟性を維持する、という更に重要な目標に取って代わられる。本発明の方法は分離を使用しないが効率的なハードウェア実装を可能にし、一般的な２Ｄマッピングを表現するのに十分な柔軟性を保つ。この方法は１パスであるため、（２Ｄフィルタの使用時に）生じる画質は２パス法のものよりも優れている。
【００２３】
本発明の有用性を十分に理解するには、ハードウェア処理を簡素化するために出力空間での２Ｄ変換の評価によく使われる走査線処理を理解することが重要である。この変換は、従来技術のように２パスでもよいし、本発明のように１パスでもよい。走査線処理では、出力ピクセルを行（水平）及び／又は列（垂直）に沿って連続的に生成する。行／列を完全に生成した後、処理は次の行／列に進む。走査線処理の変形例としては、まず各行／列のセクション、例えばセクション１を処理し、次に、（各行／列のセクション１の処理後に）セクション２を処理するなどがある。この変形例は、両方向の走査線処理を組み合わせる。出力における走査線処理は、入力画像データに実施される処理のタイプを制限しない。特に、２Ｄフィルタリングを使用することができる。
【００２４】
出力において走査線処理を使用することの主な制限は、入力における（フィルタリングに必要なピクセルデータの）メモリアクセスがランダムになりうることである。（ほぼ連続的に処理される）出力空間の近隣のピクセルは大きな領域にわたって広がる入力空間のデータを必要とする場合があるため、入力メモリアクセスが非効率的になる。このことはフィルタリングでは問題となりうる（処理が遅くなり、時間遅延が長くなる）が、本発明の焦点である、変換を記述する曲面多項式の評価ではさほど問題にならない。本発明では、曲面多項式は出力空間で定義され、入力ピクセルデータにアクセスする必要がない。
【００２５】
走査線処理のために、出力空間の全てのピクセルに空間変換を定義する必要がある。これは、データセット記述から、各ピクセルの理想的なマッピングに最も近似する関数記述に進むことを意味する（サンプリングを行ったピクセルに関しては、理想的なマッピングは公知のグリッドデータセット関係によってもたらされることを想起する）。数学モデルが明確に定義されていない領域に対しては、関数記述は明確なデータを推定したり、このような領域をバックグラウンドにマップすることができる。数学モデルの不明確な領域は常にバックグラウンドピクセルに対応するため、後者の対応の仕方は許容可能である。
【００２６】
図３はパッチ形状発生器１３０の機能を示している。パッチ形状発生器１３０は、データの曲面フィッティングが行われる出力空間（図２）で定義された長方形パッチのアレイを生成する。パッチは同一サイズである必要はないが、この特定の実施では規則的な態様ではまり合うべきである。この文脈における「規則的な」という用語は、パッチを行及び／又は列に配置できることを意味するように意図されている。長方形パッチによるいずれの分割も規則的な配列をもたらすことができるため、このことは限定的ではない。規則的及び不規則的なパッチ分割を図３に示す。パッチの数は、ワープの複雑さ、フィッティング誤差の許容レベル（後述）、フィッティングに用いる基底関数のタイプ、そして実施上の制約によって決定される。原則として、隣接する４つのピクセル点からなる各セットにパッチを割り当てることができるが、空間変換を記憶するのに大容量のメモリが必要となる。
【００２７】
グリッド変換の関数記述を生成する曲面関数推定器１４０がパッチ形状発生器１３０に結合されている。空間変換の関数記述を得るためによく使われる方法は、グリッドデータを走査線のサブセットに垂直及び／又は水平にフィットすることである。このフィッティングは通常は最小２乗ベースであるとともに、基底関数が多項式であることが多い。走査線のフィッティングの欠点は、（ａ）大量のデータ、即ちフィットする走査線毎に１セットの多項式係数を記憶する必要があることと、（ｂ）個々の走査線をフィットすることによって走査線間のワープのグローバルな記述が失われることである。特に、走査線をピクセルの行又は列毎にフィットしない場合（メモリの制約のためによくある）、内挿を行って走査線間のグリッドデータを得る必要がある。ワープのグローバルな記述を考慮しない内挿はいずれの形態でもピクセル位置の誤差を生じ、ワープの重大さによっては非常に大きな誤差になりうる。
【００２８】
両方の座標のグリッドデータに曲面フィッティングを行うことにより、これらの２つの問題を解くことができる。１パス及び２パス両方の方法に用いる曲面フィッティングは、２Ｄ空間変換を記述する自然な方法である。曲面フィッティングは、両方向の形状挙動を同時に組み込んだ正確な記述をもたらす。曲面フィッティングを多項式法によって成し遂げる場合、曲面フィッティングとは、単一方向の走査線フィッティングを記述する多項式係数をフィットすることを意味する。曲面はマッピングの完全な２Ｄ記述をもたらすが、曲面の評価を走査線の順で垂直又は水平に進めることができる。よって、効率的な走査線アルゴリズムを用いて曲面ベースの記述を実施することもできる。
【００２９】
ここで図１及び図３を参照すると、曲面関数推定器１４０は、後述するように、選択された基底系を用いて各長方形パッチのグリッドデータを曲面にフィットする。この処理は、データが多値ではない、即ちフォールディングがないことを想定していることに注意されたい。リアルタイムのハードウェアの実施では、最も一般的に選択されるフィッティングはｘ及びｙ双方の３次多項式曲面である。曲面フィッティングは理想的なデータセット関係｛（ｕi，ｖi），（ｘi，ｙi）｝に関数近似をもたらす。曲面関数はｕi＝Ｓnu（ｘi，ｙi）などと示される。出力座標空間の原点は、パッチ毎に再定義される相対的な原点となるように選択される。これは、例えば各パッチの左上隅に定義されるように原点を選択できることを意味する。このことにより、フィッティング及び曲面の評価に関連する数値の範囲が狭まる。この数値範囲の減少は、特にハードウェアの演算器における数値誤差を減少させるのに重要である。
【００３０】
ここで、多項式ベースのアプローチの特定の実施をより詳細に説明する。多項式関数（形式ｘiｙjの項）は、ハードウェア実装に用いられる最も一般的な非自明関数である。Ｂ−スプライン曲面のような多項式ベースの曲面はいずれもこの形式にすることができる。下記の記数法が種々のフィット曲面に用いられる。
【００３１】
【数２】
【００３２】
ここで、曲面を評価する座標はデータセット内のサンプルピクセルだけでなくパッチ全体にわたっている（下付きのｃは計算されたことを示す）。曲面の次数はｘ方向のＫ及びｙ方向のＬであり、これらは互いに異なっていてもよい。フィットから得られる曲面係数｛Ｓnu,kl，Ｓnv,kl｝は全てのパッチの曲面を一意的に定義する。
【００３３】
曲面フィッティングは、グリッドベースの表現即ち｛（ｕi，ｖi），（ｘi，ｙi）｝から、（パッチｎに対する）下記のような曲面多項式（関数）ベースの表現に移行する。
【００３４】
【数３】
【００３５】
前述のように、ｖに対しても同様に移行する。多数のグリッドデータ関係点｛（ｕi，ｖi），（ｘi，ｙi）｝を記憶するのではなく、曲面係数Ｓnu,klのみを記憶すればよい（即ち全ての曲面／パッチに対し）。次に、この曲面を評価し、逆マップしたピクセル位置を決定することができる。このフィッティング手順は曲面係数を決定する。異なる方法及びフィッティング関数を用いてデータをフィットすることができるが、フィッティングに最も一般的に用いられるのは最小２乗法である。
【００３６】
図４は、出力座標空間の４つの長方形パッチのアレイへの分割に基づいて、曲面関数推定器１４０によって生成された２Ｄフィット曲面の２つの例を示している。ここで、図４Ａに示す曲面は不連続的であるのに対し、図４Ｂに示す曲面は連続的である。不連続性の考察を更に後述する。
【００３７】
誤差分析段階１５０は、これらの曲面を得ると、２Ｄデータセットの出力座標点毎に関連する曲面関数を評価してｕic及びｖicの値を得る。誤差分析段階１５０は、グリッド変換発生器１２０から別に受け取った２Ｄグリッド記述からの正確な座標（（ｕi，ｖi））とこれらの値を比較する。次に、誤差分析段階１５０は、所定の誤差許容レベル条件（｜ｕic−ｕi｜，｜ｖic−ｖi｜）が満たされているか否かを判断する。予め設定された許容レベル条件が満たされていない場合、誤差分析段階１５０は誤差分析の結果をパッチ形状発生器１３０に送る。これらの結果に基づいて、パッチ形状発生器１３０はパッチ形状を更に細分する。誤差が許容レベルよりも大きいパッチのみを細分する。パッチの細分によって長方形アレイの規則性が保たれる。細分の主な候補となるパッチは大量のバックグラウンドを含むパッチである。フィッティング誤差は、入力座標空間の外側のバックグラウンドにマップするピクセルに対して大きいことが多い。この場合、これらの点を個々のパッチに関連させ、バックグラウンドにマップする態様でフィットすべきである。次に、関連する非バックグラウンド領域を個別にフィットすることができる。所望の精度を得るまでこれらのステップを繰り返す。曲面関数は所与の実施に対して変わらないことに注意されたい。
【００３８】
本発明の実施例では、パッチ形状の最適化処理は勾配探索及び／又はランダム探索によって行われる。探索はパッチ境界位置のベクトル空間で行われる。パッチのＭ×Ｎアレイの場合、Ｍ＋１のｙ境界（垂直）及びＮ＋１のｘ境界（水平）があり、ベクトル空間にＭ＋Ｎ＋２の次元数をもたらす。
【００３９】
【数４】
【００４０】
【数５】
【００４１】
【数６】
【００４２】
前述の曲面表現に関する重要な点をいくつか強調する必要がある。必要であれば、各パッチを独立した出力座標空間とみなし、このパッチのデータセットをそれ自体が独立した２Ｄ変換とみなすことができる。特に、各パッチを独立してフィッティングすることができ、このことは出力画像が連続的である必要がないことを暗示している。パッチの不連続及び連続的な曲面フィットの例を図４Ａ及び図４Ｂに示す。図４Ａに示す４つのパッチを更に分割してフィッティングを改良することができる。具体的には、１０２４×７６８のｘ−ｙ出力空間を４つのパッチに分割し、曲面（ｕ（ｘ，ｙ））をプロットした。図４Ａでは、曲面はパッチにわたって不連続的である。各パッチは独立したデータセットを有し、このデータセットは近隣のデータセットから独立してフィットされている。図４Ｂでは、曲面はパッチにわたって連続的であり、この場合、いずれのパッチのフィットも連続性を確実にすることが必要である。
【００４３】
パッチ境界にわたる画像の連続性を維持する更に一般的な状況では、連続性の制約を陽的に許容するか又はこれらの制約を課す基底関数を使用することができる。２Ｄでの連続性を制御する最もよく知られた関数はＢ−スプライン曲面及びベジエ曲面である。両タイプの曲面を用いて、（Ｃiの連続関数の数学的意味における）所要の程度の連続性を得ることができる。Ｂ−スプラインでは、テンソル積アプローチを用いてパッチのＭ×Ｎアレイに曲面フィットを行うことができ、パッチ分割はスプラインのノットから容易に得られ、逆の場合も同じである。ノット列を調節することにより、Ｂ−スプライン曲面の連続性を容易に制御することができる。双３次Ｂ−スプラインを用いて、最大でＣ2までの連続性を課すことができ、これは全ての目的に十分である。（通常は、滑らかな画像を得るにはＣ1で十分である。）不連続な曲面、即ち独立したパッチは、適切なノット列を有するＢ−スプラインの特殊なケースとみなされる。また、スプラインを、多項式ベースとしたハードウェア実装に自然に変換可能となるよう、相対的な原点を有する（各パッチに対する）局所的多項式の形式で書き込むこともできる。Ｂ−スプラインフィッティングのツールが多くの数値／数学的計算ソフトウェアパッケージによって利用可能である。また、各独立パッチを異なる演算に関連させることができる。（パッチ境界にわたる任意の連続性の）パッチベースの曲面記述は、非常に複雑な２Ｄ空間変換の表現を可能にする。
【００４４】
一般的な２Ｄ空間変換の完全な表現は下記のデータによってもたらされ、各パッチに適用される。
１）パッチの形状（パッチ原点の絶対的な位置、パッチサイズ）
２）グリッドデータ関係への曲面フィットを記述する曲面係数
【００４５】
この表現は、２Ｄマッピングを定義する統一フォーマットを提供する。この表現は、２Ｄ画像変換システムのリアルタイムのハードウェアの実施を対象としている。ハードウェア実装では、曲面多項式を走査線順に評価し、位置及び導関数情報を処理フィルタに通す。（導関数は位置の曲面から容易に抽出される。）マッピングは閉じた関数の形でもたらされるため、完全な形状データ（種々の次数の導関数）はフィルタリング段階に容易に利用可能である。
【００４６】
マップの複雑さが増すにつれて、パッチの数、よって前述の（１）及び（２）の表現に含まれるデータの量が増加する。データは、全体的なフォーマットを一切変えずにマッピングの複雑さに合わせて調整する。また、パッチ数の増加はフィッティング誤差を減少させるように機能する。原則として、パッチアレイを連続的に細分することにより、最大のフィッティング誤差を任意の小さなレベルに下げることができる。しかし、実際には、データの記憶に利用可能な空間（メモリ）の容量（各パッチにはデータコンポーネント（１）及び（２）が関連している）に対する制約により、パッチの数は制限される。メモリ要件と誤差の最小化（許容レベル）のバランスをとることによって最終的なパッチアレイサイズを決定する。
【００４７】
実施対象となる大抵の２Ｄ変換は高解像度パッチメッシュを必要としない。サイズや誤差に関するこれらの問題を定量化するために、前述のフォーマットを用いて２Ｄマッピングをいくつか検討した。これらの２Ｄマッピングは、（ｉ）放射状ピンクッション型歪み及び樽型歪みのような共通のレンズ歪み、（ｉｉ）垂直／水平キーストーン補正及び湾曲面への射影などの射影、（ｉｉｉ）線形スケーリングと組み合わせた回転、（ｉｖ）前述したものの組み合わせ、（ｖ）アークラスタマップのような更に複雑なマップ、（ｖｉ）（魚眼レンズ又は特殊３６０°イメージング（撮像）システムを用いて得られた）広角／３６０°／パノラマ画像の補正を含む。
【００４８】
パッチ毎に１６の曲面係数を示す３次（Ｋ＝Ｌ＝３）の多項式曲面を使用した。０．５ピクセルの誤差限界を設定した。（ｉｉ）−（ｉｖ）の変換では、最大で４つのパッチが必要であった。マップ全体を定義するには、曲面係数の合計が１２８以下になる。曲面係数を４バイトの浮動小数として記憶した場合、データサイズは５１２バイト以下になる。この数は非常に妥当な数であり、オンボード／オンチップメモリによって容易に受け入れられる。
【００４９】
（ｉ）及び（ｖ）の変換では（双方の座標のために）最大で合計２６のパッチが必要であった。これは１．６２５キロバイト以下のデータサイズをもたらすため、この場合も現行のオンボード／オンチップメモリによって容易に処理される。（ｖｉ）の変換では、９０°の広角に対して行う透視補正は最大で合計１８のパッチ、即ち１．１２５キロバイト以下を必要とする。この表現の機能を全て使用する場合は、（ｖｉ）から得た画像に複雑な変換を実施することができる。例えば、２つの１８０°魚眼レンズからの画像を、スティッチングした３６０°のパノラマビューと、例えば透視補正を施した特定領域の２つの９０°の拡大ビューに変換することができる。このような変換は約６つのマップ（３６０／９０＋２）に相当し、その各々が、６．７５キロバイト以下のデータサイズである特定の９０°領域を変換する。このような特殊広角／３６０°ベースの変換は、特にセキュリティの用途でここ数年人気が出ている。従って、前述の方法は一般的な２Ｄ変換を適度なデータサイズ（サイズは複雑さに対して直線的に増加する）とサブピクセル精度で表現できることがこれらの結果から明らかである。
【００５０】
【数７】
【００５１】
非バックグラウンドピクセル境界は通常は長方形でないため、全てのバックグラウンドピクセルをこのように識別するわけではない。しかし、バウンディングボックスをより細かく、おそらくパッチ毎に１つよりも多く分割することで、（バウンディングボックス座標に必要な）更に多くの記憶を犠牲にしてこの境界を長方形のバウンディングボックスに綿密に近似させることができる。大抵の変換ではバウンディングボックスデータは不要であり、極端な変換ではパッチ毎に１つのバウンディングボックスで十分である。
【００５２】
バウンディングボックスデータを使用しない場合、より標準的なアプローチを用いて不要な処理を取り除くことができる。標準のアプローチでは、全ての出力ピクセルの曲面を評価し、照合を行って、生じた座標が入力空間内に存在するか否かを判断する。座標が入力空間内にある場合、処理は通常通りに進む、即ち出力ピクセルのカラー値を２Ｄフィルタリングによって決定する。座標が入力空間の外側にある場合、単純にバックグラウンドカラーをピクセルに割り当て、２Ｄフィルタを実行しない。ここでは、曲面を評価する必要はあるが、フィルタがこれらのデータを処理しないという事実によって得られる利益はかなり大きくなりうる。また、非バックグラウンドピクセル境界は入力空間への曲面のマップによって完全に指定されるため、この境界を非常に正確に決定することができる。
【００５３】
ワープシステム１００の画像変換により、２Ｄ画像変換を記述するパラメータの完全なセットが決定される。本発明の１つの実施では、これらのデータは解像度／ズーム段階１７０によって使用され、次いでデータ再構成段階１８０によって使用される。これらの段階の前に、パッチ形状発生器１３０及び曲面関数推定器１４０からそれぞれ生じた基本的なパッチ形状及び曲面係数で構成されるマッピング表現を、バウンディングボックス発生器１６０の出力において決定する。
【００５４】
図５及び図６に示すように、解像度／ズーム発生器１７０を使用して解像度の変更及びズーミング効果を入力／出力画像に提供し、前述の画像パラメータを利用することができる。ワープシステム１００の画像変換の位置ベース表現を用いて、係数の簡単なスケーリングを行うことで空間変換を異なる解像度に合わせて容易に調節することができる。図５は、入力画像及び出力画像の双方をスケーリングする解像度変更動作に関連するステップを示している。入力／出力座標の個々のスケーリングを以下のように表すことができる。
【００５５】
【数８】
【００５６】
定数｛ｒ1，ｓ1，ｒ2，ｓ2｝は倍率を示し、ダッシュ記号はスケーリングした座標を示す。スケーリングした座標に関して、曲面を以下のように表すことができる。
【００５７】
【数９】
【００５８】
従って、入力解像度又は出力解像度の変更に合わせて調節するために、全ての係数を因数でスケーリングする。これは比較的簡単な演算で、再フィッティングや内挿を必要としない。しかし、パッチ形状（即ちパッチサイズ及びパッチ原点の絶対的な位置）もワープシステム１００によって適切にスケーリングする必要があることを理解されたい。
【００５９】
図６は、ワープシステム１００によって行われる画像変換内のズーミングマップの生成に関連するステップを示している。ベース入力画像、ベース出力画像及びスケーリングしたベース出力画像は、ベースワープ及びズーム対象領域を示している。まず、ベース出力画像をスケーリングし（即ち、スケーリングしたベース出力画像を生成し）、次に（スケーリング動作で適切にズーミングした）対象領域を抽出／トリミングすることでズーミングワープを生成する。ズーミングマップは、新しい入力画像と新しい出力画像との間に示す変換に相当する。ズーミング動作は異なる解像度に対するスケーリングと同様であるが、特定の領域を拡大／縮小することができるという違いがあり、これはパニング機能を示している。ズーム動作を入力画像空間（変換前）又は出力画像空間（変換後）に対して定義することができる。ワープシステム１００の以下の例示的な用途では、出力空間のズーミングを述べる。ズーム比Ｋを＞１となるように選択する（Ｋ＝２の場合は２×ズームなど）。他のケースも同様に処理する。
【００６０】
【数１０】
【００６１】
数学的には、ズーミングの第１のステップは乗算演算であり、第２のステップはシフト又は加算演算である。ベース出力空間及び新しい出力空間での絶対位置は下記式によって関連付けられる。
【００６２】
【数１１】
【００６３】
ベースマップのｎ番目のパッチの左上隅（１の指数で示す）及び右下隅（２の指数で示す）を以下のように示す（これらは絶対位置であるが、下付きのＡは表示を簡略にするために省略する）。
【００６４】
｛（ｘ１n，ｙ１n），（ｘ２n，ｙ２n）｝ （１４）
【００６５】
これらの点を、下記の新しい空間の新しい端点にマップする。
【００６６】
【数１２】
【００６７】
パッチの新しい幅又は高さが０以下である場合、このパッチを新しいマップから除外する。幅と高さが共にゼロよりも大きい場合、このパッチをズーミング変換に含める。このパッチの一部のみが含まれる可能性があるため、含めるパッチの絶対位置（即ち左上隅）を再計算する必要がある。新しい位置は下記式によって得られる。
【００６８】
【数１３】
【００６９】
保持する各パッチの新しいパッチ形状（位置及びサイズ）は下記式によって得られる。
【００７０】
【数１４】
【００７１】
新しいパッチ形状がわかったら、式（１２）及び式（１３）を新しい出力空間の相対的な原点表現に変換することができる（パッチの指数を下げる）。
【００７２】
【数１５】
【００７３】
最後に、これらをベースマップの曲面式に代入することができる。
【００７４】
【数１６】
【００７５】
式（２０）を展開し、これらの式を標準の形式と比較することで、新しい曲面係数を直接抽出することができる。これらの係数はパッチの形状と併せてズーミング変換を完全に定義する。
【００７６】
データ再構成段階１８０は、表現データの更なる再構成が必要である特定の画像の操作システムに用いられる。曲面多項式の評価は種々の方法で進めることができ、その詳細（使用する加算及び乗算の数やその次数など）はハードウェア又はソフトウェアの構造に依存する。例えば、多項式の評価に対する一般的なハードウェアアプローチはホーナー法を使用することである（本発明のこの実施は、一般的な表記法を用いた３次多項式を使用する）。
【００７７】
ａｘ3＋ｂｘ2＋ｃｘ＋ｄ＝（（ａｘ＋ｂ）ｘ＋ｃ）ｘ＋ｄ （２１）
【００７８】
同様の技術を曲面の評価に用いることができる。曲面を以下のように書き換えることができる。
【００７９】
【数１７】
【００８０】
曲面をｘの多項式として扱い、ｘ多項式の係数はｙの多項式である。各多項式（全部で５）を、ホーナー法を用いて評価する。各水平走査線（行）では、ｙ多項式を（パッチ毎に）一度だけ評価すればよい。垂直走査線には式（２２）を用いることもできる。この場合、各パッチの第１の垂直走査線（列）に関してｙ多項式を評価し、記憶することができる。そして、これらのｙ多項式は走査線のｘ位置から独立しているため、これらをパッチの残りの垂直走査線に使用することができる。これによって処理速度が上がると共に、この変換は、位置係数自体がｙの多項式であることによって表されるように、ｘに直接依存しｙに間接的に依存する１Ｄ位置の多項式として表される。あるいは、この曲面をｙの多項式として表し、ｙ多項式の係数をｘの多項式とすることができる。実施に応じて、一方又は他方のアプローチをメモリのアクセス／記憶及び演算器の詳細により良く適応するように構成することができる。
【００８１】
多項式を評価する他の標準的な技術は前方差分の使用である。しかし、前方差分の評価は累算の誤差を生じる傾向にある。前方差分の評価の主な利点は、ハードウェアの複雑さを低減すること（具体的には、乗数を減少することと固定小数点を使用できること）である。走査線方向のパッチサイズが小さく、適度な数値精度のビットが利用可能である場合、累算の誤差は小さくなりうる。
【００８２】
図７は本発明の一例の論理フロー７００を示している。ステップ７１０では、各出力ピクセルを入力ピクセルにマップする（逆マッピング）座標対を含むグリッドデータセットを生成する。ステップ７２０では、ワープの基本的な形状及び複雑さに依存するパッチ形状を生成する。ステップ７３０では、グリッドデータセットの記述を曲面フィッティングによって近似し、曲面係数を生成する。
【００８３】
この時点で、曲面データ及びパッチデータが全て生成されている。これらのデータを、ステップ７１０で生成したグリッドデータセットの正確な座標と比較してステップ７４０及びステップ７５０で分析する。ステップ７５２において、パッチ形状及び曲面フィッティングによって生成したピクセルの近似の誤差が所定の許容レベルよりも大きい場合、この情報を用いてステップ７２０のパッチ形状を更に細分する。誤差が許容レベル内になるまでこのループを続ける。
【００８４】
ステップ７６０で誤差分析ステップの条件が満たされると、出力画像のアクティブ領域を決定し、このアクティブ領域を含むバウンディングボックスを抽出する。これは、処理をこの領域に制限して処理時間をある程度節約するためである。
【００８５】
ステップ７７０では、生じうる解像度の変更及びズーミングのためのマップを生成し、曲面係数のスケーリングによってこれらの動作をワープ変換と同調させて実行する。ステップ７８０では、乗数の数を減らすことによってハードウェア実装効率を上げるように変換を再構成する。
【００８６】
本発明のワープシステム１００は、従来技術の画像変換方法にまさるいくつかの有意な利点をもたらす。まず、ワープシステム１００は、走査線処理、少ないメモリ要件及び簡単な多項式ベースの表現を用いることによる、リアルタイム画像変換システムの効率的なハードウェア実装である。このシステムは、任意の変換を統一して表現する。変換は出力空間での曲面−パッチ記述（逆マッピング形式）に基づいており、更なる効果のために容易に操作することのできる閉形式解をもたらす。変換は全て、パッチ形状及び曲面係数を特定するパラメータで構成される。このピクセル毎の記述を、曲面−パッチ記述の限定ケース、即ち曲面を４つのピクセル毎にフィットさせるものとみなすことができる。
【００８７】
また、ワープシステム１００は複雑さに自然に比例する空間変換の記述を提供する。変換が複雑であるほど、必要なパッチの数が大きくなる。即ち、フォーマットは変化せず、記述パラメータの増加は線形である。特に、更なる特徴を表現に組み込む必要がない。表現は、実施対象となる複雑な変換を組み込むのに十分一般的なものである。
【００８８】
また、ワープシステム１００は種々の入力／出力解像度の変換を生成する。この記述はピクセル毎の形ではなく閉じた関数の形でもたらされ、多くのワーピング特徴がパラメータに対する単純な数学演算となる。解像度の変更は曲面係数のスケーリングによって容易に説明される。また、ワープシステム１００はズーミング及びパニングのための効率的なメカニズムを提供する。解像度の変更と同様に、ズーミング及びパニングは曲面係数の線形変換を意味する。グリッドデータの再生成は不要である。「ベース」マップが計算されると、このベース記述のパラメータを直接変更して標準のスケーリング及びシフト変換を実施することができる。
【００８９】
ワープシステム１００は「理想的な」記述と比べて非常に小さな数値誤差を生じる。誤差はパッチメッシュの解像度に大きく依存する。パッチの数を増やすことで、誤差を適宜小さくすることができる。ある点を越えると、誤差を更に小さくしても、広範囲にわたるフィルタのため画質に殆ど影響を及ぼさなくなる。誤差の許容レベルは、通常はメモリの制限によって限定される。更に、基底関数が変更可能である場合は、特定のワープに対して、適切なフィッティング基底を選択することによって（パッチの数を増やさなくても）誤差をごくわずかにすることができる。
【００９０】
ワープシステム１００では、ハードウェア実装にとってこの方法を魅力的なものにする空間変換を記述するためのメモリ記憶空間（即ちデータファイルサイズ）は小さくてよい。実施対象となる大抵の変換では、少数のパッチを用いてサブピクセルの正確な結果を得ることができる。この場合、データファイルサイズは主に、ピクセル毎の大きな位置テーブルではなく少数の曲面係数で構成される。
【００９１】
ワープシステム１００は、非常に一般的なマッピングを得るために個々の変換を画像の種々の部分に適用する。各パッチ（及びそのデータ）は、画像の種々の領域を個々に変換することのできる独立したサブマップとして扱うことができる。この変換を、単一の連続曲面によってグローバルに定義する必要はない。種々のマップを組み合わせたり互いに「スティッチング」して、単一のマップを同一フォーマットで形成することができる。ワープシステム１００は、最適な結果を得るためにＢ−スプラインやベジエ曲面フィッティングのような既知の形状モデル化技術を組み込んでいる。必要に応じて、数値的／数学的に高度な種々の技術を用いて曲面係数を生成することができる。Ｂ−スプライン曲面及びベジエ曲面は本発明のフレームワークに自然に適合する。これらの曲面は、パッチにわたる曲面連続性を明確に制御する。パッチ分割も、スプライン曲面のノットシーケンスから容易に得ることができる。これらの曲面を最小２乗フィッティング技術と共に用いることで、曲面記述生成プロセスを、よく使用される多くの簡単なワープのために自動化することができる。
【００９２】
ワープシステム１００の１つの特定の実施は、フィッティングの制御をより強くするがパッチ形状を複雑にする非長方形のパッチを許容する。本発明のこの例では、パッチ形状をパラメトリック境界曲線によって記述する。このパラメータ化を座標のうちの１つに関連して行うことができ、座標の選択は境界曲線の向きに依存する。長方形パッチの場合、これらの境界曲線は単なる垂直及び水平の線である。任意形状のパッチは、前述の他の特徴と併せて、原則として非常に複雑な２Ｄ画像ワーピングを生成するために極度のレベルの柔軟性をもたらす。
【００９３】
他の実施では、ワープシステム１００は長方形パッチを用いるが、境界パッチ、即ち画像領域とバックグラウンド領域との境をなすパッチの評価ドメインを制限する境界曲線も許容する。このようにして、境界曲線によって指定されたドメイン内にあるパッチ又はパッチの一部のみに全ての計算を行う。このことは、フィッティングを特定の領域に制限するのに役立つ。
【００９４】
複数のパスを含むように前述の方法を展開して画像曲面の層化をサポートすることができる。画像データは、画像の輝度及びクロミナンスのデータにより再サンプリングされる深さ情報を含むことができる。深さ情報は、各ピクセルの可視性又はオクルージョンを決定する層化プロセスに使用される。曲面は同一サイズでなくてもよく、重複していてもしていなくてもよい。
【００９５】
当業者には明らかであるように、前述の構造に対する種々の変更及び適応が本発明から逸脱しない範囲で可能であり、本発明の要旨は添付の請求の範囲に定められる。
【図面の簡単な説明】
【００９６】
【図１】本発明の好適な実施の形態に従って構築されたワープシステムのブロック図である。
【図２】逆マップを出力画像（Ｐ）のピクセルに実施して入力画像（Ｐ’）の対応するピクセルの位置を決定する一般的な２Ｄ変換のグラフ図である。
【図３】パッチの行、パッチの列又はパッチのアレイを形成するようにパッチ境界を拡張することによって不規則及び規則的なパッチ分割を図１のシステム内で規則的にする態様の例を示す概略図である。
【図４Ａ】図１のシステム内で使用される不連続的な２Ｄ曲面のグラフ図である。
【図４Ｂ】図１のシステム内で使用される連続的な２Ｄ曲面のグラフ図である。
【図５】入力画像及び出力画像の双方をスケーリングする解像度の変更を行うための、図１に示すシステムの使用態様を示す概略図である。
【図６】ズーミングマップを得るための、図１に示すシステムの使用態様を示す概略図である。
【図７】本発明の変換方法の一般的なフローチャートである。
【技術分野】
【０００１】
本発明はデジタル画像データの変換に関し、より詳細にはデジタル画像データの２次元空間変換の表現に関する。
【背景技術】
【０００２】
大抵の画像処理システムは、一部分において空間変換システムとみなすことができる。２次元の（２Ｄ）画像処理では、入力データ（場合によっては３Ｄ）との関係に従って２Ｄ出力空間内の各ピクセルに「カラー」値を割り当てることにより画像が生成される。入力データ空間と出力データ空間に座標系を採り入れることで、この関係は空間マッピングとして都合よく表される。空間マッピングは、画像処理システムの設計（レンズ構成など）に内在していてもよいし、一定の効果を得るように明確に特定されていてもよい。２Ｄの入力画像と出力画像の間、又は２Ｄの入力空間と出力空間の間のマッピングを指す用語である画像ワーピングは、画像キャプチャデバイス及び画像表示デバイスによくみられる収差などの光学的歪みや種々のアーチファクトの補正にしばしば適用される。画像ワーピングの他の用途としては、特殊効果、アニメーション、画像のスティッチング及び一般的な幾何学変換が含まれる。一般に、画像ワーピングは空間変換である必要はないが、ここでは空間マッピングを重要視する。
【０００３】
ハードウェア実装の簡略化を主な目標として、多くの電子画像歪みアルゴリズムや電子画像変換アルゴリズムが設計されている。この目標によって空間変換の複雑さが制限されたり、変換の記述が非現実的になってしまうことが多い。例えば、画像ワーピングによく用いる方法は２パス法である。２パス法に基づいた特定のワーピングシステムとして、ベネットら(Bennett et al.)の米国特許第４，４７２，７３２号に詳述されるアンペックス(Ampex)デバイスがある。この文献に開示される方法はリアルタイム画像処理システムのハードウェア実装に好適で、２Ｄマップを１Ｄフィルタリング又は再サンプリングのみが必要な一連の１Ｄマップに分解する。１Ｄでの再サンプリングは２Ｄでの再サンプリングよりもはるかに簡単で、種々の構造を用いたハードウェアの高最適化を可能にする。しかし、２パス法はボトルネック効果を生じる傾向にある。即ち、中間画像に大きな圧縮が生じ、データが損失してしまう。極端な例では、ある領域が圧縮されて線になってしまう場合など、完全なデータ損失が生じうる。この効果は、適用可能な幾何学変換のタイプを制限してしまう。２パス法に関連する他の問題は中間パスデータの生成を含む。
【０００４】
これらの問題を解決するため、セイア(Sayre)の米国特許第５，１７５，８０８号やウォルバーグら(Wolberg et al.)の米国特許第５，２０４，９４４号に述べられるように２パス法に対して種々の強化が試みられており、これらの方法はピクセル毎の記述(description)(即ちルックアップテーブル）に基づいている。ピクセル毎の記述は大きな記憶領域を要し、更に重要なことに、追加のデータ操作を行うための簡単な手段を許容しない。画像がワープされると、ズーム操作などの第２の変換が必要となる。ピクセル毎の記述では、ズーミングワープのためにグリッド全体を再生成する必要がある。この再生成は、ズーミングが通常使用される機能である場合は特に非効率的となりうる。
【０００５】
空間変換の他のアルゴリズムは、必ずしも２パス法に基づいているわけではないが、回転、線形スケーリング、アフィン、そしてファント(Fant)の米国特許第４，８３５，５３２号、キマタら(Kimata et al.)の米国特許第４，９７５，９７６号、ハンバーグ(Hamburg)の米国特許第５，８０８，６２３号及びレヴィエン(Levien)の米国特許第６，０９７，８５５号に記載のような各変換などの一定のマッピングタイプに限られている。従来技術の方法の中にも物理的なメモリ空間を用いて数学的な座標空間を識別する傾向のものがいくつかあり、これは、ハードウェア実装の際に変換がメモリ構造の構成によって制限されてしまうことを意味する。また、大抵のワーピングアルゴリズムは、独立した変換を画像の種々の部分に適用するための簡単なフォーマットを提供しない。（例えば、円形画像から長方形画像への）トポロジーの変化のような複雑なマッピングでは、種々の領域に独立したマッピングが必要である。
【０００６】
これらの制限は、２Ｄフィルタリングを利用する２Ｄ表現、即ち１パスを用いて取り除くことができる。２Ｄ表現に基づいたシステムの例としては、オーギンクら(Orginc et al.)の米国特許第５，３８４，９１２号のビデオプロセッサ及びディスプレイユニット、並びにフェアチャイルドセミコンダクター社(Fairchild Semiconductor)製造の集積回路ＴＭＣ２３０２Ａがある。しかし、これらの従来技術の方法は２Ｄ変換の制限されたサブセットに基づいているため、一般的な２Ｄマッピングを表現することができない。特に、これらのシステムはいずれも、独立した変換を単一画像の種々の部分に適用する手段を提供しない。
【特許文献１】米国特許第４，４７２，７３２号明細書
【特許文献２】米国特許第５，１７５，８０８号明細書
【特許文献３】米国特許第５，２０４，９４４号明細書
【特許文献４】米国特許第４，８３５，５３２号明細書
【特許文献５】米国特許第４，９７５，９７６号明細書
【特許文献６】米国特許第５，８０８，６２３号明細書
【特許文献７】米国特許第６，０９７，８５５号明細書
【特許文献８】米国特許第５，３８４，９１２号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、１つの態様において、入力ピクセル座標を有する入力画像を出力ピクセル座標を有する出力画像に変換する２次元画像変換を１パスで実施する電子システムを提供する。
【課題を解決するための手段】
【０００８】
このシステムは、
（ａ）ディスプレイの光学構成を記述するレンズパラメータ、投影角、平面スクリーン及び湾曲スクリーンのディスプレイパネル形状、並びにユーザ指定パラメータを含み、前記変換を定義する形状パラメータを得る形状入力インタフェースと、
（ｂ）前記形状入力インタフェースに結合されており、前記出力ピクセル座標を前記入力ピクセル座標上にマップするグリッドデータ変換を生成するグリッド変換発生器と、
（ｃ）前記グリッド変換発生器に結合されており、基本的な形状に従って前記出力ピクセル座標の空間を多数の対応パッチに分割し、出力空間パッチの境界を決定するパッチ形状発生器であって、各パッチは関連するグリッドデータセットを有する、前記パッチ形状発生器と、
（ｄ）前記パッチ形状発生器に結合されており、各パッチの前記グリッドデータセットを曲面係数によって表された曲面関数としてパラメータ化する曲面関数推定器と、
（ｅ）前記曲面関数推定器に結合されて前記曲面係数を記憶する出力インタフェースと、
を含む。
【０００９】
他の態様において、本発明は、入力ピクセル座標を有する入力画像を出力ピクセル座標を有する出力画像に変換する２次元画像変換を１パスで行うために表現する方法を提示する。この方法は、
（ａ）ディスプレイの光学構成を記述するレンズパラメータ、投影角、平面スクリーン及び湾曲スクリーンのディスプレイパネル形状、並びにユーザ指定パラメータを含み、前記変換を定義する形状入力パラメータを得ることと、
（ｂ）前記出力ピクセル座標を前記入力ピクセル座標上にマップするためにグリッドデータ変換を前記形状入力パラメータに基づいて生成することと、
（ｃ）基本的な形状に従って、前記出力ピクセル座標の空間を、各々が関連するグリッドデータセットを有する多数の対応パッチに分割し、出力空間パッチの境界を決定することと、
（ｄ）前記パッチの各々における前記グリッドデータ変換を曲面係数によって表された曲面関数としてパラメータ化することと、
前記曲面係数を記憶することと、
を含む。
【００１０】
本発明の実施の形態の異なる態様及び利点の更なる詳細は、添付の図面と共に下記の説明において明らかになる。
【発明を実施するための最良の形態】
【００１１】
まず、本発明の好適な実施の形態に従って作られたワープシステム１００の例を示す図１を参照する。ワープシステム１００は、形状入力インタフェース１１０、グリッド変換発生器１２０、パッチ形状発生器１３０、曲面関数推定器１４０、誤差分析段階１５０、バウンディングボックス発生器１６０、解像度／ズーム発生器１７０、データ再構成段階１８０及び出力インタフェース１９０を含む。
【００１２】
ワープシステム１００は、（ピクセル毎の）グリッドデータ表現を、効率的なリアルタイムのハードウェア実装により曲面関数表現に変換する。２Ｄ空間変換の適用が必要なシステムはいずれもワープシステム１００を利用することができる。ワープシステム１００は、プロジェクタ、カメラ及び表示デバイスにおける小さな歪みの補正から、キーストーン補正や特殊な広角レンズ補正などの遠近感補正、そして、円形の３６０°画像からの長方形パノラマの形成や、他の長方形から極型のマッピングなどの画像形状の完全な変化に及ぶ用途に使用可能である。
【００１３】
形状入力インタフェース１１０は、少数の形状パラメータに関する変換の記述を得るか又はこれを含んでいる。これらのパラメータは、最高レベルの変換の記述（即ち定義）を提供する。例としては、投影角及びレンズ投射比に関するキーストーン変換の記述、放射状３次多項式関数（ここで、パラメータは４つの多項式係数である）に関するレンズ補正の記述、又は曲率半径に関するディスプレイ曲面の記述がある。少数の形状パラメータに関する閉じた記述が利用できない極端な例では、点の小さなサブセットのマッピングをもたらす数値記述の使用が必要になる場合がある。
【００１４】
グリッド変換発生器１２０は形状入力インタフェース１１０に結合している。グリッド変換発生器１２０は、形状入力インタフェース１１０から得た入力形状パラメータを用いて空間変換のグリッドデータ記述を生成する。この記述は、変換の実施後に対応する形状マッピングを定義し、新しいピクセル位置を提供する。グリッド変換発生器１２０は、逆マッピング変換、即ち出力画像の各ピクセルを入力画像のどこにマッピングしたかを指定する空間変換を用いる。このアプローチは、出力における水平／垂直の走査線内の各出力ピクセルに対してピクセルの処理順に値を割り当てることを確実にする。一方、従来から知られている順方向マッピングは、割り当てられていないピクセルによって出力画像に「穴」を残す場合がある。
【００１５】
ここで図２を参照すると、入力座標空間で入力画像のピクセルＰ’を得るために出力画像の座標空間内のピクセルＰに実施される逆マップとしての一般的な２Ｄ変換のグラフ図が示されている。一般的なワープは、入力座標空間の非整数の位置に点をマップする。ピクセルは、各格子点を取り囲む点線の正方形で示すように、数学上の点としてではなく有限の領域を有するものとしてモデル化されることが多い。よって、出力空間のピクセルＰを正方形ＡＢＣＤとみなし、この正方形を、入力座標空間のＰ’を取り囲む任意の形状ＡＢＣＤにワープする。入力空間では、ピクセルＰ’をピクセル１、２、３及び４と重複するものとみなすことができる。
【００１６】
図２に示すように、入力空間及び出力空間の原点が対応する各画像の左上隅にあると定義し、そこから正のｘが右に向き、正のｙが下に向いている。入力画像及び出力画像は一般に何らかの形態のメモリに記憶されているか又は書き込まれているため、本開示物は入力画像空間及び出力画像空間を入力メモリ空間及び出力メモリ空間と呼ぶことがある。一般に、グリッドデータ記述を以下の公式によって要約することができる。
【００１７】
Ｕ＝Ｆu（Ｘ，Ｙ）
Ｖ＝Ｆv（Ｘ，Ｙ） （１）
【００１８】
これらの式は、座標（Ｘ，Ｙ）を有する出力画像のピクセルが、空間変換Ｆ＝（Ｆu，Ｆv）によって座標（Ｕ，Ｖ）を有する入力画像のピクセルにマップされることを示している。従って、グリッドデータセット関係（又は単にグリッドデータセットと呼ぶ）｛（Ｕi，Ｖi），（Ｘi，Ｙi）｝は出力空間のピクセル｛（Ｘi，Ｙi）｝のセットであり、これらのピクセルは入力空間のピクセル｛（Ｕi，Ｖi）｝に逆マップされる。前述のように、座標｛Ｘ，Ｙ，Ｕ，Ｖ｝は物理的なメモリアドレス空間の座標である。この関係は以下のように表される。
【００１９】
【数１】
【００２０】
空間変換の定義には２つの一般的な従来のアプローチがある。第１に、マッピング（Ｆu，Ｆv）の陽関数形態を識別するか又は構築することができ、これは、空間変換のための明示的な数学モデルを有することを意味する。第２に、グリッドデータセット関係｛（Ｕi，Ｖi），（Ｘi，Ｙi）｝は、出力空間の一部又は全てに関連して識別するか又は構築することができる出力ピクセル位置（Ｘi，Ｙi）に対応する入力ピクセルの位置（Ｕi，Ｖi）をもたらす。図２に示すように、出力位置（Ｘi，Ｙi）は整数値であり、通常は出力メモリ空間の定期的なサンプリングによって構成されるが、マップされた入力ピクセルの位置（Ｕi，Ｖi）は一般に非整数である。この数学モデルは通常は形状入力インタフェース１１０における少数の形状パラメータに関する記述に関連しているのに対し、グリッドデータセットは少数の点に関する数値記述に関連している。数学モデルのアプローチでは、グリッドデータセットを得るためにマッピングを常に評価しうるため、第２のアプローチがより普遍的である。
【００２１】
グリッドデータセット関係モデルは空間変換の「理想的」表現であると考えられている（実際には、グリッドデータはノイズを含む場合があり、その場合は「理想的」自体おおよそである）。しかし、データセット（即ち関数）は画像の領域によって大きく変わるため、この記述は非常に複雑になる場合がある。このような表現に直接的に基づいた画像変換システムは、ソフトウェア又はハードウェアでの実施が難しい。グリッドデータセット｛（Ｘi，Ｙi）｝又はグリッドデータセット関係｛（Ｕi，Ｖi），（Ｘi，Ｙi）｝は出力空間全体に広がり、グリッドデータのコンポーネントは本質的にピクセル毎の表現と同じである。この意味では、２Ｄ空間変換の表現におけるグリッドデータセットの使用は、ピクセル毎の（ルックアップ／変位テーブル）記述を用いるいずれの従来技術においても暗黙の前提である。しかし、ピクセル毎の表現はハードウェア実装には非効率的である。本発明のワープシステム１００は、グリッドデータ（ピクセル毎の）関係表現を曲面関数表現に変換する。
【００２２】
関数表現の前にしばしばなされる簡素化は、２パス処理のためにデータを分離することである。従来から知られているように、分離を用いる主な利点は、対応するハードウェア実装が簡単になることである。スケーリングデータを垂直及び水平のパス（即ちデータセット）に分離することで、１Ｄフィルタリングの使用が可能になる。しかし、これによって画質が犠牲になり、また、全てのマッピングを分離できるわけではない。メモリ空間及び速度における現在の進歩により、効率的な２Ｄフィルタリングを行う１パスが実装可能となった。このような実装の一例はｓｘＴ２チップ（カリフォルニア州サンノゼのシリコンオプティックス社(Silicon Optix Inc.)製造）である。よって、２パス処理の分離から得られた従来技術のハードウェアの利点は、画質及び変換の柔軟性を維持する、という更に重要な目標に取って代わられる。本発明の方法は分離を使用しないが効率的なハードウェア実装を可能にし、一般的な２Ｄマッピングを表現するのに十分な柔軟性を保つ。この方法は１パスであるため、（２Ｄフィルタの使用時に）生じる画質は２パス法のものよりも優れている。
【００２３】
本発明の有用性を十分に理解するには、ハードウェア処理を簡素化するために出力空間での２Ｄ変換の評価によく使われる走査線処理を理解することが重要である。この変換は、従来技術のように２パスでもよいし、本発明のように１パスでもよい。走査線処理では、出力ピクセルを行（水平）及び／又は列（垂直）に沿って連続的に生成する。行／列を完全に生成した後、処理は次の行／列に進む。走査線処理の変形例としては、まず各行／列のセクション、例えばセクション１を処理し、次に、（各行／列のセクション１の処理後に）セクション２を処理するなどがある。この変形例は、両方向の走査線処理を組み合わせる。出力における走査線処理は、入力画像データに実施される処理のタイプを制限しない。特に、２Ｄフィルタリングを使用することができる。
【００２４】
出力において走査線処理を使用することの主な制限は、入力における（フィルタリングに必要なピクセルデータの）メモリアクセスがランダムになりうることである。（ほぼ連続的に処理される）出力空間の近隣のピクセルは大きな領域にわたって広がる入力空間のデータを必要とする場合があるため、入力メモリアクセスが非効率的になる。このことはフィルタリングでは問題となりうる（処理が遅くなり、時間遅延が長くなる）が、本発明の焦点である、変換を記述する曲面多項式の評価ではさほど問題にならない。本発明では、曲面多項式は出力空間で定義され、入力ピクセルデータにアクセスする必要がない。
【００２５】
走査線処理のために、出力空間の全てのピクセルに空間変換を定義する必要がある。これは、データセット記述から、各ピクセルの理想的なマッピングに最も近似する関数記述に進むことを意味する（サンプリングを行ったピクセルに関しては、理想的なマッピングは公知のグリッドデータセット関係によってもたらされることを想起する）。数学モデルが明確に定義されていない領域に対しては、関数記述は明確なデータを推定したり、このような領域をバックグラウンドにマップすることができる。数学モデルの不明確な領域は常にバックグラウンドピクセルに対応するため、後者の対応の仕方は許容可能である。
【００２６】
図３はパッチ形状発生器１３０の機能を示している。パッチ形状発生器１３０は、データの曲面フィッティングが行われる出力空間（図２）で定義された長方形パッチのアレイを生成する。パッチは同一サイズである必要はないが、この特定の実施では規則的な態様ではまり合うべきである。この文脈における「規則的な」という用語は、パッチを行及び／又は列に配置できることを意味するように意図されている。長方形パッチによるいずれの分割も規則的な配列をもたらすことができるため、このことは限定的ではない。規則的及び不規則的なパッチ分割を図３に示す。パッチの数は、ワープの複雑さ、フィッティング誤差の許容レベル（後述）、フィッティングに用いる基底関数のタイプ、そして実施上の制約によって決定される。原則として、隣接する４つのピクセル点からなる各セットにパッチを割り当てることができるが、空間変換を記憶するのに大容量のメモリが必要となる。
【００２７】
グリッド変換の関数記述を生成する曲面関数推定器１４０がパッチ形状発生器１３０に結合されている。空間変換の関数記述を得るためによく使われる方法は、グリッドデータを走査線のサブセットに垂直及び／又は水平にフィットすることである。このフィッティングは通常は最小２乗ベースであるとともに、基底関数が多項式であることが多い。走査線のフィッティングの欠点は、（ａ）大量のデータ、即ちフィットする走査線毎に１セットの多項式係数を記憶する必要があることと、（ｂ）個々の走査線をフィットすることによって走査線間のワープのグローバルな記述が失われることである。特に、走査線をピクセルの行又は列毎にフィットしない場合（メモリの制約のためによくある）、内挿を行って走査線間のグリッドデータを得る必要がある。ワープのグローバルな記述を考慮しない内挿はいずれの形態でもピクセル位置の誤差を生じ、ワープの重大さによっては非常に大きな誤差になりうる。
【００２８】
両方の座標のグリッドデータに曲面フィッティングを行うことにより、これらの２つの問題を解くことができる。１パス及び２パス両方の方法に用いる曲面フィッティングは、２Ｄ空間変換を記述する自然な方法である。曲面フィッティングは、両方向の形状挙動を同時に組み込んだ正確な記述をもたらす。曲面フィッティングを多項式法によって成し遂げる場合、曲面フィッティングとは、単一方向の走査線フィッティングを記述する多項式係数をフィットすることを意味する。曲面はマッピングの完全な２Ｄ記述をもたらすが、曲面の評価を走査線の順で垂直又は水平に進めることができる。よって、効率的な走査線アルゴリズムを用いて曲面ベースの記述を実施することもできる。
【００２９】
ここで図１及び図３を参照すると、曲面関数推定器１４０は、後述するように、選択された基底系を用いて各長方形パッチのグリッドデータを曲面にフィットする。この処理は、データが多値ではない、即ちフォールディングがないことを想定していることに注意されたい。リアルタイムのハードウェアの実施では、最も一般的に選択されるフィッティングはｘ及びｙ双方の３次多項式曲面である。曲面フィッティングは理想的なデータセット関係｛（ｕi，ｖi），（ｘi，ｙi）｝に関数近似をもたらす。曲面関数はｕi＝Ｓnu（ｘi，ｙi）などと示される。出力座標空間の原点は、パッチ毎に再定義される相対的な原点となるように選択される。これは、例えば各パッチの左上隅に定義されるように原点を選択できることを意味する。このことにより、フィッティング及び曲面の評価に関連する数値の範囲が狭まる。この数値範囲の減少は、特にハードウェアの演算器における数値誤差を減少させるのに重要である。
【００３０】
ここで、多項式ベースのアプローチの特定の実施をより詳細に説明する。多項式関数（形式ｘiｙjの項）は、ハードウェア実装に用いられる最も一般的な非自明関数である。Ｂ−スプライン曲面のような多項式ベースの曲面はいずれもこの形式にすることができる。下記の記数法が種々のフィット曲面に用いられる。
【００３１】
【数２】
【００３２】
ここで、曲面を評価する座標はデータセット内のサンプルピクセルだけでなくパッチ全体にわたっている（下付きのｃは計算されたことを示す）。曲面の次数はｘ方向のＫ及びｙ方向のＬであり、これらは互いに異なっていてもよい。フィットから得られる曲面係数｛Ｓnu,kl，Ｓnv,kl｝は全てのパッチの曲面を一意的に定義する。
【００３３】
曲面フィッティングは、グリッドベースの表現即ち｛（ｕi，ｖi），（ｘi，ｙi）｝から、（パッチｎに対する）下記のような曲面多項式（関数）ベースの表現に移行する。
【００３４】
【数３】
【００３５】
前述のように、ｖに対しても同様に移行する。多数のグリッドデータ関係点｛（ｕi，ｖi），（ｘi，ｙi）｝を記憶するのではなく、曲面係数Ｓnu,klのみを記憶すればよい（即ち全ての曲面／パッチに対し）。次に、この曲面を評価し、逆マップしたピクセル位置を決定することができる。このフィッティング手順は曲面係数を決定する。異なる方法及びフィッティング関数を用いてデータをフィットすることができるが、フィッティングに最も一般的に用いられるのは最小２乗法である。
【００３６】
図４は、出力座標空間の４つの長方形パッチのアレイへの分割に基づいて、曲面関数推定器１４０によって生成された２Ｄフィット曲面の２つの例を示している。ここで、図４Ａに示す曲面は不連続的であるのに対し、図４Ｂに示す曲面は連続的である。不連続性の考察を更に後述する。
【００３７】
誤差分析段階１５０は、これらの曲面を得ると、２Ｄデータセットの出力座標点毎に関連する曲面関数を評価してｕic及びｖicの値を得る。誤差分析段階１５０は、グリッド変換発生器１２０から別に受け取った２Ｄグリッド記述からの正確な座標（（ｕi，ｖi））とこれらの値を比較する。次に、誤差分析段階１５０は、所定の誤差許容レベル条件（｜ｕic−ｕi｜，｜ｖic−ｖi｜）が満たされているか否かを判断する。予め設定された許容レベル条件が満たされていない場合、誤差分析段階１５０は誤差分析の結果をパッチ形状発生器１３０に送る。これらの結果に基づいて、パッチ形状発生器１３０はパッチ形状を更に細分する。誤差が許容レベルよりも大きいパッチのみを細分する。パッチの細分によって長方形アレイの規則性が保たれる。細分の主な候補となるパッチは大量のバックグラウンドを含むパッチである。フィッティング誤差は、入力座標空間の外側のバックグラウンドにマップするピクセルに対して大きいことが多い。この場合、これらの点を個々のパッチに関連させ、バックグラウンドにマップする態様でフィットすべきである。次に、関連する非バックグラウンド領域を個別にフィットすることができる。所望の精度を得るまでこれらのステップを繰り返す。曲面関数は所与の実施に対して変わらないことに注意されたい。
【００３８】
本発明の実施例では、パッチ形状の最適化処理は勾配探索及び／又はランダム探索によって行われる。探索はパッチ境界位置のベクトル空間で行われる。パッチのＭ×Ｎアレイの場合、Ｍ＋１のｙ境界（垂直）及びＮ＋１のｘ境界（水平）があり、ベクトル空間にＭ＋Ｎ＋２の次元数をもたらす。
【００３９】
【数４】
【００４０】
【数５】
【００４１】
【数６】
【００４２】
前述の曲面表現に関する重要な点をいくつか強調する必要がある。必要であれば、各パッチを独立した出力座標空間とみなし、このパッチのデータセットをそれ自体が独立した２Ｄ変換とみなすことができる。特に、各パッチを独立してフィッティングすることができ、このことは出力画像が連続的である必要がないことを暗示している。パッチの不連続及び連続的な曲面フィットの例を図４Ａ及び図４Ｂに示す。図４Ａに示す４つのパッチを更に分割してフィッティングを改良することができる。具体的には、１０２４×７６８のｘ−ｙ出力空間を４つのパッチに分割し、曲面（ｕ（ｘ，ｙ））をプロットした。図４Ａでは、曲面はパッチにわたって不連続的である。各パッチは独立したデータセットを有し、このデータセットは近隣のデータセットから独立してフィットされている。図４Ｂでは、曲面はパッチにわたって連続的であり、この場合、いずれのパッチのフィットも連続性を確実にすることが必要である。
【００４３】
パッチ境界にわたる画像の連続性を維持する更に一般的な状況では、連続性の制約を陽的に許容するか又はこれらの制約を課す基底関数を使用することができる。２Ｄでの連続性を制御する最もよく知られた関数はＢ−スプライン曲面及びベジエ曲面である。両タイプの曲面を用いて、（Ｃiの連続関数の数学的意味における）所要の程度の連続性を得ることができる。Ｂ−スプラインでは、テンソル積アプローチを用いてパッチのＭ×Ｎアレイに曲面フィットを行うことができ、パッチ分割はスプラインのノットから容易に得られ、逆の場合も同じである。ノット列を調節することにより、Ｂ−スプライン曲面の連続性を容易に制御することができる。双３次Ｂ−スプラインを用いて、最大でＣ2までの連続性を課すことができ、これは全ての目的に十分である。（通常は、滑らかな画像を得るにはＣ1で十分である。）不連続な曲面、即ち独立したパッチは、適切なノット列を有するＢ−スプラインの特殊なケースとみなされる。また、スプラインを、多項式ベースとしたハードウェア実装に自然に変換可能となるよう、相対的な原点を有する（各パッチに対する）局所的多項式の形式で書き込むこともできる。Ｂ−スプラインフィッティングのツールが多くの数値／数学的計算ソフトウェアパッケージによって利用可能である。また、各独立パッチを異なる演算に関連させることができる。（パッチ境界にわたる任意の連続性の）パッチベースの曲面記述は、非常に複雑な２Ｄ空間変換の表現を可能にする。
【００４４】
一般的な２Ｄ空間変換の完全な表現は下記のデータによってもたらされ、各パッチに適用される。
１）パッチの形状（パッチ原点の絶対的な位置、パッチサイズ）
２）グリッドデータ関係への曲面フィットを記述する曲面係数
【００４５】
この表現は、２Ｄマッピングを定義する統一フォーマットを提供する。この表現は、２Ｄ画像変換システムのリアルタイムのハードウェアの実施を対象としている。ハードウェア実装では、曲面多項式を走査線順に評価し、位置及び導関数情報を処理フィルタに通す。（導関数は位置の曲面から容易に抽出される。）マッピングは閉じた関数の形でもたらされるため、完全な形状データ（種々の次数の導関数）はフィルタリング段階に容易に利用可能である。
【００４６】
マップの複雑さが増すにつれて、パッチの数、よって前述の（１）及び（２）の表現に含まれるデータの量が増加する。データは、全体的なフォーマットを一切変えずにマッピングの複雑さに合わせて調整する。また、パッチ数の増加はフィッティング誤差を減少させるように機能する。原則として、パッチアレイを連続的に細分することにより、最大のフィッティング誤差を任意の小さなレベルに下げることができる。しかし、実際には、データの記憶に利用可能な空間（メモリ）の容量（各パッチにはデータコンポーネント（１）及び（２）が関連している）に対する制約により、パッチの数は制限される。メモリ要件と誤差の最小化（許容レベル）のバランスをとることによって最終的なパッチアレイサイズを決定する。
【００４７】
実施対象となる大抵の２Ｄ変換は高解像度パッチメッシュを必要としない。サイズや誤差に関するこれらの問題を定量化するために、前述のフォーマットを用いて２Ｄマッピングをいくつか検討した。これらの２Ｄマッピングは、（ｉ）放射状ピンクッション型歪み及び樽型歪みのような共通のレンズ歪み、（ｉｉ）垂直／水平キーストーン補正及び湾曲面への射影などの射影、（ｉｉｉ）線形スケーリングと組み合わせた回転、（ｉｖ）前述したものの組み合わせ、（ｖ）アークラスタマップのような更に複雑なマップ、（ｖｉ）（魚眼レンズ又は特殊３６０°イメージング（撮像）システムを用いて得られた）広角／３６０°／パノラマ画像の補正を含む。
【００４８】
パッチ毎に１６の曲面係数を示す３次（Ｋ＝Ｌ＝３）の多項式曲面を使用した。０．５ピクセルの誤差限界を設定した。（ｉｉ）−（ｉｖ）の変換では、最大で４つのパッチが必要であった。マップ全体を定義するには、曲面係数の合計が１２８以下になる。曲面係数を４バイトの浮動小数として記憶した場合、データサイズは５１２バイト以下になる。この数は非常に妥当な数であり、オンボード／オンチップメモリによって容易に受け入れられる。
【００４９】
（ｉ）及び（ｖ）の変換では（双方の座標のために）最大で合計２６のパッチが必要であった。これは１．６２５キロバイト以下のデータサイズをもたらすため、この場合も現行のオンボード／オンチップメモリによって容易に処理される。（ｖｉ）の変換では、９０°の広角に対して行う透視補正は最大で合計１８のパッチ、即ち１．１２５キロバイト以下を必要とする。この表現の機能を全て使用する場合は、（ｖｉ）から得た画像に複雑な変換を実施することができる。例えば、２つの１８０°魚眼レンズからの画像を、スティッチングした３６０°のパノラマビューと、例えば透視補正を施した特定領域の２つの９０°の拡大ビューに変換することができる。このような変換は約６つのマップ（３６０／９０＋２）に相当し、その各々が、６．７５キロバイト以下のデータサイズである特定の９０°領域を変換する。このような特殊広角／３６０°ベースの変換は、特にセキュリティの用途でここ数年人気が出ている。従って、前述の方法は一般的な２Ｄ変換を適度なデータサイズ（サイズは複雑さに対して直線的に増加する）とサブピクセル精度で表現できることがこれらの結果から明らかである。
【００５０】
【数７】
【００５１】
非バックグラウンドピクセル境界は通常は長方形でないため、全てのバックグラウンドピクセルをこのように識別するわけではない。しかし、バウンディングボックスをより細かく、おそらくパッチ毎に１つよりも多く分割することで、（バウンディングボックス座標に必要な）更に多くの記憶を犠牲にしてこの境界を長方形のバウンディングボックスに綿密に近似させることができる。大抵の変換ではバウンディングボックスデータは不要であり、極端な変換ではパッチ毎に１つのバウンディングボックスで十分である。
【００５２】
バウンディングボックスデータを使用しない場合、より標準的なアプローチを用いて不要な処理を取り除くことができる。標準のアプローチでは、全ての出力ピクセルの曲面を評価し、照合を行って、生じた座標が入力空間内に存在するか否かを判断する。座標が入力空間内にある場合、処理は通常通りに進む、即ち出力ピクセルのカラー値を２Ｄフィルタリングによって決定する。座標が入力空間の外側にある場合、単純にバックグラウンドカラーをピクセルに割り当て、２Ｄフィルタを実行しない。ここでは、曲面を評価する必要はあるが、フィルタがこれらのデータを処理しないという事実によって得られる利益はかなり大きくなりうる。また、非バックグラウンドピクセル境界は入力空間への曲面のマップによって完全に指定されるため、この境界を非常に正確に決定することができる。
【００５３】
ワープシステム１００の画像変換により、２Ｄ画像変換を記述するパラメータの完全なセットが決定される。本発明の１つの実施では、これらのデータは解像度／ズーム段階１７０によって使用され、次いでデータ再構成段階１８０によって使用される。これらの段階の前に、パッチ形状発生器１３０及び曲面関数推定器１４０からそれぞれ生じた基本的なパッチ形状及び曲面係数で構成されるマッピング表現を、バウンディングボックス発生器１６０の出力において決定する。
【００５４】
図５及び図６に示すように、解像度／ズーム発生器１７０を使用して解像度の変更及びズーミング効果を入力／出力画像に提供し、前述の画像パラメータを利用することができる。ワープシステム１００の画像変換の位置ベース表現を用いて、係数の簡単なスケーリングを行うことで空間変換を異なる解像度に合わせて容易に調節することができる。図５は、入力画像及び出力画像の双方をスケーリングする解像度変更動作に関連するステップを示している。入力／出力座標の個々のスケーリングを以下のように表すことができる。
【００５５】
【数８】
【００５６】
定数｛ｒ1，ｓ1，ｒ2，ｓ2｝は倍率を示し、ダッシュ記号はスケーリングした座標を示す。スケーリングした座標に関して、曲面を以下のように表すことができる。
【００５７】
【数９】
【００５８】
従って、入力解像度又は出力解像度の変更に合わせて調節するために、全ての係数を因数でスケーリングする。これは比較的簡単な演算で、再フィッティングや内挿を必要としない。しかし、パッチ形状（即ちパッチサイズ及びパッチ原点の絶対的な位置）もワープシステム１００によって適切にスケーリングする必要があることを理解されたい。
【００５９】
図６は、ワープシステム１００によって行われる画像変換内のズーミングマップの生成に関連するステップを示している。ベース入力画像、ベース出力画像及びスケーリングしたベース出力画像は、ベースワープ及びズーム対象領域を示している。まず、ベース出力画像をスケーリングし（即ち、スケーリングしたベース出力画像を生成し）、次に（スケーリング動作で適切にズーミングした）対象領域を抽出／トリミングすることでズーミングワープを生成する。ズーミングマップは、新しい入力画像と新しい出力画像との間に示す変換に相当する。ズーミング動作は異なる解像度に対するスケーリングと同様であるが、特定の領域を拡大／縮小することができるという違いがあり、これはパニング機能を示している。ズーム動作を入力画像空間（変換前）又は出力画像空間（変換後）に対して定義することができる。ワープシステム１００の以下の例示的な用途では、出力空間のズーミングを述べる。ズーム比Ｋを＞１となるように選択する（Ｋ＝２の場合は２×ズームなど）。他のケースも同様に処理する。
【００６０】
【数１０】
【００６１】
数学的には、ズーミングの第１のステップは乗算演算であり、第２のステップはシフト又は加算演算である。ベース出力空間及び新しい出力空間での絶対位置は下記式によって関連付けられる。
【００６２】
【数１１】
【００６３】
ベースマップのｎ番目のパッチの左上隅（１の指数で示す）及び右下隅（２の指数で示す）を以下のように示す（これらは絶対位置であるが、下付きのＡは表示を簡略にするために省略する）。
【００６４】
｛（ｘ１n，ｙ１n），（ｘ２n，ｙ２n）｝ （１４）
【００６５】
これらの点を、下記の新しい空間の新しい端点にマップする。
【００６６】
【数１２】
【００６７】
パッチの新しい幅又は高さが０以下である場合、このパッチを新しいマップから除外する。幅と高さが共にゼロよりも大きい場合、このパッチをズーミング変換に含める。このパッチの一部のみが含まれる可能性があるため、含めるパッチの絶対位置（即ち左上隅）を再計算する必要がある。新しい位置は下記式によって得られる。
【００６８】
【数１３】
【００６９】
保持する各パッチの新しいパッチ形状（位置及びサイズ）は下記式によって得られる。
【００７０】
【数１４】
【００７１】
新しいパッチ形状がわかったら、式（１２）及び式（１３）を新しい出力空間の相対的な原点表現に変換することができる（パッチの指数を下げる）。
【００７２】
【数１５】
【００７３】
最後に、これらをベースマップの曲面式に代入することができる。
【００７４】
【数１６】
【００７５】
式（２０）を展開し、これらの式を標準の形式と比較することで、新しい曲面係数を直接抽出することができる。これらの係数はパッチの形状と併せてズーミング変換を完全に定義する。
【００７６】
データ再構成段階１８０は、表現データの更なる再構成が必要である特定の画像の操作システムに用いられる。曲面多項式の評価は種々の方法で進めることができ、その詳細（使用する加算及び乗算の数やその次数など）はハードウェア又はソフトウェアの構造に依存する。例えば、多項式の評価に対する一般的なハードウェアアプローチはホーナー法を使用することである（本発明のこの実施は、一般的な表記法を用いた３次多項式を使用する）。
【００７７】
ａｘ3＋ｂｘ2＋ｃｘ＋ｄ＝（（ａｘ＋ｂ）ｘ＋ｃ）ｘ＋ｄ （２１）
【００７８】
同様の技術を曲面の評価に用いることができる。曲面を以下のように書き換えることができる。
【００７９】
【数１７】
【００８０】
曲面をｘの多項式として扱い、ｘ多項式の係数はｙの多項式である。各多項式（全部で５）を、ホーナー法を用いて評価する。各水平走査線（行）では、ｙ多項式を（パッチ毎に）一度だけ評価すればよい。垂直走査線には式（２２）を用いることもできる。この場合、各パッチの第１の垂直走査線（列）に関してｙ多項式を評価し、記憶することができる。そして、これらのｙ多項式は走査線のｘ位置から独立しているため、これらをパッチの残りの垂直走査線に使用することができる。これによって処理速度が上がると共に、この変換は、位置係数自体がｙの多項式であることによって表されるように、ｘに直接依存しｙに間接的に依存する１Ｄ位置の多項式として表される。あるいは、この曲面をｙの多項式として表し、ｙ多項式の係数をｘの多項式とすることができる。実施に応じて、一方又は他方のアプローチをメモリのアクセス／記憶及び演算器の詳細により良く適応するように構成することができる。
【００８１】
多項式を評価する他の標準的な技術は前方差分の使用である。しかし、前方差分の評価は累算の誤差を生じる傾向にある。前方差分の評価の主な利点は、ハードウェアの複雑さを低減すること（具体的には、乗数を減少することと固定小数点を使用できること）である。走査線方向のパッチサイズが小さく、適度な数値精度のビットが利用可能である場合、累算の誤差は小さくなりうる。
【００８２】
図７は本発明の一例の論理フロー７００を示している。ステップ７１０では、各出力ピクセルを入力ピクセルにマップする（逆マッピング）座標対を含むグリッドデータセットを生成する。ステップ７２０では、ワープの基本的な形状及び複雑さに依存するパッチ形状を生成する。ステップ７３０では、グリッドデータセットの記述を曲面フィッティングによって近似し、曲面係数を生成する。
【００８３】
この時点で、曲面データ及びパッチデータが全て生成されている。これらのデータを、ステップ７１０で生成したグリッドデータセットの正確な座標と比較してステップ７４０及びステップ７５０で分析する。ステップ７５２において、パッチ形状及び曲面フィッティングによって生成したピクセルの近似の誤差が所定の許容レベルよりも大きい場合、この情報を用いてステップ７２０のパッチ形状を更に細分する。誤差が許容レベル内になるまでこのループを続ける。
【００８４】
ステップ７６０で誤差分析ステップの条件が満たされると、出力画像のアクティブ領域を決定し、このアクティブ領域を含むバウンディングボックスを抽出する。これは、処理をこの領域に制限して処理時間をある程度節約するためである。
【００８５】
ステップ７７０では、生じうる解像度の変更及びズーミングのためのマップを生成し、曲面係数のスケーリングによってこれらの動作をワープ変換と同調させて実行する。ステップ７８０では、乗数の数を減らすことによってハードウェア実装効率を上げるように変換を再構成する。
【００８６】
本発明のワープシステム１００は、従来技術の画像変換方法にまさるいくつかの有意な利点をもたらす。まず、ワープシステム１００は、走査線処理、少ないメモリ要件及び簡単な多項式ベースの表現を用いることによる、リアルタイム画像変換システムの効率的なハードウェア実装である。このシステムは、任意の変換を統一して表現する。変換は出力空間での曲面−パッチ記述（逆マッピング形式）に基づいており、更なる効果のために容易に操作することのできる閉形式解をもたらす。変換は全て、パッチ形状及び曲面係数を特定するパラメータで構成される。このピクセル毎の記述を、曲面−パッチ記述の限定ケース、即ち曲面を４つのピクセル毎にフィットさせるものとみなすことができる。
【００８７】
また、ワープシステム１００は複雑さに自然に比例する空間変換の記述を提供する。変換が複雑であるほど、必要なパッチの数が大きくなる。即ち、フォーマットは変化せず、記述パラメータの増加は線形である。特に、更なる特徴を表現に組み込む必要がない。表現は、実施対象となる複雑な変換を組み込むのに十分一般的なものである。
【００８８】
また、ワープシステム１００は種々の入力／出力解像度の変換を生成する。この記述はピクセル毎の形ではなく閉じた関数の形でもたらされ、多くのワーピング特徴がパラメータに対する単純な数学演算となる。解像度の変更は曲面係数のスケーリングによって容易に説明される。また、ワープシステム１００はズーミング及びパニングのための効率的なメカニズムを提供する。解像度の変更と同様に、ズーミング及びパニングは曲面係数の線形変換を意味する。グリッドデータの再生成は不要である。「ベース」マップが計算されると、このベース記述のパラメータを直接変更して標準のスケーリング及びシフト変換を実施することができる。
【００８９】
ワープシステム１００は「理想的な」記述と比べて非常に小さな数値誤差を生じる。誤差はパッチメッシュの解像度に大きく依存する。パッチの数を増やすことで、誤差を適宜小さくすることができる。ある点を越えると、誤差を更に小さくしても、広範囲にわたるフィルタのため画質に殆ど影響を及ぼさなくなる。誤差の許容レベルは、通常はメモリの制限によって限定される。更に、基底関数が変更可能である場合は、特定のワープに対して、適切なフィッティング基底を選択することによって（パッチの数を増やさなくても）誤差をごくわずかにすることができる。
【００９０】
ワープシステム１００では、ハードウェア実装にとってこの方法を魅力的なものにする空間変換を記述するためのメモリ記憶空間（即ちデータファイルサイズ）は小さくてよい。実施対象となる大抵の変換では、少数のパッチを用いてサブピクセルの正確な結果を得ることができる。この場合、データファイルサイズは主に、ピクセル毎の大きな位置テーブルではなく少数の曲面係数で構成される。
【００９１】
ワープシステム１００は、非常に一般的なマッピングを得るために個々の変換を画像の種々の部分に適用する。各パッチ（及びそのデータ）は、画像の種々の領域を個々に変換することのできる独立したサブマップとして扱うことができる。この変換を、単一の連続曲面によってグローバルに定義する必要はない。種々のマップを組み合わせたり互いに「スティッチング」して、単一のマップを同一フォーマットで形成することができる。ワープシステム１００は、最適な結果を得るためにＢ−スプラインやベジエ曲面フィッティングのような既知の形状モデル化技術を組み込んでいる。必要に応じて、数値的／数学的に高度な種々の技術を用いて曲面係数を生成することができる。Ｂ−スプライン曲面及びベジエ曲面は本発明のフレームワークに自然に適合する。これらの曲面は、パッチにわたる曲面連続性を明確に制御する。パッチ分割も、スプライン曲面のノットシーケンスから容易に得ることができる。これらの曲面を最小２乗フィッティング技術と共に用いることで、曲面記述生成プロセスを、よく使用される多くの簡単なワープのために自動化することができる。
【００９２】
ワープシステム１００の１つの特定の実施は、フィッティングの制御をより強くするがパッチ形状を複雑にする非長方形のパッチを許容する。本発明のこの例では、パッチ形状をパラメトリック境界曲線によって記述する。このパラメータ化を座標のうちの１つに関連して行うことができ、座標の選択は境界曲線の向きに依存する。長方形パッチの場合、これらの境界曲線は単なる垂直及び水平の線である。任意形状のパッチは、前述の他の特徴と併せて、原則として非常に複雑な２Ｄ画像ワーピングを生成するために極度のレベルの柔軟性をもたらす。
【００９３】
他の実施では、ワープシステム１００は長方形パッチを用いるが、境界パッチ、即ち画像領域とバックグラウンド領域との境をなすパッチの評価ドメインを制限する境界曲線も許容する。このようにして、境界曲線によって指定されたドメイン内にあるパッチ又はパッチの一部のみに全ての計算を行う。このことは、フィッティングを特定の領域に制限するのに役立つ。
【００９４】
複数のパスを含むように前述の方法を展開して画像曲面の層化をサポートすることができる。画像データは、画像の輝度及びクロミナンスのデータにより再サンプリングされる深さ情報を含むことができる。深さ情報は、各ピクセルの可視性又はオクルージョンを決定する層化プロセスに使用される。曲面は同一サイズでなくてもよく、重複していてもしていなくてもよい。
【００９５】
当業者には明らかであるように、前述の構造に対する種々の変更及び適応が本発明から逸脱しない範囲で可能であり、本発明の要旨は添付の請求の範囲に定められる。
【図面の簡単な説明】
【００９６】
【図１】本発明の好適な実施の形態に従って構築されたワープシステムのブロック図である。
【図２】逆マップを出力画像（Ｐ）のピクセルに実施して入力画像（Ｐ’）の対応するピクセルの位置を決定する一般的な２Ｄ変換のグラフ図である。
【図３】パッチの行、パッチの列又はパッチのアレイを形成するようにパッチ境界を拡張することによって不規則及び規則的なパッチ分割を図１のシステム内で規則的にする態様の例を示す概略図である。
【図４Ａ】図１のシステム内で使用される不連続的な２Ｄ曲面のグラフ図である。
【図４Ｂ】図１のシステム内で使用される連続的な２Ｄ曲面のグラフ図である。
【図５】入力画像及び出力画像の双方をスケーリングする解像度の変更を行うための、図１に示すシステムの使用態様を示す概略図である。
【図６】ズーミングマップを得るための、図１に示すシステムの使用態様を示す概略図である。
【図７】本発明の変換方法の一般的なフローチャートである。
【特許請求の範囲】
【請求項１】
入力ピクセル座標を有する入力画像を出力ピクセル座標を有する出力画像に変換する２次元画像変換を１パスで実施する電子システムであって、
（ａ）ディスプレイの光学構成を記述するレンズパラメータ、投影角、平面スクリーン及び湾曲スクリーンのディスプレイパネル形状、並びにユーザ指定パラメータを含み、前記変換を定義する形状パラメータを得る形状入力インタフェースと、
（ｂ）前記形状入力インタフェースに結合されており、前記出力ピクセル座標を前記入力ピクセル座標上にマップするグリッドデータ変換を生成するグリッド変換発生器と、
（ｃ）前記グリッド変換発生器に結合されており、基本的な形状に従って前記出力ピクセル座標の空間を多数の対応パッチに分割し、出力空間パッチの境界を決定するパッチ形状発生器であって、各パッチは関連するグリッドデータセットを有する、前記パッチ形状発生器と、
（ｄ）前記パッチ形状発生器に結合されており、各パッチの前記グリッドデータセットを曲面係数によって表された曲面関数としてパラメータ化する曲面関数推定器と、
（ｅ）前記曲面関数推定器に結合されて前記曲面係数を記憶する出力インタフェースと、
を含む電子システム。
【請求項２】
前記曲面関数推定器、前記パッチ形状発生器及び前記グリッド変換発生器に結合された誤差分析段階を更に含み、
該誤差分析段階が、メッシュ誤差分析を行って、選択された座標点における前記曲面関数のセットのうち１つの評価と前記グリッドデータ記述からの対応座標点との差が予め設定された許容誤差内にあるかを判断し、
該許容誤差内にない場合は前記誤差分析の結果を前記パッチ形状発生器に送り、
該パッチ形状発生器は解像度を更に高くするために前記パッチメッシュを更に細分する、
請求項１に記載のシステム。
【請求項３】
前記画像の前記アクティブ領域の周りにバウンディングボックスを生成して非アクティブ領域に関連する処理を低減するように構成されたバウンディングボックス発生器を更に含む、請求項１に記載のシステム。
【請求項４】
前記曲面座標が前記入力空間内にあるかを判断し、ない場合は前記出力ピクセルのデータの更なる処理を阻止するように構成された、請求項１に記載のシステム。
【請求項５】
前記曲面関数推定器が前記曲面関数を多項式で表すように構成された、請求項１に記載のシステム。
【請求項６】
前記多項式が３次多項式である、請求項５に記載のシステム。
【請求項７】
前記曲面関数推定器が、テンソル積双３次スプラインを用いた最小２乗法によって前記多項式をフィットするように構成された、請求項６に記載のシステム。
【請求項８】
前記曲面関数推定器が、乗算演算を減らすために冪の異なる係数を取り除くことによって多項式を計算するように構成された、請求項６に記載のシステム。
【請求項９】
前記パッチ分割を勾配探索によって最適化する、請求項１に記載のシステム。
【請求項１０】
前記パッチ分割をランダム探索によって最適化する、請求項１に記載のシステム。
【請求項１１】
前記パッチ分割をランダム探索及び勾配探索の組み合わせによって最適化し、まず前記ランダム探索が最適な形状を見出し、次に前記勾配探索が前記最適な形状を微調整する、請求項１に記載のシステム。
【請求項１２】
前記ワーピング動作を繰り返すことなく前記解像度の変更を許容するように、決定された前記曲面係数を変更する解像度変更段階を更に含む、請求項１に記載のシステム。
【請求項１３】
前記ワーピング動作を繰り返すことなくズーミングを許容するように、決定された前記曲面係数を変更するズーミング段階を更に含む、請求項１に記載のシステム。
【請求項１４】
前記曲面をｘの多項式として扱い、該ｘの多項式の係数をｙの多項式とすることによって曲面フィッティングを行う、請求項５に記載のシステム。
【請求項１５】
個々の長方形サブパッチを別々にフィットするように構成された、請求項１に記載のシステム。
【請求項１６】
座標のフィッティングに用いる数の範囲を狭めるために、パッチ上に配置される各パッチの座標原点を再定義するよう、前記曲面関数推定器が構成された、請求項１に記載のシステム。
【請求項１７】
ピンクッション型歪み及び樽型レンズ歪みを含む光学非線形性を補正するように構成された、請求項１に記載のシステム。
【請求項１８】
キーストーン歪みを含む射影歪みを補正するように構成された、請求項１に記載のシステム。
【請求項１９】
湾曲面に射影するように構成された、請求項１に記載のシステム。
【請求項２０】
広角レンズを用いたパノラマ視覚システム内に構成された、請求項１に記載のシステム。
【請求項２１】
請求項１７、請求項１８、請求項１９及び請求項２０に記載の歪みの組み合わせを補正するように構成された、請求項１に記載のシステム。
【請求項２２】
画像の輝度及びクロミナンスのデータによって再サンプリングされる深さ情報を含んだ画像曲面の層化を含むように更に構成されており、前記深さ情報を前記層化プロセスに用いて各ピクセルの可視性又はオクルージョンを決定する、請求項１に記載のシステム。
【請求項２３】
入力ピクセル座標を有する入力画像を出力ピクセル座標を有する出力画像に変換する２次元画像変換を１パスで実施するための表現方法であって、
（ａ）ディスプレイの光学構成を記述するレンズパラメータ、投影角、平面スクリーン及び湾曲スクリーンのディスプレイパネル形状、並びにユーザ指定パラメータを含み、前記変換を定義する形状入力パラメータを得ることと、
（ｂ）前記出力ピクセル座標を前記入力ピクセル座標上にマップするためにグリッドデータ変換を前記形状入力パラメータに基づいて生成することと、
（ｃ）基本的な形状に従って、前記出力ピクセル座標の空間を、各々が関連するグリッドデータセットを有する多数の対応パッチに分割し、出力空間パッチの境界を決定することと、
（ｄ）前記パッチの各々における前記グリッドデータ変換を曲面係数によって表された曲面関数としてパラメータ化することと、
（ｅ）前記曲面係数を記憶することと、
を含む前記方法。
【請求項２４】
メッシュ誤差分析を行って、選択された座標点における前記曲面関数のセットのうち１つの評価と前記グリッドデータ記述からの対応座標点との差が予め設定された許容誤差内にあるかを判断し、該許容誤差内にない場合は解像度を更に高くするために前記パッチメッシュを更に細分することを更に含む、請求項２３に記載の方法。
【請求項２５】
前記画像の前記アクティブ領域の周りにバウンディングボックスを生成し、非アクティブ領域に関連する処理を低減することを更に含む、請求項２３に記載の方法。
【請求項２６】
前記曲面座標が前記入力空間内にあるかを判断し、ない場合は前記出力ピクセルのデータの更なる処理を阻止することを更に含む、請求項２３に記載の方法。
【請求項２７】
前記曲面関数が多項式で表される、請求項２３に記載の方法。
【請求項２８】
前記多項式が３次多項式である、請求項２７に記載の方法。
【請求項２９】
テンソル積双３次スプラインを用いた最小２乗法によって前記多項式をフィットする、請求項２８に記載の方法。
【請求項３０】
乗算演算を減らすために冪の異なる係数を取り除くことによって多項式を計算する、請求項２８に記載の方法。
【請求項３１】
前記パッチ分割を勾配探索によって最適化する、請求項２３に記載の方法。
【請求項３２】
前記パッチ分割をランダム探索によって最適化する、請求項２３に記載の方法。
【請求項３３】
前記パッチ分割をランダム探索及び勾配探索の組み合わせによって最適化し、まず前記ランダム探索が最適な形状を見出し、次に前記勾配探索が前記最適な形状を微調整する、請求項２３に記載の方法。
【請求項３４】
前記ワーピング動作を繰り返すことなく前記解像度の変更を許容するように、決定された前記曲面係数を変更することを更に含む、請求項２３に記載の方法。
【請求項３５】
前記ワーピング動作を繰り返すことなくズーミングを許容するように、決定された前記曲面係数を変更することを更に含む、請求項２３に記載の方法。
【請求項３６】
前記処理の速度を更に上げるために、前記曲面をｘの多項式として扱い、該ｘの多項式の係数をｙの多項式とすることによって曲面フィッティングを行う、請求項２７に記載の方法。
【請求項３７】
個々の長方形サブパッチを別々にフィットする、請求項２３に記載の方法。
【請求項３８】
ハードウェア実装を効率化するために、座標のフィッティングに用いる数の範囲を狭めて、パッチ上に配置される各パッチの座標原点を再定義することを更に含む、請求項２３に記載の方法。
【請求項３９】
ピンクッション型歪み及び樽型レンズ歪みを含む光学非線形性を補正するように適用される、請求項２３に記載の方法。
【請求項４０】
キーストーン歪みを含む射影歪みを補正するように適用される、請求項２３に記載の方法。
【請求項４１】
湾曲面に射影するように適用される、請求項２３に記載の方法。
【請求項４２】
広角レンズを用いたパノラマ視覚システムに適用される、請求項２３に記載の方法。
【請求項４３】
請求項３９、請求項４０、請求項４１及び請求項４２に記載の歪みの組み合わせを補正するように適用される、請求項２３に記載の方法。
【請求項４４】
画像の輝度及びクロミナンスのデータによって再サンプリングされる深さ情報を含んだ画像曲面の層化を行い、前記深さ情報を前記層化プロセスに用いて各ピクセルの可視性又はオクルージョンを決定することを更に含む、請求項２３に記載の方法。
【請求項１】
入力ピクセル座標を有する入力画像を出力ピクセル座標を有する出力画像に変換する２次元画像変換を１パスで実施する電子システムであって、
（ａ）ディスプレイの光学構成を記述するレンズパラメータ、投影角、平面スクリーン及び湾曲スクリーンのディスプレイパネル形状、並びにユーザ指定パラメータを含み、前記変換を定義する形状パラメータを得る形状入力インタフェースと、
（ｂ）前記形状入力インタフェースに結合されており、前記出力ピクセル座標を前記入力ピクセル座標上にマップするグリッドデータ変換を生成するグリッド変換発生器と、
（ｃ）前記グリッド変換発生器に結合されており、基本的な形状に従って前記出力ピクセル座標の空間を多数の対応パッチに分割し、出力空間パッチの境界を決定するパッチ形状発生器であって、各パッチは関連するグリッドデータセットを有する、前記パッチ形状発生器と、
（ｄ）前記パッチ形状発生器に結合されており、各パッチの前記グリッドデータセットを曲面係数によって表された曲面関数としてパラメータ化する曲面関数推定器と、
（ｅ）前記曲面関数推定器に結合されて前記曲面係数を記憶する出力インタフェースと、
を含む電子システム。
【請求項２】
前記曲面関数推定器、前記パッチ形状発生器及び前記グリッド変換発生器に結合された誤差分析段階を更に含み、
該誤差分析段階が、メッシュ誤差分析を行って、選択された座標点における前記曲面関数のセットのうち１つの評価と前記グリッドデータ記述からの対応座標点との差が予め設定された許容誤差内にあるかを判断し、
該許容誤差内にない場合は前記誤差分析の結果を前記パッチ形状発生器に送り、
該パッチ形状発生器は解像度を更に高くするために前記パッチメッシュを更に細分する、
請求項１に記載のシステム。
【請求項３】
前記画像の前記アクティブ領域の周りにバウンディングボックスを生成して非アクティブ領域に関連する処理を低減するように構成されたバウンディングボックス発生器を更に含む、請求項１に記載のシステム。
【請求項４】
前記曲面座標が前記入力空間内にあるかを判断し、ない場合は前記出力ピクセルのデータの更なる処理を阻止するように構成された、請求項１に記載のシステム。
【請求項５】
前記曲面関数推定器が前記曲面関数を多項式で表すように構成された、請求項１に記載のシステム。
【請求項６】
前記多項式が３次多項式である、請求項５に記載のシステム。
【請求項７】
前記曲面関数推定器が、テンソル積双３次スプラインを用いた最小２乗法によって前記多項式をフィットするように構成された、請求項６に記載のシステム。
【請求項８】
前記曲面関数推定器が、乗算演算を減らすために冪の異なる係数を取り除くことによって多項式を計算するように構成された、請求項６に記載のシステム。
【請求項９】
前記パッチ分割を勾配探索によって最適化する、請求項１に記載のシステム。
【請求項１０】
前記パッチ分割をランダム探索によって最適化する、請求項１に記載のシステム。
【請求項１１】
前記パッチ分割をランダム探索及び勾配探索の組み合わせによって最適化し、まず前記ランダム探索が最適な形状を見出し、次に前記勾配探索が前記最適な形状を微調整する、請求項１に記載のシステム。
【請求項１２】
前記ワーピング動作を繰り返すことなく前記解像度の変更を許容するように、決定された前記曲面係数を変更する解像度変更段階を更に含む、請求項１に記載のシステム。
【請求項１３】
前記ワーピング動作を繰り返すことなくズーミングを許容するように、決定された前記曲面係数を変更するズーミング段階を更に含む、請求項１に記載のシステム。
【請求項１４】
前記曲面をｘの多項式として扱い、該ｘの多項式の係数をｙの多項式とすることによって曲面フィッティングを行う、請求項５に記載のシステム。
【請求項１５】
個々の長方形サブパッチを別々にフィットするように構成された、請求項１に記載のシステム。
【請求項１６】
座標のフィッティングに用いる数の範囲を狭めるために、パッチ上に配置される各パッチの座標原点を再定義するよう、前記曲面関数推定器が構成された、請求項１に記載のシステム。
【請求項１７】
ピンクッション型歪み及び樽型レンズ歪みを含む光学非線形性を補正するように構成された、請求項１に記載のシステム。
【請求項１８】
キーストーン歪みを含む射影歪みを補正するように構成された、請求項１に記載のシステム。
【請求項１９】
湾曲面に射影するように構成された、請求項１に記載のシステム。
【請求項２０】
広角レンズを用いたパノラマ視覚システム内に構成された、請求項１に記載のシステム。
【請求項２１】
請求項１７、請求項１８、請求項１９及び請求項２０に記載の歪みの組み合わせを補正するように構成された、請求項１に記載のシステム。
【請求項２２】
画像の輝度及びクロミナンスのデータによって再サンプリングされる深さ情報を含んだ画像曲面の層化を含むように更に構成されており、前記深さ情報を前記層化プロセスに用いて各ピクセルの可視性又はオクルージョンを決定する、請求項１に記載のシステム。
【請求項２３】
入力ピクセル座標を有する入力画像を出力ピクセル座標を有する出力画像に変換する２次元画像変換を１パスで実施するための表現方法であって、
（ａ）ディスプレイの光学構成を記述するレンズパラメータ、投影角、平面スクリーン及び湾曲スクリーンのディスプレイパネル形状、並びにユーザ指定パラメータを含み、前記変換を定義する形状入力パラメータを得ることと、
（ｂ）前記出力ピクセル座標を前記入力ピクセル座標上にマップするためにグリッドデータ変換を前記形状入力パラメータに基づいて生成することと、
（ｃ）基本的な形状に従って、前記出力ピクセル座標の空間を、各々が関連するグリッドデータセットを有する多数の対応パッチに分割し、出力空間パッチの境界を決定することと、
（ｄ）前記パッチの各々における前記グリッドデータ変換を曲面係数によって表された曲面関数としてパラメータ化することと、
（ｅ）前記曲面係数を記憶することと、
を含む前記方法。
【請求項２４】
メッシュ誤差分析を行って、選択された座標点における前記曲面関数のセットのうち１つの評価と前記グリッドデータ記述からの対応座標点との差が予め設定された許容誤差内にあるかを判断し、該許容誤差内にない場合は解像度を更に高くするために前記パッチメッシュを更に細分することを更に含む、請求項２３に記載の方法。
【請求項２５】
前記画像の前記アクティブ領域の周りにバウンディングボックスを生成し、非アクティブ領域に関連する処理を低減することを更に含む、請求項２３に記載の方法。
【請求項２６】
前記曲面座標が前記入力空間内にあるかを判断し、ない場合は前記出力ピクセルのデータの更なる処理を阻止することを更に含む、請求項２３に記載の方法。
【請求項２７】
前記曲面関数が多項式で表される、請求項２３に記載の方法。
【請求項２８】
前記多項式が３次多項式である、請求項２７に記載の方法。
【請求項２９】
テンソル積双３次スプラインを用いた最小２乗法によって前記多項式をフィットする、請求項２８に記載の方法。
【請求項３０】
乗算演算を減らすために冪の異なる係数を取り除くことによって多項式を計算する、請求項２８に記載の方法。
【請求項３１】
前記パッチ分割を勾配探索によって最適化する、請求項２３に記載の方法。
【請求項３２】
前記パッチ分割をランダム探索によって最適化する、請求項２３に記載の方法。
【請求項３３】
前記パッチ分割をランダム探索及び勾配探索の組み合わせによって最適化し、まず前記ランダム探索が最適な形状を見出し、次に前記勾配探索が前記最適な形状を微調整する、請求項２３に記載の方法。
【請求項３４】
前記ワーピング動作を繰り返すことなく前記解像度の変更を許容するように、決定された前記曲面係数を変更することを更に含む、請求項２３に記載の方法。
【請求項３５】
前記ワーピング動作を繰り返すことなくズーミングを許容するように、決定された前記曲面係数を変更することを更に含む、請求項２３に記載の方法。
【請求項３６】
前記処理の速度を更に上げるために、前記曲面をｘの多項式として扱い、該ｘの多項式の係数をｙの多項式とすることによって曲面フィッティングを行う、請求項２７に記載の方法。
【請求項３７】
個々の長方形サブパッチを別々にフィットする、請求項２３に記載の方法。
【請求項３８】
ハードウェア実装を効率化するために、座標のフィッティングに用いる数の範囲を狭めて、パッチ上に配置される各パッチの座標原点を再定義することを更に含む、請求項２３に記載の方法。
【請求項３９】
ピンクッション型歪み及び樽型レンズ歪みを含む光学非線形性を補正するように適用される、請求項２３に記載の方法。
【請求項４０】
キーストーン歪みを含む射影歪みを補正するように適用される、請求項２３に記載の方法。
【請求項４１】
湾曲面に射影するように適用される、請求項２３に記載の方法。
【請求項４２】
広角レンズを用いたパノラマ視覚システムに適用される、請求項２３に記載の方法。
【請求項４３】
請求項３９、請求項４０、請求項４１及び請求項４２に記載の歪みの組み合わせを補正するように適用される、請求項２３に記載の方法。
【請求項４４】
画像の輝度及びクロミナンスのデータによって再サンプリングされる深さ情報を含んだ画像曲面の層化を行い、前記深さ情報を前記層化プロセスに用いて各ピクセルの可視性又はオクルージョンを決定することを更に含む、請求項２３に記載の方法。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【公表番号】特表２００８−５１２７６７（Ｐ２００８−５１２７６７Ａ）
【公表日】平成２０年４月２４日（２００８．４．２４）
【国際特許分類】
【出願番号】特願２００７−５３１１４４（Ｐ２００７−５３１１４４）
【出願日】平成１６年９月９日（２００４．９．９）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０２９３９４
【国際公開番号】ＷＯ２００６／０３１２１４
【国際公開日】平成１８年３月２３日（２００６．３．２３）
【出願人】（５０４４５７９２４）シリコン オプティックス インコーポレイテッド (9)
【出願人】（３０７０３９７９８）
【Ｆターム（参考）】
【公表日】平成２０年４月２４日（２００８．４．２４）
【国際特許分類】
【出願日】平成１６年９月９日（２００４．９．９）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０２９３９４
【国際公開番号】ＷＯ２００６／０３１２１４
【国際公開日】平成１８年３月２３日（２００６．３．２３）
【出願人】（５０４４５７９２４）シリコン オプティックス インコーポレイテッド (9)
【出願人】（３０７０３９７９８）
【Ｆターム（参考）】
[ Back to top ]