Parallel algorithms for circle detection in images

摘要

The detection of circles in images is an important task in many computer vision applications. When the three parameters (center coordinates and radius) of a circle are quantized into O(n) values each, a sequential algorithm using the Hough transform runs with a time complexity of O(n4), where n × n is the size of the image. When information about the gradient direction is also used, the complexity of the sequential algorithm reduces to O(n3). This paper proposes three parallel algorithms for circle detection on an n × n mesh of processing elements operating in the SIMD mode. The first two algorithms use the Hough transform and the third is based on a tracing algorithm. The first algorithm uses only the gradient magnitude and takes O(n3) time. The second uses both the gradient magnitude and gradient direction and runs in O(n2) time. The third method uses a midpoint circle scan conversion algorithm and runs with a complexity of O(n2). This algorithm is the most efficient of the three. It does not use the gradient direction and offers an improvement of O(n2) over its sequential counterpart that runs in O(n4) time. When implemented with a table look-up operation, this algorithm has a low proportionality constant and offers a significant improvement in computational speed.