Re: Segmenting contours

[Stéfan van der Walt]

Hi Zetah

On Sun, Feb 24, 2013 at 1:10 AM, zetah ven <ot...@hush.ai> wrote:
> I'm hunting magenta contour, but I need it without discontinuities (gaps), like I get if I threshold just magenta. So I would like to get this:

I think image inpainting might solve your problem. Unfortunately, we
do not have an implementation in scikit-image, but OpenCV does:

http://docs.opencv.org/modules/photo/doc/inpainting.html

Let us know how that works.

Stéfan

[zetah ven]

Hi Stefan, and thank you for your reply

For some reason I did not receive email notification, and came here to post what I found, when I was pleasantly surprised by your reply :)

I was looking through OpenCV functions just yesterday, and I didn't notice this Inpaint() magic function, as I was expecting something in other parts of this library, like segmentation, tracking and countouring. Contouring ringed the most, but it was complicated for me at the time to extract something meaningful for my problem which is topological contour tracing (that I colored with above example images, not to scare potential reader ;)

I just tried the function, but I guess it works best for photo images, as line contours aren't reconstructed as expected. Anyhow thanks for the tip, it could be handy in future occasions I guess.

I was also reading various papers. There seem to be couple of methods for reconstructing dense contours with gaps, which is part of more general problem of curve reconstruction. The most accurate results are reported by using Delaunay triangulation and properties of Voronoi diagram vertices, and then applying filtering to obtain the reconstruction. It's referenced to Amenta paper "The crust and the beta -skeleton: Combinatorial curve reconstruction" and it seems to me that environment like NetworkX could be my first step in trying to visualize and then understand this method, as although I've heard about Voronoi and Delaunay triangulation, I never used those functions. Then perhaps engage scipy and matplotlib for real example.
In slow pace that is my plan.

[Stéfan van der Walt]

On Mon, Feb 25, 2013 at 6:49 AM, zetah ven <ot...@hush.ai> wrote:
> I just tried the function, but I guess it works best for photo images, as
> line contours aren't reconstructed as expected. Anyhow thanks for the tip,
> it could be handy in future occasions I guess.

How about a very simple heuristic? You extract all curves of a
certain color and fit a spline to them. The, you consider all start
and endpoints that fall within a certain radius of one another,
connect them temporarily with a line segment, and see how
discontinuous the start/end points are with this new segment inserted
(e.g., meet the angle at which they meet). If the angle is small
enough, trust that this is part of the contour and simply use a spline
fit to connect the start and endpoint.

Stéfan

[zetah ven]

Thanks Stefan, that indeed sounds like most reasonable first step I should take, instead tangling myself in Voronoi diagrams from start. Thinking about it and possible reasons why I didn't see such approach mentioned, I thought about another possible extension, and I'll explore both tomorrow - after segmenting lines by color, and thinning I could apply smooth vector tracer on lines as they are (with gaps) so that I'll get spline fit in vector format; then instead programming search for tools supporting any vector format that can get me to it. Perhaps some GIS tool, or maybe just some utility tool useful elsewhere, and then decide next step.

[zetah ven]

Hi again, I thought to report my status. Sorry if this may seem as OT for this group, I'm guided by the fact that only here initiated discussion started, and as being indexed by Google, hopefully will save time to other person is similar situation.

GIS flagship gdal, offers topo line closure if source file is DEM conformant, i.e. if I label contours in TIFF bitmap with Z values I should expect good results. But labeling lines with Z values, even if I use tool to automate part of the process will need too much time because of the gaps, which I can use to close the gaps manually instead. Gdal offers Python script `gdal_fillnodata.py` and although my source file doesn't meet the requirements, using this script closed some gaps correctly, but many were left out regardless parameters used.

If I had labeled contours, also other GIS tools could be up to the task (more of less), like for example discussed here: http://gis.stackexchange.com/questions/44319/how-to-close-multipart-polyline-gaps-in-arcmap and by other means which I'm aware but discard because I don't have Z labeled data. What I'm really surprised is that expensive commercial tools like ArcGIS can't do this out of box! In the linked question Magda (question initiator) reported success by using some third party ArcGIS extension. I don't have ArcGIS but I have a friend with license, and we tried suggested tool. Function that offered gap closure, was poor, in a sense that it just closes the gaps by minimal distance, so if contours are dense result is silly.

I wasn't able to find strictly speaking vector tool, that can help, and I'm still in this quest, afterwhich I'll try programming by hand. That is if I don't loose interest in the process, which if also one of the reasons I thought to report my status ;)

[Stéfan van der Walt]

Hi Zetah

On Wed, Feb 27, 2013 at 4:36 AM, zetah ven <ot...@hush.ai> wrote:
> If I had labeled contours, also other GIS tools could be up to the task
> (more of less), like for example discussed here:

What kind of contours can you currently extract (and can you place
such an example online)? If you can at least get the broken contours,
using a kd-tree to search for neighbors and connecting them should be
quick.

Stéfan

[zetah ven]

Stefan van der Walt wrote:

What kind of contours can you currently extract (and can you place
such an example online)?  If you can at least get the broken contours,
using a kd-tree to search for neighbors and connecting them should be
quick.

Stefan, here is example by the book: http://i.imgur.com/tgphMUK.png

Are you refering to OpenCV function?

Thanks

[zetah ven]

Stefan, here is example by the book: http://i.imgur.com/tgphMUK.png

This is reported as a result from above image by using the method with Delaneau triangulation: http://i.imgur.com/8DIEFHs.png

[Stéfan van der Walt]

Do you have a way of obtaining a vector description from a bitmap such
as the PNG shown above? That would be a good step in the right
direction.

Stéfan

[zetah]

Sure Stefan, I attached SVG version with a bit of smoothing.

[zetah]

Stefan,

I found the algorithm implemented in CGAL ipelet demo package, so except the implementation it can be applied in ipe GUI. I'm impressed by those ipelets, as they make this vector drawing program magical, allowing computational geometry algorithms in vector application.

I also went the route with Python, and it doesn't look that hard as expected. Triangulation can be applied on binary image as is, but it's better if contours are sampled. "Only" thing left for me to do is applying the crust i.e filtering the triangulation, which I interrupted as I was introduced to this huge package CGAL.


Cheers