(57)【特許請求の範囲】
【請求項１】
画像を任意形状の領域に分割した上で該分割領域の各動ベクトルを用いて動き補償予測符号化を行う領域分割符号化を目的とする動き推定領域分割方法において、
前記各動ベクトルの取り得る複数の領域パターンのおのおの毎に、前記分割領域の形状情報量、及び、該各動ベクトルの予測誤差情報量と動ベクトル情報量とを求める第１のステップと、
前記各動ベクトルを段階とし該各動ベクトルの取り得る前記複数の領域パターンを累積した累積領域パターンを状態とする動的計画法により、前記の求められた形状情報量・予測誤差情報量及び動ベクトル情報量の最小全発生情報量を求める第２のステップと、
該最小全発生情報量に対応する前記複数の領域パターンのいずれかにより前記領域分割符号化を実行させる第３のステップと、
を具備することを特徴とする画像の動き推定領域分割方法。
【請求項２】
前記各動ベクトルの取り得る複数の領域パターンの数をあらかじめ制限しておくステップをさらに含むことを特徴とする請求項１に記載の画像の動き推定領域分割方法。
【請求項３】
前記各動ベクトルの種類をあらかじめ制限しておくステップをさらに含むことを特徴とする請求項１に記載の画像の動き推定領域分割方法。
【請求項４】
画像を任意形状の領域に分割した上で該分割領域の各動ベクトルを用いて動き補償予測符号化を行う領域分割符号化を目的とする動き推定領域分割装置において、
前記各動ベクトルの取り得る複数の領域パターンのおのおの毎に、前記分割領域の形状情報量、及び、該各動ベクトルの予測誤差情報量と動ベクトル情報量とを求める第１の手段と、
前記各動ベクトルを段階とし該各動ベクトルの取り得る前記複数の領域パターンを累積した累積領域パターンを状態とする動的計画法により、前記の求められた形状情報量・予測誤差情報量及び動ベクトル情報量の最小全発生情報量を求める第２の手段と、
該最小全発生情報量に対応する前記複数の領域パターンのいずれかにより前記領域分割符号化を実行させる第３の手段と、
を具備することを特徴とする画像の動き推定領域分割装置。
【請求項５】
前記各動ベクトルの取り得る複数の領域パターンの数をあらかじめ制限しておく手段をさらに含むことを特徴とする請求項４に記載の画像の動き推定領域分割装置。
【請求項６】
前記各動ベクトルの種類をあらかじめ制限しておくステップをさらに含むことを特徴とする請求項４に記載の画像の動き推定領域分割装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像の符号化方法及び装置に関し、特に、動画像の領域分割に基づく動き補償予測符号化に好適な、動画像の動き推定領域分割方法及び装置に関する。
【０００２】
【従来の技術】
領域分割に基づく動き補償予測符号化においては、形状情報量まで含めた全発生情報量を最小とするべく領域分割・動き推定処理を行う必要がある。
従来の動き補償予測のための領域分割法としては、まず何らかの方法でクラスタリング（clustering）を行い、その後ある規範で領域結合を行う分離・統合法（split and merge 法）が代表的である。しかし、この方法では、動き情報を考慮していない最初の分離（split ）の段階に性能が大きく左右されるという点で、改善の余地が大きいといえる。〔split and merge 法の詳細に関しては、「画像処理ハンドブック」（昭晃堂）等を参照〕。
従来の方法であるSplit and merge 法では、図５（ａ）に示したように、まず画像を細かく分割した後、何らかの規範で図５（ｂ）に示すように統合するという手順を取る。この統合する規範としては、予測誤差自乗和の大小などが用いられる。
【０００３】
【発明が解決しようとする課題】
領域分割に基づく動き補償予測符号化においては、動き推定と領域分割とを互いに密接に関連付けながら同時に処理し、その結果の分割形状情報量・動ベクトル情報量・予測誤差情報量の和を最小にすることが望ましい。
しかしながら、前記の如き従来の方法では、まず分割したものを再度統合する為、始めの分割の段階に、全体の性能が大きく左右されることになる。分割の規範としては、画像のテクスチャ（texture ：模様）などに基づき、動き情報などは勘案されない為、動き補償予測符号化の目的からは、最適な領域分割・動き推定とはならない。
【０００４】
本発明の目的は、領域分割に基づく動き補償予測符号化において、動き推定と領域分割を符号化効率を最大にするように、すなわち、分割形状情報量・動ベクトル情報量・予測誤差情報量の和に相当する発生情報量を最小にするように実行する動き推定・領域分割方法及び装置を提供することにある。
【０００５】
【課題を解決するための手段】
前記した目的を達成するために、本発明による画像の動き推定領域分割方法は、画像を任意形状の領域に分割した上で該分割領域の各動ベクトルを用いて動き補償予測符号化を行う領域分割符号化を目的とする動き推定領域分割方法において、
前記各動ベクトルの取り得る複数の領域パターンのおのおの毎に、前記分割領域の形状情報量、及び、該各動ベクトルの予測誤差情報量と動ベクトル情報量とを求める第１のステップと、
前記各動ベクトルを段階とし該各動ベクトルの取り得る前記複数の領域パターンを累積した累積領域パターンを状態とする動的計画法により、前記の求められた形状情報量・予測誤差情報量及び動ベクトル情報量の最小全発生情報量を求める第２のステップと、
該最小全発生情報量に対応する前記複数の領域パターンのいずれかにより前記領域分割符号化を実行させる第３のステップと、
を具備することを特徴とする構成を有している。
また、本発明による画像の動き推定領域分割装置は、画像を任意形状の領域に分割した上で該分割領域の各動ベクトルを用いて動き補償予測符号化を行う領域分割符号化を目的とする動き推定領域分割装置において、
前記各動ベクトルの取り得る複数の領域パターンのおのおの毎に、前記領域パターンの形状情報量、及び、該各動ベクトルの予測誤差情報量と動ベクトル情報量とを求める第１の手段と、
前記分割領域の前記各動ベクトルを段階とし該各動ベクトルの取り得る前記複数の領域パターンを累積した累積領域パターンを状態とする動的計画法により、前記の求められた形状情報量・予測誤差情報量及び動ベクトル情報量の最小全発生情報量を求める第２の手段と、
該最小全発生情報量に対応する前記複数の領域パターンのいずれかにより前記領域分割符号化を実行させる第３の手段と、
を具備することを特徴とする構成を有している。
【０００６】
【発明の実施の形態】
本発明によれば、画像を任意形状の領域に分割した上でその分割領域に含まれる各動ベクトルの動き候補予測符号化を行う領域分割符号化のために、まず各動ベクトルの取り得る複数の領域パターンのおのおの毎に、その分割領域の形状情報量、及び、該動ベクトルの動ベクトル情報量と予測誤差情報量とが計算され、テーブルに格納される。ついで、各動ベクトルを段階とし、前記領域パターンを累積した累積領域パターンを状態とする動的計画法を適用することにより、全発生情報量を最小とするような最適な動き推定・領域分割の統合化同時処理方法及び装置が実現できる。
【０００７】
【実施例】
次に、本発明の実施例を図１を参照して説明する。本実施例では、画像を任意形状の領域に分割した上でその分割領域の各動ベクトルの動き候補予測符号化を行う領域分割符号化のために、まず、各動ベクトルの取り得る複数の領域パターンのおのおの毎に、発生情報量が見積もられ（Ｓ１）、テーブルに記憶される（Ｓ２）。次に、動ベクトルを段階（stage ）とし、領域パターンを累積した累積領域パターンを状態（state ）とする動的計画法（dynamic programming ）が適用され（Ｓ３）、最適領域分割・動き推定が実現される。
動的計画法については、例えば、〔杉山  昌平著「動的計画法」（日科抜連出版社，ＯＲライブラリ８）〕に詳述されている。
具体的な簡単な例として、図２に示す４個の小ブロックからなる画像を考える。
この４個の小ブロックからなる画像における、各動ベクトルが取り得る複数の領域パターンの種類は、例えば同図２に示したように、各小ブロックに「黒」が入るか入らないかで計２の４乗＝１６通りに制限されることとなる。以下この１６通りの種類の領域パターンが「前記各動ベクトルが取り得る複数の領域パターン」である場合を具体例として、本発明をさらに詳細に説明する。
【０００８】
【表１】
0003781075.tif 000002
【０００９】
次に、表１に示したように、各動ベクトルＶi （例えばｉ＝１，２，３）の取り得る複数の領域パターンＰi のおのおの毎の発生情報量ｒ（ｉ，ｊ）が計算されテーブルに格納される。この時の発生情報量ｒ（ｉ，ｊ）は、その複数の動ベクトルＶi によるその複数の領域パターンＰj の予測誤差情報量Ｉ1 と、その複数の領域パターンＰj の形状情報量Ｉ3 とに、動ベクトルＶi の情報量Ｉ2 を加算したものとなる。この場合の形状情報量Ｉ3 は、その複数の領域パターンのおのおのに固有のものであり、例えば、差分チェーン符号化での符号量であらわされる。差分チェーン符号化は、各サンプル値を（１）方向成分抽出、（２）方向差分抽出、（３）不等長符号化の符号化ステップで符号化するものである。動ベクトル情報量Ｉ2 は、例えば連結領域当たり固定のビット数であらわすことができる。図２のパターン１１については, 連結領域数は２なので、１連結領域当たりのビット数を２ビットとすると、２×２＝４ビットとなる。
【００１０】
次に、動ベクトルを「段階（stage)」とし、領域パターンＰj を累積した累積領域パターンを「状態（state)」（又は節点：nodeとも称されている）とする動的計画法を適用する。表１を元に、動ベクトルを「段階」とし、累積領域パターンを「状態」とする動的計画法は、以下のようになる。
【００１１】
まず、各動ベクトルＶi （ｉ＝１，２，３）の取り得る複数の領域パターンＰj 毎の全発生情報量ｆi （ｐj ）の最適化漸化式は、
【数１】
0003781075.tif 000003
となる。ここに、ｐj −ｐt は、複数の領域パターンｐj から領域パターンｐt を除いた残りの部分を示す領域パターンであり、図２に示す前記１６種類のパターンのどれかに一致する。
【００１２】
式（１）ないし式（３）を順次計算すると、次の表２，表３，表４が得られる。
【００１３】
【表２】
0003781075.tif 000004
【００１４】
【表３】
0003781075.tif 000005
【００１５】
【表４】
0003781075.tif 000006
【００１６】
表４の全発生情報量ｆ3 （ｐ16）は、その最小値が「３」であることを示す。この時同時に動ベクトルＶ3 の取り得る領域パターンがＰ3 （又はＰ15）に決定される。すると、これから動ベクトルＶ1 ，Ｖ2 の占めるパターン（累積領域パターン）の最小値が表３からＰ7 （又はＰ16）に決まるので、発生情報量ｆ2 （ｐj ）を示す表３のそれに対応する部分を参照すれば、動ベクトルＶ2 の領域パターンの最小値がＰ7 に決まる。同様にして、動ベクトルＶ1 の領域パターンの最小値がｆ1 （ｐj ）を示す表２よりＰ15（又はＰ3 ）に定まる。
以上のようにして、全発生情報量を最小とするような各動ベクトルの領域パターンが決定される。すなわち、領域分割・動き推定の最適統合同時処理が実行される。
【００１７】
以上の処理において、例えば、図２に示す如き各動ベクトルの取り得るパターン数もしくは種類数に個別に制限を設けることにより、漸化式において最小値を求めるための計算回数、及び状態数を減少させることができ、簡略化することができる。
また、動ベクトル数（上記の例では３個）は、通常の画像符号化では、５１２個程度存在するが、これにも制限を設けることにより、簡略化が可能である。
【００１８】
図３，図４を参照して、本発明の実施例についてさらに具体的に説明する。
図３は実施例の構成を示すブロック図であり、図４はその動作を説明するためのフローチャートである。
入力端子１１から動ベクトルＶi が入力する（Ｓ１１）。回路４からは、領域パターンＰj 毎に、入力された動ベクトルＶi の予測誤差情報量Ｉ1 が算出され、回路１からは領域パターンＰj のおのおの毎の動ベクトル情報量Ｉ2 が算出され、回路２のテーブルには領域パターンＰj のおのおの毎の形状情報量Ｉ3 が用意されている（Ｓ１２）。これらの動作において、回路３では領域パターンＰi の更新を行い（Ｓ１３）、また動ベクトルＶi の更新を行う（Ｓ１４）ことにより、回路３から各動ベクトルの取り得る複数の領域パターンのおのおの毎の情報テーブルが生成され、回路５の情報テーブルに記憶される。
【００１９】
次に、回路６〜７の計算回路で複数の領域パターンＰj を累積した累積領域パターン毎の発生情報量が算出され、回路９で最小値をとるパターンが決定され、回路８にそのパターン及び情報量が記憶される（Ｓ１５）。最終段階の登録完了後、最適領域パターン選択回路１０が回路８のメモリ内容を参照して、各動ベクトルＶi 毎の占有領域を示す領域分割・動き出力情報を出力する（Ｓ１６）。
【００２０】
すなわち、Ｓ１１，Ｓ１２，Ｓ１３，Ｓ１４により、Ｓ１２の情報量計算は、全動ベクトルＶi ，全領域パターンＰj に対して行われる。次に、Ｓ１５において「動的計画法」を適用して、ステップＳ１６で結果を出力する。
【００２１】
【発明の効果】
以上説明したように、本発明によれば、動き補償予測符号化を目的とする領域分割・動き推定の最適化統合処理を実現することができる。すなわち、発生情報量を最小化する領域分割と動き推定が同時に実行できることとなる。
【図面の簡単な説明】
【図１】  本発明の実施例の動作を説明するためのフローチャートである。
【図２】  本発明を適用する画像の動ベクトル毎の領域パターンの例を示す図である。
【図３】  本発明の実施例を示すブロック図である。
【図４】  本発明の実施例の動作を説明するためのフローチャートである。
【図５】  従来の分離・統合法を説明するための図である。
【符号の説明】
１  領域パターン毎の動ベクトル情報量テーブル
２  領域パターン毎の形状情報量テーブル
３  情報量のテーブル生成回路
４  予測誤差情報量算出回路
５  動ベクトル・領域パターン毎情報テーブル
６  領域パターン１用計算回路
７  領域パターンｎ用計算回路
８  領域パターン及び発生情報量メモリ
９  最小判定回路
１０  最適領域パターン選択回路
１１  入力端子
【図１】
0003781075.tif 000007
【図２】
0003781075.tif 000008
【図３】
0003781075.tif 000009
【図４】
0003781075.tif 000010
【図５】
0003781075.tif 000011