(57)【特許請求の範囲】
【請求項１】
画素の各走査線を出力するか、出力しないかによって、画素のビデオ画像をリサイズして、整数ｎの因数によってリサンプルする方法において、
最初の走査線へ進んで、走査カウントをゼロにセットし、誤差値を設けるステップと、
ａ）次の走査線へ進んで、該次の走査線を出力する場合に生じるであろう誤差の関数である誤差値を計算するステップと、
ｂ）前記誤差値が第１所定量より大きければ、該誤差値を減分して、ステップａ）へ戻すステップと、
ｃ）前記誤差値が第２所定量（前記第１所定量より小さい）より大きければ、前記走査カウントを増分するとともに前記誤差値を増分し、前記走査カウントがｎに等しければ、前記次の走査線を出力するとともに前記走査カウントをゼロにセットしてステップａ）へ戻し、前記走査カウントがｎに等しくなければ、そのままステップａ）へ戻すステップと、
ｄ）前記誤差値が第２所定量以下であれば、前記走査カウントを２だけ増分するとともに前記誤差値を増分するステップと、
ｅ）前記走査カウントがｎに等しいかそれ以上であれば、前記次の走査線を出力するとともに、前記走査カウントをｎだけ減分してステップａ）へ戻し、前記走査カウントがｎより小さければ、そのままステップａ）へ戻すステップとから成る
ことを特徴とする前記ビデオ画像のリサイズ及びリサンプル方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、ディジタル画像をリサンプル(resample)し、リサイズ(resize)する方法と回路を提供する。各繰り返しは、走査線上の各ｎ個の画素を１個の平均画素に変換して水平方向に１／ｎにリサンプルし、そしてｎ本のプラスまたはマイナスのわずかなパーセントの入力走査線ごとに１本の走査線を出力して画像を垂直方向にリサンプルし、かつリサイズする。
【０００２】
【従来の技術】
画像のサイズを少し変更することが必要なことは多い。例えば、１つおきの画素を削除すれば、画像は１／２に縮小するであろうし、画素を複製すれば、画像のサイズは２倍になるであろう。２の倍数未満で画像のサイズを変更するため、アルゴリズム、例えば最隣接（nearest neighbor）アルゴリズムを使用して必要な数の画素を生成することができる。
【０００３】
また、画像の画素をリサンプルすることが必要なこともある。例えば、画像をより高画素密度のスキャナで走査し、より低画素密度で処理または印刷しなければならない場合には、より少ない画素数／インチへ変換する必要がある。
【０００４】
しかし、これらの処理のどちらであっても画像の画素が削除されれば、データが失われるであろう。これを最小限度にするために、最初に画素を平均することができる。すなわち、多数の画素を１個の平均画素で置き換えることができる。
【０００５】
それらの操作の結果、画質は最小限度損なわれるが、リサンプルされ、かつサイズが少し変更された画像が得られる。
【０００６】
【発明が解決しようとする課題】
この方法は、カラー複写機において偽造防止の第１段階として使用することができる。最も簡単なやり方の場合、紙幣をプラテンの上に置いて複写することによって偽造することができる。偽造を防止するために、紙幣は種々のサイズ、形状、および色彩の標識が付いている。スキャナの画像出力を分析し、もし複写機の紙幣検出回路によって特定サイズの紙幣の標識が発見されれば、複写を中止することができる。この検出にひっかからないように、偽造者は、標識が紙幣検出器で認識されないように画像のサイズを十分に拡大し、そのあと印刷時に同じ量だけ画像を縮小するようにスキャナを設定することができる。
【０００７】
これを防止するために、偽造者がスキャナに設定した拡大（または縮小）の量に対応する数(number)を検出回路に与えて、紙幣の標識を検査する前に同じ量だけ画像のサイズを縮小（拡大）しなければならない。
【０００８】
さらに、画像の画素密度は検出回路が必要とする画素密度より大きいので、最初にデータをリサンプルしなければならない。画像の画素の平均化が加わったので、全体の処理は、平均化、サイジング、およびリサンプリングになる。
【０００９】
最後の問題は回路速度である。何かの種類のオリジナル（原文書）がプラテンの上に置かれたとき、紙幣の検査が完了するまで複写機は印刷を開始することができない。また、この検査はオリジナルごとに実行しなければならないので、経過時間をできるだけ短縮しなければならない。したがって、経過時間を最小にするためパイプライン回路において実行できるアルゴリズムが要望されている。
【００１０】
この検討において、理解を助けるため数値例を用いる。ここで、リサンプリングは４対１であると仮定する。そしてリサイジングは＋２０％または−２０％の間であると仮定する。
【００１１】
典型的なカラー複写機は、用紙の速度を垂直方向すなわち低速走査方向にスローダウンさせることによって画像のサイズを少し変化させるが、高速走査方向にはクロックは不変である。従って、複写機は、最隣接（nearest neighbor）アルゴリズムを使用して画素の密度を水平方向すなわち高速走査方向に変化させることにより、画像のサイズを少し変更できるだけである。
【００１２】
したがって、水平方向には、必要なことは画像をリサイズする前に画素をリサンプルするだけであるが、それは一度に４個の画素を平均し、その結果をサンプルされた画素として使用することによって達成される。
しかし、垂直方向には、３および５対１の間の縮小率を使用して、＋２０％または−２０％までの画像変化をさせなければならないであろう。この縮小は適当な数の介在する走査線を削除することによって行われる。
このすべてを短時間に実行する回路が要望されている。
【００１３】
【課題を解決するための手段】
このアルゴリズムは、４個の連続画素を平均して１個の現平均画素を生成する（水平方向にリサンプルする）ことができると同時に、現走査線上の画素を削除または出力すべきかどうかを決定する（垂直方向にリサンプルし、リサイズする）ことができるパイプライン回路において実施するように設計されている。
【００１４】
垂直方向には、リサンプリング比（４対１）と画像サイズ変化（＋２０％または−２０％）から、アルゴリズムはページ上の走査線を出力すべき場所を計算することができる。数値例の場合、入力が４００スポット／単位時間であれば、リサンプリングは単位時間の１／１００ごとに１本の走査線を生成するであろう。さらに、画像を５％だけ縮小しなければならないならば、最終出力は単位時間の１／９５ごとに１本の走査線を生成するであろう。走査線が存在しなければならない各時間に最も近い実際の走査線が出力されるように、アルゴリズムを構成することができるであろう。これにより、適当な走査線出力が生成されるであろうが、そのプロセスは厄介である。
【００１５】
このアルゴリズムは誤差項のランニング合計を使用して同じ結果を達成する。簡単に述べると、もし前の出力走査線が厳密に正しい時間に出力されたことがわかっていれば、誤差はゼロである。しかし、走査線の出力が早すぎたり遅すぎたりすれば、誤差項は存在するであろう。出力されない新しい各走査線については、単位時間の１／４００が誤差項に加えられる。最後に、誤差項が所定のしきい値に達すると、アルゴリズムはそれができ得る最も接近した近似であることを知り、現走査線が出力され、ランニング合計から時間単位の１／９５が減じられ、アルゴリズムは次の走査へ進む。
【００１６】
回路は、４つのクロックサイクルについて第１セクションを使用して現走査線の最初の４個の入力画素を平均し、そして第２セクションを使用して第５クロックサイクルについてリサンプリングとリサイジングを実行すると同時に、次の走査線の４個の画素に対し第１セクションを開始しようとする。このように、完全なパイプライン回路は平均化セクションの速度を操作する。
【００１７】
【発明の実施の形態】
処理は、次の走査に進む前に各完全な走査線内の４画素の各グループについて１個の平均画素を生成することによって進行する。各画素は生成されると、リサンプリングおよびリサイジングを達成する表１と表２に示すように、出力されるか，されないかのどちらかである。それらの例の場合、両ケースのリサンプリング率は２５％であると仮定しているので、基本的処理は４本の走査線のうち３本が除去されるという結果をもたらす。これは最初の４本の「走査線」、ｙ＝０からｙ＝３について示してあり、最初の３本の走査線は「出力」されず、４番目の走査線が出力される。
【００１８】
【表１】
0004298130.tif 000002
【００１９】
【表２】
0004298130.tif 000003
【００２０】
しかし、表１はスキャナの拡大率が１２０％であると仮定しているので、リサイジングステップは２５％より少し多い走査線を除去するであろう。これは、次の５本の走査線（ｙ＝４からｙ＝８まで）について出力は１つ(y=0)だけであるということで示されている。同様に、表２は、スキャナの拡大率が８０％であったと仮定しているので、３本の走査線ごとに出力がある時がある。
【００２１】
２つの表において、“count _y＝０”欄は、各走査線について、増分（インクリメント）またはリセットされた走査線カウンタのカウントを示し、“モード”欄は、現走査線がどのように扱われるかを示す。モード０の場合、出力は存在せず、走査線のカウントは増分されない。モード１の場合、走査線のカウントは増分され、出力は存在しない。モード２の場合、走査線のカウントはゼロにセットされ、現走査線が出力される。モード３の場合、走査線のカウントは２倍に増分され、出力は存在しない。モード４の場合、走査線のカウントはゼロにセットされ、出力は存在する。モード５の場合、走査線のカウントは１にセットされ、出力は存在する。この一組の結果は以下のプログラムによって生成される。
【００２２】
画像のスケールアルゴリズムのための可変リサンプルレート
低速走査方向には、４本の走査線ごとに１本の走査線を出力する（４００ｓｐｉから１００ｓｐｉへリサンプルする）代わりに、もし可変モードが＞＝４または＝＝２であれば、走査線を出力する。
各走査線について可変モードの計算アルゴリズムは下記の通りである。
Define scale = MAG (MAG = 120, if MAG = 120, scale = 120);
half_scale = scale / 2;
two_scale = scale * 2;
err_y = 0;
for (y = 0. count_y = 0; y < scanlines; Y++)
{
if (err_y > half_scale) {
mode = 0;
err_y −=100;
}
else if (err_y >= −half_scale) {
err_y += scale−100;
count_y ++;
if (count_y == 4) {
count_y = 0;
mode = 2;
}
else mode = 1;
}
else {
err_y += two_scale − 100;
count_y += 2;
if (count_y >= 4 ){
mode = count_y;
count_y -= 4;
}
else mode = 3;
}
}
【００２３】
このプログラムを表１と比較するために、初期状態は、
scale = 120.
half_scale = 60.
two_scale = 240 (表１の場合).
である。
err_y、y、および line count は０に初期化される。
【００２４】
そのあと、各ループについて、
誤差 err_y が６０以上（８０であろう）を越えると、モードは０であり、現err_y (80) から１００が減じられて−２０になり、カウントは増分されない。
【００２５】
err_y が  half_scale 以上( −40 から 60まで )であれば、err_y を２０だけ増し、カウントを増分する。カウントが４であれば、モードは２であり、走査線カウントを増分する。さもなければ、モードは１（走査線カウントを０にリセットし、走査線を出力しない）である。
【００２６】
このプログラムの残りの部分はもっぱら表２に適用される。ここで、
scale = 80.
half_scale = 40.
two_scale = 160.
である。
【００２７】
err_y (- 60) は、two_scale (160) − 100 = 60だけ増加し、その結果err_y = 0 になり、走査線カウントは２だけ増される。この時点のカウントが４または５であれば、モードはその数にセットされ、カウントは４だけ減じられる。もしそうでなければ、モードは３であり、出力はない。
【００２８】
このプログラムは図１のフローチャートに一般化されている。ここで、Ｋは err_y に対応している。プログラムは、ステップ２１、２２において、走査線カウントと err_y 項をゼロに初期化することから始まる。ステップ２３において、誤差項がhalf scale より大きければ、ステップ２４において、誤差項は１００だけ減じられ、ステップ２５において、モードは０にセットされる（走査線カウントは増分されない）。ステップ２６において、それが最後の走査線でなかったならば、処理は、ステップ２７を通って次の走査線すなわちステップ２８へ進む。
【００２９】
ステップ２３において、誤差項がhalf scaleに等しいか、それ未満であれば、ステップ２９へ進み、そこで誤差項が−half scaleより大きければ、ステップ３０において、誤差項は１００だけ減じられ、そしてscaleだけ増加される。ステップ３１において，カウントが増分される。このとき、ステップ３２において、走査線カウント＝４であれば、ステップ３３において、走査線カウントが０にリセットされ、ステップ３４において、モードは２になり（１本の走査線が出力される）、ステップ２８へ戻る。ステップ３２において、走査線カウントが４でなければ、ステップ３５において、モードは１になり、出力はない。
【００３０】
ステップ２９において、もし誤差項がhalf scale未満であれば、ステップ３６において、誤差項は１００だけ減じられ、two scaleだけ増加される。ステップ３７において、カウントは２だけ増分される。次にステップ３８において、カウントが４以上であれば、ステップ３９において、モードを４または５のカウントにセットし（走査線を出力する）、ステップ４０において、カウントから４を減じる。ステップ３８において、カウントが４未満であれば、ステップ４１において、モードは３にされる（出力はない）。
【００３１】
このアルゴリズムは、理想的な結果に最も接近した近似である出力走査線を生成する。これを明らかにするために、以下の２つの例において、誤差分散がどのように最適化されるかを示す。
（１）  Scale = 120 で拡大された画像の場合、アルゴリズムの目的は、１２０本の入力走査線ごとに２０本の走査線を削除して、入力画像をScale ＝ 100 の原サイズへ復元することと、削除した走査線が１２０本の入力走査線の端から端まで確実に均等に分布されるようにして、入力画像の完全性を維持することである。
【００３２】
Scale / (Scale − 100) 本の入力走査線ごとに１本の走査線を削除する。Scale=120の場合は、６本の走査線ごとに１本の走査線を削除する。削除されない走査線の数は、
｛Scale / (Scale − 100)= 100 / (Scale − 100) である。Scale = 120 の場合、削除されない走査線の数は５である。言い替えると，最初の５本の走査線を維持し、６番目の走査線を削除する。
【００３３】
可変err_y を定義し、各走査線について、可変 err_y を（Scale − 100）だけ増加させる。次の走査線は削除すべき走査線である。err_y > 60 の時、err_y を100 だけ減じて、再びやり直す。
【００３４】
アルゴリズムは、初期状態としてerr_y = 0 で始まる。維持した各走査線について、err_y が1 / 2 Scale を越えるまで、（Scale − 100）だけ増加させる。次の走査線を削除し、err_y を 100 だけ減じて、再びやり直す。本質的に、err_y は｛1 / 2 Scale - 100｝から1 / 2 Scale へオフセットされる。
【００３５】
Scale = 120の場合、５本の走査線の後、100 / (Scale − 100) = 5 である。  err_y は 100 の全範囲まで増加される。次の走査線について、８番目の走査線を削除し、err_y を 100 だけ減じる。err_yには何も残っていない。
【００３６】
Scale = 115の場合、100 / (Scale − 100) = 6であり、残余は１０である。７本の走査線の後、err_y は 105 の絶対範囲まで増加される。８番目の走査線を削除し、err_y を 100 だけ減じる。５の値は次の計算ラウンドへ拡散される誤差である。
【００３７】
（２）  Scale = 80 で縮小された画像の場合、アルゴリズムの目的は、８０本の入力走査線ごとに２０本の走査線を複製して、入力画像をScale = 100 の原サイズへ復元することと、複製された走査線が８０本の入力走査線の端から端まで確実に均等に分布されるようにして、入力画像の完全性を維持することである。
【００３８】
Scale / (100 − Scale) 入力走査線ごとに、１本の走査線を複製する。Scale = 80の場合には、４本の走査線ごとに１本の走査線を複製する。複製されない走査線の数は、
{Scale / (100 − Scale) − 1} = (2*Scale − 100) / (100 − Scale) である。Scale = 80の場合、複製されない走査線の数は３である。言い替えると、最初の３本の走査線を維持し、４番目の走査線の終りに、４番目の走査線を複製する。
【００３９】
可変err_y を定義し、各走査線について、その可変err_y を(Scale − 100)だけ減じる。  err_y < (2*scale − 100)まで、次の走査線は複製すべき走査線である。err_y に(2*Scale − 100)を加えて、再びやり直す。
【００４０】
アルゴリズムは、初期状態として  err_y = 0で始まる。各走査線について、err_y が  1 / 2 Scale 未満になるまで、err_y を(Scale − 100)だけ減じる。次の走査線の終りに、次の走査線を複製し、err_y に(2*Scale − 100)だけ加えて、再びやり直す。本質的に、err_y の範囲は−1 / 2 Scaleから{−1 / 2 Scale + (2*Scale − 100)}へオフセットされる。
【００４１】
Scale = 80の場合、3本の走査線の後、(2*Scale − 100) / (100 − Scale) = 3 であり、err_y は１００の全範囲まで減じられる。次の走査線について、４番目の走査線を複製し、err_y を６０だけ増加させる。err_yには何も残っていない。
【００４２】
Scale = 85の場合、(2*Scale − 100) / (100 − Scale) = 4 であり、残余は10 である。5本の走査線の後、err_y は  75の範囲まで減じられる。6番目の走査線の終りに、６番目の走査線を複製し、err_y を７０だけ増加させる。
【００４３】
５の値は次の計算ラウンドへ拡散する誤差である。
【００４４】
平均化、リサンプリング、およびリサイジングを実行する回路は、図２の２段パイプライン回路である。画素はライン５０に入力される。各ブロックの４つの入力画素の最初の画素は、加算器５２をバイパスして、マルチプレクサ５１を介して加えられ、レジスタ５３にロードされる。次の３つのクロックのとき、画素は加算器５２に対する１入力として使用される。レジスタの内容はランニング合計を他の入力に提供するため使用される。ブロックの４つの入力が合計されて１０ビット数になった後、合計はシフタ５４において１６で除せられ、マルチプレクサ５５を介してラインバッファ５６に格納される。（４つの画素の平均を求めるには、一般に、４で除すが、ここでは、結局、４つの画素の４つの走査線がそれぞれ最後に合計されることがわかっているので、１６による除算が１ステップで行われる。）最初の走査線の終りに、ラインバッファは各画素について部分合計を有する。
【００４５】
次の走査線について、シフタ５４からの合計が加算器５８の一方の入力に加えられ、加算器の他方の入力はマルチプレクサ５９によって出力レジスタ６０へ転送されたラインバッファからの部分合計を受け取る。この結果がさらに別の部分合計であれば、マルチプレクサ５５によってラインバッファ５６に送り戻される。この結果が最後の平均画素であれば、（通常は）レジスタ６０によって出力される。
【００４６】
複雑なのは、モード０の場合に、その全走査線が無視され、走査線カウンタが増分されないことである。すべての場合において、各出力画素について１６の画素を平均化する必要がある。このモード０の場合には、５つの入力走査について１つの出力があるであろうが、必要な総計１６の画素を提供するため使用されるのは４つだけであろう。
【００４７】
同様に、表２に、３本の走査線ごとに出力がある時がある。このケースにおいて１６の画素を得るために、１セットがダブラ６１へ送られ、加算器６２において加算されて正しい出力が得られる。
【００４８】
さらに、図２のフローチャートに示すように、アルゴリズムにおいて、モード数（mode number）を生成するためモジュロ３カウンタ６４が使用されており、また走査線クロックをカウントダウンしてＲＡＭ５６のためアドレスポインタを生成するためＲＡＭアドレスカウンタ６３が使用されている。
【００４９】
この完全な回路は４つの入力画素を平均するため４つのクロックを使用しており、回路の残り部分は次のブロックの最初のクロックに対して実行するようにパイプラインされる。
【図面の簡単な説明】
【図１】アルゴリズムのフローチャートである。
【図２】回路の簡単なブロック線図である。
【符号の説明】
５０  ライン
５１  マルチプレクサ
５２  加算器
５３  レジスタ
５４  シフタ
５５  マルチプレクサ
５６  ＲＡＭ
５８  加算器
５９  マルチプレクサ
６０  レジスタ
６１  ダブラ
６２  加算器
６３  ＲＡＭアドレスポインタ
６４  モジュロ３カウンタ
【図１】
0004298130.tif 000004
【図２】
0004298130.tif 000005