Orientation-based discrete Hough transform for line detection with low computational complexity

• We present two strategies to reduce the computational complexity of the DHT.
• The first strategy takes constant time to select an appropriate parameter space.
• The second strategy narrows down the parameter space to speed up the voting process.
• Experiments confirm the high-speed and high-accuracy advantages of two strategies.

Using discrete representation of line segments, recently Lee and Park presented an efficient discrete Hough transform (DHT) to improve the robustness of the standard HT (SHT). However, the DHT has much higher computational complexity than the SHT. In this paper, we present an orientation-based DHT (ODHT) which consists of two strategies, the parameter space-selection strategy and the voting space-reduction strategy, to substantially reduce the computational complexity of the DHT. Besides its low computational merit, the proposed ODHT can also improve the detection accuracy of the DHT. Experimental results demonstrated that the proposed ODHT leads to 79.26%79.26% average execution-time improvement ratio and better detection accuracy when compared with the state-of-the-art DHT by Lee and Park.