Edge hash

SourceAFIS » Algorithm » Transparency » 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 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.

Key	MIME	Filename in ZIP
`edge-hash`	`application/cbor`	`044-edge-hash.cbor`

Visualization

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.

Format

Edge hash is a CBOR-encoded data structure consisting of a list of hash entries. Every entry has an integer key and edges list as its value. Every edge has the following fields:

length - Edge length measured in pixels on scaled image.
reference - Offset of edge's reference minutia in template's minutia list.
neighbor - Offset of edge's neighbor minutia in template's minutia list.
referenceAngle - Direction of reference minutia in radians relative to edge direction. It is zero when pointing to the neighbor minutia and increases clockwise.
neighborAngle - Direction of neighbor minutia in radians relative to edge direction. It is zero when pointing to the reference minutia and increases clockwise.

Example: 044-edge-hash.cbor

[
  {
    "key": 0,
    "edges": [
      {
        "length": 24,
        "referenceAngle": 0.1488899,
        "neighborAngle": 0.0996685,
        "reference": 35,
        "neighbor": 36
      },
      {
        "length": 24,
        "referenceAngle": 0.0996685,
        "neighborAngle": 0.14889002,
        "reference": 36,
        "neighbor": 35
      }
    ]
  },
  {
    "key": 1,
    "edges": [
      {
        "length": 32,
        "referenceAngle": 0.014924049,
        "neighborAngle": 0.014924288,
        "reference": 12,
        "neighbor": 17
      },
      {
        "length": 32,
        "referenceAngle": 0.014924288,
        "neighborAngle": 0.014924049,
        "reference": 17,
        "neighbor": 12
      },
      {
        "length": 24,
        "referenceAngle": 0.1488899,
        "neighborAngle": 0.0996685,
        "reference": 35,
        "neighbor": 36
      },
      {
        "length": 24,
        "referenceAngle": 0.0996685,
        "neighborAngle": 0.14889002,
        "reference": 36,
        "neighbor": 35
      }
    ]
  },
  "... skipped 16,056 items ...",
  {
    "key": 606339085,
    "edges": [
      {
        "length": 180,
        "referenceAngle": 0.1572504,
        "neighborAngle": 6.159598,
        "reference": 9,
        "neighbor": 27
      },
      {
        "length": 180,
        "referenceAngle": 6.1595984,
        "neighborAngle": 0.15725064,
        "reference": 27,
        "neighbor": 9
      }
    ]
  },
  {
    "key": 606339086,
    "edges": [
      {
        "length": 180,
        "referenceAngle": 0.1572504,
        "neighborAngle": 6.159598,
        "reference": 9,
        "neighbor": 27
      },
      {
        "length": 180,
        "referenceAngle": 6.1595984,
        "neighborAngle": 0.15725064,
        "reference": 27,
        "neighbor": 9
      }
    ]
  }
]