矩阵中的摩尔邻域

Question

我有一个从图像（在本例中为 5 的形状）转换而来的 2d 文本文件，我正在尝试实现 Moore Neighborhood Trace 算法。问题是，当我到达矩阵中间的一个点时，我的程序开始访问在从未到达矩阵底部之前已经访问过的单元格。我的输入：

00000000000000000000
00000000000000000000
00000000000000000000
00001111111111100000
00001111111111100000
00001100000000000000
00001111111110000000
00001111111111100000
00000000000001110000
00000000000000110000
00011000000000110000
00011100000001110000
00001111111111110000
00000111111111000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

我的输出（'x'是边框，A是我迭代N次后所在的单元格）

00000000000000000000
00000000000000000000
00000xxxxxxxxxx00000
000011111111111x0000
000011111111111x0000
000011xxxxxxxxx00000
0000111111111x000000
000011111111A1100000
000000000000x1110000
00000000000000110000
00011000000000110000
00011100000001110000
00001111111111110000
00000111111111000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

我设法找到问题发生在哪次迭代 (n=29) 之后它又开始上升

    class parse:

    def __init__(self):
        self.state = 3 #entered from W so start looking from N-E-S-W
        self.matrix = self.read_file()
        self.process()
        self.save_file()

    #Handle Files I/0
    def read_file(self):
        ls = []
        with open("in","r") as g:
            tmp = g.readlines()

            for x in tmp:
                ls.append( [str(x[l]) for l in xrange(len(x))] )

        return ls


    def save_file(self):
        with open("out","w") as g:
            for i in xrange(len(self.matrix)):
                for j in xrange(len(self.matrix)):
                    g.write(self.matrix[i][j])
                g.write('\n')

    #End File Handle


    #Trace Algorithm
    #non-negative x

    def start_pixels(self):

        for x in xrange(len(self.matrix)):
            for y in xrange(len(self.matrix)):

                if self.matrix[x][y] == '1':

                    return [x,y]

    def process(self):
        init_point = self.start_pixels()

        start = self.step(init_point[0], init_point[1])
        i = 0 # iterations

        while i < 29:

            tmp = self.step(start[0],start[1])

            start= tmp

            i+=1

        self.matrix[start[0]][start[1]] = 'A' #current cell 
        print self.state #print the direction to skip

    def step(self,r,c):
        pos = [ [-1,0], [0,+1], [+1,0], [0,-1] ]  #search in the 4 directions of the cell N-E-S-W

        for p in xrange(len(pos)):

            sc = (p + self.state)%4 #start from the next direction clockwise from which was entered

            x = pos[sc][0] + r
            y = pos[sc][1] + c


            #if the cell is 1 search its neighborhood
            if self.matrix[x][y] == '1':
                self.neighborhod(x,y)
                return [x, y]


    #complete 0 cells with 1 relative to the cell
    def neighborhod(self,r,c):
        pos = [ [-1,0], [0,+1], [+1,0], [0,-1] ] #search in the 4 directions of the cell N-E-S-W

        for p in xrange(len(pos)):

            x = pos[p][0] + r
            y = pos[p][1] + c


            if self.matrix[x][y] != '1':
                self.matrix[x][y] = 'x'
                self.state = p #assign the direction to skip



p = parse()

（请忽略橙色的绿色单元格完成，我不是无法摆脱它）

Answer 1

我看到逻辑问题了。在neighborhod [sic]中，你没有考虑整体的调查方向。相反，您选择一个“1”，然后盲目 select 具有相邻“0”的第一个方向。这意味着当你走进一个厚度为 1 个字符的点时，你运行有被另一边绊倒的风险，直接穿过 "thin wall".

您可以通过一些简单的墙壁识别来解决这个问题：新台阶必须与之前的位置相邻。不要每次都从左边开始，而是从之前的方向顺时针 45 或 90 度开始，从那里循环选择。

另一种方法是检测少数可能的 "wall" 形状并设置简单的识别模式来遍历它们。抓住带有您之前位置 P、当前位置 C 和“1”标记的 3x3 矩阵。这是一个示例模式：

1P0    1x0
1C0 => 1P0
110    11C

这些观察和建议是否让您感动？

Answer 2

也许这会有所帮助，只需调整输入的大小（宽度 x 2 和高度 x 2），这样它就可以防止 "dead pixel"，在我的研究中，我使用了它，检查一下 https://www.youtube.com/watch?v=XCgcEKfQ0ao

矩阵中的摩尔邻域

Moore Neighborhood in a matrix

python

image-processing

matrix

computer-vision

computer-science