《图像细化算法》由会员分享，可在线阅读，更多相关《图像细化算法（5页珍藏版）》请在金锄头文库上搜索。
1、图像细化算法细化算法有很多，我们在这里介绍的是一种简单而且效果很好的算法，用它就能够实现从文本抽取骨架的功能。我们的对象是白纸黑字的文本，但在程序中为了处理的方便，还是采用256级灰度图，不过只用到了调色板中0和255两项。 所谓细化，就是从原来的图中去掉一些点，但仍要保持原来的形状。实际上，是保持原图的骨架。所谓骨架，可以理解为图象的中轴，例如一个长方形的骨架是它的长方向上的中轴线；正方形的骨架是它的中心点；圆的骨架是它的圆心，直线的骨架是它自身，孤立点的骨架也是自身。文本的骨架嘛，前言中的例子显示的很明白。那么怎样判断一个点是否能去掉呢？显然，要根据它的八个相邻点的情况来判断，我们给几个例
2、子。图22. 根据某点的八个相邻点的情况来判断该点是否能删除图22中，(1)不能删，因为它是个内部点，我们要求的是骨架，如果连内部点也删了，骨架也会被掏空的；（2）不能删，和（1）是同样的道理；（3）可以删，这样的点不是骨架；（4）不能删，因为删掉后，原来相连的部分断开了；（5）可以删，这样的点不是骨架；（6）不能删，因为它是直线的端点，如果这样的点删了，那么最后整个直线也被删了，剩不下什么；（7）不能删，因为孤立点的骨架就是它自身。总结一下，有如下的判据：1.内部点不能删除；2.孤立点不能删除；3.直线端点不能删除4.如果P是边界点，去掉P后，如果连通分量不增加，则P可以删除。 我们可以根据
3、上述的判据，事先做出一张表，从0到255共有256个元素，每个元素要么是0，要么是1。我们根据某点（当然是要处理的黑色点了）的八个相邻点的情况查表，若表中的元素是1，则表示该点可删，否则保留。查表的方法是，设白点为1，黑点为0；左上方点对应一个8位数的第一位（最低位），正上方点对应第二位，右上方点对应的第三位，左邻点对应第四位，右邻点对应第五位，左下方点对应第六位，正下方点对应第七位，右下方点对应的第八位，按这样组成的8位数去查表即可。例如上面的例子中(1)对应表中的第0项，该项应该为0；（2）对应37，该项应该为0；（3）对应173，该项应该为1；（4）对应231，该项应该为0；（5）对应2
4、37，该项应该为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,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
5、,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, 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,
6、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(GPtr globals,unsigned char *Gray)bool finish=false;unsigned char* wn=NULL;unsigned char* n=NULL;u
10、nsigned 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-imageSize.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,
11、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,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
12、,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;i+) /横着走的for(j=1;jimageSize.h-1;j+)if(*(Gray+(gStuff-imageSize.h*i)+j)!=255)*(Gray+(i*gStuff-imageSize.h)+j)=(BYTE)0;/将所有非白
13、的像素变为纯黑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 + (gStuff-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 = Gray + (i * g
