基于多種聚類的無監(jiān)督距離融合學(xué)習(xí)算法研究

侯守明 林曉潔 胡明凱

摘 ?要：本文針對(duì)傳統(tǒng)的形狀匹配算法的處理計(jì)算量過大、消耗時(shí)間過長，從而導(dǎo)致無法應(yīng)用于大量的圖像集以及在線的形狀匹配場(chǎng)景的問題，在學(xué)者提出的距離融合算法的基礎(chǔ)上進(jìn)行了改進(jìn)，在處理階段引入無監(jiān)督學(xué)習(xí)的方法進(jìn)行多種聚類。通過引入預(yù)處理算法對(duì)圖像集進(jìn)行特征提取以及劃分，在算法的計(jì)算量上做出優(yōu)化，大幅降低了算法的計(jì)算時(shí)耗，并且保證其正確率幾乎沒有降低。

關(guān)鍵詞：無監(jiān)督;形狀匹配;多重聚類;距離融合

中圖分類號(hào)：TP391;TP751.1 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 ?引 ?言

隨著互聯(lián)網(wǎng)的迅猛發(fā)展以及圖像資源的日益豐富，形狀匹配已經(jīng)成為計(jì)算機(jī)視覺領(lǐng)域的一個(gè)熱門研究方向。如何能夠準(zhǔn)確、快速地對(duì)已有形狀進(jìn)行同類的辨識(shí)匹配，找出同類圖像以及確定圖片中形狀所屬類別，學(xué)者們已經(jīng)在這一領(lǐng)域提出很多很有效用的算法。

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

本文基于白翔等[6，7]提出的距離融合協(xié)同傳導(dǎo)算法，在處理階段引入無監(jiān)督學(xué)習(xí)的方法進(jìn)行聚類。在算法的計(jì)算量上做出優(yōu)化，大幅降低了算法的計(jì)算時(shí)間，并且正確率幾乎沒有降低。

1 ?距離融合算法介紹

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

圖傳導(dǎo)算法在很大程度上提高了形狀匹配的準(zhǔn)確度，但是也存在一定的缺陷，因?yàn)閳D傳導(dǎo)算法是在選定的某一種形狀匹配算法上進(jìn)行流模型的計(jì)算，進(jìn)而找出最短路徑，所以算法有著事先的潛力限制，還是只關(guān)注于某一種特征。基于此，Bai X等又在圖傳導(dǎo)算法的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了協(xié)同傳導(dǎo)算法。

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

2 ?基于多種聚類的算法改進(jìn)

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

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

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

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

2.1 ?K均值聚類算法

2.3 ?AGNES聚類算法

AGNES是一種“自底向上”的層次聚類算法，算法首先將樣本集中每一個(gè)樣本當(dāng)做一個(gè)初始聚類簇，然后開始進(jìn)行算法迭代，算法的每一次迭代找出兩個(gè)最相似的聚類簇進(jìn)行合并，直到達(dá)到預(yù)設(shè)的聚類簇個(gè)數(shù)。

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

聚類結(jié)束后，算法輸出樣本集的簇劃分C={C1，C2， …，Ck}。對(duì)于查詢樣本x0，該算法無法確定x0所屬的簇。因此，我們?cè)谠撍惴ǖ幕A(chǔ)上做一些改進(jìn)，以便能夠確定查詢樣本x0所屬的簇。參考K均值算法確定查詢樣本所屬聚類簇的方式，將每個(gè)簇計(jì)算一個(gè)簇均值，查詢樣本x0所屬的類別就是與對(duì)應(yīng)相似度最高的簇均值對(duì)應(yīng)得到簇，即λ=argmaxi∈{1，2，…，k}sim（x1，μi）。

2.4 ?預(yù)處理算法

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

2.5 ?協(xié)同傳導(dǎo)步驟

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

輸入：簇劃分С

簇劃分方法?（x）

相似度函數(shù)sim1，sim2

查詢樣本x0

過程：

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

2 ?簇劃分和簇劃分方法個(gè)數(shù)n=5

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

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

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

6 ?end for

7 ?使用sim1在樣本集Dh上計(jì)算每個(gè)樣本與x0的相似度，基于相似度對(duì)樣本集排序得到S1，并基于S1計(jì)算概率轉(zhuǎn)移矩陣P1

8 ?使用sim2在樣本集Dh上計(jì)算每個(gè)樣本與x0的相似度，基于相似度對(duì)樣本集排序得到S2，并基于S2計(jì)算概率轉(zhuǎn)移矩陣P2

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

10 ?repeat

11 ?使用P1基于圖傳導(dǎo)算法學(xué)習(xí)出相似度

12 ?使用P2基于圖傳導(dǎo)算法學(xué)習(xí)出相似度（j=1，…，m是迭代次數(shù)的索引）

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

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

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

16 ?until達(dá)到最大迭代次數(shù)

17 ?取N1和N2中相似度最高的前p個(gè)樣本作為結(jié)果R

輸出：匹配結(jié)果R

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

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

實(shí)驗(yàn)的圖像數(shù)據(jù)集采用MPEG-7形狀數(shù)據(jù)集，圖像形狀如圖3所示，MPEG-7形狀數(shù)據(jù)集由70個(gè)類別，共1400個(gè)剪影圖像組成，每個(gè)類都有20種不同的形狀。

對(duì)算法運(yùn)行時(shí)間和算法正確率兩方面進(jìn)行實(shí)驗(yàn)驗(yàn)證，我們對(duì)比本文算法與Bai X提出的協(xié)同傳導(dǎo)算法，本文算法在聚類方法上可以選擇一種、兩種或三種，并對(duì)這些情況都做了實(shí)驗(yàn)驗(yàn)證。

算法運(yùn)行時(shí)間的對(duì)比。我們將Bai X的協(xié)同傳導(dǎo)算法的運(yùn)行時(shí)間定為1，比較我們的算法運(yùn)行時(shí)間和Bai X算法的運(yùn)行時(shí)間，對(duì)比了采用一種聚類算法、采用兩種聚類算法和三種聚類算法的運(yùn)行時(shí)間，運(yùn)行時(shí)間對(duì)比分析如表1所示。從表1中可以看出，算法能夠大幅降低計(jì)算時(shí)間。

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

綜合以上實(shí)驗(yàn)結(jié)果可以得出結(jié)論，該改進(jìn)算法能夠大幅降低計(jì)算時(shí)間，使算法能夠運(yùn)行到在線匹配場(chǎng)景下，同時(shí)匹配正確度上與協(xié)同傳導(dǎo)算法幾乎相同。

參考文獻(xiàn)：

[1] 劉麗，匡綱要.圖像紋理特征提取方法綜述 [J].中國圖象圖形學(xué)報(bào)，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] 張桂梅，蔡報(bào)豐.基于內(nèi)距離形狀上下文特征的形狀匹配研究 [J].南昌航空大學(xué)學(xué)報(bào)（自然科學(xué)版），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-），男，漢族，河南博愛人，教授，碩士生導(dǎo)師，博士，研究方向：圖形圖像處理、虛擬現(xiàn)實(shí)與增強(qiáng)現(xiàn)實(shí);通訊作者：林曉潔（1990-），女，漢族，河南濮陽人，碩士研究生，研究方向：系統(tǒng)軟件、圖像處理;胡明凱（1991-），男，漢族，廣東深圳人，碩士，研究方向：數(shù)字化工程與仿真。