(57)【特許請求の範囲】
【請求項１】
最終動きベクトルを生成する方法であって、
画像を表す複数の画素を各々が含んでいる第１画像フレーム及び第２画像フレームを用意するステップと、
前記第１画像フレーム内の探索領域をデシメートして、低減された解像度の探索領域を生成するステップと、
前記第２画像フレーム内の画素ブロックをデシメートして、複数の低減された解像度の画素ブロックを生成するステップと、
前記低減された解像度の画素ブロックを複数含むサブブロックを複数有するメタブロックを生成するステップと、
前記メタブロックと実質的にマッチする画素ブロックを前記低解像度探索領域内で発見する工程を含む広域探索を実行するステップと、
前記メタブロックの位置と前記メタブロックと実質的にマッチする前記第１画像フレーム内の前記画素ブロックの位置との間の隔たりを表す、前記メタブロックに対する推定動きベクトルを計算するステップと、
前記複数のサブブロックの少なくとも一つの位置と前記複数のサブブロックの少なくとも一つと実質的にマッチする前記第１画像フレーム内の画素ブロックの位置との間の隔たりを表す、前記複数のサブブロックの少なくとも一つに対する推定動きベクトルを計算するステップと、
前記第１画像フレームの局所探索を実行して前記第２画像フレームの全解像度マッチング用画素ブロックと実質的にマッチする全解像度画素ブロックを特定するステップであって、前記局所探索は、前記推定動きベクトルの少なくとも一つを利用して前記全解像度画素ブロック用の初期探索開始位置を特定する、ステップと、
前記第１画像フレーム内の前記全解像度画素ブロックの前記位置と前記第２画像フレーム内の前記全解像度マッチング用画素ブロックの前記位置との隔たりを表す最終動きベクトルを算出するステップと、
を備える方法。
【請求項２】
前記メタブロックに対して計算された前記推定動きベクトル、又は、複数の前記サブブロックに対して計算された前記推定動きベクトルの一つを、前記局所探索を実行する前に、前記低減解像度画素ブロックの各々に割り当てるステップを更に備える、請求項１記載の方法。
【請求項３】
前記メタブロックに対して計算された前記推定動きベクトルと、前記サブブロックに対して計算された一又は複数の前記推定動きベクトルとに基づいて求められるベクトルを、前記局所探索を実行する前に、前記低減解像度画素ブロックの各々に割り当てるステップを更に備える、請求項１記載の方法。
【請求項４】
画像を表す複数の画素を各々が含んでいる第１画像フレーム及び第２画像フレームを入力として有する、最終動きベクトルを生成する装置であって、
前記第１画像フレーム内の探索領域をデシメートして、低減された解像度の探索領域を生成し、前記第２画像フレーム内の画素ブロックをデシメートして、複数の低減された解像度の画素ブロックを生成すると共に、前記低減された解像度の画素ブロックを複数含むサブブロックを複数有するメタブロックを生成するピラミッドプロセッサと、 
前記ピラミッドプロセッサに接続され、前記メタブロックと実質的にマッチする画素ブロックを前記低解像度探索領域内で発見する工程を含む広域探索を実行する広域探索手段と、
前記広域探索手段に接続され、前記メタブロックの位置と前記メタブロックと実質的にマッチする前記第１画像フレーム内の前記画素ブロックの位置との間の隔たりを表す、前記メタブロックに対する推定動きベクトルを計算すると共に、前記複数のサブブロックの少なくとも一つの位置と前記複数のサブブロックの少なくとも一つと実質的にマッチする前記第１画像フレーム内の画素ブロックの位置との間の隔たりを表す、前記複数のサブブロックの少なくとも一つに対する推定動きベクトルを計算する手段と、
前記第１画像フレームの局所探索を実行して前記第２画像フレームの全解像度マッチング用画素ブロックと実質的にマッチする全解像度画素ブロックを特定する手段であって、前記局所探索は、前記推定動きベクトルの少なくとも一つを利用して前記全解像度画素ブロック用の初期探索開始位置を特定する手段と、
前記第１画像フレーム内の前記全解像度ブロックの位置と前記第２画像フレーム内の全解像度マッチング用画素ブロックの位置との隔たりを表す前記複数の推定動きベクトルのうちの少なくとも一つに基づいて、最終動きベクトルを算出する手段と、
を備える装置。
【請求項５】
シストリックアレイを更に備えており、前記シストリックアレイは、前記メタブロック内の前記複数のサブブロックに関連する複数のノード出力を加算して複数の推定動きベクトル情報ノードを求めた後、前記複数の推定動きベクトル情報ノードを加算して前記メタブロックの推定動きベクトル情報を求める、請求項４記載の装置。
【請求項６】
前記局所探索を実行する手段は、
前記メタブロックに対して計算された前記推定動きベクトル、又は、複数の前記サブブロックに対して計算された前記推定動きベクトルの一つを、前記局所探索を実行する前に、前記低減解像度画素ブロックの各々に割り当てる手段を更に備える、請求項４記載の装置。
【請求項７】
前記局所探索を実行する手段は、
前記メタブロックに対して計算された前記推定動きベクトルと、前記サブブロックに対して計算された一又は複数の前記推定動きベクトルとに基づいて求められるベクトルを、前記局所探索を実行する前に、前記低減解像度画素ブロックの各々に割り当てる手段を更に備える、請求項４記載の装置。
【請求項８】
ブロックベースの動き推定に付随する計算の複雑さを低減する方法であって、
画像を表す複数の画素を各々が含んでいる第１画像フレーム及び第２画像フレームを用意するステップと、
前記第１画像フレーム内の探索領域をデシメートして、低減された解像度の探索領域を生成するステップと、
前記第２画像フレーム内の画素ブロックをデシメートして、複数の低減された解像度の画素ブロックを生成するステップと、
前記低減された解像度の画素ブロックを複数含むサブブロックを複数有するメタブロックを生成するステップと、
前記メタブロックと実質的にマッチする画素ブロックを前記低解像度探索領域内で発見する工程を含む広域探索を実行するステップと、
前記メタブロックの位置と前記メタブロックと実質的にマッチする前記第１画像フレーム内の前記画素ブロックの位置との間の隔たりを表す、前記メタブロックに対する推定動きベクトルを計算するステップと、
前記サブブロックの少なくとも一つの位置と前記サブブロックの少なくとも一つと実質的にマッチする前記第１画像フレーム内の画素ブロックの位置との間の隔たりを表す、前記複数のサブブロックの少なくとも一つに対する推定動きベクトルを計算するステップと、
前記第１画像フレームの局所探索を実行して前記第２画像フレームの全解像度マッチング用画素ブロックと実質的にマッチする全解像度画素ブロックを特定するステップであって、前記局所探索は、前記推定動きベクトルの少なくとも一つを利用して前記全解像度画素ブロック用の初期探索開始位置を特定する、ステップと、
を備える方法。
【請求項９】
ブロックベースの動き推定に付随する計算の複雑さを低減する装置であって、
前記第１画像フレーム内の探索領域をデシメートして、低減された解像度の探索領域を生成し、前記第２画像フレーム内の画素ブロックをデシメートして、複数の低減された解像度の画素ブロックを生成すると共に、前記低減された解像度の画素ブロックを複数含むサブブロックを複数有するメタブロックを生成するピラミッドプロセッサと、
前記ピラミッドプロセッサに接続され、前記メタブロックと実質的にマッチする画素ブロックを前記低解像度探索領域内で発見する工程を含む広域探索を実行する広域探索システムと、
前記広域探索システムに接続されており、初期探索開始位置における全解像度画素ブロックを特定して、前記第２画像フレームの全解像度マッチング用画素ブロックと実質的にマッチする前記第１画像フレームの全解像度画素ブロックを更に特定する局所探索システムと、
を備える装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、画像シーケンスを符号化するシステムに関し、特に、ブロックベースの動き推定のために動きベクトルを決定する際の計算の複雑さを低減する装置及びその付随方法に関する。
【背景技術】
【０００２】
ビデオ画像シーケンス等の画像シーケンスは、通常、一連の画像フレームを含んでいる。動く物体を含むビデオの再生には、１メガバイトを超える情報を含む場合もある各フレームについて、通常、毎秒３０画像フレームのフレーム速度が必要となる。この結果、このような画像シーケンスを伝送したり記憶したりするには、大きな送信帯域幅や記憶容量が必要となる。必要な送信帯域幅又は記憶容量を低減するため、フレームシーケンス内の冗長情報が記憶又は送信されないようにシーケンスが圧縮される。このため、種々の符号化技術による画像シーケンス圧縮は、近年の膨大な研究の対象となっている。テレビジョン、ビデオ会議及びCD-ROMアーカイビングは、ビデオシーケンス符号化によって利益が得られる用途である。
【０００３】
一般に、画像シーケンスを符号化するために、一つのフレームから次のフレームへのシーン中の物体の動きに関する情報が、符号化処理において重要な役割を果たす。ほとんどの画像シーケンスにおける連続フレーム間に存在する高い冗長性のため、動き推定として知られる技術を用いることにより、実質的なデータ圧縮を達成することができる。例えば、シーケンス中に動きがない場合、シーケンス中の各フレームは、そのシーケンス中の前のフレームと同一である。従って、冗長フレームは、記憶又は送信すべきでない。このため、例えば受信機は、前に受信したフレームを単に繰り返して、シーケンス中の各フレームを受信する必要なしに一連の同一フレームを再生することができる。この動きのない例は、ビデオシーケンスの連続フレーム間の冗長性を活用して前のフレームを用いて新たなフレームを予測することができる最も単純な例である。
【０００４】
しかし、一般的には、画像シーケンス中の一つのフレームから次のフレームには、少なくともある程度の動きがある。動きを含むシーケンスでは、直前のフレーム、及び現在のフレームと直前のフレームとの差を表す情報、を用いることにより、現在のフレームを再構成することができる。例えば、単純な画像シーケンス送信システムにおいて、送信機では、現フレームを前フレームと比較して動き情報、即ち二つのフレーム間の差を求めている。この後、送信機は、前フレーム及び動き情報を受信機に送信する。受信機では、前フレームを動き情報と組み合わせることによって、現フレームが再構成される。この結果、二つの完全なフレームではなく、１フレームと差情報のみが送信及び受信される。必要な帯域幅を更に低減するために、種々の副サンプリング技術を用いて参照フレーム（例えば、前フレーム）を圧縮することができる。ビデオ会議、ビデオ電話、及びディジタルテレビジョン等の用途では、動き情報がデータ圧縮の鍵となっている。しかしながら、フレームシーケンスからの動き情報の抽出は、膨大な計算を必要としており、動き推定タスクを実行するように設計されたハードウェアに重い負担を課すことになる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
多くのシステムでは、いわゆるブロックベースアプローチを用いて動き情報を求めている。種々のブロックベースアプローチの例は、１９９０年５月８日発行の米国特許第４９２４３１０号や、１９９２年４月１４日発行の第５１０５２７１号や、１９９３年５月１１日発行の第５２１０６０５号に記載されている。単純なブロックベースアプローチでは、現フレームは複数の画素ブロック（以下では、現ブロックと呼ぶ）に分割される。これらの現ブロックの各々について、前フレーム中の選択探索領域内で、現ブロックと「最も良く」マッチする画素ブロックの探索が行われる。この探索は、通常、選択された現ブロックと前フレームの選択探索領域中の同様の大きさの画素ブロックとを繰り返し比較することにより行われる。ブロックマッチが発見されれば、現フレーム内の現ブロックの位置に対する前フレーム内の探索領域中のマッチングブロックの位置が、動きベクトルを定めることになる。このアプローチ、即ち各現ブロックを選択探索領域全体と比較するアプローチは、全探索アプローチ（full search approach）又は全数探索アプローチ（exhaustive search approach）として知られている。全探索アプローチによる動きベクトルの導出は、膨大な計算を必要とする。このため、このようなシステムは、フレーム処理が比較的遅くなりがちであり、製造費用も高かった。
【０００６】
従って、この技術分野では、この技術分野で現在存在するものよりも計算量の少ないブロック動き推定装置及びその付随方法が必要とされている。
【課題を解決するための手段】
【０００７】
本発明は、計算に効果のある方法で動きベクトルを求める広域−局所ブロック動き推定装置及びその付随方法を提供することにより従来技術の欠点を克服している。具体的には、本発明は、二つのステップからなる処理を用いる。第１のステップでは、複数の推定動きベクトルを生成し、第２のステップでは、これらの推定動きベクトルを洗練して最終的な動きベクトルにする。第１ステップは、本装置が一連の低解像度フレームを生成するように、一連の画像フレームをフィルタリング及びデシメート（decimate）することによって行われる。各低解像度フレームは、複数の画素ブロックに区分（パーティショニング）されている。これらの連続的な低解像度フレームを用いることにより、本装置は、全数探索（以下では、広域探索と呼ぶ）を実行して推定動きベクトルを生成する。
【０００８】
具体的に述べると、二つの選択された低解像度フレーム（現フレームと前フレーム）内において、本装置は、複数の現画素ブロック及び複数の前画素ブロックを定める。これらの前ブロックは、現ブロックよりも多数の画素を有する個別探索領域である。本装置は、処理のために１個の現ブロック及び１個の前ブロックを選択する。選択された現ブロックは、この後、全数探索法を用いて選択探索領域と比較される。この比較は、この探索領域内のある画素ブロックが現ブロックと実質的にマッチしていることが分かるまで行われる。前フレーム中のマッチングブロックの位置と現フレーム中の現ブロックの位置との間の隔たりが、推定動きベクトルを定める。この探索処理は、本装置が各現ブロックについて推定動きベクトルを定めるまで、各現ブロックに対して繰り返される。この探索は低減（低）解像度画像に対して行われるため、この探索は比較的迅速に行われる。
【０００９】
推定動きベクトルが計算されると、本装置は、動きベクトルを推定するために使用した低解像度フレームに対応する全解像度フレームシーケンスの中から前フレーム及び現フレームを選択する。これらの連続した全解像度フレームと推定動きベクトルを用いることにより、本装置は、修正全数探索（以下では、局所探索と呼ぶ）を実行して最終的な動きベクトルを生成する。具体的に述べると、これらの全解像度フレームでは、本装置は、これらのフレームを複数の前画素ブロック及び現画素ブロックに区分する。全解像度フレーム内のこれらのブロックは、低解像度フレーム内の同じブロックに対応している。このため、この前ブロックは、現ブロックよりも大きなサイズを有する探索領域を形成している。本装置は、この探索領域を探索して、現ブロックとこの探索領域との間のマッチを求める。しかしながら、与えられた低解像度現ブロックについての推定動きベクトルは、全解像度探索領域内の全解像度現ブロックについての初期探索開始位置を与える。このため、全解像度探索領域内で全数探索を実行することなしにマッチが迅速に発見される。
【００１０】
広域探索の雑音余裕度を改善するために、低解像度現ブロックは、メタブロックとして形成される。これらのメタブロックは、一群の近接低解像度現ブロックによって形成される。通常、これらのメタブロックは、複数のサブブロックに区分されている。ここで、各サブブロックは、複数の現ブロックを含んでいる。このメタブロックは、個々の現ブロックの代わりに広域探索で使用される。低解像度探索領域内の画素を伴うメタブロックについてマッチが発見されると、メタブロック全体についての動きベクトルとともに、メタブロック内の各サブブロックについても動きベクトルが計算される。本装置は、メタブロックを構成する現ブロックの各々に推定動きベクトルを割り当てる。これらの動きベクトルは、現ブロックを含むサブブロックの動きベクトル、メタブロック全体に対応づけられた動きベクトル、又はサブブロック動きベクトルとメタブロック動きベクトルとの組み合わせ、のいずれかから選択される。推定動きベクトルが現ブロックに割り当てられると、上述の局所探索が完了する。
【発明の効果】
【００１１】
本発明によれば、計算量の少ないブロック動き推定装置及び方法が提供される。
【発明を実施するための最良の形態】
【００１２】
理解の容易のため、図に共通の同一要素を表すために可能な限り同一の参照番号が使用されている。
図１は、本発明の好適な実施形態のブロック図を表している。本発明の広域−局所動き推定システムは、ピラミッドプロセッサ１０２、広域探索システム１０４、及び局所探索システム１０６を含んでいる。具体的に述べると、一連の画像フレームは、リード１０８で、動き推定システム１００への入力を形成している。この画像シーケンスは、ピラミッドプロセッサ１０２及び局所探索システム１０６の双方への入力である。一般に、ピラミッドプロセッサ１０２は、入力に到達したフレームとして各画像フレームをフィルタリング（フィルタ１１２）、及びデシメート（画像デシメータ（image decimator）１１４）して、一連の低減された解像度の画像フレームを生成する。広域探索システム１０４は、これらの低減解像度フレームを解析して、複数の推定動きベクトルを生成する。最後に、局所探索システム１０６は、これらの推定動きベクトルを用いて入力シーケンスのフレームを解析し、複数の最終動きベクトルを生成する。これらの最終動きベクトルは、この後、ビデオ処理システム（図示せず）が画像フレーム内のビデオ情報を圧縮するために使用することができる。
【００１３】
更に詳しく述べると、ピラミッドプロセッサ１０２において、フィルタ１１２は、通常、ガウスフィルタである。このガウスフィルタは、フレーム中で近接する画素値を用いて加重和処理を実行する。フィルタリングされた画素は、入力画素の正規化加重和である。この加重和が近接画素から受ける寄与は、遠くの近接画素ほど少なくなっている。画像デシメータ１１４は、一般的な画素副サンプリング回路である。ピラミッドプロセッサの出力は、一連の画像フレームである。
【００１４】
ここで、各フレームは、対応する入力フレームよりも低い解像度を有している。例を挙げると、デシメータ１１４は、与えられた正方形領域内の画素数を１／６４に低減する８倍デシメータである。以下では、ピラミッドプロセッサ１０２によって生成されるフレームを、低解像度フレームと呼ぶことにする。
【００１５】
広域探索システム１０４は、２つの連続した低解像度フレームを比較して、これらの低解像度画像について推定動きベクトルを求める。具体的に述べると、これらの低解像度フレームは、現フレームが複数の現ブロックを含み、前フレームが複数の前ブロックを含むように、複数の画素からなる複数のブロックに区分（パーティショニング）されている。これらの前ブロックは、現ブロックよりも多数の画素を含んでいる。例えば、各現ブロックは２画素×２画素であり、各前ブロックは３２画素×３２画素である。各現ブロックは、マッチが発見されるまで、選択された前ブロックと繰り返し比較される。例えば、現ブロック中の４画素は、前ブロック中の１０２４画素のうちの４画素と比較され、この後、これら４個の現ブロック画素が動かされ、再度、比較される、という処理が繰り返される。このため、低解像度探索領域では、本システムは、全数探索（exhaustivesearch）を実行する。以下では、この探索を、広域探索と呼ぶことにする。最も低い算出誤差を生成するブロックが、マッチとなる。この他に、算出誤差が所定の誤差しきい値よりも小さいときに、本ルーチンは、マッチを発見したとみなす。
【００１６】
マッチが発見されると、低解像度現フレーム中の現ブロックの位置と現ブロックとマッチする前ブロック中の画素ブロックの位置との差が、推定動きベクトルを決定する。この処理は、低解像度現フレーム中の各現ブロックについて動きベクトルが計算されるまで、各現ブロックについて繰り返される。これらの推定動きベクトルは、ライン１１０を介して局所探索システムに送られる。
【００１７】
局所探索システム１０６は、入力フレームシーケンス中の二つの連続した全解像度フレーム内の画素を用いて修正を加えた全数探索（以下では局所探索と呼ぶ）を実行する。これら二つのフレームは、ピラミッドプロセッサ１０２によって以前にデシメートされ、かつ、広域探索システム１０４によって比較された二つのフレームに相当している。この局所探索システムは、現在及び前の全解像度フレームを複数の現画素ブロック及び複数の前画素ブロックに区分する。現ブロックは、前ブロックよりも少ない画素を含んでいる。例えば、各現ブロックは、１６画素×１６画素の領域を含んでおり、各前ブロックは、２５６画素×２５６画素の領域を含んでいる。この局所探索システムは、広域探索システムによって供給される推定動きベクトルを用いて比較を開始する。このため、この比較は、全解像度フレーム内において、最適なマッチ位置に極めて近い対応前ブロック内に現ブロックを配置する位置で開始される。この現ブロックは、通常、マッチが発見されるまで、わずかな移動量しか必要としない。このため、推定動きベクトルを用いることにより、この局所探索は、一般的な全数探索よりも極めて高速となる。このシステムの出力は、入力フレームシーケンス中の一つのフレームから次のフレームへの動きを表す一連の最終動きベクトルである。この他に、本システムは、全解像度前フレーム内のマッチド画素ブロックを出力して、画像処理システムによってこれらのマッチド画素を更に処理できるようにしても良い。
【００１８】
図２Ａ及び図２Ｂは、図１に示されるシステムの動作を示すルーチンのフローチャートの前半および後半をそれぞれ表している。図３は、現在及び前の全解像度及び低解像度画像の双方の図を表している。本発明の動作を良く理解するためには、図２Ａ、図２Ｂ及び図３を同時に参照されたい。
【００１９】
ステップ２００において、本システムに全解像度フレームシーケンスが入力される。図３では、全解像度フレームシーケンスは、フレーム３００（前フレーム）及び３０２（現フレーム）で表されている。図２Ａのステップ２０２では、各フレームがフィルタリングされる。これは、通常、ガウスフィルタを用いて行われる。この後、ステップ２０４では、各フレームがデシメートされ、低解像度フレームが生成される。これらの低解像度フレームは、フレーム３０４（前の低解像度フレーム）及び３０６（現在の低解像度フレーム）として表されている。ステップ２０６において、このルーチンは、一つの低解像度現フレーム３０６及び一つの低解像度前フレーム３０４を選択する。ここで選択されたフレームは、ステップ２０８で、複数の画素ブロックに区分される。すなわち、現ブロック及び前ブロックが定められる。ステップ２１０では、このルーチンは、一つの現ブロック３０８及び対応する一つの前ブロック３１０を選択する。この対応前ブロックは、現ブロックとのマッチの探索が行われる探索領域を定める。ステップ２１２では、現ブロックと前ブロックとが比較される（図３では矢印３１２で表されている）。本ルーチンは、ステップ２１４で、マッチが発見されたかどうかを照会する。ステップ２１４の照会に対する答えが否定的である場合、このルーチンは、否定経路に沿ってステップ２１６に進む。ステップ２１６において、このルーチンは、前ブロック内に現ブロックを再配置してからステップ２１２に戻り、ここでもう一度比較が行われる。このルーチンは、ステップ２１４で実質的なマッチが発見されるまで、ステップ２１６を通ってループする。マッチ判定を行う技術の一例では、広域探索システムによって実行される種々の画素比較のために最小二乗誤差又は平均絶対誤差を算出する。最低の算出誤差を生成するブロックが、マッチということになる。この他に、算出誤差が所定の誤差しきい値よりも小さいときに、このルーチンは、マッチが発見されたものとみなす。この後、このルーチンは、ステップ２１８で、現在処理されている現ブロックについて推定動きベクトルを求める。動きベクトルが算出されると、このルーチンは、ステップ２２０で、全ての現ブロックが自己に関する動きベクトルを有するかどうかを照会する。その答えが否定的である場合は、このルーチンは、否定経路２２０に沿ってステップ２１０に進む。ステップ２１０では、別の現ブロック及び対応前ブロックが選択された後、推定動きベクトルを求めるための処理（広域探索）が行われる。ステップ２２０での照会に対する答えが肯定的である場合、このルーチンは、ステップ２２４に進む。この時点で、このルーチンは、低解像度現フレーム中の現ブロックの各々に関する一組の推定動きベクトルを算出したことになる。
【００２０】
図２Ｂに示されるステップ２２４において、このルーチンは、一つの現フレーム３０２及び一つの前フレーム３００を全解像度入力シーケンスから選択する。この現フレーム及び前フレームは、現在利用可能な一組の推定動きベクトルを求めるために使用された現在及び前の低解像度フレーム３０６及び３０４に対応している。選択されたこれらの入力フレームは、ステップ２２６で、複数の現ブロック及び前ブロックに区分される。重要なことに、これらの現ブロック及び前ブロックは、フレーム中の位置に関して、低解像度フレームから導出された現ブロック及び前ブロックに対応している。このため、全解像度フレーム中に与えられた任意の現ブロック又は前ブロックは、低解像度フレーム中に低解像度の等価物を有している。
【００２１】
ステップ２２８では、このルーチンは、全解像度フレームから一つの現ブロック３１４及び対応する一つの前ブロック３１６を選択する。この対応前ブロックは、現ブロックとのマッチの探索が行われる探索領域を定める。ステップ２３０では、推定動きベクトルを使用して、前ブロック３１６によって定められた探索領域内で現ブロック３１４を初期配置する（図３では矢印３１８で表されている）。この推定動きベクトルは、全解像度フレーム３０２内の現ブロック３１４に対応する低解像度フレーム内の現ブロック３０８に関連づけられたベクトルである。ステップ２３２では、現ブロックと前ブロックとが比較される（図３では矢印３２０で表されている）。このルーチンは、ステップ２３４で、実質的なマッチが発見されたかどうかを照会する。この局所探索システムは、最小二乗誤差技術又は平均絶対誤差技術を用いて全数探索を実行し、ブロック間での“最適な”マッチを求める。現ブロックの初期位置が広域探索システムによって推定されるため、局所探索に必要な探索範囲は、通常、２〜４画素だけである。ステップ２３２での照会に対する答えが否定的である場合、このルーチンは、否定経路に沿ってステップ２３６に進む。ステップ２３６において、このルーチンは、前ブロック３１６内に現ブロック３１４を再配置してからステップ２３２に戻り、ここでもう一度比較が行われる。このルーチンは、ステップ２３４でマッチが発見されるまで、ステップ２３６を通ってループする。この後、このルーチンは、ステップ２３８において、現在処理されている現ブロックに関する最終動きベクトルを決定する。最終動きベクトルが算出されると、このルーチンは、ステップ２４０で、全ての現ブロックが自己に関する最終動きベクトルを有するかどうかを照会する。この照会に対する答えが否定的である場合、このルーチンは、否定経路２４２に沿ってステップ２２８に進む。ステップ２２８では、別の現ブロック及び対応する現ブロックが選択された後、動きベクトルを決定するための処理が行われる。ステップ２４０での照会の答えが肯定的である場合、このルーチンは、ステップ２４４でステップする。
【００２２】
簡単のため、図示の前ブロック３１０及び３１６は、図３において、それぞれ２５６×２５６画素及び３２×３２画素を含んでいるものとして表されている。
【００２３】
しかしながら、実際には、これらの探索領域は、この探索領域内での現ブロック３１４及び３０８の移動を許容するために、更に１行及び１列ずつ必要とする。従って、実際には、これらの探索領域の寸法は、各次元において、それぞれ、２５６＋１画素に対応現ブロックの長さ（１６画素）を加えたもの、及び３２＋１画素に対応現ブロックの長さ（２画素）を加えたものとなる。
【００２４】
前述のように、低解像度現ブロック３０８は、２×２画素領域をカバーしている。従って、このブロックは、４個の画素しか含まない。このため、４個の画素しか含まない現ブロックを用いて広域探索システムにより行われる比較は、満足できない結果を生むことになる可能性もある。具体的には、現ブロック中の少数の画素はノイズと相関しやすいため、偽のマッチが広域探索システムによって検出されることがある。
【００２５】
従って、この広域−局所ブロック動き推定システムでは、単一の低解像度現ブロックを用いる代わりに、図４に示されるメタブロック４００をなすように整列された複数の現ブロックＢ0,0〜Ｂn,nを用いることができる。動き推定システムの好適な実施形態では、メタブロック４０２が１６個の現ブロックＢ0,0〜Ｂ3,3から形成されている。具体的には、メタブロック４０２中の各現ブロックＢ0,0〜Ｂ3,3は、全解像度現フレーム内のデシメートされていない１６×１６領域に対応する２×２行列に整列された４個の画素を含んでいる。
【００２６】
図５には、複数の異なるテストパーティション（サブブロックとも呼ばれる）に分割されたメタブロック５００が示されている。例えば、メタブロックは、２個のテストパーティション５０４及び５０６を有するメタブロック５００を形成するように垂直に半分に分割されていても良い。ここで、各テストパーティションは、現ブロックの４行と２列を含んでいる。また、メタブロックは、２個のテストパーティション５０８及び５１０を有するメタブロック５０２を形成するように水平に半分に分割されていても良い。ここで、各テストパーティションは、現ブロックの２行と４列を含んでいる。このブロック動き推定システムでは、メタブロックを他の任意の都合の良い数のテストパーティションに分割することもできる。例えば、４分の１ずつに分割して、メタブロック５１４内でテストパーティション５１２ａ〜ｄを形成したり、メタブロック５２４内で重なり合うテストパーティション５１６、５１８、５２０、５２２に分割して良い。
【００２７】
図６には、広域探索を実行する際のメタブロックの使用を説明する画像処理図６００が示されている。この画像処理図６００では、低解像度前フレーム３０４及び低解像度現フレーム３０６が、前述したように、フィルタ及びデシメータによって前入力フレーム３００及び現入力フレーム３０２に対してそれぞれ実行されるデシメーション処理の結果である。これも前述したことであるが、低解像度前ブロック３１０は、低解像度フレーム３０４内に配置される。低解像度現ブロックＢ0,0〜Ｂ3,3を含むメタブロック５００は、低解像度フレーム３０６内に配置される。メタブロックを使用するときは、広域探索システムは、各メタブロック内の各現ブロックＢ0,0〜Ｂ3,3について推定動きベクトルを決定する。
【００２８】
図示の６４×６４画素の全解像度メタブロック６０２は、現入力フレーム３０２内に配置されており、１６個の現ブロックＢ0,0′〜Ｂ3,3′を含んでいる。これらの現ブロックは、それぞれ１６×１６画素の全解像度現ブロックを有している。事実上、メタブロック６０２内の各テストブロックＢ′i,jは、対応する低解像度現ブロックＢi,jをメタブロック５００内に与えるようにデシメータによって処理される。このため、各Ｂ′i,jは、Ｂi,jに対応している。現全解像度フレーム３０２は、図示のメタブロック６０２等の複数のメタブロックでカバーされる。フレーム３０２内の複数のメタブロック６０２は、相互に重なり合わない。この複数のメタブロックの各６４×６４画素メタブロック６０２は、メタブロック５００等の８×８低解像度メタブロックに対応している。
【００２９】
最適なマッチ情報を得るため、メタブロック５００は、広域探索を用いて、広域探索システムにより低解像度前ブロック３１０（低解像度探索領域）と比較される。この比較は、矢印３１２で表されている。この方法では、広域探索システムは、メタブロック５００の全体について動きベクトル情報を求める。更に、メタブロック５００内のテストブロックＢ0,0〜Ｂ3,3の各々について、推定動きベクトル情報が求められる。
【００３０】
例えば、各テストブロックＢ0,0〜Ｂ3,3には、メタブロック５００全体について広域探索システムによって求められた動きベクトル情報が単純に割り当てられる。これにより、ブロック動き推定システムの動作が大きく単純化される。しかしながら、この方法では、メタブロックのサイズが大きいことから異なる方向へ動く多数の物体をカバーしてしまうため、ブロック動き推定の精度が比較的低く、画質が悪くなってしまう。
【００３１】
動きベクトル推定の精度を高めるため、本システムは、メタブロック５００の各パーティション（サブブロック）について推定動きベクトルを求める。例えば、メタブロック５００は、図５に示されるようなメタブロック５１４を形成するように区分されていても良い。この場合、各マッチ位置で５個の推定動きベクトルが求められる。具体的に述べると、一つの動きベクトルは、メタブロック５１４の全体について求められ、また、４個のテストパーティション５１２ａ〜ｄの各々について一つずつ動きベクトルが求められる。メタブロックがメタブロック５２４を形成するように区分されている場合は、一つの動きベクトルは、メタブロック５２４の全体について求められ、また、４個の重なりテストパーティション５１６、５１８、５２０及び５２２の各々について一つずつ動きベクトルが求められる。これらのメタブロックの各々において、各パーティションについての推定動きベクトルは、その連続した複数の現ブロックに割り当てられる。しかしながら、複数のテストパーティションが特定の現ブロックと重なっていると、これらの動きベクトルのいずれか一つがその現ブロックに対して選択されるか、或いはこれらの動きベクトルが、その現ブロックを表すように任意の方法で単一のベクトルに合成される。このような合成は、平均化や重み付き平均化等によって行うことができる。
【００３２】
一般に、メタブロックを配置し、推定動きベクトル情報を各パーティションについて求め、各パーティションについての動きベクトル情報をそのパーティション内のブロックＢ0,0〜Ｂ3,3に割り当てることによって、画質を高めることができる。また、メタブロックを多数のパーティションに分割することによって、画質を更に高めることができる。しかし、メタブロックが複数の２×２画素ブロックに区分されている場合、この２×２画素ブロックに関して既に説明したような劣悪な結果となってしまう。従って、合理的なパーティショニング・トレードオフは、雑音に対する抵抗、偽マッチ、必要とされるハードウェアの量、雑音余裕度、計算処理強度等の要因を考慮に入れることにより形成される。
【００３３】
前述のように、区分されたメタブロックを低解像度フレームの探索に使用することにより、複数の推定動きベクトル、すなわちメタブロック全体についての一つのベクトル及び各区分領域についてのベクトルが生成される。これらのベクトルは、メタブロック及びその構成要素についての最適なマッチを算出するために、最小二乗誤差等の技術を用いて求められる。これらの推定ベクトルは、この後、経路３１８で図示されるように、局所探索システムに送られる。
【００３４】
このように、２パーティションのメタブロック、例えばメタブロック５００を想定すると、局所探索システムは、広域探索システムによって最小二乗誤差マッチが発見された３個の候補位置を解析しなければならない。これらの３個の位置は、低解像度メタブロックの全体、及びその内部の２個のパーティションの各々に対応している。従って、局所探索システムの探索を実行するためには、各局所テストブロックＢ0,0′〜Ｂ3,3′について三つの可能性の中から一つを選択しなければならない。
【００３５】
三つの可能性の中の一つは、各低解像度現ブロックＢ0,0〜Ｂ3,3についてすぐに除去することができる。これは、各ブロックＢ0,0〜Ｂ3,3が、テストパーティション５０４及び５０６の一方の外側にあるためである。例えば、テストブロックＢ0,0についての開始位置を選択するとき、テストブロックＢ0,0はテストパーティション５０６の内側には配置されないため、テストパーティション５０６についての推定動きベクトルに対応する候補探索位置は無視することができる。メタブロック５００の全体及びテストパーティション５０４に対応する候補探索位置しか考慮しなくて良い。
【００３６】
この方法では、動きベクトルは、各ブロックＢ0,0′〜Ｂ3,3′について、２×２画素ブロックＢ0,0〜Ｂ3,3の一つ一つに基づいて選択されるのではなく、メタブロック５００の全体、又はテストパーティション５０４、５０６の一方、のいずれかに基づいて選択される。メタブロック５００及びテストパーティション５０４、５０６は２×２ブロックＢ0,0〜Ｂ3,3よりも相当に大きいことから、２×２テストブロックが低解像度探索領域内の小さなビットパターンとランダムにマッチしやすくなっているため、この広域−局所ブロック動き推定システムは、雑音に対してより大きな抵抗を有する。
【００３７】
最終的な動きベクトルの選択は、矢印６０４及び６０６で示されるように、二つの可能性のある開始位置の双方について全解像度ブロックＢ′i,jの最適なマッチを求めることにより行われる。これには、メタブロック５００の全体に対応する推定動きベクトルか、或いは適切なテストパーティション５０４及び５０６に対応する推定動きベクトル、のいずれかを選択することが含まれている。探索領域３１６内の二つの可能性のある開始位置の一方が選択されると、局所探索システムは、前述したようにして探索を実行する。
【００３８】
動き推定システムの他の実施形態では、二つの可能性のある候補探索開始位置の各々について全探索を実行し、二つの局所探索結果を提供することも可能である。二つの局所探索結果のうち好適な方を用いて、動きベクトルを生成すると良い。この方法は、単一の推定動きベクトルを選択してこの選択された動きベクトルに従って単一の探索を実行する場合よりも効果が薄いものと思われる。
【００３９】
図７には、８×８のシストリックアレイ（systolic array）７００が示されている。このシストリックアレイ１３０は、広域−局所ブロック動き推定システム内でメタブロックの動きベクトル情報及びメタブロック内の種々のテストパーティションの各々の動きベクトル情報を同時に求めるために使用することが可能な一般的なシストリックアレイである。このシストリックアレイ７００はこのような導出を行うための便利な方法を提供するが、メタブロックを分割することにより形成することができる種々の可能なパーティションの動きベクトル情報を、動きベクトル情報を求めるための任意の公知方法を使用して求めることもできる。
【００４０】
シストリックアレイ７００は、一般的なシストリックアレイである。このアレイでは、各ノードＮi,jがアレイ入力又はノード出力のいずれかからノード入力を受け取り、ノード演算処理を実行して、ノード出力をアレイ出力又は別のノードの入力に与えるようになっている。従って、広域探索システムの比較によって求められた差分がこのシストリックアレイに与えられれば、推定動きベクトル情報を計算することができる。特に、低解像度メタブロック５００内の種々のテストパーティションについての推定動きベクトル情報は、容易に求めることができる。シストリックアレイのこの処理は、コンピュータ又は別個のハードウェア演算回路によって実行されるプログラム命令によって行うことができる。
【００４１】
メタブロック５００では、シストリックアレイのノードＮ4,4の出力とＮ8,4の出力とを加算することにより、テストパーティション５０４についての推定動きベクトル情報が得られる。テストパーティション５０６についての推定動きベクトル情報は、シストリックアレイのノードＮ4,8の出力とＮ8,8の出力とを加算することによって得られる。メタブロック５００全体についての推定動きベクトル情報は、動きベクトル情報ノードＮ4,4、Ｎ4,8、Ｎ8,4及びＮ8,8の各出力を加算することによって得られる。
【００４２】
同様に、メタブロック５０２のテストパーティション５０８及び５１０についても、シストリックアレイの推定動きベクトル情報ノードＮ4,4＋Ｎ4,8とＮ8,4＋Ｎ8,8とが加算される。テストメタブロック５１４では、推定動きベクトル情報ノードＮ4,4がテストパーティション５１２ａに対応しており、推定動きベクトル情報ノードＮ4,8は、テストパーティション５１２ｂに対応しており、推定動きベクトル情報ノードＮ8,4は、テストパーティション５１２ｃに対応しており、推定動きベクトル情報ノードＮ8,8は、テストパーティション５１２ｄに対応している。
【００４３】
当業者は、広範な発明概念から逸脱することなく上述の実施形態に変形を加えることが可能である。従って、本発明は、ここで開示された特定の実施形態に限定されるわけではなく、添付の請求の範囲によって画定される発明の趣旨と範囲内で変形例をカバーすることが意図されている。
【図面の簡単な説明】
【００４４】
【図１】本発明の広域−局所ブロック動き推定システムのブロック図である。
【図２Ａ】図１に示されるシステムの動作を示すフローチャートである。
【図２Ｂ】図１に示されるシステムの動作を示すフローチャートである。
【図３】図１の動き推定システムによって処理される一連の画像の図である。
【図４】図１の動き推定システムの他の実施形態で処理される画素のメタブロックの図である。
【図５】図１の動き推定システムの他の実施形態で処理される画素のメタブロックの図である。
【図６】図１の動き推定システムの他の実施形態で処理される一連の画像の図である。
【図７】図１のブロック動き推定システムの他の実施形態で図５のメタブロック内のサブブロックの動きベクトル情報を求めるために用いるシストリックアレイの図である。
【符号の説明】
【００４５】
１００…推定システム、１０２…ピラミッドプロセッサ、１０…広域探索システム、１０６…局所探索システム、１０８…リード、１１０…ライン、１１２…フィルタ、１１４…デシメータ、１１４…画像デシメータ、１３０…シストリックアレイ、３００…前フレーム、３０２…現フレーム、３０４…前の低解像度フレーム、３０６…現在の低解像度フレーム、３０８…低解像度現ブロック、３１０…低解像度前ブロック（低減解像度探索領域）、３１６…探索領域、４００，４０２，５００…メタブロック、５００…低解像度メタブロック、５０２…メタブロック、５０４，５０６，５０８…テストパーティション、５１２ａ−ｄ…テストパーティション、６００…画像処理図、６０２…メタブロック、６０２…画素メタブロック、６０２…全解像度メタブロック、７００…シストリックアレイ。
【図１】
0004444252.tif 000002
【図２Ａ】
0004444252.tif 000003
【図２Ｂ】
0004444252.tif 000004
【図３】
0004444252.tif 000005
【図４】
0004444252.tif 000006
【図５】
0004444252.tif 000007
【図６】
0004444252.tif 000008
【図７】
0004444252.tif 000009