張靖　　周明全，2　　張雨禾　　耿國華

基于馬爾科夫隨機場的散亂點云全局特征提取

張靖1周明全1，2張雨禾1耿國華1

為了精確提取點云數(shù)據(jù)中的特征信息，針對激光掃描獲取的三維散亂點云數(shù)據(jù)，提出一種基于馬爾科夫隨機場（Markov random field，MRF）的散亂點云特征提取方法.首先，根據(jù)散亂點的曲率估計及閾值初始化點標號并判定穩(wěn)定點，將穩(wěn)定點標記存儲在數(shù)組中；然后，將優(yōu)化不穩(wěn)定點的標號問題轉(zhuǎn)化為隨機場標號的能量函數(shù)問題，引用貝葉斯估計求后驗概率分布函數(shù)及MAP-MRF（Maximum a posteriori-Markov random field）框架歸約得到目標函數(shù)；最后，根據(jù)圖割法α-expansion算法，利用標號調(diào)整過程中標號集相對能量變化得到不穩(wěn)定點的最優(yōu)標號集，將其與存儲穩(wěn)定點的數(shù)組綜合，根據(jù)點標號提取特征點.實驗結(jié)果表明，該方法簡單、高效、無需人工調(diào)參，能夠依據(jù)全局能量的變化自適應提取特征，特征提取結(jié)果令人滿意.

散亂點云，特征提取，馬爾科夫隨機場，標號

引用格式張靖，周明全，張雨禾，耿國華.基于馬爾科夫隨機場的散亂點云全局特征提取.自動化學報，2016，42（7）: 1090-1099

隨著三維掃描技術的快速發(fā)展，通過激光掃描技術獲得點云模型成為近幾年幾何模型的通用表示形式.一個物體的表達是通過精確描述該物體尖銳特征實現(xiàn)的，特征是反應模型幾何外觀的最小基元，也是模型外觀準確表達的關鍵因素，因此，特征提取技術也成為數(shù)字幾何處理中備受關注的熱點話題，是后續(xù)模型分析、數(shù)據(jù)配準、曲面重建的底層技術之一.如何有效地提取點云模型的特征點成為點云數(shù)據(jù)處理的關鍵問題.

目前，已有諸多學者展開了針對三維模型特征提取的研究，而大部分方法是針對網(wǎng)格曲面等含有較多拓撲信息的模型進行處理.由于點云模型缺少頂點間的拓撲鄰接關系，且不包含任何曲面和體積的信息，難以計算其物理性質(zhì)和幾何性質(zhì)，因此，針對點云數(shù)據(jù)的處理方法較少，大致可以分為三類：基于局部擬合或聚類的方法、基于多尺度的思想以及基于特征檢測算子的方法.

1）基于局部擬合或聚類的方法進行特征提?。篋aniels等［1］提出了一種基于魯棒移動最小二乘的特征線提取方法，利用魯棒移動最小二乘擬合曲面并計算一點到擬合曲面對應點的殘差，設置閾值提取潛在特征點，將潛在特征點投影在最近曲面交線上，利用協(xié)方差分析對投影點進行平滑處理.該方法在噪聲幅度較大或者稀疏采樣時算法性能較差. Demarsin等［2］提出了一種三維點云數(shù)據(jù)封閉特征線提取方法，首先，使用主成分分析計算點法向；然后，基于局部鄰域的法向變化將點聚類，形成不同的簇.在進行特征點的判斷時，是通過兩點的法向夾角同可接受最大角度閾值進行比較，而此時的特征點是以一個聚類為單位進行判斷.龐旭芳等［3］提出了一種點云模型谷脊特征的提取與增強算法，采用多步逼近策略提取特征點.通過局部最小二乘擬合曲面多項式計算主曲率，選取絕對值較大的主曲率同閾值比較，識別潛在谷脊特征點［4］，再將特征點投影到離其最近的潛在特征線上，得到增強的特征點并對其平滑處理.該算法需要用最小二乘進行曲面多項式的擬合，計算方法復雜；潛在特征點的提取不僅計算擬合曲面多項式的微分性質(zhì)，而且要調(diào)整法向，時間耗費大；且傳播閾值的設置需要根據(jù)經(jīng)驗人工設置，不能自適應調(diào)整.

2）基于多尺度的思想進行特征提?。篜auly等［5］提出了一種多尺度點云特征點提取方法，它是將局部鄰域的大小作為離散尺度參數(shù)的協(xié)方差分析，計算一點在不同尺度下成為特征點的可能性，從而提取特征點.該方法對噪聲敏感，即不具有魯棒性［6［8］提出了一種在多尺度的思想下基于曲率的方法提取特征，在多尺度的思想上采用一個剛體運動不變量曲度提取特征點，并用置信值評估特征點的穩(wěn)定性.該方法根據(jù)多尺度空間曲面點的局部擬合計算曲度（點的最大最小主曲率的算術平方根），實現(xiàn)特征點的提取.判斷特征點的原則：曲面上一點不僅在當前尺度下曲度是局部極值，而且在該尺度相鄰的兩個尺度上曲度依然是局部極值.該算法要在不同的尺度下進行局部擬合并計算點的曲度，尺度愈多，提取的特征點準確率越高，但時間耗費越大.而部分顯著特征只能在高尺度下提取出來，因此該算法是以時間為代價提高算法準確率.

3）基于特征檢測算子的方法：Gumhold等［9］通過構(gòu)造黎曼樹表示點云的連接信息，基于局部鄰域協(xié)方差矩陣的特征值計算判斷一點是特征點的可能性.Jia等［10］和Tang等［11］提出一種基于張量投票的魯棒的曲面、幾何特征線及角點提取算法，該算法需要對空間進行規(guī)格網(wǎng)格劃分，并且對每一個網(wǎng)格節(jié)點用張量投票的方法累加周圍節(jié)點對該節(jié)點的影響，由此判斷該點是否為特征點.吾守爾·斯拉木等［12］提出了一種基于平均曲率運動的散亂點云尖銳特征提取算法，它主要是通過采樣點和其對應的加權(quán)鄰域重心的距離標志尖銳特征候選點，然后將該距離投影到采樣點的法向方向進行平滑，比較投影距離和閾值，提取尖銳特征點.王麗輝等［13］提出了一種基于曲率和密度的特征點檢測算法，通過點到鄰居點的平均距離、點的法向與鄰居點法向夾角及數(shù)據(jù)點曲率三部分定義一個特征參數(shù)；然后，通過數(shù)據(jù)點密度與模型到中心點的最大距離相除得到特征閾值；最后，將特征參數(shù)與特征閾值進行比較，提取特征點.

基于局部擬合或重建的方法，計算復雜度高且時間耗費較大；而基于多尺度思想的方法，尺度愈大，時間耗費愈多，提取的特征點準確率越高，且部分顯著特征只能在高尺度下提取出來，因此，該算法是以時間為代價提高算法準確率的；而基于局部檢測算子的方法，大多依賴于全局固定的閾值，這種依賴人工調(diào)參的半交互式特征提取方法要求用戶對模型有一些先驗知識的累積，閾值較大，可能造成冗余特征，而閾值較小，則只能提取出較尖銳的特征，忽略較平滑的特征.

馬爾科夫隨機場（Markov random field，MRF）方法建立在MRF圖像模型和貝葉斯估計的基礎上，結(jié)合觀測圖像求解.在國內(nèi)，傳統(tǒng)的馬爾科夫隨機場模型起初僅用在圖像處理領域，其中包括二值圖像復原、圖像分割及目標單幀檢測等.其中最熱門的應用是圖像分割.近幾年，有些學者將馬爾科夫隨機場模型引用在三維模型處理方面，但局限在三維網(wǎng)格模型的分割以及點云模型的識別方面，例如文獻［14-15］.針對點云模型的特征提取技術，還未出現(xiàn)引用MRF的相關文獻.

針對上述問題，本文提出一種基于馬爾科夫隨機場模型［16-17］的全局特征提取方法，直接對點云進行處理.特征提取問題的本質(zhì)是分類問題，即根據(jù)設定的準則，將點云上的點劃分為特征點和非特征點兩類且將點標號并分類，不需要局部曲面擬合或重建.同時，無需人工調(diào)參，能自適應地提取特征點，首先，對散亂點進行曲率估計并設定閾值，將點的曲率估計的絕對值同閾值比較，初始化點標號；再根據(jù)點的k近鄰中k個點的標號與該點標號是否相同識別穩(wěn)定點，并將其標記存儲在數(shù)組中；然后，求解不穩(wěn)定點的最優(yōu)標號集.用多個高斯分布擬合不穩(wěn)定點的屬性信息直方圖分布，并求高斯分布各自的均值和標準差，當點的觀測信息已知時，計算該點取對應標號的聯(lián)合概率分布.依據(jù)馬爾科夫—吉布斯隨機場等價定理可得馬爾科夫隨機場狀態(tài)分布函數(shù).由聯(lián)合分布和狀態(tài)分布函數(shù)求出目標函數(shù)；接著由目標函數(shù)計算不穩(wěn)定點的最優(yōu)標號集.采用圖割法α-expansion算法，通過隨機場全局能量變化解目標函數(shù)，得到不穩(wěn)定點的最優(yōu)標號集；最后，綜合不穩(wěn)定點的最優(yōu)標號集與存儲穩(wěn)定點的數(shù)組，得到散亂點云的最優(yōu)標號集.根據(jù)點集與最優(yōu)標號集間存在一一對應的關系，提取特征點.

實驗結(jié)果表明，本文算法計算方法簡單、容易理解且速度相對較快，具有自適應性，不需要人工調(diào)參.通過計算每一次調(diào)整標號對應的隨機場全局能量選取標號集，直到全局能量達到穩(wěn)定，最小能量對應的標號集就是最優(yōu)標號集，進而提取特征點.

我國是一個古老文明的國家.然而，時間流逝，許多文物保存不當，造成文物的破碎殘缺.因此，借助計算機復原破碎文物是順應科技發(fā)展的必然趨勢，而特征提取是借助計算機復原破碎文物的初始階段，是碎片匹配、拼接等后續(xù)工作的基礎.本文算法廣泛應用在非真實感渲染以及線畫圖的繪制方面，是復原的后續(xù)工作的基石.

1　基于馬爾科夫隨機場的點云特征提取算法

馬爾科夫隨機場模型描述的是一個時間序列的問題，即一個時間的某一狀態(tài)只與它前一時間的狀態(tài)有關，和其他任何狀態(tài)都沒有關系.馬爾科夫隨機場模型性質(zhì)符合特征點判定的問題.在特征點檢測問題中，它的前一狀態(tài)指該點鄰域內(nèi)的點.因此，本文將提取特征點的問題建模為貼標簽問題，共有兩個標簽：特征點和非特征點，通過對散亂點貼標簽實現(xiàn)點分類并減少計算量：1）若一個點鄰域內(nèi)點的標號均為特征點，將該點標記為特征點；2）若一個點鄰域內(nèi)點的標號均為非特征點，將該點標記為非特征點；3）若一個點的鄰域內(nèi)點的標號既有特征點又有非特征點，構(gòu)造目標函數(shù)—能量函數(shù)，計算該點取哪一個標號的概率大，將該點標記為概率大的標號. 圖1所示為本文方法的流程圖.

1.1初始化散亂點云標號場

曲率的大小可以反映模型表面的凹凸程度，所以曲率是進行特征提取的重要信息.本文通過對數(shù)據(jù)點的m 個鄰居點進行協(xié)方差分析［18-19］估算數(shù)據(jù)點的曲率，初始化數(shù)據(jù)點標號：對于給定點pi的球鄰域鄰居點進行協(xié)方差分析，根據(jù)協(xié)方差矩陣的特征值估計曲率（本文認為點的曲率近似等于曲率估計）.設協(xié)方差矩陣特征值為且滿足，則曲率估計di為

然后對曲率估計求平均值并設定閾值θ，本文選取一個較為寬松的閾值以保留盡可能多的潛在特征點，并在后續(xù)的標號優(yōu)化時精確提取特征點.閾值為

根據(jù)閾值初始化點標號，得到初始標號場，曲率絕對值大于閾值的點標記為特征點，其標號置為1；否則，標記為非特征點，標號置為2：

由此得到初始標號場f=｛f1，f2，···，fN｝，其中fi是指第i個點的標號.

為減少計算量，在優(yōu)化標號前先判定穩(wěn)定點，若是穩(wěn)定點將其標記存儲在數(shù)組內(nèi)，然后對不穩(wěn)定點進行能量優(yōu)化.判定穩(wěn)定點時，首先計算每一個點的k近鄰（該點鄰域內(nèi)距離它最近的k個點），若這k個點的標號和該點的標號相同，該點是穩(wěn)定點；否則，是不穩(wěn)定點.

圖1　本文方法流程圖Fig.1　The flowchart of our method

1.2建立最優(yōu)標號目標函數(shù)建立最優(yōu)標號目標函數(shù)主要分為兩步：1）建立馬爾科夫隨機場的標號場模型時，首先用K個高斯分布擬合三維散亂點云中不穩(wěn)定點集P的屬性信息di的直方圖分布，這K個高斯分布是分別對K個標號的點集屬性信息進行擬合.用最大期望算法（Expectation-maximization，EM）求這K個高斯分布各自的均值和標準差得到當馬爾科夫隨機場的狀態(tài)f給定時，觀測隨機變量即屬性信息為d的聯(lián)合概率：

其中，N1是不穩(wěn)定點的數(shù)目.最大期望算法EM：

b）由當前的參數(shù)估計每個數(shù)據(jù)與每個類之間的相關性：

d）利用式（6）～（8）給出的參數(shù)計算似然函數(shù)的對數(shù)，判斷似然函數(shù)取對數(shù)之后的函數(shù)式是否滿足收斂的條件，若是，算法終止；否則，轉(zhuǎn)步驟b）.

2）然后根據(jù)Hammersley-Clifford定理求得馬爾科夫隨機場的狀態(tài)分布函數(shù)：

其中，Z為歸一化常數(shù)，β為交互系數(shù)，用來決定先驗信息在馬爾科夫隨機場中所占的權(quán)重，本文中取β=8.0.δi指點i的球鄰域，U（f）為能量函數(shù)，是子團勢能函數(shù)Vc（f）的和，即

本文僅考慮雙點勢團的能量［12］.

定義子團勢能函數(shù)V（i，j）（f），計算勢能函數(shù)時，本文相鄰頂點是：一個點鄰域內(nèi)距離該點歐氏距離最短的點.因此，子團勢函數(shù)如下：

其中，CurvDist（i，j）為點 i，j的曲率距離，max（CurvDist）和min（CurvDist）分別為在散亂點云模型中的最大值和最小值，為了避免分母為零的狀況及保證V（i，j）（·）的正定性，α取一個很小的正數(shù)，本文中取0.00001.曲率距離為

其中，Cmin為三維散亂點云模型的各個頂點的最小離散曲率，本文引用Cohen-Steiner等［20］和Alexa等［21］提出的算法來計算各個頂點的最小離散曲率.

3）根據(jù)前面求得的p（d|f）和p（f），定義目標函數(shù).由MAP-MRF（Maximum a posteriori-Markov random field）框架可知，當點云模型中點的相關屬性給定時，即觀測隨機變量的值給定時，散亂點云的馬爾科夫隨機場模型的最優(yōu)狀態(tài)f?為

使用MAP的實質(zhì)就是將標記分類的概率誤差最小化，即當觀測隨機變量即點的相關屬性給定時，每一個點屬于哪一個標號的概率最大，就將該標號賦予這個點，最后這些散亂點的標號組成的集合即為最優(yōu)標號集.

定義U（f|d）為

其中，U（d|f）為

由貝葉斯定理可知：

然而，由于p（f|d）∝exp（-U（f|d）），故

最大后驗概率的問題轉(zhuǎn)化為最小能量的問題.則由式（17）將式（13）改寫成：

那么，馬爾科夫隨機場求最優(yōu)標號問題實質(zhì)是由先驗概率求最大后驗概率的問題.當點的屬性信息已知時，每一個點取目前對應的標號的概率越大，對應的隨機場的全局能量就越小，即后驗概率同能量函數(shù)成反比，因此求最優(yōu)標號集就是求最小能量.因此采用能量最小化原理求解最優(yōu)標號的問題.

最后得到目標函數(shù)：

1.3散亂點云標號場的優(yōu)化

根據(jù)前一部分的目標函數(shù)，進一步知道最優(yōu)標號集為

其中，f?為目標函數(shù)的解，即最優(yōu)標號集.對于目標函數(shù)，本文引用圖割法α-expansion算法解優(yōu)化問題：f?=minf∈F（E（f）），求得最優(yōu)狀態(tài)f?.最終的最優(yōu)狀態(tài)就是三維散亂點云中不穩(wěn)定點的最優(yōu)標號集，將其與存儲穩(wěn)定點的數(shù)組綜合，得出散亂點云的標號集f1?.

由第1.2節(jié)可知，當點的觀測信息給定時，求最優(yōu)標號的問題實質(zhì)就是求最大概率的問題—每一個點取標號集中哪一個標號概率最大，即每一個點被正確劃分為特征點與非特征點的概率最大.由于每一個點的狀態(tài)都和它的鄰點緊密相關，將求最大概率的問題轉(zhuǎn)化為求最小能量的問題（本文能量是考慮雙點勢團的能量，用來描述鄰點之間的相關性）—點集取當前對應的標號集全局能量最小.因此，求最優(yōu)標號的問題就是求最小能量的問題，能量越小，提取特征點的準確率越高.

α-expansion算法的主要思想是通過對標號執(zhí)行α-expansion move操作來尋找基于α的一個局部最優(yōu)解.即在標記f的所有一次α擴展變換所得的標記過程f′中，找到一個f2，使得f2=argminE（f′），若E（f2）＜E（f），則f=f′.其中，一個標號集是否優(yōu)于前一個標號集是由該標號集與前一個標號集之間全局能量的大小界定.

α-expansion算法的具體步驟為

1.4提取特征點

根據(jù)第1.3節(jié)得到不穩(wěn)定點的最優(yōu)標號集，即散亂點中不穩(wěn)定點的最優(yōu)分類標號.將不穩(wěn)定點的最優(yōu)標號集同存儲穩(wěn)定點的數(shù)組綜合，得到散亂點云的最優(yōu)標號集f?.其中，最優(yōu)標號集f1?= ｛f1，f2，···，fN｝與散亂點集P=｛p1，p2，···，pN｝之間存在一一對應的關系，即點p1的標號對應的是f1，以此類推，得到所有點的標號，根據(jù)標號類型直接判斷該點是否為特征點，得到特征點集.判斷一個點是否為特征點：

2　實驗結(jié)果與分析

本文算法在Visual Studio 2010環(huán)境下實現(xiàn)了特征點的提取，硬件平臺為2.8GHz Intel Core i5處理器、4GB內(nèi)存的PC機.本文算法的參數(shù)列表如表1所示.其中，將球形鄰域半徑δ取值為0.01ldb～0.03ldb（ldb表示圖形的包圍盒的對角線長度）.

表1參數(shù)列表Table 1　The parameter list

2.1本文方法實驗

兵馬俑碎片的點云模型是通過非專業(yè)人員使用Creaform VIU 718手持式掃描儀掃描獲得.掃描分辨率是3.91mm，這有利于掃描速度，但掃描精度粗糙.在該部分應用本文特征提取方法提取兵馬俑碎片的特征點.特征檢測的結(jié)果如圖2～圖4所示.為了說明本文方法能夠準確地提取尖銳特征及細微特征點，同時能夠保留較平滑的特征，本文選取三種具有不同特征的兵馬俑碎片進行實驗.

圖2　兵馬俑1號碎片特征提取Fig.2　Feature extraction of Terracotta Army 1

圖2是兵馬俑1號碎片模型圖及特征提取結(jié)果圖.該碎片是一個僅有尖銳特征的簡單碎片模型，特征線比較突出，圖2（b）表明本文方法能夠完整準確地提取出碎片的尖銳特征點.

圖3、圖4是一個相對圖2較為復雜的兵馬俑碎片模型，這兩個模型既包含尖銳特征，也包含相對平滑的特征，既有采樣比較好的區(qū)域，也存在采樣不均的區(qū)域，甚至還包含特征強度逐漸減弱的特征線.從圖3（b）和圖4（b）中可以看出，本文方法不僅提取到尖銳特征，同時也完整地保留了相對平滑的特征，例如碎片表面較為平滑的凸起，該方法能夠識別并提取出特征點.

圖3　兵馬俑2號碎片特征提取Fig.3　Feature extraction of Terracotta Army 2

圖4　兵馬俑3號碎片特征提取Fig.4　Feature extraction of Terracotta Army 3

2.2對比實驗

為了驗證本文方法的優(yōu)越性，本文對文獻［9］及文獻［13］的方法進行了實現(xiàn).其中，文獻［9］的方法實質(zhì)是基于張量投票提取特征，主要是通過采樣點和其對應的加權(quán)鄰域重心的距離標志尖銳特征候選點，然后將該距離投影到采樣點的法向方向進行平滑，比較投影距離和閾值，提取尖銳特征點.文獻［13］的閾值檢測法首先通過點到鄰居點的平均距離、點的法向與鄰居點法向夾角和數(shù)據(jù)點曲率三部分定義一個特征參數(shù)，然后將特征參數(shù)與特征閾值進行比較，提取特征點.該兩個方法均涉及特征參數(shù)及特征閾值的選取設置，因此它們不能很好地識別逐漸平滑的特征及細微特征.

圖5為本文方法、張量投票法以及閾值檢測法在Bunny模型上的特征提取效果對比.Bunny模型既包含尖銳特征，也包含相對平滑的特征.張量投票的特征提取方法不能很好地檢測出相對平滑的特征，閾值檢測法對于頭部的眼睛嘴巴的細微特征不能完整的識別.而本文方法能夠較好地提取尖銳特征，同時盡可能地保留較平滑的特征點.

圖6為本文方法、張量投票法以及閾值檢測法在Fandisk模型上的特征檢測對比.Fandisk模型既包含顯著特征，也包含相對較弱的特征，既包含直線特征，也帶有曲線型特征強度連續(xù)變化的特征.圖6（c）為張量投票方法提取出尖銳特征，對于底部較為平滑的特征不能很好地識別.特征閾值檢測法能夠檢測出尖銳特征，但是不能識別逐漸平滑的特征. 圖 6（b）為本文方法提取特征的結(jié)果圖，從中可以看出，本文方法不僅提取到顯著特征，同時也保留了較平滑的特征.

圖 7為 Dragon模型的算法效果對比圖. Dragon模型復雜，點數(shù)量大，且其頭部細小特征較多.通過對比圖7（b）～（d）可以發(fā)現(xiàn)，本文算法檢測出該模型的尖銳特征點以及一些細微的特征點；其余兩種方法同樣能夠檢測出尖銳特征點，但是不能很好地識別一些細微特征點.

本文方法首先通過曲率估計確定穩(wěn)定點，然后通過計算能量函數(shù)使不穩(wěn)定點以一定的概率接受該點是否是特征點，使特征點的判斷具有靈活性，減少特征點的誤判.從實驗結(jié)果圖可以看出，本文方法能夠更加精確地提取出尖銳特征點，并盡可能多地保留相對平滑的特征.

圖5　Bunny模型特征提取Fig.5　Feature extraction of Bunny model

圖6　Fandisk模型特征提取Fig.6　Feature extraction of Fandisk model

圖7Dragon模型特征提取Fig.7　Feature extraction of Dragon model

2.3噪聲及時間效率

2.3.1本文算法噪聲分析

本文在兩類不同的模型上進行實驗，檢測本文算法的魯棒性，即：人工添加的含有統(tǒng)一噪聲的模型及由三維掃描獲取的含有不統(tǒng)一噪聲的模型.

本文首先對Fandisk模型人工添噪，并提取特征點.加入噪聲的方式是將噪聲點云位置偏移原位置某一距離.

表2　含噪聲模型特征提取對比表Table 2　Comparison of feature points extracted with noise model

圖8為Fandisk模型在不同尺度噪聲下的特征提取結(jié)果［22］.實驗結(jié)果表明，本文算法對噪聲不敏感.在噪聲尺度適中的情況下，該算法具有較好的魯棒性.

2.3.2本文算法與對比實驗的時間性能分析

表3中列出了本文算法、張量投票法、閾值檢測法的時間效率.

由表3可知，本文算法的時間效率優(yōu)于張量投票法及閾值檢測法.本文算法的時間效率和采樣點數(shù)及標號分類密切相關.首先，本文對于初始標號時選取曲率估計，其相對于局部擬合計算主曲率節(jié)省時間開銷；接著采用馬爾科夫隨機場模型解決問題.針對該模型，采樣點數(shù)及標號種類越多，時間開銷越大.而任何模型進行特征提取，標號種類均為2（特征點、非特征點）.因此，對于采樣點相同的模型，該算法的時間性能有所改善.

表3　算法時間效率對比表Table 3　Comparison table of algorithm time efficiency

2.4點采樣密度敏感性

為了測試本文算法對不均勻采樣的點云特征提取效果，本文將模型進行簡化，得到具有相同曲面不同采樣密度的模型，并對特征提取結(jié)果的不同視角進行展示分析.圖5為Bunny模型提取結(jié)果，圖9（a1）是將點簡化到35%的Bunny模型，圖9（b1）、（c1）、（d1）是對應圖9（a1）的簡化模型的特征提取結(jié)果，實驗結(jié)果表明對于該簡化模型，本文方法提取結(jié)果比較理想，即本文算法對采樣密度并不敏感；而圖9（a2）是簡化到24%的Bunny模型，圖9（b2）、（c2）、（d2）是對應圖9（a2）的特征提取結(jié)果，實驗結(jié)果表明該算法誤將非特征點當作特征點提取出來，導致特征點的誤判.因此，本文算法對于過于稀疏的點云模型效果不理想.

圖8　帶噪聲模型提取特征點數(shù)對比Fig.8　Fandisk feature extraction with different noise amplitude

3　結(jié)論

本文針對散亂點云模型的特征提取問題提出一種基于馬爾科夫隨機場的特征提取方法.首先，計算每個點的曲率估計及閾值，比較點的曲率估計與閾值，初始化標號場，識別穩(wěn)定點并將其標記存儲在數(shù)組中；然后，由不穩(wěn)定點屬性信息的聯(lián)合分布函數(shù)以及隨機場的狀態(tài)分布函數(shù)計算目標函數(shù)，求解目標函數(shù)得到不穩(wěn)定點的最優(yōu)標號集；最后，綜合不穩(wěn)定點的最優(yōu)標號集與存儲穩(wěn)定點的數(shù)組，根據(jù)點標號提取特征點.實驗結(jié)果表明本文算法能有效地提取尖銳特征并盡可能多保留較平滑的特征，同時算法簡單易懂.與傳統(tǒng)的特征檢測方法相比，此方法的自適應性提高了特征提取的準確率，減少了特征點的誤判率.

盡管本文方法能提取出尖銳特征點并盡可能多地保留較平滑特征，但仍存在改進空間.本文算法不適用于過度稀疏的點云模型.針對這一問題，下一步將考慮采用啟發(fā)式算法解決稀疏模型的特征提取問題.

圖9　Bunny簡化模型特征提取結(jié)果Fig.9　Feature extraction of simplified Bunny model

References

1 Daniels J，Ha L K，Ochotta T，Silva C T.Robust smooth feature extraction from point clouds.In：Proceedings of the 2007 IEEE International Conference on Shape Modeling and Applications.Lyon，F(xiàn)rance：IEEE，2007.123-136

2 Demarsin K，Vanderstraeten D，Volodine T，Roose D.Detection of closed sharp feature lines in point clouds for reverse engineering applications.In：Proceedings of the 4th International Conference.Pittsburgh，PA，USA：Springer，2006.571-577

3 Pang Xu-Fang，Pang Ming-Yong，Xiao Chun-Xia.An algorithm for extracting and enhancing valley-ridge features from point sets.Acta Automatica Sinica，2010，36（8）：1073-1083（龐旭芳，龐明勇，肖春霞.點云模型谷脊特征的提取與增強算法.自動化學報，2010，36（8）：1073-1083）

4 Tombari F，Salti S，Stefano L D.Performance evaluation of 3D keypoint detectors.International Journal of Computer Vision，2013，102（1-3）：198-220

5 Pauly M，Keiser R，Gross M.Multi-scale feature extraction on point-sampled surfaces.Computer Graphics Forum，2003，22（3）：281-289

6 Guo Y L，Bennamoun M，Sohel F，Lu M，Wan J W.3D object recognition in cluttered scenes with local surface features：a survey.IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36（11）：2270-2287

7 Guo Y L，Bennamoun M，Sohel F，Lu M，Wan J W，Kwok N M.A comprehensive performance evaluation of 3D local feature descriptors.International Journal of Computer Vision，2016，116（1）：66-89

8 Ho H T，Gibbins D.Curvature-based approach for multiscale feature extraction from 3D meshes and unstructured point clouds.IET Computer Vision，2009，3（4）：201-212

9 Gumhold S，Wang X L，MacLeod R.Feature extraction from point clouds.In：Proceedings of the 10th International Meshing Roundtable.Berlin：Springer Press，2001.293-305

10 Jia J Y，Tang C K.Tensor voting for image correction by global and local intensity alignment.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（1）：36-50

11 Tang C K，Medioni G.Inference of integrated surface，curve and junction descriptions from sparse 3D data.IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20（11）：1206-1223

12 Wushour S，Cao Ju-Ming.An extraction algorithm for sharp feature points from point clouds.Journal of Xi′an Jiaotong University，2012，46（12）：1-5（吾守爾·斯拉木，曹巨明.一種新的散亂點云尖銳特征提取方法.西安交通大學學報，2012，46（12）：1-5）

13 Wang Li-Hui，Yuan Bao-Zong.Feature point detection for 3D scattered point cloud model.Signal Processing，2011，27（6）：932-938（王麗輝，袁保宗.三維散亂點云模型的特征點檢測.信號處理，2011，27（6）：932-938）

14 Longjiang E，Waseem S，Willis A.Using a MAP-MRF model to improve 3D mesh segmentation algorithms.In：Proceedings of the 2013 IEEE Southeastcon.Jacksonville，F(xiàn)L：IEEE，2013.1-7

15 Lavou′e，Wolf C.Markov random fields for improving 3D mesh analysis and segmentation.In：Proceedings of the 1st Eurographics Conference on 3D Object Retrieval.Switzerland，Switzerland：Eurographics Association Aire-la-Ville，2008.25-32

16 Lu Xiao-Xin.Research on 3D Mesh Segmentation Algorithms Using Markov Random Filed［Master dissertation］，Harbin Institute of Technology，China，2010（盧孝新.基于馬爾科夫隨機場的三維網(wǎng)格模型分割算法研究［碩士學位論文］，哈爾濱工業(yè)大學，中國，2010）

17 Ren Ran.Research on Image Segmentation Method Based on Markov Random Field［Master dissertation］.Anhui University of Technology，China，2013（任然.基于Markov隨機場的圖像分割方法研究［碩士學位論文］，安徽工業(yè)大學，中國，2013）

18 Hoppe H，DeRose T，Duchamp T，McDonald J，Stuetzle W.Surface reconstruction from unorganized points.In：Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques.New York，NY，USA：ACM，1992.71-78

19 Wang Xiao-Chao，Liu Xiu-Ping，Li Bao-Jun，Zhang Shao-Guang.Feature detection on point cloud via local reconstruction.Journal of Computer-Aided Design&Computer Graphics，2013，25（5）：659-665（王小超，劉秀平，李寶軍，張紹光.基于局部重建的點云特征點提取.計算機輔助設計與圖形學學報，2013，25（5）：659-665）

20 Cohen-Steiner D，Morvan J M.Restricted delaunay triangulations and normal cycle.In：Proceedings of the 19th Annual Symposium on Computational Geometry.New York，USA：ACM，2003.312-321

21 Alexa M，Behr J，Cohen-Or D，F(xiàn)leishman S，Levin D，Silva C T.Computing and rendering point set surfaces. IEEE Transactions on Visualization and Computer Graphics，2003，9（1）：3-15

22 Webber C，Hahmann S，Hagen H.Sharp feature detection in point clouds.In：Proceedings of the 2010 Shape Modeling International Conference.Aix-en-Provence，F(xiàn)rance：IEEE，2010.175-186

張靖西北大學信息科學與技術學院碩士研究生.主要研究方向為圖像處理，可視化技術.

E-mail:zj18710812436@163.com

（ZHANG JingMaster student at the College of Information Science and Technology，Northwestern University. Her research interest covers computer graphics and visualization.）

周明全北京師范大學信息科學與技術學院教授.主要研究方向為虛擬現(xiàn)實與可視化技術，智能信息處理，數(shù)據(jù)庫與知識庫，圖形圖像處理.本文通信作者.

E-mail:mqzhou@nwu.edu.cn

（ZHOUMing-QuanProfessorat the College of Information Science and Technology，Beijing Normal University. His research interest covers virtual reality and visualization technology，intelligent information processing，database and knowledge base，graphics and image processing.Corresponding author of this paper.）

張雨禾西北大學信息科學與技術學院博士研究生.主要研究方向為計算機圖形圖像處理與可視化技術.

E-mail:zhangyuhe0601@126.com

（ZHANG Yu-HePh.D.candidate at the College of Information Science and Technology，Northwestern University.Her research interest covers computer graphics and visualization.）

耿國華西北大學信息科學與技術學院教授.主要研究方向為智能信息處理，數(shù)據(jù)庫與知識庫，圖形圖像處理.

E-mail:ghgeng@nwu.edu.cn

（GENG Guo-HuaProfessor at the CollegeofInformationScienceand Technology，Northwestern University. Her research interest covers intelligent information processing，dat abase and knowledge base，graphics and image processing.）

Global Feature Extraction from Scattered Point Clouds Based on Markov Random Field

ZHANG Jing1ZHOU Ming-Quan1，2ZHANG Yu-He1GENG Guo-Hua1

In order to extract the feature information of point clouds data accurately，a new method of feature extraction based on Markov random field（MRF）is proposed.First based on scattered point of curvature estimation and the threshold to initialize labels and determine the stability，the stable point marks stored in the array.Second，the problem of optimal unstable label transform to energy function of the label of the airport.By citing Bayesian estimation for posterior probability distribution function and the MAP-MRF（Maximum a posteriori-Markov random field）reduction，objective function is obtained.Finally according to the graph cut algorithm，using label adjustment process label set relative energy changes get optimal labels of unstable set，and the stable storage array synthesis，by labels rapidly extracts feature points. Experimental results show that the proposed method is simple and fast，and does not need manual setting of threshold. According to the change of global energy，the optimal labeling and feature points are extracted.

Scattered point cloud，feature extraction，Markov random field（MRF），label

10.16383/j.aas.2016.c150627

Zhang Jing，Zhou Ming-Quan，Zhang Yu-He，Geng Guo-Hua.Global feature extraction from scattered point clouds based on Markov random field.Acta Automatica Sinica，2016，42（7）:1090-1099

2015-10-10錄用日期2016-01-19
Manuscript received October 10，2015；accepted January 19，2016
國家自然科學基金（61373117，61305032），高等學校博士學科點專項科研基金（20136101110019），陜西省教育廳科研專項（2013JK1180）資助
Supported by National Natural Science Foundation of China （61373117，61305032），Special Research Fund for the Doctoral Program of Higher Education（20136101110019），and Shaanxi Provincial Department of Education Research（2013JK1180）
本文責任編委吳建鑫
Recommended by Associate Editor WU Jian-Xin
1.西北大學信息科學與技術學院西安7101272.北京師范大學信息科學與技術學院北京100875
1.College of Information Science and Technology，Northwestern University，Xi′an 7101272.College of Information Science and Technology，Beijing Normal University，Beijing 100875