(57)【特許請求の範囲】
【請求項１】
入力像の多層表示のためのパラメータを決定し、
パラメータが決定された多層表示に対し所望の縮小フィルターを用いて像の縮小を行い、
縮小像に対し縁の場所を探すためにラプラス演算を行って単位縁を検出し、検出した単位縁に基きマクロ縁を検出し、検出したマクロ縁を包み込む矩形領域毎に縁強度を算出する
ステップを含む画像の符号化方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は画像の符号化方法、特に、圧縮画像の符号化方法に関する。
【０００２】
【従来の技術及びその課題】
多層方式は、相異なる寸法の領域を持つ像表示を得る為の簡単な方法である。この表示は像の符号化、特に進み伝送（ｐｒｏｇｒｅｓｓｉｖｅ  ｔｒａｎｓｍｉｓｓｉｏｎ）を介しての像の圧縮に有用であり、その結果得られるトリー（ｔｒｅｅ）は、カッドトリー（ｑｕａｄｔｒｅｅ）符号化（Ｅ．Ｓｈｕｓｔｅｒｍａｎ及びＭ．Ｆｅｄｅｒ著“Ｉｍａｇｅ  ｃｏｍｐｒｅｓｓｉｏｎ  ｖｉａ  ｉｍｐｒｏｖｅｄ  ｑｕａｄｔｒｅｅ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ａｌｇｏｒｉｔｈｍ”ＩＥＥＥ  Ｔｒａｎｓ．Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，ｖｏｌ．３，ｎｏ．２，ｐｐ２０７−２１５，１９４４，他）を用いて伝送するのが普通である。
【０００３】
自然の像は可変量の細部及び情報を持つ異なる寸法の領域に分割することができる。像のこの様なセグメント分割は、像データの効率のよい符号化の為に好ましい。カッドトリー（ＱＴ）符号化は、像の分解、即ち多層化を表わす主要な方式であり、像を２次元の均質（ｈｏｍｏｇｅｎｏｕｓ）な方形領域に分割する。その分解がトリーをつくり、トリーの各ノードは４つの子を持つと共に像の一意的に限定された領域に関連する。根が像全体に関連する。ＱＴ符号化を像の圧縮の為に用いる時、その結果得られるトリーを符号化することが必要である。符号化手順は、トリー構造情報の符号化、及びノード／リーフ情報、即ちセグメント分割フラグの符号化を含む。各々のリーフに対し、対応する部分像（ｓｕｂｉｍａｇｅ）の強度を記述するパラメータを割当てる。勿論、像の画素は、それがＱＴコードに現われれば、常にリーフである。トリー構造の符号化は、１番下のレベル、即ち、許容し得る最小寸法のブロックの１つ前のレベルで終了すべきであり、このブロックは画素に等しいか又はそれより大きくなければならない。
【０００４】
しかし、ＱＴ符号化はその有用な性質を活用していない。或るブロックは、隣接するブロックが分割される時、部分ブロックに分割される尤度が一層大きい。この性質は、自然の像は、連続的な小さなブロックを用いて表わすべき何等かの物体を描くものであるのに対し、背景は一層大きなブロックで構成される事実によって説明される。言い換えれば、ＱＴコードには、更に圧縮することができる空間的な冗長度が存在する。これは、物体を簡潔に表現する手法を用いることにより、ＱＴ符号化よりも更に効率よく像の分解を行なうことができることを意味する。物体を表示するための幾つかの候補の一つとして、縁（エッジ）の情報がある。縁情報を用いる一つの方法では、線近似方法によって縁を抽出する（階層形縁検出）。従って、像の分解は各ブロックに縁が存在することに基づいて実施され、頭と肩の像の様な単純な物体の場面には有用であるが、冗長なオーバーヘッド、即ち、縁が、ＱＴ符号化より低い符号化効率を招くのが難点である。
【０００５】
【課題を解決するための手段及び作用】
本発明では、像の符号化の為の改良された多層化方式（Ｍｕｌｔｉｌａｙｅｒｉｎｇ  Ｓｃｈｅｍｅ）を提供する。縁は画素の精度で符号化しなくてもよく、セグメント分割の際の１番小さいブロック・レベルの精度であればよいから、縁の抽出は縮小された像（ｄｅｃｉｍａｔｅｄ  ｉｍａｇｅ）で行うことができる。その時、適切な多層化を達成しながら、メモリ空間並びに縁抽出用の計算の複雑さと共に、縁データも減らすことができる。
【０００６】
本発明の符号化方法は、入力像の多層表示のためのパラメータを決定し、パラメータが決定された多層表示に対し所望の縮小フィルターを用いて像の縮小を行い、縮小像に対し縁の場所を探すためにラプラス演算を行って単位縁を検出し、検出した単位縁に基きマクロ縁を検出し、検出したマクロ縁を包み込む矩形領域毎に縁強度を算出するステップを含む。
【０００７】
【実施例】
本発明に至った理論的考察を含め、一実施例を図面を参照して説明する。
【０００８】
先ずカッドトリー符号化について以下に説明する。
【０００９】
Ｌt,b を像の多層表示とする。ここでｔ及びｂは夫々トップ・レベル及びボトム・レベルを表わすパラメータであり、Ｔ＞ｂ≧０である。この時Ｌt,b は次の様に定義される。
【００１０】
【数１】
0003708218.tif 000002
ｌt,i は２i ×２i の寸法のブロックで構成された層であり、これは分解過程が、そのブロックについては、レベルｔで出発して、レベルｉで終わることを意味する。
【００１１】
次に変数を定義する。ｐt,i は、次に低いレベル、即ちレベルｉ−１で４個のサブブロックに分割される２i ×２i の寸法のブロックの数であり、ｑt,i は、レベルｉ−１より下でも同じ寸法のままにとどまる２i ×２i の寸法のブロックの数であり、この為、このｑt,i に対応するブロックが１t,i を構成する。入力像の寸法がＷ（幅）×Ｈ（高さ）の画素であると仮定し、像の画素の層をレベル０と表わす。その時、２つの変数の間の関係が反復方程式によって表わされる。
【００１２】
【数２】
0003708218.tif 000003
【００１３】
ｔは次の条件を満たす。
【００１４】
【数３】
0003708218.tif 000004
【００１５】
パラメータとしてｔ＝５及びｂ＝２である時の多層表示の一例を、２本の縁線が存在する図１に示す。
【００１６】
各々のレベルでの符号化の順序は、正方形の像の場合とは若干異なり、同じ寸法のブロックはラスター走査式の順序になる。即ち、左から右に、そして上から下へである。親のノードに‘１’を割当て、リーフに‘０’を割当てる。図２は、図１に示したＬ5,2 に対応するＱＴコードを示す。ｐt,i が黒のノードの数に等しく、ｑt,i がレベルｉにおける白のノードの数に相当する。
直接的な符号化を想定して、ＱＴ符号化を用いて像の分解を表わす為に使わなければならない速度Ｒt,b 〔ビット〕は次の様になる。
【００１７】
【数４】
0003708218.tif 000005
【００１８】
図２に見られる様に、ＱＴ符号化を用いて、図１に示す多層表示Ｌ5,2 を符号化するには５４ビットを必要とする。本発明は、５４ビットより少ないビットでＬ5,2 を表示することを可能にする。
【００１９】
図１において、縁がこの図に示される様に抽出される場合、その分解過程は縁情報だけに基づく。一つのブロック内に縁が存在すれば、そのブロックは４つの子ブロックにセグメント分割される。本発明においては、上−下手順と共に下−上手順（即ち、セグメント分割がボトムレベルｂから出発する）を用いることができる。その結果の分解は、縁及びパラメータが一定である限り、どの手順を採用しても同一である。
【００２０】
図３は、本発明の一実施例に係る符号器のブロック図である。像信号がパラメータ決定部１に入力し、像縮小部２を介して縁抽出部３に入力される。縁抽出部３は縁データを多層化部４へも出力する。多層化部４は、縁抽出部３から出力された縁データを基に、フレームを多層化する。最初はフレームを大きなブロック（トップ・レベル：ｔで規定されたサイズのブロック）で均等分割し（これを第ｔ層と呼ぶ）、各ブロックにマクロ縁が存在すれば４つの小ブロック（第ｔ−１層に相当）に分割する。そして、この操作をボトム・レベル：ｂで規定された層に到るまで繰り返す。符号化部５は多層化部４からの入力及び像信号とに基き視感度データ（Ｌｕｍｉｎｏｓｉｔｙ  Ｄａｔａ）を出力する。
【００２１】
以下に各ブロックの機能を詳述する。
【００２２】
（１）  パラメータ決定
パラメータ決定部１において、入力像の多層表示Ｌt,b のためのパラメータが決定される。
ｄを、縮小フィルタを用いて、水平及び垂直の両方向に入力像が係数１／ｄだけ部分標本化される様にする縮小係数とすると、ボトム・レベルである値ｂはｌｏｇ2 ｄに等しいか又はそれより大きくなることが望ましい。これは、その結果得られる分解が主符号化過程、即ち、符号化部５における適応ブロックをベースとした符号化にとって適切である様に保証するために、縁の場所の特定を十分精密にする必要があるからである。
【００２３】
（２）  像の縮小（Ｉｍａｇｅ  Ｄｅｃｉｍａｔｉｏｎ）
縮小された像に縁の抽出を適用することは、縁データ、計算の複雑さ、並びに像分解の為のメモリ空間が減少する点で利点がある。特に、像データについて云うと、１／４寸法像、即ちｄ＝２を使う時、縁データを１／３に減少することができる。図４は、ｄ＝２として、図１の縮小された像を用いた同様な分解の結果を示す。この場合、２つの縁が組合さって１つの縁になるので、多層表示のデータ量は、もと（図１参照）に比べて大体半分の寸法に減少させることができる。縁の数が減少することは、主に全体的なデータの減少に寄与し、これに対して縁データに対するコード長の変化は、データの減少に対する影響が少ない。使う縮小フィルタは符号器の選択に任される。これは、フィルタがこの後の過程、即ち縁の抽出に大した影響がないからである。
【００２４】
像縮小部２においては、パラメータが決定された多層表示に対し所望の縮小フィルタを用いて像の縮小を行う。更に、分解過程が縮小された像に適応される。実際、こうして得られた分解は若干変更されている。即ち、１つの４×４寸法のブロックはそのまま（図４参照）である。然し、この４×４寸法のブロックは、像の範囲全体の内の僅か１％を占めるにすぎず、この為、この違いは全体的な符号化の性能の低下を殆ど招かない。
【００２５】
（３）  縁の抽出
【００２６】
図５に縁抽出部３の内部ブロック図を示す。
【００２７】
縁の場所を突き止める為、最初に周知のラプラース演算子をもとの像に適用し（ラプラス・フィルタ６）、その後、強度変化が大きい位置を表わす２進像、即ち縁を、μ＋Ｋ・σを用いた閾値作用によって求めることができる。ここでμ，σ及びＫは、夫々平均、微分空間の標準偏差及び係数である。一例として、８方向の小さなセグメントのパターンが図６に示されており、これらはテンプレートＴn （ｎ＝０，１…７）によって表わされており、各々の入口（ｊ，ｋ）がｔn （ｊ，ｋ）で表わされている。
【００２８】
ｊ，ｋ＝０，１，２，３，４として、λ（ｘ＋ｊ，ｙ＋ｋ）で表わされる５×５画素領域で構成される２進像内の部分領域をΛ（ｘ，ｙ）とする。テンプレートＴn とこのΛ（ｘ，ｙ）の間の相互相関Ｒn （ｘ，ｙ）は次の式によって計算することができる。
【００２９】
【数５】
0003708218.tif 000006
【００３０】
この後、Ｒn （ｘ，ｙ）が８に等しいか又はそれより大きくなる様なｎが存在すれば、ｎビット平面内の座標（ｘ，ｙ）の所でフラグを高にする。ここでｎは０から７まで変化する。これは、テンプレートＴn が座標（ｘ，ｙ）で符号パターンとして検出されたことを示す。この過程を２進像全体に適用しなければならない。こうして単位縁が得られる（単位縁検出７）。
【００３１】
次にマクロ縁検出８について説明する。
【００３２】
単位縁を抽出した後、図７に示す様に、マクロ縁の検出が行なわれる。単位縁を接続して、１６方向に、即ち１８０°÷１６＝１１．２５°の間隔で定められたマクロ縁にする。検出の出発点は、８の内の任意のビット平面のフラグが作用している画素と定めることができる。こう云う点をラスター走査式に求めると、出発点より下に接続される探索区域を局限することができる。
【００３３】
ｎビット平面内のフラグが作用している出発点が見付かったと仮定すると、検出過程の方向Ｎは、Ｎ＝２ｎに従って定められる。この方向から次の探索動作が適用される。探索動作の前にマクロ縁の方向を予め決定するのはリスクがあるので、考えられる３つの方向、即ち、Ｎ，Ｎ−１及びＮ＋１の中から、最も起こりそうな方向を選ぶ。考えられる各々の方向で、各々に方向に沿って単位長Ｌ（単位）ごとにある各々の接続点（図７参照）で、マクロ縁が接続されているかどうかを決定する。ｎ，（Ｎ−１）／２又は（Ｎ＋１）／２の何れかのビット平面内でフラグがその接続点又はその近辺、即ち隣り合う８個の画素で作用していれば、マクロ縁を接続点まで伸ばす。こうして求められた３つの候補のマクロ縁の内、１番長いものを符号化すべきマクロ縁とする。一旦マクロ縁が検出されると、同様なマクロ縁を抽出することを避ける為の一種の後処理が適用され得る。抽出されたマクロ縁、並びにｎ，（Ｎ−１）／２又は（Ｎ＋１）／２の何れかのビット平面内の隣り合う８個の画素に対応する一連の画素を中立にする。これは、マクロ縁を減衰させる役割を果たし、像内の抽出されたマクロ縁の数を減らすのに大いに助けになる。
【００３４】
次に強度収集９について説明する。
【００３５】
抽出されたマクロ縁は、ブロックのセグメント分割を行なう時に同等に重要であると見做すことができるが、人間の視覚系の或る性質を考慮に入れた知覚上の順序付けに従ってそれらに等級を付けるのがより妥当である。ここでは、低輝度領域に於ける所定の輝度変化は、高輝度領域に於ける同じ輝度変化よりも、一層目に付きやすく、従って重要であるとするウエーバの法則を採用する。マクロ縁を求めたら、或る延長部Ｂext をもってマクロ縁を包み込む矩形領域を縁ベルトとして定める。縁ベルトの一例が図８に示されており、この図では、マクロ縁と平行な軸線及びマクロ縁に対して垂直な軸線を、夫々ｐ及びｑで示してある。こうして、縁ベルト内にある画素値をε（ｐ，ｑ）で表わすことができる。
【００３６】
一般的に、実際の縁は縁ベルト内のマクロ縁に沿って存在すると仮定してよい。ウエーバの法則から導き出した縁強度情報を求める為、各々の縁ベルト内でグレースケールの変化を検査する。（ｉ）縁ベルト全体の中でφで表わすグレー・レベルの平均値を計算する。（ｉｉ）マクロ縁に対して垂直な各々の軸線で、最小及び最大のグレースケールを見付け、こうして夫々低い方の強度δ0 及び高い方の強度δ1 を求める。
【００３７】
【数６】
0003708218.tif 000007
【００３８】
【数７】
0003708218.tif 000008
ここでτは縁ベルト内にある軸線ｐに沿った画素の数を表わす。
【００３９】
段形縁（ｓｔｅｐ−ｅｄｇｅ）の簡略例を図９に示すが、この図では、実際の縁の場所が太線で追跡され且つ表示されている。ｑ＝０である一連の画素がマクロ縁に対応することに注意されたい。
【００４０】
Ｆをもとの像に於けるグレースケール関数とする。次に、縁ベルト内で有意でなければならないコントラストＣをＦで定義する。
【００４１】
【数８】
Ｃ＝ΔＦ／Ｆ                                        （８）
【００４２】
抽出された各々のマクロ縁に対し、式（８）は上の計算によって求められた統計を用いて、近似的に書直すことができる。
【００４３】
【数９】
Ｃ＝（δ1 −δ0 ）／φ                              （９）
【００４４】
ウエーバの法則によると、マクロ縁の周りの視覚的な感度は、上に定義したコントラストＣに比例する。次に、コントラストＣが視覚的な感度の大きさを正しく量的に表わすと云う仮定に基づいて、ＩW で表わす縁強度の考えを導入する。
【００４５】
【数１０】
0003708218.tif 000009
【００４６】
そのコントラストがθ0 未満である様なマクロ縁は、人間の知覚にとって重要度が劣り、従って像のセグメント分割にとっても重要度が劣ると考えられるので、縁データから取除くことが望ましい。縁強度は、一層高い強度のマクロ縁の周りの領域が一層細かい分解能、即ち一層小さいブロックで表わされる様にするいわゆる知覚を基本とした多層化を提供することができる。更に、各々の縁がその強度値に従った以下の太さを持つことができる様にする方式を実現することも可能である。
【００４７】
【数１１】
0003708218.tif 000010
【００４８】
表１はマクロ縁当たりの符号化メッセージに関する表である。出発点に関するメッセージは適当な符号化方式を使うことによって更に圧縮することができる。
【００４９】
【表１】
0003708218.tif 000011
【００５０】
本実施例においては、多層化部４及び符号化部５により、不要なマクロ縁が取り除かれる。その多層化手順を以下に要約する。
【００５１】
縁データをそれに相当するカッドトリーに変換する為に、各々のブロック内の縁の存在を単純に探索し、縁が存在するブロックでは‘１’を割当て、そうでなければ‘０’を割当てる。例えば、上から下への手順の場合、この探索動作はレベルｔからレベルｂ＋１まで適用され、こうして抽出されたマクロ縁に対応するＱＴコードが得られる。マクロ縁がＱＴコード、従って像の分解を一意的に限定することになる。
【００５２】
この手順の利点は、レベル・パラメータｔ及びｂを変えるだけで、分解能を一層細かくなる様に拡大したり、又は一層粗くなる様に減少することができることである。言い換えれば、同じ縁データを使って、種々の多層化を実施することができる。他方、均質性テストに基づく分解は、パラメータが変化する時始めからその過程を出発させなければならない。この性質は、最大符号化ビット速度の様な或る拘束の下での最適化が反復的に満たされる多重パス符号化過程にとって有利である。それは、１回目のパスで抽出された縁データを使った２回目のパスの後でも、縁に基づく多層化を行なうことができるからである。
【００５３】
本発明に係る方式の性能を評価する為に、２種類の実験を行なった。１つは、ＱＴ符号化及び本発明に係る方式双方で、分解トリーを伝送する為のビットをそれぞれ計数し比較することである。縁強度を分類する為のパラメータは、θ0 ＝０．２，θ1 ＝０．４，θ2 ＝０．８，及びθ3 ＝１．６に設定した。ＱＴ符号化に対するビット・カウントは、本方式によって出来る分解トリーが得られると仮定して、式（４）に基づいている。図１０は、ＭＰＥＧ−２標準化用のテストシーケンスである“フラワーガーデン”と“テーブルテニス”における多層表示のデータ速度を示す。本方式のアルゴリズムが、多層表示に対するデータの減少の点で、常にＱＴ符号化を凌いでいることが観察される。
【００５４】
もう一方は、一種の主観的な品質試験であって、縁に基づく分解によって生じた視覚的な効果を８×８寸法のブロックによる標本化と比較して示したものである。両方の場合、各々のブロックは平均輝度値によって表わした。公平な比較の為、縁強度の分類に関するパラメータは、本方式によるブロックの総数ができるだけ線形標本化の数に接近する様に、即ち５，２８０ブロックになる様に、経験的に且つ帰納的に決定した。表２が、この実験から得られた統計的な結果を示す。本方式が、ピーク信号対雑音比（ＰＳＮＲ）値の点で一層品質のよい像を提供することが観察される。
【００５５】
【表２】
0003708218.tif 000012
【００５６】
これらの２つの実験結果から、本発明に係る多層化方式は、比較的少ないデータ量で、像を符号化するのに適切な像の分解を行なうことが確認できる。
【００５７】
以上、本発明の一実施例につき説明したが、本発明はこれに限られるものではない。
【００５８】
以下に、他の発明に関し説明する。これはＭＰＥＧ画像信号の制御方法に関し、特に可変長コードの復号方法に関する。
【００５９】
ＭＰＥＧ−２ビットストリームを復号する時、ＤＣＴ係数の可変長コード（ＶＬＣ）復号が、ビットストリームの復号速度に最も制約を与える。これは、符号化されたビットストリームの５０％−８０％がＤＣＴ係数によって占められているからである。従って、ＶＬＣ復号を早くする努力がなされている。他方、必要とされるメモリ空間が、ハードウェアの実現を考慮すると別の重要な因子である。
【００６０】
ＶＬＣの復号は、種々のＶＬＣで構成される２進ストリングを元の数値に変換することである。１組のＶＬＣが各々の事象の発生確率に従って組立てられる。即ち、事象の持つ確率が高ければ高いほど、その事象には一層短いコードが割り当てられ、コード当たりの平均ビット数を最小限に抑えることができる様にしている。表３は、ＭＰＥＧ−２  ＤＣＴ係数に対するＶＬＣテーブルの一例を示す。可変長コードを復号することは、２進ストリング中の２つの相次ぐＶＬＣの間の位置として定義されるコード境界を見つけることに相当する。従来のＶＬＣ復号方法は、コード境界を探すのに、ビット・パターンのマッチングを用いるのが普通であった。
【００６１】
【表３】
0003708218.tif 000013
【００６２】
例えば、ＭＰＥＧソフトウェア・シミュレーション・グループ（ＭＳＳＧ）によって考えられた復号方法は、１６ビット長の２進ストリングを一度に読取って、１６ビット長のパターンマッチングを適用することにより、対応するＤＣＴ係数に変換する機構を採用している。これは高速の復号を達成するが、この機構は、冗長なコードが少なくない為、ＤＣＴ係数テーブルに対して大量のメモリ空間を必要とする。実際、４３２個のコード項目の内の２５９が冗長であり、驚くべきことに、これは６０％に相当する。これはＶＬＣ復号方法が、関連するコードをアドレスするのに線形オペレーションを用いている為である。時には、ＶＬＣ復号をハードウェアで実現する時、メモリ空間がきめ手になることがある。これは、復号は高価な高速メモリを使うことを必要とするからである。
【００６３】
本発明は、ビット・パターンのマッチングの代わりに、非線形写像オペレーション（ｎｏｎｌｉｎｅａｒ  ｍａｐｐｉｎｇ  ｏｐｅｒａｔｉｏｎ）を用いるＶＬＣ復号方法を提供する。本発明に係る復号方法では、入力ビット列中の区切りから所定ビット数の範囲内で連続する０ビットの個数をカウントし、上記カウントした値に基いた状態レジスタの内容を用いてＤＣＴ係数を復号するステップを含む。
【００６４】
又、複数のアドレスオペレーションを介して状態レジスタの内容を取得するステップを含む復号方法も開示する。
【００６５】
本発明の一実施例を、理論的考察を含め、図面を参照しながら説明する。
【００６６】
本発明に従うＶＬＣ復号方法は、いわゆる自己位置ぎめができる様に設計された非線形写像オペレーションを特徴とする。各々のオペレーションは、それが現在位置を正しく更新することができる様に関連するビット・シフト情報を持っている。従って、係数テーブルにコード長は必要ではない。現在位置は必ずしもコード境界と同じ所にある訳ではなく、単に、その後のオペレーションを再開する時の中間ビット位置を示すにすぎないことに注意されたい。この方法において考慮すべき別の点は、ＩＳＯ／ＩＥＣ  １３８１８−２で公表されているＤＣＴ係数テーブルの０とＤＣＴ係数テーブルの１の間の冗長度を全面的に活用しなければならないことである。言い換えれば、係数テーブルは、テーブル全体の規模を縮小することができる様に、冗長コードを取去る様に設計されていなければならない。本発明の一実施例に係る方法を図１１に示す。
【００６７】
図１１は、ＤＣＴ係数の復号が最大４段階で実行されることを意味し、最初の３つの各段階で、後述の表４の１６個のオペレーションのうち規定のものを用いて入力ビット列の情報を順次入手し、第４段階目でそれらの情報をもとに係数を復号することを示している。ここでは、スタート時点で、ゼロ・テーブルかワン・テーブルのうちどちらを使うかが定められていることが前提とされており、この１ビット情報を後述の式（１３）の状態レジスタＲの構成要素Ｘとして保持する。ゼロ・テーブルとワン・テーブルでは、復号法が異なる（図１２及び１３に各々処理手順を図示）。
【００６８】
詳述すると、ゼロ・テーブルとワン・テーブル共に、第１段階（ブロック２１）では、表４のｚｅｒｏ  ｒｕｎ（  ）というオペレーションを用いて入力ビット列中の区切り（復号が終了している符号語の最後のビットの直後）から６ビットの範囲内で連続する“０”ビットの個数をカウントし、それを状態レジスタＲの構成要素Ｒ０として保持する。そして、入力ビット列中の現在位置を（Ｒ０＋１）ビット進める。第２段階（ブロック２２）では、そのＲ０の値で決定する処理を行い、その結果をＲ１として保持する。第３段階（ブロック２３）では、Ｒ１に基づいた処理を行い、その結果をＲ２として保持し、この時点で状態レジスタＲを得る。第４段階（ブロック２４）で、Ｒを用いて後述の表６の係数テーブルからＤＣＴ係数を復号する。
【００６９】
以下の説明において、ＤＣＴ係数は（ｒｕｎ、ｌｅｖｅｌ）形式で表示し、２進ストリングは‘００１０’と云う形で表記する。特に断らない限り、値は１０進値である。
【００７０】
表４は、本発明に係る方法が用いる写像オペレーションを記述する。１６個の写像オペレーションがあり、その内９つのオペレーションはコードをアドレスし、その後、復号プロセスを終わらせるのに使われ、７つのオペレーションは、定められた値に戻す。
【００７１】
【表４】
0003708218.tif 000014
【００７２】
表４で、Ｍ（Ｒ，ｎ）（ｎ＝１，２，３，４……）は次の様に定義される写像関数である。
【００７３】
【数１２】
Ｍ（Ｒ，ｎ）＝Ｔａｂｌｅ〔Ｒ〕〔ｇｅｔ  ｂｉｔ（ｎ）〕        （１２）
【００７４】
ここでＲは、下記の形で定義される８ビット・レジスタであり、セマンティクスを表５に示す。これは状態レジスタと名付けられる。ｇｅｔ−ｂｉｔ（ｎ）は、次のｎビットの１０進値を戻し、ｎビットだけシフトさせる関数である。
【００７５】
【数１３】
Ｒ≡Ｘ；Ｒ０；Ｒ１；Ｒ２                            （１３）
【００７６】
【表５】
0003708218.tif 000015
【００７７】
オペレーションｔｅｒｍ−＃４（  ）即ち、ｅｓｃａｐｅ−ｃｏｄｅはＣソース・ランゲージで以下の様に記述することができる。
【００７８】
【数１４】
0003708218.tif 000016
【００７９】
ここで、本発明に係る方法に使われる係数テーブルを定義する。この場合、各々のコードが、２次元アレイの項目としてアクセスされる。例えば、〔０；０；０；０〕〔０〕は（Ｎ／Ａ，ＥＯＢ）に相当する。
【００８０】
【表６】
0003708218.tif 000017
【００８１】
図１２は、本発明の一実施例に係る復号アルゴリズムを示し、ＤＣＴ係数テーブルの０の場合、即ち、ｉｎｔｒａ−ｖｌｃ−ｆｏｒｍａｔが作用していない時のこれらのオペレーションを有するＶＬＣ復号アルゴリズムを示す。この図において、Ｒ０とＲ１が求められ、これは図１１のブロック図における第１のアドレス・オペレーション（ブロック２１）および第２のアドレス・オペレーション（ブロック２２）に対応する。このプロセスは符号ビットをカバーしない。これは、ＶＬＣの他の先行部分が分かれば、容易に扱うことができるからである。このアルゴリズムが１つのコードの復号プロセスを示す。然し、最初の判定ルーチン、即ちｕｓｅ−ｉｎｔｒａ−ｖｌｃ（  ）は飛越すことができる。これは、映像層シンタクスｉｎｔｒａ−ｖｌｃ−ｆｏｒｍａｔが作用していない時、戻った値は０に固定されているからである。従って、こう云う状態では、復号プロセスは次のオペレーション、即ちｚｅｒｏ−ｒｕｎ（  ）から開始することができ、Ｘを強制的に０にする。それでも、状態レジスタＲは、ｕｓｅ−ｉｎｔｒａ−ｖｌｃ（  ）を適用する前に０；０；０；０にリセットすべきである。
【００８２】
ｉｎｔｒａ−ｖｌｃ−ｆｏｒｍａｔが作用している場合、図１３に示した別のアルゴリズムが使用される。この図において、Ｒ０、Ｒ１及びＲ２が求められ、これは図１１のブロック図における第１オペレーション（ブロック２１）、第２オペレーション（ブロック２２）及び第３オペレーション（ブロック２３）に対応する。
【００８３】
図１２及び図１３から、図１１に示すように、オペレーションｕｓｅ−ｉｎｔｒａ−ｖｌｃ（  ）を除いて、係数を復号するには、本発明に係るＶＬＣ復号方法は精々３回のアドレスオペレーションを必要とすることが判る。
【００８４】
表７は、２進ストリング‘００１０００１０’が現われた時のＶＬＣ復号プロセスの一例を示す。復号結果としてテーブル〔０；２；１；０〕〔２〕が得られることを示している。即ち、２進ストリング‘００１０００１０’はコード（１２，１）に対応する。表７の「現在位置」の欄で示されるビット間の縦線がビット列の区切り（符号語の区切りではなく、本発明に係るオペレーションを単位とする区切り）を示している。表７の例では、入力ビット列は右から左へ流れており、区切りより左にあるビット列は、既にそこから情報が抽出され、今後の復号処理に影響を及ぼさないデータとしてみなす。
【００８５】
【表７】
0003708218.tif 000018
【００８６】
本発明に係る方法が、種々の符号化されたビットストリングからＤＣＴ係数を正しく復号することがシミュレーションによって検証されている。
【００８７】
テーブルの規模の縮小の場合と同じく、本方法は、１５４個の係数コード持つＶＬＣ復号（１１２個はＤＣＴ係数テーブルの０に対し、４２個はＤＣＴ係数テーブルの１に対し）を可能にする。これに対して、ＭＰＥＧソフトウェア・シミュレーション・グループ（ＭＳＳＧ）によって考えられた復号方法は、４３２個の係数コードを使う。更に精密な比較の為、表８は、各々の方法に対してコード項目を表わすのに要するビット数で、係数テーブルのフォーマットを示している。最終的には、テーブルの規模は、夫々本発明に係る方法とＭＳＳＧ復号方法に対し、１，６９４ビット（１５４×１１）及び６，９１２ビット（４３２×１６）である。その比は大まかに云うと４：１に等しい。
【００８８】
【表８】
0003708218.tif 000019
【００８９】
更に、バス・アーキテクチャについて云うと、ＭＳＳＧ復号方法は８ビット・アドレス・バスを必要とする。これは、係数テーブルの最大項目数が２５０だからである。これに対し、表６に示す様な本発明に係る方法では、４ビット・アドレス・バスで十分である。
【００９０】
上述のように、各段階毎に復号のための情報（状態レジスタ）を取得し、現在位置を更新しながら復号を進めることができるので、最終的に参照する係数テーブルには符号長を表すフィールドが不要になり、その分だけ係数テーブルを縮小することができる。さらに係数テーブルを参照する際のアドレスビット長を従来（ＭＳＳＧ）の８ビットに対し、４ビットにできるので係数テーブルのエントリー数を半減できる。これらの２つの効果により係数テーブルを従来の１／３ないし１／４にできる。
【００９１】
以下に別の発明に関し説明する。この発明はビデオ映像信号の動き補償に関する。従来の動き補償を用いた符号化方式では、フレームを均等なサイズのブロックに分割して、そのブロック単位で動きを推定していた。近年、これを改良したものとして図１４に示すような可変サイズのブロック単位で動き補償を行う方式が検討されている。この手法により、フレームは、物体の近傍では小さなブロックに、また、背景など均質な領域では大きなブロックに分割される。その目的は、誤差が発生しやすい物体の近傍できめ細かく動き情報を伝送することで、フレーム全体で発生する誤差を抑制することである。しかし、この可変サイズブロック動き補償では、ブロック分割のための情報を四分木構造のデータで伝送した場合、符号化の利得に対してオーバーヘッドが大きくなるという問題が指摘されている。そこで、提案手法では、このオーバーヘッドを軽減するために、エッジ情報を抽出・伝送することにより可変サイズブロック分割を行う。すなわち、提案手法は、エッジに基づく可変サイズブロック分割を特徴とする動き補償符号化方式である。
【００９２】
従来から用いられている画素単位の追跡によるエッジ抽出では、オーバーヘッドの情報量が大きくなるので、これを防止するため提案手法では、エッジを点ではなく線分で近似的に表現する方法を採用する。ブロック分割アルゴリズムの機能ブロック図を図１５に示す。
【００９３】
まず、原画像（または、復号フレーム）に２次微分フィルタをかけることによって輝度変化の不連続点を抽出する。そして、閾値処理により得られた点（エッジ点と呼ぶ）の集合に対して２段階の群化処理を施し、物体の形状を表現する線分を抽出する。その第１段階の群化処理において、エッジ点の集合と８方向に量子化した５×５画素の大きさの線分パターンマスクとのテンプレート・マッチングを行ない方向性を持った線分（単位線分と呼ぶ）を抽出する（ブロック６１）。これが単位線分の抽出である。
【００９４】
次にマクロ線分の抽出（ブロック６２）を説明する。人間の視覚中枢細胞は物体の回転に対して１０°単位で反応する性質（これを方位選択性という）があることから、第２段階の郡化処理においては、同一方向に連続する単位線分を結合し、１６方向に量子化した線分（マクロ線分と呼ぶ）を抽出する。マクロ線分の例は図１６に示す通りである。マクロ線分を表現するデータ形式は、各線分の端点の２次元座標、方向（１６に量子化した内の１方向）及び長さ（結合画素数）である。
【００９５】
そしてブロック分割（ブロック６３）では、最初はフレームを大きなブロック（許容最大ブロック）で均等分割し（これを、第１層と呼ぶ）、各ブロックにマクロ線分が存在すれば４つの小ブロックに分割する（これを、第２層と呼ぶ）。そして、この操作を、予め規定した許容最小ブロックを得るまで繰り返す。図１６のブロック分割では、第１層から第３層までが存在している。
【００９６】
これまでの実験結果からオーバーヘッドの情報量は、画像の内容に依存せず、第２層までの分割であれば提案手法と四分木構造はほぼ同等、第３層以上であれば提案手法の方が少ない（つまり、有利である）ことを確認した。また、図１４中破線で示したブロックは、提案手法では通常エッジ抽出を原画像上で行うが、代替案として以前に復号したフレームを用いる方法があることを示している。この代替案では、符号化側の局所復号化部と復号化側ではともに等しい復号フレームが存在するので、エッジ抽出法が同じであれば得られるエッジも等しくなることを利用している。この手法の利点は、オーバーヘッドがなくなるということである。しかし、復号フレームと実際に処理しているフレームが類似していることを前提としているため、両者に違いが生じた場合は誤った分割を行うことになり符号化効率が低下する。従って、原画像を用いる場合と復号フレームを用いる場合を適応的に切換える機構が必要となる。
【００９７】
【発明の効果】
より少ないデータ量で、像を符号化するのに適切な像の分解を行うことができる。
【図面の簡単な説明】
【図１】多層表示の一例を示す図。
【図２】図１に示した多層表示例のＱＴコードを示す図。
【図３】本発明の一実施例に係る符号器のブロック図。
【図４】縮小された像を説明する図。
【図５】図３の符号器内の縁抽出部のブロック図。
【図６】８方向の小セグメント・パターンを示す図。
【図７】マクロ縁の検出を説明する図。
【図８】縁ベルトの一例を示す図。
【図９】段形縁の一例を示す図。
【図１０】シミュレーションによる多層表示のデータ速度を比較するグラフ。
【図１１】他の発明に係る復号方法の概念を示すブロック図。
【図１２】他の発明の一実施例に係る復号アルゴリズムを説明する図（ＤＣＴ係数テーブルが０の場合）。
【図１３】他の発明の一実施例に係る復号アルゴリズムを説明する図（ＤＣＴ係数テーブルが１の場合）。
【図１４】別の発明の一実施例を説明するブロック図。
【図１５】別の発明におけるアルゴリズムを説明する図。
【図１６】ブロック分割を説明する図。
【符号の説明】
１  パラメータ決定部
２  像縮小部
３  縁抽出部
４  多層化部
５  符号化部
【図１】
0003708218.tif 000020
【図２】
0003708218.tif 000021
【図３】
0003708218.tif 000022
【図４】
0003708218.tif 000023
【図５】
0003708218.tif 000024
【図６】
0003708218.tif 000025
【図７】
0003708218.tif 000026
【図８】
0003708218.tif 000027
【図９】
0003708218.tif 000028
【図１０】
0003708218.tif 000029
【図１１】
0003708218.tif 000030
【図１２】
0003708218.tif 000031
【図１３】
0003708218.tif 000032
【図１４】
0003708218.tif 000033
【図１５】
0003708218.tif 000034
【図１６】
0003708218.tif 000035