エッジ点対と選択ブロックの多重選択による高速化Hough変換アルゴリズムMRHTの提案 [in Japanese] High Performance Hough Transform Algorithm MRHT Using Multiple Randomization of Edge Points and Block Selection [in Japanese]
Access this Article
Search this Article
Line detection using Hough transform is one of the robust image processing methods for noisy image. But Hough transform has a problem whose computation cost is very large. In order to ease this problem, many high-speed algorithms were proposed.<br>Xu and Oja proposed RHT (Randomized Hough Transform) which reduces the computation cost by selecting the pair of the edge points at random. On the other hand, D. Ben-Tzvi and M. B. Sandler proposed CHT (Combinatorial Hough Transform) which reduces by dividing the image to some blocks and by limiting the combination of the pairs of the edge points in these blocks.<br>In this paper, we propose a new high-speed algorithm called MRHT (Multiply Randomized Hough Transform) which combines randomized edge point selection process on RHT and block division process on CHT. MRHT has two randomized selection processes. First process is randomized selection from the divided blocks at random. In second process, MRHT selects the pair of the edge points at random in the selected block in the previous selection. Thus, MRHT has multiply randomized selection process in two steps.<br>In CHT algorithm, we have to make the sacrifice of the quality of the detected lines, because we divide the image to many blocks to reduce the computation cost. Experimental and theoretical considerations revealed that MRHT becomes faster than CHT even in a low division rate, and that MRHT can provide almost the same quality of the detected lines 56 times faster than RHT.
- IEEJ Transactions on Sensors and Micromachines
IEEJ Transactions on Sensors and Micromachines 119(1), 58-66, 1999-01
The Institute of Electrical Engineers of Japan