JP4550221B2

JP4550221B2 - Three-dimensional space reconstruction device and three-dimensional space reconstruction method

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

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

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

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

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

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

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

【００８３】
次に、着目する分割ボクセル（以下の説明及び図面において、単に「着目ボクセル」という）と、その表面の標本ボクセルとの関係について説明する。
【００８４】
まず、分割レベルＬの着目ボクセルの一辺の長さと、標本ボクセルの間隔Ｓとを、共に２の指数乗になるように選ぶ。こうすると、図１０（ａ）、（ｂ）に示すように、着目ボクセルの各表面には、間隔Ｓで標本ボクセルが格子状に並ぶ。
【００８５】
なお、標本ボクセルの中心は、厳密には、着目ボクセルの表面上になく、標本ボクセルの大きさの半分ほど空間的にずれているが、着目ボクセルの表面付近に位置する。これは、標本ボクセルと着目ボクセルとが、上述のような分割関係にあるためであり、こうすることにより、アルゴリズムを簡単化でき、処理速度を向上できる。
【００８６】
次に、より具体的な演算例を説明する。ここでは、対象物体Ｏを一人の人間とし、各パラメータの具体的な決定方法を説明する。
【００８７】
最小ボクセルの一辺の長さ（つまり要求される空間分解能）をＡｍｉｎ＝６．２５ｍｍとする。カメラ台数は、ｎ＝４（台）とする。
【００８８】
さて人間は、多くの姿勢をとることができるが、背を丸めて両腕で屈曲した両膝を抱えている姿勢を想定し、この姿勢に外接する立方体を最小外接立方体とし、その一辺の長さをＡ＝８５０ｍｍとする。
【００８９】
（数１）を満たすレベルＬｓは７となる。
【００９０】
最大ボクセルの大きさは、（数２）からＡｍａｘ＝８００ｍｍとなる。
【００９１】
測定対象空間Ｓを、一辺が２４００ｍｍの立方体の領域とすると、最大ボクセルをＭ＝３×３×３＝２７個組み合わせた空間となる。
【００９２】
次に、標本ボクセルの間隔Ｓを求める。ここでは、人体の最も細い部分は、手首とする（本例では、手首より細い手足の指等は測定対象としない）。そして、手首の最小断面を直径７５ｍｍの円とすると、最小外接正方形の一辺の長さはＡｓ＝７５ｍｍとなる。
【００９３】
（数３）からＡｔ＝５３ｍｍとなり、（数４）から指数Ｓ１＝３、（数５）からＳ１と７−Ｌとの大小関係により指数ＳＳ＝３またはＳＳ＝７−Ｌとなり、（数６）から、標本ボクセル間隔Ｓは、同じくＳ１と７−Ｌとの大小関係によりＳ＝８またはＳ＝２＾（７−Ｌ）となる。
【００９４】
次に、本発明の三次元空間再構成装置の動作を、図１１から図１６のフローチャートを使って説明する。
【００９５】
まず、図１１のステップＳ０にて、ｎ台のカメラ２２〜２６で、対象物体Ｏを含む測定対象空間Ｓを同時に画像を撮影する。また、あらかじめ撮影していた対象物体Ｏがない背景のみの画像との背景差分により、対象物体Ｏのシルエットを抽出し画像データとする。
【００９６】
次に、全てのレベルのボクセル空間の状態テーブルの要素を”未定”に設定する（ステップＳ１）。
【００９７】
次に、ステップＳ２〜Ｓ６の処理を、レベルＬ＝０〜Ｌｓについて繰り返す。ここで、レベルを示すカウンタＬが、脱出条件を定めており、ループを抜けるとき、着目ボクセルが最小ボクセルと同じサイズになる。ステップ２では、レベルＬに合った標本ボクセルの間隔Ｓを、（数３）〜（数６）から決定する。また、粗いボクセルをレベルＬボクセルに分割し、それぞれを着目ボクセルＶｉとする（ステップＳ３）。
【００９８】
すなわち、ここでは、図１２に示すように、レベルＬを評価して（ステップＳ３１）、Ｌ＝０の場合（当初）には、測定対象空間ＳをＭ個のレベル０ボクセル（最大ボクセルと同じサイズ）に分割し、Ｍ個の着目ボクセルＶｉとする（ステップＳ３３）。また、Ｌ≠０の場合（当初以外）には、１つ粗いレベル（Ｌ−１）ボクセル空間の状態テーブルを参照し、”占有”状態にあるボクセルのみ、レベルＬボクセルに分割し、着目ボクセルＶｉとする（ステップＳ３２）。
【００９９】
図１１のステップＳ３が済んだら、ステップＳ４〜Ｓ６の処理を、各着目ボクセルＶｉについて繰り返す。即ち、着目ボクセルＶｉの表面の標本ボクセルをＳＶｊとし（ステップＳ４）、全ての標本ボクセルＳＶｊついて、その状態を決定する（ステップＳ５）。
【０１００】
ここでは、図１３に示すように、全ての標本ボクセルＳＶｊについて、ステップＳ５１、Ｓ５２の処理を繰り返す。
【０１０１】
即ち、標本ボクセルＳＶｊの状態を評価し、”未定”なら、視体積交差法でその状態を決定する（ステップＳ５１、Ｓ５２）。
【０１０２】
この視体積交差法では、図１４に示すように、標本ボクセルＳＶｊの中心とカメラＣのレンズ中心とを結ぶ直線が、カメラＣの画像面と交わる位置の画素Ｐｃを全てのカメラＣ（Ｃ＝１〜ｎ）について求める（ステップＳ５２１）。
【０１０３】
そして、全ての画素Ｐｃ（Ｃ＝１〜ｎ）が対象物体Ｏのシルエット上にあるときは、標本ボクセルＳＶｊの状態を”占有”とし、画素Ｐｃのうち少なくとも１つがシルエット上にないときは”空”とし、最小ボクセル空間の状態テーブルを更新する（ステップＳ５２２〜５２４）。以上で、標本ボクセルＳＶｊの状態が決定できる。
【０１０４】
次に、図１１のステップＳ６にて、標本ボクセルＳＶｊの状態から着目ボクセルＶｉの状態を決定する。ここでは、着目ボクセルＶｉの表面にある全ての標本ボクセルＳＶｊの状態が”空”なら着目ボクセルＶｉの状態を”空”とし、標本ボクセルＶｉのうち１つでも”占有”の状態があれば、着目ボクセルＶｉの状態を”占有”とする。以上で、レベルＬボクセル空間が決定でき、測定対象空間１２１の三次元空間再構成をレベルＬボクセル空間で完了したことになる。
【０１０５】
なお、ステップＳ３でレベルＬに分割しなかったボクセルについては、状態テーブルの内容が”未定”のままである。これは、分割前のレベル（Ｌ−１）ボクセルの段階で、対象物体と重なり合わないことが判明しているため、”未定”状態は”空”状態と見なして良い。これらのボクセルは、以降さらに詳しく検討されることはない。
【０１０６】
以上の処理をレベルＬ＝０〜ＬＳ−１まで繰り返し、測定対象空間１２１の三次元空間再構成を全てのレベルＬボクセル空間で完了する。
【０１０７】
さらに、図１１のステップＳ７にて、最小ボクセルでの三次元空間の再構成を行う。ここでは、図１６に示すように、レベル（Ｌｓ−１）ボクセル空間の状態テーブルを参照し、”占有”状態のボクセルのみ８分割し、着目ボクセルＶｉとする（ステップＳ７１）。
【０１０８】
そして、全ての着目ボクセルＶｉについて、ステップＳ７２、Ｓ５２の処理を繰り返す。即ち、着目ボクセルＶｉの状態を評価し、”未定”なら、視体積交差法でその状態を決定する（ステップＳ５２）。
【０１０９】
ここで、レベルＬｓでは、着目ボクセルと最小ボクセルは同一であり、これまでの処理で標本ボクセルを決定した結果は、最小ボクセル空間の状態テーブルに記録されており、あらためて、最小ボクセルレベルの処理を追加する必要がない。
【０１１０】
以上の処理で、最小ボクセル空間で測定対象空間Ｓの三次元空間の再構成が完成し、測定対象空間Ｓの内部にある、対象物体Ｏの位置と形状が決定できた。
【０１１１】
測定対象空間Ｓを、部屋などとすると、人が占める体積占有率（測定対象空間に占める対象物体の体積占有率）は数％から高々１０％以下である。つまり、測定対象空間のほとんどは人のいない「空」状態である。このような低い体積占有率の状況では、粗いボクセルのうちに演算対象から削除できることが、演算量削減に大きく貢献している。因みに、実際に測定を行う場合には、この程度の体積占有率になることが多く、実用上効果大である。
【０１１２】
本発明者らの試算では、２４００ｍｍ立方の空間（測定対象空間）を、４台のカメラで撮像し、１人の人物（身長１７００ｍｍ）の動きを測定する場合、測定対象空間に占める人物の体積占有率（空間占有率）は、約１．３８％となり、図１７に示すように、演算量は、従来技術と比較して、約１／５０〜１／６０というように、激減した。
【０１１３】
【発明の効果】
本発明では、対象物体の性質に着目して、最大ボクセルを利用し、さらに、意味のある部分のみについて、繰り返しボクセル分割を行っているため、演算量を劇的に削減でき、十分な解像度を持ちながら、高速に処理を完了することができる。
【図面の簡単な説明】
【図１】本発明の一実施の形態における三次元空間再構成装置の機能ブロック図
【図２】同機能ブロック図
【図３】同ブロック図
【図４】同最大ボクセルの説明図
【図５】（ａ）同処理の流れの概説図
（ｂ）同処理の流れの概説図
（ｃ）同処理の流れの概説図
（ｄ）同処理の流れの概説図
（ｅ）同処理の流れの概説図
【図６】（ａ）同測定対象空間の説明図
（ｂ）同最大ボクセルの説明図
【図７】（ａ）同分割ボクセルの分割説明図
（ｂ）同分割ボクセルの分割説明図
（ｃ）同分割ボクセルの分割説明図
（ｄ）同分割ボクセルの分割説明図
【図８】（ａ）同ボクセル状態テーブルの例示図
（ｂ）同ボクセル状態テーブルの例示図
（ｃ）同ボクセル状態テーブルの例示図
（ｄ）同ボクセル状態テーブルの例示図
【図９】（ａ）同パラメータの説明図
（ｂ）同パラメータの説明図
【図１０】（ａ）同標本ボクセルの説明図
（ｂ）同標本ボクセルの説明図
【図１１】同フローチャート
【図１２】同フローチャート
【図１３】同フローチャート
【図１４】同フローチャート
【図１５】同フローチャート
【図１６】同フローチャート
【図１７】同計算量と体積占有率との関係を示すグラフ
【図１８】従来の三次元空間再構成の原理説明図
【図１９】同三次元空間再構成装置の機能ブロック図
【図２０】同三次元空間再構成装置のフローチャート
【符号の説明】
１０制御手段
１２複数方向画像取得手段
１４ボクセル状態テーブル
１６最大ボクセル決定手段
１８ボクセル分割手段
１９ボクセル状態決定手段[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a three-dimensional space reconstruction apparatus and method for reconstructing a three-dimensional shape of a target object with minimum voxels using a visual volume intersection method.
[0002]
[Prior art]
As a conventional example of a three-dimensional spatial reconstruction method using the Volume Intersection Method, the document “Virtual View generation for 3D Digital Video” (IEEE MU LI LI. 1 pp. 18-26, 1997).
[0003]
In this case, the measurement target space in which the target object enters is divided into small cubes (voxels). That is, the measurement target space is treated as a space in which this voxel (corresponding to the “minimum voxel” of the present invention) is stacked without gaps in the XYZ directions. The length of one side of the voxel determines the resolution of the measurement. The smaller the length of one side, the higher the resolution of the measurement, and the larger the length of one side, the higher the resolution of the measurement. descend.
[0004]
Here, if the lengths of the measurement target space in the XYZ directions are XL times, YL times, and ZL times the length of one side of the voxel, the measurement target space has XL × YL × ZL voxels. It is a filled space.
[0005]
Then, in the visual volume intersection method, for all of these XL × YL × ZL voxels, it is examined in detail whether or not the corresponding voxel is inside the target object (number of investigations: XL × YL × ZL times). . As a result of the investigation, the three-dimensional shape of the target object is reconstructed so as to stack a block of voxels that are supposed to be inside the target object.
[0006]
More specifically, as shown in FIG. 18, a plurality of cameras are set so as to have viewpoints 1 to n (usually n ≧ 3), and the target object is photographed from different directions.
[0007]
Thereby, the silhouette of the target object is photographed on the image plane of each camera. The voxel state (whether or not the voxel and the target object overlap) can be determined by whether or not the pixel corresponding to the voxel is included in the silhouette.
[0008]
For example, the pixel corresponding to voxel A outside the target object is outside the silhouette in at least one camera image (in FIG. 18, it is outside the silhouette in image plane 1). In addition, the pixel corresponding to the voxel B inside the target object is inside the silhouette in all the camera images.
[0009]
That is, if a pixel corresponding to a certain voxel is included in the silhouette of the target object in all camera images, the voxel is inside the target object. Conversely, in any camera image, if the pixel corresponding to the voxel is not included in the silhouette of the target object, the voxel is outside the target object.
[0010]
If the camera calibration has been completed and the camera parameters such as the camera position, orientation, and focal length are known, the voxel is geometrically determined from the positional relationship between the lens center, the voxel position, and the image plane. Can be easily obtained.
[0011]
A configuration example for this is shown in FIG. In FIG. 19, the multi-directional image acquisition means 1 including a camera group or the like simultaneously captures the target object from a plurality of different viewpoints and directions, and outputs the image data.
[0012]
The parameter holding means 2 holds information such as the positions and postures of a plurality of cameras constituting the multi-directional image acquisition means 1 input in advance.
[0013]
The voxel state table holding unit 3 holds the state of all the voxels (whether the voxel and the target object overlap each other).
[0014]
The target voxel generating means 4 selects XL × YL × ZL voxels one by one in order and outputs them as the target voxel.
[0015]
The state determination unit 5 of the target voxel determines the target voxel output from the target voxel generation unit 4 from the image data of the multi-directional image acquisition unit 1 and the parameters of each camera stored in the parameter storage unit 2 as described above. The voxel state is determined, and the contents of the voxel state table holding means 3 are updated.
[0016]
Next, a processing example will be described with reference to FIG. First, the state determination unit 5 of the target voxel accesses the voxel state table holding unit 3 to perform initialization, and sets the state of all the voxels to “occupied” (meaning that the voxel and the target object overlap) ( Step S1001).
[0017]
Next, the target voxel generating means 4 determines the first target voxel (step S1002), and the state determination means 5 of the target voxel determines that the straight line connecting the center position of the voxel and the lens center of the first camera is an image plane. The pixel p at the point where it intersects with is determined (step S1004).
[0018]
In step S1005, the state determination unit 5 of the target voxel determines whether or not the pixel p is included in the silhouette on the image plane. If the pixel p is not included in the silhouette, the state of the voxel is set to “empty”. To the next voxel processing (step S1006). If included, the processing from step S1003 onward is repeated for the next camera.
[0019]
Then, if it is included in all cameras, the state remains “occupied”, otherwise the state is “empty”.
[0020]
The above process is repeated for all voxels (step S1002).
[0021]
When these series of processes are completed, the state of all voxels is determined and the three-dimensional space is reconstructed.
[0022]
[Problems to be solved by the invention]
Now, assuming that the measurement accuracy is insufficient with the current resolution, in order to improve the resolution, the length of one side of the voxel is set to 1/4 times the conventional one. Then, the measurement target space is filled with (4 × XL) × (4 × YL) × (4 × ZL) = 64 (XL × YL × ZL) voxels, and the number of investigations is 64. It doubles.
[0023]
As is clear from this example, in the prior art, there was a problem that when trying to obtain a practical resolution, the amount of calculation becomes enormous and it becomes very difficult to perform real-time processing. .
[0024]
Accordingly, an object of the present invention is to provide a three-dimensional space reconstruction device and method that can dramatically reduce the amount of calculation and achieve both sufficient resolution and high-speed processing.
[0025]
[Means for Solving the Problems]
In the present invention, the target object in the measurement target space is imaged from different directions, and the target object is reconstructed by a large number of minimum voxel clusters, and the maximum voxel that cannot be contained by the target object is determined. A maximum voxel determining means, and a voxel dividing means for outputting a plurality of voxels obtained by dividing the measurement target space by the maximum voxel as divided voxels and outputting divided voxels obtained by dividing a given voxel into a predetermined number from the beginning The voxel state determining means for determining whether or not each divided voxel output from the voxel dividing means and the target object overlap with each other, and the divided voxel determined to overlap with the target object does not satisfy the certain escape condition. In this case, the control unit includes control means for supplying the divided voxels to the voxel dividing means and repeatedly dividing them.
[0026]
With this configuration, it is possible to dramatically reduce the amount of calculation in the three-dimensional space reconstruction and to achieve both sufficient resolution and high-speed processing.
[0027]
DETAILED DESCRIPTION OF THE INVENTION
According to the first invention In the 3D space reconstruction device, the target object in the measurement target space is imaged from different directions, and the target object is reconstructed by a large number of minimum voxel clusters. Maximum voxel determining means for determining voxels, and a plurality of voxels obtained by dividing the measurement target space by the maximum voxels are output as divided voxels, and divided voxels obtained by dividing a given voxel into a predetermined number are output from the beginning. Voxel dividing means, voxel state determining means for determining whether or not each divided voxel output from the voxel dividing means and the target object overlap, and the divided voxel determined to overlap with the target object has a certain escape condition If this condition is not satisfied, the control means for repeating the division by giving this divided voxel to the voxel dividing means Equipped with a.
[0028]
In this configuration, by repeating the voxel division starting from the above-mentioned maximum voxel, it is possible to reduce the investigation of empty voxels and greatly reduce the amount of calculation. As a result, in order to obtain a sufficient resolution, the three-dimensional space of the target object can be reconstructed in a processing time that is practical even if one side of the minimum voxel is reduced.
[0029]
According to the second invention In the three-dimensional space reconstruction device, the constant escape condition is that the sizes of the divided voxels and the minimum voxels are the same.
[0030]
With this configuration, when the iterative process is completed, the three-dimensional shape of the target object can be reconstructed with the minimum voxel cluster without any special process.
[0031]
According to the third invention In the three-dimensional space reconstruction device, the fixed number is 8.
[0032]
With this configuration, it is possible to divide the XYZ direction by half without difficulty.
[0033]
According to the fourth invention In the three-dimensional space reconstruction device, the voxel state determination means examines only the vicinity of the surface of the given voxel, and when the target object can be detected near one of the surfaces, it is determined that the voxel and the target object overlap. To do.
[0034]
With this configuration, the amount of calculation can be further reduced by omitting the investigation inside the divided voxels.
[0035]
According to the fifth invention In the three-dimensional space reconstruction device, the voxel state determination means has a sample voxel generation unit that generates a sample voxel by sampling a part near the surface of the voxel, and detects a target object based on the sample voxel .
[0036]
With this configuration, the amount of calculation can be further reduced by thinning out the calculation target by sampling.
[0037]
According to the sixth invention In the three-dimensional space reconstruction apparatus, the sample voxel is one of a plurality of voxels obtained by equally dividing a given voxel with the minimum voxel size.
[0038]
With this configuration, the state of the sample voxel and the state of the minimum voxel become the same, and at the stage where the sample voxel is divided to the minimum voxel later, the state determination process can be omitted for the minimum voxel that matches the sample voxel, and the calculation amount Can be reduced.
[0039]
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[0040]
In FIG. 1, the control means 10 controls each means to be described later. In particular, when the divided voxel determined to overlap with the target object does not satisfy the certain escape condition, this divided voxel is given to the voxel dividing means 18 and repeatedly divided.
[0041]
The input means 11 receives an operator input.
[0042]
The multi-directional image acquisition unit 12 captures the target object in the measurement target space from different directions and viewpoints, and outputs a plurality of image data.
[0043]
The storage unit 13 has a voxel state table 14 that holds the state of each voxel for each repetition level described later, in addition to a program executed by the control unit 10 and an area for temporarily storing information as necessary. . Of course, other known data structures such as a list may be adopted as long as the table can be freely read and written without using such a table.
[0044]
The parameter holding unit 15 holds parameters such as the positions and postures of all cameras.
[0045]
The maximum voxel determining means 16 determines the maximum voxel that the target object cannot enter.
[0046]
The escape condition determination means 17 has a fixed escape condition (in this example, the divided voxel has the same size as the minimum voxel) that is referred to when the control means 10 re-divides the divided voxel using the voxel dividing means 18. Determine whether it is satisfied. This escape condition may be changed such that the divided voxel is several times the minimum voxel.
[0047]
The voxel dividing means 18 initially outputs a plurality of voxels obtained by dividing the measurement target space by the maximum voxel as divided voxels, and outputs divided voxels obtained by dividing a given voxel into a predetermined number from the beginning.
[0048]
The voxel state determination means 19 determines whether or not each divided voxel output from the voxel dividing means 18 and the target object overlap. In this example, the voxel state determination means 19 examines only the vicinity of the surface of the given voxel and determines that the voxel and the target object overlap when the target object can be detected near any of the surfaces.
[0049]
The voxel state determination means 19 has a sample voxel generator 20 that generates a sample voxel by sampling a part near the surface of the voxel, and detects a target object based on the sample voxel.
[0050]
Then, the sample voxel state determination unit 21 examines only the sample voxels generated by the sample voxel generation unit 20, and if any one of the sample voxels overlaps the target object, the corresponding divided voxel (the size is the same). Unquestioned) and the target object are determined to overlap. Otherwise, it is determined that the corresponding divided voxel and the target object do not overlap.
[0051]
More specifically, it is as shown in FIG. That is, when the target object O (here, a human being) exists in the measurement target space S, the multi-directional image acquisition unit 12 images the target object O from different directions. That is, a capture board group in which a target object O is imaged by a plurality of cameras (usually four or more are desirable to prevent occlusion) having different viewpoints and directions and connected to the cameras 22-26. 27, the image data is taken into the information processing apparatus.
[0052]
The information processing apparatus includes a keyboard 28 as an input unit, a bus 28 that mediates data communication between elements, a CPU 29, a memory 30, and an external storage device 31. Here, each means 10, 15-19 mentioned above is implement | achieved when CPU29 reads and writes with respect to the memory 30 and the external storage device 31 as the memory | storage means 13, and runs the program according to the flowchart mentioned later. Is done.
[0053]
Next, an overview of the processing of the present invention will be described. In the present invention, as described above, the concept of “maximum voxel” that does not allow the target object to enter is introduced. Here, the term “maximum” is used to refer to this “maximum voxel” as the starting point for repeated division of voxels, which will be described later, and as processing proceeds, the divided voxels become smaller from the largest voxel step by step. Because it will go.
[0054]
On the other hand, the voxel for determining the resolution is called “minimum voxel”.
In other words, the voxel division repeated in the present invention starts with the size of the maximum voxel, and after that, the number of steps (represented by the level in the following description) decreases as the division proceeds, and reaches the minimum voxel. Go through the process.
[0055]
Here, in order to realize the processing of the present invention in the most ideal state, it is desirable that the target object meets the following conditions.
(1) Although the target object can be deformed, the size of the smallest cube (minimum circumscribed cube) among the cubes spatially circumscribing in all deformation patterns is known.
(2) The size of the smallest square (minimum circumscribed square) is known assuming that a section obtained by cutting each part of the target object with an arbitrary surface circumscribes the square on the cut surface.
[0056]
However, the above conditions are not essential, and it is often sufficient in practice to set the maximum voxel relatively small.
[0057]
FIG. 4 shows how to determine the maximum voxel V0 when a human is the target object. That is, humans have a large number of joints and can take various postures, but there is a posture in which even if the body is folded as small as possible, it cannot be further reduced. At that time, a cube that is slightly smaller than a cube circumscribing a human is determined, and this is set as the maximum voxel (length of one side: L).
[0058]
When the relationship between the maximum voxel V0 determined in this way and a person is observed, the following can be understood. That is, since a human cannot enter the maximum voxel V0, a human part (in the example of FIG. 4, a head and a toe part) must protrude from the maximum voxel V0.
[0059]
Here, the maximum voxel V0 has six surfaces, and any of these surfaces will cut off the protruding human part. More specifically, paying attention to the surface of the maximum voxel V0, if there is a human part on any surface, even if the inside of the maximum voxel V0 is not viewed (even if the investigation is omitted), It can be determined that a human is present inside (that is, the maximum voxel V0 and the human are overlapping).
[0060]
On the other hand, if there is no human part on all the surfaces of the maximum voxel V0, there is no human in the maximum voxel V0 (no overlapping).
[0061]
Based on the above knowledge, the present invention uses a process of starting from the maximum voxel V0 and repeatedly subdividing it. When examining one maximum voxel, the number of investigations can be reduced by examining only the vicinity of the surface and omitting the internal investigation.
[0062]
In addition, when the maximum voxel V0 or the large divided voxel and the target object do not overlap, the subsequent division (that is, more detailed investigation) is not performed.
[0063]
If the maximum voxel V0 is composed of 1000 minimum voxels, if it does not overlap with the target object in a single survey, the subsequent survey is omitted.
On the other hand, in the prior art, since all of the 1000 minimum voxels were investigated in detail, the method of the present invention is far more advantageous than the prior art, and the amount of computation is dramatically reduced. It can be easily understood that this can be reduced.
[0064]
In FIG. 5, the processing steps according to the present invention are schematically represented. Initially, as shown in FIG. 5A, the measurement target space S is divided by divided voxels having the same size as the maximum voxel V0. At this time, as shown in FIG. 5E, only the vicinity of the surface of each divided voxel is examined, and whether or not each divided voxel and the target object overlap is determined based on the above-described knowledge.
[0065]
Further, in this example, not all of these surfaces are examined, but preferable thinning is performed by sampling in a lattice shape, and only a part of the vicinity of the surface is investigated.
[0066]
Next, as shown in FIG. 5B, only the object that overlaps the target object is handled, and the division and investigation of the divided voxels are repeated (from the level of FIG. 5B to the level of FIG. 5C). From the level c) to the level shown in FIG. 5D,..., and finally, the process ends when the minimum voxel is divided.
[0067]
More specific description will be given below. First, the voxel state table 14 is configured as shown in FIG. That is, the voxel state table 14 is composed of a state table in a voxel space for each of a plurality of levels (FIG. 8A shows the size of the maximum voxel at level 0 and FIG. 8D shows the size of the minimum voxel at level Ls). The
[0068]
In each table, voxel numbers, which are identification numbers uniquely assigned within the same level, are associated with voxels constituting each voxel space and their states.
[0069]
Next, the procedure for determining the size of the maximum voxel, the level of the minimum voxel, the interval between the sample voxels, and the like will be specifically described. These parameters are determined when the required spatial resolution, the size of the measurement target space S, and the target object O are determined.
[0070]
The length of one side of the minimum voxel is the same value as the required spatial resolution, and is Amin. Further, the length A is one side of the minimum circumscribed cube.
[0071]
The level Ls is obtained by the following equation.
[0072]
[Expression 1]

[0073]
The maximum voxel size is obtained by the following formula.
[0074]
[Expression 2]

[0075]
The sample voxel is the same size as the smallest voxel. The interval S between sample voxels is obtained by the following procedure. As shown in FIG. 9 (a), the length As of one side of the minimum circumscribed square is obtained, and as shown in FIG. 9 (b), the length At of a side of the square having a diagonal line of length As is obtained by the following equation. .
[0076]
[Equation 3]

[0077]
Further, in order to set the interval S of sample voxels (the interval corresponding to S minimum voxels) to a power of 2, an index S1 that satisfies the following equation is determined.
[0078]
[Expression 4]

[0079]
In the following equation, the smaller one of the exponents S1 and Ls-L is defined as an exponent SS.
[0080]
[Equation 5]

[0081]
The sample voxel interval S is obtained using the exponent SS according to the following equation.
[0082]
[Formula 6]

[0083]
Next, the relationship between the target divided voxel (simply referred to as “target voxel” in the following description and drawings) and the sample voxel on the surface will be described.
[0084]
First, the length of one side of the target voxel at the division level L and the interval S between the sample voxels are both selected to be powers of two. In this way, as shown in FIGS. 10A and 10B, sample voxels are arranged in a lattice pattern at intervals S on each surface of the target voxel.
[0085]
Strictly speaking, the center of the sample voxel is not on the surface of the target voxel and is spatially shifted by about half the size of the sample voxel, but is located near the surface of the target voxel. This is because the sample voxel and the target voxel are in the division relationship as described above. By doing so, the algorithm can be simplified and the processing speed can be improved.
[0086]
Next, a more specific calculation example will be described. Here, a specific determination method of each parameter will be described assuming that the target object O is one person.
[0087]
The length of one side of the minimum voxel (that is, the required spatial resolution) is Amin = 6.25 mm. The number of cameras is n = 4 (units).
[0088]
Now, humans can take many postures, but assuming a posture holding both knees with their backs bent and bent with both arms, the cube circumscribing this posture is the minimum circumscribed cube, and the length of one side Let A = 850 mm.
[0089]
The level Ls satisfying (Equation 1) is 7.
[0090]
The size of the maximum voxel is Amax = 800 mm from (Equation 2).
[0091]
Assuming that the measurement target space S is a cubic region having a side of 2400 mm, a space in which M = 3 × 3 × 3 = 27 maximum voxels are combined.
[0092]
Next, an interval S between sample voxels is obtained. Here, the thinnest part of the human body is the wrist (in this example, fingers of the limbs thinner than the wrist are not measured). If the minimum cross section of the wrist is a circle having a diameter of 75 mm, the length of one side of the minimum circumscribed square is As = 75 mm.
[0093]
From (Equation 3), At = 53 mm, from (Equation 4), the exponent S1 = 3, and from (Equation 5), the exponent SS = 3 or SS = 7-L, depending on the magnitude relationship between S1 and 7-L. ), The sample voxel interval S is S = 8 or S = 2 ^ (7-L) depending on the magnitude relationship between S1 and 7-L.
[0094]
Next, the operation of the three-dimensional space reconstruction apparatus of the present invention will be described using the flowcharts of FIGS.
[0095]
First, in step S0 in FIG. 11, images are simultaneously captured in the measurement target space S including the target object O by the n cameras 22 to 26. Also, the silhouette of the target object O is extracted and used as image data based on the background difference from the background-only image without the target object O that has been captured in advance.
[0096]
Next, the state table elements of all levels of the voxel space are set to “undecided” (step S1).
[0097]
Next, the processes in steps S2 to S6 are repeated for levels L = 0 to Ls. Here, the counter L indicating the level defines an escape condition, and when exiting the loop, the target voxel has the same size as the minimum voxel. In step 2, the interval S between the sample voxels suitable for the level L is determined from (Equation 3) to (Equation 6). Further, the coarse voxel is divided into level L voxels, and each is set as a target voxel Vi (step S3).
[0098]
That is, here, as shown in FIG. 12, the level L is evaluated (step S31), and when L = 0 (initially), the measurement target space S is set to M level 0 voxels (the same as the maximum voxels). Size) to obtain M target voxels Vi (step S33). When L ≠ 0 (other than the original), the state table of one coarse level (L-1) voxel space is referred to, and only the voxels in the “occupied” state are divided into level L voxels, and the target voxel is divided. Vi (step S32).
[0099]
When step S3 of FIG. 11 is completed, the processing of steps S4 to S6 is repeated for each target voxel Vi. That is, the sample voxel on the surface of the target voxel Vi is set as SVj (step S4), and the state of all the sample voxels SVj is determined (step S5).
[0100]
Here, as shown in FIG. 13, the processing of steps S51 and S52 is repeated for all the sample voxels SVj.
[0101]
That is, the state of the sample voxel SVj is evaluated. If “undecided”, the state is determined by the view volume intersection method (steps S51 and S52).
[0102]
In this view volume intersection method, as shown in FIG. 14, pixels Pc at positions where the straight line connecting the center of the sample voxel SVj and the lens center of the camera C intersects the image plane of the camera C are all the cameras C (C = 1 to n) (step S521).
[0103]
When all the pixels Pc (C = 1 to n) are on the silhouette of the target object O, the state of the sample voxel SVj is “occupied”, and when at least one of the pixels Pc is not on the silhouette, “ The state table of the minimum voxel space is updated with “empty” (steps S522 to S524). As described above, the state of the sample voxel SVj can be determined.
[0104]
Next, in step S6 in FIG. 11, the state of the target voxel Vi is determined from the state of the sample voxel SVj. Here, if the state of all the sample voxels SVj on the surface of the target voxel Vi is “empty”, the state of the target voxel Vi is “empty”, and even if one of the sample voxels Vi is “occupied”, The state of the target voxel Vi is “occupied”. Thus, the level L voxel space can be determined, and the three-dimensional space reconstruction of the measurement target space 121 is completed in the level L voxel space.
[0105]
For the voxels that are not divided into the level L in step S3, the contents of the state table remain “undecided”. Since it has been found that it does not overlap the target object at the level (L-1) voxel stage before division, the “undecided” state may be regarded as the “empty” state. These voxels will not be discussed in further detail below.
[0106]
The above processing is repeated from level L = 0 to LS-1, and the three-dimensional space reconstruction of the measurement target space 121 is completed in all the level L voxel spaces.
[0107]
Further, in step S7 in FIG. 11, the three-dimensional space is reconstructed with the minimum voxels. Here, as shown in FIG. 16, the state table of the level (Ls-1) voxel space is referred to, and only the “occupied” state voxel is divided into eight to be the target voxel Vi (step S71).
[0108]
And the process of step S72, S52 is repeated about all the attention voxels Vi. That is, the state of the target voxel Vi is evaluated. If “undecided”, the state is determined by the view volume intersection method (step S52).
[0109]
Here, at the level Ls, the target voxel and the minimum voxel are the same, and the result of determining the sample voxel by the processing so far is recorded in the state table of the minimum voxel space. There is no need to add.
[0110]
With the above processing, the reconstruction of the three-dimensional space of the measurement target space S in the minimum voxel space is completed, and the position and shape of the target object O inside the measurement target space S can be determined.
[0111]
When the measurement target space S is a room or the like, the volume occupancy occupied by a person (volume occupancy of the target object in the measurement target space) is from several percent to 10% at most. That is, most of the measurement target space is in an “empty” state where no people are present. In such a low volume occupancy ratio, being able to delete a rough voxel from the calculation target greatly contributes to a reduction in the calculation amount. Incidentally, when actually performing the measurement, the volume occupancy is often about this, which is practically effective.
[0112]
In the estimation by the present inventors, when a space of 2400 mm cubic (measurement target space) is imaged by four cameras and the movement of one person (height 1700 mm) is measured, the volume of the person occupying the measurement target space The occupation ratio (space occupation ratio) was about 1.38%, and as shown in FIG. 17, the amount of computation was drastically reduced to about 1/50 to 1/60 as compared with the prior art.
[0113]
【The invention's effect】
In the present invention, paying attention to the property of the target object, the maximum voxel is used, and further, voxel division is performed repeatedly only on meaningful parts, so the amount of calculation can be dramatically reduced and sufficient resolution can be achieved. The process can be completed quickly while holding it.
[Brief description of the drawings]
FIG. 1 is a functional block diagram of a three-dimensional space reconstruction device according to an embodiment of the present invention.
Fig. 2 Functional block diagram
Fig. 3 Block diagram
FIG. 4 is an explanatory diagram of the maximum voxel.
FIG. 5A is a schematic diagram of the flow of the process.
(B) Overview of the process flow
(C) Outline of the processing flow
(D) Overview of the process flow
(E) Outline of the process flow
6A is an explanatory diagram of the measurement target space. FIG.
(B) Explanatory drawing of the same maximum voxel
FIG. 7A is an explanatory diagram of division of the same divided voxel.
(B) Division explanatory diagram of the same divided voxel
(C) Explanatory drawing of the divided voxel
(D) Explanatory drawing of the divided voxel
FIG. 8A is a view showing an example of the voxel state table.
(B) Example of the voxel state table
(C) Example of the voxel state table
(D) Example of the voxel state table
FIG. 9A is an explanatory diagram of the same parameter.
(B) Explanation of the parameters
FIG. 10A is an explanatory diagram of the sample voxel.
(B) Explanatory drawing of the same sample voxel
FIG. 11 is a flowchart of the same.
FIG. 12 is a flowchart of the same.
FIG. 13 is a flowchart of the same.
FIG. 14 is a flowchart of the same.
FIG. 15 is a flowchart of the same.
FIG. 16 is a flowchart of the same.
FIG. 17 is a graph showing the relationship between the calculation amount and the volume occupation ratio
FIG. 18 is a diagram illustrating the principle of conventional three-dimensional space reconstruction.
FIG. 19 is a functional block diagram of the three-dimensional space reconstruction device.
FIG. 20 is a flowchart of the same three-dimensional space reconstruction device.
[Explanation of symbols]
10 Control means
12 Multi-directional image acquisition means
14 Voxel state table
16 Maximum voxel determination means
18 Voxel dividing means
19 Voxel state determining means

Claims

A three-dimensional space reconstruction device that images a target object in a measurement target space from different directions and reconstructs the target object with a large number of minimum voxel clusters,
A deformable target object that is smaller than a cube circumscribing the target object and has six surfaces, and any of the surfaces determines a maximum voxel that cuts at least a portion of the target object Voxel determination means;
Initially, a plurality of voxels obtained by dividing the measurement target space by the maximum voxel are output as divided voxels, and after the beginning, voxel dividing means for outputting divided voxels obtained by dividing a given voxel into a certain number,
Voxel state determining means for determining whether or not each divided voxel output by the voxel dividing means and the target object overlap;
When the divided voxel determined to overlap with the target object does not satisfy a certain escape condition, the divided voxel is provided to the voxel dividing means and repeatedly divided, and the voxel state determining means includes: For both the maximum voxel and the divided voxel, only the vicinity of the surface of the given voxel is examined, and when the target object can be detected near any of the surfaces, it is determined that the voxel and the target object overlap. Characteristic 3D space reconstruction device.

The three-dimensional space reconstruction apparatus according to claim 1, wherein the constant escape condition is that the size of the divided voxel and the minimum voxel is the same.

The predetermined number is a three-dimensional space reconstruction apparatus according to claim 1 or 2, wherein the 8.

The voxel state determination unit includes a sample voxel generation unit that generates a sample voxel by sampling a part near the surface of the voxel, and detects a target object based on the sample voxel. The three-dimensional space reconstruction apparatus according to 1.

5. The three-dimensional space reconstruction apparatus according to claim 4, wherein the sample voxel is one of a plurality of voxels obtained by equally dividing a given voxel with a minimum voxel size.

A three-dimensional space reconstruction method in which a target object in a measurement target space is imaged from different directions, and the target object is reconstructed by a plurality of minimum voxel clusters,
Determining a maximum target voxel of a deformable target object that is smaller than a cube circumscribing the target object and has six surfaces, and any of the surfaces cuts at least a portion of the target object. When,
Initially outputting a plurality of voxels obtained by dividing the measurement target space by the maximum voxel as divided voxels, and outputting a divided voxel obtained by dividing a given voxel into a predetermined number from the beginning,
Determining whether each divided voxel and the target object overlaps; and
When the divided voxel determined to overlap with the target object does not satisfy a certain escape condition, the divided voxel is repeatedly divided, and in the determining step, any one of the maximum voxel and the divided voxel For 3), only the vicinity of the surface of a given voxel is examined, and when a target object can be detected in the vicinity of one of the surfaces, it is determined that this voxel and the target object overlap. .

7. The three-dimensional space reconstruction method according to claim 6, wherein the constant escape condition is that the size of the divided voxel and the minimum voxel is the same.

The three-dimensional space reconstruction method according to claim 6 or 7, wherein the predetermined number is eight.

The three-dimensional space reconstruction method according to claim 6, wherein a sample voxel is generated by sampling a part near the surface of the voxel, and a target object is detected based on the sample voxel.

10. The three-dimensional space reconstruction method according to claim 9, wherein the sample voxel is one of a plurality of voxels obtained by equally dividing a given voxel with a minimum voxel size.