JPH0548658B2 - - Google Patents

Description

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

〔従来の技術〕

デイジタル網フアクシミリ方式に於ける画像デ
ータの圧縮方式として、現在モデフアイド・リー
ド（Modified READ）方式（以下「MR方式」
と称する。）が標準方式の一つとして採用されて
いる。のMR方式は、符号化走査線とその直前の
参照走査線との２走査線を符号化の対象とし、符
号化走査線上の白画素から黒画素へ、又黒画素か
ら白画素へ変化する点（以下「変化点」と称す
る。）の位置を参照走査線上の同色調の変化点と
の相対距離（以下「ずれ」と称する。）、又は符号
化走査線上の反色調の直前変化点との相対距離
（以下「ランレングス」と称する。）で符号化する
方式である。

MR方式の変化点モードには、パス、垂直、水
平の三つのモードがあり、例えば、第９図のａに
示すように、参照走査線上の変化点b₁の黒画素か
ら次の変化点b₂の白画素までの間Ｐの黒画素は、
符号化走査線上の変化点a₀の白画素から次の変化
点a₁の黒画素の直前の白画素a₀′までの間の連続
した白画素により、符号化走査線上の黒画素とは
連続しないので、これをパス・モードとし、又ｂ
に示すように、参照走査線上の変化点b₁の黒画素
と次の変化点b₂の白画素との間の黒画素と、符号
化走査線上の変化点a₁の黒画素と次の変化点a₂の
白画素との間の黒画素とが連続している場合を垂
直モードとするものである。しかし、水平方向に
４画素以上のずれがある場合〔Ｖ（_{1 1}）≧４〕を
水平モードとするものである。

このような各モードに対応し且つ参照走査線上
の変化点b₁，b₂及び符号化走査線上の変化点a₀，
a₁，a₂のランレングスやずれ等の関係によつて、
第１０図に示すように、符号が割当てられるもの
である。

又水平モードに対しては、モデイフアイド・ハ
フマン（Modified Huffman）方式（以下「MH
方式」と称する。）により、０〜63のランレング
スをそれぞれ符号化したターミネーテイング符号
と、64の整数倍のランレングスをそれぞれ符号化
したメイクアツプ符号との組合せでランレングス
が表され、2560のランレングスまでのメイクアツ
プ符号が定められている。

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

〔発明が解決しようとする問題点〕

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

例えば、第１１図に示すように、横500×縦300
の長方形の図形の画像データをMR方式で符号化
した場合、横方向は黒ランレングスBRL500であ
るから、BRL52のターミネーテイング符号と、
BRL448のメイクアツプ符号との合計24ビツトに
なり、24/500の圧縮率となる。しかし、縦の境界
線は、総て垂直モードのＶ（０）で表すことにな
り、１ビツト構成であるが、、長方形の両側の境
界線はビツト・バイ・ビツト形式で符号化される
ことになり、圧縮効率が低い欠点があつた。

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

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

本発明の画像データ圧縮方式は、参照走査線と
符号化走査線とを対象として、前記符号化走査線
上にのみ二つの変化点が存在する開始モードと検
出する為の検出手段と、前記参照走査線上と前記
符号化走査線とに変化点が存在する継続モードを
検出する為の検出手段と、前記参照走査線上のみ
に変化点が存在する終了モードを検出する為の検
出手段とを備えて、開始モードの二つの変化点か
ら副走査方向につながるそれぞれの境界線を継続
モードで追跡して、終了モードまでを符号化する
ものである。

〔作用〕

縦方向に対してつながる長さを開始モードと終
了モードとの間の継続モードにより追跡して、縦
方向に継続する長さを符号化し、縦方向の相関を
利用してデータ圧縮率を向上させるものである。

〔実施例〕

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

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

第２図のａに示すように、符号化走査線上にの
み白画素から黒画素、黒画素から白画素への変化
点が存在する場合を開始モードとし、変化点a₀と
変化点a₁との間及びこの変化点a₁と次の変化点a₂
との間のランレングスが符号化の対象となる。従
つて、MR方式のように、ずれa₁b₁が４以上の場
合に水平モードとすると言うものではなく、参照
走査線上の黒画素と符号化走査線上の黒画素の間
のつながりが全くないことを示すことになる。

又第２図のｂに示すように、参照走査線上と符
号化走査線上とに変化点が存在し、境界線が縦に
つながつている状態を継続モードとし、符号化の
対象は、ずれa₁b₁であり、４以上でも必ずこのず
れa₁b₁を符号化する。

又第２図のｃに示すように、参照走査線上にの
み変化点b₁，b₂が存在する場合を終了モードとす
るものであり、これはMR方式のパスモードと同
じである。

第３図は前述の各モードに対応した符号の割当
てを示すものであり、符号化形式のＳ，Ｃ，Ｅは
開始モード符号、継続モード符号、終了モード符
号を示すものである。又（V₀×ｎ）は、縦方向
に継続モードが続く数ｎを符号化すること意味し
ており．V₀はMR方式の垂直モードのＶ（０）に
相当するものである。又C₀は第１０図に示すMR
符号のＶ（０）に対応し、C_R（１），C_R（２）は、
MR符号のV_R（１），V_R（２）に対応し、又C_L
（１），C_L（２）はV_L（１），V_L（２）に対応するも
のである。

符号化手順は、参照走査線と符号化走査線とを
対象として、変化点の開始モードを検出し、開始
モード符号Ｓの後に、二つのランレングス、例え
ば、第２図のａのa₀a₁間、a₁a₂間のランレングス
を符号化する。なお、基準変化点a₀の選択方法と
しては、次の２通りがある。(1)直前の開始モード
の第２変化点a₂を基準変化点とする。(2)直前の開
始モードの第２変化点a₂から現時点の開始モード
の第１変化点a₁までに通過した継続モードの変化
点の数に加えて、第１変化点a₁直前の継続モード
の変化点を基準変化点とする。但し、途中に継続
モードの変化点がない場合は、(1)と同じとする。
前述の(2)の方法が(1)の方法よりランレングスを短
くとることができるので、高圧縮率となるが、継
続モードの変化点数が加わる為に、MR符号適用
と言う面からは(1)の方法が好適である。

開始モードの検出が行われると、第１の変化点
a₁の境界線を縦に追跡し、継続モードで順次符号
化する。即ち、(i)ずれa₁b₁＝０の場合は、縦に継
続する数を表す符号に変換し、(ii)ずれa₁b₁＝１、
２の場合は、Ｃ（１），Ｃ（２）のモード符号に変
換し、(iii)ずれa₁b₁≧３の場合は、継続モード符号
とずれa₁b₁を表す符号に変換する。そして、終了
モードが検出された時点で、最後に終了モード符
号Ｅ化して変化点a₁の境界線追跡を終了する。

次に開始モードの第２変化点a₂の境界線追跡を
前述の第１変化点a₁の場合と同様にして継続モー
ドで符号化する。但し、この場合は最後に終了モ
ード符号Ｅを付加しない。これは、第１変化点₁
の境界線追跡終了を示す終了モード符号Ｅと、次
の開始モード符号との間に、第２変化点a₂の境界
線追跡情報が含まれる為に、終了モード符号Ｅを
付加しなくても、継続モードの最後が判る為であ
る。

次に開始モードを検出し、前述の手順を繰り返
して符号化を行う。

符号化走査線に開始モードの変化点が他になけ
れば、ライン終了信号（例えば、MR方式に於け
るEOL符号、又は前述の終了モード符号Ｅ）を
付加して、そのラインの処理を終了し、次のライ
ンの処理に移行する。

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

継続モード検出部６では、レジスタ４，５にセ
ツトされた変化点a₁，a₂の絶対アドレスに従つて
画像データメモリ１から縦方向に画像データを読
出して、変化点a₁，a₂につながる画像輪郭を追跡
し、カウンタ７によりずれ即ち第２図のｂに於け
るa₁b₁間のずれをカウントし、又カウンタ８によ
りずれが零で縦方向に連続する数即ち第２図のｂ
に於けるa₂b₂の状態が継続する回数をカウントす
る。

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

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

第４図は圧縮符号化されたデータの一例を示す
ものであり、開示モード符号Ｓの次に_{0 1}のラン
レングスRLと_{1 2}のランレングスRLとが付加さ
れて開始モードのデータとなり、次に変化点a₁，
b₁が縦方向にｎ個連続した場合で、継続モード符
号C₀とMH符号で表されたｎと、変化点のずれに
対応した符号C_R（１）、C_L（２）等により第１変化
点a₁のＣモードのデータとなり、終了モード符号
Ｅが付加され、次に第２変化点a₂の境界線追跡に
よるa₂のＣモードのデータとなる。ラインの終了
には前述のように、終了モード符号Ｅ或いはMR
符号に於けるEOL符号が付加される。

前述の第１１図に於ける図形の画像データの圧
縮に於いて、従来例のMR方式では、長方形の左
側の長さを100とすると、 Ｈ（W100、B500）＋２（V₀×299）＋Ｐ ＝３＋５＋８＋12＋12＋２×299＋４ ＝642（ビツト） となる。一方本発明の実施例の圧縮方式を適用
し、MR符号を用いた場合、 Ｓ（W100、B500）＋２（C₀＋B299）＋Ｅ ＝３＋５＋８＋12＋12＋２（１＋12＋12）＋４ ＝94（ビツト） となり、従来例に比較して大幅な圧縮が可能とな
る。これは、継続モードに於けるずれが零の縦方
向の数をランレングスで表して符号化することに
よるものである。

又図形のみでなく、文字の場合にも充分な画像
データの圧縮が可能となるものであり、例えば、
第５図に示す画素No.１〜42、ラインNo.１〜29の文
字「pi1」についての画像データを圧縮符号化す
ると、第６図に示すものとなり、ビツト数の合計
は252となつた。又第５図に於いて、〜は変
化点の境界線追跡径路を示し、第６図のモード欄
にこれらの〜を対応して示している。又第７
図は従来のMR方式により圧縮符号化した場合を
対応して示すものであり、ビツト数の合計は261
となつた。この例の場合は、本発明の実施例によ
る圧縮率は余り大きくないが、符号割当ての最適
化を図れば、圧縮率は更に向上するものである。

又境界線が複雑な場合、例えば、第８図に示す
場合、左上から右下へ画像がつながつていると定
義し、Ｓ，Ｃで示すように変化点を開始モード及
び継続モードとして処理することができる。又処
理の簡単化の為に、(1)全ラインの始端及び終端の
画素を白画素とする。(2)１頁の最終ラインを総て
白画素とする。このような定義により、MR方式
に於けるような仮想変化点処理をしなくても良い
ことになり、且つ最終ラインによる境界線終了検
出が容易となる。

〔発明の効果〕

以上説明したように、本発明は、参照走査線と
符号化走査線とを対象として、前記符号化走査線
上にのみ二つの変化点が存在する開始モードを検
出する為の開始モード検出部２等の手段と、前記
参照走査線上と前記符号化走査線上とに変化点が
存在する継続モードを検出する為の継続モード検
出部６等の手段と、前記参照走査線上のみに変化
点が存在する終了モードを検出する為の終了モー
ド検出部９等の手段とを備え、開始モードを検出
することにより、その開始モードの二つの変化点
から副走査方向につながるそれぞれ境界線を継続
モードで追跡して、終了モードが検出されるまで
を符号化するものであり、縦方向の相関を充分に
利用してデータ圧縮することができる利点があ
る。

【図面の簡単な説明】

第１図は本発明の実施例のブロツク図、第２図
は本発明の実施例のモード説明図、第３図は各モ
ードと符号割当ての説明図、第４図は圧縮符号の
一例の説明図、第５図は文字の一例の説明図、第
６図は第５図の画像のデータを本発明の実施例に
より圧縮処理した場合の説明図、第７図は第５図
の画像のデータをMR方式で圧縮処理した場合の
説明図、第８図は境界線が複雑な場合の継続、切
断の定義の説明図、第９図はMR方式のパス、垂
直及び水平モードの説明図、第１０図はMR方式
の符号割当ての説明図、第１１図は長方形図形の
一例を示すものである。 １は１頁分の容量の画像データメモリ、２は開
始モード検出部、３，７，８はカウンタ、４，５
はレジスタ、６は継続モード検出部、９は終了モ
ード検出部、１０はマルチプレクサ、１１は符号
変換メモリ、１２はシフトレジスタ、１３はカウ
ンタである。

Claims (1)

【特許請求の範囲】
1. １ 二次元符号化により画像データを圧縮する画
   像データ圧縮方式に於いて、参照走査線と符号化
   走査線とを対象として、前記符号化走査線上にの
   み二つの変化点が存在する開始モードの検出手段
   と、前記参照走査線上と前記符号化走査線上とに
   変化点が存在する継続モードの検出手段と、前記
   参照走査線上のみに変化点が存在する終了モード
   の検出手段とを備え、前記開始モードの二つの変
   化点から副走査方向につながるそれぞれの境界線
   を継続モードで追跡して、終了モードまでを符号
   化することを特徴とする画像データ圧縮方式。