Compressing fingerprint templates by solving the k-node minimum label spanning arborescence problem by branch-and-price

Abstract

Diese Diplomarbeit beschäftigt sich mit der Entwicklung neuer exakter Algorithmen zur Kompression von Fingerabdrucks-Minutien-Daten.<br />Ausgangslage ist ein neuer Kompressionsansatz für kleine ungeordnete Punktmengen mittels Kombinatorischer Optimierung, welcher schon zuvor im Zuge dieses laufenden Forschungsprojekts entwickelt wurde. Die Punkte werden hierbei durch einen Spannbaum kodiert dessen Kanten durch einen Verweis in ein Wörterbuch und einer entsprechenden Korrektur gespeichert werden. Das entstehende Modell ist eine Erweiterung des bekannten Minimum Label Spanning Tree Problems. Anwendungshintergrund ist die Einbettung der Fingerabdrucks-Minutien-Daten in Passbilder anhand von Watermarking-Techniken als zusätzliches Sicherheitsmerkmal.<br />Ziel dieser Arbeit war die Entwicklung neuer, verbesserter exakter Algorithmen basierend auf Techniken der Mathematischen Programmierung zur Lösung des Problems. Das aufwändige Preprocessing eines existierenden Branch-and-Cut Algorithmus wurde direkt in den Lösungsprozess des Mixed Integer Models eingebunden. Hierbei werden während der Ausführung des Branch-and-Bound Algorithmus zur Lösung des Fluss-Modells fortwährend neue Variablen generiert. Derartige Ansätze nennt man Branch-and-Price und das entsprechende Subproblem der Erzeugung neuer Variablen das Pricing Problem.<br />Die Bestimmung neuer Variablen welche die Zielfunktion potentiell verbessern können bedarf schneller Algorithmen, da dieser Schritt oftmals ausgeführt wird. Das konkrete Pricing Problem wird anhand einer k-d Tree Datenstruktur gelöst, welche die Ausschöpfung geometrischer Eigenschaften der Eingabedaten ermöglicht. Der Baum wird jedes mal gemäß der Information der, durch die lineare Relaxierung gegebenen, numerischen Werte traversiert.<br />Der resultierende Branch-and-Price Algorithmus stellt eine klare Verbesserung zum existierenden Branch-and-Cut Verfahren dar, wobei für die meisten Modellparameter die bisherige exakte Methode übertroffen wird.<br />

This thesis deals with new exact algorithms for the compression of fingerprint minutiae templates. Basis is a novel approach to the compression of small unordered set of points by means of combinatorial optimization developed beforehand within an ongoing research project.<br />Thereby these points are encoded by a spanning tree which arcs are finally represented by a reference to a dictionary and a small correction. The resulting optimization model is an extension of the well known minimum label spanning tree problem. The application background is the embedding of fingerprint minutiae data into passport images by watermarking techniques as an additional security feature.<br />The particular goal of this thesis was to develop improved exact algorithms based on mathematical programming techniques to solve the given problem. In particular, the existing branch-and-cut algorithm required a time-consuming preprocessing step, which has now been directly integrated into the solution process of the mixed integer model. More precisely, the generation of new variables is embedded into the branch-and-bound procedure to solve the flow-based tree model. Such procedures are called branch-and-price and the recurrent subproblem of creating new variables is called the pricing problem.<br />The determination of a new variable which is potentially improving the current objective function value requires a fast algorithm as this step is performed frequently. The given pricing problem is solved by means of a k-d tree data structure which enables to exploit geometric properties of the input data. Each time this tree is traversed according to the information given by numeric values provided by the linear programming relaxation of the optimization model.<br />The resulting branch-and-price method clearly outperforms the existing branch-and-cut algorithm. This enables to obtain provably optimal results for the considered input instances for the first time.