(57)【要約】【課題】動きベクトル探索プログラムのコードサイズを増加させることなく、動きベクトル探索処理の精度を向上させ、且つ、その計算量を削減するための動きベクトル探索装置を提供する。【解決手段】動きベクトル探索装置１０は、動きベクトルを探索するためのアルゴリズム１０１を記憶するアルゴリズム記憶部１００と、アルゴリズム１０１に基づいて動きベクトルを探索するための探索点を選択する探索点選択部１２０と、を備えている。  アルゴリズム１０１は、複数の状態リストを含んでいる。各状態リストは、探索点の候補の座標が定義された探索座標と、遷移先の状態リストが定義された遷移先状態と、の対を含んでいる。探索点選択部１２０は、アルゴリズム記憶部１００から複数の状態リストの１つを取得し、その状態リストに基づいて探索点を選択し、その探索点に対応する動きベクトルを探索する。【選択図】図２
2010068105.tif 000002
【特許請求の範囲】
【請求項１】
動きベクトルを探索するためのアルゴリズムを記憶するアルゴリズム記憶部と、
前記アルゴリズムに基づいて前記動きベクトルを探索するための探索点を選択する探索点選択部と、を備え、
前記アルゴリズムは、複数の状態リストを含み、
各状態リストは、前記探索点の候補の座標が定義された探索座標と、遷移先の状態リストが定義された遷移先状態と、の対を含み、
前記探索点選択部は、前記アルゴリズム記憶部から前記複数の状態リストの１つを取得し、その状態リストに基づいて前記探索点を選択し、その探索点に対応する動きベクトルを探索することを特徴とする動きベクトル探索装置。
【請求項２】
前記探索点選択部は、前記アルゴリズム記憶部から取得された状態リストの中から前記探索座標を選択し、選択された探索座標と対を成す遷移先状態に基づいて前記アルゴリズム記憶部から新しい状態リストを取得する請求項１に記載の動きベクトル探索装置。
【請求項３】
前記探索点選択部は、
原画像ブロックおよび参照画像のコストを計算するコスト計算部と、
前記コスト計算部によって計算されたコストに基づいて前記探索点の候補を選択する制御部と、を備える請求項２に記載の動きベクトル探索装置。
【請求項４】
前記アルゴリズムを変更するための変更情報に基づいて前記探索点選択部によって取得されるべき状態リストを決定するアルゴリズム制御部をさらに備え、
前記探索点選択部は、前記アルゴリズム記憶部から前記アルゴリズム制御部によって決定された状態リストを取得する請求項１乃至３の何れか１項に記載の動きベクトル探索装置。
【請求項５】
前記アルゴリズム制御部は、条件を設定可能な条件設定レジスタと、遷移先状態を設定可能な遷移先状態設定レジスタと、を備え、前記条件設定レジスタに設定された条件が成立する場合に、前記探索点選択部によって取得されるべき状態リストを前記遷移先状態設定レジスタに設定された状態に対応する状態リストへ遷移させる請求項４に記載の動きベクトル探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動きベクトル探索装置に関し、特に、動画像を符号化するときの動きベクトル探索処理に用いられる動きベクトル探索装置に関する。
【背景技術】
【０００２】
一般的な動画像符号化装置には、基準となるフレームの動きをベクトルとして表現するための動きベクトルを探索する動きベクトル探索装置と、動画像符号化装置を制御するコントローラと、動きベクトルを用いて予測画像を生成する予測画像生成部と、原画像データおよび参照画像データを記憶するメモリと、が設けられている。
【０００３】
従来の動きベクトル探索装置は、メモリから原画像データの一部（以下、「原画像ブロック」という）および参照画像データを入力し、コントローラから参照画像の一部分（以下、「参照画像ブロック」という）のサイズ、原画像ブロックのサイズ、原画像ブロックの原画像上の座標、および探索を開始する参照画像上の座標（以下、「探索開始点座標」という）などの制御情報を入力する。そして、この動きベクトル探索装置は、様々な動きベクトル探索方法に基づいて動きベクトルを探索し、その探索結果を予測画像生成部に出力する。
【０００４】
従来の動きベクトル探索装置は、動きベクトル探索処理に大きな計算量を必要とするので、その計算量を削減するための様々なアルゴリズムを用いている。たとえば、探索を複数のステップに分割し、広範囲を粗い精度で探索し、ステップが進むごとに探索範囲を絞り込み、探索精度を上げていくアルゴリズムや、動きベクトルの値が大きいときには探索精度が悪くても符号化効率への影響が少ない傾向があることを利用して、周囲のブロックの動きベクトルから予測した動きベクトル予測値や探索の途中結果を用いて探索範囲および探索精度を変更するアルゴリズムや、近傍のマクロブロックの動きベクトルから補間した動きベクトルを探索の中心点とするアルゴリズムなどが知られている（特許文献１を参照）。
【０００５】
また、従来の動きベクトル探索装置は、動きベクトル探索処理の精度を向上させるために、上記のような複雑なアルゴリズムをできるだけ多く実装する動きベクトル探索プログラムに基づいて動きベクトル探索処理を行っている。
【０００６】
しかしながら、上記のような動きベクトル探索プログラムは、複雑なアルゴリズムを多く実装するので、コードサイズが極めて大きくなる。その結果、動きベクトル探索プログラムの設計者の手間が増加し、且つ、動きベクトル探索プログラムを格納するメモリの容量が大きく消費される。特に、動画像符号化装置が他の装置に組み込まれる場合には、メモリの容量に厳しい制限が課せられるので、この問題は重大である。
【特許文献１】特開２００６−２５４３４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、動きベクトル探索プログラムのコードサイズを増加させることなく、動きベクトル探索処理の精度を向上させ、且つ、その計算量を削減するための動きベクトル探索装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明の第１態様によれば、
動きベクトルを探索するためのアルゴリズムを記憶するアルゴリズム記憶部と、
前記アルゴリズムに基づいて前記動きベクトルを探索するための探索点を選択する探索点選択部と、を備え、
前記アルゴリズムは、複数の状態リストを含み、
各状態リストは、前記探索点の候補の座標が定義された探索座標と、遷移先の状態リストが定義された遷移先状態と、の対を含み、
前記探索点選択部は、前記アルゴリズム記憶部から前記複数の状態リストの１つを取得し、その状態リストに基づいて前記探索点を選択し、その探索点に対応する動きベクトルを探索することを特徴とする動きベクトル探索装置が提供される。
【発明の効果】
【０００９】
本発明によれば、動きベクトル探索プログラムのコードサイズを増加させることなく、動きベクトル探索処理の精度を向上させ、且つ、その計算量を削減することができる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施例について図面を参照して説明する。なお、以下の実施例は、本発明の実施の一形態であって、本発明の範囲を限定するものではない。
【実施例１】
【００１１】
はじめに、本発明の実施例１について説明する。本発明の実施例１は、アルゴリズム記憶部に記憶された探索アルゴリズムに基づいて動きベクトルを探索する動きベクトル探索装置の例である。
【００１２】
まず、本発明の実施例１に係る動きベクトル探索装置の構成について図１乃至図３を参照して説明する。図１は、本発明の実施例１に係る動きベクトル探索装置１０を含む動画像符号化装置１の構成を示すブロック図である。図２は、本発明の実施例１に係る動きベクトル探索装置１０の構成を示すブロック図である。図３は、図２の探索アルゴリズム１０１のデータ構造を示す概略図である。
【００１３】
図１に示すように、動画像符号化装置１は、動きベクトル探索装置１０と、コントローラ２０と、予測画像生成部３０と、メモリ４０と、を備えている。
【００１４】
図１に示すように、動きベクトル探索装置１０は、コントローラ２０、予測画像生成部３０、およびメモリ４０に接続されている。また、動きベクトル探索装置１０は、コントローラ２０の制御に従って、動画像の動きベクトルを探索し、探索された動きベクトル１０ａを予測画像生成部３０に出力する。
【００１５】
図１に示すように、コントローラ２０は、動きベクトル探索装置１０に接続されている。また、コントローラ２０は、動きベクトル探索装置１０を制御するための制御情報２０ａを動きベクトル探索装置１０に出力する。制御情報２０ａには、探索開始点座標および初期状態が含まれている。
【００１６】
図１に示すように、予測画像生成部３０は、動きベクトル探索装置１０に接続されている。また、予測画像生成部３０は、動きベクトル探索装置１０から探索された動きベクトル１０ａを入力し、入力された動きベクトル１０ａに基づいて予測画像３０ａを生成して、生成された予測画像３０ａを外部装置（図示せず）に出力する。
【００１７】
図１に示すように、メモリ４０は、動きベクトル探索装置１０に接続されている。また、メモリ４０は、原画像データ４０１および参照画像データ４０２を記憶可能である。
【００１８】
図２に示すように、動きベクトル探索装置１０は、アルゴリズム記憶部１００と、探索点選択部１２０と、を備えている。
【００１９】
図２に示すように、アルゴリズム記憶部１００は、制御部１２１（後述する）に接続されている。また、アルゴリズム記憶部１００は、動きベクトルを探索するための探索アルゴリズム１０１を記憶可能である。また、アルゴリズム記憶部１００は、制御部１２１（後述する）によって取得されるべき状態リスト１２１ａ（後述する）を特定する状態番号を保存する状態保存レジスタ１０２を備えている。
【００２０】
図３に示すように、探索アルゴリズム１０１は、探索点と遷移先の状態との間の関係を定義する状態リストを含む状態遷移表である。状態遷移表の「探索座標」には、探索点の候補の座標が定義され、「遷移先状態」には、遷移先の状態を特定する状態番号が定義されている。「探索座標」および「遷移先状態」は、状態リスト毎に定義されている。なお、Ｅは、終了状態を定義している。
【００２１】
図２に示すように、探索点選択部１２０は、制御部１２１と、コスト計算部１２２と、補間画像生成部１２３と、を備えている。
【００２２】
図２に示すように、制御部１２１は、アルゴリズム記憶部１００およびコスト計算部１２２、ならびにコントローラ２０および予測画像生成部３０に接続されている。また、制御部１２１は、コントローラ２０から制御情報２０ａを入力し、アルゴリズム記憶部１００から状態リスト１２１ａを取得し、コスト計算部１２２の計算結果（後述するコスト値）に基づいて状態リスト１２１ａの中から１つの探索点（たとえば、原画像ブロック１２２ｂに最も類似する参照画像ブロック１２２ｃに対応する探索点）を選択して、選択された探索点の座標１２１ｂ，１２１ｃをアルゴリズム記憶部１００およびコスト計算部１２２に出力する。また、制御部１２１は、終了状態になったときに、動きベクトル１０ａを予測画像生成装置３０に出力する。
【００２３】
図２に示すように、コスト計算部１２２は、制御部１２１および補間画像生成部１２３、ならびにメモリ４０に接続されている。また、コスト計算部１２２は、制御部１２１から探索点の座標１２１ｃを入力し、メモリ４０から原画像データ４０１の一部分である原画像ブロック１２２ｂおよび参照画像データ４０２の一部分である参照画像ブロック１２２ｃを入力し、探索点の座標１２１ｃに示される参照画像ブロック１２２ｃと原画像ブロック１２２ｂの１画素毎の差分絶対値を全画素について算出し、その差分絶対値の合計値を算出することによって原画像ブロック１２２ｂを符号化するのに必要なデータサイズ（以下、「コスト」という）を計算し、その計算結果（以下、「コスト値」という）１２２ａを制御部１２１に出力する。このとき、コスト計算部１２２は、探索点の座標１２１ｃの精度が整数画素より細かい（たとえば、１／２画素や１／４画素などである）場合には、補間画像生成部１２３に探索点の座標１２２ｄおよび参照画像ブロック１２２ｅを出力し、補間画像生成部１２３から補間画像ブロック１２３ａを入力して、その補間画像ブロック１２３ａのコストを計算する。
【００２４】
図２に示すように、補間画像生成部１２３は、コスト計算部１２２に接続されている。また、補間画像生成部１２３は、コスト計算部１２２から探索点の座標１２２ｄおよび参照画像ブロック１２２ｅを入力し、補間画像ブロック１２３ａを生成して、その補間画像ブロック１２３ａをコスト計算部１２２に出力する。
【００２５】
次に、本発明の実施例１に係る動きベクトル探索装置の処理について図４乃至図７を参照して説明する。図４は、本発明の実施例１に係る動きベクトル探索処理の処理手順を示すフローチャートである。図５乃至図７は、本発明の実施例１に係る動きベクトル探索処理における探索点の状態遷移を示す概略図である。なお、図５乃至図７において、各座標の数字は、その探索点が選択されたときに遷移先となる状態番号を定義し、Ｅは終了状態を定義している。
【００２６】
はじめに、図４に示すように、探索点選択工程（Ｓ４０１）が行われる。探索点選択工程（Ｓ４０１）では、制御部１２１が、探索点を選択して、選択された探索点の座標１２１ｂ，１２１ｃをアルゴリズム記憶部１００およびコスト計算部１２２に出力する。このとき、制御部１２１は、最初に行われる探索点選択工程（Ｓ４０１）では、コントローラ２０から入力された制御情報２０ａに含まれる探索開始点座標に基づいて探索点を選択し、２回目以降に行われる探索点選択工程（Ｓ４０１）では、アルゴリズム記憶部１００から取得された状態リスト１２１ａに基づいて遷移先の探索点を選択する。また、アルゴリズム記憶部１００は、制御部１２１によって取得されるべき状態リスト１２１ａを特定する状態番号を状態保存レジスタ１０２に保存している。制御部１２１は、状態保存レジスタ１０２に保存された状態番号に対応する状態リスト１２１ａをアルゴリズム記憶部１００から取得する。たとえば、制御情報２０ａに含まれる初期状態が状態１である場合には、制御部１２１は、アルゴリズム記憶部１００から図５に示す状態１の状態リスト１２１ａを取得する。このとき、制御部１２１は、座標（０，０）を探索点として選択した場合には、座標（０，０）の状態番号が２であるので、アルゴリズム記憶部１００から図６に示す状態２の状態リスト１２１ａを取得し、座標（−６，０）を探索点として選択した場合には、座標（−６，０）の状態番号が３であるので、アルゴリズム記憶部１００から図７に示す状態３の状態リスト１２１ａを取得する。
【００２７】
次に、図４に示すように、探索点選択工程（Ｓ４０１）において選択された探索点が整数画素でない場合には（Ｓ４０２−ＮＯ）、補間画像生成工程（Ｓ４０３）が行われる。補間画像生成工程（Ｓ４０３）では、補間画像生成部１２３が、コスト計算部１２２から入力された探索点の座標１２２ｄおよび参照画像ブロック１２２ｅに基づいて補間画像ブロック１２３ａを生成する。
【００２８】
一方、図４に示すように、探索点選択工程（Ｓ４０１）において選択された探索点が整数画素である場合（Ｓ４０２−ＹＥＳ）または補間画像生成工程（Ｓ４０３）の後に、コスト計算工程（Ｓ４０４）が行われる。コスト計算工程（Ｓ４０４）では、コスト計算部１２２が、制御部１２１から入力された探索点の座標１２１ｃ、ならびにメモリ４０から入力された原画像ブロック１２２ｂの座標（Ｘａ，Ｙａ）および参照画像ブロック１２２ｃの座標（Ｘｂ，Ｙｂ）を決定し、探索点の座標１２１ｃに示される参照画像ブロック１２２ｃのコストを計算する。このとき、コスト計算部１２２は、補間画像生成工程（Ｓ４０３）が行われた場合には、補間画像生成部１２３から入力された補間画像ブロック１２３ａのコストを計算する。
【００２９】
探索点選択工程（Ｓ４０１）乃至コスト計算工程（Ｓ４０４）は、終了状態になるまで繰り返される（Ｓ４０５−ＮＯ）。終了状態か否かは、アルゴリズム記憶部１００から取得された状態リスト１２１ａに終了状態が定義されているか否かに基づいて判断される。
【００３０】
終了状態になった場合には（Ｓ４０５−ＹＥＳ）、動きベクトル出力工程（Ｓ４０６）が行われる。動きベクトル出力工程（Ｓ４０６）では、制御部１２１が、コスト計算工程（Ｓ４０４）において決定された原画像ブロック１２２ｂの座標（Ｘａ，Ｙａ）および参照画像ブロック１２２ｃの座標（Ｘｂ，Ｙｂ）に基づいて、終了状態に至るまでの探索点に対応する動きベクトル１０ａ（Ｘａ−Ｘｂ，Ｙａ−Ｙｂ）を予測画像生成装置３０に出力する。
【００３１】
本発明の実施例１に係る動きベクトル探索処理は、動きベクトル出力工程（Ｓ４０６）の後に終了する。
【００３２】
本発明の実施例１によれば、図２に示すように、制御部１２１が、アルゴリズム記憶部１００に記憶された探索アルゴリズム１０１に基づいて動きベクトルを探索するので、動きベクトル探索プログラムのコードサイズを増加させることなく、動きベクトル探索処理の精度を向上させ、且つ、その計算量を削減することができる。
【００３３】
特に、動きベクトル探索処理の途中結果を用いて探索アルゴリズム１０１を動的に変更することが容易に実現できる。また、探索アルゴリズム１０１の種類が増えたとしても、アルゴリズム記憶部１００に状態リストを追加するだけで済むので、コードサイズの増加を抑えることができる。
【実施例２】
【００３４】
次に、本発明の実施例２について説明する。本発明の実施例２は、コントローラから探索アルゴリズムの選択に有用な情報を入力し、その情報に基づいてアルゴリズム記憶部の状態を強制的に書き換える動きベクトル探索装置の例である。なお、本発明の実施例１と同様の内容についての説明は省略する。
【００３５】
まず、本発明の実施例２に係る動きベクトル探索装置の構成について図８および図９を参照して説明する。図８は、本発明の実施例２に係る動きベクトル探索装置１０を含む動画像符号化装置１の構成を示すブロック図である。図９は、本発明の実施例２に係るアルゴリズム制御部１４０の構成を示すブロック図である。
【００３６】
図８に示すように、本発明の実施例２に係る動きベクトル探索装置１０は、本発明の実施例１に係る動きベクトル探索装置１０と同様の構成に加えて、アルゴリズム制御部１４０を備えている。
【００３７】
図８に示すように、コントローラ２０は、制御情報２０ａに加えて、探索アルゴリズム１００の選択に有用な変更情報２０ｂを動きベクトル探索装置１０に出力する。たとえば、変更情報２０ｂは、処理の締め切り時間や、カメラの加速度センサの検知結果や、前フレームまたは周囲のブロックから予測された動きベクトルや、ユーザによって予め入力された画像の特徴（たとえば、動きが激しいこと）などを示す情報である。
【００３８】
図８に示すように、アルゴリズム制御部１４０は、アルゴリズム記憶部１００およびコントローラ２０に接続されている。また、アルゴリズム制御部１４０は、コントローラ２０から変更情報２０ｂを入力し、入力された変更情報２０ｂに基づいて制御部１２１によって取得されるべき状態リスト１２１ａを決定する。
【００３９】
図９に示すように、アルゴリズム制御部１４０は、条件設定レジスタ１４１と、遷移先状態設定レジスタ１４２と、を備えている。条件設定レジスタ１４１には、強制変更を有効にする状態、閾値、および比較方法の３つの条件が設定され、遷移先状態設定レジスタ１４１には、条件設定レジスタ１４１に設定された比較方法に基づいて、変更情報２０ｂと閾値との条件式が成立する場合の遷移先の状態番号が設定される。また、アルゴリズム制御部１４０は、状態保存レジスタ１０２に保存された状態番号を取得して強制変更を有効にするか否かを判断するとともに、遷移先状態設定レジスタ１４２に設定された状態番号を状態保存レジスタ１０２に保存する。なお、条件設定レジスタ１４１および遷移先状態設定レジスタ１４２に対する設定は、ユーザによって行われる。
【００４０】
次に、本発明の実施例２に係るアルゴリズム制御処理について図１０を参照して説明する。図１０は、本発明の実施例２に係るアルゴリズム制御処理の処理手順を示すフローチャートである。
【００４１】
はじめに、図１０に示すように、設定工程（Ｓ１００１）が行われる。設定工程（Ｓ１００１）では、アルゴリズム制御部１４０が、条件設定レジスタ１４１に所定の条件を設定し、遷移先状態レジスタ１４２に遷移先の状態番号を設定する。
【００４２】
次に、図１０に示すように、設定工程（Ｓ１００１）において条件設定レジスタ１４１に設定された条件が成立した場合には（Ｓ１００２−ＹＥＳ）、遷移工程（Ｓ１００３）が行われる。遷移工程（Ｓ１００３）では、アルゴリズム制御部１４０が、遷移先状態レジスタ１４２に設定された状態番号を状態保存レジスタ１０２に保存する。
【００４３】
本発明の実施例２に係るアルゴリズム制御処理は、設定工程（Ｓ１００１）において条件設定レジスタ１４１に設定された条件が成立しなかった場合（Ｓ１００２−ＮＯ）または遷移工程（Ｓ１００３）の後に終了する。
【００４４】
本発明の実施例２によれば、図１０に示すように、アルゴリズム制御部１４０が状態保存レジスタ１０２に保存された値を制御するので、初期状態において締切までの残り時間が少ない場合に、処理時間の短いアルゴリムに変更することができる。
【図面の簡単な説明】
【００４５】
【図１】本発明の実施例１に係る動きベクトル探索装置１０を含む動画像符号化装置１の構成を示すブロック図である。
【図２】本発明の実施例１に係る動きベクトル探索装置１０の構成を示すブロック図である。
【図３】図２の探索アルゴリズム１０１のデータ構造を示す概略図である。
【図４】本発明の実施例１に係る動きベクトル探索処理の処理手順を示すフローチャートである。
【図５】本発明の実施例１に係る動きベクトル探索処理における探索点の状態遷移を示す概略図である。
【図６】本発明の実施例１に係る動きベクトル探索処理における探索点の状態遷移を示す概略図である。
【図７】本発明の実施例１に係る動きベクトル探索処理における探索点の状態遷移を示す概略図である。
【図８】本発明の実施例２に係る動きベクトル探索装置１０を含む動画像符号化装置１の構成を示すブロック図である。
【図９】本発明の実施例２に係るアルゴリズム制御部１４０の構成を示すブロック図である。
【図１０】本発明の実施例２に係るアルゴリズム制御処理の処理手順を示すフローチャートである。
【符号の説明】
【００４６】
１  動画像符号化装置
１０  動きベクトル探索装置
１００  アルゴリズム記憶部
１０２  状態保存レジスタ
１２０  探索点選択部
１２１  制御部
１２２  コスト計算部
１２３  補間画像生成部
１４０  アルゴリズム制御部
２０  コントローラ
３０  予測画像生成部
４０  メモリ
【図１】
2010068105.tif 000003
【図２】
2010068105.tif 000004
【図３】
2010068105.tif 000005
【図４】
2010068105.tif 000006
【図５】
2010068105.tif 000007
【図６】
2010068105.tif 000008
【図７】
2010068105.tif 000009
【図８】
2010068105.tif 000010
【図９】
2010068105.tif 000011
【図１０】
2010068105.tif 000012