(57)【要約】輪郭線を有する物体の表面形状を再構築するための方法および器具には、各々の輪郭線に対し点を割当てる段階が含まれる。第一の三角形分割スキームを、近接して位置している2本の輪郭線上のそれぞれの点に対して実施し、2本の輪郭線に対応する物体の一部分についての第一の表面形状を決定する。第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定する。第一の表面形状が間違っていない場合、物体の該部分についての再構築された表面形状として、第一の三角形分割スキームにより決定されたように物体の該部分について第一の表面形状を出力する。第一の表面形状が間違っている場合、2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施して、物体の該部分についての第二の表面形状を決定し、再構築された表面形状として、第二の三角形分割スキームによって決定されたように物体の該部分についての第二の表面形状を出力する。2009535693.tif 000005
2009535693.tif 000002
【特許請求の範囲】
【請求項１】
複数の輪郭線から物体の表面形状を再構築する方法であって、以下の段階を含む方法：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の一部分について第一の表面形状を決定する段階；
第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定する段階；
第一の表面形状が間違っていない場合、物体の該部分について再構築された表面形状として、第一の三角形分割スキームにより決定されたように物体の該部分についての第一の表面形状を出力する段階；ならびに
第一の表面形状が間違っている場合、
近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の該部分についての第二の表面形状を決定する段階；および
物体の該部分についての再構築された表面形状として、第二の三角形分割スキームによって決定されたように物体の該部分についての第二の表面形状を出力する段階。
【請求項２】
第一の三角形分割スキームが最短距離スキームであり、第二の三角形分割スキームが最近接方位スキームである、請求項1記載の方法。
【請求項３】
スキャンする段階が物体のCTスキャンを実施することにより達成される、請求項1記載の方法。
【請求項４】
物体が患者の骨構造を含む、請求項1記載の方法。
【請求項５】
物体の完全に再構築された表面形状を得るため、複数の輪郭線のうち近接して位置している2本の輪郭線各々の上のそれぞれの点に対して第一の三角形分割スキームか第二の三角形分割スキームのうちのいずれかまたは両方を実施する段階をさらに含む、請求項1記載の方法。
【請求項６】
第一の三角形分割スキームおよび第二の三角形分割スキームのうちの一方が、以下の段階を含む最短距離三角形分割スキームを含む、請求項1記載の方法：
a) 第一の輪郭線上の各点について、第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
e) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜d)を反復する段階。
【請求項７】
第一の三角形分割スキームおよび第二の三角形分割スキームのうちの一つが、以下の段階を含む最近接方位三角形分割スキームを含む、請求項1記載の方法：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a)およびb)を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項８】
第一の三角形分割スキームおよび第二の三角形分割スキームのうちの他方の三角形分割スキームが、以下の段階を含む最近接方位三角形分割スキームを含む、請求項6記載の方法：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点について最近接方位が決定されるまで段階a)およびb)を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として、第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項９】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項1記載の方法。
【請求項１０】
それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角形分割された輪郭の上面および底面輪郭を閉じる段階をさらに含む、請求項9記載の方法。
【請求項１１】
チェック段階が以下の段階を含む、請求項1記載の方法：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 該第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；
e) 第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックする段階であって、方位が90度より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；方位が第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が90度超の方位に対応する段階；ならびに
f) 第一および第二の輪郭線上の全ての点が、第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜e)を反復する段階。
【請求項１２】
以下の段階を含む、複数の輪郭線から物体の表面形状を再構築する方法：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
第一および第二の輪郭線に対応する近接して位置している2本の輪郭線上のそれぞれの点に対して最短距離三角形分割スキームを実施し、第一および第二の輪郭線に対応する物体の一部分についての第一の表面形状を決定する段階であって、該最短距離三角形分割スキームが以下の段階を含む、方法：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 該第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
e) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜d)を反復する段階。
【請求項１３】
スキャンする段階が物体のCTスキャンを実施することによって達成される、請求項12記載の方法。
【請求項１４】
物体が患者の骨構造を含む、請求項12記載の方法。
【請求項１５】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項12記載の方法。
【請求項１６】
それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角形分割された輪郭の上面および底面輪郭を閉じる段階をさらに含む、請求項15記載の方法。
【請求項１７】
以下の段階を含む、複数の輪郭線から物体の表面形状を再構築する方法：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
第一および第二の輪郭線に対応する近接して位置している2本の輪郭線上のそれぞれの点に対して最近接方位三角形分割スキームを実施し、第一および第二の輪郭線に対応する物体の一部分についての第一の表面形状を決定する段階であって、該最近接方位三角形分割スキームが以下の段階を含む、方法：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する該第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a)およびb)を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項１８】
スキャンする段階が物体のCTスキャンを実施することにより達成される、請求項17記載の方法。
【請求項１９】
物体が患者の骨構造を含む、請求項17記載の方法。
【請求項２０】
第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位が、該第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の各点の重心ベクトルのドット積を計算することによって決定され、最小のドット積をもつ第二の輪郭線上の点が最近接方位に対応する、請求項17記載の方法。
【請求項２１】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項17記載の方法。
【請求項２２】
それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角形分割された輪郭の上面および底面輪郭を閉じる段階をさらに含む、請求項21記載の方法。
【請求項２３】
コンピュータで実行可能であり、物体の表面形状を計算するように構成されたコンピュータプログラム製品であって、コンピュータで実行された場合に以下の段階を実行するコンピュータプログラム製品：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の一部分についての第一の表面形状を決定する段階； 
第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定する段階；
該第一の表面形状が間違っていない場合、物体の該部分についての再構築された表面形状として、第一の三角形分割スキームにより決定されたように物体の該部分についての第一の表面形状を出力する段階；ならびに
該第一の表面形状が間違っている場合、
近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の該部分についての第二の表面形状を決定する段階；および
物体の該部分についての再構築された表面形状として、第二の三角形分割スキームによって決定されたように物体の該部分についての第二の表面形状を出力する段階。
【請求項２４】
第一の三角形分割スキームが最短距離スキームであり、第二の三角形分割スキームが最近接方位スキームである、請求項23記載のコンピュータプログラム製品。
【請求項２５】
スキャンする段階が物体のCTスキャンを実施することにより達成される、請求項23記載のコンピュータプログラム製品。
【請求項２６】
物体が患者の骨構造を含む、請求項23記載のコンピュータプログラム。
【請求項２７】
物体の完全に再構築された表面形状を得るために、複数の輪郭線のうち近接して位置している2本の各々の輪郭線上のそれぞれの点に対して、第一の三角形分割スキームもしくは第二の三角形分割スキームのいずれかまたは両方を実施する段階をさらに含む、請求項23記載のコンピュータプログラム製品。
【請求項２８】
第一の三角形分割スキームおよび第二の三角形分割スキームのうちの一方が、以下の段階を含む最短距離三角形分割スキームを含む、請求項23記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
e) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜d)を反復する段階。
【請求項２９】
第一の三角形分割スキームおよび第二の三角形分割スキームのうちの一方が、以下の段階を含む最近接方位三角形分割スキームを含む、請求項23記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する該第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a)およびb)を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項３０】
第一の三角形分割スキームおよび第二の三角形分割スキームのうちの他方が、以下の段階を含む最近接方位三角形分割スキームを含む、請求項28記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する該第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する該第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a)およびb)を反復する段階；
d) 該第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項３１】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項23記載のコンピュータプログラム製品。
【請求項３２】
それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角形分割された輪郭の上面および底面輪郭を閉じる段階をさらに含む、請求項31記載のコンピュータプログラム製品。
【請求項３３】
チェック段階が以下の段階を含む、請求項23記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；
e) 第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックする段階であって、方位が90度より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；該方位は、第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が90度超の方位に対応する段階；ならびに
f) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜e)を反復する段階。
【請求項３４】
コンピュータで実行可能であり、物体の表面形状を計算するように構成されたコンピュータプログラム製品であって、コンピュータで実行された場合に以下の段階を実行するコンピュータプログラム製品：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
第一および第二の輪郭線に対応する近接して位置している2本の輪郭線上のそれぞれの点に対して最短距離三角形分割スキームを実施し、第一および第二の輪郭線に対応する物体の一部分についての第一の表面形状を決定する段階であって、該最短距離三角形分割スキームが以下の段階を含む、段階；
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
e) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜d)を反復する段階。
【請求項３５】
スキャンする段階が物体のCTスキャンを実施することによって達成される、請求項34記載のコンピュータプログラム製品。
【請求項３６】
物体が患者の骨構造を含む、請求項34記載のコンピュータプログラム製品。
【請求項３７】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項34記載のコンピュータプログラム製品。
【請求項３８】
それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角形分割された輪郭の上面および底面輪郭を閉じる段階をさらに含む、請求項37記載のコンピュータプログラム製品。
【請求項３９】
コンピュータで実行可能であり、物体の表面形状を計算するように構成されたコンピュータプログラム製品であって、コンピュータで実行された場合に以下の段階を実行するコンピュータプログラム製品：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
第一および第二の輪郭線に対応する近接して位置している2本の輪郭線上のそれぞれの点に関して最近接方位三角形分割スキームを実施し、第一および第二の輪郭線に対応する物体の一部分についての第一の表面形状を決定する段階であって、該最近接方位三角形分割スキームが以下の段階を含む、段階：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a)およびb)を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項４０】
スキャンする段階が物体のCTスキャンを実施することにより達成される、請求項39記載のコンピュータプログラム製品。
【請求項４１】
物体が患者の骨構造を含む、請求項39記載のコンピュータプログラム製品。
【請求項４２】
第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位が、第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の各点の重心ベクトルのドット積を計算することによって決定され、最小のドット積をもつ第二の輪郭線上の点が最近接方位に対応する、請求項39記載のコンピュータプログラム製品。
【請求項４３】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項39記載のコンピュータプログラム製品。
【請求項４４】
それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角形分割された輪郭の上面および底面輪郭を閉じる段階をさらに含む、請求項43記載のコンピュータプログラム製品。
【請求項４５】
以下を含む、複数の輪郭線から物体の表面形状を再構築するための器具：
スキャンデータを得てスキャンデータをセグメント化するために物体をスキャンすることによって、複数の輪郭線を得るように構成されたスキャナユニットと、
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てるように構成された割当てユニットであって、該輪郭線の各々が閉じられ、他の輪郭線に対して交差していない、割当てユニットと、
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、該近接して位置している2本の輪郭線に対応する物体の一部分についての第一の表面形状を決定するように構成された、第一の三角形分割計算ユニットと、
第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定するように構成されたチェックユニットと、
近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、該近接して位置している2本の輪郭線に対応する物体の一部分についての第二の表面形状を決定するように構成された、第二の三角形分割計算ユニットと、
物体の該部分についての再構築された表面形状として、第一の三角形分割計算ユニットによる出力としての第一の表面形状かまたは第二の三角形分割計算ユニットによる出力としての第二の表面形状のいずれかを出力し表示するように構成された、出力および表示ユニット。
【請求項４６】
第一の三角形分割計算ユニットが最短距離三角形分割を実施し、第二の三角形分割計算ユニットが最近接方位三角形分割を実施する、請求項45記載の器具。
【請求項４７】
スキャナユニットがCTスキャナを含む、請求項45記載の器具。
【請求項４８】
物体が患者の骨構造を含む、請求項45記載の器具。
【請求項４９】
互いの上部に積み重なっている三角形分割された輪郭の多数の対から物体のモデルを作製するように構成されている物体モデル作製ユニットをさらに含む、請求項45記載の器具。
【請求項５０】
物体モデル作製ユニットが、それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角分割された輪郭の上面および底面輪郭を閉じることによって、モデルの上面および底面部分を作製する、請求項49記載の器具。
【請求項５１】
チェックユニットが以下の手段を含む、請求項45記載の器具：
第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定するための手段；
第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定するための手段；
第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較するための手段；
該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定するための手段；
第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックするための手段であって、方位が90度より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；該方位が、第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が90度超の方位に対応する、手段；
ここでチェックユニットは、第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することによってチェックを実施する。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本発明は、平行または実質的に平行な面上に提供されている複数の輪郭線から表面形状を構築するためのシステムおよび方法に関する。
【背景技術】
【０００２】
関連技術の説明
生体臨床医学の分野においては、人体構造(例えば骨、腫瘍、組織)の正確な三次元(3D)表面を確保することが、画像誘導手術などの画像誘導療法および放射線療法の計画において非常に有用である。コンピュータ断層撮影法(CT)、磁気共鳴映像法(MRI)、陽電子放出型断層撮影法(PET)、単光子放出コンピュータ断層撮影法(SPECT)、およびいくつかの超音波技術により、人体の横断面を得ることが可能である。
【０００３】
人体構造の三次元表面を構築するのに適したアプローチは、異なるレベルに対応する平行なスライスから作り上げられた1組の輪郭の三角形分割による人体構造の輪郭線から作製される。これは、隣接する輪郭線の点をつなぎ合わせて三角形を生成することであると簡潔に述べることができる。表面は、これらの輪郭を複数の同じ図形に切り分けることにより表現され、ここで、関心対象の表面に近似する多面体を画定するように三角形の要素が得られる。表面の三角形分割における主たる問題点は、再構築された表面の精度ならびにアルゴリズムの信頼度および複雑性にある。
【０００４】
以上のことを考慮すると、非常に優れた精度を有する任意の複雑な表面を生成することのできる輪郭三角形分割システムおよび方法に対するニーズが存在する。複雑な表面の生成は、好ましくは、迅速で信頼性が高く、実時間アプリケーションに適しているであろう。
【発明の開示】
【０００５】
発明の概要
本発明の一局面は、複数の輪郭線から物体の表面形状を再構築する方法に関する。本方法は、物体をスキャンしてスキャンデータを得、スキャンデータをセグメント化して輪郭線を得ることによって、複数の輪郭線を得る段階を含む。この方法はまた、セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階を含み、該輪郭線の各々が閉じられ、他の輪郭線に対して交差していない。本方法はさらに、近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施する段階を含み、近接して位置している2本の輪郭線に対応する物体の一部分についての第一の表面形状を決定する。この方法はさらに、第一の表面形状が間違っているか否かを決定するために第一の表面形状をチェックする段階を含む。第一の表面形状が間違っていない場合、この方法は、第一の三角形分割スキームにより決定されたように物体の該部分についての第一の表面形状を、物体の該部分についての再構築された表面形状として出力する段階を含む。第一の表面形状が間違っている場合、この方法は、近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施する段階を含み、該近接して位置している2本の輪郭線に対応する物体の該部分についての第二の表面形状を決定し、第二の三角形分割スキームによって決定されたように物体の該部分についての第二の表面形状を、物体の該部分についての再構築された表面形状として出力する段階を含む。
【０００６】
本発明のさらに別の局面は、複数の輪郭線から物体の表面形状を再構築する方法に関する。この方法は、物体をスキャンしてスキャンデータを得、スキャンデータをセグメント化して輪郭線を得ることによって、複数の輪郭線を得る段階を含む。この方法はまた、セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階を含み、該輪郭線の各々が閉じられ、他の輪郭線に対して交差していない。この方法は、第一および第二の輪郭線に対応する近接して位置している2本の輪郭線上のそれぞれの点に対して最短距離三角形分割スキームを実施する段階をさらに含み、第一および第二の輪郭線に対応する物体の一部分についての第一の表面形状を決定する。最短距離三角形分割スキームは、以下の段階を含む：
a) 第一の輪郭線上の各点について、第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点、または第二の輪郭線上の点と隣接点のいずれかを結合する線として、第三の三角形の辺を設定する段階；および
e) 第一および第二の輪郭線上の全ての点が、第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線上または第二の輪郭線上のいずれかで時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより段階a)〜d)を反復する段階。
【０００７】
さらに本発明の別の局面は、複数の輪郭線から物体の表面形状を再構築する方法に関する。方法は、物体をスキャンしてスキャンデータを得、スキャンデータをセグメント化して輪郭線を得ることによって、複数の輪郭線を得る段階を含む。方法また、セグメント化されたスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階を含み、該輪郭線の各々が閉じられ、該輪郭線のうちの他の輪郭線に対しては交差していない。方法は、第一および第二の輪郭線に対応する近接して位置している2本の輪郭線上のそれぞれの点に関して最近接方位三角形分割スキームを実施する段階をさらに含み、第一および第二の輪郭線に対応する物体の一部分についての第一の表面形状を決定する。最近接方位スキームは、以下の段階を含む：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点に対する第一の輪郭線上の点の最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a) およびb) を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として、第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの短い方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【０００８】
好ましい態様の詳細な説明
本発明の現在好ましい態様が、図面に図示されている。本明細書は主に骨の表面画像を確保することに言及しているが、本明細書で記述されている主題は、身体の他の部分、例えば器官、腸または筋肉などに対しても適用可能できることを理解すべきである。
【０００９】
第一の態様は、患者の骨などの物体をスキャンすることから得られる一組の平行な輪郭線から複雑な表面を再構築することを目指している。限定的な意味ではなく一例として、患者のひざなどの生体構造のCTスキャンが、生データ取得段階で行なわれ、スキャンされたデータはCTスキャンファイル内に記憶される。このCTスキャンから、第一の態様は、大腿骨および脛骨の外部表面など患者のひざの3D表面を再構築する。CTスキャンファイルのフォーマットは、汎用コンピュータにより可読である任意の特定のフォーマットで得ることができ、例えばDigital Imaging and Communications in Medicine (DICOM)フォーマットから変換されるImage Guidance System (IGS)フォーマットなどで、したがって該フォーマットは当業者にとっては周知である。
【００１０】
コンピュータは、任意の公知の計算システムであり得るが、好ましくは、プログラム可能でプロセッサベースのシステムである。例えば、コンピュータは、マイクロプロセッサ、ハードドライブ、ランダムアクセスメモリ(RAM)、読取り専用メモリ(ROM)、入出力(I/O)回路、および任意の他の周知のコンピュータコンポーネントを含むことができる。コンピュータは好ましくは、例えば、ポータブルドライブ、磁気記憶装置(例えばフロッピーディスク)、固体記憶装置(例えばフラッシュメモリカード)、光学記憶装置(例えばコンパクトディスクすなわちCD)、および／またはネットワーク／インターネット記憶装置などのさまざまなタイプの記憶デバイス(固定およびリムーバブル)と共に使用するように適合化される。コンピュータは、例えばパーソナルコンピュータ(例えばIBM-PC互換コンピュータ)あるいはウインドウズ、UNIX、Linux、または他の適切なオペレーティングシステムの下で作動するワークステーション(例えばSUNまたはSilicon Graphicsワークステーション)を含めた一つまたは複数のコンピュータを含んでいてよく、好ましくは、グラフィカル・ユーザ・インターフェース(GUI)を含む。
【００１１】
ひとたび生データを取得し、コンピュータにまたはコンピュータによってアクセス可能なメモリにこれをロードしたならば、生データの表面構築が第一の態様を介して作られ、これはコンピュータにより実行可能なプログラムコードで具現化することができる。CTスキャンファイルデータから、本明細書では輪郭線とも呼ばれる一組の平行なスライス(これらは、横方向、矢状方向、王冠状または斜めなど任意の方位であり得る)が、大腿骨または脛骨全体を包含するように選択される。スライスの数は、大腿および脛骨のセグメンテーションの作業負荷と再構築された3D表面の解像度との妥協点により決定され得る。スライスの数と位置が設定された後、大腿骨および脛骨を画像のそれ以外の部分から分離するために、手作業によるセグメンテーションが実施される。多数のセグメンテーションスキームのうちの任意のものを、一平面に一つの輪郭で用いて、平行面内に1組の輪郭を作り出すことができる。例えば、「ライブワイヤ(Live Wire)」セグメンテーション(エッジ計測スキーム)または「スネークス(Snakes)」セグメンテーションを実施することができ、したがってこれらのセグメンテーションスキームは当業者にとって周知である。物体をスキャンすることで得られる出力は一連の並列画像であり、そのためこれらの画像は、輪郭線を作り出す輪郭化プロセス(先で記述されたものなどの当業者にとって公知のもののうちの任意のもの)に入力される。各々の輪郭は、1組の輪郭点により表わされる。各々の輪郭点の3D座標(x、y、z)は、第一の態様による三角形分割処理ユニットへの入力としてセーブされる。第一の態様においては、これらの輪郭点は、反時計回り(CCW)方向に順序づけされる。または、これらを時計回り(CW)方向に順序づけすることができる。第一の態様による三角形分割処理ユニットは、コンピュータにより実行可能なプログラムコードとして具現化することできる。輪郭線はセグメント化スキャン画像の一部の部域では凹状、他の部域では平坦、そしてそのさらに他の部域では凸状であり、そのため各々の輪郭線は閉じており(例えば第一の点は第二の点と結合し、第二の点は第三の点と結合し、・・・、そして最後の点は同じ輪郭線上の第一の点と結合する)、他の輪郭線と交差していない。
【００１２】
第一の態様において、コンピュータの三角形分割処理ユニットを手段として「最短距離」三角形分割アプローチが提供され、これが近接する平行な輪郭の対の間の三角形ストリップを生成する。第一の態様による「最短距離」三角形分割アプローチについては、以下で詳細に説明する。
【００１３】
ここで図1を参照すると、三角形分割は、輪郭1上の点Piおよび輪郭2上の点Qjから出発する。次の三角形分割は、Pi1またはQj1のいずれかをピックアップして、三角形パッチPiPi1QjまたはPiQjQj1を生成する。Pi1は、CCW方向で点Piに最も近い輪郭1上の点であり、点Qj1は、CCW方向で点Qjに最も近い輪郭2上の点であり、そのため、輪郭1および輪郭2は、近接して位置している輪郭である。図1に示されているように、Vciは、Piから輪郭1の重心までのベクトルであり；Vcjは、Qjから輪郭2の重心までのベクトルであり；Vci1は、Pi1から輪郭1の重心までのベクトルであり；Vcj1はQj1から輪郭2の重心までのベクトルである。
【００１４】
第一の態様による最短距離スキームにおける第一の段階は、初期点の選択にある。この初期点の決定は、以下のように行なわれる。
1) 大きい数(例えば、16ビットのデータワードを用いるコンピュータについては216-1)までの最小距離dminを設定する。
2) 輪郭1上の一つの輪郭点から出発して、輪郭2上の各輪郭点までの距離を計算し、最短距離をdsとして記録する。
3) dsがdmin未満である場合、dminをdsに設定する。輪郭1および輪郭2上の輪郭点の位置を、コンピュータによりアクセス可能なメモリ内にそれらを記憶することによって記録する。
4) 輪郭1内の別の輪郭点まで移動し、段階2) および3) を反復する。
5) 輪郭1上の全ての輪郭点がチェックされた時点で停止する。
【００１５】
輪郭上の全ての点についてひとたび初期点が決定されたならば、第一の態様において以下の最短距離決定段階が実施される。
1)輪郭1および輪郭2のそれぞれの上の最近接距離を有する二つの点PiおよびQjを選択する。
2) PiからQj1までの距離とPi1からQjまでの距離を比較する。PiとQj1がより短い距離を有する場合、Qj1を選択して三角形パッチPiQjQj1を生成する。Pi1とQjがより短い距離を有する場合、Pi1を選択して三角形パッチPiPi1Qjを生成する。図2を参照されたい。ここで図中、破線で二つの可能性のある選択肢を示している。
3) 三角形分割のために全ての輪郭点が選択されてしまうまで、段階1)および2)を反復して実施する。
4) 一方の輪郭が輪郭点から外に出た場合、該輪郭における端点にとどまり、他方の輪郭上の隣接する点を選択するだけで、次の反復において三角形パッチを生成する。
5) 三角形分割のために全ての輪郭点が選択された時点で、停止する。
【００１６】
図2、3、4、および5は、最短距離計測基準による三角形分割の詳細なプロセスを示す。下記は、上記の最短距離三角形分割方法のために使用できる疑似コードである。
2009535693.tif 000003
【００１７】
第一の態様による最短距離のソリューションでは、最短距離によって生成される三角形分割が実際の3D表面に対する最近接近似を有するということを仮定している。これは、大部分のケースにおいて真実である。したがって、それは患者のひざの脛骨または大腿などのほぼあらゆる複雑な3D表面を近似できる視覚的に平滑な表面を生成する。
【００１８】
図2は、最短距離を有する初期点PiおよびQjの選択を示し、これにより次の段階で二つの候補距離PiQj1およびPi1Qjが比較される。図3は、最短距離としてQj1の選択を示し、これが三角形パッチPiQjQj1の生成をもたらす。図4は、新しい位置へのQjの更新を示し、これにより二つの候補距離PiQj1とPi1Qjが次の段階で比較される。Qjの新しい位置は、図3で示されているように、先の段階におけるQj1の位置に対応する。候補距離PiQj1が第二段階における二つの距離のうちの最短のものである場合、三角形パッチPiQjQj1が生成される。候補距離Pi1Qjが第二段階における二つの距離のうち最短である場合、代りに三角形パッチPiPi1Qjが生成される。図5は、第一の態様の最短距離アプローチよる、輪郭1と輪郭2の全ての点の間の三角形パッチの生成の最終的パターン500を示す。
【００１９】
最短距離アプローチは、例えばCTスキャナによりスキャンされた物体の真の形状を適正に近似する3D形状を生成する目的で、それぞれの輪郭各々について続けられる。
【００２０】
第二の態様において、コンピュータの三角形分割処理ユニットを介した「最近接方位」三角形分割アプローチが提供されており、これは隣接する平行な輪郭の対の間で三角形ストリップを生成する。第二の態様による「最近接方位」三角形分割アプローチについては以下で詳しく説明される。第二の態様は、第一の態様の目的に類似した、スキャンされた物体の真の表面形状を適正に近似する表面形状を提供する。第二の態様の三角形分割処理ユニットは、コンピュータにより実行可能なプログラムコードとして具現化できる。
【００２１】
第二の態様による最近接方位スキームにおける第一の段階は、初期点の選択である。この初期点の決定は、以下のように行なわれる。
1) 最近接方位Orientmaxを0に設定する。
2) 輪郭1上の一つの輪郭i点から開始し、輪郭2上の各輪郭点jに対するベクトルVciの方位を計算する。方位はベクトルVciおよびVcjのドット積である。Orientclosestとして最近接方位を記憶する。
3) OrientclosestがOrientmaxよりも大きい場合、OrientmaxをOrientclosestにセットする。輪郭1および輪郭2上に輪郭点の位置を記憶する。
4) 輪郭1内の別の輪郭点まで移動し、段階2)および3)を反復する。
5) 輪郭1上の全ての輪郭点がチェックされた時点で停止する。
【００２２】
ひとたび輪郭上の全ての点について初期点が決定されると、第二の態様内で以下の最近接方位決定段階が実施される。
1) このスキームは、輪郭1および輪郭2それぞれの重心に関する最近接方位を有する二つの点PiおよびQjから出発する。
2) 次の段階は、ベクトル対(Vci, Vcj1)と(Vcj, Vci1)の方位を比較する。(Vci, Vcj1)がより密な方向を有する場合、次の段階は、Qj1を選択して三角形パッチPiQjQj1を生成する。(Vcj, Vci1)がより密な方位を有する場合、次の段階は、Pi1を選択して三角形パッチPiPi1Qjを生成する。
3) 全ての輪郭点が三角形分割のために選択されるまで、これらの段階が反復的に実行される。
4) 一方の輪郭が輪郭点から外に出た場合、最近接方位スキームはその輪郭の上の端点にとどまり、他方の輪郭上の隣接点を選択して次の反復において三角形パッチを生成する。
5) 最近接方位決定スキームは、全ての輪郭点が三角形分割のために選択された時点で停止する。
【００２３】
図6〜9は、第二の態様による最近接方位計測基準による詳細な三角形分割プロセスを示す。図6は、初期点選択段階に基づいて選択された初期点PiおよびPjを示し、それにより該段階で方位対(Vci, Vcj1)と(Vcj, Vci1)が比較される。図7は、最近接方位により選択されたQj1を示し、それによりベクトル対(Vci, Vcj1)がこの例においてより密な方位(より大きい値)を有した。したがって、図7に示されているように、三角形パッチPiQjQj1が作製される。図8は、Qjのその新しい位置(先の段階におけるQj1の位置)に対する更新を示し、これによりこの次の段階で方位対(Vci, Vcj1)と(Vcj, Vci1)が比較される。図9は、第二の態様の最近接方位スキームを使用することによる、二つの輪郭線から生成された三角形パッチの最終パターン900を示す。
【００２４】
以下に記すのは、第二の態様の最近接方位スキームのために使用できる疑似コードである。
2009535693.tif 000004
【００２５】
最近接方位ソリューションは、輪郭の重心に関する方位に沿って等分布する三角形分割を生成する。したがって、輪郭が類似の形状および方位を有し、相互に心出しされている（mutually centered）場合、最近接方位スキームで充分である。
【００２６】
本発明の第三の態様についてここで詳細に記述する。第三の態様は、第一および第二の態様に類似した患者からスキャンしたスキャンデータ(例えばCTスキャンから得たデータ)を得る。このスキャンデータから、このデータから表面構造を得るために三角形分割スキームが実施される。第三の態様においては、第一の態様に関して記述されたように最短距離スキームがまず実施される。このスキームの結果が許容できる場合、プロセスを終了する。このスキームの結果が許容できない場合、第三の態様が同じスキャンデータの最近接方位スキームを実施し、表面輪郭データとして結果を出力する。
【００２７】
第三の態様の背後にある論拠を以下で説明する。第一の態様の最短距離スキームは、数多くの複雑な3D表面近似に関して充分に機能する。しかしながら、二つの隣接する輪郭に輪郭点の数に大きい差異があり(例えば一つの輪郭が隣接する輪郭よりはるかに短い)、一方の輪郭が他方の輪郭の一方の側に近い場合、短い方の輪郭上の数多くの点が、最短距離スキームにより、他方の輪郭の間違った側上の輪郭点に結合する。このことは、図10に示されており、ここで、d2がd1より短く、そのため正しい結合結果であるd1短距離計測基準を満たしていない。図11は、上部輪郭が輪郭点の外に出た場合の三角形パッチを示している。図12に示されているねじれた三角形パッチは、「ボタン」様の構造を生成し、これは間違ったまたは正しくない結果に相当する。しかしながら、第二の態様による最近接方位スキームは、この場合正しい結果を生成する。したがって、第三の態様による提案された三角形分割スキームは、二つのスキームを組合せるものである。まず第一に、それは、第一の態様に関して先で説明したように、最短距離のソリューションによる三角形分割を生成する。間違った結果が検出された場合、それは、第二の態様に関して先で説明したように、最近接方位のソリューションに切り換わり、三角形分割を再生成する。これにより、表面が実際の表面に対して優れた近似であり再構築が正しいものであることが保証される。
【００２８】
第三の態様の一つの特長は、いつ第一の三角形分割スキームが「間違った」結果を提供したかとの決定である。これは、二つの近接する輪郭上の結合点のそれぞれの重心ベクトルをチェックすることによって行なうことができる。それぞれの重心ベクトルが互いに少なくとも90度の差がある方向を指している場合、間違った結果が検出される。例えば、ここで図10を見てみると、下部輪郭上の結合点は、下部輪郭の中心から下部輪郭上の結合点を指す重心ベクトルを有し、一方、上部輪郭上の結合点は、上部輪郭の中心から上部輪郭上の結合点を指し、そのためこれら二つの重心ベクトルは180度差のある方向を指している。したがって、第一の最短距離三角形分割スキームは停止され、次に、第二の最近接方位三角形分割スキームを適用して、輪郭線から表面形状を得る。第三の態様においては、最短距離スキームにしたがって、第一の輪郭上の点を第二の輪郭上の点に対して各々の結合がされた後、それぞれの重心ベクトルがチェックされ、それらが正しくない結果を示した場合、第三の態様は、最短距離スキームを停止し、結果を消去し、最近接方位スキームを開始する。
【００２９】
最短距離三角形分割スキームの出力において、チェック段階またはチェックユニットによってどのようにエラーを検出できるかについてのさらに詳しい記述が以下に提供される。
a) 第一の輪郭線上の各点について、第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する。
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する。
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する。
d) 段階c)で実施された比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点、または第二の輪郭線上の点と隣接点のいずれかを、結合する線として第三の三角形の辺を設定する。
e) 第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックする段階であって、該方位が予め定められた値(例えば90度)より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；該方位が、第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が予め定められた値(例えば90度)を超える方位に相当している。
f) 一方の第一および第二の輪郭線上の全ての点が他方の第一および第二の輪郭線上の別の点に結合されるまで、第一の輪郭線上または第二の輪郭線上のいずれかで時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜e)を反復する。
【００３０】
最短距離アプローチおよび最近接方位アプローチの三角形分割スキームの出力は、「三角形セット」リストである。三つの頂点の配位はメモリ内に保存され、次にディスプレー(例えばコンピュータモニター)上で表示するため、表面レンダリングに用いられる。図13は、最短距離三角形分割スキームの間違った三角形パッチを使用した結果として作製された、三角形パターン1300の一例を示す。これは、例えば互いに非常に異なるサイズを有する近接した輪郭線の少なくとも一対に起因したものと考えられた。図14は、図13の三角形パターン1300を生成するのに用いたものと同じ輪郭についての最近接方位三角形分割スキームの正しい三角形パッチを用いた結果として、作製された三角形パターン1400の例を示す。図15は、物体モデル作製ユニットにより生成され、図14に示されているように生成された三角形パッチに基づいて表示される表面形状1500を示す。三角形パッチから次に積み重なっている三角分割済み輪郭からの表面形状1500の生成は、当該技術分野において周知であり、簡潔にするためにこの出願においては論述しない。しかしながら、本発明の少なくとも実施の可能性によると、図16に示されている物体モデル作製ユニット255は、上面および底面それぞれの輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を用いて積み重なっている三角分割の輪郭の上面および底面輪郭を閉じることにより、表面形状(またはモデル)の上面および底面部分を作製するという点で、従来の物体モデル作製ユニットと異なっている。
【００３１】
図16は、本発明の第一、第二、または第三の態様を実施するための考えられる一つのシステム200を示す。図16において、スキャンユニット(例えばCTスキャナ) 210が、患者の体の一部分などの物体をスキャンする。次にスキャンデータはコンピュータ205に提供される。スキャンデータのセグメンテーションが、スキャンユニット210かまたはコンピュータ205によって実施できるという点に留意されたい。割当てユニット220が、スキャンデータから得た輪郭線の各々に対し点を割当てる。第一の三角形分割計算ユニット230は、第一の態様に関して先で論述したものなどのスキャンデータに対して最短距離三角形分割スキームを実施する。チェックユニット250は、先で説明したように、第一の三角形分割計算ユニット230により生成された三角形の中のエラーについてチェックする。第二の三角形分割計算ユニット240は、第二の態様に関して先で論述したものなどのスキャンデータに対して最近接方位三角形分割スキームを実施する。第一の三角形分割計算ユニット230により生成された三角形パッチ内にエラーが存在することをチェックユニット250が決定したか否かに基づいて、第二の三角形分割計算ユニット240は、何もしないか、またはスキャンデータに対するその最近接方位処理を実施するように命令を受ける。物体モデル作製ユニット255は、チェックユニット250により提供された命令にしたがって、第一の三角形分割計算ユニット230により出力された三角形パッチまたは第二の三角形分割計算ユニット240により出力された三角形パッチから、表面形状または物体モデルを生成する。出力ユニット260は、ディスプレーに対して、物体モデル作製ユニット255により提供された表面形状を出力する。図16内に示された構造は、第三の態様に関するものである。第一の態様に関しては、第二の三角形分割計算ユニット240およびチェックユニット250は提供されず、このため、第一の三角形分割計算ユニット230により生成された三角形パッチは物体モデル作製ユニット255に、次にディスプレーへの出力のため出力ユニット260に直接提供される。第二の態様に関しては、第一の三角形分割計算ユニット230およびチェックユニット250は提供されず、そのためスキャンデータは割当てユニット220から第二の三角形分割計算ユニット240へと直接提供される。
【００３２】
したがって、本発明の態様は、複数の輪郭線を含むスキャンされた画像データから表面形状を取得するための輪郭三角形分割装置および方法を提供している。本発明の他の態様は、本明細書で開示されている本発明の明細および実践方法を考慮することにより、当業者にとっては明白である。明細書および例は、単なる例示とみなすよう意図されている。
【図面の簡単な説明】
【００３３】
本明細書の中に組入れられその一部を構成する添付図面は、本発明の態様を図示し、説明と共に本発明の原理を説明するのに役立つ。
【図１】本発明の第一の態様よる最短距離三角形分割スキームが実施される二つの輪郭の斜視図である。
【図２】本発明の第一の態様よる初期点がすでに選択されかつ二つの候補距離が比較される二つの輪郭の斜視図である。
【図３】本発明の第一の態様よる第一の三角形パッチが生成された二つの輪郭の斜視図である。
【図４】本発明の第一の態様よる三角形パッチ生成スキームにおける次の反復が開始する二つの輪郭の斜視図である。
【図５】本発明の第一の態様よる複数の三角形パッチが生成された二つの輪郭の斜視図である。
【図６】本発明の第二の態様よる最近接方位三角形分割スキームが実施される二つの輪郭の斜視図である。
【図７】本発明の第二の態様よる初期点がすでに選択されかつ二つの候補最近接方位ベクトル値が比較される二つの輪郭の斜視図である。
【図８】本発明の第二の態様よる三角形パッチ生成スキームにおける次の反復が開始する二つの輪郭の斜視図である。
【図９】本発明の第二の態様よる複数の三角形パッチが生成された二つの輪郭の斜視図である。
【図１０】最短距離三角形分割スキームを使用することによって間違った三角形パッチが生成された二つの輪郭の斜視図である。
【図１１】上部輪郭が輪郭点から外に出てしまった二つの輪郭の斜視図である。
【図１２】最短距離三角形分割スキームを使用することによって複数の間違った三角形パッチが生成された二つの輪郭の斜視図である。
【図１３】最短距離三角形分割スキームの間違った三角形パッチを使用した結果として作製された表面形状の一例を示す。
【図１４】図13の表面形状を生成するために使用した同じ輪郭について最近接方位三角形分割スキームの正しい三角形パッチを用いた結果として作製された表面形状の一例を示す。
【図１５】図14に示したように生成された三角形分割パッチに基づいて生成される表面形状を示す。
【図１６】本発明の一つまたは複数の態様よる輪郭の三角形分割システムを示す。
【図１】
2009535693.tif 000006
【図２】
2009535693.tif 000007
【図３】
2009535693.tif 000008
【図４】
2009535693.tif 000009
【図５】
2009535693.tif 000010
【図６】
2009535693.tif 000011
【図７】
2009535693.tif 000012
【図８】
2009535693.tif 000013
【図９】
2009535693.tif 000014
【図１０】
2009535693.tif 000015
【図１１】
2009535693.tif 000016
【図１２】
2009535693.tif 000017
【図１３】
2009535693.tif 000018
【図１４】
2009535693.tif 000019
【図１５】
2009535693.tif 000020
【図１６】
2009535693.tif 000021
【手続補正書】
【提出日】平成20年2月26日(2008.2.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の輪郭線から物体の表面形状を再構築する方法であって、以下の段階を含む方法：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の一部分について第一の表面形状を決定する段階；
第一の表面形状のコンピュータ解析を行うことによって第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定する段階；
第一の表面形状が間違っていない場合、物体の該部分について再構築された表面形状として、第一の三角形分割スキームにより決定されたように物体の該部分についての第一の表面形状を出力する段階；ならびに
第一の表面形状が間違っている場合、
近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の該部分についての第二の表面形状を決定する段階；および
物体の該部分についての再構築された表面形状として、第二の三角形分割スキームによって決定されたように物体の該部分についての第二の表面形状を出力する段階。
【請求項２】
第一の三角形分割スキームが最短距離スキームであり、第二の三角形分割スキームが最近接方位スキームである、請求項1記載の方法。
【請求項３】
チェック段階が以下の段階を含む、請求項1記載の方法：
第一の表面形状の複数の輪郭線のうち隣接する2つの線上の結合された点のそれぞれの重心ベクトルを計算する段階；
計算する段階において計算されたそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いているか否かを決定する段階；および
複数の輪郭線のうち隣接する2つの線のそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いている場合に第一の表面形状が間違っていることを決定する段階。
【請求項４】
物体が患者の骨構造を含む、請求項1記載の方法。
【請求項５】
物体の完全に再構築された表面形状を得るため、複数の輪郭線のうち近接して位置している2本の輪郭線各々の上のそれぞれの点に対して第一の三角形分割スキームか第二の三角形分割スキームのうちのいずれかまたは両方を実施する段階をさらに含む、請求項1記載の方法。
【請求項６】
第一の三角形分割スキームが、以下の段階を含む最短距離三角形分割スキームを含む、請求項1記載の方法：
a) 第一の輪郭線上の各点について、第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
e) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜d)を反復する段階。
【請求項７】
第二の三角形分割スキームが、以下の段階を含む最近接方位三角形分割スキームを含む、請求項1記載の方法：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a)およびb)を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項８】
第二の三角形分割スキームが、以下の段階を含む最近接方位三角形分割スキームを含む、請求項6記載の方法：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点について最近接方位が決定されるまで段階a)およびb)を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として、第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項９】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項1記載の方法。
【請求項１０】
それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角形分割された輪郭の上面および底面輪郭を閉じる段階をさらに含む、請求項9記載の方法。
【請求項１１】
チェック段階が以下の段階を含む、請求項1記載の方法：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 該第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；
e) 第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックする段階であって、方位が90度より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；方位が第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が90度超の方位に対応する段階；ならびに
f) 第一および第二の輪郭線上の全ての点が、第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜e)を反復する段階。
【請求項１２】
コンピュータで実行可能であり、物体の表面形状を計算するように構成されたコンピュータプログラム製品であって、コンピュータで実行された場合に以下の段階を実行するコンピュータプログラム製品：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の一部分についての第一の表面形状を決定する段階； 
コンピュータ上でコンピュータプログラム製品を実行して第一の表面形状のコンピュータ解析を行うことによって第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定する段階；
該第一の表面形状が間違っていない場合、物体の該部分についての再構築された表面形状として、第一の三角形分割スキームにより決定されたように物体の該部分についての第一の表面形状を出力する段階；ならびに
該第一の表面形状が間違っている場合、
近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の該部分についての第二の表面形状を決定する段階；および
物体の該部分についての再構築された表面形状として、第二の三角形分割スキームによって決定されたように物体の該部分についての第二の表面形状を出力する段階。
【請求項１３】
第一の三角形分割スキームが最短距離スキームであり、第二の三角形分割スキームが最近接方位スキームである、請求項12記載のコンピュータプログラム製品。
【請求項１４】
チェック段階が以下の段階を含む、請求項12記載のコンピュータプログラム製品：
第一の表面形状の複数の輪郭線のうち隣接する2つの線上の結合された点のそれぞれの重心ベクトルを計算する段階；
計算する段階において計算されたそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いているか否かを決定する段階；および
複数の輪郭線のうち隣接する2つの線のそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いている場合に第一の表面形状が間違っていることを決定する段階。
【請求項１５】
物体が患者の骨構造を含む、請求項12記載のコンピュータプログラム。
【請求項１６】
物体の完全に再構築された表面形状を得るために、複数の輪郭線のうち近接して位置している2本の各々の輪郭線上のそれぞれの点に対して、第一の三角形分割スキームもしくは第二の三角形分割スキームのいずれかまたは両方を実施する段階をさらに含む、請求項12記載のコンピュータプログラム製品。
【請求項１７】
第一の三角形分割スキームが、以下の段階を含む最短距離三角形分割スキームを含む、請求項12記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
e) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜d)を反復する段階。
【請求項１８】
第二の三角形分割スキームが、以下の段階を含む最近接方位三角形分割スキームを含む、請求項12記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する該第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a)およびb)を反復する段階；
d) 第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項１９】
第二の三角形分割スキームが、以下の段階を含む最近接方位三角形分割スキームを含む、請求項17記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、第二の輪郭線上の各輪郭点に対する該第一の輪郭線上の点の重心ベクトルの方位を決定する段階；
b) 第二の輪郭線上の点の重心ベクトルに対する該第一の輪郭線上の点の重心ベクトルの最近接方位を決定する段階；
c) 第一の輪郭線上の全ての点についての最近接方位が決定されるまで、段階a)およびb)を反復する段階；
d) 該第一の輪郭線上の点に対して最近接方位をもつ第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
e) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の方位を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の方位と比較する段階；
f) 該比較段階に基づいて、第一および第二の方位のうちの最近接方位を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；ならびに
g) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階d)〜f)を反復する段階。
【請求項２０】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項12記載のコンピュータプログラム製品。
【請求項２１】
それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角形分割された輪郭の上面および底面輪郭を閉じる段階をさらに含む、請求項20記載のコンピュータプログラム製品。
【請求項２２】
チェック段階が以下の段階を含む、請求項12記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；
e) 第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックする段階であって、方位が90度より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；該方位は、第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が90度超の方位に対応する段階；ならびに
f) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜e)を反復する段階。
【請求項２３】
以下を含む、複数の輪郭線から物体の表面形状を再構築するための器具：
スキャンデータを得てスキャンデータをセグメント化するために物体をスキャンすることによって、複数の輪郭線を得るように構成されたスキャナユニットと、
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てるように構成された割当てユニットであって、該輪郭線の各々が閉じられ、他の輪郭線に対して交差していない、割当てユニットと、
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、該近接して位置している2本の輪郭線に対応する物体の一部分についての第一の表面形状を決定するように構成された、第一の三角形分割計算ユニットと、
第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定するように構成されたチェックユニットと、
第一の表面形状が間違っていることをチェックユニットが決定する場合に、近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、該近接して位置している2本の輪郭線に対応する物体の一部分についての第二の表面形状を決定するように構成された、第二の三角形分割計算ユニットと、
物体の該部分についての再構築された表面形状として、第一の三角形分割計算ユニットによる出力としての第一の表面形状かまたは第二の三角形分割計算ユニットによる出力としての第二の表面形状のいずれかを出力し表示するように構成された、出力および表示ユニット。
【請求項２４】
第一の三角形分割計算ユニットが最短距離三角形分割を実施し、第二の三角形分割計算ユニットが最近接方位三角形分割を実施する、請求項23記載の器具。
【請求項２５】
チェックユニットが以下を含む、請求項23記載の器具：
第一の表面形状の複数の輪郭線のうち隣接する2つの線上の結合された点のそれぞれの重心ベクトルを計算するよう構成された計算ユニット；
計算する段階において計算されたそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いているか否かを決定するよう構成された第一の決定ユニット；および
複数の輪郭線のうち隣接する2つの線のそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いている場合に第一の表面形状が間違っていることを決定するよう構成された第二の決定ユニット。
【請求項２６】
物体が患者の骨構造を含む、請求項23記載の器具。
【請求項２７】
互いの上部に積み重なっている三角形分割された輪郭の多数の対から物体のモデルを作製するように構成されている物体モデル作製ユニットをさらに含む、請求項23記載の器具。
【請求項２８】
物体モデル作製ユニットが、それぞれの上面および底面輪郭上の隣接点から各々形成された多数の三角形の頂点としてそれぞれの重心点を使用することにより、積み重なっている三角分割された輪郭の上面および底面輪郭を閉じることによって、モデルの上面および底面部分を作製する、請求項27記載の器具。
【請求項２９】
チェックユニットが以下の手段を含む、請求項23記載の器具：
第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定するための手段；
第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定するための手段；
第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較するための手段；
該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定するための手段；
第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックするための手段であって、方位が90度より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；該方位が、第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が90度超の方位に対応する、手段；
ここでチェックユニットは、第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することによってチェックを実施する。
【手続補正書】
【提出日】平成20年12月25日(2008.12.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の輪郭線から物体の表面形状を再構築する方法であって、以下の段階を含む方法：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の一部分について第一の表面形状を決定する段階；
第一の表面形状のコンピュータ解析を行うことによって第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定する段階；
第一の表面形状が間違っていない場合、物体の該部分について再構築された表面形状として、第一の三角形分割スキームにより決定されたように物体の該部分についての第一の表面形状を出力する段階；ならびに
第一の表面形状が間違っている場合、
近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の該部分についての第二の表面形状を決定する段階；および
物体の該部分についての再構築された表面形状として、第二の三角形分割スキームによって決定されたように物体の該部分についての第二の表面形状を出力する段階。
【請求項２】
第一の三角形分割スキームが最短距離スキームであり、第二の三角形分割スキームが最近接方位スキームである、請求項1記載の方法。
【請求項３】
チェック段階が以下の段階を含む、請求項1記載の方法：
第一の表面形状の複数の輪郭線のうち隣接する2つの線上の結合された点のそれぞれの重心ベクトルを計算する段階；
計算する段階において計算されたそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いているか否かを決定する段階；および
複数の輪郭線のうち隣接する2つの線のそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いている場合に第一の表面形状が間違っていることを決定する段階。
【請求項４】
物体が患者の骨構造を含む、請求項1記載の方法。
【請求項５】
物体の完全に再構築された表面形状を得るため、複数の輪郭線のうち近接して位置している2本の輪郭線各々の上のそれぞれの点に対して第一の三角形分割スキームか第二の三角形分割スキームのうちのいずれかまたは両方を実施する段階をさらに含む、請求項1記載の方法。
【請求項６】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項1記載の方法。
【請求項７】
チェック段階が以下の段階を含む、請求項1記載の方法：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 該第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；
e) 第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックする段階であって、方位が90度より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；方位が第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が90度超の方位に対応する段階；ならびに
f) 第一および第二の輪郭線上の全ての点が、第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜e)を反復する段階。
【請求項８】
コンピュータで実行可能であり、物体の表面形状を計算するように構成されたコンピュータプログラム製品であって、コンピュータで実行された場合に以下の段階を実行するコンピュータプログラム製品：
スキャンデータを得るために物体をスキャンし、スキャンデータをセグメント化することによって、複数の輪郭線を得る段階；
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てる段階であって、輪郭線の各々が閉じられ、輪郭線が他の輪郭線に対して交差していない、段階；
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の一部分についての第一の表面形状を決定する段階； 
コンピュータ上でコンピュータプログラム製品を実行して第一の表面形状のコンピュータ解析を行うことによって第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定する段階；
該第一の表面形状が間違っていない場合、物体の該部分についての再構築された表面形状として、第一の三角形分割スキームにより決定されたように物体の該部分についての第一の表面形状を出力する段階；ならびに
該第一の表面形状が間違っている場合、
近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、近接して位置している2本の輪郭線に対応する物体の該部分についての第二の表面形状を決定する段階；および
物体の該部分についての再構築された表面形状として、第二の三角形分割スキームによって決定されたように物体の該部分についての第二の表面形状を出力する段階。
【請求項９】
第一の三角形分割スキームが最短距離スキームであり、第二の三角形分割スキームが最近接方位スキームである、請求項8記載のコンピュータプログラム製品。
【請求項１０】
チェック段階が以下の段階を含む、請求項8記載のコンピュータプログラム製品：
第一の表面形状の複数の輪郭線のうち隣接する2つの線上の結合された点のそれぞれの重心ベクトルを計算する段階；
計算する段階において計算されたそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いているか否かを決定する段階；および
複数の輪郭線のうち隣接する2つの線のそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いている場合に第一の表面形状が間違っていることを決定する段階。
【請求項１１】
物体が患者の骨構造を含む、請求項8記載のコンピュータプログラム。
【請求項１２】
物体の完全に再構築された表面形状を得るために、複数の輪郭線のうち近接して位置している2本の各々の輪郭線上のそれぞれの点に対して、第一の三角形分割スキームもしくは第二の三角形分割スキームのいずれかまたは両方を実施する段階をさらに含む、請求項8記載のコンピュータプログラム製品。
【請求項１３】
互いの上部に積み重なっている、三角形分割された輪郭の多数の対から物体のモデルを作製する段階をさらに含む、請求項8記載のコンピュータプログラム製品。
【請求項１４】
チェック段階が以下の段階を含む、請求項8記載のコンピュータプログラム製品：
a) 第一の輪郭線上の各点について、該第一の輪郭線上の点に最も近い第二の輪郭線上の点を決定する段階；
b) 第一の輪郭線上の点に最も近い第二の輪郭線上の点を結合する線として第一の三角形の辺を設定する段階；
c) 第二の輪郭線上の点から該第一の輪郭線上の点に隣接する第一の輪郭線上の隣接点までの第一の距離を、第二の輪郭線上の隣接点から該第一の輪郭線上の点までの第二の距離と比較する段階；
d) 該比較段階に基づいて、第一および第二の距離のうちの短い方を結合する線として第二の三角形の辺を設定し、第一の輪郭線上の点と隣接点か、または第二の輪郭線上の点と隣接点のいずれかを結合する線として第三の三角形の辺を設定する段階；
e) 第二の輪郭線上の点についての重心ベクトルに対する第一の輪郭線上の点についての重心ベクトルの方位をチェックする段階であって、方位が90度より大きければ表面形状は間違っており、そうでなければ表面形状は正しく；該方位は、第一の輪郭線上の点の重心ベクトルと第二の輪郭線上の点の重心ベクトルのドット積を計算することによって決定され、負のドット積が90度超の方位に対応する段階；ならびに
f) 第一および第二の輪郭線上の全ての点が第一および第二の輪郭線の他方の線上の別の点に結合されるまで、第一の輪郭線または第二の輪郭線のいずれかの上で時計回り方向または反時計回り方向のいずれかで次の点まで移動することにより、段階a)〜e)を反復する段階。
【請求項１５】
以下を含む、複数の輪郭線から物体の表面形状を再構築するための器具：
スキャンデータを得てスキャンデータをセグメント化するために物体をスキャンすることによって、複数の輪郭線を得るように構成されたスキャナユニットと、
セグメント化したスキャンデータから得られた複数の輪郭線の各々に点を割当てるように構成された割当てユニットであって、該輪郭線の各々が閉じられ、他の輪郭線に対して交差していない、割当てユニットと、
近接して位置している2本の輪郭線上のそれぞれの点に対して第一の三角形分割スキームを実施し、該近接して位置している2本の輪郭線に対応する物体の一部分についての第一の表面形状を決定するように構成された、第一の三角形分割計算ユニットと、
第一の表面形状をチェックして、第一の表面形状が間違っているか否かを決定するように構成されたチェックユニットと、
第一の表面形状が間違っていることをチェックユニットが決定する場合に、近接して位置している2本の輪郭線上のそれぞれの点に対して第二の三角形分割スキームを実施し、該近接して位置している2本の輪郭線に対応する物体の一部分についての第二の表面形状を決定するように構成された、第二の三角形分割計算ユニットと、
物体の該部分についての再構築された表面形状として、第一の三角形分割計算ユニットによる出力としての第一の表面形状かまたは第二の三角形分割計算ユニットによる出力としての第二の表面形状のいずれかを出力し表示するように構成された、出力および表示ユニット。
【請求項１６】
第一の三角形分割計算ユニットが最短距離三角形分割を実施し、第二の三角形分割計算ユニットが最近接方位三角形分割を実施する、請求項15記載の器具。
【請求項１７】
チェックユニットが以下を含む、請求項15記載の器具：
第一の表面形状の複数の輪郭線のうち隣接する2つの線上の結合された点のそれぞれの重心ベクトルを計算するよう構成された計算ユニット；
計算する段階において計算されたそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いているか否かを決定するよう構成された第一の決定ユニット；および
複数の輪郭線のうち隣接する2つの線のそれぞれの重心ベクトルが互いに異なる少なくとも所定の角度の量である方向を向いている場合に第一の表面形状が間違っていることを決定するよう構成された第二の決定ユニット。
【請求項１８】
物体が患者の骨構造を含む、請求項15記載の器具。
【請求項１９】
互いの上部に積み重なっている三角形分割された輪郭の多数の対から物体のモデルを作製するように構成されている物体モデル作製ユニットをさらに含む、請求項15記載の器具。
【国際調査報告】
2009535693.tif 000022
2009535693.tif 000023