(57)【要約】【課題】  動きが大きくても動きベクトルの検出精度を低下させずに実時間処理を可能とする。符号化処理に長時間を要するフレームがあっても実時間処理を可能とする。【解決手段】  本発明は、入力フレームを縦横に分割したブロック単位に、参照フレーム上の相似したブロックの位置を求めて動きベクトルを得る動きベクトル検出装置に関する。そして、参照フレーム上の指示された探索範囲で動きベクトルを検出する動き探索手段と、フレーム内全ブロックの探索範囲の総和が、フレームについて定められた探索範囲許容量を超えないように、各ブロックの探索範囲を決定して、動き探索手段に指示する探索範囲制御手段とを有することを特徴とする。  また、複数フレームについて定められた計算量を超えないように、各フレームの計算量を決定して、符号化手段に指示する計算量制御手段を有することも好ましい。【選択図】      図１
2009153102.tif 000002
【特許請求の範囲】
【請求項１】
入力フレームを縦横に分割したブロック単位に、参照フレーム上の相似したブロックの位置を求めて動きベクトルを得る動きベクトル検出装置において、
参照フレーム上の指示された探索範囲で動きベクトルを検出する動き探索手段と、
フレーム内全ブロックの探索範囲の総和が、フレームについて定められた探索範囲許容量を超えないように、各ブロックの探索範囲を決定して、上記動き探索手段に指示する探索範囲制御手段と
を有することを特徴とする動きベクトル検出装置。
【請求項２】
上記探索範囲制御手段は、同一フレーム内の探索範囲が決定されていない残りのブロック数と、残りのブロック数に割当て可能な、残っている探索範囲許容量とに基づいて、各ブロックの探索範囲を決定することを特徴とする請求項１に記載の動きベクトル検出装置。
【請求項３】
上記動き探索手段による動き探索で得られた参照ブロックと入力ブロック間の相違度と得られた動きベクトルの大きさに基づき、予測探索範囲を決定する予測範囲決定手段を有し、
上記探索範囲制御手段は、動き探索が既に実行された、入力ブロックの周囲ブロックについての上記予測探索範囲をも利用して、各ブロックの探索範囲を決定することを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項４】
入力フレームを縦横に分割した入力ブロックと、内蔵する動きベクトル検出装置が検出した動きベクトルに応じて位置が定まる、参照フレームにおける上記入力ブロックに対応する参照ブロックとの差分を符号化するフレーム間符号化装置において、
上記動きベクトル検出装置として、請求項１〜３のいずれかに記載のものを適用したことを特徴とするフレーム間符号化装置。
【請求項５】
入力フレームを縦横に分割したブロック単位に、参照フレーム上の相似したブロックの位置を求めて動きベクトルを得る動きベクトル検出プログラムであって、
コンピュータを、
参照フレーム上の指示された探索範囲で動きベクトルを検出する動き探索手段と、
フレーム内全ブロックの探索範囲の総和が、フレームについて定められた探索範囲許容量を超えないように、各ブロックの探索範囲を決定して、上記動き探索手段に指示する探索範囲制御手段と
して機能させることを特徴とする動きベクトル検出プログラム。
【請求項６】
上記探索範囲制御手段は、同一フレーム内の探索範囲が決定されていない残りのブロック数と、残りのブロック数に割当て可能な、残っている探索範囲許容量とに基づいて、各ブロックの探索範囲を決定することを特徴とする請求項５に記載の動きベクトル検出プログラム。
【請求項７】
上記コンピュータを、上記動き探索手段による動き探索で得られた参照ブロックと入力ブロック間の相違度と得られた動きベクトルの大きさに基づき、予測探索範囲を決定する予測範囲決定手段として機能させるプログラム部分を含み、
上記探索範囲制御手段は、動き探索が既に実行された、入力ブロックの周囲ブロックについての上記予測探索範囲をも利用して、各ブロックの探索範囲を決定する
ことを特徴とする請求項６に記載の動きベクトル検出プログラム。
【請求項８】
入力フレームを縦横に分割した入力ブロックと、内蔵する動きベクトル検出プログラムが検出した動きベクトルに応じて位置が定まる、参照フレームにおける上記入力ブロックに対応する参照ブロックとの差分を符号化する、コンピュータが実行し得るように記述されたフレーム間符号化プログラムにおいて、
上記動きベクトル検出プログラムとして、請求項５〜７のいずれかに記載のものを適用したことを特徴とするフレーム間符号化プログラム。
【請求項９】
動画像をフレーム毎に符号化する動画像符号化装置において、
各フレームの符号化を行う、符号化に要する処理計算量を切り替え可能な符号化手段と、
所定数（２以上の任意の値）が連続するフレーム単位に対して予め定められている総計算量を超えないように、フレーム単位内の各フレームに対し、各フレームの内容に応じて計算量を配分する計算量配分手段と、
各フレームに配分された計算量に従うように、上記符号化手段による符号化を制御する計算量制御手段と
を有することを特徴とする動画像符号化装置。
【請求項１０】
動画像をフレーム毎に符号化する、動画像符号化装置を構成するコンピュータに搭載される動画像符号化プログラムであって、
コンピュータを、
各フレームの符号化を行う、符号化に要する処理計算量を切り替え可能な符号化手段と、
所定数（２以上の任意の値）が連続するフレーム単位に対して予め定められている総計算量を超えないように、フレーム単位内の各フレームに対し、各フレームの内容に応じて計算量を配分する計算量配分手段と、
各フレームに配分された計算量に従うように、上記符号化手段による符号化を制御する計算量制御手段として機能させる
ことを特徴とする動画像符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動きベクトル検出装置、フレーム間符号化装置、動画像符号化装置、動きベクトル検出プログラム、フレーム間符号化プログラム及び動画像符号化プログラムに関し、例えば、動画像の実時間符号化装置に適用し得るものである。
【背景技術】
【０００２】
ビデオオンデマンド、テレビ会議、デジタルＴＶ放送等でデジタルフォーマットの動画像を様々な通信経路を通して送信する際、ビデオキャプチャ装置を使いキャプチャした未圧縮のデータのままではその量が膨大であるため、そのまま送信するのは困難である。ある程度冗長な部分を削除することでデータ量を減らして送信する必要がある。また、テレビ会議、デジタルＴＶ放送等では、キャプチャした画像を実時間で圧縮（符号化）して送信する必要がある。
【０００３】
従来、この種の動画像の実時間符号化装置は、フレーム内符号化（フレーム内の画素の局所的類似性を使いブロック単位で圧縮）と、フレーム間符号化（フレームをブロック単位に分け、各ブロックがフレーム間でどれだけ動いたかを示す動きベクトルを求め、この動きベクトルを利用した符号化）とを併用し、画像内容に応じて、いずれかの符号化出力を選択する。
【０００４】
動きベクトルを求める際の各ブロックの探索範囲が一定の場合もあるが、ブロックの動き探索に要する時間を短縮するため、既に符号化された周辺ブロックの動きベクトルの大きさから探索範囲を調整する場合もある。
【０００５】
なお、実時間での符号化を考慮し、動きベクトルの探索機能以外で処理の高速化を図った技術は、特許文献１や特許文献２に記載されている。
【特許文献１】特開平１０−２１０４７５号公報
【特許文献２】特開２０００−２３２６４４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ハードウェアの性能によっては、予め動きベクトルの探索範囲を狭める必要がある。既に符号化された周辺ブロックの動きベクトルの大きさから探索範囲を調整する場合であっても、ハードウェアの性能によっては、探索範囲の最大範囲を狭める必要がある。
【０００７】
しかし、探索範囲を狭めると動きが大きい動画ではマッチするブロックをうまく探し出すことができず、画質が悪くなってしまうという問題点があった。探索範囲を狭めた場合において、動きが大きい場面が長く続くと、画質が悪い画像が連続し、動きがある期間と動きがない期間とが連続すると、画質が安定しない。
【０００８】
勿論、探索範囲を狭めずに処理するようにした場合には、処理遅延が積み重なり、実時間処理が困難となることもある。
【０００９】
そのため、動きが大きくても検出精度や画質を低下させずに実時間処理を可能とする動きベクトル検出装置、フレーム間符号化装置、動きベクトル検出プログラム及びフレーム間符号化プログラムが望まれている。また、複数フレームに対しても、安定した画質の符号化画像を実時間処理で得られる動画像符号化装置及び動画像符号化プログラムが望まれている。
【課題を解決するための手段】
【００１０】
第１の本発明は、入力フレームを縦横に分割したブロック単位に、参照フレーム上の相似したブロックの位置を求めて動きベクトルを得る動きベクトル検出装置において、（１）参照フレーム上の指示された探索範囲で動きベクトルを検出する動き探索手段と、（２）フレーム内全ブロックの探索範囲の総和が、フレームについて定められた探索範囲許容量を超えないように、各ブロックの探索範囲を決定して、上記動き探索手段に指示する探索範囲制御手段とを有することを特徴とする。
【００１１】
第２の本発明は、入力フレームを縦横に分割した入力ブロックと、内蔵する動きベクトル検出装置が検出した動きベクトルに応じて位置が定まる、参照フレームにおける上記入力ブロックに対応する参照ブロックとの差分を符号化するフレーム間符号化装置において、上記動きベクトル検出装置として、第１の本発明のものを適用したことを特徴とする。
【００１２】
第３の本発明は、入力フレームを縦横に分割したブロック単位に、参照フレーム上の相似したブロックの位置を求めて動きベクトルを得る動きベクトル検出プログラムであって、コンピュータを、（１）参照フレーム上の指示された探索範囲で動きベクトルを検出する動き探索手段と、（２）フレーム内全ブロックの探索範囲の総和が、フレームについて定められた探索範囲許容量を超えないように、各ブロックの探索範囲を決定して、上記動き探索手段に指示する探索範囲制御手段として機能させることを特徴とする。
【００１３】
第４の本発明は、入力フレームを縦横に分割した入力ブロックと、内蔵する動きベクトル検出プログラムが検出した動きベクトルに応じて位置が定まる、参照フレームにおける上記入力ブロックに対応する参照ブロックとの差分を符号化する、コンピュータが実行し得るように記述されたフレーム間符号化プログラムにおいて、上記動きベクトル検出プログラムとして、第３の本発明のものを適用したことを特徴とする。
【００１４】
第５の本発明は、動画像をフレーム毎に符号化する動画像符号化装置において、（１）各フレームの符号化を行う、符号化に要する処理計算量を切り替え可能な符号化手段と、（２）所定数（２以上の任意の値）が連続するフレーム単位に対して予め定められている総計算量を超えないように、フレーム単位内の各フレームに対し、各フレームの内容に応じて計算量を配分する計算量配分手段と、（３）各フレームに配分された計算量に従うように、上記符号化手段による符号化を制御する計算量制御手段とを有することを特徴とする。
【００１５】
第６の本発明は、動画像をフレーム毎に符号化する、動画像符号化装置を構成するコンピュータに搭載される動画像符号化プログラムであって、コンピュータを、（１）各フレームの符号化を行う、符号化に要する処理計算量を切り替え可能な符号化手段と、（２）所定数（２以上の任意の値）が連続するフレーム単位に対して予め定められている総計算量を超えないように、フレーム単位内の各フレームに対し、各フレームの内容に応じて計算量を配分する計算量配分手段と、（３）各フレームに配分された計算量に従うように、上記符号化手段による符号化を制御する計算量制御手段として機能させることを特徴とする。
【発明の効果】
【００１６】
本発明の動きベクトル検出装置、フレーム間符号化装置、動きベクトル検出プログラム及びフレーム間符号化プログラムによれば、動きが大きくても検出精度や画質を低下させずに実時間処理を可能とすることができる。
【００１７】
また、動画像符号化装置及び動画像符号化プログラムによれば、複数フレームに対して、安定した画質の符号化画像を実時間処理で得ることができる。
【発明を実施するための最良の形態】
【００１８】
（Ａ）第１の実施形態
以下、本発明による動きベクトル検出装置、フレーム間符号化装置、動きベクトル検出プログラム及びフレーム間符号化プログラムを、動画像の実時間符号化装置に適用した第１の実施形態を、図面を参照しながら詳述する。
【００１９】
ここで、第１の実施形態の動きベクトル検出装置やフレーム間符号化装置の全て又は一部は、ハードウェアによって構築することもできるが、ＣＰＵとＣＰＵが実行するプログラムで構築することもできる。上記プログラムは、記録媒体を介して装置に導入されたものであっても良く、通信処理（例えばダウンロード）を介して装置に導入されたものであっても良い（後述する第２や第３の実施形態も同様である）。
【００２０】
（Ａ−１）第１の実施形態の構成
図２は、第１実施形態のフレーム間符号化装置が適用された動画像の実時間符号化装置１０の全体構成を示すブロック図である。
【００２１】
図２において、入力バッファ１１ではキャプチャした動画像の各フレーム（動画像を構成する画像１枚）を記録する。フレーム内符号化部１２では、入力バッファ１１からフレームを取得しフレーム内符号化（フレーム内の画素の局所的類似性を使いブロック単位で圧縮）を行い、一方、フレーム間符号化部１３では、フレームをブロック単位に分け、各ブロックがフレーム間でどれだけ動いたかを示す動きベクトル（図３参照）を求めて符号化する。出力バッファ１４は、符号化部１２又は１３からの出力を蓄積する。
【００２２】
ここでは、入力バッファ１１に入力される動画像の各フレームには、フレーム内符号化するもの（例えばＩフレーム）かフレーム間符号化するもの（例えばＰフレーム）かの識別情報が盛り込まれているものとする。但し、入力バッファ１１が、例えば、相前後する対応位置の画素値の差分二乗和などに基づいて、いずれの符号化方式を適用するかを決定するものであっても良い。
【００２３】
図１は、フレーム間符号化部１３（実施形態のフレーム間符号化装置）の詳細構成を示すブロック図である。
【００２４】
図１において、フレーム間符号化部１３は、ブロック分割部２１、動き探索部２２、動き補償部２３、変換量子化逆量子化逆変換部２４、符号化部２５、参照バッファ管理部２６及び探索範囲制御部２７を有する。ここで、動き探索部２２及び探索範囲制御部２７が、実施形態の動きベクトル検出装置を構成している。
【００２５】
ブロック分割部２１は、１フレームを所定の大きさを有する複数のブロックに分割して動き探索部２２に与えるものである。
【００２６】
動き探索部２２は、参照バッファ管理部２６に格納されている参照フレーム（既に符号化したものを逆変換した後に再構成されたフレーム）から、入力されたブロックと最も良く似ているブロックを探し出し、その位置のずれを動きベクトルとして動き補償部２３及び探索範囲制御部２７に出力するものである。この実施形態の場合、動き探索部２２による探索範囲は、探索範囲制御部２７によって決定された範囲である。
【００２７】
動き補償部２３は、最も良く似ている参照フレームのブロックを動きベクトルを使って参照フレームから取り出し（取り出したものを予測ブロックと適宜呼ぶ）、変換量子化逆量子化逆変換部２４及び探索範囲制御部２７に与えるものである。
【００２８】
探索範囲制御部２７は、動き補償部２３から得られた予測ブロックと元ブロック（入力されたブロック）との差分と、動き探索部２２から得られた動きベクトルと、予め定められている探索範囲総許容量と、いくつかの閾値とに基づき、動き探索範囲を決定するものである。動き探索範囲の決定方法については、後で詳細に説明する。
【００２９】
変換量子化逆量子化逆変換部２４は、予測ブロックと元ブロックとの差分を離散コサイン変換（ＤＣＴ変換）した後、量子化を行い、この量子化データを符号化部２５に与えるものである。また、変換量子化逆量子化逆変換部２４では、上述した量子化データに対して逆量子化を行った後、逆ＤＣＴ変換を行って差分データに戻して参照バッファ管理部２６に与えるものである。
【００３０】
参照バッファ管理部２６は、変換量子化逆量子化逆変換部２４から得られた差分データを、格納している参照フレームの該当ブロックに足し合わせて新たな参照フレームを構成するものである。構成された参照フレームは、上述したように、次のフレームの符号化時における参照フレームとして使用される。
【００３１】
符号化部２５は、変換量子化逆量子化逆変換部１４で得られた量子化データをエントロピー符号化するものである。
【００３２】
（Ａ−２）第１の実施形態における探索範囲の制御方法の概要
この第１の実施形態は、最大探索範囲を狭めることなく計算量を抑えることのできる探索範囲制御部２７を設けたことに大きな特徴を有している。以下では、探索範囲制御部２７が適用している探索範囲の制御方法の概要を説明する。
【００３３】
動き探索部２２による動き探索は、入力されたブロックとよく似たブロックを参照フレームから探し出す操作である。例えば、参照フレームをＲ、入力されたブロックをＯとすると、この操作は、（１）式に示す絶対差分和（Ｓｕｍ  ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ；以下、ＳＡＤと呼ぶ）を最小にする位置（ｘ＋ｌ，ｙ＋ｍ）を探す操作となる。ＳＡＤが小さいほど似ていると言うことができる。
【数１】
2009153102.tif 000003
【００３４】
（１）式において、ａｂｓ（ｘｘ）はｘｘの絶対値である。Ｒ（ｘ＋ｌ＋ｉ，ｙ＋ｍ＋ｊ）は、参照フレームＲの位置（ｘ＋ｌ＋ｉ，ｙ＋ｍ＋ｊ）における値であり、例えば、輝度値（又は、Ｒ（赤）、Ｇ（緑）、Ｂ（青）値、若しくは、Ｃ（シアン）、Ｍ（マゼンダ）、Ｙ（イエロー）などの色成分値）である。ｉの範囲がブロック幅分だけ変化し、ｊの範囲がブロック高分だけ変化するので、Ｒ（ｘ＋ｌ＋ｉ，ｙ＋ｍ＋ｊ）は、参照フレームＲのブロックを表していると見ることができる。Ｏ（ｉ，ｊ）は、入力されたブロックＯの位置（ｉ，ｊ）における値であり、例えば、輝度値（又は、ＲＧＢ値、ＣＭＹ値など）である。ｉの範囲がブロック幅分だけ変化し、ｊの範囲がブロック高分だけ変化するので、Ｏ（ｉ，ｊ）は、入力されたブロックＯそのものを表していると見ることができる。
【００３５】
ｘの範囲は０から画像幅Ｘまでであり、ｙの範囲は０から画像高Ｙまでであり、（ｘ，ｙ）は、探索の基準点つまりブロックＯの最も左上の画素の画像上での位置を基準点（０，０）とした相対位置である。ｉの範囲はｘからブロック幅まで取り得ることが可能であり、ｊの範囲はｙからブロック高まで取り得ることが可能である。
【００３６】
ｌはｘ軸方向の探索範囲を規定するパラメータであり、ｍはｙ軸方向の探索範囲を規定するパラメータである。ｘ軸方向の探索範囲の情報をＬとし、ｙ軸方向の探索範囲の情報Ｍとすると、−Ｌ≦ｌ≦Ｌ、−Ｍ≦ｍ≦Ｍという範囲でｌ、ｍの値を変えながら、（１）式のＳＡＤが最小となる位置（ｘ＋ｌ，ｙ＋ｍ）を探す。この最小位置（ｘ＋ｌ，ｙ＋ｍ）は、動きベクトルを表している。
【００３７】
探索範囲Ｌ、Ｍ（言い換えると−Ｌ≦ｌ≦Ｌ、−Ｍ≦ｍ≦Ｍ）は、フレーム内の各ブロックにおいて一定とすることもでき、また、予め定められた最大範囲及び最小範囲の間で可変とすることもできる。
【００３８】
各種パラメータの意味合いについては、後述する図４を用いた探索範囲と入力ブロックとの関係の説明でも明確にする。
【００３９】
第１の実施形態では、このような探索範囲の定め方を採用せず、各フレームにおいて、探索範囲の総許容量となるものを定め、フレーム内ブロックの探索範囲の総和が探索範囲の総許容量を超えないように各ブロックにおける探索範囲の大きさを制御することとした。
【００４０】
こうすることにより、１フレームで探索に要する計算量を一定値以下に制限することができる。探索範囲の総許容量は、探索範囲のプールとみなすことができ、各ブロックではこのプールから必要な探索範囲を決定した分だけ取り出して、その値に基づき探索する。
【００４１】
また、第１の実施形態では、動き探索の結果得られた参照ブロックとブロック間の相違度と、動きベクトルの大きさに基づき、そのブロックの周辺ブロックに対する予測探索範囲を決定し、未処理ブロックの探索範囲の決定に反映させる。予測探索範囲とは、未処理のブロックがとるべき探索範囲を決定するための予測値である。
【００４２】
（Ａ−３）第１の実施形態の動作
以下、フレーム間符号化部１３の動作、特に、動きベクトルの検出に関係する動作を説明する。
【００４３】
動き探索部２２では、探索範囲制御部２７で指定された探索範囲内で、入力されたブロックに最もよく似ている（ある評価基準（例えば、上述したＳＡＤ）に基づいて判定する）ブロック位置を参照フレームから探し出し、動きベクトルを計算する。動き補償部２３では、動きベクトルから得られる参照フレーム中のブロック（以下、参照ブロックと呼ぶ）を求める。探索範囲制御部２７では、探索範囲を決定する。基本的には、探索範囲のプールと言える探索範囲許容量ＴｏｔａｌＲａｎｇｅから、必要な分だけ探索範囲を取り出し、その探索範囲に基づき探索を実行する。探索範囲制御部２７では、探索範囲許容量ＴｏｔａｌＲａｎｇｅ内の探索範囲を使い尽くすことがないよう制御する。
【００４４】
探索範囲許容量ＴｏｔａｌＲａｎｇｅは、例えば、ブロック数×適当な探索範囲で表せ（必ずしもそう表す必要はない）、適当な探索範囲は、最大探索範囲（ｍａｘＲａｎｇｅ；上述したＬ、Ｍの２倍の最大値）と最小探索範囲（ｍｉｎＲａｎｇｅ；上述したＬ、Ｍの２倍の最小値）の間の値である。例えば、最大探索範囲が１６（一辺の画素数）で、最小探索範囲が４で、画像サイズがＱＶＧＡ（３２０ｘ２４０）、ブロックサイズが１６ｘ１６画素の場合には、探索範囲許容量ＴｏｔａｌＲａｎｇｅは、８×（３２０×２４０÷１６÷１６）＝２４００とある。ここで、８が適当な探索範囲で、（３２０×２４０÷１６÷１６＝３００）がブロック数である。探索範囲許容量ＴｏｔａｌＲａｎｇｅは、例えば、（ブロック数−１）×ｍｉｎＲａｎｇｅ＋ｍａｘＲａｎｇｅ≦ＴｏｔａｌＲａｎｇｅ≦ブロック数×ｍａｘＲａｎｇｅの範囲内の値をとる。上の例の場合、１２１２（＝４×２９９＋１６）≦ＴｏｔａｌＲａｎｇｅ≦４８００（＝１６×３００）である。範囲の最小値（ブロック数−１）×ｍｉｎＲａｎｇｅ＋ｍａｘＲａｎｇｅは、精度の向上を図るため、それ以降の探索に影響を与える最初に探索されるブロックについては、最大探索範囲ｍａｘＲａｎｇｅとすることとしたため、上述の式のようになった。
【００４５】
図４は、探索範囲と入力ブロックとの関係を示す説明図である。
【００４６】
図４は、基本的には参照フレームを示している。参照フレームにおいて、参照ブロックになり得るものは、（０，０）を左上座標とした１３×１３画素のブロック０から、（３１，３１）を左上座標とした１３×１３画素のブロック１０２３までの１０２４個がある。
【００４７】
図４において、左上の座標が（９，１０）である１３×１３画素の実線ブロックが入力ブロックＯ（ｉ，ｊ）である。なお、図４では、図の大きさの制約から、上述した場合の例からブロックサイズの大きさを変更している。入力ブロックＯ（ｉ，ｊ）は、ｉが９〜２１内の値をとり、ｊが１０〜２２内の値をとるものである。
【００４８】
探索範囲を規定するＬ及びＭがそれぞれ４であれば、動きベクトルの検出対象の入力ブロックＯ（ｉ，ｊ）の左上座標（９，１０）を中心とし、ｘ方向に±Ｌ（＝±４）だけずれ、ｙ方向に±Ｍ（＝±４）だけずれた、破線矩形が探索範囲となり、探索範囲内に位置する座標を、左上座標とした１３×１３画素の参照ブロックについて、入力ブロックＯ（ｉ，ｊ）とのＳＡＤが求められる。図４の入力ブロックの場合、左上座標が（９−２，１０−３）である一点鎖線のブロックＲ（９−２＋ｉ，１０−３＋ｊ）や、左上座標が（９−３，１０＋２）である二点鎖線のブロックＲ（９−３＋ｉ，１０＋２＋ｊ）や、左上座標が（９＋２，１０＋３）である三点鎖線のブロックＲ（９＋２＋ｉ，１０＋３＋ｊ）等が参照ブロックとなる。
【００４９】
探索範囲制御部２７は、例えば、以下のような手順Ｔ１〜Ｔ４によって探索範囲を決定する。なお、図５は、手順Ｔ２及びＴ３に関係する処理部分を示すフローチャートであり、ある１つの入力ブロックに対する処理を示している。
【００５０】
（手順Ｔ１）
残っている探索範囲許容量を表すパラメータ（残り探索範囲許容量）ＲｅｍａｉｎＲａｎｇｅに、探索範囲総許容量（フレーム当りの許容量）ＴｏｔａｌＲａｎｇｅを設定（初期化）する。すなわち、ＲｅｍａｉｎＲａｎｇｅ＝ＴｏｔａｌＲａｎｇｅとする。
【００５１】
あるブロックの処理が終了すると、フレーム内の全てのブロックについて探索が実行されていないことを確認した後、処理対象の入力ブロックがフレーム中１番目のブロックか否かが確認される。
【００５２】
処理対象の入力ブロックがフレーム中１番目のブロックであれば手順Ｔ２が実行され、処理対象の入力ブロックが２番目以降のブロックであれば手順Ｔ３が実行される。
【００５３】
（手順Ｔ２）
入力されたブロックがフレーム中１番目の場合、探索範囲制御部２７は、予め定められた値を探索範囲にする。例えば、探索範囲を表すパラメータＲａｎｇｅ（＝Ｌ、Ｍ）を許容されている最大探索範囲ｍａｘＲａｎｇｅとする。これにより、動き探索部２２は、最大探索範囲ｍａｘＲａｎｇｅで探索を行うことになる。
【００５４】
また、探索範囲制御部２７は、残り探索範囲許容量ＲｅｍａｉｎＲａｎｇｅを、今までの値から、探索範囲Ｒａｎｇｅ分だけ小さくする。すなわち、ＲｅｍａｉｎＲａｎｇｅ＝ＲｅｍａｉｎＲａｎｇｅ−Ｒａｎｇｅとする。
【００５５】
（手順Ｔ３）
入力されたブロックがフレーム中２番目以降の場合、既に動きベクトルが決定している周辺ブロック（後述する図６参照）の予測探索範囲と、残り探索範囲許容量ＲｅｍａｉｎＲａｎｇｅとを基に、探索範囲Ｒａｎｇｅを決定する。探索範囲Ｒａｎｇｅの決定に供する周辺ブロックは、図６に例示するような、入力された処理対象ブロックの左斜め上のブロックＢＡ、真上のブロックＢＢ、右斜め上のブロックＢＣ、左隣のブロックＢＤである。但し、後述する手順Ｔ４で説明するが、各周辺ブロックＢＡ、ＢＢ、ＢＣ、ＢＤに対し、予測探索範囲ａ、ｂ、ｃ、ｄが求まっているものとする。
【００５６】
探索範囲Ｒａｎｇｅは、例えば、（２）式に従って算出される。
【００５７】
Ｒａｎｇｅ＝Ｍａｘ（Ｍｉｎ（Ｉｎｔ（ＷＡ２（ｗａ，ｒｒ）），ｍａｘＲａｎｇｅ），ｍｉｎＲａｎｇｅ）                                                    …（２）
（２）式において、ｗａは、周辺ブロックＢＡ、ＢＢ、ＢＣ、ＢＤの予測探索範囲ａ、ｂ、ｃ、ｄ（ｍｉｎＲａｎｇｅ以上ｍａｘＲａｎｇｅ以下）に関数ＷＡ１（ａ，ｂ，ｃ，ｄ）を適用した値であり、関数ＷＡ１（ａ，ｂ，ｃ，ｄ）としては、（３）式に示すような重み付け平均値を適用することができる。（３）式おける重み付け係数α，β，γ，φは、周辺ブロックで得られないものがある場合には、そのブロックに係るものを０とする。ｒｒは、（４）式に示すように、残り探索範囲許容量ＲｅｍａｉｎＲａｎｇｅを残りブロック数で割った値である。（２）式における関数ＷＡ２（ｘ，ｙ）は、（５）式に示すように、二つの値ｘ，ｙの重み付き平均値である。Ｉｎｔ（ｘ）はｘを四捨五入した値を表している。Ｍａｘは二つの引数のうち大きい方を選択する関数であり、Ｍｉｎは二つの引数のうち小さい方を選択する関数である。
【００５８】
ＷＡ１（ａ，ｂ，ｃ，ｄ）＝αａ＋βｂ＋γｃ＋φｄ
但し、０≦α，β，γ，φ≦１、α＋β＋γ＋φ＝１
（例えば、α，β，γ，φ＝０．２５）                          …（３）
ｒｒ＝  ＲｅｍａｉｎＲａｎｇｅ／残りブロック数                  …（４）
ＷＡ２（ｘ，ｙ）＝δｘ＋σｙ
但し、０≦δ，σ≦１、δ＋σ＝１
（例えば、δ，σ＝０．５）                                    …（５）
（２）式は、周辺ブロックＢＡ、ＢＢ、ＢＣ、ＢＤの予測探索範囲から定めた探索範囲候補ｗａと、残り探索範囲許容量ＲｅｍａｉｎＲａｎｇｅを残りブロック数で割ることで定めた残りの各ブロックに割り振れる１ブロック当たりの探索範囲候補ｒｒとの重み付け平均値ＷＡ２（ｗａ，ｒｒ）を探索範囲候補とすることを基本とする。値ＷＡ２（ｗａ，ｒｒ）は、整数値以外を取ることもあるので、四捨五入処理することとした。関数Ｍａｘ及びＭｉｎは、四捨五入処理後の候補Ｉｎｔ（ＷＡ２（ｗａ，ｒｒ））が、最小探索範囲ｍｉｎＲａｎｇｅと最大探索範囲ｍａｘＲａｎｇｅの間の範囲に収まるようにするための関数である。
【００５９】
すなわち、以上のようにして探索範囲Ｒａｎｇｅを求めることにより、既に処理が終わった周辺ブロックの影響を現在処理しているブロックの探索範囲Ｒａｎｇｅの決定に反映しつつ、現在割り当て可能な平均的な探索範囲ｒｒになるべく近くなるように探索範囲Ｒａｎｇｅを決定する。
【００６０】
但し、例外として、値ｒｒ（＝ＲｅｍａｉｎＲａｎｇｅ／残りのブロック数）が最小探索範囲ｍｉｎＲａｎｇｅより小さくなった場合には、最小探索範囲Ｒａｎｇｅを最小探索範囲ｍｉｎＲａｎｇｅとする。このようにしないと、最小探索範囲ｍｉｎＲａｎｇｅより小さい探索範囲が割り当てられてしまうことがある。例えば、最小探索範囲が４の場合において、残り探索範囲許容量ＲｅｍａｉｎＲａｎｇｅが１００で、残りブロック数が２６の場合であれば、探索範囲Ｒａｎｇｅ＝最小探索範囲ｍｉｎＲａｎｇｅとなる。
【００６１】
今回の入力ブロックに対する探索範囲Ｒａｎｇｅを定めると、その分だけ、残り探索範囲許容量Ｒｅｍａｉｎを小さくする。すなわち、ＲｅｍａｉｎＲａｎｇｅ＝ＲｅｍａｉｎＲａｎｇｅ−Ｒａｎｇｅとする。
【００６２】
（手順Ｔ４）
決定された探索範囲Ｒａｎｇｅを適用したその入力されたブロックについての動き探索が終了したら、次のブロックの動き探索で使用する探索範囲を求めるために用いる、上述した予測探索範囲を求める。例えば、次のような方法によって予測探索範囲を求める。
【００６３】
動き探索により求まった参照ブロックと処理中のブロック間のＳＡＤが大きく（言い換えると、探索がうまくいかなかった可能性が大きい）動きベクトルが小さい場合には、未処理の周辺ブロックの探索範囲を大きくするために、予測探索範囲を大きくし、未処理の周辺ブロックの探索がよりうまく行くようにする。逆に、ＳＡＤが小さく動きベクトルが大きい場合には、未処理の周辺ブロックの探索範囲を小さくするために、予測探索範囲を小さくし、未処理の周辺ブロックにおける計算量を多少なりとも少なくする。このような決定方法をプログラム的に記述すると、以下の通りである。
【００６４】
ＩＦ（ＳＡＤ＞ｇ  ａｎｄ  動きベクトルの大きさ＜ｍ）
予測探索範囲＝Ｍｉｎ（Ｒａｎｇｅ＋ｐ，ＭａｘＲａｎｇｅ）
ＥＬＳＥ  ＩＦ（ＳＡＤ＜ｆ  ａｎｄ  動きベクトルの大きさ＞ｎ）
予測探索範囲＝Ｍｉｎ（Ｒａｎｇｅ−ｑ，ＭｉｎＲａｎｇｅ）
ＥＬＳＥ
予測探索範囲＝Ｒａｎｇｅ
ここで、ｇ及びｆはそれぞれ、０＜ｇ，ｆ＜（ＳＡＤの最大値）を満たす整数である。
【００６５】
ＳＡＤの最大値は、１６ｘ１６画素のブロックで輝度値の最高値が２５５の場合には、１６ｘ１６ｘ２５５（＝６５２８０）である。ｐ，ｑは正の整数で特に範囲はないが、探索範囲Ｒａｎｇｅから足したり引いたりした際、最大探索範囲ＭａｘＲａｎｇｅを超えたり最小探索範囲ＭｉｎＲａｎｇｅをわったりする頻度が少なくなるような値を適用する。
【００６６】
（Ａ−３）第１の実施形態の効果
第１の実施形態によれば、探索範囲許容量ＴｏｔａｌＲａｎｇｅや残り探索範囲許容量ＲｅｍａｉｎＲａｎｇｅを使って、各ブロックの探索範囲の総和が一定値以下になるよう制御するようにしたので、各フレームにおける探索による計算量を抑えることができる。例えば、動き探索範囲一定の探索方法の場合、ａ（ｍａｘＲａｎｇｅ×ブロック数）（ａは任意の正数）の計算量が必要となり、周辺ブロックに応じて探索範囲を決定する方法でも最悪の場合、同じａ（ｍａｘＲａｎｇｅ×ブロック数）の計算量が必要となると考えられるが、この実施形態では、ａ×ＴｏｔａｌＲａｎｇｅの計算量が必要であり、ＴｏｔａｌＲａｎｇｅ＜（ｍａｘＲａｎｇｅ×ブロック数）のように、探索範囲許容量ＴｏｔａｌＲａｎｇｅを定めると、計算量を従来の方法より少なくすることができ、かつ必要な部分では最大探索範囲ｍａｘＲａｎｇｅを使った探索を行うことができる。他の方法では、最大探索範囲ｍａｘＲａｎｇｅを小さくしない限りａ×ＴｏｔａｌＲａｎｇｅの計算量を実現できる補償はない。
【００６７】
（Ａ−４）第１の実施形態の変形実施形態
第１の実施形態では、フレーム間符号化装置（フレーム間符号化部１３）を図２に示す構成の符号化装置に適用したものを示したが、適用対象は図２に示す構成のものに限定されず、フレーム間符号化装置を利用した符号化装置に広く適用することができる。
【００６８】
また、第１の実施形態の動きベクトル検出装置も、適用対象が動画像符号化装置に限定されないことは勿論である。例えば、移動体を抽出し、追跡するような処理を行う画像処理装置が、動きベクトル検出装置を内蔵しているような場合には、そのような動きベクトル検出装置に対しても本発明を適用することができる。
【００６９】
第１の実施形態では、探索範囲許容量ＴｏｔａｌＲａｎｇｅが固定のものを示したが、探索範囲許容量ＴｏｔａｌＲａｎｇｅを変化させるものであっても良い。例えば、あるフレームの全てのブロックの探索範囲を決定した後の残り探索範囲許容量ＲｅｍａｉｎＲａｎｇｅが閾値より大きいときには、次のフレームの探索範囲許容量ＴｏｔａｌＲａｎｇｅを、基準となっている探索範囲許容量ＴｏｔａｌＲａｎｇｅに所定量だけ加算したものとするようにしても良い。
【００７０】
第１の実施形態では、探索範囲の決定に影響を与える周辺ブロックが左斜め上、真上、右斜め上、左隣の４つのブロックであるものを示したが、周辺ブロックはこれに限定されるものではない。例えば、真上、右斜め上、左隣の３つのブロックであっても良い。
【００７１】
第１の実施形態では、入力ブロックと参照ブロックとの近似度を評価する指標がＳＡＤであるものを示したが、他の指標であっても良い。例えば、差分二乗和の平方根であっても良い。
【００７２】
（Ｂ）第２の実施形態
次に、本発明による動画像符号化装置及び動画像符号化プログラムの実施形態（以下、第２の実施形態と呼ぶ）を、図面を参照しながら詳述する。
【００７３】
ここで、第２の実施形態の動画像符号化装置の全て又は一部は、ハードウェアによって構築することもできるが、ＣＰＵとＣＰＵが実行するプログラムで構築することもできる。
【００７４】
上述した第１の実施形態では、１フレーム内で各ブロックの計算量の調整を行うものであったが、この第２の実施形態は、１フレーム内で計算量の調整を行うのではなく、複数フレーム単位で各フレームの符号化に要する計算量の調整を行おうとしたものであり、フレーム毎に必要となる計算量のばらつきを考慮し、実時間処理を考慮した複数フレーム単位の計算量を、必要とする計算量が多いフレームには多く、必要とする計算量が少ないフレームには少なく割り当てようとしたものである。
【００７５】
（Ｂ−１）第２の実施形態の構成
第２の実施形態の動画像符号化装置は、上述したように、複数フレーム単位で各フレームの符号化に要する計算量の割り当てを行うものであり、図７は、第２の実施形態の動画像符号化装置の全体構成を示すブロック図である。
【００７６】
図７において、第２の実施形態の動画像符号化装置は、計算量制御バッファ３１、計算量予測部３２、計算量制御部３３及び符号化部３４を有する。
【００７７】
計算量制御バッファ３１は、計算量制御を行うフレームを複数取り入れ保存する記憶装置である。計算量制御とは、バッファ内の各フレームの符号化に要する計算量の和が予め定めた総計算量を超えないように各フレームに計算量を割り当てる制御である。
【００７８】
図８は、計算量制御バッファ３１における２面構成の説明図である。計算量制御バッファ３１は、並行してアクセス可能な２つのバッファ３１−１及び３１−２を有する。計算量制御バッファ３１において、一方のバッファ３１−１（又は３１−２）を画像入力用として適用しているときには、他方のバッファ３１−２（又は３１−１）を符号化処理用として適用するように切り替え制御することにより、画像（フレーム）の入力と符号化処理とを同時に行えるようにしている。ここで、各バッファ３１−１、３１−２の容量は、予め定められている所定数（２以上）のフレーム画像を格納できる容量に選定されている。
【００７９】
計算量予測部３２は、各フレームの符号化に必要と考えられる計算量を大まかに計算（予測）するものである。計算量予測部３２は、フレーム内符号化方式で符号化するフレームについては、画素値の分散等を使って計算量を予測する。例えば、分散が取り得る範囲を複数の範囲に分け、各範囲に、その範囲の計算量を対応付けたテーブルを用意しておき、得られた分散が属する範囲の計算量を予測計算量とする。また例えば、予め、分散を計算量に変換する変換関数を定めておき、この変換関数に得られた分散を入力して予測計算量を得るようにしても良い。計算量予測部３２は、フレーム間符号化方式で符号化するフレームについては参照フレームの画素値との差の絶対値和（上述したＳＡＤ）等を使って計算量を予測する。例えば、差の絶対値和が取り得る範囲を複数の範囲に分け、各範囲に、その範囲の計算量を対応付けたテーブルを用意しておき、得られた差の絶対値和が属する範囲の計算量を予測計算量とする。また例えば、予め、差の絶対値和を計算量に変換する変換関数を定めておき、この変換関数に得られた差の絶対値和を入力して予測計算量を得るようにしても良い。
【００８０】
計算量制御部３３は、計算量予測部３２で予測した各フレームに必要な計算量に基づき各フレームの計算量を割り当てるものである。また、計算量制御部３３は、割り当てた計算量に基づいて、符号化部３４がそのフレームに対する符号化を行うように制御するものである。
【００８１】
符号化部３４は、計算量制御部３３の制御下で、計算量を調節しながら、各フレームに対する符号化を行うものである。符号化部３４は、例えば、フレーム内符号化の場合には、実行するフレーム内符号化での予測モード数を調節することで符号化の計算量を調節する。モード数によって符号化の計算量が変化することについては、例えば、特開２００６−１４８４１９号公報に記載されている。符号化部３４は、例えば、フレーム間符号化の場合には、そのフレームに適用する動きベクトルの探索範囲を調節することで符号化の計算量を調節する。
【００８２】
（Ｂ−２）第２の実施形態の動作
次に、第２の実施形態の動画像符号化装置の動作を、図面を参照しながら説明する。
【００８３】
当該動画像符号化装置に入力されたフレーム（画像）は、計算量制御バッファ３１に入力され、２面あるバッファ３１−１及び３１−２の一方に記録されていく。入力フレームを記録中のバッファが詰まったら、記録してきた入力用バッファは符号化処理用に切り替えられ、符号化処理用のバッファは入力用に切り替えられる。符号化処理用のバッファを利用した符号化処理中に、入力用バッファには、新たに入力されるフレームを符号化処理と並行して記録していく（図８参照）。ここで、計算量制御バッファ３１の一方のバッファ３１−１又は３１−２に入るフレーム数（以下、ＮｕｍＯｆＦｒａｍｅとする）は予め定められている。格納フレーム数が多いとより柔軟な制御ができ、符号化効率が高くなる可能性がある反面、動画像が入力されて動画像符号が出力されるまでの遅延が長くなり、またメモリ使用量も増える。両者のトレードオフを考慮し、フレーム数ＮｕｍＯｆＦｒａｍｅを定めれば良い。
【００８４】
図９は、一方のバッファ３１−１（又は３１−２）が符号化処理用に切り替わったときから、そのバッファ３１−１が次に入力用に切り替わるまでの期間における符号化処理を示すフローチャートである。
【００８５】
バッファが切り替わったら、計算量予測部３２において、計算量制御バッファ３１の符号化処理用のバッファに格納中の各フレームの符号化に要する計算量が予測される（ステップＳ１）。
【００８６】
例えば、フレーム内符号化を行うフレームの場合には、フレームの複雑度を元に予測する。複雑度を捉える簡単な指標としては、例えば、そのフレームの画素値の分散を挙げることができる。ここで、フレーム内符号化方式としては、幾つかの予測モードに基づき、ブロックの画素値を予測し、元の画像の画素との差分を使い符号化するものを上げることができ、画像が複雑であればあるほど、より複雑な予測モードも試す必要があるので、計算量を予測するパラメータとして画像の複雑度を反映したものを適用する。
【００８７】
また例えば、フレーム間符号化の場合には、参照フレームと比べてどれだけ変化があったかによって符号化での計算量が変わってくるため、参照フレームとの相違で、符号化に要する計算量を予測する。参照フレームとの相違を捉える指標としては、例えば、動き補償を行なわない参照フレームの画素値との差の絶対値の和を挙げることができる。フレーム間符号化の場合、参照フレームにおける対応する範囲との差分を符号するため、一般的に言えば、参照フレームとの差が大きければ大きいほど、対応する範囲を探索する範囲を十分に広げて（計算量を増やして）探索しないと、符号化効率を上げることができず、そのため、参照フレームとの相違で、符号化に要する計算量を予測することとした。
【００８８】
計算量制御部３３は、各フレームの符号化処理での計算量の予測値に基づき、各フレームに計算量を割り振る（ステップＳ２）。
【００８９】
予め、ＮｕｍＯｆＦｒａｍｅフレーム数分の総計算量（ＴｏｔａｌＣｏｍｐｕｔａｔｉｏｎ）を符号化が始まる前に定めておく。ＴｏｔａｌＣｏｍｐｕｔａｔｉｏｎは、計算量予測部３２及び計算量制御部３３での処理時間も踏まえた上で、ＮｕｍＯｆＦｒａｍｅフレーム数分の符号化に要する時間が、ＮｕｍＯｆＦｒａｍｅフレーム数分のフレームがバッファ３１−１又は３１−２に入力するのに要する時間を越えないように設定する。こうすることにより、ＮｕｍＯｆＦｒａｍｅフレーム数分を入力するための遅延が生じることがあっても、符号化の実時間性を保つことができるようになる（入力用バッファが詰まる頃には符号化処理用バッファ内のフレームの符号化が終了している）。
【００９０】
次に、各フレームに符号化処理での計算量を割り当てる方法を説明する。様々な割り当て方法が考えられるが、最も簡単な方法と思われる方法は、（６）式に従って算出する方法である。
【数２】
2009153102.tif 000004
【００９１】
（６）式において、ＡｍｏｕｎｔＯｆＣｏｍｐｕｔａｔｉｏｎ［ｉ］は、ｉ（ｉは０〜ＮｕｍＯｆＦｒａｍｅ−１）番目のフレームに割り当てる計算量を表している。α［ｉ］は、フレーム内符号化かフレーム間符号化かによって異なる値をとる符号化方式の差を吸収するためのパラメータである。α［ｉ］は、ｉ番目のフレームがフレーム内符号化の場合には０＜α［ｉ］＜１の範囲内の予め定められた値をとり、フレーム間符号化の場合には１とする。このα［ｉ］は、実装によるが、フレーム間符号化処理の計算量に対するフレーム内符号化処理の計算量によって求められる値である。ＰｒｅｄＣｏｍｐ［ｉ］は、計算量予測部３２で予測されたｉ番目のフレームの計算量である。従って、（６）式は、予測計算量ＰｒｅｄＣｏｍｐ［ｉ］にα［ｉ］を乗算して符号化方式の差を吸収させた後、総計算量ＴｏｔａｌＣｏｍｐｕｔａｔｉｏｎを按分したものを、ｉ番目のフレームの割当計算量ＡｍｏｕｎｔＯｆＣｏｍｐｕｔａｔｉｏｎ［ｉ］とすることを表している。
【００９２】
計算量制御部３３は、パラメータＩを０からインクリメントさせながら、処理対象フレームを切り替えていき、Ｉ番目のフレームの符号化処理時には、Ｉ番目のフレームの割当計算量ＡｍｏｕｎｔＯｆＣｏｍｐｕｔａｔｉｏｎ［Ｉ］に基づき、符号化部３４を制御する（ステップＳ３〜Ｓ８）。
【００９３】
符号化部３４は、計算量制御部３３の制御下で、計算量制御バッファ３１からＩ番目のフレームを取り出した場合において（Ｉ−１番目のフレームの処理は終わっているとする）、新たなフレームがフレーム内符号化方式に従って符号化するフレームの場合には、関数ＮｕｍｂｅｒＯｆＭｏｄｅ（ＡｍｏｕｎｔＯｆＣｏｍｐｕｔａｔｉｏｎ［Ｉ］）により、適用する予測モード数を求め、フレーム内予測を行うモード数を制限する。入力値に対して関数ＮｕｍｂｅｒＯｆＭｏｄｅ（）が出力する値は、フレーム内符号化処理の性能により予め定めておく。符号化部３４は、計算量制御バッファ３１から取り出したＩ番目のフレームがフレーム間符号化方式に従って符号化するフレームの場合には、関数ＳｅａｒｃｈＲａｎｇｅ（ＡｍｏｕｎｔＯｆＣｏｍｐｕｔａｔｉｏｎ［Ｉ］）により、適用する動きベクトル探索範囲を求め、その探索範囲で動き探索を行ってフレーム間符号化を行う。入力値に対して関数ＳｅａｒｃｈＲａｎｇｅ（）が出力する値も、フレーム間符号化処理の性能により予め定めておく。
【００９４】
（Ｂ−３）第２の実施形態の効果
以上のように、第２の実施形態によれば、ＮｕｍＯｆＦｒａｍｅ分のフレームの符号化処理に要する処理時間を予め定めておき、これを超えないように、各フレームの予測される計算量に基づき、計算量を配分するようにしたので、計算量をあまり要しないと思われるフレームでは計算量を少なくし、使わなかった分をより多い計算量を要するフレームに振り分けることができ、符号化効率の向上を期待することができる。
【００９５】
仮に、計算量一定で符号化した場合、計算量を要さないフレームでは余分な計算を行って、計算量を要するフレームでは十分な符号化効率を期待できない。また、計算量を単純にフレームの予測される計算量に応じ可変させる方式では、計算量が一定にならず、計算量が多いフレームが連続する場合には、実時間処理が不可能となり、フレームの間引きを行う必要が生じてしまう。
【００９６】
また、ＮｕｍＯｆＦｒａｍｅ分をバッファするための遅延は発生するものの、ＮｕｍＯｆＦｒａｍｅ分のフレームに対する計算量一定の条件は満たしているので、実時間のエンコードは可能となっている。
【００９７】
（Ｃ）第３の実施形態
次に、本発明による動画像符号化装置及び動画像符号化プログラムの他の実施形態（以下、第３の実施形態と呼ぶ）を、図面を参照しながら詳述する。
【００９８】
ここで、第３の実施形態の動画像符号化装置の全て又は一部も、ハードウェアによって構築することもできるが、ＣＰＵとＣＰＵが実行するプログラムで構築することもできる。
【００９９】
第３の実施形態も、第２の実施形態と同様に、１フレーム内で計算量の調整を行うのではなく、複数フレーム単位で各フレームの符号化に要する計算量の調整を行おうとしたものである。
【０１００】
（Ｃ−１）第３の実施形態の構成
図１０は、第３の実施形態の動画像符号化装置の全体構成を示すブロック図であり、第２の実施形態に係る図７との同一、対応部分には同一符号を付して示している。
【０１０１】
図１０に示すように、第３の実施形態の動画像符号化装置の場合、符号化部３４から、各フレームにおける符号量が計算量予測部３２へフィードバックされるようになされており、計算量予測部３２は、このフィードバックされた符号量も利用して計算量を予測する。なお、各フレームに対する計算量の予測方法が変更になったため、計算量制御部３３による各フレームに対する割当て計算量の決定方法も、第２の実施形態のものとは異なるようになっている。
【０１０２】
（Ｃ−２）第３の実施形態の動作
次に、第３の実施形態に係る動画像符号化装置の動作を説明する。
【０１０３】
第３の実施形態に係る動画像符号化装置も基本的な動作の流れは、第２の実施形態と同様である。すなわち、所定数のフレーム単位に、入力用バッファと符号化処理バッファとを切り替える。新たな切り替えが起こると、計算量予測部３２が各フレームについて符号化処理での計算量を予測し、計算量制御部３３が、所定数のフレームに対する総計算量を、各フレームの予測計算量に応じて、各フレームに振り分け、符号化部３４は、計算量制御部３３の制御下で、各フレームについて、割り当てられた計算量に応じた符号化処理を実行する。
【０１０４】
しかしながら、計算量予測部３２での予測計算量の求め方と計算量制御部３３での計算量制御の仕方が、第３の実施形態は第２の実施形態と異なっている。図１１は、第３の実施形態における計算量予測部３２での予測計算量の求め方と計算量制御部３３での計算量制御の仕方を、動作プログラム的に示している。なお、図１１では、フレームを「画面」という用語で表現している。
【０１０５】
図１１における１行目Ｒ１は、処理単位となっているフレーム数をＮとした場合、その処理単位内での各フレームを規定するパラメータＩを０から１インクリメントずつ変化させながら、そのパラメータＩでの処理を繰り返すことを表しており、パラメータＩがＮに達したときに処理を終了させることを表している。従って、パラメータＩが新たな値になったときには（新たなフレームを指示するようになったときには）、その新たな値について、２行目Ｒ２〜６行目Ｒ６の処理が実行することを表している。
【０１０６】
２行目Ｒ２の処理は、計算量予測部３２が行う計算量の予測処理である。「前画面（前フレーム）の符号量」は符号化部３４からフィードバックされた値であり、この実際の符号量と、標準的な符号量との差を求め、それに所定のパラメータα（第２の実施形態のものと意味は異なる）を掛けた右辺第２項を、符号化効率を表すものとしている。第２項の符号化効率が大きいほど前画面で符号化効率が悪かったことを示し、現画面（パラメータＩで定まる現フレーム）でより計算量を増やすべく、この符号化効率を予測計算量に反映する。なお、符号化の最初の画面（Ｉが０でのフレーム）の場合には適当な初期値を使う。また、前画面が現画面と同じ符号化方式でない場合（現画面がフレーム間符号化方式で前画面がフレーム内符号化方式の場合、又は、現画面がフレーム内符号化方式で前画面がフレーム間符号化方式の場合）には、前画面の計算量に適当なパラメータをかける。
【０１０７】
３行目Ｒ３〜６行目Ｒ６の処理は、計算量制御部３３が行う処理である。
【０１０８】
３行目Ｒ３の処理は、現画面について実際に割り当てる計算量を求める処理である。「予測計算量」と、割当て可能な残量Ｓの１画面当たりに割り当てられる平均的な計算量Ｓ／（Ｎ−Ｉ）との重み付け加算によって、現画面について実際に割り当てる計算量を求めている。割当て可能な残量Ｓの初期値は、Ｎフレームに対して予め定められている総計算量である。
【０１０９】
４行目Ｒ４の処理は、３行目Ｒ３の処理で割り当てられた現画面についての計算量が、割当て可能な残量Ｓ（若しくは、残量Ｓを残りフレーム数で除算した値の所定倍（１より大きい値））を超えていた場合には、現画面についての割り当て計算量を、割当て可能な残量Ｓの１画面当たりに割り当てられる平均的な計算量Ｓ／（Ｎ−Ｉ）に置き換える処理である。これにより、未割当ての画面に対する割当て可能な量をそれなりに残すようにしている。
【０１１０】
５行目Ｒ５の処理は、３行目Ｒ３の処理又は４行目Ｒ４の処理により決定された現画面についての割り当て計算量に基づき、符号化部３４の符号化処理を制御する処理である。
【０１１１】
６行目Ｒ６の処理は、現画面についての割り当て計算量分だけ、割当て可能な残量Ｓを少なくする処理である。
【０１１２】
（Ｃ−３）第３の実施形態の効果
第３の実施形態によれば、第２の実施形態と同様に、計算量をあまり要しないと思われるフレームでは計算量を少なくし、使わなかった分をより多い計算量を要するフレームに振り分けることができ、符号化効率の向上を期待することができる。
【０１１３】
第３の実施形態によれば、第２の実施形態に比べ、各フレームにおける符号化処理の計算量の予測に費やす計算量を少なくすることができる。
【０１１４】
（Ｄ）他の実施形態
上記各実施形態の説明でも、種々変形実施形態に言及したが、さらに、以下に例示するような変形実施形態を挙げることができる。
【０１１５】
上記各実施形態におけるフレーム間符号化方式に供する参照フレームと入力フレームの差は、１フレームに限定されるものではない。また、参照フレームが入力フレームより過去のフレームに限定されるものでもない。
【０１１６】
上記第１の実施形態では、１フレーム内の各ブロック処理に計算量（探索範囲の大きさ）の割当てを行うものを示し、第２及び第３の実施形態では、複数フレーム内の各フレーム処理に計算量の割当てを行うものを示したが、これらの技術思想を併用するようにしても良い。例えば、第２又は第３の実施形態の方法で計算量が割り振られたフレーム間符号化方式に従うフレームに対し、そのフレーム内の各ブロック処理に第１の実施形態の方法によって計算量を割当てるようにしても良い。
【図面の簡単な説明】
【０１１７】
【図１】第１の実施形態に係るフレーム間符号化装置（フレーム間符号化部）の詳細構成を示すブロック図である。
【図２】第１の実施形態のフレーム間符号化装置が適用された動画像の実時間符号化装置の全体構成を示すブロック図である。
【図３】動きベクトルの検出方法の説明図である。
【図４】探索範囲と入力ブロックとの関係を示す説明図である。
【図５】第１の実施形態における動きの探索範囲の一部決定手順を示すフローチャートである。
【図６】第１の実施形態における周辺ブロックの説明図である。
【図７】第２の実施形態に係る動画像符号化装置の全体構成を示すブロック図である。
【図８】第２の実施形態における計算量制御バッファの２面構成の説明図である。
【図９】第２の実施形態に係る動画像符号化装置の動作を示すフローチャートである。
【図１０】第３の実施形態に係る動画像符号化装置の全体構成を示すブロック図である。
【図１１】第３の実施形態の動画像符号化装置における計算量予測部及び計算量制御部の動作プログラムを示す説明図である。
【符号の説明】
【０１１８】
１３…フレーム間符号化部、２１…ブロック分割部、２２…動き探索部、２３…動き補償部、２４…変換量子化逆量子化逆変換部、２５…符号化部、２６…参照バッファ管理部、２７…探索範囲制御部、３１…計算量制御バッファ、３２…計算量予測部、３３…計算量制御部、３４…符号化部。
【図１】
2009153102.tif 000005
【図２】
2009153102.tif 000006
【図３】
2009153102.tif 000007
【図４】
2009153102.tif 000008
【図５】
2009153102.tif 000009
【図６】
2009153102.tif 000010
【図７】
2009153102.tif 000011
【図８】
2009153102.tif 000012
【図９】
2009153102.tif 000013
【図１０】
2009153102.tif 000014
【図１１】
2009153102.tif 000015