図面 (/)

技術 遮蔽された部分の表面を対称性の算出により見込み復元するための技術

出願人 ストライダーラブス,インコーポレイテッド
発明者 サラン、セバスチャンヴェッグブレイト、エリオット
出願日 2004年12月10日 (16年0ヶ月経過) 出願番号 2006-544054
公開日 2007年8月23日 (13年4ヶ月経過) 公開番号 2007-524085
状態 特許登録済
技術分野 光学的手段による測長装置 画像処理 イメージ分析
主要キーワード 遮蔽空間内 部分特性 初期開始点 垂直特性 内部遮蔽 ブーリアン型 電磁スペクトラム 収縮限界
関連する未来課題
重要な関連分野

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

図面 (8)

解決手段

所与物体遮蔽面の見込み3Dマップを計算するシステムに関する。このシステムは、物体の視認可能面の初期3Dマップを取得し、初期3Dマップから1以上の対称性を特定する。システムは、初期3Dマップの点を特定された対称性にしたがって遮蔽空間投影することにより、遮蔽面の見込み3Dマップを計算する。このシステムは初期3Dマップを取得するための画像装置を含む。現実の遮蔽面は隠されているが故に完全にはわからない。しかし、計算された3Dマップは実際の遮蔽空間に多くの点で近似する。なぜなら、ほとんどの物体は1以上の対称性をもっており、計算された3Dマップは物体の初期3Dマップにおいて特定されたそのような対称性に基づくからである。

概要

背景

この発明は、物体を観察してその物体の表面の3次元(3D)マップ写像)を作成する技術に関連し、視界から隠されている物体表面の3Dマップを見込み作成する。物体の3Dモデリングは多くのアプリケーションに必要とされている。このようなアプリケーションとしては、CAD(Computer-Aided Design)、CAM(Computer-Aided Manufacturing)、電子商取引ロボット工学ディジタルエンターテインメントなどがある。通常、広く分散された複数の視点ビューポイント)から物体の画像や範囲データ(range data)を取得した上で、物体の3Dマップを形成する。これら複数のビューポイントは、取得された全ての画像の中に物体の全面が含まれるように設定される。このような複数のビューポイントから得られた情報が既知の技術によりつなぎ合わされることにより、物体の3Dモデルが形成される。

概要

所与の物体の遮蔽面の見込み3Dマップを計算するシステムに関する。このシステムは、物体の視認可能面の初期3Dマップを取得し、初期3Dマップから1以上の対称性を特定する。システムは、初期3Dマップの点を特定された対称性にしたがって遮蔽空間投影することにより、遮蔽面の見込み3Dマップを計算する。このシステムは初期3Dマップを取得するための画像装置を含む。現実の遮蔽面は隠されているが故に完全にはわからない。しかし、計算された3Dマップは実際の遮蔽空間に多くの点で近似する。なぜなら、ほとんどの物体は1以上の対称性をもっており、計算された3Dマップは物体の初期3Dマップにおいて特定されたそのような対称性に基づくからである。

目的

通常、ロボットエンドエフェクタ(end-effector)で物体を掴むには、向かい合った関係にある面が必要である。たとえば、平行顎型把持子で物体を掴むには、物体は平行に向かい合っている面を持たねばならない。複数の指を持つ機械の手は平行する面のない物体を掴むことができるが、それでもなんらかのかたちで向かい合っている面を必要とする。一つのビューポイントからの画像は、物体表面の一部に関する情報を提供するにすぎない。単一ビューポイントからの視認可能面だけでは接触するのに有用な面の情報を充分に得られないため、うまく物体を把持するのは難しい。物体のうまく把持するためには、自己遮蔽された部分の表面も見込み計算により取得できることが望ましい。

効果

実績

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

この技術が所属する分野

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

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

請求項1

物体視認可能面の初期3Dマップを取得する画像装置と、前記初期3Dマップから1以上の対称性を特定し、前記1以上の対称性と前記初期3Dマップから遮蔽面の3Dマップを見込み計算する計算装置と、を備えることを特徴とする物体の遮蔽面の3Dマップを見込み計算するシステム

請求項2

前記画像装置は、3つのカメラを含むことを特徴とする請求項1に記載のシステム。

請求項3

前記画像装置は、パターン光投影機を含むことを特徴とする請求項1に記載のシステム。

請求項4

前記画像装置は、アクティブ照明によるデンス・ステレオ視(dense stereo with active illumination)によって前記初期3Dマップを取得することを特徴とする請求項1に記載のシステム。

請求項5

前記画像装置は、複数の画像方式(imaging modalities)から得られた結果を統合することにより、前記初期3Dマップを取得することを特徴とする請求項1に記載のシステム。

請求項6

前記画像装置は、レーザーレンジファインダ(laser range finder)を含むことを特徴とする請求項1に記載のシステム。

請求項7

既知ビューポイントから観察された物体の視認可能面の初期3Dマップを取得する手段と、前記初期3Dマップから1以上の対称性を特定する手段と、前記1以上の対称性と前記初期3Dマップから遮蔽面の3Dマップを見込み計算する手段と、を備えることを特徴とする物体の遮蔽面の3Dマップを見込み計算するシステム。

請求項8

既知のビューポイントから観察された物体の視認可能面の初期3Dマップを取得するステップと、前記初期3Dマップから1以上の対称性を特定するステップと、前記1以上の対称性と前記初期3Dマップから遮蔽面の3Dマップを見込み計算するステップと、を備えることを特徴とする物体の遮蔽面の3Dマップを見込み計算する方法。

請求項9

前記初期3Dマップから1以上の対称性を特定するステップは、前記初期3Dマップの一部に対して局所的に成立する1以上の部分対称性を検出するステップ、を含むことを特徴とする請求項8に記載の方法。

請求項10

前記1以上の部分対称性を検出するステップは、対称型を特定するステップと、数値パラメータベクトルおよびドメインを算出するステップと、を含むことを特徴とする請求項9に記載の方法。

請求項11

前記対称型は、鏡映面対称、鏡映軸対称、鏡映点対称、2重鏡映面対称、3重鏡映面対称、回転軸対称回転点対称および鏡映面に直交する回転軸対称を含む集合から選択されることを特徴とする請求項10に記載の方法。

請求項12

前記対称型は、回転軸対称についての楕円と回転点対称についての楕円体により定義される一般化された回転対称を含む集合から選択されることを特徴とする請求項10に記載の方法。

請求項13

前記対称型は、平面ではない鏡映面対称により定義される一般化された鏡映対称を含む集合から選択されることを特徴とする請求項10に記載の方法。

請求項14

前記対称型は、曲がった軸によって定義される一般化された回転軸対称と曲がった軸によって定義される一般化された鏡映軸対称を含む集合から選択されることを特徴とする請求項10に記載の方法。

請求項15

前記対称型を特定するステップは、候補となる対称型についての階層構造にしたがって探索するステップ、を含むことを特徴とする請求項10に記載の方法。

請求項16

候補となる対称型についての階層構造にしたがって探索するステップは、鏡映平面対称型の探索から開始されることを特徴とする請求項15に記載の方法。

請求項17

前記数値パラメータベクトルを算出するステップは、空間内における離散点について数値パラメータベクトル空間を検出するステップと、離散点にスコアを付けるステップと、空間内における離散点について局所最大点を検出するステップと、を含むことを特徴とする請求項10に記載の方法。

請求項18

前記数値パラメータベクトルを算出するステップは、更に、局所最大点となる離散点を初期値として、局所的にパラメータを最適化するステップを含むことを特徴とする請求項17に記載の方法。

請求項19

局所的にパラメータを最適化するステップは、山登り法(hill-climbing)による探索シーケンスを実行するステップ、を含むことを特徴とする請求項18に記載の方法。

請求項20

局所的にパラメータを最適化するステップは、共役勾配法(conjugate gradient descent)を実行するステップ、を含むことを特徴とする請求項18に記載の方法。

請求項21

局所的にパラメータを最適化するステップは、準ニュートン法(quasi-Newton method)を実行するステップ、を含むことを特徴とする請求項18に記載の方法。

請求項22

前記数値パラメータベクトルを算出するステップと前記ドメインを算出するステップは、結合した最適化処理により実行されることを特徴とする請求項10に記載の方法。

請求項23

前記結合した最適化処理は、前記数値パラメータベクトルの最適化処理と前記ドメインの最適化処理が差し挟まれた結合最適化ループにて実行されることを特徴とする請求項22に記載の方法。

請求項24

前記ドメインを算出するステップは、初期ドメインを算出するステップと、前記初期ドメインと等しいドメインを設定するステップと、そのドメインに対してドメインに隣接する点をくり返し追加することによりドメインを成長させるステップと、ドメイン外部の点と隣接する点をドメインからくり返し取り除くことによりドメインを収縮させるステップと、を含むことを特徴とする請求項10に記載の方法。

請求項25

前記遮蔽面の3Dマップを見込み計算するステップは、前記対称型と前記数値パラメータベクトルにしたがってドメイン内の点を投影するステップ、を含むことを特徴とする請求項10に記載の方法。

請求項26

前記初期3Dマップから1以上の部分対称性を検出するステップは、候補となるドメインを特定するステップと、候補となるドメインの対称特性を決定するステップと、ドメインと対称特性をあわせて最適化するステップと、を含むことを特徴とする請求項9に記載の方法。

請求項27

候補となるドメインを特定するステップは、スケトナイゼーション(skeletonization)を含むことを特徴とする請求項26に記載の方法。

請求項28

候補となるドメインを特定するステップは、内部が大きく、物体の残り部分と隣接する点の数が少ない領域を検出するステップ、を含むことを特徴とする請求項26に記載の方法。

請求項29

候補ドメインを特定するステップは、部分エリア(part-like area)に適合する表面パッチ(surface patch)を算出するステップ、を含むことを特徴とする請求項26に記載の方法。

請求項30

前記初期3Dマップから1以上の対称性を特定するステップは、前記初期3Dマップ内にて初期位置を選択するステップを含み、その初期位置から対称性の検出を開始することを特徴とする請求項8に記載の方法。

請求項31

初期位置を選択するステップは、初期位置の格子を使うことを特徴とする請求項30に記載の方法。

請求項32

初期位置を選択するステップは、ハフ変換を使うことを特徴とする請求項30に記載の方法。

請求項33

初期位置を選択するステップは、初期3Dマップの形状特性解析するステップ、を含むことを特徴とする請求項30に記載の方法。

請求項34

形状特性を解析するステップは、回転対称特性の存在し得る位置を探すために視認可能面の面法線を解析するステップ、を含むことを特徴とする請求項33に記載の方法。

請求項35

初期位置を選択するステップは、初期3Dマップの垂直特性を検出するステップ、を含むことを特徴とする請求項30に記載の方法。

請求項36

初期位置を選択するステップは、局所的な形状特性を検出するステップ、を含むことを特徴とする請求項30に記載の方法。

請求項37

局所的な形状特性を検出するステップは、線を検出するステップ、を含むことを特徴とする請求項36に記載の方法。

請求項38

前記ドメインは、複合して連続する点集合の結合として表されることを特徴とする請求項10に記載の方法。

請求項39

前記ドメインは、陰関数によって表されることを特徴とする請求項10に記載の方法。

請求項40

前記陰関数は楕円体を定義することを特徴とする請求項39に記載の方法。

請求項41

前記ドメインは、動的輪郭(active contour)によって表されることを特徴とする請求項10に記載の方法。

請求項42

前記ドメインは、スプライン(spline)によって表されることを特徴とする請求項10に記載の方法。

請求項43

見込み計算される遮蔽面の3Dマップは1以上の見込み表面領域を含み、その見込みの確度が各見込み表面領域について計算されることを特徴とする請求項8に記載の方法。

請求項44

既知のビューポイントから観察された物体の視認可能面の初期3Dマップを取得し、前記初期3Dマップから1以上の対称性を特定し、特定された1以上の対称性と前記初期3Dマップから遮蔽面の3Dマップを見込み計算する計算装置、を備えることを特徴とする物体の遮蔽面の3Dマップを見込み計算するシステム。

請求項45

既知のビューポイントから観察された物体の視認可能面の初期3Dマップを取得するステップと、前記初期3Dマップから1以上の対称性を特定するステップと、特定された1以上の対称性と前記初期3Dマップから遮蔽面の3Dマップを見込み計算するステップと、を含む、物体の遮蔽面の3Dマップを見込み計算するプログラム命令、を格納するコンピュータにて読み取り可能な記録媒体

請求項46

物体を把持する部材を持つエンドエフェクタ(end-effector)で終端されたアームと、物体の視認可能面の初期3Dマップを取得する画像装置と、前記初期3Dマップから1以上の対称性を特定し、前記1以上の対称性と前記初期3Dマップから遮蔽面の3Dマップを見込み計算し、遮蔽面の見込み3Dマップに関し、把持のために1以上の前記部材の位置を決定することによりエンドエフェクタによる把持方法を算出する計算装置と、を備えることを特徴とするロボットシステム

技術分野

0001

本出願は、米国特許仮出願第60/529,386号(発明の名称:「遮蔽された部分の表面を対称性の算出により見込み復元するための技術」、2003年12月11日出願)に関連し、その優先権を主張する。関連出願の主題は、ここに引用により組み込まれる。

0002

この発明は、一般的には、機械認識技術に関連し、より詳しくは、観察対象物体の表面のうち視界から遮られている部分の3次元座標を見込み計算するための技術、に関する。

背景技術

0003

この発明は、物体を観察してその物体の表面の3次元(3D)マップ写像)を作成する技術に関連し、視界から隠されている物体表面の3Dマップを見込み作成する。物体の3Dモデリングは多くのアプリケーションに必要とされている。このようなアプリケーションとしては、CAD(Computer-Aided Design)、CAM(Computer-Aided Manufacturing)、電子商取引ロボット工学ディジタルエンターテインメントなどがある。通常、広く分散された複数の視点ビューポイント)から物体の画像や範囲データ(range data)を取得した上で、物体の3Dマップを形成する。これら複数のビューポイントは、取得された全ての画像の中に物体の全面が含まれるように設定される。このような複数のビューポイントから得られた情報が既知の技術によりつなぎ合わされることにより、物体の3Dモデルが形成される。

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

0004

しかし、複数ビューポイントからの物体観察が不可能だったり現実的でないアプリケーションもある。また、複数のビューポイントを使っても、やはり視界から遮蔽される面が生じることがある。たとえば、アームハンドを持つロボットシステム未知の物体を拾ったり包んだりする場合、しっかりと掴むためには物体表面に関する情報を充分考慮しなければならない。しかし、コスト的、物理的な各種制約条件視覚センサの数を制限するので、たった1つの視点からしか物体を観察できないこともある。このような状況では、視覚センサに面していない物体表面は物体自体により隠される。このような面のことを、「自己遮蔽されている」とよぶ。

0005

通常、ロボットエンドエフェクタ(end-effector)で物体を掴むには、向かい合った関係にある面が必要である。たとえば、平行顎型把持子で物体を掴むには、物体は平行に向かい合っている面を持たねばならない。複数の指を持つ機械の手は平行する面のない物体を掴むことができるが、それでもなんらかのかたちで向かい合っている面を必要とする。一つのビューポイントからの画像は、物体表面の一部に関する情報を提供するにすぎない。単一ビューポイントからの視認可能面だけでは接触するのに有用な面の情報を充分に得られないため、うまく物体を把持するのは難しい。物体のうまく把持するためには、自己遮蔽された部分の表面も見込み計算により取得できることが望ましい。

0006

また、物体は、他の物体により視界から遮蔽されるかもしれない。このような部分のことを「内部遮蔽されている」とよぶ。内部遮蔽には、自己遮蔽と同様の問題がある。遮蔽された部分を把持方法の決定に際して考慮できないので、実際に可能な把持方法が制限される。したがって、内部遮蔽された部分の表面も見込み計算により取得できることが望ましい。

0007

全ての面ではないが物体の複数の面を観察可能なアプリケーションもある。標準的な画像処理技術を用いて複数の視認可能面の画像を組み合わせることにより、部分的な表面モデルを取得する。このような部分表面モデルは、単一のビューポイントから得られたものよりも完全に近くなるが完全ではない。部分表面モデルを使って遮蔽された部分の表面を見込み計算により取得できることが望ましい。

0008

センサを追加することで表面を確からしく特定する必要がある、または、特定することが望ましいアプリケーションもある。たとえば、ロボットハンドの指には、力や、接触、接近を検出するセンサが装着されることもある。あるいは、把持対象の面を観察できるようにアームの端にカメラを取り付けてもよい。しかし、このようなセンサが追加されたとしても、センサから検出値を得られない段階で把持方法を高い確度で正しく決定できなくては効率的な操作を実現できない。

0009

したがって、さまざまな状況において、数に限りのあるビューポイントから得られた位置情報だけで、遮蔽された部分の表面を見込み計算により取得できることが望ましい。

0010

これまで、視認可能面の3Dモデルから遮蔽面の3Dモデルを生成する方法については考察されてこなかった。せいぜい、2D画像や3D画像から対称性を特定したり、2D画像から3D面をモデリングするための方法の研究に限られている。

0011

多くの科学技術論文は、2D画像の対称性を取り扱っている。たとえば、D.Shen,H.H.S.Ip,K.K.T.Cheung,E.K.Teohの「Symmetry Detection by Generalized Complex(GC) Moments:A Close-Form Solution(IEEE Trans.on Pattern Analysis and Machine Intelligence,Vol.21,No.5,May 1999)」は、2D画像における対称性の検出方法し、このトピックに関連する多くの先行文献に言及している。A.Blake,M.Taylor,A.Coxの別の論文「GraspingVisual Symmetry(International Conference on Computer Vision,pp 724-733,May 1993)」は、2Dの対称性と非対称性を使って平らな物体のへりを掴むという内容を開示している。

0012

2D画像から3D形状を復元する方法については、多くの文献に言及されている。T.Kanadeの論文「Recovery of the three-dimensional shape of an object from a single view(Artificial Intelligence,Volume 17,Issue 1-3,August 1981,pp409-460)」は、このようなトピックに関する比較的初期の論文である。H.Mitsumoto,S.Tamura,K.Okazaki,N.Kajimi,Y.Fukuiの論文「3-D Reconstruction Using Mirror Images Based on a Plane Symmetry Recovery Method(IEEE Trans.on Pattern Analysis and Machine Intelligence,Vol.14,No.9,September 1992,pp941,946)」は、物体の画像と、物理的な1枚以上の鏡に映った物体の画像の両方の2D画像を使って、物体の視認可能面を3Dにて復元するという内容について開示する。F.HanとS.C.Zhuの最近の論文「Bayesian inference of 3D scene from a single images(Proc.of Int'l Workshop on High-Level Knowledge in 3D Modeling and Motion,Nice France,2003)」は、2D画像の主要な見取り図を計算してもっともらしい遮蔽表面を推測している。H.Zabrodsky,D.Weinshallの論文「Using Bilateral Symmetry to Improve 3D Reconstruction from Image Sequences(Computer Vision and Image Understanding:CVIU,Vol.67,No.1,pp 48 to 57,1997)」は、2D画像から対称性を検出し、「structure from motion」として知られる技術における視覚的特徴の復元をその対称性によって改善する方法について開示する。D.Terzopoulos他の2つの論文「Symmetry-Seeking Models and 3D Object Reconstruction(International Journal of Computer Vision 1,pp 211-221,1987)」と「Constraints on Deformable Models:Recovering 3D Shape and Nonrigid Motion(Artificial Intelligence, 36(1988)pp 91-123)」は、手動により初期化した上で、2Dデータから汎用軸について対称性を有する物体を復元している。1988年の論文では、2Dデータの複数のセットにより複数のビューポイントから2Dの輪郭を取得している。

0013

2D画像に基づく技術において、3Dの復元のための対称性の利用は限定的である。2Dに映し出されたことで3Dの対称性がゆがめるからである。物体の3Dの対称性と観察されて映し出された2D画像との間の関係は複雑であり曖昧さが残る。したがって、2D画像に関する研究は、この発明によって解決された課題にすら言及していない。

0014

3Dデータにおける対称性というトピックに関する仕事は更に少ない。C.SunとJ.Sherrahの「3D Symmetry Detection Using the Extended Gaussian Image(IEEE Trans.on Pattern Analysis and Machine Intelligence,Vol.19,No.2,February 1997,pp164-169)」は、ガウス分布図の相関関係に問題を置き換えることにより、物体全体についての3D対称性を検出する方法を開示する。R.Zabrodsky,S.Peleg,D.Avnirの「Symmetry as a Continuous Feature(IEEE Trans.Pattern Analysis and Machine Intelligence,vol.17,no.12,pp.1,154-1,166,Dec.1995)」は、2Dおよび3D物体の対称性を数量化するための連続対称性測定について開示する。同論文は、この測定結果を3D対称性の向きを検出するために利用している。M.Kazhdanの「A Reflexive Symmetry Descriptor(Europian Conference on Computer Vision,2002,pp642-656)」は、物体の3Dボクセルモデルから物体全体についての鏡映対称性を検出する方法について論じている。しかし、これらの論文のいずれも3Dデータから遮蔽された3D表面を復元するときの問題点については言及していない。

0015

以上に鑑み、遮蔽された表面を3Dデータから予測して復元できるシステムや方法が必要である。

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

0016

本発明は、物体の遮蔽表面の3Dマップを見込みにより取得するシステムを提供する。本発明のある態様におけるシステムは、既知のビューポイントから観察された物体の視認可能面について初期3Dマップを取得し、その初期3Dマップから1以上の対称性を特定し、特定された1以上の対称性と初期3Dマップから遮蔽表面の3Dマップを見込み計算する計算装置を含む。本発明の別の態様におけるシステムは、画像装置と計算装置を含む。画像装置は、物体の視認可能面の初期3Dマップを取得する。計算装置は、初期3Dマップから1以上の対称性を特定し、特定された1以上の対称性と初期3Dマップから遮蔽表面の3Dマップを見込み計算する。本発明の更に別の態様におけるシステムは、既知のビューポイントから観察された物体の視認可能面について初期3Dマップを取得する手段と、初期3Dマップから1以上の対称性を特定する手段と、特定された1以上の対称性と初期3Dマップから遮蔽表面の3Dマップを見込み計算する手段とを含む。

0017

本発明はまた、物体の遮蔽表面の3Dマップを見込みにより決定する方法を提供する。この方法は、既知のビューポイントから観察された物体の視認可能面について初期3Dマップを取得するステップと、初期3Dマップから1以上の対称性を特定するステップと、特定された1以上の対称性と初期3Dマップから遮蔽表面の3Dマップを見込み計算するステップと、を含む。本発明はまた、上記方法の各ステップを実行するためのプログラム命令を含むコンピュータにて読み取り可能な記録媒体を提供する。

0018

本発明は、更に、ロボットシステムを提供する。このロボットシステムは、物体把持用部品を持つエンドエフェクタによって終端されるアームと、画像装置と計算装置を含む。画像装置は、物体の視認可能面から初期3Dマップを取得する。計算装置は、初期3Dマップから1以上の対称性を特定し、特定された1以上の対称性と初期3Dマップから遮蔽表面の3Dマップを見込み計算し、遮蔽表面の見込みの3Dマップに関連して1以上の把持用部品の位置を決定することによりエンドエフェクタによる把持方法を算出する。

発明を実施するための最良の形態

0019

概説すると、本発明は、物体の遮蔽された部分の3D表面を見込み計算するシステムに関する。このシステムは、(その全てでなくてもよいが)物体を観察しやすい地点から、物体の視認可能部分についての3Dの座標データ(3Dマップ)を取得する。このシステムは、視認可能部分の3D座標データに現れる対称性とその対称性が適用される領域(以下、「ドメイン」とよぶ)を特定する。そして、遮蔽された部分における3D表面を対称性とドメインを用いて見込み計算する。

0020

最適な実施例として、物体に内在する各対称性は、視認可能面のデータと遮蔽された部分の形状がその対称性と適合する度合いを判定するための関数によりスコア付けされる。遮蔽面の3D表現を見込み特定するための対称性は、対称特性とドメインのスコア付け関数最適値を空間内で探すことによって検出される。このシステムは、最もスコアが高くなる対称性に基づいて、遮蔽部分の3D表面を見込み計算する。

0021

視認可能面からは一義的な復元のための充分な情報を得られないので、視認可能面だけから遮蔽部分の表面を計算することは、本来、定義として不充分な問題である。たとえば、通常の箱として観察された物体は、3つの壁だけを持ちその後ろには何もない物体かもしれない。視認可能面がその後ろにあるものを隠していて、同じ物体でも、視線軸に沿って視認可能面の後ろにかなりの長さに伸びていると考えることもできる。実際、どちらの極端な場合もありうる。ワールド座標空間内の物体に関する従来の知見は、これらを多分に不確定な問題として扱っている。

0022

以下に開示される本発明のシステムは、ワールド座標空間内の物体に関する従来の知見を踏まえた上で、遮蔽された面の3Dマップを見込み計算する。特に、本システムは、多くの物体はさまざまなタイプの対称性を内包するという事実に依拠している。もし、物体がなんらかの対称性を内包するならば、視認可能面はその対称性と矛盾してはならない。更に、視認可能領域またはその一部がなんらかの対称性を示すなら、遮蔽された領域またはその一部もまた、通常、その対称性にしたがう。このように、物体の視認可能部分に対称性が存在すると、その対称性は遮蔽された部分にまでわたっている証拠であると考えられる。以下に開示される本発明は、視認可能な領域に存在する対称性から遮蔽された領域を推論するためにこのような証拠を利用している。

0023

本発明は、さまざまな種類の対称性を利用する。これらの対称性は、物体全体に対するものであってもよいし、物体の確認可能な一部分に対する局地的なものであってもよい。対称性が局地的であるときには、視認可能領域の一部にその対称性を適用し、その一部に対応する物体の遮蔽された面を予測する。

0024

簡単な例により、その概念を説明する。図1は、回転対称軸101をもつボトル100をある観察地点から見たときの図である。ボトル100の回転対称性ゆえに、視認可能面上の点は、ボトル100自体により自己遮蔽された面上に対応点を持つ。これらの対応点は、ほぼ完全にボトル100の表面を示すので、たとえば、ボトル100を把持するための処理が可能となる。

0025

図2は、天井面201と側面202、側面203が観察された箱200を示す。天井面201は四角形であり、鏡平面204と鏡平面205によって示される2つの直交する鏡平面について対称性をもつ。鏡平面204は、視認可能な側面202と整合する。鏡平面205は、他方の視認可能な側面203と整合する。箱200にはこれら2つの鏡映対称性が内在するので、2つの視認可能な側面202と側面203上の点は、ビューポイントから隠された2つの自己遮蔽面上に対応点を持つ。2つの側面である側面202と側面203は、箱200の天井面201と平行な鏡板206について共に鏡映対称である。この鏡映対称性により、箱200の天井面201上の点は底面上に対応点を持つ。したがって、3次元空間における3つの視認可能面として天井面201、側面202、側面203をマッピングして特定した後、視認可能面である天井面201、側面202、側面203から鏡平面204、鏡平面205、鏡平面206を特定することにより、対称的な位置にある遮蔽された面を構築する上で充分な情報を得られる。

0026

人工の、または、自然の物体はさまざまな対称性を内包することが多いがゆえに、実世界の多くの応用場面において遮蔽された面を復元する上で本発明による予測方法は非常に有効であり、見えざるものの単なる予測ではないことは評価されるべき点である。ロボットによる把持のように実世界の多くの応用場面においては、遮蔽された面の完全な情報は必要ではなく、それなりに近似性の高い予測をできれば充分である。

0027

図3は、より複雑な例として、円筒状のハンドル301を持つフライパン300をある観察地点から見た図である。フライパン300は、ハンドル301とフライパン300の中央を横切る垂直面について鏡映対称性303を持つ。鏡映対称性303によると、ハンドル301の大部分を復元できる。また、2つの局所的な回転対称軸302と304がある。両方とも、表面の一部、すなわち、ハンドル301と、ハンドルなしのフライパン部分にだけ適用されるという意味で「局所的」である。ハンドルが鏡映対称性と回転軸対称性のいずれからも復元可能であることは留意すべき点である。回転軸対称性によるハンドルの復元はほぼいつでも完全であるが、鏡映対称性を使った復元は、通常、完全とはならない(鏡平面の一方の側におけるハンドルのすべてが視認可能となる角度から観察しないかぎり)。そこで、対称性のタイプ(対称型)にランク付けを行い、複数種類の対称性を適用できるときには最高ランクの対称性により復元を行う。

0028

本発明をわかりやすく説明するために、便宜上好ましい実施例(以下、「最適実施例」)としての典型的な実施例について詳細に述べた後、別の実施例についても述べる。
[最適実施例]

0029

図4は、本実施例に関連して、物体の視認可能面の3Dマップを取得する画像装置400の概要図である。画像装置400は3つの異なる観察点から画像を取得するために3つのカメラ401を含む。パターン光投影するプロジェクタ402は、カメラ401により観察されるべき物体の表面に構造化された人工テクスチャを施す。計算装置403はカメラ401から画像を取得し、以下に述べる本発明の各計算処理を実行する。

0030

図5は、本実施例に関連する処理のうち、主要な処理過程を示すフローチャートである。最初のステップ501では、物体の視認可能な領域についての3Dマップを取得する。ステップ502では、その3Dマップから対称性を特定する。ステップ503では、特定された対称性により、遮蔽された部分の表面を見込み計算する。

0031

最初のステップ501では、1以上の撮像画像を集めて、各画像に適切な3D表面復元処理を施すことにより3Dマップを取得する。このような3Dの復元処理についてはよく知られており、通常、各画像中における対応点を特定し、画像中における対応点の位置と図4のカメラ401の配置に基づいて三角測量を行うことにより3Dマップを算出する。図4に示すプロジェクタ402などから投影パターンによってテクスチャを施すことにより、このような処理を補助することも多く、一般的には、「アクティブ照明によるデンスステレオ視(dense stereo with active illumination)」として知られている。このようなシステムの例としては米国特許出願第10/703,831号(2003年11月7日出願)に詳しく開示されており、関連出願の主題は、ここに引用により組み込まれる。

0032

3次元空間内に位置する点の集まりは、通常、「ポイントクラウド(点の)」とか「ポイントセット(点の集合)」とよばれる。単一の物体に属する全ての点が、その物体のポイントクラウドとなる。これは、オブジェクトセグメンテーション(object segmentation)とよばれる。範囲データを分割する方法は既知である。画像装置の観察地点(ビューポイント)から視認可能面により遮蔽されている領域は、通常、「遮蔽領域」とよばれる。

0033

次に、ステップ502では、視認可能領域の3Dマップに内在する対称性を検出する。一般的には、物体全体に対して適用される全体的な対称性もあれば、物体の一部だけに適用される局所的な対称性もある。対称性を定義するには、ポイントクラウドのうち、対称性の特徴(対称特性)が現れる部分をあきらかにする必要がある。本実施例では、これを「部分対称性」という概念で表現する。部分対称性は、その対称性が現れる表面部分と共に対称性を定義するデータ構造である。本発明における対称性の利用法を理解しやすくするために、まず、部分対称性を概説し、候補となる部分対称性を評価する方法について述べる。そのあと、部分対称性の検出方法について述べ、ステップ503に関連して、部分対称性を表面の見込み計算に利用する方法について述べる。続いて、見本としての処理過程を示す擬似コードにより本発明を説明する。
<部分対称性の定義>

0034

部分対称性は、3つの要素により定義される。対称型、数値パラメータベクトルブーリアン型のドメイン関数である。対称型は、許容可能な型の小集合の中から選択される。許容可能な型とは、鏡平面や回転軸のように、一般的な物体から見いだされる典型的な対称性を特徴づけるものである。数値パラメータベクトルは、視認可能表面の3Dマップにおける鏡平面の向きや位置のように、対称性要素の位置を示す。以下においては、対称性型と数値パラメータベクトルをまとめていうときには「対称特性」とよぶ。ドメイン関数は、視認可能面のうち対称特性と整合する部分領域を特定する。
<対称型>

0035

対称型は、3D物体の表面と整合する特定の型を示す。対称的な物体の簡単な例は球体であり、球体は点に対して回転的に対称である。球体に見いだされる対称型は回転点対称である。円筒は軸に対して回転的に対称であるが、その軸に直交するように選ばれた平面に対しては鏡映対称である。つまり、円筒には、回転軸と鏡平面について2つの対称型が該当する。より複雑な形状はより多くの対称型に該当する。たとえば、立方体は3枚の直交する鏡平面のそれぞれについて鏡映対称である。

0036

対称性型は一般的には、要素的なファミリーと合成的なファミリーの2つに分類できる。要素的な対称型は、平面、線、点という3つの幾何形状のいずれかにより定義される。合成的な対称型は、2以上の要素的な対称性の組み合わせとなる。

0037

要素的な対称型のひとつは鏡映面対称である。鏡映対称とは対称平面とよばれる平面についての対称性である。物体表面上の点Aは、鏡平面の反対側に表面点A’を持つ。AとA’を結ぶ線は鏡平面と直交し、鏡平面と交わり、その交点はAとA’を結ぶ線を2等分する。

0038

別の要素的な対称型である鏡映軸対称は、対称軸とよばれる軸により定義される。物体表面上の点Aは、鏡映軸の反対側の表面点A’を持つ。AとA’を結ぶ線は鏡映軸に直交し、鏡映軸と交わり、その交点はAとA’を結ぶ線を2等分する。

0039

更に別の要素的な対称型である回転軸対称も軸により定義されるが、ここでいう軸とは回転軸である。点Aは、物体表面上において円を形成する連続点に対応する。この円には点Aも含まれる。この円は回転軸に対して直交する平面上に位置し、その半径は点Aから回転軸までの距離である。

0040

更に別の要素的な対称型は鏡映点対称である。鏡映点対称は対称点とよばれる点により定義される。物体表面上の点Aは、対称点の反対側に表面点A’を持つ。点Aと点A’を結ぶ線は対称点と交わる。対称点は、AとA’を結ぶ線分を2等分する。

0041

更に別の要素的な対称型は回転点対称である。回転点対称も対称点により定義される。物体表面上の点Aは、点Aを含む球体上において連続する点と対応する。球体上の各点と対称点までの距離は等しく、球体の半径は点Aから対称点までの距離である。

0042

合成的な対称型は、複数の要素的な対称型から形成される。たとえば、2重鏡平面は、2枚の直交する鏡平面から構成される。点Aは、2つの鏡映面対称のうちの一つ、または、2つの鏡映面対称を順次適用することにより点A’と対応づけられる。別の例は、3重鏡平面である。3重鏡平面は、3枚の直交する鏡平面から構成される。物体表面上の点Aは、3枚の鏡平面うちのいくつか、または、全てを順次適用することにより点A’と対応づけられる。

0043

更に別の例は、鏡平面と直交する回転軸対称である。この対称性は回転軸とその回転軸と直交する鏡平面により定義される。物体表面上の点Aは、表面点による2つの円と対応づけられる。円の1つは回転軸により定義され、もう一つは、回転軸を点A’に適用することによって定義される。点A’は点Aに対して鏡映対称な点である。
<数値パラメータベクトル>

0044

各部分対称性は、対称型に応じた数値パラメータベクトルにより特徴づけられる。鏡映面対称の場合、パラメータベクトルは鏡平面の位置と方向を示す。同様に、軸対称のパラメータベクトルは対称軸の位置と方向を示す。点対称のパラメータベクトルは、対称点の位置を示す。合成的な対称型の場合、パラメータベクトルに追加される要素は、追加された対称性要素の位置を示す。
<部分対称性のドメイン>

0045

各部分対称性は、視認可能面のうちその部分対称性が成立している部分を定義するドメイン関数によって特徴づけられる。ドメイン関数は、視認可能面上の点が部分対称性に服するか判定し、視認可能面上の点をTRUEかFALSEのいずれかにマップする論理属性となる。ここでいうドメインとは、TRUEにマップされた点の集合である。ドメインは、単一の連続した面をもつ領域となることもある。

0046

物体のポイントクラウド全体に当てはまる部分対称性であれば、ドメインは視認可能面の全ての点を含む。全体にあてはまる対称性でなければ、ドメイン関数は部分対称性を物体表面の部分領域に限定できる。物体がさまざまな対称特性をもつ複数種類の幾何形状からなるときにはこのような対策が重要となる。単一の全体的な対称性で物体を描くことは、通常不可能である。そのかわりに、それぞれが特有の対称特性やドメインを持つ複数の局所的な部分対称性を見つけだす。

0047

一般的に、部分対称性のドメインは、その対称特性による対応点を持つ点を含み、対応点は持たないけれどもその対称特性と不整合とはならない点も持つことができる。対称特性により遮蔽空間内にマップされる点は対応点を持たないが、そのような点は対称特性と不整合となる点ではなく、ドメイン内に含まれてもよい。
<部分対称性のスコア付け>

0048

図5に戻ると、3Dマップ内の対称性を特定するステップ502では、候補として内在する部分対称性にスコアをつける。仮定された対称性が許容可能かどうかを決定するためにスコアが必要となる。よりふさわしい対称性を選ぶためのランク付けを行えるようにして対称性の候補を比較できることも必要である。「対称性スコア」を計算することによってこのようなランキングが可能となる。対称性スコアは部分対称性をランキング付けし、受け入れるか拒否するかして、2以上の対称性の中から選択するために利用される。

0049

対称型S、関連する数値パラメータベクトルx、ドメインdomから成るにより示される各部分対称性は、3通りの方法でスコア付けされ、それぞれscore1、score2、score3という3つの数値スコアが算出される。第1のスコアscore1は、対称特性をドメインdom内の各点に適用することにより算出される。この結果として、ドメインの表面点は、「投影点」とよばれる1以上の新しい点にマップされる。たとえば、鏡映面対称を適用する場合、点Aは鏡平面の反対側の単一の投影点A’にマップされる。

0050

回転軸対称を適用するときには、点Aは円状に連なる投影点の集合にマップされる。本実施例は、有限個数の点をサンプリングすることにより、単一の点から無限個数の点に写像できる対称性もあるという事実となじむ。回転対称により全ての点を生成するのではなく、結果として得られるべき円や球体上の点を等間隔で抽出することにより、有限個数で等間隔に分散する点を生成してもよい。

0051

こうした投影点は、互いに排他的な3つのカテゴリのいずれかに分類される。物体の視認可能面のすぐ近くにある投影点は、「一致(match)」に分類される。遮蔽された部分やカメラから観察された領域の外に位置する投影点は、「遮蔽(occluded)」に分類される。遮蔽された部分の形状は、画像装置のビューポイントと物体のポイントクラウドの組み合わせから、既知の技術によって計算される。画像装置のビューポイントは、1以上のカメラの位置と向きにより決定される。投影点が「一致」でも「遮蔽」でもないときには、「不明(unexplained)」に分類される。もし、部分対称性が視認可能面と完全に整合するなら、各点は「一致」または「遮蔽」のいずれかに分類され「不明」に分類されることはない。したがって、「一致」または「隠蔽」に分類される点が多いほど、その部分対称性は物体の部分の対称性として確からしいことになる。

0052

score1=(cmatchnmatch+coccludednoccluded+cunexplainednunexplained)/n
によりscore1を算出する。ここで、nmatch、noccluded、nunexplainedは、それぞれ「一致」、「遮蔽」、「不明」のいずれかに分類された点の数である。
n=nmatch+noccluded+nunexplained
である。ここで、cmatchは正の定数、coccludedはcmatchより小さい非負の定数、cunexplainedは負の定数である。このスコア関数示唆するところは、「一致」点は対称性の存在を強く証拠づけ、「遮蔽」点は対称性の存在を弱く証拠づけることである。「不明」の点は対称性をうたがわしめる強い証拠となる。score1が閾値を超える部分対称性のみが、受け入れ可能となりうる。

0053

score1の計算はサブ・サンプリング(sub-sampling)により実行されてもよい。特に、部分対称性のドメインや視認可能点の完全集合から固定個数の代表点を取り出し、これらの代表点に基づいて判定処理を実行してもよい。更に、対称特性の適用にあたっては、新たな連続点集合を生じさせる対称性に対し、それらの連続点集合のうちの代表的な点集合をその対称性に服させてもよい。これらのケースのいずれにおいても、サンプリングされる点の数は、アルゴリズム計算を効率的に行うため控えめに設定される。

0054

残る2つのスコアであるscore2とscore3はドメインの属性に関連する。score2は、ドメイン内に包み込まれている点の総数、または、ドメインの点集合による閉空間の表面積によってドメインの大きさを示す。部分対称性が許容可能に内在するとされるためには、score2が所与の閾値を超えなければならない。

0055

score3はドメインの「境界(margin)」を特徴づける。ドメインの一部であり、かつ、1)ドメイン外部の点と隣接するか2)視認可能面の3Dマップにおける自然な境界面、たとえば、原画像においてポイントクラウドの深さが不連続となる位置と隣接する点がドメインの境界点である。ドメインの境界を含めた点の総数は、数量Rにより表される。ドメイン外部の点と隣接する境界点の総数は数量r1によって表される。ドメイン外部の点と隣接しない境界点の総数は数量r2によって表される。これら2つは、すべての境界点を相互排他的な2つのクラスに分類する。たとえば、ドメインが望ましいものであるためには、r1/(r1+r2)が閾値より小さくなければならない。この条件により、自然な境界面に隣接する点によってその境界が明確化されるドメインが選択されやすくなる。ゆえに、
score3=r1/(r1+r2)
と計算する。

0056

score2とscore3を閾値と比較することは、過度に小さい、あるいは、形のよくないドメイン、たとえば、より大きな表面内に細い帯のように延びるドメインを取り除く上で効率的である。既に述べたように、score3は自然な境界面と隣接する点によっては明確化されにくいドメインを排除する。閾値が、自然な境界面に接しなければならない境界点集合の大きさを規定する。

0057

本実施例におけるスコア付けを、図6に示す簡単な幾何形状を例として説明する。図6は、天井面601、側面602および側面603の3つの視認可能面を持つ箱を示す。図6は、また、天井面と1つの側面を横切る鏡平面604を示している。鏡映対称において、天井面601の点605は、鏡平面604の反対側の天井面601上に投影される。この投影点は「一致」に分類されるので、点605の投影点は正の重み付け係数であるcmatchゆえに、score1に貢献する。

0058

鏡映対称なので、側面603上の点606は、視認可能面によって遮蔽されている図示しない点に投影される。そのため、点606の投影点は「遮蔽」に分類され、非負の重み付け係数であるcoccludedゆえにscore1に貢献する。点605の投影点が「一致」に分類されるので、点605だけからなる単一点のドメインは対称性の存在の肯定的な証拠となる。点606からなる単一点のドメインは対称性の存在の肯定的な証拠とはならないが、対称性に対して不整合とはならない。

0059

ある部分対称性について計算されたドメインは、部分対称性の肯定的証拠となる点群と、肯定的証拠とはならないがその部分対称性に対して不整合となるものではない点群を含み得ることは留意すべきである。より詳しくはステップ503に関連して後述するが、復元処理において、対称特性は該当ドメインのすべての点に適用される。このとき、部分対称性の存在を証拠づけるものとはならないが部分対称性と不整合とまではならない点は、遮蔽された空間に投影され、もっともらしい遮蔽面を形成する。図6に示すように、側面603上の視認可能点は、鏡平面604の反対側に投影され、もっともらしい遮蔽面607を形成する。
<部分対称性の検出>

0060

部分対称性は、部分対称性の候補が見いだされる全ての空間を調査し、各候補を一連許容判定に供することによって特定できる。もし、複数の部分対称性の候補が検出されたときには、以下に示す階層的な順番にしたがってもっともふさわしいものを選択する。許容可能な部分対称性は、score1、score2、score3の3つのスコアそれぞれについて閾値判定パスする必要がある。
<対称特性検査に供される対称型>

0061

対称特性の検出は、ある対称特性は別の対称特性を併発するという事実を利用することによりいっそう効率的に行うことができる。回転点対称をもつ物体または物体の一部は、無限に多くの回転軸対称を持ち、これら各軸は回転点対称における対称点と交わる。別の例として、回転軸対称は無限に多くの鏡映面対称を持ち、これら各鏡平面は回転軸において交わる。更に、2重鏡映面対称は2つの鏡映面対称を持ち、3重鏡映面対称は3つの鏡映面対称を持つ。

0062

したがって、さまざまな対称型を順番に探していくことにする。まず、鏡映面対称があるか探す。鏡平面が特定されると、鏡平面とそろう全ての回転軸を探す。回転軸の検索アルゴリズムを効率的にするために、検索対象となる空間を狭めてもよい。回転軸対称が検出されると、回転点対称を探す。回転点対称が見つからなければ、鏡平面と直交する回転軸対称を探す。回転軸対称がなければ、複数鏡映面対称を探す。考慮すべき対称型の集合において部分的な順番をつけて検索を実行する。この部分的な順番において、ルートノードとなるのは鏡映面対称型である。

0063

さなざまな対称性により別の対称性も生じるので、複数の対称性が検出されることはよくあることである。もっとも望ましい対称性とは、所与の視認可能点に対して最も多くの投影点が現れる対称性である。たとえば、鏡平面は、対称型が適用されるドメイン内の点に対して1つの投影点を持つ。2重鏡平面であれば、ドメイン内の点に対し2つの投影点を持つ。一方、回転軸対称では円状に点が並び、これらの点は無限個数の1次元点集合を形成する。回転点対称は2次元点集合を形成する。このように、各種対称型は次に順に好ましい。1)回転点対称。2)鏡平面と直交する回転軸対称。3)回転軸対称。4)3重鏡映面対称。5)2重鏡映面対称。6)鏡映点対称。7)鏡映軸対称。8)鏡映面対称。である。
<対称性パラメータ空間の検査>

0064

すべての対称型にとって、その対称性が上記基準からみて許容可能か判定するには、複数次元において連続するパラメータ空間が必要である。この検出処理は2つのステップに分けて実行される。

0065

第1のステップでは、全ての数値パラメータベクトルの空間上で等間隔格子上に離散する点の集合において、パラメータ空間をサーチする。この離散的な格子についての検出結果は、格子上の各点ごとのスコアとなる。ここから、局所最大点群を特定する。局所最大点群は、格子上で直接的に隣接する点のスコアよりも大きなスコアをもつ点の集合である。

0066

第2のステップでは、対称性のスコアを改善するために局所的なパラメータの最適化を実行する。この最適化は、格子の細かさ以下のスケールでのパラメータの修正も含む。この最適化は山登り探索(hill-climbing search)によって実行してもよい。結果は、対称性のスコアを局所的に最適化する数値パラメータベクトルである。

0067

局所的なパラメータを最適化する処理に、対称性が適用されるドメイン空間を探索する処理を差し挟んだ結合最適化ループとしてもよい。この結合最適化ループの処理結果は、局所的に最適化された対称性のスコアを持つ部分対称性となる。
<対称性ドメイン空間の探索>

0068

ドメイン探索の好適な方法は以下の通りである。まず、視認可能面上の全ての点を2つに分ける。(1)対称特性による投影点が「一致」または「遮蔽」に分類される点と(2)「不明」に分類される点である。対称特性によりその投影点が「一致」または「遮蔽」に分類される点の集合としてのポイントクラウドにおいて、最も大きくつながっている部分が初期ドメインとなる。

0069

初期ドメインは、所定の成長限界に至るまで、ドメインに隣接する点をくり返し加えることで大きくなる。この処理により、「不明」の点やそういった点の孤島のような集合は、ドメインに飲み込まれる。これらの島は初期ドメインの周囲に存在しうる。所定の成長限界より小さいなら、こういった島は完全にドメインに取り込まれる。最後に、ドメイン外部の点と隣接する点をドメインの境界からくり返し取り除くことにより、ドメインを収縮させる。この処理によるドメインの収縮限界は、成長限界と同じであってもよい。ドメインの収縮によって、より多くの「不明」な点が再びドメインから取り除かれる。最終的な結果として得られるドメインは、視認可能面の3Dマップにおいて単一で連続する部分からなる。ドメインをスコア付けして、そのスコアが上記したような適切な閾値を超えたか判定することにより、その境界が視認可能面の3Dマップにおける1以上の自然な境界面によって十分に定義され、充分な大きさのドメインであることが判明する。
<部分対称性の検出>

0070

唯一最良の部分対称性を見つけるためには、すべての対称型を考慮した方がよい。各対称型について、固定的な格子を利用して数値パラメータベクトル空間を抽出し、局所最大点群を検出する。各局所最大点群について、最適な部分対称性を局所的に検出し、数値パラメータベクトルとドメインについて結合最適化処理を実行する。上記したように、部分対称性はスコア付けされる。score1、score2およびscore3のそれぞれが許容可能な閾値から外れる部分対称性は、許容不能として拒絶されるが許容可能な部分対称性は残される。これらの許容可能な部分対称性の中から、もっとも高いランクの部分対称型となる部分対称性が選ばれる。
<全ての部分対称性の検出>

0071

部分対称性の検出は、許容可能な部分対称性をそれ以上検出できなくなるまでくり返される。このくり返しの各ステップにおいて、考慮対象の全表面点の集合から、既に特定された部分対称性が適用されるドメインに含まれる表面点を全て取り除いてもよい。こうして縮小された点集合を使って最も許容可能な部分対称性の検索をくり返す。新しく特定される部分対称性により残る表面点の数が少なくなるので、このくり返し検索は最終的に収束する。
<ポイントクラウドの拡大形成>

0072

残るステップ503では、遮蔽面を見込み計算する。特定された各部分特性についての対称型がドメイン内の各点に適用される。結果として得られる投影点は、もっともらしい遮蔽面を示すポイントクラウドによる拡大された平面を形成する。「一致」か「遮蔽」のどちらかに分類されると、その点はドメイン内に位置するかもしれないと述べた。回転対称型の場合、「一致」に分類される投影点は対称軸や対称点について何回も複製される。したがて、回転対称型は復元にとって非常に有用である。鏡映対称型の場合、「一致」に分類される投影点は復元にとって有用性ではないが、「遮蔽」に分類される投影点は復元にとって有用性である。
[本実施例の擬似コード]

0073

物体の視認可能な領域についての3Dマップを取得するのに適した方法は、米国特許出願10/703,831に開示されている。本実施例における残りのステップを、次に示す処理によって示す。各処理については後に詳述する。
・compute_occluded_surfaces(遮蔽面の計算)
・find_all_part_symmetries(全ての部分対称性の検出)
・find_a_part_symmetry(部分対称性の検出)
・global_parameter_search(グローバルなパラメータ検索)
・score_symmetry(対称性のスコア付け)
・score_domain(ドメインのスコア付け)
・apply_symmetry(対称性の適用)
・search_domain(ドメインの検索)
・local_parameter_optimization(ローカルパラメータの最適化)
・symmetry_acceptance_test(対称性の許容判定)
・repartition_domains(ドメインの再分割)

0074

図7は、本実施例における呼び出し構造を示し、処理Aから処理Bへの矢印は、処理Aが処理Bを呼び出すことを示す。同図に示す各処理を、疑似コードによって以下に説明する。この疑似コードは、重要なステップだけを示している。説明をわかりやすくするためもっとも重要なステップについて説明し、付随的な詳細については割愛する。実装が簡単な低レベルの処理についても説明を割愛している。

0075

これらの処理の中にはグローバルなパラメータを使うものもある。たとえば、(global_parameter_searchで使われる)grid Gは、10度刻みの回転パラメータと物体の直径の5%刻みの変換パラメータのセットである。(search_domainで使われる)margin kは、30ポイントに設定される。(score_symmetryで使われる)cmatch,coccluded,cunexplainedという重み付けのパラメータの値は、1、0、−15である。加えて、(symmetry_acceptance_testで使われる)閾値θ、Ψ、φの値は、それぞれ0、200ポイントおよび0.5である。本発明の処理にとって、これらのパラメータが特定の値であることはさほど重要ではない。上記したような典型的な値の代わりに、処理結果を見ながら適切な範囲で設定すればよい。

0076

margin kのように、これらの値の中には画像システムに依存するものもある。また、これらのパラメータの値の中にはアプリケーションによって決定されるものもある。たとえば、symmetry_acceptance_testの処理では、なによりも、score1がθより大きくなることが必要である。対称性を緩い基準で許容するアプリケーションではθは比較的小さな値となる。反対に、許容判定に厳密な基準を課すアプリケーションであれば、θは比較的大きな値となる。他のグローバルパラメータについても同様である。これらの値は、アプリケーションの要求に合うように設定されればよい。

0077

compute_occluded_surfacesはメインとなる処理である。もともとの表面点集合Pが入力として与えられると、この処理は見込み遮蔽面も示す拡大された表面点集合P'を算出する。擬似コードにより典型的なcompute_occluded_surfacesを示すと、以下の通りである。
compute_occluded_sufaces(P)
begin
P'=Pに初期化
Y=find_all_part_symmetries(P)
for Yに属する各部分対称性について
Q=apply_symmetry(dom,S,x)
P'にQを追加
end for
return P'
end

0078

find_all_part_symmetriesは、視認可能面の3Dマップから部分対称性を見つけ出し、その部分対称性についてのドメインに属する点を取り除いていくという処理を部分対称性が見つからなくなるまでくり返す。入力値となるのは元々の表面点集合Pである。出力値となるのは(見つかった)部分対称性の集合Y={}である。擬似コードでは、バックスラッシュ文字(\)で集合の減算を示している。典型的なfind_all_part_symmetriesは、以下の通りである。
find_all_part_symmetries(P)
begin
点集合Q=Pに初期化
部分対称性集合Y=空集合(φ)に初期化
repeat
=find_a_part_symmetry(P,Q)
if success
Q=Q\dom(Qからdomを除く)
Y=Y+(見つかった部分対称性をYに追加)
Y=repartition_domains(P,Y)
end if
until not(success)
return Y
end

0079

find_a_part_symmetryは、各対称型について数値パラメータの局所最大点群を見つけ出すために固定格子上を探索する。抽出された各局所最大点について、ドメインの最適化と数値パラメータベクトルの最適化を含む結合最適化ループが実行される。最後に、結果として得られた部分対称性が受け入れ可能か判定するためにスコア付けを行う。複数の部分対称性が検出されたときには、もっとも高いランクがつけられた型の部分対称性を選ぶ。入力は元々の表面点集合Pと(調査対象となる)部分点集合Qである。出力は、ブーリアン型変数のsuccess、対称型Sbest、パラメータベクトルxbest、ドメインdombestである。以下の擬似コードでは、典型的なfind_a_part_symmetryを示す。もっとも重要なポイントを明快に示すために、この擬似コードは、ある対称型が検出されるときには別の対称型も検出されるという事実に基づく効率性を考慮していない。こういったテクニックについては、<部分対称性の検出>として先述した通りである。
find_a_part_symmetry(P,Q)
begin
Sbest=xbest=0に初期化
dombest=空に初期化
success=FALSEに初期化
for 全ての対称型Sについて
X=global_parameter_search(P,Q,S)
for Xに属する全てのパラメータベクトルxについて
repeat
dom=search_domain(P,Q,S,x)
x=local_parameter_optimization(P,dom,S,x)
until convergence(収束するまで)
if symmetry_acceptance_test(P,S,x,dom) and S>Sbest
Sbest=S
xbest=x
dombest=dom
success=TRUE
end if
end for
end for
return success,Sbest,xbest,dombest
end

0080

global_parameter_searchは、もともとの表面点集合Pと試験点集合Qおよび対称型Sを入力として受け取る。この関数は、パラメータgrid Gを使う。出力は許容可能な対称性についてのパラメータ集合Xである。この格子は、数値的な対称性のパラメータ空間がどのように抽出されるかべきを示す。格子上の点ごとに、部分対称性がスコア付けされる。スコア付けされた格子から局所最大点群が検出される。擬似コードによるglobal_parameter_searchの処理内容は以下の通りである。
global_parameter_search(P,Q,S)
begin
for grid Gにおいて各パラメータベクトルxについて
score(x)=score_symmetry(P,Q,S,x)
end for
X=パラメータベクトルxの集合
(ただし、xのscore(x)はgrid Gにおいて局所的に最適化されている)
return X
end

0081

score_symmetryは、対称特性を試験点集合Qに適用し、結果として得られる各点がどこにあるかをチェックする。ここでいうスコアとは、3つの項を線形結合したものである。すなわち、(1)もともとの視認可能点のうちのいずれかの近くにある点の数、(2)遮蔽された空間内に位置される点の数、(3)他の点の数、である。入力は表面点集合P、試験点集合Q、対称性型Sおよび対称性パラメータxである。この関数は、cmatch,coccluded,cunexplainedの重み付けパラメータも使用する。この関数は、score1を返す。典型的なscore_symmetry関数の擬似コードは以下の通りである。
score_symmetry(P,Q,S,x)
begin
Q'=apply_symmetry(Q,S,x)
nmatch=noccluded=nunexplained=0に初期化
for Q'の各点pについて
if pがP内の1以上の点のすぐ近くにある→nmatchをインクリメント
else if pが遮蔽空間にある→noccludedをインクリメント
else nunexplainedをインクリメント
end for
n=nmatch+noccluded+nunexplained(全点数計数
score1=(cmatchnmatch+coccludednoccluded+cunexplainednunexplained)/n
return score1
end

0082

score_domain関数は、対称ドメインのサイズを計算し、対称性が適用されるドメインの境界の「質」を特徴づける。入力は表面点集合Pと対称性が適用されるドメインdomである。出力はscore2とscore3の2つのスコアである。典型的なscore_domain関数の擬似コードは以下の通りである。
score_domain(P,dom)
begin
score2=|dom|
r1=0,r2=0に初期化
for ドメインdomの境界に位置する全ての点qについて
if domに属さないがqに隣接する点pがPにある→r1をインクリメント
else r2をインクリメント
end if
end for
score3 = r1/(r1+r2)
return score2,score3
end

0083

apply_symmetryは、点集合Qの各点を対称型Sにしたがってその対称位置に投影することによって、対称特性を点集合Qに適用する。入力は点集合Q、対称型Sおよび対称パラメータxである。出力は、拡大された点集合Q'である。典型的なapply_symmetryの擬似コードは以下の通りである。
apply_symmetry(Q,S,x)
begin
switch symmetry type S
case鏡映面対称
パラメータxにより定義される平面を通してQを投影し、Q'を計算
case 鏡映軸対称
パラメータxにより定義される軸を通してQを投影し、Q'を計算
case回転軸対称
パラメータxにより定義される軸の周りにQを投影し、Q'を計算
case 鏡映点対称
パラメータxにより定義される点を通してQを投影し、Q'を計算
case回転点対称
パラメータxにより定義される点の周りにQを投影し、Q'を計算
case 2重鏡映面対称
パラメータxにより定義される全てに平面を通してQを投影し、Q'を計算
case 3重鏡平面対称
パラメータxにより定義される全てに平面を通してQを投影し、Q'を計算
case 平面に直交する回転軸対称
パラメータxにより定義される平面を通してQを投影し、
パラメータxにより定義される軸の周りに投影点とQを投影し、Q'を計算
end switch
return Q'
end

0084

search_domainは、対称特性のドメインを計算する。まず、この対称特性と整合する点集合のうち最も大きくつながっている部分を算出する。そして、この集合に境界上の点を追加する。入力は表面点集合P、部分点集合Q、対称型Sおよび対称パラメータxである。処理に際してはパラメータmargin kを使う。出力はドメインdomである。典型的なsearch_domainの擬似コードは以下の通りである。
search_domain(P,Q,S,x)
begin
Dを空集合に初期化
for Qの各点qについて
point_score=score_symmetry(P,{q},S,x)
if point_score > 0
Dに{q}を追加
end if
end for
dom=Dのうち最も大きくつながっている部分
for i=1 to k
Dk=domの点と隣接する(P\dom)内の点集合
domにDkを追加
end for
for i=1 to k
Dk=(P\dom)の点と隣接するdom内の点集合
dom=dom\Dk
end for
return dom
end

0085

local_parameter_optimization関数は、数値対称パラメータ空間における局所的な検索を行う。この検索は、山登り法(hill-climbing)によって実行される。入力は、元々の表面点集合P、部分点集合Q、対称型S、対称パラメータxである。この処理は、パラメータgrid Gを使う。出力は改善された対称パラメータx'である。local_parameter_optimizationの擬似コードは以下の通りである。
local_parameter_optimization(P,Q,S,x)
begin
x'=xに初期化
score'=score_symmetry(P,Q,S,x')
repeat until convergence(収束するまでくり返す)
x0=xに設定
パラメータxをずらす。
score=score_symmetry(P,Q,S,x)
if score > score'
score'=scoreに設定
x'=xに設定
else
x=x0
end if
end repeat
return x'
end

0086

symmetry_acceptance_testは、設定された閾値についての基準をクリアできない部分集合を排除することにより部分集合をふるい分ける。許容可能な部分集合は、対称性に関する高いスコア、大きなドメインのサイズ、ドメイン外部の点と隣接する点の数が少ない境界をもつ。入力は表面点集合P、対称型S、対称パラメータx、ドメインdomである。処理に際しては、閾値を示すパラメータθ、Ψ、φを用いる。出力はブーリアン型のacceptである。symmetry_acceptance_testの擬似コードは以下の通りである。
symmetry_acceptance_test(P,S,x,dom)
begin
score1=score_symmetry(P,dom,S,x)
=score_domain(P,dom)
accept=(score1>θ)かつ(score2>Ψ)かつ(score3<φ)
return accept
end

0087

repartition_domainsは、各部分対称性のドメインが互いに重なり合う部分に関し、部分対称性集合を分析し、そのような重なりを解決する。結果として、互いに重ならない部分対称性の集合が得られる。まず、複数のドメインに分類される点を特定する。次に、これらの点を全てのドメインから取り除く。次のフェーズでは、取り除かれた点をもっとも近いドメインにて復活させる。ここでいう近さは幾何的距離として算出される。最後のフェーズでは、各部分対称性について、対称性パラメータの局所的な最適化を実行する。入力は、表面点集合Pと対称性の集合Yである。出力は改善された対称集合Y'であり、Y'においてはドメインは重なり合わない。repartition_domainsの擬似コードは以下の通りである。
repartition_domains(P,Y)
begin
Qを空集合に初期化
for 各点pについて
c(p)=0
for Yに属する各部分対称性について
pがdom内なら、c(p)に1を加算
end for
c(p)≧2ならQ=Q+{p}
end for
for Yに属する各部分対称性について
dom=dom\Q
end for
while |Q|>0
for Yに属する各部分対称性について
domに隣接し、Qに含まれるQ'を特定
Q'をdomに追加
QからQ'を除く
end for
end while
for Yに属する各部分対称性について
x=local_parameter_optimization(P,dom,S,x)
end for
Y'={}
return Y'
end
[別の実施例とその実装]

0088

本発明を、上記したような好ましい実施例および実装として説明した。以下においては、さまざまな変形例について述べる。以下に述べる内容は、本発明を限定する意図ではなく、より明らかにするためのものであることは当業者には理解されるところである。
<ビューポイント>

0089

最適な実施例としては、表面のちょうど半分を視認可能であるような実質的に単一のビューポイントから視認可能な範囲のデータを取得している。別例として、視認可能面の最初の3Dマップは複数のビューポイントから生成されてもよい。これにより、3Dマップは、単一のビューポイントのときよりもはるかに多く物体表面の情報を含みうるが、それでも、自己遮蔽や内部遮蔽により3Dマップが遮蔽領域を持つ可能性はある。本発明は、3Dマップがどのように取得されたかに関わりなく、視認可能面の3Dマップを元に実行される。それゆえ、ビューポイントの数がいくつであろうとも、ビューポイントから範囲情報を抽出するアルゴリズムがどのようであろうとも、初期3Dマップを生成できる。
<視認可能面の範囲の取得>

0090

最適実施例においては、複数のカメラと立体計測をつかって視認可能面の範囲を取得する。別例として、複数のビューポイントから画像を取得する単一の可動カメラや構造化された光を投射する光源と共に使用される単一のカメラ、レーザーレンジファインダレーダーにより、視認可能面の範囲に関する情報を取得してもよい。範囲情報は、画像焦点から範囲を特定する技術や飛行時間を計測する特殊な2Dセンサにより取得することもできる。画像は可視スペクトラムにて取得される必要はなく、、赤外線音波電磁波などによって取得されてもよい。視認可能面の範囲を取得して視認可能面の初期の3Dマップを生成するための方法としては、このほかにも多くの方法がある。
<視認性>

0091

最適実施例においては、電磁スペクトラムうちの可視領域の光によって照らし出された物質不透明性によって視認性の基準を決定していた。不透明面がカメラとの間にあるときには、その後ろにある面は見えない。特性が異なるセンサを使う場合、センサの画像特性に応じた物質の不透過性により視認性の意味がかわってくる。視認可能面の3Dマップを作るために複数の画像特性(imaging modality)を利用してもよい。ある画像特性では隠れる面も、別の画像特性であれば視認可能となるかもしれない。全ての画像特性によっても遮蔽される面については、上記した方法により推論する。
<サンプリング>

0092

最適実施例においては、上記したように点は部分抽出される。別例として、異なるサンプリング技術を使ってもよい。たとえば、部分抽出ではなく全点についてのデータを使ってもよい。このような抽出技術によればデータの全てを使うので正確さという点で優れているが、処理時間が増加する。一方、同じ大きさの領域からは同じ数の点が抽出されるように、部分抽出してもよい。このような基準は、全体にも一部にも適用できる。一つの方法として、面法線に基づく密度にて部分抽出を実行してもよい。この場合、ビューポジションからみて大きく傾いている領域には比較的多くの点が存在することになる。一方、同じ大きさの領域から同じ数のデータ点が抽出されるように、隙間のない網目を適用してもよい。別例として、同じ大きさの領域から同じ数の点が抽出されるように、分析面(analytic surfaces)を適用してもよい。3Dの視認可能面のデータの抽出方法は、このほかにも多くの方法がある。
<視認可能面の表現>

0093

最適実施例においては、視認可能面はポイントクラウドとして示された。別例として、視認可能面は三角メッシュなど隙間のなく敷き詰められるメッシュとして表されてもよい。あるいは、2次曲面(quadric)やベジェ曲面のような分析面の集合として表されてもよい。視認可能面の表現方法は、このほかにも多くの方法がある。
<局所的な対称性の表現>

0094

本発明の重要な特性は、局所的な対称性、すなわち、物体のある領域にだけあらわれる対称性を見つけて利用できる点にある。こういった局所的な対称性を表現するために、最適実施例では対称型、数値パラメータベクトル、ドメインから成る「部分対称性」という概念を使っている。局所的な対称性を表現するため他の技術を用いてよい。
<ドメインの表現>

0095

最適実施例においては、上記したように対称性が適用される局所的な領域は対称ドメイン関数によって表現された。別例として、そのような領域は別の方法で表現されてもよい。視認可能面の3Dマップは三角メッシュによって表現されてもよいし、対称特性が適用される局所的な領域もすべて三角形の集合として表現されてもよい。

0096

ドメインは、幾何的な制約条件の上で表現されてもよい。例として、対称のドメインが楕円体内の点集合に相当する場合、楕円体のパラメータはドメインの形状を特定する上で重要である。より一般的には、ドメインは表面点pと実数値をマッピングする数値関数fによって特徴づけられるかもしれない。このような関数は「陰関数(implicit function)」として知られており、f(p)<0となるpの集合としてドメインを定義できる。ドメインの境界は陰関数の階層集合となる。動的輪郭(active contour)、ヘビ(snakes)、スプライン(spline)のように、2Dや3D空間の境界領域を定義するためは他にも多くの方法がある。たとえば、ドメインはカメラ画像空間内において動的輪郭によって表現されるかもしれない。そして、ドメインの探査はこの動的輪郭のパラメータの変更を含む。ドメインの表現方法については、この他にも多くの方法があり、上記記述は本発明を制約するものではなく明快にするための記述として解釈されるべきものである。
<ドメインの属性>

0097

最適実施例においては、対称性ドメインは連続的なポイントクラウドからなるが、本発明は連続的な点の集合に限られるものでないことには留意すべきである。しばしば、物体は、その物体の複数の部分に対して適用される対称性をもつ。各部は、同じ対称性を持たない他の部分とつながっている。このような場合、ポイントクラウドは連続しなくなる。別例として、対称性ドメインは連続する必要のない複数のポイントクラウドから構成できるとしてもよい。最適実施例として述べた連続的なポイントクラウドの使用は、本発明を制約する意味ではなく明快さのための記述である。

0098

更に、最適実施例においては、各表面点は唯一の対称性に属していた。これは、「repartition_symmetries」により強制されている。別例として、上記処理を取りやめることにより、各点が複数の対称性について(スコア計算上の)貢献をしてもよい。
<対称型>

0099

最適実施例においては、8種類の対称性について考慮していた。すなわち、鏡平面、鏡映軸、回転軸、鏡映点、回転点およびこれらの組み合わせである。別例として、別の対称型を導入してもよい。物体(と物体の3Dマップ)は、複数の直交しない対称性により特徴づけることができる。たとえば、3枚の直交しない鏡平面によって特徴づけることもできる。

0100

また、回転対称と鏡映面対称は以下のように一般化できる。一般的な回転対称は回転軸対称についての述べた円の代わりに楕円を、回転点対称について述べた球の代わりに楕円体を使う。一般化された鏡映面対称は、平面とは限らない鏡面として定義できる。一般化された回転軸は、曲がった軸により定義できる。一般化された鏡映軸対称も、曲がった軸により定義できる。このような一般化された対称性は、追加された自由度を特定するために追加的な数値パラメータベクトル要素を持つ。物体とその3Dマップはこれらの一般化された対称性により特徴づけることができる。そのほかにも、計算可能であり、かつ、遮蔽領域の見込み表面作成に使えるさまざまな対称性がある。
<対称性のスコア付け>

0101

最適実施例においては、仮定された部分対称性にスコア付けがなされた。別例として、最も近くにある視認可能点との距離をスコア計算のために使ってもよい。一方、スコア算出は、距離のエクスポネンシャルや距離と定数の2次方程式最小値を計算する関数に基づいてもよい。部分対称性のスコア付けの方法については、そのほかにも多くの方法がある。

0102

最適実施例においては、部分対称性をスコア付けするために使われる物体の唯一の要素は、視認可能面の3Dマップを含む点の空間的な位置である。別例として、面法線のような追加的な3D特性により対称性を評価してもよい。たとえば、対称変換による対応点は面法線と整合する。すなわち、ある点の面法線ベクトルは、対称特性によって、別の点の面法線ベクトルにマップされる。したがって、面法線の整合性を計測する関数は、部分対称性のスコアを計算する上で使用されるべき重み付けの要素となりうる。更に、スコア付け関数は、対称特性における面法線と位置の間の自然な関係を利用できる。たとえば、回転対称においては、面法線は対称軸や対称点と交わらなければならない。それゆえ、対称軸や対称点に対する面法線方向の距離は対称性をスコア付けするときに考慮できる。また、適切なデータとして他の属性を利用できる。たとえば、光強度、色、テクスチャなどである。適切に重み付けされた属性を部分対称性評価の導入するには、多くの方法がある。

0103

最適実施例においては、ドメインは大きさと形状によってスコア付けされた。特に、最適な実施例では形状のスコアであるscore3を
score3=r1/(r1+r2)
として計算している。ここで、r1は、ドメイン外部の点と隣接し、ドメインの境界に位置する点の数である。r2は、ドメイン外部の点と隣接しない、ドメインの境界に位置する点の数である。別例として、局所的な対称性が適用される領域としてドメインの適合性を計測するためにそのほかにもさまざまな方法にて形状のスコア付けを行ってもよい。たとえば、形状の長所を示すscore3Bを、以下のように計算してもよい。
score3B=r1/sqrt(|dom|)
ここでは、閾値より小さいscore3Bを要求することにより、許容可能なドメインを制約する。ドメイン内の点の総数に比べてドメイン外部の点に隣接する点の数が少ないドメインが許容可能されやすくなる。また、ドメインの凸面を考慮し、凸がないドメインほど許容されにくくしてもよい。局所的な対称性が適用される領域としてドメインの適合度を判定する上で、ドメインの形状をスコア付けするためのはそのほかにもさまざまな方法がある。
トップダウンによる全体検索とボトムアップによる全体検索の比較>

0104

最適実施例においては、全体としての検索方針は、対称特性を見つけ、その対称特性に合致するドメインを見つけ、対称特性とドメインをあわせて最適化することであった。これは、実質的にはトップダウンアプローチであるといえる。これに対し、ボトムアップアプローチを採用してもよい。

0105

「部分のような」局所的領域を探すことによりドメインの候補を見つけることからボトムアップアプローチは始まる。ドメインの候補を、スケトナイゼーション(skeletonization)を含めたさまざまな技術により、内部が大きく物体の残り部分に隣接する点が少ない領域を検出し、「部分のような」エリア確定する表面パッチを計算してもよい。ボトムアップ技術では、いったん部分のようなエリアが特定されると、その領域は対称性についてのテストにさらされ、そのための対称特性が算出される。そのあと、ドメインと特性が結合最適化処理される。ボトムアップ技術は、局所対称性領域が比較的小さな支えが少ない小さな領域であるときに有利である。局所的に注意を集中することは、こういった小さなエリアの部分対称性を見つける上で好ましい。
<対称特性検索のための初期値の選択>

0106

最適実施例において、対称特性を見つけるための初期値は数値パラメータ空間において、規則正しく格子状に分散する。ここでは、ポイントクラウドの塊の中心と交わるという対称特性を使っている。この検索のための開始点は別の方法で選択してもよい。たとえば、鏡平面の向きに応じて、開始点を選択する上で有利な平面を見つけるためにハフ変換を使う。また、観察されたポイントクラウドの面法線や部分形状特性を分析して、開始点を選択することもできる。サーチの初期開始点を選択するために環境条件を利用してもよい。たとえば、次のような観察を利用してもよい。各回転対称にとって、視認可能面の面法線は回転対称軸や点と交わらねばならない。回転対称を探す上で、多くの面法線と交わるという特徴を見つけることにより回転対称特性がありそうな場所を見つけるのにハフ変換を応用できる。初期の検索では(鏡平面や半径軸対称などの)垂直特性だけを考慮し、多くの物体の対称特性は垂直的であるという事実を利用する。探索の初期化のために物体の特性を分析してもよい。たとえば、視認可能面の3Dマップが取り出される初期画像画像解析は、物体の対称性を示していると思われる線のような幾何的特徴を明らかにする。初期の開始点は局所的に決定され、塊の中心にこだわらなくてもよい。
<数値パラメータベクトルの最適化>

0107

最適実施例において、数値パラメータベクトルの最適化は山登り探索によって実行された。別例として、最適化は、共役勾配法や準ニュートン法などの最適化手法により実行されてもよい。最適化は、主成分分析(principal component analysis)や凸最適化技術によって実行されてもよい。関数が局所的に最大となる位置を探すためには、この他にも多くの方法がある。
<対称性ドメインの検索>

0108

対称型、数値パラメータベクトルの初期値およびドメインが与えられると、対称性スコアが最適化されるときの組み合わせを見つけるためにパラメータベクトルとドメインの空間検索を実行することにより、部分対称性の局所的な最適値を見つける。ドメインの最適化と数値パラメータベクトルの最適化が混ざった結合最適化ループを実行してもよい。

0109

局所的対称性は別の方法で実行されてもよい。たとえば、ドメインは数値検索の各ステップで最適化されてもよい。ドメインは境界点に対する内部の点の比率が最大となるまで拡大されてもよい。ドメインは少しの数値カーブパラメータによって規定される境界カーブによって記述されるてもよく、部分対称性の検索は全ての数値パラメータの結合最適化として実行してもよい。ドメインの最適化にはこのように多くの方法があり、数値パラメータベクトルをドメインの結合最適化についても同様に多くの方法がある。
<対称性と分割>

0110

最適実施例において、物体は、その物体の単一のポイントクラウドから始めて分割される。分割は、部分対称性が検出される領域に対応するさまざまな部分集合から開始されてもよい。特定の物体を残り部分から分割することなく全体を通して部分対称性を探してもよい。局所的、全体的な対称特性を検出するための画像分割については多くの方法がある。
<部分対称性のスコア計算>

0111

最適実施例において、部分対称性の集合を計算し、見込み遮蔽面を計算するためにこの集合を利用していた。実施例において、候補となる部分対称性は2値の許容可否判定、すなわち、許容するか拒否するかという2値のテストをクリアするものである。2値テストではなく、比較的ふさわしい部分対称性や他の数値スコアリング関数のような価値を数値化する計算によって置き換えてもよい。このような価値を示す数値は、復元された面について、復元された遮蔽面ごとにその復元の確かさを示すように付与されてもよい。
<部分対称性の検出>

0112

部分対称性を探すとき、許容可能な複数の部分対称性を見つけてもよい。この場合、もっとも高いランキングとなる対称型となる部分対称性を選択する。別例として、追加的な基準に基づいて選択してもよい。たとえば、ドメインのサイズや投影点集合のサイズを考慮してもよい。
<復元されたポイントクラウドのクリーンアップ

0113

最適実施例では、部分対称性を考慮し、対称特性をドメイン内の各点に適用することによって見込み遮蔽面を計算していた。対称特性による投影点は、物体内部にも点を生成する。アプリケーションによっては、この点は重要であるかもしれないし重要でないかもしれない。別例として、これらの内部点の多くを取り除くためのクリーンアップ処理を実行してもよい。この技術は、物体の外に位置する観察者からは見ることのできない全ての投影点を取り除く作業を含む。もし、投影点があらゆる観察角度からも隠されるように物体によって閉じこめられているときには、その点は安全に削除できる。この削除処理は、元の表面ポイントクラウドが取得されたとき遮蔽されていた見込み表面点を含む集合に投影点集合を縮小する。
<復元された遮蔽面の表現>

0114

最適実施例においては、復元された隠蔽面は、対称性のある点の集合として表される。別例として、復元された遮蔽面は別の手段により表現されてもよい。たとえば、解析的表現、すなわち、2次方程式パッチなどによって表面を表示したいアプリケーションと、平面対称を想定する。Qvを視認可能面の2次パッチとすると、対称面をはさんで対応する2次パッチQsは、パッチパラメータの平面対称移動によって構築できる。対称特性に基づいて、ある領域の解析的表現をその対象領域の解析的表現に直接的にマッピングする技術はよく知られている。

0115

最適実施例においては、視認可能点につき単一の対称性としたが、複数の対称性を対称性の選択に際して考慮してもよい。複数の競合する対称性を計算し、対称スコアリング関数を使ってそれぞれに数値的な重み付けを行ってもよい。遮蔽領域を再現するとき、複数の競合する対称性は複数の遮蔽面モデルを作る。ロボットマニピュレーションに関する問題において、複数の復元モデルは有用である。ロボットのエンドエフェクタが把持を試みるときに実際の表面にぶつかってしまう潜在的な可能性を減少させることができる。
<物体>

0116

最適実施例においては、本発明の処理内容の説明を容易にするために選んだ簡単な幾何形状の物体を図示しながら説明した。本発明はこれらの物体のみを対象とするものではない。ビルや木、人、動物などの複雑な構造のモデリングにも応用できる。ここにリストアップしたものは本発明を限定するものではなく、むしろ明快さのために示したものであり、本発明は多くのさまざまな物理的構造や物体に応用可能である。
<実行ステップのコンピュータによる実装>

0117

最適実施例におけるステップ502と503は、文章と擬似コードにより記述された。これらは、C++、C、JAVA(登録商標)、Ada、フォートランその他汎用プログラミング言語によって記述できる。これらの実装は特定のコンピュータのためのマシン語コンパイルされたり、インタープリタ処理されたりする。これらのコードはアセンブリ言語で記述されてもよいし、特定のコンピュータのマシン語で記述されてもよい。コンピュータの実行命令はコンピュータにて読み取り可能な記録媒体に保持されてもよい。
<ロボット把持への応用>

0118

最適実施例においては、遮蔽面の見込み3Dマップを作るとして説明した。視認可能面の3Dマップとともに得られる遮蔽面の3Dマップが物体の表面を示すことになる。この表面についての情報は、物体の好ましい把持方法を算出しようとする把持主体によって利用されてもよい。このような把持主体については、米国特許仮出願の60/561,656(2004年4月12日出願)の「System for Computing Desirable Grasps of Objects with Generally Shaped Surfaces」に詳しいので、この内容とその関連主題を引用することにする。把持方法の算出は、物体を掴むロボットシステムによって実行される。こういったロボットシステムは、単一のビューポイントによって得られる情報を使って未知の物体を掴むことができるという有用な特性を備える。
<他の応用例>

0119

最適実施例はロボット把持を想定して説明したが、本発明はこのようなアプリケーションに限られるものではない。この発明は、物体の3Dモデルや3Dムービーを作るビデオゲームにも応用可能である。もちろん、これ以外にも本発明はさまざまな目的に応じて応用可能であることはいうまでもない。
結論派生および適用範囲

0120

まとめると、本発明はオブジェクトの3Dマップの視認可能領域から対称性を検出し、これらの対称性から遮蔽領域の見込み表面を計算する。本発明は、目的物体にしばしば生じるさまざまなタイプの対称性を利用する。また、本発明は物体全体または物体の一部に適用される部分対称性を検出して利用できる。本発明は、物体の1つの視認可能面から1以上の対称性を検出し、復元に際しては視認可能面にこれらの対称性を適用する。

0121

上記においては、本発明を特定の実施例について説明しており、本発明の範囲はこれに限られるものではない。当業者であれば、本発明が実施例の範囲に限定されないことは容易に理解されるところである。上記した本発明のさまざまな特徴・特性は、単体で、または組み合わせて用いられても良い。請求項群の一式として本発明の思想や範囲から逸脱しない程度に、これらに加えてさまざまな変形や変更が可能であることは明らかなところである。それゆえ、先述の記述や図面は限定的ではなく例証的に扱われるべきものである。「含む」や「持つ」といった単語は開かれた意味に用いられている。

図面の簡単な説明

0122

軸に対して回転対称なボトルの斜視図である。
3枚の互いに直交する鏡板と箱の斜視図である。
全体的な対称性と局所的な対称性を備えるフライパンの斜視図である。
本発明の実施例に関連し、物体の視認可能面から3Dマップを取得する画像装置の概要図である。
本発明の実施例に関連し、遮蔽された面を見込み特定する処理のフローチャートである。
本発明の実施例に関連し、特定された対称性にスコア付けをする方法ついて議論の対象となる1つの鏡板と箱の斜視図である。
本発明の実施例に関連し、遮蔽された表面を見込み特定する処理について、疑似コードの呼び出し構造を示す図である。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

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

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

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

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

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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