(57)【要約】【課題】３次元モデル表面における最近傍点の探索処理を高速化する。【解決手段】３次元モデルを構成する３次元モデル構成部位において、下底面を６等分して得られた三角形ｖｉｃ０ｖｉ＋１と側面ｖｉｖｉ＋１ｖｉ＋１’ｖｉ’と上底面を６等分して得られた三角形ｖｉ’ｃ０’ｖｉ＋１’とからなる３次元モデル表面を最近傍点の探索処理を行う領域として特定する。【選択図】図７
2008112412.tif 000002
【特許請求の範囲】
【請求項１】
多角形の底面を有する構成部位からなる３次元モデルに対象物体の３次元位置を射影するデータ処理装置において、
上記対象物体の３次元表面を生成する３次元表面生成手段と、
上記構成部位の表面において、上記対象物体の３次元表面における所定の位置を示す３次元ポイントから上記構成部位の表面までの距離が最短となる最近傍点を探索する領域を特定する最近傍点探索領域特定手段と、
上記最近傍点探索領域特定手段によって特定された領域を構成する各平面において、それぞれ上記最近傍点を探索する最近傍点探索手段と、
上記最近傍点探索手段によって探索された複数の上記最近傍点の内、上記３次元ポイントからの距離が最も短い最近傍点を出力する最近傍点出力手段と、
上記最近傍点出力手段より出力された最近傍点から当該最近傍点に対応する上記３次元ポイントまでの距離における誤差関数を最小化する変換行列を算出することにより上記最近傍点と上記３次元ポイントとの相対位置を特定する変換行列算出手段と、
上記変換行列算出手段によって特定された上記最近傍点と上記３次元ポイントとの相対位置に基づいて上記３次元ポイントを当該３次元ポイントに対応する最近傍点の位置に射影し、上記３次元モデルを移動させる３次元モデル移動処理手段と
を備えることを特徴とするデータ処理装置。
【請求項２】
上記３次元モデルを構成する構成部位の形状は、多角柱、多角錘台、又は多角錘であることを特徴とする請求項１記載のデータ処理装置。
【請求項３】
上記最近傍点探索領域特定手段は、上記３次元モデルを構成する構成部位の底面において、上記３次元ポイントを示すベクトルと当該底面の中心点を示すベクトルと当該底面の法線ベクトルとによって算出されるベクトルに基づいて、上記最近傍点を探索する領域を特定することを特徴とする請求項１記載のデータ処理装置。
【請求項４】
上記変換行列算出手段は、上記誤差関数が所定の閾値より小さくなるまで繰り返し計算を行うことにより上記最近傍点と上記３次元ポイントとの相対位置を特定することを特徴とする請求項１記載のデータ処理装置。
【請求項５】
多角形の底面を有する構成部位からなる３次元モデルに対象物体の３次元位置を射影するデータ処理方法において、
上記対象物体の３次元表面を生成する３次元表面生成工程と、
上記構成部位の表面において、上記対象物体の３次元表面における所定の位置を示す３次元ポイントから上記構成部位の表面までの距離が最短となる最近傍点を探索する領域を特定する最近傍点探索領域特定工程と、
上記最近傍点探索領域特定工程にて特定された領域を構成する各平面において、それぞれ上記最近傍点を探索する最近傍点探索工程と、
上記最近傍点探索工程にて探索された複数の上記最近傍点の内、上記３次元ポイントからの距離が最も短い最近傍点を出力する最近傍点出力工程と、
上記最近傍点出力工程にて出力された最近傍点から当該最近傍点に対応する上記３次元ポイントまでの距離における誤差関数を最小化する変換行列を算出することにより上記最近傍点と上記３次元ポイントとの相対位置を特定する変換行列算出工程と、
上記変換行列算出工程にて特定された上記最近傍点と上記３次元ポイントとの相対位置に基づいて上記３次元ポイントを当該３次元ポイントに対応する最近傍点の位置に射影し、上記３次元モデルを移動させる３次元モデル移動処理工程と
を有することを特徴とするデータ処理方法。
【請求項６】
多角形の底面を有する構成部位からなる３次元モデルに対象物体の３次元位置を射影するデータ処理をコンピュータに実行させるプログラムであって、
上記対象物体の３次元表面を生成する３次元表面生成工程と、
上記構成部位の表面において、上記対象物体の３次元表面における所定の位置を示す３次元ポイントから上記構成部位の表面までの距離が最短となる最近傍点を探索する領域を特定する最近傍点探索領域特定工程と、
上記最近傍点探索領域特定工程にて特定された領域を構成する各平面において、それぞれ上記最近傍点を探索する最近傍点探索工程と、
上記最近傍点探索工程にて探索された複数の上記最近傍点の内、上記３次元ポイントからの距離が最も短い最近傍点を出力する最近傍点出力工程と、
上記最近傍点出力工程にて出力された最近傍点から当該最近傍点に対応する上記３次元ポイントまでの距離における誤差関数を最小化する変換行列を算出することにより上記最近傍点と上記３次元ポイントとの相対位置を特定する変換行列算出工程と、
上記変換行列算出工程にて特定された上記最近傍点と上記３次元ポイントとの相対位置に基づいて上記３次元ポイントを当該３次元ポイントに対応する最近傍点の位置に射影し、上記３次元モデルを移動させる３次元モデル移動処理工程と
を有することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、人物等の対象物体の位置及び姿勢を追跡し、３次元モデルを構築するデータ処理装置、データ処理方法、及びプログラムに関する。
【背景技術】
【０００２】
従来、人物等の対象物体の表面を、センサ等を用いて計測することにより対象物体の動作を追跡し、対象物体の動作を再現する３次元モデルを構築するデータ処理技術がある。このようなデータ処理技術では、対象物体の動作を完全に再現するために、対象物体の表面形状をセンサの計測位置からの距離で表す距離画像を対象物体に対して複数の方向から取得する。
【０００３】
複数の方向から取得された複数の距離画像は、それぞれの測定位置を示す座標系で記述されており、それぞれの相対位置姿勢を求めて座標系を統一する位置合わせ処理が必要となる。
【０００４】
この距離画像の位置合わせ問題を解決するために、例えば、非特許文献１に示すように、ＩＣＰ（Iterative Closest Point）アルゴリズムを適用する方法がある。
【０００５】
ＩＣＰアルゴリズムは、反復計算によってデータ間の対応状態の良否を示す対応点間の誤差を最小化する剛体変換パラメータを算出するものである。
【０００６】
このようなデータ処理技術にＩＣＰアルゴリズムを用いた場合、２つの距離画像中の最近傍点を対応点とし、この対応点間の誤差を最小化するような各距離画像の変換行列を繰り返し算出することによって相対位置を特定していく。
【０００７】
【非特許文献１】Ｐ．Ｊ Besl， and Ｎ．Ｄ．McKay；“A method for registration of ３‐Ｄ shapes，”ＩＥＥＥ Trans． of ＰＡＭＩ， vol．１４，No．２，pp．２３９‐２５６（１９９２）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、このＩＣＰアルゴリズムに基づく処理動作は膨大な時間を要するため、リアルタイムの適用が難しいといった問題があった。ＩＣＰアルゴリズムでは、３次元モデル表面上で最近傍点を探索する処理での計算量が多く、この計算処理に要する時間も長くなる。
【０００９】
本発明は、このような従来の実情に鑑みて提案されたものであり、最近傍点の探索処理の高速化を可能にするデータ処理装置、データ処理方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した目的を達成するために、本発明に係るデータ処理装置は、多角形の底面を有する構成部位からなる３次元モデルに対象物体の３次元位置を射影するデータ処理装置において、上記対象物体の３次元表面を生成する３次元表面生成手段と、上記構成部位の表面において、上記対象物体の３次元表面における所定の位置を示す３次元ポイントから上記構成部位の表面までの距離が最短となる最近傍点を探索する領域を特定する最近傍点探索領域特定手段と、上記最近傍点探索領域特定手段によって特定された領域を構成する各平面において、それぞれ上記最近傍点を探索する最近傍点探索手段と、上記最近傍点探索手段によって探索された複数の上記最近傍点の内、上記３次元ポイントからの距離が最も短い最近傍点を出力する最近傍点出力手段と、上記最近傍点出力手段より出力された最近傍点から当該最近傍点に対応する上記３次元ポイントまでの距離における誤差関数を最小化する変換行列を算出することにより上記最近傍点と上記３次元ポイントとの相対位置を特定する変換行列算出手段と、上記変換行列算出手段によって特定された上記最近傍点と上記３次元ポイントとの相対位置に基づいて上記３次元ポイントを当該３次元ポイントに対応する最近傍点の位置に射影し、上記３次元モデルを移動させる３次元モデル移動処理手段とを備えることを特徴とする。
【００１１】
また、上述した目的を達成するために、本発明に係るデータ処理方法は、多角形の底面を有する構成部位からなる３次元モデルに対象物体の３次元位置を射影するデータ処理方法において、上記対象物体の３次元表面を生成する３次元表面生成工程と、上記構成部位の表面において、上記対象物体の３次元表面における所定の位置を示す３次元ポイントから上記構成部位の表面までの距離が最短となる最近傍点を探索する領域を特定する最近傍点探索領域特定工程と、上記最近傍点探索領域特定工程にて特定された領域を構成する各平面において、それぞれ上記最近傍点を探索する最近傍点探索工程と、上記最近傍点探索工程にて探索された複数の上記最近傍点の内、上記３次元ポイントからの距離が最も短い最近傍点を出力する最近傍点出力工程と、上記最近傍点出力工程にて出力された最近傍点から当該最近傍点に対応する上記３次元ポイントまでの距離における誤差関数を最小化する変換行列を算出することにより上記最近傍点と上記３次元ポイントとの相対位置を特定する変換行列算出工程と、上記変換行列算出工程にて特定された上記最近傍点と上記３次元ポイントとの相対位置に基づいて上記３次元ポイントを当該３次元ポイントに対応する最近傍点の位置に射影し、上記３次元モデルを移動させる３次元モデル移動処理工程とを有することを特徴とする。
【００１２】
また、本発明に係るプログラムは、上述したデータ処理をコンピュータに実行させるものである。
【発明の効果】
【００１３】
本発明によれば、３次元モデル表面における最近傍点の探索処理の高速化が可能となる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００１５】
図１は、本発明の一実施形態におけるデータ処理装置１の構成を示すブロック図である。データ処理装置１は、カメラ１１Ｒ及びカメラ１１Ｌと、３次元表面生成部１２と、最近傍点探索領域特定部１３と、最近傍点探索部１４と、最近傍点出力部１５と、変換行列算出部１６と、３次元モデル移動処理部１７と、記憶部１８とを備えて構成される。なお、データ処理装置１の処理動作は、ＣＰＵ（Central Processing Unit）がＲＯＭ（Read Only Memory）に記憶されているプログラムをＲＡＭ（Random Access Memory）上で実行することにより制御される。
【００１６】
図２は、データ処理装置１の処理工程の概要を示す図である。データ処理装置１では、対象物体２１Ａの３次元表面２２に基づいて３次元モデル２３を移動させる。
【００１７】
カメラ１１Ｒ及びカメラ１１Ｌは、例えば人物等の対象物体２１Ａをそれぞれ右方向、左方向から撮影し、カメラ１１Ｒとカメラ１１Ｌとの視差に基づく視差画像２１を得る。
【００１８】
３次元表面生成部１２は、カメラ１１Ｒ及びカメラ１１Ｌによって得られた視差画像２１に基づいて、対象物体２１Ａの３次元表面２２を表す３次元座標（以下、３次元ポイントという。）を生成し、この３次元ポイントからなる３次元表面データを最近傍点探索領域特定部１３に供給する。
【００１９】
データ処理装置１では、３次元表面データに基づいて３次元モデル２３を移動させる。この３次元モデル２３は、形状が多角柱、多角錘、多角錘台等である構成部位（以下、３次元モデル構成部位という。）が複数個組み合わされて構成されるものである。なお、３次元モデル構成部位の形状は、多角柱、多角錘台、多角錘の何れであってもよいが、本実施の形態では、形状が正六角柱である３次元モデル構成部位２３Ａを例に挙げて説明する。
【００２０】
最近傍点探索領域特定部１３は、３次元モデル構成部位２３Ａの表面を所定の領域に分割することにより、３次元モデル構成部位２３Ａの表面において３次元ポイントから３次元モデル構成部位２３Ａまでの距離を最小とする点（以下、最近傍点という。）を探索する領域（以下、最近傍点探索領域という。）を特定する。
【００２１】
記憶部１８には、３次元モデル２３の位置を示す３次元座標等、３次元モデル２３の所定のデータがフレーム単位で記憶されている。最近傍点探索部１４は、特定のフレームにおける３次元モデル２３の所定のデータを記憶部１８から読み出し、最近傍点探索領域を構成する複数の平面において、それぞれ最近傍点の探索処理を行う。
【００２２】
最近傍点出力部１５は、３次元ポイントから最近傍点探索部１４によって探索された複数の最近傍点までの距離が最小となる最近傍点を出力する。
【００２３】
変換行列算出部１６は、最近傍点出力部１５より出力された最近傍点とこの最近傍点に対応する３次元ポイントとの距離における誤差関数を最小化するような変換行列を算出し、誤差関数が所定の閾値より小さくなるまで繰り返し計算を行い、対象物体２１Ａと３次元モデル構成部位２３Ａとの相対位置を特定する。
【００２４】
３次元モデル移動処理部１７は、変換行列算出部１６によって特定された３次元ポイントと最近傍点との相対位置に基づいて３次元ポイントを対応する最近傍点の位置に射影し、フレーム毎に複数の３次元モデル構成部位２３Ａからなる３次元モデル２３を移動させる。
【００２５】
ここで、データ処理装置１の処理動作について図３のフローチャートを参照しながら詳細に説明する。データ処理装置１では、ＩＣＰ（Iterative Closest Point）アルゴリズムを適用してカメラ１１Ｒ及びカメラ１１Ｌによって得られたフレーム単位の視差画像における３次元ポイントから３次元モデル構成部位２３Ａまでの距離を最小化するような各視差画像の変換行列を算出し、繰り返し計算を行うことによって対象物体２１Ａと３次元モデル構成部位２３Ａとの相対位置を算出することにより、３次元モデル２３を移動させる。
【００２６】
ステップＳ１において、３次元表面生成部１２は、カメラ１１Ｒ及びカメラ１１Ｌによって得られた視差画像２１を用いて対象物体２１Ａの３次元表面２２を表す３次元ポイントからなる３次元表面データを生成し、この３次元表面データを最近傍点探索領域特定部１３に供給する。
【００２７】
ステップＳ２において、最近傍点探索領域特定部１３、最近傍点探索部１４、及び最近傍点出力部１５は、図４のフローチャートに示されるステップＳ２１からステップＳ２９までの処理動作を行うことにより、対象物体２１Ａの表面における所定の３次元ポイントから３次元モデル構成部位２３Ａまでの距離が最短となる最近傍点を生成し、この最近傍点を変換行列算出部１６に出力する。
【００２８】
ステップＳ２１において、最近傍点探索領域特定部１３は、図５に示すように、３次元ポイントを示すベクトルｐと、３次元モデル構成部位２３Ａの下底面の中心点を示すベクトルｃ０と、３次元モデル構成部位２３Ａの下底面の法線ベクトルｎｃとを用いて、３次元モデル構成部位２３Ａにおいて最近傍点の探索処理を行う領域を特定するためのベクトルである単位射影ベクトルｎｐを以下の数式（１）によって算出する。
【００２９】
【数１】
2008112412.tif 000003
【００３０】
ステップＳ２２において、最近傍点探索領域特定部１３は、図６に示すように、単位射影ベクトルｎｐと角度の開始方向を示す角度開始ベクトルｎｖとによって得られる角度θを以下の数式（２）によって算出する。
【００３１】
【数２】
2008112412.tif 000004
【００３２】
なお、角度θは、正の値及び負の値の両方をとることが可能であり、以下の数式（３）において、ｚが０より大きければ正の値を、ｚが０以下であれば負の値をとる。
【００３３】
【数３】
2008112412.tif 000005
【００３４】
この図６において、θ（ｖｉ）は、角度開始ベクトルｎｖと頂点ｖｉを表す頂点ベクトルｖｉとによって得られる角度とし、θ（ｖｉ＋１）は、角度開始ベクトルｎｖと頂点ｖｉ＋１を表す頂点ベクトルｖｉ＋１とによって得られる角度とする。
【００３５】
ステップＳ２３において、最近傍点探索領域特定部１３は、ステップＳ２２にて算出された角度θに基づいて、３次元モデル構成部位２３Ａの表面において最近傍点の探索処理を行う領域を特定する。すなわち、最近傍点探索領域特定部１３は、角度θがθ（ｖｉ）＜θ＜θ（ｖｉ＋１）を満たす場合、図７に示すように、下底面を６等分して得られた三角形ｖｉｃ０ｖｉ＋１と側面ｖｉｖｉ＋１ｖｉ＋１’ｖｉ’と上底面を６等分して得られた三角形ｖｉ’ｃ０’ｖｉ＋１’とからなる３次元モデル表面を３次元モデル構成部位２３Ａにおいて最近傍点の探索処理を行う領域とする。この３次元モデル表面において最近傍点の探索処理を行うための３次元ポイントが存在可能である領域は、図８で示すように、三角柱ｖｉｃ０ｖｉ＋１ｖｉ’ｃ０’ｖｉ＋１’を拡大して得られる領域となる。
【００３６】
なお、本実施の形態において、３次元モデル構成部位の形状が例えば図９（Ａ）に示すような正六角錘台、又は図９（Ｂ）に示すような正六角錘である場合、最近傍点の探索処理を行うための３次元モデル表面は、それぞれ図１０（Ａ）に示すような三角形ｖｊｃａｖｊ＋１と側面ｖｊｖｊ＋１ｖｊ＋１’ｖｊ’と三角形ｖｊ’ｃａｖｊ＋１’とからなる３次元モデル表面、図１０（Ｂ）に示すような三角形ｖｋｃｂｖｋ＋１と側面ｖｋｃｂ’ｖｋ＋１とからなる３次元モデル表面となる。また、図１０（Ａ）、図１０（Ｂ）に示す３次元モデル表面において最近傍点の探索処理を行うための３次元ポイントが存在可能である領域は、それぞれ図１１（Ａ）に示すような三角錐台を拡大した領域、図１１（Ｂ）に示すような三角錐を拡大した領域となる。
【００３７】
ステップＳ２４において、最近傍点探索部１４は、３次元モデル構成部位２３Ａの下底面において最近傍点を探索する。このステップＳ２４において、先ず、最近傍点探索部１４は、３次元モデル構成部位２３Ａを下底面方向から見た際にベクトルｐで示される３次元ポイントが下底面を６等分して得られた三角形ｖｉｃ０ｖｉ＋１の内部に存在するか否かを以下の数式（４）によって判断する。
【００３８】
【数４】
2008112412.tif 000006
【００３９】
最近傍点探索部１４は、この数式（４）において、０＜ｉｎである場合は、ベクトルｐで示される３次元ポイントが三角形ｖｉｃ０ｖｉ＋１の外部に存在すると判断し、以下の数式（５）及び数式（６）によって算出されるベクトルｐｃで示される点を最近傍点とする。
【００４０】
【数５】
2008112412.tif 000007
【００４１】
そして、最近傍点探索部１４は、３次元ポイントからこの最近傍点までの距離を算出し、この距離と最近傍点の３次元座標とを最近傍点出力部１５に供給する。
【００４２】
一方、この数式（４）においてｉｎ＜０である場合、最近傍点探索部１４は、ベクトルｐで示される３次元ポイントが三角形ｖｉｃ０ｖｉ＋１の内部に存在すると判断し、以下の数式（７）及び数式（８）によって算出されるベクトルｐｊで示される点を最近傍点とする。なお、このベクトルｐｊで示される最近傍点は、３次元ポイントから３次元モデル構成部位２３Ａの下底面に下ろした垂線と下底面との交点に位置する。
【００４３】
【数６】
2008112412.tif 000008
【００４４】
そして、最近傍点探索部１４は、３次元ポイントからこの最近傍点までの距離を算出し、この距離と最近傍点の３次元座標とを最近傍点出力部１５に供給する。
【００４５】
ステップＳ２５において、最近傍点探索部１４は、３次元モデル構成部位２３Ａの側面において最近傍点を探索する。このステップＳ２５において、先ず、最近傍点探索部１４は、３次元モデル構成部位２３Ａを側面方向から見た際にベクトルｐで示される３次元ポイントが側面ｖｉｖｉ＋１ｖｉ＋１’ｖｉ’の内部に存在するか否かを以下の数式（９）〜数式（１２）によって判断する。
【００４６】
【数７】
2008112412.tif 000009
【００４７】
最近傍点探索部１４は、０＜ｉｎ１，０＜ｉｎ２，０＜ｉｎ３，０＜ｉｎ４の何れである場合は、ベクトルｐで示される３次元ポイントが側面ｖｉｖｉ＋１ｖｉ＋１’ｖｉ’の外部に存在すると判断する。
【００４８】
すなわち、数式（９）において０＜ｉｎ１である場合、最近傍点探索部１４は、上記数式（６）によって算出されるベクトルｐｃで示される点を最近傍点とする。
【００４９】
また、数式（１０）において０＜ｉｎ２である場合、最近傍点探索部１４は、以下の数式（１３）及び数式（１４）によって算出されるベクトルｐｃで示される点を最近傍点とする。
【００５０】
【数８】
2008112412.tif 000010
【００５１】
また、数式（１１）において０＜ｉｎ３である場合、最近傍点探索部１４は、以下の数式（１５）及び数式（１６）によって算出されるベクトルｐｃで示される点を最近傍点とする。
【００５２】
【数９】
2008112412.tif 000011
【００５３】
また、数式（１２）において０＜ｉｎ４である場合、最近傍点探索部１４は、以下の数式（１７）及び数式（１８）によって算出されるベクトルｐｃで示される点を最近傍点とする。
【００５４】
【数１０】
2008112412.tif 000012
【００５５】
一方、ｉｎ１＜０且つｉｎ２＜０且つｉｎ３＜０且つｉｎ４＜０である場合、最近傍点探索部１４は、ベクトルｐで示される３次元ポイントが側面ｖｉｖｉ＋１ｖｉ＋１’ｖｉ’の内部に存在すると判断し、以下の数式（１９）及び数式（２０）によって算出されるベクトルｐｊで示される点を最近傍点とする。なお、このベクトルｐｊで示される最近傍点は、３次元ポイントから３次元モデル構成部位２３Ａの側面に下ろした垂線と側面との交点に位置する。
【００５６】
【数１１】
2008112412.tif 000013
【００５７】
そして、最近傍点探索部１４は、３次元ポイントからこの最近傍点までの距離を算出し、この距離と最近傍点の３次元座標とを最近傍点出力部１５に供給する。
【００５８】
ステップＳ２６において、最近傍点探索部１４は、３次元モデル２３の形状が正六角錘等の錐体であるか否かを判断する。このステップＳ２６において、３次元モデル２３の形状が何れの錐体である場合はステップＳ２８に進み、錐体でない場合はステップＳ２７に進む。
【００５９】
３次元モデルの形状が錐体でない場合、ステップＳ２７において、最近傍点探索部１４は、３次元モデル構成部位２３Ａの上底面において最近傍点を探索する。このステップＳ２７において、先ず、最近傍点探索部１４は、３次元モデル構成部位２３Ａを上底面方向から見た際にベクトルｐで示される３次元ポイントが上底面を６等分して得られた三角形ｖｉ’ｃ０ｖｉ＋１’の内部に存在するか否かを以下の数式（２１）によって判断する。
【００６０】
【数１２】
2008112412.tif 000014
【００６１】
最近傍点探索部１４は、数式（２１）において、ｉｎ＜０である場合は、ベクトルｐで示される３次元ポイントが三角形ｖｉ’ｃ０ｖｉ＋１’の内部に存在すると判断し、以下の数式（２２）及び数式（２３）によって算出されるベクトルｐｊで示される点を最近傍点とする。
【００６２】
【数１３】
2008112412.tif 000015
【００６３】
一方、数式（２１）において０＜ｉｎである場合、最近傍点探索部１４は、ベクトルｐで示される３次元ポイントが三角形ｖｉ’ｃ０ｖｉ＋１’の外部に存在すると判断し、上記数式（１３）及び数式（１４）によって算出されるベクトルｐｃで示される点を最近傍点とする。
【００６４】
そして、最近傍点探索部１４は、３次元ポイントからこの最近傍点までの距離を算出し、この距離と最近傍点の３次元座標とを最近傍点出力部１５に供給する。
【００６５】
３次元モデル構成部位２３Ａの形状が錐体である場合、ステップＳ２８において、最近傍点探索部１４は、錐体の頂点を最近傍点とし、３次元ポイントからこの最近傍点までの距離を算出し、この距離と最近傍点の３次元座標とを最近傍点出力部１５に供給する。
【００６６】
ステップＳ２９において、最近傍点出力部１５は、ステップＳ２４、ステップＳ２５、及び、ステップＳ２７又はステップＳ２８で算出された最近傍点の内、３次元ポイントから最近傍点までの距離が最も短い最近傍点を変換行列算出部１６に出力する。
【００６７】
図３に戻って、ステップＳ３において、変換行列算出部１６は、最近傍点出力部１５より出力された最近傍点から対応する３次元ポイントまでの距離における誤差関数を最小化する変換行列を算出する。
【００６８】
ステップＳ４において、変換行列算出部１６は、最近傍点出力部１５より出力された最近傍点から対応する３次元ポイントまでの距離における誤差関数が所定の閾値より小さいか否かを判断する。このステップＳ４において、誤差関数が所定の閾値より小さい場合はステップＳ５に進む。一方、このステップＳ４において、誤差関数が所定の閾値以上である場合はステップＳ２に戻り、誤差関数が所定の閾値よりも小さくなるまでステップＳ２〜ステップＳ４の処理動作を繰り返す。このようなステップＳ２〜ステップＳ４の処理動作によって３次元ポイントと最近傍点との相対位置が特定される。
【００６９】
ステップＳ５において、３次元モデル移動処理部１７は、変換行列算出部１５によって特定された３次元ポイントと最近傍点との相対位置に基づいて３次元ポイントを対応する最近傍点の位置に射影し、フレーム毎に複数の３次元モデル構成部位２３Ａからなる３次元モデル２３を移動させる。
【００７０】
以下の表１は、正六角柱の３次元モデル構成部位を円柱に近似する際に３次元モデル構成部位の表面で行われる最近傍点探索処理に要する時間と、正五十角柱の３次元モデル構成部位を円柱に近似する際に３次元モデル構成部位の表面で行われる最近傍点探索処理に要する時間とを、従来より汎用的に行われているOctree Subdivisionによる最近傍点探索処理と、本実施の形態における最近傍点探索処理とで比較した結果を示すものである。
【００７１】
【表１】
2008112412.tif 000016
【００７２】
表１からもわかるように、データ処理装置１において、最近傍点探索処理に要する時間は、Octree Subdivisionによる最近傍点探索処理に要する時間に対して、３次元モデル構成部位の形状が正六角柱である場合には約０．０６２倍、３次元モデル構成部位の形状が正五十角柱である場合には約０．０３８倍となった。
【００７３】
また、表１からもわかるように、正五十角柱の３次元モデル構成部位を円柱に近似する際に行われる最近傍点探索処理に要する時間は、正六角柱の３次元モデル構成部位を円柱に近似する際に行われる最近傍点探索処理に要する時間に対して、Octree Subdivisionによる最近傍点探索処理では約１．６９３倍であるが、データ処理装置１における最近傍点探索処理では約１．０３３倍となった。
【００７４】
すなわち、データ処理装置１による最近傍点探索処理では、従来より汎用的に行われているOctree Subdivisionによる最近傍点探索処理に比べ、大幅に処理時間が短縮した。また、データ処理装置１による最近傍点探索処理では、３次元モデル構成部位の底面の形状が正ｎ角柱（ｎ＝３，４，５，・・・・・）である場合に、ｎの値を大幅に増やしても最近傍点探索処理に要する時間の増加率がOctree Subdivisionによる最近傍点探索処理に要する時間の増加率に比べて小さいままであった。
【００７５】
以上のように、本発明を適用した一実施の形態におけるデータ処理装置１では、対象物体の３次元表面に基づいて３次元モデルを構築する際に行われる最近傍点の探索処理において、３次元モデル表面における最近傍点の探索領域を所定の領域に特定するため、最近傍点の探索処理を従来に比べて高速化することが可能となる。
【００７６】
また、データ処理装置１では、複雑な形状の３次元モデルにおいても単純な形状の３次元モデルに比べて最近傍点探索処理における計算量が大幅に増加することはなく、従来に比べて処理の高速化が可能となる。
【００７７】
また、本発明を適用した一実施の形態におけるデータ処理装置１は、産業上利用される種々の装置に適用することが可能である。例えば、データ処理装置１は、対象物体に装着するマーカーとこれを検出するトラッカーを組み合わせて対象物体の動きを記録するモーションキャプチャ装置に適用することが可能である。また、例えば、データ処理装置１は、Ｘ−ｒａｙ等によって計測された骨の３次元表面を、形状が何れの多角柱である３次元モデルにモデリングする医療装置に適用することが可能である。
【００７８】
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【図面の簡単な説明】
【００７９】
【図１】本発明を適用した一実施形態におけるデータ処理装置の構成を示す図である。
【図２】本発明を適用した一実施形態におけるデータ処理装置の処理工程の概要を示す図である。
【図３】本発明を適用した一実施形態におけるデータ処理装置の処理動作を説明するためのフローチャートである。
【図４】本発明を適用した一実施形態におけるデータ処理装置の最近傍点探索処理を説明するためのフローチャートである。
【図５】３次元ポイントから３次元モデル構成部位の下底面へ射影する様子を示す図である。
【図６】単位射影ベクトルと角度開始ベクトルとにより得られる角度の算出処理を説明するための図である。
【図７】最近傍点の存在可能な領域を示す図である。
【図８】３次元ポイントの存在可能な領域を示す図である。
【図９】３次元モデル構成部位の形状の例を示す図である。
【図１０】最近傍点の存在可能な領域を示す図である。
【図１１】３次元ポイントの存在可能な領域を示す図である。
【符号の説明】
【００８０】
１  データ処理装置、１１Ｒ，１１Ｌ  カメラ、１２  ３次元表面生成部、１３  最近傍点探索領域特定部、１４  最近傍点探索部、１５  最近傍点出力部、１６  変換行列算出部、１７  ３次元モデル移動処理部、１８  記憶部
【図１】
2008112412.tif 000017
【図２】
2008112412.tif 000018
【図３】
2008112412.tif 000019
【図４】
2008112412.tif 000020
【図５】
2008112412.tif 000021
【図６】
2008112412.tif 000022
【図７】
2008112412.tif 000023
【図８】
2008112412.tif 000024
【図９】
2008112412.tif 000025
【図１０】
2008112412.tif 000026
【図１１】
2008112412.tif 000027