一種基于RANSAC框架的橢球提取算法

程志全， 葉永凱， 李 寶

（國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073）

將數(shù)據(jù)采集設(shè)備獲取的實(shí)物樣件數(shù)據(jù)進(jìn)行處理和三維重構(gòu)，反求工程在計(jì)算機(jī)上復(fù)現(xiàn)實(shí)物樣件的幾何形狀，并在此基礎(chǔ)上進(jìn)行原樣復(fù)制、修改或重設(shè)計(jì)，在工程實(shí)驗(yàn)、計(jì)算機(jī)圖形和計(jì)算機(jī)輔助幾何設(shè)計(jì)等方面有著廣泛的應(yīng)用。其中，如何從掃描得到的離散數(shù)據(jù)（通常為點(diǎn)云模型）中提取原始模型外表的幾何基元（多為二次曲面），是對(duì)模型進(jìn)行各種處理的基礎(chǔ)的、關(guān)鍵性的工作?；崛M合給定點(diǎn)云模型的最佳二次曲面，用點(diǎn)云與提取出的二次曲面之間的“最小距離”對(duì)擬合性能進(jìn)行評(píng)價(jià)，以確定擬合曲面是否真正充分表達(dá)了整個(gè)模型[1]。當(dāng)前各基元提取算法多針對(duì)平面、球、圓柱、圓錐和可擴(kuò)展曲面等相對(duì)簡(jiǎn)單的二次曲面，很少涉及橢球等復(fù)雜的基元[2-3]。面向幾何基元提取問題，本文提出了一種從點(diǎn)云模型中有效提取復(fù)雜橢球的算法。

1 相關(guān)工作

基元幾何基元的檢測(cè)和提取一直備受研究人員的關(guān)注。多年來，有大量不同的方法被提出，限于篇幅，本文將不在此對(duì)這些方法進(jìn)行詳細(xì)地討論，僅對(duì)一些最重要的方法做一個(gè)簡(jiǎn)要的回顧。

RANSAC（RANdom SAmpling Consensus，隨機(jī)采樣一致性）[2]和Hough變換是用于幾何基元提取的最常用的兩種方法。有大量的噪聲和外點(diǎn)的情況下，二者都被證明能成功地檢測(cè)出二維和三維空間的形狀，但是低效和高存儲(chǔ)容量要求是它們的主要缺點(diǎn)。為此，COHEN-STEINER等[3]提供了一個(gè)通用的變分框架，使用多個(gè)平面來逼近表面。WU等[4]將此方法進(jìn)行了擴(kuò)展，使用一組更加復(fù)雜的基元（平面、球面和可擴(kuò)展的圓環(huán)）來逼近表面。他們的目標(biāo)不僅僅是檢測(cè)幾何基元，而且還試圖尋找給定基元數(shù)目時(shí)的全局最優(yōu)表示。RUWEN等[2,5]增加基元的類型（平面、球體、圓柱、圓錐和圓環(huán)），并提出了一種高性能的 RANSAC算法，能在提取不同類型的基元形狀的同時(shí)，保持基本 RANSAC算法框架的良好特性，如一般性和簡(jiǎn)潔性。橢球可以看作廣義圓柱體的一個(gè)特例，具有一定的對(duì)稱性，相對(duì)于球也能更靈活地表現(xiàn)較復(fù)雜的幾何信息。本文基于文獻(xiàn)[2]中的算法框架，實(shí)現(xiàn)點(diǎn)云中橢球基元的有效檢測(cè)與提取。

2 點(diǎn)云模型的橢球體提取

本文采用RANSAC框架（偽代碼見圖1）完成橢球的提取工作：使用一種局部的采樣策略進(jìn)行采樣[2]，從點(diǎn)云數(shù)據(jù)（點(diǎn)數(shù)為 N）中隨機(jī)選取最小點(diǎn)集，即能唯一地確定橢球的最少數(shù)目的點(diǎn)的集合，本文設(shè)點(diǎn)數(shù)為6（2.1節(jié)）；利用最小二乘的方法計(jì)算橢球的參數(shù)，即橢球的中心、半軸長(zhǎng)和偏轉(zhuǎn)角度（2.2節(jié)）；基于距離和偏角參數(shù)驗(yàn)證求得的橢球的正確性（2.3節(jié)）；將通過驗(yàn)證的橢球與點(diǎn)云中的所有點(diǎn)進(jìn)行匹配，以判斷有多少點(diǎn)可以由此候選點(diǎn)基元近似表示，點(diǎn)的數(shù)目被稱作分?jǐn)?shù)，完成了分?jǐn)?shù)函數(shù)（2.4節(jié)）的計(jì)算，得到了評(píng)估橢球的方法，最后依據(jù)分?jǐn)?shù)方程篩選出最好的候選點(diǎn)m。這個(gè)最佳的候選點(diǎn)只有在這種情況下才會(huì)被接受：由m中點(diǎn)的個(gè)數(shù)|m|和已經(jīng)選出的候選點(diǎn)形狀的個(gè)數(shù)得到的能正確檢測(cè)出形狀的置信概率大于用戶定義的閾值pt。進(jìn)而通過求投影點(diǎn)的方法繪制出檢測(cè)到的橢球。如果一個(gè)候選點(diǎn)被接受，那么相應(yīng)的點(diǎn)會(huì)從點(diǎn)云中刪除，并這個(gè)候選也會(huì)從集合 C中刪除。算法在概率大于pt的時(shí)候停止，其中τ是用戶定義的最小的形狀包含的點(diǎn)的數(shù)目，這表明所包含的點(diǎn)超過τ的形狀已經(jīng)被檢測(cè)出來的概率大于pt。算法用了一種標(biāo)準(zhǔn)的分?jǐn)?shù)方程來計(jì)算一個(gè)候選點(diǎn)能容許的點(diǎn)的數(shù)目，即RANSAC算法所說的一致集。分?jǐn)?shù)方程的輸入包括評(píng)估的候選形狀的參數(shù)，以及有兩個(gè)用戶定義的閾值ε和α：ε表示一個(gè)能容許的點(diǎn)到候選形狀的最大距離；α是一個(gè)點(diǎn)的法向到候選形狀的法向的最大偏移量。綜上所述，在檢測(cè)開始前，用戶需要定義以下的閾值：計(jì)算分?jǐn)?shù)方程時(shí)的距離閾值ε、角度閾值α、最小的橢球包含的點(diǎn)的個(gè)數(shù)τ和置信概率閾值pt。

對(duì)于置信概率，我們假設(shè)任意6個(gè)點(diǎn)都可以產(chǎn)生一個(gè)候選點(diǎn)，那么一次能夠正確檢測(cè)到形狀的概率是

在選出了|C|個(gè)候選點(diǎn)之后可以正確的檢測(cè)出形狀的概率是

2.1 局部采樣

在進(jìn)行采樣時(shí)，本文采用局部的采樣策略進(jìn)行采樣[2]，使用一個(gè)八叉樹來有效地建立樣本點(diǎn)間的空間近似度。當(dāng)要選擇樣本點(diǎn)來產(chǎn)生新的候選點(diǎn)時(shí)，首先沒有任何約束地從空間中選出一個(gè)點(diǎn)，然后從八叉樹中任意一級(jí)隨機(jī)選擇一個(gè)包含該點(diǎn)的單元格，其他的5個(gè)點(diǎn)從這個(gè)單元格內(nèi)選出。

2.2 橢球的估計(jì)

橢球的估計(jì)是指從上面采樣的點(diǎn)中產(chǎn)生一個(gè)與點(diǎn)云中實(shí)際隱藏的橢球相近的一個(gè)橢球模型。橢球面的參數(shù)化方程如下

要解出這個(gè)方程中A到I這9個(gè)參數(shù)，需要在橢球面上的9個(gè)點(diǎn)，將這9個(gè)點(diǎn)帶入到公式(1)中，問題就變成了一個(gè)解線性方程組的問題了。而實(shí)際上，因?yàn)椴荒鼙ＷC所抽取的樣本點(diǎn)都在橢球面上，就算有9個(gè)樣本點(diǎn)的數(shù)據(jù)，構(gòu)成一個(gè)線性的方程組，這個(gè)方程組也可能無法解出這9個(gè)參數(shù)。本文利用橢球的幾何性質(zhì)，先估計(jì)出橢球的中心，然后用最小二乘方法計(jì)算出橢球的軸長(zhǎng)和偏轉(zhuǎn)角度。

橢球中心的估算方法的基礎(chǔ)為橢球中心的求解引理《空間解析幾何》[6]：對(duì)于橢球上的 4個(gè)不共面點(diǎn)和p4，任兩個(gè)點(diǎn)的中心和兩個(gè)點(diǎn)的橢球切平面相交所得的直線建立平面Pi，所有Pi相交于橢球的中心點(diǎn)。任取4個(gè)帶法向的點(diǎn)，建立相應(yīng)的平面Pi(i=1,…4)，平面方程為：。因?yàn)檫@4個(gè)點(diǎn)不一定在橢球面上，所以從中任取4個(gè)平面不一定交于一點(diǎn)。因此，本文選擇距離這4個(gè)平面的距離平方之和最小的點(diǎn)作為我們估計(jì)出來的合理的橢球中心，即求取下式的最小值

求出橢球中心后，將坐標(biāo)系的原點(diǎn)平移到橢球中心得到公式

參照《空間解析幾何》[6]中所述的方法，取6個(gè)點(diǎn)分別代入公式，求出橢球的3個(gè)半長(zhǎng)軸的長(zhǎng)度和偏角。

設(shè)對(duì)稱矩陣S為

如果I, J, K都大于0，則證明所求系數(shù)代入上式中得到的二次曲面的確是橢球。設(shè)λ1,λ2,λ3為S的特征值，v1,v2,v3為對(duì)應(yīng)的特征向量，那么 3個(gè)半軸的長(zhǎng)度

2.3 橢球的驗(yàn)證

由于估計(jì)出來的橢球可能存在誤差，在進(jìn)一步地評(píng)估候選的好壞之前，先驗(yàn)證用于估計(jì)橢球的樣本點(diǎn)本身是否能很好地符合估計(jì)出來的橢球，若估計(jì)時(shí)使用的所有樣本點(diǎn)都能很好符合，則驗(yàn)證通過。為了驗(yàn)證，必須得到兩個(gè)數(shù)據(jù)：樣本點(diǎn)到橢球的距離d，樣本點(diǎn)的法向與樣本點(diǎn)在橢球面上的投影處的法向之間的偏角θ。當(dāng)兩個(gè)數(shù)據(jù)滿足所給的閾值條件即d＜ε，θ＜α?xí)r，即認(rèn)為此樣本點(diǎn)可以很好符合橢球。

2.4 橢球的分?jǐn)?shù)計(jì)算

橢球的分?jǐn)?shù)就是點(diǎn)云中距離和法向偏角滿足一定的閾值要求，且其投影點(diǎn)屬于橢球的最大連通分量?jī)?nèi)的點(diǎn)的個(gè)數(shù)。直接在橢球面上求最大連通分量是困難的。因?yàn)橛?jì)算橢球面上兩點(diǎn)間沿橢球面的最短弧的長(zhǎng)度是比較復(fù)雜的。在這里，為了簡(jiǎn)化，我們先將點(diǎn)都投影到一個(gè)平面的參數(shù)域上，通過計(jì)算平面參數(shù)域上的最大連通分量求得橢球面上的最大連通分量。

將橢球面上的點(diǎn)投影到參數(shù)平面之后，先要將參數(shù)平面位圖化，然后在進(jìn)行連通分量的檢測(cè)。位圖的像素的大小由原始數(shù)據(jù)的采樣分辨率確定。如果一個(gè)像素的區(qū)域內(nèi)存在橢球面上點(diǎn)的投影，那么這個(gè)像素將被著色。連通分量的計(jì)算過程是這樣的，首先將每個(gè)像素的連通分量編號(hào)都設(shè)為-1，表示不屬于任何分量。逐行掃描位圖的每個(gè)像素，在掃描的過程中要記錄每個(gè)已檢測(cè)出的連通分量包含的像素點(diǎn)，如果掃描到的這個(gè)像素點(diǎn)未被著色，不做任何處理，如果這個(gè)像素著色了，則考察已經(jīng)掃描過的與這個(gè)像素點(diǎn)相鄰的像素點(diǎn)，將這些相鄰像素點(diǎn)所屬的連通分量合并，再加入當(dāng)前的這個(gè)點(diǎn)得到一個(gè)新的連通分量，當(dāng)掃描完畢之后就找到了所有的連通分量。包含像素點(diǎn)最多的就是最大連通分量。

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

本文算法在 VC＋＋平臺(tái)上用 OPENGL實(shí)現(xiàn)。為了測(cè)試本文橢球提取算法的有效性，本文在人工合成和掃描儀獲取的點(diǎn)云模型上展開了實(shí)驗(yàn)，并使用運(yùn)行時(shí)間、擬合誤差兩個(gè)指標(biāo)對(duì)算法的性能進(jìn)行了定量描述。

首先，本文使用了一個(gè)手工創(chuàng)建的橢球模型并記錄下其各個(gè)參數(shù)，并對(duì)此模型進(jìn)行隨機(jī)采樣得到10萬個(gè)點(diǎn)；然后運(yùn)行本文算法，將得到橢球參數(shù)與真實(shí)參數(shù)進(jìn)行比對(duì)。參數(shù)設(shè)置為：最大距離 ε = 0 .008*BB （BB為包圍盒的對(duì)角線長(zhǎng)度），最大偏角α=30°，最小形狀的大小為τ=200，置信概率 pt= 9 9.9999%。圖2中給出了球的檢測(cè)結(jié)果，算法運(yùn)行時(shí)間為1.1233秒，平均距離誤差（指的是原始數(shù)據(jù)點(diǎn)到其在檢測(cè)出的形狀上的對(duì)應(yīng)點(diǎn)的平均距離）為0.0003。表1則給出了原始橢球的數(shù)據(jù)與檢測(cè)出來的橢球的數(shù)據(jù)的比較，結(jié)果表明，本文的方法能夠正確地檢測(cè)出橢球。

圖2 人工合成的橢球的提取結(jié)果

表1 提取出的橢球參數(shù)與真實(shí)數(shù)據(jù)的比較

本文提出的算法應(yīng)用到由激光掃描儀得到的原始點(diǎn)云模型，如圖3所示?？梢钥吹?，在此點(diǎn)云模型中，每個(gè)人物的頭部可以大致由橢球來進(jìn)行擬合。我們?yōu)樗惴ㄔO(shè)置的參數(shù)為：最大距離ε= 0 .009*BB ，最大偏角α=40°，最小形狀的大小為τ=200，置信概率 pt= 9 9.9999%。實(shí)驗(yàn)結(jié)果表明，在 RANSAC算法框架基礎(chǔ)上，本文提出的算法能夠在點(diǎn)云模型中檢測(cè)并提取出來可以由橢球擬合的部分（例如人的頭部），并得到很好的擬合結(jié)果。算法的運(yùn)行時(shí)間為 58.5s，平均距離誤差為0.0407，檢測(cè)出51個(gè)基元。

4 結(jié) 論

基于RANSAC的形狀檢測(cè)已經(jīng)能從點(diǎn)云中檢測(cè)出平面，球，圓錐，圓柱，圓環(huán)等形狀，為了能得到更為準(zhǔn)確和復(fù)雜的基元表示，本文提出了一種在點(diǎn)云模型中提取橢球的算法。該算法使用了RANSAC框架；使用一種局部的采樣策略進(jìn)行采樣；利用最小二乘的方法計(jì)算橢球的參數(shù)（中心點(diǎn)、半軸長(zhǎng)和偏轉(zhuǎn)角度）；利用距離和偏角進(jìn)行橢球的初步驗(yàn)證，并通過一種低扭曲的參數(shù)化方法得到參數(shù)化平面計(jì)算出最大連通分量，完成了分?jǐn)?shù)方程的計(jì)算，得到評(píng)估橢球的分?jǐn)?shù)；最后依據(jù)分?jǐn)?shù)篩選出最好的候選，通過求投影點(diǎn)的方法繪制出提取的橢球。在人工合成和掃描儀獲取的點(diǎn)云數(shù)據(jù)上，本文驗(yàn)證了所提算法的有效性和魯棒性。

圖3 真實(shí)掃描數(shù)據(jù)(上)的橢球(下)的提取結(jié)果

[1]劉金平, 程志全, 黨 崗, 等. 三角網(wǎng)格中二次曲面的提取方法綜述[C]//第 15屆計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)術(shù)會(huì)議, 大連: 中國(guó)計(jì)算機(jī)學(xué)會(huì), 2008: 134-139.

[2]Schnabel R, Wahl R, Klein R. Efficient RANSAC for point-cloud shape detection [J]. Computer Graphic Forum, 2007, 26(2): 214-226.

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

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

[5]Li B, Schnabel R, Jin S, et al. Variational surface approximation and model selection [J]. Computer Graphics Forum, 2009, 28(7): 1985-1994.

[6]楊文茂, 李全英. 空間解析幾何[M]. 武漢: 武漢大學(xué)出版社, 1998: 128-135.