Circle Fitting Algorithm Optimization through the Iterative Hough Transform

Overview

Detection of an object, such as a line or a circle, is one of the major components of computer vision applications. The Hough Transform utilizes a voting procedure to identify arbitrary objects in an image according to pre-determined parameters to describe the shape. Recognition of the quadratic complexity – O(n^2) – of the Hough Transform has led to this research, which incorporated the iterative method into the Hough Transform to reduce the complexity of the algorithm to O(n). The traditional Hough Transform requires an examination of all possible points in the parameter space in order to fit a circle in the first trial. On the other hand, refinement through the iterative method using decreasing detection windows yields a constant amount of computation required for each trial, thus yielding O(n). The degree of accuracy is not compromised due to multiple iterations, whose Windows zoom in to the point in the parameter space that represents the fitted circle each time. The hand-coded Hough Transform in Wolfram Mathematica has allowed manual optimization and experiments to develop the iterative Hough Transform. This research successfully reduced the complexity of the traditional Hough Transform to O(n) using the iterative method, securing computing time, memory space, and accuracy.

Competition history

• ISEF 2015 Category not listed · Entry SOFT043I

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.