Edge hash

Edge hash, a part of algorithm transparency, is a search data structure created from minutiae of the probe fingerprint when matcher is instantiated. Edge hash stores and enables efficient search for edge shapes that can be constructed for any pair of reference and neighbor minutia. Edge shape, just like in edge table, is defined by edge length (distance between the two minutiae) and directions of the reference and neighbor minutiae relative to the edge.

Matcher uses edge hash to find matching edge shapes in probe fingerprint for randomly picked edge shapes in candidate fingerprint. When matching edge shape is found, it is used to select root pair where pairing starts. Offsets of reference and neighbor minutiae are stored together with the edge shape for this purpose.

Fast lookup is performed by splitting the three-dimensional edge shape space (length, reference angle, neighbor angle) into slots of equal size, mapping all probe shapes into these slots, and then looking up matches for candidate shapes in the appropriate slot. Probe edges are also mapped into several neighboring slots to provide some tolerance for fingerprint deformations. Slots are identified by a single number, kind of an edge hash code, that packs the three dimensions of slot position.



Visualization of edge hash was constructed from this stage's binary data and shuffled minutiae with original fingerprint image in the background. Visualization itself is not part of transparency data.

Edge hash visualized as a set of lines connecting minutiae with line color indicating edge length and minutia angles
Every line represents an edge in the edge hash. Color hue is computed from angle between minutia and the edge. Every line has two colors, one for every minutia. Shorter edges are brighter. Overall edge color represents shape of the edge. Similar color means similar edge.

Binary data

Binary data consists of key count, encoded as 32-bit big-endian integer, followed by that many keys. Key consists of shape hash followed by shape list. Shape hash is a 32-bit big-endian integer and identifies one slot in the edge hash. Shape list consists of shape count, encoded as 32-bit big-endian integer, followed by that many edge shapes.

Edge shape consists of three 32-bit big-endian integers encoding reference minutia, neighbor minutia, and edge length, followed by two 64-bit IEEE754-encoded big-endian floating-point numbers encoding relative angle of reference and neighbor minutiae.

Reference and neighbor minutiae are offsets into the minutia list. Edge length is measured in pixels on scaled image. Reference and neighbor angles are measured in radians clockwise and relative to edge angle. Edge angle is the direction of edge to the other minutia (so different for reference and neighbor minutia).

Example: 078-edge-hash.dat