JPH08171643A

JPH08171643A - メッシュ状図形の輪郭抽出方式

Info

Publication number: JPH08171643A
Application number: JP6313383A
Authority: JP
Inventors: Masahisa Mochida; 雅久持田
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1994-12-16
Filing date: 1994-12-16
Publication date: 1996-07-02

Abstract

(57)【要約】【目的】２値化された画像情報がメッシュ状の各格子
に任意に配列された図形において、第１の情報をもつ１
つの格子が第２の情報をもつ３つの格子に隣接されてい
る場合においても輪郭抽出を行うことが出来るメッシュ
状図形の輪郭抽出方式を提供する。【構成】右回りに輪郭を追跡する場合には、追跡方向
に対して追跡対象格子（着目格子）の左、前方、右、後
方の順に隣接格子の２値情報を検索する。左回りに輪郭
を追跡する場合には、追跡方向に対して着目格子の右、
前方、左、後方の順に隣接格子の２値情報を検索する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は２値化された画像または
地図情報等に用いられる輪郭抽出方式に関し、特にメッ
シュ状に配置された図形の輪郭抽出方式に関する。

【０００２】

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

【０００３】図６は格子点および格子を抽出する方式の
一例を示す流れ図である。この方式は同一の２値情報を
持つ隣接格子点を接続して閉ル一プを容易に抽出する手
順である。図７は、図６のステップ１１４の詳細な流れ
図である。図８はメツシュ状の格子点上に２値化された
情報をプロットした図の一例で、図９は５x５のそれぞ
れの格子に対して２値化された情報を与えた図である。
ここでは、図８における格子点の情報、および図９にお
ける格子の情報を空白と黒または斜線に２値化してい
る。以下、空白の格子点および格子を論理０に対応さ
せ、黒の格子点および斜線の格子を論理１に対応させ
る。したがって、以下の記述では、黒の格子点または斜
線の格子によって構成される図形が、輪郭を抽出しよう
とする図形である。

【０００４】図８の図形において、輪郭抽出の初期条件
は次のようにして設定される。先ず、図形の最下段の左
から右に向かって格子点の検索を開始する。一段目が終
了したら上段に移動し、同様な検索処理を行う。そこ
で、論理１を表わす格子点が検索されたら、その格子点
を最初に抽出された格子点とし、その格子点を抽出開始
格子点として、図６の流れ図に従って輪郭の抽出が実行
される。図８の格子に対してこの手順を適用すると、前
記の左から右への検索によって、格子点１２が最初に抽
出される（ステップ１０１）。したがって、この輪郭抽
出処理の初期条件は、「抽出開始格子点１２、抽出方向
左→右」である。以後、この初期条件に基づいて、次に
説明するように、格子点１２→格子点１３→格子点１４
→格子点１５→格子点１６→格子点１７→格子点１８→
格子点１９の順序で格子点が抽出され、図中の太線の様
に閉ループを抽出することができる。

【０００５】図６の流れ図では、簡略化された表現が用
いられているので、輪郭抽出処理について説明する前
に、各ステップで実行される判断または処理について説
明する。なお、前記したように、以下の記述では抽出対
象は論理１の格子点とする。図６のステップ１０２、１
０５、１０８、１１１では判定条件が「抽出方向ａ→ｂ
？」の形式で表わされている。抽出方向とは直前の着目
格子点（抽出対象格子点）から見た現在の着目格子点の
方向である。換言すれば、抽出方向とは輪郭追跡方向で
ある。この判定条件は、現在の着目格子点が抽出された
ときの抽出方向がａ→ｂで表わされる方向であるときに
はＹＥＳと判定し、その他の方向であるときにはＮＯと
判定するという意味である。例えば、図８の格子におい
て論理１の格子点として１２が抽出され、次に、論理１
の格子点として１３が抽出されたとき、着目格子点１３
の抽出方向は下→上である。着目格子点１３に与えられ
たこの抽出条件に対して、ステップ１０２、１０８、１
１１はＮＯと判定し、ステップ１０５はＹＥＳと判定す
る。

【０００６】図６のステップ１１４、１１５、１１６、
１１７は「ｘ、ｙ、ｚの順で抽出」という形式で表現さ
れている。このステップは順次に実行される３つの判
断、すなわち第１、第２、第３の判断から成っている。
第１の判断は、着目格子点のｘ側に隣接した格子点を検
索し、該格子点の情報が論理１の場合にはＹＥＳと判定
し、論理０の場合にはＮＯと判定して第２の判断を起動
する。第２の判断は、着目格子点のｙ側に隣接した格子
点を検索し、該格子点の情報が論理１の場合にはＹＥＳ
と判定し、論理０の場合にはＮＯと判定して第３の判断
を起動する。第３の判断は、着目格子点のｚ側に隣接し
た格子点を検索し、該格子点の情報が論理１の場合には
ＹＥＳと判定し、論理０の場合にはＮＯと判定して処理
を終了する。第１〜第３の判断のＹＥＳ分岐は次のステ
ップ１０４，１０７，１１０，１１３に入力される。

【０００７】図７は、「ｘ，ｙ，ｚの順で抽出」型ステ
ップの一例であるステップ１１４の流れ図である。ステ
ップ１１４は判断ステップ１１４₁、１１４₂、１１４₃
からなる。これらの判断ステップ１１４₁、１１４₂、１
１４₃は、それぞれ、着目格子点の上、右、下の隣接格
子点を検索した結果、論理１を抽出した場合にはＹＥＳ
判定を生成し、論理０を抽出した場合にはＮＯ判定を生
成する。例えば、図８において、論理１をもつ格子点と
して格子点１３が抽出された後、格子点１４が抽出され
たとき、着目格子点１４の抽出方向は左→右である。し
たがって、着目格子点１４に基づいて次の格子点を抽出
する場合に、ステップ１０２はＹＥＳ判定を生成する。
ステップ１０２のＹＥＳ判定により、ステップ１１４の
第１の判断ステップ１１４₁が起動され、まず、上方の
隣接格子点１５が検索される。格子点１５は論理１の情
報をもっているので、判断ステップ１１４₁はＹＥＳ判
定を生成する。この時以後、着目格子点は格子点１５に
なる。次に、ステップ１０４によって、着目格子点１５
が初期設定で定められた抽出格子点と一致するか否かが
判定され、一致しない時にはステップ１０２に戻り、輪
郭抽出処理が更に進行する。着目格子点１５の抽出方向
は下→上（１４→１５）である。したがって、ステップ
１０２はＮＯ判定を出力し、処理はステップ１０５に移
る。

【０００８】「抽出方向ａ→ｂ？」型ステップと「ｘ、
ｙ、ｚの順で抽出」型ステップがこのような処理を実行
することを前提にして、図６の処理フローは、次のよう
に図８の図形の輪郭抽出をする。先ず、ステップ１０１
によって、図形の最下段の左から右に向かって格子点の
検索を開始し、一段目が終了したら上段に移動し、同様
な検索処理を行って、抽出開始格子点として格子点１２
を抽出する。前記したように、格子点１２の抽出方向は
左→右である。したがって、ステップ１０２によってＹ
ＥＳ判定が出力される。次に、ステップ１１４によって
上の隣接格子点１３が抽出される。この時、格子点１３
の抽出方向は下→上である。次に、格子点１３に着目
し、ステップ１０４によって格子点１３が、抽出開始格
子点１２と同一であるか否かが判定され、ＮＯ判定が出
力されると、格子点１３を着目格子点として（格子点１
３を対象格子点として）ステップ１０２の判断が行われ
る。前記したように、格子点１３の抽出方向は下→上で
あるから、ステップ１０２によってＮＯ判定が出力さ
れ、処理はステップ１０５に分岐する。格子点１３に関
して抽出方向が下→上であると判定されると（ステップ
１０５）、格子点１３の左の隣接格子点、および抽出方
向（上）の隣接格子点が順次に検索される。この検索に
よって論理１は抽出されないので、次に右の隣接格子点
を検索して格子点１４が得られる（ステップ１１５）。
したがって、格子点１４の抽出方向は左→右である。次
に論理１の格子点が抽出されるまでの処理は、格子点１
４に着目して行われる。格子点１４が抽出開始格子点１
２でないと判定され（ステップ１０７）、該格子点１４
の抽出方向が左→右であると判定される（ステップ１０
２）と、先ず、該格子点１４の上方の隣接格子点１５を
検索し、論理１を抽出する（ステップ１１４）。したが
って、格子点１５の抽出方向は下→上である。次に、格
子点１５が抽出開始格子点１２でないと判定されると
（ステップ１０４）、格子点１５に着目してステップ１
０２、１０５の順序で抽出方向が判断され、ステップ１
０５によってＹＥＳ判断が生成される。以下、同様な処
理が次のように繰り返される。ステップ１１５（格子点
１６抽出）→ステップ１０７→ステップ１０２→ステッ
プ１１４（格子点１７抽出）→ステップ１０４→ステッ
プ１０２→ステップ１０５→ステップ１０８→ステップ
１１１→ステップ１１７（格子点１８抽出）→ステップ
１１３→ステップ１０２→ステップ１０５→ステップ１
０８→ステップ１１１→ステップ１１７（格子点１９抽
出）→ステップ１１３→ステップ１０２→ステップ１０
５→ステップ１０８→ステップ１１６（格子点１２抽
出）→ステップ１１０→終了。このようにして、図８の
太線のように閉ループを抽出することができる。上述の
方式を図９の輪郭抽出に適用すると、格子２０→格子２
１→格子２２→格子２３→格子２４→格子２５→格子２
６→格子２７の順で論理１の図形（斜線部）の輸郭を抽
出することができる。

【０００９】

【発明が解決しようとする課題】しかし、従来の輪郭抽
出方式は、隣接格子点を連結すると図８の様な、閉ルー
プが構成される図形パターンを対象としているため、図
２の格子４の様に、論理１をもつ１つの格子に論理０を
もつ３つの格子が隣接する（または、論理０をもつ１つ
の格子に論理１をもつ３つの格子が隣接する）パターン
を含む図形において、当該１つの格子点、または当該１
つの格子に前掲の「ｘ、ｙ、ｚの順で抽出」型処理を行
うと、ｘ、ｙ、ｚのいずれの側の隣接格子または隣接格
子点からも第１の情報を抽出することが出来ない場合が
生じる。この様な場合には、最初に抽出した格子に戻る
ことができないので、デッドロツクを起こしてしまうと
いう問題点があった。

【００１０】本発明の目的は、メツシユ状のあらゆる図
形パターンの輪郭抽出を容易に行うことが出来る輪郭抽
出方式を実現することである。

【００１１】

【課題を解決するための手段】本発明の第１のメッシュ
状図形の輪郭抽出方式は、２次元格子を形成して配列さ
れている複数の単位格子の各々に、第１、第２の論理値
に対応させて２値化された画像の２値情報が配置されて
成るメッシュ状図形の、第１の論理値に対応する第１の
情報を持つ図形パターンの輪郭を抽出するメッシュ状図
形の輪郭抽出方式であって、輪郭を構成する、第１の情
報をもつ単位格子の１つを輪郭抽出開始格子として初期
設定し、該輪郭抽出開始格子を第０格子とし、第２の論
理値に対応する第２の情報をもち、かつ、第０格子に隣
接する単位格子に対する第０格子の方向を第０格子の抽
出方向と定め、第０格子の抽出方向を基準として第０格
子の左側、前方すなわち当該抽出方向、右側、後方すな
わち当該抽出方向の逆方向において第０格子に隣接して
いる単位格子の２値情報を、前記左側、前方、右側、後
方の順序に検索する第１検索を実行し、何れの単位格子
からも第１の情報が抽出されなかった場合には、輪郭抽
出処理を終了し、第１の情報が抽出される場合には、最
初に第１の情報が抽出された単位格子を第１格子と定め
て処理を次に進め、第０格子に対する第１格子の方向を
判定し、その方向を第１格子の抽出方向と定め、第１格
子の抽出方向を基準として第１格子の左側、前方すなわ
ち当該抽出方向、右側、後方すなわち当該抽出方向の逆
方向において第１格子に隣接している単位格子の２値情
報を、前記左側、前方、右側、後方の順序に検索する第
２検索を実行し、第２の検索において最初に第１の情報
が抽出された単位格子を第２格子と定め、第２格子が第
０格子に一致するか否かを判定し、一致する場合には輪
郭抽出処理を終了し、一致しない場合には処理を次に進
め、第１格子に対する第２格子の方向を判定し、その方
向を第２格子の抽出方向と定め、第２格子の抽出方向を
基準として第２格子の左側、前方すなわち当該抽出方
向、右側、後方すなわち当該抽出方向の逆方向において
第２格子に隣接している単位格子の２値情報を、前記左
側、前方、右側、後方の順序に検索する第３検索を実行
し、第３検索において最初に第１の情報が抽出された単
位格子を第３格子と定め、第３格子が第０格子に一致す
るか否かを判定し、一致する場合には輪郭抽出処理を終
了し、一致しない場合には処理を次に進め、以後、第ｎ
検索によって最初に第１の情報が抽出された単位格子を
第ｎ格子とし、その直前の第ｎー１検索によって最初に
第１の情報が抽出された単位格子を第ｎー１格子とし
て、第ｎ−１格子に対する第ｎ格子の方向を判定し、そ
の方向を第ｎ格子の抽出方向と定め、第ｎ格子の抽出方
向を基準として第ｎ格子の左側、前方、右側、後方にお
いて第ｎ格子に隣接している単位格子の２値情報を、前
記左側、前方、右側、後方の順序に検索する第ｎ＋１検
索を実行し、第ｎ＋１検索において最初に第１の情報が
抽出された単位格子を第ｎ＋１格子と定め、第ｎ＋１格
子が第０格子に一致するか否かを判定し、一致する場合
には輪郭抽出処理を終了し、一致しない場合には一致す
るまで、抽出方向の判定、検索処理を繰返し、第ｍ格
子が第０格子に一致したとき輪郭抽出処理を終了し、第
０、第１、第２・・・・、第ｍー１格子を当該図形パタ
ーンの輪郭とする。

【００１２】本発明の第１の輪郭抽出方式においては、
第ｎ−１格子に対する第ｎ格子の方向を第ｎ格子の抽出
方向と定義する。しかし、この定義はｎ＝０の場合、す
なわち輪郭抽出開始格子には適用することが出来ない。
したがって、第０格子の抽出方向は設定（初期設定）さ
れる。初期設定は、メツシユ状図形の最下段または最上
段の左から右へ格子の検索を行い、一段目が終了した
ら、それぞれ上段または下段に移動し、第１の情報の格
子が検索されたとき、当該格子を第０格子とし、前記左
から右に向く方向を第０格子の抽出方向に設定すること
によって、簡単なプログラムで容易に実行することがで
きる。

【００１３】本発明の第２のメッシュ状図形の輪郭抽出
方式は、２次元格子を形成して配列されている複数の単
位格子の各々に、第１、第２の論理値に対応させて２値
化された画像の２値情報が配置されて成るメッシュ状図
形の、第１の論理値に対応する第１の情報を持つ図形パ
ターンの輪郭を抽出するメッシュ状図形の輪郭抽出方式
であって、前記輪郭を構成する、第１の情報をもつ単位
格子の１つを輪郭抽出開始格子として初期設定し、該輪
郭抽出開始格子を第０格子とし、第２の論理値に対応す
る第２の情報をもち、かつ、第０格子に隣接する単位格
子に対する第０格子の方向を第０格子の抽出方向と定
め、第０格子の抽出方向を基準として第０格子の右側、
前方すなわち当該抽出方向、左側、後方すなわち当該抽
出方向の逆方向において第０格子に隣接している単位格
子の２値情報を、前記右側、前方、左側、後方の順序に
検索する第１検索を実行し、何れの単位格子からも第１
の情報が抽出されなかった場合には、輪郭抽出処理を終
了し、第１の情報が抽出される場合には、最初に第１の
情報が抽出された単位格子を第１格子と定めて処理を次
に進め、第０格子に対する第１格子の方向を判定し、そ
の方向を第１格子の抽出方向と定め、第１格子の抽出方
向を基準として第１格子の右側、前方すなわち当該抽出
方向、左側、後方すなわち当該抽出方向の逆方向におい
て第１格子に隣接している単位格子の２値情報を、前記
右側、前方、左側、後方の順序に検索する第２検索を実
行し、第２検索において最初に第１の情報が抽出された
単位格子を第２格子と定め、第２格子が第０格子に一致
するか否かを判定し、一致する場合には輪郭抽出処理を
終了し、一致しない場合には処理を次に進め、第１格子
に対する第２格子の方向を判定し、その方向を第２格子
の抽出方向と定め、第２格子の抽出方向を基準として第
２格子の右側、前方すなわち当該抽出方向、左側、後方
すなわち当該抽出方向の逆方向において第２格子に隣接
している単位格子の２値情報を、前記右側、前方、左
側、後方の順序に検索する第３検索を実行し、第３検索
において最初に第１の情報が抽出された単位格子を第３
格子と定め、第３格子が第０格子に一致するか否かを判
定し、一致する場合には輪郭抽出処理を終了し、一致し
ない場合には処理を次に進め、以後、第ｎ検索によって
最初に第１の情報が抽出された単位格子を第ｎ格子と
し、その直前の第ｎー１検索によって最初に第１の情報
が抽出された単位格子を第ｎー１格子として、第ｎ−１
格子に対する第ｎ格子の方向を判定し、その方向を第ｎ
格子の抽出方向と定め、第ｎ格子の抽出方向を基準とし
て第ｎ格子の右側、前方、左側、後方において第ｎ格子
に隣接している単位格子の２値情報を、前記右側、前
方、左側、後方の順序に検索する第ｎ＋１検索を実行
し、第ｎ＋１検索によって最初に第１の情報が抽出され
た単位格子を第ｎ＋１格子と定め、第ｎ＋１格子が第０
格子に一致するか否かを判定し、一致する場合には輪郭
抽出処理を終了し、一致しない場合には一致するまで、
抽出方向の判定および検索処理を繰返し、第ｍ格子が第
０格子に一致したとき輪郭抽出処理を終了し、第０、第
１、第２・・・・第ｍー１格子を当該図形パターンの輪
郭とする。

【００１４】第２の輪郭抽出方式においても、第１の輪
郭抽出方式と同一の処理で初期設定を行うことができ
る。また、第１の輪郭抽出方式の初期設定とは逆向きに
右から左へ検索して初期設定することもできる。

【００１５】

【作用】本発明の第１のメッシュ状図形の輪郭抽出方式
は、第１の情報をもつ図形輪郭を右回りに追跡する。右
回りに図形輪郭を追跡する場合には、追跡方向に対して
左側に第２の情報の単位格子を見、右側に第１の情報の
単位格子を見るように、単位格子を追跡しなければなら
ない。換言すれば、追跡される単位格子は、追跡方向に
対して最も左にある第１の情報をもつ単位格子である。
したがって、本発明の第１の輪郭抽出方式においては、
追跡方向に対して左側の単位格子の２値情報を優先して
検索する。「第ｎ格子の抽出方向を基準として第ｎ格子
の左側、前方、右側、後方において第ｎ格子に隣接して
いる単位格子の２値情報を、前記左側、前方、右側、後
方の順序に検索し、該検索によって最初に第１の情報が
抽出された格子を第ｎ＋１格子と定め」という手順は、
追跡方向に対して最も左側にある第１の情報をもつ単位
格子を抽出するための手順である。「第ｎ格子の抽出方
向」とは第ｎ格子が抽出されたときの輪郭追跡方向であ
る。

【００１６】上記の検索においては、第ｎ格子の左側、
前方、右側のみならず、「後方」において第ｎ格子に隣
接している単位格子をも検索する。したがって、図２の
単位格子４のように、左側、前方、右側の隣接格子から
第１の情報が抽出できなくても、後方の隣接格子が抽出
されるので行き詰まりにならないで、輪郭の抽出処理を
進行させることができる。

【００１７】本発明の第２のメッシュ状図形の輪郭抽出
方式は、第１の情報をもつ図形輪郭を左回りに追跡す
る。左回りに図形輪郭を追跡する場合には、追跡される
単位格子は、追跡方向に対して最も右にある第１の情報
をもつ単位格子である。したがって、本発明の第２の輪
郭抽出方式においては、追跡方向に対して右側の単位格
子の２値情報を優先して検索する。「第ｎ格子の抽出方
向を基準として第ｎ格子の右側、前方、左側、後方にお
いて第ｎ格子に隣接している単位格子の２値情報を、前
記右側、前方、左側、後方の順序に検索し、該検索によ
って最初に第１の情報が抽出された格子を第ｎ＋１格子
と定め」という手順は、輪郭追跡方向に対して最も右側
にある第１の情報をもつ単位格子を抽出するための手順
である。

【００１８】この場合においても、第ｎ格子の右側、前
方、左側のみならず、後方において第ｎ格子に隣接して
いる単位格子をも検索する。したがって、右側、前方、
左側の隣接格子から第１の情報が抽出できなくても、行
き詰まりにならないで、輪郭抽出の処理を進行させるこ
とができる。このように、本発明の第１、第２の輪郭抽
出方式の何れを用いても、あらゆるメツシュ状図形パタ
ーンの輪郭抽出を容易に行うことができる。

【００１９】

【実施例】次に本発明の実施例について図面を参照にし
て説明する。図１は本発明の輪郭抽出方式の第１の実施
例の処理手順を示す流れ図である。図２および図３は５
ｘ５の２値化された情報を持つメツシュ状図形に図１の
方式を適用して抽出された輪郭の実施例である。ここで
は、メッシュ状図形は、行方向と、それと直角に交わる
列方向に配列された２次元格子図形で、情報を空白部分
と斜線部分の２値に分け、斜線部分の輪郭が抽出され
る。以下の記述において、空白部分を論理０に対応さ
せ、斜線部分を論理１に対応させる。また、行方向を左
右と記し、列方向を上下と記す。更に、２次元格子の単
位格子を格子と記す。

【００２０】図１の処理手順は、２つの処理段階に大別
される。第１段階はステップ１０１から成り、第１段階
の処理によって、輪郭抽出処理の初期設定が行われる。
後述するように、本発明においては、現在、処理（輪郭
追跡）の対象にしている格子（現在の着目格子）と、当
該現在の着目格子の抽出方向とに基づいて次の着目格子
が追跡される。したがって、前記初期設定によって、初
期時、すなわち抽出開始時における着目格子が抽出開始
格子として設定され、かつ、抽出開始格子の抽出方向が
設定される。第２段階は初期設定された格子から出発し
て順々に輪郭を構成する格子を追跡する処理段階であ
る。本実施例では、輪郭は右回り（時計方向回り）に追
跡される。

【００２１】第２段階は、判断ステップ１０２、１０
５、１０８、１１１と、処理ステップ１０３、１０６、
１０９、１１２と、判断ステップ１０４、１０７、１１
０、１１３とを有する。判断ステップ１０２、１０５、
１０８、１１１は現在の着目格子の位置と直前の着目格
子の位置とを比較し、現在の着目格子の抽出方向を判定
する。処理ステップ１０３、１０６、１０９、１１２は
「ｘ，ｙ，ｚ，ｕの順で抽出」型ステップであるが、こ
のステップの定義は、上記の従来技術の項で説明した
「ｘ，ｙ，ｚの順で抽出」する処理の後にｕ方向の隣接
格子の抽出を付加する処理である。処理ステップ１０
３、１０６、１０９、１１２は、それぞれ判断ステップ
１０２、１０５、１０８、１１１によって判定された抽
出方向に向いて着目格子の左側に隣接した格子、前方
（抽出方向）に隣接した格子、右側に隣接した格子、後
方（当該抽出方向の逆方向）に隣接した格子を、この順
序に（左側から右側へ向って右回りに）検索して第１の
論理１をもつ格子を抽出し、この検索によって最初に抽
出された格子を次の着目格子と定める。判断ステップ１
０４、１０７、１１０、１１３は前記次の着目格子が抽
出開始格子であるか否かを判定する。次の着目格子が抽
出開始格子に戻れば、輪郭抽出の手順は総て終了する。
前記次の着目格子が抽出開始格子でなければ、当該次の
着目格子を現在の着目格子（処理対象格子）として、判
断ステップ１０２、１０５、１０８、１１１に戻って次
の着目格子の抽出を開始する。

【００２２】上記の現在の着目格子の抽出方向とは、従
来の技術の項に記されているのと同様に、直前の着目格
子に対する現在の着目格子の方向である。また、図１に
記載されている上、下、左、右の用語は、それぞれ、図
面（図２、３、４）の上、下および図面に向って左、右
の意味である。例えば、ステップ１０３は、ステップ１
０２によって着目格子の抽出方向が左→右であると判定
されることを前提とする処理である。したがって、ステ
ップ１０３の「上」とは、左→右の方向を基準とすると
「左」である。ステップ１０３の「右」とは、左→右の
方向を基準とすると「前方」である。ステップ１０３の
「下」とは、左→右の方向を基準とすると「右」であ
る。ステップ１０３の「左」とは、左→右の方向を基準
とすると「後方」である。したがって、ステップ１０３
の「上、右、下、左の順」は、抽出方向を基準にする
と、左→前→右→後の順序、すなわち左から開始する右
回りの順序になる。同様に、ステップ１０６、１０９、
１１２における検索の順序も、抽出方向を基準にする
と、左→前→右→後の順序、すなわち左から開始する右
回りの順序、すなわち、左優先の順序になる。このよう
に、処理ステップ１０３、１０６、１０９、１１２にお
ける検索の順序が左優先であるのは、図形の輪郭を右回
りに追跡するとき、その追跡方向に対して、その図形の
最も左側にある格子を輪郭として抽出する必要があるた
めである。以下の記述では、上記の右回りの検索を右回
り検索と記し、右回り検索によって最初に検索された第
１の情報をもつ格子を着目格子として抽出する処理を左
優先抽出と記す。後述するように、図形の輪郭を左回り
に追跡する場合には左回り検索によって右優先抽出が行
われる。

【００２３】次に、図２を参照して本実施例の動作を説
明する。先ず、初期条件を設定するために図形の最下段
の左から右に向かって格子の検索を行う。一段目が終了
したら上段に移動し、同様な検索処理を行う。そこで、
斜線部分の格子が検索されたら、その格子１を抽出開始
格子に設定し、かつ、抽出開始格子１の抽出方向を左→
右に設定する（ステップ１０１）。ステップ１０２によ
ってＹＥＳ判定が生成され、処理はステップ１０３に移
る。ステップ１０３によって、右側の隣接格子２が左優
先抽出され、格子２が着目格子になる。着目格子２は抽
出開始格子ではないと判定される（ステップ１０４）。
現在の着目格子２の位置と抽出開始格子１の位置を比較
し抽出方向は左→右であると判定し（ステップ１０
２）、処理をステップ１０３に移す。格子３を左優先抽
出し、該格子３を新着目格子とする。新着目格子３は抽
出開始格子１に戻っていないと判定する（ステップ１０
４）。着目格子３の抽出方向は左→右でないと判定する
（ステップ１０２）。着目格子３の抽出方向は下→上で
あると判定する（ステップ１０５）。格子４を左優先抽
出し（ステップ１０６）、該格子４を新着目格子とす
る。新着目格子は抽出開始格子でないと判定する（ステ
ップ１０７）。着目格子４の抽出方向は左→右でないと
判定する（ステップ１０２）。着目格子４の抽出方向は
下→上であると判定する（ステップ１０５）。格子３を
左優先抽出し（ステップ１０６）、該格子３を新着目格
子とする。新着目格子３は抽出開始格子でないと判定す
る（ステップ１０７）。着目格子３の抽出方向は左→右
でないと判定する（ステップ１０２）。着目格子３の抽
出方向は下→上でないと判定する（ステップ１０５）。
着目格子３の抽出方向は右→左でないと判定する（ステ
ップ１０８）。着目格子３の抽出方向は上→下であると
判定する（ステップ１１１）。格子２を左優先抽出し
（ステップ１１２）、該格子２を新着目格子とする。新
着目格子２は抽出開始格子でないと判定する（ステップ
１１３）。着目格子２の抽出方向は左→右でないと判定
する（ステップ１０２）。着目格子２の抽出方向は下→
上でないと判定する（ステップ１０５）。着目格子２の
抽出方向は右→左でないと判定する（ステップ１０
８）。着目格子２の抽出方向は上→下であると判定する
（ステップ１１１）。格子１を左優先抽出し（ステップ
１１２）、該格子１を新着目格子とする。新着目格子１
は抽出開始格子であると判定し（ステップ１１３）、輪
郭抽出を終了する。ここで、輪郭抽出された格子とその
内部の格子は抽出済とし、再度抽出されないように設定
する。輪郭抽出される図形が複数ある場合には、２回目
以降の輪郭抽出も同様な手順でメッシユ状図形の全てに
対して検索および抽出を行う。

【００２４】図３は本実施例を適用する第２のメッシユ
状図形の例である。図３の格子８も図２の格子４と同様
に、論理１をもつ１つの格子８に論理０をもつ３つの格
子が隣接するパターンを含む図形例である。この場合に
も、図２の図形と同様に、格子５から出発して上→右→
上→下→右→下→左→左の順で格子５、格子６、格子
７，格子８、格子７、格子９、格子１０、格子１１が抽
出され、輪郭を抽出することが可能となる。

【００２５】図４は本実施例を適用する第３のメッシユ
状図形パターンである。外枠の図形は論理１の図形の外
輪郭の抽出と論理０の図形の外輪郭の抽出を行うことに
よって、外側と内側との輪郭を抽出することが出来る。
内枠の図形の輪郭抽出も外枠を抽出する処理と同様な方
式を適用することにより輪郭を抽出することができる。
しかし、この場合には、図形が２つあるので、前掲のよ
うに、輪郭抽出された図形とその内部の格子は抽出済と
し、再度抽出されないように設定される。図４のメッシ
ユ状図形パターンの輪郭抽出方式は、地図情報等の等高
線の描画に応用することができる。以上説明した第１の
実施例は、図形の輪郭を右回りに抽出する例である。
同様の手順で図形の輪郭を左回りに抽出することも可能
である。

【００２６】図５は、本発明のメッシュ状図形の輪郭抽
出方式の第２の実施例を示す流れ図である。第２の実施
例では、ステップ２０３、２０６、２０９、２１２が左
回り検索をし、右優先抽出をする点が第１の実施例と異
なる。その他のステップは図１の流れ図と同様である。
また、第１の実施例では、輪郭抽出処理の初めに、図形
の最下段の左から右に向かって格子の検索を行い、一段
目が終了したら上段に移動し、第１の情報を持つ格子が
検索されたら、その格子を抽出開始格子に設定し、か
つ、抽出開始格子の抽出方向を左→右に設定する方式に
よって初期設定が行われた。しかし、初期設定は必ずし
もこの方式による必要はない。抽出開始格子を輪郭上に
設定し、抽出開始格子の抽出方向を、行方向または列方
向に沿って図形の外側から内側に向って設定することが
出来るならば、任意の方式を採用することが出来る。例
えば、図形の最下段の右から左に向かって格子の検索を
行い、一段目が終了したら上段に移動し、第１の情報を
持つ格子が検索されたら、その格子を抽出開始格子に設
定し、かつ、抽出開始格子の抽出方向を右→左に設定す
る方式を用いても、簡単に初期設定を行うことができ
る。

【００２７】

【発明の効果】以上説明した様に本発明は、追跡対象の
単位格子の検索範囲を、追跡方向に対して左側、前方、
右側のみならず、後方にまで拡張することにより、第１
の情報をもつ１つの単位格子が、第２の情報をもつ３つ
の単位格子に隣接されている場合においても、行き詰ま
りを生じることなく輪郭抽出を行うことが出来、その結
果、あらゆる２値化されたメッシュ状図形の輪郭抽出を
容易に行うことが出来る効果がある。

【図面の簡単な説明】

【図１】本発明の輪郭抽出方式の第１の実施例の処理手
順を示す流れ図である。

【図２】５ｘ５の２値化された情報を持つメツシュ状図
形に図１の方式を適用して抽出された輪郭の実施例であ
る。

【図３】５ｘ５の２値化された情報を持つメツシュ状図
形に図１の方式を適用して抽出された輪郭の実施例であ
る。

【図４】図１の方式を適用するメッシユ状図形パターン
の一例である。

【図５】本発明の輪郭抽出方式の第２の実施例の処理手
順を示す流れ図である。

【図６】格子点および格子を抽出する方式の一例を示す
流れ図である。

【図７】図６のステップ１１４の詳細な流れ図である。

【図８】メツシュ状の格子点上に２値化された情報をプ
ロットした図の一例である。

【図９】５x５のそれぞれの格子に対して２値化された
情報を与えた図である。

【符号の説明】

１０１初期設定ステップ１０２、１０５、１０８、１１１抽出方向判定ステッ
プ１０３、１０６、１０９、１１２左優先抽出ステップ１０４、１０７、１１０、１１３抽出開始格子に戻っ
たか否かを判定するステップ２０３、２０６、２０９、２１２右優先抽出ステップ

Claims

【特許請求の範囲】

【請求項１】２次元格子を形成して配列されている複
数の単位格子の各々に、第１、第２の論理値に対応させ
て２値化された画像の２値情報が配置されて成るメッシ
ュ状図形の、第１の論理値に対応する第１の情報を持つ
図形パターンの輪郭を抽出するメッシュ状図形の輪郭抽
出方式であって、前記輪郭を構成する、第１の情報をもつ単位格子の１つ
を輪郭抽出開始格子として初期設定し、該輪郭抽出開始
格子を第０格子とし、第２の論理値に対応する第２の情
報をもち、かつ、第０格子に隣接する単位格子に対する
第０格子の方向を第０格子の抽出方向と定め、第０格子の抽出方向を基準として第０格子の左側、前方
すなわち当該抽出方向、右側、後方すなわち当該抽出方
向の逆方向において第０格子に隣接している単位格子の
２値情報を、前記左側、前方、右側、後方の順序に検索
する第１検索を実行し、何れの単位格子からも第１の情
報が抽出されなかった場合には、輪郭抽出処理を終了
し、第１の情報が抽出される場合には、最初に第１の情
報が抽出された単位格子を第１格子と定めて処理を次に
進め、第０格子に対する第１格子の方向を判定し、その方向を
第１格子の抽出方向と定め、第１格子の抽出方向を基準
として第１格子の左側、前方すなわち当該抽出方向、右
側、後方すなわち当該抽出方向の逆方向において第１格
子に隣接している単位格子の２値情報を、前記左側、前
方、右側、後方の順序に検索する第２検索を実行し、第
２の検索において最初に第１の情報が抽出された単位格
子を第２格子と定め、第２格子が第０格子に一致するか
否かを判定し、一致する場合には輪郭抽出処理を終了
し、一致しない場合には処理を次に進め、第１格子に対する第２格子の方向を判定し、その方向を
第２格子の抽出方向と定め、第２格子の抽出方向を基準
として第２格子の左側、前方すなわち当該抽出方向、右
側、後方すなわち当該抽出方向の逆方向において第２格
子に隣接している単位格子の２値情報を、前記左側、前
方、右側、後方の順序に検索する第３検索を実行し、第
３検索において最初に第１の情報が抽出された単位格子
を第３格子と定め、第３格子が第０格子に一致するか否
かを判定し、一致する場合には輪郭抽出処理を終了し、
一致しない場合には処理を次に進め、以後、第ｎ検索によって最初に第１の情報が抽出された
単位格子を第ｎ格子とし、その直前の第ｎー１検索によ
って最初に第１の情報が抽出された単位格子を第ｎー１
格子として、第ｎ−１格子に対する第ｎ格子の方向を判
定し、その方向を第ｎ格子の抽出方向と定め、第ｎ格子
の抽出方向を基準として第ｎ格子の左側、前方、右側、
後方において第ｎ格子に隣接している単位格子の２値情
報を、前記左側、前方、右側、後方の順序に検索する第
ｎ＋１検索を実行し、第ｎ＋１検索において最初に第１
の情報が抽出された単位格子を第ｎ＋１格子と定め、第
ｎ＋１格子が第０格子に一致するか否かを判定し、一致
する場合には輪郭抽出処理を終了し、一致しない場合に
は一致するまで、抽出方向の判定、検索処理を繰返し、
第ｍ格子が第０格子に一致したとき輪郭抽出処理を終
了し、第０、第１、第２・・・・、第ｍー１格子を当該
図形パターンの輪郭とする、メッシュ状図形の輪郭抽出
方式。
【請求項２】輪郭抽出の初期時に、メツシユ状図形の
最下段または最上段の左から右へ格子の検索を行い、一
段目が終了したら、それぞれ上段または下段に移動し、
第１の情報の単位格子が検索されたとき、当該単位格子
を第０格子とし、前記左から右に向く方向を第０格子の
抽出方向に設定する、請求項１に記載の輪郭抽出方式。
【請求項３】２次元格子を形成して配列されている複
数の単位格子の各々に、第１、第２の論理値に対応させ
て２値化された画像の２値情報が配置されて成るメッシ
ュ状図形の、第１の論理値に対応する第１の情報を持つ
図形パターンの輪郭を抽出するメッシュ状図形の輪郭抽
出方式であって、前記輪郭を構成する、第１の情報をもつ単位格子の１つ
を輪郭抽出開始格子として初期設定し、該輪郭抽出開始
格子を第０格子とし、第２の論理値に対応する第２の情
報をもち、かつ、第０格子に隣接する単位格子に対する
第０格子の方向を第０格子の抽出方向と定め、第０格子の抽出方向を基準として第０格子の右側、前方
すなわち当該抽出方向、左側、後方すなわち当該抽出方
向の逆方向において第０格子に隣接している単位格子の
２値情報を、前記右側、前方、左側、後方の順序に検索
する第１検索を実行し、何れの単位格子からも第１の情
報が抽出されなかった場合には、輪郭抽出処理を終了
し、第１の情報が抽出される場合には、最初に第１の情
報が抽出された単位格子を第１格子と定めて処理を次に
進め、第０格子に対する第１格子の方向を判定し、その方向を
第１格子の抽出方向と定め、第１格子の抽出方向を基準
として第１格子の右側、前方すなわち当該抽出方向、左
側、後方すなわち当該抽出方向の逆方向において第１格
子に隣接している単位格子の２値情報を、前記右側、前
方、左側、後方の順序に検索する第２検索を実行し、第
２検索において最初に第１の情報が抽出された単位格子
を第２格子と定め、第２格子が第０格子に一致するか否
かを判定し、一致する場合には輪郭抽出処理を終了し、
一致しない場合には処理を次に進め、第１格子に対する第２格子の方向を判定し、その方向を
第２格子の抽出方向と定め、第２格子の抽出方向を基準
として第２格子の右側、前方すなわち当該抽出方向、左
側、後方すなわち当該抽出方向の逆方向において第２格
子に隣接している単位格子の２値情報を、前記右側、前
方、左側、後方の順序に検索する第３検索を実行し、第
３検索において最初に第１の情報が抽出された単位格子
を第３格子と定め、第３格子が第０格子に一致するか否
かを判定し、一致する場合には輪郭抽出処理を終了し、
一致しない場合には処理を次に進め、以後、第ｎ検索によって最初に第１の情報が抽出された
単位格子を第ｎ格子とし、その直前の第ｎー１検索によ
って最初に第１の情報が抽出された単位格子を第ｎー１
格子として、第ｎ−１格子に対する第ｎ格子の方向を判
定し、その方向を第ｎ格子の抽出方向と定め、第ｎ格子
の抽出方向を基準として第ｎ格子の右側、前方、左側、
後方において第ｎ格子に隣接している単位格子の２値情
報を、前記右側、前方、左側、後方の順序に検索する第
ｎ＋１検索を実行し、第ｎ＋１検索によって最初に第１
の情報が抽出された単位格子を第ｎ＋１格子と定め、第
ｎ＋１格子が第０格子に一致するか否かを判定し、一致
する場合には輪郭抽出処理を終了し、一致しない場合に
は一致するまで、抽出方向の判定および検索処理を繰返
し、第ｍ格子が第０格子に一致したとき輪郭抽出処理を終了
し、第０、第１、第２・・・・第ｍー１格子を当該図形
パターンの輪郭とする、メッシュ状図形の輪郭抽出方
式。
【請求項４】輪郭抽出の初期時に、メツシユ状図形の
最下段または最上段の右から左へ格子の検索を行い、一
段目が終了したら、それぞれ上段または下段に移動し、
第１の情報の単位格子が検索されたとき、当該単位格子
を第０格子とし、前記右から左に向く方向を第０格子の
抽出方向に設定する、請求項３に記載の輪郭抽出方式。