図面 (/)

技術 情報処理装置、プログラム、及び情報処理方法

出願人 富士通株式会社
発明者 久保田智規村田康之都市雅彦
出願日 2017年12月27日 (2年2ヶ月経過) 出願番号 2017-252263
公開日 2019年7月18日 (8ヶ月経過) 公開番号 2019-117580
状態 未査定
技術分野 画像処理 イメージ分析 光学的手段による測長装置
主要キーワード 連続箇所 分断位置 終了インデックス 従カメラ 先頭インデックス 重複検査 サブ範囲 マージソート
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2019年7月18日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

解決手段

情報処理装置は、変換部と、検出部と、探索部とを備える。変換部は、基準撮像装置撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づくシルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する。検出部は、今回取得したシルエット存在位置情報と、前回取得したシルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する。探索部は、シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う。

概要

背景

計測対象である物体の2次元情報を取得し、その2次元情報に基づいて、物体の3次元情報を推定する画像処理技術がある。

第1の技術として、例えば、計測対象から取得した2つの画像間のマッチング演算を行う際に、高精度のマッチング結果を短時間で得ることができる画像処理技術がある(例えば、特許文献1)。第1の技術では、Dynamic Programming(DPマッチングを用いたステレオ計測において、フレーム間で対応する画素輝度値に変化がない領域については、前のフレームにおける経路探索結果継承する。また、1つのフレーム処理において、隣接する走査線間で対応する画素の輝度値に変化がない領域については、1つ前の走査線における経路探索結果を継承する。

第2の技術として、例えば、第2画像のエピポーララインの上で対象物特徴点を探索する際の誤検出の防止を図り、第1カメラから対象物までの距離を精度良く算出する技術がある(例えば、特許文献2)。第2の技術では、画像処理装置は、主カメラによりワークを撮像した第1画像と、主カメラと異なる視線を有する従カメラでワークを撮像した第2画像とを取得する。そして、画像処理装置は、第2画像のエピポーララインの上を探索することで第2画像の上におけるワークの特徴点を特定し、ステレオ法によりワークまでの距離を算出する。この際、画像処理装置は、予め記憶装置に記憶されたワークの特徴量の画素数及びそのワークとの距離に基づき、第1画像におけるワークの特徴量の画素数から主カメラとワークとの距離の概略値を算出する。そして、画像処理装置は、距離の概略値に応じて、第2画像のエピポーララインの上でワークの特徴点を探索する際の探索範囲を狭めるように設定する。

第3の技術として、例えば、道路周辺地物の位置を計測する技術がある(例えば、特許文献3)。第3の技術では、画像記憶部に道路周辺を撮影した画像が記憶されている。また、3次元点群モデル記憶部には画像の撮影と同時に行われたレーザ計測により得られた3次元座標を示す点群路面形状モデルとして記憶されている。モデル投影部は点群を画像に投影し、画像表示部は画像と点群とを重ね合わせて表示装置に表示する。画像点入力部は計測対象の地物上の画素を計測画像点として入力する。近傍抽出部は、計測画像点の近傍に位置し、計測対象の地物に重なっている点を点群から抽出する。地物位置算出部は、抽出された点が示す3次元座標を、計測対象の地物の3次元座標として出力する。

概要

シルエットコーン導出する際のエピポーラ線シルエットの交わる線分探索処理高速化する。情報処理装置は、変換部と、検出部と、探索部とを備える。変換部は、基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づくシルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する。検出部は、今回取得したシルエット存在位置情報と、前回取得したシルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する。探索部は、シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う。

目的

本発明は、シルエットコーンを導出する際のエピポーラ線とシルエットの交わる線分の探索処理の高速化を目的とする

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

基準撮像装置撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する変換部と、今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する検出部と、前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う探索部と、を備えることを特徴とする情報処理装置

請求項2

前記検出部は、前記シルエット不存在範囲を累積し、累積された前記シルエット不存在範囲と今回取得される前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、前記シルエット不存在範囲を検出し、前記探索部は、前記シルエット不存在範囲に基づいて、前記シルエットの存在する範囲の探索を行うことを特徴とする請求項1に記載の情報処理装置。

請求項3

前記検出部は、パイプライン処理により、新たに取得したシルエット存在位置情報が既存の前記シルエット不存在範囲に重複しているか否かにより前記シルエット不存在範囲を検出し、検出結果に応じて検出された前記シルエット不存在範囲を該既存の前記シルエット不存在範囲に追加することを特徴とする請求項1又は2に記載の情報処理装置。

請求項4

前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部よりも前記視点側となる範囲、及び前記基準撮像装置の視点から最も遠い前記範囲の端部よりも前記視点から遠方側となる範囲を、前記シルエット不存在範囲として検出することを特徴とする請求項1に記載の情報処理装置。

請求項5

前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部と前記基準撮像装置の視点から最も遠い前記範囲の端部との間に、前記シルエットが存在しない範囲が含まれる場合に、該シルエットが存在しない範囲を前記シルエット不存在範囲として検出することを特徴とする請求項4に記載の情報処理装置。

請求項6

コンピュータに、基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換し、今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出し、前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う、処理を実行させることを特徴とするプログラム

請求項7

コンピュータが、基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換し、今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出し、前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う、処理を実行することを特徴とする情報処理方法

技術分野

0001

本発明は、情報処理装置プログラム、及び情報処理方法に関する。

背景技術

0002

計測対象である物体の2次元情報を取得し、その2次元情報に基づいて、物体の3次元情報を推定する画像処理技術がある。

0003

第1の技術として、例えば、計測対象から取得した2つの画像間のマッチング演算を行う際に、高精度のマッチング結果を短時間で得ることができる画像処理技術がある(例えば、特許文献1)。第1の技術では、Dynamic Programming(DPマッチングを用いたステレオ計測において、フレーム間で対応する画素輝度値に変化がない領域については、前のフレームにおける経路探索結果継承する。また、1つのフレーム処理において、隣接する走査線間で対応する画素の輝度値に変化がない領域については、1つ前の走査線における経路探索結果を継承する。

0004

第2の技術として、例えば、第2画像のエピポーララインの上で対象物特徴点を探索する際の誤検出の防止を図り、第1カメラから対象物までの距離を精度良く算出する技術がある(例えば、特許文献2)。第2の技術では、画像処理装置は、主カメラによりワークを撮像した第1画像と、主カメラと異なる視線を有する従カメラでワークを撮像した第2画像とを取得する。そして、画像処理装置は、第2画像のエピポーララインの上を探索することで第2画像の上におけるワークの特徴点を特定し、ステレオ法によりワークまでの距離を算出する。この際、画像処理装置は、予め記憶装置に記憶されたワークの特徴量の画素数及びそのワークとの距離に基づき、第1画像におけるワークの特徴量の画素数から主カメラとワークとの距離の概略値を算出する。そして、画像処理装置は、距離の概略値に応じて、第2画像のエピポーララインの上でワークの特徴点を探索する際の探索範囲を狭めるように設定する。

0005

第3の技術として、例えば、道路周辺地物の位置を計測する技術がある(例えば、特許文献3)。第3の技術では、画像記憶部に道路周辺を撮影した画像が記憶されている。また、3次元点群モデル記憶部には画像の撮影と同時に行われたレーザ計測により得られた3次元座標を示す点群路面形状モデルとして記憶されている。モデル投影部は点群を画像に投影し、画像表示部は画像と点群とを重ね合わせて表示装置に表示する。画像点入力部は計測対象の地物上の画素を計測画像点として入力する。近傍抽出部は、計測画像点の近傍に位置し、計測対象の地物に重なっている点を点群から抽出する。地物位置算出部は、抽出された点が示す3次元座標を、計測対象の地物の3次元座標として出力する。

先行技術

0006

特開2006−331108号公報
特開2013−257289号公報
特開2009−75117号公報

発明が解決しようとする課題

0007

物体の2次元情報に基づいて該物体の3次元形状を復元する技術として、視体積交差法により多視点映像の物体シルエット画像から物体の3次元形状を復元する技術(VisualHull)がある。この種の技術では、視体積シルエットコーン)を導出する処理においてエピポーラ線シルエットの交わる線分を探索する際の演算量が大きい。また、エピポーラ線とシルエットの交わる線分を探索する際に、エピポーラ線のうちのシルエットが交わらない区間も探索範囲に含めているため、探索処理における演算量が大きくなり、処理時間が増大する。

0008

1つの側面では、本発明は、シルエットコーンを導出する際のエピポーラ線とシルエットの交わる線分の探索処理の高速化を目的とする。

課題を解決するための手段

0009

1つの態様の情報処理装置は、変換部と、検出部と、探索部とを備える。変換部は、基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づくシルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する。検出部は、今回取得したシルエット存在位置情報と、前回取得したシルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する。探索部は、シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う。

発明の効果

0010

上述の態様によれば、シルエットコーンを導出する際のエピポーラ線とシルエットの交わる線分の探索処理の高速化が可能となる。

図面の簡単な説明

0011

本実施形態における情報処理装置の一例を示す図である。
エピポーラ幾何を説明する図である。
視体積について説明する図である。
線分探索の範囲について説明するための図である。
本実施形態における先に処理した参照Viewの線分重複範囲の最大depth,最小depthで後続する参照Viewの線分探索範囲を狭めることを説明する図である。
本実施形態における3次元形状復元装置の一例を示す図である。
VisualHull部の構成を示す図である。
本実施形態における線分探索の処理フローを示す図である。
線分重複検査部及び座標変換部によるdepth決定及び線分探索範囲制限の処理フローを示す図である。
本実施形態におけるVisualHullの処理フローを示す図(その1)である。
本実施形態におけるVisualHullの処理フローを示す図(その2)である。
パイプライン処理における線分重複検査処理開始タイミングを説明する図である。
本実施形態における視野、参照Viewからの見え方、線分端探索範囲を説明するための図である。
本実施形態におけるソート後の線分端情報格納領域を説明するための図である。
本実施形態における画面端の関係を説明する図である。
本実施形態におけるNearサブ線分端情報領域を説明するための図である。
本実施形態におけるNearサブ線分端情報領域と、重複度をnear→far用とfar→near用に分けて持つ方法を説明する図である。
本実施形態における対象View(tid)のzNear,zFarと各参照Viewの画像端(Ev1(id),Ev2(id))の関係処理を説明する図である。
本実施形態における参照Viewの2D座標におけるエピポーラ線の導出方法について説明する図である。
本実施形態における参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する方法を説明する図である。
本実施形態における線分端重複検査処理を説明する図である。
本実施形態における不要な線分端探索範囲を説明する図である。
線分重複検査処理をnearからfar方向へ実施する処理の内容を説明する図である。
線分重複検査処理をfarからnear方向へ実施する処理の内容を説明する図である。
本実施形態におけるNearサブ領域処理、Core領域処理, Farサブ領域処理を説明する図である。
図22図23のNearサブ領域処理、Core領域処理、Farサブ領域処理のフローを示す図である。
対象Viewに対して参照Viewを1つごとに都度処理しつつ線分探索の範囲を削減することにより各性能ネック要因の削減となることを説明する図である。
本実施形態におけるすべてのデータがそろってから処理を行う場合と、都度データごと処理を行う場合を説明する図である。
本実施形態におけるハードウェア構成の一例を示す図である。

実施例

0012

図1は、本実施形態における情報処理装置の一例を示す図である。図1のように、情報処理装置101は、変換部102、検出部103、探索部104、及び記憶部105を含む。

0013

変換部102は、基準撮像装置(基準カメラ)が撮像するシルエットを該基準撮像装置とは異なる視点から撮影する複数の参照撮像装置(参照カメラ)のそれぞれから、順次、シルエット存在位置情報を取得して共通の座標系に変換する。シルエット存在位置情報は、参照撮像装置に基づくシルエットの存在位置を示す情報である。変換部102の一例としては、z座標→参照[F]ローカル座標算出部16(図7参照)が挙げられる。

0014

検出部103は、今回取得したシルエット存在位置情報と、前回取得したシルエット存在位置情報との比較を行う。前回取得したシルエット存在位置情報は、例えば、記憶部105に記憶させておく。検出部103は、比較の結果に基づいて、シルエットの存在しない範囲を示すシルエット不存在範囲を検出する。検出部103の一例としては、線分重複検査部18(図7参照)が挙げられる。

0015

探索部104は、シルエット不存在範囲に基づいて、シルエットの存在する範囲の探索を行う。探索部104の一例としては、探索範囲決定部14及び線分探索部15(図7参照)が挙げられる。

0016

このように構成することにより、本実施形態の情報処理装置101では、視体積交差法により多視点映像から物体の3次元形状を復元するためのシルエットコーンを導出する際の、エピポーラ線とシルエットの交わる線分の探索処理の高速化を図ることが可能となる。

0017

検出部103は、シルエット不存在範囲を累積し、累積されたシルエット不存在範囲と今回取得されるシルエット存在位置情報との比較を行い、比較の結果に基づいて、シルエット不存在範囲を検出する。当該処理は、Central Processing unit(CPU)22(図28参照)に実行されるS11(図8参照),及びS24〜S26(図9参照)の処理に該当する。また、探索部104は、上記のように、シルエット不存在範囲に基づいて、シルエットの存在する範囲の探索を行う。当該処理は、CPU22に実行されるS10(図8参照)の処理に該当する。

0018

このように構成することにより、本実施形態の情報処理装置101が行う線分の探索処理では、求めた線分探索の範囲のうち不要な範囲を、次回他の参照撮像装置より取得したシルエット存在位置情報に基づく線分探索に反映することが可能となる。

0019

検出部103は、パイプライン処理により、新たに取得したシルエット存在位置情報が既存のシルエット不存在範囲に重複しているか否かによりシルエット不存在範囲を検出してもよい。この場合、検出部103は、検出結果に応じて検出されたシルエット不存在範囲を既存のシルエット不存在範囲に追加する。

0020

このように構成することにより、本実施形態の情報処理装置1では、線分探索については、パイプライン処理により探索不要な範囲を段階的に追加して探索範囲を狭めてゆくことが可能となる。

0021

以下では、本実施形態について詳述する。
図2は、エピポーラ幾何を説明する図である。エピポーラ幾何とは、2つの異なる視点の画像から該画像内の物体についての3次元空間内での奥行情報を復元するための幾何である。

0022

図2の点OL及び点ORは、それぞれ、Lカメラ(基準カメラ)の投影中心、及びRカメラ(参照カメラ)の投影中心である。また、図2の点XL及び点XRは、それぞれ、3次元空間(実空間)内の点Xを、Lカメラの投影面60及びRカメラの投影面61に投影した点(シルエット)である。

0023

2つのカメラは異なる3次元位置にあるので、一方のカメラから他方のカメラを見ることができる。図2の点eL及び点eRは、それぞれ、エピポール(epipole)又はエピポーラ点(epipolar point)と呼ばれる点であり、互いのカメラ(投影中心)を自カメラの投影面に投影した点である。すなわち、Lカメラの投影面60における点eLはRカメラの投影中心ORを投影面60に投影した点であり、Rカメラの投影面61における点eRはLカメラの投影中心OLを投影面61に投影した点である。ここで、投影中心(点OL及び点OR)とエピポール(点eL及び点eR)とは、3次元空間内の同一直線上に存在する。

0024

図2においてRカメラの投影面61を通る直線50は、エピポーラ線と呼ばれる直線であり、点OLと点Xとを通る直線をRカメラの投影面61に投影した直線である。

0025

Lカメラを基準カメラとし、Rカメラを参照カメラとした場合、Lカメラの投影面60における点XLと対応する3次元空間内の点は、点OLと点Xとを通る直線上に存在する。また、Lカメラの投影面60における点XLと対応する3次元空間内の点は、Rカメラの投影面61では、エピポーラ線50上に存在する。例えば、Lカメラの投影面60における点XLと対応する3次元空間内の点が点Xである場合、該点Xは、Rカメラの投影面61のうち、投影中心ORと点Xとを結ぶ線分とエピポーラ線50との交点に投影される。

0026

2つのカメラの位置関係既知であれば、エピポーラ制約として以下が成り立つ。すなわち、点XのLカメラの投影面60における点XLが与えられると、Rカメラの投影面61における線分eR-XRが定義される。点XのRカメラの投影面61における点XRはエピポーラ線50上に存在する。また、例えば、Lカメラの投影面60における点XLと対応する3次元位置が点X1である場合、Rカメラの投影面61上で点X1と対応する点は、投影中心OLと点X1とを結ぶ線分と、エピポーラ線50との交点となる。同様に、Lカメラの投影面60における点XLと対応する3次元位置が点X2又はX3である場合、Rカメラの投影面61上で点X2又はX3と対応する点は、それぞれ、投影中心OLと点X2又はX3とを結ぶ線分と、エピポーラ線50との交点となる。

0027

このように、2つのカメラで同じ点を捕捉している場合、その点は必ず互いのエピポーラ線上に存在する。すなわち、一方の投影面における点が他方の投影面を通るエピポーラ線上に存在しない場合には、同じ点を捕捉していない(対応づけが正しくない)。よって、一方のカメラで見ている点が他方のカメラのどこに映っているかは、エピポーラ線上を調べれば十分である。対応づけが正しく、点XL及び点XRの位置が分かっていれば、点Xの3次元空間での位置を三角法により決定することができる。本実施形態の情報処理装置1では、上記のエピポーラ制約に基づいた視体積交差法により多視点映像から物体の3次元形状を復元する。

0028

図3は、視体積について説明する図である。図3の(a)における点zNear及び点zFarは、Rカメラの投影面61を通るエピポーラ線50上における視野範囲の両端を示す点である。点zNearはエピポーラ線50上におけるエピポール(点eR)から一番近い点を示し、点zFarはエピポーラ線50上におけるエピポール(ここでは点eR)から一番遠い点を示す。また、図3の画面端Nearは、エピポーラ線50上における点zNear側の投影面61の端を示す。また、図3の画面端Farは、エピポーラ線50上における点zFar側の投影面61の端を示す。

0029

視体積交差法では、エピポーラ線50上のうちのMax(zNear,画面端Near)〜Min(zFar,画面端Far)の範囲でシルエット(点X)の存在有無を確認する線分探索(交点探索)を行う。ここで、Max(zNear,画面端Near)は点zNearと画面端NearのうちエピポールeRから遠いほうの点を示し、Min(zFar,画面端Far)は、点zFarと画面端FarのうちエピポールeRに近いほうの点を示す。

0030

探索する線分は、Lカメラの視点(投影中心OL)から見た物体表面を示す線分と、その背景を示す線分とを含む。線分探索により得られた線分(2次元シルエット)を投影中心ORに基づいて3次元空間に逆投影すると、図3の(b)のように、投影中心ORを頂点とする錐体(シルエットコーン)が得られる。視体積交差法では、3次元空間内における複数の画像から得た同一物体についてのシルエットコーンの交差積(Visual Hull)に基づいて、物体の3次元形状を復元する。この場合、エピポーラ線50上における線分端が3次元物体の表面の候補となり得る。

0031

ここで、参照カメラF(F=0...参照カメラ数-1)についてMax(zNear,画面端Near)〜Min(zFar, 画面端Far)の範囲で線分探索をする場合を考えてみる。

0032

図4は、線分探索の範囲について説明するための図である。
図4には、3つの参照View(V0,V1,及びV2)のそれぞれについての線分探索の結果を、z座標を共通化して示している。3つの参照Viewから物体のz座標を算出する場合、3つの線分についての論理積において1となる線分範囲に物体が存在するといえる。ここで、図4の線分探索の結果における太い実線が物体の存在する範囲を示している場合、3つの参照View(V0,V1,及びV2)のすべてで太い実線となっている区間A1及びA2が、物体のz座標の候補となる。すなわち、図4の例では、区間A1及びA2を除く他の区間は、参照Viewが増えても線分の論理積は0となるため、物体のz座標の候補となることはない。論理積が0となる範囲も探索範囲に含まれる場合、探索処理におけるメモリアクセス回数及び演算量が大きくなり、線分情報を格納しておくためのメモリサイズが大きくなる。線分端の大小関係を比較する処理はソート処理で行われる。すなわち、すべてのViewの線分で重なる箇所を探したいという目的に対して線分探索処理が過剰といえる。

0033

そこで、本実施形態では、視体積交差法により多視点映像の物体シルエット画像から物体の3次元形状を復元する際の線分探索処理において、線分探索の範囲を少なくすることにより、線分探索のメモリアクセスと演算量を削減する。例えば、図4では、他の参照Viewについての線分探索は、区間A1及びA2を含む区間Aを探索範囲として線分探索を行えば十分であるため、探索範囲を狭めてメモリアクセスの回数及び演算量を削減することが可能である。また、本実施形態では、線分情報を格納するメモリ領域を削減する。更に、本実施形態では、線分重複確認の対象となる線分数を削減して演算量を削減する。

0034

図5は、本実施形態における先に処理した参照Viewの線分重複範囲の最大depth,最小depthで後続する参照Viewの線分探索範囲を狭めることを説明する図である。

0035

図5にあるように、本実施形態では、線分の重なりを確認しなくてもよい範囲を探索範囲から除外する。なお、図5では、論理積が1となる区間A1及びA2を含み、かつ探索する範囲が最小となる1個の区間Aを、探索する意味のある範囲としている。すなわち、図5において探索する意味のある範囲とした区間Aには、実際には探索しなくてもよい区間が含まれる。このため、例えば、図5の参照View(V0,V1,及びV2)とは異なる参照Viewについての探索範囲を設定する際には、区間Aの一端(最大depth)と他端(最小depth)との間となる区間のみを探索すればよい。最大depthは区間Aのうちエピポールから遠いほうの端であり、最小depthは区間Aのうちエピポールに近いほうの端である。これにより、後続の参照Viewに対する線分探索の範囲を狭めることが可能となり、探索処理におけるメモリアクセスの回数及び演算量を低減すること、並びに線分情報を格納しておくためのメモリサイズを小さくすることが可能となる。

0036

図6は、本実施形態における3次元形状復元装置の一例を示す図である。
図6のように、3次元形状復元装置1は、視点画像生成部2、シルエット画像分離部3、パラメタパラメータ)生成部4、VisualHull部5、及びレンダリング部6を含む。

0037

視点画像生成部2は、異なる複数の視点から撮影された画像(視点画像)を生成するか、又は外部から取得する。

0038

シルエット画像分離部3は、視点画像生成部2で生成された視点画像から物体(被写体)のシルエット画像を分離する。

0039

パラメタ生成部4は、カメラパラメタ光学パラメタ[0..N-1]、位置パラメタ[0..N-1]を含む。)を取得して、各種パラメタ(変換情報)を生成する。

0040

VisualHull部5は、基準カメラ(対象カメラ)で撮影されたシルエット画像と、参照カメラで撮影されたシルエット画像をシルエット画像分離部3から取得する。また、VisualHull部5は、対象カメラを特定するID(対象カメラID(TID))と、参照カメラを特定するID(参照カメラID(RID))を取得する。また、VisualHull部5は、パラメタ生成部4で生成された変換情報を取得する。VisualHull部5は、TID、RID、変換情報、シルエット画像[TID,RID]からdepth情報を算出する。

0041

レンダリング部6は、カメラパラメタ(光学パラメタ[0..N-1]、位置パラメタ[0..N-1])、VisualHull部5が算出したdepth情報、シルエット画像分離部3が生成した非シルエット画像情報、及び視点画像生成部2が出力した視点画像[0..N-1]、並びに指定視点位置を取得する。レンダリング部6は、取得した情報に基づいて、指定視点位置から見た物体の3次元画像を生成する。

0042

図7は、VisualHull部の構成を示す図である。
図7のように、VisualHull部5は、ワールド座標→参照ローカル座標部11、エピポーラ線傾き導出部12、画面範囲導出部13、探索範囲決定部14、線分探索部15を含む。VisualHull部5は、更に、z座標→参照[F]ローカル座標変換部16、参照ローカル座標→z座標変換部17、線分バッファ[n]18、及び線分重複検査部19を含む。

0043

図8は、本実施形態における線分探索の処理フローを示す図である。以下では、図7を参照しながら、図8について説明する。

0044

線分探索処理では、まず、対象View(T)が選択される(ステップS1)。ここで、“T”は、複数のカメラのうち対象カメラ(基準カメラ)とするカメラを指定する情報である。

0045

次に、ワールド座標→参照ローカル座標変換部11が、ワールド座標を参照ローカル座標に変換する。すなわち、ワールド座標→参照ローカル座標変換部11は、変換情報Aを用いて、エピポール(T)、ZNear(T)、zFar(T)の座標を、エピポール(T)[F](x,y)、zNear(T)[F](x,y)、zFar(T)[F](x,y)に変換する(ステップS2)。ここで、“F”は、参照カメラを特定する情報である(F=0、1,2、・・・・,参照カメラ数−1)。[n]は対象Viewのシルエット点(x,y)を特定する情報である。

0046

次に、対象View(T)以外のViewのなかから参照View(F)が選択される(ステップS3)。その後、対象Viewのシルエット点(T)[n](X,Y)が選択される(ステップS4)。

0047

次に、エピポーラ線傾き導出部12が、対象Viewのシルエット点(T)[n](X,Y)と、エピポール(T)[F](x,y)と、変換情報Bから、エピポーラ線の傾き[n][F]を導出する(ステップS5)。

0048

次に、画面範囲導出部13が、参照Viewの画面範囲情報[F]と、エピポーラ線の傾き[n][F]と、エピポール(T)[F](x,y)から、画面端Near(n)[F](x,y)、画面端Far(n)[F](x,y)を導出する(ステップS6)。

0049

その後、例えば、探索範囲決定部14が、探索範囲を決定するため、参照Viewが2つ以上処理されているか否かを判定する(ステップS7)。言い換えると、ステップS7では、対象Viewに選択されているViewを除く、他のViewのうちの、2つ以上のViewに対して線分探索の処理が行われたか否かを判定する。

0050

参照Viewが2つ以上処理されていない場合(ステップS7;No)、探索範囲決定部14は、Max(zNear(T)[F](x,y),画面端Near[n][F](x,y))を探索開始[n][F](x,y)に代入する。また、探索範囲決定部14は、Min(zFar(T)[F](x,y),画面端Far[n][F](x,y))を探索終了[n][F](x,y)に代入する(ステップS8)。

0051

一方、参照Viewが2つ以上処理されている場合(ステップS7;Yes)、探索範囲決定部14は、Max(zNear(T)[F](x,y)、画面端Near[n][F](x,y),最小[F](x,y))を探索開始[n][F](x,y)に代入する。また、探索範囲決定部14は、Min(zFar(T)[F](x,y),画面端Far[n][F](x,y),最大[F](x,y))を探索終了[n][F](x,y)に代入する(ステップS9)。

0052

ステップS8又はS9の処理の後、線分探索部15は、シルエット画像R[F]、探索開始[n][F](x,y)、探索終了[n][F](x,y)、変換情報Cを用いて線分探索を行い、線分[n][F][m](開始(x,y),終了(x,y))を得る(ステップS10)。ここで、mは線分探索において検出された線分を識別するインデックスである。

0053

次に、参照ローカル座標→z座標変換部17が、線分[n][F][m](開始(x,y),終了(x,y))を参照ローカル座標からz座標へ変換し、線分[n][F][m](開始(z),終了(z))を得て、線分バッファ[n]18に格納する(ステップS11)。

0054

ステップS11の処理の後、VisualHull部5は、対象View(T)のシルエット画像すべてに対する処理を行ったか否かを判定する(ステップS12)。未処理のシルエット画像がある場合(ステップS12;No)、VisualHull部5は、ステップS4以降の処理を繰り返す。

0055

対象View(T)のシルエット画像すべてに対する処理が済んだ場合(ステップS12;Yes)、VisualHull部5は、次に、参照View(F)のすべてに対する処理を行ったか否かを判定する(ステップS13)。未処理の参照View(F)がある場合(ステップS13;No)、VisualHull部5は、ステップS3以降の処理を繰り返す。

0056

参照View(F)のすべてに対する処理が済んだ場合(ステップS13;Yes)、VisualHull部5は、次に、すべてのViewを対象View(T)としてステップS1以降の処理を行ったか否かを判定する(ステップS14)。対象View(T)に選択していないViewがある場合(ステップS14;No)、VisualHull部5は、ステップS1以降の処理を繰り返す。そして、すべてのViewを対象View(T)としてステップS1以降の処理を行うと、VisualHull部5は、現在処理の対象となっているViewの組に対する線分探索処理を終了する。

0057

このように、本実施形態の3次元形状復元装置1(情報処理装置101)では、1個のViewが対象Viewに選択された状態での参照Viewに対する処理が1回目又は2回目である場合と、3回目以降である場合とで異なる探索範囲を設定する。しかも、参照Viewに対する処理が3回目以降である場合、VisualHull部5は、既に処理が済んでいる参照Viewにおける線分探索の結果で論理積が1となる区間を含む最小の区間Aを、現在処理対象となっている参照Viewにおける探索範囲に設定する。したがって、本実施形態の三次元形状復元装置1(情報処理装置101)では、参照Viewに対する3回目以降の処理を効率よく行うことが可能となる。

0058

次に、図9を参照して、線分重複検査部19及びz座標→参照[F]ローカル座標変換部16が行う処理について説明する。

0059

図9は、線分重複検査部及び座標変換部によるdepth決定及び線分探索範囲制限の処理フローを示す図である。

0060

線分重複検査部19は、まず、シルエットn||参照View(F)が変わったか否かを判定する(ステップS21)。シルエットn||参照View(F)が変わっていない場合(ステップS21;No)、線分重複検査部19は、定期又は不定期にステップS21の判定を繰り返す。そして、シルエットn||参照View(F)が変わった場合(ステップS21;Yes)、線分重複検査部19は、次に、シルエットnの参照View(F)での線分探索が終了したかを判定する(S22)。線分探索が終了していない場合(ステップS22;No)、線分重複検査部19は、定期又は不定期にステップS21の判定を繰り返す。そして、シルエットnの参照View(F)での線分探索が終了した場合(ステップS22;Yes)、線分重複検査部19は、次に、参照Viewのうちの2つ以上で線分探索処理がされているかを判定する(ステップS23)。2つ以上の参照Viewに対する線分探索処理がされていない場合(ステップS23;No)、線分重複検査部19は、ステップS21の判定に戻る。一方、2つ以上の参照Viewに対する線分探索処理がされている場合(ステップS23;Yes)、線分重複検査部19は、線分の重複するz座標の区間を導出する(ステップS24)。ステップS24において、線分重複検索19は、先の導出した線分における重複するz座標の区間、線分[n][f-1][m](開始(z),終了(z))、線分[n][f-2][m](開始(z),終了(z))から、重複するz座標の区間を導出する。

0061

次に、線分重複検査部19は、線分重複するz座標の区間のうち最近線分の最近線端と線分重複するz座標の区間の最遠線端を、重複線端[n](最小(z),最大(z))とする(ステップS25)。

0062

次に、z座標→参照[F]ローカル座標変換部16が、重複線端[n](最小(z),最大(z))と、zNear(T)[F](x,y)、zFar(T)[F](x,y)から、参照View(F)での線分探索の制限値最小[F](x,y)、最大[F](x,y)を導出する(ステップS26)。

0063

その後、線分重複検査部19は、すべての参照Viewの線分重複検査を行ったか否かを判定する(ステップS27)。未処理の参照Viewがある場合(ステップS27;No)、線分重複検査部19は、ステップS24以降の処理を繰り返す。そして、すべての参照Viewに対する処理を行った場合(ステップS27;Yes)、線分重複検査部19は、線分重複するz座標の区間の最近線端zをdepth[n]とし(ステップS28)、処理を終了する。

0064

このように本実施形態のVisualHull部5では、線分探索の処理フローと、depth決定及び線分探索範囲制限の処理フローとが、対象View、参照View、及びシルエット画素nの変化に応じて連動して行われる。VisualHull部5は、複数のViewのうちのある特定のViewを対象Viewとし、その他のViewを参照Viewとする処理を、複数のViewのそれぞれを対象Viewに設定して実行する。

0065

なお、VisualHull部5は、線分重複検査において要求される必要な重複数に応じて、必ずしもすべてのViewを対象View、或いは参照Viewとせずに処理を切り上げてもよい。また、線分重複検査は、Viewの画面外の点を考慮した場合には、すべてのViewの線分の重複を検出する代わりに、閾値以上の線分の重複を検出としてもよい。

0066

以下では、上述した本実施形態を更に詳述する。本実施形態の3次元形状復元装置1(情報処理装置101)において線分の探索範囲を狭めていく方法は、下記(1)及び(2)の2通りに大別される。
(1)探索範囲の左右端(両端)をつめていく方法。
(2)1個の探索範囲を、該探索範囲の途中(中間部分)に存在する論理積が0となる領域で分断し、探索範囲の左右端及び分断位置からそれぞれ左右につめていく方法。

0067

なお、上記(1)の方法は(2)の方法のサブセットと捉えることができるため、以下では上記(2)について説明する。

0068

図10Aは、本実施形態におけるVisualHullの処理フローを示す図(その1)である。図10Bは、本実施形態におけるVisualHullの処理フローを示す図(その2)である。なお、図10A及び図10Bの処理フローでは、ViewNumは全View数を表す変数であり、RemViewは残りの参照View数を表す変数であり、numViewは処理した参照View数を表す変数である。

0069

VisualHull部5は、まず、図10Aのように、対象View(tid)を設定する(ステップS31)。

0070

次に、VisualHull部5は、対象View(tid)の点zNear及び点zFarと各参照Viewの画面端(E1(id)、E2(id))との関係処理を行う(ステップS32)。次に、VisualHull部5は、id=0及びnumView=0と設定する(ステップS33)。

0071

ステップS33の後、VisualHull部5は、idの値とtidの値とを比較する(ステップS34)。idとtidとが同じ場合(ステップS34;Yes)、VisualHull部5は、idをインクリメントし(ステップS41)、再度ステップS34の判定を行う。

0072

一方、idとtidとが異なる場合(ステップS34;No)、VisualHull部5は、次に、numViewをインクリメントし(ステップS35)、ViewNum−numViewの値をRemViewに代入する(ステップS36)。

0073

次に、VisualHull部5は、参照View[id]を設定し(ステップS37)、該参照View[id]におけるエピポーラ線[id]を導出する(ステップS38)。その後、VisualHull部5は、線分端探索[id]を行い(ステップS39)、線分端マージソートを行う(ステップS40)。

0074

線分端マージソートを行った後、VisualHull部5は、図10Bのように、RankTH-RemViewが0以上であるか否かを判定する(ステップS42)。RankTH-RemViewが0以上の場合(ステップS42;Yes)、VisualHull部5は、次に、RankTH-RemViewをRankTHCurに代入し(ステップS43)、線分重複検査処理を行う(ステップS44)。ステップS44の処理として、VisualHull部5は、例えば、図9のフローチャートに沿った処理(ステップS21〜S28)を行う。

0075

ステップS43及びS44の処理を行うと、VisualHull部5は、次に、RemView!=0であるか否かを判定する(ステップS45)。なお、ステップS42の判定においてRankTH-RemViewが0未満であった場合(ステップS42;No)、VisualHull部5は、ステップS43及びS44の処理を省略してステップS45の判定を行う。

0076

RemView!=0の場合(ステップS45;Yes)、VisualHull部5は、図10AのステップS41の処理を行った後、ステップS34以降の処理を行う。一方、RemView!=0ではない場合(ステップS45;No)、VisualHull部5は、次に、前景画素のすべてが処理済みであるか否か判断する(ステップS46)。未処理の前景画素がある場合(ステップS46;No)、VisualHull部5は、次の前景画素に移動し(ステップS47)、ステップS32以降の処理を行う。前景画素のすべてが処理済みである場合(ステップS46;Yes)、VisualHull部5は、depthをDepthマップへ代入し(ステップS48)、処理を終了する。

0077

次に、図10A及び図10Bのフローチャートに沿った処理をパイプライン処理として行う場合の、線分重複検査処理(ステップS42)の開始タイミングについて説明する。

0078

図11は、パイプライン処理における線分重複検査処理開始タイミングを説明する図である。線分重複検査処理はRankTH-RemView≧0を満たすときに実行される。RankTH-RemView < 0の時の線分端探索による線分端情報は、線分端マージソートによりソート後の線分端情報格納領域に格納される。

0079

RankTHは線分重複検査時に線分がRankTH分以上重なった線分端を物体の表面として検出するための値である。視体積交差法ではRankTHの値を参照View数とすることが理想である。ただし、カメラの設置条件により参照Viewからの視野に対象Viewのカメラが入らない場合や、VisualHull処理に入力されるシルエット画像(マスク画像)の精度を補正するためにRankTH<参照View数とすることがある。ここで、シルエット画像生成時に本来シルエット画素として検出されなければならない画素を検出できない場合は、シルエット画像の精度が悪くなる。このため、3次元形状復元装置1において図10A及び図10Bの処理をパイプライン処理として行う場合、図11のように、マージソート及び線分重複検査処理を開始できるタイミングはRankTH-RemViewとなる。

0080

図12は、本実施形態における視野、参照Viewからの見え方、線分端探索範囲を説明するための図である。対象Viewの前景画素1つに対してエピポーラ線上のシルエット画素(マスク画素)を探す処理(線分探索)を行った結果、参照View座標での線分端の点の位置x,y座標を得る。これらの点は3D(3次元)ワールド座標を経由して対象Viewの3Dローカル座標に変換される。変換された点はソート後の線分端情報格納領域にマージソートされる。このとき、参照View(id)の光学中心から見た線分端探索範囲は、図12に例示した4通りのパターンのいずれかとなる。第1のパターンは、点Near,点Farがともに視野80に入っているパターンである。第2のパターンは、点Nearは視野80に入っておらず、点Farは視野80に入っているパターンである。第3のパターンは、点Nearは視野80に入っており、点Farは視野80に入っていないパターンである。そして、第4のパターンは、点Near,点Farがともに視野80に入っていないパターンである。

0081

図13は、本実施形態におけるソート後の線分端情報格納領域を説明するための図である。ソート後の線分端情報格納領域は、例えば以下のような実装とする。形式は実装によって別の形式でもよい。

0082

Nearサブ線分端情報は、初期時は各Viewの処理を行う前に各Viewのエピポーラ線が交わる画面端Ev1[id]の対象Viewの3Dローカル座標におけるz座標の値E1[id].z、及び、ランクしきい値が格納される。ここで、対象Viewのあるシルエット画素(マスク画素)についてすべての参照View分の線分端探索と線分端重複処理を実行することで1単位となる。ランクしきい値については、後述する「対象View(tid)のzNear,zFarと各参照Viewの画面端(E1(id), E2(id))の関係処理」を参照されたい。

0083

また、参照Viewの線分探索を行った際に得られるエピポーラ線と参照Viewのマスク画素との交点(線分端)のうち、次の情報がランクしきい値に格納される。すなわち、対象Viewの3Dローカル座標に変換した際にE1[id].zの最大値maxE1.z以下に変換される線分端のz座標値と、線分端が線分の開始点終了点かを表す情報がランクしきい値に格納される。

0084

Farサブ線分端情報は、初期時は各Viewの処理を行う前に各Viewのエピポーラ線が交わる画面端Ev2[id]の対象Viewの3Dローカル座標におけるz座標の値E2[id].z、及び、ランクしきい値が格納される。ランクしきい値については、後述する「対象View(tid)のzNear,zFarと各参照Viewの画面端(E1(id), E2(id))の関係処理」を参照されたい。

0085

また、参照Viewの線分探索を行った際に得られるエピポーラ線と参照Viewのマスク画素との交点(線分端)のうち、次の情報がランクしきい値に格納される。すなわち、対象Viewの3Dローカル座標に変換した際にE2[id].zの最小値minE2.z以上に変換される線分端のz座標値と線分端が線分の開始点か終了点かを表す情報が、ランクしきい値に格納される。

0086

Core線分端情報は、上記以外の参照Viewの線分探索を行った際に得られるエピポーラ線と参照Viewのマスク画素との交点(線分端)の対象Viewの3Dローカル座標に変換したz座標値と線分端が線分の開始点か終了点かを表す情報が、ランクしきい値に格納される。

0087

なお、Near.z ≧maxE1.zの場合にはNearサブ線分端情報は要素数0となる。また、Far.z ≦minE2.zの場合にはNearサブ線分端情報は要素数0となる。

0088

ここで、ランクしきい値に格納する値について、例えば以下のようにする。これは、領域分割時分割点における現時点ランク値を保持する理由のためである。実装上の事項であり実装により別の方法を選択してもよい。

0089

開始点:-(2*RankTH)
終了点:-(2*RankTH+1)
開始点+Rank保存:-(2*Rank)
終了点+Rank保存:-(2*Rank+1)

0090

この場合、符号から、要素に格納されているものが開始点又は終了点なのか(この場合は負)、画面境界点なのか(この場合は正)を見分ける。また、分割点における現時点のランク値はRankTHを超えないので、負値の絶対値/2≧RankTHであれば開始点又は終了点が格納され、負値の絶対値/2偶数であれば開始点、負値の絶対値が奇数であれば終了点と見分ける。

0091

次に、対象View(tid)の点zNear,点zFarと各参照Viewの画面端(Ev1(id), Ev2(id))との関係処理(ステップS32)の内容について説明する。

0092

図14は、本実施形態における画面端の関係を説明する図である。
対象Viewの3D(3次元)ローカル座標系において、各参照Viewの画面端を対象Viewの3Dローカル座標系に写像した点のzNear.z側をE1.z[id], 各参照Viewの画面端を対象Viewの3Dローカル座標系に写像した点のzFar.z側をE2.z[id]とする。ここで、図14の各座標系における斜線部分は、該当参照Viewの線分端探索では画面外となるため線分端探索が行われない。

0093

本実施形態では、予めすべての参照ViewのE1.z[id]の最大値maxE1.zを求め、Near.z=max(zNear.z,zNear側制限)からmaxE1.zの範囲をNearサブ範囲と定義する。同様に、本実施形態では、zFar.z側について、予めすべての参照ViewのE2.z[id]の最小値minE2.zを求め、minE2.zからFar.z=min(zFar.z,zFar側制限)の範囲をFarサブ範囲と定義する。

0094

また、予めすべての参照Viewについて、斜線部分をひとつの線分が存在すると考え、Nearサブ範囲では、予めすべての参照ViewのE1.z[id]についてソート処理を行いNearサブ線分端情報領域に格納する。同様に、Farサブ範囲では、予めすべての参照ViewのE2.z[id]についてソート処理を行いFarサブ線分端情報領域に格納する。このとき、zNear.z以下の点は格納しない。また、E1.z[id]が同一になった場合にはE1.z[id]自体は1要素のみ格納され、重複度が図14の斜線部分の重なりに応じた数となる。

0095

zNear,E1.z[id]格納要素には該当E1.z[id]から隣接のzFar側のE1.z[id]までの斜線部の重複数情報が付加されている。同様に、zFar,E2.z[id]格納要素には該当E2.z[id]から隣接のzNear側のE2.z[id]までの斜線部の重複数情報が付加されている(図15)。

0096

図15は、本実施形態におけるNearサブ線分端情報領域を説明するための図である。以下では、Near側のNearサブ線分情報格納領域について説明するが、Far側のFarサブ線分情報格納領域も同様である。

0097

図15のように、それぞれの区間のランクしきい値RankTH’を定義する。つまり、各区間ではRankTH’を満たすzNearに一番近い点が求めたいエッジである。

0098

各参照Viewの線分探索時に、見つけた線分端情報とNearサブ線分端情報とをマージソートする。見つけた線分端情報とNearサブ線分端情報は、それぞれごとには既にzNear.zからzFar.zへ昇順に並んでいるためである。見つけた線分端情報は画面端の点と区別し、見つけた線分端情報の線分開始点と線分終了点も区別する(例えば重複度に開始点-1、終了点-2を入れる)。参照View(id)の線分探索後のマージソート後におけるNearサブ線分端情報の要素数は、マージソート前のNearサブ線分端情報+線分開始点数(id)+線分終了開始点数(id)となる。

0099

線分重複検査部19は、線分重複検査処理において各領域のnear側からfar側に検査して条件を満たした際には処理を切り上げる。各領域のfar側からnear側に検査して線分探索のEndの範囲を狭める場合には、実装によるが、例えば重複度をnear→far用とfar→near用に分けて持つ方法も考えられる(図16及び図17参照)。ここで、図16は、本実施形態におけるNearサブ線分端情報領域と、重複度をnear→far用とfar→near用に分けて持つ方法を説明する図である。

0100

線分重複検査部19が行う線分重複検査処理は、各領域のnear側からfar側に検査して条件を満たした際にも、処理を切り上げずに領域すべてを検査してEndの範囲を狭める方法も考えられる。

0101

次に、線分重複検査処理の概要について説明する。
対象View(tid)の点zNear,点zFarと各参照Viewの画面端(Ev1(id), Ev2(id))の関係処理を行った後には次のようにランクしきい値RankTH’が格納されている。すなわち、Nearサブ線分端情報格納領域とFarサブ線分端情報格納領域に各参照Viewの画面端の対象Viewの3Dローカル座標変換したz座標と線分探索されず仮に線分があるものとして扱う部分の重複を考慮したランクしきい値RankTH’が格納されている。

0102

線分探索を行うごとに、上記領域に線分探索の結果を対象Viewの3Dローカル座標に変換してz座標を求め、マージソートを行う。その際に、各領域の開始インデックス終了インデックスをデータの挿入数に合わせて変更する。

0103

線分重複検査部19は、View2つ分の線分探索が終わった段階で動作(線分重複検査処理)を開始し、その後線分探索のView数が増えるごとにマージソートと線分重複検査処理を行う。

0104

線分重複検査処理ではzNear側から一番近いマスク画素との交点のz座標を求め、それが対象Viewから見た該当画素への距離となる。対象Viewから見た物体の表面までの距離のみを求める場合にはこの段階で線分重複検査処理を切り上げてもよいし、存在する線分すべてに対して重複度の検査を行ってもよい。物体の分離精度を向上するために、表面の距離から数点分(例えば3点まで)求める場合は、開始点-終了点-開始点、で切り上げる。この場合、対象Viewから見て表面までの距離、その表面から突入した物体から抜ける表面までの距離、その裏の次の物体の表面までの距離が求まることになる)求めることを行ってもよい。

0105

必要な点以外の線分重複検査処理を行うことは必要ない点を求めるための処理がかかることを意味し、この不必要な処理を省くことで演算量の削減となる。

0106

本実施形態は、不必要な処理を省くために、以下の情報は参照Viewを処理するにつれて制限することを実現する。
・Nearサブ線分端情報格納領域の線分探索開始点(LSMin[0])
・線分探索終了点(LSMax[0])、Core線分端情報格納領域の線分探索開始点(LSMin[1])
・線分探索終了点(LSMax[1])、Farサブ線分端情報格納領域の線分探索開始点(LSMin[2])
・線分探索終了点(LSMax[2])

0107

LSMin[Z],LSMax[Z](Z=0,1,2)は対象Viewの3D座標におけるz座標である。線分重複検査処理では、これを対象Viewの3D座標における(x,y,z)からワールド三次元座標、参照Viewの2D(二次元)座標へと、線分端情報の射影と逆方向の射影により線分探索の該当エピポーラ線上に射影する。

0108

図17は、本実施形態における対象View(tid)のzNear,zFarと各参照Viewの画像端(Ev1(id),Ev2(id))の関係処理を説明する図である。

0109

本実施形態におけるVisualHullの処理では、線分重複検査処理を行うごとに、
Nearサブ線分端情報格納領域に対応する線分探索範囲LSMax[0]〜LSMax[0]
Core線分端情報格納領域に対応する線分探索範囲LSMax[1]〜LSMax[1]
Farサブ線分端情報格納領域に対応する線分探索範囲LSMax[2]〜LSMax[2]
ソートマージを行い、各領域の先頭インデックスと終了インデックスをデータの挿入に合わせて更新する。

0110

次に、座標変換関連の行列について説明する。座標変換関連の行列は以下を用いる。
回転行列(3x3) RMat
並進ベクトル(1x3) TVec
カメラ内部パラメタ(3x3) AMat
ARMat = AMat*RMat
ATMat = AMat*TVec
invRTMat = RMat^{-1}×TVec
invRMatinvAMat=RMat^{-1}×AMat^{-1}

0111

次に、参照Viewの2D座標におけるエピポーラ線の導出方法について説明する。
図18は、本実施形態における参照Viewの2D座標におけるエピポーラ線の導出方法について説明する図である。

0112

エピポーラ線を導出する際には、VisualHull部5は、まず、図18のように、対象Viewのカメラ位置(3Dワールド座標系)を参照View(id)の2Dローカル座標系に変換してエピポールを導出する。その後、VisualHull部5は、参照View(id)の投影面におけるエピポールの位置及び対象Viewのカメラ位置及び投影面内のシルエットの位置に基づいて、エピポーラ線を導出する。このとき、VisualHull部5は、例えば、図18に示したようなアルゴリズムによりエピポーラ線を導出する。

0113

次に、参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する方法について説明する。

0114

図19は、本実施形態における参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する方法を説明する図である。

0115

参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する処理は、対象Viewの3D座標を参照Viewの2D座標における(x,y)座標に変換する処理の逆変換となる。すなわち、参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する処理では、図19のように、まず、参照Viewの2D座標における(x,y)座標をワールド3D座標に変換する。その後、ワールド3D座標を、対象View(tid)のローカル3D座標に変換する。

0116

例えば、下記アルゴリズムにより3Dワールド座標をローカル2D座標に変換する場合を考える。

0117

(t0 = ARMat × (world3Dx
t1 world3Dy
t2) world3Dz)

Pos0 = t0 +ATMat[0]
Pos1 = t1 + ATMat[1]
Pos2 = t2 + ATMat[2]

Pos2!=0.0の場合、z=1にスケーリング
local2Dx = Pos0/Pos2
local2Dy = Pos1/Pos2
Pos2==0.0の場合、
local2Dx = infinite
local2Dy = infinite

Pos2 >= 0 点がスクリーンより前にある
Pos2 < 0 点がスクリーンより手前にある

0118

この場合、ローカル2D座標をワールド3D座標に変換するアルゴリズムは、下記のようになる。

0119

(t0 = invRinvAMat × (local2Dx×s
t1 local2Dy×s
t2) s)
(world3Dx = (t0 - invRTMat
world3Dy t1
world3Dz t2)
s = 1 (3Dワールド座標→2D投影座標(ローカル2D座標)でz=1にスケーリング)

0120

更に、ワールド3D座標を対象Viewの3D座標(ローカル3D座標)に変換するアルゴリズムは、下記のようになる。

0121

(t0 = RMat× (world3Dx
t1 world3Dy
t2) world3Dz)
(local3Dx = (t0 + TVec
local3Dy t1
local3Dz t2)

0122

なお、上記のアルゴリズムは、参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換するアルゴリズムの一例である。座標変換のアルゴリズムは、適宜変更可能である。

0123

次に線分端重複検査処理について説明する。
図20は、本実施形態における線分端重複検査処理を説明する図である。

0124

図20における「初期」は、線分端重複検査処理の開始時に相当する。線分端重複処理における初期段階では、図20のように、Nearサブ領域、Core領域、Farサブ領域の各領域間にはRankの連続性が存在する。この場合にはNearサブのNear側、FarサブのFar側のみから線分探索の範囲を削減することが可能である。

0125

その後、処理を進めてViewを重ねると、線分重複検査部19は、Nearサブ領域-Core領域間のCore領域に存在するNear側に一番近い不要な線分端探索範囲と、Core領域-Farサブ領域のCore領域に存在するFar側に一番近い不要な線分端探索範囲を見つける。不要な線分端探索範囲が見つかった場合、線分重複検査部19は、そこを基点としてRankの確認ができるため、線分探索の範囲を削減することが可能となる。

0126

図21は、本実施形態における不要な線分端探索範囲を説明する図である。
図21には、サブ領域とCore領域の分割位置を決める例を示している。この位置に参照Viewを重ねてゆき、不要な線分端探索範囲を検出した後にはすべての参照Viewで線分が存在していたとしても、最終的に線分の重複度がRankTHを超えることはなく線分として検出されないからである。

0127

なお、実装の煩雑さを考慮しなければ、各領域についてRankの非連続箇所を検出したときに、都度領域分割して各領域についてViewを重ねるごとに線分端探索の範囲を削減することも可能である。

0128

図22は、線分重複検査処理をnearからfar方向へ実施する処理の内容を説明する図である。図23は、線分重複検査処理をfarからnear方向へ実施する処理の内容を説明する図である。

0129

本実施形態のVisualHullの処理では、図22のフローチャートに沿った処理を行うことにより、領域のnear側の範囲を削減することが可能となる。図22のnearからfar方向への処理では、線分開始点でRankを+1, 線分終了点でRankを-1する。ここで、開始点のランクは、nearからfar方向に線分端探索するときの範囲において一番near側(線分端探索開始点)のランク値である。

0130

また、本実施形態のVisualHullの処理では、図23のフローチャートに沿った処理を行うことにより、領域のfar側の範囲を削減することが可能となる。図23のfarからnear方向への処理では、線分開始点でRankを-1, 線分終了点でRankを+1する。ここで、終了点のランクはnearからfar方向に線分端探索するときの範囲において一番far側(線分端探索終了点)のランク値である。

0131

図22及び図23の処理フローにおけるstopCntは、線分重複検査処理でRankを満たす線分端を探す数を制御する。不要な線分端探索範囲を決定していない場合にはすべての線分端を検査する必要がある。不要な線分端探索範囲を決定した場合には、必要な数の表面位置(z座標値)を求めれば切り上げてよい。outCntはz座標値の出力数である。stopCnt,outCntはNearサブ領域、Core領域, Farサブ領域を通した処理で必要な表面位置の数を考慮してそれぞれの領域の処理に設定してもよい。

0132

なお、図22の処理フローに沿った処理及び図23の処理フローに沿った処理を連続して行う場合、処理の順序は問わない。すなわち、nearからfar方向へ実施する処理の後でfarからnear方向へ実施する処理を行ってもよいし、逆に、farからnear方向へ実施する処理の後でnearからfar方向へ実施する処理を行ってもよい。

0133

図24は、本実施形態におけるNearサブ領域処理、Core領域処理, Farサブ領域処理を説明する図である。図25は、図22図23のNearサブ領域処理、Core領域処理、Farサブ領域処理のフローを示す図である。図25におけるElm[n].重複度[a]≧0の処理より左側の分岐は画面端情報を含む領域の処理のみで使われる。Core領域は基本的に右側の分岐の処理のみとなる。

0134

次に、パイプラインで絞る処理のメリットについて説明する。
図26は、対象Viewに対して参照Viewを1つごとに都度処理しつつ線分探索の範囲を削減することにより各性能ネック要因の削減となることを説明する図である。図27は、本実施形態におけるすべてのデータがそろってから処理を行う場合と、都度データごと処理を行う場合を説明する図である。

0135

対象Viewに対して参照Viewを1つごとに都度処理しつつ線分探索の範囲を削減することにより、図26に示す各性能ネック要因の削減となる。特に、VisualHullの処理はメモリアクセス要因の性能劣化が大きいため効果がある。

0136

また、連続的なデータを処理する場合に、対象Viewに対して参照Viewを1つごとに都度処理する利点がある。例えばデータ転送帯域の状況やシルエット画像(マスク画像)生成処理の処理時間の関係でシルエット画像がViewごとに適宜到着する。この場合、図27のように、必要最小限のシルエット画像(対象Viewと1つの参照View)がそろった段階で処理を進めると(データ投入と処理をパイプライン的に実行すると)、データ転送の時間が処理時間に隠ぺいすることが可能となる。このため、都度データごとに処理を行うことにより、すべてのデータがそろってから処理を行う場合と比べて、トータルの処理時間は短縮される。

0137

図28は、本実施形態におけるハードウェア構成の一例を示す図である。
上記の情報処理装置101及び3次元形状復元装置1は、例えば、コンピュータ21である。コンピュータ21は、図28のように、中央演算装置(CPU)22,メモリ23、ハードディスクドライブ(HDD)24、ネットワークインタフェースカード(NIC)25、入力インタフェース26及びビデオインタフェース27を含む。以下、インタフェースを「I/F」と称する。

0138

CPU22は、メモリ23、HDD24、NIC25、入力I/F26及びビデオI/F27に接続されている。入力I/F26にはキーボードマウス、カメラ等の入力装置28が接続されている。ビデオI/F27には、ディスプレイ29が接続されている。

0139

CPU22は、プロセッサの一例であって、コンピュータ21の全体動作を制御する中央演算装置である。メモリ23は、ワーキングエリアとして機能する。

0140

HDD24は、大容量記憶装置の一例であって、オペレーティングシステム(OS)やシミュレーション用のプログラムが格納されている記憶装置である。NIC25は、インターネットローカルエリアネットワーク(LAN)等の通信ネットワーク有線又は無線で接続するためのインタフェースである。

0141

入力I/F26は、入力装置28から入力された指令をCPU22へ伝達するインタフェースである。ビデオI/F27は、ディスプレイ29に画像を出力するインタフェースである。

0142

CPU22は、HDD24に格納されている本実施形態に係るプログラムを読み出し、実行する。基準カメラ(対象カメラ)及び参照カメラからの画像データ及びその他のデータは、予めHDD24に格納されているものとする。なお、本実施形態に係るプログラムは、HDD24に限らず、ネットワークを介して接続される外部装置や、メモリカード光学ディスク等の可搬型記録媒体等の、各種の非一時的な記録媒体に記録しておいてもよい。

0143

コンピュータ21が本実施形態に係るプログラムを実行している間、CPU22は、図1の情報処理装置101における変換部102、検出部103、及び探索部104として機能する(動作する)。また、コンピュータ21が本実施形態に係るプログラムを実行している間、メモリ23及びHDD24、或いは他の記憶装置や記録媒体は、図1の情報処理装置101における記憶部105として機能する。

0144

更に、別の観点では、本実施形態に係るプログラムを実行している間、CPU22は、例えば、図6の3次元物体復元装置1におけるシルエット画像分離部3、パラメタ生成部4、VisualHull部5、及びレンダリング部6として機能する(動作する)。

0145

本実施形態によれば、線分重複検査部で先に処理をした参照Viewの線分重複範囲におけるz座標の最小線分端及び最大線分端を後続の参照Viewの線分探索における範囲制限に追加考慮する線分範囲設定部を持つことができる。

0146

これにより、従来の各参照Viewの線分探索についてMax(zNear,画面端Near)〜Min(zFar, 画面端Far)の範囲を行うことに対して、線分探索部及び線分重複検査部の演算量と線分バッファのメモリ使用量を少なくすることができる。

0147

なお、本発明は、以上に述べた実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の構成又は実施形態を取ることができる。

0148

上記の実施形態に関し、更に以下の付記を開示する。
(付記1)
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する変換部と、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する検出部と、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う探索部と、
を備えることを特徴とする情報処理装置。
(付記2)
前記検出部は、前記シルエット不存在範囲を累積し、累積された前記シルエット不存在範囲と今回取得される前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、前記シルエット不存在範囲を検出し、
前記探索部は、前記シルエット不存在範囲に基づいて、前記シルエットの存在する範囲の探索を行う
ことを特徴とする付記1に記載の情報処理装置。
(付記3)
前記検出部は、パイプライン処理により、新たに取得したシルエット存在位置情報が既存の前記シルエット不存在範囲に重複しているか否かにより前記シルエット不存在範囲を検出し、検出結果に応じて検出された前記シルエット不存在範囲を該既存の前記シルエット不存在範囲に追加する
ことを特徴とする付記1又は2に記載の情報処理装置。
(付記4)
前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部よりも前記視点側となる範囲、及び前記基準撮像装置の視点から最も遠い前記範囲の端部よりも前記視点から遠方側となる範囲を、前記シルエット不存在範囲として検出する
ことを特徴とする付記1に記載の情報処理装置。
(付記5)
前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部と、前記基準撮像装置の視点から最も遠い前記範囲の端部との間に、前記シルエットが存在しない範囲が含まれる場合に、該シルエットが存在しない範囲を前記シルエットが存在する範囲に含める
ことを特徴とする付記4に記載の情報処理装置。
(付記6)
前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部と、前記基準撮像装置の視点から最も遠い前記範囲の端部との間に、前記シルエットが存在しない範囲が含まれる場合に、該シルエットが存在しない範囲を前記シルエット不存在範囲として検出する
ことを特徴とする付記4に記載の情報処理装置。
(付記7)
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換し、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出し、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う、
処理をコンピュータに実行させることを特徴とするプログラム。
(付記8)
前記コンピュータに、更に、前記探索後、前記シルエット不存在範囲を累積し、
前記シルエットの検出において、累積された前記シルエット不存在範囲と今回取得される前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、前記シルエット不存在範囲を検出し、
前記探索において、前記シルエット不存在範囲に基づいて、前記シルエットの存在する範囲の探索を行う
処理を実行させることを特徴とする付記7に記載のプログラム。
(付記9)
前記検出において、パイプライン処理により、新たに取得したシルエット存在位置情報が既存の前記シルエット不存在範囲に重複しているか否かにより前記シルエット不存在範囲を検出し、検出結果に応じて検出された前記シルエット不存在範囲を該既存の前記シルエット不存在範囲に追加する
ことを特徴とする付記7又は8に記載のプログラム。
(付記10)
コンピュータが、
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換し、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出し、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う、
処理を実行することを特徴とする情報処理方法。
(付記11)
前記コンピュータは、更に、前記探索後、前記シルエット不存在範囲を累積し、
前記シルエットの検出において、累積された前記シルエット不存在範囲と今回取得される前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、前記シルエット不存在範囲を検出し、
前記探索において、前記シルエット不存在範囲に基づいて、前記シルエットの存在する範囲の探索を行う
ことを特徴とする付記10に記載の情報処理方法。
(付記12)
前記検出において、パイプライン処理により、新たに取得したシルエット存在位置情報が既存の前記シルエット不存在範囲に重複しているか否かにより前記シルエット不存在範囲を検出し、検出結果に応じて検出された前記シルエット不存在範囲を該既存の前記シルエット不存在範囲に追加する
ことを特徴とする付記10又は11に記載の情報処理方法。

0149

101情報処理装置
102 変換部
103 検出部
104 探索部
105 記憶部
1 3次元形状復元装置
2視点画像生成部
3シルエット画像分離部
4パラメタ生成部
5 VisualHull部
6レンダリング部
11,16,17座標変換部
12エピポーラ線傾き導出部
13画面範囲導出部
14探索範囲決定部
15線分探索部
18線分バッファ[n]
19 線分重複検査部
21コンピュータ
22中央処理装置(CPU)
23メモリ
24ハードディスクドライブ(HDD)
25ネットワークインタフェースカード(NIC)
26入力インタフェース
27ビデオインタフェース
28入力装置
29 ディスプレイ

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ