JP3046313B2 - フレーム間符号化装置における動き補償方式 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明はフレーム間符号化装置における動き補償方
式、特に動き補償の演算量を低減するに好適な動き補償
方式に関するものである。

［従来の技術］ 第８図から第10図までは例えば文献『動き補償・背景
予測を用いたフレーム間符号化方式』（電子通信学会論
文誌′85/1Vol.J68−BNo.1p77〜p84黒田英夫、武川直
樹、橋本秀雄共著）に示される従来の動き補償演算方法
の説明図で、特に全探索形の方法を例示するものであ
る。

図において、（１）は画像データの入力信号、（２）
は入力データを一旦１フレーム分記憶する入力フレーム
バッファ、（３）は現在の入力フレーム中の所定位置の
動き補償用のブロックサイズ１×l2を有する現在入力
ブロック、（４）は前回入力フレーム再生データ中にお
ける現在入力ブロック（３）とマッチング処理を行う対
象となるブロックの存在する範囲１＋2m、l2＋2nを示
す動きベクトル探索範囲である。

この場合、探索対象ブロック数Ｍは Ｍ＝（2m＋１）×（2n＋１） …（100） となり、探索範囲は水平方向に−ｍ〜＋ｍ画素の範囲、
垂直方向に−ｎ〜＋ｎ画素の範囲となる。

動き補償は、フレーム間符号化伝送方式において現在
入力フレームデータと前回入力フレーム再生データのフ
レーム間相関を利用して、現在入力フレームデータによ
り近い予測信号を求める処理を所定の大きさのブロック
単位で処理するものである。

そして、現在入力フレームデータ中の現在入力ブロッ
ク（３）と最も相関の高いブロックすなわち差分絶対値
和が最小となる条件等によりブロック間歪量の最も少な
いブロックを前回入力フレーム再生データ中の動きベク
トル探索範囲（４）から探索し、動きベクトルと予測信
号を得ている。

また、図において、（５）は入力信号（１）の現在入
力ブロック（３）と前回の入力信号再生データとして与
えられた動きベクトル探索範囲（４）の相関近似計算に
より予測信号を求める動き補償部、（６）は動き補償部
（５）から出力される予測信号、（７）は動き補償部
（５）から出力される動きベクトル情報である。

更に、（９）は入力ブロック信号（３）と予測信号
（６）との差分信号（８）を符号化して符号化信号（1
0）を出力する符号化部、（11）は符号化部（９）で符
号化された符号化信号（10）を復号化する復号化部であ
る。

そして、（14）は復号化部（11）からの復号化信号
（12）と動き補償部（５）からの予測信号（６）を加算
して再生データ（13）に戻してこれを記憶すると共に動
き補償部（５）に動きベクトル探索範囲（４）を与える
フレームメモリ、（15）は送信バッファ、（16）は送信
信号である。

次いで、動作を第９図及び第10図に従って説明する。

現在入力フレーム中の現在入力ブロック（３）で特定
の位置の１×l2のサイズのブロックＸに対して前回入
力フレーム再生データ中の動きベクトル探索範囲（４）
内のＭ個のブロックとの間のブロック間歪量を計算し、
この歪の最小値すなわち最小歪を与える最小歪ブロック
yiの現在入力ブロック（３）の位置に対する相対位置す
なわち動きベクトルＶを求めると共に該ブロックyiの信
号yminを予測信号（６）として出力するものである。

そして、フレーム間符号化伝送では信号の受信側にお
いても予測信号（６）を生成し得る。

例えば、与えられた動きベクトル探索範囲（４）内で
探索対象となる動きベクトルＶの個数をＭ（２以上の整
数）とすると、特定の動きベクトルＶの位置の前フレー
ム・ブロックと現在の入力ブロックとの歪量として差分
絶対値和を用いた場合、歪量は となる。ここで、入力ブロックは Ｘ＝｛x1、x2、……xL｝、 探索対象ブロックは yi＝｛yi1、yi2、……yiL｝、 ｉ＝１〜Ｍ、Ｌはｌ×l2である。そして、動きベクト
ルＶは Ｖ＝Vi｛min dili＝１〜Ｍ｝…（102）で求められる。

そして、この場合の演算量S1は絶対差分値和演算をａ
マシンサイクル、比較処理をｂマインサイクルとした場
合、 S1＝Ｍ（Ｌ×ａ＋ｂ） …（103） となる。

ここで、例えばａ＝１マシンサイクル、ｂ＝２マシン
サイクル、１＝８、l2＝８、ｍ＝８、ｎ＝８とした場
合、Ｌ＝64、Ｍ＝289となり、 S119000 …（104） マシンサイクルとなる。この演算量S1はハードウェアの
構成から見れば非常に大きい値であり、映像信号である
フレームの周期に合せてパイプライン処理等の高速の演
算系が用いられている。

しかし、ハードウェアの簡素化は大きな課題であり、
例えば特開昭63−181585号公報の『TV信号の動き補償フ
レーム間符号化装置』では演算量の低減の目的で木探索
形の動き補償演算を行う方法が提案されている。

木探索形動き補償演算方法は、第11図に示すように、
動きベクトル探索範囲（４）内を等間隔に低い密度の第
１の探索対象ブロック（○）を配置し、その中で最小歪
を与えるブロック○を検出すると、次にそのブロック○
を中心とした狭い領域内で第２の探索対象ブロック
（□）を配置し、その中で最小歪を与えるブロック□を
検出し、更にそのブロック□を中心とする領域内で第３
の探索対象ブロック（△）を設定して最小歪を与えるブ
ロック△を検出し、最終的に動きベクトル探索範囲
（４）内で最小歪を与えるブロック△を特定するという
ものである。

この場合の演算量S2は S2＝｛９×Ｌ×ａ＋９×ｂ｝×３ …（105） となる。従って、前述と同じ条件下では S21800 マシンサイクルとなり、この木探索形の動き補償演算方
法は全探索形より演算量が少なくて済む。

［発明が解決しようとする課題］ 従来の動き補償演算方法は、以上のように構成されて
いるので、動き補償演算で確実性の高い全探索を行おう
とすると演算量が増大してハードウェアの構成が大規模
となり、一方木探索等により演算量を低減した場合、最
小歪ブロックの検出性能が劣る、すなわち最初の低密度
の探索時のマッチングの過程で本来の最小歪ブロックの
位置と離れた位置のブロックが選択される可能性があ
り、目標とする最小歪量に達せず相関無しの判定がなさ
れるケースが増大して非効率な伝送を享受せざるを得な
い等の問題点があった。

この発明は、上述した課題を解決するためになされた
もので、最小歪ブロックの検出性能を劣化させることな
く演算量を少なくしてハードウェアの簡素化と小型化を
図ることのできる動き補償方式を得ることを目的とす
る。

［課題を解決するための手段］ この発明に係る動き補償方式は、入力フレームを予め
定められた大きさの入力ブロックに分割し、この入力ブ
ロックを前回フレームにおける探索対象ブロックと比較
することによって、動きベクトルを検出するフレーム間
符号化装置における動き補償方式であって、上記入力ブ
ロックを複数の平均値ブロックに分割し、各平均値ブロ
ックについてその平均値ブロック内の画素データの平均
値を求め、入力ブロックについてき平均値パターンを算
出し、入力ブロックのフレーム内位置に基づいて、その
入力ブロックに対する前回フレーム内における動きベク
トル探索範囲を設定し、この動きベクトル探索範囲内に
複数個の探索対象ブロックを低密度で配置し、配置され
た探索対象ブロックを複数の平均値ブロックに分割し、
各平均値ブロックについてその平均値ブロック内の画素
データの平均値を求め、各探索対象ブロックについての
平均値パターンを算出し、入力ブロックの平均値パター
ンと、各探索対象ブロックの平均値パターンとの間の歪
量を求め、求められた歪量から最適探索対象ブロックを
検出し、検出された最適探索対象ブロックの前回フレー
ム内の位置に基づいて、その周辺に限定化探索対象ブロ
ックを高密度で配置し、入力ブロックと各限定化探索対
象ブロック間の歪量を両者の画素データに基づきより細
かい単位で求め、求められた歪量から動きベクトルを検
出するものである。

［作用］ 上述構成に基づき、動き補償部は動きベクトル探索範
囲内において、探索対象ブロックを低密度で配置して計
算対象動きベクトルによりこれらブロックの平均値間歪
量が最小となるブロックを最小歪ブロックとして検出
し、該最小歪ブロックを中心として限定化探索範囲を高
密度の探索対象ブロックとして設定し、該ブロックの中
から動きベクトルを検出し、先ず平均値パターンで歪量
を比較することで高い精度での最小歪ブロックの存在位
置の絞り込みが可能となり、その後に限定化された領域
内で高密度の動きベクトル探索を行うことで演算量を抑
制しながら高い精度の検出を行う。

［実施例］ 以下、図面に沿って、この発明の一実施例について説
明する。

なお、前述した部分と同一又は相当部には同一符号を
付して説明を省略する。

第１図は動き補償フレーム間符号化装置の構成図であ
る。図において、（17）は再生フレーム１フレーム分に
ついて、動き補償に用いる１×l2サイズのブロックを
均等に分割できる所定の大きさの小ブロック（平均値ブ
ロック）単位にその平均値ブロック内画素の平均値（1
8）を求める平均値計算回路、（19）は１フレーム分の
平均値ブロック単位の平均値（18）を保持する平均値フ
レームメモリである。

そして、第２図は動き補償部（５）の内部構成図であ
り、図において、（21）は符号化対象入力ブロック内で
上記平均値ブロック単位の平均値（18）を計算する平均
値計算回路、（23）は該入力ブロック内の平均値ブロッ
クの各平均値を１つのパターンとして保持する入力平均
値メモリである。

また、（24）は入力ブロックの平均値パターンと上記
平均値フレームメモリ（19）内の平均値パターンとの間
で歪量計算を行いかつ最小歪ブロックを検出する平均値
パターンマッチング回路、（26）は入力ブロックとフレ
ームメモリ内探索範囲内ブロックとの間で画像間歪量を
計算して最小歪ブロックの位置検出を行う画素パータン
マッチング回路である。

更に、第４図及び第５図は平均値パターン最小歪によ
る第１段目動きベクトル検出方法の説明図であり、図に
おいて、（20）は再生フレーム平均値パターンの探索範
囲、（22）は入力ブロックの平均値パターン、（27）は
平均値ブロックである。

ついで、本発明の作用を説明する。

入力信号（１）は従来同様の動作により符号化部
（９）にて符号化されかつ復号化部（11）にて復号化さ
れて復号再生データ（13）となり、該復号再生データ
（13）は従来同様にフレームメモリ（14）に格納される
と共に１フレームをk1×k2の大きさの平均値ブロック
（27）に分割され、該平均値ブロック毎に画素の平均値
を求められる（第１図参照）。

そして、この時の平均値ブロックを動き補償に用いる
１×l2の大きさのブロックを均等に分割できるサイズ
とすると、１×l2ブロック中にＪ（Ｊ＝（１×l2）
／（k1×k2）の平均値が存在する。

なお、この際の各平均値ブロック内の画素平均値aj
（ｊ＝１〜Ｊ）をまとめて１つのパターンＡとして扱う
ことにする。

すなわち、Ａ＝｛a1、a2、……aJ｝とする。

ついで、動きベクトル検出の方法は、第３図のフロー
チャートに示すように、第１段目として探索動きベクト
ルの配置間隔を平均値ブロックのサイズに合せて最小歪
ブロックを探索する（ステップS1）（第６図参照）。

そして、入力ブロック（３）に対しては平均値計算回
路（21）で平均値パターン（22）を算出しておき、この
入力ブロック平均値パターンと、動きベクトルの位置の
ブロックに相当する前フレームの平均値パターンとの間
でマッチング歪計算及び最小歪ブロック検出を平均値パ
ターンマッチング回路（24）にて実行する（ステップS
2）（第５図参照）。

平均値歪量は以下の式で示される。

なお、入力ブロック平均値パターンＡ＝｛a1、a2、…
aJ｝、再生フレーム平均位置パターンAy＝｛ay1、ay2、
…aJ｝とする。

この際、平均値パターンマッチングを用いることによ
り演算量は１入力ブロック及び再生フレームブロック当
りで平均値算出に１×l2マシンサイクル、平均値パタ
ーンマッチング１回当りＪマシンサイクルとなる。

従って、第１段目探索において、所要演算量C1は、 C1＝（１×l2）×（M1＋１） ＋M1＋Ｊ×ａ＋M1×ｂ …（108） となる。Miは第１段目探索動きベクトルの個数である。

次に、画素パターンマッチング回路（26）における動
き検出ステップは、第７図に示すように、平均値パター
ンマッチング回路（24）で求めた最小歪ブロック（28）
を中心としてml×nlのサイズを有する限定化探索範囲
（29）を設定し、該範囲内において高密度に探索対象と
なる動きベクトルを配置する（ステップS3）。

限定化探索範囲（29）内での演算量C2は ｛（2ml＋１）（2nl＋１）×Ｌ×ａ｝ …（109） と、比較処理の （2ml＋１）（2nl＋１）＋ｂ との和となる。

ここで、１＝８、l2＝８、ｍ＝８、ｎ＝８、平均値
ブロックk1＝４、k2＝４、演算マシンサイクル数ａ＝１
（差分絶対値）、ｂ＝２（比較処理）とすると、探索ベ
クトル個数M1＝25個、Ｊ＝４個となる。

従って、第１段目における所要演算量C1は約1800とな
る。

また、第２段目の探索において限定化探索範囲をm1＝
３、n1＝３とすると、第２段目における所要演算量C2は
約3200マシンサイクルとなる。

以上により、１入力ブロック当り5000マシンサイクル
となり、従来の全探索の演算量の約1/4となる。

［発明の効果］ 以上発明したように、この発明によれば動きベクトル
探索範囲の絞り込みにブロック内平均値パターン間歪量
を用いることで絞り込み時点でのマッチング誤りを防ぐ
と共に絞り込まれた領域に対してのみ高密度の動きベク
トル探索を行うので、演算量を減少すると共に装置の簡
素化が可能となり検出精度の高い動きベクトルの検出が
可能な動き補償方式が得られる効果がある。

【図面の簡単な説明】

第１図は本発明に係る動き補償フレーム間符号化装置の
構成を示す機能ブロック図、第２図は動き補償部の内部
構成を示す機能ブロック図、第３図は本発明の作用を示
すフローチャート図、第４図は平均値パターン算出の説
明図、第５図は第１段目の平均値パターンを用いた動き
ベクトル検出の説明図、第６図は平均値パターンによる
動きベクトル検出時の探索動きベクトルの配置説明図、
第７図は第１段目の動きベクトル検出により限定された
探索範囲での第２段目の動きベクトル検出の説明図、第
８図は従来の動き補償フレーム間符号化装置の構成を示
す機能ブロック図、第９図（ａ）、（ｂ）は従来の動き
ベクトル検出方法の説明図、第10図は従来の全探索形動
きベクトル検出方法の説明図、第11図は従来の木探索形
動きベクトル検出方法の説明図である。 図において、（５）は動き補償部、（17）はサンプリン
グ回路、（19）はサンプルデータメモリ、（28）は第１
段目検出最小歪ブロックである。 なお、図中、同一符号は同一、又は相当部分を示す。

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】入力フレームを予め定められた大きさの入
   力ブロックに分割し、この入力ブロックを前回フレーム
   における探索対象ブロックと比較することによって、動
   きベクトルを検出するフレーム間符号化装置における動
   き補償方式であって、 上記入力ブロックを複数の平均値ブロックに分割し、各
   平均値ブロックについてその平均値ブロック内の画素デ
   ータの平均値を求め、入力ブロックについての平均値パ
   ターンを算出し、 入力ブロックのフレーム内位置に基づいて、その入力ブ
   ロックに対する前回フレーム内における動きベクトル探
   索範囲を設定し、この動きベクトル探索範囲内に複数個
   の探索対象ブロックを低密度で配置し、 配置された探索対象ブロックを複数の平均値ブロックに
   分割し、各平均値ブロックについてその平均値ブロック
   内の画素データの平均値を求め、各探索対象ブロックに
   ついての平均値パターンを算出し、 入力ブロックの平均値パターンと、各探索対象ブロック
   の平均値パターンとの間の歪量を求め、求められた歪量
   から最適探索対象ブロックを検出し、 検出された最適探索対象ブロックの前回フレーム内の位
   置に基づいて、その近傍に限定化探索対象ブロックを高
   密度で配置し、入力ブロックと各限定化探索対象ブロッ
   ク間の歪量を両者の画素データに基づきより細かい単位
   で求め、求められた歪量から動きベクトルを検出するフ
   レーム間符号化装置における動き補償方式。