One embodiment of the present invention provides a system that detects an object in an image. During operation, the system determines a relationship between sampling parameters and a detection rate for an object detection process. The system also determines a relationship between the sampling parameters and a detection speed for the object detection process. The system uses the determined relationships to generate specific sampling parameters. Next, the system performs the object detection process, wherein the object detection process uses the sampling parameters to sample locations in the image. This sampling process is used to refine the search for the object by identifying locations that respond to an object detector and are hence likely to be proximate to an instance of the object.