图像细化算法.doc

图像细化算法
细化算法有很多，我们在这里介绍的是一种简单而且效果很好的算法，用它就能够实现从文本抽取骨架的功能。我们的对象是白纸黑字的文本，但在程序中为了处理的方便，还是采用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,11,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,00,        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,01,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;i++) //横着走的
{
for(j=1;juff->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;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 * 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;jimageSize.h-1;j++) //竖着走的
{
for(i=1;iimageSize.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;
}