Mixed-radix fast fourier transform for biometric identification system

• Main Author: Sunil Vaishnav
• Other Authors: Li Fang
• Format: Final Year Project
• Language: English
• Published: 2014
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: http://hdl.handle.net/10356/59215
• Institution: Nanyang Technological University

Personal identification and verification based on two-dimensional features is beginning to find wider applications in today’s world. This primarily includes palmprint matching and vein matching systems. There exists a trade-off between discriminative power and user-friendliness of these systems. This leads to very restrictive applications of biometric identification. The system being explored in this work deals with developing an RST invariant algorithm to mitigate problems of distorted lines and lower-quality images. In the matching process, the brute-force matching between the test and the model image is too computationally expensive. To improve efficiency, we have to do coarse-matching to narrow down the searching scope. Here, The Fourier Transform is instrumental. The Fourier Transform is an important image-processing tool which is used to decompose an image into its sine and cosine components. It transforms one function into another, which is called the frequency domain representation or the Fourier. Since computers only deal with discrete signals, the discrete fourier transform is implemented. The original function is in its spatial domain or time domain equivalent. In this new domain image, each point represents a particular frequency contained in the spatial domain image. By representing the significant transform co-efficients obtained, system time and complexity will be greatly reduced. The original system contains a brute-force implementation of the Discrete Fourier Transform algorithm which is computationally expensive and inefficient. This work is concerned with developing a mixed-radix algorithm that would perform those computations more efficiently with a reduced number of operations. Since there are 180 points in the system, which happens to be a non-power of 2, standard radix implementation of the algorithm does not work. Hence, a customized mixed-radix algorithm is designed which improves efficiency for this specific case. Mixed radix algorithm involves factorizing the number N and splitting the operations by its factors.