JPS6055475A - 境界線抽出装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、紙などに印刷された、あるいは、手で画がか
れた図形・図面等の２値画像を、計算機によシ処理・認
識・理解などを行なう際の前処理として利用される境界
線を、座標点列の形で抽出する境界線抽出装置に関する
ものである。

従来例の構成とその問題点 画素の値が、０と１のみをとる２値画像において、従来
、図形（値１の部分）の形状を表現する有力な方法とし
て、その図形と背景（値０の部分）との境界を抽出し、
その境界線の特徴を記述することが多い。

以下に従来の座標点列を出力表現とする境界線抽出装置
について説明する。

第１図は、従来の境界線抽出装置の構成図を示すもので
あり、１は画像データ入力部であり、通常は、ファクシ
ミリやライン・スキャナなどの装置が用いられる。２は
画像データ記憶部であシ、画像データ入力部１で入力さ
れ２値化された対象画像１枚分のデータを全て記憶する
。３は境界線抽出部で、画像データ記憶部２のデータを
もとに、境界線上の点列を抽出する。４は境界点列記憶
部である。５は境界点列表示部である。

以上のように構成された従来の境界線抽出装置について
、以下その動作について、第３図を用いて説明する。

境界線抽出部３では、第２図のように画像データ記憶部
２の２値画像データを対象に、黒画素（値１の画素）に
ぶつかるまで、左上ずみの点６から線順次走査を行なう
。いま、点７で、黒画素にぶつかったとすると、次にこ
の点７から、常に黒画素を右手（あるいは、左手）にみ
るように、境界線上を追跡し、同時に境界点列を抽出し
ていく。

しかしながら、上記のような構成では、対象とする原画
像１枚分の全てのデータを記憶部に持たねばならず、大
容量の記憶部が必要となるという欠点がある。

発明の目的 本発明は、上記従来の問題点を解消するもので、原画保
全てのデータを蓄積する大容量の記憶部を持たなくとも
、画像の境界線を抽出できる境界線抽出装置を提供する
ことを目的とする。

発明の構成 本発明は、２次元□平面上に表現される画像を例えばフ
ァクシミリやラインスキャナなどの装置により１走査線
分ずつ順次２値化処理する画像データ入力部と、上記画
像データを少なくとも２走査線分一時的に記憶する一時
記憶部と、上記一時記憶内の画像データ中、上下左右に
互いに隣接する４画素を取出し、そのパターンを調べ、
境界線上の隣接する２点である境界線素を抽出する境界
線素抽出部と、境界線素を順次接続し、境界線素塊を生
成する境界線素接続部と、境界線素塊同志の接続を行な
う境界線素塊接続部を備えた境界線抽出装置であり、一
時記憶部の２走査線分の画像データを次々と処理するこ
とにより、すなわち、隣接する２本の走査線分のデータ
についての処理が終わると、そのうち古い走査線分の画
像データを捨て、新しい１本の走査線分のデータを取り
込み処理することによシ、原画像データ全てを蓄積する
記憶部を持たずして、境界線抽出ができるものである。

実施例の説明 以下、本発明の一実施例について、第３図〜第１１図を
参照しながら説明する。　− 第３図は、本発明の一実施例における図形の境界線抽出
装置の構成図である。なお、本実施例では、８連結性を
もつ境界線が抽出できる。なお、８連結性をもつ境界線
とは、境界線上の任意の１点と境界線上でその点と隣合
う点の位置関係が第４図に示す８通シの中のいずれかで
あるような関係をもつ境界線である。

以下、第３図に従って説明する。

第３図において、８は画像データ入力部であり、２次元
平面上の画像を一走査線分ずつ入力し、”ｏ”か１”か
の２値情報に変換する。９は一時記憶部であり、画像デ
ータ入力部８で最も最近入力された２走査線分のデータ
を記憶する。１ｏは境界線素抽出部であり、一時記憶部
９に蓄積されている２ライン分のデータを左から順次、
第５図で示したかたちで４画素ずつ取り出し、４画素の
パターンを調べ、境界線素を抽出する。１１は境界線素
接続部で、境界線素抽出部１ｏで得られた境界線素と、
既に境界線素抽出部１０で得られた境界線素によ多形成
されている境界線素塊を接続し、新しい境界線素塊を生
成する。１２は境界線素塊記憶部である。１３は境界線
素塊接続部で、境界線素接続部１１で形成される境界線
素塊の端点を調べ、接続可能な別の境界線素塊を見つけ
出し、接続情報を両方の境界線素塊に付加する。１４は
境界点列生成部で、境界線素塊接続部１３で境界線素塊
に付加された接続情報をもとに、境界点列を生成する。

１５は境界点列記憶部である。１６は境界点列表示部で
、境界点列生成部１４で得られた境界点列を表示する。

上記のように構成された装置において、以下その動作を
各処理部毎に説明する。

■　画像データ入力部８及び一時記憶部９第６図（、）
　、　（ｂ）を用いて説明す゛る。

画像データ入力部８では、第６図（−）のように、被処
理画像の１番目ラインから順次１ラインずつ入力し、一
時記憶部９に格納する。いま、ｊ番目ラインが入力され
た場合、一時記憶部９には、Ｎ−１）番目ラインとｊ番
目ラインが格納される。同様にＮ＋１）番目ラインが入
力されると、第６図（ｂ）のように、一時記憶部９には
、ｊ番目ラインとＮ＋１）番目ラインか格納され、（ト
１）番目ラインのデータは、捨てられる。

■　境界線素抽出部１ｏと境界線素接続部１１境界線素
抽出部１ｏについて、第７図を用いて説明する。

いま第７図のように一時記憶部９に１番目ラインとＮｅ
１）番目ラインの画像データが入っているとする。この
時、一時記憶部９の左端から縦２画素×横２画素の正方
形を形成する４画素を取出し、次に説明する境界線素抽
出処理、及び、境界線素接続処理をほどこす。この４画
素に対する境界線素抽出処理、境界線素接続処理が終っ
たなら、第７図のように１画素だけ右隣にずらして得ら
れる４画素を取出し、境界線素抽出処理、境界線素接続
処理をほどこす。以後、一時記憶部９の右端の４画素に
対するまで、同様の処理を繰返す。

（ａ）境界線素抽出部１０ 第８図ａ、ｂを用いて説明する。

一時記憶部９より取出された正方形の４画素には、第８
図すに示すように１６種類のパターンがある。

捷ず、取り出された４画素に対して、式（１）の重みう
け割算をし、パターン番号を決定する。

今、４画素の値を第８図ａに示すように、ｅｉ、ｊ　＋
８ｉ＋ｉ、ｊ　”ｉ、ｊ＋１　ｌｅｉ＋１．ｊ＋４　と
すると１パタ一ン番号−ｅｉ、ｊ＋２ｅｉ＋１．ｊ”ｅ
ｉ、ｊ＋１＋８ｅｉ＋１．ｊ＋１°°（１）とする。

（１）式より、取り出された４画素のパターンは、−意
に定まる。なお、添字ｉ、ｌは、画素の位置するＸ座標
、ｙ座標を意味する。

さて、第８図すに示すように、パターン番号に対応して
、パターンの種類を示しだパターン種と、以降の処理で
必要となる親座標・子座標・カットフラグの情報が用意
されている。従ってパターン番号のわかった４画素には
、パターン種、親座標、子座標、カットフラグの情報が
、付加される。

（ｂ）　境界線素接続部 境界線素接続部では、注目している４画素に付加された
パターン種の情報により、次の４つの処理に別れる。

：）パターン種が０の場合 何も処理しない。

１１）パターン種が１の場合 第９図ａを用いて説明する。

正順境界線素塊が、まだ１つも生成されていない場合は
、境界線素抽出部１ｏで得られる親座標と子座標より正
順境界線素塊を作る。この際、親座標・子座標の順で左
づめに格納する。

上記以外の場合は、既に生成されておシ、まだ成長停止
フラグのついていない正順境界線素塊の右端の座標を調
べ、境界線素抽出部１ｏで得られた親座標と一致するも
のがあるか否かを調べる。一致するものがない場合は、
親座標、子座標により新しい正順境界線素塊を作る。一
致するものがある場合は、一致するものの右隣シに子座
標を格納し正順境界線素塊を成長させる。

ただし、カット・フラグが１であれば、これ以上、正順
境界線素塊を成長させないように成長停止フラグをその
正順境界線素塊に付加する。

１１１）パターン種が２の場合 第９図すを用いて説明する。

逆順境界線素塊が、まだ１つも生成されていない場合は
、境界線素抽出部１ｏで得られる親座標と子座標より正
順境界線素塊を作る。この際、親座標と子座標の順で右
づめに格納する。

上記以外の時は、既に生成されており、成長停止フラグ
の付いていない逆順境界線素塊の左端の座標を調べ、境
界線素抽出部１ｏで得られた親座標と一致するものがあ
るか否かを調べる。

一致する逆順境界線素塊がある場合、次にカット・フラ
グを調べ、０なら子座標を、その逆順境界線素塊の左端
に付加する。もしカットフラグが１なら、その逆順境界
＃ｉ！素塊に成長停止フラグを付加し、親座標と子座標
で新しい逆順境界線素塊を生成する。また、親座標と一
致する左端点をもつ逆順境界線素塊がない場合も、親座
標と子座標で新しい逆順境界線素塊を生成する。その際
、親座標・子座標の順で右づめに格納する。

ｉｖ）　パターン種が３の場合 パターン種が１の場合の処理と同じ処理を行ない、続い
て、パターン種が２の場合の処理と同じ処理を行なう。

■　境界線素塊接続部１３ １番目ラインと（ト１）番目ラインの全ての４画素に対
する境界線素抽出処理と境界線素接続処理が終了した時
点で各境界線素塊の右端点の座標を調べる。端点のｙ座
標がｊであれば、その右端点は、同じＸ座標・ｙ座標を
もつ他の境界線素塊の左端点と接続できる。ある境界線
素塊の右端点に対して接続可能な左端点をもつ他の境界
線素塊が１本ある場合は、その境界線素塊同志をその端
点を介して接続する。接続可能な左端点をもつ境界線素
塊が複数（最大２本）ある場合は、以下の処理をほどこ
す。

まず、注目している境界線素塊の右端点とその隣の点に
ついて、隣の点から右端点への方向を調べる請求める境
界線が８連結であるので、方向には、第１０図ａに示す
８つの数値のいずれかが割当てられる。割シ当てだ数値
をＤｌとする。次に接続可能な２本の境界線素塊の左端
点とその隣の点について左端点から隣の点への方向を各
々、同様に調べ、この各方向に対して割当てだ数値を各
々Ｄ２　、　Ｄ３　とする。

さて、第１０図すのフローチャートを用いて説明する。

Ｄｌに１を加算したものを２で割り小数点以下を切捨て
る。この値を２倍し、１を加算したものをＤとする（図
中口）。もしＤが８よシ犬ならば（図中）・）、Ｄを１
とする（図中二）。ＤとＤ２が等しければ（図中ホ）、
Ｄ２をもつ境界線素塊が、Ｄｌをもつ境界線素塊と接続
する（図中へ）。ＤとＤ３が等しければ（図中ト）、Ｄ
３をもつ境界線素塊が、Ｄｌをもつ境界線素塊と接続す
る（図中チ）。Ｄが、Ｄ２でもＤ３でもない場合、Ｄか
ら１減算したものをＤとする（図中ヌ）。この時、Ｄが
０々ら（図中ル）、Ｄを８としく図中オ）、図中ホヘ戻
る。

上記より、ある境界線素塊に対して接続可能な境界線素
塊が２本ある場合も処理できる。

全てのラインに対して、上記の処理をほどこすことによ
シ、第１１図に示すように各境界線素塊の接続情報が得
られる。各境界線素塊の両端に他の境界線素塊との接続
情報が付加され、境界線素塊記憶部１２に記憶される。

■　境界点列生成部１４ 境界点列生成部１４は、境界線素塊記憶部１２から読み
出した接続情報をもとにして、境界点列を生成する。

なお、本実施例では、孤立点の処理について記述してい
ないが、孤立点も第８図すのパターン番号１，２，４．
．８のパターンより抽出することは可能である。寸だ、
本実施例では、一時記憶部に２走査線分の２値画像デー
タを格納するとしだが、一時記憶部を拡張し、３走査線
分の２値画像データを格納可能としておけば、輪郭線抽
出処理と入力処理を並列に行なうことが可能で、全体の
処理速度が向上する。

発明の効果 本発明の境界線抽出装置は、画像データ入力部と一時記
憶部と境界線素抽出部と境界線素接続部と境界線素塊接
続部を設けることにより、全画像データを持たずして、
境界線が抽出でき、その実用的効果は大きい。

【図面の簡単な説明】

第１図は従来の境界線抽出装置の構成を示すブロック図
、第２図は従来の境界線抽出装置の動作説明図、第３図
は本発明の一実施例における境界線抽出装置の構成を示
すブロック図、第４図は８連結性を示す図、第５図は一
時記憶部から読み出される２値情報の処理対象単位を示
す図、第６図は対象画像と一時記憶部の関係を示す図、
第７図は境界線抽出部の動作説明図、第８図は４画素か
ら生じるパターン図、第９図は境界線素接続部の動作説
明図、第１０図は境界線素塊接続部の動作説明図、第１
１図は境界点列生成部の動作説明図である。 ８・・・・・・画像データ入力部、９・・・・・・一時
記憶部、１０・・・・・・境界線素抽出部、１１・・・
・・・境界線素接続部、１２・・・・・・境界線素塊記
憶部、１３・・・・・・境界線素塊接続部、１４・・・
・・・境界点列生成部。 代理人の氏名　弁理士　中　尾　敏　男　ほか１名第１
図 一一呻デプっ流れ 第２図 メ１７’（黒山糸ＢＦ分）　５１景（白画素音し外）３
図 第４図 メ匹理則１−最小早筐とな３４面東　−ｑ　犯＠、ｙｐ
第６図 Ｃα） （ｂン 一時記便、耶 第７図 第８図 （１１〕 （ｂ） 第　８　面 （ｂ）　（綺」ン 第９図 （０−） 第９図 （い 叫り一旦 ■ 記１０図 梼） 第１１図

Claims (1)

【特許請求の範囲】
1. ２次元平面上に表現される画像を線順次走査により一走
   査線分ずつ入力し２値化し、２値画像データを得る画像
   データ入力部と、上記２値画像データを少なくとも２走
   査線分一時的に記憶する一時記憶部と、上記一時記憶部
   内の２値画像中で上下左右に互いに隣接する４画素を取
   シ出し、そのパターンを調べ２値画像の境界線上の隣接
   する２点である境界線素を抽出する境界線素抽出部と、
   境界線素を順次接続し境界線素塊を生成する境界線素接
   続部と、境界線素塊を記憶する境界線素塊記憶部と、境
   界線素塊同志の接続を行なう境界線素塊接続部と、上記
   境界線素塊接続部より得られた情報をもとに境界点列を
   生成する境界点列生成部を具備し、上記２走査線分の２
   値画像データを順次、蓄積・更新することによシ、対象
   ２値画像の境界線を抽出することを特徴とした境界線抽
   出装置。