JPH0793728B2 - 動ベクトル検出装置 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、動画像のフレーム間符号化装置に使用される
動ベクトル検出装置、特に基本演算部を複数個用いて探
索領域を拡張するに好適な動ベクトル検出装置に関す
る。

〔従来の技術〕

テレビ電話等では、画像の伝送量の縮小化をはかるた
め、動ベクトルを検出する例がある。動ベクトルとは、
現画面と前画面との間で、画面相互の動きをベクトルと
して求めておくものである。

具体的には、現画面に検出ブロックａ（Ｍ×Ｍ画素）を
設定し、前画面に検出ブロック対応に探索範囲ｂ（Ｎ×
Ｎ画素）を設定する。探索範囲は検出ブロックよりも大
きく、Ｎ＞Ｍである。探索範囲を、検出ブロックと同じ
大きさの容量を持つ探索ブロックで全面走査する。検出
ブロックと各探索ブロックとの間で、評価データD_ijを
得る。評価データD_ijは、検出ブロックと探索ブロック
との間で対応画素毎に画素データの差分をとり、その絶
対値をブロックの全画素分累積加算（総和）して求め
る。評価データは、探索範囲に含まれる全探索ブロック
数（Ｎ−Ｍ＋１）個求められる。

評価データD_ijの算出式は以下となる。

（１）式で、i,jは座標（アドレス）、ａは現画面上の
検出ブロック、ｂは前画面上の探索ブロックデータであ
る。ｋとｌとで探索ブロックの番号が定まる。

探索範囲内について求めたＮ−Ｍ＋１個の評価データの
中で、最小の評価データを求める。この最小の評価デー
タを与えた探索ブロックが、検出ブロックの移動前のブ
ロックとみなし、検出ブロックと探索ブロックの位置関
係をベクトルで表示する。このベクトルが動ベクトルで
ある。

探索範囲とは以下の通りである。前画面内で、検出ブロ
ックと同じ位置で、且つ同じ容量のブロック（これを、
同位置ブロックと呼ぶ）の周囲に、同位置ブロックより
も大きい範囲を採る。これが探索範囲である。従って、
探索範囲とは、ブロックの移動可能な範囲と考えてよ
い。また、検出ブロックも大きければ演算回数は少なく
簡単であるが、精度が低下するため、余り大きくはでき
ない。

〔発明が解決しようとする課題〕

動ベクトル検出装置として、出願人は特許出願をしてい
る。（特願平１−244454号）。かかる先願の動ベクトル
の演算部101A構成図を第７図に示す。演算部101Aは３入
力端子50〜52,1出力端子61を有する。制御端子70は同位
置ベクトル選択信号E/Cを入力する端子である。第７図
で、入力切換部10は、入力データa,b,b′を選択し、ａ
とb,aとｂ′との組合せを、演算回路20,21,22に選択的
に振り分ける。ここで、入力データａとは、入力画像ブ
ロック８であり、前述の検出ブロックである。これらは
図示しないが、それぞれ、現画面データメモリ、前画面
データメモリに記憶されている場合もあれば、オンライ
ンで得られる場合もある。入力データb,b′とは前画面
画像ブロック９を２分化して得たデータであり、且つこ
の前画面画像ブロック９とは、探索範囲そのものであ
る。

更に、b,b′に２分化したのは、演算回数低減のためで
ある。

演算回路20,21,22は、それぞれ単独で評価データを演算
する演算回路である。

出力切換部30は、演算回路20,21,22から得られる評価デ
ータを選択して出力する。

最小値検出部40は、探索範囲から得られる複数の評価デ
ータの最小値を検出する。この最小値を与える探索ブロ
ックの位置（アドレス）が、動ベクトルとなる。

第８図には、検出ブロックと探索範囲との関係を示す。
第８図（イ）は、入力画面データ例であり、この入力画
面を６×８のブロックに分割した例である。各ブロック
の大きさはＭ×Ｍ画素の均等としており、これらの各ブ
ロックが検出ブロックとなる。

第８図（ロ）は、前画面データ例であり、これも、入力
画面と同じくブロックの均等割りつけを行っている。前
画面データの各ブロックは、検出ブロックの同位置ブロ
ックに相当する。この同位置ブロックの周囲に探索範囲
Ｎ×Ｎ画素を設定する。

第９図は、検出ブロックと探索範囲とを示す図であり、
第９図（イ）の検出ブロックは、Ｍ＝３とした例であ
る。第９図（ロ）の探索範囲はＮ＝５とした例である。
探索範囲は、左側の５×３の部分ブロックｂと、右側の
５×２の部分ブロックｂ′に２分し、これが第７図のデ
ータb,b′に相当する。

第10図は、第７図の構成のもとでの、第９図のデータに
対する評価データを得るための演算プロセスを示す図で
ある。縦方向にクロックタイミング、横方向に入力デー
タ、演算回路20,21,22（PE1,PE2,PE3）でのデータの流
れを示す。例えば、クロックタイミング０〜８で第９図
（イ）の検出ブロックと第９図（ロ）の第１の探索ブロ
ック（斜線内）とのデータa,bを取込む。このデータa,b
に対し、演算回路20は、データを取込む毎に両者の差分
をとり、絶対値化する。絶対値化した差分は、アキュム
レータに送られ（図示せず）、累積化されせる。かくし
て、クロックタイミング８の終了時点では、検出ブロッ
クと第１の探索ブロックとの間での評価データD₁₁が得
られたことになる。

一方、演算回路21では、クロックタイミング１〜９にか
けて、第１の探索ブロックを右に１画素ずらした第２の
探索ブロックと検出ブロックとの間で評価データD₁₂を
得る。演算回路22では、クロックタイミング２〜10にか
けて、第２の探索ブロックを右に１画素ずらした第３の
探索ブロックと検出ブロックとの間で評価データD₁₃を
得る。

他の評価データの算出も同様に第10図に従って行われ
る。

然るに、探索範囲を拡張したい要求がある。探索範囲を
拡張することは、１つの検出ブロックに対して探索ブロ
ックの数が増大することであり、探索時間の増大、演算
時間の増大を招く。拡張した探索範囲に従って回路構成
を組み直し、少ない回路点数のもとで拡張した探索範囲
の処理を行わせることが必要となる。

本発明の目的は、特定の探索の範囲に対して構成された
演算部を複数用いて拡張した探索範囲に対応した動ベク
トル検出装置を提供するものである。

〔課題を解決するための手段〕

本発明は、入力画面中の大きさＭ×Ｍ画素の検出ブロッ
クと、前画面中の大きさ（2M−１）×（2M−１）画素の
探索範囲の複数個の大きさＭ×Ｍ画素の探索ブロックと
を遂次的に読出す手段と、読出した検出ブロックと複数
個の探索ブロックとを遂次的に相互比較を行い、局所動
ベクトルを算出する複数個の演算部と、を備えた動ベク
トル検出装置において、探索範囲を大きさ（2M−１）×
（2M−１）画素から（Ｑ×Ｍ−１）×（Ｑ×Ｍ−１）画
素に拡張する際の上記演算部の数をＰ（Ｐ＝2²，3²，
4²，……）とした時、ＱとＰとは、 の関係としたものである。更に、上記Ｐ個の演算部に
は、上記前画面の拡張探索範囲が、Ｍ（水平方向）×
（2M−１）（垂直方向）画素の小部分領域に分割されて
入力され、かつ、該Ｐ個の演算部のうち水平方向に隣接
した小部分領域が入力される２個の演算部には１つの小
部分領域が共通して入力されてなるものである。

更に、本発明での上記探索範囲及び拡張探索範囲は、検
出ブロックと同位置の同位置ブロックを中心とせしめ
た。

更に、本発明でのＰ個の演算部は各々、探索ブロックの
左上位置（エッジ）を第１番目のクロック時間で演算
し、入力画像ブロックと空間的に同一位置（センタ）を
第ｍ番目のクロック時間で演算し（ｍ＝（Ｍ＋１）×M/
2＋１で規定）、上記両クロック時間における演算結果
を外部信号により選択して出力する手段を具備し、上記
拡張された探索範囲をＰ個の演算部で処理するに左上の
部分領域を第１番目の演算部が、その右隣接部分領域を
第２番目の演算部が処理し、最後の右下の部分領域を第
Ｐ番目の演算部が処理し、Ｐの値が奇数の場合は第（Ｐ
＋１）/2番目の演算部について上記第ｍ番目のクロック
時間での演算結果を選択して、上記拡張された探索範囲
に対する同一位置ベクトルを定め、Ｐの値が偶数の場合
は第ｎ番目の演算部について上記第１番目のクロック時
間での演算結果を選択して上記拡張された探索領域に対
する同一位置ベクトルと定め ることとした。

〔作用〕

本発明によれば、（2M−１）×（2M−１）画素の大きさ
の探索範囲を持つ演算部の個数Ｐと、拡張探索範囲（Ｑ
×Ｍ−１）×（Ｑ×Ｍ−１）画素でのＱとの関係を、 とせしめたことにより、拡張探索範囲での迅速な探索を
可能とする。

更に、本発明によれば、同位置ベクトルの検出を、拡張
探索範囲についての探索過程中で自動的に検出する。

〔実施例〕 第１図は本発明の動ベクトル検出装置の実施例図であ
る。この動ベクトル検出装置は、４つの演算部101〜10
4、外部比較部200より成る。

この演算部101〜104のそれぞれは第７図に示した３入力
の演算部101Aそのものである。３入力の中で、検出ブロ
ックデータａは各回路に共通に入力しており、残りの２
つの入力は拡張した探索範囲を示すデータｂの分割デー
タb₁,b_１′,b_２′，b₃,b_３′,b_４′の中の特定の２つで
ある。（演算部101にはb₁,b_１′、演算部102には
ｂ_１′,b_２′、演算部103にはb₃,b_３′、演算部104には
ｂ_３′,b_４′）。

演算部101〜104内では、ａとｂ及びｂ′との間で差分を
とり、これらの絶対値した値を累積する。この累積結果
が評価データである。この評価データは、局所動ベクト
ル情報として外部比較部200に送られ、最小の評価デー
タを与える探索ブロックを、端子60から動ベクトル情報
として抽出する。

演算部101は、第７図の全要素10,30,40,20〜22を１つに
まとめたものである。他の演算部102〜104も同じであ
る。即ち、検出ブロックの大きさをＭ×Ｍとした時、各
演算部101〜104は（2M−１）×（2M−１）の探索範囲を
有する回路である。

ここで、演算部の数と拡張率との関係を以下に示す。検
出ブロックの大きさをＭ×Ｍ画素、拡張した探索範囲の
大きさを（Ｑ×Ｍ−１）×（Ｑ×Ｍ−１）とし、演算部
の数をＰとした時、Ｐと拡張率Ｑとの関係を以下に設定
する。但し、Ｑ＞２とする。

この（２）式は、演算部数Ｐに対して、その平方根に１
を加算した値をもって拡張率Ｑとしたものである。演算
部数Ｐは、1,2²，3²，4²，……がとられる。

具体例で示す。検出ブロックの大きさＭ×ＭのＭをＭ＝
３画素、演算部数Ｐ＝４（第１図の例）とした場合、拡
張探索範囲の大きさは、（Ｑ×Ｍ−１）×（Ｑ×Ｍ−
１）＝８×８画素となる。かかる拡張探索範囲に対して
の演算部101〜104による演算分担例を第２図に示す。第
２図（イ）の第１分割探索範囲は演算部101用とし、第
２図（ロ）の第２分割探索範囲は演算部102用とし、第
２図（ハ）の第３分割探索範囲は演算部103用とし、第
２図（ニ）の第４分割探索範囲は演算部104用とする。
又、（ニ）の斜線で示した３×３画素は同位置ブロック
に相当する。

４つの分割探索範囲の大きさは、（２×Ｍ−１）×（２
×Ｍ−１）＝５×５画素の均等な大きさとしている。

かかる４つの分割探索範囲のデータの与え方を第３図に
示す。第３図で、水平方向に左側から３画素ずつ区分す
る。最後に２画素分残る。一方、垂直方向に上から３画
素分で区切り、次に２画素分で区切る。残りは３画素分
となる。かくして均等ではないが、９個の区分ができた
ことになる。

第３図（イ）の区分に対し、垂直方向に上から５画素分
で区切ると第３図（ロ）となり、垂直方向に下から５画
素分で区切ると第３図（ハ）となる。第３図（ロ）と
（ハ）とでは、第３図（イ）の斜線で示した中間区分の
２×８の大きさのブロックが重複する。

ここで、第３図（ロ）の３つの区分のデータをb₁,
b_１′,b_２′とし、第３図（ハ）の３つの区分のデータ
をb₃,b_３′,b_４′と定義する。b₁はｂ（0.0）〜ｂ（4.
2）の15個のデータが、ｂ_１′はｂ（0.3）〜ｂ（4.5）
の15個のデータが、ｂ_２′はｂ（0.6）〜ｂ（4.7）の10
個のデータが、b₃はｂ（3.0）〜ｂ（7.2）の15個のデー
タが、ｂ_３′はｂ（3.3）〜ｂ（7.5）の15個のデータ
が、ｂ_４′はｂ（3.6）〜ｂ（7.7）の10個のデータが与
えられる。第１図の演算部101〜104へのブロックｂから
の各入力が、これらの各区分毎のデータである。

これらの各ｂ入力をもとにしての演算部101〜104の動作
を、第11図により説明する。各演算部の動作は基本的に
第10図に示したものと同様である。

演算部101は、第２図（イ）の左上の５×５画素の大き
さの分割探索範囲での、検出ブロックと探索ブロックと
の間の評価データを得る。ここで、検出ブロックと探索
ブロックの大きさは、それぞれ３×３画素である。

探索ブロックは、水平方向に３個、垂直方向に３個であ
り、合計３×３＝９個である。然るに、この第１分割探
索ブロックは、第３図（ロ）に示したように、b₁とｂ
_１′とで形成されている故、演算部101では、データａ
の他に、b₁とｂ_１′も併せて取込み、第11図に示したよ
うに、クロック28番で演算を終了する。

演算部102は、第２図（ロ）の第２分割探索範囲を担当
する。これはデータｂ_１′,b_２′で形成されており、ａ
とｂ_１′,b_２′との間で第11図に示したように、クロッ
ク32番で演算を終了する。

演算部103,104も同様の考え方で入力取込み演算を行っ
ている。

演算部104は、第２図（ニ）の第４分割探索範囲にわた
っての局所動ベクトルを得る機能の他に、同位置ブロッ
クでのベクトル値（評価値）を得る機能を持つ。拡張探
索範囲が（2m＋１）×（2m＋１）の如く、奇数の大きさ
の辺を持つ場合には、同位置ブロックは、丁度その真中
に位置する。第２図の例では拡張探索範囲が2m×2mの如
く偶数の大きさの辺を持つ故に、同位置ブロックは、拡
張探索範囲の中心に位置せず、同位置ブロックは第２図
（ニ）に斜線で示す如き位置に存在し、演算部104で
の、第１探索ブロック（エッジ）が同位置ブロックに相
当する。そこで、演算部104は、この第１探索ブロック
のデータを取込み、検出ブロックとの間で評価データを
得る演算を行う際に、外部からの同位置ラッチ信号E/C7
0を受けて（本実施例ではエッジＥを示す信号を与え
る）この第１探索ブロックに対する評価データを別に設
けたラッチ手段に保持する。このラッチした第１探索ブ
ロックの評価データは同位置ベクトルであり、適宜外部
に提供する。

外部比較部200は、４つの演算部101〜104からの評価デ
ータである局所動ベクトル情報61〜64を受けて、大小比
較をし、最小のものを拡張された探索範囲に亘る動ベク
トル60として特定する。

本実施例によれば、４つの演算部のもとで８×８画素の
大きさの拡張された探索範囲に対して、適宜分担しなが
ら評価データを得ることにより、即ち、拡張探索範囲を
小部分領域に分割して複数各演算部に入力することによ
り演算回数を低減し、また、１つの小部分領域を２つの
演算部に共通して入力することにより演算時間の低減を
することができる。

本発明の動ベクトル検出装置の他の実施例を第４図に示
す。本実施例は、Ｐ＝９個の演算部101〜109を使用して
更に大きい拡張探索範囲を探索した例である。（２）式
によれば、拡大率Ｑは、 であり、拡張後の探索範囲は、（４×Ｍ−１）×（４×
Ｍ−１）画素の大きさとなる。Ｍ＝３とすれば、拡張後
の探索範囲の大きさは、11×11画素となる。

この拡張探索範囲での分割探索範囲の考え方の例を第５
図，第６図に示す。

第５図（イ）に示した上側の領域を演算部101,102,103
が処理し、（ロ）に示した中央の領域を演算部104,105,
106が処理し、（ハ）に示した下側の領域を演算部107,1
08,109が各々処理する。第５図（ロ）で演算部105が処
理する中心部の５×５画素の内で、斜線で示した中心部
３×３画素は同位置ブロックに相当する。演算部105は
制御信号E/C70により評価データ（同位置ベクトル）を
出力する。本実施例では中心の位置が対応するのでＣ
（センター）信号を入力する。

次に拡張された探索範囲ｂのデータ配列について説明す
る。第６図に探索範囲ｂの分割について示した。11×11
画素のブロック第６図（イ）は上側の11×５画素第６図
（ロ）と、中央の11×５画素第６図（ハ）、下側の11×
５画素第６図（ニ）の領域に分割されている。各々の11
×５画素ブロックは３×５画素ブロック３個と２×５画
素ブロックとに分割され、各々b₁,b_１′＝b₂,b_２′＝
b₃,b_３′，b₄,b_４′＝b₅,b_５′＝b₆,b_６′，b₇,b_７′＝
b₈,b_８′＝b₉,b_９′とされる。第４図に示すように９個
の演算部101〜109には、入力データとしてa,b₁,b_１′が
演算部101に、a,b_１′,b_２′が演算部102に、a,b_２′,b
_３′が演算部103に、a,b₄,b_４′が演算部104に、a,b
_４′,b_５′が演算部105に、a,b_５′,b_６′が演算部106
に、a,b₇,b_７′が演算部107に、a,b_７′,b_８′が演算部
108に、a,b_８′,b_９′が演算部109に各々入力される。

演算部101〜109は各々第５図に示した分担領域に対応し
た処理を実行し、局所動きベクトル情報61〜69を出力す
る。これら９個の出力結果は外部比較手段200により大
小比較され、最小なものが拡張された探索範囲に亘る動
きベクトル情報60として出力される。

次に、同位置ベクトルの一般的な求め方を以下に示す。

Ｐ個の動きベクトル演算部は各々、探索ブロックの左上
位置（エッジ）を第１番目のクロック時間で演算し、入
力画像ブロックと空間的に同一位置（センタ）を第ｍ番
目のクロック時間で演算し（ｍ＝（Ｍ＋１）×M/2＋１
で規定）、上記両クロック時間における演算結果を外部
信号により選択して出力する。上記拡張された探索範囲
をＰ個の演算部で処理するに左上の部分領域を第１番目
の演算部が、その右隣接部分領域を第２番目の演算部が
処理し、最後の右下の部分領域を第Ｐ番目の演算部が処
理する。Ｐの値が奇数の場合は第（Ｐ＋１）/2番目の演
算部について上記第ｍ番目のクロック時間での演算結果
を選択して、上記拡張された探索範囲に対する同位置ベ
クトルと定め、Ｐの値が偶数の場合は第ｎ番目の演算部
について上記第１番目のクロック時間での演算結果を選
択して上記拡張された探索範囲に対する同一位置ベクト
ルと定め ることになる。

〔発明の効果〕

本発明によれば、同一の演算部を複数個使用して動きベ
クトルの探索領域を拡張でき、拡張探索範囲での迅速な
探索ができる新しい機能を達成できる。又、同位置ベク
トルの値も容易に演算することができ、大きな付加回路
を必要としない。

【図面の簡単な説明】

第１図は本発明の動ベクトル検出装置の実施例図、第２
図及び第３図は本発明の探索範囲の分割例図、第４図は
本発明の動ベクトル検出装置の他の実施例図、第５図及
び第６図はこの他の実施例における探索範囲の分割例
図、第７図は従来の動ベクトル検出装置を示す図、第８
図は同位置ブロックの説明図、第９図は検出ブロックと
探索範囲との関係図、第10図は従来の動ベクトル検出装
置の動作タイムチャートと演算例を示す図、第11図は第
１の実施例の動作タイムチャートと演算例を示す図であ
る。 101〜104……演算部、200……外部比較手段。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 丸山 優徳 東京都港区南青山７丁目１番５号 コラム 南青山６Ｆ 株式会社ブラフィックス・コ ミュニケーション・テノロジーズ内 (56)参考文献 特開 昭54−124927（ＪＰ，Ａ) 特開 昭63−244985（ＪＰ，Ａ)

Claims (3)

【特許請求の範囲】
1. 【請求項１】入力画面中の大きさＭ×Ｍ画素の検出ブロ
   ックと前画面中の大きさ（2M−１）×（2M−１）画素の
   探索範囲の大きさＭ×Ｍの複数個の探索ブロックとを逐
   次的に読出す手段と、読出した検出ブロックと複数個の
   探索ブロックとを逐次的に相互比較を行い、局所動ベク
   トルを算出する複数個の演算部と、を備えた動ベクトル
   検出装置において、 上記前画面の探索範囲を大きさ（2M−１）×（2M−１）
   画素から（Ｑ×Ｍ−１）×（Ｑ×Ｍ−１）画素に拡張す
   る際の上記演算部の数をＰ（Ｐ＝2²，3³，4²……）とし
   た時、上記拡張率ＱとＰとは、 の関係を持たせてなり、上記Ｐ個の演算部には、上記前
   画面の拡張探索範囲が、Ｍ（水平方向）×（2M−１）
   （垂直方向）画素の小部分領域に分割されて入力され、
   かつ、該Ｐ個の演算部のうち水平方向に隣接した小部分
   領域が入力される２個の演算部には１つの小部分領域が
   共通して入力されてなるものであることを特徴とする動
   ベクトル検出装置。
2. 【請求項２】上記拡張探索範囲は、検出ブロックと同位
   置の同位置ブロックを中心とする範囲としてなることを
   特徴とする請求項１記載の動ベクトル検出装置。
3. 【請求項３】上記Ｐ個の演算部は、各々、探索ブロック
   の左上位置（エッジ）を第１番目のクロック時間で演算
   し、入力画像ブロックと空間的に同一位置（センタ）を
   第ｍ番目のクロック時間で演算し（ｍ＝（Ｍ＋１）×M/
   2＋１で規定）、上記両クロック時間における演算結果
   を外部信号により選択して出力する手段を具備し、上記
   拡張された探索範囲を上記Ｐ個の演算部で処理する左上
   の小部分領域を第１番目の演算部が、その右隣接小部分
   領域を第２番目の演算部が処理し、最後の右下の小部分
   領域を第Ｐ番目の演算部が処理し、Ｐの値が奇数の場合
   は第（Ｐ＋１）/2番目の演算部について上記第ｍ番目の
   クロック時間での演算結果を選択して上記拡張された探
   索範囲に対する同一位置ベクトルと定め、Ｐの値が偶数
   の場合は第ｎ番目の演算部について上記第１番目のクロ
   ック時間での演算結果を選択して上記拡張された探索領
   域に対する同一位置ベクトルと定め てなることを特徴とする請求項１又は請求項２記載の動
   ベクトル検出装置。