To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that is adapted to metric spaces, since graph sets are not Euclidean spaces. A standard approach is to consider the Fréchet mean. In this work, we equip a set of graph with the pseudometric defined by the ℓ2 norm between the eigenvalues of their respective adjacency matrix. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems for graph-valued data. We describe an algorithm to compute an approximation to the sample Fréchet mean of a set of undirected unweighted graphs with a fixed size using this pseudometric.

We describe here the recent results of a multidisciplinary effort to design a biomarker that can actively and continuously decode the progressive changes in neuronal organization leading to epilepsy, a process known as epileptogenesis. Using an animal model of acquired epilepsy, we chronically record hippocampal evoked potentials elicited by an auditory stimulus. Using a set of reduced coordinates, our algorithm can identify universal smooth low-dimensional configurations of the auditory evoked potentials that correspond to distinct stages of epileptogenesis. We use a hidden Markov model to learn the dynamics of the evoked potential, as it evolves along these smooth low-dimensional subsets. We provide experimental evidence that the biomarker is able to exploit subtle changes in the evoked potential to reliably decode the stage of epileptogenesis and predict whether an animal will eventually recover from the injury, or develop spontaneous seizures.

In this paper we attempt to understand the success of algorithms that organize patches according to graph-based metrics. Algorithms that analyze patches extracted from images or time series have led to state-of-the art techniques for classification, denoising, and the study of nonlinear dynamics. The main contribution of this work is to provide a theoretical explanation for the above experimental observations. Our approach relies on a detailed analysis of the commute time metric on prototypical graph models that epitomize the geometry observed in general patch-graphs. We prove that a parametrization of the graph based on commute times shrinks the mutual distances between patches that correspond to rapid local changes in the signal, while the distances between patches that correspond to slow local changes expand. In effect, our results explain why the parametrization of the set of patches based on the eigenfunctions of the Laplacian can concentrate patches that correspond to rapid local changes, which would otherwise be scattered in the space of patches. While our results are based on a large sample analysis, numerical experiments on synthetic and real data indicate that the results hold for datasets that are very small in practice.

Terahertz imaging makes it possible to acquire images of objects concealed underneath clothing by measuring the radiometric temperatures of different objects on a human subject. The goal of this work is to automatically detect and segment concealed objects in broadband 0.1-1 THz images. Due to the inherent physical properties of passive terahertz imaging and associated hardware, images have poor contrast and low signal to noise ratio. Standard segmentation algorithms are unable to segment or detect concealed objects. Our approach relies on two stages. First, we remove the noise from the image using the anisotropic diffusion algorithm. We then detect the boundaries of the concealed objects. We use a mixture of Gaussian densities to model the distribution of the temperature inside the image. We then evolve curves along the isocontours of the image to identify the concealed objects. We have compared our approach with two state-of-the-art segmentation methods. Both methods fail to identify the concealed objects, while our method accurately detected the objects. In addition, our approach was more accurate than a state-of-the-art supervised image segmentation algorithm that required that the concealed objects be already identified. Our approach is completely unsupervised and could work in real-time on dedicated hardware.

We propose a new method for detecting activation in functional magnetic resonance imaging (fMRI) data. We project the fMRI time series on a low-dimensional subspace spanned by wavelet packets in order to create projections that are as non-Gaussian as possible. Our approach achieves two goals: it reduces the dimensionality of the problem by explicitly constructing a sparse approximation to the dataset and it also creates meaningful clusters allowing the separation of the activated regions from the clutter formed by the background time series. We use a mixture of Gaussian densities to model the distribution of the wavelet packet coefficients. We expect activated areas that are connected, and impose a spatial prior in the form of a Markov random field. Our approach was validated with in vivo data and realistic synthetic data, where it outperformed a linear model equipped with the knowledge of the true hemodynamic response.

Functional Magnetic Resonance Imaging (fMRI) provides an unprecedented window into the complex functioning of the human brain, typically detailing the activity of thousands of voxels during hundreds of sequential time points. Unfortunately, the interpretation of fMRI is complicated due both to the relatively unknown connection between the hemodynamic response and neural activity and the unknown spatiotemporal characteristics of the cognitive patterns themselves. Here, we use data from the Experience Based Cognition competition to compare global and local methods of prediction applying both linear and nonlinear techniques of dimensionality reduction. We build global low dimensional representations of an fMRI dataset, using linear and nonlinear methods. We learn a set of time series that are implicit functions of the fMRI data, and predict the values of these times series in the future from the knowledge of the fMRI data only. We find effective, low-dimensional models based on the principal components of cognitive activity in classically-defined anatomical regions, the Brodmann Areas. Furthermore for some of the stimuli, the top predictive regions were stable across subjects and episodes, including WernickeÕs area for verbal instructions, visual cortex for facial and body features, and visual-temporal regions (Brodmann Area 7) for velocity. These interpretations and the relative simplicity of our approach provide a transparent and conceptual basis upon which to build more sophisticated techniques for fMRI decoding. To our knowledge, this is the first time that classical areas have been used in fMRI for an effective prediction of complex natural experience.

Image coding methods based on adaptive wavelet transforms and those employing zerotree quantization have been shown to be successful. We present a general zerotree structure for an arbitrary wavelet packet geometry in an image coding framework. A fast basis selection algorithm is developed; it uses a Markov chain based cost estimate of encoding the image using this structure. As a result, our adaptive wavelet zerotree image coder has a relatively low computational complexity, performs comparably to state-of-the-art image coders, and is capable of progressively encoding images.

This paper addresses the problem of detecting significant changes in fMRI time series that are correlated to a stimulus time course. This paper provides a new approach to estimate the parameters of a semiparametric generalized linear model of fMRI time series. The fMRI signal is described as the sum of two effects: a smooth trend and the response to the stimulus. The trend belongs to a subspace spanned by large scale wavelets. The wavelet transform provides an approximation to the Karhunen-Loève transform for the long memory noise and we have developed a scale space regression that permits to carry out the regression in the wavelet domain while omitting the scales that are contaminated by the trend. In order to demonstrate that our approach outperforms the state-of-the art detrending technique, we evaluated our method against a smoothing spline approach. Experiments with simulated data and experimental fMRI data, demonstrate that our approach can infer and remove drifts that cannot be adequately represented with splines.

We explore a new paradigm for the analysis of event-related functional magnetic resonance images (fMRI) of brain activity. We regard the fMRI data as a very large set of time series x(i) (t), indexed by the position i of a voxel inside the brain. The decision that a voxel i(o) is activated is based not solely on the value of the fMRI signal at i(o), but rather on the comparison of all time series x(i) (t) in a small neighborhood Wi(o) around i(o). We construct basis functions on which the projection of the fMRI data reveals the organization of the time series x(i) (t) into activated and nonactivated clusters. These clustering basis functions are selected from large libraries of wavelet packets according to their ability to separate the fMRI time series into the activated cluster and a nonactivated cluster. This principle exploits the intrinsic spatial correlation that is present in the data. The construction of the clustering basis functions described in this paper is applicable to a large category of problems where time series are indexed by a spatial variable.

The goal of this work is twofold. First, we demonstrate that an advantage can be gained by using local cosine bases over wavelets to encode images that contain periodic textures. We designed a coder that outperforms one of the best wavelet coders on a large number of images. The coder finds the optimal segmentation of the image in terms of local cosine bases. The coefficients are encoded using a scalar quantizer optimized for Laplacian distributions. This new coder constitutes the first concrete contribution of the paper. Second, we used our coder to perform an extensive comparison of several optimized bells in terms of rate-distortion and visual quality for a large collection of images. This study provides for the first time a rigorous evaluation in realistic conditions of these bells. Our experiments show that bells that are designed to reproduce exactly polynomials of degree 1 resulted in the worst performance in terms of the PSNR. However, a visual inspection of the compressed images indicates that these bells often provide reconstructed images with very few visual artifacts, even at low bit rates. The bell with the most narrow Fourier transform gave the best results in terms of the PSNR on most images. This bell tends however to create annoying visual artifacts in very smooth regions at low bit rate.

The main contribution of this work is a new paradigm for image representation and image compression. We describe a new multilayered representation technique for images. An image is parsed into a superposition of coherent layers: piecewise smooth regions layer, textures layer, etc. The multilayered decomposition algorithm consists in a cascade of compressions applied successively to the image itself and to the residuals that resulted from the previous compressions. During each iteration of the algorithm, we code the residual part in a lossy way: we only retain the most significant structures of the residual part, which results in a sparse representation. Each layer is encoded independently with a different transform, or basis, at a different bitrate, and the combination of the compressed layers can always be reconstructed in a meaningful way. The strength of the multilayer approach comes from the fact that different sets of basis functions complement each others: some of the basis functions will give reasonable account of the large trend of the data, while others will catch the local transients, or the oscillatory patterns. This multilayered representation has a lot of beautiful applications in image understanding, and image and video coding. We have implemented the algorithm and we have studied its capabilities.

This work provides a new approach to estimate the parameters of a semi-parametric generalized linear model in the wavelet domain. The method is illustrated with the problem of detecting significant changes in fMRI signals that are correlated to a stimulus time course. The fMRI signal is described as the sum of two effects: a smooth trend and the response to the stimulus. The trend belongs to a subspace spanned by large scale wavelets. We have developed a scale space regression that permits us to carry out the regression in the wavelet domain while omitting the scales that are contaminated by the trend. Experiments with fMRI data demonstrate that our approach can infer and remove drifts that cannot be adequately represented with low degree polynomials. Our approach results in a noticeable improvement by reducing the false positive rate and increasing the true positive rate.

The goal of this work is twofold. First, we demonstrate that an advantage can be gained by using local cosine bases to encode images that contain periodic textures. We designed a coder that outperforms a wavelet coder on a large number of images. This new coder constitutes the first contribution of the paper. Second, we used our coder to compare the performance of several optimized bells in terms of rate-distortion for a large collection of images.

In this paper, work on a new wavelet packet basis selection paradigm is reported which emphasizes the crucial role of the quantization strategy being used. This paradigm is coupled with a new Markov chain based estimation of the cost of zerotree quantization to develop a progressive wavelet packet image coder which gives better results than its wavelet counterpart.

Compression is a relatively new introduced technique for seismic data operations. The main drive behind the use of data compression in seismic data is the very large size of seismic data acquired. Some of the most recent acquired marine seismic data sets exceed 10 Tbytes, and in fact there are currently seismic surveys planned with a volume of around 120 Tbytes. Thus, the need to compress these very large seismic data files is imperative. Nevertheless, seismic data are quite different from the typical images used in image processing and multimedia applications. Some of their major differences are the data dynamic range exceeding 100 dB in theory, very often it is data with extensive oscillatory nature, the x and y directions represent different physical meaning, and there is significant amount of coherent noise which is often present in seismic data. Up to now some of the algorithms used for seismic data compression were based on some form of wavelet or local cosine transform, while using a uniform or quasiuniform quantization scheme and they finally employ a Huffman coding scheme. Using this family of compression algorithms we achieve compression results which are acceptable to geophysicists, only at low to moderate compression ratios. For higher compression ratios or higher decibel quality, significant compression artifacts are introduced in the reconstructed images, even with high-dimensional transforms. The objective of this paper is to achieve higher compression ratio, than achieved with the wavelet/uniform quantization/Huffman coding family of compression schemes, with a comparable level of residual noise. The goal is to achieve above 40 dB in the decompressed seismic data sets. Several established compression algorithms are reviewed, and some new compression algorithms are introduced. All of these compression techniques are applied to a good representation of seismic data sets, and their results are documented in this paper. One of the conclusions is that adaptive multiscale local cosine transform with different windows sizes performs well on all the seismic data sets and outperforms the other methods from the SNR point of view. All the described methods cover wide range of different data sets. Each data set will have his own best performed method chosen from this collection. The results were performed on four different seismic data sets. Special emphasis was given to achieve faster processing speed which is another critical issue that is examined in the paper. Some of these algorithms are also suitable for multimedia type compression.

Wavelets are ill-suited to represent oscillatory patterns: rapid variations of intensity can only be described by the small scale wavelet coefficients, which are often quantized to zero, even at high bit rates. Our goal is to provide a fast numerical implementation of the best wavelet packet algorithm in order to demonstrate that an advantage can be gained by constructing a basis adapted to a target image. Emphasis is placed on developing algorithms that are computationally efficient. We developed a new fast two-dimensional (2-D) convolution decimation algorithm with factorized nonseparable 2-D filters. The algorithm is four times faster than a standard convolution-decimation. An extensive evaluation of the algorithm was performed on a large class of textured images. Because of its ability to reproduce textures so well, the wavelet packet coder significantly out performs one of the best wavelet coder on images such as Barbara and fingerprints, both visually and in term of PSNR.

Wavelet packets are an effective representation tool for adaptive waveform analysis of a given signal. We first combine the wavelet packet representation with zerotree quantization for image coding. A general zerotree structure is defined which can adapt itself to any arbitrary wavelet packet basis. We then describe an efficient coding algorithm based on this structure. Finally, the hypothesis for prediction of coefficients from coarser scale to finer scale is tested and its effectiveness is compared with that of zerotree hypothesis for wavelet coefficients.

Summary form only given. Presents a new fast wavelet packet compression algorithm that encodes very efficiently textured images. This fast wavelet packet compression technique relies on four stages: 1. Very fast convolution and decimation of the image with factorized filters. 2. Selection of a best basis in a large library of waveforms. The best basis is that basis which is best adapted to the content of the image. 3. Scanning of the wavelet packet coefficients by increasing frequency. This organization yields sequences of coefficients with a rapid decay. 4. Successive embedded approximation quantization, and entropy coding of the coefficients. We implemented the wavelet packet coder and decoder, and actual bit streams were created for each experiment. Our implementation used the 7-9 biorthogonal filters. We present the results of the algorithm, using the test image 512 x 512 Barbara. In order to evaluate the performance of the algorithm, we compared our algorithm to the SPIHT wavelet coder of Said and Pearlman (1996).

We describe a new multi-layered representation technique for images. An image is encoded as the superposition of one main approximation, and a sequence of residuals. The strength of the multi-layered method comes from the fact that we use different bases to encode the main approximation and the residuals. The different bases complement each others: some of the basis functions will give reasonable account of the large trend of the data, while others will catch the local transients, or the oscillatory patterns. By selecting different bases, we allow different features to be discovered in the image.

We construct a new algorithm for motion compensation of wavelet coefficients. The new approach outperforms standard block matching techniques both in terms of higher PSNR, and better perceptual quality. The algorithm works directly in the wavelet coefficients domain and has been successfully used for wavelet based very low bit rate video coding.

We have addressed the problem of tracking the non-rigid motion of the heart using a sequence of velocity fields and a sequence of contours. The information from both the contours and the dense velocity fields is integrated into a deforming mesh that is placed over the myocardium at one time frame and then tracked over the entire cardiac cycle. The deformation is guided by a smoothing filter that provides a compromise between (i) believing the dense field velocity and the contour data when it is crisp and coherent in a local spatial and temporal sense and (ii) employing a temporally smooth cyclic model of cardiac motion when contour and velocity data are not trustworthy. The method has been carefully evaluated with simulated data and phantom data. Experiments with in vivo data have also been conducted.

We construct a new adaptive basis that provides precise frequency localization and good spatial localization. We develop a compression algorithm that exploits this basis to obtain the most economical representation of an image in terms of textured patterns with different orientations, frequencies, sizes, and positions. The technique directly works in the Fourier domain and has potential applications for compression of richly textured images.

The authors propose a new approach for tracking the deformation of the left-ventricular (LV) myocardium from two-dimensional (2-D) magnetic resonance (MR) phase contrast velocity fields. The use of phase contrast MR velocity data in cardiac motion problems has been introduced by others (N.J. Pelc et al., 1991) and shown to be potentially useful for tracking discrete tissue elements, and therefore, characterizing LV motion. However, the authors show here that these velocity data: 1) are extremely noisy near the LV borders; and 2) cannot alone be used to estimate the motion and the deformation of the entire myocardium due to noise in the velocity fields. In this new approach, the authors use the natural spatial constraints of the endocardial and epicardial contours, detected semiautomatically in each image frame, to help remove noisy velocity vectors at the LV contours. The information from both the boundaries and the phase contrast velocity data is then integrated into a deforming mesh that is placed over the myocardium at one time frame and then tracked over the entire cardiac cycle. The deformation is guided by a Kalman filter that provides a compromise between 1) believing the dense field velocity and the contour data when it is crisp and coherent in a local spatial and temporal sense and 2) employing a temporally smooth cyclic model of cardiac motion when contour and velocity data are not trustworthy. The Kalman filter is particularly well suited to this task as it produces an optimal estimate of the left ventricle's kinematics (in the sense that the error is statistically minimized) given incomplete and noise corrupted data, and given a basic dynamical model of the left ventricle. The method has been evaluated with simulated data; the average error between tracked nodes and theoretical position was 1.8% of the total path length. The algorithm has also been evaluated with phantom data; the average error was 4.4% of the total path length. The authors show that in their initial tests with phantoms that the new approach shows small, but concrete improvements over previous techniques that used primarily phase contrast velocity data alone. They feel that these improvements will be amplified greatly as they move to direct comparisons in in vivo and three-dimensional (3-D) datasets.

A framework for tracking pointwise periodic non-rigid motion of the heart's left ventricular (LV) wall is presented which incorporates information from two different magnetic resonance imaging (MRI) techniques. New developments in phase-contrast cine MR imaging have produced spatial maps of instantaneous velocity that heave proven accuracy within the myocardium, or wall, of the heart. This information is combined with shape-based matching techniques to provide improved estimates of trajectories, especially in regions where shape information is limited. These raw trajectories act as input to a recursive least squares (RLS) filter which applies the constraints of temporal periodicity and spatial smoothness for the final estimate. The results of the RLS filter are compared with the motion of actual implanted markers. Comparisons are also made between exclusively shape-based filtered and phase-contrast enhanced trajectory estimates using both phantom and actual canine heart MR images.>

This paper describes a new approach to track complex primitives along image sequences - integrating snake-based contour tracking and region-based motion analysis. First, a snake tracks the region outline and performs segmentation. Then the motion of the extracted region is estimated by a dense analysis of the apparent motion over the region, using spatio-temporal image gradients. Finally, this motion measurement is filtered to predict the region location in the next frame, and thus to guide (i.e. to initialize) the tracking snake in the next frame. Therefore, these two approaches collaborate and exchange information to overcome the limitations of each of them. The method is illustrated by experimental results on real images.

Time-to-collision provides vital information for obstacle avoidance and for the visual navigation of a robot. The original contribution of this paper is to demonstrate with sequences of real images that time-to-collision can be robustly and accurately recovered with a single calibrated camera, using first order models of the motion field.>

The problem of establishing trajectories of objects in a long image sequence is addressed, in the case of occlusion, disocclusion of objects, and crossing trajectories and junctions. Two complementary criteria are investigated in order to arrive at the decision of linking two partial pieces of trajectory which could come from a single object in motion, i.e., the continuity of the global trajectory, and the continuity of the velocity of the moving object. Experiments are conducted on long sequences of real images. Complete trajectories are successfully recovered.>

Addresses the problem of estimating time-to-collision maps involving all the objects in relative motion with respect to the camera. The approach only takes into account normal flows. Moreover the authors prove that first-order visual motion models are sufficient to obtain time-to-collision. Experiments have been carried out on real images to validate the performance of the method.>