(57)【要約】【課題】双方向予測符号化画像（いわゆるＢピクチャ）の符号化効率を向上させる。【解決手段】第１の参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索し、第２の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索し、さらに、記第１の参照フレームから探索したブロックと前記第２の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなる、前記第１の参照フレーム中のブロックと前記第２の参照フレーム中のブロックとの組合せを求め、求めた組み合わせに基づいて、動きベクトルの対を探索し、そして、前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちから、類似度が最も大きくなる動きベクトル又は動きベクトルの対を選択する。【選択図】図１
2008011158.tif 000002
【特許請求の範囲】
【請求項１】
第１の参照フレーム及び第２の参照フレームを含む２つ以上の参照フレームを用いて、動画像信号の動き補償フレーム間予測符号化を行なうにあたり、符号化対象フレームを構成する符号化対象ブロック毎に動きベクトルを探索する動きベクトル探索方法であって、
前記第１の参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索する第１の動きベクトル探索ステップと、
前記第２の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索する第２の動きベクトル探索ステップと、
前記第１の参照フレームから探索したブロックと前記第２の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなるように、前記第１の参照フレーム中のブロックと前記第２の参照フレーム中のブロックとの組合せを求め、求めた組み合わせに基づいて、動きベクトルの対を探索する第３の動きベクトル探索ステップと、
前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちの何れかを選択する動きベクトル選択ステップと、
を有することを特徴とする動きベクトル探索方法。
【請求項２】
請求項１の動きベクトル探索方法であって、
前記第３の動きベクトル探索ステップは、前記第１の参照フレームにおける探索範囲として、前記第１の動きベクトルに対応したブロックを含む領域を設定し、前記第２の参照フレームにおける探索範囲として、前記第２の動きベクトルに対応したブロックを含む領域を設定する探索範囲設定ステップを含むことを特徴とする動きベクトル探索方法。
【請求項３】
請求項２の動きベクトル探索方法であって、
前記探索範囲設定ステップは、第１の動きベクトルに対応したブロックと前記符号化対象ブロックとの相関を示す第１の相関度、及び前記第２の動きベクトルに対応したブロックと前記符号化対象ブロックとの相関を示す第２の相関度に応じ、前記第１の参照フレーム及び前記第２の参照フレームにおける探索範囲を設定することを特徴とする動きベクトル探索方法。
【請求項４】
請求項３の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の相関度及び前記第２の相関度のうちの大きい方の相関度に対応した参照フレームにおける探索範囲を、他方の参照フレームにおける探索範囲よりも狭くすることを特徴とする動きベクトル探索方法。
【請求項５】
請求項３の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の相関度及び前記第２の相関度のうちの大きい方の相関度に対応した動きベクトルが示す１点を、大きい方の相関度に対応した参照フレームにおける探索範囲として設定することを特徴とする動きベクトル探索方法。
【請求項６】
請求項４の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の相関度及び前記第２の相関度のうちの大きい方の相関度が、所定の相関度閾値よりも大きい場合には、大きい方の相関度に対応した動きベクトルが示す１点を、大きい方の相関度に対応した参照フレームにおける探索範囲として設定することを特徴とする動きベクトル探索方法。
【請求項７】
請求項６の動きベクトル探索方法であって、
前記相関度閾値は、前記第１の参照フレームと前記符号化対象フレームとの時間軸距離、及び前記第２の参照フレームと前記符号化対象フレームとの時間軸距離に応じて設定されることを特徴とする動きベクトル探索方法。
【請求項８】
請求項６の動きベクトル探索方法であって、
前記相関度閾値は、前記符号化対象ブロックの周辺で符号化済のブロックのうちの、前記第１の動きベクトルが用いられて符号化されたブロックの個数と、前記第２の動きベクトルが用いられて符号化されたブロックの個数とに応じて設定されることを特徴とする動きベクトル探索方法。
【請求項９】
請求項２の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の参照フレームと前記符号化対象フレームとの時間軸距離を示す第１の時間軸距離、及び前記第２の参照フレームと前記符号化対象フレームとの時間軸距離を示す第２の時間軸距離に応じ、前記第１の参照フレーム及び前記第２の参照フレームにおける探索範囲を設定することを特徴とする動きベクトル探索方法。
【請求項１０】
請求項９の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の時間軸距離及び前記第２の時間軸距離のうちの小さい方の時間軸距離に対応した参照フレームにおける探索範囲を、他方の参照フレームにおける探索範囲よりも狭くすることを特徴とする動きベクトル探索方法。
【請求項１１】
請求項９の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の時間軸距離及び前記第２の時間軸距離のうちの小さい方の時間軸距離に対応した動きベクトルが示す１点を、前記探索範囲として設定することを特徴とする動きベクトル探索方法。
【請求項１２】
請求項１０の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の時間軸距離及び前記第２の時間軸距離のうちの小さい方の時間軸距離が、所定の距離閾値よりも小さい場合には、小さい方の時間軸距離に対応した動きベクトルが示す１点を、小さい方の時間軸距離に対応した参照フレームとして設定することを特徴とする動きベクトル探索方法。
【請求項１３】
請求項２の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記符号化対象ブロックの周辺の符号化済のブロックのうちの、前記第１の動きベクトルが用いられて符号化されたブロックの個数を示す第１の参照個数と、前記第２の動きベクトルが用いられて符号化されたブロックの個数を示す第２の参照個数とに応じ、前記第１の参照フレーム及び前記第２の参照フレームにおける探索範囲を設定することを特徴とする動きベクトル探索方法。
【請求項１４】
請求項１３の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の参照個数が前記第２の参照個数よりも大きい場合には、前記第１の参照フレームにおける探索範囲を、前記第２の参照フレームにおける探索範囲よりも狭く設定し、前記第２の参照個数が前記第１の参照個数よりも大きい場合には、前記第２の参照フレームにおける探索範囲を、前記第１の参照フレームにおける探索範囲よりも狭く設定することを特徴とする動きベクトル探索方法。
【請求項１５】
請求項１３の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の参照個数が前記第２の参照個数よりも大きい場合には、前記第１の参照フレームにおける探索範囲として、第１の動きベクトルが示す１点を設定し、前記第２の参照個数が前記第１の参照個数よりも大きい場合には、前記第２の参照フレームにおける探索範囲として、第２の動きベクトルが示す１点を設定することを特徴とする動きベクトル探索方法。
【請求項１６】
請求項１４の動きベクトル探索方法であって、
前記探索範囲設定ステップは、前記第１の参照フレームにおける探索範囲を、前記第２の参照フレームにおける探索範囲よりも狭く設定した場合において、前記第１の参照個数が所定の参照方式個数閾値よりも大きい場合には、前記第１の動きベクトルに対応した１点を、前記第１の参照フレームにおける探索範囲として設定し、前記第２の参照フレームにおける探索範囲を、前記第１の参照フレームにおける探索範囲よりも狭く設定した場合において、前記第２の参照個数が所定の参照方式個数閾値よりも大きい場合には、前記第２の動きベクトルに対応した１点を、前記第２の参照フレームにおける探索範囲として設定することを特徴とする動きベクトル探索方法。
【請求項１７】
請求項２の動きベクトル探索方法であって、
前記探索範囲設定ステップは、
前記参照フレームと前記符号化対象ブロックとの相関度と、
前記参照フレームと前記符号化対象ブロックとの時間軸距離と、
前記符号化対象ブロックの周辺の符号化済のブロックのうちの、前記第１の動きベクトルが用いられて符号化されたブロックの個数を示す第１の参照個数と、前記第２の動きベクトルが用いられて符号化されたブロックの個数を示す第２の参照個数とに応じ、前記第１の参照フレーム及び前記第２の参照フレームにおける探索範囲として設定することを特徴とする動きベクトル探索方法。
【請求項１８】
第１の参照フレーム及び第２の参照フレームを含む２つ以上の参照フレームを用いて、動画像信号の動き補償フレーム間予測符号化を行なうにあたり、符号化対象フレームを構成する符号化対象ブロック毎に動きベクトルを探索する動きベクトル探索方法であって、
前記第１の参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索する第１の動きベクトル探索ステップと、
前記第２の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索する第２の動きベクトル探索ステップと、
前記第１の参照フレームから探索したブロックと前記第２の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなるように、前記第１の参照フレーム中のブロックと前記第２の参照フレーム中のブロックとの組合せを求め、求めた組み合わせに基づいて、動きベクトルの対を探索する第３の動きベクトル探索ステップと、
前記第３の動きベクトル探索ステップの有効性を判定して、前記第３の動きベクトル探索ステップによる処理を行なうか否かを判定する判定ステップと、
前記第３の動きベクトル探索ステップによる処理が行なわれた場合には、前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちの何れかを選択し、前記第３の動きベクトル探索ステップによる処理が行なわれなかった場合には、前記第１の動きベクトル及び第２の動きベクトルのうちの一方を選択する動きベクトル選択ステップと、
を有することを特徴とする動きベクトル探索方法。
【請求項１９】
請求項１８の動きベクトル探索方法であって、
前記判定ステップは、前記符号化対象ブロックの画素値に基づいて、前記有効性を判定することを特徴とする動きベクトル探索方法。
【請求項２０】
請求項１８の動きベクトル探索方法であって、
前記判定ステップは、第１の動きベクトルに対応したブロックと前記符号化対象ブロックとの相関を示す第１の相関度、及び前記第２の動きベクトルに対応したブロックと前記符号化対象ブロックとの相関を示す第２の相関度のうち、大きい方の相関度が、所定の相関度閾値よりも大きい場合には、前記第３の動きベクトル探索ステップによる処理を行なわないように判定することを特徴とする動きベクトル探索方法。
【請求項２１】
請求項２０の動きベクトル探索方法であって、
前記相関度閾値は、前記第１の参照フレームと前記符号化対象フレームとの時間軸距離、及び前記第２の参照フレームと前記符号化対象フレームとの時間軸距離に応じて設定されることを特徴とする動きベクトル探索方法。
【請求項２２】
請求項２１の動きベクトル探索方法であって、
前記相関度閾値は、前記符号化対象ブロックの周辺で符号化済のブロックのうちの、前記第１の動きベクトルが用いられて符号化されたブロックの個数と前記第２の動きベクトルが用いられて符号化されたブロックの個数とに応じて設定されることを特徴とする動きベクトル探索方法。
【請求項２３】
請求項２０の動きベクトル探索方法であって、
前記相関度閾値は、前記符号化対象ブロックの画素レベルに基づいて、設定されることを特徴とする動きベクトル探索方法。
【請求項２４】
請求項１８の動きベクトル探索方法であって、
前記判定ステップは、前記第１の参照フレームと前記符号化対象フレームとの時間軸距離を示す第１の時間軸距離、及び前記第２の参照フレームと前記符号化対象フレームとの時間軸距離を示す第２の時間軸距離のうち、近い方の距離が、所定の距離閾値よりも小さい場合には、前記第３の動きベクトル探索ステップによる処理を行なわないように判定することを特徴とする動きベクトル探索方法。
【請求項２５】
請求項２４の動きベクトル探索方法であって、
前記距離閾値は、前記符号化対象ブロックの画素レベルに基づいて、設定されることを特徴とする動きベクトル探索方法。
【請求項２６】
請求項１８の動きベクトル探索方法であって、
前記判定ステップは、前記符号化対象ブロックの周辺の符号化済のブロックのうちの、前記第１の動きベクトルが用いられて符号化されたブロックの個数を示す第１の参照個数、及び前記第２の動きベクトルが用いられて符号化されたブロックの個数を示す第２の参照個数のうち、大きい方の参照個数が、所定の参照方式個数閾値よりも大きい場合には、前記第３の動きベクトル探索ステップによる処理を行なわないように判定することを特徴とする動きベクトル探索方法。
【請求項２７】
請求項２６の動きベクトル探索方法であって、
前記参照方式個数閾値は、前記符号化対象ブロックの画素レベルに基づいて、設定されることを特徴とする動きベクトル探索方法。
【請求項２８】
第１の参照フレーム及び第２の参照フレームを含む２つ以上の参照フレームを用いて、動画像信号の動き補償フレーム間予測符号化を行なうにあたり、符号化対象フレームを構成する符号化対象ブロック毎に動きベクトルを探索する動きベクトル探索方法であって、
第１の参照フレーム及び第２の参照フレームの何れか一方を選択する探索方向決定ステップと、
前記探索方向決定ステップで選択した参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索する第１の動きベクトル探索ステップと、
前記探索方向決定ステップで選択されなかった他方の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索すると同時に、前記第１の動きベクトルと対応したブロックと前記他方の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなるように、前記他方の参照フレーム中のブロックを求め、求めたブロックに基づいて、第３の動きベクトルを探索し、前記第２及び第３の動きベクトルからなる動きベクトルの対を得る動きベクトル対探索ステップと、
前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちの何れかを選択する動きベクトル選択ステップと、
を有することを特徴とする動きベクトル探索方法。
【請求項２９】
請求項２８の動きベクトル探索方法であって、
前記探索方向決定ステップは、前記第１の参照フレームと前記符号化対象フレームとの時間軸距離、及び前記第２の参照フレームと前記符号化対象フレームとの時間軸距離とを比較し、時間軸距離が小さい方の参照フレームを選択することを特徴とする動きベクトル探索方法。
【請求項３０】
請求項２８の動きベクトル探索方法であって、
前記探索方向決定ステップは、前記符号化対象ブロックの周辺で符号化済のブロックのうちの、前記第１の動きベクトルが用いられて符号化されたブロックの個数と前記第２の動きベクトルが用いられて符号化されたブロックの個数とを比較し、個数が大きい方の参照フレームを選択することを特徴とする動きベクトル探索方法。
【請求項３１】
第１の参照フレーム及び第２の参照フレームを含む２つ以上の参照フレームを用いて、動画像信号の動き補償フレーム間予測符号化を行なうにあたり、符号化対象フレームを構成する符号化対象ブロック毎に動きベクトルを探索する動きベクトル探索装置であって、
前記第１の参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索する第１の動きベクトル探索部と、
前記第２の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索する第２の動きベクトル探索部と、
前記第１の参照フレームから探索したブロックと前記第２の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなるように、前記第１の参照フレーム中のブロックと前記第２の参照フレーム中のブロックとの組合せを求め、求めた組み合わせに基づいて、動きベクトルの対を探索する第３の動きベクトル探索部と、
前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちの何れかを選択する動きベクトル選択部と、
を備えたことを特徴とする動きベクトル探索装置。
【請求項３２】
第１の参照フレーム及び第２の参照フレームを含む２つ以上の参照フレームを用いて、動画像信号の動き補償フレーム間予測符号化を行なうにあたり、符号化対象フレームを構成する符号化対象ブロック毎に動きベクトルを探索する動きベクトル探索装置であって、
第１の参照フレーム及び第２の参照フレームの何れか一方を選択する探索方向決定部と、
前記探索方向決定ステップで選択した参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索する第１の動きベクトル探索部と、
前記探索方向決定ステップで選択されなかった他方の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索すると同時に、前記第１の動きベクトルと対応したブロックと前記他方の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなるように、前記他方の参照フレーム中のブロックを求め、求めたブロックに基づいて、第３の動きベクトルを探索し、前記第２及び第３の動きベクトルからなる動きベクトルの対を探索する動きベクトル対探索部と、
前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちの何れかを選択する動きベクトル選択部と、
を有することを特徴とする動きベクトル探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル動画像データの圧縮に用いられる動きベクトル探索方法及び前記動きベクトル探索を行なう動きベクトル探索装置に関するものである。
【背景技術】
【０００２】
近年、デジタル放送やＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）等の光ディスクビデオなどの様々な分野にデジタル動画像の圧縮技術が応用されている。
【０００３】
動画像データの圧縮方法の一つとして、動画像の一部を構成する２つの画面（フレーム）間の相関関係を利用したものがあり、その圧縮方法を実現する代表的な技術として、ＩＳＯ／ＩＥＣ勧告の動画像圧縮技術であるＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅｓ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）にも採用されている動き補償予測符号化技術がある。
【０００４】
動き補償予測符号化技術は、符号化対象ブロックに最も類似するブロックを参照画像中から探索し、符号化対象ブロックと最類似ブロックとの差分ブロック、及び参照画像中における符号化対象ブロック位置を表す座標から最類似ブロックへのベクトルを符号化することで、情報量の圧縮を行なうものである。
【０００５】
ＭＰＥＧでは、動画像は、参照方法の違うＩピクチャ（フレーム内符号化画像）、Ｐピクチャ（フレーム間順方向予測符号化画像）、及びＢピクチャ（双方向予測符号化画像）の３種類のピクチャによって構成され、各ピクチャは、複数のブロック（マクロブロック）によって構成されている。
【０００６】
Ｂピクチャは、ＩピクチャもしくはＰピクチャの間に複数枚内挿されるのが一般的である。また、Ｂピクチャは、マクロブロックごとに、時間的に過去のピクチャを参照画像（前方参照画像と呼ぶ）として動き補償予測符号化を行なう方式（前方参照方式）、時間的に未来のピクチャを参照画像（後方参照画像と呼ぶ）として動き補償予測符号化を行なう方式（後方参照方式）、前方参照画像と後方参照画像との両方を参照画像として平均化ブロックを求めて動き補償予測符号化を行なう方式（双方向参照方式）の何れかを選択して、動き補償予測符号化を行うことができる。Ｂピクチャが使用されることにより、ＭＰＥＧでは動き補償予測符号化における予測精度が向上し、効率の良い符号化を実現することができる。
【０００７】
従来より知られている動き補償予測符号化の方法としては、例えば、ＭＰＥＧ２のテストモデル５（以下、ＴＭ５と呼ぶ）におけるＢピクチャの符号化アルゴリズムがある。ＴＭ５における符号化では、まず、前方参照画像内を探索して、符号化対象ブロックに最も類似するブロックを検出し、符号化対象ブロックから、検出したブロックへの動きを表す動きベクトルと類似度（すなわち相関度）とを求める（前方動きベクトル探索）。次に、後方参照画像内を探索して、符号化対象ブロックに最も類似するブロックを検出し、符号化対象ブロックから、検出したブロックへの動きを表す動きベクトルと類似度とを求める（後方動きベクトル探索）。次に、求めた類似ブロック同士を平均化して平均化ブロックを求め、符号化対象ブロックから平均化ブロックへの動きを表す動きベクトルと類似度を求める。そして、前方参照における類似度、後方参照における類似度、及び双方向参照における類似度を比較し、最も高い類似度を持つ参照方式を選択する。上記のように、ＴＭ５では、比較的少ない演算量で、動き補償予測符号化を実現している。
【０００８】
また、別の動き補償予測符号化の方法としては、平均化ブロック自体を算出せずに動きベクトルを求めるアルゴリズムを採用し、動きベクトルを探索するための演算回路の回路規模を小さくするとともに処理速度の向上を図ったものがある（例えば、特許文献１を参照）。この方法では、まず、一方の参照画像内で探索した類似ブロックの各画素データに１／２を乗じたものを、符号化対象ブロックから減算してテンプレートブロックを生成する。次に、他方の参照画像内のサーチウインドウに含まれる各ブロックに１／２を乗じて、各ブロックに対応した候補ブロックを生成する。次に、テンプレートブロックと各候補ブロックとの差分を正数データに変換し、さらに、ブロック単位で、前記の正数データの総和を求めることによって、平均化ブロックと類似ブロックとのディストーションを求める。そして、最小のディストーションに対応する候補ブロックに基づいて、動きベクトルを求める。
【特許文献１】特開平８−３２２０４９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、ＴＭ５のように、類似するブロック同士を平均化したからといっても、その平均化ブロックが最も符号化対象ブロックに類似しているとは限らない。
【００１０】
また、特許文献１に記載の方法は、前方参照画像及び後方参照画像のうちの何れか一方しか考慮されていないので、考慮されなかった方の参照画像内に最も類似するブロックが存在する可能性があり、やはり、求めたブロックが最も符号化対象ブロックに類似しているとは限らない。
【００１１】
すなわち、一般的には、求めたブロックと符号化対象ブロックとの類似度が低ければ低いほど、差分画像情報の符号化に要する情報量は大きくなるので、上記の符号化方法は、符号化に要する演算量の低減等には有効ではあるが、符号化効率は必ずしも良いとは言えないという問題を有していた。
【００１２】
本発明は、上記の問題に着目してなされたものであり、双方向予測符号化画像（いわゆるＢピクチャ）の符号化効率を向上させることが可能な動きベクトル探索方法及び動きベクトル探索装置を提供することを目的としている。
【課題を解決するための手段】
【００１３】
前記の課題を解決するため、本発明の一態様は、
第１の参照フレーム及び第２の参照フレームを含む２つ以上の参照フレームを用いて、動画像信号の動き補償フレーム間予測符号化を行なうにあたり、符号化対象フレームを構成する符号化対象ブロック毎に動きベクトルを探索する動きベクトル探索方法であって、
前記第１の参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索する第１の動きベクトル探索ステップと、
前記第２の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索する第２の動きベクトル探索ステップと、
前記第１の参照フレームから探索したブロックと前記第２の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなるように、前記第１の参照フレーム中のブロックと前記第２の参照フレーム中のブロックとの組合せを求め、求めた組み合わせに基づいて、動きベクトルの対を探索する第３の動きベクトル探索ステップと、
前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちの何れかを選択する動きベクトル選択ステップと、
を有することを特徴とする。
【００１４】
これにより、第１の参照フレームに対する探索、第２の参照フレームに対する探索、及び第１、第２の双方の参照フレームに対する探索の３種類の探索を行なった結果の中から最適なものを選択できるので、双方向予測符号化画像の符号化効率を向上させることが可能になる。
【００１５】
また、本発明の一態様は、
第１の参照フレーム及び第２の参照フレームを含む２つ以上の参照フレームを用いて、動画像信号の動き補償フレーム間予測符号化を行なうにあたり、符号化対象フレームを構成する符号化対象ブロック毎に動きベクトルを探索する動きベクトル探索方法であって、
前記第１の参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索する第１の動きベクトル探索ステップと、
前記第２の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索する第２の動きベクトル探索ステップと、
前記第１の参照フレームから探索したブロックと前記第２の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなるように、前記第１の参照フレーム中のブロックと前記第２の参照フレーム中のブロックとの組合せを求め、求めた組み合わせに基づいて、動きベクトルの対を探索する第３の動きベクトル探索ステップと、
前記第３の動きベクトル探索ステップの有効性を判定して、前記第３の動きベクトル探索ステップによる処理を行なうか否かを判定する判定ステップと、
前記第３の動きベクトル探索ステップによる処理が行なわれた場合には、前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちの何れかを選択し、前記第３の動きベクトル探索ステップによる処理が行なわれなかった場合には、前記第１の動きベクトル及び第２の動きベクトルのうちの一方を選択する動きベクトル選択ステップと、
を有することを特徴とする。
【００１６】
これにより、第１、第２の双方の参照フレームに対する探索の有効性が判断される。それゆえ、符号化効率を下げることなく演算量の削減や、消費電力の削減の達成が可能になる。
【００１７】
また、本発明の一態様は、
第１の参照フレーム及び第２の参照フレームを含む２つ以上の参照フレームを用いて、動画像信号の動き補償フレーム間予測符号化を行なうにあたり、符号化対象フレームを構成する符号化対象ブロック毎に動きベクトルを探索する動きベクトル探索方法であって、
第１の参照フレーム及び第２の参照フレームの何れか一方を選択する探索方向決定ステップと、
前記探索方向決定ステップで選択した参照フレームの中から探索したブロックに基づいて、第１の動きベクトルを探索する第１の動きベクトル探索ステップと、
前記探索方向決定ステップで選択されなかった他方の参照フレームの中から探索したブロックに基づいて、第２の動きベクトルを探索すると同時に、前記第１の動きベクトルと対応したブロックと前記他方の参照フレームから探索したブロックとの平均化ブロックと、前記符号化対象ブロックとの相関が最も高くなるように、前記他方の参照フレーム中のブロックを求め、求めたブロックに基づいて、第３の動きベクトルを探索し、前記第２及び第３の動きベクトルからなる動きベクトルの対を得る動きベクトル対探索ステップと、
前記第１〜第２の動きベクトル、及び前記動きベクトルの対のうちの何れかを選択する動きベクトル選択ステップと、
を有することを特徴とする。
【００１８】
これにより、第１及び第２の参照フレームのうちの何れか一方に対する探索（単方向の探索）と、第１、第２の双方の参照フレームに対する探索とが同時に行なわれる。それゆえ、演算量を削減することが可能になる。
【発明の効果】
【００１９】
本発明によれば、双方向予測符号化画像の符号化効率を向上させることが可能になる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の実施形態について図面を参照しながら説明する。
【００２１】
《発明の実施形態１》
図１は、本発明の実施形態１に係る動きベクトル探索方法を説明するためのフローチャートである。また、図２は、実施形態１における前方参照画像、符号化対象画像（符号化対象ブロック）、及び後方参照画像の関係を模式的に示す図である。図２において、符号化対象画像１０内の符号化対象ブロック１１が符号化するブロックである。
【００２２】
図１のフローチャートにおける各ステップの処理は、以下の通りである。
【００２３】
まず、Ｓ１０１（前方動きベクトル探索ステップ）では、前方参照画像２０における所定の前方探索範囲から、符号化対象ブロック１１に最も類似するブロックの探索を行ない、符号化対象ブロック１１と探索した最類似前方ブロックとの類似度ＳＡＤｆ、及び動きベクトルｖｅｃｆを求める。なお、ブロック同士の類似度の算出については、後に詳述する。
【００２４】
ここで、Ｓ１０１における最類似前方ブロックの探索は、例えば図３のフローチャートに示す手順で行なうことができる。なお、図３において、ｘとｙとは最類似ブロックの座標位置を保持する変数、ｍｉｎは最類似ブロックの類似度を保持する変数、ｉとｊとは探索範囲分だけ処理を繰り返すための水平方向と垂直方向のループカウンタ、ｓａｄは各探索点における類似度を一時保持する変数である。また、図３におけるｖ及びｈは、それぞれ、探索範囲の垂直方向及び水平方向の大きさを示す値である。
【００２５】
以下、図３に示す各ステップにおける処理を説明する。
【００２６】
Ｓ１０１−１（パラメータ初期化ステップ）
このステップでは、まず、ｘとｙを０に初期化し、ｍｉｎをＭＡＸに初期化し、ｊを−ｖに初期化している。ここで、ＭＡＸは、類似度として取りうる値の最大値である。本実施形態では、ブロック同士の類似度（ブロック類似度もしくは相関度とも呼ぶ）として、差分絶対値和（以下ＳＡＤ値と示す）を用いている。ＳＡＤ値は、値が小さい程、２つのブロックの類似度は高い。具体的にＳＡＤ値は、以下の式で表すことができる。
ＳＡＤ＝Σ｜ａ［ｊ］［ｉ］−ｂ［ｊ］［ｉ］｜
上式において、ａ［ｊ］［ｉ］及びｂ［ｊ］［ｉ］はそれぞれ、ブロック類似度を求める二つのブロックの画素値である。
【００２７】
Ｓ１０１−２（水平方向繰り返し回数初期化ステップ）
このステップでは、ｉを−ｈに初期化している。
【００２８】
Ｓ１０１−３（類似度演算ステップ）
このステップでは、探索点位置（ｉ，ｊ）で示される探索範囲内のブロックと、符号化対象ブロック１１とについてのＳＡＤ値の演算を行い、結果をｓａｄに格納する。
【００２９】
Ｓ１０１−４（最小類似度判定ステップ）
このステップでは、Ｓ１０１−３で求めたｓａｄとｍｉｎとの比較を行い、ｓａｄの方が小さければＳ１０１−５に進み、そうでなければＳ１０１−６に進む。
【００３０】
Ｓ１０１−５（最類似ブロック情報保持ステップ）
このステップでは、最類似ブロックの座標位置を保持変数ｘとｙに、それぞれｉ、ｊを格納し、さらにｍｉｎにｓａｄの値を格納する。
【００３１】
Ｓ１０１−６（水平方向繰り返し回数判定ステップ）
このステップでは、水平方向ループカウンタｉを１インクリメントし、ｉがｈ以下ならば、Ｓ１０１−３に進み、そうでなければ１０１−７に進む。
【００３２】
Ｓ１０１−７（垂直方向繰り返し回数判定ステップ）
このステップでは、垂直方向ループカウンタｊを１インクリメントし、ｊがｖ以下ならばＳ１０１−２に進み、そうでなければ処理を終了する。
【００３３】
Ｓ１０１−１〜Ｓ１０１−７の処理により、（−ｈ，−ｖ）、（−ｈ，ｖ）、（ｈ，−ｖ）、（ｈ，ｖ）の４点で示され、計（２ｈ＋１）×（２ｖ＋１）点の探索点を持つ探索範囲内から最小のＳＡＤ値を与えるブロックが探索される。この場合、ＳＡＤｆ＝ｍｉｎ、動きベクトルｖｅｃｆ＝（ｘ，ｙ）である。
【００３４】
次に、Ｓ１０２（後方動きベクトル探索ステップ）では、後方参照画像３０における所定の後方探索範囲内から符号化対象ブロック１１に最も類似するブロックの探索を行ない、動きベクトルｖｅｃｂと探索した最類似後方ブロックとの類似度ＳＡＤｂ、及び動きベクトルｖｅｃｂを求める。なお、Ｓ１０２における最類似後方ブロックの探索方法は、Ｓ１０１と同様である。
【００３５】
Ｓ１０３〜Ｓ１０５（これらのステップを合わせて、探索範囲設定ステップと呼ぶ）では、後述するＳ１０６（双方向動きベクトル探索ステップ）における探索範囲の設定を行なう。
【００３６】
具体的に、本実施形態の探索範囲設定ステップでは、Ｓ１０１とＳ１０２とで求めた類似度を比較し、類似度の高い方の動きベクトルを用いた探索範囲を、類似度の低い方の動きベクトルを用いて設定する探索範囲に比べて狭く設定する。
【００３７】
すなわち、Ｓ１０３（類似度比較ステップ）では、Ｓ１０１で求めたＳＡＤｆと、Ｓ１０２で求めたＳＡＤｂとを比較し、ＳＡＤｆがＳＡＤｂ以下ならば、Ｓ１０４へ進み、そうでなければＳ１０５へ進む。
【００３８】
Ｓ１０４（第１の双方向探索範囲設定ステップ）では、前方参照画像２０上に、後方探索範囲３１よりも狭い探索範囲（前方探索範囲２１）を設定する。また、Ｓ１０５（第２の双方向探索範囲設定ステップ）では、後方参照画像３０上に前方探索範囲２１よりも狭い探索範囲（後方探索範囲３１）を設定する。
【００３９】
図２では、Ｓ１０４が実行された場合の前方探索範囲２１と後方探索範囲３１とを例示している。この例では、動きベクトルｖｅｃｆで示される探索点位置２３を中心に９点の探索点を持つ前方探索範囲２１を設定し、動きベクトルｖｅｃｂで示される探索点位置３３を中心に２５点の探索点を持つ後方探索範囲３１を設定している。
【００４０】
この探索範囲の大きさの設定は、ＳＡＤ値が探索された動きベクトルの信頼度を表すものであり、信頼度が高い動きベクトルの周辺を探索する場合には探索範囲を狭く設定することが可能になるという原理に基づくものである。
【００４１】
Ｓ１０６（双方向動きベクトル探索ステップ）では、符号化対象ブロック１１に最も類似する平均化ブロックを生成するために、前方探索範囲２１と、後方探索範囲３１とのそれぞれから１つずつブロックを探索し、動きベクトル対（前方動きベクトルｖｅｃ１と後方動きベクトルｖｅｃ２）を求める。そして、動きベクトル対に対応する平均化ブロックと、符号化対象ブロック１１との類似度ＳＡＤｄを求める。最類似平均化ブロックを生成する２つのブロック（それぞれを前方ブロック、後方ブロックと呼ぶ）は、図２の例では、それぞれ最類似前方ブロック２２、最類似後方ブロック３２であるものとする。
【００４２】
ここで、Ｓ１０６における双方向最類似ブロックの探索は、例えば図４のフローチャートに示す手順で行なうことができる。なお、図４において、ｘｆとｙｆとは前方側の探索結果座標位置を保持する変数、ｘｂとｙｂとは後方側の探索結果座標位置を保持する変数、ｍｉｎは最類似ブロックにおける類似度を保持する変数、ｉとｊとは後方探索範囲分だけ処理を繰り返すための水平方向と垂直方向のループカウンタ、ｋとｌとは前方探索範囲分だけ処理を繰り返すための水平方向と垂直方向のループカウンタ、ｓａｄは各探索点における類似度を一時保持する変数である。
【００４３】
以下、図４に示す各ステップにおける処理を説明する。
【００４４】
Ｓ１０６−１（パラメータ初期化ステップ）
このステップでは、ｘｆとｙｆとｘｂとｙｂとをそれぞれ０に初期化し、ｍｉｎをＭＡＸに初期化し、ｌを−ｖｆに初期化している。ここで、ＭＡＸはＳＡＤ値として取りうる値の最大値である。また、ｖｆ及びｈｆは、前方探索範囲の垂直方向及び水平方向の大きさを示す値である。ｖｂ及びｈｂは、後方探索範囲の垂直方向及び水平方向の大きさを示す値である。
【００４５】
Ｓ１０６−２〜Ｓ１０６−４
Ｓ１０６−２〜Ｓ１０６−４においても変数の初期化を行なう。具体的に、Ｓ１０６−２（前方水平方向繰り返し回数初期化ステップ）では、ｋを−ｈｆに初期化している。また、Ｓ１０６−３（後方垂直方向繰り返し回数初期化ステップ）ではｊを−ｖｂに初期化している。Ｓ１０６−４（後方水平方向繰り返し回数初期化ステップ）ではｉを−ｈｂに初期化している。
【００４６】
Ｓ１０６−５（類似度演算ステップ）
このステップでは、前方参照画像２０内の探索点位置（ｋ，ｌ）で示される参照ブロックと後方参照画像３０内の探索点位置（ｉ，ｊ）で示される参照ブロックとから求めた平均化ブロックと、符号化対象ブロック１１とについてのＳＡＤ値演算を行い、その結果をｓａｄに格納する。
【００４７】
Ｓ１０６−６（最類似度判定ステップ）
このステップでは、ｓａｄとｍｉｎとの比較を行い、ｓａｄの方が小さければＳ１０６−７に進み、そうでなければＳ１０６−８に進む。
【００４８】
Ｓ１０６−７（最類似ブロック情報保持ステップ）
このステップでは、最類似ブロックを生成する２つの参照ブロックのうち、前方ブロックの座標位置としてｋ、ｌの値を保持変数ｘｆとｙｆに格納し、後方ブロックの座標位置としてｉ、ｊの値を保持変数ｘｂとｙｂに格納し、さらにｍｉｎにｓａｄの値を格納する。
【００４９】
Ｓ１０６−８（後方水平方向繰り返し回数判定ステップ）
このステップでは、ｉ（後方探索範囲の水平方向ループカウンタ）を１インクリメントし、ｉがｈｂ以下ならば、Ｓ１０６−５に進み、そうでなければＳ１０６−９に進む。
【００５０】
Ｓ１０６−９（後方垂直方向繰り返し回数判定ステップ）
このステップでは、ｊ（後方探索範囲の垂直方向ループカウンタ）を１インクリメントし、ｊがｖｂ以下ならばＳ１０６−４に進み、そうでなければＳ１０６−１０に進む。
【００５１】
Ｓ１０６−１０（前方水平方向繰り返し回数判定ステップ）
このステップでは、ｋ（前方探索範囲の水平方向ループカウンタ）を１インクリメントし、ｋがｈｆ以下ならばＳ１０６−３に進み、そうでなければＳ１０６−１１に進む。
【００５２】
Ｓ１０６−１１（前方垂直方向繰り返し回数判定ステップ）
このステップでは、ｌ（前方探索範囲の垂直方向ループカウンタ）を１インクリメントし、ｌがｖｆ以下ならばＳ１０６−２に進み、そうでなければ処理を終了する。
【００５３】
以上の処理により、（−ｈｆ，−ｖｆ）、（−ｈｆ，ｖｆ）、（ｈｆ，−ｖｆ）、（ｈｆ，ｖｆ）の４点で示される前方探索範囲内の探索点と、（−ｈｂ，−ｖｂ）、（−ｈｂ，ｖｂ）、（ｈｂ，−ｖｂ）、（ｈｂ，ｖｂ）の４点で示される後方探索範囲内の探索点との組み合わせ（計（２ｈｆ＋１）×（２ｖｆ＋１）×（２ｈｂ＋１）×（２ｖｂ＋１）個）の中から最小のＳＡＤ値を与える２つのブロックが探索される。この場合、ＳＡＤｄ＝ｍｉｎ、前方動きベクトルｖｅｃ１＝（ｘｆ，ｙｆ）、後方動きベクトルｖｅｃ２＝（ｘｂ，ｖｂ）である。
【００５４】
次に、Ｓ１０７（参照方式選択ステップ）では、Ｓ１０１、Ｓ１０２、及びＳ１０６で求めた各ＳＡＤ値の比較を行なう。そして、最小のＳＡＤ値に対応した参照方式を、符号化対象ブロック１１の参照方式として選択する。
【００５５】
上記のように、本実施形態によれば、前方参照、後方参照、及び双方向参照のそれぞれの探索を行ない、それらの参照方式の中から最適な参照方式を選択するので、Ｂピクチャの符号化効率の向上が可能になる。また、符号化効率が向上することによって、記録容量に余裕ができれば、それを他の画面の記録に使用できるので、その結果、画質向上が期待できる。
【００５６】
また、双方向参照では、前方参照と後方参照とにおける類似度（ＳＡＤ値）に応じて、前方側と後方側の探索範囲（探索点数）が決定されるので、探索点数を削減しつつ、効率的な双方向動きベクトル探索が可能になる。
【００５７】
《発明の実施形態２》
図５は、本発明の実施形態２に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、図５に示すように、実施形態１のフローチャート（図１）と比べ、探索範囲設定ステップにおける処理が異なっている。具体的には、新たなステップＳ２０１〜Ｓ２０４が追加されている。なお、以降の各実施形態の説明において、従前に説明したステップと同様の処理を行なうステップについては、同一のステップ番号を付して説明を省略する。
【００５８】
本実施形態の探索範囲設定ステップで、新たに設けられたステップでの処理は、以下の通りである。
【００５９】
Ｓ２０１（第１の類似度閾値判定ステップ）
このステップでは、類似度ＳＡＤｆを類似度閾値ＴＨｓ１と比較し、類似度閾値ＴＨｓ１以下ならばＳ２０３へ進み、そうでなければＳ１０４へ進む。
【００６０】
Ｓ２０２（第２の類似度閾値判定ステップ）
このステップでは、類似度ＳＡＤｂを類似度閾値ＴＨｓ１と比較し、類似度閾値ＴＨｓ１以下ならばＳ２０４へ進み、そうでなければＳ１０５へ進む。
【００６１】
Ｓ２０３（第１の双方向探索範囲設定ステップ）
このステップでは、前方探索範囲として１点を設定し、後方探索範囲として２２５点を設定する。したがって、Ｓ１０６では、前方側の動きベクトルの探索は行なわれず、前方動きベクトルｖｅｃ１＝動きベクトルｖｅｃｆとなる。一方、後方探索範囲は、Ｓ１０４における後方探索範囲と比べて広く設定している。この場合、ｈｆ＝ｖｆ＝１、ｈｂ＝ｖｂ＝１５である（ｈｆ等は、図４を参照）。
【００６２】
Ｓ２０４（第２の双方向探索範囲設定ステップ）
このステップにおいても同様に、後方探索範囲を１点に固定し、前方探索範囲をＳ１０５に比べ広く設定している。本実施形態では、前方探索範囲として２２５点を設定している。
【００６３】
探索範囲設定ステップによって、探索範囲が設定されると、Ｓ１０６で双方向参照が行なわれる。この際、探索範囲が１点である側（すなわち、探索結果の信頼度が高い動きベクトル側）は、その一点が平均化ブロックの生成に用いられる。
【００６４】
本実施形態における探索範囲設定ステップでは、前方参照と後方参照との何れが信頼できるかが、類似度に基づいてＳ１０３で判断された後、前方探索範囲と後方探索範囲が設定される。具体的には、信頼できる方の探索範囲の方が、他方の探索範囲よりも狭く設定される。この際、探索範囲の大きさは、類似度が大きいほど、狭い範囲に設定される。
【００６５】
上記のように、本実施形態によれば、前方参照での類似度と後方参照での類似度とに応じて、双方向参照での探索範囲が設定されるので、実施形態１の探索方法に比べて、効率的な探索が可能になる。
【００６６】
《発明の実施形態３》
図６は、本発明の実施形態３に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、図６に示すように、実施形態２のフローチャート（図５）と比べ、探索範囲設定ステップにおける処理が異なっている。具体的には、新たなステップとしてＳ３０１とＳ３０２とが追加されている。追加された各ステップでの処理は、以下の通りである。
【００６７】
Ｓ３０１（第１の類似度閾値修正ステップ）
このステップでは、時間軸距離Ｔｂの値に応じて、類似度閾値ＴＨｓ１の値を変動させて、Ｓ２０１へ進む。ここで、時間軸距離Ｔｂとは、符号化対象ピクチャと後方参照ピクチャとの時間軸距離を表している。例えば、Ｉピクチャ、Ｐピクチャ、及びＢピクチャの間に、図７のような参照関係があるとする。図７において、Ｉ０は、  Ｉピクチャ、Ｂ１、Ｂ２、Ｂ４、及びＢ５は、Ｂピクチャ、Ｐ３とＰ６とは、Ｐピクチャである。この場合には、ピクチャＢ１、Ｂ４では、Ｔｂ＝２であり、ピクチャＢ２、Ｂ５ではＴｂ＝１である。このステップでは、類似度閾値ＴＨｓ１の値は、後方参照ピクチャまでの時間軸距離が遠い程、探索範囲が広くなるように変動させる。
【００６８】
Ｓ３０２（第２の類似度閾値修正ステップ）
このステップでは、時間軸距離Ｔｆの値に応じて、類似度閾値ＴＨｓ１の値を変動させて、Ｓ２０２へ進む。ここで、時間軸距離Ｔｆとは、符号化対象ピクチャと前方参照ピクチャとの時間軸距離を表している。図７の例では、ピクチャＢ１、Ｂ４ではＴｆ＝１であり、ピクチャＢ２、Ｂ５ではＴｆ＝２である。このステップでは、類似度閾値ＴＨｓ１の値は、前方参照ピクチャまでの時間軸距離が遠い程、探索範囲が広くなるように変動させる。
【００６９】
次に、Ｓ３０１及びＳ３０２における類似度閾値ＴＨｓ１の変動のさせ方について、具体例を説明する。
【００７０】
例えば、２枚の参照ピクチャの間に、Ｂピクチャが３枚内挿されている場合には、それぞれのＢピクチャにおけるＴｂは、Ｔｂ＝１，２，３の何れかである。なお、本実施形態では、Ｔｂ＝２の場合に、後方探索範囲が最適となるように、類似度閾値ＴＨｓ１が初期設定されているものとする。
【００７１】
本実施形態では、Ｓ３０１が実行された場合に、Ｔｂ＝３であれば、符号化対象ピクチャと後方参照ピクチャの時間軸距離が、Ｔｂ＝２の場合よりも遠いので、後方探索範囲をより広く設定する。具体的に後方探索範囲を広く設定するには、類似度閾値ＴＨｓ１をより大きな値に変動させる。
【００７２】
また、Ｔｂ＝１の場合は、符号化対象ピクチャと後方参照ピクチャの時間軸距離が、Ｔｂ＝２の場合よりも近いので、後方探索範囲をそれほど広く設定しなくてもよい。そこで、類似度閾値ＴＨｓ１の値をより小さな値に変動させる。
【００７３】
以上説明したように、本実施形態によれば、双方向参照における探索範囲の大きさが、時間軸距離に応じて決定されるので、実施形態２の探索方法に比べて、更に効率的な双方向動きベクトル探索が可能になる。
【００７４】
なお、本実施形態の探索方法は、２枚の参照ピクチャの間のＢピクチャの数に関係なく適用できる。上記の例は、２枚の参照ピクチャの間にＢピクチャが３枚内挿されている例であったが、例えば５枚内挿されている場合には、Ｔｂ＝１の場合と、Ｔｂ＝２の場合とで類似度閾値ＴＨｓ１の値の下げ幅を変動させるようにすればよい。
【００７５】
《発明の実施形態４》
図８は、本発明の実施形態４に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、図８に示すように、実施形態３のフローチャート（図６）と比べ、探索範囲設定ステップにおける処理が異なっている。具体的には、Ｓ３０１がＳ４０１に置き換えられ、さらにＳ３０２がＳ４０２に置き換えられている。新たなステップでの処理は、以下の通りである。
【００７６】
Ｓ４０１（第１の類似度閾値修正ステップ）
このステップでは、後方参照方式個数Ｂｂの値（後述）に応じて、類似度閾値ＴＨｓ１の値を変動させ、Ｓ２０１へ進む。
【００７７】
ここで、後方参照方式個数Ｂｂは、符号化対象ブロックの周辺に位置する符号化済みのブロックのうち、後方参照により符号化されたブロック数である。このステップでは、後方参照方式個数Ｂｂが多いほど、後方探索範囲が狭く設定されるように類似度閾値ＴＨｓ１の値が変動させられる。
【００７８】
Ｓ４０２（第２の類似度閾値修正ステップ）
このステップでは、前方参照方式個数Ｂｆの値（後述）に応じて、類似度閾値ＴＨｓ１の値を変動させ、Ｓ２０２へ進む。
【００７９】
ここで、前方参照方式個数Ｂｆは、符号化対象ブロックの周辺に位置する符号化済みのブロックのうち、前方参照により符号化されたブロック数である。このステップでは、前方参照方式個数Ｂｆが多いほど、前方探索範囲が狭く設定されるように類似度閾値ＴＨｓ１の値が変動させられる。
【００８０】
図９は、符号化対象ブロック周辺の符号化済みブロックで選択された参照方式の一例を示す図である。図９の例では、Ｂｆ＝２、Ｂｂ＝１である。
【００８１】
次に、Ｓ４０１及びＳ４０２における類似度閾値ＴＨｓ１の変動のさせ方について、具体例を説明する。
【００８２】
例えば、符号化対象ブロックの周辺に位置する符号化済みブロックが４つある場合には、Ｂｂは、Ｂｂ＝０，１，２，３，４の何れかである。なお、本実施形態では、Ｂｂ＝２の場合に、後方探索範囲が最適となるように、類似度閾値ＴＨｓ１が初期設定されているものとする。
【００８３】
Ｓ４０１が実行される場合に、Ｂｂ＝０，１であれば、後方参照動きベクトルの信頼度が、Ｂｂ＝２の場合よりも低いため、後方探索範囲を広く設定する必要がある。具体的に後方探索範囲を広く設定するには、類似度閾値ＴＨｓ１をより大きな値に変動させる。
【００８４】
また、Ｂｂ＝３，４の場合は、後方参照動きベクトルの信頼度が、Ｂｂ＝２の場合よりも高いため、後方探索範囲をそれほど広く設定しなくてもよい。そこで、類似度閾値ＴＨｓ１をより小さな値に変動させる。
【００８５】
以上説明したように、本実施形態によれば、双方向参照における探索範囲の大きさが、符号化済みのブロックの参照方式に応じて決定されるので、実施形態２の探索方法に比べて、更に効率的な双方向動きベクトル探索が可能になる。
【００８６】
なお、本実施形態では、Ｂｂ＝０の場合とＢｂ＝１の場合とを同等に扱ったが、Ｂｂ＝０の場合とＢｂ＝１の場合とで類似度閾値ＴＨｓ１の値の上げ幅を変動させるようにしてもよい。
【００８７】
《発明の実施形態５》
図１０は、本発明の実施形態５に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、図１０に示すように、実施形態１のフローチャート（図１）と比べ、探索範囲設定ステップにおける処理が異なっている。具体的には、Ｓ１０３がＳ５０１に置き換えられている。新たなステップでの処理は、以下の通りである。
【００８８】
Ｓ５０１（時間軸距離比較ステップ）
このステップでは、時間軸距離Ｔｆと時間軸距離Ｔｂとの比較を行い、時間軸距離Ｔｆが時間軸距離Ｔｂ以下ならばＳ１０４へ進み、そうでなければＳ１０５へ進む。
【００８９】
すなわち、本実施形態では、双方向参照において、符号化対象ピクチャに対して時間軸距離がより近い方の参照ピクチャに、より狭い探索範囲を設定する。この探索範囲の設定は、時間軸距離が近ければ、物体の動く範囲は狭くなる傾向にあるという原理に基づくものである。
【００９０】
したがって、本実施形態においてもやはり、探索点数を削減しつつ、効率的な双方探索が可能になる。
【００９１】
《発明の実施形態６》
図１１は、本発明の実施形態６に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、図１１に示すように、実施形態２のフローチャート（図５）と比べ、探索範囲設定ステップにおける処理が異なっている。具体的には、Ｓ１０３がＳ５０１に置き換えられ、さらに、Ｓ２０１とＳ２０２とが、それぞれ、新たなステップＳ６０１とＳ６０２とに置き換えられている。新たなステップでの処理は、以下の通りである。
【００９２】
Ｓ６０１（第１の時間軸距離閾値判定ステップ）
このステップでは、時間軸距離Ｔｆを時間軸距離閾値ＴＨｔ１と比較し、時間軸距離Ｔｆが時間軸距離閾値ＴＨｔ１以下ならば、Ｓ２０３へ進み、そうでなければ、Ｓ１０４へ進む。
【００９３】
Ｓ６０２（第２の時間軸距離閾値判定ステップ）
このステップでは、時間軸距離Ｔｂを時間軸距離閾値ＴＨｔ１と比較し、時間軸距離Ｔｂが時間軸距離閾値ＴＨｔ１以下ならばＳ２０４へ進み、そうでなければ、Ｓ１０５へ進む。
【００９４】
すなわち、本実施形態では、双方向参照において、符号化対象ピクチャに対する時間軸距離がより近い方の参照ピクチャの探索範囲を、他方の参照ピクチャの探索範囲よりも狭く設定する。そして、探索範囲が狭い側の時間軸距離が、時間軸距離閾値ＴＨｔ１以下の場合には、探索範囲を１点のみに設定する（すなわち、探索範囲が狭い側の参照ピクチャ上での動きベクトルの探索を行なわない）。
【００９５】
これにより、本実施形態では、実施形態５の動きベクトル探索方法に比べて、更に効率的な双方向動きベクトル探索が可能になる。
【００９６】
《発明の実施形態７》
図１２は、本発明の実施形態７に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、図１２に示すように、実施形態１のフローチャート（図１）と比べ、探索範囲設定ステップにおける処理が異なっている。具体的には、Ｓ１０３（類似度比較ステップ）の代わりに、Ｓ７０１（参照方式個数比較ステップ）が設けられている。
【００９７】
ステップＳ７０１では、前方参照方式個数Ｂｆと後方参照方式個数Ｂｂとの比較を行い、ＢｆがＢｂ以上ならばＳ１０４へ進み、そうでなければＳ１０５へ進む。
【００９８】
すなわち、本実施形態では、双方向参照において、符号化対象ブロックの周辺に、後方参照方式よりも前方参照方式が採用されたブロック数の方が多い場合には、前方探索範囲を、後方探索範囲よりも狭くし、逆に、前方参照方式よりも後方参照方式が採用されたブロック数の方が多い場合には、後方探索範囲を、前方探索範囲よりも狭くする。
【００９９】
これは、周辺の符号化済みブロックで選択された回数が多い程、その参照方式による動きベクトルは、信頼度が高くなるという原理に基づいて、探索範囲を狭く設定するものである。
【０１００】
以上のように、本実施形態においても、探索点数を削減しつつ、効率的な双方向動きベクトル探索が可能になる。
【０１０１】
《発明の実施形態８》
図１３は、本発明の実施形態８に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、図１３に示すように、実施形態２のフローチャート（図５）と比べ、探索範囲設定ステップにおける処理が異なっている。具体的には、Ｓ１０３の代わりにＳ７０１（参照方式個数比較ステップ））を有し、Ｓ２０１（第１の類似度閾値判定ステップ）、及びＳ２０２（第２の類似度閾値判定ステップ）の代わりに、それぞれＳ８０１（第１の参照方式個数閾値判定ステップ）、Ｓ８０２（第２の参照方式個数閾値判定ステップ）を有している。新たなステップでの処理は、以下の通りである。
【０１０２】
Ｓ８０１（第１の参照方式個数閾値判定ステップ）
このステップでは、前方参照方式個数Ｂｆを参照方式個数用閾値ＴＨｍ１と比較し、ＴＨｍ１以上ならばＳ２０３へ進み、そうでなければＳ１０４へ進む。
【０１０３】
Ｓ８０２（第２の参照方式個数閾値判定ステップ）
このステップでは、後方参照方式個数Ｂｂを参照方式個数用閾値ＴＨｍ１と比較し、ＴＨｍ１以上ならばＳ２０４へ進み、そうでなければＳ１０５へ進む。
【０１０４】
すなわち、本実施形態では、双方向参照において、まず符号化対象ブロックの周辺で選択された参照方式の個数に応じ、前方及び後方の何れの探索範囲を狭くするかを決定する。そして、探索範囲が狭い側の参照方式の個数が、参照方式個数用閾値ＴＨｍ１以上の場合には、探索範囲を１点のみに設定する（すなわち、探索範囲が狭い側の参照ピクチャ上での動きベクトルの探索を行なわない）。
【０１０５】
これにより、本実施形態では、実施形態７の動きベクトル探索方法に比べて、更に効率的な双方向動きベクトル探索が可能になる。
【０１０６】
《発明の実施形態９》
図１４は、本発明の実施形態９に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態５のフローチャート（図１０）と比べ、探索範囲設定ステップにおける処理が異なっている。具体的には、本実施形態の探索範囲設定ステップは、図１４に示すように、Ｓ１０３、Ｓ１０４、Ｓ１０５、Ｓ５０１、Ｓ７０１、Ｓ９０１〜Ｓ９０４を有している。これらのうち、Ｓ９０１〜Ｓ９０４における処理は、以下のとおりである。
【０１０７】
Ｓ９０１（第１の類似度閾値判定ステップ）
このステップでは、類似度ＳＡＤｆを類似度閾値ＴＨｓ２と比較し、ＴＨｓ２以下ならばＳ１０４へ進み、そうでなければＳ５０１へ進む。
【０１０８】
Ｓ９０２（第２の類似度閾値判定ステップ）
このステップでは、類似度ＳＡＤｂを類似度閾値ＴＨｓ２と比較し、ＴＨｓ２以下ならばＳ１０５へ進み、そうでなければＳ５０１へ進む。
【０１０９】
Ｓ９０３（第１の時間軸距離閾値判定ステップ）
このステップでは、時間軸距離Ｔｆを時間軸距離閾値ＴＨｔ２と比較し、ＴＨｔ２以下ならばＳ１０４へ進み、そうでなければＳ７０１へ進む。
【０１１０】
Ｓ９０４（第２の時間軸距離閾値判定ステップ）
このステップでは、時間軸距離Ｔｂを時間軸距離閾値ＴＨｔ２と比較し、ＴＨｔ２以下ならばＳ１０５へ進み、そうでなければＳ７０１へ進む。
【０１１１】
すなわち、本実施形態では、まず、類似度と類似度閾値ＴＨｓ２とに基づいて、それぞれの探索範囲の大きさの決定を試み、決定できない場合には、時間軸距離と時間軸距離閾値ＴＨｔ２とに基づいて、それぞれの探索範囲の大きさの決定を試み、それでも決定できない場合には、周辺ブロックで選択された参照方式の個数に基づいて、それぞれの探索範囲の大きさを決定する。
【０１１２】
すなわち、本実施形態では、双方向動きベクトル探索において、単方向探索（前方動きベクトル探索、後方動きベクトル探索）の類似度、符号化対象ピクチャと参照画像との時間軸距離、及び符号化対象ブロックの周辺に位置するブロックで選択された参照方式の個数を併用して探索範囲を決定する。そのため、実施形態１、５、７の動きベクトル探索方法に比べて、更に効率的な双方向動きベクトル探索が可能になる。
【０１１３】
《発明の実施形態１０》
図１５は、本発明の実施形態１０に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態１のフローチャート（図１）と比べると、さらに、Ｓ１００１〜Ｓ１００３を有する点が異なる。Ｓ１００１〜Ｓ１００３における処理は、以下のとおりである。
【０１１４】
Ｓ１００１（類似度初期化ステップ）
このステップでは、類似度ＳＡＤｄを、ＳＡＤ値として取りうる最大値（ＭＡＸ）に初期化している。これは、Ｓ１００３にて双方向動きベクトル探索を行なわないと判定された時に、Ｓ１０７で誤ってＳＡＤｄが選択されることを防止するためである。
【０１１５】
Ｓ１００２（輝度総和値演算ステップ）
このステップでは、符号化対象ブロックを構成する画素の輝度総和Ｙｅ、Ｓ１０１で探索された動きベクトルｖｅｃｆの示す前方参照ブロックを構成する画素の輝度総和Ｙｆ、Ｓ１０２で探索された動きベクトルｖｅｃｂの示す後方参照ブロックを構成する画素の輝度総和Ｙｂを演算し、Ｓ１００３へ進む。
【０１１６】
Ｓ１００３（輝度総和値判定ステップ）
このステップでは、前記のＹｅ、Ｙｆ、Ｙｂを用いて、（Ｙｅ−Ｙｆ）×（Ｙｅ−Ｙｂ）を演算し、０と比較する。０よりも小さければＳ１０３へ進み、そうでなければ、Ｓ１０７へ進む。
【０１１７】
ここで、Ｓ１００３における処理の意味について説明する。Ｓ１００３に示される前記の式（Ｙｅ−Ｙｆ）×（Ｙｅ−Ｙｂ）が正の値になる場合は、Ｙｅ＞ＹｆかつＹｅ＞Ｙｂの場合か、Ｙｅ＜ＹｆかつＹｅ＜Ｙｆの場合である。
【０１１８】
この場合は、符号化対象ブロックの輝度総和Ｙｅが前方及び後方ブロック輝度総和ＹｆとＹｂの間の値とならないため、前方及び後方ブロックの周辺で双方向動きベクトル探索を行なっても、前方参照もしくは後方参照よりも最適な参照結果を得られる可能性が低い。したがって、この場合は、双方向動きベクトル探索を行なわず、Ｓ１０７（参照方式選択ステップ）へ進む。
【０１１９】
一方（Ｙｅ−Ｙｆ）×（Ｙｅ−Ｙｂ）が負の値の場合は、符号化対象ブロックの輝度総和Ｙｅが、輝度総和ＹｆとＹｂとの間の値となるので、双方向動きベクトル探索の結果が、前方参照もしくは後方参照よりも最適な参照結果となる可能性がある。したがって、この場合は、双方向動きベクトル探索を行なう。
【０１２０】
以上説明したように、本実施形態では、双方向参照の探索を行なう前に、符号化対象ブロック、前方の動きベクトルが示すブロック、及び後方の動きベクトルが示すブロックのそれぞれの画素レベル（上記の例では輝度総和）を比較することによって、双方向動きベクトル探索の有効性を調べ、有効な場合にのみ双方向動きベクトル探索を行なう。そのため、符号化効率を下げることなく演算量の削減や、消費電力の削減の達成が可能になる。
【０１２１】
なお、本実施形態においては、Ｓ１００２及びＳ１００３では、ブロック輝度総和を用いたが、ブロック輝度総和の代わりに、画素レベルとして色差情報を用いてもよい。
【０１２２】
《発明の実施形態１１》
図１６は、本発明の実施形態１１に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態１のフローチャート（図１）と比べると、さらに、Ｓ１００１、Ｓ１１０１、及びＳ１１０２を有する点が異なる。Ｓ１１０１及びＳ１１０２における処理は、以下のとおりである。
【０１２３】
Ｓ１１０１（第１の類似度閾値判定ステップ）
このステップでは、類似度ＳＡＤｆを類似度閾値ＴＨｓ３と比較し、ＴＨｓ３以下ならば、Ｓ１０７へ進み、そうでなければＳ１０４へ進む。
【０１２４】
Ｓ１１０２（第２の類似度閾値判定ステップ）
このステップでは、類似度ＳＡＤｂを類似度閾値ＴＨｓ３と比較し、ＴＨｓ３以下ならば、Ｓ１０７へ進み、そうでなければＳ１０５へ進む。
【０１２５】
上記のように、本実施形態では、Ｓ１１０１及びＳ１１０２において、Ｓ１０１、Ｓ１０２で行なわれた前方、後方動きベクトル探索で求めた類似度（ＳＡＤ値）のうち、小さい方の類似度が類似度閾値ＴＨｓ３以下ならば、双方向動きベクトル探索を行なわない。
【０１２６】
すなわち、本実施形態では、単方向の探索で十分良い参照結果が得られた場合には、双方向動きベクトル探索を行なわないので、符号化効率を下げることなく演算量の削減、消費電力の削減が可能になる。
【０１２７】
《発明の実施形態１２》
図１７は、本発明の実施形態１２に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態１１のフローチャート（図１６）と比べると、さらに、Ｓ１２０１とＳ１２０２とを有する点が異なる。Ｓ１２０１及びＳ１２０２における処理は、以下のとおりである。
【０１２８】
Ｓ１２０１（第１の類似度閾値修正ステップ）では、時間軸距離Ｔｂの値に応じて、類似度閾値ＴＨｓ３の値を変動させてＳ１１０１へ進む。
【０１２９】
Ｓ１２０２（第２の類似度閾値修正ステップ）では、時間軸距離Ｔｆの値に応じて、類似度閾値ＴＨｓ３の値を変動させてＳ１１０２へ進む。
【０１３０】
ここで、Ｓ１２０１とＳ１２０２とにおける類似度閾値ＴＨｓ３の変動方法について、２枚の参照ピクチャの間にＢピクチャが３枚内挿されており、Ｓ１２０１が実行された場合を例にとって説明する。この場合、それぞれのＢピクチャにおけるＴｂは、Ｔｂ＝１，２，３の何れかである。なお、本実施形態では、Ｔｂ＝２の場合に、探索範囲が最適となるように、類似度閾値ＴＨｓ３が初期設定されているものとする。
【０１３１】
例えば、Ｔｂ＝１の場合は、符号化ピクチャと後方参照ピクチャの時間軸距離が近いので、双方向動きベクトル探索を行なわなくてもよい可能性が高い。そのため、Ｔｂ＝１の場合は、ＴＨｓ３の値を大きな値に修正する。
【０１３２】
また、Ｔｂ＝３の場合は、符号化対象ピクチャと後方参照ピクチャとの時間軸距離が遠いので、双方向動きベクトル探索を行った方がよい可能性が高い。そこで、ＴＨｓ３の値を小さな値に修正する。
【０１３３】
以上説明したように、本実施形態では、双方向参照による探索を行なうかどうかを決定する閾値を、時間軸距離に応じて修正するので、実施形態１１の動きベクトル探索方法に比べて、更に効率的な双方向動きベクトル探索が可能になる。
【０１３４】
なお、本実施形態の探索方法は、２枚の参照ピクチャの間のＢピクチャの数に関係なく適用できる。上記の例は、２枚の参照ピクチャの間にＢピクチャが３枚内挿されている例であったが、例えば５枚内挿されている場合には、Ｔｂ＝１の場合と、Ｔｂ＝２の場合とで類似度閾値ＴＨｓ３の値の下げ幅を変動させるようにすればよい。
【０１３５】
《発明の実施形態１３》
図１８は、本発明の実施形態１３に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態１１のフローチャート（図１６）と比べると、Ｓ１２０１の代わりにＳ１３０１を有し、Ｓ１２０２の代わりにＳ１３０２を有する点が異なる。Ｓ１３０１及びＳ１３０２における処理は、以下のとおりである。
【０１３６】
Ｓ１３０１（第１の類似度閾値修正ステップ）では、後方参照方式個数Ｂｂの値に応じて、類似度閾値ＴＨｓ３の値を変動させてＳ１１０１へ進む。
【０１３７】
Ｓ１３０２（第２の類似度閾値修正ステップ）では、前方参照方式個数Ｂｆの値に応じて、類似度閾値ＴＨｓ３の値を変動させてＳ１１０２へ進む。
【０１３８】
ここで、Ｓ１３０１とＳ１３０２とにおける類似度閾値ＴＨｓ３の変動方法について、符号化対象ブロックの周辺に位置する符号化済みブロックが、図１０に示す４つであって、Ｓ１３０１が実行された場合を例にとって説明する。この場合、Ｂｂは、Ｂｂ＝０，１，２，３，４の何れかである。なお、本実施形態では、Ｂｂ＝２の場合に、探索範囲が最適となるように、類似度閾値ＴＨｓ３が初期設定されているものとする。
【０１３９】
例えば、Ｂｂ＝３，４の場合は、符号化対象ブロックの後方参照ベクトルの信頼度が高いので、双方向動きベクトル探索を行なわなくてもよい可能性が高い。そのため、Ｂｂ＝３，４の場合は、ＴＨｓ３を大きな値に修正する。
【０１４０】
また、Ｂｂ＝０，１の場合は、符号化対象ブロックの後方参照ベクトルの信頼度が低いので、双方向動きベクトル探索を行った方がよい可能性が高い。そのため、ＴＨｓ３を小さな値に修正する。
【０１４１】
以上説明したように、本実施形態では、双方向参照による探索を行なうかどうかを決定する閾値を、周辺ブロックの参照方式に応じて修正する。そのため、実施形態１１の動きベクトル探索方法に比べて、更に効率的な双方向動きベクトル探索が可能になる。
【０１４２】
なお、本実施形態においては、Ｂｂ＝０の場合とＢｂ＝１の場合とを同等として扱ったが、Ｂｂ＝０の場合とＢｂ＝１の場合とで、ＴＨｓ３の値の下げ幅を変動させるようにしてもよい。
【０１４３】
《発明の実施形態１４》
図１９は、本発明の実施形態１４に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態１１のフローチャート（図１６）と比べると、さらに、Ｓ１００２とＳ１４０１とが追加されている点が異なる。
【０１４４】
追加されたステップのうちＳ１４０１（類似度閾値修正ステップ）では、Ｓ１００２で演算されたＹｅ、Ｙｆ、Ｙｂの値を用いて閾値ＴＨｓ３の値を変動させてＳ１０３へ進む。
【０１４５】
ここで、Ｓ１４０１における類似度閾値ＴＨｓ３の変動方法について説明する。Ｓ１４０１では、実施形態１０と同様に、（Ｙｅ−Ｙｆ）×（Ｙｅ−Ｙｂ）が正の値か負の値かにより閾値の変動を行う。
【０１４６】
例えば、正の値の場合には、双方向参照によって、前方参照もしくは後方参照よりも最適な参照結果を得られる可能性が低い。したがって、ＴＨｓ３の値を大きな値に修正する。
【０１４７】
また、負の値の場合には、双方向参照によって、前方参照もしくは後方参照によりも最適な参照結果を得られる可能性が高い。したがって、ＴＨｓ３の値を小さな値に修正する。
【０１４８】
以上説明したように、本実施形態では、双方向参照による探索を行なうかどうかを決定する閾値を、輝度総和に応じて修正するので、実施形態１１の動きベクトル探索方法に比べて、更に効率的な双方向動きベクトル探索が可能になる。
【０１４９】
なお、本実施形態においては、（Ｙｅ−Ｙｆ）×（Ｙｅ−Ｙｂ）が正か負かという情報のみ用いて閾値を変動させたが、（Ｙｅ−Ｙｆ）×（Ｙｅ−Ｙｂ）の絶対値情報を用いて、ＴＨｓ３の修正幅を変動させるようにしてもよい。
【０１５０】
《発明の実施形態１５》
図２０は、本発明の実施形態１５に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態１１のフローチャート（図１６）と比べると、Ｓ１０３の代わりにＳ５０１を有し、Ｓ１１０１の代わりにＳ１５０１を有し、Ｓ１１０２の代わりにＳ１５０２を有する点が異なる。Ｓ１５０１及びＳ１５０２における処理は、以下のとおりである。
【０１５１】
Ｓ１５０１（第１の時間軸距離閾値判定ステップ）では、時間軸距離Ｔｆを時間軸距離閾値ＴＨｔ３と比較し、ＴＨｔ３以下ならばＳ１０７へ進み、そうでなければＳ１０４へ進む。
【０１５２】
Ｓ１５０２（第２の時間軸距離閾値判定ステップ）では、時間軸距離Ｔｂを時間軸距離閾値ＴＨｔ３と比較し、ＴＨｔ３以下ならばＳ１０７へ進み、そうでなければＳ１０５へ進む。
【０１５３】
上記のＳ１５０１及びＳ１５０２では、前方参照画像までの時間軸距離と後方参照画像までの時間軸距離のうち、近い方の時間軸距離を時間軸距離閾値ＴＨｔ３と比較して、ＴＨｔ３以下ならば、双方向動きベクトル探索を行なわない。すなわち、参照画像との時間軸距離が十分近ければ、Ｂピクチャにおける参照方式を、時間軸距離の近い参照ピクチャへの単方向探索を行ない、双方向動きベクトル探索処理を行わないということである。したがって、本実施形態では、符号化効率を下げることなく演算量の削減、消費電力の削減が可能になる。
【０１５４】
《発明の実施形態１６》
図２１は、本発明の実施形態１６に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態１１のフローチャート（図１６）と比べると、Ｓ１０３の代わりにＳ７０１を有し、Ｓ１１０１の代わりにＳ１６０１を有し、Ｓ１１０２の代わりにＳ１６０２を有する点が異なる。Ｓ１６０１及びＳ１６０２における処理は、以下のとおりである。
【０１５５】
Ｓ１６０１（第１の参照方式個数閾値判定ステップ）では、前方参照方式個数Ｂｆを参照方式個数用閾値ＴＨｍ２と比較し、ＴＨｍ２よりも小さければＳ１０４へ進み、そうでなければＳ１０７へ進む。
【０１５６】
Ｓ１６０２（第２の参照方式個数閾値判定ステップ）では、後方参照方式個数Ｂｂを参照方式個数用閾値ＴＨｍ２と比較し、ＴＨｍ２よりも小さければＳ１０５へ進み、そうでなければＳ１０７へ進む。
【０１５７】
上記のＳ１６０１及びＳ１６０２では、符号化対象ブロックの周辺に位置する符号化済みブロックにおいて、前方参照により符号化されたブロックの個数と後方参照により符号化されたブロックの個数とを求める。そして、前方参照により符号化されたブロックの個数と、後方参照により符号化されたブロックの個数のうちの、多い方の個数を閾値と比較して、閾値以上ならば双方向動きベクトル探索を行わない。すなわち、周辺ブロックの参照方式が前方参照方式、もしくは後方参照方式の何れかに十分偏っていたら、双方向動きベクトル探索処理を行わないということである。これにより、本実施形態では、符号化効率を下げることなく演算量の削減、消費電力の削減の達成が可能になる。
【０１５８】
《発明の実施形態１７》
図２２は、本発明の実施形態１７に係る動きベクトル探索方法を説明するためのフローチャートである。
【０１５９】
まず、Ｓ１７０１（優先探索方向決定ステップ）では、時間軸距離Ｔｆと時間軸距離Ｔｂとを比較し、距離の近い方の参照ピクチャを優先探索画像に決定する。
【０１６０】
Ｓ１７０２（優先方向動きベクトル探索ステップ）では、Ｓ１７０１で決定された優先探索画像上のある探索範囲内から符号化ブロックに最も類似するブロックの探索を行ない、動きベクトルｖｅｃｐと最小のＳＡＤ値（ＳＡＤｐ）を求める。本ステップにおける処理は、具体的には、図３のフローチャートに示した処理と同じである。
【０１６１】
Ｓ１７０３（非優先方向・双方向動きベクトル同時探索ステップ）では、Ｓ１７０１にて優先探索画像と決定されなかった方の参照ピクチャ（非優先探索画像と呼ぶ）上におけるある探索範囲内から、符号化対象ブロックに最も類似するブロックの探索を行なう処理と、双方向動きベクトル探索処理とを同時に行なう（これらの探索処理（同時探索）については後に詳述する）。これにより、非優先探索画像上の探索結果として、動きベクトルｖｅｃｓを得て、最小ＳＡＤ値としてＳＡＤｓを得て、さらに、双方向動きベクトル探索の結果として、動きベクトルｖｅｃｄを得て、最小ＳＡＤ値としてＳＡＤｄを得る。
【０１６２】
次に、Ｓ１７０４では、Ｓ１７０２、Ｓ１７０３で求めた、それぞれの参照方式における最小ＳＡＤ値の比較を行い、最小のものを選択することによって、符号化対象ブロックの参照方式の選択を行なう。
【０１６３】
ここで、Ｓ１７０３における同時探索について説明する。図２３は、Ｓ１７０３における同時探索を説明するためのフローチャートである。
【０１６４】
なお、図２３において、ｘｓとｙｓとは、非優先探索画像における最類似ブロックの座標位置を保持する変数、ｘｄとｙｄとは、双方向動きベクトル探索における最類似ブロックを生成する非優先側ブロックの座標位置を保持する変数、ｍｉｎｓは、非優先探索画像における最類似ブロックの類似度を保持する変数、ｍｉｎｄは、双方向動きベクトル探索における最類似ブロックの類似度を保持する変数、ｉとｊとは探索範囲分だけ処理を繰り返すための水平方向と垂直方向のループカウンタ、ｓａｄは、各探索点における類似度を一時保持する変数である。
【０１６５】
以下、各ステップにおける処理を説明する。
【０１６６】
Ｓ１７０３−１（パラメータ初期化ステップ）
このステップでは、ｘｓとｙｓ、ｘｄとｙｄを０に初期化し、ｍｉｎｓとｍｉｎｄをＭＡＸに初期化し、ｊを−ｖに初期化している。ここで、ＭＡＸはＳＡＤ値として取りうる最大値であり、ｊは探索範囲の垂直方向の大きさを示す値である。また、ｈは探索範囲の水平方向の大きさを示す値である。
【０１６７】
Ｓ１７０３−２（水平方向繰り返し回数初期化ステップ）
このステップでは、ｉを−ｈに初期化している。
【０１６８】
Ｓ１７０３−３（単方向類似度演算ステップ）
このステップでは、探索点位置（ｉ，ｊ）で示される参照ブロックと符号化ブロックとのＳＡＤ値演算を行い、結果をｓａｄに格納する。本ステップの処理は、参照ブロックとして、非優先探索画像内のブロックを用いるということ以外は、実施形態１で説明したＳ１０１−３（類似度演算ステップ）と同処理である。
【０１６９】
Ｓ１７０３−４（単方向最類似判定ステップ）
このステップでは、Ｓ１７０３−３で求めたｓａｄと、これまでに探索された中で最小のＳＡＤ値が保持されているｍｉｎｓとの比較を行い、ｓａｄの方が小さければＳ１７０３−５に進み、そうでなければＳ１７０３−６に進む。
【０１７０】
Ｓ１７０３−５（単方向最類似ブロック情報保持ステップ）
このステップでは、ｘｓ、ｙｓ、及びｍｉｎｓに、それぞれｉ、ｊ、及びｓａｄの値を格納する。
【０１７１】
Ｓ１７０３−６（双方向類似度演算ステップ）
このステップでは、優先探索画像側の動きベクトル探索により得られた最類似ブロック、及び非優先画像における探索点位置（ｉ，ｊ）で示される参照ブロックから求めた平均化ブロックと、符号化対象ブロックとのＳＡＤ値演算を行い、結果をｓａｄに格納する。
【０１７２】
なお、本ステップの処理は、平均化ブロックを求める際に、優先探索画像側のブロックは、常にＳ１７０２で求めた最類似ブロックを使用するということ以外は、図４のフローチャートで示したＳ１０６−５と同処理である。
【０１７３】
Ｓ１７０３−７（双方向類似度判定ステップ）
このステップでは、ｓａｄに格納されているＳＡＤ値と、ｍｉｎｄに保持されているＳＡＤ値との比較を行い、ｓａｄの方が小さければＳ１７０３−８に進み、そうでなければＳ１７０３−９に進む。
【０１７４】
Ｓ１７０３−８（双方向最類似ブロック情報保持ステップ）
このステップでは、ｘｄ、ｙｄ、及びｍｉｎｄに、それぞれｉ、ｊ、及びｓａｄの値を格納する。
【０１７５】
Ｓ１７０３−９（水平方向繰り返し回数判定ステップ）
このステップでは、水平方向ループカウンタｉを１インクリメントし、ｉがｈ以下ならば、Ｓ１７０３−３に進み、そうでなければＳ１７０３−１０に進む。
【０１７６】
Ｓ１７０３−１０（垂直方向繰り返し回数判定ステップ）
このステップでは、垂直方向ループカウンタｊを１インクリメントし、ｊがｖ以下ならばＳ１７０３−２に進み、そうでなければ処理を終了する。
【０１７７】
上記のように本実施形態では、平均化ブロックを求める際に、優先探索画像側のブロックは、常にＳ１７０２で求めた最類似ブロックを使用するので、双方向参照における探索範囲と非優先画像側の探索範囲とを同じにすることができる。この場合の探索範囲は、（−ｈ，−ｖ）、（−ｈ，ｖ）、（ｈ，−ｖ）、（ｈ，ｖ）の４点で示される探索範囲である。すなわち、本実施形態では、非優先探索画像における動きベクトル探索と、双方向動きベクトル探索とを同時に行なうことができ、ＳＡＤｓ＝ｍｉｎｓ、ｖｅｃｓ＝（ｘｓ，ｙｓ）、ＳＡＤｄ＝ｍｉｎｄ、ｖｅｃｄ＝（ｘｄ，ｙｄ）である。
【０１７８】
以上説明したように、本実施形態では、優先探索画像と非優先探索画像とを決めて、非優先探索と双方向動きベクトル探索とを同時に行なう。そのため、双方向動きベクトル探索と単方向探索とを別々に行なう場合と比べ、演算量の削減が可能になる。
【０１７９】
また、双方向動きベクトル探索と単方向探索とを同時に行なうことによって、二つの探索に共通に用いる参照ブロックデータの読み出しが一度で済むので、メモリへのアクセス回数を低減する効果もある。なお、優先探索画像の決定は、時間軸距離情報を用いるので、容易に行なうことが可能になる。
【０１８０】
《発明の実施形態１８》
図２４は、本発明の実施形態１８に係る動きベクトル探索方法を説明するためのフローチャートである。この動きベクトル探索方法は、実施形態１７のフローチャート（図２２）と比べると、Ｓ１７０１の代わりにＳ１８０１を有する点が異なる。
【０１８１】
Ｓ１８０１（優先探索方向決定ステップ）では、符号化対象ブロックの周辺に位置する符号化済みブロックのうち、前方参照を用いて符号化されたブロックの個数（前方参照方式個数Ｂｆ）と後方参照を用いて符号化されたブロックの個数（後方参照方式個数Ｂｂ）とを比較し、数の多い方の参照ピクチャを優先探索方向に決定する。
【０１８２】
したがって、本実施形態においても、優先探索画像の決定を容易に行なうことが可能になる。なお、本実施形態も、双方向動きベクトル探索と単方向探索とを別々に行なう場合と比べ、演算量を削減することができ、また、メモリへのアクセス回数を低減するという効果も有している。
【０１８３】
《発明の実施形態１９》
図２５は、本発明の実施形態１９に係る動きベクトル探索装置１００の構成を示すブロック図である。動きベクトル探索装置１００は、実施形態１に係る動きベクトル探索方法を実現する装置の構成例である。
【０１８４】
図２５に示すように、動きベクトル探索装置１００は、画像記憶部１０１、前方動きベクトル探索部１０２、後方動きベクトル探索部１０３、探索範囲設定部１０４、動きベクトル対探索部１０５、参照方式選択部１０６、周波数分解部１０７、量子化部１０８、画像復号部１０９、及び画像記憶部１１０を備えている。
【０１８５】
画像記憶部１０１は、入力された動画像信号を記憶するようになっている。具体的には、符号化対象画像１０を記憶する。
【０１８６】
前方動きベクトル探索部１０２は、前方参照画像２０（後述するように画像記憶部１１０に格納されている）に設定された所定の前方探索範囲内から、符号化対象ブロック１１に最も類似するブロックの探索を行ない、符号化対象ブロック１１と探索した最類似前方ブロック２２との類似度ＳＡＤｆ、及び動きベクトルｖｅｃｆを求めるようになっている。
【０１８７】
後方動きベクトル探索部１０３は、後方参照画像３０（後述するように画像記憶部１１０に格納されている）における所定の後方探索範囲内から符号化対象ブロック１１に最も類似するブロックの探索を行ない、符号化対象ブロック１１と探索した最類似後方ブロックとの類似度ＳＡＤｂ、及び動きベクトルｖｅｃｂを求めるようになっている。  
【０１８８】
探索範囲設定部１０４は、前方探索範囲２１及び後方探索範囲３１を設定するようになっている。詳しくは、前方動きベクトル探索部１０２と後方動きベクトル探索部１０３とによって求めた類似度を比較し、類似度の大きい方の参照画像の探索範囲を、他方の参照画像の探索範囲よりも狭く設定する。
【０１８９】
動きベクトル対探索部１０５は、前方探索範囲２１と、後方探索範囲３１とのそれぞれから１つずつブロックを探索し、動きベクトル対（前方動きベクトルｖｅｃ１と後方動きベクトルｖｅｃ２）を求めるとともに、動きベクトル対に対応する平均化ブロックと、符号化対象ブロック１１との類似度ＳＡＤｄを求めるようになっている。
【０１９０】
参照方式選択部１０６は、前方動きベクトル探索部１０２、後方動きベクトル探索部１０３、及び動きベクトル対探索部１０５で求めた類似度を比較し、符号化に用いる参照方式を選択するとともに、その参照方式に対応した動きベクトルと差分ブロックとを出力するようになっている。
【０１９１】
周波数分解部１０７は、参照方式選択部１０６の出力を直交変換するようになっている
量子化部１０８は、周波数分解部１０７の出力を量子化するとともに、ストリーム端子と画像復号部１０９とに出力するようになっている。
【０１９２】
画像復号部１０９は、参照方式選択部１０６の出力の復号化と、量子化部１０８の出力の復号化を行なうようになっている。
【０１９３】
画像記憶部１１０は、前方及び後方の参照画像を格納するようになっている。
【０１９４】
上記の動きベクトル探索装置１００では、まず前方参照画像及び後方参照画像が画像記憶部１１０に格納された状態で、双方向参照による符号化を開始する。この場合、まず前方動きベクトル探索部１０２、及び後方動きベクトル探索部１０３によって、それぞれ前方動きベクトル探索、及び後方動きベクトル探索が行なわれ、参照方式ごとに類似度と動きベクトルが求められる。
【０１９５】
前方及び後方方式の類似度が求められると、探索範囲設定部１０４は、前方探索範囲と後方探索範囲とを設定し、動きベクトル対探索部１０５は、動きベクトル対と類似度を求める。次に、参照方式選択部１０６は、前方動きベクトル探索部１０２、後方動きベクトル探索部１０３、及び動きベクトル対探索部１０５がそれぞれ求めた類似度を比較して、符号化に用いる参照方式を選択する。さらに、参照方式選択部１０６は、その参照方式に対応した動きベクトルと差分ブロックとを周波数分解部１０７に出力する。参照方式選択部１０６の出力は、周波数分解部１０７と量子化部１０８とによって符号化されて出力される。
【０１９６】
《発明の実施形態２０》
図２６は、本発明の実施形態２０に係る動きベクトル探索装置２００の構成を示すブロック図である。動きベクトル探索装置２００は、実施形態１７に係る動きベクトル探索方法を実現する装置の構成例である。なお、以下の説明では、前記の実施形態１９で一度説明した構成要素と同様の機能を有する構成要素については、同一の符号を付して説明を省略する。
【０１９７】
図２６に示すように、動きベクトル探索装置２００は、画像記憶部１０１、参照方式選択部１０６、周波数分解部１０７、量子化部１０８、画像復号部１０９、画像記憶部１１０、優先探索方向決定部２０１、動きベクトル探索部２０２、及び動きベクトル対探索部２０３を備えている。
【０１９８】
優先探索方向決定部２０１は、画像記憶部１１０に格納されている前方参照画像及び後方参照画像のうち、符号化対象ピクチャに対する時間軸距離の近い方の参照ピクチャを選択して動きベクトル探索部２０２に出力するようになっている。
【０１９９】
動きベクトル探索部２０２は、優先探索方向決定部２０１が出力した参照ピクチャ上に設定された探索範囲内から、符号化対象ブロックに最も類似するブロック（最類似ブロック）の探索を行ない、符号化対象ブロックと最類似ブロックとの類似度、及び動きベクトルを求めるようになっている。
【０２００】
動きベクトル対探索部２０３は、優先探索方向決定部２０１で選択されなかった方の参照ピクチャ（非優先探索画像）上におけるある探索範囲内から、符号化対象ブロックに最も類似するブロックの探索を行なう処理と、双方向動きベクトル探索処理とを同時に行なうことによって、非優先探索画像上の探索結果としての動きベクトルと類似度、さらに、双方向動きベクトル探索の結果としての動きベクトルと類似度を得るようになっている。なお、双方向動きベクトル探索処理を行なう場合は、動きベクトル探索部２０２が求めた最類似ブロックを一方の探索対象とする。
【０２０１】
上記の動き動きベクトル探索装置２００では、まず前方参照画像及び後方参照画像が画像記憶部１１０に格納された状態で、双方向参照による符号化を開始する。この場合、まず優先探索方向決定部２０１は、符号化対象ピクチャとの時間軸距離が近い方の参照ピクチャを選択して動きベクトル探索部２０２に出力する。動きベクトル探索部２０２は、画像記憶部１０１に格納されている画像と、優先探索方向決定部２０１が出力した画像とを用いて、類似度と動きベクトルを求める。
【０２０２】
一方、動きベクトル対探索部２０３は、非優先探索画像上に設定された探索範囲内から、符号化対象ブロックに最も類似するブロックの探索を行なうと同時に、双方向動きベクトル探索処理とを行なう。これにより、非優先探索画像上の探索結果としての動きベクトルと類似度、さらに、双方向動きベクトル探索の結果としての動きベクトルと類似度が得られる。
【０２０３】
次に、参照方式選択部１０６は、動きベクトル探索部２０２と動きベクトル対探索部２０３とがそれぞれ求めた類似度を比較して、符号化に用いる参照方式を選択する。さらに、参照方式選択部１０６は、その参照方式に対応した動きベクトルと差分ブロックとを周波数分解部１０７に出力する。参照方式選択部１０６の出力は、周波数分解部１０７と量子化部１０８とによって符号化されて出力される。
【０２０４】
なお、上記の各実施形態では、類似度としてＳＡＤ値を用いたがこれには限定されない。例えば、その他にも差分二乗和等を用いても構わない。また、ＳＡＤ値の演算では、演算量削減のために、ＳＡＤ値演算に用いる画素を間引いたり、符号化対象ブロックと参照画像とを縮小したりしてＳＡＤ値を演算してもよい。
【０２０５】
また、前方側と後方側の探索範囲の大きさ（探索点数）は例示である。
【０２０６】
また、Ｓ１０１やＳ１０５における探索範囲は、（−ｈ，−ｖ）、（−ｈ，ｖ）、（ｈ，−ｖ）、（ｈ，ｖ）の４点で示される探索範囲に設定したが、探索範囲の設定の仕方はこれには限定されない。
【０２０７】
また、上記の各実施形態は、ＭＰＥＧ２等で採用されている、２枚の参照画像が過去と未来のピクチャであるＢピクチャの場合の例であるが、例えばＨ．２６４等に採用されている、２枚の参照画像を、符号化ピクチャよりも過去の画像と未来の画像に限定しない、双予測ピクチャの動きベクトル探索にも応用することができる。
【０２０８】
また、各実施形態に係る動きベクトル探索方法は、ソフトウエアとして実装しても良いし、実施形態１９や２０で説明したように、ハードウェアによる実装でも同等の効果を得ることが可能である。
【産業上の利用可能性】
【０２０９】
本発明に係る動きベクトル探索方法及び動きベクトル探索装置は、双方向予測符号化画像の符号化効率を向上させることが可能になるという効果を有し、デジタル動画像データの圧縮に用いられる動きベクトル探索方法及び前記動きベクトル探索を行なう動きベクトル探索装置等として有用である。
【図面の簡単な説明】
【０２１０】
【図１】本発明の実施形態１に係る動きベクトル探索方法を説明するためのフローチャートである。
【図２】実施形態１における前方参照画像、符号化対象ブロック、及び後方参照画像の関係を模式的に示す図である。
【図３】最類似前方ブロックの探索手順の一例を示すフローチャートである。
【図４】双方向最類似ブロックの探索手順の一例を示すフローチャートである。
【図５】本発明の実施形態２に係る動きベクトル探索方法を説明するためのフローチャートである。
【図６】本発明の実施形態３に係る動きベクトル探索方法を説明するためのフローチャートである。
【図７】Ｉピクチャ、Ｐピクチャ、及びＢピクチャの間の参照関係の一例を示す図である。
【図８】本発明の実施形態４に係る動きベクトル探索方法を説明するためのフローチャートである。
【図９】符号化対象ブロック周辺の符号化済みブロックで選択された参照方式の一例を示す図である。
【図１０】本発明の実施形態５に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１１】本発明の実施形態６に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１２】本発明の実施形態７に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１３】本発明の実施形態８に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１４】本発明の実施形態９に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１５】本発明の実施形態１０に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１６】本発明の実施形態１１に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１７】本発明の実施形態１２に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１８】本発明の実施形態１３に係る動きベクトル探索方法を説明するためのフローチャートである。
【図１９】本発明の実施形態１４に係る動きベクトル探索方法を説明するためのフローチャートである。
【図２０】本発明の実施形態１５に係る動きベクトル探索方法を説明するためのフローチャートである。
【図２１】本発明の実施形態１６に係る動きベクトル探索方法を説明するためのフローチャートである。
【図２２】本発明の実施形態１７に係る動きベクトル探索方法を説明するためのフローチャートである。
【図２３】単方向探索と双方向動きベクトル探索との同時探索を説明するためのフローチャートである。
【図２４】本発明の実施形態１８に係る動きベクトル探索方法を説明するためのフローチャートである。
【図２５】本発明の実施形態１９に係る動きベクトル探索装置の構成を示すブロック図である。
【図２６】本発明の実施形態２０に係る動きベクトル探索装置の構成を示すブロック図である。
【符号の説明】
【０２１１】
１０      符号化対象画像
１１      符号化対象ブロック
２０      前方参照画像
２１      前方探索範囲
２２      最類似前方ブロック
２３      探索点位置
３０      後方参照画像
３１      後方探索範囲
３２      最類似後方ブロック
３３      探索点位置
１００      動きベクトル探索装置
１０１      画像記憶部
１０２      前方動きベクトル探索部
１０３      後方動きベクトル探索部
１０４      探索範囲設定部
１０５      動きベクトル対探索部
１０６      参照方式選択部
１０７      周波数分解部
１０８      量子化部
１０９      画像復号部
１１０      画像記憶部
２００      動きベクトル探索装置
２０１      優先探索方向決定部
２０２      動きベクトル探索部
２０３      動きベクトル対探索部
【図１】
2008011158.tif 000003
【図２】
2008011158.tif 000004
【図３】
2008011158.tif 000005
【図４】
2008011158.tif 000006
【図５】
2008011158.tif 000007
【図６】
2008011158.tif 000008
【図７】
2008011158.tif 000009
【図８】
2008011158.tif 000010
【図９】
2008011158.tif 000011
【図１０】
2008011158.tif 000012
【図１１】
2008011158.tif 000013
【図１２】
2008011158.tif 000014
【図１３】
2008011158.tif 000015
【図１４】
2008011158.tif 000016
【図１５】
2008011158.tif 000017
【図１６】
2008011158.tif 000018
【図１７】
2008011158.tif 000019
【図１８】
2008011158.tif 000020
【図１９】
2008011158.tif 000021
【図２０】
2008011158.tif 000022
【図２１】
2008011158.tif 000023
【図２２】
2008011158.tif 000024
【図２３】
2008011158.tif 000025
【図２４】
2008011158.tif 000026
【図２５】
2008011158.tif 000027
【図２６】
2008011158.tif 000028