JPH0799544B2 - 線分抽出装置 - Google Patents

Description

【発明の詳細な説明】 〔目次〕 概要 産業上の利用分野 従来の技術 発明が解決しようとする問題点 問題点を解決するための手段（第１図） 作用 実施例 （ａ）一実施例の構成の説明（第２図，第３図，第４
図） （ｂ）一実施例の動作の説明（第５図，第６図，第７
図） （ｃ）他の実施例の説明 発明の効果 〔概要〕 画像の輪郭点座標に対する写像関数を計算し、ヒストグ
ラムを作成して線分情報を抽出する線分抽出装置におい
て、写像関数の計算部と、バツフアと、ヒストグラム作
成部を直列に接続することによつて、写像関数の計算と
ヒストグラムの作成を並列に行なえるようにしたもので
ある。

〔産業上の利用分野〕

本発明は、原画像から写像によつて線分情報を抽出する
ための線分抽出装置に関し、特に高速にヒストグラムの
作成を行なうことのできる線分抽出装置に関する。

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

この様な物体の認識においては、物体を画像として肥
え、この画像から物体の特徴等の情報を抽出して物体を
認識する方法が用いられている。

このため、一般に物体をテレビカメラ等の撮像手段によ
つて撮像し、原画像を取入み、この画像を元に電気的処
理を行つて情報抽出を行なう必要がある。

一方、このような原画像は背景や証明条件に強い制限の
ある２値画像処理主体のものでは、比較的原画像の構造
線の抽出が容易であるが、制限の少ない通常反射光下で
は原画像自体が濃淡画像となり、このため濃淡画像から
輪郭抽出処理を行なう必要が生じてくる。

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

この様な輪郭の抽出方法として従来よりハフ（Hough）
変換による写像を用いるものや球面写像を用いるものが
ある。ハフ変換は、入力画像についての直線あるいは線
分の抽出等において、確かさを濃縮させる手法として用
いられるものである。第８図はハフ変換の説明図を示
す。いわゆるハフ変換においては、第８図（Ａ）図示の
如き画像プレーン上の点（xi,yi）が、第８図（Ｂ）図
示の如きパラメータプレーンにおいて、 ρ＝xicosθ＋yisinθ…………（１） で表わされる正弦波（写像関数）に変換される。ここ
で、第８図（Ａ）図示の如き１直線上の各点に対応する
正弦波を、パラメータプレーンにプロツトし、ヒストグ
ラムを作成すると、第８図（Ｂ）図示の如く、２点（ρ
が正のものだけ考えれば１点）で交れる。この点の回転
角θ_０，高さρ_０は、第８図（Ａ）の各点が構成する直
線に対し原点から垂直な線を下ろした時の垂直線の長さ
ρ_０と回転点θ_０を示すことになるから、これによつて
当該各点の構成する直線の情報を抽出出来る。即ち、直
線あるいは線分の抽出、途切れ、歪みのある線分の再生
等が可能となる。

〔従来の技術〕

このような写像による輪郭、即ち線分の抽出を行なう装
置として、従来第９図（Ａ）に示す如く、原画像より得
られた輪郭点座標（xi,yi）から前述の写像関数値ρを
計算し、ヒストグラムを作成するプロセッサCPUと、ヒ
ストグラムが書込まれるヒストグラムメモリHMで構成し
ていた。

このプロセッサCPUは、第９図（Ｂ）に示す如く、ハフ
変換においては、輪郭点座標（x₀,y₀）から対応する一
連の写像関数値ρ_０〜ρ₅₁₁を計算し、計算した関数値
からヒストグラムメモリHMにヒストグラムを作成書込み
する処理を交互に行なつてヒストグラムメモリHMに１つ
の座標に対するヒストグラムを完成させるものであつ
た。

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

このような線分抽出装置においては、輪郭点座標に対応
する写像関数ρを細かに分割して関数値を発生すればす
る程ヒストグラムの精度が上がり、従つて正確なヒスト
グラムメモリ上の極大点検出が可能となる。

例えば、第９図の例の如く一つの写像関数ρを512分割
すれば、256×256画素の入力画像に対し１画素以内の精
度で線分検出が行なえる。このような高精度の極大点検
出を可能とするには、１つの輪郭点に対し、512回の関
数値の計算とヒストグラムの作成を行わねばならず、従
来の如くプロセッサCPUによつて関数値計算とヒストグ
ラム作成の両方を交互に行なうものでは、１つの座標に
対し分オーダの時間がかかり、線分抽出に要する時間が
長くなるという問題があつた。

従つて、本発明は輪郭点座標からヒストグラムの作成を
高速に行なうことのできる線分抽出装置を提供すること
を目的とする。

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

第１図は本発明の原理説明図である。

図中、１は関数値計算部であり、輪郭点座標（xi,yi）
から対応する写像関数の関数値を計算するもの、２はバ
ツフアであり、関数値計算部１で計算された関数値を蓄
えておくもの、３はヒストグラム作成部であり、バツフ
ア２に蓄えられた関数値からヒストグラム作成計算を行
ない、ヒストグラムメモリに書込むものである。

従つて、本発明では、関数値計算部１とヒストグラム作
成部３とが別個に存在し、バツフア２を介して直列に接
続されて構成されている。

〔作用〕

本発明では、関数値計算部１とヒストグラム作成部３と
が別個に設けられているので、関数値計算とヒストグラ
ム計算を並列に実行できる。

又、バツフア２を介して計算部１と作成部３が接続され
ているので計算時間の差があつても、計算部１と作成部
３の並列動作が可能となる。

このため、輪郭点座標からヒストグラム作成までの過程
を高速化することができる。

〔実施例〕 （ａ）一実施例の構成の説明 第２図は本発明の一実施例構成図である。

図中、第１図で示したものと同一のものは同一の記号で
示してあり、４はテレビカメラであり、対象画像を撮像
し、画像信号に変換するもの、５は輪郭抽出部であり、
テレビカメラ４からの画像信号から輪郭点を抽出し、輪
郭点アドレスを発生するものであり、テレビカメラ４の
画像信号をアナログ／デジタル変換して８ビツトの画像
データに変換するA/Dコンバータ50と、A/Dコンバータ50
の出力を空間微分して輪郭（エツジ）以外を除去する空
間微分回路51と、空間微分回路51の出力を細線処理する
極値処理回路52と、極値処理回路52の出力によつて輪郭
点のアドレスを発生する輪郭アドレス発生回路53とで構
成されている。６は速度調整バツフアであり、輪郭抽出
部５からの輪郭点アドレスを一時蓄えておくもの、７は
ヒストグラムメモリであり、ヒストグラム作成部３によ
つてヒストグラムが書込まれるものであり、例えば256K
Bitの容量を有するもの、８はホストプロセツサであ
り、速度調整バツフア６、関数値計算部１、バツフア２
及びヒストグラム作成部３を制御するとともに、ヒスト
グラムメモリ７の内容を分析して線分抽出するものであ
る。

第３図は第２図構成における関数値ρ計算部の構成図で
ある。

図中、10はアドレスカウンタであり、クロツクを計数し
てハフ変換におけるθ方向10〜πのアドレスｎを発生す
るもの、11はcosθテーブルであり、各アドレスｎに対
応するcosθの値をテーブルとして有しているもの、12
はsinθテーブルであり、各アドレスｎに対応するsinθ
の値をテーブルとして有しているもの、13a,13b,13c,13
dは入力レジスタであり、入力レジスタ13aはバツフア６
からの輪郭点座標xiを格納するもの、入力レジスタ13b
はcosθテーブル11からのcosθｎ値を格納するもの、入
力レジスタ13cはバツフア６からの輪郭点座標yiを格納
するもの、入力レジスタ13dはsinθテーブル12からのsi
nθｎ値を格納するものである。

14,15は各々乗算器であり、乗算器14は入力レジスタ13a
の座標xiと入力レジスタ13bのcosθｎ値を乗算し、（xi
・cosθｎ）を出力するもの、乗算器15は入力レジスタ1
3cの座標yiと入力レジスタ13dのsinθｎ値を乗算し、
（yi・sinθｎ）を出力するもの、16a,16bは各々出力レ
ジスタであり、出力レジスタ16aはクロツクに応じて乗
算器14の出力（xi・cosθｎ）がセツトされるもの、出
力レジスタ16bはクロツクに応じて乗算器15の出力（yi
・sinθｎ）がセツトされるもの、17は加算器であり、
各出力レジスタ16a,16bの内容を加算し、ρｎ＝（xi・c
osθｎ＋yi・sinθｎ）を出力するもの、18は書込レジ
スタであり、クロツクに応じて加算器17の出力ρｎがセ
ツトされ、データバツフア２に書込むためのものであ
る。

従つて、関数値計算部１はハフ変換関数ρｎを計算する
よう構成されており、入力された輪郭点座標（xi,yi）
に対し、各アドレスｎ（＝０〜511）のハフ変換関数値
ρｎをハードウエアによつて計算するように構成され、
アドレスｎと関数値ρｎを順次バツフア２に書込むもの
である。

第４図は第２図構成におけるヒストグラム作成部３の構
成図である。

図中、30はアドレス生成部であり、バツフア２からのア
ドレスｎと関数値ρｎをヒストグラムメモリ７のアドレ
スとして生成し、ヒストグラムメモリ７をアクセスする
もの、31はインクリメント回路であり、ヒストグラムメ
モリ７からアドレス生成部30のアドレスによつて読出さ
れた８ビツトのデータに１加算し、ヒストグラムメモリ
７へデータとして出力するもの、32はメモリコントロー
ラであり、アドレスクロツクに応じてヒストグラムメモ
リ７のリード／ライトを制御するとともにインクリメン
ト回路31の動作を制御するものである。

従つて、ヒストグラム作成部３は、ヒストグラムメモリ
７をアドレスｎと関数値ρｎとをアドレスとして対応す
る位置のデータを読出し、このデータに“1"を加算して
再び同一位置に書込みを行なうよう構成されており、ヒ
ストグラムメモリ７は８ビツトのデータが縦512,横512
コ収容できるメモリで構成されている。

（ｂ）一実施例の動作の説明 第５図は第３図構成によるρ計算動作の説明図、第６図
は第４図構成によるヒストグラム作成動作の説明図、第
７図は全体動作説明図である。

テレビカメラ４から入力された原画像（濃淡画像）は、
輪郭抽出部５に入力され、輪郭抽出部５において周知の
如く輪郭点アドレス（xi,yi）が抽出され、速度調整バ
ツフア６に出力される。速度調整バツフア６はフアース
トイン・フアーストアウトメモリで構成され抽出された
輪郭点アドレス（xi,yi）を順次格納する。一方、関数
値計算部１は速度調整バツフア６から輪郭点アドレス
（xi,yi）を受け、第５図の如く動作する。

先づ、クロツクの周期Ｔを乗算器14,15の乗算時間に合
わせて設定する。これは同一素子技術の条件のもとで
は、第３図構成のものでは、乗算時間が加算時間、テー
ブルアクセス時間より長いため、最大の乗算時間に合わ
せて設定する。

そして、ハフ変換のパラメータθの０〜πを512等分し
て各関数値ρｎを計算する。

従つて、第（１）式は、 に変形され、cosθテーブル11,sinθテーブル12にはア
ドレスｎに対応して512個のcosθ,sinθ値が格納されて
いる。

第５図に示す如く、バツフア６から輪郭点アドレス（x
i,yi）を受けると、クロツクによつてレジスタ13a,13c
にこれらがセツトされるとともに、cosθテーブル11か
らcosθ_０が、sinθテーブル12からsinθ_０が各々レジ
スタ13b,13dにセツトされる。

従つて各乗算器14,15は、（xi・cosθ_０），（yi・sin
θ_０）を演算し、次のクロツクで乗算出力は出力レジス
タ16a,16bにセツトされる。

更にレジスタ16a,16bにセツトされた乗算出力は加算器1
7で加算され、更に次のクロツクで書込レジスタ18にセ
ツトされる。

従つて３クロツクで、（xi,yi）に対するアドレス“0"
の関数値ρ_０が得られる。

このρ計算部１はアドレスカウンタの歩進により順次直
列的に演算が行なわれるので、クロツク毎に関数値がρ
_０，ρ_１，ρ_２…ρ₅₁₁と出力され、従つて１つの輪郭
点アドレス（xi,yi）に対し一連の512個の関数値を発生
する時間は（512＋３）×Ｔで済む。この計算された関
数値ρｎは第７図に示す様に、データバツフア２にアド
レスｎと共に格納されていく。一方、ヒストグラム作成
部３では、アドレスクロツクの到来毎にアドレス生成部
30よりデータバツフア２のn,ρｎが読出され、これをア
ドレスとしてヒストグラムメモリ７をアクセスする。メ
モリコントローラ32はこのアドレスクロツクに応じて第
６図のライトネーブル信号▲▼を発生するから、ヒ
ストグラムメモリ７からは第６図のメモリI/Oデータの
如くアクセスされたアドレスのデータDnが先づ読出され
インクリメント回路31へ与えられ、インクリメント回路
31で“1"加算されて、ライトネーブル信号▲▼のロ
ーレベルによつてインクリメント回路31の出力データD
_n+1が同一アドレスに書込まれる。

従つて、第７図の如く、ρ計算部１で512個のρｎが計
算された後、ヒストグラム作成部３で512個のρｎがヒ
ストグラムメモリ７に書込まれる。この書込みの間にρ
計算部１は、次の輪郭点座標（x1,y1）に対するρｎの
計算が行なわれ、従つて関数値計算とヒストグラム作成
が並列で動作する。

このため、従来のヒストグラム作成までに要する時間は
ρ計算時間Ｔρとヒストグラム作成時間Tnの和であるの
に対し、本発明ではＴρとTnの大きい方の時間で済むこ
とになる。

又、ρ計算部１の計算時間も、大幅に短縮される。即
ち、従来の計算時間は、テーブルアクセス２回、乗算２
回、加算１回の５回であり、乗算時間を加算、テーブル
アクセス時間Taの２倍と設定すると、512×７×Taとな
り、本発明では前述の如く515×２×Taのため、3.5倍早
くなる。

このようにヒストグラムメモリ７にヒストグラムが書込
まれると、ホストプロセツサ８はヒストグラムメモリ７
の内容を読出し、その極大値のアドレスを交点として探
索し、極大値のアドレスによつて前述の線分の角度
θ_０，距離ρ_０を再生抽出する。

（ｃ）他の実施例の説明 前述の実施例は写像関数としてハフ変換関数を例に説明
したが他の変換関数を用いることもできる。

以上本発明の実施例により説明したが、本発明は本発明
の主旨に従い種々の変形が可能であり、本発明からこれ
らを排除するものではない。

〔発明の効果〕

以上説明した様に、本発明によれば、写像関数の計算
と、ヒストグラムの作成が並列に行なえるため、線分抽
出におけるヒストグラム作成に要する時間を短縮でも、
高速な線分抽出が可能となるという効果を奏する。特に
高精度の検出を行なうため、多数の写像関数値を発生す
る場合にその効果が大きく、線分抽出処理の高速化に寄
与するところが大きい。

【図面の簡単な説明】

第１図は本発明の原理説明図、 第２図は本発明の一実施例構成図、 第３図は第２図構成の関数値計算部の内部構成図、 第４図は第２図構成のヒストグラム作成部の構成図、 第５図は本発明の一実施例による関数値計算動作説明
図、 第６図は本発明の一実施例によるヒストグラム作成動作
説明図、 第７図は本発明の一実施例全体動作説明図、 第８図はハフ変換の説明図、 第９図は従来技術の説明図である。 図中、１……関数値計算部、２……バツフア、３……ヒ
ストグラム作成部、５……輪郭抽出部、７……ヒストグ
ラムメモリ。

Claims (1)

【特許請求の範囲】
1. 【請求項１】画像の輪郭点座標に対し写像関数値を計算
   し、該計算された写像関数値に従ってヒストグラムを作
   成して該ヒストグラムから該輪郭点座標の示す線分情報
   を抽出する線分抽出装置において、 該輪郭点座標から写像関数値を計算する写像関数値計算
   部と、 該写像関数値計算部で計算された写像関数値を記憶する
   バツフアと、 該バツフアの写像関数値からヒストグラムメモリにヒス
   トグラムを作成するヒストグラム作成部とを含み、 該写像関数値計算部による写像関数値計算動作と該ヒス
   トグラム作成部によるヒストグラム作成動作とを並列に
   行うことを 特徴とする線分抽出装置。