(57)【特許請求の範囲】
【請求項１】
複数のプロセッサエレメントにより並列に演算を実行することによって原画像と参照画像との差分絶対値和を算出するＰＥアレイ部と，動き探索の対象となる参照画像の画素データを記憶するメモリと，前記メモリから参照画像の画素データを読み出すメモリリード部と，前記メモリから読み出した画素データを並び替えて前記ＰＥアレイ部への入力とする画素並び替え部と，前記ＰＥアレイ部によって算出された差分絶対値和をもとに参照画像の所定の探索範囲における動きベクトルを検出し評価する評価部と，これらの各部による動き探索を制御する制御部とを備えた動画像符号化における動き探索装置において，
前記メモリリード部は，前記ＰＥアレイ部に同時に入力させる複数ラインの画素データが，前記メモリにおける同一バンクに格納されているときに，その複数ラインの画素データの前記メモリからの読み出しタイミングをライン単位でずらし，前記ＰＥアレイ部への入力に必要なタイミングよりも早いタイミングで画素データを読み出す制御を行う競合バンク先行読み出し制御部を備え，
前記画素並び替え部は，前記メモリリード部によって前記ＰＥアレイ部への入力に必要なタイミングよりも早いタイミングで読み出されたラインの画素データを，前記ＰＥアレイ部への入力タイミングまで保持する読み込みデータ保持回路を備える
ことを特徴とする動画像符号化における動き探索装置。
【請求項２】
請求項１記載の動画像符号化における動き探索装置において，
前記画素並び替え部は，動き探索範囲の領域が参照画像の垂直方向の画面外の領域である場合に，画面外の領域の画素データとして参照画像における画面境界部のラインの画素データをコピーして前記ＰＥアレイ部に対する入力とする垂直方向コピー部を備える
ことを特徴とする動画像符号化における動き探索装置。
【請求項３】
請求項１または請求項２記載の動画像符号化における動き探索装置において，
前記画素並び替え部は，動き探索範囲の領域が参照画像の水平方向の画面外の領域である場合に，画面外の領域の画素データとして参照画像における同じラインの画面境界部の画素データを水平方向にコピーして前記ＰＥアレイ部に対する入力とする水平方向コピー部を備える
ことを特徴とする動画像符号化における動き探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，動画像符号化においてシストリックアレイを用いて動き探索を行う動画像符号化における動き探索装置に関するものである。
【背景技術】
【０００２】
動画像符号化において，動きベクトルの検出に要する演算量は膨大であり，その演算処理の高速化のために，シストリックアレイを用いた動き探索装置が開発され，実用化されている（非特許文献１，特許文献１，非特許文献２，特許文献２参照）。
【０００３】
シストッリクアレイは，複数のプロセッサエレメント（以下，ＰＥと記す）を規則正しく配列し，複数のＰＥに演算対象データをパイプライン的に流すことにより，複数のＰＥによる演算処理を並列に高速に実行する演算装置である。ＰＥアレイともいう。
【０００４】
特に，高速な動画像符号化処理が要求される動き探索装置では，原画像の符号化対象ブロックと参照画像との間の画素値の差分絶対値和（ＳＡＤ）の計算を参照画像の動き探索範囲内で繰り返す処理に，前記ＰＥアレイを利用することにより，動きベクトル検出の高速化が図られている。
【０００５】
図９は，従来の動き探索装置におけるＰＥアレイの構成例を示している。この例では，８個のプロセッサエレメントＰＥ００〜ＰＥ３１によって，４×２画素の原画像と参照画像との間の差分絶対値和を算出する構成になっている。ＰＥの数を増やすことにより，例えば４×４画素または８×８画素というような単位での差分絶対値和を算出する構成にすることもできる。また，図９に示すＰＥアレイ４０を複数個組み合わせて，ｎ×ｍ画素（ｎ≧４，ｍ≧４）の差分絶対値和の演算回路を構成することもできる。
【０００６】
ＰＥアレイ４０には，原画像入力データＳＭＢと，４本の参照画像入力データＲＡ００，ＲＡ０１，ＲＡ１０，ＲＡ１１と，演算する参照画像入力データを選択するためのセレクタを制御する参照画像切替制御入力信号ＲＡＳＷの入力端子がある。出力端子としては，差分絶対値累算結果出力ＡＤＯＵＴの出力端子がある。
【０００７】
各ＰＥは，図９（Ｂ）に示すように，原画像入力データの入力端子ＭＢｉｎと，左隣のＰＥからの加算値の入力端子ＡＤＤｉｎと，右隣のＰＥへの加算値の出力端子ＡＤＤｏｕｔと，２本の参照画像入力データの入力端子ＲＡｉｎ０，ＲＡｉｎ１を持っている。
【０００８】
図１０は，図９に示すＰＥアレイ４０の動作を説明する図である。例えば図１０（Ａ）に示すような原画像の４×２の画素群（画素値ｃ００〜ｃ３１）に対して，図１０（Ｂ）に示す参照画像（画素値ｘ００，ｘ０１，…）の中で差分絶対値和がもっとも小さくなる部分を探索するための演算を行うものとする。
【０００９】
図１０（Ｃ）において，各ＰＥ００，ＰＥ１０，ＰＥ２０，…には，原画像の画素値ｃ００，ｃ１０，ｃ２０，…が，最初の８サイクル（クロックＣＬＫ）で順次入力され，保持される。サイクル１では，ＰＥ００は，原画像の画素値ｃ００と参照画像の画素値ｘ００とを入力し，その差分絶対値Ｓ００＝｜ｃ００−ｘ００｜を算出する。
【００１０】
次のサイクル２では，ＰＥ００は，参照画像の画素値ｘ１０を入力し，その差分絶対値和Ｓ０１＝｜ｃ００−ｘ１０｜を算出する。ＰＥ１０は，ＰＥ００がサイクル１で算出した値Ｓ００に，原画像の画素値ｃ１０と参照画像の画素値ｘ１０との差分絶対値を加算した値Ｓ１０を算出する。
【００１１】
次のサイクル３では，ＰＥ００は，参照画像の画素値ｘ２０を入力し，その差分絶対値和Ｓ０２＝｜ｃ００−ｘ２０｜を算出する。ＰＥ１０は，ＰＥ００がサイクル２で算出した値Ｓ０１に，原画像の画素値ｃ１０と参照画像の画素値ｘ２０との差分絶対値を加算した値Ｓ１１を算出する。ＰＥ２０は，ＰＥ１０がサイクル２で算出した値Ｓ１０に，原画像の画素値ｃ２０と参照画像の画素値ｘ２０との差分絶対値を加算した値Ｓ２０を算出する。
【００１２】
以上のように，各ＰＥ００〜ＰＥ３１がパイプライン的に演算を実行していくと，ＰＥアレイ４０の出力端子ＡＤＯＵＴから，最初にｃ００〜ｃ３１とｘ００〜ｘ３１との差分絶対値和が出力され，次のサイクルでは，ｃ００〜ｃ３１とｘ１０〜ｘ４１との差分絶対値和が出力され，次のサイクルでは，ｃ００〜ｃ３１とｘ２０〜ｘ５１との差分絶対値和が出力されるというように，各サイクルごとに動きベクトルの探索範囲内における差分絶対値和が順次出力されることになる（詳しくは，非特許文献１，２および特許文献１，２参照）。
【００１３】
図１１は，ＰＥアレイ４０のタイミングチャートを示している。図１１において，ＨＯＬＤＭＢは，各ＰＥ００〜ＰＥ３１に対し原画像入力データＳＭＢを保持し，演算を開始することを指示する起動信号，ＣＬＫはクロック，ＨＯＬＤＳＥＬは参照画像切替制御入力信号を表す。図１１では，参照画像の画素値を，参照画像の画素座標（ｘ，ｙ）で表している。例えば（０，０）が図１０に示す画素値ｘ００に相当する。ＰＥアレイ４０には，参照画像の各画素値が順次供給されるが，参照画像メモリからの画素値の読み出しは，メモリへの画素の格納方法の都合上やメモリアクセスの回数を減らすために，通常は複数画素まとめて行われる。図１１では，ＣＬＫ０で，参照画像の画素値（０，０）〜（６，０）と，（０，１）〜（６，１）が参照画像メモリから同時に入力され，ＣＬＫ８では，参照画像の画素値（０，２）〜（６，２）と，（０，３）〜（６，３）が参照画像メモリから同時に入力される例を示している。
【００１４】
ＣＬＫ０で読み込んだ７画素×２のデータは，ＣＬＫ１からの７クロックで最初の７画素がＰＥアレイ４０に順次供給され，ＣＬＫ５からの７クロックで別の７画素がＰＥアレイ４０に順次供給される。ＣＬＫ９のときに，探索原点位置座標（０，０）での差分絶対値累算結果が出力されることになる。ＣＬＫ１０では，探索原点位置座標（１，０）での差分絶対値累算結果が出力される。
【００１５】
図１２は，参照画像メモリからのリードタイミングを示している。前述のように，最初のサイクルでは，７画素×２のデータが参照画像メモリから読み出されるが，２つのデータを同じメモリバンクから同時に読み出すことができないので，例えば画像のラインごとに，Ｂａｎｋ０，Ｂａｎｋ１，Ｂａｎｋ２，Ｂａｎｋ０，…というように，データを各バンクに分けて格納している。これによりバンク競合を避けて，例えばＢａｎｋ０とＢａｎｋ１のデータを同時に参照画像メモリから読み出すことができるようにしている。
【００１６】
以上のような参照画像メモリからの読み出し機構を備えた動き探索装置において，参照画像の探索範囲における最下ラインから次の動き探索のために最上ラインに移る場合には，ＰＥアレイ４０における演算時間に空きが生じないようにするためには，一度に７画素×３のデータ，すなわち最下ラインのデータを読み出すとともに，最上２ラインのデータを同時に読み出す必要がある。図１２におけるサイクル３２のときの読み出しが，それに当たる。すなわち，サイクル３２では，先頭が（０，８）の最下ライン１本と，先頭が（４，０）と（４，１）の２本の最上ラインのデータを同時に読み出す必要がある。ここでは，探索範囲のライン数が奇数の場合の例を説明するが，偶数の場合も同様である。
【００１７】
ＭＰＥＧ−２などの従来の画像符号化方式における動き探索では，参照画像の参照位置が画面外にはみ出るような探索は行う必要がなかったため，最下ライン１本と最上ライン２本のデータを同時に読み出す場合でも，それぞれのバンクが異なり，バンク競合によるメモリ読み出しの遅延の問題が生じることはなかった。
【非特許文献１】南俊宏，近藤利夫，村主一仁，笠井良太，“１次元シストリックアレー型全探索動きベクトル検出器の提案”，電子情報通信学会論文誌Ｄ−Ｉ，Vol.J78-D-I, No.12, pp.913-925, 1995年12月。
【非特許文献２】南俊宏，長沼次郎，“テレスコピック探索に適した動きベクトル検出器構成方法の提案”，電子情報通信学会論文誌Ｄ−II，Vol.J87-D-II, No.11, pp.2007-2024,  2004年11月。
【特許文献１】特許第３１２７９８０号公報
【特許文献２】特開２００５−１３６４５５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
図１３は，動きベクトルを検出する探索範囲を示す図である。動き探索は，図１３（Ａ）に示す原画像２００における符号化対象ブロック２０１に最も近い画素値群を持つ参照画像１００の位置を探し出すために，参照画像１００における，例えば符号化対象ブロックの座標位置を探索中心１０１として，あらかじめ決められた大きさの探索範囲１０２から，符号化対象ブロックのサイズの画素値群を少しずつずらしながら順次切り出し，符号化対象ブロック２０１の画素値との差分絶対値和（ＳＡＤ）を算出していく。探索範囲１０２内で算出した差分絶対値をもとに動き評価を行い，動きベクトルを決定する。
【００１９】
例えばＨ．２６４符号化方式では，この動き探索を参照画像１００の外まで拡張して行うことができるように定められている。すなわち，Ｈ．２６４は，図１３（Ｂ）に示すように，符号化対象ブロック２０１の位置が原画像２００の画像端部に近い位置にある場合，探索範囲１０２は，参照画像１００の外側まで広がる仕様になっている。このとき，参照画像１００における画面外における画素値は，図１３（Ｃ）に示すように，画面上の外側に対しては，参照画像１００の最上段の画素値がコピーされた値を用い，画面左の外側に対しては，参照画像１００の最左端の列の画素値がコピーされた値が用いられるようになっている。参照画像１００の最下段，最右端についても同様である。
【００２０】
図１３（Ｃ）に示したような画面外への画素値をコピーした値を用いた場合の動き探索を，図９に示したＰＥアレイ４０を用いて行うときの最も簡単な対処方法としては，１参照画像分の参照画像メモリのサイズを参照画像のサイズよりも画面外の探索範囲分だけ大きく取っておき，参照画像の格納時にあらかじめ画面外の画素値を画面端部の画素値と同じ値に設定しておく方法が考えられる。しかし，この方法は，参照画像メモリのハードウェア量が余分に必要になるという問題がある。
【００２１】
他の方法としては，参照画像メモリからの画素値の読み出し時に，探索範囲が画面外であれば，画面端部の画素値を読み出す方法である。しかし，この方法は，以下で説明するようなバンク競合の問題が発生する。
【００２２】
図１４は，メモリバンク構成と画面外画素リード時のバンク競合の問題を説明する図である。図１４において，ＬＡＸはＸ方向の論理アドレス，ＬＡＹはＹ方向の論理アドレスを示す。また，＃０，＃１，…，＃５は，メモリバンクのバンク番号を表している。メモリバンクのバンク番号が異なる場合には，同時にデータをリードすることができるが，バンク番号が同じ場所からのデータは，バンク競合によって同時にリードすることができない。
【００２３】
図１４（Ａ）に示すように，動きの探索範囲が画面内の場合には，探索範囲の最下ラインから最上ラインへ探索を移す場合に，同時に読み出すデータは太枠で示されるバンク番号が＃２の最下ラインと，バンク番号が＃０（および＃３）と＃１（および＃４）の２本の最上位ラインであり，バンク競合が生じることはない。これは，従来技術と同様である。
【００２４】
しかしながら，動きの探索範囲が，例えば図１４（Ｂ）に示すように上画面外であった場合には，探索範囲の最下ラインから最上ラインへ探索を移す場合に，画面外では画面端部の画素値をコピーした値を用いる必要があるため，ＬＡＹ＝８の最下ラインと，ＬＡＹ＝０およびＬＡＹ＝１の２本の最上位ラインのデータとを読み出す代わりに，ＬＡＹ＝８の最下ラインと，ＬＡＹ＝５の画面端部のラインのデータを読み出すことになる。しかし，図から明らかであるように，ＬＡＹ＝８のラインもＬＡＹ＝５のラインもバンク番号は＃０であり，同じであるためバンク競合が生じ，これらのデータを同時に読み出すことはできない。
【００２５】
この問題を解決するために，メモリのバンク数を増やすのは，メモリバンク構成が複雑になり，また，一方のデータの読み出しを他方のデータの読み出しが終了するまで待たせるのは，ＰＥアレイ４０におけるパイプライン処理の流れに乱れが生じ，演算時間が長くなるという問題がある。
【００２６】
例えばバンク競合によって，競合する一方のデータの読み出しに８サイクル分余計な時間がかかるとすると，おおよその試算で約２５％のオーバーヘッドとなる。これは，バンク競合がない場合，縦の全９ラインを４回分の読み出しの時間で読んでいると考えることができるのに対し，バンク競合があると，最後の１ラインと最上２ラインとを同時に読むことができないので，縦の全９ラインを読むのに５回分の時間がかかることになるからである。
【００２７】
以上の問題点をまとめて説明すると以下のとおりである。動きベクトル検出を図９に示すようなＰＥアレイ（シストリックアレイ）４０を用いて構成する場合，参照画像の画素を複数ライン同時に読む必要がある。このため，同時に読む可能性のあるラインは，メモリ上の別のバンクに割り当てておく必要があった。
【００２８】
この方式を，画面外動きベクトルが許容されているＨ．２６４等に適用するためには，画面外画素（画素値は境界画素の値）を余分にメモリに格納しておく必要があった。そのため，メモリのハードウェア量が増加するという問題があった。しかし，画面外画素を格納するためのメモリを持たない場合，シストリックアレイの読み出しパターンが画面外画素を含むときに不規則となり，図１４（Ｂ）に示すようにバンク競合が発生して，高速な演算ができなくなるという問題があった。
【００２９】
本発明は上記問題点の解決を図り，画面外画素の格納用のメモリを増やすことなく，かつ，バンク競合が発生しないような動き探索装置を提供することを目的とする。
【課題を解決するための手段】
【００３０】
本発明では，複数のプロセッサエレメント（ＰＥ）により並列に演算を実行するＰＥアレイを用いる動き探索において，符号化対象ブロックとの差分絶対値和の算出に用いる参照画像の画素群の最上のラインが画面外の場合には，画面内での最上のラインを読み出すこととし，さらに探索範囲の最下ラインと，次の探索範囲の最上ラインとを同時に読み出すときのバンク競合を回避するために，最下ラインだけ直前のラインの読み出しと同時に先行して読み出すようにし，読み出しタイミングを早める。先行して読み出した最下ラインのデータは，シフトレジスタ等のデータ保持回路に保持しておき，ＰＥアレイが演算に必要になった時点でデータ保持回路から供給する。
【００３１】
また，探索範囲の画素が参照画像の水平方向の画面外である場合には，ライン読み出し後に，画面端の画素値をコピーする。なお，垂直方向の下が画面外であるときには，すでに読んでいる画面端ラインをコピーしてそのまま使用することができる。
【００３２】
具体的には，本発明は，  複数のプロセッサエレメントにより並列に演算を実行することによって原画像と参照画像との差分絶対値和を算出するＰＥアレイ部と，動き探索の対象となる参照画像の画素データを記憶するメモリと，前記メモリから参照画像の画素データを読み出すメモリリード部と，前記メモリから読み出した画素データを並び替えて前記ＰＥアレイ部への入力とする画素並び替え部と，前記ＰＥアレイ部によって算出された差分絶対値和をもとに参照画像の所定の探索範囲における動きベクトルを検出し評価する評価部と，これらの各部による動き探索を制御する制御部とを備えた動画像符号化における動き探索装置において，前記メモリリード部は，前記ＰＥアレイ部に同時に入力させる複数ラインの画素データが，前記メモリにおける同一バンクに格納されているときに，その複数ラインの画素データの前記メモリからの読み出しタイミングをライン単位でずらし，前記ＰＥアレイ部への入力に必要なタイミングよりも早いタイミングで画素データを読み出す制御を行う競合バンク先行読み出し制御部を備え，前記画素並び替え部は，前記メモリリード部によって前記ＰＥアレイ部への入力に必要なタイミングよりも早いタイミングで読み出されたラインの画素データを，前記ＰＥアレイ部への入力タイミングまで保持する読み込みデータ保持回路を備えることを特徴とする。
【００３３】
また，上記発明において，前記画素並び替え部は，動き探索範囲の領域が参照画像の垂直方向の画面外の領域である場合に，画面外の領域の画素データとして参照画像における画面境界部のラインの画素データをコピーして前記ＰＥアレイ部に対する入力とする垂直方向コピー部を備えることを特徴とする。
【００３４】
またさらに，上記発明において，前記画素並び替え部は，動き探索範囲の領域が参照画像の水平方向の画面外の領域である場合に，画面外の領域の画素データとして参照画像における同じラインの画面境界部の画素データを水平方向にコピーして前記ＰＥアレイ部に対する入力とする水平方向コピー部を備えることを特徴とする。
【発明の効果】
【００３５】
本発明によれば，ＰＥアレイを用いて行う動き探索において，画面外動きベクトルについても検出が可能になる。特に，画面外（垂直方向）用のメモリを持つ必要がなく，また，画面外（水平方向）用のメモリも持つ必要がない。また，メモリバンクのバンク数を増やすことなく，バンク競合を回避することができるようになる。
【発明を実施するための最良の形態】
【００３６】
図１は，本発明の概要を説明する図である。図１（Ａ）に示す参照画像メモリ３０において，探索範囲の最下ラインのデータＤａｔａ３がメモリのバンクａにあり，次の探索範囲の最上ラインのデータＤａｔａ１およびＤａｔａ２が，それぞれバンクａ，バンクｂにあったとする。これらのデータをＰＥアレイ部４に供給するために，参照画像メモリ３０から同時に読み出そうとすると，Ｄａｔａ１とＤａｔａ３とが同じバンクａに存在するため，バンク競合が生じる。
【００３７】
そこで，メモリリード部１の競合バンク先行読み出し制御部１０は，画面外の探索範囲における動きベクトルを検出するときに，探索範囲の最下ラインと最上の２ラインとの間でバンク競合が生じる場合には，最下ラインのデータＤａｔａ３の読み出しを，直前のラインの読み出しと同時に先行して読み出すように制御する。
【００３８】
画素並び替え部２は，メモリ３から読み出した画素データを，ＰＥアレイ部４における演算順序に従って並び替えて，ＰＥアレイ部４に供給する。特に，先行して読み出した最下ラインのデータＤａｔａ３を，読み込みデータ保持回路２０に保持し，ＰＥアレイ部４の入力が必要になった時点で，ＰＥアレイ部４に供給する。
【００３９】
また，画素並び替え部２における水平方向コピー部２２は，水平方向の画面外の探索範囲における動きベクトルを検出するときに，画面端の画素値をコピーしてＰＥアレイ部４に供給する。垂直方向コピー部２４は，探索範囲の領域が上画面外または下画面外のときに，画面上境界または画面下境界の画素値をコピーしてＰＥアレイ部４に供給する。
【００４０】
図２は本実施の形態に係る動き探索装置の全体構成図である。また，図３はメモリリード部１の詳細構成図，図４は画素並び替え部２の詳細構成図である。
【００４１】
メモリリード部１および画素並び替え部２以外の各部は，従来のシストリックアレイを用いた動き探索装置の構成と同様である。メモリ３は，原画像および参照画像の画素データを記憶する。なお，原画像の画素データについては別のメモリに記憶され，入力端子から入力されるようになっていてもよい。ＰＥアレイ部４は，図９で説明したような複数のプロセッサエレメント（ＰＥ）と，セレクタや加算回路，レジスタ等からなるＰＥアレイ４０を，符号化対象ブロックのサイズに応じて複数個用いて構成される。評価部５は，ＰＥアレイ部４の出力である差分絶対値和（ＳＡＤ：Sum of Absolute Difference），および動きベクトルＭＶと予測動きベクトルＰＭＶとの差分などの符号化のコスト情報から，動きベクトルを評価し，評価結果を制御部６に返す。
【００４２】
制御部６は，プログラム制御により動き探索装置の全体の制御を行う。メモリリード部１に対しては，制御部６は，探索する領域（中心動きベクトルＭＶ）を指定して探索の開始を指示する。メモリリード部１は，探索範囲を示す論理アドレスを，メモリ３における実アドレスに変換し，メモリ３に対するリード要求を行う。また，探索範囲が画面外かどうかのチェックを行い，画面外の場合には，その画面外情報を画素並び替え部２に通知する。画素並び替え部２は，メモリ３から読み出された画素データの切り出しおよび並び替えを行い，ＰＥアレイ部４に供給する。
【００４３】
メモリリード部１は，図３に示すように，論理アドレス生成部１１，画面外判定部１２，論理アドレス／実アドレス変換部１３，メモリアクセス部１４から構成される。論理アドレス生成部１１および論理アドレス／実アドレス変換部１３については，従来の装置と同様である。論理アドレス生成部１１は，制御部６から指定された探索する領域を指定する中心動きベクトルＭＶの情報から，図１４に示すような探索範囲の相対的なアドレスを示す論理アドレスＬＡＸ，ＬＡＹを生成する。
【００４４】
画面外判定部１２は，論理アドレス生成部１１が生成した論理アドレスが参照画像の画面内であるか画面外であるかを判定し，画面外である場合には，画面外情報をメモリアクセス部１４および画素並び替え部２へ送る。論理アドレス／実アドレス変換部１３は，論理アドレス生成部１１が生成した論理アドレスを，メモリ３における実際の画素データが格納されている実アドレスに変換する処理を行う。この論理アドレスから実アドレスへの変換は，メモリ３への参照画像の格納時に，参照画像の先頭実アドレスを記憶しておくことにより，容易に行うことができる。なお，制御部６から事前に通知された原画像における符号化対象ブロックのアドレスについても，実アドレスへの変換が行われる。
【００４５】
変換された実アドレスは，メモリアクセス部１４へ送られ，メモリアクセス部１４は，図８に従って後述するタイミングで，メモリ３に対するリード要求を送出する。特に，競合バンク先行読み出し制御部１０は，探索範囲が上画面外を含む場合に，図１で説明したバンク競合を避けるためのアクセス制御を行う。
【００４６】
画素並び替え部２は，図４に示すように，水平方向（Ｘ方向）切り出し部２１と，水平方向コピー部２２と，パラレル／シリアル変換部２３と，垂直方向（Ｙ方向）コピー部２４と，垂直方向並び替え部２５とを備える。このうち，水平方向切り出し部２１，パラレル／シリアル変換部２３，垂直方向並び替え部２５については，従来の装置と同様である。
【００４７】
メモリ３から画素並び替え部２に読み出されるデータは，１ラインにつき１６画素のデータを含む。そこで，水平方向切り出し部２１は，読み出したデータの中から，動き探索に必要になる８画素×３ラインのデータを切り出す。
【００４８】
水平方向コピー部２２は，画面外判定部１２から通知された画面外情報をもとに，水平方向の画面外動きベクトルを検出する演算を行う場合に，画面外の画素データとして画面境界（画面端）の画素値をコピーする処理を行う。
【００４９】
図５は，水平方向コピー部２２が行う画素値のコピーのし方を説明する図である。図５において，ＥＩＬＲＦＬＧは左右領域フラグであり，これが“００”の場合，探索領域がすべて画面内に存在し，“１０”の場合，画面端が左側に存在し，“０１”の場合，画面端が右側に存在することを示す。ＥＩＸＬＶＡＬは左画面端からのＸ方向の距離であり，ＥＩＸＲＶＡＬは右画面端からのＸ方向の距離である。Ｄ０〜Ｄ７は画素値のデータであり，ＭＳＢは８画素のデータ列の最上位側のデータ，ＬＳＢは最下位側のデータを示している。
【００５０】
水平方向コピー部２２は，画面外情報としてＥＩＬＲＦＬＧ，ＥＩＸＬＶＡＬ，ＥＩＸＲＶＡＬ等の情報を画面外判定部１２から受けると，その値に応じて，ＥＩＬＲＦＬＧ＝１０の場合には，図５（Ａ１），（Ａ２）に示すようなＸ方向の画素値のコピーを行い，ＥＩＬＲＦＬＧ＝０１の場合には，図５（Ｂ１），（Ｂ２）に示すようなＸ方向の画素値のコピーを行う。
【００５１】
図６は，水平方向コピー部２２の回路構成例を示している。図６において，ＥＤＩ０〜ＥＤＩ７は，それぞれ図５に示すＤ０〜Ｄ７の画素値の入力データである。また，ＸＥＩＸＣＰＯ０〜ＸＥＩＸＣＰＯ７は，それぞれＸ方向画素コピー処理データ０〜Ｘ方向画素コピー処理データ７であり，画面端のデータが図５に示したように画面外にコピーされた結果の出力データである。
【００５２】
水平方向コピー部２２では，ＥＩＬＲＦＬＧ，ＥＩＸＬＶＡＬ，ＥＩＸＲＶＡＬの入力信号によって，画素値の入力データＥＤＩ０〜ＥＤＩ７を，図６に示すセレクタで選択することにより，図５に示すＸ方向のデータのコピーを行う。
【００５３】
図４に示すパラレル／シリアル変換部２３は，水平方向コピー部２２の出力する８画素×３ラインの画素データを，各ラインについて１画素ずつ順番に切り出し，１画素×３ラインの画素データに変換して出力する。
【００５４】
垂直方向コピー部２４は，探索範囲の領域が上画面外または下画面外のときに，画面上境界または画面下境界の画素値をコピーする処理を行う。
【００５５】
図７は，垂直方向コピー部２４の回路構成例を示す。図７において，ＥＤＩ０〜ＥＤＩ２は，３ラインの入力データ０〜３である。ＥＩＵＤＦＬＧは，画面の上側であるか下側であるかを示す上下領域フラグであり，画面外情報として画面外判定部１２から受け取る信号である。このフラグが“００”の場合には画面内であることを示す。ＥＩＹＳＦＴＳＥＬは，入力データＹ方向シフト制御信号であり，入力データを垂直方向（Ｙ方向）へのコピーのためにシフトするかどうかを示す。ＥＩＴＲＧはメモリリードイネーブル信号であり，メモリ３からデータを読み取ったタイミングを示す。
【００５６】
また，ＸＥＩＹＣＰＯ０〜ＸＥＩＹＣＰＯ２は，３ライン分のＹ方向画素コピー処理データ出力０〜２であり，通常の探索では，このうち２ラインのデータが用いられるが，探索範囲の最下ラインから次の探索範囲の最上ラインに移るような場合には，３ラインのデータが出力される。
【００５７】
タイミング生成回路２４１は，読み込みデータ保持回路２０へのデータの保持を制御する回路である。読み込みデータ保持回路２０は，図１で説明したように，先行して読み出した最下ラインのデータを８サイクル分保持し，８サイクルだけ遅延させて出力する。読み込みデータ保持回路２０は，例えば８段のシフトレジスタで構成され，タイミング生成回路２４１のシフトイネーブル信号によって，あらかじめ読んでおいた探索範囲の最下ラインのデータを８サイクル分遅延させる。
【００５８】
垂直方向並び替え部２５は，垂直方向コピー部２４の出力する１画素×３ラインの画素データを並び替えて，ＰＥアレイ部４にデータを出力する。垂直方向並び替え部２５による画素データの並び替えの処理は，ＭＰＥＧ−２等で用いられていた従来の動き探索装置における並び替えの処理と同様である。
【００５９】
図８は，本実施の形態におけるメモリ３からの参照画像データのリードタイミングを示している。
【００６０】
本実施の形態におけるサイクル２４（ＣＬＫ２４）までのデータの読み出し，およびＰＥアレイへのデータの供給タイミングは，図１２で説明した従来の動き探索装置のタイミングと同様である。図１２に示す従来装置では，サイクル２４において，バンク番号が＃０の（０，６）から（６，６）までと，バンク番号＃１の（０，７）から（６，７）までの２ラインの画素データを同時に読み出し，次の８サイクル目のサイクル３２では，最下ラインであるバンク番号が＃２の（０，８）から（６，８）までと，最上ラインのバンク番号が＃０および＃３の（４，０）から（１０，０）までと，次の最上ラインのバンク番号が＃１および＃４の（４，１）から（１０，１）までの合計３ラインの画素データを同時に読み出していた。これは，サイクル３２目以降の読み出しでバンク競合が生じなかったからである。
【００６１】
これに対し，本実施の形態では，従来装置と同じ読み出しタイミングでは特に画面外を探索するときにメモリアクセスが不規則となり，それによってバンク競合が生じることがあるため，次のように読み出す。サイクル２４において，バンク番号が＃０の（０，６）から（６，６）までと，バンク番号＃１の（０，７）から（６，７）までの２ラインの画素データを読み出すと同時に，最下ラインであるバンク番号が＃２の（０，８）から（６，８）までの画素データについて読み出す。この最下ラインの読み出した画素データについては，８サイクル後にＰＥアレイに出力するため，読み込みデータ保持回路２０にデータを保持しておく。
【００６２】
次の８サイクル目のサイクル３２では，メモリ３から最上ラインのバンク番号が＃０および＃３の（４，０）から（１０，０）までと，次の最上ラインのバンク番号が＃１および＃４の（４，１）から（１０，１）までの２ラインの画素データを同時に読み出し，ＰＥアレイに対しては，（４，０）から（１０，０）までの画素データと（０，８）から（６，８）までの画素データとを，各サイクルごとに画素単位で出力していく。サイクル３６になったときには，さらに（４，１）から（１０，１）までのラインの画素データをＰＥアレイに出力していく。
【００６３】
以上のように読み出しのタイミングを変更することによって，最上ラインが画面外の場合で，メモリアクセスが不規則となり，直前の最下ラインのバンクである＃２のバンク読み出しが発生しても，直前の最下ラインはすでに前に読み出しているので，バンク競合が生じることはない。
【００６４】
以上説明した動き探索装置は，ＬＳＩによって構成することができる。
【図面の簡単な説明】
【００６５】
【図１】本発明の概要を説明する図である。
【図２】本実施の形態に係る動き探索装置の全体構成図である。
【図３】メモリリード部の詳細構成図である。
【図４】画素並び替え部の詳細構成図である。
【図５】水平方向コピー部が行う画素値のコピーのし方を説明する図である。
【図６】水平方向コピー部の回路構成例を示す図である。
【図７】垂直方向コピー部の回路構成例を示す図である。
【図８】本実施の形態におけるメモリからの参照画像データのリードタイミングを示す図である。
【図９】従来の動き探索装置におけるＰＥアレイの構成例を示す図である。
【図１０】ＰＥアレイの動作を説明する図である。
【図１１】ＰＥアレイのタイミングチャートを示す図である。
【図１２】参照画像メモリからのリードタイミングを示す図である。
【図１３】動きベクトルを検出する探索範囲を示す図である。
【図１４】メモリバンク構成と画面外画素リード時のバンク競合の問題を説明する図である。
【符号の説明】
【００６６】
１  メモリリード部
２  画素並び替え部
３  メモリ
４  ＰＥアレイ部
５  評価部
６  制御部
１０  競合バンク先行読み出し制御部
１１  論理アドレス生成部
１２  画面外判定部
１３  論理アドレス／実アドレス変換部
１４  メモリアクセス部
２０  読み込みデータ保持回路
２１  水平方向切り出し部
２２  水平方向コピー部
２３  パラレル／シリアル変換部
２４  垂直方向コピー部
２５  垂直方向並び替え部
３０  参照画像メモリ
【図１】
0004695124.tif 000002
【図２】
0004695124.tif 000003
【図３】
0004695124.tif 000004
【図４】
0004695124.tif 000005
【図５】
0004695124.tif 000006
【図６】
0004695124.tif 000007
【図７】
0004695124.tif 000008
【図８】
0004695124.tif 000009
【図９】
0004695124.tif 000010
【図１０】
0004695124.tif 000011
【図１１】
0004695124.tif 000012
【図１２】
0004695124.tif 000013
【図１３】
0004695124.tif 000014
【図１４】
0004695124.tif 000015