边界跟踪算法(PDF版).pdf-资料库

1 codes for defining directions of a point X under consideration. 边界跟踪算法 1 3 4 5 2 X 6 1 0 7 example for a binary image 8×8 matrix for this binary image 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 0 1 1 1 1 1 0 0 3 0 1 1 1 1 1 0 0 4 0 0 0 1 1 0 0 0 5 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 x if pixel (1,2) is set to be the start point, the next point is (2,2) and its direction code is 6. y 1

y 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 0 1 1 1 1 1 0 0 3 0 1 1 1 1 1 0 0 4 0 0 0 1 1 0 0 0 5 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 x 3 4 5 2 (0,0) (1,1) (2,1) (0,1) (1,2) (2,2) (0,2) (1,3) (2,3) 6 1 0 7 then the successive points on the contour are: (2,2), (3,1), (4,2), (5,2), (5,3), (4,4), (4,5), (3,4), (2,3) , (1,3) , (1,2). or the direction codes of the successive points are: 6, 5, 7, 6, 0, 1, 0, 3, 3, 2, 4. the direction codes depict the contour of a closed region. the algorithm to produce the direction codes of the successive points on the contour is caller Boundary tracking algorithm(BTA) 2

2 内边界跟踪算法 inner-BTA. 2.1 算法描述设在数字化网格平面的形状是封闭的，且只有一个连通的区域，这个连通的区域在二维数组中用 1 (白色) 来标记，其余的数组元素用 0 (黑色) 来标记。算法中的坐标与程序中的二维数组的下标对应。 Step 1. 对数组进行逐行查找，找到由数字 1 表示的封闭图形的最上端一行的最左边一个点（其数组行下标应该是最小的），用 P0 表示。P0 是边界跟踪的起始点。定义变量 dir 表示上述“关于方向码的概念”中的 8 个方向，所以 dir 的取值范围是 0，1 … 7 ，注意，后面的计算过程，有 dir 对 8 的模（求余）运算。对 dir 赋初值 dir=7; P0 Step 2. 按逆时针方向顺序依次判断当前点（一开始为 P0 点）的 8 个是否为 1，开始的邻居号为：（1）(dir+7) mod 8 如果当前的 dir 为偶数；即下一次搜索的方向是当前方向按顺时针方向旋转 45°。（2）(dir+6) mod 8 如果当前的 dir 为奇数；即下次搜索的方向是当前方向按顺时针方向旋转 90°。按上述的逆时针方向找到的第一个为 1 的点为找到的新的边界，记为 Pn，并更新 dir 值（以当前找到为 1 的点为最后更新的 dir 方向）。 P0 的 3x3 邻居 3 4 5 2 P0 6 1 0 7 (x-1,y-1 ) (x-1,y) (x-1,y+ 1) (x,y-1) (x,y) (x,y+1) (x+1,y- 1) (x+1,y) (x+1,y+ 1) Step 3. 如果当前的边界点 Pn 的坐标等于找到的第 2 个边界点 P1 的坐标,而且它前一个边界点 Pn-1 的坐标又与起始点 P0 坐标相同，则算法结束。否则，重复 Step 2. Step 4. 封闭形状的边界跟踪结果则为上述步骤记录的 P1,P2,P3 ….Pn-1 的坐标，或者是上述过程中保存的 dir 值。 3

2.2 算例描述以前面的图形为例，现在对于该算法的前面若干步骤的执行情况做一描述，以便更好理解算法的执行过程。 Step 1: (n=0) 找到的 Pn=P0=(1,2); dir=7; Pn=P0=(1,2) y 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 0 1 1 1 1 1 0 0 3 0 1 1 1 1 1 0 0 4 0 0 0 1 1 0 0 0 5 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 x Step 2: (n=n+1=1) 按逆时针方向顺序找到 P0(1,2)点的 8 个 3x3 邻居中第一个为 1 的点，此时 P0(1,2) dir=7 的八个近邻情形为(X 表示当前 P)： y 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 0 X 1 1 1 1 0 0 3 0 1 1 1 1 1 0 0 4 0 0 0 1 1 0 0 0 5 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 x 3 4 5 2 (0,1) (1,1) (2,1) (0,2) X (2,2) (0,3) (1,3) (2,3) 6 1 0 7 开始判断的方向为 (dir+6) mod 8 = (7(奇数)+6) mod 8 = 5, 也就是开始以逆时针依次判断的起始方向为西南方向！(7 为 P0 的方向初值) 此时，方向为 5 的邻居点(2,1)的值为 0；接着按逆时针方向要判断南，i.e. dir=dir+1=6, 方向为 6 的邻居点(2,2)的值为 1。现在要做的事情有两个：一是记录邻居“南”，（6 近邻）的坐标，Pn=P1=(2,2) 二是记录方向码 dir=6; (这两个记录过程，一般用两个数组来实现，以便最后输出结果) 4

注意，此时，当前点更新为 P1(2,2)，dir 已经更新为 6。 Step 3 , 不符合结束条件，继续转 Step 2。 Step 2: (n=n+1=2)按逆时针方向顺序找到 P1(2,2)点的 8 个 3x3 邻居中第一个为 1 的点，此时 P1(2,2) dir=6 的八个近邻情形为(X 表示当前 P)： y 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 0 1 X 1 1 1 0 0 3 0 1 1 1 1 1 0 0 4 0 0 0 1 1 0 0 0 5 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 x 3 4 5 2 (1,1) (2,1) (3,1) (1,2) X (3,2) (1,3) (2,3) (3,3) 6 1 0 7 开始判断的方向为 (dir+7) mod 8 = (6(偶数)+7) mod 8 = 5, 也就是开始以逆时针依次判断的起始方向为西南方向！(6 为 P1 的方向值) 此时，方向为 5 的邻居点(3,1)的值为 1。现在要做的事情有两个：一是记录邻居“南”，（5 近邻）的坐标，Pn=P2=(3,1) 二是记录方向码 dir=5; (两个数组记录，以便最后输出结果) 注意，此时，当前点更新为 P2(3,1)，dir 已经更新为 5。 Step 3 , 不符合结束条件，继续转 Step 2 Step 2: (n=n+1=3)按逆时针方向顺序找到 P2(3,1)点的 8 个 3x3 邻居中第一个为 1 的点，此时 P2(3,1) dir=5 的八个近邻情形为(X 表示当前 P)： 5

y 0 1 0 0 0 0 0 0 X0 0 0 0 0 0 0 0 0 2 0 1 1 1 1 1 0 0 3 0 1 1 1 1 1 0 0 4 0 0 0 1 1 0 0 0 5 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 x 3 4 5 2 (2,0) (3,0) (4,0) (2,1) X (4,1) (2,2) (3,2) (4,2) 6 1 0 7 开始判断的方向为 (dir+6) mod 8 = (5(奇数)+6) mod 8 = 3, 也就是开始以逆时针依次判断的起始方向为西北方向！(5 为 P2 的方向值) 此时，方向为 3 的邻居点(2,0)的值为 0；接着按逆时针方向要判断西，i.e. dir=dir+1=4, 方向为 4 的邻居点(3,0)的值为 0；接着按逆时针方向要判断西南，i.e. dir=dir+1=5, 方向为 5 的邻居点(4,0)的值为 0；接着按逆时针方向要判断南，i.e. dir=dir+1=6, 方向为 6 的邻居点(4,1) 的值为 0；接着按逆时针方向要判断东南，i.e. dir=dir+1=7, 方向为 7 的邻居点(4,2)的值为 1。现在要做的事情有两个：一是记录邻居“东南”，（7 近邻）的坐标，Pn=P3=(4,2) 二是记录方向码 dir=7; (两个数组记录，以便最后输出结果) 注意，此时，当前点更新为 P3(4,2)，dir 已经更新为 7。【依次得到：Pn = P1(2,2), P2(3,1), P3(4,2), P4(5,2), P5(5,3), P6(4,4), P7(4,5), P8(3,4), P9(2,3), P10(1,3), P11(1,2). dir = 6, 5, 7, 6, 0, 1, 0, 3, 3, 2, 4.】 Step 3 , 不符合结束条件，继续转 Step 2 Step 2: (n=n+1=12)按逆时针方向顺序找到 P11(1,2)点的 8 个 3x3 邻居中第一个为 1 的点，此时 P11(1,2) dir=4 的八个近邻情形为(X 表示当前 P)： 6

y 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 0 X 1 1 1 1 0 0 3 0 1 1 1 1 1 0 0 4 0 0 0 1 1 0 0 0 5 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 x 3 4 5 2 (0,1) (1,1) (2,1) (0,2) X (2,2) (0,3) (1,3) (2,3) 6 1 0 7 开始判断的方向为 (dir+7) mod 8 = (4(偶数)+7) mod 8 = 3, 也就是开始以逆时针依次判断的起始方向为西北方向！(4 为 P11 的方向值) 此时，方向为 3 的邻居点(0,1)的值为 0；接着按逆时针方向要判断西，i.e. dir=dir+1=4, 方向为 4 的邻居点(1,1)的值为 0；接着按逆时针方向要判断西南，i.e. dir=dir+1=5, 方向为 5 的邻居点(2,1)的值为 0；接着按逆时针方向要判断南，i.e. dir=dir+1=6, 方向为 6 的邻居点(2,2) 的值为 1。现在要做的事情有两个：一是记录邻居“南”，（6 近邻）的坐标，Pn=P12=(2,2) 二是记录方向码 dir=6; (两个数组记录，以便最后输出结果) 注意，此时，当前点更新为 P12(2,2)，dir 已经更新为 6。 Step 3 , Pn=P12=(2,2)= P1，Pn-1=P11=(1,2)= P0，符合结束条件，转 Step 4 Step 4: 封闭形状的边界跟踪结果为上述步骤记录的 P1,P2,P3 ….Pn-1 的坐标，或者是上述过程中保存的 dir 值。输出边界点：P1(2,2), P2(3,1), P3(4,2), P4(5,2), P5(5,3), P6(4,4), P7(4,5), P8(3,4), P9(2,3), P10(1,3), P11(1,2). dir = 6, 5, 7, 6, 0, 1, 0, 3, 3, 2, 4. 7

y 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 0 1 1 1 1 1 0 0 3 0 1 1 1 1 1 0 0 4 0 0 0 1 1 0 0 0 5 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 x 8

资料库

边界跟踪算法(PDF版).pdf

相关推荐

开发技术

热门标签

最新资料