図面 (/)

技術 動きベクトル推定方法,動きベクトル推定装置,動きベクトル推定プログラムおよび動きベクトル推定プログラム記録媒体

出願人 日本電信電話株式会社
発明者 坂東幸浩高村誠之上倉一人八島由幸
出願日 2005年8月29日 (15年3ヶ月経過) 出願番号 2005-248054
公開日 2007年3月15日 (13年9ヶ月経過) 公開番号 2007-067551
状態 特許登録済
技術分野 TV信号の圧縮,符号化方式 TV信号の圧縮,符号化方式 圧縮、伸長・符号変換及びデコーダ
主要キーワード 差分補正値 最小性 差異領域 参照領域中 差異部分 準最適解 予測性能 補正値テーブル
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2007年3月15日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (14)

課題

動きベクトル小数画素精度表現する動き補償(MC)において,予測誤差の最小化を完全に保証しつつ,探索の効率的な枝刈りを行い,計算量を低減する。

解決手段

小数画素精度の動きベクトルに対する予測誤差の下限値を,既に計算済み丸め誤差を用いて算出し(S3),この下限値と予測誤差の最小値として格納された値との大小を比較する(S4)。下限値のほうが小さい場合にのみ動きベクトルに対する予測誤差を計算し(S5),予測誤差の最小値を求める探索を行う(S6,S7)。下限値のほうが小さくない場合には探索の枝刈りを行い,現在の動きベクトルに対する予測誤差の計算を省略する。

概要

背景

動画像符号化における重要な技術の一つにブロックマッチングに基づく動き補償(MC)がある。この方法では,符号化対象フレームft (p)(p∈{(x,y)|x=0,1,... ,X−1,y=0,1,... ,Y−1})をいくつかの領域に分割し,領域毎に動き補償(MC)を用いた次のようなフレーム間予測が行われる。

ここで,Bi は第i番目の領域であり,vi は次式を満たす動きベクトルである。

なお,Ri はBi に対応する探索領域であり,

は,次に続く関数を最小化するvを返す。すなわち,探索範囲Ri において,領域Bi 内での予測誤差を最小化するvが動きベクトルvi として選ばれる。

予測誤差の最小性保証した動きベクトル探索高速化として,代表的なものにSEA(非特許文献1参照)と呼ばれる手法がある。同手法は,MC誤差の下限値を予め見積もり,その下限値をもとに探索点絞り込む手法である。同手法ではMC誤差E(v)に対して,次式の下限値を用いる。

E(v)≧C−S(v) (2)
ここで,Cは符号化ブロック画素値和,S(v)は参照ブロックの画素値和であり,各々次式で表される。

式(2)の証明は,以下の通りである。

予測誤差の低減を目的として,動きベクトルを小数画素精度表現する動き補償が検討されている。1/m画素精度の動き補償の場合,動きベクトルは次式を満たすベクトルとして求める。

ここで,f* t-1 (p)はft-1 (p)から生成される補間画像であり,1/m画素間隔で画素値をもつ。例えば,ISO/IEC13818-2MPEG−2における1/2画素精度の動き補償の場合,次のような補間画像を用いる。

ここで,δx =(1,0),δy =(0,1)であり,pは整数値を要素とするベクトルである。つまり,予測時の参照フレームの位置が2画素の中心なら(式(7b)または式(7c)),2つの画素値の丸め付き平均を予測値として使用し,同位置が正方形頂点に並んだ4画素の中心なら,4つの画素値の丸め付き平均を予測値として使用することになる(式(7d))。なお,式(7b)〜式(7d)における1/2および2/4の演算は,例えばビットシフト演算によって行われ,小数点以下は切り捨てられる。

図1は,式(7b)〜式(7d)の補間処理における参照画素位置を示している。例えば図1(a)は,補間画素位置が水平半画素位置の場合であり,矢印で示した円形がその補間画素位置である。黒い四角形が補間に用いる参照画素位置であり,この黒い四角形の側に示した数字は補間時の重み係数を表している。また,図1(b)は,補間画素位置が垂直半画素位置の場合を,図1(c)は,補間画素位置が対角半画素位置の場合を示している。

以後,式(1)より求めた動きベクトルを用いる動き補償を整数画素精度MCと呼ぶ。一方,式(6)より求めた動きベクトルを用いる動き補償を小数画素精度MCと呼ぶ。また,i番目の領域に注目して議論するので,Bi はBと表す。

小数画素精度MCの場合,整数画素精度MCに比較して動きベクトル探索の計算量が増大する。これは,探索領域内に含まれる探索点の数が増加するためである。探索領域が水平方向w,垂直方向hのw×h点の画素を含む場合,整数画素精度MCにおける探索点がw×h点であるのに対し,1/m画素精度の小数画素精度MCにおける探索点は{m(w−1)+1}×{m(h−1)+1}点となる。

小数画素精度MCの動きベクトル探索において計算量を低減させる場合,最適解である式(6)の動きベクトルを求めることをあきらめ,式(6)の準最適解に相当する動きベクトルを求める方法が多く検討されている。この場合,計算量の低減と引き替えに,予測誤差は増加してしまう。しかし,予測誤差を減少させるために導入された小数画素精度MCにおいて,こうした予測誤差の増加は望ましくない。このため,予測誤差を増加させることなく計算量を低減させる動きベクトル探索法が必要となる。

計算量を低減させる手法としては,上述した非特許文献1に示されているSEAがあるが,SEAは整数画素精度MCへの適用にとどまり,小数画素精度MCについての検討はなされていない。

そこで,本発明者等は,小数画素精度MCについても,予測誤差の最小化を保証した上で,下限値との比較による動きベクトル探索の枝刈りを行い,計算量の低減を図る技術を,非特許文献2において提案している。非特許文献2の手法によれば,特に小数MC誤差の下限値を求める際に,既に計算した結果を利用することにより計算量の増加を抑え,少ない計算量で小数画素精度MCのもつ高い予測性能を実現することができる。
W.Li and E.Salari :“Successive elimination algorithm for motion estimation”,IEEE Transactions on Image Processing ,Volume 4,Issue 1 ,Jan.,pp.105-107,1995.
東幸浩,高誠之,八島由幸:「全探索小数画素精度動き推定の高速化」,情報処理学会研究報告,2004-AVM-44 ,2004/3/4.

概要

動きベクトルを小数画素精度で表現する動き補償(MC)において,予測誤差の最小化を完全に保証しつつ,探索の効率的な枝刈りを行い,計算量を低減する。小数画素精度の動きベクトルに対する予測誤差の下限値を,既に計算済み丸め誤差を用いて算出し(S3),この下限値と予測誤差の最小値として格納された値との大小を比較する(S4)。下限値のほうが小さい場合にのみ動きベクトルに対する予測誤差を計算し(S5),予測誤差の最小値を求める探索を行う(S6,S7)。下限値のほうが小さくない場合には探索の枝刈りを行い,現在の動きベクトルに対する予測誤差の計算を省略する。

目的

本発明は,非特許文献2に記載された「全探索小数画素精度動き推定の高速化」の技術を,さらに改良し,小数画素精度の動き推定におけるMC誤差の下限値の計算において,参照画素値和の計算上生じる丸め誤差も考慮して,タイトな下限値を算出することにより,探索における枝刈りの促進を図り,小数画素精度MCにおける動きベクトル探索のさらなる高速化を実現することを目的とする。

効果

実績

技術文献被引用数
1件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定方法であって,動きベクトルおよび参照画素をもとに,小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し,被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後フレーム間予測誤差に対する下限値を算出する過程と,前記算出された下限値を用いて動きベクトル探索枝刈りを行い,フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する過程とを有することを特徴とする動きベクトル推定方法。

請求項2

請求項1記載の動きベクトル推定方法において,前記下限値を算出する際,丸め誤差を参照画素群下位ビットの値に応じて予めルックアップテーブルに格納し,そのルックアップテーブルを参照することにより決定した丸め誤差を用いて下限値を算出することを特徴とする動きベクトル推定方法。

請求項3

請求項2記載の動きベクトル推定方法において,前記丸め誤差をルックアップテーブルに格納する際,補間処理の対象となる小数画素位置に応じて個別のルックアップテーブルに格納することを特徴とする動きベクトル推定方法。

請求項4

請求項1記載の動きベクトル推定方法において,前記下限値を算出する際,既に予測誤差の下限値が算出された第1の動きベクトルと,これから予測誤差の下限値を算出する第2の動きベクトルとの,2つの動きベクトルが指す参照領域差異部分から,これらの2つの動きベクトルが指す参照領域の予測誤差の下限値の差分値を算出し,前記第1の動きベクトルの予測誤差の下限値をもとに,前記第2の動きベクトルに対する予測誤差の下限値を算出することを特徴とする動きベクトル推定方法。

請求項5

請求項4記載の動きベクトル推定方法において,前記下限値を算出する際,前記2つの動きベクトルが指す参照領域の差異部分に対する丸め誤差を,参照画素群の下位ビットの値に応じて予めルックアップテーブルに格納し,そのルックアップテーブルを参照することにより前記差異部分に対する丸め誤差を決定し,前記第1の動きベクトルに対する予測誤差の下限値をもとに,前記第2の動きベクトルに対する予測誤差の下限値を算出することを特徴とする動きベクトル推定方法。

請求項6

小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定装置であって,動きベクトルおよび参照画素をもとに,小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し,被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する手段と,前記算出された下限値を用いて動きベクトル探索の枝刈りを行い,フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する手段とを備えることを特徴とする動きベクトル推定装置。

請求項7

小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトルを,コンピュータによって推定する動きベクトル推定プログラムであって,前記コンピュータを,動きベクトルおよび参照画素をもとに,小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し,被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する手段と,前記算出された下限値を用いて動きベクトル探索の枝刈りを行い,フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する手段として機能させるための動きベクトル推定プログラム。

請求項8

小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトルを,コンピュータによって推定する動きベクトル推定プログラムを記録したコンピュータ読み取り可能な記録媒体であって,前記コンピュータを,動きベクトルおよび参照画素をもとに,小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し,被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する手段と,前記算出された下限値を用いて動きベクトル探索の枝刈りを行い,フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する手段として機能させるためのプログラムを記録した動きベクトル推定プログラム記録媒体

技術分野

0001

本発明は,高能率画像信号符号化技術に関し,特に,小数画素精度動き補償における動きベクトルの探索を高速に行うための技術に関するものである。

背景技術

0002

動画像符号化における重要な技術の一つにブロックマッチングに基づく動き補償(MC)がある。この方法では,符号化対象フレームft (p)(p∈{(x,y)|x=0,1,... ,X−1,y=0,1,... ,Y−1})をいくつかの領域に分割し,領域毎に動き補償(MC)を用いた次のようなフレーム間予測が行われる。

0003

ここで,Bi は第i番目の領域であり,vi は次式を満たす動きベクトルである。

0004

なお,Ri はBi に対応する探索領域であり,

0005

は,次に続く関数を最小化するvを返す。すなわち,探索範囲Ri において,領域Bi 内での予測誤差を最小化するvが動きベクトルvi として選ばれる。

0006

予測誤差の最小性保証した動きベクトル探索の高速化として,代表的なものにSEA(非特許文献1参照)と呼ばれる手法がある。同手法は,MC誤差の下限値を予め見積もり,その下限値をもとに探索点絞り込む手法である。同手法ではMC誤差E(v)に対して,次式の下限値を用いる。

0007

E(v)≧C−S(v) (2)
ここで,Cは符号化ブロック画素値和,S(v)は参照ブロックの画素値和であり,各々次式で表される。

0008

式(2)の証明は,以下の通りである。

0009

予測誤差の低減を目的として,動きベクトルを小数画素精度で表現する動き補償が検討されている。1/m画素精度の動き補償の場合,動きベクトルは次式を満たすベクトルとして求める。

0010

ここで,f* t-1 (p)はft-1 (p)から生成される補間画像であり,1/m画素間隔で画素値をもつ。例えば,ISO/IEC13818-2MPEG−2における1/2画素精度の動き補償の場合,次のような補間画像を用いる。

0011

ここで,δx =(1,0),δy =(0,1)であり,pは整数値を要素とするベクトルである。つまり,予測時の参照フレームの位置が2画素の中心なら(式(7b)または式(7c)),2つの画素値の丸め付き平均を予測値として使用し,同位置が正方形頂点に並んだ4画素の中心なら,4つの画素値の丸め付き平均を予測値として使用することになる(式(7d))。なお,式(7b)〜式(7d)における1/2および2/4の演算は,例えばビットシフト演算によって行われ,小数点以下は切り捨てられる。

0012

図1は,式(7b)〜式(7d)の補間処理における参照画素位置を示している。例えば図1(a)は,補間画素位置が水平半画素位置の場合であり,矢印で示した円形がその補間画素位置である。黒い四角形が補間に用いる参照画素位置であり,この黒い四角形の側に示した数字は補間時の重み係数を表している。また,図1(b)は,補間画素位置が垂直半画素位置の場合を,図1(c)は,補間画素位置が対角半画素位置の場合を示している。

0013

以後,式(1)より求めた動きベクトルを用いる動き補償を整数画素精度MCと呼ぶ。一方,式(6)より求めた動きベクトルを用いる動き補償を小数画素精度MCと呼ぶ。また,i番目の領域に注目して議論するので,Bi はBと表す。

0014

小数画素精度MCの場合,整数画素精度MCに比較して動きベクトル探索の計算量が増大する。これは,探索領域内に含まれる探索点の数が増加するためである。探索領域が水平方向w,垂直方向hのw×h点の画素を含む場合,整数画素精度MCにおける探索点がw×h点であるのに対し,1/m画素精度の小数画素精度MCにおける探索点は{m(w−1)+1}×{m(h−1)+1}点となる。

0015

小数画素精度MCの動きベクトル探索において計算量を低減させる場合,最適解である式(6)の動きベクトルを求めることをあきらめ,式(6)の準最適解に相当する動きベクトルを求める方法が多く検討されている。この場合,計算量の低減と引き替えに,予測誤差は増加してしまう。しかし,予測誤差を減少させるために導入された小数画素精度MCにおいて,こうした予測誤差の増加は望ましくない。このため,予測誤差を増加させることなく計算量を低減させる動きベクトル探索法が必要となる。

0016

計算量を低減させる手法としては,上述した非特許文献1に示されているSEAがあるが,SEAは整数画素精度MCへの適用にとどまり,小数画素精度MCについての検討はなされていない。

0017

そこで,本発明者等は,小数画素精度MCについても,予測誤差の最小化を保証した上で,下限値との比較による動きベクトル探索の枝刈りを行い,計算量の低減を図る技術を,非特許文献2において提案している。非特許文献2の手法によれば,特に小数MC誤差の下限値を求める際に,既に計算した結果を利用することにより計算量の増加を抑え,少ない計算量で小数画素精度MCのもつ高い予測性能を実現することができる。
W.Li and E.Salari :“Successive elimination algorithm for motion estimation”,IEEE Transactions on Image Processing ,Volume 4,Issue 1 ,Jan.,pp.105-107,1995.
東幸浩,高誠之,八島由幸:「全探索小数画素精度動き推定の高速化」,情報処理学会研究報告,2004-AVM-44 ,2004/3/4.

発明が解決しようとする課題

0018

上述のように,非特許文献2に記載された「全探索小数画素精度動き推定の高速化」の技術によれば,SEAの小数画素精度MCへの適用にあたって,探索点数の増加に伴う計算量増加の問題が軽減され,小数画素精度MCにおける動きベクトル探索の高速化が図られている。

0019

本発明は,非特許文献2に記載された「全探索小数画素精度動き推定の高速化」の技術を,さらに改良し,小数画素精度の動き推定におけるMC誤差の下限値の計算において,参照画素値和の計算上生じる丸め誤差も考慮して,タイトな下限値を算出することにより,探索における枝刈りの促進を図り,小数画素精度MCにおける動きベクトル探索のさらなる高速化を実現することを目的とする。

0020

また,本発明は,上記丸め誤差の算出を少ない計算量で行い,計算量の増加を抑えた動きベクトルの推定を実現することを目的とする。

課題を解決するための手段

0021

二つの動きベクトルv,uのMC誤差を比較する場合,両動きベクトルに対するMC誤差を直接比較するのではなく,動きベクトルvのMC誤差E(v)に対して,動きベクトルuのMC誤差E(u)の下限値L(u)との大小比較を行う。この時,
E(v)≦L(u)
であれば,L(u)がMC誤差E(u)の下限値であるため,
E(v)≦E(u)
となり,E(u)を算出して比較する必要はない。つまり,E(u)の算出は,
L(u)<E(v)
となる場合のみ行えば十分である。

0022

後述するように,MC誤差の下限値はMC誤差に比べて,少ない計算量での算出が可能である。このため,MC誤差の下限値との比較を行い,MC誤差の算出を省くことにより,予測誤差の最小化を保証した上で,計算量の低減を図ることができる。

0023

本発明は,小数画素精度MCにおいて,フレーム間予測誤差に対する下限値を算出し,下限値を用いた探索の枝刈りを行うとともに,この下限値を算出する際,既に計算済み加算結果およびシフト演算等を用いて,丸め誤差を算出し,その丸め誤差を用いて下限値を算出する。丸め誤差を考慮した下限値の算出を行うことにより,さらにタイトな枝刈りが可能であり,全探索を行った場合と同等の精度を保持しつつ,大きく計算量を低減することができる。

0024

また,本発明は,上記下限値を算出する際,関連する参照画素群の下位nビット(nは補間処理で参照される画素数により定まる数)の値に応じて,丸め誤差を予めルックアップテーブルに格納しておき,同テーブルを参照して丸め誤差の補正値を決定し,下限値を算出することにより,さらに計算量を低減することができる。

0025

また,丸め誤差をルックアップテーブルに格納する際,補間処理の対象となる小数画素位置に応じて個別のルックアップテーブルに格納することにより,ルックアップテーブルに必要となるメモリ容量を小さくすることができる。

0026

また,本発明は,予測誤差の下限値を算出する際,2つの動きベクトルが指す参照領域差異部分のみに注目し,2つの動きベクトルが指す参照領域の予測誤差の下限値の差分値を算出し,一方の動きベクトルの予測誤差の下限値をもとに,他方の動きベクトルに対する予測誤差の下限値を算出する。これにより,計算済みの結果を利用して計算量の低減を図ることができる。

0027

また,本発明は,予測誤差の下限値を算出する際,上記2つの動きベクトルが指す参照領域の差異部分に対する丸め誤差をルックアップテーブルに格納しておき,同テーブルを参照し,一方の動きベクトルに対する予測誤差の下限値をもとに,他方の動きベクトルに対する予測誤差の下限値を算出する。ルックアップテーブルを利用して差異部分に対する丸め誤差を求めることにより,計算量を大幅に低減することができる。

発明の効果

0028

本発明を用いれば,小数画素精度MCにおける予測誤差の最小化を完全に保証しつつ,動きベクトル探索における計算量の低減が可能となる。このため,小数画素精度MCにおいて問題とされてきた計算量の増加を解消でき,少ない計算量で,小数画素精度MCによる高い予測性能を享受できる。特に,補間処理の対象となる小数画素位置の参照画素値の計算において生じる丸め誤差を求め,これにより補正した下限値を算出することにより,探索における枝刈りの効果が大きい。

発明を実施するための最良の形態

0029

[第1の実施形態]
小数画素精度の動きベクトルv* に対するMC誤差(小数画素精度MC誤差)の下限値を導出する。以下では,式(7a)〜(7d)の補間画像を用いる1/2画素精度MCを例にあげ,説明する。このとき,動きベクトルv* の取り得る値は次の4通りである。

0030

ここで,δx =(1,0),δy =(0,1)であり,vは整数値を要素とするベクトルである。なお,以下では,動きベクトルv* がv* =vとして整数値を要素とする場合,整数動きベクトルと呼び,それ以外を小数動きベクトルと呼ぶ。以下,v* の値に応じてE(v* )を4通りに場合分けし,各下限値を求める。

0031

(i)v* =vの場合:
動きベクトルは参照フレーム中の画素位置を指すため,整数画素精度MCにおけるSEAの場合と同様に,MC誤差は次の下限値を持つ。

0032

E(v* )≧C−S(v) (9)
ここで,C,S(v)は,各々式(3),式(4)で表されるものとする。

0033

(ii)v* =v−δx /2の場合:
動きベクトルの指す参照フレームの位置は2画素の中心となり,MC誤差E(v* )は次の下限値を持つ。

0034

E(v* )≧C−S(v)/2−S(v−δx )/2−Rh (v) (10)
ここで,Rh (v)は丸め誤差の補正値であり,次式より求まる。

0035

ここで,○付きの+はビット毎の論理積を行う演算子を表す。

0036

式(10)の証明は,以下の通りである。なお,以下の証明において,式(12a)から式(12b)への展開では,動きベクトルの指す参照フレームの位置は2画素の中心となることから,式(7b)を用いた。

0037

(iii) v* =v−δy /2の場合:
上述の(ii)と同様に動きベクトルの指す参照フレームの位置は2画素の中心となり,MC誤差は次の下限値を持つ。

0038

E(v* )≧C−S(v)/2−S(v−δy )/2−Rv (v) (13)
証明は(ii)の場合と同様に行える。なお,Rv (v)は丸め誤差の補正値であり,次式より求まる。

0039

(iv)v* =v−(δx +δy )/2の場合:
動きベクトルの指す参照フレームの位置は4画素の中央となり,MC誤差は次の下限値を持つ。

0040

E(v* )≧C−S(v)/4−S(v−δx )/4−S(v−δy )/4
−S(v−δx −δy )/4−Rd (v) (15)
なお,Rd (v)は丸め誤差の補正値であり,次式より求まる。

0041

式(15)の証明は,以下の通りである。なお,以下の証明において,式(17a)から式(17b)への展開では,動きベクトルの指す参照フレームの位置は4画素の中央となることから,式(7d)を用いた。

0042

以上(i)〜(iv)をまとめると,MC誤差の下限値L(v* )は次式となる。

0043

[第2の実施形態:補正値テーブルの利用]
丸め誤差の補正値は補正値テーブルと呼ぶルックアップテーブルに格納し,予測誤差の下限値の計算時には,同テーブルを参照するものとする。以下,同テーブルの作成法について詳述する。

0044

上述(ii)の場合:
Rh (v)は,以下のように展開できる。

0045

この式(19)から明らかであるように,参照領域をx方向に17画素,y方向に1画素の幅を持つ17×1画素の矩形領域に分割したとすると,各矩形領域における丸め誤差は独立に定まる。そこで,同矩形領域単位で上述の丸め誤差の補正値をルックアップテーブルに格納する。格納する値は,以下の通りである。

0046

この補正値は,17の画素の下位1ビットから定まり,0から16の値を取り得る。従って,この補正値に対するルックアップテーブルのサイズは,
5×217=0.65536[Mbits]
となる。

0047

上述 (iii)の場合:
Rv (v)は,以下のように展開できる。

0048

この式(21)から明らかであるように,各列における丸め誤差は独立に定まる。すなわち,参照領域をx方向に1画素,y方向に17画素の幅を持つ1×17画素の矩形領域に分割したとすると,各矩形領域における丸め誤差は独立に定まる。そこで,同矩形領域単位で上述の丸め誤差の補正値をルックアップテーブルに格納する。格納する値は,以下の通りである。

0049

この補正値は,17個の画素の下位1ビットから定まり,0から16の値を取り得る。従って,この補正値に対するルックアップテーブルのサイズは,
5×217=0.65536[Mbits]
となる。

0050

上述(iv)の場合:
Rd (v)は,以下のように展開できる。

0051

ここで,Φ(x,y,t)は,以下の通りとする。

0052

Φ(x,y,t)=ft (x,y)+ft (x−1,y)
+ft (x,y−1)+ft (x−1,y−1)
この式(23)から明らかであるように,参照領域中の,x方向に17画素,y方向に2画素の幅を持つ17×2画素の矩形領域における丸め誤差は独立に定まる。しかし,この矩形領域に対して補正値のルックアップテーブルを作成した場合,同ルックアップテーブルのサイズは85.899[Gbits]となり,実装を考慮した場合,現実的なサイズとはいえない。そこで,同矩形領域を2つに分割し,2×8画素の矩形領域単位で補正値をルックアップテーブルに格納する。格納する値は,以下の通りである。

0053

rd (x0 ,y0 ,vx ,vy )に格納する補正値は,18個の画素の下位1ビットから定まり,0から8の値を取り得る。従って,このルックアップテーブルのサイズは,
4×218=1.0486[Mbits]
となる。

0054

[第3の実施形態]
連続した動きベクトルに対する予測誤差の最小値を求める場合,隣接参照領域における差異領域に注目することで計算量を削減できる。予測誤差の下限値が式(18)で与えられる場合,L(v* −δx )とL(v* )とは,以下の関係にある。

0055

ここで,S* (v* ),R* (v* )は,以下の通りである。

0056

図2図3図4に動きベクトルv* −δx およびv* の指す領域を示す。これらは,いずれも動き補償の領域が4×4[画素]の例を図示したものである。

0057

R* (v* −δx )−R* (v* )が計算すべき補正値である。以下,v* の値に応じて,S* (v* −δx )−S* (v* ),R* (v* −δx )−R* (v* )の計算法について詳述する。以下,動き補償の領域は16×16とする。

0058

(i)v* =vの場合:
この場合,丸め誤差は発生しないため,補正値は必要ない。また,S* (v* −δx )−S* (v* )は次式のようになる。

0059

(ii)v* =v−δx /2の場合:
S* (v* −δx )−S* (v* )は次式となる。

0060

また,R* (v* −δx )−R* (v* )は次式となる。

0061

(iii) v* =v−δy /2の場合:
S* (v* −δy )−S* (v* )は次式となる。

0062

また,R* (v* −δy )−R* (v* )は次式となる。

0063

(iv)v* =v−δx /2−δy /2の場合:
S* (v* −δx −δy )−S* (v* )は次式となる。

0064

また,R* (v* −δx −δy )−R* (v* )は次式となる。

0065

[第4の実施形態:差分補正値テーブルの利用]
連続した動きベクトルに対する予測誤差の最小値を求める場合,隣接参照領域における差異領域に注目することで計算量を削減できる。このときに用いる丸め誤差の補正値は差分補正値テーブルと呼ぶルックアップテーブルに格納し,予測誤差の下限値の計算時には,同テーブルを参照するものとする。

0066

予測誤差の下限値が式(18)で与えられる場合,L(v* −δx )とL(v* )とは前述の式(25)の関係にある。S* (v* −δx )−S* (v* )については,前述した「第3の実施形態:丸め誤差の補正値」の通りである。R* (v* −δx )−R* (v* )が差分補正値テーブルに格納される値となる。以下,v* の値に応じて,同テーブルの作成法について詳述する。

0067

(i)v* =vの場合:
この場合,丸め誤差は発生しないため,補正値は必要ない。

0068

(ii)v* =v−δx /2の場合:
R* (v* −δx )−R* (v* )は式(30)となる。同式によれば,x方向に2画素,y方向に16画素の幅を持つ2×16画素の矩形領域における丸め誤差は独立に定まる。この矩形領域に対する補正値のルックアップテーブルのサイズが実装するシステムに対して大きすぎる場合は,同矩形領域を2つに分割し,2×8画素の矩形領域単位で補正値をルックアップテーブル^rh (x0 ,y0 ,dx ,dy )に格納する。^rh (x0 ,y0 ,dx ,dy )を,

0069

として定義すると,R* (v* −δx )−R* (v* )は次式のように表せる。

0070

(iii) v* =v−δy /2の場合:
R* (v* −δy )−R* (v* )は式(32)となる。同式によれば,x方向に1画素,y方向に17画素の幅を持つ1×17画素の矩形領域における丸め誤差は独立に定まる。そこで,同矩形領域単位で補正値をルックアップテーブル^rv (x0 ,y0 ,dx ,dy )に格納する。^rv (x0 ,y0 ,dx ,dy )を,

0071

として定義すると,R* (v* −δy )−R* (v* )は次式のように表せる。

0072

(iv)v* =v−δx /2−δy /2の場合:
R* (v* −δx −δy )−R* (v* )は式(34)となる。同式によれば,x方向に2画素,y方向に17画素の幅を持つ2×17画素の矩形領域における丸め誤差は独立に定まる。この矩形領域に対する補正値のルックアップテーブルのサイズが実装するシステムに対して大きすぎる場合は,同矩形領域を2つに分割し,2×8画素の矩形領域単位で補正値をルックアップテーブル^rd (x0 ,y0 ,dx ,dy )に格納する。^rd (x0 ,y0 ,dx ,dy )を,

0073

として定義すると,R* (v* −δx −δy )−R* (v* )は次式のように表せる。

0074

0075

符号化処理の流れ]
本発明の実施例に係る符号化処理の流れについて,図5を参照して説明する。

0076

テップS1:被予測画素参照画素初期動きベクトルを入力とし,初期動きベクトルとして指定された動きベクトルv* に対して,予測誤差E(v* )を計算し,それを出力する。

0077

ステップS2:被予測画素を入力とし,被予測画素値和レジスタ書き出す。より具体的には,被予測画素値和を式(3)により算出する。

0078

ステップS3:動きベクトル,参照画素を入力とし,この動きベクトルを用いた場合の予測誤差の下限値L(v* )を算出する処理を行う。詳細は,後述する。

0079

ステップS4:ステップS3で求めた下限値L(v* ),予測誤差の最小値として格納された値εを入力とし,L(v* )とεとの大小比較を行い,
L(v* )<ε
であればステップS5の処理に移り,そうでなければステップS8の処理に移る。

0080

ステップS5:被予測画素,参照画素を入力とし,動きベクトルv* に対する予測誤差E(v* )を算出する処理を行い,E(v* )を出力する。

0081

ステップS6:動きベクトルv* に対する予測誤差E(v* ),予測誤差の最小値として格納された値εを入力とし,両値の大小比較を行う処理を行い,
E(v* )<ε
であればステップS7の処理に移り,そうでなければステップS8の処理に移る。

0082

ステップS7:動きベクトルv* ,同動きベクトルに対する予測誤差E(v* )を各々,レジスタM,εに代入する処理を行う。

0083

ステップS8,S9:全ての動きベクトルについて,上述の処理を繰り返し,最終的に,全動きベクトルの中で予測誤差を最小化する動きベクトルとして,レジスタMに格納された値を出力する。

0084

以下にステップS3の詳細を示す。なお,初期動きベクトルに対しては,図6または図7の処理を行う。

0085

「第1の実施形態」の場合:
図6を用いて,「第1の実施形態」の場合の下限値の算出の流れを説明する。

0086

ステップS11:図5のステップS2で書き出した被予測画素値和をレジスタから読み込む。

0087

ステップS12:動きベクトル,参照画素を入力とし,動きベクトルに対する参照画素値和S(v* )を算出し,レジスタに書き出す。より具体的には,式(4)により参照画素値和を算出する。

0088

ステップS13:動きベクトル,参照画素を入力とし,小数画素位置毎の丸め誤差に対する補正値Rh (v* ),Rv (v* ),Rd (v* )を算出し,レジスタに書き出す処理を行う。より具体的には,式(11),式(14),式(16)により求める。

0089

ステップS14:被予測画素値和C,参照画素値和S(v* ),小数画素位置毎の丸め誤差に対する補正値Rh (v* ),Rv (v* ),Rd (v* )を入力とし,動きベクトルの予測誤差の下限値L(v* )を算出する処理を行い,レジスタに書き出す。より具体的には,式(18)により同下限値を求める。

0090

「第2の実施形態」の場合:
図7を用いて,「第2の実施形態」の場合の下限値の算出の流れを説明する。

0091

ステップS21:ステップS11に同じ。

0092

ステップS22:ステップS12に同じ。

0093

ステップS23:予めレジスタに格納された補正値ルックアップテーブルを読み込む。

0094

ステップS24:参照画素,ステップS23で読み込んだ補正値ルックアップテーブルを入力とし,参照画素値に基づき補正値ルックアップテーブルを参照し,小数画素位置毎の丸め誤差に対する補正値を求め,同補正値をレジスタに書き出す処理を行う。

0095

ステップS25:ステップS14に同じ。

0096

「第3の実施形態」の場合:
図8を用いて,「第3の実施形態」の場合の下限値の算出の流れを説明する。

0097

ステップS31:更新前の動きベクトルに対する予測誤差の下限値をレジスタから読み込む。

0098

ステップS32:動きベクトル,参照画素を入力とし,動きベクトルに対する参照画素値和の差分値を算出し,レジスタに書き出す。より具体的には,式(28),式(29),式(31),式(33)により参照画素値和を算出する。

0099

ステップS33:動きベクトル,参照画素を入力とし,小数画素位置毎の丸め誤差に対する補正値の差分値を算出し,レジスタに書き出す処理を行う。より具体的には,式(30),式(32),式(34)により求める。

0100

ステップS34:参照画素値和の差分値,小数画素位置毎の丸め誤差に対する補正値の差分値,更新前の動きベクトルに対する予測誤差の下限値を入力とし,動きベクトルの予測誤差の下限値L(v* )を算出する処理を行う。より具体的には,式(25)により下限値L(v* )を求める。

0101

「第4の実施形態」の場合:
図9を用いて,「第4の実施形態」の場合の下限値の算出の流れを説明する。

0102

ステップS41:ステップS31に同じ。

0103

ステップS42:ステップS32に同じ。

0104

ステップS43:予めレジスタに格納された差分補正値ルックアップテーブルを読み込む。

0105

ステップS44:参照画素,ステップS43で読み込んだ差分補正値ルックアップテーブルを入力とし,参照画素値に基づき差分補正値ルックアップテーブルを参照し,小数画素位置毎の丸め誤差に対する補正値の差分値R* (v* −δx )−R* (v* ),R* (v* −δy )−R* (v* ),R* (v* −δx −δy )−R* (v* )を求め,レジスタに書き出す処理を行う。

0106

ステップS45:ステップS34に同じ。

0107

符号化装置
次に,符号化装置の構成例について説明する。

0108

「第1の実施形態」の場合:
図10に本発明の第1の実施形態に係る装置構成図を示す。

0109

スイッチSW1は,動きベクトルが初期動きベクトルの場合,初期動きベクトル予測誤差算出部101および被予測画素値和決定部102の処理を行う。それ以外の場合,参照画素値和決定部104の処理を行うように切り替える。

0110

初期動きベクトル予測誤差算出部101は,符号化対象ブロックの画素,参照画素,初期動きベクトルに対応する動きベクトルを入力とし,予測誤差を算出する処理を行い,同予測誤差を暫定最小予測誤差記憶部112に出力し,同動きベクトルを暫定最適動きベクトル記憶部113に出力する。

0111

被予測画素値和決定部102は,符号化対象ブロックの画素を入力とし,同ブロック内の被予測画素値和を算出する処理を行い,この被予測画素値和を被予測画素値和記憶部103に出力する。より具体的には,式(3)により被予測画素値和を算出する。

0112

参照画素値和決定部104は,参照画素,動きベクトルを入力とし,参照画素値和を算出する処理を行い,この参照画素値和を参照画素値和記憶部105に出力する。より具体的には,式(4)により参照画素値和を算出する。また,同時に計算過程で算出する値ft-1 (p−v)+ft-1 (p−v+δx ),ft-1 (p−v)+ft-1 (p−v+δy ),ft-1 (p−v)+ft-1 (p−v+δx )+ft-1 (p−v+δy )+ft-1 (p−v+δx +δy )(p∈B)を,部分参照画素値和記憶部116に書き出す。

0113

補正値算出部115は,部分参照画素値和記憶部116から部分参照画素値和を読み込み,予測誤差の下限値の補正値を算出する処理を行い,同補正値を補正値記憶部107に出力する。補正値の具体的な算出は,小数画素位置毎に式(11),式(14),式(16)により求める。

0114

予測誤差下限値決定部106は,動きベクトルを入力とし,被予測画素値和記憶部103,参照画素値和記憶部105,補正値記憶部107から各々,被予測画素値和,参照画素値和,補正値を読み込み,予測誤差の下限値を算出する処理を行い,同下限値を下限値記憶部108に出力する。下限値の具体的な算出は,式(18)により行う。

0115

枝刈り判定部109は,下限値記憶部108および暫定最小予測誤差記憶部112から各々,予測誤差の下限値,およびこれまでに格納された予測誤差の最小値を読み込み,2つの値の大小比較を行い,同下限値の方が小さい場合は,次の処理へ進む(スイッチSW2)。それ以外の場合は,現在の動きベクトルに対する処理を終了する。

0116

予測誤差算出部110は,符号化対象ブロックの画素,参照画素,動きベクトルを入力とし,予測誤差を算出する処理を行い,同予測誤差を出力する。

0117

最適動きベクトル判定部111は,予測誤差算出部110で算出された予測誤差を入力とし暫定最小予測誤差記憶部112からこれまでに格納された予測誤差の最小値を読み込み,2つの値の大小比較を行い,予測誤差算出部110で算出された予測誤差の方が小さい場合,同予測誤差を暫定最小予測誤差記憶部112に記憶し,同動きベクトルを暫定最適動きベクトル記憶部113に記憶する。

0118

動きベクトル制御部114は,以上の処理を全ての動きベクトルに対して繰り返し,最終的に暫定最適動きベクトル記憶部113に記憶された値を最適な動きベクトルとして出力する。

0119

「第2の実施形態」の場合:
図11に本発明の第2の実施形態に係る装置構成図を示す。

0120

初期動きベクトル予測誤差算出部201から動きベクトル制御部214は各々,図10で説明した初期動きベクトル予測誤差算出部101から動きベクトル制御部114と同じ処理を行う。

0121

補正値算出部215は,事前に補正値が格納済みのルックアップテーブル記憶部216から読み出した値を入力として,補正値Rh (v* ),Rv (v* ),Rd (v* )を算出し,補正値記憶部207に書き出す。補正値の具体的な算出は,式(19),式(21),式(23),に従う。

0122

ルックアップテーブル記憶部216には,補正値Rh (v* ),Rv (v* ),Rd (v* )の算出時に参照する補正値テーブルの値rv (x0 ,y0 ,vx ,vy ),rh (x0 ,y0 ,vx ,vy ),rd (x0 ,y0 ,vx ,vy )を予め格納しておく。

0123

「第3の実施形態」の場合:
図12に本発明の第3の実施形態に係る装置構成図を示す。

0124

参照画素値和差分値決定部304は,動きベクトル,参照画素を入力とし,現在の動きベクトルと更新前の動きベクトルに対する参照画素値和の差分値を算出し,参照画素値和差分値記憶部305に書き出す。より具体的には,式(28),式(29),式(31),式(33)により算出する。また,同時に計算過程で算出する値ft-1 (x0 +16−vx ,y−vy )+ft-1 (x0 +17−vx ,y−vy )(式(28)の場合),ft-1 (x0 −vx ,y−vy )+ft-1 (x0 +1−vx ,y−vy )(式(29)の場合),ft-1 (x0 +16−vx ,y−vy )+ft-1 (x0 +16−vx ,y+1−vy ),ft-1 (x0 −vx ,y−vy )+ft-1 (x0 −vx ,y+1−vy )(式(31)の場合),Φ(x0 +16−vx ,y−vy ,t−1),Φ(x0 −vx ,y−vy ,t−1)(式(33)の場合)(y0 ≦y≦y0 +15)を部分参照画素値和記憶部316に書き出す。

0125

予測誤差下限値決定部306は,参照画素値和差分値記憶部305から読み出した参照画素値和の差分値,補正値差分値記憶部307から読み出した補正値の差分値,下限値記憶部308から読み出した更新前の動きベクトルに対する予測誤差の下限値を入力とし,動きベクトルの予測誤差の下限値を算出する処理を行い,算出した下限値を下限値記憶部308に書き出す。同下限値の具体的算出は式(25)に従う。

0126

補正値差分値算出部315は,部分参照画素値和記憶部316から読み出した部分参照画素値和を入力とし,小数画素位置毎の丸め誤差に対する補正値の差分値を算出し,補正値差分値記憶部307に書き出す処理を行う。同差分値は,より具体的には,式(30),式(32),式(34)により求める。

0127

初期動きベクトル予測誤差算出部301および参照画素値和差分値決定部304から動きベクトル制御部314は各々,図10で説明した初期動きベクトル予測誤差算出部101および参照画素値和決定部104から動きベクトル制御部114と同様な処理を行う。

0128

「第4の実施形態」の場合:
図13に本発明の第4の実施形態に係る装置構成図を示す。

0129

初期動きベクトル予測誤差算出部401から動きベクトル制御部414は各々,図12の初期動きベクトル予測誤差算出部301から動きベクトル制御部314と同じ処理を行う。

0130

補正値差分値算出部415は,ルックアップテーブル記憶部416から読み出した値を入力として,補正値の差分値を算出し,補正値差分値記憶部407に書き出す。補正値の具体的な算出は,式(36),式(38),式(40)に従う。

0131

ルックアップアップテーブル記憶部416には,補正値の差分値の算出時に参照する差分補正値ルックアップテーブルの値^rv (x0 ,y0 ,vx ,vy ),^rh (x0 ,y0 ,vx ,vy ),^rd (x0 ,y0 ,vx ,vy )を予め格納しておく。

0132

1/2画素精度MCの例について説明したが,1/m(m>2)画素精度MCに容易に拡張できることは,以上の説明から明らかである。

0133

以上の動きベクトルを推定し符号化する処理は,コンピュータソフトウェアプログラムとによっても実現することができ,そのプログラムコンピュータ読み取り可能な記録媒体に記録して提供することも,ネットワークを通して提供することも可能である。

図面の簡単な説明

0134

補間処理における参照画素を示す図である。
参照画素の差異部分に着目した下限値の算出を説明する図である。
参照画素の差異部分に着目した下限値の算出を説明する図である。
参照画素の差異部分に着目した下限値の算出を説明する図である。
本発明の実施例に係る符号化処理の流れを示す図である。
下限値算出処理の流れ(その1)を示す図である。
下限値算出処理の流れ(その2)を示す図である。
下限値算出処理の流れ(その3)を示す図である。
下限値算出処理の流れ(その4)を示す図である。
本発明の実施例に係る装置構成(その1)を示す図である。
本発明の実施例に係る装置構成(その2)を示す図である。
本発明の実施例に係る装置構成(その3)を示す図である。
本発明の実施例に係る装置構成(その4)を示す図である。

符号の説明

0135

101,201,301,401初期動きベクトル予測誤差算出部
102,202被予測画素値和決定部
103,203 被予測画素値和記憶部
104,204参照画素値和決定部
304,404 参照画素値和差分値決定部
105,205 参照画素値和記憶部
305,405 参照画素値和差分値記憶部
106,206,306,406予測誤差下限値決定部
107,207補正値記憶部
307,407補正値差分値記憶部
108,208,308,408 下限値記憶部
109,209,309,409枝刈り判定部
110,210,310,410 予測誤差算出部
111,211,311,411最適動きベクトル判定部
112,212,312,412暫定最小予測誤差記憶部
113,213,313,413 暫定最適動きベクトル記憶部
114,214,314,414動きベクトル制御部
115,215補正値算出部
315,415 補正値差分値算出部
116,316 部分参照画素値和記憶部
216,416ルックアップテーブル記憶部
SW1,SW2 スイッチ

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ