JPH10326343A - 画像処理用の２次元畳み込み方法 - Google Patents
画像処理用の２次元畳み込み方法Info
- Publication number
- JPH10326343A JPH10326343A JP10123232A JP12323298A JPH10326343A JP H10326343 A JPH10326343 A JP H10326343A JP 10123232 A JP10123232 A JP 10123232A JP 12323298 A JP12323298 A JP 12323298A JP H10326343 A JPH10326343 A JP H10326343A
- Authority
- JP
- Japan
- Prior art keywords
- pixel
- row
- input
- look
- image
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T5/00—Image enhancement or restoration
- G06T5/20—Image enhancement or restoration using local operators
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Image Processing (AREA)
- Facsimile Image Signal Circuits (AREA)
Abstract
(57)【要約】
【課題】画像処理技法の計算コストを大幅に低減するこ
とを目的とする。 【解決手段】 ピクセル・アレイの１行に含まれる入力
ピクセルのすべての可能なパターンが判断され、重み関
数を表す畳み込みカーネル・マトリックス内の対応する
行によって乗算される。このような部分結果はルックア
ップ・テーブルに格納される。処理ステップでは、入力
ピクセル・ウィンドウの各行が入力ピクセルの可能なパ
ターンにマッピングされる。次に、とりうる突合せ（マ
ッチング）パターンに関連する部分結果がルックアップ
・テーブルからアクセスされる。一実施例では、入力ピ
クセル・ウィンドウの各行はライン・キャッシュに格納
される。他の実施例では、ハッシュ関数がライン・キャ
ッシュからのビットを１０進値に変換する。この１０進
値はルックアップ・テーブルへのインデックスとして使
用される。
とを目的とする。 【解決手段】 ピクセル・アレイの１行に含まれる入力
ピクセルのすべての可能なパターンが判断され、重み関
数を表す畳み込みカーネル・マトリックス内の対応する
行によって乗算される。このような部分結果はルックア
ップ・テーブルに格納される。処理ステップでは、入力
ピクセル・ウィンドウの各行が入力ピクセルの可能なパ
ターンにマッピングされる。次に、とりうる突合せ（マ
ッチング）パターンに関連する部分結果がルックアップ
・テーブルからアクセスされる。一実施例では、入力ピ
クセル・ウィンドウの各行はライン・キャッシュに格納
される。他の実施例では、ハッシュ関数がライン・キャ
ッシュからのビットを１０進値に変換する。この１０進
値はルックアップ・テーブルへのインデックスとして使
用される。
Description
【０００１】
【発明の属する技術分野】本発明は、画像処理に関し、
より具体的には、変倍、平滑化、鮮鋭化などの画像処理
技法に適用される２次元線形畳み込みの計算コストの低
減に関する。
より具体的には、変倍、平滑化、鮮鋭化などの画像処理
技法に適用される２次元線形畳み込みの計算コストの低
減に関する。
【０００２】
【従来の技術】２値（バイナリ）画像を変倍（スケーリ
ング）する場合、入力解像度と出力解像度との食い違い
を解決することが必要である。たとえば、ファクシミリ
画像処理では、通常は行方向に２０３ドット／インチ
（「ｄｐｉ」）と列方向に９８ｄｐｉの標準解像度で元
の画像が伝送される。次に画像は、行方向と列方向の両
方にたとえば３００ｄｐｉのプリンタ解像度で印刷され
る。２値画像処理というもう１つの例では、フォントの
変倍が必要である。たとえば、３００ｄｐｉで１２ポイ
ントのフォントを２４ポイントのフォントとして使用
し、６００ｄｐｉのプリンタで印刷する場合、元の画像
は４倍に変倍しなければならない。
ング）する場合、入力解像度と出力解像度との食い違い
を解決することが必要である。たとえば、ファクシミリ
画像処理では、通常は行方向に２０３ドット／インチ
（「ｄｐｉ」）と列方向に９８ｄｐｉの標準解像度で元
の画像が伝送される。次に画像は、行方向と列方向の両
方にたとえば３００ｄｐｉのプリンタ解像度で印刷され
る。２値画像処理というもう１つの例では、フォントの
変倍が必要である。たとえば、３００ｄｐｉで１２ポイ
ントのフォントを２４ポイントのフォントとして使用
し、６００ｄｐｉのプリンタで印刷する場合、元の画像
は４倍に変倍しなければならない。
【０００３】画像変倍に関する手法の１つは、R. V. Kl
assen、R. H. BartelsによるUsingB-splines for Re-Si
zing Images（University of Waterloo, Department of
Computer Science, Technical Report, 1986）に提案
されているＢスプラインなどの区分多項式補間を適用す
ることである。しかし、このような手法は十分なもので
あることが判明していない。
assen、R. H. BartelsによるUsingB-splines for Re-Si
zing Images（University of Waterloo, Department of
Computer Science, Technical Report, 1986）に提案
されているＢスプラインなどの区分多項式補間を適用す
ることである。しかし、このような手法は十分なもので
あることが判明していない。
【０００４】業界には、KlassenおよびBartelsによる画
像変倍の補間技法の実用を妨げる障壁が少なくとも２通
り存在する。第１の障壁は、結果の品質に関するもので
ある。補間方式は、条件によっては、画像変倍後に画像
ストローク幅が保存されないような量子化エラーを発生
する。たとえば、変倍用のすべての区分多項式補間体に
埋め込まれる量子化エラー問題は、I. E. Abdouおよび
K. Y. WongによるAnalysis of Linear Interpolation S
chemes for Bi-Level Image Applications（IBMJ. Res.
Develop., V. 26, No. 6, pp. 667-680, November, 19
82）で報告されている。
像変倍の補間技法の実用を妨げる障壁が少なくとも２通
り存在する。第１の障壁は、結果の品質に関するもので
ある。補間方式は、条件によっては、画像変倍後に画像
ストローク幅が保存されないような量子化エラーを発生
する。たとえば、変倍用のすべての区分多項式補間体に
埋め込まれる量子化エラー問題は、I. E. Abdouおよび
K. Y. WongによるAnalysis of Linear Interpolation S
chemes for Bi-Level Image Applications（IBMJ. Res.
Develop., V. 26, No. 6, pp. 667-680, November, 19
82）で報告されている。
【０００５】この第１の障壁である「量子化エラー問
題」に対する新規の解決策は、１９９７年５月６日発行
の米国特許第５６２７９５３号（１９９４年８月５日出
願の米国特許出願第０８／２８６５６１号）であり、参
照により本出願の一部として組み込まれるYenによるBin
ary Image Scaling by Piecewise Polynomial Interpol
ationに提示されている。Yenの変倍アルゴリズムの基本
的な考え方は、元の画像を３次元データとして扱うこと
である。画像の水平寸法と垂直寸法はそれぞれ変数Ｘお
よびＹで表され、画像の強度は変数Ｚで表される。次に
３次元データを区分多項式（スプライン）表面に適合
（fitting）させる。適合させたこの表面上で再サンプ
リングを行うと、階調（グレイ・スケール）における変
倍画像が生成される。しきい値処理という最終ステップ
によって、階調が２値結果に量子化される。
題」に対する新規の解決策は、１９９７年５月６日発行
の米国特許第５６２７９５３号（１９９４年８月５日出
願の米国特許出願第０８／２８６５６１号）であり、参
照により本出願の一部として組み込まれるYenによるBin
ary Image Scaling by Piecewise Polynomial Interpol
ationに提示されている。Yenの変倍アルゴリズムの基本
的な考え方は、元の画像を３次元データとして扱うこと
である。画像の水平寸法と垂直寸法はそれぞれ変数Ｘお
よびＹで表され、画像の強度は変数Ｚで表される。次に
３次元データを区分多項式（スプライン）表面に適合
（fitting）させる。適合させたこの表面上で再サンプ
リングを行うと、階調（グレイ・スケール）における変
倍画像が生成される。しきい値処理という最終ステップ
によって、階調が２値結果に量子化される。
【０００６】補間技法の実用を阻む第２の障壁は、特に
高度の補間を伴う大きい倍率の場合に必要な計算の複雑
性である。Yenのスプライン・アルゴリズムでは、特に
大型フォーマット・プリンタでの印刷の際に大きい倍率
が検出された場合に、２値テキストの変倍で高品質の結
果が得られると、発明者らはここでは判断していた。し
かし、その計算は非常に複雑である。
高度の補間を伴う大きい倍率の場合に必要な計算の複雑
性である。Yenのスプライン・アルゴリズムでは、特に
大型フォーマット・プリンタでの印刷の際に大きい倍率
が検出された場合に、２値テキストの変倍で高品質の結
果が得られると、発明者らはここでは判断していた。し
かし、その計算は非常に複雑である。
【０００７】Binary Image Scaling by Piecewise Poly
nomial InterpolationにおいてYenは、画像変倍のため
に補間技法の畳み込みステップを使用している。一般
に、ディジタル画像処理では、画像の平滑化、鮮鋭化、
変倍のために２次元の線形畳み込みを使用する。（たと
えば、Jainによる「Fundamentals of Digital Image Pr
ocessing」（Prentice Hall, 1989）」を参照された
い。）このタイプの変倍方法の計算の複雑性は、画像サ
イズ、水平方向の倍率Ｎｈおよび垂直方向の倍率Ｎｖ、
水平方向の補間度Ｋｈおよび垂直方向の補間度Ｋｖによ
って決まる。畳み込み重みはＮｈ・Ｎｖ通りの重みテー
ブルを必要とし、各重みテーブルはＫｈ・Ｋｖ個の項目
を有する。
nomial InterpolationにおいてYenは、画像変倍のため
に補間技法の畳み込みステップを使用している。一般
に、ディジタル画像処理では、画像の平滑化、鮮鋭化、
変倍のために２次元の線形畳み込みを使用する。（たと
えば、Jainによる「Fundamentals of Digital Image Pr
ocessing」（Prentice Hall, 1989）」を参照された
い。）このタイプの変倍方法の計算の複雑性は、画像サ
イズ、水平方向の倍率Ｎｈおよび垂直方向の倍率Ｎｖ、
水平方向の補間度Ｋｈおよび垂直方向の補間度Ｋｖによ
って決まる。畳み込み重みはＮｈ・Ｎｖ通りの重みテー
ブルを必要とし、各重みテーブルはＫｈ・Ｋｖ個の項目
を有する。
【０００８】たとえば、図１は、双３次（４次）Ｂスプ
ライン補間によって水平方向と垂直方向の両方に３倍に
画像を変倍する様子を示している。４×４の入力ピクセ
ル・ウィンドウ１４の寸法は、補間の次数によって決ま
る。
ライン補間によって水平方向と垂直方向の両方に３倍に
画像を変倍する様子を示している。４×４の入力ピクセ
ル・ウィンドウ１４の寸法は、補間の次数によって決ま
る。
【０００９】入力ピクセル１０は、隣接ピクセル１２に
よって囲まれている。水平方向と垂直方向の両方に３倍
に変倍すると、各入力ピクセル１０は９個の出力ピクセ
ルからなるアレイ２０に変倍される。出力ピクセルの数
（９）は、水平方向の倍率（３）と垂直方向の倍率
（３）の積を表している。
よって囲まれている。水平方向と垂直方向の両方に３倍
に変倍すると、各入力ピクセル１０は９個の出力ピクセ
ルからなるアレイ２０に変倍される。出力ピクセルの数
（９）は、水平方向の倍率（３）と垂直方向の倍率
（３）の積を表している。
【００１０】各出力ピクセルは関連の重み関数を有す
る。この重み関数は、補間度と倍率の両方に依存する。
Binary Image Scaling by Piecewise Polynomial Inter
polationにおいてYenは、重み関数を畳み込みカーネル
として実現している。図２は、双３次一様多項式Ｂスプ
ライン・テンソル積曲面により３倍に変倍するための畳
み込みカーネルのテーブルである。このような畳み込み
カーネルの導出は、上記のYenの教示によるものであ
る。９個の畳み込みカーネルのそれぞれは、１６個の項
目を有するマトリックスである。たとえば、マトリック
ス２２は、出力ピクセル２４用の重み関数を表す畳み込
みカーネルである。
る。この重み関数は、補間度と倍率の両方に依存する。
Binary Image Scaling by Piecewise Polynomial Inter
polationにおいてYenは、重み関数を畳み込みカーネル
として実現している。図２は、双３次一様多項式Ｂスプ
ライン・テンソル積曲面により３倍に変倍するための畳
み込みカーネルのテーブルである。このような畳み込み
カーネルの導出は、上記のYenの教示によるものであ
る。９個の畳み込みカーネルのそれぞれは、１６個の項
目を有するマトリックスである。たとえば、マトリック
ス２２は、出力ピクセル２４用の重み関数を表す畳み込
みカーネルである。
【００１１】出力ピクセル２４を計算するための畳み込
みステップは、入力ピクセル・ウィンドウを表すマトリ
ックス２６と、ウィンドウ内の各ピクセル用の適切な重
み関数を表す畳み込みカーネル・マトリックス、すなわ
ち、２２との項目ごとの乗算である。図１では、マトリ
ックス２６は、入力ピクセル・ウィンドウの各陰影付き
項目１８を値１で表し、各光項目１６を値０で表してい
る。入力ピクセル・ウィンドウ・マトリックス２６と、
重み関数マトリックス２２との乗算によって、結果の出
力ピクセルの階調値が得られる。出力ピクセルを表す最
終２値結果を達成するために、しきい値処理ステップを
使用する。
みステップは、入力ピクセル・ウィンドウを表すマトリ
ックス２６と、ウィンドウ内の各ピクセル用の適切な重
み関数を表す畳み込みカーネル・マトリックス、すなわ
ち、２２との項目ごとの乗算である。図１では、マトリ
ックス２６は、入力ピクセル・ウィンドウの各陰影付き
項目１８を値１で表し、各光項目１６を値０で表してい
る。入力ピクセル・ウィンドウ・マトリックス２６と、
重み関数マトリックス２２との乗算によって、結果の出
力ピクセルの階調値が得られる。出力ピクセルを表す最
終２値結果を達成するために、しきい値処理ステップを
使用する。
【００１２】Yenの畳み込みカーネルは、補間プロセス
の複雑性に関連する難解な数学特性を示す。たとえば、
畳み込みカーネル・マトリックス２２の値０の項目２８
は、入力ピクセル・ウィンドウの一番下の行３０と右端
の列３２に含まれるピクセルが出力ピクセル２４を導出
するための入力ピクセル重み付けプロセスの一部として
使用されないことを示している。これは、局所特性と呼
ばれる。
の複雑性に関連する難解な数学特性を示す。たとえば、
畳み込みカーネル・マトリックス２２の値０の項目２８
は、入力ピクセル・ウィンドウの一番下の行３０と右端
の列３２に含まれるピクセルが出力ピクセル２４を導出
するための入力ピクセル重み付けプロセスの一部として
使用されないことを示している。これは、局所特性と呼
ばれる。
【００１３】サンプル畳み込みカーネルのテーブル内お
よびテーブル上で様々な対称性が見られる。このような
対称性は、転置、反射、または順列内の反復ベクトルの
対称行または対称列を有するカーネルを含む。
よびテーブル上で様々な対称性が見られる。このような
対称性は、転置、反射、または順列内の反復ベクトルの
対称行または対称列を有するカーネルを含む。
【００１４】図２の各畳み込みカーネル・マトリックス
は、支配的な重みを有する１つの項目を有する。比較に
よれば、カーネルの隅の項目は通常、かなり小さく無意
味な重みを有する。したがって、小さい重みを有する入
力ピクセルの一部は、出力結果に重大な影響を及ぼさず
に畳み込みステップで無視することができる。これは、
優越特性と呼ばれる。
は、支配的な重みを有する１つの項目を有する。比較に
よれば、カーネルの隅の項目は通常、かなり小さく無意
味な重みを有する。したがって、小さい重みを有する入
力ピクセルの一部は、出力結果に重大な影響を及ぼさず
に畳み込みステップで無視することができる。これは、
優越特性と呼ばれる。
【００１５】極端な手法では、各出力ピクセルは、Ｋｈ
×Ｋｖの入力ピクセルのそれぞれと重みテーブルとを項
目ごとに掛けることによって処理される。Ｋｈ＊Ｋｖ個
の積が加算され、その和に対してしきい値処理ステップ
が実行される。この手法の総計算コストは、各出力ピク
セルごとにＫｈ＊Ｋｖ回の乗算＋Ｋｈ＊Ｋｖ−１回の加
算と１回の比較であり、いずれも倍精度浮動小数点演算
である。
×Ｋｖの入力ピクセルのそれぞれと重みテーブルとを項
目ごとに掛けることによって処理される。Ｋｈ＊Ｋｖ個
の積が加算され、その和に対してしきい値処理ステップ
が実行される。この手法の総計算コストは、各出力ピク
セルごとにＫｈ＊Ｋｖ回の乗算＋Ｋｈ＊Ｋｖ−１回の加
算と１回の比較であり、いずれも倍精度浮動小数点演算
である。
【００１６】たとえば、レターサイズの３００ｄｐｉ
（ドット／インチ）の画像を４倍に変倍して６００ｄｐ
ｉの出力を得ることは、事実上、双７次（７度、８次）
のＢスプライン補間によって両方向に８倍に画像を変倍
することと同等である。この変倍動作の合計計算は、お
よそ６５ギガの浮動小数点演算である。４０ＭＦＬＯＰ
Ｓ（１００万浮動小数点演算毎秒）のプロセッサを使用
すると、この変倍プロセスは約３０分のＣＰＵ時間を必
要とする。
（ドット／インチ）の画像を４倍に変倍して６００ｄｐ
ｉの出力を得ることは、事実上、双７次（７度、８次）
のＢスプライン補間によって両方向に８倍に画像を変倍
することと同等である。この変倍動作の合計計算は、お
よそ６５ギガの浮動小数点演算である。４０ＭＦＬＯＰ
Ｓ（１００万浮動小数点演算毎秒）のプロセッサを使用
すると、この変倍プロセスは約３０分のＣＰＵ時間を必
要とする。
【００１７】もう１つの極端な手法では、テーブルルッ
クアップ方式を使用して、畳み込みステップを高速化す
る。各入力ピクセルと重み関数との乗算の結果として可
能なすべての積は、予め計算され、テーブルに格納され
る。しきい値も予め決定される。変倍・プロセスは、入
力ピクセルのパターン同士を突き合わせ、テーブルルッ
クアップ・によって出力ピクセルを生成することによっ
て行われる。
クアップ方式を使用して、畳み込みステップを高速化す
る。各入力ピクセルと重み関数との乗算の結果として可
能なすべての積は、予め計算され、テーブルに格納され
る。しきい値も予め決定される。変倍・プロセスは、入
力ピクセルのパターン同士を突き合わせ、テーブルルッ
クアップ・によって出力ピクセルを生成することによっ
て行われる。
【００１８】テーブルルックアップ方式を使用すると、
時間複雑性は出力画像サイズに対して線形になる。空間
複雑性は、補間度に対して指数関数的に関連する。出力
が２値である場合、ルックアップ・テーブル・サイズは
２(Kh・Kv)・（Ｎｈ・Ｎｖ）ビットになる。局所性、対
称性、優越性など、Ｂスプラインのいくつかの有利な特
性を使用すると、テーブル・サイズを低減することがで
きる。たとえば、双３次Ｂスプライン補間によって３倍
に変倍するためのテーブルルックアップ方式では、上記
の畳み込み技法を使用してルックアップ・テーブル・サ
イズを７２ＫＢから約７ＫＢまで低減する。
時間複雑性は出力画像サイズに対して線形になる。空間
複雑性は、補間度に対して指数関数的に関連する。出力
が２値である場合、ルックアップ・テーブル・サイズは
２(Kh・Kv)・（Ｎｈ・Ｎｖ）ビットになる。局所性、対
称性、優越性など、Ｂスプラインのいくつかの有利な特
性を使用すると、テーブル・サイズを低減することがで
きる。たとえば、双３次Ｂスプライン補間によって３倍
に変倍するためのテーブルルックアップ方式では、上記
の畳み込み技法を使用してルックアップ・テーブル・サ
イズを７２ＫＢから約７ＫＢまで低減する。
【００１９】
【発明が解決しようとする課題】しかし、より高い次数
の補間とより大きい倍率を使用する場合、ルックアップ
・テーブルのサイズは非実用的なサイズまで大幅に増大
する。上記の例では、双７次Ｂスプライン補間によって
両方向に８倍に画像を変倍するには、２67バイトが必要
になる。
の補間とより大きい倍率を使用する場合、ルックアップ
・テーブルのサイズは非実用的なサイズまで大幅に増大
する。上記の例では、双７次Ｂスプライン補間によって
両方向に８倍に画像を変倍するには、２67バイトが必要
になる。
【００２０】したがって、この発明は、画像処理技法の
計算コストを大幅に低減することを目的とする。また、
この発明のもう１つの目的は、実用性をもたらすために
時間複雑性と空間複雑性のバランスをとることである。
計算コストを大幅に低減することを目的とする。また、
この発明のもう１つの目的は、実用性をもたらすために
時間複雑性と空間複雑性のバランスをとることである。
【００２１】
【課題を解決するための手段】本発明は、２次元線形畳
み込みの複雑性を低減するための方法およびシステムを
提供する。入力ピクセル・ウィンドウは１組の行として
構成される。本発明の好ましい実施例では、入力画像デ
ータは２値であり、各行はピクセル当たり１ビットでコ
ーディングされている。しかし、本発明は、２ビット、
４ビット、８ビットの階調を含む、ピクセル当たり複数
ビットでコーディングされる他のタイプのデータにも適
用可能である。この発明は、画像処理のための２次元線
形畳み込み方法であって、ピクセル・アレイの１行に含
まれるピクセルの組合せについて部分畳み込み結果を生
成するステップと、前記部分結果をルックアップ・テー
ブルに格納するステップと、入力ピクセル・ウィンドウ
内の１行のピクセルを前記ピクセル・アレイの前記行に
マッピングするステップと、突合せする行に関連する前
記ルックアップ・テーブルの部分結果をアクセスするス
テップとを含む。
み込みの複雑性を低減するための方法およびシステムを
提供する。入力ピクセル・ウィンドウは１組の行として
構成される。本発明の好ましい実施例では、入力画像デ
ータは２値であり、各行はピクセル当たり１ビットでコ
ーディングされている。しかし、本発明は、２ビット、
４ビット、８ビットの階調を含む、ピクセル当たり複数
ビットでコーディングされる他のタイプのデータにも適
用可能である。この発明は、画像処理のための２次元線
形畳み込み方法であって、ピクセル・アレイの１行に含
まれるピクセルの組合せについて部分畳み込み結果を生
成するステップと、前記部分結果をルックアップ・テー
ブルに格納するステップと、入力ピクセル・ウィンドウ
内の１行のピクセルを前記ピクセル・アレイの前記行に
マッピングするステップと、突合せする行に関連する前
記ルックアップ・テーブルの部分結果をアクセスするス
テップとを含む。
【００２２】
【発明の実施の形態】ピクセル・アレイの１行に含まれ
る入力ピクセルのすべての可能なパターンが判断され、
重み関数を表す畳み込みカーネル・マトリックス内の対
応する行によって乗算される。このような部分結果はル
ックアップ・テーブルに格納される。処理ステップで
は、入力ピクセル・ウィンドウの各行が入力ピクセルの
可能なパターンにマッピングされる。次に、とりうる突
合せ（マッチング）パターンに関連する部分結果がルッ
クアップ・テーブルからアクセスされる。
る入力ピクセルのすべての可能なパターンが判断され、
重み関数を表す畳み込みカーネル・マトリックス内の対
応する行によって乗算される。このような部分結果はル
ックアップ・テーブルに格納される。処理ステップで
は、入力ピクセル・ウィンドウの各行が入力ピクセルの
可能なパターンにマッピングされる。次に、とりうる突
合せ（マッチング）パターンに関連する部分結果がルッ
クアップ・テーブルからアクセスされる。
【００２３】本発明の好ましい一実施例では、入力ピク
セル・ウィンドウの各行はライン・キャッシュに格納さ
れる。同様に好ましい他の実施例では、ハッシュ関数が
ライン・キャッシュからのビットをそれと等価の１０進
値に変換する。この１０進値はルックアップ・テーブル
へのインデックスとして解釈される。次に、ルックアッ
プ・テーブルのインデックス付き項目（エントリ）に格
納された部分結果がアクセスされる。
セル・ウィンドウの各行はライン・キャッシュに格納さ
れる。同様に好ましい他の実施例では、ハッシュ関数が
ライン・キャッシュからのビットをそれと等価の１０進
値に変換する。この１０進値はルックアップ・テーブル
へのインデックスとして解釈される。次に、ルックアッ
プ・テーブルのインデックス付き項目（エントリ）に格
納された部分結果がアクセスされる。
【００２４】同様に好ましいさらに他の実施例では、２
つのライン・キャッシュ（２重バッファ）は２つの連続
する入力ピクセル・ウィンドウからのビットを格納す
る。それぞれのウィンドウは１組の行として構成されて
いる。第１のバッファの各行が処理された後、第１およ
び第２のバッファの内容が１ピクセル分左にシフトさ
れ、処理を続行する。第２のバッファのすべての内容が
第１のバッファにシフトされた後、次の入力ピクセル・
ウィンドウが第２のバッファにロードされる。したがっ
て、本発明では、各入力ピクセル・ウィンドウ内のすべ
てのピクセルを処理するためにメインメモリを１回アク
セスするだけでよい。
つのライン・キャッシュ（２重バッファ）は２つの連続
する入力ピクセル・ウィンドウからのビットを格納す
る。それぞれのウィンドウは１組の行として構成されて
いる。第１のバッファの各行が処理された後、第１およ
び第２のバッファの内容が１ピクセル分左にシフトさ
れ、処理を続行する。第２のバッファのすべての内容が
第１のバッファにシフトされた後、次の入力ピクセル・
ウィンドウが第２のバッファにロードされる。したがっ
て、本発明では、各入力ピクセル・ウィンドウ内のすべ
てのピクセルを処理するためにメインメモリを１回アク
セスするだけでよい。
【００２５】本発明の好ましい実施例では、部分畳み込
み結果は、浮動小数点演算で計算され、固定小数点精度
に変換されてから、テーブル項目として格納される。
み結果は、浮動小数点演算で計算され、固定小数点精度
に変換されてから、テーブル項目として格納される。
【００２６】本発明は、２次元線形畳み込みの複雑性を
低減するための方法およびシステムを提供する。畳み込
みは、画像平滑化、鮮鋭化、変倍を含む、様々な画像処
理技法で適用されている。前述の先行技術の畳み込み方
式は、時間複雑性の点で極端なケースである。また、前
述の先行技術のテーブルルックアップ方式は、空間複雑
性の点で極端なケースである。対照的に、本発明では、
先行技術の手法と比較して時間複雑性と空間複雑性のバ
ランスを取りながら、畳み込みとルックアップ・テーブ
ルの両方を使用する。
低減するための方法およびシステムを提供する。畳み込
みは、画像平滑化、鮮鋭化、変倍を含む、様々な画像処
理技法で適用されている。前述の先行技術の畳み込み方
式は、時間複雑性の点で極端なケースである。また、前
述の先行技術のテーブルルックアップ方式は、空間複雑
性の点で極端なケースである。対照的に、本発明では、
先行技術の手法と比較して時間複雑性と空間複雑性のバ
ランスを取りながら、畳み込みとルックアップ・テーブ
ルの両方を使用する。
【００２７】本発明は、２値および階調を含む、任意の
タイプの入力データに適用することができる。本発明を
使用すると、可変倍率による変倍の場合ならびに限定さ
れたメモリ空間を有する場合に有利である。このような
状況では、各倍率に必要な大型畳み込みテーブルを格納
するために使用可能な空間が不十分な可能性がある。
タイプの入力データに適用することができる。本発明を
使用すると、可変倍率による変倍の場合ならびに限定さ
れたメモリ空間を有する場合に有利である。このような
状況では、各倍率に必要な大型畳み込みテーブルを格納
するために使用可能な空間が不十分な可能性がある。
【００２８】前述の先行技術の畳み込み方式（図１）で
は、入力ピクセル・ウィンドウ２６内のピクセルが一度
に１つずつ項目（エントリ）ごとに対応する畳み込みカ
ーネル・マトリックス２２と乗算される。その後、入力
ピクセル・ウィンドウは１ピクセル分その右側にシフト
され、畳み込みプロセスが繰り返される。図２は、双３
次の均一多項式Ｂスプライン・テンソル積曲面ｓ（ｕ，
ｖ）で３倍に変倍するための畳み込みカーネルを示す。
Ｋu・vは、ｓ（ｕ0，ｖ0）でｓ（ｕ，ｖ）をサンプリン
グするためのカーネルである。
は、入力ピクセル・ウィンドウ２６内のピクセルが一度
に１つずつ項目（エントリ）ごとに対応する畳み込みカ
ーネル・マトリックス２２と乗算される。その後、入力
ピクセル・ウィンドウは１ピクセル分その右側にシフト
され、畳み込みプロセスが繰り返される。図２は、双３
次の均一多項式Ｂスプライン・テンソル積曲面ｓ（ｕ，
ｖ）で３倍に変倍するための畳み込みカーネルを示す。
Ｋu・vは、ｓ（ｕ0，ｖ0）でｓ（ｕ，ｖ）をサンプリン
グするためのカーネルである。
【００２９】本発明では、入力ピクセル・ウィンドウの
サイズはＫｈかけるＫｖである。したがって、１つの入
力２値ピクセル・ウィンドウでは２(Kh・Kv)通りのピク
セル値の組合せが可能である。各入力ピクセルは、Ｎｈ
かけるＮｖの出力ピクセル・アレイに変倍される。
サイズはＫｈかけるＫｖである。したがって、１つの入
力２値ピクセル・ウィンドウでは２(Kh・Kv)通りのピク
セル値の組合せが可能である。各入力ピクセルは、Ｎｈ
かけるＮｖの出力ピクセル・アレイに変倍される。
【００３０】各出力ピクセルは、対応する入力ピクセル
の隣接ピクセルの加重平均として計算される。したがっ
て、各出力ピクセルは、関連する重み関数を有し、この
重み関数が補間多項式の次数（度数＋１）の寸法を有す
るＫｈかけるＫｖの入力ピクセル・ウィンドウ内のピク
セルに適用される。補間式の次数が高くなればなるほ
ど、入力２値ピクセル・ウィンドウが大きくなる。
の隣接ピクセルの加重平均として計算される。したがっ
て、各出力ピクセルは、関連する重み関数を有し、この
重み関数が補間多項式の次数（度数＋１）の寸法を有す
るＫｈかけるＫｖの入力ピクセル・ウィンドウ内のピク
セルに適用される。補間式の次数が高くなればなるほ
ど、入力２値ピクセル・ウィンドウが大きくなる。
【００３１】図３は、本発明により２次元線形畳み込み
の複雑性を低減するための方法の流れ図である。前処理
段階では、入力ピクセル・ウィンドウの行がとりうるす
べてのパターンが決定される（１００）。各パターンに
は、畳み込みカーネル・マトリックスの対応する行が掛
けられる（１０５）。この乗算の積は、部分結果として
ルックアップ・テーブルに格納される（１１０）。
の複雑性を低減するための方法の流れ図である。前処理
段階では、入力ピクセル・ウィンドウの行がとりうるす
べてのパターンが決定される（１００）。各パターンに
は、畳み込みカーネル・マトリックスの対応する行が掛
けられる（１０５）。この乗算の積は、部分結果として
ルックアップ・テーブルに格納される（１１０）。
【００３２】実行時処理段階では、１つの入力ピクセル
・ウィンドウが複数の行に構成される（１１５）。次
に、突合せ行に関連する部分結果がルックアップ・テー
ブルからアクセスされる（１２０）。その入力ピクセル
・ウィンドウのすべての部分結果が最終結果として合計
され（１２５）、出力が２値であれば、しきい値処理ス
テップが実行される（１３０）。
・ウィンドウが複数の行に構成される（１１５）。次
に、突合せ行に関連する部分結果がルックアップ・テー
ブルからアクセスされる（１２０）。その入力ピクセル
・ウィンドウのすべての部分結果が最終結果として合計
され（１２５）、出力が２値であれば、しきい値処理ス
テップが実行される（１３０）。
【００３３】図４は、本発明の好ましい一実施例により
ライン・キャッシュ３３とハッシュ関数３５とを示す図
である。この入力画像の例は、標準の２値画像フォーマ
ットを有する。入力２値ピクセル・ウィンドウ３４は１
組の行３６として構成され、各行はピクセル当たり１ビ
ット３８でコーディングされ、ライン・キャッシュ３３
の別々の行に格納される。したがって、Ｋｈ×Ｋｖの各
入力２値ピクセル・ウィンドウは、Ｋｈビット（ピクセ
ル当たり１ビット）からなるＫｖ行として扱うことがで
きる。図３に示す双７次Ｂスプライン補間の例では、各
入力２値ピクセル・ウィンドウがそれぞれ８ビットから
なる８行に対応する。
ライン・キャッシュ３３とハッシュ関数３５とを示す図
である。この入力画像の例は、標準の２値画像フォーマ
ットを有する。入力２値ピクセル・ウィンドウ３４は１
組の行３６として構成され、各行はピクセル当たり１ビ
ット３８でコーディングされ、ライン・キャッシュ３３
の別々の行に格納される。したがって、Ｋｈ×Ｋｖの各
入力２値ピクセル・ウィンドウは、Ｋｈビット（ピクセ
ル当たり１ビット）からなるＫｖ行として扱うことがで
きる。図３に示す双７次Ｂスプライン補間の例では、各
入力２値ピクセル・ウィンドウがそれぞれ８ビットから
なる８行に対応する。
【００３４】ルックアップ・テーブル４６内に格納され
た結果を参照するためにインデックス４４を使用する。
この例のインデックス付け方式は、２値データをその１
０進値に変換するハッシュ関数である。本発明の他の実
施例では、このハッシュ関数が様々なデータ型を等価の
１０進数に変換する。
た結果を参照するためにインデックス４４を使用する。
この例のインデックス付け方式は、２値データをその１
０進値に変換するハッシュ関数である。本発明の他の実
施例では、このハッシュ関数が様々なデータ型を等価の
１０進数に変換する。
【００３５】これは、入力ピクセル・ウィンドウ全体の
畳み込みについてとりうるすべての結果を格納するとい
う先行技術の手法とは区別される。先行技術の手法で
は、次いでパターン突合せを使用して入力ピクセル・ウ
ィンドウ全体を比較し、所望の画像処理動作のために格
納した畳み込み結果を参照する。
畳み込みについてとりうるすべての結果を格納するとい
う先行技術の手法とは区別される。先行技術の手法で
は、次いでパターン突合せを使用して入力ピクセル・ウ
ィンドウ全体を比較し、所望の画像処理動作のために格
納した畳み込み結果を参照する。
【００３６】したがって、本発明では、部分畳み込み結
果を含むルックアップ・テーブルがあらかじめ生成され
る。しかし、最終畳み込み結果は、画像処理（この例で
は画像変倍）の実行中に計算される。最終畳み込み結果
は、ライン・キャッシュとインデックス付け方式を使用
して部分結果を収集することによって計算される。ルッ
クアップ・テーブルは、たとえば、各印刷ジョブごとに
またはページごとに、必要な場合に限り生成される。
果を含むルックアップ・テーブルがあらかじめ生成され
る。しかし、最終畳み込み結果は、画像処理（この例で
は画像変倍）の実行中に計算される。最終畳み込み結果
は、ライン・キャッシュとインデックス付け方式を使用
して部分結果を収集することによって計算される。ルッ
クアップ・テーブルは、たとえば、各印刷ジョブごとに
またはページごとに、必要な場合に限り生成される。
【００３７】図４に示す例では、８ピクセル（ビット）
行のすべての可能なパターンに８×８の畳み込みカーネ
ル・マトリックス内の対応する行が掛けられる。各行の
部分結果は、実行時に後で使用するためにルックアップ
・テーブル４６に格納される。図４は、双７次Ｂスプラ
インで係数８で変倍するライン・キャッシュおよびマッ
ピング機能を示す。
行のすべての可能なパターンに８×８の畳み込みカーネ
ル・マトリックス内の対応する行が掛けられる。各行の
部分結果は、実行時に後で使用するためにルックアップ
・テーブル４６に格納される。図４は、双７次Ｂスプラ
インで係数８で変倍するライン・キャッシュおよびマッ
ピング機能を示す。
【００３８】入力２値ピクセル・ウィンドウの第１の行
４０の場合、Ｋｈは８になる。この第１の行は２値数
「１０１１００１１」を含む。ハッシュ関数は、入力２
値ピクセル・ウィンドウの第１の行から受け取った２値
ビットをそれと等価の１０進数「１７９」４２に変換す
る。この値「１７９」は、第１の行の部分結果ルックア
ップ・テーブル４６の対応する「１７９」という項目４
８に含まれる、対応する予め計算された内容を参照する
ために使用する。入力２値ピクセル・ウィンドウの第２
の行の部分結果は、第２の行の部分結果テーブルの項目
「０８２」４９からアクセスすることができる。最後
に、すべての部分結果が最終畳み込み結果として合計さ
れる。
４０の場合、Ｋｈは８になる。この第１の行は２値数
「１０１１００１１」を含む。ハッシュ関数は、入力２
値ピクセル・ウィンドウの第１の行から受け取った２値
ビットをそれと等価の１０進数「１７９」４２に変換す
る。この値「１７９」は、第１の行の部分結果ルックア
ップ・テーブル４６の対応する「１７９」という項目４
８に含まれる、対応する予め計算された内容を参照する
ために使用する。入力２値ピクセル・ウィンドウの第２
の行の部分結果は、第２の行の部分結果テーブルの項目
「０８２」４９からアクセスすることができる。最後
に、すべての部分結果が最終畳み込み結果として合計さ
れる。
【００３９】本発明の好ましい実施例では、部分畳み込
み結果が浮動小数点演算で計算され、固定小数点精度に
変換されてから、テーブル項目として格納される。たと
えば、図４では、予め計算された値が８ビットの固定小
数点値として格納される。
み結果が浮動小数点演算で計算され、固定小数点精度に
変換されてから、テーブル項目として格納される。たと
えば、図４では、予め計算された値が８ビットの固定小
数点値として格納される。
【００４０】８ビットの固定小数点表現を使用すること
により、本発明のメモリ要件は、浮動小数点表現を使用
する場合に必要なメモリの１／８になる。この変換によ
り精度がわずかに失われるが、食い違いの全体が影響す
るのはわずかな数の出力ピクセルである。図５は、双７
次Ｂスプラインによって４倍に変倍するための浮動小数
点と固定小数点の８ビット表現同士の食い違いを示す画
像５０である。
により、本発明のメモリ要件は、浮動小数点表現を使用
する場合に必要なメモリの１／８になる。この変換によ
り精度がわずかに失われるが、食い違いの全体が影響す
るのはわずかな数の出力ピクセルである。図５は、双７
次Ｂスプラインによって４倍に変倍するための浮動小数
点と固定小数点の８ビット表現同士の食い違いを示す画
像５０である。
【００４１】図５の中間調（グレイ）のドット５４は、
固定小数点精度によって生成されるが、浮動小数点精度
では存在しない。黒いドット５２は、浮動小数点精度で
は検出されるが、固定小数点精度では見あたらない。画
像内の１２８０００個の全ピクセルのうち、６６個はグ
レイであり、３６個は黒である。したがって、食い違っ
ているピクセルの総数は画像内の全ピクセルの０．０８
％未満である。浮動小数点表現と固定小数点表現はどち
らも近似値である。
固定小数点精度によって生成されるが、浮動小数点精度
では存在しない。黒いドット５２は、浮動小数点精度で
は検出されるが、固定小数点精度では見あたらない。画
像内の１２８０００個の全ピクセルのうち、６６個はグ
レイであり、３６個は黒である。したがって、食い違っ
ているピクセルの総数は画像内の全ピクセルの０．０８
％未満である。浮動小数点表現と固定小数点表現はどち
らも近似値である。
【００４２】本発明の好ましい実施例では、２つのライ
ン・キャッシュ（２重バッファ）を使用して過剰なメモ
リ・アクセスを解消し、したがって、メモリ・アクセス
時間を短縮している。図６は、本発明によりメモリ・ア
クセスを最適化するための２重バッファを示す図であ
る。出力ピクセルは、入力ピクセル・ウィンドウ内の各
周囲ピクセルの合計にその適切な畳み込みカーネルを掛
けることによって計算される。この例の各入力２値ピク
セル・ウィンドウはそれぞれ８ビットからなる８行に対
応する。
ン・キャッシュ（２重バッファ）を使用して過剰なメモ
リ・アクセスを解消し、したがって、メモリ・アクセス
時間を短縮している。図６は、本発明によりメモリ・ア
クセスを最適化するための２重バッファを示す図であ
る。出力ピクセルは、入力ピクセル・ウィンドウ内の各
周囲ピクセルの合計にその適切な畳み込みカーネルを掛
けることによって計算される。この例の各入力２値ピク
セル・ウィンドウはそれぞれ８ビットからなる８行に対
応する。
【００４３】たとえば、入力ピクセル６４は入力ピクセ
ル・ウィンドウ５６によって囲まれている。入力ピクセ
ル６６は入力ピクセル６４から１ピクセル分オフセット
している。こうして、入力ピクセル６６を囲む入力ピク
セル・ウィンドウ６８も入力ピクセル・ウィンドウ５６
から各行で１ピクセル分オフセットしている。
ル・ウィンドウ５６によって囲まれている。入力ピクセ
ル６６は入力ピクセル６４から１ピクセル分オフセット
している。こうして、入力ピクセル６６を囲む入力ピク
セル・ウィンドウ６８も入力ピクセル・ウィンドウ５６
から各行で１ピクセル分オフセットしている。
【００４４】本発明では、２重バッファ７０を使用する
ことによって、この関係を利用する。処理を開始するた
めに、２つの連続する入力ピクセル・ウィンドウ５６、
５７がメモリからアクセスされ、第１および第２のバッ
ファ６０、６２にそれぞれ格納される。各入力ピクセル
・ウィンドウは１組の行５５として構築される。
ことによって、この関係を利用する。処理を開始するた
めに、２つの連続する入力ピクセル・ウィンドウ５６、
５７がメモリからアクセスされ、第１および第２のバッ
ファ６０、６２にそれぞれ格納される。各入力ピクセル
・ウィンドウは１組の行５５として構築される。
【００４５】この例では、入力ピクセル・ウィンドウ５
６の第１の行である行「０」が処理される。入力ピクセ
ル６４が完全に処理されるまで、行「１」〜「７」も処
理される。これらの行は、連続して処理するかまたは他
の所望の順序で処理することもできる。第１の列である
列「０」の入力ピクセルは第１のバッファからシフトア
ウトされる。第１の列である列「０」からの入力ピクセ
ルは、第２のバッファから第１のバッファの列「７」に
シフトされる。第２のバッファ６２の最後の列である列
「７」にはスペース・ホルダ７２が満たされる。
６の第１の行である行「０」が処理される。入力ピクセ
ル６４が完全に処理されるまで、行「１」〜「７」も処
理される。これらの行は、連続して処理するかまたは他
の所望の順序で処理することもできる。第１の列である
列「０」の入力ピクセルは第１のバッファからシフトア
ウトされる。第１の列である列「０」からの入力ピクセ
ルは、第２のバッファから第１のバッファの列「７」に
シフトされる。第２のバッファ６２の最後の列である列
「７」にはスペース・ホルダ７２が満たされる。
【００４６】第１のバッファ６０は、入力ピクセル６６
を処理するための入力ピクセル・ウィンドウ６８を含
む。各処理ステップの終了時に入力ウィンドウが１ピク
セル分ずつ順次シフトされる間、これらの処理ステップ
を繰り返す。
を処理するための入力ピクセル・ウィンドウ６８を含
む。各処理ステップの終了時に入力ウィンドウが１ピク
セル分ずつ順次シフトされる間、これらの処理ステップ
を繰り返す。
【００４７】第１のバッファ内のすべての入力ピクセル
が処理されると、第２のバッファはスペース・ホルダ７
２で完全に充填される。次に第２のバッファ６２からの
入力ピクセル５７は第１のバッファ６０を充填する。次
の入力ピクセル・ウィンドウ５８がメモリからアクセス
され、第２のバッファに格納される。完了まで処理ステ
ップを繰り返す。したがって、個々の入力ピクセルのた
めにメイン・メモリにアクセスして、入力ピクセル当た
り１バイトにアクセスする（８つの入力ピクセル当たり
８回のアクセス）のではなく、本発明では、８つの入力
ピクセル当たり１回のアクセスと７回のシフトが必要で
ある。
が処理されると、第２のバッファはスペース・ホルダ７
２で完全に充填される。次に第２のバッファ６２からの
入力ピクセル５７は第１のバッファ６０を充填する。次
の入力ピクセル・ウィンドウ５８がメモリからアクセス
され、第２のバッファに格納される。完了まで処理ステ
ップを繰り返す。したがって、個々の入力ピクセルのた
めにメイン・メモリにアクセスして、入力ピクセル当た
り１バイトにアクセスする（８つの入力ピクセル当たり
８回のアクセス）のではなく、本発明では、８つの入力
ピクセル当たり１回のアクセスと７回のシフトが必要で
ある。
【００４８】本発明によれば、各出力ピクセル用の計算
時間はスプライン補間の次数に線形に関連する。したが
って、各出力ピクセルの総計算コストは、１つの階調レ
ベルの画像を得るためには出力ピクセル当たりＫｖ−１
回（またはそれ以下）の加算になる。２値出力を獲得す
るためのしきい値処理には、出力ピクセル当たり１回の
比較が必要である。ルックアップ・テーブル４６のサイ
ズは（Ｋｖ・２Kh）・（Ｎｈ・Ｎｖ）バイトである。対
照的に、上記の先行技術の畳み込み方式では、Ｋｈ・Ｋ
ｖ回の乗算と、Ｋｈ・Ｋｖ−１回の加算と、１回の比較
が必要である。
時間はスプライン補間の次数に線形に関連する。したが
って、各出力ピクセルの総計算コストは、１つの階調レ
ベルの画像を得るためには出力ピクセル当たりＫｖ−１
回（またはそれ以下）の加算になる。２値出力を獲得す
るためのしきい値処理には、出力ピクセル当たり１回の
比較が必要である。ルックアップ・テーブル４６のサイ
ズは（Ｋｖ・２Kh）・（Ｎｈ・Ｎｖ）バイトである。対
照的に、上記の先行技術の畳み込み方式では、Ｋｈ・Ｋ
ｖ回の乗算と、Ｋｈ・Ｋｖ−１回の加算と、１回の比較
が必要である。
【００４９】たとえば、２つのライン・キャッシュと、
８ビットの固定小数点精度のハッシュ関数インデックス
を使用すると、双７次Ｂスプライン補間によって約５０
０×３００のピクセル画像を８倍に変倍するには、約
４．１ギガの命令が必要になる。対照的に、先行技術の
畳み込み方式を使用して同じピクセル画像を変倍するの
に必要な時間複雑性は、約６５ギガの浮動小数点演算で
ある。
８ビットの固定小数点精度のハッシュ関数インデックス
を使用すると、双７次Ｂスプライン補間によって約５０
０×３００のピクセル画像を８倍に変倍するには、約
４．１ギガの命令が必要になる。対照的に、先行技術の
畳み込み方式を使用して同じピクセル画像を変倍するの
に必要な時間複雑性は、約６５ギガの浮動小数点演算で
ある。
【００５０】本発明の空間複雑性は、依然として補間度
に対して指数関数的であるが、先行技術の空間複雑性と
比較すると大幅に低減される。たとえば、固定小数点の
８ビット精度を使用すると、ルックアップ・テーブル・
サイズは（Ｋｖ・２Kh）・（Ｎｈ・Ｎｖ）バイトであ
る。双７次Ｂスプライン補間によって８倍に変倍する場
合、ルックアップ・テーブル・サイズは２17バイト（１
２８Ｋｂ）または１６ＫＢになる。
に対して指数関数的であるが、先行技術の空間複雑性と
比較すると大幅に低減される。たとえば、固定小数点の
８ビット精度を使用すると、ルックアップ・テーブル・
サイズは（Ｋｖ・２Kh）・（Ｎｈ・Ｎｖ）バイトであ
る。双７次Ｂスプライン補間によって８倍に変倍する場
合、ルックアップ・テーブル・サイズは２17バイト（１
２８Ｋｂ）または１６ＫＢになる。
【００５１】対照的に、先行技術のルックアップ・テー
ブル・サイズは２(Kh・Kv)・（Ｎｈ・Ｎｖ）バイトであ
る。双７次Ｂスプライン補間によって８倍に変倍する場
合、ルックアップ・テーブル・サイズは２67バイトであ
る。したがって、先行技術のテーブルルックアップ方式
に比べ、本発明の空間複雑性の低減は、何桁分にも相当
する可能性がある。
ブル・サイズは２(Kh・Kv)・（Ｎｈ・Ｎｖ）バイトであ
る。双７次Ｂスプライン補間によって８倍に変倍する場
合、ルックアップ・テーブル・サイズは２67バイトであ
る。したがって、先行技術のテーブルルックアップ方式
に比べ、本発明の空間複雑性の低減は、何桁分にも相当
する可能性がある。
【００５２】本発明の一例では、水平方向と垂直方向の
両方に画像を８倍に変倍した。この変倍は、浮動小数点
コプロセッサ付きで９９ＭＨｚで動作し、１２４ＭＩＰ
Ｓ、４０ＭＦＬＯＰＳのＨＰワークステーション７３５
コンピュータ上で実行した。また、補間として双７次テ
ンソル積Ｂスプラインを使用した。２重バッファ・ライ
ン・キャッシュとハッシュ関数インデックスを使用し
た。固定小数点８ビット精度で部分結果を格納した。５
４２×３００ピクセルの画像サイズの場合、ルックアッ
プ・テーブル生成のＣＰＵ時間は１１０ｍｓだった。テ
ーブルに使用したメモリは１２８ＫＢであり、出力生成
の全ＣＰＵ時間は６７８０ｍｓだった。
両方に画像を８倍に変倍した。この変倍は、浮動小数点
コプロセッサ付きで９９ＭＨｚで動作し、１２４ＭＩＰ
Ｓ、４０ＭＦＬＯＰＳのＨＰワークステーション７３５
コンピュータ上で実行した。また、補間として双７次テ
ンソル積Ｂスプラインを使用した。２重バッファ・ライ
ン・キャッシュとハッシュ関数インデックスを使用し
た。固定小数点８ビット精度で部分結果を格納した。５
４２×３００ピクセルの画像サイズの場合、ルックアッ
プ・テーブル生成のＣＰＵ時間は１１０ｍｓだった。テ
ーブルに使用したメモリは１２８ＫＢであり、出力生成
の全ＣＰＵ時間は６７８０ｍｓだった。
【００５３】図７のａ〜図７のｄは、８ポイントから２
０ポイントまでのサイズのタイムズ（Times）フォント
の入力テスト画像を使用するテスト・ケースを示してい
る。各テスト画像は合計で２３１５×１０２３ピクセル
を有する。図７のｂ〜図７のｄに示すテスト画像は、い
ずれもＨＰ９０００／７３０ワークステーションを使用
して水平方向と垂直方向の両方に４倍に変倍したもので
ある。図７のａは、サイズが２０ポイントのタイムズ・
フォントのテスト画像７４である。図７のｂ〜図７のｃ
は、先行技術により変倍した、サイズが２０ポイントの
タイムズ・フォントのテスト画像である。図７のｂに示
すテスト画像７６はピクセル複製を使用して変倍したも
のである。図７のｃは、前述のYenのBinary Image Scal
ing by Piecewise Polynomial Interpolationで教示さ
れた双線形補間を使用して４倍に変倍した、サイズが２
０ポイントのタイムズ・フォントのテスト画像７８であ
る。
０ポイントまでのサイズのタイムズ（Times）フォント
の入力テスト画像を使用するテスト・ケースを示してい
る。各テスト画像は合計で２３１５×１０２３ピクセル
を有する。図７のｂ〜図７のｄに示すテスト画像は、い
ずれもＨＰ９０００／７３０ワークステーションを使用
して水平方向と垂直方向の両方に４倍に変倍したもので
ある。図７のａは、サイズが２０ポイントのタイムズ・
フォントのテスト画像７４である。図７のｂ〜図７のｃ
は、先行技術により変倍した、サイズが２０ポイントの
タイムズ・フォントのテスト画像である。図７のｂに示
すテスト画像７６はピクセル複製を使用して変倍したも
のである。図７のｃは、前述のYenのBinary Image Scal
ing by Piecewise Polynomial Interpolationで教示さ
れた双線形補間を使用して４倍に変倍した、サイズが２
０ポイントのタイムズ・フォントのテスト画像７８であ
る。
【００５４】図７のｄは、本発明により双７次Ｂスプラ
イン補間を使用して４倍に変倍した、サイズが２０ポイ
ントのタイムズ・フォントのテスト画像８０である。こ
のテスト画像は、補間として双７次テンソル積Ｂスプラ
インを使用して変倍したものである。ハッシュ関数イン
デックス付けを備えた２つのライン・キャッシュを適用
し、部分結果を固定小数点８ビット精度で格納した。
イン補間を使用して４倍に変倍した、サイズが２０ポイ
ントのタイムズ・フォントのテスト画像８０である。こ
のテスト画像は、補間として双７次テンソル積Ｂスプラ
インを使用して変倍したものである。ハッシュ関数イン
デックス付けを備えた２つのライン・キャッシュを適用
し、部分結果を固定小数点８ビット精度で格納した。
【００５５】図７のｄの例では、ルックアップ・テーブ
ル生成のＣＰＵ時間は０．０４秒であり、ルックアップ
・テーブルに使用するメモリは３２ＫＢである。図７の
ｄの例の出力生成のＣＰＵ時間は３７．１秒である。対
照的に、図７のｂに示すように、ピクセル複製による画
像変倍のＣＰＵ時間は７．４秒である。図７のｃに示す
ように、双線形補間による画像変倍のＣＰＵ時間は１
６．２秒である。
ル生成のＣＰＵ時間は０．０４秒であり、ルックアップ
・テーブルに使用するメモリは３２ＫＢである。図７の
ｄの例の出力生成のＣＰＵ時間は３７．１秒である。対
照的に、図７のｂに示すように、ピクセル複製による画
像変倍のＣＰＵ時間は７．４秒である。図７のｃに示す
ように、双線形補間による画像変倍のＣＰＵ時間は１
６．２秒である。
【００５６】ルックアップ・テーブルを生成するために
必要な時間は、全計算時間に比べるとわずかである。双
７次補間はYenの双線形補間の２倍よりわずかに長い時
間を要する。しかし、本発明によって得られる最終画像
品質は、Yenの双線形補間変倍の画像品質より改善さ
れ、ピクセル複製によって変倍した画像よりかなり優れ
ている。
必要な時間は、全計算時間に比べるとわずかである。双
７次補間はYenの双線形補間の２倍よりわずかに長い時
間を要する。しかし、本発明によって得られる最終画像
品質は、Yenの双線形補間変倍の画像品質より改善さ
れ、ピクセル複製によって変倍した画像よりかなり優れ
ている。
【００５７】ここでは好ましい実施例に関連して本発明
を説明するが、当業者であれば、本発明の精神および範
囲を逸脱せずにここに記載した適用例の代わりに他の適
用例も使用できることが容易に分かるだろう。
を説明するが、当業者であれば、本発明の精神および範
囲を逸脱せずにここに記載した適用例の代わりに他の適
用例も使用できることが容易に分かるだろう。
【００５８】本発明の実施例は、インデックス付け方
式、２重バッファ、ライン・キャッシュのいずれかまた
はすべてを含むことができる。ライン・キャッシュのサ
イズは畳み込みカーネルに応じて様々である。本発明の
好ましい実施例では入力画像データは２値データであ
り、各行がピクセル当たり１ビットでコーディングされ
ているが、本発明は、２ビット、４ビット、８ビットの
階調を含む、ピクセル当たり複数ビットでコーディング
される他のタイプのデータにも適用可能である。
式、２重バッファ、ライン・キャッシュのいずれかまた
はすべてを含むことができる。ライン・キャッシュのサ
イズは畳み込みカーネルに応じて様々である。本発明の
好ましい実施例では入力画像データは２値データであ
り、各行がピクセル当たり１ビットでコーディングされ
ているが、本発明は、２ビット、４ビット、８ビットの
階調を含む、ピクセル当たり複数ビットでコーディング
される他のタイプのデータにも適用可能である。
【００５９】入力ピクセル、重みテーブル、部分結果ル
ックアップ・テーブルは、デスクトップ・コンピュー
タ、サーバ、またはプリンタを含む、同じ装置上または
異なる装置上に格納することができる。本発明の好まし
い実施例では、部分結果は、ＰＲＯＭまたはＥＰＲＯＭ
などのプログラム可能メモリに格納される。
ックアップ・テーブルは、デスクトップ・コンピュー
タ、サーバ、またはプリンタを含む、同じ装置上または
異なる装置上に格納することができる。本発明の好まし
い実施例では、部分結果は、ＰＲＯＭまたはＥＰＲＯＭ
などのプログラム可能メモリに格納される。
【００６０】あるいは、部分結果はＲＡＭ（ランダム・
アクセス・メモリ）内のルックアップ・テーブルに格納
される。この実施例では、画像変倍・プロセス中に最終
結果が計算される。テーブル項目は、浮動小数点精度で
計算することができるが、８ビット、１６ビット、３２
ビット精度などの任意のタイプの固定小数点で格納する
ことができる。他の実施例では、入力ピクセル、畳み込
みカーネル、部分結果ルックアップ・テーブルは、磁気
記憶装置上に格納される。
アクセス・メモリ）内のルックアップ・テーブルに格納
される。この実施例では、画像変倍・プロセス中に最終
結果が計算される。テーブル項目は、浮動小数点精度で
計算することができるが、８ビット、１６ビット、３２
ビット精度などの任意のタイプの固定小数点で格納する
ことができる。他の実施例では、入力ピクセル、畳み込
みカーネル、部分結果ルックアップ・テーブルは、磁気
記憶装置上に格納される。
【００６１】部分結果ルックアップ・テーブルは、所与
の具体的な倍率について事前計算することができる。こ
のようなルックアップ・テーブルは、圧縮してＲＯＭ
（読取り専用メモリ）に格納し、ランタイム時に圧縮解
除することができる。たとえば、部分ルックアップ・テ
ーブルは、レターサイズからポスタサイズの変倍、すな
わち、３×３から４×４の変倍に対応することができ
る。
の具体的な倍率について事前計算することができる。こ
のようなルックアップ・テーブルは、圧縮してＲＯＭ
（読取り専用メモリ）に格納し、ランタイム時に圧縮解
除することができる。たとえば、部分ルックアップ・テ
ーブルは、レターサイズからポスタサイズの変倍、すな
わち、３×３から４×４の変倍に対応することができ
る。
【００６２】さらに、畳み込みステップは、ＡＳＩＣ
（特定用途向けＩＣ）ハードウェアまたはパラレル・ア
ーキテクチャで実現することができる。たとえば、パラ
レル・アーキテクチャの態様は、J. Fisher、P. Farabo
schi、およびG. Desoliによる「Custom Fit Processor
s: Letting Applications Define Architectures」（HP
Laboratories Technical Report HPL-96-144, October,
1996）に記載された設計哲学に従うことによって達成
することができる。
（特定用途向けＩＣ）ハードウェアまたはパラレル・ア
ーキテクチャで実現することができる。たとえば、パラ
レル・アーキテクチャの態様は、J. Fisher、P. Farabo
schi、およびG. Desoliによる「Custom Fit Processor
s: Letting Applications Define Architectures」（HP
Laboratories Technical Report HPL-96-144, October,
1996）に記載された設計哲学に従うことによって達成
することができる。
【００６３】大きい倍率と高い次数の補間で使用する場
合について本発明を前述してきたが、本発明の変倍・ア
ルゴリズムは一般的な適用法も有する。また、本発明
は、より小さい倍率とより低い次数の補間にも適用可能
である。当業者であれば、本発明がより高次元の畳み込
みにも適用可能であることが容易に分かるだろう。この
場合、上記の技法は、たとえば、３次元画像処理に対応
する重み関数を使用して実施される。本発明は、コンピ
ュータ処理ユニットの一部として実現することができ
る。あるいは、本発明は、プリンタのプロセッサ・ユニ
ットの一部として実現することもできる。したがって、
本発明は、上記の請求の範囲のみによって限定されるは
ずである。この発明は例として次の実施形態を含む。
合について本発明を前述してきたが、本発明の変倍・ア
ルゴリズムは一般的な適用法も有する。また、本発明
は、より小さい倍率とより低い次数の補間にも適用可能
である。当業者であれば、本発明がより高次元の畳み込
みにも適用可能であることが容易に分かるだろう。この
場合、上記の技法は、たとえば、３次元画像処理に対応
する重み関数を使用して実施される。本発明は、コンピ
ュータ処理ユニットの一部として実現することができ
る。あるいは、本発明は、プリンタのプロセッサ・ユニ
ットの一部として実現することもできる。したがって、
本発明は、上記の請求の範囲のみによって限定されるは
ずである。この発明は例として次の実施形態を含む。
【００６４】１． 画像処理のための２次元線形畳み込
み方法であって、ピクセル・アレイの１行に含まれるピ
クセルの組合せに関する部分畳み込み結果を生成するス
テップと、前記部分結果をルックアップ・テーブルに格
納するステップと、入力ピクセル・ウィンドウ内の１行
分のピクセルを前記ピクセル・アレイの前記行にマッピ
ングするステップと、突合せ行に関連する前記ルックア
ップ・テーブル部分結果にアクセスするステップとを含
む方法。 ２． 前記マッピング・ステップが、前記ピクセル・ア
レイの前記行に含まれる前記ピクセルの組合せから第１
の値を導出するステップと、前記ピクセルの組合せから
の前記第１の値を前記ルックアップ・テーブル内のその
関連部分結果に相関させるステップと、入力ピクセル・
ウィンドウ内の１行分のピクセルから第２の値を導出す
るステップと、前記第２の値に等しい第１の値に関連す
る前記ルックアップ・テーブル部分結果にアクセスする
ステップとをさらに含むことを特徴とする、上記１に記
載の方法。 ３． １行分のピクセルから入力ビットとして受け取る
ステップと、前記ビットを等価の１０進数に変換するス
テップとによって、値が導出されることを特徴とする、
上記２に記載の方法。 ４． 第１および第２の入力ピクセル・ウィンドウを第
１および第２のバッファにそれぞれ格納するステップ
と、前記第１のバッファの内容を処理するステップと、
各処理ステップの終了時に前記第１および第２にバッフ
ァの内容を１ピクセル分シフトするステップと、前記第
２のバッファの内容のすべてが前記第１のバッファにシ
フトされたときに第３の入力ピクセル・ウィンドウを前
記第２のバッファに格納するステップとをさらに含むこ
とを特徴とする、上記１に記載の方法。 ５． 前記部分結果を合計して階調・ピクセルを生成す
るステップをさらに含むことを特徴とする、上記１に記
載の方法。
み方法であって、ピクセル・アレイの１行に含まれるピ
クセルの組合せに関する部分畳み込み結果を生成するス
テップと、前記部分結果をルックアップ・テーブルに格
納するステップと、入力ピクセル・ウィンドウ内の１行
分のピクセルを前記ピクセル・アレイの前記行にマッピ
ングするステップと、突合せ行に関連する前記ルックア
ップ・テーブル部分結果にアクセスするステップとを含
む方法。 ２． 前記マッピング・ステップが、前記ピクセル・ア
レイの前記行に含まれる前記ピクセルの組合せから第１
の値を導出するステップと、前記ピクセルの組合せから
の前記第１の値を前記ルックアップ・テーブル内のその
関連部分結果に相関させるステップと、入力ピクセル・
ウィンドウ内の１行分のピクセルから第２の値を導出す
るステップと、前記第２の値に等しい第１の値に関連す
る前記ルックアップ・テーブル部分結果にアクセスする
ステップとをさらに含むことを特徴とする、上記１に記
載の方法。 ３． １行分のピクセルから入力ビットとして受け取る
ステップと、前記ビットを等価の１０進数に変換するス
テップとによって、値が導出されることを特徴とする、
上記２に記載の方法。 ４． 第１および第２の入力ピクセル・ウィンドウを第
１および第２のバッファにそれぞれ格納するステップ
と、前記第１のバッファの内容を処理するステップと、
各処理ステップの終了時に前記第１および第２にバッフ
ァの内容を１ピクセル分シフトするステップと、前記第
２のバッファの内容のすべてが前記第１のバッファにシ
フトされたときに第３の入力ピクセル・ウィンドウを前
記第２のバッファに格納するステップとをさらに含むこ
とを特徴とする、上記１に記載の方法。 ５． 前記部分結果を合計して階調・ピクセルを生成す
るステップをさらに含むことを特徴とする、上記１に記
載の方法。
【００６５】６． 前記階調出力ピクセルに対してしき
い値処理ステップを実行して出力ピクセルを生成するス
テップをさらに含むことを特徴とする、上記５に記載の
方法。 ７． 前記畳み込みが重み関数から導出されることを特
徴とする、上記１に記載の方法。 ８． 部分結果を生成する前記ステップにおいて、１つ
のピクセル行の可能なすべてのパターンに、前記ルック
アップ・テーブルに格納するための畳み込みカーネル・
マトリックスの対応行を掛けることを特徴とする、上記
１に記載の方法。 ９． 前記部分結果ルックアップ・テーブルが特定の倍
率について事前計算されることを特徴とする、上記１に
記載の方法。 １０． 前記部分結果ルックアップ・テーブルが変倍動
作中に必要に応じて生成されることを特徴とする、上記
１に記載の方法。 １１． 前記ルックアップ・テーブルが圧縮してＲＯＭ
に格納され、ランタイム時に圧縮解除されることを特徴
とする、上記１に記載の方法。 １２． 前記部分畳み込み結果が浮動小数点演算で計算
され、固定小数点精度に変換されてから、前記ルックア
ップ・テーブルに格納されることを特徴とする、上記１
に記載の方法。 １３． 前記部分結果が、プログラム可能メモリ、ＲＡ
Ｍ、または磁気記憶装置のうちの１つに格納されること
を特徴とする、上記１に記載の方法。
い値処理ステップを実行して出力ピクセルを生成するス
テップをさらに含むことを特徴とする、上記５に記載の
方法。 ７． 前記畳み込みが重み関数から導出されることを特
徴とする、上記１に記載の方法。 ８． 部分結果を生成する前記ステップにおいて、１つ
のピクセル行の可能なすべてのパターンに、前記ルック
アップ・テーブルに格納するための畳み込みカーネル・
マトリックスの対応行を掛けることを特徴とする、上記
１に記載の方法。 ９． 前記部分結果ルックアップ・テーブルが特定の倍
率について事前計算されることを特徴とする、上記１に
記載の方法。 １０． 前記部分結果ルックアップ・テーブルが変倍動
作中に必要に応じて生成されることを特徴とする、上記
１に記載の方法。 １１． 前記ルックアップ・テーブルが圧縮してＲＯＭ
に格納され、ランタイム時に圧縮解除されることを特徴
とする、上記１に記載の方法。 １２． 前記部分畳み込み結果が浮動小数点演算で計算
され、固定小数点精度に変換されてから、前記ルックア
ップ・テーブルに格納されることを特徴とする、上記１
に記載の方法。 １３． 前記部分結果が、プログラム可能メモリ、ＲＡ
Ｍ、または磁気記憶装置のうちの１つに格納されること
を特徴とする、上記１に記載の方法。
【００６６】１４． 画像処理中に２次元線形畳み込み
の複雑性を低減するための方法において、ピクセル・ア
レイの１行に含まれるピクセルの組合せに関する部分畳
み込み結果を生成するステップと、前記部分結果をルッ
クアップ・テーブルに格納するステップと、前記ピクセ
ル・アレイの前記行に含まれる前記ピクセルの組合せか
ら第１の値を導出するステップと、前記ピクセルの組合
せからの前記第１の値を前記ルックアップ・テーブル内
のその関連部分結果に相関させるステップと、第１およ
び第２の入力ピクセル・ウィンドウを第１および第２の
バッファにそれぞれ格納するステップと、前記第１のバ
ッファの内容を処理するステップと、各処理ステップの
終了時に前記第１および第２にバッファの入力ピクセル
を１ピクセル分ずつ順次シフトするステップと、入力ピ
クセル・ウィンドウ内の１行分のピクセルから第２の値
を順次導出するステップと、前記第２の値に一致する第
１の値に関連する前記ルックアップ・テーブル部分結果
にアクセスするステップと、前記第２のバッファ内の入
力ピクセルのすべてが前記第１のバッファにシフトされ
たときに第３の入力ピクセル・ウィンドウを前記第２の
バッファに格納するステップとを含む方法。
の複雑性を低減するための方法において、ピクセル・ア
レイの１行に含まれるピクセルの組合せに関する部分畳
み込み結果を生成するステップと、前記部分結果をルッ
クアップ・テーブルに格納するステップと、前記ピクセ
ル・アレイの前記行に含まれる前記ピクセルの組合せか
ら第１の値を導出するステップと、前記ピクセルの組合
せからの前記第１の値を前記ルックアップ・テーブル内
のその関連部分結果に相関させるステップと、第１およ
び第２の入力ピクセル・ウィンドウを第１および第２の
バッファにそれぞれ格納するステップと、前記第１のバ
ッファの内容を処理するステップと、各処理ステップの
終了時に前記第１および第２にバッファの入力ピクセル
を１ピクセル分ずつ順次シフトするステップと、入力ピ
クセル・ウィンドウ内の１行分のピクセルから第２の値
を順次導出するステップと、前記第２の値に一致する第
１の値に関連する前記ルックアップ・テーブル部分結果
にアクセスするステップと、前記第２のバッファ内の入
力ピクセルのすべてが前記第１のバッファにシフトされ
たときに第３の入力ピクセル・ウィンドウを前記第２の
バッファに格納するステップとを含む方法。
【００６７】１５． 前記部分結果を合計して階調・ピ
クセルを生成するステップをさらに含むことを特徴とす
る、上記１４に記載の方法。 １６． 前記階調・ピクセルに対してしきい値処理ステ
ップを実行して出力ピクセルを生成するステップをさら
に含むことを特徴とする、上記１５に記載の方法。 １７． １行分のピクセルから入力ビットとして受け取
るステップと、前記ビットを等価の１０進数に変換する
ステップとによって、値が導出されることを特徴とす
る、上記１４に記載の方法。
クセルを生成するステップをさらに含むことを特徴とす
る、上記１４に記載の方法。 １６． 前記階調・ピクセルに対してしきい値処理ステ
ップを実行して出力ピクセルを生成するステップをさら
に含むことを特徴とする、上記１５に記載の方法。 １７． １行分のピクセルから入力ビットとして受け取
るステップと、前記ビットを等価の１０進数に変換する
ステップとによって、値が導出されることを特徴とす
る、上記１４に記載の方法。
【００６８】１８． ２次元線形畳み込みの複雑性を低
減するためのシステムにおいて、ピクセル・アレイの１
行に含まれるピクセルの組合せに関する部分畳み込み結
果を生成する手段と、前記部分結果を格納するルックア
ップ・テーブルと、入力ピクセル・ウィンドウ内の１行
分のピクセルを前記ピクセル・アレイの前記行にマッピ
ングする手段と、突合せ行に関連する前記ルックアップ
・テーブル部分結果にアクセスする手段とを含むシステ
ム。 １９． 前記ピクセル・アレイの前記行に含まれる前記
ピクセルの組合せから第１の値を導出する手段と、前記
ピクセルの組合せからの前記第１の値を前記ルックアッ
プ・テーブル内のその関連部分結果に相関させる手段
と、入力ピクセル・ウィンドウ内の１行分のピクセルか
ら第２の値を導出する手段と、前記第２の値に等しい第
１の値に関連する前記ルックアップ・テーブル部分結果
にアクセスする手段とをさらに含む、上記１８に記載の
システム。 ２０． 第１および第２の入力ピクセル・ウィンドウを
それぞれ格納するための第１および第２のバッファを有
する２重バッファと、前記第１のバッファの内容を処理
する手段と、各処理ステップの終了時に前記第１および
第２にバッファの入力ピクセルを１ピクセル分シフトす
る手段と、前記第２のバッファの内容のすべてが前記第
１のバッファにシフトされたときに第３の入力ピクセル
・ウィンドウを前記第２のバッファに格納する手段とを
さらに含む、上記１８に記載のシステム。 ２１． 前記部分結果を合計して階調・ピクセルを生成
するステップをさらに含む、上記１８に記載のシステ
ム。 ２２． 前記階調・ピクセルに対してしきい値処理ステ
ップを実行して出力ピクセルを生成する手段をさらに含
む、上記２１に記載のシステム。
減するためのシステムにおいて、ピクセル・アレイの１
行に含まれるピクセルの組合せに関する部分畳み込み結
果を生成する手段と、前記部分結果を格納するルックア
ップ・テーブルと、入力ピクセル・ウィンドウ内の１行
分のピクセルを前記ピクセル・アレイの前記行にマッピ
ングする手段と、突合せ行に関連する前記ルックアップ
・テーブル部分結果にアクセスする手段とを含むシステ
ム。 １９． 前記ピクセル・アレイの前記行に含まれる前記
ピクセルの組合せから第１の値を導出する手段と、前記
ピクセルの組合せからの前記第１の値を前記ルックアッ
プ・テーブル内のその関連部分結果に相関させる手段
と、入力ピクセル・ウィンドウ内の１行分のピクセルか
ら第２の値を導出する手段と、前記第２の値に等しい第
１の値に関連する前記ルックアップ・テーブル部分結果
にアクセスする手段とをさらに含む、上記１８に記載の
システム。 ２０． 第１および第２の入力ピクセル・ウィンドウを
それぞれ格納するための第１および第２のバッファを有
する２重バッファと、前記第１のバッファの内容を処理
する手段と、各処理ステップの終了時に前記第１および
第２にバッファの入力ピクセルを１ピクセル分シフトす
る手段と、前記第２のバッファの内容のすべてが前記第
１のバッファにシフトされたときに第３の入力ピクセル
・ウィンドウを前記第２のバッファに格納する手段とを
さらに含む、上記１８に記載のシステム。 ２１． 前記部分結果を合計して階調・ピクセルを生成
するステップをさらに含む、上記１８に記載のシステ
ム。 ２２． 前記階調・ピクセルに対してしきい値処理ステ
ップを実行して出力ピクセルを生成する手段をさらに含
む、上記２１に記載のシステム。
【００６９】
【発明の効果】この発明によると画像処理技法の計算コ
ストを低減することができる。また、実用性をもたらす
ために時間複雑性と空間複雑性のバランスをとることが
できる。
ストを低減することができる。また、実用性をもたらす
ために時間複雑性と空間複雑性のバランスをとることが
できる。
【図１】先行技術により双３次Ｂスプライン補間によっ
て水平方向と垂直方向の両方に３倍に画像を変倍する様
子を示す図。
て水平方向と垂直方向の両方に３倍に画像を変倍する様
子を示す図。
【図２】双３次の均一多項式Ｂスプライン・テンソル積
曲面により３倍に変倍するための畳み込みカーネルのテ
ーブルを示す図。
曲面により３倍に変倍するための畳み込みカーネルのテ
ーブルを示す図。
【図３】２次元線形畳み込みの複雑性を低減するための
方法の流れ図。
方法の流れ図。
【図４】本発明によりライン・キャッシュとハッシュ関
数を示す図。
数を示す図。
【図５】本発明により双７次Ｂスプラインによって４倍
に変倍するための浮動小数点と固定小数点の８ビット表
現同士の食い違いを示す画像を示す図。
に変倍するための浮動小数点と固定小数点の８ビット表
現同士の食い違いを示す画像を示す図。
【図６】本発明によりメモリ・アクセスを最適化するた
めの２重バッファを示す図。
めの２重バッファを示す図。
【図７】２０ポイントのタイムズ・フォントのテスト画
像を示す図。
像を示す図。
３４ 入力ピクセル・ウィンドウ ３５ マッピング関数 ４６ 部分結果
Claims (1)
- 【請求項１】 画像処理のための２次元線形畳み込み方
法であって、 ピクセル・アレイの１行に含まれるピクセルの組合せに
ついて部分畳み込み結果を生成するステップと、 前記部分結果をルックアップ・テーブルに格納するステ
ップと、 入力ピクセル・ウィンドウ内の１行分のピクセルを前記
ピクセル・アレイの前記行にマッピングするステップ
と、 突合せする行に関連する前記ルックアップ・テーブルの
部分結果をアクセスするステップとを含む畳み込み方
法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/852,620 US6151025A (en) | 1997-05-07 | 1997-05-07 | Method and apparatus for complexity reduction on two-dimensional convolutions for image processing |
| US852,620 | 1997-05-07 |
Publications (3)
| Publication Number | Publication Date |
|---|---|
| JPH10326343A true JPH10326343A (ja) | 1998-12-08 |
| JPH10326343A5 JPH10326343A5 (ja) | 2005-09-08 |
| JP4091684B2 JP4091684B2 (ja) | 2008-05-28 |
Family
ID=25313810
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP12323298A Expired - Fee Related JP4091684B2 (ja) | 1997-05-07 | 1998-05-06 | 画像処理用の２次元畳み込み方法 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US6151025A (ja) |
| EP (1) | EP0877338A3 (ja) |
| JP (1) | JP4091684B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20200030524A (ko) * | 2020-03-12 | 2020-03-20 | 에스케이텔레콤 주식회사 | 연산 가속화가 적용된 신경망 모델의 생성 및 활용을 위한 장치 및 방법 |
Families Citing this family (24)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4046857B2 (ja) * | 1998-07-02 | 2008-02-13 | キヤノン株式会社 | 画像処理装置およびその方法、並びに、記録媒体 |
| WO2000038068A1 (en) * | 1998-12-22 | 2000-06-29 | Koninklijke Philips Electronics N.V. | Cache with access to a moving two-dimensional window |
| JP3676948B2 (ja) * | 1999-07-07 | 2005-07-27 | アルプス電気株式会社 | 画素数変換回路及びこれを用いた画像表示装置 |
| AU2002236659A1 (en) * | 2000-12-19 | 2002-07-01 | Pulsent Corporation | Adaptive transforms |
| US20050175258A1 (en) * | 2004-02-11 | 2005-08-11 | Leung Patrick W. | Method and apparatus for downscaling digital image data to fit a graphics display device |
| US7199797B2 (en) * | 2004-12-13 | 2007-04-03 | Dynacomware | Silhouette-oriented gray font generation |
| US8520253B2 (en) * | 2005-03-22 | 2013-08-27 | Infoprint Solutions Company, Llc | Method and system for scaling with dot gain control |
| US7782334B1 (en) * | 2005-09-13 | 2010-08-24 | Nvidia Corporation | Pixel shader-based data array resizing |
| US7505960B2 (en) * | 2005-11-15 | 2009-03-17 | Microsoft Corporation | Scalable retrieval of data entries using an array index or a secondary key |
| US7965305B2 (en) * | 2006-05-08 | 2011-06-21 | Global Oled Technology Llc | Color display system with improved apparent resolution |
| US8270759B2 (en) | 2008-06-16 | 2012-09-18 | International Business Machines Corporation | Transformation of a video image from a high dynamic range image to a low dynamic range image |
| US8160388B2 (en) | 2008-06-17 | 2012-04-17 | International Business Machines Corporation | Spatially selective transformation of a spatially varying optical characteristic of an image in an array of pixels |
| US8452087B2 (en) | 2009-09-30 | 2013-05-28 | Microsoft Corporation | Image selection techniques |
| US8655069B2 (en) | 2010-03-05 | 2014-02-18 | Microsoft Corporation | Updating image segmentation following user input |
| US8411948B2 (en) * | 2010-03-05 | 2013-04-02 | Microsoft Corporation | Up-sampling binary images for segmentation |
| US8422769B2 (en) | 2010-03-05 | 2013-04-16 | Microsoft Corporation | Image segmentation using reduced foreground training data |
| US8854375B2 (en) * | 2010-10-19 | 2014-10-07 | Dynacomware Taiwan Inc. | Method and system for generating gray dot-matrix font from binary dot-matrix font |
| US8687902B2 (en) | 2012-03-29 | 2014-04-01 | Intel Corporation | System, method, and computer program product for decompression of block compressed images |
| CN104462196B (zh) * | 2014-10-30 | 2019-01-22 | 南京信息工程大学 | 多特征联合哈希信息检索方法 |
| GB2552238A (en) | 2016-04-18 | 2018-01-17 | Argon Design Ltd | Blending images |
| CN107526709A (zh) | 2016-06-15 | 2017-12-29 | 辉达公司 | 使用低精度格式的张量处理 |
| US11403727B2 (en) * | 2020-01-28 | 2022-08-02 | Nxp Usa, Inc. | System and method for convolving an image |
| KR20220039313A (ko) | 2020-09-22 | 2022-03-29 | 삼성전자주식회사 | 뉴럴 네트워크 연산 처리 방법 및 장치 |
| CN114328802B (zh) * | 2021-12-08 | 2025-05-06 | 腾讯科技（深圳）有限公司 | 对象处理方法、装置、设备、存储介质和计算机程序产品 |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4528693A (en) * | 1982-09-30 | 1985-07-09 | International Business Machines Corporation | Apparatus and method for scaling facsimile image data |
| JPS623372A (ja) * | 1985-06-27 | 1987-01-09 | インタ−ナショナル ビジネス マシ−ンズ コ−ポレ−ション | 画像変換装置 |
| US4843380A (en) * | 1987-07-13 | 1989-06-27 | Megatek Corporation | Anti-aliasing raster scan display system |
| US5274469A (en) * | 1991-12-23 | 1993-12-28 | Eastman Kodak Company | Sample rate converter circuit for image data |
| US5410616A (en) * | 1992-05-28 | 1995-04-25 | Unisys Corporation | Loop-up table image scaling for rational factors |
| US5483605A (en) * | 1993-12-27 | 1996-01-09 | Xerox Corporation | High speed pattern recognition technique for implementation of resolution enhancement algorithms into an application specific integrated circuit (ASIC) device |
| US5627953A (en) * | 1994-08-05 | 1997-05-06 | Yen; Jonathan | Binary image scaling by piecewise polynomial interpolation |
-
1997
- 1997-05-07 US US08/852,620 patent/US6151025A/en not_active Expired - Lifetime
-
1998
- 1998-05-06 JP JP12323298A patent/JP4091684B2/ja not_active Expired - Fee Related
- 1998-05-06 EP EP98303531A patent/EP0877338A3/en not_active Withdrawn
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20200030524A (ko) * | 2020-03-12 | 2020-03-20 | 에스케이텔레콤 주식회사 | 연산 가속화가 적용된 신경망 모델의 생성 및 활용을 위한 장치 및 방법 |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0877338A2 (en) | 1998-11-11 |
| US6151025A (en) | 2000-11-21 |
| EP0877338A3 (en) | 1999-11-24 |
| JP4091684B2 (ja) | 2008-05-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4091684B2 (ja) | 画像処理用の２次元畳み込み方法 | |
| US7149369B2 (en) | Method and system for image scaling | |
| US5224062A (en) | Method and apparatus for fast implementation of inverse discrete cosine transform in a digital image processing system using optimized lookup tables | |
| JP2931389B2 (ja) | 単一のマルチプライヤ／アキュムレータと単一のランダムアクセスメモリを用いてｄｃｔ／ｉｄｃｔ演算を繰り返す集積回路装置 | |
| US6757431B2 (en) | Resolution conversion for anti-aliased images using loose gray scale template matching | |
| EP0407213B1 (en) | Image processing apparatus | |
| JPH0696198A (ja) | エラー拡散を利用したビットマップ画像の非量子化解像度変換 | |
| JPH06217146A (ja) | デジタル画像処理システムでｉｄｃｔを実施する方法及びそのためのｉｄｃｔプロセッサ | |
| JP2821489B2 (ja) | 静止画像圧縮処理装置及び方法 | |
| JPH05502534A (ja) | ディジタル画像のノイズ除去システムおよび方法 | |
| KR100271994B1 (ko) | 고속2차원코사인변환필터링방법및그장치 | |
| US5493419A (en) | Stack filters for 1-to-N bit image processing in electronic printers | |
| JPH09212477A (ja) | デジタル画像処理プロセッサ | |
| JPH11243490A (ja) | 誤差拡散値の処理方法 | |
| EP0454495B1 (en) | Half-tone image processing system | |
| JPH07210670A (ja) | 画像処理装置 | |
| JPH10326343A5 (ja) | ||
| US5867612A (en) | Method and apparatus for the fast scaling of an image | |
| JP3171993B2 (ja) | 画像処理方法及び装置 | |
| US5917961A (en) | Image convolution using pre-calculated lookup tables | |
| US7627188B2 (en) | Error diffusion method and hardware architecture | |
| US8520253B2 (en) | Method and system for scaling with dot gain control | |
| Chiarabini et al. | Complexity reduction on two-dimensional convolutions for image processing | |
| US6282323B1 (en) | Image processing method and apparatus | |
| JPH06187436A (ja) | 画像データ処理装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050315 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050315 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070710 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20071010 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20071015 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20071227 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20080219 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20080229 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110307 Year of fee payment: 3 |
|
| LAPS | Cancellation because of no payment of annual fees |