JP6942007B2 - 画像処理装置、及びプログラム - Google Patents

Description

本発明は、医療用画像等を処理する画像処理装置、及びプログラムに関する。

近年、例えば医療用の診断装置（ＣＴ装置等）から得られた画像データを処理して、血管等の組織を三次元的なポリゴンモデルで表現し、三次元の画像として可視化する技術が広く知られている。また、このようなモデル化、可視化のための処理としては、例えば医療分野では、マーチングキューブ法と呼ばれる画像処理が用いられるのが一般的となっている（例えば特許文献１）。

特開２０１２−２４５３７４号公報

しかしながら、上記従来のマーチングキューブを用いた画像処理では、可視化は可能であるが、手術時のシミュレーションなどを行うべく組織のポリゴンモデルの変形操作を行うときに、次のような問題が生じる。

すなわち、通常のマーチングキューブ法では、仮想空間に四面体のセルをマトリクス状に配列し、この仮想空間内に、複数の画像データに基づいて数値（例えば画像データの輝度の値）を設定する。そして、上記各セルについて、所定の値の面（等値面）が含まれるか否かを決定し、等値面が含まれるとされたセルについては、等値面を特定する情報を生成する。

ここで、互いに隣接する一対のセルには同じ位置に配される辺（共通辺と呼ぶ）が含まれる。具体的には図１０に例示するように、互いに隣接するセルＡ，Ｂにおいては、セルＡの底面を構成する辺Ａ１からＡ４と、セルＢの上面を構成する辺Ｂ５からＢ８とが共通辺として含まれる。しかしながら、上記通常のマーチングキューブ法では、各セルについて独立して等値面の設定を行うため、例えばセルＡについて設定した等値面が辺Ａ１上の点Ａｘを横切ると判断されたときには、当該等値面は、セルＢの、辺Ａ１に対する共通辺である辺Ｂ５上の点Ｂｘも同様に横切ることとなる。ここで、点Ａｘと点Ｂｘとは、上記仮想空間内の同じ点であるにも関わらず、マーチングキューブ法では、セルごとに処理を行ってしまうので、互いに異なる点として識別されて処理に供される。

このことは、可視化のみに用いる場合には通常、問題とならないが、このポリゴンモデルに対して頂点の編集操作、例えば変形操作を行う場合、点Ａｘの位置を変化させるときには、対応する点Ｂｘを探索して、当該点Ｂｘについても点Ａｘと同じように位置を変化させなければならない。

このため、変形操作の処理負荷が大きくなり、リアルタイムに頂点の編集操作を行う等の処理が困難となる場合があった。また、頂点の編集操作に先立って同一座標にある頂点を統合する処理を行う場合も、その処理負荷が大きくなっていた。

本発明は上記実情に鑑みて為されたもので、頂点の編集操作等の画像処理負荷を軽減できる画像処理装置、及びプログラムを提供することを、その目的の一つとする。

上記従来例の問題点を解決する本発明は、仮想的なポリゴンモデルを形成する仮想空間を、所定多角形状の仮想的なセルに分割して、ポリゴンモデルを形成する画像処理装置であって、処理対象となる前記仮想空間内に分布する値データを受け入れる手段と、前記値データに基づいて、前記セルの多角形状の各頂点の位置ごとの値を決定する手段と、前記各セルの辺のうち、互いにその位置が重なり合わない辺を辺要素として、各辺要素を識別する辺識別情報を設定し、各辺要素の両端の頂点の位置に対応する前記値に基づいて、セル内を通過するポリゴンの頂点が位置する辺要素の辺識別情報を特定する手段と、前記特定した辺識別情報を用いて前記ポリゴンモデルを表す情報を生成するポリゴンモデル生成手段と、を含み、当該辺識別情報を用いて表されるポリゴンモデルの情報が、可視化及び変形操作を含む所定処理に供されることとしたものである。

本発明によると、変形操作等の画像処理負荷を軽減できる。

本発明の実施の形態に係る画像処理装置の構成例を表すブロック図である。 本発明の実施の形態に係る画像処理装置の一例を表す機能ブロック図である。 本発明の実施の形態に係る画像処理装置が設定するセル、及び辺要素の例を表す説明図である。 本発明の実施の形態に係る画像処理装置による仮頂点識別情報の設定例を表す説明図である。 本発明の実施の形態に係る画像処理装置の動作例を表すフローチャート図である。 本発明の実施の形態に係る画像処理装置の動作例を表す説明図である。 本発明の実施の形態に係る画像処理装置の動作例を表すもう一つの説明図である。 本発明の実施の形態に係る画像処理装置による処理と従来例の処理との対比を表す説明図である。 本発明の実施の形態に係る画像処理装置の効果を表す説明図である。 従来の処理における頂点の設定方法を表す説明図である。

本発明の実施の形態について図面を参照しながら説明する。本発明の実施の形態に係る画像処理装置１は、図１に例示するように、制御部１１、記憶部１２、操作部１３、表示部１４、及びインタフェース部１５を含んで構成される。

制御部１１は、ＣＰＵ等のプログラム制御デバイスであり、記憶部１２に格納されたプログラムに従って動作する。本実施の形態において、この制御部１１は、仮想的なポリゴンモデルを形成する仮想空間を、所定多角形状の仮想的なセルに分割して、ポリゴンモデルを形成する処理と、当該ポリゴンモデルの情報を用いた、可視化及び頂点の編集操作（変形操作等）の所定処理とを実行する。

ここでポリゴンモデルを形成する処理では、この制御部１１は、処理対象となる仮想空間内に分布する値データを受け入れる。この値のデータは例えばＣＴやＭＲＩ等の医療機器により得られる画像データ等である。また制御部１１は、この値データに基づいて、上記セルの多角形状の各頂点の位置ごとの値を特定し、各セルの辺のうち、互いにその位置が重なり合わない辺を辺要素として、各辺要素を識別する辺識別情報を設定し、各辺要素の両端の頂点の位置に対応する値に基づいて、ポリゴンが通過する辺要素（このポリゴンと辺要素との交点はポリゴンの頂点となる）の辺識別情報を特定する。制御部１１は、そして、特定した辺識別情報を用いてポリゴンモデルを表す情報を生成する。この制御部１１の具体的な処理の内容については、後に述べる。

記憶部１２は、制御部１１により実行されるプログラムを格納している。このプログラムは、コンピュータ可読、かつ非一時的な記録媒体に格納されて提供され、この記憶部１２に格納されたものであってもよい。また本実施の形態において、この記憶部１２は、制御部１１のワークメモリとしても動作する。

操作部１３は、キーボードやマウス等であり、利用者の指示入力を受け入れて、制御部１１に対して当該指示入力の内容を出力する。表示部１４は、ディスプレイ等であり、制御部１１から入力される指示に従って情報を表示出力する。

インタフェース部１５は、ＵＳＢ（Universal Serial Bus）等のインタフェースであり、外部の装置からデータを受け入れて制御部１１に出力する。またこのインタフェース部１５は、制御部１１から入力される指示に従って、外部の装置に対して指示された情報を出力してもよい。

ここで本実施の形態の制御部１１の動作について説明する。本実施の形態の制御部１１は、記憶部１２に格納されたプログラムを実行することにより、機能的には、図２に例示するように、ポリゴンモデル生成部２０と、描画処理部３０とを含んで構成されている。ここでポリゴンモデル生成部２０は、データ受入部２１と、セル設定部２２と、辺要素設定部２３と、頂点仮識別情報取得部２４と、ポリゴンモデル設定部２５とを含んで構成される。

ポリゴンモデル生成部２０のデータ受入部２１は、本実施の形態の一例では、ＣＴやＭＲＩ等の医療機器により得られる画像データを受け入れる。これらの画像データは一般的に複数枚の画像を含み、人体内の組織の関する三次元的な形状を表現可能なものである。このようにＣＴやＭＲＩ等により得られた画像データから三次元的な空間内の各点での画素値（処理対象となる仮想空間内に分布する値データ）を得る方法は、広く知られているので、ここでの詳しい説明は省略する。

セル設定部２２は、画素値が設定された空間（処理対象となる仮想空間）内に、所定多角形状の仮想的なセルを設定する。具体的にここでは仮想空間は大きさがＬ×Ｌ×Ｌの正六面体状の空間とし、当該正六面体のいずれかの頂点を原点として、当該原点を含む正六面体の互いに直交する３つの辺の方向をそれぞれＸ，Ｙ，Ｚ軸方向としてＸＹＺ直交座標系を設定するものとする。セル設定部２２は、例えばセルの形状を大きさがｌ×ｌ×ｌ（ｌはＬの約数であるものとする）の正六面体とし、配列方向をＸ，Ｙ，Ｚ軸の各軸方向に合わせてセルを配列する。以下の説明では、原点の位置にあるセルを（０，０，０）と表し、このセルのＸ軸方向の法線を有する面と面を共有する隣接するセルを（１，０，０）などと表すものとする。つまりこの原点の位置にあるセルからＸ軸方向にξ番目、Ｙ軸方向にη番目、Ｚ軸方向にζ番目にあるセルを（ξ，η，ζ）と表す。また、図では手前側左下の点を原点として鉛直上方をＺ軸正の方向、右方向をＸ軸正の方向、奥側の方向をＹ軸正の方向とする。

またセル設定部２２は、各セルに、それぞれ固有のセル識別情報を設定しておく。具体的には、このセルは立方体（正六面体）の形状を有し、セル設定部２２は、当該立方体形状のセルを、仮想空間内に、隙間なく三次元的なマトリクス状に配列する。またこのセル設定部２２は、データ受入部２１が受け入れた値データに基づいて、セルの各頂点の位置に対応する値を決定して、当該値を記録する。

辺要素設定部２３は、セルの三次元形状の辺のうち、互いにその位置が重なり合わない辺を辺要素として、各辺要素を識別する辺識別情報を設定する。この辺要素設定部２３は、具体的にセルを立方体としている場合は、図３に例示するように、立方体のセルに属する辺０からXIの辺識別情報（ここでの説明では符号と区別するため、便宜的に０以外の数字をローマ数字で示すが、制御部１１の処理上はアラビア数字などで管理してよい）、所定の頂点（例えばセルの立方体の頂点のうち、底面（Ｚ軸方向に法線を有する面のうち原点に近い側の面）の、Ｘ，Ｙ座標の値が最も小さくなる点（図３のＰ））を共有する互いに直交する三辺（図３の辺０，III，VIII）を辺要素とする。これにより図３のセルＡの辺IXは右側（Ｘ軸正の側）に隣接するセルＢの辺要素VIIIとして表現され、また、セルＡの辺IVは、上側（Ｚ軸正の側）に隣接するセルＣの辺要素０として表現されることとなる。なお、ここでは、底面のＸ軸に平行な辺のうち、原点に近い側の辺から順に上方（Ｚ軸正の側）から見て反時計回りに辺０，I，II，III、上面（Ｚ軸方向に法線を有する面のうち原点から遠い側の面）内のＸ軸に平行な辺のうち、原点に近い側の辺から順に上方（Ｚ軸正の側）から見て反時計回りに辺IV，V，VI，VIIとし、点ＰからＺ軸に平行な辺を辺VIII、手前側の面（辺０，IV，VIIIを有する面）のＸ軸正の側にあるＺ軸に平行な辺を辺IX、右側側面（辺I，V，IXを有する面）のＹ軸正の側にあるＺ軸に平行な辺を辺X、これら辺０からXとは異なる六面体の最後の一辺を辺XIとしている（図３）。

また、処理対象となる仮想空間内でＸ軸正の側の端、Ｙ軸正の側の端、Ｚ軸正の側の端にあるセルの辺I,II,IV,V,VI,VII,IX,X,XIは、それぞれ存在しないものとして扱ってもよい。

頂点仮識別情報取得部２４は、ポリゴンの頂点が位置する辺要素の辺識別情報を特定する。具体的に頂点仮識別情報取得部２４は、セルの各頂点に対応する値と、予め指定された値（ポリゴンの面に相当する位置での値）とを比較し、各セルの各頂点がポリゴンモデルで規定される立体の内側にあるか外側にあるかを判断し、セルの頂点ごとに、当該判断の結果を記録する。

そしてこの頂点仮識別情報取得部２４は、各セルを順次注目セルとして選択し、選択している注目セルについてセルの頂点がポリゴンで表される立体の内側にあるか外側にあるかを表す２５６通りのパターン（実質的には対称性のため１５通りのパターン）のいずれのパターンに相当するかを判断し、当該判断したパターンに対応する、ポリゴン（例えば三角形）と、当該ポリゴンと注目セルの辺との交差する点とを特定する。この方法は、従来のマーチングキューブ法における処理と同様であるので、ここでの詳しい説明を省略する。この段階で、頂点仮識別情報取得部２４は、描画するべきポリゴンを特定し、各ポリゴンに固有のポリゴン識別情報を発行し、当該発行したポリゴン識別情報を記録する。

本実施の形態において頂点仮識別情報取得部２４は、ここで特定されたポリゴンごとに、ポリゴンと注目セルの辺要素との交差する点（注目セルの辺要素上にあるポリゴンの頂点）を識別する、仮識別情報（注目セルの辺要素上にあるポリゴンの頂点を仮に識別する情報）を発行する。このとき本実施の形態において特徴的なことの一つは、このポリゴンの頂点を仮に識別する仮識別情報として従来のようにセルごとの辺識別情報を用いることに代えて、注目セルまたはそれに隣接するセルの辺要素を特定する辺識別情報を用いることである。ここで辺識別要素は当該辺要素が属するセルを特定するセル識別情報と辺識別情報とを含む。

すなわち、図４に例示するように、具体的に注目セルαに対し、図中でその上方に隣接するセルβと、図中で右側に隣接するセルγと、このセルγの上方に隣接するセルδとが配列されているとき、注目セルαの図４に示す２つの頂点Ｐ，Ｑが立体の内部にあるものと判断され、他の頂点が立体の外部にあるものと判断されたとする。このときには、２つのポリゴン（三角形）Ａ，Ｂがこの注目セル内に存在するポリゴンとなるが、本実施の形態では、これらの三角形の頂点（セルの辺との交点）を表す仮識別情報として、セル識別情報と、セルごとの辺要素を識別する辺識別情報とを用いるものとする。

従って図４の例の場合、頂点仮識別情報取得部２４は、ポリゴンＡについては、セルαの辺０，III，VIIIに各頂点があるものとして記録する。また、頂点仮識別情報取得部２４は、ポリゴンＢについてはセルβの辺０、セルγの辺VIII、セルδの辺IIIに各頂点があるものとして記録する。また頂点仮識別情報取得部２４は、隣接するセルγを注目セルとして処理をした場合に、ポリゴンＡ，Ｂとは異なる別のポリゴンＣを、このセルγ内に特定することとなるが、このポリゴンＣの頂点の一つは、セルγの辺VIIIにあるものとして記録されることとなる。すなわち、ポリゴンＢの頂点の一つと、ポリゴンＣの頂点の一つとが同じ仮識別情報（セルγの辺VIIIにあるものとする情報）で特定されることとなる。

このように、本実施の形態では、各ポリゴンについて、共通する頂点については、同じ仮識別情報が付与されるよう、まずはセル識別情報と辺要素を識別する辺識別情報とを用いて抽象的に（実際のレンダリングにおいては各頂点は互いに異なる固有の番号等で識別されるので、ここでは「抽象的」と表現している）表される。すなわち、ここで特定される仮識別情報は、いわば抽象識別子として機能する。

ポリゴンモデル設定部２５は、頂点仮識別情報取得部２４がポリゴンごとに特定した辺識別情報を用いて、ポリゴンモデルを表す情報を生成する。すなわちこのポリゴンモデル設定部２５は、頂点仮識別情報取得部２４が特定した複数のポリゴンについて、各ポリゴンの各頂点を表す仮識別情報（この情報にはセル識別情報とセルごとの辺要素を識別する辺識別情報とを含む）を含むポリゴンモデルの情報を生成する。

本実施の形態においては、ここで生成したポリゴンモデルの情報を用いて、可視化及び変形操作を含む所定処理を実行する。具体的に制御部１１は、まず、ポリゴンモデルの情報に含まれる、各ポリゴンの仮識別情報を、実際の描画に用いる頂点識別情報（頂点の位置を表す情報、いわば実識別情報）へ変換する。

この変換処理は、仮識別情報ごとに固有の番号や文字列等の識別情報を、頂点識別情報として発行することで行うことができる。このとき描画等の処理のためには、ポリゴンとその頂点を表す頂点識別情報とを関連付ける必要がある。そこで本実施の形態では、制御部１１は、次のようにしてこの関連付け処理を達成する。

すなわち制御部１１は、ポリゴンモデル設定部２５の処理として、ヒストグラムピラミッド（Christopher Dyken, et.al., High-speed Marching Cubes using Histogram Pyramids, Computer Graphics Forum, Vol.27, issue 8, December 2008, pages 2028-2039）と同様の方法を用いて、仮識別情報を頂点識別情報へ変換し、さらに変換により得た頂点識別情報をヒストグラムピラミッドの方法を用いて、ポリゴン識別情報に関連付ける。

具体的に、制御部１１は、ヒストグラムピラミッドと同様の方法により、仮識別情報を頂点識別情報へ変換する。すなわち制御部１１は、セルの各々を注目セルとして順次選択し、選択した注目セルの辺要素を所定の選択順（例えばセルが正六面体であれば、辺０，辺III，辺VIIIの順）に、当該辺要素上のポリゴンの頂点の数をカウントしつつ累算する。そして制御部１１は、各辺要素について当該カウントして得られた値の和（累算値）を、注目セルについてのカウント値（ベースレベルカウント値）として記録する。

さらに制御部１１は、予め定められた位置から順に、互いに隣接する複数のセル（例えば互いに隣接するｎ×ｎ×ｎ個のセル）のグループを複数設定し、この設定したグループを第１段ブロックとして、当該第１段ブロックの各々について、第１段ブロックに属するセル内の辺要素上のポリゴンの頂点の数の和、つまり、第１段ブロックに属するセルについてのベースレベルカウント値の和を、第１段ブロックについてのカウント値（レベル１カウント値）として記録する。

ここで予め定めた位置は、例えば、仮想空間の原点にあるセル（０，０，０）とすればよい。またグループの形成順は、原点のセルを含むｎ×ｎ×ｎ個のセルをグループとし、次に、このグループのＸ軸方向に隣接するセルを含むｎ×ｎ×ｎ個のセルをグループとし…と選択してゆき、Ｘ軸方向に隣接するセルがなくなったら、Ｘ＝０に戻って、既に形成したグループにＹ軸方向に隣接するセルを含むｎ×ｎ×ｎ個のセルをグループとして、再度このグループのＸ軸方向に隣接するセルを含むｎ×ｎ×ｎ個のセルをグループとし…と選択していく。この処理を繰り返して、Ｙ軸方向に隣接するセルがなくなったら、Ｘ＝０、Ｙ＝０に戻って、既に形成したグループにＺ軸方向に隣接するセルを含むｎ×ｎ×ｎ個のセルをグループとして、Ｘ軸方向に移動しつつグループを形成する処理から繰り返していく（いわば、三次元的なスキャンライン順にグループ化を行えばよい）。この処理により、各セルが順番にグループに含められる。

制御部１１は、以下、上記の予め定められた位置から上記の形成順に、互いに隣接する複数の第（ｉ−１）段（ｉは、ｉ＞１なる整数）ブロックのグループ（例えば互いに隣接する２×２×２個の第（ｉ−１）段ブロックのグループ）を設定する。そして制御部１１は、この設定したグループを第ｉ段ブロックとして、当該第ｉ段ブロック内に属するセル内の辺要素上のポリゴンの頂点の数の和を、第ｉ段ブロックについてのカウント値（レベルｉカウント値）として記録する処理を、ｉ＝２，３…とインクリメントしつつ実行し、ブロックの数が所定の数未満となるまで（例えばグループ化不能となるまで、一例としては２×２×２未満、あるいは「１」となるまで）繰り返す。この段階を以下、便宜的に最終レベルと呼ぶ。ここでのグループの形成順も、セルのグループの形成順と同様とする。

制御部１１は、さらに、ここで記録されたブロック単位でのブロック内に属するセル内の辺要素上のポリゴンの頂点の数の和、または記録されたセル単位でのセル内の辺要素上のポリゴンの頂点の数の和の値を参照して、ポリゴンの頂点の仮識別情報を、実際の描画等の処理に用いる頂点識別情報に変換する。

すなわち制御部１１は、ポリゴンの頂点の仮識別情報ごとに、次の処理を行う。制御部１１は、変換の対象となる仮識別情報であるセル識別情報と辺要素識別情報とを取得し、当該取得したセル識別情報で識別されるセルが含まれる、上記の処理で生成した最終レベルのブロック単位でのブロックを特定する。

制御部１１は、当該特定した最終レベル（第Ｎ段）のブロックを注目ブロックとして、注目ブロックに含まれる第Ｎ−１段ブロックを特定する。制御部１１は、特定した第Ｎ−ｋ段ブロック（ｋ＝０，１，…，Ｎ−１なる整数）のうち、取得したセル識別情報で識別されるセルが含まれるブロックを特定する。制御部１１は第Ｎ−ｋ段での注目ブロックに含まれる第Ｎ−ｋ−１段ブロックを、形成順に選択しつつ、取得したセル識別情報で識別されるセルが含まれるブロックが選択されるまでに選択したブロック（取得したセル識別情報で識別されるセルが含まれるブロックそのものは除く）に割り当てられた、ポリゴンの頂点の数の和の値を累算する。そしてこの累算値を第Ｎ−ｋ−１段ブロックの予備値として記録しておく。制御部１１は、取得したセル識別情報で識別されるセルが含まれるブロックを、第Ｎ−ｋ−１段ブロックの注目ブロックとする。そして制御部１１は、この第Ｎ−ｋ−１段ブロックの注目ブロックに含まれる第Ｎ−ｋ−２段ブロック（ｋ＜Ｎ−１のとき）を特定する。制御部１１は、ｋ＝Ｎ−１となるまで、ｋを「１」ずつインクリメントしつつこの処理を繰り返す。

制御部１１は、ｋ＝Ｎ−１となると（取得したセル識別情報で識別されるセルを含む第１段グループが見いだされると）、当該見いだした第１段グループ内のセルを、上記形成順に選択しつつ、取得したセル識別情報で識別されるセルが選択されるまでに選択したセル（取得したセル識別情報で識別されるセルそのものは除く）についての、ポリゴンの頂点の数の和の値を累算する。そしてこの累算値を第１段ブロックの予備値として記録する。

さらに制御部１１は、取得したセル識別情報で識別されるセル内の辺要素を、上記選択順に選択しつつ、セル識別情報とともに取得した辺要素識別情報で識別される辺要素が選択されるまでに選択した辺要素上のポリゴンの頂点の数の和の値を累算する。そしてこの累算値を辺要素予備値として記録する。

制御部１１は、この処理で記録した辺要素予備値、及び第ｉ段ブロックの予備値（ｉ＝１，２…Ｎ−１）の総和が表す値を、取得したセル識別情報と辺要素識別情報で特定される仮識別情報に対応する頂点識別情報として出力する。これにより、仮識別情報のそれぞれが、連番の頂点識別情報に関連付けられる。

制御部１１は、さらに記録しているポリゴン識別情報で識別されるポリゴンごとに、当該ポリゴンの各頂点の頂点識別情報を取得する。この処理は、従来通りのヒストグラムピラミッドの方法により実行できるので、ここでの詳しい説明は省略する。

制御部１１の描画処理部３０は、このようにして生成したポリゴンモデルの情報、及びポリゴン識別情報と当該ポリゴン識別情報で識別されるポリゴンの各頂点を識別する頂点識別情報との組を用いて、各ポリゴンの描画を行う。この描画処理部３０における処理は、既に各ポリゴンの各頂点と頂点識別情報との組が得られているので、従来と同様の方法により実行できる。本実施の形態において特徴的なことの一つは、この段階で設定されている頂点識別情報が、そもそも重複を排除して規定されたセル識別情報と辺要素識別情報との組に対して固有に割り当てたものであるので、仮想空間内の同じ点にある頂点については同じ頂点識別情報となっていることである。

従って、制御部１１がポリゴンを変形する処理を実行する場合（頂点の移動や頂点の削除等を行う場合）にも、所定の頂点識別情報で識別される頂点を変形し、当該頂点識別情報により識別される頂点を有するポリゴンの描画を行えばよいので、移動や削除の対象となった頂点ともともと同じ位置にあった別の識別子で識別される頂点を探索するといった処理が不要となり、処理の効率を向上でき、リアルタイムの変形や描画の処理が容易になる。

さらに、本実施の形態の制御部１１の処理では、仮識別情報の設定の処理はセルごとに、他のセルでの実行結果を参照せずに実行でき、また、仮識別情報から頂点識別情報への変換の処理も、仮識別情報ごとに、他の仮識別情報に係る処理結果を参照せずに実行できる。またポリゴン識別情報と頂点識別情報との関連付けの処理も、ヒストグラムピラミッドの処理を利用するので、ポリゴンごとに独立して（他のポリゴンに係る処理を参照せずに）実行でき、並列化が容易となっている。さらに仮識別情報の決定や頂点識別情報への変換の処理においてループの処理はあるものの、条件分岐によりまったく異なる処理を実行する必要がなく、処理負荷が軽減されている。

本実施の形態の画像処理装置は、以上の構成を備えており、次のように動作する。なお、以下では説明のため、仮想空間を三次元の空間ではなく、二次元的な空間であるものとする。なお、このように次元を異ならせても一般性が失われることはない。

この例では、画像処理装置１は、図５に示すように処理対象となる仮想空間内に分布する値データを受け入れる（Ｓ１）。この値のデータは例えばＣＴやＭＲＩ等の医療機器により得られる画像データ等である。画像処理装置１は、この値データに基づいて、仮想空間内に配列したセルの多角形状の各頂点の位置ごとの値を特定する（Ｓ２）。

画像処理装置１は、各セルの辺のうち、互いにその位置が重なり合わない辺を辺要素として、各辺要素を識別する辺識別情報を設定する（図６）。ここでは仮想空間は二次元の空間としているので、セルは例えば正方形となる。そこで各セルの辺要素として、正方形の左側の辺（辺IIIとする）と下側の辺（辺０とする）とを用いる。図６では、左右方向の軸をＸ軸（右方向を正とする）、上下方向の軸をＹ軸（下方を正とする）としている。各セルのセル識別情報は、左上隅を原点（０，０）として、この原点に頂点を有するセル（左上隅にあるセル）のセル識別情報を「０」として、この原点に頂点を有するセルからＸ軸方向にｘ番目、Ｙ軸方向にｙ番目に配置されているセル（（ｘ，ｙ）の位置にあるセル）のセル識別情報を（ｘmax×ｙ＋ｘ＋１）なる整数で表すものとする。なお、ｘmaxは、Ｘ軸方向に配列されたセルの数（図６では「８」）である。

画像処理装置１は、各セルの各辺要素の両端の頂点の位置に対応する値に基づいて、ポリゴンが通過する辺要素の辺識別情報を特定する（Ｓ３）。すなわち画像処理装置１は、マーチングキューブ法の処理により、処理Ｓ２にて特定した、セルの各頂点に対応する値と、予め指定された値（ポリゴンの面に相当する位置での値）とを比較し、各セルの各頂点が三次元ポリゴンモデルで規定される立体の内側にあるか外側にあるかを判断し、セルの頂点ごとに、当該判断の結果を記録する。そして画像処理装置１は、各セルを順次注目セルとして選択し、選択している注目セルについてセルの頂点がポリゴンで表される立体の内側にあるか外側にあるかを表す１５通りのパターンのいずれのパターンに相当するかを判断し、当該判断したパターンに対応する、ポリゴン（例えば三角形）を特定するとともに、当該ポリゴンと注目セルの辺との交差する点（ポリゴンの頂点）を特定する。

また画像処理装置１は、各ポリゴンに固有のポリゴン識別情報を発行し、当該発行したポリゴン識別情報を記録する。

画像処理装置１は、また、特定したポリゴンと注目セルの辺要素との交差する点（注目セルの辺要素上にあるポリゴンの頂点）を識別する、仮識別情報（注目セルの辺要素上にあるポリゴンの頂点を仮に識別する情報）を発行する（Ｓ４）。図６に例示した二次元の例を用いて、この仮識別情報について説明すると、セル識別情報「９」で識別されるセル（（１，１）の位置にあるセル）では等値面は辺０と辺Iとを通過しているが、各セルの辺要素を用いてこれらの各点を表すと、
セル識別情報「９」の辺０
セル識別情報「１０」（（２，１）の位置にあるセル）の辺III
ということとなり、画像処理装置１は、仮識別情報として、｛セル識別情報「９」，辺０｝、｛セル識別情報「１０」，辺III｝の２つを発行して記録する。

また、セル識別情報「１０」で識別されるセルに注目したときには、画像処理装置１は、仮識別情報として、｛セル識別情報「１０」，辺III｝、｛セル識別情報「３」，辺０｝の２つを発行して記録する。

このように従来であれば、同じ位置にある｛セル識別情報「９」，辺I｝の頂点と、｛セル識別情報「１０」，辺III｝の頂点とは異なる頂点として識別されるものであるところ、本実施の形態の方法によれば、この位置の点は、共通した｛セル識別情報「１０」，辺III｝として（抽象的に）表現され、共通した識別情報が割り当てられる。

画像処理装置１は、このようにして、各セルについての処理により、セル内のいずれかの辺上のセル内のポリゴンの頂点を、いずれかのセルの辺要素を識別する辺要素識別情報により表現して記録し、ポリゴンモデルの情報を生成する。そして画像処理装置１は、当該生成したポリゴンモデルの情報を用いて、可視化及び変形操作を含む所定処理を実行する。

この所定処理の実行のために、画像処理装置１は、まず、ポリゴンモデルの情報に含まれる、各ポリゴンの頂点に係る仮識別情報を、実際の描画に用いる頂点識別情報へ変換する（Ｓ５）。

画像処理装置１は、セルの各々を注目セルとして順次選択し、また選択した注目セルの辺要素を所定の選択順（例えばセルの、辺０，辺IIIの順）に、当該辺要素上のポリゴンの頂点の数をカウントしつつ累算する。そして画像処理装置１は、各辺要素について当該カウントして得られた値の和（累算値）を、注目セルについてのカウント値（ベースレベルカウント値）として記録する（図７（ａ））。

なお、説明の都合上、図６，図７のそれぞれにおける例は一致していない。つまり図６のポリゴンの例と図７におけるポリゴンの例とは異なる。

さらに画像処理装置１は、予め定められた位置（図７（ａ）の原点Ｏ）から順に、互いに隣接する複数のセル（例えば互いに隣接する２×２個のセル）のグループを複数設定する（図７（ａ）においては実線でグループを区別する）。そして画像処理装置１は、設定したグループを第１段ブロックとして、当該第１段ブロックの各々について、第１段ブロックに属するセル内の辺要素上のポリゴンの頂点の数の和、つまり、第１段ブロックに属するセルについてのベースレベルカウント値の和を、第１段ブロックについてのカウント値（レベル１カウント値）として記録する（図７（ｂ））。

ここでは原点のセルを含む２×２個のセルをグループとし、次に、このグループのＸ軸方向に隣接するセルを含む２×２個のセルをグループとし…と選択してゆき、Ｘ軸方向に隣接するセルがなくなったら、Ｘ＝０に戻って、既に形成したグループにＹ軸方向に隣接するセルを含む２×２個のセルをグループとして、再度このグループのＸ軸方向に隣接するセルを含む２×２個のセルをグループとし…と選択していく。この処理により、各セルが順番にグループに含められる。

画像処理装置１は、予め定められた位置から上記の形成順に、互いに隣接する複数の第１段ブロックのグループ（例えば互いに隣接する２×２個の第１段ブロックのグループ）を設定する（図７（ｂ）においても実線でグループを区別する）。そして画像処理装置１は、この設定したグループを第２段ブロックとして、当該第２段ブロック内に属するセル内の辺要素上のポリゴンの頂点の数の和を、第２段ブロックについてのカウント値（レベル２カウント値）として記録する（図７（ｃ））。

画像処理装置１は、次に、予め定められた位置から上記の形成順に、互いに隣接する複数の第２段ブロックのグループ（例えば互いに隣接する２×２個の第２段ブロックのグループ）を設定する（図７（ｃ）においても実線でグループを区別する）。そして画像処理装置１は、この設定したグループを第３段ブロックとして、当該第３段ブロック内に属するセル内の辺要素上のポリゴンの頂点の数の和を、第３段ブロックについてのカウント値（レベル３カウント値）として記録する（図７（ｄ））。ここで第３段ブロックの数は「１」となり、これ以上のグループ化が不能であるので、この第３段を最終レベルとする。

次に画像処理装置１は、ポリゴンの頂点の仮識別情報ごとに、仮識別情報であるセル識別情報と辺要素識別情報とを取得し、当該取得したセル識別情報で識別されるセルが含まれる、上記の処理で生成した最終レベルのブロック単位でのブロックを特定する。

ここでは最終レベルではブロックは１つだけであるので、どの仮識別情報についてもこのブロックを注目ブロックとして、注目ブロックに含まれる第２段ブロックを特定する。画像処理装置１は、特定した第２段ブロックのうち、取得したセル識別情報で識別されるセルが含まれるブロックを特定する。以下にセル識別情報「２４」の辺要素、「辺０」にある頂点について、頂点識別情報を生成する例について説明する。

この例では、画像処理装置１は、最終ブロック（第３段ブロック）の単一のブロックを注目ブロックとして、この注目ブロックに含まれる第２段ブロックを特定する。図７の例では、第３段ブロックの注目ブロックには、第２段ブロックのすべてのブロックが含まれるので、第２段ブロックのすべてを特定する。

画像処理装置１は、第２段ブロックで特定したブロックを、形成順に選択しつつ、取得したセル識別情報で識別されるセルが含まれるブロックが選択されるまでに選択したブロック（取得したセル識別情報で識別されるセルが含まれるブロックそのものは除く）に割り当てられた、ポリゴンの頂点の数の和の値を累算する。

ここでの例であるセル識別情報「２４」のセルは、第２段ブロックでは、右上のブロックに含まれる（どのセルがどのブロックに含まれるかについては、ブロックの形成時にブロックごとに記録しておく等の広く知られた処理により判断できるので、ここでの詳しい説明を省略する）ため、形成順に、セル識別情報「２４」で識別されるセルが含まれるブロックが選択されるまでに選択したブロックは左上のブロックのみとなる。そこで画像処理装置１は、この左上のブロックに割り当てられた、ポリゴンの頂点の数の和の値「９」を第２段ブロックの予備値として記録する。

さらに画像処理装置１は、セル識別情報「２４」のセルを含む第２段ブロックの右上のブロックに含まれる第１段ブロックを特定する。ここでは画像処理装置１は、第１段ブロックの第１行の第３列，第４列目、第２行の第３列，第４列目のブロックを特定する。画像処理装置１は、第１段ブロックで特定したブロックを、形成順に選択しつつ、取得したセル識別情報で識別されるセルが含まれるブロックが選択されるまでに選択したブロック（取得したセル識別情報で識別されるセルが含まれるブロックそのものは除く）に割り当てられた、ポリゴンの頂点の数の和の値を累算する。

ここでの例であるセル識別情報「２４」のセルは、第１段ブロックでは、第２行目の第４列目のブロックに含まれるため、形成順に、セル識別情報「２４」で識別されるセルが含まれるブロックが選択されるまでに選択したブロックは、第１段ブロックの第１行目の第３列，第４列目の各ブロック、及び、第２行目の第３列目のブロックとなる。そこで画像処理装置１は、これらのブロックに割り当てられた、ポリゴンの頂点の数の和の値「３」，「１」，「２」の和「６」を第１段ブロックの予備値として記録する。

さらに画像処理装置１は、セル識別情報「２４」のセルを含む第１段ブロックのブロックに含まれるセル（ベースレベル）を特定する。ここでは、セル識別情報で「２３」，「２４」，「３１」，「３２」の各セルが特定される。画像処理装置１は、ここで特定したセルを、ブロックの形成順（セルの識別情報が小さい順）に選択しつつ、取得したセル識別情報で識別されるセルが選択されるまでに選択したセルに割り当てられた、ポリゴンの頂点の数の和の値を累算する。

ここでの例であるセル識別情報「２４」のセルを選択するまでには、セル識別情報「２３」のセルのみが選択されるので、画像処理装置１は、セル識別情報「２３」のセルに割り当てられた値「０」を、辺要素予備値として記録する。

画像処理装置１は、この処理で記録した辺要素予備値、及び第ｉ段ブロックの予備値（ｉ＝１，２…Ｎ−１）の総和が表す値を求める。ここでは、辺要素予備値が「０」、第１段ブロックの予備値が「６」、第２段ブロックの予備値が「９」であるので、画像処理装置１は、セル識別情報「２４」の辺要素、「辺０」にある頂点の頂点識別情報を、これらの和である「１５」とする。画像処理装置１は、仮識別情報のそれぞれについて、上述の方法で頂点識別情報を求める。

画像処理装置１はさらに、記録しているポリゴン識別情報で識別されるポリゴンごとに、当該ポリゴンの各頂点の頂点識別情報を取得する。この処理は、従来通りのヒストグラムピラミッドの方法により実行すればよい。そして画像処理装置１は、以下は従来と同様の方法により、各ポリゴンの描画処理を実行する。

また画像処理装置１は、利用者から頂点を特定する頂点識別情報とともに、当該頂点の移動または、当該頂点の削除の指示を受け入れると、当該頂点識別情報で識別される頂点の仮想空間内での位置座標を指示に従って移動し、または当該頂点を削除して、当該頂点を含むポリゴンを削除する処理を行う。

図８に、頂点を削除する処理における従来例と本実施の形態との対比例を示す。従来のマーチングキューブの方法によれば、図８（ａ）に示すセル１（セル識別情報「１」のセルを、図においてセル１等と略記している）の頂点Ａと、セル２の頂点Ａ′とは、同じ位置にあるにも関わらず、セルごとに頂点を識別する情報が付与されるので、セル１の頂点Ａと、セル２の頂点Ａ′とには互いに異なる頂点を識別する情報が設定される。

ここで利用者がセル１の頂点Ａを削除する指示を行うと、従来例の画像処理装置では、セル１における頂点Ａを含むポリゴンを削除するが、セル２における頂点Ａ′を含むポリゴンは削除しない。このため、頂点Ａの位置にある頂点を削除するという利用者の意図通りにならず、これを利用者の意図通りに動作させるためには、削除の対象となった頂点Ａと同じ位置にある頂点を探索する処理が必要となって、変形等の処理に時間がかかる結果となる。

一方、本実施の形態の方法によると、セル１の頂点Ａも、セル２の頂点Ａも、ともに、セル１の辺要素「０」上の点として抽象的に表現されてから、頂点識別情報（Ａ）に変換されているため、共通の頂点識別情報「Ａ」が付与される。

このため利用者がセル１の頂点Ａを削除する指示を行うと、セル２内において頂点Ａを有するポリゴンも削除されることとなり（図８（ｂ））、利用者の意図通りの処理が可能となる。また、１つの頂点識別情報により削除するべきポリゴンが特定できるので、処理負荷も軽減される。

併せて、本実施の形態の方法では、全体としてポリゴンの数に対する頂点識別情報の数が膨大とならない（従来の方法ではポリゴンの数に頂点数を乗じた数だけの頂点識別情報が発行される）。これにより、本実施の形態の方法では、描画等の処理負荷も軽減される。

具体的に、ポリゴン数に対する、従来一般的な（頂点とポリゴンとの関連付けにヒストグラムピラミッド法を用いない）マーチングキューブによる計算処理（ＶＴＫ）と、頂点とポリゴンとの関連付けにヒストグラムピラミッド法を用いた場合のマーチングキューブによる計算処理（ＨＰＭＣ）と、本実施の形態の方法による計算処理（ProposedＭＣ）とにおける、同一座標の頂点の統合時間を含む処理時間の相違を図９に示す。

図９に例示するように、ポリゴン数が比較的大きい範囲では、ＶＴＫに対して本実施の形態による方法は５倍以上（全体平均でも４倍以上）の高速化が図られる。また、ヒストグラムピラミッド法を用いた場合のマーチングキューブ法（ＨＰＭＣ）に対しても３倍以上（全体平均でも３倍以上）の高速化が図られている。

１ 画像処理装置、１１ 制御部、１２ 記憶部、１３ 操作部、１４ 表示部、１５ インタフェース部、２０ ポリゴンモデル生成部、２１ データ受入部、２２ セル設定部、２３ 辺要素設定部、２４ 頂点仮識別情報取得部、２５ ポリゴンモデル設定部、３０ 描画処理部。

Claims (3)

1. 仮想的なポリゴンモデルを形成する仮想空間を、所定多角形状の仮想的なセルに分割して、ポリゴンモデルを形成する画像処理装置であって、
   処理対象となる前記仮想空間内に分布する値データを受け入れる手段と、
   前記値データに基づいて、前記セルの多角形状の各頂点の位置ごとの値を決定する手段と、
   前記各セルの辺のうち、互いにその位置が重なり合わない辺を辺要素として、各辺要素を識別する辺識別情報を設定し、各辺要素の両端の頂点の位置に対応する前記値に基づいて、セル内を通過するポリゴンの頂点が位置する辺要素の辺識別情報を特定する手段と、
   前記特定した辺識別情報を用いて前記ポリゴンモデルを表す情報を生成するポリゴンモデル生成手段と、
   を含み、
   当該辺識別情報を用いて表されるポリゴンモデルの情報が、可視化及び変形操作を含む所定処理に供される画像処理装置。
2. 請求項１記載の画像処理装置であって、
   前記ポリゴンモデル生成手段は、
   前記セルの各々について、当該セルの当該辺要素上のポリゴンの頂点の数をカウントして、各辺要素について当該カウントして得られた値の和を記録する手段と、
   互いに隣接する複数のセルのグループを第１段ブロックとして、当該第１段ブロック内に属するセルの前記辺要素上のポリゴンの頂点の数の和を記録する手段と、
   互いに隣接する複数の第（ｉ−１）段（ｉは、ｉ＞１なる整数）ブロックのグループを、第ｉ段ブロックとして、当該第ｉ段ブロック内に属するセル内の辺要素上のポリゴンの頂点の数の和を記録する手段と、を含み、
   当該記録されたブロック単位でのブロック内に属するセル内の辺要素上のポリゴンの頂点の数の和、または記録されたセル単位でのセル内の辺要素上のポリゴンの頂点の数の和の値を参照して、前記ポリゴンモデルを表す情報から、各ポリゴンの頂点の位置を特定する情報を生成する画像処理装置。
3. コンピュータを、
   処理対象となる仮想空間内に分布する値データを受け入れる手段と、
   前記仮想空間を所定多角形状の仮想的なセルに分割し、前記値データに基づいて、前記セルの多角形状の各頂点の位置ごとの値を決定する手段と、
   前記各セルの辺のうち、互いにその位置が重なり合わない辺を辺要素として、各辺要素を識別する辺識別情報を設定し、各辺要素の両端の頂点の位置に対応する前記値に基づいて、セル内を通過するポリゴンの頂点が位置する辺要素の辺識別情報を特定する手段と、
   前記特定した辺識別情報を用いてポリゴンモデルを表す情報を生成するポリゴンモデル生成手段と、
   として機能させ、
   当該辺識別情報を用いて表されるポリゴンモデルの情報を、可視化及び変形操作を含む所定処理に供するプログラム。

Images