We present an algorithm for the realtime matching of wireframe extractions in pairs of images. Here we treat extracted wireframes as graphs and propose a simplified Graduated Assignment algorithm to use with this problem. Using this algorithm we achieve a 30% accuracy improvement over the baseline method. We show that, for this problem, the simplified Graduated Assignment algorithm can achieve realtime performance without a significant drop in accuracy as compared to the standard Graduated Assignment algorithm. We further demonstrate a method of utilizing this simplified Graduated Assignment algorithm for achieving a similar real-time improvement in the matching quality of standard features without wireframe detection.

Spatial computing experiences are physically constrained by the geometry and semantics of the local user environment. This limitation is elevated in remote multi-user interaction scenarios, where finding a common virtual ground physically accessible for all participants becomes challenging. Locating a common accessible virtual ground is difficult for the users themselves, particularly if they are not aware of the spatial properties of other participants. In this paper, we introduce a framework to generate an optimal mutual virtual space for a multi-user interaction setting where remote users’ room spaces can have different layout and sizes. The framework further recommends movement of surrounding furniture objects that expand the size of the mutual space with minimal physical effort. Finally, we demonstrate the performance of our solution on real-world datasets and also a real HoloLens application. Results show the proposed algorithm can effectively discover optimal shareable space for multi-user virtual interaction and hence facilitate remote spatial computing communication in various collaborative workflows.

When a human supervisor collaborates with a team of robots, the human's attention is divided, and cognitive resources are at a premium. We aim to optimize the distribution of these resources and the flow of attention. To this end, we propose the model of an idealized supervisor to describe human behavior. Such a supervisor employs a potentially inaccurate internal model of the the robots' dynamics to judge safety. We represent these safety judgements by constructing a safe set from this internal model using reachability theory. When a robot leaves this safe set, the idealized supervisor will intervene to assist, regardless of whether or not the robot remains objectively safe. False positives, where a human supervisor incorrectly judges a robot to be in danger, needlessly consume supervisor attention. In this work, we propose a method that decreases false positives by learning the supervisor's safe set and using that information to govern robot behavior. We prove that robots behaving according to our approach will reduce the occurrence of false positives for our idealized supervisor model. Furthermore, we empirically validate our approach with a user study that demonstrates a significant (p = 0.0328) reduction in false positives for our method compared to a baseline safety controller.

Existing commercial driver assistance systems, including automatic braking systems and lane-keeping systems, may monitor the state of the vehicle or the environment to determine whether the systems should intervene. However, the state of the human driver is not typically included in the decision making process. In this paper, we propose to use hidden mode stochastic hybrid systems to model the interaction between the human driver and the vehicle. We show that by monitoring the human behavior as well as the vehicle state, we can infer the human state and enhance the quality of decision making in a driver assistance system. The resulting control policy is obtained by solving an optimal planning problem of the proposed hidden mode hybrid system. The policy can automatically balance the decision making about when to give warning to the driver and when to actually intervene in the control of the vehicle.

Security of fingerprint authentication systems remains threatened by the presentation of spoof artifacts. Most current mitigation approaches rely upon the fingerprint liveness detection as the main anti-spoofing mechanisms. However, liveness detection algorithms are not robust to sensor variations. In other words, typical liveness detection algorithms need to be retrained and adapted to each and every sensor used for fingerprint capture. In this paper, inspired by popular invariant feature descriptors such as histograms of oriented gradients (HOG) and the scale invariant feature transform (SIFT), we propose a new invariant descriptor of fingerprint ridge texture called histograms of invariant gradients (HIG). The proposed descriptor is designed to preserve robustness to variations in gradient positions. Spoofed fingerprints are detected using multiple histograms of invariant gradients computed from spatial neighborhoods within the fingerprint. Results show that proposed method achieves an average accuracy comparable to the best algorithms of the Fingerprint Liveness Detection Competition 2013, while being applicable with no change to multiple acquisition sensors.

Single-sample face recognition is one of the most challenging problems in face recognition. We propose a novel face recognition algorithm to address this problem based on a sparse representation based classification (SRC) framework. The new algorithm is robust to image misalignment and pixel corruption, and is able to reduce required training images to one sample per class. To compensate the missing illumination information typically provided by multiple training images, a sparse illumination transfer (SIT) technique is introduced. The SIT algorithms seek additional illumination examples of face images from one or more additional subject classes, and form an illumination dictionary. By enforcing a sparse representation of the query image, the method can recover and transfer the pose and illumination information from the alignment stage to the recognition stage. Our extensive experiments have demonstrated that the new algorithms significantly outperform the existing algorithms in the single-sample regime and with less restrictions. In particular, the face alignment accuracy is comparable to that of the well-known Deformable SRC algorithm using multiple training images, and the face recognition accuracy exceeds those of the SRC and Extended SRC algorithms using hand labeled alignment initialization.

The classical shift retrieval problem considers two signals in vector form that are related by a cyclic shift. In this paper, we develop a compressive variant where the measurement of the signals is undersampled. While the standard procedure to shift retrieval is to maximize the real part of their dot product, we show that the shift can be exactly recovered from the corresponding compressed measurements if the sensing matrix satisfies certain conditions. A special case is the partial Fourier matrix. In this setting we show that the true shift can be found by as low as two measurements. We further show that the shift can often be recovered when the measurements are perturbed by noise.

In many image/video/web classification problems, we have access to a large number of unlabeled samples. However, it is typically expensive and time consuming to obtain labels for the samples. Active learning is the problem of progressively selecting and annotating the most informative unlabeled samples, in order to obtain a high classification performance. Most existing active learning algorithms select only one sample at a time prior to retraining the classifier. Hence, they are computationally expensive and cannot take advantage of parallel labeling systems such as Mechanical Turk. On the other hand, algorithms that allow the selection of multiple samples prior to retraining the classifier, may select samples that have significant information overlap or they involve solving a non-convex optimization. More importantly, the majority of active learning algorithms are developed for a certain classifier type such as SVM. In this paper, we develop an efficient active learning framework based on convex programming, which can select multiple samples at a time for annotation. Unlike the state of the art, our algorithm can be used in conjunction with any type of classifiers, including those of the family of the recently proposed Sparse Representation-based Classification (SRC). We use the two principles of classifier uncertainty and sample diversity in order to guide the optimization program towards selecting the most informative unlabeled samples, which have the least information overlap. Our method can incorporate the data distribution in the selection process by using the appropriate dissimilarity between pairs of samples. We show the effectiveness of our framework in person detection, scene categorization and face recognition on real-world datasets.

l1-minimization refers to finding the minimum l1-norm solution to an underdetermined linear system [Formula: see text]. Under certain conditions as described in compressive sensing theory, the minimum l1-norm solution is also the sparsest solution. In this paper, we study the speed and scalability of its algorithms. In particular, we focus on the numerical implementation of a sparsity-based classification framework in robust face recognition, where sparse representation is sought to recover human identities from high-dimensional facial images that may be corrupted by illumination, facial disguise, and pose variation. Although the underlying numerical problem is a linear program, traditional algorithms are known to suffer poor scalability for large-scale applications. We investigate a new solution based on a classical convex optimization framework, known as augmented Lagrangian methods. We conduct extensive experiments to validate and compare its performance against several popular l1-minimization solvers, including interior-point method, Homotopy, FISTA, SESOP-PCD, approximate message passing, and TFOCS. To aid peer evaluation, the code for all the algorithms has been made publicly available.

Smart camera networks have recently emerged as a new class of sensor network infrastructure that is capable of supporting high-power in-network signal processing and enabling a wide range of applications. In this article, we provide an exposition of our efforts to build a low-bandwidth wireless camera network platform, called CITRIC, and its applications in smart camera networks. The platform integrates a camera, a microphone, a frequency-scalable (up to 624 MHz) CPU, 16 MB FLASH, and 64 MB RAM onto a single device. The device then connects with a standard sensor network mote to form a wireless camera mote. With reasonably low power consumption and extensive algorithmic libraries running on a decent operating system that is easy to program, CITRIC is ideal for research and applications in distributed image and video processing. Its capabilities of in-network image processing also reduce communication requirements, which has been high in other existing camera networks with centralized processing. Furthermore, the mote easily integrates with other low-bandwidth sensor networks via the IEEE 802.15.4 protocol. To justify the utility of CITRIC, we present several representative applications. In particular, concrete research results will be demonstrated in two areas, namely, distributed coverage hole identification and distributed object recognition.

We present a novel primal-dual analysis on a class of NP-hard sparsity minimization problems to provide new interpretations for their well known convex relaxations. We show that the Lagrangian bidual (i.e., the Lagrangian dual of the Lagrangian dual) of the sparsity minimization problems can be used to derive interesting convex relaxations: the bidual of the ℓ0-minimization problem is ℓ1-minimization; and the bidual of ℓ0,1-minimization for enforcing group sparsity on structured data is ℓ1,∞-minimization problem. Intuitions from the bidual-based relaxation are used to introduce a new family of relaxations for the group sparsity minimization problem.

Motivated by an emerging theory of robust low-rank matrix representation, in this paper, we introduce a novel solution for online rigid-body motion registration. The goal is to develop algorithmic techniques that enable a robust, real-time motion registration solution suitable for low-cost, portable 3-D camera devices. Assuming 3-D image features are tracked via a standard tracker, the algorithm first utilizes Robust PCA to initialize a low-rank shape representation of the rigid body. Robust PCA finds the global optimal solution of the initialization, while its complexity is comparable to singular value decomposition. In the online update stage, we propose a more efficient algorithm for sparse subspace projection to sequentially project new feature observations onto the shape subspace. The lightweight update stage guarantees the real-time performance of the solution while maintaining good registration even when the image sequence is contaminated by noise, gross data corruption, outlying features, and missing data. The state-of-the-art accuracy of the solution is validated through extensive simulation and a real-world experiment, while the system enjoys one to two orders of magnitude speed-up compared to wellestablished RANSAC solutions.

While compressive sensing (CS) has been one of the most vibrant and active research fields in the past few years, most development only applies to linear models. This limits its application and excludes many areas where CS ideas could make a difference. This paper presents a novel extension of CS to the phase retrieval problem, where intensity measurements of a linear system are used to recover a complex sparse signal. We propose a novel solution using a lifting technique -- CPRL, which relaxes the NP-hard problem to a nonsmooth semidefinite program. Our analysis shows that CPRL inherits many desirable properties from CS, such as guarantees for exact recovery. We further provide scalable numerical solvers to accelerate its implementation. The source code of our algorithms will be provided to the public.

Bag-of-words (BoW) methods are a popular class of object recognition methods that use image features (e.g., SIFT) to form visual dictionaries and subsequent histogram vectors to represent object images in the recognition process. The accuracy of the BoW classifiers, however, is often limited by the presence of uninformative features extracted from the background or irrelevant image segments. Most existing solutions to prune out uninformative features rely on enforcing pairwise epipolar geometry via an expensive structure-from-motion (SfM) procedure. Such solutions are known to break down easily when the camera transformation is large or when the features are extracted from low-resolution, low-quality images. In this paper, we propose a novel method to select informative object features using a more efficient algorithm called Sparse PCA. First, we show that using a large-scale multiple-view object database, informative features can be reliably identified from a highdimensional visual dictionary by applying Sparse PCA on the histograms of each object category. Our experiment shows that the new algorithm improves recognition accuracy compared to the traditional BoW methods and SfM methods. Second, we present a new solution to Sparse PCA as a semidefinite programming problem using the Augmented Lagrangian Method. The new solver outperforms the state of the art for estimating sparse principal vectors as a basis for a low-dimensional subspace model.

We provide a comprehensive review of five representative ℓ1-minimization methods, i.e., gradient projection, homotopy, iterative shrinkage-thresholding, proximal gradient, and augmented Lagrange multiplier. The repository is intended to fill in a gap in the existing literature to systematically benchmark the performance of these algorithms using a consistent experimental setting. The experiment will be focused on the application of face recognition, where a sparse representation framework has recently been developed to recover human identities from facial images that may be affected by illumination change, occlusion, and facial disguise. The paper also provides useful guidelines to practitioners working in similar fields.

An application of compressive sensing (CS) theory in imagebased robust face recognition is considered. Most contemporary face recognition systems suffer from limited abilities to handle image nuisances such as illumination, facial disguise, and pose misalignment. Motivated by CS, the problem has been recently cast in a sparse representation framework: The sparsest linear combination of a query image is sought using all prior training images as an overcomplete dictionary, and the dominant sparse coefficients reveal the identity of the query image. The ability to perform dense error correction directly in the image space also provides an intriguing solution to compensate pixel corruption and improve the recognition accuracy exceeding most existing solutions. Furthermore, a local iterative process can be applied to solve for an image transformation applied to the face region when the query image is misaligned. Finally, we discuss the state of the art in fast ℓ1-minimization to improve the speed of the robust face recognition system. The paper also provides useful guidelines to practitioners working in similar fields, such as acoustic/speech recognition. Index Terms: face recognition, compressive sensing, ℓ1minimization 1.

This paper studies segmentation of multiple rigid-body motions in a 3-D dynamic scene under perspective camera projection. We consider dynamic scenes that contain both 3-D rigid-body structures and 2-D planar structures. Based on the well-known epipolar and homography constraints between two views, we propose a hybrid perspective constraint (HPC) to unify the representation of rigid-body and planar motions. Given a mixture of K hybrid perspective constraints, we propose an algebraic process to partition image correspondences to the individual 3-D motions, called Robust Algebraic Segmentation (RAS). Particularly, we prove that the joint distribution of image correspondences is uniquely determined by a set of (2K)-th degree polynomials, a global signature for the union of K motions of possibly mixed type. The first and second derivatives of these polynomials provide a means to recover the association of the individual image samples to their respective motions. Finally, using robust statistics, we show that the polynomials can be robustly estimated in the presence of moderate image noise and outliers. We conduct extensive simulations and real experiments to validate the performance of the new algorithm. The results demonstrate that RAS achieves notably higher accuracy than most existing robust motion-segmentation methods, including random sample consensus (RANSAC) and its variations. The implementation of the algorithm is also two to three times faster than the existing methods. The implementation of the algorithm and the benchmark scripts are available at http://perception.csl.illinois.edu/ras/ .

In this paper, sensor network scenarios are considered where the underlying signals of interest exhibit a degree of sparsity, which means that in an appropriate basis, they can be expressed in terms of a small number of nonzero coefficients. Following the emerging theory of compressive sensing (CS), an overall architecture is considered where the sensors acquire potentially noisy projections of the data, and the underlying sparsity is exploited to recover useful information about the signals of interest, which will be referred to as distributed sensor perception. First, we discuss the question of which projections of the data should be acquired, and how many of them. Then, we discuss how to take advantage of possible joint sparsity of the signals acquired by multiple sensors, and show how this can further improve the inference of the events from the sensor network. Two practical sensor applications are demonstrated, namely, distributed wearable action recognition using low-power motion sensors and distributed object recognition using high-power camera sensors. Experimental data support the utility of the CS framework in distributed sensor perception.

We consider the problem of automatically recognizing human faces from frontal views with varying expression and illumination, as well as occlusion and disguise. We cast the recognition problem as one of classifying among multiple linear regression models and argue that new theory from sparse signal representation offers the key to addressing this problem. Based on a sparse representation computed by l{1}-minimization, we propose a general classification algorithm for (image-based) object recognition. This new framework provides new insights into two crucial issues in face recognition: feature extraction and robustness to occlusion. For feature extraction, we show that if sparsity in the recognition problem is properly harnessed, the choice of features is no longer critical. What is critical, however, is whether the number of features is sufficiently large and whether the sparse representation is correctly computed. Unconventional features such as downsampled images and random projections perform just as well as conventional features such as Eigenfaces and Laplacianfaces, as long as the dimension of the feature space surpasses certain threshold, predicted by the theory of sparse representation. This framework can handle errors due to occlusion and corruption uniformly by exploiting the fact that these errors are often sparse with respect to the standard (pixel) basis. The theory of sparse representation helps predict how much occlusion the recognition algorithm can handle and how to choose the training images to maximize robustness to occlusion. We conduct extensive experiments on publicly available databases to verify the efficacy of the proposed algorithm and corroborate the above claims.

Human movement models often divide movements into parts. In walking, the stride can be segmented into four different parts, and in golf and other sports, the swing is divided into sections based on the primary direction of motion. These parts are often divided based on key events, also called temporal parameters. When analyzing a movement, it is important to correctly locate these key events, and so automated techniques are needed. There exist many methods for dividing specific actions using data from specific sensors, but for new sensors or sensing positions, new techniques must be developed. We introduce a generic method for temporal parameter extraction called the hidden Markov event model based on hidden Markov models. Our method constrains the state structure to facilitate precise location of key events. This method can be quickly adapted to new movements and new sensors/sensor placements. Furthermore, it generalizes well to subjects not used for training. A multiobjective optimization technique using genetic algorithms is applied to decrease error and increase cross-subject generalizability. Further, collaborative techniques are explored. We validate this method on a walking dataset by using inertial sensors placed on various locations on a human body. Our technique is designed to be computationally complex for training, but computationally simple at runtime to allow deployment on resource-constrained sensor nodes.

We consider the problem of simultaneously segmenting data samples drawn from multiple linear subspaces and estimating model parameters for those subspaces. This "subspace segmentation" problem naturally arises in many computer vision applications such as motion and video segmentation, and in the recognition of human faces, textures, and range data. Generalized Principal Component Analysis (GPCA) has provided an effective way to resolve the strong coupling between data segmentation and model estimation inherent in subspace segmentation. Essentially, GPCA works by first finding a global algebraic representation of the unsegmented data set, and then decomposing the model into irreducible components, each corresponding to exactly one subspace. We provide a summary of important algebraic properties and statistical facts that are crucial for making GPCA both efficient and robust, even when the given data are corrupted with noise or contaminated by outliers. We demonstrate the effectiveness of GPCA using a large testbed of synthetic and real experiments.

We study and compare two novel embedding methods for segmenting feature points of piece-wise planar structures from two (uncalibrated) perspective images. We show that a set of different homographies can be embedded in different ways to a higher-dimensional real or complex space, so that each homography corresponds to either a complex bilinear form or a real quadratic form. Each embedding reveals different algebraic properties and relations of homographies. We give a closed-form segmentation solution for each case by utilizing these properties based on subspace-segmentation methods. These theoretical results show that one can intrinsically segment a piece-wise planar scene from 2-D images without explicitly performing any 3-D reconstruction. The resulting segmentation may make subsequent 3-D reconstruction much better-conditioned. We demonstrate the proposed methods with some convincing experimental results.

In this paper, we investigate the mathematical problem underlying segmentation of hybrid motions: given a series of tracked feature correspondences between two (perspective) images, we seek to segment and estimate multiple motions, possibly of different types (e.g., affine, epipolar, and homography). In order to accomplish this task, we cast the problem into a more general mathematical framework of segmenting data samples drawn from a mixture of linear subspaces and quadratic surfaces. The result is a novel algorithm called hybrid quadratic surface analysis (HQSA). HQSA uses both the derivatives and Hessians of fitting polynomials for the data to separate linear data samples from quadratic data samples. These derivatives and Hessians also lead to important necessary conditions, based on the so-called mutual contraction subspace, to separate data samples on different quadratic surfaces. The algebraic solution we derive is non-iterative and numerically stable. It tolerates moderate noise and can be used in conjunction with outlier removal techniques. We show how to solve the hybrid motion segmentation problem using HQSA, and demonstrate its performance on simulated data with noise and on real perspective images.

This paper develops a new mathematical framework for studying the subspace-segmentation problem. We examine some important algebraic properties of subspace arrangements that are closely related to the subspace-segmentation problem. More specifically, we introduce an important class of invariants given by the Hilbert functions. We show that there exist rich relations between subspace arrangements and their corresponding Hilbert functions. We propose a new subspace-segmentation algorithm, and showcase two applications to demonstrate how the new theoretical revelation may solve subspace segmentation and model selection problems under less restrictive conditions with improved results.

We propose a mixture of multiple linear models, also known as hybrid linear model, for a sparse representation of an image. This is a generalization of the conventional Karhunen-Loeve transform (KLT) or principal component analysis (PCA). We provide an algebraic algorithm based on generalized principal component analysis (GPCA) that gives a global and noniterative solution to the identification of a hybrid linear model for any given image. We demonstrate the efficiency of the proposed hybrid linear model by experiments and comparison with other transforms such as the KLT, DCT and wavelet transforms. Such an efficient representation can be very useful for later stages of image processing, especially in applications such as image segmentation and image compression.

In this paper, we study how the presence of symmetry in man-made environments may significantly facilitate the task of automatic matching features and recovering 3-D camera pose and scene structure from multiple perspective images. While conventional methods typically rely on small-motion tracking or robust statistic techniques to resolve the coupling between feature matching and 3-D recovery, we here propose a new symmetry-based approach which allows automatic feature matching between images taken with arbitrary (both large and small) camera motions. To this end, we develop the multiple-view geometry of symmetry cells. To resolve possible ambiguities that may arise in matching symmetry cells and camera pose recovery, we find a consistent solution by finding the maximal complete subgraph of a matching graph; we also use a topological check to avoid mismatches. As our experiments shows, the resulting algorithms are simple, accurate and easy to implement.

Symmetry is an effective geometric cue to facilitate conventional segmentation techniques on images of man-made environment. Based on three fundamental principles that summarize the relations between symmetry and perspective imaging, namely, structure from symmetry, symmetry hypothesis testing, and global symmetry testing, we develop a prototype system which is able to automatically segment symmetric objects in space from single 2D perspective images. The result of such a segmentation is a hierarchy of geometric primitives, called symmetry cells and complexes, whose 3D structure and pose are fully recovered. Such a geometrically meaningful segmentation may greatly facilitate applications such as feature matching and robot navigation.

In this paper, we provide a principled and unified explanation how knowledge in global 3-D structural invariants, typically captured by a group action on a symmetric structure, can significantly facilitate the task of reconstructing a 3-D scene from one or more images. More importantly, the "absolute" pose between the camera frame and the canonical frame that symmetric objects (e.g., buildings, hallways) provide us overwhelming clues to their orientation and position. We give the necessary and sufficient conditions under which this pose can be uniquely determined, and when such conditions are not satisfied, exactly to what extent this pose can be recovered. We show how algorithms from conventional multiple-view geometry, after properly modified and extended, can be effectively applied to perform such recovery. Since the structure, pose and even camera calibration can be recovered from a single image; the techniques naturally apply to vision-based robot navigation where global position and orientation is important.