(57)【特許請求の範囲】
【請求項１】
画像のシーケンスの現在のブロックを符号化する符号化方法であって、以下のステップ、
前記現在のブロックについて予測ブロックを決定するステップと、
前記現在のブロック及び前記予測ブロックから、残差ブロックを決定するステップと、
前記残差ブロックを符号化するステップと
を含む方法において、
前記予測ブロックが以下のステップ、
少なくとも１つの動きベクトル及び少なくとも１つの参照画像から前記現在のブロックの最初の予測ブロックを決定するステップと、
前記現在のブロックの復元された隣接ブロックの画像データ及び前記現在のブロックの前記最初の予測ブロックのデータを含むベクトルＹｃｐに原子分解法を適用するステップと、
前記原子分解法の適用により分解されたベクトルから前記現在のブロックに対応するデータを抽出し、及び、該抽出されたデータを前記予測ブロックに再編成するステップと、
にしたがって決定される、前記符号化方法。
【請求項２】
前記原子分解法を適用するステップが、
ａ）Ｒk-1と最も相関がある原子を原子の辞書において選択するステップであって、ここでＲk-1はベクトルＹcpとＡc*Ｘk-1との間で計算された残差であり、Ｘk-1は繰返しｋ−１において決定されたベクトルであり、ｋが整数であり、Ａcは、各列が前記辞書の原子を表す行列である、前記ステップと、
ｂ）該選択された原子からＸk及びＲkを計算するステップと、
ｃ）ステップａ及びｂを、次の終止基準Ｎ（Ｙcp−ＡcＸk）≦ρまで繰り返すステップであって、ここでρは閾値であり、N（．）がノルムである、前記ステップと、
を含む、請求項１に記載の符号化方法。
【請求項３】
前記分解されたベクトルから前記現在のブロックに対応するデータを抽出することは、
ベクトル
【数１】
0005931747.tif 000048
から前記予測ブロックを抽出するステップであって、ここで
【数２】
0005931747.tif 000049
はベクトルＸkの１つである、前記ステップを含む、請求項２に記載の符号化方法。
【請求項４】
【数３】
0005931747.tif 000050
であり、ここでＫは最後の前記繰返しのインデックスである、請求項３に記載の符号化方法。
【請求項５】
【数４】
0005931747.tif 000051
が以下のステップ、
各繰返しでＸkを記憶するステップと、
記憶されたＸkの中から値Ｎ（Ｙp−ＡpＸk）が最小となるＸkを選択するステップであって、ここでＹpは前記現在のブロックに対応するＹcpの部分であり、Ａpは前記現在のブロックに対応する前記行列Ａcの部分である、前記ステップと、
【数５】
0005931747.tif 000052
から前記予測ブロックを決定するステップであって、ここで
【数６】
0005931747.tif 000053
は前のステップで選択されたＸkである、前記ステップと
にしたがって決定される、請求項３に記載の符号化方法。
【請求項６】
符号化データのストリームの形態における画像のシーケンスの現在のブロックを復元する復元方法であって、
符号化データの前記ストリームの一部を復号することによって残差ブロックを決定するステップと、
前記現在のブロックについて予測ブロックを決定するステップと、
前記残差ブロックと前記予測ブロックとから、前記現在のブロックを復元するステップと、
を含み、
前記予測ブロックが以下のステップ、
少なくとも１つの動きベクトル及び少なくとも１つの参照画像から前記現在のブロックの最初の予測ブロックを決定するステップと、
前記現在のブロックの復元された隣接ブロック及び前記現在のブロックの前記最初の予測ブロックのデータを含むベクトルＹｃｐに原子分解法を適用するステップと、
前記原子分解法の適用により分解されたベクトルから前記現在のブロックに対応するデータを抽出し、及び、該抽出したデータを前記予測ブロックに再編成するステップと、
にしたがって決定される、前記復元方法。
【請求項７】
前記原子分解法を適用するステップが、
ａ）Ｒk-1と最も相関がある原子を原子の辞書において選択するステップであって、ここでＲk-1はベクトルＹcpとＡc*Ｘk-1との間で計算された残差であり、Ｘk-1は繰返しｋ−１において決定されたベクトルであり、ｋが整数であり、Ａcは、各列が前記辞書の原子を表す行列であるステップと、
ｂ）該選択された原子からＸk及びＲkを計算するステップと、
ｃ）ステップａ及びｂを、次の終止基準Ｎ（Ｙcp−ＡcＸk）≦ρまで繰り返すステップであって、ここでρは閾値であり、N（．）がノルムである、前記ステップと、
を含む、請求項６に記載の復元方法。
【請求項８】
前記分解されたベクトルから前記現在のブロックに対応するデータを抽出することは、
ベクトル
【数７】
0005931747.tif 000054
から前記予測ブロックを抽出するステップであって、ここで
【数８】
0005931747.tif 000055
はベクトルＸkの１つである、前記ステップを含む、請求項７に記載の復元方法。
【請求項９】
【数９】
0005931747.tif 000056
であり、ここでＫは最後の前記繰返しのインデックスである、請求項８に記載の復元方法。
【請求項１０】
【数１０】
0005931747.tif 000057
が以下のステップ、
各繰返しでＸkを記憶するステップと、
記憶されたＸkの中から値Ｎ（Ｙp−ＡpＸk）が最小となるＸkを選択するステップであって、ここでＹpは前記現在のブロックに対応するＹcpの部分であり、Ａｐは前記現在のブロックに対応する行列Ａｃの部分であるステップと、
【数１１】
0005931747.tif 000058
から前記予測ブロックを決定するステップであって、
【数１２】
0005931747.tif 000059
は前のステップで選択されたＸkである、前記ステップと
にしたがって決定される、請求項８に記載の復元方法。
【請求項１１】
画像のシーケンスの現在のブロックを符号化する符号化デバイスであって、以下の手段、
前記現在のブロックについて予測ブロックを決定する手段と、
前記現在のブロック及び前記予測ブロックから残差ブロックを決定する手段と、
前記残差ブロックを符号化する手段と
を備えたデバイスにおいて、
前記現在のブロックについて予測ブロックを決定する前記手段は、
少なくとも１つの動きベクトル及び少なくとも１つの参照画像から前記現在のブロックの最初の予測ブロックを決定する手段と、
前記現在のブロックの復元された隣接ブロックの画像データ及び前記現在のブロックの前記最初の予測ブロックのデータを含むベクトルＹｃｐに原子分解法を適用する手段と、
前記原子分解法の適用により分解されたベクトルから前記現在のブロックに対応するデータを抽出し、及び、該抽出したデータを前記予測ブロックに再編成する手段と、
を含む、前記符号化デバイス。
【請求項１２】
請求項１から５のいずれか１項に記載の符号化方法のステップを実行するように適合された、請求項１１に記載の符号化デバイス。
【請求項１３】
符号化データのストリームの形態における画像のシーケンスの現在のブロックを復元する復号デバイスであって、
符号化データの前記ストリームの一部を復号することによって残差ブロックを決定する手段と、
前記現在のブロックについて予測ブロックを決定する手段と、
前記残差ブロック及び前記予測ブロックから前記現在のブロックを復元する手段と
を備えた復号デバイスにおいて、
前記現在のブロックについて前記予測ブロックを決定する前記手段は、
少なくとも１つの動きベクトル及び少なくとも１つの参照画像から前記現在のブロックの最初の予測ブロックを決定する手段と、
前記現在のブロックの復元された隣接ブロックの画像データ及び前記現在のブロックの前記最初の予測ブロックのデータを含むベクトルＹｃｐに原子分解法を適用する手段と、
前記原子分解法の適用により分解されたベクトルから前記現在のブロックに対応するデータを抽出し、及び、該抽出したデータを前記予測ブロックに再編成する手段と
を含む、前記復号デバイス。
【請求項１４】
請求項６から１０のいずれか１項に記載の前記復元方法のステップを実行するように適合された、請求項１３に記載の復号デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像符号化の一般分野に関する。
【０００２】
本発明は、画像のシーケンスのブロックを符号化する方法、およびこのようなブロックを復元（reconstructing）するための対応する方法に関する。
【背景技術】
【０００３】
図１を参照すると、いくつかの画像のシーケンスに属する現在の画像の画素からなる現在のブロックＢｃを空間予測または時間予測によって符号化することが当技術分野で知られている。この目的のために、符号化されるべき現在のブロックＢｃに対し、空間予測の場合では前に復元された現在のブロックに空間的に隣接する画素から、あるいは前に復元された現在の画像以外の、参照画像と呼ばれる画像の画素から予測ブロックＢｐを決定することが当技術分野で知られている。
【０００４】
ステップ１２を通じて、残差ブロックＢｒが、現在のブロックＢｃから予測ブロックＢｐを抽出することによって決定される。
【０００５】
ステップ１４を通じて、残差ブロックはストリームＦ中で符号化される。この符号化のステップは、残差ブロックを係数のブロックに変換すること、これらの係数を量子化すること、およびストリームＦ中でそれらをエントロピー符号化することを一般に含む。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】T. K. Tan et al, "Intra prediction by template matching", ICIP conference, 2006
【発明の概要】
【発明が解決しようとする課題】
【０００７】
時間予測の場合では、ブロックマッチング法などの動き推定方法により予測画素のブロックを決定することが当技術分野で知られている。しかし、このような予測ブロックは、復元された現在のブロックの隣接ブロックと比べて一般に不均質である。
【課題を解決するための手段】
【０００８】
本発明の目的は、従来技術の不利な点の少なくとも１つを克服することである。この目的のために、本発明は以下のステップ、すなわち
現在のブロックについて予測ブロックを決定するステップと、
現在のブロックから予測ブロックを抽出することによって、残差ブロックを決定するステップと、
残差ブロックを符号化するステップと
を含む、画像のシーケンスの現在のブロックを符号化する方法に関連する。
【０００９】
本発明によれば、現在のブロックの予測ブロックは、以下のステップ、すなわち
動きデータおよび前に符号化及び復元された少なくとも１つの参照画像から最初の予測ブロックを決定するステップと、
データＹｃｐのベクトルに原子分解法を適用するステップであって、データのベクトルが、前に符号化および復元された現在のブロックの隣接ブロックの画像データ、および最初の予測ブロックのデータを含むステップと、
分解されたベクトルから現在のブロックに対応するデータを抽出するステップであって、抽出したデータが予測ブロックを形成するステップと
にしたがって決定される。
【００１０】
現在のブロックの時間予測は、結果として得られる予測ブロックが参照画像からの時間情報の項目と現在の画像からの空間情報の項目との両方を結合するので、改善される。結果として得られる予測ブロックは、空間環境、すなわち現在のブロックの、前に復元された隣接画素を考慮に入れることにより、より均質になる。
【００１１】
本発明の特定の一態様によれば、符号化方法は、Ｎ（Ｙｃｐ−ＡcＸ）が最小になるベクトルＸkを以下のステップ、すなわち
ａ）Ｒk-1と最も相関がある原子ａｊkを選択するステップであって、Ｒk-1はベクトルＹcpとＡc*Ｘk-1の間で計算された残差であり、ここでＸk-1は繰返しｋ−１において決定されたＸの値であり、ｋが整数であるステップと、
ｂ）選択された原子からＸkおよびＲkを計算するステップと、
ｃ）次の終止基準Ｎ（Ｙcp−ＡcＸk）≦ρまでステップａおよびｂを繰り返すステップであって、ここでρは閾値であるステップと、
ベクトル
【００１２】
【数１】
0005931747.tif 000002
【００１３】
から予測ブロックを抽出するステップであって、ここで、
【００１４】
【数２】
0005931747.tif 000003
【００１５】
はベクトルＸkの１つであるステップと
にしたがって決定することを含み、ここでＡｃは各列が原子ａｊを表す行列であり、Ｎ（．）はノルムである。
【００１６】
本発明の特定の一特性によれば、
【００１７】
【数３】
0005931747.tif 000004
【００１８】
であり、ここでＫは最後の繰返しのインデックスである。
【００１９】
一変形形態によれば、
【００２０】
【数４】
0005931747.tif 000005
【００２１】
は以下のステップ、すなわち
各繰返しＸｋで記憶するステップと、
記憶されたＸｋの中から値Ｎ（Ｙｐ−ＡｐＸｋ）が最小となるＸｋを選択するステップであって、ここでＹｐは現在のブロックに対応するＹｃｐの部分であり、Ａｐは現在のブロックに対応する行列Ａｃの部分であるステップと、
【００２２】
【数５】
0005931747.tif 000006
【００２３】
から予測ブロックを決定するステップであって、ここで、
【００２４】
【数６】
0005931747.tif 000007
【００２５】
は前のステップで選択されたＸｋであるステップと
にしたがって決定される。
【００２６】
本発明はまた、符号化データのストリームの形の画像のシーケンスの現在のブロックを復元する方法に関し、以下のステップ、すなわち
符号化データのストリームの一部を復号することによって残差ブロックを決定するステップと、
現在のブロックから予測ブロックを決定するステップと、
残差ブロックと前記予測ブロックを合成することによって現在のブロックを復元するステップと
を含む。
【００２７】
本発明によれば、現在のブロックの予測ブロックは以下のステップ、すなわち
動きデータおよび前に符号化及び復元された少なくとも１つの参照画像から最初の予測ブロックを決定するステップと、
データＹｃｐのベクトルに原子分解法を適用するステップであって、データＹｃｐのベクトルが、前に符号化および復元された現在のブロックの隣接ブロックの画像データ、および最初の予測ブロックのデータを含むステップと、
分解されたベクトルから現在のブロックに対応するデータを抽出するステップであって、抽出したデータが前記予測ブロックを形成するステップと
にしたがって決定される。
【００２８】
特定の一実施形態によれば、復元方法は、Ｎ（Ｙｃｐ−ＡcＸ）が最小になるベクトルＸkを以下のステップ、すなわち
ａ）Ｒk-1と最も相関がある原子ａｊkを選択するステップであって、ここでＲk-1はベクトルＹcpとＡc*Ｘk-1の間で計算された残差であり、ここでＸk-1は繰返しｋ−１において決定されたＸの値であり、ｋが整数であるステップと、
ｂ）選択された原子からＸkおよびＲkを計算するステップと、
ｃ）次の終止基準Ｎ（Ｙcp−ＡcＸk）≦ρまでステップａおよびｂを繰り返すステップであって、ここでρは閾値であるステップと、
ベクトル
【００２９】
【数７】
0005931747.tif 000008
【００３０】
から予測ブロックを抽出するステップであって、
【００３１】
【数８】
0005931747.tif 000009
【００３２】
はベクトルＸkの１つであるステップと
にしたがって決定することを含み、ここでＡｃは各列が原子ａｊを表す行列であり、Ｎ（．）はノルムである。
【００３３】
本発明の特定の一特性によれば、
【００３４】
【数９】
0005931747.tif 000010
【００３５】
であり、ここでＫは最後の繰返しのインデックスである。
【００３６】
一変形形態によれば、
【００３７】
【数１０】
0005931747.tif 000011
【００３８】
は以下のステップ、すなわち
各繰返しＸｋで記憶するステップと、
記憶されたＸｋの中から値Ｎ（Ｙｐ−ＡｐＸｋ）が最小となるＸｋを選択するステップであって、ここでＹｐは現在のブロックに対応するＹｃｐの部分であり、Ａｐは現在のブロックに対応する行列Ａｃの部分であるステップと、
【００３９】
【数１１】
0005931747.tif 000012
【００４０】
から予測ブロックを決定するステップであって、ここで、
【００４１】
【数１２】
0005931747.tif 000013
【００４２】
は前のステップで選択されたＸｋであるステップと
にしたがって決定される。
【図面の簡単な説明】
【００４３】
本発明は、添付の図に関して、全く限定的ではない諸実施形態および有利な実施によってよりよく理解および説明されよう。
【００４４】
【図１】従来技術による符号化方法を示す図である。
【図２】従来技術による原子分解の方法を示す図である。
【図３】画像のブロックの群を示す図である。
【図４】本発明による符号化方法を示す図である。
【図５】本発明による復号化方法を示す図である。
【図６】本発明による符号化方法の特定の要素を示す図である。
【図７】本発明による符号化方法の特定の要素を示す図である。
【図８】本発明による符号化方法の特定の要素を示す図である。
【図９】本発明による復元の方法を示す図である。
【図１０】本発明による符号化デバイスを示す図である。
【図１１】本発明による復号デバイスを示す図である。
【図１２】因果関係ゾーン（causal zone）のそれぞれ異なる形を示す図である。
【発明を実施するための形態】
【００４５】
画像は、画像データの少なくとも１つの項目にそれぞれが関連付けられた画素または像点を含む。画像データの項目とは、例えば、輝度データの項目または彩度データの項目である。
【００４６】
「残差」という語は、他のデータの抽出後に得られるデータを意味する。抽出とは一般に、ソース画素から予測画素を減算することである。しかし、抽出はもっと一般的であり、特に重み付け減算を含む。
【００４７】
「復元」という語は、残差と予測データの合成後に得られるデータ（例えば画素、ブロック）を意味する。合成とは一般に、予測画素と残差の加算である。しかし、合成はもっと一般的であり、特に重み付け加算を含む。復元ブロックとは、復元画素のブロックである。
【００４８】
画像復号に関しては、「復元」および「復号」という用語は、同義であるとして用いられることが非常に多い。したがって、「復号ブロック」という術語で「復元ブロック」も意味する。
【００４９】
本発明による符号化の方法は、原子分解の方法（method for atomic decomposition）に基づく。信号Ｙから原子分解が得られるようにする様々な方法が存在する。これらの中で、最もよく知られているものの１つは、「マッチング探索（matching pursuit）」という用語で知られている。「直交マッチング探索」または「グローバル整合フィルタ」など、「マッチング探索」の変形形態が使用されることもあることに留意されたい。
【００５０】
原子分解全般および「マッチング探索」の一般原理を以下で説明する。Ｙが次元Ｎのソースベクトル、Ａが次元Ｎ×Ｍの行列、ただしＭ≫Ｎである。Ａの列ａjは辞書（dictionary）の基底関数または原子（atom）であり、これらはソースベクトルＹを表すために使用される。ソース信号Ｙの原子分解の目的は、次元ＭのベクトルＸをＹ＝ＡＸとなるように決定することである。ベクトルＸには無数の解がある。簡潔な表現の目的は、Ｙ＝ＡＸのすべての解の中で簡潔であるもの、すなわち、ベクトルＸが低い数字のナル（null）でない係数だけを有する解を探すことである。厳密な解を探すことは、非常にコストがかかる組み合わせ法を必要とするので、実際にはあまりに複雑である。一般には、Ｎ（Ｙ−ＡＸ）≦ρを確証する簡潔な表現が代わりに求められる。ここでρは表現の簡潔さを制御する許容閾（tolerance threshold）であり、Ｎ（．）は例えば二乗ノルムＬ２である。当然、Ｎ（．）はノルムＬ２以外のノルムでもありうる。
【００５１】
「マッチング探索」（ＭＰ）の方法では、このような準最適な解、すなわち厳密でない解が、繰返し手順を用いて得られるようになる。この方法では繰返しｋごとに、表現Ｘｋ、ナルでない係数の番号を有する次元ベクトルＭを発生し、この番号は、一般に（同じ原子が２つの繰返しの間中に選択される場合を除いて）新しい繰返しｋごとに増える。図２を参照してこのＭＰ法を詳細に説明する。
【００５２】
既知のデータは、ソース信号Ｙ、辞書Ａおよび閾ρである。初期化ステップ２０を通じて（繰返しｋ＝０）Ｘ0＝０であり、残差エラーＲ0の最初のベクトルが次式で計算される。
Ｒ0＝Ｙ−ＡＸ0＝Ｙ
【００５３】
ステップ２２を通じて、ｋ番目の繰返しに対応して、現在の残差ベクトルＲk-1との最大の相関性を有する基底関数
【００５４】
【数１３】
0005931747.tif 000014
【００５５】
が選択される。ここで、
【００５６】
【数１４】
0005931747.tif 000015
【００５７】
である。
【００５８】
ステップ２４を通じて、ベクトルＸkおよび残差ベクトルＲkが更新される。
【００５９】
ベクトルＸｋの係数
【００６０】
【数１５】
0005931747.tif 000016
【００６１】
が次式により計算される。
【００６２】
【数１６】
0005931747.tif 000017
【００６３】
残差ベクトルＲkは次式により更新される。
【００６４】
【数１７】
0005931747.tif 000018
【００６５】
計算されたばかりの係数
【００６６】
【数１８】
0005931747.tif 000019
【００６７】
がＸｋ−１に加えられ、それによって新しい表現Ｘｋが形成される。
【００６８】
ステップ２６を通じて、終止基準が満たされているかどうかを見るための検査がある。Ｎ（Ｙ−ＡＸｋ）≦ρであれば手順は終了され、そうでなければステップ２８を通じてｋが１だけインクリメントされ、ステップ２２で手順が再開する。最終ベクトルＡＸＫは、ソース信号Ｙの近似値になり、ここでＫは最後の繰返しのインデックスである。
【００６９】
図３に、サイズｎ×ｎの画素のブロックが示されている。整数「ｎ」は、例えば４、８、１６などの異なる値を取りうる。灰色のブロック（ゾーンＰ）は予測されるべき現在のブロックを表し、斜線で影をつけたブロック（ゾーンＣ）は因果関係ゾーン（causal zone）を表し、白色のゾーン（ゾーンＮＣ）は非因果関係ゾーンを表す。因果関係ゾーンは、現在のブロックの前に復元された画素を含む。因果関係ゾーンの画定は、画像中のブロックを符号化する順序によって決まる。図３では、各ブロックは、「ラスタ走査」として知られる標準符号化順序に従って符号化されると想定されている。しかし、本発明はこの符号化順序に全く限定されない。本発明による符号化方法は、一直線に走査されるゾーンＬの画素から形成される観測ベクトルＹの原子分解を含み、ここでＬ＝Ｃ∪Ｐ∪ＮＣである。したがって、ベクトルＹは、サイズ９ｎ２×１のベクトルになる。
【００７０】
図４を参照して、本発明による符号化の方法を詳細に説明する。
【００７１】
ステップ３０を通じて最初の予測ブロックＢｐ０が、例えば標準ブロックマッチング法により決定される。このブロックマッチングには、ブロックの参照画像における選択が含まれ、この選択により、この予測ブロックと予測されるべき現在のブロックとの間の計算される歪みが最小になる。このようなブロックＢｐ０は、参照画像のブロックであるか、あるいはそのようなブロックの補間バージョンである。このステップの最後で、隣接ブロックは、前に復元された現在のブロックに利用可能であり、この現在のブロックに対しては、図５に示されるように、現在のブロックのデータの第１の近似値を表す予測ブロックＢｐ０が利用可能である。
【００７２】
ステップ３２を通じて、原子分解がサイズ５ｎ2×１のベクトルＹｃｐに適用され、このベクトルは、観測ゾーンすなわち隣接ブロック（図３のゾーンＣ）の画素の値と、予測されるべき現在のブロック（図３のゾーンＰ）のデータに取って代わった最初の予測ブロックＢｐ０の画素の値とをデータとして含む。前に復元されていない現在のブロックの他の隣接ブロック（図３のゾーンＮＣ）のデータはナルである。ゾーンＣ、ＮＣおよびＰが結合することにより、サイズ３ｎ×３ｎのゾーンＬを形成する。辞書Ａは、ゾーンＬ（３ｎ×３ｎ）と同じサイズの二次元基底関数を含み、これらの基底関数は、ある信号を基本信号に分解するための適正な特性を有すると想定されている。Ａに対してＤＣＴ（離散コサイン変換）またはＤＦＴ（離散フーリエ変換）など通常の変換カーネルを用いることが当然考えられうる。これらの特定の場合には、信号の周波数分解が操作される。ＤＦＴおよびＤＣＴそれぞれを伴う基底関数または原子の式は以下の通りである。
【００７３】
【数１９】
0005931747.tif 000020
【００７４】
および
【００７５】
【数２０】
0005931747.tif 000021
【００７６】
辞書Ａは、ゾーンＬを表すために最小限で９ｎ２の原子を含まなければならない。それぞれのサイズが３ｎ×３ｎの９ｎ２の二次元原子を２Ｄ行列中に含むことができるようにするために、原子はベクトル化されなければならない。すなわち、辞書Ａは、それぞれがサイズ９ｎ２×１の原子を表す９ｎ２列から構成される。したがって、辞書Ａは大きさが９ｎ２×９ｎ２になる。
【００７７】
ＤＣＴ原子およびＤＦＴ原子の選択は制限事項ではない。実際、辞書は、画像中のあらゆるパターンタイプ（Ｇａｂｏｒ原子、異方性原子など）を表すことができる任意の基底関数により拡充することができる。原子の数、または再び行列Ａ中の列の数は、ベクトル化ゾーンＬのサイズ（すなわち９ｎ2）を最小値として有するが、理論的最大値は有さない。原子の量が多ければ多いほど、信号を回復する可能性が多くなる。
【００７８】
有用な画素はゾーンＣおよびＰのものだけであり、他の画素はナルである。ＭＰ法に有効な予測支持体になるのは、この観測ベクトルＹｃｐである。
【００７９】
ステップ３４を通じて、ゾーンＰに対応するサイズｎ２のベクトル
【００８０】
【数２１】
0005931747.tif 000022
【００８１】
は、図７に示されるように、
【００８２】
【数２２】
0005931747.tif 000023
【００８３】
から抽出される。抽出されたデータ
【００８４】
【数２３】
0005931747.tif 000024
【００８５】
は、ブロック形式に再編成される（ベクトル演算の反対の演算）。再編成されたデータは、現在のブロックの新しい予測ブロックＢｐを表す。この予測ブロックＢｐは、特に現在のブロックの空間環境に由来する理由により、Ｂｐ０よりも均質である。
【００８６】
ステップ３６を通じて、残差ブロックＢｒは、現在のブロックＢCから予測ブロックＢｐを抽出することによって、例えば画素ごとに減算することによって決定される。
【００８７】
ステップ３８を通じて、残差ブロックが符号化される。この符号化ステップは、残差ブロックを係数のブロックに変換すること、これらの係数を量子化すること、およびストリームＦ中でそれらをエントロピー符号化することを一般に含む。一変形形態によれば、このステップは、残差を量子化すること、およびストリームＦ中でそれらをエントロピー符号化することを含みうる。
【００８８】
一変形形態によれば、繰返し（ＭＰ法のステップ２４）の間中に決定されたシーケンスＸｋのセットがメモリ中に記憶される。ＸｏｐｔはもはやＸＫと等しくなく、Ｋは最後の繰返しのインデックスであるが
【００８９】
【数２４】
0005931747.tif 000025
【００９０】
であり、
【００９１】
【数２５】
0005931747.tif 000026
【００９２】
である。ここで、Ａｐは、予測されるべきゾーンＰと関連付けられたサイズｎ２×９ｎ２の行列であり、Ｙｐは、予測されるべきゾーンＰと関連付けられたサイズｎ２×１のベクトルである。
【００９３】
ＡｐおよびＹｐが図８に示されている。この変形形態によりＸｏｐｔが、ゾーンＣ∪Ｐの最良表現に必ずしも対応しないゾーンＰの最良表現であるとして決定されることが可能になる。データ
【００９４】
【数２６】
0005931747.tif 000027
【００９５】
は、ブロック形式で再編成される（ベクトル演算の反対の演算）。この変形形態によれば、係数ｋｏｐｔもまたストリームＦ中で符号化される。実際、ベクトルＹｐのデータは復号器には未知である。再編成されたデータは、現在のブロックの新しい予測ブロックＢｐを表す。
【００９６】
標準的な符号化方法では、この符号化モードは、Ｂｐ０に対応する時間予測によって標準的な符号化モードに取って代わることができ、あるいはそれを補完することができ、符号化モード決定モジュールで試験されるこれら２つのモードと、最良のビットレート−歪みを示すモードとは妥協して保持される。
【００９７】
図９は、本発明による現在のブロックを復元する方法を図示する。
【００９８】
ステップ４０を通じて、現在のブロックに対して残差ブロックＢｒが復号される。例えば、ストリームＦの一部が係数に復号される。これらの係数は復号（dequantize）され、次に必要に応じて、ステップ１４の符号器側で使用される係数へと反転変換によって変換される。こうして残差ブロックが得られる。一変形形態によれば、反転変換ステップは、特に変換ステップがステップ１４の符号器側で適用されなかった場合に省略される。
【００９９】
ステップ４２を通じて、最初の予測ブロックＢｐ０が、例えばストリームＦから復号された１つまたはいくつかの動きベクトルにより決定される。一変形形態によれば、最初の予測ブロックＢｐ０は、「テンプレートマッチング」技法によって決定される。このような技法が開示されている（例えば、非特許文献１参照）。
【０１００】
このようなブロックＢｐ０は、参照画像のブロックであるか、またはこのようなブロックの補間バージョンである。このステップの終わりに、前に復元された現在のブロックの隣接ブロックが利用可能であり、現在のブロックに対して、図５に示された現在のブロックのデータの第１の近似値を表す予測ブロックＢｐ０が利用可能である。
【０１０１】
ステップ４４を通じて、原子分解がサイズ９ｎ2×１のベクトルＹに適用され、このベクトルＹは、観測ゾーンすなわち隣接ブロック（図３のゾーンＣ）の画素の値と、予測されるべき現在のブロック（図３のゾーンＰ）のデータに取って代わった最初の予測ブロックＢｐ０の画素の値と、前に復元されていない現在のブロックの他の隣接ブロック（図３のゾーンＮＣ）のデータを表すナル値とをデータとして含む。ゾーンＣ、ＮＣおよびＰが結合することにより、サイズ３ｎ×３ｎのゾーンＬを形成する。辞書Ａは、ゾーンＬ（３ｎ×３ｎ）と同じサイズの二次元基底関数を含み、これらの基底関数は、ある信号を基本信号に分解するための適正な特性を有すると想定されている。Ａに対してＤＣＴ（離散コサイン変換）またはＤＦＴ（離散フーリエ変換）など通常の変換カーネルを用いることが当然考えられうる。これらの特定の場合には、信号の周波数分解が演算される。ＤＦＴおよびＤＣＴそれぞれを伴う基底関数または原子の式は以下の通りである。
【０１０２】
【数２７】
0005931747.tif 000028
【０１０３】
【数２８】
0005931747.tif 000029
【０１０４】
辞書Ａは、ゾーンＬを表すために最小限で９ｎ２の原子を含まなければならない。それぞれのサイズが３ｎ×３ｎの９ｎ２の二次元原子を２Ｄ行列中に含むことができるようにするために、原子はベクトル化されなければならない。すなわち、辞書Ａは、それぞれがサイズ９ｎ２×１の原子を表す９ｎ２列から構成される。したがって、辞書Ａは大きさが９ｎ２×９ｎ２になる。
【０１０５】
ＤＣＴ原子およびＤＦＴ原子の選択は制限事項ではない。実際、辞書は、画像中のあらゆるパターンタイプ（Ｇａｂｏｒ原子、異方性原子など）を表すことができる任意の基底関数により拡充することができる。原子の数、または再び行列Ａ中の列の数は、ベクトル化ゾーンＬのサイズ（すなわち９ｎ2）を最小値として有するが、理論的最大値は有さない。原子の量が多ければ多いほど、信号を回復する可能性が多くなる。
【０１０６】
有用な画素はゾーンＣおよびＰのものだけであり、他の画素はナルである。因果関係ゾーンＣおよび最初の予測ブロックＢｐ０の画素だけを含有するベクトルである、５ｎ２×１画素に等しい大きさのＹｃｐに注意されたい。ＭＰ法に有効な予測支持体になるのは、この観測ベクトルＹｃｐである。
【０１０７】
図６に示されているように、大きさ５ｎ２×１であるＹｃｐのデータ（Ｙのデータではない）を表すことができるように、行列Ａは、ゾーンＣおよびＰの外側のすべての画素に対応するその行を除去することによって修正される。実際には、これらすべての画素は未知であり、ゼロの値を有する。Ａｃと表され、高さの面では圧縮された、サイズ５ｎ２×９ｎ２の行列がこうして得られる。マッチング探索法（matching pursuit method）または他の等価な方法が、問題Ｙｃｐ＝ＡｃＸの簡潔な解のセットの中で解を決定するのに用いられ、この解は、復元エラーを最小限にするＸｏｐｔと表される。こうして、図２を参照して説明したステップ２０から２８は、Ｘｏｐｔを決定するために、観測データとしてベクトルＹｃｐ、辞書として行列Ａｃを用いて、繰返し適用される。この方法は、終止基準Ｎ（Ｙｃｐ−ＡｃＸｋ）≦ρが確証されるとすぐに終止する。すなわちＸｏｐｔ＝ＸＫであり、Ｋは最後の繰返しのインデックスである。最後のベクトル
【０１０８】
【数２９】
0005931747.tif 000030
【０１０９】
は、ベクトルＹの近似値である。
【０１１０】
ステップ４６を通じて、ゾーンＰに対応するサイズｎ２のベクトル
【０１１１】
【数３０】
0005931747.tif 000031
【０１１２】
は、図７に示されるように、
【０１１３】
【数３１】
0005931747.tif 000032
【０１１４】
から抽出される。抽出されたデータ
【０１１５】
【数３２】
0005931747.tif 000033
【０１１６】
は、ブロック形式に再編成される（ベクトル演算の反対の演算）。再編成されたデータは、現在のブロックの新しい予測ブロックＢｐを表す。この予測ブロックＢｐは、特に現在のブロックの空間環境に由来する理由により、Ｂｐ０よりも均質である。
【０１１７】
ステップ４８を通じて、現在のブロックＢCは、ステップ４６で決定された予測ブロックＢｐとステップ４０で復元された残差ブロックとを、例えば画素ごとに加算することによって合成して復元される。
【０１１８】
一変形形態によれば、インデックスＫｏｐｔはストリームＦから復号される。ＸｏｐｔはもはやＸＫと等しくなく、Ｋは最後の繰返しのインデックスであるが、
【０１１９】
【数３３】
0005931747.tif 000034
【０１２０】
である。この変形形態によりＸｏｐｔが、ゾーンＣ∪Ｐの最良表現に必ずしも対応しないゾーンＰの最良表現であるとして決定されることが可能になる。データ
【０１２１】
【数３４】
0005931747.tif 000035
【０１２２】
は、ブロック形式で再編成される（ベクトル演算の反対の演算）。再編成されたデータは、現在のブロックの新しい予測ブロックＢｐを表す。
【０１２３】
図１０は、符号化デバイス１２を図示する。符号化デバイス１２は、入力部で１つまたは複数の画像を受け取る。符号化デバイス１２は、図４を参照して説明した本発明による符号化方法を実施することができる。各画像は、画像データの少なくとも１つの項目にそれぞれが関連付けられた画素のブロックに分割される。符号化デバイス１２は、時間予測による符号化を特に実施する。時間予測による符号化、またはＩＮＴＥＲ符号化に関係がある符号化デバイス１２のモジュールだけが図９に示されている。当業者に知られている映像符号器の他のモジュールは示されていない（例えば、符号化モードの選択、空間予測）。符号化デバイス１２は、現在のブロックＢCから予測ブロックＢｐを例えば画素ごとの減算によって抽出して残差ブロックＢｒを生成できる計算モジュール１２００を特に備える。計算モジュール１２００は、本発明による符号化方法のステップ３６を実施することができる。符号化デバイス１２は、残差ブロックＢｒを変換して次に量子化データに量子化できるモジュール１２０２をさらに備える。変換Ｔは、例えば離散コサイン変換（ＤＣＴ）である。符号化デバイス１２はまた、量子化データをストリームＦに符号化できるエントロピー符号化モジュール１２０４を備える。符号化デバイス１２はまた、モジュール１２０２の反対の動作を行うモジュール１２０６を備える。モジュール１２０６は、逆量子化Ｑ-1を実行し、次に逆変換Ｔ-1を実行する。モジュール１２０６は計算モジュール１２０８に接続され、計算モジュール１２０８は、例えば画素ごとに加算することによってモジュール１２０６からのデータのブロックと予測ブロックＢｐとを合成して、メモリ１２１０に記憶される復元ブロックを生成することができる。
【０１２４】
第１の予測モジュール１２１６は、最初の予測ブロックＢｐ０を決定する。第１の予測モジュール１２１６は、本発明による符号化方法のステップ３０を実施することができる。符号化デバイス１２は、第２の予測モジュール１２１８を備える。第２の予測モジュール１２１８は、既に復元されメモリ１２１０に記憶されたデータ、および最初の予測ブロックＢｐ０から予測ブロックＢｐを決定する。第２の予測モジュール１２１８は、本発明による符号化方法のステップ３２および３４を実施することができる。
【０１２５】
この符号化方法のステップ３８は、モジュール１２０２および１２０４で実施される。
【０１２６】
図１１は、復号デバイス１３を図示する。復号デバイス１３は、画像を表すストリームＦを入力部で受け取る。ストリームＦは、例えば、符号化デバイス１２からチャネルを介して伝送される。復号デバイス１３は、図９を参照して説明した本発明による復号方法を実施することができる。復号デバイス１３は、復号データを生成できるエントロピー復号モジュール１３００を備える。復号データは次に、逆量子化を実行し、次に逆変換を実行できるモジュール１３０２に伝送される。モジュール１３０２は、ストリームＦを生成した符号化デバイス１２のモジュール１２０６と同じである。モジュール１３０２は計算モジュール１３０４に接続され、計算モジュール１３０２は、例えば画素ごとに加算することによってモジュール１３０２からのブロックと予測ブロックＢｐとを合成して、メモリ１３０６に記憶される復元された現在のブロックＢｃを生成することができる。計算モジュール１３０４は、復元方法のステップ４８を実施することができる。復号デバイス１３は、予測モジュール１３０８を備える。予測モジュール１３０８は、最初の予測ブロックＢｐ０を決定する。予測モジュール１３０８は、本発明による復元方法のステップ４２を実施することができる。復号デバイス１３はまた、第２の予測モジュール１３１０を備える。第２の予測モジュール１３１０は、既に復元されメモリ１３０６に記憶されたデータ、および最初の予測ブロックＢｐ０から予測ブロックＢｐを決定する。第２の予測モジュール１３１０は、本発明による復元方法のステップ４４および４６を実施することができる。この復元方法のステップ４０は、モジュール１３００および１３０２において実施される。
【０１２７】
当然ながら、本発明は、上記の実施形態の諸例に限定されない。
【０１２８】
とりわけ、当業者は、上述の諸実施形態に任意の変形形態を適用し、またこれらを組み合わせて、それらの様々な利点から利益を得ることができる。実際、マッチング探索法以外の他の方法を使用してベクトルＸoptを決定することができる。同様に、因果関係ゾーンの形も、図１２に示されるように変わりうる。この図では、考慮に入れられる因果関係ゾーンに斜線で影がつけられている。本発明は、説明のための例としてのみ示されているこれらの因果関係ゾーンの形に全く限定されない。この図では、ブロックは任意のサイズである。本発明による方法が画像内のブロックを走査する順序とは関係がないという意味において、因果関係ゾーンは、予測ブロックに対して任意の位置とすることができる。図５を参照して説明した実施形態では、最初の時間予測Ｂｐ０は、タイプＰ時間予測に対応する表示順序において現在の画像の前に位置している参照画像から導出される。本発明は、この予測タイプに限定されない。実際、予測ブロックＢＰ０は、表示順序において現在の画像の後に位置する参照画像からの予測により得ることができる。予測ブロックＢｐ０はまた、二方向予測または２回予測される予測から得ることもできる。
付記１
画像のシーケンスの現在のブロックを符号化する方法であって、以下のステップ、
前記現在のブロックから予測ブロックを決定するステップ（３０、３２、３４）と、
前記現在のブロックから前記予測ブロックを抽出することによって、残余ブロックを決定するステップ（３６）と、
前記残余ブロックを符号化するステップ（３８）と
を含む方法において、
前記現在のブロックからの前記予測ブロックが以下のステップ、
動きデータ及び前に符号化及び復元された少なくとも１つの参照画像から最初の予測ブロックを決定するステップ（３０）と、
データＹｃｐのベクトルに原子分解法を適用するステップ（３２）であって、データＹｃｐの前記ベクトルが、前に符号化及び復元された前記現在のブロックの隣接ブロックの画像データ、及び、前記最初の予測ブロックのデータを含むステップ（３２）と、
分解されたベクトルから前記現在のブロックに対応するデータを抽出するステップ（３４）であって、該抽出したデータが前記予測ブロックを形成するステップ（３４）と
にしたがって決定される、符号化の方法。
付記２
Ｎ（Ｙｃｐ−ＡcＸ）が最小になるベクトルＸkを以下のステップ、
ａ）Ｒk-1と最も相関がある原子ａｊkを選択するステップであって、ここでＲk-1はベクトルＹcpとＡc*Ｘk-1の間で計算された残余であり、Ｘk-1は繰返しｋ−１において決定されたＸの値であり、ｋが整数であるステップと、
ｂ）該選択された原子からＸk及びＲkを計算するステップと、
ｃ）ステップａ及びｂを、次の終止基準Ｎ（Ｙcp−ＡcＸk）≦ρまで繰り返すステップであって、ここでρは閾値であるステップと、
ベクトル
【数３５】
0005931747.tif 000036
から前記予測ブロックを抽出するステップであって、ここで、
【数３６】
0005931747.tif 000037
はベクトルＸkの１つであるステップと
にしたがって決定することを含み、ここでＡｃは各列が原子ａｊを表す行列であり、Ｎ（．）は標準である、付記１に記載の符号化の方法。
付記３
【数３７】
0005931747.tif 000038
であり、ここでＫは最後の繰返しのインデックスである、付記２に記載の符号化の方法。
付記４
【数３８】
0005931747.tif 000039
が以下のステップ、
各繰返しＸkで記憶するステップと、
記憶されたＸkの中から値Ｎ（Ｙp−ＡpＸk）が最小となるＸkを選択するステップであって、ここでＹpは前記現在のブロックに対応するＹcpの部分であり、Ａｐは前記現在のブロックに対応する行列Ａｃの部分であるステップと、
【数３９】
0005931747.tif 000040
から前記予測ブロックを決定するステップであって、ここで、
【数４０】
0005931747.tif 000041
は前のステップで選択されたＸkであるステップと
にしたがって決定される、付記２に記載の符号化の方法。
付記５
符号化データのストリームの形の画像のシーケンスの現在のブロックを復元する方法であって、
符号化データの前記ストリームの一部を復号することによって残余ブロックを決定するステップ（４０）と、
前記現在のブロックから予測ブロックを決定するステップ（４２、４４、４６）と、
前記残余ブロックと前記予測ブロックを合成することによって前記現在のブロックを復元するステップ（４８）と
を含む方法において、
前記現在のブロックからの前記予測ブロックが以下のステップ、
動きデータ及び前に符号化及び復元された少なくとも１つの参照画像から最初の予測ブロックを決定するステップ（４２）と、
データＹｃｐのベクトルに原子分解法を適用するステップ（４４）であって、データＹｃｐの前記ベクトルは、前に復元された前記現在のブロックの隣接ブロックの画像データ、及び、前記最初の予測ブロックのデータを含むステップ（４４）と、
分解されたベクトルから前記現在のブロックに対応するデータを抽出するステップ（４６）であって、該抽出したデータが前記予測ブロックを形成するステップ（４６）と
にしたがって決定される、復元の方法。
付記６
Ｎ（Ｙｃｐ−ＡcＸ）が最小になるベクトルＸkを以下のステップ、
ａ）Ｒk-1と最も相関がある原子ａｊkを選択するステップであって、ここでＲk-1はベクトルＹcpとＡc*Ｘk-1の間で計算された残余であり、Ｘk-1は繰返しｋ−１において決定されたＸの値であり、ｋが整数であるステップと、
ｂ）該選択された原子からＸk及びＲkを計算するステップと、
ｃ）ステップａ及びｂを、次の終止基準Ｎ（Ｙcp−ＡcＸk）≦ρまで繰り返すステップであって、ここでρは閾値であるステップと、
ベクトル
【数４１】
0005931747.tif 000042
から前記予測ブロックを抽出するステップであって、ここで、
【数４２】
0005931747.tif 000043
はベクトルＸkの１つであるステップと
にしたがって決定することを含み、ここでＡｃは各列が原子ａｊを表す行列であり、Ｎ（．）は標準である、付記５に記載の復元の方法。
付記７
【数４３】
0005931747.tif 000044
であり、ここでＫは最後の繰返しのインデックスである、付記６に記載の復元の方法。
付記８
【数４４】
0005931747.tif 000045
が以下のステップ、
各繰返しＸkで記憶するステップと、
記憶されたＸkの中から値Ｎ（Ｙp−ＡpＸk）が最小となるＸkを選択するステップであって、ここでＹpは前記現在のブロックに対応するＹcpの部分であり、Ａｐは前記現在のブロックに対応する行列Ａｃの部分であるステップと、
【数４５】
0005931747.tif 000046
から前記予測ブロックを決定するステップであって、
【数４６】
0005931747.tif 000047
は前のステップで選択されたＸkであるステップと
にしたがって決定される、付記６に記載の復元の方法。
【図１】
0005931747.tif 000060
【図２】
0005931747.tif 000061
【図３】
0005931747.tif 000062
【図４】
0005931747.tif 000063
【図５】
0005931747.tif 000064
【図６】
0005931747.tif 000065
【図７】
0005931747.tif 000066
【図８】
0005931747.tif 000067
【図９】
0005931747.tif 000068
【図１０】
0005931747.tif 000069
【図１１】
0005931747.tif 000070
【図１２】
0005931747.tif 000071