Moore Окрестности в матрице

Question

У меня есть 2d текстовый файл, преобразованный из изображения (форма 5 в этом случае), и я пытаюсь реализовать алгоритм отслеживания соседства Мура. Проблема заключается в том, что, когда я достигаю точки в середине матрицы, моя программа начинает посещать ячейки, которые были посещены, прежде чем не дойти до нижней части матрицы. Мой вход:

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

Мой выход («х» граница, А клетка, где я после N итераций)

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

мне удалось найти, при котором итерации возникает проблема (п = 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

Я вижу логическую проблему. В соседстве [sic] вы не задумываетесь об общем направлении расследования. Вместо этого вы выбираете «1», а затем слепо выбираете первое направление, которое имеет смежное «0». Это означает, что когда вы идете в пятно с толщиной 1 символ, вы рискуете наткнуться на другую сторону, пробираясь прямо через «тонкую стену».

Вы можете исправить это с помощью некоторого тривиального распознавания стены: новый шаг должен быть смежным с предыдущим положением. Вместо того, чтобы каждый раз начинать левое, начинайте 45 или 90 градусов по часовой стрелке от предыдущего направления, перемещаясь по выбору оттуда.

Другим способом является обнаружение нескольких возможных «стенных» форм и установка простых шаблонов распознавания для их перемещения. Возьмите матрицу 3x3 с предыдущей позицией P, текущей позицией C и отметками «1». Вот образец образца:

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

Имеют ли эти наблюдения и предложения движение?

Answer 2

может быть, это может помочь, просто изменить размер входа (ширина х 2 и х высота 2), так что это предотвратить «мертвый пиксель», в моем исследовании, я использовал его, проверить это https://www.youtube.com/watch?v=XCgcEKfQ0ao