JPH0624020B2 - ディジタル画像の塗り潰し領域検出方法 - Google Patents

Description

【発明の詳細な説明】 ＜産業上の利用分野＞ 本発明は、与えられたディジタル画像データより画像内
の塗り潰し部分を効率良く抽出するディジタル画像の塗
り潰し領域検出方法に関するものである。

＜従来の技術＞ ＯＡ（Office Automation）、ＣＡＤ（Computer Aide
d Design）等の普及により図面の自動読み取りを目的
とした図面認識に対する研究、開発が最近盛んに行なわ
れている。

図面認織では、ディジタル画像としての図面データをベ
クトル構造等の数値データに一旦変換してから解析する
ことが一般的である。この際、電気回路図に代表される
ような図面では、第13図に示すように、通常の線図形部
の分岐点を示す黒丸ａ、ダイオードの一部を形成する三
角形部ｂ等の黒画素塗り潰し部分が混在しているため、
予め両者を効率良く分離し、抽出する必要がある。

従来のディジタル画像の塗り潰し部分の抽出方法は、細
線化処理を伴うものとして次に説明するような処理手順
によるものが知られている。即ち、 第14（ａ）に示すような原ディジタル画像に対し
て、例えば「細線化法についての諸考察」（田村；電子
通信学会技術研究報告，ＰＲＬ75−66，1975）等の文献
に記載されているHildithの細線化法を用いて標準の線
幅が１画素の図形になるまで細線化を行ない、第14図
（ｂ）に示す線図形部と塗り潰し領域が混在した細線化
画像を得る。

得られた細線化画像に対して、３画素×３画素のマ
スク・パターンを用いて、輪郭点抽出処理を施し、第14
図（ｃ）に示す輪郭点抽出画像を細線化画像とは別に生
成する。

得られた輪郭点抽出画像上で線分追跡を行ない、ベ
クトル・データを作成する。

ベクトル相互間の位置関係からベクトルを辿ること
により、全てのループｌ_１〜ｌ_５を検出する。

輪郭点抽出画像上で検出された全てのループｌ_１〜
ｌ_５について、第14図（ｂ）に示す細線化画像上の対応
する位置の各ループ内の黒画素の有無を調べ、塗り潰し
領域か否かを判別する。

以上の処理手順に従って、原ディジタル画像における塗
り潰し領域を抽出する。

＜発明が解決しようとする問題点＞ しかしながら、上記した従来の方法では、画像上の全て
のループについてループ内の黒画素の有無を調べる必要
があるため、ゲート、フリップ・フロップ等のループを
構成するシンボルが塗り潰し領域に比較して数多く含ま
れる電気回路図のような図面に対しては、手間がかか
り、塗り潰し領域を効率良く抽出することができない。

また、従来の方法では、細線化画像を保持するための、
既存の画像メモリの他に輪郭点抽出画像を一時格納する
ための画像メモリをもう１枚別に設ける必要があり、こ
の分ハードウェアが増加するため好ましくない。

本発明は以上の不都合な点を考慮してなされたものであ
り、原画像に適度な細線化処理を行なって得られる、線
図形部と塗り潰し領域が混在する細線化図形において、
ループを検出することなく直接的に効率良く塗り潰し領
域を抽出できるような方法を実現することを目的とす
る。

＜問題を解決するための手段＞ 以上の問題を解決した本発明は、３画素×３画素の塗り
潰し領域検出用パターンを保持し、このパターンと現在
のマスク・パターンとを比較して塗り潰し領域を検出す
るものであり、その方法は次の通りである。

即ち、対象図面に細線化を行うことにより得られた線図
形部と塗り潰し領域とが混在するディジタル画像データ
を格納する画像メモリと、前記画像メモリ上の注目画素
の画素値及びその近傍８画素の値を読み出すリード・ア
クセスと指定された注目画素に画素値を書き込むライト
・アクセスとを行うアドレス制御部と、前記画像メモリ
から読み出された前記注目画素の画素値及びその近傍８
画素の値である３画素×３画素のマスク・パターンに対
応する直列データを順次取り込みアドレス信号列に変換
する直並列変換回路と、前記アドレス信号列に従って１
ビット・データ信号を発生するデータ・テーブル・メモ
リと、複数個のレジスタ及び演算器を有し前記直並列変
換回路及び前記データ・テーブル・メモリを参照して次
に追跡すべき注目画素の座標の決定及び塗り潰し領域の
境界線の座標を生成する境界線追跡部とを備え、前記デ
ィジタル画像の塗り潰し領域を検出するディジタル画像
の塗り潰し領域検出方法において、このディジタル画像
データを３画素×３画素のマスク・パターンを用いて順
次ラスタ操作してこのマスク・パターンの内容が予め定
めた塗り潰し領域検出用パターンと一致した場合に、 （イ）前記マスク・パターンにおける注目画素を塗り潰
し境界出発点とするとともにこの注目画素の左隣の画素
を探索開始点として反時計回りまたは時計回りに画素値
を調べ最初の黒画素を追跡画素とする手順と、 （ロ）前記追跡画素を中心に３画素×３画素のマスク・
パターンを設定してこのマスク・パターンが前記塗り潰
し領域検出用パターンと一致した場合にこの追跡画素を
塗り潰し境界点とするとともに１つ前の塗り潰し境界点
を探索開始点とする手順と、 （ハ）前記マスク・パターンと前記塗り潰し領域検出用
パターンと一致しない場合は前記追跡画素を探索開始点
とするとともに１つ前の塗り潰し境界点を追跡画素とし
て手順（ロ）を繰り返す手順と、 を有することを特徴とするディジタル画素の塗り潰し領
域検出方法である。

ここで、前記塗り潰し領域検出用パターンは、中心画素
が黒画素である２５６通りの３画素×３画素のマスク・
パターンから、（前記中心画素の周辺画素数が２以下か
つこの周辺画素数と８連結画素数が同じ値であるマスク
・パターン）を除いたマスク・パターンとする。

＜作用＞ 本発明のディジタル画像の塗り潰し領域検出方法は、細
線化画像を有する画像メモリを３画素×３画素のマスク
・パターンでラスタ走査し、予め設定した塗り潰し領域
検出用パターンと等しくなった場合に境界追跡操作を開
始する。そして、このマスク・パターン内に探索開始点
を設定し、反時計回りまたは時計回りにマスター・パタ
ーンを調べ、黒画素を追跡画素として抽出する。この追
跡画素を中心に３画素×３画素のマスク・パターンを設
定して塗り潰し領域検出用パターンと一致するか否かを
みて、一致していればこの追跡画素を塗り潰し境界点と
する。一致していない時は現在の追跡画素を探索開始
点、直前の塗り潰し境界点を追跡画素として処理を続行
する。

＜実施例＞ 第１図は本発明の方法を具体的に実施する一例を示す構
成ブロック図である。

この図はディジタル画像処理装置の一般的な構成であ
り、画像メモリ１、アドレス制御部２、直並列変換回路
３、データ・テーブル・メモリ４、境界線追跡部５、バ
ッファ・メモリ６の主要部分より構成される。本発明の
方法は境界線追跡部５内の処理アルゴリズムとして格納
される。

ここで、この画像処理装置における各部の動作を簡単に
説明する。

画像メモリ１はディジタル画像データを格納する画素メ
モリであり、対象図面に適度な細線化を行なうことによ
り得られた、線図形部を塗り潰し領域が混在するディジ
タル画像データが予め格納されている。

アドレス制御部２は、境界線追跡部５からの指示により
画像メモリ１へのリード／ライト・アクを高速に行なう
ブロックである。また、画像メモリ１上の注目画素の
Ｘ，Ｙ座標が境界線追跡部５から与えられた場合に、リ
ード・アクセスでは、第３図（ａ）に示すように、Ｘ，
Ｙ座標で指定される注目画素Ｒの画素値（黒または白、
“１”または“０”）と第３図（ｂ）に示す画素Ｒの近
傍８画素の値を画素Ｒ_０，Ｒ_１，Ｒ_２，Ｒ_３，Ｒ_４，Ｒ
_５，Ｒ_６，Ｒ_７の順に画像メモリ１より連続して読み出
し、ライト・アクセスでは、Ｘ，Ｙ座標で指定される注
目画素Ｒに画素値“０”または“１”を書き込むもので
ある。

直並列変換回路３は画像メモリ１から読み出された３画
素×３画素のマスク・パターンに対応する９ビットの直
列データを順次取り込み、９ビットのアドレス信号列に
変換する。

データ・テーブル・メモリ４は直並列変換回路３の９ビ
ット・アドレス出力ＡＤ（＃０００〜＃１ＦＦ；＃は１
６進表示）に従って予め定められている“０”または
“１”の１ビツト・データ信号Ｃを発生する。

境界線追跡部５は複数個のレジスタＲＰ_Ｓ，ＲＦ，ＲＰ
_Ｅ，ＲＰ_ｉ−１，ＲＰ_ｉ，ＲＱ_ｊ及び演算器等を有し、
全体の制御及び塗り潰し部分の抽出アルゴリズムを実行
するブロックである。また、直並列変換回路３及びデー
タ・テーブル・メモリ４からのデータを参照して、次に
追跡すべき注目画素のＸ，Ｙ座標の決定及び塗り潰し領
域の境界線の座標を生成する。

バッファ・メモリ６は境界線追跡部５で塗り潰し部分の
抽出処理に必要な一時点なデータ及び順次抽出される塗
り潰し領域の境界線の座標点列を格納する。

さて、本発明が対象とする図形は、原画像の線部分が線
図形になるまでの適度な細線化処理が予め行なわれた８
連結の線図形部（画素を注目画素から上下左右斜めの８
方向に連ねていくもの）と塗り潰し領域が混在した第４
図に示すようなディジタル画像データである。この図で
網線で示す領域が塗り潰し領域である。

次に本発明の方法を具体的に述べる前に、本発明方法の
原理を説明する。

本発明方法の概要は、＜問題を解決するための手段＞及
び＜作用＞の項にも述べたように、８連結の線図形部と
塗り潰し領域が混在する細線化画像を格納した画像メモ
リ１を３画素×３画素のマスク・パターンを用いて順次
ラスタ走査し、このマスク・パターンの内容が予め定め
られた塗り潰し領域検出用パターンに一致した場合にこ
のマスクの中心画素を出発点として、例えば「コンピュ
ータ画像処理」（安居院，中嶋；産報出版，1979）等の
文献に記載されている３画素×３画素のマスクを用いた
８連結による境界線追跡を１画素ずつ行ない、その都度
塗り潰し領域検出用パターンの内容と一致した追跡画素
のみを塗り潰し領域の境界点として順次抽出する。

ここで、塗り潰し領域検出用パターンの内容を定義す
る。

はじめに、第３図（ｂ）に示すような３画素×３画素の
マスク・パターンの内、中心画素Ｒが黒画素（Ｒ＝
“１”）であるものについて、「標本化された二値図形
のトポロジカルな性質について」（横井，島脇，福村；
電子通信学会論文誌Ｄ，56−Ｄ，11，1973）に記載され
る条件に従って次の値Ｎ_ｓ，Ｎ_ｃを算出する。

中心画素Ｒの周辺にある総黒画素数、即ち周辺画素数Ｎ
_Ｓを とし、更に、中心画素Ｒの消去によって生じる３画素×
３画素のマスク内にある、連結する黒画素成分の数、即
ち８連結数Ｎ_ｃを として算出する。但し、Ｒ_８＝Ｒ_０，▲▼＝１−Ｒ
_ｋとする。

そして、３画素×３画素のマスク・パターンの内、中心
画素Ｒが黒画素（Ｒ＝“１”）であるものを次のように
分類する。

（Ａ）周辺画素数Ｎ_ｓと８連結数Ｎ_ｃが同じ値であるも
の（Ｎ_ｓ＝Ｎ_ｃ） （Ｂ）周辺画素数Ｎ_ｓと８連結数Ｎ_ｃが異なる値である
もの（Ｎ_ｓ≠Ｎ_ｃ） 条件（Ａ）は、第５図（ａ）〜（ｅ）に示す例のよう
に、８連結数Ｎ_ｃ＝０，１，２，３，４の５通りに分類
される。即ち、８連結数Ｎ_ｃ＝０の時（ａ）は中心画素
Ｒは弧立点、８連結数Ｎ_ｃ＝１の時（ｂ）は中心画素Ｒ
は端点、８連結数Ｎ_ｃ＝２の時（ｃ）は中心画素Ｒは連
結点、８連結数Ｎ_ｃ＝３の時（ｄ）は中心画素Ｒは分岐
点、８連結数Ｎ_ｃ＝４の時（ｅ）は中心画素Ｒは交差点
となる。８連結数Ｎ_ｃ＝０，１，２の場合、中心画素は
塗り潰し領域を構成し得ず、８連結数Ｎ_ｃ＝３，４の場
合、領域が一点に集中したものとみなし、塗り潰し領域
として扱うものとする。

条件（Ｂ）は、第６図（ａ）〜（ｃ）に示す例のよう
に、（ａ）８連結数Ｎ_ｃ＝１（２≦Ｎ_ｓ≦７）、（ｂ）
８連結数Ｎ_ｃ＝２（３≦Ｎ_ｓ≦６）（ｃ）８連結数Ｎ_ｃ
＝３（４≦Ｎ_ｓ≦５）の３通りに分類される。即ち、こ
れらは中心画素の周囲に黒画素連結成分が１つ以上ある
状態を意味し、中心画素が塗り潰し領域または分岐点の
一部を構成するものとみなす。

以上の考察より、塗り潰し領域検出用パターンを次のよ
うに定義する。

即ち、塗り潰し領域検出用パターンを、中心画素Ｒが黒
画素である２５６通りの３×３のマスク・パターンか
ら、条結（Ｃ）「周辺画素数Ｎ_ｓが２以下かつ周辺画素
数Ｎ_ｃと８連結数Ｎ_ｃが同じ値であるもの」を満たすパ
ターンを除いたもの、とする。

詳しくは、条件（Ｃ）を満たすマスク・パターンは、第
７図に示すように、全部で２５通りであり、従って、塗
り潰し領域検出用パターンは２５６−２５＝２３１通り
となる。

次に、画像メモリ１を３画素×３画素のマスク・パター
ンを用いて順次ラスタ走査し、このマスク・パターンの
内容が塗り潰し領域検出用パターンに一致し、塗り潰し
境界点Ｑ_ｍが抽出された時、次の塗り潰し境界点Ｑ
_ｍ＋１を抽出する方法手順を第８図及び第９図を用いて
説明する。

（イ）第８図（ａ）に示すように、境界点Ｑ_ｍを中心画
素として３画素×３画素のマスクを設定する。

（ロ）次に、境界点Ｑ_ｍの１つ前の境界点Ｑ_ｍ−１から
反時計回りに，，…の順に黒画素か白画素かを調
べ、最初の黒画素を検出し、この点を追跡点Ｐ_ｎとす
る。

（ハ）第８図（ｂ）に示すように、追跡点Ｐ_ｎを中心に
３画素×３画素のマスクを設定し、このマスク・パター
ンが塗り潰し領域検出用パターンと一致するか否かを調
べる。

（ニ）追跡点Ｐ_ｎを中心とするマスク・パターンが塗り
潰し領域検出用パターンの内容に一致した場合は、第８
図（ｃ）に示すように、追跡点Ｐ_ｎを次の境界点Ｑ
_ｍ＋１とする。

（ホ）一方、第９図（ａ）に示す追跡点Ｐ_ｎの場合のよ
うに、この追跡点Ｐ_ｎを中心とするマスクが塗り潰し領
域検出用パターンの内容に一致しない場合は、再び境界
点Ｑ_ｍを中心とするマスクに戻り、第９図（ｂ）に示す
ように、今度は追跡点Ｐ_ｎから反時計方向に，，…
の順に黒画素か白画素かを調べ、最初に検出した黒画素
を次の追跡点Ｐ_ｎ＋１とする。

（ヘ）次に第９図（ｃ）に示すように、追跡点Ｐ_ｎ＋１
を中心に３画素×３画素のマスクを設定し、このマスク
・パターンが塗り潰し領域検出用パターンに一致した場
合は、第９図（ｄ）に示すように、追跡点Ｐ_ｎ＋１を次
の境界点Ｑ_ｍ＋１とする。

（ト）追跡点Ｐ_ｎ＋１を中心とするマスク・パターンが
塗り潰し領域検出用パターンと一致しない場合は、境界
点Ｑ_ｍを中心とするマスク・パターンに再び戻り、追跡
点Ｐ_ｎ＋１から反時計回りに黒画素か白画素かを調べ、
最初の黒画素を次の追跡点とし、以下上述と同様の操作
を繰り返す。

このようにして、順次塗り潰し境界点を抽出する。

上記の操作は塗り潰し領域の境界点を反時計方向に抽出
した場合を述べたが、時計方向に境界点を抽出する場合
は、第10図示すように、点Ｑ_ｍを中心とするマスクにお
いて、１つ前の境界点Ｑ_ｍ−１から時計方向に，，
…の順に黒画素、白画素を調べ、最初の黒画素を追跡
点Ｐ_ｎとする。

以上が本発明の方法の原理であり、次に、第４図に示す
ディジタル画像データを対象とし、第１図に示す装置を
用い、第２図のフローチャート、第11図の手順説明図を
参照として本発明の方法を具体的に説明する。

尚、第１図におけるデータ・テーブル・メモリ４には
ン、第12図に示すように、画像メモリ１から読み出され
た３×３のマスク・パターン（第12図（ａ））を入力デ
ータとして直並列変換回路３で変換された９ビット・ア
ドレス“Ｒ（ＭＳＢ），Ｒ_０，…，Ｒ_７（ＬＳＢ）”
（第12図（ｂ））に対応したデータ“０”または“１”
が格納される。この時、“１”は対応するマスク・パタ
ーンが塗り潰し領域検出用パターンと一致したことを表
わし、“０”は一致しないことを表わす（第12図
（ｃ））。

また、値“０”に対応するアドレスは、３×３のマスク
・パターンの内、中心画素Ｒが白画素（Ｒ＝“０”）の
ものを含み、アドレス＃０００〜＃０ＦＦの２５６通り
と第７図に示すマスク・パターン２５通りの計２８１通
りのアドレスである。従って、内容が“１”のアドレス
は残りの２３１通りのアドレスである。

さて、第２図に示すフローチャートに従って本発明の方
法手順を説明する。

（１）境界線追跡部５は、第４図に示すようなディジタ
ル図形における画素の座標を順次アドレス制御部２に与
えてリード・アクセスし、画素メモリ１を３×３のマス
クを用いてラスタ走査する。画像メモリ１から読み出さ
れた３×３のマスク・パターンの９ビット直列データ
“Ｒ，Ｒ_０，…，Ｒ_７”は一旦直並列変換回路３に取り
込まれ、順次、データ・テーブル・メモリ４へのアドレ
スとなる。そして、データ・テーブル・メモリ４からの
出力データＣによりその都度マスク・パターンの内容を
調べる。

（２）出力データＣ＝“０”、即ちマスク・パターンが
塗り潰し領域検出用パターンに一致していない場合には
手順（１）を繰り返す。

（３）第11図（ａ）に示すように、出力データＣ＝
“１”、即ちマスク・パターンＭ_１が塗り潰し領域検出
用パターンに一致した場合にはマスクＭ_１の中心画素Ｒ
を塗り潰し領域の境界出発点Ｐ_ｓとし、その座標を境界
線追跡部５のレジスタＲＰ_ｓ及びバッフア・メモリ６に
格納する。

（４）境界線追跡部５は、出発点Ｐ_ｓ（＝中心画素Ｒ）
の左隣の画素Ｒ_４を探索開始点Ｐ_Ｆとし、この座標をレ
ジスタＲＦ_Ｆに格納し、直並列変換回路３の出力データ
より黒画素“１”か白画素“０”かを調べる。

（５）画素Ｒ_４が黒画素の場合は、この画素Ｒ_４を終了
検出点Ｐ_Ｅとしてその座標をレジスタＲＰ_Ｅに格納し、
手順（７）に移る。

（６）画素Ｒ_４が白画素の場合（第11図（ａ）の場合）
は、出発点Ｐ_ｓを中心とする３画素×３画素のマスクに
おいてレジスタＲＰ_Ｆで指定される探索開始点Ｐ_Ｆ（画
素Ｒ_４）から時計回り（反時計回りとする場合、下の手
順（８）において反時計回りを時計回りとする）に画素
を調べ、最初の黒画素を終了検出点Ｐ_Ｅとし、その座標
をレジスタＲＰ_Ｅに格納する。

（７）出発点Ｐ_ｓを１つ前の追跡中心画素Ｐ_ｉ−１とし
てその座標をレジスタＲＰ_ｉ−１に格納する。

（８）レジスタＲＰ_ｉ−１で指定される１つ前の追跡中
心画素Ｐ_ｉ−１を中心とする３×３のマスク（第11図
（ａ）のマスクＭ_１に対応する）において、レジスタＲ
Ｐ_Ｆで指定される探索開始点Ｐ_Ｆから反時計回りに画素
を調べ、最初の黒画素を現在の追跡中心画素Ｐ_ｉ（＝Ｐ
_１）とし、その座標をレジスタＲＰ_ｉに格納する。

（９）１つ前の追跡中心画素Ｐ_ｉ−１と終了検出点
Ｐ_Ｅ、現在の追跡中心画素Ｐ_ｉと出発点Ｐ_ｓが一致した
か否かをレジスタＲＰ_ｉ−１とレジスタＲＰ_Ｅ、レジス
タＲＰ_ｉとレジスタＲＰ_ｓの内容を比較し、追跡処理が
終了したか否かを検出する。

(10)１つ前の追跡中心画素Ｐ_ｉ−１と終了検出点Ｐ_Ｅ、
現在の追跡中心画素Ｐ_ｉと出発点Ｐ_ｓが一致した場合は
手順(18)に移る。

(11)１つ前の追跡中心画素Ｐ_ｉ−１と終了検出点Ｐ_Ｅ、
現在の追跡中心画素Ｐ_ｉと出発点Ｐ_ｓが一致しない場
合、境界線追跡部５は、レジスタＲＰ_ｉで指定される現
在の追跡中心画素Ｐ_ｉの座標をアドレス制御部２に与
え、リード・アクセスを行なう。次に、第11図（ｂ）に
すように、画像メモリ１から点Ｐ_ｉ（＝Ｐ_１）を中心と
する３×３のマスク・パターンＭ_２を読み出し、直並列
変換回路３に取り込み、データ・テーブル・メモリ４か
らの出力データＣの値によりこのマスク・パターンＭ_２
の内容を調べる。

(12)出力データＣ＝“０”即ちマスク・パターンＭ_２が
塗り潰し領域検出用パターンと一致していない場合は手
順(16)に移る。

(13)第12図（ｂ）に示すマスクＭ_２の出力データＣ＝
“１”即ちマスク・パターンＭ_２が塗り潰し領域検出用
パターンに一致する場合は、レジスタＲＰ_ｉで指定され
る、現在の追跡中心画素Ｐ_ｉ（Ｐ_１）を塗り潰し領域の
境界点Ｑ_ｊとし、その座標をレジスタＲＱ_ｊ及びバッフ
ァ・メモリ６に格納する。

(14)マスクＭ_２において、１つ前の追跡中心画素Ｐ
_ｉ−１（Ｐ_ｓに対応）を探索開始点Ｐ_Ｆとし、レジスタ
ＲＰ_ｉ−１の内容をレジスタＲＰ_Ｆに格納する。

(15)現在の追跡中心画素Ｐ_ｉ（Ｐ_１）を１つ前の追跡中
心画素Ｐ_ｉ−１とし、レジスタＲＰ_ｉの内容をレジスタ
ＲＰ_ｉー１に格納する。そして、手順（８）に移る。

このようにして、手順（８），（９），(11)，(13)，(1
4)，(15)を繰り返し、塗り潰し領域境界点Ｐ_１，Ｐ_２，
Ｐ_３を抽出する。

(16)手順(12)において、点Ｐ_ｉ（＝Ｐ_１）を中心とする
３×３のマスク・パターンＭ_２に対応する出力データＣ
が“０”、即ちこのマスク・パターンＭ_２が塗り潰し領
域検出用パターンと一致しない場合、このときの追跡中
心画素Ｐ_ｉ（Ｐ_１）を探索開始点Ｐ_Ｆとし、レジスタＲ
Ｐ_ｉの内容をレジスタＲＰ_Ｆに格納する。

(17)そして、直前の塗り潰し領域の境界点Ｑ_ｊ（Ｐ_ｓ）
を１つ前の追跡中心画素Ｐ_ｉ−１とし、レジスタＲＱ_ｊ
の内容をレジスタＲＰ_ｉ−１に格納する。レジスタＲＰ
_ｉ−１で指定される点Ｐ_ｉ−１の座標をアドレス制御部
２に与えてリード・アクセスを行ない、画像メモリ１か
ら点Ｐ_ｉ−１（Ｐ_ｓ）を中心とする３×３のマスク・パ
ターン（マスクＭ_１に対応する）の内容を読み出し、直
並列変換回路３に取り込む。次に手順（８）に戻る。

ここで、手順(12)，(16)，(17)ディジタル画像における
線図形部と塗り潰し領域との境界を検出する手順であ
り、その具体的な例を第11図（ｃ），（ｄ）を用いて説
明する。

第11図（ｃ）において、画素Ｐ_１，Ｐ_２，Ｐ_３が塗り潰
し境界であると判定された点であり、現在の追跡中心画
素Ｐ_ｉとして黒画素Ｐ_４が抽出されたとする。

画素Ｐ_４を中心とする３画素×３画素のマスク・パター
ンＭ_４を設定すると、このマスク・パターンＭ_４は塗り
潰し領域検出用パターンとは一致せず、次に現在の追跡
中心画素Ｐ_４を探索開始点Ｐ_Ｆとし、直前の塗り潰し領
域の境界点Ｐ_３を追跡中心画素Ｐ_ｉ−１とするマスク・
パターンＭ_３に戻る。探索開始点Ｐ_Ｆ（Ｐ_４）より反時
計回りに黒画素を検出すると、画素Ｐ_５が抽出される。

次に、画素Ｐ_５を追跡中心画素としてマスク・パターン
Ｍ_５を設定すると、このマスク・パターンＭ_５は塗り潰
し領域検出用パターンと一致せず、第11図（ｄ）に示す
ように、現在の追跡中心画素Ｐ_５を探索開始点Ｐ_Ｆと
し、直前の塗り潰し境界点Ｐ_３を中心画素とするマスク
・パターンＭ_３に戻る。そして、画素Ｐ_５より反時計回
りに黒画素Ｐ_６を中心とする。黒画素Ｐ_６を中心とする
マスク・パターンＭ_６は塗り潰し領域検出用パターンと
一致し、画素Ｐ_６は塗り潰し領域境界点とみなされる。

このような手順により、画素Ｐ_３より画素Ｐ_４を中心と
するマスク・パターンＭ_４及び画素Ｐ_５を中心画素とす
るマスク・パターンＭ_５を設定してその内容を調べ、画
素Ｐ_３がディジタル画像の線図形部と塗り潰し領域との
境界であることが判別される。

さて、第２図のフローチャートに戻り、手順の説明を続
ける。

(18)手順（９）において、１つ前の追跡中心画素Ｐ
_ｉ−１と終了検出点Ｐ_Ｅ、現在の追跡中心画素Ｐ_ｉと出
発点Ｐ_ｓが一致した場合、例えば第11図（ｅ）におい
て、１つ前の追跡中心画素Ｐ_１４と終了検出点Ｐ_Ｅが一
致し、かつ現在の追跡中心画素Ｐ_１５と出発点Ｐ_ｓが一
致した場合、現在の追跡中心画素Ｐ_ｉ（Ｐ_１５）を塗り
潰し領域の境界点Ｑ_ｊとし、レジスタＲＰ_ｉで指定され
る現在の追跡中心画素Ｐ_ｉを塗り潰し領域の境界点Ｑ_ｊ
（この場合画素Ｐ_１５の座標は出発点Ｐ_ｓに同一）と
し、その座標をバッフア・メモリ６に格納する。

第11図（ｅ）は追跡中心画素Ｐ_ｉ（ｉ＝１，…，１５）
の追跡の様子を表わし、第11図（ｆ）は以上の操作によ
って得られた塗り潰し領域の境界点Ｑ_ｊ（ｊ＝０，…，
９）を表わす。

(19)境界線追跡部５は、バッファ・メモリ６に格納され
た塗り潰し領域の境界点列Ｑ_ｊの座標を用いて、画像メ
モリ１上の点列Ｑ_ｊよりなる境界線及びその内部の画素
を黒から白に全て変換する。

この黒画素白画素変換処理は、今回の操作によって一旦
得られた塗り潰し領域の境界点Ｑ_ｊが次回のラスタ走査
において再び検出されることがないように行なう処理で
あり、具体的には、抽出された塗り潰し領域の境界線を
多角形とみなし、例えば 「Fundamentals of InteractiveComputer Graphiccs」
（Ｊ．Ｄ．Foley／Ａ．Van Dam；Addison-Wesley，198
2）等の文献に記載されている、コンピュータ・グラフ
ィックスに使用される多角形の塗り潰し手法を用いるこ
とにより実行される。

(20)境界線追跡部５は、画像メモリ１において３×３の
マスク・パターンのラスタ走査が終了したかどうかをレ
ジスタＲＰ_ｓで指定される点Ｐ_ｓの座標により調べる。

(21)ラスタ走査が終了していない場合は、手順（１）に
戻り、画像メモリ１上の点Ｐ_ｓよりラスタ走査を行な
う。

(22)ラスタ走査が終了した場合は、塗り潰し領域の抽出
処理を終了する。

以上のようにして、８連結の線図形部と塗り潰し領域が
混在するディジタル画像データ（細線化図形）を格納し
た画像メモリ１を３画素×３画素のマスクを用いて順次
ラスタ走査し、このマスク・パターンの内容が予め定め
られた塗り潰し領域検出用パターンに一致した場合にこ
のマスクの中心画素を出発点として３画素×３画素のマ
スクを用いて境界線追跡を１画素ずつ行ない、その都度
塗り潰し領域検出用パターンの内容と一致した追跡画素
のみを塗り潰し境界点として順次抽出することができ
る。

＜発明の効果＞ 以上述べたように、本発明のディジタル画像の塗り潰し
領域検出方法によれば、８連結の線図形部と塗り潰し領
域が混在した細線化図形より塗り潰し領域の境界線を直
接的に抽出することができる。

また、本発明の方法によれば、８連結の線図形部と塗り
潰し領域が混在したディジタル画像データを保持するた
めの画像メモリのみを準備すれば良く、従来のように、
更に作業用として別の画像メモリを設ける必要がない。

【図面の簡単な説明】

第１図は本発明のディジタル画像の塗り潰し領域検出方
法を具体的に実施する画像処理装置の一例を示す構成ブ
ロック図、第２図は本発明の方法の手順を具体的に表わ
したフローチャート、第３図（ａ），（ｂ）は画像メモ
リ上の注目画素Ｒとこの注目画素Ｒを中心とする３画素
×３画素のマスク・パターンを表わす図、第４図は本発
明が対象とするディジタル画像データを表わす図、第５
図（ａ）〜（ｅ）は３画素×３画素のマスク・パターン
において周辺画素数Ｎ_ｓと８連結数Ｎ_ｃが同じ値である
もの（条件Ａ）の例を表わす図、第６図（ａ）〜（ｂ）
は３画素×３画素のマスク・パターンにおいて周辺画素
数Ｎ_ｓと８連結数Ｎ_ｃが異なる値であるもの（条件Ｂ）
の例を表わす図、第７図は３画素×３画素のマスク・パ
ターンにおいて周辺画素数Ｎ_ｓが２以下かつ周辺画素数
Ｎ_ｓと８連結数Ｎ_ｃが同じ値であるもの（条件Ｃ）の例
を表わす図、第８図（ａ）〜（ｃ）と第９図（ａ）〜
（ｄ）と第10図は塗り潰し境界点が抽出された時次の塗
り潰し境界点を抽出する手順を表わす図、第11図（ａ）
〜（ｆ）は本発明の方法を第４図に表わすディジタル画
像データに施した際の状態遷移を表わす図、第12図
（ａ）〜（ｃ）は直並列変換回路３及びデータ・テーブ
ル・メモリ４の機能を説明するための図、第13図は本発
明が対象とするような電気回路図の一部を表わす図、第
14図（ａ）〜（ｃ）は原画像に細線化処理を施す場合を
表わす図である。 １……画像メモリ、２……アドレス制御部、 ３……直並列変換回路、 ４……データ・テーブル・メモリ、 ５……境界線追跡部、６……バッファ・メモリ。

Claims (2)

【特許請求の範囲】
1. 【請求項１】対象図面に細線化を行うことにより得られ
   た線図形部と塗り潰し領域とが混在するディジタル画像
   データを格納する画像メモリと、前記画像メモリ上の注
   目画素の画素値及びその近傍８画素の値を読み出すリー
   ド・アクセスと指定された注目画素に画素値を書き込む
   ライト・アクセスとを行うアドレス制御部と、前記画像
   メモリから読み出された前記注目画素の画素値及びその
   近傍８画素の値である３画素×３画素のマスク・パター
   ンに対応する直列データを順次取り込みアドレス信号列
   に変換する直並列変換回路と、前記アドレス信号列に従
   って１ビット・データ信号を発生するデータ・テーブル
   ・メモリと、複数個のレジスタ及び演算器を有し前記直
   並列変換回路及び前記データ・テーブル・メモリを参照
   して次に追跡すべき注目画素の座標の決定及び塗り潰し
   領域の境界線の座標を生成する境界線追跡部とを備え、
   前記ディジタル画像の塗り潰し領域を検出するディジタ
   ル画像の塗り潰し領域検出方法において、 このディジタル画像データを３画素×３画素のマスク・
   パターンを用いて順次ラスタ操作してこのマスク・パタ
   ーンの内容が予め定めた塗り潰し領域検出用パターンと
   一致した場合に、 （イ）前記マスク・パターンにおける注目画素を塗り潰
   し境界出発点とするとともにこの注目画素の左隣の画素
   を探索開始点として反時計回りまたは時計回りに画素値
   を調べ最初の黒画素を追跡画素とする手順と、 （ロ）前記追跡画素を中心に３画素×３画素のマスク・
   パターンを設定してこのマスク・パターンが前記塗り潰
   し領域検出用パターンと一致した場合にこの追跡画素を
   塗り潰し境界点とするとともに１つ前の塗り潰し境界点
   を探索開始点とする手順と、 （ハ）前記マスク・パターンと前記塗り潰し領域検出用
   パターンと一致しない場合は、前記追跡蛾素を探索開始
   点とするとともに１つ前の塗り潰し境界点を追跡画素と
   して手順（ロ）を繰り返す手順と を有することを特徴とするディジタル画像の塗り潰し領
   域検出方法。
2. 【請求項２】前記塗り潰し領域検出用パターンは、中心
   画素が黒画素である２５６通りの３画素×３画素のマス
   ク・パターンから、（前記中心画素の周辺画素数が２以
   下かつこの周辺画素数と８連結画素数が同じ値であるマ
   スク・パターン）を除いたマスタ・パターンとすること
   を特徴とする特許請求の範囲第１項記載のディジタル画
   像の塗り潰し領域検出方法。