This thesis presents contributions to two major topics in computer graphics. The first part describes new algorithms for tile-based synthesis of blue noise point sets and solid textures; the second part describes systems for capturing, viewing, and manipulating outdoor photographs.

Well distributed point sets play an important role in computer graphics, as well as many other fields, since they lie in the very foundation of any sampling technique. Many previous researchers have pointed out that point sets with a blue noise Fourier spectrum, i.e. the points are distributed both evenly and randomly, are desirable in many applications.

In this thesis, we introduce a novel technique for rapidly generating such point sets. Through the use of Wang tiles, our technique deterministically generates infinite non-periodic patterns. Any local area may be consistently regenerated as needed. The points in each tile form a progressive sequence, enabling matching arbitrary spatially varying point densities. Recursion allows our technique to adaptively subdivide tiles where high density is required, and makes it possible to zoom into point sets by an arbitrary amount, while maintaining a constant apparent density. The technique is extremely fast (point generation is in the order of several millions of points per second) and has a compact memory footprint. These properties make our technique highly suitable for a variety of real-time interactive applications, some of which are demonstrated in this thesis.

Another area where tiling techniques are commonly utilized is texture synthesis. While 2D texture synthesis has been heavily researched in the past decade, synthesis of high quality solid textures remained a mostly unsolved problem. We present a novel method for synthesizing solid textures from 2D texture exemplars. First, we extend 2D texture optimization techniques to synthesize 3D texture solids. Next, the non-parametric texture optimization approach is integrated with histogram matching, which forces the global statistics of the synthesized solid to match those of the exemplar. This approach improves the convergence speed of the synthesis process and the quality of the synthesized results drastically. Our method is applicable to a wide variety of textures, including anisotropic textures, textures with large coherent structures, and multi-channel textures.

The second part of the thesis describes systems for capturing, viewing, and manipulating outdoor photographs.

First, we present a system to capture and view Gigapixel images'' (very high resolution, high dynamic range, and wide angle imagery consisting of several billion pixels each). We use a specialized camera mount, in combination with an automated pipeline for alignment, exposure compensation, and stitching, to acquire Gigapixel images with a standard camera and lens. We also present a novel viewer that enables exploration of such images at interactive rates over a network, while dynamically and smoothly interpolating the projection between perspective and curved projections, and simultaneously modifying the tone mapping to ensure an optimal view of the portion of the scene being viewed.

An important aspect of working with large imagery is how to deal with computational and memory constraints when processing the images. Image analysis and enhancement tasks such as tone mapping, colorization, stereo depth, and photomontage, often require computing a solution (e.g., for exposure, chromaticity, disparity, labels) over the pixel grid. When processing large images (e.g. our Gigapixel images) computational and memory costs often require that the solution is computed on downsampled versions of the images. Once the solution for a downsampled image is available it has to be upsampled to the full original resolution of the input image. Solutions upsampled with general purpose upsampling filters suffer from blurring of sharp edges because of the smoothness priors inherent in those filters. We demonstrate that in cases, such as those above, the available high resolution input image may be leveraged as a prior in the context of a joint bilateral upsampling'' procedure to generate a better high resolution solution. We show results for each of the applications mentioned above and compare them to traditional upsampling methods.

Finally, we introduce a novel method for browsing, enhancing, and manipulating outdoor photographs by combining them with existing geo-referenced digital terrain and urban models. A simple interactive registration process is used to align photographs with models. Once the photograph and the model have been registered, an abundance of information, such as depth, texture, and geographical data, becomes immediately available to our system. This information, in turn, enables a variety of operations, ranging from dehazing and relighting the photograph, to novel view synthesis, and overlaying with geographic information. We describe the implementation of a number of these applications and discuss possible extensions. Our results show that augmenting photographs with 3D models in this manner supports a wide variety of new ways for us to experience and interact with our everyday snapshots.

Diese Arbeit stellt eine Reihe von Beiträgen zu zwei wichtigen Gebieten der Computergrafik vor. Der erste Teil beschreibt neue Algorithmen für die kachelbasierte Synthese von Punktmengen und Volumentexturen. Der zweite Teil beschreibt Systeme für die Anfertigung, Darstellung und Bearbeitung von Fotografien.

Wohl verteilte Punktmengen spielen eine wichtige Rolle in der Computergrafik und vielen anderen Gebieten, da sie eine Grundlage für Abtasttechniken bilden. In vielen Arbeiten wurde in den letzten Jahren gezeigt, dass sich insbesondere Punktmengen mit einem so genannten "Blue Noise"' Fourierspektrum für viele Anwendungen sehr gut eignen. Dabei handelt es sich um Punktmengen, bei denen die Punkte sowohl zufällig als auch gleichmäßig verteilt sind.

In dieser Arbeit wird ein neues Verfahren vorgestellt, mit dem solche Punktmengen effizient erzeugt werden können. Die Verwendung von Wang-Kacheln ermöglicht die deterministische Erzeugung von unbegrenzten nicht-periodischen Punktmengen, bei denen auf jedes lokale Gebiet direkt zugegriffen werden kann. Die Punkte in jeder Kachel sind in einer progressiven Sequenz geordnet, wodurch die Punktdichte beliebig räumlich variiert werden kann. Die Punktmengen sind selbstähnlich, so dass die Kachelung an Stellen, an denen eine höhere Dichte benötigt wird, rekursiv unterteilt werden kann. Das Verfahren ist sehr schnell (mehrere millionen Punkte pro Sekunde) und benötigt nur wenig Speicherplatz. Aufgrund dieser Eigenschaften eignet sich das Verfahren insbesondere für Echtzeitanwendungen, was anhand von mehreren Beispielen demonstriert wird.

Die Textursynthese ist ein weiteres Gebiet, in dem Kachelungstechniken häufig benutzt werden. Während die Synthese von 2D Texturen in den letzten Jahren intensiv erforscht wurde, und viele erfolgreiche Verfahren vorgestellt wurden, blieb das Problem der Synthese von qualitativ hochwertigen Volumentexturen weitgehend ungelöst. In dieser Arbeit wird ein neues Verfahren für die Synthese von Volumentexturen vorgestellt. Das Verfahren erweitert ein existierendes 2D Texturoptimierungsverfahren, so dass Volumentexturen aus 2D Beispieltexturen erzeugt werden können. Durch die Integration eines Histogramm-Angleichungsschrittes werden die Konvergenzgeschwindigkeit der Optimierung sowie die Qualität der resultierenden Volumentexturen deutlich verbessert. Das Verfahren ist auf eine breite Auswahl von Texturen anwendbar, unter anderem anisotrope Texturen, stark strukturierte Texturen und Texturen mit vielen Kanälen.

Der zweite Teil der Arbeit beschreibt Systeme für die Anfertigung, Darstellung und Bearbeitung von Fotografien.

Zunächst wird ein System für die Aufnahme von "Gigapixel"' Bildern beschrieben (sehr hoch aufgelöste Weitwinkelbilder mit hohem Dynamikumfang und mehreren Milliarden Bildpunkten). Ein spezielles computergesteuertes Stativ mit einer digitalen Spiegelreflexkamera und einem Teleobjektiv mit hoher Brennweite wird benutzt, um in kurzer Zeit systematisch mehrere hundert Bilder einer Szene aufzunehmen. Anschließend durchlaufen die Bilder eine automatische Pipeline, in der sie zu einem Gigapixel Bild zusammengesetzt werden.

Es wird außerdem ein neuartiges interaktives Darstellungsprogramm vorgestellt, mit dem Gigapixel Bilder über eine Netzwerkverbindung betrachtet werden können. Das Programm interpoliert zwischen perspektivischer, zylindrischer und sphärischer Projektion, und modifiziert die Abbildung des Dynamikumfangs für eine optimale Darstellung des betrachteten Bildausschnitts.

Ein wichtiger Aspekt bei der Bearbeitung von großen Bildern ist der Umgang mit beschränkten Speicher- und Rechenressourcen. Bei vielen Bildverarbeitungsaufgaben werden auf dem Pixelgitter definierte Gleichungssysteme gelöst (z. B. für Belichtungskorrekturen, Farben beim Einfärben von Schwarz-Weiß-Bildern, Disparitäten bei Stereobildern, oder Quellbild-Zuord-nung bei der Fotomontage). Bei größeren Bildern kann der Speicherbedarf für die Lösung leicht den zur Verfügung stehenden Speicher überschreiten, was zu einem erheblich höheren Zeitbedarf für die Berechnung führen kann. Aus diesem Grund ist es oft erforderlich, insbesondere bei Gigapixel Bildern, die Lösung für eine kleinere Version des Bildes zu berechnen. Anschließend muss die Lösung wieder auf die ursprüngliche Auflösung vergrößert werden. Die Verwendung von allgemeinen Bildvergrößerungsverfahren führt oft zu schlechten Ergebnissen, da diese auf der Annahme basieren, dass das Bild keine scharfen Kanten enthält. Das Ergebnis erscheint deshalb je nach Vergrößerungsfaktor mehr oder weniger stark weichgezeichnet. In dieser Arbeit wird gezeigt, wie mit einem "Joint Bilateral Upsampling"' Verfahren deutlich bessere Ergebnisse erzielt werden können. Das neue Verfahren wird an den oben beschriebenen Anwendungen getestet und mit herkömmlichen Upsampling-Verfahren verglichen.

Zuletzt wird ein System für die Manipulation von Fotografien von Außenszenen mit Hilfe von digitalen Terrain- und Stadtmodellen beschrieben. Durch einen einfachen Prozess werden die inneren und äußeren Kameraparameter der Bilder bestimmt, d.h. unter anderem ihre Lage und Orientierung in Bezug auf das Modell. Dadurch steht dem System eine Fülle von Informationen zur Verfügung, unter anderem die exakte geographische Position jedes Pixels. Dies ermöglicht eine Reihe von Anwendungen, unter anderem die Entfernung von Dunst, die Änderung der Beleuchtung und des Blickpunktes und die Überlagerung von geographischen Informationen. Es werden die Implementierung der genannten Anwendungen beschrieben und mögliche Erweiterungen diskutiert.