JPH10162155A - 輪郭抽出装置 - Google Patents

Abstract

(57)【要約】 【課題】 格子状に配列された画像または地図情報等に
おいて、２値化された情報のうち、どちらか一方の情報
をもつ図形パターンの輪郭を抽出しようとする場合に、
抽出するための検索回数、即ち抽出時間の増加を防ぐ。 【解決手段】 ２つのパターン図（基本２値化パターン
図及び格子点２値化パターン図）の使用及びそれらパタ
ーン図の組み合わせによる抽出方向の分類化により、基
本２値化パターン図の２格子のみを参照して輪郭抽出が
実行できるので、抽出するための検索回数と抽出時間の
増加を防ぐことができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は２値化された画像ま
たは地図情報等に用いられる輪郭抽出装置に関し、特に
格子状に配置された図形の輪郭抽出装置に関する。

【０００２】

【従来の技術】格子状に配列された画像または地図情報
等において、２値化された情報のうち、どちらか一方の
情報をもつ図形パターンの輪郭を抽出しようとする場合
を考える。以下の記述において、輪郭を抽出しようとす
る図形の２値情報を第１の情報と記し、当該情報を論理
１に対応させる。

【０００３】図２は５×５のそれぞれの格子に対して２
値化された情報を与えた図である。ここでは、図２にお
ける格子の情報を空白と斜線で２値化し、空白の格子を
論埋０、斜線の格子を論理１に対応させる。従って、斜
線の格子（論理１）によって構成される図形が、輪郭を
抽出しようとする図形である。図２において、例えば、
輪郭抽出開始格子点を検索する方向を左から右かつ下か
ら上とすると、輪郭抽出順序は格子点６→格子点７→格
子点８→格子点９→格子点１０→格子点１１→格子点１
２→格子点１３→格子点１４→格子点１５→格子点６と
なる。

【０００４】従来はある格子点（例えば格子点８）を抽
出した後、次に論理１の格子点（例えば格子点９）を抽
出するためには、隣接する８方向の格子点（格子点７、
格子９、格子点１０、格子点１１、格子点１２、格子点
１６、格子点１７、格子点１８）を参照する必要があっ
た（特開平４−２９９４７３参照）。

【０００５】

【発明が解決しようとする課題】上述のように従来の抽
出方法の第１の問題点は、抽出するための検索回数、つ
まり抽出時間が増加してしまうことである。その理由
は、前記論理１の新たな格子点を抽出する際に、隣接す
る８方向の格子点を参照する必要性があるためである。

【０００６】本発明の目的は、２つのパターン図（基本
２値化パターン図及び格子点２値化パターン図）の組み
合わせによる輪郭抽出方向の分類化により、２値情報の
うちいずれか一方の情報をもつ輪郭格子点を接続した閉
ループを容易に抽出し、更に格子点を抽出するための検
索回数の削減、つまり抽出時間を軽減させ、処理の高速
化を図ることである。

【０００７】

【課題を解決するための手段】本発明の第１の格子状図
形の輪郭抽出装置は、２次元格子を形成して配列されて
いる複数の単位格子の各々に、第１、第２の論理値に対
応させて２値化された画像の２値情報が配置されて成る
格子状図形（基本２値化パターン図）の、第１の論理値
に対応する第１の情報をもつ図形パターンの輪郭を抽出
する格子状図形の輪郭抽出装置であって、前記基本２値
化パターン図と基本２値化パターン図の第１の論理値の
格子の４格子点に再度第１の論理値を、それ以外の格子
点に第２の論理値を格納して生成した格子状図形（格子
点２値化パターン図）を併用して輪郭抽出を実行し、ｎ
×ｍの格子数をもつ基本２値化パターン図から生成した
（ｎ＋１）×（ｍ＋１）の格子数をもつ格子点２値化パ
ターン図において、前記基本２値化パターン図の輪郭を
構成する、第１の論理値をもつ単位格子点の１つを輪郭
抽出開始格子点として初期設定し、当該輪郭抽出開始格
子点を検索する方向を４方向（左から右へかつ下から上
へ、右から左かつ下から上へ、左から右へかつ上から下
へ、右から左へかつ上から下へ）の中から予め選択した
後、当該輪郭抽出開始格子点を第０格子点とし、第２の
論理値に対応する第２の情報をもち、かつ、第０格子点
に隣接する単位格子点に対する第０格子点の方向を第０
格子点の抽出方向と定め、以後、基本２値化パターン図
と格子点２値化パターン図の組み合わせによる抽出方向
の分類表に従って第０格子点に戻るまで輪郭抽出及び輪
郭線の描画を同時に行い、第０格子点を出発して再び第
０格子点に戻るまでにたどった格子点を当該図形パター
ンの輪郭とする。

【０００８】

【発明の実施の形態】次に本発明の輪郭抽出装置の一実
施の形態を説明する。図１は本発明の輪郭抽出装置のブ
ロック図を示したものである。まず、ブロック１（基本
２値化パターン入力部）で基本２値化パターン図を入力
し、それを基にブロック２（格子点２値化パターン生成
部）で格子点２値化パターン図を生成する。次に、ブロ
ック３（輪郭抽出開始点検索方向選択部）で前記２つの
パターン図から輪郭抽出開始格子点の検索方向を図８に
示す４方向から選択し、ブロック４（輪郭抽出開始点検
索部）で輪郭抽出開始格子点を検索する。ブロック５
（輪郭抽出／表示部）では、格子点２値化パターン図に
おいて、第１の論理値をもつ単位格子点の抽出が全て終
了するまで、図６の分類表に基づいて輪郭抽出を実行
し、更に輪郭線を描画する。ブロック４及びブロック５
の処理は格子点２値化パターン図の検索が全て終了する
まで反復処理する。

【０００９】このように、前記分類表を用いることによ
り、基本２値化パターン図のうち２つの格子の情報のみ
を参照することで、あらゆる格子状図形パターンの輪郭
抽出を高速にしかも容易に実行することが可能となる。

【００１０】次に、本発明の実施の形態の勲作につい
て、図（図６、図７、図８、図９、図１０、図１１、図
１２、図１３、図１４、図１５、図１６）を参照にして
詳細に説明する。ここで、まず輪郭を抽出しようとする
図形の２値情報を第１の情報と印し、該情報を例えば論
理１に対応させる。

【００１１】図７は格子点２値化パターン生成部（ブロ
ック２）の流れ図である。ｍ×ｎの基本２値化パターン
図（図５）が入力された後、まず、格子点２値化パター
ン図として、（ｍ＋１）×（ｎ＋１）のフレーム（図
５）を用意し、全ての格子（ｉ，ｊ）に論理０を格納し
て初期化を行う（ステップ１０１）。次に基本２値化パ
ターンの各格子（ｉ，ｊ）を順次検索し（ステップ１０
２）、現在着目している格子（ｉ，ｊ）が論理１か否か
判定する（ステップ１０３）。もし、論理１でなけれ
ば、再度検索を開始し、論理１ならば、格子点２値化パ
ターン図の格子（ｉ，ｊ），（ｉ＋ｌ，ｊ），（ｉ，ｊ
＋ｌ），（ｉ＋ｌ，ｊ＋ｌ）に論理１を格納する（ステ
ップ１０４）。以後、基本２値化パターン図の全ての格
子の検索が終了するまで、同様な操作を繰り返す（ステ
ップ１０５）。

【００１２】格子点２値化パターン図の生成が終了した
後、格子点２値化パターン図上における初期値を決定す
るために検索方向を選択する。選択できる検索方向は図
８に示す様に４方向（ステップ２０２、２０５、２０
８、２１１）とする。

【００１３】次に、格子点２値化パターン図上の輪郭抽
出開始格子点を検索する（図９、１０）。検索手法は、
検索方向によって異なる（ステップ３０２、３０９、３
１６、３２３）。格子点２値化パターン図上で論理１が
検索され（ステップ３０３、３１０、３１７、３２
４）、更に、前記論理１の格子（ｉ，ｊ）によって一意
に決まる基本２値化パターン図上の３格子の値（ステッ
プ３０４、３１１、３１８、３２５）が０ならば、それ
を輪郭抽出開始格子点と判定する。

【００１４】次に、輪郭抽出及び輪郭線描画を実行す
る。具体的な処理の流れ図を図１１、図１２、図１３、
図１４、図１５に示す。まず、図９、１０によって格子
点２値化パターン図上で輪郭抽出開始格子点が検索され
た時の抽出方向を判定する（ステップ４０１、４１４、
４１５、４１６）。次に、図６の基本２値化パターン図
と格子点２値化パターン図の組み合わせによる抽出方向
の分類表に従って、処理（ステップ４０２、４０６、４
１０、５０２、５０６、５１０、６０２、６０６、６１
０、７０２、７０６、７１０）を進める。

【００１５】分類表では、２値化パターン図の現着目格
子点が抽出された方向と基本２値化パターン図の２格子
の論理値によって次の格子点２値化パターン図の着目格
子点の抽出方向を決めている。例えば、図６の抽出方向
５９は、格子点２値化パターン図上の現着目格子点
（ｉ，ｊ）が（ｉ−ｌ，ｊ）の方向から抽出され、かつ
現着目格子点（ｉ，ｊ）によって一意的に決まる基本２
値化パターン図上の格子が（ｉ−ｌ，ｊ）＝０、（ｉ，
ｊ）＝１ならば、次の格子点２値化パターン図上の着目
格子点を（ｉ，ｊ＋ｌ）とすることを意味している。こ
れは、図１１、１２のステップ４０２の処理である。

【００１６】次に輪郭線描画処理を実行する（ステップ
４０３、４０７、４１１、５０３、５０７、５１１、６
０３、６０７、６１１、７０３、７０７、７１１）。処
理の流れ図を図１６に示す。まず格子点２値化パターン
図の着目格子点が抽出開始格子点であるか否か判定する
（ステップ８０１）。抽出開始点であれば、格子点座標
の入れ替え処理を行った後（ステップ８０７）、輪郭線
描画処理を終了し、そうでなければ、現着目格子点が前
着目格子点と同一の行番号または列番号であるか否か判
定する（ステップ８０２）。もし、行番号または列番号
が同一であれば、格子点座標の入れ替え処理を行った後
（ステップ８０９）、輪郭線描画処理を終了し、そうで
なければ、直前の着目格子点と線描画を実行していない
最も古い着目格子点を直線で結び（ステップ８０３）、
現着目格子点を直前の着目格子点とする処理を実行して
輪郭線描画の処理を終了する。

【００１７】次に、図１１、図１２、図１３、図１４、
図１５において、次着目格子点を現着目格子点に置き換
え（ステップ４０４、４０８、４１２、５０４、５０
８、５１２、６０４、６０８、６１２、７０４、７０
８、７１２）、抽出開始格子点に戻ったか否かを判定し
（ステップ４０５、４０９、４１３、５０５、５０９、
５１３、６０５、６０９、６１３、７０５、７０９、７
１３）、戻った場合には描画処理を実行して（ステップ
４１７）、輪郭線抽出及び輪郭線描画の処理を終了す
る。

【００１８】

【実施例】

［１］実施例の構成の説明 次に、本発明の実施例について図面を参照して説明す
る。図２は５×５の２値化された情報をもつ格子状図形
に本発明装置を適用して抽出された輪郭の実施例であ
る。ここでは、格子状図形は、行方向と、それと直角に
交わる列方向に配列された２次元格子図形で、情報を空
白部分と斜線部分の２値に分け、斜線部分の輪郭が抽出
される。以下の記述において、空白部分を論理０に対応
させ、斜線部分を論理１に対応させる。また、行方向を
左右と記し、列方向を上下と記す。２次元格子の単位格
子を格子、単位格子点を格子点と記す。 ［２］実施例の動作の説明 図３は図２の実施例の各格子に論理０及び論理１を格納
したパターン図である（以下、基本２値化パターン図と
する）。論理１の輪郭線（格子点１９→格子点２０→格
子点２１→格子点２２→格子点２３→格子点２４→格子
点２５→格子点２６→格子点２７→格子点２８→→格子
点１９）を抽出することを目的とする。次に、前記５×
５の配列をもつの図３の基本２値化パターン図を基に、
新たに２値化パターン図を生成する。まず、（５＋１）
×（５＋１）、つまり６×６ののフレームを用意し、全
ての格子（ｉ，ｊ）に論理０を格納して初期化を行う
（ステップ１０１）。次に基本２値化パターンの各格子
（ｉ，ｊ）を順次検索し（ステップ１０２）、現在着目
している格子（ｉ，ｊ）が論理１か否か判定する（ステ
ップ１０３）。もし、論理１でなければ、再度検索を開
始し、論理１ならば、格子点２値化パターン図の格子
（ｉ，ｊ），（ｉ＋１，ｊ），（ｉ，ｊ＋ｌ），（ｉ＋
ｌ，ｊ＋ｌ）に論理１を格納する（ステップ１０４）。
以後、基本２値化パターン図の全ての格子の検索が終了
するまで、同様な操作を繰り返す（ステップ１０５）。
その結果、図４のパターンが生成される。

【００１９】格子点２値化パターン図の生成が終了した
後、格子点２値化パターン図上における初期値を決定す
るために検索方向を選択する。選択できる検索方向は図
８に示す様に４方向（ステップ２０２、２０５、２０
８、２１１）であるが、ここでは、検索方向を左から右
かつ下から上（ステップ２０２の判定条件においてｙｅ
ｓ、ｔ＝１）とする。

【００２０】次に、格子点２値化パターン図上の輪郭抽
出開始格子点を検索する（図９、１０）。ｔ＝１なの
で、ステップ３０４の判定条件により、図４の格子２９
が検索される。図４の格子２９は図３の格子点１９であ
る。

【００２１】次に、輪郭抽出及び輪郭線描画を実行す
る。図１１、１２のステップ４０１の判定条件において
ｙｅｓとなり、ステップ４０２で図６の基本２値化パタ
ーン図と格子点２値化パターン図の組み合わせによる抽
出方向の分類表（抽出方向５９）に従って、ｙｅｓの処
理が実行させる。着目格子点が輪郭抽出開始格子点であ
るので、輪郭表示処理（ステップ４０３）は実行され
ず、ステップ４０６のｎｏの判定により図１５のステッ
プ７０２が実行される。ここで、格子４１が論理０及び
格子４６が論理１なので、ステップ７０２はｙｅｓと判
定され、ステップ７０３に進むが、格子点２０は格子点
１９と同一の列上にあるため、輪郭線は描画されない。
ステップ７０５の判定はｎｏなので、再びステップ７０
２が実行される。ここで、格子４２が論理０、格子４７
が論理１なので、ステップ７０２はｙｅｓと判定され、
ステップ７０３に進むが、格子点２１は格子点１９と同
一の列上にあるため、輪郭線は描画されない。ステップ
７０５の判定はｎｏなので、再びステップ７０２が実行
させる。

【００２２】ここで、格子４７が論理１、格子４８が論
理０なので、ステップ７０２及びステップ７０６はｎｏ
と判定され、ステップ７１０においてｙｅｓと判定され
る。ステップ７１１では格子点２２が格子点１９と同一
の列上にあるため、輪郭線は描画されない。ステップ７
１３の判定はｎｏなので、ステップ図１１、１２の４０
２が実行されるが、ｎｏと判定され、ステップ４０６が
実行される。ここで格子５２が論理０、格子５３が論理
０なので、ステップ４０６はｙｅｓと判定され、ステッ
プ４０７に進む。ここで、格子点２３が格子１９と同一
の列または同一の行上に存在しないので、格子点１９か
ら格子点２２まで輪郭線を直線で結ぶ。ステップ４０９
の判定は、ｎｏなので、図１３のステップ５０２が実行
される。ここで、格子４６が論理１、格子５１が論理０
なので、ステップ５０２はｙｅｓと判定され、ステップ
５０３に進むが、格子点２４が格子点２２と同一の列ま
たは同一の行上に存在しないので、格子点２２から格子
点２３まで輪郭線を直線で結ぶ。輪郭線は描画されな
い。ステップ５０５の判定はｎｏなので、再びステップ
５０２が実行される。ここで、格子４５が論理１、格子
５０が論理１なので、ステップ５０２及びステップ５０
６はｎｏと判定され、ステップ５１０において、ｙｅｓ
と判定される。ステップ５１１では格子点２５が格子点
２３と同一の列上に存在するため、輪郭線は描画されな
い。ステップ５１３はｎｏとなるので、図１１、１２の
ステップ４０２が実行される。

【００２３】ここで、格子５５が論理０、格子５６が論
理０なので、ステップ４０２はｎｏと判定され、ステッ
プ４０６において、ｙｅｓと判定される。ステップ４０
７では、格子点２６が格子点２３と同一の列または同一
の行上に存在しないため、格子点２３から格子点２５ま
で輪郭線を直線で結ぶ。ステップ４０９の判定はｎｏな
ので、図１３のステップ５０２が実行される。ここで、
格子４９が論理０、格子５０が論理１なので、ステップ
５０２はｎｏと判定され、ステップ５０６において、ｙ
ｅｓと判定される。ステップ５０７では、格子点２７が
格子点２５と同一の列または同一の行上に存在しないの
で、格子点２５から格子点２６まで輪郭線を直線で結
ぶ。ステップ５０９の判定はｎｏなので、ステップ６０
２が実行される。ここで、格子４４が論理０、格子４５
が格子１なので、図１４のステップ６０２及びステップ
６０６がｎｏと判定され、ステップ６１０において、ｙ
ｅｓと判定される。ステップ６１１では格子点２８が格
子点２６と同一の列または同一の行上に存在しないの
で、格子点２６から格子点２７まで輪郭線を直線で結
ぶ。６１３の判定は輪郭線抽出開始格子点に戻ったので
ｙｅｓと判定され、図１１、１２のステップ４１７にお
いて格子点２７から格子点１９まで輪郭線を直線で結ん
で輪郭線抽出及び輪郭線描画の処理を以上をもって終了
する。

【００２４】次に本発明の他の実施例を述べる。図１７
は５×５の２値化された情報をもつ格子状図形に本発明
の装置を適用して抽出された輪郭の第２の実施例であ
る。前記実施例と同様、格子状図形は、行方向と、それ
と直角に交わる列方向に配列された２次元格子図形で、
情報を空白部分、斜線部分及び塗りつぶしの部分の３値
に分け、空白部分を論理０、斜線部分を論理１、塗りつ
ぶしの部分を論理２に対応させる。２次元格子の単位格
子点を格子点と記す。

【００２５】前記実施例の動作と同様な処理によって、
斜線部分の輪郭（格子点６０→格子点６１→格子点６２
→格子点６３→格子点６４→格子点６５→格子点６６→
格子点６７→格子点６８→格子点６９→格子点７０→格
子点７１→格子点７２→格子点６０）及び塗りつぶしの
部分の輪郭（格子点７３→格子点７４→格子点７５→格
子点７６→格子点７３）の抽出が可能となる。

【００２６】このような格子状図形パターンの形態は、
地図情報等の等高線の描画に応用できる。

【００２７】

【発明の効果】第１の効果は、２つのパターン図（基本
２値化パターン図及び格子点２値化パターン図）の使用
及びそれらパターン図の組み合わせによる抽出方向の分
類化により、この装置は同一の２値情報をもつ輪郭格子
点を接続して閉ループを容易に抽出することができ、更
に格子点を抽出するための検索回数の削減、つまり抽出
時間を軽減し、処理の高速化が図れることである。

【００２８】その理由は、２格子のみの参照で輪郭抽出
を実行しているからである。

【図面の簡単な説明】

【図１】本発明の輪郭抽出装置のブロック図である。

【図２】５×５の２値化された情報をもつ格子状図形に
図１の輪郭抽出装置を適用して抽出された輪郭の実施例
を示す図である。

【図３】図２の実施例の各格子に論理０及び論理１を格
納したパターン図（基本２値化パターン図）。

【図４】図３の基本２値化パターンにおける論理１の周
囲４格子点を論理１とし、それ以外を論理０としたパタ
ーン図（格子点２値化パターン図）。

【図５】基本２値化パターン図及び格子点２値化パター
ン図の配列番号。

【図６】基本２値化パターン図及び格子点２値化パター
ン図の組み合わせによる抽出方向の分類表。

【図７】格子点２値化パターン生成部の流れ図。

【図８】輪郭抽出開始点検索方向選択部の流れ図。

【図９】輪郭抽出開始点検索部の流れ図。

【図１０】輪郭抽出開始点検索部の流れ図。

【図１１】輪郭抽出／表示部の流れ図。

【図１２】輪郭抽出／表示部の流れ図。

【図１３】輪郭抽出処理（輪郭抽出／表示部）の流れ
図。

【図１４】輪郭抽出処理（輪郭抽出／表示部）の流れ
図。

【図１５】輪郭抽出処理（輪郭抽出／表示部）の流れ
図。

【図１６】輪郭抽出処理（輪郭抽出／表示部）の流れ
図。

【図１７】５×５の２値化された情報をもつ格子状図形
に図１の輪郭抽出装置を適用して抽出された輪郭の第２
実施例を示す図である。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 ２次元格子を形成して配列されている複
   数の単位格子の各々に、第１、第２の論理値に対応させ
   て２値化させた画像の２値情報が配置されて成る格子状
   図形である基本２値化パターン図の、第１の論理値に対
   応する第１の情報をもつ図形パターンの輪郭を抽出する
   格子状図形の輪郭抽出装置であって、 前記基本２値化パターン図の第１の論理値の格子の４格
   子点に再度第１の論理値を、それ以外の格子点に第２の
   論理値を格納して生成した格子状図形である格子点２値
   化パターン図によって輪郭抽出開始格子点の検索処理を
   行い、輪郭抽出開始格子点が検索されたとき、基本２値
   化パターン図を参照して再度輪郭抽出開始格子点に戻る
   まで輪郭抽出を実行し、格子点２値化パターン図による
   輪郭抽出開始格子点検索が全て終了するまで前記輪郭抽
   出開始格子点検索と輪郭抽出を繰り返す輪郭抽出装置。
2. 【請求項２】 輪郭抽出開始格子点の検索処理を、格子
   点２値化パターン図上において第１の情報をもつ格子に
   よって座標が一意に決まる基本２値化パターン図の４格
   子のうち３格子の論理値を参照することによって行う請
   求項１記載の輪郭抽出装置。
3. 【請求項３】 輪郭抽出を、格子点２値化パターン図の
   現着目格子点が抽出された方向と現着目格子点に対応す
   る基本２値化パターン図の４格子のうちの２格子の論理
   値によって格子点２値化パターン図の次着目格子点の抽
   出方向を予め定めた分類表を用いることにより行う請求
   項１記載の輪郭抽出装置。