[Back]

A Chwatal, G. Raidl, K. Oberlechner:
"Solving a k-node minimum label spanning arborescence problem to compress fingerprint templates.";
Journal of Mathematical Modelling and Algorithms, Volume 8 (2009), 3; 293 - 334.

We present a novel approach for compressing relatively small unordered data sets by means of combinatorial optimization. The application background comes from the field of biometrics, where the embedding of fingerprint template data into images by means of watermarking techniques requires extraordinary compression techniques. The approach is based on the construction of a directed tree, covering a sufficient subset of the data points. The arcs are stored via referencing a dictionary, which contains "typical" arcs w.r.t. the particular tree solution. By solving a tree-based combinatorial optimization problem we are able to find a compact representation of the input data. As optimization method we use on the one hand an exact branch-and-cut approach, and on the other hand heuristics including a greedy randomized adaptive search procedure (GRASP) and a memetic algorithm. Experimental results show that our method is able to achieve higher compression rates for fingerprint (minutiae) data than several standard compression algorithms.

http://dx.doi.org/10.1007/s10852-009-9109-1

http://publik.tuwien.ac.at/files/PubDat_179005.pdf