Pencil Tracing

[evancasey]

It's listed on the readme that "Pencil tracing" (i.e. centerline tracing) is on the roadmap. I'm working on a project where this could be super valuable and might be able to contribute to the development/discussion.

But where to even start? Aside from Autotrace and a few SIGGRAPH papers I haven't seen much work in this area. It would be great if someone with experience here could summarize the common approaches or provide some direction.

[tyt2y3]

I have had various prototypes I wrote many years ago lying around, with various degrees of success.
I think it heavily depends on the input you have. If they are more or less idealized, like electronic circuits, it is easier to exploit a few invariants there. But if you scanned a hand drawn drawing it would be very difficult and computationally expensive.

So what does your input look like?

[tyt2y3]

^ raw skeleton

^ extracted skeleton

one approach is to first skeletonize the shape and then prune the tree until you get the central axis

[evancasey]

Interesting, would you skeletonize before or after vectorization?

I'm interesting in applying this to hand-drawn animation/cartoon images. The line quality is usually very good (see attached), but there a cases where the drawing is done with a thicker pencil which could make it harder.

But even getting centerline tracing on an image like this would be huge...

[evancasey]

I'm most worried about getting all the joints to line up, in which case the vectorizer might treat the line as disjoint paths

[tyt2y3]

the skeleton does not have to be perfect to begin with, it just needs to tell us the topology roughly

the above "rough" algorithm was included in https://docs.rs/visioncortex/latest/visioncortex/struct.BinaryImage.html#method.to_skeleton

but it would fall short when the line is very thick:

[tyt2y3]

skeletonize before or after vectorization

after clustering, as raw polygons; before curve fitting

[tyt2y3]

I see you, the thickness of your lines are very manageable!

[evancasey]

nice!! I'll give skeletonizing a try and post the results here :)

[evancasey]

How thin does the line need to for vtracer to not output double lines? Or would I need to also change the vectorization code to merge double lines.

[tyt2y3]

One thing I did was to first detect all junction (or intersections) and then decompose the shapes into simplier patches before skeletonizing

^ intersection points marked in red

^ gray: input; black: final skeleton

[tyt2y3]

so the complexity in your particular sample is more or less doable

[evancasey]

Sorry, forgot to respond here. How are you using the intersections? Not sure I follow this:

One thing I did was to first detect all junction (or intersections) and then decompose the shapes into simplier patches before skeletonizing

I do think making the problem simpler with junction detection is a fruitful approach, but it seems like your output here has gaps in the junctions

[evancasey]

As a general approach, why not start with the paths and reduce them down into pencil strokes, eg: https://www.youtube.com/watch?v=tEZF7Fo6Fpg

[tyt2y3]

Depending on the input, it won't work in the general case