(57)【要約】【課題】  動きベクトルの探索速度を向上させることと、動きベクトルの探索のために使用される記憶装置の容量の増加を抑制させることとの双方を両立させる。【解決手段】  動きベクトルの探索範囲が閾値より広い場合には、動きベクトルの探索範囲の上半分と下半分とを異なるＳＲＡＭ１００３、１００４に記憶する。一方、動きベクトルの探索範囲が閾値以下の場合には、動きベクトルの探索範囲のライン単位毎に参照画像データを異なるＳＲＡＭ１００３、１００４にインターリーブして記憶する。このようにすることによって、ＳＲＡＭ１００３、１００４の記憶容量の増大を抑制しながら、複数のブロックマッチング演算器１００７、１００８における並列動作を従来よりも確実に且つ高速に実行することができる。【選択図】  図３
2008177925.tif 000002
【特許請求の範囲】
【請求項１】
入力された処理対象フレームとの相関を求めるための参照フレームを記憶する第１の記憶媒体と、
前記第１の記憶媒体よりも読み出し速度が高速である複数の第２の記憶媒体と、
前記第１の記憶媒体に記憶された参照フレームの一部のデータであって、動きベクトルの探索範囲内にある参照画像データを、前記第２の記憶媒体に記憶する記憶手段と、
前記処理対象フレームの一部のデータである処理対象データと、前記参照画像データとの相関に基づいて動きベクトルを探索する動きベクトル探索手段と、
前記記憶手段によって参照画像データが記憶される前記第２の記憶媒体の記憶フォーマットを、前記動きベクトルの探索範囲と、前記第２の記憶媒体の予め定められた関係とに基づいて決定する決定手段とを有し、
前記記憶手段は、前記決定手段によって決定された記憶フォーマットに従って複数に分割された参照画像データを、前記複数の第２の記憶媒体に個別に記憶し、
前記動きベクトル探索手段は、前記処理対象データと、前記記憶フォーマットにより複数の第２の記憶媒体に記憶された参照画像データとの相関を並列に求めることを特徴とする動きベクトル探索装置。
【請求項２】
前記複数の記憶フォーマットは、前記動きベクトルの探索範囲内にある参照画像データをｍ行ｎ列（ｍ、ｎは１以上の自然数であり、且つ少なくとも一方は２以上）の複数に分割し、分割された参照画像データを前記第２の記憶媒体に記憶する第１の記憶フォーマットと、前記動きベクトルの探索範囲内にある参照画像データのライン単位毎にインターリーブして、その参照画像データを前記第２の記憶媒体に記憶する第２の記憶フォーマットとを含むことを特徴とする請求項１に記載の動きベクトル探索装置。
【請求項３】
前記決定手段は、前記動きベクトル探索ポイント間の最大距離が、前記第２の記憶媒体のアドレスの数よりも大きい場合に、前記第１の記憶フォーマットを、前記第２の記憶媒体の記憶フォーマットとし、前記動きベクトル探索ポイント間の最大距離が、前記第２の記憶媒体のアドレスの数よりも小さい場合に、前記第２の記憶フォーマットを、前記第２の記憶媒体の記憶フォーマットと決定することを特徴とする請求項２に記載の動きベクトル探索装置。
【請求項４】
前記決定手段は、前記動きベクトルの探索範囲内にある参照画像データが、前記第２の記憶媒体の容量より大きい場合に、前記第１の記憶フォーマットを前記第２の記憶媒体の記憶フォーマットとし、前記動きベクトルの探索範囲内にある参照画像データが、前記第２の記憶媒体の容量より小さい場合に、前記第２の記憶フォーマットを前記第２の記憶媒体の記憶フォーマットと決定することを特徴とする請求項２に記載の動きベクトル探索装置。
【請求項５】
入力された処理対象フレームとの相関を求めるための参照フレームを記憶する第１の記憶媒体と、
前記第１の記憶媒体よりも読み出し速度が高速である複数の第２の記憶媒体とを用いて動きベクトルの探索を行う動きベクトル探索方法であって、
前記第１の記憶媒体に記憶された参照フレームの一部のデータであって、動きベクトルの探索範囲内にある参照画像データを、前記第２の記憶媒体に記憶する記憶ステップと、
前記処理対象フレームの一部のデータである処理対象データと、前記参照画像データとの相関に基づいて動きベクトルを探索する動きベクトル探索ステップと、
前記記憶ステップによって参照画像データが記憶される前記第２の記憶媒体の記憶フォーマットを、前記動きベクトルの探索範囲と、前記第２の記憶媒体の予め定められた関係とに基づいて決定する決定ステップとを有し、
前記記憶ステップは、前記決定ステップによって決定された記憶フォーマットに従って複数に分割された参照画像データを、前記複数の第２の記憶媒体に個別に記憶し、
前記動きベクトル探索ステップは、前記処理対象データと、前記記憶フォーマットにより複数の第２の記憶媒体に記憶された参照画像データとの相関を並列に求めることを特徴とする動きベクトル探索方法。
【請求項６】
前記複数の記憶フォーマットは、前記動きベクトルの探索範囲内にある参照画像データのｍ行ｎ列（ｍ、ｎは１以上の自然数であり、且つ少なくとも一方は２以上）の複数に分割し、分割された参照画像データを前記第２の記憶媒体に記憶する第１の記憶フォーマットと、前記動きベクトルの探索範囲内にある参照画像データのライン単位毎に、インターリーブして、その参照画像データを前記第２の記憶媒体に記憶する第２の記憶フォーマットとを含むことを特徴とする請求項５に記載の動きベクトル探索方法。
【請求項７】
入力された処理対象フレームとの相関を求めるための参照フレームを記憶する第１の記憶媒体と、
前記第１の記憶媒体よりも読み出し速度が高速である複数の第２の記憶媒体とを用いて動きベクトルの探索を行うことをコンピュータに実行させるためのコンピュータプログラムであって、
前記第１の記憶媒体に記憶された参照フレームの一部のデータであって、動きベクトルの探索範囲内にある参照画像データを、前記第２の記憶媒体に記憶する記憶ステップと、
前記処理対象フレームの一部のデータである処理対象データと、前記参照画像データとの相関に基づいて動きベクトルを探索する動きベクトル探索ステップと、
前記記憶ステップによって参照画像データが記憶される前記第２の記憶媒体の記憶フォーマットを、前記動きベクトルの探索範囲と、前記第２の記憶媒体の予め定められた関係とに基づいて決定する決定ステップとをコンピュータに実行させ、
前記記憶ステップは、前記決定ステップによって決定された記憶フォーマットに従って複数に分割された参照画像データを、前記複数の第２の記憶媒体に個別に記憶し、
前記動きベクトル探索ステップは、前記処理対象データと、前記記憶フォーマットにより複数の第２の記憶媒体に記憶された参照画像データとの相関を並列に求めることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動きベクトル探索装置、動きベクトル探索方法、及びコンピュータプログラムに関し、特に、動きベクトルを探索するために用いて好適なものである。
【背景技術】
【０００２】
フルＨＤＴＶ（1920×1080画素）等の大画面化へ対応するために、動きベクトル探索ポイントの数を増加させ、高い圧縮効率を実現するためには、如何に動きベクトルの探索処理を高速化させるかが重要となる。
このような観点から、特許文献１には、動きベクトルを探索すると共に、現画像をブロック単位で符号化する符号化処理部を複数実装し、それら複数の符号化処理部が並列に動作することにより、動きベクトルの探索を並列化させることが開示されている。
【０００３】
【特許文献１】特開平８−９３８５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、前述した従来の技術では、複数の符号化処理部が使用するＳＲＡＭ（Static ＲＡＭ）が重複する場合、それら複数の符号化処理部は、他の符号化処理部の処理が終わるまで、処理を待たなければならなくなる虞がある。
そこで、各符号化処理部（動きベクトルの探索を行うためのブロックマッチング演算器）の夫々に、独立したＳＲＡＭを割り当てる方法がある。しかしながら、このような方法では、符号化処理部の数を増加させる(動きベクトルの探索の並列度を増加させる)程、記憶装置の総容量が増加してしまい、コストが高くなってしまうという問題点がある。
【０００５】
本発明はかかる問題点に鑑みてなされたものであり、動きベクトルを並列に探索するに際し、動きベクトルの探索速度を向上させることと、動きベクトルの探索のために使用される記憶装置の容量の増加を抑制させることとの双方を両立させることを目的とする。
【課題を解決するための手段】
【０００６】
本発明の動きベクトル探索装置は、入力された処理対象フレームとの相関を求めるための参照フレームを記憶する第１の記憶媒体と、前記第１の記憶媒体よりも読み出し速度が高速である複数の第２の記憶媒体と、前記第１の記憶媒体に記憶された参照フレームの一部のデータであって、動きベクトルの探索範囲内にある参照画像データを、前記第２の記憶媒体に記憶する記憶手段と、前記処理対象フレームの一部のデータである処理対象データと、前記参照画像データとの相関に基づいて動きベクトルを探索する動きベクトル探索手段と、前記記憶手段によって参照画像データが記憶される前記第２の記憶媒体の記憶フォーマットを、前記動きベクトルの探索範囲と、前記第２の記憶媒体の予め定められた関係とに基づいて決定する決定手段とを有し、前記記憶手段は、前記決定手段によって決定された記憶フォーマットに従って複数に分割された参照画像データを、前記複数の第２の記憶媒体に個別に記憶し、前記動きベクトル探索手段は、前記処理対象データと、前記記憶フォーマットにより複数の第２の記憶媒体に記憶された参照画像データとの相関を並列に求めることを特徴とする。
【０００７】
本発明の動きベクトル探索方法は、入力された処理対象フレームとの相関を求めるための参照フレームを記憶する第１の記憶媒体と、前記第１の記憶媒体よりも読み出し速度が高速である複数の第２の記憶媒体とを用いて動きベクトルの探索を行う動きベクトル探索方法であって、前記第１の記憶媒体に記憶された参照フレームの一部のデータであって、動きベクトルの探索範囲内にある参照画像データを、前記第２の記憶媒体に記憶する記憶ステップと、前記処理対象フレームの一部のデータである処理対象データと、前記参照画像データとの相関に基づいて動きベクトルを探索する動きベクトル探索ステップと、前記記憶ステップによって参照画像データが記憶される前記第２の記憶媒体の記憶フォーマットを、前記動きベクトルの探索範囲と、前記第２の記憶媒体の予め定められた関係とに基づいて決定する決定ステップとを有し、前記記憶ステップは、前記決定ステップによって決定された記憶フォーマットに従って複数に分割された参照画像データを、前記複数の第２の記憶媒体に個別に記憶し、前記動きベクトル探索ステップは、前記処理対象データと、前記記憶フォーマットにより複数の第２の記憶媒体に記憶された参照画像データとの相関を並列に求めることを特徴とする。
【０００８】
本発明のコンピュータプログラムは、入力された処理対象フレームとの相関を求めるための参照フレームを記憶する第１の記憶媒体と、前記第１の記憶媒体よりも読み出し速度が高速である複数の第２の記憶媒体とを用いて動きベクトルの探索を行うことをコンピュータに実行させるためのコンピュータプログラムであって、前記第１の記憶媒体に記憶された参照フレームの一部のデータであって、動きベクトルの探索範囲内にある参照画像データを、前記第２の記憶媒体に記憶する記憶ステップと、前記処理対象フレームの一部のデータである処理対象データと、前記参照画像データとの相関に基づいて動きベクトルを探索する動きベクトル探索ステップと、前記記憶ステップによって参照画像データが記憶される前記第２の記憶媒体の記憶フォーマットを、前記動きベクトルの探索範囲と、前記第２の記憶媒体の予め定められた関係とに基づいて決定する決定ステップとをコンピュータに実行させ、前記記憶ステップは、前記決定ステップによって決定された記憶フォーマットに従って複数に分割された参照画像データを、前記複数の第２の記憶媒体に個別に記憶し、前記動きベクトル探索ステップは、前記処理対象データと、前記記憶フォーマットにより複数の第２の記憶媒体に記憶された参照画像データとの相関を並列に求めることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、動きベクトルの探索範囲と第２の記憶媒体の予め設定された関係とに基づいて、高速で読み出しを行う第２の記憶媒体への参照画像データの記憶フォーマットを適応的に決定するようにした。したがって、第２の記憶媒体の容量の増加を抑制させつつ、動きベクトルを効率よく並列に探索することができる。
【発明を実施するための最良の形態】
【００１０】
次に、図面を参照しながら、本発明の実施形態について説明する。
（フレーム間予測動画像符号化）
例えばMPEG-2（Motion Picture Experts Group Phase 2）では、フレーム間予測動画像符号化方式が採用されている。フレーム間予測動画像符号化方式では、動画像の動きを探索して動きを補償した後に、直交変換、量子化、及びエントロピー符号化を行う。このように、フレーム間予測動画像符号化方式では、動画像の時間的に異なるフレーム間の相関性を利用して動画像データの符号量を効果的に削減するようにしている。
【００１１】
図１は、MPEG-2におけるフレーム間予測の方法の一例を概念的に示す図である。
図１において、処理対象フレーム１０１は、１６×１６画素の処理対象領域１０１ａ毎に分割される。この分割された処理対象領域１０１ａの処理対象データ毎に動きベクトル１０３が探索される。参照フレーム１０２は、符号化された動画像データを復号化した再構成動画像データである。参照フレーム１０２内の領域であって、処理対象領域１０１ａに対応する位置の領域を含む周囲の画素群が動きベクトル探索範囲１０４となる。動きベクトル探索範囲１０４内の領域であって、処理対象領域１０１ａと同じサイズの参照領域１０４ａをずらしながら、処理対象領域１０１ａと参照領域１０４ａとの相関度を求める。そして、相関度の最も大きい処理対象領域１０１ａと参照領域１０４ａとの相対位置を動きベクトル１０３として求める。このような処理を処理対象フレーム１０１の処理対象領域１０１ａと、動きベクトル探索範囲１０４とをずらしながら順次行う。
尚、相関度の測定には、例えば、処理対象領域１０１ａと参照領域１０４ａとの互いに対応する位置の画素の差分絶対値和等が用いられる。この差分絶対値和の値が小さいほど相関度が高いと評価される。
【００１２】
（フレーム間予測動画像符号化装置の構成）
図２は、以上述べたようなフレーム間予測動画像符号化を実行するフレーム間予測動画像符号化装置の構成の一例を示す図である。
図２において、フレーム間予測動画像符号化装置は、減算器６０１、直交変換器６０２、量子化器６０３、スキャン処理器６０４、エントロピー符号化器６０５、及び逆量子化器６０６を備えている。更に、フレーム間予測動画像符号化装置は、逆直交変換器６０７、加算器６０８、バスインターフェース（Bus I/F）６０９、及び動きベクトル探索器・参照画像生成器６１０を備えている。また、バスインターフェース６０９を介して、大容量記憶装置（DRAM（Dynamic ＲＡＭ））６１１及び他のサブモジュール６１２と、フレーム間予測動画像符号化装置とが相互に接続される。
【００１３】
図２において、減算器６０１は、処理対象フレーム１０１に相当する原動画像データＤ１から、後述するようにして動きベクトル探索器・参照画像生成器６１０から出力される参照画像データＤ２を減算する。そして、減算器６０１は、その減算した結果である予測誤差Ｄ３を直交変換器６０２へ出力する。ただし、減算器６０１は、時間的に異なる複数のフレームからの予測を行うフレーム間予測動画像符号化を実行する場合にこのような動作を行う。画面内の情報のみで符号化を行うフレーム内符号化を実行する場合には、この減算器６０１による減算処理が実行されずに、原動画像データＤ１が直交変換器６０２へ出力される。
【００１４】
直交変換器６０２は、減算器６０１から出力されたデータ（予測誤差Ｄ３又は原動画像データＤ１）に対し、ブロック単位に直交変換を施して直交変換係数Ｄ４を算出し、算出した直交変換係数Ｄ４を量子化器６０３へ出力する。尚、直交変換係数Ｄ４は、例えばＤＣＴ（Discrete Cosine Transform）係数である。また、この直交変換を施すブロックと、動き補償を行う領域とは必ずしも一致するものではない。
【００１５】
量子化器６０３は、前記ブロック内の位置に対応する「量子化テーブルの値」と、そのブロックの量子化スケールの値とを用いて、直交変換係数Ｄ４を量子化する。そして、量子化器６０３は、量子化した全ての直交変換係数を、スキャン処理器６０４と逆量子化器６０６とに出力する。スキャン処理器６０４は、符号化モードに応じてジグザグスキャン等のスキャン処理を行う。エントロピー符号化器６０５は、スキャン処理器６０４から出力されたデータをエントロピー符号化し、エントロピー符号化したデータを符号Ｄ５として出力する。
【００１６】
動きベクトルの探索（検出）と動き補償とを行うために、逆量子化器６０６及び逆直交変換器６０７を用いて局所復号化処理が行われる。
逆量子化器６０６は、前記ブロックの量子化スケールの値を用いて、量子化器６０３で量子化された直交変換係数を逆量子化して、逆量子化係数を算出し、算出した逆量子化係数を逆直交変換器６０７へ出力する。逆直交変換器６０７は、逆量子化係数に対し、ブロック単位で逆直交変換を施すことにより予測誤差を復号化し、復号化した予測誤差を加算器６０８へ出力する。
【００１７】
加算器６０８は、動きベクトル探索器・参照画像生成器６１０から出力された参照画像データＤ２と、逆直交変換器６０７で復号化された予測誤差とを加算することにより、参照フレームＤ７（図１の参照フレーム１０２に相当）を復号化する。そして、加算器６０８は、バスインターフェース６０９を介して、その参照フレームＤ７をＤＲＡＭ６１１に出力する。
【００１８】
動きベクトル探索器・参照画像生成器６１０は、処理対象フレーム１０１に相当する原動画像データＤ１と、ＤＲＡＭ６１１に記憶された参照フレームＤ７とを用いて、動きベクトルの探索を行う。動きベクトル探索器・参照画像生成器６１０は、探索した動きベクトルと、ＤＲＡＭ６１１に記憶された参照フレームＤ７とを用いて、動き補償を行うための参照画像データ（ブロックデータ）Ｄ２を生成し、減算器６０１と加算器６０８とに出力する。
【００１９】
（動きベクトル探索器・参照画像生成器６１０の構成）
図３は、動きベクトル探索装置の一例である動きベクトル探索器・参照画像生成器６１０の構成の一例を詳細に示した図である。
図３において、動きベクトル探索器・参照画像生成器６１０は、メモリコントローラ１０１１、ＳＲＡＭ１００３、１００４、ブロックマッチング演算器１００７、１００８、動きベクトル探索器１０１０、及び選択器１００５、１００６、１００９を備える。
【００２０】
メモリコントローラ１０１１は、ＤＲＡＭ６１１に記憶されている参照フレームＤ７の中から、動きベクトルの探索範囲（検出範囲）に対応する参照画像データを、バスインターフェース６０９を介して読み出す。そして、メモリコントローラ１０１１は、動きベクトルの探索範囲が閾値よりも大きい場合、動きベクトルの探索範囲に対応する参照画像データのうち、上半分の参照画像データをＳＲＡＭ１００３に記憶し、下半分の参照画像データをＳＲＡＭ１００４に記憶する。一方、メモリコントローラ１０１１は、動きベクトルの探索範囲が閾値以下の場合、動きベクトルの探索範囲に対応する参照画像データのうち、奇数ラインの参照画像データをＳＲＡＭ１００３に記憶し、偶数ラインの参照画像データをＳＲＡＭ１００４に記憶する。このように、本実施形態では、動きベクトルの探索範囲に対応する参照画像データを２つに分割したものをＳＲＡＭ１００３、１００４に個別に記憶するようにしている。
【００２１】
ここでＤＲＡＭとＳＲＡＭの特性を比較すると、ＤＲＡＭ６１１は、単位面積あたりの容量（記憶できるデータ量）が大きいが読み出し速度が低速であるという特徴がある。一方、ＳＲＡＭ１００３、１００４は、単位面積あたりの容量が小さいが読み出し速度が高速であるという特徴がある。動きベクトルの探索を繰り返し行う場合には、参照フレームＤ７内の「動きベクトルの探索範囲に対応する参照画像データ」を多くの回数読み出す必要がある。この場合、ＤＲＡＭ６１１から毎回参照画像データを読み出すのでは処理が遅くなってしまう。よって、本実施形態では、ＤＲＡＭ６１１に記憶されている参照フレームＤ７の中から、動きベクトルの探索範囲に対応する参照画像データを、処理速度が高速なＳＲＡＭ１００３、１００４にコピーする。そして、ＳＲＡＭ１００３、１００４に記憶されている参照画像データを繰り返し読み出しながら実際の動きベクトルの探索を行うことで処理の高速化を実現している。
以上のように本実施形態では、例えば、ＤＲＡＭ６１１を用いて第１の記憶媒体が実現され、ＳＲＡＭ１００３を用いて第２の記憶媒体が実現され、メモリコントローラ１０１１を用いて記憶手段及び決定手段が実現される。
【００２２】
メモリコントローラ１０１１は、動きベクトル探索アルゴリズムに基づいて、ＳＲＡＭ１００３、１００４から読み出すべき参照画像データのアドレスを決定する。ＳＲＡＭ１００３、１００４から読み出された参照画像データは、選択器１００５、１００６の選択動作に従って、ブロックマッチング演算器１００７又は１００８に出力される。
【００２３】
ここで、本実施形態では、動きベクトルの探索範囲が閾値より大きい場合、ブロックマッチング演算器１００７は、ＳＲＡＭ１００３から参照画像データを読み出し、動きベクトルの探索範囲の上半分に関して動きベクトルを探索する。一方、ブロックマッチング演算器１００８は、ＳＲＡＭ１００４から参照画像データを読み出し、動きベクトルの探索範囲内の下半分に関して動きベクトルを探索する。
【００２４】
また、動きベクトルの探索範囲が閾値以下の場合、ブロックマッチング演算器１００７、１００８は、奇数ラインについてはＳＲＡＭ１００３から参照画像データを読み出し、偶数ラインについてはＳＲＡＭ１００３から参照画像データを読み出す。そして、読み出した参照画像データを用いて動きベクトルを探索する。
【００２５】
２つのＳＲＡＭ１００３、１００４は、２つのブロックマッチング演算器１００７、１００８から選択器１００５、１００６を介してアクセスされることが可能である。２つのＳＲＡＭ１００３は、動きベクトルの探索状況に応じて、選択器１００５、１００６を用いてデータフローを制御することが可能である。このように、動きベクトルの探索領域を複数に分割し、分割した領域の参照画像データを夫々ＳＲＡＭ１００３、１００４に個別に保存することにより並列に動きベクトルを探索することができ、動きベクトルの探索動作を高速化することが可能となる。
【００２６】
ブロックマッチング演算器１００７、１００８は、処理対象フレーム１０１に相当する原動画像データＤ１と、参照領域１０４ａに対応する参照画像データであって、選択器１００５、１００６から出力された参照画像データとの相関を計算する。そして、ブロックマッチング演算器１００７、１００８は、計算した結果を動きベクトル探索器１０１０へ出力する。尚、原動画像データＤ１と、参照画像データとの相関は、互いに対応する位置の画素の差分の絶対値を求め、求めた絶対値のブロック内における総和を表すＳＡＤ（Sum of Absolute value）を求めることで得ることができる。
【００２７】
（ブロックマッチング演算器１００７、１００８の基本動作）
図４は、ブロックマッチング演算器１００７、１００８の基本動作の一例を示した図である。図４では、８×８画素単位でブロックマッチングを行い、参照フレーム１０２の一部である１６×１６画素の領域のデータが、ＳＲＡＭ１００３、１００４に記憶されているとする。ＳＲＡＭ１００３、１００４は、１ＲＷ（１サイクルで１アドレスのデータを読み込むか、１サイクルで１アドレスにデータを書き込むことが可能）である。図４においては、ＳＲＡＭ１００３、１００４の１アドレスに１ライン分（１６画素）の参照画像データが記憶されている。
【００２８】
ブロックマッチング演算器１００７、１００８は、ＳＲＡＭ１００３、１００４から、１アドレス分のデータを読み出し、１６画素の中から８画素のみを選択する。そして、ブロックマッチング演算器１００７、１００８は、選択した８画素と、処理対象フレーム１０１に相当する原動画像データＤ１の８画素とのＳＡＤを計算する。この計算を８回繰り返すことで８×８画素ブロックのＳＡＤを計算する。
そして、ブロックマッチング演算器１００７、１００８は、８×８画素ブロックのＳＡＤの計算を、動きベクトル探索ポイントの数だけ繰り返す。
【００２９】
図３に説明を戻し、動きベクトル探索器１０１０は、ブロックマッチング演算器１００７、１００８で計算されたＳＡＤのうち、一番値が小さかったＳＡＤに対応する動きベクトルを最適な動きベクトルとして探索する。
メモリコントローラ１０１１は、動きベクトル探索器１０１０で探索された動きベクトルの情報Ｄ８を入力し、入力した動きベクトルの情報Ｄ８に基づいて選択器１００９を制御する。選択器１００９は、メモリコントローラ１０１１の制御に基づいて、動きベクトル探索器１０１０で探索された動きベクトルに対応する参照画像データＤ２を、減算器６０１と加算器６０８に出力する。尚、以上のような動きベクトルの探索回数（ブロックマッチングの回数）が多ければ多いほど、より最適な動きベクトルを探索することができ、結果として符号化効率を向上させることが可能となる。
以上のように本実施形態では、ブロックマッチング演算器１００７、１００８、動きベクトル探索器１０１０、メモリコントローラ１０１１、及び選択器１１０９を用いて、動きベクトル探索手段が実現される。
【００３０】
（H.264におけるフレーム間予測動画像符号化）
ところで、近年新しく定められたH.264ビデオ動画像標準符号化方式においては、符号化効率を更に向上させるために、動き補償を行う単位領域の大きさ（以下、動き補償単位と称する）を適応的に変化させることができることが定められている。図５は、H.264ビデオ動画像標準符号化方式におけるフレーム間予測の方法の一例を概念的に示す図である。
【００３１】
MPEG-2では、動き補償単位が１６画素×１６ラインのマクロブロック単位のみと定められていた。これに対し、図５に示すように、H.264では、符号化単位のマクロブロックを様々な分割方法により分割し、分割した領域を動き補償単位（動きベクトルの探索範囲５０１）とすることにより、動き補償の自由度を高めるようにしている。このように動き補償の自由度が高い場合には、互いに異なる動き補償の単位の夫々について動きベクトル５０２ａ〜５０２ｅを探索して、動き補償の単位と動きベクトルとの両方を決定する必要がある。このような場合、ブロックマッチングの回数を、例えばMPEG-2に従って行われるブロックマッチングの回数より多くする必要がある。一般的に動画像符号化装置における処理速度のボトルネックとなる箇所（一番時間がかかる処理）は、動きベクトルの探索処理である。従って、動きベクトルの探索を如何に高速化させるかが重要となる。
【００３２】
（動きベクトルの探索範囲が広い場合の問題点）
ここで、動きベクトルの探索範囲がそれほど広くない場合には、その範囲内の全ての参照画像データをＳＲＡＭに記憶した後に動きベクトルを探索することが可能である。これに対し、動きベクトルの探索範囲が広くなると、従来の技術では、動きベクトルの探索範囲分、ＳＲＡＭを実装しなければならない。しかしながら、コストの高いＳＲＡＭを実装することは現実的ではない。そこで、動きベクトルの探索範囲が広い場合には、ＳＲＡＭに記憶されている参照画像データを入れ替えながら、動きベクトルを広範囲にわたって探索できるようにする必要が生じてくる。
【００３３】
図６は、参照画像データを入れ替える方法の一例を概念的に示した図である。
図６において、動きベクトルの探索範囲は４８×４８画素であり、ＳＲＡＭ１００３、１００４には１６×４８画素のみが記憶されるとする。また、図６（ａ）に示す矢印は、動きベクトルの探索順序を示している。動きベクトルの探索範囲に対応する参照画像データが、１６×１６画素のブロックに分割されると、まずブロックＡ、Ｂ、Ｃが、ＤＲＡＭ６１１からＳＲＡＭ１００３、１００４にコピーされる。そして、ブロックＡから順に動きベクトルの探索が実行される。ブロックＡについて、動きベクトルの探索が終わると、メモリコントローラ１０１１は、ＤＲＡＭ６１１からブロックＤの参照画像データを読み出し、読み出したブロックＤの参照画像データをブロックＡの参照画像データに上書きする。その後、ブロックＢについて、動きベクトルの探索が終わると、メモリコントローラ１０１１は、ＤＲＡＭ６１１からブロックＥの参照画像データを読み出し、ブロックＥの参照画像データをブロックＢの参照画像データに上書きする。以上のような処理を順次行いながら動きベクトルが決定される。このように動きベクトルの探索範囲が広い場合には、参照画像データの入れ替えの動作が必要となる。
【００３４】
（動きベクトル探索器・参照画像生成器６１０の動作）
図７は、動きベクトル探索範囲が広い場合のＳＲＡＭ１００３、１００４の記憶フォーマットの一例を示した図である。尚、図７の枡目に示されている円は、ブロックマッチング演算器１００７でブロックマッチングを行う際に用いられる動きベクトル探索ポイント７０１ａ〜７０１ｅを示しており、その円内の番号は、ブロックマッチングの順序を示している。また、図７の枡目に示されている菱形は、ブロックマッチング演算器１００８でブロックマッチングを行う際に用いられる動きベクトル探索ポイント７０２ａ〜７０２ｄを示しており、その菱形内の番号は、ブロックマッチングの順序を示している。また、円内の番号と、菱形内の番号とが同じ動きベクトル探索ポイント７０１、７０２は、ブロックマッチング演算器１００７、１００８によって並列で処理される。
【００３５】
本実施形態において、動きベクトル探索範囲が広い場合とは、動きベクトル探索ポイント間の最大距離が、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数よりも大きい場合をいう。図７に示す例では、動きベクトル探索ポイント７０１ａ〜７０１ｃと、動きベクトル探索ポイント７０２ａ〜７０２ｃとの距離が「２４」であり、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数（＝１９）よりも大きい。
【００３６】
このように動きベクトルの探索範囲が広い程、動きベクトル探索ポイント７０１、７０２が複数のＳＲＡＭ１００３、１００４にまたがって存在する可能性が高くなる。特に、前述したように、動きベクトル探索ポイント間の最大距離が、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数よりも大きい場合には、動きベクトル探索ポイントが必ず複数のＳＲＡＭ１００３、１００４にまたがって存在する。
そこで、メモリコントローラ１０１１は、動きベクトル探索ポイント間の最大距離が、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数よりも大きいか否かを判断する。そして、メモリコントローラ１０１１は、動きベクトル探索ポイント間の最大距離が、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数よりも大きい場合には、図７に示す記憶フォーマットを選択する。すなわち、メモリコントローラ１０１１は、動きベクトルの探索範囲に対応する参照画像データのうち、上半分の参照画像データをＳＲＡＭ１００３に記憶し、下半分の参照画像データをＳＲＡＭ１００４に記憶する記憶フォーマットを選択する。これにより、動きベクトルの探索範囲に対応する参照画像データのうち、上半分の参照画像データがＳＲＡＭ１００３に記憶され、下半分の参照画像データがＳＲＡＭ１００４に記憶される。
【００３７】
また、前述したように、動きベクトルの探索範囲が広い場合には、参照画像データの入れ替え作業が必要となる。動きベクトルの探索範囲の上半分と下半分とを異なるＳＲＡＭに記憶する図７に示す方式は、動きベクトルの探索範囲のライン単位毎に参照画像データを異なるＳＲＡＭにインターリーブして記憶する図９に示す方式に比べると、次のような利点がある。すなわち、図７に示す方式は、図９に示す方式に比べ、参照画像データの入れ替えの際の競合が発生しにくい。
【００３８】
図８は、図７に示した記憶フォーマットのＳＲＡＭ１００３、１００４へブロックマッチング演算器１００７、１００８がアクセスする様子と、ＤＲＡＭ６１１からＳＲＡＭ１００３、１００４へ参照画像データを入れ替える様子との一例を概念的に示す図である。尚、図８では、ブロックマッチング演算器１００７、１００８を、夫々第１、第２のブロックマッチング演算器と表記している。また、動きベクトル探索ポイント７０１ａ〜７０１ｄを、夫々第１のブロックマッチング演算器における第１〜第４の探索ポイントと表記している。更に、動きベクトル探索ポイント７０２ａ〜７０２ｄを、夫々第２のブロックマッチング演算器における第１〜第４の探索ポイントと表記している。また、ＳＲＡＭ１００３、１００４を、夫々第１、第２のＳＲＡＭと表記している。更に、第１のＳＲＡＭのメモリアドレスに付されている丸付き数字は、図７に示すＳＲＡＭ１００３のアドレスとして表記されている数字に対応する。そして、第２のＳＲＡＭのメモリアドレスに付されている菱形付き数字は、図７に示すＳＲＡＭ１００４のアドレスとして表記されている数字に対応する。
【００３９】
また、図８に付されている矢印は、ＳＲＡＭ１００３、１００４（第１、第２のＳＲＡＭ）から読み出された参照画像データが、どのブロックマッチング演算器１００７、１００８で用いられているかを示している。尚、動きベクトル探索ポイント７０１ｄ、７０２ｄ（第４の探索ポイント）に対応する動きベクトルの探索においては、全ての読み出しアドレスを、ブロックマッチング演算器１００７、１００８（第１、第２のブロックマッチング演算器）で共有できる。
【００４０】
図８では、動きベクトル探索ポイント７０１ｃ（第３の探索ポイント）に対応する動きベクトルの探索が終わると、ブロックマッチング演算器１００７（第１のブロックマッチング演算器）は、ＳＲＡＭ１００３（第１のＳＲＡＭ）へアクセスする必要がなくなる。したがって、メモリコントローラ１０１１は、ＤＲＡＭ６１１に記憶されている参照フレーム１０２の中から次の参照画像データを読み出し、読み出した参照画像データを、ＳＲＡＭ１００３（第１のＳＲＡＭ）に記憶する。
【００４１】
以上のように、動きベクトル探索ポイント間の最大距離が、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数よりも大きく、動きベクトル探索範囲が広い場合には、図７に示す記憶フォーマットを選択する。すなわち、メモリコントローラ１０１１は、動きベクトルの探索範囲に対応する参照画像データのうち、上半分の参照画像データをＳＲＡＭ１００３に記憶し、下半分の参照画像データをＳＲＡＭ１００４に記憶する記憶フォーマットを選択する。このようにすることによって、ＳＲＡＭ１００３、１００４の記憶容量の増大を抑制しながら、複数のブロックマッチング演算器１００７、１００８における並列動作を従来よりも確実に実行することができる。更に、参照画像データの入れ替えも容易に行うことができる。
【００４２】
図９は、動きベクトル探索範囲が狭い場合のＳＲＡＭ１００３、１００４の記憶フォーマットの一例を示した図である。尚、図９では、図７と同様の表記を行っている。
本実施形態において、動きベクトル探索範囲が狭い場合とは、動きベクトル探索ポイント間の最大距離が、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数よりも小さい場合をいう。図８に示す例では、動きベクトル探索ポイント８０１ａ、８０１ｃ、８０１ｅと、動きベクトル探索ポイント８０２ｂ、８０２ｄ、８０２ｆとの距離が「５」であり、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数（＝１９）よりも小さい。
【００４３】
このような場合に、図７に示した記憶フォーマットを用いると、複数のブロックマッチング演算器１００７、１００８が同じＳＲＡＭからデータを読み出す可能性が高くなり、競合が生じ易くなる。
そこで、メモリコントローラ１０１１は、動きベクトル探索ポイント間の最大距離が、各ＳＲＡＭ１００３、１００４の記憶領域のアドレスの数以下の場合には、図８に示す記憶フォーマットを選択する。すなわち、メモリコントローラ１０１１は、動きベクトルの探索範囲に対応する参照画像データのうち、奇数ラインをＳＲＡＭ１００３に記憶し、偶数ラインをＳＲＡＭ１００４に記憶する記憶フォーマットを選択する。これにより、動きベクトルの探索範囲に対応する参照画像データのうち、奇数ラインの参照画像データがＳＲＡＭ１００３に記憶され、偶数ラインの参照画像データがＳＲＡＭ１００４に記憶される。このように、動きベクトルの探索範囲のライン単位毎に参照画像データを異なるＳＲＡＭにインターリーブして記憶することにより、動きベクトル探索ポイント８０１、８０２間の最大距離が閾値より小さい場合でも、前述したアクセスの競合を回避できる。
【００４４】
図１０は、図７に示した記憶フォーマットのＳＲＡＭ１００３、１００４へブロックマッチング演算器１００７、１００８がアクセスする様子の一例を概念的に示す図である。尚、図１０では、図８と同様の表記を行っている。
図９において、ブロックマッチング演算器１００７、１００８のうち、一方が奇数ラインを処理しているときに、他方が偶数ラインを処理しているときには、両方とも参照領域の上方からブロックマッチングを行う。一方、２つのブロックマッチング演算器１００７、１００８が共に奇数ラインを処理しているときには、一方を参照領域の上方から、他方を参照領域の下方から夫々ブロックマッチングを行う。これにより、２つのブロックマッチング演算器１００７、１００８は、ＳＲＡＭへのアクセスが競合することなく、ＳＲＡＭ１００３、１００４に高速にアクセスすることが可能になる。
【００４５】
このように、動きベクトルの探索範囲のライン単位毎に参照画像データを異なるＳＲＡＭにインターリーブして記憶する記憶フォーマットでは、各ＳＲＡＭ１００３、１００４が様々な参照画像データの複数の参照領域を含むことになる。したがって、何れかのＳＲＡＭに対する動きベクトルの探索が先に終了するということが生じにくく、参照画像データの入れ替えがし難い。しかしながら、本実施形態では、この記憶フォーマットを採用するのは、動きベクトルの探索範囲が狭く、動きベクトルが集中しやすい場合である。したがって、通常は、動きベクトルの探索範囲内の参照画素データを全てＳＲＡＭ１００３、１００４に記憶することができ、１つの動きベクトルが決定されるまでの間に、参照画素データの入れ替えが必要となる可能性は低い。
【００４６】
以上のように本実施形態では、動きベクトルの探索範囲が閾値より広い場合には、動きベクトルの探索範囲の上半分と下半分とを異なるＳＲＡＭ１００３、１００４に記憶する。一方、動きベクトルの探索範囲が閾値以下の場合には、動きベクトルの探索範囲のライン単位毎に参照画像データを異なるＳＲＡＭ１００３、１００４にインターリーブして記憶する。このように、動きベクトルの探索範囲と、ＳＲＡＭ１００３、１００４の予め定められた関係とに基づいて、ＳＲＡＭ１００３、１００４の記憶フォーマットを決定する。以上のようにすることによって、ＳＲＡＭ１００３、１００４の記憶容量の増大を抑制しながら、複数のブロックマッチング演算器１００７、１００８における並列動作を従来よりも確実に且つ高速に実行することができる。更に、動きベクトルの探索範囲が閾値より広い場合には、参照画像データの入れ替えの際の競合も発生しにくい。
また、閾値はＳＲＡＭの記憶容量に依存するし決定されるもので、前記閾値をＳＲＡＭの記憶容量範囲と読替えても同様である。つまり、動きベクトルの探索範囲内にある参照画像データが、ＳＲＡＭの容量より大きい場合と、小さい場合で記憶方法を変える事になる。
【００４７】
尚、本実施形態では、ブロックマッチング演算器が２つ、ＳＲＡＭが２つの場合を例に挙げて説明したが、ブロックマッチング演算器及びＳＲＡＭの数は、これらに限定されるものではない。
【００４８】
また、本実施形態では、動きベクトルの探索範囲が閾値よりも広い（大きい）場合に、動きベクトルの探索範囲の上半分の参照画像データをＳＲＡＭ１００３に記憶し、下半分の参照画像データをＳＲＡＭ１００４に記憶するようにした。しかしながら、動きベクトルの探索範囲をｍ行ｎ列の複数の記憶領域に分割し、分割した複数の記憶領域の参照画像データを異なるＳＲＡＭ１００３、１００４に個別に記憶するようにしていれば、必ずしもこのようにする必要はない。ここで、ｍ、ｎは、１以上の自然数であり、且つ少なくとも何れか一方は、２以上の値をとり得る。
更に、本実施形態では、動きベクトルの探索範囲が閾値以下の場合、動きベクトルの探索範囲の奇数ラインをＳＲＡＭ１００３に記憶し、偶数ラインをＳＲＡＭ１００４に記憶するようにした。しかしながら、動きベクトルの探索範囲のライン単位毎に参照画像データを異なるＳＲＡＭにインターリーブして記憶するようにしていれば、必ずしもこのようにする必要はない。ライン単位毎は、動き補償単位内であれば１ライン毎でも複数ライン毎でも同様である。
【００４９】
以上のように、ＳＲＡＭ１００３、１００４への参照画像データの記憶フォーマットは特定の動きベクトル探索アルゴリズムに依存するものではなく、動きベクトル探索アルゴリズムの変化に伴う探索範囲の変化や動きベクトル探索の並列度に柔軟に対応できる。
また、本実施形態では、動きベクトルの探索範囲が閾値よりも広い場合と、動きベクトルの探索範囲が閾値以下の場合とに場合分けして記憶フォーマットを決定するようにした。しかしながら、動きベクトルの探索範囲が閾値以上の場合と、動きベクトルの探索範囲が閾値より狭い（小さい）場合とに場合分けして記憶フォーマットを決定してもよい。
【００５０】
（本発明の他の実施形態）
前述した本発明の実施形態における動きベクトル探索装置を構成する各手段、並びに動きベクトル探索方法の各ステップは、コンピュータのＲＡＭやＲＯＭなどに記憶されたプログラムが動作することによって実現できる。このプログラム及び前記プログラムを記録したコンピュータ読み取り可能な記録媒体は本発明に含まれる。
【００５１】
また、本発明は、例えば、システム、装置、方法、プログラム若しくは記憶媒体等としての実施形態も可能であり、具体的には、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。
【００５２】
なお、本発明は、前述した実施形態の機能を実現するソフトウェアのプログラム（実施形態では図２及び図３に示した各ブロックが行う処理に対応したプログラム）を、システムあるいは装置に直接、あるいは遠隔から供給する。そして、そのシステムあるいは装置のコンピュータが前記供給されたプログラムコードを読み出して実行することによっても達成される場合を含む。
【００５３】
したがって、本発明の機能処理をコンピュータで実現するために、前記コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。
【００５４】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等の形態であってもよい。
【００５５】
プログラムを供給するための記録媒体としては、例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷなどがある。また、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ）などもある。
【００５６】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続する。そして、前記ホームページから本発明のコンピュータプログラムそのもの、若しくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードすることによっても供給できる。
【００５７】
また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明に含まれるものである。
【００５８】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布し、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせる。そして、ダウンロードした鍵情報を使用することにより暗号化されたプログラムを実行してコンピュータにインストールさせて実現することも可能である。
【００５９】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される。その他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部又は全部を行い、その処理によっても前述した実施形態の機能が実現され得る。
【００６０】
さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれる。その後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部又は全部を行い、その処理によっても前述した実施形態の機能が実現される。
【００６１】
なお、前述した各実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【図面の簡単な説明】
【００６２】
【図１】本発明の実施形態を示し、MPEG-2におけるフレーム間予測の方法の一例を概念的に示す図である。
【図２】本発明の実施形態を示し、フレーム間予測動画像符号化装置の構成の一例を示す図である。
【図３】本発明の実施形態を示し、動きベクトル探索器・参照画像生成器の構成の一例を詳細に示した図である。
【図４】本発明の実施形態を示し、ブロックマッチング演算器の基本動作の一例を示した図である。
【図５】本発明の実施形態を示し、H.264ビデオ動画像標準符号化方式におけるフレーム間予測の方法の一例を概念的に示す図である。
【図６】本発明の実施形態を示し、参照画像データを入れ替える方法の一例を概念的に示した図である。
【図７】本発明の実施形態を示し、動きベクトル探索範囲が広い場合のＳＲＡＭの記憶フォーマットの一例を示した図である。
【図８】本発明の実施形態を示し、図７に示した記憶フォーマットのＳＲＡＭへブロックマッチング演算器がアクセスする様子と、ＤＲＡＭからＳＲＡＭへ参照画像データを入れ替える様子との一例を概念的に示す図である。
【図９】本発明の実施形態を示し、動きベクトル探索範囲が狭い場合のＳＲＡＭの記憶フォーマットの一例を示した図である。
【図１０】本発明の実施形態を示し、図９に示した記憶フォーマットのＳＲＡＭへブロックマッチング演算器がアクセスする様子の一例を概念的に示す図である。
【符号の説明】
【００６３】
１０１  処理対象フレーム
１０１ａ  処理対象領域
１０２  参照フレーム
１０３、５０２  動きベクトル
１０４、５０１  動きベクトルの探索範囲
１０４ａ  参照領域
６０１  減算器
６０２  直交変換器
６０３  量子化器
６０４  スキャン処理器
６０５  エントロピー符号化器
６０６  逆量子化器
６０７  逆直交変換器
６０８  加算器
６０９  バスインターフェース
６１０  動きベクトル探索器・参照画像生成器
６１１  ＤＲＡＭ
１００３、１００４  ＳＲＡＭ
１００５、１００６、１００９  選択器
１００７、１００８  ブロックマッチング演算器
１０１０  動きベクトル探索器
１０１１  メモリコントローラ
【図１】
2008177925.tif 000003
【図２】
2008177925.tif 000004
【図３】
2008177925.tif 000005
【図４】
2008177925.tif 000006
【図５】
2008177925.tif 000007
【図６】
2008177925.tif 000008
【図７】
2008177925.tif 000009
【図８】
2008177925.tif 000010
【図９】
2008177925.tif 000011
【図１０】
2008177925.tif 000012