林文珍 黃 惠

(中國科學(xué)院深圳先進(jìn)技術(shù)研究院 深圳 518055)

三維點(diǎn)云中的二維標(biāo)記檢測

林文珍 黃 惠

(中國科學(xué)院深圳先進(jìn)技術(shù)研究院 深圳 518055)

特征檢測在物體識別、數(shù)據(jù)配準(zhǔn)等應(yīng)用中具有至關(guān)重要的作用。同一場景中不同采集數(shù)據(jù)的配準(zhǔn)和融合，必須已知或者估算不同數(shù)據(jù)中的共同特征對應(yīng)點(diǎn)。然而，許多場景缺少有效對應(yīng)特征點(diǎn)。解決該問題的一種有效的方法是在場景中添加標(biāo)記以增加特征。文章提出一種在只含有位置信息的三維點(diǎn)云中自動檢測二維標(biāo)記的方法。該方法首先在三維場景添加黑色圓形薄紙片作為二維標(biāo)記，利用區(qū)域增長法將獲取的三維場景的點(diǎn)云數(shù)據(jù)分割成不同類別，然后基于隨機(jī)抽樣一致性算法的擴(kuò)展方法依次對分割后的點(diǎn)云進(jìn)行形狀擬合，最后通過檢測形狀檢測該二維標(biāo)記。該方法能夠有效地檢測出三維場景中的二維標(biāo)記，并避免了遮擋、形變等問題，為缺少特征的場景提供了簡單可行的特征，可廣泛應(yīng)用于數(shù)據(jù)配準(zhǔn)、物體識別、物體追蹤、三維重建等領(lǐng)域。

點(diǎn)云分割；隨機(jī)抽樣一致性；擬合；二維形狀檢測

1 引 言

1.1 特征檢測背景

特征檢測在計(jì)算機(jī)圖形圖像領(lǐng)域有著至關(guān)重要的地位，廣泛應(yīng)用于圖像配準(zhǔn)、物體識別、物體跟蹤等領(lǐng)域。一般來說，特征點(diǎn)需具備以下屬性[1]：

(1)再現(xiàn)性：物體相同部位的特征點(diǎn)能夠在不同的觀察條件下被檢測出，例如物體的平面旋轉(zhuǎn)；

(2)獨(dú)特性：檢測出的特征點(diǎn)能夠很好地區(qū)分不同的物體；

(3)局部性：特征應(yīng)該是局部的，以降低閉塞的概率，并允許不同觀察條件下得到的不同數(shù)據(jù)之間的幾何變形的簡單模型估計(jì)；

(4)數(shù)量大：特征點(diǎn)的數(shù)量應(yīng)該足夠大，能提供足夠的被檢測物信息用于匹配或者識別；

(5)準(zhǔn)確性：檢測出的特征點(diǎn)應(yīng)該能夠準(zhǔn)確地體現(xiàn)出被檢測物的形狀，以及物體在場景中的位置等信息；

(6)有效性：針對實(shí)時應(yīng)用，特征點(diǎn)檢測算法應(yīng)該能夠在有效的時間范圍內(nèi)進(jìn)行。

現(xiàn)階段大多數(shù)特征檢測算法難以同時滿足上述條件，使得后續(xù)的物體配準(zhǔn)和識別的難度增大。例如，欲進(jìn)行數(shù)據(jù)采集的場景的面積遠(yuǎn)遠(yuǎn)超出采集設(shè)備的視角；或者薄板(如桌面)的上下兩面并沒有有效的重疊部分，難以配準(zhǔn)。

雖然研究者已經(jīng)提出許多針對特定應(yīng)用場景的解決方案，但是，由于存在場景特征檢測難和場景本身缺少特征[1]等問題，特征檢測依然面臨很大的挑戰(zhàn)。Martin[2]指出，利用人工設(shè)置簡單標(biāo)記可以有效解決此類問題。

人工標(biāo)記一般可以分成兩類：(1)在已獲取的數(shù)據(jù)中手動標(biāo)定出特征。用這種方式標(biāo)記出的特征，其正確率往往受主觀因素影響，并且隨著數(shù)據(jù)數(shù)量增加，人工工作量也會大幅度增加。(2)在真實(shí)場景中添加二維或三維物體作為標(biāo)記[2]。由于可以大幅度減少人工工作量，并且能夠直接在三維空間中進(jìn)行操作，這種方法得到了快速的發(fā)展。然而，這類方法比較依賴于標(biāo)記的檢測過程，如果檢測失敗，則可能使得后續(xù)的工作無效。

在真實(shí)場景中放置的標(biāo)記可以是三維或二維物體。其中，三維標(biāo)記由于易造成對場景本身信息的遮擋，產(chǎn)生較大的數(shù)據(jù)缺失。相比之下，二維標(biāo)記的特性穩(wěn)定，對場景本身的影響較小。但是，二維標(biāo)記的設(shè)計(jì)和檢測比三維標(biāo)記困難，因?yàn)樵谌S空間中的二維物體是平面的，在采集數(shù)據(jù)中易被忽略，使得其幾何特征難以檢測[3]。

本文提出一種在三維點(diǎn)云中自動檢測二維標(biāo)記的方法。首先，在三維場景添加二維標(biāo)記，利用區(qū)域生長法將獲取的三維場景的點(diǎn)云數(shù)據(jù)分割成不同類別；然后，基于隨機(jī)抽樣一致性(Random Sample Consensus，RANSAC)的擴(kuò)展方法依次對分割后的點(diǎn)云進(jìn)行形狀擬合；最后，通過檢測形狀檢測該二維標(biāo)記。

1.2 二維標(biāo)記檢測的相關(guān)工作

1.2.1 點(diǎn)云分割

理論上，不同分割方法的區(qū)別主要是測量給定點(diǎn)集相似度，并以此決定分類的方法和標(biāo)準(zhǔn)不同。一旦確定了相似度測量方法，就可以通過測量將相似度在特定閾值內(nèi)的點(diǎn)分為一組。分割算法主要有基于邊緣的、基于曲面的和基于掃描線的三種。

基于邊緣的分割方法主要分成兩步：邊緣檢測以及對邊界內(nèi)的點(diǎn)分組。在給定的深度圖中，邊緣被定義為局部表面屬性的變化超出給定閾值的那些點(diǎn)。局部表面屬性一般使用曲面法向、梯度、主曲率或高階導(dǎo)數(shù)表示。Bhanu 等[4]提出使用邊代替曲面，處理深度圖。Sappa 等[5]的方法基于邊緣檢測策略進(jìn)行曲面圖的快速分割。Wani等[6]針對可重構(gòu)的多環(huán)網(wǎng)提出了一種基于邊緣區(qū)域的平行分割算法。這些方法都是一些經(jīng)典的基于邊緣的分割算法。

基于曲面的分割方法使用局部曲面屬性作為一種相似度測量方法，合并空間位置鄰近且具有相似曲面屬性的點(diǎn)。分割途徑主要有自底向上和自頂向下兩種。其中，自底向上的分割原理是從種子點(diǎn)開始，依據(jù)給定的相似準(zhǔn)則擴(kuò)展區(qū)域，最終的分割結(jié)果取決于種子點(diǎn)的選擇；自頂向下的方法則一開始將所有點(diǎn)分配到同一組，并逐步為每個點(diǎn)擬合一個曲面單元。Parvin 等[7]的曲面分割方法使用分裂與合并的方式將曲面圖分割為諸多平面。同樣的問題，Xiang 等[8]則使用分裂-合并的聚類進(jìn)行分割。然而對于曲面，只要選擇的用于擬合該曲面的質(zhì)量因子高于指定的閾值，則可分割該區(qū)域。這樣的分割方法對數(shù)據(jù)中的噪聲不敏感，比基于邊緣的分割算法性能更好，但同時可能有很大的誤差。

第三種基于掃描線的分割方法，主要針對深度圖。該分割方法認(rèn)為深度圖的每一行是一條掃描線，在分割的第一階段獨(dú)立處理每一條掃描線。Jiang 等[9]提出一種基于掃描線分組的分割方法，對深度圖提取平面段。Natonek[10]和 Khalifa等[11]基于此又提出了改進(jìn)的方法，使用不同方向上的配置文件分割激光掃描數(shù)據(jù)。

上述這些方法雖各有優(yōu)點(diǎn)，但應(yīng)用于散亂點(diǎn)云時，存在以下問題：

(1)很多方法只針對平面，在實(shí)際場景中的應(yīng)用有限。

(2)盡管基于主曲率的方法可以處理有曲對象，但是從散亂點(diǎn)云中估計(jì)的曲率不可靠，這會導(dǎo)致嚴(yán)重的過分割。尤其是圓環(huán)和球體，很容易出現(xiàn)過分割。Trucco[12]分析了從深度數(shù)據(jù)中估計(jì)的曲率靈敏度，提議至少不應(yīng)該使用主曲率進(jìn)行深度數(shù)據(jù)的平面分割。

(3)很多分割方法需要設(shè)置大量的參數(shù)，而這些參數(shù)對于最終分割的意義和作用并不明朗。一般需使用獨(dú)立的迭代優(yōu)化方式進(jìn)行大量的結(jié)果比較，來確定參數(shù)的最佳值。

(4)還有有一些方法，如 Marshall 等[13]提出的分割方法，在分割的同時識別表面類型。但是，該方法不適用于本文的先分割再識別的檢測流程。

1.2.2 形狀檢測

形狀檢測是計(jì)算機(jī)幾何相關(guān)領(lǐng)域的常見問題。目前已有很多算法解決這個問題，在此簡短地介紹幾種重要的形狀檢測算法。

在計(jì)算機(jī)視覺中，兩個廣為人知的形狀提取方法是 RANSAC 和霍夫(Hough)變換。兩者都可以成功地應(yīng)用于檢測二維和三維形狀，甚至對噪聲點(diǎn)比例高的輸入數(shù)據(jù)也是可靠的。但是其效率低、時間和空間開銷大[14]。

Hough 變換利用點(diǎn)與線的對偶性，使用曲線表達(dá)式，將給定的曲線從原始圖像空間變換到參數(shù)空間。這樣就把原始圖像中的曲線檢測問題轉(zhuǎn)化為尋找參數(shù)空間中的峰值問題，也即把整體特性的檢測問題轉(zhuǎn)化為局部特性的檢測問題。在這種情況下，參數(shù)空間的參數(shù)量越大，模型越準(zhǔn)確。Illingorth 等[15]和 Xu 等[16]提出的 Hough 變換算法主要應(yīng)用于二維區(qū)域。Vosselman 等[17]利用 Hough 變換從三維數(shù)據(jù)集中提取平面，但參數(shù)量小，模型不夠準(zhǔn)確。

另一種在視覺領(lǐng)域中經(jīng)常使用的方法是Mediont 等[18]的張量決策體系。該體系能夠從極其混亂的場景中成功檢測幾何表面，方法具有魯棒性。但是由于無固有模型，所以不能用來檢測有預(yù)定義類型的原始模型。

Cohen-steiner 等[19]提出一種使用平面擬合進(jìn)行曲面估計(jì)的變形系統(tǒng)。Wu 等[20]使用一些更復(fù)雜的形狀擬合，擴(kuò)展了該系統(tǒng)。他們的目的不僅是提取出某個形狀，還要找到一個能夠表示原型的最優(yōu)模型。這些方法需要點(diǎn)的連接信息，且由于只使用最小二乘擬合，變形結(jié)果容易受噪聲點(diǎn)影響而產(chǎn)生錯誤。

除此之外，在計(jì)算機(jī)圖形學(xué)領(lǐng)域，針對點(diǎn)云的混合渲染，Wahl 等[21]提出一種基于 RANSAC的平面檢測方法。類似的方法也被 Hofer[23]提出，他使用從幾何線元對表面分類的矩陣特征值，進(jìn)行平面檢測。另外有人使用基于 RANSAC的分割算法進(jìn)行點(diǎn)云的形狀檢測，這些方法并沒有對 RANSAC 框架進(jìn)行優(yōu)化或者擴(kuò)展，主要對包含的點(diǎn)和形狀少的模型有效。

1.3 二維標(biāo)記檢測的方法概述

為了設(shè)計(jì)一種通用的解決方案，我們在此只利用物體的三維幾何數(shù)據(jù)，而不受顏色、紋理的影響。在沒有顏色信息輔助下，二維標(biāo)記在三維數(shù)據(jù)中很難檢測。根據(jù)三維激光掃描儀對黑色、反光表面等不敏感，很難捕捉到數(shù)據(jù)點(diǎn)這一特性，我們采用黑色或者反光表面材質(zhì)制成的二維標(biāo)記。具體而言，本文使用一張黑色的圓形薄紙片作為二維標(biāo)記。由激光掃描儀 Mantis 獲取的三維點(diǎn)云數(shù)據(jù)顯示，該二維標(biāo)記的形狀為空心圓。本文僅使用物體的三維幾何信息，因此二維標(biāo)記的檢測問題就轉(zhuǎn)化為二維形狀的檢測問題。根據(jù)本文二維標(biāo)記在點(diǎn)云中的分布特點(diǎn)，即：空心圓的內(nèi)部無數(shù)據(jù)或極少數(shù)據(jù)，而圓外數(shù)據(jù)分布密集，提取該標(biāo)記的邊緣點(diǎn)并檢測圓環(huán)，即可得到該標(biāo)記。

本文提出了可在三維點(diǎn)云中有效檢測二維形狀的方法，步驟如下：

(1)在場景中添加二維標(biāo)記；

(2)對點(diǎn)云數(shù)據(jù)進(jìn)行預(yù)處理；

(3)根據(jù)點(diǎn)云數(shù)據(jù)，將數(shù)據(jù)分割為不同段；

(4)利用擴(kuò)展 RANSAC 算法檢測二維標(biāo)記。在檢測過程中，先檢測標(biāo)記所在的數(shù)據(jù)段，再提取該段的邊緣，最后檢測圓環(huán)，即得二維標(biāo)記。

2 二維標(biāo)記檢測的技術(shù)實(shí)現(xiàn)

2.1 檢測概述

本文旨在為場景提供清晰的辨識，主要為了解決場景缺少特征或者特征難以檢測的情況。利用在真實(shí)場景中放置二維標(biāo)記作為標(biāo)記特征，提出一種在三維點(diǎn)云中檢測二維標(biāo)記形狀的方法。根據(jù)本文的數(shù)據(jù)特點(diǎn)，檢測過程中，首先對點(diǎn)云利用區(qū)域生長法進(jìn)行分割，提取出平面邊緣；然后利用擴(kuò)展的 RANSAC 進(jìn)行檢測。具體流程如圖 1 所示。

圖 1 二維標(biāo)記檢測流程Fig. 1 Detection process of 2D marker

(1)點(diǎn)云預(yù)處理

本文使用激光掃描儀 Mantis，其采集的點(diǎn)云數(shù)據(jù)量大，且包含大量噪聲，因此需要進(jìn)行點(diǎn)云的下采樣、去噪等預(yù)處理工作。為了簡單有效地進(jìn)行后續(xù)步驟，本文采用均勻下采樣以及距離統(tǒng)計(jì)去噪音法來進(jìn)行點(diǎn)云的預(yù)處理工作。

(2)點(diǎn)云分割

利用區(qū)域生長法對預(yù)處理之后的數(shù)據(jù)進(jìn)行點(diǎn)云分割。首先使用 k-d 樹進(jìn)行k近鄰搜索，估計(jì)點(diǎn)云法向。再計(jì)算曲率和法向夾角，判斷其值是否在給定的閾值范圍內(nèi)，以此進(jìn)行區(qū)域生長的段分割。

(3)二維形狀檢測

對基于區(qū)域生長分割得到的各段點(diǎn)集使用擴(kuò)展的 RANSAC 進(jìn)行二維形狀檢測。在檢測形狀前，需要先估計(jì)二維形狀(本文主要涉及平面和圓環(huán)，根據(jù)實(shí)際二維標(biāo)記形狀，也可以使用橢圓或其他形狀)。由于基于 RANSAC 分割的分割算法比較適合點(diǎn)和形狀少的模型，所以檢測二維標(biāo)記圓之前需要先檢測出標(biāo)記所在的平面，然后使用主成分分析算法(Principal Component Analysis，PCA)提取該平面的邊緣輪廓，在此邊緣點(diǎn)上檢測圓環(huán)，即可檢測出二維標(biāo)記。

2.2 技術(shù)細(xì)節(jié)

2.2.1 預(yù)處理

(1)下采樣

一個場景的點(diǎn)云數(shù)據(jù)量通常都很大，這也為后續(xù)的計(jì)算機(jī)的計(jì)算空間以及時間帶來了巨大的負(fù)擔(dān)。為了加快計(jì)算速度，以及減少計(jì)算機(jī)內(nèi)存占有，一般對原始的點(diǎn)云數(shù)據(jù)進(jìn)行下采樣。為保證輸入數(shù)據(jù)的相對密度和形狀不變，本文采用均勻下采樣算法。

對輸入的散亂點(diǎn)云中的每個點(diǎn)，在其鄰域內(nèi)搜索k近鄰點(diǎn)，去除這些鄰近點(diǎn)以實(shí)現(xiàn)均勻下采樣。該方法的關(guān)鍵在于，如何確定查找k近鄰時的搜索范圍，以及盡可能最小化該搜索范圍，以節(jié)約時間，提高效率。

一種有效的用于查找搜索范圍和最近鄰搜索的方法是劃分空間，即對空間點(diǎn)云數(shù)據(jù)建立 k-d樹。k-d 樹是一種對k維空間中的實(shí)例點(diǎn)進(jìn)行存儲，以便對其進(jìn)行快速檢索的二叉樹結(jié)構(gòu)。本文使用三維 k-d 樹處理點(diǎn)云。k-d 樹沿垂直于相應(yīng)地軸線的超平面把空間劃分為不同的子空間，將所有非葉子節(jié)點(diǎn)分割到特定維。

在 k-d 樹中為每個點(diǎn)進(jìn)行k近鄰搜索，找到k個最近的點(diǎn)并去除。即每k個點(diǎn)中只保留一個點(diǎn)，數(shù)據(jù)量縮小為原始數(shù)據(jù)的 1/k倍。

(2)去噪

激光掃描通常得到不同點(diǎn)密度的點(diǎn)云數(shù)據(jù)集，且測量誤差產(chǎn)生的稀疏噪聲點(diǎn)會嚴(yán)重干擾結(jié)果。這種對復(fù)雜的局部點(diǎn)云特性(如表面法線或曲率的變化)的估計(jì)容易產(chǎn)生錯誤，進(jìn)而導(dǎo)致無法很好地生成點(diǎn)云。一種行之有效的解決方法是通過對鄰近點(diǎn)進(jìn)行統(tǒng)計(jì)，利用統(tǒng)計(jì)信息舍棄不符合標(biāo)準(zhǔn)的點(diǎn)。

本文采用基于輸入點(diǎn)云與鄰點(diǎn)間距離的分布計(jì)算的方法進(jìn)行點(diǎn)云去噪。使用k近鄰搜索鄰點(diǎn)，k為設(shè)定值。對每一個點(diǎn)，計(jì)算該點(diǎn)到其所有鄰點(diǎn)的平均距離和標(biāo)準(zhǔn)差。假定點(diǎn)云符合一個給定平均值α和標(biāo)準(zhǔn)差σ的高斯分布。根據(jù)高斯分布的特性，平均值和標(biāo)準(zhǔn)差由所有點(diǎn)的全局平均距離決定。如果一個點(diǎn)到所有鄰點(diǎn)的平均距離和標(biāo)準(zhǔn)差分別超過了α和σ，則被視為噪聲點(diǎn)。

2.2.2 點(diǎn)云分割

點(diǎn)云的自動分割為后續(xù)物體的識別與檢測提供了基礎(chǔ)。本文使用一種基于法線平滑度約束的區(qū)域生長算法來分割預(yù)處理后的點(diǎn)云。該算法比較各點(diǎn)的法線之間的夾角，將在平滑度約束范圍內(nèi)足夠接近的點(diǎn)合并為一段。該算法需要先估計(jì)每個點(diǎn)的法線和曲率，再基于區(qū)域生長進(jìn)行分割。

(1)法線和曲率的估計(jì)

法線的估計(jì)需要對每個點(diǎn)的鄰點(diǎn)擬合一個平面并計(jì)算該點(diǎn)的曲率。該平面的法線即該點(diǎn)的法線，則點(diǎn)的法線估計(jì)轉(zhuǎn)化為對該點(diǎn)的鄰域擬合所得平面的法線估計(jì)。估計(jì)平面法線過程需對該點(diǎn)進(jìn)行k近鄰搜索，得到鄰點(diǎn)的協(xié)方差矩陣，再使用 PCA 計(jì)算該矩陣的特征向量和特征值。對每個三維坐標(biāo)點(diǎn) ，其協(xié)方差矩陣如式(1):

其中，k是點(diǎn)pi鄰域內(nèi)的鄰點(diǎn)數(shù)；表示鄰點(diǎn)的中心；λj為協(xié)方差矩陣的第j個特征值；vj即特征向量。

一般地，由于沒有數(shù)學(xué)方法確定法線的符號問題，PCA 估計(jì)的法線，其朝向是不確定的，導(dǎo)致整個數(shù)據(jù)集的朝向也是不連續(xù)的。如果視點(diǎn)vp是實(shí)際已知的，為了保證所有的法線ni連續(xù)地朝向視點(diǎn)，法線需滿足如下公式：

(2)區(qū)域生長

基于區(qū)域生長的分割算法是使用上一步得到的點(diǎn)的法線和曲率。根據(jù)設(shè)定的參數(shù)，按照平滑度約束來分段，并通過以下兩個因素避免過擬合：

①局部連通性：被分割在同一個段的點(diǎn)是局部連通的。這一約束通過在區(qū)域生長過程使用k近鄰查找鄰點(diǎn)得以保證。

②曲面平滑度：被分割在同一段的點(diǎn)在局部曲面上應(yīng)盡可能平滑，這可以通過點(diǎn)的法線與該曲面上其他點(diǎn)的法線的差別來進(jìn)行判斷。用閾值θth和曲率閾值Cth判斷某一段的點(diǎn)是否滿足平滑條件。

首先對各點(diǎn)的曲率值進(jìn)行排序。區(qū)域的生長過程是從具有最小曲率值的點(diǎn)開始(具有最小曲率的點(diǎn)處在平面的平坦區(qū))。在有序點(diǎn)云中，算法可以不斷挑選曲率值最小的點(diǎn)加入段區(qū)域中，直到點(diǎn)云中沒有可加入到該段的點(diǎn)為止，具體過程如下：

(A)挑選點(diǎn)加入到集合，即種子集；

(B)對于每一個種子點(diǎn)，搜索其鄰域點(diǎn)。

(a)對當(dāng)前種子點(diǎn)的每一個鄰點(diǎn)，計(jì)算其與當(dāng)前種子點(diǎn)的法線的夾角，如果夾角小于閾值θth，則將該點(diǎn)加入到種子集；

(b)檢測當(dāng)前種子點(diǎn)的每一個鄰點(diǎn)的曲率值，如果曲率小于閾值Cth，則該鄰點(diǎn)加入種子集；

(c)將當(dāng)前種子點(diǎn)從種子集中移除。

(C)重復(fù)第(B)步，直到種子集為空，則表示一個區(qū)域已經(jīng)生長完畢。

(D)重復(fù)上述步驟，直到?jīng)]有點(diǎn)需要被劃分區(qū)域，則所有區(qū)域生長完畢，不同的區(qū)域即為分割的不同段。

分割結(jié)果如圖 2(a)所示，分割得到的不同類塊用不同的顏色表示。

2.2.3 二維形狀檢測

(1)形狀估計(jì)

如前所述，本文需要檢測的形狀有平面和圓環(huán)，下面介紹如何在三維空間用參數(shù)估計(jì)這些形狀。

①平面

在未考慮點(diǎn)的法線時，最小點(diǎn)集 {p1,p2,p3}即可確定一個平面。為了保證生成的平面的合理性，引入三點(diǎn)的法線N1、N2和N3。如果三點(diǎn)的法線偏差小于設(shè)定的閾值α，則將該平面加入候選平面集。

②圓環(huán)

理論上需要 3 個點(diǎn)來計(jì)算出圓環(huán)的圓心坐標(biāo)、法線和半徑。這里，我們用 4 個點(diǎn)及其法線來估計(jì)圓環(huán)。由兩點(diǎn)可確定一條直線pi＋λni[4]，則四個點(diǎn)可確定兩條交叉直線，并可計(jì)算出垂直于直線所在平面的旋轉(zhuǎn)軸。4 點(diǎn)構(gòu)成兩條直線時有幾種不同情況，并得到兩個不同的旋轉(zhuǎn)軸，我們選擇誤差最小的軸作為旋轉(zhuǎn)軸。為了得到較小的半徑，需先找到繞旋轉(zhuǎn)軸旋轉(zhuǎn)的平面，然后用這個平面上的三個點(diǎn)計(jì)算圓環(huán)以及圓環(huán)上所有點(diǎn)的中心，該中心到旋轉(zhuǎn)軸的距離即為圓環(huán)的主半徑。

圖 2 二維標(biāo)記檢測各部分結(jié)果Fig. 2 Some results of 2D marker detection

(2)邊緣檢測

如形狀檢測流程，在分割段中找到二維標(biāo)記所在的平面(即最大的平面)后，由于圓環(huán)的特性和使用 RANSAC 在檢測形狀中的局限性，需要在檢測標(biāo)記圓環(huán)之前先提取出圓環(huán)所在平面的邊緣。

現(xiàn)階段有大量的算法可以有效地提取出點(diǎn)云的邊緣。由于本文涉及的二維標(biāo)記在點(diǎn)云中為空心圓(其圓形輪廓內(nèi)沒有點(diǎn)，而圓本身是由點(diǎn)包圍)，所以 PCA 算法可以有效地提取出空心圓的邊緣。

邊緣提取過程與 2.2.2 中法線和曲率估計(jì)過程類似：找到每個點(diǎn)的鄰域，對鄰點(diǎn)得到的協(xié)方差矩陣計(jì)算特征向量及特征值，如公式(1)(2)。根據(jù)上述分析，利用 PCA 算法提取邊緣，計(jì)算出特征值后，利用大特征值與小特征值的比值，進(jìn)行邊緣點(diǎn)的檢測(比值大于給定閾值β，則該點(diǎn)是邊緣點(diǎn))。邊緣點(diǎn)集合即描述了整個點(diǎn)云數(shù)據(jù)的邊緣輪廓，結(jié)果如圖 2(c)所示。

(3)RANSAC

RANSAC 是根據(jù)一組包含噪聲數(shù)據(jù)的樣本數(shù)據(jù)集，通過迭代方式計(jì)算出數(shù)據(jù)的數(shù)學(xué)模型參數(shù)，得到有效樣本數(shù)據(jù)的算法[23]。這種方法伴隨著大量的隨機(jī)過程，需要進(jìn)行多次隨機(jī)運(yùn)算才能得到最優(yōu)的結(jié)果。

①算法描述

RANSAC 基于以下假設(shè)而提出：

(a)數(shù)據(jù)由“局內(nèi)點(diǎn)”組成；

(b)“局外點(diǎn)”不能很好地適應(yīng)需擬合的模型；

(c)除此之外的數(shù)據(jù)均屬于噪聲。

算法的輸入是一組觀測數(shù)據(jù)，觀測數(shù)據(jù)的參數(shù)化模型，以及一些參數(shù)。RANSAC 通過反復(fù)選擇數(shù)據(jù)中的一組隨機(jī)子集來達(dá)成目標(biāo)。被選取的子集即為假設(shè)的局內(nèi)點(diǎn)，并用下述方法進(jìn)行驗(yàn)證：

(a)有一個模型適應(yīng)于假設(shè)的局內(nèi)點(diǎn)，即所有的未知參數(shù)都能從假設(shè)的局內(nèi)點(diǎn)計(jì)算得出；

(b)用(a)中得到的模型去測試所有的其他數(shù)據(jù)，如果某個點(diǎn)適用于估計(jì)的模型，認(rèn)為它也是局內(nèi)點(diǎn)；

(c)如果有足夠多的點(diǎn)被歸類為假設(shè)的局內(nèi)點(diǎn)，那么估計(jì)的模型就足夠合理；

(d)用所有假設(shè)的局內(nèi)點(diǎn)去重新估計(jì)模型，因?yàn)樗鼉H僅被初始的假設(shè)局內(nèi)點(diǎn)估計(jì)過；

(e)通過估計(jì)局內(nèi)點(diǎn)與模型的錯誤率來評估模型。

這個過程被重復(fù)執(zhí)行固定的次數(shù)，算法偽代碼如下(從點(diǎn)云P中檢測并提取形狀)：

RANSAC 的核心就是隨機(jī)性和假設(shè)性。加入隨機(jī)性可以減少計(jì)算量，設(shè)置循環(huán)次數(shù)是為了多次計(jì)算并選擇出最準(zhǔn)確的擬合模型；假設(shè)性，即認(rèn)為隨機(jī)抽出來的數(shù)據(jù)都是正確的。并以此進(jìn)行計(jì)算，獲得其他滿足變換關(guān)系的點(diǎn)，然后利用投票機(jī)制，選出獲票最多的一個進(jìn)行變換。

②模型參數(shù)

我們需要根據(jù)特定的問題和數(shù)據(jù)集通過實(shí)驗(yàn)來確定參數(shù)τ和d，迭代次數(shù)k可以根據(jù)理論結(jié)果設(shè)定。當(dāng)我們估計(jì)模型參數(shù)時，用ρ表示迭代過程中，從數(shù)據(jù)集內(nèi)隨機(jī)選取出的點(diǎn)均為局內(nèi)點(diǎn)的概率。隨機(jī)點(diǎn)生成的結(jié)果模型不一定都有用，因此ρ也表征了算法產(chǎn)生的結(jié)果成為有用模型的概率。

對(4)式兩邊分別取對數(shù)，得到

值得注意的是，這個結(jié)果假設(shè)n個點(diǎn)都是獨(dú)立選擇的，即某個點(diǎn)被選定之后，它可能會被后續(xù)的迭代過程重復(fù)選到，因此這種方法通常是不合理的。由于算法迭代次數(shù)k在很大程度上決定了模型的正確率，因此，為了得到更可信的參數(shù)，定義k的標(biāo)準(zhǔn)偏差為

③優(yōu)缺點(diǎn)分析

RANSAC 的優(yōu)點(diǎn)是它能魯棒地估計(jì)出模型參數(shù)。例如，從包含大量局外點(diǎn)的數(shù)據(jù)集中估計(jì)出高精度的參數(shù)。其缺點(diǎn)是計(jì)算參數(shù)的迭代次數(shù)沒有上限，如果設(shè)置迭代次數(shù)的上限，得到的結(jié)果可能不是最優(yōu)的結(jié)果，甚至可能是錯誤的結(jié)果。所以 RANSAC 只有一定的概率得到可信的模型，且概率與迭代次數(shù)成正比。RANSAC 的另一個缺點(diǎn)是它要求設(shè)置與擬合模型相關(guān)的閥值。更重要的是 RANSAC 只能從特定的數(shù)據(jù)集中估計(jì)出一個模型，如果存在兩個(或多個)模型，RANSAC 只能估計(jì)出其中的一個模型，而忽略掉其他。

④檢測二維標(biāo)記

根據(jù) RANSAC 的上述特性和場景特點(diǎn)，本文在使用 RANSAC 算法進(jìn)行形狀檢測的過程中還加入了點(diǎn)云分割和邊緣提取。本文的形狀提取涉及的形狀主要是平面和圓環(huán)。在進(jìn)行平面檢測時，我們使用的方法是先進(jìn)行點(diǎn)云分割成段(見2.2.2)，在各個段內(nèi)分別做 RANSAC 平面檢測，這樣有效地避免了由于 RANSAC 的隨機(jī)擬合造成的誤差。對于檢測圓環(huán)過程，先使用 PCA 提取點(diǎn)云邊緣(見 2.2.3)，再利用 RANSAC 檢測圓環(huán)。整個檢測過程如圖(2)所示。

3 實(shí)驗(yàn)結(jié)果

本文以一個簡單的場景為例(標(biāo)記圓半徑為1.5)，展示檢測二維標(biāo)記的每一步執(zhí)行的結(jié)果(見圖 2)。其中，圖 2(a)為點(diǎn)云分割結(jié)果，不同顏色表示不同分割段。(b)顯示從(a)中提取出標(biāo)記所在的平面。(c)中綠色點(diǎn)為從(b)提取的邊緣，從(c)中檢測出代表標(biāo)記的圓環(huán)，如(d)中紅色點(diǎn)所示。

實(shí)驗(yàn)證明，本文提出的方法可以從三維點(diǎn)云中有效地檢測出二維標(biāo)記。相比之下，如果直接使用 RANSAC 算法進(jìn)行本文的二維標(biāo)記檢測，則可能因標(biāo)記圓半徑較小而無法檢測出圓環(huán)。且對于半徑足夠大的圓，由于 RANSAC 算法的正確率具有一定的概率，難以保證檢測的正確率。如圖 3 所示，(a)中紅色點(diǎn)顯示本文方法檢測出的標(biāo)記圓。而直接使用 RANSAC 無法檢測出本文所示大小的標(biāo)記圓，且標(biāo)記圓半徑越小，檢測難度越大；(b)為直接采用 RANSAC，檢測半徑為增大一倍的圓形標(biāo)記的結(jié)果。從結(jié)果可以看出，本文的標(biāo)記檢測方法有效地避免了RANSAC 的弱點(diǎn)，相對于傳統(tǒng)形狀檢測方法，增強(qiáng)了魯棒性，能夠更加有效地檢測出二維標(biāo)記圓。

圖 3 不同算法檢測標(biāo)記圓的結(jié)果對比Fig. 3 Comparing the results of different algorithms to detect markers circle

4 討 論

本文針對缺少特征的場景，提出了一種在三維場景中自主添加二維標(biāo)記，并基于點(diǎn)云分割和邊緣提取的過程，從三維點(diǎn)云中檢測該二維標(biāo)記的方法。實(shí)驗(yàn)證明，該方法能夠有效地檢測出二維標(biāo)記，而且檢測出的二維標(biāo)記有效減少了物體對原場景的影響，為下一步場景配準(zhǔn)、以及識別等提供了關(guān)鍵基礎(chǔ)。

本文提出的標(biāo)記檢測方法在檢測過程中也存在一定的局限性。以圖 2 為例，文中使用的圓形標(biāo)記比其他形狀更容易檢測，但是由于圓形的對稱和旋轉(zhuǎn)不變的特性，在配準(zhǔn)和物體識別等過程中，并不能為場景的辨識提供清楚的方向。另外，本文的 PCA 提取邊緣僅使用了點(diǎn)的位置信息，利用空心圓邊緣的一側(cè)有鄰點(diǎn)，而另一側(cè)鄰點(diǎn)極少這一特點(diǎn)進(jìn)行邊緣提取，這種方法簡單但不夠準(zhǔn)確。對于法向變化明顯但空間位置連續(xù)的不同曲面，難以檢測其邊緣。另一方面，掃描誤差造成的局部點(diǎn)云缺失，會導(dǎo)致邊緣提取錯誤，進(jìn)而對后面的標(biāo)記形狀檢測造成困擾。此外，標(biāo)記圓的半徑越小，檢測難度越高。

鑒于以上缺陷，在未來的工作中，我們將嘗試更多不同形狀的二維標(biāo)記，使得特征更加鮮明且方向性更強(qiáng)，以便利用局部對應(yīng)點(diǎn)或關(guān)鍵點(diǎn)搜索。另一方面，使用更加魯棒的算法提取點(diǎn)云邊緣，以降低邊緣檢測中產(chǎn)生的檢測誤差。改進(jìn)后的方法的魯棒性、適用性更強(qiáng)，可廣泛應(yīng)用于檢測、物體識別和數(shù)據(jù)配準(zhǔn)等。

[1] Tinne T, Krystian M. Local invariant feature detectors: a survey [J]. Foundations and Trends in Computer Graphics and Vision 2007, 3(3): 177-280.

[2] Martin H. Marker detection for augmented reality applications [R]. ICG-TR-08/05, Graz: Graz University of Technology, 2008.

[3] Robert AM, John H, David JH, et al. A comparison of 2D-3D intensity-based registration and featurebased registration for neurointerventions [C] // Medical Image Computing and Computer-Assisted Intervention, 2002, 2489: 517-524.

[4] Bhanu B, Lee S, Ho CC, et al. Range data processing: representation of surfaces by edges [C] // Proceedings of the Eighth International Conference on Pattern Recognition, 1986: 236-238.

[5] Sappa AD, Devy M. Fast range image segmentation by an edge detection strategy [C] // Third International Conference on 3-D Digital Imaging and Modeling, 2001: 292-299.

[6] Wani MA, Arabnia HR. Parallel edge-region-based segmentation algorithm targeted at reconfigurable multiring network [J]. Journal of Supercomputing, 2003, 25(1): 43-62.

[7] Parvin B, Medioni G. Segmentation of range images into planar surfaces by split and merge [C] // Conference on Computer Vision and Pattern Recognition, 1986: 415-417.

[8] Xiang RH, Wang RS. Range image segmentation based on split-merge clustering [C] // Proceedings of the 17th International Conference on Pattern Recognition,2004,3:614-617.

[9] Jiang XY, Meier U, Bunke H. Fast range image segmentation using high-level segmentation primitives [C] // Proceedings of the 3rd IEEE Workshop on Applications of Computer Vision, 1996: 83-88.

[10] Natonek E. Fast range image segmentation for servicing robots [C] // IEEE International Conference on Robotics and Automation, 1998, 1: 406-411.

[11] Khalifa I, Moussa M, Kamel M. Range image segmentation using local approximation of scan lines with application to CAD model acquisition [J]. Machine Vision Applications, 2003, 13(5-6): 263-274.

[12] Trucco E, Fisher RB. Experiments in curvaturebased segmentation of range data [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(2): 177-182.

[13] Marshall AD, Luk′acs G, Martin RR. Robust segmentation of primitives from range data in the presence of geometric degeneracy [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(3): 304-314.

[14] Illingworth J, Kittler J. A survey of the hough transform [J]. Computer Vision, Graphics, and Image Processing, 1988, 44(1): 87-116.

[15] Illingorth J, Kittler J. The adaptive hough transform [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987, 9(5): 690-698.

[16] Xu L, Oja E. Randomized hough transform (RHT): basic mechanisms, algorithms, and computational complexities [J]. CVGIP: Image Understanding, 1993, 57(2): 131-154.

[17] Vosselman G, Gorte BGH, Sithole G, et al. Recognising structure in laser scanner point clouds [J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2004, 36: 33-38.

[18] Mediont G, Lee MS, Tang CK. Computational Framework for Segmentation and Grouping [M]. New York: Elsevier Science Incorporated, 2000.

[19] Cohen-steiner D, Alliez P, Desbrun M. Variational shape approximation [J]. ACM Transactions on Graphics, 2004, 23(3): 905-914.

[20] Wu JH, Kobbelt L. Structure recovery via hybrid variational surface approximation [J]. Computer Graphics Forum, 2005, 24(3): 277-284.

[21] Wahl R, Guthe M, Klein R. Identifying planes in point-clouds for efficient hybrid rendering [C] // The 13th Pacific Conference on Computer Graphics and Applications, 2005: 1-8.

[22] Hofer M, Odehnal B, Pottmann H, et al. 3D shape recognition and reconstruction based on line element geometry [C] // Proceedings of the Tenth IEEE International Conference on Computer Vision, 2005, 2: 1532-1538.

[23] RANSAC [OL]. [2014-01-30]. http://en.wikipedia. org/wiki/RANSAC.

Two Dimensional Marker Detection in Three Dimensional Point Cloud

LIN Wenzhen HUANG Hui

(Shenzhen Institutes of Advanced Technology,Chinese Academy of Sciences,Shenzhen518055,China)

Feature detection plays an important role in object detection and registration. For data registration, correspondences of different frames in the same scene should be found firstly. However, in many cases, there are not effective correspondences, which leads to incorrect registration. One of the effective solutions is to add marker manually in the scene. A method for detecting 2D marker (a black circle drew on paper for scene, hollow circular for point cloud) automatically in 3D point cloud (3D position information only) was proposed. First of all, add a 2D marker in real scene, and divide data set of 3D scene into segments by using region-growing segmentation. Then for each segment, detect 2D marker by extended RANSAC doing shape fitting. By this method, the 2D marker in 3D point cloud could be effectively detected without deforming or changing object. It provides simple and available features for the scene that is lack of features, laying a good foundation for next steps.

segmentation; random sample consensus; shape fitting; 2D shape detection

TP 301

A

2015-01-31

：2015-03-09

林文珍(通訊作者)，碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)，E-mail：wz.lin@siat.ac.cn；黃惠，博士，研究員，研究方向?yàn)橛?jì)算機(jī)圖形、圖像處理和科學(xué)計(jì)算。