王 鑫，賈敏智

(太原理工大學(xué)信息工程學(xué)院，山西太原030024)

改進(jìn)Harris－SIFT算法在水下圖像匹配中的應(yīng)用

王 鑫，賈敏智

(太原理工大學(xué)信息工程學(xué)院，山西太原030024)

針對尺度不變特征變換(SIFT)算法實(shí)時(shí)性差、錯(cuò)匹配多，以及Harris角點(diǎn)檢測算法精度不高、速度偏慢的問題，提出了一種運(yùn)用改進(jìn)Harris-SIFT算法對水下拍攝的雙目圖像進(jìn)行特征點(diǎn)提取與匹配的方法。利用改進(jìn)的Harris算法對兩幅圖像進(jìn)行角點(diǎn)檢測，然后為特征點(diǎn)分配方向，并生成SIFT特征描述子，完成匹配。實(shí)驗(yàn)結(jié)果表明，該算法實(shí)時(shí)性強(qiáng)、匹配率高，并能較好地反映水下物體的形狀特征。

改進(jìn)Harris-SIFT算法;雙目圖像;角點(diǎn)檢測;匹配

隨著科學(xué)技術(shù)的進(jìn)步，水下勘探、水下目標(biāo)定位、跟蹤等技術(shù)越來越受到世界各國的重視。世界上先進(jìn)的水下機(jī)器人大多采用雙目視覺技術(shù)，能否快速而準(zhǔn)確地對水下拍攝的雙目圖像進(jìn)行特征提取與匹配成為研究的核心和難點(diǎn)。由于水下光線較弱，可見度低，拍攝的圖像不夠清晰且易于變形，圖像的特征不夠明顯，因而特征點(diǎn)的提取工作尤為重要。SIFT算法具有較好的尺度、旋轉(zhuǎn)、光照及視角不變性，可以在復(fù)雜的環(huán)境中匹配并識(shí)別出目標(biāo)物體，是一種較為完善并且穩(wěn)定的方法。但SIFT算法提取的特征點(diǎn)并非人們視覺意義上的角點(diǎn)，不能很好地反映圖像的結(jié)構(gòu);而且大量復(fù)雜的計(jì)算會(huì)導(dǎo)致其實(shí)時(shí)性較差，難以滿足對實(shí)時(shí)性要求較高的雙目立體視覺系統(tǒng)。而傳統(tǒng)的Harris-SIFT算法雖然可以提取角點(diǎn)，但受系數(shù)k和閾值T的影響，提取的特征點(diǎn)不夠準(zhǔn)確且速度偏慢。

本文提出一種改進(jìn)的Harris-SIFT算法。先通過改進(jìn)的Harris算法對圖像進(jìn)行角點(diǎn)檢測，再利用SIFT算法描述圖像特征，最后根據(jù)歐氏距離判定匹配點(diǎn)，并采用RANSAC算法剔除誤匹配的點(diǎn)，完成匹配。

1 Harris算法與改進(jìn)的Harris算法

1.1 Harris角點(diǎn)檢測算法

Harris檢測算法是在Moravec角點(diǎn)檢測算法基礎(chǔ)上擴(kuò)展出來的一種特征點(diǎn)提取算法，對圖像旋轉(zhuǎn)、灰度變化以及視角變換保持較好的穩(wěn)定性。

該算法受自相關(guān)函數(shù)思想的啟發(fā)，給出了自相關(guān)矩陣

式中:Iu(x，y)，Iv(x，y)，Iuv(x，y)分別為圖像點(diǎn)的灰度在u和v方向上的偏導(dǎo)及二階混合偏導(dǎo);M的行列式表示為det(M)，其對角線之和表示為tr(M)。角點(diǎn)響應(yīng)函數(shù)定義為

式中:經(jīng)驗(yàn)值k通常取0.04～0.06。經(jīng)計(jì)算，當(dāng)某一像素點(diǎn)的R值大于設(shè)定的閾值T時(shí)，這個(gè)點(diǎn)即為角點(diǎn)。

角點(diǎn)提取的準(zhǔn)確性和可靠性受經(jīng)驗(yàn)值k的影響，k值的選取會(huì)因圖像的不同而不同。多次調(diào)試k值會(huì)花費(fèi)大量的時(shí)間，導(dǎo)致角點(diǎn)的提取速度變慢。

由于提取角點(diǎn)時(shí)閾值T是確定的，角點(diǎn)提取的效果完全取決于T值的設(shè)定，T值過大會(huì)導(dǎo)致特征點(diǎn)數(shù)目過少，信息量不足，T值過小會(huì)導(dǎo)致特征點(diǎn)數(shù)目過多，計(jì)算量加大。總之，T值過大或過小都會(huì)降低匹配的準(zhǔn)確性。每一幅圖片的屬性都不相同，要想設(shè)定具體的閾值也很困難。此外，常常出現(xiàn)一些點(diǎn)聚集在某個(gè)區(qū)域的現(xiàn)象，會(huì)影響角點(diǎn)分布的均勻性與合理性，進(jìn)而影響匹配的準(zhǔn)確性。

1.2 改進(jìn)的Harris角點(diǎn)檢測算法

針對上述情況，本文對Harris角點(diǎn)檢測算法進(jìn)行了改進(jìn)，使用一種不含k的角點(diǎn)響應(yīng)函數(shù)R

式中:ε為正的微小量。式(3)避免了k值的選取，能夠減小所檢測角點(diǎn)的點(diǎn)位置偏差。

為避免手動(dòng)設(shè)定閾值對角點(diǎn)提取結(jié)果產(chǎn)生的影響，本文采用一種自動(dòng)設(shè)定閾值的方法。采用圖像分塊與鄰近角點(diǎn)剔除的策略，無需設(shè)置閾值，保證角點(diǎn)均勻分布，避免產(chǎn)生聚簇現(xiàn)象。首先，對圖像中每個(gè)像素點(diǎn)進(jìn)行操作，得到矩陣M，再通過式(3)計(jì)算出它們的R值。然后，采用固定塊數(shù)的分塊法將圖像分為N塊，按R值的大小對每塊中的所有角點(diǎn)進(jìn)行排序，本文采用由大到小排序，留下R值較大的角點(diǎn)。最后，選用一個(gè)n×n的模板來處理整幅圖像，保留該模板下多個(gè)角點(diǎn)中R值最大的點(diǎn)，將臨近的角點(diǎn)剔除。這樣，對整幅圖像的角點(diǎn)檢測就已完成。

此外，Harris算法定位精度較低，F(xiàn)orstner算法雖然定位精度較高，但當(dāng)圖像灰度變化時(shí)呈現(xiàn)出算法的不穩(wěn)定性。本文結(jié)合兩種算法，將前面Harris算法提取出來的角點(diǎn)作為Forstner算子最佳窗口的中心點(diǎn)，在窗口內(nèi)實(shí)施加權(quán)中心化，對角點(diǎn)位置進(jìn)行精確定位，將精度提高到亞像素級(jí)。至此，完成了對Harris算法的改進(jìn)。

2 SIFT算法

SIFT算法是David G.Lowe于2004年提出的一種提取圖像局部特征的算法。該算法對圖像尺度變化、旋轉(zhuǎn)等保持不變性，對圖像變形以及光照的變化有很強(qiáng)的適應(yīng)性。

1)多尺度極值點(diǎn)的檢測

高斯卷積核是尺度變換唯一的變換核，亦即唯一的線性核。二維圖像I(x，y)尺度空間的定義為

利用DOG scale-space(高斯差分尺度空間)來檢測穩(wěn)定的關(guān)鍵特征點(diǎn)，具體表示為尺度不同的兩個(gè)高斯差分核和圖像的卷積。

在DOG尺度空間內(nèi)，每個(gè)采樣點(diǎn)均要同其空間內(nèi)的相鄰點(diǎn)逐個(gè)比較，判斷它是極大值或極小值，選出其中的極值點(diǎn)即為尺度空間的局部極值點(diǎn)。

2)精確定位極值點(diǎn)

由于DOG算子對噪聲以及邊緣較敏感，可通過對局部極值點(diǎn)的三維二次函數(shù)擬合來實(shí)現(xiàn)特征點(diǎn)位置和尺度的精確定位，利用D(x，y，σ)的二階泰勒展開式D(X)的插值得到特征點(diǎn)位置及尺度坐標(biāo)的精確值。

式中:向量X=(x，y，σ)，表示采樣點(diǎn)與特征點(diǎn)間的位置、尺度偏移。將候選關(guān)鍵點(diǎn)中低對比度的點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)去除，來增強(qiáng)匹配性能，提高抗噪能力。

3 改進(jìn)的Harris-SIFT算法

由于雙目立體視覺系統(tǒng)對實(shí)時(shí)性要求較高，通過上面對SIFT算法前兩步的分析得知，SIFT算法提取特征點(diǎn)過程較復(fù)雜，不能很好地滿足雙目立體視覺系統(tǒng)對實(shí)時(shí)性的要求。具體體現(xiàn)在以下3個(gè)方面:1)特征提取過程復(fù)雜，計(jì)算時(shí)間長。2)在生成的大量特征點(diǎn)中，能夠正確匹配的特征點(diǎn)很少，影響匹配速度。3)不能準(zhǔn)確定位圖像的角點(diǎn)，提取的特征點(diǎn)不能反映圖像結(jié)構(gòu)。然而，SIFT算法具有較好的尺度、旋轉(zhuǎn)、光照及視角不變性。

通過前面對改進(jìn)Harris算法的介紹，本文發(fā)現(xiàn)改進(jìn)后的Harris算法具有下述優(yōu)點(diǎn):1)實(shí)時(shí)性好，計(jì)算簡單。避免了對系數(shù)k及閾值T的設(shè)置，減少了計(jì)算量，節(jié)省了大量時(shí)間。2)自適應(yīng)能力強(qiáng)。閾值T的自動(dòng)設(shè)定提高了角點(diǎn)檢測的自適應(yīng)能力。3)提取的角點(diǎn)精度高，且分布均勻、合理，反映圖像結(jié)構(gòu)。4)能夠在圖像位置變化及噪聲干擾的情況下準(zhǔn)確檢測特征點(diǎn)，且誤檢率較低，穩(wěn)定性強(qiáng)。然而，它只能在單一尺度下進(jìn)行角點(diǎn)檢測，不具有尺度不變的特性。

所以，為了更準(zhǔn)確、快速地完成對水下圖像的匹配工作，本文提出一種改進(jìn)的Harris-SIFT算法。具體步驟為:先用改進(jìn)的Harris算法對圖像進(jìn)行角點(diǎn)檢測，提取圖像的特征點(diǎn);再為每個(gè)特征點(diǎn)分配方向，并生成SIFT特征描述子;最后從左右兩幅圖像的特征點(diǎn)中確定出合適的匹配點(diǎn)，完成匹配。其總流程如圖1所示。

3.1 為特征點(diǎn)分配方向

運(yùn)用改進(jìn)的Harris算法檢測到圖像的角點(diǎn)之后，本文依據(jù)角點(diǎn)的鄰域像素梯度方向的分布特性給每個(gè)角點(diǎn)分配方向，其梯度計(jì)算公式為

圖1 流程圖

式中:L為角點(diǎn)的尺度;(x，y)為角點(diǎn)的鄰域像素。

實(shí)際應(yīng)用中，創(chuàng)建梯度直方圖用以統(tǒng)計(jì)鄰域像素的梯度方向。分別將主峰值和約為主峰值80%的其他峰值作為該點(diǎn)的主方向和輔助方向，這樣能夠減少圖像旋轉(zhuǎn)對特征點(diǎn)的影響。

3.2 生成SIFT特征描述子

為確保描述子的旋轉(zhuǎn)不變性，將坐標(biāo)軸按照特征點(diǎn)的方向進(jìn)行旋轉(zhuǎn)。用16個(gè)(4×4)種子點(diǎn)來描述每個(gè)特征點(diǎn)，每個(gè)種子點(diǎn)含8個(gè)方向向量，這樣每個(gè)特征點(diǎn)就產(chǎn)生16×8即128個(gè)數(shù)據(jù)，形成128維的SIFT特征向量，再對特征向量的長度做歸一化處理，進(jìn)一步去除光照的影響。

至此，運(yùn)用改進(jìn)的Harris-SIFT算法生成的特征向量能夠去除旋轉(zhuǎn)、尺度、光照變化對特征點(diǎn)的影響。

3.3 特征點(diǎn)的匹配

本文利用描述子的歐氏距離對兩幅圖像的特征點(diǎn)進(jìn)行相似性判定。找出圖像2中與圖像1的某個(gè)特征點(diǎn)歐氏距離最近的兩個(gè)點(diǎn)，計(jì)算最近點(diǎn)與次近點(diǎn)歐氏距離的比值，若比值小于設(shè)定的比例閾值，則判定這兩點(diǎn)為一對匹配點(diǎn)。

最后，利用RANSAC算法篩選并去除錯(cuò)誤的匹配點(diǎn)，盡可能降低錯(cuò)誤率，達(dá)到最佳的匹配效果。

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

選取一組在水下拍攝的雙目圖像，圖像的尺寸均為579×440。圖2a為左攝像頭拍攝的圖像，圖2b為右攝像頭拍攝的圖像。實(shí)驗(yàn)運(yùn)用MTLAB R2009b軟件仿真，并對SIFT算法、Harris-SIFT算法和本文算法進(jìn)行了比較分析。

圖2 攝像頭拍攝的水下模糊圖像

采用SIFT算法、Harris-SIFT算法和本文算法匹配的效果分別如圖3、圖4和圖5所示。表1為采用3種算法得出的實(shí)驗(yàn)數(shù)據(jù)對比。

圖3 SIFT算法匹配圖

圖4 Harris-SIFT算法匹配圖

從圖3～5及表1可看出，采用SIFT算法提取的特征點(diǎn)數(shù)最多，誤匹配數(shù)量也最多，匹配率低，匹配時(shí)間長; Harris-SIFT算法雖然比SIFT算法在性能上有了一些改進(jìn)，但受k和T的影響，仍出現(xiàn)較多的誤匹配點(diǎn)，匹配時(shí)間也較長。而本文算法在縮短匹配時(shí)間的同時(shí)提高了匹配率，雖然特征點(diǎn)數(shù)目有所減少，但提取的點(diǎn)都是水下圖像的角點(diǎn)，且分布比較均勻，精確度高，較好地反映了水下圖像的結(jié)構(gòu)。

圖5 本文算法匹配圖

表1 3種算法的性能比較

5 結(jié)論

水下光線較弱、可見度低，拍攝的圖像不夠清晰且易變形，其特征不夠明顯，難以準(zhǔn)確提取。本文提出一種改進(jìn)的Harris－SIFT算法，先通過改進(jìn)的Harris算法對圖像進(jìn)行角點(diǎn)檢測，再利用SIFT算法描述圖像特征，最后根據(jù)歐氏距離判定匹配點(diǎn)，并采用RANSAC算法剔除誤匹配點(diǎn)，完成匹配。實(shí)驗(yàn)結(jié)果表明，本文算法提取的特征點(diǎn)特征集合性顯著，較好地反映了圖像的結(jié)構(gòu)。同時(shí)，本算法在提高匹配率的基礎(chǔ)上有效地縮短了匹配時(shí)間，即提高了準(zhǔn)確性和實(shí)時(shí)性，更加適合應(yīng)用到雙目立體視覺系統(tǒng)中，為今后水下勘察、目標(biāo)定位、場景的三維重建等方面的研究奠定了良好的基礎(chǔ)。

［1］LOWE D.Distinctive image features from scale－invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91－110.

［2］SCHIMID C，MOHR R，BAUCKHAGEC.Evaluation of interest point detectors［J］.International Journal of Computer Vsion，2000，37(2): 151－172.

［3］常麗萍，冀小平，趙梁.分塊的基于Harris角點(diǎn)檢測的圖像配準(zhǔn)方法［J］.電視技術(shù)，2013，37(1):45－47.

［4］江鐵，朱桂斌，孫奧.特征點(diǎn)提取算法性能分析研究［J］.科學(xué)技術(shù)與工程，2012，12(30):7924－7929.

［5］孟浩，程康.基于SIFT特征點(diǎn)的雙目視覺定位［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2009，30(6):649－652.

［6］邱建國，張建國，李凱.基于Harris與Sift算法的圖像匹配方法［J］.測試技術(shù)學(xué)報(bào)，2009，23(3):271－274.

［7］趙欽君，趙東標(biāo)，韋虎.Harris－SIFT算法及其在雙目立體視覺中的應(yīng)用［J］.電子科技大學(xué)學(xué)報(bào)，2010，39(4):546－550.

［8］胡海青.改進(jìn)SIFT算法在文字圖像匹配中的應(yīng)用［J］.計(jì)算機(jī)工程，2013，39(1):239－243.

Application of Improved Harris－SIFT Algorithm in Underwater Image M atching

WANG Xin，JIA Minzhi
(Institute of Information Engineering，Taiyuan University of Technology，Taiyuan 030024，China)

Due to the problems of the poor real-time performance and moremismatch in the SIFT algorithm，together with the low accuracy and slow speed in the Harris corner detection algorithm，amethod of extracting and matching the feature points for underwater binocular images based on the improved Harris-SIFT algorithm is proposed.The corner points of two images are detected by using the improved Harris algorithm，then the directions for each feature point are distributed.Finally，the SIFT feature descriptors are generated and thematching is completed.In the experimental results，it showes that the algorithm proposed in this paper has good real-time performance and high matching rate，and can reflect the objects’shape featureswell.

improved Harris-SIFT algorithm;binocular images;corner detection;matching

TP391.4

A

王 鑫(1987— )，女，碩士生，主研計(jì)算機(jī)視覺伺服系統(tǒng)、智能控制理論及其應(yīng)用;

?? 雯

2013－07－27

【本文獻(xiàn)信息】王鑫，賈敏智.改進(jìn)Harris-SIFT算法在水下圖像匹配中的應(yīng)用［J］.電視技術(shù)，2014，38(13).

賈敏智(1963— )，副教授，碩士生導(dǎo)師，主要研究方向?yàn)橹悄芸刂评碚摷捌鋺?yīng)用、微型計(jì)算機(jī)控制系統(tǒng)及工程，本文通訊作者。