JPH057751B2 - - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、文字や図形などの二次元パターンの
認識を行うための輪郭追跡方法に関する。

（従来技術） 従来、この種の方法にはフライングスポツトス
キヤナを使用して紙面上に書かれた文字や図形の
輪郭を追跡する方式が採用されていた。この方式
を用いて装置を構成した場合には、高価格で大形
のフライングスポツトスキヤナを利用するため、
装置が高価格で大形化していた。

また、２値図形の輪郭を追跡する方式も従来か
ら提案されているが、従来の方式では１画素より
成る線幅であるためにループ図形の内側の輪郭を
追跡できなかつたり、あるいは図形そのものでは
なく輪郭線に注目していたために３画素分の輪郭
線を追跡するのに４画素分の記憶エレメントに拡
大して追跡するという複雑で時間のかかる追跡方
法を採用しなければならなつた。

一方、上記において文字や図形に含まれる内部
のループ部の検出や複数のブロツクから成る図形
の検出は、輪郭の追跡とは異なる手段により行う
必要があつた。

なお、ここでいうブロツクは有意画素で外側輪
郭部が形成され周囲から独立しているものすべて
を含み、ループはその中で閉じた内側輪郭のある
ループ状のものをいう（以下同様とする）。

次に、これらの問題点を図面に参照して詳細に
説明する。

従来技術による形状追跡方法を第１図〜第５図
により説明する。

第１図は線幅が１画素の２値化されたループの
図形の二次元パターンの実例であり、第１図にお
いて論理“１”は図形部、論理“０”は背景部を
表わす。したがつて、この場合“１”は有意画素
に“０”は無意画素に対応する。

第２図は第１図と等価な追跡すべき輪郭線を表
しており、第２図における“ａ”は外側の輪郭線
を表わし、“ｂ”は内側の輪郭線を表わし、斜線
部は図形部を表わしている。第１図は線幅が１画
素であるようなループ図形を表わしているので、
論理“１”の画素のうちのほとんどのものは外側
の輪郭点と内側の輪郭点とを兼ねている。

第３図は、第１図の図形を記憶した記憶装置の
状態を示し、記憶エレメントには第１図の各画素
に対応して“１”または“０”の値が記憶されて
いる。したがつて、第３図は第２図において示さ
れた輪郭が記憶されている。また、この記憶装置
にはサイズｍ×ｎの二次元パターンに対して（ｍ
＋２）×（ｎ＋２）個の画素が備えてある。第３図
において“ｃ”は外側輪郭における最初の追跡点
（始点）を示す記号であり、“ｄ”は第２番目の追
跡点を示す記号である。

第４図は、第２図における外側の輪郭を追跡し
た後の記憶装置の状態を示し、追跡完了時の各輪
郭点に対応する記憶エレメントの内容は“１”か
ら“２”に置換されている。

第５図は、追跡中の輪郭点から次の輪郭点を探
す順序の一例を示す図である。第５図において、
＊は追跡中の輪郭点の位置である。直前に追跡し
た輪郭点が番号８の位置にあると仮定した時、番
号１〜７は番号８を基準にして反時計方向に付け
られている。そこで、番号１〜８の順に各画素に
対応する記憶エレメントの値を調べる。

輪郭追跡は次のように行われる。

まず、追跡の始点を探すため、第３図に示す記
憶装置の状態において、第１図の左上隅の画素に
対応する記憶エレメントから順次、右に向かつて
次々に各画素に対応する記憶エレメントの値を調
べてゆき、記憶エレメントの内容が最初に“０”
から“１”に変化する位置の画素を始点（第３図
ｃ点）として、第５図に示すような番号の順序に
従つて記憶エレメントの内容が“０”ではない点
を捜し、その記憶エレメントの画素に追跡点を移
すと共に、追跡済みの画素に対応する記憶エレメ
ントの内容を“１”から“２”に置換する。これ
を繰り返して追跡点が始点に戻れば追跡は終了す
る。

次に、外側の輪郭を追跡した後の第４図の記憶
装置の状態に対応して、第２図における“ｂ”に
従つて内側の輪郭追跡を開始する。しかし、この
場合には、記憶エレメントの内容が“０”から
“１”に変化する点が検出されず、内側の輪郭追
跡は不可能である。

このように、従来の輪郭追跡方法では第１図に
示すような、線幅が１画素のループ図形におい
て、内側の輪郭を追跡できないという欠点があつ
た。

さらに、従来技術による輪郭追跡では、輪郭を
追跡することのみを目的としていたので、図形ま
たは文字の形状を追跡する場合には、一つの輪郭
の追跡結果を図形または文字の内部に含まれたル
ープ部の輪郭追跡に利用できず、改めて別の手段
によつてループ部の有無を検出しなければならな
いという欠点があつた。

（発明の目的） 本発明の目的は、追跡した輪郭点に図形または
文字を表わす数値を付加し、前記数値を付された
図形または文字の形状に無関係に、輪郭追跡とは
別に、対象とする二次元全領域の順次走査を実施
することによつて上記欠点を除去し、輪郭点の位
置情報ばかりでなく、図形または文字を表わす数
値が付与された部分と未だ追跡されていない図形
または文字のパターンとの位置関係により、この
領域の内部で図形または文字を構成する未追跡の
独立線素を成すブロツクの有無、および既に追跡
が終了した図形または文字の内部に存在するルー
プ部が有無を検出することができるようにした形
状追跡方法を提供することにある。

（発明の構成） 本発明による形状追跡方法は複数のプロセスか
ら成り立つものである。

第１のプロセスは、一定の二次元領域内に存在
し、第１の数値を有する有意画素により構成され
る二次元図形、または文字の輪郭を追跡する形状
追跡方法において、前記二次元領域全域を、画素
の数値の変化を検出しつつ第１の方向に走査する
ものである。

第２のプロセスは、前記第１のプロセスで検出
した前記画素の数値の変化が、無意画素から前記
第１の数値を有する有意画素、または無意画素か
ら（前記第１の数値＋第２の数値）の数値を有す
る有意画素への変化である場合に、この変化した
画素を輪郭点の始点とするものである。

第３のプロセスは、前記第２のプロセスで輪郭
点の始点とした画素の周囲の画素を、定められた
第１の回転方向に沿つて、前記第２のプロセスに
おいて前記輪郭点の始点の直前に走査した画素か
ら、有意画素を発見するまで順次調査し、この調
査の過程で、この調査の中心となる中心輪郭点の
前記第１の方向の反対側で無意画素を発見した場
合はこの中心輪郭点の画素の値に前記第２の数値
を加えてこの中心輪郭点の画素の値を変更し、ま
たこの中心輪郭点の前記第１の方向側で無意画素
を発見した場合はこの中心輪郭点の画素の値に第
３の値（≠第２の数値、かつ≠第１の数値＋第２
の数値）を加えてこの中心輪郭点の画素の値を変
更する値変更を行ない、前記有意画素が発見され
ると、その有意画素を新たな輪郭点とするもので
ある。

第４のプロセスは、前記第３のプロセスで発見
された新たな輪郭点の周囲の画素を、前記第１の
回転方向に沿つて、直前に追跡された輪郭点の次
の画素から、前記値変更を行ないながら、有意画
素を発見するまで順次調査し、有意画素が発見さ
れると、その有意画素を新たな輪郭点として、同
様にこの新たな輪郭点についても周囲の調査を行
ない、次々と輪郭点の追跡を前記輪郭点の始点を
発見するまで行なう輪郭追跡プロセスである。

第５のプロセスはこの輪郭追跡プロセスにおい
て、前記輪郭点の始点が発見された場合に前記第
１のプロセスに戻り、前記走査を再開するための
ものである。

（実施例） 次に、本発明について図面を参照して詳細に説
明する。

第６図は、第３図に示す外側輪郭の追跡に対応
し、本発明によつて外側輪郭を追跡した後の記憶
エレメントの状態を示す図である。第６図におい
て、“ｅ”は外側輪郭追跡の始点を示す記号であ
る。第７図は、第６図において本発明によつて内
側輪郭を追跡した後の記憶エレメントの状態を示
す図である。第７図において、“ｈ”は内側輪郭
の追跡の始点を示す記号である。第８図および第
９図は、本発明により追跡を実行する順序、追跡
点との関係位置を示す記号、およびその記号に対
応した値を示す図である。第８図においてａは追
跡の順序、ｂはその追跡中の画素の周辺の画素
に、以下の説明のために仮につけた記号を示し、
第９図はその記号に対応した位置の画素に対応す
る記憶エレメントの値が“０”の場合に、その時
点で追跡中の画素（図中＊印にある画素）に既に
付加されている数値を加算されるべき数値を示し
たものである。第１０図は、本発明による追跡の
概略を示すフローチヤートの一例である。

本発明に使用するプロセスには第１から第５ま
でのプロセスがある。

第１および第２のプロセスでは、二次元の一定
領域内（例えば第３図に示す）を全面走査して二
次元図形または文字の輪郭（外側輪郭線または内
側輪郭線）の始点を検出することができる。

第１および第２のプロセスは形状追跡の始点を
捜す動作である。この動作は、いわゆるラスタス
キヤン方式等で記憶エレメントの値を順に調べて
ゆき、値が“０”から“１”または“０”から
“５”（従来技術では“０”から“１”）に変化し
たところで、この“１”の画素を始点とする動作
である（第１０図ステツプS₁およびS₂参照）。

第３、第４および第５のプロセスは第１および
第２のプロセスにより発見された始点から輪郭を
追跡する動作である。すなわち追跡点（追跡中の
画素）の周囲の画素の値を定められた方向で順に
調べ、最初に発見された“１”以上（従来技術で
は“１”）の画素に追跡点を移動するようにして
次々と画素上を移動し、輪郭を追跡する動作であ
る（第１０図ステツプS₃参照）。そして始点に戻
つた時点で動作を終了する（第１０図ステツプS₄
参照）。輪郭点の周囲の画素の捜索は、直前の輪
郭点の画素を最後に調べるように、直前の輪郭点
の画素の隣の画素から始める。

第８図ａは追跡中の輪郭点から次の輪郭点を捜
す順序の一例を示している。第８図ａにおける＊
は追跡中の輪郭点の位置であり、直前に追跡した
輪郭点を番号８としたものである。例えば、図示
したように左上の位置が番号８であり、番号１〜
７は番号８を基準として反時計方向に付けられて
いる。番号１〜８の順に各画素に対する記憶エレ
メントの値を調べる。

この第３、第４および第５のプロセスにおいて
従来技術と異なる点が２つある。

その１つは、始点における輪郭点の探索であ
る。始点の場合は前述の直前の輪郭点がないた
め、周囲のどの画素から始めるかを予め定める必
要がある。従来技術では第５図に示す順序である
が、本実施例では第８図ａの順序である。

他の１つの相違点は、記憶エレメントの値（有
意画素に付与される数値）である。従来技術では
追跡点の移動後に画素の値（前記数値）を“１”
から“２”に更新するが、本実施例では、この値
の更新に特徴がある。

第９図は、第８図中＊における追跡中の各点に
対応して該当する画素の記憶エレメントの値が
“０”である時に、追跡中の画素に対応する記憶
エレメントの値に加算されるべき値を示した図で
ある。

すなわち前述の第２の動作で追跡点の周囲の画
素の捜索時に、捜索対象画素が“０”であつた場
合に第９図に示す値を追跡点の画素に加えるよう
に動作する。したがつて捜索対象画素が追跡点の
左であり、これが“０”であつた場合は、追跡点
（図中＊印）の画素に“２”が加えられる。しか
し仮に追跡点の右が“０”であつたとしてもこれ
が捜索対象となる前に追跡点が移動することによ
つて捜索対象画像でなくなれば“４”は加算され
ない。

第６図は、第２図における“ａ”に対し外側輪
郭を追跡した後の記憶装置の状態を示している。
すなわち、１画素左の画素に対応する記憶エレメ
ントの値が“０”であるならば、追跡完了時は追
跡中の画素に対応する記憶エレメントの値“１”
に“２”が加算されて“３”に置換され、１画素
右の画素に対応する記憶エレメントの値が“０”
であるならば、追跡中の画素に対応する記憶エレ
メントの値は“４”が該当する値“１”に加算さ
れて“５”に置換されている。

第７図において、“ｈ”を含む列は第６図の記
憶装置の状態に対応して第２図における“ｂ”を
表わし、内側の輪郭を追跡した後の記憶装置の状
態を示す。したがつて、１画素左の画素に対応す
る記憶エレメントの値が“０”であるならば、追
跡時の記憶エレメントの値は追跡中の画素に対応
する記憶エレメントの値に“２”が加算されて
“７”に置換され、１画素右の画素に対応する記
憶エレメントの値が“０”であるならば、追跡中
の画素に対応する記憶エレメントの値には“５”
に“２”が加算されて“７”に置換される。

これらの状況を第８図ｂの追跡中の輪郭点（＊
印）とその周辺の探索点の関係位置を示す記号Ａ
〜Ｈを使つてさらに詳しく説明する。

第３図において、始点に続く輪郭点を検出する
には、第８図ａの順序に従つて始点を中心に反時
計方向に調べてゆき、最初に“１”が存在してい
る点を見出し、これを輪郭点として位置情報を座
標より抽出する。この“１”が検出されるまで、
第８図ｂの各記号に対応した第９図に示す値を、
追跡点の画素に対応する記憶エレメントの値に順
次に加算してゆく。次の輪郭点が検出されたなら
ば、その輪郭点の画素を次の追跡点として第８図
ａのような順序で調べてゆく。ここで始点以降の
追跡点については、直前の追跡点の番号に続く次
の位置から調べ始める。

例えば、第３図のパターンでは始点（第３図
ｃ）からみて直前の輪郭点が記号Ｈの位置にある
ものとして記号Ａの位置から調査を始める。第２
番目の追跡点（第３図ｄ）は、始点からみて記号
Ｂの位置にある。ここで、記号Ａの位置の画素に
対応する記憶エレメントの値は“０”であるか
ら、加算基準に従つて記号Ａに対応する値、すな
わち“２”を加算し、始点に対応した画素での記
憶エレメントの値は“３”となる。次に、第２番
目の追跡点からみて始点は記号Ｆの位置にあるた
め、記号Ｇの位置から反時計方向に調べ始める。
順次調べると、第３番目の追跡点は第２番目の追
跡点からみて記号Ｄの位置にあるため、第２番目
の追跡点に対応する記憶エレメントの値は記号Ｇ
に対応する値“０”と、記号Ｈに対応する値
“０”と、記号Ａに対応する値“２”と、記号Ｂ
に対応する値“Ｃ”と、記号Ｃに対応する値
“０”とが加算されたものとなり、結果は“３”
となる。次に、第３番目の追跡点からみて第２番
目の追跡点は記号Ｈの位置にあるため、記号Ａの
位値から反時計方向に調べ始める。このようにし
て追跡を繰り返して実行し、追跡点が始点に戻つ
た時点で記号Ｈに対応する値が加算された場合に
は、追跡は終了する。ここで、ブロツクが一つ検
出されたことになつて再び走査が開始される。こ
のとき、“０”から“１”への変化点を検出した
ならば、他に独立したブロツクが存在することに
なる。この実施例では、１ブロツクに１ループが
対応した図形を取り扱つているので、次は内側輪
郭の追跡を行う。

内側輪郭の追跡は外側輪郭の追跡と同様に行わ
れる。なお、前記の他に独立したブロツクについ
てはその動作の主要部分は前記の動作同様である
ので説明は省略する。

ここで、外側の輪郭を追跡した後の第６図の記
憶装置の状態において、内側の輪郭の追跡を行う
ことになる。今度は、外側の輪郭終了点から右へ
向かつて内側の輪郭追跡の始点を検出するため、
順次画素に対応する記憶エレメントの値を調べて
ゆく。ここで、“０”から“１”、あるいは“０”
から“５”に変化する点があれば、この点を内側
輪郭追跡の始点とする。

第６図の場合は“０”から“５”に変化する点
ｇがこれに該当する。

内側のループ部の輪郭の追跡は、外側の輪郭部
の追跡と同様の方法によつて行う。第８図におい
て記号Ｈに対応する画素の記憶エレメントの値か
ら順次、第８図に示す順序に従つて反時計方向に
調べ始め、画素の記憶エレメントが“０”以外の
値を有する点が見つかるまで“０”の記号に対応
する画素の記憶エレメントの値を加算してゆく。
第６図において、始点からみて第２番目の追跡点
は記号Ｂの位置にある。したがつて、始点の画素
に対応した記憶エレメントの値はすでに外側輪郭
の追跡の結果として置換された値、すなわち、
“５”に対して記号Ａに対応する値、すなわち
“２”を加算して得られた値となり、結果的に
“７”となる。第２番目の追跡点からみて始点は
記号Ｆの値にあるため、記号Ｇの位置から始めて
その画素に対応する記憶エレメントの値を調べ
る。第３番目の追跡点は記号Ａの位置にあるた
め、記号Ｇに対応する値、すなわち“０”と、記
号Ｈに対応する値、すなわち“０”とを記号Ａに
対応する値に加算して“５”となる。第２番目の
追跡点は、第３番目の追跡点からみて記号Ｅの位
置にある。したがつて、記号Ｆの位置からその画
素に対応する記憶エレメントの値を調べ始める。
このようにして、追跡を繰り返して実行し、追跡
点が始点に戻つた時点で記号Ｈに対応する画素の
記憶エレメントの値が加算されたならば、追跡は
終了する。

なお、本発明では、前述の動作により置換され
た画素の値でその画素が図形上でどのような部分
を形成しているかを判断することができる。その
代表的なものがループの検出である。（第１０図
のステツプS₁およびS₂参照）。

これは前述と同様の全面走査“３”から“１”
または“１”から“０”への変化点を捜すことで
検出することができる。

例えば外側輪郭の追跡が終わつた後の二次元全
面走査において、第３図の“ｄ”に対応する第６
図の“ｆ”の位置の記憶エレメントは“３”の数
値が付与されておりその右が“０”であるので左
から右への走査によつて“３”から“０”の変化
を検出し、第３図の“ｄ”を含む図形がループ状
であることが分かる。ここでもし、この図形の一
部に途切れた個所があつてループ状となつていな
い場合は、第８図、第９図に示されるルールに従
つて輪郭を追跡すればループの切れた端部から輪
郭に沿つて始点の方向に戻ることになり、この戻
る過程で第６図の“ｆ”の位置に付与されている
数値“３”に、第９図に示す“４”が加算され
て、“ｆ”の位置での左から右への走査によつて
は“３”から“０”とはならず“７”から“０”
となり、ループとして検出されなくなる。他の画
素についても同様であるので、このように各有意
画素に付与された数値を走査して調べることによ
り、ループ部の検出（第１０図のステツプS₅参
照）やブロツクの数（第１０図のステツプS₂に関
連して出力可能）を知ることができる。

そこで第３図（第６図）の場合は、ループ数は
１となる。なお、この追跡方法では、ｍ×ｎ画素
の二次元パターンに対して（ｍ＋２）×（ｎ＋２）
の記憶エレメントがあり、座標（ｉ、ｊ）（ｉ＝
１、２、……ｍ＋２：ｊ＝１、２、……ｎ＋２）
の記憶番地に対して座標（１、ｊ）、（ｉ、１）、
（ｍ＋２、ｊ）、（ｉ、ｎ＋２）に対応する記憶エ
レメントはすべて“０”とする。すなわち、ｍ×
ｎの二次元パターンのまわりの１画素はすべて論
理“０”とする。また、追跡点を中心に８連結の
３×３画素において反時計方向に調べ、始点にお
いて記号Ａの位置から調べたならば終了点におい
て必ず記号Ｈの位置まで調べる。

（発明の効果） 以上説明したように本発明においては、追跡し
た輪郭点に図形または文字を表わす数値を付加
し、図形または文字の形状に無関係な輪郭追跡と
は異なる二次元領域の順次走査を実施することに
より、複雑な図形、あるいは１画素の線幅のルー
プ図形に対して外側輪郭はもとより、内側輪郭も
含めて簡単な動作で追跡することができるという
効果がある。

さらに、輪郭点の位置情報だけではなくループ
の検出、およびブロツクの検出のような認識分野
における特徴抽出にも利用できるので、簡単な装
置で輪郭の追跡を完全に、すばやく行うことがで
きる安価な形状追跡方法を形成できるという効果
もある。

上記においてブロツクの検出は文字や図形のブ
ロツク数を調べることであり、ブロツク数は外側
輪郭の数に等しい。

【図面の簡単な説明】

第１図は１画素の線幅を有するループ図形図で
あり、文字や図形などの２値化された二次元パタ
ーンの実例を示す図である。第２図は第１図にお
いて追跡すべき輪郭線を示す図である。第３図は
数値に置換して書込まれた記憶エレメントの状態
を示す図である。第４図は従来技術による外側輪
郭追跡終了後の記憶エレメントの状態を示す図で
ある。第５図は従来技術による追跡先探索の順序
を示す図である。第６図は本発明により外側輪郭
を追跡した後の記憶エレメントの状態を示す図で
ある。第７図は本発明により内側輪郭を追跡した
後の記憶エレメントの状態を示す図である。第８
図ならびに第９図は本発明による追跡先探索の順
序、関係位置の記号、および記号の対応値を示す
図である。第１０図は本発明による追跡の流れの
一例を示すフローチヤートである。 ａ，ｂ……輪郭線。

Claims (1)

1. 【特許請求の範囲】 １ 一定の二次元領域内に存在し、第１の数値を
   有する有意画素により構成される二次元図形、ま
   たは文字の輪郭を追跡する形状追跡方法におい
   て、 前記二次元領域全域を、画素の数値の変化を検
   出しつつ第１の方向に走査する第１のプロセス
   と、 前記第１のプロセスで検出した前記画素の数値
   の変化が、無意画素から前記第１の数値を有する
   有意画素、または無意画素から（前記第１の数値
   ＋第２の数値）の数値を有する有意画素への変化
   である場合に、この変化した画素を輪郭点の始点
   とする第２のプロセスと、 前記第２のプロセスで前記輪郭点の始点とした
   画素の周囲の画素を、定められた第１の回転方向
   に沿つて、前記第２のプロセスにおいて前記輪郭
   点の始点である画素の直前に走査した画素から、
   有意画素を発見するまで順次調査し、この調査の
   過程で、この調査の中心となる中心輪郭点の前記
   第１の方向の反対側で無意画素を発見した場合は
   この中心輪郭点の画素の値に前記第２の数値を加
   えてこの中心輪郭点の画素の値を変更し、またこ
   の中心輪郭点の前記第１の方向側で無意画素を発
   見した場合はこの中心輪郭点の画素の値に第３の
   値（≠第２の数値、かつ≠第１の数値＋第２の数
   値）を加えてこ中心輪郭点の画素の値を変更する
   値変更を行ない、前記有意画素が発見されると、
   その有意画素を新たな輪郭点とする第３のプロセ
   スと、 前記第３のプロセスで発見された新たな輪郭点
   の周囲の画素を、前記第１の回転方向に沿つて、
   直前に追跡された輪郭点の次の画素から、前記値
   変更を行ないながら、有意画素を発見するまで順
   次調査し、有意画素が発見されると、その有意画
   素を新たな輪郭点として、同様にこの新たな輪郭
   点についても周囲の調査を行ない、次々と輪郭点
   の追跡を前記輪郭点の始点を発見するまで行なう
   輪郭追跡プロセスである第４のプロセスと、 前記輪郭追跡プロセスにおいて、前記輪郭点の
   始点が発見された場合に前記第１のプロセスに戻
   り、前記走査を再開する第５のプロセスとを有す
   ることを特徴とする形状追跡方法。