JPS60218173A - 直線性判定方式 - Google Patents
直線性判定方式Info
- Publication number
- JPS60218173A JPS60218173A JP59074520A JP7452084A JPS60218173A JP S60218173 A JPS60218173 A JP S60218173A JP 59074520 A JP59074520 A JP 59074520A JP 7452084 A JP7452084 A JP 7452084A JP S60218173 A JPS60218173 A JP S60218173A
- Authority
- JP
- Japan
- Prior art keywords
- linearity
- feature points
- circuit
- unit
- inner product
- 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
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Computational Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Algebra (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- General Engineering & Computer Science (AREA)
- Image Analysis (AREA)
- Image Processing (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔発明の技術分野〕
本発明は、線図形、立体モデル等の複数の特徴点の直線
性をデータ処理により判定する直線性判定方式に関し、
特に順次未定な三特徴点（折点、交点、接続点等）の直
線性を判定する直線性判定方式に関する゛。
性をデータ処理により判定する直線性判定方式に関し、
特に順次未定な三特徴点（折点、交点、接続点等）の直
線性を判定する直線性判定方式に関する゛。
近年、線図形や立体モデル等の認識処理技術の研究が盛
んに行なわれている。このような認識処理技術は、テレ
ビカメラ等の撮像手段でとらえた画像から対象物を認識
する画像認識装置やＣＡＤ（Ｃｏｍｐｗｔｇｒ Ａｔｚ
ｉｚｔｅｔｌ ｆ）ｅｐｉｙｎ ） 等の二次元の設計
データから三次元の物体の輪郭を認識して三次元像を完
成するシステム等において用いられる。
んに行なわれている。このような認識処理技術は、テレ
ビカメラ等の撮像手段でとらえた画像から対象物を認識
する画像認識装置やＣＡＤ（Ｃｏｍｐｗｔｇｒ Ａｔｚ
ｉｚｔｅｔｌ ｆ）ｅｐｉｙｎ ） 等の二次元の設計
データから三次元の物体の輪郭を認識して三次元像を完
成するシステム等において用いられる。
係る認識処理では、線図形、立体モデル等の特徴点を把
え、この特徴点から線図形、立体モデル等構造線、面等
の位置関係を認識する必要がある。
え、この特徴点から線図形、立体モデル等構造線、面等
の位置関係を認識する必要がある。
□
このため、複数の特徴点（の座標）からこれらによって
点の関係である線分が存在するか（直線性）を判定する
必要があり、この線分の存在を判定するのに３つの特徴
点（例えば頂点）より直線性を判定する直線性判定方式
が用いられている。
点の関係である線分が存在するか（直線性）を判定する
必要があり、この線分の存在を判定するのに３つの特徴
点（例えば頂点）より直線性を判定する直線性判定方式
が用いられている。
従来の直線性判定方式には、第１図に示す様に３つの特
徴点の内２つの端点α、Ｃより直線式をめて、その中間
点すのその直線に対するギャップ（距離）を計算して閾
値５と比較して中間点すがその直線上の点か否かを判定
する第１の方式と、第２に示す様に３つの特徴点α、ｂ
、ｃによって作られる角度θの大きさによって点すが点
α、Ｃを結ぶ直線上の点か否かを判定する第２の方式と
が知られていた。しかしながら、従来の第１、第２の方
式では特徴点αｔｈｅ’が連続でないと、即ち、予じめ
順序がαｔｈｅ’という様に定まっている場合に、点α
、ｂ、ｃが直線上にあるか否かを判定できるものである
から、不連続、即ち順序が定まっていない特徴点の直線
性は判定できないという問題があった。
徴点の内２つの端点α、Ｃより直線式をめて、その中間
点すのその直線に対するギャップ（距離）を計算して閾
値５と比較して中間点すがその直線上の点か否かを判定
する第１の方式と、第２に示す様に３つの特徴点α、ｂ
、ｃによって作られる角度θの大きさによって点すが点
α、Ｃを結ぶ直線上の点か否かを判定する第２の方式と
が知られていた。しかしながら、従来の第１、第２の方
式では特徴点αｔｈｅ’が連続でないと、即ち、予じめ
順序がαｔｈｅ’という様に定まっている場合に、点α
、ｂ、ｃが直線上にあるか否かを判定できるものである
から、不連続、即ち順序が定まっていない特徴点の直線
性は判定できないという問題があった。
また、第１の方式では、第１図（Ｂ）の如く端点α。
０間の距離が短いと、その閾値をｌ′ の如く変更しな
ければならず、特徴点の位置に応じて閾値を変更すると
いう手間のかかる演算を行なう必要があるという問題が
あり、第２の方式では、第２図（Ｂ）の如く線分α、Ｃ
と線分す、ｃ が垂直である場合でも角度θが小さいと
同一直線上にあると判定され、精度が悪いという問題も
あった。
ければならず、特徴点の位置に応じて閾値を変更すると
いう手間のかかる演算を行なう必要があるという問題が
あり、第２の方式では、第２図（Ｂ）の如く線分α、Ｃ
と線分す、ｃ が垂直である場合でも角度θが小さいと
同一直線上にあると判定され、精度が悪いという問題も
あった。
本発明の目的は、特徴点が不連続でも直線性を判定でき
しかも高速に且つ確実な判定が可能な直線性判定方式を
提供するにある。
しかも高速に且つ確実な判定が可能な直線性判定方式を
提供するにある。
上述の目的の達成のため、本発明は、３つの特徴点の直
線性を該特徴点の座標から判定する直線性判定方式にお
いて、該１つの特徴点から他の２つの特徴点に向かう２
つの単位ベクトルを作成し、該作成された２つの単位ベ
クトルの内積を演算する演算回路を設け、３つの特徴点
の内任意の２つの特徴点について該演算回路が各々の内
積を演算し１、各内積の絶対値の相加平均の値によって
直線 ６− 性を判定することを特徴としている。また、本発明の一
実施態様によれば、前記直線性の判定のため前記相加平
均の値と閾値とを比較することを特徴としている。
線性を該特徴点の座標から判定する直線性判定方式にお
いて、該１つの特徴点から他の２つの特徴点に向かう２
つの単位ベクトルを作成し、該作成された２つの単位ベ
クトルの内積を演算する演算回路を設け、３つの特徴点
の内任意の２つの特徴点について該演算回路が各々の内
積を演算し１、各内積の絶対値の相加平均の値によって
直線 ６− 性を判定することを特徴としている。また、本発明の一
実施態様によれば、前記直線性の判定のため前記相加平
均の値と閾値とを比較することを特徴としている。
以下、本発明を実施例により詳細に説明する。
第３図及び第４図は本発明の原理説明図である。
第３図に示す様に３つの特徴点をＰｌ ｗ Ｐｌ ｅ
ＰＢとすると、任意の２つの特徴点（例えば、Ｐｌ 。
ＰＢとすると、任意の２つの特徴点（例えば、Ｐｌ 。
Ｐ、）の各々について他の特徴点に向う単位はクトル
゛を作成する。そして各特徴点ＰＩｓＰ！の単位はクト
ルの内積 １ を計算する。この単位はクトルの内積は周知の如く２つ
の単位ベクトルの角度の余弦に等しい。
ルの内積 １ を計算する。この単位はクトルの内積は周知の如く２つ
の単位ベクトルの角度の余弦に等しい。
４−
一方、第４図の如く余弦関数の絶対値は角度がＯ及び１
８０ 近傍ではＩＩこ近いことから、角 □度が０又は
１８０ 近傍であれば直線とみなせるので、余弦の絶対
値が１に近いかどうかによって矛゛ 直線性の判帛Ｆきる。
８０ 近傍ではＩＩこ近いことから、角 □度が０又は
１８０ 近傍であれば直線とみなせるので、余弦の絶対
値が１に近いかどうかによって矛゛ 直線性の判帛Ｆきる。
そこで、本発明では、２つの特徴点Ｐ１ｓＰＲ′につい
ての余弦の絶対値の相加平均の値によって直線性を判定
している。即ち閾値τを１より若干率さい値に設けて、
相加平均値と閾値τとの比較によって直線性を判定する
ようにしている。
ての余弦の絶対値の相加平均の値によって直線性を判定
している。即ち閾値τを１より若干率さい値に設けて、
相加平均値と閾値τとの比較によって直線性を判定する
ようにしている。
′換言すれば各特徴点の単位はクトルのなす角θが０・
又は１８０ に近い程直線に近くなることから、３特
徴点Ｐ、〜Ｐ３で作られる三角形の２頂角の余弦の絶対
値の相加平均をめれば、直線性の判定が可能□となる。
又は１８０ に近い程直線に近くなることから、３特
徴点Ｐ、〜Ｐ３で作られる三角形の２頂角の余弦の絶対
値の相加平均をめれば、直線性の判定が可能□となる。
しかも、実際に角度を演算するのでなく、余弦値を演算
するので高速な判定が可能となる。
するので高速な判定が可能となる。
第５図は本発明の一実施例ブロック図であり、第６図は
その処理フロー図である。
その処理フロー図である。
第５図中、１はメモリであり、各特徴点の座標を格納す
るものであり、デジタイザ等の座標入力手段によって入
力される特徴点の座標を格納するもの、２は演算回路で
あり、３つの特徴点ＰｉｓＰ、、Ｐ、の直線性を判定す
るものであり、特徴点ＰＧを中心に２つの単位ばクトル
を演算する単位はクトル化回路２０と、単位はクトルの
内積を演算するスカラー積演算回路２１と、スカラー積
の相加平均値をとり直線性を判定する判定回路２２とで
構成される。
るものであり、デジタイザ等の座標入力手段によって入
力される特徴点の座標を格納するもの、２は演算回路で
あり、３つの特徴点ＰｉｓＰ、、Ｐ、の直線性を判定す
るものであり、特徴点ＰＧを中心に２つの単位ばクトル
を演算する単位はクトル化回路２０と、単位はクトルの
内積を演算するスカラー積演算回路２１と、スカラー積
の相加平均値をとり直線性を判定する判定回路２２とで
構成される。
次に、第５図実施例構成の動作化ついて第６図。
フロー図により説明する。
先づ直線性を判定すべき３つの特徴点ＰｌｙＰ！＋Ｐ３
の座標（”＋ ＊ ３’１ｓ ｚｌ ） Ｉ（”！ ＊
ｙｔ ｌｚｔ ）ｓ（”８ ＊３’ｓ ＊ｚＲ）がメ
モリ１より単位ベクトル化回路２０に入力される。
の座標（”＋ ＊ ３’１ｓ ｚｌ ） Ｉ（”！ ＊
ｙｔ ｌｚｔ ）ｓ（”８ ＊３’ｓ ＊ｚＲ）がメ
モリ１より単位ベクトル化回路２０に入力される。
単位ばクトル化回路２０では、先づ２重を中心に単位は
クトルをめる。即ち、ＰｏをＰｌとし、ベクトルを演算
する。次にスカラー積演算回路２１でスカラー積歯θ１
を次式よりめる。
クトルをめる。即ち、ＰｏをＰｌとし、ベクトルを演算
する。次にスカラー積演算回路２１でスカラー積歯θ１
を次式よりめる。
スカラー積歯θ、は判定回路２２に送られ一時格納され
る。
る。
次に、判定回路２２はＰｏかＰ２かを判定し、Ｐ、でな
ければ、ｐｔを中心に同様の動作を行なうべく、単位ベ
クトル化回路２０にＰｏをＰ、とし、単位はクトルを演
算する様化指令する。単位ばクトル化回路２０は”ＰＳ
ｅｐｏｐｓを演算し、１に規格化し、単位ベクトルを得
る。次にスカラー積演算回路２１でスカラー積（２）θ
、を（１）式と同様次式によりめる。
ければ、ｐｔを中心に同様の動作を行なうべく、単位ベ
クトル化回路２０にＰｏをＰ、とし、単位はクトルを演
算する様化指令する。単位ばクトル化回路２０は”ＰＳ
ｅｐｏｐｓを演算し、１に規格化し、単位ベクトルを得
る。次にスカラー積演算回路２１でスカラー積（２）θ
、を（１）式と同様次式によりめる。
ＩＰ！ｐＨ１ＰｔＰｓｌ
７−
スカラー積（２）θ、は判定回路２２に送られる。判定
回路２２は次式によりスカラー積の絶対値の相加平均の
値ｔを計算して、直線性の判定指標とする。
回路２２は次式によりスカラー積の絶対値の相加平均の
値ｔを計算して、直線性の判定指標とする。
判定回路２２は、この相加平均値ｔと閾値τ（第４図）
とを比較し、ｔ４τなら直線ではない、ｔ〉τなら直線
であると判定する。この閾値τは０、９以上が好ましい
。
とを比較し、ｔ４τなら直線ではない、ｔ〉τなら直線
であると判定する。この閾値τは０、９以上が好ましい
。
第５図の実施例構成においては演算回路２の内部を３つ
の回路２０〜２２によって構成しているが、例えばマイ
クロプロセッサによって１つの回路で構成してもよく、
この場合第６図の処理をプログラムζこよって実行させ
ることによって実現できる。
の回路２０〜２２によって構成しているが、例えばマイ
クロプロセッサによって１つの回路で構成してもよく、
この場合第６図の処理をプログラムζこよって実行させ
ることによって実現できる。
以上本発明を一実施例により説明したが、本発明は本発
明の主旨に従い種々の変形が可能であり、本発明からこ
れらを排除するものではない。
明の主旨に従い種々の変形が可能であり、本発明からこ
れらを排除するものではない。
８−
以上説明した様に、本発明によれば、３つの特徴点の直
線性を該特徴点の座標から判定する直線性判定方式にお
いて、該１つの特徴点から他の２つの特徴点に向かう２
つの単位ベクトルを作成し、該作成された２つの単位は
クトルの内積を演算する演算回路を設け、３つの特徴点
の内任意の２つ性を判定することを特徴としているので
、任意の２つの特徴点について処理を行えばよいから、
３つの特徴点の順序が未定（即ち不連続）であっても直
線性の判定が可能となるという効果を奏し、これらの順
序を指定する必要がなく、直線性判定の適用範囲を大巾
に拡大することができる。また、単位はルトを演算し、
その内積を演算し、相加平均をめているので、特徴点の
位置関係にかかわらず判定閾値を変更する必要がないと
いう効果も奏し、閾値の演算という余分な手間を要しな
いから、それだけ高速な判定が可能となり、更に２つの
余弦値（内積）によっているから、それだけ正確な判定
も可能となるという効果も奏する。
線性を該特徴点の座標から判定する直線性判定方式にお
いて、該１つの特徴点から他の２つの特徴点に向かう２
つの単位ベクトルを作成し、該作成された２つの単位は
クトルの内積を演算する演算回路を設け、３つの特徴点
の内任意の２つ性を判定することを特徴としているので
、任意の２つの特徴点について処理を行えばよいから、
３つの特徴点の順序が未定（即ち不連続）であっても直
線性の判定が可能となるという効果を奏し、これらの順
序を指定する必要がなく、直線性判定の適用範囲を大巾
に拡大することができる。また、単位はルトを演算し、
その内積を演算し、相加平均をめているので、特徴点の
位置関係にかかわらず判定閾値を変更する必要がないと
いう効果も奏し、閾値の演算という余分な手間を要しな
いから、それだけ高速な判定が可能となり、更に２つの
余弦値（内積）によっているから、それだけ正確な判定
も可能となるという効果も奏する。
第１図及び第２図は従来の直線性判定方式説明図、第３
図及び第４図は本発明の原理説明図、第５図は本発明の
一実施例ブロック図、第６図は本発明による一実施例処
理フロー図である。 図中、２・・・・・・演算回路、２０・・・・・・単位
はクトル化回路、２１・・・・・・スカラー積演算回路
、２２・・・・・・判定回路。 特許出願人 富士通株式会社 代理人 弁理士 山 谷 晧 榮 −１１− 第 ／ 図 （Ａ） （Ｂ） ／ 第・ ２ 図 （Ａ） （ｓ）
図及び第４図は本発明の原理説明図、第５図は本発明の
一実施例ブロック図、第６図は本発明による一実施例処
理フロー図である。 図中、２・・・・・・演算回路、２０・・・・・・単位
はクトル化回路、２１・・・・・・スカラー積演算回路
、２２・・・・・・判定回路。 特許出願人 富士通株式会社 代理人 弁理士 山 谷 晧 榮 −１１− 第 ／ 図 （Ａ） （Ｂ） ／ 第・ ２ 図 （Ａ） （ｓ）
Claims (2)
- （１）３つの特徴点の直線性を咳特徴点の座標から判定
する直線性判定方式において、該１つの特徴点から他の
２つの特徴点に向かう２つの単位ベクトルを作成し、該
作成された２つの単位ベクトルの内積を演算する演算回
路を設け、３つの特徴点の内任意の２つの特徴点につい
て該演算回路が各々の内積を演算し、各内積の絶対値の
相加平均の値によって直線性を判定することを特徴とす
る直線性判定方式０ - （２）前記直線性の判定のため前記相加平均の値と閾値
とを比較することを特徴とする特許請求の範囲第（１）
項記載の直線性判定方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59074520A JPS60218173A (ja) | 1984-04-13 | 1984-04-13 | 直線性判定方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59074520A JPS60218173A (ja) | 1984-04-13 | 1984-04-13 | 直線性判定方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS60218173A true JPS60218173A (ja) | 1985-10-31 |
Family
ID=13549677
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59074520A Pending JPS60218173A (ja) | 1984-04-13 | 1984-04-13 | 直線性判定方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS60218173A (ja) |
-
1984
- 1984-04-13 JP JP59074520A patent/JPS60218173A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Coquillart | Computing offsets of B-spline curves | |
| US4888707A (en) | Object collision detection method and apparatus | |
| US5309521A (en) | Method and apparatus for generating a character curve by dividing and developing a bezier curve | |
| Zhou et al. | A complete, accurate and efficient solution for the perspective-n-line problem | |
| Zhao et al. | Range-data-based object surface segmentation via edges and critical points | |
| JPS62272366A (ja) | 図形情報処理装置 | |
| JPS60218173A (ja) | 直線性判定方式 | |
| WO2022095507A1 (zh) | 基于平均滤波的直线段平滑方法、装置、设备及存储介质 | |
| Tokuyama | Skinning-surface generation based on spine-curve control | |
| US5402531A (en) | Method for producing offset surface and offset solid | |
| US6486878B1 (en) | Method for detecting incorrectly oriented lofted solids in a solid modeling system | |
| JPH01292474A (ja) | 立体干渉演算装置 | |
| Bensoudane et al. | Fractional half-tangent of a curve described by Iterated Function Systems. | |
| Tanaka et al. | Generalized symmetry and its application to 3D shape generation | |
| KR20160115284A (ko) | 3차원 형상의 처리방법 | |
| JPH1139517A (ja) | 立体形状記述方法及び特徴点抽出方法 | |
| JP3886293B2 (ja) | ３次元曲面形状の集合演算方法 | |
| JPS63118982A (ja) | 多角形に対する点の内外判定演算処理方法 | |
| CN116501071B (zh) | 近似回折路径的规划方法和装置、电子设备和存储介质 | |
| JPS62154113A (ja) | Ｎｃデ−タ作成装置における境界内外判定方法 | |
| JP3002519B2 (ja) | Ｃａｄシステム | |
| JPH0566607B2 (ja) | ||
| JPH04155585A (ja) | 三次元ワイヤフレームの面種判定方式 | |
| JPS63256988A (ja) | スプライン補間法 | |
| WU et al. | 3D data acquiring system fusing active projection and stereo vision |