A novel vehicle re-identification (VRID) system is proposed to re-identify a vehicle without using features such as license plate, spatial-temporal cues, or 3D information based on only one still image. To detect vehicles from a still image, a symmelet-based approach is derived to determine their ROIs without using any motion feature. A symmelet is a pair of an interest point and its corresponding symmetrical one. This paper modifies the non-symmetrical SURF descriptor into a symmetrical one without adding any time complexity. In order to obtain a set of dense symmelets, a fast interest point extraction method is proposed to detect dense SURF-like points without using a Hessian matrix. After matching with the proposed symmetrical descriptor, the central line of each vehicle can be easily detected from the set of dense symmelets via a projection technique. Then, the desired vehicle ROI can be accurately located along this line. After that, a novel grid-based approach is proposed to re-identify vehicles grid-by-grid by extracting their HOG features for coarse search and refine the final result by using their HOMs (histograms of matching pairs). Without using any GPUs, the VRID system can re-identify the same vehicle very quickly (more than 25 fps) even though a HD-dimensional frame is handled. The accuracy of this VRID system is higher than 94.5% in the FECT dataset and 54.8% in the VeRi-776 dataset.