JPH024949B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、デイジタル画像上において所定の接
続関係を有する輪郭画素列（輪郭点列）を線分で
近似する処理を高速で実行するための輪郭画素列
線分化装置に関するものである。

〔従来技術〕

一般に、点列を線分で近似する処理方式は、
種々のものが報告されており、その中には相当な
高速処理を意図したものもある。

しかし、これらは、いずれも点列上の各点ごと
に近似誤差内に存在するかどうかを確認する処理
が不可欠であるので、最も演算量の少ないものを
採用しても、なお相当量の線分処似処理が必要で
ある。

したがつて、ロボツトの視覚機能などのように
実時間処理が重要である視覚処理において、その
まま数百点、数千点の線分近似処理に適用する
と、処理の高速化が阻害され、ほとんど実用に供
しえないので、その高速化が強く要望されている
ものである。

〔発明の目的〕

本発明の目的は、上記した現状に鑑み、デイジ
タル画像において所定の接続関係を保つて連結す
る輪郭画素列について、その線分近似処理を高速
で行うことができる輪郭画素列線分化装置を提供
することにある。

〔発明の概要〕

本発明に係る輪郭画素列線分化装置の構成は、
所望のデイジタル画像の輪郭画素列について線分
近似をするのに要する各種の点列パターンに関す
る所定の線分近似データを格納しておく線分近似
データメモリと、指定領域内の輪郭外周について
当該各輪郭画素ごとに順次に探索をしつつ、それ
らの各画素間の接続関係に基づいて上記線分近似
データを参照して線分化の各終点を判定して、輪
郭画素列の各線分近似を順次に行う探索・線分化
手段と、その線分化の各終点データを記憶してお
き、それらを線分近似の各頂点データとして出力
しうる頂点データメモリとからなるようにしたも
のである。

なお、その原理を更に詳しく具体的に以下で説
明する。

まず、画素列を線分化するとは、その各画素の
中心点を代表点として、上記画素列に代るべき代
表点列を線分化することである。ここで、各画素
は、例えば、画像を細かく正方区画に分けた１つ
の領域を表わすもので、その中心点の配列は、上
下左右に等間隔に並んだものである。

このような特殊な位置関係にある点群のうち、
第１図の指定画素に対する近傍画素関係図に示す
ように、同図ａ，ｂの４近傍、８近傍の接続関係
を保つた点列を線分近似することを考えると、線
分近似の対象となる点列の連結パターン数は、線
分の最大長の制限を設けるならば、有限数であ
る。

したがつて、本発明は、起こりうる全点列パタ
ーンを前もつてデータテーブルに効率よく記憶し
ておくことにより、線分近似処理において、近似
誤差を１点ごとに計算する代りに、データテーブ
ルの検索処理に置き換え、同等の結果を高速で得
るようにしたものである。

このデータテーブルには、画像上の指定領域の
輪郭を探索するときに次の輪郭画素を最も早く見
つけることができるように、探索アドレス（相対
アドレス）データも記憶しておき、輪郭線分化処
理の高速化を図つている。

次に、第２図は、本発明に係る線分近似データ
の形式図であつて、４連結を基準にして輪郭を探
索する場合の例である。

線分近似データは、第２図ａ，ｂに示す形式の
第１，第２データから構成される。

第１データについて説明する。線分近似処理に
おいて、第１番画素に対して第２番画素が存在す
る位置関係は、上、右横、下、左横の４パターン
であり、その４パターンに対するデータを順番に
配列する。その順番は、第１番画素の周囲を右回
りに第２番画素を探索することにしている。各パ
ターンのデータは、２項目ずつある。例えば、
IA１は第１番画素に対する第２番画素（真上に
位置するもの）の画像上での相対アドレスを示
し、IP１は第３番画素の線分近似処理に関する
データが格納されているエリアの先頭アドレスを
示す。すなわち、次に述べる第２データの先頭ア
ドレスを示す。

第２データについて説明する。このデータは、
線分化における第３番目以後の輪郭画素に１つず
つ対応して作成される。例えば、線分化を行う第
Ｌ番目の輪郭画素に対するデータの場合について
説明する。SA１は画像上における第（Ｌ−１）
番目の輪郭画素に対する第Ｌ番目の輪郭画素の候
補画素の相対アドレスを示す。このアドレスに従
つて候補画素を調べ、もし輪郭画素でなければ、
続いてSA２，SA３，SA４と順次に同様な調査
をする。SA３のアドレスが示す画素が輪郭画素
と決定したら、SP３の値は、第Ｌ番目の輪郭画
素の線分化情報を示す。

すなわち、SP３の値が第１データへのポイン
タを示す場合は、第Ｌ番目の画素を含んでいて
は、もはや線分化が不可能であることを表わし、
第（Ｌ−１）番目の画素までの線分化処理を行う
ように決定するための判定値となる。また、SP
３の値が再び第２データへのポインタを示す場合
は、現在の第Ｌ番目の画素を含んでも線分化が可
能であることを表わし、続いてポインタが指し示
すデータを用いて、第（Ｌ＋１）番目の輪郭画素
を探索する処理を継続するための判定値となる。

このように、第２データは、時計回りに一周の
探索ができるように、４つの方向に対する探索ア
ドレスデータ線分化判定値データ、および次の処
理データへのポインタを意味するデータの４組を
１単位として並べたものである。

上記の２形式の第１，第２データを起りうる全
パターンについて網羅するようにデータフアイル
として構成する。なお、各データ単位における４
つの方向のデータの組の配列順序は、時計回りに
するという原則を保つたまま、最も検索数が少な
くなるようにするものである。

〔発明の実施例〕

以下、本発明の実施例を図に基づいて説明す
る。

第３図は、本発明に係る輪郭画素列線分化装置
の一実施例のブロツク図、第４図は、その輪郭画
素探索部の一実施例のブロツク図、第５図は、同
線分近似処理部の一実施例のブロツク図である。

ここで、１００は、下記の各部の処理の流れを
制御する制御部、２００は、線分近似データメモ
リ、３００は、画像メモリ、４００は、探索・線
分化手段に係る輪郭画素探索部、４０は、その画
素読取り回路、４０２は、同比較回路、４０３
は、同輪郭画素判定回路、４０４は、同判定値登
録回路、４０５は、同輪郭画素記録回路、４０６
は、同画素読出し用のアドレス生成回路、５００
も、探索・線分化手段に係る線分近似処理部、５
０１は、その輪郭探索用のアドレス読取り回路、
５０２は、同アドレス更新回路、５０３は、同線
分近似データの読出し回路、５０４は、同判別回
路、５０５は、同終点処理回路、６００は、線分
化情報メモリ、７００は、頂点データメモリであ
る。

最初に、装置全体の処理・動作について第３図
に基づいて説明する。

入力INからのデイジタル画像は、まず画像メ
モリ３００に記憶される。

また、前述の第２図の線分近似データは、前も
つて、線分近似データメモリ２００に記憶させて
おく。

画像上のどの領域の輪郭を処理対象とするかを
指示する情報STが線分化情報メモリ６００へ入
力されることにより、本装置の処理が開始され
る。この領域を指示する情報STは、例えば、画
像上を左上端からラスター方向に領域探索を行つ
たとき、最初に見つかる画素のアドレスを領域代
表位置として指示することも考えられる。この領
域代表点が輪郭追跡の始点となり、また領域の外
周を一周追跡して終点ともなる。さらに、その他
の情報として対象領域を他の領域と分ける閾値が
記録される。

輪郭画素探索部４００は、領域代表位置の画素
の値を画像メモリ３００から読み込み、対象領域
内の各画素の値が閾値に対して大小いずれの側に
あるかを判定して、その結果を線分化情報メモリ
６００に記録しておく。

続いて、輪郭画素（代表位置の画素）の周囲
に、次の輪郭画素の候補画素を選択して、その画
素の値と閾値との比較を行つて対象領域の画素か
どうか判定する。この輪郭画素の候補の選択は、
例えば４連結（４近傍）を連結の基準とするとき
は上下左右の４画素が対象となる。８連結（８近
傍）のときは、周囲８画素が対象となる。

これらを、順次に時計回りに、１つ前の輪郭画
素を始点として、その次の画素から候補として選
択する。選択した候補画素が領域内の画素でなけ
れば、次の候補を選択する。

この選択処理は、線分近似処理部５００が線分
近似データメモリ２００からの次の探索アドレス
（相対アドレス）を読み込み、これを輪郭画素探
索部４００へ受け渡すことによつて行なわれる。
もし領域内の画素であると判定したら、これを次
の輪郭画素と決定する。決定した輪郭画素のアド
レスを探索時点のアドレスとして、線分化情報メ
モリ６００へ記録する。このアドレスを中心とし
て次の輪郭画素を探す。

輪郭画素のアドレスを記録するとともに、１つ
前の輪郭画素と新たに決定した現在の輪郭画素の
位置関係の情報（例えば上、下、左、右）すなわ
ち接続関係が線分近似処理部５００へ渡される。

線分近似処理部５００は、次々と送られてくる
輪郭画素の点列を線分で近似して、その近似線分
の各端点について頂点列として出力する処理を行
う。

この処理は、１本の線分化の始点と定めた輪郭
画素に続く第２，第３，……の輪郭画素列間の相
互の位置関係を、例えば、第２番目の画素は始点
の画素の右隣り、第３番目の画素は第２番目の画
素の上、というような表現形式にして、その情報
と線分近似データとを順次に照合して行われる。

線分近似データは、前述したように、例えば、
第１番目の画素から第Ｎ番目の画素までの画素列
（点列）を線分で近似することができた場合にお
いて、第（Ｎ＋１）番目の画素が第Ｎ番目の画素
の右隣りか上に位置しているときは第１番目の画
素から第（Ｎ＋１）番目の画素までの画素列は再
び同一線分で近似できるが、左隣か下に位置して
いるときは同一線分では近似できない、という情
報を起りうる全画素列パターン（Ｎは最大値Ｍ以
下とする）について線分近似データメモリ２００
に前もつて格納（記憶）しておくデータである。

線分近似処理部５００は、１つの輪郭画素情報
が輪郭画素探索部４００から入力されたとき、そ
の画素が何番目の画素であり、それまで入力され
て来た画素列のパターンに応じ、次には線分近似
データメモリ２００上のどこのデータを見ればよ
いか、１つ前の画素処理の結果によつて判断す
る。

例えば、Ｎ番目の輪郭画素が見つかり、その情
報が入力されると、線分近似処理部５００は、す
でに第（Ｎ−１）番目の画素を処理したときに求
めて記憶しておいた線分近似データ探索アドレス
を線分化情報メモリ６００から読み出し、そのア
ドレスをもとに線分近似データメモリ２００上の
データを読み込む。

このデータは、第Ｎ番目の輪郭画素を含んだ画
素列が線分で近似できるか否かを示すとともに、
もし線分で近似できる場合は、次に（Ｎ＋１）番
目の輪郭画素の探索アドレスおよび線分化に関す
るデータが格納されているエリアの先頭アドレス
を示す。

第Ｎ番目の輪郭画素までを含むと線分で近似で
きなくなる場合は、第（Ｎ−１）番目までの画素
列を線分で近似する。すなわち、第（Ｎ−１）番
画素のアドレスを線分の終点（頂点）座標として
頂点データメモリ７００に記録する。次いで、第
（Ｎ−１）番画素を再び次の線分近似の始点（第
１画素）と決定し、最後に入力した第Ｎ番画素を
第２番画素として、次に入力される輪郭画素（第
３番画素）に関する探索アドレスおよび線分化デ
ータが格納してあるエリアの先頭アドレスを、線
分化情報メモリ６００に記録する。

第Ｎ番目の輪郭画素を含んでも線分化が可能で
ある場合は、次に入力する画素に関する探索アド
レスおよび線分化データが格納してあるエリアの
先頭アドレスを線分化情報メモリ６００に記録す
る。

続いて、次の輪郭画素の探索アドレスを線分近
似データメモリ２００から読み込み、輪郭画素探
索部４００へ受け渡して、待機状態となる。線分
近似処理部５００が処理を終了して待機状態にな
つたことを確認してから、輪郭画素探索部４００
は、次の輪郭画素を探索する処理を開始する。

以上のようにして画素上の指定領域の輪郭画素
を１つずつ探索しながら、同時に線分化データテ
ーブルを検索して、線分化頂点データを出力す
る。処理の終了は、連続して探索された２つの輪
郭画素（第Ｓ番輪郭画素、第（Ｓ＋１）番輪郭画
素）が、輪郭探索処理開始画素と２番目の輪郭画
素に一致したことを、輪郭画素探索部４００にお
いて確認した後に行われる。

次に、輪郭画素探索部４００、線分近似処理部
５００の動作・処理を更に詳細に説明する。

第４図に基づいて輪郭画素探索部４００の説明
をする。

画素読出し用のアドレス生成回路４０６におい
て、１つ前の輪郭画素のアドレス４１８を読込
み、これに線分近似処理部５００から送られてき
た探索アドレス（相対アドレス）４１６を加えて
画素読出しアドレス４１９を出力する。

これを画素読取り回路４０が入力して、画像メ
モリ３００から対応画素値４１１を読込み、次の
比較回路４０２へ出力する。

比較回路４０２は、画素値４１１と閾値４１２
とを比較して、２値化データ４２０を出力する。
輪郭画素判定回路４０３は、この２値化データ４
２０と領域判定値４１３とを照合して、輪郭画素
判定フラグ４１７を線分近似処理部５００へ出力
するとともに、輪郭画素と判定されたときは、ア
ドレス登録指示フラグ４１４をも出力する。輪郭
画素記録回路４０５は、このフラグ指示によつて
上記アドレス４１９を輪郭画素アドレス４１５に
書き換えて線分化情報メモリ６００へ記録する。

領域画素判定値登録回路４０４は、領域の第１
番目の輪郭画素の２値化データ４２０を入力し
て、その領域判定値４２１を線分化情報メモリ６
００へ記憶する。

第５図に基づいて線分近似処理部５００の説明
をする。

輪郭探索用のアドレス読取り回路５０１は、線
分化情報メモリ６００からデータ検索アドレス５
１１が入力されると、これに従つて線分近似デー
タメモリ２００から次の輪郭画素を探索するため
の探索アドレス（相対アドレス）５１２を読み込
み、これを輪郭画素探索部４００へ同アドレス情
報５１６（第４図では４１６）として送るととも
に、アドレス更新フラグ５１３を出力する。

アドレス更新回路５０２は、このフラグを受取
つて先に受け取つたデータ検索アドレス５１１を
次のデータ検索アドレスに更新した更新アドレス
５１４を線分化情報メモリ６００へ出力する。

新しい輪郭画素が見つかつた旨の判定フラグ５
１７（第４図では４１７）が輪郭画素探索部４０
０から送られてくると、線分近似データの読出し
回路５０３は、データ検索アドレス５１５に従つ
て、線分近似データメモリ２００から線分近似デ
ータ５１８を読み出す。

判別回路５０４は、このデータを判別し、線分
化終点の確認が得られると、終点処理指示フラグ
５１９を送出し、終点処理回路５０５は、終点ア
ドレス５２０を線分化情報メモリ６００から読み
込み、１線分化の頂点データ５２に変換して頂点
データメモリ７００へ記録する。また、次の線分
化データ検索アドレス５２２を線分化情報メモリ
６００へ記録する。判別回路５０４は、線分化終
点とならない場合は、次の輪郭画素探索アドレス
データが格納されているエリアのアドレス５２３
を出力する。

以上のようにして、画像上の指定領域の輪郭を
線分で近似して多角形表現のデータを出力する
際、その都度、領域の追跡処理と線分近似計算と
を行なうのではなく、あらかじめパターン化した
線分近似データを記憶しておくことにより、効率
の良いデータ検索処理によつて高速に線分化処理
を行なうことができる。

〔発明の効果〕

以上、詳細に説明したように、本発明によれ
ば、所定の接続関係を保つて連続する輪郭画素列
について、その線分化処理を高速で行う輪郭画素
列線分化装置を実現することができるので、ロボ
ツト等に視覚機能を追加し、自動作業工程の機能
向上、効率向上、信頼性向上に顕著な効果が得ら
れる。

【図面の簡単な説明】

第１図は、指定画素に対する近傍画素関係図、
第２図は、本発明に係る線分近似データの形式
図、第３図は、同じく輪郭画素列線分化装置の一
実施例のブロツク図、第４図は、その輪郭画素探
索部の一実施例のブロツク図、第５図は、同線分
近似処理部の一実施例のブロツク図である。 １００…制御部、２００…線分近似データメモ
リ、３００…画像メモリ、４００…輪郭画素探索
部、５００…線分近似処理部、６００…線分化情
報メモリ、６００…頂点データメモリ。

Claims (1)

1. 【特許請求の範囲】 １ デイジタル画像の輪郭画素列について線分近
   似をする装置において、近似線分として認定され
   る各種の点列パターンごに各点列パターンの１部
   として次に連なるべき条件を満たした画素のパタ
   ーンを予め記憶した線分近似データメモリと、デ
   イジタル画像の或る輪郭外周について或る近似線
   分の終点の画素ごとに該画素に連なる輪郭画素を
   上記データメモリを参照して順次に決定して一連
   の近似線分を得る手段と、該手段によつて得た複
   数の近似線分の各終点を各近似線分の頂点データ
   として記憶するデータメモリを有することを特徴
   とする輪郭画素列線分化装置。 ２ 上記一連の近似線分を得る手段は、上記終点
   の画素に連なる輪郭画素となるべき候補画素を上
   記データメモリを参照して判定し、該候補画素か
   ら所定の閾値により上記連なる輪郭画素を選定す
   る手段であることを特徴とする第１項記載の輪郭
   画素列線分化装置。 ３ 上記一連の近似線分を得る手段は、上記終点
   の画素に連なつて該近似線分の一部となるべき輪
   郭画素がなくなつたとき、該近似線分が完成した
   ものとして該終点を上記頂点データメモリに登録
   し、別の近似線分を探索する手段であることを特
   徴とする第１項記載の輪郭画素列線分化装置。