1、图像细化算法 细化算法有很多，我们在这里介绍的是一种简单而且效果很好的算法，用它就能够实现从文本抽取骨架 的功能。我们的对象是白纸黑字的文本，但在程序中为了处理的方便，还是采用 256 级灰度图，不过只用到 了调色板中 0 和 255 两项。 所谓细化，就是从原来的图中去掉一些点，但仍要保持原来的形状。实际上，是保持原图的骨架。所谓 骨架，可以理解为图象的中轴，例如一个长方形的骨架是它的长方向上的中轴线；正方形的骨架是它的中心 点；圆的骨架是它的圆心，直线的骨架是它自身，孤立点的骨架也是自身。文本的骨架嘛，前言中的例子显 示的很明白。那么怎样判断一个点是否能去掉呢？显然，要根据它的八个相邻点的
2、情况来判断，我们给几个 例子。 图 22. 根据某点的八个相邻点的情况来判断该点是否能删除 图 22 中，(1)不能删，因为它是个内部点，我们要求的是骨架，如果连内部点也删了，骨架也会被掏空 的；（2）不能删，和（1）是同样的道理；（3）可以删，这样的点不是骨架；（4）不能删，因为删掉后， 原来相连的部分断开了；（5）可以删，这样的点不是骨架；（6）不能删，因为它是直线的端点，如果这样 的点删了，那么最后整个直线也被删了，剩不下什么；（7）不能删，因为孤立点的骨架就是它自身。 总结一下，有如下的判据：1.内部点不能删除；2.孤立点不能删除；3.直线端点不能删除 4.如果 P 是 边界点，去掉
3、P 后，如果连通分量不增加，则 P 可以删除。 我们可以根据上述的判据，事先做出一张表，从 0 到 255 共有 256 个元素，每个元素要么是 0，要么是 1。我们根据某点（当然是要处理的黑色点了）的八个相邻点的情况查表，若表中的元素是 1，则表示该点 可删，否则保留。查表的方法是，设白点为 1，黑点为 0；左上方点对应一个 8 位数的第一位（最低位）， 正上方点对应第二位，右上方点对应的第三位，左邻点对应第四位，右邻点对应第五位，左下方点对应第六 位，正下方点对应第七位，右下方点对应的第八位，按这样组成的 8 位数去查表即可。 例如上面的例子中(1)对应表中的第 0 项，该项应该为 0；（
4、2）对应 37，该项应该为 0；（3）对应 173，该项应该为 1；（4）对应 231，该项应该为 0；（5）对应 237，该项应该为 1；（6）对应 254，该项 应该为 0；（7）对应 255，该项应该为 0。 这张表我已经替大家做好了，哇，花了我不少时间呢。 static int erasetable256= 0,0,1,1,0,0,1,1, 1,1,0,1,1,1,0,1, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,1, 0,0,1,1,0,0,1,1, 1,1,0,1,1,1,0,1, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,1, 1,1,0
5、,0,1,1,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 1,1,0,0,1,1,0,0, 1,1,0,1,1,1,0,1, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,1,1,0,0,1,1, 1,1,0,1,1,1,0,1, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,1, 0,0,1,1,0,0,1,1, 1,1,0,1,1,1,0,1, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,0, 1,1,0,0,1,1,0,0, 0,0,0,0,0,0,0,0,
6、 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,0, 1,1,0,0,1,1,0,0, 1,1,0,1,1,1,0,0, 1,1,0,0,1,1,1,0, 1,1,0,0,1,0,0,0 ; 有了这张表，算法就很简单了，每次对一行一行的将整个图象扫描一遍，对于每个点（不包括边界点）， 计算它对应在表中的索引，若为 0，则保留，否则删除该点。如果这次扫描没有一个点被删除，则循环结束， 剩下的点就是骨架点，如果有点被删除，则进行新的一轮扫描，如此反复，直到没有点被删除为止。 实际上，该算法有一些缺陷。举个简单的例子，有一个黑色矩形 经过细化后，我们预期的结果是一条水平直线，且位于该
7、黑色矩形的中心，实际的结果确实是一条水平 直线，但不是位于黑色矩形的中心，而是最下面的一条边。为什么会这样，我们来分析一下：在从上到下， 从左到右的扫描过程中，我们遇到的第一个黑点就是黑色矩形的左上角点，经查表，该点可以删。下一个点 是它右边的点，经查表，该点也可以删，如此下去，整个一行被删了。每一行都是同样的情况，所以都被删 除了。到了最后一行时，黑色矩形已经变成了一条直线，最左边的黑点不能删，因为它是直线的端点，它右 边的点也不能删，因为如果删除，直线就断了，如此下去，直到最右边的点，也不能删，因为它是直线的右 端点。所以最下面的一条边保住了，但这并不是我们希望的结果。 解决的办法是，在每
8、一行水平扫描的过程中，先判断每一点的左右邻居，如果都是黑点，则该点不做处 理，另外，如果某个黑点被删除了，那么跳过它的右邻居，处理下一个点。这样就避免了上述的问题。 解决了上面的问题，我们来看看处理后的结果。 这次变成一小段竖线了，还是不对，是不是很沮丧？别着急，让我们再来分析一下：在上面的算法中， 我们遇到的第一个能删除的点就是黑色矩形的左上角点，第二个是第一行的最右边的点，即黑色矩形的右上 角点，第三个是第二行的最左边的点，第四个是第二行的最右边的点整个图象处理这样一次后，宽度减 少 2。每次都是如此，直到剩最中间一列，就不能再删了。为什么会这样呢？原因是这样的处理过程只实现 了水平细化，
9、如果在每一次水平细化后，再进行一次竖直方向的细化（只要把上述过程的行列换一下），就 可以了。 这样一来，每处理一次，删除点的顺序变成：（先是水平方向扫描）第一行最左边的点；第一行最右边 的点；第二行最左边的点；第二行最右边的点最后一行最左边的点；最后一行最右边的点；(然后是竖 直方向扫描)第二列最上边的点（因为第一列最上边的点已被删除）；第二列最下边的点；第三列最上边的 点；第三列最下边的点倒数第二列最上边的点（因为倒数第一列最上边的点已被删除）；倒数第二列最 下边的点。我们发现，刚好剥掉了一圈，这也正是细化要做的事。 /灰度化之后，进行/ unsigned char* Thinning(GP
10、tr globals,unsigned char *Gray) bool finish=false; unsigned char* wn=NULL; unsigned char* n=NULL; unsigned char* en=NULL; unsigned char* w=NULL; unsigned char* e=NULL; unsigned char* ws=NULL; unsigned char* s=NULL; unsigned char* es=NULL; int i,j; int32 filterSize = gStuff-imageSize.v*gStuff-imageSi
11、ze.h; static int erasetable256 = 0,0,1,1,0,0,1,1, 1,1,0,1,1,1,0,1, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,1, 0,0,1,1,0,0,1,1, 1,1,0,1,1,1,0,1, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,1, 1,1,0,0,1,1,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 1,1,0,0,1,1,0,0, 1,1,0,1,1,1,0,1, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,
12、0,0, 0,0,1,1,0,0,1,1, 1,1,0,1,1,1,0,1, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,1, 0,0,1,1,0,0,1,1, 1,1,0,1,1,1,0,1, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,0, 1,1,0,0,1,1,0,0, 0,0,0,0,0,0,0,0, 1,1,0,0,1,1,1,1, 0,0,0,0,0,0,0,0, 1,1,0,0,1,1,0,0, 1,1,0,1,1,1,0,0, 1,1,0,0,1,1,1,0, 1,1,0,0,1,0,0,0 ; for(i=1;iimageSize.v-1
13、;i+) /横着走的 for(j=1;jimageSize.h-1;j+) if(*(Gray+(gStuff-imageSize.h*i)+j)!=255) *(Gray+(i*gStuff-imageSize.h)+j)=(BYTE)0;/将所有非白的像素变为纯黑 while(!finish) int bool1=0,bool2=0; for(i=1;iimageSize.v-1;i+) /横着走的 for(j=1;jimageSize.h-1;j+) if(*(Gray+(gStuff-imageSize.h*i)+j)=0) / unsigned char *g = Gray + (g
14、Stuff-imageSize.h * i) + j; / *(Gray+(i*gStuff-imageSize.h)+j)=(BYTE)0; w = Gray + (i * gStuff-imageSize.h) + j - 1; e = Gray + (i * gStuff-imageSize.h) + j + 1; wn = Gray + (i * gStuff-imageSize.h) + j - gStuff-imageSize.h - 1; n = Gray + (i * gStuff-imageSize.h) + j - gStuff-imageSize.h ; en = Gra
15、y + (i * gStuff-imageSize.h) + j - gStuff-imageSize.h + 1; ws = Gray + (i * gStuff-imageSize.h) + j + gStuff-imageSize.h - 1; s = Gray + (i * gStuff-imageSize.h) + j + gStuff-imageSize.h ; es = Gray + (i * gStuff-imageSize.h) + j + gStuff-imageSize.h + 1; int sum=0; if(*w = 255 | *e = 255) sum=(*es)
16、/255*(128)+(*s)/255*(64)+(*ws)/255*(32)+(*e)/255*(16)+ (*w)/255*(8)+(*en)/255*(4)+(*n)/255*(2)+(*wn)/255*(1); if(erasetablesum=1) *(Gray+(i*gStuff-imageSize.h)+j)=(BYTE)255; bool1=1; j+; for(j=1;jimageSize.h-1;j+) /竖着走的 for(i=1;iimageSize.v-1;i+) /unsigned char *g2 = Gray + (gStuff-imageSize.h * i)
17、+ j; /if( *g2 = 0) if(*(Gray+(i*gStuff-imageSize.h)+j)=0) / unsigned char *g2 = Gray + (i * gStuff-imageSize.h) + j; int sum=0; w=Gray+(i*gStuff-imageSize.h)+j-1; e=Gray+(i*gStuff-imageSize.h)+j+1; wn=Gray+(i*gStuff-imageSize.h)+j-gStuff-imageSize.h-1; n=Gray+(i*gStuff-imageSize.h)+j-gStuff-imageSiz
18、e.h; en=Gray+(i*gStuff-imageSize.h)+j-gStuff-imageSize.h+1; ws=Gray+(i*gStuff-imageSize.h)+j+gStuff-imageSize.h-1; s=Gray+(i*gStuff-imageSize.h)+j+gStuff-imageSize.h; es=Gray+(i*gStuff-imageSize.h)+j+gStuff-imageSize.h+1; if(*n=255|*s=255) sum=(*es)/255*(128)+(*s)/255*(64)+(*ws)/255*(32)+(*e)/255*(16)+ (*w)/255*(8)+(*en)/255*(4)+(*n)/255*(2)+(*wn)/255*(1); if(erasetablesum=1) *(Gray+(i*gStuff-imageSize.h)+j)=(BYTE)255; bool2=1; i+; if(bool1=0 return Gray;
