JPH04257084A - 線図形の識別方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は線図形の識別方法に関し
、特に重なりを持つ線図形を含む場合でも、高速かつ自
動的に線図形の識別を行うことが可能な線図形の識別方
法に関する。

【０００２】

【従来の技術】例えば、産報出版発行（１９７７年６月
１１日）の「コンピュータ画像処理」の７７〜８８頁に
記載されている如く、従来から、コンピュータによる線
図形の識別方法が用いられている。従来の一般的な線図
形の識別方法においては、線図形は線の特徴によって識
別されており、図形を構成する線の曲り具合や方向，線
と線との接触，交わり具合等が重要な特徴となっている
。ここで重要なことは、従来の線図形の識別においては
、線図形は重なりを有しないことを前提としていたこと
である。従って、この方法では、決められた枠内に描か
れたものや、他の図形との重なりを許さない厳しい制約
の上で描かれたものしか識別対象にできなかった。複数
の線図形が重なりを持つ場合、従来、それらの分節は手
作業に頼っており、これを自動化しようという試みとし
ては、本出願人が先に提案した、特願平１−５６２０号
「線図形の識別方法」が最初である。また、重なりを持
つ線図形においては、各図形は線として知覚される場合
もあれば、面として知覚される場合もある。面として重
なりを持つ場合には、ある面が他の面の輪郭線の一部を
隠蔽していると解釈される可能性があり、その場合、人
間は面の隠れた輪郭線を補って（以下、これを「補完」
という）、解釈している。 上述の補完を自動化しようという試みとしては、これも
、本出願人が先に特願平１−２２６８３４号「線図形の
識別方法」に提案した方法が最初である。

【０００３】

【発明が解決しようとする課題】上述の先願においては
、分節図形同志が線分を共有しないという条件が含まれ
ていた。しかし、観察者によって解釈が分かれるような
線図形においては、分節図形同志が線分を共有する分節
候補が、それほど不自然でない場合がある。しかし、分
節図形同志の線分の共有を認めると、一般に、分節候補
の数は非常に増加するという問題がある。そこで、本出
願人は、これに関連して、特願平１−１０３９６４号「
線図形の識別方法」において、入力線図形における線種
と、分節図形における「まとまりのある図形」を定議し
、これに基づく制約条件を導入することで、分節図形同
志が線分を共有して知覚される可能性もある重なり図形
において、非常に数多く存在する分節候補の中から、人
間にとって自然な少数の分節候補を抽出する方法を提案
している。ここで提案している方法によれば、１つの交
点に偶数本の線分が接続されている線図形においては、
上述の如く、非常に数多く存在する分節候補の中から、
人間にとって自然な少数の分節候補を抽出することが可
能であるが、この方法は、１つの交点に奇数本の線分が
接続されている線図形には、適用することができないと
いう問題があった。本発明は上記事情に鑑みてなされた
もので、その目的とするところは、従来の技術における
上述の如き問題を解消し、１つの交点に奇数本の線分が
接続されている線図形をも含む、より一般的な重なりを
持つ線図形において、非常に数多く存在する分節候補の
中から、人間にとって自然な少数の分節候補を抽出する
ことが可能な線図形の識別方法を提供することにある。

【０００４】

【課題を解決するための手段】本発明の上記目的は、与
えられた線図形に対して直線近似および円弧近似を行い
、重なりを持つ線図形を複数の部分図形（分節図形）に
分節して認識する線図形の識別方法において、前記分節
図形に対し、 （１）曲率の不連続点が３つ以下の単一閉曲線であるこ
と（２）軸対称性を持つか、回転対称性を持つ、曲率の
不連続点が６つ以下の単一閉曲線であること（３）対称
軸を２本以上持つか、第３位以上の回転対称性を持つ単
一閉曲線であること の三条件の少なくとも一つに合致する「まとまりのある
図形」を捜索し、捜索された図形のうち、下記の制約条
件（ａ），（ｂ）に適合しないものを除去した後、残り
の候補に対して、図形を構成する線分上の交点のうち、
奇数本の線分が接続されている交点（奇数交点）の数を
求め、このうちの下記の制約条件（ｃ），（ｄ）に適合
しないものを除去することにより、重なりを含む分節候
補を抽出することを特徴とする線図形の識別方法によっ
て達成される。 （ａ）分節図形の中に前記「まとまりのある図形」が存
在する場合、そうでない分節図形のみで構成される分節
候補は選択しない。 （ｂ）前記「まとまりのある図形」から成る分節図形の
みで構成可能な分節候補が存在する場合，まとまりのな
い図形を含む分節候補は選択しない。 （ｃ）外部境界線上に奇数交点がない場合は、外部境界
上で１辺以上をなす線分は共有されない。 （ｄ）外部境界線上の１つの辺にｎ個の奇数交点がある
場合、当該辺上の線分要素は（ｎ＋１）個以内の分節図
形によって共有される。

【０００５】

【作用】本発明に係る線図形の識別方法においては、与
えられた重なりを持つ線図形に対して、入力図形の各線
について、 （イ）線種１：背景との境界にならない内部境界線（ロ
）線種２：背景との境界線となる外部境界のうち、１辺
をなさないもの （ハ）線種３：外部境界のうち１辺をなすもののいずれ
か１つを定義した後、それに、前述の制約条件（ｃ），
（ｄ）を適用して条件に合致しないものを除去し、残り
の分節図形に対して前述の三条件（１）〜（３）の少な
くとも一つに合致する「まとまりのある図形」を選択し
、これについて前述の制約条件（ａ），（ｂ）を適用し
て条件に合致しないものを除去し、重なりを含む線図形
の分節候補を抽出するようにしている。すなわち、まず
、入力図形が単一図形か重なりを持つ図形かを判断した
後、重なりを持つ図形について補完を必要とするか否か
の判断を行って、補完を必要とするものについては補完
を行った後に分節候補を抽出するようにしている。

【０００６】

【実施例】以下、本発明の実施例を図面に基づいて詳細
に説明する。図４は、重なりを有する線図形およびその
解釈候補の一例を示す図である。図４（ａ）に示す如き
奇数交点を含むような重なり図形においては、前述の特
願平１−１０３９６４号「線図形の識別方法」中に示し
た条件「線種３の線分は、共有されない」を用いること
はできない。 例えば、図４（ａ）に示す如き図形を、図４（ｂ）の如
く解釈することは、人間にとって自然であるが、図４（
ｂ）においては、外部境界で１辺以上をなす線種３の線
分が共有されている。しかし、このように線種３の線分
の共有を認めると、分節候補の数が非常に増加するとい
う問題がある。そこで、上述の特願平１−１０３９６４
号中の条件「線種３の線分は、共有されない」の代りに
、別の制約条件を考慮する必要がある。分節候補を被験
者に描かせる心理実験により、以下の如き一般的な傾向
が成立するので、これを新たな制約条件として導入する
。 （ａ）外部境界線上に奇数交点がないときは、線種３の
線分は共有されない。 （ｂ）外部境界線上の１つの辺にｎ個の奇数交点がある
とき、その辺上の線種２および線種３の線分要素は、（
ｎ＋１）個以内の分節図形によって共有される。また、
対象図形がより複雑になると、上述の「まとまりのある
図形」以外の分節図形が選択される可能性がある。例え
ば、図４（ａ）に示す図形を、図４（ｃ）に示す如く解
釈することも人間にとって自然である。しかし、図４（
ｃ）に示す個々の分節図形は、上述の「まとまりのある
図形」には当てはまらない。そこで、分節候補の数がそ
れほど増加しない範囲で、「まとまりのある図形」の定
義を緩める必要がある。ここでは、「まとまりのある図
形」を、以下の（■），（■）の如く定義しなおす。 （■）曲率の不連続点が３つ以下の単一閉曲線（■）軸
対称性を持つか、回転対称性を持つ、曲率の不連続点が
６つ以下の単一閉曲線 上述の如き定義の下で、図形分節に関して以下の如き制
約条件を導入する。 （ｃ）分節図形の中に「まとまりのある図形」が存在す
る場合、そうでない分節図形のみで構成された分節候補
が選択されることはない。 （ｄ）「まとまりのある図形」から成る分節図形のみで
構成できる分節候補が存在する場合、まとまりのない図
形から成る分節図形を含む分節候補が選択されることは
ない。

【０００７】図５は、奇数交点を持つ入力線図形の例を
示す図であり、図６は本発明に係る線図形の識別方法に
より解釈候補を自動抽出した結果を示す図である。ここ
では、前述の特願平１−５６２０号「線図形の識別方法
」明細書中に示した（１）〜（６）までの条件（ここで
は、混乱防止上、（イ）〜（ヘ）の条件という）、すな
わち、（イ）分節図形の線分の単位は交点を結んだ線分
とする。 （ロ）分節図形は線分の自己重複を含まない。 （ハ）一つの分節候補において分節図形の重複は認めな
い。 （ニ）分節図形は連結図形とする。 （ホ）一つの分節候補に含まれる分節図形の線分集合は
、元の線図形のすべての線分を含む。 （ヘ）分節図形は閉図形をなす。 および、前述の特願平１−１０３９６４号「線図形の識
別方法」明細書中に示した（ｂ）の条件（ここでは、混
乱防止上、（ト）の条件という）、すなわち、 （ト）包含関係にある分節図形同志は、線種２以外の線
分を共有しない。および、上述の（ａ）〜（ｄ）の各条
件を用いて図形分節候補を自動抽出する例を、図５およ
び図６Ａおよび６Ｂ（以下、両図を合せて単に「図６」
という），図７Ａ〜７Ｄ（以下、これらの４図を合せて
単に「図７」という），図８に従って説明する。図５（
ａ）を入力図形としたときには、図６（１）〜（８）に
示す分節候補が抽出される。また、図５（ｂ）を入力図
形としたときには、図７（１）〜（２０）に示す分節候
補が抽出される。ここでは、図５（ａ）に示す入力図形
に対して、まず、上述の条件（イ）より、図８に示す如
く記述できる。図８で、１〜７は線分、■〜■が交点を
示している。次に、条件（ロ）より、１つの分節図形は
重複を含まない線分の集合として、（１，２）の如く表
わされる。次に、条件（ハ）より、１つの分節候補は重
複を含まない分節図形の集合として、｛（１，１），（
２，３，４，６），（５，７）｝の如く表わされる。次
に、条件（ニ）により、分節図形に対して（２，５）の
如き非連結図形は除去される（図９（ａ）参照）。条件
（ホ）により、｛（１，２），（２，３，４，６），（
５，６）｝の如き分節候補が除外される（図９（ｂ）参
照）。同様に　条件（ヘ）により、（３，５，７）の如
き単一閉図形でない分節図形も除去される（図９（ｃ）
参照）。

【０００８】ここまでで説明した条件適用によって、分
節図形の総数は図１０Ａおよび１０Ｂ（以下、両図を合
せて単に「図１０」という）に示す１０個になる。その
中で、本発明にいう「まとまりのある図形」の条件を満
たすものは、図１０の（１）〜（７）の７個である。こ
こで、本発明において示す　制約条件（ｂ）の前提条件
である「まとまりのある図形」の分節図形のみで構成さ
れる　分節候補が存在するという条件が成立する（例え
ば、｛（１，２），（２，３，４，６），（５，７）｝
がその例）。これにより、分節候補は、上述の７個の「
まとまりのある図形」の分節図形を用いたものに限定さ
れる。なお、制約条件（ｂ）が成立するときは、制約条
件（ａ）が成立することは明白である。 ここで、前述の特願平１−１０３９６４号「線図形の識
別方法」明細書中に示した線種について考えると、図８
において、線分１，２は線種３の線分、線分３〜７は線
種１の線分である。そこで、まず、前述の特願平１−１
０３９６４号「線図形の識別方法」明細書中に示した（
ト）の条件より、図１１に示す如き線種１の線分３，４
を包含関係にある分節図形同志が共有するような分節候
補が除去される。そして、図８において、交点■および
■は、どちらも３本の線分が接続される奇数交点である
。交点■は、外部境界の２つの辺の接続点にあり、線分
１，２がその辺を構成している。従って、本発明で示す
制約条件（ｂ）により、線分１，２は共有される可能性
がある。交点■の場合も全く同様であるから、結局、線
分１，２は２回まで共有を認められることになる。図１
０の「まとまりのある図形」について、先願の制約条件
（ト）と本発明で示す制約条件（ｂ）を考慮しながら、
分節候補を選択していくと、最終的には、図６に示つれ
る（１）〜（８）の８個の分節候補が得られる。以上は
、図５（ａ）に示す入力図形についての説明であるが、
図５（ｂ）に示す入力図形についても同様である。

【０００９】図２は、本発明の一実施例である線図形識
別装置の全体構成を示すブロック図である。図中、２１
は図面入力部であり、既存のイメージスキャナが使用可
能である。２２は線図形抽出部であり、入力画像を２値
化した後、細線化して追跡して、背景から線図形を分離
する処理を行うものである。また、２３は線図形識別部
であり、入力線図形から特徴点や線分を抽出した後、単
一図形か、重なりを持つ図形かを判断し、重なりを持つ
図形であればそれを分節する処理を行うものである。図
３は、図２中の線図形抽出部２２の具体的構成例を示す
図である。図中、３１は２値化処理部であり、入力画像
の濃淡情報を基に入力画像を２値化するものである。３
２は細線化処理部であり、２値画像を細線化する。３３
は線図形分離抽出部であり、細線化された２値画像のつ
ながりを追跡し、背景から各線図形を分離する。背景か
ら分離された各線図形は、次段の線図形識別部２３に入
力される。 図１は、本実施例に示す線図形識別装置の動作を示すフ
ローチャートである。図１中、１１は特徴点・線分抽出
部であり、入力される各線図形の特徴点（端点・屈折点
・分既点または交点等）と、線分要素およびそれらの接
続関係を抽出するものである。１２は線図形形状判断部
であり、上述の特徴点・線分抽出部１１から出力される
交点および線分から、入力線図形が単一図形が否かを判
断し、単一図形であれば、参照図形蓄積部１６に格納さ
れている参照図形データと比較し、結果を出力する。ま
た、単一図形でなければ、入力線図形は重なりを持つ図
形であると判断し、解釈可能候補抽出部１３で先に説明
した手法を用いて、特徴量を計算する。線図形形状判断
部１５では、その値を基に、入力線図形の分節候補を選
択し、その分節候補中の分節された各図形と参照図形デ
ータとを比較し、どのような図形が重なり合っているか
を結果として出力する。上記実施例によれば、重なりを
持つ線図形において、非常に数多く存在する分節候補の
中から、人間にとって自然と感じられる有限個数の候補
を抽出した後、人間が行う処理と同様の分節を行うこと
が可能になる。これにより、複数の線図形が重なりを持
つ場合にも、高速に認識することが可能になり、従来の
手作業に比べて、格段の省力化および高速化が実現でき
る。なお、上記実施例は本発明の一例を示すものであり
、本発明はこれに限定され幣べきものではないことは言
うまてもない。

【００１０】

【発明の効果】以上、詳細に説明した如く、本発明によ
れば、１つの交点に奇数本の線分が接続されている線図
形をも含む、より一般的な重なりを持つ線図形において
、非常に数多く存在する分節候補の中から、人間にとっ
て自然な少数の分節候補を抽出することが可能な線図形
の識別方法を実現できるという顕著な効果を奏するもの
である。

【００１１】

【図面の簡単な説明】

【図１】本発明の一実施例である線図形識別装置の動作
を示すフローチャートである。

【図２】実施例の線図形識別装置の全体構成を示すブロ
ック図である。

【図３】図２中の線図形抽出部２２の具体的構成例を示
す図である。

【図４】入力線図形およびその解釈候補の一例を示す図
である。

【図５】入力線図形の例を示す図である。

【図６Ａ】本発明に係る識別方法により得られた分節候
補の一部を示す図である。

【図６Ｂ】本発明に係る識別方法により得られた分節候
補の他の一部を示す図である。

【図７Ａ】本発明に係る識別方法により得られた分節候
補の一部を示す図である。

【図７Ｂ】本発明に係る識別方法により得られた分節候
補の他の一部を示す図である。

【図７Ｃ】本発明に係る識別方法により得られた分節候
補の他の一部を示す図である。

【図７Ｄ】本発明に係る識別方法により得られた分節候
補の他の一部を示す図である。

【図８】先願の制約条件の記述を示す図である。

【図９】制約条件により除去される分接図形の例を示す
図である。

【図１０Ａ】制約条件により除去される分接図形をすべ
て示す図の一部である。

【図１０Ｂ】制約条件により除去される分接図形をすべ
て示す図の他の一部である。

【図１１】制約条件により除去される分接図形の例を示
す図である。

【符号の説明】

１１：特徴点・線分抽出部、１２：線図形形状判断部、
１３：解釈可能候補抽出部、１４：重なり線図形特徴解
析部、１５：線図形形状判断部、１６：参照図形蓄積部
、２１：図面入力部、２２：線図形抽出部、２３：線図
形識別部、３１：２値化処理部、３２：細線化処理部、
３３：線図形分離抽出部。

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　与えられた線図形に対して直線近似お
   よび円弧近似を行い、重なりを持つ線図形を複数の部分
   図形（分節図形）に分節して認識する線図形の識別方法
   において、前記分節図形に対し、 （１）曲率の不連続点が３つ以下の単一閉曲線であるこ
   と（２）軸対称性を持つか、回転対称性を持つ、曲率の
   不連続点が６つ以下の単一閉曲線であること（３）対称
   軸を２本以上持つか、第３位以上の回転対称性を持つ単
   一閉曲線であること の三条件の少なくとも一つに合致する「まとまりのある
   図形」を捜索し、捜索された図形のうち、下記の制約条
   件（ａ），（ｂ）に適合しないものを除去した後、残り
   の候補に対して、図形を構成する線分上の交点のうち、
   奇数本の線分が接続されている交点（奇数交点）の数を
   求め、このうちの下記の制約条件（ｃ），（ｄ）に適合
   しないものを除去することにより、重なりを含む分節候
   補を抽出することを特徴とする線図形の識別方法。 （ａ）分節図形の中に前記「まとまりのある図形」が存
   在する場合、そうでない分節図形のみで構成される分節
   候補は選択しない。 （ｂ）前記「まとまりのある図形」から成る分節図形の
   みで構成可能な分節候補が存在する場合，まとまりのな
   い図形を含む分節候補は選択しない。 （ｃ）外部境界線上に奇数交点がない場合は、外部境界
   上で１辺以上をなす線分は共有されない。 （ｄ）外部境界線上の１つの辺にｎ個の奇数交点がある
   場合、当該辺上の線分要素は（ｎ＋１）個以内の分節図
   形によって共有される。