JPS6360953B2 - - Google Patents
Info
- Publication number
- JPS6360953B2 JPS6360953B2 JP2243482A JP2243482A JPS6360953B2 JP S6360953 B2 JPS6360953 B2 JP S6360953B2 JP 2243482 A JP2243482 A JP 2243482A JP 2243482 A JP2243482 A JP 2243482A JP S6360953 B2 JPS6360953 B2 JP S6360953B2
- Authority
- JP
- Japan
- Prior art keywords
- binary
- run length
- encoding
- run
- memory
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
- 238000000034 method Methods 0.000 claims description 17
- 238000010586 diagram Methods 0.000 description 11
- 238000006243 chemical reaction Methods 0.000 description 6
- 238000000605 extraction Methods 0.000 description 4
- 239000000284 extract Substances 0.000 description 2
- 240000005528 Arctium lappa Species 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 230000006835 compression Effects 0.000 description 1
- 238000007906 compression Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000010606 normalization Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N1/00—Scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission; Details thereof
- H04N1/41—Bandwidth or redundancy reduction
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
Description
【発明の詳細な説明】
(1) 発明の属する分野の説明
本発明は2値パターンのランレングスを符号化
する方式に関するものである。
する方式に関するものである。
(2) 従来の技術の説明
従来第1図のような2値パターンを符号化する
には、2値パターンの1次元ランレングス(ラン
長)を情報源とし、モデイフアイドハフマン
(MH)符号化やワイル符号化等を用いていた。
第2図に第1図の2値パターンをワイル符号化
(符号―ランレングスの対応テーブルは、H.
Wyle、etal:Reduced―Time Facsimile
Transmission by Digital Coding、IRE
Trans、Vol、CS―9、No.3、1961を参照)した
符号列を示す。11は第1の(白)ラン(ここで
2値パターンの最初のランは白あるいは黒のどち
らかのランから始まるものと仮定する)、12は
第2の(黒)ラン、13は第3の(白)ラン、1
4は第4の(黒)ランである。また21〜24は
それぞれラン11〜14のワイル符号列である。
ここに示した例のようにラン長は白あるいは黒画
素(あるいはドツト)の連続する個数で表現さ
れ、前記従来の符号化手法もこの画素列で表現し
たラン長をもとに符号テーブルを作成し、符号化
および復号化処理により、2値パターンの記憶あ
るいは伝送を行つてきた。
には、2値パターンの1次元ランレングス(ラン
長)を情報源とし、モデイフアイドハフマン
(MH)符号化やワイル符号化等を用いていた。
第2図に第1図の2値パターンをワイル符号化
(符号―ランレングスの対応テーブルは、H.
Wyle、etal:Reduced―Time Facsimile
Transmission by Digital Coding、IRE
Trans、Vol、CS―9、No.3、1961を参照)した
符号列を示す。11は第1の(白)ラン(ここで
2値パターンの最初のランは白あるいは黒のどち
らかのランから始まるものと仮定する)、12は
第2の(黒)ラン、13は第3の(白)ラン、1
4は第4の(黒)ランである。また21〜24は
それぞれラン11〜14のワイル符号列である。
ここに示した例のようにラン長は白あるいは黒画
素(あるいはドツト)の連続する個数で表現さ
れ、前記従来の符号化手法もこの画素列で表現し
たラン長をもとに符号テーブルを作成し、符号化
および復号化処理により、2値パターンの記憶あ
るいは伝送を行つてきた。
しかし2値パターンの入出力装置(例えばフア
クシミリ、ラスタスキヤン形CRT等)は、走査
線方向の画素数あるいは線密度が異なるため、前
記符号化手法により符号化した2値パターンを線
密度の異なる装置に出力すると走査方向の大きさ
が違つてしまうという欠点があつた。この欠点を
改良するため線密度変換(例えば午坊、桐原:フ
アクシミリ線密度変換方式、画像電子学会、全大
予稿―10、1975等)を用いて、2値パターンの大
きさを整合させたり、拡大あるいは縮小する方式
が提案されている。しかしある一定の線密度をも
つ装置相互間の変換を行うため、装置の線密度を
あらかじめ知つておく必要があり、多種類の入出
力装置で入出力する2値パターンの相互変換を行
うためには、あらかじめ変換を行う装置間でネゴ
シエイシヨンをする必要があり、変換のアルゴリ
ズムを複数種類用意する必要があつた。
クシミリ、ラスタスキヤン形CRT等)は、走査
線方向の画素数あるいは線密度が異なるため、前
記符号化手法により符号化した2値パターンを線
密度の異なる装置に出力すると走査方向の大きさ
が違つてしまうという欠点があつた。この欠点を
改良するため線密度変換(例えば午坊、桐原:フ
アクシミリ線密度変換方式、画像電子学会、全大
予稿―10、1975等)を用いて、2値パターンの大
きさを整合させたり、拡大あるいは縮小する方式
が提案されている。しかしある一定の線密度をも
つ装置相互間の変換を行うため、装置の線密度を
あらかじめ知つておく必要があり、多種類の入出
力装置で入出力する2値パターンの相互変換を行
うためには、あらかじめ変換を行う装置間でネゴ
シエイシヨンをする必要があり、変換のアルゴリ
ズムを複数種類用意する必要があつた。
(3) 発明の目的
本発明はこれらの欠点を解決するため、2値パ
ターンのランの長さ(ランレングス)を0B<
1の2進数で規格化して、該2進数Bを符号化す
ることを特徴とし、その目的は2値パターンの情
報を圧縮し、かつ入出力装置の入出力精度に依存
しない形で、2値パターンの情報を表現すること
にある。
ターンのランの長さ(ランレングス)を0B<
1の2進数で規格化して、該2進数Bを符号化す
ることを特徴とし、その目的は2値パターンの情
報を圧縮し、かつ入出力装置の入出力精度に依存
しない形で、2値パターンの情報を表現すること
にある。
(4) 発明の構成および作用の説明
第3図は、第1図の2値パターンのランレング
スを規格化する方法を示している。31〜34
は、それぞれラン11〜14を規格化した分数
(フラクシヨン)表現のラン長を示す。ここで規
格化というのは、入力(あるいは出力)装置で表
現可能な走査方向の最大の画素数をNmax、2値
パターンの走査方向の画素数をN(Nmax)、白
あるいは黒画素のあるラン長をR(RN)とす
ると、R′/N(R′△ =R−1、△ =は定義を示す)が
規格化した該ランのラン長の分類表現である。し
たがつて画素数Nは512であるから、ラン長31
は96/512=3/16、ラン長32は128/512=1/4、ラ
ン長33は160/512=5/16、ラン長34は128/512
=1/4で規格化される。第4図はラン長の分類表
現と2進表現の例である。ラン長の規格化した分
類表現R′/Nは次のように2進数Bに変換され
る。
スを規格化する方法を示している。31〜34
は、それぞれラン11〜14を規格化した分数
(フラクシヨン)表現のラン長を示す。ここで規
格化というのは、入力(あるいは出力)装置で表
現可能な走査方向の最大の画素数をNmax、2値
パターンの走査方向の画素数をN(Nmax)、白
あるいは黒画素のあるラン長をR(RN)とす
ると、R′/N(R′△ =R−1、△ =は定義を示す)が
規格化した該ランのラン長の分類表現である。し
たがつて画素数Nは512であるから、ラン長31
は96/512=3/16、ラン長32は128/512=1/4、ラ
ン長33は160/512=5/16、ラン長34は128/512
=1/4で規格化される。第4図はラン長の分類表
現と2進表現の例である。ラン長の規格化した分
類表現R′/Nは次のように2進数Bに変換され
る。
R′/N=b12-1+b22-2+……+bi2-l+……
B0.b1b2……bl
ここでは等しいあるいはほぼ等しいことを示
す。2進数Bは任意のビツト数lまで有効とし、
bi(i>l)はすべて0とする。なおlをl>
log2Nとなる最小の整数とすれば入力した2値パ
ターンの精度を最小ビツト数で保つことができ
る。
す。2進数Bは任意のビツト数lまで有効とし、
bi(i>l)はすべて0とする。なおlをl>
log2Nとなる最小の整数とすれば入力した2値パ
ターンの精度を最小ビツト数で保つことができ
る。
第5図は前記l=9としたときの2進数Bの符
号化例である。ある2進数に対応する符号を、 Ci=b10-i(0<i9)Ci=bi(i10)として、
Ck(k>k′、k′はCk=1となる最大の整数)をす
べてサプレスして構成し、0−1列C1……Ck′の
ビツト長を表現する数k′を2進数化してC1……
Ck′のヘツダとする。第6図はラン長Rと第5図
による符号例の対応を示す。第7図は第5図の符
号化方法の例により、第1図の2値パターンを符
号化した符号列である。71〜74はそれぞれ2
値パターンのラン11〜14(および規格化した
分類表現のラン長31〜34)の符号である。
号化例である。ある2進数に対応する符号を、 Ci=b10-i(0<i9)Ci=bi(i10)として、
Ck(k>k′、k′はCk=1となる最大の整数)をす
べてサプレスして構成し、0−1列C1……Ck′の
ビツト長を表現する数k′を2進数化してC1……
Ck′のヘツダとする。第6図はラン長Rと第5図
による符号例の対応を示す。第7図は第5図の符
号化方法の例により、第1図の2値パターンを符
号化した符号列である。71〜74はそれぞれ2
値パターンのラン11〜14(および規格化した
分類表現のラン長31〜34)の符号である。
第8図は本発明の一構成例であり、81は2値
パターンを記憶するためのメモリ、82はメモリ
81内の2値パターンのランの長さRを抽出する
ラン長抽出部、83は2値パターンの走査方向の
画素数Nを記憶するメモリ、84はラン長抽出部
82で得られたラン長と、メモリ83内の画素数
Nを入力として、R′/N(R′△ =R−1)なる演算
を行い規格化した2進数Bに変換する2進数化
部、85は2進数Bから、対応した符号を求める
符号化部、86は符号化部85から得られた符号
(あるいは符号列)を記憶するメモリである。
パターンを記憶するためのメモリ、82はメモリ
81内の2値パターンのランの長さRを抽出する
ラン長抽出部、83は2値パターンの走査方向の
画素数Nを記憶するメモリ、84はラン長抽出部
82で得られたラン長と、メモリ83内の画素数
Nを入力として、R′/N(R′△ =R−1)なる演算
を行い規格化した2進数Bに変換する2進数化
部、85は2進数Bから、対応した符号を求める
符号化部、86は符号化部85から得られた符号
(あるいは符号列)を記憶するメモリである。
第8図の動作例の説明上、メモリ81には第1
図の2値パターンが記憶され、メモリ83にはN
=512が記憶され、符号化部85は第5図に示し
た符号化手法を用いると仮定する。まずメモリ8
1内の2値パターンから、ラン長抽出部82によ
つてラン11を抽出し、ラン長97画素(ドツト)
を出力する。2進数化部84はラン長R=97とメ
モリ83内のN=512によりR′/N(すなわち96/
512)を演算しB=0.0011を求める。次に符号化
部85は、B=0.0011から第5図に示した符号化
手法により符号01110000011を生成し、メモリ8
6に該符号を記憶する。以下ラン12〜14につ
いても同様の動作を行い、第7図に示された符号
列をメモリ86に記憶する。
図の2値パターンが記憶され、メモリ83にはN
=512が記憶され、符号化部85は第5図に示し
た符号化手法を用いると仮定する。まずメモリ8
1内の2値パターンから、ラン長抽出部82によ
つてラン11を抽出し、ラン長97画素(ドツト)
を出力する。2進数化部84はラン長R=97とメ
モリ83内のN=512によりR′/N(すなわち96/
512)を演算しB=0.0011を求める。次に符号化
部85は、B=0.0011から第5図に示した符号化
手法により符号01110000011を生成し、メモリ8
6に該符号を記憶する。以下ラン12〜14につ
いても同様の動作を行い、第7図に示された符号
列をメモリ86に記憶する。
ここでメモリ81に第1図の2値パターンを記
憶し、N=512とし、符号化部85を第5図に示
した符号化手法を用いて実現すると仮定したが、
メモリ81内の2値パターンは任意であり、Nも
任意の自然数、またR(N)も任意の自然数で
ある。さらに2進数化部84でR′/Nを演算す
ると説明したが、1/Nを2進数化(十分大きな
精度は必要である)し、R′回和算を行つてもよ
い。また2進数Bの符号化手法を第5図に示した
bi(i1)とCj(j1)の各ビツトの組みかえ
方法は、出現頻度等を考慮することにより任意に
変換できる。さらに2進数Bの情報源に対してハ
フマン符号化等の任意の情報源符号化手法を用い
てもよい。
憶し、N=512とし、符号化部85を第5図に示
した符号化手法を用いて実現すると仮定したが、
メモリ81内の2値パターンは任意であり、Nも
任意の自然数、またR(N)も任意の自然数で
ある。さらに2進数化部84でR′/Nを演算す
ると説明したが、1/Nを2進数化(十分大きな
精度は必要である)し、R′回和算を行つてもよ
い。また2進数Bの符号化手法を第5図に示した
bi(i1)とCj(j1)の各ビツトの組みかえ
方法は、出現頻度等を考慮することにより任意に
変換できる。さらに2進数Bの情報源に対してハ
フマン符号化等の任意の情報源符号化手法を用い
てもよい。
第9図は第7図に示した符号列を復号化して2
値パターンを生成する装置の一構成例である。9
1は第7図に示した符号列を記憶するメモリ、9
2はメモリ91内の符号を第5図の示した符号化
の逆変換を行つて2進数Bを生成する復号化部、
93は出力装置で表現できる2値パターンの走査
方向の画素数N1を記憶するメモリ、94は復号
化部92の出力である2進数Bとメモリ93内の
N1からN1×B+1なる演算を行つてラン長R1を
生成するラン長発生部、95はラン長発生部94
の出力であるラン長Rから白あるいは黒画素のラ
ンを生成するラン生成部である。
値パターンを生成する装置の一構成例である。9
1は第7図に示した符号列を記憶するメモリ、9
2はメモリ91内の符号を第5図の示した符号化
の逆変換を行つて2進数Bを生成する復号化部、
93は出力装置で表現できる2値パターンの走査
方向の画素数N1を記憶するメモリ、94は復号
化部92の出力である2進数Bとメモリ93内の
N1からN1×B+1なる演算を行つてラン長R1を
生成するラン長発生部、95はラン長発生部94
の出力であるラン長Rから白あるいは黒画素のラ
ンを生成するラン生成部である。
第9図の動作は第8図と反対の動作を行なう。
ただし、N1およびR1はそれぞれ装置の特性によ
りNおよびRと等しくする必要はない。
ただし、N1およびR1はそれぞれ装置の特性によ
りNおよびRと等しくする必要はない。
以上の説明は走査方向のラン長の符号化である
が、走査方向と垂直な方向に関しては、N画素か
らなる複数のランを垂直方向に順々に入力して符
号化する。逆に符号列を複号化してN画素からな
る複数のランを垂直方向に順々に出力することに
より実現できる。
が、走査方向と垂直な方向に関しては、N画素か
らなる複数のランを垂直方向に順々に入力して符
号化する。逆に符号列を複号化してN画素からな
る複数のランを垂直方向に順々に出力することに
より実現できる。
また以上の説明ではN=512(=29)すなわち2
のべき乗について述べたが、Nが任意の自然数の
場合にも本発明が適用可能であることを以下補足
する。例えばN=24で有効ビツト(小数点以下の
ビツト数)をl=6とすると、第10図のように
ラン長と2進数Bが対応し、この2進数をもとに
符号化することができる。また第6図および第9
図の規格化した2進表現では、有効長lより大き
いビツトについては、bi=0(i>l)としてい
る。すなわち切り捨てているが、以下のように2
進化を行つてもよい。
のべき乗について述べたが、Nが任意の自然数の
場合にも本発明が適用可能であることを以下補足
する。例えばN=24で有効ビツト(小数点以下の
ビツト数)をl=6とすると、第10図のように
ラン長と2進数Bが対応し、この2進数をもとに
符号化することができる。また第6図および第9
図の規格化した2進表現では、有効長lより大き
いビツトについては、bi=0(i>l)としてい
る。すなわち切り捨てているが、以下のように2
進化を行つてもよい。
R′/Nb12-1+b22-2+…+bl2-l+bl+12-(l+1)+
… B0.b1b2……blbl+1…… のとき、例えばbl+1=1ならば、B△ =0.b1b2……bl
+0.00……01(小数点以下l桁)すなわち0捨1
入を行つてもよい。そのとき参照するビツト数h
(bl+1……bl+h)と繰りあげるか否かは任意に決め
ることができる。
… B0.b1b2……blbl+1…… のとき、例えばbl+1=1ならば、B△ =0.b1b2……bl
+0.00……01(小数点以下l桁)すなわち0捨1
入を行つてもよい。そのとき参照するビツト数h
(bl+1……bl+h)と繰りあげるか否かは任意に決め
ることができる。
(5) 効果の説明
以上説明したように2値パターンのランの長さ
を0B<1の2進数で規格化して表現し、該2
進数Bを符号化するため、入出力装置の入出力精
度(例えばフアクシミリの線密度、デイスプレイ
の解像度等)に依存しない形で2値パターンを記
憶することができ、かつ規格化した2進数を符号
化することにより情報圧縮が可能となる。
を0B<1の2進数で規格化して表現し、該2
進数Bを符号化するため、入出力装置の入出力精
度(例えばフアクシミリの線密度、デイスプレイ
の解像度等)に依存しない形で2値パターンを記
憶することができ、かつ規格化した2進数を符号
化することにより情報圧縮が可能となる。
第1図は2値パターン例の説明図、第2図は第
1図の2値パターンのワイル符号化列説明図、第
3図は規格化したラン長例の説明図、第4図はラ
ン長の分類表現と2進数表現の対応説明図、第5
図は2進数の符号化手法説明図、第6図はラン長
Rと第5図の符号例の対応説明図、第7図は第1
図の2値パターンを第5図の符号化手法に従つて
符号化した符号列説明図、第8図は本発明の実施
例構成図、第9図は復号化装置の実施例構成図、
第10図はN=24の場合のラン長と2進数の対応
説明図である。 図中、81はメモリ、82はラン長抽出部、8
3はメモリ、84は2進数化部、85は符号化
部、86はメモリ、91はメモリ、92は復号化
部、93はメモリ、94はラン長発生部、95は
ラン生成部を示す。
1図の2値パターンのワイル符号化列説明図、第
3図は規格化したラン長例の説明図、第4図はラ
ン長の分類表現と2進数表現の対応説明図、第5
図は2進数の符号化手法説明図、第6図はラン長
Rと第5図の符号例の対応説明図、第7図は第1
図の2値パターンを第5図の符号化手法に従つて
符号化した符号列説明図、第8図は本発明の実施
例構成図、第9図は復号化装置の実施例構成図、
第10図はN=24の場合のラン長と2進数の対応
説明図である。 図中、81はメモリ、82はラン長抽出部、8
3はメモリ、84は2進数化部、85は符号化
部、86はメモリ、91はメモリ、92は復号化
部、93はメモリ、94はラン長発生部、95は
ラン生成部を示す。
Claims (1)
- 【特許請求の範囲】 1 2値パターンのランレングスを符号化する方
式において、 入力装置あるいは出力装置で表現可能な走査方
向の最大の画素数をNmax、2値パターンの走査
方向の画素数をN(Nmax)、白あるいは黒画素
のあるラン長をR(RN)として、(R−1)/
Nによりラン長を規格化し、規格化したラン長を
0B<1なる2進数Bで表現し、この2進数B
を符号化することを特徴とする2値パターン符号
化方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57022434A JPS58139567A (ja) | 1982-02-15 | 1982-02-15 | 2値パタ−ン符号化方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57022434A JPS58139567A (ja) | 1982-02-15 | 1982-02-15 | 2値パタ−ン符号化方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS58139567A JPS58139567A (ja) | 1983-08-18 |
| JPS6360953B2 true JPS6360953B2 (ja) | 1988-11-25 |
Family
ID=12082581
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP57022434A Granted JPS58139567A (ja) | 1982-02-15 | 1982-02-15 | 2値パタ−ン符号化方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS58139567A (ja) |
-
1982
- 1982-02-15 JP JP57022434A patent/JPS58139567A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS58139567A (ja) | 1983-08-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0146728B1 (en) | Image processing system | |
| JP2621747B2 (ja) | 画像処理装置 | |
| EP0030437A1 (en) | Method and apparatus for compression and decompression of digital image data | |
| EP0750428B1 (en) | Image processing apparatus and method | |
| WO1997034375A1 (en) | Method for reducing storage requirements for digital data | |
| JP3461309B2 (ja) | ハフマン符号化データ圧縮装置 | |
| US6728412B1 (en) | Method and apparatus for on-the-fly image coding | |
| JP3872217B2 (ja) | ディザ画像の2値表現処理方法、ディザ画像の圧縮2値表現圧縮解除方法、及びディザ画像の圧縮及び圧縮解除システム | |
| EP0349677B1 (en) | Image coding system | |
| JP2511158B2 (ja) | 画像圧縮装置 | |
| Malvar | Fast adaptive encoder for bi-level images | |
| JP2000217003A (ja) | 符号化装置および復号化装置 | |
| JPH0937262A (ja) | 画像処理装置及び方法 | |
| JPS6360953B2 (ja) | ||
| JPH05151349A (ja) | 画像データ圧縮方法および符号化回路 | |
| Jalumuri | A study of scanning paths for BWT-based image compression | |
| JP2708253B2 (ja) | 画像データ圧縮方式 | |
| JP2755464B2 (ja) | 画像データ圧縮方式 | |
| JPH03240173A (ja) | 画像データ圧縮方式 | |
| JPS6360954B2 (ja) | ||
| JP2798767B2 (ja) | 画像データ圧縮方式 | |
| JP2615215B2 (ja) | 画像データ圧縮方式 | |
| JP2708252B2 (ja) | 画像データ圧縮方式 | |
| JPS61136378A (ja) | 符号化方式 | |
| Ignacio et al. | A New Lossless Compression Algorithm for Static Color Images-INA |