改進Harris-SIFT算法在雙目立體視覺中的應用*

劉雨婷，王曉東，2，吳建德，2，范玉剛，2，黃國勇，2

（1.昆明理工大學，云南 昆明 650500;2.云南省礦物管道輸送工程技術(shù)研究中心，云南昆明 650500）

0 引言

立體匹配是三維重建中一個至關(guān)重要且最為復雜的一個環(huán)節(jié)，是近年來數(shù)字圖像處理和計算機視領(lǐng)域備受關(guān)注的前沿方向和研究熱點。根據(jù)特征空間、相似性度量、搜索空間和搜索策略的不同，已經(jīng)形成了許許多多各具特色的特征匹配算法，但如何合理提取圖像的特征點并對其進行高精度匹配，仍然是計算機視覺技術(shù)的一個瓶頸，至今還未完全得到解決。

近年來，相繼出現(xiàn)了各種匹配算法，并且結(jié)合了許多數(shù)學理論和方法，繼而有新的匹配算法被不斷提出。比如:早期的 Moravec 檢測算子、Harris 檢測算子［1，2］、SUSAN 檢測算子［3］和目前較新的 SIFT（scale invariant feature transform）算法［4，5］，以及PCA-SIFT 算法、SVD 匹配法、積分圖像法［6］。其中，SIFT 算子［7，8］是目前最成功的局部特征提取算子，研究表明:SIFT特征點定位準確，具有很好的尺度、旋轉(zhuǎn)、視角和光照不變性，優(yōu)于其他局部特征提取算子。但由于SIFT提取的特征點在圖像上并沒有實際的物理特征即非視覺上的角點，并且SIFT計算量大、特征點多、實時性較差，難以應對于對實時性要求較高的系統(tǒng)，如基于雙目立體視覺的實時跟蹤系統(tǒng)。而Harris算子［9，10］只用到了灰度的一階差分與濾波，使得計算簡單，具有較好的重復性與信息量;同時，Harris算子對圖像中的每一個點都計算其興趣值，通過領(lǐng)域選優(yōu)，使得角點分布均勻，是一種簡單、有效、穩(wěn)定的角點提取算法。

本文針對SIFT算法的實時性差問題，結(jié)合Harris提取角點的顯著性和SIFT描述子，并由于Harris算子的尺度敏感性，提出了一種改進Harris-SIFT算法，并應用于雙目立體視覺圖像匹配中，實驗結(jié)果表明了該方法在保持很好匹配速率時能降低算法復雜度、提高算法效率。

1 特征點提取算法

1.1 SIFT算法與分析

SIFT算法是一種基于尺度空間、圖像縮放、旋轉(zhuǎn)甚至仿射變換保持不變性的圖像局部特征提取算法［11，12］。其算法步驟可分為以下4步:

1）檢測尺度空間極值點:Lowe首先定義了用DOG算子來作用于圖像得到差值圖像，在差值圖像的各像素點的26鄰域內(nèi)，若其灰度值為最大或最小，則記錄此點的位置和它所在的尺度，作為候選特征點。

2）精確定位極值點:通過擬和三維二次函數(shù)以精確確定關(guān)鍵點的位置和尺度，同時過濾低對比度的關(guān)鍵點和不穩(wěn)定的邊緣響應點，以增強匹配穩(wěn)定性、提高抗噪聲能力。

3）每個關(guān)鍵點指定方向參數(shù):利用關(guān)鍵點鄰域像素的梯度方向分布特性為每個關(guān)鍵點指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。

4）關(guān)鍵點描述子的生成:為確保特征向量旋轉(zhuǎn)不變性，先將坐標軸旋轉(zhuǎn)到特征點主方向上，采用高斯圓形窗口對梯度模值進行高斯加權(quán)，以特征點為中心取16×16的窗口，將這個窗口分成4×4個子區(qū)域，每個區(qū)域通過梯度直方圖統(tǒng)計8個方向，共產(chǎn)生一個包括128個特征信息的特征向量。

1.2 改進Harris算法

針對經(jīng)典Harris角點檢測算子對尺度比較敏感的這一缺點，以尺度空間為基礎，從空間域和尺度域來確定特征點，從而使改進的檢測算子具有特殊的尺度不變性，具體的就是把2個域中的極值點確定為角點，這樣檢測到的角點在具有合適參數(shù)的情況下能提高穩(wěn)定性［13］。改進的Harris檢測算子如式（1）所示

式中Ix，Iy分別為圖像在x和y方向上的偏導數(shù)，σl為積分尺度，σD為微分尺度且σl=sσD，其中s為一個不大于1的常數(shù)，?為對函數(shù)進行卷積運算。角點的定義跟自相關(guān)矩陣M的特征值有關(guān)，當某點的M求解得到2個足夠大的特征值λ1和λ2時，此點就是角點。

2 改進Harris-SIFT算法

當應用于對實時性要求較高的雙目立體視覺系統(tǒng)時，SIFT特征提取算法主要有如下缺點:特征提取復雜度太高，計算時間太長;生成的特征點太多，影響匹配和搜索速度;SIFT特征點不能準確定位角點，大部分特征點不能反映圖像的結(jié)構(gòu)。所以，為了解決SIFT算法的實時性問題，可以用改進Harris特征檢測算子取代SIFT中的提取算法，然后再用SIFT特征描述符來構(gòu)建特征向量，從而進行特征匹配。具體步驟如下:

1）檢測圖像角點

首先選擇方差進行高斯卷積，在每一尺度對每個角點采取局部非極大抑制法提高定位精度，得到該尺度下的粗略角點。然后對上步中每個尺度下檢測出來的角點，用3×3的模板覆蓋該尺度所有的角點，如存在多于一個角點，則取最大值作為角點，得到該尺度下的最終角點;接著從第2個尺度開始，核對在當前尺度下的每個角點，看其在前一尺度中是否出現(xiàn)過，如果沒有，則保留;如果有，則剔除。最后累計從第3步得到的全部角點，就是本文算法提取出的角點。

2）確定角點的特征向量

對得到的每一個角點處，定義其梯度幅值和方向如公式（2）、式（3）所示

分別對其3×3的鄰域內(nèi)的9個像素點，按照上式求其梯度幅值和方向，取累加后的幅值最大的前2個方向，一個主方向，一個輔方向，再加角點自身的梯度向量，作為角點的特征向量，從而得到反映角點特征的2個方向向量和1個梯度向量。

3）生成SIFT特征描述子

在本文的實際應用中，對每個角點、梯度向量保持不變，然后分別旋轉(zhuǎn)坐標軸到主方向。

如圖1所示，在以角點為中心的8×8鄰域內(nèi)，按照上一步，得到2個32維方向向量和1個2維梯度向量。當角點的特征向量生成以后，接下來采用歐氏距離法作為向量相似的的判定。

圖1 由角點鄰域梯度信息生成特征點描述子Fig 1 Corner point neighborhood gradient information to generate feature point descriptor

4）特征匹配

圖2顯示了特征匹配的一般步驟，在前文已經(jīng)進行了特征點的提取和描述，接下來對2幅圖像進行匹配。

圖2 特征匹配的步驟Fig 2 Feature matching step

對SIFT特征描述子進行相似度量時，采用歐氏距離作為相似性準則［14］

D越小，表明特征點對距離越“近”，相似程度越高。

匹配的過程是:對于左圖像中的特征點，采用最近鄰法搜索右圖像中的特征點，在右圖像中找到距離最近和次近的2個特征點，如果最近距離和次近距離的比值小于設定的閾值，則接受這一對匹配點。由此得到的初始匹配結(jié)果，難免存在一些誤匹配點，因此，需要進一步剔除誤匹配點，常采用的方法是RANSAC（隨機抽樣一致性算法）［15］。

3 實驗結(jié)果與分析

本文在VC++6.0與Open CV平臺上實現(xiàn)圖像匹配，主要用C++語言實現(xiàn)了改進Harris-SIFT算法，并對本文提出的改進Harris-SIFT算法與原SIFT算法的匹配性能進行了實驗分析和比較。

圖3、圖4和圖5、圖6為2組圖像的匹配實驗結(jié)果，可以看出:SIFT算法提取的不是角點，不能反映圖像的視覺角點，而本文算法結(jié)合改進Harris和SIFT算法提取的特征點都是角點，并降低了特征提取的復雜度，大大提高了原SIFT算法的實時性，并保證了圖像的正確匹配。

圖3 SIFT匹配Fig 3 SIFT matching

由表1、表2匹配實驗結(jié)果可知，在一定程度上，本算法解決了SIFT算法的2個問題:

1）SIFT算法要進行多次高斯卷積檢測特征點，并運算高斯差分圖像，從而占用大量時間。本算法在生成SIFT特征描述之前用Harris算子檢測角點，而Harris算子計算量小，并去除了大量不顯著特征點，同時也降低了特征描述生成階段的計算量。因此，改進Harris-SIFT算法大大提高了實時性。

2）改進Harris-SIFT算法生成的特征點數(shù)量遠少于SIFT算法，所提取的特征點即為角點，反映了圖像結(jié)構(gòu)，有利于正確匹配，并且減少了待匹配特征點數(shù)，從而待匹配時間縮短。

圖5 SIFT匹配Fig 5 SIFT matching

圖6 改進Harris-SIFT匹配Fig 6 Improved Harris-SIFT matching

表1 匹配結(jié)果統(tǒng)計Tab 1 Match result statistics

表2 匹配結(jié)果統(tǒng)計Tab 2 Match result statistics

4 結(jié)束語

SIFT算法在圖像匹配中應用廣泛，但應用于實時性要求較高的雙目立體視覺中，該算法的復雜度較高，實時性很差，且該算法的優(yōu)勢很難體現(xiàn)出來。本文提出的改進Harris-SIFT算法，有效地集成了改進Harris特征提取算子和SIFT描述子的特性，降低了特征提取和特征匹配的復雜度，大大提高了算法的實時性。通過雙目立體視覺的匹配結(jié)果可以看出:本算法有較好的實時性。

［1］唐永鶴，陶華敏.一種基于Harris算子的快速圖像匹配算法［J］.武漢大學學報，2012，37（4）:406-414.

［2］王旭光，王志衡.Harris相關(guān)與特征匹配［J］.模式識別與人工智能，2009，22（4）:505-513.

［3］Smith S M，Brady M.SUSAN——A new approach to low level image processing［J］.International Journal of Computer Vision，1997，23（1）:45-78.

［4］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60（2）:91-110.

［5］Tuytelaars T，Mikolajczyk K.Local invariant feature detectors:A survey［J］.Foundations and Trends in Computer Graphics and Vision，2008，3（1）:177-280.

［6］艾海舟，興軍亮.計算機視覺——算法與應用［M］.北京:清華大學出版社，2012:332-358.

［7］唐朝偉，肖 健.全局結(jié)構(gòu)化SIFT描述子在圖像匹配中的應用［J］.華中科技大學學報，2012，40（1）:15-20.

［8］Mikolajczyk K，Schmid C.A performance evaluation of localdescriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）:1615-1630.

［9］高 健，黃心漢.基于Harris角點和高斯差分的特征點提取算法［J］.模式識別與人工智能，2008，21（2）:171-176.

［10］孔 軍，湯心溢.多尺度特征提取的雙目視覺匹配［J］.計算機工程與應用，2010，46（33）:1-4.

［11］孟 浩，程 康.基于SIFT特征點的雙目視覺定位［J］.哈爾濱工程大學學報，2009，30（6）:649-652.

［12］王 民，劉偉光.基于改進SIFT特征的雙目圖像匹配算法［J］.計算機工程與應用，2013，49（2）:203-207.

［13］肖得勝，劉桂華.多尺度Harris角點檢測的FPGA實現(xiàn)［J］.通信技術(shù)，2012，45（11）:85-87.

［14］邵 暖，劉 樂.基于特征匹配算法的雙目視覺測距［J］.燕山大學學報，2012（1）:57-61.

［15］常 青，張 斌.基于SIFT和RANSAC的特征圖像匹配方法［J］.華東理工大學學報，2012（6）:747-751.