(57)【要約】【課題】一般的に、全探索方式の処理量削減を目的とした動き探索の改善方式は局所解問題を抱えており、画質向上の妨げとなっていた。この局所解問題は映像コンテンツの高解像度化に伴い、さらに深刻化する見込みである。【解決手段】符号化を行う対象画像内の領域である符号化対象領域を含み、かつ、この符号化対象領域よりも大きい領域である拡大領域の動きベクトルを探索し、その探索結果に基づいて、符号化対象領域の動きベクトルの探索開始点を決定する。そして、決定された探索開始点から符号化対象領域の動きベクトルを探索し、この探索結果に基づいて対象画像の画面間予測を行い、対象画像を符号化する。【選択図】図１２
2012129791.tif 000002
【特許請求の範囲】
【請求項１】
符号化を行う対象画像内の領域である符号化対象領域の動きベクトルを探索し、前記符号化対象領域の動きベクトルに基づいて前記対象画像の画面間予測を行うことによって画像の符号化を行う画像符号化装置であって、
前記符号化対象領域を含み、かつ、前記符号化対象領域よりも大きい領域である拡大領域の動きベクトルを探索し、その探索結果に基づいて、前記符号化対象領域の動きベクトルの探索開始点を決定する探索開始点決定部と、
決定された前記探索開始点から前記符号化対象領域の動きベクトルを探索する対象領域動き探索部と、
を有することを特徴とする画像符号化装置。
【請求項２】
前記探索開始決定部は、前記符号化対象領域の動きベクトルを探索する際の探索開始点を決定する際、前記拡大領域の動きベクトルの探索結果に加えて、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記符号化対象領域の動きベクトルの探索開始点を選択することを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記探索開始決定部は、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記拡大領域の動きベクトルの探索開始点を選択することを特徴とする請求項１又は２に記載の画像符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を符号化する画像符号化装置に関する。
【背景技術】
【０００２】
大容量の動画像情報をデジタルデータ化して記録、伝達する手法として、MPEG（Moving  Picture  Experts  Group）方式等の符号化方式が策定されており、MPEG-1規格、MPEG-2規格、MPEG-4規格、H.264/AVC（Advanced  Video  Coding）規格等として国際標準の符号化方式となっている。これらの方式はデジタル衛星放送、DVD（Digital  Versatile  Disc）、携帯電話、デジタルカメラなどにおける符号化方式として採用されており、現在ますます利用の範囲が広がり、身近なものとなってきている。
【０００３】
これらの規格では、符号化処理が完了した画像情報（以下、適宜「復号画像」という）を利用して符号化の対象である符号化対象画像（以下、単に「対象画像」という場合もある）をブロック単位で予測し、原画像との差分（以下、適宜「予測差分」という）を符号化することによって、動画像の持つ冗長性を除いて符号量を減らしている。特に、対象画像とは別の画像を参照する画面間予測（フレーム間予測とも言われる）では、符号化対象ブロックと相関の高いブロックを参照画像（復号画像）中から探索する動き探索処理を行うことによって、高精度な予測を可能としている。
【０００４】
同一画面内の情報を利用する画面内予測（フレーム内予測とも言われる）に比べて、過去の復号済みの画像情報を利用できる画面間予測の予測精度は著しく高いが、エンコーダの符号化効率は動き探索処理の性能に大きく依存する。そのため、動き探索の性能を改善することにより、画質を大幅に向上することができる。しかし、一般的に動き探索の処理量は非常に高く、探索範囲内のすべての領域を探索する全探索方式を用いた場合、エンコーダに必要な処理量の大半を動き探索が費やしてしまう。そのため、探索点数を削減することにより処理量を削減する方法が多数提案されている（例えば、非特許文献１）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】En-Hui  Yang,  Xiang  Yu,  “Rate  Distortion  Optimization  for  H.264  Interframe  Coding:A  General  Framework  and  Algorithms”,  IEEE  TRANSATIONS  ON  IMAGE  PROCESSING,  IEEE,  JULY  2007,  VOL.16,  NO.7,  p.1774-1784
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、探索点の数を削減することにより処理量を削減する方法は、限定的な探索を行うため局所解問題を抱えており、画質低下の原因となっている。
【０００７】
動き探索時の局所解問題は、特に空間的相関性が高く画素値変動の少ない高解像度映像の符号化時に起こりやすく、地上波デジタル放送やブルーレイディスクなどに採用されているハイビジョンコンテンツが主流である現在においては、深刻な問題となっている。さらに、8k×4kの解像度を有するスーパーHDや、4k×2kの解像度を有するディジタルシネマの実用化が見込まれており、今後さらに局所解問題が深刻化することが見込まれる。
【０００８】
そこで、本発明では、探索開始点を好適に設定することにより、上述したような探索点の数を削減することにより処理量を削減する方法が抱える局所解問題を低減することが可能な画像符号化装置を提供する。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明は、符号化を行う対象画像内の領域である符号化対象領域の動きベクトルを探索し、前記符号化対象領域の動きベクトルに基づいて前記対象画像の画面間予測を行うことによって画像の符号化を行う画像符号化装置であって、前記符号化対象領域を含み、かつ、前記符号化対象領域よりも大きい領域である拡大領域の動きベクトルを探索し、その探索結果に基づいて、前記符号化対象領域の動きベクトルの探索開始点を決定する探索開始点決定部（例えば、図１２の拡大ブロック探索開始点決定部２１２１、拡大ブロック動き探索部２１２３、および対象ブロック探索開始点決定部２１２４）と、決定された前記探索開始点から前記符号化対象領域の動きベクトルを探索する対象領域動き探索部（例えば、図１２の対象ブロック動き探索部２１２５）と、を有することを特徴とする画像符号化装置を提案する。
【００１０】
この構成によれば、局所解に陥る可能性を低減させることができる。また、局所解に陥ったとしても、コスト値の小さな解（動きベクトル）が得られ、画質劣化を低減させることができる。
【００１１】
また、前記探索開始決定部は、前記符号化対象領域の動きベクトルを探索する際の探索開始点を決定する際、前記拡大領域の動きベクトルの探索結果に加えて、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記符号化対象領域の動きベクトルの探索開始点を選択するようになっていてもよい。
【００１２】
この構成によれば、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【００１３】
また、前記探索開始決定部は、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記拡大領域の動きベクトルの探索開始点を選択するようになっていてもよい。
【００１４】
この構成によれば、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【発明の効果】
【００１５】
本発明によれば、画面間予測処理の動きベクトル探索において、局所解に陥る可能性を低減させることができる。また、局所解に陥ったとしても、コスト値の小さな解（動きベクトル）が得られ、画質劣化を低減させることができる。
【図面の簡単な説明】
【００１６】
【図１】H.264/AVCにおける動画像符号化処理に関する概念的な説明図である。
【図２】H.264/AVCによる画面間予測処理に関する概念的な説明図である。
【図３】H.264/AVCによる画面間予測において許容されるマクロブロックの分割パターンについて示す図である。
【図４】動き探索の動作を概念的に示す図である。
【図５】全探索アルゴリズムの一例を示す図である。
【図６】勾配法による動き探索処理の動作手順を示す図である。
【図７】ステップサーチの動作手順を示す図である。
【図８】局所解問題について説明する図である。
【図９】局所解問題について説明する図である。
【図１０】本発明に係る画像符号化装置の概要を示す図である。
【図１１】画像符号化装置の構成例を示すブロック図である。
【図１２】動き探索部２１２の詳細な構成の一例を示すブロック図である。
【図１３】前フレームの動きベクトルを探索開始点候補とする方法の一例について示す図である。
【図１４】動き探索とコスト関数に関する概念的な説明図である。
【図１５】画素間引き例に関する概念的な説明図である。
【図１６】動き探索部２１２での動き探索の処理手順を示すフロー図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について、図面を参照して説明する。なお、以下の説明において参照する各図では、他の図と同等部分は同一符号によって示される。
【００１８】
（H.264/AVCにおける符号化処理）
まず初めに、H.264/AVCにおける符号化処理と、その問題点について詳細に説明する。
【００１９】
H.264/AVCでは、符号化処理が完了した復号画像を利用して符号化の対象である符号化対象画像を予測し、この符号化対象画像と原画像との差分（予測差分）を符号化することによって、動画像の持つ冗長性を減らして符号量を削減している。また、H.264/AVCでは、動画像の局所的性質を利用するために、画像を細かく分割したブロック単位で予測が行われる。
【００２０】
図１に示されるように、符号化処理は対象画像１０に対して、矢印１０１で示されるラスタースキャンの順序に従い、１６×１６画素（横画素×縦画素。以下同様。）で構成されるマクロブロック（以下、適宜「対象ブロック」という）１０２単位で実行される。なお、図１に示される対象画像１０において、網掛け部分はすでに符号化が完了した領域（既符号化領域）１０３を示し、それ以外の部分は符号化が完了していない領域（未符号化領域）１０４を示している。
【００２１】
また、予測方式には、大別して画面内予測と画面間予測が存在する。図２は、H.264/AVCによる画面間予測処理の動作について概念的に説明する図である。画面間予測を行う際には、符号化対象画像１０と同じ映像３０に含まれる画像であって、符号化済みの画像である復号画像を参照画像２０とし、対象画像１０中の予測対象である対象ブロック１０２と相関の高いブロック（予測画像）２０２を参照画像２０中から探索する（動き探索）。このとき、両ブロックの差分として計算される予測差分に加えて、予測に必要な補助的な情報として、両ブロックの座標値の差分として表される動きベクトル１０５を符号化する。
【００２２】
一方、復号化の際には上記の逆の手順が行われる。すなわち、復号化された予測差分を参照画像２０中のブロック（予測画像）２０２に加算することにより、復号画像を取得できる。
【００２３】
また、H.264/AVCでは、マクロブロックをさらに小さなサイズのブロックに分割し、この分割されたブロック単位で上記の画面間予測を行うことができる。図３は、画面間予測を行う際に許容されているマクロブロック１０２の分割パターンについて示す図である。すなわち、対象画像１０中のすべてのマクロブロック１０２は、あらかじめ定義された４×４画素サイズから１６×１６画素サイズまでの分割パターンの中から最適なものを選択して予測を行うことが可能である。
【００２４】
また、符号化処理においては、マクロブロック１０２ごとにどの分割パターンを用いて分割をしたのかを示す情報がマクロブロック１０２単位で符号化される。なお、マクロブロック１０２の分割パターンとは、具体的には、図３に示されるように、１６×１６、８×１６、１６×８、８×８、４×８、８×４、４×４画素サイズの分割パターンがあり得る。
【００２５】
図４は、動き探索の動作を概念的に示す図である。符号化対象画像１０において、予測対象となる対象ブロック１０２をテンプレート画像４０１とし、参照画像２０に含まれる各画像ブロック２０１と比較する。比較対象となる画像ブロック（探索ブロック）２０１の座標（探索点）は特定の規則で決定していき、探索が終了する時点で符号化コストが最も小さい画像ブロックを探索結果２０１’として決定する。なお、符号化コストは、画質と符号量のトレードオフ関係を考慮したものが良く、例えばコスト関数を以下の数式として定義すると効果的である。
【００２６】
【数１】
2012129791.tif 000003
ここで、“Dist”は予測誤差、“Rate”は動きベクトルの符号量、“B”は対象ブロック１０２、“B’”は探索ブロック２０１とする。また、“weight”は予測誤差と符号量とがコスト値に寄与する割合を調整する定数であり、符号化モードの種類や量子化パラメータの値に応じて統計的に決定すると効果的である。また、“SAD”は絶対値誤差和（Sum  of  Absolute  Differences）を表しており、テンプレート画像４０１と探索ブロック２０１に対して、同一座標の画素値差分の絶対値和として以下のように定義される。
【００２７】
【数２】
2012129791.tif 000004
ただし、p[i,j]は対象ブロックBにおける座標（i,j）の画素値を、q[i,j]は探索ブロックB’における座標（i,j）の画素値を示している。画素値としては、輝度成分のみを利用しても良いし、色差成分も考慮しても良い。また、一般的に、予測誤差関数として、（式２）の代わりに以下の（式４）を用いるとさらに効果があるとされている。
【００２８】
【数３】
2012129791.tif 000005
“SATD”はアダマール変換係数絶対値誤差和（Sum  of  Hadamard  Transformed  Absolute  Differences）を表しており、テンプレート画像４０１と探索ブロック２０１の差分値に対して、周波数変換方式の１種であるアダマール変換を施した後、各係数値の絶対値和を計算したものとして以下のように定義される。
【００２９】
【数４】
2012129791.tif 000006
ただし、“Tr”は画像ブロックにアダマール変換を施すための関数を、“Tr（X）[a,b] ”は対象ブロックXに対してアダマール変換を施した後の変換係数成分（a,b）を表す。
【００３０】
また、コスト関数に関しては、上記以外にも、二乗誤差和（SSD：Sum  of  Squared  Differences）などテンプレート画像４０１と探索ブロック２０１の類似性を反映できるものならどのような指標を用いてもよい。
【００３１】
ところで、上述した動き探索の性能は、探索点を決定する規則を規定する探索アルゴリズムに大きく依存するため、探索アルゴリズムの違いにより符号化効率や処理量が大きく異なる。
【００３２】
（全探索アルゴリズム）
図５は、極めて単純で高い符号化効率を実現できる全探索アルゴリズムの一例を示す図である。全探索アルゴリズムでは、参照画像２０において定められた探索範囲５０１内のすべての探索点（座標）に対して探索を行う。図５は、探索範囲５０１の左上端に位置する探索開始点５０２から、ラスタースキャン順にすべての探索点に対して探索を実行した後、右下端の探索終了点５０３で探索を終了する場合を示している。
【００３３】
この場合、探索範囲５０１が適切に設定されてさえいれば、最適解は必ず得られ、画質は極めて高くなる。しかし、探索範囲５０１内のすべての探索点を探索するため処理量が極めて高く、エンコーダ処理の大半を動き探索が占めてしまうことになる。そのため、探索点数を削減することによって、処理量を削減するための方式が多数提案されている。以下に、処理量を削減するための基本的なアルゴリズムの例として、勾配法とステップサーチ法について説明する。
【００３４】
（勾配法）
図６に、勾配法（最急降下法）を用いて動き探索を行う場合について、その動作の一例を示す。勾配法とは、周辺に位置する探索点の中でコスト値を最小にするものを選択し、探索結果を徐々に更新していく方式である。
【００３５】
まず、探索開始点を中心とした周囲８点を含めた合計９点の探索点に対してコスト値を計算し、コストが最小であるコスト最小点６０１を決定する（図６（ａ））。続いて、コスト最小点６０１に隣接する３点を加えて探索を行い、メモリ等に記憶して保存されている探索結果を前回の探索結果６０１から新しい探索結果６０２に更新する（図６（ｂ））。さらに、前回の探索結果６０２に隣接する４点を加えて探索を続行し、コスト最小点６０３を探して保存されている探索結果を更新する（図６（ｃ））。上記の処理を特定回数繰り返すか、探索結果が変化しなくなれば、探索処理を終了する。
【００３６】
（ステップサーチ法）
図７に、ステップサーチ法により動き探索を行う場合について、その動作の一例を示す。ステップサーチとは、最初は画素を大幅に間引いて粗い探索を行い、その探索結果に応じて探索範囲を段階的に狭めていく方式である。図７では、３段階に渡り探索範囲を狭めていくことにより探索を行う例について示している。
【００３７】
まず、探索開始点を中心として３画素間引きして９点を対象とした探索を行い、コストが最小であるコスト最小点７０１を決定する（図７（ａ））。続いて、このコスト最小点７０１を中心として１画素間引きした周囲９点を対象とした探索を行い、コスト最小点７０２を決定する（図７（ｂ））。最後に、その探索結果７０２に対して周辺９点探索を行い、コスト最小点７０３を探索結果とする（図７（ｃ））。
【００３８】
以上では、全探索の処理量改善を行うための方式として、勾配法を用いた方式とステップサーチ法を用いた方式について述べたが、階層探索や、ダイヤモンドサーチ、ヘキサゴンサーチ、スパイラルサーチ、探索打ち切り処理など、様々な方式が提案されている。しかし、これらの方式は、どれも最適解には到達できずに局所解に陥る場合が多く、画質劣化の大きな原因になっていた。
【００３９】
（局所解問題とテンプレート画像のサイズとの関係）
ここで、図８と図９を用いて、探索点の数を削減することにより処理量を削減する動き探索が抱える局所解問題とテンプレート画像のサイズとの関係について説明する。
【００４０】
図８は、参照画像の解像度に対して十分小さなテンプレート画像を用いて動き探索を行う場合の一例について示す図である。この場合、図８（ａ）に示されるように、テンプレート画像８０１が持つ情報量が少ないため、参照画像２０内に多数の類似領域（テンプレート画像との相関が高くなる領域）８０２〜８０５が存在する。
【００４１】
そのため、図８（ｂ）に示されるように、局所解（×印）が多く存在することになり、最適解８０６（●印）に到達することが難しい。さらに、コスト値の大きな局所解（例えば、局所解８０７）に陥る可能性もあり、この場合、画質が大きく劣化してしまう。
【００４２】
一方、図９は、図８の例において、テンプレート画像８０１を拡大した場合について示す図である。この場合、テンプレート画像９０１が持つ情報量が増加することにより類似領域９０２が減少し、より最適解９０３に到達しやすくなる。さらに、局所解のコスト値（例えば局所解９０４）も図８の場合と比べて小さくなるため、局所解に陥った場合でも画質劣化は低減される。
【００４３】
上記の事実により、本発明では、大小２種類のテンプレート画像を利用した２ステップによる探索を行う。これにより、コスト値の小さな解が得られる可能性を高めることができる。
【００４４】
（本発明の概要）
図１０は、本発明に係る画像符号化装置の概要を示す図である。
【００４５】
本発明に係る画像符号化装置においては、まず、図１０（ａ）に示されるように、対象ブロック１０２に対して周囲を広げた拡大ブロック１１０をテンプレート画像４０１とした探索を行う（この処理ステップを、以下「第１ステップ」という）。なお、図１０（ａ）に示されるように、本実施形態では、対象ブロック１０２が真中（中央）に位置するように拡大ブロック１１０を設定しているが、拡大ブロック１１０中に対象ブロック１０２が納まっていればどのような設定方法でもよい。
【００４６】
ここでは、参照画像２０の解像度が高いほど拡大ブロック１１０のサイズを大きく設定すると効果的である。例えば、フルHD解像度（１９２０×１０８０画素）に対して対象ブロック１０２のサイズが１６×１６画素である場合、拡大ブロック１１０のサイズは４８×４８画素または６４×６４画素程度が適当である。また、拡大ブロック１１０は正方形でなくてもよく、特にインタレース画像に対するフィールド符号化時には６４×３２画素などの長方形の拡大ブロックを用いると効果的である。また、第１ステップでは、激しい動きにも追従できるように、広範囲の点を探索できるようにすると効果的である。
【００４７】
続いて、図１０（ｂ）に示されるように、対象ブロック１０２単位で探索を行う（この処理ステップを、以下「第２ステップ」という）。ところで、第１ステップにおける拡大ブロック１１０の探索結果の直近解は最適解である可能性が高い。また、たとえ直近解が局所解であっても、そのコスト値は比較的小さい可能性が高い。そこで、この第２ステップにおける探索開始点として、第１ステップの探索結果１００１を用いると効果的である。
【００４８】
（画像符号化装置の構成）
図１１は、本実施形態に係る画像符号化装置の構成例を示したものである。画像符号化装置１は、入力された原画像４０を保持する入力画像メモリ２１０と、原画像４０を所定の大きさの小領域に分割するブロック分割部２１１と、ブロック分割部２１１で分割されたブロック単位で画面内予測を行う画面内予測部２１３と、動き探索部２１２にて検出された動き量（動きベクトル）に基づいてブロック単位で画面間予測を行う画面間予測部２１４と、画像の性質に合致する予測モード（予測方法およびブロックサイズ）を決定するモード選択部２１５と、予測差分を生成するための減算部２１６と、生成された予測差分に対して符号化を行う周波数変換部２１７および量子化処理部２１８と、符号の発生確率に応じた適応的符号化を行うための可変長符号化部２１９と、周波数変換部２１７および量子化処理部２１８で符号化された予測差分を復号化するための逆量子化処理部２２０および逆周波数変換部２２１と、復号化された予測差分を用いて復号画像を生成するための加算部２２２と、生成された復号画像を保持して後の画面内予測または画面間予測に使用するための参照画像メモリ２２３と、を有する。
【００４９】
また、図１１に示される画像符号化装置１は、図示しないＣＰＵ（Central  Processing  Unit）、ＲＡＭ（Random  Access  Memory）等のメモリ、ハードディスク等の記憶装置、ネットワークインターフェイス等の一般的なコンピュータの構成と同様の構成により実現される。また、画像符号化装置１の各構成の機能は、例えば、ＣＰＵがハードディスク等に記憶されているプログラムを読み出して実行することにより、もしくは、例えば、ＦＰＧＡ（Field  Programmable  Gate  Array）においてシーケンサロジックをカスタム設計することに実現される機能である。
【００５０】
なお、図１１に示される構成のうち、動き探索部２１２以外の構成においては、従来の画面内予測もしくは画面間予測における処理と同様の処理が実行される。これらの構成については、図１〜図７等で説明したように公知の技術であるので、以下においては簡単に説明する。
【００５１】
入力画像メモリ２１０は、原画像４０に含まれる画像のうち一枚の画像を符号化対象画像１０として保持する。また、この符号化対象画像１０は、ブロック分割部２１１にて細かいブロックに分割され、動き探索部２１２、画面内予測部２１３、および画面間予測部２１４に出力される。
【００５２】
動き探索部２１２では、参照画像メモリ２２３に格納されている復号化済みの復号画像（参照画像２０）を用いて、対象ブロック１０２の動き量を計算し、動きベクトルを画面間予測部２１４に出力する。また、画面内予測部２１３および画面間予測部２１４では、それぞれ画面内予測処理および画面間予測処理をいくつかの大きさのブロック単位で実行し、モード選択部２１５にて最適な予測モードを選んで、画面内予測もしくは画面間予測のいずれかを選択する。
【００５３】
続いて、減算部２１６では、モード選択部２１５で選択された最適な予測符号化手段（画面内予測部２１３または画面間予測部２１４）による予測差分を生成し、周波数変換部２１７に渡す。周波数変換部２１７および量子化処理部２１８では、送られてきた予測差分に対して、指定された大きさのブロック単位でそれぞれDCT（離散コサイン変換）などの周波数変換および量子化処理を行い、可変長符号化部２１９および逆量子化処理部２２０に出力する。可変長符号化部２１９では、送られてきた（もしくは「量子化済み」）変換係数と動きベクトルなどのヘッダ情報とについて、符号の発生確率に基づき符号化を行って符号化ストリーム５０を生成する。
【００５４】
また、逆量子化処理部２２０および逆周波数変換部２２１では、量子化後の周波数変換係数に対して、それぞれ逆量子化および逆DCTなどの逆周波数変換を施し、予測差分を取得して加算部２２２に出力する。続いて、加算部２２２では、モード選択部２１５から出力される予測画像と、逆周波数変換部２２１から出力される復号化済みの予測差分とを加算して復号画像（参照画像２０）を生成する。そして、生成された復号画像は、参照画像メモリ２２３に格納される。
【００５５】
（動き探索部２１２）
図８〜図１０を用いて先に説明したように、本実施形態に係る画像符号化装置１の特徴点は動き探索部２１２における処理にある。以下、動き探索部２１２について、さらに詳細に説明する。
【００５６】
図１２は、本実施形態における動き探索部２１２について、その詳細な構成の一例を示す図である。動き探索部２１２は、拡大ブロック１１０の探索開始点を決定するための拡大ブロック探索開始点決定部２１２１と、拡大ブロック動き探索部２１２３で実行された動き探索の探索結果を格納するための動きベクトル格納用メモリ２１２２と、拡大ブロック１１０の動き探索を行う拡大ブロック動き探索部２１２３と、対象ブロック１０２の探索開始点を決定するための対象ブロック探索開始点決定部２１２４と、対象ブロック１０２の動き探索を行う対象ブロック動き探索部２１２５とを含んで構成される。
【００５７】
ここで、拡大ブロック探索開始点決定部２１２１、拡大ブロック動き探索部２１２３、および対象ブロック探索開始点決定部２１２４は、符号化対象領域（対象ブロック１０２）を含み、かつ、符号化対象領域（対象ブロック１０２）よりも大きい領域である拡大領域（拡大ブロック１１０）の動きベクトルを探索し、その探索結果に基づいて、符号化対象領域（対象ブロック１０２）の動きベクトルの探索開始点を決定する。そして、対象ブロック動き探索部２１２５は、この決定された探索開始点から符号化対象領域（対象ブロック１０２）の動きベクトルを探索する。
【００５８】
より具体的には、以下の通りである。
【００５９】
拡大ブロック探索開始点決定部２１２１は、動きベクトル格納用メモリ２１２２に格納されている対象画像１０より時間的に先の画像である前画像（前フレーム）の動きベクトル（具体的には、例えば、対象画像１０の前の画像である前画像において対象ブロック１０２の対象画像１０での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル）、対象画像１０の周辺ブロック（後に詳述する）の動きベクトル、ゼロベクトル等の中から拡大ブロック探索の探索開始点を選択し、拡大ブロック動き探索部２１２３に出力する。
【００６０】
拡大ブロック動き探索部２１２３では、参照画像メモリ２２３に格納されている参照画像２０を用いて、拡大ブロック探索開始点決定部２１２１から出力された探索開始点から動き探索を実行し、探索結果を対象ブロック探索開始点決定部２１２４に出力する。
【００６１】
対象ブロック探索開始点決定部２１２４では、拡大ブロック動き探索部２１２３から出力される拡大ブロック１１０の動きベクトルの探索結果に加えて、動きベクトル格納用メモリ２１２２に格納されている前画像の動きベクトル（具体的には、例えば、対象画像１０の前の画像である前画像において対象ブロック１０２の対象画像１０での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル）、対象画像１０の周辺ブロックの動きベクトル、ゼロベクトル等の中から対象ブロック探索の探索開始点を選択し、対象ブロック動き探索部２１２５に出力する。
【００６２】
対象ブロック動き探索部２１２５では、参照画像メモリ２２３に格納されている参照画像２０を用いて、対象ブロック探索開始点決定部２１２４から出力された探索開始点から動き探索を実行し、その探索結果を画面間予測部２１４へ出力する。
【００６３】
なお、前フレームと対象フレーム（対象画像）１０との間でシーンチェンジが検出された場合、拡大ブロック探索開始点決定部２１２１では前フレームの動きベクトルを探索開始点の候補として利用する代わりに、参照画像メモリ２２３に格納されている参照画像に対して拡大ブロックをテンプレート画像とした粗い探索を行い、探索結果を初期探索点候補の１つとする。
【００６４】
すなわち、図１０を用いて先に説明したように、本実施形態に係る画像符号化装置１では、拡大ブロック１１０単位で動き探索を行い（第１ステップ）、その探索結果を対象ブロック１０２単位の動き探索時の開始点とする（第２ステップ）のが基本である。
【００６５】
しかしながら、実際には、拡大ブロック１１０内に動く物体が複数存在する場合等のように、第１ステップの探索結果が第２ステップにおける探索開始点として最適でない場合もある。そのため、拡大ブロック探索開始点決定部２１２１は、第２ステップの探索開始点候補として、さらに、ゼロベクトル、対象ブロック１０２の周辺ベクトル等を追加し、対象ブロック探索開始点決定部２１２４は、それらの中から最適な探索開始点を決定する。
【００６６】
ここで、「周辺ベクトル」とは、図１３に示すように、対象ブロック１０２の左、上、右上に位置する符号化済みのブロック（これを「周辺ブロック」という）１２０で検出される動きベクトルのことである。拡大ブロック探索開始点決定部２１２１は、これらの周辺ベクトルのすべてを探索開始点候補としても良いし、それらのベクトルの中央値や平均値等を探索開始点候補としても良い。また、対象ブロック探索開始点決定部２１２４における探索開始点の決定方法としては、例えば、すべての探索開始点候補の中でコスト値を最小とするものを選択すると効果的であるが、他の方法でもよい。
【００６７】
また、拡大ブロック動き探索部２１２３における第１ステップの処理と、対象ブロック動き探索部２１２５における第２ステップの処理においては、同じ探索アルゴリズムを用いても良いが、別の探索アルゴリズムを用いても良い。この場合、勾配法、ステップサーチ、階層探索、ダイヤモンドサーチ、ヘキサゴンサーチ、スパイラルサーチ、探索打ち切り処理など、全探索処理の処理量を削減するための方式であればどれを用いても良いし、これらの方式を組み合わせたものや、これらの改良方式でも構わない。
【００６８】
また、第１ステップにおいても拡大ブロック１１０の探索時に探索開始点を適切に設定することが重要である。この場合、ゼロベクトル、周辺ブロック１２０の動きベクトル等に加えて、対象フレーム１０の前の前フレームの動きベクトルを候補に入れると、さらに効果的である。具体的には、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【００６９】
図１３は、前フレームの動きベクトルを探索開始点候補とする方法の一例について示す図である。すなわち、図１０（ａ）に示される第１ステップでの処理において、対象フレーム１０で拡大ブロック１１０の探索を行う際、前フレーム１１内において対象ブロック１０２の対象フレーム１０での位置と同じ位置にあるブロック（同位置ブロック）１０７を中心とした３×３の９個のブロックからなる近隣複数ブロック１０８の動きベクトルを参照し、これらの中から最適となる探索開始点を選択する。この場合、参照する動きベクトルとしては、拡大ブロック単位で探索したものでも、対象ブロック単位で探索したものでも、その両方でも構わないが、一般的に、拡大ブロック単位で探索したものを参照すると効果が高い。
【００７０】
また、前フレーム１１と対象フレーム１０との間でシーンが変わった場合、前フレーム１１の動きベクトルを利用しても効果がない場合が多い。そのため、エンコーダにシーンチェンジ検出機能が備わっていて、このシーンチェンジ検出機能によりシーンチェンジが検出された場合には、第１ステップ（図１０（ａ））において前フレーム１１の動きベクトルから探索開始点を選択する代わりに、拡大ブロック１１０をテンプレート画像とした非常に粗い探索を行い、その探索結果を初期探索点候補にすると効率が良い。
【００７１】
また、初期探索点候補に前フレーム１１の動きベクトルを利用する本方式は、第２ステップ（図１０（ｂ））における対象ブロック単位の探索にも効果があるため、第２ステップでも前フレーム１１の動きベクトルを対象ブロック１０２の初期探索点候補に追加しても良い。
【００７２】
一方、図１４に示されるように、拡大ブロック単位の動き探索では（図１４（ａ））解の数が少ないため、探索開始点１４０１から直近の解１４０２までの距離が、対象ブロック探索時（図１４（ｂ））の探索開始点４０３から直近の解１４０４までの距離よりも大きい場合が多く、解が収束するまでに多くの探索が必要である。さらに、拡大ブロック１１０の画素数は対象ブロック１０２よりも多く、コスト計算に必要な誤差計算回数も多い。そのため、拡大ブロック探索時（図１４（ａ））における１つの探索点に対する評価に必要な処理量も、対象ブロック探索時（図１４（ｂ））より高くなってしまう。
【００７３】
この問題を解決するため、図１５に示されるように、第１ステップの拡大ブロック単位の動き探索時には、誤差計算を行う画素の数を大幅に減らすと効果的である。例えば、６４×６４画素サイズの拡大ブロック単位で動き探索を行う場合には、８×８画素程度に間引いてから誤差計算を行っても、ある程度の探索精度を維持できる。その際、単純に画素を間引いて誤差計算をしても良いし、フィルタを施してから間引いて誤差計算をしても良い。
【００７４】
（動き探索部２１２における処理）
以下、動き探索部２１２における処理の流れについて説明する。図１６は、本実施形態における動き探索部２１２での動き探索の処理手順を示すフロー図である。
【００７５】
まず、拡大ブロック探索開始点決定部２１２１において、前フレーム１１と対象フレーム１０との間でシーンチェンジが検出されたか判断する（ステップＳ１０１）。シーンチェンジが検出されない場合は、前フレーム１１において、対象ブロック１０２の対象フレーム１０での位置と同じ位置にある同位置ブロック１０７の周辺ブロック（もしくは近隣複数ブロック１０８）の動きベクトルの中から、拡大ブロック１１０の探索開始点候補を選択する（ステップＳ１０２）。
【００７６】
一方、シーンチェンジが検出された場合は、拡大ブロック１１０をテンプレート画像とした粗い探索を行い、その探索結果を拡大ブロックの探索開始点候補とする（ステップＳ１０３）。
【００７７】
続いて、拡大ブロック探索開始点決定部２１２１において、ステップＳ１０２またはステップＳ１０３において取得された探索開始点候補を対象フレーム１０の周辺ベクトルやゼロベクトル等と比較し、記憶されている探索開始点を更新し、決定する（ステップＳ１０４）。さらに、拡大ブロック動き探索部２１２３において、ステップＳ１０４で決定された探索開始点を用いて拡大ブロック１１０の動き探索を実行し、探索結果を得る（ステップＳ１０５）。
【００７８】
続いて、対象ブロック探索開始点決定部２１２４において、ステップＳ１０５での拡大ブロック１１０の探索結果と対象フレーム１０における周辺ベクトルやゼロベクトル等の中から、対象ブロック１０２の探索開始点を決定する（ステップＳ１０６）。最後に、対象ブロック動き探索部２１２５において、ステップＳ１０６で決定された探索開始点から対象ブロックの動き探索を実行し（ステップＳ１０７）、動き探索処理を終了する。
【００７９】
本実施形態では、予測および周波数変換をブロック単位で行っているが、それ以外にも例えば画像の背景から分離したオブジェクト単位で算出しても良い。また、本実施形態では、周波数変換の一例としてDCTを挙げているが、DST（Discrete  Sine  Transformation：離散サイン変換）、WT（Wavelet  Transformation：ウェーブレット変換）、DFT（Discrete  Fourier  Transformation：離散フーリエ変換）、KLT（Karhunen-Loeve  Transformation：カルーネン−レーブ変換）など、画素間相関除去に利用する直交変換ならどのようなものでも構わない。また、例えば、特に画面内予測を行わなくても、MPEG-1やMPEG-2のイントラ符号化のように、原画像に対して直接周波数変換を施しても構わない。可変長符号化も特に行わなくても良い。
【００８０】
また、本発明はH.261、MPEG-1、H.262/MPEG-2、MPEG-4、H.263、H.264/AVCなど、動き探索を用いる方式ならどのような動画像符号化方式にも適用できる。
【００８１】
（付記）
以上に、本発明に係る実施形態について詳細に説明したことからも明らかなように、前述の実施形態の一部または全部は、以下の各付記のようにも記載することができる。しかしながら、以下の各付記は、あくまでも、本発明の単なる例示に過ぎず、本発明は、かかる場合のみに限るものではない。
【００８２】
（付記１）
符号化を行う対象画像内の領域である符号化対象領域の動きベクトルを探索し、前記符号化対象領域の動きベクトルに基づいて前記対象画像の画面間予測を行うことによって画像の符号化を行う画像符号化装置であって、
前記符号化対象領域を含み、かつ、前記符号化対象領域よりも大きい領域である拡大領域の動きベクトルを探索し、その探索結果に基づいて、前記符号化対象領域の動きベクトルの探索開始点を決定する探索開始点決定部（例えば、図１２の拡大ブロック探索開始点決定部２１２１、拡大ブロック動き探索部２１２３、および対象ブロック探索開始点決定部２１２４）と、
決定された前記探索開始点から前記符号化対象領域の動きベクトルを探索する対象領域動き探索部（例えば、図１２の対象ブロック動き探索部２１２５）と、
を有することを特徴とする画像符号化装置。
【００８３】
この構成によれば、局所解に陥る可能性を低減させることができる。また、局所解に陥ったとしても、コスト値の小さな解（動きベクトル）が得られ、画質劣化を低減させることができる。
【００８４】
（付記２）
前記探索開始決定部は、前記符号化対象領域の動きベクトルを探索する際の探索開始点を決定する際、前記拡大領域の動きベクトルの探索結果に加えて、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記符号化対象領域の動きベクトルの探索開始点を選択することを特徴とする付記１に記載の画像符号化装置。
【００８５】
この構成によれば、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【００８６】
（付記３）
前記探索開始決定部は、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記拡大領域の動きベクトルの探索開始点を選択することを特徴とする付記１又は２に記載の画像符号化装置。
【００８７】
この構成によれば、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【００８８】
（付記４）
前記探索開始点決定部および前記対象領域動き探索部の少なくとも一方は、勾配法、ステップサーチ、階層探索、ダイヤモンドサーチ、ヘキサゴンサーチ、スパイラルサーチ、および探索打ち切り処理のいずれか、もしくはこれらの組み合わせ、又はこれらの改良方式を用いて動き探索を実行することを特徴とする付記１から３のいずれか一項に記載の画像符号化装置。
【００８９】
これにより、探索開始点決定部と対象領域動き探索部における動き探索における全探索処理の処理量が削減される。
【００９０】
（付記５）
画面間予測を用いて画像の符号化を行う画像符号化装置によって実行される画像符号化方法であって、
前記符号化を行う対象画像内の領域である符号化対象領域を含み、かつ、前記符号化対象領域よりも大きい領域である拡大領域の動きベクトルを探索し、その探索結果に基づいて、前記符号化対象領域の動きベクトルの探索開始点を決定する探索開始点決定ステップ（例えば、図１６のステップＳ１０２又はステップＳ１０３〜ステップＳ１０６）と、
決定された前記探索開始点から前記符号化対象領域の動きベクトルを探索する対象領域動き探索ステップ（例えば、図１６のステップＳ１０７）と、
前記符号化対象領域の動きベクトルに基づいて前記対象画像の画面間予測を行う画面間予測ステップと、
を含むことを特徴とする画像符号化方法。
【００９１】
この構成によれば、局所解に陥る可能性を低減させることができる。また、局所解に陥ったとしても、コスト値の小さな解（動きベクトル）が得られ、画質劣化を低減させることができる。
【００９２】
（付記６）
前記探索開始決定ステップは、前記符号化対象領域の動きベクトルを探索する際の探索開始点を決定する際、前記拡大領域の動きベクトルの探索結果に加えて、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記符号化対象領域の動きベクトルの探索開始点を選択することを特徴とする付記５に記載の画像符号化方法。
【００９３】
この構成によれば、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【００９４】
（付記７）
前記探索開始決定ステップは、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記拡大領域の動きベクトルの探索開始点を選択することを特徴とする付記５又は６に記載の画像符号化方法。
【００９５】
この構成によれば、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【００９６】
（付記８）
前記探索開始点決定ステップおよび前記対象領域動き探索ステップの少なくとも一方は、勾配法、ステップサーチ、階層探索、ダイヤモンドサーチ、ヘキサゴンサーチ、スパイラルサーチ、および探索打ち切り処理のいずれか、もしくはこれらの組み合わせ、又はこれらの改良方式を用いて動き探索を実行することを特徴とする付記５から７のいずれか一項に記載の画像符号化方法。
【００９７】
これにより、探索開始点決定ステップと対象領域動き探索ステップにおける動き探索における全探索処理の処理量が削減される。
【００９８】
（付記９）
画面間予測を用いた画像の符号化をコンピュータに実行させる画像符号化プログラムであって、前記コンピュータに、
前記符号化を行う対象画像内の領域である符号化対象領域を含み、かつ、前記符号化対象領域よりも大きい領域である拡大領域の動きベクトルを探索し、その探索結果に基づいて、前記符号化対象領域の動きベクトルの探索開始点を決定する探索開始点決定ステップ（例えば、図１６のステップＳ１０２又はステップＳ１０３〜ステップＳ１０６）と、
決定された前記探索開始点から前記符号化対象領域の動きベクトルを探索する対象領域動き探索ステップ（例えば、図１６のステップＳ１０７）と、
前記符号化対象領域の動きベクトルに基づいて前記対象画像の画面間予測を行う画面間予測ステップと、
を実行させるための画像符号化プログラム。
【００９９】
この構成によれば、局所解に陥る可能性を低減させることができる。また、局所解に陥ったとしても、コスト値の小さな解（動きベクトル）が得られ、画質劣化を低減させることができる。
【０１００】
（付記１０）
前記探索開始決定ステップは、前記符号化対象領域の動きベクトルを探索する際の探索開始点を決定する際、前記拡大領域の動きベクトルの探索結果に加えて、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記符号化対象領域の動きベクトルの探索開始点を選択することを特徴とする付記９に記載の画像符号化プログラム。
【０１０１】
この構成によれば、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【０１０２】
（付記１１）
前記探索開始決定ステップは、前記対象画像の前の画像である前画像において前記符号化対象領域の前記対象画像での位置と同じ位置にある領域の周囲に位置する領域の動きベクトル、前記符号化対象領域の左、上、および右上に位置する領域の動きベクトル、およびゼロベクトルの中から、前記拡大領域の動きベクトルの探索開始点を選択することを特徴とする付記９又は１０に記載の画像符号化プログラム。
【０１０３】
この構成によれば、拡大領域内に動く物体が複数存在する場合であっても、より最適な探索開始点を決定することができる。
【０１０４】
（付記１２）
前記探索開始点決定ステップおよび前記対象領域動き探索ステップの少なくとも一方は、勾配法、ステップサーチ、階層探索、ダイヤモンドサーチ、ヘキサゴンサーチ、スパイラルサーチ、および探索打ち切り処理のいずれか、もしくはこれらの組み合わせ、又はこれらの改良方式を用いて動き探索を実行することを特徴とする付記９から１１のいずれか一項に記載の画像符号化プログラム。
【０１０５】
これにより、探索開始点決定ステップと対象領域動き探索ステップにおける動き探索における全探索処理の処理量が削減される。
【符号の説明】
【０１０６】
１  画像符号化装置
１０  対象画像（対象フレーム、符号化対象画像）
１１  前フレーム
２０  参照画像
４０  原画像
５０  符号化ストリーム
１０２  対象ブロック（マクロブロック）
１０３  既符号化領域
１０４  未符号化領域
１０５  動きベクトル
１０７  同位置ブロック
１０８  近隣複数ブロック
１１０  拡大ブロック
１２０  周辺ブロック
２０１  探索ブロック
２０２  予測画像
２１０  入力画像メモリ
２１１  ブロック分割部
２１２  動き探索部
２１３  画面内予測部
２１４  画面間予測部
２１５  モード選択部
２１６  減算部
２１７  周波数変換部
２１８  量子化処理部
２１９  可変長符号化部
２２０  逆量子化処理部
２２１  逆周波数変換部
２２２  加算部
２２３  参照画像メモリ
４０１  テンプレート画像
２１２１  拡大ブロック探索開始点決定部
２１２２  動きベクトル格納用メモリ
２１２３  拡大ブロック動き探索部
２１２４  対象ブロック探索開始点決定部
２１２５  対象ブロック動き探索部
【図１】
2012129791.tif 000007
【図２】
2012129791.tif 000008
【図３】
2012129791.tif 000009
【図４】
2012129791.tif 000010
【図５】
2012129791.tif 000011
【図６】
2012129791.tif 000012
【図７】
2012129791.tif 000013
【図８】
2012129791.tif 000014
【図９】
2012129791.tif 000015
【図１０】
2012129791.tif 000016
【図１１】
2012129791.tif 000017
【図１２】
2012129791.tif 000018
【図１３】
2012129791.tif 000019
【図１４】
2012129791.tif 000020
【図１５】
2012129791.tif 000021
【図１６】
2012129791.tif 000022