在二值图像处理特别是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<height-1; row++) { offset = row*width; for(int col=1; col<width-1; col++) { p1 = (input[offset+col]>>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; }
b. Step Two
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<height-1; row++) { offset = row*width; for(int col=1; col<width-1; col++) { p1 = (input[offset+col]>>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; }
c. 检查如果上述两部没有任何像素被标记，则停止迭代，否则继续执行a, b
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<pixels.length; i++) { if(flagmap[i] == 1) { pixels[i] = (0xff << 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<height-1; row++) { offset = row*width; for(int col=1; col<width-1; col++) { p1 = (input[offset+col]>>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<height-1; row++) { offset = row*width; for(int col=1; col<width-1; col++) { p1 = (input[offset+col]>>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; } }
觉得不错请支持一下！
