[Back]

C. Thöni:
"Compressing fingerprint templates by solving the $k$-node minimum label spanning arborescence problem by branch-and-price";
Supervisor: G. Raidl, A Chwatal; Institut für Computergraphik und Algorithmen, 2010; final examination: 2010-02.

This thesis deals with the development of exact algorithms based on mathematical programming techniques for the solution of a combinatorial optimization problem which emerged in the context
of a new compression model recently developed at the Algorithms and Data Structures Group of the Institute of Computer Graphics and Algorithms at the Vienna University of Technology. This
compression model is particularly suited for small sets of unordered and multidimensional data having its application background in the field of biometrics. More precisely, fingerprint data given
as a set of characteristic points and associated properties should be compressed in order to be used as an additional security feature for e.g. passports by embedding the data into passport images
by watermarking techniques.
The considered model is based on the well known Minimum Label Spanning Tree Problem
(MLST) with the objective to find a small set of labels, associated to the edges of the graph,
inducing a valid spanning tree. Based on this solution an encoding of the considered points being
more compact than their trivial representation can be derived. So far, heuristic and exact algorithms
have been developed, all of them requiring a time-consuming preprocessing step. The goal
of this work is to develop an improved exact algorithm carrying out the tasks of the preprocessing
algorithm during the execution of the exact methods in an pro table way.
Within this thesis the problem is solved by mixed integer programming techniques. For this purpose a new flow formulation is presented which can be directly solved by linear programming
based branch-and-bound, or alternatively by branch-and-price, being the main approach of this
thesis. Branch-and-price works by starting with a restricted model, and then iteratively adding
new variables potentially improving the objective function value. These variables are determined
within the pricing problem which has to be solved frequently during the overall solution process.
For this purpose specialized data structures and algorithms, based on a k-d tree are used, with the
intention to exploit possible structures of the input data. Within this tree, improving variables can
be found by various traversing and bounding techniques. These algorithms can also be adapted
in order to work as an alternative to the existing preprocessing.
All algorithms have been implemented and comprehensively tested. For the existing approaches,
the new methods reduced the preprocessing run times with a factor of 50 and use
now 2% of the original run times. With the presented branch-and-price approach it is possible to
solve a greater amount of test instances to optimality than previously. Generally, for most model
parameters the branch-and-price approach outperforms the previous exact method.

Diese Diplomarbeit beschäftigt sich mit der Entwicklung von exakten Algorithmen, welche auf
mathematischer Programmierung basieren. Ziel ist die Lösung eines kombinatorischen Optimierungsproblems,
welches im Kontext eines neuen Komprimierungsverfahren auftritt, das kürzlich vom Arbeitsbereich für Algorithmen und Datenstrukturen des Institut für Computergraphik und
Algorithmen an der Technischen Universität Wien entwickelt wurde. Dieses Komprimierungsverfahren ist insbesondere geeignet für kleine Mengen von ungeordneten und multidimensionalen
Daten, wobei biometrische Applikationen den Anwendungshintergrund bilden. Insbesondere sollen
Fingerabdruckdaten, sogenannte Minutien, gegeben als Menge charakteristischer Punkte mit
zugeordneten Eigenschaften, komprimiert werden, um als zusätzliches Sicherheitsmerkmal für z.B.
Reisepässe verwendet werden zu können, indem die Daten als Wasserzeichen in das Passbild eingebettet
werden.
Das betrachtete Modell basiert auf dem bekannten Minimum Label Spanning Tree Problem
(MLST). Das Ziel des Problems ist es, eine kleine Menge an Labels zu nden, welche den Kanten
des Graphen zugeordnet sind und so einen gültigen Spannbaum induzieren. Basierend auf dieser
Lösung kann eine Kodierung der betrachteten Punkte abgeleitet werden, welche kompakter als ihre
triviale Darstellung ist. Bislang wurden Heuristiken und ein exaktes Verfahren entwickelt, welche
alle einen laufzeitintensiven Preprocessing-Schritt voraussetzen. Das Ziel dieser Arbeit ist es, einen
verbesserten exakten Algorithmus zu entwickeln, welcher die Aufgaben des Preprocessing-Schritts
in einer vorteilhaften Weise während der Ausführung der exakten Methode erledigt.
In dieser Arbeit wurde das Problem mit Mixed Integer Programmierungstechniken gelöst. Zu
diesem Zweck wird eine neue Flussnetzwerk Formulierung vorgestellt, welche direkt mittels Branchand-
Bound, basierend auf Linearer Programmierung, gelöst werden kann. Alternativ dazu gelingt
die Lösung auch mittels Branch-and-Price, welches den Hauptansatz darstellt. Branch-and-Price
beginnt mit einem reduzierten Problem und fügt dann schrittweise neue Variablen, welche den
Zielfunktionswert verbessern können, diesem reduzierten Problem hinzu. Diese Variablen werden
mittels des Pricing Problems bestimmt, welches oftmals während des Lösungsvorgangs berechnet
werden muss. Zu diesem Zweck wurden spezialisierte, auf einem k-d Tree basierende Datenstrukturen
und Algorithmen entwickelt, welche mögliche Strukturen der Eingabedaten in geschickter
Weise ausnützen. Mittels verschiedener Traversierungs- und Boundingtechniken können aus dieser
Baumdatenstruktur verbessernde Variablen effizient extrahiert werden. Weiters können die entwickelten
Algorithmen zu einer Alternative für den Preprocessing-Schritt adaptiert werden.
Alle Algorithmen wurden implementiert und umfangreich getestet. Für die bestehenden Ansätze
wurde die Zeit, die für den ursprünglichen Vorberechnungsschritt gebraucht wurde, um Faktor 50
reduziert, die Laufzeiten sinken auf 2% der ursprünglichen Zeit. Mit dem vorgestellten Branchand-
Price Verfahren ist es möglich eine größere Anzahl an Testinstanzen optimal zu lösen als
bisher. Für die meisten Modellparameter übertrif t der Branch-and-Price Ansatz die bisherige
exakte Methode.

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