Conformal prediction is a distribution-free framework for uncertainty quantification that replaces point predictions with sets, offering marginal coverage guarantees (i.e., ensuring that the sets contain the true label with a specified probability, in expectation). In this paper, we uncover a novel connection between conformal prediction and sparse "softmax-like" transformations, such as sparsemax and $\gamma$-entmax (with $\gamma> 1$), which assign nonzero probability only to some labels. We introduce new non-conformity scores for classification that make the calibration process correspond to the widely used temperature scaling method. At test time, applying these sparse transformations with the calibrated temperature leads to a support set (i.e., the set of labels with nonzero probability) that automatically inherits the coverage guarantees of conformal prediction. Through experiments on computer vision and text classification benchmarks, we demonstrate that the proposed method achieves competitive results in terms of coverage, efficiency, and adaptiveness compared to standard non-conformity scores based on softmax.

In machine learning (ML) and data mining (DM) one often has to resort to data pre-processing techniques to achieve adequate data representations. Among these techniques, we find feature discretization (FD) and feature selection (FS), with many available methods for each one. The use of FD and FS techniques improves the data representation for ML and DM tasks. However, these techniques are usually applied in an independent way, that is, we may use a FD technique but not a FS technique or the opposite case. Using both FD and FS techniques in sequence, may not produce the most adequate results. In this paper, we propose a supervised discretization-selection technique; the discretization step is done in an incremental approach and keeps information regarding the features and the number of bits allocated per feature. Then, we apply a selection criterion based upon the discretization bins, yielding a discretized and dimensionality reduced dataset. We evaluate our technique on different typ es of data and in most cases the discretized and reduced version of the data is the most suited version, achieving better classification performance, as compared to the use of the original features.

Experimental assessment of different missing data imputation methods often compute error rates between the original values and the estimated ones. This experimental setup relies on complete datasets that are injected with missing values. The injection process is straightforward for the Missing Completely At Random and Missing At Random mechanisms; however, the Missing Not At Random mechanism poses a major challenge, since the available artificial generation strategies are limited. Furthermore, the studies focused on this latter mechanism tend to disregard a comprehensive baseline of state-of-the-art imputation methods. In this work, both challenges are addressed: four new Missing Not At Random generation strategies are introduced and a benchmark study is conducted to compare six imputation methods in an experimental setup that covers 10 datasets and five missingness levels (10% to 80%). The overall findings are that, for most missing rates and datasets, the best imputation method to deal with Missing Not At Random values is the Multiple Imputation by Chained Equations, whereas for higher missingness rates autoencoders show promising results.

Abstract The rapid proliferation of large language models and natural language processing (NLP) applications creates a crucial need for uncertainty quantification to mitigate risks such as Hallucinations and to enhance decision-making reliability in critical applications. Conformal prediction is emerging as a theoretically sound and practically useful framework, combining flexibility with strong statistical guarantees. Its model-agnostic and distribution-free nature makes it particularly promising to address the current shortcomings of NLP systems that stem from the absence of uncertainty quantification. This paper provides a comprehensive survey of conformal prediction techniques, their guarantees, and existing applications in NLP, pointing to directions for future research and open challenges.

Exponential families are widely used in machine learning, including many distributions in continuous and discrete domains (e.g., Gaussian, Dirichlet, Poisson, and categorical distributions via the softmax transformation). Distributions in each of these families have fixed support. In contrast, for finite domains, recent work on sparse alternatives to softmax (e.g., sparsemax, $\alpha$-entmax, and fusedmax), has led to distributions with varying support. This paper develops sparse alternatives to continuous distributions, based on several technical contributions: First, we define $\Omega$-regularized prediction maps and Fenchel-Young losses for arbitrary domains (possibly countably infinite or continuous). For linearly parametrized families, we show that minimization of Fenchel-Young losses is equivalent to moment matching of the statistics, generalizing a fundamental property of exponential families. When $\Omega$ is a Tsallis negentropy with parameter $\alpha$, we obtain “deformed exponential families,” which include $\alpha$-entmax and sparsemax ($\alpha=2$) as particular cases. For quadratic energy functions, the resulting densities are $\beta$-Gaussians, an instance of elliptical distributions that contain as particular cases the Gaussian, biweight, triweight, and Epanechnikov densities, and for which we derive closed-form expressions for the variance, Tsallis entropy, and Fenchel-Young loss. When $\Omega$ is a total variation or Sobolev regularizer, we obtain a continuous version of the fusedmax. Finally, we introduce continuous-domain attention mechanisms, deriving efficient gradient backpropagation algorithms for $\alpha \in \{1,\frac{4}{3}, \frac{3}{2}, 2\}$. Using these algorithms, we demonstrate our sparse continuous distributions for attention-based audio classification and visual question answering, showing that they allow attending to time intervals and compact regions.

José Manuel Bioucas-Dias was an outstanding expert in many different IEEE-related areas, including inverse problems in imaging, signal and image processing, pattern recognition, optimization, and remote sensing. He authored or coauthored more than 250 publications, including more than 100 journal papers (66 of which published in IEEE journals) and over 200 peer-reviewed international conference papers and book chapters. His contributions have been extremely influential in many different fields, namely phase estimation and unwrapping, convex optimization and Bayesian inference for imaging inverse problems, with a special emphasis on remote sensing, including synthetic aperture radar (SAR), hyperspectral unmixing, fusion, super-resolution, classification, and segmentation. In this paper, we provide an overview of his outstanding contributions to remote sensing image processing.

Although recurrent neural networks (RNNs) are state-of-the-art in numerous sequential decision-making tasks, there has been little research on explaining their predictions. In this work, we present TimeSHAP, a model-agnostic recurrent explainer that builds upon KernelSHAP and extends it to the sequential domain. TimeSHAP computes feature-, timestep-, and cell-level attributions. As sequences may be arbitrarily long, we further propose a pruning method that is shown to dramatically decrease both its computational cost and the variance of its attributions. We use TimeSHAP to explain the predictions of a real-world bank account takeover fraud detection RNN model, and draw key insights from its explanations: i) the model identifies important features and events aligned with what fraud analysts consider cues for account takeover; ii) positive predicted sequences can be pruned to only 10% of the original length, as older events have residual attribution values; iii) the most recent input event of positive predictions only contributes on average to 41% of the model's score; iv) notably high attribution to client's age, upheld on higher false positive rates for older clients.

This article proposes a denoiser for hyperspectral (HS) images that consider, not only spatial features, but also spectral features. The method starts by projecting the noisy (observed) HS data onto a lower dimensional subspace and then learns a Gaussian mixture model (GMM) from 3-D patches or blocks extracted from the projected data cube. Afterward, the minimum mean squared error (MMSE) estimates of the blocks are obtained in closed form and returned to their original positions. Experiments show that the proposed algorithm is able to outperform other state-of-the-art methods under Gaussian and Poissonian noise and to reconstruct high-quality images in the presence of stripes.

This paper introduces a novel algorithm for the fusion of magnetic resonance and ultrasound images, based on a patch-wise polynomial model relating the gray levels of the two imaging systems (called modalities). Starting from observation models adapted to each modality and exploiting a patch-wise polynomial model, the fusion problem is expressed as the minimization of a cost function including two data fidelity terms and two regularizations. This minimization is performed using a PALM-based algorithm, given its ability to handle nonlinear and possibly non-convex functions. The efficiency of the proposed method is evaluated on phantom data. The resulting fused image is shown to contain complementary information from both magnetic resonance (MR) and ultrasound (US) images, i.e., with a good contrast (as for the MR image) and a good spatial resolution (as for the US image).

Exponential families are widely used in machine learning; they include many distributions in continuous and discrete domains (e.g., Gaussian, Dirichlet, Poisson, and categorical distributions via the softmax transformation). Distributions in each of these families have fixed support. In contrast, for finite domains, there has been recent work on sparse alternatives to softmax (e.g., sparsemax and alpha-entmax), which have varying support, being able to assign zero probability to irrelevant categories. These discrete sparse mappings have been used for improving interpretability of neural attention mechanisms. This paper expands that work in two directions: first, we extend alpha-entmax to continuous domains, revealing a link with Tsallis statistics and deformed exponential families. Second, we introduce continuous-domain attention mechanisms, deriving efficient gradient backpropagation algorithms for alpha in {1,2}. Experiments on attention-based text classification, machine translation, and visual question answering illustrate the use of continuous attention in 1D and 2D, showing that it allows attending to time intervals and compact regions.

Early detection of lung cancer has shown to significantly improve patient survival. Apart from lesion detection, tumour segmentation is critical for developing radiomics signatures. In this work, we propose a novel hybrid approach for lung lesion detection and segmentation on CT scans, where the segmentation task is assisted by prior detection of regions containing lesions. For the detection task, we introduce a 2.5D residual deep CNN working in a sliding-window fashion, whereas segmentation is tackled by a modified residual U-Net with a weighted-dice plus cross-entropy loss. Experimental results on the LIDC-IDRI dataset and on the lung tumour task dataset within the Medical Segmentation Decathlon show competitive detection performance of the proposed approach (0.902 recall) and superior segmentation capabilities (0.709 dice score). These results confirm the high potential of simpler models, with lower hardware requirements, thus of more general applicability.

Complex surveillance scenarios comprise different types of agents (e.g., bikers, cars, and pedestrians) that must be efficiently characterized in order to facilitate tasks such as tracking or abnormality detection. This paper proposes an unsupervised hierarchical multiple motion fields model to represent different types of agents, which relies in the combination of hierarchical Markov model and velocity fields. Model parameters are estimated using the expectation-maximization algorithm. The proposed framework was applied to synthetic and real datasets (Stanford Drone Dataset), showing the ability to characterize and classify different agents in an unsupervised way.

Most of the existing single-image blind deblurring methods are tailored for natural images. However, in many important applications (e.g., document analysis, forensics), the image being recovered belongs to a specific class (e.g., text, faces, fingerprints) or contains two or more classes. To deal with these images, we propose a class-adapted blind deblurring framework, based on the plug-and-play scheme, which allows forward models of imaging systems to be combined with state-of-the-art denoisers. We consider three patch-based denoisers, two suitable for images that belong to a specific class and a general purpose one. Additionally, for images with two or more classes, we propose two approaches: a direct one, and one that uses a patch classification step before denoising. The proposed deblurring framework includes two priors on the blurring filter: a sparsity-inducing prior, suitable for motion blur and a weak prior, for a variety of filters. The results show the state-of-the-art performance of the proposed framework when applied to images that belong to a specific class (text, face, fingerprints), or contain two classes (text and face). For images with two classes, we show that the deblurring performance is improved by using the classification step. For these images, we choose to test one instance of the proposed framework suitable for text and faces, which is a natural test ground for the proposed framework. With the proper (dictionary and/or classifier) learning procedure, the framework can be adapted to other problems. For text images, we show that, in most cases, the proposed deblurring framework improves OCR accuracy.

Linear hyperspectral unmixing (HU) aims at factoring the observation matrix into an endmember matrix and an abundance matrix. Linear HU via variational minimum volume (MV) regularization has recently received considerable attention in the remote sensing and machine learning areas, mainly owing to its robustness against the absence of pure pixels. We put some popular linear HU formulations under a unifying framework, which involves a data-fitting term and an MV-based regularization term, and collectively solve it via a nonconvex optimization. As the former and the latter terms tend, respectively, to expand (reducing the data-fitting errors) and to shrink the simplex enclosing the measured spectra, it is critical to strike a balance between those two terms. To the best of our knowledge, the existing methods find such balance by tuning a regularization parameter manually, which has little value in unsupervised scenarios. In this paper, we aim at selecting the regularization parameter automatically by exploiting the fact that a too large parameter overshrinks the volume of the simplex defined by the endmembers, making many data points be left outside of the simplex and hence inducing a large data-fitting error, while a sufficiently small parameter yields a large simplex making data-fitting error very small. Roughly speaking, the transition point happens when the simplex still encloses the data cloud but there are data points on all its facets. These observations are systematically formulated to find the transition point that, in turn, yields a good parameter. The competitiveness of the proposed selection criterion is illustrated with simulated and real data.

We propose a new approach to image fusion, inspired by the recent plug-and-play (PnP) framework. In PnP, a denoiser is treated as a black-box and plugged into an iterative algorithm, taking the place of the proximity operator of some convex regularizer, which is formally equivalent to a denoising operation. This approach offers flexibility and excellent performance, but convergence may be hard to analyze, as most state-of-the-art denoisers lack an explicit underlying objective function. Here, we propose using a scene-adapted denoiser (i.e., targeted to the specific scene being imaged) plugged into the iterations of the alternating direction method of multipliers (ADMM). This approach, which is a natural choice for image fusion problems, not only yields state-of-the-art results, but it also allows proving convergence of the resulting algorithm. The proposed method is tested on two different problems: hyperspectral fusion/sharpening and fusion of blurred-noisy image pairs.

This letter investigates the problem of sparse signal recovery in the presence of additive impulsive noise. The heavytailed impulsive noise is well modeled with stable distributions. Since there is no explicit formula for the probability density function of SαS distribution, alternative approximations are used, such as, generalized Gaussian distribution, which imposes ℓp-norm fidelity on the residual error. In this letter, we exploit a continuous mixed norm (CMN) for robust sparse recovery instead of ℓp-norm. We show that in blind conditions, i.e., in the case where the parameters of the noise distribution are unknown, incorporating CMN can lead to near-optimal recovery. We apply alternating direction method of multipliers for solving the problem induced by utilizing CMN for robust sparse recovery. In this approach, CMN is replaced with a surrogate function and the majorization-minimization technique is incorporated to solve the problem. Simulation results confirm the efficiency of the proposed method compared to some recent algorithms for robust sparse recovery in impulsive noise.

The alternating direction method of multipliers (ADMM) is a versatile tool for solving a wide range of constrained optimization problems. However, its performance is highly sensitive to a penalty parameter, making ADMM often unreliable and hard to automate for a non-expert user. We tackle this weakness of ADMM by proposing a method that adaptively tunes the penalty parameter to achieve fast convergence. The resulting adaptive ADMM (AADMM) algorithm, inspired by the successful Barzilai-Borwein spectral method for gradient descent, yields fast convergence and relative insensitivity to the initial stepsize and problem scaling.

Many modern computer vision and machine learning applications rely on solving difficult optimization problems that involve non-differentiable objective functions and constraints. The alternating direction method of multipliers (ADMM) is a widely used approach to solve such problems. Relaxed ADMM is a generalization of ADMM that often achieves better performance, but its efficiency depends strongly on algorithm parameters that must be chosen by an expert user. We propose an adaptive method that automatically tunes the key algorithm parameters to achieve optimal performance without user oversight. Inspired by recent work on adaptivity, the proposed adaptive relaxed ADMM (ARADMM) is derived by assuming a Barzilai-Borwein style linear gradient. A detailed convergence analysis of ARADMM is provided, and numerical results on several applications demonstrate fast practical convergence.

In global models/priors (for example, using wavelet frames), there is a well known analysis vs synthesis dichotomy in the way signal/image priors are formulated. In patch-based image models/priors, this dichotomy is also present in the choice of how each patch is modeled. This paper shows that there is another analysis vs synthesis dichotomy, in terms of how the whole image is related to the patches, and that all existing patch-based formulations that provide a global image prior belong to the analysis category. We then propose a synthesis formulation, where the image is explicitly modeled as being synthesized by additively combining a collection of independent patches. We formally establish that these analysis and synthesis formulations are not equivalent in general and that both formulations are compatible with analysis and synthesis formulations at the patch level. Finally, we present an instance of the alternating direction method of multipliers (ADMM) that can be used to perform image denoising under the proposed synthesis formulation, showing its computational feasibility. Rather than showing the superiority of the synthesis or analysis formulations, the contributions of this paper is to establish the existence of both alternatives, thus closing the corresponding gap in the field of patch-based image processing.

Deblurring of document images is an important problem, with several relevant applications, such as camera-based document acquisition and processing systems. Consequently, considerable attention has been given to this problem, namely in the blind image deblurring (BID) scenario, where the blurring filter is (partially or fully) unknown. Traditional BID methods can be used for document images, but this is far from optimal, since those methods are tailored to natural images, that is, they rely on statistical properties of natural images. This has lead to the proposal of a few special-purpose techniques, namely by exploiting properties of text images. In fact, in document images, the most prevalent type of content is text, but in some cases, it is not the only one, with the other types being very different from text. For example, identity documents typically contain faces and/or fingerprints, which are not adequately treated by methods designed for images of text. In this work, we propose a new method for BID of documents, supported on a class-adapted dictionary-based prior (learned from one or more sets of clean images of specific classes) for the image and a sparsity-inducing prior on the (unknown) blurring filter. This approach handles document images that contain two or more image classes (e.g., text and faces) which is a main contribution of our work. Experiments with document images containing both text and faces show the competitiveness of the proposed method in terms of restoration quality. Additionally, our experiments show that the proposed method is able to handle images with strong noise, outperforming state-of-the-art methods designed for BID of text images.

Blind image deblurring (BID) is an ill-posed inverse problem, usually addressed by imposing prior knowledge on the (unknown) image and on the blurring filter. Most of the work on BID has focused on natural images, using image priors based on statistical properties of generic natural images. However, in many applications, it is known that the image being recovered belongs to some specific class (e.g., text, face, fingerprints), and exploiting this knowledge allows obtaining more accurate priors. In this work, we propose a method where a Gaussian mixture model (GMM) is used to learn a class-adapted prior, by training on a dataset of clean images of that class. Experiments show the competitiveness of the proposed method in terms of restoration quality when dealing with images containing text, faces, or fingerprints. Additionally, experiments show that the proposed method is able to handle text images at high noise levels, outperforming state-of-the-art methods specifically designed for BID of text images.

In this paper, we propose a new image denoising method, tailored to specific classes of images, assuming that a dataset of clean images of the same class is available. Similarly to the non-local means (NLM) algorithm, the proposed method computes a weighted average of non-local patches, which we interpret under the importance sampling framework. This viewpoint introduces flexibility regarding the adopted priors, the noise statistics, and the computation of Bayesian estimates. The importance sampling viewpoint is exploited to approximate the minimum mean squared error (MMSE) patch estimates, using the true underlying prior on image patches. The estimates thus obtained converge to the true MMSE estimates, as the number of samples approaches infinity. Experimental results provide evidence that the proposed denoiser outperforms the state-of-the-art in the specific classes of face and text images.

In this paper, we address the problem of recovering images degraded by Poisson noise, where the image is known to belong to a specific class. In the proposed method, a dataset of clean patches from images of the class of interest is clustered using multivariate Gaussian distributions. In order to recover the noisy image, each noisy patch is assigned to one of these distributions, and the corresponding minimum mean squared error (MMSE) estimate is obtained. We propose to use a self-normalized importance sampling approach, which is a method of the Monte-Carlo family, for the both determining the most likely distribution and approximating the MMSE estimate of the clean patch. Experimental results shows that our proposed method outperforms other methods for Poisson denoising at a low SNR regime.

The alternating direction method of multipliers (ADMM) is commonly used for distributed model fitting problems, but its performance and reliability depend strongly on user-defined penalty parameters. We study distributed ADMM methods that boost performance by using different fine-tuned algorithm parameters on each worker node. We present a O(1/k) convergence rate for adaptive ADMM methods with node-specific parameters, and propose adaptive consensus ADMM (ACADMM), which automatically tunes parameters without user oversight.

This paper studies the ordered weighted L1 (OWL) family of regularizers for sparse linear regression with strongly correlated covariates. We prove sufficient conditions for clustering correlated covariates, extending and qualitatively strengthening previous results for a particular member of the OWL family: OSCAR (octagonal shrinkage and clustering algorithm for regression). We derive error bounds for OWL with correlated Gaussian covariates: for cases in which clusters of covariates are strongly (even perfectly) correlated, but covariates in different clusters are uncorrelated, we show that if the true p-dimensional signal involves only s clusters, then O(s \log p) samples suffice to accurately estimate it, regardless of the number of coefficients within the clusters. Since the estimation of s-sparse signals with completely independent covariates also requires O(s \log p) measurements, this shows that by using OWL regularization, we pay no price (in the number of measurements) for the presence of strongly correlated covariates.

This paper proposes using a Gaussian mixture model as a patch-based prior, for solving two image inverse problems, namely image deblurring and compressive imaging. We capitalize on the fact that variable splitting algorithms, like ADMM, are able to decouple the handling of the observation operator from that of the regularizer, and plug a state-of-the-art algorithm into the denoising step. Furthermore, we show that, when applied to a specific type of image, a Gaussian mixture model trained from an database of images of the same type is able to outperform current state-of-the-art generic methods.

Abstract Research on the problem of feature selection for clustering continues to develop. This is a challenging task, mainly due to the absence of class labels to guide the search for relevant features. Categorical feature selection for clustering has rarely been addressed in the literature, with most of the proposed approaches having focused on numerical data. In this work, we propose an approach to simultaneously cluster categorical data and select a subset of relevant features. Our approach is based on a modification of a finite mixture model (of multinomial distributions), where a set of latent variables indicate the relevance of each feature. To estimate the model parameters, we implement a variant of the expectation‐maximization algorithm that simultaneously selects the subset of relevant features, using a minimum message length criterion. The proposed approach compares favourably with two baseline methods: a filter based on an entropy measure and a wrapper based on mutual information. The results obtained on synthetic data illustrate the ability of the proposed expectation‐maximization method to recover ground truth. An application to real data, referred to official statistics, shows its usefulness.

Arguably, the most difficult task in text classification is to choose an appropriate set of features that allows machine learning algorithms to provide accurate classification. Most state-of-the-art techniques for this task involve careful feature engineering and a pre-processing stage, which may be too expensive in the emerging context of massive collections of electronic texts. In this paper, we propose efficient methods for text classification based on information-theoretic dissimilarity measures, which are used to define dissimilarity-based representations. These methods dispense with any feature design or engineering, by mapping texts into a feature space using universal dissimilarity measures; in this space, classical classifiers (e.g. nearest neighbor or support vector machines) can then be used. The reported experimental evaluation of the proposed methods, on sentiment polarity analysis and authorship attribution problems, reveals that it approximates, sometimes even outperforms previous state-of-the-art techniques, despite being much simpler, in the sense that they do not require any text pre-processing or feature engineering.

Development of Computer Aided Diagnosis systems that mimic the performance of dermatologists when diagnosing dermoscopy images is a challenging task. Despite the relevance of color in the diagnosis of melanomas, few of the proposed systems exploit this characteristic directly. In this paper we propose a new methodology for color identification in dermoscopy images. Our approach is to learn a statistical model for each color using Gaussian mixtures. The results show that the proposed method performs well, with an average Spearman correlation of 0.7981, with respect to a human expert.

One of the early successful approaches to deal with the now classical ℓ2+ ℓ1optimization formulation of sparse signal recovery (often known as the LASSO) was based on re-writing it as a bound-constrained quadratic program (BCQP), which was then tackled using a gradient projection (GP) algorithm with a spectral (Barzilai-Borwein) step choice. The resulting algorithm (called gradient projection for sparse reconstruction - GPSR) exhibited state-of-the-art speed when it was introduced, but now, 6 years later, much faster alternatives exist. In this paper, we revisit the BCQP formulation and show how it can be efficiently dealt with using the alternating direction method of multipliers (ADMM). We give preliminary experimental evidence that this approach is competitive with the current state-of-the-art, in a set of benchmark problems.

We apply the OSCAR (octagonal selection and clustering algorithms for regression) in recovering group-sparse matrices (two-dimensional — 2D — arrays) from compressive measurements. We propose a 2D version of OSCAR (2OSCAR) consisting of the ℓ1norm and the pair-wise ℓ∞norm, which is convex but non-differentiable. We show that the proximity operator of 2OSCAR can be computed based on that of OSCAR. The 2OSCAR problem can thus be efficiently solved by state-of-the-art proximal splitting algorithms. Experiments on group-sparse 2D array recovery show that 2OSCAR regularization solved by the SpaRSA algorithm is the fastest choice, while the PADMM algorithm (with debiasing) yields the most accurate results.

We propose a new method, robust binary fused compressive sensing (RoBFCS), to recover sparse piece-wise smooth signals from 1-bit compressive measurements. The proposed method is a modification of our previous binary fused compressive sensing (BFCS) algorithm, which is based on the binary iterative hard thresholding (BIHT) algorithm. As in BIHT, the data term of the objective function is a one-sided norm. Experiments show that the proposed algorithm is able to take advantage of the piece-wise smoothness of the original signal and detect sign flips and correct them, achieving more accurate recovery than BFCS and BIHT.

In research on Silent Speech Interfaces (SSI), different sources of information (modalities) have been combined, aiming at obtaining better performance than the individual modalities. However, when combining these modalities, the dimensionality of the feature space rapidly increases, yielding the well-known "curse of dimensionality". As a consequence, in order to extract useful information from this data, one has to resort to feature selection (FS) techniques to lower the dimensionality of the learning space. In this paper, we assess the impact of FS techniques for silent speech data, in a dataset with 4 non-invasive and promising modalities, namely: video, depth, ultrasonic Doppler sensing, and surface electromyography. We consider two supervised (mutual information and Fisher's ratio) and two unsupervised (meanmedian and arithmetic mean geometric mean) FS filters. The evaluation was made by assessing the classification accuracy (word recognition error) of three well-known classifiers (knearest neighbors, support vector machines, and dynamic time warping). The key results of this study show that both unsupervised and supervised FS techniques improve on the classification accuracy on both individual and combined modalities. For instance, on the video component, we attain relative performance gains of 36.2% in error rates. FS is also useful as pre-processing for feature fusion

We consider a new family of regularizers, termed weighted sorted${\ell_1}$norms (WSL1), which generalizes the recently introduced octagonal shrinkage and clustering algorithm for regression (OSCAR) and also contains the${\ell_1}$and${\ell_\infty}$norms as particular instances. We focus on a special case of the WSL1, the decreasing WSL1 (DWSL1), where the elements of the argument vector are sorted in non-increasing order and the weights are also non-increasing. In this letter, after showing that the DWSL1 is indeed a norm, we derive two key tools for its use as a regularizer: the dual norm and the Moreau proximity operator.

This paper presents a new method to estimate the parameters of two types of blurs, linear uniform motion (approximated by a line characterized by angle and length) and out-of-focus (modeled as a uniform disk characterized by its radius), for blind restoration of natural images. The method is based on the spectrum of the blurred images and is supported on a weak assumption, which is valid for the most natural images: the power-spectrum is approximately isotropic and has a power-law decay with the spatial frequency. We introduce two modifications to the radon transform, which allow the identification of the blur spectrum pattern of the two types of blurs above mentioned. The blur parameters are identified by fitting an appropriate function that accounts separately for the natural image spectrum and the blur frequency response. The accuracy of the proposed method is validated by simulations, and the effectiveness of the proposed method is assessed by testing the algorithm on real natural blurred images and comparing it with state-of-the-art blind deconvolution methods.

The alternating direction method of multipliers (ADMM) is an efficient optimization tool that achieves state-of-the-art speed in several imaging inverse problems, by splitting the underlying problem into simpler, efficiently solvable sub-problems. In deconvolution, one of these sub-problems requires a matrix inversion, which has been shown to be efficiently computable (via the FFT), if the observation operator is circulant, i.e., under periodic boundary conditions. We extend ADMM-based image deconvolution to a more realistic scenario: unknown boundaries. The observation is modeled as the composition of a periodic convolution with a spatial mask that excludes the regions where the periodic convolution is invalid. We show that the resulting algorithms inherit the convergence guarantees of ADMM and illustrate its performance on non-periodic de-blurring under frame-based regularization.

Blind image deblurring (BID) is an ill-posed inverse problem, typically solved by imposing some form of regularization (prior knowledge) on the unknown blur and original image. A recent approach, although not requiring prior knowledge on the blurring filter, achieves state-of-the-art performance for a wide range of real-world BID problems. We propose a new version of that method, in which both the optimization problems with respect to the unknown image and with respect to the unknown blur are solved by the alternating direction method of multipliers (ADMM) - an optimization tool that has recently sparked much interest for solving inverse problems, namely due to its modularity and state-of-the-art speed. Our approach also handles seamlessly the realistic case of blind deblurring with unknown boundary conditions. Experiments with synthetic and real blurred images show the competitiveness of the proposed method, both in terms of speed and restoration quality.

Image deblurring (ID) is an ill-posed problem typically addressed by using regularization, or prior knowledge, on the unknown image (and also on the blur operator, in the blind case). ID is often formulated as an optimization problem, where the objective function includes a data term encouraging the estimated image (and blur, in blind ID) to explain the observed data well (typically, the squared norm of a residual) plus a regularizer that penalizes solutions deemed undesirable. The performance of this approach depends critically (among other things) on the relative weight of the regularizer (the regularization parameter) and on the number of iterations of the algorithm used to address the optimization problem. In this paper, we propose new criteria for adjusting the regularization parameter and/or the number of iterations of ID algorithms. The rationale is that if the recovered image (and blur, in blind ID) is well estimated, the residual image is spectrally white; contrarily, a poorly deblurred image typically exhibits structured artifacts (e.g., ringing, oversmoothness), yielding residuals that are not spectrally white. The proposed criterion is particularly well suited to a recent blind ID algorithm that uses continuation, i.e., slowly decreases the regularization parameter along the iterations; in this case, choosing this parameter and deciding when to stop are one and the same thing. Our experiments show that the proposed whiteness-based criteria yield improvements in SNR, on average, only 0.15 dB below those obtained by (clairvoyantly) stopping the algorithm at the best SNR. We also illustrate the proposed criteria on non-blind ID, reporting results that are competitive with state-of-the-art criteria (such as Monte Carlo-based GSURE and projected SURE), which, however, are not applicable for blind ID.

The alternating direction method of multipliers (ADMM) has recently sparked interest as a flexible and efficient optimization tool for inverse problems, namely, image deconvolution and reconstruction under non-smooth convex regularization. ADMM achieves state-of-the-art speed by adopting a divide and conquer strategy, wherein a hard problem is split into simpler, efficiently solvable sub-problems (e.g., using fast Fourier or wavelet transforms, or simple proximity operators). In deconvolution, one of these sub-problems involves a matrix inversion (i.e., solving a linear system), which can be done efficiently (in the discrete Fourier domain) if the observation operator is circulant, i.e., under periodic boundary conditions. This paper extends ADMM-based image deconvolution to the more realistic scenario of unknown boundary, where the observation operator is modeled as the composition of a convolution (with arbitrary boundary conditions) with a spatial mask that keeps only pixels that do not depend on the unknown boundary. The proposed approach also handles, at no extra cost, problems that combine the recovery of missing pixels (i.e., inpainting) with deconvolution. We show that the resulting algorithms inherit the convergence guarantees of ADMM and illustrate its performance on non-periodic deblurring (with and without inpainting of interior pixels) under total-variation and frame-based regularization.

The analysis of moving objects in image sequences (video) has been one of the major themes in computer vision. In this paper, we focus on video-surveillance tasks; more specifically, we consider pedestrian trajectories and propose modeling them through a small set of motion/vector fields together with a space-varying switching mechanism. Despite the diversity of motion patterns that can occur in a given scene, we show that it is often possible to find a relatively small number of typical behaviors, and model each of these behaviors by a "simple" motion field. We increase the expressiveness of the formulation by allowing the trajectories to switch from one motion field to another, in a space-dependent manner. We present an expectation-maximization algorithm to learn all the parameters of the model, and apply it to trajectory classification tasks. Experiments with both synthetic and real data support the claims about the performance of the proposed approach.

Feature selection is a central problem in machine learning and pattern recognition. On large datasets (in terms of dimension and/or number of instances), using search-based or wrapper techniques can be computationally prohibitive. Moreover, many filter methods based on relevance/redundancy assessment also take a prohibitively long time on high-dimensional datasets. In this paper, we propose efficient unsupervised and supervised feature selection/ranking filters for high-dimensional datasets. These methods use low-complexity relevance and redundancy criteria, applicable to supervised, semi-supervised, and unsupervised learning, being able to act as pre-processors for computationally intensive methods to focus their attention on smaller subsets of promising features. The experimental results, with up to 10 5 features, show the time efficiency of our methods, with lower generalization error than state-of-the-art techniques, while being dramatically simpler and faster.

The sliding window (SW) Lempel-Ziv (LZ) 77 algorithms are widely used for universal lossless data compression. The LZ77 encoding component performs repeated substring search. Data structures, such as hash tables and trees have been used for fast search, at the expense of memory usage. Recently, suffix arrays (SA) have been used for dictionary representation and LZ77 decomposition, using less memory than those data structures.

This paper addresses an image labeling problem, in which it is assumed that there are multiple sensors available at each pixel with some of them possibly inactive. In addition to not being known which sensors are active or inactive, the sensor measurements are also obtained in random unknown order. Given these incomplete observations, we wish to identify which sensors are active at each site and which observations were produced by each sensor. This labeling problem extends classic image segmentation, since it allows multiple labels (i.e., region overlapping). The paper provides methods to solve this problem in two scenarios: known and unknown sensor models. A new minimization algorithm, inspired by hierarchical clustering, is introduced to minimize the energy function resulting from the proposed inference criterion.

In this paper we introduce a novel method to determine the model order of a stochastic model for moving objects. The main assumption is that we make use of the knowledge that the obtained model is going to be used for some task, specifically, for trajectory classification. Particularly, the object motion is described by trajectories performed by the objects (e.g., pedestrians), during their motion, by representing them by a small and meaningful mixtures of vector fields. We present a discriminative method for model selection without resort to computationally expensive cross-validation procedures. The idea is, thus, to select the generative model achieving the best classification performance. Although the topic of application is video surveillance, the proposed method can easily be extended to other practical situations. Experiments with both synthetic and real data concerning pedestrian activities illustrate the performance of the proposed approach.

We propose a new fast algorithm for solving one of the standard approaches to ill-posed linear inverse problems (IPLIP), where a (possibly nonsmooth) regularizer is minimized under the constraint that the solution explains the observations sufficiently well. Although the regularizer and constraint are usually convex, several particular features of these problems (huge dimensionality, nonsmoothness) preclude the use of off-the-shelf optimization tools and have stimulated a considerable amount of research. In this paper, we propose a new efficient algorithm to handle one class of constrained problems (often known as basis pursuit denoising) tailored to image recovery applications. The proposed algorithm, which belongs to the family of augmented Lagrangian methods, can be used to deal with a variety of imaging IPLIP, including deconvolution and reconstruction from compressive observations (such as MRI), using either total-variation or wavelet-based (or, more generally, frame-based) regularization. The proposed algorithm is an instance of the so-called alternating direction method of multipliers, for which convergence sufficient conditions are known; we show that these conditions are satisfied by the proposed algorithm. Experiments on a set of image restoration and reconstruction benchmark problems show that the proposed algorithm is a strong contender for the state-of-the-art.

Ill-posed linear inverse problems (ILIP), such as restoration and reconstruction, are a core topic of signal/image processing. A standard formulation for dealing with ILIP consists in a constrained optimization problem, where a regularization function is minimized under the constraint that the solution explains the observations sufficiently well. The regularizer and constraint are usually convex; however, several particular features of these problems (huge dimensionality, non-smoothness) preclude the use of off-the-shelf optimization tools and have stimulated much research. In this paper, we propose a new efficient algorithm to handle one class of constrained problems (known as basis pursuit denoising) tailored to image recovery applications. The proposed algorithm, which belongs to the category of augmented Lagrangian methods, can be used to deal with a variety of imaging ILIP, including deconvolution and reconstruction from compressive observations (such as MRI). Experiments testify for the effectiveness of the proposed method.

In some imaging inverse problems, it may be desired that the solution simultaneously exhibits a set of properties not enforceable by a single regularizer. To attain this goal, one may use a linear combinations of regularizers, thus encouraging the solution to simultaneously exhibit the characteristics enforced by each of them. This paper addresses the optimization problem associated with this type of compound regularization, using an alternating direction optimization algorithm. We illustrate the approach in two image deblurring problems - one in which the images are simultaneously sparse and piece-wise smooth, using a linear combination of the ℓ1and total variation regularizers, and the other for a natural image with a combination of frame-based synthesis and analysis ℓ1norm regularizers.

Most approaches to learn classifiers for structured objects (e.g., images) use generative models in a classical Bayesian framework. However, state-of-the-art classifiers for vectorial data (e.g., support vector machines) are learned discriminatively. A generative embedding is a mapping from the object space into a fixed dimensional score space, induced by a generative model, usually learned from data. The fixed dimensionality of these generative score spaces makes them adequate for discriminative learning of classifiers, thus bringing together the best of the discriminative and generative paradigms. In particular, it was recently shown that this hybrid approach outperforms a classifier obtained directly for the generative model upon which the score space was built. Using a generative embedding involves two steps: (i) defining and learning the generative model and using it to build the embedding; (ii) discriminatively learning a (maybe kernel) classifier on the adopted score space. The literature on generative embeddings is essentially focused on step (i), usually using some standard off-the-shelf tool for step (ii). In this paper, we adopt a different approach, by focusing also on the discriminative learning step. In particular, we combine two very recent and top performing tools in each of the steps: (i) the free energy score space; (ii) non-extensive information theoretic kernels. In this paper, we apply this methodology in scene recognition. Experimental results on two benchmark datasets shows that our approach yields state-of-the-art performance.

Restoration of Poissonian images is a class of inverse problem arising in fields such medical and astronomical imaging. Regularization criteria that combine the Poisson log-likelihood with a non-smooth convex regularizer lead to optimization problems with several difficulties: the log-likelihood does not have a Lipschitzian gradient; the regularizer is non-smooth; there is a non-negativity constraint. Using convex analysis tools, we give sufficient conditions for existence and uniqueness of solutions of these optimization problems for (frame-based) analysis and synthesis formulations. Then, we attack these problems with an adapted version of the alternating direction method of multipliers and show that sufficient conditions for convergence are met. The algorithm is shown to be competitive, often outperform, state-of-the-art methods.

We propose a method to classify human trajectories, modeled by a set of motion vector fields, each tailored to describe a specific motion regime. Trajectories are modeled as being composed of segments corresponding to different motion regimes, each generated by one of the underlying motion fields. Switching among the motion fields follows a probabilistic mechanism, described by a field of stochastic matrices. This yields a space-dependent motion model which can be estimated using an expectation-maximization (EM) algorithm. To address the model selection question (how many fields to use?), we adopt a discriminative criterion based on classification accuracy on a held out set. Experiments with real data (human trajectories in a shopping mall) illustrate the ability of the proposed approach to classify complex trajectories into high level classes (client versus non-client).

A central issue in mixture-type models is the determination of a suitable number of components that best suits the observed data. In this paper, we address this issue in the context of trajectory classification based on mixtures of motion vector fields. We adopt a discriminative criterion for choosing among alternative models for each class, based on the classification accuracy on a held out dataset. The key idea is that we make use of the knowledge that the obtained model is going to be used for a specific task: classification. Experiments with both synthetic and real data concerning pedestrian activity classification illustrate the performance of the adopted criterion.

In this paper, a novel approach for contour based 2D shape recognition is proposed, using a class of information theoretic kernels recently introduced. This kind of kernels, based on a non-extensive generalization of the classical Shannon information theory, are defined on probability measures. In the proposed approach, chain code representations are first extracted from the contours; then n-gram statistics are computed and used as input to the information theoretic kernels. We tested different versions of such kernels, using support vector machine and nearest neighbor classifiers. An experimental evaluation on the Chicken pieces dataset shows that the proposed approach significantly outperforms the current state-of-the-art methods.

The advance of falsification technology increases security concerns and gives biometrics an important role in security solutions. The electrocardiogram (ECG) is an emerging biometric that does not need liveliness verification. There is strong evidence that ECG signals contain sufficient discriminative information to allow the identification of individuals from a large population. Most approaches rely on ECG data and the fiducia of different parts of the heartbeat waveform. However non-fiducial approaches have proved recently to be also effective, and have the advantage of not relying critically on the accurate extraction of fiducia data. In this paper, we propose a new non-fiducial ECG biometric identification method based on data compression techniques, namely the Ziv-Merhav cross parsing algorithm for symbol sequences (strings). Our method relies on a string similarity measure derived from algorithmic cross complexity concept and its compression-based approximation. We present results on real data, one-lead ECG, acquired during a concentration task, from 19 healthy individuals. Our approach achieves 100% subject recognition rate despite the existence of differentiated stress states.

Much of the progress made in image processing in the past decades can be attributed to better modeling of image content and a wise deployment of these models in relevant applications. This path of models spans from the simple l2-norm smoothness through robust, thus edge preserving, measures of smoothness (e.g. total variation), and until the very recent models that employ sparse and redundant representations. In this paper, we review the role of this recent model in image processing, its rationale, and models related to it. As it turns out, the field of image processing is one of the main beneficiaries from the recent progress made in the theory and practice of sparse and redundant representations. We discuss ways to employ these tools for various image-processing tasks and present several applications in which state-of-the-art results are obtained.

We propose a new fast algorithm for solving one of the standard formulations of image restoration and reconstruction which consists of an unconstrained optimization problem where the objective includes an l2 data-fidelity term and a nonsmooth regularizer. This formulation allows both wavelet-based (with orthogonal or frame-based representations) regularization or total-variation regularization. Our approach is based on a variable splitting to obtain an equivalent constrained optimization formulation, which is then addressed with an augmented Lagrangian method. The proposed algorithm is an instance of the so-called alternating direction method of multipliers, for which convergence has been proved. Experiments on a set of image restoration and reconstruction benchmark problems show that the proposed algorithm is faster than the current state of the art methods.

Multiplicative noise (also known as speckle noise) models are central to the study of coherent imaging systems, such as synthetic aperture radar and sonar, and ultrasound and laser imaging. These models introduce two additional layers of difficulties with respect to the standard Gaussian additive noise scenario: (1) the noise is multiplied by (rather than added to) the original image; (2) the noise is not Gaussian, with Rayleigh and Gamma being commonly used densities. These two features of multiplicative noise models preclude the direct application of most state-of-the-art algorithms, which are designed for solving unconstrained optimization problems where the objective has two terms: a quadratic data term (log-likelihood), reflecting the additive and Gaussian nature of the noise, plus a convex (possibly nonsmooth) regularizer (e.g., a total variation or wavelet-based regularizer/prior). In this paper, we address these difficulties by: (1) converting the multiplicative model into an additive one by taking logarithms, as proposed by some other authors; (2) using variable splitting to obtain an equivalent constrained problem; and (3) dealing with this optimization problem using the augmented Lagrangian framework. A set of experiments shows that the proposed method, which we name MIDAL (multiplicative image denoising by augmented Lagrangian), yields state-of-the-art results both in terms of speed and denoising performance.

Much research has been devoted to the problem of restoring Poissonian images, namely for medical and astronomical applications. However, the restoration of these images using state-of-the-art regularizers (such as those based upon multiscale representations or total variation) is still an active research area, since the associated optimization problems are quite challenging. In this paper, we propose an approach to deconvolving Poissonian images, which is based upon an alternating direction optimization method. The standard regularization [or maximum a posteriori (MAP)] restoration criterion, which combines the Poisson log-likelihood with a (nonsmooth) convex regularizer (log-prior), leads to hard optimization problems: the log-likelihood is nonquadratic and nonseparable, the regularizer is nonsmooth, and there is a nonnegativity constraint. Using standard convex analysis tools, we present sufficient conditions for existence and uniqueness of solutions of these optimization problems, for several types of regularizers: total-variation, frame-based analysis, and frame-based synthesis. We attack these problems with an instance of the alternating direction method of multipliers (ADMM), which belongs to the family of augmented Lagrangian algorithms. We study sufficient conditions for convergence and show that these are satisfied, either under total-variation or frame-based (analysis and synthesis) regularization. The resulting algorithms are shown to outperform alternative state-of-the-art methods, both in terms of speed and restoration accuracy.

This paper proposes an approach for recognizing human activities (more specifically, pedestrian trajectories) in video sequences, in a surveillance context. A system for automatic processing of video information for surveillance purposes should be capable of detecting, recognizing, and collecting statistics of human activity, reducing human intervention as much as possible. In the method described in this paper, human trajectories are modeled as a concatenation of segments produced by a set of low level dynamical models. These low level models are estimated in an unsupervised fashion, based on a finite mixture formulation, using the expectation-maximization (EM) algorithm; the number of models is automatically obtained using a minimum message length (MML) criterion. This leads to a parsimonious set of models tuned to the complexity of the scene. We describe the switching among the low-level dynamic models by a hidden Markov chain; thus, the complete model is termed a switched dynamical hidden Markov model (SD-HMM). The performance of the proposed method is illustrated with real data from two different scenarios: a shopping center and a university campus. A set of human activities in both scenarios is successfully recognized by the proposed system. These experiments show the ability of our approach to properly describe trajectories with sudden changes.

The Lempel-Ziv 77 (LZ77) and LZ-Storer-Szymanski (LZSS) text compression algorithms use a sliding window over the sequence of symbols, with two sub-windows: the dictionary (symbols already encoded) and the look-ahead-buffer (LAB) (symbols not yet encoded). Binary search trees and suffix trees (ST) have been used to speedup the search of the LAB over the dictionary, at the expense of high memory usage [1]. A suffix array (SA) is a simpler, more compact data structure which uses (much) less memory [2,3] to hold the same information. The SA for a length m string is an array of integers ([1], ...[k], ...a[m]) that stores the lexicographic order of suffix k of the string; sub-string searching, as used in LZ77/LZSS, is done by searching the SA.

Multiplicative noise models occur in the study of several coherent imaging systems, such as synthetic aperture radar and sonar, and ultrasound and laser imaging. This type of noise is also commonly referred to as speckle. Multiplicative noise introduces two additional layers of difficulties with respect to the popular Gaussian additive noise model: (1) the noise is multiplied by (rather than added to) the original image, and (2) the noise is not Gaussian, with Rayleigh and Gamma being commonly used densities. These two features of the multiplicative noise model preclude the direct application of state-of-the-art restoration methods, such as those based on the combination of total variation or wavelet-based regularization with a quadratic observation term. In this paper, we tackle these difficulties by: (1) using the common trick of converting the multiplicative model into an additive one by taking logarithms, and (2) adopting the recently proposed split Bregman approach to estimate the underlying image under total variation regularization. This approach is based on formulating a constrained problem equivalent to the original unconstrained one, which is then solved using Bregman iterations (equivalently, an augmented Lagrangian method). A set of experiments show that the proposed method yields state-of-the-art results.

This work introduces a new approach to modeling object trajectories in image sequences. Trajectories performed by natural objects (e.g., people, animals) typically depend on the position of each object in the scene and can change in an unpredictable way. Despite this diversity, there is often a small number of typical motion patterns based on which it is possible to explain all the observed trajectories. To achieve this goal, we model each of these motion patterns using a motion field and allow objects to switch between fields in a space-varying, possible probabilistic, way. Our approach provides a space-dependent motion model which can be estimated using an expectation-maximization (EM) algorithm. Experiments with both synthetic and real data are presented to illustrate the ability of the proposed approach in modeling different motion patterns.

Finding sparse approximate solutions to large underdetermined linear systems of equations is a common problem in signal/image processing and statistics. Basis pursuit, the least absolute shrinkage and selection operator (LASSO), wavelet-based deconvolution and reconstruction, and compressed sensing (CS) are a few well-known areas in which problems of this type appear. One standard approach is to minimize an objective function that includes a quadratic (pound2) error term added to a sparsity-inducing (usuallypound1) regularizer. We present an algorithmic framework for the more general problem of minimizing the sum of a smooth convex function and a nonsmooth, possibly nonconvex, sparsity-inducing function. We propose iterative methods in which each step is an optimization subproblem involving a separable quadratic term (diagonal Hessian) plus the original sparsity-inducing term. Our approach is suitable for cases in which this subproblem can be solved much more rapidly than the original problem. In addition to solving the standardpound2-pound1case, our approach handles other problems, e.g.,poundpregularizers with p ne 1, or group-separable (GS) regularizers. Experiments with CS problems show that our approach provides state-of-the-art speed for the standardpound2-pound1problem, and is also efficient on problems with GS regularizers.

In several imaging inverse problems, it may be of interest to encourage the solution to have characteristics which are most naturally expressed by the combination of more than one regularizer. The resulting optimization problems can not be dealt with by the current state-of-the-art algorithms, which are designed for single regularizers (such as total variation or sparseness-inducing penalties, but not both simultaneously). In this paper, we introduce an iterative algorithm to solve the optimization problem resulting from image (or signal) inverse problems with two (or more) regularizers. We illustrate the new algorithm in a problem of restoration of "group sparse" images, i.e., images displaying a special type of sparseness in which the active pixels tend to cluster together. Experimental results show the effectiveness of the proposed algorithm in solving the corresponding optimization problem.

This work introduces a non-supervised algorithm for learning generative models for classification/recognition of human activities (specifically, pedestrian trajectories) with application to video surveillance. The proposed algorithm comprises two main features: (?) a set of low level dynamical models of the trajectories, estimated in unsupervised manner using the expectation-maximization (EM) algorithm and automatic model selection using the minimum message length (MML) criterion; (ii) a switching dynamical model described by an hidden Markov model (HMM) used to characterize the higher level activities. The hierarchical model with these two levels is herein denoted as switched dynamical hidden Markov model (SD-HMM). We illustrate the performance of the proposed technique for human activity recognition in a university campus.

Positive definite kernels on probability measures have been recently applied in structured data classification problems. Some of these kernels are related to classic information theoretic quantities, such as mutual information and the Jensen-Shannon divergence. Meanwhile, driven by recent advances in Tsallis statistics, nonextensive generalizations of Shannon's information theory have been proposed. This paper bridges these two trends. We introduce the Jensen-Tsallis q-difference, a generalization of the Jensen-Shannon divergence. We then define a new family of nonextensive mutual information kernels, which allow weights to be assigned to their arguments, and which includes the Boolean, Jensen-Shannon, and linear kernels as particular cases. We illustrate the performance of these kernels on text categorization tasks.

Recent approaches to classification of text, images, and other types of structured data, launched the quest for positive definite (p.d.) kernels on probability measures. In particular, kernels based on the Jensen-Shannon (JS) divergence and other information-theoretic quantities have been proposed. We introduce new JS-type divergences, by extending its two building blocks: convexity and Shannon’s entropy. These divergences are then used to define new information-theoretic kernels on measures. In particular, we introduce a new concept of q-convexity, for which a Jensen q-inequality is proved. Based on this inequality, we introduce the Jensen-Tsallis q-difference, a nonextensive generalization of the Jensen-Shannon divergence. Furthermore, we provide denormalization formulae for entropies and divergences, which we use to define a family of nonextensive information-theoretic kernels on measures. This family, grounded in nonextensive entropies, extends Jensen-Shannon divergence kernels, and allows assigning weights to its arguments.

The discovery of networks is a fundamental problem arising in numerous fields of science and technology, including communication systems, biology, sociology, and neuroscience. Unfortunately, it is often difficult, or impossible, to obtain data that directly reveal network structure, and so one must infer a network from incomplete data. This paper considers inferring network structure from "co-occurrence" data: observations that identify which network components (e.g., switches, routers, genes) carry each transmission but do not indicate the order in which they handle the transmission. Without order information, the number of networks that are consistent with the data grows exponentially with the size of the network (i.e., the number of nodes). Yet, the basic engineering/evolutionary principles underlying most networks strongly suggest that not all data-consistent networks are equally likely. In particular, nodes that co-occur in many observations are probably closely connected. With this in mind, we model the co-occurrence observations as independent realizations of a random walk on the network, subjected to a random permutation to account for the lack of order information. Treating permutations as missing data, we derive an expectation-maximization (EM) algorithm for estimating the random walk parameters. The model and EM algorithm significantly simplify the problem, but the computational complexity of the reconstruction process does grow exponentially in the length of each transmission path. For networks with long paths, the exact e-step may be computationally intractable. We propose a polynomial-time Monte Carlo EM algorithm based on importance sampling and derive conditions that ensure convergence of the algorithm with high probability. Simulations and experiments with Internet measurements demonstrate the promise of this approach.

This paper considers the problem of learning cellular signaling networks from incomplete measurements of pathway activity. Cells respond to environmental changes (e.g., starvation, heat shock) via a sequence of intracellular protein-protein interactions, leading to the production of proteins which modify their fundamental operations. Biologists have discovered some of these signaling pathways, but the knowledge of cellular signaling is still very incomplete. Mathematically, the problem of genomic network tomography (GNT) - identifying cellular signaling networks from biological data - is similar to network inference problems arising in communication systems. This paper formulates GNT and presents a solution which builds on state-of-the-art communication network inference techniques while taking into account uncertainties which are inherent in biological data.

Iterative shrinkage/thresholding (IST) algorithms have been recently proposed to handle high-dimensional convex optimization problems arising in image inverse problems (namely deconvolution) under non-quadratic regularization (e.g., total variation or sparsity inducing regularizers on wavelet representations). The convergence speed of IST algorithms depends heavily on the nature of the direct operator, being very slow when this operator is severely ill-conditioned. In this paper, we introduce a two-step version of IST (termed 2IST, pronounced "twist") showing much faster convergence for strongly ill-conditioned operators. We give theoretical results concerning the convergence behavior of 2IST and show its effectiveness for wavelet-based and total variation image deconvolution.

This work introduces a semi-supervised approach for learning generative models for classification/recognition of human trajectories, with application to surveillance. The classifier is based on switched dynamical models, with each model describing a specific motion regime. We present a semi-supervised modified version of the classical Baum-Welch algorithm, which is able to take into account a subset of known model labels. The experimental results reported, using both synthetic and real data, show that the classifier learned with semi-supervision leads to a higher classification accuracy than the fully unsupervised version, thus validating the proposed approach.

Iterative shrinkage/thresholding (IST) algorithms have been recently proposed to handle a class of convex unconstrained optimization problems arising in image restoration and other linear inverse problems. This class of problems results from combining a linear observation model with a nonquadratic regularizer (e.g., total variation or wavelet-based regularization). It happens that the convergence rate of these IST algorithms depends heavily on the linear observation operator, becoming very slow when this operator is ill-conditioned or ill-posed. In this paper, we introduce two-step IST (TwIST) algorithms, exhibiting much faster convergence rate than IST for ill-conditioned problems. For a vast class of nonquadratic convex regularizers (l(p) norms, some Besov norms, and total variation), we show that TwIST converges to a minimizer of the objective function, for a given range of values of its parameters. For noninvertible observation operators, we introduce a monotonic version of TwIST (MTwIST); although the convergence proof does not apply to this scenario, we give experimental evidence that MTwIST exhibits similar speed gains over IST. The effectiveness of the new methods are experimentally confirmed on problems of image deconvolution and of restoration with missing samples.

Standard formulations of image/signal deconvolution under wavelet-based priors/regularizers lead to very high-dimensional optimization problems involving the following difficulties: the non-Gaussian (heavy-tailed) wavelet priors lead to objective functions which are nonquadratic, usually nondifferentiable, and sometimes even nonconvex; the presence of the convolution operator destroys the separability which underlies the simplicity of wavelet-based denoising. This paper presents a unified view of several recently proposed algorithms for handling this class of optimization problems, placing them in a common majorization-minimization (MM) framework. One of the classes of algorithms considered (when using quadratic bounds on nondifferentiable log-priors) shares the infamous "singularity issue" (SI) of "iteratively reweighted least squares" (IRLS) algorithms: the possibility of having to handle infinite weights, which may cause both numerical and convergence issues. In this paper, we prove several new results which strongly support the claim that the SI does not compromise the usefulness of this class of algorithms. Exploiting the unified MM perspective, we introduce a new algorithm, resulting from using l1 bounds for nonconvex regularizers; the experiments confirm the superior performance of this method, when compared to the one based on quadratic majorization. Finally, an experimental comparison of the several algorithms, reveals their relative merits for different standard types of scenarios.

The total variation regularizer is well suited to piecewise smooth images. If we add the fact that these regularizers are convex, we have, perhaps, the reason for the resurgence of interest on TV-based approaches to inverse problems. This paper proposes a new TV-based algorithm for image deconvolution, under the assumptions of linear observations and additive white Gaussian noise. To compute the TV estimate, we propose a majorization-minimization approach, which consists in replacing a difficult optimization problem by a sequence of simpler ones, by relying on convexity arguments. The resulting algorithm has O(N) computational complexity, for finite support convolutional kernels. In a comparison with state-of-the-art methods, the proposed algorithm either outperforms or equals them, with similar computational complexity

Image denoising is a classical problem which has been addressed using a variety of conceptual frameworks and computational tools. Most approaches use some form of penalty/prior as a regularizer, expressing a preference for images with some form of (generalized) "smoothness". Total variation (TV) and wavelet-based methods have received a great deal of attention in the last decade and are among the state of the art in this problem. However, as far as we know, no experimental studies have been carried out, comparing the relative performance of the two classes of methods. In this paper, we present the results of such a comparison. Prior to that, we introduce a new majorization-minimization algorithm to implement the TV denoising criterion. We conclude that TV is outperformed by recent state of the art wavelet-based denoising methods, but performs competitively with older wavelet-based methods.

This paper proposes a new approach to model-based clustering under prior knowl- edge. The proposed formulation can be interpreted from two different angles: as penalized logistic regression, where the class labels are only indirectly observed (via the probability density of each class); as finite mixture learning under a group- ing prior. To estimate the parameters of the proposed model, we derive a (gener- alized) EM algorithm with a closed-form E-step, in contrast with other recent approaches to semi-supervised probabilistic clustering which require Gibbs sam- pling or suboptimal shortcuts. We show that our approach is ideally suited for image segmentation: it avoids the combinatorial nature Markov random field pri- ors, and opens the door to more sophisticated spatial priors (e.g., wavelet-based) in a simple and computationally efficient way. Finally, we extend our formulation to work in unsupervised, semi-supervised, or discriminative modes.

We consider the problem of inferring the structure of a network from cooccurrence data: observations that indicate which nodes occur in a signaling pathway but do not directly reveal node order within the pathway. This problem is motivated by network inference problems arising in computational biology and communication systems, in which it is difficult or impossible to obtain precise time ordering information. Without order information, every permutation of the activated nodes leads to a different feasible solution, resulting in combinatorial explosion of the feasible set. However, physical principles underlying most networked systems suggest that not all feasible solutions are equally likely. Intuitively, nodes that co-occur more frequently are probably more closely connected. Building on this intuition, we model path co-occurrences as randomly shuffled samples of a random walk on the network. We derive a computationally efficient network inference algorithm and, via novel concentration inequalities for importance sampling estimators, prove that a polynomial complexity Monte Carlo version of the algorithm converges with high probability.

This paper introduces a formulation which allows using wavelet-based priors for image segmentation. This formulation can be used in supervised, unsupervised, or semi-supervised modes, and with any probabilistic observation model (intensity, multispectral, texture). Our main goal is to exploit the well-known ability of wavelet-based priors to model piece-wise smoothness (which underlies state-of-the-art methods for denoising, coding, and restoration) and the availability of fast algorithms for wavelet-based processing. The main obstacle to using wavelet-based priors for segmentation is that they're aimed at representing real values, rather than discrete labels, as needed for segmentation. This difficulty is sidestepped by the introduction of real-valued hidden fields, to which the labels are probabilistically related. These hidden fields, being unconstrained and real-valued, can be given any type of spatial prior, such as one based on wavelets. Under this model, Bayesian MAP segmentation is carried out by a (generalized) EM algorithm. Experiments on synthetic and real data testify for the adequacy of the approach.

We address the problem of image deconvolution under I/sub p/ norm (and other) penalties expressed in the wavelet domain. We propose an algorithm based on the bound optimization approach; this approach allows deriving EM-type algorithms without using the concept of missing/hidden data. The algorithm has provable monotonicity both with orthogonal or redundant wavelet transforms. We also derive bounds on the l/sub p/ norm penalties to obtain closed form update equations for any p /spl isin/ [0, 2]. Experimental results show that the proposed method achieves state-of-the-art performance.

This paper describes a new algorithm for the recognition of human activities. These activities are modelled using banks of switched dynamical models, each of which is tailored to a specific motion regime. Furthermore, it is assumed that model switching happens according to a space-dependent Markov chain, i.e., some transitions are more probable in specific regions of the image. Space dependence allows the model to represent the interaction between the person and static elements of the scene. The paper describes learning algorithms for space-dependent switched dynamical models and presents experimental results with synthetic and real data.

Recently developed methods for learning sparse classifiers are among the state-of-the-art in supervised learning. These methods learn classifiers that incorporate weighted sums of basis functions with sparsity-promoting priors encouraging the weight estimates to be either significantly large or exactly zero. From a learning-theoretic perspective, these methods control the capacity of the learned classifier by minimizing the number of basis functions used, resulting in better generalization. This paper presents three contributions related to learning sparse classifiers. First, we introduce a true multiclass formulation based on multinomial logistic regression. Second, by combining a bound optimization approach with a component-wise update procedure, we derive fast exact algorithms for learning sparse multiclass classifiers that scale favorably in both the number of training samples and the feature dimensionality, making them applicable even to large data sets in high-dimensional feature spaces. To the best of our knowledge, these are the first algorithms to perform exact multinomial logistic regression with a sparsity-promoting prior. Third, we show how nontrivial generalization bounds can be derived for our classifier in the binary case. Experimental results on standard benchmark data sets attest to the accuracy, sparsity, and efficiency of the proposed methods.

The problem of inferring 3D orientation of a camera from video sequences has been mostly addressed by first computing correspondences of image features. This intermediate step is now seen as the main bottleneck of those approaches. In this paper, we propose a new 3D orientation estimation method for urban (indoor and outdoor) environments, which avoids correspondences between frames. The scene property exploited by our method is that many edges are oriented along three orthogonal directions; this is the recently introduced Manhattan world (MW) assumption. The main contributions of this paper are: the definition of equivalence classes of equiprojective orientations, the introduction of a new small rotation model, formalizing the fact that the camera moves smoothly, and the decoupling of elevation and twist angle estimation from that of the compass angle. We build a probabilistic sequential orientation estimation method, based on an MW likelihood model, with the above-listed contributions allowing a drastic reduction of the search space for each orientation estimate. We demonstrate the performance of our method using real video sequences.

A graph-based prior is proposed for parametric semi-supervised classi- fication. The prior utilizes both labelled and unlabelled data; it also in- tegrates features from multiple views of a given sample (e.g., multiple sensors), thus implementing a Bayesian form of co-training. An EM algorithm for training the classifier automatically adjusts the tradeoff be- tween the contributions of: (a) the labelled data; (b) the unlabelled data; and (c) the co-training information. Active label query selection is per- formed using a mutual information based criterion that explicitly uses the unlabelled data and the co-training information. Encouraging results are presented on public benchmarks and on measured data from single and multiple sensors. 1 Introduction In many pattern classification problems, the acquisition of labelled training data is costly and/or time consuming, whereas unlabelled samples can be obtained easily. Semi- supervised algorithms that learn from both labelled and unlabelled samples have been the focus of much research in the last few years; a comprehensive review up to 2001 can be found in [13], while more recent references include [1, 2, 6, 7, 1618]. Most recent semi-supervised learning algorithms work by formulating the assumption that "nearby" points, and points in the same structure (e.g., cluster), should have similar labels [6, 7, 16]. This can be seen as a form of regularization, pushing the class boundaries toward regions of low data density. This regularization is often implemented by associating the vertices of a graph to all the (labelled and unlabelled) samples, and then formulating the problem on the vertices of the graph [6, 1618]. While current graph-based algorithms are inherently transductive -- i.e., they cannot be used directly to classify samples not present when training -- our classifier is paramet- ric and the learned classifier can be used directly on new samples. Furthermore, our al- gorithm is trained discriminatively by maximizing a concave objective function; thus we avoid thorny local maxima issues that plague many earlier methods. Unlike existing methods, our algorithm automatically learns the relative importance of the labelled and unlabelled data. When multiple views of the same sample are provided (e.g. features from different sensors), we develop a new Bayesian form of co-training [4]. In addition, we also show how to exploit the unlabelled data and the redundant views of the sample (from co-training) in order to improve active label query selection [15]. The paper is organized as follows. Sec. 2 briefly reviews multinomial logistic regression. Sec. 3 describes the priors for semi-supervised learning and co-training. The EM algorithm derived to learn the classifiers is presented in Sec. 4. Active label selection is discussed in Sec. 5. Experimental results are shown in Sec. 6, followed by conclusions in Sec. 7. 2 Multinomial Logistic Regression In an m-class supervised learning problem, one is given a labelled training set DL = {(x d 1, y ), . . . , (x )} 1 L, yL , where xi R is a feature vector and yi the corresponding (1) (m) class label. In "1-of-m" encoding, y = [y , . . . , y ] i is a binary vector, such that i i (c) (j) y = 1 and y = 0, for j = c, indicates that sample i belongs to class c. In multinomial i i logistic regression [5], the posterior class probabilities are modelled as log P (y(c) = 1|x) = xT w(c) - log m exp(xT w(k)), for c = 1, . . . , m, (1) k=1 where w(c) d R is the class-c weight vector. Notice that since m P (y(c)= 1|x) = 1, c=1 one of the weight vectors is redundant; we arbitrarily choose to set w(m) = 0, and consider the (d (m-1))-dimensional vector w = [(w(1))T , ..., (w(m-1))T ]T . Estimation of w may be achieved by maximizing the log-likelihood (with Y {y , ..., y } 1 L ) [5] (c) (w) log P (Y|w) = L m y xT w(c) - log m exp(xT w(j)) . (2) i=1 c=1 i i j=1 i In the presence of a prior p(w), we seek a maximum a posteriori (MAP) estimate, w = arg max { (w) + log p(w)} w . Actually, if the training data is separable, (w) is unbounded, and a prior is crucial. Although we focus on linear classifiers, we may see the d-dimensional feature vectors x as having resulted from some deterministic, maybe nonlinear, transformation of an input raw feature vector r; e.g., in a kernel classifier, xi = [1, K(ri, r1), ..., K(ri, rL)] (d = L + 1). 3 Graph-Based Data-Dependent Priors 3.1 Graph Laplacians and Regularization for Semi-Supervised Learning Consider a scalar function f = [f1, ..., f|V |]T , defined on the set V = {1, 2, ..., |V |} of vertices of an undirected graph (V, E). Each edge of the graph, joining vertices i and j, is given a weight kij = kji 0, and we collect all the weights in a |V | |V | matrix K. A natural way to measure how much f varies across the graph is by the quantity kij(fi - fj)2 = 2 f T f , (3) i j where = diag{ k k j 1j , ..., j |V |j } - K is the so-called graph Laplacian [2]. Notice that kij 0 (for all i, j) guarantees that is positive semi-definite and also that has (at least) one null eigenvalue (1T1 = 0, where 1 has all elements equal to one). In semi-supervised learning, in addition to DL, we are given U unlabelled samples DU = {xL+1, . . . , xL+U }. To use (3) for semi-supervised learning, the usual choice is to assign one vertex of the graph to each sample in X = [x1, . . . , xL+U ]T (thus |V | = L + U ), and to let kij represent some (non-negative) measure of "similarity" between xi and xj. A Gaussian random field (GRF) is defined on the vertices of V (with inverse variance ) p(f ) exp{- f T f /2}, in which configurations that vary more (according to (3)) are less probable. Most graph- based approaches estimate the values of f , given the labels, using p(f ) (or some modifica- tion thereof) as a prior. Accordingly, they work in a strictly transductive manner. 3.2 Non-Transductive Semi-Supervised Learning We first consider two-class problems (m = 2, thus w d R ). In contrast to previous uses of graph-based priors, we define f as the real function f (defined over the entire observation space) evaluated at the graph nodes. Specifically, f is defined as a linear function of x, and at the graph node i, fi f (xi) = wT xi. Then, f = [f1, ..., f|V |]T = Xw, and p(f ) induces a Gaussian prior on w, with precision matrix A = XT X, p(w) exp{-(/2) wT XT Xw} = exp{-(/2) wT Aw}. (4) Notice that since is singular, A may also be singular, and the corresponding prior may therefore be improper. This is no problem for MAP estimation of w because (as is well known) the normalization factor of the prior plays no role in this estimate. If we include extra regularization, by adding a non-negative diagonal matrix to A, the prior becomes p(w) exp -(1/2) wT (0A + ) w , (5) where we may choose = diag{1, ..., d}, = 1I, or even = 0. For m > 2, we define (m-1) identical independent priors, one for each w(c), c = 1, ..., m. The joint prior on w = [(w(1))T , ..., (w(m-1))T ]T is then m-1 1 (c) 1 p(w|) exp{- (w(c))T A + (c) w(c)} = exp{- wT ()w}, (6) 2 0 2 c=1 (c) (c) (c) where is a vector containing all the parameters, (c) = diag{ , ..., }, and i 1 d (1) (m-1) () = diag{ , ..., } A + block-diag{(1), ..., (m-1)}. (7) 0 0 Finally, since all the 's are inverses of variances, the conjugate priors are Gamma [3]: (c) (c) (c) (c) p( | | | | 0 0, 0) = Ga(0 0, 0), and p(i 1, 1) = Ga(i 1, 1), for c = 1, ..., m - 1 and i = 1, ..., d. Usually, 0, 0, 1, and 1 are given small values indicating diffuse priors. In the zero limit, we obtain scale-invariant (improper) Jeffreys hyper-priors. Summarizing, our model for semi-supervised learning includes the log-likelihood (2), a prior (6), and Gamma hyper-priors. In Section 4, we present a simple and computationally efficient expectation-maximization (EM) algorithm for obtaining the MAP estimate of w. 3.3 Exploiting Features from Multiple Sensors: The Co-Training Prior In some applications several sensors are available, each providing a different set of features. For simplicity, we assume two sensors s {1, 2}, but everything discussed here is easily (s) extended to any number of sensors. Denote the features from sensor s, for sample i, as x , i and Ss as the set of sample indices for which we have features from sensor s (S1 S2 = {1, ..., L + U }). Let O = S1 S2 be the indices for which both sensors are available, and OU = O {L + 1, ..., L + U } the unlabelled subset of O. By using the samples in S1 and S2 as two independent training sets, we may obtain two sep- arate classifiers (denoted w1 and w2). However, we can coordinate the information from both sensors by using an idea known as co-training [4]: on the OU samples, classifiers w1 and w2 should agree as much as possible. Notice that, in a logistic regression framework, the disagreement between the two classifiers on the OU samples can be measured by (1) (2) [(w1)T x - (w2)T x ]2 = T C , (8) iOU i i where = [(w1)T (w2)T ]T and C = [(x1)T (-x2)T ]T [(x1)T (-x2)T ]. This iOU i i i i suggests the "co-training prior" (where co is an inverse variance): p(w1, w2) = p() exp -(co/2) TC . (9) This Gaussian prior can be combined with two smoothness Gaussian priors on w1 and w2 (obtained as described in Section 3.2); this leads to a prior which is still Gaussian, p(w1, w2) = p() exp -(1/2) T coC + block-diag{1, 2} , (10) where 1 and 2 are the two graph-based precision matrices (see (7)) for w1 and w2. We can again adopt a Gamma hyper-prior for co. Under this prior, and with a logistic regression likelihood as above, estimates of w1 and w2 can easily be found using minor modifications to the EM algorithm described in Section 4. Computationally, this is only slightly more expensive than separately training the two classifiers. 4 Learning Via EM To find the MAP estimate w, we use the EM algorithm, with as missing data, which is equivalent to integrating out from the full posterior before maximization [8]. For simplicity, we will only describe the single sensor case (no co-training). E-step: We compute the expected value of the complete log-posterior, given Y and the current parameter estimate w: Q(w|w) E[log p(w, |Y)|w]. Since log p(w, |Y) = log p(Y|w) - (1/2)wT ()w + K, (11) (where K collects all terms independent of w) is linear w.r.t. all the parameters (see (6) and (7)), we just have to plug their conditional expectations into (11): Q(w|w) = log p(Y|w) - (1/2)wT E[()|w] w = (w) - (1/2)wT (w) w. (12) We consider several different choices for the structure of the matrix. The necessary expectations have well-known closed forms, due to the use of conjugate Gamma hyper- (c) priors [3]. For example, if the are m - 1 free non-negative parameters, we have 0 (c) (c) E[ |w] = (2 0 0 0 + d) [2 0 + (w(c))T Aw(c)]-1. (c) for c = 1, ..., m - 1. For = 0 0, we still have a simple closed-form expres- (c) sion for E[0|w], and the same is true for the parameters, for i > 0. Finally, i (w) E[()|w] results from replacing the 's in (7) by the corresponding conditional expectations. M-step: Given matrix (w), the M-step reduces to a logistic regression problem with a quadratic regularizer, i.e., maximizing (12). To this end, we adopt the bound optimization approach (see details in [5, 11]). Let B be a positive definite matrix such that -B bounds below (in the matrix sense) the Hessian of (w), which is negative definite, and g(w) is the gradient of (w). Then, we have the following lower bound on Q(w|w): Q(w|w) l(w) + (w - w)T g(w) - [(w - w)T B(w - w) + wT (w)w]/2. - The maximizer of this lower bound, wnew = (B + (w)) 1 (Bw + g(w)), is guaranteed to increase the Q-function, Q(wnew|w) Q(w|w), and we thus obtain a monotonic gen- eralized EM algorithm [5, 11]. This (maybe costly) matrix inversion can be avoided by a sequential approach where we only maximize w.r.t. one element of w at a time, preserving the monotonicity of the procedure. The sequential algorithm visits one particular element of w, say wu, and updates its estimate by maximizing the bound derived above, while keeping all other variables fixed at their previous values. This leads to - wnew = w ] [(B + (w)) 1 , u u + [gu(w) - ((w)w) (13) u uu] and wnew = w v v , for v = u. The total time required by a full sweep for all u = 1, ..., d is O(md(L + d)); this may be much better than the O((dm)3) of the matrix inversion. 5 Active Label Selection If we are allowed to obtain the label for one of the unlabelled samples, the following ques- tion arises: which sample, if labelled, would provide the most information? Consider the MAP estimate w provided by EM. Our approach uses a Laplace approxima- tion of the posterior p(w|Y) N (w|w, H-1), where H is the posterior precision matrix, i.e., the Hessian of minus the log-posterior H = 2(- log p(w|Y)). This approximation is known to be accurate for logistic regression under a Gaussian prior [14]. By treating (w) (the expectation of ()) as deterministic, we obtain an evidence-type approximation [14] H = 2[- log(p(Y|w)p(w|(w)))] = (w) + L (diag{p } - p pT ) x , i=1 i i i ixT i where pi is the (m - 1)-dimensional vector computed from (1), the c-th element of which indicates the probability that sample xi belongs to class c. Now let x DU be an unlabelled sample and y its label. Assume that the MAP esti- mate w remains unchanged after including y. In Sec. 7 we will discuss the merits and shortcomings of this assumption, which is only strictly valid when L . Accepting it implies that after labeling x, and regardless of y, the posterior precision changes to H = H + (diag{p} - ppT ) xxT . (14) Since the entropy of a Gaussian with precision H is (-1/2) log |H| (up to an additive constant), the mutual information (MI) between y and w (i.e., the expected decrease in entropy of w when y is observed) is I(w; y) = (1/2) log {|H |/|H|}. Our criterion is then: the best sample to label is the one that maximizes I(w; y). Further insight into I(w; y) can be obtained in the binary case (where p is a scalar); here, the matrix identity |H + p(1 - p)xxT | = |H|(1 + p(1 - p)xT H-1x) yields I(w; y) = (1/2) log(1 + p(1 - p)xT H-1x). (15) This MI is larger when p 0.5, i.e., for samples with uncertain classifications. On the other hand, with p fixed, I(w; y) grows with xT H-1x, i.e., it is large for samples with high variance of the corresponding class probability estimate. Summarizing, (15) favors samples with uncertain class labels and high uncertainty in the class probability estimate. 6 Experimental Results We begin by presenting two-dimensional synthetic examples to visually illustrate our semi- supervised classifier. Fig. 1 shows the utility of using unlabelled data to improve the deci- Figure 1: Synthetic two-dimensional examples. (a) Comparison of the supervised logistic linear classifier (boundary shown as dashed line) learned only from the labelled data (shown in color) with the proposed semi-supervised classifier (boundary shown as solid line) which also uses the unlabelled samples (shown as dots). (b) A RBF kernel classifier obtained by our algorithm, using two labelled samples (shaded circles) and many unlabelled samples. Figure 2: (a)-(c) Accuracy (on UCI datasets) of the proposed method, the supervised SVM, and the other semi-supervised classifiers mentioned in the text; a subset of samples is la- belled and the others are treated as unlabelled samples. In (d), a separate holdout set is used to evaluate the accuracy of our method versus the amount of labelled and unlabelled data. sion boundary in linear and non-linear (kernel) classifiers (see figure caption for details). Next we show results with linear classifiers on three UCI benchmark datasets. Results with nonlinear kernels are similar, and therefore omitted to save space. We compare our method against state-of-the-art semi-supervised classifiers: the GRF method of [18], the SGT method of [10], and the transductive SVM (TSVM) of [9]. For reference, we also present results for a standard SVM. To avoid unduly helping our method, we always use a k=5 nearest neighbors graph, though our algorithm is not very sensitive to k. To avoid disadvantaging other methods that do depend on such parameters, we use their best settings. Since these adjustments cannot be made in practice, the difference between our algorithm and the others is under-represented. Each point on the plots in Fig. 2(a)-(c) is an average of 20 trials: we randomly select 20 labelled sets which are used by every method. All remaining samples are used as unlabelled by the semi-supervised algorithms. Figs. 2(a)-(c) are transductive, in the sense that the unlabelled and test data are the same. Our logistic GRF is non-transductive: after being trained, it may be applied to classify new data without re-training. In Fig. 2(d) we present non-transductive results for the Ionosphere data. Training took place using labelled and unlabelled data, and testing was performed on 200 new unseen samples. The results suggest that semi-supervised classifiers are most relevant when the labelled set is small relative to the unlabelled set (as is often the case). Our final set of results address co-training (Sec. 3.3) and active learning (Sec. 5), applied to airborne sensing data for the detection of surface and subsurface land mines. Two sensors were used: (1) a 70-band hyper-spectral electro-optic (EOIR) sensor; (2) an X-band syn- thetic aperture radar (SAR). A simple (energy) "prescreener" detected potential targets; for each of these, two feature vectors were extracted, of sizes 420 and 9, for the EOIR and SAR sensors, respectively. 123 samples have features from the EOIR sensor alone, 398 from the Figure 3: (a) Land mine detection ROC curves of classifiers designed using only hyper- spectral (EOIR) features, only SAR features, and both. (b) Number of landmines detected during the active querying process (dotted lines), for active training and random selection (for the latter the bars reflect one standard deviation about the mean). ROC curves (solid) are for the learned classifier as applied to the remaining samples. SAR sensor alone, and 316 from both. This data will be made available upon request. We first consider supervised and semi-supervised classification. For the purely supervised case, a sparseness prior is used (as in [14]). In both cases a linear classifier is employed. For the data for which only one sensor is available, 20% of it is labelled (selected randomly). For the data for which both sensors are available, 80% is labelled (again selected randomly). The results presented in Fig. 3(a) show that, in general, the semi-supervised classifiers outperform the corresponding supervised ones, and the classifier learned from both sensors is markedly superior to classifiers learned from either sensor alone. In a second illustration, we use the active-learning algorithm (Sec. 5) to only acquire the 100 most informative labels. For comparison, we also show average results over 100 in- dependent realizations for random label query selection (error bars indicate one standard deviation). The results in Fig. 3(b) are plotted in two stages: first, mines and clutter are se- lected during the labeling process (dashed curves); then, the 100 labelled examples are used to build the final semi-supervised classifier, for which the ROC curve is obtained using the remaining unlabelled data (solid curves). Interestingly, the active-learning algorithm finds almost half of the mines while querying for labels. Due to physical limitations of the sen- sors, the rate at which mines are detected drops precipitously after approximately 90 mines are detected -- i.e., the remaining mines are poorly matched to the sensor physics.

ENERGY minimization techniques are central to many methods in computer vision and pattern recognition. Stated simply, if a task can be posed as the minimization of an energy measure, which may, for instance, be the negative logarithm of a probability or an entropy, then a variety of optimization methods may be applied to locate the solution. The solution may be a vector of parameters representing the shapes of a curve, a surface, or a volume, it may be a set of symbolic labels representing the semantic or syntactic content of a signal, or it may be a graph representing arrangement or structure. The optimization methods that can be applied to the cost function to recover the solution include gradient descent, simulated annealing, mean-field annealing, evolutionary search, and tabu search, to mention just a few. Many of the classical methods in the fields of computer vision and pattern recognitionmake use of energyminimization techniques. Familiar examples include relaxation labeling, regularization, active contours, and Markov models. More recent examples include the use of graph-cuts, spectral graph theory, and semidefinite programming. Energy minimization techniques have also been pivotal in the development of algorithms for learning, inference, and classification. One of the characteristics of this field is that it draws strongly on recent developments in other disciplines such as mathematics, statistics, operations research, biology, and economics. Moreover, the basic methodology is being developed at a great rate in these related disciplines. In this respect, energy minimization is different from other widely used techniques such as geometry or probability, where the basic methods have been available in the mathematics literature for well over 100 years. It is probably fair to say that the problems of optimization and, in particular, combinatorial optimization, are ones of a computational nature and have hence only emerged over the past few decades. Our own involvement in this field has been, in part, through a biennial series of workshops (EMMVCPR) that commenced in 1997 and which have been aimed at providing a focus for research in this area. From the interest shown in these workshops and the number of papers on the topic appearing in the main conferences (CVPR, ECCV, ICCV), it seemed to us that a special edition of IEEE Transactions on Pattern Analysis and Machine Intelligence would be both timely and valuable to the community. The call for papers was issued in mid-2001 and we received 50 papers by the deadline on 1 May 2002. Each paper was reviewed by at least three reviewers according to the standard TPAMI reviewing procedure. This meant that we needed the assistance of some 150 reviewers. By late October 2002, we had first reviews for all of the papers and met in Venice to make initial decisions. Based on the reviews, and giving authors the chance to revise their papers in the light of reviewers comments, we selected the six papers that appear in the current special section, together with three papers that will appear in a subsequent special section. The papers span a diverse set of methods and applications. The techniques covered include semidefinite programming, Markov models, and simulated annealing, while the problems addressed include deformable models, shape-from-shading, and clustering. The first regular paper in this special section is “Binary Partitioning, Perceptual Grouping, and Restoration with Semidefinite Programming” by J. Keuchel, C. Schnorr, C. Schellewald, and D. Cremers. The authors describe a new optimization method based on semidefinite programming relaxations. The method is applied to the computer vision problems of unsupervised partitioning, figure-ground discrimination, and binary restoration. The interesting feature of the proposed method is that it does not require any parameter tuning. Moreover, apart from the symmetry condition, no assumptions aremade concerning the objective criterion. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 11, NOVEMBER 2003 1361

This paper adopts a Bayesian approach to simultaneously learn both an optimal nonlinear classifier and a subset of predictor variables (or features) that are most relevant to the classification task. The approach uses heavy-tailed priors to promote sparsity in the utilization of both basis functions and features; these priors act as regularizers for the likelihood function that rewards good classification on the training data. We derive an expectation-maximization (EM) algorithm to efficiently compute a maximum a posteriori (MAP) point estimate of the various parameters. The algorithm is an extension of recent state-of-the-art sparse Bayesian classifiers, which in turn can be seen as Bayesian counterparts of support vector machines. Experimental comparisons using kernel classifiers demonstrate both parsimonious feature selection and excellent classification accuracy on a range of synthetic and benchmark data sets.

Clustering is a common unsupervised learning technique used to discover group structure in a set of data. While there exist many algorithms for clustering, the important issue of feature selection, that is, what attributes of the data should be used by the clustering algorithms, is rarely touched upon. Feature selection for clustering is difficult because, unlike in supervised learning, there are no class labels for the data and, thus, no obvious criteria to guide the search. Another important problem in clustering is the determination of the number of clusters, which clearly impacts and is influenced by the feature selection issue. In this paper, we propose the concept of feature saliency and introduce an expectation-maximization (EM) algorithm to estimate it, in the context of mixture-based clustering. Due to the introduction of a minimum message length model selection criterion, the saliency of irrelevant features is driven toward zero, which corresponds to performing feature selection. The criterion and algorithm are then extended to simultaneously estimate the feature saliencies and the number of clusters.

This paper exploits independent component analysis (ICA) to obtain transform-based compression schemes adapted to specific image classes. This adaptation results from the data-dependent nature of the ICA bases, learnt from training images. Several coder architectures are evaluated and compared, according to both standard (SNR) and perceptual (picture quality scale - PQS) criteria, on two classes of images: faces and fingerprints. For fingerprint images, our coders perform close to the well-known special-purpose wavelet-based coder developed by the FBI. For face images, our ICA-based coders clearly outperform JPEG at the low bit-rates herein considered.

This paper describes a new method for automatic estimation of the contours of the femur and of the cranial cross-section in fetal ultrasound images. Our approach can be described as a region-based maximum likelihood formulation of parametric deformable contours. This formulation provides robustness against the poor image quality, and allows simultaneous estimation of the contour parameters together with other parameters of the model. Implementation is carried out by a deterministic iterative algorithm with minimal user intervention. Experimental results testify for the very good performance of the approach.

The problem of inferring 3D orientation of a camera from video sequences has been mostly addressed by first computing correspondences of image features. This intermediate step is now seen as the main bottleneck of those approaches. In this paper, we propose a new 3D orientation estimation method for urban (indoor and outdoor) environments, which avoids correspondences between frames. The basic scene property exploited by our method is that many edges are oriented along three orthogonal directions; this is the recently introduced Manhattan world (MW) assumption. In addition to the novel adoption of the MW assumption for video analysis, we introduce the small rotation (SR) assumption, that expresses the fact that the video camera undergoes a smooth 3D motion. Using these two assumptions, we build a probabilistic estimation approach. We demonstrate the performance of our method using real video sequences.

The goal of supervised learning is to infer a functional mapping based on a set of training examples. To achieve good generalization, it is necessary to control the "complexity" of the learned function. In Bayesian approaches, this is done by adopting a prior for the parameters of the function being learned. We propose a Bayesian approach to supervised learning, which leads to sparse solutions; that is, in which irrelevant parameters are automatically set exactly to zero. Other ways to obtain sparse classifiers (such as Laplacian priors, support vector machines) involve (hyper)parameters which control the degree of sparseness of the resulting classifiers; these parameters have to be somehow adjusted/estimated from the training data. In contrast, our approach does not involve any (hyper)parameters to be adjusted or estimated. This is achieved by a hierarchical-Bayes interpretation of the Laplacian prior, which is then modified by the adoption of a Jeffreys' noninformative hyperprior. Implementation is carried out by an expectation-maximization (EM) algorithm. Experiments with several benchmark data sets show that the proposed approach yields state-of-the-art performance. In particular, our method outperforms SVMs and performs competitively with the best alternative techniques, although it involves no tuning or adjustment of sparseness-controlling hyperparameters.

This paper introduces an expectation-maximization (EM) algorithm for image restoration (deconvolution) based on a penalized likelihood formulated in the wavelet domain. Regularization is achieved by promoting a reconstruction with low-complexity, expressed in the wavelet coefficients, taking advantage of the well known sparsity of wavelet representations. Previous works have investigated wavelet-based restoration but, except for certain special cases, the resulting criteria are solved approximately or require demanding optimization methods. The EM algorithm herein proposed combines the efficient image representation offered by the discrete wavelet transform (DWT) with the diagonalization of the convolution operator obtained in the Fourier domain. Thus, it is a general-purpose approach to wavelet-based image restoration with computational complexity comparable to that of standard wavelet denoising schemes or of frequency domain deconvolution methods. The algorithm alternates between an E-step based on the fast Fourier transform (FFT) and a DWT-based M-step, resulting in an efficient iterative process requiring O(N log N) operations per iteration. The convergence behavior of the algorithm is investigated, and it is shown that under mild conditions the algorithm converges to a globally optimal restoration. Moreover, our new approach performs competitively with, in some cases better than, the best existing methods in benchmark tests.

This paper introduces an adaptive expectation-maximization (EM) algorithm for image restoration (deconvolution) formulated in the wavelet domain. The observed image is assumed to be a convolved and noisy version of the original image to be estimated. The restoration process is supported on prior knowledge about the original image, expressed in the wavelet coefficients, taking advantage of the sparsity of wavelet representations. Although similar formulations have been considered before, the resulting optimization problems have been computationally demanding and require offline tuning. The EM algorithm herein proposed combines the efficient image/signal representation offered by the discrete wavelet transform (OWT) with the diagonalization of the convolution operator provided by the discrete Fourier transform (OFT). The result is a very efficient iterative algorithm that requires D (N log N) operations per iteration. Moreover, by using a recently proposed parameter-free wavelet-domain prior, and by including the estimation of the noise variance in the EM steps, the resulting algorithm is fully data-adaptive.

In this paper we present a new deconvolution method, able to deal with noninvertible blurring functions. To avoid noise amplification, a prior model of the image to be reconstructed is used within a Bayesian framework. We use a spatially adaptive prior defined with a complex wavelet transform in order to preserve shift invariance and to better restore variously oriented features. The unknown image is estimated by an EM technique, whose E step is a Landweber update iteration, and the M step consists of denoising the image, which is achieved by wavelet coefficient thresholding. The new algorithm has been applied to high resolution satellite and aerial data, showing better performance than existing techniques when the blurring process is not invertible, like motion blur for instance.

This paper describes an expectation-maximization (EM) algorithm for wavelet-based image restoration (deconvolution). The observed image is assumed to be a convolved (e.g., blurred) and noisy version of the original image. Regularization is achieved by using a complexity penalty/prior in the wavelet domain, taking advantage of the well known sparsity of wavelet representations. The EM algorithm herein proposed combines the efficient image representation offered by the discrete wavelet transform (DWT) with the diagonalization of the convolution operator in the discrete Fourier domain. The algorithm alternates between an FFT-based E-step and a DWT-based M-step, resulting in a very efficient iterative process requiring O(N log N) operations per iteration (where N stands for the number of pixels). The algorithm, which also estimates the noise variance, is called WAFER, standing for wavelet and Fourier EM restoration. The conditions for convergence of the proposed algorithm are also presented.

There exist many approaches to clustering, but the important issue of feature selection, i.e., selecting the data attributes that are relevant for clustering, is rarely addressed. Feature selection for clustering is difficult due to the absence of class labels. We propose two approaches to feature selection in the context of Gaussian mixture-based clustering. In the first one, instead of making hard selections, we estimate feature saliencies. An expectation-maximization (EM) algorithm is derived for this task. The second approach extends Koller and Sahami’s mutual-information- based feature relevance criterion to the unsupervised case. Feature selec- tion is then carried out by a backward search scheme. This scheme can be classified as a “wrapper”, since it wraps mixture estimation in an outer layer that performs feature selection. Experimental results on synthetic and real data show that both methods have promising performance.

This paper proposes an unsupervised algorithm for learning a finite mixture model from multivariate data. The adjective "unsupervised" is justified by two properties of the algorithm: 1) it is capable of selecting the number of components and 2) unlike the standard expectation-maximization (EM) algorithm, it does not require careful initialization. The proposed method also avoids another drawback of EM for mixture fitting: the possibility of convergence toward a singular estimate at the boundary of the parameter space. The novelty of our approach is that we do not use a model selection criterion to choose one among a set of preestimated candidate models; instead, we seamlessly integrate estimation and model selection in a single algorithm. Our technique can be applied to any type of parametric mixture model for which it is possible to write an EM algorithm; in this paper, we illustrate it with experiments involving Gaussian mixtures. These experiments testify for the good performance of our approach.

Bayesian approaches to supervised learning use priors on the classifier parameters. However, few priors aim at achieving "sparse" classifiers, where irrelevant/redundant parameters are automatically set to zero. Two well-known ways of obtaining sparse classifiers are: use a zero-mean Laplacian prior on the parameters, and the "support vector machine" (SVM). Whether one uses a Laplacian prior or an SVM, one still needs to specify/estimate the parameters that control the degree of sparseness of the resulting classifiers. We propose a Bayesian approach to learning sparse classifiers which does not involve any parameters controlling the degree of sparseness. This is achieved by a hierarchical-Bayes interpretation of the Laplacian prior, followed by the adoption of a Jeffreys' non-informative hyper-prior Implementation is carried out by an EM algorithm. Experimental evaluation of the proposed method shows that it performs competitively with (often better than) the best classification techniques available.

This paper introduces multi-scale tree-based approaches to image segmentation, using Rissanen's coding theoretic minimum description length (MDL) principle to penalize overly complex segmentations. Images are modelled as Gaussian random fields of independent pixels, with piecewise constant mean and variance. This model captures variations in both intensity (mean value) and texture (variance). Segmentation thus amounts to detecting changes in the mean and/or variance. One algorithm is based on an adaptive (greedy) rectangular recursive partitioning scheme. The second algorithm is an optimally pruned "wedgelet" decorated dyadic partitioning. We compare the two schemes with an alternative constant variance dyadic CART (classification and regression tree) scheme which accounts only for variations in mean, and demonstrate their performance on SAR images.

In this paper we introduce a new sparseness inducing prior which does not involve any (hy- per)parameters that need to be adjusted or estimated. Although other applications are possi- ble, we focus here on supervised learning problems: regression and classification. Experi- ments with several publicly available benchmark data sets show that the proposed approach yields state-of-the-art performance. In particular, our method outperforms support vector machines and performs competitively with the best alternative techniques, both in terms of error rates and sparseness, although it involves no tuning or adjusting of sparseness- controlling hyper-parameters.

The sparseness and decorrelation properties of the discrete wavelet transform have been exploited to develop powerful denoising methods. However, most of these methods have free parameters which have to be adjusted or estimated. In this paper, we propose a wavelet-based denoising technique without any free parameters; it is, in this sense, a "universal" method. Our approach uses empirical Bayes estimation based on a Jeffreys' noninformative prior; it is a step toward objective Bayesian wavelet-based denoising. The result is a remarkably simple fixed nonlinear shrinkage/thresholding rule which performs better than other more computationally demanding methods.

Grouping images into (semantically) meaningful categories using low-level visual features is a challenging and important problem in content-based image retrieval. Using binary Bayesian classifiers, we attempt to capture high-level concepts from low-level image features under the constraint that the test image does belong to one of the classes. Specifically, we consider the hierarchical classification of vacation images; at the highest level, images are classified as indoor or outdoor; outdoor images are further classified as city or landscape; finally, a subset of landscape images is classified into sunset, forest, and mountain classes. We demonstrate that a small vector quantizer (whose optimal size is selected using a modified MDL criterion) can be used to model the class-conditional densities of the features, required by the Bayesian methodology. The classifiers have been designed and evaluated on a database of 6931 vacation photographs. Our system achieved a classification accuracy of 90.5% for indoor/outdoor, 95.3% for city/landscape, 96.6% for sunset/forest and mountain, and 96% for forest/mountain classification problems. We further develop a learning method to incrementally train the classifiers as additional data become available. We also show preliminary results for feature reduction using clustering techniques. Our goal is to combine multiple two-class classifiers into a single hierarchical classifier.

We focus on an interpretation of Gaussian radial basis functions (GRBF) which motivates extensions and learning strategies. Specifically, we show that GRBF regression equations naturally result from representing the input-output joint probability density function by a finite mixture of Gaussian. Corollaries of this interpretation are: some special forms of GRBF representations can be traced back to the type of Gaussian mixture used; previously proposed learning methods based on input-output clustering have a new learning; and estimation techniques for finite mixtures (namely the EM algorithm and model selection criteria) can be invoked to learn GRBF regression equations.

We describe a method for fitting mixture models to multivariate data which performs component selection and does not require external initialization. The novelty of our approach includes: an MML-like (minimum message length) model selection criterion; inclusion of the criterion into the expectation-maximization (EM) algorithm (increasing its ability to escape from local maxima); an initialization strategy supported on the interpretation of EM as a self-annealing algorithm.

Describes an approach to the analysis of Poisson point processes, in time (1D) or space (2D), which is based on the minimum description length (MDL) framework. Specifically, we describe a fully unsupervised recursive segmentation algorithm for 1D and 2D observations. Experiments illustrate the good performance of the proposed methods.

This paper describes a new approach to adaptive estimation of parametric deformable contours based on B-spline representations. The problem is formulated in a statistical framework with the likelihood function being derived from a region-based image model. The parameters of the image model, the contour parameters, and the B-spline parameterization order (i.e., the number of control points) are all considered unknown. The parameterization order is estimated via a minimum description length (MDL) type criterion. A deterministic iterative algorithm is developed to implement the derived contour estimation criterion, the result is an unsupervised parametric deformable contour: it adapts its degree of smoothness/complexity (number of control points) and it also estimates the observation (image) model parameters. The experiments reported in the paper, performed on synthetic and real (medical) images, confirm the adequate and good performance of the approach.

This paper describes novel methods for estimating piecewise homogeneous Poisson fields based on minimum description length (MDL) criteria. By adopting a coding-theoretic approach, our methods are able to adapt to the the observed field in an unsupervised manner. We present a parsing scheme based on fixed multiscale trees (binary, for 1D, quad, for 2D) and an adaptive recursive partioning algorithm, both guided by MDL criteria. Experiments show that the recursive scheme outperforms the fixed tree approaches.

This paper formulates and proposes solutions to the problem of estimating/reconstructing the absolute (not simply modulo-2pi) phase of a complex random field from noisy observations of its real and imaginary parts. This problem is representative of a class of important imaging techniques such as interferometric synthetic aperture radar, optical interferometry, magnetic resonance imaging, and diffraction tomography. We follow a Bayesian approach; then, not only a probabilistic model of the observation mechanism, but also prior knowledge concerning the (phase) image to be reconstructed, are needed. We take as prior a nonsymmetrical half plane autoregressive (NSHP AR) Gauss-Markov random field (GMRF). Based on a reduced order state-space formulation of the (linear) NSHP AR model and on the (nonlinear) observation mechanism, a recursive stochastic nonlinear filter is derived, The corresponding estimates are compared with those obtained by the extended Kalman-Bucy filter, a classical linearizing approach to the same problem. A set of examples illustrate the effectiveness of the proposed approach.

This paper describes a boundary estimation scheme based on a new adaptive approach to B-spline curve fitting. The number of control points of the spline, their locations, and the observation parameters, are all considered unknown. The optimal number of control points is estimated via a new minimum description length (MDL) type criterion. The result is an adaptive parametrically deformable contour which also estimates the observation model parameters. Experiments on synthetic and real (medical) images confirm the adequacy and good performance of the approach.

Discontinuity-preserving Bayesian image restoration typically involves two Markov random fields: one representing the image intensities/gray levels to be recovered and another one signaling discontinuities/edges to be preserved. The usual strategy is to perform joint maximum a posterori (MAP) estimation of the image and its edges, which requires the specification of priors for both fields. Instead of taking an edge prior, we interpret discontinuities (in fact their locations) as deterministic unknown parameters of the compound Gauss-Markov random field (CGMRF), which is assumed to model the intensities. This strategy should allow inferring the discontinuity locations directly from the image with no further assumptions. However, an additional problem emerges: the number of parameters (edges) is unknown. To deal with it, we invoke the minimum description length (MDL) principle; according to MDL, the best edge configuration is the one that allows the shortest description of the image and its edges. Taking the other model parameters (noise and CGMRF variances) also as unknown, we propose a new unsupervised discontinuity-preserving image restoration criterion. Implementation is carried out by a continuation-type iterative algorithm which provides estimates of the number of discontinuities, their locations, the noise variance, the original image variance, and the original image itself (restored image). Experimental results with real and synthetic images are reported.

We introduce a fully adaptive active contour model in which no parameters have to be set a priori or tuned by the user. It is based on elliptic Fourier contour description and on the minimum description length (MDL) principle. The proposed technique estimates all the observation model parameters (e.g., noise variances), the order of the contour description (number of Fourier coefficients), and the contour itself.

This paper formulates interferometric image reconstruction as a 2D absolute phase estimation problem. The original phase image is modeled as a sample of a Gauss Markov random field; the observations are the noisy in-phase (cosine) and quadrature (sine) images. The proposed solution combines features of the iterated conditional modes algorithm with nonlinear stochastic absolute phase estimation concepts. Examples of important applications are: interferometric synthetic aperture radar, optical interferometry, magnetic resonance imaging, and diffraction tomography.

Accurate and fully automatic assessment of vessel (stenoses) dimensions in angiographic images has been sought as a diagnostic tool, in particular for coronary heart disease. Here, the authors propose a new technique to estimate vessel borders in angiographic images, a necessary first step of any automatic analysis system. Unlike in previous approaches, the obtained edge estimates are not artificially smoothed; this is extremely important since quantitative analysis is the goal. Another important feature of the proposed technique is that no constant background is assumed, this making it well suited for nonsubtracted angiograms. The key aspect of the authors' approach is that continuity/smoothness constraints are not used to modify the estimates directly derived from the image (which would introduce distortion) but rather to elect (without modifying) candidate estimates. Robustness against unknown background is provided by the use a morphological edge operator, instead of some linear operator (such as a matched filter) which has to assume known background and known vessel shape.

Discontinuity-preserving Bayesian image restoration, based on Markov random fields (MRF), involves an intensity field, representing the image to be restored, and an edge (discontinuity) field. The usual strategy is to perform joint maximum a posteriori (MAP) estimation of the intensity and discontinuity fields, this requiring the specification of Bayesian priors. Departing from this approach, we interpret the discontinuity locations as deterministic unknown parameters of the intensity field. This leads to a parameter estimation problem with the important feature of having an unknown number of parameters. We introduce a discontinuity-preserving image restoration criterion (and an algorithm to implement it) based on the minimum description length (MDL) principle and built upon a compound Gauss-Markov random field (CGMRF) model; the proposed formulation does not involve the specification of a prior for the edge field which is adaptively inferred from the data.>

Sequential and parallel image restoration algorithms and their implementations on neural networks are proposed. For images degraded by linear blur and contaminated by additive white Gaussian noise, maximum a posteriori (MAP) estimation and regularization theory lead to the same high dimension convex optimization problem. The commonly adopted strategy (in using neural networks for image restoration) is to map the objective function of the optimization problem into the energy of a predefined network, taking advantage of its energy minimization properties. Departing from this approach, we propose neural implementations of iterative minimization algorithms which are first proved to converge. The developed schemes are based on modified Hopfield (1985) networks of graded elements, with both sequential and parallel updating schedules. An algorithm supported on a fully standard Hopfield network (binary elements and zero autoconnections) is also considered. Robustness with respect to finite numerical precision is studied, and examples with real images are presented.

An algorithm is introduced for discontinuity-preserving visual surface reconstruction, inspired by the formulation of the problem as the fitting of a weak membrane to the observed data. The method slowly applies the data 'force' to a weak membrane, which is allowed to tear when the tension exceeds a certain threshold. The algorithm is named simulated tearing (ST). Formally, ST is a deterministic continuation method, i.e., the problem to be solved is embedded in a family of problems, of which the first member has a simple solution. The proposed method is tested and compared with mean field annealing (MFA), using real and synthetic images. It is concluded that ST is simpler, faster, and slightly outperforms MFA. ST allows implementation based on integer arithmetic.>

A method for left ventricular contour determination in digital angiographic images is presented. The problem is formulated in a Bayesian framework, adopting as the estimation criterion the maximum a posterior probability (MAP). The true contour is modeled as a one-dimensional noncausal Gauss-Markov random field and the observed image is described as the superposition of an ideal image (deterministic function of the real contour) with white Gaussian noise. The proposed algorithm estimates simultaneously the contour and the model parameters by implementing an adaptive version of the iterated conditional modes algorithm. The convergence of this scheme is proved and its performance evaluated on both synthetic and real angiographic images. The method exhibits robustness against image artifacts and the contours obtained are considered good by expert clinicians. Being completely data-driven and fast, the proposed algorithm is suitable for routine clinical use.