Pairing tree in SourceAFIS transparency data

SourceAFIS » Algorithm » Transparency » Pairing tree

Pairing, a part of algorithm transparency, is a list of minutia pairs, one minutia from probe fingerprint and one from candidate fingerprint, constructed during matching several times, once for every root. First pair in the pairing is the root. Other pairs are found recursively by comparing edges from edge tables of both fingerprints. Minutiae thus form a tree, structured the same way in both fingerprints, that shows path from root pair to every minutia pair in the pairing. Besides minutia pairs and edges that link them to parent pair, pairing also includes list of supporting edges that would lead to the same pairing. Every pairing is scored and the best match is selected.

Key	MIME	Filename in ZIP
`pairing`	`application/cbor`	`046-pairing.cbor`
`pairing`	`application/cbor`	`048-pairing.cbor`
... skipped 48 files ...
`pairing`	`application/cbor`	`146-pairing.cbor`
`pairing`	`application/cbor`	`148-pairing.cbor`

Visualization

Visualization of pairing tree was constructed from this stage's CBOR data and shuffled minutiae (for probe and candidate) with original fingerprint images in the background (for probe and candidate). Since pairings appear several times in transparency data, the best one was chosen for visualization according to best match data. Visualization itself is not part of transparency data.

Probe fingerprint is left, candidate is right. Blue points are root minutiae. Other minutiae are red. Green lines represent pairing tree. Yellow lines are supporting edges.

Format

Pairing is a CBOR-encoded data structure representing the fully constructed pairing that contains:

root - Root pair where the pairing process started. This is one of the entries in the root list with corresponding structure.
tree - Pairing tree rooted in root pair. The tree is a set of edges. Edge structure is described below.
support - List of edges that are not part of the pairing tree but that are still consistent with the tree. Supporting edges only connect minutiae that are already part of the pairing tree. Edge structure is described below.

Both tree and support are lists of edges with the following structure:

probeFrom - Reference (starting) minutia in the probe template.
probeTo - Neighbor (ending) minutia in the probe template.
candidateFrom - Reference (starting) minutia in the candidate template.
candidateTo - Neighbor (ending) minutia in the candidate template.

Example: 046-pairing.cbor

{
  "root": {
    "probe": 0,
    "candidate": 2
  },
  "tree": [
    {
      "probeFrom": 0,
      "probeTo": 1,
      "candidateFrom": 2,
      "candidateTo": 28
    },
    {
      "probeFrom": 1,
      "probeTo": 18,
      "candidateFrom": 28,
      "candidateTo": 30
    },
    "... skipped 24 items ...",
    {
      "probeFrom": 22,
      "probeTo": 8,
      "candidateFrom": 33,
      "candidateTo": 37
    },
    {
      "probeFrom": 8,
      "probeTo": 28,
      "candidateFrom": 37,
      "candidateTo": 36
    }
  ],
  "support": [
    {
      "probeFrom": 1,
      "probeTo": 0,
      "candidateFrom": 28,
      "candidateTo": 2
    },
    {
      "probeFrom": 18,
      "probeTo": 1,
      "candidateFrom": 30,
      "candidateTo": 28
    },
    "... skipped 131 items ...",
    {
      "probeFrom": 44,
      "probeTo": 28,
      "candidateFrom": 22,
      "candidateTo": 36
    },
    {
      "probeFrom": 2,
      "probeTo": 28,
      "candidateFrom": 19,
      "candidateTo": 36
    }
  ]
}