(57)【要約】【課題】符号化効率の劣化を抑えながら、低演算量で動画像を符号化する。【解決手段】粗探索手段１は、第１のサイズのブロック単位で現画像画素と参照画像画素の差分値を算出し、差分値から得られる指標により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択する第１の動き探索手段３と、第１のサイズより小さい第２のサイズのブロック単位で、第１の動き探索手段が算出した差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択する第２の動き探索手段４と、第１の動きベクトルのコストと第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正手段５とを含む。密探索手段２は、密探索手段２が選択した動きベクトルにもとづいてブロックサイズを決定するブロックサイズ選択手段６を含む。【選択図】図１５
2016181799.tif 000002
【特許請求の範囲】
【請求項１】
現画像と参照画像との間の動きベクトルを用いる動画像符号化システムであって、
探索範囲内の一部のベクトルの動き探索を行い動きベクトルを選択する粗探索手段と、
前記粗探索手段が選択した動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択する密探索手段とを備え、
前記粗探索手段は、
第１のサイズのブロック単位で現画像画素と参照画像画素の差分値を算出し、前記差分値から得られる指標により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択する第１の動き探索手段と、
前記第１のサイズより大きい第２のサイズのブロック単位で、前記第１の動き探索手段が算出した差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択する第２の動き探索手段と、
前記第１の動きベクトルのコストと前記第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正手段とを含み、
前記密探索手段は、
当該密探索手段が選択した前記動きベクトルにもとづいてブロックサイズを決定するブロックサイズ選択手段を含む
ことを特徴とする動画像符号化システム。
【請求項２】
粗探索手段は、
探索範囲内の動きベクトルのうちの一部を第１の候補ベクトルとして選出する第１の候補ベクトル選出手段を備え、
第１の動き探索手段は、第１のサイズのブロック単位で、第１の候補ベクトルに対して動き探索を行い、前記第１の候補ベクトルの中から、現画像画素と参照画像画素の差分値から得られる指標から算出するコストが最小となる動きベクトルを選択し、
第２の動き探索手段は、第２のサイズのブロック単位で、第１の候補ベクトルに対して当該第２のサイズのブロックが内包する第１のサイズのブロックについて動き探索を行い、前記第１の候補ベクトルの中から、前記第１の動き探索手段が算出した画素差分値を集計することにより得られる指標から算出するコストが最小となる動きベクトルを選択し、
前記第１のサイズのブロックは、前記第２のサイズのブロックを分割して複数得られるブロックであり、
ベクトル修正手段は、第１の動きベクトルのコストの合計が第２の動きベクトルのコストよりも大きければ、前記第１のサイズのブロックにおける第１の動きベクトルを前記第２のサイズのブロックにおける第２の動きベクトルで更新する
請求項１記載の動画像符号化システム。
【請求項３】
密探索手段は、
粗探索手段が選択した動きベクトルを起点として得られる動きベクトルである第２の候補ベクトルを選出する第２の候補ベクトル選出手段と、
第２の候補ベクトルのうち、第２のサイズのブロックが内包するすべての第１のサイズのブロックにおいて前記第２の候補ベクトルが選出されている場合に、当該第２の候補ベクトルを第３の候補ベクトルとして選出する第３の候補ベクトル選出手段と、
第１のサイズのブロック単位で、前記第２の候補ベクトルに対して現画像画素と参照画像画素の差分値を算出し、前記差分値を集計することにより得られる指標からコストを算出し、当該コストが最小となる動きベクトルを第３の動きベクトルとして選択する第３の動き探索手段と、
第２のサイズのブロック単位で、前記第３の候補ベクトルに対して、当該第２のサイズのブロックが内包する第１のサイズのブロックについて前記第３の動き探索手段が算出した差分値から得られる指標からコストを算出し、当該コストが最小となる動きベクトルを第４の動きベクトルとして選択する第４の動き探索手段とを備え、
ブロックサイズ選択手段は、
前記第２のサイズのブロックに内包する前記第１のサイズのブロックにおける第３の動きベクトルのコストの合計と、前記第２のサイズのブロックにおける前記第４の動きベクトルのコストにもとづいて、いずれかのブロックサイズを選択し、選択したブロックサイズのブロックにおいて算出した動きベクトルを出力する
請求項１または請求項２記載の動画像符号化システム。
【請求項４】
密探索手段は、第２のサイズのブロックより大きいサイズのブロック単位で、第３の動き探索手段が算出した差分値から得られる指標により算出されるコストが最小となる動きベクトルを選択する少なくとも一つの動き探索手段をさらに備え、
前記ブロックのサイズは、所定の最大サイズを階層的に分割したサイズであり、
ブロックサイズ選択手段は、第３の動き探索手段、第４の動き探索手段および前記動き探索手段を含む３つ以上の動き探索手段から得た動きベクトルを取得し、ブロックサイズを選択する
請求項３記載の動画像符号化システム。
【請求項５】
現画像と参照画像とを縮小する縮小手段を備え、
粗探索手段は、縮小されたブロックサイズにおいて動き探索を行う
請求項１から請求項４のうちのいずれか１項に記載の動画像符号化システム。
【請求項６】
異なる縮小率に現画像と参照画像とを縮小する複数の縮小手段と、
前記縮小手段から画像を取得し、所定の最大サイズを階層的に分割した異なるサイズのブロックについて動き探索を行う１つ以上の階層探索手段をさらに備え、
密探索部および各前記階層探索手段は、
１階層上位の探索手段が行う処理の少なくとも一部を行い動きベクトルを選択する上位階層探索手段と、
対象階層の候補ベクトルを選出する対象階層候補ベクトル選出手段と、
対象階層の動き探索を行い動きベクトルを選択する対象階層動き探索手段と
前記上位階層探索手段が選択した動きベクトルのコストと、前記対象階層動き探索手段が選択した動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正手段とを含む
請求項５に記載の動画像符号化システム。
【請求項７】
探索範囲内の一部のベクトルの動き探索を行い動きベクトルを選択し、選択された前記動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択することにより、現画像と参照画像との間の動きベクトルを検出して符号化を行う動画像符号化方法であって、
第１のサイズのブロック単位で現画像画素と参照画像画素の差分値を算出し、前記差分値から得られる指標により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択し、
前記第１のサイズより大きい第２のサイズのブロック単位で、前記差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択し、
前記第１の動きベクトルのコストと前記第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正し、
修正された前記動きベクトルの周囲の所定範囲のベクトルの動き探索を行うことにより選択された動きベクトルにもとづいて、ブロックサイズを決定する
ことを特徴とする動画像符号化方法。
【請求項８】
コンピュータに、
探索範囲内の一部のベクトルの動き探索を行い動きベクトルを選択し、選択された前記動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択することにより、現画像と参照画像との間の動きベクトルを検出して符号化を行わせるための動画像符号化プログラムであって、
コンピュータに、
第１のサイズのブロック単位で現画像画素と参照画像画素の差分値を算出し、前記差分値から得られる指標により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択する第１の動き探索処理と、
前記第１のサイズより大きい第２のサイズのブロック単位で、前記差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択する第２の動き探索処理と、
前記第１の動きベクトルのコストと前記第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正処理と、
修正された前記動きベクトルの周囲の所定範囲のベクトルの動き探索を行うことにより選択された動きベクトルにもとづいて、ブロックサイズを決定するブロックサイズ決定処理とを
実行させるための動画像符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像符号化システム、動画像符号化方法、および動画像符号化用プログラムに関する。
【背景技術】
【０００２】
近年、動画像の解像度向上要求が年々高まっており、それに伴って、符号化技術もＭＰＥＧ−２，Ｈ．２６４／ＭＰＥＧ−４  ＡＶＣ（以下Ｈ．２６４），Ｈ．２６５／ＨＥＶＣ（以下Ｈ．２６５）と圧縮効率を向上するように進歩してきた。これらの符号化方式は、フレーム間の動き補償予測を用いて情報を圧縮することにより高い符号化効率を達成している。なお、非特許文献１にはＨ．２６５規格に基づく処理の内容が記載されている。Ｈ．２６５動画像符号化の処理は、ＣＵ（Ｃｏｄｉｎｇ  Ｕｎｉｔ）と呼ばれる最大６４×６４画素のブロック単位で行われる。
【０００３】
動き補償予測は、符号化対象フレームと符号化済みの参照フレームの間の動き情報を用いて参照フレームの画像を補正し、補正された画像（予測画像）と符号化対象となる現画像の差分情報とフレーム間の動きを表す情報のみを符号化することにより動画像情報を圧縮する技術である。フレーム間の動きは移動量を表す動きベクトルによって表現される。参照フレームと符号化対象フレーム間の動き情報を算出する処理を動き推定という。動き推定では、デコード画像に発生するノイズ量を抑えつつ符号化する情報量も最小化できる動き情報を算出することが重要である。
【０００４】
このため、近年の動画像符号化装置では、ＲＤ（Ｒａｔｅ−Ｄｉｓｔｏｒｔｉｏｎ）最適化と呼ばれる手法が広く用いられている。ＲＤ最適化は、多数の動きベクトル候補に対して、Ｊ=Ｄ＋λＲと表されるレート歪みコストを算出し、これが最小になるものを動きベクトルとして採用する技術である。ここで、Ｄは差分画像に発生する歪み量、Ｒは動き情報の符号化で発生する符号量、λは画像の複雑さなどに依存する重み係数である。動き情報は、動きベクトル情報やＣＵサイズ情報を含む。歪み量Ｄとして、一般に、符号化対象フレーム画像の画素と予測画像の画素の絶対値差分和ＳＡＤ（Ｓｕｍ  ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ）が用いられる。ＳＡＤは、以下の式（１）により計算される。
【０００５】
【数１】
2016181799.tif 000003
【０００６】
ここで、Ｓ（ｘ，ｙ）は動きベクトルが指し示す参照フレーム画像の画像ブロック内の相対的な座標（ｘ，ｙ）における画素値、Ｃ（ｘ，ｙ）は符号化対象フレームの画像である現画像の座標（ｘ，ｙ）における画素値を示す。多数の動きベクトル候補のレート歪みコストを算出するＲＤ最適化による動きベクトル探索は演算量が非常に多いことが課題である。
【０００７】
Ｈ．２６５／ＨＥＶＣでは、ＣＵサイズが可変であるため効率的に符号量が圧縮され、利用者が、最大サイズ６４×６４のブロックを階層的に四分木分割した６４×６４，３２×３２，１６×１６，８×８画素サイズのＣＵから最適なＣＵサイズを選択することができる。さらに動き補償予測では、２Ｎ×２ＮサイズのＣＵを動き情報を保持する単位であるＰＵ（Ｐｒｅｄｉｃｔｉｏｎ  Ｕｎｉｔ）に分割し処理が行われる。利用者は、ＰＵサイズとして、２Ｎ×２Ｎ，２Ｎ×Ｎ，Ｎ×２ＮまたはＮ×Ｎサイズから最適なブロックサイズを選択することができる。そのため、Ｈ．２６５／ＨＥＶＣを用いると、平坦な部分では大きなブロックで符号化することで動き情報の符号量を削減することができ、細かな変化のある部分は小さなブロックで符号化することで差分画像の歪み量を削減することができる。
【０００８】
しかし、最適なＣＵ，ＰＵサイズを選択するためには全てのＣＵサイズにおける全てのＰＵサイズの動きベクトル探索を行い各ブロックサイズのＲＤコストを比較して最小コストとなるＣＵ，ＰＵサイズを決定する必要がある。ＣＵ，ＰＵサイズの選択は画質に大きな影響を与える一方で、多数のＣＵ、ＰＵサイズに対する動きベクトル探索処理の演算量は非常に多い。特に、４Ｋなど高解像度向けの実用的なエンコーダの実装では全てのＣＵ、ＰＵサイズでの動きベクトル探索を実施するのは現実的ではない。特に、Ｈ．２６５では選択できるブロックサイズの種類が１３種類であり、Ｈ．２６４の７種類に比べて増えたため、演算量がさらに多くなっている。
【０００９】
以下では、ＣＵとＰＵを合わせたものをブロックと称する。低演算量で複数のブロックサイズのコストを算出する手法として、ＳＡＤ再利用法がある。これは、同一ベクトルの４つのブロックのＳＡＤの合計値が１階層大きいブロックのＳＡＤ値と等しくなることを利用するものである。同一動きベクトルであれば、例えば、６４×６４ブロックのＳＡＤは４つの内包する３２×３２ブロックのＳＡＤの合計である。同様に、３２×３２ブロックは４つの１６×１６ブロック、１６×１６ブロックは４つの８×８ブロック、８×８ブロックは４つの４×４ブロックのＳＡＤを合計することによりＳＡＤ値を得ることができる。ただし、算出する動きベクトルが下位階層ブロックの全ての動きベクトルと同一でなければ、ＳＡＤ値を合計しても求める動きベクトルのＳＡＤ値とはならない。
【００１０】
最下階層ブロックにおける動き探索のアルゴリズムとして探索範囲の全てのＳＡＤ値を算出してコストを比較する全探索法を用いた場合には、すべてのブロックサイズで同一の動きベクトル候補のコストが算出される。そのため、最小ブロックにおける動き探索の過程で得られる各候補ベクトルのＳＡＤ値からすべてのサイズのブロックの全候補ベクトルのＳＡＤ値を算出することができる。
【００１１】
一方で、全探索法は探索範囲の全てのコストを比較する必要があるため、最小ブロックの動き探索だけでも非常に演算量が大きく、特に４Ｋなどの高解像度向けの実用的なエンコーダでは現実的ではない。演算量を削減するためにダイヤモンドサーチなど適応的に探索位置、探索範囲を変更する探索手法もあるが、この探索手法ではブロックごとにＳＡＤ値を計算する候補ベクトルが異なるため、大きなサイズのブロックにＳＡＤ値を再利用できないことが多い。
【００１２】
非特許文献２には、全探索よりも演算量の少ない階層探索を用いることで、最小ブロックにおける探索量を削減しながらＳＡＤ値再利用を行う方法が示されている。階層探索では、まず縮小画像を用いて広範囲の粗探索を行う。次に粗探索で得られた最小コストとなる動きベクトルの周辺の狭範囲のみを元サイズの画像で密探索する。これにより、広範囲を少ない演算量で探索することができる。
【００１３】
非特許文献２では、例えば、まず画像を１／２に縮小した上で４×４ブロック単位（縮小前の元サイズでは８×８ブロック相当）の粗探索を行う。次の密探索では粗探索の最小コストの動きベクトルの周辺を探索するが、この時元サイズにおける４つの４×４ブロックは粗探索における縮小時には同一の４×４ブロックに含まれている。そのため、密探索でも探索範囲が同一すなわち同一の候補ベクトル群を探索することとなる。
【００１４】
これにより、４×４ブロックと８×８ブロックのレート歪みコスト計算におけるＳＡＤ値は再利用可能であり、４×４ブロックの動き探索で得られるＳＡＤ値を合計するだけで８×８ブロックの候補ベクトルのＳＡＤ値が得られる。また、１６×１６以上のブロックについても、４つの４×４ブロックごとに探索範囲は異なるが、全ての４×４ブロックにおけるＳＡＤ値が計算されている候補ベクトルに限りＳＡＤ値の再利用によりコストが計算できる。
【００１５】
粗探索の探索範囲が狭い場合、粗探索で得られる最小コストベクトルは狭い探索範囲内に限定される。すなわち、ばらつきが小さい。密探索では粗探索で得られた最小コストベクトルの周辺を探索するので、粗探索で得られる最小コストベクトルのばらつきが小さければ、４×４ブロックにおける密探索での探索範囲のばらつきも小さくなる。そのため、粗探索での探索範囲が狭い場合には、全ての１６×１６ブロック内の全ての４×４ブロックで同一候補ベクトルのＳＡＤ値を計算する可能性がある、すなわち１６×１６ブロックでＳＡＤ値の再利用ができる可能性が少なくない。
【００１６】
しかし、低解像度処理では探索範囲が狭くてよいが、特に高解像度処理では圧縮効率のために探索範囲を広くする必要がある。例えば、ある物体が画面の半分横に動いたとすると、１９２０×１０８０画素画像では探索範囲が９６０画素あれば動きを捉えられるが、３８４０×２１６０画素画像では探索範囲が１９２０画素ないと動きを捉えられないからである。探索範囲を広くすると、密探索での探索範囲がばらつきやすく、ＳＡＤ値を再利用して、１６×１６以上のサイズのブロックのコストを計算するのが困難になる。
【００１７】
また、非特許文献２で対象としているＨ．２６４／ＡＶＣではブロックサイズは４×４から１６×１６までだったが、Ｈ．２６５／ＨＥＶＣでは４×４から６４×６４とブロック階層がより深い。そのため、Ｈ．２６５／ＨＥＶＣの高圧縮効率を達成するためには大きなブロックサイズをより積極的に選択する必要がある。非特許文献２に記載されている技術では、１６×１６よりもさらに大きなブロックではＳＡＤ値の再利用が困難になる。例えば６４×６４のような大きなブロックのＳＡＤ値を求めるには、内包されている２５６個の全ての４×４ブロックで同一候補ベクトルのＳＡＤ値が計算されていなければならない。非特許文献２に記載されている技術では、ＳＡＤ値が再利用できずコストが計算できないブロックサイズは選択されないため、６４×６４などの大きなサイズのブロックを選択できる可能性が低くなり、圧縮効率が悪化する。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】ITU-T Recommendation H.265 '' High efficiency video coding，'' Apr 2013.
【非特許文献２】Ates， H.F.， Altunbasak， Y. "SAD reuse in hierarchical motion estimation for the H.264 encoder"， Proc.  Acoustics， Speech， and Signal Processing， vol.2， pp.ii/905，ii/908， March 2005.
【発明の概要】
【発明が解決しようとする課題】
【００１９】
図１６は、非特許文献２に記載されている動き推定を実現するシステムの構成例である。図１７は、図１６に示すサブ探索部の構成例を示すブロック図である。図１６に示す動き推定システムは、現画像と参照画像を例えば１／２サイズに縮小する縮小部１５と、１６×１６ブロック単位ごとに処理を行い、縮小画像を用いて広範囲を探索する粗探索部１１と、狭範囲を詳細に探索する密探索部１２から構成される。
【００２０】
粗探索部１１は、縮小された探索範囲内の全ベクトルを候補として選出する第１の候補ベクトル選出部１３と、縮小された現画像と参照画像を用いて、選出された候補ベクトルのうちレート歪みコストが最小となる動きベクトルを探索する第１の動き探索部１４からなる。第１の動き探索部１４は、例えば１６×１６を１／２に縮小した８×８ブロックにおいて４つの４×４ブロックに対して動きベクトルを探索する。
【００２１】
密探索部１２は、１６×１６ブロック内の４つの８×８ブロックに対してそれぞれ４×４ブロック単位と８×８ブロック単位の動き探索を行うサブ探索部１８と、１６×１６ブロックにおける候補ベクトルを選出する第３の候補ベクトル選出部１６と、選出された候補ベクトルを１６×１６ブロックの単位で探索する第２の動き探索部１７とブロックサイズを４×４，８×８，１６×１６から選択するブロックサイズ選択部１９とからなる。
【００２２】
サブ探索部１８は、図１７に示すように、４×４ブロックと８×８ブロックの密探索での候補ベクトルを選出する第２の候補ベクトル選出部２０と、選出された候補ベクトルを４×４ブロック単位で探索する第３の動き探索部２１と、８×８ブロック単位で探索する第４の動き探索部２２とからなる。
【００２３】
第２の候補ベクトル選出部２０は、対応する８×８ブロックにおける第１の動き探索部１４が出力した動きベクトルを起点として得られる候補ベクトルを選出する。第２の候補ベクトル選出部２０は、例えば、第１の動き探索部１４が出力した動きベクトルの周囲の９ベクトルを候補ベクトルとして選出する。第３の動き探索部２１は、選出された候補ベクトルに対して４×４ブロック単位でＳＡＤを算出して動き探索を行いレート歪みコストが最小となる動きベクトルを選択する。第３の動き探索部２１は、さらに各候補ベクトルに対するＳＡＤ値を第２の動き探索部２２に出力する。第４の動き探索部２２は、各候補ベクトルに対して、第３の動き探索部２１が算出したＳＡＤを４ブロック分合計することで８×８ブロックのＳＡＤを算出してレート歪みコストを算出し、最小コストとなる動きベクトルを選択する。
【００２４】
図１６に示す、第３の候補ベクトル選出部１６は、第２の候補ベクトル選出部２０が選出した候補ベクトルのうち、１６×１６ブロックが内包する４つの８×８ブロックすべてで選出された候補ベクトルのみを１６×１６ブロックの候補ベクトルとして選出する。４つの８×８ブロックの探索範囲が異なれば１６×１６ブロックの候補ベクトルは選出されないこともある。
【００２５】
第２の動き探索部１７は、第３の候補ベクトル選出部１６が選出した各候補ベクトルに対して、第１の動き探索部２１が算出したＳＡＤを１６ブロック分合計することにより１６×１６ブロックのＳＡＤを算出してレート歪みコストを算出し、最小コストとなる動きベクトルを選択する。
【００２６】
ブロックサイズ選択部１９は、第３の動き探索部２１、第４の動き探索部２２、第２の動き探索部１７から出力されるレート歪みコストから、１６×１６ブロックのコストを最小化するブロックサイズを選択し、選択されたサイズの動きベクトルとともに出力する。
【００２７】
上記のような、非特許文献２に記載された技術では、演算量は削減しながらも、平坦な画面のときにも大きいサイズのブロックが選択されにくく圧縮効率が低下することが課題である。
【００２８】
そこで、本発明は、符号化効率（圧縮効率及び画質）の劣化を抑えながら、低演算量で動画像を符号化する動画像符号化システム、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２９】
本発明による動画像符号化システムは、現画像と参照画像との間の動きベクトルを用いる動画像符号化システムであって、探索範囲内の一部のベクトルの動き探索を行い動きベクトルを選択する粗探索手段と、粗探索手段が選択した動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択する密探索手段とを備え、粗探索手段は、第１のサイズのブロック単位で現画像画素と参照画像画素の差分値を算出し、差分値から得られる指標により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択する第１の動き探索手段と、第１のサイズより大きい第２のサイズのブロック単位で、第１の動き探索手段が算出した差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択する第２の動き探索手段と、第１の動きベクトルのコストと第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正手段とを含み、
密探索手段は、当該密探索手段が選択した動きベクトルにもとづいてブロックサイズを決定するブロックサイズ選択手段を含むことを特徴とする。
【００３０】
本発明による動画像符号化方法は、探索範囲内の一部のベクトルの動き探索を行い動きベクトルを選択し、選択された動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択することにより、現画像と参照画像との間の動きベクトルを検出して符号化を行う動画像符号化方法であって、第１のサイズのブロック単位で現画像画素と参照画像画素の差分値を算出し、差分値から得られる指標により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択し、第１のサイズより大きい第２のサイズのブロック単位で、差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択し、第１の動きベクトルのコストと第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正し、修正された動きベクトルの周囲の所定範囲のベクトルの動き探索を行うことにより選択された動きベクトルにもとづいて、ブロックサイズを決定することを特徴とする。
【００３１】
本発明による動画像符号化プログラムは、コンピュータに、探索範囲内の一部のベクトルの動き探索を行い動きベクトルを選択し、選択された動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択することにより、現画像と参照画像との間の動きベクトルを検出して符号化を行わせるための動画像符号化プログラムであって、コンピュータに、第１のサイズのブロック単位で現画像画素と参照画像画素の差分値を算出し、差分値から得られる指標により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択する第１の動き探索処理と、第１のサイズより大きい第２のサイズのブロック単位で、差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択する第２の動き探索処理と、第１の動きベクトルのコストと第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正処理と、修正された動きベクトルの周囲の所定範囲のベクトルの動き探索を行うことにより選択された動きベクトルにもとづいて、ブロックサイズを決定するブロックサイズ決定処理とを実行させることを特徴とする。
【発明の効果】
【００３２】
本発明によれば、符号化効率（圧縮効率及び画質）の劣化を抑えながら、低演算量で動画像を符号化することができる。
【図面の簡単な説明】
【００３３】
【図１】第１の実施形態における動画像符号化システムの構成を示すブロック図である。
【図２】第１の実施形態における動画像符号化システムの動作の概要を示すフローチャートである。
【図３】第１の実施形態における動画像符号化システムの粗探索部の動作を示すフローチャートである。
【図４】第１の実施形態における動画像符号化システムの密探索部の動作を示すフローチャートである。
【図５】第２の実施形態における動画像符号化システムの構成を示すブロック図である。
【図６】第２の実施形態における動画像符号化システムのサブ探索部の構成を示すブロック図である。
【図７】第２の実施形態における動画像符号化システムの動作の概要を示すフローチャートである。
【図８】第２の実施形態における動画像符号化システムの粗探索部の動作を示すフローチャートである。
【図９】第２の実施形態における動画像符号化システムの密探索部の動作を示すフローチャートである。
【図１０】第３の実施形態における動画像符号化システムの構成を示すブロック図である。
【図１１】第３の実施形態における動画像符号化システムのサブ探索部の構成を示すブロック図である。
【図１２】第３の実施形態における動画像符号化システムの第２階層探索部の動作を示すフローチャートである。
【図１３】第３の実施形態における動画像符号化システムの第３階層探索部の動作を示すフローチャートである。
【図１４】第３の実施形態における動画像符号化システムの第４階層探索部の動作を示すフローチャートである。
【図１５】本発明による動画像符号化システムの概要を示すブロック図である。
【図１６】非特許文献２に記載されている動き推定を実現するシステムの構成例を示すブロック図である。
【図１７】図１６に示すサブ探索部の構成例を示すブロック図である。
【発明を実施するための形態】
【００３４】
次に、発明を実施するための形態を、図面を参照して詳細に説明する。
【００３５】
実施形態１．
本発明では、粗探索においてもＳＡＤ値を再利用して複数サイズのブロックのレート歪みコストを比較し、その結果により粗探索における動きベクトル、ひいては密探索における探索範囲を修正することを特徴とする。これにより、多数の小ブロックで同一の候補ベクトルを探索する可能性を高め、大きなサイズのブロックを選択しやすくなり、圧縮効率が向上できる。本実施形態では、粗探索において縮小画像を用いずにおおまかなベクトルを探索する探索法である粗密探索による例を説明する。
【００３６】
図１は、本実施形態の動画像符号化システムの構成を示すブロック図である。本実施形態における動画像符号化システムは、例えば８×８ブロック単位で、広範囲を大まかに探索する粗探索部１０１と、粗探索部１０１が出力する動きベクトルを取得し、粗探索の結果の周囲の所定範囲（狭範囲）を詳細に動き探索し動きベクトルを選択する密探索部１０２とを備える。また、動画像符号化システムは、密探索部１０２が選択した動きベクトルを用いて現画像の符号化を行う。密探索部１０２は、粗探索部１０１が出力する動きベクトルを取得する。図１に示す各構成要素は、例えば、特定の演算処理等を行うよう設計されたハードウェア、またはプログラムに従って動作するコンピュータによって実現される。また、そのプログラムは、非一時的でコンピュータが読み取り可能な記憶媒体に記憶される。
【００３７】
粗探索部１０１は、第１の候補ベクトル選出部１０３と、４つの第１の動き探索部１０４と、第２の動き探索部１０５と、ベクトル修正部１０６とを含む。密探索部１０２は、４つの第２の候補ベクトル選出部１０７と第３の候補ベクトル選出部１０８と、４つの第３の動き探索部１０９と、第４の動き探索部１１０と、ブロックサイズを決定するブロックサイズ選択部１１１とを含む。第２の動き探索部１０５および第４の動き探索部１１０は、８×８ブロックの動き探索を行い、第１の動き探索部１０４および第３の動き探索部１０９は、８×８ブロックに内包される４つの４×４ブロックそれぞれの動き探索を行う。本実施形態の動画像符号化システムは、粗探索部１０１が第２の動き探索部１０５とベクトル修正部１０６とを備えることを特徴とする。
【００３８】
第１の候補ベクトル選出部１０３は、広い探索範囲から、一部の候補ベクトルをまばらに選出する。たとえば、第１の候補ベクトル選出部１０３は、所定の探索範囲の全てのベクトルのうち縦横４ベクトルおきに候補ベクトルを選出する。これにより、全ベクトル数の１／１６個のベクトルが選出されることになる。第１の候補ベクトル選出部１０３は、選出した候補ベクトルを４つの第１の動き探索部１０４と第２の動き探索部１０５に出力する。これにより、４つの第１の動き探索部１０４と第２の動き探索部１０５には、同一の候補ベクトルが入力される。
【００３９】
第１の動き探索部１０４は、選出された候補ベクトルに対して４×４ブロック単位で、現画像画素と参照画像画素の差分値を算出し、差分値から得られる指標（ＳＡＤ値）を算出して動き探索を行い、複数の候補ベクトルの中から、最小コストとなる動きベクトルを選択する。第１の動き探索部１０４は、探索の過程で得られる各候補ベクトルに対応するＳＡＤ値を第２の動き探索部１０５に出力する。
【００４０】
第２の動き探索部１０５は、各候補ベクトルに対して、第１の動き探索部１０４が算出したＳＡＤ値を４ブロック分合計することにより８×８ブロックのＳＡＤ値を算出してレート歪みコストを算出し、複数の候補ベクトルの中から、最小コストとなる動きベクトルを選択する。このとき８×８ブロックに内包する４つの４×４ブロックの動きベクトルそれぞれと８×８ブロックの動きベクトルは必ずしも同一にはならない。
【００４１】
ベクトル修正部１０６は、第１の動き探索部１０４により４つの４×４ブロックについて算出された動きベクトルのレート歪みコストの合計と、第２の動き探索部１０５により８×８ブロックについて算出された動きベクトルのレート歪みコストを比較する。８×８ブロックのレート歪みコストが小さければ、ベクトル修正部１０６は、４つの４×４ブロックにおける動きベクトルを８×８ブロックにおける動きベクトルで修正（更新）し出力する。修正された４つの４×４ブロックの動きベクトルは同一となる。４×４ブロックのレート歪みコストの合計が８×８ブロックのレート歪みコストよりも小さければ、動きベクトル修正部１０６は、修正は行わない。その場合、４つの４×４ブロックの動きベクトルは必ずしも同一にはならない。
【００４２】
密探索部１０２において、第２の候補ベクトル選出部１０７は、各４×４ブロックの候補ベクトルを選出する。例えば、同一ブロックにおいて粗探索で得られた動きベクトルの周囲±４ベクトルの範囲にある８１個のベクトルを候補ベクトルとする。
【００４３】
第３の候補ベクトル選出部１０８は、８×８ブロックの候補ベクトルを選出する。具体的には、第２の候補ベクトル選出部１０７が選出した候補ベクトルのうち、８×８ブロックが内包する４つの４×４ブロックすべてで選出された候補ベクトルのみを８×８ブロックの候補ベクトルとして選出する。粗探索で得られた４つの４×４ブロックの動きベクトルが同一であれば、４つの４×４ブロックと８×８ブロックの候補ベクトルは同一となる。４つの４×４ブロックの粗探索で得られた動きベクトルが異なれば８×８ブロックの候補ベクトルは選出されないこともある。
【００４４】
第３の動き探索部１０９は、第２の候補ベクトル選出部１０７により選出された候補ベクトルに対して４×４ブロック単位で現画像画素と参照画像画素の差分値を算出し、前記差分値を集計することにより得られる指標（ＳＡＤ値）を算出して動き探索を行う。そして、第３の動き探索部１０９は、最小コストとなる動きベクトルを選択する。第３の動き探索部１０９は、各候補ベクトルに対応するＳＡＤ値を第４の動き探索部１１０に出力する。
【００４５】
第４の動き探索部１１０は、第３の候補ベクトル選出部１０８が選出した各候補ベクトルに対して、第３の動き探索部１０９が算出したＳＡＤ値を４ブロック分合計することにより８×８ブロックのＳＡＤ値を算出する。また、第４の動き探索部１１０は、ＳＡＤ値を用いてレート歪みコストを算出し、最小コストとなる動きベクトルを選択する。
【００４６】
ブロックサイズ選択部１１１は、第３の動き探索部１０９が４つの４×４ブロックについて算出した動きベクトルのレート歪みコストの合計と、第４の動き探索部１１０が８×８ブロックについて算出した動きベクトルのレート歪みコストを比較し、小さい方のブロックサイズとそのブロックにおける動きベクトルを出力する。
【００４７】
次に本実施形態の動作例を、図２から図４を用いて説明する。図２は、第１の実施形態における動画像符号化システムの動作の概要を示すフローチャートである。図２に示すように、本実施形態における動き推定では、まず、粗探索部１０１が、ある８×８ブロックの探索範囲に対して動き探索を行い動きベクトルを選択する（ステップＳ１０１）。次に、密探索部１０２が、粗探索部１０１が選択した動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択する（ステップＳ１０２）。全８×８ブロックの処理が終了していなければ（ステップＳ１０３のＮＯ）ステップＳ１０１に戻り、ステップＳ１０３がＹＥＳになるまで繰り返す。
【００４８】
次に、ステップＳ１０１における粗探索について図３を用いて詳細に説明する。図３は、第１の実施形態における動画像符号化システムの粗探索部の動作を示すフローチャートである。
【００４９】
まず、第１の候補ベクトル選出部１０３は、候補ベクトルを選出する（ステップＳ１１１）。たとえば、第１の候補ベクトル選出部１０３は、探索範囲の全てのベクトルのうち縦横４ベクトルおきに候補ベクトルを選出する。次に、第１の候補ベクトル選出部１０３が未処理の候補ベクトルを一つ選択する（ステップＳ１１２）。
【００５０】
第１の動き探索部１０４は、８×８ブロック内の４×４ブロックに対してステップＳ１１２で選択された候補ベクトルにおける４×４ブロックのＳＡＤを算出する（ステップＳ１１３）。８×８ブロック内の４つの４×４ブロックのＳＡＤ算出処理が終了していなければ（ステップＳ１１４のＮＯ）、第１の動き探索部１０４は、ステップＳ１１３のＳＡＤ算出処理を各４×４ブロックに対して繰り返す。
【００５１】
４つのブロックのＳＡＤ算出処理が終了すれば（ステップＳ１１４のＹＥＳ）、第２の動き探索部１０５は、４つの４×４ブロックのＳＡＤを合計した値を８×８ブロックのＳＡＤとして設定する（ステップＳ１１５）。すべての候補ベクトルのＳＡＤ算出処理が終了していなければ、ステップＳ１１２に戻る（ステップＳ１１６のＮＯ）。すなわち、ステップＳ１１２からステップＳ１１５がすべての候補ベクトルに対して繰り返される。
【００５２】
すべての候補ベクトルのＳＡＤ算出処理が終了すれば（ステップＳ１１６のＹＥＳ）、第１の動き探索部１０４は、ステップＳ１１３で算出された各候補ベクトルのＳＡＤを用いて４×４ブロックのレート歪みコストを算出し、コストが最小となる動きベクトルを選択する（ステップＳ１１７）。４つのブロックの動きベクトル探索が終了していなければ（ステップＳ１１８のＮＯ）、第１の動き探索部１０４は、終了していないブロックに対してステップＳ１１７の処理を行う。すなわち、第１の動き探索部１０４は、ステップＳ１１７の処理を４つの４×４ブロックに対して繰り返す。
【００５３】
４つのブロックの動きベクトル探索が終了すれば（ステップＳ１１８のＹＥＳ）、第２の動き探索部１０５は、ステップＳ１１５で算出された８×８ブロックのＳＡＤを用いて各候補ベクトルのレート歪みコストを算出し、コストが最小となる動きベクトルを選択する（ステップＳ１１９）。ベクトル修正部１０６は、４つの４×４ブロックのコストの合計と８×８ブロックのコストを比較し、４×４ブロックのコストの合計の方が大きければ（ステップＳ１２０のＹＥＳ）、４つの４×４ブロックの動きベクトルを全て８×８ブロックの動きベクトルで修正する（ステップＳ１２１）。
【００５４】
次に、ステップＳ１０２の密探索について図４を用いて詳細に説明する。図４は、第１の実施形態における動画像符号化システムの密探索部の動作を示すフローチャートである。
【００５５】
第２の候補ベクトル選出部１０７は、４×４ブロックごとに、粗探索で得られた動きベクトルのたとえば周囲±４ベクトルの範囲にある８１個のベクトルを候補ベクトルとして算出する（ステップＳ１３０）。４つの４×４ブロックにおけるステップＳ１３０が終了していなければ（ステップＳ１４４のＮＯ）、第２の候補ベクトル選出部１０７は、終了していないブロックに対してステップＳ１３０の処理を繰り返す。
【００５６】
４つの４×４ブロックにおけるステップＳ１３０が終了すれば（ステップＳ１４４のＹＥＳ）、第３の候補ベクトル選出部１０８は、８×８ブロックの候補ベクトルを選出する（ステップＳ１３１）。第３の候補ベクトル選出部１０８は、ステップＳ１３１において具体的には、ステップＳ１３０で選出した４×４ブロックの候補ベクトルのうち、８×８ブロックが内包する４つの４×４ブロックすべてで選出された候補ベクトルのみを８×８ブロックの候補ベクトルとして選出する。次に、第３の動き探索部１０９が、未処理の８×８ブロックの候補ベクトルをひとつ選択し（ステップＳ１３２）、各４×４ブロックにおけるＳＡＤ値を計算する（ステップＳ１３３）。
【００５７】
４つの４×４ブロックのＳＡＤ値の算出が終了すれば（ステップＳ１３４のＹＥＳ）、第４の動き探索部１１０は、４つの４×４ブロックのＳＡＤを合計した値を８×８ブロックのＳＡＤとして設定する（ステップＳ１３５）。すべての８×８候補ベクトルの処理が終了していなければ（ステップＳ１３６のＮＯ）、ステップＳ１３２に戻る。すなわち、密探索部１０２は、ステップＳ１３２からステップＳ１３５までをすべての８×８候補ベクトルに対して繰り返す。
【００５８】
すべての８×８候補ベクトルの処理が終了すれば（ステップＳ１３６のＹＥＳ）、第４の動き探索部１１０は、ステップＳ１３５で算出された８×８ブロックのＳＡＤを用いて各候補ベクトルのレート歪みコストを算出し、コストが最小となる動きベクトルを選択する（ステップＳ１３７）。
【００５９】
次に、第３の動き探索部１０９は、４つの４×４ブロックそれぞれに対して、ステップＳ１３０で選出した４×４ブロックの候補ベクトルのうち、ステップＳ１３２からステップＳ１３５の処理を行っていないベクトル、すなわち８×８ブロックの候補ベクトルに含まれない候補ベクトルを一つ選択し（ステップＳ１３８）、４×４ブロックのＳＡＤを算出する（ステップＳ１３９）。第３の動き探索部１０９は、ステップＳ１３８からステップＳ１３９を４×４ブロックの全ての候補ベクトルに対して繰り返す。ここで、８×８ブロックの候補ベクトルと処理する４×４ブロックの候補ベクトルが全て同じであれば、ステップＳ１３８からステップＳ１４１の処理は実施されない。
【００６０】
すべての候補ベクトルの処理が終了すると（ステップＳ１４０のＹＥＳ）、第４の動き探索部１１０は、ステップＳ１３９で算出された４×４ブロックのＳＡＤを用いて各候補ベクトルのレート歪みコストを算出し、コストが最小となる動きベクトルを選択する（ステップＳ１４１）。密探索部１０２は、ステップＳ１３８からステップＳ１４１を４つの４×４ブロックに対して繰り返す。
【００６１】
４つの４×４ブロックのステップＳ１３８からステップＳ１４１の処理が終了すると（ステップＳ１４２のＹＥＳ）、ブロックサイズ選択部１１１は、４つの４×４ブロックのコストの合計と８×８ブロックのコストを比較し、小さい方のブロックサイズと動きベクトルを出力する（ステップＳ１４３）。
【００６２】
本実施形態では、各画素の絶対値差分とＳＡＤの算出は４×４ブロックの動き探索である第１の動き探索部１０４と第３の動き探索部１０９のみが行う。そして、８×８ブロックの動き探索を行う第２の動き探索部１０５と第４の動き探索部１１０は、それぞれ第１の動き探索部１０４と第３の動き探索部１０９で得たＳＡＤの和のみを計算する。このため、本実施形態における動画像符号化システムは、動画４×４，８×８ブロックそれぞれに対して各画素の絶対値差分を算出してコストを計算する動き探索を行うよりも演算量を削減できる。また、密探索部１０２のみでＳＡＤ再利用を行う非特許文献２に記載された技術に対してもＳＡＤ演算数が増えることはない。
【００６３】
また、本実施形態の動画像符号化システムは、粗探索においても４つの４×４ブロックと８×８ブロックのレート歪みコスト比較を行い、８×８ブロックのレート歪みコストの方が小さい、すなわち８×８ブロックが適している可能性が高い場合には、４つの４×４ブロックの動きベクトルを同一とすることで密探索において８×８ブロックの候補ベクトルを多く選出することができる。そして、ブロックサイズ選択部１１１が８×８ブロックを選択する可能性が高くなり、またより適した８×８ブロックの動きベクトルが算出できるようになる。その結果、符号化効率が向上する。
【００６４】
また、本実施形態の動画像符号化システムは、粗探索の結果で８×８ブロックのコストの方が小さいとしても、密探索の探索範囲を変更するが、最終的なブロックサイズを限定しない。そのため、密探索の結果では小さいブロックのコストの方が小さければ、最終的には小さいブロックを選択する。よって密探索が終了するまで細かい動きをとらえる小さなブロックを選択する可能性がなくなることはない。
【００６５】
本実施形態では、４×４ブロックと８×８ブロックでＳＡＤ値を再利用してブロックサイズを選択する例を述べたが、これに限らず８×８ブロックと１６×１６ブロックなど他のブロックサイズでＳＡＤ値を再利用したり、４×４ブロックのＳＡＤ値を８×８，１６×１６，３２×３２，６４×６４など複数のブロックサイズのブロックのＳＡＤ値に再利用してもよい。ブロックは正方形でなくともよく、例えば、ブロックサイズが４×８，８×４などでもよい。また、探索段階が、粗探索と密探索の２段階ではなく、３以上の多段階であってもよい。特に、小さいブロックサイズのＳＡＤをより大きいブロックサイズのＳＡＤに再利用する場合に、本実施形態における大きいブロックが選択されやすくなる効果が大きくなる。
【００６６】
また、本実施形態では、歪み量の指標としてＳＡＤを用いているが、二乗差和ＳＳＤ（Ｓｕｍ  ｏｆ  Ｓｑｕａｒｅｄ  Ｄｉｆｆｅｒｅｎｃｅ）など、内包する小ブロックの値の合計が大ブロックの値となる他の指標を用いてもよい。
【００６７】
実施形態２．
本実施形態は、動き探索アルゴリズムに縮小画像を用いた階層探索を用いることを特徴とする。階層探索では、縮小した画像で粗探索を行い、本来のサイズの画像で密探索を行うことで、高探索精度で広範囲の探索が可能である。
【００６８】
本実施形態の構成例を図５から図６に示す。本実施形態の構成は、第１の実施形態の構成に画像を縮小する縮小部２０４が追加された構成である。図５は、第２の実施形態における動画像符号化システムの構成を示すブロック図である。図６は、第２の実施形態における動画像符号化システムのサブ探索部の構成を示すブロック図である。図５および図６に示す各構成要素は、例えば、特定の演算処理等を行うよう設計されたハードウェア、またはプログラムに従って動作するコンピュータによって実現される。また、そのプログラムは、非一時的でコンピュータが読み取り可能な記憶媒体に記憶される。
【００６９】
縮小部２０４は、例えば縦横１／２ずつに現画像と参照画像それぞれを縮小する。本実施形態における粗探索部２０１，密探索部２０２は、１６×１６サイズブロックごとに処理を行う。また、第１の候補ベクトル選出部２０３は、縮小画像における探索範囲の全てのベクトルを候補ベクトルとして選出する。画像を縦横１／２に縮小しているので、候補ベクトル数は全探索の１／４となる。縮小された画像で第１の動き探索部１０４と第２の動き探索部１０５はそれぞれ４×４ブロックと８×８ブロックの動き探索を第１の実施形態と同様にＳＡＤ再利用を用いて行う。ベクトル修正部１０６も第１の実施形態と同様に４×４ブロックの動きベクトルを修正する。縮小画像における４×４ブロック、８×８ブロックは縮小しない画像の８×８ブロック、１６×１６ブロックに対応する。
【００７０】
密探索では粗探索により決定された動きベクトルの周囲を縮小しない画像を用いて探索する。密探索部２０２は、８×８ブロックごとに処理する４つのサブ探索部２０５と、１６×１６ブロックの候補ベクトルを算出する第３の候補ベクトル選出部２０６と、１６×１６ブロックの動き探索を行う第４の動き探索部２０７とを備える。
【００７１】
図６に示すサブ探索部２０５は、８×８ブロックごとに４×４ブロックと８×８ブロックの動き探索を行う。サブ探索部２０５は、第２の候補ベクトル選出部１０７と第３の動き探索部１０９と第５の動き探索部１１２とを備える。
【００７２】
第２の候補ベクトル選出部１０７は、各４×４ブロックの候補ベクトルを選出する。たとえば粗探索で得られた動きベクトルの周囲±１ベクトルの範囲にある９個のベクトルを候補ベクトルとする。４つの４×４ブロックは、粗探索では同一の８×８ブロックに対応するため、密探索における４×４ブロックそれぞれの候補ベクトルと８×８ブロックの候補ベクトルは必ず全て同一である。
【００７３】
第３の動き探索部１０９は、第２の候補ベクトル選出部１０７により選出された候補ベクトルに対して４×４ブロック単位で動き探索を行い最小コストとなる動きベクトルを選択する。第３の動き探索部１０９は、各候補ベクトルに対するＳＡＤ値を第５の動き探索部１１２に出力する。
【００７４】
第５の動き探索部１１２は、第２の候補ベクトル選出部１０７が選出した各候補ベクトルに対して、第３の動き探索部１０９が算出したＳＡＤを４ブロック分合計することにより８×８ブロックのＳＡＤを算出してレート歪みコストを算出し、最小コストとなる動きベクトルを選択する。
【００７５】
第３の候補ベクトル選出部２０６は、１６×１６ブロックの候補ベクトルを選出する。具体的には、第２の候補ベクトル選出部１０７が選出した候補ベクトルのうち、１６×１６ブロックが内包する４つの８×８ブロックすべてについて選出された候補ベクトルのみを１６×１６ブロックの候補ベクトルとして選出する。４つの８×８ブロックの探索範囲が異なれば１６×１６ブロックの候補ベクトルは選出されないこともある。
【００７６】
第４の動き探索部２０７は、第３の候補ベクトル選出部２０６が選出した各候補ベクトルに対して、第３の動き探索部１０９が算出したＳＡＤを１６ブロック分合計することにより１６×１６ブロックのＳＡＤを算出してレート歪みコストを算出し、最小コストとなる動きベクトルを選択する。
【００７７】
ブロックサイズ選択部２０８は、１６つの４×４ブロックについて算出された動きベクトルのレート歪みコストの合計と、４つの８×８ブロックで求めた動きベクトルのレート歪みコストの合計と、１６×１６ブロックで求めた動きベクトルのレート歪みコストを比較し、最小のブロックサイズとそのブロックにおける動きベクトルを出力する。
【００７８】
次に本実施形態の動作例を図７から図９を用いて説明する。図７は、第２の実施形態における動画像符号化システムの動作の概要を示すフローチャートである。図７に示すように、本実施形態の動画像符号化システムにおける動き推定では、まず、縮小部２０４が、現画像と参照画像を例えば縦横１／２に縮小する（ステップＳ２０１）。
【００７９】
そして、粗探索部２０１は、ある１６×１６ブロックの探索範囲に対して縮小された画像で動き探索を行い動きベクトルを選択する（ステップＳ２０２）。次に、密探索部２０２は、粗探索部２０１が選択した動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択する（ステップＳ２０３）。全ブロックの処理が終了していなければ（ステップＳ２０４のＮＯ）ステップＳ２０２に戻り、ステップＳ２０４がＹＥＳになるまでステップＳ２０２からステップＳ２０４の処理が繰り返される。画像が１／２に縮小されているのでステップＳ２０２では、１６×１６ブロックの縦横１／２サイズである８×８ブロック単位で処理が行われることになる。
【００８０】
次に、ステップＳ２０２の粗探索について図８を用いて、詳細に説明する。図８は、第２の実施形態における動画像符号化システムの粗探索部の動作を示すフローチャートである。図８に示す本実施形態における粗探索は、図３に示す実施形態１におけるステップＳ１０１の粗探索のうち、第１の候補ベクトル選出部２０３の動作であるステップＳ２１１のみが異なる。ステップＳ２１１では、第１の候補ベクトル選出部２０３は、縮小画像における探索範囲の全てのベクトルを候補ベクトルとして選出する。図３に示す実施形態１と同様の処理については説明を省略する。
【００８１】
次にステップＳ２０３の密探索について図９を用いて詳細に説明する。図９は、第２の実施形態における動画像符号化システムの密探索部の動作を示すフローチャートである。粗探索での４×４ブロックは密探索での８×８ブロックに、粗探索での８×８ブロックは密探索での１６×１６ブロックにそれぞれ対応する。
【００８２】
第２の候補ベクトル選出部１０７は、８×８ブロックごとに、たとえば粗探索で４×４ブロックの動きベクトルとして得られたベクトルの周囲±１ベクトルの範囲にある９個のベクトルを候補ベクトルとして算出する（ステップＳ２３１）。この８×８ブロックの候補ベクトルは、内包する４つの４×４ブロックの候補ベクトルとしても使用される。
【００８３】
４つの８×８ブロックにおけるステップＳ２３１の処理が終了すれば（ステップＳ２３０のＹＥＳ）、第３の候補ベクトル選出部２０６は、１６×１６ブロックの候補ベクトルを選出する（ステップＳ２３２）。ステップＳ２３２では、第３の候補ベクトル選出部２０６は、ステップＳ２３１で選出された８×８ブロックの候補ベクトルのうち、１６×１６ブロックが内包する４つの８×８ブロックすべてで選出された候補ベクトルのみを１６×１６ブロックの候補ベクトルとして選出する。
【００８４】
次に、第３の動き探索部１０９は、未処理の１６×１６ブロックの候補ベクトルをひとつ選択する（ステップＳ２３３）。そして、第３の動き探索部１０９は、１６×１６ブロックに内包する１６個の４×４ブロックにおけるＳＡＤ値を計算する（ステップＳ１３３ａ）。
【００８５】
１６個の４×４ブロックのＳＡＤ値の算出が終了すれば（ステップＳ２３５のＹＥＳ）、第５の動き探索部１１２は、４つの４×４ブロックのＳＡＤを合計した値を８×８ブロックのＳＡＤとして設定する（ステップＳ１３５ａ）。また、第４の動き探索部２０７は、１６つの４×４ブロックのＳＡＤを合計した値を１６×１６ブロックのＳＡＤとして設定する（ステップＳ２３６）。密探索部２０２は、ステップＳ２３３からステップＳ２３６までをすべての１６×１６ブロックの候補ベクトルに対して繰り返す。
【００８６】
すべての１６×１６ブロックの候補ベクトルの処理が終了すれば（ステップＳ２３７のＹＥＳ）、第４の動き探索部２０７は、ステップＳ２３６で算出された１６×１６ブロックのＳＡＤを用いて各候補ベクトルのレート歪みコストを算出し、コストが最小となる動きベクトルを選択する（ステップＳ２３８）。
【００８７】
次に、第３の動き探索部１０９は、８×８ブロックに内包する４つの４×４ブロックそれぞれに対して、ステップＳ２３１で選出した８×８ブロックの候補ベクトルのうち、ステップＳ２３３からステップＳ２３７の処理を行っていないベクトル、すなわち１６×１６ブロックの候補ベクトルに含まれない候補ベクトルを一つ選択し（ステップＳ２３９）、４×４ブロックのＳＡＤを算出する（ステップＳ１３３ｂ）。ステップＳ２３９とステップＳ１３３ｂを４つの４×４ブロックに対して繰り返す。
【００８８】
８×８ブロック内の４つの４×４ブロックにおけるステップＳ２３９とステップＳ１３３ｂの処理が終了すると（ステップＳ２４５のＹＥＳ）、第５の動き探索部１１２は、４つの４×４ブロックのＳＡＤを合計した値を８×８ブロックのＳＡＤとして設定する（ステップＳ１３５ｂ）。密探索部２０２は、ステップＳ２３９からステップＳ２４６を８×８ブロックの全ての候補ベクトルに対して繰り返す。ここで、１６×１６ブロックの候補ベクトルと処理する８×８ブロックの候補ベクトルが全て同じであれば、ステップＳ２３９からステップＳ２４６は実施されない。
【００８９】
すべての候補ベクトルの処理が終了すると（ステップＳ２４６のＹＥＳ）、第３の動き探索部１０９は、ステップＳ１３３ｂで算出された４×４ブロックのＳＡＤを用いて各候補ベクトルのレート歪みコストを算出し、コストが最小となる４×４ブロックの動きベクトルを選択する（ステップＳ１４１）。
【００９０】
第５の動き探索部１１２は、ステップＳ１３５ｂで算出された８×８ブロックのＳＡＤを用いて各候補ベクトルのレート歪みコストを算出し、コストが最小となる８×８ブロックの動きベクトルを選択する（ステップＳ１３７）。ステップＳ２３９からステップＳ１３７を４つの８×８ブロックに対して繰り返す。４つの８×８ブロックのステップＳ２３９からステップＳ１３７の処理が終了すると（ステップＳ２４７のＹＥＳ）、ブロック選択部２０８が決定したブロックサイズと動きベクトルを出力する（ステップＳ２３８）。
【００９１】
ステップＳ２４８では、ブロックサイズ選択部２０８は、まず各８×８ブロックについて４つの４×４ブロックのコストの合計と８×８ブロックのコストを比較し、小さい方のブロックサイズを選択する。そして、ブロックサイズ選択部２０８は、選択された８×８もしくは４つの４×４のコストを４つの８×８ブロック分合計した値と１６×１６のコストを比較し、最小となるブロックサイズを決定する。１６×１６サイズのコストが最小ではない場合、４つの８×８ブロックにおけるブロックサイズは独立であり、８×８を選択したブロックと４×４を選択したブロックが混在してよい。
【００９２】
本実施形態では、探索アルゴリズムに階層探索を用いることで、より大きなブロックサイズ内の小ブロックの密探索での候補ベクトルが同一となりやすく、より大きなブロックサイズが選択されやすくなり、圧縮効率が向上する。
【００９３】
実施形態３．
本実施形態の動画像符号化システムの構成は、第２の実施形態に示した構成よりも階層探索を多階層に用いることを特徴とする。図１０は、第３の実施形態における動画像符号化システムの構成を示すブロック図である。また、図１１は、第３の実施形態における動画像符号化システムのサブ探索部の構成を示すブロック図である。図１０および図１１に示す各構成要素は、例えば、特定の演算処理等を行うよう設計されたハードウェア、またはプログラムに従って動作するコンピュータによって実現される。また、そのプログラムは、非一時的でコンピュータが読み取り可能な記憶媒体に記憶される。
【００９４】
本実施形態の動画像符号化システム構成は、画像を１／８に縮小する縮小部３９１と、１／４に縮小する縮小部３９２と、１／２に縮小する縮小部３９３と、各縮小画像における動き探索とベクトル修正を行う第１階層探索部３０１と、第２階層探索部３０２と，第３階層探索部３０３と，縮小しない画像における動き探索とブロックサイズ選択を行う第４階層探索部３０４とを備える。
【００９５】
第１階層探索部３０１は、縮小された８×８ブロック単位で処理を行う。第２階層探索部３０２は、縮小された１６×１６ブロック単位で処理を行う。第３階層探索部３０３は、縮小された３２×３２ブロック単位で処理を行う。第４階層探索部３０４は、６４×６４ブロック単位処理を行う。
【００９６】
第１階層探索部３０１の構成は第２の実施形態における粗探索部２０１の構成と同一である。
【００９７】
第２階層探索部３０２における第３の候補ベクトル選出部２０６，第４の動き探索部２０７は、第２の実施形態における密探索部２０２の各構成要素と同一である。サブ探索部３８５は、第２の実施形態におけるサブ探索部２０５にベクトル修正部３８９を追加した構成である。
【００９８】
ベクトル修正部３８９は、ベクトル修正部１０６と同様に８×８ブロックのコストが４つの４×４ブロックのコストの合計よりも小さければ、４つの４×４ブロックの動きベクトルを８×８ブロックにおける動きベクトルに修正し出力する。
【００９９】
ベクトル修正部３０８は、さらに第４の動き探索部２０７から取得した１６×１６ブロックのコストとサブ探索部３８５から得られるコストを比較し、１６×１６ブロックのコストが小さければ、１６つの４×４ブロックの動きベクトルを１６×１６ブロックにおける動きベクトルに修正し出力する。
【０１００】
第３階層探索部３０３は、４つの第２階層探索部３０２と、３２×３２ブロックの候補ベクトルを算出する第４の候補ベクトル選出部３１６と、３２×３２ブロックの動き探索を行う第６の動き探索部３１７とベクトル修正部３１８を備える。第２階層探索部３０２は、１６×１６ブロック単位で処理を行う。
【０１０１】
第４の候補ベクトル選出部３１６は、第２階層探索部３０２における内包する６４つの４×４ブロックすべてで選出された候補ベクトルのみを３２×３２ブロックの候補ベクトルとして選出する。
【０１０２】
第６の動き探索部３１７は、第４の候補ベクトル選出部３１６で選出した各候補ベクトルに対して、第２階層探索部３０２内部の第３の動き探索部１０９が算出した４×４ブロックのＳＡＤを６４ブロック分合計することで３２×３２ブロックのＳＡＤを求めてレート歪みコストを算出し、最小コストとなる動きベクトルを選択する。
【０１０３】
ベクトル修正部３１８は、第６の動き探索部３１７で得られた３２×３２ブロックのコストと第２階層探索部３０２の結果のコストを比較し、３２×３２ブロックのコストが小さければ、６４つの４×４ブロックの動きベクトルを３２×３２ブロックにおける動きベクトルに修正し出力する。
【０１０４】
第４階層探索部３０４は、４つの第３階層探索部３０３と、６４×６４ブロックの候補ベクトルを算出する第５の候補ベクトル選出部３２６と、６４×６４ブロックの動き探索を行う第７の動き探索部３２７とブロック選択部３２８とを備える。
【０１０５】
第３階層探索部３０３は、３２×３２ブロック単位で処理を行う。第５の候補ベクトル選出部３２６は、第３階層探索部３０３における内包する２５６つの４×４ブロックすべてで選出された候補ベクトルのみを６４×６４ブロックの候補ベクトルとして選出する。  
【０１０６】
第７の動き探索部３２７は、第５の候補ベクトル選出部３２６が選出した各候補ベクトルに対して、第３階層探索部３０３内部の第３の動き探索部１０９が算出した４×４ブロックのＳＡＤを２５６ブロック分合計することで６４×６４ブロックのＳＡＤを求めてレート歪みコストを算出し、最小コストとなる動きベクトルを選択する。
【０１０７】
ブロックサイズ選択部３２８は、第３階層探索部３０３が算出した４×４ブロック、８×８ブロック、１６×１６ブロック、３２×３２ブロックの動きベクトルのコストの合計それぞれと、第７の動き探索部３２７が算出した４×６４ブロックの動きベクトルのコストを比較し、最小のブロックサイズとそのブロックにおける動きベクトルを出力する。
【０１０８】
次に、本実施形態における動画像符号化システムの第２〜４階層探索部の動作を説明する。第１階層探索部３０１の動作は、第２の実施形態における粗探索の動作と同様であるため、図示および説明を省略する。図１２は、第３の実施形態における動画像符号化システムの第２階層探索部の動作を示すフローチャートである。図１２におけるステップＳ２３１からステップＳ２３７は、図９に示す第２の実施形態における密探索の動作と同じであるため、説明を省略する。
【０１０９】
ベクトル修正部３８９は、ベクトル修正部１０６と同様に８×８ブロックのコストと４つの４×４ブロックのコストの合計を比較する。８×８ブロックのコストが小さければ（ステップＳ３２１のＹＥＳ）、ベクトル修正部３８９は、４つの４×４ブロックの動きベクトルを８×８ブロックにおける動きベクトルに修正し出力する（ステップＳ３２２）。
【０１１０】
ベクトル修正部３０８は、さらに第４の動き探索部２０７から取得した１６×１６ブロックのコストとサブ探索部３８５から得られたコストを比較する。１６×１６ブロックのコストが小さければ（ステップＳ３２３のＹＥＳ）、ベクトル修正部３０８は、１６つの４×４ブロックの動きベクトルを１６×１６ブロックにおける動きベクトルに修正し出力する（ステップＳ３２４）。
【０１１１】
図１３は、第３の実施形態における動画像符号化システムの第３階層探索部の動作を示すフローチャートである。第４の候補ベクトル選出部３１６は、第２階層探索部３０２における内包する６４つの４×４ブロックすべてで選出された候補ベクトルのみを３２×３２ブロックの候補ベクトルとして選出する（ステップＳ３３１）。
【０１１２】
第６の動き探索部３１７は、第４の候補ベクトル選出部３１６が選出した各候補ベクトルに対して、第２階層探索部内部の第３の動き探索部１０９が算出した４×４ブロックのＳＡＤを６４ブロック分合計することにより３２×３２ブロックのＳＡＤを算出する（ステップＳ３３２）。また、第６の動き探索部３１７は、算出した３２×３２ブロックのＳＡＤを用いてレート歪みコストを算出し、最小コストとなる動きベクトルを選択する（ステップＳ３３３）。
【０１１３】
ベクトル修正部３１８は、第６の動き探索部３１７から得られた３２×３２ブロックのコストと第２階層探索部３０２から得られた４×４ブロックのコストを比較する。３２×３２ブロックのコストが小さければ（ステップＳ３３４のＹＥＳ）、６４つの４×４ブロックの動きベクトルを３２×３２ブロックにおける動きベクトルに修正し出力する（ステップＳ３３５）。
【０１１４】
図１４は、第３の実施形態における動画像符号化システムの第４階層探索部の動作を示すフローチャートである。第５の候補ベクトル選出部３２６は、第３階層探索部３０３における内包する２５６つの４×４ブロックすべてで選出された候補ベクトルのみを６４×６４ブロックの候補ベクトルとして選出する（ステップＳ３４１）。
【０１１５】
第７の動き探索部３２７は、第５の候補ベクトル選出部３２６が選出した各候補ベクトルに対して、第３階層探索部３０３内部の第１の動き探索部１０９が算出した４×４ブロックのＳＡＤを２５６ブロック分合計することにより６４×６４ブロックのＳＡＤを算出する（ステップＳ３４２）。また、第７の動き探索部３２７は、レート歪みコストを算出し、最小コストとなる動きベクトルを選択する（ステップＳ３４３）。
【０１１６】
ブロックサイズ選択部３２８は、第３階層探索部３０３で求めた４×４ブロック、８×８ブロック、１６×１６ブロック、３２×３２ブロックの動きベクトルのコストの各合計と、第７の動き探索部３２７で求めた６４×６４ブロックの動きベクトルのコストを比較し、最小のブロックサイズとそのブロックにおける動きベクトルを出力する（ステップＳ３４４）。
【０１１７】
本実施形態では、各階層におけるベクトル修正により、フレーム間の動きが複雑であっても６４×６４ブロック内の全ての４×４ブロックの候補ベクトルが同一、つまり６４×６４ブロックのコスト比較ができる可能性が高くなる。これにより、大きいブロックサイズを含む、より画像に適したブロックサイズを選択することができる。
画像の縮小率やブロックサイズは上記に限定するものではない。
【０１１８】
図１５は、本発明による動画像符号化システムの概要を示すブロック図である。本発明による動画像符号化システムは、現画像と参照画像との間の動きベクトルを用いる動画像符号化システムであって、探索範囲内の一部のベクトルの動き探索を行い動きベクトルを選択する粗探索手段１と、粗探索手段１が選択した動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択する密探索手段２とを備える。粗探索手段１は、第１のサイズのブロック単位で現画像画素と参照画像画素の差分値を算出し、差分値から得られる指標により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択する第１の動き探索手段３と、第１のサイズより小さい第２のサイズのブロック単位で、第１の動き探索手段が算出した差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択する第２の動き探索手段４と、第１の動きベクトルのコストと第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正手段５とを含む。密探索手段２は、当該密探索手段２が選択した動きベクトルにもとづいてブロックサイズを決定するブロックサイズ選択手段６を含む。
【０１１９】
また、上記の各実施形態には、以下の（１）〜（６）に示す動画像符号化システムも示されている。
【０１２０】
（１）現画像と参照画像との間の動きベクトルを用いる動画像符号化システムであって、探索範囲内の一部のベクトルの動き探索を行い動きベクトルを選択する粗探索手段（例えば、粗探索部１０１、粗探索部２０１または第１階層探索部３０１）と、粗探索手段が選択した動きベクトルの周囲の所定範囲のベクトルの動き探索を行い動きベクトルを選択する密探索手段（例えば、密探索部１０２、密探索部２０２または第４階層探索部３０４）とを備え、粗探索手段は、第１のサイズのブロック（例えば、４×４ブロック）単位で現画像画素と参照画像画素の差分値を算出し、差分値から得られる指標（例えば、ＳＡＤ値）により算出されるコストが最小となる動きベクトルを第１の動きベクトルとして選択する第１の動き探索手段（例えば、第１の動き探索部１０４）と、第１のサイズより小さい第２のサイズのブロック（例えば、８×８ブロック）単位で、第１の動き探索手段が算出した差分値から得られる指標により算出されるコストが最小となる動きベクトルを第２の動きベクトルとして選択する第２の動き探索手段（例えば、第２の動き探索部１０５）と、第１の動きベクトルのコストと第２の動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正手段（例えば、ベクトル修正部１０６、ベクトル修正部３０８、またはベクトル修正部３１８）とを含み、密探索手段は、当該密探索手段が選択した動きベクトルにもとづいてブロックサイズを決定するブロックサイズ選択手段（例えば、ブロックサイズ選択部１１１、ブロックサイズ選択部２０８またはブロックサイズ選択部３２８）を含む動画像符号化システム。
【０１２１】
（２）動画像符号化システムは、粗探索手段が、探索範囲内の複数の動きベクトルのうちの一部を第１の候補ベクトルとして選出する第１の候補ベクトル選出手段（例えば、第１の候補ベクトル選出部１０３、または第１の候補ベクトル選出部２０３）を備え、第１の動き探索手段が、第１のサイズのブロック単位で、第１の候補ベクトルに対して動き探索を行い、第１の候補ベクトルの中から、現画像画素と参照画像画素の差分値から得られる指標から算出するコストが最小となる動きベクトルを選択し、第２の動き探索手段は、第２のサイズのブロック単位で、第１の候補ベクトルに対して当該第２のサイズのブロックが内包する第１のサイズのブロックについて動き探索を行い、第１の候補ベクトルの中から、第１の動き探索手段が算出した画素差分値を集計することにより得られる指標から算出するコストが最小となる動きベクトルを選択し、第１のサイズのブロックは、第２のサイズのブロックを分割して複数得られるブロックであり、ベクトル修正手段は、第１の動きベクトルのコストの合計が第２の動きベクトルのコストよりも大きければ、第１のサイズのブロックにおける第１の動きベクトルを第２のサイズのブロックにおける第２の動きベクトルで更新するように構成されていてもよい。
【０１２２】
（３）動画像符号化システムは、密探索手段が、粗探索手段が選択した動きベクトルを起点として得られる動きベクトルである第２の候補ベクトルを選出する第２の候補ベクトル選出手段（例えば、第２の候補ベクトル選出部１０７）と、第２の候補ベクトルのうち、第２のサイズのブロックが内包するすべての第１のサイズのブロックにおいて第２の候補ベクトルが選出されている場合に、当該第２の候補ベクトルを第３の候補ベクトルとして選出する第３の候補ベクトル選出手段（例えば、第３の候補ベクトル選出部１０８、第３の候補ベクトル選出部２０６）と、第１のサイズのブロック単位で、第２の候補ベクトルに対して現画像画素と参照画像画素の差分値を算出し、差分値を集計することにより得られる指標からコストを算出し、当該コストが最小となる動きベクトルを第３の動きベクトルとして選択する第３の動き探索手段（例えば、第３の動き探索部１０９）と、第２のサイズのブロック単位で、第３の候補ベクトルに対して、当該第２のサイズのブロックが内包する第１のサイズのブロックについて第３の動き探索手段が算出した差分値から得られる指標からコストを算出し、当該コストが最小となる動きベクトルを第４の動きベクトルとして選択する第４の動き探索手段（例えば、第４の動き探索部１１０または第４の動き探索部２０７）とを備え、ブロックサイズ選択手段が、第２のサイズのブロックに内包する第１のサイズのブロックにおける第３の動きベクトルのコストの合計と、第２のサイズのブロックにおける第４の動きベクトルのコストにもとづいて、いずれかのブロックサイズを選択し、選択したブロックサイズのブロックにおいて算出した動きベクトルを出力するように構成されていてもよい。
【０１２３】
（４）動画像符号化システムは、密探索手段が、第１のサイズのブロックより小さいサイズのブロック単位で、第３の動き探索手段が算出した差分値から得られる指標により算出されるコストが最小となる動きベクトルを選択する少なくとも一つの動き探索手段（例えば、第５の動き探索部１１２）をさらに備え、ブロックのサイズは、所定の最大サイズを階層的に分割したサイズであり、ブロックサイズ選択手段が、第３の動き探索手段（例えば、第３の動き探索部１０９）、第４の動き探索手段（例えば、第４の動き探索部２０７）および動き探索手段（例えば、第５の動き探索部１１２）を含む３つ以上の動き探索手段から得た動きベクトルを取得し、ブロックサイズを選択するように構成されていてもよい。このような構成によれば、探索アルゴリズムに階層探索を用いることで、より大きなブロックサイズ内の小ブロックの密探索での候補ベクトルが同一となりやすく、より大きなブロックサイズが選択されやすくなり、圧縮効率が向上する。
【０１２４】
（５）動画像符号化システムは、現画像と参照画像とを縮小する縮小手段（例えば、縮小部２０４、または縮小部３９１）を備え、粗探索手段は、縮小されたブロックサイズにおいて動き探索を行うように構成されていてもよい。
【０１２５】
（６）動画像符号化システムは、異なる縮小率に現画像と参照画像とを縮小する複数の縮小手段（例えば、縮小部３９１、縮小部３９２または縮小部３９３）と、縮小手段から画像を取得し、所定の最大サイズを階層的に分割した異なるサイズのブロックについて動き探索を行う１つ以上の階層探索手段（例えば、第２階層探索部３０２または３階層探索部３０３）をさらに備え、密探索部（例えば、４階層探索部３０４）および各階層探索手段（例えば、第２階層探索部３０２または３階層探索部３０３）は、１階層上位の探索手段が行う処理を行い動きベクトルを選択する上位階層探索手段（例えば、サブ探索部３８５、第２階層探索部３０２または３階層探索部３０３）と、対象階層の候補ベクトルを選出する対象階層候補ベクトル選出手段（例えば、第３の候補ベクトル選出部２０６、第４の候補ベクトル選出部３１６または第５の候補ベクトル選出部３２６）と、対象階層の動き探索を行い動きベクトルを選択する対象階層動き探索手段（例えば、第４の動き探索部２０７、第６の動き探索部３１７または第７の動き探索部３２７）と上位階層探索手段が選択した動きベクトルのコストと、対象階層動き探索手段が選択した動きベクトルのコストの大小関係を用いて動きベクトルを修正するベクトル修正手段（例えば、ベクトル修正部３０８、ベクトル修正部３１８またはベクトル修正部３２８）とを含むように構成されていてもよい。
【産業上の利用可能性】
【０１２６】
本発明は、符号化効率を保ちつつ演算量を削減することができるため、高解像度映像の高速処理を実現することができ、例えば、高解像度処理を要求する撮像システムやトランスコードシステムなどに有用である。
【符号の説明】
【０１２７】
１  粗探索手段
２  密探索手段
３  第１の動き探索手段
４  第２の動き探索手段
５  ベクトル修正手段
６  ブロックサイズ選択手段
１０１、２０１  粗探索部
１０２、２０２  密探索部
１０４  第１の動き探索部
１０５  第２の動き探索部
１０６、３０８、３１８  ベクトル修正部
１１１、２０８、３２８  ブロックサイズ選択部
【図１】
2016181799.tif 000004
【図２】
2016181799.tif 000005
【図３】
2016181799.tif 000006
【図４】
2016181799.tif 000007
【図５】
2016181799.tif 000008
【図６】
2016181799.tif 000009
【図７】
2016181799.tif 000010
【図８】
2016181799.tif 000011
【図９】
2016181799.tif 000012
【図１０】
2016181799.tif 000013
【図１１】
2016181799.tif 000014
【図１２】
2016181799.tif 000015
【図１３】
2016181799.tif 000016
【図１４】
2016181799.tif 000017
【図１５】
2016181799.tif 000018
【図１６】
2016181799.tif 000019
【図１７】
2016181799.tif 000020