Thanks. That's extremely helpful. I think I'll be able to work out the
subclassing. I've never worked in cython but there's a first time for
everything.
Is there some alternative solution to my problem that I've missed? I've
scoured the documentation from various software projects (GIS and non-GIS)
to try to find something that implements an algorithm like this but I
haven't come across anything. This seems odd to me, since it's a problem I
assume others have had to solve before.
In any case, I'm sure I'll be back with more questions as I dive in.
Spencer
On Tue, May 2, 2017 at 2:11 PM, Zach Pincus <zpincus(a)gmail.com> wrote:
> > I need to implement a minimum cost path through an array of costs. The
> added
> > twist is that I need to ensure the path does not exceed some maximum
> > geometric distance (represented as a total number of traversed cells).
> So I
> > need my goal_reached() method to check whether the current path has
> exceeded
> > the maximum number of cells and return 1 if true (which tells MCP to stop
> > checking neighbors).
> >
> > Is there a good example implementation somewhere that I can refer to for
> > some guidance? I've sketched out a rough outline but I'm not sure I'm on
> the
> > right track:
> >
> > graph = MCP(costSurfaceArray,fully_connected=False)
> >
> > def goal_reached(index, cumcost):
> > '''code to check total distance'''
> >
> > graph.goal_reached = goal_reached
>
> First, note that MCP is implemented in cython, so you can't
> monkeypatch goal-reached like you could with a pure-python class.
> Instead you have to subclass:
>
> class MyMCP(MCP):
> def goal_reached(self, index, cumcost):
> print(index, cumcost)
> return 0
>
> m = MyMCP(costSurfaceArray)
>
> Second, let's figure out about casting your problem in a way that
> goal_reached can address. Here's the documentation for goal_reached:
>
> """ int goal_reached(int index, float cumcost)
> This method is called each iteration after popping an index
> from the heap, before examining the neighbours.
> This method can be overloaded to modify the behavior of the MCP
> algorithm. An example might be to stop the algorithm when a
> certain cumulative cost is reached, or when the front is a
> certain distance away from the seed point.
> This method should return 1 if the algorithm should not check
> the current point's neighbours and 2 if the algorithm is now
> done.
> """
>
> So basically, the function receives the "current" index (i.e. position
> in the array) under consideration, along with the minimum cost to get
> there. If the algorithm should not continue this portion of the search
> past that index, the function needs to return 1. If the algorithm
> should terminate wholesale, return 2.
>
> If all you needed to do was stop searching after you'd gotten a
> certain euclidian distance from the starting point, you could
> calculate that with just the index and knowledge of the starting
> points. However, you want to find out the current path length
> terminating in the current index.
>
> For this, you will need to deal with the MCP object's
> traceback_offsets attribute, which stores the paths to each point. For
> speed reasons, this is only available to subclasses written in cython,
> rather than pure-python. So you'll have to write it as a cpdef
> function in a cython subclass of MCP.
>
> For the implementation, you'll need to consult how MCP.traceback(self,
> end) is implemented, and run the same procedure in goal_reached() to
> simply count the length of the path and return 1 if the path exceeds
> your acceptable length:
>
> https://github.com/scikit-image/scikit-image/blob/
> master/skimage/graph/_mcp.pyx#L648
>
> This won't be totally trivial, however. You'll need to understand a
> bit of cython, and a bit about how MCP works under the hood: it
> doesn't store indices as n-dimensional tuples like (x,y,z) coordinates
> or whatever. Instead it stores them as 1-dimensional indices into the
> flattened cost array. So much of the logic in the traceback() function
> is converting those indices around. Basically you'll just need to
> copy-paste traceback() into goal_reached() but instead of
> un-flattening the indices to append them to a traceback list, just
> count the number of links required to get to a starting point.
>
> Let me know if this helps.
>
> Zach
>
> On Tue, May 2, 2017 at 12:14 PM, Spencer Gardner
> <spencergardner(a)gmail.com> wrote:
> > The skimage.graph documentation states that the goal_reached method can
> be
> > overloaded to introduce additional constraints on finding the minimum
> cost
> > path. I'm having some trouble implementing this but I can't find any
> useful
> > examples to follow online. I'm hoping someone can provide some guidance.
> >
> > I need to implement a minimum cost path through an array of costs. The
> added
> > twist is that I need to ensure the path does not exceed some maximum
> > geometric distance (represented as a total number of traversed cells).
> So I
> > need my goal_reached() method to check whether the current path has
> exceeded
> > the maximum number of cells and return 1 if true (which tells MCP to stop
> > checking neighbors).
> >
> > Is there a good example implementation somewhere that I can refer to for
> > some guidance? I've sketched out a rough outline but I'm not sure I'm on
> the
> > right track:
> >
> > graph = MCP(costSurfaceArray,fully_connected=False)
> >
> > def goal_reached(index, cumcost):
> > '''code to check total distance'''
> >
> > graph.goal_reached = goal_reached
> >
> > Thanks for any help!
> >
> > PS I posted this also on a Google Group that appears to be defunct.
> > Apologies if that list is actually active and you got a double post from
> me.
> >
> >
> > _______________________________________________
> > scikit-image mailing list
> > scikit-image(a)python.org
> > https://mail.python.org/mailman/listinfo/scikit-image
> >
> _______________________________________________
> scikit-image mailing list
> scikit-image(a)python.org
> https://mail.python.org/mailman/listinfo/scikit-image
>

> I need to implement a minimum cost path through an array of costs. The added
> twist is that I need to ensure the path does not exceed some maximum
> geometric distance (represented as a total number of traversed cells). So I
> need my goal_reached() method to check whether the current path has exceeded
> the maximum number of cells and return 1 if true (which tells MCP to stop
> checking neighbors).
>
> Is there a good example implementation somewhere that I can refer to for
> some guidance? I've sketched out a rough outline but I'm not sure I'm on the
> right track:
>
> graph = MCP(costSurfaceArray,fully_connected=False)
>
> def goal_reached(index, cumcost):
> '''code to check total distance'''
>
> graph.goal_reached = goal_reached
First, note that MCP is implemented in cython, so you can't
monkeypatch goal-reached like you could with a pure-python class.
Instead you have to subclass:
class MyMCP(MCP):
def goal_reached(self, index, cumcost):
print(index, cumcost)
return 0
m = MyMCP(costSurfaceArray)
Second, let's figure out about casting your problem in a way that
goal_reached can address. Here's the documentation for goal_reached:
""" int goal_reached(int index, float cumcost)
This method is called each iteration after popping an index
from the heap, before examining the neighbours.
This method can be overloaded to modify the behavior of the MCP
algorithm. An example might be to stop the algorithm when a
certain cumulative cost is reached, or when the front is a
certain distance away from the seed point.
This method should return 1 if the algorithm should not check
the current point's neighbours and 2 if the algorithm is now
done.
"""
So basically, the function receives the "current" index (i.e. position
in the array) under consideration, along with the minimum cost to get
there. If the algorithm should not continue this portion of the search
past that index, the function needs to return 1. If the algorithm
should terminate wholesale, return 2.
If all you needed to do was stop searching after you'd gotten a
certain euclidian distance from the starting point, you could
calculate that with just the index and knowledge of the starting
points. However, you want to find out the current path length
terminating in the current index.
For this, you will need to deal with the MCP object's
traceback_offsets attribute, which stores the paths to each point. For
speed reasons, this is only available to subclasses written in cython,
rather than pure-python. So you'll have to write it as a cpdef
function in a cython subclass of MCP.
For the implementation, you'll need to consult how MCP.traceback(self,
end) is implemented, and run the same procedure in goal_reached() to
simply count the length of the path and return 1 if the path exceeds
your acceptable length:
https://github.com/scikit-image/scikit-image/blob/master/skimage/graph/_mcp…
This won't be totally trivial, however. You'll need to understand a
bit of cython, and a bit about how MCP works under the hood: it
doesn't store indices as n-dimensional tuples like (x,y,z) coordinates
or whatever. Instead it stores them as 1-dimensional indices into the
flattened cost array. So much of the logic in the traceback() function
is converting those indices around. Basically you'll just need to
copy-paste traceback() into goal_reached() but instead of
un-flattening the indices to append them to a traceback list, just
count the number of links required to get to a starting point.
Let me know if this helps.
Zach
On Tue, May 2, 2017 at 12:14 PM, Spencer Gardner
<spencergardner(a)gmail.com> wrote:
> The skimage.graph documentation states that the goal_reached method can be
> overloaded to introduce additional constraints on finding the minimum cost
> path. I'm having some trouble implementing this but I can't find any useful
> examples to follow online. I'm hoping someone can provide some guidance.
>
> I need to implement a minimum cost path through an array of costs. The added
> twist is that I need to ensure the path does not exceed some maximum
> geometric distance (represented as a total number of traversed cells). So I
> need my goal_reached() method to check whether the current path has exceeded
> the maximum number of cells and return 1 if true (which tells MCP to stop
> checking neighbors).
>
> Is there a good example implementation somewhere that I can refer to for
> some guidance? I've sketched out a rough outline but I'm not sure I'm on the
> right track:
>
> graph = MCP(costSurfaceArray,fully_connected=False)
>
> def goal_reached(index, cumcost):
> '''code to check total distance'''
>
> graph.goal_reached = goal_reached
>
> Thanks for any help!
>
> PS I posted this also on a Google Group that appears to be defunct.
> Apologies if that list is actually active and you got a double post from me.
>
>
> _______________________________________________
> scikit-image mailing list
> scikit-image(a)python.org
> https://mail.python.org/mailman/listinfo/scikit-image
>

The skimage.graph documentation states that the goal_reached method can be
overloaded to introduce additional constraints on finding the minimum cost
path. I'm having some trouble implementing this but I can't find any useful
examples to follow online. I'm hoping someone can provide some guidance.
I need to implement a minimum cost path through an array of costs. The
added twist is that I need to ensure the path does not exceed some maximum
geometric distance (represented as a total number of traversed cells). So I
need my goal_reached() method to check whether the current path has
exceeded the maximum number of cells and return 1 if true (which tells MCP
to stop checking neighbors).
Is there a good example implementation somewhere that I can refer to for
some guidance? I've sketched out a rough outline but I'm not sure I'm on
the right track:
graph = MCP(costSurfaceArray,fully_connected=False)
def goal_reached(index, cumcost):
'''code to check total distance'''
graph.goal_reached = goal_reached
Thanks for any help!
PS I posted this also on a Google Group that appears to be defunct.
Apologies if that list is actually active and you got a double post from me.

I’ve raised the issue:
https://github.com/scikit-image/scikit-image/issues/2646
On 29 Apr 2017, 5:40 AM +1000, Stefan van der Walt <stefanv(a)berkeley.edu>, wrote:
> It may well be that those two functions use opposite directions for theta. Do you mind filing an issue?
>
> Thanks
> Stéfan
>
> On Fri, Apr 28, 2017, at 11:02, Surya Kasturi wrote:
> > Hi,
> >
> > I’m trying to use skimage.measure.EllipseModel to estimate an ellipse around a contour. The results seems to be not so satisfying. I am wondering if I am using “orientation” parameter correctly.
> >
> > Could anyone please let me know whether “theta” is in radians or degrees? / I am doing anything wrong?
> >
> > from skimage.measure import EllipseModel
> >
> > # create ellipse model
> > ellipse = EllipseModel()
> > ellipse.estimate(cnt)
> >
> > xc, yc, a, b, theta = np.array(ellipse.params, dtype=int)
> >
> > # find perimeter
> > rr, cc = draw.ellipse_perimeter(xc, yc, a, b, orientation=theta)
> >
> > # plot
> > ax.scatter(cc, rr, s=5, label="EllipseModel”)
> >
> >
> >
> >
> >
> > Thank you,
> > Surya
> >
> > _______________________________________________
> > scikit-image mailing list
> > scikit-image(a)python.org
> > https://mail.python.org/mailman/listinfo/scikit-image
> _______________________________________________
> scikit-image mailing list
> scikit-image(a)python.org
> https://mail.python.org/mailman/listinfo/scikit-image

Hi,
Sorry, I guess I can just mask the result with the watershed segmentation. I guess I wonder if it is the proper way to do it? And also, from your point of view, if it's the way to go to segment these cells or if you think of a better way?
Cedric