Travelling Salesperson Problem (TSP) mittles Pyramiden

Problemstellung

Aufgabe das TSP Problems ist das Finden des kuerzesten Pfades (minimale Laenge) durch alle Knoten eines gegebenen gewichteten Graphen. Das Problem ist als NP-vollstaendig bekannt. In letzer Zeit wurden Pyramidenalgorithmen benutzt um mentale Problemloesungsmechanismen zu modellieren. Solche Mechanismen koennten an der visuellen Loesung des TSP beteiligt, sowie an der Loesung anderer visueller Probleme [1,2]. Menschen scheinen die Cluster von Knoten zusammenzufassen, das Problem auf einem vereinfachten Graphen zu loesen und den gesuchten Pfad durch Verfeinerung "top-down" zu suchen. Es ist klar, dass das Resultat nur eine Approximation darstellt, in vielen Faellen aber eine sehr gute, deren Pfadlaenge nahe der optimalen Loesung liegt. Die den mentalen Processen entsprechenden Algorithmen haben eine niedrige Rechenkomplexitaet (i.e. linear). Pyramidmodelle koennten die erste glaubhafte Erklaerungen von Phenomenen des menschlichen Denken erlauben ('directedness of thought and reasoning'). Pyramidenalgorithmen werden auch als adaequate Modelle fuer die Gestaltregeln in der Wahrnehmung (perceptual organization) gesehen, wie z.B die Nachbarschaft, die gute Fortsetzung etc. Objekte der visuellen Wahrnehmung erscheinen dem Menschen in einer grossen Bandbreite an Groessen, mit vielen Details, wenn das Objekt nahe ist und mit sehr wenig Details in der Entfernung, wo der visuelle Kontext fuer die Erkennung wichtig ist. Pyramiden unterstuetzen zwei grundsaetzlich gegensaetzliche Verarbeitungsweisen, die den den Uebergang von hoher und niedriger Aufloesung bewaeltigen: bottom-up (fine to coarse) sowie top-down (coarse to fine). Der top-down Ansatz ist oft entscheidend fuer die effiziente Loesung des Segmentierungsproblems.

Ziel des Praktikums

Irregulaere Graphenpyramiden [3] als Modelle fuer die 'human problem solving'.

Gliederung des Praktikums

• Einarbeitung.
• C/C++ Implementation mit bereits bestehende Software Z. Li and Z.Pizlo (C) der Purdue University, mit aktivem Gedankenaustausch mit den Forschungsaktivitaeten an der Purdue University.
• Performance Test.

Fuer dieses Praktikum besteht auch die Moeglichkeit eine Diplomarbeit anzuschliessen. Program (unter Windows) und fuer source code bitte Z.Pizlo kontaktieren.

Literatur

• Z. Pizlo and Z. Li. Pyramid algorithms as models of human cognition. Proc. of SPIE IST Electronic Imaging, Computational Imaging, 5016, 1-12, 2003.
• Z. Pizlo and Z. Li. Graph Pyramids as models of human problem solving. Proc. of SPIE IST Electronic Imaging, Computational Imaging, 5299, 205-215, 2004.
• W.G. Kropatsch. Building Irregular Pyramids by Dual Graph Contraction. IEE-Proc. Vision, Image and Signal Processing, Vol. 142,366-374, 1995.
  Also as PRIP technical report Nr.35.

Demos of the graph pyramid solutions.

Betreuer: Yll Haxhimusa

Praktikum