(57)【要約】  本発明は、現ブロックの因果的隣接領域に位置する画素と関連付けられた少なくとも再構成された画像データを備えたデータのベクトルの第１のディクショナリの原子に分解する、反復ステップを備えた現ブロックを符号化する方法に関する。各反復において原子に分解するステップが、  原子の前記第１のディクショナリにおける第１の原子を選択するステップ（３２）と、  第１の原子がテクスチャ化された原子である場合、第１の原子に関連付けられたパッチと現残差ベクトルの間の位相相関を適用するステップ（３４、３４０）と、  パッチから、残差ベクトルと最も強い相関関係がある部分を少なくとも抽出ステップ（３４、３４２）を含み、抽出された部分は第２の原子を構成し、当該ステップは更に、  第１の原子および第２の原子から、現残差ベクトルと最も強い相関関係がある原子を選択するステップ（３６）と  選択された原子により、残差ベクトルを更新するステップ（３８）を含んでいる。
2013524597.tif 000002
【特許請求の範囲】
【請求項１】
画像のシーケンスの現ブロックを符号化する方法であって、前記方法は、
現ブロックに因果的に隣接して配置された画素に関連付けられた少なくとも再構成された画像データを備えたデータのベクトルを、第１のディクショナリの原子に反復して分解するステップ（５２）であって、前記第１のディクショナリは、分析上の原子およびテクスチャ化された原子を備える、前記ステップと、
前記現ブロックに対応する前記分解されたベクトルデータから抽出するステップ（５４）であって、前記抽出されたデータは予測ブロックを構成する、前記ステップと、
前記現ブロックから前記予測ブロックを抽出することにより、残差ブロックを決定するステップ（５６）と、
前記残差ブロックを符号化するステップ（５８）と、を含み、
前記符号化方法は、各反復において原子に分解する前記ステップが、
原子の前記第１のディクショナリにおける第１の原子を選択するステップ（３２）と、
前記第１の原子がテクスチャ化された原子である場合、前記第１の原子に関連付けられたパッチと現残差ベクトルの間の位相相関を適用するステップ（３４、３４０）と、
前記パッチから、前記残差ベクトルと最も強い相関関係がある部分を少なくとも抽出するステップ（３４、３４２）であって、前記抽出された部分は第２の原子を構成する、前記ステップと、
前記第１の原子および前記第２の原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択するステップ（３６）と
前記選択された原子により、前記残差ベクトルを更新するステップ（３８）と、を含む、前記方法。
【請求項２】
前記第２のディクショナリのパッチは円対称性である、請求項１に記載の符号化方法。
【請求項３】
前記第２のディクショナリのパッチは、それらのコンテンツに依拠する形態を有している、請求項１または２に記載の符号化方法。
【請求項４】
前記第２のディクショナリは、異なるサイズの少なくとも２つのパッチを備えている、請求項１〜３のいずれかに記載の符号化方法。
【請求項５】
前記抽出のステップ（３４、３４２）は、前記残差ベクトルに最も強い相関関係があるＮ個の部分の抽出を含み、抽出された各部分は再位相化原子を構成し、
前記選択のステップは、前記第１の原子および前記再位相化原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択することを含む、請求項１〜４のいずれかに記載の符号化方法。
【請求項６】
ストリーム形式により生じる画像のシーケンスの現ブロックを再構成する方法であって、
前記ストリームから前記現ブロックについて残差ブロックを復号するステップ（６０）と、
前記現ブロックに因果的に隣接して配置された画素に関連付けられた少なくとも再構成された画像データを備えたデータのベクトルを、第１のディクショナリの原子に反復して分解するステップ（６２）であって、前記第１のディクショナリは、分析上の原子およびテクスチャ化された原子を備える、前記ステップと、
前記現ブロックに対応する前記分解されたベクトルデータから抽出するステップ（６４）であって、当該抽出されたデータは予測ブロックを構成する、前記ステップと、
前記復号された残差ブロックと前記予測ブロックを結合することにより、前記現ブロックを再構成するステップ（６６）と、を含み、
前記再構成方法は、各反復において原子に分解する前記ステップが、
原子の前記第１のディクショナリにおける第１の原子を選択するステップ（３２）と、
前記第１の原子がテクスチャ化された原子である場合、前記第１の原子に関連付けられたパッチと現残差ベクトルの間の位相相関を適用するステップ（３４、３４０）と、
前記パッチから、前記残差ベクトルと最も強い相関関係がある部分を少なくとも抽出するステップ（３４、３４２）であって、当該抽出された部分は第２の原子を構成する前記ステップと、
前記第１の原子および前記第２の原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択するステップ（３６）と、
前記選択された原子により、前記残差ベクトルを更新するステップ（３８）と、を含む、前記方法。
【請求項７】
前記第２のディクショナリのパッチは円対称性である、請求項６に記載の再構成方法。
【請求項８】
前記第２のディクショナリのパッチは、それらのコンテンツに依拠する形態を有する、請求項６または７に記載の再構成方法。
【請求項９】
前記第２のディクショナリは、異なるサイズの少なくとも２つのパッチを備える、請求項６〜８のいずれかに記載の再構成方法。
【請求項１０】
前記抽出のステップ（３４、３４２）は、前記残差ベクトルに最も強い相関関係があるＮ個の部分の抽出を含み、抽出された各部分は再位相化原子を構成し、前記選択のステップは、前記第１の原子および前記再位相化原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択することを含む、請求項６〜８のいずれかに記載の再構成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像符号化の一般領域に関する。
【０００２】
本発明は、画像のシーケンスのブロックを符号化する方法、およびそれに対応する、当該ブロックを再構成する方法に関する。
【背景技術】
【０００３】
図１に関連して、空間的または時間的予測により、複数の画像のシーケンスに属する現画像の画素の現ブロックＢｃを符号化することは、当該技術分野で知られている。この目的のために、符号化される現ブロックＢｃについて、空間的予測の場合に事前に再構成された現ブロックに空間的に隣接する画素、または参照画像と呼ばれる、事前に再構成された現画像以外の画像の画素から、予測ブロックＢｐを決定することは、当該技術分野では知られている。
【０００４】
ステップ１２では、現ブロックＢｃから予測ブロックＢｐを抽出することにより、残差ブロックＢｒが決定される。
【０００５】
ステップ１４では、残差ブロックは、ストリームＦにおいて符号化される。この符号化のステップは一般に、ストリームＦにおける残差ブロックの係数のブロックへの変換、この係数の量子化、係数のエントロピー符号化を含んでいる。
【０００６】
予測ブロックＢｐを決定するために、「マッチング追跡」等の原子分解の反復法を、前記現ブロックに隣接するブロックの少なくとも再構成されたブロックの画像データを有するデータのベクトルに適用することが、当該技術分野において知られている。原子分解は、原子のディクショナリにおける原子を反復手法で選択することを含んでいる。ディクショナリは通常、分析上または理論上の原子と呼ばれる原子、すなわち、離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ Ｃｏｓｉｎｅ Ｔｒａｎｓｆｏｒｍ）または離散フーリエ変換（ＤＦＴ：Ｄｉｓｃｒｅｔｅ Ｆｏｕｒｉｅｒ Ｔｒａｎｓｆｏｒｍ）等の変換の基本関数に対応するものである。分析上または理論上の原子は、その数式により完全に記述される。図２においては、これらの分析上の原子は、原子のディクショナリの最初の８つの欄を構成する。予測ブロックの現ブロックに対する関連性、すなわち適合性は、ディクショナリに存在する原子に強く依存する。予測を改善するために、自然テクスチャから、テクスチャ化された原子と呼ばれるテクスチャ・サンプルを追加することにより、ディクショナリのサイズを大きくすることが可能である。図２においては、これらのテクスチャ化された原子は、原子のディクショナリの最後の８つの欄を形成する。これらは例えば、自然または合成画像から抽出される。
【０００７】
ディクショナリのサイズの増加は、計算コストの増加を招く。実際、分子分解の過程では、より多くの原子を検証する必要がある。
【発明の概要】
【０００８】
本発明の目的は、従来技術の欠点のうち少なくとも一つを克服することである。このために本発明は、画像のシーケンスの現ブロックを符号化する方法に関し、当該方法は、
現ブロックに因果的に隣接して配置された画素に関連付けられた少なくとも再構成された画像データを備えたデータのベクトルを、第１のディクショナリの原子に反復して分解するステップを含み、第１のディクショナリは、分析上の原子およびテクスチャ化された原子を備え、当該方法は更に、
現ブロックに対応する分解されたベクトルデータから抽出するステップを含み、当該抽出されたデータは予測ブロックを構成し、当該方法は更に、
現ブロックから予測ブロックを抽出することにより、残差ブロックを決定するステップと、
残差ブロックを符号化するステップを含んでいる。
【０００９】
各反復において原子に分解するステップは、
原子の第１のディクショナリにおける第１の原子を選択するステップと、
第１の原子がテクスチャ化された原子である場合、第１の原子に関連付けられたパッチと現残差ベクトルの間の位相相関を適用するステップと、
パッチから、残差ベクトルと最も強い相関関係がある部分を少なくとも抽出するステップを含み、当該抽出された部分は第２の原子を構成し、当該ステップは更に、
第１の原子および第２の原子から、現残差ベクトルと最も強い相関関係がある原子を選択するステップと
選択された原子により、残差ベクトルを更新するステップを含んでいる。
【００１０】
本発明にかかる符号化方法により、好都合にも、パッチを利用して多数の原子を検証することができる。これらのパッチにより、第１の選択されたテクスチャ化された原子は、特に位相相関のステップにより、当該テクスチャ化された原子に関して、多数の再位相化原子を検証することを可能にする。
【００１１】
同じ数の原子を先行技術の方法の一つにより検証するためには、各テクスチャ化された原子についての再位相化原子を挿入する、第１のディクショナリのサイズを増加させることが必要であろう。しかし、かかる拡大されたディクショナリから原子へ分解することは、かなりのコストがかかる。例えば、マッチング追跡型アルゴリズムに基づく分解の場合、このアプローチは、第１のディクショナリの各原子について、少なくとの一つのスカラー乗積が行われることを必要とし、これは、縮小されたサイズの第１のディクショナリについてスカラー乗積を行い、そして本発明の符号化方法で行われる第２のディクショナリを利用した単純な位相相関による複数の再位相化原子を検証することよりもかなりコストがかかる。
【００１２】
更に、第２のディクショナリを利用して多数の再位相化原子を検証するという事実により、多数の反復を削減することができる。
【００１３】
本発明の特定の特徴により、第２のディクショナリのパッチは円対称性である。
【００１４】
本発明の他の特定の特徴により、第２のディクショナリのパッチは、コンテンツにより異なる形態を備えている。
【００１５】
他の特定の特徴により、第２のディクショナリは、異なるサイズの少なくとも２つのパッチを備えている。
【００１６】
変形実施形態によると、抽出のステップは、残差ベクトルに最も強い相関関係があるＮ個の部分の抽出を含み、抽出された各部分は再位相化原子を構成し、選択のステップは、第１の原子および再位相化原子から、現残差ベクトルと最も強い相関関係がある原子を選択することを含んでいる。
【００１７】
本発明は更に、ストリーム形式による画像のシーケンスの現ブロックを再構成する方法に関し、当該方法は、
ストリームから現ブロックについて残差ブロックを復号化するステップと、
現ブロックに因果的に隣接して配置された画素に関連付けられた少なくとも再構成された画像データを備えたデータのベクトルを、第１のディクショナリの原子に反復して分解するステップを含み、第１のディクショナリは、分析上の原子およびテクスチャ化された原子を備え、当該方法は更に、
現ブロックに対応する分解されたベクトルデータから抽出するステップを含み、当該抽出されたデータは予測ブロックを構成し、当該方法は更に、
復号化された残差ブロックと予測ブロックを結合することにより、現ブロックを再構成するステップを含んでいる。
【００１８】
各反復において原子に分解するステップは、
原子の第１のディクショナリにおける第１の原子を選択するステップと、
第１の原子がテクスチャ化された原子である場合、第１の原子に関連付けられたパッチと現残差ベクトルの間の位相相関を適用するステップと、
パッチから、少なくとも残差ベクトルと最も強い相関関係がある部分を抽出し、当該抽出された部分は第２の原子を構成し、当該ステップは更に、
第１の原子および第２の原子から、現残差ベクトルと最も強い相関関係がある原子を選択するステップと
選択された原子により、現残差ベクトルを更新するステップを含んでいる。
【００１９】
符号化方法を参照しつつ記載された利点と同一の利点は、再構成の方法にも適用される。
【００２０】
本発明の特定の特徴により、第２のディクショナリのパッチは円対称性である。
【００２１】
本発明の他の特定の特徴により、第２のディクショナリのパッチは、そのコンテンツに応じた形態を備えている。
【００２２】
特定の特徴により、第２のディクショナリは、異なるサイズの少なくとも２つのパッチを備えている。
【００２３】
変形実施形態によると、抽出のステップは、残差ベクトルに最も強い相関関係があるＮ個の部分の抽出を含み、抽出された各部分は再位相化原子を構成し、選択のステップは、第１の原子および再位相化原子から、現残差ベクトルと最も強い相関関係がある原子の選択することを含んでいる。
【図面の簡単な説明】
【００２４】
本発明は、実施形態および効果的な実装を介し、以下の添付図面を参照しつつ、何ら制限することなく、より良く理解され、かつ記述される。
【００２５】
【図１】図１は、先行技術にかかる符号化方法を示している。
【図２】図２は、分析上およびテクスチャ化された原子を有する原子のディクショナリを示している。
【図３】図３は、先行技術にかかる原子分解の方法を示している。
【図４】図４は、一群の画像のブロックを示している。
【図５】図５は、本発明により絞り込まれた原子分解の方法を示している。
【図６】図６は、本発明による原子分解の方法の詳細を示している。
【図７】図７は、本発明にかかる符号化方法を示している。
【図８】図８は、本発明にかかる符号化方法の特定の構成要件を示している。
【図９】図９は、本発明にかかる再構成の方法を示している。
【図１０】図１０は、本発明にかかる符号化方法を示している。
【図１１】図１１は、本発明にかかる復号化方法を示している。
【図１２】図１２は、因果的領域の種々の形態を示している。
【発明を実施するための形態】
【００２６】
画像は画素または画像点を備え、その各々と画像データの少なくとも一つの項目が関連付けられている。画像データの項目は例えば、輝度データの項目または色データの項目である。
【００２７】
「残差」の用語は、他のデータの抽出後に得られたデータを指す。抽出は一般に、ソース画素から予測画素を差し引くことである。しかし抽出はより一般的であり、特に加重減法を含んでいる。
【００２８】
「再構成物」の用語は、残差を予測データと結合した後に得られたデータ（例えば、画素、ブロック）を指している。結合は一般に、残差予測画素の和である。しかし結合はより一般的であり、特に加重合計を含む。再構成されたブロックは、再構成された画素のブロックである。
【００２９】
画像復号化に関連して、「再構成」および「復号化」の用語は非常に頻繁に同義語として用いられる。よって「再構成されたブロック」は、「復号化されたブロック」の用語に属するものとしても称される。
【００３０】
本発明にかかる符号化方法は、原子分解の方法に基づいている。原子分解を信号Ｙから得ることを可能にする種々の方法が存在する。これらのうち最もよく知られているものの一つは、「マッチング追跡」の用語で特定される。直交マッチング追跡または「グローバル整合フィルタ」等の「マッチング追跡」の変形を使用してもよい。
【００３１】
原子分解の一般原則および「マッチング追跡」の一般原則を以下に記載する。Ｙは、次元Ｎのソースベクトルと仮定し、Ａを次元Ｎ×Ｍであって、Ｍ＞＞Ｎの行列と仮定する。Ａの列ａｊは、ソースベクトルＹを表すのに用いられるディクショナリの分析上またはテクスチャ化された原子である。ソース信号Ｙの原子分解の目的は、Ｙ=ＡＸのように、次元ＭのベクトルＸを決定することである。ベクトルＸについては、解の無限性がある。簡約表現の目的は、Ｙ=ＡＸのすべての解のうち、簡約である解、すなわちベクトルＸが少ない数の非ＮＵＬＬ係数しか有していない解を探索することである。厳密解を探索することは、非常に費用のかかる組み合わせ法が必要になるため、実際上は過度に複雑である。一般に、Ｎ（Ｙ−ＡＸ）≦ρ（ここでρは、表現の簡約性を調整する許容しきい値であり、Ｎ（.）は例えば、自乗ノルムＬ２である）を実証する簡約表現が代わりに求められる。Ｎ（.）は必然的に、ノルムＬ２以外のノルムであってもよい。
【００３２】
マッチング追跡（ＭＰ）方法により、反復法を利用して、準最適解、すなわち非厳密解を求めることができる。当該方法により、各々の新しい反復ｋにおいて（同一の原子が複数の反復の過程で選択される場合を除き）一般に増加する複数の非ＮＵＬＬ係数を有する表現Ｘｋ、次元ベクトルＭが各反復ｋにおいて生成される。ＭＰ法を図３を参照しつつ詳細に説明する。
【００３３】
既知のデータは、ソース信号Ｙ、ディクショナリＡ、しきい値ρである。反復ステップ２０（反復  ｋ＝０）において、データＸ０およびＲ０が初期化され、このときＲ０は、残差誤差または残差ベクトルの初期ベクトルである。たとえば、Ｘ０＝０であって、残差誤差または残差ベクトルＲ０の初期ベクトルが以下のように初期化される。
Ｒｏ＝Ｙ−ＡＸｏ＝Ｙ
【００３４】
ステップ２２では、ｋ番目の反復に対応して、現残差ベクトルＲｋ−１と最も高い相関関係がある基本関数ａｊｋが選択され、ここで、Ｒｋ−１＝Ｙ−ＡＸｋ−１である。
【００３５】
【数１】
2013524597.tif 000003
であり、ここで＜.＞は、スカラー乗積演算子である。
【００３６】
ステップ２４では、ベクトルＸｋおよび残差ベクトルＲｋが更新される。
【００３７】
ベクトルＸｋの係数ｘｊｋは、以下の式により算定される。
【００３８】
【数２】
2013524597.tif 000004
【００３９】
残差ベクトルＲｋは以下の式により更新される。
【００４０】
【数３】
2013524597.tif 000005
【００４１】
算定された係数ｘｊｋは、Ｘｋ−１に追加されて新たな表現Ｘｋを形成する。
【００４２】
ステップ２６では、停止基準が充たされているか否かを見極めるための検証がある。
Ｎ（Ｙ−ＡＸｋ）≦ρのときは、当該処理は終了し、そうでないときは、ステップ２８でｋが１つずつ増分され、ステップ２２で当該処理は再開する。最終ベクトルＡＸｋは、ソース信号Ｙの近似式であり、ここでＫは最終反復の指数である。
【００４３】
図４では、サイズｎ×ｎの画素のブロックが図示されている。整数ｎは、例えば４、８、１６等、様々な値をとることができる。灰色ブロック（領域Ｐ）は、予測される現ブロックを示しており、斜線を付したブロック（領域Ｃ）は、因果的領域を示しており、白い領域（領域ＮＣ）は、非因果的領域を示している。因果的領域は、現ブロックの符号化に先立ち、符号化され、かつ再構成された画素を有している。因果的領域の画定は、画像中のブロックの符号化順序に左右される。図４では、ブロックは、「ラスタスキャン」として知られた標準的な符号化順序に従って符号化されると仮定する。しかし本発明は、この符号化順序には全く限定されない。本発明にかかる符号化方法は、Ｌ＝Ｃ∪Ｐ∪ＮＣによりスキャンされた領域Ｌの画素から構成された観測ベクトルＹの原子分解を含んでいる。そしてベクトルＹは、サイズ９ｎ２ｘ１のベクトルである。実際には、原子分解は、領域Ｃの画素に関連付けられた画像データを備えたベクトルＹＣに適用され、例えば予備的予測ステップにより当該領域の画素に関連付けられた画像データに適用される場合もある。実際、領域Ｌの他の画素の画像データは知られておらず、ＮＵＬＬであると考えられる。
【００４４】
図５は、本発明により絞り込まれた原子分解の方法を示している。本発明により絞り込まれた原子分解法は、２つのディクショナリを使用している。第１のディクショナリＡは、ＭＰ型方法により通常使用される分析上および／またはテクスチャ化された原子を備えている。例えば、分析上の原子は、領域Ｌ（３ｎ×３ｎ）と同一のサイズの二次元基本関数であり、信号を基本信号に分解することについて適正な特性を有していると仮定する。例えば、離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）または離散フーリエ変換（ＤＦＴ：Ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）等、通常の変換の核は、分析上の原子を画定するのに利用される。これら特殊のケースでは、信号の周波数分解が行われる。ＤＦＴおよびＤＣＴに関連付けられた基本関数または分析上の原子の式は各々、以下の通りである。
【００４５】
【数４】
2013524597.tif 000006
および
【数５】
2013524597.tif 000007
【００４６】
ディクショナリＡは、分析上の原子と同一サイズのテクスチャ化された原子により完成する。ディクショナリＡは、領域Ｌを表すために、最小９ｎ２の原子を含んでいる必要がある。各々のサイズが二次元の行列で３ｎ×３ｎである９ｎ２の二次元原子を含むことを可能にするために、原子はベクトル化される。よってディクショナリＡは、各々がサイズ９ｎ２×１の分析上またはテクスチャ化された原子を表す最小９ｎ２の列から構成される。Ａは、ディクショナリおよび対応する行列の双方を指している。
【００４７】
ＤＣＴおよびＤＦＴ原子の選択は限定ではない。実際、ディクショナリは、画像のいずれのパターンタイプ（Ｇａｂｏｒ原子、異方性原子等）を表すこともできるいずれの基本関数によっても質を向上させることができる。行列Ａの原子の数、あるいはここでも列の数は、最小値としてベクトル領域Ｌのサイズ（すなわち９ｎ２）を有するが、理論上の最大値は有しない。原子の量が多いほど、信号が再生される可能性は大きくなる。
【００４８】
第２のディクショナリは、第１のディクショナリの原子より大きいパッチで構成される。テクスチャ化された原子のようなこれらのパッチは、自然画像から生じる。より詳細には、第１のディクショナリの各テクスチャ化された原子または第１のディクショナリの一部に過ぎない各テクスチャ化された原子と、第２のディクショナリのパッチは関連付けられている。第２のディクショナリのパッチは例えば、自然または合成画像から抽出される。パッチは長方形状であってもよい。変形によると、パッチの形状はコンテンツに左右される。例えば、パッチが実質的に垂直構造を有する場合は、高さが高いというより幅広い長方形であることが好ましいであろう。逆の場合、すなわちパッチが実質的に水平構造を有する場合は、幅広いというより高さが高い長方形であることが好ましいであろう。同様に、パッチは円対称性であってもよい。第１のディクショナリのテクスチャ化された原子は、好都合にも、第２のディクショナリの各パッチからテクスチャ化された原子を抽出することにより得られる。例えば、テクスチャ化された原子はパッチの中央に配置される。第２のディクショナリのパッチのサイズは、パッチによって異なってもよい。しかし、テクスチャ化された原子がパッチの中央に配置されるという事実は、何ら必須の特性を備えていない。同様に、本発明は、テクスチャ化された原子がパッチから生成される方法によっても、パッチが自然画像から決定される方法によっても限定されない。図３を参照して既述したＭＰ法のように、本発明にかかる原子分解の方法は、反復法である。
【００４９】
ステップ３２では、第１の原子ａｊｋは、例えば、ＭＰ法のステップ２２による原子の第１のディクショナリにおいて選択される。原子ａｊｋがテクスチャ化された原子であり、第２のディクショナリのパッチがこれと関連付けられると、当該方法はステップ３４に続く。原子ａｊｋが、いずれのパッチも対応していない分析上の原子またはテクスチャ化された原子である場合は、当該方法はステップ３８に続く。ａｊｋは、現残差ベクトルＲＫ−１と最も強い相関関係がある原子であり、例えば、スカラー乗積｜＜Ｒｋ−１，ａｊｋ＞｜が最も高い原子である。このスカラー乗積は、ｃ＿ｍａｘとして表記される。
【００５０】
ステップ３４では、第２の原子ｐｊｋが第２のディクショナリから決定される。このステップは図６で詳細に図示される。
【００５１】
ステップ３４０では、ａｊｋを決定するのに利用される残差ベクトルＲＫ−１が、位相相関により、ａｊｋに対応する第２のディクショナリのパッチＰｊｋと相関性を有する。ここで位相相関は、残差ＲＫ−１と、パッチＰｊｋのコンテンツの間の変位（ｄｘ，ｄｙ）をもたらす。この変位により、第１のディクショナリの原子と同じサイズの新たな原子の位置が決定される。
【００５２】
ステップ３４２では、位相相関という点で残差ベクトルＲＫ−１と最も高い相関性を有するパッチの一部が、当該パッチから抽出される。この抽出された部分は、再位相化原子と呼ばれ、Ｐｉｋと表記される。
【００５３】
変形によると、位相相関は、残差ＲＫ−１とパッチＰｊｋのコンテンツの間のＮ個の変位（ｄｘ，ｄｙ）をもたらす。これらのＮ個の変位は、位相相関という意味で残差ベクトルＲＫ−１と最も高い相関性を示すパッチのＮ個の部分の位置を示している。そしてこれらのＮ個の部分はパッチから抽出され、抽出された各部分は再位相化原子を形成する。
【００５４】
パッチが円対称性である場合は、位相相関についての残差は、パッチセット上で輪状に変位してもよい。
【００５５】
ステップ３６では、ＲＫ−１と最も高い相関性を有する原子は、ａｊｋおよびｐｊｋから選択され、ステップ３４２で複数の再位相化原子が抽出される場合は、ａｊｋおよびＮ個の再位相化原子から選択され場合もある。例えば、関係式ｃ＿ｍａｘ、すなわち、｜＜Ｒｋ−１，ａｊｋ＞｜と、第２の原子と関連付けられた、ｃ＿ｐｈａｓｅとして表記される関係式、すなわち｜＜Ｒｋ−１，ｐｊｋ＞｜が比較される。ｃ＿ｐｈａｓｅ＞ｃ＿ｍａｘのとき、第１の原子ａｊｋが選択されない場合は、第２の原子ｐｉｋが選択される。Ｎ個の再位相化原子の場合、選択された原子は、問題となる原子とＲｋ−１のスカラー乗積という意味での最も相関性の高い原子Ｒｋ−１である。
【００５６】
ステップ３８では、ベクトルＸｋと残差ベクトルＲｋは、選択された原子により更新される。ベクトルＸｋの係数Ｘｉｋは、ｐｉｋが選択される場合は、以下の式
Ｘｉｋ＝｜＜Ｒｋ−１，ｐｉｋ＞｜
により算定され、ａｊｋが選択される場合は、ベクトルＸｋの係数ｘｊｋは、以下の式Ｘｊｋ＝｜＜Ｒｋ−１，ａｊｋ＞｜
により算定される。残差Ｒｋは、Ｒｋ＝Ｒｋ−１−ｘｉｋｐｉｋ
のように更新され、あるいは選択された原子により、Ｒｋ＝Ｒｋ−１−ｘｊｋａｊｋ
のように更新される。
【００５７】
ステップ４０では、停止基準が充たされているか否かを見極めるための検証がある。
Ｎ（Ｙ−Ａ’ Ｘｋ）≦ρのときは、当該方法は終了し、そうでないときは、ステップ４２でｋが１つずつ増分され、ステップ３２で当該方法は再開する。Ａ’ は、第１のディクショナリの原子を備え、第２のディクショナリから選択された原子を備える場合もある。最終ベクトルＡ’ Ｘｋは、ソース信号Ｙの近似式であり、ここでＫは最終反復の指数である。
【００５８】
図５および６を参照して記載されている絞り込まれた原子分解の方法は、現ブロックを符号化するのに使用される。本発明にかかる符号化方法は、図７を参照しつつ記載されている。
【００５９】
ステップ５２では、図５を参照しつつ記載されるように、原子分解は、観察領域、すなわち隣接ブロック（図４の領域Ｃ）の画素の値をデータとして備えたサイズ４ｎ２×１のベクトルＹｐに適用される。変形によると、原子分解は、観察領域、すなわち隣接ブロック（図３の領域Ｃ）の画素、および予測される現ブロック（図４の領域Ｐ）のデータを置き換えた最初の予測ブロックＢｐ０の画素の画像データをデータとして備えるサイズ５ｎ２×１のベクトルＹｃｐに適用される。事前に再構成されていない現ブロックの他の隣接ブロック（図３の領域ＮＣ）のデータはＮＵＬＬである。最初の予測ブロックは、例えば、標準的なブロックマッチング法にかかる標準的な時間的予測により決定される。本発明は、観察領域の画定によっては何ら限定されない。以下、ベクトルＹｐの原子分解の場合を、同一の分解がベクトルＹｃｐに適用できることを理解した上で検討する。これは、ＭＰ法に有用な予測支援であるこの観察ベクトルＹｐである。
【００６０】
次元４ｎ２×１のデータである（Ｙのデータではない）Ｙｐのデータを表すことができるように、行列Ａは、領域Ｃ以外にあるすべての画素に対応する走査線を除去することにより改変される。実際、これらすべての画素は知られておらず、ゼロの値を有する。このようにして行列が得られ、Ａｃと表記され、サイズ４ｎ２×９ｎ２の高さをもつという意味で圧縮されている。そして図５を参照しつつ記載されたステップ３２〜４０は反復して適用され、観察データとしてベクトルＹｐとともにＸｏｐｔを決定する。当該方法は、停止基準Ｎ（Ｙｃ−Ａ’ ｃＸｋ）≦ρが証明されると即、終了し、Ｘｏｐｔ＝Ｘｋであり、Ｋは最終反復の指数であり、Ａ’ ｃは第１のディクショナリの原子を備え、高さという意味で圧縮された第２のディクショナリから選択された原子を備える場合もある。最終ベクトル
2013524597.tif 000008
は、領域Ｌに対応するベクトルＹの近似式である。
【００６１】
ステップ５４では、領域Ｐに対応するサイズｎ２のベクトル
2013524597.tif 000009
は、図８に図示されるように
2013524597.tif 000010
から抽出される。抽出されたデータ
2013524597.tif 000011
は、ブロック形式で再構成される（ベクトル演算に対する逆算）。再構成されたデータは、現ブロックの新たな予測ブロックＢｐを表している。
【００６２】
ステップ５６では、残差ブロックＢｒは、現ブロックＢｃから予測ブロックＢｐを抽出することにより決定される。
【００６３】
ステップ５８では、残差ブロックが符号化される。この符号化のステップは一般に、ストリームＦにおける残差ブロックの係数のブロックへの変換、この係数の量子化、その係数のエントロピー符号化を含んでいる。
【００６４】
変形によると、この符号化ステップは、ストリームＦにおける残差の量子化およびそのエントロピー符号化を含んでいる。
【００６５】
変形によると、反復の過程で決定される一連のシーケンスＸｋは、メモリに記憶される。この変形によると、ＸｏｐｔはＸｋに等しくなく、Ｋは最終反復の指数であるが、Ｘｏｐｔ＝Ｘｋｏｐｔであると共に、
【数６】
2013524597.tif 000012
であり、このときＡ’ｐは、予測される領域Ｐと関連付けられた行列部分Ａ’であり、Ｙｐは、予測される領域Ｐと関連付けられたサイズｎ２×１のベクトルであり、すなわち領域Ｐの画素の画像データを備えている。
【００６６】
ＡｐおよびＹｐは図８に図示されている。この変形により、領域Ｃの最適な表現には必ずしも相当しない領域Ｐの最適な表現としてＸｏｐｔを決定することができる。データＡｐＸｋｏｐｔは、ブロック形式で再構成される（ベクトル演算に対する逆算）。再構成されたデータは、現ブロックの新たな予測ブロックＢｐを表している。この変形によると、係数ｋｏｐｔもストリームＦで符号化される。実際上、ベクトルＹｐのデータは復号器にとって未知である。
【００６７】
図９は、本発明にかかる現ブロックを再構成する方法を模式的に示している。
【００６８】
ステップ６０では、残差ブロックＢｒは現ブロックについて復号化される。例えば、ストリームＦの一部は係数に復号化される。当該係数は逆量子化され、必要であれば、ステップ５８における符号化方法で使用されるものに逆変換により変換される。残差ブロックはこのように得られる。変形によると、ステップ５８で符号器側にいかなる変換ステップも適用されない場合は、逆変換ステップは特に省略される。
【００６９】
ステップ６２では、原子分解が適用される。このステップは、符号化方法のステップ５２と同一である。このステップにより、ベクトルＹの近似式が、
2013524597.tif 000013
であると決定できる。
【００７０】
ステップ６４では、領域Ｐに対応するサイズｎ２のベクトル
2013524597.tif 000014
は、図８に図示された
2013524597.tif 000015
から抽出される。抽出されたデータ
2013524597.tif 000016
は、ブロック形式で再構成される（ベクトル演算に対する逆算）。再構成されたデータは、現ブロックの新たな予測ブロックＢｐを表している。
【００７１】
ステップ６６では、現ブロックＢｃは、ステップ６４で決定された予測ブロックＢｐとステップ６０で復号化された残差ブロックを結合すること、たとえば画素に対する画素の加算により再構成される。
【００７２】
図１０は、符号化装置１２を図式的に示している。符号化装置１２は、（１つまたは複数の）画像を入力時に受け取る。符号化装置１２は、図７を参照しつつ記載された本発明にかかる符号化方法を実行できる。各画像は、各々が画像データの少なくとも一つの項目に関連付けられた画素のブロックに分割される。符号化装置１２は特に、時間的予測による符号化を実行する。時間的予測による符号化に関する符号化装置１２のモジュール、あるいはＩＮＴＥＲ符号化のみが図１０に図示されている。ビデオコーダ（符号化器）の当業者が知る他のモジュールは、図示されていない（例えば、符号化モードの選択、空間的予測）。符号化装置１２は特に、残差ブロックＢｒを生成するために、例えば、画素による画素の減算等、現ブロックＢｃから予測ブロックＢｐを抽出することができる算定モジュール１２００を備えている。計算モジュール１２００は、本発明にかかる符号化方法のステップ５６を実行することができる。これは更に、残差ブロックＢｒを量子化データに変換して量子化することができるモジュール１２０２を備えている。変換Ｔは例えば、離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）である。符号化装置１２は更に、量子化データをストリームＦに符号化することができるエントロピー符号化モジュール１２０４を備えている。これは更に、モジュール１２０２の逆算を行うモジュール１２０６を備えている。モジュール１２０６は、逆量子化Ｑ−１およびそれに続く逆変換Ｔ−１を行う。モジュール１２０６は、メモリ１２１０に記憶される再構成されたブロックを生成するために、例えば、画素に対する画素の加算等、モジュール１２０６から得られたデータのブロックと予測ブロックＢｐの結合を行うことができる計算モジュール１２０８に接続されている。
【００７３】
予測モジュール１２１６は、予測ブロックを決定する。予測モジュール１２１６は、本発明にかかる符号化方法のステップ５２および５４を実行することができる。
【００７４】
符号化方法のステップ５８は、モジュール１２０２および１２０４で実行される。
【００７５】
図１１は、復号化装置１３を図式的に示している。復号化装置１３は、画像を表すストリームＦを入力時に受け取る。ストリームＦは例えば、通信路を介して符号化装置１２により送信される。復号化装置１３は、図９を参照しつつ記載された本発明にかかる復号化方法を実行することができる。復号化装置１３は、復号化されたデータを生成することができるエントロピー復号化モジュール１３００を備えている。そして復号化されたデータは、逆量子化およびそれに続く逆変換を行うことができるモジュール１３０２に送信される。モジュール１３０２は、ストリームＦを生成した符号化装置１２のモジュールと同一である。モジュール１３０２は、メモリ１３０６に記憶される再構成された現ブロックＢｃを生成するために、例えば、画素に対する画素の加算等、モジュール１３０２から得られたブロックと予測ブロックＢＰの結合を行うことができる計算モジュール１３０４に接続されている。計算モジュール１３０４は、再構成方法のステップ６６を実行することができる。復号化装置１３は、予測モジュール１３０８を備えている。予測モジュール１３０８は、メモリ１３０６に記憶された事前に再構成されたデータから予測ブロックＢｐを決定する。予測モジュール１３０８は、本発明にかかる再構成方法のステップ６２および６４を実行することができる。再構成方法のステップ６０は、モジュール１３００および１３０２で実行される。
【００７６】
本発明が上記した実施形態例に限定されないことは当然である。
【００７７】
特に当業者は、いずれの変形も記載された実施形態に適用してこれらを組み合わせ、その種々の効果から利益を享受することができる。実際にＭＰ法以外の方法は、ベクトルＸｏｐｔを決定するのに利用することができる。同様に、因果的領域の形態は、図１２に図示するように変化し得る。この図では、検討した因果的領域には斜線が付されている。本発明は、例示的実施例として示されたに過ぎない因果的領域のこれらの形態には何ら限定されない。この図ではブロックはいかなるサイズでもよい。因果的領域は、本発明にかかる方法が画像のブロックの走査順序とは無関係である、という意味で予測ブロックに対していかなる位置にあってもよい。
【００７８】
パッチの形態およびサイズは変化し得る。同様に第２のディクショナリは、第１のディクショナリにあるテクスチャ化された原子より少ない数のパッチを含んでいてもよい。
【図１】
2013524597.tif 000017
【図２】
2013524597.tif 000018
【図３】
2013524597.tif 000019
【図４】
2013524597.tif 000020
【図５】
2013524597.tif 000021
【図６】
2013524597.tif 000022
【図７】
2013524597.tif 000023
【図８】
2013524597.tif 000024
【図９】
2013524597.tif 000025
【図１０】
2013524597.tif 000026
【図１１】
2013524597.tif 000027
【図１２】
2013524597.tif 000028
【手続補正書】
【提出日】平成24年11月30日(2012.11.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像のシーケンスの現ブロックを符号化する方法であって、前記方法は、
現ブロックに因果的に隣接して配置された画素に関連付けられた少なくとも再構成された画像データを備えたデータのベクトルを、第１のディクショナリの原子に反復して分解するステップ（５２）であって、前記第１のディクショナリは、分析上の原子およびテクスチャ化された原子を備える、前記ステップと、
前記現ブロックに対応する前記分解されたベクトルデータから抽出するステップ（５４）であって、前記抽出されたデータは予測ブロックを構成する、前記ステップと、
前記現ブロックから前記予測ブロックを抽出することにより、残差ブロックを決定するステップ（５６）と、
前記残差ブロックを符号化するステップ（５８）と、を含み、
前記符号化方法は、各反復において原子に分解する前記ステップが、
原子の前記第１のディクショナリにおける第１の原子を選択するステップ（３２）と、
前記第１の原子がテクスチャ化された原子である場合、前記第１の原子に関連付けられ、前記第１の原子より大きいパッチと現残差ベクトルの間の位相相関を適用するステップ（３４、３４０）と、
前記パッチから、前記残差ベクトルと最も強い相関関係がある部分を少なくとも抽出するステップ（３４、３４２）であって、前記抽出された部分は、前記第１の原子と同一サイズの第２の原子を構成する、前記ステップと、
前記第１の原子および前記第２の原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択するステップ（３６）と、
前記選択された原子により、前記残差ベクトルを更新するステップ（３８）と、を含む、前記方法。
【請求項２】
前記第２のディクショナリのパッチは円対称性である、請求項１に記載の符号化方法。
【請求項３】
前記第２のディクショナリのパッチは、それらのコンテンツに依拠する形態を有している、請求項１または２に記載の符号化方法。
【請求項４】
前記第２のディクショナリは、異なるサイズの少なくとも２つのパッチを備えている、請求項１〜３のいずれかに記載の符号化方法。
【請求項５】
前記抽出のステップ（３４、３４２）は、前記残差ベクトルに最も強い相関関係があるＮ個の部分の抽出を含み、抽出された各部分は再位相化原子を構成し、
前記選択のステップは、前記第１の原子および前記再位相化原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択することを含む、請求項１〜４のいずれかに記載の符号化方法。
【請求項６】
ストリーム形式により生じる画像のシーケンスの現ブロックを再構成する方法であって、
前記ストリームから前記現ブロックについて残差ブロックを復号化するステップ（６０）と、
前記現ブロックに因果的に隣接して配置された画素に関連付けられた少なくとも再構成された画像データを備えたデータのベクトルを、第１のディクショナリの原子に反復して分解するステップ（６２）であって、前記第１のディクショナリは、分析上の原子およびテクスチャ化された原子を備える、前記ステップと、
前記現ブロックに対応する前記分解されたベクトルデータから抽出するステップ（６４）であって、前記抽出されたデータは予測ブロックを構成する、前記ステップと、
前記復号された残差ブロックと前記予測ブロックを結合することにより、前記現ブロックを再構成するステップ（６６）と、を含み、
前記再構成方法は、各反復において原子に分解する前記ステップが、
原子の前記第１のディクショナリにおける第１の原子を選択するステップ（３２）と、
前記第１の原子がテクスチャ化された原子である場合、前記第１の原子に関連付けられ、前記第１の原子より大きいパッチと現残差ベクトルの間の位相相関を適用するステップ（３４、３４０）と、
前記パッチから、前記残差ベクトルと最も強い相関関係がある部分を少なくとも抽出するステップ（３４、３４２）であって、前記抽出された部分は、前記第１の原子と同一サイズの第２の原子を構成する、前記ステップと、
前記第１の原子および前記第２の原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択するステップ（３６）と
前記選択された原子により、前記残差ベクトルを更新するステップ（３８）を含む、前記方法。
【請求項７】
前記第２のディクショナリのパッチは円対称性である、請求項６に記載の再構成方法。
【請求項８】
前記第２のディクショナリのパッチは、それらのコンテンツに依拠する形態を有する、請求項６または７に記載の再構成方法。
【請求項９】
前記第２のディクショナリは、異なるサイズの少なくとも２つのパッチを備える、請求項６〜８のいずれかに記載の再構成方法。
【請求項１０】
前記抽出のステップ（３４、３４２）は、前記残差ベクトルに最も強い相関関係があるＮ個の部分の抽出を含み、抽出された各部分は再位相化原子を構成し、前記選択のステップは、前記第１の原子および前記再位相化原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択することを含む、請求項６〜８のいずれかに記載の再構成方法。
【請求項１１】
画像のシーケンスの現ブロックを符号化する装置に関し、前記装置は、
現ブロックに因果的に隣接して配置された画素に関連付けられた少なくとも再構成された画像データを備えたデータのベクトルを、第１のディクショナリの原子に反復して分解する手段であって、前記第１のディクショナリは、分析上の原子およびテクスチャ化された原子を備える、前記手段と、
前記現ブロックに対応する前記分解されたベクトルデータから抽出する手段であって、前記抽出されたデータは予測ブロックを構成する、前記手段と、
前記現ブロックから前記予測ブロックを抽出することにより、残差ブロックを決定する手段と、
前記残差ブロックを符号化する手段と、を備え、
前記符号化装置は、データのベクトルを反復的に第１のディクショナリの原子に分解する前記手段が、
原子の前記第１のディクショナリにおける第１の原子を選択する手段と、
前記第１の原子がテクスチャ化された原子である場合、前記第１の原子に関連付けられ、前記第１の原子より大きいパッチと現残差ベクトルの間の位相相関を適用する手段と、
前記パッチから、前記残差ベクトルと最も強い相関関係がある部分を抽出する手段であって、前記抽出された部分は、前記第１の原子と同一サイズの第２の原子を構成する前記手段と、
前記第１の原子および前記第２の原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択する手段と、
前記選択された原子により、前記残差ベクトルを更新する手段と、を含む、前記装置。
【請求項１２】
前記装置は、請求項１〜５のいずれかに記載の符号化方法のステップを実行するように構成された、請求項１１に記載の符号化装置。
【請求項１３】
ストリーム形式で生じる画像のシーケンスの現ブロックを再構成する復号装置であって、
前記ストリームから前記現ブロックについて残差ブロックを復号する手段と、
前記現ブロックに因果的に隣接して配置された画素に関連付けられた少なくとも再構成された画像データを備えたデータのベクトルを、第１のディクショナリの原子に反復して分解する手段であって、前記第１のディクショナリは、分析上の原子およびテクスチャ化された原子を備える、前記手段と、
前記現ブロックに対応する前記分解されたベクトルデータから抽出する手段であって、前記抽出されたデータは予測ブロックを構成する、前記手段と、
前記復号された残差ブロックと前記予測ブロックを結合することにより、前記現ブロックを再構成する手段と、を備え、
前記復号装置は、データのベクトルを反復的に第１のディクショナリの原子に分解する前記手段が、
原子の前記第１のディクショナリにおける第１の原子を選択する手段と、
前記第１の原子がテクスチャ化された原子である場合、前記第１の原子に関連付けられ、前記第１の原子より大きいパッチと現残差ベクトルの間の位相相関を適用する手段と、
前記パッチから、前記残差ベクトルと最も強い相関関係がある部分を少なくとも抽出する手段であって、前記抽出された部分は、前記第１の原子と同一サイズの第２の原子を構成する、前記手段と、
前記第１の原子および前記第２の原子から、前記現残差ベクトルと最も強い相関関係がある原子を選択する手段と、
前記選択された原子により、前記残差ベクトルを更新する手段と、を備える、前記装置。
【請求項１４】
前記装置は、請求項６〜１０のいずれかに記載の再構成方法のステップを実行するように構成された、請求項１３に記載の復号装置。
【国際調査報告】
2013524597.tif 000029
2013524597.tif 000030