(57)【要約】      （修正有）【課題】サブ整数画素精度の動きベクトルを高速に探索する。【解決手段】ビデオ符号化における中間画素高精度高速探索アルゴリズムは、動き推定のための階層的な探索方法であって、最初に整数高精度動きベクトルを探索し、その後、整数動きベクトルの再構築されたサブ画素を取り囲んでいるそのサブ画素高精度探索を続ける方法を実行する。前記階層化は、前記アルゴリズムが最初に最小整数画素の位置を計算し、その後、サブ整数画素探索を実行することを含んでいる。最小MAD値を有する前記整数画素値を得て、その後、第１方向に共役中間画素値を補間する。前記アルゴリズムは、どの中間画素値が前記最小MAD値に従うかを決定し、その後、第１方向から既に計算された最小MAD中間画素の位置から第２方向に共役中間画素値を補間する。【選択図】図５
2010045816.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ映像データの第１フレームに含まれる第１マクロブロックと第２フレームに含まれる第２マクロブロックとの間の移動を示す動きベクトルをサブ整数画素精度で得るための方法であって、
前記第１フレームに対する前記第２フレーム内の最小絶対誤差手段（“ＭＡＤ”）値を有する整数画素の位置から、最も小さい第１方向ＭＡＤ値を有する第１最小ＭＡＤ位置までを第１方向における第１オフセットと認識する段階と、
最も小さい第２方向ＭＡＤ値を有する第２最小ＭＡＤ位置までを第２方向における第２オフセットを認識する段階と、
前記整数画素の位置とサブ整数画素の位置とを用いて前記動きベクトルを決定する段階とを含み、
前記サブ整数画素の位置は、前記第１オフセットと前記第２オフセット以外のオフセットを用いることなく、前記第１オフセットと前記第２オフセットとの結合によって得られることを特徴とする方法。
【請求項２】
前記第１オフセットを認識する段階は、更に、
前記整数画素の位置を中心にして前記第１方向の両側の第１及び第２半画素位置に互いに共役の関係にある半画素値を定めるよう内挿を行う段階と、
前記第１及び第２半画素位置の各々でＭＡＤ値を決定する段階と、
前記第１及び第２半画素位置と前記整数画素の位置での前記ＭＡＤ値を比較することにより前記第１最小ＭＡＤ位置を決定する段階と、
前記第１最小ＭＡＤ位置と前記整数画素の位置との間の差として前記第１オフセットを計算する段階と、を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記第２オフセットを認識する段階は、更に、
前記整数画素の位置を中心にして前記第２方向の両側の第１及び第２半画素位置に互いに共役の関係にある半画素値を定めるよう内挿を行う段階と、
前記第１及び第２半画素位置の各々でＭＡＤ値を決定する段階と、
前記第１及び第２半画素位置と前記整数画素の位置での前記ＭＡＤ値を比較することにより前記第２最小ＭＡＤ位置を決定する段階と、
前記第２最小ＭＡＤ位置と前記整数画素の位置との間の差として前記第２オフセットを計算する段階と、を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記第２オフセットを認識する段階は、更に、
前記第１最小ＭＡＤ位置を中心にして前記第２方向の両側の第１及び第２半画素位置に互いに共役の関係にある半画素値を定めるよう内挿を行う段階と、
前記第１及び第２半画素位置の各々でＭＡＤ値を決定する段階と、
前記第１及び第２半画素位置と前記第１最小ＭＡＤ位置での前記ＭＡＤ値を比較することにより前記第２最小ＭＡＤ位置を決定する段階と、
前記第１最小ＭＡＤ位置と前記第２最小ＭＡＤ位置との間の差として前記第２オフセットを計算する段階と、を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記動きベクトルを決定する段階は、更に、
前記整数画素の位置を用いて整数動きベクトルを生成する段階と、
前記サブ整数画素の位置を用いてサブ整数動きベクトルを生成する段階と、
前記整数動きベクトルに前記サブ整数動きベクトルを加えて前記動きベクトルを生成する段階と、を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記第２オフセットを認識する段階は、更に、
前記第１最小ＭＡＤ位置を中心にして前記第２方向の両側の第３及び第４半画素位置に互いに共役の関係にある半画素値を定めるよう内挿を行う段階と、
前記第３及び第４半画素位置の各々でＭＡＤ値を決定する段階と、
前記第３及び第４半画素位置と前記第１最小ＭＡＤ位置での前記ＭＡＤ値を比較することにより前記第２最小ＭＡＤ位置を決定する段階と、
前記第１最小ＭＡＤ位置と前記第２最小ＭＡＤ位置との間の差として前記第２オフセットを計算する段階と、を含むことを特徴とする請求項２に記載の方法。
【請求項７】
前記第１方向はｘ軸に平行な水平方向であり、前記第２方向はｙ軸に平行な垂直方向であって、前記ｘ軸とｙ軸とは二次元マトリックスの座標軸であることを特徴とする請求項１に記載の方法。
【請求項８】
前記第１方向は前記第２方向と直交していることを特徴とする請求項１に記載の方法。
【請求項９】
ビデオ映像データの第１フレームと第２フレームとの間の移動を示す動きベクトルをサブ整数画素精度で得るための装置であって、
コンピュータで実行される命令でコード化されたコンピュータで読出し可能な媒体と接続されたプロセッサを備え、
前記コンピュータで実行される命令は前記プロセッサによって実行されると、前記第１フレームに対する前記第２フレーム内の最小絶対誤差手段（“ＭＡＤ”）値を有する整数画素の位置から、
最も小さい第１方向ＭＡＤ値を有する第１最小ＭＡＤ位置までを第１方向における第１オフセットと認識し、
最も小さい第２方向ＭＡＤ値を有する第２最小ＭＡＤ位置までを第２方向における第２オフセットと認識し、
前記整数画素の位置とサブ整数画素の位置とを用いて前記動きベクトルを決定するよう動作し、
前記サブ整数画素の位置は、前記第１オフセットと前記第２オフセット以外のオフセットを用いることなく、前記第１オフセットと前記第２オフセットとの結合によって得られることを特徴とする装置。
【請求項１０】
前記コンピュータで実行される命令は前記プロセッサによって実行されると前記第１オフセットを認識する段階は、更に、
前記整数画素の位置を中心にして前記第１方向の両側の第１及び第２半画素位置に互いに共役の関係にある半画素値を定めるよう内挿を行う段階と、
前記第１及び第２半画素位置の各々でＭＡＤ値を決定する段階と、
前記第１及び第２半画素位置と前記整数画素の位置での前記ＭＡＤ値を比較することにより前記第１最小ＭＡＤ位置を決定する段階と、
前記第１最小ＭＡＤ位置と前記整数画素の位置との間の差として前記第１オフセットを計算する段階と、を含むことを特徴とする請求項９に記載の装置。
【請求項１１】
前記コンピュータで実行される命令は前記プロセッサによって実行されると前記第２オフセットを認識する段階は、更に、
前記第１最小ＭＡＤ位置を中心にして前記第２方向の両側の第１及び第２半画素位置に互いに共役の関係にある半画素値を定めるよう内挿を行う段階と、
前記第１及び第２半画素位置の各々でＭＡＤ値を決定する段階と、
前記第１及び第２半画素位置と前記第１最小ＭＡＤ位置での前記ＭＡＤ値を比較することにより前記第２最小ＭＡＤ位置を決定する段階と、
前記第１最小ＭＡＤ値と前記第２最小ＭＡＤ値との間の差として前記第２オフセットを計算する段階と、を含むことを特徴とする請求項１０に記載の装置。
【請求項１２】
ビデオ映像データの第１フレームに含まれる第１マクロブロックと第２フレームに含まれる第２マクロブロックとの間の移動を示す動きベクトルをサブ整数画素精度で得るためにコンピュータで実行される命令でコード化されたコンピュータで読出し可能な媒体であって、
前記コンピュータで実行可能な命令は、
前記第１フレームに対する前記第２フレーム内の最小絶対誤差手段（“ＭＡＤ”）値を有する整数画素の位置から、
最も小さい第１方向ＭＡＤ値を有する第１最小ＭＡＤ位置までを第１方向における第１オフセットと認識するよう構成されたコンポーネントと、
最も小さい第２方向ＭＡＤ値を有する第２最小ＭＡＤ位置までを第２方向における第２オフセットと認識するよう構成されたコンポーネントと、
前記整数画素の位置とサブ整数画素の位置とを用いて前記動きベクトルを決定するよう構成されたコンポーネントとを含み、
前記サブ整数画素の位置は、前記第１オフセットと前記第２オフセット以外のオフセットを用いることなく、前記第１オフセットと前記第２オフセットとの結合によって得られることを特徴とする媒体。
【請求項１３】
前記第１オフセットを認識するよう構成されたコンポーネントは、更に、
前記整数画素の位置を中心にして前記第１方向の両側の第１及び第２半画素位置に互いに共役の関係にある半画素値を定めるよう内挿を行うよう構成されたコンポーネントと、
前記第１及び第２半画素位置の各々でＭＡＤ値を決定するよう構成されたコンポーネントと、
前記第１及び第２半画素位置と前記整数画素の位置での前記ＭＡＤ値を比較することにより前記第１最小ＭＡＤ位置を決定するよう構成されたコンポーネントと、
前記第１最小ＭＡＤ位置と前記整数画素の位置との差として前記第１オフセットを計算するよう構成されたコンポーネントと、を含むことを特徴とする請求項１２に記載の媒体。
【請求項１４】
前記第２オフセットを認識するよう構成されたコンポーネントは、更に、
前記第１最小ＭＡＤ位置を中心にして前記第２方向の両側の第３及び第４半画素位置に互いに共役の関係にある半画素値を定めるよう内挿を行うよう構成されたコンポーネントと、
前記第３及び第４半画素位置の各々でＭＡＤ値を決定するよう構成されたコンポーネントと、
前記第３及び第４半画素位置と前記第１最小ＭＡＤ位置での前記ＭＡＤ値を比較することにより前記第２最小ＭＡＤ位置を決定するよう構成されたコンポーネントと、
前記第１最小ＭＡＤ位置と前記第２最小ＭＡＤ位置との間の差として前記第２オフセットを計算するよう構成されたコンポーネントと、を含むことを特徴とする請求項１３に記載の媒体。
【請求項１５】
ビデオ映像データの第１フレームに含まれる第１マクロブロックと第２フレームに含まれる第２マクロブロックとの間の移動を示す動きベクトルをサブ整数画素精度で得るためのデバイスであって、
前記第１フレームに対する前記第２フレーム内の最小絶対誤差手段（“ＭＡＤ”）値を有する整数画素の位置から、
最も小さい第１方向ＭＡＤ値を有する第１位置に第１オフセットを認識するよう構成されたコンポーネントと、
最も小さい第２方向ＭＡＤ値を有する第２位置に第２オフセットを認識するよう構成されたコンポーネントと、
前記整数画素の位置とサブ整数画素の位置とを用いて前記動きベクトルを決定するよう構成されたコンポーネントとを含み、
前記サブ整数画素の位置は前記第１オフセットと前記第２オフセット以外のオフセットを用いることなく、前記第１オフセットと前記第２オフセットとの結合によって得られることを特徴とするデバイス。
【請求項１６】
前記第１オフセットを認識するよう構成されたコンポーネントは、更に、
前記整数画素の位置を中心にして前記第１方向の両側の第１及び第２半画素位置に互いに共役の関係にある半画素値を定めるための内挿を行うよう構成されたコンポーネントと、
前記第１及び第２半画素位置の各々でＭＡＤ値を決定するよう構成されたコンポーネントと、
前記第１及び第２半画素位置と前記整数画素の位置での前記ＭＡＤ値を比較することにより前記第１最小ＭＡＤ位置を決定するよう構成されたコンポーネントと、を含むことを特徴とする請求項１５に記載のデバイス。
【請求項１７】
前記第２オフセットを認識するよう構成されたコンポーネントは、更に、
前記第１最小ＭＡＤ位置を中心にして前記第２方向の両側の第３及び第４半画素位置に互いに共役の関係にある半画素値を定めるための内挿を行うよう構成されたコンポーネントと、
前記第３及び第４半画素位置の各々でＭＡＤ値を決定するよう構成されたコンポーネントと、
前記第３及び第４半画素位置と前記第１最小ＭＡＤ位置でのＭＡＤ値を比較することにより前記第２最小ＭＡＤ位置を決定するよう構成されたコンポーネントと、を含むことを特徴とする請求項１６に記載のデバイス。
【請求項１８】
ビデオ映像データの連続するフレーム間の移動を示す動きベクトルを半画素精度で得るための高速サーチ方法であって、
２次元アレイ状に配列された複数の画素からなる第１フレームの第１マクロブロックを決定する段階と、
２次元アレイ状に配列された複数の画素からなる第２フレームの第２マクロブロックであって、前記第１マクロブロックと前記第２マクロブロックとの間で最小絶対誤差手段（“ＭＡＤ”）値を有する第２マクロブロックを選択する段階と、
前記第２マクロブロック中で最も小さいＭＡＤ値を有する整数画素の位置を認識する段階と、
前記整数画素の位置を中心にして第１方向の両側の第１及び第２半画素位置に互いに共役の関係にある半画素値を計算する段階と、
前記第１及び第２半画素位置の各々でＭＡＤ値を決定する段階と、
前記第１及び第２半画素位置と前記整数画素の位置での前記ＭＡＤ値を比較することにより最も小さい第１方向ＭＡＤ値を有する第１最小ＭＡＤ位置を決定する段階と、
前記第１最小ＭＡＤ位置を中心にして第２方向の両側の第３及び第４半画素位置に互いに共役の関係にある半画素値を計算する段階と、
前記第３及び第４半画素位置の各々でＭＡＤ値を決定する段階と、
前記第３及び第４半画素位置と前記第１最小ＭＡＤ位置での前記ＭＡＤ値を比較することにより最も小さい第２方向ＭＡＤ値を有する第２最小ＭＡＤ位置を決定する段階と、
前記整数画素の位置とサブ整数画素の位置とを用いて前記動きベクトルを決定する段階と、を含み、
前記サブ整数画素の位置は前記第２最小ＭＡＤ位置であることを特徴とする高速サーチ方法。
【請求項１９】
前記動きベクトルを決定する段階は、更に、
前記複数画素の位置を用いて整数動きベクトルを生成する段階と、
前記サブ整数画素の位置を用いてサブ整数動きベクトルを生成する段階と、
前記整数動きベクトルに前記サブ整数動きベクトルを加えて前記動きベクトルを生成する段階と、を含むことを特徴とする請求項１８に記載の高速サーチ方法。
【請求項２０】
前記第１方向は前記２次元アレイのｘ軸に平行な水平方向であり、前記第２方向は前記２次元アレイのｙ軸に平行な垂直方向であることを特徴とする請求項１８に記載の高速サーチ方法。
【請求項２１】
前記半画素値を計算する段階は、更に、両線形内挿を行う段階を含むことを特徴とする請求項１８に記載の高速サーチ方法。
【請求項２２】
前記動きベクトルを決定する段階は、更に、
前記整数画素の位置での整数動きベクトルを決定する段階と、
前記サブ整数画素の位置でのサブ整数動きベクトルを決定する段階と、
前記整数動きベクトルに前記サブ整数動きベクトルを加える段階と、を含むことを特徴とする請求項１８に記載の高速サーチ方法。
【請求項２３】
前記第２最小ＭＡＤ位置を決定する段階は、更に、
前記ＭＡＤ値と前記整数画素値とを比較することにより前記最も小さいＭＡＤ値を決定する段階を含むことを特徴とする請求項１８に記載の高速サーチ方法。
【請求項２４】
ビデオ映像データの第１フレームに含まれる第１マクロブロックと第２フレームに含まれる第２マクロブロックとの間の移動を示す動きベクトルをサブ整数画素精度で得るための方法であって、
前記第１フレームに対する前記第２フレーム内の最小絶対誤差手段（“ＭＡＤ”）値を有する整数画素の位置から、
最も小さい第１方向ＭＡＤ値を有する第１最小ＭＡＤ位置までを第１方向における第１オフセットと決定する段階と、
前記第１最小ＭＡＤ位置から最も小さい第２方向ＭＡＤ値を有する第２最小ＭＡＤ位置までを第２方向における第２オフセットと決定する段階と、
前記整数画素の位置と前記第２最小ＭＡＤ位置とを用いて前記動きベクトルを決定する段階と、を含むことを特徴とする方法。
【請求項２５】
ビデオ映像データの第１フレームに含まれる第１マクロブロックと第２フレームに含まれる第２マクロブロックとの間の移動を示す動きベクトルをサブ整数画素精度で得るための方法であって、
前記第１フレームに対する前記第２フレーム内の最小絶対誤差手段（“ＭＡＤ”）値を有する整数画素の位置から、
最も小さい第１方向ＭＡＤ値を有する第１最小ＭＡＤ位置までを第１直交方向における第１オフセットと決定する段階と、
前記第１最小ＭＡＤ位置を中心として最も小さい第２方向ＭＡＤ値を有する第２最小ＭＡＤ位置までを第２直交方向における第２オフセットと決定する段階と、
前記整数画素の位置と前記第２最小ＭＡＤ位置とを用いて前記動きベクトルを決定する段階と、を含むことを特徴とする方法。
【請求項２６】
ビデオレコーダのビデオ映像データの第１フレームに含まれる第１マクロブロックと第２フレームに含まれる第２マクロブロックとの間の移動を示す動きベクトルをサブ整数画素精度で得るための方法であって、
前記第１フレームに対する前記第２フレーム内の最小絶対誤差手段（“ＭＡＤ”）値を有する整数画素の位置から、
最も小さい第１方向ＭＡＤ値を有する第１最小ＭＡＤ位置までを第１方向における第１オフセットと決定する段階と、
前記第１最小ＭＡＤ位置を中心として最も小さい第２方向ＭＡＤ値を有する第２最小ＭＡＤ位置までを第２方向における第２オフセットと決定する段階と、
前記整数画素の位置と前記第２最小ＭＡＤ位置とを用いて前記動きベクトルを決定する段階と、
前記動きベクトルを貯蔵デバイスに格納する段階と、を含むことを特徴とする方法。
【請求項２７】
前記整数画素の位置を、前記ｘ軸及び前記ｙ軸について画素オフセットのない、画素位置を示す座標点（０．０，０．０）に定める段階と、
前記第１半画素位置を、前記ｘ軸について負方向に半画素オフセットし、前記ｙ軸について画素オフセットのない画素位置を示す座標点（−０．５，０．０）に定める段階と、
前記第２半画素位置を、前記ｘ軸について正方向に半画素オフセットし、前記ｙ軸について画素オフセットのない画素位置を示す座標点（０．５，０．０）に定める段階と、
前記第３半画素位置を、前記ｘ軸について画素オフセットがなく、前記ｙ軸について負方向に半画素オフセットしている画素位置を示す座標点（０．０，−０．５）に定める段階と、
前記第４半画素位置を、前記ｘ軸について画素オフセットがなく、前記ｙ軸について正方向に半画素オフセットしている画素位置を示す座標点（０．０，０．５）に定める段階と、を更に含むことを特徴とする請求項２０に記載の高速サーチ方法。
【請求項２８】
前記整数画素の位置を、前記ｘ軸及び前記ｙ軸について画素オフセットのない画素位置を示す座標点（０．０，０．０）に定める段階と、
前記第１半画素位置を、前記ｘ軸について負方向に半画素オフセットし、前記ｙ軸について負方向に半画素オフセットしている画素位置を示す座標点（−０．５，−０．５）に定める段階と、
前記第２半画素位置を、前記ｘ軸について正方向に半画素オフセットし、前記ｙ軸について正方向に半画素オフセットしている画素位置を示す座標点（０．５，０．５）に定める段階と、
前記第３半画素位置を、前記ｘ軸について負方向に半画素オフセットし、前記ｙ軸について正方向に半画素オフセットしている画素位置を示す座標点（−０．５，０．５）に定める段階と、
前記第４半画素位置を、前記ｘ軸について正方向に半画素オフセットし、前記ｙ軸について負方向に半画素オフセットしている画素位置を示す座標点（０．５，−０．５）に定める段階と、を更に含むことを特徴とする請求項２０に記載の高速サーチ方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ圧縮のための動き推定アルゴリズムに関し、より詳細には、ビデオ符号化において中間画素精度高速探索アルゴリズムを実現するための装置及び方法に関する。
【背景技術】
【０００２】
デジタル技術の発達は、多くのデジタルビデオアプリケーションを作り出している。デジタルビデオは、現在、デジタル高精細テレビ（HDTV）、ビデオ会議、コンピュータ画像、及び高品質ビデオテープレコーダーで用いられている。非圧縮のデジタルビデオ信号は、莫大な量のデータから構成されているため、多量の帯域を必要とし、記憶し伝送するためのメモリを必要とする。例えば、米国で放送しているHDTVを定義するフォーマットの１つは、水平方向に1920画素、垂直方向に1080ライン、１秒間に30フレームである。これらの数が、三原色のそれぞれに対して8ビットで全てが一緒に多重されるならば、必要とされる全データ速度は、概して1.5Gb/secである。FCCによって課された6MHzのチャンネル帯域制限のために、各チャンネルは、19.2Mb/secのデータ速度をサポートするのみである。前記チャンネルは、オーディオ、トランスポート、補助データ情報もサポートしなければならないため、それはさらに18Mb/secへ引き下げられる。伝送データ速度の制限を与えられて、オリジナル信号は、おおよそ83:1の割合で圧縮されなければならない。それゆえ、多くのデジタルビデオシステムは、特定のアプリケーションのために最適化されるデータ圧縮技術を使用することによってデジタルビデオデータの量を減らしている。デジタル圧縮装置は、共通して“エンコーダ”と呼ばれ、一方、復元を実行する装置は、“デコーダ”と呼ばれている。符号化と複合化の両方は、しばしば、“コーデック”と呼ばれている。
【０００３】
動画ビデオ圧縮のための方法を標準化するために、ムービングピクチャーエキスパートグループ（MPEG）は、デジタルビデオ処理のための多くの標準を発行した。
【０００４】
各フレームは、画像の要素または“画素”の２次元配列として述べられている。各画素は、輝度と色相によって画像の特定のポイントを表す。方法は、各フレームを表現するのに必要とされる伝送データの量を減らすように工夫されている。伝送データの削減は、データ圧縮と呼ばれている。圧縮方法は、各画素の位置の色と明るさのための大量の情報を伝送する以前に、所定の多くの“マクロブロック”に各フレームを分割する。前記マクロブロックは、典型的には、１６×１６の画素配列として定義される。連続するフレーム間に類似するものがある時、前記フレーム間で異なるもののみを伝送することはより効果的である。最新のマクロブロックは、連続するフレームまたは以前のフレームに発見されるならば、最新のマクロブロックをどこへ動かすかを詳述する動きベクトルを伝送することはより効果的である。前記動きベクトルは、前記最新のマクロブロックにおける各画素の位置を連続する参照フレームの各画素の位置と比較することによって決定される。前記２つのマクロブロック間で違いが最小である整数の位置は、前記動きベクトルを発生させるのに用いられる。全画素の位置を探索する処理は、全探索または逐次探索とよばれ、全画素の位置よりも少ない探索処理は、高速探索と呼ばれる。
【０００５】
前記最新のマクロブロックは、現実のビデオ符号化においては与えられた方向に多くの整数画素を通常シフトしない。現実には、前記マクロブロックは、わずか一部の画素によって置き換えられる。全探索または高速探索の整数画素探索アルゴリズムによって所定の前記整数画素の位置を得る方法、及び動きベクトルをより正確に定義するための中間画素の位置を取り囲んでいる8画素全てを使って第２の探索を実行する方法が幾つか存在する。これは、より正確な動きベクトルをもたらす一方、最新の中間画素の位置を配置するために必要な計算の数が増加する。高速探索を実行する1/2画素探索アルゴリズム、すなわち、1/2画素の8つ全ての位置が探索されるアルゴリズムは存在しない。
【０００６】
非特許文献１の論文は、マクロブロックのどの整数位置が最小絶対誤差手段（MAD）を含んでいるかを第1に決定することによって、高速2段階中間画素高精度動きベクトル予測アルゴリズム（fast two-step half pixel accuracy motion vector prediction algorithm）を実現している。前記MAD関数は、式（１）で示される。
【０００７】
【数１】
2010045816.tif 000003
【０００８】
ここで、f(i,j)は、前記最新のフレームからの１６×１６画素（マクロブロック）のブロックを表しており、g(i,j)は、同じマクロブロックではなく、（時間的に前または次の）参照フレームからのマクロブロックを表しており、前記参照マクロブロックは、探索位置を表しているベクトル(dx,dy)によって置き換えられる。前記MAD関数は、連続するフレームにおけるどの整数画素の位置が最小誤差を含んでいるかを計算する。この画素値は、動きベクトルのための前記整数画素の変位値になる。
【０００９】
前記最小MAD値を作り出している最良の適合ブロックを見つけるために、探索範囲における幾つかの位置で前記MAD値を計算する必要がある。上述したように、全探索または逐次探索は、高速または部分探索が事前定義されている値を選択する一方、全ての位置で前記MADを計算する。
【００１０】
図１を参照すると、非特許文献１の論文は、所定の整数画素の位置を取り囲んでいる1/2画素ポイントをテストする方法について述べている。第1に、前記取り囲んでいる中間画素の整数位置は、水平及び垂直ペアに対して切り離されている。水平の中間画素ポイント2と7及び垂直の中間画素ポイント4と5は、取り囲んでいる整数画素に基づいて補間されており、位置2の前記MADは最小MADペアを決定するために位置7と比較され、位置4の前記MADは位置5と比較される。補間される画素は、共一次内挿法技術を承認したMPEGを使って決定される。前記最小MAD値を有するブロックは、その時、最小ペアを決定する反対のペアのブロックと比較される。例えば、ポイント2が前記最小MADを有し、5が4よりも小さいMADを有するとすると、前記最小MADペアは2と5であり、ポイント4は中間画素の動き予測のために付加的に考慮される。結局、前記中間画素の高精度動きベクトルは、中心の整数画素ブロック、前記最小候補ブロック、及びより最新と思われるポイントの前記MADを比較することによって決定される。
【００１１】
非特許文献１は、高速2段階中間画素動きベクトル予測アルゴリズムについて述べており、前記アルゴリズムは、5つの計算を実行し、従来の全中間画素探索方法と比較して37.5%計算処理上の負担を減らすのみである。従って、中間画素高精度動きベクトルを決定する計算処理上の負担を低減させる高速中間画素動き推定アルゴリズムの必要性はそのまま残る。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】米国特許第６１２８０４７号
【非特許文献】
【００１３】
【非特許文献１】“Ｆａｓｔ  Ｔｗｏ−Ｓｔｅｐ  Ｈａｌｆ−Ｐｉｘｅｌ  Ａｃｃｕｒａｃｙ  Ｍｏｔｉｏｎ  Ｖｅｃｔｏｒ  Ｐｒｅｄｉｃｔｉｏｎ”，  Ｋ．Ｈ．Ｌｅｅ，  Ｊ．Ｈ．Ｃｈｏｉ，  Ｂ．Ｋ．Ｌｅｅ  ａｎｄ  Ｄ．Ｇ．Ｋｉｍ，  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｌｅｔｔｅｒｓ，  ３０ｔｈ  Ｍａｒ．，２０００  Ｖｏｌ．３６，ｎｏ．７
【発明の概要】
【課題を解決するための手段】
【００１４】
それゆえ、本発明は、従来の方法と比較すると正確な中間画素を有する動きベクトルを決定する計算処理上の負担を低減させるビデオ符号化における中間画素高精度高速探索アルゴリズムを提供する。
さらに、本発明は、具現化し実現することが容易であるビデオ符号化における中間画素高精度高速探索アルゴリズムを提供する。
【００１５】
上記及び他の本発明を実行するために、まず初めに整数高精度動きベクトルを探索し、その後、取り囲んでいるサブ画素精度を有するその探索を続け、前記整数動きベクトルの共役サブ画素が再構築される、動き推定のための階層化探索法を実行するビデオ符号化における中間画素高精度高速探索アルゴリズムを提供する。
【００１６】
本発明の他の側面と特徴は、本発明の実施例を開示する添付図と結びつけて考察されている以下の詳細な説明からより明らかになる。しかしながら、図は説明のためだけに示されており、本発明の制限を定義するものではないということを理解すべきである。図において、類似の参照文字は、幾つかの表示にわたり類似する要素を示している。
【００１７】
動画ビデオ系列は、連続する動きの錯覚を提供するように連続的に表示されている一連の静止画または“フレーム”からなる。各フレームは、2次元配列の画像の要素または“画素”として描写される。各画素は、輝度と色相によってその画像における特定のポイントを描写する。画素情報は、デジタルの形態で表現され、高精細テレビのようなモニター上に表示され、または符号化され、放送され得る。
【００１８】
放送信号には２つの構成成分がある。１）予想できない成分（すなわち新しく予測ができない）と、２）予想できる成分である。前記新しい成分は、エントロピーと呼ばれ、それは、信号上の真の情報である。残りのものは、本質的でなく、他のフレームから作り直されるのでリダンダンシーと呼ばれる。リダンダンシーは、隣接画素がほとんど同じ値を有する画像の大きな単一領域に存在するような空間的なものである。リダンダンシーは、連続する画像間の類似性が利用されるように時系列的でもある。圧縮システムは、前記エンコーダにおいて前記リダンダンシーから前記エントロピーを切り離すことによって働く。前記エントロピーは、冗長なデータを描写する動きベクトルに沿って記録されるか、または伝送される。前記デコーダは、表示する完全なフレームを発生させるために前記エントロピーと冗長データを利用する。
【００１９】
理想的エンコーダは、連続するフレームの前記エントロピーを伝送し、画質の損失なく前または次のフレームの冗長な画素の情報を使って付加的に冗長な情報を作り直す。典型的には、圧縮率が高くなるにつれて、前記信号伝送は、デジタル人工品または誤差になりがちであり、信号の質を下げることになる。理想的エンコーダは、今のところ存在せず、あるのは圧縮率と信号の質の間の平衡を保つものである。
【００２０】
ビデオ圧縮のために、前記エンコーダは“イントラコーディング”と“インターコーディング”技術を利用している。イントラコーディングは、空間的な冗長を活用する技術、すなわちインターコーディングが時系列的な冗長または連続する画像間の冗長を活用する技術であるのに対して画像内の冗長を活用する技術である。与えられた画像が前記デコーダで利用できるならば、その次の画像は前記画像の相違点のみを送信することによって作り直される。前記画像の相違点は、物体が動いた時、増加されるが、動いている物体は一般的には、ある画像から次の画像へその外観がそれほど変わらないので、相違点は動き補償を使うことによって相殺される。その動きが計測されるならば、最新の画像に対するより徹底的な近似が、新しい位置に対して前の画像の一部をシフトすることによって作られる。前記シフト処理は、前記デコーダに対して伝送される動きベクトルによって制御される。前記動きベクトルの伝送は、前記画像の相違点データまたは完全なフレームを送信するよりも少ないデータである必要がある。
【００２１】
動き推定法の２つのタイプは、典型的には、前記動きベクトルを推定するために用いられている。すなわち、画素再帰アルゴリズムとブロックマッチングアルゴリズムである。画素再帰技術は、隣接するフレームにおける対応する画素から各画素の変位を予測する。一方、ブロックマッチングアルゴリズムは、ブロック毎を基本としてフレーム間の変位を見積もり、距離が最小である変位ベクトルを選択する。全マクロブロックは、その時、前記動きベクトルによって置き換えられる。典型的には、符号化される最新の画素は、画素情報が同等の大きさのブロックに分けられる。これらの“マクロブロック”は、典型的には、２つの色成分のそれぞれに対して８×８のブロックのサンプルと共に輝度サンプルの１６×１６のサンプル配列からなる。
【００２２】
ブロックマッチング動き推定アルゴリズムは、一般的には、その探索方式に基づいた全探索かまたは高速探索アルゴリズムとして分類される。全探索は、徹底的な探索としても知られ、前記マクロブロックの前記動きベクトルを発見するために全ての予想候補整数画素の位置において連続するマクロブロック間の誤差を見積もる。それは、実現するための複雑性としては単純である一方、各マクロブロックと連続するマクロブロックの位置の前記エリアを探索するのに広がる計算上の負担を携える。それゆえ、連続するマクロブロック間の最小誤差を探索するための整数画素の位置の量を低減する多くの高速探索アルゴリズムが提案されている。整数画素の動きベクトルの精度を改善するために、本発明は、中間画素精度を有する階層的なアプローチを提案する。
【００２３】
前記階層化は、前記アルゴリズムが最初に最小整数画素の位置を計算し、それからサブ整数画素探索を実行することを意味する。本発明は、最低MAD値を有する前記整数画素を得て、それから、第１の方向に共役中間画素値を補間する。前記アルゴリズムは、どの中間画素値が最小MAD値に従うかを決定し、それから、前記第１の方向から前に計算された最小MADの中間画素の位置で第２の方向における共役中間画素値を補間する。説明した共役探索方法は、８つから４つの中間画素の位置まで従来の中間画素探索方法によって実行される計算を低減する。
【００２４】
補間を用いる２次元再構成画像は、以下のような数式で示される。２次元コンボリューションは、標本化された画素の画像と補間関数の間で処理される。
【００２５】
【数２】
2010045816.tif 000004
ここで、B(.)は、再構成された補間画像であり、
【００２６】
【数３】
2010045816.tif 000005
２次元線形補間関数は、以下によって与えられる。
【００２７】
【数４】
2010045816.tif 000006
ここで、XとYは、画像フレームにおける水平、垂直の間隔である。
【図面の簡単な説明】
【００２８】
【図１】従来技術に従う整数画素と中間画素の位置を図示したものである。
【図２】補間のための整数と中間の画素の位置を図示したものである。
【図３】整数画素の位置のまわりに取り囲んでいる中間画素の位置を図示したものである。
【図４】本発明に従う中間画素高精度高速探索アルゴリズムの概念を図示したものである。
【図５】本発明に従うビデオ符号化における中間画素高精度高速探索アルゴリズムを説明するフローチャートである。
【図６】本発明と一致したシステム図である。
【図７】テストビデオストリーム入力と本発明のピーク信号雑音比（PSNR）の性能を図示したものである。
【図８】テストビデオストリーム入力と本発明のピーク信号雑音比（PSNR）の性能を図示したものである。
【図９】テストビデオストリーム入力と本発明のピーク信号雑音比（PSNR）の性能を図示したものである。
【図１０】テストビデオストリーム入力と本発明のピーク信号雑音比（PSNR）の性能を図示したものである。
【発明を実施するための形態】
【００２９】
ここで、図を詳細に見ることにする。図２は、共一次内挿法を利用するための整数と中間整数の位置を描写している図である。共一次内挿法は、中間画素値が決定される処理であり、中間画素値を計算するための標準としてMPEGによって採用されている。画像の整数画素の位置に関する上記共一次内挿法の式を使って、中間画素値a、b、c、d、eは、以下のように計算される。
a=(A+B)/2
b=(A+C)/2
c=(A＋B＋C＋D)/4
d=(B+D)/2
e=(C+D)/2
ここで、A、B、C、Dは整数画素であり、a、b、c、d、eは取り囲んでいる中間画素である。前記中間画素値は、中間画素高精度動きベクトルを決定する時に本発明によって利用される。
【００３０】
図３は、整数画素の位置のまわりに取り囲んでいる中間画素の位置を図示している。本発明に従うと、整数画素0を取り囲む中間画素の位置1から8は、例えば、上述の公式を使って計算される。
【００３１】
図４は、多数の中間画素の位置1から8それぞれによって取り囲まれている整数の位置0を図示している。加えて、本発明に従うビデオ符号化における前記中間画素高精度高速探索アルゴリズムに対する予想探索位置の一例は、ＩLeft、ＩCenter、ＩRight及びＩＩCenter、ＩＩLeftとＩＩRightに関して描写されている。
【００３２】
本発明に従う前記高速中間画素探索は、第１に、既知の整数画素の全探索または高速探索のアルゴリズムを使って最小MAD値を有するマクロブロックにおける整数画素の位置を計算する。一度、整数画素の位置が計算されると、第１の方向ＩLeftとＩRightにおける前記共役中間画素値が決定される。例えば、第１の方向が水平であり、２次元正方格子のX軸に平行であると仮定する。ＩLeftとＩRightの前記MADは計算され、最小MAD値を有する前記中間画素の位置が記憶される。第２の方向における共役中間画素値はまた、最小MAD値を有する既に記憶された画素の位置を起点として計算される。上記に基づき、第２の方向は垂直方向であり、正方格子のY軸に平行であると仮定する。この場合には、必要とされないが、第１と第２の方向はお互いに直交している。共一次内挿法を使って、IITopとIIBottomは決定される。ＩRight、ＩCenter、またはＩLeftは、第１と第２の方向がお互いに直交している時、IICenterに対して等しい値であるということに注目する。一度、IITopとIIBottomが計算されると、それら２つの位置に対するMAD値は決定される。最小MAD値を有する前記中間画素の位置はまた、記憶され、事前に決定される前記整数画素値のためのオフセットとして用いられる。従って、最小MAD値を有する前記中間画素の位置をもうけて整数画素の位置ＩCenterを結合する新しい動きベクトルは、前記マクロブロックを置き換える最終の動きベクトルを発生させるために用いられる。式（２）を使って、前記動きベクトルMV(x,y)は、以下のように定義される。
【００３３】
（２） MV(x,y)=MVinteger(x,y)+dh(x,y)
ここで、MVinteger(x,y)は、整数高精度動きベクトルであり、dh(x,y)は、中間画素変位である。
【００３４】
択一的なアプローチとして、その方法はまた、最小MAD値を有する位置を決定するために前記共役サブ画素の位置と前記整数の位置を比較する。
優位性としては、本発明に従い動作する中間画素の動き推定アルゴリズムは、整数画素の動きベクトルより正確な動き変位情報に従い、8つから4つまで全探索で必要とされる計算を低減し、それによって、50%計算を減らしている。
【００３５】
図４を参照している例において、最小MAD値を有する前記整数画素の位置がＩCenterに位置しているということを仮定する。本発明は、中間画素の位置ＩLeftとＩRightを補間し、それら２つのポイントのどちらが最小MAD値に従うかを決定する。ＩRightが、最小MAD値に従うと仮定すると、中間画素値IITopとIIBottomは第２の方向に計算される。IITopが最小MAD値を含んでいると仮定すると、このマクロブロックに対する動きベクトルは結果として、前記中間画素IITop動きベクトルを加えた前記整数の動きベクトルに等しい。上記の例において使用される探査命令は、説明目的のためだけのものであるということが理解されるべきである。他の適切な探索命令が選択肢として使われ、例えば、前記探索は、垂直方向に実行され、続いて水平方向に実行され、特に命令は、設計選択の事項である。他の例では、第１の方向は、右上から左下の斜方向であり得るし、第２の方向は、右下から左上であり得る。前記共役値は、斜方向に関して決定される。
【００３６】
図５は、本発明に従うビデオ符号化の例における中間画素の高精度高速探索を説明しているフローチャートである。第１に、既知である整数探索アルゴリズムを使って初期整数探索を実行し、動きベクトルMV整数(x,y)を決定する（ステップ500）。続いて、第１の方向にサブ画素の共役補間を実行する（ステップ505）。その後、第１の方向D(x+1,y)とD(x-1,y)において、それぞれの前記共役サブ画素の位置に対してMAD値を計算する。ここで、第２の方向の変数yは一定である（ステップ510）。次に、第１の方向における最小MAD値を決定する（ステップ515）。続いて、第１の方向における最小MAD値を有する前記サブ画素の位置に中心がある第２の方向においてサブ画素の共役補間を実行する（ステップ520）。次に、第２の方向D(x,y+1)とD(x,y-1)において前記共役サブ画素の位置に対するMAD値を計算する。ここで、前記変数xは一定である（ステップ525）。次に、第２の方向において最小MAD値を決定する（ステップ530）。最小MADを有する前記サブ画素の位置に基づく新しい動きベクトルを計算する（ステップ535）。その後、サブ画素に対する動きベクトルを加えた整数画素に対する動きベクトルの合計に等しいマクロブロックに対する動きベクトルを設定する（ステップ540）。
【００３７】
図６は、本発明と一致するシステム600の図である。システム600は、中央処理装置（“ＣＰＵ”）605、ランダムアクセスメモリ（“ＲＡＭ”）610、リードオンリーメモリ（“ＲＯＭ”）620、及びシステムバス670を経由して相互接続されるコンピュータ読み出し可能な媒体625を含んでいる。コンピュータ読み出し可能な媒体625は、本発明に従う前記中間画素の高精度高速探索を実行するのに必要なコンピュータ読み出し可能な命令を含んでおり、実行のためのCPU605に対して本発明に従う命令を提供する任意の媒体として限定されることなく組み入れられる。コンピュータ読み出し可能な媒体は、RAM、ROM、電気的消去可能なプログラマブルＲＯＭ（“ＥＥＰＲＯＭ”）、CD-ROM、またはネットワーク接続、電波、他のワイヤレス情報伝送手段のような伝送装置である。
【００３８】
入出力（I/O）信号660は、システム600に対して接続されており、圧縮または復元する音声/映像データの入力ストリームを提供している。CPU605は、上述したような正確な中間画素の高精度動きベクトルを決定するために媒体625に含まれる命令に沿ってI/O信号660にアクセスする。加えて、CPU605は、入力装置650から画像データを受信するか、またはディスプレー630上にI/O信号660を表示する。一度、前記画像データは、入力装置650またはI/O信号660を経由して受信され、そしてCPU605を経由して処理され、前記画像データは、記憶装置675に記憶されるか、または送信機およびアンテナ680を経由して伝送される。
【００３９】
媒体625と同様にシステム600は、モーションビデオレコーダー、デジタルビデオディスクレコーダー（“ＤＶＤ”）、衛星テレビ送受信機、パーソナルコンピュータ用のビデオディスプレーカード、及び他のMPEG準拠装置に制限されることなく多くの装置に組み込まれ、デジタルビデオ情報を伝送するのに必要とされる情報量を削減し、正確な動きベクトルを得るのに必要とされる計算量を削減する。
【００４０】
本発明の性能について、“クレア（Ｃｌａｉｒ）”、“自動車電話”、“ミスアメリカ”、“セールスマン”のような４つのテストビデオ系列を使ってノイズに対するピーク信号の割合（PSNR）に関して描写し、従来の中間画素探索と整数画素探索法の両方に対して比較する。表１はコンピュータシミュレーションデータを示し、PSNRに関して他の探索アルゴリズムとの比較を示す一方、式（３）は、前記PSNRの計算を詳述する。前記シミュレーションは、H.263フレームワークで実行し、PSNRデータは、100を超える画像のフレームデータを平均することによって得た。PSNRは以下のように計算した。
【００４１】
【数５】
2010045816.tif 000007
【００４２】
ここで、Nは、画素数であり、OiとRiは、オリジナル画像と再構成された画像の大きさである。両方の中間画素探索方法は、整数画素探索方法と比較すると、平均PSNRにおいて2dBに及ぶ差を有するより良い性能を示す。両方の中間画素探索方法、つまり高速探索及び全探索の方法の比較においては、PSNRに関して４つのビデオ系列の全てでほとんど差がない。一方、本発明で描写されている必要とされる計算の数は、全探索方法の半分に削減された。
【００４３】
表２は、計算の数に関して整数画素全探索、整数高速探索、及び中間画素全探索と比較した本発明のコンピュータシミュレーションデータを示す。本発明の処理スピードの改善は、特に、整数画素高速探索アルゴリズムを伴う時のシミュレーションデータにおいて明確に示される。中間画素全探索のポイントは、整数画素全探索の間に探索されるポイントのおおよそ1％である。従来の中間画素の全探索の間に実行される計算数は、整数画素の高速探索の計算数よりもかなり大きい。それゆえ、処理スピード改善の点から、中間画素探索における計算数を削減することには限界がある。表１は、本発明が必要とされる数を削減することによって処理スピードを改善したことを示す。前記シミュレーションデータは、必要な計算の全体の数において約30％削減を示し、従来の中間画素の全探索に比べて50％削減を示している。
【００４４】
【表１】
2010045816.tif 000008
【００４５】
【表２】
2010045816.tif 000009
【００４６】
図７−１０は、４つのテストビデオ系列を有する100個のフレームから各画像フレームのPSNRデータを示す。全中間画素探索、本発明に従う高速中間画素探索、及び整数画素探索が、各グラフにおいて比較されている。前記中間画素探索と本発明に従う高速中間画素探索は、PSNRに関して類似の性能を示してお互いにほとんど重なり合っている。しかしながら、前記整数画素探索は、2dBに及ぶPSNRの差を有して他の２つの高速探索データより低いままである。それゆえ、本発明は、全中間画素探索と比較すると取るに足らない量のノイズだけ含む一方で、中間画素の高精度動きベクトルを発生させるのに必要とされる計算数を50％削減する。
【００４７】
本発明の実施例を示した一方、添付された請求項で定義される本発明の範囲から出発することなく、多くの変化と変更がなされることが理解されることになる。
【図１】
2010045816.tif 000010
【図２】
2010045816.tif 000011
【図３】
2010045816.tif 000012
【図４】
2010045816.tif 000013
【図５】
2010045816.tif 000014
【図６】
2010045816.tif 000015
【図７】
2010045816.tif 000016
【図８】
2010045816.tif 000017
【図９】
2010045816.tif 000018
【図１０】
2010045816.tif 000019