The video-based frequency measurement method for bridge cable vibration offers advantages such as speed, efficiency, and noncontact compared to traditional sensor-based methods. However, the presence of complex backgrounds in video images can affect the accuracy of cable frequency measurement. To address the problem, a novel phase-based frequency measurement method is proposed, which focuses on extracting cable edge vibration from background noise in the spatial and temporal domains. First, in the spatial domain, to process the vibration signals more precisely, each video sequence is divided into multiple subregions. To enhance the edge vibration within the subregions while initially suppressing background noise, the Otsu threshold segmentation method (OTSM) is employed for subregion categorization. Subsequently, the phase-based vibration estimation method is utilized to build the spatial domain vibration representation of the subregions based on the phase differences between adjacent frames while maintaining optical flow consistency. Then, the temporal vibrational waveforms are extracted, which may still include noise from the background edges. To restore the cable vibration, a combination of singular spectrum analysis and nonnegative matrix factorization (NMF) is further designed for characterizing cable vibrations and attenuating the noise in the temporal domain. Finally, the cable vibration restored from all subregions is synthesized, forming the ultimate cable signal. The proposed method has been evaluated through extensive testing in outdoor environments, and it has exhibited remarkable enhancements in measuring cable vibration frequencies when dealing with complex background interference compared to the existing methods.