(57)【要約】【課題】３次元形状復元計算の並列化に当たり、並列オーバーヘッドを抑制できるようにする。【解決手段】複数のカメラから画像を入力し（ステップＳ１０１）、各計算ノードにおいて、入力シルエットの計算を行い（ステップＳ１０２）、全体の復元区域をすべての計算ノードに割当て（ステップＳ１０３）、各計算ノードにおいて、ひとつの復元区域を計算対象として選び（ステップＳ１０４）、各計算ノードにおいて、選ばれた復元区域について、有効カメラか否かを判定し（ステップＳ１０５）、有効カメラの計算ノードからそうでない計算ノードへシルエットの転送を行い（ステップＳ１０６）、各計算ノードにおいて、視体積の計算を行い（ステップＳ１０７）、前記Ｓ１０４〜Ｓ１０７をすべての復元区域について、繰り返し行うことで、全体の視体積の計算を行う。【選択図】図２
2010134546.tif 000002
【特許請求の範囲】
【請求項１】
視体積交差法により得た視体積データに基づいて３次元形状を復元する３次元形状復元装置であって、
視体積計算における複数の計算ノードに対応し、複数の視点で画像を入力する画像入力手段と、
前記入力された画像からシルエット画像を計算する入力シルエット計算手段と、
復元区域単位ですべての視体積の計算を前記すべての計算ノードに割り当てる復元区域計算ノード割り当て手段と、
各計算ノードにおいて、前記復元区域計算ノード割り当て手段により割り当てられた復元区域を計算対象として選択する復元区域選択手段と、
各計算ノードにおいて、前記復元区域選択手段により選択された復元区域にとってローカルにその区域が撮影されたシルエット画像を持つか否かを、前記入力シルエット計算手段で計算されたシルエット画像に基づいて判定する復元区域シルエットのローカル判定手段と、
前記復元区域シルエットのローカル判定手段によって、その区域が撮影されたシルエット画像を持たない復元区域であると判定された場合に、当該復元区域に割り当てられた計算ノードに対して、シルエット画像を持つ復元区域に割り当てられた計算ノードから、前記入力シルエット計算手段により計算されたシルエット画像を転送するシルエット共有手段と、
各計算ノードにおいて、前記シルエット画像を用いて該当復元区域に対応した視体積を並列に計算する視体積計算手段と、を備えたことを特徴とする視体積交差法による３次元形状復元装置。
【請求項２】
前記復元区域計算ノード割り当て手段は、前記複数の計算ノードのうち、ある計算ノードに対応する画像入力手段の視野に入っている復元区域を他の計算ノードに割り当てて、各ノードの割り当てられる復元区域を均等化することを特徴とする請求項１に記載の視体積交差法による３次元形状復元装置。
【請求項３】
視体積交差法により得た視体積データに基づいて３次元形状を復元する３次元形状復元方法であって、
画像入力手段が、視体積計算における複数の計算ノードに対応し、複数の視点で画像を入力する画像入力ステップと、
入力シルエット計算手段が、前記入力された画像からシルエット画像を計算する入力シルエット計算ステップと、
復元区域計算ノード割り当て手段が、復元区域単位ですべての視体積の計算を前記すべての計算ノードに割り当てる復元区域計算ノード割り当てステップと、
復元区域選択手段が、各計算ノードにおいて、前記復元区域計算ノード割り当て手段により割り当てられた復元区域を計算対象として選択する復元区域選択ステップと、
復元区域シルエットのローカル判定手段が、各計算ノードにおいて、前記復元区域選択手段により選択された復元区域にとってローカルにその区域が撮影されたシルエット画像を持つか否かを、前記入力シルエット計算手段で計算されたシルエット画像に基づいて判定する復元区域シルエットのローカル判定ステップと、
シルエット共有手段が、前記復元区域シルエットのローカル判定手段によって、その区域が撮影されたシルエット画像を持たない復元区域であると判定された場合に、当該復元区域に割り当てられた計算ノードに対して、シルエット画像を持つ復元区域に割り当てられた計算ノードから、前記入力シルエット計算手段により計算されたシルエット画像を転送するシルエット共有ステップと、
視体積計算手段が、各計算ノードにおいて、前記シルエット画像を用いて該当復元区域に対応した視体積を並列に計算する視体積計算ステップとを備え、
前記復元区域選択ステップ、復元区域シルエットのローカル判定ステップ、シルエット共有ステップおよび視体積計算ステップを、すべての復元区域について繰り返し実行して全体の視体積を求めることを特徴とする視体積交差法による３次元形状復元方法。
【請求項４】
前記復元区域計算ノード割り当てステップは、前記複数の計算ノードのうち、ある計算ノードに対応する画像入力手段の視野に入っている復元区域を他の計算ノードに割り当てて、各ノードの割り当てられる復元区域を均等化することを特徴とする請求項３に記載の視体積交差法による３次元形状復元方法。
【請求項５】
コンピュータを請求項１又は２に記載の各手段として機能させる視体積交差法による３次元形状復元プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カメラを視覚センサーとして用いるロボットビジョン、マシンビジョン分野や、高臨場感映像通信の３次元撮影に利用される視体積交差法による３次元形状復元装置、方法、プログラムに関する。
【背景技術】
【０００２】
動的物体、とりわけ、動く人体の３次元形状データは人物の姿勢推定、動き解析、行動理解といった研究分野に広く利用されているだけでなく、高臨場感マンマシンインターフェースの実現、ゲーム、映画撮影等、エンターテイメントの応用分野でも効果的な表現素材として注目を集めている。
【０００３】
詳細な３次元形状を計算する代表的な従来方法として視体積交差法という計算手法が提案され、近年それに基づくシステムが数多く開発されている。
【０００４】
図４に視体積交差法の基本原理を示す。図４（ａ）のように、対象物体（Ｃ）を撮影すると、撮像面（Ｓ）に対象の２次元シルエット（ＤA）が得られる。カメラの投影中心（ＰA）からシルエットの輪郭上の各点を通すように、３次元空間中に広がる錐体（ＶA）が考えられる。この錐体のことを該当するカメラによる対象の「視体積」と呼ぶ。これを図４（ｂ）に示す。さらに、図４（ｃ）に、複数の視体積の共通領域、すなわち視体積の交差（ＶＨ：Ｖｉｓｕａｌ  Ｈｕｌｌ）を求めることによって、対象の３次元形状が求まることを示す。
【０００５】
一方、３次元形状の表現として、ボクセル表現というものが考えられている。ボクセル表現では、３次元空間を複数のボクセルと呼ばれる小さい立方体に分割し、対象が占める空間領域に含まれるボクセルの集合をもって、対象の３次元形状を表す。
【０００６】
なお、視体積交差法について、下記の参考文献１〜３に詳細に記述されている。非特許文献１においては、２次元シルエット拘束の原理を説明し、視体積交差法の基本アルゴリズムについて記載されている。非特許文献２においては、視体積交差法におけるボクセル投影を高速演算するアルゴリズムおよび視体積交差法の並列化処理手法について記載されている。非特許文献３においては、視体積交差法の応用として、高精細３次元ビデオの実現について記載されている。
【０００７】
従来技術では、実時間で視体積交差法の計算を行うため、計算コストがもっとも高い各カメラの視体積の計算を並列計算によって高速化を図る。具体的には、あらかじめ決められた復元範囲に含む各カメラの視体積の計算量を複数の計算ノードに均等に分け、並列化計算を行う。前記非特許文献２では、復元範囲（３次元空間）を密な平行平面群で表現し、視体積の計算をすべての平面上の射影計算で行うようにしている。並列化に関して、平面群を均等に複数の計算ノードに割り当て、各計算ノードが並列に計算を行うようにしている。
【０００８】
従来における３次元形状復元の計算手法の流れを図５に示す。以下に各ステップの処理の概要について述べる。説明の便宜上、１台のカメラが１台の計算ノードに接続されるとする。尚、以下の説明において、例えば「ステップＳ５０１」を単に「Ｓ５０１」と省略して記載する。
【０００９】
Ｓ５０１：複数のカメラから画像を入力する。  
【００１０】
Ｓ５０２：各計算ノードにおいて、入力シルエットの計算を行う。  
【００１１】
Ｓ５０３：ひとつの復元区域を計算対象として選ぶ。  
【００１２】
Ｓ５０４：各計算ノードにおいて、選択した復元区域に対応したシルエットを切り出す。  
【００１３】
Ｓ５０５：複数の視体積（ＶＣ：Ｖｉｓｕａｌ  Ｃｏｎｅ）の計算量を均等にすべての計算ノードに割当てる。  
【００１４】
Ｓ５０６：計算ノード間の通信により、すべての計算ノード間で、Ｓ５０４で切出したシルエットが共有されるようにする。  
【００１５】
Ｓ５０７：Ｓ５０５で割当てられた計算を各計算ノードにおいて行う。
【００１６】
すべての復元区域について、Ｓ５０３〜Ｓ５０７を繰り返すことで、全復元空間に含まれるすべてのカメラに対応した視体積の計算が行える。次に各ステップの処理の詳細を以下に述べる。
【００１７】
Ｓ５０１  各計算ノードにおいて、接続されたカメラを制御し、同時に多視点から複数の画像を各計算ノードに取り込む。説明の便宜上、１台の計算ノードに１台のカメラを接続するとしたが、複数のカメラを接続しても処理は同じである。
【００１８】
Ｓ５０２  各計算ノードにおいて、入力画像により対象シルエット画像の計算を行う。具体的には、一例として、背景差分などで行う。
【００１９】
Ｓ５０３  あらかじめ、全体の復元空間を複数の復元区域に分割しておく。一例として、複数の同一サイズの立方体に分割したとする。ここでは、これら分割して得られた復元区域のうち、ひとつを計算対象に選ぶ。
【００２０】
Ｓ５０４  Ｓ５０３において選ばれた復元区域に対し、各計算ノードにおいて、該当復元区域を入力画像面に投影し、投影された画像上の２次元領域に含まれるシルエットを切出す。
【００２１】
Ｓ５０５  復元区域と対象の位置によって、有効カメラ、すなわち、視体積の計算に有効なシルエットが得られるカメラとそうでないカメラに分かれる。図６がその一例を示している。図６はある時刻における入力カメラと復元区域の関係を表した模式図である。横方向にカメラ番号を示し、縦方向に複数の復元区域の番号を示す。前記各復元区域について、図７に示すように復元区域が視野に入っている場合、対応するカメラのマス目を灰色で塗り、“区域番号，カメラ番号”のようなラベルをつけた。１台の有効カメラにつき、ひとつの視体積を計算する必要があるため、有効カメラの台数に応じて、該当復元区域の視体積の計算量が決まる。Ｓ５０３において選ばれた復元区域に対し、すべての視体積の計算量をすべての計算ノードに均等に割当てる。すなわち、有効でないカメラが接続された計算ノードにも計算タスクを割当てる。このように割り当てられた計算ノード番号と復元区域番号の関係を図８の模式図に示す。
【００２２】
Ｓ５０６  有効でないカメラが接続された計算ノードにおいて、割当てられた視体積の計算タスクが実行できるように、有効カメラが接続された計算ノードから、対象のシルエット画像を通信によって送受信する。これをシルエットの共有と呼ぶ。
【００２３】
Ｓ５０７  各計算ノードにおいて、割当てられた視体積の計算を並行に行う。
【非特許文献１】Ａ．Ｌａｕｒｅｎｔｉｎｉ，“Ｈｏｗ  Ｆａｒ  ３Ｄ  Ｓｈａｐｅｓ  Ｃａｎ  Ｂｅ  Ｕｎｄｅｒｓｔｏｏｄ  ｆｒｏｍ  ２Ｄ  Ｓｉｌｈｏｕｅｔｔｅｓ”，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，１７（２）：１８８−１９５，１９９５．
【非特許文献２】ウ小軍，和田俊和，東海彰吾，松山隆司，“平面間透視投影を用いた並列視体積交差法”，情報処理学会論文誌：コンピュータビジョンとイメージメディア，Ｖｏｌ．４２  Ｎｏ．ＳＩＧ６（ＣＶＩＭ２），２００１年６月
【非特許文献３】Ｔ．Ｍａｔｓｕｙａｍａ，Ｘ．Ｗｕ，Ｔ．Ｔａｋａｉ，Ｓ．Ｎｏｂｕｈａｒａ，“Ｒｅａｌ−Ｔｉｍｅ  ３Ｄ  Ｓｈａｐｅ  Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ，Ｄｙｎａｍｉｃ  ３Ｄ  Ｍｅｓｈ  Ｄｅｆｏｒｍａｔｉｏｎ，ａｎｄ  Ｈｉｇｈ  Ｆｉｄｅｌｉｔｙ  Ｖｉｓｕａｌｉｚａｔｉｏｎ  ｆｏｒ  ３Ｄ  Ｖｉｄｅｏ”，Ｓｐｅｃｉａｌ  Ｉｓｓｕｅ“Ｍｏｄｅｌ−ｂａｓｅｄ  ａｎｄ  Ｉｍａｇｅ−ｂａｓｅｄ  ３Ｄ  Ｓｃｅｎｅ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ”，Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｉｍａｇｅ  Ｕｎｄｅｒｓｔａｎｄｉｎｇ，ｐｐ．３９３−４３４，２００４．
【発明の開示】
【発明が解決しようとする課題】
【００２４】
復元範囲が限られる場合、上記並列化の手法は有効であった。しかし、復元範囲が広くなると、全体の計算量がさらに膨大になる。計算量を抑えるため、全体の復元範囲をあらかじめ複数の区域にわけ、対象の存在領域についてのみ、詳細復元を行うことで計算効率の向上が図れる。従来の並列化の手法を複数復元区間に適用すると、並列化のためのオーバーヘッドが大きくなり、余分な時間がかかってしまう。
【００２５】
すなわち、図５で述べた従来の、各復元区域について計算量を分割する方法では、各復元区域を均等に各計算ノードに割り当てたため、図８に示すように計算量のロードバランスが図れたが、個々の復元区域の計算の間に並列化のためのオーバーヘッドが発生（計算ループごとに通信によるオーバーヘッドが発生）している。復元区域の数が計算ノードよりはるかに多くなる場合、すなわち全復元範囲が広くなる場合、オーバーヘッドが無視できなくなり、計算効率の妨げとなる。
【００２６】
本発明は上記課題を解決するものであり、その目的は、例えば多視点からのマルチカメラを用いた動的物体の３次元形状復元計算の並列化に当たり、計算量を動的かつ効率的に各計算ノードに分けて余分な画像転送を減らし、並列オーバーヘッドを抑えることによって、効率的な並列計算システムの構築を可能とし、実時間３次元映像入力装置の実現を可能とした視体積交差法による３次元形状復元装置、３次元形状復元方法および３次元形状復元プログラムを提供することにある。
【課題を解決するための手段】
【００２７】
上記課題を解決するために、請求項１に記載の視体積交差法による３次元形状復元装置は、視体積交差法により得た視体積データに基づいて３次元形状を復元する３次元形状復元装置であって、視体積計算における複数の計算モードに対応し、複数の視点で画像を入力する画像入力手段と、前記入力された画像からシルエット画像を計算する入力シルエット計算手段と、復元区域単位ですべての視体積の計算を前記すべての計算ノードに割り当てる復元区域計算ノード割り当て手段と、各計算ノードにおいて、前記復元区域計算ノード割り当て手段により割り当てられた復元区域を計算対象として選択する復元区域選択手段と、各計算ノードにおいて、前記復元区域選択手段により選択された復元区域にとってローカルにその区域が撮影されたシルエット画像を持つか否かを、前記入力シルエット計算手段で計算されたシルエット画像に基づいて判定する復元区域シルエットのローカル判定手段と、前記復元区域シルエットのローカル判定手段によって、その区域が撮影されたシルエット画像を持たない復元区域であると判定された場合に、当該復元区域に割り当てられた計算ノードに対して、シルエット画像を持つ復元区域に割り当てられた計算ノードから、前記入力シルエット計算手段により計算されたシルエット画像を転送するシルエット共有手段と、各計算ノードにおいて、前記シルエット画像を用いて該当復元区域に対応した視体積を並列に計算する視体積計算手段と、を備えたことを特徴としている。
【００２８】
また請求項２に記載の視体積交差法による３次元形状復元装置は、請求項１において、前記復元区域計算ノード割り当て手段は、前記複数の計算ノードのうち、ある計算ノードに対応する画像入力手段の視野に入っている復元区域を他の計算ノードに割り当てて、各ノードの割り当てられる復元区域を均等化することを特徴としている。
【００２９】
また、請求項３に記載の視体積交差法による３次元形状復元方法は、視体積交差法により得た視体積データに基づいて３次元形状を復元する３次元形状復元方法であって、画像入力手段が、視体積計算における複数の計算ノードに対応し、複数の視点で画像を入力する画像入力ステップと、入力シルエット計算手段が、前記入力された画像からシルエット画像を計算する入力シルエット計算ステップと、復元区域計算ノード割り当て手段が、復元区域単位ですべての視体積の計算を前記すべての計算ノードに割り当てる復元区域計算ノード割り当てステップと、復元区域選択手段が、各計算ノードにおいて、前記復元区域計算ノード割り当て手段により割り当てられた復元区域を計算対象として選択する復元区域選択ステップと、復元区域シルエットのローカル判定手段が、各計算ノードにおいて、前記復元区域選択手段により選択された復元区域にとってローカルにその区域が撮影されたシルエット画像を持つか否かを、前記入力シルエット計算手段で計算されたシルエット画像に基づいて判定する復元区域シルエットのローカル判定ステップと、シルエット共有手段が、前記復元区域シルエットのローカル判定手段によって、その区域が撮影されたシルエット画像を持たない復元区域であると判定された場合に、当該復元区域に割り当てられた計算ノードに対して、シルエット画像を持つ復元区域に割り当てられた計算ノードから、前記入力シルエット計算手段により計算されたシルエット画像を転送するシルエット共有ステップと、視体積計算手段が、各計算ノードにおいて、前記シルエット画像を用いて該当復元区域に対応した視体積を並列に計算する視体積計算ステップとを備え、前記復元区域選択ステップ、復元区域シルエットのローカル判定ステップ、シルエット共有ステップおよび視体積計算ステップを、すべての復元区域について繰り返し実行して全体の視体積を求めることを特徴としている。
【００３０】
また請求項４に記載の視体積交差法による３次元形状復元方法は、請求項３において、前記復元区域計算ノード割り当てステップは、前記複数の計算ノードのうち、ある計算ノードに対応する画像入力手段の視野に入っている復元区域を他の計算ノードに割り当てて、各ノードの割り当てられる復元区域を均等化することを特徴としている。
【００３１】
また、請求項５に記載の視体積交差法による３次元形状復元プログラムは、コンピュータを請求項１又は２に記載の各手段として機能させる視体積交差法による３次元形状復元プログラムである。
【発明の効果】
【００３２】
本発明によれば、視体積交差法による３次元形状復元装置、方法、ブログラムにおいて、並列計算に伴うオーバーヘッドの発生が、復元空間の広がりにより大きくなることを防ぐことができる。このため、広範囲な視体積交差法も効率的に並列化でき、全体の計算時間を大幅に削減できるメリットを有している。
【発明を実施するための最良の形態】
【００３３】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。図１は本発明の視体積交差法による３次元形状復元装置の実施形態例を示す構成図であり、図２は本発明の視体積交差法による３次元形状復元方法の実施形態例を示すフローチャートである。
【００３４】
図１の装置を構成する各ブロック（１０１〜１０７）の名称、入力、出力と、図２の各ステップ（Ｓ１０１〜Ｓ１０７）の概要を次の表１に示す。
【００３５】
【表１】
2010134546.tif 000003
【００３６】
次に図１の装置の詳細を説明する。図１において、１０１は、視体積計算における複数の計算ノードに対応し、複数の視点で画像を入力する、例えばカメラなどの画像入力手段である。
【００３７】
１０２は、前記入力された画像からシルエット画像を計算する入力シルエット計算手段である。
【００３８】
１０３は、復元区域単位ですべての視体積の計算を前記すべての計算ノードに割り当てる復元区域計算ノード割り当て手段であり、復元区域番号集合を出力する。
【００３９】
１０４は、各計算ノードにおいて、前記復元区域計算ノード割り当て手段１０３により割り当てられた復元区域を計算対象として選択する復元区域選択手段であり、入力された復元区域番号集合から選択した復元区域番号を出力する。
【００４０】
１０５は、各計算ノードにおいて、前記復元区域選択手段１０４により選択された復元区域にとってローカルにその区域が撮影されたシルエット画像を持つか否かを、前記入力シルエット計算手段１０２で計算されたシルエット画像に基づいて判定する復元区域シルエットのローカル判定手段であり、前記復元区域番号およびシルエット画像を入力とし、復元区域番号およびシルエット画像を出力とする。
【００４１】
１０６は、前記復元区域シルエットのローカル判定手段１０５によって、その区域が撮影されたシルエット画像を持たない復元区域であると判定された場合に、当該復元区域に割り当てられた計算ノードに対して、シルエット画像を持つ復元区域に割り当てられた計算ノードから、前記入力シルエット計算手段１０２により計算されたシルエット画像を転送するシルエット共有手段であり、前記シルエット画像および復元区域番号を入力とし、シルエット画像を出力とする。
【００４２】
１０７は、各計算ノードにおいて、前記シルエット画像を用いて該当復元区域に対応した視体積を並列に計算する視体積計算手段であり、前記シルエット画像を入力とし、視体積データを出力とする。
【００４３】
この視体積計算手段１０７の出力データ（視体積データ）により３次元形状が復元される。
【００４４】
前記画像入力手段１０１、入力シルエット計算手段１０２、復元区域選択手段１０４、復元区域シルエットのローカル判定手段１０５および視体積計算手段１０７は各々複数設けられ、復元区域計算ノード割り当て手段１０３およびシルエット共有手段１０６は各々単数設けられている。
【００４５】
前記各手段１０２〜１０７の各機能は例えばコンピュータによって達成される。
【００４６】
次に図１の装置の動作を図２のフローチャートに沿って説明する。
【００４７】
Ｓ１０１：複数のカメラ（画像入力手段１０１）から画像を入力する。  
【００４８】
Ｓ１０２：各計算ノードにおいて、入力シルエット計算手段１０２が入力シルエットの計算を行う。  
【００４９】
Ｓ１０３：復元区域計算ノード割り当て手段１０３が、全体の復元区域をすべての計算ノードに割当てる。  
【００５０】
Ｓ１０４：復元区域選択手段１０４が、各計算ノードにおいて、ひとつの復元区域を計算対象として選ぶ。  
【００５１】
Ｓ１０５：復元区域シルエットのローカル判定手段１０５が、各計算ノードにおいて、選ばれた復元区域について、有効カメラか否かを判定する。  
【００５２】
Ｓ１０６：シルエット共有手段１０６が、有効カメラの計算ノードからそうでない計算ノードへシルエットの転送を行う。  
【００５３】
Ｓ１０７：視体積計算手段１０７が、各計算ノードにおいて、視体積の計算を行う。
【００５４】
前記Ｓ１０４〜Ｓ１０７をすべての復元区域について、繰り返し行うことで、全体の視体積の計算を行う。各ステップについて、以下に詳細を述べる。
【００５５】
Ｓ１０１  このステップは図５のＳ５０１と同じ処理を行う。
【００５６】
Ｓ１０２  このステップは図５のＳ５０２と同じ処理を行う。
【００５７】
Ｓ１０３  図６に示すように、計算ノードが復元区域にとって、有効カメラが接続される場合とそうでない場合に分かれる。ここでは、復元区域単位ですべての視体積の計算をすべての計算ノードに割当てる。定式化のため、表記を次のように定義する。
【００５８】
復元区域をｄi，ｉ＝１，２，．．．，ｎで表す。カメラ＝計算ノードをｃj，ｊ＝１，２，．．．，ｍで表す。復元区域ｄiにとって、カメラｃjが有効なカメラである場合、（ｄi，ｃj）でｄiに対するｃjの入力からの計算量を表す。（ｄi，ｃj）が割り当てる計算量の単位であり、それらの集合が全計算量を表し、それをＶ＝{（ｄi，ｃj）}で表す。
【００５９】
次に、個々の計算ノードについて、計算量の集合Ｃ（ｋ）＝{（ｄi，ｃj）｜ｊ＝ｋ}を定義する。明らかに、次の式（１）が成り立つ。
【００６０】
【数１】
2010134546.tif 000004
【００６１】
また、計算量を割り当てた結果、個々の計算ノードに当てられた計算量の集合をＳ（ｋ）と定義する。従って、上記割り当て問題は如何にＳ（ｋ）を決めるかという問題になる。Ｎを集合Ｖの要素数とする。ｎ（ｋ）を集合Ｃ（ｋ）の要素数とする。
【００６２】
【数２】
2010134546.tif 000005
【００６３】
個々の計算ノードになるべく均等に計算量を割り当てる処理の一例として、次の処理の処理方法を示す。ただし、Λで割り当てる候補集合を表し、初期値として、Λ＝Ｖである。Φで空集合を表す。
【００６４】
【数３】
2010134546.tif 000006
【００６５】
【数４】
2010134546.tif 000007
【００６６】
【数５】
2010134546.tif 000008
【００６７】
４．終了する。
【００６８】
具体的な割り当て結果として、次のような例を示す。図６にあるような模式図に対し、図３のような割当て方を行う。図６から、計算ノード１番が有効カメラとなる復元区域が１，６，８，１０、計４区域であるのに対し、計算ノード４番が有効カメラとなる復元区域が１，２，３，４，６，７，８，１０，１１、計９区域である。そこで、割当て方針として、計算ノード４の計算量をほかの計算ノードに分担させることで、すべての計算ノードの計算量の均衡を図る。結果、図３のような割当て方が実現できる。
【００６９】
Ｓ１０４  各計算ノードにおいて、前記復元区域計算ノード割り当て手段１０３に割当てられた復元区域を１つ選択する。
【００７０】
Ｓ１０５  各計算ノードにおいて、選ばれた復元区域にとってローカルにその区域が撮影されたシルエット画像を持つか否かを判定する。すなわち、該当復元区域にとって有効カメラであるか否かを判定する。有効カメラの場合、Ｓ１０７へ、そうでない場合Ｓ１０６へそれぞれ進む。
【００７１】
Ｓ１０６  該当復元区域にとって、計算ノードに有効カメラが接続されていなかったため、有効カメラの計算ノードから必要なシルエットの送受信を行う。
【００７２】
Ｓ１０７  各計算ノードにおいて、該当復元区域に対応した視体積を並列に計算する。
【００７３】
以上のように図３と図８のそれぞれの模式図を比べると、本実施形態例によれば、オーバーヘッドの発生回数が抑えられることがわかる。
【００７４】
また、本実施形態の視体積交差法による３次元形状復元装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の視体積交差法による３次元形状復元方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標）  Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【図面の簡単な説明】
【００７５】
【図１】本発明の視体積交差法による３次元形状復元装置の実施形態例を示す構成図。
【図２】本発明の視体積交差法による３次元形状復元方法の実施形態例を示すフローチャート。
【図３】本発明の実施形態例による、計算ノードに復元区域の計算量を均等に分配する並列法を説明する模式図。
【図４】本発明で用いる視体積交差法の原理を示す説明図。
【図５】従来手法の処理を示すフローチャート。
【図６】ある時刻における入力カメラと復元区域の関係の一例を説明する模式図。
【図７】カメラの視野と復元区域の関係を示す説明図。
【図８】従来の、復元区域ごとの計算量を均等に計算ノードに割当てる並列法を説明する模式図。
【符号の説明】
【００７６】
１０１…画像入力手段
１０２…入力シルエット計算手段
１０３…復元区域計算ノード割り当て手段
１０４…復元区域選択手段
１０５…復元区域シルエットのローカル判定手段
１０６…シルエット共有手段
１０７…視体積計算手段
【図１】
2010134546.tif 000009
【図２】
2010134546.tif 000010
【図５】
2010134546.tif 000011
【図３】
2010134546.tif 000012
【図４】
2010134546.tif 000013
【図６】
2010134546.tif 000014
【図７】
2010134546.tif 000015
【図８】
2010134546.tif 000016