Минимальный путь с интенсивностью от 2 точек в полутоновом изображении

Question

Я хочу определить минимальный путь между двумя конкретными точками изображения, то есть путь, для которого сумма расстояний между смежными пикселями, взвешенными по интенсивности пикселей (оттенки серого), будет минимизирована. Например, эта картина показывает входное изображение

и это (ручной тяге) минимальный путь в красный цвет, от UL к LR углу (черные границы служат в качестве нулевого веса прокладки):

Я обнаружил, что у Matlab есть функция graydist только для этого; есть что-то подобное в ndimage/scikit-image/что угодно? Я нашел scipy.ndimage.morphology.distance_transform_edt, но я не уверен, если и как использовать его для этой цели. Это нормально, если алгоритм возвращает только один из неуникальных минимумов.

Я не заинтересован в реализации намеков, это довольно простая задача алгоритмически (по крайней мере наивная реализация с использованием, например, динамического программирования), я ищу (сочетание) уже закодированных подпрограмм для этого.

Answer 1

Этот тип динамического программирования доступен в scikit-изображения, как route_through_array и shortest_path: http://scikit-image.org/docs/dev/api/skimage.graph.html