JP6080267B2 - ３次元オブジェクト分割出力装置およびその応用 - Google Patents

Description

本発明は、木構造のオブジェクトを３次元造形装置に出力する際に、３次元造形装置の出力範囲に収まるようにオブジェクトを分割して出力する３次元オブジェクト分割出力装置およびその応用に関するものである。

近年、ＣＴ（Computed Tomography）装置やＭＲＩ（Magnetic Resonance Imaging）装置などで取得された断層画像を基に、患者個人の血管や臓器の３次元模型を作製して、診断や手術の術式の検討などに役立てようとする試みが行われている。

例えば、特許文献１には、ＣＴ装置やＭＲＩ装置などで撮影された患者個人の断層画像データから目的の部位のデータを抽出して、抽出された断層画像データから模型造形用の断層データを作成したものを用いて、粉体を積層して精密粉体模型を作製した上で精密粉体模型を鋳型として透明または半透明のシリコンなど柔軟性を持つポリマーで血管や臓器を患者ごとに作製する手法が開示されている。

さらに、特許文献２には、３次元ボリュームデータから肝臓領域および肝動脈、肝静脈等の構造物を抽出し、これら構造物のサーフェスデータを生成し、構造物のサーフェスデータを合成して、立体モデルデータを生成した上で、立体モデルを等高面で分けた断面データを用いて３次元プリンターで製造する手法が開示されている。

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

３次元プリンターなどの造形装置で高解像度の大きなオブジェクトを出力する場合、オブジェクトの大きさに対応する大規模な３次元プリンターが必要になる。しかし、大規模な３次元プリンターは非常に高価であるため、実際にはオブジェクトをいくつかに小さく分割し、小規模な３次元プリンターでそれぞれ出力し、後で接合することにより大きなオブジェクトの全体を製造している。

また、分割出力する場合、オブジェクトが塊になっている場合はどのように分割しても大した問題にはならないが、血管や気管支のように木構造のオブジェクトの場合、３次元プリンターで出力可能な範囲を表す直方体の形状に当てはめて単純に分割すると、末端の枝の部分が切り取られて小さい枝に分かれてバラバラになってしまい、後に各パーツを組み立てる上で、接合する箇所が増えてしまうため、現実的な分割手法とはいえない。

例えば、木構造である気管支を３次元プリンターで出力する場合、解剖学的には葉間膜を横断する箇所でオブジェクトを分割するのが、少ない接合回数で、より大きなオブジェクトを出力するのに好適である。しかし、葉間膜部分でオブジェクトを分割した場合であっても、３次元プリンターの出力範囲を越えることがある。

このように、血管や気管支のような木構造のオブジェクトを小規模な３次元プリンターで出力するときに小さい断片にならないようにオブジェクトを分割する分割方法が重要になる。

本発明は上記事情に鑑みてなされたものであり、３次元プリンターで出力するときに小さい断片にならないように３次元のオブジェクトを分割して３次元造形装置に出力する３次元オブジェクト分割出力装置およびその応用を提供することを目的とする。

本発明の３次元オブジェクト分割出力装置は、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出部と、３次元オブジェクトの木構造のエッジ上で分割した分割オブジェクトの少なくとも一方の大きさが３次元造形装置の出力範囲に対して最大となる分割候補位置を探索する分割位置探索部と、分割候補位置のあるエッジ上の分割位置で３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割部と、分割オブジェクトを３次元造形装置に出力する出力部とを備えたものである。

また、本発明の３次元オブジェクト分割出力装置の作動方法は、抽出部と分割位置探索部と分割部と出力部とを備えた３次元オブジェクト分割出力装置の作動方法であって、抽出部が、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、分割位置探索部が、３次元オブジェクトの木構造のエッジ上で分割した分割オブジェクトの少なくとも一方の大きさが３次元造形装置の出力範囲に対して最大となる分割候補位置を探索する分割位置探索ステップと、分割部が、分割候補位置のあるエッジで３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、出力部が、分割オブジェクトを３次元造形装置に出力する出力ステップとを備えるものである。

さらに、本発明の３次元オブジェクト分割出力プログラムは、コンピュータに、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、３次元オブジェクトの木構造のエッジ上で分割した分割オブジェクトの少なくとも一方の大きさが３次元造形装置の出力範囲に対して最大となる分割候補位置を探索する分割位置探索ステップと、分割候補位置のあるエッジで３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、分割オブジェクトを３次元造形装置に出力する出力ステップとを実行させるためのものである。

「木構造」とは、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成され、分岐点でエッジが分かれた階層構造をもつものをいい、具体的に、「木構造を持つ３次元オブジェクト」には、気管支や血管などがあげられる。

「３次元造形装置の出力範囲」とは、３次元造形装置でオブジェクトが出力可能な最大の高さ、幅、奥行きで表されるものであり、「分割オブジェクトの大きさが３次元造形装置の出力範囲に対して最大となる」とは、分割オブジェクトの高さ、幅、奥行きの全てが３次元造形装置の出力範囲の最大の高さ、幅、奥行き以下であって、分割オブジェクトの高さ、幅、奥行きのうちの少なくとも1つが３次元造形装置の出力範囲の最大の大きさになるものをいう。また、「分割オブジェクトの大きさが３次元造形装置の出力範囲に対して最大となる」には、分割オブジェクトを傾けた時の高さ、幅、奥行きのうちの少なくとも1つが３次元造形装置の出力範囲の最大の大きさになるものも含む。

また、３次元オブジェクト分割出力装置が、３次元オブジェクトの木構造上の少なくとも１点から複数の端点に到達する全ての経路に基づいて、各経路が各エッジを通過する回数をエッジ毎にカウントして得られる多重度を取得する多重度取得部をさらに備えるように構成して、分割位置探索部が、多重度が最大のエッジから順に、分割候補位置を探索するものであってもよい。

「３次元オブジェクトの木構造上の少なくとも１点」は、木構造の端点であっても、分岐点であっても、木構造のエッジ上の１点であってもよい。

また、３次元オブジェクト分割出力装置が、分割オブジェクトを除いた３次元オブジェクトの木構造に対して、分割位置探索部および分割部により、新たな分割オブジェクトを繰り返し生成する繰り返し制御部をさらに備えるようにしてもよい。

あるいは、３次元オブジェクト分割出力装置が、分割オブジェクトを除いた３次元オブジェクトの木構造に対して、多重度取得部、分割位置探索部および分割部により、新たな分割オブジェクトを繰り返し生成する繰り返し制御部をさらに備えるようにしてもよい。

また、分割位置探索部は、分割オブジェクトに含まれる木構造の端点を用いて得られる包絡面による凸包体に外接する外接直方体が、出力範囲に対して最大となる分割候補位置を探索するものであってもよい。

「外接直方体が、出力範囲に対して最大となる」とは、外接直方体の高さ、幅、奥行きの全てが３次元造形装置の出力範囲の最大の高さ、幅、奥行き以下であって、外接直方体の高さ、幅、奥行きのうちの少なくとも1つが３次元造形装置の出力範囲の最大の大きさになるものをいう。

さらにまた、外接直方体は、凸包体に外接する直方体の体積が最小となる最小直方体であるものが望ましい。

また、出力部は、外接直方体の一辺が３次元造形装置の出力範囲の直方体の一辺と平行になり、かつ、外接直方体が出力範囲の直方体に収まる向きに分割オブジェクトを回転して出力するのが望ましい。

また、多重度取得部が、３次元オブジェクトの木構造の１つの端点からこの１つの端点以外の他の端点に到達する全ての経路に基づいて、各経路が各エッジを通過する回数をエッジ毎にカウントして得られる多重度を取得するものであってもよい。

また、多重度取得部が、複数の端点のうち特定の１つの端点から特定の１つの端点以外の他の端点へ到達する全ての経路、または、複数の端点以外の３次元オブジェクトの木構造上の特定の１点から複数の端点へ到達する全ての経路に基づいて、各経路が各エッジを通過する回数をカウントして多重度を取得するものであってもよい。

また、多重度取得部が、３次元オブジェクトの木構造の２つの分岐点間を接続するエッジの中から選択された１つのエッジ上の１点で木構造を２つに分けた２つの部分木構造に対して、選択されたエッジ上の１点から部分木構造の端点に到達する全ての経路に基づいて得られる多重度をそれぞれ取得し、選択されたエッジの多重度を２つの部分木構造に対して取得した多重度のうち小さい値の多重度を選択されたエッジの多重度とするものであってもよい。

また、多重度取得部が、複数の端点のうち１つの端点から１つの端点以外の他の端点へ到達する全ての経路に基づいて、各経路が各エッジを通過する回数をカウントする処理を、各端点のそれぞれに対して行ってカウントされた各エッジを通過する回数を全て加算して得られる多重度を取得するものであってもよい。

また、分割部が、分割オブジェクトが出力範囲内の大きさとなり、かつ、分割候補位置があるエッジ上で最も太くなる分割位置で分割するものであってもよい。

分割位置探索部は、２つの分岐点間を接続するいずれかのエッジで分割した時に、分割オブジェクトの少なくとも一方が出力範囲内の大きさから出力範囲を越える大きさに変わるエッジ上の分割候補位置を探索するものであってもよい。

本発明によれば、３次元オブジェクトの木構造のエッジ上で分割した分割オブジェクトの大きさが３次元造形装置の出力範囲に対して最大となる分割位置を探索して、３次元オブジェクトを分割した分割オブジェクトを生成して３次元プリンターに出力することにより、３次元オブジェクトが小さい断片にならないように分割して、なるべく少ない回数で３次元プリンターに出力することが可能になり、分割した３次元オブジェクトを組み立てる上で、接合する箇所を少なくすることできる。

本発明の実施形態による３次元オブジェクト分割出力装置を適用した立体モデル製造システムの概略構成を示す図 本発明の実施形態による３次元オブジェクト分割出力部の機能ブロック図 本発明の実施形態による立体モデル製造システムの処理の流れを示すフローチャート（その１） 木構造の一例 多重度の計算方法を説明するための図（その１） 多重度の計算方法を説明するための図（その２） 多重度の計算方法を説明するための図（その３） 多重度の計算方法を説明するための図（その４） 多重度の計算結果の一例 分割オブジェクトが３次元プリンターの出力範囲内に収まるか否かの判定方法を説明するための図（その１） 分割オブジェクトが３次元プリンターの出力範囲内に収まるか否かの判定方法を説明するための図（その２） エッジ上の分割候補位置を説明するための図 本発明の実施形態による立体モデル製造システムの処理の流れを示すフローチャート（その２） 全ての端点から他の端点へ向かう全ての経路で多重度をカウントする方法を説明するための図(その１) 全ての端点から他の端点へ向かう全ての経路で多重度をカウントする方法を説明するための図(その２) 全ての端点から他の端点へ向かう全ての経路で多重度をカウントする方法を説明するための図(その３) 全ての端点から他の端点へ向かう全ての経路で多重度をカウントする方法を説明するための図(その４) 全ての端点から他の端点へ向かう全ての経路で多重度をカウントする方法を説明するための図(その５) 全ての端点から他の端点へ向かう全ての経路で多重度をカウントする方法を説明するための図(その６) 全ての端点からカウントした多重度の一例 正規化した多重度の一例 木構造上のエッジ上の１点から多重度をカウントする方法を説明するための図 分割オブジェクトを出力時に回転させる方法を説明するための図（その１） 分割オブジェクトを出力時に回転させる方法を説明するための図（その２）

本発明の３次元オブジェクト分割出力装置の実施形態について、図に基づいて説明する。図１は、３次元オブジェクト分割出力装置を設けた立体モデル製造システムの概要を示すハードウェア構成図である。図に示すように、このシステムでは、モダリティ１と、画像保管サーバ２と、画像処理ワークステーション３と、３次元造形装置４が、ネットワーク５を経由して通信可能な状態で接続されている。

モダリティ１には、患者の対象部位を撮影することにより、その部位を表す３次元医用画像の画像データを生成し、その画像データにＤＩＣＯＭ（Digital Imaging and Communications in Medicine）規格で規定された付帯情報を付加して、画像情報として出力する装置が含まれる。具体例としては、ＣＴ、ＭＲＩなどで撮影された画像データが挙げられる。以下、３次元医用画像の画像データをボリュームデータとして説明する。

画像保管サーバ２は、モダリティ１で取得されたボリュームデータや画像処理ワークステーション３での画像処理によって生成された画像データを画像データベースに保存・管理するコンピュータであり、大容量外部記憶装置やデータベース管理用ソフトウェア（たとえば、ＯＲＤＢ（Object Relational Database）管理ソフトウェア）を備えている。

画像処理ワークステーション３は、ユーザからの要求に応じて、モダリティ１や画像保管サーバ２から取得したボリュームデータに対して画像処理を行うコンピュータであり、ＣＰＵ（Central Processing Unit），主記憶装置、補助記憶装置、入出力インターフェース、通信インターフェース、入力装置（マウス、キーボード等）、表示装置（ディスプレイモニタ）、データバス等の周知のハードウェア構成を備え、周知のオペレーティングシステム等がインストールされたものである。本発明の３次元オブジェクト分割出力装置は、この画像処理ワークステーション３に実装されており、この処理は、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）等の記録媒体からインストールされたプログラムを実行することによって実現される。また、プログラムは、インターネット等のネットワーク経由で接続されたサーバの記憶装置からダウンロードされた後にインストールされたものであってもよい。

３次元造形装置４は、出力対象の３次元オブジェクトの等高面のデータ（断面データなど）を作成し、断面データにしたがって、断面形状を積層していくことで立体物を作成する装置である。立体物を作成する方式には、液状の樹脂に紫外線などを照射し少しずつ硬化させていくインクジェット方式、熱で融解した樹脂を少しずつ積み重ねていくＦＤＭ（Fused Deposition Modeling, 熱溶解積層法）方式、粉末の樹脂に接着剤を吹きつけていく粉末固着方式などがある。以下、３次元造形装置を３次元プリンターという。

図２は、画像処理ワークステーション３の機能のうち、本発明の実施形態となる３次元オブジェクト分割出力部を示すブロック図であり、図３は処理の流れを示すフローチャートである。図２に示すように、本発明の実施形態における３次元オブジェクト分割出力部は、抽出部３１、多重度取得部３２、分割位置探索部３３、分割部３４、出力部３５、繰り返し制御部３６によって実現される。

以下、図２および図３に従って、３次元オブジェクト分割出力部について詳細に説明する。

抽出部３１は、木構造を持つ３次元オブジェクトをボリュームデータから抽出する。木構造を持つ３次元オブジェクトには、血管や気管支があるが、本実施形態では、３次元オブジェクトとして気管支を例に、ＣＴ装置で撮影されたボリュームデータから抽出する場合について説明する。

最初に、画像処理ワークステーション３は、立体モデルを作製する患者のボリュームデータＶを画像保管サーバ２から検索して受け取る。受け取ったボリュームデータＶに対して、抽出部３１を用いて患者の気管支の構造を抽出する（#1）。

ボリュームデータＶ中の気管支は、気管支の内部の画素は空気領域に相当するためＣＴ画像上では低いＣＴ値（画素値）を示す領域として表れるが、気管支壁は比較的高いＣＴ値を示す線状の構造物であると考えられる。そこで、領域拡張法により気管支らしい画像値を持つ画素の集合を気管支領域として抽出し、抽出された気管支領域に対して細線化処理を行い、得られた気管支を表す線状構造物を抽出する。

あるいは、各画素ごとにＣＴ値の分布に基づく形状の構造解析を行なって気管支を抽出する。気管支は多段階に分岐し末端に近づくほど気管支の径は小さくなっていく。異なるサイズの気管支（線状構造物）を検出することができるように、予め、ボリュームデータを多重解像度変換したガウシアンピラミッド画像（つまり、異なる解像度の複数の三次元画像）を生成し、生成したガウシアンピラミッドの各画像ごとに検出アルゴリズムを走査することで異なるサイズの線状構造物を検出する。

このようにして抽出された線状構造物は、全ての線状構造物が繋がった１つの木構造として検出されるとは限らない。そこで、検出された線状構造物の接続関係を再構築する。この再構築により、気管支の木構造の抽出が完了する。抽出した木構造を、端点・分岐点・エッジ（辺）に分類し、端点・分岐点をエッジで連結することによって、気管支を表す木構造データＴを得る。必要に応じて、木構造の各位置における気管支の径や各エッジの長さ（気管支の分岐点間の長さ）等の特徴量も木構造データとして格納する。

木構造の抽出方法については他の手法を用いて、あるいは他の手法と組み合わせて抽出することが可能であり、本願出願人が出願した特開2010-220742号公報、特開2011-212312号公報、特開2012‐200403号公報、特開2012-228396号公報などに記載の木構造の抽出手法を用いてもよい。

木構造は、複数の端点および分岐点、端点と分岐点間を接続するエッジ、２つの分岐点間を接続するエッジで構成されたものである。図４に気管支を抽出した時の木構造の一例を示す。図４では、分岐点を●、端点を○、エッジを線で表している。

多重度取得部３２は、３次元オブジェクトの木構造の上の少なくとも１点から複数の端点に到達する全ての経路が各エッジを通過する回数をエッジ毎にカウントして得られる多重度を取得する（#2）。

図５Ａ〜５Ｃの木構造を用いて、多重度の計算方法について具体的に説明する。ここでは、３次元オブジェクトの木構造の１つの端点からこの１つの端点以外の他の端点に到達する全ての経路に基づいて、各経路が各エッジを通過する回数をエッジ毎にカウントして多重度を取得する。

図５Ａ〜５Ｃに示すように、気管支の気道部に対応する端点を根として、根Rootから他の端点E1,E2,E3,E4・・・E17,E18,E19,E20に到達する全ての端点に向かう経路が、各エッジを通過した回数をカウントする。

まず、図５Ａに示すように、根Rootから端点E1に到達する経路は、根Rootと分岐点B1を接続するエッジ、分岐点B1と分岐点B2を接続するエッジ、分岐点B2と分岐点B3を接続するエッジ、分岐点B3と端点E1を接続するエッジを通過するので、各エッジを通過する回数がそれぞれ１になる。次に、図５Ｂに示すように、根Rootから端点E2に到達する経路は、根Rootと分岐点B1を接続するエッジ、分岐点B1と分岐点B2を接続するエッジ、分岐点B2と分岐点B3を接続するエッジ、分岐点B3と端点E2を接続するエッジを通過するので、根Rootから分岐点B3までの各エッジを経路が通過する回数が２となり、分岐点B3と端点E2を接続するエッジを経路が通過する回数が１になる。さらに、図５Ｃに示すように、根Rootから端点E3に到達する経路は、根Rootと分岐点B1を接続するエッジ、分岐点B1と分岐点B2を接続するエッジ、分岐点B2と分岐点B4を接続するエッジ、分岐点B4と分岐点B5を接続するエッジ、分岐点B5と端点E3を接続するエッジを通過するので、根Rootから分岐点B2までの各エッジを経路が通過する回数が３となり、分岐点B2と分岐点B4を接続するエッジ、分岐点B4と分岐点B5を接続するエッジ、分岐点B5と端点E3を接続するエッジを経路が通過する回数が１になる。同様に、図５Ｄに示すように、根Rootから端点E4に到達する経路は、根Rootと分岐点B1を接続するエッジ、分岐点B1と分岐点B2を接続するエッジ、分岐点B2と分岐点B4を接続するエッジ、分岐点B4と分岐点B5を接続するエッジ、分岐点B5と端点E4を接続するエッジを通過するので、根Rootから分岐点B2までの各エッジを経路が通過する回数が４となり、分岐点B2と分岐点B4を接続するエッジ、分岐点B4と分岐点B5を接続するエッジを経路が通過する回数が２になり、分岐点B5と端点E4を接続するエッジを経路が通過する回数が１になる。

上記のように、根Rootから全ての端点E1,E2,E3,E4・・・E17,E18,E19,E20に到達する経路が各エッジを通過した回数をカウントした結果を図６に示す。

分割位置探索部３３は、３次元オブジェクトの木構造のうち２つの分岐点間を接続するエッジ上で分割した２つの分割オブジェクトの少なくとも一方の大きさが３次元プリンター４の出力範囲に収まる大きさであって、その分割オブジェクトがなるべく大きくなるように分割候補位置を探索する。具体的には、２つの分岐点間を接続するいずれかのエッジ上で分割した時に、２つに分割された分割オブジェクトの少なくとも一方が出力範囲内の大きさから出力範囲を越える大きさに変わるエッジ上の分割位置を分割候補位置として探索する。

ここで、分割オブジェクトが３次元プリンター４の出力範囲内に収まるか否かの判定方法について説明する。

あるエッジで分割した分割オブジェクトに含まれる木構造の端点に対して凸包を計算するアルゴリズムを適用して、図７Ａに示すような包絡面による凸包体を求めて、この凸包体が３次元プリンター４の出力範囲に収まる大きさであるか否かについて判定する。３次元プリンター４の出力範囲は直方体で定義されるので、図７Ｂに示すように、分割オブジェクトを包む凸包体に外接する外接直方体を取得して、外接直方体の３辺（縦、横、高さ）と３次元プリンター４の出力範囲の直方体とを比較することで、３次元プリンター４の出力範囲に収まるか否かを判定することができる。３次元オブジェクトをなるべく少ない数に分割するために、外接直方体が出力範囲に対して最大になるか否かについて判定する。つまり、外接直方体の高さ、幅、奥行きの全てが３次元プリンター４の出力範囲の最大の高さ、幅、奥行き以下であって、外接直方体の高さ、幅、奥行きのうちの少なくとも1つが３次元プリンター４の出力範囲の最大の大きさになるものを見つけるようにする。

また、凸包体に外接する直方体は多数見つけることができるが、外接する直方体のうち体積が最小になる最小直方体が３次元プリンター４の出力範囲に収まるか否かを判定する。これにより、３次元オブジェクトをより少ない数に分割して、３次元プリンター４に少ない出力回数で効率よく３次元オブジェクト全体を出力することが可能になる。

全てのエッジで、各エッジ上で分割した時に作成される２つの分割オブジェクトのうち一方が出力範囲内の大きさから出力範囲を越える大きさに変わるか否かを判定して、分割候補位置があるエッジを探索してもよいが、効率的に分割候補位置を探索するために、上記で取得した多重度を用いる。

分割位置探索部３３は、多重度が最大のエッジから順に、分割候補位置を探索し、エッジ上で３次元オブジェクトを分割した分割オブジェクトの一方が３次元プリンター４の出力範囲内に収まるか否かの判定を行う（#3）。

図６に示す例では、根Rootと分岐点B1を結ぶエッジが最も多重度（２０）が大きいが、このエッジの長さが３次元プリンター４の出力範囲を越えていなければ、次に多重度が高いエッジで分割候補位置を捜す。次に多重度が高いエッジは分岐点B1、B2を接続するエッジ（多重度が１０）、または分岐点B1、B6を接続するエッジ（多重度が１０）である。多重度が同じエッジがある場合には、所定の規則を設けて順番に評価を行う。例えば、先に分岐点B1、B2を接続するエッジのB1側で分割した時に、図６のB1より右にある分割オブジェクトとB1より左にある分割オブジェクトのどちらかが３次元プリンター４の出力範囲内に収まるか否かを判定する。どちらも出力範囲内に収まらなければ分岐点B2側で分割した時に、左右の分割オブジェクトのどちらかが３次元プリンター４の出力範囲内に収まるか否かを判定する。分岐点B2でもどちらも出力範囲内に収まらなければ、分岐点B1、B6を接続するエッジについて判定を行う。分岐点B1、B6を接続するエッジの分岐点B1側で分割した時に分割オブジェクトのどちらかが出力範囲に収まるか否かを判定し、出力範囲に収まらなければ、分岐点B6側で分割した時に分割オブジェクトのどちらかが出力範囲に収まるか否かを判定する。分岐点B6でもどちらの分割オブジェクトも出力範囲内に収まらなければ、分岐点B2、B4を接続するエッジ（多重度が８）について判定を行う。このように多重度の大きいエッジから順に判定を行い、多重度の大きいエッジの両端で分割した時に、エッジの一方の分岐点で分割した時は出力範囲を越えているが、エッジのもう一方の分岐点で分割した時には出力範囲に収まるエッジを探索する。

例えば、分岐点B7、B8を接続するエッジの分岐点B7で分割した下側の分割オブジェクトは出力範囲を超えるが、分岐点B8で分割した下側の分割オブジェクトは出力範囲に収まる場合には、分岐点B7、B8を接続するエッジ上で出力範囲に対して分割オブジェクトが最も大きくなる分割候補位置を捜す。図８に示すように、分岐点B7、B8を接続するエッジ上で出力範囲に対して分割オブジェクトが最も大きくなる位置Pが分割候補位置となる。

分割部３４は、分割候補位置のあるエッジ上で分割して３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する(#4)。気管支のようなオブジェクトを分割した場合、分割オブジェクトを後で結合するためには、なるべく気管支が太いところで分割した方が良い。そこで、分割候補位置ではなくその位置の近くでなるべく気管支が太いところで分割するのが好ましい。例えば、分割候補位置Pから分岐点B8の間のエッジ上で最も太くなる分割位置で分割する。気管支の場合、通常は分割候補位置があるエッジの中で根に近い位置が実際の分割位置になる場合が多い。木構造を持つ３次元オブジェクトが血管である場合には、一部が狭くなっている血管もあるので、最も太くなる分割位置を探して分割をおこなうのが望ましい。

出力部３５は、生成された分割オブジェクトを３次元プリンター４に出力する(#5)。分割オブジェクトを出力する際には、図１４に示すように、分割オブジェクトが３次元プリンター４の出力範囲R内に収まるか否かの判定方法で説明した分割オブジェクト内の木構造の端点で構成した凸包体O1が３次元プリンター４の出力範囲Rに収まる方向に分割オブジェクトを回転（図１４の矢印）させて出力する。

あるいは、図１５に示すように、凸包体に外接する外接直方体O2の一辺が３次元プリンター４の出力範囲の直方体の一辺と平行になるように回転（図１５の矢印）させる方向を、分割オブジェクトを回転させる方向として決定することができる。回転させる方向によっては、外接直方体が３次元プリンター４の出力範囲Rの直方体に収まらないので、外接直方体が３次元プリンター４の出力範囲Rの直方体に収まる向きに分割オブジェクトを回転して出力するようにする。

さらに、出力部３５は、回転後の分割オブジェクトを等高面で分けた断面データを生成して、３次元プリンター４に出力する。

分割オブジェクトを出力後、出力した分割オブジェクトを除いた残りの３次元オブジェクトが３次元プリンター４の出力範囲を越える場合には再度分割する（#6-NO）。

そこで、繰り返し制御部３６は、#3に処理を戻して、再度、分割位置探索部３３は、多重度が最大のエッジから順に分割候補位置を探索して、分割候補位置のあるエッジ上で３次元オブジェクトを分割して分割オブジェクトを生成し（#4）、分割オブジェクトを３次元プリンター４に出力する(#5)処理を、出力した分割オブジェクトを除いた残りの３次元オブジェクトが３次元プリンター４の出力範囲に収まるようになるまで繰り返す。出力した分割オブジェクトを除いた残り３次元オブジェクトが３次元プリンター４の出力範囲になると（#6-YES）、３次元プリンター４が残りの３次元オブジェクトを出力して終了する(#7)。

ここでは、出力した分割オブジェクトを除いた残りの３次元オブジェクトに対して多重度を計算し直さないで多重度を１回のみ計算する場合について説明したが、図９のフローチャートの#11〜#17に示すように、分割オブジェクトを除いた残りの３次元オブジェクトが３次元プリンター４の出力範囲を越えている場合には、#12で残りの３次元オブジェクトに対して再度多重度を計算するようにしてもよい。

上述では、木構造の複数の端点のうち特定の１つの端点（根となる端点）から特定の１つの端点以外の他の端点へ到達する全ての経路に基づいて、各経路が各エッジを通過する回数をカウントして多重度を取得する場合について説明したが、全端点から、自身の端点以外の他の端点へ到達する全ての経路に基づいて、各経路が各エッジを通過する回数をカウントして多重度を取得するようにしてもよい。図１０〜１２を用いて、具体的に説明する。

図１０に示すような根を持たない木構造の場合には、全ての端点から他の端点へ向かう全ての経路で多重度をカウントする。図１０Ａ〜図１０Ｆの各数字は、１つのエッジから他の端点へ向かう経路上で各エッジを経路が通過した回数をカウントしたものである。図１０Ａは、数字「３４」が付されている１番目の端点から他の端点へ向かう経路上で各エッジを経路が通過した回数をカウントした数字を表すものである。図１０Ｂは、１番目の端点の右隣の２番目の端点から他の端点へ向かう経路上で各エッジを経路が通過した回数をカウントした数字を表すものであり、図１０Ｃは、２番目の端点の右隣の３番目の端点から他の端点へ向かう経路上で各エッジを経路が通過した回数をカウントした数字を表すものである。同様に右回りの方向に次の端点を進んで行き、各端点から他の端点へ向かう経路上で各エッジを経路が通過した回数をカウントしていく。図１０Ｄは３２番目の端点から他の端点へ向かう経路上で各エッジを経路が通過した回数をカウントした数字を表すものであり、図１０Ｅは３３番目の端点から他の端点へ向かう経路上で各エッジを経路が通過した回数をカウントした数字を表すものであり、図１０Ｆは３４番目の端点から他の端点へ向かう経路上で各エッジを経路が通過した回数をカウントした数字を表すものである。

１番目〜３４番目の各端点から他の端点へ向かう経路上でカウントした各エッジを経路が通過した回数を全て加算したものを図１１に示す。図１１の数字が、各エッジの多重度を表している。さらに、図１２は、端点に接続するエッジの多重度が１になるように、正規化した時の多重度を表している。

上述では、端点から他の端点へ向かう全ての経路で多重度をカウントする場合について説明したが、木構造の端点を除いた３次元オブジェクトの木構造上の特定の１点から木構造の複数の端点へ到達する経路に基づいて多重度を取得するようにしてもよい。具体的には、図１３に示すように、木構造の２つの分岐点間を接続するエッジの中から選択された１つのエッジ上の１点Qで木構造を２つに分けた２つの部分木構造に対して、点Qから左右の部分木構造の端点に到達する全ての経路に基づいて得られる多重度をそれぞれの部分木構造に対して取得する。選択されたエッジ（点Qのあるエッジ）の多重度は、２つの部分木構造に対して取得した多重度のうち小さい値の多重度を選択されたエッジの多重度とする。図１３の例では、点Qのあるエッジの多重度は１７になる。

上述のような根を持たない木構造は、血管などに多く表れる。

また、上述では、分割オブジェクトに含まれる木構造を包む凸包体を求めて、この凸包体が３次元プリンター４の出力範囲に収まる大きさであるか否かについて判定する手法について説明したが、単純に、分割オブジェクトの高さ、幅、奥行きの長さが３次元プリンター４の出力範囲に収まる大きさであるか否かについて判定するようにしてもよい。

あるいは、分割オブジェクトの２つの端点間の長さが最も長い２つの端点を探し、その２つの端点を結ぶ直線に対して垂直な２つの軸方向に分割オブジェクトが広がっている距離をみて、３次元プリンター４の出力範囲に収まるか否かを判定するものであってもよい。

上述の出力部３５では、単純に３次元オブジェクトを分割した分割オブジェクトを出力する場合について説明したが、分割オブジェクトに切断した切断面を結合することができるように、分割した両方の切断面に嵌め込み可能な形状の接続部を設けた上で３次元プリンター４に出力するのが望ましい。

気管支や血管をエッジ（枝）で分割した切断面は円に近い形状になるが、接続部に円形の接続部を設けると、接続したときに枝が回転して本来の枝が接続されるべき向きとは違う向きに接続される場合がある。そこで、接続部の形状は、不等辺三角形や台形など形状にして嵌め込む向きが一意に決まる様な形状にするのが望ましい。さらに、複数の分割オブジェクトに分割したときには、接続部を間違えて結合することがないように、それぞれ接続部の形状を異なる形状あるいは異なる大きさにするのが望ましい。

なお、本実施形態に限定されず、３次元オブジェクト分割出力部の一部または全部は、1台のコンピュータにより実行されるものであってもよく、ネットワークを介して接続された一台以上のコンピュータ、サーバ、記憶装置によって構成されたもので実行されるものであってもよい。なお、各機器は、ＣＤ−ＲＯＭ等の記録媒体からインストールされた本明細書の３次元オブジェクト分割出力部のプログラムによって制御される。また、プログラムは、インターネット等のネットワーク経由で接続されたサーバの記憶装置からダウンロードされた後にインストールされたものであってもよい。

１ モダリティ
２ 画像保管サーバ
３ 画像処理ワークステーション
４ ３次元プリンター
５ ネットワーク
３１ 抽出部
３２ 多重度取得部
３３ 分割位置探索部
３４ 分割部
３５ 出力部
３６ 制御部
Ｖ ボリュームデータ

Claims (15)

1. 複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出部と、
   前記３次元オブジェクトの木構造の前記エッジ上で分割した分割オブジェクトの少なくとも一方の大きさが３次元造形装置の出力範囲に対して最大となる分割候補位置を探索する分割位置探索部と、
   前記分割候補位置のあるエッジ上の分割位置で前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割部と、
   前記分割オブジェクトを前記３次元造形装置に出力する出力部とを備えた３次元オブジェクト分割出力装置。
2. 前記３次元オブジェクトの木構造上の少なくとも１点から前記複数の端点に到達する全ての経路に基づいて、各経路が各エッジを通過する回数をエッジ毎にカウントして得られる多重度を取得する多重度取得部をさらに備え、
   前記分割位置探索部は、前記多重度が最大のエッジから順に、前記分割候補位置を探索する請求項１記載の３次元オブジェクト分割出力装置。
3. 前記分割オブジェクトを除いた前記３次元オブジェクトの木構造に対して、前記分割位置探索部および前記分割部により、新たな分割オブジェクトを繰り返し生成する繰り返し制御部をさらに備えた請求項１または２記載の３次元オブジェクト分割出力装置。
4. 前記分割オブジェクトを除いた前記３次元オブジェクトの木構造に対して、前記多重度取得部、前記分割位置探索部および前記分割部により、新たな分割オブジェクトを繰り返し生成する繰り返し制御部をさらに備えた請求項２記載の３次元オブジェクト分割出力装置。
5. 前記分割位置探索部は、前記分割オブジェクトに含まれる木構造の端点を用いて得られる包絡面による凸包体に外接する外接直方体が、前記出力範囲に対して最大となる分割候補位置を探索する請求項１〜４いずれか１項記載の３次元オブジェクト分割出力装置。
6. 前記外接直方体は、前記凸包体に外接する直方体の体積が最小となる最小直方体である請求項５記載の３次元オブジェクト分割出力装置。
7. 前記出力部は、前記外接直方体の一辺が前記３次元造形装置の出力範囲の直方体の一辺と平行になり、かつ、前記外接直方体が前記出力範囲の直方体に収まる向きに前記分割オブジェクトを回転して出力する請求項５または６項記載の３次元オブジェクト分割出力装置。
8. 前記多重度取得部は、前記３次元オブジェクトの木構造の１つの端点から前記１つの端点以外の他の端点に到達する全ての経路に基づいて、各経路が各エッジを通過する回数をエッジ毎にカウントして得られる多重度を取得する請求項２または４項記載の３次元オブジェクト分割出力装置。
9. 前記多重度取得部は、前記複数の端点のうち特定の１つの端点から前記特定の１つの端点以外の他の端点へ到達する全ての経路、または、前記複数の端点以外の前記３次元オブジェクトの木構造上の特定の１点から前記複数の端点へ到達する全ての経路に基づいて、各経路が前記各エッジを通過する回数をカウントして得られる前記多重度を取得する請求項２または４項記載の３次元オブジェクト分割出力装置。
10. 前記多重度取得部は、前記３次元オブジェクトの木構造の２つの分岐点間を接続するエッジの中から選択された１つのエッジ上の１点で前記木構造を２つに分けた２つの部分木構造に対して、前記選択されたエッジ上の１点から前記部分木構造の端点に到達する全ての経路に基づいて得られる前記多重度をそれぞれ取得し、前記選択されたエッジの多重度を前記２つの部分木構造に対して取得した多重度のうち小さい値の多重度を前記選択されたエッジの多重度とする請求項２または４記載の３次元オブジェクト分割出力装置。
11. 前記多重度取得部は、前記複数の端点のうち１つの端点から前記１つの端点以外の他の端点へ到達する全ての経路に基づいて、各経路が前記各エッジを通過する回数をカウントする処理を、各端点のそれぞれに対して行ってカウントした前記各エッジを通過する回数を全て加算して得られる前記多重度を取得する請求項２または４記載の３次元オブジェクト分割出力装置。
12. 前記分割部は、前記分割オブジェクトが前記出力範囲内の大きさとなり、かつ、前記分割候補位置があるエッジ上で最も太くなる分割位置で分割する請求項１〜１１のいずれか１項記載の３次元オブジェクト分割出力装置。
13. 前記分割位置探索部は、前記２つの分岐点間を接続するいずれかのエッジで分割した時に、前記分割オブジェクトの少なくとも一方が前記出力範囲内の大きさから前記出力範囲を越える大きさに変わるエッジ上の分割候補位置を探索する請求項１〜１２のいずれか１項記載の３次元オブジェクト分割出力装置。
14. 抽出部と分割位置探索部と分割部と出力部とを備えた３次元オブジェクト分割出力装置の作動方法であって、
    前記抽出部が、複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、
    前記分割位置探索部が、前記３次元オブジェクトの木構造の前記エッジ上で分割した分割オブジェクトの少なくとも一方の大きさが３次元造形装置の出力範囲に対して最大となる分割候補位置を探索する分割位置探索ステップと、
    前記分割部が、前記分割候補位置のあるエッジで前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、
    前記出力部が、前記分割オブジェクトを前記３次元造形装置に出力する出力ステップとを備えた３次元オブジェクト分割出力装置の作動方法。
15. コンピュータに、
    複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、
    前記３次元オブジェクトの木構造の前記エッジ上で分割した分割オブジェクトの少なくとも一方の大きさが３次元造形装置の出力範囲に対して最大となる分割候補位置を探索する分割位置探索ステップと、
    前記分割候補位置のあるエッジで前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、
    前記分割オブジェクトを前記３次元造形装置に出力する出力ステップとを実行させるための３次元オブジェクト分割出力プログラム。