(57)【要約】【課題】制御論理が簡単で少ゲート数で構成可能なＳＡＤ演算器の提供。【解決手段】注目画像，参照画像の２Ｎ×２Ｎ領域を、全組み合わせ（ｎ，ｍ）に対し２ｎ×２ｍに等分割したＭＢにつきＳＡＤを計算するＳＡＤ演算器で、２ｐ×２ｐ，２ｐ×２ｐ＋１（ｐ＝２〜Ｎ−１）のＭＢのＳＡＤを記憶するレジスタ、加算器、及びコントローラを備え、コントローラは、２ｐ×２ｐレジスタから隣接するＭＢのＳＡＤを読出し加算し２ｐ＋１×２ｐＳＡＤを算出する縦長ブロック演算手段、２ｐ×２ｐレジスタから隣接するＭＢのＳＡＤを読出し加算し２ｐ×２ｐ＋１ＳＡＤを算出し２ｐ×２ｐ＋１レジスタに格納する横長ブロック演算手段、及び２ｐ×２ｐ＋１レジスタから相隣接するＭＢのＳＡＤを読出し加算し２ｐ＋１×２ｐ＋１ＳＡＤを算出し２ｐ＋１×２ｐ＋１レジスタに格納する正方ブロック演算手段を備える。各ブロック演算手段は木構造に接続する。【選択図】図２
2007281977.tif 000002
【特許請求の範囲】
【請求項１】
注目画像及び参照画像における縦横のサイズが２Ｎ×２Ｎ（Ｎ≧４）の比較画素領域を、ｎ∈｛２，３，…，Ｎ｝及びｍ∈｛２，３，…，Ｎ｝のすべての組み合わせ（ｎ，ｍ）に対して、２ｎ×２ｍのブロック・サイズに等分割して得られるマクロブロック（以下「ＭＢ」という。）について、それぞれ差分絶対値和（以下「ＳＡＤ」という。）を計算するＳＡＤ演算器であって、
サイズ２ｐ×２ｐ（ｐ＝２，３，…，Ｎ−１）のＭＢのＳＡＤを記憶する複数個のレジスタ、及びサイズ２ｐ×２ｐ＋１のＭＢのＳＡＤを記憶する複数個のレジスタと、
注目画像及び参照画像の前記比較画素領域からラスタ走査順に入力される２つの画素値の差分絶対値を計算する差分絶対値演算器と、
前記差分絶対値演算器が出力する差分絶対値を、最小のブロック・サイズのＭＢごとに累算し、各ＭＢに対応するレジスタに保存する基本ブロック演算手段と、
サイズ２ｐ×２ｐの水平方向に隣接する２つのＭＢのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、サイズ２ｐ＋１×２ｐのＭＢのＳＡＤを算出する横長ブロック演算手段と、
サイズ２ｐ×２ｐの垂直方向に隣接する２つのＭＢのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、サイズ２ｐ×２ｐ＋１のＭＢのＳＡＤを算出し出力するとともに、対応するレジスタがあれば、サイズ２ｐ×２ｐ＋１のＭＢに対するレジスタに保存する縦長ブロック演算手段と、
サイズ２ｐ＋１×２ｐの垂直方向に隣接する２つのＭＢのＳＡＤ、又はサイズ２ｐ＋１×２ｐの水平方向に隣接する２つのＭＢのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、サイズ２ｐ＋１×２ｐ＋１のＭＢのＳＡＤを算出し出力するとともに、対応するレジスタがあれば、サイズ２ｐ＋１×２ｐ＋１のＭＢに対するレジスタに保存する正方ブロック演算手段と、を備え、
前記基本ブロック演算手段、前記各横長ブロック演算手段、前記各縦長ブロック演算手段、及び前記各正方ブロック演算手段は、加算器木を構成するように接続されていることを特徴とするＳＡＤ演算器。
【請求項２】
各サイズのＭＤに対応してそれぞれ専用に設けられ、演算が終了したＳＡＤ値をＳＡＤバスに出力する３Ｎ−５個のＳＡＤインタフェースを備えていることを特徴とする請求項１記載のＳＡＤ演算器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像圧縮の可変ブロック・サイズ動き予測（variable block size motion estimation: ＶＢＳＭＥ）のための画素ブロックの差分絶対値和（sum of differences: SAD）を演算するＳＡＤ演算器に関する。
【背景技術】
【０００２】
近年、Ｈ．２６４／ＡＶＣ（符号化効率の向上に重点を置いた新ビデオ符号化規格）が、ITU-T VCEGとＩＳＯ／ＩＥＣ  ＭＰＥＧの合同ビデオチーム（Joint Video Team : JVT）により制定されている。Ｈ．２６４／ＡＶＣの目的は、動画像の圧縮効率を高め、種々のアプリケーションのための、ネットワークとの親和性のよいビデオ表現を提供することにある。従来のビデオ規格と比較すると、Ｈ．２６４／ＡＶＣは、異なるビット転送速度とビデオ解像度で、最大で５０％の符号化利得を得ることができる。これは、主に、可変ブロック・サイズ動き補償（variable block sizes motion compensation）、１／４画素精度動き補償（quarter sample accurate motion compensation）、複数参照画面動き補償（multiple reference picture motion compensation）、重み付け予測（weighted prediction）、ループ内デブロッキング・フィルタ（in-the-loop deblocking filtering）などの、Ｈ．２６４／ＡＶＣに採用された多くの新しい技術によるものである（非特許文献１参照）。
【０００３】
Ｈ．２６４／ＡＶＣにおいては、動き推定（motion estimation：ＭＥ）では、図１に示したような、4×4、4×8、8×4、8×8、8×16、16×8、及び16×16を含む異なるブロック上で行われる。１つのマクロブロック（macroblock：ＭＢ）に対して、すべてのブロック・サイズが処理され、Ｒ−Ｄ(Rate-Distortion)コストが最もよいブロック・モードが選択される。この処理は可変ブロック・サイズ動き補償（ＶＢＳＭＥ：Variable block size motion estimation）と呼ばれる。
【０００４】
固定ブロック・サイズを用いた従来のＭＢ処理と比較すると、ＶＢＳＭＥは、より高い圧縮率とよりよい画質が得られるが、動き推定（ＭＥ）ユニットに大きな負荷をかけることとなり、従来のＭＥアーキテクチャとの互換性もない。従って、ＶＢＳＭＥに対応した新たなＭＥアーキテクチャの開発が必要とされている。
【０００５】
ＭＥアルゴリズムは、映像符号化の過程においては最も多くの計算量を要する部分である。従って、その計算の複雑さを緩和するために、従来から多くの高速のＭＥアルゴリズムが提案されている。
【０００６】
しかしながら、完全探索ブロックマッチング・アルゴリズム（full search block matching algorithm ：FSBM）は、その安定した性能と規則的なワークフローにより、現在もなお広く使用されている。Ｈ．２６４／ＡＶＣにおいても、いくつかのFSBM VBSMEアーキテクチャが提案されている（非特許文献２〜５参照）。これらすべてのアーキテクチャにおいては、計算の複雑さを緩和するために、部分データの再利用の方法が採られている。すなわち、より小さいサブブロックのSADを保存しておき、より大きなブロックのSADはより小さなサブブロックのSADを累算することにより算出する方法である。
【０００７】
非特許文献８に記載されたアーキテクチャの基礎として、非特許文献２において効率的な2-D VBSMEアーキテクチャが提案された。これは、1-Dデータ・ブロードキャスティング（1-D data broadcasting）と1-D部分的SADの再利用の方法を採用している。パイプライン待ち時間を考慮しなければ、このアーキテクチャでは各クロック・サイクルにおいて１つの検索位置におけるＶＢＳＭＥが完了するため、高画質ビデオ処理に適した方法であるといえる。しかしながら、この処理を行うためには、２５６個のプロセッサ・エレメント（ＰＥ：processor element）を並列に動作させる必要がある。そのうえ、探索領域データ・メモリも３２分割されるため、ハードウェア・コストと消費電力が極めて大きくなるという問題がある。
【０００８】
その他の２−Ｄデザインとしては、非特許文献２のものと同じ処理能力を持つものが、非特許文献３に提案されている。このアーキテクチャによれば、すべてのＰＥの中に、先行読込レジスタ（preload register）と検索データバッファ（search data buffer）を備えたことにより、探索領域メモリの分割を１６まで抑えることができる。しかしながら、このアプローチは、十分なハードウェア的な余裕と複雑なメモリ管理とを必要とする。
【０００９】
非特許文献４においては、木構造ＶＢＳＭＥアーキテクチャ（tree structure VBSME architecture）が提案されている。これは、非特許文献７のツリーＭＥアーキテクチャ（tree ME architecture）を基礎とするものである。このアーキテクチャでは、余分なＶＢＳオーバーヘッドを完全に回避して、非特許文献２，３に記載のものと同程度のスループットを実現している。このアーキテクチャにおいては、すべての注目画素（current pixel）が各ＰＥに保存される。各サイクルにおいては、参照画素（reference pixel）が同時に入れられ、すべてのひずみが同時に、計算される。１６個の４×４ SADを生成するために、１６個の２−Ｄ加算器が使用される。そして、他のより大きなSADを計算するのに、１個の加算器木（adder tree）が使用される。
【００１０】
一方、携帯機器に対しては、低解像度のビデオが処理対象とされ、計算負荷はそれほど大きくはない。むしろ、この種のデバイスにおいては、ハードウェア・コストと消費電力の低減ほうが厳しく要求される。従って、この種のアプリケーションには、1-D MEアーキテクチャがより適している。
【００１１】
非特許文献５においては、参照データ・ブロードキャスティング（reference data broadcasting）（非特許文献８参照）を基礎とする1-D VBSMEアーキテクチャが提案されている。このアーキテクチャにおいては、各ＰＥに対して、４×４ SADが保存され、より大きなブロックのSADは、より小さなブロックのSADを累算することにより演算され、共通のSADバスに転送される。2-Dデザインと比較すると、このアーキテクチャはより柔軟性があり、２つの分割しか必要としないため有利である。
【００１２】
図９に、非特許文献５に記載の1-D VBSMEアーキテクチャの全体構成を示す。
【００１３】
図９の1-D VBSMEアーキテクチャにおいては、注目ＭＢに対して１６個の参照ＭＢのSADの演算が行われる。各参照ＭＢのSADの演算は、１６個のＰＥ（ＰＥ１〜ＰＥ１５）においてそれぞれ行われる。注目ＭＢの画素値はラスタ走査順に走査され、入力ラインＣから入力される。また、参照ＭＢの画素値も、ラスタ走査順に走査され、入力ラインＲ０，Ｒ１から入力される。
【００１４】
入力ラインＣには遅延器Ｄが設けられており、１個の遅延器Ｄでは１クロック・サイクルの伝達遅延がある。従って、ＰＥ１〜ＰＥ１５には１クロック・サイクルずつずれたタイミングで注目ＭＤの画素値が入力され、１６個の参照ＭＢに対してSADが並列に演算される。また、入力ラインＲ０，Ｒ１から入力される参照ＭＢの画素値は、マルチプレクサＭＵＸ１〜ＭＵＸ１５で何れかが選択され、ＰＥ１〜ＰＥ１５へ入力される。この選択は、Controlラインから入力される制御信号により行われる。
【００１５】
尚、参照ＭＢに対する入力ラインが２本設けられているのは、ラスタ走査の折り返しのポイントが、ＰＥ１〜ＰＥ１５で１画素ずつずれているため、２本の水平走査線分のデータが必要となるためである。
【００１６】
ＰＥ１〜ＰＥ１５において演算されたSADは、各ＰＥに対して専用に設けられたSADバス（SAD BUD0〜SAD BUS12）に出力される。
【００１７】
ここで、SADは次式（１）により定義される。
【００１８】
【数１】
2007281977.tif 000003
【００１９】
ここで、(i, j)は注目ＭＢに対する参照ＭＢの相対位置座標、SAD(i, j)は注目ＭＢに対する参照ＭＢ(i, j)のSAD、C(k, l)及びR(i+k, j+l)はそれぞれ注目ＭＢ，参照ＭＢ内の画素の画素値、（Ｍ，Ｎ）は注目ＭＢ及び参照ＭＢのサイズを表す。SAD(i, j)に対する動きベクトル（ＭＶ：motion vector）は(i, j)である。
【００２０】
１つのＭＢは１６×１６画素で構成される。ＢＶＳＭＥでは、このＭＢを4×4、4×8、8×4、8×8、8×16、16×8、及び16×16画素の部分ＭＢに分割し、各部分ＭＢに対してSADの演算を行う。以下では、4×4画素の部分ＭＢを「４×４ブロック」、4×8画素の部分ＭＢを「４×８ブロック」などと呼ぶことにする。
【００２１】
VBSMEにおいては、各部分ＭＢに対して、ＭＶ(i, j)を変化させてＳＡＤを計算し、ＳＡＤが最小となる部分ＭＢのＭＶを探索する。1-D VBSMEアーキテクチャでは、水平方向にずれたＮ個の参照ＭＢに対して並列に、各部分ＭＢのＳＡＤの演算を行う。
【００２２】
１つのＭＢを１６個の４×４ブロックに分割した場合、図１０に示したように、各４×４ブロックをｂ０〜ｂ１５と記す。これらの４×４ブロックを基本ブロック（base block）と呼ぶ。各基本ブロックは、１６個の画素Ｐ０〜Ｐ１５から構成されている。
【００２３】
また、基本ブロックｂ０〜ｂ１５のＳＡＤ値をSAD(b0)〜SAD(b15)と記す。さらに、基本ブロックｂ０，ｂ１で構成される８×４ブロックのＳＡＤ値をSAD(b0, b1)，基本ブロックｂ０，ｂ４で構成される４×８ブロックのＳＡＤ値をSAD(b0, b4)のように記すことにする。
【００２４】
図１１に、図９の各ＰＥの構成を示す。注目画素C(k, l)及び参照画素R(i+k, j+l)は、絶対値差演算器１０１に入力される。絶対値差演算器１０１は、絶対値差（ＡＤ：absolute difference）を計算し、絶対値差レジスタ１０２に保存する。
【００２５】
絶対値差レジスタ１０２に保存されたＡＤ値は、加算器１０３において、ＳＡＤレジスタ１０５−０〜１０５−７の何れかに保存されたＳＡＤ値と加算される。最初はＳＡＤレジスタ１０５−０〜１０５−７のＳＡＤ値は０であり、ＡＤ値は０と加算される。
【００２６】
加算器１０３の出力は、デマルチプレクサ１０４において振り分けられて、ＳＡＤレジスタ１０５−０〜１０５−７の何れかに保存される。ここで、８個のＳＡＤレジスタ１０５−０〜１０５−７には、それぞれ、基本ブロックｂ０〜ｂ７（又はｂ８〜ｂ１５）のＳＡＤ値が保存される。
【００２７】
ＳＡＤレジスタ１０５−０〜１０５−７の出力は、第１の内部バス１０６に接続されている。また、内部バス１０６には、マルチプレクサマルチプレクサ１０７，マルチプレクサ１０８，マルチプレクサ１０９が接続されている。マルチプレクサ１０９の出力は、加算器１０３の入力側にフィードバックされている。これにより、各基本ブロックのＳＡＤの累算が可能となる。
【００２８】
例えば、ＰＥ０について考えると、クロック・サイクル０において、加算器１０２にはＡＤ値|C(0,0)-R(0,0)|が入力される。加算器１０３は、この値と０を加算し、デマルチプレクサ１０４に出力する。この画素は、基本ブロックｂ０に属するので、デマルチプレクサ１０４はこの値をＳＡＤレジスタ１０５−０に保存する。保存された値（SAD(b0)）は、内部バス１０６に出力される。
【００２９】
クロック・サイクル１において、加算器１０２にはＡＤ値|C(1,0)-R(1,0)|が入力される。この画素は、基本ブロックｂ０に属するので、マルチプレクサ１０９は、内部バス１０６に出力されたＳＡＤレジスタ１０５−０の出力するSAD(b0)を選択し、加算器１０３に入力する。加算器１０３は、ＡＤ値|C(1,0)-R(1,0)|とSAD(b0)を加算し、デマルチプレクサ１０４に出力する。この画素は、基本ブロックｂ０に属するので、デマルチプレクサ１０４はこの値をＳＡＤレジスタ１０５−０に保存する。保存された値（SAD(b0)）は、内部バス１０６に出力される。
【００３０】
以下同様に、クロック・サイクル２，３についても実行され、SAD(b0)が累算される。
【００３１】
クロック・サイクル４において、加算器１０２にはＡＤ値|C(4,0)-R(4,0)|が入力される。この画素は基本ブロックｂ１に属するので、加算器１０３は、この値と０を加算し、デマルチプレクサ１０４に出力する。デマルチプレクサ１０４はこの値をＳＡＤレジスタ１０５−１に保存する。保存された値（SAD(b1)）は、内部バス１０６に出力される。以下、クロック・サイクル５〜７において、同様に基本ブロックｂ１についてのSAD(b1)の累算が行われる。
【００３２】
クロック・サイクル８〜１１，１２〜１５においては、それぞれ、基本ブロックｂ２，ｂ３のＳＡＤ値の累算が行われる。
【００３３】
クロック・サイクル１６においては、加算器１０２にはＡＤ値|C(0,1)-R(0,1)|が入力される。この画素は、基本ブロックｂ０に属するので、マルチプレクサ１０９は、SAD(b0)を選択し、加算器１０３に入力する。加算器１０３は、ＡＤ値|C(0,1)-R(0,1)|とSAD(b0)を加算し、デマルチプレクサ１０４に出力する。デマルチプレクサ１０４はこの値をＳＡＤレジスタ１０５−０に保存する。以下同様である。
【００３４】
以上のようにして、ＳＡＤ値の累算が続けて実行され、クロック・サイクル５１において基本ブロックｂ０のＳＡＤ値の累算が終わり、SAD(b0)が使用可能な状態となる。このとき、マルチプレクサ１０７はSAD(b0)を選択し、マルチプレクサ１１０を通して加算器１１２に入力する。また、マルチプレクサ１１１は０を選択して加算器１１２に入力する。加算器１１２は、SAD(b0)を０と加算して、デマルチプレクサ１１３に出力する。デマルチプレクサ１１３は、SAD(b0)を４１個のＳＡＤレジスタ１１４−０〜１１４−４０の何れか（例えば、１１４−０）に振り分けて保存する。
【００３５】
また、クロック・サイクル５５において基本ブロックｂ１のＳＡＤ値の累算が終わり、SAD(b1)が使用可能な状態となる。この場合も、同様にして、SAD(b1)はＳＡＤレジスタ１１４−１に保存される。
【００３６】
クロック・サイクル５６において、マルチプレクサ１１０はSAD(b0)を選択し、マルチプレクサ１１１はSAD(b1)を選択して、加算器１１２に入力する。加算器１１２は、SAD(b0)とSAD(b1)を加算してSAD(b0, b1)を算出する。この値は、デマルチプレクサ１１２により、ＳＡＤレジスタ１１４−０〜１１４−４０の何れか（例えば、１１４−１６）に振り分けて保存される。
【００３７】
このようにして、基本ブロックの組み合わせからなる高次の部分ＭＢは、基本ブロックの先に演算されたＳＡＤを使用して計算される。
【００３８】
図１２に、各クロックにおけるＳＡＤ演算のスケジューリングを示す。このアーキテクチャにおいては、２６２クロック・サイクルで、すべての部分ＭＢのＳＡＤ値の計算が完了する。
【特許文献１】特表２０００−５１１３６６号公報
【特許文献２】特開平10-269197号公報
【特許文献３】特開平6-225287号公報
【特許文献４】特開平6-141304号公報
【特許文献５】特開平5-266056号公報
【特許文献６】特開平5-268593号公報
【非特許文献１】T. Wiegand, G. Sullivan, A. Luthra, "Draft ITU-T recommendation and final draft international standard of joint video specification (ITU-T Rec. H.264 - ISO/IEC 14496-10 AVC)", 2003.
【非特許文献２】Y. W. Huang, T. C. Wang, B. Y. Hsieh, L. G. Chen, "Hardware architecture design for variable block size motion estimation in MPEG-4 AVC/JVT/ITU-T H.264" , IEEE International Symposium on Circuits and Systems (ISCAS'03), Vol. 2, pp. 796-799, 2003.
【非特許文献３】M. Kim, I. Hwang, S. Chae, "A Fast VLSI Architecture for Full-Search Variable Block Size Motion Estimation in MPEG-4 AVC/H.264", ACM/IEEE llth Asia and South Pacific Design Automation Conference (ASP-DAC'05), pp. 631-634, 2005.
【非特許文献４】Y. W. Huang, T. C. Chen, C. H. Tsai, C. Y. Chen, T. W. Chen, C. S, Chen, C. F. Shen, S. Y. Ma, T. C. Wang, B. Y. Hsieh, H. C. Fang, L. G. Chen, "A 1.3TOPS H.264/AVC single-chip encoder for HDTV applications", IEEE International Solid-State Circuits Conference (ISSCC'05), pp. 128-129, 2005.
【非特許文献５】S. Y. Yap, J. V. McCanny, "A VLSI architecture for variable block size video motion estimation", IEEE Transactions on Circuits and Systems-II: Express Briefs, Vol. 51, No. 7, pp. 384-389, 2004.
【非特許文献６】L. D. Vos, M. Stegherr, "Parameterizable VLSI architectures for the full-search block-matching algorithm" , IEEE Transactions on Circuits and Systems, Vol. 36, No. 10, pp. 1309-1316, 1989.
【非特許文献７】J. S. Jehng, L. G. Chen, T. D. Chiueh, "An Efficient and Simple VLSI Tree Architecture for Motion Estimation Algorithms" , IEEE Transactions on Signal Processing, Vol. 41, No. 2, pp. 889-900, 1993.
【非特許文献８】K. M. Yang, M. T. Sun, L. Wu, "A family of VLSI designs for the motion compensation block-matching algorithm", IEEE Transactions on Circuits and Systems, Vol. 36, No. 10, pp. 1317-1325, 1989.
【発明の開示】
【発明が解決しようとする課題】
【００３９】
しかしながら、上記非特許文献５に記載の従来の1-D VBSMEアーキテクチャでは、部分SADレジスタを待避（保存）するために、図１２に示したように、各PEは複雑な制御ロジックと不規則なワークフローが必要となり、ハードウェアの実装効率と利用効率が低下するという問題がある。
【００４０】
例えば、クロック・サイクル５１において、基本ブロックｂ０のＳＡＤ値SAD(b0)の累算が終了すると、SAD(b0)を下部のＳＡＤレジスタ１１４−０に転送するとともに、次の基本ブロックｂ８の累算を行うためにＳＡＤレジスタ１０５−０を初期するといった動作が必要となる。また、下位の部分ＭＢを組み合わせてできる上位の部分ＭＢのＳＡＤの計算を行うタイミングが規則的ではなく、タイミング制御が複雑である。
【００４１】
そこで、本発明の目的は、各部分ＭＢの演算のワークフローが規則的となり、単純な制御ロジックによってＳＡＤの演算制御を行うことが可能で、ハードウェアの実装効率と利用効率の高いＳＡＤ演算器を提供することにある。
【課題を解決するための手段】
【００４２】
本発明に係るＳＡＤ演算器の第１の構成は、注目画像及び参照画像における縦横のサイズが２Ｎ×２Ｎ（Ｎ≧４）の比較画素領域を、ｎ∈｛２，３，…，Ｎ｝及びｍ∈｛２，３，…，Ｎ｝のすべての組み合わせ（ｎ，ｍ）に対して、２ｎ×２ｍのブロック・サイズに等分割して得られるマクロブロック（以下「ＭＢ」という。）について、それぞれ差分絶対値和（以下「ＳＡＤ」という。）を計算するＳＡＤ演算器であって、
サイズ２ｐ×２ｐ（ｐ＝２，３，…，Ｎ−１）のＭＢのＳＡＤを記憶する複数個のレジスタ、及びサイズ２ｐ×２ｐ＋１のＭＢのＳＡＤを記憶する複数個のレジスタと、
注目画像及び参照画像の前記比較画素領域からラスタ走査順に入力される２つの画素値の差分絶対値を計算する差分絶対値演算器と、
前記差分絶対値演算器が出力する差分絶対値を、最小のブロック・サイズのＭＢごとに累算し、各ＭＢに対応するレジスタに保存する基本ブロック演算手段と、
サイズ２ｐ×２ｐの水平方向に隣接する２つのＭＢのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、サイズ２ｐ＋１×２ｐのＭＢのＳＡＤを算出する横長ブロック演算手段と、
サイズ２ｐ×２ｐの垂直方向に隣接する２つのＭＢのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、サイズ２ｐ×２ｐ＋１のＭＢのＳＡＤを算出し出力するとともに、対応するレジスタがあれば、サイズ２ｐ×２ｐ＋１のＭＢに対するレジスタに保存する縦長ブロック演算手段と、
サイズ２ｐ＋１×２ｐの垂直方向に隣接する２つのＭＢのＳＡＤ、又はサイズ２ｐ＋１×２ｐの水平方向に隣接する２つのＭＢのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、サイズ２ｐ＋１×２ｐ＋１のＭＢのＳＡＤを算出し出力するとともに、対応するレジスタがあれば、サイズ２ｐ＋１×２ｐ＋１のＭＢに対するレジスタに保存する正方ブロック演算手段と、を備え、
前記基本ブロック演算手段、前記各横長ブロック演算手段、前記各縦長ブロック演算手段、及び前記各正方ブロック演算手段は、加算器木を構成するように接続されていることを特徴とする。
【００４３】
このように、基本ブロック演算手段、各横長ブロック演算手段、各縦長ブロック演算手段、及び各正方ブロック演算手段を、加算器木を構成するように接続することにより、異なるブロック・モードのＳＡＤは同時に計算することができ、規則的なワークフローとすることができる。このように規則的なワークフローとすることで、最適なＶＬＳＩ実装が可能となる。
【００４４】
ここで、サイズ２ｐ×２ｐのＭＢのＳＡＤを記憶するレジスタの数、及びサイズ２ｐ×２ｐ＋１のＭＢのＳＡＤを記憶するレジスタの数は特に限定しないが、両者ともＮ／２ｐ個あれば十分である。
【００４５】
また、「加算器木を構成するように接続」とは、２ｐ×２ｑのＭＢに対するブロック演算手段（基本ブロック演算手段、横長ブロック演算手段、縦長ブロック演算手段、又は正方ブロック演算手段）の出力が、２ｐ＋１×２ｑ＋１又は２ｐ×２ｑ＋１の上位のＭＢに対するブロック演算手段の入力となるように、木（tree）構造状に連結されていることをいう。
【００４６】
本発明に係るＳＡＤ演算器の第２の構成は、前記第１の構成において、各サイズのＭＤに対応してそれぞれ専用に設けられ、演算が終了したＳＡＤ値をＳＡＤバスに出力する３Ｎ−５個のＳＡＤインタフェースを備えていることを特徴とする。
【００４７】
これにより、ＳＡＤ出力インタフェースを共通するためのＰＥ内でのマルチプレクサを使用する必要がなく、その結果、ハードウェア・コストと演算時間を削減することができる。
【発明の効果】
【００４８】
以上のように、本発明によれば、各部分ＭＢの演算のワークフローが規則的となり、単純な制御ロジックによってＳＡＤの演算制御を行うことが可能で、ハードウェアの実装効率と利用効率の高いＳＡＤ演算器を提供することができる。
【発明を実施するための最良の形態】
【００４９】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００５０】
〔１〕可変ブロック・サイズ動き推定器全体のアーキテクチャ
図２は、本発明の実施例１に係る可変ブロック・サイズ動き推定器（variable block size motion estimator）１の構成を表すブロック図である。本実施例１の可変ブロック・サイズ動き推定器１は、１−Ｄ ＶＢＳＭＥアルゴリズム（非特許文献８参照）の演算を実行するものである。ここでは、説明をわかりやすくするために、一例として、動きベクトルの探索範囲が［−８，＋７］の場合について説明するが、本発明において探索範囲はこの範囲に限定されるものではない。
【００５１】
動きベクトルの探索範囲の位置が１６個なので、可変ブロック・サイズ動き推定器１は、各探索位置に対応して１６個のプロセッサ・エレメントＰＥ０〜ＰＥ１５を備えている。プロセッサ・エレメントの個数は、探索範囲に合わせて決定される。また、可変ブロック・サイズ動き推定器１は、位置入力バスPos. BUS、注目画素入力バスCUR BUS、参照画素入力バスREF BUS0、参照画素入力バスREF BUS1、及びＳＡＤバスネットワーク２を備えている。
【００５２】
位置入力バスPos. BUSは、参照画素の位置情報が入力されるバスである。注目画素入力バスCUR BUSは、注目画素の画素値が入力されるバスである。また、参照画素入力バスREF BUS0，REF BUS1は、参照画素の画素値が入力されるバスである。ＳＡＤバスネットワーク２は、各ＰＥで計算されるＳＡＤを転送するためのバスである。
【００５３】
ここで、本実施例においては、注目ＭＢ及び参照ＭＢのサイズは２４×２４とし、各ＰＥは、図１に示したような部分ＭＢについてそれぞれＳＡＤの演算を行う。即ち、各ＰＥは、図３に示したような４１個の部分ＭＢについてのＳＡＤの演算を行う。また、注目ＭＢ及び参照ＭＢの画素は、図４に示したようなラスタ走査順に走査されて、１画素ずつその画素値が注目画素入力バスCUR BUS及び参照画素入力バスREF BUS0，REF BUS1に入力される。尚、参照画素入力バスREF BUS0，REF BUS1については、１行目の参照画素は参照画素入力バスREF BUS0に順次入力される。１６クロック・サイクルで１行目の参照画素が１６画素入力されると、次のクロック・サイクルからは、１行目の参照画素が参照画素入力バスREF BUS0に続けて順次入力されるとともに、２行目の参照画素が参照画素入力バスREF BUS1に順次入力される。さらに、３２クロック・サイクルで２行目の参照画素が１６画素入力されると、次のクロック・サイクルからは、２行目の参照画素が参照画素入力バスREF BUS1に続けて順次入力されるとともに、３行目の参照画素が参照画素入力バスREF BUS0に順次入力される。以下同様に、１６クロック・サイクルごとにバスを交互に切り替えながら、参照画素は入力される。これは、各プロセッサ・エレメントＰＥ０〜ＰＥ１５で参照する参照ＭＢの位置が１画素分ずつずれているため、各プロセッサ・エレメントで必要な参照画素の位置が異なるためである。
【００５４】
さらに、可変ブロック・サイズ動き推定器１は、各プロセッサ・エレメントＰＥ０〜ＰＥ１５に対応して、位置データ遅延器Ｄｐ０〜Ｄｐ１５、注目画素データ遅延器Ｄｃ０〜Ｄｃ１５、マルチプレクサＭＵＸ０〜ＭＵＸ１５、及び、最小ＳＡＤ演算器ＭＩＮ０〜ＭＩＮ１５を備えている。
【００５５】
位置データ遅延器Ｄｐ０〜Ｄｐ１５及び注目画素データ遅延器Ｄｃ０〜Ｄｃ１５は、それぞれ、位置入力バスPos. BUS及び注目画素入力バスCUR BUSに入力される位置データ及び注目画素の画素値を１クロック・サイクルだけ遅延させてバスの後段に出力する。従って、ＰＥ１〜ＰＥ１５には、位置データ及び注目画素の画素値が１クロック・サイクルずつ遅れてそれぞれ入力される。一方、参照画素の画素値は、ＰＥ１〜ＰＥ１５に同時に共通に入力される。これにより、ＰＥ１〜ＰＥ１５は、１画素ずつ参照ＭＢをずらしてＳＡＤが計算される。
【００５６】
マルチプレクサＭＵＸ０〜ＭＵＸ１５は、それぞれ、ＰＥ０〜ＰＥ１５において使用する参照画素を参照画素入力バスREF BUS0又は参照画素入力バスREF BUS1から選択する。図５に、各クロック・サイクルにおいて参照画素入力バスREF BUS0，REF BUS1に出力される参照画素の座標値とマルチプレクサＭＵＸ０〜ＭＵＸ１５の選択状態の関係を示す。
【００５７】
最小ＳＡＤ演算器ＭＩＮ０〜ＭＩＮ１５は、それぞれ、ＰＥ０〜ＰＥ１５において計算される各部分ＭＢのＳＡＤの最小値を選択し、その最小のＳＡＤ値とそれに対応する部分ＭＢのインデックス（動きベクトル）を出力する。
【００５８】
この可変ブロック・サイズ動き推定器１において、各ＰＥに対して、それぞれのクロック・サイクルにおいて、注目ＭＢデータと参照ＭＢデータとが与えられる。各ＰＥは、絶対値差（ＡＤ：absolute difference）を計算し、算出されたＡＤは、与えられた画素の位置に従って、先に計算された部分ＭＢのＳＡＤ値に加えられ、対応するＳＡＤレジスタに保存される。１つのＰＥの中に、７種類のブロック・サイズに対応したブロック・モードのための７つのＳＡＤインタフェースがある（詳細は後述する）。それぞれのブロック・モードごとに独自のＳＡＤインタフェースを持つため、ＳＡＤ出力インタフェースを共通するためのＰＥ内でのマルチプレクサ（図１１のマルチプレクサ１１７参照）を使用する必要がなく、その結果、ハードウェア・コストと演算時間を削減することができる。
【００５９】
図２に示すように、各ＰＥにより生成されるＳＡＤは、最小ＳＡＤ演算器ＭＩＮ０〜ＭＩＮ１５内のレジスタに保存された最小ＳＡＤと比較するために、ＳＡＤバスネットワーク２にスケジュールされて転送される。図３に示すように、１つのＭＢに対して、４１個の部分ＭＤ（１６×１６ＭＤも１つの部分ＭＤとみなす。）がある。従って、最小ＳＡＤとそれに対する動きベクトル（ＭＶ：motion vector）を保存するために、全部で４１個のＳＡＤ及びそれに関連するＭＶを保存するレジスタが存在する。
【００６０】
直感的には、それぞれの最小ＳＡＤレジスタに対応して、４１個のコンパレータが必要であることが分かる。しかしながら、1-D MEアーキテクチャにおいては、異なるＰＥにおける同じ部分ＭＢのＳＡＤは、異なるクロック・サイクルにおいて生成される。このように、時間を多重化することにより、異なるＰＥで生成されたＳＡＤはスケジュールされ、比較される。そのため、全部で１６個のコンパレータがあればよいことになる。
【００６１】
１６個のＰＥが並列に動作することで、１つの探索位置における１回の完全探索ＶＢＳＭＥを１６クロック・サイクルで終わらせることができる。従って、１６×１６の探索範囲で、ＶＢＳＭＥのプロセスは４０９６クロック・サイクルで終わらせることができる。ＭＥ処理の後、４１個の最小ＳＡＤと、それに関連するＭＶのすべてが、対応するレジスタに保存され、利用可能となる。
【００６２】
〔２〕プロセッサ・エレメント（ＰＥ）のアーキテクチャ
次に、図２における各ＰＥについて説明する。本実施例１の可変ブロック・サイズ動き推定器１においては、各ＰＥ内において加算器木（adder tree）を構成する。従って、異なるブロック・モードのＳＡＤは同時に計算することができ、規則的なワークフローとすることができる。
【００６３】
1-D MEアーキテクチャにおいては、１つのＰＥは１つの検索位置を担当し、その結果生成されるＳＡＤは適切なタイミングでＳＡＤバスネットワーク２に転送される。従って、ＰＥを構成するにあたっては、次の２つの問題点を解決する必要がある。
【００６４】
（１）１つのＰＥ内において部分ＳＡＤレジスタを選択する方法：  ここで最も問題となるのは、部分ＳＡＤレジスタの数と演算時間とのトレードオフを最適化することである。
【００６５】
（２）計算後に得られるＳＡＤ値をＳＡＤバスネットワーク２に転送する方法。
【００６６】
以上の点を考慮して、本実施例においては、ＰＥとして図６に示す構成のＳＡＤ演算器１０を採用する。
【００６７】
図６において、ＳＡＤ演算器１０は、差分絶対値演算器１１、４×４基本ブロック演算器１２、８×４横長ブロック演算器１３、４×８縦長ブロック演算器１４、８×８正方ブロック演算器１５、１６×８横長ブロック演算器１６、８×１６縦長ブロック演算器１７、１６×１６正方ブロック演算器１８、４×４ＳＡＤインタフェース１９、８×４ＳＡＤインタフェース２０、４×８ＳＡＤインタフェース２１、８×８ＳＡＤインタフェース２２、１６×８ＳＡＤインタフェース２３、８×１６ＳＡＤインタフェース２４、及び１６×１６ＳＡＤインタフェース２５を備えている。
【００６８】
また、４×４基本ブロック演算器１２は、マルチプレクサ２６、加算器２７、４×４ＳＡＤレジスタ２８〜３１から構成されている。８×４横長ブロック演算器１３は、マルチプレクサ３２及び加算器３３から構成されている。４×８縦長ブロック演算器１４は、マルチプレクサ３４、加算器３５、及び４×８ＳＡＤレジスタ３６〜３９から構成されている。８×８正方ブロック演算器１５は、マルチプレクサ４０、加算器４１、及び８×８ＳＡＤレジスタ４２，４３から構成されている。１６×８横長ブロック演算器１６は、加算器４４から構成されている。８×１６縦長ブロック演算器１７は、マルチプレクサ４５、加算器４６、及び８×１６ＳＡＤレジスタ４７から構成されている。１６×１６正方ブロック演算器１８は、加算器４８から構成されている。
【００６９】
差分絶対値演算器１１は、注目画素入力バスCUR BUSから入力される注目ＭＢデータＣ及び参照画素入力バスREF BUS0又はREF BUS1から入力される参照ＭＢデーらＲの差分絶対値｜Ｃ−Ｒ｜を演算する。
【００７０】
４×４基本ブロック演算器１２は、差分絶対値演算器１１が出力する差分絶対値｜Ｃ−Ｒ｜を、最小のブロック・サイズの４×４ブロックごとに累算し、各４×４ブロックに対応する４×４ＳＡＤレジスタ２８〜３１に保存する。４×４ＳＡＤレジスタ２８〜３１内の各ＳＡＤは、マルチプレクサ２６，３２，３４に分配され選択されて、それぞれ、加算器２７，３３，３５に入力される。
【００７１】
８×４横長ブロック演算器１３は、水平方向に隣接する２つの４×４ブロックのＳＡＤが完全に計算されたときに、各ＳＡＤを読み出して加算し、８×４ブロックのＳＡＤを算出する。
【００７２】
４×８縦長ブロック演算器１４は、サイズ４×４の垂直方向に隣接する２つのＭＢのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、４×８ブロックのＳＡＤを算出し出力するとともに、４×８ＳＡＤレジスタ３６〜３９に保存する。４×８ＳＡＤレジスタ３６〜３９内の各ＳＡＤは、マルチプレクサ４０に入力され選択されて、加算器４１に入力される。
【００７３】
８×８正方ブロック演算器１５は、水平方向に隣接する２つの４×８ブロックのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、８×８ブロックのＳＡＤを算出し出力するとともに、８×８ＳＡＤレジスタ４２，４３に保存する。８×８ＳＡＤレジスタ４２，４３内の各ＳＡＤは、マルチプレクサ４５に入力され選択されて、加算器４６に入力される。また、８×８ＳＡＤレジスタ４２内のＳＡＤ（SAD8×8_0）は、加算器４４に入力される。
【００７４】
１６×８横長ブロック演算器１６は、水平方向に隣接する２つの８×８ブロックのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、サイズ１６×８のＭＢのＳＡＤを算出する。
【００７５】
８×１６縦長ブロック演算器１７は、垂直方向に隣接する２つの８×８ブロックのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、８×１６ブロックのＳＡＤを算出し出力するとともに、８×１６ＳＡＤレジスタ４７に保存する。８×１６ＳＡＤレジスタ４７内のＳＡＤ（SAD8×16_0）は、加算器４８に入力される。
【００７６】
１６×１６正方ブロック演算器１８は、水平方向に隣接する２つの８×１６ブロックのＳＡＤが完全に計算されたときに、各ＳＡＤを加算し、サイズ１６×１６のＭＢのＳＡＤを算出し出力する。
【００７７】
４×４基本ブロック演算器１２の出力は、８×４横長ブロック演算器１３の加算器３３、４×８縦長ブロック演算器１４の加算器３５、及び４×４ＳＡＤインタフェース１９に入力される。８×４横長ブロック演算器１３の出力は、８×４ＳＡＤインタフェース２０に入力される。４×８縦長ブロック演算器１４の出力は、８×８正方ブロック演算器１５の加算器４１及び４×８ＳＡＤインタフェース２１に入力される。８×８正方ブロック演算器１５の出力は、１６×８横長ブロック演算器１６の加算器４４、８×１６縦長ブロック演算器１７の加算器４６、及び８×８ＳＡＤインタフェース２２に入力される。１６×８横長ブロック演算器１６の出力は、１６×８ＳＡＤインタフェース２３に入力される。８×１６縦長ブロック演算器１７の出力は、１６×１６正方ブロック演算器１８の加算器４８、及び８×１６ＳＡＤインタフェース２４に入力される。１６×１６正方ブロック演算器１８の出力は、１６×１６ＳＡＤインタフェース２５に入力される。従って、４×４基本ブロック演算器１２、８×４横長ブロック演算器１３、４×８縦長ブロック演算器１４、８×８正方ブロック演算器１５、１６×８横長ブロック演算器１６、８×１６縦長ブロック演算器１７、及び１６×１６正方ブロック演算器１８は、１つの加算器木を構成している。
【００７８】
４×４ＳＡＤインタフェース１９、８×４ＳＡＤインタフェース２０、４×８ＳＡＤインタフェース２１、８×８ＳＡＤインタフェース２２、１６×８ＳＡＤインタフェース２３、８×１６ＳＡＤインタフェース２４、及び１６×１６ＳＡＤインタフェース２５は、それぞれ、４×４基本ブロック演算器１２、８×４横長ブロック演算器１３、４×８縦長ブロック演算器１４、８×８正方ブロック演算器１５、１６×８横長ブロック演算器１６、８×１６縦長ブロック演算器１７、及び１６×１６正方ブロック演算器１８が算出するＳＡＤを、あらかじめ決められたスケジュールに従って、ＳＡＤバスネットワーク２に出力する。
【００７９】
以上のように構成された本実施例１のＳＡＤ演算器１０について、以下そのワークフローを説明する。説明を分かりやすくするため、ＰＥ０を例にとって説明する。
【００８０】
まず、クロック・サイクル０において、注目ＭＢデータＣ（０，０）と参照ＭＢデータＲ（０，０）が差分絶対値演算器１１に入力される。これは、ＢＬＫ４×４＿０の最初の部分ＡＤなので、加算器２７において、生成されるＡＤは０と加算され、４×４ＳＡＤレジスタ２８に格納される。
【００８１】
クロック・サイクル１において、注目ＭＢデータはＣ（１，０）であり、参照ＭＢデータはＲ（１，０）が入力され、生成されるＡＤはまだＢＬＫ４×４＿０に属している。これは、最初のＡＤではないので、４×４ＳＡＤレジスタ２８内のＳＡＤ４×４＿０と加算され、４×４ＳＡＤレジスタ２８に保存される。同様の操作が、クロック・サイクル２，３においても行われる。
【００８２】
クロック・サイクル４〜７，８〜１１，１２〜１５においては、生成されるＡＤはＢＬＫ４×４＿１，４×４＿２，及び４×４＿３に属するので、選択されるＳＡＤレジスタが異なることを除き、クロック・サイクル０〜３と同様の操作が採られる。
【００８３】
さらに、同様の操作が続けて行われ、そして、クロック・サイクル５１，５５，５９，６３において、ＢＬＫ４×４＿０〜ＢＬＫ４×４＿３のＳＡＤが完全に計算される。従って、クロック・サイクル０〜６３の間に、最上段の４×４ブロック（ＢＬＫ４×４＿０〜ＢＬＫ４×４＿３）に対するＳＡＤが生成され、専用の４×４ＳＡＤインタフェース１９からＳＡＤバスネットワーク２に転送される。
【００８４】
他の４×４ブロックのＳＡＤも、同様の方法で計算され、４×４ＳＡＤインタフェース１９からＳＡＤバスネットワーク２に転送される。
【００８５】
４×８ブロックのＳＡＤの計算は、４×４ブロックのＳＡＤに基づいて行われる。
【００８６】
クロック・サイクル５１において、ＢＬＫ４×４＿０のＳＡＤ値が使用可能となり、それは、ＢＬＫ４×８＿０の上部である。従って、生成されるＢＬＫ４×４＿０のＳＡＤ値は、加算器３５において０と加算され、４×８ＳＡＤレジスタ３６に保存される。
【００８７】
クロック・サイクル１１５において、ＢＬＫ４×４＿４のＳＡＤ値が使用可能となり、それは、ＢＬＫ４×８＿０の下部である。従って、４×８ＳＡＤレジスタ３６に先に保存されたＳＡＤ値と累算することにより、ＢＬＫ４×８＿０のＳＡＤが完全に得られる。計算されたＢＬＫ４×８＿０のＳＡＤは、専用の４×８ＳＡＤインタフェース２１からＳＡＤバスネットワーク２に転送される。
【００８８】
同様に、ＢＬＫ４×８＿１，ＢＬＫ４×８＿２，ＢＬＫ４×８＿３のＳＡＤ値がクロック・サイクル１１９，１２３，１２７において計算され、それぞれ、専用の４×８ＳＡＤインタフェース２１からＳＡＤバスネットワーク２に転送される。
【００８９】
ＢＬＫ４×８＿４〜ＢＬＫ４×８＿７のＳＡＤの計算過程も同様であるため、説明は省略する。
【００９０】
８×８ブロックのＳＡＤを計算するためには、４×８ブロックのＳＡＤが必要となる。
クロック・サイクル１１５において、ＢＬＫ４×８＿０のＳＡＤ値が計算され、４×８ＳＡＤレジスタ３６に保存される。クロック・サイクル１１９において、ＢＬＫ４×８＿１のＳＡＤ値も計算される。このデータと４×８ＳＡＤレジスタ３６に保存されているデータとを加えることにより、ＢＬＫ８×８＿０のＳＡＤが得られる。
【００９１】
クロック・サイクル１２７において、ＢＬＫ８×８＿１のＳＡＤが計算される。クロック・サイクル２４７及び２５５において、同様な方法で、ＢＬＫ８×８＿２及びＢＬＫ８×８＿３のＳＡＤ値をそれぞれ得ることができる。
【００９２】
８×１６ブロックのＳＡＤを計算するためには、８×８ブロックのＳＡＤが必要となる。
【００９３】
クロック・サイクル１１９において、ＢＬＫ８×８＿０のＳＡＤが利用可能となり、８×８ＳＡＤレジスタ４２に保存される。クロック・サイクル２４７において、ＢＬＫ８×８＿２のＳＡＤ値が生成され、２つの値が加算されて、ＢＬＫ８×１６＿０のＳＡＤ値が得られる。
【００９４】
同様の方法で、クロック・サイクル２５５において、ＢＬＫ８×１６＿１のＳＡＤ値が得られる。
【００９５】
他のブロック・モードのＭＢに対するＳＡＤの計算過程は、ずっと単純であり、図６により図示された通りである。従って、ここでは、それらに対応する説明は省略する。
【００９６】
上述の説明から、ＳＡＤ値の計算過程は単純であり、上記従来のアーキテクチャに比べると、整然としていることが分かる。このことを明確にするために、図７にＰＥ０のおけるＳＡＤ値の生成手順を示す。最後の画素をＰＥに入力するとき、対応するＳＡＤが生成されて、ＳＡＤインタフェースからＳＡＤバスネットワーク２に渡される。このように整然としたワークフローは、ＶＬＳＩ実装にとって最適である。
【００９７】
〔３〕ＳＡＤバスネットワーク・アーキテクチャ
上述の説明から、各ＰＥに対して、７ブロック・モードに対する７つの専用のＳＡＤインタフェースがあり、生成されたＳＡＤ値は、関連するＳＡＤインタフェースに直接渡される。従って、１６個のＰＥに対しては、全部で１１２個のＳＡＤインタフェースがある。ＳＡＤバスネットワーク２において、これらのインタフェースにおけるＳＡＤ値をどのようにスケジューリングし、それらを４１個の最小ＳＡＤレジスタに保存された値とどのように比較するかが問題となる。
【００９８】
本実施例のＳＡＤバスネットワーク・アーキテクチャは、次の２つの特徴に基づいて設計される。
【００９９】
（１）異なるＰＥに対して、同じＭＢのＳＡＤ値は、１クロック・サイクルの時間間隔ずつずれて、異なるクロック・サイクルにおいて得られる。例えば、図３のＢＬＫ４×４＿０に対しては、ＰＥ０ではクロック・サイクル５１，ＰＥ１ではクロック・サイクル５２，ＰＥ２ではクロック・サイクル５３，…においてＳＡＤ値が得られる。従って、最小ＳＡＤに対するコンパレータは、ハードウェア・コストを削減するために、隣接するＰＥ間で共有される。
【０１００】
（２）図３に示されるように、Ｈ．２６４／ＡＶＣの７つのブロック・モードは、３つのカテゴリに分類することができる。
【０１０１】
４×４ブロックと４×８ブロックは、同じＰＥ内の隣接するＳＡＤ値は４クロック・サイクルの間隔で生成されるため、Group．１に分類することができる。例えば、ＰＥ０において、ＢＬＫ４×４＿０及びＢＬＫ４×４＿１のＳＡＤは、４サイクルの時間間隔をおいて、それぞれ、クロック・サイクル５１，５５において生成される。ＢＬＫ４×８＿０及びＢＬＫ４×８＿１のＳＡＤに対しては、それらは、４サイクルの時間間隔をおいて、クロック・サイクル１１５及び１１９において生成される。
【０１０２】
同様の理由により、８×４ブロック、８×８ブロック、及び８×１６ブロックのブロック・モードはGroup．２に分類され、１６×８ブロック及び１６×１６ブロックのブロック・モードはGroup．３に分類される。
【０１０３】
この２つの性質に基づき、ＳＡＤバスネットワーク・アーキテクチャを設計する。Group．１のすべてのブロック・モードでは、各々は４つのＳＡＤバスを有し、隣接する４つのＰＥでは１つのＳＡＤバスを共有する。Group．２のブロック・モードでは、各々は２つのＳＡＤバスを有し、隣接する８つのＰＥは同じＳＡＤバスを共有する。Group．３のブロック・モードでは、各々は１つのＳＡＤバスを有し、隣接する１６個のＰＥは同じＳＡＤバスを共有する。
【０１０４】
従って、図２に示したように、全部で１１２個のＰＥ ＳＡＤインタフェースが、１６分割されたＳＡＤバス上で時分割転送を行う。各ＳＡＤバスは１個のコンパレータを備えるため、全部で１６個のコンパレータが必要とされる。
【０１０５】
ＳＡＤバスネットワーク２上のデータ転送について分かりやすく説明するため、４×４ブロックに対する４つのＳＡＤバスを例として説明する。
【０１０６】
上述のように、１６個のＰＥが４つの４×４ＳＡＤバスを共有する。すなわち、ＰＥ０〜ＰＥ３は、ＳＡＤ４×４＿ＢＵＳ０を共有し、ＰＥ４〜ＰＥ７は、ＳＡＤ４×４＿ＢＵＳ１を共有する、などである。
【０１０７】
図８に、４×４ＳＡＤバスにおけるデータ転送手順を示す。図８に示したように、これら４つのＳＡＤバスにおいて、ＢＬＫ４×４＿０〜ＢＬＫ４×４＿３のＳＡＤ値のデータが転送される。他の４×４ブロックのデータ転送も同様であるため、説明は省略する。
【０１０８】
ＳＡＤ４×４＿ＢＵＳ０に対して、クロック・サイクル５１において、ＰＥ０で、ＢＬＫ４×４＿０のＳＡＤが生成され、このデータが転送される。クロック・サイクル５２において、ＰＥ１で、同じブロックＢＬＫ４×４＿０のＳＡＤが生成され、このデータが転送される。クロック・サイクル５３，５４においても同様の操作が続けて行われ、ＰＥ２及びＰＥ３のＢＬＫ４×４＿０に対するＳＡＤが転送される。
【０１０９】
クロック・サイクル５５において、ＰＥ０内のＢＬＫ４×４＿１のＳＡＤが生成され、ＳＡＤ４×４＿ＢＵＳ０により転送される。同様にして、クロック・サイクル５５〜５８に、ＰＥ０〜ＰＥ３におけるＢＬＫ４×４＿１のＳＡＤがすべて転送される。
【０１１０】
同様に、ＰＥ０〜ＰＥ３におけるＢＬＫ４×４＿２及びＢＬＫ４×４＿３に対するＳＡＤは、それぞれ、クロック・サイクル５９〜６２及び６３〜６６の間に、ＳＡＤ４×４＿ＢＵＳ０により転送される。
【０１１１】
ＳＡＤ４×４＿ＢＵＳ１〜ＳＡＤ４×４＿ＢＵＳ３に対しても、異なるＰＥの管理下にある点を除いて、同様の転送が行われる。
【０１１２】
各ＳＡＤバスに対して、専用のコンパレータが備えられている。従って、全部で１６個のコンパレータが必要とされる。クロック・サイクルに従って、ＳＡＤバスに転送されたＳＡＤ値と比較するために、クロック・サイクルに応じて、異なる最小ＳＡＤレジスタに保存された最小ＳＡＤ値が選択される。もし、新たに転送されたＳＡＤ値が、先に保存された最小ＳＡＤ値よりも小さい場合には、対応する最小ＳＡＤレジスタとＭＶレジスタは更新される。
【０１１３】
例えば、図８に示すように、ＳＡＤ４×４＿ＢＵＳ０のコンパレータに対して、クロック・サイクル５１〜５４の間、新たに生成されるＳＡＤ値と比較するため、ＢＬＫ４×４＿０に対する最小ＳＡＤレジスタが選択される。クロック・サイクル５５〜５８の間は、新たに生成されるＳＡＤ値と比較するため、ＢＬＫ４×４＿１に対する最小ＳＡＤレジスタが選択される。以下同様である。
【０１１４】
他のＳＡＤバスにおけるコンパレータのワークフローも同様であり、図８と同様にして説明される。
【図面の簡単な説明】
【０１１５】
【図１】ＶＢＳＭＥで使用されるＭＢを示す図である。
【図２】本発明の実施例１に係る可変ブロック・サイズ動き推定器１の構成を表すブロック図である。
【図３】各ＰＥにおいて計算される部分ＭＢを表す図である。
【図４】注目ＭＢ及び参照ＭＢにおける走査順を示す図である。
【図５】各クロック・サイクルにおいて参照画素入力バスREF BUS0，REF BUS1に出力される参照画素の座標値とマルチプレクサＭＵＸ０〜ＭＵＸ１５の選択状態の関係である。
【図６】各ＰＥを構成する本発明の実施例１に係るＳＡＤ演算器の構成を表す図である。
【図７】ＰＥ０のおけるＳＡＤ値の生成手順を示す図である。
【図８】４×４ＳＡＤバス（ＳＡＤ４×４＿ＢＵＳ０〜ＳＡＤ４×４＿ＢＵＳ３）におけるデータ転送手順を示す図である。
【図９】非特許文献５に記載の1-D VBSMEアーキテクチャの全体構成を示す図である。
【図１０】ＭＢ内の基本ブロックの配置を示す図である。
【図１１】図９の各ＰＥの構成を示す図である。
【図１２】非特許文献５に記載の1-D VBSMEアーキテクチャにおける各クロックにおけるＳＡＤ演算のスケジューリングを示す図である。
【符号の説明】
【０１１６】
可変ブロック・サイズ動き推定器１
ＰＥ０〜ＰＥ１５  プロセッサ・エレメント
Pos. BUS  位置入力バス
CUR BUS  注目画素入力バス
REF BUS0, REF BUS1  参照画素入力バス
Ｄｐ０〜Ｄｐ１５  位置データ遅延器
Ｄｃ０〜Ｄｃ１５  注目画素データ遅延器
ＭＵＸ０〜ＭＵＸ１５  マルチプレクサ
ＭＩＮ０〜ＭＩＮ１５  最小ＳＡＤ演算器
２  ＳＡＤバスネットワーク
１０  ＳＡＤ演算器
１１  差分絶対値演算器
１２  ４×４基本ブロック演算器
１３  ８×４横長ブロック演算器
１４  ４×８縦長ブロック演算器
１５  ８×８正方ブロック演算器
１６  １６×８横長ブロック演算器
１７  ８×１６縦長ブロック演算器
１８  １６×１６正方ブロック演算器
１９  ４×４ＳＡＤインタフェース
２０  ８×４ＳＡＤインタフェース
２１  ４×８ＳＡＤインタフェース
２２  ８×８ＳＡＤインタフェース
２３  １６×８ＳＡＤインタフェース
２４  ８×１６ＳＡＤインタフェース
２５  １６×１６ＳＡＤインタフェース
２６  マルチプレクサ
２７  加算器
２８〜３１  ４×４ＳＡＤレジスタ
３２  マルチプレクサ
３３  加算器
３４  マルチプレクサ
３５  加算器
３６〜３９  ４×８ＳＡＤレジスタ
４０  マルチプレクサ
４１  加算器
４２，４３  ８×８ＳＡＤレジスタ
４４  加算器
４５  マルチプレクサ
４６  加算器
４７  ８×１６ＳＡＤレジスタ
４８  加算器
【図１】
2007281977.tif 000004
【図２】
2007281977.tif 000005
【図３】
2007281977.tif 000006
【図４】
2007281977.tif 000007
【図５】
2007281977.tif 000008
【図６】
2007281977.tif 000009
【図７】
2007281977.tif 000010
【図８】
2007281977.tif 000011
【図９】
2007281977.tif 000012
【図１０】
2007281977.tif 000013
【図１１】
2007281977.tif 000014
【図１２】
2007281977.tif 000015