本文著重介紹了用于圖像特征點檢測的算法，FAST算法，以及使用matlab的實現。
FAST算法是一種拐點檢測算法，其主要應用于提取圖像中的特征點，在動態成像的一系列圖像中追蹤定位對象。眾所周知，我們生活的世界是動態化的，3D的，如何關聯動態化過程中的平移，畸變，旋轉對象，對每一幀的圖像與上一幀之間的空間關系進行分析，很大程度上需求我們在每一幀中找到對應的關鍵點。FAST方法，拐點檢測方法,簡單來說就是用于提取圖像中的關鍵點的算法，為進一步的圖像處理，包括相機標定，SLAM打下了基礎。
1. FAST算法解析
FAST拐點檢測算法使用了一個包含了16個像素點的圓來判斷目標點P是不是一個真正意義上的拐點。這16個像素點標序號為1至16。對于每一個候選像素點P，其強度為IpI_pIp? (灰度圖中即為該像素點的灰度值)。如果該圓中N個連續像素都比候選像素點P的強度亮很多，或都比候選像素點P的強度暗很多，那么P就被分類為一個拐點。 這個也比較好理解，即找出局部范圍內最亮或最暗的點，作為局部圖像的關鍵點。P為拐點所包含的情況如下:
- 條件1 : 一系列NNN個連續的像素點SSS，?s∈S,Ix>Ip+t{\forall} s\in S, I_x > Ip + t?s∈S,Ix?>Ip+t
- 條件2 : 一系列NNN個連續的像素點SSS, ?s∈S,Ix<Ip?t{\forall} s\in S, I_x < Ip - t?s∈S,Ix?<Ip?t
滿足兩個條件其中的任意一個，則可以認為像素點P為該局部區域的一個拐點。上述條件中，NNN 為連續的像素點個數，IxI_xIx?為像素點xxx的強度，ttt為設置的閾值。顯然，調整NNN以及閾值ttt，可以影響被分類為拐點的像素點P的個數。NNN值越大，被分類為拐點的像素點個數就會減少，同樣ttt值越大，被分類為拐點的像素點個數也會減少。
tips : 所謂的NNN個連續的像素點，指的是例如N=5N = 5N=5 , [1,2,3,4,5],[2,3,4,5,6]...[1,2,3,4,5], [2,3,4,5,6]...[1,2,3,4,5],[2,3,4,5,6]...這樣的像素點稱為NNN個連續的像素點。
接下來我們就看看使用matlab如何實現這個拐點檢測算法FAST。
2. MATLAB實現
下面就放出matlab代碼，用于檢測圖像I中基于閾值t的拐點的函數。返回一個包含了這些拐點像素點坐標的矩陣。注釋中詳細解釋了代碼的原理。
function CS = FAST(I,t)
% I : 灰度圖片
% t : 用戶選擇的閾值% 定義一個矩陣，描述了16個像素點關于待測像素點P的坐標關系。
% 需要注意的是，這些坐標的定義(i,j)為先行后列。
List_voisinage = [ -3 0;-3 1;-2 2;-1 3;0 3;1 3;2 2;3 1;3 0;3 -1;2 -2;1 -3;0 -3;-1 -3;-2 -2;-3,-1];
[height, width] = size(I);
% 初始化CS矩陣為空矩陣
CS = [];
const = 3;
% 定義N個連續的像素點，這里取值12，可以根據需求更改
N = 12;
% 由于我們要在整個圖像上進行遍歷，因此在沒有Padding補充的情況下，需要考慮邊緣的像素點
for i = const+1 : height - constfor j = const+1 : width - constIp = I(i,j);% 與算法描述相同，根據閾值規定上限下限upper = Ip + t;lower = Ip - t;% 將P周圍的16個像素點的坐標及他們的灰度值，分別保存在coordonne_list 和% values_list 中 coordonne_list = zeros(16,2);values_list = zeros(16,1,"uint8");for k = 1:16coordonne_list(k,:) = List_voisinage(k,:) + [i, j];values_list(k,:) = I(coordonne_list(k,1),coordonne_list(k,2));end% X1向量，用于判斷條件1是否滿足X1 = zeros(16,1); for k = 1:16% 遍歷，給X1向量賦值 0 或 1 的邏輯值X1(k) = values_list(k,1) > upper; end cond1voisins = X1;cond1verifiee = 0;compteur = 0;% 當條件1滿足或數組已經循環平移過整個數組長度16時，結束循環while ~cond1verifiee && (compteur<16)nbVoisinCond1 = sum(cond1voisins(1:N));% 判斷是否N個bool值都是1，即X1前N項和為Ncond1verifiee = (nbVoisinCond1 == N);% cirshift函數用于循環平移數組cond1voisins = circshift(X1,1)';compteur = compteur + 1;end% 滿足條件1的時候，將目標點P的坐標添加進矩陣CSif cond1verifieeCS = [CS;[i,j]]; else% 如果條件1不滿足，則繼續判斷條件2，與條件一大同小異X2 = zeros(16,1);for k = 1:16X2(k) = values_list(k,1) < lower;endcond2voisins = X2;cond2verifiee = 0;compteur = 0;while ~cond2verifiee && (compteur<16)nbVoisinCond2 = sum(cond2voisins(1:N));cond2verifiee = (nbVoisinCond2 == N);cond2voisins = circshift(X1,1)';compteur = compteur + 1;end% 同樣如果滿足了條件2，點P也分類為拐點，將其坐標添加入矩陣CSif cond2verifieeCS = [CS;[i,j]];end end end endend
3. 使用FAST function進行拐點檢測的實驗
I1 = imread("1.JPG");
I1_gray = rgb2gray(I1);
cs1 = FAST(I1_gray,30);
figure()
imagesc(I1)
hold on
plot(cs1(:,2),cs1(:,1),"*")
檢測目標點結果如下 :
在這個實例中，設置了N值為12，閾值t為30。通過調整這兩個變量可以改變提取出的關鍵點的個數。
\newline
\newline
\newline
參考文獻 :
- Rosten, Edward; Reid Porter; Tom Drummond (2010). “FASTER and better: A machine learning approach to corner detection”. IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (1): 105–119. arXiv:0810.2434. doi:10.1109/TPAMI.2008.275. PMID 19926902.
)
)
