JP4550221B2

JP4550221B2 - 三次元空間再構成装置及び三次元空間再構成方法

Info

Publication number: JP4550221B2
Application number: JP2000122645A
Authority: JP
Inventors: 省吾濱崎; 裕之吉田
Original assignee: Japan Science and Technology Agency; Panasonic Corp; National Institute of Japan Science and Technology Agency; Matsushita Electric Industrial Co Ltd
Current assignee: Japan Science and Technology Agency; Panasonic Corp; National Institute of Japan Science and Technology Agency; Panasonic Holdings Corp
Priority date: 2000-04-24
Filing date: 2000-04-24
Publication date: 2010-09-22
Anticipated expiration: 2020-04-24
Also published as: JP2001307073A

Description

【０００１】
【発明の属する技術分野】
本発明は、視体積交差法を用い、最小ボクセルで対象物体の三次元形状を再構成する三次元空間再構成装置及びその方法に関するものである。
【０００２】
【従来の技術】
視体積交差法（ＶｏｌｕｍｅＩｎｔｅｒｓｅｃｔｉｏｎＭｅｔｈｏｄ）を用いた、三次元空間再構成法の従来例として、米国カリフォルニア大学のＳＡＩＥＤＭＯＥＺＺＩらの文献「ＶｉｒｔｕａｌＶｉｅｗｇｅｎｅｒａｔｉｏｎｆｏｒ３ＤＤｉｇｉｔａｌＶｉｄｅｏ」（ＩＥＥＥＭＵＬＴＩＭＥＤＩＡＶｏｌ．４Ｎｏ．１ｐｐ．１８−２６、１９９７年）がある。
【０００３】
このものでは、対象物体が入る測定対象空間を、小さな立方体（ボクセル）で分割して考える。即ち、測定対象空間を、このボクセル（本発明の「最小ボクセル」に相当）が、ＸＹＺ方向にすき間無く積み上げられた空間として扱う。また、このボクセルの一辺の長さは、測定の解像度を決定するものであり、一辺の長さを小さくするほど、測定の解像度は向上し、一辺の長さを大きくするほど、測定の解像度は低下する。
【０００４】
ここで、測定対象空間のＸＹＺ方向のそれぞれの長さが、ボクセルの一辺の長さのＸＬ倍、ＹＬ倍、ＺＬ倍であったとすると、測定対象空間は、ＸＬ×ＹＬ×ＺＬ個のボクセルで満たされた空間であるということになる。
【０００５】
そして、視体積交差法では、これらＸＬ×ＹＬ×ＺＬ個の全てのボクセルについて、該当ボクセルが対象物体の内部にあるか否かを、しらみつぶしに調べる（調査回数：ＸＬ×ＹＬ×ＺＬ回）。調査の結果、対象物体の内部にあるとされたボクセルの塊で、いわば積み木を積むように、対象物体の三次元形状を再構成する。
【０００６】
より具体的には、図１８に示すように、視点１〜視点ｎ（通常ｎ≧３）を持つように、複数のカメラをセットし、互いに異なる方向から対象物体を撮影する。
【０００７】
これにより、各カメラの画像面には、対象物体のシルエットが撮影される。ボクセルの状態（ボクセルと対象物体とが重なり合うか否か）は、ボクセルに対応する画素が、シルエットに含まれているか否かで判定できる。
【０００８】
例えば、対象物体の外にあるボクセルＡに対応する画素は、少なくとも１つのカメラ画像において、シルエットの外部にある（図１８では、画像面１においてシルエットの外部にある）。また、対象物体の内部にあるボクセルＢに対応する画素は、全てのカメラ画像において、シルエットの内部にある。
【０００９】
つまり、あるボクセルに対応する画素が、全てのカメラ画像において、対象物体のシルエットに含まれていれば、そのボクセルは、対象物体の内部に有ることになる。逆に、いずれかのカメラ画像において、ボクセルに対応する画素が、対象物体のシルエットに含まれていなければ、そのボクセルは、対象物体の外部にあることになる。
【００１０】
なお、カメラのキャリブレーションが終了しており、カメラの位置、姿勢、焦点距離などのカメラパラメータが既知であれば、レンズ中心とボクセルの位置と画像面との位置関係から幾何学的に、ボクセルを画像面に投影した位置を、容易に求めることができる。
【００１１】
このための構成例を図１９に示す。図１９において、カメラ群等を備えた複数方向画像取得手段１は、複数の異なる視点及び方向で、対象物体を同時に撮影し、それらの画像データを出力する。
【００１２】
パラメータ保持手段２は、あらかじめ入力された複数方向画像取得手段１を構成する複数のカメラの位置・姿勢などの情報を保持している。
【００１３】
ボクセル状態テーブル保持手段３は、全てのボクセルの状態（ボクセルと対象物体とが重なり合うか否か）を保持する。
【００１４】
着目ボクセル発生手段４は、ＸＬ×ＹＬ×ＺＬ個のボクセルを、１つずつ順番に選び着目ボクセルとして出力する。
【００１５】
着目ボクセルの状態決定手段５は、着目ボクセル発生手段４が出力した着目ボクセルについて、複数方向画像取得手段１の画像データとパラメータ保持手段２に保持されている各カメラのパラメータから、上述した要領でボクセルの状態を決定し、ボクセル状態テーブル保持手段３の内容を更新する。
【００１６】
次に、図２０を用いて、処理例を説明する。まず、着目ボクセルの状態決定手段５は、初期化を行うため、ボクセル状態テーブル保持手段３をアクセスし、全てのボクセルの状態を”占有”（ボクセルと対象物体とが重なり合うという意）とする（ステップＳ１００１）。
【００１７】
次に、着目ボクセル発生手段４が、最初の着目ボクセルを定め（ステップＳ１００２）、着目ボクセルの状態決定手段５が、このボクセルの中心位置と、最初のカメラのレンズ中心とを結ぶ直線が画像面と交わる点にある、画素ｐを決定する（ステップＳ１００４）。
【００１８】
ステップＳ１００５では、着目ボクセルの状態決定手段５が、画素ｐが画像面にあるシルエットに含まれているか否かを判定し、画素ｐがシルエットに含まれていなければ、ボクセルの状態を”空”とし、次のボクセルの処理に移る（ステップＳ１００６）。含まれていれば、次のカメラについて、ステップＳ１００３以降の処理を繰り返す。
【００１９】
そして、全てのカメラで含まれていることになれば、状態は、”占有”のままとなり、そうでなければ、状態は、”空”となる。
【００２０】
そして、全てのボクセルについて、以上の処理を繰り返す（ステップＳ１００２）。
【００２１】
これら一連の処理が終わると、全ボクセルの状態が確定し、三次元空間が再構成されたことになる。
【００２２】
【発明が解決しようとする課題】
いま、現状の解像度では、測定精度が不十分であるとして、解像度を向上させるため、ボクセルの一辺の長さを、従前の１／４倍にしたものとする。すると、測定対象空間は、（４×ＸＬ）×（４×ＹＬ）×（４×ＺＬ）＝６４（ＸＬ×ＹＬ×ＺＬ）個のボクセルで満たされることになり、調査回数は、従前の６４倍にも膨張してしまう。
【００２３】
この例から明らかなように、従来技術において、実用的な解像度を得ようとすると、演算量が膨大になって、実時間処理を行うのが非常に困難になってしまうという問題点があった。
【００２４】
そこで本発明は、演算量を劇的に削減して、十分な解像度と高速処理を両立できる三次元空間再構成装置及びその方法を提供することを目的とする。
【００２５】
【課題を解決するための手段】
本発明では、測定対象空間内にある対象物体を、互いに異なる方向から撮像し、多数の最小ボクセルの塊により、対象物体を再構成するものであり、対象物体が入りきれない最大ボクセルを決定する最大ボクセル決定手段と、当初、測定対象空間を最大ボクセルで分割した複数のボクセルを分割ボクセルとして出力すると共に、当初以降、与えられたボクセルを一定個数に分割した分割ボクセルを出力するボクセル分割手段と、ボクセル分割手段が出力するそれぞれの分割ボクセルと対象物体とが、重なり合うか否かを決定するボクセル状態決定手段と、対象物体と重なり合うと決定された、分割ボクセルが、一定脱出条件を満たしていない場合、この分割ボクセルをボクセル分割手段に与えて、繰り返し分割させる制御手段とを備える。
【００２６】
この構成により、三次元空間再構成における、演算量を劇的に削減して、十分な解像度と高速処理を両立できる。
【００２７】
【発明の実施の形態】
第１の発明に係る三次元空間再構成装置では、測定対象空間内にある対象物体を、互いに異なる方向から撮像し、多数の最小ボクセルの塊により、対象物体を再構成するものであり、対象物体が入りきれない最大ボクセルを決定する最大ボクセル決定手段と、当初、測定対象空間を最大ボクセルで分割した複数のボクセルを分割ボクセルとして出力すると共に、当初以降、与えられたボクセルを一定個数に分割した分割ボクセルを出力するボクセル分割手段と、ボクセル分割手段が出力するそれぞれの分割ボクセルと対象物体とが、重なり合うか否かを決定するボクセル状態決定手段と、対象物体と重なり合うと決定された、分割ボクセルが、一定脱出条件を満たしていない場合、この分割ボクセルをボクセル分割手段に与えて、繰り返し分割させる制御手段とを備える。
【００２８】
この構成において、上述の最大ボクセルからはじめて、ボクセル分割を繰り返すことにより、空のボクセルの調査を削減し、大幅に演算量を削減できる。その結果、十分な解像度を得るため、最小ボクセルの一辺を小さくしても、実用にかなう処理時間で、対象物体の三次元空間を再構築できる。
【００２９】
第２の発明に係る三次元空間再構成装置では、一定脱出条件は、分割ボクセルと最小ボクセルのサイズが同じであることである。
【００３０】
この構成により、繰り返し処理が完了すれば、別途特段の処理をしなくとも、最小ボクセルの塊で、対象物体の三次元形状を再構成できる。
【００３１】
第３の発明に係る三次元空間再構成装置では、一定個数は、８である。
【００３２】
この構成により、ＸＹＺ方向に半分ずつ無理なく分割ができる。
【００３３】
第４の発明に係る三次元空間再構成装置では、ボクセル状態決定手段が、与えられたボクセルの表面付近のみを調べ、いずれかの表面付近に対象物体を検出できたとき、このボクセルと対象物体とが、重なり合うと決定する。
【００３４】
この構成により、分割ボクセルの内部の調査を省略して、演算量を一層削減できる。
【００３５】
第５の発明に係る三次元空間再構成装置では、ボクセル状態決定手段が、ボクセルの表面付近の一部を標本化して標本ボクセルを発生する標本ボクセル発生部を有し、標本ボクセルに基づいて、対象物体の検出を行う。
【００３６】
この構成により、標本化により演算対象を間引いて、演算量をさらに削減することができる。
【００３７】
第６の発明に係る三次元空間再構成装置では、標本ボクセルは、与えられたボクセルを最小ボクセルのサイズで均等に分割した複数のボクセルのいずれかである。
【００３８】
この構成により、標本ボクセルの状態と最小ボクセルの状態が同一になり、後に最小ボクセルまで分割した段階において、標本ボクセルと一致する最小ボクセルについて、状態の決定処理を省略することができ、それだけ演算量を削減できる。
【００３９】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００４０】
図１において、制御手段１０は、後述する各手段を制御する。特に、対象物体と重なり合うと決定された、分割ボクセルが、一定脱出条件を満たしていない場合、この分割ボクセルをボクセル分割手段１８に与えて、繰り返し分割させる。
【００４１】
入力手段１１は、オペレータの入力を受け付ける。
【００４２】
複数方向画像取得手段１２は、測定対象空間内にある対象物体を、互いに異なる方向・視点から撮像し、複数の画像データを出力する。
【００４３】
記憶手段１３は、制御手段１０が実行するプログラムや、必要に応じて、情報を一時記憶させるための領域の他、後述する繰り返しレベル毎に、各ボクセルの状態を保持するボクセル状態テーブル１４を有する。勿論、このようなテーブルにしなくとも、読み書きが自在である以上、リストなど他の周知のデータ構造を採用しても差し支えない。
【００４４】
パラメータ保持手段１５は、全てのカメラの位置・姿勢などのパラメータを保持する。
【００４５】
最大ボクセル決定手段１６は、対象物体が入りきれない最大ボクセルを決定する。
【００４６】
脱出条件判定手段１７は、制御手段１０が繰り返しボクセル分割手段１８を用いて分割ボクセルを再分割する際に参照する一定脱出条件（本例では、分割ボクセルが最小ボクセルと同じサイズになること）が満たされているか否かを判定する。なお、この脱出条件は、分割ボクセルが最小ボクセルの数倍になることなどと、変更しても良い。
【００４７】
ボクセル分割手段１８は、当初、測定対象空間を最大ボクセルで分割した複数のボクセルを分割ボクセルとして出力すると共に、当初以降、与えられたボクセルを一定個数に分割した分割ボクセルを出力する。
【００４８】
ボクセル状態決定手段１９は、ボクセル分割手段１８が出力する、それぞれの分割ボクセルと、対象物体とが、重なり合うか否かを決定する。本例では、ボクセル状態決定手段１９は、与えられたボクセルの表面付近のみを調べ、いずれかの表面付近に対象物体を検出できたとき、このボクセルと対象物体とが重なり合うと決定する。
【００４９】
また、ボクセル状態決定手段１９は、ボクセルの表面付近の一部を標本化して標本ボクセルを発生する標本ボクセル発生部２０を有し、標本ボクセルに基づいて、対象物体の検出を行う。
【００５０】
そして、標本ボクセル状態決定部２１は、標本ボクセル発生部２０が発生した標本ボクセルのみを調べ、標本ボクセルのうち、１つでも対象物体と重なり合うものが存在していれば、該当分割ボクセル（サイズは不問）と、対象物体とが、重なり合うと決定し、そうでないとき、該当分割ボクセルと対象物体とは、重なり合わないと決定する。
【００５１】
さらに具体的に説明すると、図３に示すようになる。即ち、測定対象空間Ｓ内に対象物体Ｏ（ここでは、人間であるとする）が存在するとき、複数方向画像取得手段１２で異なる方向から対象物体Ｏを撮像する。即ち、視点や方向が異なる、複数台（オクルージョンを防止するため、通常、４台以上が望ましい）のカメラ２２〜２６で、対象物体Ｏを撮像し、カメラ２２〜２６に接続されるキャプチャボード群２７により、画像データを情報処理装置へ取り込む。
【００５２】
情報処理装置は、入力手段としてのキーボード３２の他、各要素間でのデータ通信を仲介するバス２８、ＣＰＵ２９、メモリ３０及び外部記憶装置３１を備える。ここで、上述した各手段１０、１５〜１９は、ＣＰＵ２９が、記憶手段１３としてのメモリ３０、外部記憶装置３１に対して、読み書きを行い、後述するフローチャートに沿ったプログラムを実行することにより実現される。
【００５３】
次に、本発明の処理のあらましを説明する。本発明では、上述したように、対象物体が入りきれない「最大ボクセル」という概念を導入している。ここで、「最大」というように命名したのは、この「最大ボクセル」が、後述するボクセルの繰り返し分割の出発点であり、処理が進むと、分割ボクセルは、最大ボクセルから一段毎に小さくなってゆくからである。
【００５４】
これに対して、解像度を決定するボクセルを「最小ボクセル」と呼んでいる。
つまり、本発明において繰り返されるボクセル分割は、最大ボクセルのサイズで出発し、爾後、何段（以下の説明では、レベルで表現する）か分割が進む毎に小さくなってゆき、最小ボクセルへ至るという過程を経る。
【００５５】
ここで、本発明の処理を最も理想的な状態で実現するには、次の条件にかなう対象物体であることが望ましい。
（１）対象物体は変形可能であるが、全ての変形パターンで空間的に外接する立方体のうち、最小となる立方体（最小外接立方体）の大きさが既知である。
（２）対象物体の各部位を任意の面で切断した断面がその切断面上で外接する正方形を想定し、最小となる正方形（最小外接正方形）の大きさが既知である。
【００５６】
但し、以上の条件は、必須ではなく、最大ボクセルを比較的小さめに設定するだけでも、実用上十分な場合が多い。
【００５７】
ところで、図４は、人間を対象物体にする場合の、最大ボクセルＶ０の決定要領を示している。即ち、人間は、多数の関節を持ち、種々の姿勢をとりうるが、体をできるだけ小さく折り畳んでも、これ以上小さくできないという姿勢がある。そのとき、人間に外接する立方体よりも、やや小さい立方体を定め、これを最大ボクセルとする（一辺の長さ：Ｌ）。
【００５８】
そして、このように決めた最大ボクセルＶ０と人間との関係を注視すると、次のことがわかる。即ち、この最大ボクセルＶ０に人間は入りきれないのであるから、人間のある部分（図４の例では、頭とつま先の部分）は、最大ボクセルＶ０からはみ出さざるを得ない。
【００５９】
ここで、最大ボクセルＶ０は、６つの表面を有するが、これらの表面のいずれかによって、はみ出した人間の部分が切断されることになる。より詳しくは、最大ボクセルＶ０の表面に着目し、いずれかの表面に人間の部分が存在していれば、最大ボクセルＶ０の内部を見なくとも（調査を省略しても）、最大ボクセルＶ０の中に人間が存在している（つまり、最大ボクセルＶ０と人間とが重なり合っている）と断定できる。
【００６０】
逆に、最大ボクセルＶ０の全ての表面に人間の部分が存在していなければ、この最大ボクセルＶ０の中には、人間は存在していない（重なり合っていない）ことになる。
【００６１】
本発明は、以上の知見に基づいて、最大ボクセルＶ０を起点とし、これを繰り返し細分化するプロセスを利用することとしたのである。また、１つの最大ボクセルを調べる際には、その表面付近のみを調べ、内部の調査を省略することにより、調査回数を削減できる。
【００６２】
また、最大ボクセルＶ０またはおおきめの分割ボクセルと、対象物体とが、重なり合わないとされたとき、爾後の分割（つまりより詳しい調査）を行わないことにしたのである。
【００６３】
仮に、最大ボクセルＶ０が１０００個の最小ボクセルからなるとき、一度の調査で対象物体と重なり合わないとされれば、その後の調査を省略するのである。
これに対し、従来技術では、１０００個の最小ボクセルの全部をしらみつぶしに調査していたのであるから、本発明の手法は、従来技術に対して、はるかに有利であり、演算量を劇的に削減できることは、容易に理解されよう。
【００６４】
図５では、本発明による処理段階を模式的に表現している。当初、図５（ａ）に示すように、測定対象空間Ｓは、最大ボクセルＶ０と同じサイズの分割ボクセルで分けられる。このとき、図５（ｅ）に示すように、各分割ボクセルの表面付近のみを調べ、上述した知見により、各分割ボクセルと対象物体とが重なり合うかどうか決定する。
【００６５】
さらに、本例では、これらの表面の全部を調べるのではなく、格子状の標本化による好ましい間引きを行っており、表面付近の一部のみについてだけ調査を行っている。
【００６６】
次に、図５（ｂ）に示すように、対象物体と重なり合うもののみ取り扱い、分割ボクセルの分割と調査を繰り返し（図５（ｂ）のレベルから図５（ｃ）のレベルへ、図５（ｃ）のレベルから図５（ｄ）のレベルへ、…）、最終的に、最小ボクセルまで分割した時点で終了するものである。
【００６７】
以下、より具体的に説明する。まず、ボクセル状態テーブル１４は、図８のように構成する。即ち、ボクセル状態テーブル１４は、複数のレベル毎（図８（ａ）はレベル０で最大ボクセルのサイズ、図８（ｄ）はレベルＬｓで最小ボクセルのサイズ）のボクセル空間の状態テーブルで構成される。
【００６８】
各テーブルには、各ボクセル空間を構成するボクセルに、同一レベル内でユニークに付与された識別番号であるボクセル番号と、その状態が対応付けられている。
【００６９】
次に、最大ボクセルの大きさ、最小ボクセルのレベル、標本ボクセルの間隔等の決定要領を、具体的に説明する。これらのパラメータは、要求される空間分解能と測定対象空間Ｓの大きさと、対象物体Ｏが決まった時点で決定する。
【００７０】
最小ボクセルの一辺の長さは、要求される空間分解能と同じ値で、Ａｍｉｎとする。また、上述した最小外接立方体の一辺の長さＡとする。
【００７１】
次式で、レベルＬｓを求める。
【００７２】
【数１】

【００７３】
次式で最大ボクセルの大きさを求める。
【００７４】
【数２】

【００７５】
標本ボクセルは、最小ボクセルと同じサイズにする。標本ボクセルの間隔Ｓは、次の手順で求める。図９（ａ）に示すように、最小外接正方形の一辺の長さＡｓとし、図９（ｂ）に示すように、長さＡｓの対角線を持つ正方形の一辺の長さＡｔを次式で求める。
【００７６】
【数３】

【００７７】
また、標本ボクセルの間隔Ｓ（最小ボクセルＳ個分の間隔）を、２の指数乗とするために、次式を満たす指数Ｓ１を決定する。
【００７８】
【数４】

【００７９】
次式で、指数Ｓ１とＬｓ−Ｌとの大きくない方の値を指数ＳＳとする。
【００８０】
【数５】

【００８１】
そして、標本ボクセルの間隔Ｓは、次式により、指数ＳＳを使って求める。
【００８２】
【数６】

【００８３】
次に、着目する分割ボクセル（以下の説明及び図面において、単に「着目ボクセル」という）と、その表面の標本ボクセルとの関係について説明する。
【００８４】
まず、分割レベルＬの着目ボクセルの一辺の長さと、標本ボクセルの間隔Ｓとを、共に２の指数乗になるように選ぶ。こうすると、図１０（ａ）、（ｂ）に示すように、着目ボクセルの各表面には、間隔Ｓで標本ボクセルが格子状に並ぶ。
【００８５】
なお、標本ボクセルの中心は、厳密には、着目ボクセルの表面上になく、標本ボクセルの大きさの半分ほど空間的にずれているが、着目ボクセルの表面付近に位置する。これは、標本ボクセルと着目ボクセルとが、上述のような分割関係にあるためであり、こうすることにより、アルゴリズムを簡単化でき、処理速度を向上できる。
【００８６】
次に、より具体的な演算例を説明する。ここでは、対象物体Ｏを一人の人間とし、各パラメータの具体的な決定方法を説明する。
【００８７】
最小ボクセルの一辺の長さ（つまり要求される空間分解能）をＡｍｉｎ＝６．２５ｍｍとする。カメラ台数は、ｎ＝４（台）とする。
【００８８】
さて人間は、多くの姿勢をとることができるが、背を丸めて両腕で屈曲した両膝を抱えている姿勢を想定し、この姿勢に外接する立方体を最小外接立方体とし、その一辺の長さをＡ＝８５０ｍｍとする。
【００８９】
（数１）を満たすレベルＬｓは７となる。
【００９０】
最大ボクセルの大きさは、（数２）からＡｍａｘ＝８００ｍｍとなる。
【００９１】
測定対象空間Ｓを、一辺が２４００ｍｍの立方体の領域とすると、最大ボクセルをＭ＝３×３×３＝２７個組み合わせた空間となる。
【００９２】
次に、標本ボクセルの間隔Ｓを求める。ここでは、人体の最も細い部分は、手首とする（本例では、手首より細い手足の指等は測定対象としない）。そして、手首の最小断面を直径７５ｍｍの円とすると、最小外接正方形の一辺の長さはＡｓ＝７５ｍｍとなる。
【００９３】
（数３）からＡｔ＝５３ｍｍとなり、（数４）から指数Ｓ１＝３、（数５）からＳ１と７−Ｌとの大小関係により指数ＳＳ＝３またはＳＳ＝７−Ｌとなり、（数６）から、標本ボクセル間隔Ｓは、同じくＳ１と７−Ｌとの大小関係によりＳ＝８またはＳ＝２＾（７−Ｌ）となる。
【００９４】
次に、本発明の三次元空間再構成装置の動作を、図１１から図１６のフローチャートを使って説明する。
【００９５】
まず、図１１のステップＳ０にて、ｎ台のカメラ２２〜２６で、対象物体Ｏを含む測定対象空間Ｓを同時に画像を撮影する。また、あらかじめ撮影していた対象物体Ｏがない背景のみの画像との背景差分により、対象物体Ｏのシルエットを抽出し画像データとする。
【００９６】
次に、全てのレベルのボクセル空間の状態テーブルの要素を”未定”に設定する（ステップＳ１）。
【００９７】
次に、ステップＳ２〜Ｓ６の処理を、レベルＬ＝０〜Ｌｓについて繰り返す。ここで、レベルを示すカウンタＬが、脱出条件を定めており、ループを抜けるとき、着目ボクセルが最小ボクセルと同じサイズになる。ステップ２では、レベルＬに合った標本ボクセルの間隔Ｓを、（数３）〜（数６）から決定する。また、粗いボクセルをレベルＬボクセルに分割し、それぞれを着目ボクセルＶｉとする（ステップＳ３）。
【００９８】
すなわち、ここでは、図１２に示すように、レベルＬを評価して（ステップＳ３１）、Ｌ＝０の場合（当初）には、測定対象空間ＳをＭ個のレベル０ボクセル（最大ボクセルと同じサイズ）に分割し、Ｍ個の着目ボクセルＶｉとする（ステップＳ３３）。また、Ｌ≠０の場合（当初以外）には、１つ粗いレベル（Ｌ−１）ボクセル空間の状態テーブルを参照し、”占有”状態にあるボクセルのみ、レベルＬボクセルに分割し、着目ボクセルＶｉとする（ステップＳ３２）。
【００９９】
図１１のステップＳ３が済んだら、ステップＳ４〜Ｓ６の処理を、各着目ボクセルＶｉについて繰り返す。即ち、着目ボクセルＶｉの表面の標本ボクセルをＳＶｊとし（ステップＳ４）、全ての標本ボクセルＳＶｊついて、その状態を決定する（ステップＳ５）。
【０１００】
ここでは、図１３に示すように、全ての標本ボクセルＳＶｊについて、ステップＳ５１、Ｓ５２の処理を繰り返す。
【０１０１】
即ち、標本ボクセルＳＶｊの状態を評価し、”未定”なら、視体積交差法でその状態を決定する（ステップＳ５１、Ｓ５２）。
【０１０２】
この視体積交差法では、図１４に示すように、標本ボクセルＳＶｊの中心とカメラＣのレンズ中心とを結ぶ直線が、カメラＣの画像面と交わる位置の画素Ｐｃを全てのカメラＣ（Ｃ＝１〜ｎ）について求める（ステップＳ５２１）。
【０１０３】
そして、全ての画素Ｐｃ（Ｃ＝１〜ｎ）が対象物体Ｏのシルエット上にあるときは、標本ボクセルＳＶｊの状態を”占有”とし、画素Ｐｃのうち少なくとも１つがシルエット上にないときは”空”とし、最小ボクセル空間の状態テーブルを更新する（ステップＳ５２２〜５２４）。以上で、標本ボクセルＳＶｊの状態が決定できる。
【０１０４】
次に、図１１のステップＳ６にて、標本ボクセルＳＶｊの状態から着目ボクセルＶｉの状態を決定する。ここでは、着目ボクセルＶｉの表面にある全ての標本ボクセルＳＶｊの状態が”空”なら着目ボクセルＶｉの状態を”空”とし、標本ボクセルＶｉのうち１つでも”占有”の状態があれば、着目ボクセルＶｉの状態を”占有”とする。以上で、レベルＬボクセル空間が決定でき、測定対象空間１２１の三次元空間再構成をレベルＬボクセル空間で完了したことになる。
【０１０５】
なお、ステップＳ３でレベルＬに分割しなかったボクセルについては、状態テーブルの内容が”未定”のままである。これは、分割前のレベル（Ｌ−１）ボクセルの段階で、対象物体と重なり合わないことが判明しているため、”未定”状態は”空”状態と見なして良い。これらのボクセルは、以降さらに詳しく検討されることはない。
【０１０６】
以上の処理をレベルＬ＝０〜ＬＳ−１まで繰り返し、測定対象空間１２１の三次元空間再構成を全てのレベルＬボクセル空間で完了する。
【０１０７】
さらに、図１１のステップＳ７にて、最小ボクセルでの三次元空間の再構成を行う。ここでは、図１６に示すように、レベル（Ｌｓ−１）ボクセル空間の状態テーブルを参照し、”占有”状態のボクセルのみ８分割し、着目ボクセルＶｉとする（ステップＳ７１）。
【０１０８】
そして、全ての着目ボクセルＶｉについて、ステップＳ７２、Ｓ５２の処理を繰り返す。即ち、着目ボクセルＶｉの状態を評価し、”未定”なら、視体積交差法でその状態を決定する（ステップＳ５２）。
【０１０９】
ここで、レベルＬｓでは、着目ボクセルと最小ボクセルは同一であり、これまでの処理で標本ボクセルを決定した結果は、最小ボクセル空間の状態テーブルに記録されており、あらためて、最小ボクセルレベルの処理を追加する必要がない。
【０１１０】
以上の処理で、最小ボクセル空間で測定対象空間Ｓの三次元空間の再構成が完成し、測定対象空間Ｓの内部にある、対象物体Ｏの位置と形状が決定できた。
【０１１１】
測定対象空間Ｓを、部屋などとすると、人が占める体積占有率（測定対象空間に占める対象物体の体積占有率）は数％から高々１０％以下である。つまり、測定対象空間のほとんどは人のいない「空」状態である。このような低い体積占有率の状況では、粗いボクセルのうちに演算対象から削除できることが、演算量削減に大きく貢献している。因みに、実際に測定を行う場合には、この程度の体積占有率になることが多く、実用上効果大である。
【０１１２】
本発明者らの試算では、２４００ｍｍ立方の空間（測定対象空間）を、４台のカメラで撮像し、１人の人物（身長１７００ｍｍ）の動きを測定する場合、測定対象空間に占める人物の体積占有率（空間占有率）は、約１．３８％となり、図１７に示すように、演算量は、従来技術と比較して、約１／５０〜１／６０というように、激減した。
【０１１３】
【発明の効果】
本発明では、対象物体の性質に着目して、最大ボクセルを利用し、さらに、意味のある部分のみについて、繰り返しボクセル分割を行っているため、演算量を劇的に削減でき、十分な解像度を持ちながら、高速に処理を完了することができる。
【図面の簡単な説明】
【図１】本発明の一実施の形態における三次元空間再構成装置の機能ブロック図
【図２】同機能ブロック図
【図３】同ブロック図
【図４】同最大ボクセルの説明図
【図５】（ａ）同処理の流れの概説図
（ｂ）同処理の流れの概説図
（ｃ）同処理の流れの概説図
（ｄ）同処理の流れの概説図
（ｅ）同処理の流れの概説図
【図６】（ａ）同測定対象空間の説明図
（ｂ）同最大ボクセルの説明図
【図７】（ａ）同分割ボクセルの分割説明図
（ｂ）同分割ボクセルの分割説明図
（ｃ）同分割ボクセルの分割説明図
（ｄ）同分割ボクセルの分割説明図
【図８】（ａ）同ボクセル状態テーブルの例示図
（ｂ）同ボクセル状態テーブルの例示図
（ｃ）同ボクセル状態テーブルの例示図
（ｄ）同ボクセル状態テーブルの例示図
【図９】（ａ）同パラメータの説明図
（ｂ）同パラメータの説明図
【図１０】（ａ）同標本ボクセルの説明図
（ｂ）同標本ボクセルの説明図
【図１１】同フローチャート
【図１２】同フローチャート
【図１３】同フローチャート
【図１４】同フローチャート
【図１５】同フローチャート
【図１６】同フローチャート
【図１７】同計算量と体積占有率との関係を示すグラフ
【図１８】従来の三次元空間再構成の原理説明図
【図１９】同三次元空間再構成装置の機能ブロック図
【図２０】同三次元空間再構成装置のフローチャート
【符号の説明】
１０制御手段
１２複数方向画像取得手段
１４ボクセル状態テーブル
１６最大ボクセル決定手段
１８ボクセル分割手段
１９ボクセル状態決定手段

Claims

測定対象空間内にある対象物体を、互いに異なる方向から撮像し、多数の最小ボクセルの塊により、対象物体を再構成する三次元空間再構成装置であって、
変形可能な対象物体について前記対象物体に外接する立方体よりも小さい立方体であって６つの表面を有し、かつ前記表面のいずれかが前記対象物体の少なくとも一部を切断する最大ボクセルを決定する最大ボクセル決定手段と、
当初、測定対象空間を前記最大ボクセルで分割した複数のボクセルを分割ボクセルとして出力すると共に、当初以降、与えられたボクセルを一定個数に分割した分割ボクセルを出力するボクセル分割手段と、
前記ボクセル分割手段が出力するそれぞれの分割ボクセルと対象物体とが、重なり合うか否かを決定するボクセル状態決定手段と、
対象物体と重なり合うと決定された、分割ボクセルが、一定脱出条件を満たしていない場合、この分割ボクセルを前記ボクセル分割手段に与えて、繰り返し分割させる制御手段とを備え、前記ボクセル状態決定手段は、前記最大ボクセル及び前記分割ボクセルのいずれについても、与えられたボクセルの表面付近のみを調べ、いずれかの表面付近に対象物体を検出できたとき、このボクセルと対象物体とが重なり合うと決定することを特徴とする三次元空間再構成装置。
前記一定脱出条件は、分割ボクセルと最小ボクセルのサイズが同じであることを特徴とする請求項１記載の三次元空間再構成装置。
前記一定個数は、８であることを特徴とする請求項１または２記載の三次元空間再構成装置。
前記ボクセル状態決定手段は、ボクセルの表面付近の一部を標本化して標本ボクセルを発生する標本ボクセル発生部を有し、標本ボクセルに基づいて、対象物体の検出を行うことを特徴とする請求項１記載の三次元空間再構成装置。
前記標本ボクセルは、与えられたボクセルを最小ボクセルのサイズで均等に分割した複数のボクセルのいずれかであることを特徴とする請求項４記載の三次元空間再構成装置。
測定対象空間内にある対象物体を、互いに異なる方向から撮像し、多数の最小ボクセルの塊により、対象物体を再構成する三次元空間再構成方法であって、
変形可能な対象物体について前記対象物体に外接する立方体よりも小さい立方体であって６つの表面を有し、かつ前記表面のいずれかが前記対象物体の少なくとも一部を切断する最大ボクセルを決定するステップと、
当初、測定対象空間を前記最大ボクセルで分割した複数のボクセルを分割ボクセルとして出力すると共に、当初以降、与えられたボクセルを一定個数に分割した分割ボクセルを出力するステップと、
それぞれの分割ボクセルと対象物体とが、重なり合う否かを決定するステップと、
対象物体と重なり合うと決定された、分割ボクセルが、一定脱出条件を満たしていない場合、この分割ボクセルを、繰り返し分割させるステップとを備え、前記決定するステップにおいて、前記最大ボクセル及び前記分割ボクセルのいずれについても、与えられたボクセルの表面付近のみを調べ、いずれかの表面付近に対象物体を検出できたとき、このボクセルと対象物体とが重なり合うと決定することを特徴とする三次元空間再構成方法。
前記一定脱出条件は、分割ボクセルと最小ボクセルのサイズが同じであることを特徴とする請求項６記載の三次元空間再構成方法。
前記一定個数は、８であることを特徴とする請求項６または７記載の三次元空間再構成方法。
ボクセルの表面付近の一部を標本化して標本ボクセルを発生し、標本ボクセルに基づいて、対象物体の検出を行うことを特徴とする請求項６記載の三次元空間再構成方法。
前記標本ボクセルは、与えられたボクセルを最小ボクセルのサイズで均等に分割した複数のボクセルのいずれかであることを特徴とする請求項９記載の三次元空間再構成方法。