Embodiments of the present invention provide systems, methods, and computer storage media for improved patch validity testing for patch-based synthesis applications using similarity transforms. The improved patch validity tests are used to validate (or invalidate) candidate patches as valid patches falling within a sampling region of a source image. The improved patch validity tests include a hole dilation test for patch validity, a no-dilation test for patch invalidity, and a comprehensive pixel test for patch invalidity. A fringe test for range invalidity can be used to identify pixels with an invalid range and invalidate corresponding candidate patches. The fringe test for range invalidity can be performed as a precursor to any or all of the improved patch validity tests. In this manner, validated candidate patches are used to automatically reconstruct a target image.