JPH02125366A - 回転運動漸化式の演算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はＨｏｕｇｈ（ハフ）変換におけるＤＤＡ（Ｄｌ
ｇｉｔａｌ　Ｄｌｒｆ’ｅｒｅｎｔｌａｌ　Ａｎａｌｙ
ｓｌｓ；ディジタル微分解析）などに用いられる回転運
動漸化式の演算装置に関する。

〔従来の技術〕

Ｈｏｕｇｈ変換などにおいては、回転運動漸化式を演算
する方法が提案されている。この場合、第８図において
、ｘ−ｙ直交座標系で原点０よりρだけ離れた点Ｐ　　
（Ｘｌ、Ｖｉ）を原点０を中心にε（ｒａｄ）だけ回転
させた点Ｐ　　　（ｘｉｌｌ　　　　　　１＋１’ ｙ−）は、下記により求められる。すなわち、１＋１ ｘ、、ｙ・を Ｘ、閤ρ・ｃｏｓθ　　　　　　　　・・・（１）ｙ　
！ρ・ｓｉｎθ　　　　　　　　・・・（２）とすると
、Ｘ　　　＋Ｖ１＋１は ｘ、ｌ−ρ・ｃｏｓ（θ十ｇ）　　　　・・−（３）ｙ
ｉｌｌ−ρ・５ｉｎ（θ＋ε）　　　・・・（４）とな
る。そこで、式（３）、（４）を加法定理によって展開
し、式（１）、（２）を代入するとｘ　　　、−ｃｏｓ
ｇｌｌｘ　　−５ｉｎε・ｙｌ−（５）！＋１　　　、
　　　　　１ ７国−５ｉｎＥ０ｘ　＋ｃｏｓｇ隼ｙ１・・（６）とな
る。

従って、この式（５）、（６）を用いれば点Ｐ１（ｘ、
ｙ）から点Ｐ　　　（ｘ　　　、ｙ　　　）１　　　　
１　　　　　　　　　１＋１　　　　１＋１　　　　１
＋１を演算できるが、この演算には三角関数が含まれ、
このためハードウェア化が面倒なだけでなく高速処理に
適していない。そこで、ｓｉｎε、ｃｏｓεをテーラ−
展開して ｓｉｎε 一ε−ε３／３！＋ε５１５！−ε７／７！＋・・・・
・・（７） ＣＯＳ　ε −１−ε２／２！十ε４／４！−εＢ／６！＋・・・・
・・（８） とし、ｓｉｎε−ε、ｃｏｓε−１と一次近似して次の
ような回転運動漸化式がまず考えられる。

ｉｌｌ　　　ｉ　　　　　　　　　　　　　・・・（９
）ｘ　　　ｍｘ　　−εｙｌ ｙ−−εｘ　１＋　ｙ　ｓ　　　　　　　　　・・・（
１０）ｅ１ しかし、これによれば回転運動は渦巻き化してしまうの
で、実際には用いられていない。そこで、回転中の誤差
による渦巻き化を防止するために、次の式（１１）、（
１２）のような回転運動漸化式が円発生ＯＤＡ演算など
で用いられている。

ｌ・、　　　ｌ　　　　　　　　　　　　゛　０ｔ）Ｘ
　　　″Ｘ　　−εｙＩ −εｘ　　　＋ｙ　　　　　　　・・・（１２）ｙｔｉ
ｔ　　　　　　ｔｉｔ　　　　ｔそして、この式（１１
）、（１２）の演算は例えば第９図のようなハードウェ
アで実現される。これらによれば、比較的簡単なハード
ウェアにより回転運動を近似することができる。

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

しかしながら、上記の従来装置では高速演算が可能にな
るものの、その誤差が大きく高精度な演算に適しないと
いう欠点があった。すなわち、第１０図（ｂ）に実線で
示すような半円を描こうとすると、回転運動漸化式の演
算につれて誤差が大きくなり、点Ｐ　（ｘ　　、ｙ□）
からπ（ｒａｄ）回転したときの誤差ｄが無視できない
ものとなる。

ここで、誤差率ｄ’　　（％）を ｄ’　−（ｄ／Ｒ）Ｘ１００　（％） とすると（但し、Ｒは円の半径）、第１０図（ａ）に示
す従来の一次近似によるハードウェアおよび第９図に示
す従来のＤＤＡに用いられていたハードウェアでは、誤
差率ｄ′が第１１図のようになってしまう。

このような誤差を伴なうものは、例えばＨｏｕｇｈ変換
などに用いることができない。すなわち、円の直径に対
する誤差率が約±０．４％（例えばＨｏｕｇｈ変換にお
いてρ（原点から線分までの距離）を１２８分割して処
理するときの量子化誤差は±０．４％である）以内にな
ると実用上の支障はないが、このようにするためには必
要な回転角εが小さくなりすぎてしまう。

そこで本発明は、ハードウェア構成が簡単であって高速
演算が可能であり、しかも回転角を大きくしても誤差を
小さくできる回転運動漸化式の演算装置を提供すること
を目的とする。

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

本発明に係る回転運動漸化式の演算装置は、Ｘ−ｙ直交
座標系で描かれる近似円の円周上の一点の座標を（Ｘ　
　、ｙｌ）とし、円周上の次の点のＦＢｍ　（ｘ　、＋
１．　　ｙ　、１）　＊テノ回転角ヲε−２−ｍとした
とき（但し、ｉは正の整数）に、ｘ、　　＝ｆ　　　（
ｘ　　、ｙ・・　ε）ｒ＋ｌ　　　ｘ　　　ｉ　　　１ ｙｉ＋１　“ｆ　　（Ｘ　Ｉ）’　　ｌ　　ε）ｙ　　
ｉ　　Ｉ となる回転運動漸化式を回転角の１または複数回転角ご
とに演算する回転運動漸化式の演算装置において、座標
データｘ　、ｙ　を入力して２ｍ−１ ｘｉ＋、−（１−２）ｘ、−２１ｙ。

の座標データを出力する第１の演算手段と、座標データ
Ｘ　＋　　ｙｌを人力して ■ Ｖ　　−２ｘ　　十（１−２−２’−１）　Ｊ国　　　
　Ｉ の座標データを出力する第２の演算手段とを備えること
を特徴とする。

ここで、第１の演算手段は、 Ｘ、、−”（１−２″″２ｍ−１＞　ｘｌ（２”−ＩＩ
−２””’　／６）　ｙ。

の座標データを出力し、第２の演算手段はｙ−（２１−
２−３１／６）ｘｌ １＋１ ＋　（１−２″″２１１−１）ｙＩ の座標データを出力することを特徴としてもよい。

〔作用〕

本発明によれば、第１の演算手段は座標データｘ１．ｙ
　にもとづいて座標データＸ　　を演算ｔ　　　　　　
　　　　　　　　　　　　　　　　　ｔｉｔ出力し、第
２の演算手段は座標データＸ１＋３’１にもとづいて座
標データｙ　　を演算出力する。

そして、第１および第２の演算手段を加算器、インバー
タのみで構成すればハードウェアの簡単化と演算の高速
化が図られ、除算器を用いて構成すれば一層の高精度化
が図られる。

〔実施例〕

以下、添付図面の第１図ないし第７図にもとづいて、本
発明の詳細な説明する。なお、図面の説明において同一
要素には同一符号を付し、重複する説明を省略する。

第１図は本発明の第１実施例に係る演算装置の回路図で
ある。図示の通り、第１の演算手段はｎ１ビツトシフト
させた座標データＹ　１．を符号反転する第１のインバ
ータ６１と、座標データＸｔと第１のインバータ６１の
出力を加算する第１の加算器５１と、２ｍ＋１ビツトシ
フトされた座標データＸ１を符号反転する第２のインバ
ータ６２と、第１の加算器５１の出力と第２のインバー
タ６２の出力を入力して座標データＸ　　を出力する第
１＋１ ２の加算器５２とを有している。一方、第２の演算手段
は座標データｙ１とｍビットシフトさせた座標データｘ
１を加算する第３の加算器５３と、２ｍ＋１ビツトシフ
トされた座標データｙ１を符号反転する第３のインバー
タ６３と、第３の加算器５３の出力と第３のインバータ
６３の出力を加算する第４の加算器５４とを有している
。

この第１図の装置によれば、式（７）、（８）を二次近
似したものとして、 ｉ１１ ２ｍ−１ ＝（１−２）ｘ　　−２ｙ　　　　・（１３）Ｉ 一２１ｘ　　＋　（１−２−”−’　）　ｙ　　　　・
・・（１４）ｌ の回転運動漸化式が実行できる。この第１実施例によれ
ば、演算装置は各２段の加算器とこれに付設されたイン
バータで実現できるので、回転運動漸化式の演算が高速
に行なえる。すなわち、最も遅いパスでも２個の加算器
を通るだけなので、第６図の従来例と比べて同じ程度に
高速演算ができる。また、その誤差は第８図のように極
めて小さくなり、回転角ε−２−４程度で誤差率ｄ′を
０．４％以下にすることができる。

第２図および第３図は上記第１実施例の変形例をそれぞ
れ示している。第２図においては、第１図のものと異な
りインバータ６１，６２．６３が省略され、かつ加算器
５１，５２．５４がそれぞれ減算器５１ａ、５２ａ、５
４ａで置き換えられている。第３図においては、インバ
ータ７１゜７２．７３と３人力加算器８１．８２により
回路が構成されている。これらによっても、第１図の回
路と同様の演算を実行することができる。

次に、第４図を参照して本発明の第２実施例を説明する
。

この実施例が第１図ないし第３図のものと異なる点は、
第１の演算手段において３ｍビットシフトした座標デー
タｙ１を１／６倍にする第１の除算器６５と、第１の除
算器６５の出力と第２の加算器５２の出力を加算する第
５の加算器５５とが付加され、第２の演算手段において
３ｍビットシフトしてインバータ９９により符号反転さ
れた座標データｘ１を１／６倍する第２の除算器６６と
、第２の除算器６６の出力と第４の加算器５４の出力を
加算する第６の加算器５６が付加されていることである
。

この第２の実施例によれば、式（７）、（８）を三次遅
１以したものとして、 ｘ−＝　（１２−”’−’　）　Ｊ ＋＋１ −ｔｏ　　　−３ｍ ＋　（−２＋２　　　／６）　ｙ、・・・（１５）２ｍ
−１ ＋（１２）Ｖｌ　　　　　・・・（１Ｂ）の回転運動漸
化式が実行できる。これによれば、□ 加算器が各３段となり除算□器も必要になるので、ハー
ドウェアが第１実施例に比べて複雑であり、高速性もや
や低下する。しかし、演算精度を第１１図のように著し
く向上できる効果がある。

第５図は本発明の第１実施例に関連する他の例に係る演
算装置の回路図である。図示の通り、第１の演算手段は
座標データｙ１をｍビットシフト（Ｓ　　）させて反転
する第１のインバータ６１と、座標データＸ、と第１の
インバータ６１の出力を加算する第１の加算器５１と、
第１の加算器５１の出力を反転する第２のインバータ６
２と、座標データｘ１を２ｍ＋１ビツトシフトさせて入
力すると共に第２のインバータ６２のを出力を入力して
座標データＸ　　を出力する第２の加算器５２とを存し
ている。一方、第２の演算手段は座標データｙ９とｍビ
ットシフトさせた座標データＸ５を加算する第３の加算
器５３と、第３の加算器５３の出力を反転する第３のイ
ンバータ６３と、２ｍ＋１ビツトシフトさせた座標デー
タｙｌと第３のインバータ６３の出力を加算する第４の
加算器５４とを有している。

この第５図の装置によれば、式（１３）　、　（１４）
の回転運動漸化式が実行できる。

第６図は上記第１実施例に関連する第２の他の例を示し
ている。第６図においては、インバータ７１．７２．７
３と３人力加算器８１．８２により回路が構成されてい
る。これらによっても、第５図の回路と同様の演算を実
行することができる。

次に、第７図を参照して本発明の第２実施例に関連する
例を説明する。

この実施例が第５図および第６図のものと異なる点は、
第１の演算手段において３ｍビットシフトした座標デー
タｙ１を１／６倍にする第１の除算器６５と、第１の除
算器６５の出力と第２の加算器５２の出力を加算する第
５の加算器５５とが付加され、第２の演算手段において
３ｍビットシフトしてインバータ９９により符号反転さ
れた座標データｘ１を１／６倍する第２の除算器６６と
、第２の除算器６６の出力と第４の加算器５４の出力を
加算する第６の加算器５６が付加されていることである
。

この第２の実施例によれば、式（１５）、（１Ｂ）の回
転運動漸化式が実行できる。

〔発明の効果〕

以上、詳細に説明した通り本発明では、第１の演算手段
は座標データｘ　、ｙｌにもとづいて座標データＸ　　
を演算出力し、第２の演算手段は座標データｘ、ｙ、に
もとづいて座標データｙ１＋１を演算出力する。そして
、第１および第２の演算手段を加算器、インバータのみ
で構成すればハードウェアの簡単化と演算の高速化が図
られ、除算器を用いて構成すれば一層の高精度化が図ら
れる。このため、ハードウェア構成が簡単であって高速
演算が可能であり、しかも回転角を大きくしても誤差を
小さくできる回転運動漸化式の演算装置を提供すること
ができる。

【図面の簡単な説明】

第１図は本発明の第１実施例に係る回転運動漸化式の演
算装置の構成図、第２図および第３図は第１実施例の変
形例の構成図、第４図は本発明の第２実施例に係る回転
運動漸化式の演算装置の構成図、第５図ないし第７図は
他の例の演算装置の構成図、第８図は回転運動の説明図
、第９図は従来の回転運動漸化式の演算装置の構成図、
第１０図は誤差の発生の説明図、第１１図は近似精度を
比較する図である。 ５１・・・第１の加算器、５２・・・第２の加算器、５
３・・・第３の加算器、５４・・・第４の加算器、５５
・・・第５の加算器、５６・・・第６の加算器、６１・
・・第１のインバータ、６２・・・第２のインバータ、
６３・・・第３のインバータ、６５・・・第１の除算器
、６６・・・第２の除算器、８１・・・第１の３人力加
算器、 ２・・・第２の３人力加算器、 ９・・・イ ンバ ータ。

Claims (1)

1. 【特許請求の範囲】 １、ｘ・ｙ直交座標系で描かれる近似円の円周上の一点
   の座標を（ｘ＿ｉ、ｙ＿ｉ）とし、前記円周上の次の点
   の座標（ｘ＿ｉ＿＋＿１、ｙ＿ｉ＿＋＿１）までの回転
   角をε＝２＾−＾ｍとしたとき（但し、ｉは自然数）に
   、 ｘ＿ｉ＿＋＿１＝ｆ＿ｘ（ｘ＿ｉ、ｙ＿ｉ、ε）ｙ＿ｉ
   ＿＋＿１＝ｆ＿ｙ（ｘ＿ｉ、ｙ＿ｉ、ε）となる回転運
   動漸化式を前記回転角の１または複数回転角ごとに演算
   する回転運動漸化式の演算装置において、 前記座標データｘ＿ｉ、ｙ＿ｉを入力して ｘ＿ｉ＿＋＿１＝（１−２＾−＾２＾ｍ＾−＾１）ｘ＿
   ｉ−２＾−＾ｍｙ＿ｉの座標データを出力する第１の演
   算手段と、前記座標データｘ＿ｉ、ｙ＿ｉを入力して ｙ＿ｉ＿＋＿１＝２＾−＾ｍｘ＿ｉ＋（１−２＾−＾２
   ＾ｍ＾−＾１）ｙ＿ｉの座標データを出力する第２の演
   算手段と を備えることを特徴とする回転運動漸化式の演算装置。 ２、前記第１の演算手段は、座標データｘ とｍビットシフトされ符号反転された座標データｙ＿ｉ
   を入力する第１の加算器と、２ｍ＋１ビットシフトされ
   符号反転された座標データｘ＿ｉと前記第１の加算器の
   出力を入力して座標データｘ＿ｉ＿＋＿１を出力する第
   ２の加算器とを有し、 前記第２の演算手段は座標データｙ＿ｉとｍビットシフ
   トされた座標データｘ＿ｉを入力する第３の加算器と、
   ２ｍ＋１ビットシフトされた符号反転され座標データｙ
   ＿ｉと前記第３の加算器の出力を入力して座標データｙ
   ＿ｉ＿＋＿１を出力する第４の加算器とを有することを
   特徴とする請求項１記載の回転運動漸化式の演算装置。 ３、前記第１の演算手段は、座標データｘ＿ｉからｍビ
   ットシフトされた座標データｙ＿ｉを減算する第１の減
   算器と、２ｍ＋１ビットシフトされた座標データｘ＿ｉ
   を前記第１の減算器の出力から減算して座標データｘ＿
   ｉ＿＋＿１を出力する第２の減算器とを有し、 前記第２の演算手段は座標データｙ＿ｉとｍビットシフ
   トされた座標データｘ＿ｉを入力する加算器と、２ｍ＋
   １ビットシフトされた座標データｙ＿ｉを前記加算器の
   出力から減算して座標データｙ＿ｉ＿＋＿１と出力する
   第３の減算器とを有することを特徴とする請求項１記載
   の回転運動漸化式の演算装置。 ４、前記第１の演算手段は、座標データｘ＿ｉとｍビッ
   トシフトされて符号反転された座標データｙ＿ｉと、２
   ｍ＋１ビットシフトされて符号反転された座標データｘ
   ＿ｉをそれぞれ入力して座標データｘ＿ｉ＿＋＿１を出
   力する第１の３入力加算器を有し、前記第２の演算手段
   は座標データｙ＿ｉとｍビットシフトされた座標データ
   ｘ＿ｉと２ｍ＋１ビットシフトされて符号反転された座
   標データｙ＿ｉとを入力して座標データｙ＿ｉ＿＋＿１
   を出力する第２の３入力加算器を有することを特徴とす
   る請求項１記載の回転運動漸化式の演算装置。 ５、前記第１の演算手段は、 ｘ＿ｉ＿＋＿１＝（１−２＾−＾２＾ｍ＾−＾１）ｘ＿
   ｉ−（２＾−＾ｍ−２＾−＾３＾ｍ／６）ｙ＿ｉの座標
   データを出力し、 前記第２の演算手段は ｙ＿ｉ＿＋＿１＝（２＾−＾ｍ−２＾−＾３＾ｍ／６）
   ｘ＿ｉ＋（１−２＾−＾２＾ｍ＾−＾１）ｙ＿ｉ の座標データを出力することを特徴とする請求項１記載
   の回転運動漸化式の演算装置。 ６、前記第１の演算手段は、座標データｘ＿ｉとｍビッ
   トシフトされて符号反転された座標データｙ＿ｉを入力
   する第１の加算器と、２ｍ＋１ビットシフトされ符号反
   転された座標データｘ＿ｉと前記第１の加算器の出力を
   入力する第２の加算器と、３ｍビットシフトされて１／
   ６倍された座標データｙ＿ｉと前記第２の加算器の出力
   を入力して座標データｘ＿ｉ＿＋＿１を出力する第５の
   加算器とを有し、前記第２の演算手段は座標データｙ＿
   ｉとｍビットシフトされた座標データｘ＿ｉを入力する
   第３の加算器と、２ｍ＋１ビットシフトされ符号反転さ
   れた座標データｙ＿ｉと前記第３の加算器の出力を入力
   する第４の加算器と、３ｍビットシフトされて１／６倍
   され符号反転された座標データｘ＿ｉと前記第４の加算
   器の出力を入力して座標データｙ＿ｉ＿＋＿１を出力す
   る第６の加算器とを有することを特徴とする請求項５記
   載の回転運動漸化式の演算装置。 ７、前記第１の演算手段は、座標データｘ＿ｉとｍビッ
   トシフトされて反転された座標データｙ＿ｉを入力する
   第１の加算器と、２ｍ＋１ビットシフトされた座標デー
   タｘ＿ｉと前記第１の加算器の反転出力を入力して座標
   データｘ＿ｉ＿＋＿１を出力する第２の加算器とを有し
   、 前記第２の演算手段は座標データｙ＿ｉとｍビットシフ
   トされた座標データｘ＿ｉを入力する第３の加算器と、
   ２ｍ＋１ビットシフトされた座標データｙ＿ｉと前記第
   ３の加算器の反転出力を入力して座標データｙ＿ｉ＿＋
   ＿１を出力する第４の加算器とを有することを特徴とす
   る請求項１記載の回転運動漸化式の演算装置。 ８、前記第１の演算手段は、座標データｘ＿ｉからｍビ
   ットシフトされた座標データｙ＿ｉを減算する第１の減
   算器と、２ｍ＋１ビットシフトされた座標データｘ＿ｉ
   から前記第１の減算器の出力を減算して座標データｘ＿
   ｉ＿＋＿１を出力する第２の減算器とを有し、 前記第２の演算手段は座標データｙ＿ｉとｍビットシフ
   トされた座標データｘ＿ｉを入力する加算器と、２ｍ＋
   １ビットシフトされた座標データｙ＿ｉから前記加算器
   の出力を減算して座標データｙ＿ｉ＿＋＿１と出力する
   第３の減算器とを有することを特徴とする請求項１記載
   の回転運動漸化式の演算装置。 ９、前記第１の演算手段は、座標データｘ＿ｉとｍビッ
   トシフトされて反転された座標データｘ＿ｉ、ｙ＿ｉを
   それぞれ入力して座標データｘ＿ｉ＿＋＿１を出力する
   第１の３入力加算器を有し、 前記第２の演算手段は座標データｙ＿ｉとｍビットシフ
   トされた座標データｘ＿ｉとｍビットシフトされて反転
   された座標データｙ＿ｉとを入力して座標データｙ＿ｉ
   ＿＋＿１を出力する第２の３入力加算器を有することを
   特徴とする請求項１記載の回転運動漸化式の演算装置。 １０、前記第１の演算手段は、 ｘ＿ｉ＿＋＿１＝ｘ＿ｉ（１−２＾−＾２＾ｍ＾−＾１
   ）＋ｙ＿ｉ（−２＾−＾ｍ＋ε＾−＾３＾ｍ／６）の座
   標データを出力し、 前記第２の演算手段は ｙ＿ｉ＿＋＿１＝ｘ＿ｉ（２＾−＾ｍ＋ε＾−＾３＾ｍ
   ／６）＋ｙ＿ｉ（１−２＾−＾２＾ｍ＾−＾１） の座標データを出力することを特徴とする請求項１記載
   の回転運動漸化式の演算装置。 １１、前記第１の演算手段は、座標データ ｘ＿ｉとｍビットシフトされて反転された座標データｙ
   ＿ｉを入力する第１の加算器と、２ｍ＋１ビットシフト
   された座標データｘ＿ｉと前記第１の加算器の反転出力
   を入力する第２の加算器と、−３ｍビットシフトされて
   １／６倍された座標データｘ＿ｉと前記第２の加算器の
   出力を入力して座標データｘ＿ｉ＿＋＿１を出力する第
   ５の加算器とを有し、前記第２の演算手段は座標データ
   ｙ＿ｉとｍビットシフトされた座標データｘ＿ｉを入力
   する第３の加算器と、２ｍ＋１ビットシフトされた座標
   データｙ＿ｉと前記第３の加算器の反転出力を入力する
   第４の加算器と、−３ｍビットシフトされて１／６倍さ
   れた座標データｘ＿ｉと前記第４の加算器の出力を入力
   して座標データｙ＿ｉ＿＋＿１を出力する第６の加算器
   とを有することを特徴とする請求項１０記載の回転運動
   漸化式の演算装置。