JPH0135385B2

JPH0135385B2 -

Info

Publication number: JPH0135385B2
Application number: JP56046179A
Authority: JP
Inventors: Toyoshi Sato
Original assignee: Tokyo Shibaura Electric Co Ltd
Current assignee: Toshiba Corp
Priority date: 1981-03-31
Filing date: 1981-03-31
Publication date: 1989-07-25
Also published as: JPS57161983A

Description

【発明の詳細な説明】本発明は特徴抽出装置の改良に関するものであ
る。

光学的文字読取装置において、パターン認識と
する為に用いられる特徴として、パターンの線縁
特徴（線縁長や方向コード列等）があることは従
来より知られている。

ここで、第１図に従来の線縁特徴を抽出する為
の特徴抽出装置を示す。

１は、パターンメモリであり、パターンメモリ
は一文字分のパターンを保持する為のものである２は、線縁追跡部であり、線縁追跡部２は、プ
ログラム制御でパターンの線縁特徴を抽出するも
のである。

３は、バツフアメモリであり、バツフアメモリ
３は、線縁追跡部２が抽出したパターンの線縁特
徴を保持する為のものである。

第２図は、パターンメモリ１に保持されたパタ
ーンを視覚的に表現した図であり、第２図のパタ
ーンの線縁追跡をする場合を例に、従来の特徴抽
出装置の動作を説明する。

尚、第２図において、Pt（ｔ＝１〜12）はパタ
ーンの輪郭線縁を構成する黒ビツトを示し、ｔは
追跡されるタイミングを表現している。

線縁追跡部２は、パターンメモリ１を左上から
ラスタスキヤンし、走査線上に最初に現われる黒
ビツトを検出する。黒ビツトP₁がこれに該当す
る。

黒ビツトP₁を検出すると、線縁追跡部２はラ
スタスキヤンを中止し、線縁追跡動作に入る。

先ず、制御部２は黒ビツトP₁の座標（２、１）
をバツフアメモリ３に格納し、続いて、黒ビツト
P₁を中心として、黒ビツトP₁に隣接する周囲８
ビツトの論理レベルを判定し、黒ビツトP₁に隣
接する黒ビツトを検出する。

周囲８ビツトの論理レベルの判定は、黒ビツト
P₁を中心として、第３図の「２」の方向から時
計廻りに行なわれる。

これによつて、線縁追跡部２は、黒ビツトP₂
を検出する。

黒ビツトP₂を検出すると、線縁追跡部２は黒
ビツトP₁から黒ビツトP₂へ向う方向コードV₁＝
３を求め、方向コードV₁＝３をバツフアメモリ
３に格納する。

尚、以下で方向コードVt（ｔ＝１〜２）は黒ビ
ツトPtから黒ビツトPt＋１への方向を表わす。

黒ビツトP₂を検出すると、線縁追跡部２は、
黒ビツトP₂を中心として、方向コードV₁＝３か
ら２を滅した方向、即ち、１の方向から、黒ビツ
トP₂に隣接するビツトの論理レベルを求め、黒
ビツトP₃を検出する。

以下同様にして、線縁追跡部２は、黒ビツト
P12まで追跡して行き、黒ビツトPtの座標及び黒
ビツトPtから黒ビツトPt＋１に向う方向コード
Vtをバツフアメモリ３に格納する。

ところで、光学的文字読取装置において、文字
「Ｎ」の様に鋭角的な文字を読むと、第４図の如
く、鋭角部分に微少ループが生じやすいことは良
く知られている。この微少ループは、アナログ信
号を量子化する時や、デジタルパターンを圧縮す
る時に発生するものであるが、従来の特微抽出装
置を用いた場合、パターンメモリ内に微少ループ
がある場合、抽出された特徴に誤まりが生じるお
それがあつた。

次に、この点を具体的に説明する。

第５図は第４図の微少ループ部分を拡大した図
である。第５図の座標（４、５）のｗが微少ルー
プである。

従来の特徴抽出装置の場合、パターンメモリ１
に第５図の様なパターンが書き込まれると、線縁
追跡部２は第６図の矢印の如く、座標（４、６）
点から座標（３、７）点、座標（３、８）点と線
縁を追跡してしまうことになる。

この為、ループ数を検出するに際して、本来な
らばループ数として数えられるべきでない微少ル
ープを、パターンのループ数として計数してしま
う（具体的には文字「Ｎ」を読みとつた場合にル
ープが２つあると判断してしまう）という欠点が
あつた。

本発明は、この様な欠点に鑑みなされたもので
あり、第５図の様なパターンがパターンメモリに格約
された場合、第７図の矢印の如く、座標（４、
６）点から座標（５、５）点、座標（４、４）
点、座標（３、５）点、座標（３、６）点、座標
（３、７）点と、線縁追跡をすることを可能なら
しめることにより、微少ループの影響を受けるこ
となく正確な特徴を抽出できる。特徴抽出装置を
提供することを目的とする。

次に、図面を参照して、本発明の一実施例を詳
細に説明する。

第８図は、本発明の一実施例に係る特徴抽出装
置のブロツク図である。

従来と同一のものは、第１図と同じ符号により
説明に代えるが、図中４は線縁追跡部、５は微少
ループ追跡部を示している。

線縁追跡部４はプログラム制御でパターンの輪
郭線縁の追跡及び、パターンメモリ１中のあるビ
ツトが微少ループとなり得る為の条件の検出をす
る為のものである。

具体的には、線縁追跡部４は、次の様なステツ
プからなるプログラムを持つている。

第１ステツプ……各黒ビツトPt（ｔ＝１−ｍ）
の周囲８ビツトの論理レベルを、方向コードVt
−１から２減した方向にあるビツトから時計廻り
に調べていき、最初に現われる黒ビツトを検出す
る。

第２ステツプ……第１ステツプで検出した黒ビ
ツトから、更に時計廻りに３ビツト分の論理レベ
ルを調べる。

第３ステツプ……第２ステツプで白ビツトを検
出しないと、第１ステツプで検出した黒ビツトを
黒ビツトPt＋１と定義し、黒ビツトPt＋１の座
標及び、方向コードVtをバツフアメモリ３に格
納し、第１ステツプに戻る。

一方、第２ステツプで白ビツトを検出すると、
次の第４ステツプに移る。

第４ステツプ……第２ビツトで検出した白ビツ
トから更に時計廻りに３ビツト分の論理レベルを
調べる。

第５ステツプ……第４ステツプで黒ビツトを検
出しないと、第１ステツプで検出した黒ビツトを
黒ビツトPt＋１と定義し、黒ビツトPt＋１の座
標及び、方向コードVtをバツフアメモリ３に格
納し、第１ステツプに戻る。

又、第４ステツプで既に追跡ずみのと同じ黒ビ
ツトを検出すると、第１ステツプで検出した黒ビ
ツトを黒ビツトPt＋１と定義し、黒ビツトPt＋
１の座標及び方向コードVtをバツフアメモリ３
に格納し、第１ステツプに戻る。

一方、第４ステツプで第１ステツプで検出した
黒ビツト以外の黒ビツトを検出すると、第６ステ
ツプに移る。

第６ステツプ……微少ループとなり得る条件を
満するものと判断し、黒ビツトPtの座標を微少
ループ追跡部５に与え、微少ループ追跡部５内に
コントロールを移す。

第７ステツプ……微少ループ追跡部５からの割
り込みを受けつけると、微少ループ追跡部５のフ
ラツグレジスタを見る。

第８ステツプ……フラツグレジスタが「０」に
セツトされていると、第１ステツプで検出した黒
ビツトを黒ビツトPt＋１と定義し、黒ビツトPt
＋１の座標及び、方向コードVtをバツフアメモ
リ３に格納し、第１ステツプに戻る。

一方、フラツグレジスタが「１」にセツトされ
ていると微少ループ追跡部５から供給された、微
少ループの輪郭線縁を構成する黒ビツトの座標及
び、方向コードをバツフアメモリに格納し、第１
ステツプに戻る。

微少ループ追跡部５は、プログラム制御で微少
ループである可能性のあるビツトの輪郭線縁を追
跡し、微少ループとなり得ない条件を一つでも満
足するとフラツグレジスタに「０」をセツトし、
微少ループとなり得ない条件を一つも満足しない
とフラツグレジスタに「１」をセツトする様にな
されている。

具体的には、微少ループ追跡部５には、第９図
に示す様なステツプからなるプログラムが与えら
れている。

第１ステツプ……線縁追跡部４から与えられた
黒ビツトPtのＸ座標値をSPXレジスタにＹ座標
値をSPYレジスタに格納し、続いてCTカウンタ
をクリヤする。

第２ステツプ……黒ビツトPt周囲８ビツトの
論理レベルを方向コードVtから１減じた方向に
あるビツトから調べていき最初にあらわれる論理
「０」でないビツトを検出すると、CTカウンタを
１カウントし第３ステツプに移る。

第３ステツプ……黒ビツトPtの周囲８ビツト
の論理レベルを方向コードVt−１から２減じた
方向にあるビツトから調べていき最初にあらわれ
る論理「０」でないビツトを検出するとCTカウ
ンタを１カウントし、第４ステツプに移る。

第４ステツプ……第３ステツプで検出されたビ
ツトの論理レベルが「−１」の時は、第11ステツ
プにジヤンプレ、第３ステツプで検出されたビツ
トの論理レベルが「１」の時は第５ステツプに移
る。

尚、輪郭線縁追跡過程で既に検出されたビツト
の論理レベルは「−１」とされている。

第５ステツプ……CTカウンタの内容を調べ、
カウント値が９以上の場合は第11ステツプへジヤ
ンプし、カウント値が８以下の場合は第６ステツ
プへ移る。

第６ステツプ……第２ステツプもしくは第３ス
テツプで検出されたビツトのＸ座標がSPXレジ
スタの内容と一致しかつＹ座標がSPYレジスタ
の内容と一致する時は、微少ループの輪郭線縁の
追跡が終了したとして、第７ステツプへ移向し、
一致しない時は、第２ステツプもしくは第３で検
出したビツトの座標及び、その方向コードを内部
レジスタに格納して、第３ステツプヘリターンす
る第７ステツプ……CTカウンタの内容を調べ、
３以下の場合は、第11ステツプへジヤンプし、３
以上の場合は、第８ステツプへ移向する。

第８ステツプ……微少ループの輪郭線縁の追跡
が終了した時点における方向コードと微少ループ
の輪郭線縁の追跡を開始した時点における方向コ
ードとを比較し、所定の関係にある場合は第９ス
テツプに移向し、しからざる場合は、第11ステツ
プにジヤンプスする。

尚、所定の関係とは、開始点の方向コードを
SFP終了点の方向コードをEPとした場合。

SFP＜FP＋２、又は、FP＋４＜SFPのいずれか
を満足することをいう。

但し、方向コードは「７」の次が「０」である
ので、FP＝７とするとFP＋２＝１、FP＋４＝
３。FP＝６とするとFP＋２＝０、FP＋４＝２。
FP＝５とするとFP＋２＝７、FP＋４＝１。FP
＝４とするとFP＋２＝６、FP＋４＝０となるも
のとする。

第９ステツプ……微少ループの輪郭線縁の追跡
が終了した時点における方向コードに＋１した方
向から隣接ビツトの論理レベルを調べ最初に検出
した黒ビツトの座標、及び、その方向コードを内
部レジスタに格納する。

第10ステツプ……フラツグレジスタに「１」立
てて終了する。

第11ステツプ……フラツグレジスタに「０」を
立てて終了する。

次に、第１０図に示すパターンの輪郭線縁を追
跡する場合を例に動作説明をする。

現在座標（７、１）点にある黒ビツトP₁を検
出しているとする。

黒ビツトP₁に進入する方向コードV₀は「２」
である。従つて、線縁追跡部４は、方向コード
「０」の方向の隣接ビツトから時計廻りに隣接ビ
ツトの論理レベルを調べて行く。

即ち、線縁追跡部４は座標（７、０）点、座標
（８、０）点、座標（８、１）点の順に論理レベ
ルを調べていく。座標（８、１）点は黒ビツトで
あるので、線縁追跡部４は、座標（８、１）点の
座標、及び、黒ビツトP₁から座標（８、１）点
に向う方向コードを内部レジスタに格納する。

続いて、線縁追跡部４は、座標（８、２）点、
座標（７、２）点、座標（６、２）点の論理レベ
ルを調べる。これらの点は、全て黒ビツトである
ので、線縁追跡部４は、座標（８、１）点を黒ビ
ツトP₂と、又、黒ビツトP₁から黒ビツトP₂に向
う方向コードを方向コードV₁と定義し、黒ビツ
トP₂の座標（８、１）及び、方向コードV₁＝２
をバツフアメモリ３に格納し、黒ビツトP₂を中
心として線縁追跡を続行する。

輪郭線縁の追跡が進行し、現在黒ビツトP₃が
検出されたとする。

黒ビツトP₃に進入する方向コードV₂は「４」
であるので、線縁追跡部４は、黒ビツトP₃を中
心として、時計廻りに「２」の方向から輪接ビツ
トの論理レベルを調べていく。

座標（14、６）点は黒ビツトであるので、線縁
追跡部４は、座標（14、６）点の座標と黒ビツト
P₃から座標（14、６）点に進入する方向コード
を線縁追跡部４の内部レジスタに格納する続いて、線縁追跡部４は、座標（13、６）点、
座標（12、６）点、座標（12、５）点の論理レベ
ルを知らべる。

座標（13、６）点は白ビツトで、座標（12、
６）点は黒ビツトであるので、線縁追跡部４は、
座標（13、６）点が微少ループとなり得ると判断
して、黒ビツトP₃の座標を微少ループ追跡部５
に与え、微少ループ追跡部５に対して割り込みを
かける。

微少ループ追跡部５は、割り込みを受けつける
と黒ビツトP₃のＸ座標をSPXレジスタに、Ｙ座
標をSPYレジスタに格納し、CTカウンタをクリ
ヤする。

従つて、この時点でSPXレジスタには「13」
が、SPYレジスタには「５」が、CTカウンタに
は「０」がセツトされる。

微少ループ追跡部５は、座標（12、６）点、座
標（13、７）点、座標（14、６）点と追跡してい
き、その都度、CTカウンタを１ずつカウントア
ツプしていく。

座標（13、５）点に戻つた時点で、そのＸ座標
「13」はSPXレジスタの内容と、又、Ｙ座標は
SPYレジスタの内容と一致するので、微少ルー
プ追跡部５は、CTカウンタの内容を調べる。

この時、CTカウンタの内容は「４」であるの
で、微少ループ追跡部５は、戻り方向を調べる。

黒ビツトP₃から、座標（12、６）点への方向
コードは「５」であり、座標（14、６）点から黒
ビツトP₃への方向コードは７である。即ち、黒
ビツトP₃においては、SFP＝５かつFP＝７であ
るので、FP＋４＜SFPを満足する。

座標（14、６）点の方向コード「７」であるの
で、微少ループ追跡部５は、座標（14、６）点を
中心に「０」の方向から時計廻りに隣接ビツトの
論理レベルを調べる。

座標（15、６）点が黒ビツトであるので、座標
（15、６）点の座標、及び、座標（14、６）点か
ら座標（15、６）点へ向う方向コードを内部レジ
スタに格納する。

次に、微少ループの追跡部５は、フラツグレジ
スタに「１」をセツトし、線縁追跡部４に割り込
みをかける。

尚、この時、微少ループ追跡部５の内部レジス
タには、次の内容が、微少ループ内の線縁特微と
して格納されている。

座標（13、５）点から座標（12、６）点へ向
う方向コード「５」座標（12、６）点の座標（12、６）点（12、６）点から座標（13、７）点へ向う方
向コード「３」座標（13、７）点の座標（13、７）座標（13、７）点から座標（14、６）点へ向
う方向コード「１」座標（14、６）点の座標（14、６）座標（14、６）点から座標（15、６）点へ向
う方向コード「２」座標（15、６）点の座標（15、６）微少ルー
プ追跡部５からの割り込みを受け付けると、線
縁追跡部４は、微少ループ追跡部５内のフラツ
グレジスタの内容を調べる。

フラツグレジスタの内容は「１」であるの
で、線縁追跡部４は、微少ループ追跡部５内の
内部レジスタに格納されている。微少ループの
線縁特徴をバツフアメモリ３に格納し、座標
（15、６）点から再び輪郭線縁の追跡を行う。

次に、輪郭線縁の追跡が進行し、黒ビツトP₄
まで至つたとする。

座標（９、14）点から、黒ビツトP₄へ向う方
向コードV₃は「１」であるので、線縁追跡部４
は、黒ビツトP₄を中心として、時計廻りに「７」
の方向から隣接ビツトの論理レベルを調べてい
く。

座標（10、12）点が黒ビツトであるので、線縁
追跡部４は、座標（10、12）点の座標と黒ビツト
P₄から座標（10、12）点へ向う方向コードを線
縁追跡部４内の内部レジスタに格納する。

続いて、線縁追跡部４は、座標（11、12）点、
座標（11、13）点、座標（11、14）点と論理レベ
ルを調べる。

座標（11、12）点、座標（11、13）点は白ビツ
トであり、座標（11、14）点は黒ビツトであるの
で、線縁追跡部４は、座標（11、12）点、座標
（11、13）点が微少ループとなり得るものと判断
し、黒ビツトP₄の座標を微少ループ追跡部５に
与え、微少ループ追跡部５に対して割り込みをか
ける。

微少ループ追跡部５は、割り込みを受けつける
と、黒ビツトP₄のＸ座標をSPXレジスタに、Ｙ
座標をSPYレジスタに格納し、更に、CTカウン
タをクリヤする。

従つて、この時点でSPXレジスタには「10」
がSPYレジスタには「13」が、CTカウンタには
「０」がセツトされている。微少ループ追跡部５
は、CTカウンタをカウントアツプしながら、座
標（11、14）点、座標（12、13）点、座標（12、
12）点、座標（12、11）点、座標（12、10）点、
座標（12、９）点、座標（12、８）点、座標
（12、７）点と追跡していく。

座標（12、７）点まで、追跡した時点でCTカ
ウンタの内容は「８」になるので、微少ループ追
跡部５は、フラツグレジスタを「０」にセツト
し、線縁追跡部４に割り込みをかける。

微少ループ追跡部５からの割り込みを受けつけ
ると、線縁追跡部４は、フラツグレジスタの内容
を調べる。

フラツグレジスタの内容は「０」であるので、
線縁追跡部４は、先に線縁追跡部４内の内部レジ
スタに格納した、座標（10、12）点の座標と黒ビ
ツトP₄から座標（10、12）点に向う方向コード
「０」をバツフアメモリ３に格納し、座標（10、
12）点から再び輪郭線縁の追跡を開始する。

輪郭線縁の追跡が進んで黒ビツトP₅に至つた
とする。

座標（12、８）点から黒ビツトP₅に向う方向
コードV₄は「０」であるので、線縁追跡部４は、
黒ビツトP₅を中心として時計廻りに「６」の方
向から隣接ビツトの論理レベルを調べていく。

座標（12、６）点が黒ビツトであるので、線縁
追跡部４は、座標（12、６）点の座標と黒ビツト
P₅から座標（12、６）点へ向う方向コードを線
縁追跡部４内の内部レジスタに格納する。

続いて、線縁追跡部４は、座標（13、６）点、
座標（14、６）点と論理レベルを調べていく。

座標（13、６）点は白ビツトであり、座標
（14、６）点は黒ビツトであるので、線縁追跡部
４は、座標（13、６）点が微少ループとなり得る
ものと判断し、黒ビツトP₅の座標を微少ループ
追跡部５に与え、微少ループ追跡部５に対して割
り込みをかける。

微少ループ追跡部５は、割り込みを受けつける
と、黒ビツトP₅のＸ座標をSPXレジスタにＹ座
標をSPYレジスタに格納し、更に、CTカウンタ
をクリヤする。

従つて、この時点で、SPXレジスタには「12」
が、SPYレジスタには「７」が、CTカウンタ
「０」がセツトされている。

微少ループ追跡部５は、CTカウンタをカウン
トアツプしながら、座標（13、７）点から輪郭線
縁の追跡を開始していく。

ところが、座標（13、７）点は、既に、線縁追
跡をされているので、論理レベルが「−１」とな
つている。

そこで、微少ループ追跡部５は、フラツグレジ
スタを「０」にセツトし、線縁追跡部４に割り込
みをかける。

微少ループ追跡部からの割り込みを受けつける
と、線縁追跡部４は、フラツグレジスタの内容を
調べる。

フラツグレジスタの内容は「０」であるので線
縁追跡部４は、先に線縁追跡部４内の内部レジス
タに格納した、座標（12、６）点の座標と黒ビツ
トP₅から座標（12、６）点に向う方向コード
「０」をバツフアメモリ３に格納し、座標（12、
６）点から再び輪郭線縁の追跡を開始する。

以上、説明した様に、本発明によれば、微少ル
ープを廻り込む様にして、輪郭線縁の追跡を行な
うことができるので、本発明に係る特徴抽出装置
を用いれば、ループ数や線縁特徴等の基本特徴を
誤まることがなくなる。

尚、上記においては、線縁追跡部４の他に、微
少ループ追跡部５を別途設ける場合につき途べた
が線縁追跡部４に、第９図に示すプログラムを用
意すれば微少ループ追跡部５を別途設けなくと
も、本発明は、実現し得るものである。

又、上記においては、線縁追跡部４と微少ルー
プ追跡部５の間で割り込み、信号をやりとりする
ものとして説明したが、相互にステータスを監視
する様になしてもよい。

又、上記においては、CTカウンタのカウント
値が８以内の場合を、微少ループとしたが、この
値はOCRの分解能によつて変化するものである。

【図面の簡単な説明】

第１図は従来の特徴抽出装置のブロツク図。第
２図はパターンメモリの内容を視覚的に表わした
図。第３図は方向コードの説明図。第４図は微少
ループの発生箇所の説明図。第５図は第４図のパ
ターンを拡大した図。第６図は従来の特徴抽出装
置により、第５図のパターンを線縁追跡する場合
の方向を示す図。第７図は本発明による特徴抽出
装置により、第５図のパターンを線縁追跡する場
合の方向を示す図。第８図は本発明の一実施に係
る特徴抽出装置のブロツク図。第９図は微少ルー
プの線縁追跡手順を示すフローチヤート。第１０
図はパターンメモリの内容を示す図。１……パターンメモリ、２，４……線縁追跡
部、３……バツフアメモリ。

Claims

【特許請求の範囲】１パターンデータを保持するパターンメモリ
と、該パターンメモリに保持されたパターンの輪
郭線縁を構成する各ビツト毎に、隣接するビツト
の論理レベルを判定して、パターンの輪郭線縁を
追跡する線縁追跡部とを具備する特徴抽出装置に
おいて、パターンの輪郭線縁を追跡する過程でパターン
を構成するビツトが、その周囲に微少ループのあ
り得る条件を持つているかを検出する第１の手段
と、この第１の手段がパターンを構成するビツトが
その周囲に、微少ループのあり得る条件を持つて
いることを検出すると、そのビツトの輪郭線縁を
追跡し、そのビツトの周囲における微少ループの
有無を検出する第２の手段とを具備する特徴抽出
装置。