JPH06131499A

JPH06131499A - 特徴抽出方法

Info

Publication number: JPH06131499A
Application number: JP4280130A
Authority: JP
Inventors: Toru Miyamae; 徹宮前; Koji Ito; 晃治伊東
Original assignee: Oki Electric Industry Co Ltd
Current assignee: Oki Electric Industry Co Ltd
Priority date: 1992-10-19
Filing date: 1992-10-19
Publication date: 1994-05-13

Abstract

(57)【要約】【目的】２値画像より求めた輪郭点座標系列及び線幅
情報を用いて、高速処理可能で高精度かつ耐ノイズ性に
優れた文字図形パタンの端点情報を抽出する特徴抽出方
法を提供する。【構成】２値画像より求められた輪郭点座標系列から
変曲点が先ず抽出され、この変曲点と輪郭点座標系列と
線幅とに基づいて仮端点が抽出される。更に、仮端点と
輪郭点座標系列と線幅とに基づいて真の端点の位置及び
その符号が文字図形パタンの特徴として抽出される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、文書等を光学的に読
み取る光学式文字読み取り装置（ＯＣＲ）等において、
認識に重要な役割を果たす文字図形パタンの端点に関す
る情報を高精度に抽出する方法に関するものである。

【０００２】

【従来の技術】従来、この分野においては例えば文献
（「筆順情報を利用した手書き漢字の分類方法」：信学
技報ＰＲＬ８０−２４、高橋時市郎、小高和己、増田
功（ＮＴＴ））に開示される方法がある。以下、上記文
献に開示された従来の技術について説明する。図１０は
従来の端点抽出方法の処理手順を示す流れ図である。先
ず、文書や帳票上に書かれた文字を光電変換装置によっ
て量子化された電気信号（ディジタル信号）である２値
画像に変換する（ステップＳ１０１）。図１１は、数字
の４の２値画像の例を示したもので文字部分が黒、背景
部は白で表現されているが、これらはそれぞれ有限個の
黒ドット（黒点）と白ドット（白点）とから構成されて
いる。尚、これらのドットの大きさは光電変換装置の分
解能に依存している。図１０の次のステップＳ１０２で
は、光電変換された２値画像に対して細線化を行い、細
線化パタンに変換する。

【０００３】図１２は図１１の２値画像を細線化パタン
に変換したものを表し、点１１２，１１３，１１４，１
１５が端点に相当している。ステップＳ１０３では前記
細線化したパタンに対し３×３メッシュのマスク走査を
行い、３×３のメッシュを通して見た黒点のパタンから
端点を決定する。尚、１メッシュはドットを観測する窓
に相当し、３×３メッシュ走査とは、縦３メッシュ、横
３メッシュの正方形領域による走査であり、文字枠で囲
まれた矩形領域全てを走査するまで（ステップＳ１０
４）続けられる。

【０００４】図１３は、図１２の端点１１５を３×３メ
ッシュの中央のメッシュで観測した時の黒点のパタンを
示したものである。図１３の斜線部は黒点を、それ以外
は白点を観測したものとする。図１３ではメッシュ１２
０が端点１１５を観測しているため黒点となっており、
その近傍の８メッシュの内、メッシュ１２３が黒点でそ
れ以外は全て白点である。同様に、図１２の端点１１
２，１１３，１１４をメッシュ１２０によって観測した
時、それぞれメッシュ１２２，１１７，１１９が黒点
を、残りの７メッシュが白点を観測する。このように、
端点はその近傍の８メッシュを観測した時、１つのメッ
シュだけが黒点を観測するということによって特徴ずけ
られる。以上のようにして、従来の技術は細線化パタン
に対し３×３メッシュによるマスク走査を行い、前述の
特徴を示す点を端点と決定している。

【０００５】

【発明が解決しようとする課題】しかしながら、以上述
べた端点抽出方法は、以下のＡ〜Ｃの問題点があった。Ａ．細線化処理に時間がかかる。Ｂ．細線化処理による文字図形パタンの情報劣化があ
る。例えば、先端部が非常に太いストロークが細線化に
よって２つに分裂した細線として表され、その結果端点
が２つ抽出されてしまうことがある。Ｃ．メッシュが１ドット単位であるため、小さいノイズ
によっても端点と判定されることがあり、ノイズに弱
い。

【０００６】この発明は、以上述べた従来の端点抽出方
法の細線化による処理時間の増大と文字図形パタンの情
報劣化という問題点及び１ドット単位のマスク走査によ
る耐ノイズ性の低さという問題点を除去するため、２値
画像より求められた輪郭点座標系列及び線幅を用いるこ
とによって、処理時間が少なく、しかも高精度で耐ノイ
ズ性に優れた端点抽出方法を提供することを目的とす
る。

【０００７】

【課題を解決するための手段】この発明は、前記課題を
解決するために、文字図形パタンを光電変換して２値画
像に変換する工程と、前記２値画像から文字図形パタン
の線幅を計算する工程と、前記２値画像から文字図形パ
タンの輪郭点座標系列を抽出する工程と、前記輪郭点座
標系列から変曲点を抽出する工程と、前記変曲点と前記
輪郭点座標系列と前記線幅とに基づいて仮端点を抽出す
る工程と、前記仮端点と前記輪郭点座標系列と前記線幅
とに基づいて真の端点を抽出する工程と、前記真の端点
の符号を決定する工程とを有することを特徴とする。

【０００８】

【作用】前記構成の特徴抽出方法においては、２値画像
より求められた輪郭点座標系列から変曲点が先ず抽出さ
れ、この変曲点と輪郭点座標系列と線幅とに基づいて仮
端点が抽出される。更に、仮端点と輪郭点座標系列と線
幅とに基づいて真の端点の位置及びその符号が文字図形
パタンの特徴として抽出される。従って、従来のように
細線化処理による処理時間の増加及び細線化歪によるノ
イズ等に起因する抽出誤りがなく、高速に高精度に特徴
抽出が可能となる。

【０００９】

【実施例】図１は、この発明の実施例の処理手順を示す
流れ図である。先ず、ステップＳ１において、文書や帳
票等に書かれた文字図形パタンを光電変換装置により２
値画像に変換する。

【００１０】図１１は数字４の２値画像の例を示したも
ので、この２値画像については、その文字部分が外接す
る文字枠１０５が検出されている。ここで、文字枠１０
５の横軸、縦軸を各々Ｘ軸、Ｙ軸とする直角座標系（図
１１の左上隅を原点とする）を考えると、２値画像を構
成するドットの座標が定まる。

【００１１】次に、ステップＳ２において、文字枠１０
５によって規定される矩形領域の内部（０≦ｘ≦Ｘ_e；
０≦ｙ≦Ｙ_e）に存在する黒点数Ａ、４黒点数Ｑを計数
し、線幅Ｗを計算する。線幅Ｗは、Ｗ＝Ａ／（Ａ−Ｑ）（１）で計算される。この式（１）による線幅Ｗは、２値画像
の文字線の平均的な線幅を表したものである。また、式
（１）における４黒点数Ｑとは４個の黒点が隣接してい
る状態の数であり。具体的には黒点（ｘ，ｙ）が与えら
れた時、３つの点（ｘ＋１，ｙ），（ｘ，ｙ＋１），
（ｘ＋１，ｙ＋１）が全て黒点である時、黒点（ｘ，
ｙ）を４黒点と称し、その個数を計数したものである。

【００１２】ステップＳ３では２値画像から文字の輪郭
線を構成する輪郭点を抽出し、それら全ての座標を求め
て、輪郭点座標系列としてメモリに格納しておく。例え
ば、図１１の２値画像では、開始点１０６から始まり、
図１１の点線に沿って反時計回り（順方向）に輪郭追跡
を行い、その順番に全ての輪郭点座標を輪郭点座標系列
としてメモリに格納する。上述のステップＳ１〜Ｓ３に
より端点を抽出するための準備を終了し、次のステップ
Ｓ４〜Ｓ６で実際に端点の抽出を行う。

【００１３】ステップＳ４では、輪郭点座標系列を前記
順方向に参照しながら（順方向サーチともいう）、変曲
点を抽出していく。本実施例における変曲点の定義は、
輪郭点のＸ座標又はＹ座標の変化の仕方が変化する点と
して与えられるものであり、数学に於ける通常の定義と
は異なる。例えば、輪郭点座標系列を順方向に１つずつ
参照する時、ある輪郭点（ｘ，ｙ）と１つ後ろの点（ｘ
_a，ｙ_a）との間のＸ座標又はＹ座標の変化が、１つ前
の点（ｘ_b，ｙ_b）との間のＸ座標又はＹ座標の変化の
仕方と異なる時、点（ｘ，ｙ）を変曲点と見なすことに
する。尚、点（ｘ，ｙ）が輪郭点座標系列の最初の点で
ある時、１つ前の点（ｘ_b，ｙ_b）とは輪郭点座標系列
の最後の点であり、逆に、点（ｘ，ｙ）が輪郭点座標系
列の最後の点である時、１つ後ろの点（ｘ_a，ｙ_a）と
は輪郭点座標系列の最初の点である。ここで、ｘ_a＞
ｘ，ｘ_a＜ｘ，ｙ_a＞ｙ，ｙ_a＜ｙという変化を示す変
曲点（ｘ，ｙ）を各々、Ｘ_up点、Ｘ_down点、Ｙ_up点、Ｙ
_down点と称し、このような変曲点が図１１の２値画像に
ついて抽出された例を図２に示す。図２より、点２０は
ｘ_a＜ｘ，かつｙ_a＞ｙという変化を示すので、Ｘ_down
点でありかつＹ_up点である。点２１ではｘ_a＞ｘとなる
のでＸ_down点となる。同様に輪郭点座標系列が終了する
まで点２２，２３，２４，２５，２６，２７，２８，２
９も変曲点として抽出されメモリに格納される。

【００１４】ステップＳ５では、以上のように抽出され
た変曲点の各々について、前記輪郭点座標系列に基づく
仮端点の抽出を行う。図３は、仮端点を抽出する方法の
説明図であり、図２の点２７の付近を拡大したもので、
順方向サーチによるＹ_up点３０（ｘ₃₀，ｙ₃₀）が与えら
れている。点３０の順方向上での次の点３１（ｘ₃₁，ｙ
₃₁）と前の点３５（ｘ₃₅，ｙ₃₅）及び点３０（ｘ₃₀，ｙ
₃₀）との間に、ｙ₃₁＞ｙ₃₀かつ、ｙ₃₀＝ｙ₃₅という関係
が成立しており、確かにＹ_up点であることがわかる。

【００１５】ここで、仮端点を抽出するために点３０よ
り逆方向に輪郭点座標系列をサーチし、点３０と同様な
変化を示す変曲点（ここではＹ_up点）を抽出する。但
し、この逆方向のサーチは、局所的なものであり、サー
チ範囲は図３では点３０より逆方向に線幅×α（α〜
２）離れた点３４までである。この逆方向サーチにおい
て、図３では点３６（ｘ₃₆，ｙ₃₆）から点３２（ｘ₃₂，
ｙ₃₂）に至る変化はｙ₃₂＝ｙ₃₆であるのに対し、点３２
から点３３（ｘ₃₃，ｙ₃₃）に至る変化はｙ₃₃＞ｙ₃₂とな
る。従って、点３２は逆方向サーチによるＹ_up点であ
る。

【００１６】このように、１つの変曲点から出発して逆
方向の局所的なサーチにより、同様な変化を示す別の変
曲点を抽出し、これらの変曲点に基づいて仮端点を抽出
する。図３の例では、順方向サーチによるＹ_up点３０及
び逆方向サーチによるＹ_up点３２の輪郭点座標系列上の
中点３７を仮端点とする。同様にして、他の変曲点全て
についても同様の仮端点の抽出方法が適用される。しか
し、全ての変曲点について、仮端点が抽出されるわけで
はない。図４は、仮端点が抽出されない例について示し
たものであり、図２の点２６付近を拡大したものであ
る。

【００１７】図４において、点４０は図２の点２６に相
当する順方向サーチによるＹ_down点であり、点４１は点
４０から逆方向に線幅×αだけ離れた逆方向サーチの最
終点である。しかし、点４０から点４１に至る逆方向サ
ーチにおいて、点４０と同じ変化であるＹ_down点は存在
しない。従って、このような場合には、仮端点は抽出さ
れない。以上のようにして、図２の変曲点では、点２
０，２１，２３，２５，２７，２９に基づいて仮端点が
抽出され、メモリに格納される。

【００１８】ステップＳ６ではステップＳ５で抽出され
た仮端点の各々に対して、真の端点であるか否かを、輪
郭点座標系列及び線幅Ｗを用いることによって決定す
る。端点の決定方法を図５を用いて説明する。

【００１９】図５において、仮端点ａ（ｘ_a，ｙ_a）５
０が抽出された時、輪郭点座標系列に基づいて、仮端点
ａから順方向及び逆方向に各々線幅×β（β〜１．５）
だけ離れた２点ｂ（ｘ_b，ｙ_b）５１，ｃ（ｘ_c，
ｙ_c）５２を求める。ここで、２点ｂｃ間の距離ｄが次
式ｄ＜線幅Ｗ × γ （２）を満足する時、仮端点ａを真の端点と見なす（以後、単
に端点と称する）。但し、γ〜２、且つγ＜２×βであ
る。尚、距離ｄを与える式としては、ｄ＝ＭＡＸ（｜ｘ_c−ｘ_b｜、｜ｙ_c−ｙ_b｜）＋［ＭＩＮ（｜ｘ_c−ｘ_b｜、｜ｙ_c−ｙ_b｜）］／２（３）を用いる。式（２）、（３）に基づき、例えば、図６に
示したような仮端点６０は点６１と６２間の距離が大き
くなるため、端点から除外される。

【００２０】以上説明したような判定方法により、端点
が決定される。例えば、図２においては、点２０，２
３，２５，２７が端点として抽出され、メモリに格納さ
れる。しかし、ステップＳ６で決定された端点の中に
は、図５の点ａのように極大付近に存在するものだけで
なく、図７の点ｄ（７０）のように極小付近に存在する
ものが含まれている。従来の端点の定義に従えば、図７
の点ｄは端点として認められない。しかし、端点ａ（図
５の５０）を＋（プラス）端点、点ｄを−（マイナス）
端点と定義して、−端点を端点に含めれば、それだけ文
字の特徴が増え、認識に有利になると考えられる。いず
れにしても、抽出された端点が＋端点であるか−端点で
あるかを区別する必要がある。そのために次のステップ
Ｓ７で端点の符号（＋，−）を決定する。

【００２１】ステップＳ７においては、抽出された端点
から順方向及び逆方向に線幅×δ（δ〜１．５）離れた
２輪郭点について、前記端点を原点とする位置ベクトル
を求め、両ベクトルの外積の符号により＋端点か−端点
かを判定する。ここでは、端点より線幅×δ離れた２点
としたが、ステップＳ６における仮端点より線幅×β離
れた２点としてもさしつかえない。この方法による端点
の符号の判定を図５に当てはめると、端点ａを原点とす
る位置ベクトルは各々、ベクトルＶ_ab，Ｖ_acとなり、従
ってその外積Ｖ_S1は、Ｖ_S1 ＝Ｖ_ab × Ｖ_ac （４）となる。また、上記方法を図７に当てはめると、端点ｄ
を原点とする位置ベクトルは各々、Ｖ_de，Ｖ_dfとなり、
従ってその外積Ｖ_S2は、Ｖ_S2 ＝Ｖ_de × Ｖ_df （５）となる。ここで、Ｖ_S1の符号は正、Ｖ_S2の符号は負であ
ることから、外積ベクトルの符号が正の時は＋端点、負
の時は−端点であると判定できる。

【００２２】しかし、外積ベクトルが零ベクトルになり
符号が零になる場合もある。図８は＋端点で符号零の場
合、図９は−端点で符号零の場合を各々示したものであ
る。何れにしても３点が一直線上に並ぶ場合であり、外
積ベクトルの符号による上記判定方法が適用できない。
このような場合は、例えば図８において、端点８０より
順方向及び逆方向に離れた２点８１，８２のうち、端点
８０からの距離が大きい点８２を選び、端点８０から８
２に至る輪郭点座標系列上で点８１と同じ座標をもつ点
が存在した場合は＋端点、存在しない場合は−端点であ
ると判定する。この−端点の判定の正当性は、図９にお
いて、端点９０から９２に至る輪郭点座標系列上で点９
１と同じ座標をもつ点が存在しないことから明らかであ
る。尚、点８１と点８２の座標が一致している場合は、
輪郭点座標系列をサーチしないで＋端点であると判定で
きる。以上の端点の符号判定を、ステップＳ６で求めら
れた端点の各々に適用してステップＳ７を終了する。

【００２３】前述のステップＳ４〜Ｓ７では、各々のス
テップの処理が全て終了してから次のステップに進む
が、必ずしもそうである必要はない。例えば、ステップ
Ｓ４では輪郭点座標系列を全てサーチし、文字図形パタ
ンの全ての変曲点をメモリに格納してから次のステップ
Ｓ５，Ｓ６，Ｓ７に進むが、１つ変曲点を見つける毎に
次のステップに進み、ステップＳ７が終了したら再びス
テップＳ４に戻って同様の処理を輪郭点座標系列が終了
するまで続けるという方法でも全く同様な結果が得られ
る。つまりステップＳ４〜Ｓ７を連結させて繰り返し処
理を行う方法である。また、ステップＳ４が終了してか
らステップＳ５〜Ｓ７を連結させるという方法も同様な
結果となる。以上のようなステップを連結する方法は何
通りかあるがその何れであっても本発明の実施例を表す
ものであることはいうまでもない。

【００２４】

【発明の効果】以上詳細に説明したように、この発明に
よれば、文字図形パタンの端点を抽出する際に、細線化
パタンでなく輪郭点座標系列を用いるようにしたので、
処理時間が少ないという効果、及び前記文字図形パタン
の情報劣化が起こらず、より正確に端点を抽出できると
いう効果がある。

【００２５】更に、前記輪郭点座標系列及び文字図形パ
タンの線幅に基づいて、仮端点抽出、端点決定を行うよ
うにしたので、線幅より小さいノイズ、或いはヒゲ等に
よる端点抽出の誤りを防止できる効果がある。しかも、
光電変換装置の分解能や前記文字図形パタンの文字線の
太さ、サイズ等に応じて、線幅の値も変化するので、そ
れらの要因に依存しない安定した性能が得られるという
効果もある。

【図面の簡単な説明】

【図１】本発明の実施例の処理手順を示す流れ図であ
る。

【図２】変曲点の抽出例を示す図である。

【図３】仮端点の抽出方法の説明図である。

【図４】仮端点が抽出されない例を示す図である。

【図５】端点決定方法の説明図である。

【図６】端点にならない場合の一例を示す図である。

【図７】−端点の一例を示す図である。

【図８】＋端点で符号が零となる場合を示す図である。

【図９】−端点で符号が零となる場合を示す図である。

【図１０】従来の端点抽出方法の処理手順を示す流れ図
である。

【図１１】２値画像の一例を示す図である。

【図１２】図１１の２値画像の細線化パタンを示す図で
ある。

【図１３】端点抽出用の３×３メッシュを示す図であ
る。

Claims

【特許請求の範囲】

【請求項１】文字図形パタンを光電変換して２値画像
に変換する工程と、前記２値画像から文字図形パタンの線幅を計算する工程
と、前記２値画像から文字図形パタンの輪郭点座標系列を抽
出する工程と、前記輪郭点座標系列から変曲点を抽出する工程と、前記変曲点と前記輪郭点座標系列と前記線幅とに基づい
て仮端点を抽出する工程と、前記仮端点と前記輪郭点座標系列と前記線幅とに基づい
て真の端点を抽出する工程と、前記真の端点の符号を決定する工程とを有することを特
徴とする特徴抽出方法。
【請求項２】請求項１に記載の特徴抽出方法におい
て、前記変曲点を抽出する工程は、前記輪郭点座標系列
における着目点とその前後の輪郭点において、輪郭点の
Ｘ座標またはＹ座標の変化の仕方が異なるか否かに基づ
いて、変曲点の判定を行うことを特徴とする特徴抽出方
法。
【請求項３】請求項１ないし請求項２に記載の特徴抽
出方法において、前記仮端点を抽出する工程は、着目す
る変曲点に対して、前記輪郭点座標系列の抽出工程で輪
郭点を探索した方向（順方向）と逆の方向に線幅×α
（α〜２）の距離範囲から検出された変曲点のタイプが
前記着目する変曲点のタイプと一致する時に、これらの
変曲点に基づいて決定した輪郭点を仮端点として抽出す
ることを特徴とする特徴抽出方法。
【請求項４】請求項１ないし請求項３に記載の特徴抽
出方法において、前記真の端点を抽出する工程は、前記
仮端点から順方向及び逆方向に線幅×β（β〜１．５）
離れた２つの輪郭点間の距離が線幅×γ（γ〜２、かつ
γ＜２×β）以下の時、当該仮端点を真の端点として抽
出することを特徴とする特徴抽出方法。
【請求項５】請求項１ないし請求項４に記載の特徴抽
出方法において、前記符号を決定する工程は、着目する
仮端点から順方向及び逆方向に線幅×δ（δ〜１．５）
離れた２輪郭点についての前記仮端点を原点とする位置
ベクトルの外積の符号に基づいて端点の符号を決定する
ことを特徴とする特徴抽出方法。