[Happy DSA] 图像的contour trace算法C++实现

分类： C++语言 编程应用 数据结构与算法 2012-10-15 16:21 1233人阅读 评论(7) 收藏 举报

算法btpairalgorithmmatrix

问题提出：

给定一个二维图像，基于某个threshold，来提取contours。

在图形图像学中，这个问题有比较好的解决方案，google "coutour trace"，可以得到以下2个比较好的参考文献：

1. http://en.wikipedia.org/wiki/Moore_neighborhood

2. http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/index.html

算法描述：

The following is a formal description of the Moore-Neighbor tracing algorithm:

Input: A square tessellation, T, containing a connected component P of black cells.

Output: A sequence B (b₁, b₂ ,..., b_k) of boundary pixels i.e. the contour.

Define M(a) to be the Moore neighborhood of pixel a. 
Let p denote the current boundary pixel. 
Let c denote the current pixel under consideration i.e. c is in M(p).

Begin

• Set B to be empty.
• From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
• Insert s in B.
• Set the current boundary point p to s i.e. p=s
• Backtrack i.e. move to the pixel from which s was entered.
• Set c to be the next clockwise pixel in M(p).
• While c not equal to s do
     If c is black
  • insert c in B
  • set p=c
  • backtrack (move the current pixel c to the pixel from which p was entered)
     else
  • advance the current pixel c to the next clockwise pixel in M(p)
  end While

End 

需要注意的是，

1. 按照先列后行，每列从下到上，每行从左到右的顺序（当然也可以按照其它顺序，只要整个过程一致就可以了），搜索第一个BLACK PIXEL；

2. 有2种情况可以作为trace one contour的条件：

a) 搜索到第一个BLACK PIXEL时，如果它位于某列的第一行，将它的backtrace point定义该列的-1行；

b) 否则进入这个BLACK PIXEL的backtrace point，一定要是WHITE PIXEL。

以下代码段是基于Moore Neighborhood算法的C++实现：

[cpp] view plaincopyprint?

1. void TraceOneContour(Image<char>* bp, const std::pair<int,int>& startpos,  
2.         const std::pair<int,int>& btpos, std::vector<int>& contour)  
3. {  
4.     int xSize = bp->x_size, ySize = bp->y_size;  
5.   
6.     char BLACK = 1;  
7.     enum { LKN = 8 };  
8.     static int cwmat[LKN][2] = {        // clock-wise matrix  
9.         {-1, +1},       // left-upper  
10.         {0, +1},        // upper  
11.         {+1,+1},  
12.         {+1, 0},  
13.         {+1, -1},  
14.         {0, -1},  
15.         {-1, -1},  
16.         {-1, 0}     // left  
17.     };  
18.     contour.clear();  
19.     int px = startpos.first, py = startpos.second;  // current center point  
20.     int bx = btpos.first, by = btpos.second ;       // bt point  
21.     contour.push_back(py*xSize + px);  
22.   
23.     int cx = bx, cy = by;  
24.     bool bstop = false;  
25.     int nVisitStart = 1;  
26.     static int nStopTimes = 5;  
27.   
28.     do {  
29.         // get next clockwise pixel for (cx, cy) around (px, py)  
30.         int cur = -1;  
31.         for (int i = 0; i < LKN; ++i)  
32.         {  
33.             if (cwmat[i][0] == (cx - px) &&  
34.                 cwmat[i][1] == (cy - py))  
35.             {  
36.                 cur = i;  
37.                 break;  
38.             }  
39.         }  
40.         if (cur < 0) break;  
41.   
42.         int last = cur;  
43.         cur = (cur+1) % LKN;  
44.         while (cur != last)  
45.         {   // loop 8-connected cells around p  
46.             int prev = (cur - 1 + LKN)%LKN;  
47.             cx = px + cwmat[cur][0], cy = py + cwmat[cur][1];  
48.             bx = px + cwmat[prev][0], by = py + cwmat[prev][1];  
49.   
50.             if ((cx == startpos.first && cy == startpos.second)  
51.                 && (bx == btpos.first && by == btpos.second))  
52.             {   // Jacob's stopping criterion  
53.                 bstop = true;  
54.                 break;  
55.             }  
56.             if (cx >= 0 && cx < xSize && cy >=0 && cy < ySize  
57.                 && bp->pixRef(cx, cy) == BLACK)  
58.             {  
59.                 if (cx == startpos.first && cy == startpos.second)  
60.                 {   // In some class, only Jacob's stopping cannot stop algorithm  
61.                     // so add visit time stopping criterion  
62.                     if (++nVisitStart >= nStopTimes)  
63.                     {  
64.                         bstop = true;  
65.                         break;  
66.                     }  
67.                 }  
68.                 contour.push_back(cy * xSize + cx);  
69.                 px = cx, py = cy;  
70.                 cx = bx, cy = by;  
71.                 break;  
72.             }  
73.             else  
74.             {  
75.                 cur = (cur+1) % LKN;  
76.             }  
77.         }  
78.         // handle isolated pixel point  
79.         if (cur == last) break;  
80.         if (bstop) break;  
81.     }  while (1);  
82. }  
83.   
84. template <typename Type, typename SpecFunc>  
85. void TraceImageContours(const Image<Type>* in_img, const SpecFunc& specFunc,  
86.     std::vector<std::vector<int> >& vPolyOut)  
87. {  
88.     assert(in_img && in_img->x_size > 0 && in_img->y_size > 0);  
89.   
90.     vPolyOut.clear();  
91.     int xSize = in_img->x_size, ySize = in_img->y_size;  
92.     int npix = xSize * ySize;  
93.   
94.     char WHITE = 0, BLACK = 1, GREEN = 2;  
95.     Image<char> bp(xSize, ySize);  
96.     std::transform(in_img->pix, in_img->pix + npix, bp.pix, specFunc);  
97.   
98.     std::vector<int> onecontour;  
99.     std::pair<int,int> bt(0, -1);  
100.     // firstly column from bottom to top, secondly row from left to right  
101.     for (int i = 0; i < xSize; i++)  
102.     {  
103.         for (int j = 0; j < ySize; j++)  
104.         {  
105.             if (bp.pixRef(i, j) == WHITE)  
106.             {  
107.                 bt = std::make_pair(i, j);  
108.             }  
109.             else if (bp.pixRef(i, j) == BLACK)  
110.             {  
111.                 if (j == 0) bt = std::make_pair(i, -1);  
112.                 if ((j > 0 && bp.pixRef(i, j-1) == WHITE)  
113.                     || j == 0)  
114.                 { // start to trace one contour  
115.                     TraceOneContour(&bp, std::make_pair(i, j), bt, onecontour);  
116.                      // mark contour point green(visited)  
117.                     for (BOOST_AUTO(itc, onecontour.begin());  
118.                         itc != onecontour.end(); ++itc)  
119.                     {  
120.                         bp.pix[*itc] = GREEN;  
121.                     }  
122.                     if (!onecontour.empty()) vPolyOut.push_back(onecontour);  
123.                 }  
124.             }  
125.         }  
126.     }  
127. }  

关于Image<T>，可以参考下面的C++类：

[cpp] view plaincopyprint?

1. template <typename T>  
2. struct Image {      
3.     int x_size;  
4.     int y_size;  
5.     T* pix;  
6.   
7. public:  
8.     Image(int w, int h) : x_size(w), y_size(h) {  
9.         pix = new T[w*h];  
10.     }  
11.     Image(int w, int h, T* p) : x_size(w), y_size(h), pix(p) {  
12.     }  
13.     ~Image() {  
14.         delete [] pix;  
15.     }  
16.        
17.     T* detach() {  
18.       T* result = pix;  
19.       pix = 0;  
20.       return result;  
21.     }  
22.       
23.     T& pixRef(int x, int y) {  
24.       return pix[y * x_size + x];  
25.     }  
26.     const T& pixRef(int x, int y) const {  
27.       return pix[y * x_size + x];  
28.     }  
29. };