Speed up the computation of randomized algorithms for detecting lines, circles, and ellipses using novel tuning- and LUT-based voting platform

摘要

Shape detection is a fundamental problem in image processing field. In shape detection, lines, circles, and ellipses are the three most important features. In the past four decades, the robustness and the time speedup are two main concerned issues in most developed algorithms. Previously, many randomized algorithms were developed to speed up the computation of the relevant detection successfully. This paper does focus on the time speedup issue. Based on Bresenham’s drawing paradigm, this paper first presents a novel lookup table (LUT)-based voting platform. According to the proposed LUT-based voting platform, we next present a novel computational scheme to significantly speed up the computation of some existing randomized algorithms for detecting lines, circles, and ellipses. Moreover, the detailed time complexity analyses are provided for the three concerned features under our proposed computational scheme and these derived nontrivial analyses also show the relevant computational advantage. Under some real images, experimental results illustrate that our proposed computational scheme can significantly speed up the computation of some existing randomized algorithms. In average, the execution-time improvement ratios are about 28%, 56%, and 48% for detecting lines, circles, and ellipses, respectively, and these improvement ratios are vary close to the theoretic analyses.