IEEE Transactions on Pattern Analysis and Machine Intelligence

PrePrint: Surface-From-Gradients Without Discrete Integrability Enforcement: A Gaussian Kernel Approach

Representative surface reconstruction algorithms taking a gradient field as input enforces the integrability constraint in a discrete manner. While enforcing integrability allows the subsequent integration to produce surface heights, existing algorithms suffer one or more of the following disadvantages: they can only handle dense per-pixel gradient fields, smooth out sharp features in a partially integrable field, or produce severe surface distortion in the results. We present a method which does not base on discrete integrability enforcement, and reconstructs a 3D continuous surface from a gradient or a height field, or a combination of both, which can be dense or sparse. The key of our approach is the use of kernel basis functions, which transfers the continuous surface reconstruction problem into high dimensional space where a closed-form solution exists. This leads to a neat implementation while producing results better than traditional techniques. A more important advantage of using kernel basis functions is that it does not suffer discretization and finite approximation, both of which leads to surface distortion, which is typical of Fourier or wavelet bases widely adopted by previous representative approaches. We perform comparison with to demonstrate that our method produces accurate surface reconstruction that preserves salient features.

IEEE Transactions on Pattern Analysis and Machine Intelligence - December 2009 (Vol. 31, No. 12)

PrePrint: Efficient Sequential Correspondence Selection by Cosegmentation

In many retrieval, object recognition and wide baseline stereo methods, correspondences of interest points (distinguished regions, transformation covariant points) are established possibly sublinearly by matching compact descriptors such as SIFTs. We show that a subsequent cosegmentation process coupled with a quasi-optimal sequential decision process leads to a correspondence verification procedure that (i) has high precision (is highly discriminative) (ii) has good recall and (iii) is fast. The sequential decision on the correctness of a correspondence is based on simple statistics of a modified dense stereo matching algorithm. The statistics are projected on a prominent discriminative direction by SVM. Wald's sequential probability ratio test is performed on the SVM projection computed on progressively larger co-segmented regions. We show experimentally that the process significantly outperforms the standard correspondence selection method based on SIFT distance ratios on challenging matching problems.

PrePrint: Coupled Prediction-Classification for Robust Visual Tracking

This paper addresses the problem of robust template tracking in image sequences. Our work falls within the discriminative framework in which the observations at each frame yield direct probabilistic predictions of the state of the target. Our primary contribution is that we explicitly address the problem that the prediction accuracy for different observations varies, and in some cases can be very low. To this end, we couple the predictor to a probabilistic classifier which, when trained, can determine the probability that a new observation can accurately predict the state of the target (that is, determine the 'relevance' or 'reliability' of the observation in question). In the particle filtering framework, we derive a recursive scheme for maintaining an approximation of the posterior probability of the state in which multiple observations can be used and their predictions moderated by their corresponding relevance. In this way the predictions of the 'relevant' observations are emphasized, while the predictions of the 'irrelevant' observations are suppressed. We apply the algorithm to the problem of 2D template tracking and demonstrate that the proposed scheme outperforms classical methods for discriminative tracking both in the case of motions which are large in magnitude and also for partial occlusions.

PrePrint: Stages as Models of Scene Geometry

Reconstruction of 3D scene geometry is an important element for scene understanding, autonomous vehicle and robot navigation, image retrieval and 3D television. We propose accounting for the inherent structure of the visual world when trying to solve the scene reconstruction problem. Consequently, we identify geometric scene categorization as the first step towards robust and efficient depth estimation from single images. We introduce 15 typical 3D scene geometries called stages, each with a unique depth profile, which roughly correspond to a large majority of broadcast video frames. Stage information serves as a first approximation of global depth, narrowing down the search space in depth estimation and object localization. We propose different sets of low-level features for depth estimation, and perform stage classification on two diverse datasets of television broadcasts. Classification results demonstrate that stages can often be efficiently learned from low-dimensional image representations.

PrePrint: Skewed Rotation Symmetry Group Detection

We present a novel and effective algorithm for affinely skewed rotation symmetry group detection from real-world images. We define a complete skewed rotation symmetry detection problem as discovering five independent properties of a rotation symmetry group: (1) the center of rotation; (2) the affine deformation; (3) the type of the symmetry group; (4) the cardinality of the symmetry group; and (5) the supporting region of the symmetry group in the image. We propose a frieze-expansion (FE) method that transforms rotation symmetry group detection into a simple one dimensional translation symmetry detection problem. We define and construct a pair of rotational symmetry saliency maps, complemented by a local feature method. Frequency analysis, using Discrete Fourier Transform (DFT), is applied to the Frieze-expansion patterns (FEPs) to uncover the types (cyclic, dihedral and O(2)), the cardinalities and the corresponding supporting regions of multiple rotation symmetry groups in an image, concentric or otherwise. The phase information of the FEP is used to rectify affinely skewed rotation symmetry groups. Our result advances the state of the art in symmetry detection by offering a unique combination of region-based, feature-based and frequency-based approach. Experimental results on 170 synthetic and natural images demonstrate superior performance of our rotation symmetry detection algorithm over existing methods.

PrePrint: Object Detection with Discriminatively Trained Part Based Models

We describe an object detection system based on mixtures of multiscale deformable part models. Our system is able to represent highly variable object classes and achieves state-of-the-art results in the PASCAL object detection challenges. While deformable part models have become quite popular, their value had not been demonstrated on difficult benchmarks such as the PASCAL datasets. Our system relies on new methods for discriminative training with partially labeled data. We combine a margin-sensitive approach for data-mining hard negative examples with a formalism we call \emph{latent SVM}. A latent SVM is a reformulation of MI-SVM in terms of latent variables. A latent SVM is semi-convex and the training problem becomes convex once latent information is specified for the positive examples. This leads to an iterative training algorithm that alternates between fixing latent values for positive examples and optimizing the latent SVM objective function.

PrePrint: Large Scale Discovery of Spatially Related Images

We propose a randomized data mining method that finds clusters of spatially overlapping images. The core of the method relies on the min-Hash algorithm for fast detection of pairs of images with spatial overlap, the so-called cluster seeds. The seeds are then used as visual queries to obtain clusters which are formed as transitive closures of sets of partially overlapping images that include the seed. We show that the probability of finding a seed for an image cluster rapidly increases with the size of the cluster. The properties and performance of the algorithm are demonstrated on datasets with 10^4, 10^5, and 5 · 10^6 images. The speed of the method depends on the size of the database and on the number of clusters. The first stage of seed generation is close to linear for databases sizes up to approximately 2^34 (10^10) images. On a single 2.4GHz PC, the clustering process took only 24 minutes for a standard database of more than hundred thousand images, i.e. only 0.014 seconds per image.

PrePrint: Class Conditional Nearest Neighbor for Large Margin Instance Selection

This paper presents a relational framework for studying properties of labeled data points related to proximity and labeling information in order to improve the performance of the 1NN rule. Specifically, the class conditional nearest neighbor (ccnn) relation over pairs of points in a labeled training set is introduced. For a given class label c this relation associates to each point a its nearest neighbor computed among only those points with class label c (excluded a). A characterization of ccnn in terms of two graphs is given. These graphs are used for defining a novel scoring function over instances by means of an information-theoretic divergence measure applied to the degree distributions of these graphs. The scoring function is employed to develop an effective large margin instance selection method, which is empirically demonstrated to improve storage and accuracy performance of the 1NN rule on artificial and reallife data sets.

PrePrint: Visualization of Spatiotemporal Behavior of Discrete Maps via Generation of Recursive Median Elements

Spatial interpolation is one of the demanding techniques in Geographic Information Science (GISci) to generate interpolated maps in a continuous manner by using two discrete spatial and/or temporal data sets. Noise-free data (thematic layers) depicting a specific theme at varied spatial or temporal resolutions consist of connected components either in aggregated or in disaggregated forms. This short paper provides a simple framework (i) to categorize the connected components of layered sets of two different time instants through their spatial relationships and the Hausdorff distances between the companion connected components, and (ii) to generate sequential maps (interpolations) between the discrete thematic maps. Development of the median set, using Hausdorff erosion and dilation distances to interpolate between temporal frames is demonstrated on lake geometries mapped at two different times, and also on the bubonic plague epidemic spread data available for eleven consecutive years. We documented the significantly fair quality of the median sets generated for epidemic data between alternative years by visually comparing the interpolated maps with actual maps. They can be used to visualize (animate) the spatio-temporal behavior of a specific theme in a continuous sequence.

PrePrint: Range Flow in Varying Illumination: Algorithms and Comparisons

We extend estimation of range flow to handle brightness changes in image data caused by inhomogeneous illumination. Standard range flow computes 3D velocity fields using both range and intensity image sequences. Towards this end, range flow estimation combines a depth change model with a brightness constancy model. However, local brightness is generally not preserved when object surfaces rotate relative to the camera or the light sources, or when surfaces move in inhomogeneous illumination. We describe and investigate different approaches to handle such brightness changes. A straightforward approach is to prefilter the intensity data such that brightness changes are suppressed, for instance by a highpass or a homomorphic filter. Such prefiltering may, though, reduce the signal to noise ratio. An alternative novel approach is to replace the brightness constancy model by (1) a gradient constancy model, or (2) by a combination of gradient and brightness constancy constraints used earlier successfully for optical flow, or (3) by a physics-based brightness change model. In performance tests, the standard version and the novel versions of range flow estimation are investigated using prefiltered or non-prefiltered synthetic data with available ground truth. Furthermore, the influences of additive Gaussian noise and simulated shot noise are investigated. We finally compare all range flow estimators on real data.

PrePrint: Accurate, Dense, and Robust Multi-View Stereopsis

This article proposes a novel algorithm for multi-view stereopsis that outputs a dense set of small rectangular patches covering the surfaces visible in the images. Stereopsis is implemented as a match, expand, and filter procedure, starting from a sparse set of matched keypoints, and repeatedly expanding these before using visibility constraints to filter away false matches. The keys to the performance of the proposed algorithm are effective techniques for enforcing local photometric consistency and global visibility constraints. Simple but effective methods are also proposed to turn the resulting patch model into a mesh which can be further refined by an algorithm that enforces both photometric consistency and regularization constraints. The proposed approach automatically detects and discards outliers and obstacles, and does not require any initialization in the form of a visual hull, a bounding box, or valid depth ranges. We have tested our algorithm on various datasets including objects with fine surface details, deep concavities, and thin structures, outdoor scenes observed from a restricted set of viewpoints, and "crowded" scenes where moving obstacles appear in front of a static structure of interest. A quantitative evaluation on the Middlebury benchmark shows that the proposed method outperforms all others submitted so far for four out of the six datasets.

PrePrint: WLD: A Robust Local Image Descriptor

Inspired by Weber's Law, this paper proposes a simple, yet very powerful and robust local descriptor, called the Weber Local Descriptor (WLD). It is based on the fact that human perception of a pattern depends not only on the change of a stimulus (such as sound, lighting) but also on the original intensity of the stimulus. Specifically, WLD consists of two components: differential excitation and orientation. The differential excitation component is a function of the ratio between two terms: one is the relative intensity differences of a current pixel against its neighbors; the other is the intensity of the current pixel. The orientation component is the gradient orientation of the current pixel. For a given image, we use the two components to construct a concatenated WLD histogram. Experimental results on the Brodatz and KTH-TIPS2-a texture databases show that WLD impressively outperforms the other widely used descriptors (e.g., Gabor and SIFT). In addition, experimental results on human face detection also show a promising performance comparable to the best known results on the MIT+CMU frontal face test set, the AR face dataset and the CMU profile test set.

PrePrint: Evaluating Color Descriptors for Object and Scene Recognition

Image category recognition is important to access visual information on the level of objects and scene types. So far, intensity-based descriptors have been widely used for feature extraction at salient points. To increase illumination invariance and discriminative power, color descriptors have been proposed. Because many different descriptors exist, a structured overview is required of color invariant descriptors in the context of category recognition. Therefore, this paper studies the invariance properties and the distinctiveness of color descriptors in a structured way. The analytical invariance properties of color descriptors are explored, using a taxonomy based on invariance properties with respect to photometric transformations, and tested experimentally using a dataset with known illumination conditions. In addition, the distinctiveness of color descriptors is assessed experimentally using two category recognition benchmarks. From the theoretical and experimental results, it can be derived that invariance to light intensity changes and light color changes affects category recognition. Results reveal further that, for light intensity changes, the usefulness of invariance is category-specific. Overall, when choosing a single descriptor and no prior knowledge about the categories and the dataset is available, OpponentSIFT is recommended. Furthermore, a combined set of color descriptors outperforms intensity-based SIFT and improves category recognition by 8% on PASCAL VOC2007 and by 10% on the Mediamill Challenge.

PrePrint: Training-free, Generic Object Detection using Locally Adaptive Regression Kernels

We present a generic detection/localization algorithm capable of searching for a visual object of interest without training. The proposed method operates using a single example of an object of interest to find similar matches; does not require prior knowledge (learning) about objects being sought; and does not require any pre-processing step or segmentation of a target image. Our method is based on the computation of local regression kernels as descriptors from a query, which measure the likeness of a pixel to its surroundings. Salient features are extracted from said descriptors and compared against analogous features from the target image. This comparison is done using a matrix generalization of the cosine similarity measure. We illustrate optimality properties of the algorithm using a naive-Bayes framework. The algorithm yields a scalar resemblance map, indicating the likelihood of similarity between the query and all patches in the target image. By employing nonparametric significance tests and non-maxima suppression, we detect the presence and location of objects similar to the given query. The approach is extended to account for large variations in scale and rotation. High performance is demonstrated on several challenging datasets, indicating successful detection of objects in diverse contexts and under different imaging conditions.

PrePrint: Geometric Feature Extraction by a Multi-Marked Point Process

This paper presents a new stochastic marked point process for describing images in terms of a finite library of geometric objects. Image analysis based on conventional marked point processes has already produced convincing results but at the expense of easy parameter tuning, short computing time, and unspecific models. Our more general multi-marked point process has simpler parametric setting, yields notably shorter computing times and can be applied to a variety of applications. Both linear and areal primitives extracted from a library of geometric objects are matched to a given image using a probabilistic Gibbs model, and a Jump-Diffusion process is performed to search for the optimal object configuration. Experiments with remotely sensed images and natural textures show the proposed approach has good potential. We conclude with a discussion about the insertion of more complex object interactions in the model by studying the compromise between model complexity and efficiency.

PrePrint: Layered Graph Matching with Composite Cluster Sampling

Many computer vision tasks can be posed as either a graph partitioning problem or a graph matching problem. In this paper, we study a framework of layered graph matching for integrating graph partition and matching with graph editing. The objective is to find an unknown number of corresponding graph structures in two images. We extract discriminative local primitives from both images and construct a candidacy graph whose vertices are match candidates (i.e. a pair of primitives) and whose edges are either negative for mutual exclusion or a positive for mutual consistence. Then we pose layered graph matching as a multi-coloring problem on the candidacy graph. We adapt a composite cluster sampling algorithm to work with both positive and negative edges. The algorithm assigns some vertices into a number of colors, each being a matched layer, and turns off all the remaining candidates. The algorithm iterates two steps: (i) Sampling the positive and negative edges probabilistically to form a composite cluster; (ii) Assigning new colors to these CCPs with consistence and exclusion relations maintained. The algorithm demonstrates state-of-the-art performance when it is applied to a number of applications on several public data sets.

PrePrint: Mixtures of Factor Analyzers with Common Factor Loadings: Applications to the Clustering and Visualisation of High-Dimensional Data

Mixtures of factor analyzers enable model-based density estimation to be undertaken for high-dimensional data, where the number of observations n is not very large relative to their dimension p. In practice, there is often the need to reduce further the number of parameters in the specification of the component-covariance matrices. To this end, we propose the use of common component-factor loadings, which considerably reduces further the number of parameters. Moreover, it allows the data to be displayed in low-dimensional plots.

PrePrint: A Generalized Kernel Consensus-Based Robust Estimator

In this paper, we present a new Adaptive Scale Kernel Consensus (ASKC) robust estimator as a generalization of the popular and state-of-the-art robust estimators such as RANSAC (RANdom SAmple Consensus), ASSC (Adaptive Scale Sample Consensus) and MKDE (Maximum Kernel Density Estimator). The ASKC framework is grounded on and unifies these robust estimators in the nonparametric kernel density estimation theory. In particular, we show that each of these methods is a special case of ASKC using a specific kernel. Like these methods, ASKC can tolerate more than 50 percent outliers, while it can also automatically estimate the scale of inliers. We apply ASKC to two important areas in computer vision: robust motion estimation and pose estimation, and show comparative results on both synthetic and real data.

PrePrint: Efficient Multilevel Eigensolvers with Applications to Data Analysis Tasks

Multigrid solvers proved very efficient for solving massive systems of equations in various fields. These solvers are based on iterative relaxation schemes together with the approximation of the "smooth" error function on a coarser level (grid). We present two efficient multilevel eigensolvers for solving massive eigenvalue problems that emerge in data analysis tasks. The first solver, a version of classical algebraic multigrid (AMG), is applied to eigen-problems arising in clustering, image segmentation, and dimensionality reduction, demonstrating an order of magnitude speedup compared to the popular Lanczos algorithm. The second solver is based on a new, much more accurate interpolation scheme. It enables calculating very inexpensively a large number of eigenvectors.

PrePrint: Designing Highly Reliable Fiducial Markers

Fiducial Markers are artificial landmarks added to a scene to facilitate locating point correspondences between images, or between images and a known model. Reliable fiducials solve the interest point detection and matching problems when adding markers is convenient. The proper design of fiducials and the associated computer vision algorithms to detect them can enable accurate pose detection for applications ranging from augmented reality, input devices for HCI, to robot navigation. Marker systems typically have two stages, hypothesis generation from unique image features and verification/identification. A set of criteria for high robustness and practical use are identified, and then optimized to produce the ARTag fiducial marker system. An edge-based method robust to lighting and partial occlusion is used for the hypothesis stage, and a reliable digital coding system is used for the identification and verification stage. Using these design criteria large gains in performance are achieved by ARTag over conventional ad hoc designs.

PrePrint: Image Segmentation with A Unified Graphical Model

We propose a unified graphical model that can represent both the causal and non-causal relationships among random variables and apply it to image segmentation problem. Specifically, we first propose to employ Conditional Random Field (CRF) to model the spatial relationships among image superpixel regions and their measurements. We then introduce a multi-layer Bayesian Network (BN) to model the causal dependencies that naturally exist among different image entities including image regions, edges, and vertices. The CRF model and the BN model are then systematically and seamlessly combined through the theories of Factor Graph to form a unified probabilistic graphical model that captures the complex relationships among different image entities. Using the unified graphical model, image segmentation can be performed through a principled probabilistic inference. Experimental results on the Weizmann horse dataset, on the VOC2006 cow dataset, and on the MSRC2 multiclass dataset demonstrate that our approach achieves favorable results compared to the state-of-the-art approaches as well as those that use either BN model or CRF model alone.

PrePrint: Fusion Moves for Markov Random Field Optimization

The efficient application of graph cuts to Markov Random Fields (MRFs) with multiple discrete or continuous labels remains an open question. In this paper, we demonstrate one possible way of achieving this by using graph cuts to combine pairs of suboptimal labelings or solutions. We call this combination process the fusion move. By employing recently developed graph cut based algorithms (so-called QPBO-graph cut), the fusion move can efficiently combine two proposal labelings in a theoretically sound way, which is in practice often globally optimal. We demonstrate that fusion moves generalize many previous graph cut approaches, which allows them to be used as building block within a broader variety of optimization schemes than were considered before. In particular, we propose new optimization schemes for computer vision MRFs with applications to image restoration, stereo, and optical flow, among others. Within these schemes the fusion moves are used 1) for the parallelization of MRF optimization into several threads; 2) for fast MRF optimization by combining cheap-to-compute solutions; and 3) for the optimization of highly non-convex continuous-labeled MRFs with 2D labels. Our final example is a non-vision MRF concerned with cartographic label placement, where fusion moves can be used to improve the performance of a standard inference method (loopy belief propagation).

PrePrint: Point Set Registration Via Particle Filtering and Stochastic Dynamics

In this paper, we propose a particle filtering approach for the problem of registering two point sets that differ by a rigid body transformation. Typically, registration algorithms compute the transformation parameters by maximizing a metric given an estimate of the correspondence between points across the two sets of interest. This can be viewed as a posterior estimation problem, in which the corresponding distribution can naturally be estimated using a particle filter. In this work, we treat motion as a local variation in pose parameters obtained by running a few iterations of a certain local optimizer. Employing this idea, we introduce stochastic motion dynamics to widen the narrow band of convergence often found in local optimizer approaches for registration. Experimental results are provided that demonstrate the robustness of the algorithm to initialization, noise, missing structures or differing point densities in each sets, on challenging 2D and 3D registration tasks.

PrePrint: A Variational Approach to Degraded Document Enhancement

The goal of this paper is to correct bleed-through in degraded documents using a variational approach. The variational model is adapted using an estimated background according to the availability of the verso side of the document image. Furthermore, for the latter case, a more advanced model based on a global control, the flow field, is introduced. The solution of each resulting model is obtained using wavelet shrinkage or a time-stepping scheme, depending on the complexity and nonlinearity of the models. When both sides of the document are available, the proposed model uses the reverse diffusion process for the enhancement of double-sided document images. The results of experiments with real and synthesized samples are promising. The proposed model, which is robust with respect to noise and complex background, can also be applied to other fields of image processing.

PrePrint: Iris Recognition: On the Segmentation of Degraded Images Acquired in the Visible Wavelength

Iris recognition imaging constraints are receiving increasing attention. There are several proposals to develop systems that operate in the visible wavelength and in less constrained environments. These imaging conditions engender acquired noisy artifacts that lead to severely degraded images, making iris segmentation a major issue. Having observed that existing iris segmentation methods tend to fail in these challenging conditions, we present a segmentation method that can handle degraded images acquired in less constrained conditions. We offer the following contributions: 1) To consider the sclera the most easily distinguishable part of the eye in degraded images. 2) To propose a new type of feature that measures the proportion of sclera in each direction and is fundamental in segmenting the iris. 3) To run the entire procedure in deterministically linear time in respect of the size of the image, making the procedure suitable for real-time applications.

PrePrint: Online Empirical Evaluation of Tracking Algorithms

Evaluation of tracking algorithms in the absence of ground truth is a challenging problem. There exist a variety of approaches for this problem, however, few of these methods scale up to the task of visual tracking where the models are usually non-linear and complex, and typically lie in a high dimensional space. We propose a performance evaluation strategy for tracking systems based on particle filter using a time-reversed Markov chain. The core intuition relies on the time-reversible nature of physical motion exhibited by most objects, which in turn should be possessed by a good tracker. This reversible nature of the tracker is usually violated when tracking fails. We use this property for detection of track failures and characterization of tracking performance. We compute the posterior density of track parameters at the starting time t = 0 by filtering back in time to the initial time instant. The distance between the posterior density of the time-reversed chain (at t = 0) and the prior density used to initialize the tracking algorithm forms the decision statistic for evaluation. We provide a thorough experimental analysis of the evaluation methodology for different tracking algorithms in tackling common challenges such as occlusion, pose and illumination changes.

PrePrint: Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction

The LP relaxation approach to weighted constraint satisfaction (Gibbs energy minimization) has been mostly considered only for binary (= pairwise) problems. We present its generalization to n-ary problems which is simple and natural. This includes a simple algorithm to minimize the LP-based upper bound, n-ary max-sum diffusion; however, other bound-optimizing algorithms can be used as well. The diffusion iteration is tractable for a certain class of high-arity constraints represented as a black-box function. Diffusion exactly solves permuted n-ary supermodular problems. A hierarchy of gradually tighter LP relaxations is obtained simply by adding various zero constraints and coupling them in various ways to existing constraints. Zero constraints can be added incrementally, which leads to a cutting plane algorithm. We give conditions on when adding a set of cutting planes leads to a better relaxation – in particular, this is so if the sub-CSP induced by it has no solution. Throughout the text, we relate Gibbs energy minimization to many works from constraint programming, which relation has so far been ignored in computer vision and machine learning.

PrePrint: The Patch Transform

The patch transform represents an image as bag of overlapping patches sampled on a regular grid. This representation allows users to manipulate images in the patch domain, which then seeds the inverse patch transform to synthesize a modified image. Possible modifications in the patch domain include the spatial locations of patches, the size of the output image, or the pool of patches from which an image is reconstructed. When no modifications are made, the inverse patch transform reduces to solving a jigsaw puzzle. The inverse patch transform is posed as a patch assignment problem on a Markov random field (MRF), where each patch should be used only once, and neighboring patches should fit to form a plausible image. We find an approximate solution to the MRF using loopy belief propagation, introducing an approximation that encourages the solution to use each patch only once. The image reconstruction algorithm scales well with the total number of patches through the use of a label pruning method that finds loops of patches that are likely to fit together. In addition, structural misalignment artifacts are supressed through a patch jittering scheme that spatially shifts the assigned patches by a sub-patch size. We demonstrate the patch transform and its effectiveness on natural images.

PrePrint: Visual Word Ambiguity

This paper studies automatic image classification by modeling soft-assignment in the popular codebook model. The codebook model describes an image as a bag of discrete visual words selected from a vocabulary, where the frequency distributions of visual words in an image allow classification. One inherent component of the codebook model is the assignment of discrete visual words to continuous image features. Despite the clear mismatch of this hard assignment with the nature of continuous features, the approach has been applied successfully for some years. In this paper we investigate four types of soft-assignment. We demonstrate that explicitly modeling assignment ambiguity improves classification performance compared to the traditional codebook model for five well-known datasets: 15 natural scenes, Caltech-101, Caltech-256, and Pascal VOC 2007/2008. We show that our method profits in high-dimensional feature spaces and is robust to increasing the number of image categories. Moreover, we demonstrate that for large codebook vocabulary sizes the performance of the traditional model completely deteriorates, while the proposed model performs consistently.

PrePrint: Hierarchical Bayesian Modeling of Topics in Time-Stamped Documents

We consider the problem of inferring and modeling topics in a sequence of documents with known publication dates. The documents at a given time are each characterized by a topic, and the topics are drawn from a mixture model. The proposed model infers the change in the topic mixture weights as a function of time. The details of this general framework may take different forms, depending on the specifics of the model. For the examples considered here we examine base measures based on independent multinomial-Dirichlet measures for representation of topic-dependent word counts. The form of the hierarchical model allows efficient variational Bayesian (VB) inference, of interest for large-scale problems. We demonstrate results and make comparisons to the model when the dynamic character is removed, and also compare to latent Dirichlet allocation (LDA) and topics over time (TOT). We consider a database of NIPS papers as well as the United States presidential State of the Union addresses from 1790 to 2008.

PrePrint: An Information-Theoretic Derivation of Min-Cut Based Clustering

Min-cut clustering, based on minimizing one of two heuristic cost-functions proposed by Shi and Malik nearly a decade ago, has spawned tremendous research, both analytic and algorithmic, in the graph partitioning and image segmentation communities over the last decade. It is however unclear if these heuristics can be derived from a more general principle facilitating generalization to new problem settings. Motivated by an existing graph partitioning framework, we derive relationships between optimizing relevance information, as defined in the Information Bottleneck method, and the regularized cut in a K-partitioned graph. For fast-mixing graphs, we show that the cost functions introduced by Shi and Malik can be well approximated as the rate of loss of predictive information about the location of random walkers on the graph. For graphs drawn from a generative model designed to describe community structure, the optimal information-theoretic partition and the optimal min-cut partition are shown to be the same with high probability.

PrePrint: Survey on Pedestrian Detection for Advanced Driver Assistance Systems

Advanced driver assistance systems (ADAS), and particularly pedestrian protection systems (PPSs), have become a very active research area aimed at improving traffic safety. The major challenge of PPSs is related to the development of reliable on-board pedestrian detection systems. Due to the varying appearance of pedestrians (e.g., different clothes, changing size and aspect ratio, dynamic shape) and the unstructured environment it is very difficult to cope with the demanded robustness of this kind of systems. An arising problem in this research area is (i) the lack of public benchmarks and (ii) the difficulty of reproducing some of the proposed methods, making it hard to compare different approaches. As a result, surveying the bibliography just by enumerating the proposals one-after-another is not the most useful way to provide a comparative point of view. Therefore, we present in this paper a more convenient strategy to survey the different approaches: we divide the problem of detecting pedestrians from images into different processing steps, each one with attached responsibilities. Then, the different proposed methods are analyzed and classified with respect to each processing stage with the intention of favoring a comparative viewpoint. Finally, discussions on the important topics are presented, putting special emphasis on the future needs and challenges.

PrePrint: Order Preserving Moves for Graph Cut Based Optimization

Graph-cut optimization has been popular for a variety of labeling problems. Typically graph-cut methods are used to incorporate smoothness constraints on a labeling, namely most nearby pixels are encouraged to have similar labels. In addition to smoothness, ordering constraints on labels are also useful. For example, in object segmentation, a pixel with a car wheel label may be prohibited above a pixel with a car roof label. We observe that the commonly used graph-cut alpha-expansion move algorithm is more likely to get stuck in a local minimum when ordering constraints are used. For a certain model with ordering constraints, we develop new graph-cut moves which we call order-preserving. The advantage of order-preserving moves is that they act on all labels simultaneously, unlike alpha-expansion. More importantly, for most labels alpha, the set of alpha-expansion moves is strictly smaller than the set of order-preserving moves. This explains why in practice optimization with order-preserving moves performs significantly better than expansion in presence of ordering constraints. We evaluate order-preserving moves for the geometric class scene labeling, where the goal is to assign each pixel a label such as sky, ground, etc., so ordering constraints arise naturally. In addition, we use order-preserving moves for certain simple shape priors in segmentation, which is a novel contribution.

PrePrint: Two Dimensional Polar Harmonic Transforms for Invariant Image Representation

This paper introduces a set of 2D transforms, based on a set of orthogonal projection bases, to generate a set of features which are invariant to rotation. We call these transforms Polar Harmonic Transforms (PHTs). Unlike the well-known Zernike and pseudo Zernike moments, the kernel computation of PHTs is extremely simple and has no numerical stability issue whatsoever. This implies that PHTs encompass the orthogonality and invariance advantages of Zernike and pseudo Zernike moments, but is free from their inherent limitations. This also means that PHTs are well-suited for application where maximal discriminant information is needed. Furthermore, PHTs make available a large set of features for further feature selection in the process of seeking for the best discriminative or representative features for a particular application.

PrePrint: Intrinsic MANOVA for Riemannian Manifolds with an Application to Kendall's Space of Planar Shapes

We propose an intrinsic multi-factorial model for data on Riemannian manifolds as typically occur in the statistical analysis of shape. Due to the lack of a linear structure, linear models cannot be defined in general; to date only one-way MANOVA is available. For a general multi-factorial model, we assume that variation not explained by the model is concentrated near elements defining the effects. By determining the asymptotic distributions of respective sample covariances under parallel transport, we show that they can be compared by standard MANOVA. Often in applications, manifolds are only implicitly given as quotients where the bottom space parallel transport can be expressed through a differential equation. For Kendall's space of planar shapes, we provide an explicit solution. We illustrate our method by an intrinsic two-way MANOVA for a set of leaf shapes. While biologists can identify genotype effects by sight, we can detect height effects that are otherwise not identifiable.

PrePrint: Spatiotemporal Saliency in Dynamic Scenes

A spatiotemporal saliency algorithm, based on a center-surround framework, is proposed. The algorithm is inspired by biological mechanisms of motion-based perceptual grouping, and extends a discriminant formulation of center-surround saliency previously proposed for static imagery. Under this formulation, the saliency of a location is equated to the power of a pre-defined set of features to discriminate between the visual stimuli on a center and a surround window, centered at that location. The features are spatiotemporal video patches, and are modeled as dynamic textures, to achieve a principled joint characterization of the spatial and temporal components of saliency. The combination of discriminant center-surround saliency with the modeling power of dynamic textures yields a robust, versatile, and fully unsupervised spatiotemporal saliency algorithm, applicable to scenes with highly dynamic backgrounds and moving cameras. The related problem of background subtraction is treated as the complement of saliency detection, by classifying non-salient (with respect to appearance and motion dynamics) points in the visual field as background. The algorithm is tested for background subtraction on challenging sequences, and shown to substantially outperform various state of the art techniques. Quantitatively, its average error rate is almost half that of the closest competitor.

PrePrint: From Canonical Poses to 3—D Motion Capture Using a Single Camera

We combine detection and tracking techniques to achieve robust 3—D motion recovery of people seen from arbitrary viewpoints by a single and potentially moving camera. We rely on detecting key postures, which can be done reliably, using a motion model to infer 3—D poses between consecutive detections, and finally refining them over the whole sequence using a generative model. We demonstrate our approach in the cases of golf motions filmed using a static camera and walking motions acquired using a potentially moving one. We will show that our approach, although monocular, is both metrically accurate because it integrates information over many frames and robust because it can recover from a few misdetections.

PrePrint: Classification of Complex Information: Inference of Co-Occurring Affective States from Their Expressions in Speech

We present a classification algorithm for inferring affective states from their non-verbal expressions in speech. It is based on the observations that affective states can occur simultaneously and that different sets of vocal features distinguish between non-verbal expressions of different affective states. The input to the inference system was a large set of vocal features and metrics that were extracted from each utterance. The classification algorithm conducted independent pair-wise comparisons between nine affective-state groups. The sets of metrics and classification algorithm were selected independently for each pair of affective state groups. Average classification accuracy of the 36 pair-wise machines was 75%, using tenfold cross-validation. The comparison results were consolidated into a single ranked list of the nine affective-state groups. This list was the output of the system and represented the inferred combination of co-occurring affective states for the analysed utterance. The inference accuracy of the combined machine was 83%. The system automatically characterised over 500 affective state concepts from the Mind Reading database. The inference of co-occurring affective states was validated by comparing the inferred combinations to the lexical definitions of the labels of the analysed sentences. The distinguishing capabilities of the system were comparable to human performance.

PrePrint: A Coupled Duration-Focused Architecture for Realtime Music to Score Alignment

The capacity for realtime synchronization and coordination is a common ability among trained musicians performing a music score that presents an interesting challenge for machine intelligence. Compared to speech recognition, which has influenced many music information retrieval systems, music's temporal dynamics and complexity pose challenging problems to common approximations regarding time modeling of data streams. In this paper, we propose a design for a realtime music to score alignment system. Given a live recording of a musician playing a music score, the system is capable of following the musician in realtime within the score and decoding the tempo (or pace) of its performance. The proposed design features two coupled audio and tempo agents within a unique probabilistic inference framework that adaptively updates its parameters based on the realtime context. Online decoding is achieved through the collaboration of the coupled agents in a Hidden Hybrid Markov/semi-Markov framework where prediction feedback of one agent affects the behavior of the other. We perform evaluations for both realtime alignment and the proposed temporal model. An implementation of the presented system has been widely used in real concert situations worldwide and the readers are encouraged to access the actual system and experiment the results.

PrePrint: Self-Similarity and Points of Interest

In this work we present a new approach to interest point detection. Different types of features in images are detected by using a common computational concept. The proposed approach consider the total variability of local regions. New entities are introduced: circumferences and radii. The total sum of squares computed on the intensity values of a local region is divided into three components: between-circumferences sum of squares, between-radii sum of squares, and the remainder. These three components normalized by the total sum of squares represent three new saliency measures, namely radial, tangential, and residual. The saliency measures are computed for different radii in a local region and scale-spaces are build in this way. Local extrema in scale-space of each of the saliency measures represent features with complementary image properties: blob-like features, corner-like feature and highly textured points. Results obtained on a wide variety of image sets compare favourably with the results obtained by the leading interest point detectors from the literature. The proposed approach gives a rich set of highly distinctive local regions that can be used for object recognition and image matching.

PrePrint: Fast Algorithm for Walsh Hadamard Transform on Sliding Windows

This paper proposes a fast algorithm for Walsh Hadamard Transform on sliding windows which can be used to implement pattern matching most efficiently. The computational requirement of the proposed algorithm is about 4/3 additions per projection vector per sample which is the lowest among existing fast algorithms for Walsh Hadamard Transform on sliding windows.

PrePrint: Rank Classification of Linear Line Structures from Images by Trifocal Tensor Determinability

The problem we address is: given line correspondences over three views, what is the condition of the line correspondences for the spatial relation of the three associated camera positions to be uniquely recoverable? The observed set of lines in space are called critical if there are multiple projectively non-equivalent configurations of the camera positions that can picture the same image triplet of the lines. We tackle the problem from the perspective of trifocal tensor, a quantity that captures the relative pose of the cameras in relation to the captured views. We show that the rank of a matrix that leads to the estimation of the tensor is reduced to $7$, $11$, $15$ if the observed lines come from a line pencil, a line bundle, and a line field respectively, which are line families belonging to linear line space; and $12$, $19$, $23$ if the lines come from a general linear ruled surface, a general linear line congruence, and a general linear line complex, which are subclasses of linear line structures. These critical structures are quite typical in reality, and thus the findings are important to the validity and stability of practically all algorithms related to structure from motion and projective reconstruction using line correspondences.

PrePrint: Shape and Spatially-Varying BRDFs From Photometric Stereo

This paper describes a photometric stereo method designed for surfaces with spatially-varying BRDFs, including surfaces with both varying diffuse and specular properties. Our optimization-based method builds on the observation that most objects are composed of a small number of fundamental materials by constraining each pixel to be representable by a combination of at most two such materials. This approach recovers not only the shape but also material BRDFs and weight maps, yielding accurate rerenderings under novel lighting conditions for a wide variety of objects. We demonstrate examples of interactive editing operations made possible by our approach.

PrePrint: Kernel Entropy Component Analysis

We introduce kernel entropy component analysis (kernel ECA) as a new method for data transformation and dimensionality reduction. Kernel ECA reveals structure relating to the Renyi entropy of the input space data set, estimated via a kernel matrix using Parzen windowing. This is achieved by projections onto a subset of entropy preserving kernel principal component analysis (kernel PCA) axes. This subset needs not in general to correspond to the top eigenvalues of the kernel matrix, in contrast to dimensionality reduction using kernel PCA. We show that kernel ECA may produce strikingly different transformed data sets compared to kernel PCA, with a distinct angle-based structure. A new spectral clustering algorithm utilizing this structure is developed with positive results. Furthermore, kernel ECA is shown to be an useful alternative for pattern denoising.

PrePrint: Design and Evaluation of More Accurate Gradient Operators on Hexagonal Lattices

Digital two-dimensional images are usually sampled on square lattices, while the receptors of the human eye are following a hexagonal structure. It is the main motivation for adopting hexagonal lattices. The fundamental operation in many image processing algorithms is to extract the gradient information. As such, various gradient operators have been proposed for square lattices, and they have been thoroughly optimized. Accurate gradient operators for hexagonal lattices have, however, not been researched well enough, while the distance between neighbor pixels is constant. We therefore derive consistent gradient operators on hexagonal lattices, and we compare them with the existing optimized filters on square lattices. The results show that the derived filters on hexagonal lattices achieve a better signal-to-noise ratio than those on square lattices. Results on artificial images also show that the derived filters on hexagonal lattices outperform the square ones with respect to accuracy of gradient intensity and orientation detection.

PrePrint: Sparse Multiple Kernel Learning for Signal Processing Applications

In many signal processing applications, grouping of features during model development and the selection of a small number of relevant groups can be useful to improve the interpretability of the learned parameters. This work proposes the use of a log-based concave penalty term in the primal problem to induce sparsity in terms of groups of parameters. A generalized iterative learning algorithm is first given for model parameter estimation in the primal space. It is then shown that a natural extension of the method to non-linear models using the “kernel trick” results in a new algorithm called Sparse Multiple Kernel Learning (SMKL) which generalizes group-feature selection to kernel selection. SMKL is capable of exploiting existing efficient single kernel algorithms while providing a sparser solution in terms of the number of kernels used as compared to the existing multiple kernel learning framework. A number of signal processing examples based on the use of mass spectra for cancer detection, hyperspectral imagery for landcover classification and NIR spectra from wheat, fescue-grass and diesel are given to highlight the ability of SMKL to achieve a very high accuracy with a very few kernels.

PrePrint: Correction of Spatially Varying Image and Video Blur Using a Hybrid Camera

We present a novel approach to reduce spatially varying motion blur in video and images using a hybrid camera system. A hybrid camera is a standard video camera that is coupled with an auxiliary low-resolution camera sharing the same optical path but capturing at a significantly higher frame rate. The difference between the two video streams is that the auxiliary video is temporally sharper but at a lower resolution, while the lower-frame-rate video has higher spatial resolution but is susceptible to motion blur. Our deblurring approach uses the data from these two video streams to significantly reduce spatially varying motion blur in the high-resolution camera with a technique that combines both deconvolution and super-resolution. Our algorithm also incorporates a refinement of the spatially varying blur kernels to further improve results. We show that our approach is not only able to reduce motion blur from the high-resolution video, but can be used to estimate new high-resolution frames between temporal samples. Experimental results on a variety of inputs demonstrate notable improvement over current state-of-the-art methods in image/video deblurring.

PrePrint: Nonstationary Shape Activities: Dynamic Models for Landmark Shape Change and Applications

The goal of this work is to develop statistical models for the shape change of a configuration of “landmark” points (key points of interest) over time and to use these models for filtering, tracking, synthesis and change detection. The term “shape activity” was introduced in recent work to denote a particular stochastic model for the dynamics of landmark shapes (dynamics after global translation, scale and rotation effects are normalized for). In that work, only models for stationary shape sequences were proposed. But most “activities” of a set of landmarks, e.g. running, jumping or crawling have large shape changes w.r.t initial shape and hence nonstationary. The key contribution of this work is a novel approach to define a generative model for both 2D and 3D nonstationary landmark shape sequences. We demonstrate the use of our nonstationary model for (a) sequentially filtering noise-corrupted landmark configurations; (b) for tracking, i.e. for using the filtering to predict the locations of the landmarks at the current time and using this prediction for faster and more accurate landmarks’ extraction from the current image; (c) for synthesis and (d) for change detection. Greatly improved performance over existing work is demonstrated for human activity videos.

PrePrint: Automatic Construction of Correspondences for Tubular Surfaces

Statistical shape modeling is an established technique and is used for a variety of tasks in medical image processing, such as image segmentation and analysis. A challenging task in the construction of a shape model is establishing a good correspondence across the set of training shapes. Especially for shapes of cylindrical topology, very little work has been done. This paper describes an automatic method to obtain a correspondence for a set of cylindrical shapes. The method starts from an initial correspondence which is provided by cylindrical parameterization. The quality, measured in terms of the description length, of the obtained correspondence is then improved by deforming the parameterizations using cylindrical b-spline deformations and by optimization of the spatial alignment of the shapes. In order to allow efficient gradient guided optimization, an analytic expression is provided for the gradient of this quality measure with respect to the parameters of the parameterization deformation and the spatial alignment. A comparison is made between models obtained from the correspondences before and after the optimization. The results show that, in comparison with parameterization based correspondences, this new method establishes correspondences that generate models with significantly increased performance in terms of reconstruction error, generalization ability, specificity, and compactness.