We investigate multi-task learning (MTL), where multiple learning tasks are performed jointly rather than separately to leverage their similarities and improve performance. We focus on the federated multi-task linear regression setting, where each machine possesses its own data for individual tasks and sharing the full local data between machines is prohibited. Motivated by graph regularization, we propose a novel fusion framework that only requires a one-shot communication of local estimates. Our method linearly combines the local estimates to produce an improved estimate for each task, and we show that the ideal mixing weight for fusion is a function of task similarity and task difficulty. A practical algorithm is developed and shown to significantly reduce mean squared error (MSE) on synthetic data, as well as improve performance on an income prediction task where the real-world data is disaggregated by race.

We present a neural-network-based architecture for 3D point cloud denoising called neural projection denoising (NPD). In our previous work, we proposed a two-stage denoising algorithm, which first estimates reference planes and follows by projecting noisy points to estimated reference planes. Since the estimated reference planes are inevitably noisy, multi-projection is applied to stabilize the denoising performance. NPD algorithm uses a neural network to estimate reference planes for points in noisy point clouds. With more accurate estimations of reference planes, we are able to achieve better denoising performances with only one-time projection. To the best of our knowledge, NPD is the first work to denoise 3D point clouds with deep learning techniques. To conduct the experiments, we sample 40000 point clouds from the 3D data in ShapeNet to train a network and sample 350 point clouds from the 3D data in ModelNet10 to test. Experimental results show that our algorithm can estimate normal vectors of points in noisy point clouds. Comparing to five competitive methods, the proposed algorithm achieves better denoising performance and produces much smaller variances. Our code is available at https://github.com/chaojingduan/Neural-Projection.

Product graphs are a useful way to model richer forms of graph-structured data that can be multi-modal in nature. In this work, we study the reconstruction or estimation of smooth signals on product graphs from noisy measurements. We motivate and present representations and algorithms that exploit the inherent structure in product graphs for better and more computationally efficient recovery. These contributions stem from the key insight that smooth graph signals on product graphs can be structured as low-rank tensors. We develop and present algorithms primarily based on two approaches, the first of which is the Tucker decomposition for tensors, while the second is a flexible convex optimization formulation. We further present numerical experiments that exhibit the superior performance of these methods with respect to existing methods for smooth signal recovery on graphs.

In this paper, we study the denoising of piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness over a graph. We extend the graph trend filtering framework to a family of nonconvex regularizers that exhibit superior recovery performance over existing convex ones. We present theoretical results in the form of asymptotic error rates for both generic and specialized graph models. We further present an ADMM-based algorithm to solve the proposed optimization problem and analyze its convergence. Numerical performance of the proposed framework with non-convex regularizers on both synthetic and real-world data are presented for denoising, support recovery, and semi-supervised classification.

In this paper, we introduce a generalized value iteration network (GVIN), which is an end-to-end neural network planning module. GVIN emulates the value iteration algorithm by using a novel graph convolution operator, which enables GVIN to learn and plan on irregular spatial graphs. We propose three novel differentiable kernels as graph convolution operators and show that the embedding-based kernel achieves the best performance. Furthermore, we present episodic Q-learning, an improvement upon traditional n-step Q-learning that stabilizes training for VIN and GVIN. Lastly, we evaluate GVIN on planning problems in 2D mazes, irregular graphs, and real-world street networks, showing that GVIN generalizes well for both arbitrary graphs and unseen graphs of larger scaleand outperforms a naive generalization of VIN (discretizing a spatial graph into a 2D image).

Research in graph signal processing (GSP) aims to develop tools for processing data defined on irregular graph domains. In this paper, we first provide an overview of core ideas in GSP and their connection to conventional digital signal processing, along with a brief historical perspective to highlight how concepts recently developed in GSP build on top of prior research in other areas. We then summarize recent advances in developing basic GSP tools, including methods for sampling, filtering, or graph learning. Next, we review progress in several application areas using GSP, including processing and analysis of sensor network data, biological data, and applications to image processing and machine learning.

To reduce storage and computational cost for processing and visualizing large-scale 3D point clouds, an efficient resampling strategy is needed to select a representative subset of 3D points that can preserve contours in the original 3D point cloud. We tackle this problem by using graph-based techniques as graphs can represent underlying surfaces and lend themselves well to efficient computation. We first construct a general graph for a 3D point cloud and then propose a graph-based metric to quantify the contour information via high-pass graph filtering. Finally, we obtain an optimal resampling distribution that preserves the contour information by solving an optimization problem. When browsing, the proposed graph-based resampling performs better than uniform resampling both for toy point clouds as well as real large-scale point clouds. Furthermore, as neither mesh construction nor surface normal calculation is involved, the proposed graph-based method is computationally more efficient than the mesh-based methods.

This paper presents the author's personal path through the signal representations of the past three decades, from the early days and excitement that surrounded the advent of wavelets and associated multiresolution representations, to the present day foray into graph signal processing and data mining. It is a tribute to Dr. John Cozzens of the NSF and his vision and support for the development of the field.

We consider a problem of localizing the destination of an activated path signal supported on a graph. An “activated path signal” is a graph signal that evolves over time that can be viewed as the trajectory of a moving agent. We show that by combining dynamic programming and graph partitioning, the computational complexity of destination localization can be significantly reduced. Then, we show that the destination localization error can be upper-bounded using methods based on large-deviation. Using simulation results, we show a tradeoff between the destination localization error and the computation time. We compare the dynamic programming algorithm with and without graph partitioning and show that the computation time can be significantly reduced by using graph partitioning. The proposed technique can scale to the problem of destination localization on a large graph with one million nodes and one thousand time slots.

“Your mom made five palačinke (crêpe in Serbian), your brother ate two; how many are left for you?” For some reason, this “sweet” math got etched in my mind as one of my earliest memories. It was my dad, playing number games with me. And many others: card games, puzzles, word riddles, brainteasers, anything where you had to figure out things, he loved. Then of course, so did I.

We study representations of piecewise-smooth signals on graphs. We first define classes for smooth, piecewise-constant, and piecewise-smooth graph signals, followed by a series of multiresolution local sets to analyze those signals by implementing a multiresolution analysis on graphs. Based on these local sets, we propose local-set-based piecewise-constant and piecewise-smooth dictionaries as graph signal representations that, in spirit, resemble the classical Haar wavelet basis and are naturally localized in both graph vertex and graph Fourier domains. Moreover, they promote sparsity when representing piecewise-smooth graph signals. In the experiments, we show that local-set-based dictionaries outperform graph Fourier domain based representations when approximating both simulated and real-world graph signals.

In this paper, we consider a statistical problem of learning a linear model from noisy samples. Existing work has focused on approximating the least squares solution by using leverage-based scores as an importance sampling distribution. However, no finite sample statistical guarantees and no computationally efficient optimal sampling strategies have been proposed. To evaluate the statistical properties of different sampling strategies, we propose a simple yet effective estimator, which is easy for theoretical analysis and is useful in multitask linear regression. We derive the exact mean square error of the proposed estimator for any given sampling scores. Based on minimizing the mean square error, we propose the optimal sampling scores for both estimator and predictor, and show that they are influenced by the noise-to-signal ratio. Numerical simulations match the theoretical analysis well.

We propose a sampling theory for finite-dimensional vectors with a generalized bandwidth restriction, which follows the same paradigm of the classical sampling theory. We use this general result to derive a sampling theorem for bandlimited graph signals in the framework of discrete signal processing on graphs. By imposing a specific structure on the graph, graph signals reduce to finite discrete-time or discrete-space signals, effectively ensuring that the proposed sampling theory works for such signals. The proposed sampling theory is applicable to both directed and undirected graphs, the assumption of perfect recovery is easy both to check and to satisfy, and, under that assumption, perfect recovery is guaranteed without any probability constraints or any approximation.

We present a distributed and decentralized algorithm for graph signal inpainting. The previous work obtained a closed-form solution with matrix inversion. In this paper, we ease the computation by using a distributed algorithm, which solves graph signal inpainting by restricting each node to communicate only with its local nodes. We show that the solution of the distributed algorithm converges to the closed-form solution with the corresponding convergence speed. Experiments on online blog classification and temperature prediction suggest that the convergence speed of the proposed distributed algorithm is competitive with that of the centralized algorithm, especially when a graph tends to be regular. Since a distributed algorithm does not require to collect data to a center, it is more practical and efficient.

Hyperspectral image classification is a challenging classification problem: obtaining complete and representative training sets is costly; pixels can belong to unknown classes; and it is generally an ill-posed problem. The need to achieve high classification accuracy surpasses the need to classify the entire image. To achieve this, we use classification with rejection by providing the classifier an option not to classify a pixel and consequently reject it. We propose a method for supervised hyperspectral image classification combining the use of contextual priors with classification with rejection. Rejection is introduced as an extra class that models the probability of classifier failure. We validate the resulting algorithm in the AVIRIS Indian Pines scene and illustrate the performance increase resulting from classification with rejection.

We propose a novel recovery algorithm for signals with complex, irregular structure that is commonly represented by graphs. Our approach is a generalization of the signal inpainting technique from classical signal processing. We formulate corresponding minimization problems and demonstrate that in many cases they have closed-form solutions. We discuss a relation of the proposed approach to regression, provide an upper bound on the error for our algorithm and compare the proposed technique with other existing algorithms on real-world datasets.

Super-resolution localization microscopy (SRLM) is a new imaging modality that is capable of resolving cellular structures at nanometer resolution, providing unprecedented insight into biological processes. Each SRLM image is reconstructed from a time series of images of randomly activated fluorophores that are localized at nanometer resolution and represented by clusters of particles of varying spatial densities. SRLM images differ significantly from conventional fluorescence microscopy images because of fundamental differences in image formation. Currently, however, quantitative image analysis techniques developed or optimized specifically for SRLM images are lacking, which significantly limit accurate and reliable image analysis. This is especially the case for image segmentation, an essential operation for image analysis and understanding. In this study, we propose a simple SRLM image segmentation technique based on estimating and smoothing spatial densities of fluorophores using adaptive anisotropic kernels. Experimental results showed that the proposed method provided robust and accurate segmentation of SRLM images and significantly outperformed conventional segmentation approaches such as active contour methods in segmentation accuracy.

In this work, we present a new algorithm and benchmark dataset for stain separation in histology images. Histology is a critical and ubiquitous task in medical practice and research, serving as a gold standard of diagnosis for many diseases. Automating routine histology analysis tasks could reduce health care costs and improve diagnostic accuracy. One challenge in automation is that histology slides vary in their stain intensity and color; we therefore seek a digital method to normalize the appearance of histology images. As histology slides often have multiple stains on them that must be normalized independently, stain separation must occur before normalization. We propose a new digital stain separation method for the universally-used hematoxylin and eosin stain; this method improves on the state-of-the-art by adjusting the contrast of its eosin-only estimate and including a notion of stain interaction. To validate this method, we have collected a new benchmark dataset via chemical destaining containing ground truth images for stain separation, which we release publicly. Our experiments show that our method achieves more accurate stain separation than two comparison methods and that this improvement in separation accuracy leads to improved normalization.

We propose a new mathematical and algorithmic framework for unsupervised image segmentation, which is a critical step in a wide variety of image processing applications. We have found that most existing segmentation methods are not successful on histopathology images, which prompted us to investigate segmentation of a broader class of images, namely those without clear edges between the regions to be segmented. We model these images as occlusions of random images, which we call textures, and show that local histograms are a useful tool for segmenting them. Based on our theoretical results, we describe a flexible segmentation framework that draws on existing work on nonnegative matrix factorization and image deconvolution. Results on synthetic texture mosaics and real histology images show the promise of the method.

We present a multiresolution classification framework with semi-supervised learning for the indirect structural health monitoring of bridges. The monitoring approach envisions a sensing system embedded into a moving vehicle traveling across the bridge of interest to measure the modal characteristics of the bridge. To enhance the reliability of the sensing system, we use a semi-supervised learning algorithm and a semi-supervised weighting algorithm within a multiresolution classification framework. We show that the proposed algorithm performs significantly better than supervised multiresolution classification.

We propose an automated algorithm for segmentation of mitochondria from widefield fluorescence microscopy images for quantitative morphology characterization. Mitochondria are membrane-bound organelles that are essential to cells of higher living organisms. Reliable and precise quantitative characterization of their shape is crucial to understanding related physiology and disease mechanisms. Building upon the active-mask framework developed for segmentation of confocal fluorescence microscope images, we propose a new adaptive region-based distributing function to effectively address the problem of halo artifacts that are common in widefield fluorescence images. Such artifacts prevent the segmentation of weak features of mitochondria using existing algorithms. We compare the algorithm to the original active-mask algorithm as well as the geodesic active contour algorithm based on hand-segmented ground truth, and find that it performs significantly better both qualitatively and quantitatively.

We propose an automated algorithm for classifying diagnostic categories of otitis media (middle ear inflammation); acute otitis media, otitis media with effusion and no effusion. Acute otitis media represents a bacterial superinfection of the middle ear fluid and otitis media with effusion a sterile effusion that tends to subside spontaneously. Diagnosing children with acute otitis media is hard, leading to overprescription of antibiotics that are beneficial only for children with acute otitis media, prompting a need for an accurate and automated algorithm. To that end, we design a feature set understood by both otoscopists and engineers based on the actual visual cues used by otoscopists; we term this otitis media vocabulary. We also design a process to combine the vocabulary terms based on the decision process used by otoscopists; we term this otitis media grammar. The algorithm achieves 84% classification accuracy, in the range or outperforming clinicians who did not receive special training, as well as state-of-the-art classifiers.

We present a method for identifying colitis in colon biopsies as an extension of our framework for the automated identification of tissues in histology images. Histology is a critical tool in both clinical and research applications, yet even mundane histological analysis, such as the screening of colon biopsies, must be carried out by highly-trained pathologists at a high cost per hour, indicating a niche for potential automation. To this end, we build upon our previous work by extending the histopathology vocabulary (a set of features based on visual cues used by pathologists) with new features driven by the colitis application. We use the multiple-instance learning framework to allow our pixel-level classifier to learn from image-level training labels. The new system achieves accuracy comparable to state-of-the-art biological image classifiers with fewer and more intuitive features.

We propose an algorithm for the compression of ECG signals, in particular QRS complexes, based on the expansion of signals with compact support into a basis of discrete Hermite functions. These functions are obtained by sampling continuous Hermite functions, previously used for the compression of ECG signals. Our algorithm uses the theory of signal models based on orthogonal polynomials, and achieves higher compression ratios compared with previously reported algorithms, both those using Hermite functions, as well as those using the discrete Fourier and discrete cosine transforms.

MOTIVATION: We present a framework and algorithms to intelligently acquire movies of protein subcellular location patterns by learning their models as they are being acquired, and simultaneously determining how many cells to acquire as well as how many frames to acquire per cell. This is motivated by the desire to minimize acquisition time and photobleaching, given the need to build such models for all proteins, in all cell types, under all conditions. Our key innovation is to build models during acquisition rather than as a post-processing step, thus allowing us to intelligently and automatically adapt the acquisition process given the model acquired. RESULTS: We validate our framework on protein subcellular location classification, and show that the combination of model building and intelligent acquisition results in time and storage savings without loss of classification accuracy, or alternatively, higher classification accuracy for the same total acquisition time. AVAILABILITY AND IMPLEMENTATION: The data and software used for this study will be made available upon publication at http://murphylab.web.cmu.edu/software and http://www.andrew.cmu.edu/user/jelenak/Software. CONTACT: [email protected].

We study the convergence behavior of the Active Mask (AM) framework, originally designed for segmenting punctate image patterns. AM combines the flexibility of traditional active contours, the statistical modeling power of region-growing methods, and the computational efficiency of multiscale and multiresolution methods. Additionally, it achieves experimental convergence to zero-change (fixed-point) configurations, a desirable property for segmentation algorithms. At its a core lies a voting-based distributing function which behaves as a majority cellular automaton. This paper proposes an empirical measure correlated to the convergence behavior of AM, and provides sufficient theoretical conditions on the smoothing filter operator to enforce convergence.

We propose a mathematical framework and algorithms both to build accurate models of fluorescence microscope time series, as well as to design intelligent acquisition systems based on these models. Model building allows the information contained in the 2-D and 3-D time series to be presented in a more useful and concise form than the raw image data. This is particularly relevant as the trend in biology tends more and more towards high-throughput applications, and the resulting increase in the amount of acquired image data makes visual inspection impractical. The intelligent acquisition system uses an active learning approach to choose the acquisition regions that let us build our model most efficiently, resulting in a shorter acquisition time, as well as a reduction of the amount of photobleaching and phototoxicity incurred during acquisition. We validate our methodology by modeling object motion within a cell. For intelligent acquisition, we propose a set of algorithms to evaluate the information contained in a given acquisition region, as well as the costs associated with acquiring this region in terms of the resulting photobleaching and phototoxicity and the amount of time taken for acquisition. We use these algorithms to determine an acquisition strategy: where and when to acquire, as well as when to stop acquiring. Results, both on synthetic as well as real data, demonstrate accurate model building and large efficiency gains during acquisition.

We propose a new active mask algorithm for the segmentation of fluorescence microscope images of punctate patterns. It combines the (a) flexibility offered by active-contour methods, (b) speed offered by multiresolution methods, (c) smoothing offered by multiscale methods, and (d) statistical modeling offered by region-growing methods into a fast and accurate segmentation tool. The framework moves from the idea of the "contour" to that of "inside and outside," or masks, allowing for easy multidimensional segmentation. It adapts to the topology of the image through the use of multiple masks. The algorithm is almost invariant under initialization, allowing for random initialization, and uses a few easily tunable parameters. Experiments show that the active mask algorithm matches the ground truth well and outperforms the algorithm widely used in fluorescence microscopy, seeded watershed, both qualitatively, as well as quantitatively.

We derive the Haar filter bank for 1-D space signals, based on our recently introduced framework for 1-D space signal processing, termed this way since it is built on a symmetric space shift operation in contrast to the directed time shift operation. The framework includes the proper notions of signal and filter spaces, “z-transform,” convolution, and Fourier transform, each of which is different from their time equivalents. In this paper, we extend this framework by deriving the proper notions of a Haar filter bank for space signal processing, and show that it has a similar yet different form compared to the time case. Our derivation also sheds light on the nature of filter banks and makes a case for viewing them as projections on subspaces rather than as based on filters.

We propose an algorithm for automated segmentation of white matter in brain MRI images, which can be used to create connected representations of the gray matter in the cerebral cortex of the brain. These representations then provide meaningful visualizations of brain activity data obtained from fMRI studies. Our algorithm to segment the white matter from the rest of the image is based on an active-contour scheme—STACS, and thus inherits all the advantages active-contour schemes possess. The segmentation, performed in three different planes of image capture, is driven by the statistics of the image. We combine the segmentation results from the three planes by a majority voting procedure to classify each voxel in the image as white matter or not. We improve the runtime of the algorithm by rewriting the force computation as a multiscale transformation. Initial results of labeling the white matter with an accuracy of about 89% show great promise of the proposed algorithm.

We propose a new class of equal-norm tight frames termed lapped tight frame transforms (LTFTs). These can be seen as a redundant counterpart to bases known as lapped orthogonal transforms (LOTs) introduced by Malvar and Cassereau, as well as an infinite-dimensional counterpart to harmonic tight frames (HTFs). To construct LTFTs, we seed them from LOTs and show that, in a specific case, the process preserves the equal norm. As both their basis counterpart LOTs as well as their finite-dimensional one HTFs, LTFTs possess many desirable properties, such as equal norm and efficient implementation.

I discuss the "what", "why" and "how" of reproducible research, a concept that emerged recently in computational sciences. It refers to the idea that the ultimate product is not a published paper only, but the data, software and everything else needed to produce that paper. In signal processing, the discussion just started, and this paper attempts to add to the current efforts of bringing the issue to the forefront and looking for solutions to make it happen.

We propose an adaptive multiresolution (MR) approach to the classification of fingerprint images. The system adds MR decomposition in front of a generic classifier consisting of feature computation and classification in each MR subspace, yielding local decisions, which are then combined into a global decision using a weighting algorithm. In our previous work on classification of protein subcellular location images, we showed that the space-frequency localized information in the MR subspaces adds significantly to the discriminative power of the system. Here, we go one step farther; We develop a new weighting method which allows for the discriminative power of each subband to be expressed and examined within each class. This, in turn, allows us to evaluate the importance of the information contained within a specific subband. Moreover, we develop a pruning procedure to eliminate the subbands that do not contain useful information. This leads to potential identification of the appropriate MR decomposition both on a per class basis and for a given dataset. With this new approach, we make the system adaptive, flexible as well as more accurate and efficient.

We present a method for efficient acquisition of fluorescence microscope datasets, to allow for higher spatial and temporal resolution, and with less damage from photobleaching. Our proposal is to restrict acquisition to regions where we expect to find an object. Given that the objects are continuously moving, we must have an accurate model to describe objects' motion to predict their future locations. We outline a system for learning and applying this motion model, provide details from some simple simulations, and summarize results from more complex applications.

BACKGROUND: Fluorescence microscopy is widely used to determine the subcellular location of proteins. Efforts to determine location on a proteome-wide basis create a need for automated methods to analyze the resulting images. Over the past ten years, the feasibility of using machine learning methods to recognize all major subcellular location patterns has been convincingly demonstrated, using diverse feature sets and classifiers. On a well-studied data set of 2D HeLa single-cell images, the best performance to date, 91.5%, was obtained by including a set of multiresolution features. This demonstrates the value of multiresolution approaches to this important problem. RESULTS: We report here a novel approach for the classification of subcellular location patterns by classifying in multiresolution subspaces. Our system is able to work with any feature set and any classifier. It consists of multiresolution (MR) decomposition, followed by feature computation and classification in each MR subspace, yielding local decisions that are then combined into a global decision. With 26 texture features alone and a neural network classifier, we obtained an increase in accuracy on the 2D HeLa data set to 95.3%. CONCLUSION: We demonstrate that the space-frequency localized information in the multiresolution subspaces adds significantly to the discriminative power of the system. Moreover, we show that a vastly reduced set of features is sufficient, consisting of our novel modified Haralick texture features. Our proposed system is general, allowing for any combinations of sets of features and any combination of classifiers.

One way of deriving the discrete Fourier transform (DFT) is by equispaced sampling of periodic signals or signals on a circle. In this paper, we show that an analogous derivation can be used to obtain the DCT (type 2). To achieve this goal, we replace the circle by a line graph with symmetric boundary conditions, and define signal space, filter space, and filtering operation appropriately. Further, we derive the corresponding sampling theorem including the proper notions of “bandlimited” and “sinc function.” The results show that, in a rigorous sense, the DCT is closely related to the DFT, and can be introduced without concepts from statistical signal processing as is the current practice.

We propose an adaptive multiresolution (MR) approach for classification of fluorescence microscopy images of subcellular protein locations, providing biologically relevant information. These images have highly localized features both in space and frequency which naturally leads us to MR tools. Moreover, as the goal of the classification system is to distinguish between various protein classes, we aim for features adapted to individual proteins. These two requirements further lead us to adaptive MR tools. We start with a simple classification system consisting of Haralick texture feature computation followed by a maximum-likelihood classifier, and demonstrate that, by adding an MR block in front, we are able to raise the average classification accuracy by roughly 10%. We conclude that selecting features in MR subspaces allows us to custom-build discriminative feature sets for fluorescence microscopy images of protein subcellular location images.

We characterize and design multidimensional (MD) orthogonal filter banks using special paraunitary matrices and the Cayley transform. Orthogonal filter banks are represented by paraunitary matrices in the polyphase domain. We define special paraunitary matrices as paraunitary matrices with unit determinant. We show that every paraunitary matrix can be characterized by a special paraunitary matrix and a phase factor. Therefore, the design of paraunitary matrices (and thus of orthogonal filter banks) becomes the design of special paraunitary matrices, which requires a smaller set of nonlinear equations. Moreover, we provide a complete characterization of special paraunitary matrices in the Cayley domain, which converts nonlinear constraints into linear constraints. Our method greatly simplifies the design of MD orthogonal filter banks and leads to complete characterizations of such filter banks.

Motivated by the use of frames for robust transmission over the Internet, we present a first systematic construction of real tight frames with maximum robustness to erasures. We approach the problem in steps: we first construct maximally robust frames by using polynomial transforms. We then add tightness as an additional property with the help of orthogonal polynomials. Finally, we impose the last requirement of equal norm and construct, to our best knowledge, the first real, tight, equal-norm frames maximally robust to erasures.

We propose a new method for the extraction of auditory brainstem responses (ABRs) from an EEG signal. It is based on adaptive filtering of signals in the wavelet domain, where the transform used is a nearly shift-invariant complex wavelet transform (CWT). We compare our algorithm to two existing methods. The first simply consists of bandpass filtering the input EEG signal followed by linear averaging. The second method uses signal-adaptive filtering in the Fourier domain based on phase variance computed at each spectral component of the FFT. Realistic models of EEG and ABR are generated for this comparison. Results show that the wavelet-based method consistently outperforms the other two methods for ABR signals with an initial signal-to-noise ratio less than -20 dB.

We present an algorithm for efficient acquisition of fluorescence microscopy data sets, a problem not addressed until now in the literature. We do this as part of a larger system for protein classification based on their subcellular location patterns, and thus strive to maintain the achieved level of classification accuracy as much as possible. This problem is similar to image compression but unique due to additional restrictions, namely causality; we have access only to the information that has been scanned up to that point. While we do want to acquire fewer samples with as low distortion as possible to achieve compression, our goal is to do so while affecting the overall classification accuracy as little as possible. We achieve this by using an adaptive multiresolution scanning scheme which samples the regions of the image area that hold the most pertinent information. Our results show that we can achieve significant compression which we can then use to increase either time or space resolution of our data set, all while minimally affecting the classification accuracy of the entire system.

We introduce wavelet packet correlation filter classifiers. Correlation filters are traditionally designed in the image domain by minimizing some criterion function of the image training set. Instead, we perform classification in wavelet spaces that have training set representations which provide better solutions to the optimization problem in the filter design. We propose a pruning algorithm to find these wavelet spaces using a correlation energy cost function, and we describe a match score fusion algorithm for applying the filters trained across the packet tree. The proposed classification algorithm is suitable for any object recognition task. We present results by implementing a biometric recognition system using the NIST 24 fingerprint database, and show that applying correlation filters in the wavelet domain results in considerable improvement of the standard correlation filter algorithm.

This paper proposes an encoding method for high-quality, low-delay audio communication that is robust to losses in packetized transmission. Robustness is provided by a multiple description vector quantization (MDVQ) technique that is designed to minimize the mean-squared error (MSE). The key to applying this technique effectively is the use of psycho-acoustically controlled preand post-filters that make the mean-squared quantization error perceptually relevant. Experiments show that the MDVQ-based encoder yields better results-in both MSE and subjective audio quality-than simple alternative coders with the same low delay.

We propose an algorithm for adaptive efficient acquisition of fluorescence microscopy data sets using a multirate (MR) approach. We simulate acquisition as part of a larger system for protein classification based on their subcellular location patterns and, thus, strive to maintain the achieved level of classification accuracy as much as possible. This problem is similar to image compression but unique due to additional restrictions, namely causality; we have access only to the information scanned up to that point. While we do want to acquire fewer samples with as low distortion as possible to achieve compression, our goal is to do so while affecting the overall classification accuracy as little as possible. We achieve this by using an adaptive MR scanning scheme which samples the regions of the image area that hold the most pertinent information. Our results show that we can achieve significant compression which we can then use to aquire faster or to increase space resolution of our data set, all while minimally affecting the classification accuracy of the entire system.

We present a complete characterization and design of orthogonal infinite impulse response (IIR) and finite impulse response (FIR) filter banks in any dimension using the Cayley transform (CT). Traditional design methods for one-dimensional orthogonal filter banks cannot be extended to higher dimensions directly due to the lack of a multidimensional (MD) spectral factorization theorem. In the polyphase domain, orthogonal filter banks are equivalent to paraunitary matrices and lead to solving a set of nonlinear equations. The CT establishes a one-to-one mapping between paraunitary matrices and para-skew-Hermitian matrices. In contrast to the paraunitary condition, the para-skew-Hermitian condition amounts to linear constraints on the matrix entries which are much easier to solve. Based on this characterization, we propose efficient methods to design MD orthogonal filter banks and present new design results for both IIR and FIR cases.

We study frames for robust transmission over a multiple-antenna wireless system - BLAST. By considering as erased a component received with an SNR inferior to a given threshold, we place frames in a setting where some of the elements are deleted. Goyal, Kovacevic and Kelner (see Journal of Appl. and Comput. Harmonic Analysis, vol.10, no.3, p.203-233, 2001) focused on the performance of quantized frame expansions up to M-N erased components, the structure of a frame being thus preserved. In this paper we consider every possible scenario of erasures for low-dimensional frames and we present optimal designs for corresponding systems using a small number of antennas.

A multiple description (MD) lattice vector quantization technique for two descriptions was previously introduced in which fine and coarse codebooks are both lattices. The encoding begins with quantization to the nearest point in the fine lattice. This encoding is an inherent optimization for the decoder that receives both descriptions; performance can be improved with little increase in complexity by considering all decoders in the initial encoding step. The altered encoding relies only on the symmetries of the coarse lattice. This allows us to further improve performance without a significant increase in complexity by replacing the fine lattice codebook with a nonlattice codebook that respects many of the symmetries of the coarse lattice. Examples constructed with the two-dimensional (2-D) hexagonal lattice demonstrate large improvement over time sharing between previously known quantizers.

We study frames for robust transmission over the Internet. In our previous work, we used quantized finite-dimensional frames to achieve resilience to packet losses; here, we allow the input to be a sequence in l/sub 2/(Z) and focus on a filter-bank implementation of the system. We present results in parallel, R/sup N/ or C/sup N/ versus l/sub 2/(Z), and show that uniform tight frames, as well as newly introduced strongly uniform tight frames, provide the best performance.

Oversampled filter banks can be used to enhance resilience to erasures in communication systems in much the same way that finite-dimensional frames have previously been applied. This paper extends previous finite dimensional treatments to frames and signals in l/sub 2/(Z) with frame expansions that can be implemented efficiently with filter banks. It is shown that tight frames attain best performance. In particular, if encoding with a uniform frame, the quantization error is minimized if and only if the frame is tight. In case of one erasure and if encoding with a strongly uniform frame, tight frames are still optimal. In case of more erasures, an expression for the mean square error is given and some general considerations are presented.

Multiple description (MD) coding is source coding in which several descriptions of the source are produced such that various reconstruction qualities are obtained from different subsets of the descriptions. Unlike multiresolution or layered source coding, there is no hierarchy of descriptions; thus, MD coding is suitable for packet erasure channels or networks without priority provisions. Generalizing work by Orchard, Wang, Vaishampayan and Reibman (see Proc IEEE Int. Conf. Image Processing, vol.I, Santa Barbara, CA, p.608-11, 1997), a transform-based approach is developed for producing M descriptions of an N-tuple source, M/spl les/N. The descriptions are sets of transform coefficients, and the transform coefficients of different descriptions are correlated so that missing coefficients can be estimated. Several transform optimization results are presented for memoryless Gaussian sources, including a complete solution of the N=2, M=2 case with arbitrary weighting of the descriptions. The technique is effective only when independent components of the source have differing variances. Numerical studies show that this method performs well at low redundancies, as compared to uniform MD scalar quantization.

Multiple description lattice vector quantization (MDLVQ) is a technique for two-channel multiple description coding. We observe that MDLVQ, in the form introduced by Servetto et al. (1999), is inherently optimized for the central decoder; i.e., for zero probability of a lost description. With a nonzero probability of description loss, performance is improved by modifying the encoding rule (using nearest neighbors with respect to "multiple description distance") and by perturbing the lattice codebook. The perturbation maintains many symmetries and hence does not significantly affect encoding or decoding complexity. An extension to more than two descriptions with attractive decoding properties is outlined.

In audio communication over a lossy packet network, concealment techniques are used to mitigate the effects of lost packets. This concealment is markedly improved if the compressed representation retains redundancy to aid in the estimation of lost information. A perceptual audio coder employing multiple description correlating transforms demonstrates this phenomenon.

We build discrete-time compactly supported biorthogonal wavelets and perfect reconstruction filter banks for any lattice in any dimension with any number of primal and dual vanishing moments. The associated scaling functions are interpolating. Our construction relies on the lifting scheme and inherits all of its advantages: fast transform, in-place calculation, and integer-to-integer transforms. We show that two lifting steps suffice: predict and update. The predict step can be built using multivariate polynomial interpolation, while update is a multiple of the adjoint of predict. While we concentrate on the discrete-time case, some discussion of convergence and stability issues together with examples is given.

We propose a perceptually based system for pattern retrieval and matching. The central idea is that similarity judgment has to be modeled along perceptual dimensions. Hence, we detect basic visual categories that people use in their judgment of similarity, and design a computational model that accepts patterns as input and, depending on the query, produces a set of choices that follow human behavior in pattern matching. There are two major research aspects to our work. The first one addresses the issue of how humans perceive and measure similarity within the domain of color patterns. To understand and describe this mechanism, we performed a subjective experiment which yielded five perceptual criteria used in comparison between color patterns (vocabulary), as well as a set of rules governing the use of these criteria in similarity judgment (grammar). The second research aspect is the implementation of the perceptual criteria and rules in an image retrieval system. Following the processing typical for human vision, we design a system to: (1) extract perceptual features from the vocabulary and (2) perform the comparison between the patterns according to the grammar rules. The modeling of human perception of color patterns is new--starting with a new color codebook design, compact color representation, and texture description through multi-scale edge distribution along different directions. Moreover, we propose new color and texture distance functions that correlate with human performance. The performance of the system is illustrated with numerous examples from image databases from different application domains.

We determine the basic categories and the hierarchy of rules used by humans in judging similarity and matching of color patterns. The categories are: (1) overall color; (2) directionality and orientation; (3) regularity and placement; (4) color purity; (5) complexity and heaviness. These categories form the pattern vocabulary which is governed by the grammar rules. Both the vocabulary and the grammar were obtained as a result of a subjective experiment. Experimental data were interpreted using multidimensional scaling techniques yielding the vocabulary and the hierarchical clustering analysis, yielding the grammar rules. Finally, we give a short overview of the existing techniques that can be used to extract and measure the elements of the vocabulary.

Quantized frame expansions are proposed as a method for generalized multiple description coding, where each quantized coefficient is a description. Whereas previous investigations have revealed the robustness of frame expansions to additive noise and quantization, this represents a new application of frame expansions. The performance of a system based on quantized frame expansions is compared to that of a system with a conventional block channel code. The new system performs well when the number of lost descriptions (erasures on an erasure channel) is hard to predict.

The quadtree data structure is widely used in digital image processing and computer graphics for modeling spatial segmentation of images and surfaces. A quadtree is a tree in which each node has four descendants. Since most algorithms based on quadtrees require complex navigation between nodes, efficient traversal methods as well as efficient storage techniques are of great interest. In this paper we first propose an efficient indexing scheme for a linear (pointerless) quadtree data structure. Such a quadtree is stored using a unidimensional array of nodes. Our indexing scheme has the property that the navigation between any pair of nodes can be computed in constant time. Moreover the navigation across multiple quadtrees can be achieved at the same cost. We illustrate our results on applications in computer graphics. We first show how the problem of computing a so-called restricted quadtree can be solved at optimal cost, e.g. with a computational complexity having the order of magnitude of the problem size. Then, we explain how this problem can be solved in the case of surfaces modeled using multiple quadtrees. Finally, we show how a tessellated sphere can be implemented and navigated using our data structure.

Multiple description coding (MDC) is source coding for multiple channels such that a decoder which receives an arbitrary subset of the channels may produce a useful reconstruction. Orchard et al. (1997) proposed a transform coding method for MDC of pairs of independent Gaussian random variables. This paper provides a general framework which extends multiple description transform coding (MDTC) to any number of variables and expands the set of transforms which are considered. Analysis of the general case is provided, which can be used to numerically design optimal MDTC systems. The case of two variables sent over two channels is analytically optimized in the most general setting where channel failures need not have equal probability or be independent. It is shown that when channel failures are equally probable and independent, the transforms used in Orchard et al. are in the optimal set, but many other choices are possible. A cascade structure is presented which facilitates low-complexity design, coding, and decoding for a system with a large number of variables.

We argue that Java is a natural language to develop interactive teaching material that can be shared and distributed widely. Unlike any other programming language or platform we know, Java development is justified because of its almost universal acceptance. We develop a block diagram (BD) based approach that allows one to develop interactive and downloadable signal processing laboratories. As an example, we show how specific experiments for a DSP class, as well as for an advanced course on wavelets have been developed. The article first explains why the Java language has been chosen, and then describes what has been realized today. Finally, we show how the BD representation can be efficiently used for the development of a wavelet theory course. It is shown that only a few simple blocks are sufficient for creating many didactic programs. This can be seen as an a posteriori justification of the BD model.

Generalized multiple description coding (GMDC) is source coding for multiple channels such that a decoder which receives an arbitrary subset of the channels may produce a useful reconstruction. This paper reports on applications of two recently proposed methods for GMDC to image coding. The first produces statistically correlated streams such that lost streams can be estimated from the received data. The second uses quantized frame expansions and hence is conceptually similar to block channel coding, except it is done prior to quantization.

We consider the problem of sending raw image data over lossy or heterogeneous network connections with as little overhead as possible. If the network connection does not support multiple priority levels and the network drops packets at random, a technique is needed where the data would be divided into parts of equal importance, so that the image could be at least partially reconstructed from the packets available. We found theoretical criteria for an image to be broken into pieces of equal importance, developed an algorithm for such criteria to be implemented and devised a signal processing scheme based on critically-sampled fast implementation filter banks. Experiments show that although the overhead is not large, it can further be reduced by using a scrambler. This scheme also solves the problem of holographic image representation.

We construct two-dimensional (2-D) local cosine bases in discrete time. Solutions are offered both for rectangular and nonrectangular lattices. In the case of nonrectangular lattices, the problem is solved by mapping it into a one-dimensional (1-D) equivalent problem.

We propose an algorithm for deinterlacing of interlaced video sequences. It successively builds approximations to the deinterlaced sequence by weighting various interpolation methods. A particular example given here uses four interpolation methods, weighted according to the errors each one introduces. Due to weighting, it is an adaptive algorithm. It is also time-recursive, since the motion-compensated part uses the previously interpolated frame. Furthermore, bidirectional motion estimation and compensation allow for better performance in the case of scene changes and covering/uncovering of objects. Experiments are run both on "real-world" and computer generated sequences. Finally, subjective testing is performed to evaluate the quality of the algorithm.

We show how to obtain arbitrary tilings of the time-frequency plane using local orthogonal bases. These bases were recently constructed as a generalization of the cosine-modulated filter banks in discrete time, and local sine and cosine bases in continuous time. Due to the fact that they use a single prototype window, these bases also lead to time-varying tilings. Moreover, they have a fast implementation algorithm, and allow for multidimensional irreducible basis functions. As an example, we show how to design a critical-band system for use in audio coding.

We show how to obtain arbitrary tilings of the time-frequency plane using local orthogonal bases. These bases were constructed as a generalization of the cosine-modulated filter banks in discrete time, and local trigonometric bases in continuous time. Due to the fact that they use a single prototype window, these bases also lead to time-varying tilings. Moreover, they have a fast implementation algorithm, and allow for multidimensional irreducible basis functions. We show examples of design, in particular, that of a critical-band system for use in audio coding.

We extend to more general groups a well-known relation used for checking the orthogonality of a system as well as for orthogonalizing a nonorthogonal one. This, in turn is used for designing local orthogonal bases obtained by modulations and rotations of a single prototype filter. These bases are useful for building systems for evaluating image quality.

The authors give an overview of the continuous and oversampled wavelet transform. They discuss how, by sampling the continuous wavelet transform, orthonormal wavelet bases can be obtained. Multiresolution analysis, as a framework for studying wavelet bases, is also presented. Finally, the authors deal with discrete-time wavelet representations, filter banks, and fast algorithms.

Constructs two-dimensional local cosine bases in discrete and continuous time. Solutions are offered both for rectangular and nonrectangular lattices. In the case of nonrectangular lattices, the problem is solved by mapping it into a one-dimensional equivalent problem.

Discrete-time cosine modulated filter banks, or modulated lapped transforms (MLT), have been in use for some time. Due to a few of their properties, they have become quite popular. For example, all filters (basis functions) of a filter bank are obtained by appropriate modulation of a single prototype filter. We present a new method for constructing local orthogonal bases, both in continuous and discrete time. The approach is very general and can handle a large variety of cases interesting for the applications.

A new method for dealing with the effects of quantization in a subband system is proposed. It uses the "gain plus additive noise" linear model for the Lloyd-Max quantizer. Based on this, it is demonstrated how, by an appropriate choice of synthesis filters, one can cancel all signal-dependent errors at the output of the system. The only remaining error is random in nature and not correlated with the input signal. We therefore have a tradeoff between the error being only random or having signal-dependent components as well (since the error variances in both cases are comparable). As a result of having only a random error, it is possible to reduce this error using, for example, a noise removal technique. The result is then extended to the case where the input is a multidimensional signal, and arbitrary sampling lattices are used, as well as to the QMF (alias cancellation) case. To demonstrate the validity of the proposed approach, two types of experiments on images are carried out: In a toy example, it is shown that using noise removal could be beneficial. For a more realistic coding scheme, however, it is demonstrated that even in the case when the model is no longer valid (when some of the subbands are discarded), the output error is still much less correlated with the input signal as opposed to the commonly used subband system, while visually, the reconstructed images look very similar.

Three-dimensional nonseparable perfect reconstruction filter banks using three-dimensional nonseparable sampling by two, FCO, are proposed. Filter structures are derived and applied to digital video. Separation into two bands is obtained, and it is shown to perform better from the perceptual point of view than interlaced sequences resulting from the quincunx sampling of a progressively scanned signal in time-vertical dimensions.

The design of multidimensional nonseparable wavelets based on iterated filter banks is investigated. To obtain regularity of the wavelet, a maximum number of zeros is put at aliasing frequencies in the lowpass filter. Two approaches are pursued. A direct method designs nonseparable perfect reconstruction filter banks based on cascade structures and with prescribed zeros both analytically (small cases) and numerically (larger cases). A second, indirect method maps biorthogonal one-dimensional banks with high regularity into multidimensional banks using the McClellan transformation. A number of properties relevant to perfect reconstruction and zero locations are shown in this case. Design examples are given in all cases, and the testing of regularity is discussed, together with a fast algorithm to compute iterated filters.>

New results on multidimensional filter banks and their connection to multidimensional nonseparable wavelets are presented. Among the topics discussed are sampling in multiple dimensions, multidimensional perfect reconstruction filter banks, the two-channel case in multiple dimensions, the synthesis of multidimensional filter banks, and the design of compactly supported wavelets.>

The authors present a general, direct method for designing perfect reconstruction filter banks with rational sampling rate changes. Such filter banks have N branches, each one having a sampling factor of p/sub i//q/sub i/ and their sum equal to one. A design example showing the advantage of using the direct over the indirect method is given. Due to recent results pointing to the relationship between filter banks and wavelet theory, the regularity question is addressed as well, and a regular filter is shown for a dilation factor of 3/2.>

The authors state and prove a theorem solving the problem of commutativity in two dimensions. It is shown under which conditions upsampling and downsampling can be interchanged in two dimensions. This is the generalization to arbitrary two-dimensional lattices of the result that one-dimensional upsampling and downsampling commute if and only if their sampling rates are coprime. Some illustrative examples are given. The result holds for arbitrary sampling lattices.>

Subband decomposition of HDTV signals is important both for representation purposes (to create compatible subchannels) and for coding (several proposed compression schemes include some subband division). We first review perfect reconstruction filter banks in multiple dimensions in the context of arbitrary sampling patterns. Then we concentrate on the special case of quincunx subsampling and derive filter banks to go from progressive to interlaced scanning (with a highpass which contains deinterlacing information) as well as from interlaced to progressive. We apply this decomposition to a sequence and indicate bitrates.

Lapped orthogonal transforms (LOT) have been introduced to provide a solution to the problem of blocking that occurs with transform coding at low bit rate. For the purpose of image coding, a more general class of exact reconstruction filter banks, that provides an additional degree of freedom in controlling ringing while relaxing the symmetry constraints of LOTs, is introduced. It is shown that windowed modulated filter banks are a very attractive candidate for image coding, since by allowing almost arbitrary selection of the window, they provide a control of the impulse response of the filters in the filter bank. The outputs of the windowed, modulated filter bank are quantized and entropy-coded in a way analogous to DCT (discrete cosine transform) coefficients. Comparisons are made between the filter bank and the DCT from the point of view of mean square error and subjective quality.>