JPH01136282A - 輪郭線追跡方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はランレングスコードに変換した２値画像の輪郭
線を追跡する輪郭線追跡方法に関する。

〔従来の技術〕

２値画像の輪郭を追跡する方法の１つとしてフリーマン
（Ｆｒｅｅｍａｎ）の方法が知られている。例えば第２
図に示す如き原画像の輪郭線を追跡する場合、先ずラス
タが左上から右下方向に順次走査され、最初の黒点が始
点とされる。次に始点から白地（点）を右手に見て隣接
する黒点が追跡される。

隣接方向は第３図に示すように８通りあり、各々の方向
に０゛乃至７のチエインコードが対応される。

輪郭線はこのチエインコードの集合として表現される。

例えば第２図の原画像の外側の輪郭線は、内側の輪郭線
は。

の各チエインコードで表わされる。

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

従来の方法はこのように１つの注目点から次の追跡方向
を決定するのに、その注目点に隣接する８画素のデータ
を読み込む必要があり、その８つのデータから最終的に
は１つのチエインコードしか生成することができないの
で、チエインコードに変換する９に演算時間が長くかか
る欠点がある。

また原画像をそのまま使用するのでデータを記憶するメ
モリの容量が大きくなる欠点がある。

そこで本発明は演算時間を短くし、かつ少ない容量のメ
モリを用いることができるようにするものである。

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

本発明の輪郭線追跡方法は、原画像をランレングスコー
ドに変換する工程と、所定の注目点を含むランの上側又
は下側のうち一方に隣接するランの一方の端点を追跡し
、この追跡に対応したコードを発生する工程と、他方の
ランの他方の端点を追跡し、この追跡に対応したコード
を発生する工程とを備えることを特徴とする。

〔作用〕

原画像はランレングスコードに一旦変換される。

そして所定の注目点を含むランの例えば下側に隣接する
ランの例えば左側の端点が追跡され、この追跡に対応し
たコードが発生される工程と、上側に隣接するランの右
側の端点が追跡され、この追跡に対応したコードを発生
する工程のいずれかが順次実行される。

従ってメモリの容量を小さくし、かつ全ての輪郭線をコ
ードで表現するのに必要な時間を短くすることか可能に
なる。

〔実施例〕

第４図は本発明の輪郭線追跡装置のブロック図である。

同図において１は原画像のデータを入力する入力手段、
２は入力手段１から入力されるデータをランレングスコ
ードに変換するエンコーダである。３はメモリであり、
エンコーダ２の出力を記憶する。４は輪郭線を追跡する
追跡手段である。５は追跡方向に対応したチエインコー
ドを発生する発生回路、６はチエインコードを記憶する
メモリである。７は例えばマイクロコンピュータ等より
なる制御手段であり、各手段を制御する。

しかして入力手段１より入力された原画像のデータはエ
ンコーダ２によりランレングスコードに変換された後、
メモリ３に記憶される。すなわち左側の端点（始点）ｓ
ｉと右側の端点（終点）ｅｉにより表わされるランの集
合がメモリ３に記憶される。例えば第５図に示すような
原画像は、端点Ｓ１、ｅｌ乃至Ｓ７、ｅｌにより表わさ
れる７つのランの集合とされる。

制御手段７は追跡手段４を制御し、メモリ３に記憶され
たデータを読みだして第１図に示す如きフローチャート
に従って追跡処理を実行させる。

先ず所定の注目点（所定のランの始点）が選定され、そ
の注目点を含むランの下に隣接するランの始点の追跡が
行われる。この追跡ができないときは、次に注目点を含
むランの上に隣接するランの終点の追跡が順次行われ、
全ての隣接するランが追跡されたとき、追跡処理は終了
される。

このような下方向の追跡と上方向の追跡を行うため、第
１表に示す如き追跡（サーチ）パターンが予め設定され
ている。

下方向の追跡はケース１からケース５までの５種類とさ
れる。ケース１は現在の注目点（始点）を含むランの下
に隣接するランが存在しない場合であり、この場合は注
目点を含むランの始点から終点までの追跡が行われ、第
３図に示すチエインコードＯがその間の画素数分だけ対
応される。またこの場合追跡が行われた後、次は上方向
への追跡に移行される。ケース２は次のラン（下行のラ
ン）の注目点（始点）が現在の注目点の真下に隣接して
いる場合であり、チエインコードは６となる。ケース３
は次のラン（下行のラン）が現在のランのいずれかの画
素に、現在の注目点より右側（後方）で隣接している場
合である。この場合のチエインコードは、次の注目点の
左上に位置する画素までの画素数分の０と、１つの７と
なる。ケース４はケース３とは逆に、現在の注目点が、
次のラン（下行のラン）のいずれかの画素に１次の注目
点（始点）より右側（後方）で隣接する場合（次の注目
点が現在の注目点より左側（前方）に位置する場合）で
ある、この場合のチエインコードは５と、次の注目点か
らそのランの現在の注目点が左下に隣接する画素までの
画素数分の４となる。ケース５はケース４のさらに特殊
な場合であって、現在の注目点を含むランと同一行の左
側に他のランがあって、そのランが下行のランを介して
現在のランに隣接している場合である。この場合のチエ
インコードは５と３、又はその間に、左側のランの終点
と現在の注目点との間の画素数から１を引いた数の４を
付加したものとなる。このケースの場合は次に上方向へ
の追跡に移行される。

上方向の追跡はケース６からケース１０までの５種類と
される。ケース６は現在の注目点（終点）を含むランの
上に隣接するランがない場合であり、終点から始点まで
の追跡が行われ、その間の画素数分の４がチエインコー
ドとなる。この場合は次に下方向への追跡に移行される
。ケース７は現在の注目点（終点）の真上に次の注目点
（終点）がある場合で、チエインコードは２となる。ケ
ース８は現在の注目点（終点）に隣接する画素を含む上
行のランの終点（次の注目点）が、現在の注目点より右
側（後方）に位置する場合である。この場合のチエイン
コードは１と、現在の注目点の右上に隣接する画素の右
の画素から次の注目点までの画素数分のＯとなる。ケー
ス９は次の注目点（終点）が現在のランに現在の注目点
（終点）より左側で隣接する場合である。チエインコー
ドは、現在の注目点から次の注目点の右下に隣接する画
素までの間の画素数分の４と、１つの３となる。ケース
１０はケース８の特殊な場合であって、現在のランと同
一行で現在のランより右側に他のランがあり、そのラン
と現在のランが上行の同一のランに隣接している場合で
ある。チエインコードは１と７．又はその間に、現在の
注目点と次のランの始点との間の画素数から１を引いた
数のＯを付加したものとなる。このケースの場合法の追
跡方向が下方向に移行される。

制御手段７は追跡手段４を制御し、メモリ３に記憶され
ているデータを読み出させ、上述したパターンに従って
輪郭線の追跡を実行させる。第６図と第７図は、現在の
注目点より下方向の追跡と上方向の追跡を行う場合のよ
り詳細なフローチャートを各々表わしている。

下方向の追跡を行う場合、先ず現在の注目点（始点）を
含むランとその下行のランとの隣接関係の検索が行われ
る。現在のランの下行に複数のランが存在する場合、最
も左側のランと現在のランとの隣接関係が先ず判断され
る。現在のランとその下行のランがケース２，３又は４
の隣接関係にある場合、追跡手段４からの出力に対応し
て発生手段５は上述した所定のチエインコードを発生す
る。このチエインコードはメモリ６に記憶される。

チエインコードが発生された後、注目点が移動され、次
の注目点が現在の注目点とされ、同様の処理が実行され
る。

ケース５の隣接関係にある場合、対応するチエインコー
ドが発生され、注目点が移動された後、上方向の追跡に
移行される。

現在のランが下行の最も左側のランと隣接関係にない場
合（ケース２．３．４，５のいずれにも屈しない場合）
、そのランの右側のランとの隣接関係が判定される。以
下同様にしてその行のすべてのランに対する隣接関係が
順次検索される。

現在のランの下行に隣接するランが他にない場合、ケー
ス１と判定され、対応するチエインコードが発生され、
注目点が移動された後、上方向の追跡ルーチンに移行さ
れる。

上方向における追跡においては、現在の注目点（終点）
を含むランとその上行のランとの隣接関係の検索が行わ
れる。この場合もその行に複数の行がある場合は最も左
側のランとの隣接関係が先ず判定される。

現在のランとその上のランとがケース７．８又は９の隣
接関係にある場合、各々に対応するチエインコードが発
生され、注目点が移動され、同様の処理が行われる。

ケース１０の隣接関係にある場合、対応するチエインコ
ードが発生され、注目点の移動が行われる。次の注目点
が既に追跡済みであれば追跡処理は終了され、追跡済み
でなければ再び下方向の追跡処理ルーチンが実行される
。

ケース７．８．９，１０のいずれの隣接関係にも属しな
い場合、その行に他のランが存在するときはそのランと
の隣接関係が判定される。存在しないときはケース６と
判定され、対応するチエインコードが発生され、注目点
の移動が行われる。

そしてすべての注目点が既に追跡されているときは追跡
が終了され、未追跡の注目点があるときは再び下方向の
追跡が実行される。

一上述した原理に基いて第５図の如き原画像の輪郭線処
理を行うと第２表のようになる。ラン（Ｓｌ、ｅｌ）の
始点ｓ１を最初の注目点として下方向の追跡を行うと、
このランの下行には２つのラン（ｓ２．ｅ２）、（ｓ３
．ｅ３）があるので、先ずラン（ｓｌ、ｅｌ）とラン（
ｓ２、ｅ２）との隣接関係が判定される。しかしながら
この２つのランは相互に隣接していない。従って次にラ
ン（Ｓｌ。

ｅｌ）とラン（ｓ３．ａ３）の隣接関係が判定される。

両者はケース４に相当するのでチエインコード５．４が
メモリ６に記憶される。次に注目点はｓｌから８３に変
更される。ラン（ｓ３、ｅ３）とラン（ｓ２、ｅ２）は
ケース５に相当するのでチエインコードは５．３となる
０次の注目点はｅ２とされ、ラン（ｓ２、ｅ２）につい
て上方向の追跡が行われる。ラン（ｓ、　２、ｅ２）の
上行にラン（ｓｌ、ｅｌ）が存在するが、両者は隣接し
ていない。そこでケース６と判定され、チエインコード
は４．４となる。注目点はｓ２に変更され、下方向の追
跡が行われる。注目点ｓ２を含むラン（＋２．ｅ゛２）
の下行には２つのラン（＋４．ｅ４）と（＋５、ｅ５）
がある。左側のランとの関係が先に判定されるのでケー
ス２に相当し、チエインコードは６となる。注目点ｓ４
の下行にはラン（＋６、ｅ６）が存在するのでケース３
となり、チエインコードは０．７となる。注目点ｓ６の
下行にはラン（Ｓ７、ｅ７）が存在するのでケース３と
なり、チエインコードは７となる。注目点ｓ７の下行に
はランが存在しないのでケース１となり、チエインコー
ドはＯ，ｏとなる。ここで追跡方向が反転される。注目
点ｅ７の真上に上行のランの終点ｅ６があるのでケース
７となり、チエインコードは２となる。注目点ｅ６の上
行には２つのラン（＋４、ｅ４）と（＋５、ｅ５）があ
る。左側のラン（＋４、ｅ４）との関係はケース８とな
り、チエインコードは１となる。注目点ｅ４は同一行の
右側のラン（ｓ　５．　ｅ　５）に対してケース１０の
隣接関係にあるので、チエインコードは１，７となる。

ここで下方向の追跡に移行される。注目点ｓ５の下行に
はラン（＋６、ｅ６）が存在するが隣接関係にはないの
でケース１とされ、チエインコードは０となる。注目点
ｅ５から再び上方向の追跡が行われる。

注目点ｅ５の上行の左のラン（ｓ　２．　ｅ　２）は隣
接関係にない。右のラン（＋３．ｅ３）の終点が注目点
ｅ５の真上にあるのでケース７となり、チエインコード
は２となる。注目点ｅ３を含むランとその上行のラン（
ｓｌ、ｅｌ）とはケース９の隣接関係となる。従ってチ
エインコードは３となる。注目点ｅ１の上行にはランが
存在しないのでケース６に相当する。その結果チエイン
コード４．４が得られる。注目点ｓ１は既に追跡してい
るので、ここで追跡は終了される。

このようにしてメモリ６には各注目点の座標とチエイン
コードとが記憶される。

〔発明の効果〕

以上の如く本発明によれば、画像データをランレングス
コードに変換した後、各ランの端点を下方向又は上方向
に追跡するようにしたので、１回の追跡で複数画素の輪
郭を追跡することができ、高速な輪郭追跡が可能となる
。また輪郭追跡に必要とされるデータはランの端点の座
標だけであるので小さい容量のメモリを用いることが可
能となる。

【図面の簡単な説明】

第１図は本発明の輪郭追跡のフローチャート、第２図は
フリーマンのチエインコードによる追跡方法の原画像の
説明図、第３図はチエインコードの説明図、第４図は本
発明の輪郭線追跡装置のブロック図、第５図はその輪郭
追跡の原画像の説明図、第６図はその下方向追跡のフロ
ーチャート、第７図はその上方向追跡のフローチャート
である。 １・・・入力手段 ２・−・エンコーダ ３・・・メモリ ４・・・追跡手段 ５・・・発生手段 ６・・・メモリ ７・・・制御手段 ｙｉ、＋１ 第２図 第４０ ２ド２♀４１ト巧ト五イ珂岨

Claims (1)

1. 【特許請求の範囲】 原画像をランレングスコードに変換する工程と、所定の
   注目点を含むランの上側又は下側のうち一方に隣接する
   ランの一方の端点を追跡し、この追跡に対応したコード
   を発生する工程と、 他方のランの他方の端点を追跡し、この追跡に対応した
   コードを発生する工程とを備えることを特徴とする輪郭
   線追跡方法。