改進(jìn)SIFT算法的圖像雙向配準(zhǔn)技術(shù)

劉清清，李士心，孫夏麗，王 坤

（天津職業(yè)技術(shù)師范大學(xué)大學(xué)電子工程學(xué)院，天津 300222）

近年來，圖像配準(zhǔn)技術(shù)被廣泛應(yīng)用于醫(yī)學(xué)圖像分析、遙感圖像處理、計(jì)算機(jī)視覺、集成電路圖像拼接等領(lǐng)域，隨著對(duì)圖像配準(zhǔn)研究的不斷深入，多領(lǐng)域的應(yīng)用場(chǎng)景對(duì)圖像配準(zhǔn)技術(shù)的需求也越來越高。目前，實(shí)現(xiàn)圖像配準(zhǔn)技術(shù)的算法主要分為基于灰度信息、變換域和特征匹配。其中，基于特征的圖像配準(zhǔn)根據(jù)選取特征屬性的不同可細(xì)分為若干方法，如基于線特征的Hough變換、基于輪廓特征的Log算子、Sobel邊緣提取算子、Canny邊緣檢測(cè)算子等，以及目前應(yīng)用最為廣泛的基于特征點(diǎn)配準(zhǔn)的SIFT算法等[1]。本文主要針對(duì)基于尺度不變特征變換（scale-invariant feature transform，SIFT）算法的k-d樹配準(zhǔn)算法進(jìn)行分析并改進(jìn)。SIFT是一種具有尺度不變性的局部特征描述子，可以檢測(cè)并描述輸入圖像中的極值點(diǎn)[2]，該特征點(diǎn)對(duì)待配準(zhǔn)圖像的旋轉(zhuǎn)、尺度、亮度等因素保持不變性，因此該算法適用于多種場(chǎng)景[3]。但是，由于一個(gè)特征點(diǎn)具有多維描述子，且特征描述子的數(shù)量與圖像配準(zhǔn)的速度成正比，故傳統(tǒng)的k-d樹單向匹配算法易出現(xiàn)錯(cuò)誤匹配，同時(shí)也無法滿足實(shí)際應(yīng)用的實(shí)時(shí)性。因此，本文在SIFT描述子匹配階段，采用準(zhǔn)歐氏距離代替歐氏距離，匹配效率顯著提高。

1 基于SIFT算法的圖像配準(zhǔn)

1.1 特征點(diǎn)檢測(cè)

1.1.1 構(gòu)建尺度空間

SIFT算法在構(gòu)建尺度空間時(shí)采取高斯核函數(shù)進(jìn)行濾波來模擬各個(gè)尺度下的特征情況，使待配準(zhǔn)圖像保留更多的信息以便后續(xù)進(jìn)行特征的提取與匹配[4]。通過將待配準(zhǔn)圖像與具有可變核的高斯濾波進(jìn)行卷積，從而得到圖像的高斯金字塔Log。高斯卷積核是唯一可以實(shí)現(xiàn)尺度變換的線性變換核，尺度空間圖像即為初始圖像與不同尺度參數(shù)σ進(jìn)行卷積運(yùn)算所產(chǎn)生的圖像，圖像I（x，y）的尺度空間L（x，y，σ）表達(dá)式為

式中：G（x，y，σ）為二維高斯函數(shù)；I（x，y）為原始圖像中某點(diǎn)的像素值；σ為尺度因子，σ值越大，代表初始圖像被平滑得越多，對(duì)應(yīng)的圖像尺度越大[5]。

1.1.2 構(gòu)建高斯金字塔

為了在尺度空間有效檢測(cè)到穩(wěn)定的關(guān)鍵點(diǎn)，SIFT算法使用了高斯差分尺度空間算子DOG（difference of Gaussian），DOG算子定義為不同尺度的高斯差分核與圖像卷積，其是歸一化高斯拉普拉斯算子Log的近似[6]，表示為

高斯差分金字塔的生成如圖1所示。圖像的金字塔模型是指將原始圖像不斷降階采樣，得到一系列大小不一的圖像，由大到小、從下到上構(gòu)成的塔狀模型。初始圖像為金字塔的第一層，每組中相鄰上下兩層圖像相減，下一層的圖像是由上一層圖像降采樣而得。

圖1 高斯差分金字塔的生成

1.1.3 DOG局部極值點(diǎn)檢測(cè)

SIFT算法中的特征點(diǎn)是由高斯差分尺度空間中的局部極值點(diǎn)組成，在建立高斯差分金字塔尺度空間后，將每個(gè)像素點(diǎn)與其同一尺度以及上下相鄰尺度的26個(gè)像素點(diǎn)作比較，局部極值點(diǎn)檢測(cè)如圖2所示。

圖2 局部極值點(diǎn)檢測(cè)

若某檢測(cè)點(diǎn)比其圖像域與尺度域的相鄰點(diǎn)大或小，該點(diǎn)即為該尺度上的局部極值點(diǎn)[7]。對(duì)于每組圖像的首尾兩層需人為使用高斯模糊生成2幅圖像，以尋找首尾兩層的極值點(diǎn)，滿足尺度變化的連續(xù)性。

1.1.4 消除不合格關(guān)鍵點(diǎn)

DOG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng)，為了提高圖像配準(zhǔn)的穩(wěn)定性和準(zhǔn)確性，通過對(duì)檢測(cè)出的極值點(diǎn)進(jìn)行差分處理，擬合3位二次函數(shù)確定特征點(diǎn)的位置和尺度，消除低對(duì)比度和不穩(wěn)定的邊緣響應(yīng)點(diǎn)。

利用DOG函數(shù)在尺度空間的Taylor展開式對(duì)尺度空間DOG函數(shù)進(jìn)行曲線擬合，其擬合函數(shù)表示為

式中：X=（x，y，σ）T。

對(duì)Taylor展開式求導(dǎo)，并令其導(dǎo)數(shù)為0，得到極值點(diǎn)的偏移量為

通過控制偏移量，可以消除低對(duì)比度的極值點(diǎn)。

由于DOG對(duì)圖像中的邊緣有比較強(qiáng)的響應(yīng)值，如果極值點(diǎn)在圖形的邊緣上，這些點(diǎn)就是不穩(wěn)定的點(diǎn)。在邊緣梯度的橫向方向上主曲率值比較大，而沿著邊緣垂直方向則主曲率值較小，主曲率可以通過2×2的Hessain矩陣H求出

式中：Dxx、Dxy、Dyy是由極值點(diǎn)鄰域?qū)?yīng)位置的差分得到的。

令H的特征值α和β表示x和y方向的梯度，特征值α較大、β較小，D的主曲率與H的特征值成正比，則

Tr（H）是矩陣H的對(duì)角線元素之和，Det（H）是矩陣H的行列式。令α=γβ，則

若上式成立，則保留該極值點(diǎn)，否則剔除該極值點(diǎn)[8]。

1.1.5 關(guān)鍵點(diǎn)的方向分配

上述步驟確定了特征點(diǎn)的尺度和位置，保證了SIFT算子的尺度不變性。此外，特征點(diǎn)還具有旋轉(zhuǎn)不變性，通過利用圖像的局部結(jié)構(gòu)特征計(jì)算關(guān)鍵點(diǎn)的方向。采集特征點(diǎn)所在DOG金字塔圖像3σ鄰域像素的梯度m（x，y）和方向θ（x，y）分布特征，如

計(jì)算出特征點(diǎn)的梯度后，通過直方圖統(tǒng)計(jì)鄰域像素的梯度和幅值。直方圖以梯度方向角為橫軸，將0°～360°劃分為若干個(gè)區(qū)間，以各梯度方向角所對(duì)應(yīng)的幅值累加值為縱軸[9]。直方圖的峰值即為該像素點(diǎn)的主方向，大于主峰值80%的方向?yàn)檩o方向。

1.2 生成特征點(diǎn)描述子

為保證特征點(diǎn)的獨(dú)特性，提高圖像配準(zhǔn)的準(zhǔn)確率，對(duì)于每個(gè)特征點(diǎn)用一組向量描述，生成特征點(diǎn)描述子。旋轉(zhuǎn)坐標(biāo)軸的方向使坐標(biāo)軸與特征點(diǎn)方向保持一致，選取以特征點(diǎn)為中心的16×16大小的區(qū)域窗口。特征描述子的生成如圖3所示。

圖3 特征描述子的生成

從圖3可知，特征點(diǎn)位于正中間，特征點(diǎn)鄰域所在尺度空間的像素由左側(cè)的每一個(gè)小方格表示，像素的梯度模值和梯度方向分別由右側(cè)的每個(gè)箭頭的長(zhǎng)度和方向表示。對(duì)每個(gè)像素進(jìn)行高斯加權(quán)運(yùn)算，鄰域像素越靠近特征點(diǎn)，梯度方向信息的價(jià)值就越大[10]。計(jì)算左側(cè)每4×4個(gè)方格區(qū)域中8個(gè)方向的梯度方向直方圖，根據(jù)梯度方向形成如右側(cè)的種子點(diǎn)。每個(gè)特征點(diǎn)最終由4×4個(gè)種子點(diǎn)組成，每個(gè)種子點(diǎn)共包含8個(gè)方向的梯度信息。對(duì)于每個(gè)特征點(diǎn)形成一個(gè)4×4×8=128維的描述子，每一維都可以代表相應(yīng)4×4方格的尺度或方向，即生成了128維的特征向量描述子。

1.3 基于k-d樹的單向配準(zhǔn)

SIFT特征點(diǎn)的相似度可以由特征向量的歐氏距離度量，歐氏距離是一個(gè)經(jīng)常引用的距離定義，是指在n維空間中向量的自然長(zhǎng)度（即該點(diǎn)到原點(diǎn)的距離）或2個(gè)點(diǎn)的真實(shí)距離。以待配準(zhǔn)圖像中的某個(gè)特征點(diǎn)為基準(zhǔn)，找到原圖像中與待配準(zhǔn)圖像的特征點(diǎn)歐氏距離最鄰近的特征點(diǎn)和次鄰近的特征點(diǎn)，若最近的距離除以次鄰近的距離的值低于設(shè)定的閾值時(shí)，則即為匹配點(diǎn)[11]。通常以0.8為比例閾值，但實(shí)際應(yīng)用中該閾值由待配準(zhǔn)圖像的大小、亮度等因素決定，合理的閾值可以提高配準(zhǔn)的準(zhǔn)確度。

搜索最鄰近點(diǎn)和次鄰近點(diǎn)通常采用窮舉策略，即根據(jù)原圖像中的某一特征點(diǎn)與待配準(zhǔn)圖像中的特征點(diǎn)逐一匹配，該策略需要遍歷所有特征描述子，搜索效率不高。本文采用k-d樹對(duì)鄰近點(diǎn)進(jìn)行搜索匹配，先建立k-d樹，對(duì)特征描述子數(shù)據(jù)進(jìn)行分類整理，從根節(jié)點(diǎn)出發(fā)，根據(jù)索引樹朝鄰近點(diǎn)所在的方向逼近，直至找到包含目標(biāo)點(diǎn)的的葉子節(jié)點(diǎn)，計(jì)算葉子節(jié)點(diǎn)的歐氏距離，找到最鄰近和次鄰近的特征點(diǎn)進(jìn)行匹配。

構(gòu)建k-d樹是一個(gè)逐級(jí)展開的遞歸過程[12]。首先確定分割域的取值，計(jì)算特征描述子的特征向量在每個(gè)維度上的數(shù)據(jù)方差，方差最大的值相對(duì)應(yīng)的維數(shù)即為分割域的值；確定節(jié)點(diǎn)數(shù)據(jù)的域值，所有特征描述符向量按照分割域的值排序，中位數(shù)即為節(jié)點(diǎn)數(shù)據(jù)；確定左子空間和右子空間，分割平面將整個(gè)空間分為2部分，分割域中小于節(jié)點(diǎn)數(shù)據(jù)的特征描述符向量對(duì)應(yīng)的特征點(diǎn)為左子空間，大于節(jié)點(diǎn)數(shù)據(jù)的特征描述符向量對(duì)應(yīng)的特征點(diǎn)則為右子空間。對(duì)左、右子空間內(nèi)的數(shù)據(jù)分別重新遍歷根節(jié)點(diǎn)，即可得到下一級(jí)的子節(jié)點(diǎn)，同時(shí)將空間和數(shù)據(jù)集再進(jìn)一步細(xì)分，如此反復(fù)直到空間中只包含1個(gè)數(shù)據(jù)點(diǎn)。從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)所遍歷的所有節(jié)點(diǎn)構(gòu)成了葉子節(jié)點(diǎn)的索引。

特征匹配另一個(gè)重要環(huán)節(jié)是在k-d樹中查找數(shù)據(jù)，其目的是找到在k-d樹中與特征點(diǎn)距離最近的數(shù)據(jù)點(diǎn)。從k-d樹的根節(jié)點(diǎn)開始搜索，若待查詢節(jié)點(diǎn)小于k-d樹節(jié)點(diǎn)分割域的值，則優(yōu)先搜索左子樹分支，反之，則搜索右子樹分支。順著搜索路徑找到葉子節(jié)點(diǎn)，該葉子節(jié)點(diǎn)對(duì)應(yīng)的特征點(diǎn)為最近鄰特征點(diǎn)的概率最大。沿搜索路徑回溯到其父節(jié)點(diǎn)，在該父節(jié)點(diǎn)的其他分支反向查找是否有距離特征點(diǎn)更近的數(shù)據(jù)點(diǎn)和次鄰近點(diǎn)，若無更近的數(shù)據(jù)點(diǎn)，則該葉子節(jié)點(diǎn)為最近鄰特征點(diǎn)；若有更近的數(shù)據(jù)點(diǎn)，則需繼續(xù)搜索其他路徑，直至搜索路徑全部回溯完畢。

2 改進(jìn)算法與實(shí)驗(yàn)結(jié)果

2.1 改進(jìn)算法

傳統(tǒng)的配準(zhǔn)算法是從k-d樹的父節(jié)點(diǎn)開始向下搜索至葉子節(jié)點(diǎn)，根據(jù)原圖像中的特征點(diǎn)搜索待配準(zhǔn)圖像中對(duì)應(yīng)的特征點(diǎn)，具有單向匹配性。每個(gè)像素點(diǎn)具有多個(gè)方向向量，方向不同屬于不同的特征描述子，但實(shí)際為同一像素點(diǎn)，匹配時(shí)易出現(xiàn)同一點(diǎn)重復(fù)匹配的情況，采取雙向匹配即可消除大部分重復(fù)的匹配點(diǎn)[13]。

傳統(tǒng)的圖像匹配采用歐氏距離度量特征點(diǎn)的相似性，在二維圖像中歐氏距離定義為

本文采用準(zhǔn)歐氏距離進(jìn)行圖像配準(zhǔn)，準(zhǔn)歐氏距離定義為

根據(jù)定義可以看出，計(jì)算準(zhǔn)歐氏距離明顯比計(jì)算歐氏距離運(yùn)算簡(jiǎn)單，求得的數(shù)值普遍偏小，采用準(zhǔn)歐氏距離可明顯縮短運(yùn)算時(shí)間，提高了算法的匹配效率[14]。

雙向匹配即在傳統(tǒng)的配準(zhǔn)算法基礎(chǔ)上，反向搜索已被匹配的特征點(diǎn)在原圖像中與之匹配的特征點(diǎn)，若正向匹配與反相匹配中2點(diǎn)的準(zhǔn)歐氏距離小于設(shè)定的閾值，則該2點(diǎn)即為正確的匹配點(diǎn)。

式中：D（xi，yj）、D（yj，xi）分別為原圖像和待配準(zhǔn)圖像中一對(duì)匹配點(diǎn)的正向和反向的準(zhǔn)歐氏距離；r1和r2分別為正向閾值和反向閾值，若滿足上式，則xi和yj為一對(duì)正確的匹配點(diǎn)[15]。

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

實(shí)驗(yàn)在Widows 10環(huán)境下采用Matlab 2017和C編程對(duì)本文提出的改進(jìn)SIFT算法的圖像雙向配準(zhǔn)算法進(jìn)行實(shí)現(xiàn)，2組實(shí)驗(yàn)圖片分別通過室外自然光和室內(nèi)光線下手機(jī)拍攝獲取，對(duì)2幅不同光照、不同角度的圖片進(jìn)行特征匹配，通過特征點(diǎn)匹配正確率進(jìn)行定量分析[16-17]。室外自然光線下和室內(nèi)光線下基于SIFT特征的圖像配準(zhǔn)分別如圖4、圖5所示。

圖4 室外自然光線下基于SIFT特征的圖像配準(zhǔn)

圖5 室內(nèi)光線下基于SIFT特征的圖像配準(zhǔn)

在室外光線下，通過平移、對(duì)焦等操作采集具有重疊部分的圖片，原圖像共檢測(cè)出866個(gè)特征點(diǎn)，待配準(zhǔn)圖像共檢測(cè)出977個(gè)特征點(diǎn)。在室內(nèi)光線下，拍攝時(shí)通過平移、旋轉(zhuǎn)、縮放等操作采集具有重疊部分的圖片，原圖像共檢測(cè)出572個(gè)特征點(diǎn)，待配準(zhǔn)圖像共檢測(cè)出724個(gè)特征點(diǎn)。室外、室內(nèi)拍攝的2組圖片分別基于SIFT特征的傳統(tǒng)單向配準(zhǔn)結(jié)果與改進(jìn)的SIFT特征的圖像雙向匹配的數(shù)據(jù)結(jié)果如表1所示。

表1 圖像匹配數(shù)據(jù)（基于歐氏距離的單向配準(zhǔn)/基于準(zhǔn)歐氏距離的雙向配準(zhǔn)）

通過對(duì)比不同光線下的2組圖片采用2種方法匹配的數(shù)據(jù)可以看出，改進(jìn)后的算法在匹配點(diǎn)對(duì)數(shù)上分別減少68對(duì)、30對(duì)，錯(cuò)誤匹配點(diǎn)數(shù)分別為52對(duì)、36對(duì)，與傳統(tǒng)配準(zhǔn)方法相比，匹配正確率約提高6%，但時(shí)間卻縮短為原來的69%。故本文提出的改進(jìn)算法在實(shí)際應(yīng)用中有效提高了圖像配準(zhǔn)技術(shù)的效率和質(zhì)量。

3 結(jié)語

本文分析了SIFT特征的提取、描述過程，介紹了SIFT特征基于k-d樹單向配準(zhǔn)的方法，并提出一種改進(jìn)的配準(zhǔn)算法，采用準(zhǔn)歐氏距離代替歐氏距離進(jìn)行運(yùn)算，縮短了運(yùn)算時(shí)間，提高了配準(zhǔn)的速度，且使用雙向配準(zhǔn)的方法進(jìn)行特征點(diǎn)匹配，有效消除了部分誤匹配點(diǎn)與重復(fù)匹配點(diǎn)，提高了圖像配準(zhǔn)的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)算法在保證特征點(diǎn)匹配性能的前提下，有效提高了圖像配準(zhǔn)的速度和正確率，對(duì)日后基于SIFT算法的圖像配準(zhǔn)技術(shù)在各領(lǐng)域的應(yīng)用研究具有一定的借鑒意義。