计算机视觉：特征提取与匹配
目錄
1. 特征提取和匹配
1.1 背景知識
1.2 特征匹配基本流程
1.3?局部特征描述子
2. Harris角點(diǎn)檢測?
2.1 角點(diǎn)（corner points）
2.2?HARRIS角點(diǎn)檢測基本思想
2.3?HARRIS檢測：數(shù)學(xué)表達(dá)
2.4 角點(diǎn)響應(yīng)函數(shù)
2.5 編程實(shí)現(xiàn)
2.5.1 角點(diǎn)檢測代碼實(shí)現(xiàn)?
2.5.2 角點(diǎn)檢測數(shù)據(jù)測試
3.??SIFT特征匹配算法
3.1 SIFT算法實(shí)現(xiàn)步驟
3.2?關(guān)鍵點(diǎn)檢測的相關(guān)概念
3.2.1 關(guān)鍵點(diǎn)（特征點(diǎn)）
3.2.2 尺度空間
3.2.3 高斯模糊
3.2.4?高斯金字塔
3.3?檢測尺度空間極值
3.3.1 DoG（Difference of Gaussian）函數(shù)
3.3.2 DoG高斯差分金字塔
3.3.3?DOG局部極值檢測
3.4 關(guān)鍵點(diǎn)的精確定位
3.4.1?特征點(diǎn)的精確定位
3.4.2?剔除不穩(wěn)定的邊緣響應(yīng)點(diǎn)
3.5?關(guān)鍵點(diǎn)方向分配
3.6?關(guān)鍵點(diǎn)描述
3.7?關(guān)鍵點(diǎn)匹配
3.8 編程實(shí)現(xiàn)
3.8.1 檢測感興趣點(diǎn)
3.8.2 兩張圖像的SIFT特征匹配
3.8.3?地理標(biāo)記圖像匹配
3.8.4?實(shí)驗(yàn)過程中遇到的問題
1. 特征提取和匹配
1.1 背景知識
????????特征提取和匹配是許多計(jì)算機(jī)視覺應(yīng)用中的一個重要任務(wù)，廣泛運(yùn)用在運(yùn)動結(jié)構(gòu)、圖像檢索、目標(biāo)檢測等領(lǐng)域。 特征可能是圖像中的特定結(jié)構(gòu)，例如點(diǎn)，邊緣或?qū)ο蟆?/span>特征也可能是應(yīng)用于圖像的一般鄰域操作或特征檢測的結(jié)果。特征點(diǎn)匹配，是圖像拼接、三維重建、相機(jī)標(biāo)定等應(yīng)用的關(guān)鍵步驟。
????????關(guān)鍵點(diǎn)也稱興趣點(diǎn)，是紋理中表達(dá)的點(diǎn)。關(guān)鍵點(diǎn)往往是物體邊界方向突然改變的點(diǎn)或兩個或多個邊緣段之間的交點(diǎn)。它在圖像空間中具有明確的位置或很好地定位。即使圖像域的局部或全局存在如光照和亮度變化等的擾動，關(guān)鍵點(diǎn)仍然是穩(wěn)定，可以被重復(fù)可靠地計(jì)算出。除此之外它能夠提供有效的檢測。
1.2 特征匹配基本流程
- 根據(jù)特定準(zhǔn)則，提取圖像中的特征點(diǎn) ；
- 提取特征點(diǎn)周圍的圖像塊，構(gòu)造特征描述符；
- 通過特征描述符對比，實(shí)現(xiàn)特征匹配。
1.3?局部特征描述子
???特征點(diǎn)必須具有不變性，比如：
- 幾何不變性: 位移、旋轉(zhuǎn)、尺度，......
- 光度不變性: 光照、 曝光，......
? ?特征分類
- 角點(diǎn)。Harris算子，SUSAN算子, FAST算子。
- 梯度特征點(diǎn)。 SIFT、SURF、GLOH、ASIFT、PSIFT算子 等。 ? 邊緣特征（線型）。Canny算子, Marr算子。
- 紋理特征。灰度共生矩陣，小波Gabor算子。
- 快速特征匹配的基本策略：以圖像中穩(wěn)定角點(diǎn)的領(lǐng)域訓(xùn)練特 征分類器，為輸入圖像的特征分類。
2. Harris角點(diǎn)檢測?
????????Harris 角點(diǎn)檢測算法（也稱 Harris & Stephens 角點(diǎn)檢測器）是一個極為簡單的角點(diǎn)檢測算法。該算法的主要思想是，如果像素周圍顯示存在多于一個方向的邊，我們認(rèn)為該點(diǎn)為興趣點(diǎn)。該點(diǎn)就稱為角點(diǎn)。
2.1 角點(diǎn)（corner points）
- 局部窗口沿各方向移動，均產(chǎn)生明顯變化的點(diǎn)；
- 圖像局部曲率突變的點(diǎn)。
? ??
? ?好的角點(diǎn)檢測算法應(yīng)該具有的特點(diǎn)：
- 檢測出圖像中“真實(shí)的”角點(diǎn)
- 準(zhǔn)確的定位性能
- 很高的穩(wěn)定性
- 具有對噪聲的魯棒性
- 具有較高的計(jì)算效率
2.2?HARRIS角點(diǎn)檢測基本思想
????????算法基本思想是使用一個固定窗口在圖像上進(jìn)行任意方向上的滑動，比較滑動前與滑動后兩種情況，窗口中的像素灰度變化程度，如果存在任意方向上的滑動，都有著較大灰度變化，那么我們可以認(rèn)為該窗口中存在角點(diǎn)。
固定窗口在圖像上進(jìn)行任意方向上的滑動，有以下幾種情況：
平坦區(qū)域： 任意方向移動，無灰度變化。
平坦區(qū)域邊緣：沿著邊緣方向移動，無灰度變化 。
邊緣上移動角點(diǎn)：窗口向任意方向的移動都導(dǎo)致圖像灰度的明顯變化。
角點(diǎn)處移動2.3?HARRIS檢測：數(shù)學(xué)表達(dá)
將圖像窗口平移??產(chǎn)生灰度變化? 的數(shù)學(xué)表達(dá)式如下：
其中，為窗口函數(shù)，可用1表示在窗口內(nèi)部，用0表示在外面，或者用高斯拉普拉斯算子。
為灰度圖像，為平移后的圖像灰度。
延伸知識點(diǎn)：
一元函數(shù)泰勒展開：
?二元函數(shù)泰勒展開：
為了對求解方便，我們利用二元泰勒近似可將表達(dá)式簡化，將函數(shù)在處泰勒展開，得：
又我們可以將??表示為：
于是對于局部微小的移動量??，可以近似得到下面的表達(dá):
其中M是 2*2 矩陣，可由圖像的導(dǎo)數(shù)求得:
窗口移動導(dǎo)致的圖像變化量：實(shí)對稱矩陣M的特征值分析
對于，??，??記的特征值為?.
通過M的兩個特征值的大小對圖像點(diǎn)進(jìn)行分類:
- 平臺區(qū)域：如果 和 都很小，圖像窗口在所有方向上移動都無明顯灰度變化;
- 邊緣：如果?或?，圖像窗口在某一方向上移動有明顯灰度變化。
-
角點(diǎn)：如果 和 都較大且數(shù)值相當(dāng) ~ ，圖像窗口在所有方向上移動都產(chǎn)生明顯灰度變化;
?
2.4 角點(diǎn)響應(yīng)函數(shù)
????????在不需要實(shí)際計(jì)算特征值的情況下，為了把重要的情況和其他情況分開，Harris 和 Stephens 引入了指示函數(shù)。
定義：角點(diǎn)響應(yīng)函數(shù)R
?
?
?
? ? R 只與M的特征值有關(guān)
- 角點(diǎn)：R 為大數(shù)值正數(shù)
- 邊緣：R為大數(shù)值負(fù)數(shù)
- 平坦區(qū)：R為小數(shù)值
? ??
角點(diǎn)計(jì)算流程
- 對角點(diǎn)響應(yīng)函數(shù)R進(jìn)行閾值處理：R>threshold
- 提取R的局部最大值
- 為了消除參數(shù)k的影響，也可采用商來計(jì)算響應(yīng)：
2.5 編程實(shí)現(xiàn)
Harris角點(diǎn)檢測步驟
2.5.1 角點(diǎn)檢測代碼實(shí)現(xiàn)?
from PIL import Image from numpy import * from pylab import * from scipy.ndimage import filters# 在灰度圖像中，對每個像素計(jì)算Harris角點(diǎn)檢測器響應(yīng)函數(shù) def compute_harris_response(im, sigma=3):# 計(jì)算導(dǎo)數(shù): 先初始化矩陣imx = zeros(im.shape)imy = zeros(im.shape)# 高斯導(dǎo)數(shù): 3*3的高斯濾波filters.gaussian_filter(im, (sigma, sigma), (0, 1), imx)filters.gaussian_filter(im, (sigma, sigma), (1, 0), imy)# 計(jì)算 Harris 矩陣的分量Wxx = filters.gaussian_filter(imx * imx, sigma)Wxy = filters.gaussian_filter(imx * imy, sigma)Wyy = filters.gaussian_filter(imy * imy, sigma)# 計(jì)算特征值Wdet = Wxx * Wyy - Wxy ** 2Wtr = Wxx + Wyyreturn Wdet/Wtr # 從一幅Harris響應(yīng)圖像中返回角點(diǎn) def get_harris_points(harrisim, min_dist=10, threshold=0.1):# min_dist 為分割角點(diǎn)和圖像邊界的最少像素數(shù)目# 尋找高于閾值的候選角點(diǎn)corner_threshold = harrisim.max() * thresholdharrisim_t = (harrisim > corner_threshold) * 1# 得到候選點(diǎn)的坐標(biāo)coords = array(harrisim_t.nonzero()).T# 獲取候選點(diǎn)的 Harris 響應(yīng)值candidate_values = [harrisim[c[0], c[1]] for c in coords]# 對候選點(diǎn)按照 Harris 響應(yīng)值進(jìn)行排序index = argsort(candidate_values)# 將可行點(diǎn)的位置保存到數(shù)組中allowed_locations = zeros(harrisim.shape)allowed_locations[min_dist:-min_dist, min_dist:-min_dist] = 1# 按照 min_distance 原則，選擇最佳 Harris 點(diǎn)filtered_coords = []for i in index:if allowed_locations[coords[i, 0], coords[i, 1]] == 1:filtered_coords.append(coords[i])allowed_locations[(coords[i, 0] - min_dist):(coords[i, 0] + min_dist),(coords[i, 1] - min_dist): (coords[i, 1] + min_dist)] = 0return filtered_coords # 繪制圖像中檢測到的角點(diǎn) def plot_harris_points(image, filtered_coords):figure()gray()imshow(image)plot([p[1] for p in filtered_coords], [p[0] for p in filtered_coords], '*')axis('off')show()2.5.2 角點(diǎn)檢測數(shù)據(jù)測試
數(shù)據(jù)一：
數(shù)據(jù)二：
?數(shù)據(jù)三：
? 測試代碼示例：
if __name__ == '__main__':# 讀入圖像im = array(Image.open('Images/picture1.jpg').convert('L'))# 檢測Harris角點(diǎn)harrisim = compute_harris_response(im)# Harris響應(yīng)函數(shù)harrisim1 = 255 - harrisimfigure()gray()# 畫出Harris響應(yīng)圖subplot(221)title("harrisim")imshow(harrisim1)axis('off')axis('equal')# 設(shè)置多個閾值，比較實(shí)驗(yàn)結(jié)果threshold = [0.1, 0.2, 0.3]for i, thres in enumerate(threshold):filtered_coords = get_harris_points(harrisim, 6, thres)subplot(2, 2, i+2)title("threshold: "+str(threshold[i]))imshow(im)plot([p[1] for p in filtered_coords], [p[0] for p in filtered_coords], '*')axis('off')show()? 運(yùn)行結(jié)果：
? 數(shù)據(jù)一結(jié)果：?
??
? 數(shù)據(jù)二結(jié)果：
?數(shù)據(jù)三結(jié)果：
????????閾值增大，角點(diǎn)響應(yīng)值R減小，降低角點(diǎn)檢測的靈性，被檢測角點(diǎn)數(shù)量減少；閾值減小，角點(diǎn)響應(yīng)值R增大，增加角點(diǎn)檢測的靈敏性，被檢測角點(diǎn)的數(shù)量增加。
3.??SIFT特征匹配算法
????????David Lowe 提出的 SIFT（Scale-Invariant Feature Transform，尺度不變特征變換）是過去十年中最成功的圖像局部描述子之一。SIFT 特征后來得到精煉并詳述，經(jīng)受住了時間的考驗(yàn)。SIFT 特征包括興趣點(diǎn)檢測器和描述 子。SIFT 描述子具有非常強(qiáng)的穩(wěn)健性，這在很大程度上也是 SIFT 特征能夠成功和流行的主要原因。自從 SIFT 特征的出現(xiàn)，許多其他本質(zhì)上使用相同描述子的方法也相繼出現(xiàn)。現(xiàn)在，SIFT 描述符經(jīng)常和許多不同的興趣點(diǎn)檢測器相結(jié)合使用（有些 情況下是區(qū)域檢測器），有時甚至在整幅圖像上密集地使用。SIFT 特征對于尺度、旋轉(zhuǎn)和亮度都具有不變性，因此，它可以用于三維視角和噪聲的可靠匹配。
SIFT算法可以解決的問題：
- 目標(biāo)的旋轉(zhuǎn)、縮放、平移（RST）
- 圖像仿射/投影變換（視點(diǎn)viewpoint）
- 弱光照影響（illumination）
- 部分目標(biāo)遮擋（occlusion）
- 雜物場景（clutter）
- 噪聲
3.1 SIFT算法實(shí)現(xiàn)步驟
實(shí)質(zhì)可以歸為在不同尺度空間上查找特征點(diǎn)（關(guān)鍵點(diǎn)）的問題。
SIFT算法實(shí)現(xiàn)特征匹配主要有三個流程：
3.2?關(guān)鍵點(diǎn)檢測的相關(guān)概念
3.2.1 關(guān)鍵點(diǎn)（特征點(diǎn)）
???????? 這些點(diǎn)是一些十分突出的點(diǎn),不會因光照、尺度、旋轉(zhuǎn)等因素的改變而消失，比如角點(diǎn)、邊緣點(diǎn)、暗區(qū)域的亮點(diǎn)以及亮區(qū)域的暗點(diǎn)。假定兩幅圖像中有相同的景物，那么使用某種算法分別提取各自的特征點(diǎn)，這些點(diǎn)之間會有相互對應(yīng)的匹配關(guān)系。根據(jù)歸納，我們可以看出SIFT特征點(diǎn)希望選出具有下述不變性的點(diǎn)：尺度、方向、位移、光照。
3.2.2 尺度空間
????????尺度空間理論最早于1962年提出，其主要思想是通過對原始圖像進(jìn)行尺度變換，獲得圖像多尺度下的空間表示。從而實(shí)現(xiàn)邊緣、角點(diǎn)檢測和不同分辨率上的特征提取，以滿足特征點(diǎn)的尺度不變性。
????????尺度空間中各尺度圖像的模 糊程度逐漸變大，能夠模擬人在 距離目標(biāo)由近到遠(yuǎn)時目標(biāo)在視網(wǎng) 膜上的形成過程。 尺度越大圖像越模糊。
? ? ? ?
- 尺度不變性
? ??
- 旋轉(zhuǎn)不變性
? ??
?根據(jù)文獻(xiàn)《Scale-space theory: A basic tool for analysing structures at different scales》可知，高斯核可以產(chǎn)生多尺度空間的核，一個圖像的尺度空間L(x, y, σ) ，定義為原始圖像 I(x, y)與一個可變尺度的2維高斯函數(shù)G(x, y, σ) 卷積運(yùn)算。
高斯函數(shù)：
尺度空間：
?其中，*表示卷積計(jì)算。
3.2.3 高斯模糊
????????高斯模糊是在Adobe Photoshop等圖像處理軟件中廣泛使用的處理 效果，通常用它來減小圖像噪聲以及降低細(xì)節(jié)層次。這種模糊技術(shù)生成的圖像的視覺效果是好像經(jīng)過一個半透明的屏幕觀察圖像。
3.2.4?高斯金字塔
????????高斯金字塔的構(gòu)建過程可分為兩步： （1）對圖像做高斯平滑； （2）對圖像做降采樣。
????????為了讓尺度體現(xiàn)其連續(xù)性，在簡單 下采樣的基礎(chǔ)上加上了高斯濾波。一幅圖像可以產(chǎn)生幾組（octave） 圖像，一組圖像包括幾層（interval）圖像。
高斯圖像金字塔共o組、s層， 則有：
σ——尺度空間坐標(biāo)；s——sub-level層坐標(biāo)；σ0——初始尺度；S——每組層數(shù)（一般為3~5）。
最后可將組內(nèi)和組間尺度歸為：
i——金字塔組數(shù)；n——每一組的層數(shù)。
3.3?檢測尺度空間極值
3.3.1 DoG（Difference of Gaussian）函數(shù)
為了有效提取穩(wěn)定的關(guān)鍵點(diǎn)，利用不同尺度的高斯差分核與卷積生成。
DOG在計(jì)算上只需相鄰高斯平滑后圖像相減，因此簡化了計(jì)算！
3.3.2 DoG高斯差分金字塔
????????對應(yīng)DOG算子，需構(gòu)建DOG金字塔。可以通過高斯差分圖像看出圖像上的像素值變化情況。（如果沒有變化，也就沒有特征。特征必須是變化盡可能多的點(diǎn)。）DOG圖像描繪的是目標(biāo)的輪廓。
3.3.3?DOG局部極值檢測
????????特征點(diǎn)是由DOG空間的局部極值點(diǎn)組成的。為了尋找DOG函數(shù)的極值點(diǎn)，每一個像素點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域 的相鄰點(diǎn)大或者小。
????????中間的檢測點(diǎn)和它同尺度的8個相鄰點(diǎn)和上下相鄰尺度對應(yīng)的9×2個點(diǎn)共26個點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測到極值點(diǎn)。
3.4 關(guān)鍵點(diǎn)的精確定位
????????以上方法檢測到的極值點(diǎn)是離散空間的極值點(diǎn)，我們可以通過擬合三維二次函數(shù)來精確定位關(guān)鍵點(diǎn)的位置與尺度，由于DoG函數(shù)在圖像邊緣有較強(qiáng)的邊緣響應(yīng)，因此需要排除邊緣響應(yīng)，增強(qiáng)穩(wěn)定性和抗噪聲能力。
3.4.1?特征點(diǎn)的精確定位
????????子像素插值（Sub-pixel Interpolation）：利用已知的離散空間點(diǎn)插值得到的連續(xù)空間極值點(diǎn)的方法。
對尺度空間DOG函數(shù)進(jìn)行曲線擬合，以提高關(guān)鍵點(diǎn)的穩(wěn)定性，減小誤差。
利用DoG函數(shù)在尺度空間的Taylor展開式(擬合函數(shù))為：
其中?，求導(dǎo)并讓方程等于零，可以得到極值點(diǎn)的偏移量為：
對應(yīng)極值點(diǎn)，方程的值為：
其中?代表相對插值中心的偏移，當(dāng)它在任意維度上的偏移量大于 0.5 時，意味著插值中心已經(jīng)偏移到它的臨近點(diǎn)上，所以必須改變當(dāng)前關(guān)鍵點(diǎn)的位置。同時在新的位置上反復(fù)插值直到收斂；有也可能超出所設(shè)定的迭代次數(shù)或者超出圖像邊界的范圍，此時這樣的點(diǎn)應(yīng)該刪除。另外，?過小的點(diǎn)易受噪聲的干擾而變得不穩(wěn)定，所以將 小于某個經(jīng)驗(yàn)值的極值點(diǎn)刪除。同時，在此過程中獲取特征點(diǎn)的精確位置（原位置上加上擬合的偏移量）以及尺度。
3.4.2?剔除不穩(wěn)定的邊緣響應(yīng)點(diǎn)
????????由于DoG函數(shù)在圖像邊緣有較強(qiáng)的邊緣響應(yīng)，因此需要排除邊緣響應(yīng)。 DoG函數(shù)的峰值點(diǎn)在邊緣方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率可以通過計(jì)算在該點(diǎn)位置尺度的2×2的Hessian矩陣得到，導(dǎo)數(shù)由采樣點(diǎn)相鄰差來估計(jì)：
其中??,是候選點(diǎn)鄰域?qū)?yīng)位置的差分求得的。
D的主曲率和H的特征值成正比。令 α ，β為特征值，則:
該值在兩特征值相等時達(dá)最小。Lowe論文中建議閾值T為1.2，即:
時保留關(guān)鍵點(diǎn)，反之剔除。
3.5?關(guān)鍵點(diǎn)方向分配
????????通過尺度不變性求極值點(diǎn)，可以使其具有縮放不變的性質(zhì)。而利用?鍵點(diǎn)鄰域像素的梯度方向分布特性，可以為每個關(guān)鍵點(diǎn)指定方向參數(shù)方向，從而使描述子對圖像旋轉(zhuǎn)具有不變性。
????????通過求每個極值點(diǎn)的梯度來為極值點(diǎn)賦予方向。
????????像素點(diǎn)的梯度表示：
? ? ? ? 梯度幅值：
????????梯度方向：
????????計(jì)算得到梯度方向后，就是用直方圖統(tǒng)計(jì)特征點(diǎn)鄰域內(nèi)像素對應(yīng)的梯度方向和幅值。梯度方向的直方圖的橫軸是梯度方向的角度（梯度方向的范圍是 0 到 360 度，直方圖每 36 度一個柱，共 10 個柱），縱軸是梯度方向?qū)?yīng)梯度幅值的累加，在直方圖的峰值就是特征點(diǎn)的主方向。
關(guān)鍵點(diǎn)的主方向與輔方向：
- 關(guān)鍵點(diǎn)主方向：極值點(diǎn)周圍區(qū)域梯度直方圖的主峰值也是特征點(diǎn)方向
- 關(guān)鍵點(diǎn)輔方向：在梯度方向直方圖中，當(dāng)存在另一個相當(dāng)于主峰值 80%能量的峰值時，則將這個方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向。
????????這可以增強(qiáng)匹配的魯棒性，Lowe的論文指出大概有15%關(guān)鍵點(diǎn)具有 多方向，但這些點(diǎn)對匹配的穩(wěn)定性至為關(guān)鍵。
3.6?關(guān)鍵點(diǎn)描述
????????下圖是一個SIFT描述子事例。其中描述子由2×2×8維向量表征，也即是 2×2個8方向的方向直方圖組成。左圖的種子點(diǎn)由8×8單元組成。每一個小格都代表了特征點(diǎn)鄰域所在的尺度空間的一個像素，箭頭方向代表了像素梯度方 向，箭頭長度代表該像素的幅值。然后在4×4的窗口內(nèi)計(jì)算8個方向的梯度方向直方圖。繪制每個梯度方向的累加可形成一個種子點(diǎn)，如右圖所示：一個特征 點(diǎn)由4個種子點(diǎn)的信息所組成。
????????與求主方向不同，此時每個種子區(qū)域的梯度直方圖在0-360之間劃分為8個方向區(qū)間，每個區(qū)間為45度，即每個種子點(diǎn)有8個方向的梯度強(qiáng)度信息。在實(shí)際的計(jì)算過程中，為了增強(qiáng)匹配的穩(wěn)健性，Lowe建議對每個關(guān)鍵點(diǎn)使用? 4×4共16個種子點(diǎn)來描述，這樣一個關(guān)鍵點(diǎn)就可以產(chǎn)生128維的SIFT特征向量。
????????通過對特征點(diǎn)周圍的像素進(jìn)行分塊，計(jì)算塊內(nèi)梯度直方圖，生成具有獨(dú)特性的向量，這個向量是該區(qū)域圖像信息的一種抽象，具有唯一性。
3.7?關(guān)鍵點(diǎn)匹配
????????分別對模板圖（參考圖，reference image）和實(shí)時圖（觀測圖， observation image）建立關(guān)鍵點(diǎn)描述子集合。目標(biāo)的識別是通過兩點(diǎn) 集內(nèi)關(guān)鍵點(diǎn)描述子的比對來完成。具有128維的關(guān)鍵點(diǎn)描述子的相似 性度量采用歐式距離。
模板圖中關(guān)鍵點(diǎn)描述子：
實(shí)時圖中關(guān)鍵點(diǎn)描述子：
任意兩描述子相似性度量：
要得到配對的關(guān)鍵點(diǎn)描述子，??? 需滿足：
????????關(guān)鍵點(diǎn)的匹配可以采用窮舉法來完成，但是這樣耗費(fèi)的時間太多，一般都采用kd樹(一個平衡二叉樹)的數(shù)據(jù)結(jié)構(gòu)來完成搜索。搜索的內(nèi)容是以目標(biāo)圖像的關(guān)鍵點(diǎn)為基準(zhǔn)，搜索與目標(biāo)圖像的特征點(diǎn)最鄰近的原圖像特征點(diǎn)和次鄰近的原圖像特征點(diǎn)。
3.8 編程實(shí)現(xiàn)
3.8.1 檢測感興趣點(diǎn)
# 檢測感興趣點(diǎn) from PIL import Image from pylab import * from numpy import * import os# 處理一幅圖像，然后將結(jié)果保存在文件中 def process_image(imagename, resultname, params="--edge-thresh 10 --peak-thresh 5"):if imagename[-3:] != 'pgm':# 創(chuàng)建一個pgm文件im = Image.open(imagename).convert('L')im.save('tmp.pgm')imagename = 'tmp.pgm'cmmd = str("D:\python\win64vlfeat\sift.exe " + imagename + " --output=" + resultname + " " + params)os.system(cmmd)print('processed', imagename, 'to', resultname)# 讀取特征屬性值，然后將其以矩陣的形式返回 def read_features_from_file(filename):f = loadtxt(filename)return f[:, :4], f[:, 4:] # 特征位置，描述子# 將特征位置和描述子保存到文件中 def write_featrues_to_file(filename, locs, desc):savetxt(filename, hstack((locs, desc)))# 顯示帶有特征的圖像 def plot_features(im, locs, circle=False):# 輸入：im（數(shù)組圖像），locs（每個特征的行、列、尺度和朝向）def draw_circle(c, r):t = arange(0, 1.01, .01) * 2 * pix = r * cos(t) + c[0]y = r * sin(t) + c[1]plot(x, y, 'b', linewidth=2)imshow(im)if circle:for p in locs:draw_circle(p[:2], p[2])else:plot(locs[:, 0], locs[:, 1], 'ob')axis('off')? 運(yùn)行測試：
imname = 'picture1.jpg' im = array(Image.open(imname).convert('L')) process_image(imname, 'picture1.sift') l1, d1 = read_features_from_file('picture1.sift')figure() gray() subplot(131) plot_features(im, l1, circle=False) title('SIFT Feature') subplot(132) plot_features(im, l1, circle=True) title('SIFT Feature Scale')# 檢測harris角點(diǎn) harrisim = compute_harris_response(im)subplot(133) filtered_coords = get_harris_points(harrisim, 60, 0.1) imshow(im) plot([p[1] for p in filtered_coords], [p[0] for p in filtered_coords], '*') axis('off') title('Harris Corner Point') show()? 輸出結(jié)果：
3.8.2 兩張圖像的SIFT特征匹配
# SIFT特征匹配 from PIL import Image from pylab import * from numpy import * import os# 處理一幅圖像，然后將結(jié)果保存在文件中 def process_image(imagename, resultname, params="--edge-thresh 10 --peak-thresh 5"):if imagename[-3:] != 'pgm':# 創(chuàng)建一個pgm文件im = Image.open(imagename).convert('L')im.save('tmp.pgm')imagename = 'tmp.pgm'cmmd = str("D:\python\win64vlfeat\sift.exe " + imagename + " --output=" + resultname + " " + params)os.system(cmmd)print('processed', imagename, 'to', resultname)# 讀取特征屬性值，然后將其以矩陣的形式返回 def read_features_from_file(filename):f = loadtxt(filename)return f[:, :4], f[:, 4:] # 特征位置，描述子# 將特征位置和描述子保存到文件中 def write_featrues_to_file(filename, locs, desc):savetxt(filename, hstack((locs, desc)))# 顯示帶有特征的圖像 def plot_features(im, locs, circle=False):# 輸入：im（數(shù)組圖像），locs（每個特征的行、列、尺度和朝向）def draw_circle(c, r):t = arange(0, 1.01, .01) * 2 * pix = r * cos(t) + c[0]y = r * sin(t) + c[1]plot(x, y, 'b', linewidth=2)imshow(im)if circle:for p in locs:draw_circle(p[:2], p[2])else:plot(locs[:, 0], locs[:, 1], 'ob')axis('off')# 對于第一幅圖像中的每個描述子，選取其在第二幅圖像中的匹配 def match(desc1, desc2):# 輸入：desc1(第一幅圖像中的描述子)，desc2(第二幅圖像中的描述子)desc1 = array([d / linalg.norm(d) for d in desc1])desc2 = array([d / linalg.norm(d) for d in desc2])dist_ratio = 0.6desc1_size = desc1.shapematchscores = zeros((desc1_size[0], 1), 'int')desc2t = desc2.T # 預(yù)先計(jì)算矩陣轉(zhuǎn)置for i in range(desc1_size[0]):dotprods = dot(desc1[i, :], desc2t) # 向量點(diǎn)乘dotprods = 0.9999 * dotprods# 反余弦和反排序，返回第二幅圖像中特征的索引indx = argsort(arccos(dotprods))# 檢查最近鄰的角度是否小于dist_ratio乘以第二近鄰的角度if arccos(dotprods)[indx[0]] < dist_ratio * arccos(dotprods)[indx[1]]:matchscores[i] = int(indx[0])return matchscores# 雙向?qū)ΨQ版本的match() def match_twosided(desc1, desc2):matches_12 = match(desc1, desc2)matches_21 = match(desc2, desc1)ndx_12 = matches_12.nonzero()[0]# 去除不對稱的匹配for n in ndx_12:if matches_21[int(matches_12[n])] != n:matches_12[n] = 0return matches_12# 返回將兩幅圖像并排拼接成的一幅新圖像 def appendimages(im1, im2):# 選取具有最少行數(shù)的圖像，然后填充足夠的空行rows1 = im1.shape[0]rows2 = im2.shape[0]if rows1 < rows2:im1 = concatenate((im1, zeros((rows2 - rows1, im1.shape[1]))), axis=0)elif rows1 > rows2:im2 = concatenate((im2, zeros((rows1 - rows2, im2.shape[1]))), axis=0)return concatenate((im1, im2), axis=1)# 顯示一幅帶有連接匹配之間連線的圖片 def plot_matches(im1, im2, locs1, locs2, matchscores, show_below=True):# 輸入：im1, im2(數(shù)組圖像), locs1,locs2（特征位置）,matchscores(match()的輸出)，# show_below（如果圖像應(yīng)該顯示在匹配的下方）im3 = appendimages(im1, im2)if show_below:im3 = vstack((im3, im3))imshow(im3)cols1 = im1.shape[1]for i in range(len(matchscores)):if matchscores[i] > 0:plot([locs1[i, 0], locs2[matchscores[i, 0], 0] + cols1], [locs1[i, 1], locs2[matchscores[i, 0], 1]], 'c')axis('off')? 運(yùn)行測試：
im1f = 'picture1.jpg' im2f = 'picture1.jpg' im1 = array(Image.open(im1f)) im2 = array(Image.open(im2f))process_image(im1f, 'out_sift_1.txt') l1, d1 = read_features_from_file('out_sift_1.txt') figure() gray() subplot(121) plot_features(im1, l1, circle=False)process_image(im2f, 'out_sift_2.txt') l2, d2 = read_features_from_file('out_sift_2.txt') subplot(122) plot_features(im2, l2, circle=False)matches = match_twosided(d1, d2) print('{} matches'.format(len(matches.nonzero()[0]))) figure() gray() plot_matches(im1, im2, l1, l2, matches, show_below=True) show()? 輸出結(jié)果：
3.8.3?地理標(biāo)記圖像匹配
from PIL import Image from numpy import * import os import pydot from PCV.localdescriptors import sift# 獲取圖像列表 def get_imlist(path):return [os.path.join(path, f) for f in os.listdir(path) if f.endswith('.png')]download_path = "D:/python/workSpace/ComputerVision/Test2/Pictures" path = "D:/python/workSpace/ComputerVision/Test2/Pictures"# 獲取文件名列表 imlist = get_imlist(download_path) nbr_images = len(imlist) print(nbr_images)# 提取特征 featlist = [imname[:-3] + 'sift' for imname in imlist] for i, imname in enumerate(imlist):sift.process_image(imname, featlist[i])matchscores = zeros((nbr_images, nbr_images))for i in range(nbr_images):for j in range(i, nbr_images): # only compute upper triangleprint('comparing ', imlist[i], imlist[j])l1, d1 = sift.read_features_from_file(featlist[i])l2, d2 = sift.read_features_from_file(featlist[j])matches = sift.match_twosided(d1, d2)nbr_matches = sum(matches > 0)print('number of matches = ', nbr_matches)matchscores[i, j] = nbr_matches print("The match scores is: \n", matchscores)# 復(fù)制值 for i in range(nbr_images):for j in range(i + 1, nbr_images): # no need tomatchscores[j, i] = matchscores[i, j]# 可視化 # min number of matches needed to craete link threshold = 2# don't want the default directed graph g = pydot.Dot(graph_type='graph')for i in range(nbr_images):for j in range(i + 1, nbr_images):if matchscores[i, j] > threshold:# 圖像對中的第一幅圖像im = Image.open(imlist[i])im.thumbnail((100, 100))filename = path + str(i) + '.png'im.save(filename) # 需要一定大小的臨時文件g.add_node(pydot.Node(str(i), fontcolor='transparent',shape='rectangle', image=filename))# 圖像對中的第二幅圖像im = Image.open(imlist[j])im.thumbnail((100, 100))filename = path + str(j) + '.png'print(filename);im.save(filename) # 需要一定大小的臨時文件g.add_node(pydot.Node(str(j), fontcolor='transparent',shape='rectangle', image=filename))g.add_edge(pydot.Edge(str(i), str(j))) g.write_png('result.png')? 輸出結(jié)果：
3.8.4?實(shí)驗(yàn)過程中遇到的問題
問題一：
UserWarning: loadtxt: Empty input file: "out_sift.1.txt"? f = loadtxt(filename)
IndexError: too many indices for array: array is 1-dinmensional，but 2 were indexed
—直報錯類似的問題，還沒解決!!!
錯誤原因：生成的sift文件為空，即特征提取為空。
解決辦法：vlfeat0.9.20版本，下載了vcomp100.dll文件，下載鏈接https://cn.dll-files.com/vcomp100.dll.html，64位系統(tǒng)對應(yīng)64位。
參考博客：vlfeat0.9.21提取sift特征為空_lrwin_bian的博客-CSDN博客
vlfeat安裝參考教程：Python計(jì)算機(jī)視覺編程 - 安裝
問題二：
關(guān)于Graphviz安裝教程的一些問題：
第一步：確認(rèn)在Graphviz官網(wǎng)下載并安裝了對應(yīng)操作系統(tǒng)（Windows，Linux，Mac）的Graphviz軟件。官網(wǎng)地址：https://www.graphviz.org/。安裝過程中有一個選項(xiàng)，建議選擇添加至所有人，如下圖：
第二步：將軟件安裝目錄的bin文件添加到系統(tǒng)環(huán)境中。如我的電腦是Windows系統(tǒng)，Graphviz安裝在D:\Program Files\Graphviz2.38，該目錄下有bin文件，將該路徑添加到系統(tǒng)環(huán)境變量中，即D:\Program Files\Graphviz2.38\bin。如果第一步選擇了PATH添加至所有人，則這一步可以直接跳過！
第三步：使用pip命令安裝以下模塊：
????????????????pip install pydot-ng
????????????????pip install graphviz
????????????????pip install pydot
????????????????注意安裝順序，一定要先安裝grahiviz，再pip install pydot！！！
第四步：進(jìn)入windows命令行界面，輸入dot -version，然后按回車，如果顯示graphviz的相關(guān)版本信息，則安裝配置成功。如圖：
依照上述步驟基本不會有問題，若仍報錯"dot" not found in path，那么在提示目錄下(如前文報錯內(nèi)容加粗目錄)找到pydot.py文件的源碼，在pydot.py中找到類Dot的定義，進(jìn)行如下修改：
保存文件，如果運(yùn)行仍報錯"dot" not found in path，那就重啟電腦！！！！
到這里，再運(yùn)行就沒出問題了。
總結(jié)
以上是生活随笔為你收集整理的计算机视觉：特征提取与匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Weisfeiler-Lehman(WL
- 下一篇： html自动适应屏幕分辨率,关于HTML