Coherent change detection (CCD) images, which are products of combining two synthetic aperture radar (SAR) images taken at different times of the same scene, can reveal subtle surface changes such as those made by tire tracks. These images, however, have low texture and are noisy, making it difficult to automate track finding. Existing techniques either require user cues and can only trace a single track or make use of templates that are difficult to generalize to different types of tracks, such as those made by motorcycles, or vehicles sizes. This paper presents an approach to automatically identify vehicle tracks in CCD images. We identify high-quality track segments and leverage the constrained Delaunay triangulation (CDT) to find completion track segments. We then impose global continuity and track smoothness using a binary random field on the resulting CDT graph to determine edges that belong to real tracks. Experimental results show that our algorithm outperforms existing state-of-the-art techniques in both accuracy and speed.