An investigation of Hough Transform and genetic algorithm for multi-modal pattern recognition

The ultimate goal in computer vision is to enable a computer to understand visual information obtained from its environment. This thesis presents methods for 2D object recognition as object (pattern) recognition is one of the ways to achieve the goal. In this thesis, an investigation of the parameterization method for the Hough transform (HT) is made, and the use of Genetic Algorithm (GA) as a fast method for multi-modal pattern recognition is proposed. In the investigation of the nature and effect of the parameterization on the HT, it is found that the transform process admits inherent bias due to four factors: 1) an improper choice of parameterization equation; 2) the sampling uncertainties; 3) the image uncertainties and 4) the vote missing problem. The last factor is discovered in this thesis. To cope with the problems, a parameterization method, namely Fourier parameterization, is adopted. Instead of the conventional non-parametric form, the Fourier parameterization, which is in parametric form, is used. In this parameterization method, copies of the transformed shape are plotted on two dimensional slices of the Hough space by using a subdivision method. It is shown that the corresponding parameterization has uniform precision with respect to translation, and can avoid the above problems. Experimental results are reported which clearly demonstrates the inadequacy of the non-parametric form and the improvement achieved by the newly introduced parametric form and the subdivision method. An application of the Fourier parameterization to pattern recognition for the simplest case of unknown translation is also reported. However, HT is found to be computational and memory intensive as a pattern recognition method. In the second part of this thesis, GA is investigated and compared with HT. It is found that GA enjoys a significantly faster speed for high dimensional problems. Unfortunately, due to the stochastic nature of the GA, it does not always converge on the correct solution. This phenomenon is particularly serious in high noises image and when multiple objects are present, the so called multi-modal optimization problem. A novel GA known as Genetic Algorithm with Competitive Image Labelling (GACIL) is reported. With the concept of 'niches and species' in the proposed algorithm, the population can be effectively prevented from premature convergence, and can maintain diversity whilst searching the global optimum. Experimental results show that the proposed GACIL is more stable and has shorter convergence time than simple GA . Experimental results on the comparison between GACIL and Goldberg's sharing method for tackling multi-modal problems is also reported. It is found that Goldberg's sharing method involves parameter settings and impractical assumptions. On the contrary, GACIL does not require special settings and assumption for different problems. Moreover, species in GACK are clearly defined and the goodness of the niches can be directly reflected from the fitness of chromosomes. This simplifies the post-analysis of the population after the GA process. Furthermore, the convergence speed of the GACIL is found to be unsatisfactory for high dimensional problems. A modified version of the GACIL is therefore proposed. The algorithm is known as Genetic Algorithm with Competitive Image Labelling and Least Square (GACILLS) which employs least square (LS) as a tool to refine the results that are found by GACIL. The proposed method can be applied to solve multi-modal problems such that multiple occurrences of object instances in different orientations can be located simultaneously. From the experimental results, it is found that the convergence speed of GACIL can be improved substantially by the introduction of the LS algorithm, thus increasing the overall performance. Experimental results also show that GACILLS is applicable to real applications with arbitrary template shapes, and has the ability to solve multi-modal problems that have different peak heights and nonuniformly distributed peaks. On the other hand, experimental results on the comparison between HT and GACILLS have been obtained. It is found that as the number of variable parameters used for matching increases, GACILLS can solve the problem with much less computation time. However, GACILLS is not suitable for high noise level problems with large number of variable parameters. Further research is needed to improve the robustness of GACILLS for problems with six or larger number of variable parameters.