(57)【特許請求の範囲】
【請求項１】
複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出部と、
前記複数の端点のうちの１つの端点を第１の端点として決定する第１の端点決定部と、
前記複数の端点のうち前記第１の端点以外の第２の端点から前記第１の端点に向かう経路上に存在するエッジ上の分割位置で、該分割位置から前記第１の端点と反対側に広がる下流側の木構造が３次元造形装置の出力範囲内の大きさから前記出力範囲を超える大きさに変わる分割位置を探索する分割位置探索部と、
前記探索した分割位置で前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割部と、
前記分割オブジェクトを前記３次元造形装置に出力する出力部とを備えた３次元オブジェクト分割出力装置。
【請求項２】
前記分割位置探索部が、前記経路上を前記第２の端点から前記第１の端点に向かって進むときに各分岐点に到着する順に、各分岐点から前記第１の端点と反対側に広がる下流側の木構造が前記出力範囲内の大きさから前記出力範囲を超える大きさになる分岐点を探索し、前記探索された分岐点の手前のエッジ上の分割位置で分割した分割オブジェクトが前記出力範囲内の大きさとなる分割位置を探索する請求項１記載の３次元オブジェクト分割出力装置。
【請求項３】
前記分割位置探索部が、前記第２の端点から前記第１の端点までの経路上の各エッジで、各エッジを接続する２つの分岐点のうちの一方の分岐点から前記第１の端点と反対側に広がる下流側の木構造が前記出力範囲内の大きさであり、かつ、前記２つの分岐点のうちの他方の分岐点から前記第１の端点と反対側に広がる下流側の木構造が前記出力範囲を越える大きさとなるエッジを探索して、該エッジ上の分割位置で分割した分割オブジェクトが前記出力範囲内の大きさとなる分割位置を探索する請求項１記載の３次元オブジェクト分割出力装置。
【請求項４】
前記分割オブジェクトを除いた前記３次元オブジェクトに対して、前記分割位置探索部および前記分割部を用いて新たな分割オブジェクトを繰り返し生成する繰り返し制御部をさらに備えた請求項１〜３いずれか１項記載の３次元オブジェクト分割出力装置。
【請求項５】
前記分割位置探索部は、前記３次元オブジェクトまたは前記分割オブジェクトを除いた前記３次元オブジェクトに含まれる端点のうち前記第１の端点を除いた端点から前記第１の端点までの経路上のエッジの長さの合計が最も長い端点を前記第２の端点として選択する請求項４記載の３次元オブジェクト分割出力装置。
【請求項６】
前記第１の端点を特定の端点とする請求項１〜５のいずれか１項記載の３次元オブジェクト分割出力装置。
【請求項７】
複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトを抽出する抽出部と、
前記複数の端点のうちの１つの端点を第３の端点として選択する第３の端点選択部と、
前記第３の端点から前記木構造の他の端点に向かう際に、前記第３の端点から到着した各分岐点で分岐したエッジのうち各エッジより先につながるエッジの数が最も多いエッジを選択しながら経路を進み、かつ、前記各分岐点から前記経路の進む方向と反対側に広がる下流側にある木構造を選択領域に含める処理を繰り返すことにより選択領域を決定する選択領域決定部と、
前記経路上の各分岐点において、前記選択領域に含まれる木構造が３次元造形装置の出力範囲内の大きさから前記出力範囲を超える大きさになる分岐点を探索し、前記探索された分岐点の手前のエッジ上の分割位置で分割した分割オブジェクトが前記出力範囲内の大きさとなる分割位置を探索する分割位置探索部と、
前記分割位置で前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割部と、
前記分割オブジェクトを前記３次元造形装置に出力する出力部とを備えた３次元オブジェクト分割出力装置。
【請求項８】
前記分割オブジェクトを除いた前記３次元オブジェクトに対して、前記第３の端点選択部と、前記選択領域決定部と、前記分割位置探索部と、前記分割部により、新たな分割オブジェクトを生成する繰り返し制御部をさらに備えた請求項７記載の３次元オブジェクト分割出力装置。
【請求項９】
前記分割位置探索部は、前記出力範囲内の大きさとなり、かつ、前記分割位置で分割したときの３次元オブジェクトの切断面の径が予め定められた大きさより小さいときは前記分割するエッジ上での前記切断面の径が前記予め定められた大きさより大きいところで分割位置を探索する請求項１〜８いずれか１項記載の３次元オブジェクト分割出力装置。
【請求項１０】
抽出部と第１の端点決定部と分割位置探索部と分割部と出力部とを備えた３次元オブジェクト分割出力装置の作動方法であって、
前記抽出部が、複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、
前記端点決定部が、前記複数の端点のうちの１つの端点を第１の端点として決定する第１の端点決定ステップと、
前記分割位置探索部が、前記複数の端点のうち前記第１の端点以外の第２の端点から前記第１の端点に向かう経路上に存在するエッジ上の分割位置で、該分割位置から前記第１の端点と反対側に広がる下流側の木構造が３次元造形装置の出力範囲内の大きさから前記出力範囲を超える大きさに変わる分割位置を探索する分割位置探索ステップと、
前記分割部が、前記探索した分割位置で前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、
前記出力部が、前記分割オブジェクトを前記３次元造形装置に出力する出力ステップとを備えた３次元オブジェクト分割出力装置の作動方法。
【請求項１１】
コンピュータに、
複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、
前記複数の端点のうちの１つの端点を第１の端点として決定する第１の端点決定ステップと、
前記複数の端点のうち前記第１の端点以外の第２の端点から前記第１の端点に向かう経路上に存在するエッジ上の分割位置で、該分割位置から前記第１の端点と反対側に広がる下流側の木構造が３次元造形装置の出力範囲内の大きさから前記出力範囲を超える大きさに変わる分割位置を探索する分割位置探索ステップと、
前記探索した分割位置で前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、
前記分割オブジェクトを前記３次元造形装置に出力する出力ステップとを実行させるための３次元オブジェクト分割出力プログラム。
【請求項１２】
抽出部と第３の端点選択部と選択領域決定部と分割位置探索部と分割部と出力部とを備えた３次元オブジェクト分割出力装置の動作方法であって、
前記抽出部が、複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、
前記第３の端点選択部が、前記複数の端点のうちの１つの端点を第３の端点として選択する第３の端点選択ステップと、
前記選択領域決定部が、前記第３の端点から前記木構造の他の端点に向かう際に、前記第３の端点から到着した各分岐点で分岐したエッジのうち各エッジより先につながる木構造に含まれるエッジまたは分岐点の数が最も多いエッジを選択しながら経路を進み、かつ、前記各分岐点から経路の進む方向と反対側に広がる下流側にある木構造を選択領域に含める処理を繰り返すことにより選択領域を決定する選択領域決定ステップと、
前記分割位置探索部が、前記経路上の各分岐点において、前記選択領域に含まれる木構造が３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさになる分岐点を探索し、前記探索された分岐点の手前のエッジ上の分割位置で分割した分割オブジェクトが前記出力範囲内の大きさとなる分割位置を探索する分割位置探索ステップと、
前記分割部が、前記分割位置で前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、
前記出力部が、前記分割オブジェクトを前記３次元造形装置に出力する出力ステップとを備えた３次元オブジェクト分割出力装置の動作方法。
【請求項１３】
コンピュータに、
複数の端点および分岐点と、前記端点と前記分岐点間を接続するエッジと、２つの前記分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、
前記複数の端点のうちの１つの端点を第３の端点として選択する第３の端点選択ステップと、
前記第３の端点から前記木構造の他の端点に向かう際に、前記第３の端点から到着した各分岐点で分岐したエッジのうち各エッジより先につながる木構造に含まれるエッジまたは分岐点の数が最も多いエッジを選択しながら経路を進み、かつ、前記各分岐点から経路の進む方向と反対側に広がる下流側にある木構造を選択領域に含める処理を繰り返すことにより選択領域を決定する選択領域決定ステップと、
前記経路上の各分岐点において、前記選択領域に含まれる木構造が３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさになる分岐点を探索し、前記探索された分岐点の手前のエッジ上の分割位置で分割した分割オブジェクトが前記出力範囲内の大きさとなる分割位置を探索する分割位置探索ステップと、
前記分割位置で前記３次元オブジェクトを前記出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、
前記分割オブジェクトを前記３次元造形装置に出力する出力ステップとを実行させるための３次元オブジェクト分割出力プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造のオブジェクトを３次元造形装置に出力する際に、３次元造形装置の出力範囲に収まるようにオブジェクトを分割して出力する３次元オブジェクト分割出力装置およびその応用に関するものである。
【背景技術】
【０００２】
近年、ＣＴ（Computed Tomography）装置やＭＲＩ（Magnetic Resonance Imaging）装置などで取得された断層画像を基に、患者個人の血管や臓器の３次元模型を作製して、診断や手術の術式の検討などに役立てようとする試みが行われている。
【０００３】
例えば、特許文献１には、ＣＴ装置やＭＲＩ装置などで撮影された患者個人の断層画像データから目的の部位のデータを抽出して、抽出された断層画像データから模型造形用の断層データを作成したものを用いて、粉体を積層して精密粉体模型を作製した上で精密粉体模型を鋳型として透明または半透明のシリコンなど柔軟性を持つポリマーで血管や臓器を患者ごとに作製する手法が開示されている。
【０００４】
さらに、特許文献２には、３次元ボリュームデータから肝臓領域および肝動脈、肝静脈等の構造物を抽出し、これら構造物のサーフェスデータを生成し、構造物のサーフェスデータを合成して、立体モデルデータを生成した上で、立体モデルを等高面で分けた断面データを用いて３次元プリンターで製造する手法が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００３−２４１６４７号公報
【特許文献２】特開２０１３−２２２３６１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
３次元プリンターなどの造形装置で高解像度の大きなオブジェクトを出力する場合、オブジェクトの大きさに対応する大規模な３次元プリンターが必要になる。しかし、大規模な３次元プリンターは非常に高価であるため、実際にはオブジェクトをいくつかに小さく分割し、小規模な３次元プリンターでそれぞれ出力し、後で接合することにより大きなオブジェクトの全体を製造している。
【０００７】
また、分割出力する場合、オブジェクトが塊になっている場合はどのように分割しても大した問題にはならないが、血管や気管支のように木構造のオブジェクトの場合、３次元プリンターで出力可能な範囲を表す直方体の形状に当てはめて単純に分割すると、末端の枝の部分が切り取られて小さい枝に分かれてバラバラになってしまい、後に各パーツを組み立てる上で、接合する箇所が増えてしまうため、現実的な分割手法とはいえない。
【０００８】
例えば、木構造である気管支を３次元プリンターで出力する場合、解剖学的には葉間膜を横断する箇所でオブジェクトを分割するのが、少ない接合回数で、より大きなオブジェクトを出力するのに好適である。しかし、葉間膜部分でオブジェクトを分割した場合であっても、３次元プリンターの出力範囲を越えることがある。
【０００９】
このように、血管や気管支のような木構造のオブジェクトを小規模な３次元プリンターで出力するときに小さい断片にならないようにオブジェクトを分割する分割方法が重要になる。
【００１０】
本発明は上記事情に鑑みてなされたものであり、３次元プリンターで出力するときに小さい断片にならないように３次元のオブジェクトを分割して３次元造形装置に出力する３次元オブジェクト分割出力装置およびその応用を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の３次元オブジェクト分割出力装置は、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出部と、複数の端点のうちの１つの端点を第１の端点として決定する第１の端点決定部と、複数の端点のうち第１の端点以外の第２の端点から第１の端点に向かう経路上に存在するエッジ上の分割位置で、分割位置から第１の端点と反対側に広がる下流側の木構造が３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさに変わる分割位置を探索する分割位置探索部と分割位置探索部と、探索した分割位置で３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割部と、分割オブジェクトを３次元造形装置に出力する出力部とを備えたものである。
【００１２】
また、本発明の３次元オブジェクト分割出力装置の作動方法は、抽出部と第１の端点決定部と分割位置探索部と分割部と出力部とを備えた３次元オブジェクト分割出力装置の作動方法であって、抽出部が、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、端点決定部が、複数の端点のうちの１つの端点を第１の端点として決定する第１の端点決定ステップと、分割位置探索部が、複数の端点のうち第１の端点以外の第２の端点から第１の端点に向かう経路上に存在するエッジ上の分割位置で、分割位置から第１の端点と反対側に広がる下流側の木構造が３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさに変わる分割位置を探索する分割位置探索ステップと、分割部が、探索した分割位置で３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、出力部が、分割位置分割オブジェクトを３次元造形装置に出力する出力ステップとを備えたものである。
【００１３】
さらに、本発明の３次元オブジェクト分割出力プログラムは、コンピュータに、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、複数の端点のうちの１つの端点を第１の端点として決定する第１の端点決定ステップと、複数の端点のうち第１の端点以外の第２の端点から第１の端点に向かう経路上に存在するエッジ上の分割位置で、分割位置から第１の端点と反対側に広がる下流側の木構造が３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさに変わる分割位置を探索する分割位置探索ステップと、探索した分割位置で３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、分割オブジェクトを３次元造形装置に出力する出力ステップとを実行させるためのものである。
【００１４】
「木構造」とは、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成され、分岐点でエッジが分かれた階層構造をもつものをいい、具体的に、「木構造を持つ３次元オブジェクト」には、気管支や血管などがあげられる。
【００１５】
「３次元造形装置の出力範囲」とは、３次元造形装置でオブジェクトが出力可能な最大の高さ、幅、奥行きで表されるものであり、「分割オブジェクトの大きさが３次元造形装置の出力範囲を越える」とは、分割オブジェクトの高さ、幅、奥行きの少なくとも１つが３次元造形装置の出力範囲の最大の大きさを越えたものをいう。
【００１６】
分割位置探索部が、経路上を第２の端点から第１の端点に向かって進むときに各分岐点に到着する順に、各分岐点から第１の端点と反対側に広がる下流側の木構造が出力範囲内の大きさから出力範囲を超える大きさになる分岐点を探索し、探索された分岐点の手前のエッジ上の分割位置で分割した分割オブジェクトが出力範囲内の大きさとなる分割位置を探索するものであってもよい。
【００１７】
分割位置探索部が、第２の端点から第１の端点までの経路上の各エッジで、各エッジを接続する２つの分岐点のうちの一方の分岐点から第１の端点と反対側に広がる下流側の木構造が出力範囲内の大きさであり、かつ、２つの分岐点のうちの他方の分岐点から第１の端点と反対側に広がる下流側の木構造が出力範囲を越える大きさとなるエッジを探索して、このエッジ上の分割位置で分割した分割オブジェクトが出力範囲内の大きさとなる分割位置を探索するものであってもよい。
【００１８】
また、分割オブジェクトを除いた３次元オブジェクトに対して、分割位置探索部および分割部を用いて新たな分割オブジェクトを繰り返し生成する繰り返し制御部をさらに備えるものが望ましい。
【００１９】
分割位置探索部は、３次元オブジェクトまたは分割オブジェクトを除いた３次元オブジェクトに含まれる端点のうち第１の端点を除いた端点から第１の端点までの経路上のエッジの長さの合計が最も長い端点を第２の端点として選択するものが望ましい。
【００２０】
第１の端点は、特定の端点であってもよい。
【００２１】
「特定の端点」は、例えば、木構造の根となる端点であってもよい。
【００２２】
本発明の他の３次元オブジェクト分割出力装置は、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトを抽出する抽出部と、複数の端点のうちの１つの端点を第３の端点として選択する第３の端点選択部と、第３の端点から木構造の他の端点に向かう際に、第３の端点から到着した各分岐点で分岐したエッジのうち各エッジより先につながるエッジの数が最も多いエッジを選択しながら経路を進み、かつ、各分岐点から経路の進む方向と反対側に広がる下流側にある木構造を選択領域に含める処理を繰り返すことにより選択領域を決定する選択領域決定部と、経路上の各分岐点において、選択領域に含まれる木構造が３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさになる分岐点を探索し、探索された分岐点の手前のエッジ上の分割位置で分割した分割オブジェクトが出力範囲内の大きさとなる分割位置を探索する分割位置探索部と、分割位置で３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割部と、分割オブジェクトを３次元造形装置に出力する出力部とを備えたものである。
【００２３】
また、本発明の他の３次元オブジェクト分割出力装置の作動方法は、抽出部と第３の端点選択部と選択領域決定部と分割位置探索部と分割部と出力部とを備えた３次元オブジェクト分割出力装置の動作方法であって、抽出部が、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、第３の端点選択部が、複数の端点のうちの１つの端点を第３の端点として選択する第３の端点選択ステップと、選択領域決定部が、第３の端点から木構造の他の端点に向かう際に、第３の端点から到着した各分岐点で分岐したエッジのうち各エッジより先につながる木構造に含まれるエッジまたは分岐点の数が最も多いエッジを選択しながら経路を進み、かつ、各分岐点から経路の進む方向と反対側に広がる下流側にある木構造を選択領域に含める処理を繰り返すことにより選択領域を決定する選択領域決定ステップ、分割位置探索部が、経路上の各分岐点において、選択領域に含まれる木構造が３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさになる分岐点を探索し、探索された分岐点の手前のエッジ上の分割位置で分割した分割オブジェクトが出力範囲内の大きさとなる分割位置を探索する分割位置探索ステップと、分割部が、分割位置で３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、出力部が、分割オブジェクトを３次元造形装置に出力する出力ステップとを備えたものである。
【００２４】
さらに、本発明の他の３次元オブジェクト分割出力プログラムは、コンピュータに、複数の端点および分岐点と、端点と分岐点間を接続するエッジと、２つの分岐点間を接続するエッジとで構成される木構造を持つ３次元オブジェクトをボリュームデータから抽出する抽出ステップと、複数の端点のうちの１つの端点を第３の端点として選択する第３の端点選択ステップと、第３の端点から木構造の他の端点に向かう際に、第３の端点から到着した各分岐点で分岐したエッジのうち各エッジより先につながる木構造に含まれるエッジまたは分岐点の数が最も多いエッジを選択しながら経路を進み、かつ、各分岐点から経路の進む方向と反対側に広がる下流側にある木構造を選択領域に含める処理を繰り返すことにより選択領域を決定する選択領域決定ステップと、経路上の各分岐点において、選択領域に含まれる木構造が３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさになる分岐点を探索し、探索された分岐点の手前のエッジ上の分割位置で分割した分割オブジェクトが出力範囲内の大きさとなる分割位置を探索する分割位置探索ステップと、分割位置で３次元オブジェクトを出力範囲内の大きさとなる分割オブジェクトに分割する分割ステップと、分割オブジェクトを３次元造形装置に出力する出力ステップとを実行させるためのものである。
【００２５】
また、分割オブジェクトを除いた３次元オブジェクトに対して、第３の端点選択部と、選択領域決定部と、分割位置探索部と、分割部により、新たな分割オブジェクトを生成する繰り返し制御部をさらに備えたものが望ましい。
【００２６】
分割位置探索部は、出力範囲内の大きさとなり、かつ、分割位置で分割したときの３次元オブジェクトの切断面の径が予め定められた大きさより小さいときは分割するエッジ上での切断面の径が予め定められた大きさより大きいところを探索して分割位置を探索するものが望ましい。
【発明の効果】
【００２７】
本発明によれば、３次元オブジェクトの木構造の複数の端点のうちの１つの端点から他の端点に向かって経路を辿り、３次元造形装置の出力範囲内の大きさから出力範囲を超える大きさになる分岐点を探索し、探索された分岐点の手前のエッジ上で３次元オブジェクトを分割した分割オブジェクトを生成して３次元造形装置に出力することにより、３次元オブジェクトが小さい断片にならないように分割して、なるべく少ない回数で３次元プリンターに出力することが可能になり、分割した３次元オブジェクトを組み立てる上で、接合する箇所を少なくすることできる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施形態による３次元オブジェクト分割出力装置を適用した立体モデル製造システムの概略構成を示す図
【図２】本発明の第１の実施形態による３次元オブジェクト分割出力部の機能ブロック図
【図３】本発明の第１の実施形態による立体モデル製造システムの処理の流れを示すフローチャート
【図４】木構造の一例
【図５】木構造の複数の端点の中から根以外の端点の選択を説明するための図
【図６Ａ】第２の端点から辿って選択領域を選択する手法を説明するための図（その１）
【図６Ｂ】第２の端点から辿って選択領域を選択する手法を説明するための図（その２）
【図６Ｃ】第２の端点から辿って選択領域を選択する手法を説明するための図（その３）
【図７】木構造を分割していく様子を示す図
【図８】本発明の第２の実施形態による３次元オブジェクト分割出力部の機能ブロック図
【図９】本発明の第２の実施形態による立体モデル製造システムの処理の流れを示すフローチャート
【図１０】第３の端点の選択を説明するための図
【図１１Ａ】本発明の第２の実施形態で経路を選択する方法を説明するための図（その１）
【図１１Ｂ】本発明の第２の実施形態で経路を選択する方法を説明するための図（その２）
【図１１Ｃ】本発明の第２の実施形態で経路を選択する方法を説明するための図（その３）
【発明を実施するための形態】
【００２９】
本発明の３次元オブジェクト分割出力装置の実施形態について、図に基づいて説明する。図１は、３次元オブジェクト分割出力装置を設けた立体モデル製造システムの概要を示すハードウェア構成図である。図に示すように、このシステムでは、モダリティ１と、画像保管サーバ２と、画像処理ワークステーション３と、３次元造形装置４が、ネットワーク５を経由して通信可能な状態で接続されている。
【００３０】
モダリティ１には、患者の対象部位を撮影することにより、その部位を表す３次元医用画像の画像データを生成し、その画像データにＤＩＣＯＭ（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を選ぶ（#3）。根Rootから端点E1までの経路は図５の太線で示すように一意に決まる。この経路上で端点E1から根Rootまで経路を遡って、３次元プリンター４の出力範囲を越える位置を探索する（#4）。第２の端点E1は、３次元オブジェクトに含まれる端点のうち根以外の端点から根までの経路上のエッジの長さの合計が最も長い端点を選択するのが望ましい。
【００４６】
第２の端点E1から経路を辿って最初の分岐点B１に到着すると、その分岐点B1より下流側の２つのエッジを選択領域（図６Ａの枠）に加える。選択領域が、３次元プリンター４の出力範囲を越えていない場合には分岐点B2まで進む。分岐点B2でも同様に、分岐点B2より下流側の木構造を全て選択領域に加える（図６Ｂの枠）。選択領域が、３次元プリンター４の出力範囲を越えていない場合には、さらに分岐点B3まで進み、分岐点B3より下流側の木構造を全て選択領域に加える（図６Ｃの枠）。分岐点B3で３次元プリンター４の出力範囲を越える場合は、B2からB3に到着するエッジの途中に３次元プリンター４の出力範囲を越える点Ｐを設定し、点Ｐを分割位置とする。
【００４７】
３次元プリンター４の出力範囲を越えるか否かの判定は、選択領域の高さ、幅、奥行きの全てが３次元プリンター４の出力範囲の最大の高さ、幅、奥行き以下であるかを判定することにより行う。つまり、点Ｐより下流側の木構造の高さ、幅、奥行きが、３次元プリンター４の出力範囲の最大の高さ、幅、奥行き以下になる点Ｐが分割位置になる。
【００４８】
具体的には、あるエッジで分割した分割オブジェクトに含まれる木構造の端点に対して凸包を計算するアルゴリズムを適用して、包絡面による凸包体を求めて、この凸包体が３次元プリンター４の出力範囲に収まる大きさであるか否かについて判定する。３次元プリンター４の出力範囲は直方体で定義されるので、分割オブジェクトを包む凸包体に外接する外接直方体を取得して、外接直方体の３辺（縦、横、高さ）と３次元プリンター４の出力範囲の直方体とを比較することで、３次元プリンター４の出力範囲に収まるか否かを判定することができる。３次元オブジェクトをなるべく少ない数に分割するために、外接直方体が出力範囲に対して最大になるか否かについて判定する。つまり、外接直方体の高さ、幅、奥行きの全てが３次元プリンター４の出力範囲の最大の高さ、幅、奥行き以下であって、外接直方体の高さ、幅、奥行きのうちの少なくとも1つが３次元プリンター４の出力範囲の最大の大きさになるものを見つけるようにする。
【００４９】
また、凸包体に外接する直方体は多数見つけることができるが、外接する直方体のうち体積が最小になる最小直方体が３次元プリンター４の出力範囲に収まるか否かを判定する。これにより、３次元オブジェクトをより少ない数に分割して、３次元プリンター４に少ない出力回数で効率よく３次元オブジェクト全体を出力することが可能になる。
【００５０】
あるいは、３次元プリンター４の出力範囲を越えるか否かの判定は、木構造を傾けたときの高さ、幅、奥行きが、３次元プリンター４の出力範囲内の大きさになるものであってもよく、端点E1から出来るだけ経路を遡った分割位置を捜すようにする。このように、端点E1から出来るだけ経路を遡った分割位置を捜すことにより、３次元オブジェクトを分割する分割回数を少なくすることができる。
【００５１】
さらに、分割位置探索部３３は、出力範囲内の大きさとなり、かつ、分割位置で分割したときの３次元オブジェクトの切断面の径が所定の大きさより小さいときは、分割するエッジ上での切断面の径が所定の大きさより大きいところを探索して分割位置とする。気管支のようなオブジェクトを分割した場合、分割オブジェクトを後で結合するためには、なるべく気管支が太いところで分割した方が良い。気管支の気道に該当する位置にあるエッジの端点を根とした場合には、通常、根に向かうに従って気管支は太くなるので、上述のように気管支の末端から遡って３次元プリンター４の出力範囲に収まる大きさになる点Ｐがそのまま分割位置になる可能性が高い。木構造を持つ３次元オブジェクトが血管である場合には、根となる端点の選び方によっては探索した分割位置の径が細い場合があるので、径が所定の大きさより小さい場合には、分割位置のあるエッジの中で径が所定の大きさより大きいところや、分割位置のあるエッジの中の最も径が大きいところを分割位置とするのが望ましい。図６Ｃの例では、分岐点B2から点Ｐの間で分割位置を探索する。
【００５２】
分割部３４で、分割位置で３次元オブジェクトを２つに分割して、２つのうち出力範囲内の大きさとなる方を分割オブジェクトとして分割する(#5)。
【００５３】
出力部３５は、生成された分割オブジェクトを３次元プリンター４に出力する(#6)。具体的には、分割オブジェクトを等高面で分けた断面データを生成して、３次元プリンター４に出力する。そのままの状態では３次元プリンター４の出力範囲に収まらない分割オブジェクトは、分割オブジェクトを３次元プリンター４の出力範囲に収まるように傾けた状態にして、等高面で分けた断面データを生成する。
【００５４】
分割オブジェクトを出力後、出力した分割オブジェクトを除いた残りの３次元オブジェクトが３次元プリンター４の出力範囲を越える場合には再度分割する（#7-NO）。
【００５５】
そこで、繰り返し制御部３６は、#3に処理を戻して、再度、分割位置探索部３３で分割位置を探索する。まず、分割位置探索部３３は、分割オブジェクトを除いた３次元オブジェクトに含まれる根以外の端点の中から１つの端点を選び、第２の端点E1とする(#3)。第２の端点E1は、分割オブジェクトを除いた３次元オブジェクトに含まれる端点のうち端点から根までの経路上のエッジの長さの合計が最も長い端点を選択するのが望ましい。
【００５６】
この第２の端点E1と根Rootの経路を遡って分割位置を探索して（#4）、３次元オブジェクトを分割して分割オブジェクトを生成し（#5）、分割オブジェクトを３次元プリンター４に出力する(#6)処理を、出力した分割オブジェクトを除いた残りの３次元オブジェクトが３次元プリンター４の出力範囲に収まるようになるまで繰り返す。出力した分割オブジェクトを除いた残り３次元オブジェクトが３次元プリンター４の出力範囲になると（#7-YES）、３次元プリンター４が残りの３次元オブジェクトを出力して終了する(#8)。
【００５７】
図７に、木構造を分割していく様子を示す。図７では、木構造の左側の下の端点から分割位置を探索して分割オブジェクトを作成し(図７の一番左のａの図の枠の部分)、次に、木構造の右側の下の端点から分割位置を探索して分割オブジェクトを作成し(図７の左から２番目のｂの図の枠の部分)、さらに、残っている木構造の左側の下の端点から分割位置を探索して分割オブジェクトを作成し(図７の左から３番目のｃの図の枠の部分)、最後に、残っている木構造の右側の下の端点から分割位置を探索して分割オブジェクトを作成している（図７の一番右のｄの図の枠の部分）。
【００５８】
上述では、分割位置探索部３３が、第２の端点から根に向かう経路上で、第２の端点から根まで遡るときに順に到達する分岐点について、各分岐点から下流側の木構造が出力範囲内の大きさになる分岐点を捜す場合について説明したが、分割位置探索部３３が、端点から根までの経路上の各エッジに対して、順番を問わず総当たりで、各エッジを接続する２つの分岐点のうちの一方の分岐点から下流側の木構造が出力範囲内の大きさであり、かつ、２つの分岐点のうちの他方の分岐点から下流側の木構造が出力範囲を越える大きさとなるエッジを探索して、そのエッジ上で分割位置を探索するようにしてもよい。あるいは、根から第２の端点に向かう時に到達する分岐点の順に、各分岐点から下流側の木構造が出力範囲内の大きさになる分岐点を捜すようにしてもよい。
【００５９】
上述では、第１の端点が根である場合について説明したが、木構造の端点のうち特定の端点を１つ選択すればよい。
【００６０】
次に、本発明の第２の実施形態となる３次元オブジェクト分割出力部について説明する。第２の実施の形態では、根のような特定の端点に向かう経路上で３次元オブジェクトの分割位置を探すのではなく、各分岐点で進む経路を決めながら分割位置を探索する場合について説明する。立体モデル製造システムの概要は第１の実施形態と同一である。
【００６１】
図８は、画像処理ワークステーション３の機能のうち、本発明の第２の実施形態となる３次元オブジェクト分割出力部を示すブロック図であり、図９は処理の流れを示すフローチャートである。図８に示すように、本発明の第２の実施形態における３次元オブジェクト分割出力処理部は、抽出部３１、第３の端点選択部３７、選択領域決定部３８、分割位置探索部３３ａ、分割部３４、出力部３５、繰り返し制御部３６ａによって実現される。抽出部３１は第１の実施形態と同一であるので詳細な説明は省略する。
【００６２】
以下、図８および図９に従って、第２の実施形態の３次元オブジェクト分割出力部について詳細に説明する。
【００６３】
最初に、画像処理ワークステーション３は、立体モデルを作製する患者のボリュームデータＶを画像保管サーバ２から検索して受け取る。受け取ったボリュームデータＶに対して、抽出部３１を用いて患者の気管支の構造を抽出する（#11）。
【００６４】
次に、図１０に示すように、第３の端点選択部３７で、３次元オブジェクトの複数の端点のうちの１つの端点を第３の端点E2として選択する（#12）。
【００６５】
選択領域決定部３８は、第３の端点E2から開始して、到着する各分岐点で、分岐点から分岐したエッジのうち、各エッジより先につながるエッジの数が最も多いエッジを経路として選択しながら進み、３次元プリンター４の出力範囲を越える位置を探索する（#13）。第２の実施形態では、上流側は、１つの分岐点から経路の進行方向に向かう木構造の部分をさし、下流側は、１つの分岐点から経路の進行方向とは反対側に向かう木構造の部分をさすものとして説明する。
【００６６】
まず、図１１Ａに示すように、選択領域決定部３８は、最初に到着する分岐点B1で、分岐点B1から分岐する2つのエッジの、分岐点B1と端点E3間のエッジと、分岐点B1と分岐点B2間のエッジでは、分岐点B1と端点E3間のエッジより、分岐点B1と分岐点B2間のエッジにつながるエッジの数（１６本）の方が多いので（図１１Ａの右上の図）、分岐点B1と分岐点B2間のエッジを経路として選択し、エッジが１つしかない分岐点B1と端点E3間のエッジは経路として選択しない（図１１Ａの右下の図）。また、分岐点B1より下流側にあるエッジは選択領域に含める（図１１Ａの左の図の枠）。
【００６７】
分割位置探索部３３ａは、選択領域が、経路上の各分岐点において、選択領域に含まれる木構造が３次元プリンター４の出力範囲内の大きさから３次元プリンター４の出力範囲を超える大きさになる分岐点を探索する。３次元プリンター４の出力範囲を越えるか否かの判定は、第１の実施形態と同様に行い、選択領域の高さ、幅、奥行きの全てが３次元プリンター４の出力範囲の最大の高さ、幅、奥行き以下であるかを判定することにより行う。そこで、分岐点B1より下流側の選択領域が３次元プリンター４の出力範囲内の大きさを越えるか否かを判定して、越えない場合は次の分岐点B2に進む。
【００６８】
次に、図１１Ｂに示すように、選択領域決定部３８は、分岐点B2から分岐する2つのエッジの、分岐点B2と端点E4間のエッジと、分岐点B2と分岐点B3間のエッジでは、分岐点B2と端点E4間のエッジより、分岐点B2と分岐点B3間のエッジの先につながるエッジの数（１３本）の方が多いので（図１１Ｂの右上の図）、分岐点B2と分岐点B3間のエッジを経路として選択し、エッジが１つしかない分岐点B2と端点E4間のエッジは経路として選択しない（図１１Ｂの右下の図）。また、分岐点B2より下流側にあるエッジは選択領域に含める（図１１Ｂの左の図の枠）。
【００６９】
分割位置探索部３３ａは、分岐点B2より下流側の選択領域が３次元プリンター４の出力範囲内の大きさを越えるか否かを判定して、越えない場合は次の分岐点B3に進む。
【００７０】
さらに、図１１Ｃに示すように、選択領域決定部３８は、分岐点B3から分岐する2つのエッジの、分岐点B3と分岐点B4間のエッジと、分岐点B3と分岐点B5間のエッジでは、分岐点B3と分岐点B4間のエッジにつながるエッジの数が７本であり（図１１Ｃの右上の図）、分岐点B3と分岐点B5間のエッジにつながるエッジの数は５本であるので（図１１Ｃの右下の図）、エッジの数が多い分岐点B3と分岐点B4間のエッジを経路として選択し、つながるエッジの数が少ない分岐点B3と分岐点B5間のエッジは経路として選択しない。また、分岐点B3より下流側にある木構造の部分は選択領域に含める（図１１Ｃの左の図の枠）。
【００７１】
以上のように経路を進めていき、分岐点B4で分割オブジェクトが出力範囲内の大きさを超える場合には、分岐点B4の手前の分岐点B3と分岐点B4間のエッジ上で分割した分割オブジェクトが出力範囲内の大きさとなる分割位置を探索する。第１の実施形態と同様に、３次元プリンター４の出力範囲の最大の高さ、幅、奥行き以下になる点Ｐを探索する。
【００７２】
以下、第１の実施形態と同様に、分割部３４で、分割位置で３次元オブジェクトを２つに分割して、２つのうち出力範囲内の大きさとなる方を分割オブジェクトとして分割し (#14)、出力部３５は、生成された分割オブジェクトを３次元プリンター４に出力する(#5)。
【００７３】
分割オブジェクトを出力後、出力した分割オブジェクトを除いた残りの３次元オブジェクトが３次元プリンター４の出力範囲を越える場合には再度分割する（#16-NO）。
【００７４】
そこで、繰り返し制御部３６ａは、#12に処理を戻して、再度、分割位置探索部３３aで別の第３の端点E2を選択して（#12）分割位置を探索する。この第３の端点E2から上述のように経路を遡って分割位置を探索して（#13）、３次元オブジェクトを分割して分割オブジェクトを生成し（#14）、分割オブジェクトを３次元プリンター４に出力する(#15)処理を、出力した分割オブジェクトを除いた残りの３次元オブジェクトが３次元プリンター４の出力範囲に収まるようになるまで繰り返す。出力した分割オブジェクトを除いた残り３次元オブジェクトが３次元プリンター４の出力範囲になると（#16-YES）、３次元プリンター４が残りの３次元オブジェクトを出力して終了する(#17)。
【００７５】
第１および第２の実施形態の出力部３５では、単純に３次元オブジェクトを分割した分割オブジェクトを出力する場合について説明したが、分割オブジェクトに切断した切断面を結合することができるように、分割した両方の切断面に嵌め込み可能な形状の接続部を設けた上で３次元プリンター４に出力するのが望ましい。
【００７６】
気管支や血管をエッジ（枝）で分割した切断面は円に近い形状になるが、接続部に円形の接続部を設けると、接続したときに枝が回転して本来の枝が接続されるべき向きとは違う向きに接続される場合がある。そこで、接続部の形状は、不等辺三角形や台形など形状にして嵌め込む向きが一意に決まる様な形状にするのが望ましい。さらに、複数の分割オブジェクトに分割したときには、接続部を間違えて結合することがないように、それぞれ接続部の形状を異なる形状あるいは異なる大きさにするのが望ましい。
【００７７】
なお、本実施形態に限定されず、３次元オブジェクト分割出力部の一部または全部は、1台のコンピュータにより実行されるものであってもよく、ネットワークを介して接続された一台以上のコンピュータ、サーバ、記憶装置によって構成されたもので実行されるものであってもよい。なお、各機器は、ＣＤ−ＲＯＭ等の記録媒体からインストールされた本明細書の３次元オブジェクト分割出力部のプログラムによって制御される。また、プログラムは、インターネット等のネットワーク経由で接続されたサーバの記憶装置からダウンロードされた後にインストールされたものであってもよい。
【符号の説明】
【００７８】
１    モダリティ
２    画像保管サーバ
３    画像処理ワークステーション
４    ３次元プリンター
５    ネットワーク
３１  抽出部
３２  端点決定部
３３、３３a 分割位置探索部
３４  分割部
３５  出力部
３６、３６ａ       制御部
３７  第３の端点選択部
３８  選択領域決定部
Ｖ    ボリュームデータ
【図１】
0006053736.tif 000002
【図２】
0006053736.tif 000003
【図３】
0006053736.tif 000004
【図４】
0006053736.tif 000005
【図５】
0006053736.tif 000006
【図６Ａ】
0006053736.tif 000007
【図６Ｂ】
0006053736.tif 000008
【図６Ｃ】
0006053736.tif 000009
【図７】
0006053736.tif 000010
【図８】
0006053736.tif 000011
【図９】
0006053736.tif 000012
【図１０】
0006053736.tif 000013
【図１１Ａ】
0006053736.tif 000014
【図１１Ｂ】
0006053736.tif 000015
【図１１Ｃ】
0006053736.tif 000016