Embodiments of the present invention provide systems, methods, and computer storage media directed at image synthesis utilizing sampling of patch correspondence information between iterations at different scales. A patch synthesis technique can be performed to synthesize a target region at a first image scale based on portions of a source region that are identified by the patch synthesis technique. The image can then be sampled to generate an image at a second image scale. The sampling can include generating patch correspondence information for the image at the second image scale. Invalid patch assignments in the patch correspondence information at the second image scale can then be identified, and valid patches can be assigned to the pixels having invalid patch assignments. Other embodiments may be described and/or claimed.