Image completion with structure propagation is described. In one aspect, synthesized patches for an unknown region in an input image are automatically generated. The synthesized patches are generated from a known region in the input image based on information from one or more curves. The one or more curves were generated to provide missing structure to the unknown region. Structure is propagated to the unknown region with the synthesized patches.