JPS63204376A - 輪郭追跡方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は標本化された図形の輪郭追跡方法に係り、特に
圧縮符号化された図面や文書の画像から図形の輪郭座標
列を高速に得るのに好適な１輪郭追跡方法に関する。

〔従来の技術〕

従来、画像中の図形や物体の輪郭座標列の抽出を実行す
るための方法としては、特開昭５７−１１１７８６号に
記載のように、画像に対して互いに直交する２方向より
走査した時のそれぞれの画像変化点の座標をまず求め、
次にこれらの座標値の連続性を調べて輪郭座標列を得る
ようになっていた。

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

上記の従来技術では水平及び垂直方向のそれぞれの画像
変化点を抽出する必要があるが、この演算は画像全面に
亘る処理であるため処理量が多い。

さらに画像変化点の座標を抽出した後は、座標テーブル
上で一種のマスクを用いた追跡を行なうため処理時間が
大きくなるなどの問題があった。

本発明の目的は上記問題点を解決し、高速な輪郭追跡方
法を提供することにある。　　　′〔問題点を解決する
ための手段〕 上記目的は、画像変化点を１ライン毎に入力し、現在の
ラインの画像変化点と該現在ラインの一つ前のラインの
両像変化点を記憶し、該記憶された現在ラインの画像変
化点と該記憶された１つ前のラインの画像変化点とを参
照して輪郭線の一部を構成する基本形状を抽出し、該抽
出された基本形状を統合して輪郭座標列に変換すること
により達成される。

【作用〕

輪郭線の１部を構成する基本形状を抽出するために、記
憶された現在ラインの画像変化点と、このラインの１つ
前のラインの画像変化点（Ｘ座ＩＩ）を参照する。この
時の位置関係から特定の基本形状を抽出するとともに、
−ライン前の処理で抽出した基本形状との間をポインタ
で連結しておく。

１ラインについて基本形状の抽出が済むと、現在ライン
の画像変化点を前ライン記憶部に転送し、新たなライン
の画像変化点を現在ライン記憶部に入力する０以上の処
理を全ラインについて行った後、ポインタで連結された
基本形状を統合し１輪郭座標列を得る。

以上の方式により、１方向だけの画像変化点を用いて輪
郭追跡が実行できると共に、基本形状にポインタが付与
されているため、輪郭座標への変換が高速に実行できる
。

尚、現在ライン記憶部の内容を前ライン記憶部に転送す
る処理は、各ライン記憶手段のアドレスを交互に切替え
ることにより、実際のデータ転送を省くことができる。

〔実施例〕

以下本発明を図面を参照しながら説明する。第１図は本
発明の輪郭追跡方法の全体構成図である。

第１図において１は画像変化点ファイル、２は制御部、
３は画像変化点入力部、４は現在ラインバッファ、５は
前ラインバッファ、６は基本形状抽出部、７は基本形状
リンクテーブル、８は輪郭座標ファイルである０画像変
化点ファイル１にはライン毎の画像変化点の座標が格納
されており１画像変化点入力部３により、１ライン毎に
、ｌ！在シラインバッファ４入力される。この際、現在
ラインバッファ４に既に格納されていた画像変化点は前
ラインバッファ５に移される１次に基本形状抽出部６に
より、ラインバッファ４，５の内容を１つづつ読出し、
それらの座標の大小比較に基づいて１輪郭線の１部を構
成する基本形状を抽出する。

抽出した基本□形状は基本形状リンクテーブル７に格納
される。この際、１ライン前に抽出した基本形状との間
でポインタによるリンクを行なう、ラインバッファ４，
５の内容についてすべての基本形状の抽出が終えると１
次のラインの画像変化点を画像変化点ファイル１から読
出す０以上の処理が全ラインについて終えると、輪郭座
標変換部８は、基本形状リンクテーブル７の基本形状を
ポインタを辿りながら統合し１輪郭座標列を作成して、
輪郭座標ファイル９へ出力し、輪郭追跡を終える。

制御部２は以上の処理の全体を制御する。

第２図は基本形状抽出部６で抽出する基本形状１０種類
について示したものである６輪郭線はこの基本形状の組
み合わせですべて表現できる。この基本形状に■〜［相
］までの番号を付し、これをＲＤコード（ラン型方向コ
ード）と呼ぶことにする。ＲＤコードの先端の矢印部の
端点をＩ（ｓａｄ、逆の端点をＴａ１ｌと呼ぶ１図中黒
丸の部分はＲＤコードの代表点位置であり１位置を特定
するために決めたものである６輪郭線をＲＤコードと呼
ぶ基本形状で記述する場合、ＲＤコードのＨｅａｄは必
ず相手のＴａ１ｌにリンクするようにポインタを操作す
る。

第３図は画一サイズが８×６９画像中の図形をＲＤコー
ドを用いて、輪郭を記述した様子を示した例である０図
形５０の輪郭は１４個のＲＤコードを用いて（■■■・
・・＠）と表現できる。このＲＤコード列を一般の輪郭
座標列に変換するのは容易である。ＲＤコードの代表点
位置だけを輪郭線座標列とすると中間の座標が欠落する
が、これらは前後のＲＤコードの代表点位置を用いて補
間できる０例えば（■■・・・）において■の代表点位
置が（２，５，Ｌ、Ｓ）、■の代表点位置が（１，５゜
２．５）であれば、中間の座標は（２，５，２，５）と
なり、座標列は（（２，５，１，５）（２，５゜２．５
　）（Ｌ、Ｓ、２．５）・・・）となる、尚ここで代表
点位置が０．５　の端数を持つのは、画素中心の座標を
基準としているからであり、端数を切り捨てて簡略化し
ても良いことは言うまでもない。

第４図はラインバッファのデータ構造の１実施例を示し
たものであり、現在ラインバッファ４及び、前ラインバ
ッファ５には画像変化点のＸ座標列が格納されており、
データの最後には終了コードのが入っている。尚前ライ
ンバッファ５の読出しにはポインタＰ１、現在ラインバ
ッファ４の読出しにはポインタＰ２を用いる。

第５図は基本形状抽出部６のＲＤコード抽出用オートマ
トンを示したものである１図において下のライン間のラ
ンの組み合わせを示したものである。上段は前ラインの
ランの種類、下段は現在ラインのランの種類であり、Ｂ
は黒ラン（画像上で１すなわち黒画素の連続）、Ｗは白
ラン（Ｏすなわち白画素の連続）であることを示す１図
中Ｘ１は前ラインバッファ５から読出した画像変化点位
置、ｘ２は現在ラインバッファ４から読出した画像変化
点位置である。状態は全部で６つあり。

各ライン単位での走査開始及び終了時は必ず状態１を経
由する。各状態ではｘｌとＸ２の比較結果によって３種
類の状態遷移があり、そのときＲＤコード■〜［相］が
抽出される。各ラインバッファ５゜４からの画像変化点
Ｘｉ、Ｘ２の読出しの規則は。

比較した画像変化点の内、値の小さい方のラインバッフ
ァから読出すものとする。もし同じであれば両方のライ
ンバッファから読出す、このオートマトンによればたと
えばＲＤコード■の抽出条件は、状態１でＸＩ＞Ｘ２が
成立し、新たにＸ２を更新した後、状態３でＸｉ＞Ｘ２
が成立した場合と言える。これは図形的な解釈によれば
、現在着目しているラン（この例では黒ランである）の
上方が背景部分であったことを確認したことを意味する
。尚第４図で説明したようにラインバッファの最後には
ψコードが入っており、処理上これは左エツジＢと見な
す、したがって全データの続出になる。

第６図は第５図のオートマトンに基づき、具体的に実行
する処理を状態別にまとめたものである。

ｘｌとＸ２の大小条件に基づいて、ＲＤコードの代表点
位置のＸ座標の更新、ＲＤコードの抽出。

登録２次の状態への番号の更新２次の画像変化点の読出
しを行なう、尚ＲＤコードの登録時にはすでにリンク待
ちになっているＲＤコードとのリンク処理がある。ＲＤ
コードには、 （１）リンク待ちにならないもの ■［相］・・・Ｈｅａｄ、　Ｔａ１ｌがともに上向き（
２）リンク待ちになるもの ■■■■■■■■・・・Ｈｅａｄ　、またはＴａ１ｌが
下向きの２種類があり、（２）についてはＲＤコード抽
出時にリンク待ちリストとしてポインタで管理しておき
、現在抽出したＲＤコードとリンク待ちリストのＲＤコ
ードとを順次リンクしてゆく。

第７図は基本形状リンクテーブル７の一実施例である。

基本形状リンクテーブル７はＲＤコードの代表点位７１
１Ｘ、Ｙとそのコード番号Ｃ０ＤＥと、ＲＤコード間を
リンクするＬＩＮＫポインタと、ＲＤコードのリンク待
ちになっているものを一時的にリスト化しておくＷ−Ｌ
ＩＮＫポインタの５項からなるテーブルである。また基
本形状リンクテーブル７を操作するためのポインタとし
てＡ。

Ｂ、Ｃの３つがある。Ａポインタは新規のＲＤコードを
登録するアドレスを指すポインタである。

Ｂポインタはリンク待ちＲＤコードリストの先頭アドレ
スを指すポインタであり、Ｃポインタはリンク待ちＲＤ
コードリストの最終アドレスを指すポインタである。尚
第７図の値は第３図の画像を処理した例である。

第８図は、第１図の制御部２の輪郭追跡処理手順を流れ
図（ＰＡＤ）で示したものである。尚、流れ図中で使わ
れる変数名を定義しておく。

Ｃ−Ｌｉｎｅ　−Ｂｏｆｆｏｒ　：現在ラインバッファ
４Ｐ　−Ｌｉｎｅ−Ｂｕｆｆｅｒ　Ｓ前ラインバッファ
５Ｓｔａｔｕｓ　：状態番号（１〜６） Ａ、Ｂ、Ｃ：ポインタ Ｆｌａｇ：Ｂポインタの制御フラグ（０又は１）に：現
在走査中の画像のライン番号 Ｎ７８画像の最大ライン数 ＲＤ　−Ｌｉｓｔ　：基本形状リンクテーブル７く輪郭
追跡処理の流れ〉 ５ｔｏｐｌ：初期化 Ｃ−Ｌｌｎａ−Ｂｕｆｆｅｒ（１）　＝ｏｏ　；現在ラ
インバッファ４を「空」にする。

５ｔａｔｕｓ＝　１　：オートマトンの初期状態を１に
する。

Ａ＝Ｏ，Ｂ＝１．Ｃ＝１．Ｆｌａｇ＝Ｏ；各種変数の初
期化 ５ｔｏｐ２　：　ＮＹ＋１．回以下の処理を実行５ｔｏ
ｐ２．１　ニラインバッファのシフトここでバッファシ
フトは、実際にデータ転送は行なわず、Ｋの奇数、偶数
に基づいてラインバッファのアドレスを切り替える方式
である。

Ｃ−Ｌｉｎｅ−Ｂｏｆｆｏｒの内容をＰ　−Ｌｉｎｅ　
−Ｂｕｆｆｅｒへ転送する（実際はＣ−Ｌｉｎｅ−Ｂｏ
ｆｆｏｒとＰ　−Ｌｉｎｅ−Ｂｏｆｆｏｒのアドレスを
切替える） Ｓｔａｐ２　、２　：　１ライン分の画像変化点の読出
し、もしＫ＞ＮＹであれば、Ｃ−Ｌｉｎｅ−Ｂｕｆｆｅ
ｒ（１）＝ψそれ以外であれば１画像変化点ファイル１
かも１ライン分の画像変化点を読出し、Ｃ−Ｌｉｎｅ−
Ｂｏｆｆｏｒ　ヘセットする。

５ｔｏｐ２　、３　：　２ライン間での輪郭追跡のため
の初期化 Ｐｚ＝１．Ｐｚ＝１　ニラインバッファ５，４の読出し
ポインタの初期化 Ｘ　１　＝　Ｐ　−Ｌｉｎｅ−Ｂｏｆｆｏｒ　（Ｐ　Ｌ
　）　　：前ラインバッファ５の先頭データを変数Ｘ１
にセット Ｘ　２　＝　Ｃ−Ｌｉｎｅ−Ｂｕｆｆｅｒ　（Ｐ　２　
）　　；現在ラインバッファ４の先頭データを変数ｘ２
にセット ５ｔｏｐ２　、４　：　２ライン間での輪郭追跡処理（
ＸＩ、Ｘ２が共にψコードになるまで以下の処理を実行
） Ｓｔａｐ２．４．ｌ　：　ＲＤコード抽出、賛録、リン
ク処理 ５ｔｏｐ２．４．２　：　Ｘｉ、Ｘ２＋７１データ更新
（注）Ｓｔｅｐ２．４．１，２．４．２は第６図の表に
基づくものとする。

５ｔｏｐ　３　：　５ｔｏｐ　２で求めたＲＤコードを
座標列へ変換する。

以上本実施例によれば、輪郭追跡のための画像メモリは
２ライン分のラインバッファで済むため経済的であると
ともに、一方向の画像変化点位置しか輪郭追跡に利用し
ておらず、二方向の画像変化点位置を利用する方式に比
べると高速である。

また輪郭線を構成する１０種類の基本形状は、あらゆる
図形に対して適用できる汎用的なものであり１図形の輪
郭を忠実に記述できる。又通常文書や図面の画像ファイ
ルはランレングス符号化されており、本発明の輪郭追跡
方式との整合性が良い。

さらに本実施例では特殊や演算器は用いておらず、通常
の汎用計算機を用いても高速性が保証される。

〔発明の効果〕

本発明によれば、１方向だけの画像変化点を用いて輪郭
追跡が実行できると共に、２ライン間の画像変化点の位
置比較から抽出した基本形状には。

ポインタが付与されているため、輪郭座標への変換に際
して余分なサーチが不要となり、したがって高速に輪郭
座標列を得られる効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例の全体構成図、第２図は基本
形状の種類、第３図は第２図の基本形状を用いた図形の
輪郭記述例。、第４図はラインバッファのデータ構造、
第５図は第１図の基本形状抽出部のオートマトン、第６
図は第５図のオートマトンを状態別に表にした、画像変
化点解析衣、第７図は第１図の基本形状リンクテーブル
のデータ構造、第８図は、処理全体の流れ図（ＰＡＤ）
である。 １・・・画像変化点ファイル、２・・・制御部、３・・
・画像変化点入力部、４・・・現在ラインバッファ、５
・・・前ラインバッファ、６・・・基本形状抽出部、７
・・・基本形状リンクテーブル、８・・・輪郭座標変換
部、９・・・輪郭座標ファイル、　　　　　　　　　　
　　　　、　　、代理人　□よ　４１，１１□甲　。 ■　Ｚ　図 ￥Ｊ　３　図　　　　　　　５０図形部会 Ｎｒ（（Ｄ■■■■■■■■■■■■Ｏ）不　４　図 ４　　彬巳在−ライ〉へ°ゾ々 ５　　哨ηラインハ“ン７ｒ 篤　５　図 （ａ）オーシマトンの全体図 Ｖ：Ｊ　６　口 冨　７　　図

Claims (1)

【特許請求の範囲】
1. １．画像変化点で記述された画像から図形の輪郭線を追
   跡して輪郭座標列を作成する輪郭追跡方法において、 画像変化点を１ライン毎に入力し、 現在のラインの画像変化点と該現在ラインの一つ前のラ
   インの画像変化点を記憶し、 該記憶された現在ラインの画像変化点と該記憶された１
   つ前のラインの画像変化点とを参照して輪郭線の一部を
   構成する基本形状を抽出し、該抽出された基本形状を統
   合して輪郭座標列に変換することを特徴とする輪郭追跡
   方法。