JPS5810964A - ２次元パタ−ン修正方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は英数字、漢字かな混り文の文章、グラフや表、
設計図面など、一般に線図形と呼ばれている２次元パタ
ーンの処理に関し、さら（＝詳しくは、歪をうけノイズ
の重畳した２次元パターンを本来のパターンに修正・復
元する方式に関する。

いわゆる線図形と呼ばれている２次元パターンを通信伝
送゛したり複写したりすると、パターンの品質が劣化す
る。これは、伝送途中や複写過程で発生するノイズや歪
によるものである。このような本来のパターン以外の成
分が全く混入しないような伝送系や複写機構を実現する
ことは、実際上殆ど不可能である。したがって、ノイズ
が混入したり歪を受けた２次元パターンを、その本来の
パターンへ修正・復元するための技術の確立が要請され
ている。

さて、文章や図面の情報源である線図形は、自然画像と
違って、ある手段を用い、ある特定の規則（二沿って生
成されるのが普通である。すなわち、伝送や複写；二よ
って２次元パターンの品質が劣化するということは、ノ
イズや歪（、二より上記の規則（ユ合わないパターンへ
変形されたと考えることができる。したがって、２次元
−パターン中の生成規則に合わない成分を修正すれば、
本来のパターンの復元が可能なはずである。

発明者は、かかる観点に基づいて２次元パターンを修正
・復元する一方犬を既に特許出願（特願昭５６−４４４
６４号）している。この方式は、２次元パターン（二お
い゛Ｃ出現する単位メツシュの特定のパターンを合法パ
ターンとして予め選定しておき、処理すべき２次元パタ
ーンに出現する各単位メツシュのパターンのうち、合法
パターン以外のパターン（非合法パターン）は、それと
特定の関係にある１つの合法パターンへ強制的（＝変換
するというものである。例えば、単位メツシュのサイズ
をｍｘｍ画素としたときに、単位メツシュパターンをｍ
ｘｍビットのハミング符号と考え、非合法パターンをそ
れとのハミング距離が最小の合法パターンへ変換する。

また、同一ハミング距離の合法パターンが２つり、Ｌ存
在するときは、その中で良質の２次元パターン、におけ
る出現頻度の高い１つの合法パターンを選択して非合法
・２ターンに割り付ける。

合法パターンの選定、単位メツシュのサイズの決定、非
合法パターンから合法）くターンへの変換等の詳細につ
いては、上記の特許願に添付の明細書に述ベーＣあるの
で、ここではこれ以上の説明は省略する。

本発明は上（＝略述した既出願発明の延長上にあるもの
で、単位メツシュ間の接続関係、画素間の接紗関係をも
考慮して２次元）くターンを修正・復゛元する方式を提
供することを目的とする。

また本発明のもう一つの目的は、ノ・−ドウエア化やリ
アルタイム処理の容易性を考慮した２次元パターン修正
方式を提供することにある。

しかして本発明にあっては、既出願発明と同様（二合法
パターンを選定し、修正処理すべき２次元パターンに非
合法・；ターンが出現すると、それを１つの合法パター
ンへ変換する。この際の変換則は前述の既出願発明と同
様でよく、例えば、非合法パターンをそれとの）・ミン
グ距離が最小の合法パターンへ変換する。

本発明ではさらに、合法パターンが本来の２次元パター
ンの要素として矛盾することなく隣接し。

ているときに、これら隣接合法パターン相互間で満足さ
れるべき特定のパターン接続条件を予め決定する。すな
わち、このパターン接続条件を満足しない接続関係で隣
接する合法パターンは、そのままでは本来の２次元パタ
ーンの要素としては許容されないということである。

しかして、上記の非合法パターンの合法″ターンへの変
換処理を完了した、寸たは該変換処理の途上にある２次
元パターン（この変換処理によって非合法パターンが合
法パターンに置換された後の２次元パターンを、以後゛
シンボル表記画像”と称す）上の隣接する単位メソシュ
相互間のパターン接続関係を観測する。そして上記の特
定のパターン接続条件を満足しないときは、それを満足
するように当該隣接単位メツシュ中の１つ以上の単位ツ
ノシュのパターン（合法パターン）を他の合法パターン
へ変換する。この処理後の２次元パターンを、今後は゛
合法シンボル表記画像”と称す。

処理すべき２次元パターンからシンボル表記画像を得る
過程は、既出願発明と同様でよいのでこれ以−ヒの説明
は割愛し、シンボル表記画像から合法シンボル表記画像
への変換について、図面に沿つ゛Ｃ具体的に説明する。

まず、ト配のパターン接続条件について説明する。

今、ｍｘｍ画素サイズの正方形の単位メソシュを想定す
る。これは一般に妥当である。このような正方形の単位
メツシュ相互の直接的な接続としては、縦方向（通常、
２次元パターンの副走査方向）の接続と、横方向（通常
、２次元パターンの主走査方向）の接続の２種類が考え
られる。しかし斜め方向に隣接する単位メツシュ相互の
相関もかなり強いので、斜め方向の接続も考えるのが望
ましい。したがって、第１図に示すように、隣接する４
つの単位メソシュＡ、Ｂ、Ｃ，Ｄの相互間の接続を同時
に考える。

ここでパターン接続法則を決定するに先立ち、単位メッ
シュの画素の呼称を若干定義する。ｍｘｍサイズの単位
メツシュにおいて、最も外側（二位置する画素を周辺画
素と呼ぶ。周辺画素のうち、第１行と第ｍ行の画素（上
端と下端の画素）を縦方向の接続に関する接続周辺画素
、第１列と第１ｎ列の画素（左端と右端の画素）を横方
向の４１Ｇ−続に関する接続周辺画素とそれぞれ呼ぶ。

単位メッシュのサイズを３×３とした場合、単位メツシ
ュの周辺画素は第２図（ａ）においてノ・ツチングを施
して示した画素、縦方向接続の接続周辺画素は第２図の
）においてハツチングを施して示した画素、横方向接続
の接続周辺画素は第２図（Ｃ）において・・ソチングを
施して示した画素がそれぞれ該当する。

つぎに、各方向の接続周辺画素について、次のようなベ
リファラル値ＢｋまたはＷｋを定義する。

Ｂは黒画素を示し、Ｗは白画素を示す記号である。

またｋは、個々の接続周辺画素と同種類（白または黒）
の画素が接続方向に連結している個数である。

第；３図（ａ）に示すような３×３サイズの単位メッシ
ュ（合法パターン）の縦方向の接続周辺画素のそれぞれ
のペリフェラル値は、第３図（ｂ）に示す如くである。

すなわち、第１行・第１列の画素は白画素で、それを含
めて３個の白画素が縦方向に並ぶ。したがって、当該接
続周辺画素のペリフェラル値はＷ３である。第１行・第
２列の接続周辺画素は白画素で、縦方向（接続方向）に
白画素が２個並ぶから、そのペリフェラル値はＷ２であ
る。

同様に、第３行・第２列の接続周辺画素は黒画素で、縦
方向に黒画素は１個しか並ばないから、そのペリフェラ
ル値はＢ１である。また横方向の接続周辺画素のペリフ
ェラル値は、第３図（Ｃ）に示す通りである。すなわち
、第１行・第１列の接続周辺＋＋＋＋ｉ素は白画素で、
横方向（接続方向）（；白画素が３個並ぶから、そのペ
リフェラル値はＷ３である。第３行・第３列の接続周辺
画素は黒画素で、黒画素が横方向に２個並ぶから、その
ペリフェラル値はＢ　２である。

１−記のペリフェラル値をもとに、隣接する１−〕の単
位メソシュ相互間のノ；ターン接続法則を考える。ここ
では、くｚターン接続法則として、以下のよう（二接続
方向に隣接する個々の接続周辺画素間の接続法則と、接
続方向に隣接する接続周辺画素群間、つ捷り単位メツシ
ュ相互間の接続法則（二分けて考える。

（１）隣接する個々の画素間の接続法則（受容する接続
条件） Ｐ１接続二同種画素間（黒−黒、白−白）の接続で、両
画素のペリフェラル値（ｋ）の和が（ｎ−１）以上であ
る。

Ｐ２接続：異種画素間（黒−白、白−黒）の接続で、各
画素自体のペリフェラル値 も）が（ｎ−１）以上である。

ただし、ｎは２次元パターンの線（ディジタル線）の太
さであり、単位メツシュの一辺のサイズ以」−と仮定す
る。

（１１）単位メツシュ相互間の接続法則Ｓ１接続：全て
の隣接画素間がＰｉ接続の場合で、合法な接続として受
容可能。

Ｓ２接続：Ｂ２接続が２つ以−Ｌある接続。この接続は
、黒−白接続の両隣り（横方 向（二ついては上下、縦方向につイテ は左右）２つ以下に、白一点接続が １つ以」二存在する場合は受容不可能。

Ｓ３接続：Ｂ２接続が１つ以上ある接続。この接続は、
Ｂ２接続の黒画素の両隣り （横方向については上下、縦方向に ついでは左右）２つ以内の少なくと も一方の画素のベリフエラ値がＢ１ であるか、または、Ｂ２接続の白画 素の両隣り２つ以内の少なくとも一 方の画素のペリフェラル値がｗｌで あるときは受容不可能。また、Ｂ２ を含む場合で受容可能のときは８２゜ ８３両者を満たすときのみ。

１　　　　　以１−の接続法則の適用例を第４図ないし
第６図に示す（単位メツシュは３×３画素のサイズ）。

いずれの図でも、ハンチングを施した画素は黒画素であ
る。

第４図（ａ）のＡ−Ｄの４つの単位メツシュ（いずレノ
″ターンも合法パターン）の間の横方向の接続をみると
、個々の画素間（二ついては第４図０））（二示すよう
に全てＰ１接続で、受容可能なＳ１接続である。第５図
（ａ）のＡ−Ｄの４つの単位メツシュ間の横方向の接続
は、第５図（１））に示すようにＰ１接続とＢ２接続が
混在し、受容不可能なＳ２接続である。また第６図（ａ
）のＡ−Ｄの４つの単位メツシュ間の横方向の接続は、
第６図（ｂ）に示すようにＰ１接続とＢ２接続が混在し
、受容不可能なＳ３接続である。縦方向の接続について
は図示しないが、同様に適用すればよい。

七に述べた接続法則の妥当性を確認するために、以下（
二示すような実験を行なった。

すなわち、ＣＣＩ　ＴＴのファクシミリ用テストチャー
）Ｎｌｌ（英文手紙）の良画質原稿、汚染した原稿、″
かすれ”させた原稿のそれぞれを、３×３画素サイズの
単位メツシュに機械的（二分割して２次元パターン情報
（２値）を得た。この２次元パターン情報から、合法パ
ターンのみから成るシンボル表記画像を生成した。ただ
し合法パターンとして、前記の特許願に添付の明細書お
よび図面で示した６６種の合法パターンを用いた。

１−記のシンボル表記画像（＝おいて、　８１．８２，
８；３接続の受容可能条件のみを満たす（受容不可能な
Ｓ２接続、Ｓ３接続のない）合法パターン間の縦方向と
横方向の接続（合法接続と称す）の総数をそれぞれ調べ
た。また、接続総数（４５０，２２５）に対する各方向
の合法接続の比率を求めた。さらに、合法接続のうち白
−白接続数（オール白の単位メツシュ間の接続数）と、
それを除いた接続数の比率を調べた。これらの数値を表
１に示す。

表　　１ 表１かられかるように、良画′質原稿では合法接続の累
積は全接続数の９９．７％以４二に及ぶ。最も頻度の高
い白−白接続を除外しても、その比率は９６チ以上であ
る。この比−率は汚染原稿や”′がすれ″原稿では下・
かり、汚染原稿では８２％前後、かすれ原稿では８５チ
前後の累積比率を示した。したがって、これらの比率は
対象画像の状態（良質、汚染、かすれ）−を判定する１
つのパラメータとして利用できる。

一方、６６種の合法パターンの場合、縦、横各方向につ
いて可能な合法接続の種類は１５８２であり、各方向に
ついて可能な接続種類６６２＝　４３５６の約３６．３
％であった。また゛、第１図に示すような４つの単位メ
ツシュ相互で縦、横両方向が同時に合法接続となるよう
な合法パターンの組合せ数は３８４．５６２で、総組合
せ数６６４の２．０３％であった。このことは、単位メ
ツシュ間においても、対象がディジタル線の集合である
ということが強い拘束を持っているという１つの証拠で
ある。

以上の諸事項を総合評価すれば、前記の「Ｓｌ。

８２．８３接続の受容可能条件のみを満たす」ことが、
隣接する単位メツシュ相互間の接続が合法受容可能であ
るためのパターン接続条件として妥当であると結論する
ことができる。

つぎに、上記のパターン接続条件を用いて、シンボル表
記画像を合法シンボル表記画像へ変換する処理を説明す
る。

第７図において、シンボル表記画像上の任意の１つの単
位メソシュ（図中、ハンチングを施した学位メツシュ）
に注目すると、この注目単位メッ７ュは周囲の８個の単
位メツシュと接続している。

換言すれば、注目単位メソシュは、第１図で説明した４
単位メツシュ間の接続関係が（イ）、（ｏ）、（ハ）。

に）と４組存在することになる。

したがって、注目している単位メツシュの現在のパター
ン（合法パターン）が周囲の単位メツシュのパターンと
の関係で妥当であるかどうかを判定するには、基本的に
は（イ）〜に）の４組の接続関係ｌ　　を観察する必要
がある。そして、１組でも前記のパターン接続条件に適
合しない受容不可能な接続関係が存在すれば、注目単位
メツシュまたはその隣接の単位メツシュ（例えば注目単
位メツシュ真上のチ印を付した単位メツシュとの関係が
受容不可能な場合、図のどちらか一方）のパターンを他
の合法パターンに変換し、４組共に受容可能な合法接続
となるように修正を施す。この修正によって、修正され
た単位メツシュを含む他の接続関係が受容不可能となる
ことも起り得るので、接続関係の再チェックと修正を必
要なだけ繰り返す。このようにして、シンボル表記画像
を合法シンボル表記画像（二変換することができる。

以上、基本的な変換処理の手順を述べたが、これは以下
に述べるように簡略化することが可能である。

一般に、画像はラスク走査しながら処理する。

またラスク走査は、左から右へ向って主走査し、トから
下へ向って副走査するのが普通である。

そこで、リアルタイム処理を行なう場合には、走査の進
行に合せて次のような手順によって処理するのがよい。

今、第８Ｖにお・いて、）・ツチングを施した単位メツ
シュＥが読み取られたとする。この時点では、周囲の単
位メツシュＡ、Ｂ、Ｃ，Ｄは、シンボル表記画像への変
換処理、およびシンボル表記画像から合法／ンボル表記
画像への変換処理が終了している。

注目している単位メツシュＥのパターンをチェックし、
非合法パターンの場合はまず合法パターンへの変換（シ
ンボル表記画像への変換処理）を行なった後（二、そう
でなければ直ち（１以下の処理手順を実行する。

〔ステップ］〕

単位メソシュＡ、ｒ３．Ｄ、Ｅ間の接続関係と、単位メ
ツシュＢ、Ｅ、Ｃ間の接続関係を観測し、前記のパター
ン接続条件を満たす受容可能なものかチェックする。

〔ステップ２〕 両方の接続が受容できるならば、注目している単位メソ
シュＥ（二対する合法シンボル表記画像への変換処理を
終了する。一方あるいは両方の接続が受容不可能なら、
両方の接続が受容ｂ］能となるように、注目している単
位メツシ、：Ｉ：Ｅの・ζターンを他の合法パターンへ
修正し、処理を終了する。

なお、両方の接続を受容可能とする合法・；ターンが２
つ以上存在する場合は、例えば修正前の単位メツシュパ
ターンとのノ・ミング距離を考慮して選択する。

このような注目単位メツシュＥの・；ターンの修正のみ
で接続関係を受容可能にできるのは、次の理由による。

注目単位メツシュＥの処理時点では、単位メツシュＡ、
Ｄ間、Ａ、Ｉ’３間、Ｂ、Ｄ間の接続はチェック済みで
ある。したがって、単位メツシュＡ、Ｂ、Ｄ、Ｂ間の接
続が受容不可能な場合、単位メツシュＥのパターン修正
だけで、その接続を受容可能なものにできる。同様（二
、単位メツシュＢ、Ｅ、Ｃ間の接続が受容不可能な場合
も、単位メツ７１８，０間の接続はチェック済みである
ので、注目単位メツシュＥのパターン修正のみでその接
続を受容可能なもの（二できる。

尚、にではリアルタイム処理を想定したが、処理すべき
２次元パターン全体についてシンボル表記画像を生成し
たのちに、合法シンボル表記画像への変換処理を行なっ
てもよいことは勿論である。

以北に詳述したように、本発明による２次元パターン修
正方式は、単位メツシュ個々のパターンだけでなく、隣
接する単位メツシュ間および画素間の接続関係をチェッ
クしてパターンの修正を行なうため、ノイズが混入した
り歪んだ２次元パターンを高品質の２次元パターンに効
果的（−修正・復元できる。また前述したことから明ら
かなように、それ程大容量のバッファメモリを必要とす
ることなく、１回の画像走査だけでリアルタイムで処理
することも容易である。

【図面の簡単な説明】

第１図は単位メツシュの接続を説明するための図、第２
図は単位メツシュの周辺画素の定義を説明するための図
、第３図は単位メツシュのペリフェラル値を例示する図
、第４図ないし第６図は隣接する単位メツシュ間の横方
向接続の例を説明するための図、第７図はシンボル表記
画像から合法シンボル表記画像への基本的な変換処理を
説明するための図、第８図はより実際的な２次元パター
ン修正処理を説明するための図である。 代理人　弁理士　鈴　木　　　誠 第１図 第２図 （Ｌ）　　　　　（ｂ）　　　　　　（り第３図 第４図 （の　　　　　　　　　　　　（ｂ） 第５図 第７図 第８図 手続補正書（自発） 収ノ＼印１１（金゛釦 ０円 昭和５６年１２月２２目 特許庁長官　島　１）春　樹　殿 １°“］′件の表′バ　　特願昭５６−１０９７６６号
２・発明　の名称　２次元パターン修正方式３、補正を
する者 ・」１件との関係　　出願人 住　所　大阪府高槻市奈佐原元町１５８番地４、代理人
　　　＠１５１ 住　　所　　東京都渋谷区代々木２丁目３８番１２号　
線部ビル２０１Ｑ氏　　名　　（７３７６）　　　弁理
士　鈴　木　　　　誠電話０３　（３７４）　９６７１
番 ５　補正により増加する発明の数　なし６、補正の対象 明細書の「発明の詳細な説明」の欄 ７、　補正の内容 （１）　　明細件第８頁下から４行目の１ペリフアラル
値」を「ペリフェラル値」に補正する。 （２）　　明細書第１１頁５行目の「２一つ以下」を１
２つ以内」に補正する。 （３１明細書第１１頁１４・〜１７行目の記載を下記の
通りに補正する。 「　　　　方の画素のペリフェラル値カＷｌであるとき
は受容不可能。 すなわら、Ｐ２を含む場合で受容可能のときはＳ２．８
３両者を満たすときのみ。」１４）　　明ｔ＠再第１５
頁１２行目の１注目単位メッンユ２は、」を「注目単位
メツシュに対して、」に補正する。

Claims (1)

1. 【特許請求の範囲】 １．２次元パターンに出現する単位メツシュのパターン
   のうち特定のパターンを合法パターンとして予め選定し
   ておくとともに、隣接して存在することの許容される合
   法パターン相互間で満足されねばならない特定のパター
   ン接続条件を予め決定しておき、処理すべき２次元パタ
   ーンに合法ハターン以外の非合法パターンの単位メソシ
   ュが出現するとその非合法パターンはそれと特定の関係
   にある１つの合法パターンに変換し、該変換の処理を完
   了した、または該変換処理の途上にある２次元パターン
   上の隣接する単位メツシュ相互間のパターン接続関係を
   観測し、前記の特定のパターン接続条件を満足しないと
   きはそれを満足するように、当該隣接単位メツシュ中の
   １つ［ｈの単位メツシュのパターンを他の合法パターン
   へ変換することにより、前記の特定のパターン接続条件
   を満足して接続する合法パターンのみより成る２次元パ
   ターンを生成することを特徴とする２次元パターン修正
   方式。 ２、　非合法パターンは、それとの）・ミング距離にし
   たがって選んだ合法パターンに変換することを特徴とす
   る特許請求の範囲第１項記載の２次元パターン修正方式
   。 ３６　　前記のパターン接続条件は、隣接する単位メツ
   シュ間および個々の画素間に関して定義することを特徴
   とする特許請求の範囲第１項記載の２次元パターン修正
   方式。 ４．２次元パターンを左から右へ主走査し、」二から下
   へ副走査するとして、注目している単位メツシュと、そ
   の左、直上、左斜め上、右斜めＬに隣接する単位メツシ
   ュに関して前記のパターン接続関係を観測し、これら全
   ての単位メツシュ間で前記の特定のパターン接続条件が
   満足されるように該注目単位メツシュのパターンの変換
   を行なうことを特徴とする特許請求の範囲第１項記載の
   ２次元パターン修正方式。