JPS6277689A - 一般化ハフ変換回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、ディジタル画像処理において、ＩＩ淡両画像
中から任意の領域を抽出する一般化へフ（Ｈｏｕａｈ）
変挟回路に１３ＬＴる。

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

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

先ず、第１０図の参照対象ＩＭ内に参照点くＸｃ＋”ｉ
／ｃ）を設定する。次に、参照対象ＩＭの境界の各点（
Ｘ、　Ｓ／＞に関して、次のことを行う。

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

■　点（ｘ、ｙ）と参照点（Ｘｃ　＊　Ｖｃ　）とのＸ
軸方向、ｙ軸方向の距離ΔｘＱＸｃ−Ｘ。

Δｙ会Ｖｃ−Ｖを求める。

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

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

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

即ち、第１２図に示すイメージ空間の各点（Ｘ。

ｙ）について次のことを行う。

■　点（ｘ、ｙ）の？１１度の変化（ｇｒａｄｉｅｎｔ
）の方向φｉ′を求め、定められたレベルで量子化した
φｉを得る。

■　Ｒテーブル中のφ：の欄にある全ての（△ＸＩ＋　
ΔＹｓ）”（Δｘｎ、ΔＶｎ）に対して、次のことを行
う。

■−１ｘ（、蟲Ｘ＋Δｘｊ　　　（ｊ−１〜ｎ）ｙｃ公
ｙ＋Δｙｊ　　　を計算する。

■−２パラメータ空間の（Ｘｃ　＊　Ｖｃ　）上の値を
＋１する。

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

続いて、第１３図に示すパラメータ空間を探索し、極大
点（ＸＣ、Ｖｃ　）・・・（Ｘｃ、Ｖｃ）を求める。こ
れらがイメージ空間上の参照点の位置になる。

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

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

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

Δｙ用Ｒテーブルから読み出した信号Δｘ、Δｙを入力
し、Ｘ＋Δｘ、ｙ＋△ｙを演算する演算器と、この演算
器からの演算結果Ｘ＋△ｘ、ｙ＋△ｙがアドレス信号と
して与えられるパラメータカウンタ列と、前記勾配大き
さ２値画像領域からの信号を入力し、前記各回路に制御
信号を与える制御回路とを備えたことを特徴とするもの
である。

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

第１図は、本発明の一実施例の構成ブロック図である。

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

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

第２図に示すように濃淡画像Ａ（原画像）の勾配画像は
、勾配の大きさγを表わす画像と、勾配の方向φを表わ
す画像からなる。即ち、点（Ｘ。

ｙ）の濃度をＡ　（Ｘ、ｌとすると、点（ｘ、ｙ）にお
ける勾配ｇｒａｄＡ　（ｘ、　Ｖ）は、（ａＡ　（Ｘ。

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

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

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

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

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

■　リファレンスカウンタ列４に全て“Ｏ１１をセット
する。

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

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

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

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

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

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

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

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

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

■　アドレスカウンタ２が勾配画像メモリ３の全域を走
査し終えると動作は終了し、Ｒテーブル６．７へ全ての
データが書き込まれる。

（イメージ空間からパラメータ空間への変換時）この時
の信号の流れと、制御信号を第６図に示す。この回路に
おいて、初期設定は、次のようにして行われる。

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

■　パラメータカウンタ列１０に全て“Ｏ″をセットす
る。

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

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

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

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

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

■　ダウンカウンタ５の（直が０″になるまで、以下の
■−１〜■−４の処理を行う。

■−１Δｘ用Ｒテーブル７と△ｙ用Ｒテーブル６のφと
ダウンカウンタ５とで指さ れる番所のデータ△Ｘ、Δｙを読み出 す。

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

■−２演算器８において、ここに入力されているアドレ
スカウンタ２からの信号Ｘ。

ｙ１バススイッチ９からのＲテーブル ６．７からの読み出しデータΔｘ、Δ ｙに対して、Ｘ＋Δｘ、ｙ＋Δｙをそ れぞれ計算する ■−３パラメータカウンタ列１０のＸ＋Δｘ。

ｙ＋Δｙで指されるカウンタの倍を＋ １する。

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

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

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

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

第９図は、この第２の′ａ尊振器１１詳細な構成ブロッ
ク図である。この回路において、ＭＵＬは何れも掛算器
であり、ＡＤＤは加算器、ＳＵＢは減算器で、加算器へ
ＤＤからは大きさＳと方向θを考慮した信号Δ×′が出
力され、又、減算器ＳＵＢからは、大きさＳと方向θを
考慮した信号△ｙ′が出力される。

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

Ｒテーブル作成時の動作は第１図と同様である。

（イメージ空間から、パラメータ空間への変換時）（追
加する初期設定〉 ■　考える参照対象の拡大・縮小の係数を、スケール関
数テーブル１４に設定すると共に、その係数の個数をＮ
ｓバッファ１２に設定する。

■　考える参照対象の回転角θに対するｓｉｎθ。

ＣＯＳθの１直を、ｓｉｎ　、　ｃｏｓ関数テーブル１
７に設定すると共に、そのθの個数をＮｏバッファ１５
に設定する。

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

■　ダウンカウンタ５の値が０′°になるまで、以下の
■づ〜■−４の処理を行う。

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

■−２ＮＳバッファ１２の値をＳカウンタ１３に格納す
る。Ｓカウンタ１３の値が “０″になるまで（イ）〜（ハ）の処 理を行う。

（イ）スケール関数テーブル１４のＳノＪウンタ１３が
指す（「ｌを、第２の演算器１１の入力にセットする。

（ロ）Ｎｏバッファ１５の（ｆｆｊをθカウンタ１６に
格納する。θカウンタの値が°゛０″になるまで、（ロ
ー１）〜（ロー４〉の処理を行う。

（ロー１）　ｓｉｎ　、　ｃｏｓ関数テーブル１７のθ
カウンタ１６が指す値＜　ｓｉｎθ、　ＣＯＳθ）を第
２の演Ｑ器２の入力に設定覆 る。

（ロー２）第２の演粋器、第１の演算器で所定の演算を
行い、Ｘｃ、Ｖｃを求める。

（ロー３）パラメータカウンタ列１０のＸ（。

Ｖｃ、Ｓ、θに対応するカウンタの合 価を＋１する。

（ロー４）θカウンタ１６の値を−１する。

〈ハ）Ｓカウンタ１３の値を−１する。

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

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

【図面の簡単な説明】

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

Claims (1)

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