A stroke refinement technique can be used refine the location, orientation, and shape of input strokes by exploiting gradient features from an underlying image being traced. The technique can also be used to adjust user strokes with respect to image gradients. The stroke refinement technique can comprise a local optimization, a semi-global optimization, and a global optimization to facilitate error tolerant image optimization.