Structurally optimal dual graph pyramid and its application in image partitioning

Abstract

Das Ziel im Bildverstehen ist, Maschinen sehen zu lassen, oder mindestens den Maschinen die Fähigkeit beizubringen, Sehtätigkeiten mit derselben Qualität, Quantität und Geschwindigkeit wie von Menschen oder Tieren durchzuführen.<br />Menschen und Tiere sind imstande, Objekte in komplexen Szenen sofort abzugrenzen, zu detektieren und zu erkennen. Daher ist Zeit eine sehr kritische Ressource und die biologische Antwort im menschlichen visuellen System ist ein hoch paralleles Model. Hierarchische Repräsentationen und hierarchische Verarbeitung im Bildverstehen sind ein guter Ansatz um die Raum- und Leistungsbeschränkungen zu bewältigen, die im menschlichen visuellen System beobachtet worden sind.<br />Eine häufig verwendete hierarchische Repräsentation in vielen Bereichen des Bildverstehens und der Mustererkennung ist die (reguläre) Bildpyramide.<br />Diese Repräsentation setzt beide Verarbeitungsstrategien ein, grob zu fein und fein zu grob.<br />Der Hauptvorteil der regulären Pyramide ist eine schnelle Berechnung der globalen Information in rekursiven Verfahren, aufgrund der logarithmischen Höhe bezüglich der Eingabegröße. Daher haben die Algorithmen, die auf diese Datenstruktur laufen, eine logarithmische Zeitkomplexität. Dennoch mangelt die reguläre Bildpyramide an Schiebeinvarianz und ist nicht in der Lage die Zusammenhänge der Objekte wegen der festgelegten vertikalen Nachbarschaft zu gewährleisten. Daher sollte die reguläre Pyramide nicht als allgemeine Segmentationsmethode verwendet werden.<br />Zur Bewältigung der Schiebeinvarianz sollten neue hierarchische Strukturen, die so genanten irreguläre Pyramiden, bevorzugt werden.<br />Allerdings, sowohl die logarithmische Höhe der irregulären Pyramide als auch die rechnerbetonte Effizienz gehen verloren.<br />Die Verwendung des Graphentheorieformalismus, um die irregulären Strukturen zu beschreiben, ermöglicht eine einfache Analyse dieser irregulären Pyramide.<br />Um in der Lage zu sein mehrfache Grenzen zwischen Regionen zu repräsentieren, benutzen wir duale Graphen und deshalb heißt die konstruierte Pyramide duale Graphenpyramide. In dieser Doktorarbeit befassen wir uns hauptsächlich mit dualen Graphenpyramiden und ihrer Anwendung in der Bildpartitionierung. Wir führen zwei neue Graphenkonzepte ein und zeigen, dass die präsentierte Methoden (maximal unabhängige Kantenmenge (MIES) und maximal unabhängige gerichtete Kantenmenge (MIDES)), die für Konstruktion der stochastischen irregulären Pyramide einsetzt, grenzen logarithmisch die Höhe der Pyramide ein. Wir zeigen auf, dass die zwei häufig verwendete stochastische Dezimierungsstrategien (die maximal unabhängige Knotenmenge (MIS) und den datengesteuerte Dezimierungsprozess (D3P)) nicht zur logarithmischen Höhe der Graphenpyramiden führen. Nach der Analyse der verschiedenen Techniken für den Aufbau der Bildpyramidenstrukturen möchten wir diese Strukturen in einem Rahmen für bottom-up Verarbeitung einsetzen.<br />Basierend auf den Boruvkas minimalen aufspannenden Baum (MST) präsentieren wir eine zeiteffiziente Bildpartitionierungmethode in dieser irregulären Graphenpyramide (BoruSeg). Wenn der Bildkontext nicht in Betracht gezogen wird, ist die hierarchische Repräsentation erforderlich, obwohl das Ziel der Bildsegmentation eine einzige Bildpartitionierung und nicht unbedingt eine Bildhierarchie ist.<br />Selbst wenn diese Methode nur greedy Entscheidungen während des Prozesses betrifft, ist sie imstande wichtige Gestaltgruppierungen wahrzunehmen. Wir vergleichen die Qualität der Segmentationsergebnisse von MIES, MIS und D3P Versionen dieser MST Methode mit menschlichen Bildsegmentationen und Segmentationen von anderen graphenbasierten Methoden.<br />Diese Bewertung zeigt, dass verschiedenen stochastischen Dezimierungen in MST basierte Bildesegmentation dieselben vergleichbaren Ergebnisse liefert. Wir fassen die wichtigsten Beiträge dieser Doktoratarbeit zusammen, und schließen die Diskussion über das Graph-Matching Problem und die Anwendbarkeit der hierarchischen Ansätze, um die Komplexität dieses schwer-rechenbaren Problems zu lösen.<br />

The goal of computer vision is to make machines see, or at least to perform vision tasks with the same quality, quantity and speed as humans and animals.Humans and animals are able to delineate, detect and recognize objects in complex scenes 'in no time'. One of the most valuable and critical resources in human visual processing is time, therefore a highly parallel model is the biological answer dealing satisfactorily with this resource. Hierarchical representation and hierarchical processing in computer vision systems are the credible approach to address space and performance constraints, observed in human and animal visual systems. A widely used hierarchical representation in many areas of computer vision and pattern recognition is the (regular) image pyramid, which employs both coarse to fine and fine to coarse processing strategies. The main advantage of regular pyramids is rapid computation of global information in a recursive manner, due to logarithmic height with respect to the size of the input, making algorithms running in this data structure having a logarithmic time complexity. However, regular image pyramids lack shift invariance and do not preserve object connectivity as a result of the fixed vertical neighborhood. Thus they should be abandoned as general segmentation methods. In order to cope with shift invariance, among others, new hierarchical structures, the so called irregular pyramids, should be used. However, the logarithmic height of irregular pyramids is lost, as well as the computational efficiency. The non-logarithmic height is the main drawback of the irregular structures. Employing graph theoretical formalisms to describe irregular hierarchical structures allows an easy analysis of irregular graph pyramids. In order to be able to encode multiple boundaries between regions we use dual graphs, and the build pyramid is called dual graph pyramid.In this thesis we mainly deal with dual graph pyramids and their application in image partitioning. We introduce two new graph concepts and show that the presented methods, maximal independent edge set (MIES) and maximal independent directed edge set (MIDES) used for the construction of stochastic irregular pyramids, bound logarithmically the height of the pyramid. We show that the two widely used stochastic decimation strategies, the maximal independent vertex set (MIS) and data driven decimation process (D3P) do not lead to logarithmic tapering graph pyramids. After studying different techniques to build the structure of the pyramid, we are motivated to use these structures in a framework for bottom-up processing. Thus into this irregular graph pyramid framework, we introduce a time efficient image partitioning method based on Boruvka's minimum spanning tree principle (MST)(BoruSeg). Although the goal of image segmentation is a single partitioning of the image, and not necessarily an image hierarchy, a hierarchical representation is needed, especially if the image context is not taken into consideration.<br />Even thought this method makes greedy decisions during the merging process it is able to capture important perceptually groupings. We evaluate the quality of the segmentation results of the MIES, MIS and D3P versions of this MST based method with respect to humans and to other graph-based methods. The evaluation shows that in image segmentation, the different stochastic decimations used in this MST image partitioning method produce comparable results. We summarize the major contribution of this thesis and discuss about the computationally hard problem of graph matching and the applicability of hierarchical approaches in dealing with its complexity.