JP5037526B2 - 幾何学的画像表現方法および圧縮方法 - Google Patents

Description

優先権

[0001]本出願は、２００５年１２月２１日に出願した、「Ｇｅｏｍｅｔｒｉｃａｌ Ｉｍａｇｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ａｎｄ Ｃｏｍｐｒｅｓｓｉｏｎ」という名称の、対応する仮特許出願第６０／７５２８０９号の優先権を主張し、参照により組み込むものである。

発明の分野

[0002]本発明は、画像処理の分野に関する。より詳細には、本発明は、画像データの幾何学的画像表現を生成し、その新しい表現を使って画像処理操作を行うことに関する。

発明の背景

[0003]コンパクト画像表現は周知の問題である。ここ数年にわたって提案された典型的技法には、画像が、ベクトル辞書における画像のインデックスによって表されるベクトル量子化のような非線形法と、画像が、線形変換され、画像の線形変換係数によって表される線形表現（ウェーブレット変換ベースの表現、フーリエ変換ベースの表現、離散コサイン変換（ＤＣＴ）ベースの表現など）が含まれる。線形表現は、しばしば、それらの表現の有効性をさらに拡張するために、単純な非線形処理を用いて増補される。

[0004]コンパクト表現の最も重要な特性の１つは、これらが少数のパラメータを使って画像を近似することができることである。ある表現の近似率は、その表現においてより多くのパラメータが使用される際の表現誤差の低減として獲得することができる。例えば、この比率は、表現により多くのパラメータが加えられる際の、元の画像と所与の表現を使った元の画像の近似との間の平均二乗誤差の低減を計算することによって獲得することができる。いくつかの例外はあるが、高い近似率（所与の数のパラメータでより少ない誤差）を有する表現は、圧縮、雑音除去、および様々な他の用途においてよりよい成績をもたらすことが期待される。

[0005]孤立した特異点を含む１次元（１Ｄ）信号について、最適な、またはほぼ最適な近似率を達成する線形表現の解決法が知られている。例えば、消失モーメントを有するコンパクトウェーブレットに基づく線形変換が、ほぼ最適な近似率を達成し得ることが知られている。しかしながら、２次元画像と共に使用するためにこれらの表現を２次元に直接的に一般化（例えば、２次元（２−Ｄ）ウェーブレット変換など）しても、最適状態には及ばないことが知られている。本明細書では、これらの直接的な一般化を第１世代線形表現と呼ぶ。

[0006]第１世代線形表現および第１世代線形表現に基づく圧縮アルゴリズムは多数存在する。しかしながら、これらの解決法は、曲線に沿って特異点が現れる画像および映像に関しては、最適状態には及ばないことが知られている。すなわち、第１世代表現および第１世代表現に基づく技法は、特異点の周りに余分な係数またはパラメータを生じる。圧縮法の中には、係数を符号化するのに非常に適するものもあるが、これらの技法は、使用する第１世代表現がもたらす係数が符号化するには多すぎるため、結果として生じる性能は準最適である。

[0007]２次元画像では、特異点が曲線に沿ってあるが、第１世代表現は、特異点を処理することだけしかできず、２次元においては、指数的に準最適である。図１の（ａ）〜（ｃ）に、様々な次元の信号でのコンパクトウェーブレットの使用を示す。図１の（ａ）を参照すると、１Ｄ信号についてほぼ最適に至るコンパクトウェーブレットが示されており、図１の（ｂ）には、特異点を有する２Ｄ信号についてほぼ最適に至るコンパクトウェーブレットが示されている。しかしながら、図１の（ｃ）に示すように、コンパクトウェーブレットは、曲線上の特異点を有する２Ｄ信号では、準最適状態である。すなわち、図１の（ｃ）の信号は、曲線に沿った特異点を表しており、このような信号上では、２次元ウェーブレット変換は、ほぼ最適な近似率を生じない。興味深いことに、現在の最新の画像圧縮法は、これらの第１世代表現に基づくものである。したがって、研究者らの間では、現在の最新の画像圧縮法準最適状態であることは周知である。

[0008]最近では、第１世代表現の準最適性を改善することを目指す第２世代表現が導入されている。これらの技法は、典型的には、連続領域上で定義される画像の理想化された数学モデルを使って設計されている。他方、ディジタル画像は、離散グリッド上で定義され、これらの方法の基本的仮定の多くを満たすことができない。したがって、これらの技法は、目下のところ、第１世代の技法より指数的に優れていたとしても、最新の第１世代の技法を超えることができない。

[0009]複素ウェーブレットなど、最善の第２世代表現の中には、拡張的／過完備であり、画像の画素数より多くのパラメータを生じるものがある。これらの余分なパラメータの多くは小さいが、事実上（レートひずみ的意味において）このような膨張的領域において圧縮を利用する圧縮法は、いまだ開発されていない。

[0010]ディジタル画像の特性とより適合する他の表現、およびこれらの表現に基づく圧縮アルゴリズムが存在する。しかしながら、これらにはまだ、第１世代の技法に優る性能を欠いている。

[0011]また、圧縮アルゴリズムの中には、方向予測を使って、特異点の周りにおける性能を改善しようとするものがある（例えば、ＩＴＵ−ＴとＩＳＯ／ＩＥＣ ＪＴＣ１のＪｏｉｎｔ Ｖｉｄｅｏ Ｔｅａｍにおいて使用されるＩＮＴＲＡフレーム符号化法、「Ｄｒａｆｔ ＩＴＵ Ｔ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ａｎｄ Ｆｉｎａｌ Ｄｒａｆｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｔａｎｄａｒｄ ｏｆ Ｊｏｉｎｔ Ｖｉｄｅｏ Ｓｐｅｃｉｆｉｃａｔｉｏｎ （ＩＴＵ−Ｔ Ｒｅｃ．Ｈ２６４ ｜ ＩＳＯ／ＩＥＣ １４４９６−１０ ＡＶＣ）」、Ｊｏｉｎｔ Ｖｉｄｅｏ Ｔｅａｍ （ＪＶＴ） ｏｆ ＩＳＯ／ＩＥＣ ＭＰＥＧ ａｎｄ ＩＴＵ−Ｔ ＶＣＥＧ、ＪＶＴ−Ｇ０５０、２００３年３月などを参照）。このような解決法は、線形の、または線状の特異点を有する区分的に滑らかな画像モデルに対してのみ適用できる。さらに、これらの技法は、限られたクラスの予測子を使って大規模な領域を予測しようとするため、利用可能なデータの境界から離れた画素が、誤って予測される。同様に、特異点が、単に線状ではなく曲線に沿ってあるとき、または画像統計値が局所的に滑らかでないとき、これらの方法はうまくいかない。

[0012]また、方向線上に変換を配置することによって方向予測子を一般化する方法も、線状の特異点に限定される。さらに、これらの方法は、様々なサイズのブロックに対してその圧縮アルゴリズムを設計する必要があり、これは、結果として生じる係数がエントロピ符号器を用いて符号化されるときに、非効率的結果をもたらす。

発明の概要

[0013]本明細書では、幾何学的画像表現および／または圧縮の方法および装置を開示する。一実施形態において、方法は、画像データの幾何学的フローを求める工程を含む画像データの表現を生成するステップと、幾何学的フローを使って表現内のデータに対する画像処理操作を実行するステップとを含む。

[0014]本発明は、以下に与えられる詳細な説明を読み、添付する本発明の様々な実施形態の図面を参照すれば、より十分に理解されるであろう。しかしながら、図面は、本発明を特定の実施形態だけに限定するものとみなすべきではなく、説明と理解のためにものにすぎない。

本発明の詳細な説明

[0027]画像特異点（曲線に沿って現れるエッジおよびその他の特徴）の取り込みを可能にする新規の画像表現を開示する。一実施形態では、画像における固有の幾何学的特異点構造を特徴付けるのに役立つ画像適応的幾何学的フローフィールドが算出され、続いて、算出されたフローを条件とする画像画素が指定される。この条件指定は、画像を表現するのに必要なパラメータの数が大幅に低減されるような、画像画素の非常にコンパクトな取り込みを可能にする。

[0028]一実施形態では、幾何学的フローの生成プラス条件付き画素指定の手順が変換領域において実行され、そこで、この手順は、「幾何学的フロープラス条件付き変換係数指定」になる。後者の手法は、提案の幾何学的フローベースの表現が、特定の用途に適する領域に利用されることを可能にする。

[0029]画像表現は、様々な画像処理用途において使用することができ、これには、例えば、これらの用途の性能を改善するための画像圧縮や雑音除去が含まれる。

[0030]一実施形態では、画像表現は、表面上の特異点を効率よく取り込むために、２次元より高い次元に一般化される。

[0031]以下の説明では、本発明のより十分な説明を提供するために多くの詳細を示す。しかしながら、本発明は、これらの具体的詳細なしでも実施され得ることが、当分野の技術者には明らかであろう。別の例では、本発明が不明瞭にならないように、周知の構造および装置を、詳細にではなく、ブロック図として示す。

[0032]以下の詳細な説明のいくつかの部分は、アルゴリズム、およびコンピュータメモリ内のデータビットに対する操作の記号的表現として提示する。これらのアルゴリズム的記述および表現は、データ処理分野の技術者が、その作業の内容を当分野の他の技術者に最も有効に伝えるのに使用される手段である。本明細書において、また一般に、アルゴリズムとは、所望の結果をもたらす、筋道の通ったステップのシーケンスであると考えられるものである。各ステップは、物理量の物理的操作を必要とするものである。必要であるとは限らないが、普通は、これらの量は、格納され、転送され、合成され、比較され、別の方法で操作されることのできる電気信号または磁気信号の形を取る。時として、これらの信号を、主に一般的用法により、ビット、値、要素、シンボル、文字、用語、数字などで呼ぶのが好都合なこともある。

[0033]しかしながら、これらの用語および類似の用語は、すべて、適切な物理量と関連付けられるべきものであり、単に、これらの量に適用される便宜的表示にすぎないことに留意すべきである。以下の考察から明らかなように、特に具体的に言及しない限り、説明全体を通して、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」または「算出する（ｃｏｍｐｕｔｉｎｇ）」または「計算する（ｃａｌｃｕｌａｔｉｎｇ）」または「求める（ｄｅｔｅｒｍｉｎｉｎｇ）」または「表示する（ｄｉｓｐｌａｙｉｎｇ）」などといった用語を使用する考察は、コンピュータシステムのレジスタおよびメモリ内で物理（電子）量として表されるデータを操作し、コンピュータシステムメモリまたはレジスタまたは他のこのような情報記憶、伝送または表示装置内で同様に物理量として表される他のデータに変換するコンピュータシステム、または類似の電子計算処理装置の動作およびプロセスを指すものである。

[0034]また、本発明は、本明細書における各操作を実行する装置にも関するものである。この装置は、必要な目的のために専用に構築されてもよく、コンピュータに格納されたコンピュータプログラムによって選択的に作動され、または再構成される汎用コンピュータを備えていてもよい。このようなコンピュータプログラムは、それだけに限らないが、それぞれ、コンピュータシステムバスに結合された、フロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、および光磁気ディスクを含む任意の種類のディスク、読取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光学カード、もしくは電子命令を格納するのに適した任意の種類の媒体などといったコンピュータ可読記憶媒体に格納されていてもよい。

[0035]本明細書で提示するアルゴリズムおよび表示は、どんな特定のコンピュータとも、その他の装置とも固有の関連性を持たない。様々な汎用システムが、本明細書の教示によるプログラムと共に使用されてもよく、必要な方法ステップを実行する、より専門化された装置を構築する方が好都合な場合もある。これらの様々なシステムに必要な構造は、以下の説明を読めば明らかになるであろう。加えて、本発明は、どんな特定のプログラミング言語との関連でも説明されない。本明細書で説明する発明の教示を実施するのに、様々なプログラミング言語が使用され得ることが理解される。

[0036]機械可読媒体は、機械（コンピュータなど）によって読まれ得る形で情報を格納し、または伝送する任意の機構を含む。例えば、機械可読媒体には、読取り専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気的、光学的、音響的またはその他の形の伝搬信号（搬送波、赤外線信号、ディジタル信号など）等々が含まれる。

概要
[0037]幾何学的フローフィールドは、曲線に沿った不連続部分を有する区分的に均一な関数に対して定義されるフィールドと考えられてもよい。区分的に滑らかな関数に対して、幾何学的フローフィールドは、その曲線に沿って関数が正則である、すなわち、幾何学的フロー曲線によって接続される２点が、その曲線に沿って２点間で特異点を持たない曲線を叙述する。図２に、２つの単純な画像、対応する関数、および可能な幾何学的フローを示す。各フローに沿った画素は、そのフローに沿ってこれらの画素を隔てる特異点を持たない。区分的に均一な関数に対して、この定義は、関数または関数の近似率の予測可能性を使用するように拡張することができる。

[0038]所与の画像について、多くのフローが存在し得る。一実施形態では、本明細書で開示する技法が、目的の用途に最適なフローを選択する。圧縮用途では、レートひずみの意味において最もコンパクトな表現をもたらすフローが選択される。

[0039]一実施形態では、所与の画像について、画素（ｉ，ｊ）の方向角θ（ｉ，ｊ）を識別するフローフィールドが生成される。方向角θ（ｉ，ｊ）は、（ｉ，ｊ）の画素と、（ｉ，ｊ）から方向θ（ｉ，ｊ）に進むことによって獲得される（ｋ，ｌ）の画素とが、同じフロー上にあるような方向角である。図３に、所与のθ（ｉ，ｊ）について場所（ｋ，ｌ）を獲得することのできる方法を示す。この技法は、離散グリッド上で定義される画像のために設計されているため、様々な補間法およびステップサイズを利用して、（ｋ，ｌ）における画素値を求めることができる。言い換えると、（ｉ，ｊ）から方向θ（ｉ，ｊ）に進んだ結果として整数の場所がもたらされない（すなわち、非整数の場所がもたらされる）場合、適切な補間法を使って、（ｋ，ｌ）の画素の画素値を求めることができる。

[0040]（ｉ，ｊ）の画素について、（ｉ，ｊ）を通るフローに沿った画素の集合を含む画素近傍η（ｉ，ｊ）が求められる。例えば、この近傍は、θ（ｉ，ｊ）に基づき、（ｋ，ｌ）に到達するまでθ（ｉ，ｊ）の方向に進み、続いてθ（ｋ，ｌ）を使ってさらに進み、以下同様に、所定数のステップが取られるまで進むことによって求めることができる。この場合もやはり、非線形の場所に到達し、または方向が不明瞭であるときにはいつでも、適切な補間法を使って方向および場所を求めることができる。一実施形態では、近傍は、局所的に線形のフローに対応する方向θ（ｉ，ｊ）＋πに進むなどによって、双方向に拡張される。局所的に２次、局所的に３次など、様々なフローの滑らかさの規則および仮定に基づく他の双方向拡張規則を用いることもできる。

[0041]予測用途では、（ｉ，ｊ）の画素が、画素近傍η（ｉ，ｊ）内の画素値に基づいて予測される。この操作を画像内のすべての画素に反復し、予測誤差画像が算出される。圧縮など後続の操作が、この予測誤差画像を使って行われる。

[0042]雑音除去用途では（ｉ，ｊ）の画素値が、画素近傍η（ｉ，ｊ）内の画素値に基づいて雑音除去される。この操作を画像内のすべての画素に反復し、雑音除去画像が算出される。

[0043]操縦可能変換の用途では、画像が、おそらくは重なり合う領域に分割され、操縦可能変換、または方向変換が、各領域に対して評価され、変換の操縦／方向パラメータは、領域内の画素の計算されるフローパラメータに基づいて調整される。それだけに限らないが、圧縮や雑音除去といった後続の操作が、結果として生じる変換係数に対して実行される。

[0044]過完備変換の用途では、例えば、カーブレットや複素ウェーブレットといった、方向過完備変換が、画像に対して評価される。フローパラメータを使って、過完備係数のうちのどれが画像に関連するかが指定される。次いで、これらの指定された係数が、それだけに限らないが、圧縮や雑音除去といった後続の操作で使用される。

[0045]代替の実施形態では、増補された画素値の集合を含む画像が生成される。増補画素値集合は、適切な補間法を使って生成され得る。元の画像の予測、雑音除去、圧縮、過完備変換係数指定などを円滑に行わせるために、この増補画像に対して、フロー計算、近傍計算、領域決定および操縦可能変換決定のうちの１つ以上が実行される。

[0046]一実施形態では、前述の操作が、変換係数のグループによって形成される画像に対し、変換領域において、まず、画像の所与の変換を計算し、変換係数によって形成される画像に対して前述の操作を繰り返すことによって実行される。

[0047]例えば３次元画像／関数などといったより高次の画像／関数（映像シーケンス、磁気共鳴スライスによって描写されるボリュームなど）に対して、幾何学的フローは、所与のフロー表面上の２つの画素が、この表面上でこれらの画素を隔てるどんな特異点も持たないようなより高次の面を叙述する。次いで、前述の操作が、これらの面に沿って実行される。

[0048]一実施形態では、幾何学的フローは、特定のクラスの平滑空間に対してフローを考察することによって最適化される。一実施形態では、四分木を使ったフローの区分が獲得され、四分木の各葉は、その葉に対応するセグメント内のフローを指定するパラメータを有し、パラメータは、このセグメント内のフローの滑らかさを表す。例えば、一実施形態では、パラメータは、セグメント内の１次多項式フロー、２次多項式フロー、３次多項式フローなどを表す。最適な四分木区分および各セグメント内の最適なパラメータは、圧縮用途におけるレートひずみ性能または雑音除去用途における雑音除去性能を最適化するように求めることができる。

様々な実施形態に関する、より詳細な仕様
[0049]一実施形態では、画像に対して２次元ウェーブレット変換が適用される。この変換のサブバンドにおける変換係数が、フローベースの計算を行うための画像を形成する。

[0050]ウェーブレット変換の各サブバンドはデシメーションによって形成されるため、増補サブバンドが、まず、計算され、各サブバンドが、各方向に２つずつアップサンプリングされる。すなわち、非デシメート（ｕｎｄｅｃｉｍａｔｅｄ）ウェーブレット変換係数が計算される。非デシメート／アップサンプリング係数は、偶数のサンプル場所（ｉｍｏｄ２＝０かつｊｍｏｄ２＝０）に配置された元の係数と、残りのサンプル場所（ｉｍｏｄ２≠０またはｊｍｏｄ２≠０）の所の新しい係数を含む。図４は、元の係数と増補係数とに基づく増補サブバンドの形成を示すブロック図である。図４を参照すると、ＬＨサブバンドが、増補ＬＨサブバンドにアップサンプリングされている。本明細書では、アップサンプリングプロセス後に獲得される新しい係数を、元の係数に対して、増補係数と呼ぶ。

[0051]一実施形態では、元の係数が、増補データ（増補係数など）を用いて処理される。一実施形態では、元の係数が、利用可能な元の係数の集合に元の係数を１度に１つずつ加えることによって、１度に１つずつ処理される。各係数を利用可能な集合に加えた後で、一連の操作が、利用可能な集合内の係数を使って実行される。一実施形態では、すべてのウェーブレット変換係数がゼロに設定されている画像から開始して、一度に１つの元の係数が、利用可能な元の係数の集合に加えられる。これと合わせて、一連の画素領域画像が構築され、各画像が、現在利用可能な元の係数だけを、残りの元の係数をゼロに設定して逆変換することによって形成される。元の係数は、例えば、各サブバンド内でのラスタ走査などにおいて利用可能な集合に加えられる。図５の（ａ）および（ｂ）に、元の係数の様々な走査の例を示す。各走査で、元の係数が、走査によって決定される特定の順序で、利用可能な係数集合に加えられる。図５の（ａ）では、２ＬＬサブバンドと２ＬＨサブバンドがラスタ走査され、２ＨＬバンドが反転ラスタ走査され、１ＨＨバンドがジグザグ走査される。図５の（ｂ）では、３つの帯域がタンデム走査される。３つのバンド内の係数は、連結ラスタ走査として走査され、各係数が並べて帯域に加えられる。構築された画素領域画像のシーケンスを、本明細書では、近似画像と呼ぶ。

[0052]一実施形態では、所与のサブバンドにおいて、場所（ｐ，ｑ）の元の係数を加える前に、このサブバンドの増補係数推定値が、現在の近似画像、すなわち、（ｐ，ｑ）の元の係数ではなく、（ｐ，ｑ）の前のすべての元の係数を、残りの全ての元の係数をゼロに設定して逆変換することによって獲得される近似画像にシフトウェーブレット変換を適用することによって計算される。一実施形態では、シフトウェーブレット変換は、現在の近似画像が完全な近似であった場合に、実際の増補係数をもたらしたはずの変換である。したがって、増補係数の推定値は、より多くの元の係数がサブバンドに加えられ、よりよい近似画像が構築されるに従って、次第により正確になる。

[0053]元の係数が加えられるたびに、別の近似画像が算出される。この近似画像を使って、増補係数と増補サブバンドが推定される。また、他の、より洗練された補間法およびデータ回復法を使って増補係数を生成することもできる。これらの方法には、Ｏｎｕｒ Ｇ．Ｇｕｌｅｒｙｕｚ、「Ｎｏｎｌｉｎｅａｒ Ａｐｐｒｏｘｉｍａｔｉｏｎ Ｂａｓｅｄ Ｉｍａｇｅ Ｒｅｃｏｖｅｒｙ Ｕｓｉｎｇ Ａｄａｐｔｉｖｅ Ｓｐａｒｓｅ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎｓ ａｎｄ Ｉｔｅｒａｔｅｄ Ｄｅｎｏｉｓｉｎｇ：Ｐａｒｔ Ｉ−Ｔｈｅｏｒｙ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ、Ｏｎｕｒ Ｇ．Ｇｕｌｅｒｙｕｚ、「Ｎｏｎｌｉｎｅａｒ Ａｐｐｒｏｘｉｍａｔｉｏｎ Ｂａｓｅｄ Ｉｍａｇｅ Ｒｅｃｏｖｅｒｙ Ｕｓｉｎｇ Ａｄａｐｔｉｖｅ Ｓｐａｒｓｅ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎｓ ａｎｄ Ｉｔｅｒａｔｅｄ Ｄｅｎｏｓｉｎｇ：Ｐａｒｔ ＩＩ−Ａｄａｐｔｉｖｅ Ａｌｇｏｒｉｔｈｍｓ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ、およびＯｎｕｒ Ｇ．Ｇｕｌｅｒｙｕｚ、「Ｐｒｅｄｉｃｔｉｎｇ Ｗａｖｅｌｅｔ Ｃｏｅｆｆｉｃｉｅｎｔｓ Ｏｖｅｒ Ｅｄｇｅｓ Ｕｓｉｎｇ Ｅｓｔｉｍａｔｅｓ Ｂａｓｅｄ ｏｎ Ｎｏｎｌｉｎｅａｒ Ａｐｐｒｏｘｉｍａｔｉｏｎｓ」、Ｐｒｏｃ．Ｄａｔａ Ｃｏｍｐｒｅｓｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ、ＩＥＥＥ ＤＣＣ−０４、２００４年４月が含まれる。

[0054]所与のサブバンド内の場所（ｐ，ｑ）と、増補サブバンド内の場所（ｉ＝２ｐ，ｊ＝２ｑ）のところの元の係数について、フロー方向θ（ｉ，ｊ）が獲得され、係数の集合を含む近傍η（ｉ，ｊ）が構築される。この近傍は、増補サブバンドにおいて構築され、現在利用可能な元の係数の一部と、現在推定される増補係数の一部とを含む。図６に、場所（ｉ＝２ｐ，ｊ＝２ｑ）における予測近傍の一例の形成を示す。フロー方向が非整数の場所を指し示す場合、非整数の場所の周りの整数位置に位置する画素におけるフローを使って、近傍形成を伝播させることができる。さらに、一実施形態では、フロー方向が非整数の場所を指し示す場合、非整数の場所の周りの整数位置に位置する画素におけるフローが、近傍形成を伝播させるように補間される。

予測用途および圧縮用途
[0055]幾何学的画像表現は、予測用途および圧縮用途で使用され得る。このプロセスは、操縦可能変換など、他の用途に一般化することができることに留意されたい。

[0056]予測では、目的は、（ｉ＝２ｐ，ｊ＝２ｑ）元の係数について予測を行い、予測誤差を計算することである。よって、予測誤差係数が、元のサンプル点において形成される。その後、これらの予測誤差係数が、元の係数の代わりに圧縮される。伸張を行う復号器が、元の係数を再構築し、再構築された元の係数に逆ウェーブレット変換を適用し、画像を再構築することができるように、各元の係数ごとのフロー方向θ（ｉ，ｊ）が、因果関係を示すために予測誤差と共に送られる。一実施形態では、まず、係数を、その係数の前に送られた係数と、その係数の前に送られた係数を使って構築された増補係数とを使って予測するために、操作が、因果関係を示すようやり方で行われる。

[0057]図７Ａは、幾何学的フローを使った予測ベースの画像圧縮システムの一部である符号器の一実施形態を示すブロック図である。図７Ａの各ブロックは、ハードウェア（回路、専用論理など）、ソフトウェア（汎用コンピュータシステムまたは専用マシン上で走るものなど）、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。

[0058]図７Ａを参照すると、ウェーブレット変換７０２が、画像データ７０１にウェーブレット変換を適用する。量子化ユニット７０３が、ウェーブレット変換７０２によって生成されるウェーブレット係数に対し量子化を行って、量子化係数を生成する。予測ユニット７０４が、各量子化係数ごとに予測を生成し、その予測を実際の量子化係数値と比較し、比較の結果に基づいて予測誤差係数を生成する。係数エントロピ符号器７０５が、予測誤差係数をエントロピ符号化し、結果として生じるビットストリーム、ビット７０６が復号器に送られる。予測で使用される幾何学的フローは、副情報７０７として復号器に送られる。

[0059]図７Ｂは、復号器の一実施形態を示すブロック図である。復号器では、予測操作が反転され、量子化ウェーブレット係数が正しく再構築される。図７Ｂの各ブロックは、ハードウェア（回路、専用論理など）、ソフトウェア（汎用コンピュータシステムまたは専用マシン上で走るものなど）、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。

[0060]図７Ｂを参照すると、係数エントロピ復号器７１３が、ビット７１２に対しエントロピ復号を行って、復号予測誤差係数を生成する。逆予測ユニット７１４が、復号予測誤差係数と、符号化時に使用された幾何学的フローを指定する副情報７１１を受け取り、係数値を生成する。逆量子化ユニット７０５が、これらの量子化係数値に対し逆量子化を行って、量子化されていない係数値を生成する。逆ウェーブレット変換ユニット７１６が、逆量子化係数値に逆変換を適用して、再構築画像データ７１７を生成する。

[0061]一実施形態では、コーデックは、最初にウェーブレット係数を量子化せず、代わりに予測誤差係数を、例えば、ＤＰＣＭ方式において予測プロセス内に量子化を組み込むなどによって量子化する。

[0062]一実施形態では、本明細書で述べる技法によって使用される元の係数が量子化された値を表すように、予測の前に、量子化操作が行われる。この量子化モードでは、増補係数が、フル解像度で、利用可能な量子化された元の係数に基づいて形成される。図８は、幾何学的フローを使って予測を実行する予測プロセス論理の一実施形態を示すブロック図である。図８を参照すると、増補係数算出ユニット８０２が、量子化ウェーブレット係数８０１を受け取り、前述のように増補係数８０３を算出する。フロー算出ユニット８０４が、増補係数を受け取り、幾何学的フローを算出する。予測ユニットの８０５が、増補係数８０３（一部は、その係数の幾何学的フローによって定義される元の係数のそれぞれの周りの増補係数の近傍など）と、フロー算出ユニット８０４からの算出フローとを使って、元の係数のそれぞれについて生成を行う。

[0063]一実施形態では、予測誤差が、まず、フル解像度予測子を計算し、この予測子を量子化し、量子化された予測子を量子化された元の係数から差し引くことによって形成される。図１０は、幾何学的フローを使用し、元の係数に基づいて予測を実行するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア（回路、専用論理など）、ソフトウェア（汎用コンピュータシステムまたは専用マシン上で走るものなど）、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。

[0064]図１０を参照すると、プロセスは、（ｐ，ｑ）のところの元の係数を取り、これを、走査順序を使って利用可能な元の係数のリストに加える処理論理（処理ブロック１００１）から開始する。次いで、処理論理は、付加を行うたびに、異なる、より精密な近似がもたらされるように、各付加後の画像近似を算出する（処理ブロック１００２）。処理論理は、画像近似を使って、増補係数を計算し（処理ブロック１００３）、増補サブバンドを形成する（処理ブロック１００４）。

[0065]（ｐ，ｑ）の元の係数の前にすべての係数が加えられた後、場所（ｉ＝２ｐ，ｊ＝２ｑ）の増補バンドにおける元の係数に関する予測が行われる。一実施形態では、これは、以下の操作を使って行われる。まず、処理論理は、幾何学的フローと、フローがどのようにして補間されるべきか、値がどのようにして補間されるべきか、および近傍の構築のために取られるべきステップの数を求める近傍パラメータとを使って、予測において使用されるべき近傍η（ｉ＝２ｐ，ｊ＝２ｑ）を構築する（処理ブロック１００５）。補間は、双一次補間、Ｓｉｎｃ補間、またはより洗練された補間法とすることもできる。ステップ数は、１、２、５、１０、２０などとすることができる。次に、処理論理は、予測重みを、近傍から獲得される係数値と組み合わせて、予測値を計算する（処理ブロック１００６）。処理論理は、予測値を量子化し（処理ブロック１００７）、量子化された予測値を、（ｐ，ｑ）の元の係数から差し引いて、予測誤差係数を形成する（処理ブロック１００８）。

[0066]したがって、一実施形態では、量子化モードにおいて、圧縮符号器は、量子化された元の係数を、量子化された予測誤差係数と計算されたフローとを使って正確に回復することができるように、量子化された元の係数を取り込み、量子化された予測誤差係数を出力するものとみなすことができる。

[0067]一実施形態では、予測操作の前に、予測で使用される増補係数の変調操作も行われる。この変調は、増補係数によって占められる高周波数帯域を、よりよい予測がもたらされ得る低周波数帯域にシフトする。例えば、増補ＬＨバンド係数は、１つおきの列に（−１）を掛けることによってシフトすることができ、増補ＬＨバンド係数は、１つおきの行に（−１）を掛けることによってシフトすることができ、増補ＨＨバンド係数は、１つおきの行に（−１）を掛け、続いて１つおきの列に（−１）を掛けることによってシフトすることができる。

[0068]ウェーブレット変換全体の予測誤差係数が計算されると、様々な公知の技法を使ってこれらを符号化し、復号器に送ることができる。例えば、ＪＰＥＧ２０００に基づく係数エントロピ符号化法や、Ａ．ＳａｉｄおよびＷ．Ａ．Ｐｅａｒｌｍａｎ、「Ａ Ｎｅｗ Ｆａｓｔ ａｎｄ Ｅｆｆｉｃｉｅｎｔ Ｉｍａｇｅ Ｃｏｄｅｃ Ｂａｓｅｄ ｏｎ Ｓｅｔ Ｐａｒｔｉｔｉｏｎｉｎｇ ｉｎ Ｈｉｅｒａｒｃｈｉｃａｌ Ｔｒｅｅｓ」、ＩＥＥＥＥ．Ｔｒａｎｓ．Ｃｉｒｃ．Ｓｙｓｔ．Ｖｉｄｅｏ Ｔｅｃｈ．６、ｐｐ．２４３〜２５０ページ、１９９６年６月に記載されているような集合分割法や、その他の方法を使用することができる。

[0069]一実施形態では、各帯域におけるフロー計算が、その用途に有利なやり方で行われる。一実施形態では、予測とそれに続く圧縮の用途で、各帯域内のフローが、最善のレートひずみ性能をもたらすように計算される。図９の（ａ）と（ｂ）は、予測ベースの圧縮用途のための幾何学的フローである。

[0070]図９の（ｂ）は、最適なフローの計算のプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア（回路、専用論理など）、ソフトウェア（汎用コンピュータシステムまたは専用マシン上で走るものなど）、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。

[0071]図９の（ｂ）を参照すると、プロセスは、様々な可能な予測のコストを保持するデータ構造を算出する処理論理（処理ブロック９１１）から開始する。次いで、このデータ構造を使って、最適なフローが算出される。図９の（ａ）は、予測コストデータ構造を計算するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア（回路、専用論理など）、ソフトウェア（汎用コンピュータシステムまたは専用マシン上で走るものなど）、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。図９の（ａ）を参照すると、処理論理は、各帯域の走査順序を使って利用可能な元の係数のリストに元の係数を加え（処理ブロック９０１）、付加するたびに画像近似を算出する（処理ブロック９０２）。処理論理は、シフト２Ｄウェーブレット変換を使って増補係数を計算し（処理ブロック９０３）、増補帯域を形成する（処理ブロック９０４）する際に、この画像近似を使用する。

[0072]処理ブロック９０４において（ｐ，ｑ）の元の係数の前にすべての係数を加えた後で、処理論理は、（ｉ＝２ｐ，ｊ＝２ｑ）におけるすべての可能なフロー方向（すなわち、その場所の係数からの任意の可能な方向角）を使って、場所（ｉ＝２ｐ，ｊ＝２ｑ）における増補帯域における元の係数に関する予測を生成し、各フロー方向ごとの予測誤差を算出し、誤差対ビットコストのデータを保持する表を使って誤差を指定するビットコストを獲得し、フロー方向と対応するコストを、データ構造に格納する。

[0073]図９の（ｂ）に戻って、予測コストデータ構造が算出されると、各帯域ごとのフロー計算が、処理論理がその帯域のすべての四分木区分を考察することによって進む。サブバンドのすべての四分木区分について、処理論理は、特定のサブバンド四分木区分のビット単位のコストを計算し、四分木区分の各葉ノード上の幾何学的フローを指定するビットコストを計算し、これら前の２つのコストを併せて加算することにより、特定の四分木の合計コストを計算する（処理ブロック９１２）。一実施形態では、四分木の各葉ノードが、特定のフローを有する１つ以上の元の係数のセグメントに対応する。一実施形態では、この特定のフローは、セグメント内の線状のフローである。別の実施形態では、このフローは、セグメント内のより高次の多項式フローである。他の種類のフローも使用され得る。一実施形態では、各特定のフローが、パラメータによって指定される。四分木区分のコストは、区分を指定するのに必要とされるビット数、区分の各セグメント内の特定のフローパラメータを指定するのに必要とされるビット数、および区分によって決定されるフローの部分と関連付けられる予測誤差を指定するビット単位のコストである。一実施形態では、各セグメント内の特定のフローパラメータを指定するコストは、ビットコスト対フローパラメータ情報を保持する表に基づいて求められる。処理論理は、最小限のコストを獲得する区分およびセグメントフローパラメータを、最適なフローとして選択する（処理ブロック９１３）。

[0074]レートは、各帯域におけるフローおよび予測誤差を指定するのに必要とされるレートを含む。ひずみは、予測プロセスを反転させ、元の係数を形成し、逆ウェーブレット変換を行い、初期の画素領域画像に対する結果の不一致を計算することによって計算される。一実施形態では、不一致は、平均二乗誤差を算出することによって計算される。他の公知の方法も使用され得る。

[0075]一実施形態では、近傍η（ｉ，ｊ）から獲得される画素値を使った予測子が、これらの値を予測重みと直線的に掛け合わせ、結果を合計することによって獲得される。一実施形態では、予測重みは、各（ｉ＝２ｐ，ｊ＝２ｑ）ごとに、その点において利用可能なデータに基づいて最適な重みを計算する統計的技法を使って、適応的に獲得される。例えば、自己回帰統計モデル、自己回帰移動平均統計モデル、共分散モデルなどに基づく予測子を用いることができる。また、Ｏｎｕｒ Ｇ．Ｇｕｌｅｒｙｕｚ、「Ｎｏｎｌｉｎｅａｒ Ａｐｐｒｏｘｉｍａｔｉｏｎ Ｂａｓｅｄ Ｉｍａｇｅ Ｒｅｃｏｖｅｒｙ Ｕｓｉｎｇ Ａｄａｐｔｉｖｅ Ｓｐａｒｓｅ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎｓ ａｎｄ Ｉｔｅｒａｔｅｄ Ｄｅｎｏｉｓｉｎｇ：Ｐａｒｔ Ｉ−Ｔｈｅｏｒｙ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇおよび、Ｏｎｕｒ Ｇ．Ｇｕｌｅｒｙｕｚ、「Ｎｏｎｌｉｎｅａｒ Ａｐｐｒｏｘｉｍａｔｉｏｎ Ｂａｓｅｄ Ｉｍａｇｅ Ｒｅｃｏｖｅｒｙ Ｕｓｉｎｇ Ａｄａｐｔｉｖｅ Ｓｐａｒｓｅ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎｓ ａｎｄ Ｉｔｅｒａｔｅｄ Ｄｅｎｏｉｓｉｎｇ：Ｐａｒｔ ＩＩ−Ａｄａｐｔｉｖｅ Ａｌｇｏｒｉｔｈｍｓ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇなどに開示されている、他のより洗練された予測子を使用することもできる。

代替の実施形態
[0076]一実施形態では、フロー方向θ（ｉ，ｊ）は、Ｄ個の異なる値の１つであり、Ｄは、２、３、４などとすることができる。フローなしの元の係数が予測されず、これらの予測誤差がこれらの値と同じになるように、予約ＮＵＬＬ方向を使って、フローなしが示される。これは、段落［００７２］で概説した最適化プロセスにおいて、予測＝０での可能なフロー値として使用され得る。

[0077]一実施形態では、各四分木セグメント内のフローは、１次多項式（線状）、２次多項式、または３次多項式などである。

[0078]一実施形態では、近傍構築で使用されるステップサイズを、１、２、３、……、または、例えば、２^１／２、２×２^１／２、３．１×２^１／２、……といった他の実数のシーケンスとすることができ、もしくは、各ステップごとに、新しい行または列に達するようにすることもできる。ステップの数は、１、２、３、４、５、……とすることができる。

[0079]一実施形態では、方向と画素値の補間が、1次補間によって行われる。

[0080]一実施形態では、所与のフローの操縦可能変換が、方向が幾何学的フローに基づいて決定される方向共分散行列を構築し、方向カルーネン・レーベ変換（ＫＬＴ）を構築するためにこの行列の固有ベクトルを獲得し、方向ＫＬＴを操縦可能変換として使用することによって獲得される。

[0081]一実施形態では、量子化が、デッドゾーン量子化器によって行われる。別の実施形態では、量子化が行われない。

[0082]一実施形態では、ウェーブレット帯域が、粗い解像度から、より精密な解像度へと処理される。最も粗い解像度における各帯域の順序は、ＬＬ、ＬＨ、ＨＬ、ＨＨ、またはＬＬ、ＨＬ、ＬＨ、ＨＨ、またはＬＬ、ＨＨ、ＬＨ、ＨＬなどとすることができる。別の実施形態では、より精密な解像度において、この順序は、ＬＨ、ＨＬ、ＨＨ、またはＨＬ、ＬＨ，ＨＨなどである。各帯域における係数を、トラバースラスタ走査し、または反転ラスタ走査することができる。一実施形態では、ＬＬ帯域が、ラスタ走査でトラバースされ、ある解像度の他の帯域が、タンデムラスタ走査でトラバースされる。

コンピュータシステムの一例
[0083]図１１は、本明細書で述べる各操作の１つ以上を実行し得る例示的コンピュータシステムを示すブロック図である。図１１を参照すると、コンピュータシステム１１００は、例示的クライアントまたはサーバコンピュータシステムを備え得る。コンピュータシステム１１００は、情報をやりとりする通信機構またはバス１１１１と、情報を処理する、バス１１１１に結合されたプロセッサ１１１２とを備える。プロセッサ１１１２は、それだけに限らないが、例えば、Ｐｅｎｔｉｕｍ（商標）、ＰｏｗｅｒＰＣ（商標）、Ａｌｐｈａ（商標）などといったマイクロプロセッサを含む。

[0084]システム１１００は、さらに、情報およびプロセッサ１１１２によって実行されるべき命令を格納する、バス１１１１に結合された（メインメモリと呼ばれる）ランダムアクセスメモリ（ＲＡＭ）またはその他の動的記憶装置１１０４を備える。また、メインメモリ１１０４は、プロセッサ１１１２による命令の実行中に、一時変数またはその他の中間情報を格納するのにも使用され得る。

[0085]また、コンピュータシステム１１００は、静的状態情報およびプロセッサ１１１２のための命令を格納する、バス１１１１に結合された読取り専用メモリ（ＲＯＭ）および／またはその他の静的記憶装置１１０６と、磁気ディスクや光ディスクとこれに対応するディスクドライブなどのデータ記憶装置１１０７も備える。データ記憶装置１１０７は、情報および命令を格納するためにバス１１１１に結合されている。

[0086]コンピュータシステム１１００は、さらに、コンピュータユーザに情報を表示する、バス１１１１に結合された、ブラウン管（ＣＲＴ）や液晶ディスプレイ（ＬＣＤ）などの表示装置１１２１に結合されていてもよい。また、プロセッサ１１１２に情報およびコマンド選択を伝達するための、英数字その他のキーを含む英数字入力装置１１２２がバス１１１１に結合されていてもよい。プロセッサ１１１２に方向情報およびコマンド選択を伝達し、ディスプレイ１１２１上のカーソル移動を制御するためにバス１１１１に結合された別のユーザ入力装置が、マウス、トラックボール、トラックパッド、スタイラス、カーソル方向キーなどのカーソル制御１１２３である。

[0087]バス１１１１に結合され得る別の装置が、ハードコピー装置１１２４であり、これは、紙、フィルムまたは同種の媒体などの媒体上に情報を記録するのに使用され得る。バス１１１１に結合され得る別の装置が、電話機または手持ち式パーム機器との通信を行う有線／無線通信機能１１２５である。

[0088]本発明では、システム１１００および関連するハードウェアの構成部品のいずれか、またはすべてが使用され得ることに留意されたい。しかしながら、コンピュータシステムの他の構成は、これらの装置の一部または全部を含み得ることも理解することができる。

[0089]以上の説明を読めば、当分野の技術者には、おそらく、本発明の多くの変更および改変が明らかになるであろうが、例示として図示し、説明しているどんな特定の実施形態も、決して、限定的とみなすためのものではないことを理解すべきである。したがって、様々な実施形態の詳細への言及は、それ自体で、本発明にとって必要不可欠であるとみなされる特徴だけを列挙している特許請求の範囲を限定するためのものではない。

（ａ）〜（ｃ）は様々な次元の信号でのコンパクトウェーブレットの使用を示す図である。 ２つの単純な画像、対応する関数、および可能な幾何学的フローを示す図である。 所与の方向角での場所の獲得を示す図である。 元の係数と増強係数とに基づく増補サブバンドの形成を示すブロック図である。 （ａ）および（ｂ）は元の係数の様々な走査例を示す図である。 予測近傍の一例の形成を示す図である。 幾何学的フローを使った予測ベースの画像圧縮システムの一部である符号器の一実施形態を示すブロック図である。 幾何学的フローを使って予測を実行する予測プロセス論理の一実施形態を示すブロック図である。 （ａ）は予測コストデータ構造を計算するプロセスの一実施形態を示すフロー図であり、（ｂ）は最適なフローの計算のプロセスの一実施形態を示すフロー図である。 幾何学的フローを使い、元の係数に基づいて予測を実行するプロセスの一実施形態を示すフロー図である。 本明細書で説明する操作のうちの１つ以上を実行し得る例示的コンピュータシステムを示すブロック図である。

Claims (14)

1. 画像データの幾何学的フローを求めるステップを含む画像データの表現を生成するステップと、
   前記幾何学的フローを使って前記表現内のデータに対する画像処理操作を実行するステップと
   を備え、
   前記幾何学的フローが、前記画像データ中の画素ごとの方向角を含み、
   前記幾何学的フローを求める前記ステップが、
   所定の補間法によって、前記画像データの中の画素の画素値から、当該画像内データ内に増補された画素の画素値の集合を計算するステップと、
   所定の補間法によって、前記画像データの中の画素の方向角から、前記増補された画素ごとの方向角を求めるステップと、
   を備える方法。
2. 前記画像データ中の画素の画素値を走査するステップと、
   走査された画素を、前記画像処理操作に利用可能な画素の集合に加えるステップと
   をさらに備える請求項１に記載の方法。
3. 前記利用可能な係数の集合に、順次、前記１つ以上の画像操作を実行するステップをさらに備える請求項２に記載の方法。
4. 前記画像データ中の複数の画素の複数の近傍であり、前記複数の近傍内の各近傍が、前記画像データ中の前記複数の画素のうちの１画素と関連付けられている前記複数の近傍を求めるステップと、
   前記複数の画素の複数の予測であり、前記複数の画素のそれぞれについての前記複数の予測が、前記画素と関連付けられている近傍における画素値に基づくものである前記複数の予測を生成するステップと、
   前記複数の予測中の各予測ごとの予測誤差を求めるステップと、
   予測誤差を圧縮するステップと
   をさらに備える請求項１に記載の方法。
5. 前記複数の近傍を求める前記ステップが、方向角と増補された前記画像の画素値の集合とに基づいて、前記近傍のうちの少なくとも１つを求めるステップを備える請求項４に記載の方法。
6. 前記幾何学的フローを求める前記ステップが、レートひずみ最適化基準に基づいて算出される請求項１に記載の方法。
7. 前記幾何学的フローが四分木区分上で定義される請求項１に記載の方法。
8. 前記幾何学的フローが区分的多項式である請求項１に記載の方法。
9. 前記幾何学的フローが、点状の特異点に対して区分的に滑らかである請求項１に記載の方法。
10. 前記画像処理操作が、圧縮操作、雑音除去操作、および変換操作からなるグループから選択される少なくとも１つを備える請求項１に記載の方法。
11. 前記計算された幾何学的フローを使って画像データを変換するステップをさらに備える請求項１に記載の方法。
12. 前記計算された幾何学的フローを使って画像データの雑音を除去するステップをさらに備える請求項１に記載の方法。
13. 前記計算された幾何学的フローを使って画像データを圧縮するステップをさらに備える請求項１に記載の方法。
14. 前記フローを使って獲得される方向の統計的共分散行列モデルを使って、前記画像データ中の画素の領域にわたる、線形の、可逆な、操縦可能変換を定義するステップをさらに備える請求項１に記載の方法。

Images