A Variational Framework for Structure from Motion in Omnidirectional Image Sequences

We address the problem of depth and ego-motion estimation from omnidirectional images. We propose a correspondence-free structure-from-motion problem for sequences of images mapped on the 2-sphere. A novel graph-based variational framework is first proposed for depth estimation between pairs of images. The estimation is cast as a TV-L1 optimization problem that is solved by a fast graph-based algorithm. The ego-motion is then estimated directly from the depth information without explicit computation of the optical flow. Both problems are finally addressed together in an iterative algorithm that alternates between depth and ego-motion estimation for fast computation of 3D information from motion in image sequences. Experimental results demonstrate the effective performance of the proposed algorithm for 3D reconstruction from synthetic and natural omnidirectional images.     

An Almost Quadratic Time Algorithm for Sparse Spliced Alignment

The sparse spliced alignment problem consists of finding a chain of zero or more exons from O(n) prescribed candidate exons of a DNA sequence of length O(n) that is most similar to a known related gene sequence of length n. This study improves the running time of the fastest known algorithm for this problem to date, which executes in O(n ^2.25) time, or very recently, in O(n ²log ² n) time, by proposing an O(n ²log n)-time algorithm.     

A Distributed CFAR Detector Based on Local Test Statistics

In order to improve detection performance of a distributed system, a new CFAR （Constant False Alarm Rate） detector is proposed based on local test statistics. In the scheme, each sensor transmits its test sample and a designated order statistic （OS） of its reference samples to the fusion center. At the fusion center, the global test statistic in the test cells is formed by the cell averaging algorithm （CA）, and the global test statistic in the reference cells is also formed by the CA. Comparing the ratio of the global test statistic of test samples and that of reference samples with a scaling factor, which is determined by probability of false alarm, to make the final decision. For a Rayleigh fluctuating target in Gaussian clutter of unknown level, its closed-form expressions for the false alarm probability and the detection probability are obtained in both homogeneous and nonhomogeneous background. The numerical analysis results show that the CFAR detector proposed in this paper has good detection performance.     

A Memory and Computation Efficient Sparse Level-Set Method

Since its introduction, the level set method has become the favorite technique for capturing and tracking moving interfaces, and found applications in a wide variety of scientific fields. In this paper we present efficient data structures and algorithms for tracking dynamic interfaces through the level set method. Several approaches which address both computational and memory requirements have been very recently introduced. We show that our method is up to 8.5 times faster than these recent approaches. More importantly, our algorithm can greatly benefit from both fine- and coarse-grain parallelization by leveraging SIMD and/or multi-core parallel architectures.     

A General Approach for Dexterous Manipulation Planning Based on Configuration Space Structuring

In this paper, we propose a new method for the dexterous manipulation planning problem, under quasi-static movement assumption. This method computes both object and finger trajectories as well as finger relocation sequence and applies to every object shape and hand geometry. It relies on the exploration of the particular subspaces GS k that are the subspaces of all the grasps that can be achieved for a given set of k grasping fingers. The originality is to use continuous paths in these subspaces to directly link two configurations. The proposed approach captures the GS k connectivity in a graph structure. The answer of the manipulation planning query is then given by searching a path in the computed graph. Another specificity of our technique is that it considers manipulated object and hand as an only system, unlike most existing methods that first compute object trajectory then fingers trajectories and thus can not find a solution in all situations. Simulation experiments were conducted for different dexterous manipulation task examples to validate the proposed method.     

LDG2: A Variant of the LDG Flux Formulation for the Spectral Volume Method

The local discontinuous Galerkin (LDG) viscous flux formulation was originally developed by Cockburn and Shu for the discontinuous Galerkin setting and later extended to the spectral volume setting by Wang and his collaborators. Unlike the penalty formulations like the interior penalty and the BR2 schemes, the LDG formulation requires no length based penalizing terms and is compact. However, computational results using LDG are dependant of the orientation of the faces especially for unstructured and non uniform grids. This results in lower solution accuracy and stiffer stability constraints as shown by Kannan and Wang. In this paper, we develop a variant of the LDG, which not only retains its attractive features, but also vastly reduces its unsymmetrical nature. This variant (aptly named LDG2), displayed higher accuracy than the LDG approach and has a milder stability constraint than the original LDG formulation. In general, the 1D and the 2D numerical results are very promising and indicate that the approach has a great potential for 3D flow problems.     

Infinite Photography: New Mathematical Model for High-Resolution Images

A new mathematical image model is introduced using the photographic process as the starting point. Images are represented as infinite sequences of photons allowing analysis at arbitrarily high resolution and leading to novel computational methods for processing, representation, transmission and storage of images. The resulting space of infinite photographs is proved to have a metric structure and to be intimately connected with bounded Borel measures. Theorems are proved indicating that the imaging power of the photographic process exceeds function spaces in the high resolution limit; this implies in particular that natural photographic images need to be modelled by generalized functions. Furthermore, computational results are presented to illustrate the novel algorithms based on photon sequences. The algorithms include stochastic halftoning, representation of cartoon images with outlines, anti-aliasing, blurring and singularity extraction.     

Scale Selection for Compact Scale-Space Representation of Vector-Valued Images

This paper investigates the scale selection problem for nonlinear diffusion scale-spaces. This topic comprises the notions of localization scale selection and scale space discretization. For the former, we present a new approach. It aims at maximizing the image content’s presence by finding the scale that has a maximum correlation with the noise-free image. For the latter, we propose to adapt the optimal diffusion stopping time criterion of Mrázek and Navara in such a way that it may identify multiple scales of importance.     

A New Family of Mixed Methods for the Reissner-Mindlin Plate Model Based on a System of First-Order Equations

The mixed method for the biharmonic problem introduced in (Behrens and Guzmán, SIAM J. Numer. Anal., 2010) is extended to the Reissner-Mindlin plate model. The Reissner-Mindlin problem is written as a system of first order equations and all the resulting variables are approximated. However, the hybrid form of the method allows one to eliminate all the variables and have a final system only involving the Lagrange multipliers that approximate the transverse displacement and rotation at the edges of the triangulation. Mixed finite element spaces for elasticity with weakly imposed symmetry are used to approximate the bending moment matrix. Optimal estimates independent of the plate thickness are proved for the transverse displacement, rotations and bending moments. A post-processing technique is provided for the displacement and rotations variables and we show numerically that they converge faster than the original approximations.     

Topological and Variational Properties of a Model for the Reconstruction of Three-Dimensional Transparent Images with Self-Occlusions

We introduce and study a two-dimensional variational model for the reconstruction of a smooth generic solid shape E, which may handle the self-occlusions and that can be considered as an improvement of the 2.1D sketch of Nitzberg and Mumford (Proceedings of the Third International Conference on Computer Vision, Osaka, 1990). We characterize from the topological viewpoint the apparent contour of E, namely, we characterize those planar graphs that are apparent contours of some shape E. This is the classical problem of recovering a three-dimensional layered shape from its apparent contour, which is of interest in theoretical computer vision. We make use of the so-called Huffman labeling (Machine Intelligence, vol. 6, Am. Elsevier, New York, 1971), see also the papers of Williams (Ph.D. Dissertation, 1994 and Int. J. Comput. Vis. 23:93–108, 1997) and the paper of Karpenko and Hughes (Preprint, 2006) for related results. Moreover, we show that if E and F are two shapes having the same apparent contour, then E and F differ by a global homeomorphism which is strictly increasing on each fiber along the direction of the eye of the observer. These two topological theorems allow to find the domain of the functional ℱ describing the model. Compactness, semicontinuity and relaxation properties of ℱ are then studied, as well as connections of our model with the problem of completion of hidden contours.

On Nonmonotone Chambolle Gradient Projection Algorithms for Total Variation Image Restoration

The main aim of this paper is to accelerate the Chambolle gradient projection method for total variation image restoration. In the proposed minimization method model, we use the well known Barzilai-Borwein stepsize instead of the constant time stepsize in Chambolle’s method. Further, we adopt the adaptive nonmonotone line search scheme proposed by Dai and Fletcher to guarantee the global convergence of the proposed method. Numerical results illustrate the efficiency of this method and indicate that such a nonmonotone method is more suitable to solve some large-scale inverse problems.

Characteristic Line Based Schemes for Solving a Quasilinear Hierarchical Size-Structured Model

New schemes, based on the characteristics line method, for solving a hierarchical size-structured model with nonlinear growth, mortality and reproduction rate are developed. The idea of the schemes is not to follow the characteristics from the initial condition, but for each time-step to find the origins of the grid nodes at the previous time level. Numerical tests, including comparison with exact solutions for the new schemes, are elaborated. Numerical results that confirm the theoretical order of convergence of the new schemes are presented.     

A hybrid Kaczmarz–Conjugate Gradient algorithm for image reconstruction

The present paper is a theoretical contribution to the field of iterative methods for solving inconsistent linear least squares problems arising in image reconstruction from projections in computerized tomography. It consists on a hybrid algorithm which includes in each iteration a CG-like step for modifying the right-hand side and a Kaczmarz-like step for producing the approximate solution. We prove convergence of the hybrid algorithm for general inconsistent and rank-deficient least-squares problems. Although the new algorithm has potential for more applied experiments and comparisons, we restrict them in this paper to a regularized image reconstruction problem involving a 2D medical data set.     

A Variational Model to Remove the Multiplicative Noise in Ultrasound Images

In this paper we study a variational model to deal with the speckle noise in ultrasound images. We prove the existence and uniqueness of the minimizer for the variational problem, and derive the existence and uniqueness of weak solutions for the associated evolution equation. Furthermore, we show that the solution of the evolution equation converges weakly in BV and strongly in L ² to the minimizer as t→∞. Finally, some numerical results illustrate the effectiveness of the proposed model for multiplicative noise removal.     

Predicate Logic Based Image Grammars for Complex Pattern Recognition

Predicate logic based reasoning approaches provide a means of formally specifying domain knowledge and manipulating symbolic information to explicitly reason about different concepts of interest. Extension of traditional binary predicate logics with the bilattice formalism permits the handling of uncertainty in reasoning, thereby facilitating their application to computer vision problems. In this paper, we propose using first order predicate logics, extended with a bilattice based uncertainty handling formalism, as a means of formally encoding pattern grammars, to parse a set of image features, and detect the presence of different patterns of interest. Detections from low level feature detectors are treated as logical facts and, in conjunction with logical rules, used to drive the reasoning. Positive and negative information from different sources, as well as uncertainties from detections, are integrated within the bilattice framework. We show that this approach can also generate proofs or justifications (in the form of parse trees) for each hypothesis it proposes thus permitting direct analysis of the final solution in linguistic form. Automated logical rule weight learning is an important aspect of the application of such systems in the computer vision domain. We propose a rule weight optimization method which casts the instantiated inference tree as a knowledge-based neural network, interprets rule uncertainties as link weights in the network, and applies a constrained, back-propagation algorithm to converge upon a set of rule weights that give optimal performance within the bilattice framework. Finally, we evaluate the proposed predicate logic based pattern grammar formulation via application to the problems of (a) detecting the presence of humans under partial occlusions and (b) detecting large complex man made structures as viewed in satellite imagery. We also evaluate the optimization approach on real as well as simulated data and show favorable results.     

A Dual-Petrov-Galerkin Method for the Kawahara-Type Equations

An efficient and accurate numerical scheme is proposed, analyzed and implemented for the Kawahara and modified Kawahara equations which model many physical phenomena such as gravity-capillary waves and magneto-sound propagation in plasmas. The scheme consists of dual-Petrov-Galerkin method in space and Crank-Nicholson-leap-frog in time such that at each time step only a sparse banded linear system needs to be solved. Theoretical analysis and numerical results are presented to show that the proposed numerical is extremely accurate and efficient for Kawahara type equations and other fifth-order nonlinear equations. This work is partially supported by the National Science Council of the Republic of China under the grant NSC 94-2115-M-126-004 and 95-2115-M-126-003. This work is partially supported by NSF grant DMS-0610646.     

Lattice Boltzmann Model Based on the Rebuilding-Divergency Method for the Laplace Equation and the Poisson Equation

In this paper, a new lattice Boltzmann model based on the rebuilding-divergency method for the Poisson equation is proposed. In order to translate the Poisson equation into a conservation law equation, the source term and diffusion term are changed into divergence forms. By using the Chapman-Enskog expansion and the multi-scale time expansion, a series of partial differential equations in different time scales and several higher-order moments of equilibrium distribution functions are obtained. Thus, by rebuilding the divergence of the source and diffusion terms, the Laplace equation and the Poisson equation with the second accuracy of the truncation errors are recovered. In the numerical examples, we compare the numerical results of this scheme with those obtained by other classical method for the Green-Taylor vortex flow, numerical results agree well with the classical ones.     

A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration

In this paper, we propose a unified primal-dual algorithm framework for two classes of problems that arise from various signal and image processing applications. We also show the connections to existing methods, in particular Bregman iteration (Osher et al., Multiscale Model. Simul. 4(2):460–489, 2005) based methods, such as linearized Bregman (Osher et al., Commun. Math. Sci. 8(1):93–111, 2010; Cai et al., SIAM J. Imag. Sci. 2(1):226–252, 2009, CAM Report 09-28, UCLA, March 2009; Yin, CAAM Report, Rice University, 2009) and split Bregman (Goldstein and Osher, SIAM J. Imag. Sci., 2, 2009). The convergence of the general algorithm framework is proved under mild assumptions. The applications to ℓ ¹ basis pursuit, TV−L ² minimization and matrix completion are demonstrated. Finally, the numerical examples show the algorithms proposed are easy to implement, efficient, stable and flexible enough to cover a wide variety of applications.     

Adaptive Variational Method for Restoring Color Images with High Density Impulse Noise

In this paper, a new variational framework of restoring color images with impulse noise is presented. The novelty of this work is the introduction of an adaptively weighting data-fidelity term in the cost functional. The fidelity term is derived from statistical methods and contains two weighting functions as well as some statistical control parameters of noise. This method is based on the fact that impulse noise can be approximated as an additive noise with probability density function (PDF) being the finite mixture model. A Bayesian framework is then formulated in which likelihood functions are given by the mixture model. Inspired by the expectation-maximization (EM) algorithm, we present two models with variational framework in this study. The superiority of the proposed models is that: the weighting functions can effectively detect the noise in the image; with the noise information, the proposed algorithm can automatically balance the regularity of the restored image and the fidelity term by updating the weighting functions and the control parameters. These two steps ensure that one can obtain a good restoration even though the degraded color image is contaminated by impulse noise with large ration (90% or more). In addition, the numerical implementation of this algorithm is very fast by using a split algorithm. Some numerical experimental results and comparisons with other methods are provided to show the significant effectiveness of our approach.     

A Universal Online Caching Algorithm Based on Pattern Matching

We present a universal algorithm for the classical online problem of caching or demand paging. We consider the caching problem when the page request sequence is drawn from an unknown probability distribution and the goal is to devise an efficient algorithm whose performance is close to the optimal online algorithm which has full knowledge of the underlying distribution. Most previous works have devised such algorithms for specific classes of distributions with the assumption that the algorithm has full knowledge of the source. In this paper, we present a universal and simple algorithm based on pattern matching for mixing sources (includes Markov sources). The expected performance of our algorithm is within 4+o(1) times the optimal online algorithm (which has full knowledge of the input model and can use unbounded resources).