FAST角点检测算法简介与实现

发表于   |   分类于   |  

算法原理

对于一个像素$P$，它的亮度值设为$I_P$。
设定一个合适的阈值$t$。
考虑以该像素点为中心的一个半径等于3像素的离散化的Bresenham圆，这个圆的边界上有16个像素（如下图所示）。

现在，如果在这个大小为16个像素的圆上有$n$个连续的像素点，它们的像素值要么都比$I_P+t$大，要么都比$I_P-t$小，那么它就是一个角点。$n$的值可以设置为12或者9，实验证明选择9可能会有更好的效果。

上面的算法中，对于图像中的每一个点，我们都要去遍历其邻域圆上的16个点的像素，效率较低。我们下面提出了一种高效的测试（high-speed test）来快速排除一大部分非角点的像素。该方法仅仅检查在位置1，9，5和13四个位置的像素，首先检测位置1和位置9，如果它们都比阈值暗或比阈值亮，再检测位置5和位置13。如果$P$是一个角点，那么上述四个像素点中至少有3个应该必须都大于$I_P+t$或者小于$I_P-t$，因为若是一个角点，超过四分之三圆的部分应该满足判断条件。如果不满足，那么pp不可能是一个角点。对于所有点做上面这一部分初步的检测后，符合条件的将成为候选的角点，我们再对候选的角点，做完整的测试，即检测圆上的所有点。

Matlab代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
function [ corners ] = myfast9( image , threshold )
[m,n]=size(image);
corner_cnt=0;
precorners=zeros(0,2);
corners_map=zeros(m,n);
scores=zeros(0,0);
scores_map=zeros(m,n);
%% FAST角点提取
for i=4:m-3
    
    for j=4:n-3
        
        p=image(i,j);
        
        count=0;
        score=0.0;
        
        p1=image(i-3,j);
        p9=image(i+3,j);
        
        if( abs(p1-p) > threshold)
            count = count+1;
            score=score+abs(p1-p);
        end
        if(abs(p9-p) > threshold)
            count = count+1;
            score=score+abs(p9-p);
        end
        
        if(count==0)
            continue;
        end
        
        p5=image(i,j+3);
        p13=image(i,j-3);
        
        if( abs(p5-p) > threshold)
            count = count+1;
            score=score+abs(p5-p);
        end
        if(abs(p13-p) > threshold)
            count = count+1;
            score=score+abs(p13-p);
        end
        
        if(count<3)
            continue;
        end
        
        p2=image(i-3,j+1);
        p3=image(i-2,j+2);
        p4=image(i-1,j+3);
        
        p6=image(i+1,j+3);
        p7=image(i+2,j+2);
        p8=image(i+3,j+1);
        
        p10=image(i+3,j-1);
        p11=image(i+2,j-2);
        p12=image(i+1,j-3);
        
        p14=image(i-1,j-3);
        p15=image(i-2,j-2);
        p16=image(i-3,j-3);
        
        if( abs(p2-p) > threshold)
            count = count+1;
            score=score+abs(p2-p);
        end
        if(abs(p3-p) > threshold)
            count = count+1;
            score=score+abs(p3-p);
        end
        if(abs(p4-p) > threshold)
            count = count+1;
            score=score+abs(p4-p);
        end
        if(abs(p6-p) > threshold)
            count = count+1;
            score=score+abs(p6-p);
        end
        if(abs(p7-p) > threshold)
            count = count+1;
            score=score+abs(p7-p);
        end
        if(abs(p8-p) > threshold)
            count = count+1;
            score=score+abs(p8-p);
        end
        if(abs(p10-p) > threshold)
            count = count+1;
            score=score+abs(p10-p);
        end
        if(abs(p11-p) > threshold)
            count = count+1;
            score=score+abs(p11-p);
        end
        if(abs(p12-p) > threshold)
            count = count+1;
            score=score+abs(p12-p);
        end
        if(abs(p14-p) > threshold)
            count = count+1;
            score=score+abs(p14-p);
        end
        if(abs(p15-p) > threshold)
            count = count+1;
            score=score+abs(p15-p);
        end
        if(abs(p16-p) > threshold)
            count = count+1;
            score=score+abs(p16-p);
        end
        
        % FAST9
        if(count<9)
            continue;
        end
        
        corner_cnt=corner_cnt+1;
        precorners(corner_cnt,1)=i;
        precorners(corner_cnt,2)=j;
        corners_map(i,j)=1;
        
        scores_map(i,j)=score;
        
        scores(corner_cnt)=score;
        
    end
    
end
%% 非极大值抑制
new_cnt=0;
for k=1:corner_cnt
    i=precorners(k,1);
    j=precorners(k,2);
    ts=scores(k);
    
    ok=1;
    
    for p=i-2:i+2
        for q=j-2:j+2
            if(scores_map(p,q) > ts)
                ok=0;
                break;
            end  
        end
        if(ok==0)
            break;
        end
    end
    
    if(ok==1)
        new_cnt=new_cnt+1;
        corners(new_cnt,1)=j;
        corners(new_cnt,2)=i;
    end
    
end
end

FAST9（阈值40）

坚持原创技术分享，您的支持将鼓励我继续创作！