JPH02238579A - パターン抽出認識装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業」二の利用分野 本発明は図形画像中からパタ ンを抽出認識す 従来の技術 従来のパターン抽出認識装置は第５図に示す構成を持ち
、入力千段１にょり入カした図形画像に対して、前処理
手段２でノイズ除去や細線化処理を施１，、入力図を入
力要素である線分ベクタ等を用いた表現に変換し、パタ
ーン分離手段３において、大まかな図形的特徴、例えば
、閉ループや短セグメント等を手掛りに抽出すべきパタ
ーンが含まれると予測される候補領域の抽出処理を施し
た後、パターン類別千段４でその領域の詳細な図形的特
徴量分析によりパターンの類別を行い、出カ手段５にお
いてそのベターンの抽出認Ｒ結果を出力してい／ユ３， 発明か解決１〜ようとする課題 しかし２、従来のバクーン抽出認識装置では地図などに
兄１’．＞ｔｌる」こウか複雑に各種要素が描かれ、線
分が複雑に入り組んでいる図形からパターン分離千段３
において、バターノが含まれると予想されろ領域を正＋
−＜う』ｆずることが困難なだめ、パ３　・・−７ ターン抽出認識装置全体として正しくパターンを抽出認
識することが困難であった。本発明は、特に地図など複
雑に各種要素が描かれ、線分が複雑に入り組んでいる図
形に対しても確実にパターン抽出認識処理を可能とする
ことを目的としている。

課題を解決するだめの手段 上記課題を解決するために本発明のパターン抽出認識装
置は、入力された図形画像を図形の基本構成要素である
入力要素を用いたデータに変換する手段と、変換された
入力要素のデータを保持する入力要素記憶手段と、抽出
認識すべきパターンの構成要素である規範パターン要素
に関するデータを保持する規範パターン記憶手段７、入
力要素記憶手段中の入力要素と規範パターン記憶手段中
の規範パターン要素と処理履歴データとを用いて規範パ
ターン記憶手段中の規範パターン要素と入力要素記憶手
段６中の入力要素を対応付けするマソチング手段９、マ
ソチング手段において行ったマッチング処理の履歴デー
タを保持する履歴保持手段とを具備するものである。

作用 本発明によるパターン抽出認識装置では以下の処理が可
能となる。すなわち、本装置ではパターンが存在すると
予想される領域を分離抽出する処理を行わず、入力要素
記憶手段に記憶された入力要素に対して、規範パターン
記憶手段に記憶された規範パターン要素との対応付け処
理をマッチング手段により行う。マッチング手段におい
ては、順次行われる各規範パターン要素に対する入カ要
素との対応付け処理で、規範パターン要素に対応付け可
能な入力要素候補の中から一要素を対応付け要素として
仮定すると共に、このマッチング処理の状態を履歴とし
て履歴保持手段に記録する。

もし、以後の対応付け処理が失敗した場合には、最新の
対応付けの仮定を却下すると共に、マッチング手段の内
部状態を履歴保持手段から呼び戻す後戻り処理を行い、
別の入力要素を対応付ける。

その後、この仮定の下、まだ対応付けられていない規範
パターン要素の対応付け処理を継続する。

以上述べたように、本発明によるパターン抽出認５７、
−７ 識装置では、誤って、抽出すべきパターンと交錯してい
る他の要素と規範パターン要素をマッチングさせてしま
っても、履歴保持手段によりマッチング処理の履歴を保
持しているため、正しい対応付け処理に後戻りすること
が可能であり、他の要素と交錯するパターンをも誤りな
く抽出認識できる。

実施例 以下本発明の実施例について、図面とともに詳細に説明
する。

第１図は本発明によるパターン抽出認識装置の実施例に
おける全体構成を示すブロノク図である。

同図において１はスキャナ等の入力手段、２ｒ／′ｉ入
力手段１より入力された入力図形に対してノイズ処理や
細線化処理を施し、図形の基本構成要素である入力要素
を用いた表現のデータに変換する前処理手段である。こ
こで、基本構成要素である入力要素としては例えば点要
素および線要素で表わした線分ベクタが使用される。６
は前処理手段で得られた入力要素データを記憶する入力
要素記憶６　・・−ノ 手段、７は抽出認識すべきパターンの構成要素である規
範パターン要素に関するデータを予め保持する規範パタ
ーン記憶手段である。規範パターン要素も点要素と線要
素で表わした線分ベクタの形で表現されている。９はマ
ソチング手段で、入力要素記憶千段６に記憶されている
入力要素データと規範パターン記憶手段７に保持されて
いるデータとを対応付けする。８はマッチング手段９に
おいて行ったマッチング処理の履歴データを保持する履
歴保持手段、５はマッチング千段９の対応付け結果を出
力表示する出力手段である。

次に具体的な入力図形をもとに動作を説明する。

入力図形として地図を使用し、入力されたパターンを第
２図に示すような地図中に現われる橋の記号の部分を例
に考える。第２図においては、入力要素１０から入力要
素１９で構成された橋と、入力要素２０から入力要素２
３で構成された川及び入力要素２４かも入力要素２７で
構成された道路が交錯している部分が描かれている地図
の一部が示されている。

まず、第３図に示した規範パターン要素２８から７　　
、−， 規範パターン要素３３で構成された抽出認識すべき橋の
規範パターンを入力千段１で読みとり、前処理千段２で
前処理し、入力要素としての線分ベクタに変換して規範
パターン記憶手段７に格納する規範バクーンの記憶は、
マッチング手段９で行う対応付け処理の順序で行われ、
本実施例では規範パターン要素２８→規範パターン要素
２９→規範ハターン要素３０→規範ハターン要素３１→
規範パターン要素３２→規範パターン要素３３の順に記
憶される。

一方、第２図の図形画像を入力千段１により入力し、前
処理手段２によりノイズ除去及び線状部分の抽出処理を
行い、第２図に示した入力要素１０から入力要素２７ま
での各入力要素を生成する。これらの入力要素は入力要
素記憶手段６に記憶される。

マッチング千段９では規範パターン記憶千段７に記憶し
た規範パターン要素を順に読みだし、入力要素記憶千段
６に記憶した入力要素の中から、規範パターン要素と対
応付け可能な入力要素を選定し、対応伺け候補として選
び出す。対応付け処理の各段階では、複数の入力要素の
候補がある場合でも、ある一つの候補に仮定し、以後に
続く対応付け処理を行う。対応付けの候補として仮定し
た入力要素、マッチング千段９内で行われた処理内容な
履歴保持千段８に記録する。その後、まだ対応付けされ
ていない規範パターン記憶手段７中の規範パターン要素
の対応付け処理を継続する。

しかし、この以後の対応付け処理で対応付けが成功しな
かったならば、履歴保持千段８に記録した履歴データを
元に最新の対応付けを仮定した状況まで処理状態を戻す
。この後戻り処理により、前に対応付け候補として仮定
した入力要素を棄却し、別の候補に対応付けを切り替え
る。もし、別の候補がなければ、更に後戻り処理を行う
。この後戻り処理を伴った対応付け処理を、規範パター
ン記憶千段７にある規範パターン要素全てが対応付けら
れるまで行う。最後に、規範パターン記憶手段７中の規
範パターンに対応付けられた入力要素は、出力千段５を
経て、パターン抽出認識結果として出力する。

９　・・−７ 次に、全ての規範パターン要素の対応付け処理が失敗せ
ず、後戻り処理が行われなかった処理過程の例を以下に
示す。

処理ａ１ マッチング手段９において規範パターン要素２８を読み
出し、その規範パターン要素２８の線分長などの図形的
属性値をもとに、対応付け可能な入力要素の一つである
入力要素１０を入力要素記憶千段６より選択し、規範パ
ターン要素２８と入力要素１０の対応付けを仮定する。

その処理履歴を履歴保持手段８に記録する。

処理ａ２ マッチング手段９において規範パターン要素２９を読み
出し、その規範パターン要素２９の線分長などの図形的
属性値、及び規範パターン２８との対応付けを前の処理
ａ１で仮定された入力要素１０との接続関係等をもとに
、対応付け可能な入力要素列である入力要素１１、１２
及び１３を入力要素記憶千段６より選択し、規範パター
ン要素２９と入力要素１１Ｊ２及び、１３の対応伺けを
仮定する。その処理履歴１０　　＝−７ を履歴保持手段８に記録する。

処理ａ３ 処理ａ２と同様な処理によって、規範パターン要素３０
と入力要素１４の対応付けを仮定し、履歴保持手段８に
記録する。

処理ａ４一処理ａ６ 以上の処理ａ１から処理ａ３までの処理と同様な処理を
行い、規範パターン要素３１と入力要素１５を対応付け
、規範パターン要素３２と入力要素列１６１７及び１８
を対応付け、最後に、規範パターン要素３３と入力要素
１９を対応付けてそれぞれ履歴保持千段８に記憶する。

処理ａ７ 以上の処理結果として、橋として抽出認識した入力要素
１０、１１、１２、１３、１４、１５、１６、１７、１
８及び１９が、出力手段５により出力される。

次に、対応付けが失敗し、後戻り処理が行われた処理過
程の例を示す。

処理ｂ１ 処理ａ１と同じ。

１１　・・ 処理ｂ２ 処理ａ２と異なり規範パターン要素２９は、入力要素１
１及び２０と対応付けが仮定される。その処理履歴を履
歴保持千段８に記録する。

処理１〕３ 規範パターン要素３０を規範パターン記憶手段７から読
みだし、入力要素記憶手段６中から、対応付け可能な入
力要素を探索する。ここで、規範パターン要素３０は、
規範パターン要素２９と接続していることより、処理１
〕２で規範パター７要素２９と対応付けた入力要素月と
２０の先に接続していろ入力要素を探索する。しかし、
入力要素１１、２０の先には入力要素がないため、規範
パターン要素３０の対応利け処理は失敗し、後戻り処理
を行う。この後戻り処理では、履歴保持千段８から最新
の対応付け処理である、上の処理１〕２の状態を呼び出
し処理ｂ２で仮定した対応付けを解除する。

処理１〕３ 処理ｌ）２の対応付けをやり直し、規範パターン要素２
９と入力要素１１、１２おＪ：び１３を対応伺けて、履
歴保持千段８に記憶する。

処理１〕４−処理ｂ　７ 以後の処理は処理ａ４−処理ａ７と同じ処理を行う。

以上の説明から明らかなように、記号の大きさや方向が
一定でない場合や、パターンに他の線や記号が交錯１〜
でいる場合でも、各入力要素毎に試行錯誤的探索を行う
ことにより確実に抽出認識することができる。

なお、上記の実施例においては、第３図に示した規範パ
ターンと同一の入力パターンの抽出認識を行う場合につ
いて説明しだが、この規範パターンを種々変更して規範
パターン記憶千段７に記憶させろことにより入力図形か
ら任意のパターンな抽出認識することができる。

発明の効果 以上のように、本発明のパターン抽出認識装置では入力
図中の抽出認識すべきパターンが他の要素と交錯してい
る場合でも、マッチング処理の履歴を用いた後戻り処理
に」＝り、全ての対応イ」けの可能性を調べることが可
能となり、規範パターンに記述されたパターンの構造に
合致する部分を入力図中からもれなく抽出認識できる。

【図面の簡単な説明】

第１図は本発明によるパターン抽出認識装置の実施例に
おける全体構成を示すブロノク図、第２図はパターン抽
出認識装置へ入力される入力パターンの一例を示す図、
第３図は本発明のパターン抽出装置に使用される抽出認
識すべき規範パターンの一例を示す図、第４図は従来の
パターン抽出認識装置の構成を示すブロノク図である。 １・・入力手段、２・・前処理手段、５　出力手段、６
・・・入力要素記憶手段、７・規範パターン記憶手段、
８・・・履歴保持手段、９　・マッチング手段、１０〜
２７・入力パターンの入力要素、２８〜３３・規範パタ
ーンの規範パクー７要素。 第１図 代理人の氏名　弁理士　粟　野　重　孝ほが１名第３

Claims (1)

【特許請求の範囲】
1. 図形画像の入力手段と、入力手段により得られた入力図
   形画像を図形の基本構成要素を用いたデータに変換する
   前処理手段と、前処理手段により作成されたデータを保
   持する入力要素記憶手段と、抽出認識すべきパターンの
   構成要素である規範パターン要素に関するデータを保持
   する規範パターン記憶手段と、入力要素記憶手段中のデ
   ータと規範パターン記憶手段中のデータを対応付けする
   マッチング手段と、マッチング手段において行ったマッ
   チング処理の履歴データを保持する履歴保持手段と、マ
   ッチング手段において得た対応付け結果を出力する出力
   手段を具備したパターン抽出認識装置。