JPS6360954B2 - - Google Patents

Description

【発明の詳細な説明】 (1) 発明の属する分野の説明 本発明は、２次元の２値パターンをランレング
ス符号化する２値パターン符号化処処理方式に関
するものである。

(2) 従来の技術の説明 従来第１図のような２次元の２値パターンを符
号化するには、２値パターンの水平方向のランレ
ングス（ラン長）を情報源として、モデイフアイ
ド・ハフマン（MH）符号化やリード符号化、ワ
イル符号化方法等を用いていた。第１図の１１１
は垂直方向の第１番目のライン（第１ライン）第
１の（白）ラン（ここで２値パターンの水平方向
の最初のランは白ランから始まるものとする）、
１１２はラン１１１の次の（黒）ラン、１１３〜
１１４はラン１１２に続くラン、１２１は第２ラ
インのラン（このように１ラインすべて白画素
（白ドツト）のランを白ラインと呼ぶ）、１３１〜
１３３は第３ラインのランである。第２図に第１
図の２次元の２値パターンをワイル符号化（符号
表はＨ・Wyle、et al：Reduced―Time
Facsimile Transmission by Digital Coding、
IRE Trans、Val、CS―９、No.３、1961を参照）
した符号列を示す。２１１〜２１４はそれぞれラ
ン１１１〜１１４の符号、２２１はラン１２１の
符号、２３１〜２３３はそれぞれラン１３１〜１
３３の符号である。

上述の例のようにラン長は白あるいは黒画素の
連続する個数で表現され、前記従来の符号化手法
もこの画素列で表現したラン長をもとに符号テー
ブルを作成し、符号化および復号化処理により、
２値パターンの記憶あるいは伝送を行つてきた。

しかし２値パターンの入出力装置（例えばフア
クシミリ、ラスタスキヤン形CRT等）は走査線
方向と副走査線方向（あるいは水平方向と垂直方
向）の画素数あるいは線密度が異なるため、前記
符号化手法により符号化した２値パターンを線密
度の異なる装置に出力すると水平および垂直方向
の大きさが違つてしまうという欠点があつた。こ
の点を改良するため線密度変換（例えば午坊、桐
原：フアクシミリ線密度変換方式、画像電子学
会、全大予稿―10、1975等）を用いて、２値パタ
ーンの大きさを整合させたり、拡大あるいは縮小
する方式が提案されている。しかしある一定の線
密度をもつ装置相互間の変換を行うため、装置の
線密度をあらかじめ知つておく必要があり、多種
類の入出力装置で入出力する２値パターンの相互
変換を行うためには、あらかじめ変換を行う装置
間で各々の線密度に関してネゴシエイシヨンする
必要があり、変換のアルゴリズムを複数種類用意
する必要があつた。

(3) 発明の目的 本発明はこれらの欠点を解決するため、２値パ
ターンの水平方向のランレングス（ランの長さ）
を０BX＜１の２進数で規格化して、該２進数
BXを符号化すると共に、垂直方向における（水
平方向の）ランの位置を０BY＜１あるいは０
△BY＜１なる２進数BYあるいは△BYで表現
して符号化することを特徴とし、その目的は２次
元の２値パターンの情報を圧縮し、かつ入出力装
置の入出力精度（例えばフアクシミリの主走査方
向、副走査方向の線密度等）に依存しない形で、
２次元の２値パターンの情報を表現することにあ
る。

(4) 発明の構成および作用の説明 第３図は第１図の２次元２値パターンの水平方
向のランの長さおよび該ランの垂直方向の位置を
規格化する方法を示している。３１０，３２０，
３３０はそれぞれ第１図のラインの垂直方向の位
置である第１ライン、第２ライン、第３ラインを
規格化した10進の分数（フラクシヨン）表現であ
る。連続する水平方向の１つ以上のランがライン
を構成するため、ラインの垂直方向の位置は、水
平方向のランの垂直方向の位置を示す。３１１〜
３１４は分数表現で規格化した垂直方向の位置３
１０のそれぞれラン１１１〜１１４（第１図参
照）を規格化した分数表現のラン長を、３２１は
規格化した分数表現の垂直方向の位置３２０のラ
ン１２１（第１図参照）を規格化した分数表現の
ラン長を、３３１〜３３３は分数表現で規格化し
た垂直方向の位置３３０において、それぞれラン
１３１〜１３３（第１図参照）を規格化した分数
表現のラン長を示す。

ここで規格化の定義を述べる。入力（あるいは
出力）装置で表現可能な水平方向、垂直方向の最
大の画素数をそれぞれNmax、Mmaxとし、２値
パターンの水平方向、垂直方向の画素数をそれぞ
れＮ（Nmax）、Ｍ（Mmax）とし、白あるい
は黒画素の任意のランの長さをＲ（ＲＮ）、該ラ
ンの垂直方向の位置（該ランを含むラインの位
置）をＬ（ＬＭ）とすると、（Ｒ−１）／Ｎが規
格化した水平方向の該ランのラン長の10進の分数
表現、（Ｌ−１）／Ｍが規格化した該ランの垂直
方向の位置の10進分数表現である。したがつて第
１図の例ではＮ＝248、Ｍ＝204であるから、垂直
方向の位置３１０は０／204、ラン長３１１〜３
１４はそれぞれ34／248、109／248、29／248、
72／248の10進分数表現で規格化される。

次に２進数による規格化表現について述べる。
規格化した分数表現のラン長R′／Ｎ（R′△ ＝Ｒ−
１、「△ ＝」は定義を示す。ラン長が１のときR′＝
０ラン長がＮのときR′＝Ｎ−１となる）以下の
ように２進数の規格化した表現BXに変換され
る。

R′／Ｎ＝b₁2^-1＋b₂2^-2＋…＋b_lx2^-lx＋… (1) BX0.b₁b₂…b_lx (2) ここでは等しいあるいはほぼ等しいことを示
す。２進数BXは任意のビツト数lx有効とし、bi
（ｉ＞lx）はすべて０とする。なおlxをlx
log₂Nとなる最小の整数とすれば２値パターンの
情報報を失うことなく、最小のビツト数で水平方
向の精度を保つことができる。

規格化した分数表現のランの垂直方向の位置
L′／Ｍ（L′△ ＝Ｌ−１）もR′／Ｎと同様に以下のよ
うに規格化した２進数の表現BYに変換される。

L′／Ｍ＝b₁2^-1＋b₂2^-2＋…b_ly2^-ly＋… (3) BY0.b₁b₂…b_ly (4) ここで２進数BYは任意のビツト数lyまで有効
とし、bi（ｉ＞ly）はすべて０とする。なおlxと
同様、lyをlylog₂Mとなる最小の整数とすれ
ば、最小のビツト数で２値パターンの垂直方向の
精度を保つことができる。(3)式のL′は各ラインの
絶対位置（例えば何番目のラインなど）を表わす
が、後述のようにラインの相対的な位置（相対位
置）で垂直方向のランの位置を表わすこともでき
る。垂直方向の位置L₀を入力（あるいは出力）
した後、垂直方向の位置L₁を入力（あるいは出
力）したとすると、絶対位置L₁の相対位置△Ｌ
を△Ｌ△ ＝L₁−L₀とする。ここで２値パターンの
第１ラインから入力（あるいは出力）するときは
△Ｌ＝０とする。この△Ｌについても、規格化し
た分数表現のランの垂直方向の相対位置△Ｌ／Ｍ
を定義し、以下のように規格化した２進数の表現
△BYに変換される。

△Ｌ／Ｍ＝b₁2^-1＋b₂2^-2＋…b_l△_y2^-l△^y＋… (5) △BY0.b₁b₂…b_l△_y (6) ここで２進数△BYは任意のビツト数ｌ△ｙま
で有効とし、bi（ｉ＞ｌ△ｙ）はすべて０とする。
なおly同様、ｌ△ｙをｌ△ｙlog₂Nとなる最小
の整数とすれば最小のビツト数で２値パターンの
垂直方向の精度を保つことができる。

以下特に断わらない限り、BX、BY、△BYを
それぞれ、水平方向のランの長さを規格化した２
進数表現、垂直方向のランの絶対位置を規格化し
た２進数表現、垂直方向のランの相対位置を規格
化した２進数表現（BYに垂直方向の絶対／相対
位置の両方の性質をもつとしてもよいが説明上
BYが絶対位置、△BYが相対位置を表わすとし
て述べる）とする。

本発明では、BXとBY（あるいはBXと△BY）
を情報源として以下に示す例のような符号化を行
う。

第４図は２進数BXの符号化例である。BXの
ビツト列b₁……b₁₅に対応する符号列c₁……c₁₅を、
ci＝b_11-i（１ｉ10）、ci＝bi（ｉ11）として、
cj（ｊ＞ｋ、ｋはck＋１＝１となる最大の整数）
をすべてサプレスして構成する。符号列c₁……ck
のヘツダとして、ｋ＋１を２進数化する。ここで
ci＝０（ｉ１）のときはヘツダは０（２進）であ
り、c₁＝１ ci＝０（ｉ２）のときはヘツダは
１（２進）であり、相方とも符号列c₁……ckはす
べてサプレスされる。なお図中Ｘは１または０を
示す（以下同様）。

第５図は２進数BYおよび△BYの符号化例で
ある。BYおよび△BYのビツト列b₁……b₁₅に対
応する符号列c₁……c₁₅を、ci＝b_9-i（１ｉ
８）、ci＝bi（ｉ９）として、cj（ｊ＞ｋ、ｋは
ck＋１＝１となる最大の整数）をすべてサプレ
スして構成する。符号列c₁……ckのヘツダとし
て、ｋ＋１を２進数化する。ここでci＝０（ｉ
１）のときはヘツダは０（２進）であり、c₁＝１、
ci＝０（ｉ２）のときはヘツダは１（２進）であ
り、相方とも符号列c₁……ckはすべてサプレスさ
れる。

第６図はラン長Ｒと第４図による符号例（lx＝
10）の対応、第７図は垂直方向のランの絶対位置
（絶対ライン位置）Ｌおよび相対位置（相対ライ
ン位置）△Ｌと第５図による符号化例の対応を示
す。なお相対ライン位置とは絶対ライン位置L₁
と次に符号化する絶対ライン位置L₂との差△Ｌ
＝L₂−L₁を表わす。第８図ａは第６図および第
７図（絶対ライン位置）により、第１図の２値パ
ターンを符号化した符号列である。第８図ｂは第
６図および第７図（相対ライン位置）により、第
１図の２値パターンを符号化した符号列である。
８１０ａは垂直方向の絶対位置３１０の符号化
例、８１１〜８１４はそれぞれラン長３１１〜３
１４の符号化例、８３０ａは垂直方向の絶対位置
３３０の符号化例、８３１〜８３３はそれぞれラ
ン長３３１〜３３３の符号化例、８４０ａは第３
図の203／204ラインの符号化例である。８１０ｂは第 １ラインの垂直方向の相対位置（この場合△Ｌ＝
０）の符号化例、８３０ｂは第３ラインの垂直方
向の相対位置（△Ｌ＝２）の符号化例、８４０ｂ
は第204ラインの垂直方向の相対位置（この場合
仮に△Ｌ＝１とした）である。第８図の符号化例
では、白ライン（例えば第１図の第２ライン）を
符号化しない。したがつて第８図ａでは第１ライ
ンの次が第３ラインの符号列になり、第８図ｂで
は相対位置８３０ｂが第２ラインをスキツプする
ため、第１ラインからの相対位置は△Ｌ＝２を表
わす。

第９図は本発明の一構成例であり、９０１は第
１図に示される２次元の２値パターンを記憶する
ためのメモリ、９０２は２値パターンの水平方向
の画素数Ｎ（第１図ではＮ＝248）を記憶するため
のメモリ、９０３は２値パターンの垂直方向の画
素数（すなわちライン数）Ｍ（第１図ではＭ＝
204）を記憶するためのメモリ、９０４は２次元
の２値パターンの１ライン分の２値パターンを記
憶するためのラインバツフア、９０５はメモリ９
０１とラインバツフア９０４の読み出し／書き込
み制御を行うメモリ制御部、９０６はラインバツ
フア９０４内の２値パターンのランの長さＲを抽
出するラン長抽出部、９０７はラン長ＲとＮか
ら、（Ｒ−１）／Ｎの２進数BXを求めるラン長
変換部、９０８は２進数BXを第４図および第６
図に示した方法により符号化する符号化部、９０
９はラインバツフア９０４内の２値パターンが白
ラインである場合、および１ラインのすべてのラ
ンを抽出した場合を、メモリ９０２とラン長抽出
部９０６からの出力により検出し、メモリ制御部
９０５への制御信号を出力するとともに、ライン
の位置Ｌ（あるいは△Ｌ）を出力するライン検出
部、９１０はライン検出部９０９とメモリ９０３
内の２値パターンのライン数Ｍから、（Ｌ−
１）／Ｍ（あるいは△Ｌ／Ｍ）の２進数BY（ある
いは△BY）を求める位置変換部、９１１は位置
変換部９１０の出力である２進数BY（あるいは
△BY）を第５図ａ（あるいは第５図ｂ）および
第７図に示した方法により符号化する符号化部、
９１２は符号化部９０８および９１１の出力を１
ライン毎に合成する合成部、９１３は第８図ａ
（あるいは第８図ｂ）に示す符号列を記憶するメ
モリである。

次に第９図の動作例を説明する。メモリ制御部
９０５により、メモリ９０１内の２次元の２値パ
ターンの第１ライン目をラインバツフア９０４に
記憶する。ラインバツフア９０４から、ラン長抽
出部９０６により、ラン１１１を抽出し、ラン長
３５画素（ドツト）（第１図）を出力する。本動
作と同時にライン検出部９０９は、ラン長抽出部
９０６の出力であるラン長R_s＝35を記憶し、メ
モリ９０２内のＮ＝248と比較し、Ｎ＞R_sである
ので、動作を継続し、ランの垂直方向の位置をＬ
＝０（あるいは△Ｌ＝０）とする。ラン長変換部
はラン長Ｒ＝35とメモリ９０２内のＮ＝248によ
り、R′／Ｎ（すなわち34／248）を演算し、BX＝
0.0010001100（l_x＝10である）を出力する。符号化
部９０８はBX＝0.0010001100から、第４図およ
び第６図に示した方法により符号10000011000を
生成する。位置変換部９１０はＬ＝１（あるいは
△Ｌ＝０）から（Ｌ−１）／Ｍ（あるいは△Ｌ／
Ｍ）を演算し、BY＝0.00000000（あるいは△BY
＝0.00000000）（l_BY＝８あるいはl△_BY＝８）を出
力する。符号化部９１１はBY（あるいは△BY）
を第５図ａ（あるいは第５図ｂ）および第７図に
示した方法により符号0000（あるいは0000）を生
成する。合成部９１２は符号化部９０８，９１１
の出力を合成し、000010000011000（あるいは
000010000011000）を出力し、メモリ９１３に記
憶する。次にラン長抽出部９０６はラインバツフ
ア９０４からラン１１２を抽出し、ラン長Ｒ＝
110を出力する。ラン長変換部９０７および符号
化部９０８により符号100101000011を生成し、合
成部９１２を介して100101000011をメモリ９１３
に記憶する。ライン検出部ではラン長１１０と記
憶していたラン長R_s＝35との和をとり、R_s＝145
とし、Ｎ＞R_sであるので動作を継続する。ラン
１１３、ラン１１４に対しても同様の動作を繰り
返しメモリ９１３に２値パターンの第１ライン目
に対応した符号（第８図のａ（あるいは第８図ｂ
の第１行目）を記憶する。このときライン検出部
９０９ではR_s＝248となりＮと等しくなるので、
１ライン終了したことを検出し、メモリ制御部９
０５に次ライン続出しを指示する。メモリ制御部
９０５はメモリ９０１内の２値パターンの第２ラ
イン目をラインバツフア９０４に呼び出す。ラン
長抽出部９０６はラインバツフア９０４内の２値
パターンからラン長Ｒ＝248を抽出する。ライン
検出部９０９ではR_s＝248とし、Ｎと等しくなる
ので、１ライン終了を検出し、（白ライン検出）、
メモリ制御部に次ライン読出しを指示すると同時
に、Ｌ（あるいは△Ｌ）をインクリメントしてＬ
＝２（あるいは△Ｌ＝１）とする。次に２値パタ
ーンの第３ラインをラインバツフア９０４に呼び
出す。ラン長抽出部９０６はラン１３１を抽出し
てラン長３０を出力する。ライン検出部９０９は
R_s＝30としR_s＜Ｎであるため動作を継続すると
ともにＬ（あるいは△Ｌ）をインクリメントして
Ｌ＝３（あるいは△Ｌ＝32）とする。以下ラン１
３１〜１３３を抽出して、メモリ９１３に第８図
ａ（あるいは第８図ｂ）の第２行目の符号列を記
憶する。この時ライン検出部９０９では次のライ
ンの呼び出し指示を行うとともに、ランの垂直方
向の位置が相対のときは△Ｌ＝０にリセツトす
る。以降同様の動作を繰り返し、メモリ９１３に
第８図ａ（あるいは第８図ｂ）の符号列を記憶す
る。（本動作例では垂直方向の絶対位置および相
対方向の２つの場合の動作を示したが、実際には
どちらか一方でよい） 以上が動作の説明である。説明上、メモリ９０
１〜９０３に第１図の２値パターン（Ｎ＝248、
Ｍ＝204）を記憶し、符号化部９０８，９１１に
それぞれ第４図（第６図）、第５図（第７図）に
示した符号化手法を用いると仮定したが、２値パ
ターン、ＮおよびＭ（したがつてＲおよびＬ、△
Ｌも）は任意である。第４図および第５図に示し
たbi（ｉ１）とcj（ｊ１）の各ビツトの組みか
え方法も任意である。また２進数BX、BY、△
BYの情報源に対してハフマン符号化等の任意の
情報源符号化手法を用いてもよい。第９図の実施
例の動作手順で、あるラインの最初のラン（例え
ば第１図の２値パターンのラン１１１やラン１２
１等）にランの垂直方向の位置を示す符号を付け
たが、１ライン分のランの符号を符号化部９０８
に記憶して、ランの垂直方向の位置を示す符号を
付け加えて合成してもよい。またメモリ９０２，
９０３それぞれにＮ，Ｍを記憶するとしたが、第
１ライン目は特別にラン長を抽出しながら画素数
をカウントしてＮを登録することも可能である。
また２値パターンの水平方向のランをすべて符号
化しながら、ライン数をカウントし、後でランの
垂直方向の位置を２進数で規格化し、符号化して
付加してもよい。

本発明による符号化手法を用いて符号化した符
号列を復号するには、出力する装置に適した水平
方向の画素数N₁と垂直方向の画素数M₁を選択し
て、２値パターンを生成することができ、N₁，
M₁を入力時の画素数Ｎ，Ｍと等しくする必要は
ない。垂直方向の位置の符号の復号化は、１ライ
ン中のランの２進数の和を検出することにより符
号列が切れるため可能である。

また水平方向、垂直方向という意味を互いに直
交していれば水平方向を装置の水平方向とする必
要はない。

(5) 効果の説明 以上説明したように、本発明によれば、２次元
の２値パターンの水平方向のランの長さを０
BX＜１の２進数で規格化して該２進数BXを符
号化し、水平方向のランの垂直方向の絶対あるい
は相対位置（ラインの絶対あるいは相対位置）を
０BY＜１の２進数で規格化して該２進数BY
（絶対あるいは相対位置を示す）を符号化するた
め、入出力装置の入出力精度（例えばフアクシミ
リの走査線方向、副走査線方向の線密度、デイス
プレイの水平、垂直方向の解像度等）に依存しな
い形で、２値パターンを記憶することができ、か
つ規格化した２進数を符号化するため情報圧縮が
可能である。

【図面の簡単な説明】

第１図は２次元の２値パターンの例、第２図は
第１図の２値パターンについてのワイル符号化
列、第３図は規格化したラン長の例、第４図は水
平方向のラン長の２進表現BXの符号化例、第５
図は水平方向のランの垂直方向の位置の２進表現
BXおよび△BYの符号化例、第６図はラン長Ｒ
と第４図の手法による符号の対応、第７図はライ
ン位置と第５図の手法による符号の対応、第８図
は第１図の２次元の２値パターンを第４図（第６
図）および第５図（第７図）の手法によつて符号
化した符号列、第９図は本発明の一構成例であ
る。 １１１〜１１４……第１ラインのラン、１２１
……第２ラインのラン、１３１〜１３３……第３
ラインのラン、２１１〜２１４……ラン１１１〜
１１４のワイル符号、２２１……ラン１２１のワ
イル符号、２３１〜２３３……ラン１３１〜１３
３のワイル符号、３１０，３２０，３３０……垂
直方向の絶対位置を規格化した位置、３１１〜３
１４……ラン１１１〜１１４の規格化したラン
長、３２１……ラン１２１の規格化したラン長、
３３１〜３３３……ラン１３１〜１３３の規格化
したラン長、８１０ａ，８３０ａ……位置３１
０，３３０の絶対位置の符号、８１０ｂ，８３０
ｂ……位置３１０，３３０の相対位置の符号、８
１１〜８１４……ラン長３１１〜３１４の２進数
を符号化した符号、８３１〜８３３……ラン長３
３１〜３３３の２進数を符号化した符号、９０１
〜９０３……メモリ、９０４……ラインバツフ
ア、９０５……メモリ制御部、９０６……ラン長
抽出部、９０７……ラン長変換部、９０８……符
号化部、９０９……ライン検出部、９１０……位
置変換部、９１１……符号化部、９１２……合成
部、９１３……メモリ。

Claims (1)

1. 【特許請求の範囲】 １ ２値パターンのランレングスを符号化する処
   理方式において、 入力装置あるいは出力装置において表現可能な
   水平方向、垂直方向の最大画素数をそれぞれ
   Nmax、Mmax、２値パターンの水平方向、垂直
   方向の画素数をそれぞれＮ（Nmax）、Ｍ（
   Mmax）、白あるいは黒画素の水平方向の任意の
   ランの長さをＲ（Ｎ）、該ランを含むラインの絶
   対あるいは相対位置をそれぞれＬ（ＬＭ）ある
   いは△Ｌ（△ＬＭ）として、 （Ｒ−１）／Ｎによりランの長さを規格化し、
   規格化した該ランの長さを０BX＜１なる２進
   数BXで表現する手段と、 該２進数BXを符号化する手段と、 （Ｌ−１）／Ｍあるいは△Ｌ／Ｍにより該ラン
   を含むラインのそれぞれ絶対あるいは相対位置を
   規格化し、規格化した該ラインの絶対あるいは相
   対位置を、０BY＜１あるいは０△BY＜１
   なる２進数BYあるいは△BYで表現する手段と、 該２進数BYあるいは△BYを符号化する手段
   とを有することを特徴とした ２値パターン符号化処理方式。