JPH03119486A - 記入済書式に含まれている情報を記憶または伝送のために圧縮する方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、特に、画像の部分が印刷された書式のような
、不変または標準的なものであって、情報内容に寄与し
ないような場合に、画像情報を圧縮し、圧縮を解除する
方法に関するものである。

〔従来の技術〕

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

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

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

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

この問題を減少するために、従来の文書走査装置にはデ
ータ圧縮ルーチンが設けられる。走査されるＡ４ページ
の圧縮されたデータはもちろん、走査されるページの内
容に応じて、２５〜７５にバイトの記憶空間に納めるこ
とができるように、それらのルーチンはほぼ１桁の大き
さを節約する。算術的コード化を基にした非常に賢いア
ルゴリズノ、は約１８％更に減少できる。どの圧縮装置
も、情報を処理または出力のいずれのためであっても、
後で情報の圧縮解除を行うことを可能にしなければなら
ないことはいうまでもない。

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

この問題に対する１つの可能な技術が、アイイーイーイ
ー会報（Ｐｒｏｃ、　ＩＥＥＥ）８８巻７号、１９８０
年７月号、所載のダブりニー・ケー・プラット（Ｗ、に
、Ｐｒａｔｔ）　、ピーＱジェー９キャピタント（Ｐ、
Ｊ、Ｃａｐｌ　ｔａｎｋ）、ダブりニー・チェノ（Ｗ、
Ｃｈｅｎ）、イー・アールΦハミルトン（Ｅ、Ｒ，ｌＩ
ａｍｉ　１ｉｏｎ）、アール・エイチ・ウォリス（Ｒ，
１１，νａｌｌｉｓ）による「組合わせ記号一致ファク
シミリデータ圧縮装置（Ｃｏｍｂｉｎｅｄ　Ｓｙｍｂｏ
ｌ　Ｍａｔｃｈｉｎｇ　Ｐａｃｓｌａｌｌｅ　Ｄａｔａ
Ｃｏ＋１ｐｒｅｓｓ１ｏｎ　Ｓｙｓｔｅｍ）　Ｊに記載
されている。その論文においては、２進画像を文字一致
プロセスへ供給することが提案されている。認識された
文字はそれらの文字の英数字態様により非常に効率的に
表される。それから残っている情報が通常の２進画像と
して別々に圧縮される。そうすると圧縮比が約２倍にな
るが、この技術の効率は認識される文字の百分比とデジ
タル化ノイズの程度とに大きく依存する。

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

その技術では、単一文字の認識の代りに、テキスト中の
個々の語のような大きな記号の一致が考えられる。しか
し、圧縮のために語より大きい記号を考える提案は行わ
れていない。したがって、この文献は満足できる比まで
の圧縮を可能にする方法を開示していない。

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

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

課題を解決するための手段 本発明の方法は、書式中に見出だされるものに類似する
一定の構造を有する画像に対してとくに有用である。業
務上の取引きにおいて用いられる文書の高い割合が種々
の設計の態様とレイアウトにより構成される。それらの
うちで、管理用のアンケート、小切手、交通機関の切符
および地図をほんの数例について述べる。

元の各書式（Ｏ）、すなわち、処理のために提出された
書式が、それの種類のあらゆる書式で循環する標準的な
部分すなわち一定の部分（ＣＰ）と、可変部分（ＶＰ）
、すなわち、書式を完成するために充填させられる情報
、とで構成される。

したがって、数字的な記法では、 ０−ＣＰ　　Ｕ　　ＶＰ で表される。ここに、ＣＰとＶＰは２レベルの画像、Ｕ
は、ＣＰまたはＶＰ（または両方）中の対応する画素が
黒であるならば０が黒であるような、各画素結合操作を
示す。

可変部分ｖＰは書式間で互いに異なる。

同じ一定部分（ＣＰ）を有する多数の書式に含まれてい
る情報については、その種の書式の一定部分の１つの単
一コピーと、各可変部分（ＶＰ）の１つのコピーとを有
する。、すなわち、その特定の種類の書式の個々の書式
が存在する数と同数の可変部分を有するだけで十分であ
る。したがって、それのＣＰを記憶させることにより各
種類の書式を効率的に記憶でき、その種の形態の多数の
個々の書式のそれぞれの可変部分（ＶＰ）を記憶するだ
けで、それら多数の書式を記憶できる。実際に、このや
り方は電子的書式の管理においてしばしば採用される。

これは簡単な着想であるが、問題は、２進画像として処
理せねばならない膨大な数の紙書式にこの着想をどのよ
うにして適用できるかということである。１つの可能な
解決法は、通常の走査器に対しては透明である特殊な色
インキを用いて、それらの書式の線、ボックスおよびテ
キストの基本的なパターンを印字することである。この
種の完成された書式が走査されるものとすると、基本パ
ターン（すなわち、ＣＰ）は走査器には見えず、可変部
ＶＰだけがコンピュータに入れられる。１Ｇ／Ａ４４Ｍ
Ｃｌプログラム、ワーキング・ベーパー（Ｗｏｒｋｉｎ
ｇ　Ｐａｐｅｒ）　４号、１９７３年９月、所載の、デ
イ−・イー、＋−ルセン（Ｄ、Ｒ，Ｎ１ｅｌｓｅｎ）ア
ール争ビー・アーブス（Ｒ，Ｂ、＾ｒｐｓ）およびティ
ー・エイチ・モーリン（Ｔ、１１．Ｍａｒｉｎ）による
「保険業文書用の走査器スペクトル応答の評価（Ｅｖａ
ｌｕａｔｉｏｎ　ｏｆ’５ｃａｎｎｅｒ　５ｐｅｃｔｒ
ａｌ　Ｒｅ５ｐｏｎｓｅ　Ｉ’ｏｒ　Ｉｎ５ｕｒａｎｃ
ｅＩｎｄｕｓｔｒｙ　Ｄｏｃｕｍｅｎｔ）Ｊにより発表
されたこのやり方の実用的な実現の開発にかなりの努力
が注がれた。このやり方の明らかな欠点は、特殊インキ
感知走査器の使用のために、既存の文書にこのやり方を
応用できないことである。

したがって、本発明の目的は、既存の文書を含めて、書
式の情報内容を提供することである。

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

基本的な着想は、−窓部分ＣＰを得て、それをメモリに
記憶させることである。この方法では、特定な用途にお
ける対象とする可能な空き書式のライブラリを発生でき
る。完成された書式が装置へ提示されると、その書式は
走査され、デジタル化され、結果として得られた２進情
報が記憶される。それから、走査された書式のそれぞれ
のＣＰが、ぷ別され、＝１算された書式の２進情報から
「差し引かれる」。このようにして得られた差は可変１ ２ 部ｖＰ１すなわち、対象とする情報である。これは計算
された書式のデータの一部分だけを通常含む。通常の手
段によるそれ以上の圧縮がｉｉＪ能であり、最後の記憶
は非常に効率的である。

再構成のために、圧縮されたデータが記憶装置から検索
され、通常のようにして圧縮解除され、ＣＰを表すデー
タでまきこまれる。しかし、はとんどの場合には、これ
以上の処理は可変部ｖＰだけを含む。

本発明の方法は、対応する空き書式（ＣＰ）と、それに
書込まれた情報（ＶＰ）とを別々に取扱うことにより、
記入済書式（Ｏ）で含まれている情報を記憶または伝送
のために圧縮する方法において、空き書式（ＣＰ）を予
め走査し、得たデータをデジタル化し、各空き書式（Ｃ
Ｐ）に関連するデジタル化された表現をコンピュータメ
モリに記憶させて書式ライブラリを構成する過程と、圧
縮すべき元の充填された書式（ＣＰ）を走査し、得たデ
ータをデジタル化する過程と、前記書式のライブラリ中
の前記空き書式（ｃ　ｐ）のうちの特定の１つを議別し
、それのデジタル表現を検索する過程と、空き書式（Ｃ
Ｐ）の前記検索した表現を、走査された記入済書式（Ｏ
）の前記デジタル表現から差し引く過程と、この差し引
く過程の差である充填された情報（ＶＰ）のデジタル表
現を適切な方法で圧縮する過程と、を備えることを特徴
とする充填された書式で含まれている情報を記憶または
伝送のために圧縮する方法である。

〔作　用〕

本発明の方法を要約すれば次の通りである。すなわち、
この方法は、対応する空き書式（ＣＰ）と、それに書込
まれた情報（ＶＰ）とを別々に取扱うことにより、記入
済書式（Ｏ）で含まれている情報を圧縮することに関す
るものである。空き書式のサンプルを前走査し、得たデ
ータをデジタル化し、コンピュータのメモリに記憶させ
て書式ライブラリを形成する。次に、圧縮すべき充填書
式（ＣＰ）の検索した表現を差し引く。それの差は充填
された情報（Ｖ　Ｐ）のデジタル表現である。

そうすると、その差を従来の方法で圧縮でき、または、
好ましくは、圧縮すべきデータ中の黒い画素の相対的な
内容に応じた少なくとも２つの圧縮比を用いる適応圧縮
技術により圧縮できる。

〔実施例〕

以下、本発明のｈ゛法の詳細を例により、図面を参照し
て詳しく説明する。

本発明の方法はほぼ４つの段階、すなわち、情報の獲得
と、予め記憶されているデータを走査されたデータに位
置合わせすることと、「差し引く」過程と、圧縮とを含
む。付加される段階は元の完成された書式の再構成であ
る。

画像情報の獲得には、書式の一定部分と可変部分に対す
る輝度パラメータが大きく異なることがあることを考慮
にいれなければならない。すなわち、手書きの１１工変
部分は、印刷された線や一定部分ＣＰのテキストより通
常は太い。したがって、走査パラメータをＣＰ部分と７
２部分に対して別々に最適化すべきである。走査自体は
標準的である。すなわち、走査装置は従来の走査器また
はデジタルテレビカメラとすることができる。走査は、
線の長さ１センチメートル当り１００画素、すなわち、
直径が約０　、０１　！ＩＩｍのドツト寸法、のオーダ
ーの解像力で、線ごとに行う。

この走査の結県として２つの２進データ列が生ずる。一
方の列は一定部分ＣＰ（すなわち、空き書式）を表し、
別の列は完成された、すなわち、元の走査された書式ｏ
−ｃｏ＋ｖｐを表す。この書式Ｏは一定部分ＣＰと充填
された情報ＶＰを含む。やり遂げるべき作業は、元の書
式Ｏを表すデータからＶＰを単に抽出することである。

実際の走査装置においては、書式が２回走査されると、
走査される書式を表すデータは、小さい直線的な位置の
狂いまたは小さい角度の狂い、したがってそれの２進走
査信号におけるずれをひき起こす結果となる小さな相対
的移動のためにわずかに異なる。また、デジタル化によ
りある位取りが導入されることがある。この観察は、Ｃ
Ｐデータを記憶するために走査される時には空き書式の
位置合わせに適用され、■Ｐデータの獲得のために走査
される時は元の書式Ｏに適用される。した　５ ６ かって、ｐめ記憶されている空き書式に関する元の書式
０をＣＰ内に位１わせする８鼓がある。

これは、１つの画像を別の画像へ変換できる幾何学的交
換パラメータを最適化することにより行われる。この最
適化のねらいは、変換が終わった時にある誤った測定値
を最小にすることである。

パターン認識、検査、変化検出、文字認識等のようない
くつかの技術領域においてデータの位置ぎめを行うため
の各種の技術が従来知られている。

それらの技術が次の米国特許第４．０２８，５３１号、
第４．４４１．２３７号、第４．０４４．５８２号、第
４．（ｉ５１．３４１号、第４．６５４．８７３号、第
４．６７２．６７１３号、第４．７０Ｇ、２９Ｇ号、第
４．８１５，１４０号、イメージ・ビジョン・コンビュ
ート（Ｉｍａｇｅ　ｌ＋Ｎ５ｉｏｎ　Ｃｏｍｐｕｔｅ）
、４巻、３号、１９８８年８月、の１５１〜１５８ペー
ジ所載の「画像位置ぎめアルゴリズムのハードウェア実
現（ｌｌａｒｄ−ＷａｒＯＩｍｐｌｅｍｅｎｔａｔｉｏ
ｎ　ｏｆ　ＩｌｌａｇＣＲＯｇｊＳＬｒａＬ＋０１１Ａ
１ｇｏｒｉｉｈｓｓ）　Ｊと題するエイチ・ニス・ラン
ガナス（＋１．８．　ＲａｎｇａｎａＬｌ＋）の論文、
アイイーイーイー会報（Ｐｒｏｃ、ＩＥＥＥ）　、８８
巻、７号。１９８０年７月、所載のダブりニー・ケー・
プラット（ν、に、Ｐｒａｔｔ）　、ビー・リュー・キ
ャピタント（Ｐｊ、Ｃａｐｌｔａｎｔ）、ダブリュー・
ケー・プラット（Ｖ、に、Ｐｒａｔｔ）　、ダブりニー
・チェン（ν、Ｃｈｃｎ）　、イー・アール・ハミルト
ン（Ｅ、Ｒ，Ｈａｍｉｌｔｏｎ）、アール・エイチ・ウ
オリス（Ｒ，Ｈ，Ｗａｌ　ｌ１ｓ）による「組合わせ記
号一致ファクシミリデータ圧縮装置（Ｃｏｍｂｉｎｅｄ
　Ｓｙｍｂｏｌ　Ｍａｔｅｌ＋ｉｎｇＦａｃｓｉａ＋ｉ
　Ｉｅ　Ｄａｔａ　Ｃｏｍｐｒｅｓｓｉｏｎ　ＳｙｓＬ
ｅｍ）Ｊと題する論文、およびアイビーエム・テクニカ
ル・ディスクローシト−・プルテン（ＩＢＭ　Ｔｅｃｈ
ｎｉｃａｌ　Ｄｉｓｃｌｏ−ｓｕｒｅ　Ｂｕｌｌｅｔｉ
ｎ）、１９７１年、１２９１〜１２９４所載のビー・シ
ルバーマン（Ｂ、Ｓｉ　ｌｖｃｒｍａｎ）による「高速
デジタル画像位置決定用アルゴリズム（Ａｌｇｏｒｉｔ
ｈｍｓｆｏｒ　Ｐａ５ｔ　Ｄｉｇｉｔａｌ　Ｉｍａｇｅ
　Ｒｅｇｉｓｔｒａｔｉｏｎ）Ｊと題する論文に開示さ
れている。知られている技術のいくつかは簡単な要約を
保障する。

最後に挙げた文献の最小自乗（Ｌ　Ｓ）法または最小絶
対値（ＬＡＵ）法に従って、変換された現在の画像と２
進画像の間の差の自乗または絶対値をとらなければなら
ず、かつ許された全ての変換のセットに対する最小を求
めなければならない。

交差相関計画の下においては、許された変換のセットに
対して、変換された現在の画像とライブラリィ画像の間
の交差相関を最高にする。モーメント不変概念の下にお
いては、画像の第１のモーメントと第２のモーメントが
移動と回転に対して不変であると仮定し、与えられた分
４１の固自゛ベクトルを計算し、それから２つの２進画
像の相対的な回転を決定する。

変換パラメータを計算する簡単で、しかもＨ用な方法は
、１つの画像中の１組の点と基準画像中の対応するセッ
トの間のりえられた一致から出る方程式系を解くことで
ある。この計画は自動点抽出プロセスと手動点抽出プロ
セスに分けられる。

不幸なことに、上記のやり方の全ては、位置決定が２次
元問題であるために計算的に重くなりがちであり、演算
の数が画像の画素の数に比例する。

全体の書式を取扱う場合には、大きなデータアレイを位
置ぎめせねばならない本発明に関連するように、従来技
術は計算の観点からは使用できない。

たとえばＡ４（２９７Ｘ２１０　ｍ＋ｓ）寸法の書式に
ついて考える。１００画素／ｃ＋ｎの標準的な密度でこ
の書式をサブサンプルすると、５百万個以上の画素を持
つ２進画像が生ずる。従来の装置による位置ぎめ法は同
程度の大きさの計算をいくつか要求する。

これは現在の構成のパーソナルコンピュータには非実用
的である。

本発明に従って、次元減少により位置ぎめ問題を解くこ
とが提案される。これは、画像をＸ軸とｙ軸の上に投射
し、結果としての１次元ヒストグラムの位置ぎめのため
の最小絶対値法を用いることにより行われる。したがっ
て、１次元ヒストグラムは、マトリックスのような、２
次元またはそれ以上の次元を有するアレイとは対照的に
、ただ１つの次元を有するアレイ、すなわち、ベクトル
、として定義される。この次元減少により、求められる
計算の数を画像の高さおよび幅に比例させることができ
る（Ａ４のページに対して５０００画素より少ない）。

それと同時に、・位置ぎめプロセスの速度が劇的に向上
する。

９ ０ わずかに回転させられ、かつ縮小された画像の場合でも
、本発明の位置ぎめプロセスを良ぐ機能させるために、
元の画像をいくつかの比較的小さい重なり合うセグメン
トに区分する。各セグメントに対しては簡単な移動変換
だけが許される。全体の画像の変換は、全ての個々のセ
グメント移動の組合わせとして表すことができる。もち
ろん、セグメントが小さくなると、この計画は回転のよ
うな複雑な変換をより良く取扱うことができる。

典型的なＡ４書式および標準の走査器に対して、４Ｘ４
の配置でページ当り１６ブロツク（−ｉするだけで十分
であることが経験的に見出だされている。

ブロックを分離させる望ましくない白い″分裂の形成を
避けるためにある程度のブロック間型なり合いを必要と
する。それらの分裂はセグメントの間の移動の違いによ
りひき起こされることがある。

他方、重なり合うマージンが増加すると変換の柔軟性が
減少する。２画素の重なり合いが多数の実用的な用途に
おいて良く機能することが実験的に見出だされた。

次にＸヒストグラムとＸヒストグラムを発生するために
、各セグメントに対して、１番目の成分中に対応する線
の黒い画素をその数だけ含んでいるベクトルを構成する
。これは、バイトをそれの画素にアンバックすることな
しに各線をバイトごとに走査することにより効率的に行
われる。現在のバイト中の「１」の数が適切な探索表、
たとえば、２５６個のエントリイと９個の出力を有する
探索表から得られ、ランニング和に加え合わされる。

このプロセスにより各線中に黒い画素の数が生ずる。

それから、最小絶対差を用いてＸヒストグラムを１次元
的に位置ぎめする。上記のようにして計算された現在の
ベクトルを、ライブラリベクトル（これは予め記憶され
ている空き書式の表現から同数のやり方で得られたもの
である）に一致させるために、現在のベクトルをシフト
させる。現在のベクトルのシフトは、必要な数の場所だ
け左または右へ機械シフト命令により行われる。最小で
ある差は最適なシフトを示す。その最適なシフトは対応
するセグメンｉ・の相対的な変位として後で用いられる
。

Ｘヒストグラムの発生は同様に行われる。各セグメント
に対して、対応する列のその数の黒い画素を１番１１の
成分中に含むベクトルが構成される。

これは、バイトをそれの画素にアンバックすることなし
に、各線をバイトごとに走査することにより行われる。

明らかに、各パイ！・に対して異なる活動を行う必要が
ある。２８個の可能なバイトの各バイトに対して、適切
な短いプログラムを予め用意しておく。

また、２５６個のエントリと、各エントリに１個の出力
とを有し、プログラムの対応する部分のアドレスを与え
る探索表が設けられる。各バイトに対して、探索表の２
５６のプログラム部分の１つへ進むと、ヒストグラムベ
クトルの１番１」の成分が、対応する画素が黒い時だけ
増加させられるように、与えられたバイトの２進航を基
にして適切な部分が選択される。

これを次の例により示すことができる。現（Ｅのバイト
が１０００００００であると仮定する。明らかに、最初
の画素に対応する場所でヒストグラムに１を加えて、残
りの７個の画素をそのままにしておくべきである。バイ
ト＋０００００００に対応する探索表中の線へ進んで適
切なアドレスを探す。そのアドレスにおいて求められて
いる短いプログラムを探す。

そのプログラムを実行し、次のバイトへ戻る。こ）手続
きによって、求められている数のオペレーションが黒い
画素の数に比例する（これは典型的には画素の総数の１
０％以下である）。

次に、最小平均絶対値差を用い、Ｘヒストグラムの位置
ぎめに関連して上で説明したのと全く同じやり方で、Ｘ
ヒストグラムの位置ぎめを１次元的に行う。

最適な翻訳パラメータの計算のための以上述べた手続き
を画像の各セグメントに対して繰り返す。

しかし、種々のブロックに対して計算した結果の一貫性
を検査する必要がある。このタスクは２重の目的を持つ
変位制御モジュールにより行う。それらの目的は次の通
りである。（１）任意の位置ぎ２′う ４ め誤りを検出する。これは、たとえば、最も近い８個の
セグメントのシフトの平均を＝１算することにより行う
。任意の２つの結果の間の差があるしきい値、たとえば
４、をこえたとすると、正常な位置ぎめが失敗したと仮
定でき、変位制御器を採用せねばならない。（２）情報
不足のために正常な手続きがうまく行かなかった失敗し
た場合に、ブロックに対するシフトパラメータを評価す
る。これは、与えられたセグメント中の空き書式が黒い
画素を持たない場合に起こることがある。この場合には
、最も近いものに対して計算されたシフトパラメータを
基にして評価する。

最適シフトがひとたび設定されると、各セグメントを出
力画像アレイの適切な区域に置く。出力画像アレイとい
うのは、位置ぎめプロセスの結果が発生されるメモリ中
の場所である。それぞれのシフトを行った後で、走査さ
れた画像のセグメントをそれの関連する場所に置く。

ｙ軸方向に置くことは変位インデックスの簡単な選択で
制御できる。たとえば、ここで考えているセグメントは
走査されている画像の線１００でスタートし、書式ライ
ブラリ中の対応するセグメントとの比較の後で、上方へ
５だけシフトさせるべきであることが決定されたと仮定
する。このことは、考えているセグメントを線９５から
始まって、出力画像に付加すべきであることを意味する
。はとんど全てのコンピュータがインデクシングモード
で動作する（すなわち、全てのメモリアドレスがある変
位インデックに関連して書かれ、それにより、関連する
アドレスと変位インデックスを加え合わせることにより
絶対メモリアドレスが得られる）ということを考えると
、１つのレジスタ値、すなわち、インデックスの値、を
変えることにより、全セグメントのｙ方向のシフトを行
うことができる。

Ｘ軸方向に置くことを制御することはもう少し困難であ
る。この場合には、適切な数の場所だけ（１から７へ）
データを実際にシフトさせることが必要かもしれない。

このようにして、データをビット書式にアンバックした
り、バイト書式へ戻したりする必要なしに、出力アレイ
を得ることが可能である。

上記のように、走査された画像のセグメント化が少しの
重なり合いで行われる。また、個々のセグメントの相互
のシフトがいくらか重なり合わせることがある。しかし
、セグメント化手続きの痕跡が見えない滑らかな出力画
像に関心が持たれるものである。明らかに、出力画像ア
レイ中の画素のうち、走査される画像の２つ以上のセグ
メントにより影響される画素に特殊な処理を行う必要は
ない。好ましい解決法は、含まれている全てのセグメン
トに対してプール計数のオア演算を行うことである。推
奨される手続きは出力画像アレイをまずクリヤし、それ
から走査された画像をセグメントごとに処理することで
ある。適切な場所にある出力アレイへ、各画素に対して
オア走査を行うことにより、新しい各セグメントを加え
る。

上記のように、本発明の方法の１つの段階が２つの１次
元アレイ、すなわち、Ｘヒストグラムとｙヒストグラム
、の位置ぎめを要求する。実現の１つの可能性は、既知
の最小絶対値（ＬＡＶ）手法によるものである。しかし
、状況に応じてもっと有利なことがある、従来の交差相
関（ＣＣ）手法のような、利用できる別の手法がある。

後者は性能の面でたしかに有利であるが、計算の観点か
らははるかに複雑である。

この計算の複雑さは、含まれている２つのヒストグラム
上のピーク、すなわち、ヒストグラムが最大である所、
の相対的な位置の比較によりしばしば減少させられる。

たとえば、第１のヒストグラムが場所１０に最大値１０
０を有し、第２のヒストグラムの最大が場所２０にある
とすると、１０のシフトは非常に低い計算の犠牲で、２
つのヒストグラムの間に受けいれることができる一致を
生ずる。

２進画像、すなわち、黒成分と白成分だけを有する画像
、に関連して位置合わせ手続きを説明したが、この手続
きを灰色側の画像にも同様に適用できる。そのために、
画像またはそれの傾いたもの（ｇｒａｄｉｃｎｔ　ｖｃ
ｒｓｌｏｎ）に対してしきい値操作することにより、灰
色調画像をそれの２進片われへ変７ ８ 換し、それから、変換パラメータを上記のようにして計
算する。与えられた線（または列）内の全ての画素の灰
色側画素を加え合わせることにより、ヒストグラム投射
を灰色調画像から直接計算できる。

予め記憶されている画像ＣＰとの走査される画像Ｏの位
置合わせが成功したとすると、次に行う段階は元の両像
Ｏから一定部分ＣＰを差し引くことである。不幸なこと
に、はとんどの実際的なケースにおいては、一定部分Ｃ
Ｐを表す予め記憶されているデータの検索はもちろん、
元の画像０の走査によってノイズが生ずる（たとえば、
書式が記載されている用紙がきれいでないこと、すなわ
ちくしゃくしゃになっていることから生ずるノイズに加
えて）。したがって、元の充填された書式０と、空き書
式ＣＰと、それらの直線的な差とをそれぞれ示す第１〜
３図の比較かられかるように、直線的な減算では希望の
結果は生じない。もちろん、目的は走査ノイズの除去で
ある。第３図の場合には、そのノイズは、手書き部分を
囲むボックスのかすかな残りである。

これを行う方法は、（Ｉ）一定部分ＣＰのできるだけ多
く　（すなわち、■に等しい）黒い画素を元の両像０か
ら除き、（２）可変部分ｖＰに属する全ての画素をその
まま残すこと、である。

明らかに、他方を犠牲にしてそれらの目標の１つを達成
することが比較的容易である。従来の解決法は両方の目
標を同時に達成することに失敗している。本発明の方法
は、アイイーイーイー会報（Ｐｒｏｃ、　ＩＩＥＩシ１
シ）８８巻７号、１９８０年７月号、所載のダブりニー
・ケー・ブラット（Ｗ、に、　Ｐｒａｔｔ）、ピー昏ジ
エー・キャピタント（Ｐ、　Ｊ、Ｃａｐｆ　ｔａｎＯ、
ダブリュー・チェノ（Ｗ、Ｃｈｃｎ）、イー・アール・
ハミルトン（Ｅ、Ｒ，）ｌａｍｉｌｔｏｎ）、アール・
エイチ番つオリス（Ｒ，１１，Ｗａｌ　Ｉ　ｉｓ）によ
る「組合わせ記号一致ファクシミリデータ圧縮装置（Ｃ
ｏｍｂｉｎｅｄ　Ｓｙｍｂｏｌ　ＭａｔｃｈｉｎｇＦａ
ｃｓｉｍｉｌｅ　Ｄａｔａ　Ｃｏｍｐｒｅｓｓｉｏｎ　
５ｙｓｔｅ＋ｇ）Ｊに記載されている研究から始まった
ものである。彼等の手法は Ｐ〜−〇−（１品）［１］ Ｐ により、あるいはいいかえれば Ｐ〜−〇〇（Ｐ心）　−［２］ ＶＰ により可変部分ｖＰのＰ心を評価を得ることである。こ
こに、ｎは交差を示し、記号″は論理否定を示す。この
場合には、目標（２）は完全に達される。しかし、多数
の黒いＣＰ画素がＰ心の附近に位置させられるが、Ｐε
１自体の」二にないから、ＣＰに属するかなりな数の画
素がＰＶＰに残る。その結果、ＰＶｌはＶＰより「大き
い」。

この効果はもちろん望ましくない。というのは、本発明
の画像圧縮においては、ＰＶｉ）の圧縮が、ＶＰを表す
ために必要なものよりはるかに多いコードビットを要求
するからである。

この欠点のために、デユーダ（１）ｕｔｌｔ）および／
入−ト（ｌｌａｒＤ著［パターン分類および光景解析（
Ｐａｔｔｅｒｎ　　ＣＩａｓｓｉｒｉｃａＬｉｏｎ　　
ａｎｄ　　５ｃｅｎｅ　　Ａｎｄｌｙｓｉｓ）　　Ｊ、
ワイリー・アンド・サンズ（Ｗｉｌｅｙ　＆　５ｏｎｓ
）、１９年発行、にはＰＶｌをまず拡げることを示唆し
ている。拡げられたもの、ＢＣＰ、においては、全ての
画素の近くに少なくとも１個の黒い画素ＰｃＰがあるよ
うに、全ての画素を「１」にセットする。拡げる手続き
では”ｖｐは次のようにして得られる。

Ｐ〜−０−ＢＣＰ＝ＯｎＢＣＰ　−［３］Ｐ この手法では、拡げる過程が十分に広かったとすると、
全０２区域を除去することが可能である。

しかし、不幸なことに、ＶＰのある部分も除去される。

ＣＰとｖＰが交差する時に常にこれは起こる。交差区域
の近くではＰＶｌは白である、すなわち、ｖＰが黒であ
ったとしても対応する画素は０であり、それに伴って画
像の質が低くなる。

本発明の方法は上記欠点を避けるものである。

すなわち、上記目標をいずれも不当に折り合わせること
なしに、かつパーソナルコンピュータにも応用できるよ
うにする効率で、ＶＰのよい近似を１ｕられるようにす
る。それと同時に、本発明の方法によりＰ心およびＰＶ
ｌから元の画像を容易に再構成できる。そのために、本
発明の下に、これが劣化させない場合、すなわち、Ｐ心
が黒の場合に式１　（または２）が常に用いられ、拡げ
ら１ れたＢＣＰが白である場合に弐３が用いられ、ＣＰがｖ
Ｐに交差する（問題のある区域）場合に最適な解を決定
するために特殊なテストを行う。

元の画像Ｏを１度に１画素づつ走査する。各画素Ｐに対
してそれのすぐ近（（ｎＸｒｉの正方形）について考え
る。ＣＰのできるだけ多くの黒い画素（１）をＯから除
去する。空き書式ＣＰにおいである画素が黒であるとす
ると、差画像ではこれは同様に白であるかもしれない。

元の画像Ｏにおいて、空き書式に属する黒い画素から遠
く離れて黒い画素が見出だされたとすると、差画像にお
いてはその画素も黒でなければならない。それらの代り
のものがいずれも適用されないとすると、より高度の試
験を行わねばならない。

ここで、０中のＰの対応する近くのものをＮ。

で表し、ＰＥ１中のＰの対応する近くのもの（それは最
初は０にセットされる）をＮど１で表すことにする。種
々のアレイ中の画素Ｐの可能な値を次のようにして示す
ことができる。

ａ　、　　Ｐ　ｏ　（Ｏ中の画素Ｐの値）が０゜２ もちろん、この場合にはどのような操作も行う必要はな
い。（すなわち、付加計算は求められない）。次の画素
へ進むことができる。

ｂ、ｐ、−ＰｃＰ〜１ ここでは、画：ＡＰはＯにセットすべきである（すなわ
ち、近似Ｊ１においては、ＰＶｌの値は０である）。し
かし、アレイｂがＯに初期化されているから、実際には
付加活動を行う必要はなく、次の画素へ進むことができ
る。

Ｃ，Ｐｏ−１、およびｐ各−ｏ。

この問題のケースにおいては、Ｐの値ばかりでなく、そ
れの近くにある画素の値も考える必要がある。ＰＶｌの
希望の値は下記の試験を基にできる。

１、　　ＰがＣＰに属することができるかどうかを調べ
る。答えが否定であれば”ｖｐ””にセットし、次の画
素へ進む。答えが肯定であれば、次の試験へ進む（ｃ、
　　２．　）全体のウィンドウＮｖｉが消えるか、また
は、一般に、ＮＥｉ中の黒い画素の数が所定のしきい値
をこえるかどうか、を確かめることに２゜ より行うことができる。実際に、ＣＰ内のＰの附近が空
であれば、０中の黒い画素はＣＰのひずみから生じたも
のではあり得す、したがってそれは必ずｖＰに属する。

ＰがｖＰに連結されているかどうかを調べる。

答えが肯定であればＰ自体はｖＰに属し、ＰＶＰを「１
」にセットせねばならない。答えが否定であれば、Ｐが
ＣＰに属する結論となり、したがって、ｐ、、−ｏであ
る。ＰがｖＰへ連結されているかどうかを決定するため
にはＮ７１を知らねばならない。いいかえると”ｖｐを
計算できるようにするためには、Ｐの附近の全ての画素
に対してＶＰを知らねばならない。しかし、実際の場合
には、Ｎｉｉの部分だけが既知である。すなわち、ｖＰ
のそれに対応する評価が既に知られているように、過去
において既に横切られた部分が知られていることはもち
ろんである。したがって、連結性試験においては、実際
のＮ〜の代りにアレイ蒜を使用せねばならなりＰ い。〜自体はＮ占の「第１次」近似である。

これは次のようにして行うことができる。

ａ、附近のＮεｉを係数ｍだけ拡張する（拡げる）。こ
れは、Ｎｉ１を左、上または下ヘシフトすることにより
行うことができる。次に、全部で５つのアレイ、１つの
原アレイとシフトされた４つのアレイ、をブール加算す
ることにより拡げられたＢＮＩ、、が得られる。ＢＮ２
εｉを得るためにこの拡張をアレイＢＮ１ε１に対して
繰返す。ｍ個の段階の後で最後のアレイＢＮＭεｉが得
られるまでこのプロセスを続ける。

ｂ。

Ｖｐのローカルな近似値は Ｎ　０−ＢＮ　ｍｃ　ｐ　ｌ−ｌＮ０　ｎ　＜　Ｂ　Ｎ
　＝　ｃｐ）′にしたがって＝１算する。

Ｃ２上で＝１算された近似をＮＶｌの「既知」の値に組
合わせることにより青を見出だす。例えば、画像が左か
ら右へ、および上から下へ横切られるものとし、かつ、
ウィンドウの寸法５ がｎ＝５であるとする。そうすると近くの各アレイは次
のようにして編成される。

１１　１２　１３　１４　１５ ２１　２２２３２４２５ ８＋　　３２８３３４３５ ４１　４２　４３　４４　４５ ５１　５２５１５４５５ ニスに、数字ｉｊは１行ｊ列の画素の位置を定める。そ
れらの仮定のドにおいては、アレイ０の画素１１．１２
．１３．１４．１５．２１．２２．２３．２４．２５．
３１．３２は既に分析されており、したがってＪｌに対
する適切な鎖が計算されている。残りの位置（３３，３
４，３５，４１，４２，４３，４４，４５，５１，５２
，５Ｂ、５４．５５）における値は上の点ｂ）において
計算されたアレイが得られる。

Ｎがひとたび知られると、画ｄｉｒが、中央において、
ｖＰへ連結されるかどうかを決定することは容易である
。非常に簡単な基準を使用できる。蒜中の黒い画素の数
が所定のしきい値をこえたとすると、考察中の画素Ｐは
６ Ｊｌに属する。

ここで、たとえば、記入済のアレイ中の近くのものＮ　
と、空き書式アレイ中の近くのものＮδとを有する黒い
画素について考える。

Ｎｏ　　　Ｎぶ ｏｏｏｏｏ　　　ｏｏｏｏ。

ｏｏｏｏｏ　　　ｏｏｏｏ。

００ＰＩＩ　　　００１１１ １．１１］、１　　　１１１１１ １１１１１　　１１１１１ これは明らかに上記のケースの初めのものであり、出力
アレイにおいては、Ｐは白（Ｏ）にちがいない。しかし
、次のことが起きたとすると（第２のケース） Ｎｏ　　　　Ｎ四 ｏｏｏｏｏ　　　ｏｏｏｏ。

ｏｏｏｏｏ　　　ｏｏｏｏ。

００ＰＩＩ　　　０００００ １１１１１　　０００００ １１１１１　　０００００ Ｐを黒のままにすべきである。他方、近くのものがこれ
に似ているとすると、 ＮＯＮＣＰ ００　Ｄ　Ｄ　ＯＤ　Ｄ　Ｄ　ＯＤ ｏｏｏｏｏ　　　ｏｏｏｏ。

ｏｏｐｏｏ　　　ｏｏｏｏ。

１１１１１　　　１１１１１ １１１１．１．　　　１１１１１ Ｎ心の１番下におけるノイズからＰが生じた（したがっ
て、出力アレイにおいて０にセットすべきである）、ま
たは充填された行に属するからＰが黒であるか（したが
・−）で、出力においては画像を１にセットすべきであ
る）、を決定するためにはより高度の試験が必要である
。上の最後の例においては、判定はＰを０にセットする
ことである。しかし、ドの例ではＰ−１にする決定をす
ることがより合理的である。

ＮＯＮＣＰ ｏｏｏｏｏ　　　　ｏｏｏｏ。

０００１０　　　　０００００ ００Ｐ００　　　００（１（１（１ １１１１１１１１１１ １１１，１１１１１１１ 次に、図面を参照して本発明の方法の性能を説明する。

たとえば、第１図に元の書式Ｏの小さい部分が拡大して
示されている。その図は書式Ｏの小さい部分が拡大して
示されている。その図は書式を構成しているボックスの
形からのボックスと、このボックス中へのある手書きの
エントリとを含む。適切な空き書式が記憶装置内に識別
された後で、それの２進表現を検索する。対応する出力
が第２図に示されている。線の太さおよび連続性とのあ
るずれの他に、空き書式の表現が第１図の元の書式の表
現とは大きくずれて現われる。位置ぎめプロセスが終わ
ると、画像を第３図に示すようにほぼ正確に重ね合わせ
る。次に、空き書式ＣＰを表すデータを元の書式Ｏを表
すデータから差し引く。直線的な減算の結果が第４図に
示されている。上で述べたように、走査プロセスにより
ある程度のノイズを生ずることがあり、それが第２図に
示されているボックスの残りのシルエットすなわち影と
して第４図に見える。第４図は減算を示すためだけのも
のであって、通常は第４図は発生されないことに注目す
べきである。本発明の減算９ プロセスを適用すると第５図に示す結果が生ずることに
注目すべきである。第５図には最初に走査された書式Ｏ
の一定部分ＣＩ’の跡は残らない。

第６図はこの方法の終りで見る結果である。すなわち、
この図は第２図の空き書式ＣＰと第５図の充填された部
分との再構成を表す。希望どおり、第６図の画像は第１
図のオリジナルとほぼ同じように見えるが、もちろん、
画素ごとに比較するとそれらの画像は異なる。

第７図は第１図の部分を取り出した全体的な元の書式（
ｇ、）の表現である。ヘブライ語のテキストが描かれて
いるこの書式を選択した理由は、はとんどがヘブライ語
を読むことがてきないと仮定される読者がこの図を抽象
的な２進画像の例として見ることができないようにする
ためである。

この画像を走査し、その走査結果から直線的なやり方で
、すなわち、［１］式に従って得たデータは、適切な位
置ぎめプロセスが終わった後の第８図の対応する空き書
式に対して予め記憶されたデータである。その結果を第
９図に示す。明らかに、０ ＣＰの不完全な除去の結果である黒い画素のような望ま
しくない情報を多数含むから、それは本発明の枠組み内
では受けいれることはできない。これは、前述したよう
に、直線的な結果が許容できる結果を生じないことを示
す。

本発明の減算スキームでは、減算の結果は第１０図に示
すようなものである。空き書式ＣＰの情報内容は完全に
除去されている。空き書式ＣＰの黒い画素が手書き情報
に属する黒い画素にたまたま重なり合ったとすると、第
１０図に「空白」として見ることができる白い画素でそ
の画素が置き換えられることがある。変化検出プロセス
が、ｖＰのひずみのような、ノイズを導入したかどうか
を調べるために、たとえば、第８図の空き書式と第１０
図の「画像変化」を組合わせすることを望むことができ
る。その結果を第１１図に示す。

この図には可視不連続が少しあるが、テキストの可読性
が損なわれていないから、一致はほぼ完全であると考え
られる。

したがって、本発明の方法により元の画像の−定部分Ｃ
Ｐを完全に除去すること、および元の画像の６工変部分
ｖＰのひずみのない画像を得ることができる。したがっ
て、３０にバイトのオーダの情報内容を有する元の書式
の全体を記憶させる必要はなく、僅かに約６にバイトの
情報内容を白”する第８図の画像を記憶することで十分
であり、したがって画像の質が実際に低下することなし
に５倍の圧縮比を達成する。画像の可変部分ＶＰの圧縮
は従来の方法で行うことができる。

圧縮段階を、この技術で知られているものよりも優雅な
やり方で行うこともできる。好適なやり方は、圧縮すべ
き情報の「密度」に応じて少なくとも２種類の圧縮比を
適用することを含む。たとえば、２つの圧縮比を用いる
やり方を仮定すると、第１の比を「無損失ｊと呼び、第
２の比を「有崩失」と呼ぶ。したがって、圧縮するデー
タのうち、密度が非常に高い部分、すなわち、比較的多
数の黒い画素を含んでいる部分を低い圧縮比で処理して
、圧縮した時に黒い画素が失われないようにし、比較的
少数の黒い画素を含んでいる部分は高い圧縮比で処理し
て、情報内容に実際に関連する少数の画素が失われるこ
とがある可能性を許容できる程度にとどめる。

したがって、無損失圧縮比と有損失圧縮比の適用を制御
するために、画像の高密度部分と低密度部分を決定する
ための前フィルタリング段階をこの技術は要する。一定
の、すなわち、あらかじめ印字された性質の情報と、可
変の、すなわち、手書きの性質の情報とを含んでいる書
式の処理に適用すると、手書き部分が高い圧縮比に大し
て通常修飾するから、帯域幅と記憶空間が大幅に節約さ
れる。

【図面の簡単な説明】

第１図は走査されて、コンピュータメモリに（拡大尺度
で）記憶された元の充填された書式の一部を表す図、第
２図は空き書式の対応する部分を表す図、第３図は位置
ぎめプロセスの結果を示、す図、第４図は第１図と題２
図との画像の直線的な減算を示す図、第５図は空き書式
の全ての痕跡３ ４ が除去されている元の書式の充填部分を示す図、第６図
は第５図の充填された情報と第２図の空き書式の再構成
を示す図、第７図は完成した充填された書式を表す図、
第８図は対応する空き書式を走査する結果を表す図、第
９図は第７図と第８図の画像の直線的な減算の結果を示
す図、第１υ図は第７図と第８図に本発明の方法を適用
した結果を示す図、第１１図は第８図占第１０図がらの
充填された書式の再構成を表す図である。 １（

Claims (1)

1. 【特許請求の範囲】 １、対応する空き書式（ＣＰ）と、それに書込まれた情
   報（ＶＰ）とを別々に取扱うことにより、記入済書式（
   Ｏ）で含まれている情報を記憶または伝送のために圧縮
   する方法において、空き書式（ＣＰ）を予め走査し、得
   たデータをデジタル化し、各空き書式（ＣＰ）に関連す
   るデジタル化された表現をコンピュータメモリに記憶さ
   せて書式ライブラリを構成する過程と、圧縮すべき元の
   記入済書式（Ｏ）を走査し、得たデータをデジタル化す
   る過程と、 前記書式のライブラリ中の前記空き書式（ＣＰ）のうち
   の特定の１つを識別し、それのデジタル表現を検索する
   過程と、 空き書式（ＣＰ）の前記検索した表現を、 走査された記入済書式（Ｏ）の前記デジタル表現から差
   し引く過程と、 この差し引く過程の差である充填された情報（ＶＰ）の
   デジタル表現を適切な方法で圧縮する過程と、 を備えることを特徴とする充填された書式で含まれてい
   る情報を記憶または伝送のために圧縮する方法。 ２、請求項１記載の方法において、輝度およびしきい値
   レベルのような走査パラメータを、空き書式（ＣＰ）お
   よび前記元の入力済書式（Ｏ）に対して別々に決定する
   ことを特徴とする方法。 ３、請求項１記載の方法において、差し引く過程の前に
   、完成された書式（Ｏ）に関する充填された情報（ＶＰ
   ）の相対的な位置に関連する情報を決定し、元の入力済
   書式（Ｏ）と前記空き書式（ＣＰ）の位置合わせを行う
   ことを特徴とする方法。 ４、請求項３記載の方法において、前記位置合わせ情報
   を次元の数を減少させることにより決定することを特徴
   とする方法。 ５、請求項３記載の方法において、前記位置合わせを、 走査された記入済書式（Ｏ）を小さいセグメントに区分
   する過程と、 各セグメントごとにｘ方向とｙ方向で実行すべき最適な
   桁送りを評価する過程と、 前記元の記入済書式（Ｏ）の各セグメントを、以前に設
   定された桁送り情報を用いて、出力画像アレイの適切な
   区域に置き、全てのセグメントを置くことが終わった時
   に、桁送りされた画像が得られるようにする過程と、 の一連の過程で行うことを特徴とする方法。 ６、請求項５記載の方法において、前記元の記入済書式
   （Ｏ）を、２１０×２９７ｍｍの寸法のページ当り少な
   くとも約１６セグメントに対応する割合で区分すること
   を特徴とする方法。 ７、請求項５記載の方法において、セグメントのマージ
   ンが約２画素に対応する距離だけ重なり合うように前記
   区分を行うことを特徴とする方法。 ８、請求項５記載の方法において、近くの各セグメント
   対の差が特定のしきい値をこえないようにすることによ
   り、前記各セグメント対に対して前記評価された最適な
   桁送りの一貫性を検査し、もし前記差が前記しきい値を
   こえたとすると、オペレータの介入を自動的に求めるこ
   とを特徴とする方法。 ９、請求項１記載の方法において、前記差し引く過程は
   、前記対応する空き書式（ＣＰ）に属するか、または前
   記対応する空き書式（ＣＰ）に属する黒い画素の近くに
   位置させられている全ての黒い画素を元の記入済書式（
   Ｏ）から除去する過程と、前記充填された情報（ＶＰ）
   に属する全ての黒い画素を保持する過程とを含むことを
   特徴とする方法。 １０、請求項１記載の方法において、前記圧縮過程は、
   圧縮すべきデータ中の、比較的多数の黒い画素を含んで
   いる部分および比較的少数の黒い画素を含んでいる部分
   との内容に応じて、少なくとも２種類の圧縮比を適用す
   ることを含み、圧縮すべきデータはまず前フィルタリン
   グして、それの相対的な圧縮可能性を決定することを特
   徴とする方法。 １１、請求項１ないし１０のいずれか１つに記載の方法
   において、どのバイトもそれの成分画素に詰めこむこと
   なしにバイト様式で維持されている前記２進表現で前記
   全ての過程を行うことを特徴とする方法。