JPH03269691A - 光学式文字認識システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、一般に、光学式文字認識の分野に関するもの
である。

（従来の技術及びその課題） 光学式文字認識装置は、プリントされたベージからテキ
ストを読み取り、適合するフォーマット、例えば、ＡＳ
ＣＩＩコードでテキストを表わした出力を送り出す。光
学式文字認識に利用できる基本技法には、２つある。１
つは、マトリックスマツチング（ｍａｔｒｉｘ　ｍａｔ
ｃｈｉｎｇ）に基づくものであり、もう１つは、特徴抽
出（ｆｅａｔｕｒｅ　ｅｘｔｒａｃｔｉｏｎ）に基づく
ものである。マトリックスマツチングには、文字のビッ
トマツプイメージと１組のテンプレートとの比較が必要
である。マトリックスマツチングの主な欠点は、所定の
フォントに制限されるということと、文字間隔に極めて
影響されやすいということである。これは、比例した間
隔をあけて配置される文字に関連した特有の欠点である
。

特徴抽出には、文字の選択された特徴の認識と、それら
の特徴と記憶された特徴のバージョンとの比較が必要で
ある。システムは記憶された特徴のバージョンに基づい
てトレーニングされる。特徴抽出に基づく技法には、多
くの異なるフォントを読み取る能力がよりすぐれている
という利点がある。しかしながら、既知の特徴抽出法は
、実施が複雑で、作業速度が緩慢である。

従って、本発明の目的は、特徴抽出に基づく光学式文字
認識を特に応用して、簡便且つ作業速度が早い、新規な
態様を得ようとするものである。これらの方法及び装置
のいくつかは、イメージ処理分野でより一般的に利用さ
れるものである。

（課題を解決するための手段） 上記課題を解決するために、本発明の第１の態様によれ
ば、光学的に文書を走査して、そのイメージを生じる走
査手段と；前記イメージ内のエツジを識別し、エツジの
経路を識別して、前記イメージ内で識別された各対象の
輪郭を示すデータを生じるエツジ識別手段と；前記エツ
ジ識別手段によって得られたデータに処理を施し、前記
イメージの文字を適合するフォーマットで表わしたデー
タを生じる手段から収る、光学式文字認識システムが提
供される。

本発明の第２の態様によれば、光学走査装置によって発
生する、ビクセルアレイから成るグレイレベルイメージ
で対象の輪郭を表すデータを生じるエツジ抽出器が得ら
れるが、前記エツジ抽出器は、前記イメージアレイを順
次走査してエツジを求め、各エツジの位置毎に、前記エ
ツジに関連して対象の輪郭をトレースするようになって
おり、また、各ピクセル毎にエツジ値を発生するエツジ
オペレータによってエツジの位置を指定するようになっ
ている。

本発明の第３の態様によれば、文書を走査し、該文書で
識別した各対象の輪郭を表わすデータを生じるタイプの
イメージ処理システムが得られるが、前記システムには
、前記対象の輪郭のうちグループをなすものを識別し、
前記輪郭を輪郭のブロックに形威し、前記ブロックの配
列を整えるためのページセグメンテーション機構が含ま
れている。

本発明の第４の態様によれば、文書を走査し、該文書で
識別される各対象の輪郭を表わしたデータを生じるタイ
プのイメージ処理システムが得られるが、前記システム
には、前記データを処理して、各輪郭の特定の特徴を識
別し、識別した特徴に従って、この輪郭をクラスに分類
する機構が備わっている。

本発明の第５の態様によれば、文書に処理を施して、前
記文書の文字を表わするデータを生じるシステムが得ら
れるが、この場合、前記文書の走査を行なって、そのイ
メージ生じさせ、エツジ識別手段が、該イメージデータ
に処理を加えて、該イメージにおいて識別される対象の
輪郭を表わしたデータを発生するようになっており、該
システムには、各輪郭のでこぼこの数を減らすための多
角形近似機構が設けられており、前記多角形近似機構は
、各対象の輪郭をたどって、所定の特徴を有する前記輪
郭上の一連のポイントを識別し、隣接して各対をなすポ
イント間の凹所の深さを測定し、所定の値未満の深さを
有する凹所を除去するというやり方で動作する。

本発明の第６の態様によれば、文書の走査を行なって、
そのイメージを生じさせ、前記イメージにおけるエツジ
経路を識別して、前記エツジ経路を表わしたデータに処
理を加え、前記イメージにおける文字を適合するフォー
マットで表わしたデータを発生することから戊る、文書
に処理を施して前記文書の文字を表わすデータを発生す
る方法が得られる。

本発明の第７の態様によれば、各輪郭をたどって、所定
の特徴を有する前記輪郭に沿った一連のポイントを識別
し、隣接した各対をなすポイント間における凹所の深さ
を測定し、所定の値未満の深さを有する凹所を除去する
ことから成る、文書のイメージにおけるエツジの輪郭を
表わすデータに処理を加え、前記輪郭の近似多角形が生
じるようにする方法が得られる。

（実施例及び作用） 第１図を参照すると、光学式文字認識システムは、スキ
ャナ／スキャナインターフェース１０、エツジ抽出器１
１、特徴抽出器１４及び組合せ装置／セグメンタ（ｍｅ
ｒｇｅｒ／ｓｅｇｍｅｎｔｅｒ）　１５と関連して動作
するテキスト配列機構１２、及び、最終類別器１６から
構成されている。スキャナは、グレイレベルのイメージ
を形成する。ことが可能な、市販の任意の適合する装置
とすることができる。

利用できるこうした装置の１つに、ヒユーレットバラカ
ード社のＨＰ９　Ｉ　９０Ａ型走査ジエツト装置（ｓｃ
ａｎ−ｊｅｔ　ｄｅｖｉｃｅ）がある。この装置の場合
、インチ当り３００ピクセルの解像度で１６グレイレベ
ルのイメージを形成する。この解像度の場合、Ａ４の各
ページを約３０秒で読み取ることが可能であり、４メガ
バイト（Ｍバイト）を超える記憶容量が必要になる。こ
のタイプの装置は、感光素子として線形電荷結合素子ア
レイを利用するものであり、文字「ａ」に関する典型的
なグレーレベルのイメージが、第２図に示されている。

第２Ａ図には、イメージの形態が示されており、第２Ｂ
図には、１６進数値によるイメージの形態が示されてい
る。これらの値において、「Ｏ」は黒を表わし、ｒＦＪ
は白を表わしており、その間の値１〜９、ｒＡＪ〜ｒＥ
Ｊはさまざまなグレイレベルを表わしている。

エツジ抽出器は、グレイレベルのイメージをラスターを
走査して、エツジの位置を突きとめる働きをする。エツ
ジが見つかると、閉ループが形成されるまで、ずっとエ
ツジをたどり、これによって、対象の輪郭、例えば、エ
ツジに関連する文字が形成される。エツジが閉ループを
形成しなければ、そのエツジは無視される。本光学式文
字認識装置の重要な特徴は、エツジ抽出器と関連したグ
レイレベルイメージの利用である。下記は、この装置に
よって得られる重要な利点である。

１、　黒領域でなくエツジを探すことによって、コント
ラストが十分に大きければ、任意のカラーを背景として
任意のカラーのテキストを読み取る能力が得られる。こ
れは、手動で陽画または陰画の選択を行なわなければ、
しきい漬方式では不可能である。

２、　　しきい値タイプの構成において、イメージをし
きい値で形成すると、そのイメージの非テキスト部分で
あっても、白の背景にテキトスと同じ種類の黒領域を形
成する。

このため、文字セルロケーションアルゴリズムに混乱を
生じることになる。グレイレベルイメージの場合、非テ
キトス領域のエツジは、はとんど、閉ループを形成せず
、従って、排除されることになる。エツジが閉ループを
形成する場合であっても、既知の文字と似ていないか、
あるいは、理にかなったテキストのラインを形成するこ
とはできない。従って、グレイレベルイのイメージによ
って、テキストと非テキストの弁別が行なわれることに
なる。

３、　　しきい値によるイメージの質は、文書記憶また
は新しい文書に用いるには不十分である。走査に関する
ハーフトーンアルゴリズムでは、テキストが破壊されて
しまう。

従って、１回の走査であるページからテキストとイメー
ジを得るには、グレイスケールが不可欠になる。

４、　　スキャナによるイメージ全体のラスター走査と
は別に、エツジ抽出器によって、文字のエツジだけが検
査される。詳細に分析されるイメージのピクセル数は、
従って、約９０％減少し、この結果、妥当な時間でペー
ジの処理を行なえるようになる。エツジ抽出器の出力は
、走査されたページの文字の輪郭を表わす、隣接ピクセ
ル間のステップから成る長いシーケンスである。テキス
ト配列機構へ送る前に、この出力は、多角形近似ステッ
プを受け、直線針のシーケンス、すなわち、多角形によ
って、文字の輪郭の近似が行なわれる。次のステージへ
送る前に、輪郭の近似を行なう主たる理由は、次の２つ
である。

１、　多角形近似、及び、特徴抽出に用いられる処理は
、両方とも、入力多角形におけるいくつかのポイントに
関して線形時間を費やすことになる。しかしながら、特
徴抽出の場合には比例定数がかなり大きいものとなって
しまう。従って、多角形近似によれば、時間を大幅に節
約することが可能になる。

２、　明らかになるように、文字認識に用いられる最も
重要な特徴の１つは、輪郭における凹領域の存在である
。その他の方法の場合には、擬似凹部を生じ、認識プロ
セスを混乱させることになる輪郭のジグザクが、多角形
近似によって取り除くことが可能である。

第３Ａ図及び第３Ｂ図には、多角形近似の一例が示され
ている。第３Ａ図は、文字ｒａＪの典型的なエツジ経路
を表わしており、第３Ｂ図は、多角形処理をすませた後
の相当する輪郭を示している。

エツジ抽出器の出力は、それぞれ、その境界を形成して
いる矩形の情報と共に、対象、普通は、文字のエツジ経
路を表わしている、一連のイメージプロブ（ｉｍａｇｅ
　ｂｌｏｂ）と考えることができる。これは、テキスト
配列プロセッサー１２、特徴抽出器１４、及び、組合せ
装置／セグメンタ１５に対する主入力である。特徴抽出
器の機能は、文字の輪郭から所定の基本的特徴を抽出す
ることにある。本構成において抽出のため選択された特
定の特徴は、次の通りである： １３　　凹部（Ｃｏｎｃａｖｉｔｙ）　。一般的には、
凹部は、充填することのできる、また、いくつかの凸状
ポイントを含む領域である。

２、　クローン＋　（Ｃ１ｏｓｕｒｅ）　。クロージャ
は、文字によって完全に囲まれた背景の領域である。第
４図の場合、クロージャは、区域２１で示されている。

「ｐ」やｒｅＪのような所定のフォントの文字は、不完
全なりロージャでプリントされる。検出しなければなら
ないのは、物理的にクロージャではなく、機能的クロー
ジャの存在である。

３、　　ライン（Ｌｉｎｅ）。ラインは、輪郭の直線部
分である。曲線が少数の直線に変換されるので、ライン
検出は、多角形近似の場合やっかいになる。従って、そ
れらは、実際の直線に比べて不明瞭になる。

４、　軸（Ａｘｅ）。凹部またはクロージャのない対象
に対し、軸を探索する。軸の特徴によって、凸状対象の
長軸と短軸の比率が測定される。それは、ドツトや、普
通のコンマのような文字間の区別に用いられる。

５、　対称（Ｓｙｍｍｅｔｒｙ）　ｏ対称は、軸の両側
において文字を部分的に比較することによって測定され
る。対称の測定は、イタリック体のテキストの場合、対
称軸が測定方向に対して垂直なならないので、困難であ
る。

輪郭が太い場合、上述の特徴を利用すると、特徴抽出器
によって、未知の文字と一般的な文字クラスとの突合せ
が行なわれる、すなわち、それによって、プロブとなる
ＡＳＣＩ　Ｉ文字のクラスまたは集合が生じることにな
る。一般的な文字クラスのＡＳＣＩＩ文字へのマツピン
グは、ｌ対１にはならない。例えば、「ｇ」のような、
若干の文字では２つ以上の基本形状をとる。こうした文
字の場合、同じＡＳＣＩＩ文字にマツピングする２つ以
上のクラスを備えなければならない。

より一般的なケースには、いくつかの文字の１つについ
てマツピングが可能な単一クラスがある。例えば所定の
フォントの中には、文字「１」　（数字のイチ）、「ｌ
」　（小文字のエル）、及び「Ｉ」（大文字のアイ）が
、同じになるものもある。それらを区別する唯一の方法
は、文脈である。特徴抽出段階において、これら３つの
文字のさまざまな物理形状を扱ういくつかの一般クラス
が存在する。これらのクラスは、はとんど、特定の形状
に従って、２つまたは３つのＡＳＣＩＩ文字の１つにマ
ツピングされる。

テキスト配列段階の主たる機能は、文書構造を識別して
、文書内のテキストの配列を補正することである。テキ
トス配列における主なステップは、以下の通りである二 Ａ、　文書内の独立した領域（ブロック）を識別する。

Ｂ、　　ブロックをテキストまたは図形に分類する。

Ｃ０テキストブロックを論理読取り順に配列する。

Ｄ、　テキストブロックを文字順に配列する。

Ｅ、　　白の間隔文字を演鐸する。

Ｆ、　慎重に分割した文字の部分を関連づける。

Ｇ、　組み合わせられる可能形性のある文字を識別する
。

Ｈ９幾何学的に文字に固有のあいまいさ（フォントの特
徴である）を分解する。

組合せ装置／セグメンタ１５は、意図せぬ分解文字の一
部として識別された２つ以上のプロブの輪郭を組み合わ
せたり、あるいは、２つ以上の文字のリゲーチュア（ｌ
ｉｇａｔｕｒ＋ｓ）として識別されたプロブの輪郭をセ
グメント分割し、たりしようとする。この処理によって
、写真複写機からの出力のような比較的質の劣るコピー
を読み取ることが可能になる。

最終類別器１６は、きわだってあいまいな部分を分解す
ることによって、各プロブに関連したＡＳＣＩＩ文字に
関する最終判定を行なう、例えば、最終類別では、文脈
情報を利用することによって、大文字と小文字の区別を
行なうこともできる。また、文脈を利用することにより
、数字の「１」と、小文字のｒｌＪと、大文字のｒＩＪ
のような難解なあいまいさを分解することもできる。最
終類別器に利用し得る技法には、辞書編集の規則（語に
数が含まれない）、マルコフ連鎖解析、及び、辞書探索
が含まれる。

以上は、光学式文字認識システムの全体構造の概要であ
る。この全体構造のうちいくつかの要素については、次
に、さらに詳細に述べることにする。

前述のように、本システムにおける重要な要素は、エツ
ジ抽出器である。エツジ抽出器の機能については、図面
のうち第５図に表わされている。エツジ抽出器に対する
人力は、２８で示すように記憶されたビクセルのアレイ
から成る、グレイレベルのイメージである。このアレイ
に対し、３０で示すようにラスター走査が施され隣接す
るビクセルとのグレーレベルの差が大きいエツジの位置
がつきとめられる。エツジの位置が分ると、エツジ抽出
器が作動して、３１で示すように輪郭をトレースする。

閉ループのエツジ経路の位置が３２で示すように確定す
るまで、このトレースが続行される。この閉ループ経路
の近似化が３３で示すように実施されて１．多角形近似
が得られることになる。３４で示すように輪郭を関連づ
けることによって、テキスト配列プロセッサーに送られ
る対象のプロブ輪郭が生じる。

エツジ抽出器は、エツジが閉ループを形成するまで、新
規のエツジオペレータを利用して、輪郭まわりにおける
エツジの位置をつきとめ、それをたどっていく。このオ
ペレータは、隣接するビクセル間における移動方向に垂
直なエツジ強度を見つけるように設計されている。第６
図には、オペレータの動作方法が示されている。

第６ａ図には、３×３のビクセルのアレイが示されてい
るが、これは、−船釣には２．４００Ｘ３゜３００ピク
セルからなる。走査を受けた文書のイメージの小部分を
なすものと理解される。表示のように、エツジ抽出器は
イメージのラスクー走査を行ないｒＸＪは走査時におけ
る現在点を表わす。「Ｘ」が現在位置とすると、連鎖コ
ード「Ｎ」を備えた次の位置のエツジ値は、連鎖コード
（４＋１）（モジューロ８）と（Ｎ−１）（モジューロ
８）を備えた点におけるグレイレベル間の差である。例
えば、第６ａ図を参照すると、連鎖コードＯを備えた点
におけるエツジ値は、１のグレイレベルから７のグレー
レベルを引くことによって得られる。このステップが、
第６ｂ図に示されている。第６ｃ図には連鎖コード７に
対する該オペレータによる同様の表現が示されている。

注目すべきは、各方向毎に１つのオペレータしかなく、
その結果は、符号がつけられるという点である。特定の
しきい値を超えるエツジ値があれば、エツジの表示が行
なわれる。

エツジの位置が分ると、エツジ追跡アルゴリズムが実施
される。主たる処理は、イメージのラスター走査に、連
鎖コード４に対応するエツジオペレータを用いることで
ある。こうして、ラスクー走査によって、普通はテキス
トの文字である新しい対象の上部エツジの位置がつきと
められる。特定の開始しきい値を超え、いずれかの符号
が付されたエツジ値を有するこうした点の位置を突きと
めると、ラスター走査によって、イメージ内でビクセル
１つ針下のチエツクが繰り返されることになる。エツジ
の位置が突きとめられる場合、そのエツジが確実に有効
であるためには、エツジの符号が同じで、強さは開始し
きい値を２×２のセルにわたって上まわっていなければ
ならない。これらのエツジのうち最も強いエツジから明
るいグレイレベルと暗いグレイレベルを利用して、明る
いグレイレベルと暗いグレイレベルの平均である中心値
が求められる。エツジを検出すると、ラスター走査が中
断され、より高いエツジ値を有する点からライン追跡プ
ロセスが開始する。２重にチエツクを行なって、エツジ
が有効であることと、追跡が最強のエツジ値から開始さ
れたことを確める。中心値に集中するグレイ値の領域は
、輪郭をたどる際「グレイ」とみなされ、それを上まわ
ると「白」とみなされ、それを下まわると「黒」とみな
されことになる。

追跡アルゴリズムは、基本的には、次のように行なわれ
る。ライン追跡が開始すると開始点、すなわら、第６図
において連鎖コード４で示した点から左へトラッキング
が行なわれ、輪郭のアンチカンタ−（ａｎｔｉ−ｃｏｕ
ｎｔｅｒ）追跡を達成しようとする。最後の方向の連鎖
コードＮを確めると、現在の位置から、連鎖コードＮ−
２、Ｎ−１、Ｎ、Ｎ＋１及びＮ＋２（モジューロ８）を
備えた５つの点のそれぞれについてエツジ値が得られる
ことになる。正しい符号を有し、しきい値を超え、エツ
ジの集合がこの位置及び方向に対応する、５つ以下の点
を規定する。エツジの集合から、最強のエツジ値を備え
た点が分る。次の点の選択は、自明のことではないが、
はとんどの場合、最強のエツジ値を備えた点になる。

これは、図面中、第７図に示されている。第７ａ図には
、５×５のビクセルによるアレイが示されており、該ア
レイの各ます目における値は、図面のうち第２図に示し
た文字ｒａＪの部分に対する実際のグレイレベルを表わ
している。

現在の点が、円で囲んだ点、すなわち、点８０であり、
方向４における最後の移動であったとすると、円８０で
計算されることになるエツジ値は、第７ｂ図に示す通り
である。次のステップは、第７ｂ図に示すエツジ値１３
に対応する角の丸います目８１である。第７ｃ図に示す
エツジ値は、このまず目で計算されるエツジ値である。

第７ｄ図には、計算されるエツジ値が、最後の連鎖コー
ドによってどのように変化するかが表わされており、ひ
し形ます目８２におけるエツジ値が示されている。

第７図に示すように、各ステップ毎に、いくつかの有効
なエツジ値が存在する。エツジをたどるプロセスが進行
している限り、エツジ経路の点に、現在、それらが処理
中の輪郭の一部をなしていることを表わすマーキングが
施される。

各ステップにおいて、マーキングを施される点が１つし
かない場合、後で、ラスター走査によって同じエツジに
おける未使用の点が確められて、再び輪郭をたどる試み
がなされることになる。従って、下記制約条件下におい
てできるだけ多くの点（３つが限度）にマーキングが施
される。

Ａ。

最強のエツジには、必ずマーキングが施される。

マーキングを施される全ての点は、エツジ集合をなすも
のであって、追跡しきい値を超えるエツジ値を有するも
のでなければならない。

マーキングを施される全ての点は隣接していなければな
らない。

従って、しきい値を４と仮定すると、マーキＢ。

１ ングを施される点は、第７図の場合、第７ｂ図が１３．
１０、第７ｃ図が１１．１２、第７ｄ図が１２になる。

いつでも、追跡しきい値に対して点が見つからない場合
、その対象を放棄し、エツジ全体が削除されたものとし
てマーキングがやり直される。追跡プロセスは、エツジ
が失なわれるか、閉ループが完成するか、あるいは、エ
ツジが前に完成した輪郭と一致するまで続行される。エ
ツジが満足のゆく閉ループを形成する場合には、ループ
の全ての点について、用いられたものとしてマーキング
がやり直される。エツジが完全な場合に、全てのマーク
を変更する理由は、他のラインとの衝突と、ループの閉
鎖との区別がつくようにするためである。

第７図には、また、次のステップが明確な選択でない場
合もあることが示されている。例えば、第７Ｃ図の角の
丸います目において最高のエツジ値は１２と１１である
。多くの場合、必ずしも常にそうこうなるわけではない
が、この選択は、その結果にあまり影響を及はすことは
ない。

この選択が影響する可能性があるのは、以下の状況の場
合である。

Ａ、　　フォントによって、ライン幅が変動する場合が
ある。ラインの最も細い部分で、ラインを横切るエツジ
経路をたどる可能性があり、このため、間違って文字の
分解を行なうおそれがある。

Ｂ、　文字の中に、ごく近接して並置された状態にプリ
ントされたものがある。２つの文字がほとんど触れそう
になっている点では、いずれかの文字を横切る際、二通
りの判定を行なう可能性がある。両方の判定とも正しく
なければならない、さもなければ、方の輪郭が、もう一
方と衝突し、一方または両方の文字を損うことになる。

Ｃ１エツジかにじんでいる場合、後続のステップでエツ
ジが消失するのを回避するため、より弱いエツジ値に対
応する経路を選択し。

なければならない可能性もある。

こうした問題について、図面のうち第８図に例示されて
いる。第８ａ図には、図面のうち第２図に示された文字
ｒａＪの一部、すなわち、輪の上部が縦線と交わる点に
おけるｒａＪの部分が示されている。第８ｂ図には、円
で囲んだ点９０のエツジ値が示されているが、図示のよ
うに、２つの点がエツジ値１１を有している。これらの
点のそれぞれからのエツジ集合が、第８Ｃ図及び第８ｄ
図に示されており、可能性のある宛先が、第８ａ図に角
の丸います目とひし形をしたまず目によって指示されて
いる。角の丸います目は、正しい経路であり、ひし形の
ます目は、ループの間違った側である。

上述の問題Ｂについては、第９図に示されている。第９
ａ図は、一対の間隔の密な文字に関する正しい輪郭が示
されている。各輪郭をたどる開始点は、十符号で表示さ
れている。第９ｂ図の場合、ｒｔＪのトレース時に異な
る選択を行なった結果、文字が結合している。第９Ｃ図
の場合、同じ経路をたどっているが、第２の経路に対す
る判定が異なるため、窮状に陥る領域を通ってしまって
いる。結果として、「ｉ」は完全であるが、エツジが、
ループの開始部で閉じず、従って、両方の文字が、共に
、損なわれることになった。第９ｄ図には、第９ａ図の
ように、正確にｒｔＪをたどったが、「ｉ」についても
同じ経路を選択し、完成したｒｔＪと衝突して、削除さ
れた状況が示されている。この問題に対する解決方法は
、現在の点以降のエツジ値について、いくつかのステッ
プを先読みし、どの経路を選択すべきか判定することで
ある。

先読みによって、完成したラインと衝突することにより
消失することになるエツジ、及び、その経路を検出する
ことが可能になる。問題Ｃを回避するため、代替経路の
選択が可能である。

このアプローチに関する難点は、妥当な深さまで可能性
のある経路を探索することによって費やされる処理時間
の量が考えられる。

最適のエツジ経路を適度な時間内に選択するには、多種
多様なアルゴリズムがあり、下記は、比較的単純な例で
ある。それは、上述の失敗モードに基づくものである。

大部分の輪郭のほとんど全ての点で、いくつかの選択が
生じるので、いくつかの代替上・ｙジ経路について選択
を行なうアルゴリズムは、できるだけ迅速であることが
必要になる。ただし、その選択がきわめて重要になるケ
ースは数の上で、全体のほんの一部にしかならない。

最も重要な考慮事項は、第９Ｃ図及び第９ｄ図に示す状
況によって文字が損われるのを防ぐことである。文字の
結合は、それほど重要ではない。

第２図には、ｒａＪの輪が縦線と交わるところに、かな
り暗いラインの生じることが示されているが、その太さ
は、単一のピクセルの幅である。第８図で特徴となる問
題は、エツジオペレータの失敗によるものである。

問題となるエツジ点において、「白」から「グレイ」、
または「グレイ」から「黒」への遷移が生じる場合、エ
ツジ点の選択を行なう有値に加算することである。遷移
が「白」から「黒」の間で直接生じる場合、この値は２
倍になる。

候補のエツジ点は、考慮の対象となるためには、ともか
く、正しい方向へ遷移するものでなければならない。エ
ツジ点におけるグレイ値と「中心値」との差に等しい量
が、エツジ値から引かれる。この結果、エツジ経路が、
そのエツジの開始時に認められたのと同じ中心値に向け
られることになり、通常、細いラインの場合に生じる誤
りエツジの大部分が除去される。

第９図に示すタイプのエツジの消失及び衝突を防ぐには
、適度なレベルの先読み（４ステツプ）が、不可避的に
必要になる。ただし、時間を節約するため、エツジ経路
アルゴリズムによる先読みは、最強のエツジ経路に限ら
れる。最強のエツジ経路が、消失したり、あるいは、別
のエツジと衝突したりする毎に、代替案が考慮される。

第９Ｃ図に示すように、エツジが、ラインの開始から離
れたところでそれ自体と衝突する場合、そのラインは放
棄されない。閉じた部分は、受けいれられ、代替エツジ
経路の存在する点まで逆にたどってから、ラインの残り
の部分について続きが行なわれる。このアプローチによ
って、上述の経路選択問題の多くを解決することかでき
る。

エツジ抽出時に用いられる「中心値」は、しきい値とみ
なすことができる。エツジ抽出器の代替バージョンの１
つでは、局部領域におけるグレイレベルのヒストグラム
解析によって、しきい値が評価される。これは標準的な
技法である。（１９８２年、アカデミツクプレス（Ａｃ
ａｄｅｍｉｃＰｒｅｓｓ）発行のエイ・ローゼンフェル
ト（Ａ　、　Ｒ。

５ｅｎｆｅｌｄ）　、エイ・シー・カフ（Ａ、Ｃ，Ｋａ
ｋ）による「ディジタル画像処理（Ｄｉｇｉｔａｌ　Ｐ
ｉｃｔｕｒｅ　Ｐｒｏｃｅｓｓｉｎｇ）第２版第２巻の
７０〜７１頁参照）。しきい値は、２つのピーク間の傾
斜の重みつき平均を計算することによって得られる。

ピーク間の傾斜におけるグレイレベルの分布の差異を利
用して、追跡しきい値を計算することができる。この操
作は、イメージにおける小さな区画に対して行なわれ、
局部的しきい値か計算される。

計算されたしきい値は、ラスター走査において、単純な
しきい値として用いられるのを別にすれば、強いエツジ
の探索ではなく、通常のエツジ抽出プロセスの場合、中
心値として用いられることになる。

以上から明らかなように、全てのエツジラインは、別個
に検出され、追跡されるが、エツジには関連しているも
のもある。例えは、文字ｒｏＪの内側エツジと外側エツ
ジについて考えてみる。エツジは、両方とも、「Ｏ」の
一部であり、特徴を正確に抽出するためには、出力構造
が関連していなければならない。内側のエツジが外側の
エツジによって完全に包囲されていることを記録する必
要がある。

これを扱う方法の１つに、ネスティングツリー　（１６
ｓｔｉｎｇ　ｔｒｅｅ）があるが、これは複雑なプロセ
スとなるので、以下に、より単純なプロセスを示す。

閉ループＣＩのまっすぐな矩形の境界をなす最小のボッ
クスを考えてみる。ボックスの底部左手コーナの座標を
（ｘｍｉｎｌ、ｙｍｉｎｌ）とする。

同様に、ボックスの上部右手コーナの座標を（ｘｍａｘ
、、ｙｍａｘ、　）とする。Ｃ１における点の座標が（
ｘ＋、ｙ＋）で、ｉ＝Ｉ、ｎとすると：ｉ＝１、ｎに対
し、 ｘｍｉｎｌ＝ｍｉｎ（ｘ、）、ｘｍａｘ、＝ｍａｘ（ｘ
、）ｉ＝１．ｎに対し、 ｙｍｉｎ　、　＝　ｍｉｎ　（ｙ　、　）、ｙｍａｘ　
１　＝　ｍａｘ　（ｙ　＋　）完全にＣ１の役目をする
第２の閉ループＣ２が与えられると、明らかに、Ｃ２の
矩形の境界をなすボックスは、Ｃ１の境界をなすボック
ス内に位置することになる、すなわち、ｘｍｉｎ、＜ｘ
ｍｉｎ２、ＸｍａＸ４　＞　ＸｍａＸ＊、ｙｍｉｎｌ＜
　ｙｍｉｎ＊、及びｙｍａｘ、〉ｙｍａｘ２ということ
になる。

テキストの処理しか行なわない場合、そのページにおけ
る全ての対象の境界をなすボックスが、２次元のパケッ
ト分類を利用して分類される。パケットサイズは、最小
の許容可能文字サイズに設定されるので、１頁における
パケット数は、ピクセル数を大幅に下まわることになる
。

各輪郭が完成する毎に、境界をなすボックスの上部左手
コーナに従って、関連するパケットに挿入される。ペー
ジが完成すると、パケットの単純な線形探索を利用して
、完成した全ての輪郭の位置が確かめられる。各輪郭毎
に、境界をなすボックスでカバーされる小さな局部領域
のパケットが、探索される。包囲されている他の輪郭が
見つかると、回復されて、文字におけるホールとして記
録される。

パケット対ビクセル比が極めて小さいので（約２５６分
の１で十分）、このパケット分類によって費やされる処
理時間は最短になるが、ＡＳＣＩＩ文字集合における全
ての文字についてネスティング関係を見つけ出すことが
保証される。ただし、　ＡＳＣＩＩ文字集合において、
パケット分類で間違った結果を生じる可能性のある文字
が１つ存在する。それは、まずありそうにないことであ
るが、パーセント記号「％」がプリントされていて、そ
の円が、その斜線によって囲われているように見える場
合である。

この状況については、第１１ａ図に示されている。これ
は、唯一の例外なので、簡単に解決される。スペース（
ｘ、ｙ）がスペース（ｘ　＋　ｙｓ　ｘ　　ｙ）に変換
され、回転したスペースについて、やはり、境界をなす
ボックスの計算が行なわれる場合、両方のスペースにつ
いて包囲状態をテストすることによって、正しい結果が
確保される。

この単純な回転変換の結果が、ｌｌｂ図に示されている
。

パケット分類の唯一の目的は、ｒｏＪのようなホールを
有する文字のネスティング情報を得ることにあるが、広
範囲のページレイアウトに関し、この操作によって、副
次的に文字を理論的テキスト配列をなすようにうまく分
類可能である。

エツジ抽出器の出力は、直線でつながれた一連の点から
成る輪郭とみなすことかできる。ある点の両側のライン
は、互いに９０°をなして延びるか、互いに４５°をな
して延びるか、あるいは、共線上に延びるかのいずれか
である。

多角形抽出プロセスは、本質的に、２段階のプロセスで
ある。最初の段階で、固定された１点、例えば、９０゛
曲がった点を識別し、第１３図に示すように２方向から
成るセグメントを識別する。

プロセスが開始すると、直角の曲り部ζまたは、同じ方
向または向きにおける２つの４５゛の曲り部の第１の点
の位置を突きとめる。次の点での曲り部が４５°の場合
、このプロセスは、セグメントの端が見つかるまで、続
けられる。

また、そのセグメントを構成する各方向の全長にわたっ
て検討される。始点からのラインか方向１であり（第１
４図参照）、始点に後続する点からのラインが、方向２
の場合、方向Ｘが方向２に等しければ、また、Ｘの長さ
が長さ１を超えるか、あるいは、セグメントにおける全
ての方向２の合計が、全ての方向１の合計を上まわるこ
とになれば、始点が移動して点Ｘに戻る。

次の点は、固定点としてマーキングが施される。

そのセグメントが終了すると、すなわち、次の方向が方
向１または２ではない（第１４図）点に達すると、プロ
セスは、そのセグメントからある点に戻るが、前述の点
が始点の場合、新しい終点が固定される。さもなければ
、最後の曲り部が９０°の場合、または、最後のセグメ
ントの長さが最後から２番目のセグメントの長さを超え
る場合、または、１つの方向における全長の合計が、他
の方向からの全長の合計を超える場合、その終点が文字
どおりの終点として固定される。さもなければ、終点は
、最後の意思外の点になる。

このプロセスは、もとの始点に達するまでそのループで
続行される。これは、多角形近似の第１の段階を表わし
ている。第２の段階に進む前に、該プロセスは、固定の
マーキングが施された隣接する２点が存在するかを識別
し、また、これらの点間のステップで、長さ値１を有し
ている場所、及び、その長さの両側の点が固定されてい
ない場所を識別する。この状況が識別されなければ、こ
の２つの固定点は、固定されていないものとみなされる
。

段階２において、プロセスは、ループを進行し、まず、
後続の計算に備えて補正値の計算を行なう。、これは、
エツジ抽出器から出力されるもとのループに基づいて行
なわれる。該プロセスでは、各セクション毎に、主経路
の両側においてマーキングの施された点の数がカウント
される。さらに、カウントの差が確められ、そのスケー
リングを行なって、ステップ数で割られる。これが補正
値である。該プロセスは、次に、非固定点が後続する固
定点を探す。固定点を見つけることができなければ（あ
りそうにないことだが）、任意の１つを選択する。最初
に位置決めされた固定点から始めて、該プロセスは、次
の固定点を識別し、関数によって、固定点間の近似を行
なう。残りの固定点について、これを繰り返す。

該プロセスでは、隣接する固定点をつなぐライン上のあ
る点からこの２つの固定点の間における各中間点までの
垂直距離が計算される。このプロセスの実施時には、前
述の補正値が用いられる。該プロセスにおいて、垂直距
離の２乗が合計され、平均２乗偏差、及び、該固定点を
つなぐラインからの最長垂直距離が求められる。

最大及び平均２乗偏差が、矩形の境界をなすボックスの
輪郭の最長の辺と比較される。いずれかが、ある限界を
超えると、２つの固定点は接合されない。さらに、該プ
ロセスが、再び、繰り返されることになり、固定点が最
長垂直距離を有する点まで戻り、必要な基準に合致する
点が見つかるまで、このプロセスが反復される。

該プロセスは、これらの計算を繰返し、基準に合致する
固定点をつないで、多角形として近似した輪郭を形成す
るループを進めていく。このデータは、さらに、特徴抽
出段階、及び、組合せ及びセグメンテーション段階に送
られることになる。

エツジ抽出及び多角形近似がすむと、次のプロセスは、
特徴抽出と、組合せ及びセグメンテーションに関連した
テキスト配列である。テキスト配列段階１２に対する主
入力は、プロブ輪郭と、それらの境界を形成する矩形の
集合である。

これは、他のイメージセグメンテーションシステムに対
する始点とは異なる点に注目することが重要である。テ
キスト配列段階の動作に関する機能図が、図面のうち第
１２図に示されている。

図示のように、該プロセスにおける第１のステップでは
、１００で表示の文書の区分化を行なう。

プロブ輪郭が、特徴抽出１０１のために送られ、識別さ
れたブロックが、ブロック記憶装置１０２に送られる。

ブロックタイプ識別機構１０３が設けられており、その
後、プロブは、１０５で示すように、関連づけられて、
行にまとめられる。

最後に、分類されたプロブ輪郭は、文字選択１０６を受
けることになる。この機構からの出力は、エツジ抽出器
から受信する各プロブに対する文字の任意選択を表わし
ている。キテスト配列段階についてさらに詳述する前に
、特徴抽出機構１４において特徴の抽出を行なう方法に
ついて説明することにする。この機構は、エツジ抽出器
から出力される輪郭多角形から特徴を抽出する。

先行技術による構成について考察してみると、文字輪郭
の処理に利用することが可能な多くの文字属性が存在す
ることが分る。本構成の場合、下記のように、文字認識
の重要度が低下する順に並べられた１つの集合をなす５
つの機能属性が選択された： １、　凹部（Ｃｏｎｃａｖｉｔｙ）　。凹部は、輪郭の
凹状の部分として定義される。これには、ペイ（ｂａｙ
）　、インレット（ｉｎｌｅｔ）　、ノツチ（ｎｏｔｃ
ｈ）　、及び、フック（ｈｏｏｋ）として知られる凹部
に加え、交差、結合、及び、マーカによって生じる小さ
な凹部も含まれる。

２、　閉鎖（Ｃ１ｏｓｕｒｅ）　。例えば、これは１９
７４年発行の「インターナショナル・ジャーナル・オブ
・マン−マシン・スダディーズ（Ｉｎｔｅｒｎａｔｉｏ
ｎａｌ　Ｊｏｕｒｕａｌ　ｏｆ　Ｍａｎ−Ｍａｃｈｉｎ
ｅＳｔｕｄｉ＃−ｓ）第６巻第６号７０１〜７１４頁に
おける「現象モデル属性に基づく文字認識：その理論と
方法（Ｃｈａｒａｃｔｅｒ　Ｒｅｃｏｇｎｉｔｉｏｎ　
Ｂａ５ｅｄ　ｏｎ　Ｐｈｅｎｏｍｅｎｏｌｏｇｉｃａｌ
　Ａｔｔｒｆｂｕｔｅｓ　：　Ｔｈｅｏｒｙ　ａｎｄ　
Ｍｅｔｈｏｄｓ）　Ｊと題するシリマン・アール（Ｓｈ
ｉｌｌｍａｎ　Ｒ，）による博士号論文において定義さ
れているような機能的閉鎖を意図するものである。

３、　　ライン（Ｌｉｎｅ）。ラインは、シャフト（５
ｈａｆｔ）、アーム（ａｒｍ）または、レッグ（ｌｅｇ
）から生じる輪郭の直線部分である。

軸（Ａｘｉｓ）。軸は、凹部または閉鎖のない文字につ
いてのみ定義される。軸は、対象の長軸の方向を示し、
長軸と短軸の長さの比が測定される。それを利用するこ
とによって、シルマン（Ｓｉｌｌｍａｎ）の属性で扱わ
れていない。ＡＳＣＩＩ文字集合内の属性が分解できる
ことになる。−例として、ドツトと、普通の引用符また
はコンマとの間におけるあいまいさが分解される。

５、　対称（Ｓｙｍｍｅｔｒｙ）　。対称は、垂直軸と
水平軸のいずれかにおいて測定することができる。

下記は、上述の特徴が、エツジ抽出器によって与えられ
る多角形の輪郭近似から抽出される方法、及び、それぞ
れを数値的に表わす方法に関する説明である。各特徴の
抽出について詳述する前に、輪郭における点及びベクト
ルに関する簡潔な表記について、以下に示すことにする
。

認識すべき対象は、整数の座標を有する全部でｎ個の点
によって形成される。１つ以上の閉ループから構成され
る。ｎ個の点を直線性によって順番につなぎ、最後の点
が最初の点につながるようにすると、左に向いた閉ルー
プが形成される。すなわち、その文字の内側は、ある点
からそれに後続する点へ移動する際、常に左側に位置す
ることになる。従って、外側のループは、反時計廻りの
順序で記憶され、ホールは、時計廻りの順序で記憶され
ることになる。

ｉ番目の点の座標対（ｘ＋、ｙ＋） Ｐ＋　＋　Ｉ　　Ｐ＋の後続点の座標を表わす。

これは、Ｐ、を含む閉ループまわりに おける次の点であって、必ずしも（ｉ ＋１）番目の点になるとは限らない点 に注意すること。

Ｐ、−１同様に、Ｐｌの先行点。

Ｐ、Ｐ、　　　点Ｐ、から点Ｐ、へのベクトル。

Ｐ５、Ｐ、異なる閉ループ上に位置することもあり得る
。

Ｐ、Ｐ、や、の省略形。

Ｐ＋ＰＩ−１の省略形。

＝ａ、ｂ、＋ａ、ｂ、が、２つのベクトルのスカラー積
である。

＝ａ、ｂ、＋ａ、ｂｘが、２つのベクトルのクロス乗積
である。この結果は、スカラ ー値である。

ｐ、、ｘｐ、−＞　＝　０の場合は、凸部、そうでなけ
れば、凹部。

ＰＩＰｌ　１　”＝Ｐ＋ＰＢＰ＋Ｐ１＝　（ＸＩ　　Ｘ
＋）’　＋　（Ｐ＋　　Ｐ＋）”Ｐ。

　− Ｐｌ＋ −ｂ Ｘｂ は、ベクトルＰ、Ｐ、の平方ユークリッド長、すなわち
、Ｐ＋と１８間の距離である。

本明細書において、距離の２乗、長さ の２乗等の用語は、この測定値を表わ している。

Ｐ、ＰＩ　ｌ　Ｉ　ＰＩＰ、Ｉ　”の平方根。

凹部は、輪郭の凸状ハル（ｈｕｌｌ）上に存在しない、
輪郭の一部である。輪郭の凸状ハル上に存在しない点の
各集合毎に、１つ以上の凹部が生じることになる。

ハルのラインから垂直方向に離れた距離に関して、局部
的に最小となる凸部が凹部に含まれている場合、その凹
部は分割される。（）＼ルラインは、輪郭が一致しない
凸状のハルの一部である）。最小部分の両側における凹
部の深さは、分割が行なわれる最小点までの深さの有効
な一部を形成しなければならない。

分割の場合、その方向がもとのハルラインの方向である
場合を除いて、２つの部分は、全く通常の凹部のように
扱われる。第１５ａ図には、最も広い部分の幅と比較し
て、最も狭い部分の幅が、極端に狭ければ、凹部は、閉
鎖を形成することもあり得る。

凹部にそれ以上分割が含まれていないということが識別
されると、局部的な最小幅が中間点までに存在する場合
、両端が最狭の点まで移動する。第１５ｂ図参照のこと
。

ハルラインと平行に、その深さの１７４と３／４のとこ
ろで凹部を横切るラインを引くと、台形が形成されるこ
とになる。第１５ｂ）図には、その台形が示されている
。この台形の利用によって、凹部の数値成分のいくつか
が生じることになる：（ａ）　　凹部の方向は、値域〔
０，６３）に対して量子化されたハルラインの方向であ
る（最初に位置決めされた時）。

（ｂ）　　両端が最狭の部分に移動した後における凹部
の重心の位置。座標は、輪郭の直立した最小の矩形の境
界をなすボックスに対し、領域（０，６３）とは関係な
く正規化されるので、［６３，６３］は、境界を形成す
るボックスの上部右側コーナを表わす。

（Ｃ）　　凹部の形状は、 ４ａＸ　ｃ ａＸｂ＋ｂＸｃ で示されるが、ここで、ａ、ｂ、ｃは、第１５ｂ図に示
す通りとする。この結果には、〔０゜６３〕に対してク
リッピングが施される。これによって、台形の辺間にお
ける角度の測定値が得られる。

（ｄ）　　凹部の深さは、底の長さで台形の垂直方向の
深さを割ることによって得られる。

（ハルラインに最も近いライン）。その結果に３２がか
けられ（０，６３）に対してクリッピングが施される。

（ｅ）　　凹部のスキューは、ラインの中心から凹部の
端部を横切り、凹部の重心まで引かれたラインと、凹部
の両端を横切るラインに対して垂直なラインとの角度に
よって得られる。この角度は、第１５ｂ図に、「Ｓ」で
表示されている。この角度は、Ｏを３２に、−πをＯに
、πを６３にマツピングす ることによって、値域（０，６３）に対し量子化される
。

（ｆ）　　値域［：０．６３］に対してスケーリングが
施された、凸状ハル領域の一部としての凹状領域。

ここで、閉鎖に転じて、説明すると、閉鎖は、各物理的
閉鎖毎に発生する。各凹部が発生する毎に、機能的閉鎖
についてテストを受ける。既知の機能的閉鎖の定義につ
いては、第１６図を参照することによって分る。第１６
ａ図に示すように、上部にギャップを有する円形文字の
場合、このルールでは： ｇ／ｗ＜０．５６の場合、そのギャップは、機能的に閉
鎖されているということになる。

ｒＯＪとｒＣＪの間があいまいな場合、すなわち、ギャ
ップが、第１６ｂ図に示すように、右へ集中する場合、
ルールでは： ｇ／ｗ＜０．２３であれば、ギャップは機能的に閉鎖さ
れていることになる。

テストは、方向によって左右さる。右に向いた凹部の場
合、実験の結果、上述のしきい値が大きくなりすぎるこ
とが分った。いくつか発生する「ｇ」が、機能的に閉鎖
されないようにするため、しきい値が、ｇ／ｗ＜０．２
３からｇ／ｗ＜０．１７に下げられたが、ここで、ｇ＝
　ｌ　ＰｉＰｊＷは、Ｐ、Ｐ、と同じ方向における凹部
の最大幅である。

他の方向については、異なる値が用いられる。

下方または左に向いた凹部の場合、しきい値は、現在の
ところ０．２９にセットされる。上方に向いた凹部の場
合、しきい値は、０．３８にセットされる。全方向につ
いて、付加制約条件：Ａ が加えられるが、ここで、ｄは、上述の凹部の深さ、Ａ
は、凹部の面積である。この制約条件によって、深い凹
部のｇ／ｗＬきい値が低下し、「ｅ」のような文字が閉
鎖される確率が低くなる。

以下の値が、閉鎖の数値表現を形成する：（ａ）　　閉
鎖された領域の重心に関する正規化相対座標。重心座標
の計算は、凹部に用いられる方法と同じであり、後述す
る。

（ｂ）　　文字の矩形に境界をなすボックス領域の一部
としてスケーリングが施された閉鎖領域。

この部分は、通常の値域（０，６３）に対してスケーリ
ングが施される。

軸の特徴は、文字に凹部または閉鎖がない場合に限って
生じる。輪郭の対をなす点間の最大距離を求めるのに、
次数の２乗計算を行なうのではなく、線形アルゴリズム
を用いる。

まず、対象の重心Ｃが計算される。輪郭における点Ｐ１
はｌ　ＰＩＣＩ　”が最大になるように求められる。ラ
インＰ、Ｃからの輪郭における任意の点までの最長垂直
距離は、ラインのそれぞれの側に対して無関係に計算さ
れる。結果は合計され、対象の幅が得られることになる
。第１７ａ図には対象の幅の計算方法が示されている。

Ｐを中間点Ｐ、。まで、または、中間点Ｐ１−まで移動
させても、結果として幅が狭くならなければ、対象の長
軸方向は、ベクトルＰ、Ｃによって得られる。Ｐｌを隣
接する中間点の１つまで移動させると、第１７ｂ図の対
象の場合、方向が調整されることになるが、Ｐ、の新し
い位置については、Ｐｌ゛とじて示される。

長軸の方向が確定すると、ｈＣに垂直なベクトルに対し
同じ幅の計算を行なうことによって、長さが得られる。

軸の数値表現は、下記項目から構成される。

（ａ）　　対象の幅対長軸の長さの比。

（ｂ）　　長軸の方向は、値域（０，６３）に対して量
子化される。方向を含む他の特徴とは異なり、該軸には
向きがない。従って、同じ方向における別のものとは３
２単位（モジュール１２３２）だけ異なる可能性がある
。

例えば、ドツトには方向がないので、幅対長さの比が高
くなると（すなわち、１に近づく）、方向は、明らかに
無意味になる。

凹部、閉鎖、及び、軸について比較し、未知の文字が標
準テンプレートのうち２つにほぼ一致する場合に限り、
ラインが用いられる。

ラインは、最短長の条件を満たす近似多角形の１つ以上
のセグメントから成るものと定義される。ラインが２つ
以上のセグメントから戊る場合、両端をつなぐ直線から
ラインに沿った任意の点までの最大垂直偏差は、所定の
限界未満でなければならない。

この条件は、曲線の一部なすラインを排除するのに役立
つ。第１８ａ図には、いくつかの可能なラインが示され
ているが、これらは全ての判定基準に合致はしないもの
である。第１８ｂ図における輪郭の肉太の部分は、受け
いれられるラインを示している。ラインは下記数値によ
って識別される。

（ａ）　　ラインの中心の正規化相対位置。

（ｂ）　　ラインの量子化方向。

（Ｃ）　　最大サイズの矩形の境界をなすボックスの一
部として、スケーリングを施したうインの長さ。

対称は、対をなす次の文字の弁別に有効な手段である：
　Ｃ／Ｇ、ｊ／）　、ｊ／）　、Ｔ／１、］／７、Ｂ／
８、Ｏ／Ｄ０主たる難点は、対称軸の位置をつきとめる
ことにある。垂直テキストの場合には、軸は、文字の直
立した境界をなすボックスの中心を通る単なる垂線であ
る。しかし、イタリック体のテキストの場合には、軸が
わずかに回転しており、となわけ、「Ｏ」のような文字
の場合には、正確な位置をつきとめるのは困難である。

対称軸の計算は、２つの方法によって行なわれる。第１
の方法で結果が得られなければ、第２の方法が用いられ
る。第２の方法は、常に何らかの結果を生じることにな
る。

（ａ）　　第１の方法は、境界をなすボックスの下半分
から上半分に通るベクトルを求めて、輪郭の探索を行う
。輪郭のまわりにベクトルが延びていて境界をなすボッ
クスの高さの半分に至り、同様に、中心まわりに延び合
は、ベクトルの合計が結果に加えられることになる。

こうしたベクトルが見つかると、その合計によって、対
称軸の方向が得られる。この方法は、「Ｏ」やｒｅＪの
ような丸い文字、及び、ｒＨＪ、ｒＰＪ等のような垂直
な線を含む文字の場合には有効である。

ｒＸＪまたは「８」のような角度のある文字の場合は、
結果が得られない。

（ｂ）　　第２の方法では、輪郭の最も右側の点が求め
られ、輪郭の他の部分を交差せずに、この点を通るよう
に引くことのできる最も右へ回転したラインが見つけら
れる。同じ操作が、輪郭の最も左側の点についても実施
される。垂線から右への回転が最小のラインが対称軸と
なる。

認識プロセスには、垂直対称と水平対称の両方を用いる
ことが可能である。垂直対称は、輪郭上の各点Ｐ、を考
慮して測定される。軸が垂直でなければ、Ｐ、の座標が
、横ずれ座標から変換されて、矩形座標に戻される。軸
におけるＰ＋の鏡映と変換された輪郭との間における最
短距離の２乗が測定される。垂直対称の測定値は、輪郭
上における全ての点に関するこうした最長距離によって
得られる。

水平対称は、同様に、水平軸を用いることによって測定
される。垂直対称の測定のために作成されたのと同じ変
換輪郭を用いることができる。第１９ａ図には、イタリ
ック体のｒＢＪの最も外側の輪郭が示されている。第１
９ｂ図の場合、輪郭は、逆の横ずれを施されて、垂直に
戻され、鏡映点が、図示のようにドツトラインでつなが
れている。「＋」マークのいくつかは、明らかに、実線
の輪郭の一部からの有効距離である。

軸と輪郭が交差する点から始め、同時に逆方向へ、対称
テストが行われる。対象がいやしくも対称をなすという
ことになれば、鏡映点に最も近い点が、その対象の反対
側における現在の点になければならない。

対称の測定が行われるのは、未知の文字と特定の対をな
すテンプレートか一致する場合に限られる。はとんどの
場合、対をなす問題のテンプレートに従って、単一方向
の測定だけしか行われない。結果は、２乗された距離で
あり、対象のサイズの測定値、例えば、矩形の境界をな
すボックスの面積の分数に対しスケーリングが施される
。

対称の第２の測定値は、横ずれを直した境界をなすボッ
クスの中心から横ずれを直した輪郭の重心へのベクトル
を計算することによって求められる。

この対称の数値表現は、横ずれを直した境界をなすボッ
クスのサイズの分数としてのベクトルの個々の成分に１
２８をかけ、［−３２，３１］に対しクリッピングを施
したものから構成される。

下記に、面積及び重心の計算を示す。

単純な手順を利用して、閉鎖領域の面積と重心が同時に
計算される。第２０図には、ｎ個の点ＰＯ＋　Ｐ１＋　
ｐａ−＋の近似多角形によって境界が形威された閉鎖領
域が示されている。この閉鎖領域は、ｎ−２の三角形Ｔ
１、Ｔ２、”’Ｔｍ−１に分割される。三角形Ｔ、が点
ｐｏ、　ｐＨ，ＰＩ−１によって境界が形成されるもの
とする。

三角形Ｔ１の領域Ａ１は： Ａ１＝　（ＰＯＰＩ、ＩＸＰＯＰＩ）　／　２で得られ
る。

Ｐから重心Ｔ１までのベクトルをＣ５とする。

この場合、Ｃ＋＝　（ＰｏＰ＋＋ＰｏＰ＋＋ｔ）　／　
３゜ＰＯから全領域の重心へのベクトルは：によって得
られる。

クロス乗積によって、必要の場合には、負の結果が得ら
れるので、総面積と重心に関する上記の式は、凹状の対
象によって影響されることはないということが分る。

上述の異なるタイプの特徴は、全体として別個のものと
みなされ、従って、例えば、凹部とラインとの近接関係
は記録されない。この分離によって認識プロセスが単純
化され、また、この分離は、実験によって決定されたも
のであって、実際に、認識の精確さが向上することにな
る。複雑な近接情報によって、認識率が高くならずに、
低下することについては、２つの理由がある： （ａ）ＡＳＣＩＩ文字集合の一意性にとって、単純な位
置情報で十分である。例えば、上部に閉鎖、下部に下に
向いた凹部、左右に斜線を含む輪郭を作成して、ｒＡＪ
が生じないようにするのは困難である。従って、近接情
報を除去しても、精確さが低下することはない。

（ｂ）　　ラインは、凹部内に位置する可能性がある。

場合によっては、ラインの一方の端が凹部の限界を超え
て延び、その特徴の明確な配列に変化を生じることもあ
る。従って、近接情報を利用することによって、精確さ
が低下する可能性がある。

一方、同じタイプの特徴も比較を簡単にするので、この
同じタイプの特徴の多重発生について、配列が行われる
。別個になった各タイプの特徴が、輪郭上に配置される
順序で記録される。

これには、信頼できる起点の定義が必要になる。

明らかな解決方法は、輪郭全体にわたって選択されたあ
る点の座標の関数を最大化することである。この関数は
、適度に計算しやすいものでなければならないが、輪郭
は、最大の輪郭上に、２つの離れた点を有する文字がな
いようにしなければならない。単純な例として、対象の
上部左コーナを選択する関数ｆ（ｘ、ｙ）　＝　Ｖ−Ｘ
について考察することにする。ただし、文字「＋」は、
ｆ　（ｘ　、　ｙ）の最大輪郭に位置する２つの離れた
点である。サイズまたは縦横比がわずかに変化しても、
起点の位置は、劇的にシフトする可能性があり、同じ文
字の異なる表現が生じることになる。

第２１図に、この問題が例示されている。ドツトライン
１１０によって、各場合におけるｆ　（ｘ　、　ｙ）＝
ｙ、ｘの最大値か示されている。第２１ａ図における「
＋」は、上部に起点を有しており、一方、第２１ｂ図の
場合は、左に起点を有している。起点を選択するこの関
数は、ｆ（ｘ、ｙ）＝４ｙ−ｘである。この関数は、ペ
ージの適度なスキューを許容すると同時に、「＊」を可
能性のある例外として、全てのＡＳＣＩＩ文字に信頼の
できる点を選択するように選択されたものである。

第２２図に示す機能表示から明らかなように、該システ
ムには、未知の文字を比較するのに用いる、１組の標準
テンプレートが必要になる。

テンブレヒートを発生するのに最も適した方法は、広範
囲にわたるフォントのサンプルを分析することである。

完成したシステムは、トレーニングまたはユーザーの介
入を伴わずに、極めて広い範囲にわたってプリントされ
たフォントの認識を行うことを意図したものである。従
って、学習プロセスで、十分に広い範囲のフォントを提
供し、それ以上トレーニングの必要がないようにしなけ
ればならない。

学習プロセスには、既知のＡＳＣＩＩコードによる文字
輪郭の集合に関する特徴の発生が含まれる。できる限り
広範囲のフォントによって、各文字のいくつかのサンプ
ルを供給し、各特徴の数値表示において予測される変動
値が学べるようにしなければならない。

学習プロセスの結果は、文字クラスの集合である。文字
クラスは、区別のつかない特徴の集合を有する１つ以上
の文字の集合を表している。

同じクラスを占める１対の文字の一例として、「Ｃ７０
」があり、唯一の差は、隣接する文字に対するサイズの
差である。

逆に、１つのＡＳＣＩＩ文字が、「ａ／ＩＪのように、
いくつかの異なる外観をとることもある。よりとらえが
たい変化が句読点において生じる。セミコロン、引用符
、及び、二重引用符において同じ形状をとることになる
コンマは、基本的に、２つの異なる形状、すなわち、「
′」のような直線と、「′」のようなカールを有してい
る。それぞれ、前述の全ての文字を含んでいる、２つの
異なるクラスが生じることになる。

標準的なテンプレートを自動的に作成するため、同じ文
字の２つのバージョンにおける差、及び、異なる文字間
における類似点を検出することが必要になる。従って、
このプロセスには、次のステップが含まれる。

（ａ）　　クラスター化（Ｃｌｕｓｔｅｒｉｎｇ）　、
同じ文字の異なるサンプルから同様の特徴を全てまとめ
て、クラスターにする。各クラスター内における特徴の
極値によって、許容範囲に対する限界が得られる。クラ
スターに寄与するサンプル数によって、認識における対
応する特徴の重要性が示される。

（ｂ）　　クラスの区分化（Ｐａｒｔｉｔｉｏｎｉｎｇ
　ｏｆ　ｃｌａｓｓｅｓ）。最少数の一致する特徴を備
えないクラス、すなわち、クラスターが全てのサンプル
によって発生するクラスは、区分化される。

（ｃ）　　あいまいさの組合せ（Ｍｅｒｇｉｎｇ　ｏｆ
　ａｍｂｉｇｕｉｔｉｅｓ）。後続段階で、区別をする
のに利用できる物理的特質が文字の間に存在する場合、
あいまいなりラスが組合せられる。

テンプレートの発生に関する機能的表現が第２４図に示
されている。

標準的なりラスター化アルゴリズムを利用して、同じ文
字の異なるサンプルにおける同様の特徴を検出すること
ができる。ただし、データの性質から、クラスター化の
問題は単純になる。

サンプル文字は、同じタイプの特徴をいくつか備えるこ
とができるが、それぞれ、別個のクラスター内のもので
なければならない。クラスの区分化が行えない場合のよ
うに、同じ文字のほとんどのサンプルに、はぼ同じ特徴
が含まれている場合、対応する特徴と突き合わせ、整合
しないものについて新しいクラスターをつくる。

クラスター化アルゴリズムでは、第１のサンプル文字が
、標準的なテンプレートに合わせてコピーされる。フレ
キシブルな突合せアルゴリズムを利用して、同じ文字の
後続する各サンプルが、標準的なテンプレートと比較さ
れる。比較の際、例えば、凹部の位置及び方向といった
、最も重要な値だけが考慮される。公差のかなり大きい
エラーも含まれる。標準的なテンプレートにおける特徴
と整合する特徴については、許容限度が拡大される。標
準的なテンプレートと整合しない特徴は、起点からの順
番を利用して、関連する位置に挿入される。

第２５ａ図には、文字ｒＨＪの第１のサンプルの例が示
されている。正方形には、凹部の重心の（ｘ、ｙ）座標
における標準的な値域［０，６３］の限界を示している
。マークは、第１のサンプルにおける２つの凹部の位置
を表わしている。第２５ｂ図には、全部で７つのサンプ
ルについて分析をすました後の、凹部に対する最後のテ
ンプレートが示されている。該正方形の左側と右側のク
ラスターは、ｒＨＪの上部と下部のセリフ（ｓｅｒｉｆ
）によって生じるものである。ドットラインによるｒＨ
Ｊが第２５ｂ図において重ねられており、文字と凹部と
の関係を示している。

一致する特徴は、テンプレートの作成に用いられた全て
のサンプル文字に存在するものである。文字の全サンプ
ルを読み取り、クラスター化アルゴリズムで短縮すると
、カウントが一致する特徴から構成される。その数が設
定された限界を下まわる場合、そのクラスの区分化が行
われる。該限界は、データベース内の各文字について、
個々に設定される。

区分化はモデルの特徴に基づいて行われる。

モード特徴を有する全てのサンプルが１つの区画に入れ
られ、残りは、別の区画に入れられる。

文字に関して一致する特徴の最少数が２の場合、２つの
最も一般的な特徴を有するサンプルだけが、第１の区画
に入れられる。

第２の区画に、必要な数の一致する特徴が収容されてい
なければ、全ての区画が一致する特徴の最低基準を満た
すまで、細区分化されていく。ある区画に最少数未満の
特徴しかないサンプルが含まれていれば、それは、一致
する特徴の最低基準を満たすことはできない。一致しな
い特徴がなければ、少なすぎる一致する特徴を区画に含
めることができるという例外が、明らかに、このルール
に対して存在するに違いない。

最終テンプレート間に存在するあいまいさか少なければ
、それだけ、最終分類の精度が高くなる。あいまいさを
低いレベルにするには、いくつかのクラスに、２つ以上
のＡＳＣＩＩ文字を含めなければならない。特徴抽出段
階において利用できない何らかの物理的尺度で文字の区
別ができる場合に限り、組合せを許容することが可能で
ある。こうした測定例には次のようなものがある。

（ａ）　　相対的高さ。大文字と小文字の区別に用いら
れる。

（ｂ）　　テキストの行における位置。ｒ、　／’　Ｊ
及びｒ−／　　Ｊのような対は、行における位置によっ
てしか弁別することができない。

（ｃ）　　隣接するマーク。集合（！、　、％、＝、；
、：、？、１％　Ｊ）は、全て、隣接するマークの存在
によって他の文字と区別される。これらの文字は、それ
ぞれ、異なる文字集合を含む、いくつかのクラスを生じ
ることになる。

（ｄ）文脈。いくつかの文字は、フォントが同一になる
。通常問題となる集合は、（０１０）及び（１，１，Ｉ
）である。正しい文字を判定する上で唯一確実な方法は
、文脈に頼ることである。従って、クラスを組み合わせ
ることが可能になる。（Ｓ、５）のような他のいくつか
の対は、困難ではあるが、区別が不可能ということはな
い。文脈は、こうした場合の正しい判断に役立つが、ク
ラスの組合せには適応できない。

正しい文字を自動的に組合わせて、妥当な標準テンプレ
ートの集合にまとめるには、知識ベースを利用すること
になる。知識ベースは、文字集合内の各文字と組み合わ
せることが可能な文字リストから構成される。

最終クラスが決まると、各クラス内の各特徴に重みづけ
が行われる。この重みによって、未知の文字に特徴がな
い場合に生じることになる突合せエラーが決まることに
なる。

重みを発生する理想の方法は、全ての妥当な値の組合せ
を試行して、文字集合全体のあいまいさを最小限におさ
えることである。これは、妥当な値の組合せが膨大な数
になるため、明らかに実施不能である。ただし、対話式
展開プロセスを利用して、重みをランダムに改良し、異
なるクラス間の距離を最大にすることは不可能である。

こうしたプロセスによって対（＊、＃）における閉鎖の
ような、はとんど判然としない文字の区別において重要
な特徴が識別される。

特徴に重みづけを行う本アルゴリズムは、単純ではある
が、有効である。一致する特徴に関して、重みは、クラ
ス内において一致する特徴の数と反比例する。従って、
一致する特徴が１つしかないｒＣＪは、その凹部に関し
高い重みを有することになる。逆に「＃」は、閉鎖は別
として、どれかが損なわれたとしてもあまり重要ではな
く、一般的であるため、各特徴に対する重みは低くなる
。７５％を超えるサンプルに生じる特徴は、同様の重み
づけが施されているが、比較定数は低くなる。残りの特
徴は、全て装飾とみなされ、割り当てられる重みはゼロ
である。

いったん未知の文字から特徴が抽出されると、その特徴
と標準のクラステンプレートとの突合せが試みられる。

認識プロセスの最も重要な面は、フレキシブルでなけれ
ばならないということである。フォントが異なれば、検
出される特徴に変化が生じることになる。従って、１つ
または２つの付加的特徴を有する、または、特徴に欠落
がある文字の認識を行えなければならない。

同時に、認識速度の増すため、未知の文字のテストは、
できるだけ少ないテンプレートで行うのてが望ましい。

速度とフレキシビリティは、ある程度、互いに矛盾した
ものである。

フレキシブルな比較は、次のように実施される。別個の
タイプの特徴のそれぞれを、別個に考慮する。ただし、
各タイプに関して、特徴の配列は、それらが基点から生
じた順序に従って行われる。従って、比較タスクは、そ
れぞれ、もう一方には生じない要素を含んでいる可能性
のある、２つの配列されたリストについて突合せを行う
ことにある。第２６図には、フレキシブルな突合せの結
果が示されている。テストの特徴のリスト＜　ＴＩ　、
Ｔｉ　、Ｔｓ　、Ｔａ　＞が、標準的な特徴のリスト＜
　Ｓｌ、Ｓｚ　、ＳＨ、Ｓ４＞と突き合わされる。

矢印は、個々の特徴間の突合せを示している。

矢印でつながれた特徴間における個々の突合せエラーと
、欠落した特徴及び付加的特徴について発生するエラー
との合計である、リスト全体に関する突合せエラーが発
生する。

２つの単一の特徴間における直接比較には、特徴の数値
表現に関する全ての要素のテストが必要になる。例えば
、閉鎖について考えてみることにする。閉鎖の重心のＸ
座標に関する限界をＸｍ１ｎ及びＸｍａｘとする。テス
トする特徴におけるクロージヤーの重心のＸ座標をＸと
すると、突合せエラーｅは、次のように発生する：ｅ　
＝　ｌ　Ｘ　−（Ｘｍｉｎ＋Ｘｍａｘ）　／　２Ｘｍｉ
ｎ＜　＝ｘＸｍａｘの場合。

Ｗ（Ｘｍｉｎ−Ｘ） Ｘｍｉｎ−ｄ＜Ｘ＜Ｘｍ１ｎの場合、 Ｗ（Ｘ−Ｘｍａｘ） Ｘｍａｘ　＜　Ｘ　＜　Ｘｍａｘ　＋ｄの場合、ｄ Ｘ＞＝Ｘｍａｘ＋ｄまたはＸ＜＝Ｘｍｉｎ−ｄの場合。

ここで、ｄは許容範囲からの最大許容偏差、Ｗは重みで
ある。Ｗは、Ｘｗａａｘ　　Ｌｌ＋及びＭ。

１、から導き出される。

各要素に重みづけをし、特徴の全要素に関する突合せエ
ラーが合計される。合計が札、８を超えると、Ｍｌ、に
セットされる。この結果、どんなタイプの特徴であろう
と、うまくゆかない突合せは、全て同じ値になることが
保証される。

テストする特徴Ｔ、と標準的な特徴Ｓｌとの突合せエラ
ーは、Ｍ（Ｔ＋、Ｓｔ）で表すことにする。

このアプローチによって、許容範囲を十分に超える値は
、無限のエラーではなく、一定の最大エラーを生じるこ
とになる。限られた数の特徴のわずかな部分が範囲外に
なる場合でも、突合せが可能になるので、この一定の最
大エラーによって、フレキシビリティが得られることに
なる。

値が許容範囲内の場合には、ゼロではなく、わずかな突
合せエラーが生じるが、これは、許容範囲の中心からの
距離を示すものである。このわずかなエラーは、「Ｕ」
とｒＶＪのような本来あいまいな文字の間に差を示すも
のであるが、さもなければ、ある文字の両方のクラスに
対する突合せエラーはゼロになる可能性もある。

配列された可能性のある全ての整合のツリーについて、
深さの第１の探索を実施することで、再帰的手順により
、特徴に関して配列された２つのリスト間において最良
の整合が得られる。

第１の操作については、第２７図に示されている。

Ｍ（Ｔ１．Ｓｌ）＜に□８の場合 ストリング全体に対する整合定格は、Ｍ（Ｔ工、Ｓｌ）
に、帰納法によって生じた、リストの残りの部分に対す
る最良の整合定格を加えたものに等しい。さらに、残り
の標準的な特徴のそれぞれに対し、次々と、第１のテス
トの特徴の突合せを行い、スキップした標準的な特徴の
それぞれについてエラーを合計する。このプロセスにつ
いては、第２７ｂ図において第２の再帰レベルでしめさ
れているが、この場合、Ｓ２はスキップされ、Ｔ！はＳ
３と突き合わせられている。第２７Ｃ図においては、Ｓ
ｌとＳ、の両方がスキップされている。このエラーは、
その重みによって左右されるＳ２をスキップするために
生じたものである。Ｍｌ、８を下まわる整合が存在する
場合にのみ、再帰が生じる点に注意すること。

最後の操作は、第１のテストの特徴が余分な特徴である
と仮定することである。これをスキップすると、一定レ
ベルのエラーが生じ、再帰を利用して、リストの残りの
部分に関する整合定格の評価が行われる。第２７ｄ図に
は、再帰の第３のレベルにおける第１のテストの特徴の
スキップが示されている。

このリストに関する整合定格は、深さの第１の探索から
得られる最低の結果であると定義される。突合せ時間は
累積エラーが、それまでの全ての深ざで最低のエラーを
超える探索を切り捨てることによって、明らかに短縮さ
れることになる。

標準的なテンプレートに対し未知の文字の突合せを行う
ためのアルゴリズムについて、上述した。テンプレート
の全集合に対して各文字をテストすることによって、可
能性のある全ての整合の検出が保証される。ただし、許
容できないほどの長時間を必要とすることになる。従っ
て、正しい整合が確実に得られるようにすると同時に、
テストされる標準テンプレートの数を減らすことが必要
になる。

採択される方法は、ルックアップテーブルを用いて、完
全な文字集合の小さな部分集合を選択することである。

テスト文字の各特徴を利用することによって、同じ特徴
を含む標準クラスの位置が求められる。

通常の値域［０，６３］において可能性のある全てのＸ
座標に関し、各文字クラス毎に１ビツトのビットアレイ
を作成する。あるクラスが許容範囲内のＸ座標を含む１
つ以上の凹部を備えている場合、そのクラスのビットが
セットされる。

これに関する許容範囲には、２つの特徴の比較時に生じ
るエラーの最大許容差ｄが含まれる。

凹部の可能性のあるｙ座標及び方向についても、同様の
ビットアレイが作成される。未知の文字の凹部を利用し
て、凹部の位置及び方向に対応するビットアレイが参照
される。次に、３つのアレイについて、論理積の演算が
施され（ＡＮＤゲートで処理される）、凹部を受けいれ
る全クラスを表したビットアレイが得られる。

未知の文字の他の全ての特徴について、同様の操作が行
われ、各特徴毎に１つの、ビットアレイの集合が得られ
る。このアレイを利用して、各ビット位置におけるビッ
ト数を示す単一のアレイが作成される。未知の文字が特
徴を有しており、標準テンプレートの１つと完全に整合
する場合、整合クラスの位置で、最高のビットカウント
は、ｎになる。ｎのビットカウントを有する全てのクラ
スに対し未知の文を比較することによって、確実に正し
いクラスが求められることになる。

未知の文字と関連するテンプレートとの完全な整合が得
られなければ、１つ以上の余分な特徴及び欠落した特徴
の両方または一方が含まれている可能性がある。欠落し
た特徴は、やはり、正しいクラスに完全に応答すること
になるが、完全な応答が得られる他のクラスの数も増え
るので、結果として、探索時間が増すことになる。

余分な特徴が十分に存在すれば、他のクラスにはより多
くの整合する特徴が備わっていて、よりビットカウント
が大きくなる可能性があるので、正しいテンプレートの
テストが行われないという可能性さえある。この場合、
整合エラーの十分に少ないクラスが見つかっていなげれ
ば、目標ビットカウントを下げることによって、まだ、
正しいクラスの見つかる可能性がある。

従って、ルックアップテーブルを利用することによって
、正しいクラスを失う危険を冒さずに、未知の文字と比
較する必要のあるテンプレートの数を大幅に減少させる
ことができる。実際には、約８０〜８５％減少するのが
普通である。

有効な特徴が１つしかないクラスが少なくなれば、すな
わち、対称が増す場合には、この数字はかなり高くなる
。

要するに、特徴抽出機構は、ＡＳＣＩＩ文字集合全体の
認識に十分な５つの特徴の集合を利用することになる。

これらの特徴は、凹部、閉鎖、ライン、軸、及び、対称
である。上記各特徴は、文字における輪郭の点数に関連
して時間的に線形に検出することができる。従って、任
意の種類の間引き操作（ｔｈｉｎｎｉｎｇ　ｏｐｅｒａ
ｔａｉｏｎ）を実施する必要は、完全になくなる。

文字のトレーニング集合を利用すれば、分割及び組合せ
手順によって、標準テンプレートが得られる。まず、ｒ
ａＪとｒＪＪの場合のように同じ文字が、特徴について
、互いに素の集合を有している場合、クラスが分割され
る。単純な操作を利用して、後続の処理段階で区別する
ことが可能な場合には、あいまいな文字を組み合わせて
、単一のクラスにすることができる。

１つ以上の特徴が、存在しないか、付加されるか、ある
いは、許容可能な受容範囲外にある場合でも、フレキシ
ブルな突合せプロセスを利用して、未知の文字とクラス
テンプレートの突合せが行われる。ルックアップテーブ
ルを利用することによって、未知の文字のテストに用い
るテンプレートの数が減少する。

ここで、第１２図に機能について表したテキスト配列プ
ロセスに言及すると、前述のように、本構成の重要な特
徴は、ページ内におけるテキスト及びイメージのブロッ
クを識別して、テキストブロックに実際の読取り配列を
施す能力である。テキスト配列機能の一部は、多角形抽
出機構から出力される１ペ一ジ分のプロブ輪郭を矩形ブ
ロックに区分するページセグメンテーションとして知ら
れるプロセスである。このプロセスを実施する場合、文
書は、テキストまたは図形の矩形のブロックから戒るも
のと仮定する。

また、読取り配列は、新聞の読取り配列、すなわち、ブ
ロックは、上から下へ、左から右へ読み取られるが、狭
いコラムの上の広いコラムは、従属するコラムに入れ子
状に収められるような配列であると仮定する。

前に強調しておいたように、エツジ抽出器からの出力は
、文字輪郭またはプロブからなるページであり、これに
よって、本構成において、多くの異なるフォントによる
テキストを読み取るのに十分なフレキシビリティがもた
らされている。また、それによって、ページセグメンテ
ーションが、フォントサイズの差によって受ける影響が
少なくなっている。ページセグメンテーションに続いて
、どのブロックにテキストが含まれているかを判定し、
その内容について最終的な類別を行うプロセスが実施さ
れる。

ページセグメンテーションに含まれるプロセスについて
、まず説明する。ページセグメンテーションは、本質的
に、３つの段階、すなわち、準備（ｐｒｅｐａｒａｔｉ
ｏｎ）　、統合（ｃｏｎｓｏｌｉｄａｔｉｏｎ）、及び
、区分化（ｐａｒｔｉｔｉｏｎｉｎｇ）自体から構成さ
れる。

まず、準備（ｐｒｅｐａｒａｔｉｏｎ）について検討す
る。実際の区分化アルゴリズムは、解像度の低いページ
表現に作用する。それらは、プロブまたは潜在的な文字
がページのどの部分を占めるのかを知る必要がある。準
備は、これに関する第１段階である。プロブからなるペ
ージが選択され、低解像度のマツプによって表されるが
、この場合、ページの各セルは、それが占められている
場合には値が−１であり、そうでない場合にはＯである
。

まず、各非偽（ｎｏｎ−ｓｐｕｒｉｏｕｓ）輪郭の境界
をなすボックスが、拡張される、すなわち、設定量だけ
拡大される。注目すべきは、ラインまたはドツトの可能
性がある全ての輪郭、及び、関連した特徴を異常に多く
有する輪郭は、除外されるという点である。この拡大は
、粗雑であるが、互いに接近した輪郭を組み合わせて、
同じブロック内に保持しておくのには有効な方法である
ことが分った。ボックスが下方に拡大されると、大見出
しが、その下方のテキストのコラムと結びつけられるお
それかあるので、ボックスの拡大は３方向に限られる。

ブロック内の白のスペースはフォントのサイズに関連し
ているので、拡張について絶対量ではなく係数を用いる
ことによって、フォントのアルゴリズムへの依存が強ま
ることになる。

現在の実施例による解像度の低いページ表現の場合、各
方向における解像度は、ページの解像度の１／８である
。ページ内の各位置セルには、整数値が割り当てられる
。当初、プロブの拡大されたボックスによってカバーさ
れる全セルは、値が−１であり、他のセルは、全て、０
である。

統合（ｃｏｎｓｏｌｉｄａｔｉｏｎ）について述べると
、テキスト配列の基調をなす仮定は、テキストが矩形ブ
ロックで構成されるということである。

準備の次のステップは、主としてプロブが占める低解像
度のマツプ内に、矩形の領域を見つけることである。統
合に対する人力は、値がＯと−１のマツプである。その
出力は、これら矩形ののブロックに関する情報を備えた
マツプである。プロブのかなりの部分、すなわち、マツ
プの値が−１の領域を求めてマツプの探索が行われる。

値が−１のセルが見つかると、該プロセスでは、そのセ
ルが属しているセルが占めている領域のまわりでエツジ
をたどることになる。

その部分に結びつけられるのは正のブロック数である。

分解時、エツジまわりの全てのセルには、負のブロック
数が割り当てられる。このアルゴリズムでは、そのブロ
ック数と、負のブロック数が利用される。−１は、すで
に利用されているので、従って、ブロック数は、２から
始まることになる。その割当ては、昇順で行われる。た
だし、それらは、そのページの最終的な読取り配列を表
すものではない、というのは、これは、区分化段階で画
定するからである。

セグメンテーションアルゴリズムは、プロブのかなりの
部分における明確な水平径路と垂直径路の発見に頼って
いるものである。ページが斜めになっている場合がある
が、こうした場合、これらの径路は、肉眼では明らかで
あるが、最大限に拡大された部分に作用するアルゴリズ
ムには、検出することができない。このおそれを軽減す
るため、プロブのかなりの部分のそれぞれにおける境界
をなす矩形が削られる。すなわち、設定量だけ全ての辺
が減らされる。これによって、該プロセスでは、新しい
かなりの部分について、Ｏの右側の負の値ではなく、Ｏ
の右側の−１によって識別されるので、削減された矩形
と重なるプロブに対し、単純な負値テストが可能になる
と同時に、大部分の処理が１度しか行われずにすむこと
が保証される。このプロセスについては、第２９図に示
されているが、左手の図は、斜めになったページのテキ
スト部分について簡単に示したものであり、右手の図は
、上述の削減プロセスの効果を示すものである。

ブロックの削減された矩形内における全てのセルには、
その値としてブロック数が割り当てられる。これには、
統合に先立つ値が０のセルも含まれる。もとの大部分に
属しているが、削減された矩形の外側で重なるセルは、
その大部分のエツジにおいては−ｎ１それ以外では、１
の値をとることになる。

最後に、正の値を有するセルに従って、ページが、ブロ
ックに区分化（ｐａｒｔｉｔｉｏｎｉｎｇ）される。ル
ーチンが開始されると、さまざまな正の値を有する削減
された矩形間において、ページを通る完全な垂直径路を
求めて、左から右へ、上から下へ探索が行われる。これ
が見つかると、別のルーチンが呼び出され、完全な水平
区画を求めて、左側部分の探索が行われるが、同時に、
さらに垂直区画を求めて、最初に述べたルーチンによる
探索が、右側部分で続行される。区画が見つからなけれ
ば、水平区画を求めて、全べ−ジの探索が行われる。そ
れ以上水平径路が見つからなければ、区分化は、第２の
ルーチンで終了する。

このアルゴリズムでは、切断器と同様にして矩形を順次
切断することによって、文書を矩形のブロックに区分化
できるという仮定がなされている。読取り配列は、新聞
の配列と仮定され、ブロックは、上から下、左から右へ
読み取られ、狭いコラムの上方の広いコラムは、狭い方
のコラムに入れ子状に収められる。その結果が、第２８
ａ図に示されている。従って、テキスト配列に対する入
力（第２２図）は、ブロックからなるページであり、出
力は、内容をロードする矩形のボックスから威るブロッ
ク集合である。

ページセグメンテーションに関連して、プロブの類別が
行われる。ブロック内の各プロブは、上述の特徴抽出器
に通され、「偽（ｓｐｕｒｉｏｕｓ）　Ｊの可能性のあ
るプロブの数が表示される。プロブは、既知のＡＳＣＩ
Ｉ文字と整合しなければ、あるいは、ドツトまたはライ
ンの場合には、偽として類別される。プロブ総数に対す
る偽の可能性のあるプロブの割合が計算され、この割合
が高ければ、非テキストとみなされる。単一の孤立した
プロブしか含まないブロックは、それだけで表示され、
テキストとしては処理されない。

テキストブロックの　　　ｏｒｄｅｒｉｎ前述の区分化
シーケンスに従うと、ブロックは、「新聞」の読取り配
列で識別されることになる。ブロック配列問題は、明白
ではないが、最も「妥当」な配列方法であり、高位の情
報レベル（ユーザー介入のような）に頼らずにすむ、お
そらく最良の方法である。

ブロックのないテキスト　１ ブロックのないプロブでは、結びつけて行にし、次に、
プロブと行の配列を行う必要がある。

このテキスト配列プロセスは、プロブを受は入れる配列
について、何ら仮定を行わない。

ブロック内の各プロブについて検討する毎に、その最大
及び最小のｙ（垂直）位置が、表示される。そのプロブ
が、最初に、検討されるプロブであれば、これらのｙ値
は、第１行に関する最大及び最小のｙ値として表示され
る。後続の各プロブについては、それが既存の行内にあ
るか否かが表示される。既存の行内にあれば、その行と
関係づけられ、その行の最大値と最小値が修正される。

既存の行内になければ、新しい行を開始する。

こうして、ブロック内の全てのプロブについて検討がす
むと、行にバスを行って、表示の行を組み合わせる必要
があるか否かをチエツクする。例えば、ある行について
検討される最初の２つのプロブが、小文字の「ｉ」と関
連するドツトの場合には、２つの別個の行が開始された
ことになる。従って、これら２つの行を１つに結びつけ
るため、組合せのバスが必要になる。

全てのプロブが行に関連づけられると、各行内のプロブ
が、ｘ（水平）配列に分類される。次に、行が、減少し
てい＜ｙ（垂直）配列に分類される。これで、テキスト
ブロック内におけるプロブの関連づけと配列が完成する
。

ａ乙さ二Ｚ里遺潰 いったんテキストプロブの正しい配列がすむと、それら
の内部における白スペース文字の位置を演鐸することが
必要になる。これは、ブロック内におけるプロブ内の空
間関係に距離の集合を適用することによって行われる。

各プロブはその右手の隣接部分と関連しており、プロブ
の中間点とその隣接部分の中間点との距離（スペーシン
グ：　ｓｐａｃｉｎｇ）が表示される。プロブの右側エ
ツジを隣接部分の左側エツジとの距離（カーニング：　
ｋｅｒｎｉｎｇ）についても表示される。最後に、プロ
ブの幅（ｗｉｄｔｈ）が表示される（第３０図参照のこ
と）。

次に、ブロック内のテキストの間隔が、比例したものに
なりそうか、比例したものにはなりそうにないかの判定
が行われる。これは、下記に基づいて行われることにな
る（ここで、ＩＱＲ（ｘ）は、Ｘの四文位数間領域）。

ＩＱＲ（スペーシング）がＩＱＲ（カーニング）を超え
ると、テキストの間隔は比例し、そうでなければ、比例
しない。ＩＱＲは、分布の足部形状（行のそろったテキ
スト／行のそろっていないテキストによって変化する）
に反応せず、小さなサンプル集合のサイズに対し安定し
ているので、尺度として選択された。

従って、白スペースアルゴリズムは、比例したテキスト
が存在するのか、あるいは、比例しないテキストが存在
するのかによって左右される。比例したテキストの場合
、メジアンカーニング値が用いられ、カーニング値が２
．０×この値を超える場合には、白スペースが挿入され
る。（ここで用いた２、０は、経験的に評価された数字
である。モードの利用は、直観的には正しいが、サンプ
ル集合のサイズが小さいとか、あるいは、測定分解能が
高い場合には、安定性の問題を生じる可能性がある。こ
のため、メジアン値を利用する。） 比例しないテキストの場合、メジアンスペーシイング値
が利用され、カーニング値が１．５×この値を超えると
ころへ、白スペースか挿入される。（ここで用いた１、
５は、比例しないテキストのモデルによれば直観的に正
しい）。

に　　される　　にお　るプロブの 慎重な分解（ｄｅｌｉｂｅｒａｔｅ　ｂｒｅａｋ）の特
徴（小文字の「ｉ」におけるボディーとドツトのような
）は、同じ行内の２つのプロブが、Ｘにおいて重なる点
にある。これが生じると、２つの文字の小さい方には、
ドツトが割り当てられることになり、この情報がテスト
配列プロセス（後で参照）のテスト部分に送られる。

みＡわせ゛れる　　　の　る　　の プロブは、広すぎる場合、組合せとして識別される。こ
れは、プロブ幅のある分布から判定される。テキストブ
ロック内のプロブも、既知のＡＳＣＩＩ文字に整合しな
ければ、組合せの可能性があるものとして定義される。

組み合わせられた可能性のあるプロブは、組合せ装置／
セグメンタ１５によるセグメンテーションの候補である
。セグメンテーションが正しかったか否かの選択は、最
終類別器１６によって行われる。

のあいまいさの 上述の特徴抽出器によって、プロブと、ＡＳＣＩＩ文字
の可能性のあるクラスの集合との突合せが行われるが、
この場合、各クラスには、特徴によって分解することの
できない文字が含まれているが、行内におけるそれらの
サイズまたは位置を検討すれば、解決することができる
。

これを行うためには、各行に関連したデータが、さらに
必要になる。プロブを最初に関連づけて２行にする場合
、最大のｙと最小のｙ（垂直）については、すでに、各
行に対して表示されている。また、ベースラインの位置
、すなわち、アラセンダーのない文字がおさまるライン
の位置、及び、Ｘ高さ、すなわち、小文字のｒｘＪの上
部の垂直位置（第３１図参照）についても表示が必要で
ある。これらの余分な行の距離を演鐸するには、行の文
字タイプ（アラセンダー（ｄｅｓｃｅｎｄｅｒ）の有無
、ｒｘＪの高さ、または、アラセンダー（ａｓｃｅｎｄ
ｅｒ）を伴う）を表した表示が各プロブ毎に必要になる
。ただし、この情報は、この処理段階では利用できない
。代わりに、あるリストは、アラセンダーを有する文字
を含むクラスから構成され、あるリストは、アラセンダ
ーのない、明らかに小文字のクラスから構成されること
になる。ベースラインの測定に関するプロブからの情報
は、前者のリストに含まれないクラスとうまく整合する
場合に限って用いられ、Ｘの高さの測定に関するプロブ
からの情報は、後者のリストに含まれるクラスとうまく
整合する場合に用いられる。こうして得られる値は、エ
ラーに対する感度をおさえるため、平滑化されて、実行
トータル（ｒｕｎｎｉｎｇ　ｔｏｔａｌ）になる。

行内において、ドツトとして識別されなかった各プロブ
をテストして、クラス内における可能性のある文字の識
別を助けるのに用いられる、プロブの距離集合が求めら
れる。用いられる距離は：最大のＹと最小のＹとの距離
と比較したプロブの相対高さである、ＲＥＬＨＴ、最大
のＹと最小のＹとの距離と比較したプロブの中心の垂直
位置である。ＶＰＯＳ；及び、ＦＩＬＬである。

ＦＩＬＬはＸの高さと最大のＹの間の、領域におけるプ
ロブの割合を調べることによって、同じ文字の大文字バ
ージョンと小文字バージョンとの識別を行うのに用いら
れる、特殊な距離である。

テキスト配列プロセスのテストセクションでは、ＡＳＣ
Ｉ　Ｉ文字のデータベースをチエツクして、各クラスか
らの文字のうちどの可能性が最も高いか判定される。こ
のデータベースには、各文字の高さ、垂直位置、及び、
ドツトの有無に関する情報が含まれている。この情報は
、文字の説明と呼ばれる。各プロブの距離はゾーンに分
割され、文字の説明は語として記憶されるが、この場合
、設定されたビットがこのゾーン内に対応するプロブの
距離があることを表示する。各プロブ毎に、それ自体の
説明が形成され、これから、特徴抽出によって送られて
くる、可能性のある各クラスに対する単一のＡＳＣＩＩ
文字の選択が行われる。クラス内の文字がうまく適合し
なければ、選択の整合定格を下げることになる（整合定
格は、特徴抽出によって得られる信頼の尺度である）。

従って、テキスト配列１２から各プロブに対する最終類
別への出力は、それぞれに整合定格を伴う、１つ以上の
ＡＳＣＩＩ文字である。

こうして、テキスト配列機構によって、少し制限されて
いるが、それにもかかわらず、複合文書の代表的な集合
である構造について、分析し、これを利用する能力が得
られることになる。

これは、本システムの重要な特徴である。

ここで、最終類別器１６について説明する。特徴抽出及
びプロブ類別ステップ（認識プロセスの　「核心（ｈｅ
ａｒｔ）　Ｊ　）では、各プロブに関連したＡＳＣＩＩ
値に対する最終判定は得られないが、代わりに、最終文
字が一部をなす、文字クラスの集合を表したデータが得
られる。各クラスには、信頼値またはそれに関連した整
合定格が備わっている。

従って、この段階では、それぞれ、最終文字の選択を可
能にするいくつかのＡＳＣＩＩ文字を含む、いくつかの
クラスが存在する。

クラスのメンバーシップは、同クラスのメンバーは、同
様の特徴を備えるが、幾何学的脈絡（ライン上における
位置、サイズ、ドツトの存在等）によって区別できるよ
うに、慎重に選択される。従って、「Ｃ」及びｒｃＪは
、同じクラスに存在するかもしれないが（それらは、高
さで区別できる）、「Ｏ」とｒＯＪは、別個のクラスに
ならなければならない。

クラスのメンバーシップに関するこの選択のため、各ク
ラス内からどの文字を選択するかについては、上述のテ
キスト配列段階で選択することができる。

従って、テキストの配列がすむと、文字集合から各プロ
ブについて選択を行わなければならない。この場合、助
けとなる整合定格は存在するが、プロブの物理的レイア
ウト、または、外観からの情報は、それ以上ないような
選択が行われる。

最終類別器は、テキストモデルを利用して、その最終類
別を実施する。まず、これらのモードについて説明し、
引続き、それらを利用して最終類別を行う方法について
説明する。

各モデルとも、テキスト構造について何らがの仮定を行
っている。これらのモデルは、一般には、特定の言語で
あり、言語が異なれば、異なるデータベースが必要とな
り、あるいは、モデルと一致しないということになる（
これは、特に、コンピュータ言語の場合にあてはまる）
。

本書に解説のモデルの場合、データベースが変更される
可能性はあるが、おそらく、全てのヨーロッパ言語に有
効である。

（１）辞書的ルール（Ｌｅｘｉｃａｌ　ｒｕｌｅｓ）　
　：テキスト単位が、白スペース区切り文字間の文字集
合として識別できるものと仮定することによって、単純
な文字レベルの構文ルールを開発することが可能である
。文字は、次のように類別される。文字は、英数字また
は句読点とすることができる。英数字文字は、英字また
は数字とすることができる。英字は、大文字または小文
字とすることができる。テキスト単位における最初の英
数字が英字の場合、最初の英数字から最後の英数字まで
の文字のストリングを語と呼ぶ。辞書的ルールは、従っ
て： ａ）　語の中に数字が含まれない。

ｂ）　語において、大文字が小文字に続くことはない。

Ｃ）　語中に句読点（アポストロフィを除く）が生じる
ことはない。

（２）マルコフ法（Ｍａｒｋｏｖ　Ｍｅｔｈｏｄｓ）　
　：　ｖルコフ連鎖は、各インクリメント毎に、有限数
の状態の１つを選択することができる離散的確率的プロ
セスである。現在の状態が　ｉ　の場合、次のインクリ
メント時に状態　ｊ　になる確率は、純粋に、ｉとｊの
関数にほかならない。

従って、該プロセスは、通常、遷移行列Ｔの形で説明さ
れる遷移確率ｐ（ｉ、”ｊ）によって完全に説明するこ
とができる。可能性のある状態がｎ個存在する場合、Ｔ
は、ｎＸｎになる。ある状態の確率のベクトルＳ３につ
いて、ＳＫのｉ番目の要素かに番目のインクリメント時
におけるｉ番目の状態の確率であると定義すると： Ｓｋ、、＝ＴＳ工 と書くことができる。

テキストは、真のマルコフプロセスではないが、ある程
度うまくいくものとして、モデル化することができる。

これは、スペリングの慣例（例えば、Ｕがｇに続く）と
、語を発音できるようにする必要性のためである（従っ
て、ｇがｊの後にくることはありそうにない）。可能性
のある状態として各英字毎に（大文字か小文字かは無視
して）、インクリメントに伴う文字の各発生毎に、２６
Ｘ２６の遷移行列を利用して、次の文字の選択を助ける
ことができる。所定の遷移の生じる確率を反映するため
に必要なのは、ただ整合定格に修正を加えるだけのこと
である。

最終化される文字及び次の文字から、遷移の確率を考慮
して、マルコフ連鎖を逆方向へ適用することも可能であ
る。

文字は信頼できると仮定されているので（遷移が行われ
ている状態）、上述の「逆方向（ｂａｃｋｗａｒｄｓ　
Ｊまたは「順方向（ｆｏｒｗａｒｄｓ）　Ｊの選択は、
理想的とはいえない。この問題は、後述のように、文字
レベルではなく、語レベルで判定を行う場合には解消さ
れることになる。

上記は、前のｍ−１文字に基づく選択にも敷術すること
ができる。ただし、これには、可能性のある２６（″−
１）の組合せのような状態についての検討が必要になる
。これは、２６３″″−１］Ｘ２６”−１）の遷移行列
を示すものである。実際には、全ての遷移が可能という
わけではないので（例えば、状態「ａｂＣ」からｒｘｙ
ｚＪ、ｒｂｃａＪだけ、ｒｂｃｂＪ、ｒｂ　ｃｃＪ等へ
は不可能）　、２６ｍの項目しか、非ゼロではない。上
記に必要な遷移表は、急激に増大するので、２を超える
ｍの利用については、議論の余地がある。大きい値のｍ
を用いるよりも、次に述べるように、辞書的方法の方が
良い。

（３）辞書的方法（Ｄｉｃｔｉｏｎａｒｙ　Ｍｅｔｈｏ
ｄｓ）　　：生成ルールの特定の集合を用いることによ
って、テキスト単位（自スペース間のストリング）を、
辞書にある語と、辞書の項目から導き出すことのできる
語のいずれかに変換することができる。発生の方法、す
なわち、生成ルールは既知のものであり、例えば、１９
８２年１月のＩ　ＥＥＥの報告書（Ｔｒａｎｓ、　Ｃｏ
ｍｍ５．）における、エム・ダグラス・マクロイ（Ｍ、
　Ｄｏｕｇｌａｓ　Ｍｃｉｌｒｏｙ）による「スペリン
グリストの転回（Ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ａ　
Ｓｐｅｌｌｉｎｇ　Ｌｉ５ｔ）　Ｊ参照。

最終類別器は、１９８０年１０月のベル・システム・テ
クニカル・ジャーナル（Ｂｅｌｌ　Ｓｙｓｔｅｍ　Ｔｅ
ｃｈｎｉｃａｌ　Ｊｏｕｒｎａｌ）におけるビー・アル
デフエルド（Ｂ、　Ａｌｄｅｆｅｌｄ）による「最小距
離走査技法（Ａ＊ｎｉｎｉｍｕｍ　Ｄｉｓｔａｎｃｅ　
５ｅａｒｃｈ　Ｔｅｃｈｎｉｑｕｅ）　Ｊに記載のやり
方で、辞書的探索方法を利用することができる。

最終類別器は、上記を次のように利用する：前述のテキ
スト配列段階において、ページ上の文字ブロックが、ブ
ロックに分割され、これらのブロック内での配列が行わ
れ、行に分類され、自スペースが演鐸される。テキスト
配列の「テスト」部分において上述のように、適合する
文字が各クラスから選択される。最終類別段階では、テ
キスト単位がアセンブルされ（白スペース間において）
、それに送られてくる文字選択から可能性のある各テキ
スト単位が権威される。可能性のある各テキスト単位は
、総定格（ｔｏｔａｌ　ｒａｔｉｎｇ）を有しているが
、これは、各文字選択の個々の確率の積にすぎない。ま
た、以下に示すように、可能性のある各テキスト単位は
、テキストモデルのそれぞれに対してどれだけうまく一
致するか反映させるため、その総定格に修正を加えるこ
とが可能である。

上記（１）に示すように、手順バンクストリップ（ｐｕ
ｎｃ　５ｔｒｉｐ）によって、テキスト単位は、語に分
解される。次に、３つの辞書的ルールが、下記実施ルー
ルに変換される。

語内で英字から数字への遷移は生じない。

小文字から大文字への遷移は生じない。

句読点は含まれない（アポストロフィを除く）。

マルコフ連鎖の適用によって、語選択に関して所定の径
路が選択される確率が得られる。この結果、順逆両方向
への分析を実行する必要がなくなり、また、語全体につ
いて径路の確率か計算されるので、特定の文字に信頼を
置く必要がなくなる。

径路の確率は、語に関する各遷移におけるＰ（ｉ、ｊ）
の積である。確率が高まるということは、その語が正し
いという可能性も高まることになる（マルコフモデル内
において）。

辞書探索方法は、市販のプログラムを用いて実施するこ
とが可能である。

注意すべきは、マルコフモデルと辞書的方法の両方を利
用する必要はないという点である。

一方、やはり注意すべきは、マルコフモデルの場合、デ
ータベースに占めるスペースが大幅に少なくなるという
点である。

（発明の効果） 以上のように、本発明によれば、特徴抽出法に基づく光
学式文字認識を応用した、簡便且つ作業速度が迅速な文
字認識システムが提供される。

本発明のいくつかの実施例について詳述したが、通常の
技術者であれば、本発明の精神を逸脱することなく、数
多くの変更及び修正が可能であることは明らかである。

従って、付属のクレームを参照し、本発明の範囲を確認
すること第１図は、本発明に基づく光学式文字認識シス
テムの概略的ブロック図であり、 第２図は、文字ｒａＪに関する典型的なグレーレベルの
イメージを示し、第２Ａ図にはイメージの形態が示され
ており、第２Ｂ図には１６進数値によるイメージの形態
が示されており、第３Ａ図及び第３Ｂ図には、多角形近
似の一例が示されており、第３Ａ図は文字ｒａＪの典型
的なエツジ経路を表わしており、第３Ｂ図は、多角形処
理をすませた後のエツジ経路が示されており、 第４図は、多角形処理後の文字「ａ」のエツジ経路であ
り、番号２１によってクロージャを示しており、 第５図は、第１図のシステムに使用されるエツジ抽出器
の概略的ブロック図であり、第６図は、第５図に示すエ
ツジ抽出器の動作を示しており、第６ａ図は３×３のピ
クセルのアレイを示し、第６ｂ図は連鎖コード０のエツ
ジ値を求める様子を示しており、第６ｃ図は連鎖コード
７のエツジ値を求める様子を示しており、 第７図も、第５図に示すエツジ抽出器のある動作を示し
ており、第７ａ図は５×５のピクセルのアレイを示して
おり、第７ｂ図は第７ａ図の丸８０のエツジ値を示して
おり、第７ｃ図は第７ａ図の角の丸います目８１のエツ
ジ値を示しており、第７ｄ図は第７ａ図のひし形まず目
８２のエツジ値を示しており、 第８図も、第５図に示すエツジ抽出器のある動作を示し
ており、第８ａ図は第２図に示す文字ｒａＪの部分を示
しており、第８ｂ図は第８ａ図の円９０のエツジ値を示
し、第８ｃ図及び第８ｄ図は第８ｂ図でエツジ値１１を
示す２つの点のそれぞれについてのエツジ集合を示して
おり、第９図も、第５図に示すエツジ抽出器のある動作
を示しており、第９ａ図は一対の間隔の密な文字に関す
る正しい輪郭を示し、第９ｂ図は文字が結合している場
合を示し、第９ｃ図は文字「ｉ」は完全であるが、エツ
ジがループの開始部で閉じなかった場合を示し、第９ｄ
図は正確にｒｔＪをたどったが、「ｉ」についても同じ
経路を選択し、完成したｒｔＪと衝突して削除された様
子が示されており、 第１Ｏ図も、第５図に示すエツジ抽出器のある動作を示
しており、第１０ａ図はその一態様を示し、第１０ｂ図
はその別態様を示し、 第１１図も、第５図に示すエツジ抽出器のある動作を示
しており、第１１ａ図は文字「％」の場合を示し、第１
１ｂ図は文字「％」の回転変換の結果を示しており、 第１２図は、第１図のシステムのテキスト配列部分の概
略的ブロック図であり、 第１３図は、多角形近似機能のある動作を示しており、 第１４図は、多角形近似機能の別の動作を示しており、 第１５図〜第２１図は、文字を識別する方法を示してお
り、 第１５ａ図は分割を伴う凹部を示し、第１５ｂ図は、凹
部より形成される台形を示し、 第１６ａ図は上部にギャップを有する場合の閉鎖の様子
を示し、第１６ｂ図は側部にギャップを有する閉鎖の様
子を示し、 第１７ａ図には対象幅の計算方法が示されており、第１
７ｂ図には対象方向の調整の様子が示されており、 第１８ａ図は受は入れられないが可能なラインを含む文
字を示し、第１８ｂ図は受は入れられるラインを含む文
字を示しており、 第１９ａ図はイタリック体のｒＢＪの最も外側の輪郭を
示し、第１９ｂ図は第１９ａ図に示すイタリック体のｒ
ＢＪに逆の横ずれが施された様子を示し、 第２０図はｎ個の点ＰＯ，ＰＩ、　Ｐｎ−１の近似多角
形によって境界が形成された閉鎖領域を示し、第２１ａ
図は上部に起点を有する「＋」を示し、第２１ｂ図は左
に起点を有する「＋」を示しており、 第２２図は、第１図に示すシステムの特徴抽出、テキス
ト配列及びセグメンテーション、及び最終分類部分の概
略的なブロック図であり、第２３図は、文字ｒＥＪとし
て表現される方法の例を示しており、 第２４図は、テンプレート発生機能を機能的に示した図
であり、 第２５図〜第２７図は、テンプレート発生機能の動作を
示しており、 第２５ａ図は文字ｒＨＪの第１のサンプルの例を示し、
第２５ｂ図は分析後の、凹部に対する最後のテンプレー
トが示されており、 第２６図には、フレキシブルな突き合わせの例が例示さ
れており、 第２７図は突き合わせのプロセスを示しており、第２７
ａ図はＴ１が８１に突き合わされた様子を示し、第２７
ｂ図はＳ２がスキップされた様子を示し、第２７ｃ図は
Ｓ２及びＳ３がスキップされた様子を示し、第２７ｄ図
は再帰の第３のレベルにおける第１のテストの特徴がス
キップされた様子を示しており、 第２８図〜第３１図はセグメンテーションと最終分類段
階の動作を示しており、 第２８図はセグメンテーションの様子を示しており、第
２８ａ図はブロック区分化の一態様を示し、第２８ｂ図
はブロック区分化の別態様を示しており、 第２９図もセグメンテーショにの様子を示しており、第
２９ａ図は斜めになったページのテキスト部分を示して
おり、第２９ｂ図は削減プロセスの効果を示しており、 第３０図は隣接するプロブの様子を示しており、第３１
図は行に関するプロブの様子を示している。

１０・・・スキャナ／インタフェース、１１・・・エツ
ジ抽出器、 １２・・・テキスト配列機構、 １４・・・特徴抽出器、 １５・・・組合わせ装置／セグメンタ、１６・・・最終
類別器、

Claims (1)

【特許請求の範囲】
1. １　光学的に文書を走査して、そのイメージを生じる走
   査手段と；前記イメージ内のエッジを識別し、エッジの
   経路を識別して、前記イメージ内で識別された各対象の
   輪郭を示すデータを生じるエッジ識別手段と；前記エッ
   ジ識別手段によって得られたデータに処理を施し、前記
   イメージの文字を適合するフォーマットで表わしたデー
   タを生じる手段から成ることを特徴とする、光学式文字
   認識システム。