JPH03127282A - ディジタル・イメージのランド変換装置および方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はディジタル・イメージ処理の分野のものであり
、詳細にいえばラスタ走査信号を有するディジタル・イ
メージのラドン変換を行なうためのパラメータ付き処理
に関する。

Ｂ、従来の技術 イメージ表示技術において、ラスタ表示装置はイメージ
を一連の構成画素（「ピクセル」または「ペル」）とし
て表す。イメージを形成しているラスタは一般に水平の
ラスタ・ラインないしピクセルの行に配列されたピクセ
ルのアレイを含んでいる。列もラスク上に画定され、こ
れによってイメージ表示域を充填するピクセルの２次元
マトリックスを確立する。イメージは表示域の上のコー
ナーから下の反対側のコーナーまで、画素を順次１行ご
とに走査することによって生成される。次いで、この操
作をマトリックスの上のコーナーまで再トレースするこ
とによって繰り返す。

表示域上のラスク走査イメージは、ラスク上で走査され
るビームの変調によって形成され、ビームの輝度はピク
セルがイメージ全体に及ぼす寄与にしたがって、各ピク
セル位置で変調される。

ディジモルうススクによるイメージの表示において、一
般に個々の記憶位置とラスク内のピクセル位置との間に
１対１の対応を有するピクセル・マツプの形式の記憶域
が設けられる。各ピクセル記憶位置はピクセル位置にお
けるイメージの輝度の複数ビットの表示（通常はバイト
）を含んでいる。

ディジタル化されたイメージのラスク形式は表示された
イメージの高速処理を、このような処理に敏感な中間情
報形態を生、じる多数の離散変換法のいずれかによって
サポートする。周知のものとしては、離散フーリエ変換
（ＤＦＴ）があるが、これをディジタル・イメージのフ
ーリエ空間への高速変換を行なうために、バイブライン
式アーキテクチャで適宜実施できる。

ディジタル化イメージの分析に用いられている特に重要
な変換はラドン変換で、これはたとえばＸ線断層撮影の
形態で医療診断に応用されている。

２次元の物体が一連の１次元のプロジェクシ日ンから再
構成されるラドン変換の他の応用例には、電波天文学、
電子顕微鏡、光学インターフェロメトリ、及び物理探鉱
がある。最近、ラドン変換が、ディジタル・イメージを
ラドン空間に変換しなければならない一般的なイメージ
処理に有利であることが示されるようになった。ラドン
空間の表示及び走査の各種の機械視覚の問題に対する顕
著な影響は、たとえば、Ｊ−Ｌ−Ｃ−サンツ（Ｓａｎｚ
）他の「ラドン及びプロジェクシｅン変換に基づくコン
ピュータ視覚（Ｒａｄｏｎ　ａｎｄ　Ｐｒｏｊｅｃｔｉ
ｏｎＴｒａｎｓｆｏｒｍ−Ｂａｓｅｄ　Ｃｏｍｐｕｔｅ
ｒ　Ｖｉｓｉｏｎ）　Ｊ　％　Ｓｐｒｉｎｇｅｒ−Ｖｅ
ｒｌａｇｓ　　１９８８年という刊行物に示されている
。

この刊行物はディジタル・イメージのラドン変換に対す
る近似値の迅速な計算を教示している。オーヤマ（Ｏｈ
ｙａｍａ　）他の「連続空間における離散ラドン変換（
Ｄｉｓｃｒｅｔｅ　Ｒａｄｏｎ　Ｔｒａｎｓｆｏｒｍ　
ｉｎ　ａＣｏｎｔｉｎｕｏｕｓ　５ｐａｃｅ）　Ｊ　１
ＪＯＳＡ％　１９８７年２月、ｐＩ）、３１８−３２４
において、イメージのラドン・プロジェクションを合成
するために、変換矩形関数を使用すると、正確な結果が
得られると断言されている。したがって、変換矩形から
なるイメージ・モデルに対してラドン変換の正確な結果
をもたらす装置及び手順は、当技術分野において歓迎さ
れる進歩となる。

Ｃ６発明が解決しようとする課題 したがうて、本発明の目的はラスク走査されたディジタ
ル・イメージをラドン空間のプロジェクシθンに変換す
る改善された方法を提供することである。

００課題を解決するための手段 本発明はラスク走査されたディジタル・イメージをラド
ン空間の対応する表現に変換する改善された方法に関す
る。対応する表現をプロジェクションと呼ぶ。これらの
表現は、線積分が希望するラドン・プロジェクシｅンを
形成する光線によって生成される。矩形近似関数を使用
して、光線を特徴づけることによって、正確な変換が行
なわれることが判明した。

ディジタル・ラドン変換プロセッサにおいて、ピクセル
化されたディジタル・イメージのラドン・プロジェクシ
ョンが、ディジタル・イメージをラスク走査形式で与え
、各イメージ・ピクセルに対して、プロジェクシ１ンの
線積分がそれに沿って取られるところの光線に対応する
プロセッサの記憶位置を決定することによって得られる
。この場合、この記憶位置に対して、対応する光線のピ
クセルと交差する部分の長さには、ピクセルの輝度が乗
じられ、記憶位置の内容はその積だけ増分される。

Ｅ、実施例 ２次元関数ｆ　（ｘ、ｙ）のラドン変換は２次元関数Ｐ
ｅ（ｚ）として定義される。

ただし、 ２およびｅの所与の値に対して、式（１）はプロジェク
タぴｙ軸の原点から距離２のところにある、ｙ軸に対し
て角ｅをなしている線に沿ったｆ（ｘ、Ｖ）の線積分を
表す。向きｅのすべてのこのような線積分の集合を、こ
の向きにおけるｆ（ｘ　＋　Ｖ　）の「プロジェクシ評
ン」という。線積分の集合はｆ　（ｘ、ｙ）の２次元ラ
ドン変換をもたらす。式（１）を理解するには、第１図
参照。

第１図において、任意の２次元イメージ平面が直交する
Ｘ軸及びｙ軸によって表されている。Ｘ。

ｙ空間におけるイメージは楕円のイメージ１０である。

楕円１０は２次元の表示に通常な形態の、関数ｆ　（Ｘ
、”１）で記述される。イメージ１０のプロジェクショ
ンは参照番号１２で示されており、プロジェクション軸
１４に関してイメージが形成されている。プロジェクシ
ョン１２はイメージ１Ｏを記述する関数の線積分をすべ
て統合することによって構成されるが、積分は１つが１
６で示されている線すなわち光線に沿って取られる。光
線の各々はｙ軸と角ｅをなしている。それゆえ、第１図
において、プロジェクタｅ７１２はイメージ１０を表す
関数の２次元ラドン変換である。したがって、曲線１２
をイメージ１０のラドン・プロジェクタ３ンであるとい
うことができる。

ここで、第１０図のイメージが連続しておらず、ラスタ
に配列されたピクセルで構成されていると断言する。こ
れに関連し、イメージを「ディジタル」イメージといい
、関数ｆ（ｉ、ｊ）で記述される。第１図の線積分のデ
ィジタル近似値の計算は、矩形関数の格子、すなわちピ
クセルのラスタに対応する格子として、イメージ１０を
モデル化することによって支援される。このモデルは次
の式（２）によって充分に予測される。

Ｐｅ（ｚ）＝Σｄ、。−ｇｒａｙｌｅｖｅｌｐａ　＋　
　　　（２）ただし、アスタリスクは乗算を示し、和は
Ｚ＝Ｘｃｏｓｅ＋７ｓｉｎｅなとの光線２が切るすべて
のピクセルに対するものである。このブロジェクシｅン
を離散形式としたものは、２を適切に量子化することに
よって与えられる。式（２）の幾何学的解釈については
、第２図を参照されたい。

第２図において、ディジタル・イメージはＸ。

ｙ空間において、ピクセル２０のラスタによって表され
る。ラスタ２０の部分はピクセル２１−２５を含んでい
る。各ピクセルは座標（ｒ＊ｃ）によって示されている
。ただし、ｒはピクセルが配置されているラスタの行を
示し、Ｃは列を示す。

それゆえ、ピクセル２１はラスタ２０の行０１列Ｏにあ
る。各ピクセルは輝度を有しており、これはグレー・ス
ケールで表すこともできる。光！２８はラスタ２０によ
って表されるイメージの線積分が取られる光線の１つで
構成されている。本発明の態様において、光線２８に沿
った線積分は光線の線積分のすべてのセグメントを合成
することによって得られる。線積分セグメントとは、そ
れぞれ−のピクセルを切る光線２８の部分の長さに、切
られたピクセルの輝度を乗”じたものである。それゆえ
、光線２８に沿った線積分を得るには、光線のセグメン
トの長さｄｈｄ２、ｄ３、ｄ４、ｄ５などを求め、各々
にこれが切るピクセルの輝度を乗じなければならない。

得られる積を合計し、この光線に対する線積分を得る。

すべてのこのような線積分の集合は、イメージのプロジ
ェクシｅンを確立するプロジェクション軸３１に沿った
点の集合を定義する。概念上、線積分を先端が接続され
て、イメージのプロジェクシａンを形成する、プロジェ
クション軸３１に沿った一連のヒストグラムの集合で表
すことができる。プロジェクシゴンの滑らかさはヒスト
グラムの間の間隔で決定される。

プロジェクション軸３１における線積分の位置は、積分
を生成する光線による軸の切断と一致している。このパ
ラメータを光線の２切片という。

図示のとおり、２の大きさはｘ−ｙ空間の右側の象限か
らｙ軸の方向へ増加する。

第１図及び第２図に関する最後の考慮事項は、ラドン変
換が角ｅのそれぞれの値に対するものである−群のプロ
ジェクシｅンの判定を含んでいることである。ディジタ
ル・イメージ処理の分野の技術者には、ラドン変換プロ
セッサのアーキテクチャ上の並行性を活用して、Ｏの特
定の値に対するプロジェクタ１ンが計算される各ステー
ジにおけるパイプラインを通して、ディジタル・イメー
ジを送ることによって、ｅのすべての値の計算を並行し
て行なえることが明らかであろう。

第２図の近似値を使用したディジタル・イメージに対す
るｅの任意の値におけるプロジェクシｅンの効率的な計
算が、浮動小数点及び固定小数点の両方に対し、本発明
で提供される。いずれの場合においても、光線の和を考
慮するには、ディジタル・イメージが記憶されているメ
モリのランダム・アクセスが必要であると思われる。周
知のように、ランダム・アクセスは並行変換プロセッサ
のスルーブツトを減少させる。しかしながら、ラスタ形
式のディジタル・イメージを活用することによって、イ
メージへのランダム・アクセスを回避でき、またｅの異
なる方向での多くのプロジェクションの計算のパイプラ
イン化を、イメージを表すラスタの１回の通過で行なう
ことができる。

なお、ディジタル・イメージの「ラスタ処理」とは、デ
ィジタル・イメージを構成しているピクセルに課される
ラスタ・シーケンスに対応するアルゴリズム上のシーケ
ンスで変換を行なうことを意味する。

処理パイプラインの任意のステージにおけるプロジェク
シｅンの計算にラスタ処理を使用するには、θの各値に
おけるすべての光線の部分和の維持及び蓄積が必要であ
る。ディジタル・イメージ内の各ピクセルに順次アクセ
スすると、このピクセルと交差する光線に対する該当す
る光線和が、更新される。以下の説明において、部分光
線和の記憶位置を「パケット」と呼ぶ。それゆえ、第２
図を再度参照すると、プロジェクシａンに対するθの値
における光線２８の部分和は、ラスタ２０内のピクセル
に対する光線セグメント長／輝度の積を、これらのピク
セルが発生した順に蓄積することを含んでいる。それゆ
え、ピクセル・アレイ２０を行Ｏから始まる行順でアド
レスすると想定すると、光線２８に対する部分和はまず
、ピクセル２１の輝度を乗じた積ｄ１を記憶し、これに
ｄ２とピクセル２２の輝度の積、ｄ３とピクセル２３の
輝度の積、ｄ４とピクセル２４の輝度の積、ｄｓとピク
セル２５の積などを加える。部分光線和に記憶域を設け
ると想定すると、−意の「パケット」が光線２８の光線
和を蓄積するための記憶域に設けられる。

イメージを光線を使用して変換し、イメージをラドン空
間にプロジェクションにマツプすると、対応するラドン
・イメージの他の処理が想定され、たとえば、イメージ
・オブジェクトの位置を断定するか、プロジェクション
をフィルタして、イメージの雑音を軽減するかする。

亙且里 本発明はピクセルのラスタによって表されるディジタル
・イメージのラドン変換で遭遇する２つの顕著な問題を
解決する。最初の問題はどのパケットを各ピクセルに対
して更新するかを決定することである。第２の問題は各
ピクセルとの光線の交点の長さの決定に関するものであ
る。

パケットを求める問題の解を理解するために、第３図を
参照されたい。第３図において、直交するＸ軸３６及び
ｙ軸３７は、ディジタル・イメージのプロジェクション
が生成される２次元の領域を画定する。プロジェクショ
ン軸は３８で示される。プロジェクシａンは光線４０及
び４１を含んでいる光線に沿って取られた線積分によっ
て生成される。軸３８上の光線の位置は２に対する値に
よって示され、２の大きさはそのＸ輪切片からｙ輪切片
への方向へ軸３８に沿って増加する。変換されるディジ
タル・イメージはピクセル４３及び４４を含むラスタの
形態である。各ピクセルの中心は（ｘ、Ｙ）である。１
つまたは複数の光線がピクセルを切ることがわかる。第
３図はピクセル４３を切る２つの光線４０，４１を示し
ている。

光線４０及び４１の「パケット」は、それぞれのプロジ
ェクシＢン軸切片４６及び４８によって画定される。こ
の場合、問題はピクセル４３をアドレスした場合に、切
片４６及び４８の値を得ることである。

パケットを求める問題の解は上述したように、光線４０
及び４１の間の、したがってプロジェクションを形成す
るすべての光線の間の均等な間隔を想定している。ピク
セル４３の中心（ｘ＊ｙ）を通る線５０の式は、次の式
（３）によって与えられる。

ｚ　＝　ｘ：ｃｏｓｅ　＋　ｙ掌５ｉｎｅ　　　　　　
　　　（３）プロジェクション軸への第１のピクセル４
３の中心のプロジェクションは、軸の原点５１をもたら
す。ピクセル４３の右上及び左下のコーナーを、プロジ
ェクション５２及び５３で示すように軸３８にプロジェ
クトすると、上下の切片（パケット）４６及び４７は次
の式（４）及び（５）で与えられる。

ｚｕ　＝　ｆｌｏｏｒ（（ｘ−，５）＊ｃｏｓｅ＋（ｙ
◆、５）＊ｓｉｎθ＋２）（４） ｚｌ　＝　ｃｅｉｌ（（ｘ＋、５）＊ｃｏｓｅ＋（ｙ−
，５）＊５ｉｎｅ＋ｚ）（５） ただし、関数ｆｌｏｏｒ（ｘ）はＸ以下の最大の整数で
あり、関数ｃｅｉｌ（ｘ）はＸ以上の最小の整数である
。式（４）及び（５）が各ピクセルに対する最大及び最
小のパケットをもたらすことが理解されよう。これは最
大のパケットを指すＺＵ及び最小のパケットを指すｚｌ
という名称によって表される。複数の光線がピクセルを
通過する場合、最大及び最小のパケットに対する値及び
対応する記憶位置によって、これらのプロジェクション
軸の切片及び対応するパケットの記憶位置は、ｚｌ、ｚ
ｌ＋１１．、、、ｚｕとなる。１つの光線だけがピクセ
ルを通過する場合、ｚｌは２Ｕと等しくなる。

第４図において、ピクセル４３の左下コーナーのプロジ
ェクション５２を決定した場合、決定された値はこのコ
ーナーのプロジェクション軸切片に対応する。ピクセル
を通過する光線のパケット位置を計算する場合、この切
片は２とパラメータ化される。ピクセル４３の左下の２
切片を、ピクセルの右上のコーナーのものから引くと（
第４図参照）、任意の固定角ｅに対する定数ｌ　ｃｏｓ
ｅ１＋１８ｉｎｅｌが得られる。三角関数の絶対値を使
用して、値のいずれかまたは両方が負となる象限に合わ
せる。ピクセル４３の左下コーナーのプロジェクション
の２切片がわかると、この定数を切片４３に加えるだけ
で、右上のコーナーの２切片が求められる。この情報は
ピクセルが式（４）及び（５）のそれぞれのｆｌｏｏｒ
及びｃｅｉｌ関数を使用して更新する必要のある上部及
び下部パケットの決定を容易とする。

最後に、各ピクセルの左下コーナーの２切片を計算する
簡単な手順が、再度第３図を参照することによって理解
できよう。第３図において、中心がプロジェクション軸
の原点５１を画定するピクセル４３の左下コーナーのプ
ロジェクションの２切片によって、始点が与えられる。

この場合、始ある。

隣接するピクセル４４の左下コーナーが第４図において
、ピクセル４３の左下コーナーのプロジェクション軸に
沿って距離ｃｏｓｅだけ離隔したものとして示されてい
る。

それゆえ、始点が次のピクセルが与えられるたびに連続
的にｃｏｓｅだけ増加するのであれば、次のピクセルの
左下コーナーの２切片は、第４図に示した関係によって
得られる。この手順を第１表で与えられる手順にしたが
って、ラスタの行の１つに沿ったピクセルのすべてにつ
いて繰り返すことができる。

第１表 ２゜ ３゜ ４゜ ｚｕ＝Ｎｏｏｒ（ｓａ）　／掌これはこのベルを通過す
る最大のパケットを与える＊／ Ｚｌ＝ｃｅｉｌ　（ｓａ−Ｉｃｏｓ　ｅ　ｌ−１ｓｉｎ
　（３ｌ）／：これはこのペルを通過する最小のパケッ
トを与える＊ｌ−現行のピクセルを切る各パケットの出
力の識別記号ｉｓ　ｚｌ≦ｉ≦ｚｕ テ、　次のピクセルを受は取る ６、　　５ａ＝ｓａ＋ｃｏｓ　ｅ／掌ここで、次のベル
のために更新するキ／ ？、ｇｏｔｏ２ 現行行の最後の（最も右側の）ピクセルがもたらされ、
次の行が始まった場合、第１表の手順を各行の始点、す
なわち行の最初の（最も左側の）ピクセルに対する区切
片を保管するようにすることができる。この場合、次の
始点を得るために必要なのは（第４図参照）、直前の行
の始点に５ｉｎｅを加えることだけである。次いで、次
の行の処理は第１表で与えられるように進行する。ある
いは、現行行の最後のピクセルに到達したときに、現行
位置に−Ｎ（ｃｏｓｅ＋ｓｉｎθ）を加えることによっ
て、次の行の始点を得ることができる。

もちろん、これは各行が正確にＮ個のピクセルを含んで
いると想定している。

次に、本発明では現行のピクセルを切る各光線セグメン
トの長さを求める。現行のピクセルを切る光線の区切片
が既知の場合、この光線に対する直線の式はｚ＝ｘ　（
ｃｏｓｅ）　十ｙ（ｓ　１ｎｅ）で与えられる。ただし
、ピクセルの中心は（Ｘ　＋ｙ）である。ピクセルの中
心（ｘ、ｙ）の区切片がｘ＊ｃｏｓｅ＋Ｙ＊ｓ　ｉｎｅ
であることがわかると、この位置がピクセルの左下コー
ナーにおけしい一定量だけ常に異なっていることもわか
る。

それゆえ、光線のパケットを求める手順では常にピクセ
ルの左下コーナーの区切片がわかるので、簡単な加算を
使用して、ピクセルの中心の区切片を得ることができる
。本発明において、ピクセルとの光線の交差部の長さは
、第３図に示す距離デルタ、によってパラメータ化され
る。交差部の長さｄは関数２−２の関数である。ただし
、２はプロジェクタ１ン軸切片４８であり、ｉはｚ１≦
ｉ≦ＺＵという２の任意の整数値を表す。図形で表した
場合、この距離の関数は原点を中心とした対称形となり
、第５図に示す形状を有している。第５図において、垂
直軸６０はピクセルを切る光線セグメントの長さに対応
しており、水平軸６２はピクセルの中心からの距離を表
す。第５図において、距離の関数は３つのパラメータ、
すなわちｄｍａＸＮ　ｂｒｅａｋｐｎｔｌ及びｃｕｔｏ
ｆｆで表される。これら３つのパラメータは角ｅの関数
であり、角度の任意の値に対して一定である。これらの
パラメータは下記の式（６）、（７）及び（７）で与え
られる。

ｂｒｅａｋｐｎｔ＝ （７） 距離ファインダの公式によって、区切り点及びカットオ
フの値の間の直線の式の計算、ならびに直線の勾配及び
切片の獲得が簡単になる。当分野の技術者には、パケッ
トｚｌ及びＺＵによって識別される光線がピクセルを通
過するのであるから、第５図に示す距離ファインダ関数
がカットオフ値を超えることがないことは明らかであろ
う。ｚｌとＺＵの間の各整数バケツ）Ｚについて、第５
図の距離関数が本発明においてｌ　Ｚ−Ｚ　Ｉを使用し
て評価される。したがって、距離は下記の第■表の簡単
な手順を使用して得られる。

第■表 １、　　ｉｆ　（（Ｉｚ−ｉｌ）≦ｂｒｅａｋｐｎｔ）
　ｔｈｅｎ　ｄ＝ｄｍａｘ２、ｅｌｓｅｄ＝勾配＊１ｚ
−ｉｔ＋切片距離関数をピクセルの左下コーナーの区切
片からの距離の関数としてパラメータ化でき、これが２
を求めるための加算を回避することがわかる。

しかしながら、この場合、距離関数はもはや原点を中心
とする対称形ではなくなり、距ｗ１ｄを評価するのに２
つのテスト及び２つの式を必要とするようになる。好ま
しい実施例においては、第■表の手順が使用される。

本発明を実施するのに必要な関数要素の基本セットを、
３つのピクセルと組み合わせて第６図に示すが、これは
ディジタル・イメージを含んでいるピクセルのラスタの
一部である。３つのピクセル８０．８１、及び８２はラ
スタの２つの隣接する行にある。ラスタは行ごとに左か
ら右へ、上から下へ掃引され、各行の終わりで水平同期
信号Ｈ８ＹＮＣＨが活動化され、次の行の始まりを示す
。

最も下の行の最後の最後のピクセルに達すると、垂直同
期信号ＶＳＹＮＣＨが活動化されて、走査装置をブラン
クとするとともに、走査を最初の行の最初のピクセルに
戻す。各ピクセルは列及び行の表示（ｃ、ｒ）を有して
おり、アレイのピクセルはピクセル・クロックが示す速
度でメモリまたは変換器のいずれかからもたらされる。

ディジタル・イメージ処理分野の技術者には、Ｈ８ＹＮ
ＣＨ，ＶＳＹＮＣＨ及びピクセル・クロックの信号が周
知のものであり、市販の手段によってもたらされること
が理解されよう。

本発明はピクセル８０−８２が一部となっているラスタ
によって表されるディジタル・イメージのラドン変換を
行なろ。得られる変換は上述の線積分手順によって生成
されるプロジェクシゴンの形態となる。それゆえ、各ピ
クセルに対し、本発明は遮断光線（パケット）及びピク
セルを切る光線セグメントの長さを決定する。これらの
関数は図のブロック８４及び８５によって示される。ブ
ロック８４は上部及び下部の光線、すなわちｒａｙｕ及
びｒａｙ　　ｌのそれぞれを決定するが、これらは切片
ＺＵ及びｚｌに対応している。ブロック８４は上記の第
工表に示したように現行のピクセルを切る各光線も決定
する。ブロック８４は現行の光線、ｒａｙｊを識別し、
現行の光線の識別記号を周知のアドレス・ジェネレータ
８７に与える。

アドレス・ジェネレータ８７は現行の光線の識別記号を
、ｒａｙｌに沿って取られた線積分の部分和が蓄積され
るレジスタの記憶アドレスＲ（ｌに変換する。レジスタ
は第６図において、読み書き（ＲＷ）サイクルでアクセ
スできるアドレス可能高速記憶アレイとして示されてい
る記憶アレイ８９に含まれている。θの特定の値に対し
て生成されるプロジェクシ替ン内の各光線は、記憶アレ
イ８９内に対応するレジスタを有している。

ｒａｙ、に沿った線積分の部分和は、ピクセル８０を切
る光線のセグメントであるｒａＹ、のｎ番目のセグメン
トの長さｄ（ｎ、ｊ）をまず決定することによって増加
させられる。この長さは第５図に関連して上述した手順
にしたがって決定され、長さジェネレータ８５によって
もたらされる。ｄ（ｎ、ｊ）について計算される値はピ
クセル８０の輝度の値とともに、高速乗算器９１に与え
られ、この乗算器はｒａＹｉのｎ番目のセグメントの長
さと、ピクセル（ｘ、ｙ）の輝度の積を生じる。この積
はレジスタＲ（Ｊ）の内容とともに、加算器９３に与え
られる。加算器９３の出力は１番目の光線の線積分の部
分和を蓄積するレジスタのアドレスＲ（ｊ）において、
記憶アレイ８９に記憶される。

第７図は第６図に示した本発明が作動することを目的と
する作動環境を示す。第７図は上述のサンツ他の刊行物
で図示説明したパイプライン式並行処理アーキテクチャ
に対応している。この構造は本質的に、変換プロセッサ
１００で構成されており、このプロセッサはピクセル化
イメージ・ジェネレータ１０２によってもたらされるピ
クセル化イメージの変換処理を行ない、イメージを処理
して周知の表示装置１０８に表示する。ピクセル化イメ
ージ・ジェネレータ１０２はラスタ走査形式で与えられ
るバイト・マツプの形でピクセル化イメージを記憶し、
提供するメモリを含むことができる。このように提供し
た場合、信号経路１０４にもたらされる各ピクセルの輝
度値１を有するディジタル・イメージがピクセルごとに
もたらされる。

さらに、ジェネレータ１０２は、信号経路１０４にもた
らされるピクセル輝度値のシーケンスと同期して、周知
のピクセル信号Ｃｒ及びＣｃを多心信号経路１０５にも
たらす。これらの信号は行と列のクロックに過ぎなくて
もよいものであって、これらのクロックはそのラスタ切
片によってピクセルを識別する。

上記の説明と一貫させるため、ＣｒはＨ８ＹＮＣＨ信号
に対応しており、各ラスク行に一回パルスを発生する。

Ｃｃはピクセル・クロックに対応する。

ジェネレータ１０２によってもたらされるピクセル・シ
ーケンスは、３つのステージが１１０．１１１及び１１
２によって示されているｍ個のステージからなる変換プ
ロセッサ・パイプラインに提示される。ピクセルはプロ
セッサ・パイプラインを通して、パイプライン・バス１
１４上を順次供給される。プロセッサの各ステージはジ
ェネレータ１０２によってもたらされるイメージのラド
ン変換を生じるのに使用される、それぞれのプロジェク
ションを生成する。変換プロセッサのパイプライン構成
は、ｍ番目のピクセルと交差する光線に対する部分和が
ステージ１１０で更新された場合に、アレイの最初のピ
クセルと交差する光線に対する部分和が生成されて、パ
イプライン・ステージ１１２のこれらの光線に対する部
分和を更新することを意味する。変換プロセッサはホス
ト・プロセッサ１１６を含んでおり、このプロセッサは
通信経路１１７でイメージ・ジェネレータ１０２と通信
し、かつホスト・バス１１８上でプロセッサ・パイプラ
イン・ステージに接続されている。

ホスト・プロセッサ１１６は生成されるプロジェクシｅ
ンに対するｅの値を生成し、完了したときにラドン空間
において希望する処理を行なうプロジェクションを取得
する。処理結果はホスト・プロセッサによって、表示装
置１０８に与えられ、処理されたディジタル・イメージ
を表示する。

第８図は変換プロセッサ１００のプロセッサ・パイプラ
インのステージの１つの構成要素を示しているが、これ
らの構成要素は本発明の実施に必要なものである。第８
図に示されているステージのアーキテクチャは、変換プ
ロセッサ１００のプロセッサ・パイプラインのステージ
の各々に適用されるものである。ステージ・アーキテク
チャは信号ライン１２２及び１２３でＣｒ及びＣ０信号
を受は取るパケット・ジェネレータ１２０を含んでいる
。パケット・ジェネレータ１２０は信号ライン１２８で
値ｅも受は取る。入力信号に応答して、パケット・ジェ
ネレータ１２０は第■表及び第■表にしたがって作動し
、第５図に関連して上述した距離予測手順を用いて、２
つの信号を発生する。

与えられる最初の信号は、第８図において丁と示されて
いる２切片による現行の光線の識別記号である。上述の
ように、現行の光線ｒａｇ、について、光線の２切片ｉ
はこの光線に対する線積分の部分和を含んでいるレジス
タのパケットないしアドレスＲ（ｊ）に対応している。

この値は信号ライン１３２に１０ビツト・ワードとして
与えられる。

最後に、パケット・ジェネレータは８ビツト・ワードと
して、現行のピクセルと交差する光線のセグメントであ
るｒａｙｊのｎ番目のセグメントの長さに対する振幅値
ｄ（ｎ、ｊ）をもたらす。

第８図のアーキテクチャは索引テーブル（ＬＵＴ）も含
んでおり、これは信号ライン１２１に現行の輝度値ｉに
対応する８ビツト・ワードを受は取り、また信号ライン
１３３に８ビツト・ワードモ受ケ取ル。ＬＵＴ　１３５
は周知の構成とされ、信号ライン１２１及び１３３でこ
れに与えられる値の索引乗算を行ない、これに応じて、
その積を信号ライン１３７にもたらす。

さらに、プロジェクシｅン・データ・コレクタ１３８は
グレー・レベル・ハードウェア・ヒストグラマと同等な
態様で作動し、アドレス可能記憶空間はこのステージで
生成されるプロジェクタ１ンを形成する光線のすべてに
対する部分和の値を記憶し、更新できる。プロジェクシ
ョン・コレクタ１３８は、ピクセル・クロック速度の倍
数である速度でそのレジスタを更新できる。更新はレジ
スタＲ（ｊ）の内容を獲得し、これらを信号ライン１３
７上の値だけ増分し、増加した値をレジスタＲ（ｊ）に
記憶することからなる。

第■表はソースのＣ言語で表したパケット・ジェネレー
タ及び索引テーブルの機能特性を示すもので、これを使
用して、第８図に示すようなパケット・ジェネレータ及
び索引テーブルを構成するのに必要なプログラミンダを
生成することができる。

第■表においては、変形プロセッサのパイプライン・ス
テージが変形プロセッサによって並列に実行されるプロ
グラム・モジュールであると想定されている。第■表は
固定小数点演算を使用して、ｅの任意の値における任意
の大きさのディジタル・イメージのプロジェクシｅンを
計算する。

第１表及び第■表のパケットを求める手順を適応させる
には、式（４）及び（５）を固定小数点数に適合させる
必要がある。任意の数ｙを有理関数Ｖ＝ｘ／２”（固定
小数点表記であり、Ｂは端数ビットの数であり、「２進
小数点」と呼ばれる）として表せるので、単純な論理プ
リミティブを使用して、ｆｌｏＯｒ及びｃｅｉｌ関数を
実現することが簡単に行なえる。すべての端数ビットが
マスクされた場合、ｆｌｏｏｒ関数がｆｌｏｏｒ（ｘ）
−ｘ＆−（２Ｂ）（ただし、＆はビット・ワイズな論理
ＡＮＤ演算を示す）で与えられることを利用する。この
ように適応した場合、ｆｉ。

Ｏｒはｆｌｏｏｒ（Ｘ）／２Ｂが整数であることを意味
する。パケットが常に整数値に対応しているので、この
ようなビット・マスキングは不必要となり、所望の整数
値のパケットをパケット値の高位ビットを吟味するだけ
で得ることができる。

ｃｅｉｌ関数は整数ステップよりも若干少なく増分し、
かつ結果をｆｌｏｏｒ関数に適用することによって得ら
れる。それゆえ、ｃｅｉｌ（ｘ）＝ｆ　１ｏｏｒ　（ｘ
＋２Ｂ−１）となる。

次に、浮動小数点手順のパラメータを、固定小数点表示
に変換する。ｓｉｎ及びＣＯＳが±１の間の値に制限さ
れるので、これは簡単なプロセスである。パケットを求
める手順の固定小数点表示は、正規の２の補整数演算を
使用することを除けば、浮動小数点と同一である。固定
小数点のパケットを求める手順が切捨て誤差のため、間
違ったパケットを選択する場合があることが認められる
。

この場合、正しくないパケットが更新されることになる
。さらに、更新される量がピクセル値の関数であるから
、この劣化効果はデータに依存することになる。パケッ
ト・ファインダの誤りがラインの終わり近くではより多
くなることがある。これは近似増分を加算した累積切捨
て誤差によるものである。これらの理由から、最良なの
は、固定小数点表示で適切な数のビットを使用すること
である。

距離ファインダを固定小数点手順に変換するのに必要な
のは、パラメータｄｍａｘ１ＣｕｔｅｒＬ　ｂｒｅａｋ
ｐｎｔｓ　ｓ　１ｏｐｅ及びｔｎｔｅｒｃｅｐｔを固定
小数点で表し、固定小数点演算を使用することだけであ
る。距離ファインダ及び固定小数点演算を実施すること
で、切捨てによる誤差が生じることが認められる。しか
しながら、距離ファインダの切捨て誤差の効果は、正し
いパケットを選択することを想定すると、パケットを若
干小さい、あるいは大きい値だけ増加させることとなる
。当分野の技術者には、これがパケット・ファインダの
誤りによって生じるような間違ったパケットを増加させ
た場合はど大きな誤差でないことがわかろう。したがっ
て、距離を求める計算で必要なビット数は、パケットを
求める計算の場合よりも少なくなる。これには乗算する
オペランドのサイズを小さくするといつ利点があり、第
８図に示したよつなテーブル索引操作として乗算の実施
を実用的なものとする。

次に第■表において、パケット・ファインダ１２０とＬ
ＵＴ　１３５はイメージ・ピクセルがアドレス可能位置
に記憶され、ラスク順に読み出されるバイト・マツプを
含むピクセル化イメージ・ソースから、ラスク走査順に
イメージ・ピクセルを受は取る。

００ ０１ ０２ ０３ ０４ ０５ ０６ ０７ ０８ ０９ １０ 第ｍ表 ｄｅｆｉｎｅ　ＤＴＯＲｙｒ／１８０．０＃ｄｅｆｉｎ
ｅ　ｄｂｉｔｓ　８ ＃ｄｅｆｉｎｅ　ｂｂｉｔｓ　１６ ｈｐｒｏｊ（ｐｉｃｔｕｒｅ、　ｔｈｅｔａ。

ＩＭＡＧＣｐｆｃｔｕｒｅ； ｄｏｕｂｌｅ　ｔｈｅｔａ： ｉｎｔ宰ｐｄａｔａ； （ ｉｎｔ ＰＥＬ８　　　宰ｐｉｘｅｌ： ｉｎｔ　　　ｏｆｆｓｅｔ、　ＸＩ　ｙ；ｖｄ、ｈＬｎ
ｐｏｉｎｔｓ＋ｉ； ｐｄａｔａ） １１ １１２ １３ １４ １５ １６ １７ １８ １９ ２０ ｉｎｔ　ｚｌ：／：ベルを通過する下位パケットの番号
寧／ Ｉｎｔ　ｚｕ；／：ベルを通過する上位パケットの番号
′Ｐ／ ｄｏｕｂｌｅ　ａｓ、ｓｎ；／＊角度の正弦及び余弦ネ
／ｄｏｕｂｌｅ　ｄ；　　　＃ベルを通過するプロジェ
クシｅンの距１１ｉ＊／ ｄｏｕｂｌｅ　ｄｅｌｔａｉ　／キバケットからベルの
中心のプロジェクシｅンまでの距離：／ ｄｏｕｂｌｅ　ｄｍａｘｉ／宰ピクセルを通るプロジェ
クシーンのｗａｘ　ｄ　＊／ ｄｏｕｂｌｅ　ｃｕｔｏｆｆｉ／＊ｃｕｔｏｆｆ　ｄ以
上はゼロである＊／ ｄｏｕｂｌｅ　５ｌｏｐｅ；　／＊ｄが直線的に減少す
る領域の勾配＊／ ｄｏｕｂｌｅ　ｂｒｅａｋｐｎｔ；　＃ｄが減少を開始
する点キー ｄｏｕｂｌｅ　１ｎｔｅｒｃｅｐｔ；　／掌ｄの直線領
域の切片キ／ ２１ ２２ ２３ ２４ ２５ ２６ ２７ ２８ ２９ ３０ ３１ ３２ ｄｏｕｂｌｅ　ｓａ　　；　　／＊プロジェクシ日フン
軸カウンタ掌／ ｄｏｕｂｌｅ　１ｉｎｅｓｔａｒｔ；　／＊プロジェク
ション軸のカウンタ＊／ ｄｏｕｂｌｅ　ｄｅｌｔａｄ；　／＊ペルがプロジェク
ション軸上にプロジェクトする距離　宰／ ｄｏｕｂｌｅ　ｆｚ：　　／＊ピクセルの中心がここへ
プロジェクシθンをマツプするキ／ ｄｏｕｂｌｅ　ｔｍａｘ、　ｔｗｉｎ；／雰ｓｏｍｅ　
ｔｅｍｐｓ＊／ｉｎｔ　ｉｃｓ、　ｉｓｎ、　ｉｄ、　
１ｄｅｌｔａ、　ｉｄｍａｘ、　１ｄｅｌｔａ２．　ｉ
ｓａ；ｉｎｔ　１ｌｉｎｅｓｔａｒｔ、１ｄｅｌｔａｄ
、１ｆｚｉｎｔ　ｂｓｃａｌｅ；／＊パケット・ファイ
ンダに対する固定小数点スケール掌／ ｉｎｔ　ｄｓｃａｌｅ；／掌距離コンピュータに対する
固定小数点スケール掌／ ｉｎｔ　ｔａｄｄｒ；　　／＊テーブル・アドレスネ／
ｄｏｕｂｌｅ　ｐｅｌ；　　／＊テーブルの構築に使用
される＊／ ５ｔａｔｉｃ　ｉｎｔ　ｔａｂｌｅ　［６５５３５］；
　＊乗算及び索引を行なうテーブル寧／ ３３ ３４ ３５ ３６ ３７ ３８ ３９ ４０ ４１ ４２ ４３ ４４ ４５ ４６ ４７ ４８ ４９ ５０ ｖｄ　＝　ＳＭ（：ｐｉｃｔｕｒｅ）；ｈｔ　＝　ＬＨ
（＊ｐｉｃｔｕｒｅ）；ｎｐｏｉｎｔｓ　＝　　（ｉｎ
ｔ）（ｓｑｒｔ（（ｄｏｕｂｌｅ）（ｖｄ＊ｖｄｈｔ寥
ｈｔ）））； ｎｐｏｉｎｔｓ　　＋＋： ｆｏｒ　（ｉ＝ｏ　；　ｉ＜ｎｐｏ　１ｎｔｓ　；　１
−−）ｐｄａｔａ　［ｉ　］＝Ｏ、Ｏ：ｃｓ　＝　ｃｏ
ｓ（ｔｈｅｔａネＤＴＯＲ）　；ｓｎ　＝　５ｉｎ（ｔ
ｈｅｔａネＤＴＯＲ）　；ｄｅｌｔａｄ　＝　ｆａｂｓ
（ａｓ）＋　ｆａｂｓ（ｓｎ）；ｔｍａｘ　＝　ＭＡＸ
（ｆａｂｓ（Ｃｓ）、ｆａｂｓ（ｓｎ））；ｔｗｉｎ　
＝　ＨＩＭ（ｆａｂｓ（ａｓ）、ｆａｂｓ（ｓｎ））；
ｄｍａｘ　　＝　　１．０／１ｍａｘｉｃｕｔｏｆｆ　
　＝　　ｄｅｌｔａｄＬ５；ｂｒｅａｋｐｎｔ　＝　　
（ｔｍａｘ　−ｔｗｉｎ）Ｌ５；５ｌｏｐｅ　　＝　０
．０； １ｎｔｅｒｃｅｐｔ　　＝　０．０； １ｆ（ｂｒｅａｋｐｎｔ＜ｃｕｔｏｆｆ）ｓｌｏｐｅ　
＝ｄｍａｘ／（ｂｒｅａｋｐｎｔ　　−ｃｕｔｏｆｆ）
；１ｎｔｅｒｃｅｐｔ　　＝　　、５ｌｏｐｅ掌ｃｕｔ
ｏｆｆ；ｂｓｃａｌｅ　　＝　　１＜＜ｂｂｉｔｓ；５
１ ５２ ５３ ５４ ５５ ５６ ５７ ５８ ５９ ６０ ６１ ６２ ６３ ｄｓｃａｌｅ　　＝　　１＜＜ｄｂｉｔｓ；ｉｃｓ　　
＝　ｂｓｃａｌｅ宰ｃｓ　　＋、５：ｉｓｎ　　＝　　
ｂｓｃａｌｅ宰ｓｎ　　＋、５；１ｄｅｌｔａｄ　　＝
　　ｂｓｃａｌｅ：ｄｅｌｔａｄ　　＋、５；１ｄｅｌ
ｔａｄ２　　＝　　ｂｓｃａｌｅ：ｃｕｔｏｆｆ　　＋
、５；／ネテーブルを構築する一低位８ビットはベル値
である掌／ ｌ＊高位８ビットは距離のパラメータである：／ｉ＝０
； ｆｏｒ（ｄｅｌｔａ　＝　０．０：ｄｅｌｔａ＜ｄｓｃ
ａｌｅｉｄｅｌｔａ　＋＝ｌ、Ｑ）ｆｏｒ（ｐｅｌ＝ｏ
、ｏｉｐｅｌ＜２５６．０：ｐｅｌ＋＝１．０）　（ｉ
ｆ　（ｄｅｌｔａ／ｄｓｃａｌｅ＜＝ｂｒｅａｋｐｎｔ
）ｄ　＝　ｄｍａｘ；ｅｌｓｅ　ｄ　＝　５ｌｏｐｅ＊
ｄｅｌｔａ／ｄｓｃａｌｅ＋１ｎｔｅｒｃｅｐｔ： ｔａｂｌｅ［ｉ＋＋］”（ｉｎｔ）　（ｄ＊ｐｅｌ＊２
５５．ｏ／３６１．０＋６４ ６５ ６６ ．５； ） ｐｉｘｅｌ　　＝　ＰＡ８（宰ｐｉｃｔｕｒｅ、０．０
）？ｉｆ’　（ｔｈｅｔａ）９０．０）ｏｆｆｓｅｔ＝
（ｉｎｔ）ｃｅｉｌ　（（（ｖｄ−０，５）＊ｃｓ−０
，５＊５ｎ））； ６７ １６８ ６９ ７０ ７１ ７２ ｅｌｓｅ　　ｏｆｆｓｅｔ　　＝　Ｏ；ｆｏｒ　（ｙ：
ｏ、　１ｌｉｎｅｓｔａｒｔ＝ｉｄｅｌｔａｄ２；ｙ＜
ｈｔ；ｙ＋＋。

１１ｉｎｅｓｔａｒｔ＋＝ｉｓｎ）　（ｆｏｒ（ｉｓａ
　＝　　１ｌｉｎｅｓｔａｒｔ、ｘ＋Ｏ；ｘ＜ｖｄ；ｘ
＋”＋ｉｓａ◆＝ｉｃｓ）（ ｉｆｚ　＝　　ｉｓａ　−１ｄｅｌｔａｄ２；ｚｕ　　
＝　　ｉｓａ＞＞ｂｂｉｔｓ；ｚｌ　＝　（ｉｓａ　−
１ｄｅｌｔａｄ＋ｂｓｃａｌｅ−１）＞＞ｂｂ　ｉ　ｔ
ｓ　； ７３ ７４ ７５ ｆｏｒ（ｉ＝ｚｌ；ｉ＜＋ｚｕ；ｉ”）（ｉｄｅｌｔａ
＝ＡＢｓ　（（ｉ＜＜ｂｂｉｔｓ）−ｉｆｚ）：／雰新
しい固定小数点表示に変換す るキ／ ７６ ７７ ７８ ７９ ８０ ８１ ８２ ） ｉｄｅｌｔａ　＝　１ｄｅｌｔａ＞＞（ｂｂｉｔｓ−ｄ
ｂｉｔｓ）Ｓ／雰索引テーブル・アドレスを生成する掌
／１ａｄｄｒ　＝　（＊ｐｉｘｅｌ）ｌ（ｉｄｅｌｔａ
＜＜８）；ｐｄａｔａ［１−ｏｆｆｓｅｔ］　＋＝　ｔ
ａｂｌｅ［ｔａｄｄｒ］：） １）ｌＸｅｌ”； １８３　　） １８４　） 第■表において、ステップ１００−１０２は角ｅをラジ
アンに変換し、定数ｄｂｉｔｓを、距離ファインダに使
用される、光線セグメントの長さを表す端数ビットの数
に等しく、また定数ｂｂｉｔｓをパケットを表すのに使
用される端数ビットの数に等しく定義する。手順の入口
点はステップ１０３である。プログラムへの入力はイメ
ージ及び角ｅである。出力（ｐｄａｔａ）は現行の光線
のセグメントの長さと現行のピクセルの輝度からなる積
である。

変数の定義はステップ１０８−１１２で与えられ、ステ
ートメント１１１及び１１２はそれぞれ現行のピクセル
に対し下位及び上位パケットを定義する。残りの変数の
定義はステートメント１１３−１２５で与えられる。こ
れらの定義を第３図を参照して説明する。ステートメン
ト１１４はｄを、現行のピクセルを通過する現行の光線
のセグメントの長さ（たとえば、ＺＵ）として定義する
。

ステートメント１１５は現行の光線のプロジェクシａン
軸交点と、現行のピクセルの中心の切片の間の距離に対
応する変数ｒｄｅｌｔａＪを定義する。第３図において
、これは切片４６と５１の間に示されている。ステート
メント１１７−１２Ｇは第５図を参照して上述した変数
を定義する。ステートメント１２１の変数Ｓａは、プロ
ジェクション軸上の現行のピクセルの左下コーナーのプ
ロジェクシｅン軸切片に対応する固定小数点カウンタで
ある。変数１ｉｎｅｓｔａｒｔは現行のラスク行の最初
のピクセルの左下コーナーのプロジェクシ寥ン軸上の切
片である。第３図において、ピクセル４３を、その行の
最初のピクセルとして取ると、Ｓａ及び１ｉｎｅｓｔａ
ｒｔの値は、ピクセル４３が処理される場合と同様に処
理されている。処理がピクセル４４に移ると、値Ｓａが
更新されて、ピクセル４４の左下コーナーを軸３８上に
プロジェクトする。変数ｄｅｌｉａｄは第３図及び４４
で示すように、ｅの正弦及び余弦の絶対値の和に対応し
ている。変数ｄｅｌｔａｄ２の大きさはｄｅｌｔａｄの
値の半分と等しい。これはピクセルの左下または右上の
コーナーの切片と、ピクセルの中心のプロジェクション
の間のプロジェクシ日ン軸上の距離を表す。ピクセルの
中心は変数ｆｚによってプロジェクシｅン軸にマツプさ
れる（ステートメン）１２４）。

ステートメント１２７−１３０は以前のステートメント
で定義された変数の値をスケールするのに使用される変
数を定義し、これらの固定小数点値を得る。

第８図の索引テーブル１３５は本質的に、ステートメン
ト１３０−１３２で定義される。現行のピクセルの倍精
度値（ｄｏｕｂｌｅ　　１）ｅｌ）を使用して、ＬＵＴ
を構築すること、及びテーブルが各々がそれぞれの光線
セグメント長／ピクセル輝度の積に対応している８５．
５３５のアドレス可能ワードを記憶していることに留意
されたい。

ステートメント１３３−１３７はｘｙ空間におけるイメ
ージのピクセルの寸法の、プロジェクシ日ン軸上でのパ
ケットの単位への単位変換を行なう。

この場合、パケットの数はステートメント１３５におい
て、ピクセル化されたイメージ・マトリックスの対向す
るコーナーの間に引かれた弦の長さと等しく設定される
。ステートメント１３７において、各パケットに対する
プロジェクション・コレクタへの出力（ｂｕｃｋｅｔ　
（ｆ））は、ゼロに初期設定される。

次に、第５図にしたがって可能な光線のセグメント長の
すべてをパラメータ化するのに必要な値が、ステートメ
ント１３８−１４９で計算される。

ステップ１５０及び１５１において、パケット・ファイ
ンダ（ｂｓｃａｌｅ）及び光線セグメント長（ｄ　ｓ　
ｃ　ａ　ｌ　ｅ）の固定小数点表示が、固定小数点表示
のためにスケールされる。ステートメント１５２及び１
５３は第５図に関連した区切り点及びカットオフの計算
のために、余弦値及び正弦値をスケールする。同様に、
ステートメント１５４及び１５５は固定小数点演算のた
めにパラメータｄｅｌｔａｄ及びｄｅｌｔａｄ２をスケ
ールする。

次に、ステートメント１５Ｂ−１６４において、８ビツ
ト・ピクセル輝度値の可能な積のナベて、及びステップ
１５０−１５５でスケールさ・れたものとして第５図に
含まれている光線セグメント長の整数値のすべてに対し
て、索引テーブル１３５が構築される。

パケット・ジェネレータがステップ１８５−１８４で与
えられる。第■表のこの部分においては、ピクセル・イ
メージ・ジェネレータは変換されるイメージの内蔵式バ
イト・マツプからなっており、このマツプにピクセルが
ラスタ・シーケンスに対応した順次形式で記憶され、シ
ーケンス内の各アドレス可能位置がピクセル輝度の８ビ
ツト表示を含んでいるものと想定されている。パケット
・ジェネレータはステートメント１６５で開始ピクセル
のアドレスを取り入れ、ステートメント１８６及び１６
７で角度のオフセットを定義し、ステートメント１６８
でパケットの識別を開始する。

バケツ）ＩＩＩ別過程において、Ｘｙ主空間原点、プロ
ジェクシｅン軸の原点、及びラスク内の最初のピクセル
の中心が整合される。明確に理解するため、第３図に示
すよろに、Ｘとｙの両方がＯである場合に、ピクセル４
３の左下コーナーとプロジェクション軸の交点は距離ｄ
ｅｌｔａｄ／２で与えられる。このパラメータの現行値
は、現行のピクセルの行を識別する。行の終わりに達し
た場合、次の行の始め（すなわち、プロジェクション軸
への、次の行の最初のピクセルの左下コーナーのプロジ
ェクシｅン）は、１ｉｎｅｓｔａｒｔの現行値を、ｅの
正弦の固定小数点値ｉｓｎだけ増加させることによって
与えられる。マトリックスの現行行内のピクセルがステ
ートメント１６８でカウントされるが、この場合、パラ
メータｉｓａはプロジェクション軸への、現行のピクセ
ルの左下コーナーのプロジェクションである。この値は
ピクセルが更新された場合のｅの余弦の固定小数点値ｉ
ｃｓだけ増加させられる。ステートメント１７０におい
て、現行のピクセルの中心のプロジェクション軸位置が
、ｄｅｌｔａｄ２をｉｓａの現行値から差し引くことに
よって計算され、その後、現行のピクセルに対する上下
のパケットがステートメント１７１及び１７２で識別さ
れる。ステートメント１７３及び１７４は、ステートメ
ント１７１及び１７２で識別された上下のパケットの間
の範囲に含まれる各パケットを識別するループを構成す
る。この範囲内の各パケットについて、このパケットと
ピクセル１ｄｅｌｔａの中心との間のプロジェクシｅン
軸における距離がステートメント１７４で計算され、ス
テートメント１７６で固定小数点表示に変換され、ステ
ートメント１７８でピクセルの輝度と連結され、索引テ
ーブルに対するアドレスを生成する。

この時点で、索引テーブルがどのように構成されたかを
再考するのが、有益である。ここでステートメント番号
１５９−１８５に戻ると、テーブルは各テーブル・アド
レスｔａｄｄｒに、光線セグメントの長さとピクセル・
イメージの輝度の積を記憶するように構成されている。

第５図を参照した上述したところで確認したように、パ
ラメータ１ｄｅｌｔａは光線セグメントの値を暗示する
。

したがって、アドレスはイメージの輝度の現行の値から
形成されｓ　１ｄｅｌｔａは１ｄｅｌｔａのこの値に対
応する光線セグメントと、現行のイメージの輝度の積を
もたらす。ステートメント１７９において、現行のパケ
ットの識別記号（ｐｄａｔａ［ｉ−コ）及び光線セグメ
ント／輝度の積（ｔａｂｌｅ　［ｔａｄｄｒ］）が、プ
ロジェクシ、ン−コレクタに出力される。ステートメン
ト１８０は次のパケットのためにステートメント１７３
に戻る。現行のピクセルに対する最後のパケットが処理
されると（ｉ＝ｚｕ）、ピクセルの（ｘｓＶ）アドレス
が増加する。ステートメント１８２はステートメント１
６９にループ・パックして、プロジェクション軸への次
のピクセルの左下コーナーのプロジェクシｅン、ｉｓａ
の値を更新する。このループはＸの値がラスタ・マトリ
ックスの幅（ｗｄ）と等しくなったときに終了する。ス
テートメント１８３はステートメント１６８にループ・
バックして、次のラインに更新する。このループは現行
のピクセルのｙの値がピクセル・マトリックスの高さ（
ｈｔ）の値と等しくなるまで作動する。

ステートメント１８４は手順の終わりを意味する。

第９図は本発明のハードウェアの実施例を示す。

第９図は第７図の変換プロセッサ１１０が、マルチＣＰ
Ｕプロセッサであって、各プロセッサ段が他のすべての
ステージと並列に作動するものと想定している。したが
って、第９図は行及び列のクロックとピクセルの輝度を
含んでいるピクセル・データを、イメージ・ジェネレー
タから受は取るハードウェア・プロセッサの形態で、第
８図のステージ・アーキテクチャを示すものである。第
９図のステージ・プロセッサはホスト・プロセッサ１１
６から、５ＴＡＲＴ信号、角ｅで計算されるプロジェク
シＩンに対する索引テーブルの値、ならびに値１ｄｅｌ
ｔａｄ２及び（ｉｄｌｅｔａｄ十ｂ８Ｃａｌｅ−１）を
受は取る。さらに、ステージ・プロセッサはｎ　Ｃｃで
示される列クロックの倍数を受は取る。

第９図のステージ・プロセッサは入力■を有しており、
ホスト・プロセッサ１１６からパラメータ１ｄｅｌｔａ
ｄ２の値を受は取る３２ビツト・レジスタ２００を含ん
でいる。レジスタ２００の出力ポートＯは、プリロード
された３２ビツトの、ｎずつカウントするカウンタであ
ることが好ましいカウンタ２０２への３２ビット信号ラ
イン２０１に設けられている。カウンタ２０２は信号ラ
イン２０３の行うロックＣｒによってクロックされ、信
号ライン２０４上の５ＴＡＲＴ信号に応答して、レジス
タ２００の内容をロードする。カウンタ２０２の現在の
３２ビツトのカウントは、信号ライン２０７に出力され
るが、この信号ラインは行うロックＣ７によってプリロ
ードされる、第２の３２ビツトの、ｎずつカウント“す
るカウンタ２１０の入力ｌに接続されている。カウンタ
２１０は信号ライン２１１に与えられる列クロックＣｃ
によってクロックされる。カウンタ２１０の３２ビツト
出力は・信号ライン２１３にもたらされる。３２ビツト
・レジスタ２１５は信号ライン２１６で値（ｉｄｅｌｔ
ａｄ＋ｂａｃａｌｅ−１）を受は取って記憶し、この値
を信号ライン２１７で３２ビツト加算器２１９にもたら
す。加算器２１９はそのＡ入力でレジスタ２１５の内容
を、またそのＢ入力でカウンタ２１０の出力を受は取る
。加算器２１９はその入力で受は取った値の和（Ａ十Ｂ
）をもたらす。出力は和の最上位１６ビツトのみからな
り、信号ライン２２０にもたらされる。

３２ビツト減算器２２２はそのＡ入力でカウンタ２１０
の出力を、またそのＢ入力でレジスタ２００の内容を受
は取る。減算器２２２はＢの大きさをＡの大きさから差
し引き、その差を３２ビツトの信号として、信号ライン
２２３にもたらす。

増分回路２２５は１６ピツトの和を信号ライン２２０で
受は取り、またカウンタ２１０で生成された最上位１６
ビツトを信号ライン２２６で受は取る。増分回路２２５
は信号ライン２２８のクロック信号ｎｃｃに応答して信
号ライン２２０の値を、これが信号ライン２２６の値に
達するまで、１ずつ増加させる。増分回路２２５の出力
は１６ビツトの信号として、信号ライン２２７にもたら
される。これらの１６ビツトは３２ビツト減算器２３０
のＡ出力において、値ゼロに設定された信号ライン２２
９の１６ビツトと連結される。減算器２３０のＢ入力は
信号ライン２２３で差信号を受は取る。減算器２３０は
そのＢ入力に与えられる大きさを、そのＡ入力に与えら
れる大きさから差し引き、Ａ−Ｈの絶対値を出力する。

この絶対値は１８ビツトの信号として信号ライン２３２
にもたらされる。信号ライン２３２の１８ビツト値号は
、信号ライン２３３のピクセル輝度信号Ｉと連結され、
索引テーブル（ＬＵＴ）２３Ｅ３のアドレス入力を形成
する。索引テーブル２３６は、内容が第■表で構築され
た索引テーブルに関連して上述したものである８４ＫＸ
８のメモリからなる。上述のプロジスクシ８ン・コレク
タに対応するプロジェクシｅン・コレクタ２４０は、信
号ライン２２７からの更新アドレス、信号ライン２３９
上の索引テーブル２３６の出力からの更新値、及び加速
列クロックｎｃｃを受は取る。

第９図の回路の作動はレジスタ２００及び２１５のそれ
ぞれに、値１ｄｅｌｔａｄ２及び（ｌｄｅｌｔａｄ＋ｂ
ｓｃａｌｅ−１）をロードすることから始まる。１ｄｅ
ｌｔａｄ２の初期値は、ラスタの最初の行の最初のピク
セルの左下コーナーの、プロジェクション軸上のプロジ
ェクションである。第■表において、これは１ｌｉｎｅ
ｓｔａｒｔの初期値である。第４図において、このプロ
ジェクタ１ンは１１１ｎｅｓｔａｔ、で示されている。

行うロックＣｒの各サイクルに１回、カウンタ２０２は
その現行値を、ｅの正弦の整数値ｉｓｎだけ増加させる
。第４図に関連して上述したように、これは完了した行
の次の行の最初のピクセルの左下コーナーのプロジェク
シｅンを与える。

カウンタ２１０は各ラスク行の初めにおけるカウンタ２
０２の出力を受は取る。第３図及び第４図に関連して上
述したように、この値は最初の行のピクセルの左下コー
ナーの、プロジェクシｅン軸上のプロジェクシｌンに対
応している。この値は列クロックＣ０の各サイクルに１
回、ｅの余弦の固定小数点値１ｃｓだけ増加させられ、
行の次のピクセルのプロジェクシーン軸の位置を得る。

これは第４図に示されている。

加算器２１９は現行のピクセルの左下コーナーのプロジ
ェクション軸位置に、オフセット（ｉｄｅｌｔａｄ＋ｂ
ｓｃａｌｅ−１）を加える。これはｃｅｉｌ関数を計算
し、上述の固定小数点ｆｌｏｏｒ関数によって下部パケ
ットｚｌを求める。

ｚｕを求めるｆｌｏｏｒ関数は本質的に、現行のピクセ
ルの左下及び右上のコーナーのプロジェクシｌンに対す
る３２ビツト値を丸めることによって実行される。した
がって、信号ライン２１３の最上位１６ビツトと加算器
２１９の出力のみが、増分回路２２５にもたらされる。

左下コーナーを表す３２ビツトの数のうち最上位１６ビ
ツトは、ＺＵの表示として取られ、右上コーナーの表示
のうち再上位１６ビツトはｚｌの表示として取られる。

増分回路２２５はその作動時に、これら２つの値に応答
する。

作動時に、増分回路２２５はｎｃｃの各サイクルに１回
、ループ・パラメータｉに対する新しい値を計算する。

カウントはｚｌに対する表示から始まり、ＺＵの値に達
したときに停止する。それゆえ、増分回路２２５はｎ　
Ｃｃの各サイクルに１回、現行のパケットを８ビツトの
更新アドレスとして出力する。

減算器２２２は定数値ｉｄｅ　ｌ　ｔａ２を、現行のピ
クセルの左下コーナーのプロジェクシ騨ン軸位置から差
し引き、第３図においてｆｚ１第■表においてｉｆｚと
示されているピクセルの中心のプロジェクシＢン軸位置
を生じる。

減算器２３０はピクセルの中心及び処理されるパケット
ｉに対する上述の演算によって、第３図に示されている
距離ｒｄｅｌｔａＪ　　（第■表の１ｄｅｌｔａ）をも
たらす。ｄｅｌｔａの値は減算器２３０によって生じる
結果の最上位８ビツトから得られる。これらの８ビツト
は索引テーブル２３６のアドレス入力において、ピクセ
ルの輝度を表す８ビツトと連結され、光線セグメント長
／ピクセル輝度の積の形式の更新値を得、これは信号ラ
イン２３９に更新値としてもたらされる。

プロジェクシ日ン・コレクタ２４０は乗算された列クロ
ックｎｃｃに応じて作動する。プロジェクション・コレ
クタの作動は第１０図に示すよろに、ピクセル当り最大
４つの更新と同期させられる。

すなわち、任意の所与のピクセルと所定の方向で交差す
る光線の数は、１から４まで変化することを意味する。

したがって、当技術分野の技術者には、乗算クロックｎ
Ｃｃは発生しうる更新の最大数をクロックできる周波数
を有していなければならないことが明らかとなろう。こ
の場合、ピクセル当り最大４つの更新によって、加速さ
れたクロックは４Ｃ，となる。

１０発明の効果 本発明によれば、ディジタル・イメージがラスク走査順
に処理されるので、ラスク走査されたディジタル・イメ
ージをラドン空間のプロジェクシ冒ンに変換する方法を
、コンピュータのパイプラインの実施形態に合わせて修
正することが可能となる。

【図面の簡単な説明】

第１図は、楕円関数のラドン・プロジェクションの説明
図である。 第２図は、ラスク走査ディジタル・イメージを変換した
場合の、ラドン線積分の計算方法の幾何学的解釈の説明
図である。 第３図は、ピクセルと交差する光線を見いだすために、
ディジタル・イメージのピクセルのラドン・プロジェク
ション軸へのプロジェクションの説明図である。 第４図は、ピクセルと交差する光線のラドン・プロジェ
クタ９ン軸位置を計算するための、ピクセル始点のプロ
ジェクションの説明図である。 第５図は、ピクセルと交差する光線セグメントの長さの
パラメータ化の説明図である。 第６図は、ディジタル化イメージの３つのピクセルの表
示を、要素の処理のブロック図と組み合わせ、本発明の
詳細な説明する図である。 第７図は、本発明の態様に有用なパイプライン・アーキ
テクチャの説明図である。 第８図は、パイプライン段の構造を説明するブロック図
である。 第９図は、第８図のパイプライン段を詳細に示すブロッ
ク図である。 第１０図は、コレクタの動作を示すタイミング図である
。

Claims (4)

【特許請求の範囲】
1. （１）ピクセルのアレイを含むラスタ走査信号によって
   表されるディジタル・イメージのラドン変換を行なう、
   複数のプロジェクション記憶位置を含んでいるプロセッ
   サにおける、プロジェクション角Θで前記イメージのラ
   ドン・プロジェクションを構成する方法において、 前記ピクセルのアレイを行順に前記プロセッサに与え、 前記ピクセルのアレイ内の各ピクセルに対して、前記ラ
   ドン・プロジェクションを前記ピクセルのアレイに対応
   させる軸上において、前記ピクセルを含んでいる前記ピ
   クセルのアレイの行に対応する基準位置ｚを決定し、 ｚｕ＝ｆｌｏｏｒ（（ｘ−．５）＊ｃｏｓΘ＋（ｙ＋．
   ５）＊ｓｉｎΘ＋ｚ）にしたがって、ｚをΘと組み合わ
   せることによって、前記プロセッサ内のプロジェクショ
   ン記憶位置ｚｕを決定し（ただし、ｆｌｏｏｒ（ｗ）は
   ｗ以下の最大の整数であり、ｘ、ｙは前記ピクセルのア
   レイ内の前記ピクセルの中心の位置に対応しており、前
   記記憶位置は前記ピクセルと交差する前記プロジェクシ
   ョンの光線に対応している）、 前記光線の前記ピクセルに含まれている部分の長さを決
   定し、 前記長さを、前記ピクセルの輝度と組み合わせて、光線
   セグメント値を獲得し、 前記光線セグメント値を、前記プロジェクション記憶位
   置に記憶されている部分光線値と組み合わせ、かつその
   結果を前記記憶位置に、更新された部分光線値として記
   憶し、 前記プロジェクション記憶位置において、 前記ピクセルのアレイ内のピクセルについての更新され
   た部分光線値を積算することによって、前記プロジェク
   ションを組み立てる、 ステップからなる、方法。
2. （２）ピクセルのアレイを含むラスタ走査信号によって
   表されるディジタル・イメージのラドン変換を行なう、
   複数のプロジェクション記憶位置を含んでいるプロセッ
   サにおける、プロジェクション角Θで前記イメージのラ
   ドン・プロジェクションを構成する方法において、 前記ピクセルのアレイを行順に前記プロセッサに与え、 前記ピクセルのアレイ内の各ピクセルに対して、前記ラ
   ドン・プロジェクションを前記ピクセルのアレイに対応
   させる軸上において、前記ピクセルを含んでいる前記ピ
   クセルのアレイの行に対応する基準位置ｚを決定し、 ｚｌ＝ｃｅｉｌ（（ｘ＋．５）＊ｃｏｓΘ＋（ｙ−．５
   ）＊ｓｉｎΘ＋ｚ）にしたがって、ｚをΘと組み合わせ
   ることによって、前記プロセッサ内のプロジェクション
   記憶位置ｚｌを決定し（ただし、ｃｅｉｌ（ｗ）はｗ以
   上の最小の整数であり、ｘ、ｙは前記ピクセルのアレイ
   内の前記ピクセルの中心の位置に対応しており、前記記
   憶位置は前記ピクセルと交差する前記プロジェクション
   の光線に対応している）、 前記光線の前記ピクセルに含まれている部分の長さを決
   定し、 前記長さを、前記ピクセルの輝度と組み合わせて、光線
   セグメント値を獲得し、 前記光線セグメント値を、前記プロジェクション記憶位
   置に記憶されている部分光線値と組み合わせ、かつその
   結果を前記記憶位置に、更新された部分光線値として記
   憶し、 前記プロジェクション記憶位置において、 前記ピクセルのアレイ内のピクセルについての更新され
   た部分光線値を積算することによって、前記プロジェク
   ションを組み立てる、 ステップからなる、方法。
3. （３）２次元ピクセル・アレイ（ラスタ・イメージ）を
   中間情報形態としてラドン空間（プロジェクションの集
   合）に変換し、前記中間形態がイメージ・オブジェクト
   位置の測定値を確認するための処理を施せるか、あるい
   は雑音を除去するため濾波を施せるものである、パイプ
   ライン・プロセッサまたは並列プロセッサのいずれかで
   実行される方法において、 行順にアレイを走査し、 ピクセル値及びアレイ位置の２次元矩形関数の和として
   生成される、有限範囲の関数に対して、走査されたアレ
   イのピクセルから連続線積分を計算する、 ステップからなる、方法。
4. （４）２次元ピクセル・アレイ（ラスタ・イメージ）を
   中間情報形態としてラドン空間（プロジェクションの集
   合）に変換し、前記中間形態がイメージ・オブジェクト
   位置の測定値を確認するための処理を施せるか、あるい
   は雑音を除去するため濾波を施せるものである、パイプ
   ライン・プロセッサまたは並列プロセッサのいずれかで
   実行される方法において、 行順にアレイを走査し、 各ピクセルについて、該ピクセルがマップされるラドン
   空間における位置及びその大きさを確認し、これによっ
   て直線などのアレイ・ピクセル・オブジェクトを、点な
   どのプロジェクション・オブジェクトにマップし、前記
   ラドン空間のオブジェクトが対応するアレイ・オブジェ
   クトよりも効率よく処理される、 ステップからなる、方法。