Measuring surface deformation of objects with natural patterns using digital image correlation (DIC) is difficult due to the challenges of the pattern quality and discriminative pattern matching. Existing studies in DIC predominantly focus on the artificial speckle patterns while seldom paying attention to the inevitable natural texture patterns. We propose a recursive-iterative method based on salient features to measure the deformation of objects with natural patterns. The method is proposed to select salient features according to the local intensity gradient and then to compute their displacements by incorporating the inverse compositional Gauss–Newton (IC-GN) algorithm into the classic image pyramidal computation. Compared with the existing IC-GN-based DIC technology, the use of discriminative subsets allows avoidance of displacement computation at pixels with poor spatial gradient distribution. Furthermore, the recursive computation based on the image pyramid can estimate the displacements of the features without the need for initial value estimation. This method remains effective even for large displacement measurements. The results of simulation and experiment prove the method’s feasibility, demonstrating that the method is effective in deformation measurement based on natural texture patterns.