JPH05143733A - 輪郭抽出装置 - Google Patents

Abstract

(57)【要約】 【目的】 ハードウェアによる輪郭内領域の塗りつぶ
し、及び排他的論理和の演算による内側に存在する輪郭
に囲まれた領域の抽出を併せもつ手段によって、高速か
つ容易に全ての輪郭を抽出することを目的とする。 【構成】 量子化された画像データの、輪郭を抽出する
手段の内、注目する画像データの、抽出されている輪郭
によって囲まれている閉領域を塗りつぶした画素群と、
注目する閉領域との排他的論理和をとる手段、及び、排
他的論理和をとることによって抽出された、注目する閉
領域の輪郭の内側に存在する、塗りつぶしの行われない
閉領域の輪郭抽出を逐次行う手段により構成されている
ことを特徴としている。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はコンピュータ周辺機器の
一つである、印刷装置、表示装置に係わり、詳しくは文
字、画像を表す２値化画像の輪郭抽出の装置に関する。

【０００２】

【従来の技術】従来、２値化画像の内側輪郭の検出に
は、逐次検出法が用いられた。これは、以下の３つの手
順を持つものである。

【０００３】（１）縦横いずれかを走査方向と定め、走
査方向に画素の１／０を順次検査し、白領域を求める手
順。

【０００４】（２）求めた白領域に内の１つの点から出
発し、上、下、右、左の各方向に白領域を探査する手
順。

【０００５】（３）現在探査中の白領域が、すでに求め
た白領域の一部と、同一座標の点を含んでいた場合、両
白領域が、同一であることを登録する手順。

【０００６】上記の３手順を逐次行うことで、白領域の
検出をすれば、閉じた黒領域に含まれる内側輪郭の検出
が可能となる。例えば、「Ｂ」という文字を形成する画
素群には、内側に２つの白領域が存在する。上記３手順
の繰り返しを行うことで、互いに独立した２つの白領域
の検出が可能となる。図１７にこの例の説明図を示す。
矢印４０の方向への走査により第１の白領域が検出さ
れ、矢印４１、４２で検出される白領域は、第１の白領
域と同一であると判断される。これに対し、矢印４３方
向の走査で、第２の白領域が検出される。

【０００７】一方「Ｃ」という文字を形成する画素群に
同様の手段を用いれば、白領域が、走査開始の座標を含
むものであることが検出されるため、閉じた黒領域の内
側の輪郭が存在しないと判断できる。

【０００８】

【発明が解決しようとする課題】上記の例からも明らか
なように、従来の方法では、矢印４０〜４３等のよう
に、縦方向の画素数に同一の回数だけ走査を実行する必
要があった。この場合、処理時間を多く必要とするとい
う問題があった。

【０００９】本発明は、この様な従来技術の問題点を解
決するために発明されたもので、ハードウェアによる輪
郭内領域の塗りつぶし、及び排他的論理和の演算による
内側に存在する輪郭に囲まれた領域の抽出を併せもつ手
段によって、高速かつ容易に全ての輪郭を抽出すること
を目的とする。

【００１０】

【課題を解決するための手段】本発明は量子化された画
像データの、輪郭を抽出する装置であって、抽出されて
いる輪郭の閉領域を塗りつぶした画素群と、注目する閉
領域との排他的論理和をとる手段と、排他的論理和をと
ることによって抽出され、注目する閉領域の輪郭の内側
に存在する、塗りつぶしの行われない閉領域の輪郭抽出
を逐次行う手段とから構成されたことを特徴とする。

【００１１】

【作用】本発明の上記装置によれば、２値化画像の輪郭
抽出において、特に内側の輪郭を抽出する場合、直前に
抽出された輪郭に囲まれた閉領域を、ハードウェアによ
り塗りつぶし、得られた画素群と元の画素群との排他的
論理和をとることによって、本来塗りつぶしの行われな
い白領域を抽出できる。さらに、この領域についても同
様な処理を行い内側の輪郭も抽出する。上記の方法を繰
り返すことにより、全ての輪郭を抽出する。

【００１２】

【実施例】以下、本発明について、実施例に基づき詳細
に説明する。図１は、本発明の輪郭抽出の構成図であ
る。図中５１は、元画像メモリであり、元データは、文
字、画像を表す一般の２値化画像データが格納されてい
る。５２は、フローチャート図３で後述する輪郭抽出手
段を実行する輪郭抽出部である。元画像データの一番外
側の輪郭がこの処理によって抽出され、次にこの画素デ
ータを元にして、塗り潰し部５３において、奇数偶数規
則に従った既知の方法により塗り潰しを行う。その結果
得られた画素データを１次作業メモリ５４に格納し、さ
らに元画像の画素データをそのまま２次作業メモリ５５
に格納する。ここで、塗り潰しの行われる黒領域の画素
を１塗り潰しの行われない白領域の画素を０とする。バ
ンド読み取り部５６ａ及び５６ｂによって、それぞれの
作業メモリ５４、５５から画素データを読み取り、排他
的論理和回路５７によって両データの排他的論理和をと
る。これより、輪郭抽出部５２で抽出された輪郭の内側
に含まれている最初の閉領域が検出できる。バンド書き
込み部５８は、この検出された画素データを、イメージ
メモリ５９に書き込む。これらの一連の行程は、出力装
置の分解能に対し、必要な画素数まで繰り返される。ま
た、画像の全ての範囲にわたって、排他的論理和回路５
７によって画素群を抽出した結果、０でない画素が存在
しなかった場合、全ての輪郭が抽出されたことは明かで
あり、この行程は終了する。以上の処理を行うためのプ
ログラムは、ＲＯＭ６１上に記述されており、アドレス
バス６２、データバス６３を介して、マイクロプロセッ
サユニット（ＭＰＵ）が制御を行っている。

【００１３】図２は、本発明の輪郭抽出の基本構成を示
すフローチャートである。元データは、文字、画像を表
す一般の２値化画像データを用いる。この装置において
は、半導体ＲＯＭ等に記録された、ドットによって形成
された元データが、図中（１）において読み取られる。
次に、検出領域内を順次調べることにより、注目する画
素を取り出す。ドットによって形成された元の画素群の
データをＤ０とする（２）。この取り出した画素を開始
点として輪郭抽出を実行する（３）。

【００１４】輪郭抽出は、ＡＮＩＬ Ｋ．ＪＡＩＮの報
告にある方法（ＡＮＩＬＫ．ＪＡＩＮ ”ＦＵＮＤＡＭ
ＥＮＴＡＬＳ ＯＦ ＤＩＧＩＴＡＬ ＩＭＡＧＥ Ｐ
ＲＯＣＥＳＳＩＮＧ” Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ
１９８９）に従う。公知ではあるが、簡単に述べる。Ｊ
ＡＩＮの方法は、２値化画像について、図３のフローチ
ャートのように輪郭部分の座標を決める。ここでは、表
示されるべき画素が値”１”をとり、表示されない画素
は、値”０”をとるものとする。まず注目する画素を取
り出す（１０）。画素を取り出したとき、検出領域をす
でに一周していれば、処理は終了である（１１）。それ
以外の場合は、注目する画素の値が１であるか判断し
（１２）、１であれば、左周りに進行方向を決めて１ス
テップ進む（１３）。判断（１２）の結果１でないとき
は、右周りに進行方向を決めて、１ステップ進む（１
４）。この後、処理（１０）に戻り、同様に繰り返す。
この処理の様子を、図４に図示した。まず検出領域の境
界１５の中を、点群１６で示される画素群を順次調べ、
最初の０でない画素を捜し出す。これは、０でない画素
群１８の中に含まれる画素である。その後、図３（フロ
ーチャート）の方法を用いると、折れ線１７に示される
軌跡に添って、輪郭部分に位置する画素群が検出され
る。処理（１３）が行なわれる度に、その位置座標を記
録し続ければ、輪郭部分の画素の位置座標の配列が得ら
れる。この位置座標の配列の隣り合う要素間で、距離の
差分をとれば、水平・垂直方法の差分から、｛上、下、
右、左｝の４方向からなるベクトルの配列を作ることが
できる。このベクトルの配列を辿れば、図５の折れ線１
９の様に輪郭線を取り出すことができる。

【００１５】以上に延べた手段を用いて抽出した輪郭に
よって囲まれた閉領域の塗りつぶしを行う（４）。この
ときのドットの画素群のデータをＤ１としておく。塗り
つぶし方法は、周知である奇数偶数規則に従った方法を
採用した。本実施例では、ハードウェアにより塗りつぶ
しを行うものである。

【００１６】次に、上記手段によって抽出されたデータ
Ｄ１と元データＤ０の排他的論理和をとる（５）。後述
の説明のために、ここで求められたデータを再びＤ０と
する。つまり、もし、既に抽出された輪郭の閉領域に含
まれる輪郭が存在する場合、排他的論理和をとることに
よって、内側にある輪郭に囲まれる閉領域を取り出すこ
とが可能である。従って、再度、注目する画素があるか
どうかを調べ（６）、存在しない場合は終了となる。し
かし、存在した場合、今度は、上述で生成された画素群
の輪郭抽出を行う（３）。この動作を注目する画素がな
くなるまで行うことによって、全ての輪郭を抽出するこ
とが出来る。

【００１７】さらに、図２における処理を以降に詳細に
延べる。

【００１８】図６において、最初の０でない画素を求め
る。まず検出領域の境界２５の中に存在する、これから
抽出すべき、ドット読み取り手段により取り出された、
元データである画素群２７を、図７において、順次画素
を調べる。その後さらに、図３に示した処理を施すこと
により、検出処理の軌跡２６に沿って輪郭部分に位置す
る画素群が検出される。輪郭部分の画素の位置座標の配
列を取得すれば、図８の輪郭線２８を取り出すことが出
来る。

【００１９】次に、奇数偶数規則に従った方法の塗りつ
ぶしのハードウェアを使用して、図８の輪郭線２８で囲
まれる閉領域の塗りつぶしを行う。この画素群を図９の
２９に示す。図６の検出する元データの画素群と、今求
められた輪郭の内部を塗りつぶした画素群との排他的論
理和をとると、図１０の３１に示す画素群が抽出でき
る。この画素群は、元データにおいて、塗りつぶしの実
施されない閉領域である。

【００２０】今、排他的論理和をとることによって、本
来塗りつぶしをされない部分領域が抽出できた。ここ
で、この閉領域を図６の画素群２７と同一の状態にある
ものと考えることができる。本実施例では、元データで
ある注目する領域の内側に、輪郭を伴う領域が複数個存
在している場合について行っているが、通常必ず存在す
るとは限らないのは明かであり、その場合には、直ちに
終了となる。図１０に戻り、再び順次検出領域の画素を
調べ最初に０でない画素を捜す。後は、前述した方法で
図７の処理と同様に、図１１の検出処理の軌跡３０に沿
って輪郭部分に位置する画素群が検出できる。さらに図
１２に示すように内側領域の輪郭線３２も抽出すること
ができる。この輪郭に囲まれた閉領域を、塗りつぶしハ
ードウェアを用いて塗りつぶした画素群（図１３の３
３）と、前回、排他的論理和演算によって得られた画素
群（図１０の３１）との排他的論理和をとると、図１４
に示す様に、最後の求めるべき輪郭線が囲む閉領域３４
を抽出することができる。この、最後の画素群３４につ
いても、図３に示したような処理を行えば（図１５にそ
の処理過程を示す）、輪郭線（図１６の３６）が求めら
れる。このように、注目する画素データの内部に、幾つ
も求めるべき輪郭線が存在したとしても、上記の動作を
複数回繰り返すことによって、最終的に全ての輪郭線を
求めることが可能である。

【００２１】

【発明の効果】以上の実施例から明らかなように、本発
明の輪郭抽出手段によれば、内側の白領域の検出が容易
にできるため、２値化画像における全ての輪郭が、従来
の、走査方向の画素数に同一の回数だけ走査を実行する
逐次検出法を行うよりも高速に抽出でき、かつハードウ
ェアに置き換えることも容易であると言える。

【図面の簡単な説明】

【図１】本発明の輪郭抽出手段の構成図。

【図２】本発明の処理の流れ図。

【図３】輪郭線抽出法の流れ図。

【図４】輪郭線抽出法の説明図。

【図５】抽出された輪郭線の説明図。

【図６】輪郭抽出する元データの説明図。

【図７】最初の輪郭抽出の過程の説明図。

【図８】最初に抽出された輪郭線の説明図。

【図９】最初に抽出された輪郭線の内部の塗りつぶしの
説明図。

【図１０】元データと、最初に抽出された輪郭線の内部
を塗りつぶした画素データとの、排他的論理和の説明
図。

【図１１】元データの内部の輪郭線抽出の過程の説明
図。

【図１２】抽出された内部の輪郭線の１つの説明図。

【図１３】抽出された、内部の輪郭線の１つに囲まれた
閉領域の説明図。

【図１４】排他的論理和をとることによって、最初に得
られた画素データと、内部の輪郭線の１つに囲まれた閉
領域との排他的論理和の説明図。

【図１５】元データの内部の輪郭線抽出の過程の説明
図。

【図１６】抽出された内部の輪郭線の１つの説明図。

【図１７】従来の内側輪郭の検出手段の説明図。

【符号の説明】

２５ 検出領域の境界 ２６ 検出処理の軌跡 ２７ 元データの画素群 ２８ 輪郭線 ２９ 塗りつぶし実行後の画素群 ３１ 排他的論理和演算による画素群 ３２ 内側領域の輪郭線 ５２ 輪郭抽出部 ５３ 塗り潰し部 ５７ 排他的論理和回路

Claims (1)

【特許請求の範囲】
1. 【請求項１】 量子化された画像データの、輪郭を抽
   出する装置であって、抽出されている輪郭の閉領域を塗
   りつぶした画素群と、注目する閉領域との排他的論理和
   をとる手段と、排他的論理和をとることによって抽出さ
   れ、注目する閉領域の輪郭の内側に存在する、塗りつぶ
   しの行われない閉領域の輪郭抽出を行う手段と、から構
   成されることを特徴とする輪郭抽出装置。