JPH0548900A

JPH0548900A - 多値画像信号の符号化復号化方法および装置

Info

Publication number: JPH0548900A
Application number: JP3008199A
Authority: JP
Inventors: Shoji Mizuno; 昇治水野
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1991-01-28
Filing date: 1991-01-28
Publication date: 1993-02-26

Abstract

(57)【要約】【目的】画像データを効率よく伝送あるいは蓄積する
ためにそのデータ量を削減する方法および装置を提供す
ること。【構成】送信側では、入力画像信号Ｘを、その発生確
率順位を示す順位信号に変換し、それを２進数表現し、
その各ビットをシリアルに接続して信号Ｙを得、信号Ｙ
を０になる確率が高いか低いかによってＧＯＯＤとＢＡ
Ｄにグループ分けし、ＧＯＯＤランとＢＡＤランを交互
に取出すことにより信号Ｕを得、信号Ｕを平滑化して信
号Ｖを得、これをランレングス符号化する。受信側では
送信側と全く逆の処理をして画像信号Ｘを得る。【効果】ＧＯＯＤを白、ＢＡＤを黒に対応させれば、
ランレングス符号器４には標準ＭＨ符号器を用いて効率
のよい符号化ができる。

Description

【発明の詳細な説明】

【産業上の利用分野】本発明は画像信号のデータ圧縮符
号化方法および装置に関する。

【従来の技術】予測符号化では、通常、予測信号と原信
号との差、すなわち予測誤差信号をエントロピ−符号化
する。これは予測的中率が高いと、予測誤差信号が０に
集中する傾向が高く、原信号より予測誤差信号の方がエ
ントロピーが小さくなることを利用している。これに対
し、ピ・エリアス（Ｐ．Ｅｌｉａｓ）は、予測符号化に
おいて原信号をできるだけ小さなエントロピーを有する
信号に変換する方法について考察し、原信号を予測によ
って発生確率順位に順位付けるならば、その順位を示す
信号のエントロピーが、原信号に対し他のどんな変換を
行って得られる信号のエントロピーよりも小さいことを
示した。これは（ピ−・エリアス（Ｐ．Ｅｌｉａｓ）
「プレディクティブコーディング（Ｐｒｅｄｉｃｔｉｖ
ｅｃｏｄｉｎｇ）」ＩＲＥＴｒａｎｓ．，ＩＴ−
１誌１９５５年３月号、ＰＰ．１６〜３３、以下、「文
献１」）に詳しく示されている。以下では、原信号の発
生確率順位を示す信号を順位信号、原信号を順位信号に
変換するプロセスを順位予測と呼ぶことにする。もちろ
ん予測誤差信号のエントロピーより、順位信号のエント
ロピーの方が必ず小さい。以下において、順位信号は予
測順位信号と呼ぶこともある。このことを利用して、順
位信号を２進数で表現しランレングス符号化する方式が
（水野昇治「中間調画像の予測順位符号化」電子情報通
信学会論文誌Ｂ−１Ｖｏｌ．Ｊ７３−Ｂ−Ｉ，Ｎｏ．
６，１９９０年６月号、ｐｐ．５５４〜５６０、以下、
「文献２」）に詳しく示されている。以下図８を用い
て、予測順位符号化の説明を行う。送信側では予測変換
回路４３は、すでに符号化ずみの画像信号を用いて、入
力画像信号Ｘの発生確率順位を予測し、順位信号ｅを２
進数表現し、それをパラレルシリアル変換して信号ｅ_k
を得、配列変換回路４４へ加える。それと同時に、予測
変換回路４４は、すでに符号化ずみの画像信号とすでに
配列変換メモリ４４に書き込みずみのｅ_ｋにもとづき信
号ｅ_kが０になる確率が高いか低いかを示す信号Ｍ_kを
発生し、信号ｅ_kとともに配列変換回路４４へ加える。
配列変換回路４４は、１ラインメモリを有し、Ｍ_k＝０
（ＧＯＯＤ）の状態のｅ_kをメモリの先頭番地から番地
の昇順に格納し、Ｍ_k＝１（ＢＡＤ）の状態のｅ_kをメ
モリの最終番地から番地の降順に格納する。このように
して１ライン分のｅ_kをメモリに格納した後、ランレン
グス符号器４５はＧＯＯＤのｅ_k' とＢＡＤのｅ_k' を
順に読出し、それぞれ別々のランレングス符号を用いて
符号化し、ランレングス符号Ｃを得、伝送路４６へ送出
する。ｅ_k' はｅ_kを並びかえたものである。受信側で
は、ランレングス復号器４７は、伝送路４６よりランレ
ングス符号Ｃを入力し、これを復号化して信号ｅ_k' を
得、配列逆変換回路４８へ加える。配列逆変換回路４８
は、１ラインメモリを有し、Ｍ_k＝０（ＧＯＯＤ）の状
態ｅ_k' をメモリの先頭番地から番地の昇順に格納し、
Ｍ_k＝１（ＢＡＤ）の状態のｅ_k' をメモリの最終番地
から番地の降順に格納する。このようにして１ライン分
のｅ_k' をメモリに格納した後、予測逆変換回路４９
は、すでに復号化ずみの画像信号とすでにメモリから読
み出したｅ_kにもとづき、次に読み出すｅ_kの状態を示
すモード信号Ｍ_kを配列逆変換回路４８へ加え、Ｍ_kに
対応する新たなｅ_kを配列逆変換回路４８のメモリから
読み出す。予測逆変換回路４９は、１画素に対応する複
数のｅ_kを得た後、すでに復号化ずみの画像信号にもと
づきこれを逆変換し、画像信号Ｘを得、出力する。

【発明が解決しようとする課題】文献２によれば予測順
位符号化の符号量はＤＰＣＭ符号化の符号量より、４値
のとき約６０％、８値で約４０％、１６値で約１０％少
ない。予測順位信号の符号化にランレングス符号化を用
いているので、ＧＯＯＤランを白ラン、ＢＡＤランを黒
ランに対応させ、このランレングス符号化に国際標準の
ＭＨ符号器を利用することが考えられるが、予測順位符
号化ではＧＯＯＤランとＢＡＤランは交互に発生すると
は限らないので、このままでは、国際標準のＭＨ符号器
を利用できないという欠点がある。

【課題を解決するための手段】本発明の多値画像信号の
符号化復号化方法は、既に符号化済みの画像信号を用い
て、現在符号化中の画像信号の発生確率順位を予測し、
現在符号化中の画像信号が何番目の順位であるかを２進
数で表現した予測順位信号を発生し、前記予測順位信号
の各ビットを予測状態によりラベル付けし、ブロック毎
に前記予測順位信号の各ビットを、同一ラベルが連続し
かつビットの値が所定値になる毎にラベルができるだけ
変化するという規則により配列変換し、配列変換した予
測順位信号の各ビットに対してビットの値が所定値であ
るのをランの区切りとして、第１および第２のランレン
グス符号を交互に用いてランレングス符号化し、画像信
号の復号化においてランレングス復号化した予測順位信
号の各ビットを定められた規則に従って逆配列変換し、
既に復号化済みの画像信号を用いて現在復号化中の画像
信号の発生確率順位を予測するとともに、予測状態によ
り予測順位信号の各ビットのラベルを判定して予測順位
信号を元の画像信号に復号する。本発明の多値画像信号
符号化装置は、既に符号化済みの画像信号を用いて、現
在符号化中の画像信号の発生確率順位を予測し、現在符
号化中の画像信号が何番目の順位であるかを２進数で表
現した予測順位信号と予測順位信号の各ビットに対応す
る予測状態信号を発生する手段と、予測状態信号をラベ
ル付けしたとき、同一ラベルが連続しかつビットの値が
所定値になる毎にラベルができるだけ変化するという規
則により前記予測順位信号の各ビットをブロック毎に配
列変換する手段と、配列変換した予測順位信号の各位ビ
ットに対してビットの値が所定値であるのをランの区切
りとして、第１および第２のランレングス符号を交互に
用いてランレングス符号化する手段を有している。本発
明の多値画像信号複号化装置は、ランレングス符号化さ
れた予測順位信号の各ビットをランレングス復号化する
手段と、ブロック毎にランレングス復号化した予測順位
信号の各ビットをランの区切りに応じて定められた規則
に従って逆配列変換する手段と、既に復号化済みの画像
信号とすでにラベルが判定された予測順位信号のビット
を用いて現在復号化中の画像信号に対する予測順位信号
の各ビットの予測順位信号を発生する手段と、予測状態
信号により予測順位信号の各ビットのラベルを判定して
予測順位信号のビットが１画素分そろう毎に既に復号化
済みの画像信号を用いて予測順位信号を元の画像信号に
復号化する手段を有する。

【実施例】次に本発明の多値画像信号符号化方法および
装置を図面を参照して詳細に説明する。図１は本発明の
構成の一例を示すブロック図である。図において、端子
１００に画像信号Ｘが印加され、端子１０１にタイミン
グ信号が印加される。タイミング信号としては画像信号
に対する同期信号とクロックパルスの２つがある。画像
信号Ｘは予測変換回路１により予測順位信号ｅを２進数
現したときの各ビットを示す信号、その予測状態信号ｚ
に変換される。予測順位符号化の説明では、Ｙはｅ_ｋ、
ＭはＭ_ｋと記されていた。Ｙは１か０かの１ビットの信
号で、画像の階調数がｍで、ｍ＝２ⁿの場合それがｎビ
ットまとまって、１個の画素に対する予測順位信号ｅと
なる。予測状態信号Ｚは予測順位信号の各ビットＹが０
である確率を示す１ビットの信号で、確率的にＹが０に
なり易い状態のときＧＯＯＤ、逆の場合をＢＡＤとし
て、それぞれを０，１で表す。したがって、予測状態信
号により予測順位信号の各ビットはＧＯＯＤ又はＢＡＤ
にラベル付けされる。予測順位信号ｅの各ビットＹは配
列変換回路２によって、ブロック毎に配列変換され、配
列変換された予測順位信号Ｕになる。この配列変換は予
測状態信号Ｚの制御の下に実行される。また、１ブロッ
クを例えば１走査線に対応させる。配列変換の具体的方
法は後述するが、基本的には予測順位信号をＧＯＯＤと
ＢＡＤにラベル付けしたとき、Ｕ＝０が続く間は同一ラベルが連続するＵ＝１が生じる毎にラベルができるだけ変化するという規則の下に配列変換を行う。配列変換された予測
順位信号Ｕは平滑化回路３により平滑化信号Ｖに変換さ
れる。平滑化回路３は例えば、図中破線内に示すように
レジスター１１と排他的論理和回路１０とで構成され、
信号Ｕが１になる毎に信号Ｖの符号を１から０または０
から１の如く反転させる働きをする。この変換により、
信号Ｕが１になる間隔が信号Ｖを白黒２値信号と見なし
たときのランレングスに対応するようになる。平滑化信
号Ｖはランレングス符号器４により、白黒別のランレン
グス符号を用いてランレングス符号化される。ランレン
グス符号器としては国際標準のＭＨ符号器を用いること
ができる。このランレングス符号化においては、ＧＯＯ
Ｄにラベル付けされた予測順位信号系列が白のランレン
グス符号で符号化される確率が高く、ＢＡＤにラベル付
けされた予測順位信号系列が黒のランレングス符号で符
号化される確率が高くなるので、それぞれの統計的性質
に合ったランレングス符号を設計すれば効率的なランレ
ングス符号化が実行される。ランレングス符号化により
得られた圧縮符号Ｃは伝送路に送出されるかあるいはフ
ァイルメモリーに格納される。図１では伝送路の場合を
参照数字５で示した。伝送路あるいはファイルメモリー
からとり出された圧縮符号Ｃ’は、参照数字６，７，
８，９で構成される復号化装置により符号化の逆変換処
理を受け元の画像信号Ｘ’に復号され、端子２００に出
力される。圧縮符号Ｃ’は、まずランレングス復号器６
によりランレングス復号される信号Ｖ’に変換され、更
に逆平滑化回路７により白黒の変化点が抽出された信号
Ｕ’に変換される。逆平滑化回路７は例えば図中破線内
に示すように、レジスター１３と排他的論理和１２で構
成される。レジスター１２の出力には１ビット前の復号
値が現れるので、排他的論理和出力では白黒の変化点が
１となり、これがＵ’＝１に対応する。信号Ｕ’は更に
配列逆変換回路８により配列逆変換され予測順位信号を
構成するビットＹ’に変換される。配列逆変換回路は予
測逆変換回路９から供給される予測状態信号Ｚ’の制御
のもとに動作し、符号化の逆の論理によって、信号Ｕ’
を配列逆変換し、予測順位信号を構成するビットＹ’に
変換する。予測順位信号を構成するビットＹ’は予測逆
変換回路９により、１サンプル分まとめられて予測順位
信号となり、既に復号化済みの画像信号をもとにして画
像信号Ｘ’に変換される。なお、ランレングス復号器６
からはタイミング信号が復号化装置の各部に供給される
と共に出力端子２０１にとり出される。ここで、伝送路
やファイルメモリーに誤りがなければＣ’＝Ｃであり、
符号化および復号化動作が正しく行われれば、Ｖ’＝
Ｖ，Ｕ’＝Ｕ，Ｚ’＝Ｚ，Ｙ’＝Ｙ，Ｘ’＝Ｘとなる。
図３に８値画像信号に対する予測変換回路の実施例を示
す。ここで、予測に用いる参照画素は図２に示すように
２ラインにわたる２画素とする。すなわち、画素Ａは符
号化しようとする画素Ｘと同一ラインにある直前の画
素、画素Ｂは前ラインの画素である。Ａ，Ｂの画素は既
に符号化済の画素であるから予測の参照画素として用い
ることができる。図３において、８値画像信号Ｘはタッ
プ付き遅延線１１に印加され、その２つの出力端子には
参照画素Ａ，Ｂに対応する参照信号がとり出される。こ
れらの参照信号は予測符号化ＲＯＭ（ＲｅａｄＯｎｌ
ｙＭｅｍｏｒｙ）１５、第１モード信号ＲＯＭ１６、
第２モード信号ＲＯＭ１７、第３モード信号ＲＯＭ１８
に印加される。予測符号化ＲＯＭ１５は参照信号と画像
信号Ｘに基づき画像信号Ｘに対する３ビットの予測順位
信号ｅ＝（ｅ₁，ｅ₂，ｅ₃）（ｅ₁がＭＳＢでｅ₃が
ＬＳＢ）を発生し、パラレルシリアル変換器１９に加え
る。パラレルシリアル変換器１９は予測順位信号の各ビ
ットをＭＳＢからＬＳＢの順に取出し、これを１ビット
の信号Ｙとして出力する。第１モード信号ＲＯＭ１６は
参照信号に基づき、予測順位信号の第１ビットｅ₁に対
する予測状態信号Ｍ₁を発生する。第２モード信号ＲＯ
Ｍ１７は、参照信号と予測順位信号の第１ビットｅ₁、
に基づき予測順位信号の第２ビットｅ₂に対する予測状
態信号Ｍ₂を発生する。第３モード信号ＲＯＭ１８は、
参照信号および予測順位信号の第１ビットｅ₁、と第２
ビットｅ₂に基づき予測順位信号の第３ビットｅ₃に対
する予測状態信号Ｍ₃を発生する。各予測状態信号Ｍ
_ｋはセレクタ２０に加えられる。各予測状態信号Ｍ_kは
ｅ_kが０である確率が例えば０．９４以上のものをＧＯ
ＯＤ（Ｍ_k＝０）、以下のものをＢＡＤ（Ｍ_k＝１）と
なる様に統計的に定める。セレクタ２０は予測状態信号
をＭ₁，Ｍ₂，Ｍ₃の順でパラレルシリアル変換された
予測順位信号Ｙと同期して取出し、Ｙに対応する予測状
態信号Ｚとして出力する。なお、端子１０から供給され
るタイミング信号Ｔは、タップ付遅延線１４、パラレル
シリアル変換器１９、セレクタ２０のクロックパルスお
よび初期状態の設定に用いられる。図４は図３の予測変
換回路と対になる予測逆変換回路の実施例である。図に
おいて参照数字２１，２３，２４，２５は、それぞれタ
ップ付遅延線および第１モード信号ＲＯＭ、第２モード
信号ＲＯＭ、第３モード信号ＲＯＭで、予測変換回路で
用いたものとそれぞれ同じ働きをする。セレクタ２７は
第１モード信号ＲＯＭ２３から予測状態信号Ｍ₁' を入
力し、これを信号Ｚ’として出力する。図１に示した配
列逆変換回路８は信号Ｚ’を入力し、これに対応するパ
ラレルシリアル変換された予測順位信号Ｙ’をレジスタ
４０に出力する。レジスタ４０は信号Ｙ’を信号ｅ₁’
として第２モード信号ＲＯＭ２４と予測復号化ＲＯＭ２
２に出力する。信号ｅ₁’は予測順位信号の第１ビット
（ＭＳＢ）である。第２モード信号ＲＯＭ２４は、信号
ｅ₁’とタップ付遅延線２１からの参照信号Ａ’、Ｂ’
に基づき予測状態信号Ｍ₂’を発生し、セレクタ２７に
出力する。セレクタ２７は今度は信号Ｍ₂’を選択し、
信号Ｚ’として出力する。図１に示した配列逆変換回路
８は信号Ｚ’を入力し、これに対応するパラレルシリア
ル変換された予測順位信号Ｙ’をレジスタ４１に出力す
る。レジスタ４１は信号Ｙ’を信号ｅ₂’として第３モ
ード信号ＲＯＭ２５と予測復号化ＲＯＭ２２に出力す
る。信号ｅ₂’は予測順位信号の第２ビットである。第
３モード信号ＲＯＭ２５は、信号ｅ₁’と信号ｅ₂’
および参照信号Ａ’、Ｂ’に基づき予測状態信号Ｍ₃’
を発生し、セレクタ２７に出力する。セレクタ２７は、
今度は信号Ｍ₃’を選択し信号Ｚ’として出力する。図
１に示した配列逆変換回路８は信号Ｚ’を入力し、これ
に対応するパラレルシリアル変換された予測順位信号
Ｙ’をレジスタ４２に出力する。レジスタ４２は信号
Ｙ’を信号ｅ₃’として予測復号化ＲＯＭ２２に出力す
る。信号ｅ₃’は予測順位信号の第３ビット（ＬＳＢ）
である。予測復号化ＲＯＭ２２は参照信号Ａ’、Ｂ’と
予測順位信号（ｅ₁’、ｅ₂’、ｅ₃’）に基づき、復
号化画像信号Ｘ’を発生し、端子２００およびタップ付
遅延線２１に加える。なお、端子から供給されるタイミ
ング信号Ｔ’はタップ付遅延線２１、セレクタ２７、レ
ジスタ４０、４１、４２のクロックパルスおよび初期状
態の設定に用いられる。次に配列変換および配列逆変
換について説明する。図５は配列変換回路の実施例を示
すブロック図である。図において、予測順位信号の各ビ
ットＹは１走査線毎にメモリー２８に一旦書き込まれ次
に読み出され配列変換された信号Ｕとして出力される。
配列変換はメモリーの書き込みと読み出しの過程で行う
ので、メモリーのアドレス制御が配列変換の方法と対応
する。図７に配列変換法の一例を示す。図において、Ａ
１は１走査線の予測順位信号の各ビット時系列を示す。
同じ画素に対してはＭＳＢに近い方が先に発生する。こ
の場合、簡単の為１走査線の画素数は４、画像の階調数
は８で３ビット／画素としている。Ｙｉの添字ｉは信号
の時系列番号を示し、斜線は予測順位信号のビットが１
であることを示す。したがって、図においてＹ₁〜
Ｙ₃，Ｙ₅，Ｙ₇〜Ｙ₁₀，Ｙ₁₂は０、Ｙ₄，Ｙ₆，Ｙ₁₁
は１である。Ａ２は信号Ｙに対応する予測状態信号Ｚの
時系列を示す。ＧはＧＯＯＤ、ＢはＢＡＤを示す。信号
Ｙ_iはこの予測状態Ｚ_iによって、それぞれＧＯＯＤか
ＢＡＤかのいずれかにラベル付けされる。すなわち、図
の例では、Ｙ₁，Ｙ₂，Ｙ₄，Ｙ₅，Ｙ₇，Ｙ₁₀，Ｙ
₁₁はＧＯＯＤ、Ｙ₃，Ｙ₆，Ｙ₈，Ｙ₉，Ｙ₁₂はＢＡＤ
である。Ａ３はメモリーに書き込んだ信号Ｙを示す。メ
モリーの番地は左端から順に１，２，…１２番地とす
る。そして書き込みにおいてはＧＯＯＤにラベル付けさ
れた信号Ｙを１番地から順に書き込み、ＢＡＤにラベル
付けされた信号Ｙを１２番地（１走査線の最終番地）か
ら逆向きに書き込む。このように書き込めば、メモリー
内にＧＯＯＤとＢＡＤの信号Ｙをそれぞれ分離して書き
込むことができる。図において、メモリーの１〜７番地
にはＧＯＯＤの信号Ｙ、８〜１２番地にはＢＡＤの信号
Ｙが書き込まれている。次に、メモリー内の信号Ｙを読
み出すが、読み出した時系列信号を図７のＡ４に示す。
まず、メモリー内の１番地からＧＯＯＤに対応するＹが
１になるまで順に読み出す。図の例では３番地に書き込
まれたＹ₄が、Ｙが０から１になるところなので、
Ｙ₁，Ｙ₂，Ｙ₄が読み出される。Ｙ＝１になると今度
はメモリーの最終番地からＢＡＤのＹをやはりＹ＝１に
なるまで読み出す。図の例では１１番地のＹ₆がＹが０
から１になるところなのでＹ₃とＹ₆が読み出される。
次は再び、ＧＯＯＤを読み出すので、Ｙ₅，Ｙ₇，
Ｙ₁₀，Ｙ₁₁が読み出され、Ｙ₁₁がＹが０から１になると
ころなので、次はＢＡＤの（Ｙ₈，Ｙ₉，Ｙ₁₂）が読み
出される。このようにして、配列変換が完了する。配列
変換された信号Ｕは図７のＡ４に示されているが、同図
Ａ５にはこれを平滑化した信号Ｖを示している。すなわ
ち、信号Ｙが１になる毎に白黒を反転させる処理が施さ
れている。同図Ａ６には信号Ｖを白黒別ランレングス符
号化したときのランレングスを示している。図におい
て、Ｗ２，Ｗ４は白のランレングスが２，４であること
を表し、Ｂ２，Ｂ４は黒のランレングスが２，４である
ことを表す。平滑化処理を施した信号のランはＷ２，Ｂ
２，Ｗ４，Ｂ４の４つである。これに対して、平滑化処
理をせずに信号Ｕ（図７のＡ４）を直接ランレングス符
号化したとすれば、ランはＷ２，Ｂ１，Ｗ１，Ｂ１，Ｗ
３，Ｂ１，Ｗ３の７つとなるので、平滑化処理により大
幅なラン数の削減が行われていることが分かる。配列変換の規則は（１）同一ラベルをできるだけ連続させること（２）予測順位信号のビットが０から１になる毎にラベ
ルをできるだけ変化させることの２つの条件を満たすようにするのが、符号化能率の点
から得策である。勿論、配列逆変換により元に戻せるこ
とが前提条件であることは言うまでもない。ここで「で
きるだけ」という意味は「出来ない場合は逆変換が可能
な他の約束を用いる」ことを示す。例えば図７に示した
例で、信号ＹはＡ１で与えられた予測状態信号はＹ₁〜
Ｙ₁₂に対してすべてＧＯＯＤであった場合を仮定しよ
う。そうすると、メモリには図７のＢ３に示すようにＹ
₁〜Ｙ₁₂の順に予測順位信号を構成するビットが書き込
まれる。この場合、すべてのデータはＧＯＯＤにラベル
付けされているので、ＧＯＯＤに次にＢＡＤを読み出す
ことはできない。メモリーの読み出しを、前述の様にア
ドレスの昇順と降順にとり、Ｙ＝１になる毎にこれらを
切換えることにすれば、配列変換後の信号Ｙは図７のＢ
４に示すようになる。この配列変換においてはＹ＝１に
なる毎にラベルが変化していないが、配列逆変換は可能
であるから、本発明では許される。図５に戻って配列変
換回路の動作説明を行う。図において、参照数字３０，
３１はそれぞれ、昇順アドレスカウンタ（アップカウン
タ）および降順アドレスカウンタ（ダウンカウンタ）で
ある。参照数字２９は論理回路で、書き込み時には予測
状態信号Ｚにより、Ｚ＝０（ＧＯＯＤ）のときはアップ
カウントパルスを線１２３に発生し、Ｚ＝１（ＢＡＤ）
のときはダウンカウントパルスを線１２４に発生する。
また、マルチプレクサー３２の切換信号を線１２２に通
して供給する。この切換信号は書き込み時には予測状態
信号Ｚそのものである。アップカウンタ３０およびダウ
カウンタ３１は走査線の始まりにおいてタイミングパル
スにより、それぞれ、１および１２がロードされ、以後
はカウントパルスにより、メモリーアドレスを１番地づ
つ増減させる。２つのアドレスカウンタにより指定され
たアドレスはマルチプレクサー３２で切換えられて線１
２１を通してメモリー２８のアドレス線に供給される。
このようにして、メモリー２８にはＧＯＯＤの信号Ｙが
昇順に、ＢＡＤの信号Ｙが降順に書き込まれる。１走査
線の書き込みが終了すると、次の走査線の画像信号が到
来する前にメモリーの読み出しを行う。なお、次の走査
線の画像信号が連続して到来する場合は配列変換回路を
ダブルにして交互に動作させればよい。読み出しにおい
ては読み出した信号Ｕをフリップフロップ３３に供給
し、Ｕ＝１になる毎にフリップフロップを反転させる。
フリップフロップの出力は線１２５を通して理論回路２
９に供給し、読み出し時のアップカウントパルス、ダウ
ンカウントパルスおよびマルチプレクサーの切換信号作
成に用いられる。図６は図５に示した配列変換回路に対
応する配列逆変換回路を示す。参照数字３４はメモリ
ー、３５は論理回路、３６はアップカウンタ、３７はダ
ウンカウンタ、３８はマルチプレクサ、３９はフリップ
フロップで、これらは配列変換回路で用いたものと同じ
機能で同じ動作をする。ただし、書き込みと読み出しの
動作が配列逆変換回路とは逆になる。すなわち、配列変
換された信号Ｕ’がまず、メモリー３４に書き込まれる
が、書き込みアドレスの制御はＵ’＝１になる毎に出力
を反転させるフリップフロップ３９の出力信号を用いて
行なう。また、読み出しアドレスの制御は予測逆変換回
路から供給される予測状態信号Ｚ’を用いて行う。これ
らのアドレス制御の方法は配列変換回路と同じである。
以上に配列変換とその逆変換動作を説明したが、配列変
換の方法および回路はメモリー番地の昇順・降順による
もの以外にもいろいろ考えられる。例えばメモリーを２
個用意し、ＧＯＯＤの信号Ｙを第１のメモリーに、ＢＡ
Ｄの信号Ｙをだい２のメモリーに順に格納し、信号Ｙが
１になる毎に読みだすメモリを交互に変えても良い。

【発明の効果】本発明の原理と効果を要約すれば次のよ
うになる。まず、本発明においては、画像信号を予測と
いう手段により画像信号の発生確率順位を示す予測順位
信号に変換するが、この変換によって、画像信号の冗長
度が削減される。冗長度が削減された画像信号、すなわ
ち予測順位信号をできるだけ少ないビット数の符号で表
すために、ランレングス符号化を用いる。ここで、ラン
レングス符号化の方法としてはＭＨ符号化の如く、平均
ランレングスが比較的長い場合に適合する白ラン用符号
と平均ランレングスが比較的短い場合に適合する黒ラン
用符号の２種類のランレングス符号を用意し、白、黒、
白、黒、…の如く用いるランレングス符号を交互に変化
させる。本発明においては、この様なランレングス符号
化に適合するように前述の予測順位信号を２進数で表現
しその各ビットに変換を施す。変換には２種の手段が含
まれており、その第１は予測状態信号により予測順位信
号の各ビットが０になりやすいグループ（ＧＯＯＤ）と
０になりにくいグループ（ＢＡＤ）の２つのグループに
ラベル付けし、配列変換する手段である。この手段によ
り、ＧＯＯＤは平均ランレングスが比較的長いグルー
プ、ＢＡＤは平均ランレングスが比較的短いグループに
分離することができる。第２の手段は予測順位信号の各
ビット１をランの区切りとして符号化する手段であり、
具体的には予測順位信号の各ビットが１になる毎に白黒
を反転させる平滑化処理を施す。ＧＯＯＤとＢＡＤを予
測順位信号のビットが１になる毎に交互に読み出す配列
変換と平滑化処理により、ＧＯＯＤのランは白のランレ
ングス符号で、ＢＡＤのランは黒のランレングス符号で
符号化される確率が高まり、圧縮率を高くすることがで
きるのである。本発明の特徴は変換処理を標準のＭＨ符
号器及び復号器の前後で施すことにより、ＭＨ符号化ア
ルゴリズムを何ら変更せずに、多値画像の効率良いデー
タ圧縮を可能ならしめることにあり、種々の目的に応用
可能である。

【図面の簡単な説明】

【図１】本発明の構成を示すブロック図

【図２】参照画素配置を示す略図

【図３】予測変換回路のブロック図

【図４】予測逆変換回路のブロック図

【図５】配列変換回路の一例と示すブロック図

【図６】配列逆変換回路の一例を示すブロック図

【図７】配列変換動作の説明に供する略図

【図８】予測順位符号化のブロック図

【符号の説明】

１予測変換回路２配列変換回路３平滑化回路４ランレングス符号器５伝送路６ランレングス復号器７逆平滑化回路８配列逆変換回路９予測逆変換回路１０排他的論理和回路１１レジスタ１２排他的論理和回路１３レジスタ１４タップ付遅延線１５予測符号化ＲＯＭ１６第１モード信号ＲＯＭ１７第２モード信号ＲＯＭ１８第３モード信号ＲＯＭ１９パラレルシリアル変換器２０セレクタ２１タップ付遅延線２２予測復号化ＲＯＭ２３第１モード信号ＲＯＭ２４第２モード信号ＲＯＭ２５第３モード信号ＲＯＭ２７セレクタ２８メモリ２９論理回路３０アップカウンタ３１ダウンカウンタ３２マルチプレクサ３３フリップフロップ３４メモリ３５論理回路３６アップカウンタ３７ダウンカウンタ３８マルチプレクサ３９フリップフロップ４０レジスタ４１レジスタ４２レジスタ４３予測変換回路４４配列変換回路４５ランレングス符号器４６伝送路４７ランレングス復号器４８配列逆変換回路４９予測逆変換回路

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成４年６月１７日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】請求項３

【補正方法】変更

【補正内容】

【手続補正２】

【補正対象書類名】明細書

【補正対象項目名】発明の詳細な説明

【補正方法】追加

【補正内容】

【発明の詳細な説明】

【０００１】

【０００２】

【従来の技術】予測符号化では、通常、予測信号と原信
号との差、すなわち予測誤差信号をエントロピ−符号化
する。これは予測的中率が高いと、予測誤差信号が０に
集中する傾向が高く、原信号より予測誤差信号の方がエ
ントロピーが小さくなることを利用している。

【０００３】これに対し、ピ・エリアス（Ｐ．Ｅｌｉａ
ｓ）は、予測符号化において原信号をできるだけ小さな
エントロピーを有する信号に変換する方法について考察
し、原信号を予測によって発生確率順位に順位付けるな
らば、その順位を示す信号のエントロピーが、原信号に
対し他のどんな変換を行って得られる信号のエントロピ
ーよりも小さいことを示した。これは（ピ−・エリアス
（Ｐ．Ｅｌｉａｓ）「プレディクティブコーディング
（Ｐｒｅｄｉｃｔｉｖｅｃｏｄｉｎｇ）」ＩＲＥＴ
ｒａｎｓ．，ＩＴ−１誌１９５５年３月号、ＰＰ．１
６〜３３、以下、「文献１」）に詳しく示されている。

【０００４】以下では、原信号の発生確率順位を示す信
号を順位信号、原信号を順位信号に変換するプロセスを
順位予測と呼ぶことにする。もちろん予測誤差信号のエ
ントロピーより、順位信号のエントロピーの方が必ず小
さい。以下において、順位信号は予測順位信号と呼ぶこ
ともある。

【０００５】このことを利用して、順位信号を２進数で
表現しランレングス符号化する方式が（水野昇治「中間
調画像の予測順位符号化」電子情報通信学会論文誌Ｂ−
１Ｖｏｌ．Ｊ７３−Ｂ−Ｉ，Ｎｏ．６，１９９０年６月
号、ｐｐ．５５４〜５６０、以下、「文献２」）に詳し
く示されている。

【０００６】以下図８を用いて、予測順位符号化の説明
を行う。送信側では予測変換回路４３は、すでに符号化
ずみの画像信号を用いて、入力画像信号Ｘの発生確率順
位を予測し、順位信号ｅを２進数表現し、それをパラレ
ルシリアル変換して信号ｅ_kを得、配列変換回路４４へ
加える。それと同時に、予測変換回路４４は、すでに符
号化ずみの画像信号とすでに配列変換メモリ４４に書き
込みずみのｅ_ｋにもとづき信号ｅ_kが０になる確率が高
いか低いかを示す信号Ｍ_kを発生し、信号ｅ_kとともに
配列変換回路４４へ加える。

【０００７】配列変換回路４４は、１ラインメモリを有
し、Ｍ_k＝０（ＧＯＯＤ）の状態のｅ_kをメモリの先頭
番地から番地の昇順に格納し、Ｍ_k＝１（ＢＡＤ）の状
態のｅ_kをメモリの最終番地から番地の降順に格納す
る。このようにして１ライン分のｅ_kをメモリに格納し
た後、ランレングス符号器４５はＧＯＯＤのｅ_k’とＢ
ＡＤのｅ_k’を順に読出し、それぞれ別々のランレング
ス符号を用いて符号化し、ランレングス符号Ｃを得、伝
送路４６へ送出する。ｅ_k’はｅ_kを並びかえたもので
ある。

【０００９】受信側では、ランレングス復号器４７は、
伝送路４６よりランレングス符号Ｃを入力し、これを復
号化して信号ｅ_k’を得、配列逆変換回路４８へ加え
る。配列逆変換回路４８は、１ラインメモリを有し、Ｍ
_k＝０（ＧＯＯＤ）の状態ｅ_k’をメモリの先頭番地か
ら番地の昇順に格納し、Ｍ_k＝１（ＢＡＤ）の状態のｅ
_k’をメモリの最終番地から番地の降順に格納する。こ
のようにして１ライン分のｅ_k’をメモリに格納した
後、予測逆変換回路４９は、すでに復号化ずみの画像信
号とすでにメモリから読み出したｅ_kにもとづき、次に
読み出すｅ_kの状態を示すモード信号Ｍ_kを配列逆変換
回路４８へ加え、Ｍ_kに対応する新たなｅ_kを配列逆変
換回路４８のメモリから読み出す。予測逆変換回路４９
は、１画素に対応する複数のｅ_kを得た後、すでに復号
化ずみの画像信号にもとづきこれを逆変換し、画像信号
Ｘを得、出力する。

【００１０】

【００１１】

【課題を解決するための手段】本発明の多値画像信号の
符号化復号化方法は、既に符号化済みの画像信号を用い
て、現在符号化中の画像信号の発生確率順位を予測し、
現在符号化中の画像信号が何番目の順位であるかを２進
数で表現した予測順位信号を発生し、前記予測順位信号
の各ビットを予測状態によりラベル付けし、ブロック毎
に前記予測順位信号の各ビットを、同一ラベルが連続し
かつビットの値が所定値になる毎にラベルができるだけ
変化するという規則により配列変換し、配列変換した予
測順位信号の各ビットに対してビットの値が所定値であ
るのをランの区切りとして、第１および第２のランレン
グス符号を交互に用いてランレングス符号化し、画像信
号の復号化においてランレングス復号化した予測順位信
号の各ビットを定められた規則に従って逆配列変換し、
既に復号化済みの画像信号を用いて現在復号化中の画像
信号の発生確率順位を予測するとともに、予測状態によ
り予測順位信号の各ビットのラベルを判定して予測順位
信号を元の画像信号に復号する。

【００１２】本発明の多値画像信号符号化装置は、既に
符号化済みの画像信号を用いて、現在符号化中の画像信
号の発生確率順位を予測し、現在符号化中の画像信号が
何番目の順位であるかを２進数で表現した予測順位信号
と予測順位信号の各ビットに対応する予測状態信号を発
生する手段と、予測状態信号をラベル付けしたとき、同
一ラベルが連続しかつビットの値が所定値になる毎にラ
ベルができるだけ変化するという規則により前記予測順
位信号の各ビットをブロック毎に配列変換する手段と、
配列変換した予測順位信号の各位ビットに対してビット
の値が所定値であるのをランの区切りとして、第１およ
び第２のランレングス符号を交互に用いてランレングス
符号化する手段を有している。

【００１３】本発明の多値画像信号複号化装置は、ラン
レングス符号化された予測順位信号の各ビットをランレ
ングス復号化する手段と、ブロック毎にランレングス復
号化した予測順位信号の各ビットをランの区切りに応じ
て定められた規則に従って逆配列変換する手段と、既に
復号化済みの画像信号とすでにラベルが判定された予測
順位信号のビットを用いて現在復号化中の画像信号に対
する予測順位信号の各ビットの予測順位信号を発生する
手段と、予測状態信号により予測順位信号の各ビットの
ラベルを判定して予測順位信号のビットが１画素分そろ
う毎に既に復号化済みの画像信号を用いて予測順位信号
を元の画像信号に復号化する手段を有する。

【００１４】

【実施例】次に本発明の多値画像信号符号化方法および
装置を図面を参照して詳細に説明する。

【００１５】図１は本発明の構成の一例を示すブロック
図である。図において、端子１００に画像信号Ｘが印加
され、端子１０１にタイミング信号が印加される。タイ
ミング信号としては画像信号に対する同期信号とクロッ
クパルスの２つがある。

【００１６】画像信号Ｘは予測変換回路１により予測順
位信号ｅを２進数現したときの各ビットを示す信号、そ
の予測状態信号ｚに変換される。予測順位符号化の説明
では、Ｙはｅ_ｋ、ＭはＭ_ｋと記されていた。Ｙは１か０
かの１ビットの信号で、画像の階調数がｍで、ｍ＝２ⁿ
の場合それがｎビットまとまって、１個の画素に対する
予測順位信号ｅとなる。

【００１７】予測状態信号Ｚは予測順位信号の各ビット
Ｙが０である確率を示す１ビットの信号で、確率的にＹ
が０になり易い状態のときＧＯＯＤ、逆の場合をＢＡＤ
として、それぞれを０，１で表す。したがって、予測状
態信号により予測順位信号の各ビットはＧＯＯＤ又はＢ
ＡＤにラベル付けされる。

【００１８】予測順位信号ｅの各ビットＹは配列変換回
路２によって、ブロック毎に配列変換され、配列変換さ
れた予測順位信号Ｕになる。この配列変換は予測状態信
号Ｚの制御の下に実行される。また、１ブロックを例え
ば１走査線に対応させる。配列変換の具体的方法は後述
するが、基本的には予測順位信号をＧＯＯＤとＢＡＤに
ラベル付けしたとき、Ｕ＝０が続く間は同一ラベルが連続するＵ＝１が生じる毎にラベルができるだけ変化するという規則の下に配列変換を行う。

【００１９】配列変換された予測順位信号Ｕは平滑化回
路３により平滑化信号Ｖに変換される。平滑化回路３は
例えば、図中破線内に示すようにレジスター１１と排他
的論理和回路１０とで構成され、信号Ｕが１になる毎に
信号Ｖの符号を１から０または０から１の如く反転させ
る働きをする。この変換により、信号Ｕが１になる間隔
が信号Ｖを白黒２値信号と見なしたときのランレングス
に対応するようになる。

【００２０】平滑化信号Ｖはランレングス符号器４によ
り、白黒別のランレングス符号を用いてランレングス符
号化される。ランレングス符号器としては国際標準のＭ
Ｈ符号器を用いることができる。このランレングス符号
化においては、ＧＯＯＤにラベル付けされた予測順位信
号系列が白のランレングス符号で符号化される確率が高
く、ＢＡＤにラベル付けされた予測順位信号系列が黒の
ランレングス符号で符号化される確率が高くなるので、
それぞれの統計的性質に合ったランレングス符号を設計
すれば効率的なランレングス符号化が実行される。

【００２１】ランレングス符号化により得られた圧縮符
号Ｃは伝送路に送出されるかあるいはファイルメモリー
に格納される。図１では伝送路の場合を参照数字５で示
した。伝送路あるいはファイルメモリーからとり出され
た圧縮符号Ｃ’は、参照数字６，７，８，９で構成され
る復号化装置により符号化の逆変換処理を受け元の画像
信号Ｘ’に復号され、端子２００に出力される。

【００２２】圧縮符号Ｃ’は、まずランレングス復号器
６によりランレングス復号される信号Ｖ’に変換され、
更に逆平滑化回路７により白黒の変化点が抽出された信
号Ｕ’に変換される。逆平滑化回路７は例えば図中破線
内に示すように、レジスター１３と排他的論理和１２で
構成される。レジスター１２の出力には１ビット前の復
号値が現れるので、排他的論理和出力では白黒の変化点
が１となり、これがＵ’＝１に対応する。

【００２３】信号Ｕ’は更に配列逆変換回路８により配
列逆変換され予測順位信号を構成するビットＹ’に変換
される。配列逆変換回路は予測逆変換回路９から供給さ
れる予測状態信号Ｚ’の制御のもとに動作し、符号化の
逆の論理によって、信号Ｕ’を配列逆変換し、予測順位
信号を構成するビットＹ’に変換する。予測順位信号を
構成するビットＹ’は予測逆変換回路９により、１サン
プル分まとめられて予測順位信号となり、既に復号化済
みの画像信号をもとにして画像信号Ｘ’に変換される。

【００２４】なお、ランレングス復号器６からはタイミ
ング信号が復号化装置の各部に供給されると共に出力端
子２０１にとり出される。ここで、伝送路やファイルメ
モリーに誤りがなければＣ’＝Ｃであり、符号化および
復号化動作が正しく行われれば、Ｖ’＝Ｖ，Ｕ’＝Ｕ，
Ｚ’＝Ｚ，Ｙ’＝Ｙ，Ｘ’＝Ｘとなる。

【００２５】図３に８値画像信号に対する予測変換回路
の実施例を示す。ここで、予測に用いる参照画素は図２
に示すように２ラインにわたる２画素とする。すなわ
ち、画素Ａは符号化しようとする画素Ｘと同一ラインに
ある直前の画素、画素Ｂは前ラインの画素である。Ａ，
Ｂの画素は既に符号化済の画素であるから予測の参照画
素として用いることができる。

【００２６】図３において、８値画像信号Ｘはタップ付
き遅延線１１に印加され、その２つの出力端子には参照
画素Ａ，Ｂに対応する参照信号がとり出される。これら
の参照信号は予測符号化ＲＯＭ（ＲｅａｄＯｎｌｙ
Ｍｅｍｏｒｙ）１５、第１モード信号ＲＯＭ１６、第２
モード信号ＲＯＭ１７、第３モード信号ＲＯＭ１８に印
加される。

【００２７】予測符号化ＲＯＭ１５は参照信号と画像信
号Ｘに基づき画像信号Ｘに対する３ビットの予測順位信
号ｅ＝（ｅ₁，ｅ₂，ｅ₃）（ｅ₁がＭＳＢでｅ₃がＬ
ＳＢ）を発生し、パラレルシリアル変換器１９に加え
る。パラレルシリアル変換器１９は予測順位信号の各ビ
ットをＭＳＢからＬＳＢの順に取出し、これを１ビット
の信号Ｙとして出力する。

【００２８】第１モード信号ＲＯＭ１６は参照信号に基
づき、予測順位信号の第１ビットｅ₁に対する予測状態
信号Ｍ₁を発生する。

【００２９】第２モード信号ＲＯＭ１７は、参照信号と
予測順位信号の第１ビットｅ₁、に基づき予測順位信号
の第２ビットｅ₂に対する予測状態信号Ｍ₂を発生す
る。

【００３０】第３モード信号ＲＯＭ１８は、参照信号お
よび予測順位信号の第１ビットｅ₁、と第２ビットｅ₂
に基づき予測順位信号の第３ビットｅ₃に対する予測状
態信号Ｍ₃を発生する。各予測状態信号Ｍ_ｋはセレク
タ２０に加えられる。各予測状態信号Ｍ_kはｅ_kが０で
ある確率が例えば０．９４以上のものをＧＯＯＤ（Ｍ_k
＝０）、以下のものをＢＡＤ（Ｍ_k＝１）となる様に統
計的に定める。

【００３１】セレクタ２０は予測状態信号をＭ₁，
Ｍ₂，Ｍ₃の順でパラレルシリアル変換された予測順位
信号Ｙと同期して取出し、Ｙに対応する予測状態信号Ｚ
として出力する。なお、端子１０から供給されるタイミ
ング信号Ｔは、タップ付遅延線１４、パラレルシリアル
変換器１９、セレクタ２０のクロックパルスおよび初期
状態の設定に用いられる。

【００３２】図４は図３の予測変換回路と対になる予測
逆変換回路の実施例である。図において参照数字２１，
２３，２４，２５は、それぞれタップ付遅延線および第
１モード信号ＲＯＭ、第２モード信号ＲＯＭ、第３モー
ド信号ＲＯＭで、予測変換回路で用いたものとそれぞれ
同じ働きをする。

【００３３】セレクタ２７は第１モード信号ＲＯＭ２３
から予測状態信号Ｍ₁’を入力し、これを信号Ｚ’とし
て出力する。図１に示した配列逆変換回路８は信号Ｚ’
を入力し、これに対応するパラレルシリアル変換された
予測順位信号Ｙ’をレジスタ４０に出力する。

【００３４】レジスタ４０は信号Ｙ’を信号ｅ₁’とし
て第２モード信号ＲＯＭ２４と予測復号化ＲＯＭ２２に
出力する。信号ｅ₁’は予測順位信号の第１ビット（Ｍ
ＳＢ）である。第２モード信号ＲＯＭ２４は、信号
ｅ₁’とタップ付遅延線２１からの参照信号Ａ’、Ｂ’
に基づき予測状態信号Ｍ₂’を発生し、セレクタ２７に
出力する。セレクタ２７は今度は信号Ｍ₂’を選択し、
信号Ｚ’として出力する。

【００３５】図１に示した配列逆変換回路８は信号Ｚ’
を入力し、これに対応するパラレルシリアル変換された
予測順位信号Ｙ’をレジスタ４１に出力する。レジスタ
４１は信号Ｙ’を信号ｅ₂’として第３モード信号ＲＯ
Ｍ２５と予測復号化ＲＯＭ２２に出力する。信号ｅ₂’
は予測順位信号の第２ビットである。第３モード信号Ｒ
ＯＭ２５は、信号ｅ₁’と信号ｅ₂’および参照信号
Ａ’、Ｂ’に基づき予測状態信号Ｍ₃’を発生し、セレ
クタ２７に出力する。セレクタ２７は、今度は信号
Ｍ₃’を選択し信号Ｚ’として出力する。

【００３６】図１に示した配列逆変換回路８は信号Ｚ’
を入力し、これに対応するパラレルシリアル変換された
予測順位信号Ｙ’をレジスタ４２に出力する。レジスタ
４２は信号Ｙ’を信号ｅ₃’として予測復号化ＲＯＭ２
２に出力する。信号ｅ₃’は予測順位信号の第３ビット
（ＬＳＢ）である。予測復号化ＲＯＭ２２は参照信号
Ａ’、Ｂ’と予測順位信号（ｅ₁’、ｅ₂’、ｅ₃’）
に基づき、復号化画像信号Ｘ’を発生し、端子２００お
よびタップ付遅延線２１に加える。

【００３７】なお、端子から供給されるタイミング信号
Ｔ’はタップ付遅延線２１、セレクタ２７、レジスタ４
０、４１、４２のクロックパルスおよび初期状態の設定
に用いられる。次に配列変換および配列逆変換につい
て説明する。図５は配列変換回路の実施例を示すブロッ
ク図である。図において、予測順位信号の各ビットＹは
１走査線毎にメモリー２８に一旦書き込まれ次に読み出
され配列変換された信号Ｕとして出力される。配列変換
はメモリーの書き込みと読み出しの過程で行うので、メ
モリーのアドレス制御が配列変換の方法と対応する。

【００３８】図７に配列変換法の一例を示す。図におい
て、Ａ１は１走査線の予測順位信号の各ビット時系列を
示す。同じ画素に対してはＭＳＢに近い方が先に発生す
る。この場合、簡単の為１走査線の画素数は４、画像の
階調数は８で３ビット／画素としている。Ｙｉの添字ｉ
は信号の時系列番号を示し、斜線は予測順位信号のビッ
トが１であることを示す。したがって、図においてＹ₁
〜Ｙ₃，Ｙ₅，Ｙ₇〜Ｙ₁₀，Ｙ₁₂は０、Ｙ₄，Ｙ₆，Ｙ
₁₁は１である。Ａ２は信号Ｙに対応する予測状態信号Ｚ
の時系列を示す。ＧはＧＯＯＤ、ＢはＢＡＤを示す。信
号Ｙ_iはこの予測状態Ｚ_iによって、それぞれＧＯＯＤ
かＢＡＤかのいずれかにラベル付けされる。すなわち、
図の例では、Ｙ₁，Ｙ₂，Ｙ₄，Ｙ₅，Ｙ₇，Ｙ₁₀，
Ｙ₁₁はＧＯＯＤ、Ｙ₃，Ｙ₆，Ｙ₈，Ｙ₉，Ｙ₁₂はＢＡ
Ｄである。

【００３９】Ａ３はメモリーに書き込んだ信号Ｙを示
す。メモリーの番地は左端から順に１，２，…１２番地
とする。そして書き込みにおいてはＧＯＯＤにラベル付
けされた信号Ｙを１番地から順に書き込み、ＢＡＤにラ
ベル付けされた信号Ｙを１２番地（１走査線の最終番
地）から逆向きに書き込む。このように書き込めば、メ
モリー内にＧＯＯＤとＢＡＤの信号Ｙをそれぞれ分離し
て書き込むことができる。図において、メモリーの１〜
７番地にはＧＯＯＤの信号Ｙ、８〜１２番地にはＢＡＤ
の信号Ｙが書き込まれている。

【００４０】次に、メモリー内の信号Ｙを読み出すが、
読み出した時系列信号を図７のＡ４に示す。まず、メモ
リー内の１番地からＧＯＯＤに対応するＹが１になるま
で順に読み出す。図の例では３番地に書き込まれたＹ₄
が、Ｙが０から１になるところなので、Ｙ₁，Ｙ₂，Ｙ
₄が読み出される。Ｙ＝１になると今度はメモリーの最
終番地からＢＡＤのＹをやはりＹ＝１になるまで読み出
す。図の例では１１番地のＹ₆がＹが０から１になると
ころなのでＹ₃とＹ₆が読み出される。次は再び、ＧＯ
ＯＤを読み出すので、Ｙ₅，Ｙ₇，Ｙ₁₀，Ｙ₁₁が読み出
され、Ｙ₁₁がＹが０から１になるところなので、次はＢ
ＡＤの（Ｙ₈，Ｙ₉，Ｙ₁₂）が読み出される。このよう
にして、配列変換が完了する。

【００４１】配列変換された信号Ｕは図７のＡ４に示さ
れているが、同図Ａ５にはこれを平滑化した信号Ｖを示
している。すなわち、信号Ｙが１になる毎に白黒を反転
させる処理が施されている。同図Ａ６には信号Ｖを白黒
別ランレングス符号化したときのランレングスを示して
いる。図において、Ｗ２，Ｗ４は白のランレングスが
２，４であることを表し、Ｂ２，Ｂ４は黒のランレング
スが２，４であることを表す。平滑化処理を施した信号
のランはＷ２，Ｂ２，Ｗ４，Ｂ４の４つである。これに
対して、平滑化処理をせずに信号Ｕ（図７のＡ４）を直
接ランレングス符号化したとすれば、ランはＷ２，Ｂ
１，Ｗ１，Ｂ１，Ｗ３，Ｂ１，Ｗ３の７つとなるので、
平滑化処理により大幅なラン数の削減が行われているこ
とが分かる。

【００４２】配列変換の規則は（１）同一ラベルをできるだけ連続させること（２）予測順位信号のビットが０から１になる毎にラベ
ルをできるだけ変化させることの２つの条件を満たすようにするのが、符号化能率の点
から得策である。勿論、配列逆変換により元に戻せるこ
とが前提条件であることは言うまでもない。

【００４３】ここで「できるだけ」という意味は「出来
ない場合は逆変換が可能な他の約束を用いる」ことを示
す。例えば図７に示した例で、信号ＹはＡ１で与えられ
た予測状態信号はＹ₁〜Ｙ₁₂に対してすべてＧＯＯＤで
あった場合を仮定しよう。そうすると、メモリには図７
のＢ３に示すようにＹ₁〜Ｙ₁₂の順に予測順位信号を構
成するビットが書き込まれる。この場合、すべてのデー
タはＧＯＯＤにラベル付けされているので、ＧＯＯＤに
次にＢＡＤを読み出すことはできない。メモリーの読み
出しを、前述の様にアドレスの昇順と降順にとり、Ｙ＝
１になる毎にこれらを切換えることにすれば、配列変換
後の信号Ｙは図７のＢ４に示すようになる。この配列変
換においてはＹ＝１になる毎にラベルが変化していない
が、配列逆変換は可能であるから、本発明では許され
る。

【００４４】図５に戻って配列変換回路の動作説明を行
う。図において、参照数字３０，３１はそれぞれ、昇順
アドレスカウンタ（アップカウンタ）および降順アドレ
スカウンタ（ダウンカウンタ）である。参照数字２９は
論理回路で、書き込み時には予測状態信号Ｚにより、Ｚ
＝０（ＧＯＯＤ）のときはアップカウントパルスを線１
２３に発生し、Ｚ＝１（ＢＡＤ）のときはダウンカウン
トパルスを線１２４に発生する。また、マルチプレクサ
ー３２の切換信号を線１２２に通して供給する。この切
換信号は書き込み時には予測状態信号Ｚそのものであ
る。

【００４５】アップカウンタ３０およびダウカウンタ３
１は走査線の始まりにおいてタイミングパルスにより、
それぞれ、１および１２がロードされ、以後はカウント
パルスにより、メモリーアドレスを１番地づつ増減させ
る。２つのアドレスカウンタにより指定されたアドレス
はマルチプレクサー３２で切換えられて線１２１を通し
てメモリー２８のアドレス線に供給される。このように
して、メモリー２８にはＧＯＯＤの信号Ｙが昇順に、Ｂ
ＡＤの信号Ｙが降順に書き込まれる。１走査線の書き込
みが終了すると、次の走査線の画像信号が到来する前に
メモリーの読み出しを行う。なお、次の走査線の画像信
号が連続して到来する場合は配列変換回路をダブルにし
て交互に動作させればよい。

【００４６】読み出しにおいては読み出した信号Ｕをフ
リップフロップ３３に供給し、Ｕ＝１になる毎にフリッ
プフロップを反転させる。フリップフロップの出力は線
１２５を通して理論回路２９に供給し、読み出し時のア
ップカウントパルス、ダウンカウントパルスおよびマル
チプレクサーの切換信号作成に用いられる。

【００４７】図６は図５に示した配列変換回路に対応す
る配列逆変換回路を示す。参照数字３４はメモリー、３
５は論理回路、３６はアップカウンタ、３７はダウンカ
ウンタ、３８はマルチプレクサ、３９はフリップフロッ
プで、これらは配列変換回路で用いたものと同じ機能で
同じ動作をする。ただし、書き込みと読み出しの動作が
配列逆変換回路とは逆になる。すなわち、配列変換され
た信号Ｕ’がまず、メモリー３４に書き込まれるが、書
き込みアドレスの制御はＵ’＝１になる毎に出力を反転
させるフリップフロップ３９の出力信号を用いて行な
う。また、読み出しアドレスの制御は予測逆変換回路か
ら供給される予測状態信号Ｚ’を用いて行う。これらの
アドレス制御の方法は配列変換回路と同じである。

【００４８】以上に配列変換とその逆変換動作を説明し
たが、配列変換の方法および回路はメモリー番地の昇順
・降順によるもの以外にもいろいろ考えられる。例えば
メモリーを２個用意し、ＧＯＯＤの信号Ｙを第１のメモ
リーに、ＢＡＤの信号Ｙをだい２のメモリーに順に格納
し、信号Ｙが１になる毎に読みだすメモリを交互に変え
ても良い。

【００４９】

【発明の効果】本発明の原理と効果を要約すれば次のよ
うになる。まず、本発明においては、画像信号を予測と
いう手段により画像信号の発生確率順位を示す予測順位
信号に変換するが、この変換によって、画像信号の冗長
度が削減される。冗長度が削減された画像信号、すなわ
ち予測順位信号をできるだけ少ないビット数の符号で表
すために、ランレングス符号化を用いる。

【００５０】ここで、ランレングス符号化の方法として
はＭＨ符号化の如く、平均ランレングスが比較的長い場
合に適合する白ラン用符号と平均ランレングスが比較的
短い場合に適合する黒ラン用符号の２種類のランレング
ス符号を用意し、白、黒、白、黒、…の如く用いるラン
レングス符号を交互に変化させる。

【００５１】本発明においては、この様なランレングス
符号化に適合するように前述の予測順位信号を２進数で
表現しその各ビットに変換を施す。変換には２種の手段
が含まれており、その第１は予測状態信号により予測順
位信号の各ビットが０になりやすいグループ（ＧＯＯ
Ｄ）と０になりにくいグループ（ＢＡＤ）の２つのグル
ープにラベル付けし、配列変換する手段である。この手
段により、ＧＯＯＤは平均ランレングスが比較的長いグ
ループ、ＢＡＤは平均ランレングスが比較的短いグルー
プに分離することができる。

【００５２】第２の手段は予測順位信号の各ビット１を
ランの区切りとして符号化する手段であり、具体的には
予測順位信号の各ビットが１になる毎に白黒を反転させ
る平滑化処理を施す。ＧＯＯＤとＢＡＤを予測順位信号
のビットが１になる毎に交互に読み出す配列変換と平滑
化処理により、ＧＯＯＤのランは白のランレングス符号
で、ＢＡＤのランは黒のランレングス符号で符号化され
る確率が高まり、圧縮率を高くすることができるのであ
る。

【００５３】本発明の特徴は変換処理を標準のＭＨ符号
器及び復号器の前後で施すことにより、ＭＨ符号化アル
ゴリズムを何ら変更せずに、多値画像の効率良いデータ
圧縮を可能ならしめることにあり、種々の目的に応用可
能である。

Claims

【特許請求の範囲】

【請求項１】多値画像信号の符号化において、既に符
号化済みの画像信号を用いて、現在符号化中の画像信号
の発生確率順位を予測し、現在符号化中の画像信号が何
番目の順位であるかを２進数で表現した予測順位信号を
発生し、前期予測順位信号の各ビットを予測状態により
ラベル付けし、ブロック毎に前記予測順位信号の各ビッ
トを、同一ラベルが連続しかつビットの値が所定値にな
る毎にラベルができるだけ変化するという規則により配
列変換し、配列変換した予測順位信号の各ビットに対し
てビットの値が所定値であるのをランの区切りとして、
第１および第２のランレングス符号を交互に用いてラン
レングス符号化し、画像信号の復号化においてランレン
グス復号化した予測順位信号の各ビットを定められた規
則に従って逆配列変換し、既に復号化済みの画像信号を
用いて現在復号化中の画像信号の発生確率順位を予測す
るとともに予測状態により予測順位信号の各ビットのラ
ベルを判定して予測順位信号を元の画像信号に復号する
ことを特徴とする多値画像信号の符号化復号化方法。
【請求項２】既に符号化済みの画像信号を用いて、現
在符号化中の画像信号の発生確率順位を予測し、現在符
号化中の画像信号が何番目の順位であるかを２進数で表
現した予測順位信号と予測順位信号の各ビットに対応す
る予測状態信号を発生する手段と、予測状態信号をラベ
ル付けしたとき、同一ラベルが連続しかつビットの値が
所定値になる毎にラベルができるだけ変化するという規
則により前記予測順位信号の各ビットをブロック毎に配
列変換する手段と、配列変換した予測順位信号の各ビッ
トに対してビットの値が所定値であるのをランの区切り
として、第１および第２のランレングス符号を交互に用
いてランレングス符号化する手段、とから構成されるこ
とを特徴とする多値画像信号の符号化装置。
【請求項３】ランレングス符号化された予測順位信号
の各ビットをランレングス復号化する手段と、ブロック
毎にランレングス復号化した予測順位信号の各ビットを
ランの区切りに応じて定められた規則に従って逆配列変
換する手段と、既に復号化済みの画像信号と既にラベル
が判定された予測順位信号のビットを用いて現在復号化
中の画像信号に対する予測順位信号の各ビットの予測状
態信号を発生する手段と、予測状態信号により予測順位
信号の各ビットのラベルを判定して予測順位信号のビッ
トが１画素分揃う毎に既に復号化済みの画像信号を用い
て予測順位信号を元の画像信号に復号化する手段とから
構成されることを特徴とする多値画像信号の復号化装
置。