在二值图像处理特别是OCR识别与匹配中，都要通过对字符进行细化以便获得图像的骨架，通过zhang-suen细化算法获得图像，作为图像的特征之一，常用来作为识别或者模式匹配。

一：算法介绍

Zhang-Suen细化算法通常是一个迭代算法，整个迭代过程分为两步：

Step One：循环所有前景像素点，对符合如下条件的像素点标记为删除：

1.      2 <= N(p1) <=6

2.      S(P1) = 1

3.      P2 * P4 * P6 = 0

4.      P4 * P6 * P8 = 0

其中N(p1)表示跟P1相邻的8个像素点中，为前景像素点的个数

S(P1)表示从P2 ～ P9 ～ P2像素中出现0～1的累计次数，其中0表示背景，1表示前景

完整的P1 ～P9的像素位置与举例如下：

其中 N(p1) = 4, S(P1) = 3, P2*P4*P6=0*0*0=0, P4*P6*P8=0*0*1=0, 不符合条件，无需标记为删除。

Step Two：跟Step One很类似，条件1、2完全一致，只是条件3、4稍微不同，满足如下条件的像素P1则标记为删除，条件如下：

1.      2 <= N(p1) <=6

2.      S(P1) = 1

3.      P2 * P4 * P8 = 0

4.      P2 * P6 * P8 = 0

循环上述两步骤，直到两步中都没有像素被标记为删除为止，输出的结果即为二值图像细化后的骨架。

二：代码实现步骤

1.      二值化输入图像，初始化图像像素对应的标记映射数组

BufferedImage binaryImage = super.process(image);		int width = binaryImage.getWidth();		int height = binaryImage.getHeight();		int[] pixels = new int[width*height];		int[] flagmap = new int[width*height];		getRGB(binaryImage, 0, 0, width, height, pixels);		Arrays.fill(flagmap, 0);

2.      迭代细化算法(Zhang-Suen)

a.      Step One

private boolean step1Scan(int[] input, int[] flagmap, int width, int height) {		boolean stop = true;		int bc = 255 - fcolor;		int p1=0, p2=0, p3=0;		int p4=0, p5=0, p6=0;		int p7=0, p8=0, p9=0;		int offset = 0;		for(int row=1; row
    
     >16)&0xff;				if(p1 == bc) continue;				p2 = (input[offset-width+col]>>16)&0xff;				p3 = (input[offset-width+col+1]>>16)&0xff;				p4 = (input[offset+col+1]>>16)&0xff;				p5 = (input[offset+width+col+1]>>16)&0xff;				p6 = (input[offset+width+col]>>16)&0xff;				p7 = (input[offset+width+col-1]>>16)&0xff;				p8 = (input[offset+col-1]>>16)&0xff;				p9 = (input[offset-width+col-1]>>16)&0xff;				// match 1 - 前景像素  0 - 背景像素				p1 = (p1 == fcolor) ? 1 : 0;				p2 = (p2 == fcolor) ? 1 : 0;				p3 = (p3 == fcolor) ? 1 : 0;				p4 = (p4 == fcolor) ? 1 : 0;				p5 = (p5 == fcolor) ? 1 : 0;				p6 = (p6 == fcolor) ? 1 : 0;				p7 = (p7 == fcolor) ? 1 : 0;				p8 = (p8 == fcolor) ? 1 : 0;				p9 = (p9 == fcolor) ? 1 : 0;								int con1 = p2+p3+p4+p5+p6+p7+p8+p9;				String sequence = "" + String.valueOf(p2) + String.valueOf(p3) + String.valueOf(p4) + String.valueOf(p5) +						String.valueOf(p6) + String.valueOf(p7) + String.valueOf(p8) + String.valueOf(p9) + String.valueOf(p2);				int index1 = sequence.indexOf("01");				int index2 = sequence.lastIndexOf("01");								int con3 = p2*p4*p6;				int con4 = p4*p6*p8;								if((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) {					flagmap[offset+col] = 1;					stop = false;				}			}		}		return stop;	}
    

private boolean step2Scan(int[] input, int[] flagmap, int width, int height) {		boolean stop = true;		int bc = 255 - fcolor;		int p1=0, p2=0, p3=0;		int p4=0, p5=0, p6=0;		int p7=0, p8=0, p9=0;		int offset = 0;		for(int row=1; row
    
     >16)&0xff;				if(p1 == bc) continue;				p2 = (input[offset-width+col]>>16)&0xff;				p3 = (input[offset-width+col+1]>>16)&0xff;				p4 = (input[offset+col+1]>>16)&0xff;				p5 = (input[offset+width+col+1]>>16)&0xff;				p6 = (input[offset+width+col]>>16)&0xff;				p7 = (input[offset+width+col-1]>>16)&0xff;				p8 = (input[offset+col-1]>>16)&0xff;				p9 = (input[offset-width+col-1]>>16)&0xff;				// match 1 - 前景像素  0 - 背景像素				p1 = (p1 == fcolor) ? 1 : 0;				p2 = (p2 == fcolor) ? 1 : 0;				p3 = (p3 == fcolor) ? 1 : 0;				p4 = (p4 == fcolor) ? 1 : 0;				p5 = (p5 == fcolor) ? 1 : 0;				p6 = (p6 == fcolor) ? 1 : 0;				p7 = (p7 == fcolor) ? 1 : 0;				p8 = (p8 == fcolor) ? 1 : 0;				p9 = (p9 == fcolor) ? 1 : 0;								int con1 = p2+p3+p4+p5+p6+p7+p8+p9;				String sequence = "" + String.valueOf(p2) + String.valueOf(p3) + String.valueOf(p4) + String.valueOf(p5) +						String.valueOf(p6) + String.valueOf(p7) + String.valueOf(p8) + String.valueOf(p9) + String.valueOf(p2);				int index1 = sequence.indexOf("01");				int index2 = sequence.lastIndexOf("01");								int con3 = p2*p4*p8;				int con4 = p2*p6*p8;								if((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) {					flagmap[offset+col] = 1;					stop = false;				}			}		}		return stop;	}
    

3.      返回细化后的图像，并显示

三：运行效果

四：完整的Zhang-suen算法代码实现：

import java.awt.image.BufferedImage;import java.util.Arrays;public class ZhangSuenThinFilter extends BinaryFilter {	private int fcolor;	public ZhangSuenThinFilter() {		fcolor = 0;	}	public int getFcolor() {		return fcolor;	}	public void setFcolor(int fcolor) {		this.fcolor = fcolor;	}		@Override	public BufferedImage process(BufferedImage image) {		BufferedImage binaryImage = super.process(image);		int width = binaryImage.getWidth();		int height = binaryImage.getHeight();		int[] pixels = new int[width*height];		int[] flagmap = new int[width*height];		getRGB(binaryImage, 0, 0, width, height, pixels);		Arrays.fill(flagmap, 0);						// 距离变化		boolean stop = false;		while(!stop) {			// step one			boolean s1 = step1Scan(pixels, flagmap, width, height);			deletewithFlag(pixels, flagmap);			Arrays.fill(flagmap, 0);			// step two			boolean s2 = step2Scan(pixels, flagmap, width, height);			deletewithFlag(pixels, flagmap);			Arrays.fill(flagmap, 0);			if(s1 && s2) {				stop = true;			}		}		// 结果		BufferedImage bi = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);		setRGB(bi, 0, 0, width, height, pixels);		return bi;	}		private void deletewithFlag(int[] pixels, int[] flagmap) {		int bc = 255 - fcolor;		for(int i=0; i
    
     << 24) | ((bc&0xff) << 16) | ((bc&0xff) << 8) | (bc&0xff);			}		}			}	private boolean step1Scan(int[] input, int[] flagmap, int width, int height) {		boolean stop = true;		int bc = 255 - fcolor;		int p1=0, p2=0, p3=0;		int p4=0, p5=0, p6=0;		int p7=0, p8=0, p9=0;		int offset = 0;		for(int row=1; row
     
      >16)&0xff;				if(p1 == bc) continue;				p2 = (input[offset-width+col]>>16)&0xff;				p3 = (input[offset-width+col+1]>>16)&0xff;				p4 = (input[offset+col+1]>>16)&0xff;				p5 = (input[offset+width+col+1]>>16)&0xff;				p6 = (input[offset+width+col]>>16)&0xff;				p7 = (input[offset+width+col-1]>>16)&0xff;				p8 = (input[offset+col-1]>>16)&0xff;				p9 = (input[offset-width+col-1]>>16)&0xff;				// match 1 - 前景像素  0 - 背景像素				p1 = (p1 == fcolor) ? 1 : 0;				p2 = (p2 == fcolor) ? 1 : 0;				p3 = (p3 == fcolor) ? 1 : 0;				p4 = (p4 == fcolor) ? 1 : 0;				p5 = (p5 == fcolor) ? 1 : 0;				p6 = (p6 == fcolor) ? 1 : 0;				p7 = (p7 == fcolor) ? 1 : 0;				p8 = (p8 == fcolor) ? 1 : 0;				p9 = (p9 == fcolor) ? 1 : 0;								int con1 = p2+p3+p4+p5+p6+p7+p8+p9;				String sequence = "" + String.valueOf(p2) + String.valueOf(p3) + String.valueOf(p4) + String.valueOf(p5) +						String.valueOf(p6) + String.valueOf(p7) + String.valueOf(p8) + String.valueOf(p9) + String.valueOf(p2);				int index1 = sequence.indexOf("01");				int index2 = sequence.lastIndexOf("01");								int con3 = p2*p4*p6;				int con4 = p4*p6*p8;								if((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) {					flagmap[offset+col] = 1;					stop = false;				}			}		}		return stop;	}		private boolean step2Scan(int[] input, int[] flagmap, int width, int height) {		boolean stop = true;		int bc = 255 - fcolor;		int p1=0, p2=0, p3=0;		int p4=0, p5=0, p6=0;		int p7=0, p8=0, p9=0;		int offset = 0;		for(int row=1; row
      
       >16)&0xff;				if(p1 == bc) continue;				p2 = (input[offset-width+col]>>16)&0xff;				p3 = (input[offset-width+col+1]>>16)&0xff;				p4 = (input[offset+col+1]>>16)&0xff;				p5 = (input[offset+width+col+1]>>16)&0xff;				p6 = (input[offset+width+col]>>16)&0xff;				p7 = (input[offset+width+col-1]>>16)&0xff;				p8 = (input[offset+col-1]>>16)&0xff;				p9 = (input[offset-width+col-1]>>16)&0xff;				// match 1 - 前景像素  0 - 背景像素				p1 = (p1 == fcolor) ? 1 : 0;				p2 = (p2 == fcolor) ? 1 : 0;				p3 = (p3 == fcolor) ? 1 : 0;				p4 = (p4 == fcolor) ? 1 : 0;				p5 = (p5 == fcolor) ? 1 : 0;				p6 = (p6 == fcolor) ? 1 : 0;				p7 = (p7 == fcolor) ? 1 : 0;				p8 = (p8 == fcolor) ? 1 : 0;				p9 = (p9 == fcolor) ? 1 : 0;								int con1 = p2+p3+p4+p5+p6+p7+p8+p9;				String sequence = "" + String.valueOf(p2) + String.valueOf(p3) + String.valueOf(p4) + String.valueOf(p5) +						String.valueOf(p6) + String.valueOf(p7) + String.valueOf(p8) + String.valueOf(p9) + String.valueOf(p2);				int index1 = sequence.indexOf("01");				int index2 = sequence.lastIndexOf("01");								int con3 = p2*p4*p8;				int con4 = p2*p6*p8;								if((con1 >= 2 && con1 <= 6) && (index1 == index2) && con3 == 0 && con4 == 0) {					flagmap[offset+col] = 1;					stop = false;				}			}		}		return stop;	}}