JPH04287290A

JPH04287290A - ハフ変換画像処理装置

Info

Publication number: JPH04287290A
Application number: JP3303602A
Authority: JP
Inventors: Takao Saeki; 佐伯　孝夫
Original assignee: IMRA America Inc
Current assignee: IMRA America Inc
Priority date: 1990-11-20
Filing date: 1991-11-19
Publication date: 1992-10-12
Also published as: US5430810A

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は画像処理装置に関し、詳
しくはハフ変換を用いて画像認識を行うハフ変換画像処
理装置に関する。

【０００２】

【従来の技術】ハフ変換は画像像認識システムで幅広く
使用されている公知の技術である。たとえば、米国特許
Ｎｏ．４，８６８，７５２　（Ｆｕｊｉｉ　ｅｔ　ａｌ
）　は、ハフ変換を用いた境界線検出システムを有する
自動化作業車両制御システムを開示している。そこに開
示されているように、車両前方の作業領域の一部が撮像
され、各画素の明度情報から得られたエッジデータに従
って可変密度画像が作成される。

【０００３】像の暗い部分が明るい部分に変わる画像内
の遷移点が、境界線検出のために識別される。この境界
線は暗い未処理領域（たとえば、車両が芝刈り機の場合
には未処理の領域は刈られていない芝に相当する）と、
処理済領域（たとえば、刈られた芝）とを区別し、そし
て車両がこの境界線に沿って誘導される。ハフ変換は、
ノイズ（たとえば、未処理領域中の明るい部位や、処理
済領域中の暗い部位）が、車両が誘導されるべき境界線
として誤検出するのを回避するために採用される。

【０００４】すなわち、米国特許Ｎｏ．４，８６８，７
５２　の第１３図に示されるように、ハフ変換は、画像
内においてノイズがその周辺に存在するにもかかわらず
画像の境界線を示す直線を検出することを可能とする。ハフ変換は、デジタル化像の各画素の値（すなわち強さ
）に作用する。ハフ変換は、境界線条件の強さに相当す
る強さを持つ画素値の（Ｘ、Ｙ）座標点上に、軌跡曲線
を割り付ける。これらの画素についての軌跡曲線は、上
記各画素の（Ｘ、Ｙ）座標を極座標に変換することに相
当する。その後、画像内の境界線を表すのに用いる直線が、軌跡
を示す曲線が集中する極座標の一点を見出すことによっ
て得られる。

【０００５】多くの形式のハフ変換が様々なシステムで
用いられているけれども、この変換はソフトウエアで非
常によく実行され、かなりの処理時間を必要とする。ハ
フ変換をソフトウエアで実行すると、画像データの各フ
レーム毎に、一分以上の処理時間が通常かかる。更に処
理時間を短縮するために専用ハードウエアが用いられる
時でさえ、画像データ生成の典型的なフレーム速度（た
とえば毎秒３０フレームの画像データ）ではリアルタイ
ム処理はできなかった。

【０００６】たとえば、パターン分析および機械知能に
ついての「ハフ変換のためのリアルタイム処理装置（米
国電気電子学会会報１９８８年１月Ｖｏｌ．１０、Ｎｏ
．１）」のという題のハナハラらによる論文は、ハフ変
換を用いた専用の直線検出ハードウエアに関し、パラレ
ル演算およびパイプライン処理技術を利用する実験的な
モデルが記載されている。１０２４個の明暗画像につい
て、画像総処理時間はＴＴＬ回路を用いて０．７９秒と
記載されており、これには上記処理に用いたヒストグラ
ムメモリのクリア時間は含まれていない。

【０００７】パターン分析および機械知能についての「
再構築可能なＶＬＳＩに基づくモノリシックハフ変換プ
ロセッサ（米国電気電子学会会報１９８８年１月Ｖｏｌ
．１０、Ｎｏ．１）」と題するローデスらによる別の論
文では、再構築可能なＶＳＬＩ及びウェハスケール集積
技術を用いたハフ変換プロセッサの実行が説明されてお
り、特に、典型的なラインの抽出のための基礎的処理に
伝統的なハフ変換処理を用いることが記載されている。

【０００８】ナカヤマらによるヨーロッパ特許出願Ｎｏ
．Ａ２−３６１，９１４では、カメラで撮影した道路像
のデータを処理することによって道路の形状を判断する
ための特殊化されたハフ変換処理が記載されている。こ
こでは、デジタル化画像の第一及び第二領域内での直線
抽出のために、公知のハフ変換技術が採用されている。しかしながら、たとえば第１６図及び第１７図に示され
た第一及び第二領域のいずれかもしくは両方に潜在的に
存在する数多くのエッジに対してハフ処理のリアルタイ
ム処理を可能とするような特殊なハードウエアは開示さ
れていない。

【０００９】

【発明が解決しようとする課題】このようにハフ変換を
用いた画像解析処理の速度を高めるために多大な努力が
なされてきたものの、典型的なデジタル画像データ生成
速度を超える処理速度を有し、融通が効くハフ変換処理
は現在のところ可能ではない。したがって、本発明は、
融通が効き、リアルタイム処理が可能なハフ変換画像処
理装置の提供を、その目的としている。

【００１０】

【課題を解決するための手段】本発明のハフ変換画像処
理装置は、極座標値がオ−バラップする行列を提供する
ために、画像を表す画素の直交座標と関連した値を加算
する加算手段と、該極座標値の少なくとも一部を比較す
る複数のコンパレータと、該コンパレータの出力を論理
的に結合させる論理手段と、該論理手段及び該加算手段
に応答して該加算手段の出力を選択的にゲートで制御す
るためのゲ−ト制御手段と、該ゲート制御手段の出力と
所定のしきい値とを比較する比較手段とを備え、該比較
手段の出力は、該画像と関連する極座標値の最大交差点
に対応することを特徴としている。

【００１１】

【作用及び発明の効果】デジタル化画像データをハフ変
換を実行し、極座標空間内の２値エッジデータの最大交
差点が検出される。すなわち、複数フレームの画像デー
タが、直交座標システム内の画素アレイとして受信され
、記憶される。デジタル化画像内の所与の区画もしくは
ウインドウ内のエッジデータを示す値を有する画素は、
更に引き続いて極座標空間に変換される。

【００１２】その後、極座標空間ヘ変換された画素と関
連する曲線群の複数の最大交差点が、デジタル化画像の
ウインドウ部分を解析するためにニューロハフ変換のハ
ードウエア処理により識別される。上記説明したように
、本発明のハフ変換画像処理装置はニューロハフ変換の
ハードウエア処理により、極座標空間ヘ変換された画素
と関連する曲線群の複数の最大交差点が識別されるので
、ハフ変換を用いた画像解析処理の速度を高め、典型的
なデジタル画像データ生成速度をもつ画像識別に対し、
リアルタイム処理が可能なハフ変換画像処理装置を実現
できる。

【００１３】

【実施例】以下の実施例の説明では、リアルタイムの制
御又は操縦のための画像データ解析を説明する。しかし
ながら、本発明がリアルタイムで実行されるされないに
かかわらず特定の特徴認識のための画像データ解析を要
する何らかのシステムに等しく適用できることは、当業
者にとって当然、理解される。

【００１４】画像生成及び処理システムの好ましい実施
例が第１図に示されている。この図に示されるように画
像データ生成手段は、撮像装置１０として表され、公知
のビデオカメラ（ＣＣＤビデオカメラなど）で構成でき
る。ビデオカメラ１０のアナログ出力はＡ／Ｄ変換器１
４に接続される出力ライン１２に送出される。

【００１５】Ａ／Ｄ変換器１４は、撮像装置１０からの
アナログ画像データをテレビモニターやブラウン管など
のモニター手段１８に送出するアナログ出力１６を含む
。Ａ／Ｄ変換器１４の第一のデジタル入力／出力ライン
２０はたとえば１６ビットのバスの如きデータバス２２
に接続されている。Ａ／Ｄ変換器１４の第二のデジタル
出力ライン２４はフレームバッファ２６に入力される。

【００１６】第１図に記載された本発明の実施例では、
Ａ／Ｄ変換器１４は多くのデジタル化画像データのフレ
ームをつくり出す。デジタル化画像データの各々のフレ
ームはたとえば５１２×５１２画素アレイの明暗画像デ
ータであって、各々の画素は８ビットの値として表され
る。Ａ／Ｄ変換器もよって創成される画像デ−タの各デ
ジタルフレ−ムは、フレ−ムバッファ２６に入力され、
記憶される。

【００１７】１フレームのデジタル化画像データは撮像
装置１０から受信した１フレームのアナログ画像データ
を表し、それは５１２×５１２×８、すなわち、２．０
９７１５２メガビット相当のデータの総合解像度を有す
る。Ａ／Ｄ変換器１４の第一のデジタル入力／出力ライ
ン２０はホスト中央演算プロセッサ（ＣＰＵ）２８から
の制御信号に応答する。また、ＣＰＵ２８はまた双方向
ライン３０を介してデータバス２２に公知の形式で接続
されている。Ａ／Ｄ変換器１４からのステ−タス信号は
、デジタル入力／出力ライン２０およびデータバス２２
を介して第１図のシステムの他の部品へと同様に、ＣＰ
Ｕ２８に送出され得る、フレームバッファ２６は、公知
の形で制御およびステ−タス信号送受用の双方向ライン
３２を含む。フレームバッファ２６は、記憶する画像デ
ータのフレームを画像プロセッサ４０に移送するための
デジタル出力３８を含む。

【００１８】Ａ／Ｄ変換器１４、フレームバッファ２６
、および、画像プロセッサ４０は、たとえばマサチュー
セッツ州ウォバーン、ウエストカミングスパーク６００
のイメージングテクノロジーインコーポレーティド（Ｉ
ｍａｇｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｃ．）　が
製造している公知の、シリーズ１５１イメージプロセッ
サ（Ｓｅｒｉｅｓ　１５１　Ｉｍａｇｅ　Ｐｒｏｃｅｓ
ｓｏｒ）で構成される。

【００１９】たとえば、シリーズ１５１イメージプロセ
ッサを使う場合、画像プロセッサ４０は、パイプライン
形の算術論理演算装置（ＡＬＵ）およびリアルタイムの
コンボルバを含む。バス２２は、シリーズ１５１イメー
ジプロセッサに有効な標準の内部１６ビットのバスとす
ることができる。画像プロセッサ４０の出力は、バス２
２を介して第１図のシステムの他の部分と制御およびス
テ−タス信号を送受信するための双方向ライン４２とし
て示されている。

【００２０】双方向ライン２０、３０、３２、４２およ
びデータバス２２はそれぞれ、たとえば１６ビットのバ
スとすることができる。しかしながら、これらのデータ
ラインの実際のサイズは、たとえば画像データのデジタ
ル化フレームにおえる画素の値（強さ）を表すビット数
によって変化する。すなわち、画像データフレームの各
画素は、第１図の実施例では８ビットで表されるので、
Ａ／Ｄ変換器１４とフレームバッファ２６と画像プロセ
ッサ４０とは、８ビットの画素の値を受け入れるだけで
足りる。しかしながら、本発明は第１図の実施例の解像
度に限定されるわけではない。たとえば、デジタル化画
像フレームの各画素はどんなビット数ででも表示でき、
第１図の実施例のデータラインをそれに応じて変更する
ことができる。もし各画素が１６ビットで表示されるな
ら、デジタル化画像データの移送に供される各デジタル
出力は画像情報用に１６ビット以上とされる。

【００２１】作動において、撮像装置１０が原画像の画
像データを生成し、Ａ／Ｄ変換器へ入力するべくアナロ
グの明暗マップを創成する。Ａ／Ｄ変換器は、フレーム
バッファ２６に記憶するために第２図に示されるような
明暗画像データのデジタルフレ−ムをつくる。また、Ａ
／Ｄ変換器はデジタル化画像の各画素について明度値を
出す。たとえば、各画素８ビットの標準的な５１２×５
１２のアレイが、第３図の明暗画像を表示するのに採用
することができる。

【００２２】続いて、デジタル化画像データの各フレー
ムは、フレームバッファから画像プロセッサ４０へ従来
公知のリアルタイム画像処理のために移送される。たと
えば、各画素が１ビットで表されている２値エッジデー
タの５１２×５１２のアレイを作成するためにデジタル
化画像の標準的なエッジ検出が実施される。第２図の明
暗画像においてエッジが検出された全ての画素の値は、
２進数の１で表され、他の全ての画素の値は２進数の０
で表される。こうして第３図に示される２値エッジ画像
が作成される。この実施例では、標準的なエッジ検出は
しきい値検出段階とフィルタリング段階とを有する。

【００２３】このしきい値検出は、デジタル画像の８ビ
ットの各明度値を一つのしきい値と比較することによっ
て行われる。たとえば、可能な全明度値のほぼ中間値が
しきい値として選択される（たとえば、８ビット表示で
はとりうる０から２５５までの画素値に対して１００の
値が適当なしきい値である。）。あるいは、しきい値は
、すでに処理された画像データの多くのフレームに関連
するヒストグラム値によって決めてもよい。しきい値よ
りも大きい値には２進数「１」が、しきい値よりも小さ
い値には２進数「０」が割り当てられる。

【００２４】結果として得られる２値データのアレイは
、リアルタイム処理がたとえばラプラシアンフィルタで
行われるフィルタリング段階にかけられる。つまり、ラ
プラシアンフィルタに関連した特徴を有する３×３画素
のウインドウが、エッジ検出改善のために２値データア
レイ内の各々の値に適用される。公知の３×３のラプラ
シアンフィルタのウインドウには、たとえば「４」の値
を持つ中央画素と、−１及び０とを交互にもつ周辺ビッ
トとが含まれる。

【００２５】デジタル化画像全てに対して画像データの
２値エッジフレームを創成した後、一小区画すなわち第
３図に示されるようなウインドウ「Ａ」がデータから抽
出される。実施例では２値エッジデータの小ウインドウ
は、５１２×５１２画素の２値エッジデータアレイの中
央の画素を含む１５×１５の画素値のアレイ（すなわち
行列）として定義される。中央部の画素のウインドウが
以下に記載されるような方法で処理された後、小ウイン
ドウは別のウインドウの２値エッジデータを判別するた
めに水平にもしくは垂直に動かされる。この処理は５１
２×５１２のアレイ全体についてのデータが処理される
まで繰り返される。

【００２６】第４図では、第３図のウインドウＡについ
ての１５×１５のアレイの２値エッジデータに相当する
デジタル化ウインドウ画像が示され、各画素値は１ビッ
トで表される。第５図は第３図と第４図のデジタル化ウ
インドウ画像に相当する２値エッジデータを表す。第４
図及び第５図に示されているように、デジタル化ウイン
ドウ画像内のエッジデータの各ビットは、１から１５ま
での対応する（Ｘ×、Ｙ）座標値として表すことができ
る。

【００２７】デジタル化ウインドウ画像に相当する２値
エッジデータは、第１図の画像プロセッサ４０からニュ
ーロハフプロセッサ３６へデジタル出力４２、バス２２
、およびニューロハフプロセッサ３６とバス２２とをつ
なぐ双方向インターフェイスバス４４（たとえば１６ビ
ット）を介して出力される。一方、画像プロセッサ４０
からの２値エッジデータがフレームバッファ２６に記憶
されていた場合には、データはニューロハフプロセッサ
３６にデジタル出力３２、バス２２およびバス４４を介
して出力される。ニューロハフプロセッサ３６はホスト
ＣＰＵ２８へ処理済データを移送するためのバス４３（
たとえば１６ビット）を含んでいる。

【００２８】ニューロハフプロセッサ３６は、エッジデ
ータの存在を表し（すなわち第５図では「１」によって
表されている）、かつ、ある一組の極座標を含む一本の
曲線に変換されるデジタル化ウインドウ画像内の画素位
置の数を識別するために本発明に従って設計されている
。すなわち、ニューロハフプロセッサ３６は第５図のデ
ジタル化ウインドウ画像内の「１」で表される全ての（
Ｘ、Ｙ）座標に関連する曲線の数を決定し、これら曲線
は極座標ρとθのある一組において、一部重なり合う。

【００２９】好適な実施例ではニューロハフプロセッサ
３６、はそれぞれある一組の極座標に一部重なり合う２
値エッジデータに関連した曲線の数を識別するためのハ
フ変換のハードウエア処理を代表している。すなわち、
一部重なり合う極座標を持つ第５図の画像内のこれら画
素位置を識別することによって、ニューロハフプロセッ
サ３６は局所的最大交差点として指定される最大の重な
り点に関連した極座標を検出することができる。この局
所的最大交差点から全体としての最大交差点が判断でき
る。

【００３０】（Ｘ、Ｙ）座標値のハフ変換の結果として
得られる曲線を表すのに用いられる極座標がρおよびθ
の値で規定される。前に述べたように第５図の画素位置
は第５図の画像が直交座標空間とみなされる（Ｘ、Ｙ）
座標値によって表すことができる。ρの値はエッジ点の
第５図のデジタル化ウインドウの画像の中心からの距離
に相当し、θの値はエッジ点と第５図のデジタル化ウイ
ンドウ画像の水平な×軸との間の角度に相当する。

【００３１】第５図の直交座標空間内の各々の点に対し
て、１から１５の組の関連の極座標（たとえば一組の極
座標は第６図の各行内の一点に相当する）を有すること
ができる極座標空間内に一本の曲線が創成される。それ
ゆえ、第５図のアレイ内の一本のラインと関連した２値
エッジデータは、第６図の極座標空間の少なくとも一つ
の極座標位置で重なり合う関連した曲線を持つことにな
る。

【００３２】たとえば、第５図において直線を表す２値
エッジデータと関連した曲線は、理想的には第６図の極
座標空間における一個の最大重なり点を有するべきであ
る。したがって、第６図内の所与の一組の極座標値で重
なり合う曲線の数は、普通１５を超えない。実際たいて
いの場合には、たとえば第４図に示されるように直交座
標空間では直線は連続して表されないので、ある極座標
位置で重なり合う曲線の数は１５より少ないであろう。

【００３３】第５図のアレイに含まれる全ての２値エッ
ジデータに関連した重なる極座標が決定された後、第６
図に示されるように極座標アレイのデータが得られる。その後、処理されているデジタル化ウインドウに存在す
るエッジ点を表す曲線の軌跡が集中している最大交差点
を表すρとθの値が識別される。これらの最大交差点は
実施例では何らかのビット数で表示されるρとθの値を
有する。しかしながら、ρとθの値はそれぞれ典型的に
は第６図に示される極座標空間を表すために用いられた
１６の値の一つをとることになるので、これらの値の各
々に対しては４ビット表示で充分である。上記各値は出
力ライン４４を介してフレームバッファ２６に記憶され
る。もしくは、上記データは直接、ホストＣＰＵ２８に
記憶されることができる。その後、次のウインドウの２
値エッジ画像データが処理される。

【００３４】前述のステップは、第３図の２値エッジ画
像の１５×１５の各々のウインドウについて繰り返され
る。ニューロハフプロセッサによってこのようにフレー
ムバッファもしくはホストＣＰＵに記憶されている全デ
ータは３４×３４×｛（４ビット×２）×ｎ｝のアレイ
に相当する。ここで｛（４ビット×２）×ｎ｝の指定は
、ｎ組のρおよびθの各４ビットが５１２×５１２の２
値エッジ画像の１５×１５のビットのウインドウの各々
について記憶されていることを表しており、ｎはあるウ
インドウで検出されたラインの数に相当する。

【００３５】あるいは、ラインデータを含むと判断され
たウインドウからのデータだけが記憶されてもよい。こ
の場合には３４×３４のマトリックス内の各々の位置は
６ビットの行の値と６ビットの列の値を有するアドレス
として表すことができる。ρとθの値は｛（４ビット×
２）×ｎ｝の値として表すことができる。したがって、
記憶された全データは｛６ビット×２＋（４ビット×２
）｝×ｎの値の合計であり、ラインデータに関連した極
座標のアドレスを識別する最初の１２ビットを有する。

【００３６】記憶されたデータは、逐次リアルタイム画
像認識のためにフレームバッファからホストＣＰＵ２８
へ移される。このリアルタイム画像認識には、記憶され
たρおよびθの値によって識別された画像内でのライン
の再構成が含まれる。この目的のために、ホストＣＰＵ
はサンマイクロシステムインコーポレーティッド（Ｓｕ
ｎＭｉｃｒｏｓｙｓｔｅｍｓ，　Ｉｎｃ．）のサンスパ
ーク３３０（Ｓｕｎ　Ｓｐａｒｃ　３３０）　コンピュ
ータのような公知のコンピュータとすることができる。

【００３７】以下、ニューロハフプロセッサについて詳
細説明する。ニューロハフプロセッサ３６の入力データ
は上記したように第５図に示す１５×１５×１ビットの
データアレイである。プロセッサ３６で受信される入力
データについての極座標内の最大交差点は、第６図から
第３図（ｅ）で説明するようにニューロハフ変換を用い
て識別される。たとえば、上記したように第６図のハフ
変換アレイに示された数は、第５図の（Ｘ、Ｙ）空間内
の全ての２値エッジ点に対し、次の等式で示される一部
重なり合う曲線によって得られる。

【００３８】 ρ　　＝　　ｘ　ｃｏｓ（θ）　　＋　　ｙ　ｓｉｎ（
θ）実施例内のρの潜在的な値は、２×１５（すなわち
、中心点から第５図のアレイの外の角までの最大距離）
の平方根に等しい値に相当することができるので、１９
のρの潜在値が選ばれた。それゆえ、第６図に示された
１９×１５のマトリックスが第５図のデータのハフ変換
を表すのに用いられる。　　しかしながら、第６図の極
座標内の最低位の２行または最高位の２行によって表さ
れたρおよびθの値を有する局部的な最大値を持つ第５
図のアレイでは、少数のラインしか存在しないことがあ
らかじめわかっているので、これらの行は適宜その後の
識別を省略し得る。この場合には、第６図のアレイは１
５×１５のマトリックスで表示可能である。しかしなが
ら、どんなサイズのマトリックスでも極座標を示すのに
用いることができ、上記サイズはρおよびθの解像度を
反映する。

【００３９】第６図において、ρの１９の値は−９から
＋９までの範囲をとることができるが、実際は−７から
＋７までの値だけが考慮される。θの１５の値は０°か
ら＋１８０°の範囲にある。すなわち、第５図の画像内
の水平なｘ軸がθを決めるのに用いられるので、１８０
°から３６０°の角度は考慮する必要はない。引き続き
、３×３のマトリックスで表されるウインドウが、ハフ
変換アレイ内の局所的最大値を検出するのに用いられる
。たとえば、第７図に示される３×３のマトリックスは
局所的最大交差点の検出を表しており、上記局所的最大
値は各ウインドウの中心極座標値を調べることによって
判断される。

【００４０】これら複数の３×３のマトリックスは第８
図に詳しく示されている。上記局所的最大値を検出する
ために、データの中心極座標値（たとえば実線で示され
た第８図の値１１）が、そのウインドウ内の隣接極座標
値と比較される。もし３×３のマトリックスの中央値が
周辺極座標の値よりも大きければ第９図に示されるよう
に局所的な最大交差点とみなされる。

【００４１】第９図に示すように一度、局所的最大値が
決定されると、不適当な局所的最大値の検出を避けるた
めに、各局所的最大値はしきい値により比較される。　
　その後、ハフ変換アレイ全体について残りの局所的最
大交差点に第１０図に示す極座標空間内の２進数の”１
”が割り当てられる。第８図のウインドウによって局所
的最大交差点が検出されたなら、そのウインドウ内の全
ての周辺点に第９図に示す０の値が割り当てられる。

【００４２】局所的最大交差点が局所化されたもしくは
適当なしきい値と比較された後、局所的最大交差点だけ
が第９図のマトリックスのアレイになおも残留する。　
　そして、これら局所的最大交差点に第１０図に示すよ
うに１の値が割り当てられる。第１図のシステムに示さ
れるニューロハフ変換プロセッサ３６の極座標のハード
ウエア処理例を第４図により詳しく示す。

【００４３】第１１図のハードウエアで処理は、各フレ
ームの画像データに対して第５図のアレイ（行列）によ
って求められる２値エッジデータから第１０図にみられ
るような最大交差点を検出するニューロハフプロセッサ
の一部を表している。第１１図の実施例に相当するニュ
ーロハフ変換は、１チップのプロセッサで実行される。説明のために、２つの極座標出力５０および５２が第１
１図に示され、第５図のアレイの直交座標に関連した４
つの入力５４、５６、５８および６０も第１１図に示さ
れている。これら各入力は、第５図のアレイ内の２値エ
ッジデータのビットに相当している。しかしながら、第
５図のデジタル化ウインドウ画像に相当する２値エッジ
データを受け入れるために、ニューロハフプロセッサ３
６のハードウエアで処理には少なくとも１５×１５の入
力ラインが含まれる。

【００４４】さらに、１５×１５の入力アレイの各局所
的最大交差点が第１１図のハードウエア処理によって決
定される場合、第３図の極座標空間に相当する１５×１
５の出力ラインが採用される。入力ライン５４乃至６０
はそれぞれ、１ビットのデータすなわち画素の値を第５
図の２値エッジデータのアレイから受信する。第１１図
のハードウエア処理には、さらに加算器６８および７０
を含む一連の加算器によって創成される極座標データを
表す一連の結節点６２、６４、６６が含まれる。これら
の加算器の各々は、第６図のハフ変換アレイ内の一組の
極座標値に相当している。

【００４５】各加算器は。第５図のアレイの（Ｘ、Ｙ）
空間内の各点に相当するとともに、対応する加算器と関
連する極座標値で重なる曲線の数を計算する。加算器は
このように第６図に示すハフ変換アレイの値を出力する
。第１１図に示された前出の２つの加算器６８および７
０は、第５図のアレイ内のそれぞれの画素位置と関連す
る所定の直交座標の入力ラインから受信したデジタルデ
ータを加算するためのものである。直交座標の２値エッ
ジデータと関連している曲線の極座標値は、前もって決
められる。

【００４６】すなわち、第１１図のニューロハフプロセ
ッサの処理に先立って、第５図のアレイの各画素位置に
”１”が存在することによって影響を受ける第６図のハ
フ変換アレイの極座標値が算術的に決定される。たとえ
ば、前出のハフ変換等式は第５図の２値エッジデータア
レイの各画素の位置について解くことができる。その後
、第１１図の各加算器は自己と関連した極座標値を含む
ハフ変換曲線を持つ第５図内の全ての（ｘ、ｙ）画素位
置から受信するべく、結線される。たとえば、加算器６
８は少なくとも３つの入力ライン５４、５６、５８から
の値を受信し、第５図のアレイ内のエッジデータと関連
しているこれらの入力の合計に相当する出力をする。

【００４７】第１１図のニューロハフプロセッサ処理で
は、さらにコンパレータ７４等の複数のコンパレータが
設けられている。これらのコンパレータは、各加算器出
力の値を、たとえば第６図のアレイ内の周辺極座標値に
相当する８つの加算器出力値と比べるために設けられて
いる。極座標位置のいくつかは第６図の最も外側の列も
しくは行内の極座標位置のように８個の周辺値を持たな
いので、この場合には８より少ない値が考慮される。

【００４８】たとえば、コンパレータ７４は加算器７０
の出力からの極座標値を結節点７５に存在する加算器出
力と比較する。もし結節点７５からコンパレータ７５へ
の入力値が加算器７０の出力値よりも大きい場合には、
コンパレータ７４は低い出力をする。しかしながら、も
し結節点からの入力値が加算器７０の出力値よりも大き
い場合には高い出力をする。加算器の出力につながれた
コンパレータは第７図や第８図に示されるようなウイン
ドウを作るためにグループ化される。もしあるウインド
ウに含まれたデータに関連した全てのコンパレータの出
力が高かったら、そのウインドウの中央の極座標値は局
所的な最大値を示すものとみなされる。

【００４９】この局所的な最大値は、所与のウインドウ
に関連したコンパレータの出力全てを一つのＡＮＤゲー
ト、たとえばＡＮＤゲート７８に導くことによって検出
される。第４図に示されたようなさらなるＡＮＤゲート
は別の３×３のウインドウアレイに関連している。第４
図の実施例に示されたような加算器およびコンパレータ
は、ＡＮＤゲートにデジタル電圧を出力するアナログ装
置である。

【００５０】たとえば、もしＡＮＤゲート７８に接続さ
れたコンパレータの出力すべてが高く、そのウインドウ
中央の極座標値が局所的最大値に相当するなら、ＡＮＤ
ゲート７８の出力は高くなる。さもなければ、ＡＮＤゲ
ート７８の出力は依然として低いままである。インバー
タ７７などのインバータもハフ変換処理で必要とされる
回路を小さくするために用いられる。たとえば、加算器
７０および７２の出力はコンパレータ７９につながれて
いるので、コンパレータ７９は加算器７２の出力が加算
器７０の出力を超える時にハイレベルを出力する。しか
しながら、もし加算器７０の出力が加算器７２の出力を
超えるなら、結果として生じるロ−レベルが、インバー
タ７７を介してＡＮＤゲート７８に高い信号を入力する
ために使われる。これによって、加算器７０および７２
の出力を比較するのに異なる２つのコンパレータを用い
る必要性を避けることができる。

【００５１】ここに記載したように加算器の出力を受信
するコンパレータは一つの入力が他の入力を超える時の
みにハイレベルをする。しかしながら、本発明はこのよ
うな構成に限定されるわけではない。たとえば、コンパ
レータは二つの出力が等しい時にハイレベルをするよう
にも設計可能である。もしＡＮＤゲート７８の出力が高
いなら、ゲート８０は加算器７０の出力がゲート８０の
出力へ送ることができる。たとえば、第８図のウインド
ウについては、１１の値がゲート８０を通過してしきい
コンパレータ８２に送られることになる。同様のゲート
８４がしきいコンパレータ８２に関しても設けられてい
る。ゲート８０および８４の出力はこのように第９図に
示すような局所的最大交差点のアレイを提供する。

【００５２】しきいコンパレータ８２および８６は、ゲ
ート８０および８４からのデータ出力を結節点８８およ
び９０のしきい値レベルとそれぞれ比較する。もしゲー
トからしきいコンパレータに入力されたデータが各しき
い値レベルより高いなら、しきいコンパレータの出力は
高くなる。一方、しきいコンパレータの出力は依然とし
て低いままである。しきいコンパレータ８２および８６
は、局所的最大交差点を上記局所的な最大値の交差点か
ら検出する制度を向上させる。

【００５３】しきいコンパレータの出力は局所的最大交
差点を表すので、それらは２進数の”１”および”０”
として表すことができる。最大交差点は第９図のアレイ
のしきいコンパレータの出力として第１０図に示される
。結節点８８および９０に入力されたしきい値は、たと
えば第１２図に示されるような完全黒画像に相当する画
像部位からハフ変換で決定される。第１２図のデータに
対する１５×１９のハフ変換アレイが第５図（ｂ）に示
される。　　その後、第５図（ｂ）のハフ変換アレイは
、試行錯誤の結果として、適切な最大交差点をより正確
に検出するしきい値の決定を可能にするべく修正される
。

【００５４】たとえば、第１３図のアレイ内の４の値は
５の値に変換されるので、より大きなしきい値が極座標
の位置に関連づけられることになる。さらに、ランダム
ノイズが局所的な最大値として検出されるのを防ぐため
、２の値よりも小さなしきい値はどれでも２の値で表さ
れる。さらに、第１３図のアレイの１５よりも大きいす
べての値は１５で表される。最大値１５は、第５図の直
交座標空間と第６図の極座標空間内の行の数に相当する
ように選ばれる。前述のように、第２図の（Ｘ、Ｙ）直
交座標空間内の直線は、理想的には第１３図において一
組の極座標に重なり合うかもしくは集中する極座標空間
内の１５本の曲線によって表されるべきである。

【００５５】さらに第１３図の１５×１９のアレイは、
前に述べたように第１３図の極座標空間の最高位および
最低位の２行を考慮する必要がないので、第１４図内の
１５×１５のアレイに縮小することができる。しきい値
を得るために、第１４図のハフ変換アレイ内の様々な極
座標位置に関連した値には、０から１の範囲にある（た
とえば０．４の）しきい係数が掛けられる。ゲート８０
および８４などのゲートの出力が局所的な最大交差点と
しての資格を有するために、ゲートから出力された値は
しきい値よりも大きくなければならない。

【００５６】上記したように、第１１図のニューロハフ
変換処理で示した出力５０および５２を含む１５×１５
の出力の各々は、所与の一組の極座標に相当している。したがって、これらの出力のうちの一つに高い信号が存
在するということはその出力に関連した極座標位置での
最大交差点の存在を意味する。したがって、ニューロハ
フ変換装置の出力と所与の一組の極座標との相互関係を
示す参照用テーブルは、ホストＣＰＵに内蔵できるので
、デジタル化画像の最大交差点に関連した極座標だけを
記憶すればよい。前記したように、最大交差点の極座標
は実施例では２０ビットの値として記憶することができ
る。

【００５７】第１５図はニューロハフプロセッサの一部
の別の実施例を示す。このニューロハフプロセッサでは
第１１図のアナログの加算器とコンパレータがカウンタ
とデジタルコンパレータに置換されている。すなわち、
カウンタ９０は、第６図のハフ変換アレイ内のある極座
標位置と関連している。カウンタ９０は第５図の２値エ
ッジウインドウ内のこれら（ｘ、ｙ）位置からの入力を
受信する。上記２値エッジウインドウは、カウンタ９０
の入力と関連した極座標を含むハフ変換曲線を持つよう
にあらかじめ決定されている。

【００５８】このように、カウンタ９０はエッジデータ
に関連付けられており、しかもカウンタ９０と関連した
極座標を含むハフ変換曲線を持つ（ｘとｙ）座標値の数
に対応する４ビット出力を送出する。カウンタ９０の出
力は、第６図のハフ変換アレイに示される値の一つを表
している。その後、カウンタ９０の出力は局所的な最大
値の検出に供される。　　たとえば、各カウンタの出力
は前に記載したように８個の周辺値と比較される。第６
図に示されるコンパレータ９２、９４、９６、９８、１
０２、１０４、および１０６は、第８図に示されるウイ
ンドウを表す。

【００５９】もしカウンタ９０の出力値がコンパレータ
９２乃至１０６への他の各入力によって示される８個の
周辺値より大きいなら、これらのコンパレータ全てはＡ
ＮＤゲート１０８へハイレベルを出力する。更に、カウ
ンタ出力は最大交差点を識別するために、しきいコンパ
レータ１１０でしきい装置１１２からのデジタルしきい
値と比較される。このしきい値は第１１図および第１５
図に関連して記載されたしきい値と同様の方法で決めら
れる。

【００６０】もしカウンタ出力が、あるウインドウの８
個の周辺値よりも大きく、かつ、装置１１２からのしき
い値よりも大きい場合にはＡＮＤゲート１１４からのハ
イレベルは、カウンタ９０に関連した極座標値が最大交
差点であることを表す。しかしながら、ＡＮＤゲート１
１４は必須ではなく、適宜コンパレータ１１０からの出
力をＡＮＤゲート１０８へ送出することによって削減す
ることもできる。

【００６１】第１１図の実施例のように、３４×３４×
（４ビット×２）×ｎのアレイが、各デジタル画像につ
いて考慮された２値エッジデータの１５×１５の各ウイ
ンドウと関連するρおよびθの最大交差点の値を示すの
に用いられる。第１６図は第６図のものに似たニューロ
ハフプロセッサの一部のより好ましい別の実施例を示す
。

【００６２】第１６図のＡＮＤゲート１０８はコンパレ
ータ１１０からの出力を受信し、前に記載したように第
１５図のＡＮＤゲート１１４を不要なものとしている。さらに第１６図のカウンタ９０はプログラマブルロジッ
クアレイ１２０に置き換えられている。ロジックアレイ
１２０は、デジタルのハイレベルを有している入力ライ
ンの数を表す２値出力のカウント値に相当する出力をす
るべくプログラム可能な公知の装置を示す。

【００６３】しかしながら、デジタルのハイレベルを持
つ入力ラインの数を逐次、カウントするのを回避できる
ので、ロジックアレイはカウンタ９０よりも早く作動す
る。例えば、ロジックアレイ１２０に対する関数表は、
全入力がローレベルの場合に４本の出力ラインすべてが
ローレベル（すなわち、カウント０に相当する）となり
、かつ、全入力がハイレベルの場合に４本の出力ライン
すべてがハイレベル（すなわち、デジタルカウント１５
に相当する）となるようしている。

【００６４】このように、ロジックアレイの出力はハイ
レベルの入力の数によって決まる０から１５のカウント
値を表している。いままで、ハフ変換のいくつかのハー
ドウエア処理例を説明してきたが、本発明に基づいて別
の形式のハフ変換を実行してもよい。たとえば、第１１
図および第１５図に記載されたハードウエアの特徴は、
適宜ソフトウエアで実行できる。

【００６５】このように、本発明を図面を参照して例と
して充分に説明してきたが、当業者による様々な変更お
よび修正が可能なことは当然であり、そのような変更お
よび修正が本発明の範囲を逸脱しない限り、特許請求の
範囲に含まれるものとして解釈されるべきである。

【図面の簡単な説明】

【図１】本発明にしたがって設計された画像生成、処理
システムを示すブロック図、

【図２】画像を１フレームの画素値にデジタル化するこ
とを示す画面図、

【図３】画像を１フレームの画素値にデジタル化するこ
とを示す画面図、

【図４】画像を１フレームの画素値にデジタル化するこ
とを示す画面図、

【図５】画像を１フレームの画素値にデジタル化するこ
とを示す画面図、

【図６】ニューロハフ変換を用いた図２のデジタル化画
像の解析を示す行列図、

【図７】ニューロハフ変換を用いた図２のデジタル化画
像の解析を示す行列図、

【図８】ニューロハフ変換を用いた図２のデジタル化画
像の解析を示す行列図、

【図９】ニューロハフ変換を用いた図２のデジタル化画
像の解析を示す行列図、

【図１０】ニューロハフ変換を用いた図２のデジタル化
画像の解析を示す行列図、

【図１１】ニューロハフプロセッサの要部ブロック図、

【図１２】図１２のニューロハフプロセッサに用いるし
きい値の決定を示す行列図、

【図１３】図１２のニューロハフプロセッサに用いるし
きい値の決定を示す行列図、

【図１４】図１２のニューロハフプロセッサに用いるし
きい値の決定を示す行列図、

【図１５】ニューロハフ変換装置の他の実施例を示すブ
ロック図、

【図１６】ニューロハフ変換装置の他の実施例を示すブ
ロック図。

Claims

【特許請求の範囲】

【請求項１】極座標値がオ−バラップする行列を提供す
るために、画像を表す画素の直交座標と関連した値を加
算する加算手段と、該極座標値の少なくとも一部を比較
する複数のコンパレータと、該コンパレータの出力を論
理的に結合させる論理手段と、該論理手段及び該加算手
段に応答して該加算手段の出力を選択的にゲートで制御
するためのゲ−ト制御手段と、該ゲート制御手段の出力
と所定のしきい値とを比較する比較手段とを備え、該比
較手段の出力は、該画像と関連する極座標値の最大交差
点に対応することを特徴とするハフ変換画像処理装置。
【請求項２】該加算手段は複数の加算器を含み、上記各
加算器は所定の直交座標を有する画素からの入力を受信
する請求項１記載のハフ変換画像処理装置。
【請求項３】該画素の直交座標は直交座標空間内の上記
画像の一区画を表す請求項１記載のハフ変換画像処理装
置。