Compressed sensing, which involves reconstruction of sparse signals from an under-determined linear system, has been recently applied to problems in group testing to save on the number of tests administered during a pandemic or other resource-constrained scenarios. In practical group testing in time-constrained situations, the results of two different groups can sometimes be mistakenly exchanged by a technician. This is called ‘permutation noise’ and it presents challenges in determining the signal vector containing p health status values of the participating subjects from the results on n ≪ p pooled tests. In this paper, we present a method to determine the health status values in a manner that is robust to a small number of such permutations. The technique is based on a ‘debiased’ form of the robust LASSO estimator, with which we carefully design hypothesis tests in order (i) to identify the unhealthy subjects (based on non-zero values in the health status signal vector), and (ii) to identify the pooled measurements which were corrupted by permutation noise. Furthermore, we present an algorithm to correct the permutations in the pooled tests and subsequently reconstruct the signal vector from the corrected measurements. We further provide empirical results showing the efficacy of both the identification and correction of permutation errors, and show that it is superior to many intuitive baseline techniques.

This study presents a technique for 2D tomography under unknown viewing angles when the distribution of the viewing angles is also unknown. Unknown view tomography (UVT) is a problem encountered in cryo-electron microscopy and in the geometric calibration of CT systems. There exists a moderate-sized literature on the 2D UVT problem, but most existing 2D UVT algorithms assume knowledge of the angle distribution which is not available usually. Our proposed methodology formulates the problem as an optimization task based on cross-validation error, to estimate the angle distribution jointly with the underlying 2D structure in an alternating fashion. We explore the algorithm’s capabilities for the case of two probability distribution models: a semi-parametric mixture of von Mises densities and a probability mass function model. We evaluate our algorithm’s performance under noisy projections using a PCAbased denoising technique and Graph Laplacian Tomography (GLT) driven by order statistics of the estimated distribution, to ensure near-perfect ordering, and compare our algorithm to intuitive baselines.

In this study, we consider a variant of unlabelled sensing where the measurements are sparsely permuted, and additionally, a few correspondences are known. We present an estimator to solve for the unknown vector. We derive a theoretical upper bound on the ℓ2reconstruction error of the unknown vector. Through numerical experiments, we demonstrate that the additional known correspondences result in a significant improvement in the reconstruction error. Additionally, we compare our estimator with the classical robust regression estimator and we find that our method outperforms it on the normalized reconstruction error metric by up to 20% in the high permutation regimes (> 30%). Lastly, we showcase the practical utility of our framework on a non-rigid motion estimation problem. We show that using a few manually annotated points along point pairs with the key-point (SIFT-based) descriptor pairs with unknown or incorrectly known correspondences can improve motion estimation.

Vintage videos, as well as modern day videos acquired at high frame rates, suffer from a visually disturbing artifact called flicker, which is the rapid change in average intensity across consecutive frames. Vintage videos also suffer from blotch artifacts, i.e., each video frame contains small regions at random locations with undefined pixel values. We present a model-based learning approach to remove flicker as well as blotches simultaneously. Our work uses a pixel-wise affine intensity model for flicker between neighboring frames, with coefficients that vary smoothly in the spatial sense but randomly across time. Due to smooth spatial variation, the flicker coefficients for any given frame can be modelled as linear combinations of low-frequency discrete cosine transform (DCT) bases. We also model blotches as heavy-tailed but sparse artifacts affecting every frame. We then present a novel framework to restore the video frames by jointly estimating the blotches as well as the DCT coefficients of the flicker via convex optimization. Given the high computational cost of the optimization-based method for processing an entire video, we use a deep unrolled neural network approach to achieve similar restoration quality at significantly reduced cost. Our approach is completely unsupervised and model-based, and hence simple and interpretable. It produces high-quality reconstructions, in terms of visual appeal as well as numerical metrics, on a variety of vintage videos as well as high-speed videos. It does not suffer from generalization issues unlike some recent state-of-the-art supervised methods which use end-to-end neural networks for restoration.

Videos shot by laymen using hand-held cameras contain undesirable shaky motion. Estimating the global motion between successive frames, in a manner not influenced by moving objects, is central to many video stabilization techniques, but poses significant challenges. A large body of work uses 2D affine transformations or homography for the global motion. However, in this work, we introduce a more general representation scheme, which adapts any existing optical flow network to ignore the moving objects and obtain a spatially smooth approximation of the global motion between video frames. We achieve this by a knowledge distillation approach, where we first introduce a low pass filter module into the optical flow network to constrain the predicted optical flow to be spatially smooth. This becomes our student network, named as GlobalFlowNet. Then, using the original optical flow network as the teacher network, we train the student network using a robust loss function. Given a trained GlobalFlowNet, we stabilize videos using a two stage process. In the first stage, we correct the instability in affine parameters using a quadratic programming approach constrained by a user-specified cropping limit to control loss of field of view. In the second stage, we stabilize the video further by smoothing global motion parameters, expressed using a small number of discrete cosine transform coefficients. In extensive experiments on a variety of different videos, our technique outperforms state of the art techniques in terms of subjective quality and different quantitative measures of video stability. Additionally, we present a new measure for evaluation of video stabilization based on the flow generated by GlobalFlowNet and argue that it is based on a more general motion model in contrast to the affine motion model on which most existing measures are based. The source code is publicly available at https://github.com/GlobalFlowNet/GlobalFlowNet

Group testing can save testing resources in the context of the ongoing COVID-19 pandemic. In group testing, we are given n samples, one per individual, and arrange them into m < n pooled samples, where each pool is obtained by mixing a subset of the n individual samples. Infected individuals are then identified using a group testing algorithm. In this paper, we use side information (SI) collected from contact tracing (CT) within nonadaptive/single-stage group testing algorithms. We generate data by incorporating CT SI and characteristics of disease spread between individuals. These data are fed into two signal and measurement models for group testing, where numerical results show that our algorithms provide improved sensitivity and specificity. While Nikolopoulos et al. utilized family structure to improve nonadaptive group testing, ours is the first work to explore and demonstrate how CT SI can further improve group testing performance.

Compressed Sensing assumes a linear model for acquiring signals however imperfections may arise in the specification of the ‘ideal’ measurement model. We present the first study which considers the case of two such common calibration issues: (a) unknown measurement scaling (sensor gains) due to hardware vagaries or due to unknown object motion in MRI scanning, in conjunction with (b) unknown offsets to measurement frequencies in case of a Fourier measurement matrix. We propose an alternating minimisation algorithm for on-the-fly signal recovery in the case when errors (a) and (b) occur jointly. We show simulation results over a variety of situations that outperform the baselines of signal recovery by ignoring either or both types of calibration errors. We also show theoretical results for signal recovery by introducing a perturbed version of the well-known Generalized Multiple Measurement Vectors (GMMV) model.

Brain neural connectivity patterns are increasingly analyzed with diffusion magnetic resonance imaging (dMRI) via the estimation of local fiber-tract orientations. High angular resolution diffusion imaging (HARDI), a variant of dMRI, is known to produce better representation of fiber orientations than the traditionally used diffusion tensor imaging (DTI). However, it requires a large number of samples leading to longer scan times. In this paper, we propose a new method, namely, MSR-HARDI, for the accelerated reconstruction of HARDI data using multiple sparsity regularizers in the k - q space. Combination of regularizers is observed to provide improved reconstructions as compared to individual regularizers. The proposed method is also observed to provide better reconstruction than the existing state-of-the-art methods in terms of the normalized mean squared error.

Consider a scene submerged underneath a fluctuating water surface. Images of such a scene, when acquired from a camera in the air, exhibit significant spatial distortions. In this paper, we present a novel, computationally efficient pre-processing algorithm to correct a significant amount (≈ 50%) of apparent distortion present in video sequences of such a scene. We demonstrate that when the partially restored video output from this stage is given as input to other methods, it significantly improves their performance. This algorithm involves (i) tracking a small number N of salient feature points across the T frames to yield point-trajectories {qi=Δ{(xit, yit)}t=1T}i=1N, and (ii) using the point-trajectories to infer the deformations at other non-tracked points in every frame. A Fourier decomposition of the N trajectories, followed by a novel Fourier phase-interpolation step, is used to infer deformations at all other points. Our method exploits the inherent spatio-temporal characteristics of the fluctuating water surface to correct non-rigid deformations to a very large extent. The source code, datasets and supplemental material can be accessed at [1], [2].

Images of static scenes submerged beneath a wavy water surface exhibit severe non-rigid distortions. The physics of water flow suggests that water surfaces possess spatio-temporal smoothness and temporal periodicity. Hence they possess a sparse representation in the 3D discrete Fourier (DFT) basis. Motivated by this, we pose the task of restoration of such video sequences as a compressed sensing (CS) problem. We begin by tracking a few salient feature points across the frames of a video sequence of the submerged scene. Using these point trajectories, we show that the motion fields at all other (non-tracked) points can be effectively estimated using a typical CS solver. This by itself is a novel contribution in the field of non-rigid motion estimation. We show that this method outperforms state of the art algorithms for underwater image restoration. We further consider a simple optical flow algorithm based on local polynomial expansion of the image frames (PEOF). Surprisingly, we demonstrate that PEOF is more efficient and often outperforms all the state of the art methods in terms of numerical measures. Finally, we demonstrate that a two-stage approach consisting of the CS step followed by PEOF much more accurately preserves the image structure and improves the (visual as well as numerical) video quality as compared to just the PEOF stage. The source code, datasets and supplemental material can be accessed at \cite{GitRepo}, \cite{ProjectPage}.

In this paper, we consider the problem of nonlinear blind compressed sensing, i.e. jointly estimating the sparse codes and sparsity-promoting basis, under signal-dependent noise. We focus our efforts on the Poisson noise model, though other signal-dependent noise models can be considered. By employing a well-known variance stabilizing transform such as the Anscombe transform, we formulate our task as a nonlinear least squares problem with the ℓ1penalty imposed for promoting sparsity. We solve this objective function under non-negativity constraints imposed on both the sparse codes and the basis. To this end, we propose a multiplicative update rule, similar to that used in non-negative matrix factorization (NMF), for our alternating minimization algorithm. To the best of our knowledge, this is the first attempt at a formulation for nonlinear blind compressed sensing, with and without the Poisson noise model. Further, we also provide some theoretical bounds on the performance of our algorithm.

Abnormality detection in medical images is a one-class classification problem for which typical methods use variants of kernel principal component analysis or one-class support vector machines. However, in practical deployment scenarios, many such methods are sensitive to the outliers present in the imperfectly-curated training sets. Current robust methods use heuristics for model fitting or lack formulations to leverage even a small amount of high-quality expert feedback. In contrast, we propose a novel method combining (i) robust statistical modeling, extending the multivariate generalized-Gaussian to a reproducing kernel Hilbert space, with (ii) semi-supervised learning to leverage a small expert-labeled outlier set. Results on simulated and real-world data, including endoscopy data, show that our method outperforms the state of the art in accurately detecting abnormalities.

The analysis of reconstruction errors for compressed sensing under Poisson noise is challenging due to the signal dependent nature of the noise, and also because the Poisson negative log-likelihood is not a metric. In this paper, we present error bounds for reconstruction of signals which are sparse or compressible under any given orthonormal basis, given compressed measurements corrupted by Poisson noise and acquired in a realistic physical system. The concerned optimization problem is framed based on the well-known Variance Stabilization Transforms which transform the noise to (approximately) Gaussian with a fixed variance. This problem also turns out to be convex. We demonstrate promising numerical results on signals with different sparsity, intensity levels and given different numbers of compressed measurements.

This paper presents a method for improving the recovery guarantee for signals that are sparse or compressible in some general basis (dictionary) using a splitting and reordering approach. The splitting algorithm applies existing results for dictionaries that are naturally characterized as a concatenation of two sub-parts, to arbitrary dictionaries, by devising the optimal artificially induced split in the dictionary. A complete approach is presented for partitioning arbitrary dictionaries into two parts, so as to obtain the optimal coherence bounds on recovery, along with a proof of optimality. A heuristic is provided for recursive application of the splitting algorithm to further improve upon these bounds, using a multi-way dictionary split. We analyze cases where an appropriate split in the dictionary predicts less conservative signal sparsity bounds for successful recovery than those considering the dictionary as a monolithic block. Our present work does not provide a new algorithm for sparse signal recovery but rather mines for structures in the dictionary, towards strengthening the existing coherence-based recovery bounds.

Typical methods for abnormality detection in medical images, which is a one-class classification problem, rely on kernel principal component analysis (KPCA) and its robust invariants. However, typical methods for robust KPCA appear heuristical in nature and often ignore the variances of the data along the principal modes of variation. In this paper, we propose a novel method for robust statistical learning in a reproducing kernel Hilbert space (RKHS) that relies on our extension of the multivariate generalized Gaussian distribution to RKHS. We propose novel algorithms to fit our kernel generalized Gaussian (KGG) in RKHS, using solely the Gram matrix and without the explicit lifting map. We exploit the KGG model, including mean, principal directions, and variances, for abnormality detection in medical images. The results on two large publicly available retinopathy datasets show that our method outperforms the state of the art.

Imaging techniques involve counting of photons striking a detector. Due to fluctuations in the counting process, the measured photon counts are known to be corrupted by Poisson noise. In this paper, we propose a blind dictionary learning framework for the reconstruction of photographic image data from Poisson corrupted measurements acquired by a compressive camera. We exploit the inherent non-negativity of the data by modeling the dictionary as well as the sparse dictionary coefficients as non-negative entities, and infer these directly from the compressed measurements in a Poisson maximum likelihood framework. We experimentally demonstrate the advantage of this in situ dictionary learning over commonly used sparsifying bases such as DCT or wavelets, especially on color images.

In this paper we describe a straightforward, yet effective method of recovering angles from a set of tomographic projections when the view-angles are completely unknown. Existing works on this problem have consistently assumed availability of projections from a large number of angles as well as made assumptions on the underlying distribution of angles to aid reconstruction. We make no such assumptions, and yet show a principled technique which is empirically validated, and quite robust to noise.

The method of coded snapshots has been proposed recently for compressive acquisition of video data to overcome the space-time trade-of inherent in video acquisition. The method involves modulation of the light entering the video camera at different time instants during the exposure period by means of a different and randomly generated code pattern at each of those time instants, followed by integration across time, leading to a single coded snapshot image. Given this image and knowledge of the random codes, it is possible to reconstruct the underlying video frames - by means of sparse coding on a suitably learned dictionary. In this paper, we apply a modified version of this idea, proposed formerly in the compressive sensing literature, to the task of compression of videos and light-field data. At low bit rates, we demonstrate markedly better reconstruction fidelity for the same storage costs, in comparison to JPEG2000 and MPEG-4 (H.264) on light-field and video data respectively. Our technique can cope with overlapping blocks of image data, thereby leading to suppression of block artifacts.