CellCognition / cecog

A fast and cross-platform image analysis framework for fluorescence time-lapse microscopy and bioimage informatics.
https://cellcognition-project.org
Other
43 stars 17 forks source link

Artefacts in the calculation of the convex hull #221

Closed rhoef closed 7 years ago

rhoef commented 8 years ago

The calculation of the convex hull shows a lot of artifacts located preferably in the upper left quadrant of an ROI object. The Image below is just one example of many. This affects the calculation of the convex hull features. Number off connected components and anything derived from it.

artifacts

a) bianry mask of the original image b) convex hull of the binary mask c) difference image

ThomasWalter commented 8 years ago

I am not sure that this is an artefact, as all Bresenham lines between any two points need to be inside the resulting set (which is clearly not the case in image a). Do you have other examples?

A rotational preference is worrying however (and would indeed indicate a bug). Did you test what happens if you turn image a? Perhaps there is a problem in the line scanning for solving ties?

Just to modulate a bit what you said regarding the effect of this: if the problem mainly consists in the many small connected components in the residue image, their number is probably the only feature severely affected. All other features take the size of the connected components (or the size of the residue) into consideration. Take this just as a side-remark: we still have to investigate, whether everything is correct.

rhoef commented 8 years ago

What we observe here is mostly noise resulting from pure discretization of smooth outlines. As already said it is just one example of many.
convexhull.zip

convex

I assume that cellcognition is calculating the convexhull also from a pixelized outlines (i.e. taking the outer most corner of a pixel). Here are two images produced with fiji.

polygon polygons as calculated

pixelized pixelized polygons

It is clear if we consider the blue contour (which occupies an area due to pixelization) as part of the convex hull that we find every now and then additional pixels.

We could simply erode the convex hull by one pixel before calculating the difference. It might bias the area of the connect components a little. Taking only the two white areas into account for feature calculation will reflect better the situation that having many additional tiny objects due to noise

ThomasWalter commented 8 years ago

It is clear if we consider the blue contour (which occupies an area due to pixelazation) as part of the convex hull that we find every now and then additional pixels.

I am perfectly fine with finding every now and then additional pixels which are mainly due to the discrete nature of the image support. That's inline with the definition of a convex hull, and that's the limitation of working in Z^2. One solution is to define features accordingly. For instance, there is one feature that applies a size filter (number of connected components with area larger than lambda). Others work directly with the size of the connected components or the size of the sets, so that the effect should be negligible.

What worries me more is that apparently these "additional pixels" seem to appear more on the left than on the right side. There must be something in the algorithm responsible for this ... maybe it's how ties are handled in the line scanning. This must be corrected in the code (but for this I would test with rotated images).

We could simply erode the convex hull by one pixel before calculating the difference.

Please don't. This would mean that the initial set is not even guaranteed to be a subset of its convex hull. And in any case, that is not a clean solution.

I can check the algorithm and code when I am back next week (I am still traveling this week).

ThomasWalter commented 7 years ago

OK, I checked this. As I suspected, there was a minor bug in the line scanning algorithm (it was implicitly a floor instead of round, so a systematic shift to the left). I do not believe that it seriously affects the results. Nevertheless, I corrected this and pushed to the branch debug_convex_hull

I did not want to merge, as I do not know how our policy is regarding changes that can affect previous classifiers. Again, I really think that this is minor, but you never know. If everybody is fine I can just merge this to the master.

The new version does not have any directional preference, but it is also not entirely rotationally invariant (again due to the line scanning algorithm). Also it calculates the convex hull in Z^2, so there are still small components. Again, I do not see that this is a problem. The only feature affected is the number of cc of the difference; all other features use the size in one or the other way. What exactly is your purpose, actually?

ThomasWalter commented 7 years ago

Just two examples (original image, convex hull and overlay with the original image in grey): single_points convex_hull convex_hull_overlay shape convex_hull_shape convex_hull_overlay_shape

First example with just a list of points, second example with a shape.

ThomasWalter commented 7 years ago

I also exported the function so that the convex hull can be calculated from ccore directly (without having to make feature extraction for candidates etc.)

rhoef commented 7 years ago

Added post processing step using this this function.