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代码

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）