A Matter of Perspective - Three-dimensional Placement of Multiple Cameras to Maximize their Coverage

Titelangaben

Hänel, Maria L.:
A Matter of Perspective - Three-dimensional Placement of Multiple Cameras to Maximize their Coverage.
Bayreuth , 2015 . - i, 165 S.
( Dissertation, 2015 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Angaben zu Projekten

Abstract

In dieser Arbeit wird eine Methode zur optimalen Platzierung und Orientierung mehrerer Kameras erstellt. Der Algorithmus optimiert die Positionen und Orientierungen der Kameras in einer vorgegebenen dreidimensionalen Umgebung, um ein Objekt, zum Beispiel eine Person, möglichst genau zu approximieren, oder die wichtigen Bereiche der Umgebung möglichst gut auszuleuchten. Denn je genauer die Approximation der Person ist, desto einfacher ist es, sie zu beschützen. Außerdem ist eine Approximation einfacher zu erstellen, je mehr von der Umgebung, in der sich das Objekt befindet, von den Kameras abgedeckt wird.

In einem solchen Programm wird eine Sichtbarkeitsanalyse benötigt, eine Analyse die zu einer gegebenen Umgebung den Sichtbereich einer Kamera bestimmt. Diese Analyse muss automatisch geometrisch berechnet werden und ist zeitaufwendig. In der existierenden Literatur wird die Sichtbarkeitsanalyse deshalb stark vereinfacht, beispielsweise wird nur die zweidimensionale Draufsicht auf einen Raum als Umgebung verwendet, Hindernisse, wie Mauern oder andere Menschen, werden nicht berücksichtigt oder es gibt nur diskrete Montagepunkte für die Kameras. Im Gegensatz zu existierenden Arbeiten, werden hier mehrere Kameras in einer dreidimensionalen Umgebung auf einem kontinuierlichen Definitionsbereich, also beispielsweise im ganzen Raum, unter Berücksichtigung von Hindernissen betrachtet.

Die drei erstellten Algorithmen sind zuverlässig, global konvergent und gelangen nach einer kurzen Initialisierungsphase zu einer zulässigen Lösung. Mehrere Strategien werden vorgestellt, um deren Berechnungszeit zu verkürzen: Die Reduktion der Funktionsaufrufe, die Beschleunigung der Sichtbarkeitsanalyse und die Beschleunigung der Konvergenz. Im Allgemeinen ist die Anzahl der Funktionsaufrufe der Methoden bis zur Terminierung vergleichbar mit lokalen Methoden, obwohl sie keinen analytischen Gradienten benötigen. Die Methoden sind für eine Vielzahl an Problemen interessant, deren Zielfunktion quantisiert, zeitaufwendig, nicht konvex oder nur als "Blackbox" gegeben ist. Mit der vorgestellten Architektur für Kameraplatzierung ist ein System entwickelt worden, das effizient gute Positionen und Orientierungen der Kameras in drei Dimensionen erstellt, an die der Mensch nicht unbedingt gedacht hätte. Das ist an mehreren synthetischen und praktischen Beispielen getestet worden.

Außerdem wurde die Berechnung durch die folgenden Strategien beschleunigt: Die Optimierungsmethoden können vorher bekannte Informationen über gute und schlechte Platzierungen berücksichtigen, beispielsweise um von vornherein auszuschließen, dass die Kameras an einer Wand zu dieser hinorientiert werden. Zusätzlich können die Methoden die Symmetrie einer Funktion und die Tatsache, dass die Funktion auf Unterräumen des Definitionsbereichs wesentlich einfacher zu berechnen ist, ausnutzen um die gesamte Berechnung zu beschleunigen. Zuletzt ist sogar eine der Optimierungsmethoden bewiesenermaßen konvergent, wenn die Zielfunktionsaufrufe parallel berechnet werden.

Um vorher bekannte Informationen und Eigenschaften von der Zielfunktion unseres Problems abzuleiten, wird die Funktion zu Beginn der Arbeit analysiert: Die Analyse beweist, dass die Gestalt der Bereiche, die durch die Kameras abgedeckt werden, oder der Bereiche, die die Approximation des Objektes definieren, ein entartetes Polyeder ist. Die Ecken, Flächen und das Aufeinandertreffen von Ecken und Flächen werden in Abhängigkeit der Kameraparameter klassifiziert. Diese Klassifizierungen sind besonders wichtig für die Untersuchung der Differenzierbarkeit und der Quantisierung der Zielfunktion.

Abstract in weiterer Sprache

In this thesis, the problem of optimally placing and orienting multiple cameras by a suitable algorithm is considered. The algorithm optimizes the positions and orientations of the cameras in a given three-dimensional environment to approximate a target, such as a human, most accurately, or to maximally cover the important regions of the environment. The more precise the approximation, the easier it is to protect the human. In general, the better the environment is covered in the relevant regions, the easier an approximation can be formed.

Such a method requires a visibility analysis, a simulation of the field of view of each camera. The visibility analysis is time consuming, since it can only be done geometrically. Previous work severely simplifies the optimization, e.g., by only considering a two-dimensional top view of the environment, by defining the possible mounting spots of the cameras in a discretized way, or by neglecting visual obstacles. In contrast to the existing work, the proposed algorithms place multiple cameras in a three-dimensional environment on a continuous domain considering static and dynamic visual obstacles.

The three algorithms are globally convergent and establish a feasible solution at any time after a short initialization phase. Several strategies are developed for decreasing the computation time of the methods: Some of the strategies decrease the number of objective function calls, some accelerate the visibility analysis, and some increase the convergence rate of the solver. In general, the number of function evaluations of the solvers is as low as in case of a local solver although it is applied to functions without gradient. It is practical for a variety of problems whose objective functions are non-convex, stair-cased, expensive, or given only as a black-box.

Furthermore, the computation is accelerated by the following strategies: The optimization methods are ready to incorporate prior information about good and bad placements, e.g., to prevent cameras from facing a wall of the room right from the beginning. Additionally, they can use the symmetry of a function and the fact that a function is substantially cheaper on subspaces of the domain for an acceleration. Lastly, one of the solvers has been proved to converge even when some of the function calls are computed in parallel. With the proposed architecture for camera placement, a system has been developed that efficiently generates provably good positions and orientations of cameras in three dimensions that a human might not think of. This is demonstrated on several synthetic and realistic examples.

In order to establish prior information about the objective function and its properties, the function is analyzed in the beginning of the thesis. The analysis shows the regions which are covered by the cameras or the regions that define the approximation of the target. Both regions have a polyhedral shape. Vertices, faces, and the contact of faces with specified points of the environment are classified depending on the camera parameters. This is particularly interesting to investigate the differentiability and stair-casing of the objective function.