# 探討特徵提取與匹配 - 理論與實驗

# 1. 前言
特徵提取與匹配在二維電腦視覺和三維電腦視覺都有廣泛的應用，從靜態影像拼接、相機校正到三維模型重建等。

本文將逐一講解特徵提取的演算法，從經典的 SIFT (Scale Invariant Feature Transform)，到基於其衍生的 DSP-SIFT (Domain-Size Pooling Scale Invariant Feature Transform)，和近期基於深度學習網路的 SuperPoint 等。

最後，我們會做實驗去比較、分析和評估這三種演算法的特性、優缺點，希望藉此更理解他們的理論基礎以及應用場景的差異。

# 2. 理論

## 2.1 SIFT (Scale Invariant Feature Transform)

此演算法會將一張影像轉換成一個大的局部特徵向量 (local feature vectors) 的集合，每一個局部特徵向量會不變，即使在影像平移 (translation), 縮放 (scaling) 和旋轉 (rotation), 以及部份不變在光照改變的情況下。

在尺度空間中（在 2.1.1 會介紹），透過尋找高斯差分（Difference-of-Gaussian）函數的極大值或極小值位置（在 2.1.1 後面會介紹），來識別關鍵位置。每個關鍵點都會用來產生一個特徵向量，用於描述依照其尺度空間座標系取樣的局部影像區域。這些特徵透過對影像梯度位置進行模糊處理，達成對局部變化（例如仿射變換或三維投影）的部分不變性。此方法是基於哺乳類視覺皮層中複雜細胞（complex cells）行為的模型所設計。最終得到的特徵向量稱為 SIFT 關鍵點（SIFT keys）。在目前的實作中，每張影像會產生約 1000 個 SIFT 關鍵點，而整個過程的計算時間少於 1 秒。


### 2.1.1 尺度空間的建立 (Construction of Scale-Space)

#### 高斯影像金字塔的生成

以白話來說，可以假設現在我們有一張對台北市仁愛圓環的空拍圖，現在我們先對它做高斯模糊，並得到在這個影像尺寸下的從清晰到越來越模糊的一疊影像，越模糊的放在越上面。現在我們複製那疊影像裡面中度模糊的影像然後做尺寸上的縮小，當作是影像金字塔的往上面新的一層的底，然後重複剛才高斯模糊的操作在該層得到另一疊影像。經過數次這樣的操作後，按照時間先後順序，越近期得到的那疊影像，放在越上面，我們就得到所謂的高斯影像金字塔。

以實做細節上來說，由於二維高斯函數（2D Gaussian function）是可分離的，因此將其與輸入影像進行卷積時，可以先在水平方向、再在垂直方向各進行一次一維高斯函數（1D Gaussian function）的運算，就能高效地完成計算。在關鍵點定位（key localization）過程中，所有的平滑（smoothing）運算都採用 $\sigma = \sqrt{2}$ 。這個運算可以用一個包含 7 個取樣點的一維濾波器（1D kernel）來近似，並且能達到足夠的精確度。


在這裡，輸入影像首先使用高斯函數以 $\sigma = \sqrt{2}$ 進行卷積，得到影像 \(A\)。接著，再以相同的 $\sigma = \sqrt{2}$ 進行一次增量平滑，得到新的影像 \(B\)，此時影像 \(B\) 的有效平滑尺度為 $\sigma = {2}$。

為了產生下一層金字塔（pyramid）影像，此方法利用雙線性插值（bilinear interpolation）對已經平滑過的影像 \(B\) 進行重取樣（resample），在每個方向上的像素間距為 1.5。 雖然看起來用比例 $\sqrt{2}$ 進行重取樣會比較自然，但唯一的限制是取樣必須夠密，才能偵測到極大值與極小值。1.5 的間距表示每個新像素都是原本相鄰 4 個像素的線性組合，這樣的做法計算效率高，且能最小化重取樣系數變動所帶來的混疊（aliasing）現象。


#### 高斯差分影像金字塔 (DoG) 的生成

我們為了要得到 DoG 影像金字塔，我們將該層的底部的影像和它上面一層的影像相減，得到一張 DoG 影像，然後在它上面一層的影像又和它上上面一層的影像相減，得到第二張 DoG 影像。以此類推，對於高斯影像金字塔的每一層都做一樣的操作，我們可以得到 DoG 影像金字塔。

高斯差分函數（Difference of Gaussian, DoG）也就是是透過用影像 \(A\) 減去影像 \(B\) 來得到，這兩個高斯的比例為 $(2/\sqrt{2} = \sqrt{2})$。


### 2.1.2 關鍵點定位與篩選 (Keypoint Localization and Filtering)

尺度空間函數的極大值與極小值，是透過比較 DoG 影像金字塔中每個像素與其鄰居來決定的。 首先，每個像素會和該 DoG 影像金字塔層級內的 8 個鄰居做比較，如果該像素在這層是極大值或極小值，接著會計算在下一個較低層（解析度較高）中對應的像素位置，考慮到 1.5 倍的重取樣比例。 如果該像素在較低層依然比該位置像素和其 8 個鄰居更大（或更小），則會進一步向上一層重複此測試。由於大部分像素會在幾次比較後被淘汰，因此這個偵測過程的計算成本很低，比建立 DoG 影像金字塔的計算量小得多。

若 DoG 影像金字塔的第一層取樣率和輸入影像相同，最高頻率訊號將會被忽略。這是因為初始的平滑步驟會使得訊號峰值分離，確保偵測的穩健性。因此，我們會先將輸入影像使用雙線性插值放大 2 倍，然後再建構 DoG 影像金字塔。這樣做後，一張典型的 512×512 像素影像大約能產生 1000 個關鍵點，相較於沒有放大時只有四分之一的數量。

### 2.1.3 關鍵點穩定性

為了在每個關鍵點描述影像，金字塔每一層的平滑影像 \(A\) 會被用來提取影像梯度和方向。在每個像素 $A_{ij}$ 上，利用像素差分計算影像梯度的大小 $M_{ij}$ 和方向 $R_{ij}$：


像素差分計算效率很高，並且由於先前已經進行了大量平滑，其精確度也足夠。在確定關鍵點位置時，會補償有效的半像素偏移。

對光照變化的魯棒性透過對梯度大小進行閾值處理來增強，閾值設定為最大可能梯度值的 0.1 倍。這可以減少光照方向變化對具有 3D 凹凸表面的影響，因為光照改變可能會導致梯度大小發生很大變化，但對梯度方向的影響相對較小。

每個關鍵點會被分配一個標準方向，使得影像描述符對旋轉保持不變。為了使其對光照或對比度變化盡可能穩定，方向是透過局部影像梯度方向的直方圖峰值來決定的。方向直方圖是使用高斯加權窗口建立的，其標準差為當前平滑尺度的 3 倍。

這些權重會與閾值化後的梯度值相乘，並累加到對應方向 $R_{ij}$ 的直方圖中。直方圖共有 36 個區間，覆蓋 360 度的旋轉範圍，並在選擇峰值前進行平滑處理。

可以通過對自然影像施加仿射投影、對比度與亮度變化，以及加入噪聲，來測試所得到的關鍵點的穩定性。對第一張影像中檢測到的每個關鍵點，其在變換後影像中的位置可以根據變換參數進行預測。這個框架被用來選擇上述各種採樣和平滑參數，以在保持穩定性的同時獲得最佳效率。

圖 1 顯示了在 2 個倍頻範圍內僅對較大尺度檢測到的相對少量關鍵點（以避免過度擁擠）。每個關鍵點用一個方框表示，從中心到方框一邊的線表示方向。在圖的後半部分，影像旋轉了 15 度，縮放因子為 0.9，水平方向拉伸 1.1 倍。像素強度範圍在 0 到 1 之間，亮度減去 0.1，對比度乘以 0.9。隨後加入隨機像素噪聲，使信號小於 5 bits/像素。儘管經過這些變換，第一張影像中 78% 的關鍵點在第二張影像中仍能在預測位置、尺度和方向上找到相匹配的關鍵點。


### 2.1.4 局部影像描述子 (Local image description)

給定每個關鍵點的穩定**位置、尺度和方向**後，就可以以一種對這些變換不變的方式來描述該區域的局部影像。此外，還希望這種表示方式對局部幾何形狀的小偏移具有魯棒性，例如仿射變換或 3D 投影所造成的變化。

其中一種方法來自於視覺皮層複雜神經元（complex neurons）的反應特性：
**在保持方向和空間頻率專一性的同時，允許特徵位置在一個小範圍內變化**。 Edelman, Intrator 和 Poggio [5] 進行的實驗模擬了複雜神經元對不同 3D 視角的電腦圖形模型的反應，發現複雜細胞的輸出在區分能力上明顯優於基於簡單相關性的匹配。這可以用一個例子來說明：**若仿射投影在某一方向上對影像進行了拉伸，則梯度特徵的相對位置會改變，但對它們的方向和空間頻率影響較小。**

這種對局部幾何失真的魯棒性可以透過用多張分別表示不同方向的影像（稱為方向平面）來描述局部影像區域而獲得。每個方向平面僅包含對應該方向的梯度，對於中間方向則使用線性插值。每個方向平面會進行模糊處理（blurring）和重新取樣，以允許梯度位置有較大的偏移。

這種方法可以高效實作，因為可以直接重用在高斯影像金字塔每一層為方向選擇所預先計算好的梯度與方向資訊。對於每個關鍵點，作者使用其被檢測到所在高斯影像金字塔層的像素取樣。在關鍵點位置周圍半徑 8 像素的圓內的像素，會被插入到對應的方向平面中。方向的計算是相對於關鍵點方向進行的，方法是用像素的梯度方向減去關鍵點的方向。

在實驗中，作者使用了 8 個方向平面，每個平面在 4×4 的位置網格上進行取樣，取樣間距是梯度檢測時像素間距的 4 倍。模糊處理是透過將每個像素的梯度分配給其在取樣網格中的 8 個最近鄰點，並在方向與兩個空間維度上進行線性插值來完成的。這種實現方式比顯式進行模糊與重新取樣要高效得多，但效果幾乎相同。

為了在更大尺度下取樣，這一過程會在高斯影像金字塔高一個八度的第二層重複一次。不過，這一次採用的是 2×2 的取樣區域，而不是 4×4，這樣在兩個尺度下觀察到的影像區域就大致相同，因此附近的遮擋不會對某一個尺度產生更大影響。因此，SIFT 關鍵點向量中來自兩個尺度的總取樣數為：8×4×4+8×2×2=160，也就產生了一個 160 維的向量，這提供了足夠多的測量值來保證高度的區分能力。

## 2.2 DSP-SIFT (Domain-Size Pooling - Scale Invariant Feature Transform)



（待補）

## 2.3 SuperPoint

SuperPoint 基於深度學習的方法在一張影像上尋找關鍵點 keypoints (interesting points)。它使用一個 downsized map (W/8 and H/8) 的張量 65 channels 來編碼關鍵點，而不是使用 deconvolution layers 和一個原始影像大小的 binary mask 來表示關鍵點。


（待補）

# 3. 實驗與結果

我們將做實驗去比較、分析和評估這三種演算法的特性、優缺點。希望藉此更理解他們的理論基礎以及應用場景的差異。

（待補）

# 參考文獻
[1] D. G. Lowe, "Object recognition from local scale-invariant features," in Proc. 7th IEEE Int. Conf. Computer Vision, vol. 2, Kerkyra, Greece, 1999, pp. 1150–1157.
[2] J. Dong and S. Soatto, "Domain-size pooling in local descriptors: DSP-SIFT," in Proc. IEEE Conf. Computer Vision and Pattern Recognition, Boston, MA, USA, 2015, pp. 5097–5106.
[3] D. DeTone, T. Malisiewicz, and A. Rabinovich, "Superpoint: Self-supervised interest point detection and description," in Proc. IEEE Conf. Computer Vision and Pattern Recognition Workshops, Salt Lake City, UT, USA, 2018, pp. 224–236.