Fingerprint recognition system curbs crime in China

Because of their well-known distinctiveness, fingerprints are one of the most widely deployed tools in the detection of crime. The Chinese Automatic Fingerprint Identification System (AFIS) was introduced as a method for detecting a criminal case more than 26 years ago. Today, every province in mainland China has established such a system with its own fingerprint database.

Nearly 300 million fingerprints are stored in province databases. The fingerprints were taken from possible suspects, including many repeat prints taken from different situations, times and locations. The total number of fingerprints continues to grow by more than 20 percent per year, including many repeat prints. In addition, more than 400 million citizens have two thumbprints recorded in their ID cards. A few years ago, the sheer volume of fingerprints hindered police when they needed fingerprint checks. The volume resulted in a loss of precision in the fingerprint system and a low speed of comparison, which restricted the further development of the AFIS.

More specifically, the matching rate was decreasing significantly; it was very difficult for the existing core algorithms to obtain identical matches for suspects when the system capacity rose to tens of millions of people and hundreds of millions of fingerprints. In addition, users had increasing expectations of high checking accuracy and speeds at the same time that the fingerprint database capacity increased, so the actual demand of police grassroots work was becoming hard to meet.

The current fingerprint checking requirement of AFIS is 800,000 fingerprints per second. To meet this, the existing system needed to use accelerator boards or parallel computers, both of which are very expensive. Additionally, the system could not guarantee effectiveness due to its high-power consumption, high pollution and high instability. Therefore, developing fast and accurate fingerprint recognition algorithms was vital.

Overview of Fingerprint Recognition

The core role of AFIS (which can be viewed as a pattern recognition system) is to determine whether two fingerprints are from the same person. To carry out this role, feature extraction and matching are the two most important steps, and a series of optimization models is used to achieve the whole process of fingerprint identification (see Figure 1).

To address the problem, a team based at the University of Chinese Academy of Sciences developed algorithms and optimization models to speed up fingerprint identification. The team made three main improvements in the following areas so the system could better handle the large-scale database: 1) estimating the fingerprint orientation field, 2) detecting singular points, and 3) fingerprint matching. These are described as follows (see also references [1] and [2]):

Estimating the fingerprint orientation field. The fingerprint orientation field is a global feature of fingerprints and plays a critical role in fingerprint enhancement, fingerprint segmentation, singular point detection, fingerprint classification, fingerprint indexing and fingerprint matching. It is clearly important to obtain a good orientation field in order to improve the performance of a fingerprint recognition system.

A global orientation field estimation method based on seed growth was developed for this purpose. First, the fingerprint is divided into overlapping blocks, and each block is enhanced by mean filtering. Good blocks that have satisfied some conditions are selected as seeds. From these seeds, a whole orientation field can be generated through an optimization model. The method is described in detail in Tiande [2].

The proposed algorithm was tested on two public test databases. The orientation field estimated by our algorithm was very similar to that marked manually by experts, which indicates that the seed growth method is valid (see Figure 2). The method was compared with several state‐of‐art approaches, and it was found that the new algorithm performed well for both good and poor-quality fingerprints [2].

Detecting singular points. The common strategy to speed up the search in databases of over hundreds of millions of fingerprints is fingerprint classification, which only requires a fingerprint to be compared with the fingerprints in the corresponding class. Fingerprint classification is generally based on global features, especially singularities including core and delta ([1], see Figure 3). 

From the Galton-Henry classification [1] method, a fingerprint can be simply classified into several classes according to the number and position of the singularities (see Figure 4). Singular points of fingerprints are those that are invariant to translation, rotation, enlargement and shrinking. There are some simple methods that can be used to detect singularity, but they are easily affected by noise and other problems.

Inspired by the zero-pole model [5], which generates an orientation field based on the location and number of known singularities, a new model was developed by the team to find the location and number of singularities and overcome existing problems [3]. Based on the minimum error between the orientation fields by direct estimation and the zero-pole model, a variable dimension optimization model was proposed. In this model the number and position of singular points are decision variables and the number of decision variables is variable.

The optimal solution of this model is the position and number of determined singular points [2]. This model is very difficult to solve. According to the characteristics of the fingerprint, it must be transformed to the complex plane and solved using a Hough transformation. Finally, each singular point is refined by solving the corresponding optimization model constrained with its own search window.

The proposed models and algorithms were tested on two public fingerprint databases. The results show the method to be fairly robust to noise [2].

Fingerprint matching by minutiae. Fingerprint matching by minutiae is the comparison of two fingerprint images and the calculation of a similarity score that represents the probability of a match between the two. There is a risk, however, that spurious matching may occur because it is processed locally without reference to global information. These spurious matchings seriously affect the results, so a novel and efficient algorithm was proposed based on a convex hull method for eliminating spurious matches [4]. An example is shown in Figure 5. Compared with the results of other algorithms, the performance of the revised algorithm is good [4].

Impact of the New System

The Golden Automatic Fingerprint Identification System (GAFIS), using the models and algorithms mentioned in this article, is now used in many provinces of China. The optimization models and algorithms developed by the team have increased the speed of the GAFIS 20-fold while keeping the accuracy unchanged. The old GAFIS version could only search a database of 5-8 million people and needed 40 servers. But the updated version based on the new algorithms is being used in the 12-15 million people database and only needs 10 servers.

GAFIS has been successfully used in the forensic systems of many provinces and cities in China, including Shanghai, Chongqing cities, Jiangxi, Liaoning, Xinjiang, Guizhou and Shandong provinces. As of 2015, these forensic systems cracked about 370 A-cases (A-case is an emergency, a very serious case, or a malignant case), 2,400 B-cases (B-case is a serious case such as murder) and 90,000 other cases, through successful fingerprint matching.

Between 2005 and 2015, Shanghai captured more than 1,500 criminal suspects and cleared up more than 3,000 cases each year using GAFIS. During the same time frame, Shanghai directly cracked at least six murder cases through direct archival inquiry and fingerprint matching. Since 2009, Jiangxi province has cleared more than 1,800 important joint investigations using GAFIS. GAFIS has achieved important results in criminal investigation, public security, anti-terrorism and other fields.

According to the Fingerprint Office of Criminal Science Research & Management Center of Shanghai Public Security Bureau, “The operation and application of the system has given very important technical support to the maintenance of social stability and the effective fight against crime in Shanghai.” The team responsible for the GAFIS models and algorithms was runner-up in the 2017 IFORS Prize Competition and commended for their innovative work. Team members included: Tian-De Guo, Congying Han, Tong Zhao, Yong A, Chao-Chao Bai, Si-Qi Tang and Min Wu.

Note: A version of this article appeared in the IFORS Newsletter. Reprinted with permission.

References

1. Maltoni, D., Maio, D., Jain, A., and Prabhakar, S., 2009, “Handbook of fingerprint recognition,” Springer Science & Business Media.
2. Tiande, G., Congying, H., et al., “Optimization Models and Algorithms for Fingerprint Recognition and Its Applications in AFIS of China,” submitted to International Transactions in Operational Research.
3. Lingling, F., Shuguang, W., Hongfa, W., and Tiande, G., 2008, “Singular Points Detection Based on Zero-Pole Model in Fingerprint Images,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 6, pp. 1-12.
4. Chengming, W., Tiande, G., 2009, “An efficient algorithm for fingerprint matching based on convex hulls,” Proceedings of the 2009 International Conference on Computational Intelligence and Natural Computing, pp. 66-69.
5. Sherlock, B. and Monro, D., 1993, “A Model for Interpreting Fingerprint Topology,” Pattern Recognition, Vol. 26, pp. 1047-1055.