二值图像的骨架提取

  本文介绍的二值图像细化算法是来自 T.Y. Zhang and C.Y. Suen 1984 年发表的论文 “A fast parallel algorithm for thinning digital patterns” 中所介绍的算法。

算法介绍

我们先进行如下定义：

P1 为我们要判断是否删去的点，则对其 8 邻域分别按照上图顺序标记为 P2 P3 P4 P5 P6 P7 P8 P9；
B(P1) 为 P1 8 邻域值为 1（图像为 0-1 二值图）的点，即：

B(P1)=P2+P3+P4+P5+P6+P7+P8+P9

A(P1) 为 P1 8 领域按照上图排序时（P9 后面接 P2），序列 0-1 的个数：

若 P1 8 邻域的值如上图所示，则有 A（P1）= 2。

我们遍历图像的每个点，对每个像素为 1 的点做如下判断：
1. 2<=B(P1)<=6
2. A(P1)=1
3. 当为奇数次迭代时，判断 P2∗P4∗P6=0,P4∗P6∗P8=0 ；当为偶数次迭代时，判断 P2∗P4∗P8=0,P2∗P6∗P8=0
如果满足上述条件，则删除该点。
循环遍历图像，直至没有点被删除。

算法流程

while point are deleted :
for P1 in all pixels :
if ((1)P1=1 
           (2)2<=B(P1)<=6
           (3)A(P1)=1
           (4)in odd iterations:
              P2*P4*P6=0 && P4*P6*P8=0
              in even iterations:
              P2*P4*P8=0 && P2*P6*P8=0)
delete P1
    end for
end while

代码

void zhangSkeleton(Mat &srcimage)
{
    int kernel[9];
    int nl = srcimage.rows;
    int nc = srcimage.cols;
    vector<Point> delete_list;
    int A, B;
while (true)
    {
        for (int j = 1; j < nl - 1; j++)
        {
            uchar* data_pre = srcimage.ptr<uchar>(j - 1);
            uchar* data = srcimage.ptr<uchar>(j);
            uchar* data_next = srcimage.ptr<uchar>(j + 1);
            for (int i = 1; i < (nc - 1); i++)
            {
if (data[i] == 255)
                {
                    kernel[0] = 1;
if (data_pre[i] == 255) kernel[1] = 1;
else  kernel[1] = 0;
if (data_pre[i + 1] == 255) kernel[2] = 1;
else  kernel[2] = 0;
if (data[i + 1] == 255) kernel[3] = 1;
else  kernel[3] = 0;
if (data_next[i + 1] == 255) kernel[4] = 1;
else  kernel[4] = 0;
if (data_next[i] == 255) kernel[5] = 1;
else  kernel[5] = 0;
if (data_next[i - 1] == 255) kernel[6] = 1;
else  kernel[6] = 0;
if (data[i - 1] == 255) kernel[7] = 1;
else  kernel[7] = 0;
if (data_pre[i - 1] == 255) kernel[8] = 1;
else  kernel[8] = 0;

                    B=0;
                    for (int k = 1; k < 9; k++)
                    {
                        B = B + kernel[k];
                    }
if ((B >= 2) && (B <= 6))
                    {
A = 0;
if (!kernel[1] && kernel[2]) A++;
if (!kernel[2] && kernel[3]) A++;
if (!kernel[3] && kernel[4]) A++;
if (!kernel[4] && kernel[5]) A++;
if (!kernel[5] && kernel[6]) A++;
if (!kernel[6] && kernel[7]) A++;
if (!kernel[7] && kernel[8]) A++;
if (!kernel[8] && kernel[1]) A++;
                        //
if (A == 1)
                        {
if ((kernel[1] * kernel[3] * kernel[5] == 0) 
                            && (kernel[3] * kernel[5] * kernel[7] == 0))
                            {
                                delete_list.push_back(Point(i, j));
                            }
                        }
                    }               
                }
            }
        }
        int size = delete_list.size();
if (size == 0)
        {
break;
        }
        for (int n = 0; n < size; n++)
        {
            Point tem;
            tem = delete_list[n];
            uchar* data = srcimage.ptr<uchar>(tem.y);
            data[tem.x] = 0;
        }
        delete_list.clear();
        for (int j = 1; j < nl - 1; j++)
        {
            uchar* data_pre = srcimage.ptr<uchar>(j - 1);
            uchar* data = srcimage.ptr<uchar>(j);
            uchar* data_next = srcimage.ptr<uchar>(j + 1);
            for (int i = 1; i < (nc - 1); i++)
            {
if (data[i] == 255)
                {
                    kernel[0] = 1;
if (data_pre[i] == 255) kernel[1] = 1;
else  kernel[1] = 0;
if (data_pre[i + 1] == 255) kernel[2] = 1;
else  kernel[2] = 0;
if (data[i + 1] == 255) kernel[3] = 1;
else  kernel[3] = 0;
if (data_next[i + 1] == 255) kernel[4] = 1;
else  kernel[4] = 0;
if (data_next[i] == 255) kernel[5] = 1;
else  kernel[5] = 0;
if (data_next[i - 1] == 255) kernel[6] = 1;
else  kernel[6] = 0;
if (data[i - 1] == 255) kernel[7] = 1;
else  kernel[7] = 0;
if (data_pre[i - 1] == 255) kernel[8] = 1;
else  kernel[8] = 0;

                    B = 0;
                    for (int k = 1; k < 9; k++)
                    {
                        B = B + kernel[k];
                    }
if ((B >= 2) && (B <= 6))
                    {
A = 0;
if (!kernel[1] && kernel[2]) A++;
if (!kernel[2] && kernel[3]) A++;
if (!kernel[3] && kernel[4]) A++;
if (!kernel[4] && kernel[5]) A++;
if (!kernel[5] && kernel[6]) A++;
if (!kernel[6] && kernel[7]) A++;
if (!kernel[7] && kernel[8]) A++;
if (!kernel[8] && kernel[1]) A++;
                        //
if (A == 1)
                        {
if ((kernel[1] * kernel[3] * kernel[7] == 0) 
                            && (kernel[1] * kernel[5] * kernel[7] == 0))
                            {
                                delete_list.push_back(Point(i, j));
                            }
                        }
                    }
                }
            }
        }
if (size == 0)
        {
break;
        }
        for (int n = 0; n < size; n++)
        {
            Point tem;
            tem = delete_list[n];
            uchar* data = srcimage.ptr<uchar>(tem.y);
            data[tem.x] = 0;
        }
        delete_list.clear();
    }
}

测试