(57)【特許請求の範囲】
【請求項１】
フレーム間の検出済み動きベクトルの水平成分の統計値及び垂直成分の統計値の少なくとも一方に基づいて動きベクトルの探索範囲の長さを決定する範囲決定部と、
長さが決定された前記探索範囲における探索点について前記動きベクトルを探索する動き探索部と
を備え、
前記検出済み動きベクトルは、符号化の対象ブロックの参照フレームを前記対象ブロックが属する対象フレームから参照する動きベクトルであり、
前記範囲決定部は、前記検出済み動きベクトルを検出した際の評価値が閾値以下である前記探索点を前記探索範囲から除外する、
動きベクトル検出装置。
【請求項２】
フレーム間の検出済み動きベクトルの水平成分の統計値及び垂直成分の統計値の少なくとも一方に基づいて動きベクトルの探索範囲の長さを決定する範囲決定部と、
長さが決定された前記探索範囲における探索点について前記動きベクトルを探索する動き探索部と
を備え、
前記検出済み動きベクトルは、符号化の対象ブロックの参照フレームをフレームから参照する第１の前記検出済み動きベクトルと、前記対象ブロックを前記フレームから参照する第２の前記検出済み動きベクトルとであり、
前記範囲決定部は、第１の前記検出済み動きベクトルを検出した際の評価値が閾値以上である前記探索点を前記探索範囲から除外する、
動きベクトル検出装置。
【請求項３】
動きベクトル検出装置が実行する動きベクトル検出方法であって、
フレーム間の検出済み動きベクトルの水平成分の統計値及び垂直成分の統計値の少なくとも一方に基づいて動きベクトルの探索範囲の長さを決定するステップと、
長さが決定された前記探索範囲における探索点について前記動きベクトルを探索するステップと
を含み、
前記検出済み動きベクトルは、符号化の対象ブロックの参照フレームを前記対象ブロックが属する対象フレームから参照する動きベクトルであり、
前記探索範囲の長さを決定するステップでは、前記検出済み動きベクトルを検出した際の評価値が閾値以下である前記探索点を前記探索範囲から除外する、
動きベクトル検出方法。
【請求項４】
動きベクトル検出装置が実行する動きベクトル検出方法であって、
フレーム間の検出済み動きベクトルの水平成分の統計値及び垂直成分の統計値の少なくとも一方に基づいて動きベクトルの探索範囲の長さを決定するステップと、
長さが決定された前記探索範囲における探索点について前記動きベクトルを探索するステップと
を含み、
前記検出済み動きベクトルは、符号化の対象ブロックの参照フレームをフレームから参照する第１の前記検出済み動きベクトルと、前記対象ブロックを前記フレームから参照する第２の前記検出済み動きベクトルとであり、
前記探索範囲の長さを決定するステップでは、第１の前記検出済み動きベクトルを検出した際の評価値が閾値以上である前記探索点を前記探索範囲から除外する、
動きベクトル検出方法。
【請求項５】
請求項１又は請求項２に記載の動きベクトル検出装置としてコンピュータを機能させるための動きベクトル検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動きベクトル検出装置、動きベクトル検出方法及び動きベクトル検出プログラムに関する。
【背景技術】
【０００２】
Ｈ.２６４／ＡＶＣやＨ.２６５／ＨＥＶＣ（High Efficiency Video Coding）などの動画像符号化規格が、動画像符号化の標準規格として策定されている。動画像符号化では、フレームは複数のブロックに分割される。動画像符号化では、符号化された動画像の情報量は、フレーム内予測符号化とフレーム間予測符号化とをブロックごとに切り替えることによって削減することが可能である。フレーム内予測符号化とは、フレーム内の情報を用いて動きベクトルを予測する符号化である。フレーム間予測符号化とは、フレーム間における符号化済みのフレーム情報を用いて動きベクトルを予測する符号化である。
【０００３】
フレーム間予測符号化では、差分画像は、参照フレーム（参照画像）を予測画像として用いることによって算出される。参照フレームとは、動きベクトルを用いて符号化の対象フレームから参照されるフレームである。符号化された動画像の情報量は、動きベクトルと差分画像とを用いて符号化されることによって削減される。
【０００４】
動きベクトルは、動き探索（動きベクトル探索）によって算出される。動き探索とは、対象フレームなどの第１フレーム内のブロックに最も類似した領域を参照フレームなどの第２フレーム内で探索することである。動き探索では、例えば、参照フレーム内において特定された領域に対象フレーム内の対象ブロックから向かう動きベクトルが算出される。対象フレーム内の対象ブロックは、正確な動きベクトルが算出された場合、効率的に符号化される。動き探索における一般的な課題として、探索範囲に関する課題がある。
【０００５】
図３１は、参照距離が短い場合の探索範囲１１１の例を示す図である。図３２は、参照距離が長い場合の探索範囲１１１の例を示す図である。探索範囲１１１は、対象フレーム１００と参照フレーム１１０との間の時間的な距離（参照距離）が長いほど拡大される。符号化のための演算量は、探索範囲１１１が拡大されるほど増加する。したがって、フレーム間予測符号化では、少ない演算量で効率的に動きベクトルを算出する手法が望まれる。少ない演算量で効率的に動きベクトルを算出することを目的とした手法が、非特許文献１に開示されている。
【０００６】
図３３は、中継フレーム１２０を中心として探索する方法の例を示す図である。中継フレーム１２０は、時間軸方向について、対象フレーム１００と参照フレーム１１０との間に位置するフレームである。対象フレーム１００を中継フレーム１２０から参照する動きベクトルは、中継フレーム１２０を中心に動き探索が実行されることによって算出される。参照フレーム１１０を中継フレーム１２０から参照する動きベクトルも、中継フレーム１２０を中心に動き探索が実行されることによって算出される。
【０００７】
図３４は、動きベクトルを連結した点を中心に探索する方法の例を示す図である。対象フレーム１００を中継フレーム１２０から参照する動きベクトルと、参照フレーム１１０を中継フレーム１２０から参照する動きベクトルとは連結されてもよい。連結された結果の動きベクトルは、参照フレームに投影される。投影された動きベクトルが示す位置は、参照フレームにおける探索の中心（探索中心）と定められる。参照フレームにおける物体の画像に近い位置から動き探索が開始されるので、探索範囲が拡大されない場合でも、動きベクトルは正確に算出される。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１５−２２６０８５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
図３５は、符号化効率が低下した例を示す図である。動画像において物体が加速しながら動いている場合には、探索範囲は正確には定められない。動きベクトルは、探索範囲が正確に定められない場合には、正確に算出されない。すなわち、従来の動画像符号化装置は、動き探索の演算量の増加を抑えた場合には、動きベクトルを効率的に算出することができないという問題があった。
【００１０】
上記事情に鑑み、本発明は、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能である動きベクトル検出装置、動きベクトル検出方法及び動きベクトル検出プログラムを提供することを目的としている。
【課題を解決するための手段】
【００１１】
本発明の一態様は、フレーム間の検出済み動きベクトルの水平成分の統計値及び垂直成分の統計値の少なくとも一方に基づいて動きベクトルの探索範囲の長さを決定する範囲決定部と、長さが決定された前記探索範囲における探索点について前記動きベクトルを探索する動き探索部とを備える動きベクトル検出装置である。
【００１２】
本発明の一態様は、上記の動きベクトル検出装置であって、前記範囲決定部は、前記水平成分の統計値と前記垂直成分の統計値との比に応じて前記探索範囲の長さを決定し、前記検出済み動きベクトルの方向に基づいて前記探索範囲の形状を決定する。
【００１３】
本発明の一態様は、上記の動きベクトル検出装置であって、前記範囲決定部は、前記探索範囲における前記探索点の数が所定値となるまで前記探索範囲の長さを変更する。
【００１４】
本発明の一態様は、上記の動きベクトル検出装置であって、前記範囲決定部は、前記探索範囲の長さを変更する前後で、前記探索範囲の面積の変更量を閾値以内に収める。
【００１５】
本発明の一態様は、上記の動きベクトル検出装置であって、前記検出済み動きベクトルは、符号化の対象ブロックの参照フレームを前記対象ブロックが属する対象フレームから参照する動きベクトルであり、前記範囲決定部は、第１の前記検出済み動きベクトルを検出した際の評価値が閾値以下である前記探索点を前記探索範囲から除外する。
【００１６】
本発明の一態様は、上記の動きベクトル検出装置であって、前記検出済み動きベクトルは、符号化の対象ブロックの参照フレームをフレームから参照する第１の前記検出済み動きベクトルと、前記対象ブロックを前記フレームから参照する第２の前記検出済み動きベクトルとであり、前記範囲決定部は、前記検出済み動きベクトルを検出した際の評価値が閾値以上である前記探索点を前記探索範囲から除外する。
【００１７】
本発明の一態様は、動きベクトル検出装置が実行する動きベクトル検出方法であって、フレーム間の検出済み動きベクトルの水平成分の統計値及び垂直成分の統計値の少なくとも一方に基づいて動きベクトルの探索範囲の長さを決定するステップと、長さが決定された前記探索範囲における探索点について前記動きベクトルを探索するステップとを含む動きベクトル検出方法である。
【００１８】
本発明の一態様は、上記の動きベクトル検出装置としてコンピュータを機能させるための動きベクトル検出プログラムである。
【発明の効果】
【００１９】
本発明により、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】第１実施形態における、動画像符号化装置の構成の例を示す図である。
【図２】第１実施形態における、動きベクトル算出部の構成の例を示す図である。
【図３】第１実施形態における、探索範囲の例を示す図である。
【図４】第１実施形態における、楕円型探索パターンの例を示す図である。
【図５】第１実施形態における、ドーナツ型探索パターンの例を示す図である。
【図６】第１実施形態における、ランダム型探索パターンの例を示す図である。
【図７】第１実施形態における、動きベクトル算出部２０の動作の例を示すフローチャートである。
【図８】第１実施形態における、探索パラメータを決定するための動作の例を示すフローチャートである。
【図９】第１実施形態における、検出済み動きベクトルのスケーリングの例を示す図である。
【図１０】第１実施形態における、ｘ成分の統計値とｙ成分の統計値を成分に持つベクトルの方向の例を示す図である。
【図１１】第１実施形態における、第１の探索パターンの例を示す図である。
【図１２】第１実施形態における、第２の探索パターンの例を示す図である。
【図１３】第１実施形態における、第３の探索パターンの例を示す図である。
【図１４】第１実施形態における、第４の探索パターンの例を示す図である。
【図１５】第１実施形態における、探索パターンを決定するための方法の例を示す図である。
【図１６】第２実施形態における、動きベクトル算出部の構成の例を示す図である。
【図１７】第２実施形態における、動きベクトル算出部の動作の例を示すフローチャートである。
【図１８】第２実施形態における、探索点を削除することによる探索パターンの変更の例を示す図である。
【図１９】第２実施形態における、探索点を追加することによる探索パターンの変更の例を示す図である。
【図２０】第３実施形態における、動きベクトル算出部の構成の例を示す図である。
【図２１】第３実施形態における、動きベクトル算出部の動作の例を示すフローチャートである。
【図２２】第３実施形態における、対象フレームと参照フレームとの例を示す図である。
【図２３】第３実施形態における、対象フレームのブロックと参照ブロックとの差が小さい探索点を除外するための方法の例を示す図である。
【図２４】第３実施形態における、対象フレームのブロックと参照ブロックとの差が小さい探索点を除外したことによる効果の例を示す図である。
【図２５】第４実施形態における、動きベクトル算出部の構成の例を示す図である。
【図２６】第４実施形態における、動き探索順序の例を示す図である。
【図２７】第４実施形態における、動きベクトル算出部の動作の例を示すフローチャートである。
【図２８】第４実施形態における、対象フレームと参照フレームと動きベクトル検出済みフレームとの例を示す図である。
【図２９】第４実施形態における、対象フレーム以外のフレームのブロックと参照ブロックとの差が大きい探索点を除外するための方法の例を示す図である。
【図３０】第４実施形態における、対象フレーム以外のフレームのブロックと参照ブロックとの差が大きい探索点を除外したことによる効果の例を示す図である。
【図３１】参照距離が短い場合の探索範囲の例を示す図である。
【図３２】参照距離が長い場合の探索範囲の例を示す図である。
【図３３】中継フレームを中心として探索する方法の例を示す図である。
【図３４】動きベクトルを連結した点を中心に探索する方法の例を示す図である。
【図３５】符号化効率が低下した例を示す図である。
【発明を実施するための形態】
【００２１】
本発明の実施形態について、図面を参照して詳細に説明する。
実施形態の動画像符号化装置は、符号化の対象フレームの対象ピクチャと探索パラメータと探索中心とに基づいて、対象フレーム内の対象ブロックの動きベクトルを検出する。ここで、動きベクトルは、ｘ方向（水平方向）及びｙ方向（垂直方向）に成分を持つ２次元ベクトルによって表される。
【００２２】
実施形態の動画像符号化装置は、検出済み動きベクトルに基づいて、探索パラメータを決定する。ここで、検出済み動きベクトルとは、対象フレーム内の対象ブロックの動きベクトルが検出されるよりも前の算出された動きベクトルである。検出済み動きベクトルとは、対象フレームとは異なるフレームのうち、動きベクトルが検出済みであるフレームのブロックの動きベクトルでもよい。探索パラメータとは、探索範囲の形状（以下、「探索パターン」という。）を表すパラメータである。探索パラメータは、例えば、ｘ方向に関する長さ（値）とｙ方向に関する長さ（値）とを用いて表現される。探索範囲は、１個以上の探索点を含む。実施形態の動画像符号化装置は、検出済み動きベクトルに基づいて探索中心を決定する。
【００２３】
実施形態の動画像符号化装置は、検出済み動きベクトルの統計値に基づいて、探索パラメータを適応的に変更する。すなわち、実施形態の動画像符号化装置は、動きベクトルのｘ成分（水平成分）及びｙ成分（垂直成分）に基づいて、探索範囲のｘ方向及びｙ方向の長さを変更する。これによって、実施形態の動画像符号化装置は、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能となる。
【００２４】
実施形態の動画像符号化装置は、検出済み動きベクトルの統計値により定まる角度に基づいて、探索パターンを決定してもよい。実施形態の動画像符号化装置は、対象フレーム内の対象ブロックを参照する動きベクトルに基づいて、探索パターンを決定する。これによって、実施形態の動画像符号化装置は、最適な動きベクトルが存在する確率の高い探索範囲を定めて、動きベクトルを効率的に探索することができる。
【００２５】
以下、動画像符号化装置が準拠する標準規格は、特定の標準規格に限定されない。以下、一例として、Ｈ.２６５／ＨＥＶＣに準拠する動画像符号化装置について説明する。
【００２６】
（第１実施形態）
図１は、動画像符号化装置１の構成の例を示す図である。動画像符号化装置１は、パーソナルコンピュータ装置、タブレット端末、スマートフォン端末、サーバ装置などの情報処理端末である。動画像符号化装置１は、符号化の対象となる動画像を取得する。動画像符号化装置１は、符号化の対象フレームの対象ピクチャを、符号化の対象ブロックごとに取得する。対象ピクチャとは、符号化の対象フレームの対象ブロックにおける画像情報である。画像情報は、例えば、画像特徴量を表す情報である。動画像符号化装置１は、ラスタスキャン順に対象ブロックを符号化する。動画像符号化装置１は、対象ブロックが符号化された結果を表す符号化データを送信する。
【００２７】
動画像符号化装置１は、減算器１０と、直交変換・量子化部１１と、可変長符号化部１２と、逆量子化・逆直交変換部１３と、加算器１４と、ループフィルタ１５と、復号ピクチャメモリ１６と、イントラ予測部１７と、インタ予測部１８と、スイッチ１９と、動きベクトル算出部２０ａと、動きベクトルメモリ２１とを備える。
【００２８】
減算器１０と直交変換・量子化部１１と可変長符号化部１２と逆量子化・逆直交変換部１３と加算器１４とループフィルタ１５とイントラ予測部１７とインタ予測部１８とスイッチ１９と動きベクトル算出部２０ａとのうち一部又は全部は、例えば、ＣＰＵ（Central Processing Unit）等のプロセッサが、メモリに記憶されたプログラムを実行することにより機能するソフトウェア機能部である。また、これらの機能部のうち一部又は全部は、ＬＳＩ（Large Scale Integration）やＡＳＩＣ（Application Specific Integrated Circuit）等のハードウェア機能部であってもよい。
【００２９】
復号ピクチャメモリ１６及び動きベクトルメモリ２１は、磁気ハードディスク装置や半導体記憶装置等の不揮発性の記憶媒体（非一時的な記録媒体）を有する記憶装置を用いて構成される。復号ピクチャメモリ１６及び動きベクトルメモリ２１は、例えば、ＲＡＭ（Random Access Memory）やレジスタなどの揮発性の記憶媒体を有していてもよい。
【００３０】
減算器１０は、対象ブロックを取得する。減算器１０は、スイッチ１９を介して、予測画像をイントラ予測部１７又はインタ予測部１８から取得する。減算器１０は、対象ブロックと予測画像との差である差分画像を、直交変換・量子化部１１に送信する。
【００３１】
直交変換・量子化部１１は、直交変換処理及び量子化処理を差分画像に施す。直交変換・量子化部１１は、直交変換処理及び量子化処理が施された差分画像を、可変長符号化部１２及び逆量子化・逆直交変換部１３に送信する。
【００３２】
可変長符号化部１２は、直交変換・量子化部１１から送信された量子化係数に、可変長符号化処理を施す。可変長符号化部１２は、符号化処理の結果を表す符号化データを、動画像符号化装置１の外部に送信する。
【００３３】
逆量子化・逆直交変換部１３は、直交変換・量子化部１１から送信された量子化係数に、逆量子化処理及び逆直交変換処理を施す。逆量子化・逆直交変換部１３は、逆量子化処理及び逆直交変換処理の結果を表す画像を、加算器１４に送信する。
【００３４】
加算器１４は、逆量子化処理及び逆直交変換処理の結果を表す画像を、逆量子化・逆直交変換部１３から取得する。加算器１４は、予測画像を減算器１０から取得する。加算器１４は、逆量子化・逆直交変換部１３から送信された画像と予測画像との和を、イントラ予測部１７及びループフィルタ１５に送信する。
【００３５】
ループフィルタ１５は、加算器１４を介して、予測画像をイントラ予測部１７又はインタ予測部１８から取得する。ループフィルタ１５は、逆量子化・逆直交変換部１３から送信された画像と予測画像との和に、ループフィルタを適用する。ループフィルタ１５は、ループフィルタを適用した結果を表す画像（復号ピクチャ）を、復号ピクチャメモリ１６に記録する。
【００３６】
復号ピクチャメモリ１６は、ループフィルタを適用した結果を表す画像を記憶する。ループフィルタを適用した結果を表す画像は、インタ予測部１８が対象ブロックのインタ予測処理を実行する場合、参照フレームとしてインタ予測部１８に利用される。
【００３７】
イントラ予測部１７（フレーム内予測部）は、加算器１４を介して、逆量子化処理及び逆直交変換処理の結果を表す画像を逆量子化・逆直交変換部１３から取得する。イントラ予測部１７は、イントラ予測部１７が送信した予測画像を、加算器１４を介して取得する。すなわち、イントラ予測部１７は、逆量子化・逆直交変換部１３から送信された画像とイントラ予測部１７が送信した予測画像との和を、加算器１４を介して取得する。
【００３８】
イントラ予測部１７は、インタ予測部１８が送信した予測画像を、加算器１４を介して取得してもよい。すなわち、イントラ予測部１７は、逆量子化・逆直交変換部１３から送信された画像とインタ予測部１８が送信した予測画像との和を、加算器１４を介して取得してもよい。イントラ予測部１７は、参照フレームに基づいて、対象ブロックのイントラ予測画像（フレーム内予測画像）を生成する。
【００３９】
インタ予測部１８（フレーム間予測部）は、ループフィルタを適用した結果を表す画像である参照フレームを、復号ピクチャメモリ１６から取得する。インタ予測部１８は、動きベクトルを動きベクトルメモリ２１から取得する。インタ予測部１８は、参照フレーム及び動きベクトルに基づいて、対象ブロックのインタ予測画像（フレーム間予測画像）を生成する。
【００４０】
スイッチ１９は、対象ブロックに定められた予測モードに応じて、イントラ予測部１７又はインタ予測部１８から予測画像を取得する。スイッチ１９は、取得した予測画像を減算器１０及び加算器１４に送信する。
【００４１】
動きベクトル算出部２０ａ（動きベクトル検出装置）は、符号化の対象ブロックを取得する。動きベクトル算出部２０ａは、参照フレームを復号ピクチャメモリ１６から取得する。動きベクトル算出部２０ａは、検出済み動きベクトルを動きベクトルメモリ２１から取得する。動きベクトル算出部２０ａは、対象ブロックと参照フレームと検出済み動きベクトルとに基づいて、対象ブロックの動きベクトルを算出する。動きベクトル算出部２０ａは、対象ブロックの動きベクトルを、動きベクトルメモリ２１に記録する。
【００４２】
動きベクトルメモリ２１は、対象ブロックの動きベクトルを記憶する。動きベクトルメモリ２１は、アクセスに応じて、対象ブロックの動きベクトルを動きベクトル算出部２０に送信する。動きベクトルメモリ２１は、アクセスに応じて、対象ブロックの動きベクトルをインタ予測部１８に送信する。
【００４３】
図２は、動きベクトル算出部２０ａの構成の例を示す図である。動きベクトル算出部２０ａは、探索パラメータ算出部２００と、探索中心算出部２０１と、動き探索部２０２とを備える。探索パラメータ算出部２００は、検出済み動きベクトルに基づいて、探索パラメータを決定する。探索中心算出部２０１は、検出済み動きベクトルに基づいて、探索中心を決定する。
【００４４】
動き探索部２０２は、対象フレームの対象ピクチャを取得する。動き探索部２０２は、参照フレームを復号ピクチャメモリ１６から取得する。動き探索部２０２は、探索パラメータを探索パラメータ算出部２００から取得する。動き探索部２０２は、探索中心を探索中心算出部２０１から取得する。動き探索部２０２は、対象ピクチャと参照ピクチャと探索パラメータと探索中心とに基づいて、動き探索処理を実行する。動き探索部２０２は、対象ブロックの動きベクトルを、動き探索処理によって検出する。
【００４５】
図３は、探索範囲の例を示す図である。探索中心３００は、探索範囲の中心である。図３では、探索パターンは長方形である。探索範囲のｘ成分は、一例として９である。すなわち、探索範囲のｘ方向の探索点３０１の数は、一例として９である。探索範囲のｙ成分は、一例として７である。すなわち、探索範囲のｙ方向の探索点３０１の数は、一例として７である。
【００４６】
図４は、楕円型探索パターンの例を示す図である。図４では、探索中心３００は、楕円型探索パターン（楕円型探索領域）の中心である。
図５は、ドーナツ型探索パターンの例を示す図である。図５では、探索中心３００は、ドーナツ型探索パターン（単一の空き領域がある探索領域）の中心である。ドーナツ型探索パターンでは、探索点が連続している。
【００４７】
図６は、ランダム型探索パターンの例を示す図である。探索点は、連続して配置されなくてもよい。例えば、探索点はランダムに配置されてもよい。例えば、探索パターンは、上下対称でなくてもよい。例えば、探索パターンは、左右対称でなくてもよい。
【００４８】
図７は、動きベクトル算出部２０ａの動作の例を示すフローチャートである。探索パラメータ算出部２００（範囲決定部）は、検出済みの動きベクトルに基づいて、探索パラメータを決定する（ステップＳ１０１）。
【００４９】
探索中心算出部２０１は、検出済みの動きベクトルに基づいて、探索中心を決定する。例えば、探索中心算出部２０１は、対象フレームの対象ブロックと参照フレームの参照ブロックとの差が最小となる検出済み動きベクトルが示す点を、探索中心と決定する。対象ブロックと参照ブロックの差は、例えば、差分の絶対値の和で表現される。対象ブロックと参照ブロックの差は、動きベクトルの符号量が考慮された差分の絶対値の和で表現される。探索中心算出部２０１は、検出済み動きベクトルがない場合、ｘ成分及びｙ成分が０であるゼロベクトルが示す点を、探索中心としてもよい（ステップＳ１０２）。
【００５０】
動き探索部２０２は、探索パラメータ及び探索中心に基づいて、対象ブロックについて動き探索処理を実行する。具体的には、動き探索部２０２は、参照フレームにおける探索範囲の探索中心について、対象ブロックと参照ブロックとの差を算出する。動き探索部２０２は、探索中心以外の各探索点についても、対象ブロックと参照ブロックとの差（差分情報）を算出する。対象ブロックと参照ブロックとの差とは、例えば、対象ブロックの画像特徴量と参照ブロックの画像特徴量との差である。動き探索部２０２は、対象ブロックと参照ブロックとの差が最小となる探索点を示す動きベクトルを検出する。
【００５１】
図８は、探索パラメータを決定するための動作の例を示すフローチャートである。探索パラメータ算出部２００は、検出済み動きベクトルが存在するか否かを判定する（ステップＳ２０１）。探索パラメータ算出部２００は、検出済み動きベクトルが存在しない場合（ステップＳ２０１：ＮＯ）、デフォルト値の探索パラメータに基づいて探索パターンを定める（ステップＳ２０２）。探索パラメータ算出部２００は、検出済み動きベクトルが存在する場合（ステップＳ２０１：ＹＥＳ）、参照距離に応じて、検出済み動きベクトルのスケーリングを実行する。すなわち、探索パラメータ算出部２００は、参照距離に応じて、検出済み動きベクトルの長さを圧縮又は伸張する（ステップＳ２０３）。
【００５２】
図９は、検出済み動きベクトルのスケーリングの例を示す図である。参照フレーム４２０は、動きベクトル検出済みフレーム４３０の参照フレームである。動きベクトル検出済みフレーム４３０は、検出済み動きベクトル４３１を持つ。スケーリングされた検出済み動きベクトルは、式（１）によって表される。
【００５３】
ｍｖ＿ｓｃａｌｅ＝ｍｖ×（ｄ１／ｄ２）  …（１）
【００５４】
ｍｖ＿ｓｃａｌｅは、スケーリングされた検出済み動きベクトルを示す。すなわち、ｍｖ＿ｓｃａｌｅは、拡大又は縮小された検出済み動きベクトルを示す。ｍｖは、検出済み動きベクトルを示す。ｄ１は、対象フレーム４００と参照フレーム４１０のフレーム間距離を示す。ｄ２は、参照フレーム４２０と動きベクトル検出済みフレーム４３０とのフレーム間距離を示す。
【００５５】
図８に示すように、探索パラメータ算出部２００は、スケーリングされた検出済み動きベクトルのｘ成分の統計値を算出する（ステップＳ２０４）。探索パラメータ算出部２００は、スケーリングされた検出済み動きベクトルのｙ成分の統計値を算出する。動きベクトルの統計値は、例えば、最大値、最小値、平均値、合計値、中央値、分散値、最頻値である。動きベクトルの統計値は、例えば、最大値と最小値と平均値と合計値と中央値と分散値と最頻値との重みづけ和でもよい（ステップＳ２０５）。
【００５６】
探索パラメータ算出部２００は、スケーリングされた検出済み動きベクトルのｘ成分の統計値を、探索範囲のｘ成分と定める（ステップＳ２０６）。探索パラメータ算出部２００は、スケーリングされた検出済み動きベクトルのｙ成分の統計値を、探索範囲のｙ成分と定める。
【００５７】
探索パラメータ算出部２００は、探索パラメータに基づいて探索パターンを定める（ステップＳ２０８）。
【００５８】
（探索パターン決定の第１例）
図１０は、ｘ成分の統計値とｙ成分の統計値を成分に持つベクトルの方向の例を示す図である。探索パターン決定の第１例では、探索パラメータ算出部２００は、スケーリングされた検出済み動きベクトルのｘ成分の統計値とスケーリングされた検出済み動きベクトルのｙ成分の統計値とが成す角度θに基づいて、探索パターンを定める。すなわち、探索パラメータ算出部２００は、x成分の統計値とy成分の統計値とを成分に持つベクトルの方向に基づいて、探索パターンを定める。例えば、探索パラメータ算出部２００は、ｘ成分の統計値とｙ成分の統計値との比に応じて探索範囲の長さを決定する。角度θは、式（２）によって表される。
【００５９】
θ＝ａｒｃｔａｎ（ｙ成分の統計値／ｘ成分の統計値）  …（２）
【００６０】
角度θは、ｘ成分の統計値とｙ成分の統計値との比に応じた値である。角度θは、x成分又はy成分のどちらの割合が高いかを示している。探索パラメータ算出部２００は、例えば、（−π／４≦θ＜π／４）が成立する場合、すなわち、x成分の割合がｙ成分よりも高い場合、x方向を重視した探索パターンを選択する。探索パラメータ算出部２００は、例えば、（−π／４≦θ＜π／４）が成立しない場合、すなわち、ｙ成分の割合がｘ成分よりも高い場合、ｙ方向を重視した探索パターンを選択する。
【００６１】
図１１は、第１の探索パターンの例を示す図である。探索パラメータ算出部２００は、（−π／２≦θ＜３π／８）が成立する場合、探索パターンとして第１の探索パターンを選択する。
【００６２】
図１２は、第２の探索パターンの例を示す図である。探索パラメータ算出部２００は、（−３π／８≦θ＜−π／８）が成立する場合、探索パターンとして第２の探索パターンを選択する。
【００６３】
図１３は、第３の探索パターンの例を示す図である。探索パラメータ算出部２００は、（−π／８≦θ＜π／８）が成立する場合、探索パターンとして第３の探索パターンを選択する。
【００６４】
図１４は、第４の探索パターンの例を示す図である。探索パラメータ算出部２００は、（π／８≦θ＜３π／８）が成立する場合、探索パターンとして第４の探索パターンを選択する。
【００６５】
（探索パターン決定の第２例）
探索パターン決定の第２例では、探索パラメータ算出部２００は、検出済み動きベクトルの分散値（探索パラメータ）に基づいて、探索パターンを定める。探索パラメータ算出部２００は、検出済み動きベクトルの分散値を算出する。検出済み動きベクトルの分散値が閾値以上である場合、動画像のシーケンスでは、フレームにおける物体の画像の動きには法則性が無いと考えられる。探索パラメータ算出部２００は、検出済み動きベクトルの分散値が閾値以上である場合、一部の探索点が省略された探索パターンを選択する。一部の探索点が省略された探索パターンとは、例えば、図５に示すドーナツ型探索パターンである。図２に示す動き探索部２０２は、一部の探索点が省略された探索パターンを用いて動きベクトルを離散的に探索する。これによって、動き探索部２０２は、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能となる。
【００６６】
（探索パターン決定の第３例）
図１５は、探索パターンを決定するための方法の例を示す図である。探索パターン決定の第３例では、探索パラメータ算出部２００は、参照フレームを参照する検出済み動きベクトルと対象ブロックを参照する検出済み動きベクトルとに基づいて、探索パターンを定める。
【００６７】
第１の検出済み動きベクトル４３２は、動きベクトル検出済みフレーム４３０において、対象フレーム４００の対象ブロック４０１の参照フレーム４１０を参照する動きベクトルである。参照フレーム４１０には、探索範囲４１１が定められている。第２の検出済み動きベクトル４３３は、動きベクトル検出済みフレーム４３０において、対象フレーム４００の対象ブロック４０１を参照する動きベクトルである。
【００６８】
第１の検出済み動きベクトル４３２は、式（３）によって表される。第２の検出済み動きベクトル４３３は、式（４）によって表される。
【００６９】
ｍｖ１＝（ｍｖ１ｘ, ｍｖ１ｙ）  …（３）
【００７０】
ｍｖ２＝（ｍｖ２ｘ, ｍｖ２ｙ）  …（４）
【００７１】
ｍｖ１ｘは、第１の検出済み動きベクトルのｘ成分である。ｍｖ１ｙは、第１の検出済み動きベクトルのｙ成分である。ｍｖ２ｘは、第２の検出済み動きベクトルのｘ成分である。ｍｖ２ｙは、第２の検出済み動きベクトルのｙ成分である。
【００７２】
探索パラメータ算出部２００は、第１の検出済み動きベクトルと第２の検出済み動きベクトルとの差分ベクトル（以下、「差分動きベクトル」という。）の方向α（探索パラメータ）に基づいて、探索パターンを定める。差分動きベクトルの方向αは、式（５）によって表される。
【００７３】
α＝ａｒｃｔａｎ（（ｍｖ２ｙ−ｍｖ１ｙ）／（ｍｖ２ｘ−ｍｖ１ｘ））…（５）
【００７４】
図１５では、（π／８≦α＜３π／８）が成立する。したがって、差分動きベクトルの方向αは、図１５における右上斜め方向に偏っている。この場合、探索パラメータ算出部２００は、差分動きベクトルの方向（探索パラメータ）に基づいて、右上斜め方向に偏っている探索パターンを選択する。右上斜め方向に偏っている探索パターンとは、例えば、図１４に示す第４の探索パターンである。これによって、動き探索部２０２は、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能となる。
【００７５】
以上のように、第１実施形態の動きベクトル算出部２０ａ（動きベクトル検出装置）は、探索パラメータ算出部２００と、動き探索部２０２とを備える。探索パラメータ算出部２００は、フレーム間の検出済み動きベクトルの水平成分の統計値及び垂直成分の統計値の少なくとも一方に基づいて動きベクトルの探索範囲の長さを決定する。動き探索部２０２は、長さが決定された探索範囲における探索点について動きベクトルを探索する。
【００７６】
これによって、第１実施形態の動画像符号化装置１は、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能となる。第１実施形態の動画像符号化装置１は、画像における物体が加速した等の理由によって動きベクトルが正確に算出されない場合でも、予測画像の精度を低下させないので、符号化効率を低下させない。
【００７７】
すなわち、第１実施形態の動画像符号化装置１は、探索パターン決定の第１例のように、検出済み動きベクトルの統計値に基づいて探索パラメータを適応的に変更する。これによって、第１実施形態の動画像符号化装置１は、動き探索の演算量の増加を抑えつつも適切な動きベクトルを算出することができる。
【００７８】
第１実施形態の動画像符号化装置１は、探索パターン決定の第２例のように、検出済み動きベクトルの統計値の成す角度に基づいて探索パラメータを適応的に変更する。これによって、第１実施形態の動画像符号化装置１は、最適な動きベクトルが存在する確率の高い範囲を割り出し、動きベクトルを効率的に算出することが可能となる。
【００７９】
第１実施形態の動画像符号化装置１は、探索パターン決定の第３例のように、対象ブロックを参照する動きベクトルに基づいて探索パラメータを適応的に変更する。これによって、第１実施形態の動画像符号化装置１は、最適な動きベクトルが存在する確率の高い範囲を割り出し、動きベクトルを効率的に算出することが可能となる。
【００８０】
（第２実施形態）
第２実施形態では、動きベクトル算出部の構成及び動作が、第１実施形態と相違する。第２実施形態では、第１実施形態との相違点についてのみ説明する。
【００８１】
図１６は、動きベクトル算出部２０ｂの構成の例を示す図である。動画像符号化装置１の動きベクトル算出部２０ｂは、探索パラメータ算出部２００と、探索中心算出部２０１と、動き探索部２０２とを備える。動きベクトル算出部２０ｂは、探索パラメータ制御部２０３を更に備える。
【００８２】
探索パラメータ制御部２０３は、探索パラメータを変更する。すなわち、探索パラメータ制御部２０３は、探索パラメータにより定まる探索パターンの探索範囲に含まれている探索点の数を変更する。探索パラメータ制御部２０３は、探索点の数が所定値となるまで、探索パターンの探索範囲から探索点を追加又は削除する。所定値は、予め定められる値である。探索パラメータ制御部２０３は、変更された探索パラメータを動き探索部２０２に送信する。
【００８３】
図１７は、動きベクトル算出部２０ｂの動作の例を示すフローチャートである。探索パラメータ算出部２００は、検出済み動きベクトルに基づいて探索パラメータを定める（ステップＳ３０１）。探索パラメータ制御部２０３は、探索パターンの探索範囲に含まれている探索点の数が所定値となるまで、探索パラメータを変更する（ステップＳ３０２）。探索中心算出部２０１は、検出済み動きベクトルに基づいて探索中心を定める（ステップＳ３０３）。動き探索部２０２は、変更された探索パラメータと探索中心とに基づいて、対象ブロックの動きベクトルを算出する（ステップＳ３０４）。
【００８４】
図１８は、探索点を削除することによる探索パターンの変更の例を示す図である。探索パラメータ制御部２０３は、一例として、図１４に示す第４の探索パターンを表す探索パラメータを、探索パラメータ算出部２００から取得する。探索中心３００は、第４の探索パターンの中心である。なお、探索パラメータ制御部２０３は、円や多角形などの任意形状の探索パターンを表す探索パラメータを、探索パラメータ算出部２００から取得してもよい。
【００８５】
探索パラメータ制御部２０３は、取得した探索パラメータの探索範囲に含まれている全ての探索点３０１を包含する最小面積の楕円３０２を算出する。探索パラメータ制御部２０３は、取得した探索パラメータの探索範囲に含まれている探索点３０１の数が所定値よりも多い場合、楕円３０２の楕円形状を維持したまま、中心３０３を中心として楕円３０２を縮小する。探索パラメータ制御部２０３は、探索点３０１の数が所定値になるまで探索点３０１を削除する。図１８では、探索パラメータ制御部２０３は、４個の探索点３０１を削除する。探索パラメータ制御部２０３は、楕円３０２に包含される探索点３０１のうち、中心３０３から遠い探索点３０１を優先して、探索点３０１を削除する。探索パラメータ制御部２０３は、中心３０３から同じ距離にある探索点３０１が複数ある場合、ラスタスキャンの順番が先である探索点３０１を優先して削除する。
【００８６】
図１８では、所定値は、一例として２７である。図１８の最も左に示す初期状態では、探索点３０１の数は３３である。探索パラメータ制御部２０３は、探索点３０１を６個削除する必要がある。探索パラメータ制御部２０３は、縮小した楕円３０２の領域外の探索点３０１−１及び３０１−２を削除する。探索パラメータ制御部２０３は、更に縮小した楕円３０２の領域外の探索点３０１−３〜３０１−６を削除する。
【００８７】
図１９は、探索点を追加することによる探索パターンの変更の例を示す図である。探索パラメータ制御部２０３は、一例として、図１４に示す第４の探索パターンを表す探索パラメータを、探索パラメータ算出部２００から取得する。中心３０３は、第４の探索パターンの中心である。なお、探索パラメータ制御部２０３は、円や多角形などの任意形状の探索パターンを表す探索パラメータを、探索パラメータ算出部２００から取得してもよい。
【００８８】
探索パラメータ制御部２０３は、楕円３０２を算出する。楕円３０２は、探索パラメータ制御部２０３が取得した探索パラメータにより定まる探索パターンの探索範囲に含まれている全ての探索点３０１を包含する最小面積の楕円である。
【００８９】
探索パラメータ制御部２０３は、取得した探索パラメータの探索範囲に含まれている探索点３０１の数が所定値よりも少ない場合、楕円３０２の楕円形状を維持したまま、中心３０３を中心として楕円３０２を拡大する。探索パラメータ制御部２０３は、探索点３０１の数が所定値になるまで探索点３０１を追加する。図１９では、探索パラメータ制御部２０３は、７個の探索点３０１を追加する。探索パラメータ制御部２０３は、楕円３０２に包含される探索点３０１のうち、中心３０３から近い探索点３０１を優先して、探索点３０１を追加する。探索パラメータ制御部２０３は、中心３０３から同じ距離にある探索点３０１が複数ある場合、ラスタスキャンの順番が先である探索点３０１を優先して追加する。
【００９０】
図１９では、所定値は、一例として４０である。図１９の最も左に示す初期状態では、探索点３０１の数は３３である。探索パラメータ制御部２０３は、探索点３０１を７個追加する必要がある。探索パラメータ制御部２０３は、拡大した楕円３０２の領域外の探索点３０１−７〜３０１−１０を追加する。探索パラメータ制御部２０３は、更に拡大した楕円３０２の領域外の探索点３０１−１１〜３０１−１３を追加する。図１９では、探索パラメータ制御部２０３は、探索点３０１−１４を追加しない。探索点３０１−１４のラスタスキャンの順番は、探索点３０１−１３のラスタスキャンの順番よりも後だからである。
【００９１】
なお、探索パラメータ制御部２０３が探索点の数が所定値となるまで探索範囲から探索点を追加又は削除する（探索範囲の長さを変更する）場合、探索範囲の面積は、探索点が追加又は削除される前後で同じ面積でもよい。したがって、探索パラメータ制御部２０３は、探索点を追加又は削除する前後で、探索範囲の形状を変更したとしても、探索範囲の面積を変更しなくてもよい。また、探索パラメータ制御部２０３は、探索点を追加又は削除する前後で、探索範囲の面積の変更量を閾値以内に収めてもよい。したがって、探索点が追加又は削除される前後で探索範囲の面積がほぼ同じ面積となるように、所定値の変更幅は閾値以下でもよい。
【００９２】
以上のように、第２実施形態の動きベクトル算出部２０ｂの探索パラメータ算出部２００は、探索範囲における探索点の数が所定値となるまで探索範囲の長さを変更する。探索パラメータ算出部２００は、探索範囲の長さを変更する前後で、探索範囲の面積の変更量を閾値以内に収めてもよい。
【００９３】
これによって、第２実施形態の動画像符号化装置１は、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能となる。第２実施形態の動画像符号化装置１は、画像における物体が加速した等の理由によって動きベクトルが正確に算出されない場合でも、予測画像の精度を低下させないので、符号化効率を低下させない。
【００９４】
すなわち、第２実施形態の動画像符号化装置１は、探索点の数が所定値となるまで探索点を追加又は削除することによって、探索パラメータを変更する。これによって、第２実施形態の動画像符号化装置１は、動き探索の演算量を制御して、適切な動きベクトルを算出することができる。ハードウェア実装では単位時間当たりの処理量が決まっているため、動き探索の演算量を制御することは有効である。
【００９５】
第２実施形態の動画像符号化装置１は、探索範囲の拡大又は縮小の前後で探索パターンが互いに相似形状となるように、探索範囲を拡大又は縮小する。これによって、第２実施形態の動画像符号化装置１は、単に探索点を追加又は削除する場合と比較して動きベクトルの精度を向上させて、動き探索の演算量を効率的に制御することができる。第２実施形態の動画像符号化装置１は、単に探索点を追加又は削除する場合と比較して動きベクトルの精度を維持したままでも、動き探索の演算量を効率的に制御することができる。
【００９６】
動画像符号化装置１が探索パターンの探索範囲を拡大又は縮小することによって、以下の（１）、（２）、（３）に示す効果が得られる。
（１）動画像符号化装置１が探索範囲を縮小した場合
動き探索の演算量は減少する。予測画像の精度は低下する場合がある。符号化効率は低下する場合がある。
（２）動画像符号化装置１が探索範囲の面積を変更しない場合（拡大又は縮小される前の探索範囲の面積と、拡大又は縮小された後の探索範囲の面積とがほぼ同じである場合）
動き探索の演算量の減少量又は増加量は少ない。予測画像の精度は向上する。符号化効率は向上する。
（３）動画像符号化装置１が探索範囲を拡大した場合、
動き探索の演算量は増加する。上記（２）と比較して、予測画像の精度は更に向上する。上記（２）と比較して、符号化効率は更に向上する。
【００９７】
（第３実施形態）
第３実施形態では、動きベクトル算出部の構成及び動作が、第１実施形態と相違する。第３実施形態では、第１実施形態との相違点についてのみ説明する。
【００９８】
図２０は、動きベクトル算出部２０ｃの構成の例を示す図である。動画像符号化装置１の動きベクトル算出部２０ｃは、探索パラメータ算出部２００と、探索中心算出部２０１と、動き探索部２０２とを備える。動きベクトル算出部２０ｃは、差分メモリ２０４と、探索パラメータ除外部２０５とを更に備える。以下、動きベクトルを検出済みであるブロックを「動きベクトル検出済みブロック」という。
【００９９】
動き探索部２０２は、差分情報（評価値）を差分メモリ２０４に記録する。差分情報とは、第１のブロックの画像特徴量と第２のブロックの画像特徴量との差を表す情報である。第１のブロックは、例えば、対象フレーム４００の対象ブロック４０１である。第１のブロックは、対象フレーム４００のブロックのうち対象ブロック４０１以外のブロックでもよい。例えば、第１のブロックは、対象フレーム４００の動きベクトル検出済みブロックでもよい。第１のブロックは、対象フレーム４００以外のフレームのブロックでもよい。第２のブロックは、例えば、参照フレーム４１０の参照ブロックである。
【０１００】
差分メモリ２０４は、差分情報（評価値）を動き探索部２０２から取得する。差分メモリ２０４は、差分情報を記憶する。差分メモリ２０４は、アクセスに応じて、差分情報を探索パラメータ除外部２０５に送信する。
【０１０１】
探索パラメータ除外部２０５は、探索パラメータを探索パラメータ算出部２００から取得する。探索パラメータ除外部２０５は、差分情報を差分メモリ２０４から取得する。探索パラメータ除外部２０５は、対象フレームにおける対象ブロック以外のブロックと参照ブロックとの差（差分情報）が閾値以下である探索点を、取得した探索パラメータの探索範囲から除外する。探索パラメータ除外部２０５は、探索点を除外した結果を表す探索パラメータを、動き探索部２０２に送信する。なお、探索パラメータ除外部２０５は、全ての探索点が探索範囲から除外される可能性がある場合、対象フレームにおける対象ブロック以外のブロックと参照ブロックとの差が最も大きい探索点を探索範囲から除外しなくてもよい。
【０１０２】
図２１は、動きベクトル算出部２０ｃの動作の例を示すフローチャートである。探索パラメータ算出部２００は、対象ブロックと同じ対象フレームに属する動きベクトル検出済みブロックの動きベクトルのうち、対象ブロックと同じ参照フレームを参照する検出済み動きベクトル（以下、「同フレーム参照動きベクトル」という。）が存在するか否かを判定する（ステップＳ４０１）。
【０１０３】
同フレーム参照動きベクトルが存在する場合（ステップＳ４０１：ＹＥＳ）、探索パラメータ算出部２００は、同フレーム参照動きベクトルに基づいて、探索パラメータを決定する（ステップＳ４０２）。探索中心算出部２０１は、同フレーム参照動きベクトルに基づいて、探索中心を決定する（ステップＳ４０３）。
【０１０４】
探索パラメータ除外部２０５は、対象フレームにおける対象ブロック以外のブロックと参照ブロックとの差（差分情報）が閾値以下である探索点を、取得した探索パラメータの探索範囲から除外する（ステップＳ４０４）。動きベクトル算出部２０ｃは、ステップＳ４０７に処理を進める。
【０１０５】
同フレーム参照動きベクトルが存在しない場合（ステップＳ４０１：ＮＯ）、探索パラメータ算出部２００は、同フレーム参照動きベクトル以外の検出済み動きベクトルに基づいて、探索パラメータを決定する（ステップＳ４０５）。探索中心算出部２０１は、同フレーム参照動きベクトル以外の検出済み動きベクトルに基づいて、探索中心を決定する（ステップＳ４０６）。動きベクトル算出部２０ｃは、ステップＳ４０７に処理を進める。
【０１０６】
動き探索部２０２は、探索パラメータ及び探索中心に基づいて、対象ブロックの動きベクトルを検出する（ステップＳ４０７）。動き探索部２０２は、差分情報を差分メモリ２０４に記録する（ステップＳ４０８）。
【０１０７】
図２２は、対象フレーム４００と参照フレーム４１０との例を示す図である。対象ブロック４０１は、符号化の対象となるブロックである。対象ブロック４０１は、対象フレーム４００に属する。動きベクトル検出済みブロック４０２は、動きベクトルが検出済みであるブロックである。動きベクトル検出済みブロック４０２は、対象フレーム４００に属する。探索範囲４１１は、対象ブロック４０１の動きベクトルの探索範囲である。探索範囲４１２は、動きベクトル検出済みブロック４０２の動きベクトルの探索範囲である。重複範囲４１３は、探索範囲４１１と探索範囲４１２とが重複している範囲である。
【０１０８】
探索中心ベクトル４０３は、対象ブロック４０１の動きベクトルであって、参照フレーム４１０の探索範囲４１１の探索中心を示す動きベクトルである。探索中心ベクトル４０４は、動きベクトル検出済みブロック４０２の動きベクトルであって、参照フレーム４１０の探索範囲４１２の探索中心を示す検出済み動きベクトルである。したがって、探索中心ベクトル４０４は、同フレーム参照動きベクトルである。
【０１０９】
探索パラメータ算出部２００は、同フレーム参照動きベクトルが存在するので、同フレーム参照動きベクトルである探索中心ベクトル４０４に基づいて、探索パラメータを決定する。探索中心算出部２０１は、探索中心ベクトル４０４に基づいて、探索中心を決定する。
【０１１０】
図２３は、対象フレームのブロックと参照ブロックとの差が小さい探索点を除外するための方法の例を示す図である。探索パターン５００は、対象ブロック４０１に対応付けられた探索パターンを示す。探索パターン５１０は、動きベクトル検出済みブロック４０２に対応付けられた探索パターンを示す。探索パターン５１０に記載された値は、動きベクトル検出済みブロック４０２と参照ブロックとの差（差分情報）を探索点ごとに表す値である。図２３では、参照ブロックは、参照フレーム４１０の探索範囲４１２に含まれているブロックである。
【０１１１】
探索パターン５２０は、探索パターン５００の探索点と探索パターン５１０の探索点とが対応付けられた結果を示す。すなわち、探索パターン５２０は、探索パターン５００と探索パターン５１０とが探索点の位置を合わせて重ねられた結果を示す。動きベクトル検出済みブロック４０２と参照ブロックとの差が閾値以下の探索点は、黒星印を用いて示されている。閾値は、一例として５０である。
【０１１２】
図２０に示す探索パラメータ除外部２０５は、重複している探索点のうち、動きベクトル検出済みブロック４０２と参照ブロックとの差が閾値以下である探索点を、取得した探索パラメータの探索範囲から除外する。図２３では、探索パラメータ除外部２０５は、１１個の探索点を除外する。探索パターン５３０は、変更された探索パラメータの探索パターンを示す。探索パラメータ除外部２０５は、探索パターン５３０を表す探索パラメータを、動き探索部２０２に送信する。
【０１１３】
以上のように、第３実施形態の検出済み動きベクトルである探索中心ベクトル４０４は、符号化の対象ブロック４０１の参照フレーム４１０を対象ブロック４０１が属する対象フレーム４００から参照する動きベクトルである。第３実施形態の動きベクトル算出部２０ｃの探索パラメータ算出部２００は、検出済み動きベクトルである探索中心ベクトル４０４を検出した際の差分情報（評価値）が閾値以下である探索点を、探索範囲から除外する。
【０１１４】
これによって、第３実施形態の動画像符号化装置１は、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能となる。第３実施形態の動画像符号化装置１は、画像における物体が加速した等の理由によって動きベクトルが正確に算出されない場合でも、予測画像の精度を低下させないので、符号化効率を低下させない。
【０１１５】
すなわち、第３実施形態の動画像符号化装置１は、同フレーム参照動きベクトルである探索中心ベクトル４０４を算出した際に算出された差分情報に基づいて、対象ブロック４０１の動きベクトルが指す先となる可能性が低い探索点を除外する。対象ブロック４０１の動きベクトルが指す先となる可能性が低い探索点とは、対象ブロックが候補となる確率の低い探索点である。これによって、第３実施形態の動画像符号化装置１は、動き探索の演算量を制御して、適切な動きベクトルを算出することができる。
【０１１６】
図２４は、対象フレーム４００の動きベクトル検出済みブロック４０２と参照ブロック４１４との差が小さい探索点を除外したことによる効果の例を示す図である。参照ブロック４１４は、動きベクトル検出済みブロック４０２が参照するブロックである。対象フレーム４００において異なるブロックが参照フレーム４１０において重なる可能性は低い。例えば、対象ブロック４０１と動きベクトル検出済みブロック４０２とが参照フレーム４１０において重なる可能性は低い。したがって、動きベクトル検出済みブロック４０２との差が小さい探索点（動きベクトル検出済みブロック４０２の画像に類似する画像の領域）が除外された場合でも、動きベクトル検出済みブロック４０２とは異なる対象ブロック４０１の予測画像の精度は低下しない。
【０１１７】
（第４実施形態）
第４実施形態では、動きベクトル算出部の構成及び動作が、第１実施形態と相違する。第４実施形態では、第１実施形態との相違点についてのみ説明する。
【０１１８】
図２５は、動きベクトル算出部２０ｄの構成の例を示す図である。動画像符号化装置１の動きベクトル算出部２０ｄは、探索パラメータ算出部２００と、探索中心算出部２０１と、動き探索部２０２とを備える。動きベクトル算出部２０ｄは、差分メモリ２０４と、探索パラメータ除外部２０５と、探索順序制御部２０６とを更に備える。
【０１１９】
以下、動き探索が施されるフレームの順序を「動き探索順序」という。探索順序制御部２０６は、符号化処理における参照構造に基づいて、符号化処理において参照されるフレームの順に動き探索順序を変更する。
【０１２０】
図２６は、動き探索順序の例を示す図である。フレーム６００とフレーム６１０とは、第１レイヤに属する。フレーム６２０は、第２レイヤに属する。フレーム６３０とフレーム６６０とは、第３レイヤに属する。フレーム６４０とフレーム６５０とフレーム６７０とフレーム６８０とは、第４レイヤに属する。
【０１２１】
図２６では、動画像符号化装置１は、階層型参照構造に基づいて、フレーム６００、フレーム６１０、フレーム６２０、フレーム６４０、フレーム６５０、フレーム６６０、フレーム６７０、フレーム６８０の順に符号化する。
【０１２２】
符号化処理において参照されるフレームは、参照される順に、フレーム６４０、フレーム６５０、フレーム６７０、フレーム６８０、フレーム６３０、フレーム６６０、フレーム６２０、フレーム６１０である。したがって、符号化処理において参照されるフレームのフレーム番号は、参照される順で、Ｆ１、Ｆ３、Ｆ５、Ｆ７、Ｆ２、Ｆ６、Ｆ４、Ｆ８である。
【０１２３】
動き探索順序は、変更される前では、フレーム６４０、フレーム６５０、フレーム６７０、フレーム６８０、フレーム６３０、フレーム６６０、フレーム６２０、フレーム６１０である。探索順序制御部２０６は、階層型参照構造に基づいて、参照されるフレームの順となるよう動き探索順序を変更する。したがって、動き探索順序は、変更された後では、フレーム６４０、フレーム６５０、フレーム６７０、フレーム６８０、フレーム６３０、フレーム６６０、フレーム６２０、フレーム６１０である。探索順序制御部２０６は、対象フレームの対象ピクチャを、動き探索を施す順に動き探索部２０２に送信する。
【０１２４】
図２５に示す動き探索部２０２は、対象フレームの対象ピクチャを、動き探索を施す順に探索順序制御部２０６から取得する。動き探索部２０２は、対象ピクチャと参照ピクチャと探索パラメータと探索中心とに基づいて、動き探索処理を実行する。動き探索部２０２は、対象ブロックの動きベクトルを、動き探索処理によって検出する。
【０１２５】
差分メモリ２０４は、動き探索の際に算出された差分情報を、動き探索部２０２から取得する。差分メモリ２０４は、差分情報を記憶する。差分メモリ２０４は、アクセスに応じて、差分情報を探索パラメータ除外部２０５に送信する。
【０１２６】
探索パラメータ除外部２０５は、探索パラメータを探索パラメータ算出部２００から取得する。探索パラメータ除外部２０５は、差分情報を差分メモリ２０４から取得する。探索パラメータ除外部２０５は、対象フレーム以外のフレームにおけるブロックと対象ブロックと参照ブロックとの差（差分情報）が閾値以上である探索点を、取得した探索パラメータの探索範囲から除外する。探索パラメータ除外部２０５は、探索点を除外した結果を表す探索パラメータを、動き探索部２０２に送信する。なお、探索パラメータ除外部２０５は、全ての探索点が探索範囲から除外される可能性がある場合、対象フレーム以外のフレームにおけるブロックと参照ブロックとの差が最も小さい探索点を探索範囲から除外しなくてもよい。
【０１２７】
以下、対象フレームとは異なるフレームのブロックが持つ検出済み動きベクトルであって、対象ブロックの参照フレームのブロックを指す検出済み動きベクトルが存在するという条件を「第１条件」という。
【０１２８】
以下、対象フレームとは異なるフレームのブロックが持つ第１の検出済み動きベクトルが対象フレームの参照フレームのブロックを指し、第１の検出済み動きベクトルを持つブロックが更に持つ第２の検出済み動きベクトルが対象フレームの対象ブロックを指すという条件を「第２条件」という。
【０１２９】
図２７は、動きベクトル算出部２０ｄの動作の例を示すフローチャートである。探索パラメータ算出部２００は、第１条件及び第２条件の両方が成立するか否かを判定する（ステップＳ５０１）。
【０１３０】
第１条件及び第２条件の両方が成立する場合（ステップＳ５０１：ＹＥＳ）、探索パラメータ算出部２００は、差分動きベクトルに基づいて、探索パラメータを決定する（ステップＳ５０２）。探索中心算出部２０１は、差分動きベクトルに基づいて、探索中心を決定する（ステップＳ５０３）。
【０１３１】
探索パラメータ除外部２０５は、対象フレーム以外のフレームにおけるブロックと参照ブロックとの差（差分情報）が閾値以上である探索点を、取得した探索パラメータの探索範囲から除外する（ステップＳ５０４）。動きベクトル算出部２０ｄは、ステップＳ５０７に処理を進める。
【０１３２】
第１条件又は第２条件が成立しない場合（ステップＳ５０１：ＮＯ）、探索パラメータ算出部２００は、差分動きベクトル以外の検出済み動きベクトルに基づいて、探索パラメータを決定する（ステップＳ５０５）。探索中心算出部２０１は、差分動きベクトル以外の検出済み動きベクトルに基づいて、探索中心を決定する（ステップＳ５０６）。動きベクトル算出部２０ｄは、ステップＳ５０７に処理を進める。
【０１３３】
動き探索部２０２は、探索パラメータ及び探索中心に基づいて、対象ブロックの動きベクトルを検出する（ステップＳ５０７）。動き探索部２０２は、差分情報を差分メモリ２０４に記録する（ステップＳ５０８）。
【０１３４】
図２８は、対象フレームと参照フレームと動きベクトル検出済みフレームとの例を示す図である。動きベクトル検出済みフレーム４３０は、時間軸方向について、対象フレーム４００と参照フレーム４１０との間に位置するフレームである。したがって、動きベクトル検出済みフレーム４３０は、対象フレーム４００とは異なるフレームである。
【０１３５】
図２８では、第１の検出済み動きベクトル４３２は、動きベクトル検出済みフレーム４３０の動きベクトル検出済みブロック４３４が持つ検出済み動きベクトルである。第１の検出済み動きベクトル４３２は、対象フレーム４００の参照フレーム４１０の探索範囲４１２のブロックを指している。
【０１３６】
図２８では、第２の検出済み動きベクトル４３３は、動きベクトル検出済みブロック４３４の検出済み動きベクトルである。第２の検出済み動きベクトル４３３は、対象フレーム４００の対象ブロック４０１を指している。動きベクトル検出済みブロック４３４は、第１の検出済み動きベクトル４３２を持つブロックである。
【０１３７】
動きベクトル検出済みブロック４３４は、対象ブロック４０１について、第１条件及び第２条件の両方が成立するか否かを判定する。図２８では、動きベクトル検出済みブロック４３４は、動きベクトル検出済みフレーム４３０のブロックである。第１の検出済み動きベクトル４３２は、対象フレーム４００の参照フレーム４１０のブロックを指す検出済み動きベクトルである。したがって、第１条件は成立する。図２８では、第１の検出済み動きベクトル４３２は、対象フレーム４００の参照フレーム４１０のブロックを指している。第２の検出済み動きベクトル４３３は、対象フレーム４００の対象ブロックを指している。したがって、第２条件も成立する。
【０１３８】
図２５に示す探索パラメータ算出部２００は、第１の検出済み動きベクトル４３２と第２の検出済み動きベクトル４３３との差分動きベクトルを算出する。探索パラメータ算出部２００は、差分動きベクトルに基づいて、探索パラメータを決定する。図２５に示す探索中心算出部２０１は、差分動きベクトルに基づいて、探索中心を決定する。
【０１３９】
図２９は、対象フレーム以外のフレームのブロックと参照ブロックとの差が大きい探索点を除外するための方法の例を示す図である。探索パターン５００は、対象ブロック４０１に対応付けられた探索パターンを示す。探索パターン５４０は、第１の検出済み動きベクトル４３２について動きベクトル検出済みブロック４３４に対応付けられた探索パターンを示す。探索パターン５４０に記載された値は、動きベクトル検出済みブロック４３４と参照ブロックとの差（差分情報）を探索点ごとに表す値である。図２９では、参照ブロックは、参照フレーム４１０の探索範囲４１２に含まれているブロックである。
【０１４０】
探索パターン５５０は、探索パターン５００の探索点と探索パターン５４０の探索点とが対応付けられた結果を示す。すなわち、探索パターン５５０は、探索パターン５００と探索パターン５４０とが探索点の位置を合わせて重ねられた結果を示す。対象ブロック４０１と参照ブロックとの差が閾値以下の探索点は、黒星印を用いて示されている。閾値は、一例として５０である。
【０１４１】
図２５に示す探索パラメータ除外部２０５は、重複している探索点のうち、動きベクトル検出済みブロック４３４と参照ブロックとの差が閾値以下である探索点を、取得した探索パラメータの探索範囲から除外する。図２９では、探索パラメータ除外部２０５は、７個の探索点を除外する。探索パターン５３０は、変更された探索パラメータの探索パターンを示す。探索パラメータ除外部２０５は、探索パターン５３０を表す探索パラメータを、動き探索部２０２に送信する。
【０１４２】
以上のように、第４実施形態の検出済み動きベクトルは、符号化の対象ブロック４０１の参照フレーム４１０を動きベクトル検出済みフレーム４３０から参照する第１の検出済み動きベクトル４３２と、対象ブロック４０１を動きベクトル検出済みフレーム４３０から参照する第２の検出済み動きベクトル４３３とである。探索パラメータ算出部２００は、第１の検出済み動きベクトル４３２を検出した際の差分情報（評価値）が閾値以上である探索点を、探索範囲から除外する。
【０１４３】
これによって、第４実施形態の動画像符号化装置１は、動き探索の演算量の増加を抑えても動きベクトルを効率的に算出することが可能となる。第４実施形態の動画像符号化装置１は、画像における物体が加速した等の理由によって動きベクトルが正確に算出されない場合でも、予測画像の精度を低下させないので、符号化効率を低下させない。
【０１４４】
すなわち、第４実施形態の動画像符号化装置１は、第２の検出済み動きベクトル４３３が指し示す対象ブロック４０１と第１の検出済み動きベクトル４３２を算出した際に算出された差分情報とに基づいて、対象ブロック４０１の動きベクトルが指す先となる可能性が低い探索点を除外する。対象ブロック４０１の動きベクトルが指す先となる可能性が低い探索点とは、対象ブロックが候補となる確率の低い探索点である。これによって、第４実施形態の動画像符号化装置１は、動き探索の演算量を制御して、適切な動きベクトルを算出することができる。
【０１４５】
図３０は、対象フレーム以外のフレームのブロックと参照ブロックとの差が大きい探索点を除外したことによる効果の例を示す図である。参照ブロック４１４は、対象ブロック４０１が参照するブロックの候補の一つである。参照ブロック４１５は、対象ブロック４０１が参照するブロックの候補の一つである。参照ブロック４１６は、動きベクトル検出済みブロック４３４が参照するブロックである。
【０１４６】
対象フレーム４００以外のフレームにおいて動きベクトル検出済みブロック４３４との差分が大きいブロックを、対象ブロック４０１が参照する可能性は低い。例えば、参照フレーム４１０において動きベクトル検出済みブロック４３４との差分が大きい参照ブロック４１４又は参照ブロック４１５を、対象ブロック４０１が参照する可能性は低い。
【０１４７】
第１の検出済み動きベクトル４３２が指し示すブロックの画像と第２の検出済み動きベクトル４３３が指し示すブロックの画像とは、同一物体の画像である可能性が高い。動きベクトル検出済みブロック４３４の画像と対象ブロック４０１の画像とは、類似する可能性が高い。したがって、動きベクトル検出済みブロック４３４との差が大きい探索点（動きベクトル検出済みブロック４３４の画像に類似しない画像の領域）が除外された場合でも、第２の検出済み動きベクトル４３３が指し示す対象ブロック４０１の予測画像の精度は低下しない。
【０１４８】
上述した実施形態における動画像符号化装置及び動きベクトル検出装置の少なくとも一部をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。
【０１４９】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【産業上の利用可能性】
【０１５０】
本発明は、動画像を符号化する動画像符号化装置に適用可能である。
【符号の説明】
【０１５１】
１…動画像符号化装置、１０…減算器、１１…直交変換・量子化部、１２…可変長符号化部、１３…逆量子化・逆直交変換部、１４…加算器、１５…ループフィルタ、１６…復号ピクチャメモリ、１７…イントラ予測部、１８…インタ予測部、１９…スイッチ、２０ａ〜２０ｄ…動きベクトル算出部、２１…動きベクトルメモリ、１００…対象フレーム、１１０…参照フレーム、１１１…探索範囲、１２０…中継フレーム、２００…探索パラメータ算出部、２０１…探索中心算出部、２０２…動き探索部、２０３…探索パラメータ制御部、２０４…差分メモリ、２０５…探索パラメータ除外部、２０６…探索順序制御部、３００…探索中心、３０１…探索点、３０２…楕円、３０３…中心、４００…対象フレーム、４０１…対象ブロック、４０２…動きベクトル検出済みブロック、４０３…探索中心ベクトル、４０４…探索中心ベクトル、４０５…探索中心ベクトル、４１０…参照フレーム、４１１…探索範囲、４１２…探索範囲、４１３…重複範囲、４１４…参照ブロック、４１５…参照ブロック、４１６…参照ブロック、４２０…参照フレーム、４３０…動きベクトル検出済みフレーム、４３１…検出済み動きベクトル、４３２…第１の検出済み動きベクトル、４３３…第２の検出済み動きベクトル、４３４…動きベクトル検出済みブロック、５００…探索パターン、５１０…探索パターン、５２０…探索パターン、５３０…探索パターン、５４０…探索パターン、５５０…探索パターン、５６０…探索パターン、６００…フレーム、６１０…フレーム、６２０…フレーム、６３０…フレーム、６４０…フレーム、６５０…フレーム、６６０…フレーム、６７０…フレーム、６８０…フレーム
【図１】
0006538609.tif 000002
【図２】
0006538609.tif 000003
【図３】
0006538609.tif 000004
【図４】
0006538609.tif 000005
【図５】
0006538609.tif 000006
【図６】
0006538609.tif 000007
【図７】
0006538609.tif 000008
【図８】
0006538609.tif 000009
【図９】
0006538609.tif 000010
【図１０】
0006538609.tif 000011
【図１１】
0006538609.tif 000012
【図１２】
0006538609.tif 000013
【図１３】
0006538609.tif 000014
【図１４】
0006538609.tif 000015
【図１５】
0006538609.tif 000016
【図１６】
0006538609.tif 000017
【図１７】
0006538609.tif 000018
【図１８】
0006538609.tif 000019
【図１９】
0006538609.tif 000020
【図２０】
0006538609.tif 000021
【図２１】
0006538609.tif 000022
【図２２】
0006538609.tif 000023
【図２３】
0006538609.tif 000024
【図２４】
0006538609.tif 000025
【図２５】
0006538609.tif 000026
【図２６】
0006538609.tif 000027
【図２７】
0006538609.tif 000028
【図２８】
0006538609.tif 000029
【図２９】
0006538609.tif 000030
【図３０】
0006538609.tif 000031
【図３１】
0006538609.tif 000032
【図３２】
0006538609.tif 000033
【図３３】
0006538609.tif 000034
【図３４】
0006538609.tif 000035
【図３５】
0006538609.tif 000036