Hill climbing for image-to-primitive approximation
Approximate a photo by adding one randomly-mutated geometric shape at a time, keeping only mutations that reduce RMSE error against the target image.
Run it
What it looks like when it goes wrong (4)
- Every mutation is accepted whether or not it lowers the error, so the search stops climbing and starts wandering — shapes drift into whatever an unlucky sequence of tweaks handed them instead of converging on the target.
- Scoring every trial against the whole working buffer — including a real canvas read-back — instead of only the pixels a candidate shape touches reaches the same accept/reject decisions, just far more slowly. Watch the shape counter crawl instead of climb: that is the entire argument for scoring only the affected region.
- Four shapes is nowhere near enough capacity to cover the target's gradients. The greedy search runs out of budget while the error is still high, so the result reads as a handful of flat coloured blobs rather than an approximation of anything — a budget problem, not a broken search.
- A rectangle's hill-climb only ever nudges its centre, half-extents or rotation — a different move set from an ellipse's radii or a triangle's vertex jitter — so at the same shape count against the same target it settles into a visibly more angular picture, not a worse one.
Clean-room implementation — written from the described algorithm, not from source. Reuse policy
What it is
primitive rebuilds a target photo as an ordered stack of solid-coloured shapes, added one at a time onto a canvas that starts as a single flat colour. Each round proposes one shape, refines it until it stops helping, paints it down for good, and moves on. A shape earns its place purely by how much it lowers the root-mean-square error against the target.
How it works
- Fill the canvas with one solid colour before adding anything.
- Propose a candidate shape and score it: composite it onto the canvas and measure root-mean-square error against the target.
- Hill-climb that shape: tweak one thing about it (a triangle’s vertex, an ellipse’s radius or centre) and rescore. “If the mutation improved the score, we keep it. Otherwise we rollback to the previous state” — that one rule is the entire search.
- Repeat step 3 many times per shape. This stays affordable because of two pieces composed into the loop: a shape’s fill colour is computed directly from the pixels it covers rather than hill-climbed, so a mutation searches geometry only; and rescoring touches only the pixels a candidate changed, not the whole canvas — which is what keeps the search practical.
- When a shape stops improving, composite it and start the next one.
The source is upfront about the weakness: “hill climbing is prone to getting stuck in local minima.” How any single shape recovers from that, beyond the mutate/rescore/rollback loop itself, isn’t covered here — an open question, not a solved one.
Parameters & tuning
Rollback isn’t optional tuning, it’s the mechanism itself — remove it and shapes drift to whatever an unlucky mutation handed them instead of converging. Which shape types are enabled sets the mutation vocabulary: a vertex nudge and a radius/centre nudge are different moves through different spaces, so a triangle-only run and an ellipse-only run look visibly different at the same shape count against the same target. And because root-mean-square error is the only judge, a patch that looks wrong to the eye but averages out over its own pixels scores exactly as well as one that looks right.
Where it’s been used
The only implementation this source evidences is Michael Fogleman’s primitive. No other named artwork applying this specific technique is evidenced here.
Variants & neighbours
Both composed pieces above are separable, and each yields a working-but-worse variant without the other. Score with full-canvas RMSE instead of the partial-difference shortcut and the output is identical, just slower — a speed trick, not a change to what gets drawn. Hill-climb the fill colour instead of computing it directly and the per-shape search space grows with no evidenced gain in the result.
Go deeper
- fogleman/primitive — README — the “How it Works” section is the primary source for everything above.
Related, in brief
Optimal color computation based on affected pixels
Compute a candidate shape's fill colour directly as the best-fit average of the target image over the pixels it covers, instead of searching for it.
Partial image difference for faster scoring
Speed up iterative image-fitting by recomputing error only over the pixels a new candidate actually changes, instead of rescoring the whole canvas per trial.
Connected to
Further reading: Genetic Programming: Evolution of Mona Lisa
Contrast with: Genetic Programming: Evolution of Mona Lisa
Steps: Optimal color computation based on affected pixels · Partial image difference for faster scoring
Requires: Optimal color computation based on affected pixels · Partial image difference for faster scoring
Try it yourself
Disable the rollback rule — accept every mutation regardless of score — and run it for a hundred shapes. What does the output look like, and why?
It stops converging. The one sentence in the README that turns this from a random walk into a search is "if the mutation improved the score, we keep it — otherwise we roll back." Remove it and every accepted mutation is as likely to raise the error as lower it, so a shape can settle into whatever position an unlucky sequence of tweaks handed it instead of settling on ones that match the target.
Run it with only triangles enabled, then again with only ellipses, same shape count both times. Why do the two outputs look different even though the scoring rule never changed?
The score is identical in both runs — same RMSE against the same target — but the mutation isn't: a triangle's hill-climb moves one vertex at a time, an ellipse's moves a radius or its centre. Different moves reach different local minima, so the two runs settle on visibly different pictures for the same number of shapes.