A branch-and-cut-and-price algorithm for a fingerprint-template compression application

In this work we present a branch-and-cut-and-price algorithm for the compression of fingerprint minutiae templates, in order to embed them into passport images by watermarking techniques as an additional security feature. For this purpose the minutiae data, which is a set of characteristic points of the fingerprint, is encoded by a spanning tree whose edges are encoded efficiently by a reference to an element in a dictionary (template arc) and a small correction vector. Our proposed branch-and-cut-and-price algorithm creates meaningful template arcs from a huge set of possible ones on demand in the pricing-procedure. Cutting-planes are separated in order to obtain connected subgraphs from which spanning trees can then be easily deduced. Our computational experiments confirm the superior performance of the algorithm in comparison to previous approaches for the spanning tree based encoding scheme.