JPH0697465B2 - ３次元の面の定義を発生する装置及び方法、並びにグラフィック表示システム - Google Patents
３次元の面の定義を発生する装置及び方法、並びにグラフィック表示システムInfo
- Publication number
- JPH0697465B2 JPH0697465B2 JP63289055A JP28905588A JPH0697465B2 JP H0697465 B2 JPH0697465 B2 JP H0697465B2 JP 63289055 A JP63289055 A JP 63289055A JP 28905588 A JP28905588 A JP 28905588A JP H0697465 B2 JPH0697465 B2 JP H0697465B2
- Authority
- JP
- Japan
- Prior art keywords
- cube
- value
- small
- cubes
- vertex
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three-dimensional [3D] modelling for computer graphics
- G06T17/005—Tree description, e.g. octree, quadtree
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T1/00—General purpose image data processing
- G06T1/20—Processor architectures; Processor configuration, e.g. pipelining
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three-dimensional [3D] modelling for computer graphics
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Geometry (AREA)
- Software Systems (AREA)
- Computer Graphics (AREA)
- Image Generation (AREA)
- Apparatus For Radiation Diagnosis (AREA)
- Image Processing (AREA)
- Magnetic Resonance Imaging Apparatus (AREA)
- Ultra Sonic Daignosis Equipment (AREA)
- Analysing Materials By The Use Of Radiation (AREA)
- Investigating Or Analyzing Materials By The Use Of Ultrasonic Waves (AREA)
Description
【発明の詳細な説明】 産業上の利用分野 本発明は、全般的には断層写真データの３次元（3D）表
示に関し、更に具体的に言えば、ベクトル動作に対して
最適にされたアレイ・プロセッサで行うような、アレイ
処理技術を採用することによって処理速度を高めること
に関する。
示に関し、更に具体的に言えば、ベクトル動作に対して
最適にされたアレイ・プロセッサで行うような、アレイ
処理技術を採用することによって処理速度を高めること
に関する。
従来の技術 断層写真による医療用作像は、身体の断面を表すデータ
の集合を用いる。複数の物体の照会値を数学的に処理し
て、隣接する断面像の表示を発生することができる。こ
のような断面像は、身体の内部構造を非侵入形に検査す
る上で、診断医師にとって非常に価値がある。データを
収集するために用いられる方法は、本発明にとって重要
ではない。例えば、Ｘ線計算機式断層写真法、核磁気共
鳴断層写真法、単一光子放出断層写真法、ポジトロン放
出断層写真法又は超音波断層写真法のような任意の方法
が同じように役に立つ。
の集合を用いる。複数の物体の照会値を数学的に処理し
て、隣接する断面像の表示を発生することができる。こ
のような断面像は、身体の内部構造を非侵入形に検査す
る上で、診断医師にとって非常に価値がある。データを
収集するために用いられる方法は、本発明にとって重要
ではない。例えば、Ｘ線計算機式断層写真法、核磁気共
鳴断層写真法、単一光子放出断層写真法、ポジトロン放
出断層写真法又は超音波断層写真法のような任意の方法
が同じように役に立つ。
作像する身体は３次元である。断層写真装置が、身体を
通る選択可能な軸線に沿った一連の隣接する断面スライ
スとして提示するために、データを処理する。
通る選択可能な軸線に沿った一連の隣接する断面スライ
スとして提示するために、データを処理する。
各々の断面スライスは、多数の行及び列の容積要素（あ
る面が各々のスライス内の画素の間隔と対応しており、
他の面がスライスの間隔と対応しているような平行六面
体の容積）で構成されており、その各々が容積要素内の
計算された信号強度に関係するディジタル形で記憶され
る数によって表される。実際には、例えば64個のスライ
スから成っている配列は、それぞれ512×512個の容積要
素を有していることがある。普通に使用するときには、
診断医師は、多数の個別のスライスの像を見て、所望の
情報を取り出す。身体内部のある面に関する情報を希望
する場合、診断医師は、断面スライスの照会から導出し
た物体が３次元の性質を有することを推測することに頼
る。ときには、隣接するスライスを見ることによって、
必要な推測に達することが困難であるか又は不可能であ
る。このような場合、合成３次元像があれば貴重であ
る。
る面が各々のスライス内の画素の間隔と対応しており、
他の面がスライスの間隔と対応しているような平行六面
体の容積）で構成されており、その各々が容積要素内の
計算された信号強度に関係するディジタル形で記憶され
る数によって表される。実際には、例えば64個のスライ
スから成っている配列は、それぞれ512×512個の容積要
素を有していることがある。普通に使用するときには、
診断医師は、多数の個別のスライスの像を見て、所望の
情報を取り出す。身体内部のある面に関する情報を希望
する場合、診断医師は、断面スライスの照会から導出し
た物体が３次元の性質を有することを推測することに頼
る。ときには、隣接するスライスを見ることによって、
必要な推測に達することが困難であるか又は不可能であ
る。このような場合、合成３次元像があれば貴重であ
る。
断層写真データから３次元像を合成することは、２つの
工程から成っている方法である。第１の工程では、所望
の物体の数学的な記述を断層写真データから抽出する。
第２の工程では、この数学的な記述から像を合成する。
工程から成っている方法である。第１の工程では、所望
の物体の数学的な記述を断層写真データから抽出する。
第２の工程では、この数学的な記述から像を合成する。
最初に第２の工程を取り上げて、スライスの知識から、
面の記述を合成することができると仮定すると、問題
は、この面から３次元像に移すことである。物体の数学
的な記述は、非常に多数の表面要素（SURFEL）の結合で
構成されている。計算機支援設計及び計算機支援製造に
端を発する普通のコンピュータ・グラフィックス・ソフ
トウェアをSURFELに作用させて、合成された２次元像を
介して像の解釈を助けるために、物体に表面の陰影（シ
ェイディング）を付ける。コンピュータ・グラフィック
ス・ソフトウェアはSURFELをラスタ化像に投影し、ラス
タ化像のどの画素がターンオンであるか、又、どんな強
度又は色であるかを決定する。一般的に、陰影は、オペ
レータによって選択される視線に沿った面の法線を有す
る像の要素では最も明るく（即ち、最も強く）、視線に
対して傾斜した要素では、次第に暗くなる。面の法線が
選択された視線から90゜よりも大きな角度だけ傾斜した
像の要素は、３次元物体内で隠れており、表示されな
い。視線上の前景の物体が背景の物体を隠す。陰影は、
３次元の現実的な感じを持たせる。
面の記述を合成することができると仮定すると、問題
は、この面から３次元像に移すことである。物体の数学
的な記述は、非常に多数の表面要素（SURFEL）の結合で
構成されている。計算機支援設計及び計算機支援製造に
端を発する普通のコンピュータ・グラフィックス・ソフ
トウェアをSURFELに作用させて、合成された２次元像を
介して像の解釈を助けるために、物体に表面の陰影（シ
ェイディング）を付ける。コンピュータ・グラフィック
ス・ソフトウェアはSURFELをラスタ化像に投影し、ラス
タ化像のどの画素がターンオンであるか、又、どんな強
度又は色であるかを決定する。一般的に、陰影は、オペ
レータによって選択される視線に沿った面の法線を有す
る像の要素では最も明るく（即ち、最も強く）、視線に
対して傾斜した要素では、次第に暗くなる。面の法線が
選択された視線から90゜よりも大きな角度だけ傾斜した
像の要素は、３次元物体内で隠れており、表示されな
い。視線上の前景の物体が背景の物体を隠す。陰影は、
３次元の現実的な感じを持たせる。
次に断層写真スライス・データから所望の面の数学的な
記述を抽出する問題について言うと、この工程は、２つ
のサブタスク、即ち断層写真データから物体を抽出する
ことと、抽出された物体に面をはめ合わせる（フィッテ
ィング）こととに分解される。第１のサブタスクを行う
ために多数の方法を利用し得る。例えば、スライスの容
積要素の信号強度を探索して、物体を形成している材料
が周囲の領域に対して十分な信号のコントラストを有す
るような領域を区別することが可能である。例えば、Ｘ
線計算機式断層写真法の骨に特有な信号強度は、周囲の
組織に対して強いコントラストを有している。このと
き、容積要素に閾値を適用して、完全な配列のうち、所
望の物体内にあるそれぞれの容積要素を、物体内にない
すべての容積要素から区別することができる。
記述を抽出する問題について言うと、この工程は、２つ
のサブタスク、即ち断層写真データから物体を抽出する
ことと、抽出された物体に面をはめ合わせる（フィッテ
ィング）こととに分解される。第１のサブタスクを行う
ために多数の方法を利用し得る。例えば、スライスの容
積要素の信号強度を探索して、物体を形成している材料
が周囲の領域に対して十分な信号のコントラストを有す
るような領域を区別することが可能である。例えば、Ｘ
線計算機式断層写真法の骨に特有な信号強度は、周囲の
組織に対して強いコントラストを有している。このと
き、容積要素に閾値を適用して、完全な配列のうち、所
望の物体内にあるそれぞれの容積要素を、物体内にない
すべての容積要素から区別することができる。
次に第２のサブタスクについて言うと、３次元面を抽出
された物体にはめ合わせる（フィッティングする）１つ
の方式が、1985年８月28日に出願された係属中の米国特
許出願番号第770164号に記載された分割キューブ方法の
名前で知られている。分割キューブ方法では、関心のあ
る面が、多数の方向決めされた点の結合によって表され
る。方向決めされた点は、隣接するスライスのデータベ
ース内の、立方体として隣接している８つの容積要素の
各組を考えることによって求められる。差分方程式を用
いて、立方体の頂点に対する勾配の値を計算する。面が
大きなキューブを通過すれば、そのキューブを小分けし
て、小キューブ又は小容積要素と呼ぶ多数の一層小さい
キューブを形成する。隣接する点の密度及び勾配の値を
補間することにより、小キューブの頂点に対する密度が
計算され、小キューブの中心に対する勾配が計算され
る。密度を試験する（例えば、閾値と比較する。）。あ
るものが閾値よりも大きく、あるものが閾値よりも小さ
ければ、そのとき、面はその小キューブを通る。その場
合、その小キューブの位置を正規化された勾配と共に、
方向決めされた点として出力する。ある範囲の密度（例
えば、上側及び下側の閾値）を用いて面を限定すること
も可能である。面がその中を通過する大きなキューブ内
のすべての小キューブを試験することによって発生され
たすべての方向決めされた点の結合が、面の表示とな
る。その後、方向決めされた点を、例えばCRTで表示す
るために処理する（即ち、ラスタ化する。）。
された物体にはめ合わせる（フィッティングする）１つ
の方式が、1985年８月28日に出願された係属中の米国特
許出願番号第770164号に記載された分割キューブ方法の
名前で知られている。分割キューブ方法では、関心のあ
る面が、多数の方向決めされた点の結合によって表され
る。方向決めされた点は、隣接するスライスのデータベ
ース内の、立方体として隣接している８つの容積要素の
各組を考えることによって求められる。差分方程式を用
いて、立方体の頂点に対する勾配の値を計算する。面が
大きなキューブを通過すれば、そのキューブを小分けし
て、小キューブ又は小容積要素と呼ぶ多数の一層小さい
キューブを形成する。隣接する点の密度及び勾配の値を
補間することにより、小キューブの頂点に対する密度が
計算され、小キューブの中心に対する勾配が計算され
る。密度を試験する（例えば、閾値と比較する。）。あ
るものが閾値よりも大きく、あるものが閾値よりも小さ
ければ、そのとき、面はその小キューブを通る。その場
合、その小キューブの位置を正規化された勾配と共に、
方向決めされた点として出力する。ある範囲の密度（例
えば、上側及び下側の閾値）を用いて面を限定すること
も可能である。面がその中を通過する大きなキューブ内
のすべての小キューブを試験することによって発生され
たすべての方向決めされた点の結合が、面の表示とな
る。その後、方向決めされた点を、例えばCRTで表示す
るために処理する（即ち、ラスタ化する。）。
上に述べた分割キューブ方法は、直列コンピュータで実
行されるように仕立てられている。しかしながら、大抵
の断層写真医療診断用作像システムは、走査データから
２次元のスライス像を再構成するために典型的に用いら
れるアレイ・プロセッサを含んでいる。アレイ・プロセ
ッサは、データの配列に作用するときにベクトル処理を
用いている。典型的にはアレイ・プロセッサを利用する
ことができ、アレイ・プロセッサを用いることによっ
て、像の処理が促進される可能性があるので、３次元像
を処理するために、診断用作像装置に付設されているア
レイ・プロセッサを用いて、分割キューブ方法を実施す
ることが望ましい。
行されるように仕立てられている。しかしながら、大抵
の断層写真医療診断用作像システムは、走査データから
２次元のスライス像を再構成するために典型的に用いら
れるアレイ・プロセッサを含んでいる。アレイ・プロセ
ッサは、データの配列に作用するときにベクトル処理を
用いている。典型的にはアレイ・プロセッサを利用する
ことができ、アレイ・プロセッサを用いることによっ
て、像の処理が促進される可能性があるので、３次元像
を処理するために、診断用作像装置に付設されているア
レイ・プロセッサを用いて、分割キューブ方法を実施す
ることが望ましい。
アレイ・プロセッサは、ホスト・コンピュータから供給
された複数のデータ要素（即ち、ベクトル）に対して種
々の操作（これをベクトル・ルーチンと呼ぶ。）を遂行
し、ときにはこれらの操作と同時にメモリ・アクセスの
ような他のタスクをも遂行するように設計されており、
これは、すべての動作が順次である直列コンピュータと
は対照的である。このため、アレイ・プロセッサの動作
及びプログラミングは、直列コンピュータとはかなり異
なる。更に、データ及びパラメータを設定するためのベ
クトル・ルーチンを行うためには、ある長さのオーバヘ
ッドが必要である。ベクトル・ルーチンによって処理す
る配列が十分大きくないと、オーバヘッドのために、運
転時間は悪化する。
された複数のデータ要素（即ち、ベクトル）に対して種
々の操作（これをベクトル・ルーチンと呼ぶ。）を遂行
し、ときにはこれらの操作と同時にメモリ・アクセスの
ような他のタスクをも遂行するように設計されており、
これは、すべての動作が順次である直列コンピュータと
は対照的である。このため、アレイ・プロセッサの動作
及びプログラミングは、直列コンピュータとはかなり異
なる。更に、データ及びパラメータを設定するためのベ
クトル・ルーチンを行うためには、ある長さのオーバヘ
ッドが必要である。ベクトル・ルーチンによって処理す
る配列が十分大きくないと、オーバヘッドのために、運
転時間は悪化する。
前に定義した工程に従って、分割キューブ方法を実施す
るようにアレイ・プロセッサをプログラムするとき、像
に対する面を発生する時間は極めて長く、直列コンピュ
ータのときよりもずっと長い。このように運転時間が長
くなるのは、分割キューブ方法に特有の直列方式と、ア
レイ・プロセッサがベクトル形である性質との非両立性
のため、並びにベクトル・ルーチンを呼び出す度に利用
し得る要素の数に比べてオーバヘッドの割合が大きいた
めである。
るようにアレイ・プロセッサをプログラムするとき、像
に対する面を発生する時間は極めて長く、直列コンピュ
ータのときよりもずっと長い。このように運転時間が長
くなるのは、分割キューブ方法に特有の直列方式と、ア
レイ・プロセッサがベクトル形である性質との非両立性
のため、並びにベクトル・ルーチンを呼び出す度に利用
し得る要素の数に比べてオーバヘッドの割合が大きいた
めである。
従って、本発明の主な目的は、３次元グラフィック・デ
ータを敏速に処理する方法及び装置を提供することであ
る。
ータを敏速に処理する方法及び装置を提供することであ
る。
本発明の他の目的は、ベクトル処理を用いて実行するの
に適するように、断層写真データから面の定義を抽出す
る改良された分解キューブ方法を提供することである。
に適するように、断層写真データから面の定義を抽出す
る改良された分解キューブ方法を提供することである。
本発明の他の目的は、アレイ・プロセッサで３次元像の
面を発生するときに、オーバヘッドの影響を少なくする
ことである。
面を発生するときに、オーバヘッドの影響を少なくする
ことである。
発明の要約 本発明の上述及びその他の目的が、分割キューブ方法を
改良して、断層写真データベース内の１次元の軸線（例
えば、行）に沿った複数の要素を同時に処理することに
よって達成される。好ましい実施例では、複数の大きな
キューブを同時に処理し、面が通るキューブを待ち行列
に送る。
改良して、断層写真データベース内の１次元の軸線（例
えば、行）に沿った複数の要素を同時に処理することに
よって達成される。好ましい実施例では、複数の大きな
キューブを同時に処理し、面が通るキューブを待ち行列
に送る。
待ち行列が、小分けを行うベクトル・ルーチンに要求さ
れるオーバヘッドに見合うくらいの数の要素を有してい
るときに、待ち行列からのキューブを小分けする。一実
施例では、小キューブの密度及び勾配の値を発生するた
めに用いられる３重１次補間を、多項式補間を用いて実
施し、１つの小キューブに対するすべての値が、同じ大
きなキューブ内にある他の小キューブとは独立に見つけ
られるようにする。多項式を評価するときに級数近似を
用いることにより、速度及びメモリの利用度を更に改善
する。
れるオーバヘッドに見合うくらいの数の要素を有してい
るときに、待ち行列からのキューブを小分けする。一実
施例では、小キューブの密度及び勾配の値を発生するた
めに用いられる３重１次補間を、多項式補間を用いて実
施し、１つの小キューブに対するすべての値が、同じ大
きなキューブ内にある他の小キューブとは独立に見つけ
られるようにする。多項式を評価するときに級数近似を
用いることにより、速度及びメモリの利用度を更に改善
する。
本発明の新規な特徴は、特許請求の範囲に具体的に記載
してあるが、本発明自体の構成、作用、並びにその他の
目的及び利点は、以下図面について説明するところから
最もよく理解されよう。
してあるが、本発明自体の構成、作用、並びにその他の
目的及び利点は、以下図面について説明するところから
最もよく理解されよう。
実施例 第１図には、節（ノード）14を辺16によって接続して構
成されているキューブ12の配列を含んでいる断層写真配
列の一部が、全体的に参照番号10で示されている。各々
の節14は、断層写真データの容積要素の信号の振幅を表
しており、各々の辺16は、１つの容積要素とその隣りの
容積要素との間の距離を表している。ここで説明する容
積をキューブと呼ぶが、辺16は必ずしもすべて同じ長さ
ではなく、普通はスライスの厚さがスライス内の画素の
解像度と等しくないので、辺16はすべて同じ長さではな
い場合の方が多い。キューブ12に対する画素の間隔Ｐ及
びＱと、スライスの間隔Ｓとが示されている。
成されているキューブ12の配列を含んでいる断層写真配
列の一部が、全体的に参照番号10で示されている。各々
の節14は、断層写真データの容積要素の信号の振幅を表
しており、各々の辺16は、１つの容積要素とその隣りの
容積要素との間の距離を表している。ここで説明する容
積をキューブと呼ぶが、辺16は必ずしもすべて同じ長さ
ではなく、普通はスライスの厚さがスライス内の画素の
解像度と等しくないので、辺16はすべて同じ長さではな
い場合の方が多い。キューブ12に対する画素の間隔Ｐ及
びＱと、スライスの間隔Ｓとが示されている。
本発明を実施する際、表示すべき面（閾値との比較によ
って決定される）を含んでいる各々の大きなキューブを
整数（０よりも大きいか又は０と等しい）によって多数
の小キューブに小分けする。小キューブの頂点を閾値
（１つ又は複数）と比較して、面がその中を通るような
小キューブを確認する。このように確認された小キュー
ブでは、小キューブの位置及び小キューブの中心に対す
る規格化勾配を結合して、方向決めされた点を求める。
小分け過程は、第２図に示す大きなキューブと隣接して
いる点を用いる。断層写真データのうちの立方体として
隣接している容積要素を選択して、大きなキューブの頂
点V1〜V8を表す。点W1〜W24が頂点V1〜V8に隣接してお
り、大きなキューブの頂点における勾配を計算するため
に、頂点V1〜V8と共に用いられる。その後、キューブ及
び勾配に対する補間を実行することができる。
って決定される）を含んでいる各々の大きなキューブを
整数（０よりも大きいか又は０と等しい）によって多数
の小キューブに小分けする。小キューブの頂点を閾値
（１つ又は複数）と比較して、面がその中を通るような
小キューブを確認する。このように確認された小キュー
ブでは、小キューブの位置及び小キューブの中心に対す
る規格化勾配を結合して、方向決めされた点を求める。
小分け過程は、第２図に示す大きなキューブと隣接して
いる点を用いる。断層写真データのうちの立方体として
隣接している容積要素を選択して、大きなキューブの頂
点V1〜V8を表す。点W1〜W24が頂点V1〜V8に隣接してお
り、大きなキューブの頂点における勾配を計算するため
に、頂点V1〜V8と共に用いられる。その後、キューブ及
び勾配に対する補間を実行することができる。
第３図はキューブの頂点に関連する勾配の例を示す。第
４図は大きなキューブ内の小キューブを限定している補
間された小キューブ及び勾配の法線を表す。第５図は相
異なる軸線に沿って相異なる補間の係数を有している小
キューブを示す。
４図は大きなキューブ内の小キューブを限定している補
間された小キューブ及び勾配の法線を表す。第５図は相
異なる軸線に沿って相異なる補間の係数を有している小
キューブを示す。
第６図のフローチャートについて、分割キューブ方法自
体を更に詳しく説明する。このフローチャートは開始ブ
ロック25から始まる。工程26及び27で、８つ１組の密度
関数ｆ（x,y,z）、即ち、ｉを行、ｊを列、ｋを断層写
真データ内のスライスとして、［ｆ（i,j,k）、ｆ（ｉ
＋1,j,k）、ｆ（i,j＋1,k）、ｆ（ｉ＋1,j＋1,k）、ｆ
（i,j,k＋１）、ｆ（ｉ＋1,j,k＋１）、ｆ（i,j＋1,k＋
１）、ｆ（ｉ＋1,j＋1,k＋１）］で構成されている大き
なキューブ（即ち、マーチング・キューブ）を求める。
Ｎ行、Ｎ列及びＭ個のスライス（即ち、ＭはＮ×Ｎ個の
２次元像の数である）を有しているデータベースでは、
ｉ＝２、………、Ｎ−1;j＝２、………、Ｎ−1;及びｋ
＝２、………、Ｍのすべての組み合わせをループ状に通
ることにより、マーチング・キューブが求められる。
体を更に詳しく説明する。このフローチャートは開始ブ
ロック25から始まる。工程26及び27で、８つ１組の密度
関数ｆ（x,y,z）、即ち、ｉを行、ｊを列、ｋを断層写
真データ内のスライスとして、［ｆ（i,j,k）、ｆ（ｉ
＋1,j,k）、ｆ（i,j＋1,k）、ｆ（ｉ＋1,j＋1,k）、ｆ
（i,j,k＋１）、ｆ（ｉ＋1,j,k＋１）、ｆ（i,j＋1,k＋
１）、ｆ（ｉ＋1,j＋1,k＋１）］で構成されている大き
なキューブ（即ち、マーチング・キューブ）を求める。
Ｎ行、Ｎ列及びＭ個のスライス（即ち、ＭはＮ×Ｎ個の
２次元像の数である）を有しているデータベースでは、
ｉ＝２、………、Ｎ−1;j＝２、………、Ｎ−1;及びｋ
＝２、………、Ｍのすべての組み合わせをループ状に通
ることにより、マーチング・キューブが求められる。
各々の大きなキューブに対して、工程28で８つの頂点を
閾値Ｔと比較する。頂点に対するすべての値が閾値より
も大きいか、又はすべてが閾値よりも小さければ、面は
この大きなキューブを通らず、従って、この方法は、工
程29ですべての大きなキューブが処理されたかどうかを
調べる。済んでいれば、この方法は停止ブロック30で停
止し、その後、（定義された面の処理及び表示のよう
な）他の機能を実施することができる。そうでなけれ
ば、工程26に戻り、他の大きなキューブの処理を開始す
る。
閾値Ｔと比較する。頂点に対するすべての値が閾値より
も大きいか、又はすべてが閾値よりも小さければ、面は
この大きなキューブを通らず、従って、この方法は、工
程29ですべての大きなキューブが処理されたかどうかを
調べる。済んでいれば、この方法は停止ブロック30で停
止し、その後、（定義された面の処理及び表示のよう
な）他の機能を実施することができる。そうでなけれ
ば、工程26に戻り、他の大きなキューブの処理を開始す
る。
工程28で、閾値よりも大きい頂点及び小さい頂点がある
ことが判定されると、次に工程31で、大きなキューブの
各々の頂点における勾配の値を計算する。大きなキュー
ブ内の各々の頂点（i,j,k）に対する勾配推定値ｇ（i,
j,k）＝［gx（i,i,k）,gy（i,j,k）,gz（i,j,k）］を計
算するために、中心の差を用いることができる。これを
次の式に示す。
ことが判定されると、次に工程31で、大きなキューブの
各々の頂点における勾配の値を計算する。大きなキュー
ブ内の各々の頂点（i,j,k）に対する勾配推定値ｇ（i,
j,k）＝［gx（i,i,k）,gy（i,j,k）,gz（i,j,k）］を計
算するために、中心の差を用いることができる。これを
次の式に示す。
gx（i,j,k）＝［ｆ（ｉ＋1,j,k）−ｆ（ｉ−1,j,k）］c
1 gy（i,j,k）＝［ｆ（i,j＋1,k）−ｆ（i,j−1,k）］c2 gz（i,j,k）＝［ｆ（i,j,k＋１）−ｆ（i,j,k−１）］c
3 ここで、c1、c2、c3は断層写真データ内の画素の間隔及
びスライスの間隔に関係する定数である。こうして、そ
れぞれgx、gy及びgzから成っている８つの値が見つか
る。
1 gy（i,j,k）＝［ｆ（i,j＋1,k）−ｆ（i,j−1,k）］c2 gz（i,j,k）＝［ｆ（i,j,k＋１）−ｆ（i,j,k−１）］c
3 ここで、c1、c2、c3は断層写真データ内の画素の間隔及
びスライスの間隔に関係する定数である。こうして、そ
れぞれgx、gy及びgzから成っている８つの値が見つか
る。
工程32で、３重１次補間により、小キューブの頂点に対
する密度の値を見つける。ｉ、ｊ及びｋに対応して、正
の整数の補間係数Ａ、Ｂ及びＣを用いると、大きなキュ
ーブ内の小キューブの増分は、Δｉ＝1/A、Δｊ＝1/B、
及びΔｋ＝1/Cとそれぞれ定義される。各々の大きなキ
ューブの頂点ｖ（i,j,k）をｖ（0,0,0）、ｖ（1,0,
0）、ｖ（0,1,0）、ｖ（1,1,0）、ｖ（0,0,1）、ｖ（1,
0,1）、ｖ（0,1,1）、及びｖ（1,1,1）と表す。１次補
間により、各々の小キューブの頂点には、ｆ（ｉ＋ＩΔ
i,j＋ＪΔj,k＋ＫΔｋ）として定義される密度ｆ′（I,
J,K）が得られる。ここで、Ｉ＝０、１、………、A;J＝
０、１、………、B;K＝０、１、………、Ｃである。
する密度の値を見つける。ｉ、ｊ及びｋに対応して、正
の整数の補間係数Ａ、Ｂ及びＣを用いると、大きなキュ
ーブ内の小キューブの増分は、Δｉ＝1/A、Δｊ＝1/B、
及びΔｋ＝1/Cとそれぞれ定義される。各々の大きなキ
ューブの頂点ｖ（i,j,k）をｖ（0,0,0）、ｖ（1,0,
0）、ｖ（0,1,0）、ｖ（1,1,0）、ｖ（0,0,1）、ｖ（1,
0,1）、ｖ（0,1,1）、及びｖ（1,1,1）と表す。１次補
間により、各々の小キューブの頂点には、ｆ（ｉ＋ＩΔ
i,j＋ＪΔj,k＋ＫΔｋ）として定義される密度ｆ′（I,
J,K）が得られる。ここで、Ｉ＝０、１、………、A;J＝
０、１、………、B;K＝０、１、………、Ｃである。
工程33で、大きなキューブの頂点における勾配gx、gy及
びgzの３重１次補間を用いて、各々の小キューブの中心
に対する勾配の値を計算する。ｘ、ｙ及びｚ成分の各々
に対する小キューブの勾配（それぞれ成分gx、gy及びgz
を有しているベクトルＧ（I,J,K））は、Ｇx,y,z（I,J,
K）＝ｇx,y,z（ｉ＋［Ｉ＋0.5］Δi,j＋［Ｊ＋0.5］Δ
j,k＋［Ｋ＋0.5］Δｋ）である。ここで、Ｉ＝０、１、
………、Ａ−1;J＝０、１、………、Ｂ−1;K＝０、１、
………、Ｃ−１である。
びgzの３重１次補間を用いて、各々の小キューブの中心
に対する勾配の値を計算する。ｘ、ｙ及びｚ成分の各々
に対する小キューブの勾配（それぞれ成分gx、gy及びgz
を有しているベクトルＧ（I,J,K））は、Ｇx,y,z（I,J,
K）＝ｇx,y,z（ｉ＋［Ｉ＋0.5］Δi,j＋［Ｊ＋0.5］Δ
j,k＋［Ｋ＋0.5］Δｋ）である。ここで、Ｉ＝０、１、
………、Ａ−1;J＝０、１、………、Ｂ−1;K＝０、１、
………、Ｃ−１である。
小キューブ及びその勾配を計算した後、工程34で、Ｉ＝
０、………、Ａ−1;J＝０、………、Ｂ−1;及びＫ＝
０、………、Ｃ−１のすべての組み合わせを経由するこ
とにより、一度に１つずつ小キューブを取り出す。Ｉ、
Ｊ及びＫの各々の組み合わせに対して、小キューブは８
つの組［ｆ′（I,J,K）、ｆ′（Ｉ＋1,J,K）、ｆ′（I,
J＋1,K）、ｆ′（Ｉ＋1,J＋1,K）、ｆ′（I,J,K＋
１）、ｆ′（Ｉ＋1,J,K＋１）、ｆ′（I,J＋1,K＋
１）、ｆ′（Ｉ＋1,J＋1,K＋１）］によって限定され
る。工程35で、現在の小キューブを閾値に対して試験す
る。すべての小キューブの頂点が閾値よりも高くないか
又は全部低くない場合には、小キューブの位置及びその
規格化勾配を、工程36で、方向決めされた点として表
（テーブル）に出力する。そうでなければ、完了したか
どうかを工程37で検査する。工程36の間の表に対する勾
配の出力は、Ｇ（I,J,K）/|G（I,J,K）｜として定義さ
れる規格化勾配である。
０、………、Ａ−1;J＝０、………、Ｂ−1;及びＫ＝
０、………、Ｃ−１のすべての組み合わせを経由するこ
とにより、一度に１つずつ小キューブを取り出す。Ｉ、
Ｊ及びＫの各々の組み合わせに対して、小キューブは８
つの組［ｆ′（I,J,K）、ｆ′（Ｉ＋1,J,K）、ｆ′（I,
J＋1,K）、ｆ′（Ｉ＋1,J＋1,K）、ｆ′（I,J,K＋
１）、ｆ′（Ｉ＋1,J,K＋１）、ｆ′（I,J＋1,K＋
１）、ｆ′（Ｉ＋1,J＋1,K＋１）］によって限定され
る。工程35で、現在の小キューブを閾値に対して試験す
る。すべての小キューブの頂点が閾値よりも高くないか
又は全部低くない場合には、小キューブの位置及びその
規格化勾配を、工程36で、方向決めされた点として表
（テーブル）に出力する。そうでなければ、完了したか
どうかを工程37で検査する。工程36の間の表に対する勾
配の出力は、Ｇ（I,J,K）/|G（I,J,K）｜として定義さ
れる規格化勾配である。
すべての小キューブが処理されたときに、工程37が工程
29にブランチ（分岐）して、次の大きなキューブを処理
する。
29にブランチ（分岐）して、次の大きなキューブを処理
する。
普通の分割キューブ方法は、汎用計算機で操作されるよ
うに効率よく設計されている。しかしながら、このよう
に構成された方法は、大部分の処理が、フローチャート
の内側のループ（即ち、工程31〜工程37）内にある小キ
ューブの計算に関するものであるので、ベクトル処理に
なじまない。
うに効率よく設計されている。しかしながら、このよう
に構成された方法は、大部分の処理が、フローチャート
の内側のループ（即ち、工程31〜工程37）内にある小キ
ューブの計算に関するものであるので、ベクトル処理に
なじまない。
本発明の１つの工程が第７図に示されている。２次元
（2D）断層写真データが面発生器40に供給される。面発
生器40には、小キューブを形成するための補間係数も入
力されるが、これらの補間係数は、汎用計算機39のよう
な他の処理装置又はソフトウェアによって決定されてい
る。面発生器40は、ベクトル処理を用いて分割キューブ
方法を実施して、面を限定する多数の方向決めされた点
を発生し、それらの点が表示プロセッサ41に供給され
る。表示プロセッサ41は、電流変換マトリクス（CTM）
発生器42と、処理装置43とを含んでいる。
（2D）断層写真データが面発生器40に供給される。面発
生器40には、小キューブを形成するための補間係数も入
力されるが、これらの補間係数は、汎用計算機39のよう
な他の処理装置又はソフトウェアによって決定されてい
る。面発生器40は、ベクトル処理を用いて分割キューブ
方法を実施して、面を限定する多数の方向決めされた点
を発生し、それらの点が表示プロセッサ41に供給され
る。表示プロセッサ41は、電流変換マトリクス（CTM）
発生器42と、処理装置43とを含んでいる。
CTM発生器42は、物体の倍率、移動及び回転のための観
察者の指令を指令プロセッサ45から受け取ると共にCTM
を形成しており、このCTMが処理装置43に供給されて、
方向決めされた点に対して作用する。処理装置43は、３
次元像（方向決めされた点を３次元画素に投影し、照明
された画素の陰影を決定することを含んでいる）を合成
し、この３次元像はラスタ化され、表示装置44に送られ
る。表示装置44は、例えば陰極線管（CRT）であっても
よい。
察者の指令を指令プロセッサ45から受け取ると共にCTM
を形成しており、このCTMが処理装置43に供給されて、
方向決めされた点に対して作用する。処理装置43は、３
次元像（方向決めされた点を３次元画素に投影し、照明
された画素の陰影を決定することを含んでいる）を合成
し、この３次元像はラスタ化され、表示装置44に送られ
る。表示装置44は、例えば陰極線管（CRT）であっても
よい。
面発生器40における配列処理に適した改良された分割キ
ューブ方法が、第８図のブロック図に示されている。ベ
クトル処理のための十分なオペランドを供給するため
に、行処理方式が採用されている。即ち、１行内のすべ
ての列がベクトル関数によって一緒に処理されるので、
データを処理する間、列指数を特定しない。アレイ・プ
ロセッサ・メモリの規模に応じて、同時に１行よりも多
く又は少なく処理することができる。
ューブ方法が、第８図のブロック図に示されている。ベ
クトル処理のための十分なオペランドを供給するため
に、行処理方式が採用されている。即ち、１行内のすべ
ての列がベクトル関数によって一緒に処理されるので、
データを処理する間、列指数を特定しない。アレイ・プ
ロセッサ・メモリの規模に応じて、同時に１行よりも多
く又は少なく処理することができる。
ブロック50で、１行（又は何行か）のマーチング・キュ
ーブ及び関連した隣りの情報を受け取り、断層写真デー
タ内の物体を限定する閾値と比較する。物体の表面を含
んでいるキューブにラベル（記し）を付け、勾配を計算
するために、ブロック51に送る。小分けを十分速く行う
ことができれば、ブロック50を飛び越し、面がその中を
通らなくても、すべてのマーチング・キューブを処理の
ために小分けすることができる。しかしながら、好まし
い実施例では、大きいマーチング・キューブを試験して
ラベルを付けて、圧縮された行ベクトルを形成する。圧
縮ベクトルを用いることにより、処理を必要とするデー
タ量が減少するが、各々のマーチング・キューブの空間
的な位置を追跡するために、若干の余分の記録管理を必
要とする。
ーブ及び関連した隣りの情報を受け取り、断層写真デー
タ内の物体を限定する閾値と比較する。物体の表面を含
んでいるキューブにラベル（記し）を付け、勾配を計算
するために、ブロック51に送る。小分けを十分速く行う
ことができれば、ブロック50を飛び越し、面がその中を
通らなくても、すべてのマーチング・キューブを処理の
ために小分けすることができる。しかしながら、好まし
い実施例では、大きいマーチング・キューブを試験して
ラベルを付けて、圧縮された行ベクトルを形成する。圧
縮ベクトルを用いることにより、処理を必要とするデー
タ量が減少するが、各々のマーチング・キューブの空間
的な位置を追跡するために、若干の余分の記録管理を必
要とする。
ブロック51における勾配の計算は、ラベルを付けられた
各々のマーチング・キューブに対する頂点の勾配のｘ、
ｙ及びｚ成分に対応するそれぞれ８つから成る３組を発
生するために、中心差分方式を用いる。これらが圧縮ベ
クトル内で結合される。
各々のマーチング・キューブに対する頂点の勾配のｘ、
ｙ及びｚ成分に対応するそれぞれ８つから成る３組を発
生するために、中心差分方式を用いる。これらが圧縮ベ
クトル内で結合される。
ベクトル・ルーチンを呼び出すことにより、ベクトル内
にあるすべての要素に対して１回の操作（大抵は複素
数）が行われる。通常、このルーチンを作用させるため
には、いくらかのオーバヘッドがある。しかしながら、
ベクトル内にある要素の数が大きければ、オーバヘッド
を無視することができる。圧縮ベクトル内にある要素の
数は比較的小さくすることができる。この場合、ベクト
ル内の呼び出しに伴うオーバヘッドが、分割キューブの
運転時間を悪化させる。本発明の一実施例では、多数の
圧縮ベクトルを結合して、その結果得られるベクトルが
十分長くなるようにする。これは、ラベルを付けられた
キューブ及び勾配を受け取る待ち行列52によって行われ
る。待ち行列の寸法は、小分けベクトル・ルーチンの容
量に近い大きな結合ベクトルが得られるように選択され
ている。待ち行列が一杯であるときに、又はデータの最
後の行が閾値に対して試験されたときに、マーチング・
キューブ及び勾配を待ち行列から取り出し、小分けのた
めに送り出す。
にあるすべての要素に対して１回の操作（大抵は複素
数）が行われる。通常、このルーチンを作用させるため
には、いくらかのオーバヘッドがある。しかしながら、
ベクトル内にある要素の数が大きければ、オーバヘッド
を無視することができる。圧縮ベクトル内にある要素の
数は比較的小さくすることができる。この場合、ベクト
ル内の呼び出しに伴うオーバヘッドが、分割キューブの
運転時間を悪化させる。本発明の一実施例では、多数の
圧縮ベクトルを結合して、その結果得られるベクトルが
十分長くなるようにする。これは、ラベルを付けられた
キューブ及び勾配を受け取る待ち行列52によって行われ
る。待ち行列の寸法は、小分けベクトル・ルーチンの容
量に近い大きな結合ベクトルが得られるように選択され
ている。待ち行列が一杯であるときに、又はデータの最
後の行が閾値に対して試験されたときに、マーチング・
キューブ及び勾配を待ち行列から取り出し、小分けのた
めに送り出す。
従来の方法では、大きなキューブ内にあるすべての小キ
ューブに対する密度及び勾配が、一度に計算されてい
た。典型的な場合、小分けされる１行全体に対するすべ
ての値をアレイ・プロセッサ方法で一度に計算した場
合、各々の行にあるマーチング・キューブ当たり、64個
までの小キューブの各々に対して、４つの値（１つの密
度及び３つの勾配成分）を記憶するためには、128Kまで
の記憶位置又は更に多くが必要であり、１行には512個
までのキューブ又はそれ以上がある。
ューブに対する密度及び勾配が、一度に計算されてい
た。典型的な場合、小分けされる１行全体に対するすべ
ての値をアレイ・プロセッサ方法で一度に計算した場
合、各々の行にあるマーチング・キューブ当たり、64個
までの小キューブの各々に対して、４つの値（１つの密
度及び３つの勾配成分）を記憶するためには、128Kまで
の記憶位置又は更に多くが必要であり、１行には512個
までのキューブ又はそれ以上がある。
その中で用いられるメモリが高速形であるため、アレイ
・プロセッサ内にこのような大量のメモリを設けること
は経済的ではない。このような過剰な大きさのアレイ・
プロセッサのメモリの必要性を低下させるため、本発明
は、一度に各々のマーチング・キューブからの１つの小
キューブに対する密度と勾配とを計算し、これらを（１
つ又は複数の）閾値に対して試験する。小キューブの部
分集合からの方向決めされた点を出力した後に、小キュ
ーブの他の部分集合を計算する。一度にマーチング・キ
ューブ当たり１つの小キューブのみを計算することによ
り、小キューブ当たり４つの値を用い、１行当たり512
個の大きなキューブがある例では、2Kの記憶位置しか必
要としない。
・プロセッサ内にこのような大量のメモリを設けること
は経済的ではない。このような過剰な大きさのアレイ・
プロセッサのメモリの必要性を低下させるため、本発明
は、一度に各々のマーチング・キューブからの１つの小
キューブに対する密度と勾配とを計算し、これらを（１
つ又は複数の）閾値に対して試験する。小キューブの部
分集合からの方向決めされた点を出力した後に、小キュ
ーブの他の部分集合を計算する。一度にマーチング・キ
ューブ当たり１つの小キューブのみを計算することによ
り、小キューブ当たり４つの値を用い、１行当たり512
個の大きなキューブがある例では、2Kの記憶位置しか必
要としない。
大きなキューブ内の他のすべての小キューブとは独立し
て、選択された各々の小キューブを計算するために、本
発明は、第８図のブロック53〜55を用いる。即ち、従来
行われていたように、大きなキューブの周りの選択され
た順序での相次ぐ３重１次補間の代わりに、大きなキュ
ーブの値から導き出した１つの多項式の評価を用いる。
前に定義した大きなキューブの頂点ｖ（0,0,0）、……
…、ｖ（1,1,1）、補間係数Ａ、Ｂ及びＣ、並びに小キ
ューブ指数Ｉ、Ｊ及びＫ（Ｉ＝０、………、A;J＝０、
………、B;K＝０、………、Ｃ）を用いて、各々の小キ
ューブの頂点をｖ（α，β，γ）と定義する。ここで、
α＝I/A、β＝J/B、γ＝K/Cである。記号をわかり易く
するために、頂点ｖには添字を付けていないが、ｖ（0,
0,0）の値を有するベクトル、ｖ（0,0,1）の値を有する
ベクトルというように、いずれも待ち行列から取り出し
たマーチング・キューブの数と等しい数の要素を有して
いるベクトルがあることを承知されたい。本発明は、各
々の小キューブの頂点ｖ（α，β，γ）を得るために大
きなキューブの８つの頂点の３重の１次補間をすること
が、次の多項式を解くことになるという事実を利用す
る。
て、選択された各々の小キューブを計算するために、本
発明は、第８図のブロック53〜55を用いる。即ち、従来
行われていたように、大きなキューブの周りの選択され
た順序での相次ぐ３重１次補間の代わりに、大きなキュ
ーブの値から導き出した１つの多項式の評価を用いる。
前に定義した大きなキューブの頂点ｖ（0,0,0）、……
…、ｖ（1,1,1）、補間係数Ａ、Ｂ及びＣ、並びに小キ
ューブ指数Ｉ、Ｊ及びＫ（Ｉ＝０、………、A;J＝０、
………、B;K＝０、………、Ｃ）を用いて、各々の小キ
ューブの頂点をｖ（α，β，γ）と定義する。ここで、
α＝I/A、β＝J/B、γ＝K/Cである。記号をわかり易く
するために、頂点ｖには添字を付けていないが、ｖ（0,
0,0）の値を有するベクトル、ｖ（0,0,1）の値を有する
ベクトルというように、いずれも待ち行列から取り出し
たマーチング・キューブの数と等しい数の要素を有して
いるベクトルがあることを承知されたい。本発明は、各
々の小キューブの頂点ｖ（α，β，γ）を得るために大
きなキューブの８つの頂点の３重の１次補間をすること
が、次の多項式を解くことになるという事実を利用す
る。
ｖ（α，β，γ）＝D0＋D1α＋D2β＋D3γ＋D4αβ＋D5
αγ ＋D6βγ＋D7αβγ （１） ここで、 D0＝ｖ（0,0,0） D1＝ｖ（1,0,0）−ｖ（0,0,0） D2＝ｖ（0,1,0）−ｖ（0,0,0） D3＝ｖ（0,0,1）−ｖ（0,0,0） D4＝ｖ（1,1,0）−ｖ（0,1,0）−ｖ（1,0,0） ＋ｖ（0,0,0） D5＝ｖ（1,0,1）−ｖ（0,0,1）−ｖ（1,0,0） ＋ｖ（0,0,0） D6＝ｖ（0,1,1）−ｖ（0,0,1）−ｖ（0,1,0） ＋ｖ（0,0,0） D7＝ｖ（1,1,1）−ｖ（0,1,1）−ｖ（1,0,1） ＋ｖ（0,0,1）−ｖ（1,1,0）＋ｖ（0,1,0） ＋ｖ（1,0,0）−ｖ（0,0,0） α、β及びγは、大きなキューブの各々の小分けに対し
て同じである。従って、種々の組み合わせ（α，β，
γ，αβ，αγ，βγ，αβγ）にある３つのパラメー
タの値の配列を分割キューブに対する設定段階で計算す
ることができる。圧縮ベクトルを小分けする前に、密度
に対する［D0,………,D7］のベクトルを発生する。Ｇ
（I,J,K）から勾配の成分のために更に３組の［D0,……
…,D7］をも発生する。その後、４つの多項式を用い
て、各々の小キューブの頂点における密度の値と、Ｇ
（I,J,K）に対する多項式展開を用いて、各々の小キュ
ーブの中心における勾配の成分の値とを発生する。
αγ ＋D6βγ＋D7αβγ （１） ここで、 D0＝ｖ（0,0,0） D1＝ｖ（1,0,0）−ｖ（0,0,0） D2＝ｖ（0,1,0）−ｖ（0,0,0） D3＝ｖ（0,0,1）−ｖ（0,0,0） D4＝ｖ（1,1,0）−ｖ（0,1,0）−ｖ（1,0,0） ＋ｖ（0,0,0） D5＝ｖ（1,0,1）−ｖ（0,0,1）−ｖ（1,0,0） ＋ｖ（0,0,0） D6＝ｖ（0,1,1）−ｖ（0,0,1）−ｖ（0,1,0） ＋ｖ（0,0,0） D7＝ｖ（1,1,1）−ｖ（0,1,1）−ｖ（1,0,1） ＋ｖ（0,0,1）−ｖ（1,1,0）＋ｖ（0,1,0） ＋ｖ（1,0,0）−ｖ（0,0,0） α、β及びγは、大きなキューブの各々の小分けに対し
て同じである。従って、種々の組み合わせ（α，β，
γ，αβ，αγ，βγ，αβγ）にある３つのパラメー
タの値の配列を分割キューブに対する設定段階で計算す
ることができる。圧縮ベクトルを小分けする前に、密度
に対する［D0,………,D7］のベクトルを発生する。Ｇ
（I,J,K）から勾配の成分のために更に３組の［D0,……
…,D7］をも発生する。その後、４つの多項式を用い
て、各々の小キューブの頂点における密度の値と、Ｇ
（I,J,K）に対する多項式展開を用いて、各々の小キュ
ーブの中心における勾配の成分の値とを発生する。
第８図について説明すると、ブロック53が多項式の係数
を計算する。ブロック54は、一度に各々のマーチング・
キューブからの１つの小キューブを供給し、その小キュ
ーブに対する密度及び勾配をブロック55で計算する。ブ
ロック56で、各々の小キューブを閾値に対して試験し、
ブロック57で、面を含んでいる小キューブを方向決めさ
れた点として表に出力する。各々の方向決めされた点
は、小キューブの中心における規格化勾配のｘ、ｙ、ｚ
成分（gx,gy,gz）と小キューブの位置（x,y,z）とを結
合することによって形成される６つ１組で構成されてい
る。
を計算する。ブロック54は、一度に各々のマーチング・
キューブからの１つの小キューブを供給し、その小キュ
ーブに対する密度及び勾配をブロック55で計算する。ブ
ロック56で、各々の小キューブを閾値に対して試験し、
ブロック57で、面を含んでいる小キューブを方向決めさ
れた点として表に出力する。各々の方向決めされた点
は、小キューブの中心における規格化勾配のｘ、ｙ、ｚ
成分（gx,gy,gz）と小キューブの位置（x,y,z）とを結
合することによって形成される６つ１組で構成されてい
る。
ブロック55における密度の計算に戻って説明すると、各
々の小キューブは、小キューブの８つの頂点における密
度の計算を必要とする。この計算が多項式を８回評価す
ること（即ち、各々の頂点の空間的な位置で１回ずつ）
によって行われる場合には、64回の乗算−加算が必要に
なる。
々の小キューブは、小キューブの８つの頂点における密
度の計算を必要とする。この計算が多項式を８回評価す
ること（即ち、各々の頂点の空間的な位置で１回ずつ）
によって行われる場合には、64回の乗算−加算が必要に
なる。
本発明の一実施例では、ブロック55で必要な計算の回数
を、多項式補間のテーラ級数近似を用いることによって
減少させる。各々の頂点における密度関数をｘ（α，
β，γ）で表すとする。小キューブの中心が（a,b,c）
にあるとする。小キューブの８つの頂点は（ａ±δa,b
±δb,c±δｃ）で表される。ここで、δａ＝Δi/2、δ
ｂ＝Δj/2、δｃ＝Δk/2である。
を、多項式補間のテーラ級数近似を用いることによって
減少させる。各々の頂点における密度関数をｘ（α，
β，γ）で表すとする。小キューブの中心が（a,b,c）
にあるとする。小キューブの８つの頂点は（ａ±δa,b
±δb,c±δｃ）で表される。ここで、δａ＝Δi/2、δ
ｂ＝Δj/2、δｃ＝Δk/2である。
式（１）の１次テーラ級数展開は、次のようになる。
ｘ（α＋δα，β＋δβ，γ＋δγ） ＝ｘ（α，β，γ）＋Ｐαδａ＋Ｐβδｂ＋Ｐγδｃ ここで、Ｐα、Ｐβ及びＰγは、次のように表される偏
微分である。
微分である。
Ｐα＝D1＋D4β＋D5γ＋D7βγ Ｐβ＝D2＋D4α＋D6γ＋D7αγ Ｐγ＝D3＋D5α＋D6γ＋D7αβ 次に多項式を１回評価することによって、ｘ（a,b,c）
を見つけることができる。そのとき、密度の値は次のよ
うになる。
を見つけることができる。そのとき、密度の値は次のよ
うになる。
ｘ（ａ±δa,b±δb,c±δｃ） ＝ｘ（a,b,c）±Ｐαδａ±Ｐβδｂ±Ｐγδｃ この方法は、17回の乗算−加算と、27回の加算としか必
要としない。
要としない。
本発明のベクトル処理方法を更に例示するため、本発明
の最もよい態様のフローチャートが第９図に示されてい
る。この方法は開始ブロック60から始まる。工程61及び
62で、１行又は何行かの断層写真データ及び関連した隣
りの情報が入力され、マーチング・キューブの８つの組
が形成される。工程63で、キューブの各々の頂点におけ
る密度をオペレータが指定した閾値に対して試験し、面
を含んでいるすべてのキューブにラベルを付ける。工程
64で、どのキューブもラベルが付けられていなければ
（即ち、面が現在の行を通らない場合には）、方法は工
程73に飛び越して、未だ処理する行があるかどうかを試
験する。ラベルを付けられたキューブがあれば、ラベル
を付けられたすべてのキューブの頂点における勾配を工
程65で計算する。
の最もよい態様のフローチャートが第９図に示されてい
る。この方法は開始ブロック60から始まる。工程61及び
62で、１行又は何行かの断層写真データ及び関連した隣
りの情報が入力され、マーチング・キューブの８つの組
が形成される。工程63で、キューブの各々の頂点におけ
る密度をオペレータが指定した閾値に対して試験し、面
を含んでいるすべてのキューブにラベルを付ける。工程
64で、どのキューブもラベルが付けられていなければ
（即ち、面が現在の行を通らない場合には）、方法は工
程73に飛び越して、未だ処理する行があるかどうかを試
験する。ラベルを付けられたキューブがあれば、ラベル
を付けられたすべてのキューブの頂点における勾配を工
程65で計算する。
工程66で、ラベルを付けられたキューブ及びそれに関連
する勾配が待ち行列に入れられる。工程67で、待ち行列
が一枚かどうか、又は断層写真データ内の最後の行が処
理されたかどうかを試験する。待ち行列が一杯でなく、
未だ行があれば、方法は工程61に戻る。そうでなけれ
ば、工程68で多項式の係数が計算される。
する勾配が待ち行列に入れられる。工程67で、待ち行列
が一枚かどうか、又は断層写真データ内の最後の行が処
理されたかどうかを試験する。待ち行列が一杯でなく、
未だ行があれば、方法は工程61に戻る。そうでなけれ
ば、工程68で多項式の係数が計算される。
工程69で、各々のマーチング・キューブからそれぞれの
小キューブを取り出す。工程70で、密度及び勾配を計算
する。工程71で、各々の小キューブを閾値と比較し、面
を含んでいるすべての小キューブが、、それらの勾配と
共に、表に出力される。現在待ち行列から取り出したマ
ーチング・キューブに未だ処理すべき小キューブがある
場合には、工程72から工程69に戻る。そうでなければ、
工程73で、処理されていない残りの行があるかどうかを
検査する。一旦すべての行が処理されれば、この方法は
停止ブロック74で止まる。
小キューブを取り出す。工程70で、密度及び勾配を計算
する。工程71で、各々の小キューブを閾値と比較し、面
を含んでいるすべての小キューブが、、それらの勾配と
共に、表に出力される。現在待ち行列から取り出したマ
ーチング・キューブに未だ処理すべき小キューブがある
場合には、工程72から工程69に戻る。そうでなければ、
工程73で、処理されていない残りの行があるかどうかを
検査する。一旦すべての行が処理されれば、この方法は
停止ブロック74で止まる。
第９図の大部分の工程は、ベクトル操作として実行され
得る。従って、この方法は、３次元グラフィック・デー
タが速やかに処理されるように、アレイ・プロセッサで
有利に用いることができる。
得る。従って、この方法は、３次元グラフィック・デー
タが速やかに処理されるように、アレイ・プロセッサで
有利に用いることができる。
本発明の好ましい実施例を図面に示して説明したが、こ
の実施例は例に過ぎないことを承知されたい。本発明の
範囲内で、当業者には種々の変更、改変及び置換が考え
られよう。従って、特許請求の範囲は、本発明の要旨の
範囲内に含まれるこのようなすべての変更を包括するも
のであることを承知されたい。
の実施例は例に過ぎないことを承知されたい。本発明の
範囲内で、当業者には種々の変更、改変及び置換が考え
られよう。従って、特許請求の範囲は、本発明の要旨の
範囲内に含まれるこのようなすべての変更を包括するも
のであることを承知されたい。
第１図はそれから面を抽出する断層写真データの配列の
一部を示す図である。 第２図は大きなキューブ及びそのキューブに隣接するデ
ータ点を示す斜視図である。 第３図はキューブの各々の頂点に関連する勾配の法線を
示す図である。 第４図は小キューブ及びそれらの小キューブの勾配の法
線を示す図である。 第５図は第４図とは異なる大きさの補間を用いた小分け
を示す図である。 第６図は分割キューブ方法を実施する従来の方法による
フローチャートである。 第７図は本発明の一実施例における処理ハードウェアの
ブロック図である。 第８図は本発明の好ましい実施例によるアレイ・プロセ
ッサのブロック図である。 第９図はベクトル操作を用いる方法のフローチャートで
ある。 符号の説明 39……汎用計算機、40……面発生器、41……表示プロセ
ッサ、42……電流変換マトリクス発生器、43……処理装
置、44……表示装置、45……指令プロセッサ。
一部を示す図である。 第２図は大きなキューブ及びそのキューブに隣接するデ
ータ点を示す斜視図である。 第３図はキューブの各々の頂点に関連する勾配の法線を
示す図である。 第４図は小キューブ及びそれらの小キューブの勾配の法
線を示す図である。 第５図は第４図とは異なる大きさの補間を用いた小分け
を示す図である。 第６図は分割キューブ方法を実施する従来の方法による
フローチャートである。 第７図は本発明の一実施例における処理ハードウェアの
ブロック図である。 第８図は本発明の好ましい実施例によるアレイ・プロセ
ッサのブロック図である。 第９図はベクトル操作を用いる方法のフローチャートで
ある。 符号の説明 39……汎用計算機、40……面発生器、41……表示プロセ
ッサ、42……電流変換マトリクス発生器、43……処理装
置、44……表示装置、45……指令プロセッサ。
フロントページの続き (72)発明者 エンリク・サントス アメリカ合衆国、マサチューセッツ州、ロ ウェル、ナンバー１、クラー・ストリー ト、22番
Claims (16)
- 【請求項１】ベクトル・プロセッサの３次元断層写真デ
ータから３次元の面の定義を発生する装置であって、 前記断層写真データの行又は列を示す１次元の軸線に沿
った複数のキューブ要素の頂点の値を所定の閾値と一度
に比較すると共に、該閾値よりも大きい少なくとも１つ
の頂点の値と、該閾値よりも小さい少なくとも１つの頂
点の値とを有している各々のキューブ要素にラベルを付
ける第１の比較手段と、 該第１の比較手段に接続されており、ラベルを付けられ
た所定数のキューブ要素を蓄積する待ち行列手段と、 該待ち行列手段に接続されており、ラベルを付けられた
各々のキューブ要素のうちの１つの小キューブに対し
て、小キューブの頂点の値と、小キューブの中心密度と
を一度に算出する小分け手段と、 該小分け手段に接続されており、前記小キューブの頂点
の値を前記閾値と比較すると共に、前記閾値よりも大き
い少なくとも１つの小キューブの頂点の値と、該閾値よ
りも小さい少なくとも１つの小キューブの頂点の値とを
有している各々の小キューブを表に作成して出力する第
２の比較手段とを備えており、 前記面を含んでいる前記表内のすべての小キューブの結
合が、前記面の定義を与えている３次元の面の定義を発
生する装置。 - 【請求項２】前記小分け手段は、前記断層写真データの
多項式補間を実行しており、 前記小分け手段は、 前記待ち行列手段に接続されており、前記キューブ要素
の頂点に対応する前記データから複数の多項式係数を計
算する多項式係数手段を含んでいる請求項１に記載の装
置。 - 【請求項３】前記小分け手段は、 前記多項式係数手段に接続されており、各々の小キュー
ブの中心における多項式補間値を評価すると共に前記多
項式の級数展開を用いて前記小キューブの頂点の値を決
定する計算手段を更に含んでいる請求項２に記載の装
置。 - 【請求項４】前記第１の比較手段と、前記待ち行列手段
とに接続されており、前記ラベルを付けられたキューブ
要素の頂点における勾配を計算すると共に該勾配を前記
待ち行列手段に供給する第１の勾配手段と、 前記待ち行列手段に接続されており、前記小キューブの
頂点の値により定められた小キューブに対応する勾配を
計算する第２の勾配手段とを更に含んでいる請求項１に
記載の装置。 - 【請求項５】前記所定数は、特定の最小値である請求項
１に記載の装置。 - 【請求項６】前記小分け手段は、前記待ち行列手段から
蓄積されている前記ラベルを付けられたキューブ要素を
受け取っていると共に、前記所定数により決定される処
理効率のレベルで小キューブの頂点の値を算出している
請求項４又は請求項５に記載の装置。 - 【請求項７】ベクトル・プロセッサの３次元断層写真デ
ータから３次元の面の定義を発生する方法であって、 前記データ内の複数のマーチング・キューブを処理する
工程であって、前記マーチング・キューブの頂点の値を
所定の閾値と一度に比較し、該閾値よりも大きい少なく
とも１つの頂点の値と、該閾値よりも小さい少なくとも
１つの頂点の値とを有している各々のキューブ要素にラ
ベルを付けることにより、前記面がそれぞれのマーチン
グ・キューブを通るかどうかを決定するように、前記デ
ータ内の複数のマーチング・キューブを処理する工程
と、 前記面を含んでいるマーチング・キューブを待ち行列に
並べる工程と、 前記待ち行列が所定数のマーチング・キューブを含むま
で、前記処理する工程と、前記並べる工程とを繰り返す
工程と、 前記待ち行列から前記マーチング・キューブを取り出す
工程と、 ラベルを付けられた各々のキューブ要素のうちの１つの
小キューブに対して、小キューブの頂点の値と、小キュ
ーブの中心密度とを一度に算出することにより小キュー
ブを形成するように、取り出された前記マーチング・キ
ューブを小分けする工程と、 それぞれの前記小キューブの頂点の値を前記所定の閾値
と一度に比較し、該閾値よりも大きい少なくとも１つの
小キューブの頂点の値と、該閾値よりも小さい少なくと
も１つの小キューブの頂点の値とを有している各々の小
キューブを表に作成して出力することにより、前記面が
それぞれの小キューブを通るかどうかを決定するよう
に、前記小キューブを処理する工程とを備えており、 前記面を含んでいる前記表内のすべての小キューブの結
合が、前記面の定義を与える３次元の面の定義を発生す
る方法。 - 【請求項８】前記所定数は、特定の最小値である請求項
７に記載の方法。 - 【請求項９】前記取り出す数は、前記最小値である請求
項８に記載の方法。 - 【請求項１０】前記並べる工程は、前記所定数のマーチ
ング・キューブを前記待ち行列に送って、結合されたデ
ータ要素のベクトルを形成する工程を含んでいる請求項
７又は請求項８に記載の方法。 - 【請求項１１】前記小分けする工程は、各々の前記小キ
ューブの中心における前記断層写真データの勾配を計算
する工程を含んでいる請求項７に記載の方法。 - 【請求項１２】前記小分けする工程と、前記小キューブ
を処理する工程とは、取り出された前記マーチング・キ
ューブ内のすべての小キューブが処理されるまで繰り返
して実行され、各々の繰り返しは、各々の前記取り出さ
れたマーチング・キューブからの１つの小キューブをそ
れぞれ用いる請求項７に記載の方法。 - 【請求項１３】前記小分けする工程は、前記断層写真デ
ータの多項式補間を用いる請求項７に記載の方法。 - 【請求項１４】前記小分けする工程は、 前記取り出されたマーチング・キューブの各々に対する
複数の多項式係数を計算する工程と、 各々の小キューブの中心における前記多項式の補間値を
評価する工程と、 級数展開を解いて、各々の小キューブの頂点の値を導出
する工程とを含んでいる請求項13に記載の方法。 - 【請求項１５】３次元断層写真データを供給するホスト
・コンピュータ手段と、 該コンピュータ手段に接続されており、前記データ内の
面の定義を求めるアレイ・プロセッサ手段であって、該
アレイ・プロセッサ手段は、マーチング・キューブ及び
小キューブを形成して、該キューブ及び小キューブを所
定の閾値と比較するバッチ動作を実行するように構成さ
れており、 前記断層写真データの行又は列を示す１次元の軸線に沿
った複数のキューブ要素の頂点の値を所定の閾値と一度
に比較すると共に、該閾値よりも大きい少なくとも１つ
の頂点の値と、該閾値よりも小さい少なくとも１つの頂
点の値とを有している各々のキューブ要素にラベルを付
ける第１の比較手段と、 該第１の比較手段に接続されており、ラベルを付けられ
た所定数のキューブ要素を蓄積する待ち行列手段と、 該待ち行列手段に接続されており、ラベルを付けられた
各々のキューブ要素のうちの１つの小キューブに対し
て、小キューブの頂点の値と、小キューブの中心密度と
を一度に算出する小分け手段と、 該小分け手段に接続されており、前記小キューブの頂点
の値を前記閾値と比較すると共に、前記閾値よりも大き
く少なくとも１つの小キューブの頂点の値と、該閾値よ
りも小さい少なくとも１つの小キューブの頂点の値とを
有している各々の小キューブを表に作成して出力する第
２の比較手段とを含んでおり、 前記面を含んでいる前記表内のすべての小キューブの結
合が、前記面の定義を与えている、アレイ・プロセッサ
手段と、 該アレイ・プロセッサ手段に接続されており、前記面の
定義を受け取って像を合成する処理手段と、 該処理手段に接続されており、前記像を表示する表示手
段とを備えたグラフィック表示システム。 - 【請求項１６】前記アレイ・プロセッサ手段は、マーチ
ング・キューブ及び小キューブをそれぞれ表している最
小の大きさのデータ要素のバッチを形成して、それぞれ
の該データ要素のバッチを、前記最小の大きさにより決
定される処理効率のレベルで前記所定の閾値と比較する
動作を実行するように構成されている請求項15に記載の
システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/125,426 US4868748A (en) | 1987-11-25 | 1987-11-25 | Rapid processing of three-dimensional graphical objects from tomographic data |
| US125426 | 1987-11-25 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH021082A JPH021082A (ja) | 1990-01-05 |
| JPH0697465B2 true JPH0697465B2 (ja) | 1994-11-30 |
Family
ID=22419672
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63289055A Expired - Lifetime JPH0697465B2 (ja) | 1987-11-25 | 1988-11-17 | ３次元の面の定義を発生する装置及び方法、並びにグラフィック表示システム |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US4868748A (ja) |
| EP (1) | EP0318293B1 (ja) |
| JP (1) | JPH0697465B2 (ja) |
| DE (1) | DE3854960T2 (ja) |
| IL (1) | IL87964A (ja) |
Families Citing this family (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4984157A (en) * | 1988-09-21 | 1991-01-08 | General Electric Company | System and method for displaying oblique planar cross sections of a solid body using tri-linear interpolation to determine pixel position dataes |
| US5150427A (en) * | 1989-09-29 | 1992-09-22 | General Electric Company | Three dimensional disarticulation |
| GB2246689A (en) * | 1990-08-04 | 1992-02-05 | David John Winter | Creating a 3-D image from a plurality of cross-sections |
| US5644689A (en) * | 1992-01-13 | 1997-07-01 | Hitachi, Ltd. | Arbitrary viewpoint three-dimensional imaging method using compressed voxel data constructed by a directed search of voxel data representing an image of an object and an arbitrary viewpoint |
| US5396890A (en) * | 1993-09-30 | 1995-03-14 | Siemens Medical Systems, Inc. | Three-dimensional scan converter for ultrasound imaging |
| KR100329338B1 (ko) * | 1994-12-02 | 2002-07-18 | 피터 엔. 데트킨 | 복합피연산자의팩연산을수행하는마이크로프로세서 |
| US6175655B1 (en) | 1996-09-19 | 2001-01-16 | Integrated Medical Systems, Inc. | Medical imaging system for displaying, manipulating and analyzing three-dimensional images |
| US6246784B1 (en) | 1997-08-19 | 2001-06-12 | The United States Of America As Represented By The Department Of Health And Human Services | Method for segmenting medical images and detecting surface anomalies in anatomical structures |
| US6697539B1 (en) * | 2000-03-31 | 2004-02-24 | Sharp Laboratories Of America, Inc. | Image scaling by exact 2D implicit polynomials |
| WO2002089066A1 (en) * | 2001-04-26 | 2002-11-07 | Koninklijke Philips Electronics N.V. | Approximating an implicit surface |
| JP2003022448A (ja) * | 2001-07-06 | 2003-01-24 | Canon Inc | 階層的格子生成方法、装置およびプログラム |
| DE10149556A1 (de) * | 2001-10-08 | 2003-04-24 | Siemens Ag | Verfahren zur Erzeugung eines zweidimensionalen Bildes aus einem 3D-Datensatz eines Tomographie-Geräts und medizinisches Tomographie-Gerät |
| US7260250B2 (en) * | 2002-09-30 | 2007-08-21 | The United States Of America As Represented By The Secretary Of The Department Of Health And Human Services | Computer-aided classification of anomalies in anatomical structures |
| JP4744072B2 (ja) * | 2003-10-31 | 2011-08-10 | Ｊｕｋｉ株式会社 | ミシン |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4653013A (en) * | 1984-11-19 | 1987-03-24 | General Electric Company | Altering spatial characteristics of a digital image |
| US4710876A (en) * | 1985-06-05 | 1987-12-01 | General Electric Company | System and method for the display of surface structures contained within the interior region of a solid body |
| US4719585A (en) * | 1985-08-28 | 1988-01-12 | General Electric Company | Dividing cubes system and method for the display of surface structures contained within the interior region of a solid body |
| US4751643A (en) * | 1986-08-04 | 1988-06-14 | General Electric Company | Method and apparatus for determining connected substructures within a body |
-
1987
- 1987-11-25 US US07/125,426 patent/US4868748A/en not_active Expired - Fee Related
-
1988
- 1988-10-07 IL IL87964A patent/IL87964A/xx not_active IP Right Cessation
- 1988-11-17 JP JP63289055A patent/JPH0697465B2/ja not_active Expired - Lifetime
- 1988-11-24 EP EP88311145A patent/EP0318293B1/en not_active Expired - Lifetime
- 1988-11-24 DE DE3854960T patent/DE3854960T2/de not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH021082A (ja) | 1990-01-05 |
| DE3854960D1 (de) | 1996-03-14 |
| US4868748A (en) | 1989-09-19 |
| IL87964A (en) | 1992-05-25 |
| EP0318293A3 (en) | 1991-02-06 |
| DE3854960T2 (de) | 1996-09-12 |
| IL87964A0 (en) | 1989-03-31 |
| EP0318293A2 (en) | 1989-05-31 |
| EP0318293B1 (en) | 1996-01-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2744490B2 (ja) | 物体内部構造表面の２次元像を表示する装置と方法 | |
| US5166876A (en) | System and method for detecting internal structures contained within the interior region of a solid object | |
| JPH0731739B2 (ja) | ２次元断層撮影スライスの中の面を抽出する方法と装置 | |
| US4885688A (en) | Minimization of directed points generated in three-dimensional dividing cubes method | |
| JP2885842B2 (ja) | 固体内部領域の切断平面を表示する装置と方法 | |
| US4989142A (en) | Three-dimensional images obtained from tomographic slices with gantry tilt | |
| US7242401B2 (en) | System and method for fast volume rendering | |
| US5170347A (en) | System to reformat images for three-dimensional display using unique spatial encoding and non-planar bisectioning | |
| EP0638875B1 (en) | A 3-dimensional animation generating apparatus and a method for generating a 3-dimensional animation | |
| US4953087A (en) | Three-dimensional images obtained from tomographic data having unequally spaced slices | |
| JPH0697465B2 (ja) | ３次元の面の定義を発生する装置及び方法、並びにグラフィック表示システム | |
| US5923789A (en) | Band limited interpolation and projection of spatial 3-D images | |
| JP2000149047A (ja) | ボリュ―ムレンダリングプロセッサ | |
| Jense | Voxel-based methods for CAD | |
| US5900880A (en) | 3-D surfaces generated from a list of cubic elements | |
| US6891963B1 (en) | Image display | |
| EP1775685B1 (en) | Information processing device and program | |
| US6522324B1 (en) | Deriving an iso-surface in a multi-dimensional data field | |
| JP4242527B2 (ja) | 立体測定データにおける表面を表示する方法及びシステム | |
| US6191789B1 (en) | Ray casting method using hardware | |
| EP0373854B1 (en) | Apparatus and method for detecting internal structures contained within the interior region of a solid object | |
| EP0318291B1 (en) | Apparatus and method for generating images from tomographic data | |
| US5821942A (en) | Ray tracing through an ordered array | |
| JP2519779B2 (ja) | ３次元画像表示装置 | |
| JP2998577B2 (ja) | 投影像作成装置 |