基于深度信念網絡的異常點集間的匹配算法

李 舫，張 挺

(上海電力學院 計算機科學與技術學院，上海 200090)(*通信作者電子郵箱tingzh@shiep.edu.cn)

0 引言

點集配準是計算機視覺、醫學圖像分析、模式識別和信號處理的基本和關鍵問題之一[1-3]。點集配準的目標是找到兩個點集之間的正確匹配關系，并確定出能對準它們的空間變換。通常從圖像中提取或由3D掃描儀生成的點集所表示的物體表面，由于測量方法的可變性、實驗誤差、光照變化等因素，不可避免地在圖像采集和特征提取的過程中產生噪聲、異常值和缺失點。因此，點集配準問題面臨著一些挑戰，最關鍵的挑戰之一是能否在存在異常值、缺失點和噪聲的情況下建立正確的匹配關系。

已有研究提出了迭代算法以解決配準問題，它交替地估計匹配關系和計算變換關系以獲得近似最優解。這類方法使用的匹配關系是基于局部特征描述符的，其中，典型的迭代最近點(Iterative Closest Point, ICP)算法就是試圖將兩組點之間的距離最小化[4]?？紤]到這種點對點的匹配關系，ICP的一個重要缺陷就是缺乏對噪聲、異常值和缺失點的穩健性。針對這個問題已經作了一些研究，如:文獻[5-8]提出了魯棒點匹配(Robust Points Matching, RPM)及其變體算法，并廣泛用于非剛性配準。 RPM方法使用軟分類、松弛點匹配關系的變量以建立模糊匹配，并采用確定性模擬退火方法逐步估計點的匹配關系。雖然模糊匹配減輕了噪聲等的影響，但錯誤的匹配關系仍然存在。另一方面的研究是基于概率統計理論的新度量方法建立點集間的匹配關系，其中連續密度函數，如高斯混合模型(Gaussian Mixture Model, GMM)被用來表示點集[9-12]。文獻[9]利用一致點漂移(Coherent Point Drift, CPD)之類的概率方法將配準視為最大似然估計問題；文獻[10]則基于GMM的方法將配準視為與點集相應的兩個分布之間的對準。

為了提高算法對異常值、噪聲和缺失點的魯棒性，文獻[1]利用基于混合模型的流形正則化一致向量場(Manifold Regularized Coherent Vector Field, MRCVF)從異常點集中排除外部數據，尋求點集間的正確匹配關系。由此，考慮到正常點和異常點之間存在某種關系或區別的先驗知識，可以通過機器學習的過程來模擬對匹配關系的估計。本文提出了一種基于深度信念網絡(Deep Belief Network, DBN)的學習方法來訓練具有正常點集的網絡，使用訓練好的DBN就可以在異常點集中識別異常值和不匹配的點，從而實現魯棒的點集配準。

1 點集間匹配關系的學習框架

1.1 基于深度信念網絡的學習

作為一種無監督學習方法，DBN可以使用訓練數據集來訓練獲得數據的特征表示。DBN是通過限制玻爾茲曼機器(Restricted Boltzmann Machine, RBM)的多級連接組成的，在RBM中一個可見層和一個隱藏層之間是雙向和完全連接的[13]。DBN的結構如圖1所示。

圖1 DBN 的結構Fig. 1 Structure of DBN

波爾茲曼機器(BM)是對數線性馬爾可夫隨機場(Markov Random Field, MRF)的一種特殊形式，RBM將BM限制為沒有可見層-可見層連接和隱藏層-隱藏層連接關系的BM。RBM的能量函數定義如下:

(1)

其中:vi和hj分別表示可見層和隱含層的單元;bi和cj分別表示可見單元和隱層單元的偏差;Wij表示連接可見單元和隱藏單元的權重。機器學習的過程中需要通過給DBN輸入訓練樣本集，學習可見層和隱藏層的偏差向量以及兩層之間的權重矩陣，以便使網絡能夠表征數據的分布。

1.2 利用DBN學習點集之間的匹配關系

實際中的采樣點集可能會出現某些異常情況，如噪聲、異常值和缺失數據等，這可能會影響點集之間匹配關系的確定。因此，有必要學習檢測數據中存在的異常點，以利于在兩個采樣點集之間建立正確的匹配關系。

假設兩個點集X和Y分別是原始的和經過變換后的樣本。根據正常情況下X和Y匹配點的關系，兩點集之間的誤差符合具有均值為零且均勻標準差的高斯分布特征[14-15]，這正是通過訓練DBN所需學習的特征。設X-Y為DBN的輸入，將輸入樣本劃分為子塊，然后依次輸入到網絡。本文采用的DBN由三級RBM組成，每一級的隱層單元數目為10。每一級的訓練都是獨立完成，訓練次數設定為5次，具體訓練過程為：

(2)

(3)

cj=cj+P(hj|v(0))-P(hj|v(1))

(4)

2)由子塊訓練得到第一級的參數后，再隨機選取新的子塊輸入到這一級，按照同樣的方法訓練會進一步調整權重和偏差參數，直到所有的樣本數據都被訓練過為止。

對于異常情況下的兩個采樣點集，一些異常值、噪聲和缺失點可能會影響正常點的匹配關系?？紤]到正常匹配點誤差的高斯分布，異常點間的誤差與該高斯分布不一致，因此，可以通過訓練好的DBN從點集中檢測噪聲和缺失數據。

1.3 利用訓練好的DBN識別異常點

考慮到數據不完整的情況，兩點集的大小可能不一致。因此將每個點集分組為多個分塊，然后將一個點集的分塊與另一個點集的分塊之間的誤差依次輸入到網絡中。

利用正常點集訓練DBN,除了學習權重和偏差參數外，還學習了分塊的平均重構誤差σ。當檢測含有異常點集的數據時，由于含有異常點的分塊間的誤差不符合高斯分布，經過訓練好的DBN之后將不能重建可見單元，因而分塊的重構誤差將遠遠大于σ。對于具有噪聲的兩個采樣點集，如果來自一對分塊的重構誤差接近于σ，則將這對分塊中的點視為點集的正常點。否則，若一對分塊的誤差大于k×σ，則其中的點被認為是點集中的噪聲，而系數k的大小可以通過實驗確定出最優值。

特別是對于有缺失數據的兩個點集，當定義為Xb和Yb的一對分塊間的誤差大于k×σ時，其中一個分塊肯定是沒有匹配關系的。為了確定不匹配的分塊，將Xb的相鄰分塊和Yb之間的誤差重新輸入到網絡中。如果其中一對分塊的輸出接近于σ，說明在點集Y的某個區域中存在缺失點，并且Xb被標識為不匹配的分塊；否則，將Yb的相鄰分塊和Xb之間的誤差重新輸入網絡，以找到輸出接近于σ的匹配分塊，說明在點集X的某個區域中存在缺失數據，并將Yb標識為不匹配的分塊。

2 模擬實驗及分析

采用的實驗數據包括魚的2D點集、人臉的3D點集和兔子的3D點集，如圖2所示。待配準的兩個點集中，一個是原始采樣數據，另一個則是由原始數據經過空間變換得到的。實驗中模擬了缺失數據由5%上升到10%，以及噪聲由30%上升到50%的情況。通過應用本文算法建立了點集間的匹配關系，并對實驗結果作了定量評估。

圖2 實驗中的2D和3D點集Fig. 2 2D and 3D point sets in the experiment

實驗主要分為兩個階段。首先，將原始點集和變換后的點集輸入到DBN之前，這兩個正常點集都被分塊處理，并且分塊的大小為10。通過DBN來訓練樣本，學習與點集有關的特征參數。接下來，將含有噪聲或者缺失數據的點集輸入訓練好的DBN，對異常情況下的點集進行測試以檢測異常值或未匹配點。

點集間要建立正確的匹配關系，首先就要能盡量減少異常點的影響，所以異常點誤判為正常點的情況應降低。為此，本文采用精確率來評估所提出的方法的性能。根據異常點和正常匹配點的預測結果，假定用TP(True Positive)表示真正，TN(True Negative)表示真負，FP(False Positive)表示假正，FN(False Negative)表示假負，則評估標準精確率可以定義為：

precision=TP/(TP+FP)

(5)

從式(5)可以看出，精確率越高，說明配準受異常點影響的程度越小。

另外，為了進一步分析模型的性能，實驗中根據系數k的大小在不同取值下繪制了受試者工作特征(Receiver Operating Characteristic, ROC)曲線，以反映模型區分正常點、異常點的性能，并且從中確定出最優的系數值。ROC曲線的橫坐標是假正率(False Positive Rate, FPR)，縱坐標是真正率(True Positive Rate, TPR)，其中TPR、FPR分別定義為:

TPR=TP/(TP+FN)

(6)

FPR=FP/(FP+TN)

(7)

2.1 具有缺失數據的點集

為了模擬實際應用中數據缺失的情況，其中一個點集中的5%和10%的點被分別移除。缺失數據的兩點集間的匹配結果如圖3所示。

圖3(a)中,魚的正常點集隨機選取的兩個區域中有10%的點被移除，通過算法檢測出兩個點集中有匹配關系的點，并用箭頭連接表示，無箭頭連接的則為未匹配的點，如圖3(b)所示。圖3(c)中,人臉的一個正常點集中5%的點被移除，經過檢測兩個點集之間的匹配關系如圖3(d)所示，其中有匹配關系的點以線連接。

2.2 具有噪聲的點集

對于兩個正常點集，在每個點集中分別添加30%和50%的隨機噪聲。含有噪聲的兩點集間的匹配結果如圖4所示。

圖4(a)中，魚的兩個點集中加入50%的噪聲，它們之間有匹配關系的點在圖4(b)中用箭頭連接表示，無箭頭連接的為未匹配的點。圖4(c)中，人臉的每個點集中加入了30%的隨機噪聲，兩個點集之間的匹配關系如圖4(d)所示，其中有匹配關系的點以線連接。

圖3 缺失數據的兩點集間的匹配結果Fig. 3 Matching results of two point sets with missing data

圖4 含有噪聲的兩點集間的匹配結果Fig. 4 Matching results of two point sets with noise

2.3 測量結果

對于魚的2D點集以及人臉和兔子的3D點集，根據所有實驗的預測結果估算了點集匹配的精確率，結果如表1所示。表1中，分別給出了點集中的噪聲比和點集中缺失數據的比例。

表1 實驗中所用點集的精確率 %Tab. 1 Precision of point sets used in the experiment %

從表1結果可以看出，對于有噪聲的采樣點集，兩個點集之間的匹配關系受隨機噪聲的影響很小，即使對于噪聲為50%的點集也是如此。另外，對于數據缺失的采樣點集，精確率稍有下降，反映出數據缺失對點集的匹配關系有一定影響。

實驗中還對魚的2D點集、人臉和兔子的3D點集，分別在含有50%噪聲和缺失10%數據的兩種情況下，根據系數k的6個取值(0.5,2,4,6,8,10)確定出相應的假正率(FPR)和真正率(TPR)，并繪制了ROC曲線，結果如圖5～6所示。

從圖5～6可以看出，在兩種情況下，FPR較低而TPR較高，這說明點集中的正常點較多地被歸為匹配點，同時異常點較少地被誤歸入正常匹配的點集中。為了獲得最優性能，本文選取曲線靠近左上角的點對應的系數k作為算法的最優系數，k=6，該系數對應的FPR相對較低，TPR相對較高。由此，利用這個訓練好的DBN就能夠識別點集中的異常點，排除了異常值對正常匹配關系的影響，同時保證了正常點的匹配關系，這有助于接下來獲得較高的點集配準精度。

圖5 含有50%噪聲的三種點集的ROC曲線Fig. 5 ROC curve of three point sets with 50% noise

圖6 缺少10%數據的三種點集的ROC曲線Fig. 6 ROC curve of three point sets with 10% missing data

對比圖5～6可以看出，圖5中的FPR明顯低于圖6中的FPR，說明在噪聲情況下異常點很少被誤判為正常匹配的點；同時圖5中的TPR略高于圖6中的TPR，說明在噪聲情況下正常點能較多地保留在匹配點集中。圖5～6對比結果說明，本文算法在噪聲情況下比在缺失數據的情況下能更好地區分正常點和異常點。這是由于含噪分塊間的誤差分布不同于正常分塊，而在缺失數據的情況下，由于點集鄰域的相關性，未匹配的分塊與缺失數據的鄰域間的誤差分布接近于正常分塊，從而會將未匹配的點誤歸入正常點，導致了FPR的數值較高。

2.4 算法的比較

流形正則化一致向量場(MRCVF)算法能夠在異常點集中排除外部數據，為此，將本文算法和MRCVF算法在同樣的數據集上進行了比較。實驗中利用人臉的3D點集，在加入噪聲和數據缺失的情況下，比較了兩種算法的精確率，結果如表2所示。

表2 不同算法精確率的比較結果 %Tab. 2 Comparison results of precision of different algorithms %

從表2精確率的結果可以看出：在含噪聲情況下，MRCVF算法的精確率明顯低于本文算法，說明MRCVF算法會將較多的噪聲點引入到正常匹配關系的點對中，這不利于下一步點集間的配準；而在缺失數據情況下，兩種算法的精確率都較高，說明缺失點對正常點的匹配關系影響較小。

3 結語

由于異常值、噪聲和缺失數據會影響點集間匹配關系的確定，本文提出了基于DBN的學習方法來識別異常點和不匹配點。兩個正常采樣點集之間的誤差分布可以通過訓練DBN來學習，利用異常值或缺失數據的不一致的誤差分布，可以由訓練好的DBN識別出異常點。對2D和3D點集的實驗結果表明，本文算法可以在噪聲和缺失數據情況下識別出異常點，確保點集之間建立正確的匹配關系。不過由于點集鄰域的相關性，缺失點對正常點的匹配關系有較小影響。未來的工作將著重于機器學習方法在點集配準中的應用，并將探索醫學成像和圖像引導的神經外科系統的配準方法。