JPH0516625B2 - - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、デイジタル画像処理において、濃淡
画像の中から任意の領域を抽出する一般化ハフ
（Hough）変換回路に関し、更に詳しくは、一般
化ハフ変換の一部を変更し、２値画像から任意の
曲線を抽出することができるようにした一般化ハ
フ変換回路に関する。

（従来の技術） デイジタル画像処理において、濃淡画像中から
任意の領域を抽出する手法として、一般化ハフ変
換があり、これはコンピユータを用いソフトウエ
アによつて処理される。

（発明が解決しようとする問題点） しかしながら、これまで公知の一般化ホフ変換
の手法を、２値画像から任意の曲線を抽出する場
合に適用しようとする次のような問題点がある。

濃淡画像に一般化ハフ変換を適用する場合、
各点ｘ，ｙの濃度Ｚ（ｘ、ｙ）の変化の方向の
情報を利用している。即ち、第５図に示す濃淡
画像において、ベクトル（∂Z／∂x、∂Z／∂y）
の方向φを利用している。しかしながら、第６
図に示す２値画像においては、これに対応する
方向φ′を見つける簡便な手法がない。換言すれ
ば、２値画像に対し、変化の方向（△ｙ／△
ｘ）を精度よく求めるオペレータがない。従つ
て、２値画像から任意の曲線を抽出する問題
に、直接一般化ハフ変換は適用できない。

ハフ変換をコンピユータを用い、ソフトウエ
アによつて処理しようとすると、処理時間が長
く、実用的でない。

本発明はこのような問題点に鑑みてなされたも
ので、その目的は、一般化ハフ変換の一部を変更
し、２値画像から任意の曲線を高速で抽出するこ
のできる一般化ハフ変換回路を実現することにあ
る。

（問題点を解決するための手段） 前記した問題点を解決する本発明は、イメージ
空間として機能する２値画像メモリと、この２値
画像メモリにアドレス信号を与える第１のアドレ
スカウンタと、パラメータ・ポイント・スプレツ
ド・フアンクシヨン（ppsf）の個数Nppsfが初期
設定されるバツフアと、このバツフアからの個数
Nppsfがセツトされる第２のアドレスカウンタ
と、この第２のアドレスカウンタからの信号がそ
れぞれアドレス信号として与えられ、予め参照対
象、参照点から計算された原点に対するppsfの
ｘ、ｙ座標がそれぞれ格納されているｘ−ppsfテ
ーブル及びｙ−ppsfテーブルと、前記第１のアド
レスカウンタからの信号ｘ、ｙと前記ｘ−ppsfテ
ーブル、ｙ−ppsfテーブルからそれぞれ読み出さ
れたデータ△ｘ、△ｙを入力し所定の演算を行う
演算器と、この演算器からの演算結果x_c、y_cがア
ドレス信号として与えられるパラメータカウンタ
列と、前記２値画像メモリからのデータ及び前記
第２のアドレスカウンタからの“０”検出信号を
入力し、前記各回路に制御信号を与える制御回路
とを備えたことを特徴とするものである。

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

本発明の回路は、形が解析的な形（パラメー
タ）として表現できているとは限らないが、２値
データとしてそれを表現できている曲線（参照対
象）を、雑音が含まれた他の２値画像（イメージ
空間と呼ぶ）から検出し、その位置を知るように
したものであつて、はじめに、処理手順について
説明する。

（手順） (1) パラメータ・ポイント・スプレツド・フアン
クシヨン：Parameter Point Spread
Function（以下：ppsfと略称する）テーブルの
作成 参照対象に対して参照点（x_c、y_c）を設定
する。

この参照点に対する、原点（０、０）の
ppsfテーブルを作成する。

イメージ空間上の点ｘ，ｙのppsfの値は、点
ｘ，ｙを通ることのできる全ての参照対象に対
する参照点の集合である。例えば、第７図に示
すように、参照対象が円で参照点が円の中心で
ある場合を考える。この時、第８図に示すイメ
ージ空間の原点を通る（含む）全ての参照対象
を考える。ここで実線の円が原点を含む参照対
象であり、破線の円がその参照点の軌跡、即ち
原点のppsfの値である。第９図は、この参照点
の軌跡を取り出した図であり、（x₁、y₁）、（x₂、
y₂）…（xn、yn）が原点に対するppsfの値で
ある。

これを第１０図に示すようにテーブル化した
ものがppsfテーブルである。

第１１図乃至第１４図は、参照対象が正三角
形、参照点はその正三角形の重心の場合の説明
図であり、第１１図は参照対象と参照点、第１
２図はイメージ空間において、原点を通る参照
対象、第１３図は原点のppsf、第１４図はこれ
をテーブル化した図をそれぞれ示している。

以上の説明から明らかなように、点（ｘ、
ｙ）のppsfの値は、原点（０、０）のppsfの値
を、（ｘ、ｙ）平行移動したものである。従つ
て、原点のppsfの値は次のように表わされる。

｛（Ｘ、Ｙ）｜Ｘ△＝x_c−x′、Ｙ△＝y_c−y′ ここで、（x_c、y_c）は参照点 （x′、y′）は参照点上の任意の点） 又、点ｘ，ｙのppsfの値は次のように表わさ
れる。

｛（Ｘ、Ｙ）｜Ｘ△＝x_c−x′＋ｘ、 Ｙ△＝y_c−y′＋ｙ｝ (2) イメージ空間からパラメータ空間への変換第
１５図に示すようなイメージ空間（２値画像）
の“１”である各点ｘ，ｙについて、次のこと
を行う。

ppsfテーブル上の値（x_i、y_i）に対し、
（xⁱ _c、yⁱ _c）△＝（ｘ＋x_i、ｙ＋y_i）を全て求め
る。

ここで、（xⁱ _c、yⁱ _c）（ｉ＝１〜ｎ）は、点
ｘ，ｙのppsfの値がある。即ち、イメージ空
間上の点ｘ，ｙは、（xⁱ _c、yⁱ _c）（ｉ＝１〜ｎ）
を参照点とする参照対象の何れかのものの上
の点になる可能性があるということである。

パラメータ空間で、xⁱ _c，yⁱ _cの点を＋１す
る。尚、パラメータ空間の各点の初期値は
“０”である。

(3) パラメータ空間の探索 第１６図に示すパラメータ空間を探索し、極
大点（x¹ _c、y¹ _c）、…（xⁿ _c、yⁿ _c）を求める。これ
らがイメージ空間上の参照点の位置になる。

本発明は、上述した手順のうちで、イメージ
空間からパラメータ空間への変換を行う部分を
ハードウエア化し、２値画像からの曲線抽出が
行えるようにしている。

第１図は、本発明の一実施例の構成ブロツク
図である。図において、１は全体回路を統括、
制御するタイミング及び制御回路（以下、これ
を単に制御回路と略称する）、２はこの制御回
路１からカウントアツプ信号及びクリア信号が
与えられる第１のアドレスカウンタ、３はアド
レスカウンタ２からのアドレス信号が与えられ
る２値画像メモリで、イメージ空間として機能
するもので、ここから読み出されたデータは、
制御回路１に印加されている。４はバツフア、
５はバツフア４からのデータがセツトされる第
２のアドレスカウンタで、制御回路１からロー
ド、カウントダウンの制御信号が与えられ、
又、ここからは、“０”検出のための信号が制
御回路に印加される。

６はｘ−ppsfテーブル、７はｙ−ppsfテーブ
ルで、何れもメモリが用いられており、第２の
アドレスカウンタ５からそれぞれアドレス信号
が与えられている。８はｘ−ppsfテーブル６か
らのデータ△ｘと、第１のアドレスカウンタ２
からの信号ｘとを入力する第１の演算器、９は
ｙ−ppsfテーブル７からのデータ△ｙと、第１
のアドレスカウンタ２からの信号ｙとを入力す
る第２の演算器、１０は第１、第２の演算器
８，９からの演算結果x_c′、y_c′をアドレス信号
として入力するパラメータカウンタ列で、パラ
メータ空間として機能するものである。但し、
△ｘ、△ｙは原点に関するppsfの値であり、
x_c′、y_c′は（ｘ、ｙ）に関するppsfの値であ
る。

尚、このパラメータ空間としてのパラメータ
カウンタ列１０は、これに代えて、ランダム・
アクセス・メモリ（RAM）を用いてもよい。

このように構成した回路の動作を説明すれば、
以下の通りである。

はじめに、ここには図示していないコンピユー
タのプログラムによつて、参照対象、参照点から
原点に対するppsfの値を計算し、そのｘ、ｙ座標
を各々ｘ−ppsfテーブル６と、ｙ−ppsfテーブル
７に、それぞれ初期設定すると共に、点の個数
Nppsfをバツフア４にセツトする。この初期設定
状態では、第１のアドレスカウンタ２は、イメー
ジ空間として機能する２値画像メモリ３の最初の
アドレスを指している。又、パラメータカウンタ
列１０は、全て“０”が入つている。以上の初期
設定後に、次のような処理動作を行う。

制御回路１は、２値画像メモリ３からの画像
データが“１”になるまで、第１のアドレスカ
ウンタ２をインクリメントする。

ppsfの個数Nppsfをバツフア４から読み出し
て、第２のアドレスカウンタ５にセツトする。

第１、第２の演算器８，９で、ｘ−ppsfテー
ブル６及びｙ−ppsfテーブル７からそれぞれ読
み出されたデータ△ｘ、△ｙ、アドレスカウン
タ２からの信号ｘ、ｙとをそれぞれ加算し、原
点用のppsfの値を、サンプルのｘ、ｙ座標用に
ずらす。

第１、第２の演算器８，９からの演算結果
x_c′、y_c′で指されるパラメータカウンタ列１０
内のカウンタをインクリメントする。

第２のアドレスカウンタ５が“０”ならば、
第１のアドレスカウンタ２を＋１し、処理動作
のへ戻る。そうでなければ、第２のアドレス
カウンタ５を−１し、処理動作のへ戻る。

第１のアドレスカウンタ２が２値画像メモリ
全域を走査し終ると動作は終了する。この後
に、パラメータ空間を探索し、極大点（x¹ _c、
y¹ _c）…（xⁿ _c、yⁿ _c）を求めることになるが、この
手法は公知の技術によつて行われる。

第２図は、本発明の他の実施例を示す構成ブロ
ツク図である。この実施例においては、参照対象
が位置だけでなく、大きさＳ、方向θも未知の場
合も、ハフ変換できるようにしたものである。

図において、１１はバツフア４から読み出され
る参照対象の拡大・縮小の係数の個数Nsが設定
されるＳカウンタ、１２は参照対象の拡大・縮小
の係数を格納したスケール関数テーブル、１３は
バツフア４から読み出される参照対象の回転角θ
の個数Nθが設定されるθカウンタ、１４は参照
対象の回転角θに対するsinθ、cosθの値を格納し
たsin、cos関数テーブルである。１５，１６は係
数Ｓを乗算する乗算器、１７はこの乗算器からの
信号ｘ、ｙと、sin、cos関数テーブル１４からの
信号sinθ、cosθを入力する回転部演算回路で、こ
こからの演算出力Ｘ、Ｙは、第１、第２の演算器
８，９に印加されている。この実施例において
は、乗算器１５，１６、回転部演算回路１７を、
ｘ−ppsfテーブル６、ｙ−ppsfテーブル７と、第
１、第２の演算器８，９との間に設けた点が第１
図実施例と異なつている。

第３図は、第２図における回転演算回路１７の
詳細な構成ブロツク図である。この回路におい
て、MULは何れも掛算器、SUBは減算器、
ADDは加算器を示しており、減算器SUBの出力
Ｘ、加算器ADDの出力Ｙは、次式で表わされる。

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

（追加する初期設定） 考える参照対象の拡大・縮小の係数をスケー
ル関数テーブル１２に、その係数の個数Nsを
バツフア４にそれぞれ設定する。

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

（動作の変更点） 前記第１図回路の動作説明における項につい
て、次のように変更する。

ｘ−ppsfテーブル６及びｙ−ppsfテーブル７
の第２のアドレスカウンタ５で指されるデータ
△ｘ、△ｙを取り出すと共に、バツフア４の係
数の個性NsをＳカウンタ１１にロード（load）
する。

Ｓカウンタ１１の値が“０”になるまで、次
の−１〜−３の処理を行う。

‐１ スケール関数テーブル１２のＳカウンタ
１１が指す値を乗算器１５，１６にセツトす
る。

‐２ バツフア４の回転角θの個数Nθを、θ
カウンタ１３にロードする。

θカウンタ１３の値が“０”になるまで、
次の(イ)〜(ニ)の処理を行う。

(イ) sin、cos関数テーブル１４のθカウンタ
１３が指す値（sinθ、cosθ）を回転演算回
路１７にセツトする。

(ロ) 各演算回路で、所定の演算を行い、（x_c、
y_c）を求める。

(ハ) パラメータカウンタ列１０に、Ｓカウン
タ１１、θカウンタ１３、各加算器８，９
から与えられる信号θ、Ｓ、x_c、y_cに対応
するカウンタの値を＋１する。

(ニ) θカウンタ１１の値を−１する。

‐３ Ｓカウンタ１１の値を−１する。

第４図は、第２図の実施例において、大き
さＳ、方向θを変更する部分を乗算器で構成
する代りに、この機能をｘ−ppsfテーブル６
及びｙ−ppsfテーブル７に持たせるようにし
た場合の要部の構成ブロツク図である。

ここでは、各テーブル６，７のサイズは、
それぞれNθxNs倍になつている。

（発明の効果） 以上説明したように、本発明によれば、主要な
部分をハードウエアによつて構成することによ
り、２値画像から任意の曲線を高速で抽出するこ
とのできる一般化ハフ変換回路を実現することが
できる。

【図面の簡単な説明】

第１図及び第２図は本発明回路の一例を示す構
成ブロツク図、第３図は第２図回路における回転
部演算回路の詳細な構成ブロツク図、第４図は本
発明回路の他の例を示す要部の構成ブロツク図、
第５図は濃淡画像の説明図、第６図は２値画像の
説明図、第７図乃至第１６図は本発明回路による
ハフ変換の原理を説明するための図である。 １……制御回路、２……アドレスカウンタ、３
……２値画像メモリ、４……バツフア、５……ア
ドレスカウンタ、６……ｘ−ppsfテーブル、７…
…ｙ−ppsfテーブル、８，９……加算器、１０…
…パラメータカウンタ列。

Claims (1)

1. 【特許請求の範囲】 １ イメージ空間として機能する２値画像メモリ
   と、 この２値画像メモリにアドレス信号を与える第
   １のアドレスカウンタと、イメージ空間上のある
   点（ｘ、ｙ）を通ることのできるすべての参照対
   象に対する参照点の集合であるパラメータ・ポイ
   ント・スプレツド・フアンクシヨン（ppsf）の個
   数Nppsfが初期設定されるバツフアと、 このバツフアからの個数Nppsfがセツトされる
   第２のアドレスカウンタと、 この第２のアドレスカウンタからの信号がそれ
   ぞれアドレス信号として与えられ、予め参照対
   象、参照点から計算された原点に対するppsfの
   ｘ、ｙ座標がそれぞれ格納されているｘ−ppsfテ
   ーブル及びｙ−ppsfテーブルと、 前記第１のアドレスカウンタからの信号ｘ、ｙ
   と前記ｘ−ppsfテーブル、ｙ−ppsfテーブルから
   それぞれ読み出されたデータ△ｘ、△ｙを入力し
   所定の演算を行う演算器と、 この演算器からの演算結果xc、ycがアドレス
   信号として与えられるパラメータカウンタ列と、 前記２値画像メモリからのデータ及び前記第２
   のアドレスカウンタからの“０”検出信号を入力
   し、前記各回路に制御信号を与える制御回路 とを備えた一般化ハフ変換回路。