Linear Time Construction of Vectorial Object Boundaries

N. Lovell and J. Fenwick (Australia)


Computer Vision, Artificial Intelligence Applications, Image Segmentation, Pattern Recognition.


Classical algorithms for identifying straight edges within an image, such as the Hough transform, run in O(n2) time which has been improved to O(nlog2(n)) by other heuris tic algorithms. By focusing on 8-connected space rather than Euclidean space, we present a method for classifying a connected list of pixels as either straight or non-straight in constant time. We then build on this method to enable a heuristic algorithm to identify the straight edges within in an image in linear time. Although the improvement from O(nlog2(n)) to O(n) time does not appear great we find that our algorithm is faster than others even on small im ages due to the large amount of data required to represent an image. As images become larger or as the number of straight edges in each image increases our improvement be comes more pronounced. Our algorithm then enables fast construction of vectorial object boundaries and medial axes which, in turn, enables efficient object recognition. We illustrate this with images from RoboCup.

Important Links:

Go Back