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.