<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Python Fingerprint Example
Python is a flexible and popular language for running data analysis pipelines. In this tutorial we will implement a solution for a fingerprint matching.
Overview
Fingerprint recognition refers to the automated method for verifying a match between two fingerprints and that is used to identify individuals and verify their identity. Fingerprints (Figure 1) are the most widely used form of biometric used to identify individuals.
The automated fingerprint matching generally required the detection of different fingerprint features (aggregate characteristics of ridges, and minutia points) and then the use of fingerprint matching algorithm, which can do both one-to- one and one-to- many matching operations. Based on the number of matches a proximity score (distance or similarity) can be calculated.
We use the following NIST dataset for the study
Step1:  We'll be interacting with the operating system and manipulating files and their pathnames.
Step2:  Some general usefull utilities
Step3:  Using the attrs library provides some nice shortcuts to defining objects
Step4:  We'll be randomly dividing the entire dataset, based on user input, into the probe and gallery stets
Step5:  We'll need to call out to the NBIS software. We'll also be using multiple processes to take advantage of all the cores on our machine
Step6:  As for plotting, we'll use matplotlib, though there are many alternatives.
Step7:  Finally, we'll write the results to a database.
Step9:  Utility functions
Next, we'll define some utility functions
Step10:  Dataset
We'll now define some global parameters
First, the fingerprint dataset
Step11:  We’ll define how to download the dataset. This function is general enough that it could be used to retrieve most files, but we’ll default it to use the values from above.
Step12:  Data Model
We'll define some classes so we have a nice API for working with the dataflow. We set slots=True so that the resulting objects will be more space-efficient.
Utilities
Checksum
The checksum consists of the actual hash value (value) as well as a string representing the hashing algorithm.
The validator enforces that the algorith can only be one of the listed acceptable methods
Step13:  Path
Paths refer to an image's filepath and associated Checksum. We get the checksum "for "free" since the MD5 hash is provided for each image in the dataset.
Step14:  Image
The start of the data pipeline is the image. An image has an id (the md5 hash) and the path to the image.
Step15:  Mindtct
The next step in the pipeline is to apply the mindtct program from NBIS. A mindtct object therefore represents the results of applying mindtct on an image. The xyt output is needed fo r the next step, and the image attribute represents the image id.
Step16:  We need a way to construct a mindtct object from an image object. A straightforward way of doing this would be to have a from_image @staticmethod or @classmethod, but that doesn't work well with multiprocessing as top-level functions work best as they need to be serialized.
Step17:  Bozorth3
The final step in the pipeline is running the bozorth3 from NBIS. The bozorth3 class represents the match being done
Step18:  In order to work well with multiprocessing, we define a class representuing the input paramaters to bozorth3 and a helper function to run bozorth3. This way the pipeline definition can be kept simple to a map to create the input and then a map to run the program.
As NBIS bozorth3 can be called to compare one-to-one or one-to-many, we'll also dynamically choose between these approaches depending on if the gallery attribute is a list or a single object.
Step19:  The next is the top-level function to running bozorth3. It accepts an instance of bozorth3_input. The is implemented as a simple top-level wrapper so that it can be easily passed to the multiprocessing library.
Step20:  Running Bozorth3
There are two cases to handle
Step21:  One-to-many
Step22:  Plotting
For plotting we'll operate only on the database. We'll select a small number of probe images and plot the score between them and the rest of the gallery images.
The mk_short_labels helper function will be defined below.
Step23:  The image ids are long hash strings. In ordere to minimize the amount of space on the figure the labels occupy, we provide a helper function to create a short label that still uniquely identifies each probe image in the selected sample
Step24:  Putting it all Together
First, set up a temporary directory in which to work
Step25:  Next we download and extract the fingerprint images from NIST
Step26:  Next we'll configure the location of of the MD5 checksum file that comes with the download
Step27:  Load the images from the downloaded files to start the analysis pipeline
Step28:  We can examine one of the loaded image. Note that image is refers to the MD5 checksum that came with the image and the xyt attribute represents the raw image data.
Step29:  For example purposes we'll only a use a small percentage of the database, randomly selected, for pur probe and gallery datasets.
Step30:  We can now compute the matching scores between the probe and gallery sets.
This will use all cores available on this workstation.
Step31:  bozorth3s is now a list of lists of bozorth3 instances.
Step32:  Now add the results to the database
Step33:  We now plot the results.
<ASSISTANT_TASK:>
Python Code:
from __future__ import print_function
import urllib
import zipfile
import hashlib
Explanation: Python Fingerprint Example
Python is a flexible and popular language for running data analysis pipelines. In this tutorial we will implement a solution for a fingerprint matching.
Overview
Fingerprint recognition refers to the automated method for verifying a match between two fingerprints and that is used to identify individuals and verify their identity. Fingerprints (Figure 1) are the most widely used form of biometric used to identify individuals.
The automated fingerprint matching generally required the detection of different fingerprint features (aggregate characteristics of ridges, and minutia points) and then the use of fingerprint matching algorithm, which can do both one-to- one and one-to- many matching operations. Based on the number of matches a proximity score (distance or similarity) can be calculated.
We use the following NIST dataset for the study:
Special Database 14 - NIST Mated Fingerprint Card Pairs 2. (http://www.nist.gov/itl/iad/ig/special_dbases.cfm)
Objectives
Match the fingerprint images from a probe set to a gallery set and report the match scores.
Prerequisites
For this work we will use the following algorithms:
MINDTCT: The NIST minutiae detector, which automatically locates and records ridge ending and bifurcations in a fingerprint image. (http://www.nist.gov/itl/iad/ig/nbis.cfm)
BOZORTH3: A NIST fingerprint matching algorithm, which is a minutiae based fingerprint-matching algorithm. It can do both one-to- one and one-to- many matching operations. (http://www.nist.gov/itl/iad/ig/nbis.cfm)
In order to follow along, you must have the NBIS tools which provide mindtct and bozorth3 installed. If you are on Ubuntu 16.04 Xenial, the following steps will accomplish this:
$ sudo apt-get update -qq
$ sudo apt-get install -y build-essential cmake unzip
$ wget "http://nigos.nist.gov:8080/nist/nbis/nbis_v5_0_0.zip"
$ unzip -d nbis nbis_v5_0_0.zip
$ cd nbis/Rel_5.0.0
$ ./setup.sh /usr/local --without-X11
$ sudo make
Implementation
Fetch the fingerprint images from the web
Call out to external programs to prepare and compute the match scoreds
Store the results in a database
Generate a plot to identify  likely matches.
End of explanation
import os.path
import os
import sys
import shutil
import tempfile
Explanation: We'll be interacting with the operating system and manipulating files and their pathnames.
End of explanation
import itertools
import functools
import types
from pprint import pprint
Explanation: Some general usefull utilities
End of explanation
import attr
import sys
Explanation: Using the attrs library provides some nice shortcuts to defining objects
End of explanation
import random
Explanation: We'll be randomly dividing the entire dataset, based on user input, into the probe and gallery stets
End of explanation
import subprocess
import multiprocessing
Explanation: We'll need to call out to the NBIS software. We'll also be using multiple processes to take advantage of all the cores on our machine
End of explanation
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
Explanation: As for plotting, we'll use matplotlib, though there are many alternatives.
End of explanation
import sqlite3
Explanation: Finally, we'll write the results to a database.
End of explanation
def take(n, iterable):
    "Returns a generator of the first **n** elements of an iterable"
    return itertools.islice(iterable, n )
def zipWith(function, *iterables):
    "Zip a set of **iterables** together and apply **function** to each tuple"
    for group in itertools.izip(*iterables):
        yield function(*group)
def uncurry(function):
    "Transforms an N-arry **function** so that it accepts a single parameter of an N-tuple"
    @functools.wraps(function)
    def wrapper(args):
        return function(*args)
    return wrapper
def fetch_url(url, sha256, prefix='.', checksum_blocksize=2**20, dryRun=False):
    Download a url.
    :param url: the url to the file on the web
    :param sha256: the SHA-256 checksum. Used to determine if the file was previously downloaded.
    :param prefix: directory to save the file
    :param checksum_blocksize: blocksize to used when computing the checksum
    :param dryRun: boolean indicating that calling this function should do nothing
    :returns: the local path to the downloaded file
    :rtype:
    
    if not os.path.exists(prefix):
        os.makedirs(prefix)
    local = os.path.join(prefix, os.path.basename(url))
    if dryRun: return local
    if os.path.exists(local):
        print ('Verifying checksum')
        chk = hashlib.sha256()
        with open(local, 'rb') as fd:
            while True:
                bits = fd.read(checksum_blocksize)
                if not bits: break
                chk.update(bits)
        if sha256 == chk.hexdigest():
            return local
    print ('Downloading', url)
    def report(sofar, blocksize, totalsize):
        msg = '{}%\r'.format(100 * sofar * blocksize / totalsize, 100)
        sys.stderr.write(msg)
    urllib.urlretrieve(url, local, report)
    return local
Explanation: Utility functions
Next, we'll define some utility functions:
End of explanation
DATASET_URL = 'https://s3.amazonaws.com/nist-srd/SD4/NISTSpecialDatabase4GrayScaleImagesofFIGS.zip'
DATASET_SHA256 = '4db6a8f3f9dc14c504180cbf67cdf35167a109280f121c901be37a80ac13c449'
Explanation: Dataset
We'll now define some global parameters
First, the fingerprint dataset
End of explanation
def prepare_dataset(url=None, sha256=None, prefix='.', skip=False):
    url = url or DATASET_URL
    sha256 = sha256 or DATASET_SHA256
    local = fetch_url(url, sha256=sha256, prefix=prefix, dryRun=skip)
    if not skip:
        print ('Extracting', local, 'to', prefix)
        with zipfile.ZipFile(local, 'r') as zip:
            zip.extractall(prefix)
    name, _ = os.path.splitext(local)
    return name
def locate_paths(path_md5list, prefix):
    with open(path_md5list) as fd:
        for line in itertools.imap(str.strip, fd):
            parts = line.split()
            if not len(parts) == 2: continue
            md5sum, path = parts
            chksum = Checksum(value=md5sum, kind='md5')
            filepath = os.path.join(prefix, path)
            yield Path(checksum=chksum, filepath=filepath)
def locate_images(paths):
    def predicate(path):
        _, ext = os.path.splitext(path.filepath)
        return ext in ['.png']
    for path in itertools.ifilter(predicate, paths):
        yield image(id=path.checksum.value, path=path)
Explanation: We’ll define how to download the dataset. This function is general enough that it could be used to retrieve most files, but we’ll default it to use the values from above.
End of explanation
@attr.s(slots=True)
class Checksum(object):
  value = attr.ib()
  kind = attr.ib(validator=lambda o, a, v: v in 'md5 sha1 sha224 sha256 sha384 sha512'.split())
Explanation: Data Model
We'll define some classes so we have a nice API for working with the dataflow. We set slots=True so that the resulting objects will be more space-efficient.
Utilities
Checksum
The checksum consists of the actual hash value (value) as well as a string representing the hashing algorithm.
The validator enforces that the algorith can only be one of the listed acceptable methods
End of explanation
@attr.s(slots=True)
class Path(object):
    checksum = attr.ib()
    filepath = attr.ib()
Explanation: Path
Paths refer to an image's filepath and associated Checksum. We get the checksum "for "free" since the MD5 hash is provided for each image in the dataset.
End of explanation
@attr.s(slots=True)
class image(object):
    id = attr.ib()
    path = attr.ib()
Explanation: Image
The start of the data pipeline is the image. An image has an id (the md5 hash) and the path to the image.
End of explanation
@attr.s(slots=True)
class mindtct(object):
    image = attr.ib()
    xyt = attr.ib()
    
    def pretty(self):
        d = dict(id=self.image.id, path=self.image.path)
        return pprint(d)
Explanation: Mindtct
The next step in the pipeline is to apply the mindtct program from NBIS. A mindtct object therefore represents the results of applying mindtct on an image. The xyt output is needed fo r the next step, and the image attribute represents the image id.
End of explanation
def mindtct_from_image(image):
    imgpath = os.path.abspath(image.path.filepath)
    tempdir = tempfile.mkdtemp()
    oroot = os.path.join(tempdir, 'result')
    cmd = ['mindtct', imgpath, oroot]
    try:
        subprocess.check_call(cmd)
        with open(oroot + '.xyt') as fd:
            xyt = fd.read()
        result = mindtct(image=image.id, xyt=xyt)
        return result
    finally:
        shutil.rmtree(tempdir)
Explanation: We need a way to construct a mindtct object from an image object. A straightforward way of doing this would be to have a from_image @staticmethod or @classmethod, but that doesn't work well with multiprocessing as top-level functions work best as they need to be serialized.
End of explanation
@attr.s(slots=True)
class bozorth3(object):
    probe = attr.ib()
    gallery = attr.ib()
    score = attr.ib()
    
    @staticmethod
    def sql_stmt_create_table():
        return 'CREATE TABLE IF NOT EXISTS bozorth3' \
             + '(probe TEXT, gallery TEXT, score NUMERIC)'
        
    @staticmethod
    def sql_prepared_stmt_insert():
        return 'INSERT INTO bozorth3 VALUES (?, ?, ?)'
    
    def sql_prepared_stmt_insert_values(self):
        return self.probe, self.gallery, self.score
Explanation: Bozorth3
The final step in the pipeline is running the bozorth3 from NBIS. The bozorth3 class represents the match being done: tracking the ids of the probe and gallery images as well as the match score.
Since we'll be writing these instance out to a database, we provide some static methods for SQL statements. While there are many Object-Relational-Model (ORM) libraries available for Python, this approach keeps the current implementation simple.
End of explanation
@attr.s(slots=True)
class bozorth3_input(object):
    probe = attr.ib()
    gallery = attr.ib()
    
    def run(self):
        if isinstance(self.gallery, mindtct):
            return bozorth3_from_one_to_one(self.probe, self.gallery)
        elif isinstance(self.gallery, types.ListType):
            return bozorth3_from_one_to_many(self.probe, self.gallery)
        else:
            raise ValueError('Unhandled type for gallery: {}'.format(type(gallery)))
Explanation: In order to work well with multiprocessing, we define a class representuing the input paramaters to bozorth3 and a helper function to run bozorth3. This way the pipeline definition can be kept simple to a map to create the input and then a map to run the program.
As NBIS bozorth3 can be called to compare one-to-one or one-to-many, we'll also dynamically choose between these approaches depending on if the gallery attribute is a list or a single object.
End of explanation
def run_bozorth3(input):
    return input.run()
Explanation: The next is the top-level function to running bozorth3. It accepts an instance of bozorth3_input. The is implemented as a simple top-level wrapper so that it can be easily passed to the multiprocessing library.
End of explanation
def bozorth3_from_one_to_one(probe, gallery):
    tempdir = tempfile.mkdtemp()
    probeFile = os.path.join(tempdir, 'probe.xyt')
    galleryFile = os.path.join(tempdir, 'gallery.xyt')
    
    with open(probeFile,   'wb') as fd: fd.write(probe.xyt)
    with open(galleryFile, 'wb') as fd: fd.write(gallery.xyt)
        
    cmd = ['bozorth3', probeFile, galleryFile]
    
    try:
        result = subprocess.check_output(cmd)
        score = int(result.strip())
        return bozorth3(probe=probe.image, gallery=gallery.image, score=score)
    finally:
        shutil.rmtree(tempdir)
Explanation: Running Bozorth3
There are two cases to handle:
1. One-to-one probe to gallery sets
1. One-to-many probe to gallery sets
Both approaches are implemented below.
The implementations follow the same pattern:
1. Create a temporary directory within with to work
1. Write the probe and gallery images to files in the temporary directory
1. Call the bozorth3 executable
1. The match score is written to stdout which is captured and then parsed.
1. Return a bozorth3 instance for each match
1. Make sure to clean up the temporary directory
One-to-one
End of explanation
def bozorth3_from_one_to_many(probe, galleryset):
    tempdir = tempfile.mkdtemp()
    probeFile = os.path.join(tempdir, 'probe.xyt')
    galleryFiles = [os.path.join(tempdir, 'gallery%d.xyt' % i)
                    for i,_ in enumerate(galleryset)]
    
    with open(probeFile, 'wb') as fd: fd.write(probe.xyt)
    for galleryFile, gallery in itertools.izip(galleryFiles, galleryset):
        with open(galleryFile, 'wb') as fd: fd.write(gallery.xyt)
            
    cmd = ['bozorth3', '-p', probeFile] + galleryFiles
    
    try:
        result = subprocess.check_output(cmd).strip()
        scores = map(int, result.split('\n'))
        return [bozorth3(probe=probe.image, gallery=gallery.image, score=score)
               for score, gallery in zip(scores, galleryset)]
    finally:
        shutil.rmtree(tempdir)
Explanation: One-to-many
End of explanation
def plot(dbfile, nprobes=10):
    conn = sqlite3.connect(dbfile)
    results = pd.read_sql(
        "SELECT DISTINCT probe FROM bozorth3 ORDER BY score LIMIT '%s'" % nprobes,
        con=conn
    )
    shortlabels = mk_short_labels(results.probe)
    plt.figure()
    
    for i, probe in results.probe.iteritems():
        stmt = 'SELECT gallery, score FROM bozorth3 WHERE probe = ? ORDER BY gallery DESC'
        matches = pd.read_sql(stmt, params=(probe,), con=conn)
        xs = np.arange(len(matches), dtype=np.int)
        plt.plot(xs, matches.score, label='probe %s' % shortlabels[i])
        
    plt.ylabel('Score')
    plt.xlabel('Gallery')
    plt.legend(bbox_to_anchor=(0, 0, 1, -0.2))
    plt.show()
Explanation: Plotting
For plotting we'll operate only on the database. We'll select a small number of probe images and plot the score between them and the rest of the gallery images.
The mk_short_labels helper function will be defined below.
End of explanation
def mk_short_labels(series, start=7):
    for size in xrange(start, len(series[0])):
        if len(series) == len(set(map(lambda s: s[:size], series))):
            break
    return map(lambda s: s[:size], series)
Explanation: The image ids are long hash strings. In ordere to minimize the amount of space on the figure the labels occupy, we provide a helper function to create a short label that still uniquely identifies each probe image in the selected sample
End of explanation
pool = multiprocessing.Pool()
prefix = '/tmp/fingerprint_example/'
if not os.path.exists(prefix):
    os.makedirs(prefix)
Explanation: Putting it all Together
First, set up a temporary directory in which to work:
End of explanation
%%time
dataprefix = prepare_dataset(prefix=prefix)
Explanation: Next we download and extract the fingerprint images from NIST:
End of explanation
md5listpath = os.path.join(prefix, 'NISTSpecialDatabase4GrayScaleImagesofFIGS/sd04/sd04_md5.lst')
Explanation: Next we'll configure the location of of the MD5 checksum file that comes with the download
End of explanation
%%time
print('Loading images')
paths = locate_paths(md5listpath, dataprefix)
images = locate_images(paths)
mindtcts = pool.map(mindtct_from_image, images)
print('Done')
Explanation: Load the images from the downloaded files to start the analysis pipeline
End of explanation
print(mindtcts[0].image)
print(mindtcts[0].xyt[:50])
Explanation: We can examine one of the loaded image. Note that image is refers to the MD5 checksum that came with the image and the xyt attribute represents the raw image data.
End of explanation
perc_probe = 0.001
perc_gallery = 0.1
%%time
print('Generating samples')
probes  = random.sample(mindtcts, int(perc_probe   * len(mindtcts)))
gallery = random.sample(mindtcts, int(perc_gallery * len(mindtcts)))
print('|Probes| =', len(probes))
print('|Gallery|=', len(gallery))
Explanation: For example purposes we'll only a use a small percentage of the database, randomly selected, for pur probe and gallery datasets.
End of explanation
%%time
print('Matching')
input = [bozorth3_input(probe=probe, gallery=gallery)
         for probe in probes]
bozorth3s = pool.map(run_bozorth3, input)
Explanation: We can now compute the matching scores between the probe and gallery sets.
This will use all cores available on this workstation.
End of explanation
print('|Probes|  =', len(bozorth3s))
print('|Gallery| =', len(bozorth3s[0]))
print('Result:', bozorth3s[0][0])
Explanation: bozorth3s is now a list of lists of bozorth3 instances.
End of explanation
dbfile = os.path.join(prefix, 'scores.db')
conn = sqlite3.connect(dbfile)
cursor = conn.cursor()
cursor.execute(bozorth3.sql_stmt_create_table())
%%time
for group in bozorth3s:
    vals = map(bozorth3.sql_prepared_stmt_insert_values, group)
    cursor.executemany(bozorth3.sql_prepared_stmt_insert(), vals)
    conn.commit()
    print('Inserted results for probe', group[0].probe)
Explanation: Now add the results to the database
End of explanation
plot(dbfile, nprobes=len(probes))
cursor.close()
Explanation: We now plot the results.
End of explanation
<END_TASK>