(57)【特許請求の範囲】
【請求項１】
ディジタル画像上の隣接画素グループに対する空間周波数を計算し、一定値以上の高周波成分を含んでいる領域を抽出するステップと、
前記ディジタル画像中の除去候補となる画素グループを含む縦又は横方向のパスである除去パスを、前記抽出した高周波成分を含んだ領域を迂回するように、上下又は左右若しくは対角に隣接した画素をつなげて、前記ディジタル画像を上下に縦断もしくは左右に横断するパスとし、前記除去パスを複数選択するステップと、
前記１つの除去パスに含まれる画素グループを削除することにより、前記ディジタル画像の高周波成分が維持される程度を得点化した除去パスメトリックを除去パス毎に計算するステップと、
前記複数選択した除去パスの中から最も高周波成分が維持される得点となる除去パスメトリックを有する除去パスを選択するステップと、
該選択した除去パスに含まれる画素グループを除去するステップと
を含んでなることを特徴とするディジタル画像のダウンサンプリング方法。
【請求項２】
所望のダウンサンプリング率を達成するために設定したパス起点数で、前記ディジタル画像の１つのエッジに沿ってパス起点をほぼ均等に配分するステップをさらに含むことを特徴とする請求項１に記載のディジタル画像のダウンサンプリング方法。
【請求項３】
前記パス起点をほぼ均等に配分する前記ステップにおける前記パス起点を順序立てて配置するステップと、所与のパス起点に対応する除去パスを選択するステップをさらに含み、該除去パスを選択する該ステップは、それ以後に配置するパス起点用の除去パスを選択する以前に実行することを特徴とする請求項２に記載のディジタル画像のダウンサンプリング方法。
【請求項４】
前記パス起点を順序立てて配置する前記ステップは、先に選択された全てのパス起点との距離の和と前記画像のエッジからの距離の和が最も離れた位置にあるパス起点を、次のパス起点として選択することを特徴とする請求項３に記載のディジタル画像のダウンサンプリング方法。
【請求項５】
各パス起点毎に２つ又はそれ以上の除去パスのスタート位置候補の組みを生成するステップをさらに含むことを特徴とする請求項２に記載のディジタル画像のダウンサンプリング方法。
【請求項６】
前記除去パスメトリックは、現在選択されているパス起点により近い前記除去パスを優先選択することを特徴とする請求項２に記載のディジタル画像のダウンサンプリング方法。
【請求項７】
各々の除去パスメトリックは、前記除去パスが垂直方向に折れ曲がっている箇所に対し該除去パスにペナルティを課すことを特徴とする請求項１に記載のディジタル画像のダウンサンプリング方法。
【請求項８】
前記ディジタル画像中の拡張チェッカー盤模様の領域を位置決めするステップと、ダウンサンプリング前に、これらの領域を２つのチェッカー盤色の平均値である一様色に置き換えるステップとをさらに含むことを特徴とする請求項１に記載のディジタル画像のダウンサンプリング方法。
【請求項９】
前記画素を除去するステップは、該ステップ中にその画素の強度を少なくとも１つの近隣の画素の強度と平均化することを含むことを特徴とする請求項１に記載のディジタル画像のダウンサンプリング方法。
【請求項１０】
除去のためにマークされた前記画素とその近隣の画素が強度において著しく異なる場合にのみ前記平均化するステップを実行することを特徴とする請求項９に記載のディジタル画像のダウンサンプリング方法。
【請求項１１】
ディジタル画像を入力として受信し、該ディジタル画像上の隣接画素グループに対する空間周波数推定値を計算し、一定値以上の高周波成分を含んでいる領域を抽出する空間周波数推定器と、
前記ディジタル画像中の除去候補となる画素グループを含む縦又は横方向のパスである除去パスを、前記抽出した高周波成分を含んだ領域を迂回するように、上下又は左右若しくは対角に隣接した画素をつなげて、前記ディジタル画像を上下に縦断もしくは左右に横断するパスとし、前記除去パスを複数発生するパス候補発生器と、
前記１つの除去パスに含まれる画素グループを削除することにより、前記ディジタル画像の高周波成分が維持される程度をパス得点として計算するパス得点評価器と、
前記複数発生した除去パスの中から最も高周波成分が維持される得点を有する除去パスを選択して該除去パスに含まれる画素グループを除去し、ダウンサンプルリングしたディジタル画像を生成する画素除去器と
を有することを特徴とするディジタル画像のダウンサンプリングシステム。
【請求項１２】
前記画素除去器により得られた前記ダウンサンプリングされたディジタル画像を、原ディジタル画像から所望数の除去パスが当該システムによって除去されるまで、当該システムにフィードバックする反復器をさらに含むことを特徴とする請求項１１に記載のディジタル画像のダウンサンプリングシステム。
【請求項１３】
前記パス候補発生器のために前記ディジタル画像中のパス起点位置を選択するパス起点位置発生器をさらに含むことを特徴とする請求項１１に記載のディジタル画像のダウンサンプリングシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタル画像処理における冗長画素を除去してダウンサンプリングを行うディジタル画像のダウンサンプリング方法及びシステムに関する。
【０００２】
【従来の技術】
ディジタル画像は、典型的には、行列グリッドに配置された画素値の集まりとして入力シーンを表現する。画像グリッド中の各画素値は、種々の可能な画素フォーマットによるその位置で抽出された画像のグレイシェード又は色を表現する。
【０００３】
図１は、仮想の画像の横列に沿った画素強度を示す棒グラフである。画像の強度変化は、人が画像をトラバースする際に生じる強度変化速度の測定値である空間周波数で記述できる。図１の棒グラフは、画像の１つの横列に対する画素値を仮想で示したものである。縦列０から１７迄の範囲で優勢な強度変化は１５画素毎に約１サイクルの低い周波数変化である。縦列１８から３８迄の範囲で優勢な変化は、更に高く、４画素毎に約１サイクルである。最後に、縦列３９から４４は、２画素毎に１サイクルに近い空間周波数を示しており、これは、ディジタルサンプル化画像上で表現できうる最高の空間周波数である。１画素当たり０.５サイクルの空間周波数は、テキストのような鋭いエッジを有するコンピュータ生成グラフィックスにおいて最も頻繁に観察される。
【０００４】
ディジタル画像表示装置は種々の空間解像度のものがある。例えば、パーソナルコンピュータのスーパービデオグラフィックスアレイ（ＳＶＧＡ）表示フォーマットは、幅８００画素×高さ６００画素のグリッドを使用している。拡張グラフィックスアレイ（ＸＧＡ）表示フォーマットは、幅１０２４画素×高さ７６８画素のグリッドを使用している。
【０００５】
或る１つの空間解像度で生成された画像をより低い解像度の装置で表示しなければならない場合、画像は低解像度装置にとって大きすぎることになる。かような場合、表示方法として以下の２つの選択が可能である。
【０００６】
第１の表示方法として、ユーザは画像の一部を見ることが可能である。例えば、ユーザはＳＶＧＡサイズ表示装置上でＸＧＡサイズ画像中の６１％の画素領域を見ることができる。残りの画素を見るために、ユーザは、画像を水平及び垂直の両方向にスクロールしなければならず、当初画素の若干部は画面からはみ出してしまう。この方法は、全体的に不愉快である。テキストを読む際には、ユーザは、テキストの各行ごとに画像を前後に移動させねばならない。又、グラフィクスは、まとめて見ることができないので迫力を失う。
【０００７】
第２の表示方法として、ユーザは画像のダウンサンプリングを行なうことが可能である。ダウンサンプリングでは、原画像から画素を除去することにより所望の解像度に適合する画像を生成する。例えば、１０２４×７６８のＸＧＡ画像は、画像の縦列から２２４画素列と画像の横列から１６８画素列を除去して８００×６００のＳＶＧＡ画像にダウンサンプリングすることができる。この方法の利点は全体画像を一度に見られることである。しかし、原画像の縦列と横列を除去することで情報を放棄するという欠点がある。
【０００８】
最も簡単なダウンサンプリング方法は、ダウンサンプリング率により定められた間隔で横列と縦列を除去する方法である。かような方法では、除去すべき横列の数と横列間の必要な間隔が計算される。第１横列を除去すると、その後、第１横列から除去間隔の倍数だけ離れた横列を各々同様にして除去する。次に、同一のアルゴリズムを縦列に適用し、同様にして縦列を除去する。
【０００９】
この除去方法は、詳細度の低い像の場合は許容できる結果をもたらすが、詳細度の高い像、特にグラフィックス像は実質的に理解不能にする。
図３０は、従来技術による図１の画素強度値をダウンサンプリングするための画素強度値を示す棒グラフで、図中の画像は図１の幅に一致させるために２倍幅で示した画素を有している。倍率２で、偶数番の横列を除去することで図中の画像の横列を生成するために図１の画像の横列をダウンサンプリングする場合を考える。原画像画素の横列（縦列０〜１７）の低周波数部分において、除去後も強度変化の全体形状は保存された。中間周波数部分（縦列１８〜３８）においては、除去により強度変化が殆ど失われた。高周波数部分（縦列３９〜４４）においては、強度変化は除去により消去された。縦列１８〜４４における劣等な結果は、エイリアシングのためであり、即ち、所望されるサンプルレートに対し高すぎる空間周波数を含んでいるために生じるサンプル資料からのアーチファクトによるものである。
【００１０】
このエイリアシングの影響は、実際の像において観察できる。
図３は、コンピュータで作成されたグラフィクスウィンドウのスナップショット画像を示す図である。図３２は、０.７８１の倍率（ＸＧＡ画像のＳＶＧＡ画像への変換に相当する）で消去したダウンサンプリング後の同じスナップショット画像を示す図である。画像中の大半のテキストは、エイリアシングのため理解不能になっている。例えば、左上付近の単語"Ｆｉｌｅ"から"ｌ"が脱落し、意味をなさない文字"Ｆｉｅ"が残っている。
【００１１】
エイリアシングの影響は、ダウンサンプリングされた像において、画像を事前フィルタ処理して高周波数のコンテンツを減少させることにより減少させることができる。
【００１２】
図３１は、従来技術による図１の画素強度値をダウンサンプリングするための画素強度値を示す棒グラフで、図中の画像の横列は、図１の各々の画素を対で平均化し、両画素を平均値を含む単一画素で置き換えることにより生成されたものである。この方法により若干の中間空間周波数エネルギーが完全に保持されていることが認められる。しかしながら、高周波数の明暗変化は単一パルスに併合されている。
【００１３】
実際の像において、事前フィルタ処理はテキストのような高周波領域周辺に“ぼけ”または“曖昧”な外観を生み出す。
図３３は、図３の画像を、補間フィルタを用いて０.７８１の倍率でダウンサンプリングした画像を示す図である。テキストのコンテンツは全体的として理解できるが、テキストがぼけており、目を疲れさせる。
【００１４】
【発明が解決しようとする課題】
従来技術によるダウンサンプリング（縮小標本化）方法は、一般的に、自然なシーンを適当に標本化した画像を処理することを予定している。かような画像は通常、高周波情報エリアをほとんど含んでおらず、ボケをともなうダウンサンプリング作用を受け入れることができる。コンピュータグラフィックスは、自然なシーンと異なり、殆どの情報を高周波情報として伝えることができる。又、自然なシーンのディジタル化画像と異なり、コンピュータグラフィックスは、異なる解像度でグラフィック画像を再生成することによりダウンサンプリングを避けることができる。しかしながら、コンピュータグラフィックス画像は、何らかの理由により新しい解像度で再生成できない場合は（例えば、生成プログラムが入手できない，同一画像に対する２つの出力装置等）、ダウンサンプリングを採用しなければならない。従来技術によるダウンサンプリング方法は、コンピュータグラフィックス及び／又は高周波コンテンツの画像に、通常、視覚的に受け入れ難い結果をもたらす。
【００１５】
本発明は、上述のごとき実情に鑑みてなされたものであり、高空間周波数情報を維持しながらディジタル画像をダウンサンプリングする方法及びシステムを提供することをその目的とする。
【００１６】
グラフィックを含む画像の多くは、高周波と低周波領域、例えば、テキストと背景の両方を含んでいる。グラフィックの高周波領域はしばしば冗長画素を含み、同一強度又は同色の近隣の画素を多く持っている。本発明は、好ましくは高周波画像領域におけるダウンサンプリングを避けて、画像を非一様にダウンサンプリングすることで、高周波領域を保持する方法及びシステムを提供することをその目的とする。高周波領域をダウンサンプリングしなければならない場合、高周波冗長画素を除去するのが好ましい。非一様ダウンサンプリングは、エイリアシングを最少にしてぼけを発生させることなく、高空間周波領域を維持することが可能である。
【００１７】
【課題を解決するための手段】
本発明は、特にコンピュータグラフィックス像へのアプリケーションに関するディジタル画像のダウンサンプリング方法及びシステムであり、ディジタル画像を、除去パスを低い空間周波数領域に集中させることにより高い空間周波数の画像情報のエイリアシングが最小になる様に非均一にダウンサンプリングする。空間周波数の推定器は、画像を画素群毎に比較して分類する。パス発生器とパス得点評価器は、画像を通る潜在除去パスを追跡して得点で評価する。最大得点を得たパス（即ち、最小の歪みと最小のエイリアシングをもたらすパス）が画素除去のパスとして選択される。反復器は、所望数の画素行と列が除去される迄このプロセスを反復する。
【００１８】
本発明の第１の技術手段は、ディジタル画像上の隣接画素グループに対する空間周波数を計算し、一定値以上の高周波成分を含んでいる領域を抽出するステップと、前記ディジタル画像中の除去候補となる画素グループを含む縦又は横方向のパスである除去パスを、前記抽出した高周波成分を含んだ領域を迂回するように、上下又は左右若しくは対角に隣接した画素をつなげて、前記ディジタル画像を上下に縦断もしくは左右に横断するパスとし、前記除去パスを複数選択するステップと、前記１つの除去パスに含まれる画素グループを削除することにより、前記ディジタル画像の高周波成分が維持される程度を得点化した除去パスメトリックを除去パス毎に計算するステップと、前記複数選択した除去パスの中から最も高周波成分が維持される得点となる除去パスメトリックを有する除去パスを選択するステップと、該選択した除去パスに含まれる画素グループを除去するステップとを含んでなるディジタル画像のダウンサンプリング方法を特徴とする。
【００１９】
本発明の第２の技術手段は、第１の技術手段において、所望のダウンサンプリング率を達成するために設定したパス起点数で、前記ディジタル画像の１つのエッジに沿ってパス起点をほぼ均等に配分するステップをさらに含むことを特徴としたものである。
【００２０】
本発明の第３の技術手段は、第２の技術手段において、前記パス起点をほぼ均等に配分する前記ステップにおける前記パス起点を順序立てて配置するステップと、所与のパス起点に対応する除去パスを選択するステップをさらに含み、該除去パスを選択する該ステップは、それ以後に配置するパス起点用の除去パスを選択する以前に実行することを特徴としたものである。
【００２１】
本発明の第４の技術手段は、第３の技術手段において、前記パス起点を順序立てて配置する前記ステップは、先に選択された全てのパス起点との距離の和と前記画像のエッジからの距離の和が最も離れた位置にあるパス起点を、次のパス起点として選択することを特徴としたものである。
【００２３】
本発明の第５の技術手段は、第２の技術手段において、各パス起点毎に２つ又はそれ以上の除去パスのスタート位置候補の組みを生成するステップをさらに含むことを特徴としたものである。
【００２４】
本発明の第６の技術手段は、第２の技術手段において、前記除去パスメトリックは、現在選択されているパス起点により近い前記除去パスを優先選択することを特徴としたものである。
【００２５】
本発明の第７の技術手段は、第１の技術手段において、各々の除去パスメトリックは、前記除去パスが垂直方向に折れ曲がっている箇所に対し該除去パスにペナルティを課すことを特徴としたものである。
【００２６】
本発明の第８の技術手段は、第１の技術手段において、前記ディジタル画像中の拡張チェッカー盤模様の領域を位置決めするステップと、ダウンサンプリング前に、これらの領域を２つのチェッカー盤色の平均値である一様色に置き換えるステップとをさらに含むことを特徴としたものである。
【００２７】
本発明の第９の技術手段は、第１の技術手段において、前記画素を除去するステップは、該ステップ中にその画素の強度を少なくとも１つの近隣の画素の強度と平均化することを含むことを特徴としたものである。
【００２８】
本発明の第１０の技術手段は、第９の技術手段において、除去のためにマークされた前記画素とその近隣の画素が強度において著しく異なる場合にのみ前記平均化するステップを実行することを特徴としたものである。
【００３１】
本発明の第１１の技術手段は、ディジタル画像を入力として受信し、該ディジタル画像上の隣接画素グループに対する空間周波数推定値を計算し、一定値以上の高周波成分を含んでいる領域を抽出する空間周波数推定器と、前記ディジタル画像中の除去候補となる画素グループを含む縦又は横方向のパスである除去パスを、前記抽出した高周波成分を含んだ領域を迂回するように、上下又は左右若しくは対角に隣接した画素をつなげて、前記ディジタル画像を上下に縦断もしくは左右に横断するパスとし、前記除去パスを複数発生するパス候補発生器と、前記１つの除去パスに含まれる画素グループを削除することにより、前記ディジタル画像の高周波成分が維持される程度をパス得点として計算するパス得点評価器と、前記複数発生した除去パスの中から最も高周波成分が維持される得点を有する除去パスを選択して該除去パスに含まれる画素グループを除去し、ダウンサンプルリングしたディジタル画像を生成する画素除去器とを有するディジタル画像のダウンサンプリングシステムを特徴とする。
【００３２】
本発明の第１２の技術手段は、第１１の技術手段において、前記画素除去器により得られた前記ダウンサンプリングされたディジタル画像を、原ディジタル画像から所望数の除去パスが当該システムによって除去されるまで、当該システムにフィードバックする反復器をさらに含むことを特徴としたものである。
【００３３】
本発明の第１３の技術手段は、第１１の技術手段において、前記パス候補発生器のために前記ディジタル画像中のパス起点位置を選択するパス起点位置発生器をさらに含むことを特徴としたものである。
【００３４】
【発明の実施の形態】
本発明の一実施形態において、ディジタル画像のダウンサンプリング方法を開示する。最も簡略して云えば、この方法は、画像の相対的に低い空間周波領域を通るパスに偏した除去パスメトリックを用いて画像を通る除去パスを選択し、その除去パスに沿って存在する画素を除去することより成る。選択されたパスに沿った幾つかの画素が相対的に高い空間周波数を有している場合、画像のその領域を画素除去前にローパスフィルタで任意処理することができる。
【００３５】
詳述すれば、この方法は、次のステップより成る。本方法は、ディジタル画像上の隣接画素グループ毎に空間周波数を計算する。次に、空間周波数を用いて、ディジタル画像を通る異なる潜在的な除去パスに対して各々の得点を計算する。潜在パス中から最も好ましい得点を持つ除去パスを選択し、そのパスに沿って画素を除去する。好ましくは、この方法を所望のダウンサンプリングに達するまで繰り返す。
【００３６】
幾つかの要因が潜在的な除去パスの得点に好適に寄与する。最初に、パスに沿う平行な高空間周波数エッジが無ければ、そのパスに大きな得点を加える。パスを直角に横断する高空間周波数エッジが相対的に少ないときもまたそのパスへの加点が大きい。直線パスは、曲がったパスより一般に高い得点を得る。所望のパス位置に近接するパスもまたパスとして好ましい。
【００３７】
本発明の他の実施態様では、ディジタル画像をダウンサンプリングするためのシステムを開示する。このシステムは、ディジタル画像を入力として受信し、ディジタル画像上の隣接画素グループにつき空間周波数の推定値を計算する空間周波数推定器を含んでいる。このシステムは、又、画像を通る潜在的な画素除去パスを生成するパス発生器を含む。パス得点器は、潜在的な画素除去パスに対するパス得点を、少なくとも空間周波数推定値の一部に基づき計算し、画素除去器は、潜在的な除去パスのうちで最も望ましい除去パスメトリックを持つ除去パスを選択し、そのパスに沿って存在する画素を除去することにより、ディジタル画像の画素サイズを削減する。このシステムは、反復するこなくダウンサンプリングするか、或いは、１回で１パスを除去し反復することができる。本システムは、水平，垂直または水平垂直の両方向にダウンサンプリングすることができる。
【００３８】
図１は、仮想の画像の横列に沿った画素強度を示す棒グラフで、これを参照し、基本的なレベルについて記述する。この画像を倍率２で一様にダウンサンプリングすると、縦列３９〜４４は、エイリアシング又はボケが生じ認識できなくなり、縦列１８〜３８は最高空間周波数の２倍でクリティカルにサンプル化される。
【００３９】
図２は、本発明の一実施形態により、図１の画素強度値をダウンサンプリングした画素強度値を示す棒グラフである。本発明は、かような問題の発生を、非一様ダウンサンプリングのスキームにより回避し、例えば図２の棒グラフに示すような結果を得ることができる。図２において特記すべき点は、このダウンサンプリング法が、最高空間周波数が存在した原縦列３９〜４３から画素を除去するのを避け、その代わりに付近のより低い周波数画素を除去していることである。このために、原縦列に関しスケールの歪みが生じる。しかし、高周波数情報は残り、画像オブジェクトの相対サイズの美的価値に関して、おそらく存在した情報のみが失われている。
【００４０】
（非一様ダウンサンプリングの効果）
図３は、コンピュータグラフィックスの原画像を示す図で、図４は、本発明の一実施形態により図３のコンピュータグラフィックスの原画像をダウンサンプリングした結果を示す図である。
【００４１】
図５は、コンピュータグラフィックス画像中の空間周波数の可能な分布の１例を示す図である。本発明の効果は、図５の原画像マップを調べることにより容易に理解できよう。この画像マップは、グラフィック画像を類似空間周波数の領域グループとして表現している。背景領域（例えば３０ａ，３０ｂ，３０ｃ）は、隣接画素間に殆ど強度差がない。テクスチャ領域（例えば３２ａ〜３２ｆ）は隣接画素間の強度に若干の差があるが、これらは、正規のディザパターンであり、高周波情報を伝えることを意味しない。高周波領域（例えば３４ａ〜３４ｊ）はテキストと高コントラストグラフィックスより成る。
【００４２】
図６は、本発明の方法による図５の画像に対するダウンサンプリングした結果を示す図で、図５の画像マップのダウンサンプルバージョンとして可能な１つの空間周波数マップを示している。画像全体の高さと幅は３０％だけ縮小されているが、高周波数領域３４ａ〜３４ｊのサイズは縮小されていない。テクスチャ領域３２ａ〜３２ｆのサイズは比例して縮小されている。背景領域３０ａ〜３０ｃは、不均衡に変化した形状を有している。ダウンサンプリングは、要するに、画像上の空間周波数オブジェクトを各々異なるサイズに変えて“再配置”することである。
【００４３】
（除去パス候補のシードと追跡）
図７は、図５の空間周波数分布に対して選択された除去パスを示す図で、図５の空間周波数マップ３５の複製を用いて、本発明の一実施形態の動作を説明するための図である。マップ３５を上から下にトラバースする１５本のパスが示されている。これらのパスは画像の縦列に沿って等間隔に並んでいる。各パスは、背景及びテクスチャ領域を通るようにスタート点の縦列またはシード縦列に留まるのが好ましい。しかしながら、高周波数領域に遭遇した時は、パスはその高周波領域を通らずに迂回する方が望ましい。かように、パス７，１５，１は背景を通り左に折れ、パス１０，６は背景を通り右に折れ、領域３４ｄ〜３４ｊを迂回するのが好ましい。これらのパスに沿って画素を除去することにより、図６のマップ３６を得るダウンサンプリングのプロセスの始まりとなる。
【００４４】
図７は、又、除去パスを計算するための好ましいシーケンスを示している。画像を一方から他方に横切り順次パスを発生させる代わりに、距離メトリックを用いてパス発生シーケンスを決定する。距離メトリックは、新しいパス毎にスタート位置として、全ての先発縦列の組みから最大距離に位置し、第１仮想縦列から入力画像の最左端縦列の左α縦列、第２仮想縦列から入力画像の最右端縦列の右α縦列の距離に位置する縦列を選択する。数αは、シード縦列間、最左端パスと画像の最左端縦列との間、及び最右端パスと画像の最右端縦列との間の等間隔に対して各々１である。次のスタート縦列Ｃnの位置は下記のような関数式を最小にする縦列として数学的に表現できる。
【００４５】
【数１】
0004363728.tif 000002
【００４６】
上式において、入力画像は、０からＮ−１まで番号付けしたＮ個の縦列を有する。
かように、第１スタート縦列Ｃ0は、中央画像位置（図７中のパス１に該当する）であり、第２及び第３スタート縦列Ｃ1及びＣ2は、１／４画像位置（図１１中のパス２とパス３に該当する）にある。２つの縦列が同じメトリックを示す場合は、何れかを次のシード縦列とすることができる。
【００４７】
この順序付けアルゴリズムは、近くのスタート縦列が相対的に近くの領域をトラバースさせたのちに、その領域をトラバースできなくさせる多数の遠方スタート縦列によりその領域がトラバースされるという点で好適である。
【００４８】
図８は、従来技術の方法における、テキストのダウンサンプリングによるエイリアシングの影響を示す図である。本発明の一実施形態の動作を、単語"ＦＩＬＥ"のビットマップ表現を含む２４×９画素の、図８（Ａ）の単純なグラフィック画像を参照し説明する。図８（Ａ）は、参考のために、画像幅を１／３だけ縮小する場合、従来技術の除去アルゴリズムにより除去される縦列１〜８を示している。図８（Ｂ）は、従来技術でダウンサンプリングされた画像４０を示している。文字"Ｆ"，"Ｌ"及び"Ｅ"は幸運な文字間隔により、視覚的に受容できるようにダウンサンプリングされたが、文字"Ｉ"は画像から完全に消去され、文字"Ｌ"と"Ｅ"がくっついてしまっている。文字"Ｉ"を保存する他の可能なスタート縦列を選択すると、エイリアシングの悪影響が強まる。図８（Ｃ）は、除去縦列を図８（Ａ）の縦列から１縦列右にシフトさせてダウンサンプルされた画像４１を示している。
【００４９】
図９は、本発明の一実施形態の方法による同一テキストのダウンサンプリングを示す図である。図９（Ａ）は、本発明の一実施態様により計算された除去パスを表示した画像３８を示している。これらのパスは、図８（Ａ）の従来技術による除去縦列位置と同じ位置にシードされている。しかしながら、本発明の場合は、パスは高周波数領域を避けるために原位置からシフトすることができる。かようにして、これらのパスは、画像３８の低周波数領域に向かって、特に、文字の垂直部分に関連する難しい領域を避けて通る。図９（Ｂ）は、このプロセスで生成されてダウンサンプルされた画像４２を示している。各文字は、隣の文字からの間隔が確保され明確に判読できる。
【００５０】
（ダウンサンプリングシステム）
図１０は、本発明の一実施形態のダウンサンプリング方法における幾つかのステップを示す図で、図１１は、本発明の一実施形態によるダウンサンプリングシステムを説明するための図である。本発明の一実施形態の順次動作を図１０（Ａ）に示す画像３８を用いて説明する。この実施形態では、図１１に示すように、空間周波数の推定，パス候補の生成，パス候補のスコア計算，及び画素の除去の４つの基本的ダウンサンプリング機能の動作が用いられる。少なくとも後の３ステップは循環して実行されるのが好ましく、即ち、第１除去パスを選択し除去してから第２除去パスを処理する。このダウンサンプリングシステムにおいては、入力画像１を、直接及び空間周波数推定器２を通した空間周波数マップ３として、反復器４へ送ることによりダウンサンプリングされる。ダウンサンプリングの動作としては、シード縦列発生器５で発生させたシード縦列をもとにパス候補発生器６でパス候補を発生させ、パス得点評価器７にて各候補パスをスコアリングし、その得点（スコア）によって除去するパスを決めて（最小の歪みと最小のエイリアシングをもたらすパスを除去する）、画素除去器８により、そのパスを除去する、といった動作を反復器４により繰り返して、ダウンサンプル画像９を得る。全ての機能ブロックは、入力画像データへのアクセスと中間画像蓄積メモリと画像データの出力とを有するプログラム可能な信号処理装置に実装するのが好ましい。
【００５１】
（空間周波数の推定）
本発明は、非一様除去パスを生成するための空間周波数の測定に依拠する。最も簡単な形態において、本発明はＭ横列×Ｎ縦列の入力画像Ｉ（Ｍ，Ｎ）上の隣接画素対の間の強度差を検討する。例えば、垂直エッジの空間周波数画像Ｖ（Ｍ，Ｎ−１）と水平エッジの空間周波数画像Ｈ（Ｍ，Ｎ−１）は、各々次式で計算できる。
【００５２】
Ｖ（ｉ，ｊ）＝｜Ｉ（ｉ，ｊ）−Ｉ（ｉ，ｊ＋１）｜
Ｈ（ｉ，ｊ）＝｜Ｉ（ｉ，ｊ）−Ｉ（ｉ＋１，ｊ）｜
【００５３】
入力画像が個別の色成分（例えば、赤，緑，青）で表示される色強度を含んでいる場合は、各色は個別に強度差を計算し、例えば下記のように差分結果を合計するのが好ましい。
【００５４】
Ｖ（ｉ，ｊ）＝｜ＩR（ｉ，ｊ）−ＩR（ｉ，ｊ＋１）｜＋｜ＩG（ｉ，ｊ）−ＩG（ｉ，ｊ＋１）｜＋｜ＩB（ｉ，ｊ）−ＩB（ｉ，ｊ＋１）｜
【００５５】
画像Ｖ（ｉ，ｊ）は除去する画素の縦列を選択するのに役立つ情報を提供する。特定の座標ｉ，ｊのＶ（ｉ，ｊ）が小さいかゼロであれば、画素Ｉ（ｉ，ｊ）とＩ（ｉ，ｊ＋１）は同等又は近似である。反対に、Ｖ（ｉ，ｊ）が大きい場合、２つの画素間にはかなり高い空間周波数情報が存在する。画素除去の決定はＶ（ｉ，ｊ）の生の測定値に基づくが、一般的には、しきい値Ｖ（ｉ，ｊ）を低い値、例えば２５６のグレイシェードの５レベルで判定し、しきい値を越えるものは全て高周波とすれば十分である。Ｖ（ｉ，ｊ）の演算とグレイシェード５のしきい値を画像３８に適用し、図１０（Ｂ）の分類図を得る。
【００５６】
図１０（Ｂ）は、しきい値処理後の画像３８の垂直エッジの空間周波数コンテンツを示している。しきい値マップ４４は、領域４６のように影を付けた高周波数領域と、影を付けられていない低周波領域を示している。又、マップ４４は、矢尻で画像３８内の水平エッジ位置を示している。
【００５７】
画像３８は、マップ４４に示された情報に基づき分割できる。分割により、類似属性を持つ近隣の画素をグループに纏める。本発明の目的のために、この分割により、垂直及び水平の両方向における空間周波数のしきい値より低い、類似強度を有する近隣の画素を連結する。
【００５８】
この特定の実施形態における分割は、図１０（Ｃ）の分割マップ４８に示すように、低周波数情報の矩形ブロックに画素をグループ分けする。マップ４８中の影付けしていない矩形ブロックは各々、何れの側にも高周波数エッジを有しない画素のみを含んでいる。かような画素は、トリプレット（横１列に並んだ３つの類似画素）の１部として定義する。マップ４８の中間影付ブロックは、トリプレットの一端画素又はダブレット（横１列に並んだ２つの類似画素）の一部の何れかを含む。これらの画素は、片側に低周波数情報を他方に高周波数情報を有している。最後に、マップ４８中の完全に影付したブロックは両側に高周波数情報を有する画素を示している。
【００５９】
（パスの生成）
パス候補の生成は、除去すべき１パスを選択する度ごとに複数のパス候補を発生させることが好ましい。これらのパスの１つをシード縦列の順序から得られた次のシード縦列上でスタートさせる。他のパスは、シード縦列の近くの縦列上でスタートさせる。パス総数はスタートパス幅の指標によって定められる。例えば、スタートパスを各々、７本の（シード縦列の各側に３本とシード縦列）固定縦列数として始めることもできる。スタートパス幅は、シード縦列の間隔に応じて変えることができる（例えば、スタートパスをシード縦列の間隔に略等しく設定すれば、殆ど全ての縦列を幾つかの点において潜在的除去対象であるかどうか検査することができる）。或いは、スタートパス幅を、例えば、第１幅が不十分なパス候補しか形成されない場合、探索を第２幅に拡張するように、動的に変化させても良い。
【００６０】
パス候補用スタート縦列が決定すれば、分割マップ４８を用いてパス候補を発生させる。パス候補は、マップ４８の最上横列中の予定縦列からスタートする。パスの次の横列への移動は連続するように、即ち、パスの現在位置をＩ（ｉ，ｊ）とすると、Ｉ（ｉ＋１，ｊ−１），Ｉ（ｉ＋１，ｊ）またはＩ（ｉ＋１，ｊ＋１）の画素へのみ移行できる。移行すべき正しい画素は下記の規則に従って決定される。
【００６１】
１．下方画素がトリプレットブロックの一部であれば、パスの移動は縦列を移動することなくそのブロックの終端まで下方に移行する（但し、画素が現在、スタート列上でなければ次の規則２ａを用いてトリプレットブロック内でシフトできる）。
２．上記以外で、且つ、下記の条件の何れでもない場合、パスは真下の画素に移行する。
ａ．対角線画素の１つがパスのスタート縦列により近接しており、トリプレットブロックの一部である（この場合、パスはその画素の方に移行する）。
ｂ．真下の画素がダブレットの一部でなく、対角線画素がタブレットの一部である場合（この場合、パスはその画素の方に移行する）。もし、両対角線画素が異なるダブレットに属している場合は、スタート列に近い対角線画素に移行する方を選ぶ。
【００６２】
これらの規則は、パスの直線性と冗長画素の除去に関する２つの判定基準を支持する。パスの直線性による選択は、現パスでは高周波画素を消すことになるが隣接パスならば高周波画素を消さずにすむか、或いは、パスがトリプレットブロックを通りスタート縦列の方向にその進路を修正するかの何れかの場合にのみ生じる。冗長画素は、何時でも可能な時に、除去すべきトリプレット及びダブレット画素を選択することにより除去することができる。
【００６３】
その他の規則も可能である。例えば、スタートパス横列への復帰選択を任意無効とし直線除去パスを選ぶことができる。除去パス縦列の境界をスタート縦列候補の境界に対し任意に拡張又は収縮させることができる。除去パスを予定又は計算された強度の画素上に残すように任意選択するか、或いは、非隣接画素に移動させることができる。除去パスを予見して、現列より先の画素に基づき決定を下すことも可能である。
【００６４】
（パスの得点評価）
好適な実施形態は複数のパス候補を比較するので、比較メトリックが用いられる。このプロセスを、パスの得点評価と名付け、パスの属性に基づきパスの品質を特徴づける。パスの属性は、通常、２つの種類に、即ち、パス自身の形状の質を測定する属性と除去パス中の画素の空間周波数コンテンツを反映する属性とに分類できる。
【００６５】
幾つかのパス属性は、パス自身の形状に基づく。例えば、シード縦列からパススタート縦列迄の距離に基づく、絶対的パス移動のペナルティは、シード縦列への近接が好ましいことを表現するために課すことができる。又、相対的パス移動のペナルティを、パスが縦列を変える度に課すことができる。
【００６６】
その他のパス属性は、パスに沿った画素の空間周波数コンテンツに基づいている。例えば、パスの得点評価では、パスに垂直に測定した低い空間周波数コンテンツを持つ画素の方を選択すべきである。パスの得点評価は、パスと同一方向の空間周波数コンテンツを反映することができ、他の全てが同じであれば、両方向の空間周波数が低い方を選ぶべきである。この得点値は、色変化のペナルティに反映させることができ、即ち、パスに沿った色変化がある場合にペナルティを課すことができる。これは、又、共通色の拡張したトリプレットブロックに与える色の連続性の得点に反映させることができる。色変化のペナルティに対し、色の連続性に得点を与える利点は、どの特定パスについても個別に計算できることである。
【００６７】
これらのパス属性は各々、相対的な重要性を調整するように重み付けることができる。図示の形態では、下記の重み付けを採用している。
絶対パス移動のペナルティ：移動縦列当たり１単位
相対パス移動のペナルティ：移動縦列当たり１単位
空間周波数得点：プリセット最大値（画素当たり０.０６２５サイクルより少ない空間周波数を示す６単位）又は隣接低周波数画素の数から２を減じた値のどちらか小さい値。
色変化のペナルティ：領域当たり１単位
色連続性の得点：色連続の各隣接列に対し１単位
【００６８】
空間周波数の得点、色変化のペナルティ及び色連続性の得点は、任意特定のパスから独立して推定できるのでパス得点を迅速に計算できる。例えば、図１０（Ｃ）のマップ４８は画像の領域に対する複合領域得点を示している。領域５０は、８個を越える隣接低周波数画素を有しており、６の最大空間周波数得点を獲得する。又、１列の色の連続性を有しているので、色の連続性の得点１を獲得する。これらの２種類の得点を１トリプレットブロック毎に乗算し、次に、領域当たり１単位の色変化のペナルティを差し引き、総得点（６×１−１＝５）を計算する。同様に、領域５２は、同様の計算（５×５−１）により複合領域得点２４を得る。
【００６９】
ダブレット画素と高周波画素はグループにしない。各ダブレット画素は、空間周波数得点０、色連続性得点１及び色変化のペナルティ１で、（０×１−１＝−１）の総得点を得る。各高周波数画素は、空間周波数得点−１色連続性得点１及び色変化のペナルティ１で、（−１×１−１＝−２）の総得点を得る。
【００７０】
（実施例）
図１２は、本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。図１２（Ａ）及び図１２（Ｂ）を先ず参照し、図９（Ａ）の全部で８本の除去パスに対する前述の実施形態の動作について説明する。本実施例では、探索パス幅を十分大きく設定し、どの縦列も可能なスタート縦列と見なせるようにする。但し、関連する全ての考えられるパスを示してはいないが、発明のコンテンツを理解するのに十分なパスを示している。
【００７１】
図１２（Ａ）中のパス候補には、"シード"及び"ａ"乃至"ｅ"の文字を付けて識別している。各パスは最初に、シード縦列への近接度に基づく絶対パス移動ペナルティ、即ち、シードパスは０，パスｂは１、パスａとｃは２，パスｄは３，パスｅは６のペナルティを受ける。各パスは、次に、上から下に追跡され、画像を通過する間に領域得点が加算されて行く。パス移行規則によりパスの縦列変更が生じる（シードパスが文字“Ｌ”と“Ｅ”の間の高周波数画素を避けるために６番目と７番目の列上を通らない）場合、相対移動ペナルティが各縦列変更時に課せられる。かように、原画像中の文字"Ｅ"の左に沿ったシード縦列は、５つのダブレットと４つのトリプレット画素を使用するパスを生成する。シードパスの得点は、パスの下に示してあるように、移動ペナルティ（２縦列移動によるペナルティ−２）と領域得点（５−１−１−１−１−１＋５＋１１）の複合で１４の総得点となる。
【００７２】
対照的に、文字"Ｅ"の右の２画素に位置するパス"ｅ"は、直線であり、トリプレットブロックからの画素のみを用いて、シード縦列からの６縦列のマイナス点にも拘らず、３９のパス得点を得る。かように、パス"ｅ"は最良のパス得点を得て、そのパスの画素が除去画素としてマークされる。
【００７３】
最良得点のパスを認定した後、そのパスに沿った画素を除去する。好適な除去方法は、空間周波数に依存する。除去するためにマークされた画素が、トリプレット画素である場合は、単純に除去する。除去するためにマークされた画素が、タブレット画素の一部である場合は、単純に除去するか、又は、その左右の近隣の画素に平均化してから除去することができる（近隣の画素の１つは類似であるので、平均化によりその近隣の画素の強度に明らかに認められる変化をもたらさないことが肝要である）。除去に先立つ平均化は、除去のためにマークされたどの高周波周波数画素に対しても好ましい。平均化は、例えば、近隣の画素の強度の３分の２を除去画素の強度の３分の１に加えることにより本質的に新しい画素値を形成する補間を用いる。
【００７４】
図１２（Ｂ）はパス"ｅ"を除去後の画像を示している。
図１３は、本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。図１３（Ａ）は、パス"ｅ"を除去後の更新された分割マップを示している。領域５２はサイズが縮小されており、その領域得点は再計算される。この領域は、パス"ｅ"を除去後もトリプレット領域であるので、この除去は領域５２の左の領域には影響を及ぼさない。
【００７５】
図１３（Ａ）は、第２シード用の４つのパス候補を示している。シード縦列は画像の文字"Ｉ"と整列しており、縦列を除去するには特に不適当な選択肢である。このシードパスは"Ｉ"の最上画素を通り、次に、"Ｆ"と"Ｉ"の間のダブレット空間に移動する。パス"ｂ"は文字"Ｌ"の水平部分を通り、かなり高い得点を得る。背景領域を通るパス"ｃ"は最高得点を獲得したので（パス"ｃ"は、より小さい探索パス幅では試験しなかった）、同パスが除去され図１３（Ｂ）の画像が生成される。
【００７６】
図１４及び図１５は、本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。図１４（Ａ）及び図１４（Ｂ）は、高得点を生成して後続する次のシード縦列を示している。図１５（Ａ）は、領域５２の更新された領域得点を示している。図１５（Ａ）のシード縦列は、文字"Ｆ"の左真横に当たる。強度画像においてシード縦列は縦列"ａ"と同じ値を有しているが、シードパスが１つのエッジに沿って高い周波数画素を有しているために、パス"ａ"の方がより良いメトリックを生成する。図１５（Ｂ）は、パス"ａ"を除去した後の画像を示している。パス"ａ"の除去により図１５（Ａ）のトリプレットブロック５４が破壊されるので、ブロック５４に当接する領域は、分割マップ中で更新されねばならない。
【００７７】
図１６は、本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。更新されたマップは、左側に沿って高周波数領域５６を含んでいる。次のシード縦列は、図１６（Ａ）の文字"Ｌ"の垂直部分と整列しており、右側に移動すればこれを避けられるので、"Ｌ"の水平部分から１画素を除去する隣の直線パス"ａ"の方が選択される。図１６（Ｂ）は、パス"ａ"を除去した後の画像を示している。
【００７８】
図１７は、本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。図１７（Ａ）のシード縦列は、再び背景画素と整列しており、高得点を得て、除去されて図１７（Ｂ）の画像が生成される。
【００７９】
図１８は、本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。図１８（Ａ）のシード縦列は、文字"Ｆ"の中央に整列している。右又は左に移動すると劣った除去パスになることは明らかであるので、このシード縦列は最高の結果を得る。図１８（Ｂ）は、このシード縦列を除去した後の画像を示している。
【００８０】
図１９は、本発明の一実施形態による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。最後のシード縦列を図１９（Ａ）に示す。このシード縦列と縦列"ａ"は、同一の画素値を含んでいるが、縦列"ａ"の方が、シード縦列よりも、高周波エッジから離れているので除去パスとして選択される。図１９（Ｂ）は、パス"ａ"を除去した後の画像を示している。
【００８１】
（別の実施形態）
好適な一実施形態において、パスの直線性の制約条件は、拡張した隣接背景領域の一部である領域に対して緩和することができる。パスは動き横列当たり１縦列以下のシフトを許容されるのが好ましい。しかしながら、パスが大きい背景領域に及び大きい背景領域から背景を通って移動することができるならば、そのようなパスは、たとえ当初の探索領域から一度に複数縦列シフトしたとしても、選択する方がよい。隣接背景領域は、パス生成前に予め連結しておくことができる。
【００８２】
背景領域は、最小サイズ基準に一致するトリプレット領域として定義できる。現在のパスを高周波エッジを横断するパスを通ることなくかような領域に接続できれば、そのパスは、高周波エッジを横断しなければならない局所パスよりも好ましい。
【００８３】
図２０は、背景パスを選択する一実施形態による結果を示す図で、上に重ねた暗い除去パスが目に見えるように薄れさせた画像からの抜粋を示している。パス７０は、３つの大きなジョグを示しており、除去パスの１つに対するパス生成が高周波領域周辺の背景に続いている。
【００８４】
本発明の他の改良は、テクスチャを高周波数情報から区別させることである。幾つかのコンピュータグラフィックスのアプリケーションは、チェッカー盤模様に撒き散らした２色を用いて第３の色を模擬生成している。これらは、高周波数エッジとして現れるが、人間の目により、単一色に平均化または“混合”される。本発明は、好ましくは、拡張したチェッカー盤模様をテクスチャとして認識し、かような領域を、背景領域と同様に処理する。これを実現する１つの方法は、画像を予備処理し、全てのチェッカー盤の画素を、チェッカー盤中の２色の平均である共通色で置き換えることである。別の方法では、かような領域をパス生成中に認識する。
【００８５】
通常、画像は縦列及び横列の両方ともでダウンサンプリングされる。本発明によるダウンサンプリングシステムは、最初に縦列をその次に横列を、或いはその逆順で処理することができる。１画像方向にダウンサンプラを走らせ、結果の画像を転置させ、ダウンサンプラを再びその画像方向に走らせ、結果の画像を再び転置させることにより、符号の複製を大幅に避けるシステムが実現できる。
【００８６】
図２１は、図３のコンピュータグラフィックス画像に対し、本発明の一実施形態に対して選択された除去パスと出力結果を示す図である。図２１（Ａ）は、全ての選択した横列の除去パスを上に重ねた画像を示す図である。この画像は、除去パスが明瞭に見えるように薄れさせてある。図２１（Ｂ）は、これらのパスに沿った画素を（可能な場合は平均化して）除去した後の中間画像を示している。
【００８７】
図２２は、図３のコンピュータグラフィックス画像に対し、本発明の一実施形態に対して選択された除去パスと出力結果を示す図である。図２２（Ａ）は、全ての選択した縦列の除去パスを上に重ねて薄れさせた図２１（Ｂ）の中間画像を示している。図２２（Ｂ）は、ダウンサンプリングした最終画像を示している。
【００８８】
個別の実装は多様に変化させることができる。パスの得点パラメータと結合技法は、個別の選択に合わせて調整することができる。アルゴリズムは、固定しきい値でなく適応しきい値を用いることができる。例えば、高周波数エッジ対低周波数エッジのしきい値は、画像の統計値に基づき決定できる。別例では、複数のしきい値（又は、生の差分）を用いることができる。例えば、１つのトリプレットブロックと共に、移行できる他のトリプレットブロックを示すことによりパスの部分を予め生成することができる。
【００８９】
背景領域の場合、領域が既に縮小された量を追跡し、既に大きく縮小された領域をさらに歪ませるパスにペナルティを課すメトリックを含ませることにより歪みを制限することができる。
【００９０】
（ディジタル画像をダウンサンプリングするプロセス）
本発明のディジタル画像をダウンサンプリングするプロセスを、図２３乃至図２９のフロー図に沿って説明する。
図２３は、本発明におけるディジタル画像のダウンサンプリング方法の一実施形態を説明するためのフロー図である。最初に、ディジタル画像をディジタル画像上の隣接画素グループに対する空間周波数を計算する（ステップＳ１）。次に、ディジタル画像を通る少なくとも２本の潜在的除去パスの各々についてステップＳ１の空間周波数計算ステップの結果に少なくとも部分的に基づき除去パスメトリックを計算し（ステップＳ２）、潜在的除去パスから最も望ましい除去パスメトリックを有する除去パスを選択し（ステップＳ３）、その除去パスに沿って画素を除去する（ステップＳ４）。
【００９１】
本実施形態において、ステップＳ２を以下のステップＳ５（図示せず）で代えることができる。ステップＳ５においては、ディジタル画像の少なくとも２本の潜在的除去パスの各々についてステップＳ１の空間周波数計算ステップの結果に少なくとも部分的に基づく除去パスメトリックを、各々、パスの方向に垂直な運動に対してそのパスを減点させる規則に基づいて計算する。
【００９２】
また、本実施形態において、ステップＳ４を以下のステップＳ６（図示せず）に代えることができる。ステップＳ６においては、除去パスに沿った除去ピクセルに対して、除去ステップ中にその画素の強度を少なくとも１つの隣接画素の強度に平均化する。
【００９３】
さらに、本実施形態において、ステップＳ６を以下のステップＳ７（図示せず）に代えることができる。ステップＳ７で、除去のためにマークされた画素とその隣接画素が強度において著しく異なる場合にのみ除去パスに沿った除去ピクセルに対して、除去ステップ中にピクセルの強度の平均化ステップを実行する。
【００９４】
図２４は、本発明におけるディジタル画像のダウンサンプリング方法の他の実施形態を説明するためのフロー図である。まず、ディジタル画像の隣接画素のグループに対して空間周波数を計算する（ステップＳ１１）。次に、所望のダウンサンプリング率を達成するために設定したパスシード数で、ディジタル画像の１つのエッジに沿ってパスシードをほぼ均等に分配する（ステップＳ１２）。続いて、ディジタル画像を通る少なくとも２つの除去する可能性を持つ除去パスのそれぞれに対して、ステップＳ１１の結果に少なくとも一部に基づいて除去パスメトリックを計算し（ステップＳ１３）、除去する可能性を持つ除去パス中から、最も望ましい除去パスメトリックを有する除去パスを選択する（ステップＳ１４）。最後に、その除去パスに沿って除去画素を除去する（ステップＳ１５）。
【００９５】
本実施形態において、ステップＳ１３をステップＳ１６（図示せず）に代えることができる。ステップＳ１６においては、ディジタル画像を通る少なくとも２つの除去する可能性を持つ除去パスのそれぞれに対して、ステップＳ１１の結果に少なくとも一部に基づいて除去パスメトリックを、現在選択されているパスシードにより近い除去パスを優先選択する規則に従って計算する。
【００９６】
図２５は、本発明におけるディジタル画像のダウンサンプリング方法の他の実施形態を説明するためのフロー図である。まず、ディジタル画像上の隣接画素のグループに対して空間周波数を計算する（ステップＳ２１）。次に、所望のダウンサンプリング率を達成するために設定したパスシード数でディジタル画像の１つのエッジに沿ってパスシードをほぼ均等に分配し（ステップＳ２２）、シードシーケンス中のパスシードを配置してシーケンス中に所与のシードに該当する除去パスをシーケンス中の後のシード用の除去パスを選択する以前に選択する（ステップＳ２３）。続いて、ディジタル画像を通る少なくとも２本の除去する可能性を持つ除去パスメトリックの各々に対して、ステップＳ２１の結果に少なくとも一部に基づいて除去パスメトリックを計算する（ステップＳ２４）。最後に、除去する可能性を持つ除去パス中からもっとも望ましい除去パスメトリックを有する除去パスを選択し（ステップＳ２５）、その除去パスに沿って画素を除去する（ステップＳ２６）。
【００９７】
本実施形態は、ステップＳ２３を以下のステップＳ２７（図示せず）で代えることができる。ステップＳ２７においては、シードシーケンス中のパスシードを配置し、そのシーケンス中に所与のシードに対応する除去パスを、そのシーケンス中の後のシード用の除去パスを選択する以前に選択する。このステップ２７においては、シードシーケンス中のパスシードを配置することは、全ての先に選択されたパスシードと画像エッジから最大距離にある全ての先に選択されていないパスシードから、１つのパスシードを、シードシーケンスの次のシードとして再帰的に選択することを含んでいる。
【００９８】
本実施形態では、ステップＳ２７をステップＳ２８（図示せず）に代えることができる。ステップＳ２８においては、ステップ２７において最大距離を決定するための距離の測定値をディジタル画像中の２点間の画素距離の逆数としている。
【００９９】
図２６は、本発明におけるディジタル画像のダウンサンプリング方法の他の実施形態を説明するためのフロー図である。最初に、ディジタル画像の隣接画素のグループに対して空間周波数を計算する（ステップＳ３１）。次に、所望のダウンサンプリング率を達成するために設定したパスシード数でディジタル画像の１つのエッジに沿ってパスシードをほぼ均等に分配し（ステップＳ３２）、各パスシード毎に２つ又はそれ以上の除去パススタート位置候補の組みを生成する（ステップＳ３３）。続いて、ディジタル画像を通る少なくとも２本の除去する可能性を持つ除去パスの各々に対して、ステップＳ３１の結果の少なくとも一部に基づいて除去パスメトリックを計算し（ステップＳ３４）、除去する可能性をもつ除去パスから最も望ましい除去パスメトリックを有する除去パスを選択する（ステップＳ３５）。最後に、除去パスに沿って画素を除去する（ステップＳ３６）。
【０１００】
図２７は、本発明におけるディジタル画像のダウンサンプリング方法の他の実施形態を説明するためのフロー図である。まず、ディジタル画像の隣接画素のグループに対して空間周波数を計算し（ステップＳ４１）、ステップＳ４１の結果の少なくとも一部に基づく除去パスメトリックを計算する（ステップＳ４２）。次に、その除去する可能性をもつ除去パスから最も望ましい除去パスメトリックを有する除去パスを選択し（ステップＳ４３）、位置に関し２つ以上の除去経路候補のセットを生成し、ディジタル画像中の拡張チェッカー盤模様領域を位置決めし、これらの領域を２つのチェッカー盤カラーの平均値である均一色とダウンサンプリング前に交換する（ステップＳ４４）。最後に、除去パスに沿って画素を除去する（ステップ４５）。
【０１０１】
図２８は、本発明におけるディジタル画像のダウンサンプリング方法の他の実施形態を説明するためのフロー図である。最初に、ディジタル画像の隣接画素のグループに対して空間周波数を計算する（ステップＳ５１）。次に、所望のダウンサンプリング率を達成するために設定したパスシード数でディジタル画像の１つのエッジに沿ってパスシードをほぼ均等に分配し（ステップＳ５２）、そのパスシード中から先に選択されていないシードを再帰的に配置（選択）する（ステップＳ５３）。続いて、そのシードに相当する除去パスのスタート位置に関し２つ以上の除去経路候補のセットを生成し（ステップＳ５４）、近接する高周波数画素より低周波数画素の方を選択する除去パス候補により前記セット中の各スタート位置毎にディジタル画像を通る除去パス候補をトラバースし（ステップＳ５５）、ステップ５１の結果に少なくとも部分的に基づいて各除去パス候補毎に除去パスメトリックを計算し（ステップＳ５６）、さらに、それらの除去パス候補中から最も望ましい除去パスメトリックを有する除去パスを選択する（ステップ５７）。最後に、その除去パスに沿って画素を除去する（ステップＳ５８）。
【０１０２】
図２９は、本発明におけるディジタル画像のダウンサンプリング方法の他の実施形態を説明するためのフロー図である。最初に、画像の相対的に低い空間周波数を選択する除去パスメトリックを用いて若干数の除去パス候補から画像を通る除去パスを選択し（ステップＳ６１）、次に、その除去パスに沿って存在する画素を除去する（ステップＳ６２）。
【０１０３】
上述の説明を読めば、通常の技術を有する者は、開示の実施態様に多くの他の明白で有利な変更を加えることが教示のコンセプトにより可能であることを認識できるであろう。例えば、ハールのウェーブレット変換のような別の空間周波数測定スキームを本発明に使用することができる。本発明は、計量をさらに強化し、例えば、光学的文字認識を用いて文字を位置を特定し、それらの文字をダウンサンプリング中に別々に処理することも可能である。
【０１０４】
【発明の効果】
本発明によれば、高空間周波数情報を維持しながらディジタル画像をダウンサンプリングすることが可能である。グラフィックを含む画像の多くは、高周波と低周波領域、例えば、テキストと背景の両方を含んでいる。グラフィックの高周波領域はしばしば冗長画素を含み、同一強度又は同色の近隣の画素を多く持っている。本発明によれば、高周波画像領域におけるダウンサンプリングを避けて、画像を非一様にダウンサンプリングすることで、高周波領域を保持することが可能である。高周波領域をダウンサンプリングしなければならない場合には、高周波冗長画素のみを除去することが可能である。また、本発明による非一様ダウンサンプリングは、エイリアシングを最少にしてぼけを発生させることなく、高空間周波領域を維持することが可能である。
【図面の簡単な説明】
【図１】仮想の画像の横列に沿った画素強度を示す棒グラフである。
【図２】本発明の一実施形態により、図１の画素強度値をダウンサンプリングした画素強度値を示す棒グラフである。
【図３】コンピュータグラフィックスの原画像を示す図である。
【図４】本発明の一実施形態により図３のコンピュータグラフィックスの原画像をダウンサンプリングした結果を示す図である。
【図５】コンピュータグラフィックス画像中の空間周波数の可能な分布の１例を示す図である。
【図６】本発明の方法による図５の画像に対するダウンサンプリングの効果を示す図である。
【図７】図５の空間周波数分布に対して選択された除去パスを示す図である。
【図８】従来技術の方法によるテキストのダウンサンプリングによるエイリアシングの影響を示す図である。
【図９】本発明の一実施形態の方法による同一テキストのダウンサンプリングを示す図である。
【図１０】本発明の一実施形態のダウンサンプリング方法における幾つかのステップを示す図である。
【図１１】本発明の一実施形態による画像のダウンサンプリングシステムを説明するための図である。
【図１２】本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。
【図１３】本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。
【図１４】本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。
【図１５】本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。
【図１６】本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。
【図１７】本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。
【図１８】本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。
【図１９】本発明の一実施例による、図９のテキスト領域に対する除去パスの選択の順次ステップを示す図である。
【図２０】背景パスを選択する一実施形態による結果を示す図である。
【図２１】図３のコンピュータグラフィックス画像に対し、本発明の一実施形態に対して選択された除去パスと出力結果を示す図である。
【図２２】図３のコンピュータグラフィックス画像に対し、本発明の一実施形態に対して選択された除去パスと出力結果を示す図である。
【図２３】本発明の一実施形態におけるダウンサンプリング方法を説明するためのフロー図である。
【図２４】本発明の他の実施形態におけるダウンサンプリング方法を説明するためのフロー図である。
【図２５】本発明の他の実施形態におけるダウンサンプリング方法を説明するためのフロー図である。
【図２６】本発明の他の実施形態におけるダウンサンプリング方法を説明するためのフロー図である。
【図２７】本発明の他の実施形態におけるダウンサンプリング方法を説明するためのフロー図である。
【図２８】本発明の他の実施形態におけるダウンサンプリング方法を説明するためのフロー図である。
【図２９】本発明の他の実施形態におけるダウンサンプリング方法を説明するためのフロー図である。
【図３０】従来技術による図１の画素強度値をダウンサンプリングするための画素強度値を示す棒グラフである。
【図３１】従来技術による図１の画素強度値をダウンサンプリングするための画素強度値を示す棒グラフである。
【図３２】従来技術により図３のコンピュータグラフィックスの原画像をダウンサンプリングした結果を示す図である。
【図３３】従来技術により図３のコンピュータグラフィックスの原画像をダウンサンプリングした結果を示す図である。
【符号の説明】
１…入力画像、２…空間周波数推定器、３…空間周波数マップ、４…反復器、５…シード縦列発生器、６…パス候補発生器、７…パス得点評価器、８…画素除去器、９…ダウンサンプル画像、３０ａ，３０ｂ，３０ｃ…背景領域、３２ａ〜３２ｆ…テクスチャ領域、３４ａ〜３４ｊ，５６…高周波数領域、３５，３６…空間周波数マップ、４０，４１，４２…ダウンサンプル画像、３８…画像、４４…しきい値マップ、４６，５０，５２…領域、４８…分割マップ、５４…トリプルレットブロック、７０…パス。
【図１】
0004363728.tif 000003
【図２】
0004363728.tif 000004
【図３】
0004363728.tif 000005
【図４】
0004363728.tif 000006
【図５】
0004363728.tif 000007
【図６】
0004363728.tif 000008
【図７】
0004363728.tif 000009
【図８】
0004363728.tif 000010
【図９】
0004363728.tif 000011
【図１０】
0004363728.tif 000012
【図１１】
0004363728.tif 000013
【図１２】
0004363728.tif 000014
【図１３】
0004363728.tif 000015
【図１４】
0004363728.tif 000016
【図１５】
0004363728.tif 000017
【図１６】
0004363728.tif 000018
【図１７】
0004363728.tif 000019
【図１８】
0004363728.tif 000020
【図１９】
0004363728.tif 000021
【図２０】
0004363728.tif 000022
【図２１】
0004363728.tif 000023
【図２２】
0004363728.tif 000024
【図２３】
0004363728.tif 000025
【図２４】
0004363728.tif 000026
【図２５】
0004363728.tif 000027
【図２６】
0004363728.tif 000028
【図２７】
0004363728.tif 000029
【図２８】
0004363728.tif 000030
【図２９】
0004363728.tif 000031
【図３０】
0004363728.tif 000032
【図３１】
0004363728.tif 000033
【図３２】
0004363728.tif 000034
【図３３】
0004363728.tif 000035