поиск кратчайшего пути заданное изображение для преобразования расстояния

Question

Мне дано преобразование расстояния (ниже), и мне нужно написать программу, которая найдет кратчайший путь, идущий от точки A (140,200) до точки B (725,1095), убедившись, что я Я по крайней мере, десять пикселей от каких-либо препятствий

distance_transform_given

(выше изображение расстояние преобразования map)

Это то, что я сделал до сих пор:

1. Я начал с начальной точки и оценил интенсивность оттенков серого в каждой точке вокруг нее. (8 соседних точек, которые есть)

2. Затем я перешел к точке с самой высокой интенсивностью оттенков серого из 8 соседних точек.

3. Затем я повторил этот процесс, но получаю случайные повороты, а не кратчайший путь.

пожалуйста, помогите мне

код того, что я сделал до сих пор:

def find_max_neigh_location(np,img): 
maxi = 0 
x0=0 
y0=0 
for i in range(len(np)): 
    if img[np[i][0]][np[i][1]][0] >maxi: 
     maxi = img[np[i][0]][np[i][1]][0] 
     x0 = np[i][0] 
     y0 = np[i][1] 
return x0,y0 

------------------ -----------------------------------------------

def check_if_extremes(x,y): 
    if(x==1099 and y==1174):return 1 
    elif(y==1174 and x!=1099):return 2 
    elif(x==1099 and y!=1174):return 3 
    else:return 0 

---------------------------------------------- ----------

def find_highest_neighbour(img,x,y,visted_points): 
val = check_if_extremes(x,y) 
if val==1: 
    neigh_points = [(x-1,y),(x-1,y-1),(x,y-1)] 
    np = list(set(neigh_points)-set(visited_points)) 
    x0,y0 = find_max_neigh_location(np,img) 
elif val==2: 
    neigh_points = [(x-1,y),(x-1,y-1),(x,y-1),(x+1,y-1),(x+1,y)] 
    np = list(set(neigh_points)-set(visited_points)) 
    x0,y0 = find_max_neigh_location(np,img)  
elif val==3: 
    neigh_points = [(x-1,y),(x-1,y-1),(x,y-1),(x,y+1),(x-1,y+1)] 
    np = list(set(neigh_points)-set(visited_points)) 
    x0,y0 = find_max_neigh_location(np,img) 
elif val==0: 
    neigh_points = [(x-1,y),(x-1,y-1),(x,y-1),(x,y+1),(x+1,y),(x+1,y+1),(x,y+1),(x-1,y+1)] 
    np = list(set(neigh_points)-set(visited_points)) 
    x0,y0 = find_max_neigh_location(np,img) 
for pt in neigh_points: 
    visited_points.append(pt) 
return x0,y0,visited_points 

--------------------------------------------- ------------

def check_if_neighbour_is_final_pt(img,x,y): 
l = [(x-1,y), (x+1,y),(x,y-1),(x,y+1),(x-1,y-1),(x+1,y+1),(x-1,y+1),(x+1,y-1)] 
if (725,1095) in l: 
    return True 
else: 
    return False 

------------------------------- -------------------------------

x=140 
y=200 
pos=[] 
count = 0 
visited_points = [(x,y)] 
keyword = True 
while keyword: 
    val = check_if_neighbour_is_final_pt(img,x,y) 
    if val == True: 
     keyword = False 
    if val == False: 
     count=count+1 
     x,y,visited_points = find_highest_neighbour(img,x,y,visited_points) 
     img[x][y] = [255,0,0] 
cv2.imwrite("img\distance_transform_result__"+str(count)+".png",img) 

Answer 1

Поскольку вы не комментировали свой код вообще, я выиграл ' t прочитайте свой код.

Я буду придерживаться того, что вы описали как ваш подход.

Тот факт, что вы начинаете в точке A и переходите в самую яркую точку Соседства A, показывает, что вы не знаете, что делает преобразование расстояния или что вы видите на вашей дистанционной карте ... Никогда не начинайте кодирование, если вы Я не знаю, с чем вы имеете дело.

Дистанционное преобразование преобразует двоичное изображение в изображение, где каждое значение пикселя представляет собой минимальное расстояние переднего пикселя входного изображения до фона.

Темные пиксели означают близость к фону (препятствия в вашей проблеме) и яркие пиксели подальше.

Таким образом, переход к самому яркому пикселю рядом приведет вас только к препятствиям, но не к вашей целевой точке.

Первое ограничение: Никогда не приближайтесь к препятствию, чем 10 пикселей!

Это означает, что каждый пиксель, который ближе к препятствию (более темный, чем 10), не может быть частью вашего пути. Поэтому примените глобальный порог 10 к вашей дистанционной карте.

Теперь каждый белый пиксель может быть использован для вашего пути к В.

Остальные IST задачи оптимизации. Существует множество литературы по алгоритмам кратчайшего пути в Интернете. Я оставлю это до вас ...