Vehicle re-identification is a demanding and challenging task in automated surveillance systems. The goal of vehicle re-identification is to associate images of the same vehicle to identify re-occurrences of the same vehicle. Robust re-identification of individual vehicles requires reliable and discriminative features extracted from specific parts of the vehicle. In this work, we construct an efficient and robust wheel detector that precisely locates and selects vehicular wheels from vehicle images. The associated hubcap geometry can hence be utilized to extract fundamental signatures from vehicle images and exploit them for vehicle re-identification. Wheels pattern information can yield additional information about vehicles in questions. To that end, we utilized a vehicle imagery dataset that has thousands of side-view vehicle collected under different illumination conditions and elevation angles. The collected dataset was used for training and testing the wheel detector. Experiments show that our approach could detect vehicular wheels accurately for 99.41% of the vehicles in the dataset.