改進PCA-SIFT的電子標簽圖像匹配算法

于林飛,李云紅,穆 興,李傳真

(西安工程大學 電子信息學院,陜西 西安 710048)

0 引 言

圖像匹配是在特定的算法下將2幅或多幅圖像識別特征點的過程。其發(fā)展迅速,在許多領(lǐng)域有著廣泛的實際應用[1]。近些年,出現(xiàn)了許多圖像匹配算法[2-7],而SIFT算法是非常經(jīng)典、成熟的算法,可在圖像中檢測出關(guān)鍵點,同時也延伸出多種SIFT改進算法。張楊等[8]提出了基于改進PCA算法的人臉識別,通過ORL人臉的實驗庫得到運算耗時少于經(jīng)典PCA算法;程德志等[9]提出了基于改進SIFT算法的圖像匹配方法,使得圖像匹配精度和匹配效率有所提高;何成偉等[10]提出了基于直方圖均衡化的PCA-SIFT[11-12]圖像特征提取與匹配改進算法,增強圖像的明暗對比度,提高圖像匹配效率;田健飛[13]提出了一種曲線擬合的柱面圖像匹配算法,增加了剔除誤匹配后靠近柱面圖像邊緣部分的匹配點數(shù)量,提高了柱面圖像匹配的精度。雖然采用上述方法可以達到一定的效果,但無論使用什么圖像匹配方法,在匹配過程中多少都會收到其他因素的干擾,圖像匹配的結(jié)果就會產(chǎn)生一些錯匹配,因此,在圖像匹配技術(shù)中,為獲得高精度的匹配效果,對匹配后的錯匹配點進行有效地剔除就顯得尤為重要。

目前對于誤匹配點改進算法有很多,其中較為常用的算法是RANSAC[14],該算法在剔除錯誤匹配點時,使用的參數(shù)是隨機的,主要由隨機樣本點組成,這樣選出的模型參數(shù)就不能對更多的特征點信息做出有效的響應,雖然也能檢測出誤匹配點,但很難區(qū)分正確匹配點和錯誤匹配點[15]。

針對以上存在問題,本文提出了基于改進PCA-SIFT的電子標簽圖像匹配算法,通過SIFT算法獲取圖像關(guān)鍵特征點,結(jié)合PCA和K-means聚類結(jié)果,對剔除后的待匹配的圖像集進行圖像匹配。實驗結(jié)果表明,基于PCA-SIFT算法比經(jīng)典SIFT算法具有更好的匹配效果。

1 SIFT算法

SIFT算法是由Lowe提出并完善的圖像特征點檢測和描述算法。該算法在圖像匹配中具有很好的優(yōu)勢,比如在圖像平移、旋轉(zhuǎn)和尺度變換等方面,且對噪聲也能保持一定的穩(wěn)定性,其主要流程是:尺度空間的構(gòu)建、特征點的檢測和描述、特征點的匹配。

1.1 獲取圖像數(shù)據(jù)

使用工業(yè)CCD傳感器獲取電子標簽數(shù)據(jù)。如圖1所示。

圖 1 電子標簽圖像庫

其中，圖1(b)～(d)與模板不一致,圖1(e)和(f)標簽缺失(即空白)，圖1(g)和(h)與模板一致。

1.2 SIFT特征點生成

高斯尺度核可以用原始圖像與一個可變尺度二維高斯函數(shù)的卷積運算定義圖像的尺度空間:

L(x,y,σ)=G(x,y,kσ)*I(x,y)

(1)

式中:G(x,y,kσ)為尺度可變高斯函數(shù);I(x,y)為原始圖像;k為尺度變化量。為保證檢測到的特征點的穩(wěn)定性,一般采用不同高斯差分核與圖像卷積生成高斯差分空間:

(2)

對檢測到的特征點,計算出鄰域梯度直方圖并確定其主方向。需要注意的是,一些特征點不僅具有主方向,而且具有輔方向,它對于后續(xù)匹配的穩(wěn)定性非常重要。

1.3 PCA基本原理

PCA[16-17]是通過線性變換將原有的多個變量轉(zhuǎn)化為少數(shù)幾個新的綜合變量的統(tǒng)計分析方法。PCA的目標是在降維之后盡可能多的保持原有的內(nèi)在信息,并通過衡量在投影方向上的數(shù)據(jù)方差的大小來判斷該方向的重要性。PCA數(shù)學原理如下:設(shè)n維向量w,表示低維映射空間的1個映射向量,經(jīng)過最大化數(shù)據(jù)映射后可得方差公式為

(3)

定義W是由所有特征映射向量的列向量組成的矩陣,該矩陣可以較好地保留數(shù)據(jù)中的信息,該矩陣通過線性變換可以得到一個優(yōu)化的目標函數(shù),為

(4)

式中:tr是矩陣的跡;A是協(xié)方差矩陣。A表達式如下:

(5)

PCA 是輸出, 可以用Y=W′X來表示, 最優(yōu)的W是數(shù)據(jù)協(xié)方差矩陣前k個最大的特征值對應的特征向量作為列向量而組成,據(jù)此將X原始維度降低到了k維。

1.4 改進PCA-SIFT算法

在圖像匹配中,為了便于和傳統(tǒng)的SIFT算法作比對,改進算法中引入PCA先進行降維對圖像二維表征,再根據(jù)聚類后的結(jié)果進行初步分類,最后采用RANSAC仿射變換實現(xiàn)圖像的快速匹配。改進算法主要流程圖如圖2所示。

圖 2 實驗流程圖

1)為了增強該算法過程的魯棒性,將原來8張圖像旋轉(zhuǎn)和圖像平移操作,得到24張圖,增大圖像集,并對得到圖像集后的所有的圖像進行特征提取,得到圖像的特征點的高維特征向量。其中1、4、7、10、13、16、19、22圖為原始的8張圖,分別對應圖1(a)～(h)。因為通過降維表征可以更加容易觀察出高維特征向量的分布特性,同時大的數(shù)據(jù)集可以使得PCA的降維矩陣更具有魯棒性,所以對所有提取的高維特征向量,整體進行PCA降維,得到最佳的降維矩陣和降維后的特征向量。此外,在得到整體分布后,結(jié)合最優(yōu)降維矩陣,進一步觀察標記的圖像在特征空間的分布特性,同時為了實現(xiàn)圖像區(qū)分的量化方法,本文提出了基于K均值聚類算法的量化處理方法。

2) K-means聚類算法[18-21]是一種聚類分析算法,通過數(shù)學迭代運算,其步驟是隨機選取k個對象作為初始的聚類中心,然后計算每個對象與各個種子聚類中心之間的距離,把每個對象分配給距離它最近的聚類中心。輪廓系數(shù),是聚類效果好壞的一種評價方式。最早由Peter J.Rousseeuw在1986提出。它結(jié)合內(nèi)聚度和分離度2種因素。可以用來在相同原始數(shù)據(jù)的基礎(chǔ)上用來評價不同算法、或者算法不同運行方式對聚類結(jié)果所產(chǎn)生的影響。輪廓系數(shù)的值是介于 [-1,1],越趨近于1代表內(nèi)聚度和分離度都相對較優(yōu)。

為了尋求較優(yōu)的聚類數(shù),本文對于從2到20的聚類個數(shù)進行聚類分析,根據(jù)每次聚類的結(jié)果,計算出所有樣品點的輪廓系數(shù)S,并取均值，得到圖3的散點圖?？紤]到聚類數(shù)不應該過大或者過小,所以對散點圖進行高斯擬合?？梢钥闯?降維后的特征點呈現(xiàn)出聚類的特性,由圖3發(fā)現(xiàn),聚類數(shù)為2、3、4時,具有較大的平均輪廓系數(shù)。分析高斯擬合得到的結(jié)果,高斯函數(shù)的對稱軸在x=2.7,接近3。

圖 3 聚類散點圖與高斯函數(shù)擬合曲線

為了更直觀地觀察點分布的聚類中心,計算得到的24張圖的各自的聚類中心并表征在同一個坐標下,如圖4所示。

圖 4 24張圖的聚類中心表征

圖4中的圖例的表征為8×3的排列結(jié)構(gòu),每一行代表著一張原始及其變化后的圖。通過圖4可以發(fā)現(xiàn),圖例的第5行和第6行所代表的點(13～16圖),顯著偏移其他點,尤其是第一聚類區(qū)間和第二聚類區(qū)間。相對于其他聚類中心,偏X軸負向、Y軸正向,印證了上述對于1圖和13圖的聚類分析結(jié)果。

3) 為了區(qū)分標簽是否丟失,計算類間距(歐氏距離)的加權(quán)和,通過距離閾值進行了類的劃分。即將有標簽的圖對應的聚類中心作為基準點的重心,計算得到3個參考點,分別計算24個聚類在各個聚類區(qū)間下離參考點的距離,并對3個區(qū)間的距離進行求和得到的歐氏距離進行量化分析,如圖5所示。

圖 5 24張圖在特征空間的歐氏距離

通過圖5可得,(13～18圖)的歐氏距離顯著高于其他圖。為了獲得合適的分類閾值和高可信度,本文采取的算法是取無標簽的最小值和有標簽的最大值的均值。計算得到,其閾值取0.165 4。

在獲得分類閾值后,可以對具有或不具有標簽的圖片進行分類,之后進行圖片配準的計算,得到圖片的相似度(匹配點的百分比的曲線)。再將標簽缺失的圖進行計算,如圖6所示。

圖 6 24張圖的相似度表征

圖6中1～3和19～24為與標準圖片吻合的正確圖片,13～18為缺失的圖片,4～12為其他標簽。從標簽中剔除缺失的圖像,并計算其余圖像的相似性,如圖7所示。

圖 7 分類后的24張圖的相似度表征

通過相似度可以進一步進行分類,可以實現(xiàn)相似圖片和不相似圖片的分類,為了獲得合適的分類閾值且具有較高的可信度,本文采用的算法為:取模板圖及其變換圖的相似度的最小值和非模板圖的相似度的最大值的均值。計算得到,其相似度閾值取0.4。此過程在有無標簽圖片的基礎(chǔ)上,進一步實現(xiàn)了相似圖片和不相似圖片的分類。

4) 使用RANSAC,獲取仿射變換矩陣,利用幾何變換查找物體進行配準。

2 結(jié)果與分析

實驗硬件環(huán)境為Intel CORE i7,內(nèi)存為8 G,操作系統(tǒng)為64位的PC機。仿真實驗環(huán)境是Windows10下的Matlab2019(a)軟件,實驗所采用的電子標簽圖像為工業(yè)CCD相機采集。

除了實現(xiàn)圖片的2次分類,剔除了絕大多數(shù)的無關(guān)圖片外,本文提出的算法仍然可以在最終匹配上提高速度。為了表征該算法與現(xiàn)有主流算法的計算速度的差異,本文在最終圖像匹配的計算速度上,將改進的PCA-SIFT算法與傳統(tǒng)的SIFT匹配進行對比實驗分析,改進的PCA-SIFT算法首先通過SIFT獲取圖像關(guān)鍵特征點后進行PCA降維,實現(xiàn)對電子標簽的量化辨別,進而剔除無標簽和和不相似圖片,在這里,設(shè)定匹配閾值為0.165 4,實現(xiàn)標簽分類后,又進行相似度分類,設(shè)定匹配閾值為0.4,獲取出相似圖片,再進行RANSAC仿射變換,進行圖像的配準。本文不失一般性,認為當匹配點與真實點的歐幾里得距離小于5個像素時,認為匹配正確,即當匹配點與真實點的歐幾里得距離大于5個像素時,認為匹配錯誤。傳統(tǒng)的SIFT算法是沒有進行PCA分類,直接進行圖像的配準。

改進的PCA-SIFT算法在進行圖像匹配時,將旋轉(zhuǎn)平移的3張圖,與原始圖進行匹配,計算匹配率。此時,匹配率是相同物體不同照片的特征點匹配的計算,特征點的匹配關(guān)系是事先知道的,是一一對應的關(guān)系。通過計算圖像的特征點及其特征向量,并計算出特征點與特征點的對應關(guān)系,并與實際的對應關(guān)系相比較,計算出與實際相匹配的百分比。將這2種算法匹配率進行比較,如圖8所示。

圖 8 2種算法匹配率對比

圖9為2種算法耗時結(jié)果對比圖。表1和表2分別為改進PCA-SIFT算法與傳統(tǒng)SIFT算法的匹配率和相對耗時時間。

通過圖8和表1發(fā)現(xiàn),當加入PCA分析時,匹配率提高平均約6%,證明該算法能夠提高圖像的匹配率。通過圖9和表2得到,該過程的實現(xiàn)比傳統(tǒng)SIFT算法在運算速度上提升了約0.1 s,在處理速度上比原先算法平均大約提升了2倍,如樣品2實驗,經(jīng)典SIFT算法耗時約0.19 s,而改進算法只需不到0.04 s,其他同組實驗與該結(jié)論一致。證明改進過的算法在處理速度上有明顯的改善。

圖 9 2種算法耗時結(jié)果對比

表 1 經(jīng)典SIFT算法與改進算法的匹配率

表 2 經(jīng)典SITFT算法與改進算法相對耗時

3 結(jié) 語

針對SIFT算法在圖像匹配中匹配率不高的問題,提出了改進PCA-SIFT的電子標簽圖像匹配算法。由于電子標簽的數(shù)量有限,將原有8張圖進行旋轉(zhuǎn)和平移操作擴充了圖庫數(shù)據(jù),將同一幅圖的旋轉(zhuǎn)變換圖與原始圖進行匹配。本實驗在SIFT獲取圖像特征關(guān)鍵點后,進行PCA降維和聚類,實現(xiàn)了對無效圖像的分類和剔除,再通過相似性匹配,獲取相似圖像,比經(jīng)典SIFT算法在圖像匹配時,快速剔除了標簽缺失或者相似度不高的圖像,有效提高了圖像的匹配速度和匹配率。實驗結(jié)果發(fā)現(xiàn),改進PCA-SIFT算法比經(jīng)典SIFT算法在圖像匹配精度上平均提高了6%,耗時時間上平均節(jié)省了約0.1 s,比經(jīng)典SIFT算法在處理速度上提高了2倍以上。經(jīng)過大量實驗數(shù)據(jù)結(jié)果驗證了改進PCA-SIFT算法對電子標簽快速匹配的有效性。但是,該研究只進行了改進算法和經(jīng)典SIFT算法的對比,在其他算法下的效果對比存在不足,以及在背景復雜情況下仍存在檢測效果不佳等問題,這些問題將是今后研究的重點。