JPH0224432B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、画像情報圧縮方式に関し、特に符号
化、復号化の処理が簡単で、メモリ容量を削減で
きるパターン・データの圧縮方式に関するもので
ある。

〔発明の背景〕

従来、フアクス等に採用されているデータ圧縮
方法は、MH（Modified Huffman）またはMR
（Modified Read）符号を用いた符号化によるデ
ータ圧縮であり、圧縮率を高くできる利点はある
が、符号化データをドツト・パターンに戻す復号
化処理において、複雑な処理手順を要し、これを
高速化するには、符号化および復号化のための専
用ハードウエアを多く必要とするため高価となる
欠点があつた。

また、圧縮効果のないパターンが存在し、最悪
パターンでは、MH符号の場合、符号化前のデー
タが符号化後には4.5倍にも増大されることが知
られている。従つて、パターン・データを格納す
る記憶装置の記憶容量は、最悪パターンの出現頻
度を考慮して決めなければならないため、平均圧
縮率が高い割にはあまり大幅な容量削減を望めな
い。

また、紙葉上の画像データをスキヤンして取込
む際、スキヤンの等速性を保つためにある一定時
間以内に当該スキヤンのデータを記憶装置内へ格
納しなければならないような要件がある場合に
は、最悪パターンに合せたスループツト（格納速
度）を確保しなければならない等の問題があつ
た。

また、各ラインとも連続した複数画素ずつのブ
ロツクに区切り、各ブロツク内に１ビツトでも情
報があるときは“１”、全然情報がないときは
“０”としてテーブルを作り、“１”であるブロツ
クの画素情報のみを記憶する方式が提案されてい
る（特開昭58−53272号公報参照）。しかし、この
方式では、オール“１”のものは圧縮できず、特
に帳票の背景部を黒にする装置に対しては、圧縮
効果が少ない欠点がある。

〔発明の目的〕

本発明の目的は、これらの従来の欠点を改善
し、符号化および復号化の処理が簡単な回路で実
現でき、かつ最悪パターンに対しても圧縮効果が
あり、パターン格納用メモリの容量を削減するこ
とができる画像情報圧縮方式を提供することにあ
る。

〔発明の概要〕

上記目的を達成するために、本発明の画像情報
圧縮方式は、時系列の２値画像信号を複数ビツト
単位のワード・データに分割して、メモリに格納
する場合、上記ワード・データの全ビツトが白ま
たは黒のとき以外はメモリに格納するが、全ビツ
トが白または黒のときには、該ワード・データの
直前のワード・データの内容と比較した結果によ
り、メモリに格納するか否かを決定し、かつ各ワ
ード・データごとに、当該ワード・データがメモ
リに格納されているか否かを示すフラグ・ビツト
を発生して、該フラグ・ビツトもメモリに格納す
ることに特徴がある。

すなわち、本発明の第１のポイントは、紙葉上
の画像データをラスタ・スキヤン方式で走査し、
２値化データとしてメモリに取り込む際に、２値
データのビツト列を複数ビツト単位（ワード単
位）に分割し、ワードを構成するビツトがすべて
白データまたはすべて黒データのときは、当該ワ
ードをメモリに格納しないようにして、それ以外
のデータのワードのみをメモリに格納することで
ある。したがつて、紙葉上の大部分を占める余白
を白データとして表わすとともに、紙葉の背景を
黒データとして取り込むことにより、これらはメ
モリに格納されないため、画像データを格納する
メモリ容量を大幅に削減することができる。

本発明の第２のポイントは、各ワードに対応し
て当該ワードがメモリに格納されているか否かを
示すフラグ・ビツトを設け、これをメモリのパタ
ーン格納エリアとは別個のエリアにマツプ・デー
タとして格納するようにした点である。すなわ
ち、前記第１のポイントで、ワード単位にその内
容によつて格納したり、あるいは格納しなかつた
りするのみでは、復号化する際に不十分であるた
め、フラグを設ける。このようにすれば、復号化
の際に、先ず、マツプ・データを読み出し、当該
ワードがメモリに格納されているか否かを判定し
て、格納されていることを示すフラグ・ビツトが
立つているときは、パターン格納エリアより対応
するワードを読み出し、フラグ・ビツトが立つて
いないときは全ビツト白データまたは全ビツト黒
データのワードを発生させればよい。

次に、本発明の第３のポイントは、メモリに格
納しないことを判定する条件として、直前のワー
ドの内容との比較結果、あるいは先頭のときには
白または黒のいずれかに初期値を決めておく点に
ある。

すなわち、第１、第２のポイントだけの符号方
式では、フラグ・ビツトを各ワード当り１ビツト
としているため、当該ワードをメモリに格納して
いないことを示す意味付けは１通りしかなく、全
ビツト白データあるいは全ビツト黒データのう
ち、いずれか一方のみが圧縮対象となる。したが
つて、大部分が白データあるいは黒データのいず
れかに限られる場合には、大きな圧縮効果を期待
できるが、白データおよび黒データのいずれも混
在する場合はどちらであるか判別できない。そこ
で、白データおよび黒データのいずれも圧縮対象
とする必要がある場合には、フラグ・ビツトを各
ワード当り２ビツトとし、当該ワードを格納しな
いとき白データが黒データかを区別できるように
する方法が考えられる。しかし、これでは圧縮効
果がフラグ・ビツトの増加分だけ減ることにな
る。したがつて、第３のポイントを、メモリに格
納しないことを判定する条件として直前のワード
との比較結果によることにするのである。例え
ば、直前のワードと同一内容の場合には、格納し
ないことにしてフラグ・ビツトを増加することな
く、白データおよび黒データの両方を圧縮対象に
することが可能となる。

格納を省略する判定条件としての比較対象は、
直前のワードの全ビツトとするか、または以下の
実施例で示すように直前のワードの最後のビツト
の内容とするか、あるいは直前のワードの内容で
白か黒のビツト数が多い方とする等種々の方法が
考えられるが、いずれの場合も復号化の際は、フ
ラグ・ビツトがメモリに格納されていないことを
示す場合は、直前のワードの内容を参照すればよ
い。なお、スキヤンの先頭等、直前のワードを定
義できない場合では、あらかじめ白または黒のい
ずれかに初期値を決めておけば良い。本発明の圧
縮方式によれば、仮にワードを構成するビツト数
を16、フラグ・ビツトを１ビツトとすれば、圧縮
効果の出ない最悪パターンにおいても、データ量
は16＋１／16＝1.0625倍にしかならず、MHコード の4.5倍に比較すると大幅に改善され、最悪パタ
ーン取込みのためスループツトを上げなければな
らない等の問題点を解消できる。一方、最大圧縮
率について見ると、MHコードでは約100倍であ
るのに対し、本方式では前記の例で16／１＝16倍と なり、ワードを構成するビツト数を増さない限
り、それ程大きい圧縮率とはならないが、確実な
圧縮効果を期待できる。また、パターン格納用の
メモリ容量は、想定される最大データ量を含む紙
葉をカバーするように決められなければならない
ことを考慮すると、本方式によつても用意される
べきメモリ容量は従来のMHコード等に比較して
同程度となり、実質的なメモリ削減効果は殆んど
変わらない。

なお、ワードのビツト数を決定する場合には、
圧縮対象のパターンの特性に合わせて最適な値に
決めるようにすることが望ましい。

〔発明の実施例〕

以下、本発明の一実施例を図面により説明す
る。

第１図は、本発明を適用した光学文字読取り装
置のブロツク図である。

第１図において、１は紙票、２はセンサ、３は
２値化回路、４は符号化回路、５はメモリ、６は
プロセツサ、７は表示装置、８は出力装置、９は
紙送り機構である。

プロセツサ６の指令により、紙送り機構９は、
紙票１を搬送する。搬送された紙票１上の画像デ
ータは、センサ２によつて光電変換され、２値化
回路３で２値化された空、符号化回路４によつて
データ圧縮され、メモリ５に格納される。プロセ
ツサ６は、メモリ５に格納された画像データを順
次復号化処理し、文字部分を切出し、認識処理し
て、認識結果を表示装置７に表示あるいは、出力
装置８に出力する。

第２図は第１図の符号化回路の具体例図であ
る。

第２図において、４０１はＤタイプ・フリツ
プ・フロツプ、４０２は排他的論理和ゲート、４
０３はJKタイプ・フリツプ・プロツプ、４０４，
４０５はシフト・レジスタ、４０６，４１２はマ
ルチプレクサ、４０７，４０９はカウンタ、４１
０，４１１はアドレス・カウンタ、４０８は非圧
縮モード・スイツチ、４１３は書込み制御回路で
ある。

２値化回路３で２値化されたデータ４２１は、
シフト・レジスタ４０４でクロツク４２２により
ｎビツトシフトされ、ｎビツトのワード・データ
に変換される。一方、２値化データ４２１は、シ
フト・レジスタ４０４で変換されるワードの直前
のワードの最終ビツトを記憶したフリツプ・フロ
ツプ４０１の出力と排他的論理和ゲート４０２で
比較されて、ワード・データ中で１ビツトでも不
一致があつた場合、フリツプ・フロツプ４０３が
セツトされる。このセツトで、フラグ・ビツトが
立つたことになる。なお、フリツプ・フロツプ４
０１は、各スキヤンの先頭では直前のデータがな
いため、あらかじめ初期化しておき、セツトまた
はリセツト出力を供給する。

カウンタ４０７は、シフト・レジスタ４０４の
シフト回数を計数するカウンタであつて、シフ
ト・レジスタ４０４がｎビツト・シフトされたと
き、カウンタ４０７の出力が“１”となり、この
出力“１”をシフト・レジスタ４０５の端子Ｔに
送つて、フリツプ・フロツプ４０３の内容をシフ
ト・レジスタ４０５にシフトさせるための同期信
号とする。フリツプ・フロツプ４０３の内容がシ
フトされると、次のワード・データとのために、
２値化データ４２１の２ビツト目の内容をフリツ
プ・フロツプ４０１にセツトしておく。シフト・
レジスタ４０５にフリツプ・フロツプ４０３の内
容をシフトするとき、その内容が“１”であれ
ば、あらかじめ設定されたアドレス・カウンタ４
１０にカウント・アツプのための信号を送ると同
時に、メモリ５にデータを格納するため、メモリ
書込み制御回路４１３に書込み信号を送る。

書込み制御回路４１３は、フリツプ・フロツプ
４０３から書込み信号を受けると、マルチプレク
サ４０６と４１２と制御してカウンタ４１０の内
容をアドレスとし、シフト・レジスタ４０４の内
容をデータとして、メモリ５にこれらを送出し格
納する。アドレス・カウンタ４１０は、データ格
納終了後、フリツプ・フロツプ４０３から受け取
つたカウント・アツプ信号によりトリガされ、内
容にプラス１する。

なお、フリツプ・フロツプ４０３の内容が
“０”であれば、書込み信号が出力されないため、
パターン・データはメモリ５には格納されない。
また、カウンタ４０９は、シフト・レジスタ４０
５のシフト回数を計数するカウンタであり、シフ
ト・レジスタ４０５がｎビツト・シフトされたと
き、あらかじめ設定されたアドレス・カウンタ４
１１にカウント・アツプのための信号を送ると同
時に、メモリ５に格納するため、メモリ書込み制
御回路４１３に書込み信号を送る。書込み制御回
路４１３は、カウンタ４０９から書込み信号を受
け取ると、マルチプレクサ４０６，４１２を制御
して、カウンタ４１１の内容をアドレスとし、シ
フト・レジスタ４０５の内容をデータとして、メ
モリ５に格納する。これにより、ｎビツト（１ワ
ード）分のフラグ・ビツトがメモリ５に格納され
る。アドレス・カウンタ４１１はメモリ５への格
納終了後、カウンタ４０９から送られるカウン
ト・アツプ信号によりトリガされて、内容をプラ
ス１する。

なお、第２図では、各スキヤンの先頭でフリツ
プ・フロツプ４０３をセツトしているが、逆にリ
セツトさせてもよいし、また符号化の最初のスキ
ヤンすなわち第１番目の走査のみでセツトあるい
はリセツトさせるようにしてもよい。

第３図および第４図は、それぞれメモリに格納
される符号化データの説明図である。

第３図では、シフト・レジスタ４０４，４０５
をそれぞれ４ビツト、アドレス・カウンタ４１０
の初期値を（00）₁₆、アドレス・カウンタ４１１
の初期値を（100）₁₆、各スキヤンの先頭ビツト10
（フリツプ・フロツプ４０１の各スキヤンの初期
値）を“１”とし、各スキヤンの２値化入力デー
タ１１Ａ〜１３Ａに対するメモリ５に格納される
データを示す。図中、１１Ｂ〜１３Ｂは、２値化
入力データ１１Ａ〜１３Ａに対するフラグ・ビツ
トを示す。パターン・データ１４は、フラグ・ビ
ツトが“１”の部分のデータのみ格納されたもの
であり、またマツプ・データ１５は、フラグ・ビ
ツトが格納されたものである。すなわち入力デー
タ１１Ａでは、直前の４ビツトの最終ビツト10と
比較して、同一の４ビツトであるため記憶せず、
フラグ・ビツト“０”とし、次の４ビツト・パタ
ーン“1010”はテーブル１４のアドレス（00）₁₆
に格納する。次のデータはオール“０”のため記
憶せず、その次のデータのパターン“0101”はテ
ーブル１４のアドレス（01）₁₆に格納する。入力
データ１２Ａでは、直前の４ビツトの最終ビツト
10と比較して異なる４ビツトであるため、オール
“０”であつてもテーブル１４のアドレス（03）₁₆
に格納する。このように、メモリ５のテーブル１
４上にフラグ・ビツト“１”に対応するパター
ン・データのみが格納され、またテーブル１５に
は４ビツトずつ区切つてフラグ・ビツトのマツ
プ・データが格納される。

また、第３図において、パターン・データ１４
の容量は、２値化入力データ４２１の内容によ
り、圧縮されたり、圧縮されなかつたりして可変
となるので、任意のスキヤン位置からの復号化が
出来ない。そこで、第４図に示すように、アドレ
ス・カウンタ４１０の内容をマルチプレクサ４０
６で選択出来るようにし、各スキヤンに１回、ア
ドレス・カウンタ４１１をアドレスとし、アドレ
ス・カウンタ４１０の内容をデータとしてメモリ
５に格納するようにすれば、パターン・データ格
納アドレスが任意のスキヤン位置で分かるように
なり、復号化を任意のスキヤン位置から行えるよ
うにできる。第４図にその場合のメモリ５のマツ
プ・データを示す。第４図のテーブル１６では、
マツプ・データの最初の４つのフラグ・ビツトに
対応するパターン・データの先頭アドレスがアド
レス“0000”＝（00）₁₆に格納されており、次の４
つのフラグ・ビツトに対応するパターン・データ
の先頭アドレスもアドレス“0000”＝（00）₁₆に格
納されていることが判る。また、任意のスキヤン
位置であるデータ１３Ａの最後の４ビツト・パタ
ーンは、アドレス“0101”＝（05）₁₆に格納されて
いることが判る。

第５図は、本発明のおける圧縮対象領域を示す
図である。

第５図に示す点線内のみがメモリ５に記憶さ
れ、それ以外は圧縮されることを表している。す
なわち紙票上の枠線と数字、アルフアベツトのみ
の符号を記憶するのみでよく、背景の黒と紙票中
の余白は記憶されないため、メモリ容量は少なく
てよい。

また、第２図において、プログラムで切替可能
なモードスイツチ４０８を設け、アドレス・カウ
ンタ４０３のセツト端子およびカウンタ４０９の
リセツト端子に接続することにより、マツプ・デ
ータはメモリ５に格納せず、パターン・データは
常に格納するようにできるため、大形紙葉用にメ
モリ５の容量が設定された装置において、小形紙
葉など画像データ量が少ない場合は、２値化入力
データ４２１をそのままワード・データに変換だ
け行つて、メモリ５に格納するようにすれば、復
号化処理が不要となり高速化することができる。

なお、本発明は、紙葉上からのパターン・デー
タにその適用が限定されるものではなく、広く一
般のパターン・データを圧縮する方法として利用
できるものである。

〔発明の効果〕

以上説明したように、本発明によれば、符号
化、復号化処理を簡単かつ安価な回路で構成で
き、かち復元が容易であり、また最悪パターンに
対してデータが逆に増加することがないため、パ
ターンを格納するメモリ容量を削減することがで
きる。また、全ビツト黒パターンおよび全ビツト
白パターンとも圧縮されるため、帳票背景部が黒
の装置でも、背景の黒と帳票上の白を圧縮でき
る。したがつて、紙葉上の大部分ないし全面のパ
ターン・データを扱う画像入力装置あるいは光学
文字読取装置に適用すれば、その効果は大であ
る。

【図面の簡単な説明】

第１図は本発明を適用した光学文字読取り装置
のブロツク図、第２図は第１図の符号化回路の具
体例図、第３図、第４図はメモリに格納される符
号化データの説明図、第５図は本発明における圧
縮対象領域を示す帳票の図である。 １：紙票、２：センサ、３：２値化回路、４：
符号化回路、５：メモリ、６：プロセツサ、７：
表示装置、８：出力装置、９：紙送り機構、４０
１：Ｄタイプ・フリツプ・フロツプ、４０２：排
他的論理和ゲート、４０３：JKタイプ・フリツ
プ・フロツプ、４０４，４０５：シフト・レジス
タ、４０６，４１２：マルチプレクサ、４０７，
４０９：カウンタ、４１０，４１１：アドレス・
カウンタ、４１３：書込み制御回路。

Claims (1)

【特許請求の範囲】
1. １ 時系列の２値画像信号を複数ビツト単位のワ
   ード・データに分割して、メモリに格納する場
   合、上記ワード・データの全ビツトが白または黒
   のとき以外はメモリに格納するが、全ビツトが白
   または黒のときには、該ワード・データの直前の
   ワード・データの内容と比較した結果により、メ
   モリに格納するか否かを決定し、かつ各ワード・
   データごとに、当該ワード・データがメモリに格
   納されているか否かを示すフラグ・ビツトを発生
   して、該フラグ・ビツトもメモリに格納すること
   を特徴とする画像情報圧縮方式。