JPH022189B2 - - Google Patents
Info
- Publication number
- JPH022189B2 JPH022189B2 JP57214354A JP21435482A JPH022189B2 JP H022189 B2 JPH022189 B2 JP H022189B2 JP 57214354 A JP57214354 A JP 57214354A JP 21435482 A JP21435482 A JP 21435482A JP H022189 B2 JPH022189 B2 JP H022189B2
- Authority
- JP
- Japan
- Prior art keywords
- line
- run
- stroke
- strokes
- list storage
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06V10/00—Arrangements for image or video recognition or understanding
- G06V10/40—Extraction of image or video features
- G06V10/44—Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
- G06V10/457—Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components by analysing connectivity, e.g. edge linking, connected component analysis or slices
Landscapes
- Engineering & Computer Science (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Multimedia (AREA)
- Theoretical Computer Science (AREA)
- Character Discrimination (AREA)
- Image Analysis (AREA)
Description
【発明の詳細な説明】
産業上の利用分野
本発明は図形、図面の認識や理解などを行なう
際、線図形中から、その形状特徴を示す線部分要
素としてのストロークを抽出するストローク抽出
装置に関するものである。
際、線図形中から、その形状特徴を示す線部分要
素としてのストロークを抽出するストローク抽出
装置に関するものである。
従来例の構成とその問題点
従来、計算機へ線図形（論理回路図面や図表
等）情報を入力には、 線図形の座標情報をコーデイングし、カード
で入力する デイジタイザ、タブレツト等で線図形の座標
を指定して入力する グラフイツクデイスプレイ上にキイボードや
タブレツトからの入力により線図形を描きなが
ら入力する 線図形を画像データとして読み取り、パター
ン認識によつて情報を得る 等の方法がある。この中での入力方法は、計算
機による自動化が計れること、処理工数の短縮が
計れること、および人手介入によるミスを減少で
きることなど非常に大きな効果が期待できる。そ
のために関する方法にはこれまでいくつかの装
置が考案されている。
等）情報を入力には、 線図形の座標情報をコーデイングし、カード
で入力する デイジタイザ、タブレツト等で線図形の座標
を指定して入力する グラフイツクデイスプレイ上にキイボードや
タブレツトからの入力により線図形を描きなが
ら入力する 線図形を画像データとして読み取り、パター
ン認識によつて情報を得る 等の方法がある。この中での入力方法は、計算
機による自動化が計れること、処理工数の短縮が
計れること、および人手介入によるミスを減少で
きることなど非常に大きな効果が期待できる。そ
のために関する方法にはこれまでいくつかの装
置が考案されている。
しかしながら従来の方法には、ストロークや線
図形の構成要素を抽出するために、原画像の全て
のデータ上での追跡方法を採つているため、原画
像の全てのデータを蓄積する大容量の記憶部が必
要である。また、追跡方法の前処理として細線化
処理が必要な場合もあり、この場合は処理時間が
長くかかる。さらに抽出を確実にまた効率良く行
なうためには、直線は定規を使用して書いたり、
図面構成要素の形はテンプレートを使用して書く
必要がある等、図面作成上に大きな制約を有する
という欠点がある。
図形の構成要素を抽出するために、原画像の全て
のデータ上での追跡方法を採つているため、原画
像の全てのデータを蓄積する大容量の記憶部が必
要である。また、追跡方法の前処理として細線化
処理が必要な場合もあり、この場合は処理時間が
長くかかる。さらに抽出を確実にまた効率良く行
なうためには、直線は定規を使用して書いたり、
図面構成要素の形はテンプレートを使用して書く
必要がある等、図面作成上に大きな制約を有する
という欠点がある。
発明の目的
本発明は上記従来の問題点を解消するもので、
原画像データすべてを蓄積する記憶部をもたなく
とも、線図形を構成する水平ストローク、垂直ス
トローク、ななめストロークとその接続関係を抽
出でき、細線化処理等の前処理が不要であり、さ
らに対象とする図形にも大きな制約を加える必要
がない線図形のストローク抽出装置を提供するこ
とを目的とする。
原画像データすべてを蓄積する記憶部をもたなく
とも、線図形を構成する水平ストローク、垂直ス
トローク、ななめストロークとその接続関係を抽
出でき、細線化処理等の前処理が不要であり、さ
らに対象とする図形にも大きな制約を加える必要
がない線図形のストローク抽出装置を提供するこ
とを目的とする。
発明の構成
本発明は２次元平面上に表現される２次元線図
形をラインスキヤナなどの線走査により観測しな
がら観測値を順次２値化処理する読取手段と、前
記２値化処理により生成された白画素、黒画素を
表現する２値化データを一走査線上で連続する黒
画素の集合毎に、上記２次元平面上における始点
と終点の座標値データに変換する処理および一走
査線上に存在する上記連続する黒画素の集合の数
を計数する処理とを行なうスキヤンリスト生成手
段と、前記スキヤンリスト生成手段により生成さ
れた座標値データと連続する黒画素の集合の数と
を、最新のものから２走査線分記憶するスキヤン
リスト記憶部と、前記スキヤンリスト記憶部に記
憶されているデータをもとに、隣接する２本の走
査線上にある一走査線上で連続する黒画素の集合
の長さと、前記連続する黒画素の隣接する２本の
走査線相互の接続関係とを調べ、あらかじめ設定
された接続パターン毎に処理を振り分けるパター
ン処理呼出手段と、前記パターン処理呼出手段に
より起動され、各接続パターンより、図形を構成
する線部分であるストロークとストローク相互間
の接続部分を表わすノードとを生成してパターン
処理を行なうパターン処理手段とを設け、前記２
走査線分の一走査線で連続する黒画素の集合の始
点と終点の座標値データと一走査線上に存在する
前記連続する黒画素の集合の数とを一走査線分更
新し、上記パターン毎に処理を振り分け、パター
ン処理を行なうことを反復することによつて、図
形を構成する線部分として、水平、垂直、ななめ
の３種のストロークとその接続関係を抽出するも
のである。
形をラインスキヤナなどの線走査により観測しな
がら観測値を順次２値化処理する読取手段と、前
記２値化処理により生成された白画素、黒画素を
表現する２値化データを一走査線上で連続する黒
画素の集合毎に、上記２次元平面上における始点
と終点の座標値データに変換する処理および一走
査線上に存在する上記連続する黒画素の集合の数
を計数する処理とを行なうスキヤンリスト生成手
段と、前記スキヤンリスト生成手段により生成さ
れた座標値データと連続する黒画素の集合の数と
を、最新のものから２走査線分記憶するスキヤン
リスト記憶部と、前記スキヤンリスト記憶部に記
憶されているデータをもとに、隣接する２本の走
査線上にある一走査線上で連続する黒画素の集合
の長さと、前記連続する黒画素の隣接する２本の
走査線相互の接続関係とを調べ、あらかじめ設定
された接続パターン毎に処理を振り分けるパター
ン処理呼出手段と、前記パターン処理呼出手段に
より起動され、各接続パターンより、図形を構成
する線部分であるストロークとストローク相互間
の接続部分を表わすノードとを生成してパターン
処理を行なうパターン処理手段とを設け、前記２
走査線分の一走査線で連続する黒画素の集合の始
点と終点の座標値データと一走査線上に存在する
前記連続する黒画素の集合の数とを一走査線分更
新し、上記パターン毎に処理を振り分け、パター
ン処理を行なうことを反復することによつて、図
形を構成する線部分として、水平、垂直、ななめ
の３種のストロークとその接続関係を抽出するも
のである。
実施例の説明
以下、図面を参照しながら本発明の一実施例に
ついて説明する。
ついて説明する。
第１図は本発明の一実施例における線図形のス
トローク抽出装置のブロツク図である。
トローク抽出装置のブロツク図である。
同図において、１はフアクシミリ等のラスタ走
査型の読取部で、２次元線図形に２値化処理を行
ない、白画素と黒画素とを表現する２値化データ
を出力する。２はスキヤンリスト生成部で、読取
部１の出力情報に基いて黒ラン毎の始点、終点の
座標値データへの変換と一走査線上の黒ラン数の
計数と水平、垂直及びななめストロークのいずれ
を構成する黒ランかの識別を行なう。３はスキヤ
ンリスト生成部で、スキヤンリスト生成部２から
送出される黒ランの始点、終点の座標値データ、
黒ランの種類及び一走査線上の黒ランの数を常に
新しいものから２走査線分だけ記憶する。４はパ
ターン処理呼出部で、上下２走査線上の黒ランの
接続関係を調べ、あらかじめ設定されたパターン
のうちどのパターンに属するかを類別し、対応す
るパターン処理部５を呼び出す。６はリスト処理
部で、パターン処理部５の呼び出しに応じてスト
ロークの基本的抽出処理を行なう。７ａ，７ｂ及
び７ｃはそれぞれストロークリスト記憶部、ノー
ドリスト記憶部及びランリスト記憶部で、リスト
処理部６の処理結果に応じて最新のデータに遂次
更新され、最終的にストロークとストロークの接
続関係を記憶する。８は出力部で、線図形のスト
ローク抽出結果を出力する。
査型の読取部で、２次元線図形に２値化処理を行
ない、白画素と黒画素とを表現する２値化データ
を出力する。２はスキヤンリスト生成部で、読取
部１の出力情報に基いて黒ラン毎の始点、終点の
座標値データへの変換と一走査線上の黒ラン数の
計数と水平、垂直及びななめストロークのいずれ
を構成する黒ランかの識別を行なう。３はスキヤ
ンリスト生成部で、スキヤンリスト生成部２から
送出される黒ランの始点、終点の座標値データ、
黒ランの種類及び一走査線上の黒ランの数を常に
新しいものから２走査線分だけ記憶する。４はパ
ターン処理呼出部で、上下２走査線上の黒ランの
接続関係を調べ、あらかじめ設定されたパターン
のうちどのパターンに属するかを類別し、対応す
るパターン処理部５を呼び出す。６はリスト処理
部で、パターン処理部５の呼び出しに応じてスト
ロークの基本的抽出処理を行なう。７ａ，７ｂ及
び７ｃはそれぞれストロークリスト記憶部、ノー
ドリスト記憶部及びランリスト記憶部で、リスト
処理部６の処理結果に応じて最新のデータに遂次
更新され、最終的にストロークとストロークの接
続関係を記憶する。８は出力部で、線図形のスト
ローク抽出結果を出力する。
上記のように構成された装置について、以下そ
の動作を説明する。
の動作を説明する。
まず対象となる２次元線図形は、フアクシミリ
等のラスタ走査型の読取部１で観測され、２値化
処理により、白画素と黒画素を表現する２値化デ
ータとなる。この２値化データは、順次、スキヤ
ンリスト生成部１２に入力され、黒ラン毎に、２
次元平面上での始点、終点の座標値データに変換
され、出力される。
等のラスタ走査型の読取部１で観測され、２値化
処理により、白画素と黒画素を表現する２値化デ
ータとなる。この２値化データは、順次、スキヤ
ンリスト生成部１２に入力され、黒ラン毎に、２
次元平面上での始点、終点の座標値データに変換
され、出力される。
またスキヤンリスト生成部２では、黒ランの長
さによつて、それが水平ストロークを構成する黒
ラン（以下水平ランと言う）か、垂直ストローク
あるいはななめストロークを構成する黒ラン（以
下、非水平ランと言う）かを識別する。すなわち
第２図に示すように２次元線図形の代表線巾を
Ｗ、ストローク２１の水平方向からの傾きをθと
すると、ラン長Ｌは、 Ｌ＝（１／sinθ）Ｗ となる。したがつて水平ストロークとみなす最大
のθをθHとすると、ラン長Ｌが、 Ｌ≧（１／sinθH）Ｗ となる黒ランを水平ランとする。θHとしては例え
ば15゜程度を選ぶことにより、通常の手書き図形
に対し、良好な結果を得ることができる。
さによつて、それが水平ストロークを構成する黒
ラン（以下水平ランと言う）か、垂直ストローク
あるいはななめストロークを構成する黒ラン（以
下、非水平ランと言う）かを識別する。すなわち
第２図に示すように２次元線図形の代表線巾を
Ｗ、ストローク２１の水平方向からの傾きをθと
すると、ラン長Ｌは、 Ｌ＝（１／sinθ）Ｗ となる。したがつて水平ストロークとみなす最大
のθをθHとすると、ラン長Ｌが、 Ｌ≧（１／sinθH）Ｗ となる黒ランを水平ランとする。θHとしては例え
ば15゜程度を選ぶことにより、通常の手書き図形
に対し、良好な結果を得ることができる。
そしてスキヤンリスト生成部２は、対象と考え
ている黒ランが水平ランか非水平ランかの識別結
果と、一走査線上に存在する黒ランの個数を出力
する。
ている黒ランが水平ランか非水平ランかの識別結
果と、一走査線上に存在する黒ランの個数を出力
する。
次にスキヤンリスト生成部２から出力される黒
ランの始点、終点の座標値データ、黒ランの種類
及び一走査線上の黒ランの数は、常に新しいもの
から２走査線分がスキヤンリスト記憶部３に登録
される。（以下、スキヤンリスト記憶部３の内容
を単にスキヤンリストと言い、最新走査線のスキ
ヤンリストを第２走査線のスキヤンリスト、その
１本前のスキヤンリストを第１走査線のスキヤン
リストと言う。） そしてパターン処理呼出部１４では、上記スキ
ヤンリストをもとに、第２走査線上の黒ランと、
第１走査線上の黒ランを順に対応させ、上下２走
査線上の黒ランの接続関係を調べ、その接続関係
と、それらの黒ランの種類（水平ランか非水平ラ
ンか）に応じて、あらかじめ設定されたパターン
のうちどのパターンに属するか類別し、対応する
パターン処理部５を呼び出す。
ランの始点、終点の座標値データ、黒ランの種類
及び一走査線上の黒ランの数は、常に新しいもの
から２走査線分がスキヤンリスト記憶部３に登録
される。（以下、スキヤンリスト記憶部３の内容
を単にスキヤンリストと言い、最新走査線のスキ
ヤンリストを第２走査線のスキヤンリスト、その
１本前のスキヤンリストを第１走査線のスキヤン
リストと言う。） そしてパターン処理呼出部１４では、上記スキ
ヤンリストをもとに、第２走査線上の黒ランと、
第１走査線上の黒ランを順に対応させ、上下２走
査線上の黒ランの接続関係を調べ、その接続関係
と、それらの黒ランの種類（水平ランか非水平ラ
ンか）に応じて、あらかじめ設定されたパターン
のうちどのパターンに属するか類別し、対応する
パターン処理部５を呼び出す。
なお上記黒ランの接続関係は、スキヤンリスト
をもとに、次のように調べる。
をもとに、次のように調べる。
すなわち、第３図に示すように第２走査線上の
黒ランの始点、終点のｘ座標をxS,2，xE,2、また、
第１走査線上の黒ランの始点、終点ｘ座標をxS,1，
xE,1とすると、これらの間に次の，，のう
ち、どれか１つの関係がある時、上下２走査線上
の黒ランは接続していると判定する。
黒ランの始点、終点のｘ座標をxS,2，xE,2、また、
第１走査線上の黒ランの始点、終点ｘ座標をxS,1，
xE,1とすると、これらの間に次の，，のう
ち、どれか１つの関係がある時、上下２走査線上
の黒ランは接続していると判定する。
xS,2≦xS,1≦xE,2＋１
xS,2−１≦xE,1≦xE,2
xS,1＜xS,2≦xE,2＜xE,1
なおここで座標を次のようにとる。ラインスキ
ヤナの主走査方向をｘ座標とし、副走査方向（主
走査方向に垂直方向）をｙ座標とする。ｘ方向は
画素毎に、ｙ方向は１走査線毎に座標値が１だけ
増加するものとする。
ヤナの主走査方向をｘ座標とし、副走査方向（主
走査方向に垂直方向）をｙ座標とする。ｘ方向は
画素毎に、ｙ方向は１走査線毎に座標値が１だけ
増加するものとする。
上記のあらかじめ設定された接続パターンは多
種類あるが、その中で基本的なものは次の７種類
である。
種類あるが、その中で基本的なものは次の７種類
である。
Ａ…第４図ａに示すように、第２走査線に第１走
査線の黒ランと接続しない水平ランが存在する
場合。
査線の黒ランと接続しない水平ランが存在する
場合。
Ｂ…第４図ｂに示すように、第２走査線に第１走
査線の黒ランと接続しない非水平ランが存在す
る場合。
査線の黒ランと接続しない非水平ランが存在す
る場合。
Ｃ…第４図ｃに示すように、第２査線の水平ラン
と第１走査線の水平ランが接続している場合。
と第１走査線の水平ランが接続している場合。
Ｄ…第４図ｄに示すように第２走査線の非水平ラ
ンと、第１走査線の非水平ランが接続している
場合。
ンと、第１走査線の非水平ランが接続している
場合。
Ｅ…第４図ｅに示すように、第２走査線の水平ラ
ンと、第１走査線の非水平ランとが接続してい
る場合。
ンと、第１走査線の非水平ランとが接続してい
る場合。
Ｆ…第４図ｆに示すように、第２走査線の非水平
ランと、第１走査線の水平ランとが接続してい
る場合。
ランと、第１走査線の水平ランとが接続してい
る場合。
Ｇ…第４図ｇに示すように、第１走査線に非水平
ランがあり、第２走査線にこれと接続されるべ
き黒ランが存在しない場合。
ランがあり、第２走査線にこれと接続されるべ
き黒ランが存在しない場合。
以上のように、スキヤンリストをもとに黒ラン
の接続関係が分類できる。
の接続関係が分類できる。
さてパターン処理呼出部４で呼出されたパター
ン処理部５では、パターンに応じた処理手順に従
い、後述するリスト処理部６を複数個呼び出し、
後述するストロークリスト記憶部７ａ、ノードリ
スト記憶部７ｂ、ランリスト記憶部７ｃをリスト
処理部６の処理結果に応じて最新のデータに遂次
更新して、最終的にストロークとストロークの接
続関係をこれらの記憶部７ａ〜７ｃに蓄積する。
ン処理部５では、パターンに応じた処理手順に従
い、後述するリスト処理部６を複数個呼び出し、
後述するストロークリスト記憶部７ａ、ノードリ
スト記憶部７ｂ、ランリスト記憶部７ｃをリスト
処理部６の処理結果に応じて最新のデータに遂次
更新して、最終的にストロークとストロークの接
続関係をこれらの記憶部７ａ〜７ｃに蓄積する。
ここでパターン処理部５と、パターン処理部５
から呼び出されるリスト処理部６で行われるスト
ロークの基本的な抽出過程について、上記記憶部
と関連させながら説明をする。
から呼び出されるリスト処理部６で行われるスト
ロークの基本的な抽出過程について、上記記憶部
と関連させながら説明をする。
(イ) 第５図ａに示すように水平ランが接続してい
る場合、 順次走査をして行くと第２走査線分のスキヤ
ンリストの最新のスキヤンリストである第２走
査線のスキヤンリストにまず第ｉランが現われ
る。この場合、この黒ランから水平ストローク
が始まると判断し、ストロークリスト記憶部７
ａにストロークの種類と第ｉランのｙ座標、始
点および終点のｘ座標を登録する。
る場合、 順次走査をして行くと第２走査線分のスキヤ
ンリストの最新のスキヤンリストである第２走
査線のスキヤンリストにまず第ｉランが現われ
る。この場合、この黒ランから水平ストローク
が始まると判断し、ストロークリスト記憶部７
ａにストロークの種類と第ｉランのｙ座標、始
点および終点のｘ座標を登録する。
次にスキヤンリストを１ライン分更新すると
第１走査線のスキヤンリストに第ｉランが第２
走査線のスキヤンリストに第（ｉ＋１）ランが
現われる。ここで、ストロークリスト記憶部７
ａの始点および終点のｘ座標と第（ｉ＋１）ラ
ンの始点および終点のｘ座標を第（ｉ＋１）ラ
ンの始点および終点のｘ座標を比較し、ストロ
ークリスト記憶部７ａを更新する。即ち、 xS＝MiN（xS，xS，I+1）を始点ｘ座標 xE＝MAX（xE，xE，I+1）を終点ｘ座標とする。
第１走査線のスキヤンリストに第ｉランが第２
走査線のスキヤンリストに第（ｉ＋１）ランが
現われる。ここで、ストロークリスト記憶部７
ａの始点および終点のｘ座標と第（ｉ＋１）ラ
ンの始点および終点のｘ座標を第（ｉ＋１）ラ
ンの始点および終点のｘ座標を比較し、ストロ
ークリスト記憶部７ａを更新する。即ち、 xS＝MiN（xS，xS，I+1）を始点ｘ座標 xE＝MAX（xE，xE，I+1）を終点ｘ座標とする。
但し、xS，xE：ストロークリスト記憶部１７ａ
に登録されている水平ストロークの始点および
終点のｘ座標。
に登録されている水平ストロークの始点および
終点のｘ座標。
xS，I+1，xE，I+1：第（ｉ＋１）ランの始点
および終点のｘ座標。
および終点のｘ座標。
以下、順次スキヤンリストを更新しながら同
様の処理を繰り返し、第１走査線上のスキヤン
リストに第（ｉ＋ｋ）ランが現われた時に、第
２走査線には続く黒ランが無いため水平ストロ
ークの抽出が完了する。すなわち、第５図ｂに
示すように、最小の始点座標xSと最大の終点座
標xEとを結ぶストローク５１が検出される。
様の処理を繰り返し、第１走査線上のスキヤン
リストに第（ｉ＋ｋ）ランが現われた時に、第
２走査線には続く黒ランが無いため水平ストロ
ークの抽出が完了する。すなわち、第５図ｂに
示すように、最小の始点座標xSと最大の終点座
標xEとを結ぶストローク５１が検出される。
(ロ) 第６図ａに示すように非水平ランが連続して
いる場合、 順次走査を行なうとまず第２走査線のスキヤ
ンリストに第ｉランが現われる。この時この黒
ランより垂直ストロークあるいはななめストロ
ークが始まつたと判断し、ランリスト記憶部７
ｃに第ｉランのｙ座標、始点および終点のｘ座
標を登録する。その後スキヤンリストを順次更
新してゆくと第２走査線のスキヤンリストに
は、第（ｉ＋１）ラン、第（ｉ＋２）ラン……
と現われるが、その都度ランリスト記憶部１７
ｃにそのランの情報（例えば始点と終点の座
標）を登録してゆく。そして、第１走査線のス
キヤンリストに第（ｉ＋ｋ）ランが現われた
時、第２走査線上に続く黒ランが存在しないた
めに垂直ストロークあるいは、ななめストロー
クが終結したと判断し、遂次記憶したランリス
トの情報より、それが垂直ストロークか、なな
めストロークか、あるいは雑音であるか判別
し、ストロークリスト記憶部７ａにそのストロ
ークの種類と始点および終点の座標を登録す
る。その結果、ストロークは第６図ｂ６１に示
すように抽出される。
いる場合、 順次走査を行なうとまず第２走査線のスキヤ
ンリストに第ｉランが現われる。この時この黒
ランより垂直ストロークあるいはななめストロ
ークが始まつたと判断し、ランリスト記憶部７
ｃに第ｉランのｙ座標、始点および終点のｘ座
標を登録する。その後スキヤンリストを順次更
新してゆくと第２走査線のスキヤンリストに
は、第（ｉ＋１）ラン、第（ｉ＋２）ラン……
と現われるが、その都度ランリスト記憶部１７
ｃにそのランの情報（例えば始点と終点の座
標）を登録してゆく。そして、第１走査線のス
キヤンリストに第（ｉ＋ｋ）ランが現われた
時、第２走査線上に続く黒ランが存在しないた
めに垂直ストロークあるいは、ななめストロー
クが終結したと判断し、遂次記憶したランリス
トの情報より、それが垂直ストロークか、なな
めストロークか、あるいは雑音であるか判別
し、ストロークリスト記憶部７ａにそのストロ
ークの種類と始点および終点の座標を登録す
る。その結果、ストロークは第６図ｂ６１に示
すように抽出される。
ここで、垂直ストロークとななめストローク
との判別は、１例としてストロークを構成する
第６図ａ第ｉランおよび第（ｉ＋ｋ）ランの位
置関係より、求めることができ。即ち、始ラン
（最初の黒ラン）の中点を（xS，YS）終ラン
（最後の黒ラン）の中点を（xE，yE）とすれば、
ある値θVを設定し、 yS−yE／xS−xE≧tanθV ならば、垂直ストローク、それ以外はななめ
ストロークとする。ここでtanθVの設定は任意
にできるが、通常の線図形の場合は、例えば、 θV＝80゜ 程度とすることにより、良好な結果が得られ
る。
との判別は、１例としてストロークを構成する
第６図ａ第ｉランおよび第（ｉ＋ｋ）ランの位
置関係より、求めることができ。即ち、始ラン
（最初の黒ラン）の中点を（xS，YS）終ラン
（最後の黒ラン）の中点を（xE，yE）とすれば、
ある値θVを設定し、 yS−yE／xS−xE≧tanθV ならば、垂直ストローク、それ以外はななめ
ストロークとする。ここでtanθVの設定は任意
にできるが、通常の線図形の場合は、例えば、 θV＝80゜ 程度とすることにより、良好な結果が得られ
る。
(ハ) 第７ａ図に示すように、水平ランと非水平ラ
ンが接続している場合、 順次走査をくり返し、スキヤンリストを更新
し第２走査線のスキヤンリストに第ｉランが、
第１走査線のスキヤンリストに第（ｉ−１）ラ
ンが現れた場合、まず第（ｉ−１）ランで水平
ストロークが終了したと判断し、そのストロー
クリスト記憶部７ａのそのストロークの更新を
終了する。そして、第ｉランより新たに垂直ス
トロークあるいはななめストロークが現われた
と判断し、第ｉランのｙ座標および始点および
終点のｘ座標をランリスト記憶部７ｃに登録す
る。
ンが接続している場合、 順次走査をくり返し、スキヤンリストを更新
し第２走査線のスキヤンリストに第ｉランが、
第１走査線のスキヤンリストに第（ｉ−１）ラ
ンが現れた場合、まず第（ｉ−１）ランで水平
ストロークが終了したと判断し、そのストロー
クリスト記憶部７ａのそのストロークの更新を
終了する。そして、第ｉランより新たに垂直ス
トロークあるいはななめストロークが現われた
と判断し、第ｉランのｙ座標および始点および
終点のｘ座標をランリスト記憶部７ｃに登録す
る。
さらに、この２種のストロークの接続関係を
表現するため「ノード」という概念を用い、ノ
ードリスト記憶部７ｂにそのノードの座標と、
そのノードで接続するストロークとを登録す
る。抽出されたストロークとノードは第７図ｂ
に示すようになる。ここで、ノードの座標とし
て上記第ｉランに現われた黒ランのほぼ中心相
当位置を用いている。
表現するため「ノード」という概念を用い、ノ
ードリスト記憶部７ｂにそのノードの座標と、
そのノードで接続するストロークとを登録す
る。抽出されたストロークとノードは第７図ｂ
に示すようになる。ここで、ノードの座標とし
て上記第ｉランに現われた黒ランのほぼ中心相
当位置を用いている。
(ニ) 第８図ａに示すように非水平ランと水平ラン
が接続している場合、 順次走査をくり返し、スキヤンリストを更新
し第２走査線のスキヤンリストに第ｉランが、
第１走査線のスキヤンリストに第（ｉ−１）ラ
ンが現われた場合、まず第（ｉ−１）ランの情
報をランリスト記憶部７ｃに登録し、第（ｉ−
１）ランで垂直あるいはななめストロークが終
結したと判断し、このストロークを構成するラ
ンリスト記憶部の情報より、それが垂直ストロ
ークがななめストロークか雑音かを判別し、ス
トロークリスト記憶部７ａにそのストロークの
種類と始点および終点座標を登録する。さら
に、第２走査線のスキヤンリストにある第ｉラ
ンから水平ストロークが始まると判断し、スト
ロークリストに第ｉランのストロークの種類、
ｙ座標、始点および終点のｙ座標を登録する。
同時にこの２種のストロークの接続関係を表わ
すため、ノードリスト記憶部７ｂにそのノード
の座標すなわち第（ｉ−１）ランの中心相当位
置座標とそのノードに接続するストロークとを
登録する。これにより第８図ｂのようにストロ
ークとノードが抽出される。
が接続している場合、 順次走査をくり返し、スキヤンリストを更新
し第２走査線のスキヤンリストに第ｉランが、
第１走査線のスキヤンリストに第（ｉ−１）ラ
ンが現われた場合、まず第（ｉ−１）ランの情
報をランリスト記憶部７ｃに登録し、第（ｉ−
１）ランで垂直あるいはななめストロークが終
結したと判断し、このストロークを構成するラ
ンリスト記憶部の情報より、それが垂直ストロ
ークがななめストロークか雑音かを判別し、ス
トロークリスト記憶部７ａにそのストロークの
種類と始点および終点座標を登録する。さら
に、第２走査線のスキヤンリストにある第ｉラ
ンから水平ストロークが始まると判断し、スト
ロークリストに第ｉランのストロークの種類、
ｙ座標、始点および終点のｙ座標を登録する。
同時にこの２種のストロークの接続関係を表わ
すため、ノードリスト記憶部７ｂにそのノード
の座標すなわち第（ｉ−１）ランの中心相当位
置座標とそのノードに接続するストロークとを
登録する。これにより第８図ｂのようにストロ
ークとノードが抽出される。
なお上記(イ)〜(ニ)の処理における、ストロークリ
スト記憶部７ａ、ノード記憶部７ｂ、ランリスト
記憶部７ｃとの入出力処理は、リスト処理部が行
なう。
スト記憶部７ａ、ノード記憶部７ｂ、ランリスト
記憶部７ｃとの入出力処理は、リスト処理部が行
なう。
以上本実施例によれば例えば、A4版の原図形
を副走査８本／mmで走査する場合、原図形の全画
像データを蓄積する方法に較べて本方式は約１／
1200の画像データ蓄積容量で済むことになり、低
コストの装置を実現することができる。
を副走査８本／mmで走査する場合、原図形の全画
像データを蓄積する方法に較べて本方式は約１／
1200の画像データ蓄積容量で済むことになり、低
コストの装置を実現することができる。
なお本実施例においては基本的部分を説明した
が、実際の場合には第９図に示すように水平ラン
の最初および最後に短かい黒ランが検出されるこ
とが多い。そのような黒ランは一旦は非水平ラン
としてランリストに登録されるが、一定走査線数
以上続いて出現しない場合はノイズと見倣してそ
の情報を捨てる。例えば２本以内の黒ランの連続
はノイズとして捨てても、本方式によるストロー
ク抽出に何等悪影響を与えないばかりでなく、ノ
イズ成分が少なくなり良好な結果が得られる。
が、実際の場合には第９図に示すように水平ラン
の最初および最後に短かい黒ランが検出されるこ
とが多い。そのような黒ランは一旦は非水平ラン
としてランリストに登録されるが、一定走査線数
以上続いて出現しない場合はノイズと見倣してそ
の情報を捨てる。例えば２本以内の黒ランの連続
はノイズとして捨てても、本方式によるストロー
ク抽出に何等悪影響を与えないばかりでなく、ノ
イズ成分が少なくなり良好な結果が得られる。
また、本実施例では１走査線上に単一の黒ラン
が存在する場合を述べたが、１走査線上に複数の
黒ランが存在する場合にも全く同様にストローク
を抽出することができる。
が存在する場合を述べたが、１走査線上に複数の
黒ランが存在する場合にも全く同様にストローク
を抽出することができる。
発明の効果
以上に述べたように本発明は、原図形の読取と
同時に一走査線の走査毎にその走査線内の黒ラン
の情報を座標値データに変換し、黒ランの始点お
よび終点の座標値から成るスキヤンリストを蓄積
するスキヤンリスト記憶部を主たる記憶部として
設けるだけで、線図形を構成する水平ストロー
ク、垂直ストローク、ななめストロークとそれら
の接続関係を抽出することができ、従来の装置に
比べ蓄積容量が少なくて済み、データ量も少な
く、高効率で高速の処理ができるという効果があ
る。
同時に一走査線の走査毎にその走査線内の黒ラン
の情報を座標値データに変換し、黒ランの始点お
よび終点の座標値から成るスキヤンリストを蓄積
するスキヤンリスト記憶部を主たる記憶部として
設けるだけで、線図形を構成する水平ストロー
ク、垂直ストローク、ななめストロークとそれら
の接続関係を抽出することができ、従来の装置に
比べ蓄積容量が少なくて済み、データ量も少な
く、高効率で高速の処理ができるという効果があ
る。
また、一連の処理のうち最も図形入力部分に近
い部分において、画像データを、ストロークとそ
の接続関係という符号化され圧縮された情報に変
換するので、従来の細線化を行なう手法などと比
較して全体の処理速度を大幅に短縮することが可
能である。
い部分において、画像データを、ストロークとそ
の接続関係という符号化され圧縮された情報に変
換するので、従来の細線化を行なう手法などと比
較して全体の処理速度を大幅に短縮することが可
能である。
第１図は本発明の一実施例における線図形のス
トローク抽出装置のブロツク結線図、第２図は水
平ランと非水平ランの区別を示す図、第３図は黒
ラン相互の接続関係を示す図、第４図は黒ランの
接続関係の基本を示す図、第５図は水平ラン相互
の接続関係から水平ストロークの抽出を示す図、
第６図は非水平ラン相互の接続関係から非水平
（垂直またはななめ）ストロークの抽出を示す図、
第７図は水平ランに非水平ランが続きノードを形
成する場合の抽出方法を示す図、第８図は非水平
ランに水平ランが続きノードを形成する場合の抽
出を示す図、第９図は水平ランにノイズ的な非水
平ランが続く場合を示す図である。 １……読取部、２……スキヤンリスト生成部、
３……スキヤンリスト記憶部、４……パターン処
理呼出部、５……パターン処理部、６……リスト
処理部、７ａ……ストロークリスト記憶部、７ｂ
……ノードリスト記憶部、７ｃ……ランリスト記
憶部。
トローク抽出装置のブロツク結線図、第２図は水
平ランと非水平ランの区別を示す図、第３図は黒
ラン相互の接続関係を示す図、第４図は黒ランの
接続関係の基本を示す図、第５図は水平ラン相互
の接続関係から水平ストロークの抽出を示す図、
第６図は非水平ラン相互の接続関係から非水平
（垂直またはななめ）ストロークの抽出を示す図、
第７図は水平ランに非水平ランが続きノードを形
成する場合の抽出方法を示す図、第８図は非水平
ランに水平ランが続きノードを形成する場合の抽
出を示す図、第９図は水平ランにノイズ的な非水
平ランが続く場合を示す図である。 １……読取部、２……スキヤンリスト生成部、
３……スキヤンリスト記憶部、４……パターン処
理呼出部、５……パターン処理部、６……リスト
処理部、７ａ……ストロークリスト記憶部、７ｂ
……ノードリスト記憶部、７ｃ……ランリスト記
憶部。
Claims (1)
- 【特許請求の範囲】 １ ２次元平面上に表現される２次元線図形をラ
インスヤナなどの線走査により観測しながら観測
値を順次２値化処理する読取手段と、前記２値化
処理により生成された白画素、黒画素を表現する
２値化データを一走査線上で連続する黒画素の集
合毎に、上記２次元平面上における始点と終点の
座標値データに変換する処理、および一走査線上
に存在する上記連続する黒画素の集合の数を計数
する処理とを行なうスキヤンリスト生成手段と、
前記スキヤンリスト生成手段により生成された座
標値データと連続する黒画素の集合の数とを、最
新のものから２走査線分記憶するスキヤンリスト
記憶部と、前記スキヤンリスト記憶部に記憶され
ているデータをもとに、隣接する２本の走査線上
にある、一走査線上で連続する黒画素の集合の長
さと、前記連続する黒画素の隣接する２本の走査
相互の接続関係とを調べ、あらかじめ設定された
接続パターン毎に処理を振り分けるパターン処理
呼出手段と、前記パターン処理呼出手段により起
動され、各接続パターンより、図形を構成する線
部分であるストロークとストローク相互間の接続
部分を表わすノードとを生成してパターン処理を
行なうパターン処理手段とを具備し、前記２走査
線分の一走査線で連続する黒画素の集合の始点と
終点の座標値データと一走査線上に存在する前記
連続する黒画素の集合の数とを一走査線分更新
し、上記パターン毎に処理を振り分け、パターン
処理を行なうことを反復することによつて、図形
を構成する線部分として、水平、垂直、ななめの
３種のストロークとその接続関係を抽出すること
を特徴とする線図形のストローク抽出装置。 ２ パターン処理手段は図形を構成する線部分で
あるところのストロークの始点および終点の座標
とストロークの種類とを登録するストロークリス
ト記憶部と、ストローク相互間の接続部分を表わ
すノードの座標、およびそのノードで接続するス
トロークを登録するノードリスト記憶部と、垂直
あるいは、ななめのストロークを構成すると考え
られている一連の黒画素の集合の始点、および終
点の座標を登録するランリスト記憶部と、各パタ
ーン毎に前記ストロークリスト記憶部、前記ノー
ドリスト記憶部、および前記ランリスト記憶部の
データを操作するリスト処理手段とを具備する特
許請求の範囲第１項記載の線図形のストローク抽
出装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57214354A JPS59103178A (ja) | 1982-12-06 | 1982-12-06 | 線図形のストロ−ク抽出装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57214354A JPS59103178A (ja) | 1982-12-06 | 1982-12-06 | 線図形のストロ−ク抽出装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS59103178A JPS59103178A (ja) | 1984-06-14 |
| JPH022189B2 true JPH022189B2 (ja) | 1990-01-17 |
Family
ID=16654381
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP57214354A Granted JPS59103178A (ja) | 1982-12-06 | 1982-12-06 | 線図形のストロ−ク抽出装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS59103178A (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6345687A (ja) * | 1986-08-13 | 1988-02-26 | Yokogawa Electric Corp | デイジタル画像の線分抽出方法 |
| JP4262471B2 (ja) | 2002-11-12 | 2009-05-13 | 富士通株式会社 | 生体特徴データ取得装置 |
| JP4692109B2 (ja) * | 2005-07-04 | 2011-06-01 | セイコーエプソン株式会社 | 画像傾き検出方法、画像傾き検出装置および画像傾き検出プログラム |
-
1982
- 1982-12-06 JP JP57214354A patent/JPS59103178A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS59103178A (ja) | 1984-06-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2940936B2 (ja) | 表領域識別方法 | |
| JPH0772861B2 (ja) | プログラム作成装置 | |
| JPH05342408A (ja) | 文書画像ファイリング装置 | |
| JPH022189B2 (ja) | ||
| JPH0656618B2 (ja) | 画像情報の文字・図形分離方法 | |
| JP2789622B2 (ja) | 文字／図形領域判定装置 | |
| Ablameyko et al. | Automatic/interactive interpretation of color map images | |
| JP2507949B2 (ja) | 文字／図形領域判定装置 | |
| JP3104355B2 (ja) | 特徴抽出装置 | |
| JP3045810B2 (ja) | 二値画像処理方法および装置 | |
| JPH03269780A (ja) | 指紋データの２値化方法 | |
| JPH11120291A (ja) | パタン認識システム | |
| JP2674286B2 (ja) | 特徴抽出方式 | |
| KR100332753B1 (ko) | 화상처리장치의이미지처리방법 | |
| JPH0540848A (ja) | 文書画像の領域抽出方法 | |
| JP2659377B2 (ja) | 文字認識方法 | |
| JPS63157287A (ja) | 文字パタ−ン抽出方法 | |
| JP2650903B2 (ja) | 文字認識装置における標準パターン記憶方法及び装置 | |
| JPS60146380A (ja) | 文字認識装置 | |
| JPH03268181A (ja) | 文書読み取り装置 | |
| JP2575402B2 (ja) | 文字認識方法 | |
| Ablameyko et al. | Hierarchical vector representation of document images | |
| JPH06168358A (ja) | ファジィテンプレート作成装置 | |
| JPH0495180A (ja) | 線分・曲線認識方式 | |
| JPH0421911B2 (ja) |