二值图像的细化是讨论将一个图像中的黑色部分沿着它的中心轴线将其细化为一个像素宽的线条的处理过程,细化的结果能基本保留图形中黑色部分的拓扑结构。图像细化是图像模式识别的关键步骤。快速细化算法的思想是优化了原细化算法中由边界逐层消除黑色像素点的过程,提高细化效率。
细化前 细化后(灰色为去除点)
细化算法
本算法基于逐层剥取理念,快速细化算法改进了反复扫描的过程,顺序、逆序搜索两次,确定每个点的层数,通过层数可判断该点属于边界点还是骨架, 因而优化算法的效率,大量减少程序运算时间。
算法步骤:
假设黑色值为1,白色为0.
第一步,从上到下,从左到右依次扫描每一个点,若当前点(x,y)为黑点时,需判断其右上、上、左上和左四点的情况。(x-1,y+1) (x-1,y) (x-1,y-1) (x,y-1) 这四点可以理解为当前点是被该四点包围,该点层数即四点层数最小值多一层;如果当前点(x,y)为白色,层数值赋为0。
第二步,自下而上,自右而左,与第一步相似的判断每个点的状态,若当前点是黑点,于是判断其左下、下、右下和右四点的情况(图6)。(x+1,y-1) (x+1,y) (x+1,y+1) (x,y+1)四点包围了当前点,同样取这四点层数的最小值加1 作为该点层数值;如果当前点(x,y)为白色,层数值赋为0。
与此同时,既然已经求得每一个点上包围层数值和下包围层数值,每个点的实际层数其实就是两种层数值中最小值(图7)。
M[x][y]=Min(F[x][y],G[x][y])
第三步,从上到下,从左到右依次扫描每一个点,此时需要判断该点8 方向(图7)范围内所有点层数的情况。如果当前点的层数值是周围相邻点中最大,该点即保留;如果当前点的层数值并非最大,该点即可删去。
M[x][y]==Max(M[x+i][y+i]│(-1<=i,j<=1))? 保留:删去
综上步骤,即完成了该图像细化的全部过程,算法只需遍历3 次,就能将一幅图像进行快速细化。
MATLAB代码
%二值化
binary=imread('PIC_NAME');
[high,weight]=size(binary);
F=zeros(high,weight);
G=zeros(high,weight);
M=zeros(high,weight);
out=zeros(high,weight);
for i=2:high-1
for j=2:weight-1
if binary(i,j)==0
F(i,j)=0;
else
mi=[F(i,j-1),F(i-1,j-1),F(i-1,j),F(i-1,j+1)];
F(i,j)=min(mi)+1;
end
end
end
for i=high-1:-1:2
for j=weight-1:-1:2
if binary(i,j)==0
G(i,j)=0;
else
mi=[G(i+1,j-1),G(i+1,j),G(i+1,j+1),G(i,j+1)];
G(i,j)=min(mi)+1;
end
end
end
for i=2:high-1
for j=2:weight-1
mi=[F(i,j),G(i,j)];
M(i,j)=min(mi);
end
end
for i=2:high-1
for j=2:weight-1
ma=[M(i,j-1),M(i-1,j-1),M(i-1,j),M(i-1,j+1),M(i+1,j-1),M(i+1,j),M(i+1,j+1),M(i,j+1)];
if M(i,j)==max(ma)
out(i,j)=M(i,j);
else
out(i,j)=0;
end
end
end
imshow(out);