(57)【特許請求の範囲】
【請求項１】
ブロックマッチングにより動き検出を行う動き補償予測型動画像符号化装置の動き検出装置であって、
入力画像を複数の画素からなるブロックに分割し、
前記ブロックに対し、画素値を表すビットの上位ビットからなる低解像度ブロックを生成し、
現画面の低解像度ブロックと前画面の低解像度ブロックの各画素間の差分を計算する複数の演算器からなる第１の演算器群を備え、該第１の演算器群の各演算器は前記画素値を表すビットの上位ビット数の計算精度で構成し、
動き検出は、第１段階として該第１の演算器群を用いて検索範囲内の低解像度ブロックのうちから差分の最も小さいブロックを検索し、
第２段階として該第１の演算器群を複数個使用し、該第１の演算器群の演算器の計算精度を前記使用した複数個の演算器の個数倍にした演算精度で行うように該第１の演算器群を複数個組み合わせた第２の演算器群を構成し、
該第１段階で検索したブロックを含むその周辺の領域に対してブロック内の画素の画素値を表すビット全体に対し第２の演算器群を用い演算を行うことで差分の最も小さいブロックを検索するように構成した動画像符号化装置の動き検出装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は動き補償予測を行う動画像符号化装置の動き検出装置に関する。
【０００２】
Ｈ２６１やＭＰＥＧ−１，ＭＰＥＧ−２といった最近の国際標準動画像符号化方式では、動きをブロックマッチングで検出するフレ−ム間動き補償予測が採用されている。図５はこの動き検出のためのブロックマッチングの概念を説明する図である。図示するように、現画面中の画素のブロックを前画面中の所定の検索範囲内の複数のブロックと比較して両者の各画素値の差分合計値が最も少ないブロックを検索し、その検索したブロックが前画面から現画面のブロックに移動したとして動きを検出するものである。
【０００３】
ここで、実用的な、すなわち効果のある動き補償予測を行うためには、探索範囲をある程度広くすることが必要であるが、これに伴って演算量と画像メモリからのデ−タ読出しが膨大なものとなる。
【０００４】
具体的な数値をあげると、たとえば１画面のサイズを７２０画素×４８０ライン、フレ−ム周波数を３０Ｈｚ、１画素あたりの値（輝度値）を８ビット、マッチングを行うブロックサイズを１６画素×１６ライン、探索範囲をそれぞれ上下１５ライン、左右１５画素とした場合、
ブロック数は  ７２０×４８０  ×３０÷（１６  ×１６）  ＝４０，５００  ブロック／秒
ベクトル数は  （１５×２＋１）×（１５  ×２＋１）＝９６１ベクトル／ブロック
となり、したがって差分演算は
１６  ×１６×９６１  ×４０，５００＝９，９６３，６４８，０００回／秒
が必要である。
【０００５】
この演算の動作速度を５０ＭＨｚと仮定すると、
９，９６３，６４８，０００／５０ＭＨＺ  ＝１９９．２７
となるから、２００以上の演算を並行して行わなければならないことが判る。実際にはこの値を上回り、かつブロックサイズである２５６とも整合性があり、さらにＬＳＩの高集積化もあって、演算器を２５６個並べることが多くなってきている。この演算器は画像の精度のビット精度でそれぞれ構成される。
【０００６】
このように従来装置では演算器の回路規模がかなり大きくなるので、回路規模を削減することが要求される。そこで画像の精度を例えば８ビットとすると、演算にはその８ビット中の例えば上位４ビットのみを用いることにすれば、各演算器を４ビットで構成することができるので、回線規模はほぼ半分となる。しかし下位ビットが表す詳細な情報を切り捨てることから、動き検出性能が低下するという問題がある。
【０００７】
一方、ＭＰＥＧ−１、ＭＰＥＧ−２では、画素デ−タが存在する整数位置だけでなく、水平・垂直それぞれの中間位置に周辺の画素の値を用いて画素を補間し、それを予測値の候補とする方式が導入されている。
【０００８】
図６はこの補間方式を説明する図である。図６において、実線で示す○は整数位置にある参照画素、点線の○は隣接する実線の画素から補間された参照画素である。参照される画面にある実線の○画素から成るブロックと、点線の○から成るブロックを合わせたものの中から最適なブロックが選択（探索）される。
【０００９】
ここで一般には、上述の補間方式における動き検出では、演算量を減らすために、まず第１段階として整数画素（実線の○）のみを対象として最適位置を探索し、次いで第２段階として第１段階で検索した最適位置の周囲の８個の半画素精度の補間画素（点線の○）を対象として更に探索が行われる。
【００１０】
この整数画素単位、半画素単位の探索について説明する。以降、説明を簡単にするために１次元の画素列の場合について考えることにする。２次元については同じ処理を垂直方向に並列に行うことによって可能だからである。
【００１１】
探索の元になる原画像の画素列をＡ０  〜ＡＸ  、参照する画像の画素列をＢ０  〜Ｂｚ  とする。まず、第１段階の整数画素単位探索とはＡ０  〜ＡＸ  と最も近いＢｙ  〜Ｂｙ＋ｘ  を求めることである。つまり図７で下式の合計値Ｓｕｍが最小となる位置ｙを求めることである。
Ｓｕｍ（ｙ）＝Σ｜Ａｉ  −Ｂｙ＋ｉ  ｜                        （１）
但し、Σはｉ＝０からｘまでの加算
【００１２】
ここで画素Ａ，Ｂの精度はそれぞれｎビットとする。この探索に必要な回路を図８に示す。Ｓ０  〜Ｓｘ  はそれぞれ減算器であり、ｎビットの入力をもち、画素Ａ，Ｂがそれぞれ入力されて両者の減算結果を絶対値として出力する。加算器４は各減算器Ｓ０  〜Ｓｘ  の減算結果を加算して合計値Ｓｕｍとして出力する。この回路では、比較する画素の個数ｘ＋１と同じ数の減算器が必要になる。探索範囲内でｙを変化させ合計値Ｓｕｍが最小である変位ｙを求め、これを検索結果の変位Ｙとする。
【００１３】
次に、第２段階の半画素単位の探索とは、図９に示す画素Ａ，Ｃについて下式に示す合計値Ｓｕｍが最小となる位置Ｕを求めることである。ここで画素Ｃは参照画素Ｂから補間により求めた半画素精度の補間画素である。
Ｃｉ  （ｕ）＝（Ｂｉ＋ｕ  ＋Ｂｉ＋ｕ＋１  ）／２                  （２）
Ｓｕｍ（ｕ）＝Σ｜Ａｉ  −Ｃｉ  （ｕ）｜                  （３）
Ｓｕｍ（ｕ）＝  ｍｉｎｕ  Ｓｕｍ（ｕ）                                          （４）
【００１４】
ここで、Ａ，Ｂ，Ｃの精度はそれぞれｎビットとする。通常、半画素単位の探索は整数画素単位で求められたＹの周辺の隣り合った位置（Ｙ−１≦ｕ≦Ｙ＋１）につていてだけ計算する。この探索に必要な回路を図１０に示す。やはり比較する画素の個数ｘ＋１と同じ数の減算器が必要になり、各減算器の精度はｎビットが必要である。
【００１５】
この補間方式の動き検出の場合にも、回路規模の削減のために減算器の演算精度を落とすことが考えられる。しかしその場合には前述同様に、探索精度が著しく低下する。
【００１６】
一方、これらの並列配置された演算器は同一の構成をもつため、個々の演算器の回線規模を削減することができれば演算器の数が多いだけその効果は大である。例えば前述の例では１個の演算器の削減効果の２５６倍にもなる。
【００１７】
本発明は以上のような技術的諸問題に鑑みてなされたものであり、動き検出の検索精度を低下させることなく回路規模を削減することを目的とする。
【００１８】
【課題を解決するための手段】
上述の課題を解決するために、本発明においては、ブロックマッチングにより動き検出を行う動き補償予測型動画像符号化装置の動き検出装置であって、現画面のブロックと前画面のブロックの各画素の差分を計算する複数の演算器からなる第１の演算器群を備え、該第１の演算器群の各演算器は画素桁精度よりも低い計算精度で構成し、動き検出は、第１段階として該第１の演算器群を用いて検索範囲内のブロックのうちから差分の最も小さいブロックを検索し、第２段階として該第１の演算器群を２以上の演算器を互いに組み合わせて高精度化した複数の演算器組に分けて第２の演算器群を構成し、該第１段階で検索したブロックを含むその周辺のブロックに対して１ブロックの画素を複数に分割して該第２の演算器群を用い複数回の演算を行うことで差分の最も小さいブロックを検索することで行うように構成した動画像符号化装置の動き検出装置が提供される。
【００１９】
回線規模の削減に直接的な効果があるのは、演算精度の低減である。そこで、本発明の動き検出装置では、第１段階の検索ではブロックの画素の下位桁を省略して第１の演算器群で検索を行うことでこの検索に必要な演算器の計算精度を低くして全体の回路規模を削減している。そして、第２段階の検索では第２の演算器群により第１段階の検索よりも多い桁を演算に用いることで検索精度を上げている。
【００２０】
この動き検出装置による探索動作を説明する。ここでは前述同様に、説明を簡単化するために１次元の画素列の場合を例にする。２次元については同じ処理を垂直方向に並列に行うことによって行える。
【００２１】
探索の元になる原画像の画素列をＡ０  〜ＡＸ  、参照する画像の画素列をＢ０  〜Ｂｚ  とする。第１段階の探索ではＡ０  〜ＡＸ  と最も近いＢｙ  〜Ｂｙ＋ｘ  を求める。つまり前記の（１）式のＳｕｍが最小となる位置ｙを求める。
【００２２】
ここでＡ，Ｂの桁精度はそれぞれｎビットとする。この第１段階の探索に必要な回路を図２に示す。第１段階の検索では、演算器Ｓ０  〜Ｓｘ  に計算精度（ｎ−ｍ）ビットのものを用いて行い、画素列Ａ，Ｂは最上位桁（ＭＳＢ）側の（ｎ−ｍ）ビットを各演算器Ｓ０  〜Ｓｘ  に入力する。
【００２３】
第１段階の検索で差分が最小の画素列Ｂｙ  〜Ｂｙ＋ｘ  が求められたら、その検索した画素列を含むその周辺にある画素列を求め、これを画素列Ｃとする。
【００２４】
第２段階の探索は１画素あたりの差分計算に使用する演算器をｐ個にし、演算精度をＡ，Ｃそれぞれｐ倍｛ｐ×（ｎ−ｍ）ビット｝として行う（図１）。この場合、同時に差分計算する画素数が１／ｐ個になるため（ｘ＋１）個画素の差分を求めるためにｐ回の演算が必要になる。よって各回の演算結果を加算器４とメモリ７を用いて順次に累算していき、ｐ回演算した後に最終結果を得る。
【００２５】
この方法では演算回数が増加するため処理時間の増加は避けられない。しかし第２段階の検索は第１段階の探索範囲より狭い範囲（第１段階で検索したブロックとその周辺ブロック）で行うため、処理時間の増加は少ない。例えば第１段階で２次元でブロックの探索を水平、垂直方向の３１点について行い、第２段階の探索は第１段階の探索で求めたＹの周辺の８点について行う場合を考える。このとき第１段階の探索に３１２  ＝９６１点での演算が必要となるのに対し、第２段階の探索に必要な演算回数ｐの割合は全体の１％以下である。
【００２６】
このように第１段階の探索の演算精度だけを減らす一方、第２段階の探索の演算精度を上げることで、第１段階と第２段階で演算器を共有しながら、最終的に求まる探索誤差を少なく抑えることができる。
【００２７】
上述の動き検出装置は、第２段階での検索を、第１段階で検索したブロックを含むその周辺の補間により求めたブロックに対して行うように構成することができる。
【００２８】
前述したように、ＭＰＥＧ−１、ＭＰＥＧ−２では、画素デ−タが存在する整数位置だけでなく、水平・垂直それぞれの中間位置に周辺の画素の値を用いて画素を補間し、それを予測値の候補とする方式が導入されている。本発明はこの方式にも適用できる。
【００２９】
すなわち、第１段階の検索を図６に○で示す整数位置にある参照画素に対して行い、第２段階の検索を第１段階の検索で求めた参照画素とその周辺の点線の○で示す隣接する実線の画素から補間された参照画素に対して行う。第１段階の整数画素探索には下位ビットを省略し、第２段階の半画素探索は全てビット、あるいは整数画素探索よりも多いビットを演算に用いることで、検出精度を上げ、画質向上を図る。
【００３０】
また本発明の動き検出装置は、第１段階での検索を、検索範囲内における全ブロックに対して行うことに代えて画素複数個置き（例えば１画素置き）の各ブロックに対して行うように構成できる。
【００３１】
【発明の実施の形態】
以下、本発明の実施例を図面を参照して説明する。
図３、図４には本発明の一実施例としての動画像符号化装置の動き検出装置が示される。この実施例装置は、画素デ−タが存在する整数位置だけでなく、水平・垂直それぞれの中間位置に周辺の画素の値を用いて画素を補間し、それを予測値の候補とする方式の動画像符号化装置に本発明を適用したものである。
【００３２】
図中、１は現画面の画像データを記憶するフレームメモリ、２は前画面の画像データを記憶するフレームメモリであり、画像データの各画素は８ビットからなる。３はフレームメモリ２から検索範囲にあるブロックを読み出すアドレスを発生するアドレス発生器である。
【００３３】
Ｓ０  〜Ｓ１５はそれぞれ４ビットの減算器であり、フレームメモリ１からの画素データとフレームメモリ２からの画素データがそれぞれ入力されて両者の差分を計算する。４は各減算器Ｓ０  〜Ｓ１５からの差分値を加算する加算器である。５は比較器、６はメモリであり、比較器５はメモリ６の内容（ＳｕｍＭｉｎ）と加算器４の加算値ＳｕｍＴｍｐを比較し、加算値ＳｕｍＴｍｐが小さい場合にそれを新たな加算値ＳｕｍＭｉｎとしてメモリ６に送出する。このメモリ６には加算値ＳｕｍＭｉｎとともにその加算値ＳｕｍＭｉｎに対応する変位Ｙも記憶される。
【００３４】
また図４において、７は累算用のメモリであり、メモリ７の出力を加算器４の入力側に戻すことにより、複数回の演算にわたる加算器４の加算結果をメモリ７に累算できるようになっている。また８は補間画素生成回路であり、フレームメモリ２の画素を補間して半画素精度の補間画素を生成し、各減算器Ｓ０  〜Ｓ１５に供給する。
【００３５】
以下、図３と図４を参照して実施例装置の動作を説明する。この図３と図４は同じ減算器Ｓ０  〜Ｓ１５を使って、整数画素単位の検索を行う時（図３）と、半画素単位の探索を行う時（図４）のそれぞれの接続形態を示したものである。説明を簡略化するため、ここではベクトル探索の対象とする画素の個数を水平方向の１６個のみとする。２次元画像については同様の回路を垂直方向に並列にならべることで実現する。またそれぞれの画素値は８ビットで表現されるものとする。
【００３６】
図３の接続形態での動作について説明する。まず原画像の格納されたフレ−ムメモリ１から画素Ａ０  〜Ａ１５を順次読み出し、それぞれを減算器Ｓ０  〜Ｓ１５の入力とする。ここで各減算器Ｓ０  〜Ｓ１５は減算結果の絶対値をとって出力するものとする。またそれぞれの減算器Ｓ０  〜Ｓ１５の入力は４ビットのものを使用する。そのため８ビットの画素ＡのＭＳＢ側の４ビットを入力する。
【００３７】
次に参照画像用のフレ−ムメモリ２から比較する画素Ｂｙ  ，Ｂｙ＋１  ，  ・・・，  Ｂｙ＋１５を読みだし、やはり減算器Ｓ０  〜Ｓ１５の入力とする。こちらもやはりＭＳＢ側の４ビットだけを使用する。減算器Ｓ０  〜Ｓ１５によって入力されたＡ，Ｂの差分計算を行い、この差分累積和を加算器４で求める。この計算をｙの値を探索範囲内で変化させながら減算器Ｓ０  〜Ｓ１５に順次に入力して行い、加算器４で求めた差分累積和ＳｕｍＴｍｐをメモリ６に格納されているそれまでの最小の差分累積和ＳｕｍＭｉｎと比較器５で比較する。加算器４の差分累積値ＳｕｍＴｍｐがそれまでの差分累積和の最小値より小さい場合、その差分累積値ＳｕｍＴｍｐとその時の変位ｙを新たに最小値ＳｕｍＭｉｎとしてメモリ６に格納する。このようにして全検索範囲について検索して求めた最小値をＳｕｍＭｉｎ、その時の変位をＹとする。
【００３８】
次に同じ減算器Ｓ０  〜Ｓ１５をつかって図４のような構成に接続を切り替える。まず原画像の格納されたフレ−ムメモリ１から画素Ａ０  〜Ａ１５のうちの半分にあたる画素Ａ０  〜Ａ７  を順次に読み出し、それぞれを減算器Ｓ０  ，  Ｓ１  ，  ・・・Ｓ１４，Ｓ１５の入力とする。今度はＡの精度を８ビットのままにするが、かわりに減算器を１画素あたり２個使用して接続することにより８ビット計算精度の減算器を構成する。すなわち１６個の減算器Ｓ０  〜Ｓ１５をそれぞれ二つずつ組み合わせてキャリー信号線を接続し８ビット精度の減算器ペアーＳ０  ＋Ｓ１  、Ｓ２  ＋Ｓ３  ，・・・Ｓ１４＋Ｓ１５を８個構成する。この減算器ペアーの一方に画素データのＭＳＢ側４ビットを、もう一方にＬＳＢ側４ビットを入力する。
【００３９】
次に半画素単位の参照画素Ｃを生成するため、参照画像用のフレ−ムメモリ２から画素Ｂｕ  ，Ｂｕ＋１  （Ｙ−１≦ｕ≦Ｙ＋１）を読み出して補間画素生成回路８に入力し、ここで平均値を算出することで補間画素Ｃｕ  〜Ｃｕ＋７  を生成し、やはり減算器Ｓ０  〜Ｓ１５の入力とする。Ａ０  〜Ａ７  とＣｕ  〜Ｃｕ＋７  の差分を計算し、絶対値累積和とその変位ｕをメモリ７に格納する。
【００４０】
画素Ａ０  〜Ａ１５のうちの残り半分の画素Ａ８  〜Ａ１５についても同様に計算し、既に求めてメモリ７に格納してあるＡ０  〜Ａ７  の結果と合わせることで、Ａ０  〜Ａ１５とＣｕ  〜Ｃｕ＋１５についての差分絶対値和ＳｕｍＴｍｐを求め、これをメモリ７にその時の変位ｕとともに格納する。このため演算回数は整数画素単位の探索時の２倍になるが、探索単位が少ないので処理時間の増加は大きくない。
【００４１】
このメモリ７の差分累積値ＳｕｍＴｍｐとメモリ６のそれまでの最小値ＳｕｍＭｉｎと比較して、最小値ＳｕｍＭｉｎよりも小さければその値を新たな最小値ＳｕｍＭｉｎとしてその時の変位Ｕと共にメモリ６に格納する。このようにしてＡ０  〜Ａ１５にもっとも近いＣｕ  〜Ｃｕ＋１５となる変位Ｕを求めることができる。
【００４２】
本発明の実施にあたっては種々の変形形態が可能である。例えば上述の実施例は補間画素を作って半画素精度の動き検出を行える動画像符号化装置に本発明を適用した場合のものであるが、もちろん本発明はかかる半画素精度の動き検出を行わない方式の動画像符号化装置にも適用できる。この場合、図６に○で示す整数画素を対象として第１段階、第２段階の検索を行うことになる。またその場合、第１段階の検索は例えば画素一つ置きにブロックを抽出してそれらのブロックに対して行い、第２段階の検索で、第１段階で検索されたブロックの周辺にある第１段階で一つ置きにより飛ばされたブロックに対して検索を行うようにすれば、演算回数を削減することができる。
【００４３】
【発明の効果】
以上に説明したように、本発明によれば、動き検出の検索精度を低下させることなく回路規模を削減することができる。
【図面の簡単な説明】
【図１】本発明に係る原理説明図（第２段階の接続）である。
【図２】本発明に係る原理説明図（第１段階の接続）である。
【図３】本発明の一実施例としての動画像符号化装置の動き検出装置（第１段階の接続形態）を示す図である。
【図４】本発明の一実施例としての動画像符号化装置の動き検出装置（第２段階の接続形態）を示す図である。
【図５】ブロックマッチングによる動き検出を説明する図である。
【図６】補間画素による動き検出を説明する図である。
【図７】補間画素による動き検出方式の第１段階の整数画素検索を説明する図である。
【図８】補間画素による動き検出方式の第１段階の整数画素検索を行う回路を示す図である。
【図９】補間画素による動き検出方式の第２段階の半画素検索を説明する図である。
【図１０】補間画素による動き検出方式の第２段階の半画素検索を行う回路を示す図である。
【符号の説明】
１、２  フレームメモリ
３  アドレス発生器
４  加算器
５  比較器
６、７  メモリ
８  補間画素生成回路
【図１】
0003580612.tif 000002
【図２】
0003580612.tif 000003
【図３】
0003580612.tif 000004
【図４】
0003580612.tif 000005
【図５】
0003580612.tif 000006
【図６】
0003580612.tif 000007
【図７】
0003580612.tif 000008
【図８】
0003580612.tif 000009
【図９】
0003580612.tif 000010
【図１０】
0003580612.tif 000011