也就是說(shuō)多尺度表示時(shí)，都會(huì)有平滑這一步

2.2.2尺度空間

上面提到的四分樹或者八分樹以及金字塔表示法，在獲得多尺度時(shí)所采取的步驟是相當(dāng)粗略的，尺度與尺度之間的“間隔”太大。而這里要提到的“尺度空間”（Scale-Space ）表示法是多尺度表示的另外一種有效方法，它的尺度參數(shù)是連續(xù)的，并且所有尺度上空間采樣點(diǎn)個(gè)數(shù)是相同的（實(shí)際上，一個(gè)尺度上得到的就是一幅圖像，尺度空間采樣點(diǎn)也就是該尺度上圖像的像素點(diǎn)。也就是說(shuō)，尺度空間表示法在各個(gè)尺度上圖像的分辨率都是一樣的）。尺度空間表示的主要思想是，由原始信號(hào)（例如一幅圖像）生成一系列信號(hào)，并用這些信號(hào)來(lái)表示原始信號(hào)，這個(gè)過(guò)程中，精細(xì)尺度的信息被逐步的平滑掉（可以認(rèn)為是細(xì)節(jié)信息被丟棄）。

要注意的是，并不是所有的尺度函數(shù)都可以用于生成尺度空間。因?yàn)橐粋€(gè)很重要的問(wèn)題是，從精細(xì)尺度到較粗糙的尺度的變換過(guò)程中，信息被逐漸的簡(jiǎn)化和削弱。也就是說(shuō)，較粗尺度不可能產(chǎn)生較細(xì)尺度中沒(méi)有的特征。Koenderink[7]（1984 ）和Lindeberg[8]（1994 ）已經(jīng)證明，在一些合理的約束之下，高斯函數(shù)是唯一的尺度空間的平滑核函數(shù)[7]，而且是唯一的線性平滑核函數(shù)[8]

產(chǎn)生尺度空間的公式可以表示如下：

 （1）

公式（1）表示，以t 作為尺度參數(shù)，在整個(gè)定義域上用二維高斯核與輸入圖像做卷積，得到與t 對(duì)應(yīng)的尺度（即在該尺度上的一副圖像）。也可以采用與之等價(jià)的操作：

公式（2）采用了物理學(xué)中著名的熱擴(kuò)散公式，熱擴(kuò)散公式描述了在均勻介質(zhì)中，熱量是如何向各個(gè)方向均勻傳導(dǎo)的。注意到（2）式右邊是拉普拉斯算子的形式，拉普拉斯算子是各向同性的，這恰好符合熱傳導(dǎo)的特性。

3 SIFT方法介紹

　　SIFT 特征的優(yōu)點(diǎn)在前面已經(jīng)做了說(shuō)明，下面將對(duì)SIFT 方法做詳細(xì)的介紹。SIFT 算法有以下幾個(gè)步驟：

　　1. 檢測(cè)尺度空間的極值點(diǎn)。

　　2. 抽取穩(wěn)定的關(guān)鍵點(diǎn)。

　　3. 為每個(gè)關(guān)鍵點(diǎn)指定一個(gè)或者多個(gè)方向。

　　4. 生成特征點(diǎn)描述子。

3.1 相關(guān)工作

       采用特征點(diǎn)進(jìn)行圖像匹配可以追溯到1981 年，Moravec[9] 采用角點(diǎn)檢測(cè)做立體匹配。1988 年，Harris 和Stephens[10] 改進(jìn)了Moravec 的檢測(cè)器，使檢測(cè)到的特征更加穩(wěn)定。1992 年，Harris[11] 顯示了他的角點(diǎn)檢測(cè)器在運(yùn)動(dòng)跟蹤和3 維重構(gòu)方面的優(yōu)勢(shì)，從此之后，角點(diǎn)檢測(cè)方法被廣泛的使用。但是角點(diǎn)檢測(cè)有兩個(gè)問(wèn)題，一是不但可以檢測(cè)出角點(diǎn)，而且對(duì)邊緣也十分敏感；二是它不是尺度無(wú)關(guān)的方法。焦點(diǎn)檢測(cè)最初的應(yīng)用多在于運(yùn)動(dòng)跟蹤和立體匹配方面，后來(lái)Zhang 等人[12] 在1995 年實(shí)現(xiàn)了圖像角點(diǎn)的匹配。他們使用了角點(diǎn)鄰域的關(guān)聯(lián)窗來(lái)尋找可能的匹配。 19 97 年Schmid 和Mohr[13]做出了開創(chuàng)性的工作，他們采用圖像的局部特征進(jìn)行圖像匹配，使得一個(gè)特征可以和一個(gè)大的圖像庫(kù)中的圖像做匹配。他們同樣采用Harris 角點(diǎn)，但不同的是，他們開創(chuàng)性的使用了旋轉(zhuǎn)不變的、圖像局部區(qū)域的描述子。 Harris 角點(diǎn)檢測(cè)對(duì)尺度變化十分敏感，Lowe 在1999 年實(shí)現(xiàn)了局部特征的尺度無(wú)關(guān)性，并且他提出了新的局部描述子，這種描述子更具獨(dú)特性和魯棒性。

        最近，有很多工作致力于使局部特征對(duì)仿射變換具有不變性：Baumberg, 2000[14]; Tuytelaars and Van Gool, 2000[15]; Mikolajczyk and Schmid, 2002[16]; Schaffalitzky and Zisserman, 2002[17]; Brown and Lowe, 2002[18] 。

 （在開始之前，需要將彩色圖像處理成灰度圖像），然后進(jìn)行3.2中所說(shuō)的內(nèi)容

3.2  建立圖像尺度空間(或高斯金字塔)，并檢測(cè)極值點(diǎn)

提取尺度不變的特征點(diǎn)，其主要思想是提取的特征點(diǎn)出現(xiàn)在任何一個(gè)尺度上。這樣不論圖像的尺度如何變化，總能夠提取出這種特征點(diǎn)。檢測(cè)尺度無(wú)關(guān)的特征點(diǎn)可以通過(guò)搜索所有可能的尺度，這可以基于尺度空間理論來(lái)解決。

前面已經(jīng)提到，在一些合理的假設(shè)之下，高斯函數(shù)是得到圖像尺度空間唯一可用的核函數(shù)。將圖像I (x, y) 的尺度定義為一個(gè)函數(shù)L(x, y,σ) ，它由高斯函數(shù)G(x, y,σ) 和圖像I (x, y) 卷積得到：

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

為了在尺度空間中高效的檢測(cè)穩(wěn)定關(guān)鍵點(diǎn)的位置，[1][2] 提出在高斯差分函數(shù)與圖像卷積得到的空間D(x, y,σ) 中尋找極值點(diǎn)，

D(x, y,σ) = （G(x, y, kσ) -G(x, y,σ) ） * I (x, y) = L(x, y, kσ) -L(x, y,σ) 。（3）

其中，相鄰兩個(gè)尺度由一個(gè)常數(shù)k 分開。

選擇這個(gè)公式有兩個(gè)原因。一是這個(gè)公式的計(jì)算是省時(shí)的，因?yàn)橐枋龀叨瓤臻g中的特征點(diǎn)，就必須計(jì)算輸入圖像的尺度L，而這里計(jì)算D 時(shí)，僅需要計(jì)算相鄰尺度函數(shù)的差值。另外一個(gè)原因是函數(shù)D 的性質(zhì)與尺度歸一化的拉普拉斯高斯函數(shù)——即σ²?²G 很相近[8]。而Mikolajczyk 在實(shí)驗(yàn)中表明σ ²?²G的極大值和極小值能夠產(chǎn)生比其他函數(shù)（包括梯度，Hessian，Harris 角點(diǎn)函數(shù)）更加穩(wěn)定的特征。D 和σ²?²G 的關(guān)系可由以下公式說(shuō)

該公式是熱擴(kuò)散公式的另一種表示形式，公式左邊的項(xiàng)可以用近似的方法計(jì)算：

所以可得：

從公式可以看出，D 和σ²?²G 的形式是類似的。由于拉普拉斯函數(shù)是尺度無(wú)關(guān)的，因而高斯差分函數(shù)也是尺度無(wú)關(guān)的。對(duì)于所有尺度而言，k 都是一個(gè)常數(shù)，所以使用D 不會(huì)影響極值的選取。當(dāng)k 趨向于1 的時(shí)候，誤差會(huì)越來(lái)越小。但是實(shí)驗(yàn)表明，即使k 值不接近1（例如k 取 2 ），對(duì)極值的選取也沒(méi)有多大影響。

3.2.1計(jì)算高斯差分圖像

前面已經(jīng)論述，為了求尺度無(wú)關(guān)的特征點(diǎn)，首先需要計(jì)算相鄰尺度圖像的差分，得到一系列圖像并在該圖像空間中求極值點(diǎn)。采用金字塔可以高效的計(jì)算高斯差分圖像，如圖5 所示：[c1] 

金子塔自下而上分為多層，在第一層中，對(duì)原始圖像不斷用高斯函數(shù)卷積，得到一系列逐漸平滑的圖像。在這一層中，相鄰的高斯圖像差分得到高斯差分圖像。這一組進(jìn)行完畢后，從中抽取一幅圖像A 進(jìn)行降采樣，得到圖像B 的面積變?yōu)锳 的1/4 ，并將B 作為下一層的初始圖像，重復(fù)第一層的過(guò)程。選取A 的原則是，得到A 所用的尺度空間參數(shù)σ為初始尺度空間參數(shù)的2 倍。設(shè)k = 2^{1/ s} ，在s 個(gè)尺度中尋找極值點(diǎn)，則每層要有s+3 幅圖像，生成s+2 幅高斯差分圖像。

經(jīng)驗(yàn)值分別為3 和1.6* 2^1/3(*為乘號(hào))。也就是說(shuō)，k 取2^1/3 。

構(gòu)造D(x,y,e)的詳細(xì)步驟：

 1、首先采用不同尺度因子的高斯核對(duì)圖像進(jìn)行卷積以得到圖像的不同尺度空間，將這一組圖像作為金子塔圖像的第一層。

 2、接著對(duì)第一層圖像中的2倍尺度圖像（相對(duì)于該層第一幅圖像的2倍尺度）以2倍像素距離進(jìn)行下采樣來(lái)得到金子塔圖像的第二層中的第一幅圖像，對(duì)該圖像采用不同尺度因子的高斯核進(jìn)行卷積，以獲得金字塔圖像中第二層的一組圖像。

 3、再以金字塔圖像中第二層中的2倍尺度圖像（相對(duì)于該層第一幅圖像的2倍尺度）以2倍像素距離進(jìn)行下采樣來(lái)得到金字塔圖像的第三層中的第一幅圖像，對(duì)該圖像采用不同尺度因子的高斯核進(jìn)行卷積，以獲得金字塔圖像中第三層的一組圖像。這樣依次類推，從而獲得了金字塔圖像的每一層中的一組圖像。

4、對(duì)上圖得到的每一層相鄰的高斯圖像相減，就得到了高斯差分圖像。

5、因?yàn)楦咚共罘趾瘮?shù)是歸一化的高斯拉普拉斯函數(shù)的近似，所以可以從高斯差分金字塔分層結(jié)構(gòu)提取出圖像中的極值點(diǎn)作為候選的特征點(diǎn)。對(duì)DOG 尺度空間每個(gè)點(diǎn)與相鄰尺度和相鄰位置的點(diǎn)逐個(gè)進(jìn)行比較，得到的局部極值位置即為特征點(diǎn)所處的位置和對(duì)應(yīng)的尺度。

3.2.2計(jì)算極值點(diǎn)

上一步中已經(jīng)生成了高斯差分圖像，這一步中要計(jì)算該空間中的極值點(diǎn)。 為了尋找尺度空間的極值點(diǎn)，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。如下圖，圖3所示，中間的檢測(cè)點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的9×2個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。

有一個(gè)問(wèn)題是到底要在多少個(gè)尺度中尋找極值點(diǎn)，即如何確定s 值。實(shí)驗(yàn)表明，s 取3 是較好的選擇。如果s = 3，則需要5 幅高斯差分圖像才可以。這里的計(jì)算是高效的，因?yàn)榇蠖鄶?shù)情況下，只需要幾步比較，就可以排除一個(gè)像素點(diǎn)，認(rèn)為它不是極值。

當(dāng)然這樣產(chǎn)生的極值點(diǎn)并不都是穩(wěn)定的特征點(diǎn)，因?yàn)槟承O值點(diǎn)響應(yīng)較弱，而且DOG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng)。

3.3 抽取穩(wěn)定的關(guān)鍵點(diǎn)

上一步已經(jīng)求出了極值點(diǎn)，現(xiàn)在要對(duì)這些極值點(diǎn)進(jìn)行篩選，去除不穩(wěn)定的點(diǎn)，以增強(qiáng)特征

不穩(wěn)定的點(diǎn)包括低對(duì)比度的點(diǎn)和邊緣上的點(diǎn)。 點(diǎn)匹配時(shí)的穩(wěn)定性、提高抗噪聲能力。同時(shí)，由于在金子塔中存在降采樣的圖像，在這些圖像中提取的極值點(diǎn)在原始輸入圖像中到底在什么位置，也是一個(gè)問(wèn)題。下面將提出上面兩個(gè)問(wèn)題的解決方案。

對(duì)于某一個(gè)尺度上求取的極值點(diǎn)，采用一個(gè)3 維的2 次函數(shù)求該極值點(diǎn)在原圖像上的位置，并去除低對(duì)比度的極值點(diǎn)。首先在某極值點(diǎn)A 對(duì)D(x, y,σ) 進(jìn)行泰勒展開：

其中，X =(x, y,σ)^T 是到點(diǎn)A 的偏移量。對(duì)（4）式求X 的偏導(dǎo)數(shù)，并令偏導(dǎo)為零，得到

如果x⁾ 大于0.5 ，也就意味著這個(gè)極值點(diǎn)和另一個(gè)采樣點(diǎn)（圖像中的另一個(gè)像素）離得更近。采用插值法求得極值點(diǎn)位置的估計(jì)值。

同時(shí)，可以利用D(x⁾) 去除低對(duì)比度的點(diǎn)。將公式（5）帶入公式（4）得

通過(guò)觀察實(shí)驗(yàn)結(jié)果得出，D(x⁾) 絕對(duì)值小于0.03 的極值點(diǎn)都將被丟棄。為了得到穩(wěn)定的極值點(diǎn)，還要去除邊緣的影響，因?yàn)檫吘壣系臉O值點(diǎn)抗噪性較差。曲面上每個(gè)點(diǎn)（非平點(diǎn)）都有兩個(gè)主方向，并且沿這兩個(gè)主方向的法曲率（即兩個(gè)主曲率）分別是曲面在該點(diǎn)法曲率的最大值和最小值。在邊緣上的極值點(diǎn)，垂直于邊緣的方向上，法曲率最大，沿邊緣的方向上，法曲率最小。如果極值點(diǎn)分布在邊緣上，該點(diǎn)的法曲率最大值和最小值之比（即兩個(gè)主曲率之比），一般情況下要比非邊緣點(diǎn)的比值大。根據(jù)這種思想，我們可以設(shè)一個(gè)比值的閾值，當(dāng)比值大于這個(gè)閾值就認(rèn)為極值點(diǎn)在邊緣上。可以采用近似的方法來(lái)求主曲率的比值。首先計(jì)算待測(cè)極值點(diǎn)的海瑟矩陣：

其中微分可以通過(guò)計(jì)算鄰近點(diǎn)的差值來(lái)近似計(jì)算。H 的特征值和D 的主曲率對(duì)應(yīng)成比例，這里

我們只需要計(jì)算H 的較大特征值與較小特征值的比例即可。設(shè)α是較大的特征值，β是較小的特征值，由矩陣性質(zhì)知：

其中用到了矩陣的跡和行列式。通常這里的行列式不會(huì)是負(fù)值，如果出現(xiàn)負(fù)值的情況，即兩個(gè)主曲率不同號(hào)，我們將丟棄這個(gè)點(diǎn)，不將其視為極值點(diǎn)。設(shè)r=α/ β，我們可得：

當(dāng)r≥1，(r +1)² / r 是r 的單調(diào)遞增函數(shù)，所以要計(jì)算主曲率的比值（即r）是否在某閾值之下，只需要判斷上式左邊的項(xiàng)是否在閾值之下即可。實(shí)驗(yàn)表明，閾值通常選擇r = 10。

3.4 為關(guān)鍵點(diǎn)指定方向

SIFT特征的一個(gè)關(guān)鍵的特性是旋轉(zhuǎn)不變性，實(shí)現(xiàn)旋轉(zhuǎn)不變的基本思想是采用“相對(duì)”的概念。為關(guān)鍵點(diǎn)賦一個(gè)方向，定義的關(guān)鍵點(diǎn)描述子是相對(duì)于這個(gè)方向的，因而可以實(shí)現(xiàn)匹配時(shí)圖像的旋轉(zhuǎn)無(wú)關(guān)性。

， 為了實(shí)現(xiàn)尺度無(wú)關(guān)根據(jù)關(guān)鍵點(diǎn)所在的尺度選擇與該尺度最相近的高斯平滑圖像L。對(duì)于L 上的每個(gè)點(diǎn)L(x, y) ，計(jì)算梯度和方向

以關(guān)鍵點(diǎn)為中心，劃定一個(gè)鄰域，利用所有在此區(qū)域內(nèi)的點(diǎn)的梯度形成一個(gè)方向直方圖。直方圖的橫坐標(biāo)是梯度方向，共36 項(xiàng)，每項(xiàng)代表了10 度的范圍；縱坐標(biāo)是梯度大小，對(duì)于歸到橫坐標(biāo)上任一項(xiàng)內(nèi)所有的點(diǎn)，將其梯度大小相加，其和作為縱坐標(biāo)。如圖8 所示：

圖8. 方向直方圖從直方圖中選出縱坐標(biāo)值最大的一項(xiàng)的方向作為該關(guān)鍵點(diǎn)的主方向。如果存在其他方向，縱坐標(biāo)的大小大于主方向縱坐標(biāo)大小的80%，也將其作為該關(guān)鍵點(diǎn)的方向。特征點(diǎn)有多個(gè)方向的情況下，實(shí)際上是在此位置上有多個(gè)關(guān)鍵點(diǎn)，他們的方向不同。另外，為了獲得更好的穩(wěn)定性，可以對(duì)關(guān)鍵點(diǎn)鄰域的梯度大小進(jìn)行高斯加權(quán)。有方法改進(jìn)了采用直方圖指定方向的方式，改用PCA 求關(guān)鍵點(diǎn)的主方向。

3.5 局部描述子

前面已經(jīng)為關(guān)鍵點(diǎn)賦予了圖像位置、尺度以及方向，這一步將根據(jù)關(guān)鍵點(diǎn)周圍的局部特性計(jì)算一個(gè)特征描述子。這個(gè)描述子還需要對(duì)仿射變換、光照變換等具有一定的魯棒性。如圖9 所示，在關(guān)鍵點(diǎn)周圍取一個(gè)鄰域，并對(duì)其中點(diǎn)的梯度做高斯加權(quán)。這個(gè)鄰域分為四個(gè)子區(qū)域，每個(gè)子區(qū)域取八個(gè)方向，生成圖8 所示的相同形式的直方圖。

這是SIFT算法的最后一步，現(xiàn)在我們已經(jīng)得到了擁有尺度不變性和旋轉(zhuǎn)不變性的特征點(diǎn)，接下來(lái)要為每個(gè)特征點(diǎn)創(chuàng)建一個(gè)唯一標(biāo)識(shí)它的“指紋”，SIFT算法作者將它稱為SIFT描述子(descriptor)。所生成的SIFT描述子既要能讓相同場(chǎng)景中圖像的特征點(diǎn)能夠正確匹配，而且還要讓不同場(chǎng)景中圖像的特征點(diǎn)能夠正確區(qū)分。

為了得到這樣的SIFT描述子，我們將特征點(diǎn)周圍16*16的窗口分解為16個(gè)4*4的子窗口，圖2.12顯示了分解的過(guò)程。在每個(gè)4*4的子窗口中，計(jì)算出梯度的大小和方向，并用一個(gè)8個(gè)bin的直方圖來(lái)統(tǒng)計(jì)子窗口的平均方向，如圖2.13所示。

圖2.12將特征點(diǎn)周圍16*16的窗口分解為16個(gè)4*4的子窗口

圖2.13每個(gè)子窗口創(chuàng)建一個(gè)8bin的直方圖

梯度方向在0-44度范圍的像素點(diǎn)被放到第一個(gè)bin中，45-89度范圍的像素點(diǎn)被放到下一個(gè)bin中，依此類推。同樣加入到bin中的量依賴于該像素點(diǎn)梯度的大小。與之前不同的是，加入的量不僅與像素點(diǎn)的梯度大小相關(guān)，而且還依賴離特征點(diǎn)的距離，這樣遠(yuǎn)離特征點(diǎn)的像素點(diǎn)會(huì)加入較少的量到直方圖中。這通過(guò)一個(gè)高斯加權(quán)函數(shù)來(lái)實(shí)現(xiàn)，這個(gè)函數(shù)生成一個(gè)加權(quán)值（像一個(gè)二維的鐘形曲線），用它乘以16*16的窗口中每個(gè)像素點(diǎn)的梯度大小，得到加權(quán)后的梯度大小，距離特征點(diǎn)越遠(yuǎn)，要加入直方圖的像素點(diǎn)的梯度大小越小。

這樣每個(gè)4*4的子窗口都對(duì)應(yīng)一個(gè)8bin的直方圖，且直方圖中加入的值是像素的用高斯加權(quán)后的梯度大小，而特征點(diǎn)周圍16*16的窗口中包含16個(gè)4*4的子窗口，共有16*8=128個(gè)數(shù)，然后將這128個(gè)數(shù)組成的向量進(jìn)行單位化，單位化后的128維向量就是SIFT的描述子。

實(shí)現(xiàn)細(xì)節(jié)

在最后得到SIFT描述子前，我們還要處理兩個(gè)問(wèn)題：旋轉(zhuǎn)依賴和亮度依賴。

由于SIFT描述子中包含梯度方向信息，如果我們旋轉(zhuǎn)圖像，那么所有的梯度方向都會(huì)改變。為了實(shí)現(xiàn)旋轉(zhuǎn)不變性，要使用2.5中計(jì)算出的特征點(diǎn)方向，在使用每個(gè)4*4子窗口中像素的梯度方向時(shí)，要先減去特征點(diǎn)方向。

由于某些圖像亮度變化較大，這可能會(huì)導(dǎo)致特征點(diǎn)周圍像素的梯度大小變化過(guò)大，也就是說(shuō)在單位化后的SIFT描述子中某些維度的量要遠(yuǎn)大于其它維度的量。為了減少亮度的依賴，我們將128維SIFT描述子中大于0.2的維度量截取為0.2，并對(duì)最后的128為描述子再做一次單位化。

通過(guò)這系列操作，我們最后得到了具有位置穩(wěn)定、尺度不變性、旋轉(zhuǎn)不變性和較少亮度依賴的SIFT描述子。

謝謝諸位