sift算法解析

　　SIFT綜述

　　尺度不變特征轉(zhuǎn)換（Scale-invariant feature transform或SIFT）是一種電腦視覺(jué)的算法用來(lái)偵測(cè)與描述影像中的局部性特征，它在空間尺度中尋找極值點(diǎn)，并提取出其位置、尺度、旋轉(zhuǎn)不變量，此算法由 David Lowe在1999年所發(fā)表，2004年完善總結(jié)。

　　其應(yīng)用范圍包含物體辨識(shí)、機(jī)器人地圖感知與導(dǎo)航、影像縫合、3D模型建立、手勢(shì)辨識(shí)、影像追蹤和動(dòng)作比對(duì)。

　　此算法有其專(zhuān)利，專(zhuān)利擁有者為英屬哥倫比亞大學(xué)。

　　局部影像特征的描述與偵測(cè)可以幫助辨識(shí)物體，SIFT 特征是基于物體上的一些局部外觀的興趣點(diǎn)而與影像的大小和旋轉(zhuǎn)無(wú)關(guān)。對(duì)于光線、噪聲、些微視角改變的容忍度也相當(dāng)高。基于這些特性，它們是高度顯著而且相對(duì)容易擷取，在母數(shù)龐大的特征數(shù)據(jù)庫(kù)中，很容易辨識(shí)物體而且鮮有誤認(rèn)。使用 SIFT特征描述對(duì)于部分物體遮蔽的偵測(cè)率也相當(dāng)高，甚至只需要3個(gè)以上的SIFT物體特征就足以計(jì)算出位置與方位。在現(xiàn)今的電腦硬件速度下和小型的特征數(shù)據(jù)庫(kù)條件下，辨識(shí)速度可接近即時(shí)運(yùn)算。SIFT特征的信息量大，適合在海量數(shù)據(jù)庫(kù)中快速準(zhǔn)確匹配。

　　SIFT算法的特點(diǎn)有：

　　1、SIFT特征是圖像的局部特征，其對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性；

　　2、獨(dú)特性（Distinctiveness）好，信息量豐富，適用于在海量特征數(shù)據(jù)庫(kù)中進(jìn)行快速、準(zhǔn)確的匹配；

　　3、 多量性，即使少數(shù)的幾個(gè)物體也可以產(chǎn)生大量的SIFT特征向量；

　　4、 高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達(dá)到實(shí)時(shí)的要求；

　　5、可擴(kuò)展性，可以很方便的與其他形式的特征向量進(jìn)行聯(lián)合。

　　SIFT算法可以解決的問(wèn)題：

　　目標(biāo)的自身狀態(tài)、場(chǎng)景所處的環(huán)境和成像器材的成像特性等因素影響圖像配準(zhǔn)/目標(biāo)識(shí)別跟蹤的性能。而SIFT算法在一定程度上可解決：

　　1、目標(biāo)的旋轉(zhuǎn)、縮放、平移（RST）

　　2、圖像仿射/投影變換（視點(diǎn)viewpoint）

　　3、光照影響（illumination）

　　4、目標(biāo)遮擋（occlusion）

　　5、雜物場(chǎng)景（clutter）

　　6、噪聲

　　SIFT算法的實(shí)質(zhì)是在不同的尺度空間上查找關(guān)鍵點(diǎn)（特征點(diǎn)），并計(jì)算出關(guān)鍵點(diǎn)的方向。SIFT所查找到的關(guān)鍵點(diǎn)是一些十分突出，不會(huì)因光照，仿射變換和噪音等因素而變化的點(diǎn)，如角點(diǎn)、邊緣點(diǎn)、暗區(qū)的亮點(diǎn)及亮區(qū)的暗點(diǎn)等。

　　SIFT的缺點(diǎn)

　　SIFT在圖像的不變特征提取方面擁有無(wú)與倫比的優(yōu)勢(shì)，但并不完美，仍然存在：

　　1、實(shí)時(shí)性不高。

　　2、有時(shí)特征點(diǎn)較少。

　　3、對(duì)邊緣光滑的目標(biāo)無(wú)法準(zhǔn)確提取特征點(diǎn)。

　　sift算法matlab代碼的實(shí)現(xiàn)

　　1、構(gòu)建尺度空間

　　定理1 對(duì)圖像做 σ=σ1 的高斯平滑，再做一次 σ=σ2 的高斯平滑，等效于對(duì)原圖像做一次的高斯平滑。

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

　　高斯卷積核是實(shí)現(xiàn)尺度變換的唯一線性核（Koenderink， 1984; Lindeberg， 1994）。

　　一幅圖像的尺度空間被定義為對(duì)其做可變尺度的高斯卷積：

　　對(duì)于給定的彩色圖像，轉(zhuǎn)化為灰度圖像，用不同大小的σ做高斯平滑（按照 3σ 準(zhǔn)則，高斯核矩陣的大小設(shè)為 （6σ+1）?（6σ+1） ，并保證行和列為奇數(shù)），再此基礎(chǔ)上將圖像降采樣得到不同大小的組（octave），每組若干圖像（interval）。詳細(xì)描述如下：

　　為了得到更多的特征點(diǎn)，將圖像擴(kuò)大為原來(lái)的兩倍。假設(shè)原圖像已有 σ=0.5 的高斯平滑，而我們需要第一個(gè)octave的第一張圖像的 σ=1.6 ，按照定理1，我們要對(duì)擴(kuò)大兩倍的圖像做一次高斯平滑，。

　　上一個(gè)octave的圖像的長(zhǎng)度和寬度分別是下一個(gè)octave的圖像的兩倍。因此圖像組數(shù)（octaves）可由圖像大小決定，將其設(shè)為 log2（min（height，width）） ? 2 ，這樣將使頂層octave圖像的長(zhǎng)度和寬度最小值在8像素左右。

　　設(shè)第m個(gè)octave的第n張圖像相對(duì)于原始圖像的參數(shù)σ為 sigma（m，n），則sigma（1，1）=σ0=1.6。每個(gè)octave有s+1張圖像（即intervals），這樣得到的高斯差分金字塔（DoG）每個(gè)octave將有s張圖像，我們?cè)O(shè)s為3。為了滿足在不同octave間尺度的連續(xù)性，并使 sigma（m，n）= 2?sigma（m?1，n），按照定理1，則：

　　如上圖所示，在第一個(gè)octave中尺度為k3?σ0的“最后”一張圖像進(jìn)行下采樣得到第二個(gè)octave的第一張圖像，尺度仍為k3?σ0=2?σ0。

　　但實(shí)際上我們需要做出更多不同尺度的高斯平滑圖像，這是因?yàn)樵诤罄m(xù)高斯差分金字塔的極值檢測(cè)中，需要前后兩級(jí)尺度都存在圖像。如圖中紅框所示，高斯差分金字塔中每個(gè)octave有s幅圖像，則需要高斯金字塔中每個(gè)octave包含s+3幅圖像。其中第s+1幅圖像用作下一個(gè)octave第一幅圖像的降采樣。

　　具體實(shí)現(xiàn)中并未對(duì)單幅圖像多次進(jìn)行高斯平滑，而是由上一幅圖像進(jìn)行高斯平滑得到下一幅圖像并迭代之，按照定理1計(jì)算σ。

　　1.2 構(gòu)建高斯差分金字塔

　　對(duì)兩幅高斯金字塔的圖像作差。

　　1.3 檢測(cè)極值點(diǎn)

　　如上圖，與前后兩幅圖像及自身的共26個(gè)鄰域像素點(diǎn)比較灰度值檢測(cè)極值。

　　2、關(guān)鍵點(diǎn)精確定位

　　檢測(cè)到的極值點(diǎn)是離散的，通過(guò)三元二次函數(shù)擬合來(lái)精確確定關(guān)鍵點(diǎn)的位置和尺度，達(dá)到亞像素精度。以某關(guān)鍵點(diǎn)為中心的尺度空間函數(shù) D（x，y，intvl） 的二次泰勒展開(kāi)式為：

　　其中等號(hào)右邊第一個(gè)D為某關(guān)鍵點(diǎn)處的灰度值， X=（x，y，intvl）T 是以此點(diǎn)為中心的偏移量，由于 D（X） 是離散的，其導(dǎo)數(shù)用差分法求得。令 D（X） 導(dǎo)數(shù)為零，得到精確極值位置的偏移量為：

　　在任意一個(gè)維度大于0.5，說(shuō)明極值點(diǎn)精確位置距離另一個(gè)點(diǎn)更近，應(yīng)該將關(guān)鍵點(diǎn)定位于更近的那個(gè)位置。定位到新點(diǎn)后再進(jìn)行相同操作，若迭代5次位置仍不收斂，則不認(rèn)為此點(diǎn)為關(guān)鍵點(diǎn)。設(shè)定圖像邊緣img_border，若關(guān)鍵點(diǎn)落在圖像邊緣區(qū)域（以img_border為寬度的矩形外框）也不認(rèn)為此點(diǎn)為關(guān)鍵點(diǎn)。

　　2.1 去除低反差（low contrast）的點(diǎn)精確極值點(diǎn)處函數(shù)值：

　　同樣不認(rèn)為此點(diǎn)是極值點(diǎn)。在此過(guò)程中保存極值點(diǎn)的數(shù)據(jù)ddata，為特征的構(gòu)建做準(zhǔn)備。計(jì)算出σ_octv，即位于一個(gè)相同的octave內(nèi)的尺度，某個(gè)octave內(nèi)第n張圖像的 σ_octv=σ0?kintvl?1 ，此處intvl為精確定位后的intvl。

　　2.2 消除邊緣響應(yīng)

　　高斯差分函數(shù)有較強(qiáng)的邊緣響應(yīng)，對(duì)于比較像邊緣的點(diǎn)應(yīng)該去除掉。這樣的點(diǎn)的特征為在某個(gè)方向有較大主曲率，而在垂直的方向主曲率很小。

　　設(shè)r為大主曲率與小主曲率的比值，H為關(guān)鍵點(diǎn)處的Hessian矩陣，則有（具體推導(dǎo)可見(jiàn)Lowe的論文）：

　　其中rt為一閾值，設(shè)為10說(shuō)明此處r較小，認(rèn)為此關(guān)鍵點(diǎn)不位于邊緣，否則則去除該點(diǎn)。

　　3、方向指定

　　根據(jù)關(guān)鍵點(diǎn)的局部特性為每個(gè)關(guān)鍵點(diǎn)指定一個(gè)方向，可以具備旋轉(zhuǎn)不變性。關(guān)鍵點(diǎn)局部特性在檢測(cè)到關(guān)鍵點(diǎn)的高斯差分金字塔圖像臨近的高斯金字塔圖像中計(jì)算。在關(guān)鍵點(diǎn)3σ鄰域窗口計(jì)算梯度和方向分布，計(jì)算方式如下：

　　此處的x正方向向右，y正方向向上。其中L為關(guān)鍵點(diǎn)在上述精確定位后所處尺度的灰度值，m（x，y）為梯度的幅值，θ（x，y）為關(guān)鍵點(diǎn)處梯度方向的弧度（范圍為（?π，π］）。將360度的方向劃分為36個(gè)區(qū)域（bins），第一個(gè)區(qū)域的范圍是［35π36，37π36），按逆時(shí)針?lè)较蛞来蝿澐?。?duì)m（x，y）按 σ=1.5σ_octv 的高斯分布，在 3σ=3?1.5σ_octv 的鄰域窗口加權(quán)計(jì)算，得到36個(gè)方向的直方圖。然后對(duì)直方圖進(jìn)行兩次平滑處理，即按0.25，0.5，0.25的大小對(duì)每3個(gè)連續(xù)的bin加權(quán)兩次。

　　直方圖最大值的方向代表該關(guān)鍵點(diǎn)的主方向，對(duì)于其他峰值，若大于或等于主方向值的80%，則再分配一個(gè)方向。所以對(duì)于一個(gè)關(guān)鍵點(diǎn)，可能會(huì)有多個(gè)對(duì)應(yīng)的方向，將帶有方向的關(guān)鍵點(diǎn)定義為feature，則一個(gè)關(guān)鍵點(diǎn)可能對(duì)應(yīng)多個(gè)feature。由于第一個(gè)octave是雙倍大小的圖像，feature的坐標(biāo)和尺度應(yīng)轉(zhuǎn)換到原始圖像所在的octave處理。最后用拋物插值精確定位feature的方向。

　　對(duì)于x為-1，0，1，y為l，c，r的三個(gè)點(diǎn)來(lái)說(shuō)，拋物插值得到極值點(diǎn)的x為：

　　上一步已得到具有主方向的關(guān)鍵點(diǎn)，即feature，下一步是對(duì)feature的鄰域進(jìn)行采樣，形成對(duì)該局部圖像的描述，然后可用某種度量方法對(duì)描述進(jìn)行匹配。

　　Lowe提出的sift描述子是一個(gè) 4×4×8=128 維的向量。描述子的數(shù)學(xué)形式可定義為 h（x，y，θ） ，其中的x，y代表 4×4=16 個(gè)圖像區(qū)域的位置，θ即梯度方向，只能取8個(gè)值。h（x，y，θ）的值就是在（x，y）代表的圖像區(qū)域計(jì)算得到的在θ方向的梯度大小。

　　4.1、描述子采樣區(qū)域

　　這16個(gè)圖像區(qū)域中的每一個(gè)區(qū)域均為 3σ_octv 像素，因此16個(gè)區(qū)域的半邊長(zhǎng)為 4×3σ_octv/2 ，考慮到后續(xù)操作需要三線性插值，采樣區(qū)域半邊長(zhǎng)設(shè)為 （4+1）×3σ_octv/2 ，又由于旋轉(zhuǎn)操作，這個(gè)值需要乘以2√，得到 radius=（4+1）× 2√×3σ_octv/2 。

　　如下圖所示，圖中 m=3， Bp=4，σ=σ_octv 。

　　4.2、旋轉(zhuǎn)至主方向

　　為了使描述符具有旋轉(zhuǎn)不變性，將坐標(biāo)軸旋轉(zhuǎn)至關(guān)鍵點(diǎn)主方向。設(shè)i，j分別為采樣點(diǎn)相對(duì)關(guān)鍵點(diǎn)的行偏移量和列偏移量，i = -radius:radius，j = -radius:radius，關(guān)鍵點(diǎn)左上角i和j均為負(fù)數(shù)。關(guān)鍵點(diǎn)主方向?yàn)棣?，范圍是?π，π］。

　　定理2 在右手平面直角坐標(biāo)系中，向量（x，y）逆時(shí)針旋轉(zhuǎn)θ，得到的向量（x’，y’）為：

　　在左圖以關(guān)鍵點(diǎn)為中心建立右手平面直角坐標(biāo)系o-uv，u的正方向與左圖x方向相同，v的正方向與左圖y方向相反。左圖中x=（1，0），y=（0，-1），將x，y代入定理2的公式，得到右圖中 x′=（cosθ，sinθ）， y′=（sinθ，?cosθ） 。其中θ為左圖坐標(biāo)系旋轉(zhuǎn)到右圖坐標(biāo)系的角度，在上圖中為一負(fù)數(shù)。設(shè)圖像中有一點(diǎn)按左圖的x，y可表示為 j?x+i?y ，按右圖中的x′，y′可表示為 j′?x′+i′?y′ ，則有：

　　得到新的行、列偏移量后，將 3σ_octv 設(shè)為單位長(zhǎng)度，并將中心轉(zhuǎn)移至最左上角區(qū)域中心，得到新的坐標(biāo)r_bin和c_bin。對(duì)梯度方向弧度值減去主方向弧度，并設(shè) 2π8 為一個(gè)單位，得到o_bin。

　　采樣點(diǎn)的梯度幅值按照 σ=0.5?4?3σ_octv （即16個(gè)區(qū)域邊長(zhǎng)的一半）的高斯函數(shù)加權(quán)：

　　其中a，b為關(guān)鍵點(diǎn)在高斯金字塔圖像中的位置坐標(biāo)。

　　4.3、三線性插值

　　上述過(guò)程中構(gòu)造了一個(gè)三維的bin空間，如4.1中右圖所示，維度包括r_bin，c_bin和o_bin。注意最上層格子和最底層格子是相連的，因?yàn)?度等于360度。所有帶有三維坐標(biāo)的梯度幅值都將分配到三維格子里。

　　為了減少一個(gè)梯度幅值從一個(gè)格子漂移（shift）到另一個(gè)格子引起的描述子突變，需要對(duì)梯度值做三線性插值。也就是根據(jù)三維坐標(biāo)計(jì)算距離周?chē)褡拥木嚯x，按距離的倒數(shù)計(jì)算權(quán)重，將梯度幅值按權(quán)重分配到臨近的格子里。

　　某點(diǎn)在三維bin空間的坐標(biāo)為（r_bin，c_bin，o_bin），求出r=?r_bin?， c=?c_bin?， o=?o_bin?， dr=r_bin?r， dc=c_bin?c， do=o_bin?o，它的梯度幅值最多可能分配到周?chē)?個(gè)格子中。計(jì)算公式如下：

　　1?k其中i，j，k均可取0或1，weightedValue下標(biāo)加1的目的是使下標(biāo)從1開(kāi)始。

　　為簡(jiǎn)化計(jì)算，可改為：

　　4.4、生成描述子

　　將上述直方圖數(shù)組按順序排列可轉(zhuǎn)換為一個(gè)128維的向量。

　　為了減少光照變化的影響，對(duì)該向量進(jìn)行歸一化處理。非線性光照變化仍可能導(dǎo)致梯度幅值的較大變化，然而影響梯度方向的可能性較小。因此對(duì)于超過(guò)閾值0.2的梯度幅值設(shè)為0.2，然后再進(jìn)行一次歸一化。最后將描述子按照對(duì)應(yīng)高斯金字塔圖像的尺度大小排序。

　　5、匹配

　　描述子向量已經(jīng)歸一化，所以可直接用向量之間的夾角進(jìn)行匹配，相當(dāng)于球面距離。圖像A 的描述子匹配圖像B最近的兩個(gè)描述子點(diǎn)積之比小于0.6，則認(rèn)為匹配成功。

? ? ? 6、總結(jié)

　　6.1、性能優(yōu)化

　　因?yàn)橛玫氖荕atlab，所以不注重性能。然而又不得不注重性能，因?yàn)榈谝淮闻芡ǔ绦虻臅r(shí)候跑了一晚上都沒(méi)跑完一半！也就是一張圖片的描述子都沒(méi)算完。后來(lái)發(fā)現(xiàn)是因?yàn)樵谶\(yùn)行次數(shù)最多的for循環(huán)（描述子計(jì)算中的梯度計(jì)算）里用到了cell數(shù)組。把對(duì)這個(gè)cell數(shù)組的查詢操作提到兩重循環(huán)前以后，這個(gè)程序好像跑了半個(gè)小時(shí)左右跑出結(jié)果了。然而還是太慢，于是我又用Matlab的計(jì)時(shí)分析工具分析了程序最耗時(shí)的地方：

　　1）把cell數(shù)組的查詢盡可能減少

　　2）充分利用Matlab的向量操作

　　3）一些沒(méi)用的參數(shù)給去掉了（如計(jì)算梯度時(shí)的三個(gè)返回值合并到了一個(gè)二維數(shù)組）

　　4）一個(gè)三維數(shù)組折疊成了一維的（hist）

　　程序里用了很多全局變量，是因?yàn)槲野押瘮?shù)分成了文件而不是放在一個(gè)文件，為了節(jié)省點(diǎn)內(nèi)存（以及方便）只能這么做（雖然據(jù)說(shuō)Matlab在不改變變量的情況下函數(shù)傳值等于引用，然而我并不清楚究竟是怎樣的）。把for循環(huán)換成parfor的時(shí)候提示，parfor里似乎不推薦用全局變量，而且實(shí)際運(yùn)行的時(shí)候全局變量似乎也會(huì)影響性能，于是我把全局變量復(fù)制成了局部的再放進(jìn)parfor里。

　　我還發(fā)現(xiàn)一個(gè)奇葩的問(wèn)題，在運(yùn)行次數(shù)最多的計(jì)算梯度的函數(shù)里用zeros（1，2）創(chuàng)建一個(gè)數(shù)組竟然也耗時(shí)非常多，改成［0 0］就好了。

　　經(jīng)過(guò)這些修改后，在開(kāi)啟parallel pool的情況下運(yùn)行時(shí)間縮短到了7分鐘左右。（然而Lowe的C語(yǔ)言版本只要十幾秒

　　6.2 運(yùn)行結(jié)果

　　這次作業(yè)老師給的是兩張768x1024的圖片，分別檢測(cè)到5288和4798個(gè)特征點(diǎn)，最后匹配了906對(duì)點(diǎn)。用Lowe的siftDemoV4跑出來(lái)的結(jié)果是1252對(duì)匹配。

　　這個(gè)程序的參數(shù)基本都是參照opensift，但最后的匹配用的是Lowe的方案。Lowe的實(shí)現(xiàn)畢竟不太一樣，運(yùn)行的結(jié)果和opensift有一些差異。以下是匹配siftDemoV4.zip里的scene.pgm和book.pgm的結(jié)果：

　　sw-sift和opensift的區(qū)別主要是在高斯平滑和匹配算法上。opensift的高斯平滑用的是OpenCV的CVSmooth函數(shù)，匹配用的是歐式距離（而且把描述子乘以512從double類(lèi)型轉(zhuǎn)成了int）。和opensift相比，sw-sift檢測(cè)到的特征點(diǎn)數(shù)量很接近，但是匹配數(shù)量較少，所以可改進(jìn)的地方主要是匹配算法（然而我不想改了==）。另外，我發(fā)現(xiàn)高斯平滑的核矩陣大小對(duì)結(jié)果有很大影響，根據(jù)3σ準(zhǔn)則它的寬度應(yīng)該是 （6σ+1）?（6σ+1） ，然而有人設(shè)成 （3σ+1）?（3σ+1） 卻取得了更多特征點(diǎn)，因此調(diào)整這個(gè)參數(shù)再用其它參數(shù)限制錯(cuò)誤數(shù)量或許可以得到更好的結(jié)果。