【手続補正書】
【提出日】平成19年10月11日(2007.10.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する動き補償予測符号化装置において、
前記第二ブロックの各々について、所定の探索アルゴリズムを予め定められた第１の反復数以下の少ない反復で動きベクトルを演算する第一動きベクトル演算手段と、
この第一動きベクトル演算手段によって演算された各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定手段と、
この第一判定手段による判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックを動き補償予測ブロックとして選択するよう制御する第一選択制御手段と
を備えたことを特徴とする動き補償予測符号化装置。
【請求項２】
前記第一判定手段による判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックについて、前記所定の探索アルゴリズムにより予め定められた第２の反復数を上限として動きベクトルを演算する第二動きベクトル演算手段と、
前記第一判定手段による判定の結果、完全等価又は近似等価でないと判定した場合に、前記第二ブロックの各々について、所定の探索アルゴリズムにより予め定められた第３の反復数を上限として動きベクトルを演算する第三動きベクトル演算手段と、
この第三動きベクトル演算手段で演算された各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第二判定手段と、
前記第二判定手段による判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックを動き補償予測ブロックとして選択するよう制御する一方、前記第二判定手段による判定の結果、完全等価又は近似等価でないと判定した場合に、前記第二ブロックを動き補償予測ブロックとして選択するよう制御する第二選択制御手段と
を更に備えたことを特徴とする請求項１記載の動き補償予測符号化装置。
【請求項３】
前記第二動きベクトル演算手段及び前記第三動きベクトル演算手段は、前記第一動きベクトル演算手段が前記所定の探索アルゴリズムをｎ′回反復した場合には、このｎ′回反復した結果得られた中間値を初期値としてｎ′＋１回目から前記所定の探索アルゴリズムによる反復を開始することを特徴とする請求項２記載の動き補償予測符号化装置。
【請求項４】
前記所定の探索アルゴリズムとは、最近傍探索法又はＮステップ探索法若しくは対数探索法を利用したアルゴリズムであることを特徴とする請求項１乃至３の何れか記載の動き補償予測符号化装置。
【請求項５】
第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する動き補償予測符号化方法であって、
前記第二ブロックの各々について、予め定められた反復数以下の少ない反復で所定の探索アルゴリズムを反復させて動きベクトルを演算する動きベクトル演算ステップと、
この動きベクトル演算ステップにて演算された各々の動きベクトルが完全等価又は近似等価であるか否かを判定する判定ステップと、
この判定ステップによる判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックを動き補償予測ブロックとして選択するよう制御する制御ステップと
を含むことを特徴とする動き補償予測符号化方法。
【請求項６】
コンピュータを、
第一ブロックを複数に分割した第二ブロックの各々ついて、予め定められた反復数以下の少ない反復で所定の探索アルゴリズムを反復させて動きベクトルを演算する動きベクトル演算手段、
この動きベクトル演算手段によって演算された各々の動きベクトルが完全等価又は近似等価であるか否かを判定する判定手段、
この判定手段による判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックを動き補償予測ブロックとして選択するよう制御する選択制御手段
として機能させることを特徴とする動き補償予測符号化プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】動き補償予測符号化装置及び動き補償予測符号化方法、動き補償予測符号化プログラム
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、動き補償予測符号化装置及び動き補償予測符号化方法、動き補償予測符号化プログラムに関し、詳しくは、動き補償予測ブロックのサイズを選択して使用できる動き補償予測符号化装置及び動き補償予測符号化方法、動き補償予測符号化プログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
そこで、本発明の目的は、トータルの演算量を減らしつつ、最適なブロックサイズの選択を可能とする動き補償予測符号化装置及び動き補償予測符号化方法、動き補償予測符号化プログラムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
請求項１記載の発明は、第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する動き補償予測符号化装置において、
前記第二ブロックの各々について、所定の探索アルゴリズムを予め定められた反復数以下の少ない反復で動きベクトルを演算する第一動きベクトル演算手段と、この第一動きベクトル演算手段によって演算された各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定手段と、この第一判定手段による判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックを動き補償予測ブロックとして選択するよう制御する第一選択制御手段とを備えたことを特徴とする動き補償予測符号化装置である。
この発明では、予め定められた反復数以下の少ない反復で所定の探索アルゴリズムを用いて複数の第二ブロックの各々の動きベクトルを演算し、それらの動きベクトルが完全等価又は近似等価である場合に、第一ブロックを動き補償予測ブロックとして選択する一方、それらの動きベクトルが完全等価又は近似等価でない場合に第二ブロックを動き補償予測ブロックとして選択する。ここで、第一ブロックを複数に分割したものが第二ブロックであるから、第一ブロックは「大きい動き補償予測ブロック」であり、第二ブロックは「小さい動き補償予測ブロック」である。
そして、複数の第二ブロック（小さい動き補償予測ブロック）の各々の動きベクトルが揃っている（完全等価又は近似等価している）ということは、各々の画像が同一方向且つ同一量に動いているということであり、これは、第一ブロック（大きい動き補償予測ブロック）の画像の動きを表すから、この場合は、演算量削減を意図として大きい動き補償予測ブロック、つまり、第一ブロックを選択する。
この発明の“ブロック選択”に要する時間は、もっぱら、複数の第二ブロックの各々の動きベクトルの演算時間で与えられるが、この演算は、探索アルゴリズムの“予め定められた反復数以下の少ない反復”で行われるため、探索アルゴリズムを予め定められた反復数で行った場合に比べて明らかに短い時間で済む。
したがって、トータルの演算量を減らしつつ、最適なブロックサイズの選択を可能とする動き補償予測符号化装置を提供できる。
請求項２記載の発明は、前記第一判定手段による判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックについて、前記所定の探索アルゴリズムにより予め定められた第２の反復数を上限として動きベクトルを演算する第二動きベクトル演算手段と、前記第一判定手段による判定の結果、完全等価又は近似等価でないと判定した場合に、前記第二ブロックの各々について、所定の探索アルゴリズムにより予め定められた第３の反復数を上限として動きベクトルを演算する第三動きベクトル演算手段と、この第三動きベクトル演算手段で演算された各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第二判定手段と、前記第二判定手段による判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックを動き補償予測ブロックとして選択するよう制御する一方、前記第二判定手段による判定の結果、完全等価又は近似等価でないと判定した場合に、前記第二ブロックを動き補償予測ブロックとして選択するよう制御する第二選択制御手段とを更に備えたことを特徴とする請求項１記載の動き補償予測符号化装置である。
この発明では、請求項１の発明に加えて、複数の第二ブロックの各々の動きベクトルが揃っていない（完全等価又は近似等価していない）場合には、第二ブロックの各々の動きベクトルを再探索する。この再探索は、予め定められた第３の反復数を上限にした所定の探索アルゴリズムの正確な演算で行われるので、第一動きベクトル演算手段の演算結果に比べて精度が高い。
このため、仮に、第二判定手段で逆の判定結果（等価）が得られた場合には、第一判定手段の判定結果が間違っていると判断して、大きい動き補償予測ブロック、つまり、第一ブロックを選択し、また、第二判定手段で同じ判定結果（等価でない）が得られた場合には、第一判定手段の判定結果が正しかったと判断して、小さい動き補償予測ブロック、つまり、第二ブロックを選択する。
したがって、仮に、第一判定手段の判定結果に誤りがあった場合でも、正しいブロック選択を行うことができ、実用上好ましいものとすることができる。
請求項３記載の発明は、前記第二動きベクトル演算手段及び前記第三動きベクトル演算手段は、前記第一動きベクトル演算手段が前記所定の探索アルゴリズムをｎ′回反復した場合には、このｎ′回反復した結果得られた中間値を初期値としてｎ′＋１回目から前記所定の探索アルゴリズムによる反復を開始することを特徴とする請求項２記載の動き補償予測符号化装置である。
この発明では、前記第一動きベクトル演算手段の演算で得られた中間値を、前記第二動きベクトル演算手段及び前記第三動きベクトル演算手段で流用するため、それらの第二動きベクトル演算手段及び第三動きベクトル演算手段の反復を少なくして、処理量の削減が図られる。
請求項４記載の発明は、  前記所定の探索アルゴリズムとは、最近傍探索法又はＮステップ探索法若しくは対数探索法を利用したアルゴリズムであることを特徴とする請求項１乃至３の何れか記載の動き補償予測符号化装置である。
請求項５記載の発明は、第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する動き補償予測符号化方法であって、前記第二ブロックの各々について、予め定められた反復数以下の少ない反復で所定の探索アルゴリズムを反復させて動きベクトルを演算する動きベクトル演算ステップと、この動きベクトル演算ステップにて演算された各々の動きベクトルが完全等価又は近似等価であるか否かを判定する判定ステップと、この判定ステップによる判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックを動き補償予測ブロックとして選択するよう制御する制御ステップとを含むことを特徴とする動き補償予測符号化方法である。
請求項６記載の発明は、コンピュータを、第一ブロックを複数に分割した第二ブロックの各々ついて、予め定められた反復数以下の少ない反復で所定の探索アルゴリズムを反復させて動きベクトルを演算する動きベクトル演算手段、この動きベクトル演算手段によって演算された各々の動きベクトルが完全等価又は近似等価であるか否かを判定する判定手段、この判定手段による判定の結果、完全等価又は近似等価であると判定した場合に、前記第一ブロックを動き補償予測ブロックとして選択するよう制御する選択制御手段として機能させることを特徴とする動き補償予測符号化プログラムである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
本発明によれば、“ブロック選択”に要する時間が、もっぱら、複数の第二ブロックの各々の動きベクトルの演算時間で与えられる。この演算は、「予め定められた反復数以下の少ない反復」で行われるため、探索アルゴリズムを予め定められた反復数で行った場合に比べて明らかに短い時間で済む。
したがって、トータルの演算量を減らしつつ、最適なブロックサイズの選択を可能とする動き補償予測符号化装置を提供できる。