This paper presents a mathematical analysis of the impact of key-point detection errors on the similarity of local image descriptors that are based on histogram of gradients. First, we derive a closed-form expression for the Lp distance between two descriptors, for general translation, scale and orientation detection errors. Second, we introduce a detailed analysis for the special case where translation errors dominate, using the L2 distance. We show that the individual components which form the squared L2 distance can be approximated using Gamma distributions whose parameters are computed in closed-form by our model. We obtain approximate closed-form expressions for the expected squared L2 distances when translation errors are fixed or uniformly distributed. Finally, these models are validated using image patches extracted from two standard image retrieval datasets, by comparing the predicted distributions to the ground-truth.

We address the challenge of using image queries to retrieve video clips from a large database. Using binarized Fisher Vectors as global signatures, we present three novel contributions. First, an asymmetric comparison scheme for binarized Fisher Vectors is shown to boost retrieval performance by 0.27 mean Average Precision, exploiting the fact that query images contain much less clutter than database videos. Second, aggregation of frame-based local features over shots is shown to achieve retrieval performance comparable to aggregation of those local features over single frames, while reducing retrieval latency and memory requirements by more than 3X. Several shot aggregation strategies are compared and results indicate that most perform equally well. Third, aggregation over scenes, in combination with shot signatures, is shown to achieve one order of magnitude faster retrieval at comparable performance. Scene aggregation also outperforms the recently proposed aggregation in random groups.

Reproducible research in the area of visual search depends on the availability of large annotated datasets. In this paper, we address the problem of querying a video database by images that might share some contents with one or more video clips. We present a new large dataset, called Stanford I2V. We have collected more than 3; 800 hours of newscast videos and annotated more than 200 ground-truth queries. In the following, the dataset is described in detail, the collection methodology is outlined and retrieval performance for a benchmark algorithm is presented. These results may serve as a baseline for future research and provide an example of the intended use of the Stanford I2V dataset. The dataset can be downloaded at http://purl.stanford.edu/zx935qw7203.

Acquiring 3D geometry of an object is a tedious and time-consuming task, typically requiring scanning the surface from multiple viewpoints. In this work we focus on reconstructing complete geometry from a single scan acquired with a low-quality consumer-level scanning device. Our method uses a collection of example 3D shapes to build structural part-based priors that are necessary to complete the shape. In our representation, we associate a local coordinate system to each part and learn the distribution of positions and orientations of all the other parts from the database, which implicitly also defines positions of symmetry planes and symmetry axes. At the inference stage, this knowledge enables us to analyze incomplete point clouds with substantial occlusions, because observing only a few regions is still sufficient to infer the global structure. Once the parts and the symmetries are estimated, both data sources, symmetry and database, are fused to complete the point cloud. We evaluate our technique on a synthetic dataset containing 481 shapes, and on real scans acquired with a Kinect scanner. Our method demonstrates high accuracy for the estimated part structure and detected symmetries, enabling higher quality shape completions in comparison to alternative techniques.

We study the challenges of image-based retrieval when the database consists of videos. This variation of visual search is important for a broad range of applications that require indexing video databases based on their visual contents. We present new solutions to reduce storage requirements, while at the same time improving video search quality. The video database is preprocessed to find different appearances of the same visual elements, and build robust descriptors. Compression algorithms are developed to reduce system's storage requirements. We introduce a dataset of CNN broadcasts and queries that include photos taken with mobile phones and images of objects. Our experiments include pairwise matching and retrieval scenarios. We demonstrate one order of magnitude storage reduction and search quality improvements of up to 12% in mean average precision, compared to a baseline system that does not make use of our techniques.

In cameras with radial distortion, straight lines in space are in general mapped to curves in the image. Although epipolar geometry also gets distorted, there is a set of special epipolar lines that remain straight, namely those that go through the distortion center. By finding these straight epipolar lines in camera pairs we can obtain constraints on the distortion center(s) without any calibration object or plumb line assumptions in the scene. Although this holds for all radial distortion models we conceptually prove this idea using the division distortion model and the radial fundamental matrix which allow for a very simple closed form solution of the distortion center from two views (same distortion) or three views (different distortions). The non-iterative nature of our approach makes it immune to local minima and allows finding the distortion center also for cropped images or those where no good prior exists. Besides this, we give comprehensive relations between different undistortion models and discuss advantages and drawbacks.

Both image segmentation and dense 3D modeling from images represent an intrinsically ill-posed problem. Strong regularizers are therefore required to constrain the solutions from being 'too noisy'. Unfortunately, these priors generally yield overly smooth reconstructions and/or segmentations in certain regions whereas they fail in other areas to constrain the solution sufficiently. In this paper we argue that image segmentation and dense 3D reconstruction contribute valuable information to each other's task. As a consequence, we propose a rigorous mathematical framework to formulate and solve a joint segmentation and dense reconstruction problem. Image segmentations provide geometric cues about which surface orientations are more likely to appear at a certain location in space whereas a dense 3D reconstruction yields a suitable regularization for the segmentation problem by lifting the labeling from 2D images to 3D space. We show how appearance-based cues and 3D surface orientation priors can be learned from training data and subsequently used for class-specific regularization. Experimental results on several real data sets highlight the advantages of our joint formulation.

Articulated objects represent an important class of objects in our everyday environment. Automatic detection of the type of articulated or otherwise restricted motion and extraction of the corresponding motion parameters are therefore of high value, \eg in order to augment an otherwise static 3D reconstruction with dynamic semantics, such as rotation axes and allowable translation directions for certain rigid parts or objects. Hence, in this paper, a novel theory to analyse relative transformations between two motion-restricted parts will be presented. The analysis is based on linear subspaces spanned by relative transformations. Moreover, a signature for relative transformations will be introduced which uniquely specifies the type of restricted motion encoded in these relative transformations. This theoretic framework enables the derivation of novel algebraic constraints, such as low-rank constraints for subsequent rotations around two fixed axes for example. Lastly, given the type of restricted motion as predicted by the signature, the paper shows how to extract all the motion parameters with matrix manipulations from linear algebra. Our theory is verified on several real data sets, such as a rotating blackboard or a wheel rolling on the floor amongst others.

In geometric computer vision, the structure from motion (SfM) problem can be formulated as a optimization problem with a rank constraint. It is well known that the trace norm of a matrix can act as a convex proxy for a low rank constraint. Hence, in recent work [7], the trace-norm relaxation has been applied to the SfM problem. However, SfM problems often exhibit a certain structure, for example a smooth camera path. Unfortunately, the trace norm relaxation can not make use of this additional structure. This observation motivates the main contribution of this paper. We present the so-called generalized trace norm which allows to encode prior knowledge about a specific problem into a convex regularization term which enforces a low rank solution while at the same time taking the problem structure into account. While deriving the generalized trace norm and stating its different formulations, we draw interesting connections to other fields, most importantly to the field of compressive sensing. Even though the generalized trace norm is a very general concept with a wide area of potential applications we are ultimately interested in applying it to SfM problems. Therefore, we also present an efficient algorithm to optimize the resulting generalized trace norm regularized optimization problems. Results show that the generalized trace norm indeed achieves its goals in providing a problem-dependent regularization.

Camera networks have gained increased importance in recent years. Previous approaches mostly used point correspondences between different camera views to calibrate such systems. However, it is often difficult or even impossible to establish such correspondences. In this paper, we therefore present an approach to calibrate a static camera network where no correspondences between different camera views are required. Each camera tracks its own set of feature points on a commonly observed moving rigid object and these 2D feature trajectories are then fed into our algorithm. By assuming the cameras can be well approximated with an affine camera model, we show that the projection of any feature point trajectory onto any affine camera axis is restricted to a 13-dimensional subspace. This observation enables the computation of the camera calibration matrices, the coordinates of the tracked feature points, and the rigid motion of the object with a non-iterative trilinear factorization approach. This solution can then be used as an initial guess for iterative optimization schemes which make use of the strong algebraic structure contained in the data. Our new approach can handle extreme configurations, e.g. a camera in a camera network tracking only one single feature point. The applicability of our algorithm is evaluated with synthetic and real world data.

Abstract The goal of this paper is to enable the interactive simulation of phenomena such as animated fluid characters. While full 3D fluid solvers achieve this with control algorithms, these 3D simulations are usually too costly for real‐time environments. In order to achieve our goal, we reduce the problem from a three‐ to a two‐dimensional one, and make use of the shallow water equations to simulate surface waves that can be solved very efficiently. In addition to a low runtime cost, stability is likewise crucial for interactive applications. Hence, we make use of an implicit time integration scheme to obtain a robust solver. To ensure a low energy dissipation, we apply an Implicit Newmark time integration scheme. We propose a general formulation of the underlying equations that is tailored towards the use with an Implicit Newmark integrator. Furthermore, we gain efficiency by making use of a direct solver. Due to the generality of our formulation, the fluid simulation can be coupled interactively with arbitrary external forces, such as forces caused by inertia or collisions. We will discuss the properties of our algorithm, and demonstrate its robustness with simulations on strongly deforming meshes.

We present a novel multi-scale representation and acquisition method for the animation of high-resolution facial geometry and wrinkles. We first acquire a static scan of the face including reflectance data at the highest possible quality. We then augment a traditional marker-based facial motion-capture system by two synchronized video cameras to track expression wrinkles. The resulting model consists of high-resolution geometry, motion-capture data, and expression wrinkles in 2D parametric form. This combination represents the facial shape and its salient features at multiple scales. During motion synthesis the motion-capture data deforms the high-resolution geometry using a linear shell-based mesh-deformation method. The wrinkle geometry is added to the facial base mesh using nonlinear energy optimization. We present the results of our approach for performance replay as well as for wrinkle editing.