## SIFT
尺度不變特徵轉換是圖像處理領域中的一種局部特徵描述算法，不僅具有尺度不變性，即使改變圖像旋轉角度或亮度，依然能得到很好的檢測結果。其中，算法流程包含以下步驟:

1. 建立高斯影像金字塔（Gaussian image pyramid）
2. 在差分影像金字塔（DoG）中提取 SIFT 特徵點
3. 建立 SIFT 特徵敘述子，對測試影像作關鍵點匹配

<div class="text-center">
<img src="https://hackmd.io/_uploads/ryox9Ihs0.png" style="width: 600px; object-fit: cover;">
</div>

## Gaussain Image Pyramid
影像金字塔是一種以多解析度來解釋影像的結構，通過對原始影像進行多尺度點數採樣的管道，生成 N 個不同分辨率（解析度）的影像。將分辨率最高的影像放在底部，以金字塔形狀排列，往上是一系列解析度逐漸降低的影像，一直到金字塔的頂部可能只包含一個點數的影像，初衷在於模擬人眼感知遠近差異:

* 大小: 物體遠看小、近看大
* 模糊: 可理解為粗細，遠看模糊（輪廓）、近看清晰（紋理）

其中，若以頻率角度切入，模糊的輪廓代表圖像較平滑的區域，也就是低頻部分；而清晰的紋理則屬於高頻部分。因此，影像金字塔就是考慮了

* 圖像遠近程度: 以 Upsampling 和 Downsampling 來做
* 圖像粗細程度: 用 Gaussian kernel 做平滑化

詳細過程如下:

1. 影像先擴大一倍做為第一組第一層 $(1,1)$，通過高斯平滑（高斯濾波）後變成第一組第二層 $(1,2)$，Gaussain kernel 為

\begin{gathered}
G(x,y)=\frac{1}{2\pi\sigma^2}e^{-\frac{(x-x_0)^2+(y-y_0)^2}{2\sigma^2}}
\end{gathered}

其中，$\sigma$ 預設為 1.6

2. $\sigma$ 乘以固定比例得到新平滑因子 $\sigma=k\sigma$，用來平滑 $(1,2)$ 後得到 $(1,3)$...不斷持續下去，==在同一組中影像尺寸都相同，只是平滑係數不同==

3. 假設有 $L$ 層，將倒數第三層 $(1,L-2)$ 做二倍 Downsampling 變為第二組第一層 $(2,1)$，==執行高斯平滑邏輯同樣如上述，只是尺寸變為第一組影像的一半==，最後得到的影像金字塔如下圖:

<div class="text-center">
<img src="https://hackmd.io/_uploads/ByX1F2XJye.png" style="width: 250px; object-fit: cover;">
</div>

舉例來說，第一組的前四層、第二組的前四層會長這樣:

<div class="text-center">
<img src="https://hackmd.io/_uploads/BkNYF27yyx.png" style="width: 300px; object-fit: cover;">
<img src="https://hackmd.io/_uploads/HkhFKhX1kx.png" style="width: 200px; object-fit: cover;">
</div>

&nbsp;
透過上述流程組成 $O$ 組 $L$ 層影像金字塔，組成一個 $(O,L)$ 的二維尺度空間，任意給定一組 $(O,L)$ 座標就代表著金字塔中的一幅影像:

<div class="text-center">
<img src="https://hackmd.io/_uploads/ByL1o2mJyg.png" style="width: 500px; object-fit: cover;">
</div>

## DoG（Difference of Gaussian）
建立出影像金字塔後，將每一組的相鄰二層相減，就會得到差分金字塔，後續 SIFT 的特徵點提取都是在差分金字塔上進行:

<div class="text-center">
<img src="https://hackmd.io/_uploads/BJpY8pm1Je.png" style="width: 400px; object-fit: cover;">
</div>

在差分的影像中，可以觀察出即使在不同尺度下，某些特徵都還是存在，這些就是 SIFT 要提取的穩定特徵:

<div class="text-center">
<img src="https://hackmd.io/_uploads/SkdGwpXJyl.png" style="width: 400px; object-fit: cover;">
</div>

&nbsp;
而提取 SIFT 特徵點的步驟如下:

1. 先設定閥值濾除雜訊:

\begin{gathered}
abs(val)>0.5\frac{T}{n}
\end{gathered}

$T$ 預設為 0.04、$n$ 為能用來提取特徵的差分影像數量、$abs(val)$ 為像素灰階值

2. 尋找極值
每一個像素要和三個方向上所有相鄰點（26 個點）做比較。假設該組 DoG 影像有三層，只有中間層能夠找極值，其餘兩端圖像不連續，沒有極值；假設有五層，只有中間三層能夠找極值，依此類推:

<div class="text-center">
<img src="https://hackmd.io/_uploads/rkhbsaX1ke.png" style="width: 250px; object-fit: cover;">
</div>

由於 DoG 影像是離散的，有時找到的極值並不準確，可以用泰勒展開式去近似:

<div class="text-center">
<img src="https://hackmd.io/_uploads/rkIhsp7ykl.png" style="width: 450px; object-fit: cover;">
</div>

泰勒展開式計算出的值，依然必須高於步驟一的閥值。接著還有去除邊緣效應、去除 DoG 影像曲率不對稱像素...等，可再參考 [Reference](https://blog.csdn.net/weixin_48167570/article/details/123704075) 說明

## SIFT Descriptor
經過上述流程已找到所有極值點，接下來要為這些極值點分配方向:

1. 在極值點 $3\sigma$ 的鄰近區域像素計算梯度和方向
2. 計算梯度和方向時還需加入高斯權重，在極值點處以 $1.5\sigma$ 做高斯濾波，也就是距離中心點愈近權重愈高，並根據和中心點距離降低權重
3. 橫軸以 10 度作為一個 Bin 統計直方圖
4. 直方圖峰值的方向作為主方向，並保留大小為峰值 80% 的方向作為輔方向
<div class="text-center">
<img src="https://hackmd.io/_uploads/BktlfgI11g.png" style="width: 400px; object-fit: cover;">
</div>

在上述完成後，目前每一個極值點都具有位置、尺度和方向的資訊。在每一個極值點上，取鄰近 16X16 像素並區分為 4X4 個 Block，因此每一個 Block 都代表 4X4 的像素區塊，接著:

1. 將每個 4X4=16 Block 的圖像，先轉至上述計算出的主方向
<div class="text-center">
<img src="https://hackmd.io/_uploads/BkXnXl8kJe.png" style="width: 400px; object-fit: cover;">
</div>

2. 每個 Block 都計算 8 Bins 的角度統計直方圖，最終會有 4X4X8=128 的 Feature vector 作為特徵點描述子
<div class="text-center">
<img src="https://hackmd.io/_uploads/r1bqVxUykl.png" style="width: 450px; object-fit: cover;">
<img src="https://hackmd.io/_uploads/r1zlHgI11l.png" style="width: 450px; object-fit: cover;">
</div>

上述式為完整特徵敘述子的建立流程。實務上:

1. 將樣板/參考圖（Reference image）和觀測/測試圖（Observation image）都建立特徵敘述子集合，利用歐式距離或其他衡量方式匹配這 128 維度的相似性
2. 匹配可以用窮舉法但太耗時，通常會使用 KD 樹來做搜尋，以樣板特徵點為基準，搜尋其與觀測圖最接近、次接近的特徵點

總結，特徵敘述子的建立流程如下:

1. 在 DoG 空間中做極值檢測
2. 刪除不穩定極值點
3. 確定特徵點的主方向
4. 生成特徵點敘述子並做關鍵點匹配

## Reference
* [全网最详细SIFT算法原理实现](https://blog.csdn.net/weixin_48167570/article/details/123704075)
* [Introduction to SIFT( Scale Invariant Feature Transform)](https://medium.com/@deepanshut041/introduction-to-sift-scale-invariant-feature-transform-65d7f3a72d40)
* [圖像特徵比對(二)-特徵點描述及比對](https://chtseng.wordpress.com/2017/05/22/%E5%9C%96%E5%83%8F%E7%89%B9%E5%BE%B5%E6%AF%94%E5%B0%8D%E4%BA%8C-%E7%89%B9%E5%BE%B5%E9%BB%9E%E6%8F%8F%E8%BF%B0%E5%8F%8A%E6%AF%94%E5%B0%8D/)