JPH0664607B2

JPH0664607B2 - 直線抽出装置

Info

Publication number: JPH0664607B2
Application number: JP61034393A
Authority: JP
Inventors: 信一郎岡▲崎▼
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1986-02-18
Filing date: 1986-02-18
Publication date: 1994-08-22
Anticipated expiration: 2009-08-22
Also published as: JPS62191988A

Description

【発明の詳細な説明】（産業上の利用分野）本発明は文書図面を走査して入力された画像を認識する
文書図面認識方式に係わり、特に入力画像中から文字や
線図形を構成する直線成分を抽出する直線抽出方式に係
わる。

（従来の技術）計算機の普及に伴い、より効果的に計算機を利用する技
術の一つとして、我々の身の回りに氾濫する多くの文書
図面を計算機へ自動的に入力する文書図面認識技術の重
要性が高まっている。文書図面画像の認識においては、
文字や線図形を構成する直線あるいは線分を抽出するこ
とが多くの後続する処理の基礎となっており、文書図面
画像中の直線や線分を漏れることなく且つ精度良く抽出
する方式の確立が重要な課題である。

従来用いられてきた代表的な直線抽出方式としては、画
像を細線化した後、細線化画像を追跡し、交点や分岐点
あるいは傾きが変化する点といった特徴点ごとに分割し
て折れ線近似を行い、ベクトル情報に変換する方式が知
られている（例えば昭和58年度電子通信学会総合全国大
会論文集1150）。また細線化を必要としない方式として
は、線画像の両側の輪郭を同時に追跡し、傾きの変化や
交点、分岐点の存在を考慮しながら両側輪郭の中心をベ
クトル化することによって線分を検出する方式がある
（例えば昭和58年度電子通信学会総合全国大会論文集11
53）。

（発明が解決しようとする問題点）画像の細線化の後折れ線近似する方式は画像の細線化時
に生ずる「ヒゲ」や「切れ」のために、本来意図しない
直線が発生したり、一つの直線が分断される問題点があ
った。またベクトル化処理では、直線性を有する連結画
素を特徴点において分割して抽出するが、特徴点の存在
を局所的にのみ判断するため、局所的な画像の変動に影
響され易く線分の抽出が不安定となる欠点があった。一
方、直線の両側の輪郭を同時に追跡しながら特徴点ごと
に分割して線分を抽出する方式は、前記方式の細線化に
伴う問題点は解消されるが、特徴点間を折れ線近似する
原理は同じであるため、局所的な線方向や線幅の変動に
影響されやすい欠点は解消されない。更に、両側輪郭の
追跡状況から分岐点や交点の存在を判断する必要がある
ため、処理が複雑になる問題点があった。

本発明の目的は、上記の問題点を解決すべく、線幅や局
所的な直線方向の揺らぎに影響されにくく、且つ単純な
処理で実現可能な直線抽出方式を提供することにある。

（問題点を解決するための手段）本発明の直線抽出装置は、紙面上に記録された文書図面
を走査して入力された画像の微小な局所領域ごとの局所
パターンを所定の方向線素に分類した識別情報および該
局所パターンの角度を抽出する局所パターン識別手段
と、前記局所パターン識別手段によって抽出された識別
情報と角度および角度分類情報並びに線素連結情報から
成る線素情報を記憶する線素記憶手段と、入力される識
別情報又は識別情報と角度分類情報の組み合わせに一致
する線素情報群を前記線素記憶手段から取り出す線素読
み出し手段と、前記線素読み出し手段によって読み出さ
れた線素情報群の角度に基づいて分類を行い角度分類情
報を出力する角度分類手段と、前記線素読み出し手段に
よって読み出された線素情報群の識別情報と角度分類情
報を基に画像上で連結する線素群を抽出し、線素に連結
する線素情報の識別子である線素連結情報を線素記憶手
段へ出力する共に該線素群の代表線素を線分情報記憶手
段へ出力する線素接続手段と、該代表線素と線分の特徴
値から成る線分情報を記憶する線分情報記憶手段と、前
記線分情報記憶手段に格納された代表線素と線素情報の
線素連結情報でたぐられる線素群で定まる線分の特徴値
を求め前記線分情報記憶手段へ出力する特徴量算出手段
とを備え、文書図面画像の直線成分は線分情報の代表線素と線素情
報の線素連結情報とでたぐられる線素群としてその位置
と特徴量が求められることを特徴とする。

（作用）本発明においては、入力された画像中の線分を構成する
微小な線素を局所パターン識別手段によって求めるた
め、微小領域内での局所的な線幅や線方向の変動が吸収
され、線分を構成する線素およびその方向が安定に抽出
される。更に局所パターン識別手段では分類されなかっ
た微妙に方向の異なる線分を構成する線素を、局所パタ
ーン識別手段が求めた方向値を用いて、角度分類手段が
細かく分類することによって線の方向に対する識別能力
を確保している。更に線素接続手段において、角度分類
手段が分類した線素群ごとに、二つの線素が位置する相
対的な方向が線素の方向と一致し、二つの線素の距離が
近いものほど同一線分上にあると判断することにより、
線の切れや局所的な線方向・線幅の変動に影響されない
線分抽出が行われる。

（実施例）以下本発明における実施例について図面を参照しつつ説
明する。第１図は本発明を用いた直線抽出方式の機能を
示す論理ブロック図であり、１は入力画像を得るための
画像入力手段、２は該入力画像の微小な局所領域ごとに
局所パターンを所定の方向線素に分類した識別情報およ
び該局所パターンの角度を抽出する局所パターン識別手
段、３は該局所パターン識別手段２によって抽出された
識別情報と角度および角度分類情報並びに線素連結情報
から成る線素情報を記憶する線素記憶手段、４は制御部
９によって指定された特性を持つ線素情報群を該線素記
憶手段３から取出す線素読出し手段、５は該線素読出し
手段４によって読出された線素情報群の角度に基づいて
分類を行い角度分類情報を出力する角度分類手段、６は
前記線素読出し手段４によって読出された線素情報群の
識別情報と角度分類情報より画像上で連結する線素群と
して線分を検出し線素連結情報および該線素群の代表線
素を出力する線素接続手段、７は該代表線素と線分の特
徴値から成る線分情報を記憶する線分情報記憶手段、８
は該線分情報記憶手段７に格納された代表線素によって
示される線分の特徴値を求め線分情報記憶手段７へ出力
する特徴量算出手段、９は画像入力手段１ないし特徴量
算出手段８を制御する制御部である。

画像入力手段１によって入力された文字図形を含む入力
画像は、まず局所パターン識別手段２によって所定の方
向線素に分類される。局所パターン識別手段２は相異な
る方向を持つ線素の方向基本パターンを有し、該入力画
像の微小領域ごとにその内部の局所パターンを予め設定
された方向基本パターンのいづれかに分類することによ
って線分を構成する方向線素を抽出し、分類された方向
基本パターンに対応する番号または記号である識別子を
求める。線分上の局所領域についてはいづれかの方向基
本パターンと一致するため方向線素が求まり、交点・分
岐点といった部分の局所領域ではどの方向基本パターン
とも類似しないため方向線素は抽出されない。いずれか
に分類が可能であった方向線素について、更にその局所
パターンの角度を示す方向値を求める。更に求められた
方向線素の画像上の位置および識別子から成る識別情報
と共に局所パターンの方向値を線素記憶手段３へ格納す
る。いずれの方向線素にも分類不可能なときは該当する
局所領域に対して何も出力しない。この処理を予め設定
された画素数ずつ異なる位置の局所領域ごとに画像全体
に対して行い、画像中の全ての方向線素を抽出する。
尚、局所パターンを方向線素に分類する機能はパターン
認識技術で用いられるマッチング手法、例えば２次元相
関法やパターンの固有値展開による類似度法等の公知の
技術で実現できる。またマッチングに要する辞書を記憶
する機能は局所パターン識別手段２内にROM等の固定記
憶手段あるいは通信回線を介して書き換え可能な記憶手
段によって実現される。局所パターンの方向値を求める
方法としては、パターンのモーメントから慣性楕円の長
軸方向を求める手法などが利用できる。

線素記憶手段３は、前記局所パターン識別手段２におい
て抽出された方向線素ごとに第２図に示すデータ項目か
ら成る線素情報10を記憶する機能を有する。第２図にお
いて、線素座標は方向線素の画像上の位置座標、線素識
別子は局所パターン識別手段２によって分類された方向
基本パターンに対応した番号または記号、方向値は局所
パターン識別手段２によって算出された局所パターンの
画像上での角度、角度分類識別子は角度分類手段５によ
って得られる角度分類情報、即ち分類された集合に対応
する番号または記号である。また線素連結子は線素接続
手段６によって求まる線素連結情報であり、抽出された
直線を構成する線素群を線素記憶手段３上で結び付ける
ポインタである。線素記憶手段３中の線素情報10はそれ
が記憶されている番地（以下、線素番地と呼ぶ）によっ
て特定され、参照・書込みが行われる。

線素読出し手段４は、線素記憶手段３に記憶された方向
線素のうち、制御部９によって指定された線素識別子を
持つ方向線素の線素情報10を読出し、角度分類手段５へ
出力する機能、および指定された線素識別子と角度分類
識別子の両方を持つ方向線素の線素情報10を読出し、線
素接続手段６へ出力する機能を有する。即ち、制御部９
より指定線素識別子を受け取ると線素読出し手段４は、
線素記憶手段３に記憶されている方向線素のうち、線素
識別子の項が指定線素識別子と一致する全ての方向線素
の線素番地と方向値の組を角度分類手段５へ出力する。
また、制御部９より指定線素識別子と指定角度分類識別
子を受け取ると、線素記憶手段３に記憶された方向線素
のうち、線素識別子の項が指定線素識別子と一致し且つ
角度分類識所子が指定角度分類識別子に一致する全ての
方向線素の線素番地と線素座標の組を線素接続手段６へ
出力する。

角度分類手段５は入力された方向線素群の方向値を用い
て、類似する方向値を持つ方向線素の集合（以下類似方
向線素群と呼ぶ）に分類し、類似方向線素群に属する全
ての方向線素について、線素記憶手段３中へ同一の角度
分類識別子を書込む機能を有する。方向値に基づく分類
には統計処理で用いられるクラスタリング手法、例えば
最大距離法やアイソデータ（Isodata）法等の公知の手
法が利用できる。即ち、方向線素群［Ｓ_ｉ］（以下［］
は集合を表すものとする）の方向値について分類した結
果、Ｎ個の集合Ｃ_ｋ＝［Ｓ_kj］（ｋ＝１〜Ｎ）が得られ
たとき、Ｃ_ｋに属する方向線素Ｓ_kjの全てについて、Ｓ
_kjに対応する線素記憶手段３中の線素情報10の角度分類
識別子の項に、Ｃ_ｋに対応する番号または記号ID_ｋ（例
えば番号ｋ）を書込む。

線素接続手段６は、入力された方向線素群を同一の線分
を構成する方向線素群に分割することによって線分を抽
出する機能を有する。線素接続手段６には２つの方向線
素が同一の線分を構成するか否かを判断する手段とし
て、方向線素の相対的な位置ずれを基に、両者が同一線
分を構成する信頼性を求める位置信頼性変換手段を方向
線素識別子毎に持つ。即ち、位置信頼性変換手段は、２
つの方向線素の位置する相対的な方向と方向線素の線素
識別子に固有の向きが一致し、両者の相対的な距離が近
いほど高い信頼性を、そうでないとき低い信頼性を与え
る手段である。以下に位置信頼性変換手段を用いて同一
線分を構成する方向線素群を求める手順を示す。

1.C＝０とする。

2.C＋１を新たなＣとする。方向線素群Ｓ＝［Ｓ_ｉ］の
任意の一つＳ_ａを取り出し、集合Ａ_ｃの要素とする。ま
たＳ_ａをＳから除く。

3.S＝［Ｓ_ｉ］の各々の要素Ｓ_ｉについて以下の3.1ない
し3.3を行う。

3.1 Ｓ_ｉと集合Ａ_ｃの各要素Ｓ_cjとの信頼性Ｒ_icjを位
置信頼性変換手段により求める。

3.2 を求める。

3.3 Rmaxが予め設定された閾値Ｔを越えるならば、Ｓ
_ｉをＡ_ｃの要素に加え、Ｓ_ｉをＳの要素から除く。

4.Sが空でなければ2.から繰返す。空であれば終了。

これにより一つの線分を構成する方向線素の集合がＡ_ｉ
（ｉ＝１〜ｃ）として抽出される。次に線素接続手段６
は、各Ａ_ｉについて以下の1.ないし3.の手続きを行い、
線素記憶手段３および線分情報記憶手段７に線分を構成
する線素を連結した情報を生成する。ここでＡ_ｉの各要
素をＳ_ik，即ちＡ_ｉ＝［Ｓ_ik］（ｋ＝１〜ｎ）とする。

1.S_i1の線素番地を線分情報記憶手段７の線分情報11の
代表線素の項に書込む。

2.S_ik（ｋ＝１〜ｎ−１）の各々について以下を行う。

2.1 Ｓ_ikの線素連結子の項にＳ_ik＋１の線素番地を書
込む。

3.S_inの線素連結子の項に終了を示す記号を書込む。

これにより線分情報11の代表線素の項から最初の線素番
地を検索し、順次線素番地の示す線素情報10の線素連結
子をたどることによって、一つの線分を構成する方向線
素を参照できるデータが得られる。線素接続手段６にお
ける手続きは、マイクロプロセッサ等のプログラム可能
な処理装置により容易に実現できる。また位置信頼性変
換手段は該手続きを行う同一の処理装置上のプログラ
ム、または読出し専用記憶装置や通信回線を介して予め
内容を設定可能にした随時書込み可能型記憶装置に記憶
されたテーブル形式の数表により実現可能である。

線分情報記憶手段７は、第３図に示すデータ項目から成
る線分情報11を記憶する機能を有する。第３図におい
て、代表線素は線分を構成する方向線素群の線素番地の
一つを表すポインタであり、線素接続手段６によって書
込まれる。また線分方向値は、線分の画像上における角
度、線分長は画像上における長さ、端点座標は線分の二
つの端点の画像上の座標であり、特徴量算出手段８によ
って書込まれる。線分情報記憶手段７は線素記憶手段３
と同一の記憶装置上の特定の位置に実現されてもよい。

特徴量算出手段８は線素接続手段６によって抽出された
線分の画像上での角度、長さおよび線分の端点の座標を
算出する機能を有し、第４図に示す構成で実現される。
第４図において、最大最小算出手段12は線素座標の最大
値および最小値を求める機能、線分方向算出手段13は方
向値より線分の方向値を求める機能、線分長算出手段14
は線素座標の最大値と最小値より線分の長さを求める機
能、端点座標算出手段15は線分の２つの端点の座標を求
める機能である。特徴量算出手段８は線分情報記憶手段
７に格納された線分の各々についてその代表線素を基に
線分を構成する方向線素群の位置座標Ｘ_ｉとＹ_ｉ，方向
値Ｄ_ｉを順次読出し以下の1.ないし4.の処理を行う。

1.最大最小算出手段12は下記の式で定まるXmax,Xmin,Ym
ax,Yminを求める。

ただしＷ_ｘ,W_ｙはそれぞれ微小領域の横幅と縦幅 2.線分長算出手段14は前記1.で求めたXmax,Xmin,Ymax,Y
minを用いて下記の式で定まるＬを求める。

3.線分方向算出手段13は下記の式で定まるＤを求める。

4.端点座標算出手段15は前記1.および2.で求まるXmax,X
min,Ymax,Ymin,Dを用いて下記の式で定まる（EX1,EY1）
および（EX2,EY2）を求める。

これにより求まったD,L,EX1,EY1,EX2,EY2をそれぞれ線
分情報記憶手段７の線分方向値、線分長、端点座標の項
へ格納する。

制御部９は画像入力手段１ないし特徴量算出手段８を制
御し、以下に説明する直線抽出処理の手順を司どる機能
である。

以下に、第５図ないし第10図を用いて本直線抽出方式に
おける処理の一具体例を詳述する。

第６図（ａ）は線幅の変動のある線分を含む画像例で、
左上を原点、右方向をＸ軸、下方向をＹ軸とした座標を
設けている。一方、第５図（ａ），（ｂ），（ｃ），
（ｄ）は局所パターン識別手段２において分類に用いる
方向基本パターンの辞書と対応する線素識別子の例で、
微小領域として矩形領域をとり、４方向の線素に分類す
る場合を示している。第５図（ａ）ないし（ｄ）の左上
に付与した番号が各方向基本パターンに対応した線素識
別子である。局所パターン識別手段２は画像のＸ軸およ
びＹ軸方向に例えば２画素ずつ位置をずらしながら、５
×５画素の矩形領域ごとにこの４つの方向基本パターン
とマッチングにより比較し、最も類似するパターンを求
める。第６図（ａ）の画像が入力されると局所パターン
識別手段２は、該入力画像に対して微小矩形領域ごとに
マッチングを行い、４つの方向線素のうちで最も類似す
る方向線素の識別子と、矩形領域内のパターンの方向値
（第６図（ａ）においては時計回りが正の方向で、度単
位の角度）を求め、線素記憶手段３内に線素情報を生成
する。これによって生成されたデータが第２図の具体例
である第７図（ａ）の線素情報の線素座標と線素識別子
の項であり、他の項はこの時点では求められていない。
尚、第７図（ａ）の各線素情報の左端に記した記号A₁な
いしA₁₇は線素番地を表しており、線素番地Ｘを持つ方
向線素を以下では方向線素Ｘと呼ぶ。また第６図（ｂ）
は求めた方向線素をその線素識別子を用いて画像と対応
する位置に図示したものである。

次に制御部９は抽出された方向線素の線素識別子１ない
し４のそれぞれについて、同じ線素識別子を持つ方向線
素を方向値を用いて細分類し、類似方向線素群を求める
処理を起動する。即ち第７図（ａ）の線素情報につい
て、まず方向識別子に３を持つ方向線素を読出すよう線
素読出し手段４に指示し、線素読出し手段４は線素番地
と方向値の組、（A₁,90），（A₃,92），（A₄,94），（A
₅,90），（A₇,92），（A₈,92），（A₉,88），（A₁₁,9
0），（A₁₂,92），（A₁₄,92），（A₁₅,88），（A₁₇,9
0）を角度分類手段５へ出力する。角度分類手段５は入
力された12個の方向線素の方向値に基づいて分類を行う
が、本例では細分類の結果12個全体が一つの類似方向線
素群となる。従って線素番地A₁,A₃,A₄,A₅,A₇,A₈,A₉,
A₁₁,A₁₂,A₁₄,A₁₅,A₁₇の全ての線素情報の角度分類識別
子の項へ同一の番号１を書込む。これは方向識別子３を
持つ方向線素は詳細に方向値を調べても差異のないこと
を示す。更に方向識別子に４を持つ方向線素に対しても
同様の処理を行い、線素番地A₂,A₆,A₁₀,A₁₃,A₁₆で示さ
れた線素情報の角度分類識別子の項に同一の番号１を書
込み、方向識別子４を持つ方向線素の方向値に差異のな
いことが求まる。

角度分類手段５によって複数の方向線素群に分類される
実施例については後記する。

次に制御部９は、同じ線素識別子と角度分類識別子を持
つ方向線素群を、線分を構成する単位に分割する処理を
起動する。まず、線素識別子が３で角度分類識別子が１
である方向線素を読出すよう線素読出し手段４に指示
し、線素読出し手段４は線素番地と位置座標の組（A₁,2
0,20），（A₃,32,20），（A₄,34,20），（A₅,20,22），
（A₇,32,22），（A₈,34,22），（A₉,20,24），（A₁₁,3
2,24），（A₁₂,20,26），（A₁₄,32,26），（A₁₅,20,2
8），（A₁₇,32,28）を線素接続手段６へ出力する。第８
図は線素接続手段６が持つ位置信頼性変換手段の変換例
である。同図（ａ）は線素識別子が１の、（ｂ）は線素
識別子が２の、（ｃ）は線素識別子が３の、（ｄ）は線
素識別子が４の方向線素に対する変換値を示す。第８図
（ａ）ないし（ｄ）において、横方向はＸ座標の差dx
を、縦方向はＹ座標の差dyであり、dxとdyの交わる位置
に記された数字が２つの方向線素が同一線分上にある信
頼性の百分率を意味する。尚、第８図（ａ）と（ｃ）は
dx＝０およびdy＝０の二つについて対称であり全体の四
分の一を表している。また（ｂ）と（ｄ）はそれぞれ図
中に示した直線S₁S₂と直線S₃S₄について対称であり、全
体の半分を表している。線素接続手段６は入力された線
素番地と位置座標の組および第８図（ｃ）の位置信頼性
変換手段により、前述した手続きに従って線分を構成す
る方向線素群を抽出する。第７図（ｂ）は第３図の具体
例であり、抽出の結果線分情報記憶手段７に格納された
線分情報を示している。即ち、線分情報B₁の代表線素の
項に線素番地A₁が書込まれ、更に第７図（ａ）の線素番
地A₁の線素連結子の項にA₅が、線素番地A₅の線素連結子
の項にA₉が、線素番地A₉の線素連結子の項にA₁₂が、線
素番地A₁₂の線素連結子の項にA₁₅が、線素番地A₁₅の線
素連結子の項に終了を示すEND記号が書込まれる。また
同時に、線分情報B₂の代表線素の項に線素番地A₃が書込
まれ、第７図（ａ）の線素番地A₃の線素連結子の項にA₄
が、線素番地A₄の線素連結子の項にA₇が、線素番地A₇の
線素連結子の項にA₈が、線素番地A₈の線素連結子の項に
A₁₁が、線素番地A₁₁の線素連結子の項にA₁₄が、線素番
地A₁₄の線素連結子の項にA₁₇が、線素番地A₁₇の線素連
結子の項に終了を示すEND記号が書込まれる。これによ
り線素番地A₁,A₅,A₉,A₁₂,A₁₅で示される方向線素群およ
び線素番地A₃,A₄,A₇,A₈,A₁₁,A₁₄,A₁₇で示される方向線
素群により構成される二つの線分が抽出される。同様に
して制御部９は方向識別子に４を、角度分類識別子に１
を持つ方向線素群についても同じ処理を起動する。線素
接続手段６は方向識別子４に対応する第８図（ｄ）の位
置信頼性変換手段を用いて連結する線素群を抽出する。
その結果第７図（ｂ）の線分情報B₃に代表線素A₂を、第
７図（ａ）の線素番地A₂,A₆,A₁₀,A₁₃の線素連結子の項
にそれぞれA₆,A₁₀,A₁₃,A₁₆を、線素番地A₁₆の線素連結
子の項にEND記号を書込む。これにより線素番地A₂,A₆,A
₁₀,A₁₃,A₁₆の方向線素群により構成される線分が抽出さ
れる。制御部９はこれ以外の方向識別子と角度分類識別
子の組合せについても同様の処理を起動するが、この例
では該当する線素群はない。

最後に制御部９は特徴量算出手段８を起動し、得られた
３本の線分の特徴量を算出する処理を行う。特徴量算出
手段８はまず線分情報B₁についてその代表線素の項より
線素番地A₁を得て、順に線素連結子をたぐることによっ
て線分情報B₁に対応する方向線素群の方向値と位置座標
を読出す。前記した手順に従って線分長、線分方向値お
よび二つの端点の位置座標を求め、線分情報記憶手段７
の線分情報B₁に格納する。同様に線分情報B₂とB₃につい
ても特徴量を算出し、最終的に３つの線分に関する情報
が第７図（ｂ）に示すように求められる。

以下では第９図（ａ）の画像に対する処理を詳述する。
第９図（ａ）はわずかに傾きが異なる線分を含む画像の
例である。該画像が入力されると上述した第６図（ａ）
の場合と同様に、局所パターン識別手段２は第10図
（ａ）に示すような方向線素を抽出し、線素記憶手段３
内にA₁₈ないしA₃₂の線素番地を持つ線素情報の位置座標
と線素識別子および方向値を格納する。第９図（ｂ）は
方向線素をその線素識別子を用いて画像と対応する位置
に図示したものである。

次に線素読出し手段４は線素識別子に１を持つ方向線素
の線素番地と方向値の組を読出し、角度分類手段５へ出
力する。この場合はA₁₈ないしA₃₂全ての方向線素が該当
する。角度分類手段５は読出されてた方向線素の方向値
の集合［−10,8,−8,−10,−8,10,9,10,−8,−10,−10,
−12,10,8,8］に基づいて二つの類似方向線素群［A₁₈,A
₂₀,A₂₁,A₂₂,A₂₆,A₂₇,A₂₈,A₂₉］と［A₁₉,A₂₃,A₂₄,A₂₅,A
₃₀,A₃₁,A₃₂］を求め、前者の類似方向線素群の角度分類
識別子として１を、後者の類似方向線素群の角度分類識
別子として２を、それぞれの線素情報の角度分類識別子
の項に書込む（第10図（ａ）参照）。これにより同一の
線素識別子１を持つ方向線素でも方向値の異なる２つの
成分があることが求まる。制御部９は線素識別子に１以
外の値を持つ方向線素群についても同様の処理を起動す
るが、この例では該当する線素群は存在しない。

次に線素読出し手段４は線素識別子が１、角度分類識別
子が１である方向線素の線素番地と位置座標を読出し、
線素接続手段６へ出力する。線素接続手段６は第８図
（ａ）に示された変換を行う位置信頼性変換手段を用い
て、線分を構成する方向線素群［A₁₈,A₂₀,A₂₁,A₂₂,A₂₆,
A₂₇,A₂₈,A₂₉］を抽出する。更に線素識別子が１、角度
分類識別子が２である方向線素について、線素接続手段
６は第８図（ａ）の位置信頼性変換手段を用いて同様の
処理を行い、方向線素群［A₁₉,A₂₃,A₂₄,A₂₅,A₃₀,A₃₁,A
₃₂］が抽出される。この結果第10図（ｂ）に示される線
分情報B₄とB₅の代表線素および第10図（ａ）の線素情報
A₁₈ないしA₃₂の線素連結子が求まる。

続いて線分B₄およびB₅の特徴量を特徴量算出手段８が算
出し、第10図（ｂ）の線分情報に書込み、最終的に２本
の線分に関する情報が得られる。

以上の実施例では、局所パターン識別手段２において分
類する方向線素を４方向のパターンとしたが、８方向等
の多種にすることも可能である。この場合には線素接続
手段６中の位置信頼性変換手段の変換機能も方向線素の
種類ごとに設けておく。また局所パターン識別手段２に
おいてマッチングを行う矩形領域の大きさ（５×５画
素）やマッチングを行う位置の移動量（２画素ごと）は
ここに示した以外の値でもよく、矩形領域の大きさを粗
く又は移動量を大きくすれば大まかな線分が抽出され、
必要な精度に応じて設定が可能である。

（発明の効果）以上説明したように、本直線抽出方式は局所領域のマッ
チングにより方向線素を求めるため、線の局所的な切れ
や線幅の変動に影響されない特徴を持つ。また、従来技
術のように交点や分岐点あるいは傾きの変化する点とい
った特徴点間を折れ線近似する方式とは異なり、方向線
素の方向値と方向線素同士の位置関係により同一線分を
構成する方向線素であるか否かを判断するため、局所的
な線の方向の変動や線の切れに対しても安定して線分を
抽出することが可能である。また、多数の方向線素群の
方向値に基づいて方向線素を分類し大局的な判断を行う
ので、方向の差異の小さな連結する２つの線分を分離で
きる。更に本直線抽出方式は、細線化画像や画像の輪郭
の追跡処理における交点や分岐点の判定を必要としない
ので、処理が単純である特徴を持つ。

【図面の簡単な説明】

第１図は本発明を用いた直線抽出方式の機能を示す論理
ブロック図、第２図は線素記憶手段内の線素情報のデー
タ形式を示す図、第３図は線分情報記憶手段内の線分情
報のデータ形式を示す図、第４図は特徴量算出手段の機
能構成例を示すブロック図、第５図は局所パターン識別
手段が画像より抽出する方向線素の方向基本パターンの
例を示す図、第６図は第一の入力画像例を示す図、第７
図は第６図の画像から線分を抽出した結果を示す図、第
８図は線素接続手段が有する位置信頼性変換手段の変換
例を示す図、第９図は第２の入力画像例を示す図、第10
図は第９図の画像から線分を抽出した結果を示す図であ
る。図において、１は入力画像を得るための画像入力手段、
２は該入力画像の微小な局所領域ごとに局所パターンを
所定方向の線素に分類・記号化すると共に、該局所パタ
ーンの方向値を抽出する局所パターン識別手段、３は局
所パターン識別手段２によって抽出された結果および後
記する角度分類手段５並びに線素接続手段６の結果を記
憶する線素記憶手段、４は該線素記憶手段３から指定さ
れた特性を持つ線素を取出す線素読出し手段、５は前記
局所パターン識別手段２によって抽出された線素の方向
値に基づいて分類を行う角度分類手段、６は前記局所パ
ターン識別手段２および角度分類手段５の結果より線分
を画像上で連続する線素として検出する線素接続手段、
７は該線素接続手段６によって抽出された線分を検索す
るための情報を記憶する線分情報記憶手段、８は前記線
素接続手段６によって抽出された線分の特徴値を求める
特徴量算出手段、９は画像入力手段１ないし特徴量算出
手段８を制御する制御部である。

Claims

【特許請求の範囲】

【請求項１】紙面上に記録された文書図面を走査して入
力された画像の微小な局所領域ごとの局所パターンを所
定の方向線素に分類した識別情報および該局所パターン
の角度を抽出する局所パターン識別手段と、前記局所パ
ターン識別手段によって抽出された識別情報と角度およ
び角度分類情報並びに線素連結情報から成る線素情報を
記憶する線素記憶手段と、入力される識別情報又は識別
情報と角度分類情報の組み合わせに一致する線素情報群
を前記線素記憶手段から取り出す線素読み出し手段と、
前記線素読み出し手段によって読み出された線素情報群
の角度に基づいて分類を行い角度分類情報を出力する角
度分類手段と、前記線素読み出し手段によって読み出さ
れた線素情報群の識別情報と角度分類情報を基に画像上
で連結する線素群を抽出し、線素に連結する線素情報の
識別子である線素連結情報を線素記憶手段へ出力すると
共に該線素群の代表線素を線分情報記憶手段へ出力する
線素接続手段と、該代表線素と線分の特徴値から成る線
分情報を記憶する線分情報記憶手段と、前記線分情報記
憶手段に格納された代表線素と線素情報の線素連結情報
でたぐられる線素群で定まる線分の特徴値を求め前記線
分情報記憶手段へ出力する特徴量算出手段とを備え、文書図面画像の直線成分は線分情報の代表線素と線素情
報の線素連結情報とでたぐられる線素群としてその位置
と特徴量が求められることを特徴とする直線抽出装置。