JPH0447867B2 - - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、例えば視覚認識システム等において
テレビカメラで捉えた物体の形状を把握するため
に、その物体の輪郭を構成する二値画像に対して
画面走査順に得られる輪郭点データ群から、物体
の輪郭に沿う輪郭線データを抽出する輪郭線抽出
装置に関するものである。

〔従来の技術〕

一般に視覚認識システム等においては、物体の
輪郭を構成する二値画像から、物体の形状を抽出
したり、例えば物体の重心位置や物体の輪郭の周
囲長等の各種パラメータを求めるにあたり、計算
のやり易さ等の観点からして、物体の輪郭に沿つ
て配列される輪郭線データを抽出することが必要
となる。即ち、例えばテレビカメラから得られた
濃淡画像における濃淡の境界から輪郭点データを
生成し、その輪郭点データに基づいて閉ループを
形成する輪郭線データを抽出することが必要とな
る。

第５図および第６図は従来方式による輪郭線抽
出を説明するための図である。

従来におけるこの種の輪郭線抽出方式として
は、例えば第５図に示すように、物体の輪郭を構
成する二値画像GDが表示される画面１上に、ｘ
−ｙ座標系を予め設定し、上記画面１を走査２す
ることにより、上記二値画像GDの輪郭点データ
群（x₁，y₁）（x₂，y₂）……（x_o，y_o）を画面走
査順に得て、これらを輪郭点データメモリ３に格
納し、しかる後上記輪郭点データ群に輪郭線抽出
処理を施し、上記輪郭点データ群を物体の輪郭の
例えば反時計回り方向（図中ｍで示す）に沿う輪
郭線データ（x_A1，y_A1）（x_A2，y_A2）……（x_Ao，
y_Ao）として抽出し、輪郭線データメモリ４に格
納するようにしたものがある。この方式におい
て、上記輪郭線抽出処理としては、例えば第６図
に示すように、輪郭点データ中に始点Ｐ（x_i，y_i）
を定め、この始点に連結可能な８つの囲繞位置Ａ
ないしＧについて上記輪郭点データメモリ３を検
索して、始点Ｐの次に連結される次輪郭点を抽出
した後、当該抽出された輪郭点の次に連結される
次輪郭点を上述したのと同様にして抽出し、以後
この手順を繰り返すことにより、抽出した輪郭点
を輪郭線データとして輪郭線データメモリ４に順
次格納するようしている。

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

しかしながら、このような従来の輪郭線抽出方
式あつては、ある１つの輪郭点の次に連結される
次輪郭点を抽出するために、１つの輪郭点を囲繞
する８個所すべてのデータ値について輪郭点デー
タメモリ３を検索しなければならないことから、
最終的な輪郭線データを得るまでにおいて必要な
輪郭点データメモリ３の検索回数が膨大なものと
なつてしまい、その分、輪郭線抽出のための処理
時間が大幅にかかるという問題があつた。

この問題を解決するために、本願発明者は、先
に特願昭58−225622号に示されるような輪郭線抽
出装置を提案している。この提案の発明によれ
ば、輪郭点データ群を格納するメモリを１回走査
して、中間的なデータ点列を点列バツフアに格納
し、各データ点列を結合させることによつて、輪
郭線データを抽出するようにしている。１回だけ
の走査で順次輪郭点データを処理していくことが
できるので、輪郭線データ抽出を極めて高速に行
うことができるようになつている。

上記提案の発明において、上記点列バツフアが
不要となれば、メモリ領域を節減できるので、よ
り望ましい。

本発明は上記問題点の解決を図り、処理時間の
高速化を可能とすると共に、上記提案の発明をさ
らに改良発展させ、比較的大きなメモリ領域を必
要とする点列バツフアを設けずに、同様な輪郭線
データの抽出を可能とする輪郭線抽出装置を提供
することを目的としている。

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

そのため本発明は、先に提案した発明におい
て、最初に読み出した輪郭点データを、一対のデ
ータ点列の双方の始点とし、データ点列を一旦点
列バツフアに格納することはしないで、代わりに
輪郭点の連結関係の情報を連結情報メモリに持つ
ようにし、中間的なデータ点列を連結情報メモリ
によつて管理するようにしている。即ち、本発明
の輪郭線抽出装置は、物体の輪郭を構成する閉ル
ープ二値画像に対して画面走査順に得られる輪郭
点データ群を物体の輪郭に沿う輪郭線データとし
て抽出する輪郭線抽出装置であつて、上記輪郭点
データ群を格納する輪郭点データメモリと、処理
される各データ点列の端点に対応する各点列端点
データを記憶する点列端点記憶手段と、上記各輪
郭点データ毎にその連結する輪郭点データを指す
ポインタ情報を記憶する連結情報メモリと、上記
輪郭点データメモリから読み出した輪郭点データ
が上記点列端点記憶手段に記憶されている点列端
点データと隣接するか否かを判定する手段を有す
るデータ抽出処理手段と、該データ抽出処理手段
により上記輪郭点データが上記点列端点データに
連結しないと判定されたときに当該輪郭点データ
を新しいデータ点列の始点として検出しこれを上
記点列端点記憶手段に格納する始点検出手段と、
上記データ抽出処理手段により上記輪郭点データ
が先に検出された点列端点データに連結すると判
定されたときに当該輪郭点データを延長点として
検出しこれを上記点列端点記憶手段に格納すると
共にその連結する輪郭点データを指すポインタ情
報を上記連結情報メモリに格納する延長点検出手
段と、上記連結情報メモリに格納された情報に基
づき各点列データの端点を比較して各端点相互の
連結関係を判定し連結され得る各点列同士を結合
して閉ループ状の輪郭線データを抽出する閉ルー
プ形成手段と、該閉ループ形成手段からの輪郭線
データが格納される輪郭線データメモリとを備え
たことを特徴としている。以下、図面を参照しつ
つ、実施例に従つて説明する。

〔実施例〕

第１図は本発明の一実施例構成、第２図は第１
図図示実施例の具体的な処理態様を説明するため
の図、第３図は第１図図示実施例による処理概要
を説明するためのフローチヤート、第４図は始点
と連結点との関係を説明するための図を示す。

第１図において、輪郭点データメモリ３は、例
えば第２図ａに示すような物体の輪郭を構成する
閉ループ輪郭二値画像に対して、画面走査順に得
られる輪郭点データ群を格納するメモリである。
第２図ａのような二値画像の場合、輪郭点データ
メモリ３には、第２図ｂ図示のような情報が設定
される。輪郭線データメモリ４は、輪郭線の抽出
結果が格納されるメモリであつて、第２図ａのよ
うな二値画像の場合、第２図ｇに示すように、輪
郭点データ群を物体の輪郭に沿う輪郭線データと
して最終的に記憶保持するものである。

データ抽出処理部１０は、輪郭点データメモリ
３から順次読み出した輪郭点データを処理するも
のであつて、圧縮回路１１と処理判定回路１２と
連結点判定回路１３とからなる。圧縮回路１１
は、本発明では必須ではないが、中間処理対象と
なる輪郭点データ数を削減して、処理の一層の高
速化とメモリの節減を可能とするために、輪郭点
データメモリ３から輪郭点データを読み出す際、
例えば水平方向に連続した点を、新たに１つ輪郭
点データとしてまとめる処理を実行するものであ
る。即ち、圧縮回路１１は、ｙ座標が等しくｘ座
標が１増加するデータを、第２図ｃに図示するよ
うにまとめる。第２図ｂに示した輪郭点データメ
モリ３の内容に対して、圧縮回路１１の出力は、
第２図ｄ図示のようになる。その結果は、必要に
応じて輪郭点データメモリ３または連結情報メモ
リ１５に書き出される。

処理判定回路１２は、輪郭点データメモリ３の
走査が終了するまで、輪郭点データのｙ座標値
が、先に読み出された輪郭点データのものに比べ
て変化したか否か、即ちラスタ走査が一段下がる
か否かを判定するものであり、ラスタ走査が一段
下がる場合には、後述する点列レジスタ１４内の
ｙ座標値を更新する。また、ラスタ走査が終了す
るとラスタ走査終了信号Ｓを出力する。

連結点判定回路１３は、点列レジスタ１４に格
納されたｘ座標値を参照して、輪郭点データメモ
リ３から読み出された輪郭点データが、先に処理
されたデータのどれかの点列に連結するかまたは
連結しないかを判定する回路である。

点列レジスタ１４は、点列端点データを記憶す
るレジスタであつて、既に検出されたデータ点列
の一対の端点のｘ座標値〔x_T1，x_T2〕とｙ座標値
とを記憶するものである。本実施例では、説明を
簡単化するために、１組の点列端点データを扱う
場合について説明するが、実際には点列端点デー
タの数に応じて各々座標情報を記憶するようにな
つている。連結情報メモリ１５は、例えば第２図
ｄに示したような輪郭点データに対して、第２図
ｅ図示の如く、隣接する各輪郭点相互の順方向ポ
インタおよび逆方向ポインタ情報を保持するワー
クメモリである。これらのポインタ情報は、各輪
郭点データに対応して持つようにされ、従つて、
発生する点列の数に関係しないので、連結情報メ
モリ１５としては、比較的小さなメモリ容量を持
つものでよい。

始点検出回路１６は、連結点判定回路１３によ
り、処理対象となつている輪郭点データが、点列
レジスタ１４および連結情報メモリ１５に記憶さ
れているデータ点列に連結しないと判定されたと
きに起動される回路であつて、このとき当該輪郭
点データの左端のｘ座標および右端のｘ座標（こ
れらのｘ座標は同じ値をとることもある）の組
を、一対の点列の端点として、点列レジスタ１４
に送り、新たな点列端点データとして設定するも
のである。

一方、点列延長回路１７は、連結点判定回路１
３により、処理対象となつている輪郭点データ
が、点列レジスタ１４および連結情報メモリ１５
に記憶されているデータ点列に連結すると判定さ
れたときに働く回路であり、これは、点列レジス
タ１４に記憶されている端点データに基づいて、
連結対象となつたデータ点列の端点と当該輪郭点
データとの間に相互に関連づけるポインタ情報
を、連結情報メモリ１５に設定する。そして、現
在処理対象となつている輪郭点データが、新たな
端点となるので、そのｘ座標値でもつて、もとの
端点についての点列レジスタ１４の内容を更新す
る。これによつて、データ点列が延長されること
になる。

閉ループ形成回路１８は、処理判定回路１２か
らのラスタ走査終了信号Ｓによつて作動する回路
であり、これは、連結情報メモリ１５に設定され
たデータ点列に関するポインタ情報に基づき、各
データ点列の端点を比較して各端点相互の連結関
係を判定し、連結され得る各点列同士を結合し
て、輪郭点データを閉ループ状に読み出すもので
ある。順方向ポインタまたは逆方向ポインタに従
つて、例えば反時計回りに抽出された輪郭点デー
タは、閉ループを形成する輪郭線データとして、
順次輪郭線データメモリ４に格納される。

次に本実施例に係る輪郭線抽出装置の作用動作
を第１図ないし第４図に従つて説明する。

今、物体の輪郭線を構成する閉ループ二値画像
が、第２図ａ図示のようなものであるとすると、
輪郭点データメモリ３には、第２図ｂに示すよう
に、画面上のラスタ走査順に輪郭点データ（x₂，
y₃）……（x₂，y₁）が格納される。

この輪郭点データメモリ３から、順次輪郭点デ
ータ（x₂，y₃）……が、データ抽出処理部１０に
よつて読み出されると、圧縮回路１１は水平方向
に連続したデータ、即ちｙ座標が等しく、ｘ座標
が１増加するデータをまとめる。その結果、読み
出しが終了した時点では、輪郭点データメモリ３
の内容は、第２図ｄ図示の如くになる。即ち、各
データにつき、その左端のｘ座標、右端のｘ座標
およびｙ座標を持つ。

この圧縮された最初の輪郭点データ（x₂，x₃，
y₃）が、処理判定回路１２に供給されると、処理
判定回路１２において、点列レジスタ１４のｙ座
標レジスタ中にy₃が設定される。次いで、この輪
郭点データ（x₂，x₃，y₃）が、連結点判定回路１
３に送られると、上記点列レジスタ１４のｘ座標
値が空きデータであることから、当該輪郭点デー
タ（x₂，x₃，y₃）が連結するデータ点列はないと
判定され、このデータは、始点検出回路１６に送
られる。始点検出回路１６では、輪郭点データ
（x₂，x₃，y₃）を、第４図図示のような一対の点
列Ｔ１，Ｔ２の始点として記憶する。そして、第
２図ｆ中に（ｉ）として示すように、点列レジス
タ１４の一対の格納部（x_T1，x_T2）に、点列端点
データとしてX₂，X₃の対を設定する。

次の輪郭点データ（x₁，x₁，y₂）が、処理判定
回路１２に送られると、処理判定回路１２におい
て、まずｙ座標値が変化していることが検出さ
れ、点列レジスタ１４中のｙ座標レジスタがy₂に
更新される。そして、そのデータは連結点判定回
路１３に送られ、連結点判定回路１３において、
点列レジスタ１４が参照されて、この輪郭点デー
タ（x₁，x₁，y₂）が、先に設定された格納部
（x_T1，x_T2）の端点データのいずれかに隣接する
か否かが判定される。そして、x₁はx_T1部の内容
x₂に隣接することから、点列延長回路１７が起動
される。

点列延長回路１７は、輪郭点データ（x₁，x₁，
y₂）に対し、第２図ｅ図示の如く、連結情報メモ
リ１５中の輪郭点データ（x₂，x₃，y₃）に対応す
るアドレスに、輪郭点データ（x₁，x₁，y₂）への
順方向ポインタを設定すると共に、連結情報メ
モリ１５中の輪郭点データ（x₁，x₁，y₂）に対応
するアドレスに、輪郭点データ（x₂，x₃，y₃）へ
の逆方向ポインタを設定する。また、点列レジ
スタ１４のx_T1部をx₁に更新する。

同様に、次の輪郭点データ（x₃，x₃，y₂）が処
理判定回路１２に送られると、処理判定回路１２
でｙ座標値のチエツクがなされるが、点列レジス
タ１４中のｙ座標値は変化しないので、そのまま
連結点判定回路１３にデータが引き渡される。連
結点判定回路１３では、輪郭点データ（x₃，x₃，
y₂）が、点列レジスタ１４に記憶されたもう一方
の点列Ｔ２に連結することが認知され、点列延長
回路１７が起動される。

点列延長回路１７は、輪郭点データ（x₃，x₃，
y₂）に対し、第２図ｅ図示の如く、連結情報メモ
リ１５中の輪郭点データ（x₂，x₃，y₃）に対応す
るアドレスに、輪郭点データ（x₃，x₃，y₂）への
順方向ポインタを設定すると共に、連結情報メ
モリ１５中の輪郭点データ（x₃，x₃，y₂）に対応
するアドレスに、輪郭点データ（x₂，x₃，y₃）へ
の逆方向ポインタを設定する。また、点列レジ
スタ１４のx_T2部をx₃に更新する。

さらに、次の輪郭点データ（x₁，x₂，y₂）が処
理判定回路１２に送られると、処理判定回路１２
でｙ座標値のチエツクがなされ、点列レジスタ１
４中のｙ座標値が変化しているので、点列レジス
タ１４にy₁が設定される。そして、連結点判定回
路１３にデータが引き渡され、連結点判定回路１
３では、輪郭点データ（x₁，x₂，y₂）が、点列レ
ジスタ１４に記憶された点列Ｔ１または点列Ｔ２
のいずれかに連結するか否かが判定される。この
場合、まず点列Ｔ１に連結することが認知され、
点列延長回路１７が起動される。

点列延長回路１７は、輪郭点データ（x₁，x₂，
y₂）に対し、第２図ｅ図示の如く、連結情報メモ
リ１５中の輪郭点データ（x₁，x₁，y₂）に対応す
るアドレスに、輪郭点データ（x₁，x₂，y₂）への
順方向ポインタを設定すると共に、連結情報メ
モリ１５中の輪郭点データ（x₁，x₁，y₂）に対応
するアドレスに、輪郭点データ（x₁，x₁，y₂）へ
の逆方向ポインタを設定する。また、点列レジ
スタ１４のx_T1部をx₂に更新する。これによつて、
点列レジスタ１４は第２図ｆの（）のようにな
る。また、連結情報メモリ１５は、第２図ｅ図示
のような情報を持つ。

次の段階で、処理判定回路１２によつて、デー
タの終了が検出され、処理判定回路１２からラス
タ走査終了信号Ｓが出力されて、閉ループ形成回
路１８に与えられる。閉ループ形成回路１８は、
連結情報メモリ１５中の順方向ポインタまたは逆
方向ポインタをたどり、端点となつている第番
目の（x₃，x₃，y₂）と第番目の（x₁，x₂，y₁）
とが連結関係にあることを検出する。そして、第
２図ｅ図示の圧縮後の輪郭点データ列と連結情報
メモリ１５の内容を参照し、輪郭点データ中の左
端のｘ座標と右端のｘ座標とが異なるものについ
ては、水平方向への復元を行いつつ、データ点列
Ｔ１に相当する部分を順方向に、データ点列T2
に相当する部分を逆方向にたどつて、その結果を
輪郭線データとして輪郭線データメモリ４に書き
込んでいく。輪郭線データメモリ４には、第２図
ｇ図示の如く、物体の輪郭を反時計回り方向に沿
つて抽出した輪郭線データが格納されることとな
る。

第３図は、上記処理の概要をフローチヤートの
形で示したものであり、閉ループ形成により処理
を終了する。上記各回路または処理部についての
個々の実施形態として、例えばマイクロプログラ
ミングその他の手段を採用することができ、上記
説明により、当業者であればインプリメントでき
ることは明らかであり、具体的構成についての設
計変更は適宜可能である。

なお、上記実施例においては、物体の輪郭が１
つ、即ち閉ループが１つの場合について説明した
が、物体の輪郭が複雑な場合あるいは物体が複数
ある場合についても、この発明を適用すれば、処
理途中の輪郭点データについて始点検出回路１６
が働くことになるので、その分、データ点列の数
が増加するだけで、各データ点列を適宜結合させ
ることにより、同様に輪郭線データを抽出するこ
とができる。

〔発明の効果〕

以上説明した如く、本発明によれば、輪郭点デ
ータ群を格納するメモリを実質的に１回走査する
だけで、輪郭線データを抽出することが可能にな
り、輪郭線データ抽出に必要な処理時間を大幅に
短縮することできる。また、途中の中間的なデー
タ点列に関する情報を、ポインタ情報によつて管
理するので、処理が容易になり、必要とするメモ
リ量も少なくてよいという効果がある。なお、水
平に連続した輪郭点データをまとめて圧縮するこ
とが可能であり、この圧縮を採用すれば、さらに
メモリ量を節減可能とすることができる。

【図面の簡単な説明】

第１図は本発明の一実施例構成、第２図は第１
図図示実施例の具体的な処理態様を説明するため
の図、第３図は第１図図示実施例による処理概要
を説明するためのフローチヤート、第４図は始点
と連結点との関係を説明するための図、第５図お
よび第６図は従来方式による輪郭線抽出を説明す
るための図を示す。 図中、３は輪郭点データメモリ、４は輪郭線デ
ータメモリ、１０はデータ抽出処理部、１１は圧
縮回路、１２は処理判定回路、１３は連結点判定
回路、１４は点列レジスタ、１５は連結情報メモ
リ、１６は始点検出回路、１７は点列延長回路、
１８は閉ループ形成回路、Ｔ１，Ｔ２はデータ点
列を表す。

Claims (1)

1. 【特許請求の範囲】 １ 物体の輪郭を構成する閉ループ二値画像に対
   して画面走査順に得られる輪郭点データ群を物体
   の輪郭に沿う輪郭線データとして抽出する輪郭線
   抽出装置であつて、上記輪郭点データ群を格納す
   る輪郭点データメモリと、処理される各データ点
   列の端点に対応する各点列端点データを記憶する
   点列端点記憶手段と、上記各輪郭点データ毎にそ
   の連結する輪郭点データを指すポインタ情報を記
   憶する連結情報メモリと、上記輪郭点データメモ
   リから読み出した輪郭点データが上記点列端点記
   憶手段に記憶されている点列端点データと隣接す
   るか否かを判定する手段を有するデータ抽出処理
   手段と、該データ抽出処理手段により上記輪郭点
   データが上記点列端点データに連結しないと判定
   されたときに当該輪郭点データを新しいデータ点
   列の始点として検出しこれを上記点列端点記憶手
   段に格納する始点検出手段と、上記データ抽出処
   理手段により上記輪郭点データが先に検出された
   点列端点データに連結すると判定されたときに当
   該輪郭点データを延長点として検出しこれを上記
   点列端点記憶手段に格納すると共にその連結する
   輪郭点データを指すポインタ情報を上記連結情報
   メモリに格納する延長点検出手段と、上記連結情
   報メモリに格納された情報に基づき各点列データ
   の端点を比較して各端点相互の連結関係を判定し
   連結され得る各点列同士を結合して閉ループ状の
   輪郭線データを抽出する閉ループ形成手段と、該
   閉ループ形成手段からの輪郭線データが格納され
   る輪郭線データメモリとを備えたことを特徴とす
   る輪郭線抽出装置。 ２ 上記データ抽出処理手段は、上記輪郭点デー
   タメモリ内の走査方向に連続した輪郭点データを
   まとめて１つの輪郭点データとして出力するデー
   タ圧縮手段を有することを特徴とする特許請求の
   範囲第１項記載の輪郭線抽出装置。