JPS63229576A - 線分抽出装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概　要〕 ハフ（Ｈｏｕｇｈ）変換に基づいて画像データの輪郭部
の座標データについて写像変換を行ない、写像関数パラ
メータとしての座標系原点からの線分画像の法線方向の
線分状画像までの距離および線分状画像が座標系となす
角度、を２次元状パラメータとしてヒストグラムを算出
し、ヒストグラムの最大のものが生じた距離および角度
を求めて、この距離と角度によって表わされる線分を算
出する装置であり、特に、上記写像関数値の計算を高速
にするため、角度を複数のセグメントに分割し、各セグ
メントについて同一の座標データについて乗算をするこ
となく加算のみで写像関数を、同時的に行なわせるよう
にした線分抽出装置である。

〔産業上の利用分野〕

本発明は画像解析技術に関するものであり、より特定的
には、線分成分を含む原画像から写像変換を行ない線分
を抽出する線分抽出装置に関する。

本発明の線分抽出装置は、ロボットの眼の一部として機
能するパターン認識装置等に用いられる。

〔従来の技術〕

近年、人間の眼と同様の機能を機械によって実現するた
めに物体の認識技術が盛んに開発されている。

この様な物体の認識においては、物体を画像として把え
、この画像から物体の特徴等の情報を抽出して物体を認
識する方法が用いられている。このため、一般に物体を
テレビカメラ等の撮像手段によって盪像し、原画像を取
り込み、この画像をもとに電気的処理を行って情報抽出
、特に直線線分抽出を行なう必要がある。一方、このよ
うな原画像は背景や照明条件に強い制限のある２値画像
処理主体のものでは、比較的原画像の構造線の抽出が容
易であるが、制限の少ない通常反射光下では原画像自体
が濃淡画像となる。このため濃淡画像から輪郭抽出処理
を行なう必要が生じてくる。

この輪郭抽出処理における問題として、原画像に輪郭の
途切れや輪郭成分以外のものが含まれていることにあり
、このような不明確な原画像からいかに輪郭を抽出する
かの解決策が望まれている。

この様な輪郭の抽出方法として従来よりハフ変換による
写像を用いるものがある。ハフ変換は、入力画像につい
ての直線あるいは線分の抽出等において、確かさを濃縮
させる手法として用いられるものである。第６図はハフ
変換の説明図を示す。

いわゆるハフ変換においては、第６図（Ａ）に図示の如
き、変数をｘ、ｙとする直交座標系の画像ブレーン上の
座標点（Ｘｔ、ｙｌで示される直線が、第６図（Ｂ）に
図示の如き、第４図（ａ）における原点０から直線への
法線方向の距離ρ、Ｘ軸と法線がなす角度θをパラメー
タとするパラメータプレーンにおいて、それぞれの（Ｘ
、。

ｙ僅）についてθをパラメータとして変化させた場合、
次式で表わされる正弦波（写像関数）に変換される。

ρ１＝ｘＩｃｏｓθ＋ｙＨ８ｉｎθ１″″。（１）ここ
で、第４図（Ａ）に図示の如きｌ直線上の各点に対応す
る正弦波を、パラメータプレーンにプロットし、ヒスト
グラムを作成すると、完全な直線の場合、第４図（Ｂ）
図示の如く、２点（ρが正のものだけ考えれば１点）で
交わる。この点の回転角θ。、高さρ。は、第４図（Ａ
）の各点が構成する直線に対し原点から垂直な線を下ろ
した時の垂直線の長さρ。と回転点θ。を示すことにな
る。これによって当該各点の構成する直線の情報を抽出
出来る。即ち、直線あるいは線分の抽出が可能となる。

また、完全な直線でない場合、ρ。、θ。の近傍に高い
頻度で交点が生ずるので、最も頻度の高いρ、θを抽出
することにより、最も直線に近いものを選び出すことが
できる。従って、途切れ、歪みのある線分画像であって
も線分の再生が可能となる。

第１式から明らかなように、ハフ変換は、１つの座標点
（Ｘｔ　　、ｙ；　）について角度をＯ〜２πまで変化
させた写像関数値ρを求めるものであり、１つの座標点
についても相当の計算がか＼る。更に、ヒストグラムの
最大ピークを求めるため、複数の座標点について、ぞれ
ぞれθを変化させた計算をしなければならない。

このような写像による画像の輪郭、即ち線分の抽出を高
速に行なう装置として、輪郭点座標を求め、さらに輪郭
点座標からパラメータθ、ρとする２次元メモリ空間に
おいて高速にヒストグラムを作成し、ヒストグラムのピ
ークに相当するθ、。

ρ、を見出す線分抽出装置が提案されている（例えば、
「線分抽出装置」特願昭６０−２４７７７８）。線分抽
出装置のブロック図を第５図に示す。図中、１１は輪郭
抽出部、１２はバッファ、１３は関数値計算部であり、
輪郭点座標（ｘｔ、ｙ、）から対応する写像関数の関数
値を計算するもの、４はバッファであり、関数値計算部
１３で計算された関数値を蓄えておくもの、１５はヒス
トグラム作成部であり、バッファ１４に蓄えられた関数
値からヒストグラム作成計算を行ない、ヒストグラムメ
モリ１６に書込むものである。１７はこれらの構成部分
の全体を制御すると共に、最大ヒストグラムが生じたρ
、θを検出するホストコンピュータである。この構成に
おいては、関数値計算部１３とヒストグラム作成部１５
とが別個に存在し、バッファ１４を介して直列に接続さ
れて、ヒストグラム作成の高速化を図っている。

ヒストグラム作成部１５およびヒストグラムメモリ１６
のより詳細な接線図を第６図に示す。図中、２０はアド
レス生成部であり、バッファ１４からのアドレスｎと関
数値ρ７をヒストグラムメモリ１６のアドレスとして生
成し、ヒストグラムメモリ１６をアクセスするもの、２
１はインクリメント回路であり、ヒストグラムメモリ１
６からアドレス生成部２０のアドレスによって読出され
たデータに１を加算し、すなわち、ヒストグラムを求め
、ヒストグラムメモリ１６ヘデータとして出力するもの
、２２はメモリコントローラであり、アドレスクロック
ＣＩ、に。、に応じてヒストグラムメモリ１６のリード
／ライトを制御するとともにインクリメント回路２１の
動作を制御するものである。

ヒストグラム作成部１５は、ヒストグラムメモリ１６を
アドレスｎと関数値ρ、とをアドレスとして対応する位
置のデータを読出し、このデータに“１”を加算して再
び同一位置に書込みを行なうよう構成されている。ヒス
トグラムメモリ１６は、例えば、８ビツトのデータが縦
５１２、横５１２コ収容できるメモリで構成されている
。ヒストグラムのピークが生じた縦の位置、および横の
位置がそれぞれθ２．ρ、を示している。

線分が完全な直線の場合、θ２．ρ、は１点である。一
方、そうでない場合は、複数のヒストグラム値が生じる
が、最大のピークの生じたθ、。

ρ、が最も直線に近い線分を示していると考えられる。

ホストコンピュータがこれらθ２　、ρ２を検出し、線
分を再生する。

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

上述の装置は成程度の高速化が図られるものの・忠実に
第１式の計算を行うものであるから、三角関数発生計算
、正弦成分および余弦成分の計算のための乗算に相当時
間がか＼す、依然として高速化が要望されている。

高速化を図る方法としては、各座標点について角度θに
ついてＯ〜２πまで変化させず、輪郭部の縁（エツジ）
の傾きにより成程度ヒストグラムのピークが生ずる点が
予測できることを用い、この傾きの角度についてのみハ
フ変換に基づ（写像変換を行う方法が提案されているじ
ＦｉｎｄｉｎｇＰｉｃｔｕｒｅ　Ｅｄｇｅｓ　Ｔｈｒｏ
ｕｇｈ　Ｃｏ１１ｉｎｅａｒｉｔｙ　ｏｆ　Ｆｅａｔｕ
ｒｅＰｏｉｎｔｓ　”　、Ｆｒａｎｋ　Ｏ’Ｇｏｒｍａ
ｎ　％他、ＩＥＥＥ　ＴＲＡＮＳＡＣＴ［０ＮＳＯＮ　
ＣＯＭＰＵＴＥＲ５、ＶＯＬ、Ｃ−２５、ｌｌｈ　４　
、＾ＰＲＩＬ　１９７６）。

しかしながらこの方法は傾きを求める微分がノイズによ
り大きく変動するため、ノイズに著しく弱く、正確な線
分抽出ができにくいという問題がある。

従って前述の単純な手法に基づくハフ変換によって線分
抽出を行うことが好ましい。

このような計算の時間を短縮化する方法としては、第１
に、余弦関数および正弦関数を逐時計算することなく予
め計算してテーブルに保存しておき、角度θをパラメー
タとしてテーブルルックアップして計算することなくＣ
Ｏ３θ、ｓｉｎθを抽出し、これらにＸ＋＋）’＋をそ
れぞれ乗算し、更にρ。

”Ｘ１ＣＯ８θ＋ｙＨｓｉｎθを求め、順次θを変化さ
せていく方法がある。しかしながらこの方法は、θを順
次変化させていかなければならず、例えば、０〜２πの
θを５１２ステツプに分割した場合、ｌ座標について、
５１２回の計算をしなければならず、依然として計算時
間がか＼るという問題が残る。

これを解決する方法としては、上述のシ析アル計算に代
えて、パイプライン処理を行って高速化を図る方法、或
いは、角度θを予め複数のセグメント、例えば５１２に
分け、各セグメントについて定まる角度のｃｏｓθ、ｓ
ｉｎθをテーブル化しておき、各セグメントｊごとＸ１
ＣＯ３θ７．ｙＨｓｉｎθｊを並列に計算させるように
する方法がある。しかしながら、この方法においても、
先ず、（ｘ、）と（ｃｏｓθｊ）の乗算、（ｙ＋）と（
ｓｉｎθ、）の乗算を行なわねばならず、この乗算時間
がかなり時間がか−るという問題がある。

〔問題を解決するための手段、および、作用〕本発明は
上述の問題を解決すべく創作されたものであり、その基
本的概念は、乗算を一切行なわない点、および相互干渉
のない複数パラレル処理を行うことにある。

本発明の線分抽出装置の原理ブロック図を第１図に示す
。当該線分抽出装置は、濃淡画像データ［ＮＩＭＡＧＦ
を人力し、その輪郭部を抽出し、二次元座標データ（Ｘ
ｉ、ｙｉ）としてとり出す輪郭抽出部ｌ、および、該輪
郭抽出部からの座標データについて、角度θを予め複数
のセグメントに分割し、各セグメント（θｊ）について
座標データをパラメータとしてハフ変換の正弦成分Ｘ、
・ｃｏｓθ、およびｙ、ｓｉｎθ、を乗算することなく
抽出し、これらを加算しヒストグラムを計算する写像計
算およびヒストグラム計算部４を具備する。

写像計算およびヒストグラム計算部４のθ、におけるセ
グメントの計算回路４０、の構成を第２図に示す。Ｘ、
・　ｃｏｓθｊ出力部４１．は座標データｘ１をパラメ
ータとして、このパラメータに対応したアドレス内に記
憶されたＸ１ＣＯ３θ、の値を出力する。すなわち、Ｘ
ｉ　　’　　ＣＯ５θ１出力部４１ｊは、Ｘ、に対応し
た容量を有し、ｘ、＝０〜±Ｘ□８について、予め、Ｘ
、・　ｃｏｓθｊが計算されて格納されている。従って
、Ｘ、が与えられると、Ｘ、・　ＣＯ３θｊの乗算をす
ることなく乗算結果が抽出される。ｙ（・　ｓｉｎθ、
出力部４２Ｊも同様である。このようにパラメータとし
てＸｉ　　。

ｙ、を与えることにより、乗算することなく、ｘ、ｃｏ
ｓ０７，３ｒ４５ｊｎθｊが出力部４１．　．４２．、
から出力され加算部４３．で））ｊ＝Ｘ、ｃＯ５θ、＋
ｙ。

ｓｉｎθ１が計算される。次いで、このρ、をアドレス
としてヒストグラムメモリ４４Ｊから現在の値ｔ７を取
り出し、ヒストグラム演算部４５．で“１′を加算して
、ρｊをアドレスとするヒストグラムメモリ４４．に保
存する。

第２図を参照して述べた写像計算およびヒストグラム計
算を、同じ座標（Ｘｉ　　、３’ｉ　）　ニツイテ他の
セグメントの角度についても、並列して同時計算をする
。

以下同様に、他の座標データについても行う・全ての座
標データについて以上の演算を行なった後・各セグメン
トのヒストグラムの最大が生じた（ρｗｒｍｗ　）　ｊ
を検出し、更に、これらの中の最大のものρ。を抽出す
る。各ヒストグラムメモリは角度に対応しているから、
最大のピークが生したヒストグラムにより角度θ。が判
る。このρ０゜θ。により線分が抽出できる。

以上の構成においては、Ｘｊ＋）’ｊの入力以降、ヒス
トグラム計算まで、各セグメント毎並列して独立動作可
能な構成としているので、メモリを共有することに伴う
オーバーヘッドも生じない。

尚、第１図におけるバッファ２は輪郭抽出部１で計算し
た座標データを一時保存し、写像計算およびヒストグラ
ム計算部４に転送するための任意的なものであり、両者
の処理スピードの相違を調整するために設けている。

またホストコンピュータ３は、上述の部分ｌ。

２．４の全体制御を行なう外、ρ。、θ。を抽出し、更
には線分を抽出する。

〔実施例〕

第１図および第２図のバッファ２、写像計算およびヒス
トグラム計算部４、およびホストコンピュータ３の一部
の実施例を第３図に示す。

バッファ２はＦＩＦＯ（ｆｉｒｓｔ−ｉｎ　ｆｉｒｓｔ
−ｏｕｔ）バッファ２１により実現されており、輪郭抽
出部１からの座標データを順次入力し、写像計算および
ヒストグラム計算部４が１つの座標データについてハフ
変換による写像関数値計算およびヒストグラムを更新す
る毎に、新たな座標データを出力する。

写像計算およびヒストグラム計算部４は、角度θについ
てＯ〜（Ｎｏ−＋）のＮ０個、例えばＮ、＝５１２のセ
グメントに分割されている。そのｊ番目の回路４０ｊは
プロセッサ５１ノー、　　（ｘｔ　　−ｃｏｓｊΔθ）
がテーブルとして記憶されているＲＯＭ　（ＴＭＣｊ　
）５２Ｊ、（ｙ、・５ｉｎｊΔθ）がテーブルとして記
憶されているｌ？ＯＭ　（ＴＭＳｊ　）　５３Ｊ、ヒス
トグラムメモｌ７５４．がデータバスＤ−ＢＵｓを介し
て接続されている。

プロセッサ５１ｊは、例えばマイクロプロセッサで構成
されており、ＦＩＦＯバッファ２１から座標データ（ｘ
ｌ、ｙ、）を入力し、Ｘ、をアドレスとしてｔｈｅ、５
２．に印加する。これにより、予め計算されたＸ逼ｃｏ
ｓ　（ｊΔθ）、イｌしθｔ＝ｊΔθがＴＭＣＪ５２ｊ
から抽出されプロセッサ５１Ｊに印加される。ｙ、が同
時にアドレスとしてＴＭＳ、　５３ｊに印加され、同様
に予め計算されテーブルとして記憶されているｙＨｓｉ
ｎ（ｊΔθ）が抽出されてプロセッサ５１Ｊに印加され
る。ここでＸｉ　　、Ｖｉ　はアドレッシング可能な整
数値としてＴＭＣｊ５２ｊ　　。

ＴＭＳ、　５３．に与えられる。プロセッサ５１Ｊは、
ＴＭＣｊ５２ｊからのｘ、ｃｏｓ（ｊΔθ）とＴＭＳｊ
５３゜からの（ｙ＝ｓｉｎ（ｊΔ°θ）を加算して写像
関数値（ρ、）、を計算する。この（ρ＋）Ｊは、ヒス
トグラムメモリ５４．のアドレシングに便利なように整
数値に変換される。更にプロセッサ５１．は整数値に変
換した（ρ、）、をアドレスとしてヒストグラムメモリ
５４Ｊ　の該当アドレスから現在のヒストグラム値ｔ１
を読出し、“ｌ”を加算して同アドレスに格納する。

これにより、１つの座標（ｘ８．ｙ、）について、且つ
、角度θｊ＝ｊΔθについて写像関数イ１σ（ρｉ）ｊ
およびヒストグラムが求められる。

同じ座標（ｘ；　　、ｙ＋）について、異なる角度につ
いても、他のセグメント回路４０．　　、４ＯＮｎ　−
１について、独立且つ並列に処理が行なわれる。

以下、順次次の座標データについても上記同様の処理を
行う。

対象とする線分についての画像データについて以上の処
理が終了すると、ピーク検出器６ｏが作動する。

ピーク検出１１６０はホストコンピュータ３の一部をな
すものであり、角度アドレスデコーダ６１を含み、角度
θによって規定される各セグメント内のヒストグラムメ
モリがらヒストグラムを抽出してそのセグメントについ
ての最大値を検出し、更に全体の中の最大のピークを求
める。これによりρ。、θ。が抽出される。ホストコン
ピュータは、このρ。、θ。に基いて線分を抽出する。

〔発明の効果〕

以上に述べた如く本発明によれば、ハフ変換に基づく写
像計算において三角関数計算および乗算を行なわず、加
算のみであり、且つ、角度範囲について独立並列的に同
時的に写像計算からヒストグラム計算まで行うので、各
セグメント相互間の干渉を生ずることなく、非常に高速
に写像関数値ρおよび角度θをパラメータとするヒスト
グラムを求めることができる。

以上により求めたヒストグラムの最大ピークが生じたρ
。、θ。を検出することにより、高速に線分抽出が可能
となる。

【図面の簡単な説明】

第１図は本発明の線分抽出装置の原理ブロック図、 第２図は第１図の写像計算およびヒストグラム計算部の
回路図、 第３図は本発明の実施例の写像計算・ヒストグラム計算
部の回路図、 第４図はハフ変換の説明図であって、（Ａ）は二次元直
交座標系における線分を示す図、（Ｂ）はρ、θプレイ
ンにおける写像関数のグラフ、第５図は従来の線分抽出
装置のブロック図、第６図は従来のヒストグラム生成関
係部接続図、である。 （符号の説明） １・・・輪郭抽出部、　　　　２・・・バッファ、３・
・・ホストコンピュータ、 ４・・・写像計算およびヒストグラム計算部、４１、・
・・Ｘｉ　・　ｃｏｓθ、出力部、４２、・・・ｙ８　
・　ｓｉｎθ１出力部、４３、・・・加算部、 ４４、・・・ヒストグラムメモリ、 ４５、・・・ヒストグラム演算部、 ４０ｏ〜４ＯＮ０・・・セグメント写像計算・ヒストグ
ラム計算回路、 ５１Ｊ・・・プロセッサ、 ５２Ｊ＝　（ｘ、’　ｃｏｓｊΔθ）　ＲＯＭ、５３Ｊ
−（ｙｔ　　・５ｉｎｊΔθ’）　ＲＯＭ、５４Ｊ　・
・・ヒストグラムメモリ、 ６０・・・ピーク検出器、 ６１・・・角度アドレスデコーダ。

Claims (1)

1. 【特許請求の範囲】 １、濃淡画像データの輪郭部の座標（ｘ＿ｉ、ｙ＿ｉ）
   を算出する手段（１）、および、 それぞれが予め定められた角度（θ＿ｊ）について、前
   座標データをパラメータとしてハフ変換の余弦成分（ｘ
   ＿ｉ・ｃｏｓθ＿ｊ）および正弦成分（ｙ＿ｉ・ｓｉｎ
   θ＿ｊ）を抽出する第１および第２のメモリ回路（４１
   ＿ｊ、４２＿ｊ）、該第１および第２のメモリ回路から
   の抽出結果を加算し写像関数値（ρ）を算出する回路（
   ４３＿ｊ）、および該加算回路の写像関数値出力に応じ
   た位置に記憶された値を加算してヒストグラムを計算し
   記憶する回路（４４＿ｊ、４５＿ｊ）、が複数個（４０
   ＿１〜４０＿ｎ）形成され、且つ、これらの複数個の回
   路が同じ座標データについてそれぞれ独立して演算され
   るように構成された、写像計算およびヒストグラム計算
   手段（４）、 を具備し、前記ヒストグラムのうち最大のものが生じた
   写像関数値（ρ＿０）および角度（θ＿０）を抽出して
   、これらの値によって規定される線分を抽出する、線分
   抽出装置。