JPH0495180A - 線分・曲線認識方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 【産業上の利用分野】

この発明は、線図形画像を２値ディジタル−データとし
て読み込み、２値デイジタル・データから線分と曲線を
認識して取り出す、線分・曲線認識方式に関するもので
ある。

【従来の技術】

線分と曲線の識別を行う従来技術としては、線図形を短
線分化してシ１−トベクトルで表し、隣り合うシ罰−ト
ベクトル間の角度の変化を調べ、その変化がある所定値
以上のとき曲線と判定し、所定値以内のとき線分と判定
する手法があった（特開平１−１１６７７２号公報）。 また、他の従来技術として、折れ線データに対して曲線
のあてほめを行い曲線近似して表し、この曲線とシｍ　
−）ベクトルとで囲まれる部分の面積を計算し、この面
積に基づいて上記曲線を採用するかの可否を決定する手
法があった（特開昭６２−２５１９８８号公報）。

【発明が解決しようとする課題】

しかし前者の方式の場合、線図形を構成する特徴点（交
差点、屈折点）をあらかじめ抽出し、その特定の区間内
が直線であるか、曲線であるかを認識する方式であって
、複数の直線あるいは直線と曲線が混合している区間を
認識することはできなかった。 また後者の方式の場合、曲線と直線の判定を行うために
、１ｍ像中の全てのシ譚−ト・ベクトルに対して、曲線
の当てほめを行うために、処理に長時間を必要とした。 この発明は、上記従来技術の問題点を解消し、画像処理
を行うことなく、画像データ中の直線線分と曲線を正確
でしかも高速に認識することのできる線分・曲線認識方
式を実現することを目的とするものである。

【課題を解決するための手段】

本発明の線分・曲線認識方式は、２値ディジタル画像を
主走査方向に走査して、背景画素から画像の画素に変化
した画素を開始点の画素とし、画像の画素から背景画素
に変化した画素を終了点の画素とする画素連結データを
生成する画素連結データ生成手段（第１図１０３）と、 画素連結データの相互の関係を調べ、所定の関係を有す
る画素連結データの集まりを画素ブロックデータとして
生成する画素ブロックデータ生成手段（第１図１０５）
と、 生成された画素ブロックデータを調べ、その画素ブロッ
クが直線であるか、曲線であるかを識別する線分・１曲
線認識手段（第１図１．．０７、ｌ　Ｏ８，１０９，１
１０）と を備えたものである。

【作用】

本発明は、前記目的を達成するために、画像を階層的な
データ構造に変換して、そのデータ構造を用いて線分・
曲線認識処理を行う。すなわち、画像を画素連結データ
と、画素連結データの集まりである画素ブロックデータ
により表現されるようにし、これらのデータをもとに線
分と曲線とをそれぞれ識別するものである。 画素連結データ生成手段において、画素連結データを生
成する。画素連結データは、２値ディジタル画像を主走
査方向に走査して、背景画素（白画素）から画像の画素
（黒画素）に変化した画素を開始点の画素とし、画像の
画素から背景画素に変化した画素を終了点の画素とする
ものでありいわゆる画像のラン情報である。 画素ブロックデータ生成手段は画素ブロックデータを生
成する。画素ブロックデータとは、所定の関係を有する
画素連結データの集まりをいう。 その所定の関係としては、例えば、 ■１つの画素連結データには２つ以上の画素連結データ
が連結しない、 ■１つの画素連結データの下に連結する画素連結データ
の長さは、１つ前の画素連結データの長さに対して、大
きく変化しない、 の２つの条件を満たすものがある。 線分・曲線認識手段は、各画素ブロックデータを基に、
画素ブロックが線分を表すものか曲線を表すものかをど
うかを識別する。その識別の具体例としては、例えば、
　■後で述べる本発明の実施例のように、ブロックデー
タをその中に所定数だけ画素連結データを含むようなサ
ブ・ブロックに分割し、その各サブ・ブロックの一番上
と一番下の画素連結データの開始点と終了点の中点を求
めてベクトル・データとし、各画素ブロックデータ内の
ベクトルの方向の変化を調べて直線拳曲線の識別を行う
もの、■　画素ブロックデータ内の各画素連結データの
特定の点（開始点あるいは中点）に対してハフ変換を行
うことで、その画素ブロックデータの直線性を識別する
もの、■　画素ブロックのパターンマツチングにより識
別するもの等がある。 本発明によれば、画像データを画素連結データおよび画
素ブロックデータからなる階層的なデータ構造に変換し
て、そのデータ構造を用いて線分・曲線認識処理を行う
ようにしたので、線分・曲線認識処理を行う際に、処理
時間のかかる画像処理を行う必要がなく、短い処理時間
で正確な処理を行うことができる。

【実施例】

第１図は本発明の一実施例の構成を示すものである。本
実施例の線分・曲線認識方式は、画像入力部１０１、画
像データ記憶部１０２、画素連結データ生成部１０３、
画素連結データ記憶部１０４、画素ブロックデータ生成
部１０５、画素ブロックデータ記憶部ｌＯ６、サブ・ブ
ロック生成部１０７、サブ・ブロック記憶′部１０８、
単位ベクトル計算部１０９、線分・曲線認識部１１０、
画素ブロック分解部１１１、線分データ記憶部１１２、
曲線データ記憶部１１３からな−っている。 画像入力部１０１はイメージスキャナのような画像を２
値化して入力するものである。 画像データ記憶部１０２は画像入力部１０１から入力し
た画像データを記憶するものである。 画素連結データ生成部１０３は、画像データ記憶部１０
２に記憶された２値ディジタル画像を主走査方向に走査
して、背景画素（白画素）から画像の画素（黒画素）に
変化した画素を開始点の画素とし、黒画素から白画素に
変化した画素を終了点の画素とする画素連結データを生
成するものである。 画素連結データ記憶部１０４は、画素連結データ生成部
１０３によって生成されたデータを記憶するものである
。 画素ブロックデータ生成部１０５は、上下方向（副走査
方向）に隣接する画素連結データを調べ、予め定めた関
係を有する画素連結データの集まりを画素ブロックデー
タとするものである。 画素ブロックデータ記憶部１０６は、画素ブロックデー
タ生成部１０５により生成された画素ブロックデータを
記憶するものである。 サブ−ブロック生成部１０７は、画素ブロックデータを
所定の亮さを持つサブ・ブロックに分解し、サブ・ブロ
ック記憶部１０８に記憶するものである。 単位ベクトル計算部１０９は、ある画素ブロックデータ
内の全てのサブ・ブロックに対してそのサブ・ブロック
を表す単位ベクトルを求めるものである。 線分・曲線認識部１１０は、単位ベクトル計算部１０９
で計算した全ての単位ベクトルの変化を調べ、複数の線
分／線要素（線分と曲線）を求めるものである。 画素ブロック分解部１１１は、複数の線分／線要素を含
む画素ブロックデータを単一の線分／線要素を表す画素
ブロックに分解し、線分を表す画素ブロックデータを線
分データ記憶部１１２に、曲線を表す画素ブロックデー
タを曲線データ記憶部１１３に格納するものである。 以下、第１図を参照しながら順をおって折線化処理の手
順を説明する。 画像入力部１０１で入力された、２値のディジタル画像
データは画像データ記憶部１０２に記憶される。画素連
結データ生成部１０３では、画像データ記憶部１０２の
内容から、画像のラン情報である画素連結データと、画
像中の上下方向に連結している画素連結データを表す画
素ブロックデータを抽出する。 第２図を用いて画素連結データの抽出手順を説明する。 なお、第４図は画素連結データを説明した図である。 画像をラスク方向（主走査方向）に走査し、画像の背景
画素値から線図形画素値に変化する画素１ｓ（ｉ、ｊ）
を見つける（第２図ステップ２０１〜２０４）。すなわ
ち、まず画像の幅ｍ１画像の高さｎ１黒画素値ｐｘを設
定しくステップ２０１）、ラスク走査の開始位置をｒ　
＝０＋　Ｊ　＝Ｏとして設定する（ステップ２０２）。 走査位置の画素１ｓ（ｉ、、＋）が黒画素値ｐｘである
かを調べ（ステップ２０３　）、黒画素であるときは、
画素ｌ５（ｉ、ｊ）を開始点として登録する（ステップ
２０４）。 さらに、走査を続けて線図形画素値から背景画素値に変
化する画素Ｉｅ（＋、、＋）≠ｐｘを見つける（ステッ
プ２０５〜２０７）。すなわち、走査が一つの走査ライ
ンの終りに達したかどうかをｉ＜ｍにより判定しくステ
ップ２０５）、終りに達していないときは線図形画素値
から背景画素値に変化したかどうかを判定しくステップ
２０６）、変化していなかったときは走査を１ｍ票進め
（ステップ２０７）　、同様の処理を繰り返す。ステッ
プ２０６の判定で画素の変化があったときすなわちＩｅ
（ｉ、ｊ）≠ｐｘとなったときは画素１ｅ（ｉ、ｊ）を
画素連結データの終了点として登録する（ステップ２０
８）。このとき、ｒＢ像の右端まで線図形画素値から背
景画素値に変化する画素を見つけられないときは、その
走査ライン上で画素の連結が終っていると判断して、線
図形画素値から背景画素値に変化する画素をＩｅ（ｍ、
Ｊ）と決定する。 なお、画素の登録は、画素Ｉｓをｔ番目の画素連結デー
タの開始点５（ｔ）、画素１ｅをｔ番目の画素連結デー
タの終了点Ｅ　（ｔ）として、画素連結データ記憶部１
０４に記憶することにより行う。このとき、付加的な情
報として画素連結データの長さＬ　（ｔ）を−緒に登録
してもよい。さらに、この処理を続け、走査ラインが画
像の肩さ（ｎ）を越えるまで続ける（ステップ２１１〜
２１３）。 次に上記で抽出した画素連結データと画像から、画素ブ
ロックデータの抽出を行う。第３図に画素ブロックデー
タ抽出処理に関する流れ図を示す。 まず、画素連結データの総数をｍに設定しくステップ３
０１）、画素連結データの番号ｎおよび画素ブロックデ
ータの番号ｊをＯに設定する（ステップ３０２）。 画素連結データ記憶部１０４から、ｎ番目の画素連結デ
ータｄａｔａ（ｎ）を取り出し、このデータが既にブロ
ックの一部として登録されているか否かを調べる（ステ
ップ３０３）。既に登録されているときは次の画素連結
データを取り出すためにｎ＝ｎ＋　１とする（ステップ
３０４）。ｎくｍであるかどうかの判定によりすべての
画素連結データについて画素ブロック生成処理が終了し
たかどうかを判定する（ステップ３０５）。 未だ、ステップ３０３の判定において、登録されていな
かったと′きは、新しい画素ブロックデータの生成処理
を行う（ステップ３０６〜３１４）。 新しい画素ブロックデータの生成処理について詳細に説
明する。 画素連結データｄａｔａ（ｎ）が、画素ブロックに登録
されていなかったとき、新しい画素ブロックである画素
ブロックデータｂｌｏｃｋ（ｉ）に登録する（ステップ
３０６）。次に、変数ｎの値を後の利用のために一時的
に退避する（ステップ３０７）。 そして、この画素連結データｄａｔａ（ｎ）が次の２つ
の条件を満たしているか調べる（ステップ３０８）。 ■　下方向に連結している連結画素データが１つだけ存
在する。 ■　下方向に連結している連結画素データの長さが急に
変化しない。例えば、自分自身の長さの２倍以上、ある
いは１／２以下にならない。 条件■■を画素連結データｄａｔａ（ｎ）が満たしてい
ない場合、画素ブロックデータｂｌｏｃｋ　（ｎ）は終
了しているとする。 画素連結データｄａｔａ（ｎ）が条件■■を満たしてい
るとき、このｄａｔａ（ｎ）に連結する画素連結データ
ｄａｔａ（ｊ）を画素連結データ記憶部１０４の中から
探す（ステップ３０９）。 次に画素連結データｄａｔａ（ｊ）に対して、次の条件
■を満たしているかを調べる（ステップ３１０）。 ■　上に続く連結画素データはｄａｔａ（ｎ）のみであ
る。 画素連結データｄａｔａ（ｊ）が条件■を満たしている
とき、この画素連結データｄａｔａ（ｊ）を画素ブロッ
クデータｂｌｏｃｋ（ｉ）に追加登録する（ステップ３
１１）。そして、新しく追加登録した画素連結データｄ
ａｔａ（ｊ）に連結する画素連結データを探すために変
数ｎにｊを設定しくステップ３１２）、ステップ３０８
に戻る。 以上のような処理を画素ブロックデータｂｌ。 ｃｋ（ｉ）が終了するまで続ける。この終了は、ステッ
プ３０８またはステップ３１０で、条件■〜■または■
を満たさなかったことをもって判定し、ステップ３０４
へ戻る。その際に、ステップ３０７で退避した値を変数
ｎに設定するとともに（ステップ３１３）　、変数ｉの
値をインクリメントしておく（ステップ３１４）。 そして、画素連結データ記憶部１０４から画素ブロック
データに登録していない画素連結データを探し、以上の
処理を続け、全ての画素連結データが画素ブロックデー
タに登録されるまで続ける。 本実施例では画素ブロックデータは、その内にある全て
の画素連結データを実際に持っているように説明したが
、実際の画素ブロックデータは、そのブロックが画像内
で占める領域の外接矩形で代表して表し、ブロック内に
含まれる画素連結データは、画素連結データ記憶部１０
４における位置のみを記録している。 画像を画素ブロックデータで表した結果の一例を第５図
に示す。 次に、サブ・ブロック生成部１０７は、画素ブロックデ
ータ記憶部１０６に記憶されている全ての画素ブロック
データを所定の高さ（たとえば画素連結データＮ個分）
を持つサブ・ブロックに分解する。画素ブロックデータ
内の一番上にある画素連結データからＮ個分を１つのサ
ブ・ブロックとして抽出し、これを画素ブロックデータ
の最後の画素連結データに行き着（まで続ける。最後の
サブ・ブロックは、画素連結データをＮ個分取れないこ
とがあるが、残っている画素連結データで最後のサブ・
ブロックとする。 以上のようにしてサブ・ブロック生成部１０７で抽出さ
れた、全てのサブ番ブロックをサブ・ブロック記憶部１
０８に記憶する。記憶されているサブ・ブロックは、次
の処理を簡単にするため、どの画素ブロックデータに属
しているかを表すデータを付加してお（必要がある。そ
のため、各サブ・ブロックは、自分の属している画素ブ
ロックデータが画素ブロックデータ記憶部１０６内のど
こに位置しているかの情報も抽出時に付加される。 次に、単位ベクトル計算部１０９においてサブ・ブロッ
ク記憶部１０８内の各サブ・ブロックを表す単位ベクト
ルを計算する。ただし、ここでは単位ベクトルのＸ成分
のみを計算する。第６図に、単位ベクトルについて説明
した図を示す。 単位ベクトルの計算方法について説明する。まず、サブ
・ブロック記憶部１０８から１つのサブ・ブロックを選
び、このサブ・ブロックの一番上と一番下の画素連結デ
ータの中点を抽出し、サブ・ブロックを表すベクトルデ
ータとする。このベクトルデータをＡ１長さをＩＡＩ、
Ａの始点のＸ座標をＡｓｘ５終点をＡｅｘとすると、ベ
クトルＡの単位ベクトルのＸ成分λは次式で求められる
。 λ＝　（Ａｅｘ　−Ａｓｘ）　／　ｌ　Ａ　ｌ　−（式
１）次に線分・曲線認識部１１０における認識処理につ
いて説明する。単位ベクトル計算部１０９で計算した値
λをある画素ブロックデータについてグラフとして表す
と、第８図のような特徴的なグラフを得ることができる
。つまり、単一の線分からなる画素ブロックデータの場
合（第８図（ａ））、そのλのグラフはほぼ傾き０とな
り、曲線を表す画素ブロックデータの場合（第８図（Ｃ
））、そのλのグラフは増加あるいは減少となる。また
、複数の線分要素をもつ画素ブロックデータの場合（第
８図（ｂ））は、線分要素の分だけ傾き０のグラフに分
割できることがわかる。したがって、λのグラフから幾
つかの傾きＯのグラフに分解できるとき、画素ブロック
分解部１１１においてグラフの示す点で画素ブロックデ
ータを分割する。 曲線を表す画素ブロックデータの場合（第８図（Ｃ））
　、そのλのグラフは増加あるいは減少となることは、
次のことで説明できる。λの値は、第６図に示すように
、Ｘ軸とベクトルＡのなす角をρとするとＣＯＳρの値
を表している。円を画素ブロックデータに分解したとき
には、最悪の場合でも第７図のように４つの部分に分割
され、左右の曲線を表現している画素ブロックデータ内
のサブ・ブロックを表すベクトルとＸ軸のなす角ρは、
０≦ρ≦■（■≦ρ≦２１）となるため、曲線を表す画
素ブロックデータについてのλのグラフは、必ず増加あ
るいは減少という傾きを持って現れる。 線分・曲線認識部１１０では、以上のように画素ブロッ
クデータについてのλのグラフを調べ、そのグラフが傾
きＯのい（つかの部分に分割可能ならば、画素ブロック
分解部１１１において、グラフの表している分割点にお
いて分割して、分割各画素ブロックデータを線分データ
記憶部１１２に記憶し、そのグラフが単一の傾きＯのグ
ラフを表していれば、そのまま線分データ記憶部１１２
に記憶し、グラフが増加あるいは減少の傾きを表してい
れば、曲線データ記憶部１１３に記憶する。 この実施例では、特に明記していないが、画素ブロック
データの中には、曲線にも線分にも判定できないような
画素ブロックデータが存在する。 このような、画素ブロックデータを記憶するために、画
像データ記憶部を線分データ記憶部、曲線データ記憶部
と同様に設けることも可能である。 また、この実施例では、曲線と線分の混在している画素
ブロックデータについて述べていないが、このような画
素ブロックデータについても、λのグラフは傾きＯの部
分と増加あるいは減少の傾きを持つ部分を持つため、そ
れぞれの部分に分割することによって、線分を表す画素
ブロックデータと曲線を表す画素ブロックデータを得る
ことができる。 線分・曲線認識部１１０において、λのグラフの傾きが
Ｏであるとしても、第７図に示すような円の上下部分を
表す画素ブロックデータや矢印の部分は線分として表現
することはできない。このようなことを避けるために、
線分データ記憶部１１２に記憶する前に、そのデータが
線分を表しているか否かを判定する。具体的には、その
画素ブロックデータ内の画素連結データの長さを調べ、
同じ長さの画素連結データが多く存在すれば、その画素
ブロックデータは、線分データであると確定して線分デ
ータ記憶部１１２に記憶する。 また、第７図に示す円の場合、左右の部分のみを曲線を
表す画素ブロックデータと判定するが、残りの部分は線
分とも曲線とも判定されないまま残され、完全な円を認
識できない。しかし、曲線を表す画素ブロックデータに
隣接する画素ブロックデータを調べ、その画素ブロック
データが曲線を表すブロックデータか、線分とも曲線と
も判定されていない場合、これらの画素ブロックデータ
を統合することにより、完全な円を１つのデータとして
表現することができる。 ２値ディジタル画像データを階層的なデータ構造に変換
し、このデータ内の単位ベクトルの方向の変化を調べる
ことにより、各データの表現する図形が、線分であるか
曲線であるかを認識すること。 また、この実施例では、線分−曲線の認識は、画素ブロ
ックデータをサブ・ブロックに分け、その単位ベクトル
により行っているが、この外にもハフ変換を用いて直線
・曲線の識別を行う方法や、画素ブロックのパターンマ
ツチングにより識別する方法がある。例えば、ハフ変換
を用いた場合、画素ブロック内の各画素連結データの特
定の点（開始点、あるいは中点）をハフ変換式ｐ＝ｘ・
ｃｏｓθ＋ｙｅｓｉｎθにより、ｐ−θ空間に変換する
。このとき、ｐは原点と画素連結データ上の点（ｘ、ｙ
）との距離、θは原点と画素連結データ上の点（ｘ、ｙ
）を結んだ線分とＸ座標軸との角度である。このｐ−θ
空間上の特徴からその画素ブロックが直線線分であるか
、また複数の直線線分を持つかを判定することができる
。また、曲線に対応したハフ変換式を用いることで、同
様に曲線の識別が可能である。

【発明の効果】

本発明によれば、２値ディジタル画像データを階層的な
データ構造に変換し、このデータを調べることにより、
各データの表現する図形が、線分であるか曲線であるか
を認識するようにしたので、線分０曲線認識処理を行う
際に、処理時間のかかる画像処理を行う必要がなく、短
い処理時間で正確な線分・曲線認識を行うことができる
。 また、本発明によれば、画素ブロックデータという、あ
る程度まとまった大きさを持つデータを使用しているの
で、図形の局所的な変動に左右されずに線分と曲線を正
確に認識することができる。 また、万一誤認識が発生しても、画素ブロックデータは
画素連結データを含むので、各ブロック内の形状を容易
に知ることができ、認識処理に簡単にフィードバックを
かけることが可能である。

【図面の簡単な説明】

第１図は、本発明の一実施例の構成を示すブロック図で
ある。 第２図は、実施例の画素連結データ生成部の処理につい
ての流れ図である。 第３図は、実施例の画素ブロックデー、夕生成部の処理
についての流れ図である。 第４図は、画素連結データについて説明した図である。 第５図は、画素ブロックデータを説明した図である。 第６図は、単位ベクトルについて説明した図である。 第７図は、曲線に対する画素ブロック・データを説明し
た図である。 第８図は、１つの画素ブロックデータ内での単位ベクト
ルの変化を示したグラフである。 １０１・・・画像入力部、１０２・・・画像データ記憶
部、１０３・・・画素連結データ生成部、１０４・・・
画素連結データ記憶部、１０５・・・画素ブロックデー
タ生成部、１０６・・・画素ブロックデータ記憶部、１
０７・・・サブ書ブロック生成部、１０８・・・サブ・
ブロック記憶部、１０９・・・単位ベクトル計算部、１
１０・・・線分・曲線認識部、１１１・・・画素ブロッ
ク分解部、１１２・・・線分データ記憶部、１１３・・
・曲線データ記憶部。 特許出願人　富士ゼロックス株式会社 代　理　人　弁理士　岩上昇 外２名

Claims (1)

1. 【特許請求の範囲】 ２値ディジタル画像を主走査方向に走査して、背景画素
   から画像の画素に変化した画素を開始点の画素とし、画
   像の画素から背景画素に変化した画素を終了点の画素と
   する画素連結データを生成する画素連結データ生成手段
   と、 画素連結データの相互の関係を調べ、所定の関係を有す
   る画素連結データの集まりを画素ブロックデータとして
   生成する画素ブロックデータ生成手段と、 生成された画素ブロックデータを調べ、その画素ブロッ
   クが直線であるか、曲線であるかを識別する線分・曲線
   認識手段と を備えたことを特徴とする線分・曲線認識方式。