The Story of Project AFIS: Automated Fingerprint Identification System
Inspiration
The primary inspiration for AFIS was the slow, error-prone nature of manual fingerprint processing in legacy identification systems. We aimed to develop a high-speed, highly accurate digital solution that could drastically reduce false positives and processing time in large databases, thereby enhancing security and efficiency in forensic and access control applications. Our core goal was to make biometric identification instantaneous and reliable.
How We Built It
AFIS was constructed using a combination of classical image processing techniques and modern machine learning.
- Image Processing: We used OpenCV to normalize and enhance raw fingerprint images. This included filtering, binarization, and noise reduction steps.
- Feature Extraction: We implemented a classical minutiae extraction algorithm to identify and map ridge endings and bifurcations. This data was stored as a structured vector, $V_{m}$.
- Matching Algorithm: We developed a custom $\mathbf{RANN}$ (Robust Approximate Nearest Neighbor) algorithm to quickly search and compare the minutiae vectors, $V_{m1}$ and $V_{m2}$, between a query print and the database. The match score, $S$, was calculated based on the geometric alignment and count of paired minutiae: $$S = w_c \cdot C_{pair} + w_d \cdot e^{-d_{avg}}$$ where $C_{pair}$ is the count of matched minutiae, $d_{avg}$ is the average alignment error, and $w_c, w_d$ are weighting coefficients.
- Database: All processed minutiae vectors were indexed using an optimized KD-Tree structure within a PostgreSQL database for rapid retrieval.
Challenges We Ran Into
The most significant challenge was handling poor quality and partial prints. Prints with low contrast, significant smudges, or incomplete features often led to:
- Spurious Minutiae: Noise was incorrectly identified as valid minutiae points, polluting the feature vector. We addressed this by implementing a localized ridge flow verification step.
- Rotation and Scaling Variance: Ensuring accurate matching regardless of how the finger was pressed required a robust alignment and normalization transformation before the vector comparison step.
- Speed vs. Accuracy: Optimizing the RANN algorithm to search a database of millions of records in under 100 milliseconds without sacrificing the minimum required match threshold was a constant balancing act.
What We Learned
We gained deep insights into the limitations of purely statistical matching and the necessity of combining them with image processing heuristics. We learned that the effectiveness of a biometric system relies heavily on the quality of the initial feature extraction, and that even the best matching algorithm is useless if the input features are noisy. We also mastered the art of database indexing for high-dimensional vectors to achieve sub-second search times.
Built With
- kafka
- postgresql
- rust
- scylladb
