JPS5946395B2 - 文字パタ−ンデ−タ圧縮方法 - Google Patents

Description

【発明の詳細な説明】 本発明はドット・マトリックスを用いて表現された文字
パターンデータの圧縮方法に関する。

第１図は漢字「高」を（２４行×２４列）のドット・マ
トリックスで表現した例で、あるが、画素の黒丸を゛１
’’、空白を゛゛ｏ’’に対応させ、第１百花より右へ
進み、以下第２行、第３行へと順次進めると５７６ビッ
トのビット列が得られる。文字′ゞターンンデータの圧
縮を行なわない場合はこれを１語として記憶装置に番地
付けして格納する。もしドット・マトリックスの゛０１
’’、゛ｏ”が全くランダムに生起するものであればこ
の文字′ゞターンデータを圧縮することは困難であるが
、漢字のドット′ゞターンは一定の統計的傾向を有して
いる。したがつてこの傾向を利用することによつて漢字
′ゞターンデータをもつと短かいデータで表現できる可
能性がある。そこで、漢字パターンが統計的にどのよう
な性質を持つているかを考えてみるとある画素の状態は
、その周囲の画素の状態に対して互いに独立ではなく、
それらの間に極めて強い相関関係のあることが分かる。
例えば、ある画素の周囲の画素の状態がすべて白ならば
その画素の状態も白、反対に周囲が黒ならば、その画素
も黒である確率は極めて高い。さらに周囲の画素もそれ
ぞれ互いに条件が異なり左右上下に隣接した画素が黒で
ある時に、注目している画素が黒である確率と斜めに隣
接した画素が黒である時に、注目している画素が黒であ
る確率とでは、前者の方がはるかに大きいと予想できる
。その理由は漢字には横線または縦線は多く使われるが
、斜めの線はそれに比較して少ないからである。このよ
うな漢字パターンの統計的傾向を利用した漢字パターン
データの圧縮法が既に幾つか提案されている。

その一つは例えば（２４×２４）のドツト・マトリツク
スを２×２のサブマトリクスに分割し、ハフマン（Ｈｕ
ｆｆｍａｎ）の符号化法を適用するものである。

サブマトリツクスは４個の画素から成つているので、そ
のとり得るパターン（以下サブパターンと呼ぶ）は２４
＝１６通りあり、あるサブマトリクスにどのサブパター
ンが生じるかは、その周囲のサブマトリクスの状態に依
存していると考えられるので、各サブパターンを単独に
符号化するより周囲の条件を考慮して符号化すると効率
が土がる。そこであるサブマトリクスに対して、条件と
なるサブマトリクスを１つだけ定めるものとすると、漢
字の特性を考慮して、土下よりも左右の相関の方が強い
と考えられることから、左隣りまたは右隣りのサブパタ
ーンを条件とすることが望ましい。

ここでは、左隣りに特定のサブパターンが与えられたこ
とを条件として注目するサブマトリクスに生じる１６個
のサブパターンに対してハフマンの符号化を行う。２４
×２４ドツト・マトリツクスの符号語への変換は第２図
に示されるように左土からスタートして、各行毎に右方
向にスキヤニングしていき、右下で終了する方式によつ
てなされる。

ただし、左の欄外に条件付確率を与える初期条件として
、任意のサブパターンがあるものと仮定する。そして最
も自然な初期条件として第３図に示されるサブパターン
を初期条件Ｓ。とする。一つの漢字パターンのデータは
次のようにして作られる。

すなわち、サブパターンＳ。

を条件とした時にＳ，に割当てられた符号語を先頭にじ
て、順番に次々とＳｉを条件とした時に、Ｓ１＋１に割
当てられた符号語を並べＳｌ２まで行ない、次に行を変
え同じくサブパターンＳ。を条件とした時にＳｌ３に割
当てられた符号語を先頭にして前記と同じ操作を行なう
。この操作をＳ，４４まで行なえば、漢字パターンデー
タが得られる。以上の方法を、明朝体漢字２９６１文字
について実際に調べた結果、得られたパターンデータの
漢字１個当りの平均符号長は約３５５ビツトとなつた。

したがつて従来のドツト・マトリツクスパターンをその
まま記憶装置に入れる方法に比べて約３８．４％圧縮さ
れたことになる。ハフマン符号の符号長及びハフマン符
号の例は第４図に示す表の通りである。このようにハフ
マンの符号化を行なえば高い圧縮率が得られるが、ハフ
マンの符号化法では１つのサブパターンに対して１６個
の符号語から成る１つの符号（符号語の集合）が得られ
るから全部で１６通りの異なる符号が得られ、各事象に
与えられる符号は長さに規側性のない符号となつてしま
う。

したがつてこの圧縮法では文字ノマターンデータの復元
が難しく、非常に復雑な復元回路を要するという欠点を
有する。そこで条件となる１６通りのサブパターンに対
して第５図の表に示す１６個の出現頻度に応じた順位と
等しい長さをもつ可変長符号語を出現頻度の高い順に符
号長の短かいものから割り当てる方法が提案された。

しかしながらこの方法は復号回路が簡単である利点はあ
るが、実際に明朝体漢字２９６１文字について調べた結
果得られたパターンデータの漢字１個当りの平均符号長
は約３８４ビツトで、圧縮率は約３３．４％に下がり、
あまり高い圧縮率が得られない欠点を有する。本発明は
上記従来の文字ノマターン圧縮方法の欠点を除去するも
ので、圧縮率が高くかつ復元の容易な文字パターン圧縮
方法を提供することを目的とする。

この目的を達成するため、本発明の方法は上記方法と同
様に（Ｍ行×Ｎ列）のドツト・マトリツクスを用いて表
現された文字パターンを（ｍ行×ｎ列）のサブマトリク
スに分割し、個々のサブマトリクスに対してその隣りの
サブマトリクスを条件とする出現頻度に基いて可変長符
号化を行なうものであつて、上記サブマトリクスのパタ
ーンを出現頻度の大きい順に並べ、順位が２位までのも
のに対しては順位と等しい長さの符号を割り当て、順位
が３位以降のものに対しては順位！と（１十１）（ｉは
３以上の奇数）の符号長を等しくかつ順位が２つ下がる
ごとに符号長を１ビツトずつ長くすると共に符号の後に
符号の切れ目を示すビツトと上記順位１と（１＋１）を
区別するビツトとをつけた符号を割り当てたものである
。

第６図は本発明の文字パターンデータ圧縮方法に用いた
可変長符号の例を示すものである。

前述のサブノぐターンを出現頻度の大きい順に並べ、順
位が一位と２位のものに対しては順位と等しい１ビツト
と２ビツトの符号長の符号を割り当てる。即ち順位が２
位までのサブ′マターンに対しては、順位をｌとすると
“１サを（１−１）個並べ、その後に“０”をつけた符
号を割り当てる。そして順位が３位以降のサブノマター
ンに対しては順位をｉとすると、順位がｉと（１＋１）
のサブパターンに割り当てる符号の長さを等しくし、か
つｉが２つ下がることに３１″を１個ずつ増やし、その
後に“０１をつけ、更にその後に００７又は″１”をつ
ける。前記最後のビツト６０５゛又は″１゛は同符号長
の符号を区別するためのもので、これ以外の“０゛は符
号の切れ目を示すためのものである。このようにして（
Ｍ行×Ｎ列）のドツト・マトリツクスノマターンを（ｍ
行×ｎ列）のサブマトリクスに分割し、このサブマトリ
クスに対してその隣りのサブマトリクスを条件とする出
現頻度に応じて可変長符号化を行なうと、明朝体漢字２
９６１文字について調べた結果、漢字１個当りのパター
ンデータの平均符号長は約３５８ビツトとなり、約３７
，９％圧縮された。

この符号化方法によれば、ハフマン符号による圧縮法よ
りやや圧縮率は下がるが、ほとんど同程度の圧縮率で復
号回路がハフマン符号のものより非常に簡単になる。

次に文字パターンデータ圧縮方法によつて圧縮された文
字パターンデータの復号について説明する。

第７図において、文字の内部コードによつて文字パター
ンデータの先頭アドレスを知り、使用している符号の最
大符号長のデータ（上記例では１０ビツト）を図示せぬ
メモリから読み出し、シフトレジスタ１に入れる。この
シフトレジスタ１は１クロツク・タイムごとに１ビツト
のシフトを行ない、その結果が２安定素子２に入る。ま
ず最初に２安定素子２に入つたビツトが“０”であつた
場合には、無条件にワンシヨツト・マルチバイブレータ
３を動作させ、サブパターン変換ＲＯＭ４の出力を、レ
ジスタ５に入る。この場合サブパターン変換ＲＯＭ４の
下４ビツトのアドレスには６００００゛を与える。レジ
スタ５にセツトされたデータが所望のサブパターンであ
り、これはかつ、次のサブパターンを得る条件サブパタ
ーンとなる。

次に最初に２安安素子２に入つたビツトがＵ１”であつ
た場合にはさらに１ビツトのシフトを行ない２安定素子
６に入れる。この時、２安定素子２が゛０″の場合には
ワンシヨツト・マルチバイブレータ３を動作させサブパ
ターン変換ＲＯＭ４の出力をレジスタ５に入れる。この
場合サブパターン変換ＲＯＭの下４ビツトのアドレスに
は、−０００１Ｗを与える。２安定素子２が６１゛の場
合にはワンシヨツト・マルチバイブレータ３は動作させ
ず、カウンタ７に１が加算される。

そして、２安定素子２に゛０にが来るまでカウンタ７に
１を加算し、２安定素子６が１から″′０゛に変わつた
時にワンシヨツト・マルチバイブレータ３を動作させサ
ブパターン変換ＲＯＭ４の出力をレジスタ５ｔこ入れる
。この場合サブパターン変換ＲＯＭ４の下４ビツトのア
ドレスには、カウンタ７の出力と２安定素子２の出力と
を与える。一方、マルチバイブレータ３の出力は遅延回
路８により遅延をうけて、カウンタ７のりセツト端子に
入り、その値を初期値０に戻す。また行カウンタ９はサ
ブノ寸ターンがレジスタ５にセツトされる毎に１が加算
され、その内容が１２になつた時、遅延回路１０により
遅延をうけた信号がレジスタ５のりセツト端子に入り、
その値を初期条件のサブパターン６００００゛に戻す。
以上詳細に説明したように、本発明の文字パターン圧縮
方法によれば、文字パターンデータへの復号が容易であ
ると共に多数の文字パターンを高度に圧縮できる効果が
ある。

【図面の簡単な説明】

第１図は本発明の文字パターンデータ圧縮方法を適用す
る漢字ドツト・マトリツクズノ゛マターンの一例を示す
図、第２図は第１図のドツト・マトリツクスのサブマト
リクスへの分割例を示す図、第３図は初期条件のサブパ
ターンを示す図、第４図はハフマン符号の例を示す図、
第５図は従来の可変長符号の例を示す図、第６図は本発
明で用いた可変長符号の例を示す図、第７図は本発明に
よつて圧縮されたパターンデータの復号回路の一例を示
すプロツク図である。

Claims (1)

【特許請求の範囲】
1. １ 今回入力した文字パターンデータの連続した「１」
   の数を計数するカウンタと、このカウンタの出力を第１
   のアドレスとし、前回入力した文字パターンデータを復
   号した結果のサブパターンを第２のアドレスとするサブ
   パターン変換メモリと、このメモリのサブパターン出力
   を蓄積するレジスタとを備え、このレジスタの出力を今
   回入力した文字パターンデータのサブパターンとする復
   号回路に用いる符号において、（Ｍ行×Ｎ列）のドット
   ・マトリックスを用いて表現された文字パターンデータ
   を（ｍ行×ｎ列）のサブマトリックスに分割してサブパ
   ターンとし、個々のサブマトリックスに対してその隣り
   のサブマトリックスを条件とする出現頻度に基いて可変
   長符号化を行なうものであつて、上記サブパターンを出
   現頻度の大きい順に並べ、順位が２位までのものに対し
   ては順位と等しい長さの符号を割り当て、順位が３位以
   降のものに対してはｉを３以上の奇数として順位ｉと（
   ｉ＋１）の符号長を等しくかつ順位が２つ下がるごとに
   符号長を１ビットずつ長くするとともに符号の後に符号
   の切れ目を示すビットと上記順位ｉと（ｉ＋１）を区別
   するビットとをつけた符号を割り当てて上記サブパター
   ン変換メモリに蓄積したことを特徴とする文字パターン
   データ圧縮方法。