EXTENDING THE HOUGH TRANSFORM THROUGH ALTERNATIVE SHAPE PARAMETERISATIONS

Available from UMI in association with The British Library.; In this thesis a programme of research is presented which concentrates on reducing the computational and memory requirements of the standard Hough transform (HT) by using alternative analytic descriptions of the shape which reduce the dimensionality of the parameter spaces required. Savings in computational effort can result since the calculations involved in computing the transform are reduced.; This thesis presents two novel Hough-based schemes; one for extracting circles and the other for ellipses. Circle extraction using the standard implementation of the HT requires a 3-dimensional accumulator array if the radius is unknown. A novel two-plane HT (TPHT) for circle extraction eliminates the requirement for a third (radius) dimension in parameter space. The TPHT uses edge tangent normal direction to map points into two accumulator planes. In application to real images, the TPHT was observed to extract circle parameters up to five times faster that the equivalent standard HT and with significantly reduced memory requirements. The direct extension of the HT to ellipses is impractical since a 5-dimensional accumulator array is required. A novel three-stage procedure for ellipse extraction based on decomposing the problem into sequentially executed stages is presented. Candidate ellipse centres are determined using an improved centre-finding method and novel Hough-based procedures extract the remaining parameters in two further stages. Although the concept of multistage parameter extraction is not new, many of the problems encountered in previous schemes are resolved. In the new technique, the dimensionality of the accumulator arrays used does not exceed two, while the range of each parameter is pre-defined. Memory savings are therefore significant. Two extensions of the three-stage procedure to multiple ellipse extraction are included. The three-stage procedure was compared with other multi-stage techniques for ellipse extraction. In tests on synthetic ellipse contours the three-stage procedure was shown to be robust both to errors in edge tangent gradient data and to outlier points in the feature space. These factors were observed to reduce the reliability of the other schemes. In application to real images, the three-stage procedure was observed to extract reliably the parameters describing ellipse contours with favourable computational requirements. (Abstract shortened by UMI.)...