(57)【要約】【課題】単位探索範囲あたりの探索演算コストを抑え、かつ探索範囲を効率よく決定することを可能とする動きベクトル検出動作を実現した動画符号化方法と動画符号化回路を提供する。【解決手段】動きベクトル検出の傾向情報を利用して、動きベクトルの探索範囲を探索の過程において動的に最適な位置に変更し、最適な動きベクトルを検出することができる。また、動きベクトル探索の過程において動きベクトル候補に対する閾値を設けることにより動きベクトルを得るに必要な演算量を最適化し、余剰となった演算量を次の動きベクトルを得るのに必要な演算量に加えることにより、探索範囲を拡大し最適な動きベクトルを検出することができる。【選択図】　　　図４
2004048512.tif 000002
【特許請求の範囲】
【請求項１】
動画像の各フレームをブロックに分割し、各符号化ブロックを参照フレームからのフレーム間予測を用いて符号化する動画像符号化方法であって、
上記各符号化ブロックを参照フレームからのフレーム間予測を用いて符号化する動画像符号化の動きベクトル検出における各符号化ブロックの動きベクトルの探索において、動きベクトル探索の過程で検出される動きベクトル候補が探索領域のどの部分に偏在するかを示す情報である動きベクトルの傾向情報を用いて探索範囲を動的に変形させて最適な動きベクトルを探索してなることを特徴とする動画像符号化方法。
【請求項２】
請求項１において、
各符号化ブロックの動きベクトルの探索において、動きベクトル探索演算における個々の動きベクトル候補の判定演算時の終了閾値を設けて動きベクトル候補の判定演算を強制的に終了させることにより発生する余剰な演算時間を用いて探索範囲を拡大してより最適な動きベクトルを探索してなることを特徴とする動画像符号化方法。
【請求項３】
請求項１において、
各符号化ブロックの動きベクトルの探索において、動きベクトル探索の過程で検出される動きベクトル候補の加算平均を求め、動きベクトル候補の平均値の座標として保持することにより、動きベクトル探索の過程におけるその時点までの動きベクトルの傾向情報として用いてなることを特徴とする動画像符号化方法。
【請求項４】
請求項１において、
現フレームと参照フレームの時間的距離、符号化ブロックのフレーム間予測における予測誤差、符号化ブロックのフレーム内予測における予測符号量、現フレームの符号化ブロックと時間的に相関の高い過去のフレームの符号化ブロックに対する動きベクトルの大きさあるいは向き、現フレームの符号化ブロックと空間的に相関の高い現フレームの符号化済み符号化ブロックに対する動きベクトルの大きさあるいは向きを用いて得られる値を動きベクトル候補の判定演算時の終了閾値の初期値とし、
上記各符号化ブロックの動きベクトルの探索において、動きベクトル探索の各探索位置で検出される動きベクトル候補の絶対値差分和を利用して動きベクトル候補の判定演算時の終了閾値を探索の過程で更新してなることを特徴とする動画像符号化方法。
【請求項５】
動画像の各フレームをブロックに分割し、各符号化ブロックを参照フレームからのフレーム間予測を用いて符号化する動画像符号化回路であって、
動きベクトル探索領域の予測ブロックと符号化ブロックとの間で演算を行う動きベクトル検出手段と、
フレーム間予測における動きベクトル判定閾値を計算する動きベクトル判定閾値計算手段と、
動きベクトル探索における探索位置を制御する手段と、
現フレームにおける動きベクトル探索の過程における動きベクトル検出の傾向情報を記憶する手段とを備え、
上記動きベクトルの傾向情報を用いて探索範囲を動的に変形させて最適な動きベクトルを探索してなることを特徴とする動画像符号化回路。
【請求項６】
請求項５において、
動きベクトル探索領域の予測ブロックと符号化ブロックとの間で演算を行う動きベクトル検出手段と、
フレーム間予測における動きベクトル判定閾値を計算する動きベクトル判定閾値計算手段と、
動きベクトル探索における探索位置を制御する手段と、
動きベクトル探索における所要演算量を記憶する演算量メモリとを備え、
個々の動きベクトル候補の判定演算時の終了閾値を設けて動きベクトル候補の判定演算を強制的に終了させることにより発生する余剰な演算時間を用いて探索範囲を拡大してより最適な動きベクトルを探索してなることを特徴とする動画像符号化回路
【請求項７】
請求項５において、
動きベクトル探索の過程で検出される動きベクトル候補の加算平均を求める手段と、
動きベクトル候補の平均値の座標を保持する手段とを備え、
動きベクトル探索の過程におけるその時点までの動きベクトルの傾向情報として用いてなることを特徴とする動画像符号化回路。
【請求項８】
請求項５において、
現フレームと参照フレームの時間的距離を記憶する手段と、
符号化ブロックのフレーム間予測における予測誤差を記憶する手段と、
符号化ブロックのフレーム内予測における予測符号量を記憶する手段と、
現フレームの符号化ブロックと時間的に相関の高い過去のフレームの符号化ブロックに対する動きベクトルの大きさあるいは向きを記憶する手段と、
現フレームの符号化ブロックと空間的に相関の高い現フレームの符号化済み符号化ブロックに対する動きベクトルの大きさあるいは向きをを記憶する手段と、
終了閾値の初期値を算出する手段と、
終了閾値を記憶する手段と、
各符号化ブロックの動きベクトルの探索において、動きベクトル探索の各探索位置で検出される動きベクトル候補の絶対値差分和から終了閾値を更新する手段とを備え、
動きベクトル探索の各探索位置で検出される動きベクトル候補の絶対値差分和を利用して動きベクトル候補の判定演算時の終了閾値を探索の過程で更新してなることを特徴とする動画像符号化回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、動画像符号化方法と動画像符号化回路に関し、特に、動画像の符号化技術におけるフレーム間予測符号化を行うための動きベクトル検出技術に利用して有効な技術に関するものである。
【０００２】
【従来の技術】
ＭＰＥＧ（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）　などの動画像符号化方式において、動画像シーケンスの各フレームを符号化ブロックに分割し、符号化ブロック毎に過去や未来、または過去と未来のフレームから検出した動きベクトルを用いて予測ブロックを求める動き補償フレーム間予測とフレーム間予測を用いず符号化ブロック自身を符号化するフレーム内符号化がある。
【０００３】
本願発明に先立って検討された動画像符号化器のブロック図を図１０に示す。この動画像符号化器は、入力画像６１１を一時的に記憶する入力フレームメモリ６０１、符号化ブロックと予測ブロックの差分ブロックを計算する減算器６０２、差分ブロックを符号化する符号化器６０３、セレクタ６０４、動きベクトル検出回路６１０によって計算された情報から符号化モードを決定する符号化モード判定回路６０５、符号化データを復号する復号器６０６、復号された差分ブロックと予測ブロックとを加算して復号ブロックを生成する加算器６０７、予測ブロックを生成する動き補償予測回路６０８、復号された参照フレームを記憶する参照フレームメモリ６０９、動き補償フレーム間予測のための動きベクトルを算出する動きベクトル検出回路６１０から成り、符号化器６０３から符号化されたストリーム６１２が出力される。
【０００４】
以下、図１０を用いて先に検討された動画像符号化器の動作について説明する。入力画像６１１は一旦入力フレームメモリ６０１に書き込まれ、入力フレームメモリ６０１から読み出された入力画像を分割した符号化ブロックは、動きベクトル検出回路６１０に入力される。動きベクトル検出回路６１０は参照フレームメモリ６０９から参照フレームの参照画像データを読み出し、符号化ブロックとの間でマッチング誤差演算を行い動きベクトルを検出する。
【０００５】
動き補償予測回路６０８は、動きベクトル検出回路６１０によって検出された動きベクトルが示す参照画像データを参照フレームメモリ６０９から読み出し、その参照画像データを用いて予測ブロックを生成する。また、フレーム間予測における予測誤差を符号化モード判定回路６０５に出力する。符号化モード判定回路６０５は、入力フレームメモリ６０１が出力する符号化ブロックの発生符号量予測を行い、動き補償予測回路６０８が出力する予測ブロックの予測誤差を用いて、符号化ブロックの発生符号量予測と予測ブロックの予測誤差の大小比較を行なう。
【０００６】
セレクタ６０４は、符号化モード判定回路６０５によって決定された符号化方法に従って出力を切り替える。符号化ブロックの発生符号量予測の方が予測誤差より小さい場合はフレーム内符号化モードと判定する。この場合、セレクタ６０４で“０”が選択される。予測誤差の方が符号化ブロックの発生符号量予測の方より小さい場合はフレーム間予測と判定する。この場合、セレクタ６０４で動き補償予測回路６０８から出力される予測ブロックが選択される。減算器６０２は符号化ブロックと予測ブロックとの間の差分を算出する。
【０００７】
差分は動きベクトル検出回路６１０によって検出された動きベクトルとともに符号化器６０３で符号化され、符号化ストリームが出力される。符号化ストリームは復号器６０６で復号され、復号された差分ブロックは加算器６０７において予測ブロックと加算される。加算器６０７の出力は、フレームに対する予測に用いる参照フレームとして参照参照フレームメモリ６０９に記憶される。
【０００８】
動き補償予測における動きベクトル探索方法の例を図１２に示す。動きベクトルの探索方式としては、参照フレーム８０１の探索範囲８０２の予測ブロック８０４に対し、予測ブロック候補８０４と符号化フレーム８０６にある符号化ブロック８０７との間の差分を計算し、差分が最小となる候補の符号化ブロック８０７と参照フレーム上で同一の位置にあるブロック８０５から見た向きと大きさを動きベクトル８０３とするブロックマッチング方式が一般的である。
【０００９】
動き補償予測におけるブロックマッチング方式の動きベクトル探索回路の例を図１１に示す。符号化の対象となる符号化画像データ７０９と参照フレームメモリ７０８から読み出された、探索位置演算器７０１に記憶された探索位置の参照画像データ７１０が絶対値差分演算器７０２に入力され両者の絶対値差分が計算される。これを符号化ブロック内の画素分繰り返し，その結果が累算器７０３および絶対値差分和メモリ７０４に格納される。
【００１０】
符号化ブロックのすべての画素に対する演算が終了すると，その結果は最適解メモリ７０６に格納される。同時にそのときの探索位置も動きベクトル候補として格納される。以上の演算を探索範囲内で水平または垂直に１画素移動させ繰り返し行う。その演算結果は比較器７０７で過去の演算結果と比較され、絶対値差分和の小さいほうがセレクタ７０５により最適解として最適解メモリ７０６に格納される。絶対値差分和が新しい値に更新された場合は動きベクトルもそのときの探索位置に更新される。探索範囲全てについて演算を終了したとき最適解メモリに格納された値が最適な動きベクトル７１１となる。
【００１１】
このように、ブロックマッチング方式の動きベクトル探索では、符号化ブロック画素数と探索範囲画素数の積の絶対値差分演算が必要となるため、探索範囲を参照フレーム全体まで広くすると総演算量が膨大となる問題がある。このため、探索範囲を参照フレームの一部分に限定し所要演算量を抑えることが一般に行われる。
【００１２】
動きベクトルが探索範囲を超える様な動きの大きな画像が入力された場合には、適切な予測ブロックを検出することができないため符号化効率が低下する。単に探索領域の拡大を行うだけでは、先に述べたようにブロックマッチング演算の回数が増えることで演算量の増加、処理時間の増加という問題がある。ブロックマッチング演算の並列処理を行い、演算量の処理時間を抑える方法もあるが、動きベクトル検出回路の規模が大きくなるという問題がある。
【００１３】
この問題の改善手法として、過去の符号化における動きベクトル情報を利用して次の探索範囲を効率よく求める方式が特開平０５−３２８３３号公報、特開平１０−３０４３７１号公報に開示されている。
【００１４】
【発明が解決しようとする課題】
過去の符号化における動きベクトル情報は常に利用可能なわけではない。例えば、符号化開始時は過去にフレーム間予測符号化を用いて符号化されたフレームが無いため時間的過去のフレームの動きベクトル情報は全く利用できない。このため、過去の動きベクトル情報から次の探索範囲を予測する手段を有し、探索範囲を効率よく絞り込むことが可能であっても、過去の動きベクトル情報が利用できない場合も想定しなければならないため、実際には探索範囲をある程度以下にすることはできない。
【００１５】
特開平０５−３２８３３号公報や特開平１０−３０４３７１号公報で開示された改善手法では探索範囲あたりの演算量は前記図１１に示した手法に比べ削減されていないため、全体として探索演算量をある程度以下には減らすことができない。その場合、特開平０５−３２８３３号公報や特開平１０−３０４３７１号公報で開示された改善手法で設けられている次の探索範囲の予測を最適に行うための過去の動きベクトル検出時の情報を記憶するための手段を多く備えた場合、回路規模が従来の固定された範囲の探索を行う動きベクトル検出方式よりも増加する。
【００１６】
本発明は以上の問題点に鑑みなされたものであり、その目的とするところは、単位探索範囲あたりの探索演算コストを抑え、かつ探索範囲を効率よく決定することを可能とする動きベクトル検出動作を実現した動画符号化方法と動画符号化回路を提供することにある。この発明の前記ならびにそのほかの目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【００１７】
【課題を解決するための手段】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば、下記の通りである。本発明は動きベクトル検出の傾向情報を利用して、動きベクトルの探索範囲を探索の過程において動的に最適な位置に変更し、最適な動きベクトルを検出する。また、動きベクトル探索の過程において動きベクトル候補に対する閾値を設けることにより動きベクトルを得るに必要な演算量を最適化し、余剰となった演算量を次の動きベクトルを得るのに必要な演算量に加えることにより、探索範囲を拡大し最適な動きベクトルを検出する。
【００１８】
【発明の実施の形態】
本発明の動きベクトル探索方法について図１を用い説明する。この実施例の動きベクトル探索方法は、特に制限されないが、前記図１０の動画符号化器に用いられる。ある符号化ブロックの動きベクトル探索において、過去の符号化情報より予測された動きベクトル１０４の情報を元にし、動きベクトル探索を開始する時点で符号化ブロック１０９に対する初期の探索範囲１０２を決定する。決定した初期の探索範囲内で動きベクトル探索を開始する。
【００１９】
本発明ではさらに探索開始後、動きベクトル探索の過程において動きベクトル検出の傾向情報を求め、これを利用して動きベクトル探索の探索範囲をより最適な位置に変更する。また、動きベクトル探索の過程において動きベクトル探索演算における個々の動きベクトル候補の判定演算時の終了閾値を設けることにより無駄な演算を削減し、結果として発生する余剰な演算時間を利用して探索範囲を拡大する。
【００２０】
これら探索範囲の変更を動きベクトル探索が終了するまで探索の過程において随時行い、動きベクトル探索範囲をより最適な位置へ動的に変更する。動きベクトル探索が終了する時点で最終的な探索範囲１０３は初期の探索範囲１０２とは形状が異なり、また探索面積は広くなる。以上の方法により、例えば予測ブロック１０６のように初期の探索範囲１０２では探索対象とならない位置に最適解がある場合においても本発明で用いられる探索範囲１０３では動きベクトル探索を可能とし、最適な動きベクトル１０５を検出する。
【００２１】
初めに符号化する任意のブロックの動きベクトルの探索演算方法を図２と図３のフローチャートに沿って説明する。図２の▲１▼ないし▲５▼は、図３の▲１▼ないし▲５▼に対応している。符号化するブロックの探索範囲の初期値２１８、閾値（ｔｈ＿ｖａｌｕｅ）の初期値２０２、最大許容演算量（ｃ＿ｒｅｓｔ）　の初期値２０３は、次のようにして求められる。
【００２２】
探索範囲の初期値２１８は次に示す式（１）および式（２）を用いて、過去のフレームにおける同一位置ブロックの動きベクトルおよび参照フレームと符号化フレームの距離より求められる探索範囲の中心座標（ｈ＿ｐｒｄ，　ｖ＿ｐｒｄ）、符号化　するブロックの位置座標（ｋ，ｊ）、符号化ブロックの水平サイズｐ　、符号化ブロ　ックの垂直サイズｑ　、現在の探索位置（ｍ，ｌ）から次式（１）および式（２）を満たす範囲として求められる。
ａｂｓ（　ｍ　−　ｋ×ｐ　−　ｈ　＿ｐｒｄ）　＜（　ｈ＿ｍａｘ　／　２）　　　・・・・・・・・・・・・　（１）
ａｂｓ（　ｌ　−　ｊ×ｑ　−　ｖ　＿ｐｒｄ）　＜（　ｖ＿ｍａｘ　／　２）　　　・・・・・・・・・・・・　（２）
【００２３】
ここで、
ａｂｓ（　）：絶対値を計算する関数
ｋ　　　　　：符号化ブロックの水平位置
ｊ　　　　　：符号化ブロックの垂直位置
ｍ　　　　　：現在の探索位置の水平位置
ｌ　　　　　：現在の探索位置の垂直位置
ｐ　　　　　：符号化ブロックの水平サイズ
ｑ　　　　　：符号化ブロックの垂直サイズ
ｈ＿ｍａｘ　：初期探索範囲の水平方向の長さ
ｖ＿ｍａｘ　：初期探索範囲の垂直方向の長さ
である。
【００２４】
動きベクトルの探索演算で用いる閾値（ｔｈ＿ｖａｌｕｅ）の初期値２０２は、符号化するブロックの画像データから得られる閾値または符号化するブロックと同一位置ブロックの過去のフレームにおける予測符号量から得られる閾値から求める。符号化するブロックの画像データから得られる閾値は次に示す式（３）から求める。
【００２５】
【式３】
2004048512.tif 000003
【００２６】
ここで、
ｔｈ＿ｉｎ：閾値
ｎ　　　　：ブロック内の画素数
ａｎ　　　：符号化ブロックの画素データ
ｐ　　　　：符号化ブロックの水平サイズ
ｑ　　　　：符号化ブロックの垂直サイズ
ａｂｓ（　）　　：絶対値を計算する関数
ｍｅａｎ（　）　　：ブロック内画素の平均値
である。
【００２７】
符号化するブロックと同一位置ブロックの過去のフレームにおける予測符号量から得られる閾値は、符号化するブロックと同一位置ブロックの過去のフレームにおける予測符号量に対し、前回の動きベクトル探索時の絶対値差分和に参照フレームと符号化フレームの距離で決定する係数を乗じた値から求められる。閾値（ｔｈ＿ｖａｌｕｅ）の初期値２０２は、符号化するブロックと同一位置ブロックの過去のフレームにおける予測符号量から得られる閾値が無い場合、式（３）から得られる符号化するブロックの画像データから得られる閾値を用いる。逆に、符号化するブロックと同一位置ブロックの過去のフレームにおける予測符号量から得られる閾値がある場合、式（３）から得られる符号化するブロックの画像データから得られる予測符号量から得られる閾値と符号化するブロックと同一位置ブロックの過去のフレームにおける閾値を比較し、値の小さい方を閾値（ｔｈ＿ｖａｌｕｅ）の初期値２０２として用いる。
【００２８】
最大許容演算量（ｃ＿ｒｅｓｔ）　の初期値２０３は、初期状態の探索範囲形状を完全に探索した場合の所要演算時間とし、式（４）で示す値とする。
ｃ＿ｒｅｓｔ　＝　ｈ＿ｍａｘ　×　ｖ＿ｍａｘ　×　ｐ×ｑ　　　　　　　　　　・・・・・・・・・・・・　（４）
【００２９】
ここで、
ｃ＿ｒｅｓｔ　　：所要演算量初期値
ｐ　　　　　　　：符号化ブロックの水平サイズ
ｑ　　　　　　　：符号化ブロックの垂直サイズ
ｈ＿ｍａｘ　　　：初期探索範囲の水平方向の長さ
ｖ＿ｍａｘ　　：初期探索範囲の垂直方向の長さ
である。
【００３０】
探索位置（ｘ，ｙ）の初期値２１９は、初期探索範囲の中心座標（ｈ＿ｐｒｄ，　ｖ＿ｐｒｄ）と初期探索範囲の水平方向の長さ　ｈ＿ｍａｘ　および初期探索範囲の垂直方向の長さｖ＿ｍａｘ　から求められる値である。また、探索画素相対位置（ｉ）　は探索位置（ｘ，ｙ）の初期値２１９からの相対的な画素位置を示し、２０４にて探索画素相対位置（ｉ）を０にする。次に、絶対値差分和（ａｂｓｄｉｆｆ）の初期値２０５および探索ブロックない画素位置（ｊ）の初期値２０６を０にした後、パターンマッチング演算の実行に移る。
【００３１】
絶対値差分和演算２０７は、探索位置（ｘ，ｙ）と探索ブロック内画素位置（ｊ）で示された位置の符号化ブロックの画像データと参照ブロックの画像データから得られる絶対値差分値を絶対値差分和（ａｂｓｄｉｆｆ）に加算し、その結果を再び絶対値差分和（ａｂｓｄｉｆｆ）に代入する。
【００３２】
絶対値差分和（ａｂｓｄｉｆｆ）の値が閾値（ｔｈ＿ｖａｌｕｅ）の値よりも小さいとき、探索ブロック内に最適な動きベクトル候補が得られる可能性があると判断し２０９に移る。逆に、絶対値差分和（ａｂｓｄｉｆｆ）の値が閾値（ｔｈ＿ｖａｌｕｅ）以上の値になったとき、探索ブロック範囲内にさらなる最適な動きベクトル候補が得られないと判断し２１５に移る。絶対値差分和演算が符号化ブロックの全画素数に対し完了していない場合、２１０にて最大許容演算量（ｃ＿ｒｅｓｔ）を減算する。
【００３３】
２１１は演算量の制限による絶対値差分和演算の打ち切りを示す。２１１にて最大許容演算量（ｃ＿ｒｅｓｔ）が０になった場合、符号化ブロックの画全素分の絶対値差分和演算が終了していなくても符号化ブロックの動きベクトルの探索を終了する。逆に、最大許容演算量（ｃ＿ｒｅｓｔ）が０でない場合、探索ブロック内画素位置（ｊ）の値を１加算し、次の画素との絶対値差分和演算２０７を行う。
【００３４】
２０９にて絶対値差分和演算２０７が符号化ブロックの全画素数に対し行われた場合、それまでに得られた動きベクトル候補が探索ブロック内の最適なものとなるため、２１３にて動きベクトルの更新を行う。また、そのときの絶対値差分和（ａｂｓｄｉｆｆ）は探索ブロック内の最適な閾値となるため、２１４にて閾値の更新を行う。
【００３５】
２１５にて、探索範囲内の全ての画素に対し符号化ブロックの画像データと参照ブロックの画像データとの比較が終了していない場合、２１６にて次の探索範囲の中心座標（　ｈ＿ｐｒｄ，　ｖ＿ｐｒｄ）の演算を行う。探索範囲の中心座標を水平方向移動させるか、垂直方向に移動させるかは任意である。２１５にて、探索範囲内の全ての画素に対し符号化ブロックの画像データと参照ブロックの画像データとの比較が終了した場合、２１７に移りパターンマッチング演算は終了する。このとき、探索範囲内での最適な動きベクトルが得られる。
【００３６】
本発明の動きベクトル探索回路による探索演算と閾値の関係について図４を用いて説明する。１回のパターンマッチング演算に必要な演算量を　ｍと仮定する。絶対値差分和が　ｎ　（但しｍ＞ｎ）の演算量で閾値を超えた場合、その探索位置はそれ以上演算を続けても最適な動きベクトル候補を得られないと判断され、図４（ａ）のグラフに示すようにその探索位置の演算はブロック内画素分の演算が終了していなくても途中で打ち切る。ｍからｎを減じた演算量が次回以降のパターンマッチング演算に繰り越される。
【００３７】
１回のパターンマッチング演算が演算途中で閾値に達せずにブロック内画素すべてについて終了した場合、そのときの探索位置および絶対値差分和が動きベクトル候補として選択される。またこの場合、図４（ｂ）のグラフに示すように、絶対値差分和が閾値を下回っているのでその絶対値差分和が次回以降のパターンマッチング演算における新たな閾値として選択される。
【００３８】
以上の演算を探索位置毎に行うと、閾値の変化は図４（ｃ）のようになる。パターンマッチング演算が演算途中で閾値に達することなく動きベクトル候補が検出された個所が図中○で示された位置であり、その中から◎の探索個所が最適解として選択される。すべての探索範囲において絶対値差分和が閾値を上回り、動きベクトルが検出されない場合はフレーム内符号化と判定し処理する。
【００３９】
動きベクトル検出の傾向情報について説明する。動きベクトル検出の傾向情報とは、符号化ブロックの動きベクトル探索の過程において検出される動きベクトル候補が探索領域のどの部分に偏在するかを示す情報である。動きベクトル検出の傾向情報で得られる動きベクトル候補を多く検出できる部分に、動きベクトル探索を集中させれば、最適な動きベクトルを検出できる可能性が大きくなる。
【００４０】
水平または垂直方向に探索を行う場合において、ある１ラインの探索が終了した時点で動きベクトル候補の座標（ｈ＿ｖｅｃ２，ｖ＿ｖｅｃ２）が検出されるとする。次ライン以降の探索が進むに従い動きベクトル候補の加算平均を求め、動きベクトル候補の平均値の座標（ｈ＿ｐｒｄ２，ｖ＿ｐｒｄ２）として保持する。
ｈ＿ｐｒｄ２　＝　ｈ＿ｐｒｄ２×（（ｔ−１）／ｔ）　＋　　ｈ＿ｖｅｃ２×（１／ｔ）　・・・・・・・・（５）
ｖ＿ｐｒｄ２　＝　ｖ＿ｐｒｄ２×（（ｔ−１）／ｔ）　＋　　ｖ＿ｖｅｃ２×（１／ｔ）　　　　　・・・・・・（６）
ここで、ｔ　：そのラインまでに求められた動きベクトル候補の総数である。
【００４１】
得られた動きベクトル候補の平均値の座標を、そのラインまで動きベクトル探索が終了した時点での動きベクトル検出の傾向情報とする。水平または垂直方向に探索を行う場合、１ラインの探索が終了した時点で初期の探索範囲の中心座標（ｈ＿ｐｒｄ，　ｖ＿ｐｒｄ）に対して動きベクトル候補の平均値の座標（ｈ＿ｐｒｄ２，ｖ＿ｐｒｄ２）を追加し、探索範囲を決定する式（１）および式（２）は以下の式（７）および式（８）に示すように変形する。
ａｂｓ（ｍ　−　ｋ　×　ｐ　−　（　ｈ＿ｐｒｄ＋　ｈ＿ｐｒｄ２）／２　）　＜　（ｈ＿ｍａｘ／２）　　　・・・・（７）
ａｂｓ（ｌ　−　ｊ　×　ｑ　−　（　ｖ＿ｐｒｄ＋　ｖ＿ｐｒｄ２）／２　）　＜　（ｖ＿ｍａｘ／２）　　　・・・・（８）
【００４２】
ここで、
ａｂｓ（　）：絶対値を計算する関数
ｋ　　　：符号化ブロックの水平位置
ｊ　　：符号化ブロックの垂直位置
ｍ　　：現在の探索位置の水平位置
ｌ　　：現在の探索位置の垂直位置
ｐ　　：符号化ブロックの水平サイズ
ｑ　　：符号化ブロックの垂直サイズ
ｈ＿ｍａｘ　：初期の探索範囲の水平方向の長さ
ｖ＿ｍａｘ　：初期の探索範囲の垂直方向の長さ
ｈ＿ｐｒｄ　：初期の探索範囲の中央の水平位置
ｖ＿ｐｒｄ　：初期の探索範囲の中央の垂直位置
ｈ＿ｐｒｄ２：動きベクトル候補の平均値の水平位置
ｖ＿ｐｒｄ２：動きベクトル候補の平均値の垂直位置
である。但し、水平方向に探索を行う場合は式（８）は適用せず、垂直方向に探索を行う場合は式（７）は適用しない。
【００４３】
図５に動きベクトル検出の傾向情報と探索範囲の変化の関係を示す。ｌｉｎｅ０で示すライン上の探索範囲の探索が終了した時点で動きベクトル最適解候補４０３が得られたと仮定する。この結果を式（５）から式（８）に当てはめると、ｌｉｎｅ１で示すライン上の探索範囲の位置は初期の探索範囲と比較して左へ２画素移動する。
【００４４】
ｌｉｎｅ１で示すライン上の探索範囲の探索が終了した時点で動きベクトル最適解候補が得られなかった場合、探索位置は変化しない。ｌｉｎｅ２で示すライン上の探索範囲の探索が終了した時点で動きベクトル最適解候補４０２が得られたと仮定する。この結果を式（５）から式（８）に当てはめると、ｌｉｎｅ３で示すライン上の探索範囲の位置は初期の探索範囲と比較して左へ３画素移動される。このような処理をライン毎に繰り返す。
【００４５】
その結果として、ライン毎に探索範囲が移動し、探索範囲は動きベクトル検出情報が示す位置に探索の中心が近づくように変形する。このように、動きベクトル探索過程で実際に求まった動きベクトル検出の傾向情報を以降の探索範囲に反映させることで、より適切な探索範囲へ変更が可能となる。
【００４６】
図６に絶対値差分演算の演算量と探索範囲の変化の関係を示す。閾値判定により動きベクトル探索が途中で打ち切られた場合、実際に行われた絶対値差分演算の演算量は打ち切られなかった場合のパターンマッチングの所要演算量より少ない。この演算量の差分を繰越演算量として記憶しておく。繰り越された演算量を１つの探索位置におけるパターンマッチング演算の所要演算量で割った値の画素分だけ探索範囲を追加することが可能となる。１ライン分の動きベクトル探索演算が終了した時点での繰越演算量から追加可能な次のラインの探索範囲を広くする。
【００４７】
図６はブロックサイズが水平２画素、垂直２画素の場合のある符号化ブロックの動きベクトル探索を示す。図は探索範囲のｌｉｎｅ０で示すライン上の探索位置の探索における絶対値差分和および絶対値差分演算回数を示す。１ラインの初期の探索範囲５０２は１１画素であり、ブロックサイズから得られる必要な絶対値差分演算回数は４４回である。
【００４８】
図６で絶対値差分和が閾値５０３を上回っている部分はパターンマッチング演算が途中で打ち切られる。その結果、実際に行われる絶対値差分演算回数５０５は２５となる。差分の１９回は繰越演算量となる。これを１回のパターンマッチングに必要な絶対値差分演算回数である４で割った商は４となり、４画素分の探索ができる演算量が繰り越されたことを意味する。図７の５０９に示すように次のｌｉｎｅ１で繰り越された演算量を利用して探索範囲を左右２画素拡大することが可能となる。この処理がライン毎に繰り返されると、探索範囲は初期の探索範囲よりも広くなるように変化する。
【００４９】
以上に述べた動きベクトル探索範囲の変形および拡大の効果について、前記図１を用い説明する。動きベクトル探索過程で実際に求まった動きベクトル検出の傾向情報を以降の動きベクトル探索に動的に反映させることで、最終的な探索範囲１０３は初期の探索範囲１０２よりも適切な探索位置へ変更される。また、探索の過程において絶対値差分演算を最適に行い余剰となった演算量を用いて探索範囲を拡大するので、最終的な探索範囲１０３は初期の探索範囲１０２よりも広くなる。
【００５０】
このように、従来手法において初期の探索範囲１０２で示される範囲を探索する為に必要な演算量で、本発明では最終的な探索範囲１０３で示される範囲の探索が可能となる。その結果、例えば予測ブロック１０６のように従来の手法では探索できなかった位置とのパターンマッチングが可能となり、最適な動きベクトル１０５が検出可能となる。
【００５１】
本発明に係る動きベクトル探索回路の一実施例のブロック図を図８に示す。この実施例は、特に制限されないが、前記図１０の動画符号化器の動きベクトル検出回路として用いられる。
【００５２】
本発明の動きベクトル探索方法を用いた動きベクトル探索回路は、参照画像データの探索位置を制御する探索位置演算器９０１、動きベクトル探索の総演算時間を格納する演算量メモリ９０２、符号化画像データ９１３および過去の符号化情報９１２より閾値初期値を算出する閾値初期値演算器９０３、算出された閾値初期値を格納する閾値メモリ９０４、閾値および最適解を選択するセレクタ９０５、各探索位置の絶対値差分演算時の演算結果と閾値を比較する比較器９０６、符号化の対象となる符号化画像データ９１３と参照フレームメモリから読み出された参照画像データの絶対値差分を計算する絶対値差分演算器９０７、絶対値差分演算器９０７の結果を符号化ブロック内の画素分累算する累算器９０８およびそれを格納する絶対値差分和メモリ９０９、最適な動きベクトル候補と絶対値差分和を格納する最適解メモリ９１０からなり、最適解メモリ９１０から動きベクトル探索結果である動きベクトル９１４と次に過去の符号化情報として用いられる絶対値差分和９１５が出力される。
【００５３】
図２、図３で示した本発明の動きベクトル探索方法の探索範囲の初期値２１８は探索位置演算器９０１で求められる。閾値の初期値２０２は閾値初期値演算器９０３で行われる。閾値初期値演算器９０３は、符号化画像データ９１３および過去の符号化情報９１２より閾値初期値を算出する。算出された閾値初期値は閾値メモリ９０４に格納する。最大許容演算量設定２０３は演算量メモリ９０２で行われる。演算量メモリ９０２は動きベクトル探索の総演算時間を格納する。
【００５４】
探索位置の初期値２１９は探索位置演算器９０１の制御部で行われる。絶対値差分和の初期化２０５およびブロック内画素位置の初期化２０６は絶対値差分和メモリ９０９の制御時に行われる。絶対値差分和演算２０７は絶対値差分演算器９０７、累算器９０８および絶対値差分和メモリ９０９で行われる。
【００５５】
符号化の対象となる符号化画像データ９１３と参照フレームメモリから読み出された探索位置演算器９０１に記憶された探索位置の参照画像データ９１２が絶対値差分演算器９０７に入力され両者の絶対値差分が計算される。計算結果は累算器９０８で絶対値差分和メモリ９０９が出力する、それまでの絶対値差分和演算結果に加算され絶対値差分和メモリ９０９へ再び格納される。
【００５６】
閾値と絶対値差分和の比較２０８は比較器９０６で行われる。各探索位置の絶対値差分演算２０７の演算結果が比較器９０６で閾値と比較され、絶対値差分和が閾値以上の値になった場合、その探索位置以降の絶対値差分演算は打ち切られる。閾値との比較が符号化ブロック画素数分行われたどうかの判断は絶対値差分和メモリ９０９の制御時に行われる。
【００５７】
絶対値差分和演算２０７を符号化ブロックの画素分繰り返し、その結果が累算器９０８および絶対値差分和メモリ９０９に格納される。演算量の再設定２１０は演算量メモリ９０２の制御時に行われる。絶対値差分和演算終了時にその位置の動きベクトル探索の所要演算時間を計算し、求まった値を演算量メモリ９０２に格納された値から減じる。
【００５８】
残り演算量の判定は演算量メモリ９０２の制御時に行われる。判定の結果、演算量メモリの値が０となった場合は以降の動きベクトル探索演算を打ち切る。探索ブロック内画素位置２１２の制御は絶対値差分和メモリの制御時に行われる。動きベクトル更新２１３は比較器９０６、セレクタ９０５および最適解メモリ９１０で行われる。各探索位置の絶対値差分演算終了時に絶対値差分和メモリ９０９の値が閾値メモリ９０４の値を下回っていた場合、絶対値差分和メモリ９０９に格納されている値が最適解として最適解メモリ９１０に格納される。
【００５９】
最適解メモリ９１０に格納されている絶対値差分和が新しい値に更新された場合は最適解メモリ９１０に格納されている動きベクトルもそのときの探索位置から求まる動きベクトルを新しい値として更新する。閾値更新２１４は比較器９０６、セレクタ９０５および閾値メモリ９０４で行われる。探索位置の再設定２１６は探索位置演算器９０１の制御時に行われる。
【００６０】
２０５から２１２の動作を探索位置演算器９０１で探索範囲内を水平または垂直に１画素ずつ移動させ繰り返し行う。探索終了の判定２１５は探索位置演算器９０１の制御時に行われる。探索範囲全てについて演算を終了したとき最適解メモリに格納された値が最適な動きベクトルとなり、最適解メモリ９１０から出力される。
【００６１】
図９には、この発明が適用された携帯電話装置の一実施例のブロック図が示されている。マイク（送話器）、スピーカ（受話器）に対応して音声インターフェスが設けられる。アンテナに対応して送信電波を出力し、受信電波を入力する高周波インターフェイスが設けられる。カメラに対応して画像インターフェイスが設けられる。画像インターフェイスには、アナログ画像信号をデジタル画像信号に変換するＡＤ変換回路も含まれる。信号処理はマイクロプロセッサ、ＤＳＰ（デジタル・シグナル・プロセッサ）及びＡＳＩＣ（論理回路）からり、かかる信号処理回路に前記図１０の符号化回路とそれに用いられる図８に示したような動きベクトル検出回路が含まれる。
【００６２】
また、データを記憶するメモリ回路が設けられる。メモリ回路は、ダイナミック型ＲＡＭ、スタティック型ＲＡＭや不揮発性メモリ（フラッシュメモリ）が用いられる。そして、液晶コントローラ（ＬＳＩ）と液晶パネルが設けられて必要な表示動作が行われる。ダイヤル入力や文字入力のためのスイッチ（ボタンや動作モードの切り替えを行うスイッチ（ボタン）は、信号処理部に含まれる。このような携帯電話装置では、動画像処理が高速に行われるために高品質の動画情報を送信及び受信することができる。それ故、この発明に係る動画像符号化方法及び符号化回路は、携帯テレビ電話装置に好適なものとなる。
【００６３】
以上本発明者よりなされた発明を実施例に基づき具体的に説明したが、本願発明は前記実施例に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。動画像符号化方法そのものは種々の実施形態を採ることができる。この発明は、動画符号化方法又は動画符号化回路における動きベクトルを探索に広く利用できる。
【００６４】
【発明の効果】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。本発明は動きベクトル検出の傾向情報を利用して、動きベクトルの探索範囲を探索の過程において動的に最適な位置に変更し、最適な動きベクトルを検出することができる。また、動きベクトル探索の過程において動きベクトル候補に対する閾値を設けることにより動きベクトルを得るに必要な演算量を最適化し、余剰となった演算量を次の動きベクトルを得るのに必要な演算量に加えることにより、探索範囲を拡大し最適な動きベクトルを検出することができる。
【図面の簡単な説明】
【図１】この発明に係る動きベクトル探索方法の説明図である。
【図２】この発明に係る動きベクトル探索方法を説明するための一部フローチャート図である。
【図３】この発明に係る動きベクトル探索方法を説明するための残り一部フローチャート図である。
【図４】この発明に係る動きベクトル探索方法の閾値判定動作の説明図である。
【図５】この発明に係る動きベクトル探索方法の変形例の説明図である。
【図６】この発明に係る動きベクトル探索方法の閾値判定動作の拡大図説明図である。
【図７】この発明に係る動きベクトル探索方法の説明図である。
【図８】この発明に係る動きベクトル探索回路の一実施例を示すブロック図である。
【図９】この発明が適用された携帯電話機の一実施例を示すブロック図である。
【図１０】本願発明に先立って検討された動画像符号化器のブロック図である。
【図１１】図１０の動きベクトル探索回路のブロック図である。
【図１２】図１０の動き補償予測における動きベクトル探索方法の説明図である。
【符号の説明】
１０１…参照フレーム、１０２…初期の探索範囲、１０３…最終的な探索範囲、１０４…過去の符号化情報により予測された動きベクトル、１０５…検出された動きベクトル、１０６…予測ブロック、１０７…符号化ブロックと同一位置にあるブロック、１０８…符号化フレーム、１０９…符号化ブロック、２０１〜２１９…本発明の動きベクトル探索方法の演算処理ステップ、
４０１…実際の探索範囲、４０２…ｌｉｎｅ２の動きベクトル最適解候補、４０３…ｌｉｎｅ０の動きベクトル最適解候補、４０４…初期の探索範囲、４０５…過去のフレーム情報により予測された探索位置の中心座標、　　　　　　　　　　　　５０１…絶対値差分和、５０２…初期の探索範囲、５０３…閾値、５０４…探索位置、５０５…演算回数、５０６…実際の探索範囲、５０７…初期の探索範囲、５０８…過去のフレーム情報により予測された探索位置の中心座標、５０９…追加された探索領域、
６０１…入力フレームメモリ、６０２…減算器、６０３…符号化器、６０４…セレクタ、６０５…符号化モード判定回路、６０６…復号器、６０７…加算器、６０８…動き補償予測回路、６０９…参照フレームメモリ、６１０…動きベクトル検出回路、６１１…入力画像、６１２…符号化ストリーム、
７０１…探索位置演算器、７０２…絶対値差分演算器、７０３…累算器、７０４…絶対値差分和メモリ、７０５…セレクタ、７０６…最適解メモリ、７０７…比較器、７０８…参照画像フレームメモリ、７０９…符号化画像データ、７１０…参照画像データ、７１１…動きベクトル、７１２…絶対値差分和、
８０１…参照フレーム、８０２…探索範囲、８０３…動きベクトル、８０４…予測ブロック、８０５…符号化ブロックと同一位置にあるブロック、８０６…符号化フレーム、８０７…符号化ブロック、
９０１…探索位置演算器、９０２…演算量メモリ、９０３…閾値初期値演算器、９０４…閾値メモリ、９０５…セレクタ、９０６…比較器、９０７…絶対値差分演算器、９０８…累算器、９０９…絶対値差分和メモリ、９１０…最適解メモリ、９１１…参照フレームメモリ、９１２…過去の符号化情報、９１３…符号化画像データ、９１４…動きベクトル、９１５…絶対値差分和。
【図１】
2004048512.tif 000004
【図２】
2004048512.tif 000005
【図３】
2004048512.tif 000006
【図４】
2004048512.tif 000007
【図５】
2004048512.tif 000008
【図６】
2004048512.tif 000009
【図７】
2004048512.tif 000010
【図８】
2004048512.tif 000011
【図９】
2004048512.tif 000012
【図１０】
2004048512.tif 000013
【図１１】
2004048512.tif 000014
【図１２】
2004048512.tif 000015