A Caltech Library Service

VLSI Computational Structures Applied to Fingerprint Image Analysis


Megdal, Barry Bruce (1983) VLSI Computational Structures Applied to Fingerprint Image Analysis. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/9tyn-bc11.


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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Computer Science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Mead, Carver
Thesis Committee:
  • Johnsson, S. Lennart (chair)
  • Fox, Geoffrey C.
  • Kajiya, James Thomas
  • Mead, Carver
  • Wilts, Charles Harold
Defense Date:8 February 1983
Funding AgencyGrant Number
Hughes Aircraft CompanyUNSPECIFIED
Office of Naval Research (ONR)UNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Record Number:CaltechTHESIS:03202012-091934255
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6855
Deposited By: Benjamin Perez
Deposited On:20 Mar 2012 18:40
Last Modified:09 Nov 2022 19:20

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page