基于多種聚類的無監督距離融合學習算法研究

侯守明 林曉潔 胡明凱

摘 ?要：本文針對傳統的形狀匹配算法的處理計算量過大、消耗時間過長，從而導致無法應用于大量的圖像集以及在線的形狀匹配場景的問題，在學者提出的距離融合算法的基礎上進行了改進，在處理階段引入無監督學習的方法進行多種聚類。通過引入預處理算法對圖像集進行特征提取以及劃分，在算法的計算量上做出優化，大幅降低了算法的計算時耗，并且保證其正確率幾乎沒有降低。

關鍵詞：無監督;形狀匹配;多重聚類;距離融合

中圖分類號：TP391;TP751.1 ? ? ?文獻標識碼：A 文章編號：2096-4706（2019）05-0070-04

Abstract：The problem of traditional shape matching algorithm is too large and the consumption time is too long，which can not be applied to a large number of image sets and online shape matching scenes. It is improved on the basis of the distance fusion algorithm proposed by scholars. Introduce unsupervised learning methods in the processing stage to perform multiple clustering. The feature extraction and division of the image set are introduced by introducing the preprocessing algorithm，and the calculation of the algorithm is optimized，which greatly reduces the computational time consumption of the algorithm and ensures that the correct rate is almost not reduced.

Keywords：unsupervised;shape matching;multiple clustering;distance fusion

0 ?引 ?言

隨著互聯網的迅猛發展以及圖像資源的日益豐富，形狀匹配已經成為計算機視覺領域的一個熱門研究方向。如何能夠準確、快速地對已有形狀進行同類的辨識匹配，找出同類圖像以及確定圖片中形狀所屬類別，學者們已經在這一領域提出很多很有效用的算法。

利用形狀本身的特征、顏色差異以及圖像的紋理特征進行形狀區分是形狀匹配算法的主要方法，通過不同的特征提取方法得到各形狀之間的相似度或者相似距離。例如匡綱要等[1]提出的基于圖像紋理特征的提取方法，重點關注紋理特征的分類與分割，并對一般的紋理特征提取方法進行了總結。Zhao等[2]提出的基于顏色空間分布特征的圖像檢索方法利用顏色之間的對比度的多尺度鄰域形成的加權顏色直方圖來檢索圖像。進一步地，Micha?等[3]研究了基于顏色和關鍵點的特征提取算法在分布式上的應用，將計算任務分發到多個節點，從而提高了算法整體的算力和圖像集的容量。Zhu X等[4]利用支持向量機對基于骨架的形狀匹配算法進行了研究，使得算法在有噪音的情況下也能展示出良好的性能，同時與圖形的旋轉縮放平移無關。張桂梅等[5]研究了基于內距離形狀上下文特征的形狀匹配。

本文基于白翔等[6，7]提出的距離融合協同傳導算法，在處理階段引入無監督學習的方法進行聚類。在算法的計算量上做出優化，大幅降低了算法的計算時間，并且正確率幾乎沒有降低。

1 ?距離融合算法介紹

Bai X等提出的距離融合算法基于他們提出的圖傳導算法。在圖傳導算法中，他們提出使用圖形的轉換學習算法來解決傳統形狀特征匹配算法不能夠有效正確地識別有效差異與無效差異的問題，該算法的特點是不專注于計算孤立的每一對形狀之間的相似性距離，而是利用現有較多的形狀形成的流模型，通過算法中提出的概率轉移矩陣。如存在這樣一個匹配的場景，利用內距離形狀匹配算法計算相似性距離，在計算一個站立的人（記為A）與蹲著的人（記為B）以及站立的猴子（記為C）之間的相似性距離時，我們能夠得出這樣一個結果，即SAB

圖傳導算法在很大程度上提高了形狀匹配的準確度，但是也存在一定的缺陷，因為圖傳導算法是在選定的某一種形狀匹配算法上進行流模型的計算，進而找出最短路徑，所以算法有著事先的潛力限制，還是只關注于某一種特征。基于此，Bai X等又在圖傳導算法的基礎上進行了改進，提出了協同傳導算法。

該算法克服了上面提到的單一圖傳導算法只能關注某一類形狀特征的局限，通過利用兩種甚至多種特征提取算法計算出的特征矩陣進行協同傳導，在迭代過程中利用多種特征提取得到的距離矩陣通過概率轉移矩陣進行距離融合傳遞，關注形狀多個方面的特征，從而提高形狀匹配的正確率。

2 ?基于多種聚類的算法改進

Bai X等人提出算法，應用LP算法來學習一個新的相似度函數simT，這種方法大大提高了對查詢形狀x1的查詢準確度，但是該算法需要計算任意兩個樣本之間的相似度，并且不斷迭代。當已知樣本集很大時，計算查詢樣本與所有形狀的相似度由于耗時問題變得不切實際，而且無法用于在線的圖像匹配應用中。

為了算法在大的樣本集上同樣有著較快的運行速度，本文采用啟發式方式，從兩個思路入手，第一，對樣本集做預處理，以便對查詢對象在樣本集中做匹配時不需要對數據庫中所有圖像計算相似度;第二，采用自適應的方式篩選最相似樣本，減少需要匹配的樣本的數量。

因此算法分為兩個步驟：第一步，預處理步驟，對樣本集所有樣本進行聚類，輸出聚類簇和劃分查詢樣本x0的方法;第二步，協同傳導步驟，對于查詢樣本x0，只需要根據聚類模型，將x0分類到聚類形成的簇類別中，x0所屬簇類別的所有樣本作為查詢樣本候選匹配樣本，然后在候選匹配樣本上采用協同傳導算法計算最相似樣本。

在這種方式下，當查詢樣本x0落入某兩個簇類別的邊界，x0的最相似樣本可能存在于這兩個類別中，而且單一聚類標準的算法魯棒性并不高，因此，本文選擇多種聚類算法，x0在所有聚類算法中落入類別的樣本都作為候選匹配樣本，然后在這些樣本上采用協同傳導算法計算最相似樣本。

2.1 ?K均值聚類算法

2.3 ?AGNES聚類算法

AGNES是一種“自底向上”的層次聚類算法，算法首先將樣本集中每一個樣本當做一個初始聚類簇，然后開始進行算法迭代，算法的每一次迭代找出兩個最相似的聚類簇進行合并，直到達到預設的聚類簇個數。

傳統AGNES算法通過度量兩個簇之間的距離來進行簇合并，簇Сi與Сj間的距離度量通常有以下三種方式：最小距離、最大距離和平均距離。

聚類結束后，算法輸出樣本集的簇劃分C={C1，C2， …，Ck}。對于查詢樣本x0，該算法無法確定x0所屬的簇。因此，我們在該算法的基礎上做一些改進，以便能夠確定查詢樣本x0所屬的簇。參考K均值算法確定查詢樣本所屬聚類簇的方式，將每個簇計算一個簇均值，查詢樣本x0所屬的類別就是與對應相似度最高的簇均值對應得到簇，即λ=argmaxi∈{1，2，…，k}sim（x1，μi）。

2.4 ?預處理算法

基于以上三個聚類算法，我們可以對樣本集進行預處理。K均值算法和AGNES使用了sim函數來計算相似度，它應該與協同傳導步驟中的sim函數保持一致，協同傳導步驟中，將使用兩個相似度函數，即sim1和sim2。高斯混合聚類算法沒有使用sim函數，而是假設了樣本服從高斯分布，因此不存在保持一致的問題，所以預處理算法輸出五個聚類簇劃分С，和五個劃分查詢樣本到對應分類簇的方法?（x），調用該函數得到給定樣本所屬的簇標記。預處理算法如圖1所示。

2.5 ?協同傳導步驟

2.4節對樣本集做出了預處理，每種聚類算法都給出了簇劃分和劃分查詢樣本x0的方式。因此，對于查詢樣本x0，我們可以基于預處理步驟給出的結果快速得到候選匹配樣本集，然后在候選匹配樣本中采用協同傳導算法計算最相似樣本。由于預處理步驟大大縮小了候選匹配樣本范圍，因此協同傳導步驟的計算量大大降低。

輸入：簇劃分С

簇劃分方法?（x）

相似度函數sim1，sim2

查詢樣本x0

過程：

1 ?初始化候選樣本集Dh=?

2 ?簇劃分和簇劃分方法個數n=5

3 ?for j=1，2，…，n do

4 ?找出查詢樣本所屬類別λ=f j（x0）

5 ?將該類中的樣本劃入候選樣本集

6 ?end for

7 ?使用sim1在樣本集Dh上計算每個樣本與x0的相似度，基于相似度對樣本集排序得到S1，并基于S1計算概率轉移矩陣P1

8 ?使用sim2在樣本集Dh上計算每個樣本與x0的相似度，基于相似度對樣本集排序得到S2，并基于S2計算概率轉移矩陣P2

9 ?令Y1=Y2{x0}，X1=X2=Dh

10 ?repeat

11 ?使用P1基于圖傳導算法學習出相似度

12 ?使用P2基于圖傳導算法學習出相似度（j=1，…，m是迭代次數的索引）

13 ?（N1表示X1前p個最相似樣本）

14 ?（N2表示X2前p個最相似樣本）

15 ?X1=X1-Y1，X2=X2-Y2

16 ?until達到最大迭代次數

17 ?取N1和N2中相似度最高的前p個樣本作為結果R

輸出：匹配結果R

對于給定的查詢樣本，該步驟需要基于預處理步驟的結果，計算出候選樣本集Dh，然后再候選樣本集上應用協同傳導算法，計算出最匹配的樣本。算法偽代碼如圖2所示，其中涉及到的圖傳導算法已經在背景介紹部分進行了說明。

3 ?實驗結果與分析

實驗的圖像數據集采用MPEG-7形狀數據集，圖像形狀如圖3所示，MPEG-7形狀數據集由70個類別，共1400個剪影圖像組成，每個類都有20種不同的形狀。

對算法運行時間和算法正確率兩方面進行實驗驗證，我們對比本文算法與Bai X提出的協同傳導算法，本文算法在聚類方法上可以選擇一種、兩種或三種，并對這些情況都做了實驗驗證。

算法運行時間的對比。我們將Bai X的協同傳導算法的運行時間定為1，比較我們的算法運行時間和Bai X算法的運行時間，對比了采用一種聚類算法、采用兩種聚類算法和三種聚類算法的運行時間，運行時間對比分析如表1所示。從表1中可以看出，算法能夠大幅降低計算時間。

算法的正確率對比。本文算法與協同傳導算法采用相同的相似度函數，對比采用不同種類聚類算法時，該算法與協同傳導算法的正確率比較，匹配準確度對比分析如表2所示。本文算法的正確率隨著聚類算法的增多而接近協同傳導算法，從一種聚類算法的95%左右的正確率上升到三種聚類算法時的97.59%，而協同傳導算法為97.63%，這意味著只有個別的最相似樣本沒有被劃入候選匹配樣本中。

綜合以上實驗結果可以得出結論，該改進算法能夠大幅降低計算時間，使算法能夠運行到在線匹配場景下，同時匹配正確度上與協同傳導算法幾乎相同。

參考文獻：

[1] 劉麗，匡綱要.圖像紋理特征提取方法綜述 [J].中國圖象圖形學報，2009，14（4）： 622-635.

[2] Zhao Q，Cao J，Hu Y.Image Retrieval Based on Color-Spatial Distributing Feature [J].Journal of Southern Yangtze University，2007，346：79-86.

[3] Micha? ??giewka，Korytkowski M，Scherer R. Distributed image retrieval with color and keypoint features [C]// IEEE International Conference on Innovations in Intelligent Systems & Applications. IEEE，2017.

[4] Zhu X. Shape Recognition Based on Skeleton and Support Vector Machines [C]// International Conference on Intelligent Computing. Springer，Berlin，Heidelberg，2007.

[5] 張桂梅，蔡報豐.基于內距離形狀上下文特征的形狀匹配研究 [J].南昌航空大學學報（自然科學版），2016，30（2）：1-7.

[6] BAI X，YANG X，LATECKI LJ，et al. Learning context-sensitive shape similarity by graph transduction [J].IEEE transactions on pattern analysis and machine intelligence，2010，32（5）：861-74.

[7] BAI X，WANG B，YAO C，et al. Co-transduction for shape retrieval [J].IEEE Transactions on Image Processing，2012，21（5）：2747-2757.

作者簡介：侯守明（1972-），男，漢族，河南博愛人，教授，碩士生導師，博士，研究方向：圖形圖像處理、虛擬現實與增強現實;通訊作者：林曉潔（1990-），女，漢族，河南濮陽人，碩士研究生，研究方向：系統軟件、圖像處理;胡明凱（1991-），男，漢族，廣東深圳人，碩士，研究方向：數字化工程與仿真。