In this paper, we address the problem of non-parametric template matching which does not assume any specific deformation models. In real-world matching scenarios, deformation between a template and a matching result usually appears to be non-rigid and non-linear. We propose a novel approach called local rigidity constraints (LRC). LRC is built based on an assumption that the local rigidity, which is referred to as structural persistence between image patches, can help the algorithm to achieve better performance. A spatial relation test is proposed to weight the rigidity between two image patches. When estimating visual similarity under an unconstrained environment, high-level similarity (e.g. with complex geometry transformations) can then be estimated by investigating the number of LRC. In the searching step, exhaustive matching is possible because of the simplicity of the algorithm. Global maximum is given out as the final matching result. To evaluate our method, we carry out a comprehensive comparison on a publicly available benchmark and show that our method can outperform the state-of-the-art method.