JPH0896160A - 演算装置および演算方法 - Google Patents

Abstract

(57)【要約】 【目的】 演算順序の交換が可能なｐ個の演算（第１の
演算〜第ｐの演算）を行う周波数領域ボリューム・レン
ダリング演算装置において、光線の数に比例しないで演
算可能な周波数領域ボリューム・レンダリングを行う演
算方法とその装置を提供する。 【構成】 ｐ＝２の場合について述べる。演算処理時間
が少ない演算順序を検出する演算順序検出回路１と、第
１の演算回路（逆フーリエ変換を処理する回路）２と第
２の演算回路（ＲＧＢデータ算出回路）３とを有し、上
記演算順序検出回路１により検出された順番どおりに２
個の演算を上記第１の演算回路〜第２の演算回路にて演
算する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、演算順序が交換可能な
複数の演算を処理する演算装置、及び演算方法に関す
る。本発明は特に、ボリューム・レンダリング（Ｖｏｌ
ｕｍｅ Ｒｅｎｄｅｒｉｎｇ）を高速に計算する装置、
及び方法に関する。

【０００２】

【従来の技術】具体例を用いて説明を行う。文献、Ｔａ
ｋａｓｈｉ Ｔｏｔｓｕｋａ，”Ｆｒｅｑｕｅｎｃｙ
Ｄｏｍａｉｎ Ｖｏｌｕｍｅ Ｒｅｎｄｅｒｉｎｇ”
（周波数領域ボリューム・レンダリング），ＣＯＭＰＵ
ＴＥＲ ＧＲＡＰＨＩＣＳ Ｐｒｏｃｅｅｄｉｎｇｓ，
Ａｎｎｕａｌ Ｃｏｎｆｅｒｅｎｃｅ Ｓｃｅｒｉｅ
ｓ，１９９３，ＰＰ．２７１−２７８に開示されたもの
への演算装置の適用を考える。ボリューム・レンダリン
グとは、３次元のデータ（ボリュームデータ）から視線
方向に垂直な平面（スクリーン）上の投影画像を求める
手法である。上記論文に述べられているＦｒｅｑｕｅｎ
ｃｙ Ｄｏｍａｉｎ ＶｏｌｕｍｅＲｅｎｄｅｒｉｎｇ
（以下では、ＦＤＶＲと呼ぶことにする。）とはボリュ
ーム・レンダリングの高速化アルゴリズムである。

【０００３】ＦＤＶＲについて簡単に述べておく。ＦＤ
ＶＲにおいては、まず、与えられたボリュームデータを
３次元フーリエ変換を行い、周波数空間上のデータを求
めておく。この計算は、１つのボリュームデータに対し
て一度だけ行えば良い。そして、実際にある角度からの
視線に対応した投影画像を求めるには、以下の操作を行
うことになる。この操作は次の２つの手順より成る。第１の手順 ：周波数空間上のデータの中心を通り、視線
方向と垂直な平面を考え、周波数空間上のデータを補間
することでこの平面上のデータを算出する。第２の手順 ：平面Ａ上のデータに２次元の逆フーリエ変
換を行ない、実空間上のデータを求める。 以上の２つの手順により算出された２次元のデータは、
先に述べた視線方向に垂直な平面上の投影画像に他なら
ない。この２つの手順の計算量は、ｍ×ｌｏｇ（ｍ）の
オーダーである。ここでｍはボリュームデータの一辺の
長さである。もし、この手法を使わずに、ボリュームデ
ータからスクリーン上の投影画像を直接求めると、ｍの
３乗のオーダーの計算時間がかかる。ｍ×ｌｏｇ（ｍ）
＜ｍの３乗であるので、ＦＤＶＲは高速なボリューム・
レンダリングを行う手法であると言える。

【０００４】従来のＦＤＶＲを計算する回路の一部を図
４に示す。図４において、ＦＤＶＲ計算回路は、逆フー
リエ変換回路２と、ＲＧＢデータ算出回路３とを有す
る。図５にＲＧＢデータ算出回路３の回路構成を示す。
ＲＧＢデータ算出回路３は、乗算回路３１〜３３におい
て入力されるデータｉｎにＲＧＢ係数Ｒｉｎ，Ｇｉｎ，
Ｂｉｎを乗じて、加算回路３４〜３６においてＲＧＢの
成分毎に加算している。

【０００５】図４に示したＦＤＶＲ計算回路において、
実際にどのように計算が行なわれていくかを具体的な例
を用いて説明する。光線が１つの時 逆フーリエ変換回路２でまず計算する。このときの時間
をｔ１とする。次に、ＲＧＢデータ算出回路３で計算す
る。このときの時間をｔ２とする。以上より、計算時間
は、（ｔ１＋ｔ２）時間かかる事になる。光線が５つの時 逆フーリエ変換回路２でまず、１つ目のデータを計算す
る。このときの計算時間はｔ１である。逆フーリエ変換
回路２で次に、２つ目のデータを計算する。このときの
計算時間はｔ１である。逆フーリエ変換回路２で次に、
３つ目のデータを計算する。このときの計算時間はｔ１
である。逆フーリエ変換回路２で次に、４つ目のデータ
を計算する。このときの計算時間はｔ１である。逆フー
リエ変換回路２で次に、５つ目のデータを計算する。こ
のときの計算時間はｔ１である。逆フーリエ変換回路２
で５つの計算がし終わったら、その５つのデータを次段
の回路であるＲＧＢデータ算出回路３にシリアルに送
る。ＲＧＢデータ算出回路３では５つのデータを順次乗
算し、累加算器で計算する。このときの時間は５×ｔ２
であるので、計算時間は、５×（ｔ１＋ｔ２）時間かか
る事になる。光線がｎ個の時 光線がｎ個の時、計算時間は、ｎ×（ｔ１＋ｔ２）時間
かかる事になる。

【０００６】

【発明が解決しようとする課題】従来の技術による演算
装置および演算方法では、例えば、ＦＤＶＲを計算する
場合、光線の数に比例した計算時間がかかるため、光線
の数が多い場合に計算時間がかかり過ぎていた。

【０００７】したがって、本発明は、時間計算が光線の
数に比例して増加することなく演算可能な周波数領域ボ
リューム・レンダリングを行う演算方法とその装置を提
供することにある。

【０００８】

【課題を解決するための手段】本発明は、演算順序の交
換が可能なｐ個の演算（第１の演算〜第ｐの演算）を行
う演算装置において、演算処理時間が少ない演算順序を
検出する演算順序検出回路と、上記第１の演算〜第ｐの
演算をそれぞれ処理する第１の演算回路〜第ｐの演算回
路を有し、上記演算順序検出回路により検出された順番
どおりに上記ｐ個の演算を上記第１の演算回路〜第ｐの
演算回路にて演算することを特徴とする演算装置であ
る。

【０００９】また、上記演算装置において、上記演算順
序検出回路は、上記第ｋ（ｋ＝１〜ｐ）の演算回路に入
力する第ｋの入力データの数と出力される第ｋの出力デ
ータの数の関係を用いて演算順序を検出する。

【００１０】また、上記演算装置において、上記ｐは２
であり、上記第１の演算回路は逆フーリエ変換を処理す
る回路であり、上記第２の演算回路は上記第２の演算回
路に入力されるデータにＲＧＢ係数を乗算してＲＧＢの
成分毎に加算するＲＧＢデータ算出回路である。

【００１１】さらに、演算順序の交換が可能なｐ個の演
算（第１の演算〜第ｐの演算）を行う演算方法におい
て、演算処理時間が少ない演算順序を検出する為の演算
順序検出処理を行い、上記演算順序検出処理により検出
された順番どおりに上記ｐ個の演算を行う。

【００１２】また、上記演算方法において、上記演算順
序検出処理は、上記第ｋ（ｋ＝１〜ｐ）の演算に入力す
る第ｋの入力データの数と出力される第ｋの出力データ
の数の関係を用いて演算順序を検出していく。

【００１３】また、上記演算方法において、上記ｐは２
であり、上記第１の演算は逆フーリエ変換を処理する演
算であり、上記第２の演算は上記第２の演算に入力され
るデータにＲＧＢ係数を乗算してＲＧＢの成分毎に加算
するＲＧＢデータ算出である。

【００１４】

【作用】上記の構成によれば、演算順序検出回路は、演
算処理時間が少ない演算順序を検出し、第１の演算回路
〜第ｐの演算回路は、上記演算順序検出回路により検出
された順番通りに上記ｐ個の演算を上記第１の演算回路
〜第ｐの演算回路にて演算する。

【００１５】

【実施例】本発明を説明するにあたり、従来例でも用い
たＦＤＶＲ計算回路をさらに具体的に説明することにす
る。その前に、逆フーリエ変換とＲＧＢデータ算出処理
の演算順序の交換が可能であることを示しておく。い
ま、逆フーリエ変換回路が逆フーリエ変換を行ない、Ｒ
ＧＢデータ算出回路がＲＧＢデータ算出処理を行なうと
き、ＲＧＢデータ算出回路の入力データをＸ１，Ｘ２，
・・・，Ｘｎ、出力データをＹ１，Ｙ２，Ｙ３、光源ｉ
（１，２，・・・，ｎ）のＲＧＢの各係数をＲｉ，Ｇ
ｉ，Ｂｉとすると、以下の関係式が成り立つ。

【００１６】 Ｙ１＝Ｒ１Ｘ１＋Ｒ２Ｘ２＋ ・・・ ＋ＲｎＸｎ ・・・（１）

【００１７】 Ｙ２＝Ｇ１Ｘ１＋Ｇ２Ｘ２＋ ・・・ ＋ＧｎＸｎ ・・・（２）

【００１８】 Ｙ３＝Ｂ１Ｘ１＋Ｂ２Ｘ２＋ ・・・ ＋ＢｎＸｎ ・・・（３）

【００１９】逆フーリエ変換（Ｆ（ｘ））は線形演算で
あり以下の関係式が成立することは一般に知られてい
る。

【００２０】 Ｆ（ｘ）＋Ｆ（ｙ）＝Ｆ（ｘ＋ｙ） ・・・（４）

【００２１】 ａＦ（ｘ）＝Ｆ（ａｘ） ・・・（５）

【００２２】ここで、ＲＧＢデータ算出処理・逆フーリ
エ変換の順に演算を施したときの出力結果をＺ１，Ｚ
２，Ｚ３とすると、下記式が成立する。

【００２３】 Ｚ１＝Ｆ（Ｒ１Ｘ１＋Ｒ２Ｘ２＋・・・＋ＲｎＸｎ） ・・・（６） Ｚ２＝Ｆ（Ｇ１Ｘ１＋Ｇ２Ｘ２＋・・・＋ＧｎＸｎ） ・・・（７） Ｚ３＝Ｆ（Ｂ１Ｘ１＋Ｂ２Ｘ２＋・・・＋ＢｎＸｎ） ・・・（８）

【００２４】また、逆フーリエ変換・ＲＧＢデータ算出
の順に演算を施したときの出力結果をＷ１，Ｗ２，Ｗ３
とすると、下記式が成立する。

【００２５】 Ｗ１＝Ｒ１Ｆ（Ｘ１）＋Ｒ２Ｆ（Ｘ２）＋・・・＋ＲｎＦ（Ｘｎ） ・・・（９） Ｗ２＝Ｇ１Ｆ（Ｘ１）＋Ｇ２Ｆ（Ｘ２）＋・・・＋ＧｎＦ（Ｘｎ） ・・・（１０） Ｗ３＝Ｂ１Ｆ（Ｘ１）＋Ｂ２Ｆ（Ｘ２）＋・・・＋ＢｎＦ（Ｘｎ） ・・・（１１）

【００２６】式４〜式１１から下記式が成立する。

【００２７】 Ｚ１ ＝ Ｗ１ ・・・（１２） Ｚ２ ＝ Ｗ２ ・・・（１３） Ｚ３ ＝ Ｗ３ ・・・（１４）

【００２８】以上から、逆フーリエ変換とＲＧＢデータ
算出処理は演算順序の交換が可能であることが分かる。

【００２９】演算順序が、逆フーリエ変換・ＲＧＢデー
タ算出の場合と、ＲＧＢデータ算出処理・逆フーリエ変
換の場合の演算装置について演算処理時間を考える。従
来の技術で示したように、入力するデータ数が１個の場
合の逆フーリエ変換回路の計算時間をｔ１、入力するデ
ータ数が２個の場合のＲＧＢデータ算出回路の計算時間
をｔ２とする。演算順序が、逆フーリエ変換・ＲＧＢデ
ータ算出の場合は、従来の技術で示したのと同じ構成の
演算装置になるので計算時間は、下記式で示される時間
だけかかる。

【００３０】 ｎ×（ｔ１＋ｔ２） ・・・（１４）

【００３１】演算順序が、ＲＧＢデータ算出処理・逆フ
ーリエ変換の場合は、ＲＧＢデータ算出回路は入力した
ｎ個のデータを順次乗算し、累積加算器で計算するので
計算時間は、（ｎ×ｔ２）時間かかる。ＲＧＢデータ算
出回路はＲＧＢの成分毎に３個のデータを出力する。従
って、逆フーリエ変換は、１つ目のデータ、２つ目のデ
ータ、３つ目のデータを計算するのにそれぞれｔ１時間
かかるので、計算時間は、（３×ｔ１）時間かかる。そ
の結果、両方を加算した下記式が示される時間だけかか
る。

【００３２】 ｎ×ｔ２＋３×ｔ１ ・・・（１５）

【００３３】式１４と式１５とを比較すると、ｎ＜３の
場合には、演算順序が、逆フーリエ変換・ＲＧＢデータ
算出の場合の方が演算処理時間が少ないことが分かる。

【００３４】次に、本発明をＦＤＶＲの計算に適用した
回路（ＦＤＶＲ計算回路）を図１に示す。ＦＤＶＲ計算
回路は、演算順序検出回路１、逆フーリエ変換回路２、
ＲＧＢデータ算出回路３、および、第１〜第３のマルチ
プレクサ（ＭＰＸ）４、４、６を有する。

【００３５】本発明の演算装置の一実施例の動作を説明
する。演算順序検出回路１は演算処理時間が少ない演算
順序を検出し、第１のＭＰＸ４、第２のＭＰＸ５、第３
のＭＰＸ６ににデータの流れを指示する。この場合のデ
ータの流れはＭＰＸ４〜６への入力が０の場合と１の場
合がある。いま、入力データ数（光源数）をｎとする。
ｎ＜３の場合には、演算順序検出回路１は３個のＭＰＸ
４〜６に入力が０の場合を指示する。このとき、入力デ
ータＦ１は、逆フーリエ変換・ＲＧＢデータ算出処理の
順に演算を施され、出力データＦ２が算出される。ｎ＞
３またはｎ＝３の場合には、演算順序検出回路１は３個
のＭＰＸ４〜６に入力が１の場合を指示する。このと
き、入力データＦ１は、ＲＧＢデータ算出処理・逆フー
リエ変換の順に演算を施され、出力データＦ２が算出さ
れる。

【００３６】図２のフローチャートは、図１の回路の動
作を示している。 ステップ１（Ｓ１）：入力データ数をｎとしたとき、ｎ
＞３によって場合分けする。 ステップ２（Ｓ２）：ｎ＜３の場合には、ｎ個の光源に
ついて１個ずつ逆フーリエ変換を施す。 ステップ３（Ｓ３）：ＲＧＢデータ算出処理を行なう。 ステップ４（Ｓ４）：ｎ＞３またはｎ＝３の場合には、
ＲＧＢデータ算出を行なう。 ステップ５（Ｓ５）：ｎ個の光源について１個ずつ逆フ
ーリエ変換を施す。

【００３７】

【発明の効果】以上説明したように本発明によれば、演
算順序が交換可能なｐ個の演算（第１の演算〜第ｐの演
算）を行なう演算装置において以下の効果をもたらす。 （１）ＦＤＶＲの演算の一部を処理する演算装置におい
て、入力データに２個の演算として、逆フーリエ変換と
ＲＧＢデータ算出処理が施されるとき、演算装置の光源
数ｎと３の大小関係を比較することにより、（ａ）ｎ＜
３の場合には、演算順序検出回路が逆フーリエ変換・Ｒ
ＧＢデータ算出処理の順に演算を行なうことで演算処理
時間が少なくなり、（ｂ）ｎ＞３またはｎ＝０の場合に
は、演算順序検出回路がＲＧＢデータ算出・逆フーリエ
変換の処理の順に演算を行なうことで演算処理時間が少
なくなる。

【００３８】（２）演算順序検出回路が、第ｋ（ｋ＝１
〜ｐ）の演算回路に入力する第ｋの入力データの数と、
出力される第ｋの出力データの数の関係を用いて演算順
序を検出することにより、演算処理時間が少なくなる。

【００３９】（３）演算順序検出回路が、演算処理時間
の少ない演算順序を検出し、検出された順番通りに第１
の演算〜第ｐの演算を処理することで、演算処理時間が
少なくなる。

【図面の簡単な説明】

【図１】本発明の演算装置の一実施例の動作を示すブロ
ック図である。

【図２】本発明の演算装置の一実施例の処理を示すフロ
ーチャート図である。

【図３】ボリューム・レンダリングに光源の効果を与え
る場合を示す図である。

【図４】従来の技術の演算装置の動作を示すブロック図
である。

【図５】ＲＧＢデータ算出部の構成を示すブロック図で
ある。

【符号の説明】

１・・演算順序検出回路 ２・・逆フーリエ変換回路 ３・・ＲＧＢデータ算出回路 ４〜６・・マルチプレクサ（ＭＰＸ） Ｆ１・・入力データ Ｆ２・・出力データ

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 9365−5Ｈ Ｇ０６Ｆ 15/72 ４６５

Claims (6)

【特許請求の範囲】
1. 【請求項１】演算順序の交換が可能なｐ個の演算（第１
   の演算〜第ｐの演算）を行う演算装置において、 演算処理時間が少ない演算順序を検出する演算順序検出
   回路と、 上記第１の演算〜第ｐの演算をそれぞれ処理する第１の
   演算回路〜第ｐの演算回路とを有し、上記演算順序検出
   回路により検出された順番どおりに上記ｐ個の演算を上
   記第１の演算回路〜第ｐの演算回路にて演算することを
   特徴とする演算装置。
2. 【請求項２】請求項第１項記載の演算装置において、上
   記演算順序検出回路は、上記第ｋ（ｋ＝１〜ｐ）の演算
   回路に入力する第ｋの入力データの数と出力される第ｋ
   の出力データの数の関係を用いて演算順序を検出するこ
   とを特徴とする演算装置。
3. 【請求項３】請求項１または２記載の演算装置におい
   て、上記ｐは２であり、上記第１の演算回路は逆フーリ
   エ変換を処理する回路であり、上記第２の演算回路は上
   記第２の演算回路に入力されるデータにＲＧＢ係数を乗
   算してＲＧＢの成分毎に加算するＲＧＢデータ算出回路
   であることを特徴とする演算装置。
4. 【請求項４】演算順序の交換が可能なｐ個の演算（第１
   の演算〜第ｐの演算）を行う演算方法において、 演算処理時間が少ない演算順序を検出する為の演算順序
   検出処理を行い、 上記演算順序検出処理により検出された順番どおりに上
   記ｐ個の演算を行うことを特徴とする演算方法。
5. 【請求項５】請求項第４項記載の演算方法において、上
   記演算順序検出処理は、上記第ｋ（ｋ＝１〜ｐ）の演算
   に入力する第ｋの入力データの数と出力される第ｋの出
   力データの数の関係を用いて演算順序を検出していくこ
   とを特徴とする演算方法。
6. 【請求項６】請求項４または５記載の演算方法におい
   て、上記ｐは２であり、上記第１の演算は逆フーリエ変
   換を処理する演算であり、上記第２の演算は上記第２の
   演算に入力されるデータにＲＧＢ係数を乗算してＲＧＢ
   の成分毎に加算するＲＧＢデータ算出であることを特徴
   とする演算方法。