VLSI Computational Structures Applied to Fingerprint Image Analysis

Abstract

Advances in integrated circuit technology have made possible the application of LSI and VLSI techniques to a wide range of computational problems. Image processing is one of the areas that stands to benefit most from these techniques. This thesis presents an architecture suitable for VLSI implementations which enables a wide range of image processing operations to be done in a real-time, pipelined fashion. These operations include filtering, thresholding, thinning and feature extraction. The particular class of images chosen for study are fingerprints. There exists a long history of fingerprint classification and comparison techniques used by humans, but previous attempts at automation have met with little success. This thesis makes use of VLSI image processing operations to create a graph structure representation (minutia graph) of the inter-relationships of various low-level features of fingerprint images. An approach is then presented which allows derivation of a metric for the similarity of these graphs and of the fingerprints which they represent. An efficient algorithm for derivation of maximal common subgraphs of two minutia graphs serves as the basis for computation of this metric, and is itself based upon a specialized clique-finding algorithm. Results of cross comparison of fingerprints from multiple individuals are presented.