(57)【要約】  スパース正規直交変換で圧縮を実行するための方法および装置が開示される。一実施形態において、この方法は、データブロックを受信するステップと、方向性構造に基づいて、データブロックを分類するステップと、ブロックの分類結果に基づいて、ブロックに適用するための複数の利用可能な方向性正規直交変換の１つを選択するステップと、複数の係数を生成するために選択された変換をブロックに適用することで、ブロックの圧縮バージョンを発生させるステップとを備える。【選択図】  図１Ａ
2010536263.tif 000002
【特許請求の範囲】
【請求項１】
データブロックを受信するステップと、
スパース構造に基づいて前記データブロックを分類するステップと、
前記ブロックの分類結果に基づいて、前記ブロックに適用するための複数の利用可能な方向性正規直交変換の１つを選択するステップと、
複数の係数を生成するために、前記ブロックに前記選択された変換を適用することで、前記ブロックの圧縮バージョンを発生させるステップと、
を備える方法。
【請求項２】
システムによる実行時、
データブロックを受信するステップと、
スパース構造に基づいて前記データブロックを分類するステップと、
前記ブロックの分類結果に基づいて、前記ブロックに適用するための複数の利用可能な方向性正規直交変換の１つを選択するステップと、
複数の係数を生成するために、前記ブロックに前記選択された変換を適用することで、前記ブロックの圧縮バージョンを発生させるステップと、
を備える方法を前記システムに実行させる命令を格納する１つ以上のコンピュータ読み取り可能記憶媒体を有する製造物品。
【請求項３】
圧縮コードストリームを受信するステップと、
前記圧縮コードストリームの係数群に対してブロック分類を決定するステップと、
前記ブロック分類に基づいて、複数の利用可能な方向性正規直交逆変換の１つを選択するステップと、
前記係数群に前記選択された逆変換を適用するステップと、
を備える復号化プロセス。
【発明の詳細な説明】
【優先権】
【０００１】
本願は、２００７年８月７日に出願された「Ｉｍａｇｅ  ａｎｄ  Ｖｉｄｅｏ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｕｓｉｎｇ  Ｓｐａｒｓｅ  Ｏｒｔｈｏｎｏｒｍａｌ  Ｔｒａｎｓｆｏｒｍｓ」という発明の名称の対応する米国仮特許出願第６０／９５４，５３８号の優先権を主張し、同出願を参照により本明細書に組み込まれる。
【技術分野】
【０００２】
本発明は、画像および映像圧縮／復元システムの分野に関し、特に、本発明は、圧縮および復元システムのスパース正規直交変換の使用に関する。
【背景技術】
【０００３】
画像圧縮およびハイブリッド映像圧縮は、フレームをブロックに分割し、各ブロックを予測し、ブロック変換を用いて残差を変換することからなる。映像圧縮アルゴリズムでは、一般に、前のフレームから動き補償を用いるのに対して、画像圧縮アルゴリズムでは、すでに符号化された隣接ブロックを用いて予測を生成してもよく、または、まったく予測を使用しなくてもよい。変換後、生成係数は量子化され、エントロピー符号化される。これまで長期にわたり、ＤＣＴは、自然画像に存在する相関性をうまく圧縮するため、画像および映像圧縮に最適な変換であった。ＤＣＴはほとんどの場合成功するが、変換されているブロックに特異点（すなわち、エッジ）がある場合、失敗する。このようなブロックは、水平方向または垂直方向に整列していない強いエッジを含む。その結果、ＤＣＴは、多くの非ゼロ係数を生成してブロックを表すことで、要求ビットレートが増大する。従来技術には多くの解決策があるが、これらには欠点がある。以下に、従来技術の解決策の欠点を一部要約する。従来の解決策には、ウェーブレットベースのものもあり、これは、ブロックベースではなく、最新のブロックベース映像および画像コーデックでの使用に適していない。ウェーブレットベースの従来技術の解決策では、周波数分解の粒状性が良好ではなく、すなわち、周波数選択性が制限され、圧縮の性能に悪影響を及ぼすこともある。従来の別の種の解決策では、すでに復号化されたデータ部分からの予測を使用する。これらのアルゴリズムセットは、動き補償ブロック境界を越えて残留信号が相関されない映像圧縮環境での使用に適していない。また、別の種の関連する従来の解決策に、変換のトレーニングがある。しかしながら、これらの解決策では、方向性が保たれるように変換に制約がかかる。これは、レート歪みを最適化するという意味では必ずしも当てはまらない場合もある。
【発明の概要】
【課題を解決するための手段】
【０００４】
本明細書において、スパース正規直交変換を用いて圧縮を行うための方法および装置が開示される。一実施形態において、この方法は、データブロックを受信するステップと、方向性構造に基づいて、データブロックを分類するステップと、ブロックの分類結果に基づいて、ブロックに適用するための複数の利用可能な方向性正規直交変換の１つを選択するステップと、複数の係数を生成するために選択された変換をブロックに適用することで、ブロックの圧縮バージョンを生じるステップとを備える。
【０００５】
本発明は、以下の詳細な記載および本発明のさまざまな実施形態の添付の図面から、さらに深く理解されるであろうが、これらは説明および理解を促すためのものであって、本発明を特定の実施形態に限定するものではない。
【図面の簡単な説明】
【０００６】
【図１Ａ】圧縮プロセスの一実施形態の流れ図である。
【図１Ｂ】反復同時分類および変換最適化プロセスの一実施形態の別の流れ図である。
【図２】レート歪み最適変換の選択および予測ブロックベースの圧縮プロセスの一実施形態の流れ図である。
【図３】ブロックベースの画像および映像エンコーダにおいて使用している変換を最適化するためのプロセスの一実施形態の流れ図である。
【図４】同じフレームのブロックから係数を予測するためのプロセスの一実施形態を例示する。
【図５】前のフレームのブロックから動き補償された係数を予測するための動き補償された係数予測プロセスの一実施形態を例示する。
【図６】一次元（１Ｄ）ベクトルと二次元（２Ｄ）ブロックとの間の直列化および非直列化を示す。
【図７】パワー順次係数からの係数のジグザグ走査マッピングの一例を示す。
【図８】ＥＺＷ／ＳＰＩＨＴのようなエントロピーコーダでの変換係数のウェーブレット順序付けの一例を示す。
【図９】四分木分割アルゴリズムを実行するためのプロセスの一実施形態の流れ図である。
【図１０】ノードおよび適応変換サイズを示す四分木分割を例示する。
【図１１】Ｎ＝９クラス、Ｌ＝４λ、Ｐ＝３の異なるブロックサイズの例示的なルックアップテーブル（ＬＵＴ）を示す。
【図１２】コンピュータシステムのブロック図である。
【図１３】反復プロセスの一実施形態の概略図を例示する。
【発明を実施するための形態】
【０００７】
圧縮応用分野において使用するための改良されたブロック変換について記載する。本明細書に記載する技術は、ブロックの分類に依存し、一実施形態において、対応するクラスに対して設計された最適変換を用いる。一実施形態において、ブロックの分類および変換の最適化は、トレーニングブロックセットを用いて一緒に実行される。
【０００８】
一実施形態において、提示された技術は、最適な分類を自動的に導き出す。曲線に沿って特異点を有する区分的に滑らかな画像の場合、１つのこのような分類は、画像の特異点に沿った相関性を利用する幾何学的フローに基づく。従来の変換では、幾何学を意識していないデザインであるため、このような特異点に沿うことができない。
【０００９】
圧縮フレームワークにおいて、生成された最適変換は、既知の離散コサイン変換（ＤＣＴ）に代わるものとして見なされうる。エンコーダは、レート歪みの最適性に応じて設計される最適変換またはＤＣＴでブロックを符号化するように選択しうる。
【００１０】
これらの技術は、静止画を圧縮するための画像圧縮において使用可能であり、または、映像を圧縮するための映像圧縮においても使用可能である。このような圧縮フレームワークにおいて、この技術は、各ブロックに使用する変換のインデックスをデコーダに通知するサイド情報を送信する。映像の圧縮時、この方法は、すべてのブロックに関するサイド情報を送信しないように選択してもよい。一実施形態において、これは、最適変換インデックスの予測可能性を見て、レート歪み解析を実行することによって、エンコーダで行われる。その結果、サイド情報が送信されないこともあれば、選択したブロックにのみサイド情報が送信されることもある。したがって、復号化中、ブロックの変換がエンコーダによって指定されなければ（サイド情報から省略）、デコーダは、前に復号化したフレームおよびそのブロックの動きベクトルを用いて、該当ブロックにどの変換インデックスを使用するかを決定しうる。
【００１１】
一実施形態において、本明細書に記載する変換／分類設計技術は、適切な変換を用いて各ブロックにおいて幾何学的フローをうまく取り込む。実験結果によれば、レート歪みの意味でも、視覚的な品質の意味でも、これらの技術の性能に有効であることが示されている。強いエッジがある場合、これらの技術では、設計された変換に自動的に方向性をもたせる。次に、エンコーダは、各ブロックに対してレート歪みの意味で最良の変換を選択し、変換識別子および係数を送信する。識別子送信のオーバーヘッドは、ブロックを表現するための非常に少数の係数を生成するために、変換の効率によって簡単に均衡がとられる。
【００１２】
以下の記載において、本発明をより完全に説明するために、多くの詳細を示す。しかしながら、当業者であれば、本発明は、これらの特定の詳細がなくとも実施されうることは明らかであろう。場合によっては、本発明を不明瞭にしないためにも、既知の構造およびデバイスを詳細に示さずにブロック図の形態で示すこともある。
【００１３】
以下の詳細な記載の一部は、コンピュータメモリ内のデータビットでの動作のアルゴリズムおよび記号表現で与えられる。これらのアルゴリズムの記述および表現は、データ処理分野に携わる者に用いられ、仕事の実体を当業者に最も効率的に伝えるための手段である。アルゴリズムは、本明細書において、さらには、一般に、首尾一貫した一連のステップから所望の結果を導き出すものと考えられる。これらのステップは、物理量の物理操作を要するものである。通常、必須ではないが、これらの物理量は、格納、転送、結合、比較、および他の方法で操作可能である電気信号または磁気信号の形をとる。これらの信号をビット、値、要素、記号、文字、用語、数などとして言及することは、主に、一般的な用法の理由から都合が良い場合があることが分かった。しかしながら、上記および同様の用語はすべて、適切な物理量と関連付けられ、これらの量に適用される利便性の良いラベルにすぎないことに留意されたい。以下の記述から明らかなように、他に特記しない限り、本明細書を通して、「処理」、「演算」、「計算」、「決定」、または「表示」などの用語を利用する記述は、コンピュータシステムのレジスタおよびメモリ内の物理（電子）量として表されるデータを操作し、コンピュータシステムメモリまたはレジスタ内、他のこのような情報格納、送信、または表示デバイス内の物理量として同様に表される他のデータに変換するコンピュータシステムまたは同様の電子コンピューティングデバイスのアクションおよびプロセスについて言及することを認識されたい。
【００１４】
本発明はまた、本明細書における動作を実行するための装置に関する。この装置は、要求された目的に合わせて特別に作られてもよく、または、コンピュータに格納されたコンピュータプログラムによって選択的にアクティブ化または再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、コンピュータ読み取り可能記憶媒体に格納されてもよく、この媒体は、例えば、フロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、および磁気ディスクを含む任意のタイプのディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光学カード、または電子命令を格納するのに適し、コンピュータシステムバスにそれぞれ結合される任意のタイプの媒体を含むが、これらに限定されるものではない。
【００１５】
本明細書に提示されたアルゴリズムおよびディスプレイは、任意の特定のコンピュータまたは他の装置に本質的に関係するものではない。本明細書の教示に従ったプログラムとともに、さまざまな汎用システムが使用されてもよく、または、要求された方法ステップの実行に特化した専用装置を構築することが都合が良い場合もある。これらの種々のシステムに要求される構造については、以下に記載する。さらに、本発明は、任意の特定のプログラミング言語を参照して記載しない。本明細書に記載するように本発明の教示を実施するために、種々のプログラミング言語が使用されてもよいことを認識されたい。機械読み取り可能媒体は、機械（例えば、コンピュータ）によって読み出し可能な形態で情報を格納または送信するための任意の機構を含む。例えば、機械読み取り可能媒体が、読み出し専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイスなどを含む。
【００１６】
［概要］
図１Ａは、圧縮プロセスの一実施形態の流れ図である。このプロセスは、ハードウェア（例えば、回路、専用ロジックなど）、ソフトウェア（例えば、汎用コンピュータシステムまたは専用マシンで実行）、またはそれら両方の組み合わせを備えてもよい処理ロジックによって実行される。
【００１７】
図１Ａを参照すると、このプロセスは、データをブロックに分割する処理ロジックから始まる（処理ブロック１０１）。データは、画像、映像、または画像や映像を表す他のデータ（例えば、変換係数）であってもよい。一実施形態において、ブロックは、圧縮されているイントラフレームの一部である。
【００１８】
一実施形態において、ブロックを表すデータは、変換係数のベクトルを備える。一実施形態において、変換係数のベクトルは、重複変換係数のベクトルを備える。別の実施形態において、変換係数のベクトルは、ウェーブレット変換係数のベクトルを備える。一実施形態において、ブロックはＫ×Ｋのサイズを有し、変換係数のベクトルは、Ｋ２×１の第２のサイズを有し、ここで、Ｋは整数である。
【００１９】
処理ロジックが、１つのデータブロックを受信し処理する（処理ブロック１０２）。複数のブロックを同時に処理するために、並列処理が用いられてもよい。次に、処理ロジックは、ブロック分類に基づいてデータを分類する（処理ブロック１０３）。一実施形態において、ブロックを分類する結果は、ブロック分類を表すブロック分類情報を含む。一実施形態において、ブロック分類の各々は、利用可能な変換の１つに関連付けられる。一実施形態において、ブロック分類および複数の変換は、レート歪みの意味で一緒に反復的に最適化される。
【００２０】
分類の結果に基づいて、処理ロジックが、ブロックに適用するために複数の利用可能なブロックベースの変換の１つを選択し（処理ブロック１０４）、複数の係数を生成するために、選択した変換をブロックに適用する（処理ブロック１０５）。
【００２１】
一実施形態において、処理ロジックはまた、任意に、ブロック分類情報および方向情報に基づいて、係数の予測を実行する（処理ブロック１０６）。
【００２２】
一実施形態において、利用可能な変換は、多方向性正規直交変換を含む。一実施形態において、トレーニングデータのブロックを分類し、変換を繰り返し適用する反復プロセスによって、１つ以上の変換が作成される。一実施形態において、利用可能な変換は、ＤＣＴ変換を含む。一実施形態において、利用可能な変換は、さまざまな量子化およびブロックサイズパラメータに最適化された１つ以上の変換を含む。一実施形態において、処理ロジックはまた、ブロック分類情報を符号化する（処理ブロック１０７）。一実施形態において、処理ロジックは、四分木を用いてブロック分類情報を符号化する。エンコーダの処理ロジックは、ブロック分類情報をデコーダに送信する（処理ブロック１０６）。任意に、処理ロジックは、前のフレームおよび現在のフレームに対して決定され送信されるサイド情報に基づいて、およびその時点までに送信された他の圧縮データ（例えば、変換係数、動きベクトル、すでに復号化されたフレームなどを指定するデータ）に基づいて、分類情報を条件付きで符号化する。
【００２３】
他の形態において、ブロックの分類結果は、ブロック分類情報を含み、任意に、デコーダの処理ロジックは、フレーム予測からブロックの分類を表すブロック分類情報を導き出す（処理ブロック１０９）。一実施形態において、デコーダの処理ロジックは、インターフレームの伸長時にブロック分類情報を導き出す。処理ロジックはまた、量子化係数を発生させるために、係数（または残差）を量子化する（処理ブロック１１０）。一実施形態において、量子化係数は、予測係数を備える。
【００２４】
量子化後、処理ロジックが、符号化前に変換係数を再順序付け（任意）、係数をエントロピー符号化する（処理ロジック１１１）。一実施形態において、利用可能な変換の各々は、別個のジグザグパターンに関連付けられ、再順序づけ変換係数は、変換係数に関連付けられたジグザグパターンを適用することで実行される。
【００２５】
一実施形態において、すべてのブロックが処理されるまで繰り返される。図１Ｂは、同時変換最適化およびブロック分類のプロセスの別の実施形態の流れ図である。このプロセスは、ハードウェア（例えば、回路、専用ロジックなど）、ソフトウェア（例えば、汎用コンピュータシステムまたは専用マシンで実行）、またはそれら両方の組み合わせを備えてもよい処理ロジックによって実行される。
【００２６】
図１Ｂを参照すると、このプロセスは、変換を設計するためにブロックサイズを選択し、画像および映像のトレーニングセットからトレーニングセットを生成する処理ロジックから始まる（処理ブロック１０１）。また、トレーニングブロックに初期分類が実行される。
【００２７】
次に、反復最適化プロセスが実行される。このプロセスでは、初期分類に最適な変換を推定した後、最適なスパース係数セットを推定する。係数が見つかると、所与の係数を用いて変換を最適化する。更新された変換を用いて、別のスパース係数セットを計算し、収束するまでこの反復が続けられる。
【００２８】
上記最適化プロセスの最適化において、レート歪みメトリックが使用される。上記反復が収束すると、ブロックは、同じレート歪みメトリックが最小限に抑えられるように再度分類される。新しい分類で、上記最適化が繰り返される。新しい変換が、新しい分類のために計算された後、分類は、レート歪みメトリックおよび新しい分類が収束するまで再度実行される。これらの動作をまとめて最適化すると、分類および変換が効率的に同時に最適化される。
【００２９】
一実施形態において、異なる量子化レベルおよび異なるブロックサイズに対して変換が最適化され、デコーダおよびエンコーダの両方のルックアップテーブルに格納される。一実施形態において、変換が最適化されると、任意の画像または映像を圧縮するさいに使用するために、エンコーダとデコーダとの間で変換が共有される。画像圧縮フレームワークにおいて、エンコーダで、各ブロックに分類情報を送ると、過大なオーバーヘッドを招く。一実施形態において、分類によって生じるオーバーヘッド量を制御するために、四分木構造が使用される。一実施形態において、この四分木は、レート歪みが最適化されるように作られる。映像圧縮フレームワークにおいて、一実施形態において、分類情報は、ブロックのすべてに対して送られない。例えば、エンコーダおよびデコーダは、各ブロックの分類を決定するために、またはより効率的に条件付きで符号化／復号化するために、動きベクトルと、前に復号化された参照フレームの対応データとの両方を使用しうる。一実施形態において、エンコーダはまた、ブロックのサブセットに対してのみ分類情報を送信するように選択するのに対して、他のブロックの分類は、動きベクトルおよび参照フレームを用いて決定される。エンコーダが、各ブロックの分類を決定すると、係数を生成するために対応する変換を用いる。
【００３０】
これらの係数は、例えば、Ｈ．２６４または任意の他のブロックベースの画像／映像コーデックなどの圧縮アルゴリズムにおいて使用されうる。
【００３１】
また、本明細書に記載する技術は、例えば、音声、医療用ボリューム画像などの高次元信号などの他のタイプの信号にも適用されうる。
【００３２】
スパース正規直交変換
一実施形態において、レート歪みの意味でのコストが、トレーニングデータにわたって最小限に抑えられるように、ｋ個のクラス（ｉ＝１．．．ｋ）に対して最適正規直交変換が演算される。例えば、歪みのみに基づいたコスト、レート／エントロピーのみに基づいたコスト、分類精度に基づいたコストなど、他のタイプのコストが使用されうる。Ｇｉ、１＜ｉ＜Ｎが、設計される予定の変換を示すとする。
【数１】
2010536263.tif 000003
が、ｉ番目のクラスとして分類されるトレーニングセットのｋ番目のブロックを示すとする。一実施形態において、
【数２】
2010536263.tif 000004
は、図６に示すように、ベクトルに直列化された２Ｄアレイである。Ｓｉは、ｉ番目のクラスとしてラベル付けしたブロックのセットを示すとする。一実施形態において、ＳｉおよびＧｉを反復的に演算する反復最適化方法が使用される。一実施形態において、反復最適化方法は、ブロックの初期分類から始まる。一実施形態において、初期分類は、トレーニングセットのブロックが発見的方法に基づいた初期分類が実行される各ブロックでの画像勾配に基づいて行われ、予測分類を決定するために画像勾配を使用し、初期Ｓｉを演算する。一実施形態において、変換Ｇｉは、Ｓｉによって決定されるような各クラスに対応するブロックを用いて、カールネン・ルーベ（Ｋａｒｈｕｎｅｎ−Ｌｏｅｖｅ）変換に初期化される。次に、反復最適化プロセスが始まる。
【００３３】
一実施形態において、変換は、以下のジョイント最適化問題に従って設計される。
【数３】
2010536263.tif 000005
【数４】
2010536263.tif 000006
は、所与のラグランジェ乗数λに対して変換Ｇｉによって生成された
【数５】
2010536263.tif 000007
の最適係数である。｜Ｃ｜０は、係数のＬ０ノルムを示し、Ｃの非ゼロ要素の数に等しい。
【００３４】
ブロックの各クラスに対して式（１）を解くと、生成されれば、そのクラスに対して最適な変換が得られる。反復最適化について開示し、以下のサブセクションにおいてさらなる詳細を記載する。
【００３５】
最初に、一実施形態において、最適化アルゴリズムは、所与の変換Ｇｉに対して最疎表現を求める。これは、一般的に、以下のように公式化されうる。
【数６】
2010536263.tif 000008
【００３６】
式（２）を解くには、
【数７】
2010536263.tif 000009
に等しいしきい値で
【数８】
2010536263.tif 000010
の成分をハードしきい値処理する。
【数９】
2010536263.tif 000011
とすると、最適
【数１０】
2010536263.tif 000012
の成分は以下の式で与えられる。
【数１１】
2010536263.tif 000013
【００３７】
一実施形態において、最適化プロセスの次のステップは、所与の係数に対して再現誤差を最小限に抑える最適な正規直交変換を決定することである。次に、
【数１２】
2010536263.tif 000014
はすべてのＧｉに対して一定である。各ｉに対して、１＜ｉ＜Ｎとなるように、以下の最小項が用いられる。
【数１３】
2010536263.tif 000015
【００３８】
式（３）は、
【数１４】
2010536263.tif 000016
のように書き表され、ここで、Ｔｒ｛．｝は行列のトレースを示す。上記式の項を並び替えると、以下の式になる。
【数１５】
2010536263.tif 000017
【００３９】
【数１６】
2010536263.tif 000018
および
【数１７】
2010536263.tif 000019
がＹｉのＳＶＤを示すものとする。ここで、ＵｉおよびＶｉは正規直交であり、Λｉは対角である。式（５）の解は、
【数１８】
2010536263.tif 000020
【００４０】
数式（１）は、コストが定常状態に達するまで順次、数式（２）および（３）に示すコスト関数の逐次最小化により解くことができる。
【００４１】
上述した最適化プロセスは、ブロックの初期分類に対して最初に実行される。別の実施形態において、ブロックの初期分類は、画像勾配ベースのアルゴリズムを用いて実行され、当業者に既知の方法でソーベル演算子を用いてブロック勾配を演算する。次に、勾配は、８方向の１つにマッピングされる。有力な方向が見つからなければ、ブロックは、方向性なしと分類され、ＤＣＴが使用される。収束後、決定された変換を用いて、処理ロジックがブロックを再分類する。一実施形態において、トレーニングブロックは、以下の最小化問題に従って再分類される。Ｘをトレーニングブロックとする。
【数１９】
2010536263.tif 000021
【００４２】
次に、分類および変換最適化の同時収束が達成されるまで、新しい変換セットを決定するために、上記最適化プロセス（式２〜６）において、再分類されたブロックが使用される。
【００４３】
このように、一実施形態において、初期分類後、まず変換および係数を最適化した後、レート歪みを最適な方法で最適変換の使用を再分類し、収束するまで反復的に変換Ｇiを再度最適化するために、反復最適化方法が用いられる。
【００４４】
一実施形態において、各ブロックに対して最適変換を決定するために、量子化デッドゾーンサイズおよびブロックサイズに従ってルックアップテーブル（ＬＵＴ）から選択されたＮ個の可能変換からの変換に、画像または動き補償ビデオフレームのブロックが割り当てられる。
【００４５】
一実施形態において、ブロックで各変換を用いるために、レート歪みコストが演算される。コストを最小化するものが選択される。映像圧縮の場合、レート歪みの最適化に加え、変換は、すでに復号化されたフレームおよび動きベクトルを用いて選択されてもよい。画像圧縮の場合、最適変換および適応ブロックサイズを送信するオーバーヘッドは、レート歪みが最適化されるように作られた四分木を用いて実行される。図１３は、反復プロセスの一実施形態の概略図を例示する。図１Ｂに、全体的な反復同時最適化プロセスの一実施形態の流れ図を示す。
【００４６】
一実施形態において、ブロックの分類により、方向性変換が得られ、したがって、分類は方向としても見なされる。
【００４７】
一実施形態において、変換に利用されるブロックは、ｐ×ｐブロックであるため、各変換は、ｐ２×ｐ２である。ｐは、４、５、８、１６などでありうる。一実施形態において、ｐ＝８である。一実施形態において、変換のサイズは、画像の異なる場所で異なるブロックサイズが使用されるように、変換のサイズが空間的に変更され、例えば、ｐ１＝４、ｐ２＝８、ｐ３＝１６である。ブロックサイズがｐ×ｐであれば、上記最適化プロセスの出力は、各分類ｉ＜Ｎに対してｐ２基底関数である。
【数２０】
2010536263.tif 000022
ここで、Ｇｉ（ｌ），ｌ＝１，．．．，Ｐ２は、変換Ｇｉの基底関数を示す。
【００４８】
最適化の完了後、一実施形態において、各クラスの基底関数は、応用に応じて順序付けられる。例えば、基底関数は、トレーニングセットにわたったパワー圧縮能力に応じて順序付けられる。
【数２１】
2010536263.tif 000023
をトレーニングセットＳｉにわたった変換Ｇｉのｎ番目の基底によって達成された圧縮を示すとする。
【数２２】
2010536263.tif 000024
【００４９】
さらに、基底関数は、
【数２３】
2010536263.tif 000025
のように順序付けられる。このようにして順序付けられた基底関数は、ジグザグ順序のＤＣＴ基底関数の順序付けと一致する。このように、一実施形態において、各方向性変換は、このように関連付けられた順序を有する。一実施形態において、順序付けられた変換係数は量子化され、逆ジグザグ走査されることで、ＤＣＴ係数のエントロピー符号化と同様の方法でエントロピー符号化されうる。エントロピーコーダに応じて、量子化係数は、エントロピー符号化などの前に関連するジグザグ順序付けを用いて再度順序付けられる必要がある。別の実施形態において、基底関数は、周波数成分に基づいてＤＣＴ基底関数にマッピングされうる。
【００５０】
量子化を用いるブロックベースの圧縮フレームワークで変換が用いられると、量子化ステップサイズおよびλは、式（２）の解に関係する。Δがゼロビン（すなわち、デッドゾーン）に量子化レベルを示すとすると、
【数２４】
2010536263.tif 000026
よって、λ＝Δ２である。
【００５１】
一実施形態において、異なるλ値に対して、変換が最適化される。さらに、各λに対して、異なるブロックサイズに対しても変換が最適化される。次に、多数の変換が生成され、ルックアップテーブル（ＬＵＴ）に格納される。
【数２５】
2010536263.tif 000027
ここで、Ｌは固有λの数であり、Ｐは応用によって望ましい最大ブロックサイズである。変換を生成するために本明細書に記載される技術は、ＬまたはＰを制限しない。図１１に、例示的なＬＵＴを示す。表記しやすいように、λｌおよびｐは、Ｇｉの上付き文字から下ろして表記している。ＬＵＴは、１＜ｉ＜Ｎ、１＜ｌ＜Ｌ、および２＜ｐ＜Ｐのすべてに対してＧｉ（λｌ，ｐ）を含む。量子化方法に応じて、Δはゼロビンに対応するデッドゾーンを示すものとする。また、λは、λ＝Δ２として演算され、ＬＵＴからλに対応する変換が使用される。こうして、これらの変換は量子化適応である。
【００５２】
一実施形態において、選択できる変換はＮ個ある。一実施形態において、Ｎ＝９である。一実施形態において、変換のうちの１つは、ＤＣＴであるように制約されることで、方向性変換が８つとＤＣＴが１つある。
【００５３】
一実施形態において、変換は重複が可能であり、これは当分野で既知である。このような場合、変換行列サイズは、ｑ２×ｐ２、ｑ＞ｐである。式（２〜９）に提示した公式は、最適重複変換を決定するために使用されうる。
【００５４】
一実施形態において、変換の公式を修正することによって、別の変換が用いられうる。さらに、最適Ｈｉを決定するために、同様の反復最適化方法が用いられうる。
【００５５】
別の実施形態において、最適化問題は、インプリメンテーションを達成するために対のギブンス回転およびリフティングパラメータの点で述べることもできる。このような場合、再度、同様の反復最適化が用いられうる。
【００５６】
一実施形態において、設計された最適変換は、以下にさらに詳細に記述するように、図２および図３に示すような予測を用いた、画像および映像のブロックベースの圧縮に対して用いられうる。
【数２６】
2010536263.tif 000028
は、ｉ番目のクラスとしてラベル付けされた画像またはビデオフレームのｎ番目のブロックを示すものとする。
【数２７】
2010536263.tif 000029
は、変換係数を示すものとする。予測係数
【数２８】
2010536263.tif 000030
は、各ブロックに対して最初に生成される。残差係数は、元の係数と予測係数の差
【数２９】
2010536263.tif 000031
として演算される。残差は量子化され
【数３０】
2010536263.tif 000032
、エントロピー符号化される。量子化は、スカラーまたはベクトルでありうる。量子化後、ブロックが再現され、再現係数
【数３１】
2010536263.tif 000033
として格納される。
【数３２】
2010536263.tif 000034
は、同じ画像のすでに符号化されたブロック、映像内の過去画像のすでに符号化されたブロック、またはそれらの両方の組み合わせを用いて生成されうる。
【００５７】
図２は、レート歪み最適変換の選択および予測ブロックベースの圧縮を形成するためのプロセスの一実施形態の流れ図である。このプロセスは、ハードウェア（例えば、回路、専用ロジックなど）、ソフトウェア（例えば、汎用コンピュータシステムまたは専用マシンで実行）、またはそれら両方の組み合わせを備えてもよい処理ロジックによって実行される。
【００５８】
図２を参照すると、ブロックＢに対して、およびすべての変換されたＧｉに対して、ｉがＮより小さい場合、プロセスは、変換Ｇｉを用いてブロックＢを変換して、以下の式、
【数３３】
2010536263.tif 000035
を用いて変形された係数を生じさせる処理ロジックから始まる（処理ブロック２０１）。次に、処理ロジックは、各ブロックに対して予測係数
【数３４】
2010536263.tif 000036
を生成する（処理ブロック２０２）。予測係数
【数３５】
2010536263.tif 000037
を生成した後、処理ロジックは、以下の公式
【数３６】
2010536263.tif 000038
に従って残差係数を演算し、以下の式
【数３７】
2010536263.tif 000039
に従って残差係数を量子化し（処理ブロック２０３）、これは元の係数と予測係数の差である。残差係数が演算され量子化されると、処理ロジックは、以下の式
【数３８】
2010536263.tif 000040
に従って歪みを演算し、エントロピーコーダＲｉに基づいてビットレートを演算する（処理ブロック２０４）。
【００５９】
他の形態において、ビットレートは、モデルを用いて推定されうる。
【００６０】
次に、処理ロジックは、レート歪みコストを演算する（処理ブロック２０５）。一実施形態において、レート歪みコストは、以下の式で演算される。
【数３９】
2010536263.tif 000041
【００６１】
処理ロジックは、最低レート歪みコストを与える変換として最適変換を選択する（処理ブロック２０６）。処理ロジックはまた、量子化された残差係数
【数４０】
2010536263.tif 000042
を、エントロピー符号化が行われるエントロピーコーダに渡し（処理ブロック２０７）、量子化された変換係数およびデコーダに使用される変換のインデックスを送信する（処理ブロック２０８）。
【００６２】
図３は、変換の選択を最適化し、ブロックベースの画像および映像符号化システムにおいて提案された変換を用いるためのプロセスの一実施形態の流れ図である。このプロセスは、ハードウェア（例えば、回路、専用ロジックなど）、ソフトウェア（例えば、汎用コンピュータシステムまたは専用マシンで実行）、またはそれら両方の組み合わせを備えてもよい処理ロジックによって実行される。
【００６３】
図３を参照すると、画像または映像フレームの各ブロックＢｋに対して、処理ロジックは、図１Ｂに記載したように、変換Ｇｉを選択する（処理ブロック３０１）。処理ロジックはまた、本明細書に記載されるように、デコーダに分類情報を送信する（処理ブロック３１０）。変換Ｇｉを選択した後、処理ロジックが、残差変換係数を演算する（処理ブロック３０２）。一実施形態において、残差変換係数は、以下の式に従って演算される。
【数４１】
2010536263.tif 000043
【００６４】
さらに、処理ロジックは、以下の式
【数４２】
2010536263.tif 000044
に従って係数を量子化する（処理ブロック３０３）。
【００６５】
係数の量子化後、処理ロジックは、後続ブロックの変換係数の予測において、ブロックＢｋデータが使用可能であるように、量子化されたデータを用いてブロックＢｋを再現し（処理ブロック３０４）、プロセスを繰り返す処理ブロック３０１に進む。
【００６６】
また、係数の量子化後、処理ロジックは、エントロピーコーダに従って係数を再順序付け（処理ブロック３０５）、処理するブロックがさらにあるかテストする（処理ブロック３０６）。さらなるブロックがあれば、プロセスは、処理ブロック３０１に進み、プロセスを繰り返す。さらなるブロックがなければ、処理ロジックは、量子化係数をエントロピー符号化する処理ブロック３０７に進む。エントロピー符号化後、処理ロジックは、符号化データをデコーダに送信する（処理ブロック３０８）。
【００６７】
一実施形態において、現在のブロックの係数が最初に予測される。画像圧縮の応用では、図４のように、すでに符号化されたブロックから予測され、映像符号化の応用では、この予測は、図５のように、すでに符号化されたフレームから動き補償により行われる。一実施形態において、画像圧縮の予測は、画像の現在のブロックの分類を用いて実行される。図４は、同じフレームのブロックから係数を予測するための係数予測プロセスの一実施形態を例示する。図４を参照すると、各記号は、別の係数を示し、斜影が付いたブロックにある各記号は、対応する記号から予測される。予測プロセスに関して、ブロックの方向は、画像の前に復号化されたブロックの対応する最も近いブロックを決定するために使用される。対応するブロックが、同じ分類を用いて符号化されなければ、ブロックのＤＣ係数のみが、隣接ブロックのすべてを平均化することによって予測される。対応する予測ブロックが、２つ以上のブロックと重なり合えば、両方のブロックは、現在のブロックと同じ方向になければならない。ここで、重複ブロックは、予測ブロックとして用いられる。分類情報が非方向性であると判明すれば、エンコーダは、予測に使用するのに適したブロックを探すために、前に符号化されたブロックを検索する。このブロックは、ブロック境界と重なり合いうる。一実施形態において、検索基準は、候補ブロックに見られる最適分類が、現在のブロックの分類と一致するようなものである。現在のブロックの分類と一致する候補ブロックが見つかると、検索は終了し、ブロックの係数が予測に使用される。一致するブロックが見つからなければ、最も近い分類が現在の分類の許容レベル内という条件で、最も近い分類のブロックが予測のために使用される。方向性分類の場合、この許容レベルは、例えば、１０度内、２３度内などの度数表記のものでありうる。非方向性分類の場合、トレーニングセットから近似許容値が決定される。一実施形態において、映像圧縮用の予測が、図５に示すように、動きベクトル情報を用いて実行される。フレームｆｋのブロック
【数４３】
2010536263.tif 000045
の場合（例えば、ブロック５０１）、参照フレームｆｌ：ｌ＜ｋの対応するブロックを探すために、動きベクトルが用いられる（例えば、ブロック５０２）。
【００６８】
一実施形態において、変形係数と予測係数との差は、使用するエントロピーエンコーダの種類に従って順序付けられる。この順序付けは、平均圧縮に従って実行される。Ｈ２６４のようなエントロピーコーダが使用されれば、圧縮順序係数は、図７に示すような２Ｄブロックに逆ジグザグ順序付けられ、エントロピーコーダに渡される。ＥＺＷ／ＳＰＩＨＴのようなエントロピーコーダが使用されれば、圧縮順序係数は、最初に、図７に示すように２Ｄブロックに逆ジグザグ順序付けられ、図８に示すような対応する周波数サブバンドに調整され（Ｘｉｏｎｇらの「Ａ  ＤＣＴ−ｂａｓｅｄ  Ｅｍｂｅｄｄｅｄ  Ｉｍａｇｅ  Ｃｏｄｅｒ」，ＩＥＥＥ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｌｅｔｔｅｒｓ，Ｖｏｌ．３，１１，ｐｐ．２８９−２９０，１９９６年１１月（参照により本明細書に組み込まれたものとする）に開示されているように）、エントロピーコーダに渡される。
【００６９】
一実施形態において、画像圧縮の場合、四分木が生成される。一実施形態において、四分木は、ブロック分類を符号化するために使用される。四分木の各ノードに方向が割り当てられ、同じ四分木ノードのブロックがすべて、その方向の変換を用いて符号化される。Ｒｕｐは、非分割の四分木ノードを送信するための係数および分類情報のビットレートを示し、Ｄｕｐは、非分割の四分木ノードのブロックのすべての係数の変換および量子化によって被る歪みを示すものとする。Ｒｐ、Ｄｐは、それぞれ、同じノードを４つの小さなノードに分割するためのビットレートおよび歪みの合計である。ＲｕｐおよびＲｐはまた、各ノードの方向の送信のオーバーヘッドを含む。これは、固定数のビットとして演算されうる。例えば、Ｒｐの場合、４つの新しい方向が生成されるため、オーバーヘッドは、
【数４４】
2010536263.tif 000046
でありうる。非分割の場合、オーバーヘッドは、一方向しかないため、
【数４５】
2010536263.tif 000047
でありうる。一実施形態において、四分木ノードは、適応変換サイズを用いて変換される。各ノードは、ノードのサイズに応じて、ＬＵＴの利用可能な変換サイズに基づいて、異なる変換サイズを使用しうる。例えば、ＬＵＴの最大変換サイズが１６×１６であれば、サイズ３２×３２のノードは、１６×１６ブロックを用いて変換される。ノードが１６×１６のサイズであれば、単一のブロック変換で十分である。さらに、係数のビットレートが、算術符号化の確率評価を用いて、または可変長符号化の符号語長から直接決定されうる。次に、四分木生成アルゴリズムは、分割または非分割のラグランジェコストを比較し、Ｄｐ＋λＲｐ＜Ｄｕｐ＋λＲｕｐであれば、ノードの分割を選択する。他のコストメトリックが使用されてもよい。
【００７０】
図９は、最適な四分木分割プロセスの一実施形態の流れ図である。このプロセスは、ハードウェア（例えば、回路、専用ロジックなど）、ソフトウェア（例えば、汎用コンピュータシステムまたは専用マシンで実行）、またはそれら両方の組み合わせを備えてもよい処理ロジックによって実行される。このプロセスは、最初のノードとして画像全体から開始される。Ｒｃｌａｓｓは、単一のノードに対して分類情報を送信するビットレートである。また、最良の分類を探すことは、変換されたサイズを探すことを伴い、コスト関数に基づいて同じレート歪みを比較する単純な問題である。
【００７１】
図９を参照すると、このプロセスは、所与の四分木ノード（９０１）に対して、ノードを４つの同じサイズのノードに分割する処理ブロックから始まり（処理ブロック９０２）、より小さな各ノードに対して最良の非分割分類を探し（９０３）、４つの同様のノードのコストを合計することによって分割ノードのコストを演算する（処理ブロック２０４）。一実施形態において、このコストは、以下の式のように計算される。
【数４６】
2010536263.tif 000048
その後、プロセスは、処理ブロック９０７に進む。
【００７２】
同時に、処理ロジックは、最良の非分割分類を探し（処理ブロック９０３）、非分割ノードのコストを演算する（処理ブロック９０６）。一実施形態において、非分割ノードのコストは、以下の式に従って演算される。
【数４７】
2010536263.tif 000049
その後、プロセスは、処理ブロック９０７に進む。
【００７３】
処理ブロック９０７で、分割のコストが低ければ、処理ロジックはノードを分割する。次に、分割されれば、処理ロジックは、同じアルゴリズムを新しく生成したノードに適用し（処理ブロック９０８）、プロセスは、処理ブロック９０１に進み、プロセスが繰り返される。
【００７４】
生成された四分木は、さまざまなノードサイズを有するものであってもよい。各ノードにおいて、最も適切な変換サイズが選択される。ノードが、ＬＵＴの最大利用可能な変換より大きければ、ノードは、多数のブロックとして変換される。図１０は、四分木分割における適応変換サイズの一例を示す。図１０を参照すると、太い線は、四分木ノードの境界を示し、矢印は、該当ブロックに用いられる変換の方向を示す。
【００７５】
一実施形態において、最大利用可能な変換サイズより大きい四分木ノードをカバーするために、複数の変換が使用される。例えば、図１０において、３２×３２の左下のノードは、１６×１６変換の４つのブロックを用いて符号化される。一実施形態において、映像圧縮の場合、サイド情報の符号化は、すでに符号化されたフレームに基づく。このような場合、フレームｆｋのブロック
【数４８】
2010536263.tif 000050
が符号化されているとき、フレームｆｌ：ｌ＜ｋの対応するブロックは、動きベクトルを用いて求められる。
【数４９】
2010536263.tif 000051
は、フレームｆｌの対応するブロックを示すものとする。次に、
【数５０】
2010536263.tif 000052
の分類は、
【数５１】
2010536263.tif 000053
に対して演算された分類を条件にしてエントロピー符号化される。別の実施形態において、エンコーダは、
【数５２】
2010536263.tif 000054
に対して演算された分類を用いる。したがって、サイド情報は完全に削除されうる。
【００７６】
一実施形態において、上述した符号化プロセスの逆が、デコーダによって実行される。例えば、図１Ａの流れ図の動作の逆は、図１Ａに示すように符号化されたデータを復号化するために実行される。これは、当業者に既知のものである。
【００７７】
本発明の実施形態は、ブロックベースの映像および画像コーダに対応しうる。本発明の実施形態は、さまざまな初期分類に適用可能であり、一次幾何学的フローに限定されない。一実施形態において、変換最適化は、分類と一緒に実行される。変換設計は、演算の複雑性を低減するために、分離可能変換などのさらなる正規化に開かれている。典型的な画像での本発明の実施形態のレート歪み性能および典型的な画像での本発明の実施形態の視覚的な品質は、従来技術より優れている。
【００７８】
コンピュータシステムの例
図１２は、本明細書に記載する動作の１つ以上を実行するものであってもよい例示的なコンピュータシステムのブロック図である。図１２を参照すると、コンピュータシステム１２００は、例示的なクライアントまたはサーバコンピュータシステムを備えてもよい。コンピュータシステム１２００は、情報通信用の通信機構またはバス１２１１と、バス１２１１に結合された情報処理用のプロセッサ１２１２とを備える。プロセッサ１２１２は、マイクロプロセッサを含むが、例えば、Ｐｅｎｔｉｕｍ（商標）、ＰｏｗｅｒＰＣ（商標）、Ａｌｐｈａ（商標）などのマイクロプロセッサに限定されるものではない。
【００７９】
システム１２００は、ランダムアクセスメモリ（ＲＡＭ）、またはプロセッサ１２１２によって実行される情報および命令を格納するための、バス１２１１に結合された他の動的記憶デバイス１２０４（メインメモリと呼ぶ）をさらに備える。メインメモリ１２０４はまた、プロセッサ１２１２によって命令を実行している間、一時的な変数または他の中間情報を格納するために使用されてもよい。
【００８０】
コンピュータシステム１２００はまた、プロセッサ１２１２の静的情報および命令を格納するためのバス１２１１に結合された読み出し専用メモリ（ＲＯＭ）および／または他の静的記憶デバイス１２０６と、磁気ディスクまたは光ディスクおよびそれに対応するディスクドライブなどのデータ記憶デバイス１２０７とを備える。情報および命令を格納するためのデータ記憶デバイス１２０７が、バス１２１１に結合される。
【００８１】
コンピュータシステム１２００が、コンピュータユーザに情報を表示するための、バス１２１１に結合された陰極線管（ＣＲＴ）または液晶ディスプレイ（ＬＣＤ）などのディスプレイデバイス１２２１にさらに結合されてもよい。英数字および他のキーを含む英数字入力デバイス１２２２が、プロセッサ１２１２に情報およびコマンド選択を通信するためにバス１２１１に結合されてもよい。追加のユーザ入力デバイスは、方向情報およびコマンド選択をプロセッサ１２１２に通信し、ディスプレイ１２２１上でのカーソルの動きを制御するために、バス１２１１に結合された、マウス、トラックボール、トラックパッド、スタイラス、またはカーソル方向キーなどのカーソル制御１２２３である。
【００８２】
バス１２１１に結合されてもよい別のデバイスは、紙、フィルム、または同様のタイプの媒体などの媒体上に情報をマーキングするために使用されてもよいハードコピーデバイス１２２４である。バス１２１１に結合されてもよい別のデバイスは、電話またはハンドヘルドパームと通信を行うための有線／無線通信能力１２２５である。本発明において、システム１２００のコンポーネントの任意またはすべておよび関連するハードウェアが使用されてもよいことを留意されたい。しかしながら、コンピュータシステムの他の構成が、デバイスの一部またはすべてを含んでもよいことを認識されうる。
【００８３】
本発明の多くの変更例および修正例は、前述した記載を読んだ後であれば、当業者に明らかであろうが、例示的に図示および記載した任意の特定の実施形態は、制限的なものと見なされるべきではないことを理解されたい。したがって、さまざまな実施形態の詳細を参照することは、本発明に必須であると見なされる特徴のみを列挙した特許請求の範囲を限定することを意図していない。
【図１Ａ】
2010536263.tif 000055
【図１Ｂ】
2010536263.tif 000056
【図２】
2010536263.tif 000057
【図３】
2010536263.tif 000058
【図４】
2010536263.tif 000059
【図５】
2010536263.tif 000060
【図６】
2010536263.tif 000061
【図７】
2010536263.tif 000062
【図８】
2010536263.tif 000063
【図９】
2010536263.tif 000064
【図１０】
2010536263.tif 000065
【図１１】
2010536263.tif 000066
【図１２】
2010536263.tif 000067
【図１３】
2010536263.tif 000068
【手続補正書】
【提出日】平成22年7月1日(2010.7.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データブロックを受信するステップと、
スパース構造に基づいて前記データブロックを分類するステップと、
前記ブロックの分類結果に基づいて、複数の利用可能な方向性正規直交変換の１つを選択して前記ブロックに適用するステップと、
前記ブロックに前記選択された変換を適用して複数の係数を生成し、もって、前記ブロックの圧縮バージョンを発生させるステップと、
を備える方法。
【請求項２】
前記ブロックの分類結果が、前記ブロックの分類を表すブロック分類情報を含む、請求項１に記載の方法。
【請求項３】
前記ブロック分類情報をデコーダに送信するステップをさらに備える、請求項２に記載の方法。
【請求項４】
前記ブロックが、圧縮されるイントラフレームの部分である、請求項３に記載の方法。
【請求項５】
四分木を用いて前記ブロック分類情報を符号化するステップをさらに備える、請求項２に記載の方法。
【請求項６】
前記ブロックの分類結果が、ブロック分類情報を含み、フレーム予測から前記ブロックの分類を表す前記ブロック分類情報を導き出すデコーダをさらに備える、請求項２に記載の方法。
【請求項７】
前記過去フレームに対して決定され送信されたサイド情報に基づいて、前記分類情報を予測し、条件付きで符号化するステップをさらに備える、請求項６に記載の方法。
【請求項８】
前記デコーダが、インターフレームの復元時、前記ブロック分類情報を導き出す、請求項６に記載の方法。
【請求項９】
前記ブロック分類情報および方向情報に基づいて、ブロックベースの係数予測を実行す
るステップをさらに備える、請求項２に記載の方法。
【請求項１０】
前記ブロックを表す前記データが、変換係数のベクトルを備える、請求項１に記載の方法。
【請求項１１】
前記変換係数のベクトルが、重複変換係数のベクトル、ウェーブレット変換係数のベクトル、フーリエ変換係数のベクトルからなる群の１つを備える、請求項１０に記載の方法。
【請求項１２】
前記ブロックが、Ｋ×Ｋのサイズを有し、前記変換係数のベクトルが、Ｋ２×１の第２のサイズを有し、ここで、Ｋが整数である、請求項１１に記載の方法。
【請求項１３】
前記複数の方向性変換の１つ以上の変換が、トレーニングデータのブロックが分類された後に、変換の適用を繰り返し施す反復プロセスによって生じる、請求項１に記載の方法。
【請求項１４】
前記複数の利用可能な変換が、ＤＣＴ変換を含む、請求項１に記載の方法。
【請求項１５】
前記複数の利用可能な変換が、さまざまな量子化およびブロックサイズパラメータに最適化された変換を備える、請求項１に記載の方法。
【請求項１６】
前記ブロック分類の各々が、前記複数の利用可能な変換の１つに関連付けられる、請求項１に記載の方法。
【請求項１７】
前記ブロックの分類および複数の変換が、レート歪みの意味で一緒に反復的に最適化される、請求項１６に記載の方法。
【請求項１８】
符号化の前に変換係数を再順序付けするステップをさらに備える、請求項１に記載の方法。
【請求項１９】
前記複数の利用可能な変換の各々が、別個のジグザグパターンに関連付けられ、変換係数を再順序付けするステップをさらに備えることが、前記変換係数に関連付けられたジグザグパターンを適用する工程を備える、請求項１８に記載の方法。
【請求項２０】
量子化された係数を生じるために、前記複数の係数を量子化するステップと、
前記量子化された係数をエントロピー符号化するステップと
をさらに備える、請求項１８に記載の方法。
【請求項２１】
前記量子化された係数が、予測された係数を備える、請求項２０に記載の方法。
【請求項２２】
前記ブロックに対して予測係数を生成するステップと、
前記予測係数と前記複数の係数との間の差として残差係数を演算するステップと、
前記残差係数を量子化して、量子化された係数を生じさせるステップと、
前記量子化された係数をエントロピー符号化するステップと
をさらに備える、請求項１８に記載の方法。
【請求項２３】
前記データブロックが、画像および映像からなる群から選択されるものを備える、請求項１に記載の方法。
【請求項２４】
スパース構造に基づいて前記データブロックを分類するステップが、ターゲット歪みレ
ベルに基づいてラグランジェ乗数λを選択して、前記ブロックを分類し、前記ブロックに対する等式を解く工程を備え、前記等式が、
【数１】
2010536263.tif 000069
であり、式中、Ｘはブロック、Ｇｊは変換、Ｃはブロックの係数である、請求項１に記載の方法。
【請求項２５】
設計された変換および方向性分類情報を含むサイド情報を生成するステップと、
前記サイド情報をデコーダに送信するステップと
をさらに備える、請求項１に記載の方法。
【請求項２６】
所定の方法をシステムに実行させる命令を格納する１つ以上のコンピュータ読み取り可能記憶媒体を有する製造物品であって
前記方法は、
前記システムによる実行時、
データブロックを受信するステップと、
スパース構造に基づいて前記データブロックを分類するステップと、
前記ブロックの分類結果に基づいて、複数の利用可能な方向性正規直交変換の１つを選択して前記ブロックに適用するステップと、
前記ブロックに前記選択された変換を適用して複数の係数を生成し、もって、前記ブロックの圧縮バージョンを発生させるステップと、
を備える、製造物品。
【請求項２７】
圧縮コードストリームを受信するステップと、
前記圧縮コードストリームの係数群に対してブロック分類を決定するステップと、
前記ブロック分類に基づいて、複数の利用可能な方向性正規直交逆変換の１つを選択するステップと、
前記係数群に前記選択された逆変換を適用するステップと、
を備える復号化プロセス。
【請求項２８】
フレーム予測からブロック分類情報を導き出すステップをさらに備える、請求項２７に記載の復号化プロセス。
【請求項２９】
前記ブロック分類を表す情報が、四分木を用いて符号化される、請求項２７に記載の復号化プロセス。
【国際調査報告】
2010536263.tif 000070
2010536263.tif 000071
2010536263.tif 000072