Iterative image reconstruction using random cubic bézier strokes

https://tangled.org/luthenwald.tngl.sh/splined

by luthenwald • 6 months ago

97 18 6 months ago

kvnhn• 6 months ago

I made a simple web UI[1] for generating images like this. It uses a Go library by Michael Fogleman[2] for all the heavy lifting—hat’s off to him.

For Bézier curves in particular, iteratively constraining the search around initial matches seems key to retaining detail (see the “rep” argument in Fogleman’s work), for example in the eyes of the Vermeer portrait in the OP.

[1] https://github.com/kevin-hanselman/primitive-web-ui

[2] https://github.com/fogleman/primitive

behnamoh• 6 months ago

The project references Geometrize: https://github.com/Tw1ddle/geometrize and I find both insanely cool!

vessenes• 6 months ago

Those are sort of like 2D splats - if only they'd thought to make it all differentiable!

Sharlin• 6 months ago

Back in the 00s a friend and I played with the idea of using genetic programming and random line segments to approximate images (ie. maintain a population of candidates, take the best n percent, "breed" them to create the next generation, add some "mutations", repeat). This implementation seems to use a basic hill-climbing algorithm to reach a local optimum – something like simulated annealing might improve both quality and speed of convergence.

bArray• 6 months ago

I wrote something similar years ago, which would instead convert an image into a mesh of polygons. The idea was to have a vector low-size SVG that could be used as an image placeholder or background for web pages.

I think I lost the code, but it was initially a genetic algorithm that randomly placed overlapping polygons, but the later improved method had connected polygons that shared points - which was far more computationally cheaper.

Another method I explored was to compose a representative image via a two-colour binarised bitmap, which provided a pixelated version of the image as a placeholder.

The core idea is that you drop the image as a small Data URI straight into the page, and then fetch the high-detail version later. From the user's perspective, they are getting a very usable web page early on, even on poor connections.

seg_lol• 6 months ago

For historic reference, back in 2008, Roger https://www.rogeralsing.com/2008/12/07/genetic-programming-e... kicked this off by attempting to reproduce the Mona Lisa using evolved polygons.

https://news.ycombinator.com/item?id=389727

atulvi• 6 months ago

I tried something like this years ago but using genetic algorithms https://a.tulv.in/genetic-art.html

9021007• 6 months ago

Nice to see Tangled used out there in the wild :)

mattdesl• 6 months ago

Nice work, the outputs look ethereal and quite beautiful. For some related work using genetic algorithms and evolution strategies, see[1].

Sketch synthesis is an area I'm pretty interested in lately; I'm currently exploring similar things with CLIP to guide fitness, natural evolution strategy to optimize the rendered results, and using an implicit neural representation to represent pen plotter paths (rather than a series of explicit curves/strokes).[2]

[1] https://es-clip.github.io/

[2] https://x.com/mattdesl/status/2011434166022476109

dirkc• 6 months ago

Nice, I did something similar for a university project, but my results weren't great. Although that has been almost 20 years ago. It's been a while since I've seen mention of "genetic algorithms".

anematode• 6 months ago

Awesome stuff :) The results are really impressive.

GPU acceleration is a really good idea; my CPU implementation of a similar idea with triangles (https://github.com/anematode/triangle-stacking) was compute constrained for smaller images (which was fixable with good SIMD optimizations) but became bandwidth constrained for very large images that don't fit in L2. I think a port to OpenCL would have been a good idea.

jeremyscanvic2• 6 months ago

Really cool! Any specific reason for the choice of Oklab instead of say HSL/HSV?

ronsor• 6 months ago

Oklab is a great color space that does what you expect[0] much better than HSL/HSV.

[0] https://bottosson.github.io/posts/oklab/. The better a color space matches human perception, the easier it is to certain processing operations, such as converting to grayscale while preserving the perceived brightness.

jeremyscanvic2• 6 months ago

Thanks!

odyssey7• 6 months ago

See also: Differentiable Vector Graphics Rasterization

https://people.csail.mit.edu/tzumao/diffvg/

akoboldfrying• 6 months ago

I think you'll find that most of the retained curves are short, because these are the ones that are able to provide local detail. Maybe you could improve the detail level by choosing the 4 control points to be nearby most of the time?

I made a similar thing a few years ago using randomly placed translucent circles of random sizes and fixed opacity level (about 20% as I recall). Initially the circles had unknown colours; after placing them all, for each of the R, G and B channels, I used a linear programming solver to solve exactly for the intensities in that channel that would minimise an overall error (I had to use the L1 distance, since the more usual squared error couldn't be expressed in the solver). This produced some quite nice images, that were also fun to animate :)

HelloNurse• 6 months ago

It might make sense to reduce curve size adaptively. Suppose the first control point of each candidate curve is randomly distributed anywhere in the image (weighted by error at each pixel might be more efficient than a uniform distribution), the other three control points are randomly distributed according to a Gaussian distribution with variance σ and average the previous control point, and the actual curve is clipped against the image rectangle. Then after N consecutive candidate curves are rejected we could reduce σ in order to try smaller curves.

bazzargh• 6 months ago

I was doing something related for genuary recently, but with different constraints - I wanted to make a photgraph look painted in a fauvist style, with visible brushstrokes (and a vivid, unrealistic colour scheme). When you're overlaying many, many strokes like that you end up hiding the errors but also hiding the digital brushtrokes; with very few strokes, placement becomes important.

Instead of just stroking with the average colour, I chose to only connect points that were similar in colour (because of the fauvist thing, I was mainly interested in hue; the paints are all intense). By doing this, I was trying to be edge preserving, without explicitly calculation, eg of the Sobel operator.

It kinda worked in that the edges came out clearly; the resulting painting was messy tho; the thick brushstrokes and the colours are intentional, but the brushstrokes going in random directions is not https://media.hachyderm.io/media_attachments/files/115/894/8... compare to an actual fauvist work, https://en.wikipedia.org/wiki/Robert_Delaunay#/media/File:Ro... which still has the 'dithered' look to the face but the strokes are deliberately aligned, I'd fix that if I try again. (Delaunay also uses small strokes for detail, a thing I wasn't going to try in a throwaway program)

An earlier attempt at generating pencil sketches from photos - again, keeping the number of strokes small, and using parallel strokes for hatching - worked much better https://media.hachyderm.io/media_attachments/files/112/767/4... (it's just sobel to find edges and a bit of sampling with a filter to decide where to shade)

Iterative image reconstruction using random cubic bézier strokes

Related Stories