基于馬爾科夫隨機(jī)場(chǎng)的散亂點(diǎn)云全局特征提取

張靖　　周明全，2　　張雨禾　　耿國(guó)華

基于馬爾科夫隨機(jī)場(chǎng)的散亂點(diǎn)云全局特征提取

張靖1周明全1，2張雨禾1耿國(guó)華1

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

散亂點(diǎn)云，特征提取，馬爾科夫隨機(jī)場(chǎng)，標(biāo)號(hào)

引用格式張靖，周明全，張雨禾，耿國(guó)華.基于馬爾科夫隨機(jī)場(chǎng)的散亂點(diǎn)云全局特征提取.自動(dòng)化學(xué)報(bào)，2016，42（7）: 1090-1099

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

目前，已有諸多學(xué)者展開了針對(duì)三維模型特征提取的研究，而大部分方法是針對(duì)網(wǎng)格曲面等含有較多拓?fù)湫畔⒌哪Ｐ瓦M(jìn)行處理.由于點(diǎn)云模型缺少頂點(diǎn)間的拓?fù)溧徑雨P(guān)系，且不包含任何曲面和體積的信息，難以計(jì)算其物理性質(zhì)和幾何性質(zhì)，因此，針對(duì)點(diǎn)云數(shù)據(jù)的處理方法較少，大致可以分為三類：基于局部擬合或聚類的方法、基于多尺度的思想以及基于特征檢測(cè)算子的方法.

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

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

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

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

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

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

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

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

1　基于馬爾科夫隨機(jī)場(chǎng)的點(diǎn)云特征提取算法

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

1.1初始化散亂點(diǎn)云標(biāo)號(hào)場(chǎng)

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

然后對(duì)曲率估計(jì)求平均值并設(shè)定閾值θ，本文選取一個(gè)較為寬松的閾值以保留盡可能多的潛在特征點(diǎn)，并在后續(xù)的標(biāo)號(hào)優(yōu)化時(shí)精確提取特征點(diǎn).閾值為

根據(jù)閾值初始化點(diǎn)標(biāo)號(hào)，得到初始標(biāo)號(hào)場(chǎng)，曲率絕對(duì)值大于閾值的點(diǎn)標(biāo)記為特征點(diǎn)，其標(biāo)號(hào)置為1；否則，標(biāo)記為非特征點(diǎn)，標(biāo)號(hào)置為2：

由此得到初始標(biāo)號(hào)場(chǎng)f=｛f1，f2，···，fN｝，其中fi是指第i個(gè)點(diǎn)的標(biāo)號(hào).

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

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

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

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

b）由當(dāng)前的參數(shù)估計(jì)每個(gè)數(shù)據(jù)與每個(gè)類之間的相關(guān)性：

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

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

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

本文僅考慮雙點(diǎn)勢(shì)團(tuán)的能量［12］.

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

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

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

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

使用MAP的實(shí)質(zhì)就是將標(biāo)記分類的概率誤差最小化，即當(dāng)觀測(cè)隨機(jī)變量即點(diǎn)的相關(guān)屬性給定時(shí)，每一個(gè)點(diǎn)屬于哪一個(gè)標(biāo)號(hào)的概率最大，就將該標(biāo)號(hào)賦予這個(gè)點(diǎn)，最后這些散亂點(diǎn)的標(biāo)號(hào)組成的集合即為最優(yōu)標(biāo)號(hào)集.

定義U（f|d）為

其中，U（d|f）為

由貝葉斯定理可知：

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

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

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

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

1.3散亂點(diǎn)云標(biāo)號(hào)場(chǎng)的優(yōu)化

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

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

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

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

α-expansion算法的具體步驟為

1.4提取特征點(diǎn)

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

2　實(shí)驗(yàn)結(jié)果與分析

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

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

2.1本文方法實(shí)驗(yàn)

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

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

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

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

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

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

2.2對(duì)比實(shí)驗(yàn)

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

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

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

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

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

圖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噪聲及時(shí)間效率

2.3.1本文算法噪聲分析

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

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

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

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

2.3.2本文算法與對(duì)比實(shí)驗(yàn)的時(shí)間性能分析

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

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

表3　算法時(shí)間效率對(duì)比表Table 3　Comparison table of algorithm time efficiency

2.4點(diǎn)采樣密度敏感性

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

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

3　結(jié)論

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

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

圖9　Bunny簡(jiǎn)化模型特征提取結(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（龐旭芳，龐明勇，肖春霞.點(diǎn)云模型谷脊特征的提取與增強(qiáng)算法.自動(dòng)化學(xué)報(bào)，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（吾守爾·斯拉木，曹巨明.一種新的散亂點(diǎn)云尖銳特征提取方法.西安交通大學(xué)學(xué)報(bào)，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（王麗輝，袁保宗.三維散亂點(diǎn)云模型的特征點(diǎn)檢測(cè).信號(hào)處理，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（盧孝新.基于馬爾科夫隨機(jī)場(chǎng)的三維網(wǎng)格模型分割算法研究［碩士學(xué)位論文］，哈爾濱工業(yè)大學(xué)，中國(guó)，2010）

17 Ren Ran.Research on Image Segmentation Method Based on Markov Random Field［Master dissertation］.Anhui University of Technology，China，2013（任然.基于Markov隨機(jī)場(chǎng)的圖像分割方法研究［碩士學(xué)位論文］，安徽工業(yè)大學(xué)，中國(guó)，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（王小超，劉秀平，李寶軍，張紹光.基于局部重建的點(diǎn)云特征點(diǎn)提取.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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

張靖西北大學(xué)信息科學(xué)與技術(shù)學(xué)院碩士研究生.主要研究方向?yàn)閳D像處理，可視化技術(shù).

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.）

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

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.）

張雨禾西北大學(xué)信息科學(xué)與技術(shù)學(xué)院博士研究生.主要研究方向?yàn)橛?jì)算機(jī)圖形圖像處理與可視化技術(shù).

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.）

耿國(guó)華西北大學(xué)信息科學(xué)與技術(shù)學(xué)院教授.主要研究方向?yàn)橹悄苄畔⑻幚?，?shù)據(jù)庫與知識(shí)庫，圖形圖像處理.

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
國(guó)家自然科學(xué)基金（61373117，61305032），高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金（20136101110019），陜西省教育廳科研專項(xiàng)（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）
本文責(zé)任編委吳建鑫
Recommended by Associate Editor WU Jian-Xin
1.西北大學(xué)信息科學(xué)與技術(shù)學(xué)院西安7101272.北京師范大學(xué)信息科學(xué)與技術(shù)學(xué)院北京100875
1.College of Information Science and Technology，Northwestern University，Xi′an 7101272.College of Information Science and Technology，Beijing Normal University，Beijing 100875