Vegetation restoration potential (VRP) assessment is an important aspect and foundation of ecological restoration projects. Neglecting the carrying capacity of the natural environment in the formulation and implementation of ecological restoration projects often leads to diminished effectiveness or even environmental damage. Existing models for VRP either overly rely on empirical knowledge, resulting in low efficiency and reproducibility, or fail to consider the nonlinear relationship between the natural environment and vegetation cover, leading to low accuracy in assessment results. Building upon existing models, this study proposes a new Vegetation Restoration Potential Mapping (VRPM) model based on a dual-variable discretization method for habitat similarity division and machine learning. Focused on Central Asia as the research area, the study evaluates the vegetation restoration potential of the region and validates the model. The results demonstrate that this model efficiently produces high-resolution and high-precision vegetation restoration potential maps. The average VRP in Central Asia is relatively low, around 36%, with most areas already having vegetation cover close to or reaching their restoration potential The regions with a higher degree of unrealized vegetation restoration potential (VRPU) are mainly distributed near human settlements, while VRPU is negative in some areas around the desert-oasis boundaries and artificial structures in the desert. The findings of this research demonstrate that the model can provide a basis for planning and implementing ecological restoration projects, thereby aiding in the health and sustainable development of ecosystems in arid regions.