Pairing graph

SourceAFIS » Algorithm » Transparency » Pairing graph

Pairing, a part of algorithm transparency, matches edges and minutiae between probe and candidate fingerprints. It consists of root minutia pair, tree edges, and support edges. This structure reflects nature of the matching algorithm that recursively expands the pairing by crawling probe and candidate edge tables starting from root minutia pair. Edges that lead to newly added minutiae become part of pairing tree while other matched edges are added to the list of support edges.

Every pairing is scored and the best match is selected. Best pairing is also recorded in transparency data under separate best-pairing key.

Key	MIME	Filename in ZIP
`pairing`	`application/cbor`	`046-pairing.cbor`
`pairing`	`application/cbor`	`048-pairing.cbor`
... skipped 56 files ...
`pairing`	`application/cbor`	`162-pairing.cbor`
`pairing`	`application/cbor`	`164-pairing.cbor`
`best-pairing`	`application/cbor`	`166-best-pairing.cbor`

Visualization

Visualization of pairing graph was constructed from best pairing's CBOR data and shuffled minutiae (for probe and candidate) with original fingerprint images in the background. Visualization itself is not part of transparency data.

Pairing tree for probe and candidate fingerprint, including supporting edges — 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": 25,
    "candidate": 19
  },
  "tree": [
    {
      "probeFrom": 25,
      "probeTo": 29,
      "candidateFrom": 19,
      "candidateTo": 11
    },
    {
      "probeFrom": 29,
      "probeTo": 4,
      "candidateFrom": 11,
      "candidateTo": 18
    },
    "... skipped 25 items ...",
    {
      "probeFrom": 1,
      "probeTo": 0,
      "candidateFrom": 26,
      "candidateTo": 1
    },
    {
      "probeFrom": 38,
      "probeTo": 9,
      "candidateFrom": 34,
      "candidateTo": 15
    }
  ],
  "support": [
    {
      "probeFrom": 29,
      "probeTo": 25,
      "candidateFrom": 11,
      "candidateTo": 19
    },
    {
      "probeFrom": 4,
      "probeTo": 29,
      "candidateFrom": 18,
      "candidateTo": 11
    },
    "... skipped 138 items ...",
    {
      "probeFrom": 27,
      "probeTo": 0,
      "candidateFrom": 27,
      "candidateTo": 1
    },
    {
      "probeFrom": 2,
      "probeTo": 38,
      "candidateFrom": 17,
      "candidateTo": 34
    }
  ]
}