JPH0516624B2 - - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、デイジタル画像処理において、濃淡
画像の中から任意の領域を抽出する一般化ハフ
（Hough）変換回路に関する。

（従来の技術） 形は既知で、シルエツトとして画像に表現でき
ているが、解析的な形（パラメータ）で表現でき
ていない対象（これを参照対象と呼ぶ）を、濃淡
画像（イメージ空間と呼ぶ）からその対象を検出
し、その位置（向き、大きさも可変にして扱うこ
とができるが、ここでは向き、大きさは固定して
いるものとする）を知るのが、一般化ハフ変換で
ある。

従来、このようなハフ変換は、コンピユータを
用い、ソフトウエアによつて処理されており、そ
の手順の原理について第１０図乃至第１３図を用
いて以下に説明する。

先ず、第１０図の参照対象IM内に参照点（x_c，
y_c）を設定する。次に、参照対象IMの境界の各
点（ｘ，ｙ）に関して、次のことを行う。

参照対象の境界の法線方向の角度φi′を求め、
定められたレベで量子化したφiを得る。

点（ｘ，ｙ）と参照点（x_c，y_c）とのｘ軸方
向、ｙ軸方向の距離Δx△＝x_c−ｘ、Δy△＝y_c−ｙ
を求める。

第１１図に示すＲテーブル中のφに対応する
欄に、（Δx，Δy）を書き加える。

以上によりＲテーブルを作成する。

続いて、イメージ空間からパラメータ空間への
変換を行う（ここで、イメージ空間内で、参照対
象は、背景より明るいか又は暗いことが分つてい
るものとする）。

即ち、第１２図に示すイメージ空間の各点
（ｘ，ｙ）について次のことを行う。

点（ｘ，ｙ）の濃度の変化（gradient）の方
向φi′を求め、定められたレベルで量子化した
φiを得る。

Ｒテーブル中のφiの欄にある全ての（Δx₁，
Δy₁）…（Δxn，Δyn）に対して、次のことを
行う。

−１ x_c△＝ｘ＋Δxj（ｊ＝１〜ｎ） y_c△＝ｙ＋Δyjを計算する。

−２ パラメータ空間の（x_c，y_c）上の値を＋
１とする。

尚、パラメータ空間の各点の初期値は“０”で
ある。

続いて、第１３図に示すパラメータ空間を探索
し、極大点（x¹ _c，y¹ _c）…（x^m _c，y^m _c）を求める。
これらがイメージ空間上の参照点の位置になる。

（発明が解決しようとする問題点） このような手順に従つて処理されるハフ変換
は、ノイズに強いという特徴があるが、処理時間
が長く、実用的でないという問題点がある。

本発明はこのような問題点に鑑みてなされたも
ので、その目的は、一般化ハフ変換を高速で行え
る回路をハードウエアによつて実現することにあ
る。

（問題点を解決するための手段） 前記した問題点を解決する本発明は、Ｒテーブ
ル作成時に参照対象勾配画像ブロツクとなり、イ
メージ空間からパラメータ空間への変換時にイメ
ージ空間勾配画像ブロツクとなるものであつて、
勾配の大きさを表わす２値画像を格納する領域と
勾配の方向を表わす濃淡画像を格納する領域とか
らなる勾配画像メモリと、この勾配画像メモリに
アドレス信号を与えるアドレスカウンタと、前記
勾配方向濃淡画像領域からのデータがアドレス信
号として与えられるリフアレンスカウンタ列と、
このリフアレンスカウンタ列からのデータを入力
するダウンカウンタと、このダウンカウンタから
の信号及び前記勾配方向濃淡画像領域からのデー
タがそれぞれアドレス信号として与えられるΔx
用Ｒテーブル及びΔy用Ｒテーブルと、Ｒテーブ
ル作成時において、前記アドレスカウンタからの
信号ｘ，ｙと参照点の座標信号x_c，y_cを入力し、
ｘ−x_c，ｙ−y_cをそれぞれ演算し、この演算結果
を前記Δx用Ｒテーブル、Δy用Ｒテーブルに書き
込むと共に、イメージ空間からパラメータ空間へ
の変換時において、前記アドレスカウンタからの
信号ｘ，ｙと前記Δx用Ｒテーブル、Δy用Ｒテー
ブルから読み出した信号Δx，Δyを入力し、ｘ＋
Δx，ｙ＋Δyを演算する演算器と、この演算器か
らの演算結果ｘ＋Δx，ｙ＋Δyがアドレス信号と
して与えられるパラメータカウンタ列と、前記勾
配大きさ２値画像領域からの信号を入力し、前記
各回路に制御信号を与える制御回路とを備えたこ
とを特徴とするものである。

（実施例） 以下、図面を用いて本発明の実施例を詳細に説
明する。

第１図は、本発明の一実施例の構成ブロツク図
である。図において、１は全体回路を統括、制御
するタイミング及び制御回路（以下これを単に制
御回路と略称する）、２はこの制御回路１からカ
ウントアツプ信号及びクリア信号が与えられるア
ドレスカウンタ、３はアドレスカウンタ２からの
アドレス信号が印加される勾配画像メモリで、Ｒ
テーブル作成時には参照対象勾配画像ブロツクと
なり、又、イメージ空間からパラメータ空間への
変換時には、イメージ空間勾配画像ブロツクとな
る。この勾配画像メモリ３は、勾配の大きさを表
わす２値画像を格納する領域３１と、勾配の方向
を表わす濃淡画像を格納する領域３２とからな
る。

ここで、勾配画像の定義をすれば以下の通りで
ある。

第２図に示すように濃淡画像Ａ（原画像）の勾
配画像は、勾配の大きさγを表わす画像と、勾配
の方向φを表わす画像からなる。即ち、点（ｘ，
ｙ）の濃度をＡ（ｘ，ｙ）とすると、点（ｘ，ｙ）
における勾配gradA（ｘ，ｙ）は、（∂A（ｘ，
ｙ）／∂x，∂A（ｘ，ｙ）／∂y）になる。この勾
配の大きさγを２値化したものが、勾配の大きさ
を表わす２値画像であり、勾配の方向φを濃淡値
で表わしたものが、勾配の方向を表わす濃淡画像
である。第３図は、以上の関係を図で説明したも
のである。第１図に戻り、４は勾配画像メモリ３
の勾配方向濃淡画像領域３２からの勾配の方向を
表わすデータφがアドレス信号として与えられる
フアレンスカウンタ列で、制御回路１からカウン
トアツプ信号が印加される。５はリフアレンスカ
ウンタ列４からのデータが与えられるダウンカウ
ンタ、６はΔy用Ｒテーブル、７はΔx用Ｒテーブ
ルで、何れもメモリが用いられており、勾配方向
濃淡画像領域３２からの信号φがアドレス信号と
して与えられると共に、ダウンカウンタ５からの
データがアドレス信号として与えられる。

８はアドレスカウンタ２からの信号と、バスス
イツチ９で切換えられて印加される信号との減算
又は加算を行う演算器、１０は演算器８からの信
号がアドレス信号として与えられるパラメータカ
ウンタ列である。尚、このパラメータカウンタ
は、ランダム・アクセス・メモリ（RAM）を用
いてもよい。

このように構成した回路の動作を、Ｒテーブル
作成時と、イメージ空間からパラメータ空間への
変換時とに分けて説明すれば、以下の通りであ
る。

（Ｒテーブル作成時） この時の信号の流れと、制御信号を第４図に示
す。この回路において、初期設定は、次のように
して行われる。

参照対象画像の勾配画像を求め、そのデータ
を勾配画像メモリ（勾配画像ブロツク）３にセ
ツトする。

リフアレンスカウンタ列４に全て“０”をセ
ツトする。

アドレスカウンタ２は、勾配画像メモリ３の
最初のアドレスを指す。

以上の初期設定後に、次のような処理動作を行
う。

制御回路１は、勾配大きさ２値画像データが
“１”になるまで、アドレスカウンタ２をイン
クリメントする。

この時の勾配方向濃淡画像領域３２からのデ
ータφで指される、リフアレンスカウンタ列４
のデータを、ダウンカウンタ５に格納する。

データφで指されているリフアレンスカウン
タ列４の内容に＋１する。

演算器８で、ここに入力されているアドレス
カウンタ２からの信号ｘ，ｙ、バススイツチ９
からの参照点の座標信号x_c，y_cに対して、ｘ−
x_c，ｙ−y_cをそれぞれ計算する。

データφ及びダウンカウンタ５の内容で指さ
れるΔx用Ｒテーブル７とΔy用Ｒテーブル６の
所定番所に、バススイツチ９を介して印加され
る計算結果ｘ−x_cとｙ−y_cとをそれぞれ書き込
む。

第５図はΔy用Ｒテーブル６、Δx用Ｒテーブ
ル７へのデータの書き込みの様子を示す概念図
である。

アドレスカウンタ２の内容に＋１し、処理動
作のへ戻る。

アドレスカウンタ２が勾配画像メモリ３の全
域を走査し終えると動作は終了し、Ｒテーブル
６，７へ全てのデータが書き込まれる。（イメ
ージ空間からパラメータ空間への変換時）この
時の信号の流れと、制御信号を第６図に示す。
この回路において、初期設定は、次のようにし
て行われる。

イメージ空間画像の勾配画像を求め、そのデ
ータを勾配画像メモリ３にセツトする。

パラメータカウンタ列１０に全て“０”をセ
ツトする。

アドレスカウンタ２は、勾配画像の最初のア
ドレスを指す。

以上の初期制定後に、次のような処理動作を行
う。

制御回路１は、勾配大きさ２値画像データが
“１”になるまで、アドレスカウンタ２をイン
クリメントする。

勾配方向濃淡画像領域３２の、アドレスカウ
ンタ２の指す点の値φを取り出す。

リフアレンスカウンタ列４のφに相当するカ
ウンタの内容を、ダウンカウンタ５に格納す
る。

ダウンカウンタ５の値が“０”になるまで、
以下の−１〜−４の処理を行う。

−１ Δx用Ｒテーブル７とΔy用Ｒテーブル
６のφとダウンカウンタ５とで指される番所
のデータΔx，Δyを読み出す。

第７図はＲテーブル６，７からのこのデー
タの読み出しの様子を示す概念図である。

−２ 演算器８において、ここに入力されて
いるアドレスカウンタ２からの信号ｘ，ｙ、
バススイツチ９からのＲテーブル６，７から
の読み出しデータΔx，Δyに対して、ｘ＋
Δx，ｙ＋Δyをそれぞれ計算する。

−３ パラメータカウンタ列１０のｘ＋Δx，
ｙ＋Δyで指されるカウンタの倍を＋１する。

−４ ダウンカウンタ５を−１する。

アドレスカウンタ２を＋１し、処理動作の
へ戻る。

アドレスカウンタ２が勾配画像メモリ３の全
域を走査し終えると、動作は終了する。

第８図は、本発明の他の実施例の要部の構成ブ
ロツク図である。この実施例においては、参照対
象の位置だけでなく、大きさＳ、方向θも未知の
場合も、ハフ変換できるようにしたもので、演算
器８と、バススイツチ９との間に第２の演算器１
１を設けると共に、N_sバツフア１２、Ｓカウン
タ１３、スケール関数テーブル１４及びNθバツ
フア１５、θカウンタ１６、sin、cos関数テーブ
ル１７をそれぞれ設けている。Ｓカウンタ１３、
θカウンタ１６の出力はそれぞれパラメータカウ
ンタ列１０に与えられ、又、スケール関数テーブ
ル１４、sin、cos関数テーブル１７の出力は、そ
れぞれ第２の演算器１１に与えられている。

第９図は、この第２の演算器１１の詳細な構成
ブロツク図である。この回路において、MULは
何れも掛算器であり、ADDは加算器、SUBは減
算器で、加算器ADDからは大きさＳと方向θを
考慮した信号Δx′が出力され、又、減算器SUBか
らは、大きさＳと方向θを考慮した信号Δy′が出
力される。

このように構成した回路の動作を、第１図回路
の動作と重複する部分を除いて説明すれば、以下
の通りである。

Ｒテーブル作成時の動作は第１図と同様であ
る。（イメージ空間から、パラメータ空間への変
換時） （追加する初期設定） 考える参照対象の拡大・縮小の係数を、スケ
ール関数テーブル１４に設定すると共に、その
係数の個数をNsバツフア１２に設定する。

考える参照対象の回転角θに対するsinθ、
cosθの値を、sin、cos関数テーブル１７に設定
すると共に、そのθの個数をNθバツフア１５
に設定する。

（動作の変更点） 前記項のダウンカウンタ５の値が“０”にな
るまでの動作部分について、次のように変更す
る。

ダウンカウンタ５の値が“０”になるまで、
以下の−１〜−４の処理を行う。

−１ Δx，Δy用のＲテーブル７，６中のφ
と、ダウンカウンタ５とで指される番所のデ
ータΔx，Δyを読み出す。

−２ Nsバツフア１２の値をＳカウンタ１
３に格納する。Ｓカウンタ１３の値が“０”
になるまで(イ)〜(ハ)の処理を行う。

(イ) スケール関数テーブル１４のＳカウンタ１３
が指す値を、第２の演算器１１の入力にセツト
する。

(ロ) Nθバツフア１５の値をθカウンタ１６に格
納する。θカウンタの値が“０”になるまで、
（ロ−１）〜（ロ−４）の処理を行う。

(ロ‐1) sin、cos関数テーブル１７のθカウンタ
１６が指す値（sinθ、cosθ）を第２の演算器
２の入力に設定する。

(ロ‐2) 第２の演算器、第１の演算器で所定の
演算を行い、x_c，y_cを求める。

(ロ‐3) パラメータカウンタ列１０のx_c，y_c，
Ｓ，θに対応するカウンタの各値を＋１とす
る。

(ロ‐4) θカウンタ１６の値を−１する。

(ハ) Ｓカウンタ１３の値を−１する。

−３ ダウンカウンタ５を−１する。

（発明の効果） 以上説明したように、本発明によれば、一般化
ハフ変換をハードウエア化された回路によつて主
として行うようにしたもので、一般化ハフ変換を
高速で行うことができる。

【図面の簡単な説明】

第１図は本発明回路の一例を示す構成ブロツク
図、第２図及び第３図は勾配画像の定義を説明す
るための図、第４図はＲテーブル作成時における
信号の流れを示す図、第５図はこの時の各Ｒテー
ブルへのデータの書き込みの様子を示す概念図、
第６図はイメージ空間からパラメータ空間への変
換時における信号の流れを示す図、第７図はこの
時の各Ｒテーブルからのデータの読み出しの様子
を示す概念図、第８図は本発明回路の他の実施例
の要部構成ブロツク図、第９図は第８図における
第２の演算器の構成ブロツク図、第１０図乃至第
１３図は一般化ハフ変換の原理説明図である。 １……制御回路、２……アドレスカウンタ、３
……勾配画像メモリ、３１……勾配大きさ２値画
像領域、３２……勾配方向濃淡画像領域、４……
リフアレンスカウンタ列、５……ダウンカウン
タ、６……Δy用Ｒテーブル、７……Δx用Ｒテー
ブル、８……演算器、９……バススイツチ、１０
……パラメータカウンタ列。

Claims (1)

1. 【特許請求の範囲】 １ 参照対象の境界の各点に対し参照点からの位
   置（Δx，Δy）とその参照対象の境界の各点の境
   界に対する法線の角度が格納された参照テーブル
   を作成する時に参照対象勾配画像ブロツクとな
   り、イメージ空間からパラメータ空間への変換時
   にイメージ空間勾配画像ブロツクとなるものであ
   つて、 勾配の大きさを表わす２値画像を格納する領域
   と勾配の方向を表わす濃淡画像を格納する領域と
   からなる勾配画像メモリと、この勾配画像メモリ
   にアドレス信号を与えるアドレスカウンタと、 前記勾配方向濃淡画像領域からのデータがアド
   レス信号として与えられるリフアレンスカウンタ
   列と、このリフアレンスカウンタ列からのデータ
   を入力するダウンカウンタと、 このダウンカウンタからの信号及び前記勾配方
   向濃淡画像領域からのデータがそれぞれアドレス
   信号として与えられるΔx用参照テーブル及びΔy
   用参照テーブルと、 参照テーブル作成時において、前記アドレスカ
   ウンタからの信号ｘ，ｙと参照点の座標信号xc，
   ycを入力し、ｘ−xc，ｙ−ycをそれぞれ演算し、
   この演算結果を前記Δx参照テーブル、Δy用参照
   テーブルに書き込むと共に、イメージ空間からパ
   ラメータ空間への変換時において、前記アドレス
   カウンタからの信号ｘ，ｙと前記Δx用参照テー
   ブル、Δy用Ｒテーブルから読み出した信号Δx，
   Δyを入力し、ｘ＋Δx，ｙ＋Δyを演算する演算
   器と、 この演算器からの演算結果ｘ＋Δx，ｙ＋Δyが
   アドレス信号として与えられるパラメータカウン
   タ列と、前記勾配の大きさを表わす２値画像領域
   からの信号を入力し、前記各回路に制御信号を与
   える制御回路 とを備えた一般化ハフ変換回路。