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

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

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

0 引 言

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

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

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

1 SIFT算法

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

1.1 獲取圖像數據

使用工業CCD傳感器獲取電子標簽數據。如圖1所示。

圖 1 電子標簽圖像庫

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

1.2 SIFT特征點生成

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

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

(1)

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

(2)

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

1.3 PCA基本原理

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

(3)

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

(4)

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

(5)

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

1.4 改進PCA-SIFT算法

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

圖 2 實驗流程圖

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

2) K-means聚類算法[18-21]是一種聚類分析算法,通過數學迭代運算,其步驟是隨機選取k個對象作為初始的聚類中心,然后計算每個對象與各個種子聚類中心之間的距離,把每個對象分配給距離它最近的聚類中心。輪廓系數,是聚類效果好壞的一種評價方式。最早由Peter J.Rousseeuw在1986提出。它結合內聚度和分離度2種因素?？梢杂脕碓谙嗤紨祿幕A上用來評價不同算法、或者算法不同運行方式對聚類結果所產生的影響。輪廓系數的值是介于 [-1,1],越趨近于1代表內聚度和分離度都相對較優。

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

圖 3 聚類散點圖與高斯函數擬合曲線

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

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

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

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

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

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

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

圖 6 24張圖的相似度表征

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

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

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

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

2 結果與分析

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

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

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

圖 8 2種算法匹配率對比

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

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

圖 9 2種算法耗時結果對比

表 1 經典SIFT算法與改進算法的匹配率

表 2 經典SITFT算法與改進算法相對耗時

3 結 語

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