(57)【特許請求の範囲】
【請求項１】
画像処理のための２次元線形畳み込み方法であって、
ピクセル・アレイの１行に含まれるピクセルの組合せについて部分畳み込み結果を生成するステップと、
前記部分畳み込み結果をルックアップ・テーブルに格納するステップと、
入力ピクセル・ウィンドウ内の１行分のピクセルを前記ピクセル・アレイの前記行にマッピングするステップと、
突合せする行に関連する前記ルックアップ・テーブルの部分畳み込み結果にアクセスするステップと、
前記突合せする行に関連する前記部分結果を合計してピクセルを生成するステップと、
前記生成したピクセルに対してしきい値処理ステップを実行して出力ピクセルを生成するステップと、
を含む畳み込み方法。
【請求項２】
前記突合せする行に関連する前記部分結果を前記合計してピクセルを生成するステップにおいて、前記生成するピクセルがグレイスケールのピクセルである、請求項１に記載の方法。
【請求項３】
前記マッピングするステップが、
前記ピクセル・アレイの前記行に含まれる前記ピクセルの組合せから第１の値を導出するステップと、
前記ピクセルの組合せからの前記第１の値を前記ルックアップ・テーブル内の関連する部分畳み込み結果に相関させるステップと、
入力ピクセル・ウィンドウ内の１行分のピクセルから第２の値を導出するステップと、
前記第２の値に等しい第１の値に関連する前記ルックアップ・テーブルの部分畳み込み結果にアクセスするステップと、
をさらに含む、請求項１または２に記載の方法。
【請求項４】
１行分のピクセルから入力ビットとして受け取るステップと、前記ビットを等価の１０進数に変換するステップと、によって値が導出される、請求項３に記載の方法。
【請求項５】
前記畳み込みが重み関数から導出される、請求項１または２に記載の方法。
【請求項６】
前記部分畳み込み結果を生成するステップにおいて、１つのピクセル行の可能なすべてのパターンに、前記ルックアップ・テーブルに格納するための畳み込みカーネル・マトリックスの対応する行をかける、請求項１または２に記載の方法。
【請求項７】
前記部分結果ルックアップ・テーブルが特定の倍率について事前計算される、請求項１または２に記載の方法。
【請求項８】
前記ルックアップ・テーブルの部分畳み込み結果が変倍動作中に必要に応じて生成される、請求項１または２に記載の方法。
【請求項９】
前記ルックアップ・テーブルが圧縮されてＲＯＭに格納され、ランタイム時に圧縮解除される、請求項１または２に記載の方法。
【請求項１０】
前記部分畳み込み結果が浮動小数点演算で計算され、固定小数点精度に変換されてから、前記ルックアップ・テーブルに格納される、請求項１または２に記載の方法。
【請求項１１】
前記部分畳み込み結果が、プログラム可能メモリ、ＲＡＭ、または磁気記憶装置のうちの１つに格納される、請求項１または２に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理に関し、より具体的には、変倍、平滑化、鮮鋭化などの画像処理技法に適用される２次元線形畳み込みの計算コストの低減に関する。
【０００２】
【従来の技術】
２値（バイナリ）画像を変倍（スケーリング）する場合、入力解像度と出力解像度との食い違いを解決することが必要である。たとえば、ファクシミリ画像処理では、通常は行方向に２０３ドット／インチ（「ｄｐｉ」）と列方向に９８ｄｐｉの標準解像度で元の画像が伝送される。次に画像は、行方向と列方向の両方にたとえば３００ｄｐｉのプリンタ解像度で印刷される。２値画像処理というもう１つの例では、フォントの変倍が必要である。たとえば、３００ｄｐｉで１２ポイントのフォントを２４ポイントのフォントとして使用し、６００ｄｐｉのプリンタで印刷する場合、元の画像は４倍に変倍しなければならない。
【０００３】
画像変倍に関する手法の１つは、R. V. Klassen、R. H. BartelsによるUsing B-splines for Re-Sizing Images（University of Waterloo, Department of Computer Science, Technical Report, 1986）に提案されているＢスプラインなどの区分多項式補間を適用することである。しかし、このような手法は十分なものであることが判明していない。
【０００４】
業界には、KlassenおよびBartelsによる画像変倍の補間技法の実用を妨げる障壁が少なくとも２通り存在する。第１の障壁は、結果の品質に関するものである。補間方式は、条件によっては、画像変倍後に画像ストローク幅が保存されないような量子化エラーを発生する。たとえば、変倍用のすべての区分多項式補間体に埋め込まれる量子化エラー問題は、I. E. AbdouおよびK. Y. WongによるAnalysis of Linear Interpolation Schemes for Bi-Level Image Applications（IBM J. Res. Develop., V. 26, No. 6, pp. 667-680, November, 1982）で報告されている。
【０００５】
この第１の障壁である「量子化エラー問題」に対する新規の解決策は、１９９７年５月６日発行の米国特許第５６２７９５３号（１９９４年８月５日出願の米国特許出願第０８／２８６５６１号）であり、参照により本出願の一部として組み込まれるYenによるBinary Image Scaling by Piecewise Polynomial Interpolationに提示されている。Yenの変倍アルゴリズムの基本的な考え方は、元の画像を３次元データとして扱うことである。画像の水平寸法と垂直寸法はそれぞれ変数ＸおよびＹで表され、画像の強度は変数Ｚで表される。次に３次元データを区分多項式（スプライン）表面に適合（fitting）させる。適合させたこの表面上で再サンプリングを行うと、階調（グレイ・スケール）における変倍画像が生成される。しきい値処理という最終ステップによって、階調が２値結果に量子化される。
【０００６】
補間技法の実用を阻む第２の障壁は、特に高度の補間を伴う大きい倍率の場合に必要な計算の複雑性である。Yenのスプライン・アルゴリズムでは、特に大型フォーマット・プリンタでの印刷の際に大きい倍率が検出された場合に、２値テキストの変倍で高品質の結果が得られると、発明者らはここでは判断していた。しかし、その計算は非常に複雑である。
【０００７】
Binary Image Scaling by Piecewise Polynomial InterpolationにおいてYenは、画像変倍のために補間技法の畳み込みステップを使用している。一般に、ディジタル画像処理では、画像の平滑化、鮮鋭化、変倍のために２次元の線形畳み込みを使用する。（たとえば、Jainによる「Fundamentals of Digital Image Processing」（Prentice Hall, 1989）」を参照されたい。）このタイプの変倍方法の計算の複雑性は、画像サイズ、水平方向の倍率Ｎｈおよび垂直方向の倍率Ｎｖ、水平方向の補間度Ｋｈおよび垂直方向の補間度Ｋｖによって決まる。畳み込み重みはＮｈ・Ｎｖ通りの重みテーブルを必要とし、各重みテーブルはＫｈ・Ｋｖ個の項目を有する。
【０００８】
たとえば、図１は、双３次（４次）Ｂスプライン補間によって水平方向と垂直方向の両方に３倍に画像を変倍する様子を示している。４×４の入力ピクセル・ウィンドウ１４の寸法は、補間の次数によって決まる。
【０００９】
入力ピクセル１０は、隣接ピクセル１２によって囲まれている。水平方向と垂直方向の両方に３倍に変倍すると、各入力ピクセル１０は９個の出力ピクセルからなるアレイ２０に変倍される。出力ピクセルの数（９）は、水平方向の倍率（３）と垂直方向の倍率（３）の積を表している。
【００１０】
各出力ピクセルは関連の重み関数を有する。この重み関数は、補間度と倍率の両方に依存する。Binary Image Scaling by Piecewise Polynomial InterpolationにおいてYenは、重み関数を畳み込みカーネルとして実現している。図２は、双３次一様多項式Ｂスプライン・テンソル積曲面により３倍に変倍するための畳み込みカーネルのテーブルである。このような畳み込みカーネルの導出は、上記のYenの教示によるものである。９個の畳み込みカーネルのそれぞれは、１６個の項目を有するマトリックスである。たとえば、マトリックス２２は、出力ピクセル２４用の重み関数を表す畳み込みカーネルである。
【００１１】
出力ピクセル２４を計算するための畳み込みステップは、入力ピクセル・ウィンドウを表すマトリックス２６と、ウィンドウ内の各ピクセル用の適切な重み関数を表す畳み込みカーネル・マトリックス、すなわち、２２との項目ごとの乗算である。図１では、マトリックス２６は、入力ピクセル・ウィンドウの各陰影付き項目１８を値１で表し、各光項目１６を値０で表している。入力ピクセル・ウィンドウ・マトリックス２６と、重み関数マトリックス２２との乗算によって、結果の出力ピクセルの階調値が得られる。出力ピクセルを表す最終２値結果を達成するために、しきい値処理ステップを使用する。
【００１２】
Yenの畳み込みカーネルは、補間プロセスの複雑性に関連する難解な数学特性を示す。たとえば、畳み込みカーネル・マトリックス２２の値０の項目２８は、入力ピクセル・ウィンドウの一番下の行３０と右端の列３２に含まれるピクセルが出力ピクセル２４を導出するための入力ピクセル重み付けプロセスの一部として使用されないことを示している。これは、局所特性と呼ばれる。
【００１３】
サンプル畳み込みカーネルのテーブル内およびテーブル上で様々な対称性が見られる。このような対称性は、転置、反射、または順列内の反復ベクトルの対称行または対称列を有するカーネルを含む。
【００１４】
図２の各畳み込みカーネル・マトリックスは、支配的な重みを有する１つの項目を有する。比較によれば、カーネルの隅の項目は通常、かなり小さく無意味な重みを有する。したがって、小さい重みを有する入力ピクセルの一部は、出力結果に重大な影響を及ぼさずに畳み込みステップで無視することができる。これは、優越特性と呼ばれる。
【００１５】
極端な手法では、各出力ピクセルは、Ｋｈ×Ｋｖの入力ピクセルのそれぞれと重みテーブルとを項目ごとに掛けることによって処理される。Ｋｈ＊Ｋｖ個の積が加算され、その和に対してしきい値処理ステップが実行される。この手法の総計算コストは、各出力ピクセルごとにＫｈ＊Ｋｖ回の乗算＋Ｋｈ＊Ｋｖ−１回の加算と１回の比較であり、いずれも倍精度浮動小数点演算である。
【００１６】
たとえば、レターサイズの３００ｄｐｉ（ドット／インチ）の画像を４倍に変倍して６００ｄｐｉの出力を得ることは、事実上、双７次（７度、８次）のＢスプライン補間によって両方向に８倍に画像を変倍することと同等である。この変倍動作の合計計算は、およそ６５ギガの浮動小数点演算である。４０ＭＦＬＯＰＳ（１００万浮動小数点演算毎秒）のプロセッサを使用すると、この変倍プロセスは約３０分のＣＰＵ時間を必要とする。
【００１７】
もう１つの極端な手法では、テーブルルックアップ方式を使用して、畳み込みステップを高速化する。各入力ピクセルと重み関数との乗算の結果として可能なすべての積は、予め計算され、テーブルに格納される。しきい値も予め決定される。変倍・プロセスは、入力ピクセルのパターン同士を突き合わせ、テーブルルックアップ・によって出力ピクセルを生成することによって行われる。
【００１８】
テーブルルックアップ方式を使用すると、時間複雑性は出力画像サイズに対して線形になる。空間複雑性は、補間度に対して指数関数的に関連する。出力が２値である場合、ルックアップ・テーブル・サイズは２(Kh・Kv)・（Ｎｈ・Ｎｖ）ビットになる。局所性、対称性、優越性など、Ｂスプラインのいくつかの有利な特性を使用すると、テーブル・サイズを低減することができる。たとえば、双３次Ｂスプライン補間によって３倍に変倍するためのテーブルルックアップ方式では、上記の畳み込み技法を使用してルックアップ・テーブル・サイズを７２ＫＢから約７ＫＢまで低減する。
【００１９】
【発明が解決しようとする課題】
しかし、より高い次数の補間とより大きい倍率を使用する場合、ルックアップ・テーブルのサイズは非実用的なサイズまで大幅に増大する。上記の例では、双７次Ｂスプライン補間によって両方向に８倍に画像を変倍するには、２67バイトが必要になる。
【００２０】
したがって、この発明は、画像処理技法の計算コストを大幅に低減することを目的とする。また、この発明のもう１つの目的は、実用性をもたらすために時間複雑性と空間複雑性のバランスをとることである。
【００２１】
【課題を解決するための手段】
本発明は、２次元線形畳み込みの複雑性を低減するための方法およびシステムを提供する。入力ピクセル・ウィンドウは１組の行として構成される。本発明の好ましい実施例では、入力画像データは２値であり、各行はピクセル当たり１ビットでコーディングされている。しかし、本発明は、２ビット、４ビット、８ビットの階調を含む、ピクセル当たり複数ビットでコーディングされる他のタイプのデータにも適用可能である。この発明は、画像処理のための２次元線形畳み込み方法であって、ピクセル・アレイの１行に含まれるピクセルの組合せについて部分畳み込み結果を生成するステップと、前記部分結果をルックアップ・テーブルに格納するステップと、入力ピクセル・ウィンドウ内の１行のピクセルを前記ピクセル・アレイの前記行にマッピングするステップと、突合せする行に関連する前記ルックアップ・テーブルの部分結果をアクセスするステップとを含む。
【００２２】
【発明の実施の形態】
ピクセル・アレイの１行に含まれる入力ピクセルのすべての可能なパターンが判断され、重み関数を表す畳み込みカーネル・マトリックス内の対応する行によって乗算される。このような部分結果はルックアップ・テーブルに格納される。処理ステップでは、入力ピクセル・ウィンドウの各行が入力ピクセルの可能なパターンにマッピングされる。次に、とりうる突合せ（マッチング）パターンに関連する部分結果がルックアップ・テーブルからアクセスされる。
【００２３】
本発明の好ましい一実施例では、入力ピクセル・ウィンドウの各行はライン・キャッシュに格納される。同様に好ましい他の実施例では、ハッシュ関数がライン・キャッシュからのビットをそれと等価の１０進値に変換する。この１０進値はルックアップ・テーブルへのインデックスとして解釈される。次に、ルックアップ・テーブルのインデックス付き項目（エントリ）に格納された部分結果がアクセスされる。
【００２４】
同様に好ましいさらに他の実施例では、２つのライン・キャッシュ（２重バッファ）は２つの連続する入力ピクセル・ウィンドウからのビットを格納する。それぞれのウィンドウは１組の行として構成されている。第１のバッファの各行が処理された後、第１および第２のバッファの内容が１ピクセル分左にシフトされ、処理を続行する。第２のバッファのすべての内容が第１のバッファにシフトされた後、次の入力ピクセル・ウィンドウが第２のバッファにロードされる。したがって、本発明では、各入力ピクセル・ウィンドウ内のすべてのピクセルを処理するためにメインメモリを１回アクセスするだけでよい。
【００２５】
本発明の好ましい実施例では、部分畳み込み結果は、浮動小数点演算で計算され、固定小数点精度に変換されてから、テーブル項目として格納される。
【００２６】
本発明は、２次元線形畳み込みの複雑性を低減するための方法およびシステムを提供する。畳み込みは、画像平滑化、鮮鋭化、変倍を含む、様々な画像処理技法で適用されている。前述の先行技術の畳み込み方式は、時間複雑性の点で極端なケースである。また、前述の先行技術のテーブルルックアップ方式は、空間複雑性の点で極端なケースである。対照的に、本発明では、先行技術の手法と比較して時間複雑性と空間複雑性のバランスを取りながら、畳み込みとルックアップ・テーブルの両方を使用する。
【００２７】
本発明は、２値および階調を含む、任意のタイプの入力データに適用することができる。本発明を使用すると、可変倍率による変倍の場合ならびに限定されたメモリ空間を有する場合に有利である。このような状況では、各倍率に必要な大型畳み込みテーブルを格納するために使用可能な空間が不十分な可能性がある。
【００２８】
前述の先行技術の畳み込み方式（図１）では、入力ピクセル・ウィンドウ２６内のピクセルが一度に１つずつ項目（エントリ）ごとに対応する畳み込みカーネル・マトリックス２２と乗算される。その後、入力ピクセル・ウィンドウは１ピクセル分その右側にシフトされ、畳み込みプロセスが繰り返される。図２は、双３次の均一多項式Ｂスプライン・テンソル積曲面ｓ（ｕ，ｖ）で３倍に変倍するための畳み込みカーネルを示す。Ｋu・vは、ｓ（ｕ0，ｖ0）でｓ（ｕ，ｖ）をサンプリングするためのカーネルである。
【００２９】
本発明では、入力ピクセル・ウィンドウのサイズはＫｈかけるＫｖである。したがって、１つの入力２値ピクセル・ウィンドウでは２(Kh・Kv)通りのピクセル値の組合せが可能である。各入力ピクセルは、ＮｈかけるＮｖの出力ピクセル・アレイに変倍される。
【００３０】
各出力ピクセルは、対応する入力ピクセルの隣接ピクセルの加重平均として計算される。したがって、各出力ピクセルは、関連する重み関数を有し、この重み関数が補間多項式の次数（度数＋１）の寸法を有するＫｈかけるＫｖの入力ピクセル・ウィンドウ内のピクセルに適用される。補間式の次数が高くなればなるほど、入力２値ピクセル・ウィンドウが大きくなる。
【００３１】
図３は、本発明により２次元線形畳み込みの複雑性を低減するための方法の流れ図である。前処理段階では、入力ピクセル・ウィンドウの行がとりうるすべてのパターンが決定される（１００）。各パターンには、畳み込みカーネル・マトリックスの対応する行が掛けられる（１０５）。この乗算の積は、部分結果としてルックアップ・テーブルに格納される（１１０）。
【００３２】
実行時処理段階では、１つの入力ピクセル・ウィンドウが複数の行に構成される（１１５）。次に、突合せ行に関連する部分結果がルックアップ・テーブルからアクセスされる（１２０）。その入力ピクセル・ウィンドウのすべての部分結果が最終結果として合計され（１２５）、出力が２値であれば、しきい値処理ステップが実行される（１３０）。
【００３３】
図４は、本発明の好ましい一実施例によりライン・キャッシュ３３とハッシュ関数３５とを示す図である。この入力画像の例は、標準の２値画像フォーマットを有する。入力２値ピクセル・ウィンドウ３４は１組の行３６として構成され、各行はピクセル当たり１ビット３８でコーディングされ、ライン・キャッシュ３３の別々の行に格納される。したがって、Ｋｈ×Ｋｖの各入力２値ピクセル・ウィンドウは、Ｋｈビット（ピクセル当たり１ビット）からなるＫｖ行として扱うことができる。図３に示す双７次Ｂスプライン補間の例では、各入力２値ピクセル・ウィンドウがそれぞれ８ビットからなる８行に対応する。
【００３４】
ルックアップ・テーブル４６内に格納された結果を参照するためにインデックス４４を使用する。この例のインデックス付け方式は、２値データをその１０進値に変換するハッシュ関数である。本発明の他の実施例では、このハッシュ関数が様々なデータ型を等価の１０進数に変換する。
【００３５】
これは、入力ピクセル・ウィンドウ全体の畳み込みについてとりうるすべての結果を格納するという先行技術の手法とは区別される。先行技術の手法では、次いでパターン突合せを使用して入力ピクセル・ウィンドウ全体を比較し、所望の画像処理動作のために格納した畳み込み結果を参照する。
【００３６】
したがって、本発明では、部分畳み込み結果を含むルックアップ・テーブルがあらかじめ生成される。しかし、最終畳み込み結果は、画像処理（この例では画像変倍）の実行中に計算される。最終畳み込み結果は、ライン・キャッシュとインデックス付け方式を使用して部分結果を収集することによって計算される。ルックアップ・テーブルは、たとえば、各印刷ジョブごとにまたはページごとに、必要な場合に限り生成される。
【００３７】
図４に示す例では、８ピクセル（ビット）行のすべての可能なパターンに８×８の畳み込みカーネル・マトリックス内の対応する行が掛けられる。各行の部分結果は、実行時に後で使用するためにルックアップ・テーブル４６に格納される。図４は、双７次Ｂスプラインで係数８で変倍するライン・キャッシュおよびマッピング機能を示す。
【００３８】
入力２値ピクセル・ウィンドウの第１の行４０の場合、Ｋｈは８になる。この第１の行は２値数「１０１１００１１」を含む。ハッシュ関数は、入力２値ピクセル・ウィンドウの第１の行から受け取った２値ビットをそれと等価の１０進数「１７９」４２に変換する。この値「１７９」は、第１の行の部分結果ルックアップ・テーブル４６の対応する「１７９」という項目４８に含まれる、対応する予め計算された内容を参照するために使用する。入力２値ピクセル・ウィンドウの第２の行の部分結果は、第２の行の部分結果テーブルの項目「０８２」４９からアクセスすることができる。最後に、すべての部分結果が最終畳み込み結果として合計される。
【００３９】
本発明の好ましい実施例では、部分畳み込み結果が浮動小数点演算で計算され、固定小数点精度に変換されてから、テーブル項目として格納される。たとえば、図４では、予め計算された値が８ビットの固定小数点値として格納される。
【００４０】
８ビットの固定小数点表現を使用することにより、本発明のメモリ要件は、浮動小数点表現を使用する場合に必要なメモリの１／８になる。この変換により精度がわずかに失われるが、食い違いの全体が影響するのはわずかな数の出力ピクセルである。図５は、双７次Ｂスプラインによって４倍に変倍するための浮動小数点と固定小数点の８ビット表現同士の食い違いを示す画像５０である。
【００４１】
図５の中間調（グレイ）のドット５４は、固定小数点精度によって生成されるが、浮動小数点精度では存在しない。黒いドット５２は、浮動小数点精度では検出されるが、固定小数点精度では見あたらない。画像内の１２８０００個の全ピクセルのうち、６６個はグレイであり、３６個は黒である。したがって、食い違っているピクセルの総数は画像内の全ピクセルの０．０８％未満である。浮動小数点表現と固定小数点表現はどちらも近似値である。
【００４２】
本発明の好ましい実施例では、２つのライン・キャッシュ（２重バッファ）を使用して過剰なメモリ・アクセスを解消し、したがって、メモリ・アクセス時間を短縮している。図６は、本発明によりメモリ・アクセスを最適化するための２重バッファを示す図である。出力ピクセルは、入力ピクセル・ウィンドウ内の各周囲ピクセルの合計にその適切な畳み込みカーネルを掛けることによって計算される。この例の各入力２値ピクセル・ウィンドウはそれぞれ８ビットからなる８行に対応する。
【００４３】
たとえば、入力ピクセル６４は入力ピクセル・ウィンドウ５６によって囲まれている。入力ピクセル６６は入力ピクセル６４から１ピクセル分オフセットしている。こうして、入力ピクセル６６を囲む入力ピクセル・ウィンドウ６８も入力ピクセル・ウィンドウ５６から各行で１ピクセル分オフセットしている。
【００４４】
本発明では、２重バッファ７０を使用することによって、この関係を利用する。処理を開始するために、２つの連続する入力ピクセル・ウィンドウ５６、５７がメモリからアクセスされ、第１および第２のバッファ６０、６２にそれぞれ格納される。各入力ピクセル・ウィンドウは１組の行５５として構築される。
【００４５】
この例では、入力ピクセル・ウィンドウ５６の第１の行である行「０」が処理される。入力ピクセル６４が完全に処理されるまで、行「１」〜「７」も処理される。これらの行は、連続して処理するかまたは他の所望の順序で処理することもできる。第１の列である列「０」の入力ピクセルは第１のバッファからシフトアウトされる。第１の列である列「０」からの入力ピクセルは、第２のバッファから第１のバッファの列「７」にシフトされる。第２のバッファ６２の最後の列である列「７」にはスペース・ホルダ７２が満たされる。
【００４６】
第１のバッファ６０は、入力ピクセル６６を処理するための入力ピクセル・ウィンドウ６８を含む。各処理ステップの終了時に入力ウィンドウが１ピクセル分ずつ順次シフトされる間、これらの処理ステップを繰り返す。
【００４７】
第１のバッファ内のすべての入力ピクセルが処理されると、第２のバッファはスペース・ホルダ７２で完全に充填される。次に第２のバッファ６２からの入力ピクセル５７は第１のバッファ６０を充填する。次の入力ピクセル・ウィンドウ５８がメモリからアクセスされ、第２のバッファに格納される。完了まで処理ステップを繰り返す。したがって、個々の入力ピクセルのためにメイン・メモリにアクセスして、入力ピクセル当たり１バイトにアクセスする（８つの入力ピクセル当たり８回のアクセス）のではなく、本発明では、８つの入力ピクセル当たり１回のアクセスと７回のシフトが必要である。
【００４８】
本発明によれば、各出力ピクセル用の計算時間はスプライン補間の次数に線形に関連する。したがって、各出力ピクセルの総計算コストは、１つの階調レベルの画像を得るためには出力ピクセル当たりＫｖ−１回（またはそれ以下）の加算になる。２値出力を獲得するためのしきい値処理には、出力ピクセル当たり１回の比較が必要である。ルックアップ・テーブル４６のサイズは（Ｋｖ・２Kh）・（Ｎｈ・Ｎｖ）バイトである。対照的に、上記の先行技術の畳み込み方式では、Ｋｈ・Ｋｖ回の乗算と、Ｋｈ・Ｋｖ−１回の加算と、１回の比較が必要である。
【００４９】
たとえば、２つのライン・キャッシュと、８ビットの固定小数点精度のハッシュ関数インデックスを使用すると、双７次Ｂスプライン補間によって約５００×３００のピクセル画像を８倍に変倍するには、約４．１ギガの命令が必要になる。対照的に、先行技術の畳み込み方式を使用して同じピクセル画像を変倍するのに必要な時間複雑性は、約６５ギガの浮動小数点演算である。
【００５０】
本発明の空間複雑性は、依然として補間度に対して指数関数的であるが、先行技術の空間複雑性と比較すると大幅に低減される。たとえば、固定小数点の８ビット精度を使用すると、ルックアップ・テーブル・サイズは（Ｋｖ・２Kh）・（Ｎｈ・Ｎｖ）バイトである。双７次Ｂスプライン補間によって８倍に変倍する場合、ルックアップ・テーブル・サイズは２17バイト（１２８Ｋｂ）または１６ＫＢになる。
【００５１】
対照的に、先行技術のルックアップ・テーブル・サイズは２(Kh・Kv)・（Ｎｈ・Ｎｖ）バイトである。双７次Ｂスプライン補間によって８倍に変倍する場合、ルックアップ・テーブル・サイズは２67バイトである。したがって、先行技術のテーブルルックアップ方式に比べ、本発明の空間複雑性の低減は、何桁分にも相当する可能性がある。
【００５２】
本発明の一例では、水平方向と垂直方向の両方に画像を８倍に変倍した。この変倍は、浮動小数点コプロセッサ付きで９９ＭＨｚで動作し、１２４ＭＩＰＳ、４０ＭＦＬＯＰＳのＨＰワークステーション７３５コンピュータ上で実行した。また、補間として双７次テンソル積Ｂスプラインを使用した。２重バッファ・ライン・キャッシュとハッシュ関数インデックスを使用した。固定小数点８ビット精度で部分結果を格納した。５４２×３００ピクセルの画像サイズの場合、ルックアップ・テーブル生成のＣＰＵ時間は１１０ｍｓだった。テーブルに使用したメモリは１２８ＫＢであり、出力生成の全ＣＰＵ時間は６７８０ｍｓだった。
【００５３】
図７のａ〜図７のｄは、８ポイントから２０ポイントまでのサイズのタイムズ（Times）フォントの入力テスト画像を使用するテスト・ケースを示している。各テスト画像は合計で２３１５×１０２３ピクセルを有する。図７のｂ〜図７のｄに示すテスト画像は、いずれもＨＰ９０００／７３０ワークステーションを使用して水平方向と垂直方向の両方に４倍に変倍したものである。図７のａは、サイズが２０ポイントのタイムズ・フォントのテスト画像７４である。図７のｂ〜図７のｃは、先行技術により変倍した、サイズが２０ポイントのタイムズ・フォントのテスト画像である。図７のｂに示すテスト画像７６はピクセル複製を使用して変倍したものである。図７のｃは、前述のYenのBinary Image Scaling by Piecewise Polynomial Interpolationで教示された双線形補間を使用して４倍に変倍した、サイズが２０ポイントのタイムズ・フォントのテスト画像７８である。
【００５４】
図７のｄは、本発明により双７次Ｂスプライン補間を使用して４倍に変倍した、サイズが２０ポイントのタイムズ・フォントのテスト画像８０である。このテスト画像は、補間として双７次テンソル積Ｂスプラインを使用して変倍したものである。ハッシュ関数インデックス付けを備えた２つのライン・キャッシュを適用し、部分結果を固定小数点８ビット精度で格納した。
【００５５】
図７のｄの例では、ルックアップ・テーブル生成のＣＰＵ時間は０．０４秒であり、ルックアップ・テーブルに使用するメモリは３２ＫＢである。図７のｄの例の出力生成のＣＰＵ時間は３７．１秒である。対照的に、図７のｂに示すように、ピクセル複製による画像変倍のＣＰＵ時間は７．４秒である。図７のｃに示すように、双線形補間による画像変倍のＣＰＵ時間は１６．２秒である。
【００５６】
ルックアップ・テーブルを生成するために必要な時間は、全計算時間に比べるとわずかである。双７次補間はYenの双線形補間の２倍よりわずかに長い時間を要する。しかし、本発明によって得られる最終画像品質は、Yenの双線形補間変倍の画像品質より改善され、ピクセル複製によって変倍した画像よりかなり優れている。
【００５７】
ここでは好ましい実施例に関連して本発明を説明するが、当業者であれば、本発明の精神および範囲を逸脱せずにここに記載した適用例の代わりに他の適用例も使用できることが容易に分かるだろう。
【００５８】
本発明の実施例は、インデックス付け方式、２重バッファ、ライン・キャッシュのいずれかまたはすべてを含むことができる。ライン・キャッシュのサイズは畳み込みカーネルに応じて様々である。本発明の好ましい実施例では入力画像データは２値データであり、各行がピクセル当たり１ビットでコーディングされているが、本発明は、２ビット、４ビット、８ビットの階調を含む、ピクセル当たり複数ビットでコーディングされる他のタイプのデータにも適用可能である。
【００５９】
入力ピクセル、重みテーブル、部分結果ルックアップ・テーブルは、デスクトップ・コンピュータ、サーバ、またはプリンタを含む、同じ装置上または異なる装置上に格納することができる。本発明の好ましい実施例では、部分結果は、ＰＲＯＭまたはＥＰＲＯＭなどのプログラム可能メモリに格納される。
【００６０】
あるいは、部分結果はＲＡＭ（ランダム・アクセス・メモリ）内のルックアップ・テーブルに格納される。この実施例では、画像変倍・プロセス中に最終結果が計算される。テーブル項目は、浮動小数点精度で計算することができるが、８ビット、１６ビット、３２ビット精度などの任意のタイプの固定小数点で格納することができる。他の実施例では、入力ピクセル、畳み込みカーネル、部分結果ルックアップ・テーブルは、磁気記憶装置上に格納される。
【００６１】
部分結果ルックアップ・テーブルは、所与の具体的な倍率について事前計算することができる。このようなルックアップ・テーブルは、圧縮してＲＯＭ（読取り専用メモリ）に格納し、ランタイム時に圧縮解除することができる。たとえば、部分ルックアップ・テーブルは、レターサイズからポスタサイズの変倍、すなわち、３×３から４×４の変倍に対応することができる。
【００６２】
さらに、畳み込みステップは、ＡＳＩＣ（特定用途向けＩＣ）ハードウェアまたはパラレル・アーキテクチャで実現することができる。たとえば、パラレル・アーキテクチャの態様は、J. Fisher、P. Faraboschi、およびG. Desoliによる「Custom Fit Processors: Letting Applications Define Architectures」（HP Laboratories Technical Report HPL-96-144, October, 1996）に記載された設計哲学に従うことによって達成することができる。
【００６３】
大きい倍率と高い次数の補間で使用する場合について本発明を前述してきたが、本発明の変倍・アルゴリズムは一般的な適用法も有する。また、本発明は、より小さい倍率とより低い次数の補間にも適用可能である。
当業者であれば、本発明がより高次元の畳み込みにも適用可能であることが容易に分かるだろう。この場合、上記の技法は、たとえば、３次元画像処理に対応する重み関数を使用して実施される。
本発明は、コンピュータ処理ユニットの一部として実現することができる。あるいは、本発明は、プリンタのプロセッサ・ユニットの一部として実現することもできる。したがって、本発明は、上記の請求の範囲のみによって限定されるはずである。この発明は例として次の実施形態を含む。
【００６４】
１．  画像処理のための２次元線形畳み込み方法であって、ピクセル・アレイの１行に含まれるピクセルの組合せに関する部分畳み込み結果を生成するステップと、前記部分結果をルックアップ・テーブルに格納するステップと、入力ピクセル・ウィンドウ内の１行分のピクセルを前記ピクセル・アレイの前記行にマッピングするステップと、突合せ行に関連する前記ルックアップ・テーブル部分結果にアクセスするステップとを含む方法。
２．  前記マッピング・ステップが、前記ピクセル・アレイの前記行に含まれる前記ピクセルの組合せから第１の値を導出するステップと、前記ピクセルの組合せからの前記第１の値を前記ルックアップ・テーブル内のその関連部分結果に相関させるステップと、入力ピクセル・ウィンドウ内の１行分のピクセルから第２の値を導出するステップと、前記第２の値に等しい第１の値に関連する前記ルックアップ・テーブル部分結果にアクセスするステップとをさらに含むことを特徴とする、上記１に記載の方法。
３．  １行分のピクセルから入力ビットとして受け取るステップと、前記ビットを等価の１０進数に変換するステップとによって、値が導出されることを特徴とする、上記２に記載の方法。
４．  第１および第２の入力ピクセル・ウィンドウを第１および第２のバッファにそれぞれ格納するステップと、前記第１のバッファの内容を処理するステップと、各処理ステップの終了時に前記第１および第２にバッファの内容を１ピクセル分シフトするステップと、前記第２のバッファの内容のすべてが前記第１のバッファにシフトされたときに第３の入力ピクセル・ウィンドウを前記第２のバッファに格納するステップとをさらに含むことを特徴とする、上記１に記載の方法。
５．  前記部分結果を合計して階調・ピクセルを生成するステップをさらに含むことを特徴とする、上記１に記載の方法。
【００６５】
６．  前記階調出力ピクセルに対してしきい値処理ステップを実行して出力ピクセルを生成するステップをさらに含むことを特徴とする、上記５に記載の方法。
７．  前記畳み込みが重み関数から導出されることを特徴とする、上記１に記載の方法。
８．  部分結果を生成する前記ステップにおいて、１つのピクセル行の可能なすべてのパターンに、前記ルックアップ・テーブルに格納するための畳み込みカーネル・マトリックスの対応行を掛けることを特徴とする、上記１に記載の方法。
９．  前記部分結果ルックアップ・テーブルが特定の倍率について事前計算されることを特徴とする、上記１に記載の方法。
１０．  前記部分結果ルックアップ・テーブルが変倍動作中に必要に応じて生成されることを特徴とする、上記１に記載の方法。
１１．  前記ルックアップ・テーブルが圧縮してＲＯＭに格納され、ランタイム時に圧縮解除されることを特徴とする、上記１に記載の方法。
１２．  前記部分畳み込み結果が浮動小数点演算で計算され、固定小数点精度に変換されてから、前記ルックアップ・テーブルに格納されることを特徴とする、上記１に記載の方法。
１３．  前記部分結果が、プログラム可能メモリ、ＲＡＭ、または磁気記憶装置のうちの１つに格納されることを特徴とする、上記１に記載の方法。
【００６６】
１４．  画像処理中に２次元線形畳み込みの複雑性を低減するための方法において、ピクセル・アレイの１行に含まれるピクセルの組合せに関する部分畳み込み結果を生成するステップと、前記部分結果をルックアップ・テーブルに格納するステップと、前記ピクセル・アレイの前記行に含まれる前記ピクセルの組合せから第１の値を導出するステップと、前記ピクセルの組合せからの前記第１の値を前記ルックアップ・テーブル内のその関連部分結果に相関させるステップと、第１および第２の入力ピクセル・ウィンドウを第１および第２のバッファにそれぞれ格納するステップと、前記第１のバッファの内容を処理するステップと、各処理ステップの終了時に前記第１および第２にバッファの入力ピクセルを１ピクセル分ずつ順次シフトするステップと、入力ピクセル・ウィンドウ内の１行分のピクセルから第２の値を順次導出するステップと、前記第２の値に一致する第１の値に関連する前記ルックアップ・テーブル部分結果にアクセスするステップと、前記第２のバッファ内の入力ピクセルのすべてが前記第１のバッファにシフトされたときに第３の入力ピクセル・ウィンドウを前記第２のバッファに格納するステップとを含む方法。
【００６７】
１５．  前記部分結果を合計して階調・ピクセルを生成するステップをさらに含むことを特徴とする、上記１４に記載の方法。
１６．  前記階調・ピクセルに対してしきい値処理ステップを実行して出力ピクセルを生成するステップをさらに含むことを特徴とする、上記１５に記載の方法。
１７．  １行分のピクセルから入力ビットとして受け取るステップと、前記ビットを等価の１０進数に変換するステップとによって、値が導出されることを特徴とする、上記１４に記載の方法。
【００６８】
１８．  ２次元線形畳み込みの複雑性を低減するためのシステムにおいて、
ピクセル・アレイの１行に含まれるピクセルの組合せに関する部分畳み込み結果を生成する手段と、前記部分結果を格納するルックアップ・テーブルと、入力ピクセル・ウィンドウ内の１行分のピクセルを前記ピクセル・アレイの前記行にマッピングする手段と、突合せ行に関連する前記ルックアップ・テーブル部分結果にアクセスする手段とを含むシステム。
１９．  前記ピクセル・アレイの前記行に含まれる前記ピクセルの組合せから第１の値を導出する手段と、前記ピクセルの組合せからの前記第１の値を前記ルックアップ・テーブル内のその関連部分結果に相関させる手段と、入力ピクセル・ウィンドウ内の１行分のピクセルから第２の値を導出する手段と、前記第２の値に等しい第１の値に関連する前記ルックアップ・テーブル部分結果にアクセスする手段とをさらに含む、上記１８に記載のシステム。
２０．  第１および第２の入力ピクセル・ウィンドウをそれぞれ格納するための第１および第２のバッファを有する２重バッファと、前記第１のバッファの内容を処理する手段と、各処理ステップの終了時に前記第１および第２にバッファの入力ピクセルを１ピクセル分シフトする手段と、前記第２のバッファの内容のすべてが前記第１のバッファにシフトされたときに第３の入力ピクセル・ウィンドウを前記第２のバッファに格納する手段とをさらに含む、上記１８に記載のシステム。
２１．  前記部分結果を合計して階調・ピクセルを生成するステップをさらに含む、上記１８に記載のシステム。
２２．  前記階調・ピクセルに対してしきい値処理ステップを実行して出力ピクセルを生成する手段をさらに含む、上記２１に記載のシステム。
【００６９】
【発明の効果】
この発明によると画像処理技法の計算コストを低減することができる。また、実用性をもたらすために時間複雑性と空間複雑性のバランスをとることができる。
【図面の簡単な説明】
【図１】先行技術により双３次Ｂスプライン補間によって水平方向と垂直方向の両方に３倍に画像を変倍する様子を示す図。
【図２】双３次の均一多項式Ｂスプライン・テンソル積曲面により３倍に変倍するための畳み込みカーネルのテーブルを示す図。
【図３】２次元線形畳み込みの複雑性を低減するための方法の流れ図。
【図４】本発明によりライン・キャッシュとハッシュ関数を示す図。
【図５】本発明により双７次Ｂスプラインによって４倍に変倍するための浮動小数点と固定小数点の８ビット表現同士の食い違いを示す画像を示す図。
【図６】本発明によりメモリ・アクセスを最適化するための２重バッファを示す図。
【図７】２０ポイントのタイムズ・フォントのテスト画像を示す図。
【符号の説明】
３４          入力ピクセル・ウィンドウ
３５          マッピング関数
４６          部分結果
【図１】
0004091684.tif 000002
【図２】
0004091684.tif 000003
【図３】
0004091684.tif 000004
【図４】
0004091684.tif 000005
【図５】
0004091684.tif 000006
【図６】
0004091684.tif 000007
【図７】
0004091684.tif 000008