JPH03224071A - 二値画像の細線化方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概要］ 処理対象画面を複数の領域に分割して、各分割画面の画
像について細線化を行って得られた各細線化分割画像を
統合して全体の細線化画像を得る二値画像の細線化方式
に関し。

画面分割による細線化を行う際に逐次型細線化処理を使
用しながら分割画面の重畳領域における細線化の結果と
、隣接する分割画面の細線化の結果にずれが生しない二
値画像の細線化方式を提供することを目的とし 画面全体のイメージデータをイメージデータ格納部に備
え、処理部は、隣接する分割画像と重畳領域を持つよう
画面全体を所定の大きさに分割して分割テーブルに格納
する画面分割手段と１分割画面のイメージデータをメモ
リに取り出して各分副画面の重畳領域の画像について並
列型ａｔ線化を行う並列型細線化処理手段と、各分割画
面の重畳領域を除く領域について逐次型の細線化を行う
と共に上記並列型細線化により得られた処理結果との結
合を行う逐次型細線化処理手段とを備えるよう構成する
。

［産業上の利用分野Ｊ 本発明は処理対象画面を複数の領域に分割して。

各分割画面の画像について細線化を行って得られた各細
線化分割画像を統合して全体の細線化画像を得る二値画
像の細線化方式に関する。

近年２紙に書かれた図面や文書等を計算機に入力して活
用することが盛んに行われるようになった。特にスキャ
ナ等で図面を読み込んだ後、自動的に折れ線近似を行っ
て計算機の入力とする凹面入力装置が用いられるように
なってきた。このような装置において、細線化処理は折
れ線近似を行うための前処理の手法の一つとして重要で
ある。

細線化処理とは、スキャナ等で読み込んだ時に得られる
イメージデータを、その線幅が１になるように細めてい
く処理であるが、イメージデータ全体を一度に細線化し
ようとすると、当然のことだがそのイメージデータをロ
ードするためのメモリが必要となる。この時１例えばＡ
３サイズの図面を４００ｄｐｉ　　（ドツト・パー・イ
ンチ）で入力すると約４Ｍ（メガ）バイト、ＡＯサイズ
の図面を４００ｄｐｉで入力すると３１Ｍハイドのメモ
リが必要になる。このため、近年、入力イメージデータ
を複数の領域に分割しておのおのを個別にメモリにロー
ドすることにより必要なメモリ量を削減する方法が用い
られるようになった。

ところが、この画面分割による細線化をした後分割され
た画像を相互に接続する時に問題が生じその改善が望ま
れている。

［従来の技術］ 第７図は分割細線化の例９第８図は重畳領域を設けた画
面分割の説明図、第９図は重畳領域を設けた分割画面の
細線化の例、第１０図は細線化の概要図、第１１図は逐
次型細線化方式の問題説明図である。

従来１画面中の画像を細線化する為には１画像メモリに
図面イメージデータ全体をロードし、このイメージデー
タに対して一度に細線化を行っていた。この方法は一番
簡単であるが、上記したように大きな図面を４００ｄｐ
　ｉで入力した時イメージデータを格納するメモリとし
て大容量が必要となる。

この方法ではメモリ量が多いため装置のコストが増大す
るので２画面全体を一度にメモリにロードするのではな
く、イメージデータを適当な大きさに分割し１個別にメ
モリにロードして処理を行う手法が用いられるようにな
った。イメージデータを分割することにより、必要なメ
モリ量は分割したひとつひとつのイメージデータの必要
量だけあればよいので装置に必要なメモリ量を従来のも
のに比べ大幅に削減することが可能となる。

両面分割を行うためには２分割して処理を行った後処理
結果を再び統合することが必要となる。

この分割の方法を第７図により説明すると、Ａ。

に示す画面を上・下の２つに単純に分割してそれぞれで
細線化を実行した場合、Ｂ、に示すように分割された画
像の端部の線が細線化処理により消えたり、線の位置が
不安定になる（線の最端部はその先のデータが無いため
細線化処理が困難）。

この場合１分割した２つの画面を統合する時に２つの画
面の接続する位置に細線が無くなったり。

細線があったとしても位置が合わなくなるという問題が
生じた。

これを解決するための手法の一つに１発明の名称「画面
分割による線図形折線近似化方式」　（特開昭６３−１
１８８８７号公報参照）が提案されている。

この方式を第８図及び第９図により説明すると。

第８図のＡ、に示すように画面が複数に分割する時、各
分割画面の境界線に対して画像の最大細線化回数（画像
の表現に使用される線幅に対応）以上の幅ｄを持つ重畳
領域を設けておく。Ａ、の例では５画面全体を■乃至■
の３つに分割した場合であり、各分割画面は境界線より
さらに幅ｄだけ広い部分を含めた領域のイメージデータ
について細線化を行う（従って互いに境界線を中心にし
て２ｄの幅の共通の重畳領域を持つことになる）。

すなわち、各隣接する分割画面においてそれぞれが幅ｄ
だけ広い領域のイメージデータについて細線化処理を行
う。第８図Ｂ、には左側、右側及び下側に隣接画面があ
る時の分割画面の例が示されそれぞれ隣接画面に対して
重畳領域が設けられている。

このような重畳領域を設けた場合の分割の例を第９図に
より説明すると１図の左側に示す全体画面９０を重畳領
域を設けて２分割すると１図の境界線より幅ｄだけ相互
に拡大した重畳領域を持つように分割されて、２つの画
面９１．９２が得られる。次にこの分割画面９１．９２
の画像に対してそれぞれ細線化処理を行うと第９図の右
側に示すように細線化画面９１’、９２が得られる。

この図に示されるように境界上で細線化画像が一致し、
上記第７図の重畳領域を設けない場合に比べて良好な結
果が得られる。

一方、イメージデータを細線化する手法には従来大きく
わけて逐次型細線化と並列型細線化の２つがあり、第１
０図に細線化の概要図が示されている。

逐次型細線化は、第１Ｏ図のＡ、に示すように。

図形の輪郭を追跡しながらマスク演算を行って輪郭画素
を削ってゆく方式である。図中の矢印が輪郭追跡をする
様子を示す。なお、マスク演算とは。

３×３（中心ドツトその中心ドツトに対して上。

下、左、右および４つの斜め方向）のマスクパターンを
用いて１画像の注目画素に対して周囲の画素（ドツト）
の分布を照合演算して、線の形状や幅を検出するもので
ある。

そして１図形の線の軌跡に従って各ドツトを１つずつ調
べ、線幅が複数ドツトで構成すると１ドνトづつ削るこ
とにより行う。

この逐次型細線化処理の特徴は、演算量が比較的に少な
いので、汎用プロセッサ上で実現しやすいことである。

次に並列型細線化は、第１０図Ｂ、に概略を示すように
９図形を含む画面（画像）の最上部の水平方向に、マス
クパターンを用いて左端から右端へ走査（スキャン）し
ながら演算を行い、これが終了するとｌドツト下の水平
方向について同じ走査・演算を行って、最下部まで順次
同様の処理を繰り返しながら、線幅の検出と細線化の処
理を行う方式である。この方式では、処理に影響を与え
ないように細線化途中の結果は９例えば別のイメージメ
モリ等に保存される。細線化結果の例を第１０図Ｃ１に
示す。但しこの図は縮小化された図である。

この並列型細線化は、処理が単純であり、演算量が多い
ためハードウェア化に適している。また。

細線化途中の画像が処理に影響を与えないようになって
いるので、細線化画像は常に同じものになっている。（
これは、同しイメージメモリ上に細線化の途中結果を書
込むと、以前の段階の図形が消えてしまい、必ずしも細
線化の結果が同じにならない。） ［発明が解決しようとする課題］ 上記した従来の画面を複数の領域に分割して細線化を行
う方式では、細線化処理の後で分割画面を統合した時に
隣接する画面の線の位置を常に一致させるため、細線化
の結果が常に一定している並列型の細線化方式を行う必
要があるが、汎用プロセッサで実現したときは処理時間
がかかるという問題があった。

一方、逐次型細線化方弐の場合は、処理量が並列型細線
化に比べて限定されている（処理の対象となる個所は画
面中の図形部分だけ）ので、汎用プロセッサの処理に適
しているが、追跡開始点によって得られる細線化画像が
異なってしまうという問題があった。

この問題を第１１図により説明すると、第１１図のＡ、
にドツト構成の図形（一部）の例が示されている。この
図形を■に示すように左上から右下に向かってマスク演
算により細線化を行って。

Ａ、の中のａで示すドツト（二重まる）を対象に細線化
を行う場合、その右隣にもドントが存在するのでａを消
去して細線化を行うと、第１１図のＢ、のような図形に
なる。他方Ａ、において■で示す方向、すなわち図形の
下から右側にそって上に向かって処理を行うと、ｂで示
すドントが細線化により消去して細線化（斜め方向の線
幅を１ドツトにする）が行われてＣ０のようになる。こ
の結果、Ｂ、とＣでは異なる図形となる。

このように細線化画像が追跡開始点で異なると分割した
画面に対して逐次型細線化をした後で。

画面を統合する時に隣接画像と細線が一致しなくなると
いう問題がある。

本発明は画面分割による細線化を行う際に逐次型細線化
処理を使用しながら分割画面の重畳領域における細線化
の結果と、隣接する分割画面の細線化の結果にずれが生
しない二値画像の細線化方式を提供することを目的とす
る。

［課題を解決するための手段］ 第１図は本発明の原理構成図である。

第１図において、１０は処理部、１１は画面分割手段、
１２は並列型細線化処理手段、１３は逐次型細線化処理
手段、１４はイメージデータ格納部、１５は分割テーブ
ル、１６はメモリを表す。

本発明は複数の分割画面の境界部分で重複する領域につ
いてのみ並列型細線化処理を行い、それ以外の領域では
逐次型細線化を行うことにより細線化処理を高速化する
と共に境界部分での細線化画像のずれの発生を防止する
ものである。

［作用］ 処理部１０において、最初に全体画面のイメージデータ
が格納されたイメージデータ格納部１４のデータについ
て２画面分割手段１１により境界部分で重畳するように
所定の大きさに分割する。

重畳部分の幅は細線化すべき線の幅に対応して。

線幅が広い場合重畳部分の幅が広くなる。各分割画面の
領域のデータは分割テーブル１５に格納される。

次に、細線化の処理が行われるが、細線化の対象となる
１つの分割画面の領域に含まれるイメージデータがイメ
ージデータ格納部１４からメモリ１６にロードされ、先
ず重畳領域のデータに対して並列型細線化処理手段１２
により並列型細線化処理が実行される。この並列型細線
化処理手段１２は従来と同様の方式で５重畳領域のデー
タに対してマスクパターンによる走査を行って細線化処
理を行う。この細線化結果はメモリ１６内に格納される
。この場合１重畳領域の元のデータを細線化処理結果に
より書き換えるか、細線化処理結果をメモリ１６内の別
の領域に格納するかの何れの方法でもよい。

重畳領域の細線化処理が終了すると１次に逐次型細線化
処理手段１３が起動して２分割領域の中の重畳領域を除
いた部分のデータについて従来と同様の方法により逐次
型細線化処理が行われる。

この時、上記並列型細線化処理手段１２による重畳領域
の細線化結果がメモリ１６に格納されており、この逐次
型細線化処理による図形の輪郭を追跡する時に重畳領域
の細線化処理結果を連続して参照する。この場合２重畳
領域の部分は既に細線化されているので１逐次型細線化
処理の対象となるデータと並列型細線化処理が実行され
たデータとが連続して処理されて１両領域の線の連続性
が保たれる。

逐次型細線化処理手段１３による処理の結果はメモリ１
６に格納されている。

［実施例］ 第２図は実施例の折線近似化装置の構成図、第３図は分
割の具体例を示す図、第４図は画面分割テーブルの例を
示す回、第５図は実施例の処理フロー図、第６図（ａ）
は並列型細線化処理の具体例第６図（ｂ）は重複領域の
処理を変えた逐次型細線化処理の具体例である。

第２図において９２０は原画像データを格納する磁気デ
ィスク、２１は処理の流れを制御する制御部、２２は原
画の大きさや原画中の線幅の情報から画面分割テーブル
を作成する画面分割テーブル作成部、２３は分割テーブ
ルに従ってイメージメモリ２７に画像データをロードす
る画像ロード部５２４は並列型細線化部、２５は逐次型
細線化部、２６は細線化された画像から折線近イ以を行
う折線近偵部、２７はイメージメモリである。

動作を説明すると、入力されたイメージデータは、−時
的に磁気ディスク２０に格納される。これは通常の細線
化機構であればイメージメモリに一度にロードできるが
２本発明ではイメージメモリとして容量が少ないものを
使用するので、磁気ディスク２０に一時的な格納のため
必要となる。

次に１画面分割テーブル作成部２２において人力された
イメージデータの大きさ１個々の分割画面間の必要な重
畳領域の大きさ（重畳領域の線幅に比例）、及びイメー
ジメモリ２７の実装サイズとから、入力イメージデータ
を分割する情報である画面分割テーブルを作成する。

画面分割の例を第３図に示す。

第３図のＡ、は画面全体を示し、これを６つに分割する
場合、各分割画面の境界線に対して、それぞれ幅ｄだけ
拡張した部分を含めて分割画面を構成する。分割画面の
例は同図のＢ、に示されＡ、の中央・上部の部分を表す
。これに示すように、境界線の内・外の幅ｄの帯状の領
域が隣接する分割画面と重畳しており、この例では図に
示すように並列型細線化領域１〜３に対して並列型細線
化処理が行われる。

画面分割テーブルの例を第４図に示す。

分割テーブル４０には複数の各分割画面に対応して分割
テーブル１（４１）〜分割テーブルＮ（４Ｎ）が設けら
れ、各分割テーブルには個々の分割画面の領域情報が格
納されている。第４図には分割テーブル１（４１）に格
納された情報の内容が示されている。

即ち、最初にこの分割画面が未処理が処理済かを表すフ
ラグ４１１１分割画面の全領域を表す情報として分割画
面の左上座標と右下座標４１２次にのりしろを含まない
領域（分割画面の境界線から外部にｄだけ張り出した部
分をのりしろという）の左上座標と右下座標４１３１次
に逐次型細線化を行う領域（分割領域内の重複領域を除
いた内部の領域）の左上座標と右下座標４１４．さらに
並列型細線化を行う領域（隣接領域と重複する領域）と
して上、下、左、右の４つの領域１〜４（それぞれ長方
形）のそれぞれの左上座標と右下座標４１５〜４１８と
が格納される。

ここで、他の分割画面との重複部分は、上記したように
上下左右の４個所に生じる可能性があるため、この分割
テーブルには４個所用の領域がとられているが１例えば
第３図のＡ、のように６分割した時の、Ｂ、に示す分割
画面に対応する分割テーブルには左、下、右の３個所に
のみ隣り合う分割画面との重複部分が存在する。この分
割テーブルが分割画面の枚数骨２画面分割テーブル作成
部２２（第２回）によって作成される。

画面分割テーブルが作成された後は、このテーブルに登
録された個々の領域毎に細線化を行ってゆく。

この処理フローの実施例を第５図に示す。

このフローはＹＡＣチャートと呼ばれる公知のフローを
表現する図であり１例えばｒｌＦ、の場合、その条件の
内容が右側に示され１条件を満たす場合はｒＹＥＳＪと
いうｒｌＦＪの文字の右下に示す方向に進み、ＮＯの場
合は、ｒｌＦＪの文字の先端から下へ向かって次のｒＩ
ＦＪや「ＤＯＪの処理に進むようになっている。

以下に第５図の処理フローの内容を第２図乃至第４図を
参照しながら説明する。

まず、制御部２１が未処理の領域が画面分割テーブルに
残っているかを第４図に示す分割テーブル１〜Ｎの各フ
ラグ４１１を参照して判断しく第５図の５１）、未処理
の分割画面が存在しないと。

［ＴＨＩＮＮ−ＥＮＤ　）へ進み細線化が終了しく同５
２）存在する場合は、その未処理の分割テーブルで示す
部分を画像ロード部２３により磁気ディスク２０からイ
メージメモリ２７にロードする（同５３）。

イメージメモリ２７にロードされた画像の細線化処理の
流れは、第５図の５４から始まり６８で終了する細線化
ループにおいて実行され、最初に並列型細線化処理が行
われ（第５図の５４〜６ｌ）２次に逐次型細線化処理が
実行される（第５図の６２〜６６）。

並列型細線化処理は、第２図の並列型細線化部２４にお
いて実行され、まず分割画面の上部に重複領域があるか
否かを判定しく第５図の５４）。

ある場合その重複領域に並列型の細線化を実行し。

削除画素にフラグをつける（同５５）。このフラグは実
際に対象となる画素を削除すると、並列型細線化を行う
領域と逐次型細線化を行う領域との境界部分が正しい細
線化画像にならないからである。

分割画面の上部の重複領域についての細線化が終了する
と（または上部に重複領域がない場合）次に分割画面の
下部に重複領域があるか否かを判定しく同５６）、ある
場合は同様に並列型の細線化処理を行う（同５７）。以
下１分割画面の右部左部について同様に並列型の細線化
処理を行う（同５８〜６１）。

この後、第２図の逐次型細線化部２５において逐次型細
線化処理が開始される。この処理は１画面内の全ての図
形について２図形の輪祁を一周するよう、追跡を行いな
がら逐次型の細線化処理を行う（同６２．６３）。もし
この追跡において重複領域に入った場合は（同６４）、
追跡だけを行うが、上記の並列型細線化処理においてフ
ラグが付された画素を検出するとその画素を削除しく同
６５）１重畳領域でないと逐次型細線化を行う（同６６
）。そして１画面の全てに対してまだ細線化可能な点が
存在するか否かを判定し、ある場合は、再び５４に戻っ
て細線化のループを再開する（同６７．６８）。

最後に細線化可能な点がなくなると、折線返信処理が第
２図の折線近似部２６において実行され（同６９）、そ
の後他の未処理の分割画面についての処理に移る（同７
０）。

次に細線化処理の内容を第６図（ａ）、第６図（１））
に示す具体例を用いて説明する。

第６図（ａ）は、並列型細線化処理の具体例を示し。

第６図（ｂ）は逐次型細線化処理の具体例を示す。

第６図（ａ）においてＡ、は細線化する前の原画の画像
データであり１画像を示す■は画素値１の黒画素を示し
、その他の白画素は図示しない。

第５図の並列型細線化処理が実行されると、並列型細線
化部２４（第２図）により重畳領域で１画素分の細線化
処理を行い１重畳領域の情報は画面分割テーブル（第４
図）に格納されており、これを参照することにより並列
型の細線化を行う領域を設定する。並列型の細線化では
、実際の画素の削除は行わず、第６図（ａ）のＢ、に示
すように削除される画素の画素値を変える（フラグを付
す）だけとする。図の例では画素値を■に変更している
。

このように３画素値を変更するには並列型細線化処理を
行う領域の各画素は９通常は１ビツトで表すのに対して
少なくとも２ピント（２ピント目はフラグに対応）を割
当てればよい。

次に逐次型細線化処理では９重複領域以外の内部の画像
データについて細線化処理を行う。この場合は削除対象
の画素は実際に削除し９重複領域を追跡中に細線化によ
ってフラグの付いた画素を検出すると追跡を行いつつそ
の画素を削除する。

この様子を第６図（ａ）のＣ０及びり、に示す。

このような処理を１画面中の全ての図形について、これ
以上細線化されるものが無くなるまで繰り返し行うこと
により境界部分で食い違いのない細線化を行うことがで
きる。

上記の第２図の実施例の構成では、並列型細線化部２４
と逐次型細線化部２５を別々の処理部として示したが、
汎用プロセッサによって構成しファームウェアを切り換
えることで一つの処理部として構成することは可能であ
り、装置のコスト上は一つにする方が有利である。

さらに、上記の実施例では、並列型細線化処理（第５図
の５５．５７．５９．６１）で削除画素にフラグをつけ
ていたが、その方式では１画素を削除対象の画素か否か
を区別するため各画素に最低２ピントを割当てる必要が
あるため、イメージメモリの容量が増大する。これを避
けるため１画素にフラグを付けない方法を第６図ら）を
用いて説明する。

第６図（ｂ）のＡ、に示す原画の画像データに対して並
列型細線化を実行した時、境界部分以外の重複領域につ
いては細線化により削除対象となった画素を削除するが
、同図のＢ、に示すように境界部分（図の点線で区切る
部分）については、細線化結果（削除対象のデータと削
除されないデータとからなる）のみを−旦別のワーキン
グメモリ（１示せず）に退避する。

この後、逐次型細線化処理が実行されるが２重複領域に
ついては第６図（ト））のＣ９のように追跡だけが行わ
れ（第５図の６５において、フラグについての処理は行
われない）、逐次型細線化が終了した後、上記ワーキン
グメモリに退避した境界部分の画素を元の境界部分に戻
して同図り、のような最終状態が得られる。この方式に
より得られた結果は、第６図（ａ）に示す方式と同しに
なることば図により明らかである。

［発明の効果］ 本発明によれば大きな図面を計算機に入力するだめの細
線化処理を大容量のイメージメモリを使用することなく
実現すると同時に分割画面の細線化を行うと隣接画面と
の境界において発生する細線のずれを防止することがで
きる。

さらに画面分割による細線化において、汎用プロセッサ
による処理に適した逐次型細線化で行うことができ、処
理速度の向上とハードウェアを使用せずに済むなどの効
果がある。

【図面の簡単な説明】

第１図は本発明の原理構成図、第２図は実施例の折線近
似化装置の構成図１第３図は分割の具体例を示す図、第
４図は画面分割テーブルの例を示す図、第５図は実施例
の処理フロー図、第６図（ａ）は並列型細線化処理の具
体例、第６図（ｂ）は逐次型細線化処理の具体例、第７
図は分割細線化の例、第８図は重畳領域を設けた画面分
割の説明図、第９図は重畳領域を設けた分割画面の細線
化の例、第１０図は細線化の概要図、第１１図は逐次型
細線化方式の問題説明図である。 第１図中。 】０：処理部 １１：画像分割手段 １２：並列型細線化処理手段 Ｉ３：逐次型細線化処理手段 １４：イメージデータ格納部 １５：分割テーブル １６：メモリ

Claims (1)

1. 【特許請求の範囲】 処理対象画面を複数の領域に分割して、各分割画面の画
   像について細線化を行って得られた各細線化分割画像を
   統合して全体の細線化画像を得る二値画像の細線化方式
   において、画面全体のイメージデータをイメージデータ
   格納部（１４）に備え、 処理部（１０）は、隣接する分割画像と重畳領域を持つ
   よう画面全体を所定の大きさに分割して分割テーブル（
   １５）に格納する画面分割手段（１１）と、分割画面の
   イメージデータをメモリ（１６）に取り出して各分割画
   面の重畳領域の画像について並列型細線化を行う並列型
   細線化処理手段（１２）と、各分割画面の重畳領域を除
   く領域について逐次型の細線化を行うと共に上記並列型
   細線化により得られた処理結果との結合を行う逐次型細
   線化処理手段（１３）とを備えることを特徴とする二値
   画像の細線化方式。