IEEE Transactions on Pattern Analysis and Machine Intelligence

PrePrint: A Fast Algorithm for Multidimensional Ellipsoid-Specific Fitting by Minimizing a New Defined Vector Norm of Residuals Using Semidefinite Programming

A quadratic surface in n-dimensional space is defined as the locus of zeros of a quadratic polynomial. The quadratic polynomial may be compactly written in notation by an (n+1)-vector and a real symmetric matrix of order n+1, where the vector represents homogenous coordinates of an n-D point, and the symmetric matrix is constructed from the quadratic coefficients. If an n-D quadratic surface is an n-D ellipsoid, the leading n-by-n principal submatrix of the symmetric matrix would be positive or opposite definite. As we know, to impose a matrix being positive or opposite definite, perhaps the best choice may be to employ semidefinite programming (SDP). From such straightforward and intuitive knowledge, in the literature till 2002, Calafiore first proposed a feasible method for multidimensional ellipsoid-specific fitting using SDP, which minimizes the 2-norm of the algebraic residual vector. However, runtime of the method is significantly long and memory is often out when the number of fitted points is greater than several thousand. In this paper, we propose a fast and easily implemented algorithm, by minimizing a new defined vector norm using SDP, which drastically decreases the size of the SDP problem while preserving accuracy. The proposed fast method can handle several million fitted points without any difficulty.

PrePrint: Trainable COSFIRE Filters for Keypoint Detection and Pattern Recognition

Background: Keypoint detection is important for many computer vision applications. Existing methods suffer from insufficient selectivity regarding the shape properties of features and are vulnerable to contrast variations and to the presence of noise or texture. Methods: We propose a trainable filter which we call COSFIRE (Combination Of Shifted FIlter REsponses) and use for keypoint detection and pattern recognition. It is automatically configured to be selective for a local contour pattern specified by an example. The configuration comprises selecting given channels of a bank of Gabor filters and determining certain blur and shift parameters. A COSFIRE filter response is computed as the weighted geometric mean of the blurred and shifted responses of the selected Gabor filters. It shares similar properties with some shape-selective neurons in visual cortex, which provided inspiration for this work. Results: We demonstrate the effectiveness of the proposed filters in three applications: the detection of retinal vascular bifurcations (DRIVE data set: 98.50% recall, 96.09% precision), the recognition of handwritten digits (MNIST data set: 99.48% correct classification), and the detection and recognition of traffic signs in complex scenes (100% recall and precision). Conclusions: The proposed COSFIRE filters are conceptually simple and easy to implement. They are versatile keypoint detectors and are highly effective in practical computer vision applications.

PrePrint: Robust Simultaneous Registration and Segmentation with Sparse Error Reconstruction

We introduce a fast and efficient variational framework for simultaneous registration and segmentation applicable to a wide variety of image sequences. We demonstrate that a dense correspondence map (between consecutive frames) can be reconstructed correctly even in the presence of partial occlusion, shading and reflections. The errors are efficiently handled by exploiting their sparse nature. In addition, the segmentation functional is reformulated using a dual Rudin-Osher-Fatemi (ROF) model for fast implementation. Moreover, non-parametric shape prior terms that are suited for this dual-ROF model are proposed. The efficacy of the proposed method is validated with extensive experiments on both indoor, outdoor natural and biological image sequences demonstrating the higher accuracy and efficiency compared to various state-of-the-art methods.

PrePrint: Tree-structured CRF Models for Interactive Image Labeling

We propose structured prediction models for image labeling that explicitly take into account dependencies among image labels. In our tree structured models, image labels are nodes, and edges encode dependency relations. To allow for more complex dependencies, we combine labels in a single node, and use mixtures of trees. Our models are more expressive than independent predictors, and lead to more accurate label predictions. The gain becomes more significant in an interactive scenario where a user provides the value of some of the image labels at test time. Such an interactive scenario offers an interesting trade-off between label accuracy and manual labeling effort. The structured models are used to decide which labels should be set by the user, and transfer the user input to more accurate predictions on other image labels. We also apply our models to attribute-based image classification, where attribute predictions of a test image are mapped to class probabilities by means of a given attribute-class mapping. Experimental results on three publicly available benchmark data sets show that in all scenarios our structured models lead to more accurate predictions, and leverage user input much more effectively than state-of-the-art independent models.

PrePrint: A Hybrid Multi-View Stereo Algorithm for Modeling Urban Scenes

We present an original multi-view stereo reconstruction algorithm which allows the 3D-modeling of urban scenes as a combination of meshes and geometric primitives. The method provides a compact model while preserving details: irregular elements such as statues and ornaments are described by meshes whereas regular structures such as columns and walls are described by primitives (planes, spheres, cylinders, cones and tori). We adopt a two-step strategy consisting first in segmenting the initial mesh-based surface using a multi-label Markov Random Field based model and second, in sampling primitive and mesh components simultaneously on the obtained partition by a Jump-Diffusion process. The quality of a reconstruction is measured by a multi-object energy model which takes into account both photo-consistency and semantic considerations (i.e. geometry and shape layout). The segmentation and sampling steps are embedded into an iterative refinement procedure which provides an increasingly accurate hybrid representation. Experimental results on complex urban structures and large scenes are presented and compared to the state-of-the-art multi-view stereo meshing algorithms.

PrePrint: Removing Atmospheric Turbulence via Space-Invariant Deconvolution

To correct geometric distortion and reduce space and time-varying blur, a new approach is proposed in this paper capable of restoring a single high-quality image from a given image sequence distorted by atmospheric turbulence. This approach reduces the space and time-varying deblurring problem to a shift invariant one. It first registers each frame to suppress geometric deformation through B-spline based non-rigid registration. Next, a temporal regression process is carried out to produce an image from the registered frames, which can be viewed as being convolved with a space invariant near-diffraction-limited blur. Finally, a blind deconvolution algorithm is implemented to deblur the fused image, generating a final output. Experiments using real data illustrate that this approach can effectively alleviate blur and distortions, recover details of the scene and significantly improve visual quality.

PrePrint: A Novel Bayesian Framework for Discriminative Feature Extraction in Brain-Computer Interfaces

As there has been a paradigm shift in the learning load from a human subject to a computer, machine learning has been considered as a useful tool for Brain-Computer Interfaces (BCIs). In this paper, we propose a novel Bayesian framework for discriminative feature extraction for motor imagery classification in an EEG-based BCI, in which the class-discriminative frequency bands and the corresponding spatial filters are optimized by means of the probabilistic and information-theoretic approaches. In our framework, the problem of simultaneous spatio-spectral filter optimization is formulated as the estimation of an unknown posterior pdf that represents the probability that a single-trial EEG of predefined mental tasks can be discriminated in a state. In order to estimate the posterior pdf, we propose a particle-based approximation method by extending a factored-sampling technique with a diffusion process. An information-theoretic observation model is also devised to measure discriminative power of features between classes. From the viewpoint of classifier design, the proposed method naturally allows us to construct a spectrally weighted label decision rule by linearly combining the outputs from multiple classifiers. We demonstrate the feasibility and effectiveness of the proposed method by analyzing the results and its success on three public databases.

PrePrint: Recognizing Human-Object Interactions in Still Images by Modeling the Mutual Context of Objects and Human Poses

Detecting objects in cluttered scenes and estimating articulated human body parts from 2D images are two challenging problems in computer vision. The difficulty is particularly pronounced in activities involving human-object interactions (e.g. playing tennis), where the relevant objects tend to be small or only partially visible, and the human body parts are often self-occluded. We observe, however, that objects and human poses can serve as mutual context to each other - recognizing one facilitates the recognition of the other. In this paper we propose a mutual context model to jointly model objects and human poses in human-object interaction activities. In our approach, object detection provides a strong prior for better human pose estimation, while human pose estimation improves the accuracy of detecting the objects that interact with the human. On a six-class sports dataset and a 24-class people interacting with musical instruments dataset, we show that our mutual context model outperforms state-of-the-art in detecting very difficult objects and estimating human poses, as well as classifying human-object interaction activities.

PrePrint: Whole-Book Recognition

Whole-book recognition is a document image analysis strategy that operates on the complete set of a book's page images using automatic adaptation to improve accuracy. The algorithm is initialized with approximate iconic and linguistic models---derived from (generally errorful) OCR results and (generally imperfect) dictionaries---and then, guided entirely by evidence internal to the test set, corrects the models which, in turn, yields higher recognition accuracy. It detects "disagreements" by measuring cross entropy between (1) the posterior probability distribution of character classes, and (2) the posterior probability distribution of word classes. We show how disagreements can identify candidates for model corrections at both the character and word levels. Experiments on passages up to one hundred and eighty pages long show that when a candidate model adaptation reduces whole-book disagreement, it is also likely to correct recognition errors. Also, the longer the passage operated on by the algorithm, the more reliable this adaptation policy becomes, and the lower the error rate achieved. Best results occur when both the iconic and linguistic models mutually correct one another. We have observed recognition error rates driven down by nearly an order of magnitude fully automatically without supervision (or indeed without any user intervention).

PrePrint: Semi-Supervised Hashing for Large Scale Search

Hashing based approximate nearest neighbor (ANN) search in huge databases has become popular owing to its computational and memory efficiency. The popular hashing methods, e.g., Locality Sensitive Hashing and Spectral Hashing, construct hash functions based on random or principal projections. The resulting hashes are either not very accurate or inefficient. Moreover these methods are designed for a given metric similarity. On the contrary, semantic similarity is usually given in terms of pairwise labels of samples. In this work, we propose a semi-supervised hashing (SSH) framework that minimizes empirical error over the labeled set and an information theoretic regularizer over both labeled and unlabeled set. Based on this framework, we present three different semi-supervised hashing methods, including orthogonal hashing, non-orthogonal hashing, and sequential hashing. Particularly, the sequential hashing method generates robust codes in which each hash function is designed to correct the errors made by the previous ones. We further show that the sequential learning paradigm can be extended to unsupervised domains where no labeled pairs are available. Extensive experiments on four large datasets (up to 80 million samples) demonstrate the superior performance of the proposed SSH methods over state-of-the-art supervised and unsupervised hashing techniques.

PrePrint: A Model-based Sequence Similarity with Application to Handwritten Word-spotting

This article proposes a novel similarity measure between vector sequences. We work in the framework of model-based approaches, where each sequence is first mapped to a Hidden Markov Model (HMM) and then a probabilistic measure of similarity is computed between the HMMs. We propose to model sequences with semi-continuous HMMs (SC-HMMs). This is a particular type of HMM whose emission probabilities in each state are mixtures of shared Gaussians. This crucial constraint provides two major benefits. First, the a priori information contained in the common set of Gaussians leads to a more accurate estimate of the HMM parameters. Second, the computation of a probabilistic similarity between two SC-HMMs can be simplified to a Dynamic Time Warping (DTW) between their mixture weight vectors, which reduces significantly the computational cost. Experiments are carried out on a handwritten word retrieval task in three different datasets - an in-house dataset of real handwritten letters, the George Washington dataset and the IFN/ENIT dataset of Arabic handwritten words. These experiments show that the proposed similarity outperforms the traditional DTW between the original sequences, and the model-based approach which uses ordinary continuous HMMs. We also show that this increase in accuracy can be traded against a significant reduction of the computational cost.

PrePrint: RASL: Robust Alignment by Sparse and Low-rank Decomposition for Linearly Correlated Images

This paper studies the problem of simultaneously aligning a batch of linearly correlated images despite gross corruption (such as occlusion). Our method seeks an optimal set of image domain transformations such that the matrix of transformed images can be decomposed as the sum of a sparse matrix of errors and a low-rank matrix of recovered aligned images. We reduce this extremely challenging optimization problem to a sequence of convex programs that minimize the sum of l1-norm and nuclear norm of the two component matrices, which can be efficiently solved by fast and scalable convex optimization techniques. We verify the efficacy of the proposed robust alignment algorithm with extensive experiments on both controlled and uncontrolled real data, demonstrating higher accuracy and efficiency than existing methods over a wide range of realistic misalignments and corruptions.

PrePrint: Ensemble Segmentation Using Efficient Integer Linear Programming

We present a method for combining several segmentations of an image into a single one, that is in some sense is the average segmentation, in order to achieve a more reliable and accurate segmentation result. The goal is to find a point in the "space of segmentations" which is close to all the individual segmentations. We present an algorithm for segmentation averaging. The image is first over-segmented into superpixels. Next, each segmentation is projected onto the superpixel map. An instance of the EM algorithm combined with integer linear programming is applied on the set of binary merging decisions of neighboring superpixels to obtain the average segmentation. Apart from segmentation averaging, the algorithm also reports the reliability of each segmentation. The performance of the proposed algorithm is demonstrated on manually annotated images from the Berkeley segmentation dataset and on the results of automatic segmentation algorithms.

PrePrint: Pushing the Envelope of Modern Methods for Bundle Adjustment

In this paper, we present results and experiments with several methods for bundle adjustment, producing the fastest bundle adjuster ever published in terms of computation and convergence. From a computational perspective, the fastest methods naturally handle the block-sparse pattern that arises in a reduced camera system. Adapting to the naturally arising block-sparsity allows the use of BLAS3, efficient memory handling, fast variable ordering, and customized sparse solving all simultaneously. We present two methods; one uses exact minimum degree ordering and block-based LDL solving, and the other uses block-based preconditioned conjugate gradients. Both methods are performed on the reduced camera system. We show experimentally that the adaptation to the natural block sparsity allows both of these methods to perform better than previous methods. Further improvements in convergence speed are achieved by the novel use of embedded point iterations. Embedded point iterations take place inside each camera update step yielding a greater cost decrease from each camera update step and, consequently, a lower minimum. This is especially true for points projecting far out on the flatter region of the robustifier. Intensive analyses from various angles demonstrate the improved performance of the presented bundler.

IEEE Transactions on Pattern Analysis and Machine Intelligence - July 2012 (Vol. 34, No. 7)

IEEE Transactions on Pattern Analysis and Machine Intelligence

PrePrint: A Framework for Mining Signatures from Event Sequences and Its Applications in Healthcare Data

This paper proposes a novel temporal knowledge representation and learning framework to perform large-scale temporal pattern mining of longitudinal heterogeneous event data. The framework enables the representation, extraction, and mining of high-order latent event structure and relationships within single and multiple event squences. The proposed knowledge representation maps the heterogeneous event sequences to a geometric image by encoding events as a structured spatial-temporal shape process. We present a doubly constrained convolutional sparse coding framework that learns interpretable and shift-invariant latent temporal event patterns. We show how to cope with the sparsity in the data as well as in the latent factor model by inducing a double sparsity constraint on the $\beta$-divergence to learn an over-complete sparse latent factor model. A novel stochastic optimization scheme performs large-scale incremental learning of group-specific temporal event patterns. We validate the framework on synthetic data and on an electronic health record dataset.

PrePrint: Simultaneous Cast Shadows, Illumination & Geometry Inference Using Hypergraphs

The cast shadows in an image provide important information about illumination and geometry. In this paper, we utilize this information in a novel framework, in order to jointly recover the illumination environment, a set of geometry parameters and an estimate of the cast shadows in the scene, given a single image and coarse initial 3D geometry. We model the interaction of illumination and geometry in the scene and associate it with image evidence for cast shadows using a higher-order Markov Random Field (MRF) illumination model, while we also introduce a method to obtain approximate image evidence for cast shadows. Capturing the interaction between light sources and geometry in the proposed graphical model necessitates higher-order cliques and continuous-valued variables, which make inference challenging. Taking advantage of domain knowledge, we provide a two-stage minimization technique for the MRF energy of our model. We evaluate our method in different datasets, both synthetic and real. Our model is robust to rough knowledge of geometry and inaccurate initial shadow estimates, allowing a generic coarse 3D model to represent a whole class of objects for the task of illumination estimation, or the estimation of geometry parameters to refine our initial knowledge of scene geometry, simultaneously with illumination estimation.

PrePrint: Design and Estimation of Coded Exposure Point Spread Functions

We address the problem of motion deblurring using coded exposure. This approach allows for accurate estimation of a sharp latent image via well-posed deconvolution, and avoids lost image content that cannot be recovered from images acquired with a traditional shutter. Previous work in this area has used either manual user input or alpha matting approaches to estimate the coded exposure point spread function (PSF) from the input image. In order to automate de-blurring, and to avoid the limitations of matting approaches, we propose a Fourier-domain statistical approach to coded exposure PSF estimation that allows us to estimate the latent image in cases of constant velocity, constant acceleration, and harmonic motion. We also demonstrate that previously-used criteria to choose a coded exposure PSF do not necessarily produce one with optimal reconstruction error, and that an additional 50% reduction in Root Mean Squared Error (RMSE) of the latent image can be achieved by considering other measures of PSF quality.

PrePrint: A Dual Decomposition Approach to Feature Correspondence

In this paper we present a new approach for establishing correspondences between sparse image features related by an unknown non-rigid mapping and corrupted by clutter and occlusion, such as points extracted from images of different instances of the same object category. We formulate this matching task as an energy minimization problem by defining a complex objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general an NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples, DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods.

PrePrint: CoSLAM: Collaborative Visual SLAM in Dynamic Environments

This paper studies the problem of vision-based simultaneous localization and mapping (SLAM) in dynamic environments with multiple cameras. These cameras move independently and can be mounted on different platforms. All cameras work together to build a global map, including 3D positions of static background points and trajectories of moving foreground points. We introduce inter-camera pose estimation and inter-camera mapping to deal with dynamic objects in the localization and mapping process. To further enhance the system robustness, we maintain the position uncertainty of each map point. To facilitate inter-camera operations, we cluster cameras into groups according to their view overlap, and manage the split and merge of camera groups in real-time. Experimental results demonstrate that our system can work robustly in highly dynamic environments and produce more accurate results in static environments.

PrePrint: Stochastic Exploration of Ambiguities for Non-Rigid Shape Recovery

Recovering the 3D shape of deformable surfaces from single images is known to be a highly ambiguous problem because many different shapes may have very similar projections. This is commonly addressed by restricting the set of possible shapes to linear combinations of deformation modes and by imposing additional geometric constraints. Unfortunately, because image measurements are noisy, such constraints do not always guarantee that the correct shape will be recovered. To overcome this limitation, we introduce an stochastic sampling approach to efficiently explore the set of solutions of an objective function based on point correspondences. This allows to propose a small set of ambiguous candidate 3D shapes and then use additional image information to choose the best one. As a proof of concept, we use either motion or shading cues to this end and show that we can handle a complex objective function without having to solve a difficult non-linear minimization problem. The advantages of our method are demonstrated on a variety of problems including both real and synthetic data.

PrePrint: Object Matching Using a Locally Affine Invariant and Linear Programming Techniques

In this paper, we introduce a new matching method based on a novel locally affine-invariant geometric constraint and linear programming techniques. To model and solve the matching problem in a linear programming formulation, all geometric constraints should be able to be exactly or approximately reformulated into a linear form. This is a major difficulty for this kind of matching algorithms. We propose a novel locally affine-invariant constraint which can be exactly linearized and requires a lot fewer auxiliary variables than other linear programming based methods do. The key idea behind it is that each point in the template point set can be exactly represented by an affine combination of its neighboring points, whose weights can be solved easily by least squares. Errors of reconstructing each matched point using such weights are used to penalize the disagreement of geometric relationships between the template points and the matched points. The resulting overall objective function can be solved efficiently by linear programming techniques. Our experimental results on both rigid and non-rigid object matching show the effectiveness of the proposed algorithm.

PrePrint: Biologically Inspired Object Tracking Using Center-surround Saliency Mechanisms

A biologically inspired discriminant object tracker is proposed. It is argued that discriminant tracking is a consequence of top-down tuning of the saliency mechanisms that guide the deployment of visual attention. The principle of discriminant saliency is then used to derive a tracker that implements a combination of center-surround saliency, a spatial spotlight of attention, and feature based attention. In this framework, the tracking problem is formulated as one of continuous target-background classification, implemented in two stages. The first, or learning stage, combines a focus of attention mechanism and bottom-up saliency to identify a maximally discriminant set of features for target detection. The second, or detection stage, uses a feature based attention mechanism and a target-tuned top-down discriminant saliency detector, to detect the target. Overall, the tracker iterates between learning discriminant features from the target location in a video frame and detecting the location of the target in the next. The statistics of natural images are exploited to derive an implementation which is conceptually simple and computationally efficient. The saliency formulation is also shown to establish a unified framework for classifier design, target detection, automatic tracker initialization, and scale adaptation. Experimental results show that the proposed discriminant saliency tracker outperforms a number of state-of-the art trackers in the literature.

PrePrint: Simultaneous Video Stabilization and Moving Object Detection in Turbulence

Turbulence mitigation refers to the stabilization of videos with non-uniform deformations due to the influence of optical turbulence. Typical approaches for turbulence mitigation follow averaging or de-warping techniques. Although these methods can reduce the turbulence, they distort the independently moving objects which can often be of great interest. In this paper, we address the novel problem of simultaneous turbulence mitigation and moving object detection. We propose a novel three-term low-rank matrix decomposition approach in which we decompose the turbulence sequence into three components: the background, the turbulence, and the object. We simplify this extremely difficult problem into a minimization of nuclear norm, Frobenius norm, and l1 norm. Our method is based on two observations: First, the turbulence causes dense and Gaussian noise, and therefore can be captured by Frobenius norm, while the moving objects are sparse and thus can be captured by l1 norm. Second, since the object's motion is linear and intrinsically different than the Gaussian-like turbulence, a Gaussian-based turbulence model can be employed to enforce an additional constraint on the search space of the minimization. We demonstrate the robustness of our approach on challenging sequences which are significantly distorted with atmospheric turbulence and include extremely tiny moving objects.

PrePrint: Learning Multivariate Distributions by Competitive Assembly of Marginals

We present a new framework for learning high-dimensional multivariate probability distributions from estimated marginals. The approach is motivated by compositional models and Bayesian networks, and designed to adapt to small sample sizes. We start with a large, overlapping set of elementary statistical building blocks, or "primitives", which are low-dimensional marginal distributions learned from data. Each variable may appear in many primitives. Subsets of primitives are combined in a lego-like fashion to construct a probabilistic graphical model; only a small fraction of the primitives will participate in any valid construction. Since primitives can be precomputed, parameter estimation and structure search are separated. Model complexity is controlled by strong biases; we adapt the primitives to the amount of training data and impose rules which restrict the merging of them into allowable compositions. The likelihood of the data decomposes into a sum of local gains, one for each primitive in the final structure. We focus on a specific subclass of networks which are binary forests. Structure optimization corresponds to an integer linear program and the maximizing composition can be computed for reasonably large numbers of variables. Performance is evaluated using both synthetic data and real datasets from natural language processing and computational biology.

PrePrint: Image Transformation based on Learning Dictionaries across Image Spaces

In this paper, we propose a framework of transforming images from a source image space to a target image space, based on learning coupled dictionaries from a training set of paired images. The framework can be used for applications such as image super-resolution, and estimation of image intrinsic components (shading and albedo). It is based on a local parametric regression approach, using sparse feature representations over learned coupled dictionaries across the source and target image spaces. The contributions of our proposed framework are three-fold. (1) We propose a concept of coupled dictionary learning based on coupled sparse coding, which requires the sparse coefficient vectors of a pair of corresponding source and target image patches have the same support, i.e., the same indices of nonzero elements. (2) We devise a space partitioning scheme to divide the high-dimensional but sparse feature space into local clusters. The partitioning facilitates extremely fast retrieval of closest local clusters for query patches. (3) Benefiting from sparse feature based image transformation, our method is more robust to corrupted input data, and can be considered as a simultaneous image restoration and transformation process. Experiments on intrinsic image estimation and super-resolution demonstrate the effectiveness and efficiency of our proposed method.

PrePrint: State-of-the-art in Visual Attention Modeling

Modeling visual attention -- particularly stimulus-driven, saliency-based attention -- has been a very active research area over the past 25 years. Many different models of attention are now available, which aside from lending theoretical contributions to other fields, have demonstrated successful applications in computer vision, mobile robotics, and cognitive systems. Here we review, from a computational perspective, the basic concepts of attention implemented in these models. We present a taxonomy of nearly 65 models, which provides a critical comparison of approaches, their capabilities, and shortcomings. In particular, thirteen criteria derived from behavioral and computational studies are formulated for qualitative comparison of attention models. Furthermore, we address several challenging issues with models, including biological plausibility of the computations, correlation with eye movement datasets, bottom-up and top-down dissociation, and constructing meaningful performance measures. Finally, we highlight current research trends in attention modeling and provide insights for future.

PrePrint: Human Pose Co-Estimation and Applications

Most existing techniques for articulated human pose estimation consider each person independently. Here we tackle the problem in a new setting, coined Human Pose Co-estimation (PCE), where multiple persons are in a common, but unknown pose. The task of PCE is to estimate their poses jointly and to produce prototypes characterizing the shared pose. Since the poses of the individual persons should be similar to the prototype, PCE has less freedom compared to estimating each pose independently, which simplifies the problem. We demonstrate our PCE technique on two applications. The first is estimating pose of people performing the same activity synchronously, such as during aerobic, cheerleading and dancing in a group. We show that PCE improves pose estimation accuracy over estimating each person independently. The second application is learning prototype poses characterizing a pose class directly from an image search engine queried by the class name (e.g. `lotus pose'). We show that PCE leads to better pose estimation in such images, and it learns meaningful prototypes which can be used as priors for pose estimation in novel images.

PrePrint: Categorizing Dynamic Textures using a Bag of Dynamical Systems

Categorizing videos of dynamic textures (DTs) (nonrigid dynamical objects such as fire, water, etc.) is an extremely challenging problem because of their continuous change in shape and appearance. State-of-the-art DT categorization methods have been successful at classifying videos taken from the same viewpoint and scale by using a linear dynamical system (LDS) to model each video and metrics between LDSs to classify them. However, these methods perform poorly when the videos are taken from different viewpoints or scales. In this paper, we propose a novel DT categorization framework that can handle these changes by modeling DTs with a collection of LDSs, each describing a small spatiotemporal patch extracted from the video. This Bag-of-Systems (BoS) representation is analogous to the Bag-of-Features (BoF) representation for object recognition, except that we use LDSs as feature descriptors. The space of LDSs, however, is not Euclidean, and hence methods for computing codewords of LDSs need to be developed. Our framework uses nonlinear dimensionality reduction, clustering techniques and distances for LDSs to tackle this issue. Our experiments show that our approach can be used for categorizing DTs in challenging scenarios, which could not be handled by existing methods.

PrePrint: Probabilistic Tracking of Affine-Invariant Anisotropic Regions

Despite a wide range of feature detectors developed in the computer vision community over the years, direct application of these techniques to surgical navigation has shown significant difficulties due to the paucity of reliable salient features coupled with free-form tissue deformation and changing visual appearance of surgical scenes. The aim of this paper is to propose a novel probabilistic framework to track affine-invariant anisotropic regions under contrastingly different visual appearances during Minimally Invasive Surgery (MIS). The theoretical background of the affine-invariant anisotropic feature detector is presented and a real-time implementation exploiting the computational power of the GPU is proposed. An Extended Kalman Filter (EKF) parameterisation scheme is used to adaptively adjust the optimal templates of the detected regions, enabling accurate identification and matching of the tracked features. For effective tracking verification, spatial context and region similarity have also been incorporated. They are used to boost the prediction of the EKF and recover potential tracking failure due to drift or false positives. The proposed framework is compared to the existing methods and their respective performance is evaluated with in vivo video sequences recorded from robotic assisted MIS procedures, as well as real-world scenes.

PrePrint: Consensus Clustering Based on a New Probabilistic Rand Index with Application to Subtopic Retrieval

We introduce a probabilistic version of the well known Rand Index for measuring the similarity between two partitions, called Probabilistic Rand Index (PRI), in which agreements and disagreements at the object-pair level are weighted according to the probability of their occurring by chance. We then cast consensus clustering as an optimization problem of the PRI value between a target partition and a set of given partitions, experimenting with a simple and very efficient stochastic optimization algorithm. Remarkable performance gains over input partitions as well as over existing related methods are demonstrated through a range of applications, including a new use of consensus clustering to improve subtopic retrieval.

PrePrint: On Detection of Multiple Object Instances using Hough Transforms

Hough transform based methods for detecting multiple objects use non-maxima suppression or mode-seeking to locate and distinguish peaks in Hough images. Such postprocessing requires tuning of many parameters and is often fragile, especially when objects are located spatially close to each other. In this paper, we develop a new probabilistic framework for object detection which is related to the Hough transform. It shares the simplicity and wide applicability of the Hough transform but at the same time, bypasses the problem of multiple peak identification in Hough images, and permits detection of multiple objects without invoking non-maximum suppression heuristics. Our experiments demonstrate that this method results in a significant improvement in detection accuracy both for the classical task of straight line detection and for a more modern category-level (pedestrian) detection problem.

PrePrint: Estimating Information from Image Colors: An Application to Digital Cameras and Natural Scenes

The colors present in an image of a scene provide information about its constituent elements. But the amount of information depends on the imaging conditions and on how information is calculated. This work had two aims. The first was to derive explicitly estimators of the information available and the information retrieved from the color values at each point in images of a scene under different illuminations. The second was to apply these estimators to simulations of images obtained with five sets of sensors used in digital cameras and with the cone photoreceptors of the human eye. Estimates were obtained for 50 hyperspectral images of natural scenes under daylight illuminants with correlated color temperatures 4000 K, 6500 K, and 25000 K. Depending on the sensor set, the mean estimated information available across images with the largest illumination difference varied from 15.5 to 18.0 bits and the mean estimated information retrieved after optimal linear processing varied from 13.2 to 15.5 bits (each about 85% of the corresponding information available). With the best sensor set, 390% more points could be identified per scene than with the worst. Capturing scene information from image colors depends crucially on the choice of camera sensors.

PrePrint: Discriminative Multi-Manifold Analysis for Face Recognition from A Single Training Sample per Person

Conventional appearance-based face recognition methods usually assume that there are multiple samples per person (MSPP) available during the training phase for discriminative feature extraction. In many practical face recognition applications such as law enhancement, e-passport and ID card identification, this assumption, however, may not hold as there is only a single sample per person (SSPP) enrolled or recorded in these systems. Many popular face recognition methods fail to work well in this scenario because there are not enough samples for discriminant learning. To address this problem, we propose in this paper a novel discriminative multi-manifold analysis (DMMA) method by learning discriminative features from image patches. First, we partition each enrolled face image into several non-overlapping patches to form an image set for each sample per person. Then, we formulate the SSPP face recognition as a manifold-manifold matching problem and learn multiple DMMA feature spaces to maximize the manifold margins of different persons. Lastly, we propose a reconstruction-based manifold-manifold distance to identify the unlabeled subjects. Experimental results on three widely used face databases are presented to demonstrate the efficacy of the proposed approach.

PrePrint: Large-margin Predictive Latent Subspace Learning for Multi-view Data Analysis

Learning from multi-view data is important in many applications such as image classification, retrieval and annotation. Standard predictive methods, such as support vector machines that are built with all the variables available without taking into consideration the presence of distinct views, would sacrifice predictive performance and may also be incapable of performing view-level analysis. In this paper, we present a statistical method to learn a predictive subspace representation shared by multiple views when supervising side information is provided and perform view-level predictions. Our approach is based on a multi-view latent subspace Markov network (MN) which fulfills a weak conditional independence assumption that multi-view observations and response variables are conditionally independent given a set of latent variables. To learn the latent subspace multi-view MN, we develop a large-margin approach which jointly maximizes data likelihood and minimizes a prediction loss on training data. The learning and inference problems are efficiently solved with a contrastive divergence method. Finally, we extensively evaluate the large-margin multi-view latent subspace MN on real TRECVID video, Flickr web image and hotel review datasets for classification, regression, image annotation and retrieval. Our results demonstrate that the large-margin approach can achieve significant improvements in terms of prediction performance and discovering predictive latent subspace representations.

PrePrint: A New In-Camera Imaging Model for Color Computer Vision and its Application

We present a study of the in-camera image processing through an extensive analysis of more than 10,000 images from over 30 cameras. The goal of this work is to investigate if image values can be transformed to physically meaningful values, and if so, when and how this can be done. From our analysis, we found a major limitation of the imaging model employed in conventional radiometric calibration methods and propose a new in-camera imaging model that fits well with today's cameras. With the new model, we present associated calibration procedures that allow us to convert an sRGB images back to their original CCD RAW responses in a manner that is significantly more accurate than any existing methods. Additionally, we show how this new imaging model can be used to build an image correction application that converts an sRGB input image captured with the wrong camera settings to an sRGB output image that would have been recorded under the correct settings of a specific camera.

PrePrint: Generalized Projection Based M-Estimator

We propose a novel robust estimation algorithm - the generalized projection based M-estimator (gpbM), which does not require the user to specify any scale parameters. The algorithm is general and can handle heteroscedastic data with multiple linear constraints for single and multi-carrier problems. The gpbM has three distinct stages -- scale estimation, robust model estimation and inlier/outlier dichotomy. In contrast, in its predecessor pbM, each model hypotheses was associated with a different scale estimate. For data containing multiple inlier structures with generally different noise covariances, the estimator iteratively determines one structure at a time. The model estimation can be further optimized by using Grassmann manifold theory. We present several homoscedastic and heteroscedastic synthetic and real-world computer vision problems with single and multiple carriers.

PrePrint: A Probabilistic Approach to Spectral Graph Matching

Spectral matching is a computationally efficient approach to the approximate solution of pairwise matching problems that are np-hard. In this work we present a probabilistic interpretation of spectral matching schemes and derive a novel probabilistic matching scheme that is shown to outperform previous approaches. We show that spectral matching can be interpreted as a maximum likelihood estimate of the assignment probabilities and that the Graduated Assignment algorithm can be cast as a Maximum a Posteriori estimator. Based on this analysis we derive a ranking scheme for spectral matchings based on their reliability, and propose a novel iterative probabilistic matching algorithm that relaxes some of the implicit assumption used in prior works. We experimentally show our approaches to outperforms previous schemes when applied to exhaustive synthetic tests, as well as the analysis of real image sequences.

PrePrint: Detecting Mutual Awareness Events

It is quite common that multiple human observers attend to a single static interest point. This is known as a mutual awareness event (MAWE). A preferred way to monitor these situations is with a camera that captures the human observers while using existing face detection and head pose estimation algorithms. The current work studies the underlying geometric constraints of MAWEs and reformulates them in terms of image measurements. The constraints are then used in a method that (1) detects whether such an interest point does exist, (2) determines where it is located, (3) identifies who was attending to it, and (4) reports where and when each observer was while attending to it. The method is also applied on another interesting event when a single moving human observer fixates on a single static interest point. The method can deal with the general case of an uncalibrated camera in a general environment. This is in contrast to other work on similar problems that inherently assume a known environment or a calibrated camera. The method was tested on about 75 images from various scenes and robustly detects MAWEs and estimates their related attributes. Most of the images were found by searching the Internet.

PrePrint: A Quantitative Evaluation of Confidence Measures for Stereo Vision

We present an extensive evaluation of 17 confidence measures for stereo matching that compares the most widely used measures as well as several novel techniques proposed here. We begin by categorizing these methods according to which aspects of stereo cost estimation they take into account and, then, assess their strengths and weaknesses. The evaluation is conducted using a winner-take-all framework on binocular and multi-baseline datasets with ground truth. It measures the capability of each confidence method to rank depth estimates according to their likelihood for being correct, to detect occluded pixels and to generate low-error depth maps by selecting among multiple hypotheses for each pixel. Our work was motivated by the observation that such an evaluation is missing from the rapidly maturing stereo literature and that our findings would be helpful to researchers binocular and multi-view stereo.

PrePrint: Shape Retrieval using Hierarchical Total Bregman Soft Clustering

We consider the family of total Bregman divergences (tBDs) as an efficient and robust "distance" measure to quantify the dissimilarity between shapes.The tBD based L1-norm center is used as the representative of a set of shapes, called the t-center. We then prove that for any tBD, there exists a distribution which belongs to the lifted exponential family of distributions. Further, we show that finding the MAP estimate of the parameters of this family is equivalent to minimizing the tBD to find the t-centers. This leads to a new clustering technique namely, the total Bregman soft clustering algorithm. We evaluate the tBD, t-center and the soft clustering algorithm on shape retrieval applications. Our shape retrieval framework is composed of three steps: (1) extraction of the shape boundary points (2) affine alignment of the shapes and use of a Gaussian mixture model (GMM) to represent the aligned boundaries, and (3) comparison of the GMMs using tBD to find the best matches given a query shape. To further speed up the shape retrieval algorithm, we perform hierarchical clustering of the shapes using the tBD soft clustering algorithm. We evaluate our method on various public domain 2D and 3D databases, and demonstrate comparable or better results than state-of-the-art retrieval techniques.

PrePrint: An Efficient Hidden Variable Approach to Minimal-Case Camera Motion Estimation

In this paper we present an efficient new approach for addressing two-view minimal-case problems in camera motion estimation, most notably the so-called five-point relative orientation, and the six-point focal-length problem. Our approach is based on the hidden variable technique for solving multivariate polynomial systems. The resulting algorithm is conceptually simple, which involves a relaxation which replaces monomials in all but one of the variables to reduce the problem to the solution of sets of linear equations, and finding the solution of a polynomial eigenvalue problem. To actually solve the polynomial eigenvalues efficiently, we make novel use of several numeric techniques, which include quotient-free Gaussian elimination, Levinson-Durbin iteration, as well as a dedicated root-polishing procedure. We have tested the approach on different minimal cases and extensions, with very satisfactory results obtained. Both executables and source codes of the proposed algorithms are made online and freely downloadable.

PrePrint: Single and Multiple Object Tracking Using Log-Euclidean Riemannian Subspace and Block-Division Appearance Model

Object appearance modeling is crucial for tracking objects especially in videos captured by non-stationary cameras and for reasoning about occlusions between multiple moving objects. Based on the log-Euclidean Riemannian metric on symmetric positive definite matrices, we propose an incremental log-Euclidean Riemannian subspace learning algorithm in which covariance matrices of image features are mapped into a vector space with the log-Euclidean Riemannian metric. Based on the subspace learning algorithm, we develop a log-Euclidean block-division appearance model which captures both the global and local spatial layout information about object appearances. Single object tracking and multi-object tracking with occlusion reasoning are then achieved by particle filtering-based Bayesian state inference. During tracking, incremental updating of the log-Euclidean block-division appearance model captures changes in object appearance. For multi-object tracking, the appearance models of the objects can be updated even in the presence of occlusions. Experimental results demonstrate that the proposed tracking algorithm obtains more accurate results than six state-of-the-art tracking algorithms.

PrePrint: Subspace Learning from Image Gradient Orientations

We introduce the notion of subspace learning from image gradient orientations for appearance-based object recognition. As image data is typically noisy and noise is substantially different from Gaussian, traditional subspace learning from pixel intensities fails very often to estimate reliably the low-dimensional subspace of a given data population. We show that replacing pixel intensities with gradient orientations and the $\ell_2$ norm with a cosine-based distance measure offers, to some extend, a remedy to this problem. Within this framework, which we coin IGO (Image Gradient Orientations) subspace learning, we first formulate and study the properties of Principal Component Analysis of image gradient orientations (IGO-PCA). We then show its connection to previously proposed robust PCA techniques both theoretically and experimentally. Finally, we derive a number of other popular subspace learning techniques, namely Linear Discriminant Analysis (LDA), Locally Linear Embedding (LLE) and Laplacian Eigenmaps (LE). Experimental results show that our algorithms outperform significantly popular methods such as Gabor features and Local Binary Patterns and achieve state-of-the-art performance for difficult problems such as illumination- and occlusion-robust face recognition. In addition to this, the proposed IGO-methods require the eigen-decomposition of simple covariance matrices and are as computationally efficient as their corresponding $\ell_2$ norm intensity-based counterparts.

PrePrint: Tensor Completion for Estimating Missing Values in Visual Data

In this paper we propose an algorithm to estimate missing values in tensors of visual data. Our methodology is built on recent studies about matrix completion using the matrix trace norm. The contribution of our paper is to extend the matrix case to the tensor case by proposing the first definition of the trace norm for tensors and then by building a working algorithm. First, we propose a definition for the tensor trace norm, that generalizes the established definition of the matrix trace norm. Second, similar to matrix completion, the tensor completion is formulated as a convex optimization problem. We developed three algorithms: SiLRTC, FaLRTC, and HaLRTC. The SiLRTC algorithm is simple to implement and employs a relaxation technique to separate the dependant relationships and uses the block coordinate descent (BCD) method to achieve a globally optimal solution; The FaLRTC algorithm utilizes a smoothing scheme to transform the original nonsmooth problem into a smooth one; The HaLRTC algorithm applies the alternating direction method of multipliers (ADMM) to our problem. Our experiments show potential applications of our algorithms and the quantitative evaluation indicates that our methods are more accurate and robust than heuristic approaches.

PrePrint: Meaningful Scales Detection along Digital Contours for Unsupervised Local Noise Estimation

The automatic detection of noisy or damaged parts along digital contours is a difficult problem, since it is hard to distinguish between information and perturbation without further a priori hypotheses. However, solving this issue has a great impact on numerous applications, including image segmentation, geometric estimators, contour reconstruction, shape matching or image edition. We propose an original strategy to detect what are the relevant scales at which each point of the digital contours should be considered. It relies on theoretical results of asymptotic discrete geometry. A direct consequence is the automatic detection of the noisy or damaged parts of the contour, together with its quantitative evaluation (or noise level). Apart from a given maximal observation scale, the proposed approach does not require any parameter tuning and is easy to implement. We demonstrate its effectiveness on several datasets. We present different direct applications of this local measure to contour smoothing and geometric estimators, whose algorithms initially required a noise/scale parameter to tune: they show the pertinence of the proposed measure for digital shape analysis and reconstruction.

PrePrint: Extended SRC: Undersampled Face Recognition via Intra-Class Variant Dictionary

Sparse Representation based Classification (SRC) is a face-recognition breakthrough in recent years, which has successfully addressed the recognition problem with sufficient training images of each gallery subject. In this paper, we extend SRC to applications where there are very few, or even a single, training images per subject. Assuming that the intra-class variations of one subject can be approximated by a sparse linear combination of those of other subjects, Extended SRC (ESRC) applies an auxiliary intra-class variant dictionary to represent the possible variation between the training and testing images. The dictionary atoms typically represent intra-class sample differences computed from either the gallery faces themselves, or the generic faces that are outside the gallery. Experimental results on AR and FERET databases show that ESRC has better generalization ability than SRC for undersampled face recognition under variable expressions, illuminations, disguises, and ages. The superior results of ESRC suggest that if the dictionary is properly constructed, sparse representation based algorithms can generalize well to the large-scale face recognition problem, even with a single training image per class.

PrePrint: Learning Image Similarity from Flickr Groups Using Fast Kernel Machines

Measuring image similarity is a central topic in computer vision. In this paper, we propose to measure image similarity by learning from the online Flickr image groups. We do so by: choosing 103 Flickr groups; building a one-vs-all multi-class classifier to classify test images into a group; taking the set of responses of the classifiers as features; calculating the distance between feature vectors to measure image similarity. Experimental results on the Corel dataset and the PASCAL VOC 2007 dataset show that our approach performs better on image matching, retrieval, and classification than using conventional visual features. To build our similarity measure, we need one-vs-all classifiers that are accurate, and can be trained quickly on very large quantities of data. We adopt an SVM classifier with a histogram intersection kernel. We describe a novel fast training algorithm for this classifier: the Stochastic Intersection Kernel MAchine (SIKMA) training algorithm. This method can produce a kernel classifier that is more accurate than a linear classifier, on tens of thousands of examples in minutes

PrePrint: Measuring the Objectness of Image Windows

We present a generic objectness measure, quantifying how likely it is for an image window to contain an object of any class. We explicitly train it to distinguish objects with a well-defined boundary in space, such as cows and telephones, from amorphous background elements, such as grass and road. The measure combines in a Bayesian framework several image cues measuring characteristics of objects, such as appearing different from their surroundings and having a closed boundary. These include an innovative cue to measure the closed boundary characteristic. In experiments on the challenging PASCAL VOC 07 dataset, we show this new cue to outperform a state-of-the-art saliency measure, and the combined objectness measure to perform better than any cue alone. We also compare to interest point operators, a HOG detector, and three recent works aiming at automatic object segmentation. Finally, we present two applications of objectness. In the first, we sample a small number windows according to their objectness probability and give an algorithm to employ them as location priors for modern class-specific object detectors. This greatly reduces the number of windows evaluated by the expensive class-specific model. In the second application, we use objectness as a complementary score in addition to the class-specific model, which leads to fewer false positives.

PrePrint: Structured Learning of Human Interactions in TV Shows

The objective of this work is recognition and spatio-temporal localization of two-person interactions in video. We consider four types of interactions: hand-shakes, high fives, hugs and kisses. Our approach is person-centric, and we first track all upper bodies and heads in a video using a tracking-by-detection approach that combines detections with KLT tracking and clique partitioning, together with occlusion detection to yield robust person tracks. We develop local descriptors of activity based on the head orientation (estimated using a set of pose-specific classifiers) and the local spatio-temporal region around them, together with global descriptors that encode the relative positions of people as a function of interaction type. Learning and inference on the model uses a structured output SVM which combines the local and global descriptors in a principled manner. We develop an efficient polynomial complexity cutting plane algorithm for the learning. Inference using the model yields information about which pairs of people are interacting, their interaction class, and their head orientation (which is also treated as a variable, enabling mistakes in the classifier to be corrected using global context). The method is evaluated on a new data-set comprising 300 video clips acquired from 23 different TV shows.