JPH11120366A - 線分隣接関係決定方法 - Google Patents
線分隣接関係決定方法Info
- Publication number
- JPH11120366A JPH11120366A JP10106165A JP10616598A JPH11120366A JP H11120366 A JPH11120366 A JP H11120366A JP 10106165 A JP10106165 A JP 10106165A JP 10616598 A JP10616598 A JP 10616598A JP H11120366 A JPH11120366 A JP H11120366A
- Authority
- JP
- Japan
- Prior art keywords
- line segment
- line
- sets
- gradient
- adjacency
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06V10/00—Arrangements for image or video recognition or understanding
- G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
- G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
- G06V10/75—Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
- G06V10/757—Matching configurations of points or features
Landscapes
- Engineering & Computer Science (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Computing Systems (AREA)
- Databases & Information Systems (AREA)
- Artificial Intelligence (AREA)
- General Health & Medical Sciences (AREA)
- Medical Informatics (AREA)
- Software Systems (AREA)
- Health & Medical Sciences (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Multimedia (AREA)
- Image Analysis (AREA)
Abstract
(57)【要約】
【課題】 パターン認識システムに用いられ、入力映
像から抽した複数の線分の間の隣接関係を決定して、高
速且つ効率的にパターン認識を行えるようにする線分隣
接関係決定方法及びその装置を提供する。 【解決手段】 Ｘ軸及びＹ軸方向に各々複数の線分か
ら選択される基準線分と隣接関係にある線分の集合を求
め、基準線分の勾配ｍと、基準線分と隣接関係を満足す
る各線分の中点とを結ぶ複数直線の勾配ｍiとを求め、
ｍがｍiより小さい場合、基準線分が直線の左側で隣接
関係を有することと決定し、ｍがｍiより大きい場合、
基準線分が線分の右側で隣接関係を有することと決定
し、ｍとｍiが等しい場合、基準線分が直線と隣接関係
を有しないと決定する。
像から抽した複数の線分の間の隣接関係を決定して、高
速且つ効率的にパターン認識を行えるようにする線分隣
接関係決定方法及びその装置を提供する。 【解決手段】 Ｘ軸及びＹ軸方向に各々複数の線分か
ら選択される基準線分と隣接関係にある線分の集合を求
め、基準線分の勾配ｍと、基準線分と隣接関係を満足す
る各線分の中点とを結ぶ複数直線の勾配ｍiとを求め、
ｍがｍiより小さい場合、基準線分が直線の左側で隣接
関係を有することと決定し、ｍがｍiより大きい場合、
基準線分が線分の右側で隣接関係を有することと決定
し、ｍとｍiが等しい場合、基準線分が直線と隣接関係
を有しないと決定する。
Description
【０００１】
【発明の属する技術分野】本発明は、パターン認識シス
テムに関し、特に、そのパターン認識システムにおい
て、走査された映像から抽出される物体の輪郭線を表す
複数の線分間の隣接関係を決定する方法に関する。
テムに関し、特に、そのパターン認識システムにおい
て、走査された映像から抽出される物体の輪郭線を表す
複数の線分間の隣接関係を決定する方法に関する。
【０００２】
【従来の技術】電気通信情報システムにおける映像処理
において、パターン認識技法はますます活発に研究され
ている。パターン認識技法において、パターンの認識
は、入力パターンを格納されたパターンモデルのリスト
と比較することにより行われる。他のパターン認識技法
としては、与えられた入力映像がどのパターンに属して
いるかを決定する手法があり、また、より改善された技
法としては、パターン表示がサブパターンまたはパター
ンプリミティブ（pattern primitive）の同定、連関性
（connectivity）またはシンタクスに基づいて構成され
る。
において、パターン認識技法はますます活発に研究され
ている。パターン認識技法において、パターンの認識
は、入力パターンを格納されたパターンモデルのリスト
と比較することにより行われる。他のパターン認識技法
としては、与えられた入力映像がどのパターンに属して
いるかを決定する手法があり、また、より改善された技
法としては、パターン表示がサブパターンまたはパター
ンプリミティブ（pattern primitive）の同定、連関性
（connectivity）またはシンタクスに基づいて構成され
る。
【０００３】入力映像は２進データに変換され、その
後、物体の輪郭線が抽出される。物体の輪郭線は、境界
部分に存在する画素間を線分で結んで形成される軌跡と
して求められる。その後、物体の輪郭線を構成する線
分、または曲線は線分近似法によって一連の連続する線
分によって近似される。この直線近似法はハフ変換法
（Hough transform）によって行われる。
後、物体の輪郭線が抽出される。物体の輪郭線は、境界
部分に存在する画素間を線分で結んで形成される軌跡と
して求められる。その後、物体の輪郭線を構成する線
分、または曲線は線分近似法によって一連の連続する線
分によって近似される。この直線近似法はハフ変換法
（Hough transform）によって行われる。
【０００４】入力映像における物体の輪郭線が複数の線
分により表現され得る場合に、該当物体を構成する複数
の線分の間には一定の規則が存在することになる。
分により表現され得る場合に、該当物体を構成する複数
の線分の間には一定の規則が存在することになる。
【０００５】しかしながら、入力映像データを直線近似
法で近似して求められたデータは無意味なデータに過ぎ
ない。従来の方法においては、直線近似法により得られ
た全ての線分が物体を構成する線分に適用されて、該当
物体の外形を形成している。
法で近似して求められたデータは無意味なデータに過ぎ
ない。従来の方法においては、直線近似法により得られ
た全ての線分が物体を構成する線分に適用されて、該当
物体の外形を形成している。
【０００６】従って、従来の方法は物体の輪郭線を抽出
するの相当な時間がかかり、非効率であるという問題が
あった。
するの相当な時間がかかり、非効率であるという問題が
あった。
【０００７】
【発明が解決しようとする課題】従って、本発明の主な
目的は、パターン認識システムに用いられ、入力映像か
ら抽出した複数の線分の間の隣接関係を効果的に決定し
て、高速且つ効率的にパターン認識する線分隣接関係決
定方法を提供することにある。
目的は、パターン認識システムに用いられ、入力映像か
ら抽出した複数の線分の間の隣接関係を効果的に決定し
て、高速且つ効率的にパターン認識する線分隣接関係決
定方法を提供することにある。
【０００８】
【課題を解決するための手段】上記の目的を達成するた
めに、本発明によれば、パターン認識システムに用いら
れ、各々が走査された映像から抽出され、直線で近似さ
れた物体の輪郭線を表す複数の線分の間の隣接関係を決
定する線分隣接関係決定方法であって、Ｘ軸及びＹ軸方
向に各々前記複数の線分から順次選択される基準線分と
隣接関係を満足する線分の集合を求める第ａ過程と、前
記基準線分の勾配と、前記基準線分と隣接関係を満足す
る前記各線分の中点とを結ぶ複数直線の勾配とを求める
第ｂ過程と、前記基準線分の勾配が前記直線の勾配より
小さい場合は、前記基準線分が前記直線の左側で隣接関
係を有することと決定し、前記基準線分の勾配が前記直
線の勾配より大きい場合は、前記基準線分が前記線分の
右側で隣接関係を有することと決定し、前記基準線分の
勾配が前記直線の勾配と等しい場合は、前記基準線分が
前記直線と隣接関係を有さないことと決定する第ｃ過程
とを含むことを特徴とする線分隣接関係決定方法が提供
される。
めに、本発明によれば、パターン認識システムに用いら
れ、各々が走査された映像から抽出され、直線で近似さ
れた物体の輪郭線を表す複数の線分の間の隣接関係を決
定する線分隣接関係決定方法であって、Ｘ軸及びＹ軸方
向に各々前記複数の線分から順次選択される基準線分と
隣接関係を満足する線分の集合を求める第ａ過程と、前
記基準線分の勾配と、前記基準線分と隣接関係を満足す
る前記各線分の中点とを結ぶ複数直線の勾配とを求める
第ｂ過程と、前記基準線分の勾配が前記直線の勾配より
小さい場合は、前記基準線分が前記直線の左側で隣接関
係を有することと決定し、前記基準線分の勾配が前記直
線の勾配より大きい場合は、前記基準線分が前記線分の
右側で隣接関係を有することと決定し、前記基準線分の
勾配が前記直線の勾配と等しい場合は、前記基準線分が
前記直線と隣接関係を有さないことと決定する第ｃ過程
とを含むことを特徴とする線分隣接関係決定方法が提供
される。
【０００９】
【発明の実施の形態】以下、本発明の好適実施例につい
て図面を参照しながらより詳しく説明する。
て図面を参照しながらより詳しく説明する。
【００１０】図１を参照すると、本発明によるパターン
認識システムの概略的なブロック図が示されており、こ
のシステムは、スキャナ１０、分割部２０、線分推定部
３０及び物体認識部４０から構成されている。
認識システムの概略的なブロック図が示されており、こ
のシステムは、スキャナ１０、分割部２０、線分推定部
３０及び物体認識部４０から構成されている。
【００１１】スキャナ１０は通常のスキャナ機の１つで
あって、入力される映像信号を２進データに変換する役
割を果たす。このスキャナ１０によって走査された映像
は、図２に示したように線分Ｌ1、Ｌ2、Ｌ3、…により
構成される物体を含む。
あって、入力される映像信号を２進データに変換する役
割を果たす。このスキャナ１０によって走査された映像
は、図２に示したように線分Ｌ1、Ｌ2、Ｌ3、…により
構成される物体を含む。
【００１２】分割部２０は線分化及び輪郭線抽出アルゴ
リズムを用いて、例えば、線分のようなパターンプリミ
ティブを抽出する。その分割部２０により抽出された出
力は、図２に示したように線分Ｌ1、Ｌ2、Ｌ3、…によ
り構成される物体を有する。パターンプリミティブで表
現される抽出輪郭線は可変空間、例えば、Ｘ−Ｙ平面に
マッピングされて、ベクトルデータに変換される。この
ベクトルデータの変換プロセスには、物体を線分に近似
するハフ変換法（Ｈｏｕｇｈ ｔｒａｎｓｆｏｒｍ）が
用いられる。その後、線分に近似された線分データは線
分推定部３０に供給される。
リズムを用いて、例えば、線分のようなパターンプリミ
ティブを抽出する。その分割部２０により抽出された出
力は、図２に示したように線分Ｌ1、Ｌ2、Ｌ3、…によ
り構成される物体を有する。パターンプリミティブで表
現される抽出輪郭線は可変空間、例えば、Ｘ−Ｙ平面に
マッピングされて、ベクトルデータに変換される。この
ベクトルデータの変換プロセスには、物体を線分に近似
するハフ変換法（Ｈｏｕｇｈ ｔｒａｎｓｆｏｒｍ）が
用いられる。その後、線分に近似された線分データは線
分推定部３０に供給される。
【００１３】この線分推定部３０は、選択された線分に
対してＸ軸またはＹ軸方向に線分間の隣接関係、即ち、
右方向のまたは左方向の隣接関係を決定する。こうして
決定された隣接関係の情報は、線分推定部３０内のメモ
リ４０（図３参照）に格納される。
対してＸ軸またはＹ軸方向に線分間の隣接関係、即ち、
右方向のまたは左方向の隣接関係を決定する。こうして
決定された隣接関係の情報は、線分推定部３０内のメモ
リ４０（図３参照）に格納される。
【００１４】図３に示したように、メモリ４０は線分デ
ータ格納領域４２と隣接関係情報格納領域４４とより構
成される。線分データ格納領域４２には線分ベクトルデ
ータが格納され、隣接関係情報格納領域４４には該当線
分ベクトルデータに対する隣接関係情報即ち、右方向の
または左方向の隣接関係情報が格納される。その後、線
分推定部３０で得られた隣接関係情報は、物体認識部５
０に供給される。
ータ格納領域４２と隣接関係情報格納領域４４とより構
成される。線分データ格納領域４２には線分ベクトルデ
ータが格納され、隣接関係情報格納領域４４には該当線
分ベクトルデータに対する隣接関係情報即ち、右方向の
または左方向の隣接関係情報が格納される。その後、線
分推定部３０で得られた隣接関係情報は、物体認識部５
０に供給される。
【００１５】この物体認識部５０は、検索されるシンタ
クス及びそれ自体のパターンシンタクスルールに基づい
てパターン分類を行って、最終的なパターン認識結果を
出力する。
クス及びそれ自体のパターンシンタクスルールに基づい
てパターン分類を行って、最終的なパターン認識結果を
出力する。
【００１６】図４〜図６は、各々本発明による線分推定
部３０にて行われる線分の隣接関係を決定する過程を説
明するための流れ図である。図７〜９は各々線分間の隣
接関係を示した模式図である。
部３０にて行われる線分の隣接関係を決定する過程を説
明するための流れ図である。図７〜９は各々線分間の隣
接関係を示した模式図である。
【００１７】図４〜図６を参照すると、最初、ステップ
１１０において、一組の線分ベクトル（例えば、Ｌ1、
Ｌ2、Ｌ3、Ｌ4）で表現される各線分がＸ−Ｙ平面上に
配列される。これらの各線分の両終点をＸ座標上に整列
することによって、集合Ｘを形成する。この集合Ｘは下
記の式（１）通り表現される。
１１０において、一組の線分ベクトル（例えば、Ｌ1、
Ｌ2、Ｌ3、Ｌ4）で表現される各線分がＸ−Ｙ平面上に
配列される。これらの各線分の両終点をＸ座標上に整列
することによって、集合Ｘを形成する。この集合Ｘは下
記の式（１）通り表現される。
【００１８】
【数１】 Ｘ＝｛χi｜χi＜χi+1，ｉ＝１，２，…，ｎ｝ 式（１）
【００１９】上記式（１）を満足する集合Ｘは、
｛Ｘ1、Ｘ2、Ｘ3、…、Ｘ8｝として表現され得る。
｛Ｘ1、Ｘ2、Ｘ3、…、Ｘ8｝として表現され得る。
【００２０】ステップ１２０において、各線分の両終点
をＸ軸上にマッピングして、２つの隣接する要素よりな
る集合Ｓを求める。この集合Ｓは、下記の式（２）のよ
うに表現され得る。
をＸ軸上にマッピングして、２つの隣接する要素よりな
る集合Ｓを求める。この集合Ｓは、下記の式（２）のよ
うに表現され得る。
【００２１】
【数２】 Ｓ＝｛（Ｘ、ｙ）χi≦χ≦χi+1，‐∞ｙ∞、ｉ＝１，２，…，ｎ−１｝ 式（２）
【００２２】従って、上記式（２）を満足する集合Ｓ
は、｛（Ｘ1、Ｘ2）、（Ｘ2、Ｘ3）、（Ｘ3、Ｘ4）、
…、（Ｘ7、Ｘ8）｝となる。
は、｛（Ｘ1、Ｘ2）、（Ｘ2、Ｘ3）、（Ｘ3、Ｘ4）、
…、（Ｘ7、Ｘ8）｝となる。
【００２３】ステップ１３０においては、Ｘ座標上で集
合Ｓの各要素により定義される区間内に存在する、線分
要素よりなる集合Ｕの第１要素が求められる。ここで、
図７に示すように、集合Ｕの第１要素の各線分は、各線
分の中点をＹ座標上にマッピングしてＹ座標値の昇順に
従って整列される。例えば、区間（Ｘ1、Ｘ2）に対応す
る集合Ｕの第１要素は（Ｌ4、Ｌ1）となる。その後、ス
テップ１４０にて、処理される区間があるか否かが判定
される。まだ、残りの区間が（Ｘ2、Ｘ3）より（Ｘ2、
Ｘ3）まで存在するので、プロセスはステップ１３０に
戻り、残りの区間全体に対して繰返して行われる。同様
に、区間（Ｘ1、Ｘ2）に対応する集合Ｕの第２要素は
（Ｌ4、Ｌ1、Ｌ2）であり、区間（Ｘ3、Ｘ4）に対応す
る第３要素は（Ｌ4、Ｌ1、Ｌ2）である。このようにし
て、全ての区間に対する処理が終了すると、ステップ１
５０にて集合Ｕは、｛（Ｌ4、Ｌ1）、（Ｌ4、Ｌ1、
Ｌ2）、（Ｌ4、Ｌ1、Ｌ2）、（Ｌ4、Ｌ1、Ｌ2）、
（Ｌ4、Ｌ2）、（Ｌ4、Ｌ3）、（Ｌ3）｝となる。
合Ｓの各要素により定義される区間内に存在する、線分
要素よりなる集合Ｕの第１要素が求められる。ここで、
図７に示すように、集合Ｕの第１要素の各線分は、各線
分の中点をＹ座標上にマッピングしてＹ座標値の昇順に
従って整列される。例えば、区間（Ｘ1、Ｘ2）に対応す
る集合Ｕの第１要素は（Ｌ4、Ｌ1）となる。その後、ス
テップ１４０にて、処理される区間があるか否かが判定
される。まだ、残りの区間が（Ｘ2、Ｘ3）より（Ｘ2、
Ｘ3）まで存在するので、プロセスはステップ１３０に
戻り、残りの区間全体に対して繰返して行われる。同様
に、区間（Ｘ1、Ｘ2）に対応する集合Ｕの第２要素は
（Ｌ4、Ｌ1、Ｌ2）であり、区間（Ｘ3、Ｘ4）に対応す
る第３要素は（Ｌ4、Ｌ1、Ｌ2）である。このようにし
て、全ての区間に対する処理が終了すると、ステップ１
５０にて集合Ｕは、｛（Ｌ4、Ｌ1）、（Ｌ4、Ｌ1、
Ｌ2）、（Ｌ4、Ｌ1、Ｌ2）、（Ｌ4、Ｌ1、Ｌ2）、
（Ｌ4、Ｌ2）、（Ｌ4、Ｌ3）、（Ｌ3）｝となる。
【００２４】ステップ１６０〜１８０では、各要素が各
線分Ｌiと隣接関係を有する線分の組よりなる集合Ｍを
求める。ここで、ｉは正の整数であって、輪郭線を構成
する線分の個数と同じであり、本実施例においては４で
ある。ステップ１６０にて最初、線分Ｌ1と隣接関係を
有する線分が両線分Ｌ4、Ｌ2として求められる。その
後、隣接関係を有する線分がも存在するか否かがチェッ
クされる（ステップ１７０）。残りの線分Ｌ2、Ｌ3、Ｌ
4が存在するので、プロセスはステップ１６０に戻り、
残りの線分全体に対して繰返して行われる。このように
して、全ての線分に対する処理が終了すると、ステップ
１８０にて集合Ｍは｛（Ｌ2、Ｌ4）、（Ｌ1、Ｌ4）、
（Ｌ4）、（Ｌ1、Ｌ2、Ｌ3）｝となる。従って、各線分
Ｌ1〜Ｌ4と隣接関係を有する各線分の組はＹ軸方向への
隣接関係を満足する。
線分Ｌiと隣接関係を有する線分の組よりなる集合Ｍを
求める。ここで、ｉは正の整数であって、輪郭線を構成
する線分の個数と同じであり、本実施例においては４で
ある。ステップ１６０にて最初、線分Ｌ1と隣接関係を
有する線分が両線分Ｌ4、Ｌ2として求められる。その
後、隣接関係を有する線分がも存在するか否かがチェッ
クされる（ステップ１７０）。残りの線分Ｌ2、Ｌ3、Ｌ
4が存在するので、プロセスはステップ１６０に戻り、
残りの線分全体に対して繰返して行われる。このように
して、全ての線分に対する処理が終了すると、ステップ
１８０にて集合Ｍは｛（Ｌ2、Ｌ4）、（Ｌ1、Ｌ4）、
（Ｌ4）、（Ｌ1、Ｌ2、Ｌ3）｝となる。従って、各線分
Ｌ1〜Ｌ4と隣接関係を有する各線分の組はＹ軸方向への
隣接関係を満足する。
【００２５】前述したステップ１１０〜１８０における
Ｙ軸方向の隣接関係を満足する線分の集合を求める過程
と同様に、ステップ１９０〜２６０が、Ｘ軸方向の隣接
関係を満足する線分の集合を求めるために繰返して行わ
れる。
Ｙ軸方向の隣接関係を満足する線分の集合を求める過程
と同様に、ステップ１９０〜２６０が、Ｘ軸方向の隣接
関係を満足する線分の集合を求めるために繰返して行わ
れる。
【００２６】ステップ１９０にて、集合Ｙが｛ｙ1、
ｙ2、ｙ3、…、ｙ8｝が求められる。
ｙ2、ｙ3、…、ｙ8｝が求められる。
【００２７】ステップ２００にて、各要素が各線分の両
終点の間の区間を表す集合Ｔが、｛（ｙ1、ｙ2）、（ｙ
2、ｙ3）、…、（ｙ7、ｙ8）｝通り求められる。
終点の間の区間を表す集合Ｔが、｛（ｙ1、ｙ2）、（ｙ
2、ｙ3）、…、（ｙ7、ｙ8）｝通り求められる。
【００２８】ステップ１３０〜１５０と同様に、ステッ
プ２１０〜２３０が繰返して行われることによって、Ｙ
座標上で集合Ｔの各要素により定義される区間内に存在
する、線分要素よりなる集合Ｖの第１要素が求められ
る。ここで、図８に示すように、集合Ｖ内の第１要素の
各線分は、各線分の中点をＸ座標上にマッピングしてＸ
座標値の昇順に従って整列される。そのようにして求め
られた集合Ｖは、｛（Ｌ4、Ｌ3）、（Ｌ1、Ｌ4、
Ｌ3）、（Ｌ1、Ｌ4、Ｌ3）、（Ｌ1、Ｌ4、Ｌ3）、
（Ｌ1 、Ｌ3）、（Ｌ1、Ｌ2）、（Ｌ2）｝となる。
プ２１０〜２３０が繰返して行われることによって、Ｙ
座標上で集合Ｔの各要素により定義される区間内に存在
する、線分要素よりなる集合Ｖの第１要素が求められ
る。ここで、図８に示すように、集合Ｖ内の第１要素の
各線分は、各線分の中点をＸ座標上にマッピングしてＸ
座標値の昇順に従って整列される。そのようにして求め
られた集合Ｖは、｛（Ｌ4、Ｌ3）、（Ｌ1、Ｌ4、
Ｌ3）、（Ｌ1、Ｌ4、Ｌ3）、（Ｌ1、Ｌ4、Ｌ3）、
（Ｌ1 、Ｌ3）、（Ｌ1、Ｌ2）、（Ｌ2）｝となる。
【００２９】ステップ２４０〜２６０にて、各要素が各
線分Ｌiと隣接関係を有する線分の組よりなる集合Ｏが
｛（Ｌ2、Ｌ3、Ｌ4）、（Ｌ1）、（Ｌ1、Ｌ4）、
（Ｌ1、Ｌ3 ）｝通り求められる。各線分Ｌ1〜Ｌ4と隣接
関係を有する各線分の要素はＸ軸方向への隣接関係を満
足する。
線分Ｌiと隣接関係を有する線分の組よりなる集合Ｏが
｛（Ｌ2、Ｌ3、Ｌ4）、（Ｌ1）、（Ｌ1、Ｌ4）、
（Ｌ1、Ｌ3 ）｝通り求められる。各線分Ｌ1〜Ｌ4と隣接
関係を有する各線分の要素はＸ軸方向への隣接関係を満
足する。
【００３０】ステップ２７０においては、集合Ｍと集合
Ｏとの間の和集合Ｎｄｉ（Ｌ）が｛（Ｌ2、Ｌ3、
Ｌ4）、（Ｌ1、Ｌ4）、（Ｌ1、Ｌ4）、（Ｌ1、Ｌ2、
Ｌ3）｝通り求められる。ここで、和集合Ｎｄｉ（Ｌ）
内の各要素の成分は、両集合Ｍ、Ｏにおける対応要素の
成分どうしの和である。
Ｏとの間の和集合Ｎｄｉ（Ｌ）が｛（Ｌ2、Ｌ3、
Ｌ4）、（Ｌ1、Ｌ4）、（Ｌ1、Ｌ4）、（Ｌ1、Ｌ2、
Ｌ3）｝通り求められる。ここで、和集合Ｎｄｉ（Ｌ）
内の各要素の成分は、両集合Ｍ、Ｏにおける対応要素の
成分どうしの和である。
【００３１】図９には、各線分Ｌ1、Ｌ2、Ｌ3、Ｌ4に対
してＸ及びＹ軸方向に各々隣接関係を満足する線分が示
されている。ステップ２８０にて、基準線分のグラディ
エントまたは勾配ｍと、この基準線分の中点と基準線分
と隣接関係を満足する各線分の中点とを結ぶ直線の勾配
ｍiを求める。例えば、基準線分がＬ1であり、その基準
線分の勾配がｍであると、Ｌ1と隣接関係を満足する線
分はＬ2、Ｌ3及びＬ4である。Ｌ1の中点とＬ2、Ｌ3及び
Ｌ4と隣接関係を満足する各線分の中点とを結ぶ直線の
勾配は、各々ｍ2、ｍ3及びｍ4として求められる。
してＸ及びＹ軸方向に各々隣接関係を満足する線分が示
されている。ステップ２８０にて、基準線分のグラディ
エントまたは勾配ｍと、この基準線分の中点と基準線分
と隣接関係を満足する各線分の中点とを結ぶ直線の勾配
ｍiを求める。例えば、基準線分がＬ1であり、その基準
線分の勾配がｍであると、Ｌ1と隣接関係を満足する線
分はＬ2、Ｌ3及びＬ4である。Ｌ1の中点とＬ2、Ｌ3及び
Ｌ4と隣接関係を満足する各線分の中点とを結ぶ直線の
勾配は、各々ｍ2、ｍ3及びｍ4として求められる。
【００３２】ステップ２９０においては、勾配ｍと勾配
ｍi（例えば、ｍ2）との間の比較が行われる。もし、勾
配ｍが勾配ｍ2より小さい場合は、基準線分Ｌ1が隣接関
係を満足する線分Ｌ2の左側に配置されていると決定し
（ステップ３００）、勾配ｍが勾配ｍ2より大きい場合
には、基準線分Ｌ1が線分Ｌ2の右側に配置されていると
決め（ステップ３１０）、勾配ｍ＝勾配ｍ2の場合は、
両側の何れにも属さないと決定する（ステップ３０
５）。
ｍi（例えば、ｍ2）との間の比較が行われる。もし、勾
配ｍが勾配ｍ2より小さい場合は、基準線分Ｌ1が隣接関
係を満足する線分Ｌ2の左側に配置されていると決定し
（ステップ３００）、勾配ｍが勾配ｍ2より大きい場合
には、基準線分Ｌ1が線分Ｌ2の右側に配置されていると
決め（ステップ３１０）、勾配ｍ＝勾配ｍ2の場合は、
両側の何れにも属さないと決定する（ステップ３０
５）。
【００３３】ステップ２８０において全ての線分Ｌ1、
Ｌ2、Ｌ3及びＬ4に対するチェックが行われることによ
って、本実施例においては、線分Ｌ1が線分Ｌ2の左側で
隣接関係を有することと決定する。すると、ステップ３
００〜ステップ３１０で得られた結果データはメモリ４
０に格納される（ステップ３２０）。
Ｌ2、Ｌ3及びＬ4に対するチェックが行われることによ
って、本実施例においては、線分Ｌ1が線分Ｌ2の左側で
隣接関係を有することと決定する。すると、ステップ３
００〜ステップ３１０で得られた結果データはメモリ４
０に格納される（ステップ３２０）。
【００３４】ステップ３３０においては、処理される線
分が存在するか否かを判断して、存在する場合はプロセ
スはステップ３００に戻り、上記ステップ２８０〜３３
０を繰返して行われる。全ての線分が処理され、その結
果データがメモリ４０に全て格納された場合、プロセス
は終了する。
分が存在するか否かを判断して、存在する場合はプロセ
スはステップ３００に戻り、上記ステップ２８０〜３３
０を繰返して行われる。全ての線分が処理され、その結
果データがメモリ４０に全て格納された場合、プロセス
は終了する。
【００３５】上記において、本発明の好適な実施の形態
について説明したが、本発明の請求範囲を逸脱すること
なく、当業者は種々の改変をなし得るであろう。
について説明したが、本発明の請求範囲を逸脱すること
なく、当業者は種々の改変をなし得るであろう。
【００３６】
【発明の効果】従って、本発明によれば、走査された映
像から抽出される各線分の間の隣接関係を効果的に取り
決め、その隣接関係情報をメモリに格納することによっ
て、線分を推定するに掛かる時間をより一層減らすこと
ができる。
像から抽出される各線分の間の隣接関係を効果的に取り
決め、その隣接関係情報をメモリに格納することによっ
て、線分を推定するに掛かる時間をより一層減らすこと
ができる。
【図１】通常のパターン認識システムのブロック図であ
る。
る。
【図２】複数の線分よりなる物体の近似輪郭線映像を示
した模式図である。
した模式図である。
【図３】図１中の線分推定部内のメモリの構成を示した
模式図である。
模式図である。
【図４】本発明による線分隣接関係決定方法を説明する
流れ図である。
流れ図である。
【図５】本発明による線分隣接関係決定方法を説明する
流れ図である。
流れ図である。
【図６】本発明による線分隣接関係決定方法を説明する
流れ図である。
流れ図である。
【図７】線分間の隣接関係を示した模式図である。
【図８】図７と同様線分間の隣接関係を示した模式図で
ある。
ある。
【図９】図７及び図８と同様線分間の隣接関係を示した
模式図である。
模式図である。
１０ スキャナ ２０ 分割部 ３０ 線分推定部 ４０ メモリ ４２ 線分データ格納領域 ４４ 隣接関係情報格納領域 ５０ 物体認識部
Claims (8)
- 【請求項１】 パターン認識システムに用いられ、各
々が走査された映像から抽出され、直線で近似された物
体の輪郭線を表す複数の線分の間の隣接関係を決定する
線分隣接関係決定方法であって、 Ｘ軸及びＹ軸方向に各々前記複数の線分から順次選択さ
れる基準線分と隣接関係を満足する線分の集合を求める
第ａ過程と、 前記基準線分の勾配と、前記基準線分と隣接関係を満足
する前記各線分の中点とを結ぶ複数直線の勾配とを求め
る第ｂ過程と、 前記基準線分の勾配が前記直線の勾配より小さい場合
は、前記基準線分が前記直線の左側で隣接関係を有する
ことと決定し、前記基準線分の勾配が前記直線の勾配よ
り大きい場合は、前記基準線分が前記線分の右側で隣接
関係を有することと決定し、前記基準線分の勾配が前記
直線の勾配と等しい場合は、前記基準線分が前記直線と
隣接関係を有さないことと決定する第ｃ過程とを含むこ
とを特徴とする線分隣接関係決定方法。 - 【請求項２】 前記第ｃ過程で得られた結果データ
を、前記パターン認識システムに組み込まれたメモリに
格納する第ｄ過程を更に含むことを特徴とする請求項１
に記載の線分隣接関係決定方法。 - 【請求項３】 前記第ａ過程が、 各要素が前記複数の線分の各終点をＸ座標及びＹ座標上
にマッピングして各座標上の値を表す２つの集合を求め
る第ａ１過程と、 各要素が前記複数の線分の両終点をＸ軸及びＹ軸上にマ
ッピングして、２つの隣接する値よりなる２つの集合を
求める第ａ２過程と、 前記第ａ２過程で得られた各集合に対して、前記２つの
隣接する値の間の区間内に存在する、線分要素よりなる
２つの集合を求める第ａ３過程と、 前記第ａ３過程で得られた各集合に対して、各要素が前
記各線分と隣接関係を有する線分よりなる２つの集合を
求める第ａ４過程と、 前記第ａ４過程で得られた２つの集合の間の和集合を求
める第ａ５過程とを有することを特徴とする請求項１に
記載の線分隣接関係決定方法。 - 【請求項４】 前記第ａ過程が、 各要素が前記複数の線分の各終点をＸ座標及びＹ座標上
にマッピングして、各座標上の値を表す２つの集合を求
める第ａ１過程と、 各要素が前記複数の線分の両終点をＸ軸及びＹ軸上にマ
ッピングして、２つの隣接する値よりなる２つの集合を
求める第ａ２過程と、 前記第ａ２過程で得られた各集合に対して、前記２つの
隣接する値の間の区間内に存在する、線分要素よりなる
２つの集合を求める第ａ３過程と、 前記第ａ３過程で得られた各集合に対して、各要素が前
記各線分と隣接関係を有する線分よりなる２つの集合を
求める第ａ４過程と、 前記第ａ４過程で得られた２つの集合の間の和集合を求
める第ａ５過程とを有することを特徴とする請求項２に
記載の線分隣接関係決定方法。 - 【請求項５】 パターン認識システムに用いられ、各
々が走査された映像から抽出され、直線で近似された物
体の輪郭線を表す複数の線分の間の隣接関係を決定する
線分隣接関係決定装置であって、 Ｘ軸及びＹ軸方向に各々前記複数の線分から順次選択さ
れる基準線分と隣接関係を満足する線分の集合を求める
線分集合計算手段と、 前記基準線分の勾配と、前記基準線分と隣接関係を満足
する前記各線分の中点とを結ぶ複数直線の勾配とを求め
る勾配計算手段と、 前記基準線分の勾配が前記直線の勾配より小さい場合
は、前記基準線分が前記直線の左側で隣接関係を有する
ことと決定し、前記基準線分の勾配が前記直線の勾配よ
り大きい場合は、前記基準線分が前記線分の右側で隣接
関係を有することと決定し、前記基準線分の勾配が前記
直線の勾配と等しい場合は、前記基準線分が前記直線と
隣接関係を有さないことと決定する隣接関係決定手段と
を含むことを特徴とする線分隣接関係決定装置。 - 【請求項６】 前記隣接関係決定手段で得られた結果
データを格納する格納手段をさらに含むことを特徴とす
る請求項５に記載の線分隣接関係決定装置。 - 【請求項７】 前記線分集合計算手段が、 各要素が前記複数の線分の各終点をＸ座標及びＹ座標上
にマッピングして各座標上の値を表す２つの集合を求め
る第１集合計算手段と、 各要素が前記複数の線分の両終点をＸ軸及びＹ軸上にマ
ッピングして、２つの隣接する値よりなる２つの集合を
求める第２集合計算手段と、 前記第２集合計算手段で得られた各集合に対して、前記
２つの隣接する値の間の区間内に存在する、線分要素よ
りなる２つの集合を求める第３集合計算手段と、 前記第３集合計算手段で得られた各集合に対して、各要
素が前記各線分と隣接関係を有する線分よりなる２つの
集合を求める第４集合計算手段と、 前記第４集合計算手段で得られた２つの集合の間の和集
合を求める第５集合計算手段とを有することを特徴とす
る請求項５に記載の線分隣接関係決定装置。 - 【請求項８】 前記線分集合計算手段が、 各要素が前記複数の線分の各終点をＸ座標及びＹ座標上
にマッピングして各座標上の値を表す２つの集合を求め
る第１集合計算手段と、 各要素が前記複数の線分の両終点をＸ軸及びＹ軸上にマ
ッピングして、２つの隣接する値よりなる２つの集合を
求める第２集合計算手段と、 前記第２集合計算手段で得られた各集合に対して、前記
２つの隣接する値の間の区間内に存在する、線分要素よ
りなる２つの集合を求める第３集合計算手段と、 前記第３集合計算手段で得られた各集合に対して、各要
素が前記各線分と隣接関係を有する線分よりなる２つの
集合を求める第４集合計算手段と、 前記第４集合計算手段で得られた２つの集合の間の和集
合を求める第５集合計算手段とを有することを特徴とす
る請求項６に記載の線分隣接関係決定装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1997-49947 | 1997-09-30 | ||
| KR1019970049947A KR19990027482A (ko) | 1997-09-30 | 1997-09-30 | 패턴 인식 시스템에서 영상내 물체 구성 직선들의 관계 설정방법 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11120366A true JPH11120366A (ja) | 1999-04-30 |
Family
ID=19521961
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10106165A Pending JPH11120366A (ja) | 1997-09-30 | 1998-04-16 | 線分隣接関係決定方法 |
Country Status (3)
| Country | Link |
|---|---|
| JP (1) | JPH11120366A (ja) |
| KR (1) | KR19990027482A (ja) |
| GB (1) | GB2329738A (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3861157B2 (ja) | 2004-02-27 | 2006-12-20 | 国立大学法人広島大学 | 参照データ最適化装置とパターン認識システム |
| KR100817298B1 (ko) * | 2005-12-08 | 2008-03-27 | 한국전자통신연구원 | 양손 검출 및 추적 방법 |
| CN115631235B (zh) * | 2022-11-11 | 2026-02-17 | 武船重型工程股份有限公司 | 一种定位尺寸标注方法 |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0293397A1 (en) * | 1986-09-18 | 1988-12-07 | LEAVERS, Violet Frances | Shape detection |
-
1997
- 1997-09-30 KR KR1019970049947A patent/KR19990027482A/ko not_active Withdrawn
-
1998
- 1998-04-08 GB GB9807618A patent/GB2329738A/en not_active Withdrawn
- 1998-04-16 JP JP10106165A patent/JPH11120366A/ja active Pending
Also Published As
| Publication number | Publication date |
|---|---|
| KR19990027482A (ko) | 1999-04-15 |
| GB2329738A (en) | 1999-03-31 |
| GB9807618D0 (en) | 1998-06-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2940317B2 (ja) | 画像処理装置 | |
| US6185341B1 (en) | Image processing using vector data to reduce noise | |
| CN112419208A (zh) | 一种基于施工图审查矢量图纸编译方法及系统 | |
| CN116137913B (zh) | 用于对象分割的方法、数据处理系统、计算机程序产品和计算机可读介质 | |
| US20020006224A1 (en) | Computer automated process for vectorization of raster images | |
| JP2542947B2 (ja) | 画像処理装置 | |
| CN107146215A (zh) | 一种基于颜色直方图和凸包的显著性检测方法 | |
| JPH11120366A (ja) | 線分隣接関係決定方法 | |
| JP2845269B2 (ja) | 図形整形装置および図形整形方法 | |
| Ablameyko et al. | Vectorization and representation of large-size 2-D line-drawing images | |
| US5426712A (en) | Method and apparatus for describing a character image based on its contours, and for classifying the character image for character recognition based on a resulting contour-based description of the character image | |
| JPH07334648A (ja) | 画像処理方法及びその装置 | |
| JP2770849B2 (ja) | 画像処理装置 | |
| JPH08167028A (ja) | 画像処理方法 | |
| JP3782239B2 (ja) | 画像部品化方法及び画像部品化プログラムを記録した記録媒体 | |
| CN117291944B (zh) | 图像处理方法及相关设备 | |
| Bose et al. | An integrated approach for range image segmentation and representation | |
| Shimotsuji et al. | A High Speed Raster-to-Vector Conversion Using Special Hardware for Contour Tracking. | |
| JPH0461558A (ja) | 画像処理方法 | |
| JP2868533B2 (ja) | 図面読み取り装置 | |
| JPH07298265A (ja) | 動きベクトル探索方法と装置 | |
| JPH0414391B2 (ja) | ||
| JPH04119477A (ja) | 曲線近似方法 | |
| JP2613211B2 (ja) | 画像入力装置 | |
| WO1990012370A1 (fr) | Appareil de reconnaissance |