JP4109740B2 - 畳み込み走査ラインレンダリング - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、一般的な画像畳み込み（convolution）技術に関するものであり、特に、走査ラインレンダリング環境におけるデジタル画像あるいはオブジェクトベースのグラフィックの畳み込みを実行する画像畳み込み技術に関するものである。
【０００２】
【従来技術】
現在の画像畳み込みシステムは、半導体メモリフレームバッファを用いて画像畳み込みを実行する。しかしながら、この技術では、特に、画像の高速レンダリングが必要とされる場合に、利用可能なメモリがどのくらい記憶できるかで、畳み込みに適用され得る画像のサイズの制限の可能性がある。また、現在のシステムは、画素ベースの画像データで形成される画像のみに畳み込みが適用されることが許容され、オブジェクトベースの画像データから形成される画像に畳み込むが適用されることは一般的に許容されていない。
【０００３】
図１において、任意の数学的関数による画像の畳み込みは以下のように定義され得る。画像１０は、走査ラインに沿う水平位置がｘで、画像１０の左上角から下に向かう垂直位置がｙである関数Ｉ（ｘ，ｙ）によって示され得る。画素整数座標ｐ及びｑの画素１２は、ｐ≦ｘ≦ｐ＋１、ｑ≦ｑ＋１の範囲での関数Ｉ（ｘ，ｙ）によって返される値を有する。これの実行においては、通常、画像は、例えば、ＲＧＢ値として知られる赤、緑及び青の連続色成分として表現される。このように、通常、関数Ｉ（ｘ，ｙ）は、各色成分、Ｉ_R（ｘ，ｙ）、Ｉ_G（ｘ，ｙ）及びＩ_B（ｘ，ｙ）と、いくつかの関数で示される。所定関数ｆ（ｘ，ｙ）による画像１０の畳み込みは、以下の式によって数学的に定義され、
【０００４】
【数１】

【０００５】
理論上、ｆは有限あるいは無限範囲上で定義され得る。実条件として、畳み込みは、通常、図２に示されるような有限マスク２１（カーネルとしてまた知られている）ｋ_ij、i=-m,…,m、j=-n,…,nによって表現されるｆ（ｘ，ｙ）によって実行され、中央要素あるいはマスク係数がｋ₀₀要素２２であるように表現される。畳み込みは、以下の式によって各画素（ｐ，ｑ）に対し計算され、
【０００６】
【数２】

【０００７】
Ｉの使用は、必要とされる各色成分上での連続独立計算を示している。
【０００８】
図３は、図２の有限マスク２１に従う畳み込み計算を示す。出力画像３２内の各画素３１は、入力画像３４の複数走査ラインを横切る複数の隣接画素３３に依存する。従来のシステムでは、隣接領域画素を利用する困難が全くないので、全画像半導体フレームバッファは、入力画像３４を完全に記憶するように用いられる。
【０００９】
本明細書を通して、特に示されない限り、「メモリ」の対象は、 例えば、ハード（磁気）ディスクあるいは光ディスクメモリよりも、実質的により高速データ転送レート及びより短いアクセス時間を供給する半導体ベースのランダムアクセスメモリのような高速データ転送レート及びアクセス時間が短いメモリが対象とされることである。高速データ転送レートで、アクセス時間が短いメモリの他の例としては、バブルメモリ（bubble memory）及び水銀遅延ラインメモリ（mercury delay line memory）の類を含む。
【００１０】
【発明が解決しようとする課題】
しかしながら、他の画像操作処理において、画像畳み込み用フレームバッファの使用は、多くの問題及び短所を引き起こす。第一に、上述したようなメモリの価格は過去数年来から下降しているけれども、相対的に高価なものである。そのため、コンピュータシステムに典型的に使用されるこのようなメモリの記憶容量は、内部記憶用の低速メモリ（例えば、ハードディスク）を利用するよりも優先して高速メモリ資源を使用する傾向があるオペレーティングシステム及び多くのアプリケーションプログラムのうちの１つの同時実行によって、頻繁に消費される。また、フレームバッファの規格は、画素ベース形式へのグラフィカルオブジェクトのレンダリングによって、より多くのメモリの資源の占有及び上述した問題点を助長する。
【００１１】
それゆえ、従来技術の構成によって結び付けられた１つ以上の問題点を実質的に克服し、あるいは改善することが本発明の目的である。
【００１２】
本発明は上記の問題点に鑑みてなされたものであり、従来のフレームバッファよりむしろ走査ラインバッファ（あるいバンドバッファ）を使用して画像畳み込み操作を実行することを提供し、また、グラフィカルオブジェクトベースの画像を取り扱う場合に格別な効果をもたらす。
【００１３】
【課題を解決するための手段】
本発明の目的に従えば、画像に畳み込み演算子を適用する方法を提供し、その方法は以下のステップからなる。
【００１４】
（ａ）所定行数及び所定列数で構成された有限畳み込みマスクを供給し、
（ｂ）前記画像の一部を記憶するためのバッファ手段を供給し、
（ｃ）前記バッファ手段が記憶する少なくとも前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい前記画像の所定数の走査ラインをレンダリングし、
（ｄ）出力画像の複数の走査ラインを生成するために、前記レンダリングされた複数の走査ラインに前記有限畳み込みマスクを適用し、
（ｅ）前記ステップ（ｃ）及び前記ステップ（ｄ）を繰り返し、該ステップ（ｃ）ではある走査ラインが廃棄されると、次の走査ラインが出力画像のそれぞれの走査ラインに対してレンダリングを行い、
（ｆ）前記画像は、オブジェクトベースのグラフィック環境で表されるとともに、複数のノードから構成される式木表現によって表され、前記式木の１つ以上のノードは、レンダリング数を付加している。
また、他の目的に従えば、画像に畳み込み演算子を適用する方法を提供し、その方法は以下のステップからなる。
（ａ）所定行数及び所定列数で構成された有限畳み込みマスクを供給し、
（ｂ）前記画像の一部を記憶するためのバッファ手段を供給し、
（ｃ）前記バッファ手段が記憶する少なくとも前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい前記画像の所定数の走査ラインをレンダリングし、
（ｄ）出力画像の複数の走査ラインを生成するために、前記レンダリングされた複数の走査ラインに前記有限畳み込みマスクを適用し、
（ｅ）前記ステップ（ｃ）及び前記ステップ（ｄ）を繰り返し、該ステップ（ｃ）ではある走査ラインが廃棄されると、次の走査ラインが出力画像のそれぞれの走査ラインに対してレンダリングを行い、
（ｆ）前記画像は、オブジェクトベースのグラフィック環境で表されるとともに、レンダリング数を付加する命令を含む命令シーケンスによって表される。
【００１５】
好ましくは、前記出力画像の複数の走査ラインを生成するために、前記ステップ（ｃ）及び前記ステップ（ｄ）を繰り返し、前記ステップ（ｃ）では、走査ラインが廃棄され、次の走査ラインが出力画像のそれぞれの走査ラインに対しレンダリングされる。
【００１６】
より好ましくは、前記画像は、オブジェクトベースのグラフィック環境で表される。このような環境の場合、前記画像は、複数のノードから構成される式木表現によって表される。典型的なノードは、演算子あるいは原始関数のどちらかとして特徴づけられる。画像は、選択的に命令シーケンスあるいは階層的データ表現で表されても良い。一般的に、式木表現の１つ以上のノードあるいは命令シーケンスの各シーケンスは、レンダリング数を付加している。典型的なレンダリング数は、ノードあるいは命令に対する注目走査ラインの前のレンダリングされる走査ライン数を表す。
【００１７】
好ましくは、マスクの係数は、任意関数によって決定される。
【００１８】
本発明の他の目的に従えば、出力画像を生成するために入力画像に畳み込み演算子を適用する方法が開示され、その方法は以下のステップからなる。
【００１９】
（ａ）前記入力画像の所定走査ライン数に対応する画素データを記憶するためのバッファ手段を供給し、
（ｂ）前記出力画像の走査ラインを生成するために前記入力画像の画素データに対し、前記所定走査ライン数に実質的に等しい所定行数及び所定列数で構成される有限畳み込みマスクを適用し、
（ｃ）前記出力画像の複数の走査ラインを生成するために、前記ステップ（ａ）及びステップ（ｂ）を繰り返し、前記ステップ（ａ）では、ある走査ラインが廃棄されると、次の走査ラインが前記出力画像の各走査ラインに対し供給され、
（ｄ）前記バッファ手段に供給される前記入力画像は、オブジェクトベースのグラフィック環境における少なくとも１つのグラフィカルオブジェクトからレンダリングされた画像の画素データからなり、かつ前記グラフィック環境において複数のノードから構成され、レンダリング数を付加する１つ以上のノードを含む式木表現によって表される。
【００２０】
本発明の他の目的に従えば、オブジェクトベースのグラフィック環境において少なくとも１つのグラフィカルオブジェクトを表す画像に対し畳み込み演算子を適用する方法が開示され、その方法は以下のステップからなる。
【００２１】
（ａ）前記入力画像の所定走査ライン数に対応する画素データを記憶するためのバッファ手段を供給し、
（ｂ）前記出力画像の走査ラインを生成するために前記入力画像の画素データに対し、前記所定走査ライン数に実質的に等しい所定行数及び所定列数で構成される有限畳み込みマスクを適用し、
（ｃ）前記出力画像の複数の走査ラインを生成するために前記ステップ（ａ）及びステップ（ｂ）を繰り返し、前記ステップ（ａ）では、ある走査ラインが廃棄されると、次の走査ラインが前記出力画像の各走査ラインに対し供給され、
（ｄ）前記バッファ手段に供給される前記入力画像は、オブジェクトベースのグラフィック環境における少なくとも１つのグラフィカルオブジェクトからレンダリングされた画像の画素データからなり、かつ前記画像は、オブジェクトベースのグラフィック環境で表されるとともに、レンダリング数を付加する命令を含む命令シーケンスによって表される。
【００２２】
本発明の他の目的に従えば、画像に畳み込み演算子を適用する装置が開示され、その装置は以下の構成からなる。
【００２３】
所定行数及び所定列数で構成される有限畳み込みマスクを供給する第１手段と、
前記画像の一部を記憶するバッファ手段と、
前記バッファ手段へ、少なくとも前記入力画像の前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい所定ライン数の画像の画素データを供給するとともに、当該供給された画像データを前記バッファ手段に記憶されている前記所定ライン数の画像に対してレンダリングする第２手段と、
出力画像の走査ラインを生成するために前記所定ライン数の画像に対して前記有限畳み込みマスクを適用する第３手段とからなり、
前記入力画像は、オブジェクトベースのグラフィック環境における少なくとも１つのグラフィカルオブジェクトによって表され、かつ複数のノードから構成された式木表現によって表され、前記複数のノードは、演算子及び原始関数を有するグループから選択されるとともに、レンダリング数を付加する１つ以上のノードを含む。
本発明の他の目的に従えば、画像に畳み込み演算子を適用する装置が開示され、その装置は以下の構成からなる。
所定行数及び所定列数で構成される有限畳み込みマスクを供給する第１手段と、
前記画像の一部を記憶するバッファ手段と、
前記バッファ手段へ、少なくとも前記入力画像の前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい所定ライン数の画像の画素データを供給するとともに、当該供給された画像データを前記バッファ手段に記憶されている前記所定ライン数の画像に対してレンダリングする第２手段と、
出力画像の走査ラインを生成するために前記所定ライン数の走査ラインに対して前記有限畳み込みマスクを適用する第３手段とからなり、
前記入力画像は、オブジェクトベースのグラフィック環境における少なくとも１つのグラフィカルオブジェクトによって表され、かつレンダリング数を付加する複数の命令を含む命令シーケンスによって表される。
【００２４】
好ましくは、各目的において、前記バッファ手段は、全入力画像より実質的に小さい入力画像の限定部分を保持するように構成される。
【００２５】
走査ライン単位あるいは複数の走査ラインからなる各バンドの任意のバンド単位の出力画像の合成は、必要あるいは要求されるメモリ記憶容量を削減する効果となる。同様に、後述するが、例えば、畳み込み操作を実行するために必要とされる入力画像の最低走査ライン数である入力画像の一部分だけを記憶することがたいていは好ましい。
【００２６】
以下、図面を参照して本発明の好適な実施形態を詳細に説明する。
【００２７】
図４は、本発明の実施形態に従う処理を入力画像４１の注目バンド４０に施して得られる出力画像４３の１つの注目走査ラインの構成あるいは形式の一例を示す図である。これに従うと、入力画像４１の注目バンド４０及び出力画像４３の注目走査ラインは、それぞれメモリに記憶する必要がある入力画像４１及び出力画像４３の選択部分を表している。入力画像４１がソフトウェア（即ち、グラフィックオブジェクトからを例とするレンダリング）によって生成されようと、あるいは外部資源（例えば、ハードディスクからのピクセルベースのデータ、スキャナ、ＣＤーＲＯＭ、その他）からメモリに読み取られようと、畳み込みを実行するために入力画像４１の一部だけをメモリ４１に記憶する必要がある。「Ｎ」行「Ｍ」列要素を有する畳み込みマスク（Ｎ×Ｍ）に対し、メモリに記憶される入力画像の選択部分はＮ走査ラインから構成される。しかしながら、各Ｎ走査ラインの部分は、本発明実施形態に従う畳み込みを実行するには満足するであろう。
【００２８】
「Ｎ」及び「Ｍ」が、畳み込みマスク２１のサイズに依存する正の整数値をとれる限りは、畳み込みマスクの幾何学中心に中心要素「ｋ₀₀」２２（図２にその例が示される）が存在するように、奇数の正の整数となるように「Ｎ」及び「Ｍ」を選択することが好ましい。
【００２９】
「ｎ」及び「ｍ」が任意の正の整数で表される「２ｎ＋１」行及び「２ｍ＋１」列を有する畳み込みマスクを例とすると、入力画像４１の複数の走査ライン４０（即ち、バンド）は、出力画像４３の１つの走査ラインを形成する処理のためにメモリに記憶されるように要求される。本例では、出力画像４３の走査ライン「ｑ」４２を出力するために、走査ライン「ｑーｎ」から「ｑ＋ｎ」がメモリに記憶されるようように要求される。畳み込みマスクを用いたバンド４０の処理においては、バンド４０の走査ライン「ｑーｎ」がメモリから廃棄され、走査ライン「ｑ＋ｎ＋１」がメモリへ読込まれる。走査ライン「ｑーｎ＋１」から「ｑ＋ｎ＋１」から構成される新しいバンド４４を形成するために、バンド４０は注目走査ラインの前の１つの走査ラインを有している。出力画像４３の走査ライン「ｑ＋１」４５を生成するために、畳み込みマスクを用いて新しいバンド４４が処理される。出力走査ライン（例えば、出力走査ライン「ｑ」４２）が生成される場合、例えば、表示装置あるいは記憶媒体に送信するというように、走査ラインは出力され、所望の出力画像が得られるまですべての出力走査ラインに対し上述の処理が繰り返される。
【００３０】
オブジェクトベースのグラフィック環境において、画像は演算子によって関係づけられた一連のグラフィック原始関数によって記述される。そのような原始関数は、典型的に次のものを含む：矩形及び円のような単純な形状にしろ、あるいは変数的スプライン曲線、テキストやデジタルピクセルベースの画像のような複雑な形状であろうと、を幾何学的に定義された形状を含む。
【００３１】
図５に示すオブジェクトベースのグラフィックの簡単な例では、「ｏｖｅｒ」演算子５２、５４、５７で、背景５３を有して原始関数５１、５５及び５６が所定順序で構成され、上記処理のための 階層的な「式木」表現を与える。 図５に示す式木表現より複雑な式木表現を構成するために、「ｏｖｅｒ」演算子以外の合成演算子が任意に利用される。これらの演算子は、以下の図１に設定される合成演算子を含む、つまり、Ｄｃは予備積算目標値（premultipled destination）あるいは合成色（resultant colour）であり、Ｄｏは予備積算目標値あるいは合成αチャンネル値であり、Ａｃは第１資源Ａの第１部分の予備積算画素色であり、Ａｏは色がＡｃである画素に対応する値であり、Ｂｃは第２資源Ｂの画像の一部の予備積算画素色値であり、Ｂｏは第２資源ＢのＢｃに対応する画素のαチャンネル値である。表１は、特に、異なる演算子を利用して、異なる２つの画像を合成する様々な合成方法を示している。追加演算子も可能である。特別な効果を実現するために、様々な演算子は主に利用される得る。
【００３２】
図６は、表１に示される様々な演算子が、２つの完全に不透明な円Ａ及びＢにおいて利用される場合に生成される様々な最終画像の例を示している。演算子「ｒｏｖｅｒ」、「ｒｉｎ」、「ｒｏｕｔ」及び「ｒａｔｏｐ」は、「r」（逆）演算子に対するオペランドの交換及び対応演算子「ｏｖｅｒ」、「ｉｎ」、「ｏｕｔ」及び「ａｔｏｐ」それぞれの適用と同等であることに注意されるべきである。
【００３３】
【表１】

【００３４】
図５に示す式木よりもより複雑な式木は、２つの合成演算子、単一演算子及び原始関数を含む様々なノードタイプを包含できる。 単一演算子は典型的には、色変換、画像畳み込み、擬似変換及び画像ラッピング（wrapping）を含む。
【００３５】
ここで、図７から図１１に進むと、構成要素７１〜７７を有する図１１に示される画像９０の式木表現７０（図７）が示される。図７の選択表現は、図８の描画命令８０〜８４一式のシーケンスである。本例の図８の選択表現は、ステップ８０及びステップ８１において、「バッファ１」と呼ばれる中間走査ラインバッファ及び図９Ａに示される画像９０の様々なレンダリング位置での「バッファ１」の内容について言及する。ステップ８２、８３及び８４それぞれは、出力走査ラインを生成するために必要とされるバッファである「メインバッファ」内で実行する。
【００３６】
ここで図９Ａ及び図９Ｂを参照し、中間走査ラインバッファ１１０を用いた画像９０の走査ラインレンダリング例を示す。中間（走査ライン）バッファ１１０は、典型的には、レンダリングされた画像の１つの走査ラインと同等の記憶可能容量を有するが、連続する複数の走査ラインのバンドバッファとして任意に実現しても良い。典型的に、画像は少なくとも数百走査ラインを含み、１つのバンドは、一般的に、全画像を占める走査ラインよりも実質的に少ない複数の走査ラインから形成される。従って、中間走査ラインバッファの必要条件、フレームバッファの必要条件よりも実質的には小さい。適当あるいは所望とされるなら、中間走査ラインバッファの記憶容量及び／あるいは位置は、画像操作を最適化にするために動的に再構成されても良い。例えば、図８の命令シーケンスを使用して画像９０を走査ラインレンダリングするには、出力画像の１つの走査ラインを構成するための命令の実行において中間走査ラインバッファ１１０が使用される。
【００３７】
図８の命令シーケンスは繰り返し実行され、それぞれのシーケンスの完全な実行で出力画像の一連の走査ラインが生成される。図９Ａに、図８の命令の実行の繰り返しを通して３つの位置１１１、１１２、１１３における中間バッファ１１０の内容が示される。
【００３８】
図１０に示される中間走査ラインバッファ１１０（「バッファ１」）の時間積分内容は、最初に２つの描画命令８０、８１がフレームバッファ上で実行された場合に示される画像１０４を表している。「バッファ１」１１０の内容は、一般的に表示装置上で表示されず、好ましくは、図８の命令シーケンスのそれぞれの実行の繰り返しによって上書きされる。図９Ａに示す、位置１１１は画像１０４の空白部分１０１に対応し、位置１１２はテキスト文字「Ａ」の先端部分１０２に対応し、位置１１３はテキスト文字「Ａ」の足内の部分１０３に対応する。
【００３９】
図９Ｂは、図９Ａの３つの位置１１１、１１２、１１３のそれぞれに対応する出力画像９０のレンダリングされた３つの走査ライン１１４、１１５、１１６を示している。これらの表現において、前もってレンダリングされたテキスト文字「Ａ」は、図１１に示される黒円に横たわるようにしてレンダリングされ、出力画像の部分画像９１、９２、９３は位置１１４、１１５、１１６それぞれに対応する。
【００４０】
図１２から図１８は、少なくとも１つの畳み込み演算子１２１で構成され、構成要素１２１〜１２９（図１２）を有する式木１２０あるいは構成要素１３１〜１３６（図１３）を有する命令シーケンスによって表される画像の走査ラインレンダリング例を示す。本例での畳み込み演算子は、ぼかしが適用される画像の一部あるいは画像のぼかし（あるいは拡散）を生成する「ぼかし」演算子１２１である。
【００４１】
図１２の式木１２０は、「ぼかし」畳み込み演算子１２１が式木１２０のノードを取り込んでいる以外は、図７の式木７０と実質的に同じである。図１２の式木表現によって表される画像１４０が図１４に示される。本例での「ぼかし」演算子のオペランドは、オペランドとする第１原始関数１２４及び第２原始関数１２５を有する「ｉｎ」演算子１２３から構成される副木１２２である。
【００４２】
副木１２２は、図１４に示される方法によって、副木１２２によって表される画像１４１の一部をぼかす任意関数で畳み込まれ、テキスト文字「Ａ」のエッジはぼかされ、あるいはそのテキスト文字「Ａ」が存在する位置で黒円と融合される。オブジェクトベースのグラフィック環境では、畳み込み演算子は、式木の一部あるいは命令シーケンス（１３０）の１つの命令１３１として含み得り、かつこれに応じて実行され得る。
【００４３】
オブジェクトベースのグラフィック環境において畳み込み演算子を適用するために、２つの中間バッファがメインバッファに追加して用いられる。画像の一部を記憶するバンドバッファ（「バッファ２」）に畳み込みが適用され、「バッファ２」の内容に対する畳み込みの適用によって得られる出力結果を記憶するために第１の中間走査ラインバッファ（「バッファ３」）が適用される。図１５は、「ぼかし演算子」１２１が以降に続く第１中間バッファ（「バッファ３」）の時間積分内容１５０、あるいは命令シーケンスからぼかし畳み込み命令１３１の実行後に等しい状態を示している。
【００４４】
図１６を参照すると、走査ラインレンダリングに適応させた構成要素１６２〜１６９を有する式木表現１６０が示される。レンダリング数１６１は、各末端ノード１６３での各原始関数に対する演算子及び各中間ノード１６２での演算子に付加されていることを示し、また、出力バッファの注目走査ラインの前の走査ラインでレンダリングされなければならない走査ラインがいくつあるかを表している。例えば、注目走査ラインの前に少なくともレンダリングされたｎ走査ラインが存在する場合、畳み込みぼかし１６２操作が先行走査ライン、注目走査ライン及び注目走査ラインの前のｎ走査ライン上で実行され得る前に、「グレーボックス」と記載されている原始関数の注目走査ラインの前のｎ走査ライン及び「テキストＡ」と記載されている原始関数の注目走査ラインの前のｎ走査ラインが「ｉｎ」演算子１６４を用いて中間バッファへレンダリングされる。典型的には、ｎ走査ラインがレンダリングされるまで、「ｉｎ」演算子１６４によって操作される「グレーボックス」及び「テキストＡ」の各走査ラインの注目走査ラインの前のｎ走査ラインをレンダリングするために、走査ライン単位で走査ライン上に副木の各走査ラインがレンダリングされる。副木１６５の総計「２ｎ＋１」の走査ラインは、畳み込み演算子１６２が適用され得る前に中間バッファへのレンダリングを必要とし、総計「２ｎ＋１」の走査ラインは「２ｎ＋１」行を有する畳み込みマスクを適用する前にレンダリングを必要とする最低走査ライン数である。また、走査ラインレンダリングシステムにおいては、このｎ走査ラインは、出力バッファの注目走査ラインより前にレンダリングされなければならない。
【００４５】
図１７は、図１６の式木表現に対応する命令シーケンス１７０表現である。命令シーケンス１７０における各命令１７２〜１７７は、図１６のレンダリング数１６１と同じ命令シーケンス表現となる数１７１によって実行される。
【００４６】
注目走査ラインの前の走査ラインがいくつであるかを決定するレンダリング数は、積算畳み込みの適用の効果を累積するために考慮される。例えば、２ｎ＋１行を有するマスクの第１畳み込みのオペランドが、２ｍ＋１行を有するマスクの第２畳み込み演算子を含む副木である場合、第２畳み込みのオペランドは、注目走査ラインの前のｎ＋ｍ走査ラインレンダリングされなければならない。
【００４７】
図１８Ａから図１８Ｃでは、２ｎ＋１走査ラインを記憶可能とする第１中間バッファ１８０（例えば、バッファ２）、１つの走査ラインを記憶可能な第２中間バッファ１９０（例えば、バッファ３）、及び１つの走査ラインを記憶可能な出力（メイン）バッファ２００が示される。図１８Ａから図１８Ｃは、図１６の式木表現あるいは図１７の命令シーケンス１７０に従う様々なレンダリング位置を示している。
【００４８】
画像の一部１８０は式木表現１６０の副木１６５からレンダリングされ、注目畳み込み走査ライン１９１を生成するために画像の一部１８１に畳み込みぼかし１６２が適用されて、第２バッファ１９０に配置される。第２バッファ１９０の内容は、画像１４０の注目走査ライン２０１を出力するために、式木表現１６０のノードと一緒に処理される。
【００４９】
シーケンスにおける各命令毎、あるいは式木表現のノードの各演算子は、最終画像の各走査ラインに対し必ずしも作用しない。この場合、注目走査ラインだけにむしろ作用する命令の「アクティブリスト」が必要とされる。各走査ラインが生成されると、アクティブリストが除去されない間は、注目走査ラインに作用する命令はアクティブリストに追加される。この方法では、出力画像を生成するために必要とされる時間が、かなり頻繁に削減される。
【００５０】
好ましくは、本方法は、画像の水平走査ライン上で実現され、これに応じて画像がレンダリングされる。しかしながら、この処理は、画像の垂直走査ライン上で実現され得り、本発明の範囲あるいは精神から逸脱しないでそれ相応にレンダリングされ得る。
【００５１】
好ましくは、本発明の実施形態は、コンピュータ上で実行されるソフトウェアとして実現される図４から図１８を参照して説明される処理を、図１９に示すような通常の汎用コンピュータを使用して実行され得る。コンピュータ５００は、コンピュータモジュール５０１、キーボード５０２及びマウス５０３のような入力装置、表示装置５０４を構成する。
【００５２】
コンピュータモジュール５０１は、少なくともプロセッサユニット５０５、半導体ランダムアクセスメモリメモリ（ＲＡＭ）及びリードオンリーメモリ（ＲＯＭ）を典型的に含むメモリユニット５０６、ビデオインタフェース５０７及びキーボードインタフェース５０８を含む入力／出力（Ｉ／Ｏ）インタフェースから構成される。記憶手段５０９は、以下の装置のひとつ以上が含み得り供給される：フロッピーディスク、ハードディスクドライブ、ＣＤーＲＯＭドライブあるいはそれと同様の当業者に知られている不揮発性記憶装置。コンピュータモジュール５０１の構成要素５０５から５０９は、コンピュータ５００の関連技術として知られる通常の操作モードとなる方法及び内部バス５１０を介した典型的な通信を行う。本実施形態のコンピュータ例としては、ＩＢＭ−ＰＣ／ＡＴ互換機、サンスパークステーション（Sun Sparcstations）コンピュータシステムあるいは同様のコンピュータシステムを含んで実行され得る。また、図１９は、上述した走査ラインレンダリング及び畳み込みを有効にするためにメモリ５０６内に供給されるライン／バンドバッファ５１１を示している。バッファ５１１は記憶容量に制限があるので、同様の機能を実行するフレームバッファによる使用とは違って自由にメモリを占有しない。バッファ５１１は、走査ラインの画素データを保持するように配置され、本実施形態では、複数の走査ラインを有するバンドそれぞれを保持する記憶容量を有する。バッファ５１１は、メモリ５０６内の固定領域に配置されても良いし、あるいは選択的に動的に再構成可能な位置および／あるいは記憶容量であっても良く、仮想メモリアドレッシング方法あるいはメモリスワッピングによってアクセス可能にしても良いことに注意されるべきである。例えば、画素ベースの画像あるいは図１６のグラフィック例では、１つの畳み込み処理（ぼかし１６２）だけが、１つのバッファ内で実行されても良い領域を獲得する。しかしながら、１つ以上の畳み込み（例えば、「ｏｖｅｒ」演算子１６６及び１６９間の式木１６０内にぼかし演算子が挿入された場合）を伴うグラフィカルレンダリングにおいて、中間バッファ数は、グラフィカルオブジェクトのレンダリング、それらの個々の畳み込み及び「ｏｖｅｒ」演算子１６９を用いた次の合成を実質的に同時に完了するために用いられても良い。
【００５３】
本発明の実施形態は、１つこコンピュータ５００、あるいはコンピュータネットワーク（例えば、ローカルエリアネットワーク、インターネット）のような複数のコンピュータを含むシステムを代替にして実行しても良い。特に、本実施形態では、フロッピーディスクあるいは光ディスクのような記憶媒体を介して直接的に、あるいはコンピュータネットワークを介して間接的に、１つ以上のプログラムをコンピュータに供給することによって達成されても良い。どちらの場合でも、プログラムは、プロセッサ５０５とメモリ５０６及びバッファ５１１での同時実行によって連続に読み出すための記憶装置５０９を使用して記憶されても良い。また、有限畳み込みマスクは、プログラム、あるいはプログラムから独立して供給及び／あるいは次の使用のために記憶装置５０９に記憶されても良く、これにより、有限畳み込みマスクは、画像データの畳み込みのためにメモリ５０６に一時的に保持されアクセスされても良い。選択的に、有限畳み込みマトリクスがプログラム／アプリケーションの実行で動的に生成されても良い。コンピュータシステム５００の操作モードに従って、このようなプログラムは、バッファ５１１に対し画素ベースの画像データを送受信するのと、同様にグラフィカルオブジェクトから画素ベースの画像データをレンダリングすることが操作可能なプロセッサユニット５０５によって典型的に実行される。後者では、レンダリングは、バッファ５１１内で直接実行されても良い。
【００５４】
上記実施形態は本発明の一実施形態を説明しているだけであるが、本発明の範囲から逸脱しないで本発明の実施形態は当業者によって変形及び／あるいは変更され得る。例えば、ダイレクトアサイクリックグラフ（ＤＡＧ）のような選択的階層的データ表現を用ち得る。
【００５５】
【発明の効果】
以上説明したように、本発明によれば、画像畳み込み操作の実行を、従来のフレームバッファよりむしろ走査ラインバッファ（あるいバンドバッファ）の使用を提供し、また、グラフィカルオブジェクトベースの画像を取り扱う場合に格別な効果をもたらす。
【００５６】
【図面の簡単な説明】
【図１】整数座標（ｐ，ｑ）及び空間座標（ｘ，ｙ）によって示される複数の画素から構成されるデジタル画像を表す図である。
【図２】畳み込みマスクの概要を表す図である。
【図３】フレームバッファを使用した従来の画像の畳み込みを表す図である。
【図４】本発明の実施形態に従う、入力画像のバンドを１つの走査ラインの出力に畳み込んだ走査ラインの概念を表す図である。
【図５】簡易オブジェクトベースのグラフィック画像の式木表現を示す図である。
【図６】２つの部分画像の合成演算子の実行例を示す図である。
【図７】画像に対する式木表現の他の例を示す図である。
【図８】図７の式木表現の命令シーケンス表現を示す図である。
【図９Ａ】図８の命令シーケンスの部分的な算出による複数位置での一時的な走査ラインバッファの内容を示す図である。
【図９Ｂ】図９Ａの複数位置に対応する出力画像の走査ラインを示す図である。
【図１０】図９Ａの一時的な走査ラインバッファの時間積分内容を表す図である。
【図１１】図７の式木あるいは図８の命令シーケンスに従うレンダリングされた画像を表す図である。
【図１２】ぼかし畳み込み演算子による画像の式木表現を示す図である。
【図１３】図１２の式木表現の対応命令シーケンス表現を示す図である。
【図１４】図１２の式木表現あるいは図１３の命令シーケンス表現に従うレンダリングされた出力画像を表す図である。
【図１５】ぼかし（畳み込み）操作が実行された図１３の命令シーケンスあるいは図１２の式木表現の時間積分内容の部分的な算出を表す図である。
【図１６】本発明の実施形態に従う走査ラインレンダリングを使用して、図１４の画像を表す式木を表す図である。
【図１７】図１６の式木表現の対応命令シーケンス表現を示す図である。
【図１８Ａ】本発明の実施形態に従う図１７の命令シーケンスで説明される入力バンドバッファの内容を表す図である。
【図１８Ｂ】本発明の実施形態に従う一時的な走査ラインバッファ及びその内容に続くぼかし（畳み込み）演算子を示す図である。
【図１８Ｃ】図１８Ｂの一時的な走査ラインバッファに対応するレンダリングされた出力画像走査ラインを示す図である。
【図１９】本実施形態で実行されても良いコンピュータシステムの概要を示す図である。

Claims (26)

1. 画像に畳み込み演算子を適用する方法であって、
   （ａ）所定行数及び所定列数で構成された有限畳み込みマスクを供給し、
   （ｂ）前記画像の一部を記憶するためのバッファ手段を供給し、
   （ｃ）前記バッファ手段が記憶する少なくとも前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい前記画像の所定数の走査ラインをレンダリングし、
   （ｄ）出力画像の複数の走査ラインを生成するために、前記レンダリングされた複数の走査ラインに前記有限畳み込みマスクを適用し、
   （ｅ）前記ステップ（ｃ）及び前記ステップ（ｄ）を繰り返し、該ステップ（ｃ）ではある走査ラインが廃棄されると、次の走査ラインが出力画像のそれぞれの走査ラインに対してレンダリングを行い、
   （ｆ）前記画像は、オブジェクトベースのグラフィック環境で表されるとともに、複数のノードから構成される式木表現によって表され、前記式木の１つ以上のノードは、レンダリング数を付加している
   ことを特徴とする方法。
2. 前記ノードは、演算子あるいは原始関数のどちらかとして特徴づけられる
   ことを特徴とする請求項１に記載の方法。
3. 前記レンダリング数は、前記ノードあるいは命令に対する現在の走査ラインよりも前にレンダリングされる走査ライン数を表す
   ことを特徴とする請求項１に記載の方法。
4. 前記有限畳み込みマスクの係数は、任意の関数によって決定される
   ことを特徴とする請求項１に記載の方法。
5. 画像に畳み込み演算子を適用する方法であって、
   （ａ）所定行数及び所定列数で構成された有限畳み込みマスクを供給し、
   （ｂ）前記画像の一部を記憶するためのバッファ手段を供給し、
   （ｃ）前記バッファ手段が記憶する少なくとも前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい前記画像の所定数の走査ラインをレンダリングし、
   （ｄ）出力画像の複数の走査ラインを生成するために、前記レンダリングされた複数の走査ラインに前記有限畳み込みマスクを適用し、
   （ｅ）前記ステップ（ｃ）及び前記ステップ（ｄ）を繰り返し、該ステップ（ｃ）ではある走査ラインが廃棄されると、次の走査ラインが出力画像のそれぞれの走査ラインに対してレンダリングを行い、
   （ｆ）前記画像は、オブジェクトベースのグラフィック環境で表されるとともに、レンダリング数を付加する命令を含む命令シーケンスによって表される
   ことを特徴とする方法。
6. 前記レンダリング数は、前記ノードあるいは命令に対する現在の走査ラインよりも前にレンダリングされる走査ライン数を表す
   ことを特徴とする請求項５に記載の方法。
7. 前記有限畳み込みマスクの係数は、任意の関数によって決定される
   ことを特徴とする請求項５に記載の方法。
8. 出力画像を生成するために、入力画像へ畳み込み演算子を適用する方法であって、
   （ａ）前記入力画像の所定走査ライン数に対応する画素データを記憶するためのバッファ手段を供給し、
   （ｂ）前記出力画像の走査ラインを生成するために前記入力画像の画素データに対し、前記所定走査ライン数に実質的に等しい所定行数及び所定列数で構成される有限畳み込みマスクを適用し、
   （ｃ）前記出力画像の複数の走査ラインを生成するために、前記ステップ（ａ）及びステップ（ｂ）を繰り返し、前記ステップ（ａ）では、ある走査ラインが廃棄されると、次の走査ラインが前記出力画像の各走査ラインに対し供給され、
   （ｄ）前記バッファ手段に供給される前記入力画像は、オブジェクトベースのグラフィック環境における少なくとも１つのグラフィカルオブジェクトからレンダリングされた画像の画素データからなり、かつ前記グラフィック環境において複数のノードから構成され、レンダリング数を付加する１つ以上のノードを含む式木表現によって表される
   ことを特徴とする方法。
9. 前記ノードは、演算子及び原始関数を含むグループから選択される
   ことを特徴とする請求項８に記載の方法。
10. 前記画像は、階層的データ表現によって表される
    ことを特徴とする請求項８に記載の方法。
11. 前記レンダリング数は、前記ノードあるいは命令に対する現在の走査ラインよりも前にレンダリングされる走査ライン数を表す
    ことを特徴とする請求項８に記載の方法。
12. 前記有限畳み込みマスクの係数は、任意の関数によって決定される
    ことを特徴とする請求項８に記載の方法。
13. 出力画像を生成するために、入力画像へ畳み込み演算子を適用する方法であって、
    （ａ）前記入力画像の所定走査ライン数に対応する画素データを記憶するためのバッファ手段を供給し、
    （ｂ）前記出力画像の走査ラインを生成するために前記入力画像の画素データに対し、前記所定走査ライン数に実質的に等しい所定行数及び所定列数で構成される有限畳み込みマスクを適用し、
    （ｃ）前記出力画像の複数の走査ラインを生成するために前記ステップ（ａ）及びステップ（ｂ）を繰り返し、前記ステップ（ａ）では、ある走査ラインが廃棄されると、次の走査ラインが前記出力画像の各走査ラインに対し供給され、
    （ｄ）前記バッファ手段に供給される前記入力画像は、オブジェクトベースのグラフィック環境における少なくとも１つのグラフィカルオブジェクトからレンダリングされた画像の画素データからなり、かつ前記画像は、オブジェクトベースのグラフィック環境で表されるとともに、レンダリング数を付加する命令を含む命令シーケンスによって表される
    ことを特徴とする方法。
14. 前記レンダリング数は、前記ノードあるいは命令に対する現在の走査ラインよりも前にレンダリングされる走査ライン数を表す
    ことを特徴とする請求項１３に記載の方法。
15. 入力画像に畳み込みを適用する装置であって、
    所定行数及び所定列数で構成される有限畳み込みマスクを供給する第１手段と、
    前記画像の一部を記憶するバッファ手段と、
    前記バッファ手段へ、少なくとも前記入力画像の前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい所定ライン数の画像の画素データを供給するとともに、当該供給された画像データを前記バッファ手段に記憶されている前記所定ライン数の画像に対してレンダリングする第２手段と、
    出力画像の走査ラインを生成するために前記所定ライン数の画像に対して前記有限畳み込みマスクを適用する第３手段とからなり、
    前記入力画像は、オブジェクトベースのグラフィック環境における少なくとも１つのグラフィカルオブジェクトによって表され、かつ複数のノードから構成された式木表現によって表され、前記複数のノードは、演算子及び原始関数を有するグループから選択されるとともに、レンダリング数を付加する１つ以上のノードを含む
    ことを特徴とする装置。
16. 前記生成された出力画像の各走査ラインに対し、前記第２手段は前記バッファ手段から予め畳み込まれたある走査ラインを廃棄すると、前記入力画像の次の走査ラインを前記バッファ手段に対し供給する
    ことを特徴とする請求項１５に記載の装置。
17. 前記バッファ手段は、前記入力画像の２つの走査ラインを少なくとも記憶する記憶容量であり、前記第２手段は該バッファ手段へライン単位で該入力画像の該走査ラインを供給する
    ことを特徴とする請求項１６に記載の装置。
18. 前記バッファ手段は前記入力画像の走査ラインのバンドを少なくとも記憶する記憶容量であり、前記第２手段は該バッファ手段へバンド毎に該入力画像の該走査ラインを供給し、前記出力画像の走査ラインを生成するために前記有限畳み込みマスクで畳み込みを行った後、該バッファ手段から該入力画像の該バンドの該走査ラインを廃棄する
    ことを特徴とする請求項１７に記載の装置。
19. 前記レンダリング数は、前記ノードあるいは命令に対する現在の走査ラインよりも前にレンダリングされる走査ライン数を表す
    ことを特徴とする請求項１５に記載の装置。
20. 入力画像に畳み込みを適用する装置であって、
    所定行数及び所定列数で構成される有限畳み込みマスクを供給する第１手段と、
    前記画像の一部を記憶するバッファ手段と、
    前記バッファ手段へ、少なくとも前記入力画像の前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい所定ライン数の画像の画素データを供給するとともに、当該供給された画像データを前記バッファ手段に記憶されている前記所定ライン数の画像に対してレンダリングする第２手段と、
    出力画像の走査ラインを生成するために前記所定ライン数の走査ラインに対して前記有限畳み込みマスクを適用する第３手段とからなり、
    前記入力画像は、オブジェクトベースのグラフィック環境における少なくとも１つのグラフィカルオブジェクトによって表され、かつレンダリング数を付加する複数の命令を含む命令シーケンスによって表される
    ことを特徴とする装置。
21. 前記生成された出力画像の各走査ラインに対し、前記第２手段は前記バッファ手段から予め畳み込まれたある走査ラインを廃棄すると、前記入力画像の次の走査ラインを前記バッファ手段に対し供給する
    ことを特徴とする請求項２０に記載の装置。
22. 前記バッファ手段は前記入力画像の２つの走査ラインを少なくとも記憶する記憶容量であり、前記第２手段は該バッファ手段へライン単位で該入力画像の該走査ラインを供給する
    ことを特徴とする請求項２１に記載の装置。
23. 前記バッファ手段は、前記入力画像の走査ラインのバンドを少なくとも記憶する記憶容量であり、前記第２手段は該バッファ手段へバンド毎に該入力画像の該走査ラインを供給し、前記出力画像の走査ラインを生成するために前記有限畳み込みマスクで畳み込みを行った後、該バッファ手段から該入力画像の該バンドの該走査ラインを廃棄する
    ことを特徴とする請求項２２に記載の装置。
24. 前記レンダリング数は、前記ノードあるいは命令に対する現在の走査ラインよりも前にレンダリングされる走査ライン数を表す
    ことを特徴とする請求項２０に記載の装置。
25. 画像に畳み込み演算子を適用する処理方法であって、
    （ａ）所定行数及び所定列数で構成された有限畳み込みマスクを供給し、
    （ｂ）前記画像の一部を記憶するためのバッファ手段を供給し、
    （ｃ）前記バッファ手段が記憶する少なくとも前記有限畳み込みマスクの前記所定行数 あるいは前記所定列数に実質的に等しい前記画像の所定数の走査ラインをレンダリングし、
    （ｄ）出力画像の複数の走査ラインを生成するために、前記レンダリングされた複数の走査ラインに前記有限畳み込みマスクを適用し、前記ステップ（ｃ）及び前記ステップ（ｄ）を繰り返し、該ステップ（ｃ）ではある走査ラインが廃棄されると、次の走査ラインが出力画像のそれぞれの走査ラインに対してレンダリングを行い、
    前記画像は、オブジェクトベースのグラフィック環境で表されるとともに、複数のノードから構成される式木表現によって表され、前記式木の１つ以上のノードは、レンダリング数を付加するものである処理方法を、コンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
26. 画像に畳み込み演算子を適用する処理方法であって、
    （ａ）所定行数及び所定列数で構成された有限畳み込みマスクを供給し、
    （ｂ）前記画像の一部を記憶するためのバッファ手段を供給し、
    （ｃ）前記バッファ手段が記憶する少なくとも前記有限畳み込みマスクの前記所定行数あるいは前記所定列数に実質的に等しい前記画像の所定数の走査ラインをレンダリングし、
    （ｄ）出力画像の複数の走査ラインを生成するために、前記レンダリングされた複数の走査ラインに前記有限畳み込みマスクを適用し、前記ステップ（ｃ）及び前記ステップ（ｄ）を繰り返し、該ステップ（ｃ）ではある走査ラインが廃棄されると、次の走査ラインが出力画像のそれぞれの走査ラインに対してレンダリングを行い、
    前記画像は、オブジェクトベースのグラフィック環境で表されるとともに、レンダリング数を付加する命令を含む命令シーケンスによって表されるものである処理方法を、コンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。

Images