(57)【特許請求の範囲】
【請求項１】
三次元表面を計測するためにコンピュータが実行する方法であって、該方法は、前記コンピュータが、
構造化照明を三次元表面に投影し、且つ複数の画像セットを取得すること、
複数の点群を得るために画像セットを処理すること、
空間アキュムレータの格子の各素子内に点群情報を受け取るように構成された空間アキュムレータを規定すること、
空間アキュムレータへ複数の点群を蓄積すること、
空間アキュムレータ内の複数の点群を統合すること、及び、
統合された空間アキュムレータの内容に基づいて三次元表面の空間座標を生成すること、を包含し、
各点群の各点が、品質測定及び空間値を有する複素値を有する、方法。
【請求項２】
構造化照明は、互いに異なる入射角から投影される、請求項１に記載の方法。
【請求項３】
複数の画像セットは、第１画像セット及び第２画像セットを含み、第１画像セット及び第２画像セットが異なるカメラにより取得される、請求項１に記載の方法。
【請求項４】
複数の画像セットは、第１画像セット及び第２画像セットを包含し、且つ第１及び第２の画像セットは、２つの異なるパターン集合を投影することによって取得される、請求項１に記載の方法。
【請求項５】
２つの異なるパターン集合は、２つの異なる方向を有する縞パターンである、請求項４に記載の方法。
【請求項６】
構造化照明は、正弦波縞パターンである、請求項１に記載の方法。
【請求項７】
複数の画像セットを取得することは、第１カメラを用いて画像の第１トリオ及び第２カメラを用いて画像の第２トリオを取得し、画像の第１トリオは、第１点群を生成するために処理され、且つ画像の第２トリオは、第２点群を生成するために処理される、請求項１に記載の方法。
【請求項８】
空間アキュムレータ内の複数の点群を統合することは、空間アキュムレータ内での点群の代数的総和を包含する、請求項１に記載の方法。
【請求項９】
代数的総和は、複素値の代数的総和である、請求項８に記載の方法。
【請求項１０】
空間アキュムレータ内の複数の点群を統合することは、非線形な結合を包含する、請求項１に記載の方法。
【請求項１１】
非線形な結合は、空間アキュムレータの各素子について幾何学的中央値を決定することを包含する、請求項１０に記載の方法。
【請求項１２】
非線形な結合は、投票処理を採用する、請求項１０に記載の方法。
【請求項１３】
三次元表面に関する情報を提供するために三次元表面の空間座標を利用することをさらに包含する、請求項１に記載の方法。
【請求項１４】
三次元表面に関する情報は、検査情報である、請求項１３に記載の方法。
【請求項１５】
三次元表面に関する情報は、計測情報である、請求項１３に記載の方法。
【請求項１６】
複数の点群は、多重反射によって引き起こされるエラーを低減するように統合される、請求項１に記載の方法。
【請求項１７】
三次元表面を計測するためのシステムであって、該システムは、
三次元表面に構造化照明を投影するように構成された構造化照明プロジェクタ；
構造化照明プロジェクタに結合され、複数の異なる構造化照明投影を三次元表面へ生成するように構造化照明プロジェクタを制御するための制御器；
それぞれは制御器へ結合された複数のカメラ、ここで各カメラは、それぞれ異なる構造化照明投影が三次元表面に存在する間に、三次元表面の画像を取得するように構成される；
を備え、
制御器は、各カメラから画像情報を受け取り、且つ複数の点群を生成するように構成され、各点群は、各画素毎に、各カメラからの三次元画像データ及び品質測定を含む複素値を含み；且つ
制御器は、空間アキュムレータへ複数の点群を蓄積し、その後、空間アキュムレータ内の複数の点群を、空間アキュムレータの内容として統合し、且つ空間アキュムレータの内容を用いて単一の統合された三次元点群を生成するよう構成される、システム。
【請求項１８】
構造化照明プロジェクタは、空間光変調器を具備する、請求項１７に記載のシステム。
【請求項１９】
空間光変調器は、各構造化照明投影を規定する制御器から信号を受信するように制御器へ結合される、請求項１８に記載のシステム。
【請求項２０】
各構造化照明投影は、別の構造化照明投影とは異なる位相を有する正弦波縞パターンを具備する、請求項１９に記載のシステム。
【請求項２１】
制御器は、複素値の代数的総和を実行することによって複数の点群を統合するように構成されている、請求項１７に記載のシステム。
【請求項２２】
制御器は、複数の点群を非線形演算で統合するように構成される、請求項１７に記載のシステム。
【請求項２３】
非線形演算は、各点群における対応する点についての幾何学的中央値を決定することを包含する、請求項２２に記載のシステム。
【請求項２４】
非線形演算は投票処理を包含する、請求項２２に記載のシステム。
【請求項２５】
統合された複数の点群は、空間アキュムレータの各素子のための領域値及び品質測定の両方を含む、請求項１に記載の方法。
【請求項２６】
統合された複数の点群は、空間アキュムレータの各素子のための領域値及び品質測定の両方を含む、請求項１７に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の態様は、三角測量の原理を用いる、複数のカメラ及び構造化光源からの画像データに基づく対象の複合表面プロファイルの生成に関する。
【背景技術】
【０００２】
電子集積回路及び個別電子部品を載せる回路基板は公知である。回路基板は、所定の導体パス及び電子部品、例えば集積回路チップ、抵抗、及びコンデンサ、のリード線を受けるパッドを用意する。回路基板構築工程中、はんだペースト塗布部が、適当な位置で基板上に置かれる。はんだペースト塗布部は、通常、基板上にステンシルスクリーンを置き、ステンシル開口部を通してはんだペーストを施与し、且つ基板からステンシルを外すことによって施与される。その後、回路基板電子部品が、好ましくは部品装着装置で、基板上に位置合わせされ、電子部品のリード線で個々のはんだペースト塗布部に置かれる。回路基板は、全部品が基板上に置かれた後に、はんだペースト塗布部を溶かすためにオーブンを通過され、部品と基板との間の電気的及び機械的接続を作る。
【０００３】
はんだペースト塗布部と電子部品とのサイズ、及びそれらが基板上に置かれねばならない精度は、電子産業におけるミニチュアライゼーションの重要視とともに益々小さくかつ緊密になっている。はんだペースト塗布部の高さは、５０ミクロンでありえ、そしてはんだペーストブリックの高さは、設計された高さ及びサイズの１％以内まで頻繁に測定されるに違いない。はんだブリックの間の中心と中心の間隔は、時々２００ミクロン程度に小さくなることがある。はんだペーストが余りに少ないと、電子部品のリード線と回路基板のパッドとの間の電気接続を生じないことがあり、はんだペーストが余りに多いと、部品のリード線の間の架橋且つ短絡をもたらすことがある。個別電子部品、例えば抵抗及び容量は２００ｘ４００ミクロン程度に小さく、そしてマイクロボールグリッドアレイ部品のリード線は、３００ミクロン未満の中心間の間隔を有しうる。
【０００４】
単一回路基板は、製造するのに数千ドル及び数万ドルすらかかることがある。組立工程が完了した後の回路基板のテストは、はんだペースト配置、部品配置、及びリード線接続における誤りを検出しうるが、欠陥基板の唯一の救済策は、多くの場合、基板全体を廃棄することであることが多かった。さらに、構成部品の微細化で、回路基板の目視検査は、光学的な拡大を用いても信頼性が低い。従って回路基板は、電子部品の基板への配置の前に不適切なはんだペースト塗布が検出されうるように、組立工程の間に検査されることが緊急の課題である。そのような工程内はんだ検査は、高価な部品が未だ回路基板上に置かれていないので、失敗のコストを低減する。
【０００５】
配置後、部品の適切な配置を確実にするために、部品を検査することも重要である。不適切に置かれた部品、失われた部品、又は不良のはんだ接合は、部品の配置又ははんだペーストのリフロー中に導入される典型的な欠陥である。リフローの後、部品の適切な配置及びリフローされたはんだ接合の品質は、全部品が適切にはんだ付けされ且つ回路基板に接続されたことを確実にするために自動光学検査システムを用いて検査されうる。現行の光学検査システムは、欠陥を検出するために回路基板の二次元映像イメージを用いる。しかし、回路基板の三次元高さ画像を検出する光学検査システムは、例えば、持上げられたリード線、パッケージ共平面性、及び部品が墓石や掲示板のように立つような配置欠陥の検出を可能に又はそうでなければ改善しなければならない。
【０００６】
三次元検査システムの１つのタイプは、位相表面形状計測法を用いる。通常、位相表面形状計測法システムは、単一のカメラ及びプロジェクタを用いる。多数のカメラが用いられるときには、ユーザは、取得結果の点群をツール、例えばPoint Cloud Library（ＰＣＬ）のような、これはオープンソースコンピュータ映像ライブラリである、を用いて統合する必要がある。ＰＣＬは非常に強力であるが、高速自動検査システム、例えば上で挙げたものに用いるには余りにも遅過ぎる。
【発明の概要】
【０００７】
三次元表面を計測するためのコンピュータ実装方法及びシステムが提供される。本方法は、構造化照明を表面に投影すること、及び複数の画像セットを取得することを包含する。画像セットは、複数の点群を得るために処理される。空間アキュムレータが規定される。複数の点群の第１点群は、空間アキュムレータ内で複数の点群の第２点群と結合される。表面の空間座標が、空間アキュムレータの内容に基づいて生成される。
【図面の簡単な説明】
【０００８】
【図１】ここで記載される実施態様が特に適する多重反射問題を例示する図である。
【図２】本発明の実施態様による位相差構造化光を用いる、回路基板の三次元画像化のための多数画像化デバイス高さ画像センサの部分図である。
【図３】本発明の実施態様による位相差構造化光を用いる、回路基板の三次元画像化のための多数画像化デバイス高さ画像センサの斜視部分図である。
【図４】本発明の実施態様による点群統合の方法のフロー図である。
【図５】本発明の実施態様による多数の点群を取得し且つそれらを共に統合する方法のフロー図である。
【図６】２つのカメラＡ及びＢのために同じＸ-Ｙ位置からの複素値がプロットされる例を示す図である。
【図７】本発明の実施態様による、規則的な空間アキュムレータ格子に投射されるときの斜め視線からのカメラにおける複素値を用いる利点を例示する図である。
【図８】同じ対象物と右側からカメラによって見られた投影パターンとを示す図である。
【図９】本発明の実施態様による、空間アキュムレータにおける単一直線に沿う多数のカメラ視点からの複素値の統合を示す図である。
【図１０Ａ】数台のカメラの結果の非線形混合、この場合には幾何学的中央値、の利点を示す図である。
【図１０Ｂ】数台のカメラの結果の非線形混合、この場合には幾何学的中央値、の利点を示す図である。
【図１１】本発明の実施態様により計測されるべき表面と、３台のカメラの画素との交点を示す図である。
【図１２】本発明の実施態様における、投影された画素についての信号がいかにして格子上に分配されるかを示す図である。
【発明を実施するための形態】
【０００９】
白色光位相差表面形状計測法の使用は、回路基板の位置的な表面高さ画像を光学的に取得するための公知の技術である。３Ｄ（三次元）プロファイルを生成するために正弦波縞パターンを投影するシステムが、米国特許第6,750,899号明細書に記載されている。三次元プロファイル又は高さ地図は、光源からの様々な構造化光パターンを対象へ投影することによって生成され得、１以上のカメラによってパターンを記録し且つ画像を適切に処理する。パターンは、様々なカメラによって見られるときに対象の形状によって変調される。パターンの変調は、三次元点群を生成するために解析される。ここで用いられるとき、「点群（point cloud）」とは、或る座標系におけるデータ点と、品質測定を示す少なくとも１つの追加のデータ点との集合である。三次元座標系においては、点は、通常、Ｘ、Ｙ、Ｚ座標により規定される。３Ｄプロファイルを生成するための正弦波縞パターンを投影するシステムが、米国特許第6,750,899号明細書に記載されている。
【００１０】
被検査対象の急傾斜及び窪み形状は、影および吸蔵(occlusions)をもたらし、したがって、1つの再構成における欠落が別の再構成から補われうるようにするために、複数の点群を結合することが望ましい。三次元縞投影装置の１例が、図２に関して以下で記載される。
【００１１】
カメラによって画像化される前に、構造化光パターンは、対象からの多重反射を受けうる。これらの反射は、画像に基づいて生成される点群に重大な誤り又は雑音をもたらしうる。多重反射は、光沢又は鏡面反射性の対象によってより悪くされる。
【００１２】
図１は、多重反射問題を示す。入射の構造化照明が線１０で示されており、それは、Ｚ座標の値Ｚ１を有する点Ａで表面１８から反射される。反射された構造化照明の部分１２が、光学部品２６を通過し、そして検出器１５によって検出される。しかし、反射された入射の照明の別の部分１４は、対象物１７の表面１６で線１９のように反射される。この多重反射の照明はまた、光学部品２６を通過しそして検出器１５により検出される。もし、線１９に沿う多重反射照明の強度が、線１２に沿う直接反射照明よりも強いと、点Ａの報告されるＺ座標は、Ｚ２であり、ここで線１９は入射照明の線１０を交差する。こうして、多重反射照明が、本方法における誤りの源である。
【００１３】
点群雑音低減法が存在するが、通常の位相表面形状計測法の再構成方法は、弱いデータにおいて雑音を大きく増大させうるので、問題が生じる前に方法の初期段階で、弱いデータの重み付けを軽減することが特に望ましい。さらに、悪い点を除去するための従来技術が、吸蔵及び多重反射の故に攪乱されうるところのデータの大きな割合によって効果的でなくなる傾向がある。必要とされるものは、点群エラー、特に光る対象物及び部分的吸蔵領域に対する、を劇的に減らすために点群を統合するための改良された方法である。
【００１４】
図２は、本発明の実施態様による位相差構造化光(phased structured light)を用いた、回路基板１８の三次元画像化のための多数画像化デバイス高さ画像センサ６０の線図である。パターン投影源６２は、制御器６６と結合され、且つ、結像レンズ２２を有する空間光変調器（ＳＬＭ）６４で結像することによって、構造化光パターン３０（図３に表示）を回路基板１８上へ投影する。１実施態様において、ＳＬＭ６４は、Texas Instruments（テキサスインスツルメンツ）社から入手可能なデジタル・マイクロミラー・デバイス（ＤＭＤ）（例えばＴＩ社の製品番号はDLP5500）である。この装置は、表面上に任意の画像を形成するように個々に向きを向けうるデジタル・マイクロミラーのアレイを組み込んでいる。動作において、要求された構造化光パターンは、ＤＭＤアレイ上でプログラム化される。プログラム化された画像は、マイクロミラーのそれぞれを、個々のミラーの位置での画像の画素強度値に対応するところの２つの位置の１つへ傾斜させる。高輝度の画素にていては、傾けられたＤＭＤは、光源２４からの光を反射し、結像レンズ２２を通して回路基板１８へ明るい画素を生成する。構造化光パターン３０における低輝度に対応する画素については、ＤＭＤミラーの傾斜は、光源２４からの光を反射し、結像レンズ２２から離れたところに構造化光パターン３０内の暗い画素を生成する。ＤＭＤへ送られるプログラム化された画像を変えることによって、位相シフトされた画像の要求された列を生成することができる。ＳＬＭ６４は、明るい光源２４、例えば白色光ＬＥＤを用いて照射される。２台のカメラ５２ａ、５２ｂは、制御器６６へ結合され、且つ構造化光パターン３０で照射された回路基板１８の画像を同時に取得するように構成されている。カメラ５２ａ、５２ｂは、マシン・ビジョンにおいて用いられるいくつかの画像センシング技術の何れかの１つ、例えば検出器上に回路基板１８の画像を作るところの、結像レンズ２６と結合されたＣＣＤ又はＣＭＯＳ検出器でありうる。パターン投影源６２及びカメラ５２ａ、５２ｂの各光軸入射角の間の相違は、高さセンサの三角測量角を示す。
【００１５】
動作において、光源２４がＳＬＭ６４を照射し、そして高輝度値を有するようにプログラムされた画素は、結像レンズを通して光を反射する。結像レンズ２２は、ＳＬＭからの光を回路基板１８上に投影する。同時に、両方のカメラ５２ａ、５２ｂが、照射期間の間、回路基板１８の最初の画像を取得する。その後、ＳＬＭ６４内にプログラム化された投影パターンが、第１の正弦波パターンの分数の位相間隔の等価間隔の相対的位相シフトを有する第２の正弦波パターンへ変えられ、そしてカメラ５２ａ、５２ｂは第２画像を取得する。最後に、ＳＬＭ６４内にプログラム化された投影パターンは、その後、第１及び第２正弦波パターンの分数の位相間隔の等価間隔の相対的位相シフトを有する第３の正弦波パターンへ変えられ、そしてカメラ５２ａ、５２ｂは第３画像を取得する。
【００１６】
構造化光画像の列を生成するためにＳＬＭ６４を使用することは、機械的にシフトさせられるガラス上のクロームレチクル（十字線）の使用よりも利点がある。ガラス上のクロームレチクルによって、構造化光パターン３０は、ガラス上のクロームパターンで固定され、且つ異なる位相を有する画像の列は、レチクルの物理的な移動によって生成される。レチクルを物理的に移動させることは、コストが高く且つ機械的に擦り減り且つ究極的に壊れがちな運動構成要素を必要とする。加えて、正弦波パターンの周期を変化させることがしばしば要求される。正弦波パターンの周期を変化させることによって、高さイメージセンサの高さ領域及び高さ分解能は、調整されうる。センサの高さ領域を変えることは、配置された部品の高さが、レチクルパターンによって決定されるところのセンサの高さ領域よりも高くありうるので、部品が配置された後に回路基板を検査するときに特に重要である。ガラス上のクロームレチクルパターンは、１つのレチクルを別のものに物理的に取り替えることを必要とし、これはセンサの動作中に通常は達成し得ない。
【００１７】
ＳＬＭ６４によって、様々なパターンが、数のアレイを制御器６６内に簡単にプログラミングすることによって回路基板１８上に投影されうる。変化する位相をもつ画像列を投影することは、連続する画像を制御器６６へプログラミングすることによって簡単に達成される。制御器６６メモリから連続する画像を指定することによって、位相画像の列が、レチクルを物理的に動かすことなく投影される。さらに、制御器６６へプログラムされたパターンの位相周期を変えることによって、高さ画像化センサ６２の高さ分解能及び高さ領域が、センサの動作中に変えられうる。
【００１８】
図３は、本発明の別の実施態様による位相差構造化光を用いて回路基板の三次元画像化のための多数画像化デバイス高さ画像センサ７０の線図である。この実施態様において、４台のカメラ５２ａ、５２ｂ、５２ｃ、５２ｄは、回路基板１８上の正弦波構造化光パターン３０の画像を、４つの異なる入射角から同時に取得するよう構成されている。４台のカメラ５２ａ、５２ｂ、５２ｃ、５２ｄの入射角のそれぞれは、パターン投影源６２の投影入射角に対する三角測量の角を形成する。パターン投影源６２は、正弦波の構造化光パターン３０を回路基板１８上に投影する。カメラ５２ａ、５２ｂ、５２ｃ、５２ｄは、正弦波パターン３０の画像を取得するために好ましくは同時に起動される。パターン投影源６２は、第１正弦波パターンの分数の位相間隔の等価間隔の相対的位相シフトを有する第２正弦波パターンを投影し、そして４つの光イメージセンサ５２ａ、５２ｂ、５２ｃ、５２ｄは、画像の第２セットを取得するために同時に起動される。最後に、パターン投影ソース６２内のプログラム化された投影パターンは次に、第１及び第２正弦波パターンの分数位相間隔の等価間隔の相対的位相シフトを有する第３正弦波パターンに変えられ、そしてカメラ５２ａ、５２ｂ、５２ｃ、５２ｄは、それぞれ第三画像を取得する。図３においては、４台のカメラが単一のプロジェクタを伴って示されるが、本発明の実施態様はまた、単一のカメラと連動して動作する多数のプロジェクタを備える。さらに、本発明の実施態様はまた、多数のプロジェクタと動作する多数のカメラを備える。画像は、画像セットを１つの高さ画像へ処理する制御器６６へ送られる。
【００１９】
図４は、本発明の実施態様による点群統合方法のフロー図である。方法１００は、ブロック１０２で始まり、そこでは、数個の異なる構造化光パターンが、１以上の方向から対象に投影される。これらの投影されたパターンの各々は、１以上のカメラで画像化される。次に、ブロック１０４では、与えられたプロジェクタについて、三次元表面が規定され、そしてこの表面上の空間アレイが、空間アキュムレータとして用いられる。ブロック１０６で、ブロック１０４のプロジェクタと関連付けられた各カメラについて、三次元対象座標とカメラ画素に対応する１以上の品質測定とから成る点群を決定するために、構造化パターン画像が、システムの較正された幾何的配置を用いて解析される。ブロック１０８で、ブロック１０６からの各点群座標は、空間アキュムレータへ数学的に投影され、その空間アキュムレータは領域値（空間アレイに対する）及び領域値に結合された品質測定を蓄積する。ブロック１１０では、複素値が、空間アキュムレータ内の各素子についての領域値と品質測定とに対応して作られる。次に、ブロック１１２では、複素値は、空間アキュムレータ内の各素子についての単一の領域値及び単一の品質測定を作るために空間アキュムレータ内の各素子について統合される。結果が点群情報の吸蔵及び/又は多重反射の影響を低減又は除去するところの単一の点群である限り、様々な方法が統合のために用いられうる。ブロック１１４では、方法は、全プロジェクタについて繰り返しがなされるまで、別のプロジェクタについて繰り返される。
【００２０】
図５は、本発明の実施態様による、多数の点群を取得し且つそれらを一緒に統合する方法のフロー図である。方法１５０は、ブロック１５２で始まり、そこでは少なくとも３つの異なるパターンが、計測されるべき表面に順次投影され、そしてその画像が複数のカメラによって取得される。好ましくはパターンは、３つの異なる位相で表示された正弦波縞パターンである。次に、ブロック１５４では、画素の灰色レベルの組み合せが、複素値（直角座標、例えばｚ＝ｕ＋ｉｖで表示された、又は大きさと位相の極座標で表示された）を作るように形成される。好ましくは複素値の大きさは、値の質を表示し、そして位相は、観測されたパターンについての空間情報（例えば、投影された正弦波の位相）を示す。ブロック１５６においては、画素の位相が、画素に対応する投影されたパターン内の一定位相の表面を識別するために処理される。ブロック１５８では、システムの較正された幾何学的配置が、カメラから対象領域への画素に対応する光線を識別するために用いられる。次に、ブロック１６０では、光線（ブロック１５８）と識別された表面（ブロック１５６）との間の交差が、画素に対応する観測された点の唯一の三次元座標を決定するために計算される。ブロック１６２では、位相が公称のラップ高さに対応するように、且つ画素の位相に対応する訂正された複素値を作るように、訂正される。ブロック１６２は、共通の高さのスケールへ正規化されなければならない多数のカメラを採用する実施態様において、要求されるだけである。ブロック１６４では、画素に対応する複素値が、空間アレイ内に蓄積される。ブロック１６６では、ブロック１５４〜１６４が、全てのカメラの画像内の各画素について繰り返される。パターンの追加の集合が、投影され得、且つ追加の点群が、各カメラとプロジェクタの対に関する特定のパターンの集合のために生成されうることが注意されるべきである。例えば、縞パターン集合の方向が変化させられ得、そして追加の点群は、各カメラとプロジェクタの対について生成されうる。ここで規定されたように、パターン集合は、特定のパターンを用いて取得された多数の画像であり、その集合は単一の点群を生成するために十分な画像情報を含んでいる。ブロック１６６が一度完了すると、方法１５０は、ブロック１６８で、そこでは空間アレイにおける各アキュムレータの値が統合される、ことを続ける。この統合は、何らかの適切な技術により遂行されうる。いくつかの代表的な技術は、これに限定することなく、代数的総和又は幾何学的中央値を含む。最後に、ブロック１７０で、空間アレイにおける各アキュムレータの値の逆正接が、表面に対する領域マップを導き出すために取られる。
【００２１】
各画素が与えられたカメラとプロジェクタの対について処理された後、複数の値（ｘ,ｙ,ｚ,ｒ,ｍ）の点群の１つが処理される。ここで、ｒは正規化された反射率、そしてｍは、米国特許第6,750,899号明細書の式（１）によって定義された縞変調（コントラスト）である。それぞれの点は、反射率の値及び変調値と併せて３Ｄ座標（ｘ,ｙ,ｚ）を有する。この点群は、対象の真の形状を識別するために多くのスキーム又は技術によって直接的に用いられることができる（参照 Jagan Sankaranarayanan, Hanan Samet, and Amitabh Varshney. "A fast all nearest neighbor algorithm for applications involving large point-clouds.（大きな点群を含む応用のための高速全最近傍アルゴリズム）" Computers & Graphics 31,.(2) (2007), 157-174, Ruwen Schnabel, Roland Wahl, and Reinhard Klein. "Efficient RANSAC for Point‐Cloud Shape Detection.（点群形状検出のための効率的RANSAC）" Computer Graphics Forum. 26, 2 (2007)）。参照された論文は、点群のエラー又は欠落データを減らし又は除去することを試みている。これらの問題は、吸蔵又は多重反射によってもたらされることが多い。
【００２２】
従来技術の限界は、現代のプリント回路基板構築ラインの著しい速度要請に合わせるよう要請される膨大な計算上の負荷である。従って、非常に速度の速いアプローチが、プリント回路板製造産業へ貢献するために要求された。ここで記載された実施態様は、空間アキュムレータとして公知の点の格子上に点群を投影する。１実施態様において、空間アキュムレータは点の空間的拡がりに概略で平行な２次元平面である。これらの実施態様において、空間アキュムレータは、複素値を蓄積するように構成される。複素値の大きさは、何らかの品質測定を示し、そしてその位相は何らかの基準面（通常は平面）からの距離を示す。
【００２３】
投影処理は、部分的には斜めの幾何的配置によって、且つ部分的には平坦でない形状によって引き起こされる不規則性によって、画素の不規則な格子を作る。２Ｄ空間アキュムレータの格子上に正確には置かれないｘ−ｙ座標の画素は、適切なアンチエイリアシング・カーネル、例えば双線形補間に関係したピラミッド・カーネルによって補間される。投影処理の１例として、図１１は、３台のカメラ画素と計測されるべき表面との交点を示す。カメラ光線と計測される投影パターンとの交点は、交点の較正されたＸ、Ｙ、Ｚ位置の決定を可能にする。これらの各点は、その後、アキュムレータ格子に投影される。図示された場合について、格子は、点の空間的拡がりに概略で平行な平面である。しかし、ここで記載された実施態様は、平坦な面を概略で計測することに限定されない。効率的なアキュムレータ格子のための主要な要求は、格子内の各アキュムレータについて、いくつかの空間的位置の評価を結合することである。もし格子が過度に斜交していると、例えば、広く分離された空間点からの画素は、単一アキュムレータ内で偶然に結合されうる。実際、アキュムレータ格子は、傾けられ又は計測工程にとって都合のよい何らかの形状へ歪められうる。通常、アキュムレータ格子へ投影されたものとしてのカメラ画素は、格子点に正確には置かれていない。もし画素値が、最も近いアキュムレータ格子点へ簡単に追加されるならば、空間位置の丸め（四捨五入）に際の誤差が、ラスタ機器への映像の描画において遭遇するところの周知のアンチエイリアシング問題に類似の再構成における雑音をもたらす。この問題を回避するために、各画素は、蓄積される前に、再構成（アンチエイリアシング）カーネルと共に畳み込み積分されなければならない。図１２は、投影された画素についての信号が、いかにして格子上に分配されるのかを示しており、この例においては、双線形補間カーネルが適用される。投影された点の近傍の画素の各々は、その画素におけるカーネルの領域により乗算された、投影点の複素値によって増分される。工程は、各投影されたカメラ画素について繰り返され、それにより、簡単で速い重み付け及びアキュムレータ格子への複素加算を提供する。アキュムレータ格子へのこの簡単な加算の数多くの利点は、以下に記載されるように与えられる。方法自体は、点群を順序付けられた方向（例えば低から高へ）に点検する必要がないので、且つアキュムレータ内での既存の値を新たな値で書き換える必要がないので、三次元対象の画像を生成するのに用いられる「スプラッティング（splatting）」法とは異なる。各カメラ及び投影されるパターンの集合について、表面形状についての或る推定値が与えられ、そして空間アキュムレータは表面推定値を追加される。
【００２４】
推定量は、平面以外の何らかの適切な表面上に投影されてもよい。例えば、もし対象物が球体であると予想されるなら、推定量は、推定量に最も適合するように調整された球体のパラメータで球体上に投影されうる。
【００２５】
高さ画像を生成する容易な仕方は、各カメラからの高さ推定値を任意のＸ、Ｙ位置で平均化することである。この手法の主な利点は、簡単さであるが、多重反射の影響を抑制し又は除去するにはほとんど役立たない。
【００２６】
１実施態様において、空間アキュムレータの各素子における複素値（ｕ＋ｉｖ）が、総計されうる。ここで、ｕ及びｖは、複素画素値の実の構成部分及び虚の構成部分である。（代替的には、複素画素は、長さ√ｕ２＋ｖ２及びatan2(u,v)の位相角のベクトルとして表示されうる）。正弦波縞パターンを用いる実施態様において、与えられた画素に対する領域値は位相値の関数として符号化される。１実施態様において、品質測定は、より高い反射と縞コントラストを有する画素に対してより大きな重みを指定するところのＱ＝ｒx ｍとして定義される。この実施態様において、複素点値の位相は、点の高さ（又は空間アキュムレータについての公称ゼロ位置からの距離）を符号化する。
【００２７】
複素平面における総和は、低い品質推定値を有する画素の重み付けを自動的に減らす。図６は、２台のカメラＡ及びＢについての同一のＸ-Ｙ位置からの複素値がプロットされている１例である。カメラＡからの強い信号「Ａ」は、位相角ΦＡ及びベクトル長ＱＡとして符号化された高さを有し、そして弱い信号「Ｂ」は、位相角ΦＢ及びベクトル長ＱＢとして符号化される。もしもカメラＡ及びＢからの信号が、高さに簡単に変換され平均化されると、結果は、高さＨＡとＨＢの間の中間レベルである。複素平面でのベクトルの加算は、強い信号（ベクトル「Ａ」）によって支配され、弱い信号（ベクトル「Ｂ」）からのほんの小さな寄与しかなく、位相角ΦＣとして符号化された結果の高さを有する結果を生成する。
【００２８】
図７は、通常の空間アキュムレータ格子上に投影されるとき、傾いた視点のカメラにおいて複素値を用いる利点を示す。上部の図面は、傾いたカメラの画素が、どのようにして不規則な表面形状に写像するのかを示す。各画素は、点の間の間隔が対象の局所的形状に依存するところの対象上の点を見る。正弦波縞パターンが投影される１実施態様において、各画素は、表面に投影された位相（プロジェクタは示されていない）及び品質測定を測定しうる。図７の第２の部分は、測定された複素値を示し、各画素位置でベクトルのプロットは描かれ、水平軸及び垂直軸はそれぞれ、その画素での信号の実部（ｕ）成分、及び虚部（ｉｖ）成分である。各画素についてのベクトルプロットは、それらの適切な横位置で描かれている。動作は、測定された画像複素値及びクリアに（ゼロに設定）された出力複素画像で始まる。簡単のため、この操作は、より正しい位置補完技術（例えば、上に記載された双線形フィルタ）の代わりに最近傍サンプリング技術を用いて記載される。最近傍サンプリングにおいては、カメラ画素は、最近傍空間格子位置へ投影される。各カメラ画素をそれらがアキュムレータへ加えられるときに順番に見ると；（１）最も左の画素は、アキュムレータ内の適切な位置へ単純に加えられる；（２）次の２つの画素は、両方とも最近傍の同一アキュムレータ位置であり、それらは順番にアキュムレータへ加えられる（我々は。複素値データで作業しているので、この総和は位相値の重み付け平均のように働く）；（３）この例で次の３つの画素は全て、唯一つのアキュムレータ位置に届けられる。ここで、２つのアキュムレータ格子点は、それらに写像する如何なるデータも持っていない；これら格子位置はゼロ値（信号強度がないとして印が付けられた）に留まることに留意されたい。
【００２９】
第２のカメラはまた、同じ対象を写し、且つ同じ仕方で処理される。図８は、同じ対象及び右側からカメラによって写される投影されたパターンを示す。再び、各カメラ画素の複素信号に沿って表面へ写像するカメラ画素が示されている。その後、カメラ画素の位置は空間アキュムレータ格子へ投影される。左カメラにより失われた画素位置は、右カメラにより写され、逆の場合もまた同様でありえ、吸蔵の領域を満たすことに注意されたい。
【００３０】
図９は、空間アキュムレータ内の単一直線に沿う多数のカメラ視界からの複素値の統合を示す。空間アキュムレータの別の複素値は、明確のため省略されている。図９のプロットの上段は、左カメラによって観測された複素値であり、プロットの第２段目は、右カメラからの値である。もしも２台のカメラだけが利用可能であるならば、画像を結合する最も簡単な方法は、プロットの第３段目に示されたように複素値を単純に加えることである。喪失されていた値は満たされ、そして全カメラが一致しているデータ点は強力な信号を生成することに留意されたい。
【００３１】
非線形手法（複素値の単なる加法ではない）を用いることによって数台のカメラの空間アキュムレータを結合することは、実際に有利であることが判った。そのようなスキームは、幾何学的中央値及び投票処理(voting)を用いることを含む。幾何学的中央値のアプローチにおいて、個々の複素値は、いわゆる幾何学的中央値又はＬ１推定量、即ち、それは各点までのユークリッド距離の総和を最小化する複素平面内の位置である、によって結合されうる。このスキームの有利点は、異常値に対する優れた抵抗力である。投票処理アプローチは、最良推定量を用い、それ以外は捨てられる。多くのロバスト推定量が統計学の文献に記載されているが、典型的な技術は、異常値を捨てうること（例えば、切り捨て平均）又は異常値の重み付けを軽減すること（例えば、ウィンザー化平均）である。効果的に、これらのツールは不適当と思われるそれらの点を除外する。
【００３２】
図１０Ａ及び１０Ｂは、数台のカメラから得られた結果の非線形混合、この場合は幾何学的中央値についての有利点を示す。単一アキュムレータ位置に関する実際の結果が示される。カメラＡ及びＢは、高いチップコンデンサの近くの点の比較的良好なサンプルを得る。カメラＣの結果は、コンデンサの側面から反射する光の多重反射によって攪乱される。プロットにおいて、ベクトルの長さ（複素値の大きさ）は、各カメラの信号強度を表し、ベクトルの向き（複素値の角度）は、各カメラについての高さ評価を表す。複素値のプロットは、カメラＡ１９１及びカメラＢ１９２についての類似の結果を示す一方、カメラＣ１９３は、非常に強いが間違った値を有している。３つの値の平均１９４又は総計を単純に取ることによって、カメラＡ及びＢの値から離れた値を得る。一つの異常値が算術平均の結果に損傷を与えうる。幾何学的中央値１９５（中央の傾向の非線形推定）は、どのような強さの一つの異常値によっても攪乱されない。
【００３３】
幾何学的中央値の別の利用は、空間フィルタとしてのものである。これまでの段落では、単一地点での数個の推定値の幾何学的中央値を取ることの記載がある。関心のある対象の周りの画素の領域の幾何学的中央値がまた、取られることも可能である。例えば、もしも３ｘ３空間フィルタが、４台のカメラを有するシステムで用いられるならば、それぞれの場所での４つの推定値及び９画素空間領域が存在する。すると、３６個の推定値の幾何学的中央値が取られるであろう。結果は、線形フィルタよりも雑音に対してロバスト（頑健）であり、かつラッピングのような問題によって影響されない。
【００３４】
一度、点群が統合されると、統合された値は、表面についての三次元情報を与えられるよう用いられうる。そのような情報は、他のものと一緒に計測及び/又は検査のために用いられうる。
【図１】
0006457072.tif 000002
【図２】
0006457072.tif 000003
【図３】
0006457072.tif 000004
【図４】
0006457072.tif 000005
【図５】
0006457072.tif 000006
【図６】
0006457072.tif 000007
【図７】
0006457072.tif 000008
【図８】
0006457072.tif 000009
【図９】
0006457072.tif 000010
【図１０Ａ】
0006457072.tif 000011
【図１０Ｂ】
0006457072.tif 000012
【図１１】
0006457072.tif 000013
【図１２】
0006457072.tif 000014