图像细化算法.doc_咨信网zixin.com.cn

资源描述

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

展开阅读全文