espdev / scikit-mpe

Minimal path extraction using the fast marching method

scikit-mpe

scikit-mpe is a package for extracting a minimal path in N-dimensional Euclidean space (on regular Cartesian grids) using the fast marching method.

Quickstart

Installing

pip install -U scikit-mpe

Usage

Here is a simple example that demonstrates how to extract the path passing through the retina vessels.

from matplotlib import pyplot as plt

from skimage.data import retina
from skimage.color import rgb2gray
from skimage.transform import rescale
from skimage.filters import sato

from skmpe import mpe

image = rescale(rgb2gray(retina()), 0.5)
speed_image = sato(image)

start_point = (76, 388)
end_point = (611, 442)
way_points = [(330, 98), (554, 203)]

path_info = mpe(speed_image, start_point, end_point, way_points)

px, py = path_info.path[:, 1], path_info.path[:, 0]

plt.imshow(image, cmap='gray')
plt.plot(px, py, '-r')

plt.plot(*start_point[::-1], 'oy')
plt.plot(*end_point[::-1], 'og')
for p in way_points:
    plt.plot(*p[::-1], 'ob')

plt.show()

Documentation

The full documentation can be found at scikit-mpe.readthedocs.io

References

• Fast Marching Methods: A boundary value formulation
• Level Set Methods and Fast Marching Methods
• scikit-fmm - Python implementation of the fast marching method
• ITKMinimalPathExtraction - ITK based C++ implementation of MPE

License

MIT

scikit-mpe's Issues

Go from a given start to different goals given binary image

This github has really interesting codes.

My question is: I do not want to use the whole road map graph around my vehicle, but an efficient way to go from A to the different goals (B1, etc.) using a binary image (driveable area in white, centerlines in red or whatever colour). Would it be possible to go from my start to the different goals using the Fast Marching Method in order to get the shortest path for each case?

Is this more efficient than an A* algorithm?

Add support for multiple-thread

Hi there,

Thanks for this fantastic library. It solves my problem quite well.

I am following this example
https://scikit-mpe.readthedocs.io/en/latest/examples.html#maze

It works well when the maze is small, but when working on a maze like the blow

It takes ages to finish its job.(Actually I started running the code 7 minutes before I submitted this issue and up until now, it's still running.)

Is it possible to make the code multi-threading?

one possible approach to make the maze path finding multi-threading is to at least launch 2 workers, one from start point to endpoint and one from end point to start point, once they meet each other, the path is found.

I am looking forward to your response.

Cheers,

Winston

Could you give an 3D example

sorry to bother you，but when i use this method to find path in 3d array, there always warring“Reason: the distance between old and current point stay too small for 100 _step_count”

travel_time with order==2 has failed

Currently, order == 2 for computing travel time in scikit-fmm (v 2019.1.30) has a numerical issue and does not work properly: scikit-fmm/scikit-fmm#28

The following code should be removed after fixing the issue in scikit-fmm:

scikit-mpe/skmpe/_parameters.py

Lines 40 to 47 in 59551ba

	@validator('travel_time_order')
	def _check_travel_time_order(cls, v):
	if v == TravelTimeOrder.second:
	raise ValueError(
	'Currently the second order for computing travel time does not work properly.'
	'\nSee the following issue for details: https://github.com/scikit-fmm/scikit-fmm/issues/28'
	)
	return v

And also in the tests:

scikit-mpe/tests/test_mpe.py

Line 13 in 59551ba

pytest.param(2, marks=pytest.mark.skip('https://github.com/scikit-fmm/scikit-fmm/issues/28')),

EndPointNotReachedError

Hi @espdev ,

I hope you had a good weekend :)

I'm trying to use the mpe to find a path, but received an error message which I cannot understand why it happens.
To my eyes, the entry and exist points have been provided and all edges are well sealed so leaky side, it should find the path, but the error happens.
I did notice that the left bottom corner misses a bit black edge, so I have manually painted black edge on that part to "seal" the edge and still the error happens.

Could you please help?

Many thanks,

here is the image

Here is the code

from skimage.io import imread
from skmpe import parameters, mpe, OdeSolverMethod
from skimage.exposure import rescale_intensity

start_p, end_p = [0, 126], [415, 0]
test_img = imread('cv2.jpg', as_gray=True)

speed_image = rescale_intensity(test_img, out_range=(0.005, 1.0))

with parameters(ode_solver_method=OdeSolverMethod.LSODA, integrate_max_step=1.0):
    path_info = mpe(speed_image, start_point, end_point)

path = path_info.path

I received this error message:

EndPointNotReachedError: The extracted path from the start point (0, 126) did not reach the end point (415, 0) in 1.2363352244019011e-05 time and 100 _step_count with distance 433.71 to the end point. Reason: the distance between old and current point stay too small for 100 _step_count

Conflicting dependencies

The scikit-fmm just fixed a bug in it's latest version 2021.2.2
If you could like to see what's the bug there, here is the link:
scikit-fmm/scikit-fmm#49

So I updated my project requirements.txt to use its latest version, then conflict happened.
Here is the error message:

Deploying...
Successfully deployed changes
Updating dependencies...
  Downloading scikit-fmm-2021.2.2.tar.gz (419 kB)
Collecting scikit-image==0.18.1
  Downloading scikit_image-0.18.1-cp37-cp37m-manylinux1_x86_64.whl (29.2 MB)
Collecting scikit-mpe==0.2.2
  Downloading scikit_mpe-0.2.2-py3-none-any.whl (13 kB)
INFO: pip is looking at multiple versions of <Python from Requires-Python> to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of scikit-image to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of scikit-fmm to determine which version is compatible with other requirements. This could take a while.
ERROR: Cannot install scikit-fmm==2021.2.2 and scikit-mpe==0.2.2 because these package versions have conflicting dependencies.

The conflict is caused by:
    The user requested scikit-fmm==2021.2.2
    scikit-mpe 0.2.2 depends on scikit-fmm<2020.0.0 and >=2019.1.30

To fix this you could try to:
1. loosen the range of package versions you've specified
2. remove package versions to allow pip attempt to solve the dependency conflict

ERROR: ResolutionImpossible: for help visit https://pip.pypa.io/en/latest/user_guide/#fixing-conflicting-dependencies

Error: failed to update dependecies: error on one or more dependencies, no dependencies were added, see output for details

I'm deploying my project to Deta

The conflict is caused by:
The user requested scikit-fmm==2021.2.2
scikit-mpe 0.2.2 depends on scikit-fmm<2020.0.0 and >=2019.1.30

Could you please bump the dependency version to its latest 2021.2.2 for scikit-fmm?

thanks