JPS60582A - 二値図形中の線検出方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は、図形画像中における線の切出し方法乃至検出
方法に関し、殊に、予め二値化された図形においての特
定方向を向いた線の検出方法に関する。

二値図形における線の切出しは、画像認識技術の一つの
大きな課題であり、今までにも種々の方法が考えられて
きた。図形の輪郭を追い、これを多角形近似するという
のも一つの方法であるが、種々の方向を向く線同志が重
なっているような場合、この多角形近似法は間接的なも
のとなり、線そのものを切出すには相当複雑な処理を要
する欠点があった。一方、線検出として、ハフ変換の応
用技術があるが、これもエツジを使用するものであるた
め、線が複雑に入組んでくると問題が生ずる。また、処
理にかなりな量の計算を要するのも欠点の一つである。

。 本発明は、この点に鑑みて成されたもので、原ｉ理的に
も明確であり、実現するためのハード・ウェアの構成も
簡単化でＳ、演算処理の容易な線検出方法を提供せんと
するものである。

本発明は、このような目的に沿い、新たな知見に基き、
非常に単純な方法としての所謂、縮小化オペレーション
（通常、シュリンキング・オペレーションと呼ばれる）
の応用を提案するものである。この縮小化オペレーショ
ンは、従来、一般には連結成分数の簡単なめ方として用
いられてきた。即ち、図形が消失するのでない限り、一
様に図形を削って行くのである。従って、この方法によ
ると、例えば凸状の連結体は仕舞いには一点にまで縮小
されるから、この集束点の数を数えることにより、連結
体の個数を数えることができる。

然して、本発明では、こうした縮小化オペレーションに
おける一様な縮小化という既存の概念に沿うだけではな
く、特定の方向に継がっていれば縮小しない、というよ
うに変更して用いており、こうした発想に先ず本発明の
独自性がある。

一般に図形画像を見るのには、縦方向にｎ行、横方向に
ｍ列の計ｎＸｍのマスク構成で見るのが普通であり、ま
たｎ＝ｍであるのが普通であるが、ここでは先ず、簡単
のために縦方向に３行、横方向に３列の３Ｘ３の読取り
マスクを考える。

そして、このように構成したマスクにて読取られる二値
画像中の各画素点を例えば次のような表に化体して表現
する。

上記マスク構成において、中心画素点はＰ点としである
。そして、二値化図形におｌ、）て、画素点中の画素濃
度の有無乃至濃淡は数値“１　”と０“で表すものとす
ると、ここで、水平方向のみの線成分を残すオペレータ
は次のように構成される。

）１０ＲＩＺＯＮＴＡＬ　０ＰＥＲＡＴＯＲ（）１．Ｏ
Ｐ、）１１　Ｆ、＝１の時、 ｄとｅが共に１であったなら、 Ｐ＝１にする。

その他の場合は、 Ｐ＝０とする。　Ｊ この場合、ａ＋ｌ］＋Ｃ＋ｆ＋ｇ＋ｈ＋は、所謂ドント
・ケア（ｄｏｎ’　ｔ　ｃａｒｅ）であって、１でも０
でも良い。

要するに、点Ｐで見て水平方向に継がっていればこれを
残し、さもなくば消す、ということである。

同様に、垂直方向のオペレータは次のように構成する。

ＶＥＲＴＩＣＡＬ　０ＰＥＲＡＴＯＲ（Ｖ、ＯＰ、）１
　Ｆ＝１の時。

ｂ、！−ｇが共に１であれば、 Ｐ＝１とする。

その他の場合は、 Ｐ＝Ｏとする。　」 このような水平、垂直の各オペレータ（Ｈ，ＯＰ。

及びｖ、ｏｐ、）を用いると、例えば、＋″という二値
図形が与えられた時、Ｈ，ＯＰ、のオペレーションを繰
返すことにより、垂直線は消え、水平線のみが残ること
になる。反対に、ｖ、ｏｐ、オペレータを繰返し適用す
ると、水平線は消え、垂直線のみが残ることになる。即
ち、Ｈ，ＯＰ、は水平線の検出、ｖ、ｏｐ、は垂直線の
検出を夫々行なうことになる。

同様にして、二つの対角方向のオペレータも容易に構成
できる。このようにして、先ず、水平。

垂直、対角の主要四方向に就いては容易に線の切出しが
行なえることになる。

次いで、これ等の主要な方向の中間方向に伸びる線の切
出しに就き考えて見る。これに応える一つの方法は、線
方向の分解能を高めるために、オペレータのサイズを３
×３から例えば５×５に増して、夫々の方向に適したオ
ペレータを構成することである。然し、方向は一般には
無限大であるので、これに対処するにはこういった考え
方の方策では限界がある。

そこで、本書では、本発明の要旨を有効に全うする一つ
の補助的な方法として、成る１］を持った方向を検出す
るオペレータの構成を開示して置く。このような方式を
導入すると、この巾方向内での分解能は低減するが、然
し、この１］方向の線を見失うことが無く、一般には無
限の方向を持つ線の切出しを有限のオペレータで成すこ
とができるようになる。

以下、こうした実際的配慮を含めて、本発明の思想を添
付の図面に即して詳細に説明する。

第１図には、種々の方向を向いた幾つかのデジタル直線
が描かれている。但し、この第１図を始め、後続の各図
面中においては、既述した二値画像中の各画素点の１°
′は単に縦の線“ビで表し、ＩＩ　ＯＩＩは表示せずに
白地のままとする。

然して、図示するようなこういった図形画像で問題とな
るのは、先に述べたように、０６と４５゜の方向の中間
を向いた直線である０例えば、略（２８，５”に等しい
ｊａｎ４（１／　２）の方向を向いた線の切出しである
。この線のみの切出しであるなら、第２図（Ａ）に示す
オペレータで良い。本書では、直感的にオペレータの性
質を見易くするために、当該オペレータを図式的に示し
ている。３×３のマスクで“ｌ゛′　（図中では１”）
とある所が実際の図形で“ｌ　’ＴＩとなっていない場
合には、中心位置での図形乃至画素のｌ″は“Ｏ″に変
える。尚、マスクに関しての図中の白地部分乃至ブラン
クはドント・ケアで、何であっても良い。

この第２図（Ａ）に示すオペレータは、オア（ＯＲ）で
示す通り、各マスクにおいて少なくともどちらか一つが
満足されれば、中心の画素点における“ｌ”は“θ′′
とならないことを示している。然し、この第２図（Ａ）
に示すオペレータだけでは、例えばθ″と４５″の間の
全ての方向の線の検出が年末されたとしても、これに対
処することはできない。例えば第１図中で、０°とｔａ
ｎ４（１／２）と−ｐ′間に描かれている線では、図中
に円Ｏで囲った部分において切断されてしまう。

そこで、このような中間角度方向を向いた線の検出が要
求される時には、第２図（Ｂ）に示すように、上記の同
図（Ａ）に示すオペレータに加えて、水平方向のオペレ
ータを用いる。このようにすれば、このオペレータは、
０°と　ｊａｎ’　（１／２）　、及びそれとそれらの
中間にある全ての線を残し、且つ、子れ以外の線を消失
させることができる。

同様な考え方により、第３図示のオペレータ群を構成で
きる。第３図中では、各方向に番号１〜８を与え、夫々
の方向用のマスク構成に夫々オペレータ名を付している
。また、オアは表記ｒＶＪで示しである。これらのオペ
レータにより、第４図に示すように、１１」のあるへ方
向の線検出が可能となる。然し、ここで若干の注意が必
要である。

それは、一種のデッド・ロック現象である。例えば第３
図中のｎｖｐ　、オペレータでは、垂直線は消去トれて
しまう筈であるが、第５図（Ａ）に示すように、このＤ
ＶＰ　、オペレータ中にはその構成要素；があるため、
同図中、Ａ点の１′が消えないということが起こり得る
のである。また、この反対側にあるＡ′点も、下のＢ点
で示されるように、消えないで残ってしまう。この現象
は、線ｌＪが３メツシユ以」二になると起こってくる。

こうしたデッド・ロックを強制的に崩すには、例えば３
×３の垂直線は、第５図（Ｂ）に示すように、その中心
を強制的に“０′°にすれば良い。このオペレーション
はｎｖｐ、のオペレーションには伺等悪い影響１彰与え
ない。同様な事が水平線、対角線に就いて−６言えるの
で、同様にこれらを壊すオペレータが−Ｊ要である。

次に実際的な問題となってくるのは、線の先端が削られ
てしまうことである。然しこれは、線はその線ｌＪより
十分に長いと仮定できるので、線そのものが消えること
はない。またオペレータの繰返し回数が分っているので
、後での修正は容易である。また、何回かの繰返しの後
、線が消失していくのを検出して、その時点でその点で
の消去オペレーションを停止させることもできる。こう
した付帯的方法自体は、これまでの公知技術の援用で足
りる。

以上のようにして、この実施例によれば、第３図示のへ
種類のオペレータにより、夫々の方向を持った線が検出
または切出されることになる。第６図以降に、より具体
的な一例を示す。この第６図（Ａ）には入力文字の一例
として、“横“なる文字が示されており、同図（Ｂ）　
、　（Ｃ）　、　（Ｄ）　、　（Ｅ）には夫々、方向１
，２，３，４．に沿う各成分が振されている。

本図から顕かなように、垂直線は、Ｔ度ｌと２の中間方
向を向いているため、両方に等しく検出されてしまう。

一般に図形の任意の点が複数の方向を持つことはあり得
る。例えば、線の公差点では、公差する線の数だけの方
向を持つ。そこで、問題は、実際に複数の方向を持つ場
合と、上述のように見掛けのものとをどうやって区別す
るかである。

然し、これは例えば、−例として下記の方法により比較
的簡単に行なうことができる。

先ず、簡単のため、既述した各方向の中、ｌと２．３と
４，５と６，７と８．を夫々纏めて四方向とする。そし
て、これら纒めた四方ｌｆｑ　＆こ改めて１．２，３，
４．の番号を伺ける。尚、実際にも、文字認識等の応用
では、これらの方向の分解能で十分であることが知られ
てしする。

次に、このような四つの方向内におｌ、Ｘて、各ノテ向
に割振られた線の夫々の面積を計算する。正確に言うと
、連結する領域の面積である。これ（士良憫知られた公
知手法でめることができる。そこ÷、例えば、方向ｌと
方向２とで互しｓｌこ重なり合尋線分をチェックし、そ
の重なり具合力ζ予定の閾値より少なければそれは本当
の重なりであり、大きければそれは見掛けの重なりであ
る力）ら、どちらかの方向に同定するようにする。

第７図に、第６図示の入力文字に対する具体例を示す。

ここで、第７図（Ｃ）　、　ＣＤ）中に若干、ノイズ的
な線の検出が見られるが、相対的に無視される性質のも
のである。然し、これに対して、隣り合う方向で切出さ
れた線分を比較し、比較される線分に、比較する注目方
向の線分が殆ど含まれるような関係があれば、当該注目
方向のその線分は消去する、という考え方で実際にノイ
ズを除去したより高精度な例を第７図（Ｅ）　、　（Ｆ
）に示す。

同図（Ｅ）は同図（’Ｃ）に、同図（Ｆ）は同図（Ｄ）
に、夫々対応する。

上述した本発明の方法をハード・ウェア化するには種々
の方法があり、本発明においてその構成を特定するもの
ではないが、本書では、先に例と１て示した漢字認識の
場合を想定して一例を示しＩＹ置く。

先ず、四方向に対応させて、四個のシフト・レジスタＳ
ＲＩ〜ＳＷ４を用いる。入力の二値化図形Ｉｉは、これ
等四個のシフト・レジスタＳＲＩ〜ＳＲ４に並列に供給
する。これらシフト・レジスタのメモリ空間の大きさは
入力文字枠のサイズに等しく、例えば６４Ｘ　Ｅｉ４で
ある。この様子を第８図に示している。また、用いるシ
フト・レジスタは図示のように巡回式のものとする。即
ち、文字平面全面に並列にオペレーションを行なう代わ
りＫ、出口の所での局所的オペレーション０．ＬＯＣＡ
Ｌ、を用い、図形をシフトさせることにより、−回の巡
回でそれを行なう。

各オペレーション０．ＬＯＣＡＬ、の構成が第９図に示
されている。片隅に示す３Ｘ３のパターンが八個の縮小
化オペレータ０１〜０８に並列に供給される。

その中の一個でも、そのオペレータに予定されている方
向に線が継がっていることを検出すると、オア・ゲート
Ｇｏｒには論理”　ｉ　”のパルスが発生螺、このパル
スを反転入力に受けるアンド・グー７．１ｒＧａｎｄは
閉じた状態に維持されるため、このアン１：「・ゲート
出力としてのリヤー２ト・パルスＰｒは出ることがなく
、片隅に示す３Ｘ３のレジスタ部分の中心値はそのまま
保持される。

一方、全てのオペレータが線の継がりを検出しなかった
時には、全てのオア・ゲートＧＯ［の出力は論理１１０
１１となるため、アンド・グー）　Ｇａｎｄに出力パル
スＰｒが発生して、３×３の中心画素点の値はリセット
、即ち“０°゛にされる。このようにして線の縮小化が
実行されて行く。このようにして、何回か予め決められ
た回数（この実施例においては線の太さにより決まる）
、シフト・レジスタ上で文字パターンが巡回することに
より、線の切出しが行なわれる。

こうした処理に引続く処理は良く知られている公知手法
によって良く、本発明には直接の関係はないため、その
説明は省略する。

ともかくも、以上詳記のように、本発明によれば、明快
な原理により、極めて簡単な構成で特定方向の線の切出
し乃至検出が行なえ、文字認識等ニド画像認識技術に大
きな貢献を為し得るものであ′ト・

【図面の簡単な説明】

第１図は各方向に伸びる線の説明図、第２図は予定の特
定方向に伸びる線をめるためのオペレータ例の説明図、
第３図は入方向検出用オペレータ群の説明図、第４図は
検出されるべきへ方向の説明図、第５図はデッド・ロッ
ク現象の説明図、第６図は入力文字図形の一例とその検
出各方向成分の説明図、第７図は見掛けの重なりを排除
した場合ゐ各方向成分の説明図、第８図及び第９図は本
発明の方法の実施に用ｌ／）る装置の一例の概略構成図
、である。 第２図 （Ａ） 第３図 力６０厩呂　マ人り　重重べ　大ペレータＧ第４図 第６図 （Ａ）（Ｂ） φ×Ｏ Ｊ　１１１１１１１１１１１１１１１１１１１１１１　
ＩＩ　１１１１１１１１１１１１１１１１１１１１１　
Ｉｌｌ　ｌ　１１１１１１１１１１１１１１１１１ ：：：ｉ ：１１ｉ す１ｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌ
ｌｌｌｌｌｌｌｌ１曲曲１１１１１１１１１１１１１１
１１１１１１１１１′ １ｉ１ｉ Ｊ　１１１１１１１１１１１１１１１１１１１１１　Ｉ
Ｉ　Ｉ　Ｉｌｌ　１１１１１１１１１１１１１１１１１
１１１１　ＩＩ目１１１１１１１１１１１１巴目１１１
１１１１１１１１１１１１１１１１１１１１１１１１１
１１１１１１１１１１１１１１１１１１１１１１１１１
１１１１１１１１１山 ”　！ｉｔＬ ＋１ｉｌｉｉ Ｊ１１１１１１１１１１１１１１１１１１１１１田＋１
１１１１１１１１１１１１１嗜１１１１１１１１１１１
１１１１１１１１１１１１噛山 ｊｊｊ 硼

Claims (1)

【特許請求の範囲】
1. 二値図形中において、特定の方向を向いた線を検出する
   二値図形中の線検出方法であって、複数列、複数行の画
   像読取りマスク構成において予定の特定方向に継がるも
   のを残し他は消去するオペレータを作成し、該オペレー
   タを繰返し適用することにより、該特定方向に伸びる線
   のみを残すことを特徴とする二値図形中の線検出方法。