Harren R.,Max Planck Institute for Computer Science MPII |
Van Stee R.,Max Planck Institute for Computer Science MPII
Journal of Scheduling | Year: 2012
We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm with an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided P ≠ N P. For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm Hybrid First Fit which was introduced by Chung et al. (SIAM J. Algebr. Discrete Methods 3(1):66-76, 1982) and whose running time is slightly better than the running time of Zhang's previously known 3-approximation algorithm (Zhang in Oper. Res. Lett. 33(2):121-126, 2005). © The Author(s) 2009.
Kurz C.,Max Planck Institute for Computer Science MPII |
Thormahlen T.,Max Planck Institute for Computer Science MPII |
Seidel H.-P.,Max Planck Institute for Computer Science MPII
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011
The recent resurgence of stereoscopic 3D films has triggered a high demand for post-processing tools for stereoscopic image sequences. Camera motion estimation, also known as structure-from-motion (SfM) or match-moving, is an essential step in the post-processing pipeline. In order to ensure a high accuracy of the estimated camera parameters, a bundle adjustment algorithm should be employed. We present a new stereo camera model for bundle adjustment. It is designed to be applicable to a wide range of cameras employed in today's movie productions. In addition, we describe how the model can be integrated efficiently into the sparse bundle adjustment framework, enabling the processing of stereoscopic image sequences with traditional efficiency and improved accuracy. Our camera model is validated by synthetic experiments, on rendered sequences, and on a variety of real-world video sequences. © 2011 Springer-Verlag Berlin Heidelberg.