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 :)
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.
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 :)