JPH03165181A

JPH03165181A - ２進テキスト画像の高品質圧縮法

Info

Publication number: JPH03165181A
Application number: JP2177224A
Authority: JP
Inventors: Dan S Chevion; ダン、シムエル、シェビオン; Ehud D Karnin; エフド、ドブ、カーニン; Eugeniusz Walach; ユージニウス、ワラハ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1989-08-04
Filing date: 1990-07-04
Publication date: 1991-07-17
Anticipated expiration: 2011-09-04
Also published as: JP2531840B2; EP0411232A2; IL91221A0; CA2019133C; CA2019133A1; DE68925281D1; DE68925281T2; ES2081859T3; EP0411232B1; US5204756A; EP0411232A3; IL91221A

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、特に、画像がテキストを含む、すなわち、黒
の領域または白の領域だけを含む場合に、２進画像情報
を圧縮する方法に関するものである。

したがって、本発明は、印刷された文書または手書きの
文書で提供された情報の電子的処理に応用できる。この
場合には、種々の処理過程が実行されている間の情報の
記憶と、将来の参照または検索あるいはデータリンクを
介しての伝送のための保管のために、スペースの問題と
時間の問題の少なくとも１つが起る。

〔従来の技術〕

紙に記載されている文書の取扱いは、現代の事務所の環
境にお１ｊる日常業務である。文書に用いる紙の製造に
必要な自然資源と、文書の目的を果させるために文書を
作成および取扱う速さと、文書の記憶および後日の検索
とに対して注意して払わねばならない考慮のために、回
覧される文書の数を減少させ、文書を伴う作業を自動記
録取扱い装置にゆだねるための努力をする結果となって
きた。文書の物理的な取扱いはこれに関連する１つの重
要な面であり、そしておそらくはより重要な別の面は、
文書に含まれている情報の処理である。

文書に含まれている情報の処理は、一般にある読取り装
置による情報の獲得と、得た情報の機械読取り可能なコ
ードへの変換と、後日のためのコード化された情報の記
憶と、おそらくは繰返される処理と、情報の実際の処理
と、最後に処理結果の出力とを含む。その出力は表示装
置における硯宛的な態様、または印字、あるいは純粋に
電子的な態様をとることができる。

光走査器のような読取り装置による情報の獲得は、情報
が多重化されたり、部分的に失われたりするようになら
ないように、合理的に高い分解能で行うべきである。し
たがって、読取り装置は大量の走査データを発生する。

そのために記憶用に大きな記憶容量を必要とする。典型
的な例として、１００ベル／ｃｍ（ここに、「ベル」と
いうのは画素を意味し、白または黒のドツトである）の
ページは約７００にバイトの記憶空間を要する。がなり
適度な数、例えば数千、の文書でも法外に大容量メモリ
を要する。

この問題を軽減するために、従来の文書走査装置にはデ
ータ圧縮ルーチンが設けられる。走査されるＡ４ページ
の圧縮されたデータは、もちろん走査されるページの内
容に応じて、２５〜７５にバイトの記憶空間に納めるこ
とができるように、それらのルーチンはほぼ１桁の大き
さを節約する。算術的コード化を基にした非常に賢いア
ルゴリズムは約１６％更に減少できる。たとえば、アー
ル・アープス（Ｒ，Ａｒｐｓ）　、ティー・フリートマ
ン（Ｔ、Ｐｒｉｅｄｍａｎ）、ジー・ラングトン（Ｇ、
Ｒａｎｇｒｌｏｎ）、およびティー・トウルオング（Ｔ
、Ｔｒｕｏｎｇ）著「最適２進画像圧縮：チップの現状
および応用（＾ｄａｐｔｌｖｅ　Ｂｉｎａｒｙ　ＩＩＩ
ａｇｅ　Ｃｏｌｌ１ｐｒｅｓｓｉｏｎ：ＣｈｉｐＳｔａ
ｔｕｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ）Ｊイメー
ジ・アイティーエル（ＩＩＩｌａｇｅ　ＩＴＬ）　、１
９８６年５月、をづ照されたい。

情報を処理するにせよ、出力するにせよ、どのような圧
縮装置も情報の圧縮を後で元に戻すことができるという
ものでなければならないことはいうまでもない。圧縮や
圧縮したものを元に反すことをある程度の情報の損失を
もって、すなわち品質の低下を伴って行うことができる
かどぅがは、出力を必要とする目的と、元の画像に含ま
れている冗長性とに依存する。

例えば、国勢調査に関連するような、非常に大量の文書
を取扱わねばならないいくっがの用途においては、圧縮
比をそれの限度まで、少なくとももう１桁、高くするこ
とが重要である。

この問題に対する１つの可能な技術が、アイイーイーイ
ー会報（Ｐｒｏｃ、　ＩＥＥＥ）（ｉ８巻７号、１９８
０年７月号、所載のダブりニー・ケー・ブラット（ｗ。

Ｋ、Ｐｒａｔｔ）、ビー・ジェー・キャピタント（Ｐ、
Ｊ。

Ｃａｐｉｔａｎｔ）　、ダブりニー・チェン（ｗ、Ｃｈ
ｃｎ）、イー・アール・ハミルトン（Ｅ、Ｒ，Ｈａｍｉ
　ｌ　ｔｏｎ）、アール・エイチ・ウォリス（１？、Ｈ
，νａｔ　Ｉ　＋Ｓ）による「組合わせ記号一致ファク
シミリデータ圧縮装置（Ｃｏｍｂｉｎｅｄ　Ｓｙｍｂｏ
ｌ　Ｍａｔｃｌ＋ｉｎｇ　ＦａｃｓｉｒＡｉｌｅ　Ｄａ
ｔａ　Ｃｏ−ｍｐｒｅｓｓｉｏｉ　５ｙｓｔｅ）　Ｊ　
ｌこ＝己載されている。その論文においては、２進画像
を文字一致プロセスへ供給することが提案されている。

認識された文字はそれらの文字の英数字態様により非常
に効率的に表される。それから残っている情報が通常の
２進画像として別々に圧縮される。そうすると圧縮比が
約２倍になるが、この技術の効率は認識される文字の百
分比とデジタル化ノイズの程度とに大きく依存する。

ブリックマン（ＢｒｌｅｋＩＷａｎ）他へ付与された米
国特許第４．４９９．４９９号に改良技術が開示されて
いる。

その技術では、１１１−文字認識の代りに、テキスト中
の個々の語のような大きな記号の一致が考えられいる。

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

しかし、この技術はファクシミリ記号、または語、のア
ドレス可能なライブラリィを記憶することを必要とし、
そのライブラリィ中に認められない語に対しては作動し
ない。

本発明の目的は、従来の圧縮法により達成されるものよ
りもかなり高い圧縮比で画像データを圧縮する方法を提
案することである。

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

本発明の方法は、無損失圧縮、すなわち、元の情報の正
確な再構成を行えるようにする圧縮、に固執するならば
、それを達成できないという認識を基にしている。実際
に、テキスト画像を含む多数の実用的な応用においては
、無損失圧縮は重要ではない。主観的には元のテキスト
と区別できない読みやすいテキストを有するだけで十分
である。

これの試行的なやり方は走査の解像力を低くすることで
ある。実際に、従来の走査器およびファクシミリ装置の
多くはこの選択を行えるようにしている。しかし、大き
な手書きテキストのようなある種の画像に対してはこの
やり方を行えるかもしれないが、小さい印字を含んでい
るテキストのような別の種類のテキストには受は容れら
れないことを意味する。中間・」法のテキストに対して
も、解像力をｌｉｔに匹くすると使用者を悩ませる画ｊ
象の質の低下を招く。

これとは対照的に、本発明は、許容できる「白゛損失」
コード化により、および再生品質の維持に重要である「
無損失」コード化により、全体的に高い圧縮比を特徴と
する方法によりその問題を解決するものである。したが
って、この提案は、近い将来の２進画像の性質の評価に
依存する可変圧縮比の使用を含み、有損失圧縮は大きな
低周波区域に限られる（この場合には質の低下は主観的
には気づくことがなく、小さい高周波区域は無損失で圧
縮される）。

本発明の方法はさらに１ステップ進む。有損失圧縮がｉ
′ｊＪ能であることが見出だされる区域においてさえも
、それは無差別に適用されるものではない。その代りに
、使用すべき圧縮比は特定の各場合に、全体的な優れた
画像品質を保証するために、線の連続性と滑らかさを保
持するようにされる。

本発明を要約すれば次の通りである。すなわち、まず、
本発明は２進テキスト画像の圧縮および圧縮解除のため
の方法に関するものである。

この方法は元のフレーム中で大きい低周波区域と小さい
高周波区域を忠別する。低周波区域に対しては、有損失
圧縮のためのスキームが用いられるのに対して、高周波
区域に対しては、無損失圧縮を許すスキームが適用され
る。圧縮／圧縮解除法は次の５つの段階を含む。

１、全ての黒バッチを除去するために前フィルタリング
段階（たとえば、大きくて黒いセグメントに属する場合
を除き、全ての黒い画素を除去することにより）。

２、画像を相互に排他的なセグメントに区画し、かつ種
々の圧縮モードを各セグメントに適用することによる圧
縮可能性の高速評価。

３８水平方向と垂直力向における解像力を低くするため
の連続性−指向サブサンプリング。画像はブロックに区
分され、各ブロックのための１画素表現が決定される。

４、減少させられたファイルが通常の技術により圧縮さ
れるような無損失圧縮および圧縮解除。

５、順序の逆転による再構成。無損失圧縮解除はサブサ
ンプルされたファイルを検索する。等しい値を有するブ
ロックにより各画素を交換することにより、サブサンプ
ルされたファイルの拡張、後フィルタリング。

〔実施例〕

以下、図面を参照して実施例により本発明を説明する。

本発明の方法は次の５つの過程を本質的に有する。すな
わち、前フィルタリング、圧縮可能性の評価、連結性指
向サブサンプリング、無損失圧縮および無損失圧縮解除
、および再構成、がそれである。それらの各過程につい
ては以下に詳しく説明する。

１、前フィルタリング圧縮可能性の実際の評価の前に、ノイズの走査から、ま
たは文書の背景が一様でないことから生ずることがある
全ての小さい余分な黒バッチを除去することにより、走
査データを「きれいに」せねばならない。使用できるフ
ィルタには多種多様のものを入手できる。アイビーエム
・リサーチ・レポート（ＩＢＭ　Ｒｅ５ｅａｒｃｈ　Ｒ
ｅｐｏｒｔ）ＲＪ４１５Ｂ　、　１９８４年１１月所載
のティー・キモトおよびアール・ジー・ケージ−（Ｒ，
Ｇ、Ｃａ５ｃｙ）による「２進画像中の水平線パターン
と垂直線パターンのための縁部を清らかにするアルゴリ
ズム（Ｅｄｇｅ　Ｓａ＋ｏｏｔｈ１ｎｇ　Ａｌｇｏ−ｒ
ｉｔｈｍｓ　ｆｏｒ　Ｈｏｒｉｚｏｎｔａｌ　ａｎｄ　
Ｖｃｒｔｌｃａｌ　ＬｉｎｅＰａｔｔｅｒｎｓ　Ｉｎ　
Ｂｉｎａｒｙ　Ｉｍａｇｅｓ）Ｊと、上記アイビーエム
・リサーチ・レポート、ＲＺ１４３８．１９８５年１２
月、所載のエフ・エム・ワール（Ｐ、Ｍ、Ｗａｈｌ）に
よる［文書品質向上およびデータ圧縮のための２進画像
プロセッサ（Ａ　Ｂｉｎａｒｙ　Ｉｍａｇｅ　Ｐｒｏｃ
ｅｓｓｏｒ　ｆ’ｏｒＤｏｃｕｍｅｎＬ　Ｑｕａｌｉｔ
ｙ　ＩｗｐｒＯＶｅｌｅｎｔ　ａｎｄ　ＤａｔａＲｅｄ
ｕｃｔ　Ｉｏｎ）　Ｊを参照する。

フィルタの最適な選択は特定の用途の文字と、計算力の
利用可能性とに依存する。高速で、広範囲な実際的用途
に効果的である１つの好ましいフィルタは、大きな黒い
セグメントに属しているピクセル（ビクセルとは画素の
ことである）、そのセグメントに隣接する画素とを除き
、全ての黒い画素を２進画像から除去するという原理で
作動する。この文脈における大きいセグメントとは水・
１之または垂直の行中の連続する３個の黒い画素として
定義される。下記の情報パターン（アレイ１）．．．１
１１１１１１１１１１１１１．．．．．．．．．．．．
．．．．．．．、、．１．、、。

．．．、、１．．．．．．．．１１１．．．．．．．．
１１．．．．、．１．．．．．１．、、。

．．．．．．．．．．．．、、１１１．．．．．．．、
、．１．．．．．１．．．．．１．、、。

．．．．．．．．．．．．、１．ｌ１１．．．．．．．
．．．．．．．．．．．．、．１．、、。

がそのフィルタを通されるものとすると、結果は次の通
り（アレイ２）となる。

．．．１１１１１１１１１１１１１．．．．．．．．．．．．．１１１．．．．．．．．．．．．、Ｉ！１．．．．．．．．．．．．．１１１１１．．．。

１．．．。

明らかに、このフィルタリング過程の結果として、人の
視覚がノイズと解釈する傾向がある小さい特徴が消える
。それと同時に、書かれた文字は、それが１画素幅だけ
であっても、そのまま残る。

このやり方の効率の例として第１図と第２図を参照する
。第１図は色の付いた点の拡散された格子により構成さ
れ、色の付いた背景を有する元の形態のコピーである。

走査後は、色の付いた背景から出た多量のノイズがオー
バーロードされる。

このノイズはもちろん主観的には煩しいものではあるが
、貴重な記憶空間を大きく使うとともに、効率的な圧縮
を妨げる。走査データを上記のような諸特性を有するフ
ィルタを通すとフィルタリングされたデータから発生さ
れた再構成である第２図により示すように、背景ノイズ
はデータから消失する。

上記フィルタは白い背景上の小さな黒いバッチだけを除
去するために構成されていると仮定したが、通常は黒の
線素子上の白色ノイズのような、黒い背景上の小さな白
いバッチを除去するために類似のフィルタを製作するこ
とができる。黒いノイズ区域と、白いノイズ区域を取扱
うことができるように、両方の種類のフィルタを直列に
することも好ましい。

２、圧縮可能度の評価もちろん、処理時間を短縮し、記憶空間を節約するため
に、走査される２進テキスト画像を表すデータの全てに
有損失圧縮を加えることが好ましい。しかし、どの２進
画像も情報密度の高い区域と、情報内容が少ない他の区
域とを有する。したがって、有損失圧縮は、高密度情報
に加えられると、その情報の了解度を低下させることに
なることが避けられない。したがって、本発明の方法は
、情報のうち、了解度が気がつくほど低下する危険のな
い部分だけに有損失圧縮を加えようとする。

したがって、比較的幅広の線で文字が書かれ、語間隔が
広い低周波だけに加えるべきである。

そのために、画像は相互に排他的なセグメントに区画さ
れ、各セグメントに個々の圧縮比が割当てられる。その
区画操作は、もちろん統＝１的な圧縮＝［画がいぜんと
して合意であるような最小のセグメントを持ちたいとい
う希望により、もちろん支配される任意のやり方で行う
ことができる。

この作業は、画像と、データアレイのテキストセグメン
トとの間の違いに類似する。そのために、アイビーエム
−ジャーナル・オブ・リサーチ・アンド争ディベロップ
メント（ＩＢＭ　Ｊｏｕｒｎａｌ　ｏｆ　Ｒｅ−５ｅａ
ｒｃｈ　＆　Ｄｃｖｃｌｏｐｍｃｎｔ）　、１１巻、１
９８２年１１月号、６４７〜６５６ページ所載のケー・
ワイ・ワンプ（Ｋ。

Ｙ、　Ｗｏｎｇ）、アール・ジー・ケージ−（Ｒ，Ｇ、
Ｃａ５ｅｙ）、エフ・エム・ワール（Ｆ、Ｍ、Ｗａｈｌ
）による「文書解析装置（Ｄｏｃｕｍｅｎｔ　Ａｎａｌ
ｙｓｉｓ　Ｓｙｓｔｅｍ）Ｊにより提案が行われている
。しかし、本発明が取組む問題の特定の性質は、この参
考文献において提案されているものとは全く異なる解決
法を要求する。

有損失圧縮の実行のｉｌ能性が、元のテキスト画像中の
白と黒の間隔の幅に依存することが当業者には明らかで
あろう。したがって、それらの間隔の相対的な幅の定量
的な測定を行う必要があり、それをこえると弁別が始ま
るようなしきい値を絶対幅が支配する、互いに代替的な
２つのやり方を考えることができる。

ａ９画素をベースとするやりｈ゛この考えは、画像を線ごとに走査し、各ブロックに対し
て、全ての黒の白の間隔の平均長さを決定することであ
る。簡単にするために、以下の説明においては、連続す
る２本の線が１つのブロックを常に構成すると仮定する
。当然、ページの広い余白のような大きい黒または白の
区域の存在が圧縮の決定にインパクトを与えるべきでは
ない。

次に、第３図の流れ図を参照して区画作業を説明する。

それの最初の過程においては、この作業により、ｍおよ
びｎで表されるレジスタのクリヤされていることを確認
する。それらのレジスタが単に、たとえば、２個の整数
を格納する主メモリ中の２つの場所とすることができる
。それから、評価中のセグメントの終りに既に達したか
どうかを判定する。達したならば、ｎの値を調べるため
に分岐を行う。それが所定のしきい値ｎ　Ｌ　％だとえ
ば、５、をこえたとすると、新しいセグメントをアドレ
ス指定する。また、ｎがそのしきい値をこえなければ、
遮断されない長さＷを決定するために、新しい一連の黒
（１）または白（０）を考慮に入れる。

次に、長さＷがしきい値Ｗｔをこえたかどうかについて
調べる。本発明の一実施例においてはしきい値ｗ＝１２
が適切であることが判明している。

しきい値を超えているときは新しい側流が宣言される。

その調べの結果が否定であるとｎの値を１だけ増加し、
ｍの値をＷだけ増加する。セグメントの終りになるまで
この処理を続ける。ｎがしきい値　ｎｔよりいぜんとし
て小さいとすると、そのセグメントに対して有損失圧縮
を行う。ｎがｎ　より大きいと、ｒｎ／　ｎ　＞　（ｍ／　ｎ　）　ｔの時だけ有損失圧縮を行う。これはたとえば４にセット
できる。

上記しきい値のような設計パラメータの選択は経験上の
問題であることに注目すべきである。ここに示す値は経
験的に決定したが、それらの値は限定的なものであるこ
とを決して意味するものではない。圧縮される区域の分
担を増加または減少して、画像の品質と希望の圧縮度の
間のトレードオフを選択するために、その値は必要に応
じて変えることができる。

ｂ、バイトをベースとするやり方上の１）において概略を述べた画素をベースとするやり
方は非常に良く機能するが、ある状況の下では計算が面
倒であることが判明することがある。これは、画素をよ
り大きい「包含（Ｃｏｎｔａｉｎ−ｍｅｎｔ）　Ｊに詰
め込み、または詰め直しすることにより改善される。実
際に、多くの実際的用途においては、画像データはバイ
トモードで詰められる。

なお、１バイトは連続する８個の画素を表す。したがっ
て、黒間隔と白間隔の全ての間隔の長さを計算するため
にデータを「通常の」ラスタモードへ翻訳するためには
かなりの時間を要する。ここに、「通常の」というのは
、各画素へ１つの数が割当てられることを意味する。し
たがって、画素値に対して算術演算を行わねばならない
とすると、各バイトを対応する８個の画素値へまず変換
せねばならない。これは、たとえば、可能な各バイト値
に１つずつの２５６個の入口と、各画素に１つずつの８
個の出口ボートとを有する探索表を用いることにより行
うことができる。

好適な手順は次の４つの過程を含む。

１）非零バイトの数ｍをまず＝！算する。

２）各バイトを２進数へ変換する。与えられたバイトが
小さい黒または白のランを含んでいるならば、その２進
数は１に等しく、他の全ての場合にはそれは０に等しい
。あるバイトが００００００００または＋１１１１１１
１に等しくなく、それと同時に、そのバイトの最初の画
素が最後の画素に等しいとすると、そのバイトがそのよ
うに小さくて黒い、または白いランを実際に含んでいる
と判定される。

３）連続する「１」対の数ｎを：（算する。

４）ｎがある所定のしきい＠（たとえば３とすることが
できる）より小さいか、ｍの与えられた部分（たとえば
５％以下）より小さいとすると、有損失圧縮を行う。そ
のしきい値と、部分とは特定の用途に依存し、実験的に
決定すべきである。

水１シ距離と垂直距離は一般に同程度の大きさであるが
、ある場合には前記試験を元の画像の変換されたものに
対して行うことが有利なことがある。

それから垂直距離について考える。さらに、元の画像の
正規なものと変換されたものの組合わせから圧縮可能性
の基準を発生することが有用かもしれないが、行ワた実
験によれば、はとんどの実際的な場合には、上記のよう
に、水を距離について考えるだけで十分である。

連続する２本の線を同時に試験することが有用なことが
あることにも注目すべきである。この場合には、短いラ
ンの長さが連続する２つの間隔のうちの大きい方である
と定義される。その結果、１画素幅ノイズの衝撃は和ら
げられる。これは、とくに、画素が線の縁部にある時に
そうである。

それから１または０値を得ることができる。したがって
、直線の縁部において走査ノイズの１画素層を見ること
ができる。もちろん、これは可能なノイズの影響にであ
るばかりでなく、圧縮度試験の観点から非常に重要でも
ある。

たとえば、次の長い水平線について考えてみる（アレイ
３）。

０００００００００００００００００００００００００
０００００００００００００００００００００００００
００００００００００００００００００００００１１０
００００１１１１１０００００１１１１０００００１０
１０１０１１１１１１１１１．１１１１１１１１１１１
０１１１１１．１１１１１１１１１１１１１１１１１１
１１１１１１１１１１１１．１．１１１１１１］１１１
．１１１０１００００１１０００１０１０１０１０１０
０００１１１１１１１１１０００００００００００００
００００００００００００００００００００００００明
らかに、画像の質の識別可能な低下なしにそれを有損失
圧縮できるが、縁部（１番上から３番目と６番目の線）
においては多数の黒と白の列が、この区域は圧縮できな
いと判定させることがある。

３、連結性指向のサブサンプリング元の画像の連結性指向のサブサンプリングにおいては、
目的は水平方向と垂直方向の解像力をある係数だけ低ド
させることである。その係数を２と選択したとすると、
画像を２×２のブロックに区画しなければならなくなり
、各ブロックに対して１画素表現を出さねばならない。

黒い画素の数が２個未満のブロックは白と見なされる。

それらのブロックの平均的な表現値は０である。３個以
上の黒い画素を有するブロックは黒と考えられ、それら
のブロックの平均的な表現値は１である。問題は、黒い
画素がちょうど２個有するブロックに対する最も適切な
判断は何かということである。１つの明らかなやり方は
、ある任意の判定モードを用いることである。たとえば
、「問題の」ブロックには常に０または１が割当てられ
る。不幸なことに、そのやり方を採用したとすると、全
ての細い（１画素幅）の線を消失させるか、もともとば
らばらの何本かの線を一緒にするかである。いずれにし
ても、画像の質の劣化は受は容れられない。

好適なやり方は各「問題のコブロックの附近の考慮を基
にしている。このスキームの下においては、黒い画素を
２個Ｈする各ブロックに値０が割当てられる。ただし、
そのような割当てが２本の線の連結を破るような場合を
除く。この最後の場合には、割当ては１へ切換えられる
。そのような割当て計画の１つの可能な例が書きの繰返
し手続きである（解像力の低下係数は２であると、いぜ
んとして仮定する）。

８２元の２進画像アレイＯを相互に排他的な２×２のブ
ロックに区分する。

ｂ、０のブロックに対応する全ての画素を１にセットす
ることにより最後のアレイＯ（すなわち、解像力の低い
もの）を構成する。

Ｃ１黒い画素をちょうど２個有する各ブロックに対して
、元のアレイＯをブロックごとに横切る。下に示すよう
に近くの全ての画素（アレイＯ中の）にＡ−Ｈの名称を
つけ、考察中の画素にはｒＸＪという名称をつける（ア
レイ４）。

ＢＣＸＥＧＨＣ１ｆ。

Ｂ−Ｄ−Ｅ−Ｇ−１であれば、Ｘは黒い背景上に狭い開
口部を構成する。したがって、ＸはＯにセットされ、考
察をＯの次の画素へ（またはＯの対応するブロックへ）
移す。

Ｄ−Ｅ−０で、０中にＢから６への連結が存在するもの
とすると、Ｘを１にセットし、ド記の次の試験を行う。

ＢとＧの間の連結の存在は、考察中のブロックに属する
画素と、それに最も近い８個と、すなわち、上記計画中
のブロックに属する画素、で構成されている６Ｘ６のア
レイをＯから取出すことにより設定される。Ｔの各線が
黒い画素を少なくとも１個白°するならば、定義ごとに
連結は存在する。

ｇ、Ｂ−Ｇ−０で、０中にＤとＥの間の連結が存在する
ものとすれば、Ｘを１にセットし、計画は下記の次の試
験へ進む。

前の段階で定められたアレイＴを考察することにより、
ＤとＥの間の連結の存在が設定される。Ｔの各列が黒い
画素を少なくとも１個何するならばその連結は存在する
。

ｈ、プロセスのこの段階においては３つだけ可能性が残
る。画素Ｂ、ＤＳＥ、Ｇのうちに１個、２個、または３
個の黒い画素がある。それらの各場合に対して、判定論
理は次の通りである。

１）Ｂ、Ｄ、ＥＳＣのうちには正確に１個の黒い画素が
ある場合。

この場合は、比較的太い線の縁部上にある画素に主とし
て適用できる。したがって、任意の決定モードを適用で
きる。しかし、線の幅を保持するために、左と上の方向
から来る線に対してＸはＸ−１を選択し、右と下から来
る線に対してはＸ−０を選択した。したがって、ａ）Ｂ−１およびＤ−Ｇ−０ならば、Ｘを１にセットし
、ｂ）Ｄ−１およびＢ−Ｅ−０ならば、Ｘを１にセットし
、Ｃ）さもなければＸを０にセットし、次の画素へ進む。

２）Ｂ、ＤＳＥ、Ｇのうちに正確に２個の黒い画素が存
在する。

ａ）黒い画素が互いに対向して位置させられると（Ｂ−
Ｇ−１またはＤ−Ｅ−１）　、Ｘを１にセットする。

ｂ）黒い画素が互いに隣接しているとすると、すなわち
、Ｂ−Ｄ−１であれば、たとえば、Ｂ（またはＤ）に対
応するブロック内の元の画像内の黒い画素の数が２をこ
えなければ、Ｘを１にセットすべきである。

Ｃ）他の場合には、Ｘを０にセットする。

３）Ｂ、ＤＳＥ、Ｇのうちに正確に２個の黒い画素があ
る場合。

この場合には、Ｘ−０を割当てることにより画像の質が
向上するように、Ａが曲っている線の附近になければ、
そのＡを１にセットすべきである。

下記のように定義されている４８３アレイＴ（アレイ５
）に考慮を払って、Ｘの附近の線の曲率についての判定
に達することができる。

ＢＣＧＨＤＦＥＨＴｌの各線内に少なくとも１つの黒い画素があるとする
と、曲率が大きい（すなわち、Ｘ−０）ということが通
例である。

４、サブサンプルされた画像の無損失圧縮および圧縮解
除縮減された元のファイルＯは、ＭＭＲまたは算術符号器
のように、２進フアイルの無損失圧縮のために、通常の
技術のいずれかを用いて圧縮し、記憶する。もちろん、
元のファイルＯと比較して０　は画素の数の４分の１だ
けを含んでいるから、それをより効率的に符号化できる
。元のファイル０を符号化するために必要なものの２分
の１の長さの符号により、サブサンプルされたファイル
０　を表すことができることが実験的に認められた。

５、元の画像の再構成および後フィルタリング上記の段
階を逆にすることにより元のファイルの再構成を行う。

まず、無１Ｍ失圧縮により、サブサンプルされたファイ
ル０　を検索する。次に、「０　の各画素が等しい値を存する画素の２Ｘ２ブ「ロックで置換されるように、拡張板のＯが得られる。

元のファイルの連結性を保持するやり方で本発明のサブ
サンプリング手続きは行われるから、実用的な目的のた
め４こは、再構成されたファイルＯは元のファイルＯの
ように読みやすい。しかし、サブサンプリングにより画
素の実効寸法が大きくなるから、ある線が多少「でこぼ
この外観」を持つことがあるかもしれない。

たとえば、サブサンプルされた画像のＯ（アレイ６）の
下記の短い部分について考えることにする。

１゜この形は、下に示すように（アレイ７）像中の斜線から
生じたのかもしれない。

、元の映１１１１１１　。

１１１　。

１１１゜１上の画像のサブサンプリングと、その後の拡張の後で、
下記のアレイ（アレイ８）が生ずる。

１１１１　。

１１゜１１　。

１１　。

明らかに、元の線は滑らかであるが、再構成された線は
著しい「階段効果」によって損なわれている。この問題
を解決する１つの明らかなやり方は、次の種類のセグメ
ント（アレイ９）を、１゜次のアレイ（アレイ１０）に似ているフィルタリングさ
れたアレイに拡張させることである。

１１１１１１　。

１この技術は上記の例に対して適切であるが、画像のある
区域、とくに、次のアレイ（アレイ１１）に示すように
、２本の線の直角交差区域において、質を低下させるこ
とがある。

１１１１１１１１この場合には、０　は前記最後のアレイ６の　中ｒのアレイ１０への無差別な変換が鋭角を乱すことがある
。したがって、上で概略を述べた簡単な解決技術は実際
の用途には受けいれられない。本発明による別のやり方
は、斜線（アレイ７の斜線に類似する）が滑らかに見え
ると同時に、鋭角がそのままではっきりした画像という
主観的な印象を維持するようにするために、拡張された
画像　の後フィルタリングを用いる。このやり方は、Ｐ
Ｃをベースとする装置に対してそれを実行できるように
するように、多数の画素に対して＝１算的には十分に簡
単であり、比較的少数の「問題のある」区域に対しての
みより高度な試験を要求される。これに関連して提案さ
れるフィルタリング論理は次の通りである。

ａ１画画像　を横切り、「問題のある」区域（アレイ１
２）がなければ嚢史しない。

ＩＡ　　　　ＡｌまたはＢＩ　　　　ＩＢ二二にＡとＢの少なくとも１つが０に等しい。

下に示すアレイ（アレイ１３）について考えてみる。説
明はこの種の１つのアレイに限定するが、実際には、こ
のアレイが持つことができる可能な向きのすべてについ
て考えねばならない。

ＢＣＤＥＦ、　ＩＨＩ１１）Ｃ−１でＢ＝Ｆ＝Ｈ＝０てあれば、小さい曲線を取
扱う、アレイ１３を下記の（アレイ１４）へ変換すべき
である。

２）ＡＡ、、１．ＩＤＤＡＡ、、　　ＩＩＤＤＥＥ．．．１１１ＥＥ．．．１１１ＧＧ、、１］、ＩＩＣＧ、、１１１１Ｃ−Ｄ−Ｅ−Ｆ−０であれば、斜線を取扱う。

アレイを下記の（アレイ１５）へ変換すべきである。

ＡＡ、　　、　　、、　　、　　。

ＡＡ、　　、　　、　　、、　　。

１．．．ＪＨｌｌｌＧＧ．．　　１　１　　ＩＧＧ．．　　１　１　　に二に、ＧとＨが１に等しければＪ−１である。

３）他の場合には、２本の直線の間の直角を取扱い、そ
れ以上の操作を行う必要はない。

すなわち、次の画素へ進む。

この方法の５つの段階の可能な置き換え以上の説明は本
発明の方法の５つの段階の好適な実施例についてのもの
であった。しかし、特定の任意の用途の特定の必要によ
り良く合致させるために、あるやり方で各段階を修正で
きる。それらの可能な変更のいくつかを以下に説明する
。

１、先に述べた前フィルタリング段階を、アイビーエム
・リサーチ・レポート（ＩＢＭ　Ｒｅ５ｅａｒｃｈＲｅ
ｐｏｒｔ）ＲＪ４１５Ｂ　（４５９４４）１９８４年１
１月所載のティー・キモト（Ｔ、ＫｉｍｏＬｏ）および
アール・ジー・ケージ−（Ｒ，Ｇ、Ｃａ５ｅｙ）による
論文［２進テキスト画像における水平線パターンおよび
垂り直線パターンのための縁部円滑化アルゴリズム（Ｅｄｇ
ｅ　Ｓｍｏｏｔｈｉｎｇ＾ＩｇｏｒｉｔｈｌＩｓ　ｆ’
ｏｒＨｏｒｉｚｏｎｔａｌ　ａｎｄ　ＶｅｒｔｌｃａＩ
　Ｌｆｎｅ　Ｐａｔｔｅｒｎｓ　ｆｎＢｉｎａｒｙ　Ｉ
ｍａｇｅｓ　）　Ｊまたは、アイビーエム・リサーチ・
レポートＲＺ１３４ｇ（５３１４１）１９１１５年１２
月所載のエフ・エム・ワール（Ｐ、Ｍ、Ｗａｈｌ）によ
る論文［文書の質向上およびデータ縮減のための２進テ
キスト画像プロセッサ（Ａ　Ｂｉ−ｎａｒｙ　Ｉｍａｇ
ｅ　Ｐｒｏｃｅｓｓｏｒ　ｆｏｒ　ＤｏｃｕｍｅｎｔＱ
ｕａｙ！ｔｙ　ａｎｄ　Ｄａｔａ　Ｒｅｄｕｃｔｉｏｎ
）　Ｊに教示されるもののように、走査ノイズを減少で
きる別の技術へ変更できる。ある場合、たとえば、ノイ
ズが非常に少ないか、時間がほとんどなく、かつ実行時
間を短くするために性能の質を犠牲にしたい場合には、
この段階をすっかり捨てることもすすめられる。

圧縮率の程度の高速評価に関しては、画素をベースとす
るものと、バイトをベースとするものとの２つのやり方
を上で説明した。両方のやり方においては、もちろん、
種々の判定しきい値を変更できる。さらに、圧縮率を許
されたものとしてとることができる用途においては、手
書きテキストの圧縮と同様に、この段階は全く無用であ
る。

３、サブサンプリング段階に関する限りは、連結性を保
持すること、およびばらばらの構造を意図しないのに一
緒にすることを保証するために、この操作を行うことが
重要である。この段階についての上の説明は、Ｘ方向と
Ｙ方向における、サブサンプリング係数が２である特定
の例を基にしたものであった。このサブサンプリング係
数は最も好ましいものであると信じられるが、この係数
は２に等しくないものを同様に選択できる。非常に高い
圧縮比が望ましい場合には、サブサンプリング操作を繰
返し行うことができ、効果的なサブサンプリング係数は
２．４．８等である。

４、無損失圧縮を行うために、バッフマン、ｍｍｒまた
は算術コーデックのような、各種の通常の符号化技術を
利用できる。

５、上記後フィルタリングの代りの技術は、前フィルタ
リング段階に関連して先に述べたキモトほかの文献に記
載されているフィルタラ用いることである。また、ある
場合には、画像の質のある程度の低下を進んで受は容れ
ることがあるから、後フィルタリングの手続きを飛越す
。

本発明の方法に含まれる杆々の操作をハードウェアによ
り、実現することは困難ではなく、求められている設計
論理を実現するためには種々の従来のやり方があること
を当業者はただちに理解するであろう。１つの好ましい
やり方は探索表（ＬｔＪＴ）を用いることである。例え
ば、サブサンプリング操作においては、考えるべきケー
スが３つある。それらのケースの間の識別はある４個の
画素（ここではＢ、ＤＳＥ、Ｇ）の値を基にする。１Ｂ
（２’　）行および３列のＬＵＴを構成することは熟練
者には容易であろう。それにより、任意に与えられた時
刻にどのケースが妥当であるかを判定する速いやり方が
得られる。

本発明の方法は圧縮をかなり高くするという意味で、本
発明の方法は従来の無損失圧縮技術より有利である。２
倍の改良というのは決して誇張ではない。もちろん、こ
の改良は画像品質をある程度低下させるという犠牲を払
って達成される。しかし、本発明の方法の関連するやり
方、すなわち、画像の特性に適合させられている特定の
各画素に対して用いられる圧縮のやり方、のために、再
構成された２進テキストは、その２進テキストの元のテ
キストと主観的にはほとんど区別できない。

−例として、第４図の手書きテキストについて考えるこ
とにする。圧縮しなければこのテキストは８００８０バ
イトの記憶空間を必要とする。通常の無損失圧縮の後で
は、同じテキストを僅かに２２１７バイトで表すことか
できる。第４図はそのように圧縮されたテキストをボす
。本発明の方法圧縮計画により、同しテキストを単に７
１８バイトに圧縮できる。それらの７１８バイトから再
構成された画像を第５図に示す。通常の無損失圧縮と比
較して、３倍より高い圧縮を行ったが、第４図の従来通
りに圧縮された画像と、本発明に従って圧縮された第５
図の再構成された画像との読みやすさはほぼ同じである
。

本発明の方法の特別の性質のために、その方法の実現は
ハードウェアの観点からは非常に簡単であると指摘され
る。今日のほとんどのパーソナルコンピュータによって
、この方法を採用するのに十分な計算能力が得られる。

【図面の簡単な説明】

第１図は背景に色がついている元の完成された態様を示
す説明図、第２図はフィルタリング後の第１図の態様を
示す説明図上第３図は本発明における圧縮率決定を示す
フローチャート、第４図は従来の方法で圧縮された手書
きテキストの再構成結果を示す図、第５図は本発明に従
って圧縮された第４図のテキストの再構成結果を示す図
である。

Claims

【特許請求の範囲】１、画素ごとのラスタ走査で２進テキスト画像が表示さ
れる記録キャリヤの上で２進テキスト画像を走査するこ
とと、走査器出力からデジタルデータの列を取出すこと
とを含み、記憶と、データリンクを介する伝送を含めた
将来の可能な処理とのための２進テキスト画像の高品質
圧縮法において、元の画像の個々の特徴の圧縮率の程度
を、元の画像中の画素の特定の近傍からのデータの情報
内容の頻度に応じて、少なくとも２種類の圧縮比の一方
を各近傍からのデータに割当てて決定する過程と、前記
一方の圧縮比に従って前記データを圧縮する過程とを備
えることを特徴とする２進テキスト画像の高品質圧縮法
。２、請求項１記載の方法において、画素の附近のうち高
い情報内容を有する近傍に、無損失圧縮に対応する第１
の圧縮比を割当て、低い情報内容を有する画素の附近に
、有損失圧縮に対応する第２の圧縮比を割当てることを
特徴とする方法。３、請求項１記載の方法において、元の画像の個々の特
徴の圧縮率の程度を決定する前記過程に、「１」画素の
全ての水平列と全ての垂直列がある所定の長さより短い
ならば、前記全ての列はもちろん、分離されている全て
の「１」画素の「０」への強制的な変更により、圧縮前
に走査データをフィルタリングすることを含む前フィル
タリング過程が先行することを特徴とする方法。４、請求項１記載の方法において、前記所定の長さを３
個の画素に決定することを特徴とする方法。５、請求項１記載の方法において、全画像区域を一様な
寸法の相互に排他的なセグメントに区画することにより
画素の前記近傍を定め、各セグメントに対して、値が「
１」と「０」である画素を含む間隔の平均長さ（ｗ）を
決定し、任意の１つのセグメントに対して、前記長さが
所定の長さ（ｗ＿ｔ）を超えたとすると、次のセグメン
トを質問し、さもなければ、以前にクリヤされたレジス
タ対（ｍ、ｎ）の内容を質問し、ｎは１だけ増加し、ｍ
はｗだけ増加し、セグメントの終りにおいて、ｎが所定
の第１のしきい値（ｎ＿ｔ）より小さいか、比ｍ／ｎが
所定の第２のしきい値（［ｍ／ｎ］＿ｔ）をこえるかを検査することにより圧
縮の実行可能性を決定し、該当する場合には、有損失圧
縮を行い、他の全ての場合には、無損失圧縮を行うこと
を特徴とする方法。６、請求項４記載の方法において、前記所定の長さ値（
ｗ＿ｔ）は１２であり、前記第１のしきい値（ｎ＿ｔ）
は５であり、前記第２のしきい値（［ｍ／ｎ］＿ｔ）は
４であることを特徴とする方法。７、請求項１記載の方法において、全画像区域を一様な
寸法の相互に排他的なセグメントに区画することにより
画素の前記附近を定め、各セグメントに対して、非零バ
イトの数（ｍ）を数え、各そのバイトを２進数に変え、
その２進数は、考察しているバイトが小さい黒または白
の間隔を含む、すなわち、そのバイトが０００００００
０または１１１１１１１１に等しくなく、かつバイトの
最初のビットが最後のビットに等しいものとすると、１
に等しく、および、他の全ての場合には０に等しく、連
続する「１」の対の数を数え、ｎが所定のしきい値より
小さいことと、ｎがｍの所定の部分より小さいこととの
少なくとも一方であるならば、有損失圧縮を行うことを
特徴とする方法。８、請求項７記載の方法において、前記しきい値は３で
あり、前記部分は５％に等しいことを特徴とする方法。９、請求項７記載の方法において、前記各セグメントは
元の２進テキスト画像の走査の線に対応することを特徴
とする方法。１０、請求項７記載の方法において、前記各セグメント
は元の２進テキスト画像の走査の連続する２本の線に対
応することを特徴とする方法。１１、請求項５記載の方法において、前記附近を２×２
のブロックとして定め、各そのようなブロックに対して
、１個以下の黒の画素を有する全てのブロックに「０」
値を割当て、正確に２個の黒の画素を有する全てのブロ
ックに「０」値を割当てることにより、そのような割り
当てが２本の線の間の連結を破らず、かつ線の曲りを歪
ませなければ、かつその破れとその他のものとの少なく
とも一方が起こらなければ、正確に２個の黒い画素を有
する全てのブロックに「１」値を割当てることにより、
１ビット表現を発生させることを特徴とする方法。１２、請求項１記載の方法において、カーブを保存し、
かつ線の間の鋭角を保存し、さらに斜線の構成を滑らか
にするために、前記圧縮操作はＡＢＣＤＥＦ．１ＧＨ１Ｉという形式のアレイに従って附近に適用できる再構成お
よびフィルタリング過程を含み、それは、Ｃ＝１かつＢ
＝Ｆ＝Ｈ＝０（小さいカーブのケース）であるならば、
前記アレイを次の新しいアレイＡＡ．．１１ＤＤＡＡ．．１１ＤＤＥＥ．．．１１１ＥＥ．．．１１１ＧＧ．．１１ＩＩＧＧ．．１１ＩＩへ変換し、およびＣ＝Ｄ＝Ｅ＝Ｆ＝０（斜線のケース）ならば、前
記アレイを次の新しいアレイＡＡ．．．．．．ＡＡ．．．．．．．．．．．．１１．．．．．．１１．．．ＪＨ１１１ＧＧＨＨ１１ＩＩＧＧＨＨ１１ＩＩへ変換するようにして実行することを特徴とする方法。