3d場景中3d對象的識別和姿態確定的製作方法

2023-09-20 08:17:20 6

專利名稱：3d場景中3d對象的識別和姿態確定的製作方法
技術領域：
本發明通常涉及機器視覺系統，更特別地，涉及3D場景中的3D對象的識別和定位。
背景技術：
3D對象識別是很多計算機視覺應用的一部分。與處理平面的強度圖像(intensity image)的基於圖像的計算機視覺相比，3D計算機視覺處理三維信息，並且對於需要檢查或操控的非平面對象和表面尤其重要。已開發了很多不同方法和傳感器，用於獲取場景的3D 表面信息。這些方法中的很多是返回所謂的深度圖像(range image)，這是一種在每一點的值表示場景表面距相機的距離的圖像。如果傳感器經過校正並且其內部參數是已知的，則深度圖像可以變換為其中每個點的X坐標、Y坐標和Z坐標是已知的3D場景。此外，可以組合來自多個傳感器的信息來得到無法表示為深度圖像的3D場景。與現有技術相反，本發明的方法能夠識別任意3D場景中任何形狀的任何形式的對象，並且無需近似姿態作為先驗信息。基於描述符或特徵的技術基於通過使用表面描述符而找到場景中的3D點與對象上的3D點之間的對應關係。表面描述符使用低維度表示方式來表示該表面上的點周圍的表面。通常，對於對象的表面上的所有點計算表面描述符並且將其存儲於資料庫中。為了識別場景中的對象，對於場景中的點計算表面描述符，並且使用預先計算出的資料庫搜索對應的對象點。一旦找出足夠的對應關係，就可以恢復對象的姿態。在 Campbell 禾口 Flynn(A Survey Of Free-Form ObjectRepresentation and Recognition Techniques，2001， Computer Vision and ImageUnderstanding, Vol.81, Issue 2， pp. 166-210(自由形式對象表示與識別技術縱覽，2001，計算機視覺和圖像理解，第81卷， 第 2 期，166 至 210 頁))，Mamic 禾口 Bennamoun(Representation and recognition of 3D free-form objects，2002，DigitalSignal Processing，Vol. 12，Issue 1，pp.47-76 (3D 自由形式對象的表示與識別，2002，數位訊號處理，第12卷，第1期，47至76頁))以及 Mian 等人(AutomaticCorrespondence for 3D Modeling :An Extensive Review, 2005, International Journalof Shape Modeling，Vol. 11，Issue 2，p. 253 (用於 3D 建模的自動對應外延評審，2005，形狀建模國際期刊，第11卷，第2期，253頁))給出了不同表面描述符的大量概述。依靠通過局部描述符進行對應關係搜索的方法具有若干缺點。首先，局部描述符無法區分對象上的各相似表面部分(例如較大的平面小塊)。這樣的相似部分產生相同或者相似的局部描述符，並且進而導致場景與對象之間的不正確的對應關係。影響半徑增大從而使得不相似的表面部分包括於描述符的構造中，這產生對該表面的丟失部分的敏感性，這對於封閉或者傳感器問題是頻繁出現的。第二，局部描述符通常太慢而無法在實時系統中實現，並且需要若干秒的處理時間。第三，局部描述符對於雜波(clutter，即不屬於感興趣的對象的場景部分)敏感。此外，局部描述符需要3D場景數據的密集表示，該密集表示通常是不可用的。最後，當前描述符對於實時應用並非足夠快。有若干方法使用所謂的幾何圖元來檢測場景中的對象。幾何圖元是一種簡單的幾何對象，例如平面、圓柱體或者球體。與自由形式的對象相比，幾何圖元由於其固有對稱性而更易於在場景中檢測出。存在若干檢測圖元或者場景中由幾何圖元構成的對象的方法。在EP-A-2 047 403中，3D對象劃分為多個幾何圖元。於是在3D場景中搜索這些幾何圖元，並且通過標識場景中的與對象中的圖元相似的圖元而識別對象。其它方法使用普通霍夫變換(Hough transform)的變型來檢測場景中的幾何圖元，例如Katsoulas (Robust extraction of vertices in rangeimages by constraining the hough transform, 2003, Lecture Notes in Computei^cience，VoU652，pp. 360-369 (通過限制霍夫變換盲提取深度圖像中的頂點，2003，計算機科學講稿，第沈51卷，360至369頁))，Rabbani和 Heuvel (Efficienthough transform for automatic detection of cylinders in point clouds，2005， Proceedings of the Ilth Annual Conference of the Advanced School for Computingand Imaging(ASCF 05)，pp. 60-65 (用於自動檢測由點雲中的圓柱體的有效霍夫變換，2005，計算和成像講習班第十一次年會公報(ASCI』 05)，60至65頁))，以及 Zaharia 禾口 Preteux(Hough transform-based 3D mesh retrieval,2001, Proceedings of the SPIE Conf. 4476on Vision Geometry X，pp. 175-185 (基於霍夫變換的 3D 網格模型檢索，2001，在視覺幾何X上的SPIE會議4476公報，175至185頁))。依靠幾何圖元的所有方法具有的缺點在於，它們對於普通自由形式對象不起作用。已開發出用於識別深度圖像中的3D對象的若干方法，例如在EP-A-I 986153中的方法。這些方法作用於由各種傳感器系統返回的單深度圖像。然而，所有基於深度圖像的系統受限於從單個深度圖像所獲取的3D信息，並且不能處理來自其它3D傳感器或來自不同深度圖像的組合的普通3D信息。此外，它們對於實時系統而言並不足夠快，原因是它們通常需要在參數空間中進行暴力搜索。已知有若干用於細化對象的已知3D姿態的方法。這些方法需要場景中對象的近似 3D姿態作為輸入，並且增加了該姿態的精度。已開發出若干這樣的方法，例如迭代最接近點 (Iterative Closest Points，見例如 Zhang (Iterative point matchingfor registration of free-form curves，1994，International Journal of Computer Vision, Vol. 7,Issue 3，pp. 119-152(用於註冊自由形式的曲線的迭代點匹配，計算機視覺國際期刊，第7卷，第三期，119至 152頁))，EP-A-2 026 279和Fitzgibbon(Robustregistration of 2D and 3D point sets,2003, Image and Vision Computing, Vol. 21,Issue 13-14, pp. 1145-1153(2D 穩健匹配和3D點集，2003，圖像和視覺計算，第21卷，第13至14期，1145至1153頁))。 姿態細化的主要缺點在於，輸入姿態需要足夠接近於正確姿態，否則各方法將無法收斂。然而，對於3D場景，正確姿態的良好近似難以獲得，因為實際應用一般包含雜波(clutter)、 封閉(occlusion)和噪聲。出於前述原因，需要一種方法，其允許高效識別任意自由形式的3D對象，並且恢復它們在普通3D場景中的3D姿態。

發明內容
本發明提供一種用於找尋3D場景中的3D對象以及以場景坐標確定對象的3D姿態的系統和方法。在典型應用中，使用例如具有兩個或更多相機的立體系統、片光(sheet of light)、飛行時間、對焦深度、或光度立體(photometric stereo)來獲取3D場景。於是， 使用所提出的方法找到對象的3D姿態。所得3D姿態用於例如以機器人來操控對象或者檢測對象表面上的誤差。所提出的方法比先前方法具有若干優點其允許識別具有任何類型表面幾何形狀的自由形式的對象，因此不受限於特定類型的對象。此外，該方法對於噪聲、丟失對象部分以及雜波是健壯的。能夠以高精度確定3D對象的姿態。找到3D對象以及恢復其3D姿態需要很少的計算時間，並且適合於實時環境。該方法包括兩個階段。在離線階段中，計算模型描述，該模型描述可以稍後用於找尋3D對象。用戶需要提供需找尋的對象的3D表示，例如3D CAD模型或3D點集合。該方法僅需要對象的幾何形狀，而不需要顏色、紋理或表面反射信息，使得本發明適合於廣泛的對象類型。可以提供另外的局部信息(例如顏色和紋理)以進一步增加該方法的健壯性。 通過以特定速率來採樣對象的表面，從採樣的表面計算用於每一對點的描述符，並且將點對存儲在由所述點對描述符進行索引的資料庫中，從而構建模型描述。於在線階段中用戶提供3D場景，且在離線階段中計算出的模型描述。以特定速率對場景的表面進行採樣。這些場景點的子集用作基準點。對於每一基準點，對象的3D姿態相對於該基準點而被參數化，計算出基準點與所有其它場景點之間的點對描述符並且在離線階段中所創建的資料庫中對其進行搜索，並且返回資料庫中具有最多匹配的3D姿態。於是關於一致性而檢查從所有基準點恢復的3D姿態，並且使用在所有一致的3D姿態上的平均姿態。最後，可以使用任何用於姿態細化的方法來改進找到的姿態。根據第一方面，本發明提供一種用於識別3D場景數據中3D對象的實例以及用於確定所述實例的3D姿態的方法，該方法包括以下步驟(a)提供3D場景數據；(b)從所述 3D場景數據中選擇至少一個基準點；(c)對於每一選中的基準點，在所述基準點是所述3D 對象的一部分的假設下，計算所述3D對象的候選姿態；(d)從所述候選姿態計算過濾後的姿態的集合。步驟(a)中的3D場景數據優選被提供作為3D點的集合或3D計算機輔助設計模型。優選地，在步驟(a)之前從3D對象計算3D模型，且該3D模型用於步驟(b)、(c)、 (d)中，包括以下步驟(ml)提供所述3D對象的3D對象數據；(π )從所述3D對象數據創建用於3D對象識別和姿態確定的3D模型。優選地提供步驟(ml)中的3D場景數據作為3D 點集合或者作為3D計算機輔助設計模型。根據優選實施例，步驟(m2)包括(m2a)從所述 3D對象數據中選擇至少兩個採樣點；(m2b)計算點對描述符，所述點對描述符對於每一對選中的採樣點描述這兩個點及其關係；(m2c)創建存儲由所述點對描述符索引的點對的全局模型描述。更優選地，步驟(m2c)包括(m2d)對點對描述符進行採樣；(m2e)創建將每一採樣後的點對描述符映射到點對的列表的全局模型描述，其中，每一列表包含具有相同的經採樣的點對描述符的所有成對的選中的採樣點。優選地，在處理之前過濾3D對象數據和/或3D場景數據，包括以下步驟中的至少一個檢測並且去除離群值；減少噪聲；計算表面法線。所述點對描述符優選包含以下項中的至少一個兩個點的距離、兩個點的兩條法線之間的角度以及兩個點的法線中的每一條與兩個點之間的差矢量之間的兩個角度。
根據另一優選實施例，在步驟(b)中，基準點是從所述3D場景數據中隨機選擇的， 或者是通過對3D場景數據均勻採樣而隨機選擇的。優選地，相對於3D對象的大小來計算 3D場景數據的均勻採樣的採樣距離。更優選地，在步驟(C)中，對於每一候選姿態計算得分值。優選地，使用投票方案計算候選姿態。投票方案優選地包括以下步驟(Cl)對可能的對象姿態的空間進行採樣； (c2)關於步驟(cl)的每一姿態空間採樣創建計數；(d)從所述3D場景數據中選擇場景點的集合。(c4)對於每一選中的場景點計算姿態，使得選中的場景點和基準點皆在所述3D 對象的表面上；(c5)對於在步驟(c4)中計算的每一姿態，增加用於相應姿態空間採樣的計數；以及(c6)檢測所採樣的姿態空間中的峰值計數值，並且選擇相應的姿態空間採樣作為候選姿態。在步驟(c6)中，峰值計數值的檢測受限於超過閾值的計數值。在步驟(cl) 中，可能的對象姿態的空間優選由兩個參數表示，其中，第一參數是3D對象上的點，第二參數是描述繞著表面法線進行的旋轉的角度。3D對象上的點優選地表示為對於從3D對象數據中選擇的點集合的索引，旋轉角度是通過將角度的集合劃分為相等大小的間隔而被採樣的。點集合優選地通過對3D對象的表面進行均勻採樣而選自3D對象數據。更優選地，在步驟(c4)中，使用允許搜索與成對基準點和選中的場景點相似的3D 對象上的點對的數據結構，從而計算姿態。搜索點對優選地包括步驟(c4a)計算描述所述兩個點及其關係的點對描述符；(c4b)使用所述點對描述符作為對於數據結構的索引。所述點對描述符優選地包含以下項中的至少一個兩個點的距離；兩個點的兩條法線之間的角度；兩個點的法線中的每一條與兩個點之間的差矢量之間的兩個角度；在每一點處的顏色或者灰度值；在每一點處的紋理信息；在每一點處的表面描述符；在每一點處的曲率；在每一點處的其它幾何表面信息。點對描述符包含兩個點的距離、兩個點的兩條法線之間的角度以及兩個點的法線中的每一條與兩個點之間的差矢量之間的兩個角度。根據優選實施例，步驟(c4b)包括(c4c)對點對描述符進行採樣；(c4d)使用將經採樣的點對描述符映射到點對列表的數據結構。在步驟(c4d)中，優選使用散列表作為數據結構。根據優選實施例，步驟(d)中的計算包括(dl)限定在候選姿態之間的鄰居關係； (d2)計算每一姿態的得分，作為鄰居候選姿態的得分的加權和；(們)通過根據(業)中計算的得分對姿態進行排序，選擇過濾後的姿態的集合。優選地，所述鄰居關係是通過以下方式限定的設定姿態的變換與姿態的旋轉的差的閾值，或者設定在兩個姿態之下3D對象上的點可具有的最大距離的閾值。所述方法還包括步驟將在(們)中選擇的姿態重新計算作為鄰居姿態上的平均姿態。加權優選地取決於候選姿態和當前鄰居姿態。本發明的方法優選地還包括步驟通過優化在所述姿態下基於3D場景與3D對象之間的距離的誤差函數，從而細化過濾後姿態的集合中的每一姿態。本發明的方法優選地還包括步驟對於過濾後姿態的集合中的每一姿態計算得分，其中，所述得分描述在所述姿態下3D場景與3D對象之間的一致性。本發明的方法優選還包括步驟對於最終姿態中的每一個計算得分。計算出的得分優選為在計算出的姿態下位於3D對象表面上的3D場景中的點的數量。


結合附圖，根據以下詳細描述將更充分地理解本發明，其中圖1示出如何通過均勻採樣來調整3D數據；圖2示出可以如何描述兩個3D點之間的關係；圖3示出如何創建描述全局特性的全局模型描述；圖4是離線階段(即模型生成)的流程圖；圖5是在線階段(即匹配階段)的流程圖；圖6使用局部坐標示出對象坐標系、局部坐標系與場景坐標系之間的變換。
具體實施例方式說明和定義所有以下數據應當以電子(優選為數字)形式可得。所描述的方法和算法被看作電子形式並且是以計算機實現的。在以下記法中，3D點是具有三個坐標值的3D空間中的點。每一 3D點參考一坐標系，其中，最著名的坐標系是定義了 3D場景數據的場景坐標系，以及定義了感興趣的3D對象的對象坐標系。3D矢量是具有三個坐標值的3D空間中的矢量。在表面上的點處的3D法線矢量是具有為1的歐幾裡得長度並且在給定點處垂直於該表面的3D矢量。3D點雲是3D 點的集合。定向的3D點雲是其中3D法線矢量與每一點關聯的3D點雲。3D剛性變換是3D 點至3D點的映射，該映射保留點距離，形式上為映射f，使得對於任何點P、Q，方程IP-Ql =
f(P)-f(Q)成立。每個3D剛性變換可以分解為旋轉和平移，其中，首先對輻角點進行旋轉，並且對結果應用平移。形式上，每個3D剛性變換可以分解為3D旋轉R和3D矢量T，使得 f (P) = R(P) +T03D數據調整是將3D中的表面變換為在所述表面上均勻分布的3D點集合的方法， 如圖1所示。在優選實施例中，3D數據調整是取以下項作為輸入的方法(a)描述3D中的 2D表面的3D數據(101)，以及(b)採樣距離d;其輸出具有以下特性的3D點的集合(102) (a)其僅包括同樣處於輸入的3D數據的表面上的點，(b)所得點雲中的所有成對點可具有至少為d的距離，(c)輸入的3D數據中的每個點在輸出集合中具有距離至多為d的點。在本發明優選實施例中，通過在輸入點集合上進行迭代，並且使每一個輸入點僅當在輸出雲中不存在相比採樣距離更接近該新的點的點時添加到輸出集合中，從而對於3D點集合產生具有期望特性的調整後的點集合。通過將每個面採樣為點集合併且如上所述處理所得到的點，從而變換3D CAD模型。在一可替選實施例中，通過從表面隨機選擇點來調整3D數據。在另一可替選實施例中，法線方向用於調整，其中，子採樣點集合在高曲率區域中更密集。在優選實施例中，計算出從3D數據的表面選出的各點的表面法線(103)。調整輸入點雲通常產生具有更少的點的雲，該具有更少的點的雲仍然良好表示原始的雲。在離線階段和在線階段中，本發明使用調整，用於高效減小點的數量，產生更快的性能。如下所述，對局部參數空間的採樣也很重要。在優選實施例中，採樣距離d以與對象的直徑相關的項而被參數化，其中，直徑是3D對象上兩個點之間的最大距離。設D。w是對象的直徑，則採樣距離d通過^而被參數化為d= TdD。bj。在一可替選實施例中，由用戶給出採樣因子。在另一可替選實施例中，採樣因子是根據例如3D數據的噪聲級別的先驗信息而設置的。
點對(point pair)描述符是值的列表，描述成對3D點。在優選實施例中，這些值包括兩個點之間的距離、兩條法線之間的角度、第一法線與兩個點的差矢量之間的角度以及第二法線與兩個點的差矢量之間的角度。在一可替選實施例中，點對描述符中可以包括局部特徵(例如在兩個點處的表面的顏色、在兩個點處的曲率以及其它集合特徵)以及背景技術部分中所述的局部點描述符(例如旋轉圖像、點斑以及其它)。通常，在不脫離本發明範圍的情況下，前面所述的值的任何子集可以用作描述符。將更多信息添加到點對描述符中會增加其區分不同的成對點的能力，但也增加其複雜度進而增加其計算、存儲的複雜度以及處理描述符的複雜度。在優選實施例中，分別具有法線Ii1和n2的兩個3D點P1和P2的點對描述符F的形式定義如圖2所示，(I)F (P1, P2, Ii1, n2) = (| P2-P11 , Z (n1 n2), Z (IiijP2-P1)jZ (n2, P2-P1))其中，Z (a,b)表示兩個矢量之間的角度。在文獻中描述了相似的特徵，例如Wahl 等人(Surflet-pair-relation histograms :A statistical 3d-shape representation forrapid classification,2003, Proceedings Fourth International Conference on 3-DDigital Imaging and Modeling 2003 (3DIM 2003)，pp. 474-481 (Surflet 對關係直方圖用於快速分類的統計3D形狀表示，2003，3D數字成像和建模第四次國際會議公報 2003 (3DIM 2003)，474至481頁))，他構建了基於點對描述符的直方圖的3D對象的標識系統。對於法線方位未知(即，僅已知方向)的情況，上述角度在；90° ]中被歸一化， 並且對於矢量的取反是不變的。採樣後的點對描述符是點對描述符的經採樣版本。在優選實施例中，以相等大小的間隔對點對描述符的四個項採樣，以產生採樣後的點對描述符。採樣後的點對描述符的形式定義如下設na是關於角度值的間隔的數量，並且da = 360° /na。設d是上述距離採樣因子，並且設是小於χ的最大整數值，則點對特徵F(PpPyrvn2) = (F1, F2, F3, F4)的採樣版本Fs (P1, P2, H1, n2)定義為(2) FsCPl,P2,n,,n2) = (L^1 /dj,Lf2 /da]L^3 /da」,Lf4 /da])全局模型描述是一種允許高效搜索與來自場景的給定的點對相似的對象上的所有點對的數據結構。因此，其為將來自場景的點對作為輸入並且輸出與輸入點對相似的對象上的點對的列表的數據結構或方法。在優選實施例中，從採樣後的點對描述符到點對集合的映射用作點對描述符。通過計算用於給定點對的採樣後的點對描述符，並且使用散列映射來獲取具有相等的經採樣點對描述符的所有點對，從而完成查找。散列表允許高效地訪問相似的點對，其中，時序獨立於模型描述中存儲的點對的數量。在一可替選實施例中， 用於最接近鄰居訪問(nearestneighbor access)的方法可以用於獲取與給定點對之一相似的具有點對描述符的所有點對。在另一替換實施例中，任意索引方案可以用作數據結構， 例如搜索樹。圖3概述全局模型描述選擇來自表面(301)的點對(302)，並且計算點對描述符(303)。使用點對描述符(30 來索引全局模型描述(304)，並且返回與點對(302)具有相似特性的在3D對象(307)的表面上的點對(308)的集合。場景中的對象的局部姿態定義為場景中對象的、相對於給定場景點(稱為基準點)的3D姿態，其中假設給定基準點位於對象的表面上。這種假設限制了可能的姿態。因此，局部姿態具有比完全3D姿態更少的自由度。在優選實施例中，如下使用局部坐標來對局部姿態進行參數化設\是被假設為位於對象表面上的場景中的基準點，則(a)nv是與\ 對應的模型表面上的點，並且(b) α是在對準^、mr以及它們的法線之後繞著\的法線旋轉的角度(圖6)。局部坐標相對於&寫作Ov α)，並且具有總共三個自由度，兩個用於模型表面上的HV的位置，一個用於旋轉角度a。在一可替選實施例中，可以使用對象的表面的不同參數化，例如U-V-坐標或紋理坐標。對於場景的基準點h設是將\平移到原點並且將\的法線旋轉到χ軸上 (指向正方向)的剛性3D變換。對於模型點m,，設是將m,平移到原點並且將m,的法線旋轉到Χ軸上(指向正方向)的剛性3D變換。設Rx(Ci)是以角度α繞著χ軸旋轉的剛性3D變換。那麼，給定關於基準點、的局部坐標(m,，α )，從模型空間中的點Hii到場景空間中的其對應點Si的映射可以寫作(3) ^T-lLRx{a)TM\Lmi如果SpmpTs^和Tm^已知，則對於α可以求解上述方程。3D模型創建在該方法的離線階段，通過適合於後續在場景中識別感興趣對象的方式構建描述該感興趣對象的模型。用於創建模型的方法包括以下步驟，如圖4所示(a)任選地，準備 3D對象數據；(b)對象採樣點的選擇；(c)全局模型描述的創建；(d)任選地，用於姿態細化的準備。在優選實施例中，所創建的模型會包括選中的採樣點和全局模型描述。在一可替選實施例中，可以包括以下信息原始3D對象數據；用於姿態細化而計算出的數據；該方法的用戶所需的附加信息。3D對象數據的準備這一步驟用於通過去除不期望的特徵並且添加期望的特徵來準備輸入3D數據。在優選實施例中，包括以下步驟(al)任選地抑制來自數據的期望的特徵(例如3D傳感器所產生的噪聲和離群值)，其中，所使用的確切方法還取決於用於獲取數據的傳感器；(a2)計算表面法線，如果表面法線已經可用，則這是任選的。在優選實施例中，3D對象數據作為3D點集合或者計算機輔助設計模型(CAD模型)的形式給出。在一可替選實施例中，可以使用代數表面。在另一可替選實施例中，可以使用3D表面的任何其它表示。需要從3D對象數據中選擇對象採樣點集合，用於創建全局模型描述。在優選實施例中，使用上述3D數據調整方法來對3D對象數據進行子採樣，以創建稀疏採樣點集合。在一可替選實施例中，用戶可以提供將用作採樣點的點集合。在另一可替選實施例中，來自3D 對象數據的所有點可以用作對象採樣點。在又一可替選實施例中，來自對象的點的隨機子集可以用作採樣點。在其它可替選實施例中，在不脫離本發明範圍的情況下，其它對象採樣點選擇策略是可能的。用於創建全局模型描述的方法取決於關於全局模型描述而選擇的具體數據結構。 在優選實施例中，創建全局模型描述包括(Cl)根據對象採樣點的集合關於每一成對點計算點對描述符；(^)通過使用計算出的點對描述符作為索引，存儲全局模型描述中的每一對採樣點。在一可替選實施例中，點可以存儲在數據結構中，從而對於相似點對的高效查找不需點對描述符。如果在匹配處理中會使用任選的姿態細化，並且如果選中的用於姿態細化的方法需要可以根據3D對象預先計算出的某種數據，則該數據也可以在離線階段計算，並且與模型一起存儲。在優選實施例中，計算出允許快速搜索最接近於給定搜索點的對象上的點的數據結構。該數據結構後續用於針對姿態細化的迭代最接近點(Iterative Closest Points, ICP)方法。在一可替選實施例中，可以使用任何其它姿態細化方法的數據結構，例如期望最大化(expectation maximization, EM) (Granger 禾口 Pennec (Multi-scale EM-ICP A fast and robust approach forsurface registration,2002, European Conference on Computer Vision (ECCV 2002)，pp. 418-432) (Granger 和 Pennec (通用換算 EM-ICP 用於表面拼接的計算機快速和穩健接近，2002，歐洲計算機視覺會議(ECCV 200 ，418至432 頁))。對象識別和姿態確定該方法的在線階段識別3D場景中的3D對象的實例，並且計算該場景中的所述實例的3D姿態。其將離線階段中計算出的3D場景和3D模型作為輸入，並且輸出場景中該對象的3D姿態集合，並且任選地輸出對姿態進行排序的得分的集合。如圖5所示，在線階段包括以下步驟(a) 3D場景數據的準備；(b)基準點的選擇；(c)假設基準點處於感興趣的對象上，計算最佳地描述對象位置的關於每一基準點的局部坐標的集合；(d)過濾所得姿態以形成最終姿態，(e)任選的姿態細化；以及(f)任選地，對最終姿態評分。3D場景數據的準備這一步驟用於通過去除不期望的特徵並且添加期望的特徵來準備輸入3D數據。在優選實施例中，準備輸入3D數據包括以下步驟(al)任選地抑制來自數據的不期望的特徵(例如3D傳感器所產生的噪聲和離群值)，其中，所使用的確切方法還取決於用於獲取數據的傳感器；(a2)計算表面法線，如果表面法線已經可用，則這是任選的；(a!3)將各點均勻分布在場景點雲中，以避免偏向場景的更密集採樣的部分(例如對於基於投影的測距掃描儀而言更接近掃描儀的部分)。在優選實施例中，用於步驟(a3)的採樣距離設置為等於或大於離線階段中用於調整模型點雲的採樣距離，並且等於或大於用於創建經採樣的點對描述符的採樣距離。改變採樣距離產生具有不同數量的點的經調整的點雲，這樣隨後影響本發明方法的運行時間和精度，其因此成為用於平衡二者的重要參數。 在一可替選實施例中，採樣距離可以由用戶給出。在另一可替選實施例中，可以通過例如3D 數據的噪聲級別的先驗信息來計算採樣距離。在優選實施例中，3D場景數據作為3D點集合給出，或以計算機輔助設計模型(CAD 模型)的形式給出。在在一可替選施例中，可以使用代數表面。在另一可替選實施例中，可以使用3D表面的任何其它表示。多個基準點選自3D場景數據，並且用在後續步驟中。為了該方法得以運作，重要的是，選擇位於感興趣的對象的表面上的至少一個基準點，原因是僅當基準點中的至少一個滿足條件時後續步驟找到對象姿態。在優選實施例中，通過從場景點雲中取出隨機的點子集來選擇基準點，其中，該子集中的點的數量相對於場景點雲的大小而被參數化。在一可替選實施例中，來自均勻分布的場景點集合或原始3D場景數據的所有點可以用作基準點。 在另一可替選實施例中，用戶提供的關於對象的可能位置的知識、關於模型的表面特徵的知識、場景點雲的調整或其它方法可以用於掌控基準點的選擇。在不脫離本發明範圍的情況下，它們可以容易地用在本發明中。選中的基準點的數量直接影響本發明方法的運行時間。基準點選擇方法因此需要在選擇過多基準點(導致較差的性能)與過少基準點(其中丟失感興趣的對象的機率增加)之間做出平衡。
對於在前一步驟中選擇的每一基準點，在基準點處於感興趣對象的表面上的假設下，計算與感興趣對象最可能具有的3D姿態對應的局部坐標的集合。在優選實施例中，採用與普通霍夫變換(Hough transform)相似的投票方案，其計算最佳說明所觀測到的數據的局部坐標。在一可替選實施例中，可能有優化局部坐標的若干其它方式，包括但不限於窮舉搜索和能量函數的數值最小化。在優選實施例中，使用相似於普通霍夫變換(Hough transform)的用於計算對象的局部坐標的投票方案。投票方案包括以下步驟(Cl)參數空間(在此為局部坐標的空間)被劃分為採樣集合，並且每一採樣附有計數器並且計數器初始被設置為零；(W)對於場景雲中的每一點，確定通過模型形成對該點的說明的所有局部坐標，意味著當使用這些局部坐標對對象進行變換時，當前場景點和當前基準點皆位於對象的表面上；(d)對於說明該點的每一局部坐標，包含該局部坐標的相應參數空間採樣的計數增加；(c4)在通過步驟(U)和(c!3)處理所有場景點之後，用於局部坐標空間的每一採樣的計數會與說明該部分參數空間的場景點的數量對應。其計數具有最大值的採樣對應於以最佳方式說明場景點的局部坐標。在最後的步驟中，選擇具有最大計數值的採樣或其計數超過閾值的採樣集合。 投票方案的若干可替選實施例是可能的，包括但不限於在步驟(^)中，不使用所有場景點而僅使用場景點的子集；在步驟(c!3)中，以取決於當前場景點的權重的值增加計數；在步驟(c4)中，使用直方圖分析來分析峰值的投票空間。在優選實施例中，如下完成步驟(Cl)中的參數空間的劃分通過選自3D對象數據的採樣點之一描述局部坐標的第一分量(即描述模型表面上的位置的分量)，並且第一分量因此隱式地劃分為離散值。通過將可能的旋轉角的間隔；360° ]分為相等大小的 na個間隔(相似於上述對採樣後的點對描述符的角度值的採樣)，劃分第二分量(即描述繞著基準點的法線旋轉的角度的分量)。在一可替選實施例中，第一分量的劃分可以通過以 U-V-坐標或紋理坐標來表示第一分量並且對這些坐標進行採樣來完成。在步驟(c2)中說明當前場景點的局部坐標的計算如下完成(c2. 1)如上所述計算基準點與當前場景點之間的點對描述符並且對其採樣；(c2. 2)經採樣的點對描述符用於訪問在離線階段計算出的全局模型描述，其將返回具有與場景點對相似的距離和方位的模型點對的列表；(c2. 3)對於每一這種模型點對，使用場景點對和模型點對使用方程(3) 來計算局部坐標。在一可替選實施例中，全局模型描述可以基於最接近的鄰居，比如在不對點對描述符採樣的情況下允許搜索相似點對的數據結構。在另一替選實施例中，可以使用在不需要點對描述符的情況下允許直接搜索相似點對的數據結構。在處理所有場景點之後，步驟(c4)選擇其中相應計數具有最大值的參數空間的採樣。在優選實施例中，選擇具有最大值(即全局最大值)的計數。在一可替選實施例中， 可以使用具有超過特定閾值的計數值的所有採樣，其中，閾值可以是固定的，或者可以取決於所有計數的最大值。在另一可替選實施例中，可以使用用於檢測計數空間中的局部峰值而不是全局閾值的方法。從每一選中的採樣取出一個局部坐標，並且局部坐標被變換為完全3D姿態，其中的每一個返回有對應局部坐標採樣的計數值。該計數值是所述3D姿態的得分。姿態過濾是一種從一個或多個基準點將候選姿態(任選地增添有得分值)作為輸入，並且輸出按姿態正確的似然率排序的僅包含感興趣對象的最有可能的姿態的經過濾姿態的集合的方法。通常，姿態集合可以包含零個、一個或多個姿態。姿態過濾用於不同目的(1)離群值去除假設基準點位於感興趣對象的表面上，計算基準點的候選姿態。 如果該假設不正確，例如對於場景中的不屬於感興趣對象雜波點，或者如果基準點的法線不正確，則該基準點的所得候選姿態將包含不與對象的正確姿態對應的不正確姿態。姿態過濾應該去除這樣的不正確的姿態。(2)增加精度和穩定性如果若干基準點處於對象的表面上，則關於它們中的每一個的候選姿態將包含與對象的正確姿態對應的姿態。然而，由於計算中的數值誤差、數據中的噪聲，並且由於上述機制中涉及的採樣步長，因此姿態將與正確姿態稍有不同。姿態過濾對關於不同基準點找到的所有正確姿態分組，並且計算平均姿態，因此增加了最終結果的精度和穩定性。在優選實施例中，姿態過濾包括以下步驟(dl)定義姿態之間的鄰居關係，其中， 如果姿態的旋轉部分差異小於固定閾值，並且如果它們的平移矢量的差具有小於固定閾值的長度，則姿態被定義為鄰居；(d2)將新的得分分配給每一姿態，該新的得分為((dl)中所定義的)鄰居姿態的所有得分的和；(們)按新的得分對姿態進行排序；(d4)選擇具有最佳得分的姿態；(肪)通過對鄰居姿態進行平均來任選地重新計算選中的姿態。在一可替選實施例中，通過規定來自模型的點在兩個姿態下可能具有的最大差來定義步驟(dl)中的姿態的鄰居關係，例如=1^yICv— L在步驟(d2)的的一可替選實施例中，將得分計算為鄰居姿態的得分的加權和，其中，加權函數取決於兩個姿態。在(dl)的另一可替選實施例中， 所有姿態被看作鄰居，並且如所描述的那樣使用加權函數。此外，沒有姿態可以被看作步驟 (dl)中的鄰居，有效地導致從投票方案選擇具有最高單個得分的姿態。在一可替選實施例中，聚類方法(例如k均值或均值轉移)可以用於選擇最終姿態集合。在步驟(肪)的優選實施例中，通過計算姿態的平移矢量的均值來對平移進行平均化，並且通過計算姿態的旋轉的平均Rodriguez矢量來對旋轉進行平均化。在步驟(肪)的一可替選實施例中，旋轉可以包括在計算平均旋轉之前選中的姿態的旋轉的反轉。這樣增加了均值旋轉的穩定性。在步驟(肪)的另一可替選實施例中，通過優化取決於姿態和平均姿態的得分函數來計算平均旋轉。在可替選實施例中，若干其它方法是可能的，用於在不脫離本發明範圍的情況下實現上述目的中的一個或多個。姿態細化描述了一類方法，該類方法將3D對象模型、3D場景和場景中模型的近似姿態作為輸入，並且輸出模型的細化的、更精確的姿態。姿態細化方法通常通過使誤差函數最小化來優化場景與對象之間的對應性。姿態細化的缺點在於，初始近似姿態需是已知的， 並且足夠好以足以讓該方法收斂。如上所述的本發明計算對象的近似姿態，該姿態足夠好以足以使用姿態細化進行細化。姿態細化的使用是任選的，並且取決於本發明的用戶所需的精度。所提方法的所得姿態通常足夠精確以足以進行對象操控，例如抓握。然而，使用本發明進行表面檢查的應用(例如檢測未正確生產的部分)可能需要姿態細化步驟。在優選實施例中，使用迭代最接近點(ICP)進行姿態細化。對於ICP，場景中的各點與對象表面之間的距離的總和被最小化。在一可替選實施例中，可以使用期望最大化進行姿態細化。在另一可替選實施例中，可以使用任何使場景點與對象之間的距離最小化的方法。在其它可替選實施例中，在不脫離本發明範圍的情況下，若干用於細化近似姿態的其它方法也是可能的。評分是這樣一種方法，該方法將在算法中計算出的最終姿態以及3D場景數據和 3D對象數據作為輸入，並且輸出描述所計算出的姿態的質量或者在所述姿態下場景與對象之間的一致性的一個或多個值。其中，最終姿態的質量和精度取決於場景中感興趣的對象的存在以及可視性，並且取決於場景數據和模型數據的質量。需要評分來向該方法的用戶提供估計所得姿態的方式，其為後續判斷的基礎。可能有若干用於對最終姿態進行評分的可替選實施例，包括但不限於(a)返回以投票方案計算出的姿態的得分；(b)返回姿態過濾步驟中計算出的累積得分；(C)給定所得姿態，計算位於模型表面上的場景點的數量；(d)計算場景點與在所得姿態下接近於模型的場景點的模型表面之間的距離的協方差；(e)將模型投影到用於獲取場景數據的深度傳感器的圖像，並且在圖像域中計算模型與場景點之間的距離；(f) (e)的方法，但具有附加的、從多於一個視點驗證所投影的模型點的可視性的步驟，如對於立體方法所要求的那樣；(g)計算模型表面點的法線與對應場景表面點之間的點積的和；(h)給定所得姿態，計算可見模型表面與總模型表面的比率，或可見模型表面與在傳感器相機中可見的模型表面之間的比率；(i)使用從(a)到(g)的方法中的兩種或更多種，並且組合所得值。在不脫離本發明範圍的情況下，取決於用戶需求和傳感器特性，可以由計算得分的其它方式。在優選實施例中，如果不使用姿態細化，則返回如方法(b)中計算出的、在姿態過濾步驟中計算出的得分；如果使用姿態細化，則返回方法(C)、(d)、(e)或(f)的得分。雖然已經在附圖和前面的描述中詳細說明並且描述了本發明，但這種說明和描述應認為是說明性或示例性的，而並非限制性的。應理解，在所附權利要求的範圍內，本領域技術人員可以進行改變和修改。特別地，本發明涵蓋其它具有來自以上以及以下描述的不同實施例的各特徵的任何組合的實施例。此外，在權利要求中，詞語「包括」並不排除其它元件或步驟，並且數量詞「一個」並非排除多個。單一單元可以實現權利要求中記載的若干特徵的功能。與屬性或值結合的術語「基本上」、「大約」、「近似」等也特別地分別確切定義屬性或確切地定義值。權利要求中的任意標號不應理解為對範圍進行限制。
權利要求
1.一種用於識別3D場景數據中3D對象的實例並且用於確定所述實例的3D姿態的方法，包括以下步驟(a)提供3D場景數據；(b)從所述3D場景數據中選擇至少一個基準點；(c)對於每一選中的基準點，在所述基準點是所述3D對象的一部分的假設下，計算所述3D對象的候選姿態；(d)從所述候選姿態計算過濾後的姿態的集合。
2.如權利要求1所述的方法，其中，在步驟(a)之前從3D對象計算3D模型，並且該3D 模型用在步驟(b)、(c)、(d)中，包括以下步驟(ml)提供所述3D對象的3D對象數據；(m2)從所述3D對象數據創建用於3D對象識別和姿態確定的3D模型。
3.如權利要求2所述的方法，其中，步驟(m2)包括 (m2a)從所述3D對象數據中選擇至少兩個採樣點；(m2b)計算點對描述符，對於每一對選中的採樣點，點對描述符描述這兩個點及其關係；(m2c)創建全局模型描述，該全局模型描述存儲由所述點對描述符索引的點對。
4.如權利要求3所述的方法，其中，步驟(m2c)包括 (m2d)對點對描述符進行採樣；(m2e)創建將每一採樣後的點對描述符映射到點對列表的全局模型描述，其中，每一列表包含具有相同的經採樣點對描述符的所有成對的選中的採樣點。
5.如權利要求1所述的方法，其中，在步驟(b)中，所述基準點是從所述3D場景數據中隨機選擇的或者通過對所述3D場景數據均勻採樣而隨機選擇的。
6.如權利要求1所述的方法，其中，在步驟(c)中，對於每個候選姿態計算得分值。
7.如權利要求6所述的方法，其中，使用投票方案計算所述候選姿態。
8.如權利要求7的方法，其中，所述投票方案包括以下步驟 (cl)對可能的對象姿態的空間進行採樣；(c2)關於步驟(cl)的每一姿態空間採樣創建計數； (c3)從所述3D場景數據中選擇場景點的集合。(c4)對於每一選中的場景點計算匹配姿態，使得選中的場景點和基準點皆在所述3D 對象的表面上；(c5)對於在步驟(c4)中計算的每一姿態，增加相應姿態空間採樣的計數； (c6)檢測經採樣的姿態空間中的峰值計數器值，並且選擇相應姿態空間採樣作為候選姿態。
9.如權利要求8所述的方法，其中，在步驟(cl)中，可能的對象姿態的空間由兩個參數表示，其中，第一參數是所述3D對象上的點，第二參數是描述繞著表面法線旋轉的角度。
10.如權利要求9所述的方法，其中，在所述3D對象上的點被表示為對於從所述3D對象數據中選擇的點集合的索引，旋轉角度是通過將角度的集合劃分為相等大小的間隔而被採樣的。
11.如權利要求8所述的方法，其中，在步驟(c4)中，使用允許搜索與成對基準點和選中的場景點相似的3D對象上的點對的數據結構，計算匹配姿態。
12.如權利要求11所述的方法，其中，搜索點對包括步驟 (c4a)計算描述所述兩個點及其關係的點對描述符； (c4b)使用所述點對描述符作為對所述數據結構的索引。
13.如權利要求12所述的方法，其中，步驟(c4b)包括 (c4c)對所述點對描述符進行採樣；(c4d)使用將採樣後的點對描述符映射到點對的列表的數據結構。
14.如權利要求13所述的方法，其中，在步驟(c4d)中，散列表用作數據結構。
15.如權利要求7所述的方法，其中，在步驟(d)中，所述計算包括 (dl)限定各候選姿態之間的鄰居關係；(d2)計算每一姿態的得分，作為鄰居候選姿態的得分的加權和；(d3)通過根據對在(業)中計算的得分對姿態進行排序，選擇過濾後的姿態的集合。
16.如權利要求15所述的方法，其中，所述鄰居關係是通過以下方式限定的設定所述姿態的變換和所述姿態的旋轉的差的閾值，或者設定所述3D對象上的點在兩個姿態下具有的最大距離的閾值。
17.如權利要求15的方法，還包括步驟重新計算在(d3)中選擇的姿態作為鄰居姿態上的平均姿態。
18.如權利要求1所述的方法，還包括步驟通過優化在所述姿態下基於所述3D場景與所述3D對象之間的距離的誤差函數，細化過濾後姿態的集合中的每一姿態。
19.如權利要求1所述的方法，還包括步驟對於過濾後姿態的集合中的每一姿態計算得分，其中，所述得分描述在所述姿態下所述3D場景與所述3D對象之間的一致性。
全文摘要
本發明涉及3D場景中3D對象的識別和姿態確定。本發明提供一種方法，用於識別3D場景數據中3D對象的實例，並且確定所述實例的3D姿態，該方法包括以下步驟(a)提供3D場景數據；(b)從3D場景數據中選擇至少一個基準點；(c)對於每一選中的基準點，在所述基準點是所述3D對象的一部分的假設下，計算所述3D對象的候選姿態；以及(d)根據所述候選姿態計算過濾後的姿態的集合。
文檔編號G06T17/00GK102236794SQ20101029283
公開日2011年11月9日 申請日期2010年9月25日 優先權日2010年5月7日
發明者伯特倫·海因裡希·德羅斯特, 馬庫斯·烏爾裡希 申請人:Mv科技軟體有限責任公司