JPH0562018A - 文字認識方法 - Google Patents

Abstract

(57)【要約】 【目的】 重なりを有する直線群によって輪郭を表現す
ることによって、角と弧の識別を容易にする。 【構成】 ２値化処理部１は、画像を読み取って２値化
し、ｐライン生成部２は、２値画像の輪郭に対して、重
なりを有する直線（ｐライン）を生成する。このｐライ
ンとしては、複数の画素を通る共通直線あるいは８方向
線を用いる。概念生成部３は、ｐラインから弧、角、直
線の概念を生成し、その概念を図形の表現データとして
黒板データ記憶部４に書き込む。文字認識部５は、輪郭
部の認識時に、記憶部４の概念を参照して輪郭部の詳細
構造を識別処理する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、角および弧の識別を容
易にした文字認識方法に関する。

【０００２】

【従来の技術】文字認識においては、認識すべき対象か
ら如何にして特徴を抽出するかによって、認識の精度が
大きく左右される。特徴抽出の手法としては、従来から
種々の方法が開発され、また実用に供されて来たが、そ
の一手法として、輪郭線の形を調べる方法が知られてい
る。この輪郭線特徴抽出法は、簡単にいえば何らかの方
法で境界を追跡し（追跡のアルゴリズムが各種提案され
ている）、この追跡結果をチェインコードで表現するも
のである。そして、更にコード表現を直線や円弧で近似
表現した後、識別処理される。また、輪郭を直線で表現
する方法としては、多角形近似の手法が研究されている
（例えば、Ｗilliamsの方法等）。

【０００３】

【発明が解決しようとする課題】しかしながら、従来の
方法では、角と弧を区別することが難しく、認識系から
の要求に応じて種々の大きさと曲率を持つ弧を輪郭から
探し出すことが困難であるという問題があった。

【０００４】本発明の目的は、重なりを有する直線群に
よって輪郭を表現することによって、角と弧の識別を容
易にした文字認識方法を提供することにある。

【０００５】

【課題を解決するための手段】前記目的を達成するため
に、本発明では、２値画像の輪郭を、重なりを有する直
線群によって生成し、該生成された直線群に基づいて、
該輪郭を構成する角と弧と直線とを識別することを特徴
としている。

【０００６】

【作用】２値化処理部では、画像を読み取って２値化処
理し、ｐライン生成部では、２値画像の輪郭部に対し
て、重なりを有する直線（ｐライン）を生成する。この
ｐラインとしては、極大直線あるいは８方向線を用い
る。概念生成部では、ｐラインから弧、角、直線の概念
を生成し、その概念を図形の表現データとして黒板デー
タ記憶部に書き込む。文字認識部では、輪郭部の認識時
に、黒板データ記憶部の概念を参照して輪郭部の詳細構
造を識別処理する。これにより、弧と角の識別が容易に
なる。

【０００７】

【実施例】以下、本発明の一実施例を図面を用いて具体
的に説明する。文字認識の手法には、大きく分けて統計
的手法と構造的手法があるが、本発明は、輪郭解析に構
造的手法を用いたものである。

【０００８】図１は、本実施例のブロック構成図であ
り、１は、画像を読み取って２値化する２値化処理部、
２は、２値画像の輪郭に対して後述するｐラインを作成
するｐライン生成部、３は、ｐラインから弧、角、直線
の概念を生成する概念生成部、４は、概念を図形の表現
データとして黒板に書き込まれる黒板データ記憶部、５
は、文字認識部である。

【０００９】本実施例では、図２に示すディジタル２値
画像の輪郭に対して、図３のように、重なりを有する直
線を形成する。以下、この重なりを有する直線をｐライ
ン（ primitive line）と云う。ｐラインの具体例とし
ては、本実施例では極大直線と、８方向線を用いる。

【００１０】〈極大直線〉図４は、極大直線を説明する
図で、ａ１からａ８、ｂは、輪郭の一部を構成する各黒
画素である。ここで、各黒画素は、所定の大きさを有す
る四角形とする。極大直線は以下のようにして作成され
る。まず、輪郭上の一点が選ばれ、その点から前（後）
方に一画素づつ追加し、各画素を通る共通直線が存在す
る間は、該直線を伸ばす。すなわち、点ａ１からａ
（ｎ）を通っていた直線を点ａ（ｎ＋１）まで伸ばすと
は、点ａ１．．．点ａ（ｎ）及び点ａ（ｎ＋１）を全て
通る直線が存在するか否かを調べ、存在する場合は、点
ａ１からａ（ｎ）を通っていた直線を、点ａ１から点ａ
（ｎ＋１）を全て通る直線に置き換える、ことを云う。
そして、次の画素を追加したら全ての点を通る直線が存
在しないところで、直線を伸ばす処理を止め、今度は後
方に一画素づつ追加して、同様の処理を行う。このよう
にして作成される直線を、開始点から生成される極大直
線という。図４の直線４１、４２、４３等はこのように
して作成された極大直線である。

【００１１】上記した極大直線を作成するときに、直線
が通過する画素領域の形状が四角形（正方形）であった
が、これを黒画素の四辺の中点を結ぶ菱形（図５）ある
いは黒画素に接する円（図６）等、種々の形状を用いる
ことができる。

【００１２】ところで、原画像が直線であっても、スキ
ャナー等によって読み取られると、図７に示すように画
素レベルのずれである量子化誤差が発生するが、本実施
例の極大直線は、このような量子化誤差を吸収すること
ができ、図８に示す一本の直線が生成される。また、こ
の極大直線の集合は、輪郭に対して一通りに決まる。図
９は、極大直線の集合を説明する図である。輪郭上の任
意の点Ａから開始し、輪郭上の一方向を前、反対方向を
後とし、前述した手順で初めに後に伸ばし、次いで前に
伸ばして最初の極大直線９１を生成する。前記生成され
た極大直線９１上の一番前の点Ｂと、輪郭上のその次の
点Ｃ（前記極大直線９１上にない点）について、この２
点を通る直線から出発し、まず後の画素を通るように直
線を伸ばし、次に前に伸ばして、次の極大直線９２を生
成する。この手順を繰り返すことによって、極大直線の
集合が生成される。

【００１３】〈８方向線〉重なりを有する直線（ｐライ
ン）の他の例として、本実施例では、８方向線を用い
る。この８方向線は、輪郭から８方向のチェインコード
（方向コード）を生成し、同じコードが続く部分を同一
直線とするもので、図１０に８方向線の一例を示す。

【００１４】以上で説明したｐラインは、輪郭上の全て
の点から生成されるものであるから計算量が多くなる。
そこで、輪郭の特徴を損なうことなく、輪郭を代表する
点を選ぶことによって、ｐラインを生成する処理を含む
後段の計算量を減らす、代表点の取り方（以下、ドット
シーケンスという）を説明する。すなわち、第１の方法
（行毎あるいは列毎のドットシーケンス）は、行方向の
各行の端点の内、次のものだけを選ぶ。つまり、ｘ座標
の差が一定の場合、同一直線上の点であるとして、その
直線の端点のみを選ぶ。図１１の例では、ｄｘ１＝ｘ２
−ｘ１，ｄｘ２＝ｘ３−ｘ２であり、ｄｘ１＝ｄｘ２で
あるので、２行目の点（ｘ座標がｘ２の点）がドットシ
ーケンスから除かれる。列毎のドットシーケンスも同様
である。

【００１５】第２の方法（行あるいは列のドットシーケ
ンス）は、輪郭上の点からチェインコードを生成し、同
じコードが続くときは一つの直線上にあるとして、この
直線の端点だけを選ぶ。図１２に、行あるいは列のドッ
トシーケンスの一例を示す。また、第３の方法（行およ
び列のドットシーケンス）は、前述した行毎のドットシ
ーケンスと列毎のドットシーケンスの共通点を選んだも
ので、図１３にその例を示す。なお、このドットシーケ
ンスは、ランレングスデータから作成されるものであ
る。

【００１６】概念生成部３は、前述したｐラインから
弧、角、直線の概念を生成する。すなわち、弧は、次の
条件を満たすｐラインから構成される。隣合う
ｐラインがｎドット以上の共通部分を有する、隣合う
ｐラインの方向の差ｄθが同符号である、隣合うｐラ
インの方向の差ｄθがある一定値以下であること。

【００１７】直線（より大きな直線）は、次の条件
を満たすｐラインから構成される。隣合うｐライン
がｍドット以上の共通部分を有する、隣合うｐライン
の方向の差ｄθがある一定値以下であること、全ての
ｐラインの方向θがある一定の範囲に収まっているこ
と。

【００１８】角は、次の条件を満たすｐラインか
ら構成される。２つのｐラインがｋドット以下の共通
部分を有する、２つのｐラインの方向の差ｄθがある
一定値以上であること、２つのｐライン間に他の概念
が存在しても良いが、それら概念の大きさの合計が角を
構成するｐラインに対して十分小さいこと。

【００１９】これらの各概念は、それぞれ独立に全ての
ｐラインの位置においてその有無が調べられ、概念が生
成されると、それを次々と後述する黒板データ記憶部４
に、その物理的な大きさ別に書き込んでいく。このよう
な処理は、ｐラインから概念を生成する場合だけではな
く、概念から概念を生成する場合についても行い、もは
や新しい概念が生成されなくなるまで、次々と大きな概
念を生成していく。なお、各ｐラインや概念は、そのｐ
ラインの示す方向の範囲、その概念の始めのｐラインと
終わりのｐラインの方向、大きさ等種々の属性を持つよ
うにすることが可能で、そのような属性を利用した条件
に変更することもできる。また、弧についても、弧の始
まりから終わりまでの角度の変化に応じて、小さい弧、
中程度の弧など異なる概念にしてもよい。

【００２０】図１４は、原画像からｐラインが生成さ
れ、更にｐラインから角の概念が生成された図である。
図１５は、ｐラインから同様に弧と直線の概念が生成さ
れ、更にこれらの概念から新しい概念である角が生成さ
れた図である。図１６は、ｐラインから弧の概念が生成
された図である。なお、上記概念を生成する過程で、ｐ
ラインの一部だけを新概念に取り込むような処理を許す
ようにする。すなわち、図１７において、大きさの極端
に異なる２つのｐラインから角を生成するとき、大きい
方のｐラインの一部だけを概念である角に取り込んだ実
施例を示す図である。また、各概念も、ｐラインと同様
に重なりを持つことができる。

【００２１】このように、本実施例によれば、従来の多
角形近似では不可能であった曲線と直線の識別が、概念
構造で容易に可能となる。

【００２２】直線、弧、角等の概念は、その物理的な大
きさ別に黒板に書き込まれる。図１８は、黒板に書き込
まれた概念を示す図である。図において、横軸は輪郭上
での始点からの距離であり、縦軸は概念の大きさ（対
数）である。概念の大きさは、直線と弧についてはその
長さ、角については、角を構成する２直線の長さの和
（あるいは最も離れた２点間の距離、角によって構成さ
れる三角形の面積）等によって決められる。

【００２３】また、概念間を接続する接続情報によっ
て、図の上位に配置される大きな概念は、どのような概
念によって構成されているかを示し、２つの概念が同じ
下位の概念を共有している等の情報を容易に得ることが
できる。更に接続情報は、位置を用いて概念をたどると
きの手がかりになる。

【００２４】前述した黒板の計算機内部のデータ構造と
しては、２次元配列、スケール毎のリスト構造によって
記憶される。図１９は、縦軸、横軸に概念の大きさと位
置を持った２次元配列を示し、配列内の各点には概念を
指すポインタが記入され、ポインタで指定される内容に
は、各概念が格納されている。図２０は、大きさ別の１
次元配列を作り、位置の順にソートされた概念が、配列
の各要素からのポインタで接続されたリスト構造を示
す。

【００２５】文字認識を行うときの黒板の使い方につい
て説明する。文字認識部５は、認識すべき文字の所定範
囲の輪郭部の構造を調べるために、スケールレベルを設
定して黒板データ記憶部４を参照する。黒板データ記憶
部４からは、図２１に示すようにスケールレベル以下の
概念が読みだされ、文字認識部５では、読みだされた概
念（角、凸弧、凹弧）を用いて、所定範囲の輪郭部の詳
細構造を識別処理する。このように、認識処理時に参照
する概念の数は、輪郭部を構成する画素数に比べて格段
に少ないデータ量であるので、高速に処理することがで
きる。

【００２６】前記した実施例の黒板の縦軸は、概念の大
きさであった。例えば、図２２は、折線（あるいは角）
であり、図２３は、ギザギザした点Ａと点Ｂを結ぶ直線
であるが、これを黒板で大きさ別の階層で表現すると、
図２２は、図２４になり、角であって、ＡとＢを結ぶ直
線でないということを表すことが比較的難しい。また図
２３は、図２５になり、全体としてはギザギザした線で
あるとしか、表すことができない。そこで、本発明の他
の実施例では、生成された概念を黒板に書き込む際に、
黒板の縦軸に概念の滑らかさを用いるようにしたもので
ある。図２６は、滑らかさによる概念の階層構造の例を
示す図である。

【００２７】直線の滑らかさとしては、例えば、図２７
において、ｐラインによって生成される直線ＡＢと各ｐ
ラインの両端との距離（２７１，２７２，２７
３．．．）の内、最も大きいもので、滑らかさを表す。
また、弧の滑らかさは、図２８において、ｐラインによ
って生成される弧ＡＢと各ｐラインの両端との距離（２
８１，２８２，２８３．．．）の内、最も大きいもの
で、滑らかさを表す。この滑らかさは、上記した距離の
他に距離の対数あるいは距離の関数にすることも可能で
ある。

【００２８】図２９は、図２２の折線を滑らかさで表現
した図である。図２９において、領域γ〜δ（これは図
２２の領域γ〜δに対応する）を指定すれば、角（折
線）と認識され、滑らかでない直線とみなされることは
ない。また、領域α〜β（これは図２２の領域α〜βに
対応する）を指定しても、図２２は折線と認識される。
図３０は、図２３のギザギザした線を滑らかさで表現し
た図である。

【００２９】このように、文字認識部５は、認識すべき
文字の所定範囲の輪郭部の構造を調べるために、領域を
指定して黒板データ記憶部４を参照し、黒板データ記憶
部４からは、領域内の概念が滑らかさ情報と共に読みだ
されるので、文字認識部５では、例えば、部分的にギザ
ギザしていても弧の一部である等と認識することができ
る。また、輪郭上のある領域を概念で表現する場合、図
３１において、文字認識部５が領域ＡからＢを指定して
概念を読みだしたとき、領域ＡからＢの形を、滑らかさ
の度合いが高い順に、「概念５，６，７から構成された
もの」、「概念４」、「概念３の一部」であると、認識
する。

【００３０】

【発明の効果】以上、説明したように、本発明によれ
ば、２値画像の輪郭部を、重なりを有する直線群で形成
することにより弧、角、直線の概念を生成しているの
で、曲線と直線の識別、更には弧と角の識別を容易に行
うことができる。

【図面の簡単な説明】

【図１】本発明の実施例に係るブロック構成図である。

【図２】２値化された線図形画像の例である。

【図３】重なりを持った直線が形成された図である。

【図４】極大直線を説明する図である。

【図５】極大直線が通過する領域の例である。

【図６】極大直線が通過する領域の他の例である。

【図７】量子化誤差が発生した直線の図である。

【図８】量子化誤差を吸収した極大直線の図である。

【図９】極大直線の集合を説明する図である。

【図１０】８方向線の一例を示す図である。

【図１１】行毎のドットシーケンスを示す図である。

【図１２】行あるいは列のドットシーケンスを示す図で
ある。

【図１３】行および列のドットシーケンスを示す図であ
る。

【図１４】ｐラインから角の概念が生成された図であ
る。

【図１５】ｐラインから弧と直線の概念が生成された図
である。

【図１６】ｐラインから弧の概念が生成された図であ
る。

【図１７】ｐラインの一部だけを角の概念に取り込んだ
図である。

【図１８】黒板に書き込まれた概念を示す図である。

【図１９】２次元配列の黒板のデータ構造図である。

【図２０】リスト構造の黒板のデータ構造図である。

【図２１】スケールレベルが設定された黒板の図であ
る。

【図２２】折線を示す図である。

【図２３】ギザギザした直線を示す図である。

【図２４】図２２を、黒板で大きさ別の階層で表した図
である。

【図２５】図２３を、黒板で大きさ別の階層で表した図
である。

【図２６】滑らかさによる概念の階層構造図である。

【図２７】直線の滑らかさを説明する図である。

【図２８】弧の滑らかさを説明する図である。

【図２９】図２２の折線を滑らかさで表現した図であ
る。

【図３０】図２３の線を滑らかさで表現した図である。

【図３１】輪郭上のある領域を概念で表現する場合の説
明図である。

【符号の説明】 １ ２値化処理部 ２ ｐライン生成部 ３ 概念生成部 ４ 黒板データ記憶部 ５ 文字認識部

Claims (1)

【特許請求の範囲】
1. 【請求項１】 ２値画像の輪郭を、重なりを有する直線
   群によって生成し、該生成された直線群に基づいて、該
   輪郭を構成する角と弧と直線とを識別することを特徴と
   する文字認識方法。