JPS61123284A - 画像デ−タ圧縮方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、二次元符号化により画像データを圧縮して、
高速ファクシミリ伝送を行わせる為の画像データ圧縮方
式に関するものである。

〔従来の技術〕

ディジタル網ファクシミリ方式に於ける画像データの圧
縮方式として、現在モデファイト・リード（Ｍｏｄｉｆ
ｉｅｄ　ＲＥＡＤ）方式（以下ｒＭＲＭＲ方式称する。

）が標準方式の一つとして採用されている。このＭＲ方
式は、符号化走査線とその直前の参照走査線との２走査
線を符号化の対象とし、符号化走査線上の白画素から黒
画素へ、又は黒画素から白画素へ変化する点（以下「変
化点」と称する。）の位置を参照走査線上の同色調の変
化点との相対距離（以下「ずれ」と称する。）、又は符
号化走査線上の反色調の直前変化点との相対距離（以下
「ランレングス」と称する。）で符号化する方式である
。

ＭＲ方式の変化点モードには、バス、ｉＨＥ、　水平の
三つのモードがあり、例えば、第１１図の（ａ）に示す
ように、参照走査線上の変化点す、の黒画素から次の変
化点ｂ２の白画素までの間Ｐの黒画素は、符号化走査線
上の変化点ａ。の白画素から次の変化点ａ１の黒画素の
直前の白画素ａ　ｏ＋までの間の連続した白画素により
、符号化走査線上の黒画素とは連続しないので、これを
パス・モードとし、又第１１図の中）に示すように、参
照走査線上の変化点ｂＩの黒画素と次の変化点ｂ２の白
画素との間の黒画素と、符号化走査線上の変化点ａ１の
黒画素と次の変化点ａ２の白画素との間の黒画素とが連
続している場合を垂直モードとするものである。しかし
、水平方向に４画素以上のずれがある場合（Ｖ　（ＴＴ
ｖ下）≧４〕は水平モードとするものである。

このような各モードに対応し且つ参照走査線上の変化点
す、、ｂ２及び符号化走査線上の変化点ａ（１，ａＩ、
ａｚのランレングス（ＲＬ）やずれ（Ｚ　Ｌ）等の関係
によって、第１２図に示すように、符号が割当てられる
ものである。

又水平モードに対しては、モディファイド・ハフマン（
Ｍｏｄｉｆｉｅｄ　Ｈｕｆｆｍａｎ）方式（以下ｒＭＨ
方式」と称する。）により、θ〜６３のランレングス（
ＲＬ）をそれぞれ符号化したターミネーティング符号と
、６４の整数倍のランレングス（ＲＬ）をそれぞれ符号
化したメイクアップ符号との組合せでランレングスが表
され、メイクアップ符号としては２５６０のランレング
スまで定められるでいる。

又第１２図に於ける水平モードのＭＲ符号中のＭＨは、
ターミネーティング符号とメイクアップ符号との組合せ
で符号化されたＭＨ符号を示すものであり、又通常の画
像データに於いては、その中の変化点の５０％が垂直モ
ードのＶ　（０）で表現することができ、又３０％が垂
直モードのｖ、Ｉ（ｔ）、ＶＬ　　（ｔ）で表現するこ
とができるから、これらに対して符号長１又は３の短い
符号を割当てて、高圧縮率を得ているものである。

〔発明が解決しようとする問題点３ 画像データは、一般的に横の相関だけでなく、縦の相関
も大きい場合が多いものである。即ち、画像の境界線を
見ると、横だけでなく縦にもつながっていると考えられ
る。従って、前述のＭＲ方式に於いては、参照走査線と
符号化走査線との２走査線だけを対象として符号化を行
うものであるから、縦の相関を充分に利用しているもの
ではないことになる。

例えば、第１３図に示すように、Ａ４判原稿（横１７２
８ｘ縦２３８４画素）の左端より画素数で３００の位置
に横５００×縦３００の画素数の長方形の図形が描かれ
、そのＡ４判画像データをＭＲ方式で符号化した場合、
横方向は白ランレングスＷＲＬ３００．黒ランレングス
ＢＲＬ５００であるから、次のように符号化される。

Ｈ（Ｗ２Ｏ３，８５００）＋２　Ｘ（ｖ（０）　Ｘ２９
９）＋Ｐ＋　２３８４　Ｘ　Ｖ　（０） ＝３＋１５＋２４＋２Ｘ２９９＋４＋２３８４−３０２
８　　（ビット） 即ち、水平モード符号Ｈの３ビツトと、白ランレングス
Ｗ３００をＷＲＬ４４のターミネーティング符号と、Ｗ
ＲＬ２５°６のメイクアップ符号とで表した１５ビツト
と、黒ランレングスＢ５００をＢＲＬ５２のターミネー
ティング符号と、ＢＲＬ４４８のメイクアップ符号とで
表した２４ビツトと、垂直モード符号Ｖ（０）が縦方向
に２９９連続し且つ両側であることによる５９８ビツト
と、バス・モード符゛号Ｐの４ビツトと、仮想変化点を
示す２３８４ビツトとの合計３０２８ビツトとなる。こ
のように、長方形の両側の縦方向の境界線は、変化点の
ずれ０の垂直モードにより符号化されるが、ビット・バ
４・ビット形式で符号化されることになるから、画像デ
ータの圧縮率が低い欠点があった。

本発明は、前述の従来の欠点を改善し、縦方向について
も符号化して、圧縮率を向上することを目的とするもの
である。

〔問題点を解決するための手段〕

本発明の画像データ圧縮方式は、参照走査線と符号化走
査線とを対象として、前記符号化走査線上にのみ白から
黒又は黒から白へ変化する変化点が二つ存在する開始モ
ードの検出手段と、前記参照走査線上と前記符号化走査
線上とに変化点が存在する継続モードの検出手段と、前
記参照走査線上のみに変化点が存在する終了モードの検
出手段とを備えて、開始モードに於けるそれまでの通過
境界線数と二つのランレングスを符号化し、且つ開始モ
ードの二つの変化点から副走査方向につながるそれぞれ
の境界線を継続モードのずれ（ＺＬ）のＯの継続数又は
ずれ（ＺＬ）の大きさを、終了モードまで符号化するも
のである。

〔作用〕

開始モードが検出された時の符号化走査線上のみに存在
する二つの変化点を、通過境界線数と二・　つのランレ
ングスを符号化し、それらの変化点につながる境界線を
縦方向に続く長さ及び横方向のずれの長さを符号化し、
縦方向の相関を利用することにより、高圧縮率を得るも
のである。

〔実施例〕

以下図面を参照して、本発明の実施例について詳細に説
明する。

第１図は本発明の実施例のブロック図であり、■は画像
データメモリ、２は開始モード検出部、３．７．８．１
４はカウンタ、４．５はレジスタ、６は継続モード検出
部、９は終了モード検出部、１０はマルチプレクサ、１
１は符号とその符号長情報とを出力する符号変換メモリ
、１２はシフトレジスタ、１３は符号長カウンタである
。画像データは画像データメモリｌに加えられて、１頁
分が一旦蓄積され、その画像データメモリ１から開始モ
ード検出部２．継続モード検出部６及び終了モード検出
部９にそれぞれ参照走査線と符号化走査線との２走査線
上の画像データが加えられて、それぞれ開始モード、継
続モード及び終了モードの検出が行われる。

第２図の（ａｌに示すように、符号化走査線上にのみ白
画素から黒画素、黒画素から白画素への変化点ａｌｌ＋
ａｌ＋１２が存在する場合を開始モードとし、同じ走査
線上の直前の開始モードから現時点までの境界線の数と
、二つのランレングス（ＲＬ）即ち、（ａｏ　ａ　＋）
　＋　　（ａ　ｔ　ａ　Ｚ）が符号化の対象となる。

又第２図の伽）に示すように、参照走査線上と符号化走
査線上とに変化点ｂＩ、ｂ２．ａｌ、ａ２が存在し、境
界線が縦につながっている状態を継続モードとし、符号
化の対象は、ずれａＩｂｌであり、そのずれ（ＺＬ）が
４以上でも必ず符号化するものである。

又第２図の（Ｃ１に示すように、参照走査線上にのみ変
化点す、、ｂｚが存在する状態を終了モードとするもの
であり、ＭＲ方式に於けるパス・モードと同じである。

従って、従来のＭＲ方式と比較すると、通過した境界線
の数を符号化する点と、ずれ（Ｚ　Ｌ）が４以上であっ
ても、そのずれ（Ｚ　Ｌ）を符号化する点とが相違する
ものとなる。

第３図は前述の各モードに対応した符号対象要素、符号
化形式５符号適用を示すものであり、開始モードに於い
ては、通過境界線数ｍと二つのランレングスａｏａＩ、
ａ１ａ、２とを符号化して、開始モード符号Ｓを付加す
るもの″であり、開始モード符号Ｓは“Ｏｌ”、通過境
界線数の符号ＢＬ（ｍ）は第４図に示すものを用い、ラ
ンレングス（ＲＬ）は、ＭＨ符号を用いるものである。

又終了モードに於いては、終了モード符号Ｅを付加する
ものであり、この終了モード符号Ｅは開始モード符号Ｓ
と同じ＠０１“を用いる。

又継続モードに於いては、ａ１丁Ｔ−〇即ちずれ（ＺＬ
）が零で縦方向に連続した変化点の数ｎを符号化するも
ので、この継続モード符号Ｃ，を１１”とし、数ｎの符
号ＶＬ　（ｎ）は第５図に示すものを用いるものである
。又継続モードに於いて、参照走査線上の変化点す、に
対して符号化走査線上の変化点ａ１が右側にずれるか左
側にずれるかにより、符号Ｃ１，ＣＬが割当てられ、ず
れ（ＺＬ）が３以下の場合に、３〜５ビツトの符号が割
当てられる。又ずれ（ＺＬ）が４以上の場合には、それ
を示す継続モード符号Ｃ１ｔ、ＣＬの後にずれ（ＺＬ）
の大きさを表す第６図に示す符号ＺＬが付加されるもの
である。

符号化手順は、（１）参照走査線と符号化走査線とを対
象として、変化点の開始モードを検出し、開始モード符
号Ｓの後に、通過した境界線の数及び二つのランレング
スａＯａｌ＋　　”Ｉａ２を符号化して付加する。

（２）開始モードの検出が行われると、第１の変化点ａ
、の境界線を縦方向に追跡し、継続モードで順次符号化
する。即ち、（ｉ）ずれａｌｂ１＝Ｑの場合、ｃ、＋Ｖ
Ｌ　（ｎ）、（ｉｉ　）ずれａ１ｂｌ＝１．２．３の場
合は、ＣＲ，ＣＬ　　（１〜３）、（ｉｉｉ　）ずれａ
ｌｂ、＞３の場合、ＣＩ、ＣＬ＋ＺＬ（丁Ｔ丁下）によ
る符号化を行い、終了モードが現れた時点で終了モード
符号Ｅを付加して、第１変化点ａ、の境界線符号化を終
了する。なお、終了モード符号Ｅと開始モード符号Ｓと
は同じものを用いているが、開始モード符号Ｓと終了モ
ード符号Ｅとは、常に対となって用いられるから、１回
目が開始モード符号Ｓで、２回目が終了モード符号Ｅと
判断できる為である。

（３）次に開始モードの第２変化点ａ２の境界線を追跡
し、継続モードで符号化する。但し、この場合は、最後
に終了モード符号Ｅを付加しないものである。以上の処
理で１組の境界線符号化を終了する。

（４）次に開始モードを検出し、前述の＋１１〜（３）
の手順で符号化を行う。

（５）ライン終了を示す為に、最初にライン上に仮想変
化点の位置に黒Ｏのランレングス（ＲＬ）を持つ境界線
が原稿の端まで縦につながっているとして符号化してお
き、次のライン以降にこの仮想境界線を通り過ぎる毎に
境界線を１本通り過ぎたとしてカウントアツプする。

第１３図に示す図形について、前述の符号化手順を適用
して符号化すると次のようになる。

Ｓ　（０，Ｗ１７２Ｂ、　ＢＯ）　＋　Ｅ　＋　Ｓ　（
３９９、Ｗ２Ｏ３゜Ｂ５００）　＋　Ｃｏ　（２９９）
　＋　Ｅ　＋　Ｃ６（２９９）＝２＋２＋１７＋９＋２
＋２＋２１＋１５＋２４＋２＋２２＋２＋２＋２２ −１４４　　（ビット） 前述のＭＲ方式と比較すると、約５／１００以下のビッ
ト数となるように圧縮されることになり、大幅な圧縮率
の向上を図ることができる。

前述の手順の符号化を行う為に、第１図に於ける開始モ
ード検出部２では、前述のように、参照走査線と符号化
走査線との２走査線の画像データを読出して、第２図の
（ａ）に示す状態の画像データであるか否か識別し、開
始モードである場合は、カウンタ３によりａｌ）１１間
及び３１３２間の二つのランレングスをカウントし、白
画素から黒画素への第１変化点ａｌの絶対アドレスをレ
ジスタ４にラッチし、黒画素から白画素への第２変化点
ａ２の絶対アドレスをレジスタ５にラッチする。

又開始モード検出の際に通り過ぎた境界線数をカウンタ
１４によりカウントする。

継続モード検出部６では、レジスタ４．５にセットされ
た変化点ａｌ、ａ２の絶対アドレスに従って画像データ
メモリ１から縦方向に画像データを読出して、変化点ａ
Ｉ＋８２につながる画像輪郭を追跡し、カランタフによ
りずれ（ＺＬ）、即ち第２図の（ｂｌに於けるａＩｂ１
間のずれ（Ｚ　Ｌ）をカウントし、又カウンタ８により
ずれ（ＺＬ）が零で縦方向に連続する数、即ち、第２図
の（ｂ）に於ける第２変化点ａ２ｂ２の状態がｍ続する
回数をカウントする。

又終了モード検出部９では、継続モード検出動作に於い
て第２図の（Ｃ）に示す状態の画像データであるか否か
識別する。

マルチプレクサｌＯは符号手順に従ってカウンタ３．７
，８．１４及び終了モード検出部９−の検出信号を切換
えて符号変換メモリ１１に加えるもので、符号変換メモ
リ１１はリードオンリメモリにより構成され、第３図に
示す符号適用欄の符号データ及びその符号長が読出され
るものであり、その符号データをシフトレジスタ１２に
セットし、符号長をカウンタ１３にセットし、符号長に
従ったビット数をシフトレジスタ１２から圧縮データと
して送出する。

第７図は前述の実施例により圧縮符号化された符号系列
の一例を示すものであり、１組目の境界線符号化に於い
ては、開始モード符号Ｓの次に通過境界線数０の場合を
示す符号ＢＬ　（０）　、変化点間の白ランレングス４
の場合を示す符号ＭＨ（Ｗ４）、次の変化点間の黒ラン
レグス３の場合を示す符号ＭＨ（Ｂ３）が付加される。

次に第１変化点ａｌの境界線の追跡が行われて符号化さ
れるものであり、継続モード符号ｃｏの次にずれ（Ｚ　
Ｌ）零の回数５の場合を示す符号ＶＬ（５）が付加され
、又ずれ（ＺＬ）が２及び１の場合を示す符号Ｃｍ　　
（２）、Ｃ１１（１）が付加され、終了モードが検出さ
れると、終了モード符号Ｅが付加されて、第１変化点ａ
ｌの境界線追跡が終了する。

次に、第２変化点ａ２の境界線の追跡が行われて継続モ
ードで符号化されるものであり、ずれ（ＺＬ）が１及び
２の場合を示す符号ＣＩ（１）。

ＣＲ（２）が付加されて、１組目の境界線の符号化が終
了する。

以下同様にして２組目の境界線の符号化が行われるもの
である。

本発明に於いては、図形のみでなく、文字の場合につい
ても画像データの大幅な圧縮が可能となるものであり、
第８図に示すように、横方向の画素１〜４８、縦方向を
ライン魔１〜３０で示す中のｒｓａｌＪの画像データを
圧縮符号化すると、第９図に示すものとなった。この第
９図に於ける■〜［相］は、第８図に於ける境界線追跡
径路■〜［株］に対応するものであり、最初の開始モー
ドは、ライン隨４に於いて画素番号３６が第１の変化点
となり、画素番号４２が第２の変化点となる。そして、
モード欄に示すモード符号が割当てられ、符号欄に示す
符号に変換されるものである。この場合は、ビット数の
合計は３９１となった。これに対して、従来のＭＲ方式
により圧縮符号化した場合、第１０図に示すものとなっ
た。そしてビット数の合計は４０６となった。この場合
、境界線の凹凸が比較的激しく、圧縮率の向上は僅かで
あるが、符号割当ての最適化を行うことにより、更に圧
縮率の向上を図ることが可能である。

〔発明の効果〕

以上説明したように、本発明は、参照走査線と符号化走
査線とを対象として、符号化走査線上のみ二つの変化点
が存在することを検出する開始モード検出部２等の検出
手段と、参照走査線上と符号化走査線上とに変化点が存
在することを検出する″ｍｍ上モード検出６等の検出手
段と、参照走査線上のみに変化点が存在することを検出
する終了モード検出部９等の検出手段とを備えて、開始
モードに於けるそれまでの通過境界線の数と二つのラン
レングスの符号化を行い且つ開始モードに於ける二つの
変化点から副走査方向につながるそれぞれの境界線を継
続モードのずれが０の継続数又はずれの大きさを終了モ
ードまで符号化するものであり、縦方向に連続する画像
についても、短い符号で表現できるので、ＭＲ方式より
も更にデータ圧縮が可能となる利点がある。

【図面の簡単な説明】

第１図は本発明の実施例のブロック図、第２図は本発明
の実施例のモード説明図、第３図は各モードと符号割当
ての説明図、第４図は通過境界線数と割当符号との説明
図、第５図はずれ０の縦方向の継続数と割当符号との説
明図、第６図はずれと割当符号との説明図、第７図は圧
縮符号列の一例の説明図、第８図は文字画像の説明図、
第９図は本発明の実施例により第８図の文字画像データ
を圧縮符号化した場合の説明図、第１０図は従来のＭＲ
方式により第８図の文字画像データを圧縮符号化した場
合の説明図、第１１図はＭＲ方式の図形画像の説明図で
ある。 １は１頁分の容量の画像データメモリ、２は開始モード
検出部、３．７．８はカウンタ、４，５はレジスタ、６
は継続モード検出部、９は終了モード検出部、１０はマ
ルチプレクサ、１１は符号変換メモリ、１２はシフトレ
ジスタ、１３．１４はカウンタである。

Claims (1)

【特許請求の範囲】
1. 二次元符号化により画像データを圧縮する画像データ圧
   縮方式に於いて、参照走査線と符号化走査線とを対象と
   して、前記符号化走査線上にのみ二つの変化点が存在す
   る開始モードの検出手段と、前記参照走査線上と前記符
   号化走査線上とに変化点が存在する継続モードの検出手
   段と、前記参照走査線上のみに変化点が存在する終了モ
   ードの検出手段とを備え、前記開始モードに於けるそれ
   までの通過境界線数と二つのランレングスで符号化し且
   つ開始モードに於ける二つの変化点から副走査方向につ
   ながるそれぞれの境界線を継続モードのずれが零の継続
   数又はずれの大きさを符号化し、該符号化を終了モード
   まで行うことを特徴とする画像データ圧縮方式。