一種基于點集體素的多質物體分界面提取方法研究

寧小娟，劉 瑛，王怡軒，王映輝

(西安理工大學 計算機科學與工程學院，陜西 西安 710048)

多質物體的分界面提取是三維數據場可視化、逆向工程、三維重建領域的一個研究熱點，也在醫學、地質勘探等方面有著重要的應用。傳統的等值面提取方法適用于標量場的可視化問題[1-2]。然而，在現實生活中幾乎所有的物體都由三種或三種以上的材質組成，等值面提取方法很難支撐含有超過三種材質物體的重建工作。因此，提取多質物體分界面成為了當前研究工作的重點[3]。

目前，已有許多學者對多質物體分界面的提取展開了相關研究。Shamma等[4]提出一種提取多質物體等值面的方法。該方法首先將區域生長算法[5]和圖割算法[6]相結合，對同一類材質的體素進行歸類，然后使用移動立方體算法獲取三角網格表示的各物質的分界面，但是當多質物體包含三種以上的不同介質時，由該算法提取的分界面變得不理想。Shamma等[7]又提出一種多圖像分割方法提取體數據圖像的邊界表面。該方法首先確定一個初始種子區域，然后在邊緣梯度小的地方使用限制的區域增長方法，最后使用速度函數進行輪廓擴張，直到給出整個圖像的分割結果，從而獲得邊界表面。王明等[8-9]提出了對異質物體分界面提取與邊界面重構的方法。該方法對已經標識材質的體數據分別提出了基于四面體和三棱柱的分界面提取方法，但是該算法不能一次性提取所需要的多個分界面。Wu等[10]提出一種能夠處理多介質物體的移動立方體算法。Wang[11]提出了一個采用隱式的網格化形式表示多質物體分界面的方法，但是該算法無法保留分界面之間的邊界信息。Wang等[12]提出一種從醫學圖像中檢測具有連續變化的梯度幅度邊界表面的方法。Zhang等[13]提出一種基于擴展加權最小二乘的體數據去噪方法，實現了多質物體的分界面提取，該方法在去除噪聲的同時也能夠保持清晰的特征。Ju等[14]提出一種擴展的移動立方體算法，將移動立方體算法和對偶算法相結合提取分界面，但是當介質數量超過三種時，該算法的效果明顯下降。因此，本文通過給圖像的每個像素點賦予相應的三維坐標，將其轉為點集體素數據，在此基礎上利用改進的球面收縮方法，一次提取出多質物體的所有分界面，然后對所有分界面進行分割與優化，從而確定各個分界面間的拓撲關系。

1 多質物體分界點標識

1.1 分界點的凸顯

由于直接采用球面收縮方法對多質物體進行分界面提取時，會存在噪聲點和局部分界面不清晰等問題。因此，本文在提取分界面之前先進行分界點的凸顯。

1.1.1Gauss濾波去噪

在圖像處理中，Gauss濾波方法[15]具有一定的去噪效果，可以通過調整Gauss分布參數σ改變平滑的程度。它的思想是對整幅圖像的每個像素點加權平均，每個像素點的值都由其本身和鄰域內的像素值通過加權平均得到。其具體實現過程是使用一個模板掃描圖像中的每個像素，用模板確定的鄰域內像素的加權平均值替代模板中心像素點的灰度值。該方法中使用的Gauss模板是通過離散化二維Gauss函數得到的，計算公式為：

(1)

式中：m和n表示圖像的大小。

具體的去噪流程如下：

1) 計算Gauss模板。用式(1)計算Gauss模板M，M的大小為(2k+1)×(2k+1)，那么矩陣中的元素mi,j及矩陣M為:

(2)

(3)

2) Gauss濾波。滑動Gauss模板，使其中心位于圖像I的(x,y)像素上，(x,y)位置的計算式為：

(4)

對整幅圖像的每個像素運用式(4)即可得到Gauss濾波結果。本文給圖像的每個像素點賦予了相應的三維坐標，對每個具體點迭代執行從而實現去噪。

1.1.2基于權重的分界點凸顯

基于權重的分界點凸顯是給鄰域中心點及其鄰域點賦予權重，以此來增大點的自身灰度值，減小其鄰域點的灰度值，這樣就可以增大鄰域中心點與其鄰域點灰度的差值，也更加合理地利用鄰域對鄰域中心的影響，從而凸顯分界點。該方法的主要步驟為如下。

1) 計算權重矩陣。根據Gauss分布設定了一個權重矩陣，并將其歸一化，得到一個3×3的權重矩陣W：

(5)

2) 計算任意一點P的灰度值結果。將點P的灰度值乘以權重矩陣中心元素值，P的鄰域點的灰度值乘以權重矩陣中相應的權重值，然后用點P的計算結果和它的每一個鄰域點的計算結果作差值，并對所有差值求和，該求和結果作為點P的灰度值。對于圖像I(x,y)，被權重矩陣W覆蓋的圖像部分記為矩陣F：

(6)

F各位置對應的灰度值記為矩陣G：

(7)

式中：0≤gij≤255,1≤i≤3,1≤j≤3。

以圖像的(0,0)位置作為起始位置，首先將權重矩陣W的中心元素與待處理點(0,0)重合，然后計算待處理點(0,0)的權重凸顯結果。權重矩陣覆蓋的圖像的每個點加權結果記為resultij：

resultij=wij·gij

(8)

式中：1≤i≤3,1≤j≤3。記中心位置的結果為center，center=w22·g22那么待處理點(0,0)處的灰度值為(下式中對i,j同時求和)：

∑|resultij-center|

(9)

3) 對所有點迭代步驟2)，當所有點都計算結束時得到凸顯分界點的結果。

以物體的一個截面為例，基于權重的分界點凸顯方法見圖1。圖1(c)讓權重矩陣中心(圖1(a)紅色框)與圖像灰度示意圖上的點(0,0)位置(圖1(b)紅色框)重合，計算權重矩陣每個元素和圖像中對應位置灰度值的乘積，然后用權重中心處的結果和各個鄰域點結果作差值，再對差值求和，該求和結果作為點(0,0)位置的灰度值。再次移動權重矩陣(如圖1(d)所示)，使權重矩陣中心元素和處理點(0,1)重合，計算(0,1)位置的灰度值，依次按照該過程迭代處理所有點即可得到凸顯分界點的結果。

圖1 凸顯分界點示意圖

1.1.3基于球形鄰域的分界點標識

通常描述某個點的局部特征時，需要借助其鄰域點的信息。

鄰域是一個特殊的區間，以點a為中心點的任何開區間稱為點a的鄰域，記作U(a)。對于任意一個點O，以O為圓心，定長r為半徑作一個球，包含在該球內的點屬于點O的球形鄰域點[16]。

設以點O為球心的球形鄰域中點的數量為n，點集為S，S={si∈S|0≤i≤n}，si表示第i個點，每個點對應的灰度值的集合為G，G={gi∈G|0≤i≤n,0≤gi≤255}，gi表示第i個點的灰度值，球心O的灰度值為go，則球心O的梯度grado為：

(10)

按照式(10)對每個點基于球形鄰域進行轉換計算，得到新的數據點集。材質相同的點集則灰度值都接近于0，而材質不同的點集則灰度值遠大于0。按照此過程，本文完成一個個截面的分界點標識工作，將這些截面組合起來即可得到整個物體的分界點標識結果。

2 多質物體的分界面提取

2.1 改進的球面收縮方法

由于在球面收縮方法中，球面點遇到分界面就停止不再移動。因而，自遮擋部分的分界面上也就沒有收縮后的球面點。針對此問題，本文對球面收縮方法進行改進，使得球面點在向球心移動的過程中，每遇到一次分界面就停止，并將球面點加入到提取分界面的結果中，直到球面點遇到球心，該球面點停止移動。同時由于分界面具有一定的厚度，因此，本文給所有的球面點設置一個標志位，標志位有0和1兩個狀態，0表示未遇到分界面，1表示遇到分界面。球面點的初始狀態都為0，在移動的過程中檢測到球面點遇到分界面時，設置球面點的標志位為1。接著讓球面點繼續向球心移動，移動過程中檢測球面點的小球形鄰域是否包含分界點，當檢測到球面點的小球形鄰域中沒有分界點時，標記該球面點的狀態為0，再繼續向球心移動。通過這個方法可以使得球面點在同一個分界面上只停留一次，從而達到提取分界面的目的。

根據以上思路，改進后的球面收縮方法的具體過程分為以下四步。

1) 采用均值法[17]作物體的最小外接球，設球面點集的集合為P。

2) 對球面上任意一點pi，沿球心方向以一定的步長向球心O移動。在移動過程中檢測點pi是否遇到球心O，如果遇到球心則點pi停止移動。反之，檢測點pi是否遇到分界面，如果遇到分界面則點pi停止移動，并將點pi加入到提取分界面的結果中，同時將點pi的狀態設置為1。

3) 點pi繼續向球心移動，移動過程中檢測點pi的小球形鄰域是否有分界點，如果沒有就設置點pi的狀態為0，然后pi執行步驟2)。

4) 球面上所有的點都執行步驟2)和步驟3)操作，直到所有球面點全部移動到球心為止。

2.2 多質分界面的分割

在球面收縮方法中，球面點向球心移動的過程中遇到分界面是有先后順序的,因此利用球面點遇到分界面的先后順序進行分類，將同一順序檢測到分界面的球面點聚為一類，作為一個分界面，從而實現多分界面的基礎分割。

該方法的具體實現過程是：在生成物體的最小外接球時，給球面點設置一個順序屬性type，并初始化所有球面點的type為0。在球面點向球心O移動的過程中，球面點每遇到一次分界面，球面點的順序屬性type就加1，當所有球面點都收縮結束時，將相同type的球面點聚為一類，表示一個分界面。

圖2描述了基于球面點收縮順序的分割方法。圖中綠色點表示球面點，紅色點表示第一次收縮到分界面上的球面點，藍色點表示第二次收縮到分界面上的球面點。

圖2 基于球面點收縮順序的分割方法示意圖

球面點在向球心O移動的過程中，第一次遇到分界面上的點是圖中角α對應弧上的球面點，將這部分球面點的順序屬性type標記為1。然后球面點穿過分界面繼續向球心移動，第二次遇到分界面上的點是圖中角β對應弧上的球面點，將這部分球面點的順序屬性type標記為 2。球面收縮后，根據球面點的順序屬性type，把順序屬性相同的球面點聚類。將type為1的球面點聚為一類并標記為紅色，type為2的球面點聚為一類并標記為藍色，實現了采用球面點收縮順序進行分類的方法。

2.3 優化分割結果

由圖2可觀察到，圖中左下角紅色點和藍色點(右上角紅色點和藍色點)其實屬于同一分界面，造成這一分割結果是由于在球面收縮方法中，球面點收縮順序受分界面自身遮擋的影響，使得分割結果不準確。針對此問題，本文采用基于距離的聚類方法對多質分界面的結果進行進一步的優化。

首先，通過球面點收縮順序的方法得到各個聚類，按照順序屬性值從小到大依次以每一個類為初始聚類中心，進行基于距離的聚類，將剩余類中滿足距離條件的點加入到這個類中，直到沒有點加入時停止，得到一個聚類結果。然后，選擇剩余點中最小順序值的那一類作為新的聚類中心進行迭代，直到沒有剩余的點時優化結束。例如，圖2中紅色點的順序屬性type值為1，藍色點的順序屬性type值為2。首先，以紅色點為聚類中心，檢測type值大于1的點，將其與紅色點集中任意一點的距離小于一定閾值的點的順序屬性type設置為1，加入到紅色點集中，直到沒有點可以加入時結束。這樣就可以通過基于距離的聚類方法將圖2中左下角(或右上角)的藍色點加入到左下角(或右上角)的紅色點類中，表示一個分界面，從而實現多質分界面提取結果的優化。

3 實驗結果與分析

3.1 實驗環境與實驗數據

本文實驗的硬件平臺為：CPU 為Intel Core i5-4460 3.2 GHz，內存為4GB，操作系統為Windows 7(64位)，編程平臺為Visual Studio 2010。

本文的實驗數據集包括兩部分：一種是合成數據，一種是點集體素數據。本文中的Tomato數據主要是以PVM格式存儲。對PVM格式的體數據，使用V3程序(來自：http://www.informatik.ni-erlangen.de)提供的PVM2RAW可執行程序將其轉換為RAW格式，基于RAW格式進行進一步的處理。

3.2 分界點標識結果

為了驗證本文方法的有效性，本文在相關的實驗數據集上進行了實驗。本文按照Gauss去噪、分界點標識、最后進行基于球形鄰域的標識分界點，實驗結果見圖3。圖3(a)和3(d)中紅色框部分，可以看出紅色框中該局部物質的灰度值和其周圍鄰域物質的灰度值過于相近，難以區分開來。然而，圖3(d)紅色框中該物質的灰度值和其周圍鄰域物質的灰度值已經有了很明顯的差異，圖3(c)是去噪后進行分界點標識，圖3(d)可觀察到在不丟失邊界的前提下，可以將占整個物體體積比例很小的異質物體的邊界清晰的表示出來。實驗表明本文方法可以更加準確地標定出分界點，也較好地解決了受鄰域信息影響導致的局部分界面不清晰的問題。

圖3 Tomato模型截面的標識分界點結果

同時為了驗證本文方法的效果，我們進行了對比實驗，如圖4所示。

圖4 對比實驗

圖4(a)為原始數據直接進行標識分界點的結果，該結果對于整個物體體積比例很小的異質物體的邊界描述不清晰。圖4(b)為凸顯邊界點然后去噪再標識分界點的結果，可以看出其中的噪聲點仍然較多。圖4(c)為凸顯邊界點然后標識分界點再進行去噪的結果，此結果會導致邊界缺失不清晰。圖4(d)為本文方法，本文方法得到的效果相比較而言噪聲少，邊界較清晰。

3.3 分界面提取結果

本文分別針對由立方體和球體構成的多質物體以及Tomato模型進行多分界面提取實驗。實驗結果分別見圖5和圖6所示。

圖5 多質物體分界面提取結果

圖6 Tomato模型多質物體分界面提取結果

圖5(a)是一個立方體里面包含兩個相同的球體，圖5(d)是球面收縮的結果，且收縮效果良好，球面收縮結果截面圖5(e)也證實了這一點。從圖中可以看出球面點(綠色點)很好地描述出了兩個球體各自的形狀，而其中有一部分球面點收縮到了球體的內分界面上(圖5(e)紅色框所示)，但兩個球體的分界面很薄，對提取分界面的結果影響較小。圖5(g)是在5(f)的基礎上基于球面點收縮順序的方法分割多分界面的結果。從圖5(h)可以看出球面點收縮到球體的外分界面上和內分界面上表示出的結果不同。球面點收縮到球體外分界面上的結果如圖5(h)中的紅色點所示，球面點收縮到球體內分界面上的結果如圖5(h)中的藍色點所示，這個分割結果把收縮到兩個球體分界面上的外側點和內側點各分為一類，該分割結果是不正確的。圖5(i)是在5(g)的基礎上采用基于距離的聚類方法對分割的分界面進行優化，因而得到了如圖5(k)和5(l)所示正確的分割結果。

圖6是對Tomato模型進行多分界面提取的實驗結果。Tomato模型的球面收縮結果如圖6(e)所示，可以觀察到球面點(綠色點)都較好地貼合了Tomato模型中的各個分界面(黑色點)，收縮效果良好。對比圖6(b)和6(f)可以觀察到，提取的多分界面結果能良好的描述Tomato模型的外輪廓以及Tomato模型中的各個分界面，提取多分界面結果截面圖6(g)也印證了這一點。其次，對提取到多分界面的結果(圖6(f))采用基于球面點收縮順序方法進行多分界面的分割。分割結果如圖6(h)和6(i)所示，圖中不同的顏色表示球面點不同的收縮順序，圖6(i)為其分割結果截面圖，從圖中可以觀察到從邊緣到中心，球面點的順序值逐漸增大。最后，對多分界面的分割結果(圖6(h))采用基于距離的聚類方法進行優化，其優化結果如圖6(g)～6(n)所示。其中，圖6(j)是優化后的多分界面分割結果圖，圖6(k)和6(l)是優化分割結果截面圖，圖6(m)和6(n)是最終得到的分割結果。

4 結 論

本文提出了一種基于點集體素的多質物體分界面提取方法，該方法可以正確有效地一次性提取多質物體的所有分界面，多個實驗表明本文的提取效果良好。但是采用本文方法解決分界面自身遮擋問題時，有部分球面點會停留在分界面的內邊界，雖然不影響對整個分界面的外形描述，但是結果不夠準確。因此，在今后的研究工作中仍需進行深入的探索。