轮廓追踪与C#实现

           轮廓追踪是图像处理中常见的方法，主要目的是追踪二值图像中目标物体的外轮廓，所得结果为单像素闭合轮廓。

流       程：

                   1. 确定种子点，即追踪的起始像素(如最左上方在轮廓上的像素点)；                   

                   2. 以相应的追踪规则搜索外部轮廓点。

追踪规则：以种子点为起点，按某以确定方向（如顺时针）寻找与当前轮廓点相邻（8邻域）的轮廓点（第一个相邻），再以 此点为当前轮廓点按照前述方法搜索，直到最后搜索到 的点与种子点相同为止。

注        意：搜索过程中，下一次搜索的起始方向，是上一次搜索到当前像素方向的逆时针45度方向（如果搜索方向是顺时针）。如当前像素在上个轮廓像素的右邻域，那么当前像素可以从其右上角方向搜索，因为这时其上邻域必不是轮廓像素。这样做可以减少算法的计算量。

      追踪过程如图1所示：其中红色点表示种子点，黑色点表示轮廓点，蓝色点表示目标物体内部点,搜索方向是顺时针。

      我的代码中dircection是搜索方向，定义如下：

      int[,] direction = new int[8, 2] { { -1, 0 }, { -1, +1 }, { 0, +1 }, { +1, +1 }, { +1, 0 }, { +1, -1 }, { 0, -1 }, { -1, -1 } };

      在代码中的abrect是一个矩形对象，指的是追踪目标所在矩形，这是我原来代码中要用的东西，和这个算法没有关系。

                                 

                                                                        图1.追踪过程图示

C#实现：

unsafe protected void TraceContour(byte* imagedata, int wid, int hei)
        {
            int stride = (wid + 3) / 4 * 4;
            int offset = stride - wid;

            List<Point> ContourPoints = new List<Point>();
            
            bool bfindstartpoint = false;
            int ss = 0;
            byte* p = null;
            for (int i = 0; i < hei; i++)
            {
                imagedata[i * stride] = 0;
                imagedata[i * stride + wid - 1] = 0;
            }
            for (int i = 0; i < wid; i++)
            {
                imagedata[i] = 0;
                imagedata[(hei - 1) * stride + i] = 0;
            }
            //寻找种子点
            for (int i = 1; i < hei - 1; i++)
            {
                p = imagedata + i * stride;
                for (int j = 1; j < wid - 1; j++)
                {
                    if (p[j] == 255 && (p[j + 1] + p[j - 1] + p[j - stride] + p[j + stride] + p[j + stride - 1] + p[stride + j + 1] + p[j - stride - 1] + p[j 

- stride + 1] != 0))
                    {
                        bfindstartpoint = true;
                        ss = i * stride + j;
                        break;
                    }
                }
                if (bfindstartpoint)
                {
                    break;
                }
            }

            //寻找种子点失败
            if (!bfindstartpoint)
                return ;

            //搜索方向
            /*
             * 7 0 1
             * 6 + 2
             * 5 4 3
             */           
            int begindirect = 0;//从0开始顺时针搜索
            int kk = ss;
            int k = 0;
            int bb = 0;
            bool bfindpoint = false;
            Point pt = new Point();

            while (bfindstartpoint)
            {
                bfindpoint = false;
                k = begindirect;
                while (!bfindpoint)
                {
                    bb = kk;
                    kk += (stride * direction[k, 0] + direction[k, 1]);
                    int ih = kk / stride;
                    int iw = kk % stride;
                    //如果只有一点会死循环
                    //如果超出边界
                    if (ih == hei || iw == wid || kk < ss || (kk >= stride * hei))
                    {
                        k++;
                        kk = bb;
                        if (k == 8)
                            k = 0;
                    }
                    else if (imagedata[kk] == 255)
                    {
                        //还原到原坐标系
                        pt.X = iw + abrect.X;
                        pt.Y = ih + abrect.Y;
                        ContourPoints.Add(pt);
                        if (kk == ss)
                            bfindstartpoint = false;
                        begindirect = (k + 7) % 8;//逆时针旋转45度
                        bfindpoint = true;
                    }
                    else
                    {
                        kk = bb;
                        k++;
                        if (k == 8)
                            k = 0;
                    }
                }
            }
        }