Real-time needle segmentation and tracking is very important in image-guided surgery, biopsy, and therapy. Due to its robustness to the addition of extraneous noise, the Hough Transform is one of the most powerful line-detection techniques nowadays and has been widely used in different areas. Unfortunately, its high computation needs often prevent it from being applied in real-time applications without the help of specially designed hardware. In order to solve this problem, a variety of fast implementation algorithms have been proposed. However, none of them can be performed in a real time on an affordable computer. In this paper, we describe a fast implementation of the Hough Transform based on coarse-fine search and the determination of the optimal image resolution. Compared to conventional techniques, our approach decreases the time for needle segmentation by an order of magnitude. Experiments with agar phantom and patient breast biopsy ultrasound (US) image sequences showed that our approach can segment the biopsy needle in real time (i.e., less than 33 ms) on an affordable PC computer without the help of specially designed hardware with the angular rms error of about 1 degrees and the position rms error of about 0.5 mm.