情報エ学教室玉木明和 　　　　　　　　加　　藤　　清　　史

同心円による線図形の特徴抽出

（il召和51−q三5 月3ユ日   蛎〔稿 受f司つ

情報エ学教室玉木明和

        加  藤  清  史

Feature Detection of Lines by Collcentric Circles

by Aakikazu TAMAKI   Kiyoshi KATO

      abstract

  Apattern is recognized by mean§of the mapping on pattern space into feature space， which is also called¶feature detection．

  In thi引eportjt is described to detect the features of lines with width by the concentric circle8 in macroscoplc rnethod・The fea亡ures are terminal point， cross point and corner point， and then a feature of curved line is not detected in this meth〔｝d、 The feature detection ls simulated with digital computer and the results are described．

1． まえかさ       2． 同心内による特徴抽出

 最近，計算機による画像処理がさかんに行われている   パターン・マトリ・ンクス上を同心円で走査して、バ が，画像そのもののもつ箭報｛iiが非常に多いため，画像   ターンと円周が交叉した数と交叉した（円の中心を基準 処理は容易ではない。文字の認識も一部のものは実用化   とした）方向をそれぞれの円周にっいて検出する。同心 されているが，機械による認識が完全に行われていると   円の数は多いほど，より広範囲な特徴が得られるが，処 はいえない。パターン認識はパターンのもつ莫大な情報   理が複推になり処理時間が長くなる。ここでは．二重同 の中から，必要な情報だけをもつ特徴を抽出し，認識を  心円を用いて線図形の特徴を抽出することとする。線図 行うのであるから，特徴抽出は必要不可欠である。パター   形の特徴は，端点，交叉点．屈曲点の特異点を対象とし、

ン・マトリ・アクス上のある図形を，位置だけを示す大き  曲線状の特徴は除外する。

さのない点とみるか，長さを示すだけの太さのない線分    血線上の同心円は図1−aのようになり、小円の交叉 とみるか、大きさのある図形そのものとみるかによって、  数，大円の交叉数は共に2となる。小円の交叉数をτ．

その図形の処理は異なる。文字の認識で対象となる文宇   大円の交叉数をη1とし．その点の交叉数の組合せを「同 パターンは太さのある線図形としてさしつかえない。本  心円交叉払描］」と表わすことにすれば、図1−aの 報告では，太さのある線図形から特徴を抽出する手段を   場合は，同心円交叉［2，2］となる。さらに．各円周と 提案し，計算機によってシミレーションを行い，その結   線分との交点の（円の中心を」苗1もとした）方向も得られ 果を報告するものである。特徴抽出には円形視野を使用   るわけであるが，その点が特異点であると判断するには，

するが，安居院ら（文献1．2参照）によっても提案され   同心円交叉［2，2］の場合を除き，方向を必要としな ている。パターンの雑音対策として巨視的処理（文献3   い。同心円交叉ぱ祖］の種類は、それぞれの交叉数の 劇恥を行っているが，パターンの存在の判定にはそれ   最大値をLとすれば （五＋1ア 種類が可能であるが，図

媒礎となっている・       （tl，1］信1胡により得ら、、る甦数の船甦一般的に示

      寸ユ時には，「1司心11」吏苦lf，川1」 と11｝くことに 十る邑

 イ       ノ ノ

！ 〆ノ〆   一      

a       b       c       d      e

図一1 同心円とパターンの一部

1でb．E，4βの特異点を検出するには，すべての組合   形成する。よって，その部分（特異点の集まり）の平均 せでなくてもよい。図1−aは特異点ではないので検出   位置（中央位｛間で特異点の同心円交叉［4ノ｝4を代表

しない。図1−bは端点であ1｝同心円交叉［1，1］で   させる。特異点は不連続に出現する。

検出する。図1−cは交叉数3の3交叉点であるから同    対象バターンは2匝化されたバイナリー・パタ・一ン 心円交叉［3，3］で検出する。交叉数4であれば同心   で，マトリックスの上に表わされるものとする。2次元 円交叉［4，4］で検出する。同様に，交叉数の増加とと   マトリックス上に表現されるのであるから．距離ρを導

もにψ，，πを増加する。屈曲点の検出では，図1−dの   入する。

場合は同心円交叉［1，2ユを検出すればよい、しかし，

同心円交叉［1．2］を検出するためには、この部分だ け線の太さがある程度以上太くなければなちない。たと えば，図1−eの場合は同心円交叉［1、2］が検出さ れないことが多いと思われる。そこで．円周上の交点の 方向を利用して屈曲点を検出する。すなわち，同心円交 叉［2、2］が検出され，小円の交点の方向と大円の交 点の方向が等しく，円周上の2個の交点の方向のなす角 がある範囲内にある場合，屈曲点として検出する。円周 上の交点を検出するには，マスク・パターンを円周上で 回転させ，マスク・パターンとパターンの一部とで論理

      図一2 擬 似 円 積をとり1（true）の数が，閾値より大きい時をパターン

が存在するとする方法をとることによって，平均化され，

儲の影綱少なくなる㌍パターン上の酬点を検  ・｛副＝m・・｛1・1一訓エ・一〃・1｝

出するのであるから沖楠はパター吐にな｛甜ばな   ただL・＝｛…エい＝ω1調

らない．円趾の酬走狛峰）は・1・円と畑で行っ 距勧を用いてマド1・・クス上に円を作れば正方形とな ているのであるから沖心と2個の円周上のパターンの る．こ唖方形を擬∬靴呼び融酬の交点を擬似円 形態によって酷異点桃出するのである坤已がパ 帥心とする項周走査の代酬・・マトリ・・ほ上で

タ＿ン上にあるか否かの判定にも円周走査と同様に，マ   は擬似円（正方形）の辺の上を走査することになる・マ スク．．，ターンを用いる．パタ＿マトリ。ク珪体 トリ・クスの蝋ま肝化されている抽・馴円の半 の酬点の検出には，パターン．マトリ。クス全体を同 径は中心から各辺までの雛であり，整数値をとる・方

心円帥口麟す已さのあるパターンを対象とし 向嚇化されてお日・図2に半径4の擬胴と獅 ているの舗異点の同心円奴［ 1は，パター． 子化方向を示す．半径力猶れば肝化方向の酬異

の一部分で同胴心円奴［刷をもつもの力端 なる呪柵畑酬の比較をする時1珊化方

し，パクーン、マトリ。クス上剛一酬点の集まりを 向の変酬必要となる・擬岬周上紺化方向の小さ

ヨL

32 ³¹ 3〔｝ 四 28 27 26 25

2 24

3 23

4

5 × ²¹

6 20

7 19

8 18

9 10

12 13 ¹⁴ 15 16 17

「注2｝ 文献3参照．

いものから順に走査し，パターンとの交点を調べる・

       ていないため），それぞれの特異点を繰送し検出する方       1     法を用いた。同心円の中心のパターン・マトリックス全 中心の移動      体の走査は，横プ∫向に行う。すなわち，まず，パターン・

       マトリックスの1行目を走査し，そして，2行目を走査        する方法をとる。

N。   、         ワ    1．同心円の中心をパターンの存在を次に調べるべき位     ！㌍ン」，にあ、か？ ｝  置（パターン岬トリ・ク社の点）1・馴する．

       2．中心が移動した位置にパターンの一部が存在するか       Yes      調べ，存在しなければ中心を移動する。

      へ

      ゜     3，同心擬似円の円周を走査し，パターンとの交点の数       とその方向を調べ，同心円交叉［ψ，η1］を検出する。

       4．検出した同心円交叉｛ψ，，司を調べ．抽出すべき特       異点の同心円交叉［ψ，，H］｛ここでは，同心円交叉

N・     、  ［L1］）と『するか齢一致しな1ナftぱ中心の移

     同心円交刻4 1］の         動を行う。同心円交叉［2ほ］の時は，さらに、それ       一致？

      それの擬似円の円周上の交点の方向をも調べて特異点          Yes      を検出する。

      5     5．特異点の平均位置を目：出するために，抽出された特     特異・点の位置の計算      異点が過去に抽出された特異点の近傍に含まれるか否     または記世

      か調べ，含まれれば平均位置を計口：し、そうでなけれ       ばこの位置を新たに記憶しておく，

No      6．パターン・マトリックス全体の走査が終了するまで

      走酬丁， G  継す・

Yes     7 平均位置の

同心円交叉lf， m］の検出

7．パターンの特異点の平均位置〔5で算出されたもの）

 を中心とする同心円交叉［ ，mjを検出し、新たに検  出された同心円交叉［￡抄1］をその特異点の特徴とす

 る。

a．結 果

      おわり       128×128のマトリックス上に表わされたパイ十り一        パターンを対象としたシミレーション結果を示す。これ 図一3 特異点抽出アルゴリズムのフロー・チャート   らのパターンはテスト用に作製したもので、実際の文字

アルゴリズム      ○○○

繊，類点舳鱒た州、1虫立であり湘互に    OCO已○

彰響を及ぼさな・侃それぞれの寺寺異点の抽出を並列   ○○嫁○○

して行うことができる。ア・レ訓ズムも検出する同心円    ○○○○○

奴［翻］の欄が財るだけで．他闘じである．     OOO

簡卑な7ロー・チャー｝を図3に示す。説明では端点抽

出を想定して述べるが紬嘩貼撤Uもほ胴敵あ   図一4マスク パターン

撫籔…………1……1………三………1…

      華c

   図＿5−。テストパターン      図一6−・テスト・パターン

図＿5−b 同心円交叉［L1］の検出された位置      図一6−b 同心円交叉11．1工の検出された位置

図一5−e 同心円交叉［2．2］の検出された位置      図一6−￠ 同心円交叉［1，2］の検出された位置

図一7−a テスト・パターン      図一7−d 同心円交叉［3ほ1の検出された位置

図一7−b 同心円交叉［1，1］の検出された位置      囲一一7−e 同心円交叉［1，2］の検出された位置

      パターン等を入力したものではない。同心円の中心位置       にパターンの一部が存在するか否かの判定に使用したマ       スク・パターンを図4に示す。閥値は15で、それ以下で       あればパターンは存在しないと判定する。特異点の近傍       は距離が8以下のものとする、すなわち，対角線の交点       を中心とする一辺が17の正方形の内部が近傍となる．

       図5−aと図6−aのテスト・パターンに対して特異       点の抽出を行う。この例では、端点（図5−aではA．C        図6−aではD，F）と屈曲点（図5−−aではB図6       −aではE）を抽出すればよい。同心円交叉［1，1］が       検出された点が端点となり，図5−aではA，Cが，図       6−aではD，E， Fが抽出されている．｛図5−b，図6       −b参照）E点は屈曲点であるが視野を狭くすれば端点

図一7−・恥円蜘22］醜出された雌  拷えることもできる洞棚奴［12］では．図6

図一8−a テスト・パターン      図一8−d 同心円交叉［4，4］の検出された位置

図＿8＿b恥円交叉［L1］の検出された雌   図一8−・同心円交叉［1・2］の検出された位置

       一aのEが抽出されている。（図6−c参照）図5−aの        Bは抽出されない。原因は，Eでは線の太い部分があ！L        Bでは太い部分がないためである。逆に，角度の一致した        同心円交叉［2．2］では、図5−aのBが抽出され・

       （図5＿c参照）図6−aのEは抽出されない。同心円        奴［L2］と同棚類ほ2］を用いれば・屈曲        鮒どちらか一方に幽出されると思われる．また・他        の種類の同心円交叉［ψ，斑］も検出されたが（たとえば・

       端点では同心円交叉［2，1］，交叉点では同心円交叉        ［2．31等遵点，奴怠屈齢を抽出するには掴        心臓叉［L1］、剛・円交叉［2．2］洞心瞭叉        ［3．3］洞心腋叉［4，4］洞・心円交叉［L2］

       で廿と思われるはらに，瓢ク・パターンを変えて

図一8−・同心服叉［2・2ユの検出された位置 シミレーシ，ンを行ったが，ほぼ同様の結果が得ら麟

きない。したがって，直線から構成され曲線部分の少な   間の短縮が大きな課題となる。高連化の手段とLて各特 いカタカナの特徴抽出に利用してみた。その結果を図   異点の抽出を並列に行うことは，ハードウェアがあれば 7．図8に示す。      可能である。特異点抽出アルゴリズムも局所的に処理を  なお，抽出した特異点のデータ形式は特異点の位置，   行っているので，ひとつの特異点抽出アルゴリズムその 小円とパターンとの交点の数とその方向，大円とパター   ものの並列処理が可能だと思われる。本報告では，直線 ンとの交点の数とその方向が量子化され、数値化された   図形だけからなるパターンを対象とし曲線等の特徴の抽 ものである。そのデータをもとにしてベクトル図を作製   出は行っていないため，一般のパターン認識の特徴抽出 した。      への幅広い応用には，他の必要な特徴を抽出する必要が  使用した計算機はFACOM・23045Sである。      ある。

4．あとがき      参考文献

 パターン認識への応用を前提として線図形バターンの   ］．安居院el al，「図形の幾何学的特徴抽出の一方法」昭和50 特異点抽出のシミレーションを行ったが，この方法に    年電子通｛甚学会全国大会；降汕論丈集南1172・

よ・て得られたテータをもとにしてカタ卵の文宇認㌔霊鑑霊誓㌫≧蕊の剛酬

識を行いたい。このシミレーションでは良好な結果がで   3．玉木eta1．「バターンの巨視的処理について」九州コニ粟大 ているが，パターンの線の太さが大きく異った場合には，   学研究托1告（工学）第30号昭相50年・

良好な結果が得られるとは思われない。対策として，同