(57)【要約】【課題】メモリ量が制限された計算環境でも、SEA探索法に基づく動きベクトル探索を効果的に実行すること。【解決手段】本発明は、画像フレームIBに定めた探索範囲中のブロックbBに対応する積算データGBの要素GBzを上位からkビット分ずつ順次取得し、取得の度に、これまで取得したGBzと、画像フレームIA中のブロックbAに対応する積算データGAの要素GAzと、を用いて、ブロックbBのSAD値が最小になる可能性があるか評価することを繰り返し行い、その繰り返しの過程において、ブロックbBのSAD値が最小になる可能性がないと評価できた場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、積算データGBの要素GBzの既取得ビット数が積算データGBの表現ビット数wよりも大きくなる場合には、繰り返しを終了して、ブロックbAと当該ブロックbBとの間でSAD計算を行う。【選択図】図７
2015111753.tif 000002
【特許請求の範囲】
【請求項１】
画像フレームIA中のブロックbAと、画像フレームIBに定めた探索範囲中のブロックbBとの間で、SAD値を計算することで類似度を評価し、当該探索範囲中でSAD値が最小となるブロックbBmaxを見つけることにより、画像フレームIAの各ブロックについて動きベクトルを計算する動きベクトル探索方法であって、
ブロックbBmaxの探索中に、SAD値が最小になる可能性がないブロックbBをSAD計算の対象から除外する、SEA探索法に基づく動きベクトル探索方法において、
画像フレームIA中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGAを用意し、
画像フレームIB中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGBを用意し、
ブロックbBに対応する積算データGBの要素GBzを上位からkビット分ずつ順次取得し、取得の度に、これまで取得したGBzと、ブロックbAに対応する積算データGAの要素GAzと、を用いて、ブロックbBのSAD値が最小になる可能性があるか評価することを繰り返し行い、
その繰り返しの過程において、
ブロックbBのSAD値が最小になる可能性がないと評価できた場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
積算データGBの要素GBzの既取得ビット数が積算データGBの表現ビット数wよりも大きくなる場合には、繰り返しを終了して、ブロックbAと当該ブロックbBとの間でSAD計算を行う、
ことを特徴とする動きベクトル探索方法。
【請求項２】
画像フレームIA中のブロックbAと、画像フレームIBに定めた探索範囲中のブロックbBとの間で、SAD値を計算することで類似度を評価し、当該探索範囲中でSAD値が最小となるブロックbBmaxを見つけることにより、画像フレームIAの各ブロックについて動きベクトルを計算する動きベクトル探索方法であって、
ブロックbBmaxの探索中に、SAD値が最小になる可能性がないブロックbBをSAD計算の対象から除外する、SEA探索法に基づく動きベクトル探索方法において、
画像フレームIA中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGAと、
画像フレームIB中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGBと、
を用意し、
積算データGBの各要素の表現ビット数がwであるとしたとき、積算データGBの各要素から、
上位Qビットを取り出してこれを新たな要素とした上位ビットデータGBUと、
下位w-Qビットを取り出してこれを新たな要素とした下位ビットデータGBLと、
を用意し、
積算データGAと上位ビットデータGBUとを内部メモリに、
下位ビットデータGBLを当該内部メモリ以外のメモリ外記憶装置に、
それぞれ配置し、
ブロックbAに対応する積算データGAの要素GAzを取得し、
既取得ビット数を表す変数kkを値kで初期化した後に、ブロックbBに対応する積算データGBの要素GBzの上位kビットを上位ビットデータGBUから取得してこれをGBz(kk)とし、
補正値Thの値を2の(w-kk)乗に設定し、
ブロックbBmaxの探索中に得られたSAD値の最小値SADminとして暫定的な値を用いて、
値GBz(kk)から補正値Thを減じた値が、値GAzから最小値SADminを減じた値以上であることを示す不等式E1'と、
値GBz(kk)に補正値Thを加えた値が、値GAzに最小値SADminを加えた値以下であることを示す不等式E2'と、
を評価し、
不等式E1'および不等式E2'がいずれも真である場合には、
変数kkに値kを加えたものを新たなkkとした後に、ブロックbBに対応する積算データGBの要素GBzの上位kk-kビット目からkビット分を、変数kkがデータGBUのビット幅Q以下の場合には上位ビットデータGBUから、変数kkがQよりも大きい場合には下位ビットデータGBLから、取得して、これを取得済みのGBz(kk)に加算したものを新たなGBz(kk)とし、
補正値Thの値を2の(w-kk)乗に更新し、
現時点のSAD値の最小値SADminを用いて、
再び、不等式E1'および不等式E2'を評価することを繰り返し、
その繰り返しの過程において、
不等式E1'および不等式E2'の一方または双方が偽となった場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
変数kkの値が積算データGBの表現ビット数wよりも大きくなった場合には、繰り返しを終了して、ブロックbAと当該ブロックbBとの間でSAD計算を行う、
ことを特徴とする動きベクトル探索方法。
【請求項３】
画像フレームIA中のブロックbAと、画像フレームIBに定めた探索範囲中のブロックbBとの間で、SAD値を計算することで類似度を評価し、当該探索範囲中でSAD値が最小となるブロックbBmaxを見つけることにより、画像フレームIAの各ブロックについて動きベクトルを計算する動きベクトル探索方法であって、
ブロックbBmaxの探索中に、SAD値が最小になる可能性がないブロックbBをSAD計算の対象から除外する、SEA探索法に基づく動きベクトル探索方法において、
画像フレームIA中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGAと、
画像フレームIB中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGBと、
を用意し、
積算データGAおよび積算データGBの各要素の表現ビット数がwであるとしたとき、積算データGAの各要素から、
上位Qビットを取り出してこれを新たな要素とした上位ビットデータGAUと、
下位w-Qビットを取り出してこれを新たな要素とした下位ビットデータGALと、
を用意し、
積算データGBの各要素から、
上位Qビットを取り出してこれを新たな要素とした上位ビットデータGBUと、
下位w-Qビットを取り出してこれを新たな要素とした下位ビットデータGBLと、
を用意し、
上位ビットデータGAUと上位ビットデータGBUとを内部メモリ内に、
下位ビットデータGALと下位ビットデータGBLとを当該内部メモリ以外のメモリ外記憶装置に、
それぞれ配置し、
既取得ビット数を表す変数kkを値kで初期化した後に、ブロックbAに対応する積算データGAの要素GAzの上位kビットを上位ビットデータGAUから取得してこれをGAz(kk)とし、
ブロックbBに対応する積算データGBの要素GBzの上位kビットを上位ビットデータGBUから取得してこれをGBz(kk)とし、
補正値Thの値を2の(w-kk+1)乗に設定し、
ブロックbBmaxの探索中に得られたSAD値の最小値SADminとして暫定的な値を用いて、
値GBz(kk)から補正値Thを減じた値が、値GAz(kk)から最小値SADminを減じた値以上であることを示す不等式E1'と、
値GBz(kk)に補正値Thを加えた値が、値GAz(kk)に最小値SADminを加えた値以下であることを示す不等式E2'と、
を評価し、
不等式E1'および不等式E2'がいずれも真である場合には、
変数kkに値kを加えたものを新たなkkとした後に、ブロックbAに対応する積算データGAの要素GAzの上位kk-kビット目からkビット分を、変数kkがデータGAUのビット幅Q以下の場合には上位ビットデータGAUから、変数kkがQよりも大きい場合には下位ビットデータGALから、取得して、これを取得済みのGAz(kk)に加算したものを新たなGAz(kk)とし、
ブロックbBに対応する積算データGBの要素GBzの上位kk-kビット目からkビット分を、変数kkがデータGBUのビット幅Q以下の場合には上位ビットデータGBUから、変数kkがQよりも大きい場合には下位ビットデータGBLから、取得して、これを取得済みのGBz(kk)に加算したものを新たなGBz(kk)とし、
補正値Thの値を2の(w-kk+1)乗に更新し、
現時点のSAD値の最小値SADminを用いて、
再び、不等式E1'および不等式E2'を評価することを繰り返し、
その繰り返しの過程において、
不等式E1'および不等式E2'の一方または双方が偽となった場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
変数kkの値が積算データGBの表現ビット数wより大きくなった場合には、繰り返しを終了して、ブロックbAと当該ブロックbBとの間でSAD計算を行う、
ことを特徴とする動きベクトル探索方法。
【請求項４】
画像フレームIA中のブロックbAと、画像フレームIBに定めた探索範囲中のブロックbBとの間で、SAD値を計算することで類似度を評価し、当該探索範囲中でSAD値が最小となるブロックbBmaxを見つけることにより、画像フレームIAの各ブロックについて動きベクトルを計算する動きベクトル探索方法として、
ブロックbBmaxの探索中に、SAD値が最小になる可能性がないブロックbBをSAD計算の対象から除外する、SEA探索法に基づく動きベクトル探索方法を実行する画像符号化装置において、
画像フレームIA中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGAを用意するとともに、画像フレームIB中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGBを用意する積算データ作成部と、
ブロックbBに対応する積算データGBの要素GBzを上位からkビット分ずつ取得する度に、これまで取得したGBzと、ブロックbAに対応する積算データGAの要素GAzと、を用いて、ブロックbBのSAD値が最小になる可能性があるか評価することを繰り返し行うSAD計算必要性判定部と、
終了判定部と、
SAD計算実行部と、を有し、
その繰り返しの過程において、
前記終了判定部は、ブロックbBのSAD値が最小になる可能性がないと評価できた場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
前記終了判定部は、積算データGBの要素GBzの既取得ビット数が積算データGBの表現ビット数wよりも大きくなる場合には、繰り返しを終了し、前記SAD計算実行部は、ブロックbAと当該ブロックbBとの間でSAD計算を行う、
ことを特徴とする画像符号化装置。
【請求項５】
画像フレームIA中のブロックbAと、画像フレームIBに定めた探索範囲中のブロックbBとの間で、SAD値を計算することで類似度を評価し、当該探索範囲中でSAD値が最小となるブロックbBmaxを見つけることにより、画像フレームIAの各ブロックについて動きベクトルを計算する動きベクトル探索方法として、
ブロックbBmaxの探索中に、SAD値が最小になる可能性がないブロックbBをSAD計算の対象から除外する、SEA探索法に基づく動きベクトル探索方法を実行する画像符号化装置において、
画像フレームIA中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGAを用意するとともに、画像フレームIB中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGBを用意する積算データ作成部と、
積算データGBの各要素の表現ビット数がwであるとしたとき、積算データGBの各要素から、上位Qビットを取り出してこれを新たな要素とした上位ビットデータGBUと、下位w-Qビットを取り出してこれを新たな要素とした下位ビットデータGBLと、を用意する積算データ分割部と、
積算データGAと上位ビットデータGBUとが配置される内部メモリと、
下位ビットデータGBLが配置される、当該内部メモリ以外のメモリ外記憶装置と、
既取得ビット数を表す変数kkを値kで初期化するとともに、補正値Thの値を2の(w-kk)乗に設定するパラメータ設定部と、
ブロックbAに対応する積算データGAの要素GAzを取得するとともに、前記パラメータ設定部が変数kkを値kで初期化した後に、ブロックbBに対応する積算データGBの要素GBzの上位kビットを上位ビットデータGBUから取得してこれをGBz(kk)とするビットデータ取得部と、
ブロックbBmaxの探索中に得られたSAD値の最小値SADminとして暫定的な値を用いて、値GBz(kk)から補正値Thを減じた値が、値GAzから最小値SADminを減じた値以上であることを示す不等式E1'と、値GBz(kk)に補正値Thを加えた値が、値GAzに最小値SADminを加えた値以下であることを示す不等式E2'と、を評価するSAD計算必要性判定部と、
終了判定部と、
SAD計算実行部と、を有し、
不等式E1'および不等式E2'がいずれも真である場合には、
前記パラメータ設定部が変数kkに値kを加えたものを新たなkkとした後に、前記ビットデータ取得部は、ブロックbBに対応する積算データGBの要素GBzの上位kk-k目ビットからkビット分を、変数kkがデータGBUのビット幅Q以下の場合には上位ビットデータGBUから、変数kkがQよりも大きい場合には下位ビットデータGBLから、取得して、これを取得済みのGBz(kk)に加算したものを新たなGBz(kk)とし、
前記パラメータ設定部は、補正値Thの値を2の(w-kk)乗に更新し、
前記SAD計算必要性判定部は、現時点のSAD値の最小値SADminを用いて、再び、不等式E1'および不等式E2'を評価することを繰り返し、
その繰り返しの過程において、
前記終了判定部は、不等式E1'および不等式E2'の一方または双方が偽となった場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
前記終了判定部は、変数kkの値が積算データGBの表現ビット数wよりも大きくなった場合には、繰り返しを終了し、前記SAD計算実行部は、ブロックbAと当該ブロックbBとの間でSAD計算を行う、
ことを特徴とする画像符号化装置。
【請求項６】
画像フレームIA中のブロックbAと、画像フレームIBに定めた探索範囲中のブロックbBとの間で、SAD値を計算することで類似度を評価し、当該探索範囲中でSAD値が最小となるブロックbBmaxを見つけることにより、画像フレームIAの各ブロックについて動きベクトルを計算する動きベクトル探索方法として、
ブロックbBmaxの探索中に、SAD値が最小になる可能性がないブロックbBをSAD計算の対象から除外する、SEA探索法に基づく動きベクトル探索方法を実行する画像符号化装置において、
画像フレームIA中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGAを用意するとともに、画像フレームIB中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGBを用意する積算データ作成部と、
積算データGAおよび積算データGBの各要素の表現ビット数がwであるとしたとき、積算データGAの各要素から、上位Qビットを取り出してこれを新たな要素とした上位ビットデータGAUと、下位w-Qビットを取り出してこれを新たな要素とした下位ビットデータGALと、を用意するとともに、積算データGBの各要素から、上位Qビットを取り出してこれを新たな要素とした上位ビットデータGBUと、下位w-Qビットを取り出してこれを新たな要素とした下位ビットデータGBLと、を用意する積算データ分割部と、
上位ビットデータGAUと上位ビットデータGBUとが配置される内部メモリと、
下位ビットデータGALと下位ビットデータGBLとが配置される、当該内部メモリ以外のメモリ外記憶装置と、
既取得ビット数を表す変数kkを値kで初期化するとともに、補正値Thの値を2の(w-kk)乗に設定するパラメータ設定部と、
前記パラメータ設定部が既取得ビット数を表す変数kkを値kで初期化した後に、ブロックbAに対応する積算データGAの要素GAzの上位kビットを上位ビットデータGAUから取得してこれをGAz(kk)とするとともに、ブロックbBに対応する積算データGBの要素GBzの上位kビットを上位ビットデータGBUから取得してこれをGBz(kk)とするビットデータ取得部と、
ブロックbBmaxの探索中に得られたSAD値の最小値SADminとして暫定的な値を用いて、値GBz(kk)から補正値Thを減じた値が、値GAz(kk)から最小値SADminを減じた値以上であることを示す不等式E1'と、値GBz(kk)に補正値Thを加えた値が、値GAz(kk)に最小値SADminを加えた値以下であることを示す不等式E2'と、を評価するSAD計算必要性判定部と、
終了判定部と、
SAD計算実行部と、を有し、
不等式E1'および不等式E2'がいずれも真である場合には、
前記パラメータ設定部が変数kkに値kを加えたものを新たなkkとした後に、前記ビットデータ取得部は、ブロックbAに対応する積算データGAの要素GAzの上位kk-kビット目からkビット分を、変数kkがデータGAUのビット幅Q以下の場合には上位ビットデータGAUから、変数kkがQよりも大きい場合には下位ビットデータGALから、取得して、これを取得済みのGAz(kk)に加算したものを新たなGAz(kk)とするとともに、ブロックbBに対応する積算データGBの要素GBzの上位kk-kビット目からkビット分を、変数kkがデータGBUのビット幅Q以下の場合には上位ビットデータGBUから、変数kkがQよりも大きい場合には下位ビットデータGBLから、取得して、これを取得済みのGBz(kk)に加算したものを新たなGBz(kk)とし、
前記パラメータ設定部は、補正値Thの値を2の(w-kk+1)乗に更新し、
前記SAD計算必要性判定部は、現時点のSAD値の最小値SADminを用いて、再び、不等式E1'および不等式E2'を評価することを繰り返し、
その繰り返しの過程において、
前記終了判定部は、不等式E1'および不等式E2'の一方または双方が偽となった場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
前記終了判定部は、変数kkの値が積算データGBの表現ビット数wより大きくなった場合には、繰り返しを終了し、前記SAD計算実行部は、ブロックbAと当該ブロックbBとの間でSAD計算を行う、
ことを特徴とする画像符号化装置。
【請求項７】
請求項４から６のいずれか１項に記載の画像符号化装置をコンピュータに実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル動画像の符号化における動きベクトル探索を行うための技術に関する。
【背景技術】
【０００２】
近年の動画像圧縮符号化方式（MPEG-4等）では、動画像を構成する複数の画像フレームの間で動きベクトル探索を行い、動画像の圧縮率を向上させている。
【０００３】
動きベクトル探索では、動画像を構成するある画像フレーム（以下、対象フレームと呼ぶ）中の小領域（以下、ブロックbAと呼ぶ）について、別の画像フレーム（以下、探索先フレームと呼ぶ）中の小領域（以下、ブロックbBと呼ぶ）のうちで最も類似度の高いブロック（以下、ブロックbBmaxと呼ぶ）を探索し、ブロックbAとブロックbBmaxとの画像平面上での座標変分を求める（図1）。
【０００４】
ブロックbBmaxを探索するに際しては、探索先フレーム内に一定の範囲を設定し、その範囲に含まれるブロックを順次取り出しながら、ブロックbAとの類似度を計算し、最も類似するブロックを探すという処理を行う。
【０００５】
この際に用いる類似度としては、SAD（Sum of Absolute Difference）が一般的である。ブロックbAとブロックbBとがともにN個のピクセルを含む場合、ブロックbA中のピクセルとブロックbB中のピクセルとのピクセル値の絶対差をブロック全体で積算した値がSADとなる（式1）。
【０００６】
SAD  =  Σ | pA[x,y] ‐ pB[x,y] |
．．．  （式1）
ここで、
pA[x,y]：ブロックbA中の位置[x,y]にあるピクセルのピクセル値
pB[x,y]：ブロックbB中の位置[x,y]にあるピクセルのピクセル値
Σ：ブロック内の全ピクセルについて積算する意味
である。
【０００７】
動きベクトル探索では、対象フレーム中のブロックbAについて、探索先フレーム中の同じ位置を中心として上下左右に数十から百数十ピクセルずれた範囲（以下、探索範囲という）を設定し、この探索範囲に含まれるブロックを順次取り出し、その度にSAD計算を行って、得られたSAD値の中から最も小さいSAD値を与えるブロックを探す（図2）。
【０００８】
したがって、動きベクトル探索を完了させるためには、対象フレーム中の１つのブロックにつき、探索先フレーム中の探索範囲に含まれる数千ないし１万数千個のブロックとの間でSAD計算を行う必要がある。１回のSAD計算には、ブロック内のピクセル数（通常、数百ピクセル程度）分の加減算と絶対値演算とを要する。この処理を対象フレーム中の全ブロックについて行うことになる。
【０００９】
いま、ブロックの大きさを横bxピクセル、縦byピクセルとし、各画像フレーム内にnb個のブロックが含まれているものとする。探索範囲を横sx、縦syとし、探索１回あたりに要する加減算および絶対値演算の回数をbx * by * 3とすると、探索完了に要する演算回数 qs は、おおよそ、 nb * sx * sy * bx * by * 3 で概算できる（実際には、画像端で探索範囲が減少するため、qsよりも少なくなる）。例えば、横640ピクセル、縦480ピクセルのVGA画像の場合、ブロックのサイズを bx = by = 16とすると、画像フレーム内のブロック数 nb は (640/16) * (480/16) = 1200 である。そのため、探索範囲を sx = sy = 128とすると、qs は150億程度となる。
【００１０】
このように、動きベクトル探索は、非常に膨大な演算量を要するため、リアルタイムで動画像の符号化を行う場合などには処理の効率化が必須となる。
【００１１】
動きベクトル探索を効率的に行う著名な手法として、SEA（Successive Elimination Algorithm）探索法がある（非特許文献１参照）。SEA探索法は、SAD値が最小（類似度が最大）にはなり得ないブロックを探索対象から除外することで処理を効率化する方法であり、あるブロックがある不等式さえ満たせば、SAD計算をせずとも、そのブロックが除外できるというものである。
【００１２】
SEA探索法では、対象フレームおよび探索先フレームについて、各ブロックごとに、そのブロック内のピクセル値を積算したデータ（以下、積算データ）を作成する。画像平面内の位置[x,y]上にある大きさ横bx、縦byのブロックに対応する積算データの値をG[x,y]とすると、G[x,y]は画像フレーム上のピクセル位置 [x,y]から横にbx、縦にbyの矩形領域（ブロック）に含まれるピクセル値全てを積算した値となる。
【００１３】
G(x,y)  =  Σ p[x+i,y+j] 
．．．  （式2）
ここで、
p[x+i,y+j]：画像フレーム上の位置[x+i,y+j]にあるピクセルの値
Σ： i = 0 〜 bx - 1,  j = 0 〜 by ‐ 1  にわたりピクセル値を積算する意味
である。
【００１４】
この積算データを用いると、類似度が最大にはなり得ないブロックを、次のようにして探索対象から除外できる。
【００１５】
まず、対象フレーム上の位置[x,y]にあるブロックbAに対し、探索先フレーム上の探索範囲内の位置[x',y']にあるブロックをとる。そして、次の２つの不等式を計算する。
【００１６】
GA[x,y] ‐ SADmin   ≦   GB[x',y']
GB[x',y']   ≦   GA[x, y] + SADmin
．．．  （式3）
ここで、
GA[x,y]：対象フレーム中の位置[x,y]にあるブロックbAに対応する積算データ
GB[x',y']：探索先フレーム中の位置[x',y']にあるブロックに対応する積算データ
SADmin：それまでの探索で得たSAD値の最小値
である。
【００１７】
この２つの不等式が双方とも満たされない限り、位置[x',y']にあるこのブロックについてのSAD値が最小となることはない（非特許文献１参照）。よって、SAD計算をする必要もなく、このブロックを探索対象から除外できる。一方、この２つの不等式がいずれも満たされた場合には、このブロックについてのSAD値が最小となる可能性を否定できない。この場合には、式1に基づくSAD計算をせざるを得ない。そのSAD計算の結果がそれまでの探索で得られたものの中で最小であれば、上記の式3の中のSADminをその値で更新し、探索を続ける。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】W. Li and E.Sarari, “Successive Elimination Algorithm for motion estimation”, IEEE trans. Image Proc., vol.4, pp.105-107, JAN. 1995
【発明の概要】
【発明が解決しようとする課題】
【００１９】
上記のように、動きベクトル探索に要する演算量は非常に大きいので、リアルタイムで動画像の符号化を行う際には処理の効率化の要求が高い。効率化を図る手法の一つとして非特許文献１に記載のSEA探索法がある。
【００２０】
SEA探索法では、画像フレームごとに積算データを作成しなければならない。この積算データは、画像フレーム中の各ブロックごとに、そのブロックに含まれるピクセル値を積算した値を要素として持つ。そのため、画像のピクセル値そのものよりも値域が広く、その表現に多数のビットを要する。例えば、8ビットの画像に対し、ブロックの大きさが横16ピクセル、縦16ピクセルである場合、積算データの個々の値を表現するには8 + log2(16*16) = 16ビットが必要になる。
【００２１】
したがって、SEA探索を行うためには、画像フレームの画像データとともに、それよりも多くの表現ビット数を要する積算データを内部メモリ上に配置しておく必要がある。しかし、処理が行われる計算環境（ハードウェア）によっては、こうしたことが難しい場合もある。例えば、組み込み用途の環境では、利用できるメモリ量は厳しく制限され得る。
【００２２】
本発明は、メモリ量が制限された計算環境においても、SEA探索法に基づく動きベクトル探索を効果的に実行することができる技術を提供することを目的とするものである。
【課題を解決するための手段】
【００２３】
本発明の動きベクトル探索方法は、
画像フレームIA中のブロックbAと、画像フレームIBに定めた探索範囲中のブロックbBとの間で、SAD値を計算することで類似度を評価し、当該探索範囲中でSAD値が最小となるブロックbBmaxを見つけることにより、画像フレームIAの各ブロックについて動きベクトルを計算する動きベクトル探索方法であって、
ブロックbBmaxの探索中に、SAD値が最小になる可能性がないブロックbBをSAD計算の対象から除外する、SEA探索法に基づく動きベクトル探索方法において、
画像フレームIA中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGAを用意し、
画像フレームIB中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGBを用意し、
ブロックbBに対応する積算データGBの要素GBzを上位からkビット分ずつ順次取得し、取得の度に、これまで取得したGBzと、ブロックbAに対応する積算データGAの要素GAzと、を用いて、ブロックbBのSAD値が最小になる可能性があるか評価することを繰り返し行い、
その繰り返しの過程において、
ブロックbBのSAD値が最小になる可能性がないと評価できた場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
積算データGBの要素GBzの既取得ビット数が積算データGBの表現ビット数wよりも大きくなる場合には、繰り返しを終了して、ブロックbAと当該ブロックbBとの間でSAD計算を行う、
ことを特徴とする。
【００２４】
本発明の画像符号化装置は、
画像フレームIA中のブロックbAと、画像フレームIBに定めた探索範囲中のブロックbBとの間で、SAD値を計算することで類似度を評価し、当該探索範囲中でSAD値が最小となるブロックbBmaxを見つけることにより、画像フレームIAの各ブロックについて動きベクトルを計算する動きベクトル探索方法として、
ブロックbBmaxの探索中に、SAD値が最小になる可能性がないブロックbBをSAD計算の対象から除外する、SEA探索法に基づく動きベクトル探索方法を実行する画像符号化装置において、
画像フレームIA中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGAを用意するとともに、画像フレームIB中の各ブロックごとに、当該ブロックに含まれるピクセル値を積算したものを要素とする積算データGBを用意する積算データ作成部と、
ブロックbBに対応する積算データGBの要素GBzを上位からkビット分ずつ取得する度に、これまで取得したGBzと、ブロックbAに対応する積算データGAの要素GAzと、を用いて、ブロックbBのSAD値が最小になる可能性があるか評価することを繰り返し行うSAD計算必要性判定部と、
終了判定部と、
SAD計算実行部と、を有し、
その繰り返しの過程において、
前記終了判定部は、ブロックbBのSAD値が最小になる可能性がないと評価できた場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
前記終了判定部は、積算データGBの要素GBzの既取得ビット数が積算データGBの表現ビット数wよりも大きくなる場合には、繰り返しを終了し、前記SAD計算実行部は、ブロックbAと当該ブロックbBとの間でSAD計算を行う、
ことを特徴とする。
【００２５】
本発明のプログラムは、前記画像符号化装置をコンピュータに実現させるためのプログラムであることを特徴とする。
【発明の効果】
【００２６】
以上説明したように、本発明は、
画像フレームIBに定めた探索範囲中のブロックbBに対応する積算データGBの要素GBzを上位からkビット分ずつ順次取得し、取得の度に、これまで取得したGBzと、画像フレームIA中のブロックbAに対応する積算データGAの要素GAzと、を用いて、ブロックbBのSAD値が最小になる可能性があるか評価することを繰り返し行い、
その繰り返しの過程において、
ブロックbBのSAD値が最小になる可能性がないと評価できた場合には、繰り返しを終了して、ブロックbAに対するSAD計算の対象から当該ブロックbBを除外し、
GBzの既取得ビット数が積算データGBの表現ビット数wよりも大きくなる場合には、繰り返しを終了して、ブロックbAとブロックbBとの間でSAD計算を行う。
【００２７】
ここで、例えば、積算データGBの上位Qビットのデータは内部メモリに配置し、下位w-Qビットのデータは内部メモリ以外のメモリ外記憶装置に配置するとする。
【００２８】
上記の繰り返し手順においては、積算データGBzを上位からkビット分ずつ取り出しているので、既取得ビット数がQ以下であれば、内部メモリに配置された積算データのみで探索ができ、既取得ビット数がQを超えたならば、メモリ外記憶装置に配置された下位側データを取得することで、探索を続けることができる。
【００２９】
したがって、本発明の構成をとれば、探索処理量の軽減効果を従来のSEA探索法に基づく動きベクトル探索と同等に維持しつつ、内部メモリに配置すべき積算データの量を低減することができ、メモリ量の限られた計算環境であっても、高速な動きベクトル探索が可能となるという効果が得られる。
【図面の簡単な説明】
【００３０】
【図１】対象フレーム、探索先フレーム、探索範囲、およびブロックを説明する図である。
【図２】対象フレーム、探索先フレーム、探索範囲、およびブロックの位置関係を説明する図である。
【図３】実験に用いた画像を示す図である。
【図４】探索先フレームの積算データを減ビット操作した際のSEA探索法の効果を示す実験結果を表す図である。
【図５】積算データを上位8ビットと下位8ビットとに分割する方法を説明する図である。
【図６】対象フレームの積算データと探索先フレームの積算データとの双方を減ビット操作した際のSEA探索法の効果を示す実験結果を表す図である。
【図７】本発明の第1の実施形態の画像符号化装置の構成を示す図である。
【図８】本発明の第1の実施形態の画像符号化装置による動きベクトル探索方法の手順を説明する図である。
【図９】図8に示したS101〜S103の手順を概略的に説明する図である。
【図１０】本発明の第2の実施形態の画像符号化装置の構成を示す図である。
【図１１】本発明の第2の実施形態の画像符号化装置による動きベクトル探索方法の手順を説明する図である。
【図１２】図11に示したS201〜S203の手順を概略的に説明する図である。
【発明を実施するための形態】
【００３１】
〔１〕本発明の概要
まず、本発明の概要について説明する。
〔１−１〕第1の態様
上記の目的を達成するために、SEA探索に関するある特徴を利用する。その特徴とは、SEA探索において、探索対象（すなわち、SAD計算の対象）からのブロックの除外を式3により行う際、多くの場合はさほどの計算精度を必要としない、ということである。式3の不等式は、多少精度の低いデータで評価しても不成立と評価できることが多いのである。例として、図3の画像IAを用いた実験結果を示すことにする。実験諸元は次のとおりである。
【００３２】
対象フレーム  ：画像IAとする。
【００３３】
大きさは縦横512ピクセル、
ピクセルの表現ビット数は8ビットとする。
【００３４】
探索先フレーム：IAを人為的にずらした画像IBとする。
【００３５】
ブロック      ：大きさ縦横16ピクセルとする。
【００３６】
ブロック内に16*16 = 256ピクセルが含まれる。
【００３７】
積算データ    ：IAに対して積算データGAを作成し、
IBに対して積算データGBを作成する。
【００３８】
ピクセルのビット数が8で、ブロックの大きさが縦横16ピクセルであることから、積算データGAおよびGBの個々のデータは、8+log2(16*16) = 16ビットで表現されることになる。式3の評価にデータの精度が必要ないことを示すため、探索先フレームの積算データGBを低精度化する。具体的には、積算データGBに含まれる個々のデータについて、そのデータを表現するビットの上位kビットのみを取り出し、残りのビットは捨ててしまう（以下、減ビット操作という）ということをする。例えば、１６ビットの積算データの上位2ビット以外は捨ててしまう。ただし、そのように減ビット操作した積算データにより式3の不等式を評価することは論理的に誤りがある。減ビット操作をした積算データを用いる場合には、式3を変形した次式を用いる。
【００３９】
GA[x,y] ‐ SADmin   ≦   GB[x', y'] ‐ Th
GB[x',y'] + Th   ≦   GA[x, y] + SADmin
．．．  （式4）
ここで、式4中のGA[x,y]，GB[x',y']、およびSADminについては式3と同様である。Thは、減ビット操作により積算データが低精度化したことに起因する項である。Thの大きさは、ビット数の減少量に応じて一律に定められる。元の積算データの表現ビット数をwとし、減ビット操作で取り出した上位ビット数をkkとしたとき、
Th   =   2 ^ (w - kk)
．．．  （式5）
である。
【００４０】
ここで、 2 ^ X は、2のX乗を表す。不等式の評価に用いる積算データが減ビット操作により精度を失ったので、その分だけ曖昧さを見込んで不等式を評価するのである。
【００４１】
図4が実験結果である。図4のグラフの横軸は積算データGBについての減ビット数であり、元々の表現ビット数16から横軸の値を差し引くと、実際にSEA探索に用いたビット数となる。グラフの縦軸はSEA探索により除外されるブロック数を全ブロック数との比（パーセント表示）で表したものである。このグラフを見ると、減ビット操作をしていない従来のSEA検索（横軸0）は全ブロック中の約90%を探索対象から除外でき、大幅な効率化が可能であることがわかる。そして、減ビット操作を進める（横軸正方向に進む）と除外できる率は下がっていくのだが、上位4ビット（横軸12）を用いるだけでも全体の70%程度は除外できている。上位2ビット（横軸14）だけでも全体の30%程度に及ぶ。
【００４２】
このように、積算データの上位数ビットを用いるだけで、SEA探索の効果がある程度得られることがわかる。したがって、計算環境で許される内部メモリのメモリ量に応じて、積算データの上位数ビットのみを内部メモリに保存してSEA探索を行う方法が考えられる。しかし、現実の動画像の画像フレームについて、どの程度のビット数を用いれば十分な効果が得られるのかを推定するのは難しい。画像フレームごとに画像の傾向は異なるからである。
【００４３】
そこで、本発明では、積算データに対する減ビット操作を繰り返し行う構成を採ることで、課題の解決を図る。
【００４４】
まず、SEA探索を行うにあたり、積算データの上位kビットだけを取得し、これを用いて式4の不等式を評価する。その結果、そのブロックを探索対象から除外できなければ、既に取得済みのビット数を表す変数kkに値kを加算した後、積算データの上位kk-kビット目からkビット分を取得し、それを既に取得済みの積算データに加算し（こうすることにより、積算データの表現ビット数はkk-kビットからkkビットに増える）、補正項Thを2の（w-kk）乗に更新して、あらためて式4の評価を行う。この手順を、式4の一方または双方が満たされないか、あるいは、積算データの全ビットを使い切るか、いずれかに至るまで繰り返す。繰り返し途中に、式4の一方または双方が満たされなくなったときはそのブロックは探索対象から除外され、そうでなければSAD計算を実行する、ということになる。式4の評価に必要な精度が高くないことからすれば、この手順の繰り返し回数が少ないうちに、探索候補であるブロックの多くが除外されるものと期待できる。
【００４５】
この繰り返し構成によれば、少ないメモリ量の計算環境で、通常のSEA探索の効果を得ることができる。そのために、まず、積算データ全体を上位ビット側と下位ビット側との２つの部分に分割する。例えば、16ビットの積算データに対し、上位側にそのうちの8ビットを割り当てるとした場合、値“1025"のデータは、上位側に“1024"、下位側に“1"として分割できる（1025 = 4 * 2^8 + 1 なので、上位は4 * 256 = 1024、下位は1となる。図5参照）。そして、上位ビット側のデータは内部メモリに配置し、下位ビット側のデータは内部メモリ以外のメモリ外記憶装置に配置する。上位側ビット数をQとすると、Qは計算環境が許すメモリ量に応じて決めることになる。上記の繰り返し手順においては、積算データを上位からkビットずつ取り出してSEA探索を行っているので、既に取り出したビット数がQ以下であれば、内部メモリに配置された積算データのみで探索ができ、そのビット数がQを超えたならば、メモリ外記憶装置に配置された下位側データを取得することで、探索を続けることができる。
【００４６】
したがって、この構成をとれば、少ないメモリ量の計算環境で、通常のSEA探索と同等の効果を得るという課題を解決することができる。
〔１−２〕第2の態様
上記のように、第1の態様においては、SEA探索に用いる２つの積算データのうち、探索先フレームの積算データのみを減ビット操作の対象とした。もう一方の対象フレームの積算データも減ビット操作の対象に加えても、第1の態様と同様に課題の解決が図れる。ただし、式4中の補正項 Th の値を次のようにする。
【００４７】
Th   =   2 ^ (w - kk + 1)
．．．  （式6）
ここで、
w：元の積算データの表現ビット数
kk：減ビット操作で取り出した上位ビット数
である。
【００４８】
つまり、補正項 Th は、第1の態様の場合の2倍とする。式4では、対象フレームの積算データと探索先フレームの積算データとを比較しており、その双方が減ビット操作により精度を失ったため、曖昧さが2倍になるものと考えている。
【００４９】
第1の態様について、図4のグラフを得た実験では、探索先フレームの積算データの上位4ビットを用いれば、約70%のブロックが探索対象から除外できることを確認した。この実験と同じ条件で、対象フレームの積算データも減ビット操作して効果を測定した実験の結果を図6に示す。ただし、減ビット操作は、対象フレームについても探索先フレームについても同じビット数だけ同時に減じるようにしている。
【００５０】
この図6のグラフの傾向は、第1の態様で得た図4のグラフと同様である。しかし、上位4ビット（横軸12）でのブロック除外率は約50%となっており、第1の態様の場合に比べて、効果が小さくなっている。減ビット数が小さいうち（横軸0〜10まで）は、第1の態様とほぼ同程度の効果が見られる。
【００５１】
第2の態様は、第1の態様に比べて、探索効率の向上率がやや小さめの傾向にある。一方で、SEA探索で用いる2つの積算データを双方ともに減ビット操作を施していることから、メモリ量の制限がより厳しい計算環境に対応できるものと言える。
〔２〕本発明の実施形態
次に、本発明の具体的な実施形態について説明する。
〔２−１〕第1の実施形態
第1の実施形態は、上述した第1の態様を具体的に表したものである。
【００５２】
図7に、第1の実施形態の画像符号化装置の構成図を示す。
【００５３】
第1の実施形態の画像符号化装置は、内部メモリ101と、メモリ外記憶装置102と、積算データ作成部103と、積算データ分割部104と、ビットデータ取得部105と、SAD計算必要性判定部106と、ビット幅判定部107と、パラメータ設定部108と、SAD計算部109と、SAD値保持部110と、終了判定部111と、を有している。なお、第1の実施形態の画像符号化装置内の各構成要素が行う処理内容については、図8において説明する。
【００５４】
図8に、第1の実施形態の画像符号化装置による動きベクトル探索方法の具体的な手順を示す。なお、以下で説明する各記号は、上述してきたものに準ずる。
（1）：
まず、ステップS101において、積算データ作成部103は、内部メモリ101に配置されている対象フレームIAについて、対象フレームIA中の各ブロックごとに、そのブロックに含まれるピクセル値を積算したものを要素とする積算データGAを作成する。
【００５５】
また、積算データ作成部103は、内部メモリ101に配置されている探索先フレームIBについて、探索先フレームIB中の各ブロックごとに、そのブロックに含まれるピクセル値を積算したものを要素とする積算データGBを作成する。
【００５６】
ここで、GAおよびGBの各データの表現ビット数をwとする。
（2）：
次に、ステップS102において、積算データ分割部104は、積算データGBを上位ビットデータGBUと下位ビットデータGBLとに分割する。
【００５７】
ここで、GBUはGBの各データから上位Qビットを取り出したものであり、GBLはGBの各データの残りの下位w-Qビットを取り出したものである。
（3）：
次に、ステップS103において、積算データ作成部103は、積算データGAを内部メモリ101に配置する。
【００５８】
また、積算データ分割部104は、上位ビットデータGBUを内部メモリ101に配置し、下位ビットデータGBLをメモリ外記憶装置102に配置する。
【００５９】
以上のステップS101〜S103の手順を概略的に示したのが図9になる。以降、内部メモリ101に配置されたGAから、後述のブロックbAに対応する積算データGA[x,y]（=GAz）が取り出され、内部メモリ101に配置されたGBUまたはメモリ外記憶装置102に配置されたGBLから、後述のブロックbBに対応する積算データGB[x',y']（=GBz）が取り出されることになる。
（4）：
次に、ステップS104において、ビットデータ取得部105は、対象フレームIAの位置[x,y]上のブロックbAについて、これに対応する積算データGA[x,y]（=GAz）を、内部メモリ101に配置されている積算データGAから取得する。
【００６０】
また、SAD値保持部110は、ブロックbAに関する探索でのSAD最小値であるSADminを暫定最小値に初期化する。
【００６１】
次に、ステップS105において、パラメータ設定部108は、探索先フレームIBに設定された探索範囲内の位置[x',y']上のブロックbBに対応する積算データGB[x',y']（=GBz）について現時点で取得済みの既取得ビット数を表す変数kkをkで初期化する。
【００６２】
次に、ステップS106において、ビットデータ取得部105は、積算データGB[x',y']の上位kビットを、内部メモリ101に配置されている上位ビットデータGBUから取得する。
【００６３】
次に、ステップS107において、ビットデータ取得部105は、ステップS106で取得した積算データGB[x',y']の上位kビットを、取得済みのGB[x',y']（=GBz(kk)）とする。
【００６４】
次に、ステップS108において、パラメータ設定部108は、変数kkと積算データGBの表現ビット数wから、補正値Thを以下のように設定する。
【００６５】
Th  =  2 ^ (w-kk)
（5）：
次に、ステップS109において、SAD計算必要性判定部106は、ステップS104で得られたGA[x,y]（=GAz）およびSADmin、ステップS107で得られたGB[x',y']（=GBz(kk)）、およびステップS108で得られたThを用いて、次の2つの不等式を評価する。
【００６６】
GA[x,y] ‐ SADmin   ≦   GB[x',y'] ‐ Th
GB[x',y'] + Th   ≦   GA[x,y] + SADmin
（6）：
ステップS109において、双方の不等式とも満たされる場合は、ステップS110において、ビット幅判定部107は、kk+kの値が積算データGBの表現ビット数wを超えるか判定する。
【００６７】
ステップS110において、kk+kの値がwを超えない場合は、ステップS111において、パラメータ設定部108は、kkを以下のように更新する。
【００６８】
kk  ←  kk + k
次に、ステップS112において、ビットデータ取得部105は、積算データGB[x',y']（=GBz）の上位kk-kビット目からkk-1ビット目までのkビット分のデータを取得する。
【００６９】
このとき、ビットデータ取得部105は、kkの値がGBUの表現ビット数Qを超えない場合は、内部メモリ101に配置されている上位ビットデータGBUから、Qを超える場合は、メモリ外記憶装置102に配置されている下位ビットデータGBLから、データを取得する。
【００７０】
次に、ステップS113において、ビットデータ取得部105は、ステップS112で取得した積算データGB[x',y']の上位kk-kビット目からkビット分のデータを、取得済みのGB[x',y']に加算する（GB[x',y']の加算結果=新たなGBz(kk)）。
【００７１】
次に、ステップS114において、パラメータ設定部108は、Thを以下のように更新する。
【００７２】
Th  =  2 ^ (w-kk)
その後、ステップS109の評価を繰り返す。このステップS109の評価には、SADminとして現時点のSADminが用いられる。
（7）：
ステップS109において、双方または一方の不等式が満たされない場合は、ブロックbBは最小のSAD値を与えるものではない。
【００７３】
そのため、ステップS115において、終了判定部111は、ブロックbBのSAD計算を行わずに、ブロックbBを探索対象から除外する。
【００７４】
この場合、ステップS117において、終了判定部111は、探索範囲内の全ブロックbBについての処理が終了したかを判定する。
【００７５】
ステップS117において、全ブロックbBについての処理が終了していない場合、ステップS118において、終了判定部111は、探索範囲内の次のブロックbBを選択する。
【００７６】
その後、ステップS105に戻り、次のブロックbBに対してステップS105以降の処理を行う。
（8）：
ステップS109において、双方の不等式が満たされ続けた後、ステップS110において、kk+kの値がwを超えた場合は、ステップS116において、SAD計算部109は、対象フレームIA上のブロックbAと探索先フレームIB上のブロックbBについて、SAD計算を行う。
【００７７】
また、その結果得られた値SADcandが現時点の最小値SADminよりも小さい場合は、SAD値保持部110は、SADminの値をSADcandで更新する。
【００７８】
次に、ステップS117において、終了判定部111は、探索範囲内の全ブロックbBについての処理が終了したかを判定する。
【００７９】
ステップS117において、全ブロックbBについての処理が終了していない場合、ステップS118において、終了判定部111は、探索範囲内の次のブロックbBを選択する。
【００８０】
その後、ステップS105に戻り、次のブロックbBに対してステップS105以降の処理を行う。
（9）：
ステップS117において、探索範囲内の全ブロックbBについての処理が終了した場合は、最小のSAD値を与えるブロックbBmaxが判明するので、処理を終了する。
〔２−２〕第2の実施形態
第2の実施形態は、上述した第2の態様を具体的に表したものである。
【００８１】
図10に、第2の実施形態の画像符号化装置の構成図を示す。
【００８２】
第2の実施形態の画像符号化装置は、第1の実施形態と比較して、構成自体は同様であるが、探索先フレームIBだけでなく、対象フレームIAについても、積算データを分割した上で処理を行う点が異なる。なお、第2の実施形態の画像符号化装置内の各構成要素が行う処理内容については、図11において説明する。
【００８３】
図11に、第2の実施形態の画像符号化装置による動きベクトル探索方法の具体的な手順を示す。なお、以下で説明する各記号は、上述してきたものに準ずる。
（1）：
まず、ステップS201において、積算データ作成部103は、内部メモリ101に配置されている対象フレームIAについて、対象フレームIA中の各ブロックごとに、そのブロックに含まれるピクセル値を積算したものを要素とする積算データGAを作成する。
【００８４】
また、積算データ作成部103は、内部メモリ101に配置されている探索先フレームIBについて、探索先フレームIB中の各ブロックごとに、そのブロックに含まれるピクセル値を積算したものを要素とする積算データGBを作成する。
【００８５】
ここで、GAおよびGBの各データの表現ビット数をwとする。
（2）：
次に、ステップS202において、積算データ分割部104は、積算データGAを上位ビットデータGAUと下位ビットデータGALとに分割する。
【００８６】
また、積算データ分割部104は、積算データGBを上位ビットデータGBUと下位ビットデータGBLとに分割する。
【００８７】
ここで、GAUはGAの各データから上位Qビットを取り出したものであり、GALはGAの各データの残りの下位w-Qビットを取り出したものである。
【００８８】
また、GBUはGBの各データから上位Qビットを取り出したものであり、GBLはGBの各データの残りの下位w-Qビットを取り出したものである。
（3）：
次に、ステップS203において、積算データ分割部104は、上位ビットデータGAUおよびGBUを内部メモリ101に配置し、下位ビットデータGALおよびGBLをメモリ外記憶装置102に配置する。
【００８９】
以上のステップS201〜S203の手順を概略的に示したのが図12になる。以降、内部メモリ101に配置されたGAUまたはメモリ外記憶装置102に配置されたGALから、後述のブロックbAに対応する積算データGA[x,y]（=GAz）が取り出され、内部メモリ101に配置されたGBUまたはメモリ外記憶装置102に配置されたGBLから、後述のブロックbBに対応する積算データGB[x',y']（=GBz）が取り出されることになる。
（4）：
次に、ステップS204において、パラメータ設定部108は、対象フレームIAの位置[x,y]上のブロックbAに対応する積算データGA[x,y]（=GAz）および探索先フレームIBに設定された探索範囲内の位置[x',y']上のブロックbBに対応する積算データGB[x',y']（=GBz）について、現時点で取得済みの既取得ビット数を表す変数kkをkで初期化する。
【００９０】
次に、ステップS205において、ビットデータ取得部105は、積算データGA[x,y]の上位kビットを、内部メモリ101に配置されている上位ビットデータGAUから取得する。
【００９１】
また、SAD値保持部110は、ブロックbAに関する探索でのSAD最小値であるSADminを暫定最小値に初期化する。
【００９２】
次に、ステップS206において、ビットデータ取得部105は、積算データGB[x',y']の上位kビットを、内部メモリ101に配置されている上位ビットデータGBUから取得する。
【００９３】
次に、ステップS207において、ビットデータ取得部105は、ステップS205で取得した積算データGA[x,y]の上位kビットを、取得済みのGA[x,y]（=GAz(kk)）とする。
【００９４】
また、ビットデータ取得部105は、ステップS206で取得した積算データGB[x',y']の上位kビットを、取得済みのGB[x',y']（=GBz(kk)）とする。
【００９５】
次に、ステップS208において、パラメータ設定部108は、変数kkと積算データGBの表現ビット数wから、補正値Thを以下のように設定する。
【００９６】
Th  =  2 ^ (w-kk+1)
（5）：
次に、ステップS209において、SAD計算必要性判定部106は、ステップS205で得られたSADmin、ステップS207で得られたGA[x,y]（=GAz(kk)）およびGB[x',y']（=GBz(kk)）、およびステップS208で得られたThを用いて、次の2つの不等式を評価する。
【００９７】
GA[x,y] ‐ SADmin   ≦   GB[x',y'] ‐ Th
GB[x',y'] + Th   ≦   GA[x,y] + SADmin
（6）：
ステップS209において、双方の不等式とも満たされる場合は、ステップS210において、ビット幅判定部107は、kk+kの値が積算データGBの表現ビット数wを超えるか判定する。
【００９８】
ステップS210において、kk+kの値がwを超えない場合は、ステップS211において、パラメータ設定部108は、kkを以下のように更新する。
【００９９】
kk  ←  kk + k
次に、ステップS212において、ビットデータ取得部105は、積算データGA[x,y]の上位kk-kビット目からkk-1ビット目までのkビット分のデータを取得する。
【０１００】
このとき、ビットデータ取得部105は、kkの値がGAUおよびGBUの表現ビット数Qを超えない場合は、内部メモリ101に配置されている上位ビットデータGAUから、Qを超える場合は、メモリ外記憶装置102に配置されている下位ビットデータGALから、データを取得する。
【０１０１】
また、ビットデータ取得部105は、積算データGB[x',y']の上位kk-kビット目からkk-1ビット目までのkビット分のデータを取得する。
【０１０２】
このとき、ビットデータ取得部105は、kkの値がGAUおよびGBUの表現ビット数Qを超えない場合は、内部メモリ101に配置されている上位ビットデータGBUから、Qを超える場合は、メモリ外記憶装置102に配置されている下位ビットデータGBLから、データを取得する。
【０１０３】
次に、ステップS213において、ビットデータ取得部105は、ステップS212で取得した積算データGA[x,y]の上位kk-kビット目からkビット分のデータを、取得済みのGA[x,y]に加算する（GA[x,y]の加算結果=新たなGAz(kk)）。
【０１０４】
また、ビットデータ取得部105は、ステップS212で取得した積算データGB[x',y']の上位kk-kビット目からkビット分のデータを、取得済みのGB[x',y']に加算する（GB[x',y']の加算結果=新たなGBz(kk)）。
【０１０５】
次に、ステップS214において、パラメータ設定部108は、Thを以下のように更新する。
【０１０６】
Th  =  2 ^ (w-kk+1)
その後、ステップS209の評価を繰り返す。このステップS209の評価には、SADminとして現時点のSADminが用いられる。
（7）：
ステップS209において、双方または一方の不等式が満たされない場合は、ブロックbBは最小のSAD値を与えるものではない。
【０１０７】
そのため、ステップS215において、終了判定部111は、ブロックbBのSAD計算を行わずに、ブロックbBを探索対象から除外する。
【０１０８】
この場合、ステップS217において、終了判定部111は、探索範囲内の全ブロックbBについての処理が終了したかを判定する。
【０１０９】
ステップS217において、全ブロックbBについての処理が終了していない場合、ステップS218において、終了判定部111は、探索範囲内の次のブロックbBを選択する。
【０１１０】
次に、ステップS219において、パラメータ設定部108は、変数kkをkで初期化する。
【０１１１】
その後、ステップS206に戻り、次のブロックbBに対してステップS206以降の処理を行う。
（8）：
ステップS209において、双方の不等式が満たされ続けた後、ステップS210において、kk+kの値がwを超えた場合は、ステップS216において、SAD計算部109は、対象フレームIA上のブロックbAと探索先フレームIB上のブロックbBについて、SAD計算を行う。
【０１１２】
また、その結果得られた値SADcandが現時点の最小値SADminよりも小さい場合は、SAD値保持部110は、SADminの値をSADcandで更新する。
【０１１３】
次に、ステップS217において、終了判定部111は、探索範囲内の全ブロックbBについての処理が終了したかを判定する。
【０１１４】
ステップS217において、全ブロックbBについての処理が終了していない場合、ステップS218において、終了判定部111は、探索範囲内の次のブロックbBを選択する。
【０１１５】
次に、ステップS219において、パラメータ設定部108は、変数kkをkで初期化する。
【０１１６】
その後、ステップS206に戻り、次のブロックbBに対してステップS206以降の処理を行う。
（9）：
ステップS217において、探索範囲内の全ブロックbBについての処理が終了した場合は、最小のSAD値を与えるブロックbBmaxが判明するので、処理を終了する。
【０１１７】
なお、本発明の画像符号化装置は、コンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。また、このプログラムは、本発明を実施する際に計算環境にインストールされ、ＣＰＵ等の計算手段の下で動作して本発明を実現することになる。
【産業上の利用可能性】
【０１１８】
本発明は、ディジタル動画像の符号化を行う画像符号化装置に適用することができる。本発明を適用することで、従来よりもメモリ量が制限された計算環境でも、従来と同等に効率的な符号化処理を実現できる。
【符号の説明】
【０１１９】
101    内部メモリ
102    メモリ外記憶装置
103    積算データ作成部
104    積算データ分割部
105    ビットデータ取得部
106    SAD計算必要性判定部
107    ビット幅判定部
108    パラメータ設定部
109    SAD計算部
110    SAD値保持部
111    終了判定部
【図２】
2015111753.tif 000003
【図３】
2015111753.tif 000004
【図７】
2015111753.tif 000005
【図８】
2015111753.tif 000006
【図１０】
2015111753.tif 000007
【図１１】
2015111753.tif 000008
【図１】
2015111753.tif 000009
【図４】
2015111753.tif 000010
【図５】
2015111753.tif 000011
【図６】
2015111753.tif 000012
【図９】
2015111753.tif 000013
【図１２】
2015111753.tif 000014