With the fast development of full-field vibration measurements by using computer vision-based methods, the structural spatial characteristic deflection shapes such as mode shapes and operational deflection shapes can be readily captured. However, they are susceptive to measurement noise and not sensitive to incipient damage. To address these problems, a novel damage detection and localization method is proposed based on output-only vibration responses by improving the mode shape estimation and damage feature extraction methods. Firstly, a robust mode shape estimation method is developed by enhancing the traditional frequency domain decomposition method (FDD), which evaluates the common dominant singular vector of several power spectral density matrices around a resonant frequency as the corresponding mode shape. Moreover, the local contiguity and spatial sparsity of damage induced features are examined by using a robust principal component analysis (PCA) for more accurate damage feature extraction. In addition, numerical and experimental studies of crack damaged plates are conducted to validate the feasibility and effectiveness of the proposed damage identification method. In the experiments, the full-field vibration measurements are acquired based on binocular high-speed cameras and 3-D digital image correlation algorithm is adopted to evaluate the full-field vibration displacements. By comparing with the damage identification results based on traditional FDD and PCA methods, the damage identification results of the proposed method are more accurate and noise-robust.