Lack of symmetry in find_boundaries? #738

josteinbf · 2013-09-26T10:35:15Z

I'm trying to use the find_boundaries function, and to figure out what output to expect, I tested it on an array with only a single pixel being True and the rest being False:

import numpy as np
from skimage.segmentation import find_boundaries

a = np.zeros((5, 5), dtype='bool')
a[2, 2] = True

boundary = find_boundaries(a)
print(boundary)

The output was the following:

[[False False False False False]
 [False False False False False]
 [False False  True  True False]
 [False False  True False False]
 [False False False False False]]

I was surprised by this output, as it seems to me that it is less symmetric than it ought to be. I was expecting either just a single pixel being True, or perhaps a 2x2 block being True. I decided to test the symmetry a bit further by finding the boundary of the same array after flipping it:

boundary_inverted = find_boundaries(a[::-1, ::-1])[::-1, ::-1]
print(boundary_inverted)
print(np.all(boundary == boundary_inverted))

The output was

[[False False False False False]
 [False False  True False False]
 [False  True  True False False]
 [False False False False False]
 [False False False False False]]
False

I'm not sure if this is a bug, but it may well be. The docs could certainly be improved, though, as I cannot understand why the result is what it is.

Can anyone please help me clarify what to expect here?

The text was updated successfully, but these errors were encountered:

jni · 2013-09-27T01:17:19Z

I always knew this was a problem in skimage, but I'm not sure what the best solution is. The problem is that a boundary is really a subpixel property, so what we really should do is return an image twice the size of the original with the "between" pixels marked True.

Anything that operates on the space of the original image is going to be an unsatisfactory approximation. @tonysyu (I think) went with an asymmetrical solution: it's finding every pixel where img[i, j] != img[i-1, j] or img[i, j] != img[i, j-1]. Whenever I do it, I prefer a symmetrical solution: I find every pixel where dilation(img) != erosion(img). But my solution gives boundaries that are 2 pixels thick, which is often uglier.

Hopefully that makes sense. Again, both solutions have issues. Not sure what the best way forward is.

JDWarner · 2013-09-27T03:08:58Z

As an alternative, I suggest trying out skimage.measure.find_contours which is freed from the limitations of the original array. It returns true sub-pixel contours in 2D. The output is a set of vertices for each detected contour. Try this:

import numpy as np
from skimage.measure import find_contours  # New function, similar name

a = np.zeros((5, 5), dtype='bool')
a[2, 2] = True

# a is converted to double; the 0.5 tells it the level of the contour
contours = find_contours(a, 0.5)

The result is a list of arrays containing contour vertices for all unconnected contours found for the passed level. In this case only one contour is found. The contour for this trivial example has four unique vertices (obvious by inspection) but five are returned. The first is always repeated at the end, to make it a truly closed contour. Printing contours for this example yields:

[array([[ 2.5,  2. ],
       [ 2. ,  1.5],
       [ 1.5,  2. ],
       [ 2. ,  2.5],
       [ 2.5,  2. ]])]

Which is correct by inspection for the given example.

The 3D analogue of this is marching_cubes, now merged and also available in skimage.measure. Indeed, marching_cubes was based upon find_contours.

josteinbf · 2013-09-27T08:49:12Z

@jni I see the problem. I think you are on the right track when you use dilation/erosion. What about image & (~binary_erosion(image)) (where image is bool)? That is the approach I'm currently using as a workaround. I think that makes more sense than the asymmetric version implemented now. I think I've come to the conclusion that I consider the current behaviour a bug (at least in the docs for the function).

@JDWarner Thanks, this is an excellent suggestion for my particular use case right now, which is to calculate the Hausdorff distance between two boolean images (True representing points that are included in the sets).

jni · 2013-09-27T12:06:43Z

@josteinbf, very nice for binary images, but won't work for n-labeled images, which find_boundaries tries to do (as does my solution). Also, it is application-dependent whether one would prefer your image & (~binary_erosion(image)) or the complementary (~image) & binary_dilation(image). We could write two functions, binary_inner_boundary and binary_outer_boundary, to explicitly cover both cases. I'd certainly find them worthy additions to the current function. If we add my solution to the mix though, we now have four boundary-finding approaches, which might be a bit heavy. There's a design decision to be made here.

In another note, I hadn't heard about Hausdorff distance, which is totally awesome, and indeed find_contours appears perfect for it.

I've been meaning to add segmentation evaluation functions to scikit-image for quite some time... Would you like to start an evaluation.py file with your Hausdorff implementation? Bonus points if it works for both 2D and 3D! =)

josteinbf · 2013-09-27T15:25:45Z

@jni Agreed when it comes to your assessment of binary vs labelled. However, I'm starting to think that having boundaries two pixels wide actually makes sense. Consider this definition: "A pixel in a labelled image is a boundary pixel if it has one or neighbour pixels that has a different label than it 8000 self." This should be equivalent to the dilation != erosion that you suggested before. Now, to also cater for my usage, consider adding the concept of a "background label", which really means a pixel without a label (this is already in use elsewhere in skimage). Amend the definition above by saying that "A pixel in the background is never a boundary pixel", and then I can get the behaviour I want by defining False as the background label. Choosing True as the background label would result in the "outer boundary" (but I think "outer boundary" can be confusing: Boundary points in a set are still members of the set, usually, so the "inner boundary" is what I think people would expect by default).

Summary of the above: Implement find_boundaries as per your first suggestion, just adding the concept of a "background label".

I really think skimage could use a Hausdorff distance function :) I don't have much time for skimage developments these days, and I should complete my phase unwrapping stuff before I file more PRs, so it may take a while before you see a PR on this. If you get inpatient, let me know, and I'll put the code in a gist or something for you to play with. It seems to be working fine, but needs tests and docs.

JDWarner · 2013-09-27T15:29:49Z

I have Dice and Jaccard metrics I could be persuaded to upload... If you publish a working skeleton in a gist I'm sure we could help with fleshing that out into an addition!

josteinbf · 2013-09-27T15:36:11Z

@JDWarner I would certainly appreciate it if you could upload the code for those two metrics, too! A gist right away would be great; I'm struggling with a "measure quality of segmentation" problem at work at the moment (hence the Hausdorff implementation), and more metrics would be great.

Let me see if I can't find time for a Hausdorff PR over the next few days. If not, a gist is coming. I don't want to dump this on anyone else before I'm sure that's the only way to do it.

josteinbf · 2013-09-27T15:43:51Z

By the way, are we sure that metrics such as these belong in the segmentation subpackage? They're useful for evaluating segmentations, sure, but there are other use cases as well (template matching is certainly one). Are morphology, measure or even filter more appropriate?

JDWarner · 2013-09-27T16:13:05Z

Generally these comparisons are done between segmented or masked images, which presumably may have had previous work done by segmentation.

That said, if we had a more robust set of them I could see the case for moving similarity metrics over to measure. Since you really are attempting to quantify the relationship between two objects, it seems to me a naive user would probably look there first.

Here's a Gist for the Dice coefficient, and here's a Gist for the Jaccard coefficient. Only the Jaccard coefficient is a true metric; the Dice coefficient does not satisfy the triangle inequality. They both are defined on the range [0, 1] but the Jaccard metric is generally more difficult to satisfy.

jni · 2013-09-28T01:18:10Z

Either segmentation or measure work well for me.

I have implementations of the variation of information and Rand index in gala. (More precisely in evaluate.py). Both work with n-dimensional images.

josteinbf · 2013-09-28T08:49:07Z

Sounds to me like we have a few metrics; I think I will submit the first Hausdorff to measure, then. The Hausdorff I have now works with 2D and 3D images. The only thing missing to make it nD is having a structuring element for erosion like disk and ball that works in nD, I think.

jni · 2013-10-03T02:14:34Z

@JDWarner @stefanv I think it might be a bit much to pin down all of these metrics for 0.9, but what do you think?

Fixes scikit-image#738

josteinbf mentioned this issue Sep 29, 2013

Hausdorff distance #742

Closed

jni added a commit to jni/scikit-image that referenced this issue Jan 8, 2015

Make find_boundaries symmetric

85509c3

Fixes scikit-image#738

jni added a commit to jni/scikit-image that referenced this issue Jan 8, 2015

Make find_boundaries symmetric

22acb12

Fixes scikit-image#738

jni mentioned this issue Jan 8, 2015

WIP: wrap ndimage morphology #1310

Merged

jni closed this as completed in b1891dc Jan 22, 2015

msarahan pushed a commit to msarahan/scikit-image that referenced this issue Feb 21, 2015

Make find_boundaries symmetric

17146e0

Fixes scikit-image#738

clementkng mentioned this issue Jul 11, 2019

[WIP] Hausdorff Distance (new) #4005

Closed

9 tasks

clementkng mentioned this issue Dec 31, 2019

Hausdorff Distance (updated) #4382

Merged

9 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Lack of symmetry in find_boundaries? #738

Lack of symmetry in find_boundaries? #738

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Lack of symmetry in find_boundaries? #738

Lack of symmetry in find_boundaries? #738

Comments

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!