JPH0377174A - 輪郭データの出力順序決定方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、画像処理の１つである輪郭追跡処理におい
て、追跡した輪郭データを出力する順序を決定する方式
に関するものである。

〔従来の技術〕

第８図は従来の輪郭データ出力方式の１例を示すもので
、図において、（１）はカメラやスキャナ等によって白
黒の２値情報として記録されたイメージファイル、（２
）はイメージファイル（１）より輪郭線を追跡する輪郭
追跡部、（３）は追跡された輪郭線を座標系列として記
録する点列ファイル、（４）は輪郭線の座標系列を加工
する輪郭データ加工部、（５）は加工されたデータを記
録する加工データファイル、（６）は加工データファイ
ルより出力ファイル（７）を作成する輪郭データ出力部
である。

次に動作について説明する。輪郭追跡部（２）はイメー
ジファイル（１）の２値情報として記録された画像デー
タについて公知のアルゴリズムにより輪郭線の追跡を行
う。−例として、まず輪郭線追跡のための追跡開始点を
見つけることからはじめ、順に追跡を行う過程で追跡し
終わった点に次々に追跡済みのマークを付けながら追跡
を進行し、追跡を一巡した時点で１木の輪郭線を求める
。この手順を繰り返すことで画像中のすべての輪郭線を
抽出する。このとき、追跡開始点を探すためにファイル
（１）の中の例えば左上画素を初期点としてラスク走査
を行う。第５図にイメージファイル（１）の内容の一例
と輪郭追跡開始点（最初の輪郭点）を見つけるまでの走
査の様子を示す。

ここで輪郭点とは注目画素を中央にみた８近傍を第７図
とするとき、注目点が黒で、１，３゜５．７のうち少な
くとも１つが白、かつ処理済マークのついていない点の
ことである。

輪郭線の追跡は、輪郭点を常に左（または右）に見るよ
うな方向で８近傍のいずれかに位置する輪郭点を次々に
追跡し、追跡し終った輪郭点は処理済マークをつけ、座
標データを点列ファイル（３）に記録する。

第６図（ａ）　、　（ｂ）に第５図を輪郭線追跡した結
果と点列ファイル（３）の内容を例として示す。

輪郭データ加工部（４）は、点列ファイル（３）の内容
に対してベクトル化等の加工を行い、結果を加工データ
ファイル（５）に記録する。

輪郭データ出力部は加工データファイル（５）を所定の
出力データ形式に変換し、所定の記録領域に転送する。

〔発明が解決しようとする課題］ 従来の輪郭データ出力方式は以上のように構成されてい
たので、複数の輪郭線がある場合、出力順序は各輪郭の
追跡開始点が見つかった順序になる。したがって、輪郭
線が２重以上のループになっている場合、第９図に示す
ように、外側の輪郭線から順に出力されることになり、
この出力データを材料の切断加工用に使用する場合、内
側の輪郭線を切断する前に、外側の輪郭線を切断するこ
とによって材料が欠落するなどの事態が生じ、これを回
避するために、人が介して輪郭線の包含関係を判断して
切断加工用出力順序を再構成するという手間が必要であ
った。

この発明は上記のような問題点を解消するためになされ
たもので、内包される輪郭線より順に出力データを構成
することにより、出力された順序に切断加工等を行って
も何ら不具合の生じない輪郭データ出力方式を得ること
を目的とする。

（課題を解決するための手段） この発明に係る輪郭データの出力順序決定方式は、複数
の輪郭線について、内部ループか外部ループかを判定し
、また各輪郭線の縦方向、横方向の最大値、最小値を検
出し、上記判定結果及び検出結果をもとに、各輪郭の包
含関係を識別して、内包される輪郭より順に自動的に出
力データを構成するようにしたものである。

〔作用〕

この発明における包含関係の識別方法は、輪郭線の縦方
向、横方向の最大値、最小値とともに、内部ループ、外
部ループの情報と合わせて使用することにより、必要か
つ十分な条件で内包される輪郭を選択し、内包される順
に輪郭データを出力する。

（実施例〕 以下、この発明の一実施例を図について説明する。第１
図において、（１）はイメージファイル、（２）はイメ
ージファイル（１，）より輪郭線を追跡し、同時に該輪
郭線が外部ループか内部ループかを判定する輪郭追跡部
、（３）は追跡された輪郭線を座標系列として記録する
点列ファイル、（８）は各輪郭線のマクロな情報を記録
する輪郭線ファイル、（９）は各輪郭線の縦方向、横方
向のそれぞれ最大値、最小値を検出し、輪郭線ファイル
（８）に記録する最大値、最小値検出部、（１０）は輪
郭線ファイル（８）を検索して輪郭線の包含関係を識別
し、内包される輪郭線から順に、輪郭データ加工部（４
）に処理を指示する包含関係認識部、（４）は上記指示
の順に点列ファイル（３）の内容を加工する輪郭データ
加工部、（６）は加工データファイル（５）より出力フ
ァイル（７）を作成する輪郭データ出力部である。

次に上記構成に従って動作を説明する。

輪郭追跡部（２）が、イメージファイル（１）より輪郭
線の追跡を行い点列ファイル（３）を作成する手法は従
来技術と同様であるが、輪郭追跡開始点を見つけたとき
に当該輪郭線が外周ループであるか内周ループであるか
を判別して、輪郭線ファイル（８）に記録する。

外周ループと内周ループの判別は、例えば輪郭追跡開始
点を探すのに、第５図のように左上から順に上から下に
ラスク走査していく場合には、外周ループの輪郭追跡開
始点は右上の画素（第７図の６の点）が白、内周ループ
の輪郭追跡開始点は右上の画素が黒となるので、容易に
判別可能である（第６図（ａ））。

輪郭線ファイル（８）は追跡された各輪郭線毎のマクロ
な情報を記録するもので、第２図の如きフォーマットで
ある。

処理済フラグは最初は全て′Ｏ”で未処理を表す。内周
外周フラグは当該輪郭線が内周ループならＯ゛、外周ル
ープなら“１”とする。ポインタは点列ファイル上で当
該輪郭線の追跡開始点が記録されているアドレス、画素
数は当該輪郭線の点数であり、以上は輪郭追跡部（２）
が記録する。

最大値、最小値検出部は、各輪郭線について、点列ファ
イルを参照して、縦方向（ｙ方向とする）、横方向（Ｘ
方向とする）のそれぞれの最大値、最小値を検出し、輪
郭線ファイルに記録する。

包含関係認識部（１０）は輪郭線ファイルの内容によっ
て各輪郭間の包含関係を認識し、内包されるものから順
に輪郭データ加工部に処理を指示する。第５図のフロー
チャートに従ってそのアルゴリズムを述べる。

Ｎ個の輪郭線が登録されている輪郭線ファイルのｉ番目
の輪郭をＣ１で表し、ＣＩの処理済フラグをＦｌ（ｉ）
　、外周内周フラグをＦ２（ｉ）　、　ｘの最大値、最
小値、ｙの最大値、最小値をそれぞれＸ　ｆｆ１ａｘ（
ｔ）、Ｘ　ｍ＋ｎ（１）、　　３Ｆ　ｍ１ｘ（１）、　
　ｙｍ＋ｎ（１）とする。

まず最初の輪郭をとり（１−＋ｉ）、ｃ、が未処理なら
ＣＩに内包される輪郭が存在しないかを以下のように調
べる。輪郭線ファイルの最初から未処理の輪郭ＣＪ　（
Ｆｌ（ｊ）　＝　Ｏ）をとり、Ｃ，とＣ，で外周と内周
の種別を調べ、Ｃ，が外周でＣ」も外周（ｐ２（ｔ）　
＝ｐ２（ｊ）　　＝　１　）またはＣＩが内周でＣ１が
内周（Ｆ２（ｉ）　＝Ｆ２（ｊ）　＝　Ｏ）ならＣ，は
Ｃ１に直接内包されないと判定する。

Ｆ２（ｉ）≠Ｆ２（ｊ）の場合はＣ４の外接矩形がＣＩ
の外接矩形の内包されるかどうかを調べる。すなわち次
の４式 ％式％：：７ の全てが満たされる場合Ｃ」はＣＩに内包されると判定
する。

Ｃ，がＣ１に内包されると判定された場合はＣ」に内包
される未処理の輪郭がないかを調べるためＣ」−Ｃ，と
して再びｊ＝１より同様の処理を行う。

Ｃ，がＣ，に内包されないと判定された場合はｊ＋ｉ−
ｊとして次の輪郭について調べるが、ｊ＝Ｈの場合には
全ての輪郭について調べたのでＣ１に内包される未処理
の輪郭は存在しない。このとき包含関係認識部は輪郭デ
ータ加工部（４）を指示して輪郭Ｃ１に対してベクトル
化等の加工を行い、処理結果を加工データファイル（５
）に記録する。

本処理が終了すると、ＣＩを処理済（１−Ｆｌ（ｉ））
にして本アルゴリズムの最初にもどって同様の処理を繰
り返す。

以上の処理を全ての輪郭データの処理済フラグが１にな
るまで繰り返す。

ここで、先にＣＩとＣｊが両方とも外周、または両方と
も内周のときはＣ」はＣＩに直接内包されないと判定し
たがその場合第４図（ａ）でＣ３はＣ１に内包されない
ことになる。しかしこの場合、ともに外周であるＣ２と
Ｃ３の間に内周Ｃ２が存在し、本アルゴリズムではＣ２
が０１に内包され、Ｃ３が０２に内包されることになる
ので０１とＣ３の包含関係は間接的に正しく判定される
。このようにするのは例えば第４図（ｂ）のような場合
、Ｃ２の外接矩形はＣ１の外接矩形に内包されるが、Ｃ
２はＣ１には内包されないことからもわかるように、外
接矩形の包含関係だけでは正確な包含関係が判定できな
いからである。

以上の処理によって加工データファイル（５）には内包
される輪郭から順に加工データが生成される。

輪郭データ出力部（６）は加工データファイルの内容を
所定の出力データ形式に変換し、所定の記録領域に転送
を行い内包される輪郭の順序からなる出力ファイル（９
）を作成する。

なお、上記実施例では輪郭データ加工部に包含関係認識
部の機能を作用させたが、輪郭データ加工部は追跡され
た順に処理を行い、輪郭データ出力部に包含関係認識部
の機能を作用させても同様の効果が得られ、内包される
輪郭の順に出力ファイルを作成することができる。

〔発明の効果〕

以上のように、この発明によれば、輪郭線の外接矩形の
包含関係と、外周、内周の種別によって輪郭線の包含関
係を認識し、内包される輪郭から順に出力データを作成
するようにしたので、複雑な形状であっても正確に包含
関係を識別でき、出力された順に切断等の加工を行って
も材料の欠落がない輪郭出力データが得られる効果があ
る。

【図面の簡単な説明】

第１図はこの発明の輪郭データ出力順序決定方式の一実
施例を表す図、第２図は輪郭線ファイルの例を示す図、
第３図は包含関係認識のアルゴリズムを示すフローチャ
ート、第４図は包含関係の説明図、第５図は輪郭追跡開
始点のラスク走査を表す図、第６図は輪郭追跡結果と点
列データを示す図、第７図は注目点の８近傍を表す図、
第８図は従来の輪郭データ作成方法を表す図、第９図は
従来方式の輪郭データ出力順序を表す図である。 図において、（１）はイメージファイル、（２）は輪郭
追跡部、（９）は最大値最小値検出部、（８）は輪郭線
ファイル、（１０）は包含関係認識部。 なお、各図中、同一符号は同−又は相当部分を示す。

Claims (1)

【特許請求の範囲】
1. ２値情報として入力されたイメージより輪郭を追跡する
   輪郭追跡部と、当該輪郭が外周であるか内周であるかを
   判定して当該輪郭の縦方向、横方向の最大値、最小値を
   検出する検出部と、上記判定部の出力及び上記検出部の
   出力を記録する輪郭線ファイルと、このファイルデータ
   を検索することによって各輪郭間の包含関係を認識する
   認識部とを有し、内包される輪郭から順次出力すること
   を特徴とする輪郭データの出力順序決定方式。