(57)【特許請求の範囲】
【請求項１】
同一パッチに所属するすべての画素が共通の動きベクトルを持つ制約がなく、かつ画素の動きベクトルの水平・垂直成分が隣接画素間距離の整数倍以外の値を取り得る動き補償方式を実行する手段と、
参照画像において画素の存在しない点の輝度値を内挿により求めることによって画素の密度を水平、垂直方向にそれぞれｍ1、ｍ2倍（ｍ1、ｍ2は正の整数）とした高精細参照画像を合成する手段と、
上記高精細参照画像を格納するメモリとを具備し、
上記動き補償方式を実行する手段は、動き推定を行う場合に上記参照画像と予測画像の関係を表す変換関数を用いて上記予測画像の画素の位置に対応する上記参照画像内の点の位置を求め、該求められた点の位置に該参照画像の画素の存在しない場合に、該求められた点の輝度値を上記高精細参照画像内でこの点の最も近くに位置する画素の輝度値で近似することで動きベクトルを近似し、該動きベクトルの近似により上記予測画像の画素位置に対応する参照画像内の点で該参照画像の画素の存在しない点の位置と、上記高精細参照画像内でのこの点の最も近くに位置する画素の位置が一致しない場合があることを特徴とする画像符号化装置。
【請求項２】
同一パッチに所属するすべての画素が共通の動きベクトルを持つ制約がなく、かつ画素の動きベクトルの水平・垂直成分が隣接画素間距離の整数倍以外の値を取り得る動き補償方式を実行する手段と、
参照画像の一部を対象として、画素の存在しない点の輝度値を内挿により求めることによって画素の密度を水平、垂直方向にそれぞれｍ1、ｍ2倍（ｍ1、ｍ2は正の整数）とした高精細参照画像の一部を合成する手段と、
上記高精細参照画像の一部を格納するメモリとを具備し、
上記動き補償方式を実行する手段は、動き推定を行う際に上記参照画像と予測画像の関係を表す変換関数を用いて上記予測画像の画素の位置に対応する上記参照画像の一部の中の点の位置を求め、該求められた点の位置に該参照画像の画素の存在しない場合に、該求められた点の輝度値を、上記高精細参照画像の一部の中でこの点の最も近くに位置する画素の輝度値で近似することで動きベクトルを近似し、該動きベクトルの近似により上記予測画像の画素位置に対応する参照画像の一部の中の点で該参照画像の画素の存在しない点の位置と、該位置に最も近い上記高精細参照画像の一部の中の画素の位置が一致しない場合があることを特徴とする画像符号化装置。
【請求項３】
予測画像の合成の際の各画素における動きベクトルの水平、垂直成分をそれぞれ隣接画素間距離の１／ｄ1、１／ｄ2（ｄ1、ｄ2は正の整数）の整数倍に制限する手段を具備し、ｍ1≦ｄ1、ｍ2≦ｄ2であることを特徴とする請求項１または２に記載の画像符号化装置。
【請求項４】
上記ｍ1、ｍ2の値がそれぞれ２以上の整数であることを特徴とする請求項１または２または３に記載の画像符号化装置。
【請求項５】
上記ｍ1、ｍ2の値がそれぞれ２のｗ1乗、２のｗ2乗（ｗ1とｗ2は正の整数）であることを特徴とする請求項１または２または３に記載の画像符号化装置。
【請求項６】
上記ｍ1とｍ2の値が２であることを特徴とする請求項１または２または３に記載の画像符号化装置。
【請求項７】
上記ｍ1とｍ2の値が４であることを特徴とする請求項１または２または３に記載の画像符号化装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、同一パッチに所属するすべての画素が共通の動きベクトルを持つ制約がなく、画素の動きベクトルの水平・垂直成分が隣接画素間距離の整数倍以外の値を取り得る動き補償方式を実行する画像符号化装置に関するものである。
【０００２】
【従来の技術】
動画像の高能率符号化において、時間的に近接するフレーム間の類似性を活用する動き補償は情報圧縮に大きな効果を示すことが知られている。現在の画像符号化技術の主流となっている動き補償方式は、動画像符号化方式の国際標準であるＭＰＥＧ１およびＭＰＥＧ２にも採用されている半画素精度のブロックマッチングである。この方式では、符号化しようとする画像を多数のブロックに分割し、ブロックごとにその動きベクトルを水平・垂直方向に隣接画素間距離の半分の長さを最小単位として求める。この処理を数式を用いて表現すると以下のようになる。符号化しようとするフレーム（現フレーム）の予測画像をＰ（ｘ，  ｙ）、参照画像（Ｐと時間的に近接しており、既に符号化が完了しているフレームの復号画像）をＲ（ｘ，  ｙ）とする。また、ｘとｙは整数であるとして、ＰとＲでは座標値が整数である点に画素が存在すると仮定する。このとき、ＰとＲの関係は、
【０００３】
【数１】
0003634878.tif 000002
【０００４】
で表される。ただし、画像はｎ個のブロックに分割されるとして、Ｂｉは画像のｉ番目のブロックに含まれる画素、（ｕｉ，  ｖｉ）はｉ番目のブロックの動きベクトルを表している。動きベクトル（ｕｉ，  ｖｉ）の推定方式として最も一般的に用いられているのは、（ｕｉ，  ｖｉ）に一定の探索範囲を設け（例えば−１５≦ｕｉ，  ｖｉ≦１５）、その中でブロック内の予測誤差Ｅｉ（ｕｉ，  ｖｉ）を最小化するものを探索するという方式である。予測誤差の評価基準として平均絶対誤差を用いた場合、Ｅｉ（ｕｉ，  ｖｉ）は、符号化しようとしているフレームの原画像をＩ（ｘ，  ｙ）として、
【０００５】
【数２】
0003634878.tif 000003
【０００６】
で表される。ただし、Ｎｉはｉ番目のブロックに含まれる画素の数である。このように、異なる動きベクトルについてそれぞれ予測誤差を評価し、この誤差が最も小さい動きベクトルを探索する処理をマッチング処理とよぶ。一定の探索範囲の中ですべての（ｕｉ，  ｖｉ）についてＥｉ（ｕｉ，  ｖｉ）を計算し、その最小値を探索することを全探索とよぶ。
【０００７】
半画素精度のブロックマッチングでは、ｕｉとｖｉはそれぞれ画素間距離の半分、つまりこの場合は１／２を最小単位として求められることになる。したがって、座標値が整数ではなく、参照画像において実際には画素が存在しない点（以後、このような点を内挿点とよぶ）の輝度値を求めることが必要となる。この際の処理としては、周辺４画素を用いた共１次内挿が使われることが多い。この内挿方式を数式で記述すると、座標値の小数成分をｐとｑ（０≦ｐ，  ｑ＜１）として、参照画像の内挿点（ｘ＋ｐ，  ｙ＋ｑ）における輝度値Ｒ（ｘ＋ｐ，  ｙ＋ｑ）は、
【０００８】
【数３】
0003634878.tif 000004
【０００９】
で表される。
【００１０】
半画素精度のブロックマッチングを行うシステムでは、まず広い探索範囲に対して１画素精度の全探索を行なって大まかに動きベクトルを推定した後に、この動きベクトルの周辺のごく狭い範囲（例えば、縦横±半画素の範囲）に対して半画素精度の全探索を行なう２段階探索が広く用いられている。そして、第２段階の探索を行う際には、まず内挿点における輝度値を事前に求めてから探索を行う方法が良く用いられる。この方法の処理の例を図１に示す。この例では縦横４画素のブロックを使用している。参照画像において、座標値が整数でもともと画素が存在する点を「○」で表し、新たに輝度値を求めた内挿点を「×」で表す。また、現フレームの原画像のブロックの画素を「□」で表す。第１段階の探索で得られた動きベクトルを（ｕｃ，  ｖｃ）とする。マッチングの例１０１は、第１段階の探索で、動きベクトルが（ｕｃ，  ｖｃ）であるときのマッチングの様子を示している。予測誤差の評価は重なった「○」と「□」の間で行われる。例１０２、１０３、１０４はそれぞれ第２段階の探索で動きベクトルが（ｕｃ  ＋  １／２，  ｖｃ）、（ｕｃ  ＋  １／２，  ｖｃ  ＋  １／２）、（ｕｃ  −  １／２，  ｖｃ  −  １／２）であるときを表している。これらの例では、予測誤差の評価は重なった「×」と「□」の間で行われる。この図からわかる通り、第２段階の探索における探索範囲を縦横±１／２画素とした場合、６５個（図１の「×」の数）の内挿点の輝度値を求めることにより、動きベクトル８個分のマッチング処理をカバーすることができる。このとき、輝度値を求めた内挿点はすべてマッチングに使用される。マッチングのたびに参照画像において内挿の計算をすると、４×４×８＝１２８回の内挿を行う必要がある。このように内挿演算の回数を減らすことができるのは、参照画像の同じ内挿点が複数回使用されるためである。
【００１１】
半画素精度のブロックマッチングは上で述べた通り、現在広く用いられているが、ＭＰＥＧ１やＭＰＥＧ２より高い情報圧縮率が必要となるアプリケーションではさらに高度な動き補償方式が要求される。ブロックマッチングの欠点はブロック内のすべての画素が同一の動きベクトルを持たなければならない点にある。そこでこの問題を解決するために、隣接する画素が異なる動きベクトルを持つことを許容する動き補償方式が最近提案されている。以下にこの方式の一例である空間変換に基づく動き補償に関して簡単に説明する。
【００１２】
空間変換に基づく動き補償では、予測画像Ｐと参照画像Ｒの関係は、
【００１３】
【数４】
0003634878.tif 000005
【００１４】
で表される。ただし、画像はｎ個の小領域（パッチ）に分割されるとして、Ｐｉは画像のｉ番目のパッチに含まれる画素を表している。また、変換関数ｆｉ（ｘ，  ｙ）とｇｉ（ｘ，  ｙ）は現フレームの画像と参照画像との間の空間的な対応を表現している。このとき、Ｐｉ内の画素（ｘ，  ｙ）の動きベクトルは、（ｘ−ｆｉ（ｘ，  ｙ），ｙ−ｇｉ（ｘ，  ｙ））で表すことができる。ところで、ブロックマッチングは変換関数が定数である方式として、空間変換に基づく動き補償の特殊な例として解釈することもできる。しかし、本明細書で空間変換に基づく動き補償という言葉を用いるときには、ブロックマッチングはその中に含まないこととする。
【００１５】
変換関数の形としては、アフィン変換
【００１６】
【数５】
0003634878.tif 000006
【００１７】
を用いた例（中屋他、「３角形パッチに基づく動き補償の基礎検討」、電子情報通信学会技術報告、ＩＥ９０−１０６、平２−０３参照）、共１次変換
【００１８】
【数６】
0003634878.tif 000007
【００１９】
を用いた例（  Ｇ．  Ｊ．  Ｓｕｌｌｉｖａｎ  ａｎｄ  Ｒ．  Ｌ．  Ｂａｋｅｒ，  ”Ｍｏｔｉｏｎ  ｃｏｍｐｅｎｓａｔｉｏｎ  ｆｏｒ  ｖｉｄｅｏ  ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  ｃｏｎｔｒｏｌ  ｇｒｉｄ  ｉｎｔｅｒｐｏｌａｔｉｏｎ”，  Ｐｒｏｃ．  ＩＣＡＳＳＰ  ’９１  ，  Ｍ９．１，  ｐｐ．２７１３−２７１６，  １９９１−０５）、透視変換
【００２０】
【数７】
0003634878.tif 000008
【００２１】
を用いた例（Ｖ．Ｓｅｆｅｒｄｉｓ  ａｎｄ  Ｍ．Ｇｈａｎｂａｒｉ，  ”Ｇｅｎｅｒａｌ  ａｐｐｒｏａｃｈ  ｔｏ  ｂｌｏｃｋ−ｍａｔｃｈｉｎｇ  ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ’’，  Ｏｐｔｉｃａｌ  Ｅｎｇｉｎｅｅｒｉｎｇ，  ｖｏｌ．  ３２，  ｎｏ．  ７，  ｐｐ．  １４６４−１４７４，  １９９３−０７）などが報告されている。ここでａｉｊ、ｂｉｊ、ｃｉｊはパッチごとに推定される動きパラメータである。符号化装置で得られる予測画像と同じものを受信側で得るためには、画像符号化装置は何らかの形でパッチごとに変換関数の動きパラメータが特定できる情報を、動き情報として受信側に伝送すればよい。例えば、変換関数にアフィン変換を用い、パッチの形状が３角形であるとする。この場合は、６個の動きパラメータを直接伝送しても、パッチの３個の頂点の動きベクトルを伝送しても、受信側で６個の動きパラメータを再生することができる（共１次変換を用いた場合には４角形のパッチを採用すれば同様の処理が可能である）。以下では、変換関数にアフィン変換を用いた場合に関して説明するが、この説明は他の変換を用いた場合についても、ほぼそのまま適用することができる。
【００２２】
変換関数が確定しても空間変換に基づく動き補償には様々なバリエーションを考えることができるが、その一例を図２に示す。この例では、パッチの境界において動きベクトルが連続的に変化するように制約されている。以下では、参照画像２０１を用いて現フレームの原画像２０２の予測画像を合成することを考える。このために、まず現フレームは複数の多角形のパッチに分割され、パッチ分割された画像２０８となる。パッチの頂点は格子点とよばれ、各格子点は複数のパッチに共有される。例えば、パッチ２０９は、格子点２１０、２１１、２１２から構成され、これらの格子点は他のパッチの頂点を兼ねている。こうして画像を複数のパッチに分割した後に、動き推定が行なわれる。ここに示す例では、動き推定は各格子点を対象として参照画像との間でを行なわれる。この結果、動き推定後の参照画像２０３で各パッチは変形されたものとなる。例えば、パッチ２０９は、変形されたパッチ２０４に対応している。これは、動き推定の結果、格子点２０５、２０６、２０７がそれぞれ２１０、２１１、２１２に移動したと推定されたためである。予測画像はパッチ内の各画素に関して変換関数を計算し、数４にしたがって参照画像の中から対応する点の輝度値を求めることにより合成される。これは、この例では３個の頂点の動きベクトルから数５の６個の動きパラメータを計算し、画素ごとに数５を計算することにより実現される。上で述べた通り、動き情報として格子点の動きベクトルを伝送しても、動きパラメータを伝送しても良いが、この例では１個の格子点が複数のパッチの頂点を兼ねている分だけ前者の方が効率的である。
【００２３】
空間変換に基づく動き補償においてもブロックマッチングと同様に、マッチングに基づく動き推定が有効であることが指摘されている。マッチングに基づく動き補償のアルゴリズムの一例を以下に示す。この方式は６角マッチングとよばれ、上の例のようにパッチの境界で動きベクトルが連続的に変化する場合に有効である。この方式は、以下の２つの処理により構成されている。
【００２４】
（１）ブロックマッチングによる格子点の大まかな動き推定
（２）  修正アルゴリズムによる動きベクトルの修正
（１）の処理では、格子点を含むブロック（大きさは任意）に対してブロックマッチングを適用し、このブロックの動きベクトルを格子点の大まかな動きベクトルとする。この処理の目的はあくまで格子点の大まかな動きベクトルを求めることであって、必ずブロックマッチングを用いなければならないわけではない。（２）の処理の様子は図３に示す。この図は参照画像におけるパッチと格子点の一部を示したもの（図２の画像２０３に相当する）である。したがって、この図の中で格子点の位置を変化させることは、その格子点の動きベクトルを変化させることを意味する。格子点３０１の動きベクトルを修正する場合、まずこの格子点が関与するすべてのパッチによって構成される多角形３０２の頂点にあたる、格子点３０３〜３０８の動きベクトルを固定する。こうして格子点３０１の動きベクトルを一定の範囲内で変化させる（例えば格子点３０１を格子点３０９の位置に移動させる）と、その結果多角形３０２が含むパッチ内の予測誤差も変化する。そして、探索範囲内で多角形３０２内の予測誤差を最小にした動きベクトルが、格子点３０１の修正された動きベクトルとして登録される。こうして格子点３０１の修正が終了し、他の格子点に移動してから同様の修正を続ける。一旦すべての格子点に対して修正を行なった後に、もう一度最初の格子点から繰り返し修正を行なえば、さらに予測誤差を小さくすることができる。この繰り返しの回数としては、２〜３回が適当であることが報告されている。
【００２５】
修正アルゴリズムにおける典型的な探索範囲は縦横±３画素である。この場合、１個の格子点について１回の修正で４９回のマッチングが多角形３０２内で行なわれる。一方で、１個のパッチは３個の格子点の修正アルゴリズムに関与するため、パッチ内の各画素に対して合計で１４７回予測誤差の評価が行なわれることになる。さらにこの修正が繰り返し行なわれれば、そのたびに誤差評価の回数はさらに増えることになる。この結果、誤差評価が行なわれるたびに対象となる画素に対して内挿の計算が行なわれ、演算量が膨大となる。
【００２６】
空間変換に基づく動き補償における内挿演算の問題は、半画素精度のブロックマッチングにおける同様の問題と比較して以下の点で本質的な違いがあるためにやっかいである。空間変換に基づく動き補償では、たとえ格子点の動きベクトルの水平・垂直成分を１／２の整数倍に制限したとしても、各画素の動きベクトルの水平・垂直成分は同様に１／２の整数倍とはならない。また、一般的に各画素の動きベクトルの小数点以下の成分は任意の値がとれるため、マッチング処理において参照画像の同じ内挿点の輝度値が複数回用いられることはむしろまれである。
【００２７】
【発明が解決しようとする課題】
空間変換に基づく動き補償においてマッチングに基づく動き推定を行なう場合、輝度値の内挿に要する演算量が膨大となる問題が発生する。本発明の目的は、輝度値の内挿の計算回数を減らし、少ない演算量で動き推定の処理を実現することにある。
【００２８】
【課題を解決するための手段】
動き推定処理の前に、参照画像においてｘ座標とｙ座標がそれぞれ１／ｍ１と１／ｍ２の整数倍である点（ｍ１とｍ２は正の整数）の輝度値を内挿により求めた高精細参照画像を用意する。したがって、高精細参照画像においては、ｘ座標とｙ座標がそれぞれ１／ｍ１と１／ｍ２の整数倍である点に画素が存在することになる。動き推定処理において、座標値が整数でない位置における参照画像の輝度値が必要となった場合には、高精細参照画像の中でこの座標に最も近い位置に存在する画素の輝度値で近似することにより、内挿演算の回数を減らす目的は達成される。
【００２９】
【作用】
上記の高精細参照画像を作成する処理では、原画像の１画像あたりｍ１×ｍ２−１回の内挿計算が必要となる。しかし、一旦この高精細化処理を終えてしまうと、動き推定処理においてこれ以上に内挿の演算を行なう必要はなくなる。「従来の技術」でとりあげた空間変換に基づく動き補償の例では、動き推定処理で１画素あたり１４７回以上の内挿演算が必要である。したがって、ｍ１＝ｍ２＝２とすれば、内挿演算の回数は５０分の１程度にすることができ、演算量の大幅な低減につながる。
【００３０】
【実施例】
第１の実施例として、参照画像全体を高精細化してから動き推定処理を行う方式を示す。まず、高精細参照画像Ｒ’を作成する。輝度値の内挿方式に共１次内挿（数３）を用いるとして、Ｒ’は以下の式で表される。
【００３１】
【数８】
0003634878.tif 000009
【００３２】
ただし、ｓとｔは整数であり、かつ０≦ｓ＜ｍ１，  ０≦ｔ＜ｍ２であるとする。また、Ｒ’ではｘ、ｙ、ｓ、ｔがすべて整数である点に画素が存在するとする。ｓ＝ｔ＝０である点は、もともと参照画像に存在する画素に対応しており、それ以外の点の輝度値は内挿によって求められる。なお、以下では簡単のため、特にｍ１＝ｍ２＝ｍ（ｍは正の整数）である場合について実施例を挙げる。
【００３３】
図４に高精細参照画像を活用する画像符号化装置の例を示す。なお、図の矢印はデータの流れを表しており、アドレス信号などは省略してある。この装置では、動き推定部４０１が動き推定の処理を担当している。参照画像４０４は高精細化の処理を行う参照画像高精細化回路４０５で処理された後、高精細参照画像４０６としてフレームメモリ４０７に蓄えられ、マッチング処理回路４０９へ近似輝度値情報４０８を提供する。一方で現フレームの原画像４０２もフレームメモリ４０３に蓄えられ、マッチング処理回路４０９で動き推定のために活用される。マッチング処理回路が出力した動き情報４１５は受信側に伝送されるが、符号化装置内でも予測画像合成回路４１０における予測画像の合成のために活用される。合成された予測画像と現フレームの原画像４１１との差は減算器４１２で求められ、予測誤差４１３として、予測誤差符号化器４１４で符号化され、予測誤差情報４１６として伝送される。従来の方式では、変換関数の演算、内挿処理、予測誤差の評価がすべてマッチング回路で行なわれていたのに対し、本実施例では内挿処理を事前に参照画像高精細化回路で行なうことにより演算量を低減させている。また、高精細参照画像を用いることにより、変換関数に求められる演算精度を下げることができ、さらに処理を簡略化することができる。これは、変換関数の演算に誤差が発生した場合に、高精細参照画像で近似に用いる画素が異なるものにならない範囲であれば、動き推定の結果に影響がないためである。なお、ここで内挿により輝度値を求められた高精細参照画像の画素は、すべてがマッチング処理で使用されるとは限らない。この点は「従来の技術」でとりあげたブロックマッチングの例とは異なっている。
【００３４】
図５にｍ＝２として、輝度値の内挿に共１次内挿を用いた場合の参照画像高精細化回路４０５の例を示す。この図でも矢印はデータの流れを表しており、図４と同じ参照番号は同じものをさしている。入力の参照画像信号４０４は、上から下へラインごとに左から右へ画素の輝度値を与えるとする。この信号を２個の画素遅延回路５０２、５０３と１個のライン遅延回路５０１より構成された回路に加えることにより、上下左右に隣接する４個の画素の輝度値５０４〜５０７を得ることができる。これらの輝度値それぞれにに対して積算器５０８〜５１１を用いて内挿位置に応じて重み付け係数を掛け、この結果を加算器５１２〜５１４に加える。この結果をさらに加算器５１５とシフトレジスタ５１６に加えることにより、４で割った後に小数点以下を四捨五入する演算を実現する。以上の処理の結果、高精細参照画像Ｒ’の４画素分の輝度値５１７〜５２０を出力４０６として得ることができる。
【００３５】
図６に、マッチング処理回路４０９内において、高精細参照画像Ｒ’を用いて参照画像の内挿点における輝度値の近似値を得る回路の一例を示す。図４と同じ参照番号は同じものをさしている。ここでは、変換関数を計算することにより、２進固定小数点表現の座標値６０１、６０２が与えられていると仮定する。また、ｍは図５と同様に２であるとして、高精細参照画像Ｒ’はフレームメモリ４０７に蓄えられているとする。座標値６０１、６０２は１／４を加える加算器６０３、小数点以下２桁目以下を切り捨てる回路６０４を通過することにより、小数点以下２桁目を四捨五入され、１／２の整数倍に変換される。この結果得られる座標値６０５、６０６は、高精細参照画像Ｒ’において画素の存在する点の座標値に対応している。この座標値は座標−アドレス変換回路６０７によりフレームメモリ４０７のアドレスに変換され、目的の近似輝度値情報４０８を得る。なお、この例では変換関数の小数点以下３桁目以下の成分は全く使用されていない。したがって、変換関数の小数点以下２桁目以上に影響しない範囲の演算誤差は動き推定結果に影響を与えないことになる。これは上で述べたように、高精細参照画像を用いることにより、変換関数に要求される演算精度が下がったためである。
【００３６】
上で挙げた実施例では内挿演算の回数が減少する一方で、高精細参照画像を格納するために参照画像の４倍の大きさの画像を蓄えるメモリが必要となる。そこで内挿演算の回数は上の実施例よりは多くなるものの、必要となるメモリ容量の小さい方式の実施例を示す。この方式では、現フレームの原画像と参照画像の必要な部分を少しずつ取り込みながら参照画像を高精細化して動き推定に用いる。隣接画素間距離は、現フレームの原画像、参照画像共に水平・垂直方向に１であるとする。なお、ここでは動き推定方式に６角マッチングが使用されていると仮定して、６角マッチングにおける修正処理を実行する回路を中心に説明する。６角マッチングのもう一方の処理である格子点の大まかな動き推定は、「従来の技術」で説明した通り、格子点を含むブロックに対してブロックマッチングを実行することにより行われる。
【００３７】
図７に現フレームの原画像の一部における格子点７０３〜７１１の位置を示す。格子点の間隔を縦横にＮｇ、格子点ごとの動きベクトルの探索範囲を水平・垂直方向に±Ｎｓであるとすれば、参照画像の縦横２Ｎｇ  ＋  ２Ｎｓの範囲７０１と、現フレームの原画像の縦横２Ｎｇの範囲７０２（斜線の範囲）に含まれる画素を使えば、格子点７０３に関する６角マッチングの修正処理を行うことができる（実際にはこれらより狭い範囲でも良いが、処理を簡略化するために正方形の領域を用いる）。したがって、修正処理を行う装置はこれらの範囲に含まれる画素の輝度値をあらかじめ読み込むことにより、以後の処理を外部のフレームメモリとは独立した状態で実行することができる。またこの場合、格子点７０３の修正処理を行う前に格子点７０８の修正処理を行うようにすれば、既に範囲７０１および７０２の画素の一部が修正処理を行う装置に読み込まれていることになる。したがって、このときには図８に示すように参照画像の範囲８０１および現フレームの原画像の範囲８０２のみを追加して読み込むようにすれば良い（図８において図７と同じ参照番号は同じものをさしている）。この追加読み込みのときには、格子点７０８の動き推定処理に使用した画素情報の一部は必要なくなるので、この情報が入っていたメモリの上に範囲８０１および８０２の情報を書き込んでも良い。このようにして、動き推定を行う格子点が左から右に移動するごとに、新たに必要な情報のみを読み込むようにすれば処理を簡略化することができる。
【００３８】
図９に、図７および８に示した方式に従って６角マッチングの修正処理を行う装置の動き推定部９０９の例を示す。この図において矢印はデータの流れを表しており、図４と同じ参照番号は同じものをさしている。動き推定部９０９は、図４の動き推定部４０１と異なる構成で同じ働きをする。入力の現フレームの原画像４０２と参照画像４０４はそれぞれフレームメモリ９０１と９０３に蓄えられる。これに対してまず格子点の大まかな動き推定が回路９０２で実行され、求められた動きベクトルに従って参照画像における格子点の座標の情報が格子点座標メモリ９０４に蓄えられる。続いて修正処理部９０５が６角マッチングにおける修正処理を行う。以下では、図８の例にならって、直前に格子点７０８に対する処理が行われた場合の格子点７０３に対する修正処理に関して説明する。修正処理部９０５は、高精細化回路９０７とマッチング処理回路９０６からなっている。まず高精細化回路９０７は、参照画像が蓄えられたフレームメモリ９０３から新たに必要な範囲（図８の例では、範囲８０１）の画素の輝度値情報を読み出す。この情報に対して内挿処理を行い、動き推定において必要となる範囲の高精細参照画像を作成して、マッチング処理回路９０６に与える。マッチング処理回路では、同様に現フレームの原画像のフレームメモリ９０１からも新たに必要な範囲（図８の例では、範囲８０２）の輝度値情報を読み込む。マッチング処理回路は自分自身で修正処理に必要な範囲の高精細参照画像と現フレームの原画像を蓄えるフレームメモリを持っており、このメモリを利用して処理を行う。マッチング処理回路はさらに格子点座標メモリ９０４から参照画像における格子点の座標情報の中で新たに必要となったもの（図８の例では、格子点７０４、７０６、７１１の座標情報。これは格子点７０７、７０８、７１０の座標情報が前の処理で使用されているため。）を読み込み、６角マッチングの修正処理を行う。この処理結果に従い、修正された参照画像における格子点の座標（図８の例では、格子点７０３の座標）を格子点座標メモリ９０４に書き込む。以上で格子点７０３の修正は終了し、修正処理部は図８の格子点７０４の修正処理に移る。修正処理がすべて終了すると、格子点座標メモリ９０４に蓄えられた情報は動きベクトル演算回路９０８において格子点ごとの動きベクトルに変換されて動き情報４１５として出力される。また、予測画像の予測誤差を計算するために、現フレームの原画像の情報４１１も出力される。
【００３９】
図１０に図９の処理において並列処理を導入した例を示す。図９と同じ参照番号は同じものをさしている。この例では、６角マッチングにおける修正処理を行う修正処理部が複数存在し、処理を分担している。参照画像と現フレームの原画像を蓄えているフレームメモリ９０１と９０３から輝度値情報を読み出すためには、共通のデータバス１００１とアドレスバス１００２を利用する。また、参照画像における格子点の座標を蓄えた格子点座標メモリ９０４から情報を読み出したり、情報を書き込む場合には共通のデータバス１００５とアドレスバス１００４を用いる。これらのバスを介して、格子点の大まかな動き推定を行う回路９０２、６角マッチングの修正処理を行う回路９０５、１００３は情報の転送を行う。修正処理部９０５と１００３は同じ構成である。同様の構成の修正処理部をさらに加えることのより、修正処理をさらに高速に実行することができる。修正処理部は輝度値情報の読み込みと格子点座標情報の読み込みと書き込みのとき以外はほぼ独立に処理を行うことができるため、メモリへのアクセスの衝突を避けて並列に処理を行うことができる。
【００４０】
図８、９、１０に示した実施例では、修正処理において参照画像の１画素について約（２＋  ２Ｎｓ  ／Ｎｇ）×（ｍ×ｍ  −  １）回の内挿演算が必要であり、図４で示した実施例の約（２＋  ２Ｎｓ  ／Ｎｇ）倍の回数を必要とする。しかし、高精細参照画像全体を蓄えるメモリが必要ないため、全体で必要なメモリ容量を小さくすることができる。
【００４１】
回路における乗除算のしやすさを考慮すると、ｍは２のべき乗であることが望ましい。ｍを小さくすると回路規模を小さくすることができる。しかし、一方で動き推定における座標（動きベクトル）の近似精度が悪くなり、数２の演算で予測誤差の大小関係が逆転しやすくなるために動き推定結果に狂いが生じ、予測特性は劣化する。これに対し、ｍを大きくすると逆の現象が起こる。回路規模を考慮すれば、ｍの値としては４以下が望ましい。また、予測特性を考慮すれば、ｍの値としては２以上が望ましい。したがって、両者のバランスを考えてｍの値としては２、４が適当である。許容される予測誤差と回路規模に応じて適当なｍの値は選択すれば良い。
【００４２】
画素密度が縦横にｍ倍の高精細参照画像を用いて動き推定を行なうことは、数３における変換関数ｆｉ（ｘ，  ｙ）とｇｉ（ｘ，  ｙ）の値が１／ｍの整数倍となるように制限される（変換関数の最小単位が隣接画素間距離の１／ｍとなる）ことを意味する。しかし、これはあくまで動き推定の際の制限で、予測画像の合成の際にもこの制限を守る必要はない。一方で、空間変換に基づく動き補償では送信側と受信側における予測画像のミスマッチ（送信側と受信側における変換関数の演算精度が異なることが原因で、両者で合成される予測画像に不一致が生じること）を防ぐため、予測画像を合成するときの変換関数の演算精度に関して何らかの基準を設定する必要がある。この基準を設定する方法の一つとして、動き推定の際と同様に予測画像を合成する際の変換関数に最小単位を設ける方法がある。しかし、上で述べた理由から、このときの最小単位は必ずしも動き推定における最小単位と同じ１／ｍである必要はない。一般的に動き推定が終了し、動きパラメータが確定していても、予測画像の合成における変換関数の演算精度を上げると予測誤差は減少する。したがって、予測画像の合成のときには動き推定のときよりも動きベクトルの最小単位を小さくすることにより、予測誤差を減少させることができる。予測画像の合成の際には、輝度値の内挿演算は１画素につき１回のみ行なわれるため、この演算が多少複雑になっても動き推定の場合ほど全体の処理量に大きな影響を及ぼさない。
【００４３】
なお、以下の変形も本発明に含まれることは明らかである。
【００４４】
（１）輝度値の内挿に用いる関数として、本明細書では共１次内挿をとりあげたが、これ以外の関数を用いても良い。関数が複雑になると、内挿演算の回数を減らすことの効果は大きくなる。
【００４５】
（２）変換関数の種類として、本明細書ではアフィン変換を中心にとりあげたが、これ以外の変換関数を用いても良い。同一パッチ内の画素が共通の動きベクトルに従う必要がなく、画素の動きベクトルの垂直・水平成分が隣接画素間距離の整数倍以外の値を取り得る限り、本発明は有効である。
【００４６】
（３）パッチの形状は、画素の集合を特定するものであれば良く、特に本明細書でとりあげた３角形でなくても良い。
【００４７】
（４）空間変換に基づく動き補償に関し、本明細書ではパッチの境界で動きベクトルが連続的に変化する方式をとりあげた。しかし、例えばパッチごとに動きパラメータをそのまま伝送する方式など、パッチ境界で不連続を許容する方式であっても良い。
【００４８】
（５）動き推定アルゴリズムとして、本明細書ではブロックマッチングと６角マッチングをとりあげたが、これは他のマッチングに基づく方式であっても良い。予測誤差の評価が多数回行なわれる方式である限り、本発明は有効である。
【００４９】
（６）空間変換に基づく動き補償において、本明細書でとりあげた例のように伝送される動き情報が格子点の動きベクトルでなくても良い。動き情報は、上記項目（４）でとりあげた例のように、パッチごとの変換関数を特定するものであれば良い。
【００５０】
（７）実施例では、ｍ１＝ｍ２の場合について述べたが、両者が異なっていても良い。
【００５１】
（８）本明細書では、現フレームのパッチ構造を固定して参照画像のパッチを変形させる方式に関して説明したが、逆に参照画像のパッチ構造を固定して現フレームのパッチを変形させる方式であっても良い。
【００５２】
（９）本明細書では、１個の予測画像を合成するために用いる参照画像の数は１個として説明したが、複数の参照画像を用いる方式であっても良い。
【００５３】
【発明の効果】
本発明により、同一パッチに所属するすべての画素が共通の動きベクトルを持つ制約がなく、かつ画素の動きベクトルの水平・垂直成分が隣接画素間距離の整数倍以外の値を取り得る動き補償方式の動き推定処理において、輝度値の内挿の演算を行なう回数を減らすことが可能となる。
【図面の簡単な説明】
【図１】半画素精度のブロックマッチングにおける２段階探索の処理の例を示した図である。
【図２】空間変換に基づく動き補償の処理の例を示した図である。
【図３】空間変換に基づく動き補償における動き推定処理の例として、６角マッチングとよばれる方式の処理を示した図である。
【図４】高精細参照画像を活用する画像符号化装置の例を示した図である。
【図５】輝度値の内挿により、参照画像を高精細化する回路の例を示した図である。
【図６】変換関数の演算結果から、高精細参照画像における輝度値を得る回路の例を示した図である。
【図７】６角マッチングの修正処理で使用する画素の範囲を示した図である。
【図８】６角マッチングの修正処理において隣の格子点に続いて修正処理を行う場合に、新たに必要となる画素の範囲を示した図である。
【図９】現フレームの原画像と参照画像の必要な部分を少しずつ取り込みながら参照画像を高精細化して動き推定に用いる方式を示した図である。
【図１０】現フレームの原画像と参照画像の必要な部分を少しずつ取り込みながら動き推定に用いる方式に並列処理を導入した場合を示した図である。
【符号の説明】
１０１、１０２、１０３、１０４…半画素精度のブロックマッチングにおけるマッチング処理の例、２０１…参照画像、２０２…現フレームの原画像、２０３…動き推定後の参照画像のパッチと格子点、２０４、２０９…パッチ、２０５〜２０７、２１０〜２１２、３０１、３０３〜３０９、７０３〜７１１…格子点、２０８…現フレームの原画像のパッチと格子点、３０２…修正処理におけるマッチングの対象となる多角形、４０１、９０９…動き推定部、４０２、４１１…現フレームの原画像、４０３、４０７、９０１、９０３…フレームメモリ、４０４…参照画像、４０５…参照画像高精細化回路、４０６…高精細参照画像、４０８…近似輝度値、４０９…マッチング処理回路、４１０…予測画像合成回路、４１２…減算器、４１３…予測誤差、４１４…予測誤差符号化器、４１５…動き情報、４１６…予測誤差情報、５０１…ライン遅延回路、５０２、５０３…画素遅延回路、５０４〜５０７…参照画像の画素の輝度値、５０８〜５１１…乗算器、５１２〜５１５、６０３…加算器、５１６…シフトレジスタ、５１７〜５２０…高精細参照画像の画素の輝度値、６０１、６０２…参照画像における座標値の固定小数点表現（変換関数の演算結果）、６０４…小数点以下２桁目以下（２進表現）切り捨て回路、６０５、６０６…高精細参照画像における座標値、６０７…座標−アドレス変換回路、７０１…参照画像において修正に使用される範囲、７０２…現フレームの原画像において修正に使用される範囲、８０１…参照画像において追加される範囲、８０２…現フレームの原画像において追加される範囲、９０２…６角マッチングにおける格子点の大まかな動き推定を行う回路、９０４…参照画像における格子点の座標メモリ、９０５、１００３…６角マッチングの修正処理部、９０６…マッチング処理回路、９０７…参照画像の一部の高精細化回路、９０８…動きベクトル演算回路、１００１…輝度値情報のデータバス、１００２…輝度値情報のアドレスバス、１００４…格子点の座標情報のアドレスバス、１００５…格子点の座標情報のデータバス。
【図１】
0003634878.tif 000010
【図２】
0003634878.tif 000011
【図３】
0003634878.tif 000012
【図４】
0003634878.tif 000013
【図５】
0003634878.tif 000014
【図６】
0003634878.tif 000015
【図７】
0003634878.tif 000016
【図８】
0003634878.tif 000017
【図９】
0003634878.tif 000018
【図１０】
0003634878.tif 000019