Fingerprint Template Compression by Solving a Minimum Label k-Node Subtree Problem
Günther Robert Raidl, Andreas M. Chwatal, Theodore E. Simos, George Psihoyios, Ch. Tsitouras · AIP conference proceedings · 2007
We present a new approach for strongly compressing a relatively small amount of poorly structured data, as is required when embedding fingerprint template information in images of ID‐cards by means of watermarking techniques. The approach is based on the construction of a directed tree spanning a selected part of the data points and a codebook of template arcs used for a compact encoding of relative point positions. The selection of data points, the tree structure, and the codebook are simultaneously optimized by a new exact branch‐and‐cut approach or, alternatively, a faster greedy randomized adaptive search procedure (GRASP) to maximize compression. Experiments indicate that the new method can encode the required information in less space than several standard compression algorithms.