幾何学的画像表現および圧縮
【課題】幾何学的画像表現および/または圧縮の方法および装置を提供する。
【解決手段】ウェーブレット変換を使い画像データを係数に変換し、画像の係数に適応した幾何学的フローを求め、係数の幾何学的フローと近傍パラメータに基づいて近傍に含めるための係数を選択し、得られた近傍の係数も使い予測誤差を生成し、予測誤差を符号化して圧縮ビットストリームを生成すると共に、複数の走査パターンを用いて前記画像の係数を補間する係数を生成する。
【解決手段】ウェーブレット変換を使い画像データを係数に変換し、画像の係数に適応した幾何学的フローを求め、係数の幾何学的フローと近傍パラメータに基づいて近傍に含めるための係数を選択し、得られた近傍の係数も使い予測誤差を生成し、予測誤差を符号化して圧縮ビットストリームを生成すると共に、複数の走査パターンを用いて前記画像の係数を補間する係数を生成する。
【発明の詳細な説明】
【技術分野】
【0001】
[0001]本出願は、2005年12月21日に出願した、「Geometrical Image Representation and Compression」という名称の、対応する仮特許出願第60/752809号の優先権を主張し、参照により組み込むものである。
【0002】
[0002]本発明は、画像処理の分野に関する。より詳細には、本発明は、画像データの幾何学的画像表現を生成し、その新しい表現を使って画像処理操作を行うことに関する。
【背景技術】
【0003】
[0003]コンパクト画像表現は周知の問題である。ここ数年にわたって提案された典型的技法には、画像が、ベクトル辞書における画像のインデックスによって表されるベクトル量子化のような非線形法と、画像が、線形変換され、画像の線形変換係数によって表される線形表現(ウェーブレット変換ベースの表現、フーリエ変換ベースの表現、離散コサイン変換(DCT)ベースの表現など)が含まれる。線形表現は、しばしば、それらの表現の有効性をさらに拡張するために、単純な非線形処理を用いて増補される。
【0004】
[0004]コンパクト表現の最も重要な特性の1つは、これらが少数のパラメータを使って画像を近似することができることである。ある表現の近似率は、その表現においてより多くのパラメータが使用される際の表現誤差の低減として獲得することができる。例えば、この比率は、表現により多くのパラメータが加えられる際の、元の画像と所与の表現を使った元の画像の近似との間の平均二乗誤差の低減を計算することによって獲得することができる。いくつかの例外はあるが、高い近似率(所与の数のパラメータでより少ない誤差)を有する表現は、圧縮、雑音除去、および様々な他の用途においてよりよい成績をもたらすことが期待される。
【0005】
[0005]孤立した特異点を含む1次元(1D)信号について、最適な、またはほぼ最適な近似率を達成する線形表現の解決法が知られている。例えば、消失モーメントを有するコンパクトウェーブレットに基づく線形変換が、ほぼ最適な近似率を達成し得ることが知られている。しかしながら、2次元画像と共に使用するためにこれらの表現を2次元に直接的に一般化(例えば、2次元(2−D)ウェーブレット変換など)しても、最適状態には及ばないことが知られている。本明細書では、これらの直接的な一般化を第1世代線形表現と呼ぶ。
【0006】
[0006]第1世代線形表現および第1世代線形表現に基づく圧縮アルゴリズムは多数存在する。しかしながら、これらの解決法は、曲線に沿って特異点が現れる画像および映像に関しては、最適状態には及ばないことが知られている。すなわち、第1世代表現および第1世代表現に基づく技法は、特異点の周りに余分な係数またはパラメータを生じる。圧縮法の中には、係数を符号化するのに非常に適するものもあるが、これらの技法は、使用する第1世代表現がもたらす係数が符号化するには多すぎるため、結果として生じる性能は準最適である。
【0007】
[0007]2次元画像では、特異点が曲線に沿ってあるが、第1世代表現は、特異点を処理することだけしかできず、2次元においては、指数的に準最適である。図1の(a)〜(c)に、様々な次元の信号でのコンパクトウェーブレットの使用を示す。図1の(a)を参照すると、1D信号についてほぼ最適に至るコンパクトウェーブレットが示されており、図1の(b)には、特異点を有する2D信号についてほぼ最適に至るコンパクトウェーブレットが示されている。しかしながら、図1の(c)に示すように、コンパクトウェーブレットは、曲線上の特異点を有する2D信号では、準最適状態である。すなわち、図1の(c)の信号は、曲線に沿った特異点を表しており、このような信号上では、2次元ウェーブレット変換は、ほぼ最適な近似率を生じない。興味深いことに、現在の最新の画像圧縮法は、これらの第1世代表現に基づくものである。したがって、研究者らの間では、現在の最新の画像圧縮法準最適状態であることは周知である。
【0008】
[0008]最近では、第1世代表現の準最適性を改善することを目指す第2世代表現が導入されている。これらの技法は、典型的には、連続領域上で定義される画像の理想化された数学モデルを使って設計されている。他方、ディジタル画像は、離散グリッド上で定義され、これらの方法の基本的仮定の多くを満たすことができない。したがって、これらの技法は、目下のところ、第1世代の技法より指数的に優れていたとしても、最新の第1世代の技法を超えることができない。
【0009】
[0009]複素ウェーブレットなど、最善の第2世代表現の中には、拡張的/過完備であり、画像の画素数より多くのパラメータを生じるものがある。これらの余分なパラメータの多くは小さいが、事実上(レートひずみ的意味において)このような膨張的領域において圧縮を利用する圧縮法は、いまだ開発されていない。
【0010】
[0010]ディジタル画像の特性とより適合する他の表現、およびこれらの表現に基づく圧縮アルゴリズムが存在する。しかしながら、これらにはまだ、第1世代の技法に優る性能を欠いている。
【0011】
[0011]また、圧縮アルゴリズムの中には、方向予測を使って、特異点の周りにおける性能を改善しようとするものがある(例えば、ITU−TとISO/IEC JTC1のJoint Video Teamにおいて使用されるINTRAフレーム符号化法、「Draft ITU T Recommendation and Final Draft International Standard of Joint Video Specification (ITU−T Rec.H264 | ISO/IEC 14496−10 AVC)」、Joint Video Team (JVT) of ISO/IEC MPEG and ITU−T VCEG、JVT−G050、2003年3月などを参照)。このような解決法は、線形の、または線状の特異点を有する区分的に滑らかな画像モデルに対してのみ適用できる。さらに、これらの技法は、限られたクラスの予測子を使って大規模な領域を予測しようとするため、利用可能なデータの境界から離れた画素が、誤って予測される。同様に、特異点が、単に線状ではなく曲線に沿ってあるとき、または画像統計値が局所的に滑らかでないとき、これらの方法はうまくいかない。
【0012】
[0012]また、方向線上に変換を配置することによって方向予測子を一般化する方法も、線状の特異点に限定される。さらに、これらの方法は、様々なサイズのブロックに対してその圧縮アルゴリズムを設計する必要があり、これは、結果として生じる係数がエントロピ符号器を用いて符号化されるときに、非効率的結果をもたらす。
【発明の概要】
【課題を解決するための手段】
【0013】
[0013]本明細書では、幾何学的画像表現および/または圧縮の方法および装置を開示する。一実施形態において、方法は、画像データの幾何学的フローを求める工程を含む画像データの表現を生成するステップと、幾何学的フローを使って表現内のデータに対する画像処理操作を実行するステップとを含む。
【0014】
[0014]本発明は、以下に与えられる詳細な説明を読み、添付する本発明の様々な実施形態の図面を参照すれば、より十分に理解されるであろう。しかしながら、図面は、本発明を特定の実施形態だけに限定するものとみなすべきではなく、説明と理解のためにものにすぎない。
【図面の簡単な説明】
【0015】
【図1】(a)〜(c)は様々な次元の信号でのコンパクトウェーブレットの使用を示す図である。
【図2】2つの単純な画像、対応する関数、および可能な幾何学的フローを示す図である。
【図3】所与の方向角での場所の獲得を示す図である。
【図4】元の係数と増強係数とに基づく増補サブバンドの形成を示すブロック図である。
【図5】(a)および(b)は元の係数の様々な走査例を示す図である。
【図6】予測近傍の一例の形成を示す図である。
【図7】幾何学的フローを使った予測ベースの画像圧縮システムの一部である符号器の一実施形態を示すブロック図である。
【図8】幾何学的フローを使って予測を実行する予測プロセス論理の一実施形態を示すブロック図である。
【図9】(a)は予測コストデータ構造を計算するプロセスの一実施形態を示すフロー図であり、(b)は最適なフローの計算のプロセスの一実施形態を示すフロー図である。
【図10】幾何学的フローを使い、元の係数に基づいて予測を実行するプロセスの一実施形態を示すフロー図である。
【図11】本明細書で説明する操作のうちの1つ以上を実行し得る例示的コンピュータシステムを示すブロック図である。
【発明を実施するための形態】
【0016】
[0027]画像特異点(曲線に沿って現れるエッジおよびその他の特徴)の取り込みを可能にする新規の画像表現を開示する。一実施形態では、画像における固有の幾何学的特異点構造を特徴付けるのに役立つ画像適応的幾何学的フローフィールドが算出され、続いて、算出されたフローを条件とする画像画素が指定される。この条件指定は、画像を表現するのに必要なパラメータの数が大幅に低減されるような、画像画素の非常にコンパクトな取り込みを可能にする。
【0017】
[0028]一実施形態では、幾何学的フローの生成プラス条件付き画素指定の手順が変換領域において実行され、そこで、この手順は、「幾何学的フロープラス条件付き変換係数指定」になる。後者の手法は、提案の幾何学的フローベースの表現が、特定の用途に適する領域に利用されることを可能にする。
【0018】
[0029]画像表現は、様々な画像処理用途において使用することができ、これには、例えば、これらの用途の性能を改善するための画像圧縮や雑音除去が含まれる。
【0019】
[0030]一実施形態では、画像表現は、表面上の特異点を効率よく取り込むために、2次元より高い次元に一般化される。
【0020】
[0031]以下の説明では、本発明のより十分な説明を提供するために多くの詳細を示す。しかしながら、本発明は、これらの具体的詳細なしでも実施され得ることが、当分野の技術者には明らかであろう。別の例では、本発明が不明瞭にならないように、周知の構造および装置を、詳細にではなく、ブロック図として示す。
【0021】
[0032]以下の詳細な説明のいくつかの部分は、アルゴリズム、およびコンピュータメモリ内のデータビットに対する操作の記号的表現として提示する。これらのアルゴリズム的記述および表現は、データ処理分野の技術者が、その作業の内容を当分野の他の技術者に最も有効に伝えるのに使用される手段である。本明細書において、また一般に、アルゴリズムとは、所望の結果をもたらす、筋道の通ったステップのシーケンスであると考えられるものである。各ステップは、物理量の物理的操作を必要とするものである。必要であるとは限らないが、普通は、これらの量は、格納され、転送され、合成され、比較され、別の方法で操作されることのできる電気信号または磁気信号の形を取る。時として、これらの信号を、主に一般的用法により、ビット、値、要素、シンボル、文字、用語、数字などで呼ぶのが好都合なこともある。
【0022】
[0033]しかしながら、これらの用語および類似の用語は、すべて、適切な物理量と関連付けられるべきものであり、単に、これらの量に適用される便宜的表示にすぎないことに留意すべきである。以下の考察から明らかなように、特に具体的に言及しない限り、説明全体を通して、「処理する(processing)」または「算出する(computing)」または「計算する(calculating)」または「求める(determining)」または「表示する(displaying)」などといった用語を使用する考察は、コンピュータシステムのレジスタおよびメモリ内で物理(電子)量として表されるデータを操作し、コンピュータシステムメモリまたはレジスタまたは他のこのような情報記憶、伝送または表示装置内で同様に物理量として表される他のデータに変換するコンピュータシステム、または類似の電子計算処理装置の動作およびプロセスを指すものである。
【0023】
[0034]また、本発明は、本明細書における各操作を実行する装置にも関するものである。この装置は、必要な目的のために専用に構築されてもよく、コンピュータに格納されたコンピュータプログラムによって選択的に作動され、または再構成される汎用コンピュータを備えていてもよい。このようなコンピュータプログラムは、それだけに限らないが、それぞれ、コンピュータシステムバスに結合された、フロッピーディスク、光ディスク、CD−ROM、および光磁気ディスクを含む任意の種類のディスク、読取り専用メモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気または光学カード、もしくは電子命令を格納するのに適した任意の種類の媒体などといったコンピュータ可読記憶媒体に格納されていてもよい。
【0024】
[0035]本明細書で提示するアルゴリズムおよび表示は、どんな特定のコンピュータとも、その他の装置とも固有の関連性を持たない。様々な汎用システムが、本明細書の教示によるプログラムと共に使用されてもよく、必要な方法ステップを実行する、より専門化された装置を構築する方が好都合な場合もある。これらの様々なシステムに必要な構造は、以下の説明を読めば明らかになるであろう。加えて、本発明は、どんな特定のプログラミング言語との関連でも説明されない。本明細書で説明する発明の教示を実施するのに、様々なプログラミング言語が使用され得ることが理解される。
【0025】
[0036]機械可読媒体は、機械(コンピュータなど)によって読まれ得る形で情報を格納し、または伝送する任意の機構を含む。例えば、機械可読媒体には、読取り専用メモリ(「ROM」)、ランダムアクセスメモリ(「RAM」)、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気的、光学的、音響的またはその他の形の伝搬信号(搬送波、赤外線信号、ディジタル信号など)等々が含まれる。
【0026】
概要
[0037]幾何学的フローフィールドは、曲線に沿った不連続部分を有する区分的に均一な関数に対して定義されるフィールドと考えられてもよい。区分的に滑らかな関数に対して、幾何学的フローフィールドは、その曲線に沿って関数が正則である、すなわち、幾何学的フロー曲線によって接続される2点が、その曲線に沿って2点間で特異点を持たない曲線を叙述する。図2に、2つの単純な画像、対応する関数、および可能な幾何学的フローを示す。各フローに沿った画素は、そのフローに沿ってこれらの画素を隔てる特異点を持たない。区分的に均一な関数に対して、この定義は、関数または関数の近似率の予測可能性を使用するように拡張することができる。
【0027】
[0038]所与の画像について、多くのフローが存在し得る。一実施形態では、本明細書で開示する技法が、目的の用途に最適なフローを選択する。圧縮用途では、レートひずみの意味において最もコンパクトな表現をもたらすフローが選択される。
【0028】
[0039]一実施形態では、所与の画像について、画素(i,j)の方向角θ(i,j)を識別するフローフィールドが生成される。方向角θ(i,j)は、(i,j)の画素と、(i,j)から方向θ(i,j)に進むことによって獲得される(k,l)の画素とが、同じフロー上にあるような方向角である。図3に、所与のθ(i,j)について場所(k,l)を獲得することのできる方法を示す。この技法は、離散グリッド上で定義される画像のために設計されているため、様々な補間法およびステップサイズを利用して、(k,l)における画素値を求めることができる。言い換えると、(i,j)から方向θ(i,j)に進んだ結果として整数の場所がもたらされない(すなわち、非整数の場所がもたらされる)場合、適切な補間法を使って、(k,l)の画素の画素値を求めることができる。
【0029】
[0040](i,j)の画素について、(i,j)を通るフローに沿った画素の集合を含む画素近傍η(i,j)が求められる。例えば、この近傍は、θ(i,j)に基づき、(k,l)に到達するまでθ(i,j)の方向に進み、続いてθ(k,l)を使ってさらに進み、以下同様に、所定数のステップが取られるまで進むことによって求めることができる。この場合もやはり、非線形の場所に到達し、または方向が不明瞭であるときにはいつでも、適切な補間法を使って方向および場所を求めることができる。一実施形態では、近傍は、局所的に線形のフローに対応する方向θ(i,j)+πに進むなどによって、双方向に拡張される。局所的に2次、局所的に3次など、様々なフローの滑らかさの規則および仮定に基づく他の双方向拡張規則を用いることもできる。
【0030】
[0041]予測用途では、(i,j)の画素が、画素近傍η(i,j)内の画素値に基づいて予測される。この操作を画像内のすべての画素に反復し、予測誤差画像が算出される。圧縮など後続の操作が、この予測誤差画像を使って行われる。
【0031】
[0042]雑音除去用途では(i,j)の画素値が、画素近傍η(i,j)内の画素値に基づいて雑音除去される。この操作を画像内のすべての画素に反復し、雑音除去画像が算出される。
【0032】
[0043]操縦可能変換の用途では、画像が、おそらくは重なり合う領域に分割され、操縦可能変換、または方向変換が、各領域に対して評価され、変換の操縦/方向パラメータは、領域内の画素の計算されるフローパラメータに基づいて調整される。それだけに限らないが、圧縮や雑音除去といった後続の操作が、結果として生じる変換係数に対して実行される。
【0033】
[0044]過完備変換の用途では、例えば、カーブレットや複素ウェーブレットといった、方向過完備変換が、画像に対して評価される。フローパラメータを使って、過完備係数のうちのどれが画像に関連するかが指定される。次いで、これらの指定された係数が、それだけに限らないが、圧縮や雑音除去といった後続の操作で使用される。
【0034】
[0045]代替の実施形態では、増補された画素値の集合を含む画像が生成される。増補画素値集合は、適切な補間法を使って生成され得る。元の画像の予測、雑音除去、圧縮、過完備変換係数指定などを円滑に行わせるために、この増補画像に対して、フロー計算、近傍計算、領域決定および操縦可能変換決定のうちの1つ以上が実行される。
【0035】
[0046]一実施形態では、前述の操作が、変換係数のグループによって形成される画像に対し、変換領域において、まず、画像の所与の変換を計算し、変換係数によって形成される画像に対して前述の操作を繰り返すことによって実行される。
【0036】
[0047]例えば3次元画像/関数などといったより高次の画像/関数(映像シーケンス、磁気共鳴スライスによって描写されるボリュームなど)に対して、幾何学的フローは、所与のフロー表面上の2つの画素が、この表面上でこれらの画素を隔てるどんな特異点も持たないようなより高次の面を叙述する。次いで、前述の操作が、これらの面に沿って実行される。
【0037】
[0048]一実施形態では、幾何学的フローは、特定のクラスの平滑空間に対してフローを考察することによって最適化される。一実施形態では、四分木を使ったフローの区分が獲得され、四分木の各葉は、その葉に対応するセグメント内のフローを指定するパラメータを有し、パラメータは、このセグメント内のフローの滑らかさを表す。例えば、一実施形態では、パラメータは、セグメント内の1次多項式フロー、2次多項式フロー、3次多項式フローなどを表す。最適な四分木区分および各セグメント内の最適なパラメータは、圧縮用途におけるレートひずみ性能または雑音除去用途における雑音除去性能を最適化するように求めることができる。
【0038】
様々な実施形態に関する、より詳細な仕様
[0049]一実施形態では、画像に対して2次元ウェーブレット変換が適用される。この変換のサブバンドにおける変換係数が、フローベースの計算を行うための画像を形成する。
【0039】
[0050]ウェーブレット変換の各サブバンドはデシメーションによって形成されるため、増補サブバンドが、まず、計算され、各サブバンドが、各方向に2つずつアップサンプリングされる。すなわち、非デシメート(undecimated)ウェーブレット変換係数が計算される。非デシメート/アップサンプリング係数は、偶数のサンプル場所(imod2=0かつjmod2=0)に配置された元の係数と、残りのサンプル場所(imod2≠0またはjmod2≠0)の所の新しい係数を含む。図4は、元の係数と増補係数とに基づく増補サブバンドの形成を示すブロック図である。図4を参照すると、LHサブバンドが、増補LHサブバンドにアップサンプリングされている。本明細書では、アップサンプリングプロセス後に獲得される新しい係数を、元の係数に対して、増補係数と呼ぶ。
【0040】
[0051]一実施形態では、元の係数が、増補データ(増補係数など)を用いて処理される。一実施形態では、元の係数が、利用可能な元の係数の集合に元の係数を1度に1つずつ加えることによって、1度に1つずつ処理される。各係数を利用可能な集合に加えた後で、一連の操作が、利用可能な集合内の係数を使って実行される。一実施形態では、すべてのウェーブレット変換係数がゼロに設定されている画像から開始して、一度に1つの元の係数が、利用可能な元の係数の集合に加えられる。これと合わせて、一連の画素領域画像が構築され、各画像が、現在利用可能な元の係数だけを、残りの元の係数をゼロに設定して逆変換することによって形成される。元の係数は、例えば、各サブバンド内でのラスタ走査などにおいて利用可能な集合に加えられる。図5の(a)および(b)に、元の係数の様々な走査の例を示す。各走査で、元の係数が、走査によって決定される特定の順序で、利用可能な係数集合に加えられる。図5の(a)では、2LLサブバンドと2LHサブバンドがラスタ走査され、2HLバンドが反転ラスタ走査され、1HHバンドがジグザグ走査される。図5の(b)では、3つの帯域がタンデム走査される。3つのバンド内の係数は、連結ラスタ走査として走査され、各係数が並べて帯域に加えられる。構築された画素領域画像のシーケンスを、本明細書では、近似画像と呼ぶ。
【0041】
[0052]一実施形態では、所与のサブバンドにおいて、場所(p,q)の元の係数を加える前に、このサブバンドの増補係数推定値が、現在の近似画像、すなわち、(p,q)の元の係数ではなく、(p,q)の前のすべての元の係数を、残りの全ての元の係数をゼロに設定して逆変換することによって獲得される近似画像にシフトウェーブレット変換を適用することによって計算される。一実施形態では、シフトウェーブレット変換は、現在の近似画像が完全な近似であった場合に、実際の増補係数をもたらしたはずの変換である。したがって、増補係数の推定値は、より多くの元の係数がサブバンドに加えられ、よりよい近似画像が構築されるに従って、次第により正確になる。
【0042】
[0053]元の係数が加えられるたびに、別の近似画像が算出される。この近似画像を使って、増補係数と増補サブバンドが推定される。また、他の、より洗練された補間法およびデータ回復法を使って増補係数を生成することもできる。これらの方法には、Onur G.Guleryuz、「Nonlinear Approximation Based Image Recovery Using Adaptive Sparse Reconstructions and Iterated Denoising:Part I−Theory」、IEEE Transactions on Image Processing、Onur G.Guleryuz、「Nonlinear Approximation Based Image Recovery Using Adaptive Sparse Reconstructions and Iterated Denosing:Part II−Adaptive Algorithms」、IEEE Transactions on Image Processing、およびOnur G.Guleryuz、「Predicting Wavelet Coefficients Over Edges Using Estimates Based on Nonlinear Approximations」、Proc.Data Compression Conference、IEEE DCC−04、2004年4月が含まれる。
【0043】
[0054]所与のサブバンド内の場所(p,q)と、増補サブバンド内の場所(i=2p,j=2q)のところの元の係数について、フロー方向θ(i,j)が獲得され、係数の集合を含む近傍η(i,j)が構築される。この近傍は、増補サブバンドにおいて構築され、現在利用可能な元の係数の一部と、現在推定される増補係数の一部とを含む。図6に、場所(i=2p,j=2q)における予測近傍の一例の形成を示す。フロー方向が非整数の場所を指し示す場合、非整数の場所の周りの整数位置に位置する画素におけるフローを使って、近傍形成を伝播させることができる。さらに、一実施形態では、フロー方向が非整数の場所を指し示す場合、非整数の場所の周りの整数位置に位置する画素におけるフローが、近傍形成を伝播させるように補間される。
【0044】
予測用途および圧縮用途
[0055]幾何学的画像表現は、予測用途および圧縮用途で使用され得る。このプロセスは、操縦可能変換など、他の用途に一般化することができることに留意されたい。
【0045】
[0056]予測では、目的は、(i=2p,j=2q)元の係数について予測を行い、予測誤差を計算することである。よって、予測誤差係数が、元のサンプル点において形成される。その後、これらの予測誤差係数が、元の係数の代わりに圧縮される。伸張を行う復号器が、元の係数を再構築し、再構築された元の係数に逆ウェーブレット変換を適用し、画像を再構築することができるように、各元の係数ごとのフロー方向θ(i,j)が、因果関係を示すために予測誤差と共に送られる。一実施形態では、まず、係数を、その係数の前に送られた係数と、その係数の前に送られた係数を使って構築された増補係数とを使って予測するために、操作が、因果関係を示すようやり方で行われる。
【0046】
[0057]図7Aは、幾何学的フローを使った予測ベースの画像圧縮システムの一部である符号器の一実施形態を示すブロック図である。図7Aの各ブロックは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。
【0047】
[0058]図7Aを参照すると、ウェーブレット変換702が、画像データ701にウェーブレット変換を適用する。量子化ユニット703が、ウェーブレット変換702によって生成されるウェーブレット係数に対し量子化を行って、量子化係数を生成する。予測ユニット704が、各量子化係数ごとに予測を生成し、その予測を実際の量子化係数値と比較し、比較の結果に基づいて予測誤差係数を生成する。係数エントロピ符号器705が、予測誤差係数をエントロピ符号化し、結果として生じるビットストリーム、ビット706が復号器に送られる。予測で使用される幾何学的フローは、副情報707として復号器に送られる。
【0048】
[0059]図7Bは、復号器の一実施形態を示すブロック図である。復号器では、予測操作が反転され、量子化ウェーブレット係数が正しく再構築される。図7Bの各ブロックは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。
【0049】
[0060]図7Bを参照すると、係数エントロピ復号器713が、ビット712に対しエントロピ復号を行って、復号予測誤差係数を生成する。逆予測ユニット714が、復号予測誤差係数と、符号化時に使用された幾何学的フローを指定する副情報711を受け取り、係数値を生成する。逆量子化ユニット705が、これらの量子化係数値に対し逆量子化を行って、量子化されていない係数値を生成する。逆ウェーブレット変換ユニット716が、逆量子化係数値に逆変換を適用して、再構築画像データ717を生成する。
【0050】
[0061]一実施形態では、コーデックは、最初にウェーブレット係数を量子化せず、代わりに予測誤差係数を、例えば、DPCM方式において予測プロセス内に量子化を組み込むなどによって量子化する。
【0051】
[0062]一実施形態では、本明細書で述べる技法によって使用される元の係数が量子化された値を表すように、予測の前に、量子化操作が行われる。この量子化モードでは、増補係数が、フル解像度で、利用可能な量子化された元の係数に基づいて形成される。図8は、幾何学的フローを使って予測を実行する予測プロセス論理の一実施形態を示すブロック図である。図8を参照すると、増補係数算出ユニット802が、量子化ウェーブレット係数801を受け取り、前述のように増補係数803を算出する。フロー算出ユニット804が、増補係数を受け取り、幾何学的フローを算出する。予測ユニットの805が、増補係数803(一部は、その係数の幾何学的フローによって定義される元の係数のそれぞれの周りの増補係数の近傍など)と、フロー算出ユニット804からの算出フローとを使って、元の係数のそれぞれについて生成を行う。
【0052】
[0063]一実施形態では、予測誤差が、まず、フル解像度予測子を計算し、この予測子を量子化し、量子化された予測子を量子化された元の係数から差し引くことによって形成される。図10は、幾何学的フローを使用し、元の係数に基づいて予測を実行するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。
【0053】
[0064]図10を参照すると、プロセスは、(p,q)のところの元の係数を取り、これを、走査順序を使って利用可能な元の係数のリストに加える処理論理(処理ブロック1001)から開始する。次いで、処理論理は、付加を行うたびに、異なる、より精密な近似がもたらされるように、各付加後の画像近似を算出する(処理ブロック1002)。処理論理は、画像近似を使って、増補係数を計算し(処理ブロック1003)、増補サブバンドを形成する(処理ブロック1004)。
【0054】
[0065](p,q)の元の係数の前にすべての係数が加えられた後、場所(i=2p,j=2q)の増補バンドにおける元の係数に関する予測が行われる。一実施形態では、これは、以下の操作を使って行われる。まず、処理論理は、幾何学的フローと、フローがどのようにして補間されるべきか、値がどのようにして補間されるべきか、および近傍の構築のために取られるべきステップの数を求める近傍パラメータとを使って、予測において使用されるべき近傍η(i=2p,j=2q)を構築する(処理ブロック1005)。補間は、双一次補間、Sinc補間、またはより洗練された補間法とすることもできる。ステップ数は、1、2、5、10、20などとすることができる。次に、処理論理は、予測重みを、近傍から獲得される係数値と組み合わせて、予測値を計算する(処理ブロック1006)。処理論理は、予測値を量子化し(処理ブロック1007)、量子化された予測値を、(p,q)の元の係数から差し引いて、予測誤差係数を形成する(処理ブロック1008)。
【0055】
[0066]したがって、一実施形態では、量子化モードにおいて、圧縮符号器は、量子化された元の係数を、量子化された予測誤差係数と計算されたフローとを使って正確に回復することができるように、量子化された元の係数を取り込み、量子化された予測誤差係数を出力するものとみなすことができる。
【0056】
[0067]一実施形態では、予測操作の前に、予測で使用される増補係数の変調操作も行われる。この変調は、増補係数によって占められる高周波数帯域を、よりよい予測がもたらされ得る低周波数帯域にシフトする。例えば、増補LHバンド係数は、1つおきの列に(−1)を掛けることによってシフトすることができ、増補LHバンド係数は、1つおきの行に(−1)を掛けることによってシフトすることができ、増補HHバンド係数は、1つおきの行に(−1)を掛け、続いて1つおきの列に(−1)を掛けることによってシフトすることができる。
【0057】
[0068]ウェーブレット変換全体の予測誤差係数が計算されると、様々な公知の技法を使ってこれらを符号化し、復号器に送ることができる。例えば、JPEG2000に基づく係数エントロピ符号化法や、A.SaidおよびW.A.Pearlman、「A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees」、IEEEE.Trans.Circ.Syst.Video Tech.6、pp.243〜250ページ、1996年6月に記載されているような集合分割法や、その他の方法を使用することができる。
【0058】
[0069]一実施形態では、各帯域におけるフロー計算が、その用途に有利なやり方で行われる。一実施形態では、予測とそれに続く圧縮の用途で、各帯域内のフローが、最善のレートひずみ性能をもたらすように計算される。図9の(a)と(b)は、予測ベースの圧縮用途のための幾何学的フローである。
【0059】
[0070]図9の(b)は、最適なフローの計算のプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。
【0060】
[0071]図9の(b)を参照すると、プロセスは、様々な可能な予測のコストを保持するデータ構造を算出する処理論理(処理ブロック911)から開始する。次いで、このデータ構造を使って、最適なフローが算出される。図9の(a)は、予測コストデータ構造を計算するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。図9の(a)を参照すると、処理論理は、各帯域の走査順序を使って利用可能な元の係数のリストに元の係数を加え(処理ブロック901)、付加するたびに画像近似を算出する(処理ブロック902)。処理論理は、シフト2Dウェーブレット変換を使って増補係数を計算し(処理ブロック903)、増補帯域を形成する(処理ブロック904)する際に、この画像近似を使用する。
【0061】
[0072]処理ブロック904において(p,q)の元の係数の前にすべての係数を加えた後で、処理論理は、(i=2p,j=2q)におけるすべての可能なフロー方向(すなわち、その場所の係数からの任意の可能な方向角)を使って、場所(i=2p,j=2q)における増補帯域における元の係数に関する予測を生成し、各フロー方向ごとの予測誤差を算出し、誤差対ビットコストのデータを保持する表を使って誤差を指定するビットコストを獲得し、フロー方向と対応するコストを、データ構造に格納する。
【0062】
[0073]図9の(b)に戻って、予測コストデータ構造が算出されると、各帯域ごとのフロー計算が、処理論理がその帯域のすべての四分木区分を考察することによって進む。サブバンドのすべての四分木区分について、処理論理は、特定のサブバンド四分木区分のビット単位のコストを計算し、四分木区分の各葉ノード上の幾何学的フローを指定するビットコストを計算し、これら前の2つのコストを併せて加算することにより、特定の四分木の合計コストを計算する(処理ブロック912)。一実施形態では、四分木の各葉ノードが、特定のフローを有する1つ以上の元の係数のセグメントに対応する。一実施形態では、この特定のフローは、セグメント内の線状のフローである。別の実施形態では、このフローは、セグメント内のより高次の多項式フローである。他の種類のフローも使用され得る。一実施形態では、各特定のフローが、パラメータによって指定される。四分木区分のコストは、区分を指定するのに必要とされるビット数、区分の各セグメント内の特定のフローパラメータを指定するのに必要とされるビット数、および区分によって決定されるフローの部分と関連付けられる予測誤差を指定するビット単位のコストである。一実施形態では、各セグメント内の特定のフローパラメータを指定するコストは、ビットコスト対フローパラメータ情報を保持する表に基づいて求められる。処理論理は、最小限のコストを獲得する区分およびセグメントフローパラメータを、最適なフローとして選択する(処理ブロック913)。
【0063】
[0074]レートは、各帯域におけるフローおよび予測誤差を指定するのに必要とされるレートを含む。ひずみは、予測プロセスを反転させ、元の係数を形成し、逆ウェーブレット変換を行い、初期の画素領域画像に対する結果の不一致を計算することによって計算される。一実施形態では、不一致は、平均二乗誤差を算出することによって計算される。他の公知の方法も使用され得る。
【0064】
[0075]一実施形態では、近傍η(i,j)から獲得される画素値を使った予測子が、これらの値を予測重みと直線的に掛け合わせ、結果を合計することによって獲得される。一実施形態では、予測重みは、各(i=2p,j=2q)ごとに、その点において利用可能なデータに基づいて最適な重みを計算する統計的技法を使って、適応的に獲得される。例えば、自己回帰統計モデル、自己回帰移動平均統計モデル、共分散モデルなどに基づく予測子を用いることができる。また、Onur G.Guleryuz、「Nonlinear Approximation Based Image Recovery Using Adaptive Sparse Reconstructions and Iterated Denoising:Part I−Theory」、IEEE Transactions on Image Processingおよび、Onur G.Guleryuz、「Nonlinear Approximation Based Image Recovery Using Adaptive Sparse Reconstructions and Iterated Denoising:Part II−Adaptive Algorithms」、IEEE Transactions on Image Processingなどに開示されている、他のより洗練された予測子を使用することもできる。
【0065】
代替の実施形態
[0076]一実施形態では、フロー方向θ(i,j)は、D個の異なる値の1つであり、Dは、2、3、4などとすることができる。フローなしの元の係数が予測されず、これらの予測誤差がこれらの値と同じになるように、予約NULL方向を使って、フローなしが示される。これは、段落[0072]で概説した最適化プロセスにおいて、予測=0での可能なフロー値として使用され得る。
【0066】
[0077]一実施形態では、各四分木セグメント内のフローは、1次多項式(線状)、2次多項式、または3次多項式などである。
【0067】
[0078]一実施形態では、近傍構築で使用されるステップサイズを、1、2、3、……、または、例えば、21/2、2×21/2、3.1×21/2、……といった他の実数のシーケンスとすることができ、もしくは、各ステップごとに、新しい行または列に達するようにすることもできる。ステップの数は、1、2、3、4、5、……とすることができる。
【0068】
[0079]一実施形態では、方向と画素値の補間が、1次補間によって行われる。
【0069】
[0080]一実施形態では、所与のフローの操縦可能変換が、方向が幾何学的フローに基づいて決定される方向共分散行列を構築し、方向カルーネン・レーベ変換(KLT)を構築するためにこの行列の固有ベクトルを獲得し、方向KLTを操縦可能変換として使用することによって獲得される。
【0070】
[0081]一実施形態では、量子化が、デッドゾーン量子化器によって行われる。別の実施形態では、量子化が行われない。
【0071】
[0082]一実施形態では、ウェーブレット帯域が、粗い解像度から、より精密な解像度へと処理される。最も粗い解像度における各帯域の順序は、LL、LH、HL、HH、またはLL、HL、LH、HH、またはLL、HH、LH、HLなどとすることができる。別の実施形態では、より精密な解像度において、この順序は、LH、HL、HH、またはHL、LH,HHなどである。各帯域における係数を、トラバースラスタ走査し、または反転ラスタ走査することができる。一実施形態では、LL帯域が、ラスタ走査でトラバースされ、ある解像度の他の帯域が、タンデムラスタ走査でトラバースされる。
【0072】
コンピュータシステムの一例
[0083]図11は、本明細書で述べる各操作の1つ以上を実行し得る例示的コンピュータシステムを示すブロック図である。図11を参照すると、コンピュータシステム1100は、例示的クライアントまたはサーバコンピュータシステムを備え得る。コンピュータシステム1100は、情報をやりとりする通信機構またはバス1111と、情報を処理する、バス1111に結合されたプロセッサ1112とを備える。プロセッサ1112は、それだけに限らないが、例えば、Pentium(商標)、PowerPC(商標)、Alpha(商標)などといったマイクロプロセッサを含む。
【0073】
[0084]システム1100は、さらに、情報およびプロセッサ1112によって実行されるべき命令を格納する、バス1111に結合された(メインメモリと呼ばれる)ランダムアクセスメモリ(RAM)またはその他の動的記憶装置1104を備える。また、メインメモリ1104は、プロセッサ1112による命令の実行中に、一時変数またはその他の中間情報を格納するのにも使用され得る。
【0074】
[0085]また、コンピュータシステム1100は、静的状態情報およびプロセッサ1112のための命令を格納する、バス1111に結合された読取り専用メモリ(ROM)および/またはその他の静的記憶装置1106と、磁気ディスクや光ディスクとこれに対応するディスクドライブなどのデータ記憶装置1107も備える。データ記憶装置1107は、情報および命令を格納するためにバス1111に結合されている。
【0075】
[0086]コンピュータシステム1100は、さらに、コンピュータユーザに情報を表示する、バス1111に結合された、ブラウン管(CRT)や液晶ディスプレイ(LCD)などの表示装置1121に結合されていてもよい。また、プロセッサ1112に情報およびコマンド選択を伝達するための、英数字その他のキーを含む英数字入力装置1122がバス1111に結合されていてもよい。プロセッサ1112に方向情報およびコマンド選択を伝達し、ディスプレイ1121上のカーソル移動を制御するためにバス1111に結合された別のユーザ入力装置が、マウス、トラックボール、トラックパッド、スタイラス、カーソル方向キーなどのカーソル制御1123である。
【0076】
[0087]バス1111に結合され得る別の装置が、ハードコピー装置1124であり、これは、紙、フィルムまたは同種の媒体などの媒体上に情報を記録するのに使用され得る。バス1111に結合され得る別の装置が、電話機または手持ち式パーム機器との通信を行う有線/無線通信機能1125である。
【0077】
[0088]本発明では、システム1100および関連するハードウェアの構成部品のいずれか、またはすべてが使用され得ることに留意されたい。しかしながら、コンピュータシステムの他の構成は、これらの装置の一部または全部を含み得ることも理解することができる。
【0078】
[0089]以上の説明を読めば、当分野の技術者には、おそらく、本発明の多くの変更および改変が明らかになるであろうが、例示として図示し、説明しているどんな特定の実施形態も、決して、限定的とみなすためのものではないことを理解すべきである。したがって、様々な実施形態の詳細への言及は、それ自体で、本発明にとって必要不可欠であるとみなされる特徴だけを列挙している特許請求の範囲を限定するためのものではない。
【技術分野】
【0001】
[0001]本出願は、2005年12月21日に出願した、「Geometrical Image Representation and Compression」という名称の、対応する仮特許出願第60/752809号の優先権を主張し、参照により組み込むものである。
【0002】
[0002]本発明は、画像処理の分野に関する。より詳細には、本発明は、画像データの幾何学的画像表現を生成し、その新しい表現を使って画像処理操作を行うことに関する。
【背景技術】
【0003】
[0003]コンパクト画像表現は周知の問題である。ここ数年にわたって提案された典型的技法には、画像が、ベクトル辞書における画像のインデックスによって表されるベクトル量子化のような非線形法と、画像が、線形変換され、画像の線形変換係数によって表される線形表現(ウェーブレット変換ベースの表現、フーリエ変換ベースの表現、離散コサイン変換(DCT)ベースの表現など)が含まれる。線形表現は、しばしば、それらの表現の有効性をさらに拡張するために、単純な非線形処理を用いて増補される。
【0004】
[0004]コンパクト表現の最も重要な特性の1つは、これらが少数のパラメータを使って画像を近似することができることである。ある表現の近似率は、その表現においてより多くのパラメータが使用される際の表現誤差の低減として獲得することができる。例えば、この比率は、表現により多くのパラメータが加えられる際の、元の画像と所与の表現を使った元の画像の近似との間の平均二乗誤差の低減を計算することによって獲得することができる。いくつかの例外はあるが、高い近似率(所与の数のパラメータでより少ない誤差)を有する表現は、圧縮、雑音除去、および様々な他の用途においてよりよい成績をもたらすことが期待される。
【0005】
[0005]孤立した特異点を含む1次元(1D)信号について、最適な、またはほぼ最適な近似率を達成する線形表現の解決法が知られている。例えば、消失モーメントを有するコンパクトウェーブレットに基づく線形変換が、ほぼ最適な近似率を達成し得ることが知られている。しかしながら、2次元画像と共に使用するためにこれらの表現を2次元に直接的に一般化(例えば、2次元(2−D)ウェーブレット変換など)しても、最適状態には及ばないことが知られている。本明細書では、これらの直接的な一般化を第1世代線形表現と呼ぶ。
【0006】
[0006]第1世代線形表現および第1世代線形表現に基づく圧縮アルゴリズムは多数存在する。しかしながら、これらの解決法は、曲線に沿って特異点が現れる画像および映像に関しては、最適状態には及ばないことが知られている。すなわち、第1世代表現および第1世代表現に基づく技法は、特異点の周りに余分な係数またはパラメータを生じる。圧縮法の中には、係数を符号化するのに非常に適するものもあるが、これらの技法は、使用する第1世代表現がもたらす係数が符号化するには多すぎるため、結果として生じる性能は準最適である。
【0007】
[0007]2次元画像では、特異点が曲線に沿ってあるが、第1世代表現は、特異点を処理することだけしかできず、2次元においては、指数的に準最適である。図1の(a)〜(c)に、様々な次元の信号でのコンパクトウェーブレットの使用を示す。図1の(a)を参照すると、1D信号についてほぼ最適に至るコンパクトウェーブレットが示されており、図1の(b)には、特異点を有する2D信号についてほぼ最適に至るコンパクトウェーブレットが示されている。しかしながら、図1の(c)に示すように、コンパクトウェーブレットは、曲線上の特異点を有する2D信号では、準最適状態である。すなわち、図1の(c)の信号は、曲線に沿った特異点を表しており、このような信号上では、2次元ウェーブレット変換は、ほぼ最適な近似率を生じない。興味深いことに、現在の最新の画像圧縮法は、これらの第1世代表現に基づくものである。したがって、研究者らの間では、現在の最新の画像圧縮法準最適状態であることは周知である。
【0008】
[0008]最近では、第1世代表現の準最適性を改善することを目指す第2世代表現が導入されている。これらの技法は、典型的には、連続領域上で定義される画像の理想化された数学モデルを使って設計されている。他方、ディジタル画像は、離散グリッド上で定義され、これらの方法の基本的仮定の多くを満たすことができない。したがって、これらの技法は、目下のところ、第1世代の技法より指数的に優れていたとしても、最新の第1世代の技法を超えることができない。
【0009】
[0009]複素ウェーブレットなど、最善の第2世代表現の中には、拡張的/過完備であり、画像の画素数より多くのパラメータを生じるものがある。これらの余分なパラメータの多くは小さいが、事実上(レートひずみ的意味において)このような膨張的領域において圧縮を利用する圧縮法は、いまだ開発されていない。
【0010】
[0010]ディジタル画像の特性とより適合する他の表現、およびこれらの表現に基づく圧縮アルゴリズムが存在する。しかしながら、これらにはまだ、第1世代の技法に優る性能を欠いている。
【0011】
[0011]また、圧縮アルゴリズムの中には、方向予測を使って、特異点の周りにおける性能を改善しようとするものがある(例えば、ITU−TとISO/IEC JTC1のJoint Video Teamにおいて使用されるINTRAフレーム符号化法、「Draft ITU T Recommendation and Final Draft International Standard of Joint Video Specification (ITU−T Rec.H264 | ISO/IEC 14496−10 AVC)」、Joint Video Team (JVT) of ISO/IEC MPEG and ITU−T VCEG、JVT−G050、2003年3月などを参照)。このような解決法は、線形の、または線状の特異点を有する区分的に滑らかな画像モデルに対してのみ適用できる。さらに、これらの技法は、限られたクラスの予測子を使って大規模な領域を予測しようとするため、利用可能なデータの境界から離れた画素が、誤って予測される。同様に、特異点が、単に線状ではなく曲線に沿ってあるとき、または画像統計値が局所的に滑らかでないとき、これらの方法はうまくいかない。
【0012】
[0012]また、方向線上に変換を配置することによって方向予測子を一般化する方法も、線状の特異点に限定される。さらに、これらの方法は、様々なサイズのブロックに対してその圧縮アルゴリズムを設計する必要があり、これは、結果として生じる係数がエントロピ符号器を用いて符号化されるときに、非効率的結果をもたらす。
【発明の概要】
【課題を解決するための手段】
【0013】
[0013]本明細書では、幾何学的画像表現および/または圧縮の方法および装置を開示する。一実施形態において、方法は、画像データの幾何学的フローを求める工程を含む画像データの表現を生成するステップと、幾何学的フローを使って表現内のデータに対する画像処理操作を実行するステップとを含む。
【0014】
[0014]本発明は、以下に与えられる詳細な説明を読み、添付する本発明の様々な実施形態の図面を参照すれば、より十分に理解されるであろう。しかしながら、図面は、本発明を特定の実施形態だけに限定するものとみなすべきではなく、説明と理解のためにものにすぎない。
【図面の簡単な説明】
【0015】
【図1】(a)〜(c)は様々な次元の信号でのコンパクトウェーブレットの使用を示す図である。
【図2】2つの単純な画像、対応する関数、および可能な幾何学的フローを示す図である。
【図3】所与の方向角での場所の獲得を示す図である。
【図4】元の係数と増強係数とに基づく増補サブバンドの形成を示すブロック図である。
【図5】(a)および(b)は元の係数の様々な走査例を示す図である。
【図6】予測近傍の一例の形成を示す図である。
【図7】幾何学的フローを使った予測ベースの画像圧縮システムの一部である符号器の一実施形態を示すブロック図である。
【図8】幾何学的フローを使って予測を実行する予測プロセス論理の一実施形態を示すブロック図である。
【図9】(a)は予測コストデータ構造を計算するプロセスの一実施形態を示すフロー図であり、(b)は最適なフローの計算のプロセスの一実施形態を示すフロー図である。
【図10】幾何学的フローを使い、元の係数に基づいて予測を実行するプロセスの一実施形態を示すフロー図である。
【図11】本明細書で説明する操作のうちの1つ以上を実行し得る例示的コンピュータシステムを示すブロック図である。
【発明を実施するための形態】
【0016】
[0027]画像特異点(曲線に沿って現れるエッジおよびその他の特徴)の取り込みを可能にする新規の画像表現を開示する。一実施形態では、画像における固有の幾何学的特異点構造を特徴付けるのに役立つ画像適応的幾何学的フローフィールドが算出され、続いて、算出されたフローを条件とする画像画素が指定される。この条件指定は、画像を表現するのに必要なパラメータの数が大幅に低減されるような、画像画素の非常にコンパクトな取り込みを可能にする。
【0017】
[0028]一実施形態では、幾何学的フローの生成プラス条件付き画素指定の手順が変換領域において実行され、そこで、この手順は、「幾何学的フロープラス条件付き変換係数指定」になる。後者の手法は、提案の幾何学的フローベースの表現が、特定の用途に適する領域に利用されることを可能にする。
【0018】
[0029]画像表現は、様々な画像処理用途において使用することができ、これには、例えば、これらの用途の性能を改善するための画像圧縮や雑音除去が含まれる。
【0019】
[0030]一実施形態では、画像表現は、表面上の特異点を効率よく取り込むために、2次元より高い次元に一般化される。
【0020】
[0031]以下の説明では、本発明のより十分な説明を提供するために多くの詳細を示す。しかしながら、本発明は、これらの具体的詳細なしでも実施され得ることが、当分野の技術者には明らかであろう。別の例では、本発明が不明瞭にならないように、周知の構造および装置を、詳細にではなく、ブロック図として示す。
【0021】
[0032]以下の詳細な説明のいくつかの部分は、アルゴリズム、およびコンピュータメモリ内のデータビットに対する操作の記号的表現として提示する。これらのアルゴリズム的記述および表現は、データ処理分野の技術者が、その作業の内容を当分野の他の技術者に最も有効に伝えるのに使用される手段である。本明細書において、また一般に、アルゴリズムとは、所望の結果をもたらす、筋道の通ったステップのシーケンスであると考えられるものである。各ステップは、物理量の物理的操作を必要とするものである。必要であるとは限らないが、普通は、これらの量は、格納され、転送され、合成され、比較され、別の方法で操作されることのできる電気信号または磁気信号の形を取る。時として、これらの信号を、主に一般的用法により、ビット、値、要素、シンボル、文字、用語、数字などで呼ぶのが好都合なこともある。
【0022】
[0033]しかしながら、これらの用語および類似の用語は、すべて、適切な物理量と関連付けられるべきものであり、単に、これらの量に適用される便宜的表示にすぎないことに留意すべきである。以下の考察から明らかなように、特に具体的に言及しない限り、説明全体を通して、「処理する(processing)」または「算出する(computing)」または「計算する(calculating)」または「求める(determining)」または「表示する(displaying)」などといった用語を使用する考察は、コンピュータシステムのレジスタおよびメモリ内で物理(電子)量として表されるデータを操作し、コンピュータシステムメモリまたはレジスタまたは他のこのような情報記憶、伝送または表示装置内で同様に物理量として表される他のデータに変換するコンピュータシステム、または類似の電子計算処理装置の動作およびプロセスを指すものである。
【0023】
[0034]また、本発明は、本明細書における各操作を実行する装置にも関するものである。この装置は、必要な目的のために専用に構築されてもよく、コンピュータに格納されたコンピュータプログラムによって選択的に作動され、または再構成される汎用コンピュータを備えていてもよい。このようなコンピュータプログラムは、それだけに限らないが、それぞれ、コンピュータシステムバスに結合された、フロッピーディスク、光ディスク、CD−ROM、および光磁気ディスクを含む任意の種類のディスク、読取り専用メモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気または光学カード、もしくは電子命令を格納するのに適した任意の種類の媒体などといったコンピュータ可読記憶媒体に格納されていてもよい。
【0024】
[0035]本明細書で提示するアルゴリズムおよび表示は、どんな特定のコンピュータとも、その他の装置とも固有の関連性を持たない。様々な汎用システムが、本明細書の教示によるプログラムと共に使用されてもよく、必要な方法ステップを実行する、より専門化された装置を構築する方が好都合な場合もある。これらの様々なシステムに必要な構造は、以下の説明を読めば明らかになるであろう。加えて、本発明は、どんな特定のプログラミング言語との関連でも説明されない。本明細書で説明する発明の教示を実施するのに、様々なプログラミング言語が使用され得ることが理解される。
【0025】
[0036]機械可読媒体は、機械(コンピュータなど)によって読まれ得る形で情報を格納し、または伝送する任意の機構を含む。例えば、機械可読媒体には、読取り専用メモリ(「ROM」)、ランダムアクセスメモリ(「RAM」)、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気的、光学的、音響的またはその他の形の伝搬信号(搬送波、赤外線信号、ディジタル信号など)等々が含まれる。
【0026】
概要
[0037]幾何学的フローフィールドは、曲線に沿った不連続部分を有する区分的に均一な関数に対して定義されるフィールドと考えられてもよい。区分的に滑らかな関数に対して、幾何学的フローフィールドは、その曲線に沿って関数が正則である、すなわち、幾何学的フロー曲線によって接続される2点が、その曲線に沿って2点間で特異点を持たない曲線を叙述する。図2に、2つの単純な画像、対応する関数、および可能な幾何学的フローを示す。各フローに沿った画素は、そのフローに沿ってこれらの画素を隔てる特異点を持たない。区分的に均一な関数に対して、この定義は、関数または関数の近似率の予測可能性を使用するように拡張することができる。
【0027】
[0038]所与の画像について、多くのフローが存在し得る。一実施形態では、本明細書で開示する技法が、目的の用途に最適なフローを選択する。圧縮用途では、レートひずみの意味において最もコンパクトな表現をもたらすフローが選択される。
【0028】
[0039]一実施形態では、所与の画像について、画素(i,j)の方向角θ(i,j)を識別するフローフィールドが生成される。方向角θ(i,j)は、(i,j)の画素と、(i,j)から方向θ(i,j)に進むことによって獲得される(k,l)の画素とが、同じフロー上にあるような方向角である。図3に、所与のθ(i,j)について場所(k,l)を獲得することのできる方法を示す。この技法は、離散グリッド上で定義される画像のために設計されているため、様々な補間法およびステップサイズを利用して、(k,l)における画素値を求めることができる。言い換えると、(i,j)から方向θ(i,j)に進んだ結果として整数の場所がもたらされない(すなわち、非整数の場所がもたらされる)場合、適切な補間法を使って、(k,l)の画素の画素値を求めることができる。
【0029】
[0040](i,j)の画素について、(i,j)を通るフローに沿った画素の集合を含む画素近傍η(i,j)が求められる。例えば、この近傍は、θ(i,j)に基づき、(k,l)に到達するまでθ(i,j)の方向に進み、続いてθ(k,l)を使ってさらに進み、以下同様に、所定数のステップが取られるまで進むことによって求めることができる。この場合もやはり、非線形の場所に到達し、または方向が不明瞭であるときにはいつでも、適切な補間法を使って方向および場所を求めることができる。一実施形態では、近傍は、局所的に線形のフローに対応する方向θ(i,j)+πに進むなどによって、双方向に拡張される。局所的に2次、局所的に3次など、様々なフローの滑らかさの規則および仮定に基づく他の双方向拡張規則を用いることもできる。
【0030】
[0041]予測用途では、(i,j)の画素が、画素近傍η(i,j)内の画素値に基づいて予測される。この操作を画像内のすべての画素に反復し、予測誤差画像が算出される。圧縮など後続の操作が、この予測誤差画像を使って行われる。
【0031】
[0042]雑音除去用途では(i,j)の画素値が、画素近傍η(i,j)内の画素値に基づいて雑音除去される。この操作を画像内のすべての画素に反復し、雑音除去画像が算出される。
【0032】
[0043]操縦可能変換の用途では、画像が、おそらくは重なり合う領域に分割され、操縦可能変換、または方向変換が、各領域に対して評価され、変換の操縦/方向パラメータは、領域内の画素の計算されるフローパラメータに基づいて調整される。それだけに限らないが、圧縮や雑音除去といった後続の操作が、結果として生じる変換係数に対して実行される。
【0033】
[0044]過完備変換の用途では、例えば、カーブレットや複素ウェーブレットといった、方向過完備変換が、画像に対して評価される。フローパラメータを使って、過完備係数のうちのどれが画像に関連するかが指定される。次いで、これらの指定された係数が、それだけに限らないが、圧縮や雑音除去といった後続の操作で使用される。
【0034】
[0045]代替の実施形態では、増補された画素値の集合を含む画像が生成される。増補画素値集合は、適切な補間法を使って生成され得る。元の画像の予測、雑音除去、圧縮、過完備変換係数指定などを円滑に行わせるために、この増補画像に対して、フロー計算、近傍計算、領域決定および操縦可能変換決定のうちの1つ以上が実行される。
【0035】
[0046]一実施形態では、前述の操作が、変換係数のグループによって形成される画像に対し、変換領域において、まず、画像の所与の変換を計算し、変換係数によって形成される画像に対して前述の操作を繰り返すことによって実行される。
【0036】
[0047]例えば3次元画像/関数などといったより高次の画像/関数(映像シーケンス、磁気共鳴スライスによって描写されるボリュームなど)に対して、幾何学的フローは、所与のフロー表面上の2つの画素が、この表面上でこれらの画素を隔てるどんな特異点も持たないようなより高次の面を叙述する。次いで、前述の操作が、これらの面に沿って実行される。
【0037】
[0048]一実施形態では、幾何学的フローは、特定のクラスの平滑空間に対してフローを考察することによって最適化される。一実施形態では、四分木を使ったフローの区分が獲得され、四分木の各葉は、その葉に対応するセグメント内のフローを指定するパラメータを有し、パラメータは、このセグメント内のフローの滑らかさを表す。例えば、一実施形態では、パラメータは、セグメント内の1次多項式フロー、2次多項式フロー、3次多項式フローなどを表す。最適な四分木区分および各セグメント内の最適なパラメータは、圧縮用途におけるレートひずみ性能または雑音除去用途における雑音除去性能を最適化するように求めることができる。
【0038】
様々な実施形態に関する、より詳細な仕様
[0049]一実施形態では、画像に対して2次元ウェーブレット変換が適用される。この変換のサブバンドにおける変換係数が、フローベースの計算を行うための画像を形成する。
【0039】
[0050]ウェーブレット変換の各サブバンドはデシメーションによって形成されるため、増補サブバンドが、まず、計算され、各サブバンドが、各方向に2つずつアップサンプリングされる。すなわち、非デシメート(undecimated)ウェーブレット変換係数が計算される。非デシメート/アップサンプリング係数は、偶数のサンプル場所(imod2=0かつjmod2=0)に配置された元の係数と、残りのサンプル場所(imod2≠0またはjmod2≠0)の所の新しい係数を含む。図4は、元の係数と増補係数とに基づく増補サブバンドの形成を示すブロック図である。図4を参照すると、LHサブバンドが、増補LHサブバンドにアップサンプリングされている。本明細書では、アップサンプリングプロセス後に獲得される新しい係数を、元の係数に対して、増補係数と呼ぶ。
【0040】
[0051]一実施形態では、元の係数が、増補データ(増補係数など)を用いて処理される。一実施形態では、元の係数が、利用可能な元の係数の集合に元の係数を1度に1つずつ加えることによって、1度に1つずつ処理される。各係数を利用可能な集合に加えた後で、一連の操作が、利用可能な集合内の係数を使って実行される。一実施形態では、すべてのウェーブレット変換係数がゼロに設定されている画像から開始して、一度に1つの元の係数が、利用可能な元の係数の集合に加えられる。これと合わせて、一連の画素領域画像が構築され、各画像が、現在利用可能な元の係数だけを、残りの元の係数をゼロに設定して逆変換することによって形成される。元の係数は、例えば、各サブバンド内でのラスタ走査などにおいて利用可能な集合に加えられる。図5の(a)および(b)に、元の係数の様々な走査の例を示す。各走査で、元の係数が、走査によって決定される特定の順序で、利用可能な係数集合に加えられる。図5の(a)では、2LLサブバンドと2LHサブバンドがラスタ走査され、2HLバンドが反転ラスタ走査され、1HHバンドがジグザグ走査される。図5の(b)では、3つの帯域がタンデム走査される。3つのバンド内の係数は、連結ラスタ走査として走査され、各係数が並べて帯域に加えられる。構築された画素領域画像のシーケンスを、本明細書では、近似画像と呼ぶ。
【0041】
[0052]一実施形態では、所与のサブバンドにおいて、場所(p,q)の元の係数を加える前に、このサブバンドの増補係数推定値が、現在の近似画像、すなわち、(p,q)の元の係数ではなく、(p,q)の前のすべての元の係数を、残りの全ての元の係数をゼロに設定して逆変換することによって獲得される近似画像にシフトウェーブレット変換を適用することによって計算される。一実施形態では、シフトウェーブレット変換は、現在の近似画像が完全な近似であった場合に、実際の増補係数をもたらしたはずの変換である。したがって、増補係数の推定値は、より多くの元の係数がサブバンドに加えられ、よりよい近似画像が構築されるに従って、次第により正確になる。
【0042】
[0053]元の係数が加えられるたびに、別の近似画像が算出される。この近似画像を使って、増補係数と増補サブバンドが推定される。また、他の、より洗練された補間法およびデータ回復法を使って増補係数を生成することもできる。これらの方法には、Onur G.Guleryuz、「Nonlinear Approximation Based Image Recovery Using Adaptive Sparse Reconstructions and Iterated Denoising:Part I−Theory」、IEEE Transactions on Image Processing、Onur G.Guleryuz、「Nonlinear Approximation Based Image Recovery Using Adaptive Sparse Reconstructions and Iterated Denosing:Part II−Adaptive Algorithms」、IEEE Transactions on Image Processing、およびOnur G.Guleryuz、「Predicting Wavelet Coefficients Over Edges Using Estimates Based on Nonlinear Approximations」、Proc.Data Compression Conference、IEEE DCC−04、2004年4月が含まれる。
【0043】
[0054]所与のサブバンド内の場所(p,q)と、増補サブバンド内の場所(i=2p,j=2q)のところの元の係数について、フロー方向θ(i,j)が獲得され、係数の集合を含む近傍η(i,j)が構築される。この近傍は、増補サブバンドにおいて構築され、現在利用可能な元の係数の一部と、現在推定される増補係数の一部とを含む。図6に、場所(i=2p,j=2q)における予測近傍の一例の形成を示す。フロー方向が非整数の場所を指し示す場合、非整数の場所の周りの整数位置に位置する画素におけるフローを使って、近傍形成を伝播させることができる。さらに、一実施形態では、フロー方向が非整数の場所を指し示す場合、非整数の場所の周りの整数位置に位置する画素におけるフローが、近傍形成を伝播させるように補間される。
【0044】
予測用途および圧縮用途
[0055]幾何学的画像表現は、予測用途および圧縮用途で使用され得る。このプロセスは、操縦可能変換など、他の用途に一般化することができることに留意されたい。
【0045】
[0056]予測では、目的は、(i=2p,j=2q)元の係数について予測を行い、予測誤差を計算することである。よって、予測誤差係数が、元のサンプル点において形成される。その後、これらの予測誤差係数が、元の係数の代わりに圧縮される。伸張を行う復号器が、元の係数を再構築し、再構築された元の係数に逆ウェーブレット変換を適用し、画像を再構築することができるように、各元の係数ごとのフロー方向θ(i,j)が、因果関係を示すために予測誤差と共に送られる。一実施形態では、まず、係数を、その係数の前に送られた係数と、その係数の前に送られた係数を使って構築された増補係数とを使って予測するために、操作が、因果関係を示すようやり方で行われる。
【0046】
[0057]図7Aは、幾何学的フローを使った予測ベースの画像圧縮システムの一部である符号器の一実施形態を示すブロック図である。図7Aの各ブロックは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。
【0047】
[0058]図7Aを参照すると、ウェーブレット変換702が、画像データ701にウェーブレット変換を適用する。量子化ユニット703が、ウェーブレット変換702によって生成されるウェーブレット係数に対し量子化を行って、量子化係数を生成する。予測ユニット704が、各量子化係数ごとに予測を生成し、その予測を実際の量子化係数値と比較し、比較の結果に基づいて予測誤差係数を生成する。係数エントロピ符号器705が、予測誤差係数をエントロピ符号化し、結果として生じるビットストリーム、ビット706が復号器に送られる。予測で使用される幾何学的フローは、副情報707として復号器に送られる。
【0048】
[0059]図7Bは、復号器の一実施形態を示すブロック図である。復号器では、予測操作が反転され、量子化ウェーブレット係数が正しく再構築される。図7Bの各ブロックは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。
【0049】
[0060]図7Bを参照すると、係数エントロピ復号器713が、ビット712に対しエントロピ復号を行って、復号予測誤差係数を生成する。逆予測ユニット714が、復号予測誤差係数と、符号化時に使用された幾何学的フローを指定する副情報711を受け取り、係数値を生成する。逆量子化ユニット705が、これらの量子化係数値に対し逆量子化を行って、量子化されていない係数値を生成する。逆ウェーブレット変換ユニット716が、逆量子化係数値に逆変換を適用して、再構築画像データ717を生成する。
【0050】
[0061]一実施形態では、コーデックは、最初にウェーブレット係数を量子化せず、代わりに予測誤差係数を、例えば、DPCM方式において予測プロセス内に量子化を組み込むなどによって量子化する。
【0051】
[0062]一実施形態では、本明細書で述べる技法によって使用される元の係数が量子化された値を表すように、予測の前に、量子化操作が行われる。この量子化モードでは、増補係数が、フル解像度で、利用可能な量子化された元の係数に基づいて形成される。図8は、幾何学的フローを使って予測を実行する予測プロセス論理の一実施形態を示すブロック図である。図8を参照すると、増補係数算出ユニット802が、量子化ウェーブレット係数801を受け取り、前述のように増補係数803を算出する。フロー算出ユニット804が、増補係数を受け取り、幾何学的フローを算出する。予測ユニットの805が、増補係数803(一部は、その係数の幾何学的フローによって定義される元の係数のそれぞれの周りの増補係数の近傍など)と、フロー算出ユニット804からの算出フローとを使って、元の係数のそれぞれについて生成を行う。
【0052】
[0063]一実施形態では、予測誤差が、まず、フル解像度予測子を計算し、この予測子を量子化し、量子化された予測子を量子化された元の係数から差し引くことによって形成される。図10は、幾何学的フローを使用し、元の係数に基づいて予測を実行するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。
【0053】
[0064]図10を参照すると、プロセスは、(p,q)のところの元の係数を取り、これを、走査順序を使って利用可能な元の係数のリストに加える処理論理(処理ブロック1001)から開始する。次いで、処理論理は、付加を行うたびに、異なる、より精密な近似がもたらされるように、各付加後の画像近似を算出する(処理ブロック1002)。処理論理は、画像近似を使って、増補係数を計算し(処理ブロック1003)、増補サブバンドを形成する(処理ブロック1004)。
【0054】
[0065](p,q)の元の係数の前にすべての係数が加えられた後、場所(i=2p,j=2q)の増補バンドにおける元の係数に関する予測が行われる。一実施形態では、これは、以下の操作を使って行われる。まず、処理論理は、幾何学的フローと、フローがどのようにして補間されるべきか、値がどのようにして補間されるべきか、および近傍の構築のために取られるべきステップの数を求める近傍パラメータとを使って、予測において使用されるべき近傍η(i=2p,j=2q)を構築する(処理ブロック1005)。補間は、双一次補間、Sinc補間、またはより洗練された補間法とすることもできる。ステップ数は、1、2、5、10、20などとすることができる。次に、処理論理は、予測重みを、近傍から獲得される係数値と組み合わせて、予測値を計算する(処理ブロック1006)。処理論理は、予測値を量子化し(処理ブロック1007)、量子化された予測値を、(p,q)の元の係数から差し引いて、予測誤差係数を形成する(処理ブロック1008)。
【0055】
[0066]したがって、一実施形態では、量子化モードにおいて、圧縮符号器は、量子化された元の係数を、量子化された予測誤差係数と計算されたフローとを使って正確に回復することができるように、量子化された元の係数を取り込み、量子化された予測誤差係数を出力するものとみなすことができる。
【0056】
[0067]一実施形態では、予測操作の前に、予測で使用される増補係数の変調操作も行われる。この変調は、増補係数によって占められる高周波数帯域を、よりよい予測がもたらされ得る低周波数帯域にシフトする。例えば、増補LHバンド係数は、1つおきの列に(−1)を掛けることによってシフトすることができ、増補LHバンド係数は、1つおきの行に(−1)を掛けることによってシフトすることができ、増補HHバンド係数は、1つおきの行に(−1)を掛け、続いて1つおきの列に(−1)を掛けることによってシフトすることができる。
【0057】
[0068]ウェーブレット変換全体の予測誤差係数が計算されると、様々な公知の技法を使ってこれらを符号化し、復号器に送ることができる。例えば、JPEG2000に基づく係数エントロピ符号化法や、A.SaidおよびW.A.Pearlman、「A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees」、IEEEE.Trans.Circ.Syst.Video Tech.6、pp.243〜250ページ、1996年6月に記載されているような集合分割法や、その他の方法を使用することができる。
【0058】
[0069]一実施形態では、各帯域におけるフロー計算が、その用途に有利なやり方で行われる。一実施形態では、予測とそれに続く圧縮の用途で、各帯域内のフローが、最善のレートひずみ性能をもたらすように計算される。図9の(a)と(b)は、予測ベースの圧縮用途のための幾何学的フローである。
【0059】
[0070]図9の(b)は、最適なフローの計算のプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。
【0060】
[0071]図9の(b)を参照すると、プロセスは、様々な可能な予測のコストを保持するデータ構造を算出する処理論理(処理ブロック911)から開始する。次いで、このデータ構造を使って、最適なフローが算出される。図9の(a)は、予測コストデータ構造を計算するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(回路、専用論理など)、ソフトウェア(汎用コンピュータシステムまたは専用マシン上で走るものなど)、またはハードウェアとソフトウェアの組み合わせを備え得る処理論理によって実行される。図9の(a)を参照すると、処理論理は、各帯域の走査順序を使って利用可能な元の係数のリストに元の係数を加え(処理ブロック901)、付加するたびに画像近似を算出する(処理ブロック902)。処理論理は、シフト2Dウェーブレット変換を使って増補係数を計算し(処理ブロック903)、増補帯域を形成する(処理ブロック904)する際に、この画像近似を使用する。
【0061】
[0072]処理ブロック904において(p,q)の元の係数の前にすべての係数を加えた後で、処理論理は、(i=2p,j=2q)におけるすべての可能なフロー方向(すなわち、その場所の係数からの任意の可能な方向角)を使って、場所(i=2p,j=2q)における増補帯域における元の係数に関する予測を生成し、各フロー方向ごとの予測誤差を算出し、誤差対ビットコストのデータを保持する表を使って誤差を指定するビットコストを獲得し、フロー方向と対応するコストを、データ構造に格納する。
【0062】
[0073]図9の(b)に戻って、予測コストデータ構造が算出されると、各帯域ごとのフロー計算が、処理論理がその帯域のすべての四分木区分を考察することによって進む。サブバンドのすべての四分木区分について、処理論理は、特定のサブバンド四分木区分のビット単位のコストを計算し、四分木区分の各葉ノード上の幾何学的フローを指定するビットコストを計算し、これら前の2つのコストを併せて加算することにより、特定の四分木の合計コストを計算する(処理ブロック912)。一実施形態では、四分木の各葉ノードが、特定のフローを有する1つ以上の元の係数のセグメントに対応する。一実施形態では、この特定のフローは、セグメント内の線状のフローである。別の実施形態では、このフローは、セグメント内のより高次の多項式フローである。他の種類のフローも使用され得る。一実施形態では、各特定のフローが、パラメータによって指定される。四分木区分のコストは、区分を指定するのに必要とされるビット数、区分の各セグメント内の特定のフローパラメータを指定するのに必要とされるビット数、および区分によって決定されるフローの部分と関連付けられる予測誤差を指定するビット単位のコストである。一実施形態では、各セグメント内の特定のフローパラメータを指定するコストは、ビットコスト対フローパラメータ情報を保持する表に基づいて求められる。処理論理は、最小限のコストを獲得する区分およびセグメントフローパラメータを、最適なフローとして選択する(処理ブロック913)。
【0063】
[0074]レートは、各帯域におけるフローおよび予測誤差を指定するのに必要とされるレートを含む。ひずみは、予測プロセスを反転させ、元の係数を形成し、逆ウェーブレット変換を行い、初期の画素領域画像に対する結果の不一致を計算することによって計算される。一実施形態では、不一致は、平均二乗誤差を算出することによって計算される。他の公知の方法も使用され得る。
【0064】
[0075]一実施形態では、近傍η(i,j)から獲得される画素値を使った予測子が、これらの値を予測重みと直線的に掛け合わせ、結果を合計することによって獲得される。一実施形態では、予測重みは、各(i=2p,j=2q)ごとに、その点において利用可能なデータに基づいて最適な重みを計算する統計的技法を使って、適応的に獲得される。例えば、自己回帰統計モデル、自己回帰移動平均統計モデル、共分散モデルなどに基づく予測子を用いることができる。また、Onur G.Guleryuz、「Nonlinear Approximation Based Image Recovery Using Adaptive Sparse Reconstructions and Iterated Denoising:Part I−Theory」、IEEE Transactions on Image Processingおよび、Onur G.Guleryuz、「Nonlinear Approximation Based Image Recovery Using Adaptive Sparse Reconstructions and Iterated Denoising:Part II−Adaptive Algorithms」、IEEE Transactions on Image Processingなどに開示されている、他のより洗練された予測子を使用することもできる。
【0065】
代替の実施形態
[0076]一実施形態では、フロー方向θ(i,j)は、D個の異なる値の1つであり、Dは、2、3、4などとすることができる。フローなしの元の係数が予測されず、これらの予測誤差がこれらの値と同じになるように、予約NULL方向を使って、フローなしが示される。これは、段落[0072]で概説した最適化プロセスにおいて、予測=0での可能なフロー値として使用され得る。
【0066】
[0077]一実施形態では、各四分木セグメント内のフローは、1次多項式(線状)、2次多項式、または3次多項式などである。
【0067】
[0078]一実施形態では、近傍構築で使用されるステップサイズを、1、2、3、……、または、例えば、21/2、2×21/2、3.1×21/2、……といった他の実数のシーケンスとすることができ、もしくは、各ステップごとに、新しい行または列に達するようにすることもできる。ステップの数は、1、2、3、4、5、……とすることができる。
【0068】
[0079]一実施形態では、方向と画素値の補間が、1次補間によって行われる。
【0069】
[0080]一実施形態では、所与のフローの操縦可能変換が、方向が幾何学的フローに基づいて決定される方向共分散行列を構築し、方向カルーネン・レーベ変換(KLT)を構築するためにこの行列の固有ベクトルを獲得し、方向KLTを操縦可能変換として使用することによって獲得される。
【0070】
[0081]一実施形態では、量子化が、デッドゾーン量子化器によって行われる。別の実施形態では、量子化が行われない。
【0071】
[0082]一実施形態では、ウェーブレット帯域が、粗い解像度から、より精密な解像度へと処理される。最も粗い解像度における各帯域の順序は、LL、LH、HL、HH、またはLL、HL、LH、HH、またはLL、HH、LH、HLなどとすることができる。別の実施形態では、より精密な解像度において、この順序は、LH、HL、HH、またはHL、LH,HHなどである。各帯域における係数を、トラバースラスタ走査し、または反転ラスタ走査することができる。一実施形態では、LL帯域が、ラスタ走査でトラバースされ、ある解像度の他の帯域が、タンデムラスタ走査でトラバースされる。
【0072】
コンピュータシステムの一例
[0083]図11は、本明細書で述べる各操作の1つ以上を実行し得る例示的コンピュータシステムを示すブロック図である。図11を参照すると、コンピュータシステム1100は、例示的クライアントまたはサーバコンピュータシステムを備え得る。コンピュータシステム1100は、情報をやりとりする通信機構またはバス1111と、情報を処理する、バス1111に結合されたプロセッサ1112とを備える。プロセッサ1112は、それだけに限らないが、例えば、Pentium(商標)、PowerPC(商標)、Alpha(商標)などといったマイクロプロセッサを含む。
【0073】
[0084]システム1100は、さらに、情報およびプロセッサ1112によって実行されるべき命令を格納する、バス1111に結合された(メインメモリと呼ばれる)ランダムアクセスメモリ(RAM)またはその他の動的記憶装置1104を備える。また、メインメモリ1104は、プロセッサ1112による命令の実行中に、一時変数またはその他の中間情報を格納するのにも使用され得る。
【0074】
[0085]また、コンピュータシステム1100は、静的状態情報およびプロセッサ1112のための命令を格納する、バス1111に結合された読取り専用メモリ(ROM)および/またはその他の静的記憶装置1106と、磁気ディスクや光ディスクとこれに対応するディスクドライブなどのデータ記憶装置1107も備える。データ記憶装置1107は、情報および命令を格納するためにバス1111に結合されている。
【0075】
[0086]コンピュータシステム1100は、さらに、コンピュータユーザに情報を表示する、バス1111に結合された、ブラウン管(CRT)や液晶ディスプレイ(LCD)などの表示装置1121に結合されていてもよい。また、プロセッサ1112に情報およびコマンド選択を伝達するための、英数字その他のキーを含む英数字入力装置1122がバス1111に結合されていてもよい。プロセッサ1112に方向情報およびコマンド選択を伝達し、ディスプレイ1121上のカーソル移動を制御するためにバス1111に結合された別のユーザ入力装置が、マウス、トラックボール、トラックパッド、スタイラス、カーソル方向キーなどのカーソル制御1123である。
【0076】
[0087]バス1111に結合され得る別の装置が、ハードコピー装置1124であり、これは、紙、フィルムまたは同種の媒体などの媒体上に情報を記録するのに使用され得る。バス1111に結合され得る別の装置が、電話機または手持ち式パーム機器との通信を行う有線/無線通信機能1125である。
【0077】
[0088]本発明では、システム1100および関連するハードウェアの構成部品のいずれか、またはすべてが使用され得ることに留意されたい。しかしながら、コンピュータシステムの他の構成は、これらの装置の一部または全部を含み得ることも理解することができる。
【0078】
[0089]以上の説明を読めば、当分野の技術者には、おそらく、本発明の多くの変更および改変が明らかになるであろうが、例示として図示し、説明しているどんな特定の実施形態も、決して、限定的とみなすためのものではないことを理解すべきである。したがって、様々な実施形態の詳細への言及は、それ自体で、本発明にとって必要不可欠であるとみなされる特徴だけを列挙している特許請求の範囲を限定するためのものではない。
【特許請求の範囲】
【請求項1】
ウェーブレット変換を使って、画像データを第1の複数の係数に変換するステップと、
幾何学的フローを使って、係数の予測を生成し、前記予測に対応する予測誤差を生成するステップと、
前記幾何学的フローを指定する情報を生成するステップと、
前記予測誤差を符号化して圧縮ビットストリームを生成するステップと
を備える方法。
【請求項2】
前記第1の複数の係数に画像適応的幾何学変換を適用することによって、前記第1の複数の係数から第2の複数の係数を生成するステップをさらに備え、
予測を生成する前記ステップが、前記第1の複数の係数に関する予測を生成する工程を備え、
個々の予測誤差が、前記第1の複数の係数の1つと関連付けられる予測と、前記第1の複数の係数のそれぞれについて獲得される係数の近傍との差を表す請求項1に記載の方法。
【請求項3】
前記第1の複数の係数の前記1つの係数の前記幾何学的フローに基づいて、前記近傍に含めるための係数を選択するステップをさらに備える請求項2に記載の方法。
【請求項4】
幾何学的フローと近傍パラメータとに基づいて前記近傍を形成するステップをさらに備える請求項3に記載の方法。
【請求項5】
前記近傍内のすべての係数の幾何学的フローと近傍パラメータとに基づいて前記近傍を形成するステップをさらに備える請求項3に記載の方法。
【請求項6】
前記第1の複数の係数が複数のサブバンドを備え、さらに、前記第2の複数の係数を生成する前記ステップが、異なる走査パターンを使って、前記複数のサブバンドのうちの少なくとも2つにおける係数を走査する工程を備える請求項2に記載の方法。
【請求項7】
3つのサブバンド内の係数がタンデムラスタ走査として走査される請求項6に記載の方法。
【請求項8】
あるサブバンド内の係数がラスタ走査パターンで走査され、第2のサブバンドが反転ラスタ走査パターンで走査される請求項6に記載の方法。
【請求項9】
前記予測プロセスを実行する前に、前記第1の複数の係数内の係数を量子化するステップをさらに備える請求項1に記載の方法。
【請求項10】
前記予測誤差を符号化する前記ステップが、前記予測誤差をエントロピ符号化する工程を備える請求項1に記載の方法。
【請求項11】
幾何学的フローを指定する情報を送るステップと、
前記第2の複数の係数内のどの係数が有意であるかを示す第1の指示を送るステップと、
有意な係数の数を示す第2の指示を送るステップと、
前記予測誤差の圧縮バージョンを表す圧縮データを送るステップと
をさらに備える請求項1に記載の方法。
【請求項12】
システムによって実行されると、前記システムに、
ウェーブレット変換を使って、画像データを第1の複数の係数に変換するステップと、
幾何学的フローを使って、係数の予測を生成し、前記予測に対応する予測誤差を生成するステップと、
前記幾何学的フローを指定する情報を生成するステップと、
前記予測誤差を符号化して圧縮ビットストリームを生成するステップと
を備える方法を実行させる命令を格納する1つ以上のコンピュータ可読媒体を備える製造品。
【請求項13】
前記方法が、前記第1の複数の係数に画像適応的幾何学変換を適用することによって、前記第1の複数の係数から第2の複数の係数を生成するステップをさらに備え、予測を生成する前記ステップが、前記第1の複数の係数に関する予測を生成する工程を備え、個々の予測誤差が、前記第1の複数の係数の1つと関連付けられる予測と、前記第1の複数の係数のそれぞれについて獲得される係数の近傍との差を表す請求項12に記載の製造品。
【請求項14】
画像データを第1の複数の係数に変換するウェーブレット変換器と、
幾何学的フローを使って、係数の予測を生成し、前記予測に対応する予測誤差を生成する予測器であり、前記予測ユニットが前記幾何学的フローを指定する情報を生成する前記予測器と、
前記予測ユニットによって生成される予測誤差を符号化して圧縮ビットストリームを生成する符号器と
を備える圧縮器。
【請求項15】
前記予測器が、前記第1の複数の係数から増補係数の集合を生成し、前記増補係数の集合を使って、前記増補係数の集合と関連付けられる幾何学的フローに基づいて、前記第1の複数の係数に関する予測を生成する予測プロセスであり、前記予測プロセスの結果として前記予測誤差を出力する前記予測プロセスを実行する請求項14に記載の圧縮器。
【請求項16】
前記予測器が、前記第1の複数の係数内の係数の周りの近傍を形成する増補係数を使って個々の予測を生成する請求項15に記載の圧縮器。
【請求項17】
前記近傍の各々が、幾何学的フローと近傍パラメータとに基づいて形成される請求項16に記載の圧縮器。
【請求項18】
前記増補係数の集合が前記第1の複数の係数を含む請求項16に記載の圧縮器。
【請求項19】
前記符号器がエントロピ符号器を備える請求項14に記載の圧縮器。
【請求項20】
復号器が、前記情報を使って前記圧縮ビットストリームを復号した請求項14に記載の圧縮器。
【請求項21】
前記予測器による予測の前に前記第1の複数の係数内の係数を量子化する量子化器をさらに備える請求項14に記載の圧縮器。
【請求項22】
圧縮ビットを復号して復号データを生成する復号器と、
幾何学的フローを指定する情報を使って、前記復号データに対する逆予測を実行する逆予測器であり、第1の複数の係数を生成する前記逆予測器と、
前記第1の複数の係数に逆変換を適用して再構築画像データを生成する逆ウェーブレット変換と
を備える展開器。
【請求項23】
前記復号器がエントロピ復号器を備える請求項22に記載の展開器。
【請求項24】
前記逆ウェーブレット変換による前記逆変換の適用前に、前記第1の複数の係数の係数に対して逆量子化を実行する逆量子化器をさらに備える請求項22に記載の展開器。
【請求項1】
ウェーブレット変換を使って、画像データを第1の複数の係数に変換するステップと、
幾何学的フローを使って、係数の予測を生成し、前記予測に対応する予測誤差を生成するステップと、
前記幾何学的フローを指定する情報を生成するステップと、
前記予測誤差を符号化して圧縮ビットストリームを生成するステップと
を備える方法。
【請求項2】
前記第1の複数の係数に画像適応的幾何学変換を適用することによって、前記第1の複数の係数から第2の複数の係数を生成するステップをさらに備え、
予測を生成する前記ステップが、前記第1の複数の係数に関する予測を生成する工程を備え、
個々の予測誤差が、前記第1の複数の係数の1つと関連付けられる予測と、前記第1の複数の係数のそれぞれについて獲得される係数の近傍との差を表す請求項1に記載の方法。
【請求項3】
前記第1の複数の係数の前記1つの係数の前記幾何学的フローに基づいて、前記近傍に含めるための係数を選択するステップをさらに備える請求項2に記載の方法。
【請求項4】
幾何学的フローと近傍パラメータとに基づいて前記近傍を形成するステップをさらに備える請求項3に記載の方法。
【請求項5】
前記近傍内のすべての係数の幾何学的フローと近傍パラメータとに基づいて前記近傍を形成するステップをさらに備える請求項3に記載の方法。
【請求項6】
前記第1の複数の係数が複数のサブバンドを備え、さらに、前記第2の複数の係数を生成する前記ステップが、異なる走査パターンを使って、前記複数のサブバンドのうちの少なくとも2つにおける係数を走査する工程を備える請求項2に記載の方法。
【請求項7】
3つのサブバンド内の係数がタンデムラスタ走査として走査される請求項6に記載の方法。
【請求項8】
あるサブバンド内の係数がラスタ走査パターンで走査され、第2のサブバンドが反転ラスタ走査パターンで走査される請求項6に記載の方法。
【請求項9】
前記予測プロセスを実行する前に、前記第1の複数の係数内の係数を量子化するステップをさらに備える請求項1に記載の方法。
【請求項10】
前記予測誤差を符号化する前記ステップが、前記予測誤差をエントロピ符号化する工程を備える請求項1に記載の方法。
【請求項11】
幾何学的フローを指定する情報を送るステップと、
前記第2の複数の係数内のどの係数が有意であるかを示す第1の指示を送るステップと、
有意な係数の数を示す第2の指示を送るステップと、
前記予測誤差の圧縮バージョンを表す圧縮データを送るステップと
をさらに備える請求項1に記載の方法。
【請求項12】
システムによって実行されると、前記システムに、
ウェーブレット変換を使って、画像データを第1の複数の係数に変換するステップと、
幾何学的フローを使って、係数の予測を生成し、前記予測に対応する予測誤差を生成するステップと、
前記幾何学的フローを指定する情報を生成するステップと、
前記予測誤差を符号化して圧縮ビットストリームを生成するステップと
を備える方法を実行させる命令を格納する1つ以上のコンピュータ可読媒体を備える製造品。
【請求項13】
前記方法が、前記第1の複数の係数に画像適応的幾何学変換を適用することによって、前記第1の複数の係数から第2の複数の係数を生成するステップをさらに備え、予測を生成する前記ステップが、前記第1の複数の係数に関する予測を生成する工程を備え、個々の予測誤差が、前記第1の複数の係数の1つと関連付けられる予測と、前記第1の複数の係数のそれぞれについて獲得される係数の近傍との差を表す請求項12に記載の製造品。
【請求項14】
画像データを第1の複数の係数に変換するウェーブレット変換器と、
幾何学的フローを使って、係数の予測を生成し、前記予測に対応する予測誤差を生成する予測器であり、前記予測ユニットが前記幾何学的フローを指定する情報を生成する前記予測器と、
前記予測ユニットによって生成される予測誤差を符号化して圧縮ビットストリームを生成する符号器と
を備える圧縮器。
【請求項15】
前記予測器が、前記第1の複数の係数から増補係数の集合を生成し、前記増補係数の集合を使って、前記増補係数の集合と関連付けられる幾何学的フローに基づいて、前記第1の複数の係数に関する予測を生成する予測プロセスであり、前記予測プロセスの結果として前記予測誤差を出力する前記予測プロセスを実行する請求項14に記載の圧縮器。
【請求項16】
前記予測器が、前記第1の複数の係数内の係数の周りの近傍を形成する増補係数を使って個々の予測を生成する請求項15に記載の圧縮器。
【請求項17】
前記近傍の各々が、幾何学的フローと近傍パラメータとに基づいて形成される請求項16に記載の圧縮器。
【請求項18】
前記増補係数の集合が前記第1の複数の係数を含む請求項16に記載の圧縮器。
【請求項19】
前記符号器がエントロピ符号器を備える請求項14に記載の圧縮器。
【請求項20】
復号器が、前記情報を使って前記圧縮ビットストリームを復号した請求項14に記載の圧縮器。
【請求項21】
前記予測器による予測の前に前記第1の複数の係数内の係数を量子化する量子化器をさらに備える請求項14に記載の圧縮器。
【請求項22】
圧縮ビットを復号して復号データを生成する復号器と、
幾何学的フローを指定する情報を使って、前記復号データに対する逆予測を実行する逆予測器であり、第1の複数の係数を生成する前記逆予測器と、
前記第1の複数の係数に逆変換を適用して再構築画像データを生成する逆ウェーブレット変換と
を備える展開器。
【請求項23】
前記復号器がエントロピ復号器を備える請求項22に記載の展開器。
【請求項24】
前記逆ウェーブレット変換による前記逆変換の適用前に、前記第1の複数の係数の係数に対して逆量子化を実行する逆量子化器をさらに備える請求項22に記載の展開器。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2012−109957(P2012−109957A)
【公開日】平成24年6月7日(2012.6.7)
【国際特許分類】
【外国語出願】
【出願番号】特願2011−232908(P2011−232908)
【出願日】平成23年10月24日(2011.10.24)
【分割の表示】特願2008−547642(P2008−547642)の分割
【原出願日】平成18年12月21日(2006.12.21)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
【公開日】平成24年6月7日(2012.6.7)
【国際特許分類】
【出願番号】特願2011−232908(P2011−232908)
【出願日】平成23年10月24日(2011.10.24)
【分割の表示】特願2008−547642(P2008−547642)の分割
【原出願日】平成18年12月21日(2006.12.21)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
[ Back to top ]