JPH0146912B2 - - Google Patents
Info
- Publication number
- JPH0146912B2 JPH0146912B2 JP58225622A JP22562283A JPH0146912B2 JP H0146912 B2 JPH0146912 B2 JP H0146912B2 JP 58225622 A JP58225622 A JP 58225622A JP 22562283 A JP22562283 A JP 22562283A JP H0146912 B2 JPH0146912 B2 JP H0146912B2
- Authority
- JP
- Japan
- Prior art keywords
- point
- data
- contour
- sequence
- point sequence
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
Landscapes
- Image Analysis (AREA)
Description
【発明の詳細な説明】
(1) 発明の技術分野
この発明は、物体の輪郭を構成する二値画像に
対して画面走査順に得られる輪郭点データ群を、
物体の輪郭に沿う輪郭線データとして抽出する輪
郭線抽出方法及びその装置に関する。
対して画面走査順に得られる輪郭点データ群を、
物体の輪郭に沿う輪郭線データとして抽出する輪
郭線抽出方法及びその装置に関する。
(2) 技術の背景
一般に、物体の輪郭を構成する二値画像から物
体の形状を抽出したり、各種パラメータ、例えば
物体の重心位置、物体の輪郭の周長等を求めるに
は、計算のやり易さ等の観点からして物体の輪郭
に沿つて配列される輪郭線データを抽出すること
が必要になる。
体の形状を抽出したり、各種パラメータ、例えば
物体の重心位置、物体の輪郭の周長等を求めるに
は、計算のやり易さ等の観点からして物体の輪郭
に沿つて配列される輪郭線データを抽出すること
が必要になる。
(3) 従来技術とその問題点
従来におけるこの種の輪郭線抽出方法として
は、例えば第１図に示すように、物体の輪郭を構
成する二値画像Ｇが表示される場面１上にＸ−Ｙ
座標系を予め設定し、上記画面１を走査２するこ
とにより上記二値画像Ｇの輪郭点データ群（X1、
Y1）（X2、Y2）…（Xn、Yn）を画面走査順に
得て、これらを輪郭点データメモリ３に格納し、
しかる後上記輪郭点データ群に輪郭線抽出処理を
施し、上記輪郭点データ群を物体の輪郭の例えば
反時計回り方向（図中ｍで示す）に沿う輪郭線デ
ータ（XA1、YA1）（XA2、YA2）…（XAo、YAo）
として抽出し、輪郭線データメモリ４に格納する
ようにしたものがある。この方法において、上記
輪郭線抽出処理としては、例えば第２図に示すよ
うに、輪郭点データ中に始点Ｐ（Xi、Yi）を定
め、この始点に連結可能な８つの囲繞位置Ａ乃至
Ｇについて上記輪郭点データメモリ３を検索し
て、始点Ｐの次に連結される次輪郭点を抽出した
後、当該抽出された輪郭点の次に連結される次輪
郭点を上述したのと同様にして抽出し、以後この
手順を繰返すことにより、抽出した輪郭点を輪郭
線データとして輪郭線データメモリに順次格納す
るようにしたものである。
は、例えば第１図に示すように、物体の輪郭を構
成する二値画像Ｇが表示される場面１上にＸ−Ｙ
座標系を予め設定し、上記画面１を走査２するこ
とにより上記二値画像Ｇの輪郭点データ群（X1、
Y1）（X2、Y2）…（Xn、Yn）を画面走査順に
得て、これらを輪郭点データメモリ３に格納し、
しかる後上記輪郭点データ群に輪郭線抽出処理を
施し、上記輪郭点データ群を物体の輪郭の例えば
反時計回り方向（図中ｍで示す）に沿う輪郭線デ
ータ（XA1、YA1）（XA2、YA2）…（XAo、YAo）
として抽出し、輪郭線データメモリ４に格納する
ようにしたものがある。この方法において、上記
輪郭線抽出処理としては、例えば第２図に示すよ
うに、輪郭点データ中に始点Ｐ（Xi、Yi）を定
め、この始点に連結可能な８つの囲繞位置Ａ乃至
Ｇについて上記輪郭点データメモリ３を検索し
て、始点Ｐの次に連結される次輪郭点を抽出した
後、当該抽出された輪郭点の次に連結される次輪
郭点を上述したのと同様にして抽出し、以後この
手順を繰返すことにより、抽出した輪郭点を輪郭
線データとして輪郭線データメモリに順次格納す
るようにしたものである。
然しながら、このような従来の輪郭線抽出方法
にあつては、ある一つの輪郭点の次に連結される
次輪郭点を抽出するために、一つの輪郭点を囲繞
する８ケ所すべてのデータ値について輪郭点デー
タメモリ３を検索しなければならないことから、
最終的な輪郭線データを得るまでにおいて必要な
輪郭点データメモリ３の検索回数が膨大なものと
なつてしまい、その分、輪郭線抽出のための処理
時間が大幅にかかるという問題がある。
にあつては、ある一つの輪郭点の次に連結される
次輪郭点を抽出するために、一つの輪郭点を囲繞
する８ケ所すべてのデータ値について輪郭点デー
タメモリ３を検索しなければならないことから、
最終的な輪郭線データを得るまでにおいて必要な
輪郭点データメモリ３の検索回数が膨大なものと
なつてしまい、その分、輪郭線抽出のための処理
時間が大幅にかかるという問題がある。
(4) 発明の目的
この発明は以上の観点に立つて為されたもので
あつて、その目的とするところは、輪郭線抽出に
伴う処理時間の短縮化を企図した輪郭線抽出方法
及びその装置を提供することにある。
あつて、その目的とするところは、輪郭線抽出に
伴う処理時間の短縮化を企図した輪郭線抽出方法
及びその装置を提供することにある。
(5) 発明の構成
そして、この発明に係る輪郭線抽出方法の基本
的構成は、物体の輪郭を構成する閉ループ二値画
像に対して画面走査順に得られる輪郭点データ群
を、物体の輪郭に沿う輪郭点データとして抽出す
るに際し、上記輪郭点データ群を輪郭点データメ
モリに予め格納し、この輪郭点データメモリから
最初に読み出される輪郭点データを一対のデータ
点列における一方の始点とし、この始点データに
連結可能な２点のうちより上かつ右の輪郭点デー
タを上記一対のデータ点列の他方の始点とすると
共に、一対のデータ点列の始点が抽出された段階
において上記いずれかのデータ点列の端点に連結
される輪郭点データを該当するデータ点列の延長
点として検出する一方、上記輪郭点データメモリ
から順次読出される任意の輪郭点データが先に読
出された輪郭点データによるデータ点列の端点に
連結しないときには上記輪郭点データを新たな一
対のデータ点列における一方の始点として、この
新たなデータ点列における他方の始点及びその延
長点を前記したのと同様に順次検出することによ
り、輪郭点データメモリから順次読出された輪郭
点データ群を複数のデータ点列として点列バツフ
アに一旦格納した後、各データ点列の端点データ
を比較して各端点相互の連結関係を判定し、連結
され得るデータ点列同士を結合させて輪郭線デー
タメモリに格納するようにしたことを特徴する輪
郭線抽出方法にある。
的構成は、物体の輪郭を構成する閉ループ二値画
像に対して画面走査順に得られる輪郭点データ群
を、物体の輪郭に沿う輪郭点データとして抽出す
るに際し、上記輪郭点データ群を輪郭点データメ
モリに予め格納し、この輪郭点データメモリから
最初に読み出される輪郭点データを一対のデータ
点列における一方の始点とし、この始点データに
連結可能な２点のうちより上かつ右の輪郭点デー
タを上記一対のデータ点列の他方の始点とすると
共に、一対のデータ点列の始点が抽出された段階
において上記いずれかのデータ点列の端点に連結
される輪郭点データを該当するデータ点列の延長
点として検出する一方、上記輪郭点データメモリ
から順次読出される任意の輪郭点データが先に読
出された輪郭点データによるデータ点列の端点に
連結しないときには上記輪郭点データを新たな一
対のデータ点列における一方の始点として、この
新たなデータ点列における他方の始点及びその延
長点を前記したのと同様に順次検出することによ
り、輪郭点データメモリから順次読出された輪郭
点データ群を複数のデータ点列として点列バツフ
アに一旦格納した後、各データ点列の端点データ
を比較して各端点相互の連結関係を判定し、連結
され得るデータ点列同士を結合させて輪郭線デー
タメモリに格納するようにしたことを特徴する輪
郭線抽出方法にある。
そしてまた、上記方法を実施するための装置の
基本的構成は、物体の輪郭を構成する閉ループ二
値画像に対して画面走査順に得られる輪郭点デー
タ群を、物体の輪郭に沿う輪郭線データとして抽
出する輪郭線抽出装置であつて、上記輪郭点デー
タ群を格納する輪郭点データメモリと、この輪郭
点データメモリから順次読出される輪郭点データ
を順次所定のデータ点列として格納する点列バツ
フアと、この点列バツフア内の各データ点列の端
点に対応する各点列端点データを順次格納する点
列端点レジスタと、上記輪郭点データメモリから
順次読出される輪郭点データが上記点列レジスタ
内の点列端点データと隣接するか否かを判定する
判定手段と、この判定手段により上記輪郭点デー
タが点列端点データに連結しないと判定されたと
きに、上記点列バツフアに一対のデータ点列を格
納するスペースを設定すると共に、一対のデータ
点列における一方の始点として上記輪郭点データ
を検出し、これを点列バツフア及び点列端点バツ
フアに送る始点検出手段と、上記判定手段により
上記輪郭点データが所定の点列端点データに連結
すると判定されたときに点列バツフアに格納すべ
き上記一対のデータ点列における他方の始点若し
くは該当するデータ点列の延長点として上記輪郭
点データを検出し、これを点列バツフア及び点列
端点レジスタに送る延長点検出手段と、すべての
輪郭点データが点列バツフア内に格納されたとき
に点列バツフア内の各データ点列の端点を比較し
て各端点相互の連結関係を判定し、連結され得る
各点列同士を結合して閉ループ状の輪郭線データ
を抽出する閉ループ形成手段と、この閉ループ形
成手段からの輪郭線データを格納する輪郭線デー
タメモリとを備えたものである。
基本的構成は、物体の輪郭を構成する閉ループ二
値画像に対して画面走査順に得られる輪郭点デー
タ群を、物体の輪郭に沿う輪郭線データとして抽
出する輪郭線抽出装置であつて、上記輪郭点デー
タ群を格納する輪郭点データメモリと、この輪郭
点データメモリから順次読出される輪郭点データ
を順次所定のデータ点列として格納する点列バツ
フアと、この点列バツフア内の各データ点列の端
点に対応する各点列端点データを順次格納する点
列端点レジスタと、上記輪郭点データメモリから
順次読出される輪郭点データが上記点列レジスタ
内の点列端点データと隣接するか否かを判定する
判定手段と、この判定手段により上記輪郭点デー
タが点列端点データに連結しないと判定されたと
きに、上記点列バツフアに一対のデータ点列を格
納するスペースを設定すると共に、一対のデータ
点列における一方の始点として上記輪郭点データ
を検出し、これを点列バツフア及び点列端点バツ
フアに送る始点検出手段と、上記判定手段により
上記輪郭点データが所定の点列端点データに連結
すると判定されたときに点列バツフアに格納すべ
き上記一対のデータ点列における他方の始点若し
くは該当するデータ点列の延長点として上記輪郭
点データを検出し、これを点列バツフア及び点列
端点レジスタに送る延長点検出手段と、すべての
輪郭点データが点列バツフア内に格納されたとき
に点列バツフア内の各データ点列の端点を比較し
て各端点相互の連結関係を判定し、連結され得る
各点列同士を結合して閉ループ状の輪郭線データ
を抽出する閉ループ形成手段と、この閉ループ形
成手段からの輪郭線データを格納する輪郭線デー
タメモリとを備えたものである。
(6) 発明の実施例
以下、添付図面に示す実施例に基づいてこの発
明に係る輪郭線抽出方法及びその装置を詳細に説
明する。
明に係る輪郭線抽出方法及びその装置を詳細に説
明する。
第３図はこの発明に係る輪郭線抽出装置の一実
施例を示すブロツク図である。
施例を示すブロツク図である。
同図において、３は、例えば第５図ａに示すよ
うに、物体の輪郭を構成する閉ループ二値画像に
対して画面走査順に得られる輪郭点データ群を
（第５図ｂ参照）を格納する輪郭点データメモリ、
４は、例えば第５図ｂの輪郭点データ群を物体の
輪郭に沿う輪郭線データ（第５図ｆ参照）として
格納する輪郭線データメモリ、１０は、例えば第
５図ｂ及びｄに示すように、上記輪郭点データメ
モリ３から順次読出される輪郭線データ群を二つ
のデータ点列T1、T2として格納する点列バツフ
ア、１１は、例えば第５図ｄ及びｅに示すよう
に、上記点列バツフア１０内の各データ点列T1、
T2の端点に対応する各点列端点データを順次格
納する点列端点レジスタであり、この点列端点デ
ータは、二つのＸ座標（XT1、XT2）と一つのＹ
座標値とからなつている。
うに、物体の輪郭を構成する閉ループ二値画像に
対して画面走査順に得られる輪郭点データ群を
（第５図ｂ参照）を格納する輪郭点データメモリ、
４は、例えば第５図ｂの輪郭点データ群を物体の
輪郭に沿う輪郭線データ（第５図ｆ参照）として
格納する輪郭線データメモリ、１０は、例えば第
５図ｂ及びｄに示すように、上記輪郭点データメ
モリ３から順次読出される輪郭線データ群を二つ
のデータ点列T1、T2として格納する点列バツフ
ア、１１は、例えば第５図ｄ及びｅに示すよう
に、上記点列バツフア１０内の各データ点列T1、
T2の端点に対応する各点列端点データを順次格
納する点列端点レジスタであり、この点列端点デ
ータは、二つのＸ座標（XT1、XT2）と一つのＹ
座標値とからなつている。
また、この実施例において、１２は、輪郭点デ
ータメモリ３の走査が終了するまで輪郭点データ
のＹ座標値が先に読出された輪郭点データのもの
に比べて変化したか否か、即ちラスタ走査が一段
下がるか否かを判定する処理判定回路であり、こ
れは、ラスタ走査が一段下がる場合には上記点列
端点レジスタ１１内のＹ座標値を更新するように
なつており、ラスタ走査が終了すると、ラスタ走
査終了信号Ｓを出力するようになつている。
ータメモリ３の走査が終了するまで輪郭点データ
のＹ座標値が先に読出された輪郭点データのもの
に比べて変化したか否か、即ちラスタ走査が一段
下がるか否かを判定する処理判定回路であり、こ
れは、ラスタ走査が一段下がる場合には上記点列
端点レジスタ１１内のＹ座標値を更新するように
なつており、ラスタ走査が終了すると、ラスタ走
査終了信号Ｓを出力するようになつている。
また、１３は点列端点レジスタ１１のＸ座標値
を参照して、輪郭点データメモリ３から読出され
た輪郭点データが点列バツフア１０内のどのデー
タ点列に連結するか否かを判定する連結点判定回
路である。第６図に、最初の始点に隣接する場所
に輪郭点の存在する仕方の組合せを示す。図にお
いて、ハツチング部分が、一対の点列のうち、他
方の始点となる点である。また４，５，６におい
ては２番目の輪郭点が他方の始点となる。１４は
連結点判定回路１３により上記輪郭点データが点
列バツフア１０内のデータ点列に連結しないと判
定されたときに働く始点検出回路であり、これ
は、上記点列バツフア１０内に新たに一対のデー
タ点列を格納するスペースを設定すると共に、上
記輪郭データを一対のデータ点列の一方の始点と
して検出し、これを点列バツフア１０に送ると共
に、新たな初期点列端点データとして点列端点レ
ジスタ１１に送るようになつている。一方、１５
は上記連結点判定回路１３により上記輪郭点デー
タが点列バツフア１０内のデータ点列に連結する
と判定されたときに働く延長点検出回路であり、
これは、点列バツフア１０内の上記一対のデータ
点列の他方の始点が空データである場合には上記
輪郭点データを上記一対のデータ点列の他方の始
点として検出すると共に、上記一対のデータ点列
の始点が設定されている場合には上記輪郭点デー
タを該当するデータ点列の延長点として検出し、
これを点列バツフア１０に送ると共に、更新する
点列端点データとして点列端点レジスタ１１に送
るようになつている。
を参照して、輪郭点データメモリ３から読出され
た輪郭点データが点列バツフア１０内のどのデー
タ点列に連結するか否かを判定する連結点判定回
路である。第６図に、最初の始点に隣接する場所
に輪郭点の存在する仕方の組合せを示す。図にお
いて、ハツチング部分が、一対の点列のうち、他
方の始点となる点である。また４，５，６におい
ては２番目の輪郭点が他方の始点となる。１４は
連結点判定回路１３により上記輪郭点データが点
列バツフア１０内のデータ点列に連結しないと判
定されたときに働く始点検出回路であり、これ
は、上記点列バツフア１０内に新たに一対のデー
タ点列を格納するスペースを設定すると共に、上
記輪郭データを一対のデータ点列の一方の始点と
して検出し、これを点列バツフア１０に送ると共
に、新たな初期点列端点データとして点列端点レ
ジスタ１１に送るようになつている。一方、１５
は上記連結点判定回路１３により上記輪郭点デー
タが点列バツフア１０内のデータ点列に連結する
と判定されたときに働く延長点検出回路であり、
これは、点列バツフア１０内の上記一対のデータ
点列の他方の始点が空データである場合には上記
輪郭点データを上記一対のデータ点列の他方の始
点として検出すると共に、上記一対のデータ点列
の始点が設定されている場合には上記輪郭点デー
タを該当するデータ点列の延長点として検出し、
これを点列バツフア１０に送ると共に、更新する
点列端点データとして点列端点レジスタ１１に送
るようになつている。
更に、符号１６は処理判定回路１２からのラス
タ走査終了信号Ｓによつて作動する閉ループ形成
回路であり、これは、点列バツフア１０内の各デ
ータ点列の端点を比較して各端点相互の連結関係
を判定し、連結され得る各点列同士を結合して点
列バツフア１０内の各点列を閉ループ状に読出す
ものである。
タ走査終了信号Ｓによつて作動する閉ループ形成
回路であり、これは、点列バツフア１０内の各デ
ータ点列の端点を比較して各端点相互の連結関係
を判定し、連結され得る各点列同士を結合して点
列バツフア１０内の各点列を閉ループ状に読出す
ものである。
次に、この実施例に係る輪郭点抽出装置の作用
を第３乃至第５図を用いて説明する。
を第３乃至第５図を用いて説明する。
今、物体の輪郭を構成する閉ループ二値画像が
第５図ａで示すようなものであるとすると、輪郭
点データメモリ３には、第５図ｂで示すように、
画面上のラスタ走査順に輪郭点データ（X2、
Y3）…（X2、Y1）が格納される。この輪郭点デ
ータメモリ３から最初の輪郭点データ（X2、
Y3）が読出されると、先ず、処理判定回路１２
において、点列端点レジスタ１１の空データであ
るＹ座標値がY3に設定され、次いで、上記輪郭
点データ（X2、Y2）が連結点判定回路１３に送
られると、上記点列端点レジスタ１３のＸ座標値
が空データであることから、上記輪郭点データ
（X2、Y3）が連結するデータ点列はないと判定
され、上記輪郭点データ（X2、Y3）は始点検出
回路１４に送られる。すると、この始点検出回路
１４は、第５図ｄに示すように、点列バツフア１
０内に一対のデータ点列T1、T2を格納するスペ
ースを設定し、上記輪郭点データ（X2、Y3）を
一方のデータ点列T1の始点として検出し、これ
を点列バツフア１０に送ると共に、上記輪郭点デ
ータ（X2、Y3）のＹ座標値を初期点列端点デー
タとして点列端点レジスタ１１の一対の格納部
（XT1、XT2）に送る。この段階において、点列バ
ツフア１０のデータ点列T1は上記輪郭データ
（X2、Y3）を始点として格納すると共に、デー
タ点列T2の始点は空データであり、点列端点レ
ジスタ１１の内容は、第５図ｅ，１に示すように
なつている。
第５図ａで示すようなものであるとすると、輪郭
点データメモリ３には、第５図ｂで示すように、
画面上のラスタ走査順に輪郭点データ（X2、
Y3）…（X2、Y1）が格納される。この輪郭点デ
ータメモリ３から最初の輪郭点データ（X2、
Y3）が読出されると、先ず、処理判定回路１２
において、点列端点レジスタ１１の空データであ
るＹ座標値がY3に設定され、次いで、上記輪郭
点データ（X2、Y2）が連結点判定回路１３に送
られると、上記点列端点レジスタ１３のＸ座標値
が空データであることから、上記輪郭点データ
（X2、Y3）が連結するデータ点列はないと判定
され、上記輪郭点データ（X2、Y3）は始点検出
回路１４に送られる。すると、この始点検出回路
１４は、第５図ｄに示すように、点列バツフア１
０内に一対のデータ点列T1、T2を格納するスペ
ースを設定し、上記輪郭点データ（X2、Y3）を
一方のデータ点列T1の始点として検出し、これ
を点列バツフア１０に送ると共に、上記輪郭点デ
ータ（X2、Y3）のＹ座標値を初期点列端点デー
タとして点列端点レジスタ１１の一対の格納部
（XT1、XT2）に送る。この段階において、点列バ
ツフア１０のデータ点列T1は上記輪郭データ
（X2、Y3）を始点として格納すると共に、デー
タ点列T2の始点は空データであり、点列端点レ
ジスタ１１の内容は、第５図ｅ，１に示すように
なつている。
次に、第５図ｂに示すように、輪郭点データメ
モリ３から次の輪郭点データ（X3、Y3）が読出
されると、処理判定回路１２において該輪郭点デ
ータ（X3、Y3）のＹ座標値が点列端点レジスタ
１１のＹ座標値と比較されるが、両者が等しいこ
とから点列端点レジスタ１１は更新されない。そ
して、上記輪郭点データ（X3、Y3）が連結点判
定回路１３に送られると、この輪郭点データ
（X3、Y3）のＸ座標値が点列端点レジスタ１１
の一対のＸ座標と比較され、連結点判定回路１３
は、この輪郭点データ（X3、Y3）が点列端点
（XT1、XT2）＝（X2、Y2）のいずれかにも連結す
ることを判定し、上記輪郭点データ（X3、Y3）
は延長点検出回路１５に送られる。すると、この
延長点検出回路１５は、上記輪郭点データ（X3、
Y3）を他方のデータ点列T2の始点して検出し、
これを点列バツフア１０に送ると共に、上記輪郭
点データ（X3、Y3）のＹ座標値を点列端点デー
タとして点列端点レジスタ１１の一方の格納部
XT2に格納する。この段階において、点列バツフ
ア１０の各データ点列T1、T2は夫々の輪郭点デ
ータを始点として格納しており、点列端点レジス
タ１１の内容は第５図２に示すようになつてい
る。
モリ３から次の輪郭点データ（X3、Y3）が読出
されると、処理判定回路１２において該輪郭点デ
ータ（X3、Y3）のＹ座標値が点列端点レジスタ
１１のＹ座標値と比較されるが、両者が等しいこ
とから点列端点レジスタ１１は更新されない。そ
して、上記輪郭点データ（X3、Y3）が連結点判
定回路１３に送られると、この輪郭点データ
（X3、Y3）のＸ座標値が点列端点レジスタ１１
の一対のＸ座標と比較され、連結点判定回路１３
は、この輪郭点データ（X3、Y3）が点列端点
（XT1、XT2）＝（X2、Y2）のいずれかにも連結す
ることを判定し、上記輪郭点データ（X3、Y3）
は延長点検出回路１５に送られる。すると、この
延長点検出回路１５は、上記輪郭点データ（X3、
Y3）を他方のデータ点列T2の始点して検出し、
これを点列バツフア１０に送ると共に、上記輪郭
点データ（X3、Y3）のＹ座標値を点列端点デー
タとして点列端点レジスタ１１の一方の格納部
XT2に格納する。この段階において、点列バツフ
ア１０の各データ点列T1、T2は夫々の輪郭点デ
ータを始点として格納しており、点列端点レジス
タ１１の内容は第５図２に示すようになつてい
る。
更に、輪郭点データメモリ３から次の輪郭点デ
ータ（X1、Y2）が読出されると、処理判定回路
１２は、上記輪郭点データ（X1、Y2）のＹ座標
値が点列端点レジスタ１１のＹ座標値と異なるこ
とから、点列端点レジスタ１１のＹ座標値をY2
に更新する。そして、上記輪郭データ（X1、
Y2）が連結点判定回路１３に送られると、該連
結点判定回路１３は上記輪郭点データ（X1、
Y2）が点列端点データXT1＝X2に連結すること
を判定し、上記輪郭点データ（X1、Y2）を延長
検出回路１５に送る。すると、この延長検出回路
１５は、上記輪郭点データ（X3、Y3）を一方の
データ点列T1の延長点として検出し、これを点
列バツフア１０に送ると共に、上記輪郭点データ
（X1、Y2）のＹ座標値を点列端点データとして
点列端点レジスタ１１の一方の格納部XT1に格納
する。以後、上述したのと同様に処理され、輪郭
点データ（X3、Y2）は、上記データ点列T2に連
結され、この段階で点列端点レジスタ１１の内容
は第５図ｅ，３に示すようになつている。そし
て、輪郭点データ（X1、Y1）が輪郭データメモ
リ３から読出されると、点列端点レジスタ１１の
Ｙ座標値が再び更新されると共に、上記輪郭点デ
ータ（X1、Y1）はデータ点列T1に連結され、更
に、最後に読出される輪郭点データ（X2、Y1）
も上記データ点列T1に連結される。この段階に
おいて、輪郭点データメモリ３の走査が終了し、
点列バツフア１０には第５図ｃ及び第５図ｄに示
すような配列をもつて各輪郭点データが格納され
る。尚、点列端点レジスタ１１の内容吏は第５図
ｅ，４で示すようになつている。
ータ（X1、Y2）が読出されると、処理判定回路
１２は、上記輪郭点データ（X1、Y2）のＹ座標
値が点列端点レジスタ１１のＹ座標値と異なるこ
とから、点列端点レジスタ１１のＹ座標値をY2
に更新する。そして、上記輪郭データ（X1、
Y2）が連結点判定回路１３に送られると、該連
結点判定回路１３は上記輪郭点データ（X1、
Y2）が点列端点データXT1＝X2に連結すること
を判定し、上記輪郭点データ（X1、Y2）を延長
検出回路１５に送る。すると、この延長検出回路
１５は、上記輪郭点データ（X3、Y3）を一方の
データ点列T1の延長点として検出し、これを点
列バツフア１０に送ると共に、上記輪郭点データ
（X1、Y2）のＹ座標値を点列端点データとして
点列端点レジスタ１１の一方の格納部XT1に格納
する。以後、上述したのと同様に処理され、輪郭
点データ（X3、Y2）は、上記データ点列T2に連
結され、この段階で点列端点レジスタ１１の内容
は第５図ｅ，３に示すようになつている。そし
て、輪郭点データ（X1、Y1）が輪郭データメモ
リ３から読出されると、点列端点レジスタ１１の
Ｙ座標値が再び更新されると共に、上記輪郭点デ
ータ（X1、Y1）はデータ点列T1に連結され、更
に、最後に読出される輪郭点データ（X2、Y1）
も上記データ点列T1に連結される。この段階に
おいて、輪郭点データメモリ３の走査が終了し、
点列バツフア１０には第５図ｃ及び第５図ｄに示
すような配列をもつて各輪郭点データが格納され
る。尚、点列端点レジスタ１１の内容吏は第５図
ｅ，４で示すようになつている。
この場合において、処理判定回路１２からラス
タ走査終了信号Ｓが閉ループ形成回路１６に与え
られ、この閉ループ形成回路１６は、データ点列
T1、T2の端点（X2、Y1）（X3、Y2）が連結関
係にあると判定し、データ点列T1を順方向にデ
ータ点列T2を逆方向に走査して各データ点列の
データを読出す。この読出データは、第５図ａに
示す物体の輪郭を反時計回り方向に沿う輪郭点デ
ータとして抽出されている。
タ走査終了信号Ｓが閉ループ形成回路１６に与え
られ、この閉ループ形成回路１６は、データ点列
T1、T2の端点（X2、Y1）（X3、Y2）が連結関
係にあると判定し、データ点列T1を順方向にデ
ータ点列T2を逆方向に走査して各データ点列の
データを読出す。この読出データは、第５図ａに
示す物体の輪郭を反時計回り方向に沿う輪郭点デ
ータとして抽出されている。
そして、この輪郭線データは、第５図ｆで示す
ように輪郭線データメモリ４に格納される。
ように輪郭線データメモリ４に格納される。
尚、上記実施例にあつては、データ点列が二つ
になる場合について説明しているが、物体の輪郭
が複雑なものについてもこの発明を適用すれば、
処理が途中の輪郭点データについて始点検出回路
１４が働くことになるので、その分、データ点列
の数が増加するだけで各データ点列を適宜結合さ
せることによつて輪郭線データを抽出できる。ま
た、上記実施例に係る装置の具体的構成について
は適宜設計変更して差支えない。
になる場合について説明しているが、物体の輪郭
が複雑なものについてもこの発明を適用すれば、
処理が途中の輪郭点データについて始点検出回路
１４が働くことになるので、その分、データ点列
の数が増加するだけで各データ点列を適宜結合さ
せることによつて輪郭線データを抽出できる。ま
た、上記実施例に係る装置の具体的構成について
は適宜設計変更して差支えない。
(7) 発明の効果
以上説明したきたように、この発明に係る輪郭
線抽出方法及びその装置によれば、輪郭点データ
群を格納するメモリを一回走査して、中間的なデ
ータ点列を点列バツフアに格納し、各データ点列
を結合させるように上記点列バツフアを一回だけ
操作することにより、輪郭線データを抽出するこ
とができる。このため、輪郭線データ抽出に伴う
処理時間を高速に行なうことが可能になる。
線抽出方法及びその装置によれば、輪郭点データ
群を格納するメモリを一回走査して、中間的なデ
ータ点列を点列バツフアに格納し、各データ点列
を結合させるように上記点列バツフアを一回だけ
操作することにより、輪郭線データを抽出するこ
とができる。このため、輪郭線データ抽出に伴う
処理時間を高速に行なうことが可能になる。
第１図は従来における輪郭線抽出方法の一例を
示す説明図、第２図は輪郭線抽出処理に当つて用
いられる原理説明図、第３図はこの発明に係る輪
郭線抽出装置の一実施例を示すブロツク図、第４
図は第３図に示す輪郭線抽出装置の基本作動を示
すフローチヤート、第５図は第３図に示す輪郭点
抽出装置の具体的作動状態を示し、第５図ａは物
体の輪郭を構成する二値画像の一例を、第５図ｂ
は輪郭点データメモリの内容を、第５図ｃは点列
バツフアへのデータの格納順序を、第５図ｄは点
列バツフアの内容を、第５図ｅは点列端点レジス
タの内容を、第５図ｆは輪郭線データメモリの内
容を夫々示す説明図、第６図は最初の始点に隣接
する場所に輪郭点の存在する仕方の組合せを示す
図である。 ３……輪郭点データメモリ、４……輪郭線デー
タメモリ、１０……点列バツフア、１１……点列
端点レジスタ、１２……処理判定回路、１３……
連結点判定回路（判定手段）、１４……始点検出
回路（手段）、１５……延長点検出回路、１６…
…閉ループ形成回路。
示す説明図、第２図は輪郭線抽出処理に当つて用
いられる原理説明図、第３図はこの発明に係る輪
郭線抽出装置の一実施例を示すブロツク図、第４
図は第３図に示す輪郭線抽出装置の基本作動を示
すフローチヤート、第５図は第３図に示す輪郭点
抽出装置の具体的作動状態を示し、第５図ａは物
体の輪郭を構成する二値画像の一例を、第５図ｂ
は輪郭点データメモリの内容を、第５図ｃは点列
バツフアへのデータの格納順序を、第５図ｄは点
列バツフアの内容を、第５図ｅは点列端点レジス
タの内容を、第５図ｆは輪郭線データメモリの内
容を夫々示す説明図、第６図は最初の始点に隣接
する場所に輪郭点の存在する仕方の組合せを示す
図である。 ３……輪郭点データメモリ、４……輪郭線デー
タメモリ、１０……点列バツフア、１１……点列
端点レジスタ、１２……処理判定回路、１３……
連結点判定回路（判定手段）、１４……始点検出
回路（手段）、１５……延長点検出回路、１６…
…閉ループ形成回路。
Claims (1)
- 【特許請求の範囲】 １ 物体の輪郭を構成する閉ループ二値画像に対
して画面走査順に得られる輪郭点データ群を、物
体の輪郭に沿う輪郭点データとして抽出するに際
し、上記輪郭点データ群を輪郭点データメモリに
予め格納し、この輪郭点データメモリから最初に
読み出される輪郭点データを一対のデータ点列に
おける一方の始点とし、この始点データに連結可
能な２点のうちより上かつ右の輪郭点データを上
記一対のデータ点列の他方の始点とすると共に、
一対のデータ点列の始点が抽出された段階におい
て上記いずれかのデータ点列の端点に連結される
輪郭点データを該当するデータ点列の延長点とし
て検出する一方、上記輪郭点データメモリから順
次読出される任意の輪郭点データが先に読出され
た輪郭点データによるデータ点列の端点に連結し
ないときには上記輪郭点データを新たな一対のデ
ータ点列における一方の始点として、この新たな
データ点列における他方の始点及びその延長点を
前記したのと同様に順次検出することにより、輪
郭点データメモリから順次読出された輪郭点デー
タ群を複数のデータ点列として点列バツフアに一
旦格納した後、各データ点列の端点データを比較
して各端点相互の連結関係を判定し、連結され得
るデータ点列同士を結合させて輪郭線データメモ
リに格納するようにしたことを特徴する輪郭線抽
出方法。 ２ 物体の輪郭を構成する閉ループ二値画像に対
して画面走査順に得られる輪郭点データ群を、物
体の輪郭に沿う輪郭線データとして抽出する輪郭
線抽出装置であつて、上記輪郭点データ群を格納
する輪郭点データメモリと、この輪郭点データメ
モリから順次読出される輪郭点データを順次所定
のデータ点列として格納する点列バツフアと、こ
の点列バツフア内の各データ点列の端点に対応す
る各点列端点データを順次格納する点列端点レジ
スタと、上記輪郭点データメモリから順次読出さ
れる輪郭点データが上記点列レジスタ内の点列端
点データと隣接するか否かを判定する判定手段
と、この判定手段により上記輪郭点データが点列
端点データに連結しないと判定されたときに、上
記点列バツフアに一対のデータ点列を格納するス
ペースを設定すると共に、一対のデータ点列にお
ける一方の始点として上記輪郭点データを検出
し、これを点列バツフア及び点列端点バツフアに
送る始点検出手段と、上記判定手段により上記輪
郭点データが所定の点列端点データに連結すると
判定されたときに点列バツフアに格納すべき上記
一対のデータ点列における他方の始点若しくは該
当するデータ点列の延長点として上記輪郭点デー
タを検出し、これを点列バツフア及び点列端点レ
ジスタに送る延長点検出手段と、すべての輪郭点
データが点列バツフア内に格納されたときに点列
バツフア内の各データ点列の端点を比較して各端
点相互の連結関係を判定し、連結され得る各点列
同士を結合して閉ループ状の輪郭線データを抽出
する閉ループ形成手段と、この閉ループ形成手段
からの輪郭線データを格納する輪郭線データメモ
リとを備えた輪郭線抽出装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58225622A JPS60117381A (ja) | 1983-11-30 | 1983-11-30 | 輪郭線抽出方法及びその装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58225622A JPS60117381A (ja) | 1983-11-30 | 1983-11-30 | 輪郭線抽出方法及びその装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS60117381A JPS60117381A (ja) | 1985-06-24 |
| JPH0146912B2 true JPH0146912B2 (ja) | 1989-10-11 |
Family
ID=16832194
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58225622A Granted JPS60117381A (ja) | 1983-11-30 | 1983-11-30 | 輪郭線抽出方法及びその装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS60117381A (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2591984B2 (ja) * | 1988-06-06 | 1997-03-19 | 日立ソフトウェアエンジニアリング株式会社 | パターン認識装置 |
| JP2918383B2 (ja) * | 1992-02-27 | 1999-07-12 | 大日本スクリーン製造株式会社 | 画像の輪郭抽出方法および装置 |
-
1983
- 1983-11-30 JP JP58225622A patent/JPS60117381A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS60117381A (ja) | 1985-06-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2918383B2 (ja) | 画像の輪郭抽出方法および装置 | |
| EP0173098A2 (en) | Pattern outline tracking method and apparatus | |
| US5563995A (en) | Method and system for directly drawing a convex polygon having a given number of vertices with high speed | |
| HK4997A (en) | Method of generating dot signal corresponding to character pattern and device therefor | |
| JPS60117381A (ja) | 輪郭線抽出方法及びその装置 | |
| EP0278528B1 (en) | Area searching system | |
| US5307454A (en) | Apparatus for extracting local image from original image | |
| KR960003871B1 (ko) | 레이블링 방법 및 이것에 사용하는 장치 | |
| JPS6019549B2 (ja) | 図形照合装置 | |
| JP2910295B2 (ja) | 輪郭情報抽出装置 | |
| JP2922014B2 (ja) | 原画像パターンデータ再生装置 | |
| JPS61131084A (ja) | 画像処理装置 | |
| JP3100304B2 (ja) | ドットパターン発生装置およびドットパターン発生方法 | |
| JP3037504B2 (ja) | 画像処理方法及びその装置 | |
| JPS59140586A (ja) | 画像処理装置 | |
| JPH0348981A (ja) | 閉領域判別方式 | |
| JPH11272860A (ja) | 図面自動入力装置の特殊線表示方法 | |
| JP2573972B2 (ja) | パターン整合装置 | |
| JPS6155789A (ja) | 輪郭線抽出装置 | |
| JPH11345333A (ja) | ラベリング処理システム及び方法 | |
| JPS59128662A (ja) | ラスタ・ベクトル変換装置 | |
| JPS6250971A (ja) | パタ−ン判別装置 | |
| JPS63184887A (ja) | 削除ライン決定処理方式 | |
| JPH06309468A (ja) | データ表示装置 | |
| JPS5846476A (ja) | 黒領域頂点検出回路 |