sexta-feira, 11 de dezembro de 2015

Evaluating NIST Biometric Image Software (NBIS) using FVC2004 Databases - Part 2

This series of articles aim at evaluating NBIS biometric software by using it against fingerprint image databases from FVC2004 verification competition.



WARNING: If you have not yet read the first article, I hardly suggest you to do so: Evaluating NIST Biometric Image Software (NBIS) using FVC2004 Databases - Part 1.

Considering you have already followed the steps made in the first article, which included installing NBIS and downloading FVC2004 databases, open a terminal and type these commands: 

source nbis-env.sh

cd images/

3. Lights, camera, action!


3.1. Converting TIFF images to WSQ format

The first step on our biometric journey is to convert fingerprint image files into a format called WSQ (Wavelet Scalar Quantization) [11]. The WSQ algorithm is based on wavelet theory and has become a standard for the exchange and storage of fingerprint images. It was developed by the FBI, the Los Alamos National Laboratory, and the National Institute of Standards and Technology (NIST).

NBIS provides a tool called CWSQ to compress grayscale fingerprint images using WSQ algorithm. We'll use it in this section.

In our case of FVC2004 databases, fingerprint image files are offered in TIFF format. We'll select a single one to test NBIS tools: "db1/101_1.tif". You could display this fingerprint image by issuing (or your preferred image viewer): 

qiv db1/101_1.tif


As the image is in TIFF file format, we need to know its dimensions before invoking CWSQ. Therefore, type this: 

identify db1/101_1.tif

db1/101_1.tif TIFF 640x480 640x480+0+0 8-bit Grayscale DirectClass 308KB 0.000u 0:00.009

The command output means that the image we chose is really a TIFF format, has 640 of width and 480 of height in pixels, and is in 8-bit Grayscale.

Finally, call the CWSQ program using these arguments (.75 stands for a 15:1 compression rate): 

cwsq .75 wsq db1/101_1.tif -r 640,480,8

If successful, it will produce a new file with the extension ".wsq" (11 kB) in the same directory of the ".tif" (301 kB) file: 

ls -la db1/101_1.*

NBIS provides a WSQ viewing tool called DPYIMAGE. Try running it to see the resulting WSQ file: 

dpyimage db1/101_1.wsq

Once we could convert a single TIFF image into a WSQ specific format, let's do the same throughout all four FVC2004 databases. As each database has distinct dimensions, we need to specify them separately: 

find db1/ -name "*.tif" -exec cwsq .75 wsq {} -r 640,480,8 \;
find db2/ -name "*.tif" -exec cwsq .75 wsq {} -r 328,364,8 \;
find db3/ -name "*.tif" -exec cwsq .75 wsq {} -r 300,480,8 \;
find db4/ -name "*.tif" -exec cwsq .75 wsq {} -r 288,384,8 \;

You can verify whether all WSQ files were created by issuing this command: 

find -name "*.wsq" | head

./db1/108_4.wsq
./db1/109_2.wsq
./db1/102_2.wsq
./db1/109_5.wsq
./db1/101_4.wsq
./db1/104_4.wsq
./db1/104_8.wsq
./db1/103_2.wsq
./db1/110_4.wsq
./db1/109_8.wsq

3.2. Checking quality of WSQ images through NFIQ

Another interesting NIST algorithm to test is NIST Fingerprint Image Quality (NFIQ) [12], which also comes with the NBIS bundle.

NFIQ, a fingerprint image quality algorithm, analyses a fingerprint image and assigns to it a quality value on a scale of 1 (highest quality) to 5 (lowest quality). Higher quality images produce significantly better performance with matching algorithms. That's exactly why NFIQ is so important to biometric applications: it can be employed to assure fingerprint images are being collected with an acceptable quality.

As we have already produced WSQ files, the synthax for NFIQ is quite simple. Just execute this: 

nfiq db1/101_1.wsq

By the output value ("2"), we can assume the biometric quality for the given image is quite good.

If we would want to check the quality of our entire dataset, we could execute the following Shell Script: 

for i in `seq 1 4`
do
  for a in db$i/*.wsq
  do
    echo "$a"
    #nfiq $a
  done
done

3.3. Extracting features from fingerprints through MINDTCT

In an Automated Fingerprint Identification System (AFIS), there are two major biometric algorithms that play an indispensable role: 1) the features extractor (or simply "extractor") and 2) the templates matcher (or simply "matcher"). We'll start by the extractor: in the case of NBIS, it is embedded in a program called MINDTCT [1].

NBIS bundle provides MINDTCT, a minutiae detector, which automatically locates and records ridge ending and bifurcations in a fingerprint image [13, 15]. This system includes minutiae quality assessment based on local image conditions. The FBI's Universal Latent Workstation uses MINDTCT, and it too is the only known no cost system of its kind [16].

The program MINDTCT takes a WSQ compressed image file, processes the fingerprint image and automatically detects minutiae [16].

Considering the file "db1/101_1.wsq" we generated previously, we could invoke MINDTCT in order to extract the features: 

mindtct -b -m1 db1/101_1.wsq db1/101_1

The result of the last instruction is a bunch of other files with the same prefix and in the same directory. Check it out: 

find db1/101_1.*

db1/101_1.brw
db1/101_1.dm
db1/101_1.hcm
db1/101_1.lcm
db1/101_1.lfm
db1/101_1.min
db1/101_1.qm
db1/101_1.tif
db1/101_1.wsq
db1/101_1.xyt

One of these files is of special interest to us: the one with the ".xyt" extension. Take a look of its contents: 

head db1/101_1.xyt

85 102 0 13
86 142 174 12
88 90 0 13
104 79 0 35
111 92 90 36
120 31 17 82
129 54 5 39
135 176 90 78
136 143 84 74
140 30 95 42

In this ".xyt" file created by the MINDTCT program, the minutiae values are written in "x y theta quality" format, each minutia per line. This file format is what NBIS matcher program, BOZORTH3, considers. We'll use it further in this article.

Likewise, we could extract the features of the entire dataset, by executing this small Shell Script: 

for i in `seq 1 4`
do
  for a in db$i/*.wsq
  do
    echo "$a"
    b="${a/.wsq/}"
    mindtct $a $b
  done
done

After a little while, you can verify whether all XYT files were created by issuing this command: 

find -name "*.xyt" | head

./db1/103_3.xyt
./db1/109_4.xyt
./db1/106_1.xyt
./db1/108_1.xyt
./db1/102_5.xyt
./db1/104_5.xyt
./db1/102_1.xyt
./db1/105_4.xyt
./db1/105_3.xyt
./db1/102_4.xyt

3.4. Performing fingerprint matches through BOZORTH3

Now that we have extracted the minutiae from every fingerprint image in the dataset, we can finally use the matcher algorithm. In the case of NBIS, it is embedded in a program called BOZORTH3 [1].

NBIS bundle provides BOZORTH3, a fingerprint matching system. It uses the minutiae detected by MINDTCT to determine if two fingerprints are from the same person, same finger [14]. It can analyze fingers two at a time or run in a batch mode comparing a single finger (probe) against a large database of fingerprints (gallery).

The program BOZORTH3 computes match scores from fingerprint minutiae files. The files are expected to be in xyt-format, a simple text file format that is produced by the minutiae detector program MINDTCT, which is also part of the NBIS distribution.

Considering the specific file "db1/101_1.xyt" we generated previously, as well as all others ".xyt" in that same directory, we could invoke BOZORTH3 in order to compare the fingerprint "101_1.tif" with the rest images in the same database (i.e., residing in "db1/" directory): 

bozorth3 -m1 -A outfmt=spg -T 20 -p db1/101_1.xyt db1/*.xyt

271 db1/101_1.xyt db1/101_1.xyt
59 db1/101_1.xyt db1/101_2.xyt
25 db1/101_1.xyt db1/101_4.xyt

The output states that there are 3 possible fingerprint candidates that match the "101_1.tif" probe, where the first value is the number representing the matching score. As a good practice, we set a match score threshold (note the "-T 20" argument) in the matcher. Once the threshold is specified, only match scores meeting or exceeding that value are printed.

The first line represents exactly the same image as the probe ("101_1"). That explains the highest score value. The remaining two are fingerprints that the matching algorithm identified as possibly the same, "101_2" having higher probability than "101_4".

But as we know by the FVC2004 database, there are 8 versions for each fingerprint, which means in an ideal AFIS system all them should be listed: 

find db1/101_?.xyt

db1/101_1.xyt
db1/101_2.xyt
db1/101_3.xyt
db1/101_4.xyt
db1/101_5.xyt
db1/101_6.xyt
db1/101_7.xyt
db1/101_8.xyt


Well, that is an issue concerning "Error Rates" in security systems, particularly "False Acceptance Rate (FAR)" and "False Rejection Rate (FRR)", but that is a whole new subject I'll keep for another article. :D

At least other fingerprint images in the same dataset (e.g., "102_*", "103_*", etc) didn't have high scores by the matcher algorithm.

In other words, in this case of NBIS algorithms against FVC2004 database, we are facing a high FRR value (i.e., many genuine fingerprints don't match) and a low FAR value (i.e., it is difficult to a fake fingerprint match).

If we would want to compute the matches of our entire dataset, considering each fingerprint as a probe at a time, we could execute the following Shell Script: 

for i in `seq 1 4`
do
  for a in db$i/*.xyt
  do
    echo "[$a]"
    bozorth3 -m1 -A outfmt=spg -T 20 -p $a db$i/*.xyt
    echo
  done
done

For instance, note how good is the matching score for the fingerprint named "104_4.tif" in the "db3" dataset: 

[db3/104_4.xyt]
80 db3/104_4.xyt db3/104_1.xyt
59 db3/104_4.xyt db3/104_2.xyt
136 db3/104_4.xyt db3/104_3.xyt
948 db3/104_4.xyt db3/104_4.xyt
113 db3/104_4.xyt db3/104_5.xyt
72 db3/104_4.xyt db3/104_7.xyt
61 db3/104_4.xyt db3/104_8.xyt


4. Summing up


4.1. A complete Shell Script

In order to reproduce all the steps explained before, I suggest you to create a single Shell Script, named "02-run-nbis.sh", inside the "images/" directory, with the following content: 

#!/bin/bash

if ! which bozorth3
then
  echo "NBIS programs not in shell path"
  exit 1
fi

echo "Converting TIFF images to WSQ format..."
find db1/ -name "*.tif" -exec cwsq .75 wsq {} -r 640,480,8 \;
find db2/ -name "*.tif" -exec cwsq .75 wsq {} -r 328,364,8 \;
find db3/ -name "*.tif" -exec cwsq .75 wsq {} -r 300,480,8 \;
find db4/ -name "*.tif" -exec cwsq .75 wsq {} -r 288,384,8 \;

echo "Checking quality of WSQ images through NFIQ..."
for i in `seq 1 4`
do
  for a in db$i/*.wsq
  do
    echo "$a"
    nfiq $a
  done
done

echo "Extracting features from fingerprints through MINDTCT..."
for i in `seq 1 4`
do
  for a in db$i/*.wsq
  do
    echo "$a"
    b="${a/.wsq/}"
    mindtct $a $b
  done
done

echo "Performing fingerprint matches through BOZORTH3..."
for i in `seq 1 4`
do
  for a in db$i/*.xyt
  do
    echo "[$a]"
    bozorth3 -m1 -A outfmt=spg -T 20 -p $a db$i/*.xyt
    echo
  done
done

exit 0

Then you should give the file proper permissions and run it using the following instructions: 

source nbis-env.sh

cd images/

chmod +x 02-run-nbis.sh

./02-run-nbis.sh

That's all for today, folks! We have reached the end of our article. I hope you enjoyed achieving the proposed tasks, as much as I enjoyed writing them. :D


References

Postado por Rodrigo HJORT às 16:07
Marcadores: , , , , , , , , , , , , , , , , , ,