JPS6220077A

JPS6220077A - 距離変換方法及びその装置

Info

Publication number: JPS6220077A
Application number: JP60159867A
Authority: JP
Inventors: Toshiyuki Goto; 敏行後藤; Hiromichi Iwase; 岩瀬　洋道
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1985-07-19
Filing date: 1985-07-19
Publication date: 1987-01-28

Abstract

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

Description

【発明の詳細な説明】〔概要〕距離変換方法及びその装置であって、境界より一方向に
おける距離を算出して得た画像を逆方向に走査して距離
ラベルを更新することで距離の算出を高速に行なえるよ
うにする。

〔産業上の利用分野〕

本発明は画像処理方法及びその装置に関するもので、さ
らに詳しく言えば、距離変換における処理の高速化に関
するものである。

二値画像における一つの基本的処理として距離変換があ
る。これは、例えば、領域内の任意の点から周縁に対す
る最小の距離を求めて咳点の値とするものである。距離
の変換方式として幾つかの方式が提案されているが、高
速性とハードウェアの負担量の両方について満足できる
距離変換方式及び装置は提供されるに至ってない。

〔従来の技術〕

距離変換の代表的方法として従来より、論理フィルタを
応用する方式と輪郭の追跡処理を行なう方式とがある。

論理フィルタを用いる方式は結果が収束するまで同様な
処理を繰り返し行なうものであり、また、輪郭の追跡処
理を行なう方式は画像データをランダムアクセス及びス
キャンして行なうものである。

〔発明が解決しようとする問題点〕

この従来方式では処理結果が収束する迄、同様な処理を
繰り返し行なう必要があって処理時間が長くなりまた、
処理に要する時間が不定であり、更に、画像データのラ
ンダムアクセスの必要があって、装置全体の規模が大き
くなるという欠点があった。

本発明はこのような点に鑑みて創作されたもので、領域
の境界から領域内の各画素までの距離をパイプライン処
理により高速に算出可能な距離変換方法及びその装置を
提供することを目的としている。

〔問題点を解決するための手段〕

第１図は本発明の原理ブロック図であって、第１のラベ
ル付けを行なう初期ラベル付け部１．走査方向変換部２
及び初期ラベル付け部１により付けられたラベルを更新
するための距離ラベル更新部３より成る。

〔作用〕

初期ラベル付け部１は入力画像中の各領域内の画素に対
して境界から定められた１方向の距離を算出してラベル
付けを行なう。走査方向変換部２は初期ラベル付け部１
によりラベル付けされた画像を逆方向に走査するために
設けられる。距離ラベル更新部３は逆方向に走査して得
られた値より領域の各画素と境界との最短距離を算出し
て距離ラベルを更新するために設けられる。

本発明では初期ラベル付け部１によりラベル付けされた
画像を逆方向に走査する走査方向変換部２においてメモ
リに蓄積した画像を逆方向に読み出す操作を行なうこと
でパイプライン処理を可能にしている。

〔実施例〕

以下に本発明の好適な実施例を添付図面を参照して説明
する。第６図は第１図に示した本発明の実施例の初期ラ
ベル付け部１の詳細なブロック図で、ウィンド設定回路
１００．ウィンド演算回路１１０及び背景検出回路１２
０より成る。ウィンド設定回路１００にはＤ型のフリッ
プフロップ４と画像の水平方向のドツト数に対応して設
計されたシフトレジスタ５が含まれ、ウィンド演算回路
１１０には比較回路６１選択回路７及び加算回路８が含
まれる。また、背景検出回路１２０には入力データが全
てＯであるか否かを検出するためのＮＡＮＤゲート９と
選択回路１０が含まれる。この初期ラベル付け部は第４
図（ａｌに示すようなウィンドを例えば第２図に示すよ
うな入力画像上に設定する。なお、第４図（ａ）におい
てＣは注目画素を示し、ａ及びｂはこのウィンドにより
画像上を走査した時の隣接画素を示す。ここでｃ＝０の
時にラベル付けされた注目画素をｃｎｅｘｔ＝ｏとし、
Ｃ≠０の時にａ、ｂの最小値に１を加えるものとし、ｃ
ｎｅｘｔ＝Ｍ　Ｉ　Ｎ　（ａ、　　ｂ）　　＋　１とす
る。この様な論理に従って第２図に示す入力画像を処理
すると第３図に示す様に各画素に対して右上からの距離
に対応した初期ラベルが付与された処理結果が得られる
。なお、第６図に示すウィンド設定回路１００では順次
入力及び出力される画像データを保持しながら上述のウ
ィンドを設定するものである。

また、ウィンド演算回路１１０はウィンド内の各データ
につき上述論理に従ってラベル付けされた注目画素Ｃｎ
ｅｘｔを演算する。更に、背景検出回路１２０は例えば
８ビツトの全ての入力が０であるか否かによってウィン
ド演算回路１１０内の加算回路８の出力と０人力とを選
択して出力する。第７図は第１図に示す走査方向変換部
２の詳細なブロック図であって、メモリ１４のアドレス
を指定するカウンタ１１とノットゲート１２及び選択回
路１３が含まれる。この走査方向変換部２はメモリ１４
にカウンタ１１によるアドレスに従って順に画素を記憶
した後、順次逆方向から読み出すもので、例えば９ビツ
トのカウンタを用い、１０ビツト目に選択回路１３を切
り換えて読出方向を反転させるものであって、１フレー
ム毎にパイプライン的な処理が可能である。

第８図は第１図に示す距離ラベル更新部３の詳細なブロ
ック図で、ウィンド設定回路２００．ウィンド演算回路
２１０及び背景検出回路２２０より成る。ウィンド設定
回路２００にはＤ型のフリップフロップ１５と画像の水
平方向のドツト故に対応して設けられたシフトレジスタ
１７が含まれ、ウィンド演算回路２１０には比較回路１
６．１９、選択回路１８．２０及び加算回路２１が含ま
れる。

また、背景検出回路２２０には入力データが全て０であ
るか否かを検出するためのＮＡＮＤゲート２２と選択回
路２３が含まれる。この距離ラベル更新部は第４図（ｂ
）に示すようなウィンド（但し、図式的に示したものに
過ぎず、本質的には第４図（ａｌと同じ。）を用いてウ
ィンド内の画素の最小値を算出し、Ｃが０でない時に１
を加えるような演算を行なうもので、ｃ＝０の時にｃｎ
ｅｘｔ＝ｏとし、Ｃ≠０の時にｃｎｅｘｔ＝ＭＩＮ　（
ａ、ｂ、ｃ）＋１とするものである。ＣがＯであるか否
かの判別及び最小値の検出と加算のためにＮＡＮＤゲー
ト２２．２″″′Ｏ）Ｊ［ｉＳ、ｊ６．”ｓ＆及ｉｉ択
回１？＆　１　ｓ　。

２０．２３と　　　　２１が　けら　る。これ等の回路
によって逆方向への走査と領域内の各画素と境界との最
短距離の算出が行なわれて第３図に示す様な初期ラベル
付けされた画像が第５図に示すように更新される。

なお、前記実施例においては、ウィンド設定回路１００
，２００；ウィンド演算回路１１０．２１Ｏ；背景検出
回路１２０，２２０を各別に設ける場合について説明し
たが、ウィンド設定回路及び背景検出回路については切
換回路を設けてこれらを各ラベル付けに共用し、又ウィ
ンド演算回路についてもウィンド演算回路２１０を次の
ようにして共用してもよい。即ち、第８図において、初
期ラベル付けに際しては選択回路１８を常にｂ・の値（
フリップフロップ１５の出力値）を選択せしめるように
選択機能を固定にし、又距離ラベル付け更新処理におい
ては上述した選択機能を回復させる如くしてその共用化
を実現するようにしてもよい。このような共用化を施し
た場合のウィンド設定手段を４００、ウィンド演算手段
を４１０、そして背景検出手段を４２０として参照する
。

〔発明の効果〕

以上説明したように本発明によれば、画像領域の境界か
ら領域内の各画素までの距離をバイブライン処理により
距離変換を高速に算出可能である。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、第２図は入力画像の例を示す説明図、第３図は初期ラベル付けされた画像の説明図、第４図（
ａｌ及び（ｂｌはウィンドの例を示す説明図、第５図は
更新されたラベル画像の説明図、第６図は第１図に示し
た初期ラベル付け部の詳細なブロック図、第７図は走査方向変換部の詳細なブロック図、第８図は
距離ラベル更新部の詳細なブロック図である。第１図、第６図、第７図、第８図において、１は初期ラ
ベル付け部、２は走査方向変換部、３は距離ラベル更新部、４．１５はＤ型フリップフロップ、５．１７はシフトレジスタ、６．１６．１９は比較回路、７．１０，１３，１８．２０．２３は選択回路、８．２
１は加算回路、１２はノットゲート、９．２２はＮＡＮＤゲート、１１はカウンタ、１４はメモリである。ウィンドの枠１ｔポア説酬図　　　　更許翻はラベル画
イ象ｎ貌−図第４図　　　　　　第５図距離ラヘ・ル更ｉｕｐめ詳輔−フ゛口７フ図第８図

Claims

【特許請求の範囲】

（１）注目画素と前記注目画素に隣接する画素に対し設
定されたウインドを用いて入力画像を走査し、前記入力
画像における境界から一方向における距離を算出して初
期ラベルを付けた後（１）、前記初期ラベル付けされた
画像を逆方向に走査し（２）、領域内の各画素と境界と
の最短距離を算出する（３）ことを特徴とする距離変換
方法。
（２）画像の注目画素及び該注目画素に隣接する画素に
対しウインドを設定するウインド設定手段（４００）と
、走査されて入力される画像に対する初期ラベル付けに際
して前記ウインド内の画素を用いて注目画素への初期ラ
ベル付け論理による初期ラベル付けを為し、初期ラベル
付けされた画像に対するラベル付けに際して前記ウイン
ド内の画素を用いて注目画素への距離ラベル付け更新論
理によるラベル付けを為すウインド演算手段（４１０）
と、ウインド演算手段（４１０）からの画素出力が画像
領域内のものか背景のものかを判定する背景検出手段（
４２０）と、背景検出手段（４２０）から初期ラベル付けされた出力
画像を入力画像の走査方向に対し逆方向に走査した初期
ラベル付け済み画素出力をウインド設定手段（４００）
に供給する走査変換手段（３００）とを備えて構成した
ことを特徴とする距離変換装置。
（３）画像の注目画素及び該注目画素に隣接する画素に
対しウインドを設定する第１及び第２のウインド設定手
段（１００、２００）と、走査されて入力される画像に対する初期ラベル付けに際
して第１のウインド設定手段（１００）のウインド内の
画素を用いて注目画素への初期ラベル付け論理による初
期ラベル付けを為す第１のウインド演算手段（１１０）
と、第１のウインド演算手段（１１０）からの初期ラベル付
け画素出力が画像領域内のものか背景のものかを判定す
る第１の背景検出手段（１２０）と、第１の背景検出手段（１２０）から初期ラベル付けされ
た出力画像を前記入力画像の走査方向に対し逆方向に走
査した画素出力を第２のウインド設定手段（２００）に
供給する走査変換手段（３００）と、第２のウインド設定手段（２００）のウインド内の画素
を用いて注目画素への距離ラベル付け更新論理によるラ
ベル付けを為す第２のウインド演算手段（２１０）と、第２のウインド演算手段（２１０）からの画素出力が画
像領域のものか背景のものかを判定して距離変換出力を
出力する第２の背景検出手段（２２０）とを備えて構成
したことを特徴とする距離変換装置。