JPH0824341B2

JPH0824341B2 - 画像データ符号化方法

Info

Publication number: JPH0824341B2
Application number: JP60241218A
Authority: JP
Inventors: 伸一郎宮岡; 良一佐々木; 高義白石
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1985-10-28
Filing date: 1985-10-28
Publication date: 1996-03-06
Anticipated expiration: 2011-03-06
Also published as: JPS62101183A; EP0220706A2; US4831659A; EP0220706B1; DE3686754T2; DE3686754D1; EP0220706A3

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は、画像データ符号化方法に関し、特に低ビッ
トレートでの画像通信、画像ファイル検索用の概略画像
作成等に好適な画像データ高能率圧縮方法に関する。

〔発明の背景〕

画像通信、画像ファイルの低コスト化および高応答性
を実現するために、さらに能率のよい画像データの圧縮
方式が望まれている。従来の画像データの圧縮方式は、
予測符号化方式と変換符号化方式に大別される。予測符
号化方式は、画素単位で、近傍の画素からその画素の輝
度値を予測し、これを可変長符号化するものである。こ
の方式では、原理的に1bit/pixel以上の圧縮を行うこと
はできない。一方、変換符号化方式では、画像を一定の
大きさ（８×8,16×16等がよく用いられる）のサブブロ
ツクに分割し、このブロツク単位で直交変換を施こし、
符号化するものである。この方式では、ブロツクサイズ
を超える大域的な冗長性（平坦な背景等がその典型例）
を利用できないため、やはり圧縮率に限界がある。上記
２つの方式の他には、最近活発に研究が行われているベ
クトル量子化方式があるが、この方式でも、一定の大き
さのサブブロツクに画像を分割し、ブロツクごとに量子
化を行う方法をとつているため、上記変換符号化方式と
同じような限界がある。これらの圧縮方式については、
例えば、信学技報IE83-106「静止画像用符号化方式の比
較検討」において述べられている。この文献では、アダ
プテイブ・コサイン変換符号化、階層的アダマール変換
符号化、ベクトル量子化、DPCM符号化、およびアダブテ
イブ・ブロツク符号化の５種類の方式について、S/N
比、符号量の関係を中心に各種データを計算機シミユレ
ーシヨンにより求め、比較検討を行つた結果について記
載している。これらの全ての方式では、いずれも上述の
ような圧縮率の限界が存在する。

〔発明の目的〕

本発明の目的は、このような従来の問題を解決し、画
像の持つ局所的な冗長性のみならず、大域的な冗長性ま
で活用して、画像データを大幅に圧縮することができる
高能率な画像データ符号化方法を提供することにある。

〔発明の概要〕

前記目的を達成するため、本発明の画像データ符号化
方法は、イ）圧縮符号化の対象である画像を複数のブロックに分
割する処理と、ロ）それぞれ係数が乗算され、画像データの座標に相当
する２つの独立変数を持ち、かつ平均輝度の項を含む多
項式関数によって前記複数のブロックの各々の画像を近
似する処理と、ハ）前記複数のブロックの各々について、近似により得
られる近似画像と元の画像との各画素の輝度の差を算出
して、近似により発生する平均ひずみを算出する処理
と、ニ）前記平均ひずみの指標が予め定められた値を超えな
いブロックが集合して上位レベルのブロックを形成する
場合には、該上位レベルのブロックの画像について、上
記ロ）およびハ）の処理を行う処理と、ホ）定められた最上位レベルのブロックに向けて上記
ロ）、ハ）およびニ）の処理を繰り返し行い、その結
果、前記画像のそれぞれの領域ごとに最終的に統合され
たブロックについて得られる多項式関数の係数列および
平均輝度のデータを木構造に形成された符号化データと
する処理の各処理手順を含むことを特徴としている。

〔発明の実施例〕

以下、本発明の原理および実施例を、図面により詳細
に説明する。第３図〜第６図、および第１図により符号
化の原理を説明し、第７図〜第９図により復号化の原理
を説明する。

（イ）符号化方式第３図（ａ）（ｂ）は、等長ブロツク符号化と非等長
ブロツク符号化の概念比較図である。

画像の持つ大域的冗長性まで活用してデータ圧縮を行
うため、画像を輝度変化の大小に応じて非等長ブロツク
（大きさの異なるブロツク）に分割する。すなわち、輝
度変化の緩やかな部分は大きなブロツクに、一方、輝度
変化の激しい部分は小さなブロツクに分割されるように
する。このようにブロツク分割して、各ブロツクを同一
のビツト数で符号化すれば、第３図（ａ）に示すように
等長ブロツクで分割した場合に利用できなかった大域的
冗長性まで利用した符号化が行えるようになる（３図
（ｂ）参照）。

ブロツク分割の基準としては、平均ひずみを用い、符
号化・復号化された後の各ブロツクの平均ひずみが、指
定された許容値を超えないようにする。なお、ひずみの
指標として最もよく用いられるものに、例えば、平均２
乗誤差があり、これは次式により表わされる。

ここで、ｄは平均ひずみ、Ｎはブロツク内画素数、X
_ijは画素（i,j）の輝度、_ijは画素（i,j）の符号化・
復号化した値である。

第４図は、ブロツク階層の説明図であり、第５図は第
４図におけるリダクシヨンの説明図である。

いま、１×1,2×2,・・・2ⁿ×2ⁿの大きさのブロツク
図を考える。１×１ブロツクは、画素そのものであり、
2ⁿ×2ⁿブロツクは画像全体を表わしている。ここで、2ⁿ
×2ⁿブロツクを最上位レベル（第０レベル）、１×１ブ
ロツクを最下位レベル（第ｎレベル）と呼ぶことにす
る。第４図の例（ｎ＝４）では、０〜４が、それぞれ第
０〜第４レベルのブロツクとなつている。各ブロツクを
表現するため、次のような表記法を用いることにする。
第１レベルでは、2^n-1×2^n-1（８×８画素）の大きさの
ブロツクが４個存在するので、これらを左上、右上、左
下、右下の順に1,2,3,4と記す。次に、第２レベルで
は、2^n-2×2^n-2（４×４画素）の大きさのブロツクが16
個存在し、４個づつ区切つたものが第１レベルの１つの
ブロツクに対応している。そこで、第１レベルの同一ブ
ロツクに含まれる第２レベルの４個のブロツクに対し
て、第１レベルと同じように１〜４の番号を与えること
にする。つまり、第２レベルのブロツクは、第１レベル
のブロツク番号i₁（i₁＝１〜４）と第２レベルのブロツ
ク番号i₂（i₂＝１〜４）の組合せ（i₁,i₂）により一意
に定められる。このようにして、一般に第ｋレベルの１
つのブロツクを（i₁,i₁，・・・,ik）で表わすことがで
きる。第４図の例で、ブロツク５（ハツチングされたブ
ロツク）は、（1,1,1,4）と表わされる。

以上の表記法により表わされるブロツク（i₁,i₂，・
・・,ik）の平均輝度をXi₁i₂・・・・ikとし、ブロツク
内の全画素の輝度をXi₁i₂・・・・ikで代表させたとき
に生ずる平均ひずみを、di₁i₂・・・ikと表わす。すな
わち、とする。ここで、Zi₁‥‥i_nは画素（i₁,i₂……，i_n）の
輝度である。

最下位レベルから出発し、前式（２）で定義される平
均ひずみが与えられた許容値Ｄを超えないとき、４個の
ブロツクを、これらを含む一段階上位のブロツクに統合
することにする。すなわち、 di₁・・・ik≦Ｄ ……（３）のとき、Xi₁‥‥ik1〜Xi₁…ik4を、Xi₁・・・ikで代表
させる（第５図参照）。以後、この処理をリダクシヨン
と呼ぶことにする。ここで、Xi₁・・・ik,di₁・・・ik
は一段階下のレベルから以下に示す漸化式で計算するこ
とができるので、実用面からも効率的な計算が行える。

第１図は、本発明の一実施例を示す符号化手順のフロ
ーチヤートである。

第３図および第４図の考え方による符号化手順を、第
１図のフローチヤートに従つて説明する。ステツプ10で
は、最下位レベル、先頭ブロツクの設定を行う。ステツ
プ11,12でそれぞれ前式（４）、前式（５）の計算を行
い、平均輝度、平均ひずみを求める。ステツプ13で前式
（３）の判定を行い、平均ひずみが許容値より小さいと
き、つまり（３）式が成立したときには、ステツプ14で
リダクシヨンを実行する。ステツプ15では、次のブロツ
クの処理に進むが、次のブロツクが既にリダクシヨン不
能になつている場合には、スキツプするものとする。ス
テツプ16で、現在処理中のレベルの全ブロツクの処理が
終了したか否かの判定を行い、終了している場合には、
ステツプ17で次のレベルに進む。ステツプ18は、全レベ
ルの処理が終了したか否かの判定であり、終了している
場合には、符号化処理は終了する。

第６図（ａ）（ｂ）（ｃ）は、それぞれ符号化データ
のデータ構造説明図である。以下、符号化されたデータ
の構造（蓄積用、通信用）について述べる。第６図
（ａ）に示すように符号化されたデータは、第６図
（ｂ）に示すような４分木で表わすことができる。この
４分木構造を、第６図（ｃ）で示すようなデータ構造で
記憶する。データは、４個ずつのデータブロツクに区切
られ、これが画像上の１ブロツクに対応している。画像
ブロツクは、上位レベルから順に格納されており、ESC
はエスケープ記号（これは、そのレベルまでリダクシヨ
ンされておらず、さらに下位レベルを参照する必要があ
ることを示す）を表わしている。例えば、第６図（ｃ）
の最初のデータブロツクでは、（ESC,X₂,X₃,ESC）とな
つており、第１レベルの第１ブロツクと第４ブロツク
は、さらに下位レベルを参照する必要があつて、第２、
第３ブロツクは、それぞれX₂,X₃の輝度値をとることが
わかる。ESC記号が格納されていたブロツクは、１段階
下のレベルに展開されて、後続のデータブロツクに格納
される。すなわち、第６図（ｃ）の例では、最初のESC
に対応するデータが２番目のデータブロツクに、２番目
のESCに対応するデータが３番目のデータブロツクに、
それぞれ格納されている。このようなデータ構造を生成
した後、データの値に片寄りがある場合には、ESC記号
を含め可変長符号化（ハフマン符号化）することも考え
られる。

第２図は、本発明が適用されるデータ符号化・復号装
置のブロツク図である。例えば、フアクシミリ信号等に
適用した場合には、ラインバツフア31,計数・輝度発生
回路32,コード・デコード回路33,バツフア34で構成され
る。符号化するときには、スキヤナで読み込んだ画像
を、１ラインごとにラインバツフア31に格納し、計数・
輝度発生回路32で一画面中のいくつ目のラインかを計数
しながら、ラインバツファのデータをコード・デコード
回路の中のイメージバツファに格納していき、コード・
デコード回路33で第１図に示す符号化処理を行う。そし
て、第６図（ｃ）に示すような形式のデータでバツフア
34に格納する。送信する場合には、モデムを介して交流
信号に変調した後、伝送路に送出する。また、伝送路か
ら圧縮信号を受信した場合には、モデムを介して受信し
たデータを第６図（ｃ）に示す形式で伝送された順にバ
ツフア34に格納し、バツフア34からFIFOのキユーにデー
タを移して、コード・デコード回路33において、第８図
で後述する復号処理を行い、輝度発生回路32で輝度を発
生させた後、ラインバツフア31に一旦格納し、シリアル
信号としてプロツタに出力して描画させる。

（ロ）復号方式符号化されたデータの復号方式について、説明する。
第６図（ｃ）のデータブロツク番号をl,ブロツク内のデ
ータ番号をｍ（ｍ＝１〜４）とし、符号化されたデータ
をYl,mで表わす。ここで、ESC記号からその下位レベル
展開ブロツクを求める手段として、FIFO（First In Fir
st Out）のキユーを用意する。

第７図は、FIFOの動作説明図であり、第８図は本発明
の一実施例を示す復号処理のフローチヤートである。復
号の手順は、次のように行われる。先ず、ｌ＝１のとき
（ステツプ20）、（ａ）Yl,m≠ESCであれば、Xm＝Yl,m（ステツプ21,2
2）。

Yl,m＝ESCであれば、ｍをFIFOに格納する（ステツプ2
3）。

また、ｌ≧２のとき（ステツプ26）、（ａ）FIFOから先頭要素ωを取り出す（ステツプ28）。

（ｂ）Yl,m≠ESCであれば、Ｘωｍ＝Yl,m（ステツプ21,
22）。Yl,m＝ESCであれば、（ω,m）をFIFOに格納する
（ステツプ23）。

ここで、ωは整数列であり、（ω,m）はωにｍを追加
した整数列である。このようにして、全データブロツク
が終了するまで繰り返し、ブロツク終了により処理を終
る（ステツプ27）。

第７図（ａ）（ｂ）（ｃ）は、第６図（ｃ）の例にお
けるFIFOの動作を示している。先入れ先出し動作を行う
ため、第７図では、バツフアの下方から格納されて順次
上方に移り、最上位のものが読み出される。（ａ）では
1,4の順にデータが格納され、（ｂ）では最初の１が読
み出された後、4,13の順で格納されている。（ｃ）では
４が読み出された後、13のみが格納されている状態が示
されている。

このようにして、第６図（ｃ）のデータ列から、各ブ
ロツクの輝度Xi₁・・・ikが再現できる。ブロツク（i₁
・・・ik）に含まれる画素の座標（X,Y）は次式で求め
られ、画素レベルでの復号が可能となる。

である。

次に、簡単なモデルに基づき圧縮率の評価を行う。

（イ）仮定（ａ）512×512×8bit/pixelの画像を想定する。（ｂ）
与えられた許容ひずみＤと対象画像に関し、レベルｉ以
上の精度を必要とする領域のうち、レベル（ｉ＋１）以
上の精度を必要としない領域城の比率がαになるとす
る。（ｃ）可変長符号化による圧縮分は考慮しない。す
なわち、第５図（ｃ）の形式のデータを等長符号化する
ものとする。

（ロ）圧縮率評価想定する最下位レベルをＫとする。すなわち、Ｋ＝９
であれば、１×１を、Ｋ＝８であれば、２×２を、それ
ぞれ最下位レベルのブロツクとする。このとき、ESC記
号まで含めて符号化すれば、必要なビツト数は次式とな
る。

従つて、圧縮率Ｃα,kは、となる。

第９図は、圧縮率評価のグラフであつて、k,αのいく
つかの値に対して、Ｃα,kを計算した結果を示したもの
である。α＝1/2のときには、Ｋ＝９（画素レベル）ま
で空間分解能を上げても1/100の圧縮率を達成すること
ができるが、α＝1/4となると、1/100の圧縮を行うため
には、Ｋ＝７（４×４ブロツク）程度まで空間分解能を
下げなければならないことがわかる。

（ハ）SNの評価 SN値は、平均ひずみから求まる。

ここで、M.S.Eは、平均ひずみであり、許容平均ひず
みを超えることがないため、が成立する。このように、従来の方法が符号化・復号
化を実行後、始めてSNを評価できるのに対して、本発明
では、許容ひずみＤをパラメータとしてSNを事前に評価
できるため、見通しのよい方式となる。

次に、本発明の他の実施例を、第10図〜第15図により
説明する。

第10図（ａ）（ｂ）は、輝度勾配の説明図および輝度
の近似方式の説明図である。ブロツク分割の基準とし
て、平均ひずみを用い、指定された許容値を超えないよ
うにすることは、前述した。第３図で述べたように、最
もよく用いられるひずみの指標として、平均２乗差があ
り、この式を再び記載する。

ここで、ｄは平均ひずみ、N²はブロツク内画素数、X
_ijは画素（i,j）の輝度、_ijは画素（i,j）の符号化・
復号した輝度である。

各ブロツクの符号化には、そのブロツク内の平均輝度
と近似的な輝度勾配を用いる。平均輝度Ｘは次式で表わ
される。

また、輝度勾配Δ（ｉ軸方向）およびδ（ｊ軸方向）
は、第10図（ａ）に示すようなもので、次のようにして
定められる。先ず、（８）式の_ijを、，Δ，δを用
いて次のように表わす。_ij ＝＋（2i−Ｎ−１）Δ＋（2j−Ｎ−１）δ ……（10）これは、ブロツク内の輝度が形成する曲面を、勾配
（２Δ,2δ）の平面で近似することを意味している（第
10図（ａ）（ｂ）参照）。ひずみが最小となるような近
似は、（10）式を（８）式に代入して得られるｄを最小
化する条件から導かれる。この条件に基づくΔ，δの具
体的な計算法については、実施例で詳述する。

第11図〜第14図で符号化方式を、第15図で復号方式
を、説明する。

（イ）符号化方式先ず、第11図は第４図を再現したもので、非等長ブロ
ツクの表記法の説明のために使用される。１×1,2×2,
・・・・2ⁿ×2ⁿの大きさのブロツクを考える。１×１ブ
ロツクは画素そのものであり、2ⁿ×2ⁿブロツクは画像全
体を表わしている。ここで、2ⁿ×2ⁿブロツクを最上位レ
ベル（第０レベル）、１×１ブロツクを最下位レベル
（第ｎレベル）を呼ぶ。第11図の例では、０〜４がそれ
ぞれ第０〜第４レベルのブロツクとなつている。各ブロ
ツクを表現するため、第１レベルでは，2^n-1×2^n-1の大
きさのブロツクが４個存在するので、これらを左上、右
上、左下、右下の順に1,2,3,4と記す。次に、第２レベ
ルでは、2^n-2×2^n-2のブロツクが16個存在し、４個づつ
区切つたものが第１レベルの１つのブロツクに対応して
いる。そこで、第１レベル同一ブロツクに含まれる第２
レベルの４個のブロツクに対して、第１レベルと同じよ
うにして、１〜４の番号を与えることにする。すなわ
ち、第２レベルのブロツクは、第１レベルのブロツク番
号i₁（i₁＝１〜４）と第２レベルのブロツク番号i₂（i₂
＝１〜４）の組合せ（i₁,i₂）により一意に定められ
る。このようにして、一般的に、第ｋレベルの１つのブ
ロツクを（i₁,i₂，・・・ik）で表わすことができる。
第３図の例で、ブロツク５（ハツチングされたブロツ
ク）は、（1,1,1,4）と表わされる。

以上の表記法により表わされるブロツク（i₁,i₂，・
・・ik）の平均輝度をXi₁i₂・・・ik,近似輝度勾配をΔ
i₁i₂・・・ik,δi₁i₂・・ikとする。さらに、ブロツク
内の画素の輝度をXi₁・・・ik,Δi₁・・・ik,δi₁・・
・ikを用いて（10）式で近似したときの近似値をXi₁・
・・ik,そのときの平均ひずみをdi₁・・・ikと表わす。
すなわち、とする。ここで、Zi₁・・i_nは、画素（i₁i₂・・i_n）の
輝度である。なお、添字i₁・・i_nはそれぞれ１から４の
範囲を動くものとする。

最下位レベルから出発し、（12）式で定義される平均
ひずみが、与えられた許容値Ｄを超えないとき、４個の
ブロツクをこれらを含む一段階上位のブロツクに統合す
ることにする。すなわち、 di₁・・・ik≦Ｄ ……（13）のとき、Xi₁・・・ik1〜Xi₁・・・ik4を、Xi₁・・・ik
で、Δi₁・・・ik1〜Δi₁・・・ik4を、Δi₁・・・ik
で、またδi₁・・・ik1〜δi₁・・・δi₁・・・ik4を、
δi₁・・・ikで、それぞれ代表させる（第12図参照）。
以後、この処理をリダクシヨンと呼ぶことにする。

次に、リダクシヨンを実行するためのX,Δ，δ,dの具
体的な計算法について述べる。（11），（12）式から、
X,Δ，δ,dに関する以下の関係式が導ける。

ここで、S_i,t_i（ともに、ｉ＝１〜４）,Ak（ｋ＝1,・
・・ｎ）は、以下の値をとる係数である。

S₁＝S₃＝−1, S₂＝S₄＝１ t₁＝t₂＝−1,t₃＝t₄＝１（７）〜（10）式から、X,Δ,S,dは一段下のレベルのX,
Δ，δ,dから漸化的に計算でき、実用面からも効率的な
計算が行えることになる。

第13図は、本発明の他の実施例を示す符号化処理の手
順のフローチヤートである。先ず、ステツプ40では、最
下位レベルおよび先頭ブロツクの設定を行う。ステツプ
41では、（14）式により、平均輝度Ｘを求め、ステツプ
42で（15）（16）式により、輝度勾配Δ，δを計算す
る。ステツプ43では、（17）式に基づき平均ひずみｄを
求める。ステツプ44で（13）式の判定を行い、（13）式
が成立した場合、ステツプ45でリダクシヨンを実行す
る。ステツプ46では、次のブロツクの処理に進むが、次
のブロツクが既にリダクシヨン不能となつている場合に
は、スキツプするものとする。ステツプ47では、現在処
理中のレベルの全ブロツクの処理が終了したか否かの判
定を行い、終了している場合には、ステツプ48で次のレ
ベルに進む。ステツプ49は、全レベルの処理が終了した
か否かの判定であり、終了している場合には、符号化処
理を終了する。

第14図（ａ）（ｂ）（ｃ）は、符号化データのデータ
構造図である。第14図（ａ）に示すように符号化された
データは、第14図（ｂ）に示すような４分木で表わすこ
とができる。これを第14図（ｃ）に示すようなデータ構
造により記憶する。データは４個づつのデータブロツク
に区切られ、これが画像上の１ブロツクに対応してい
る。画像ブロツクは、上位レベルから順に格納されてお
り、ESCはエスケープ記号（そのレベルまでリダクシヨ
ンされておらず、さらに下位レベルを参照する必要があ
ることを示す）を表わしている。例えば、第14図（ｃ）
の最初のデータブロツクでは、（ESC,（X₂，Δ_２，
δ_２），（X₃，Δ_３，δ_３）ESC）となつており、第１
レベルの第１ブロツクと第４ブロツクはさらに下位レベ
ルを参照する必要があり、第２、第３ブロツクは、それ
ぞれ（X₂，Δ_２，δ_２），（X₃，Δ_３，δ_３）に符号化
されていることがわかる。ESC記号が格納されていたブ
ロツクは、一段下のレベルに展開されて後続のデータブ
ロツクに格納される。すなわち、第14図（ｃ）の例で
は、最初のESCに対応するデータが２番目のデータブロ
ツクに、２番目のESCに対応するデータが３番目のデー
タブロツクに格納されている。このようなデータ構造を
生成した後、データの値に片寄りがある場合には、ESC
記号も含めて可変長符号化（ハフマン符号化）すること
も考えられる。

（ロ）復号方式符号化されたデータの復号方式について述べる。

第14図（ｃ）のデータブロツク番号をl,ブロツク内の
データ番号をｍ（ｍ＝１〜４）とし、符号化されたデー
タをYl,m （X,Δ，δの組）で表わす。ここで、ESC記号からその
下位レベルの展開ブロツクを求める手段としてFIFOのキ
ユーを用意する。

第15図は、本発明の他の実施例を示す復号処理フロー
チヤートである。

先ず,l＝１のとき、（ａ）Yl,m≠ESCであれば、
（Ｘ），Δm,δｍ）＝Yl,mである（ステツプ50,51,5
2）。

また、Yl,m＝ESCであれば、ｍをFIFOに格納する（ス
テツプ51,53）。

次に、ｌ≧２のとき、（ａ）FIFOから先頭要素ωを取
り出す（ステツプ56,58）。（ｂ）Yl,m≠ESCであれば
（Ｘωm,Δωm,δωｍ）＝Yl,m（ステツプ51,52）。

Yl,m＝ESCであれば、（ω,m）をFIFOに格納する（ステ
ツプ51,53）。

ここで、ωは整数列であり、（ω,m）はωにｍを追加
した整数列である。

このようにして、第14図（ｃ）のデータ列から、各ブ
ロツクの輝度Xi₁・・・ik,輝度勾配Δi₁‥ik,δi₁‥ik
が再現できる。ところで、このブロツクに含まれる画素
の座標（X,Y）は、次式の範囲にある。

である。

ここで、とおき、画素（X,Y）の輝度X_xyに（10）式を適用すれ
ば、 X_xy＝Xi₁・・・ik ＋（2X−−Ｘ−１）Δi₁・・ik ＋（2Y−−Ｙ−１）δi₁・・ik ……（21）が成立し、画素レベルの復号が可能となる。

このように、本実施例においては、特にブロツク内を
輝度勾配を用いて符号化することにより、輝度勾配が一
定に近い部分を１つのブロツクとして圧縮することがで
きる。圧縮率は、許容平均ひずみＤと対象画像の特性か
ら定まるものであるが、以下、簡単なモデルに基づき圧
縮率の評価を行う。

（イ）仮定（ａ）512×512×8bit/pの画像を想定する（ｂ）与え
られた許容ひずみＤと対象画像に関し、レベルｉ以上の
精度を必要とする領域のうちレベル（ｉ＋１）以上の精
度は必要としない領域の比率がαとなるようにする。
（ｃ）可変長符号化による圧縮分は考慮しない。すなわ
ち、第14図（ｃ）の形式のデータを等長符号化するもの
とする。

従つて、圧縮率Ｃα,kは、となる。

K,αのいくつかの値に対して、Ｃα,kを計算した結果
は、第９図に示されている。なお、SNの評価について
は、前述したとおりであるため、記載を省略する。

〔発明の効果〕

以上説明したように、本発明によれば、画像の持つ局
所的冗長性のみならず、大域的冗長性まで利用して符号
化するので、圧縮率および視認性のよい符号化方法が実
現できる。また、ブロック内を近似することにより、輝
度勾配の一定領域での圧縮率が上るとともに、視認性が
向上するという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例を示す符号化処理手順のフロ
ーチヤート、第２図は本発明の実施例を示す符号化・復
号処理装置のブロツク図、第３図は等長ブロツク符号
化、非等長ブロツク符号化の概念比較図、第４図はブロ
ツク階層の説明図、第５図はリダクシヨンの説明図、第
６図は符号化データのデータ構造図、第７図はFIFOの動
作図、第８図は本発明の一実施例を示す復号処理手順の
フローチヤート、第９図は圧縮率評価のグラフ図、第10
図は輝度勾配の説明と輝度の近似方式説明図、第11図は
ブロツク階層の説明図、第12図リダクシヨンの説明図、
第13図は本発明の他の実施例を示す符号化処理手順のフ
ローチヤート、第14図は符号化データのデータ構造図、
第15図は第14図のデータの復号処理手順のフローチヤー
トである。 31:ラインバツフア、32:計数・輝度発生回路、33:コー
ド・デコード回路、34:バツフア。

Claims

【特許請求の範囲】

【請求項１】イ）圧縮符号化の対象である画像を複数の
ブロックに分割する処理と、ロ）それぞれ係数が乗算され、画像データの座標に相当
する２つの独立変数を持ち、かつ平均輝度の項を含む多
項式関数によって前記複数のブロックの各々の画像を近
似する処理と、ハ）前記複数のブロックの各々について、近似により得
られる近似画像と元の画像との各画素の輝度の差を算出
して、近似により発生する平均ひずみを算出する処理
と、ニ）前記平均ひずみの指標が予め定められた値を超えな
いブロックが集合して上位レベルのブロックを形成する
場合には、該上位レベルのブロックの画像について、上
記ロ）およびハ）の処理を行う処理と、ホ）定められた最上位レベルのブロックに向けて上記
ロ）、ハ）およびニ）の処理を繰り返し行い、その結
果、前記画像のそれぞれの領域ごとに最終的に統合され
たブロックについて得られる多項式関数の係数列および
平均輝度のデータを木構造に形成された符号化データと
する処理の各処理手順を含むことを特徴とする画像データ符号化
方法。