Learning Sparse Overcomplete Codes for Images

Images can be coded accurately using a sparse set of vectors from a learned overcomplete dictionary, with potential applications in image compression and feature selection for pattern recognition. We present a survey of algorithms that perform dictionary learning and sparse coding and make three contributions. First, we compare our overcomplete dictionary learning algorithm (FOCUSS-CNDL) with overcomplete independent component analysis (ICA). Second, noting that once a dictionary has been learned in a given domain the problem becomes one of choosing the vectors to form an accurate, sparse representation, we compare a recently developed algorithm (sparse Bayesian learning with adjustable variance Gaussians, SBL-AVG) to well known methods of subset selection: matching pursuit and FOCUSS. Third, noting that in some cases it may be necessary to find a non-negative sparse coding, we present a modified version of the FOCUSS algorithm that can find such non-negative codings. Efficient parallel implementations in VLSI could make these algorithms more practical for many applications.

$rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation

In recent years there has been a growing interest in the study of sparse representation of signals. Using an overcomplete dictionary that contains prototype signal-atoms, signals are described by sparse linear combinations of these atoms. Applications that use sparse representation are many and include compression, regularization in inverse problems, feature extraction, and more. Recent activity in this field has concentrated mainly on the study of pursuit algorithms that decompose signals with respect to a given dictionary. Designing dictionaries to better fit the above model can be done by either selecting one from a prespecified set of linear transforms or adapting the dictionary to a set of training signals. Both of these techniques have been considered, but this topic is largely still open. In this paper we propose a novel algorithm for adapting dictionaries in order to achieve sparse signal representations. Given a set of training signals, we seek the dictionary that leads to the best representation for each member in this set, under strict sparsity constraints. We present a new method—the$ K$-SVD algorithm—generalizing the$ K$-means clustering process.$ K$-SVD is an iterative method that alternates between sparse coding of the examples based on the current dictionary and a process of updating the dictionary atoms to better fit the data. The update of the dictionary columns is combined with an update of the sparse representations, thereby accelerating convergence. The$ K$-SVD algorithm is flexible and can work with any pursuit method (e.g., basis pursuit, FOCUSS, or matching pursuit). We analyze this algorithm and demonstrate its results both on synthetic tests and in applications on real image data.     

Compression of facial images using the K-SVD algorithm

The use of sparse representations in signal and image processing is gradually increasing in the past several years. Obtaining an overcomplete dictionary from a set of signals allows us to represent them as a sparse linear combination of dictionary atoms. Pursuit algorithms are then used for signal decomposition. A recent work introduced the K-SVD algorithm, which is a novel method for training overcomplete dictionaries that lead to sparse signal representation. In this work we propose a new method for compressing facial images, based on the K-SVD algorithm. We train K-SVD dictionaries for predefined image patches, and compress each new image according to these dictionaries. The encoding is based on sparse coding of each image patch using the relevant trained dictionary, and the decoding is a simple reconstruction of the patches by linear combination of atoms. An essential pre-process stage for this method is an image alignment procedure, where several facial features are detected and geometrically warped into a canonical spatial location. We present this new method, analyze its results and compare it to several competing compression techniques.     

基于稀疏编码的鲁棒型人脸超分辨率重建

为了减少人脸超分图像的边缘伪影和图像噪点,利用基于稀疏编码的单幅图像超分辨率重建算法,在字典学习阶段,结合L1范数引入在线字典学习方法,使字典根据当前输入图像块和上次迭代生成的字典逐列更新,得到更加精确的超完备字典对,用于图像重建.实验中进行的仿真结果表明,改进算法超分结果的峰值信噪比(PSNR)和结构相似性(SSIM)比同类型的稀疏编码超分法(SCSR)和应用在线字典学习算法的超分方法(ODLSR)均有较大幅度提升,比后者平均提升0.72 dB和0.0187.同时,视觉上有效地消除了边缘伪影,且在处理含噪人脸图像时,具备更强的去噪能力和更好的鲁棒性.     

利用稳健字典学习的雷达高分辨距离像目标识别算法

基于字典学习算法的信号稀疏表示被广泛应用于信号处理领域。由于字典原子间存在冗余性,求解信号的稀疏表示会受到观测信号中扰动分量的影响,从而带来表示的不确定性,不利于雷达高分辨距离像(HRRP)目标识别任务。针对这一问题,该文提出一种稳健字典学习(SDL)算法,通过边缘化信号丢失,构建稳健损失函数用于学习自适应字典。该算法利用距离像在散射点不发生越距离单元走动的方位帧内具有结构相似性,约束临近训练样本间稀疏表示的非零元素位置相同,并通过结构化稀疏约束选择最优子字典用于测试样本的分类。基于实测HRRP数据的实验结果验证了所提算法的有效性。     

Sparse solutions to linear inverse problems with multiple measurement vectors

We address the problem of finding sparse solutions to an underdetermined system of equations when there are multiple measurement vectors having the same, but unknown, sparsity structure. The single measurement sparse solution problem has been extensively studied in the past. Although known to be NP-hard, many single-measurement suboptimal algorithms have been formulated that have found utility in many different applications. Here, we consider in depth the extension of two classes of algorithms-Matching Pursuit (MP) and FOCal Underdetermined System Solver (FOCUSS)-to the multiple measurement case so that they may be used in applications such as neuromagnetic imaging, where multiple measurement vectors are available, and solutions with a common sparsity structure must be computed. Cost functions appropriate to the multiple measurement problem are developed, and algorithms are derived based on their minimization. A simulation study is conducted on a test-case dictionary to show how the utilization of more than one measurement vector improves the performance of the MP and FOCUSS classes of algorithm, and their performances are compared.     

Sparsity in optical flow and trajectories

In this article, we apply sparse constraints to improve optical flow and trajectories. We apply sparsity in two ways. First, with two-frame optical flow, we enforce a sparse representation of flow patches using a learned overcomplete dictionary. Second, we apply a low-rank constraint to trajectories via robust coupling. Optical flow is an ill-posed underconstrained inverse problem. Many recent approaches use total variation to constrain the flow solution to satisfy color constancy. In our first results presented, we find that learning a 2D overcomplete dictionary from the total variation result and then enforcing a sparse constraint on the flow improves the result. A new technique using partially overlapping patches accelerates the calculation. This approach is implemented in a coarse-to-fine strategy. Our results show that combining total variation and a sparse constraint from a learned dictionary is more effective than total variation alone. In the second part, we compute optical flow and trajectories from an image sequence. Sparsity in trajectories is measured by matrix rank. We introduce a low-rank constraint of linear complexity using random subsampling of the data. We demonstrate that, by using a robust coupling with the low-rank constraint, our approach outperforms baseline methods on general image sequences.     

An image denoising algorithm for mixed noise combining nonlocal means filter and sparse representation technique

Nonlocal means (NLM) filtering or sparse representation based denoising method has obtained a remarkable denoising performance. In order to integrate the advantages of two methods into a unified framework, we propose an image denoising algorithm through skillfully combining NLM and sparse representation technique to remove Gaussian noise mixed with random-valued impulse noise. In the non-Gaussian circumstance, we propose a customized blockwise NLM (CBNLM) filter to generate an initial denoised image. Based on it, we classify the different noisy pixels according to the three-sigma rule. Besides, an overcomplete dictionary is trained on the initial denoised image. Then, a complementary sparse coding technique is used to find the sparse vector for each input noisy patch over the overcomplete dictionary. Through solving a more reasonable variational denoising model, we can reconstruct the clean image. Experimental results verify that our proposed algorithm can obtain the best denoising performance, compared with some typical methods.     

组合正交基字典稀疏分解快速匹配追踪算法

组合正交基字典稀疏分解通过正交基的级联来构造完备字典,实现稀疏分解。针对稀疏分解的常见算法计算复杂度高的问题,提出一种快速匹配追踪算法。该算法首先求出并存储正交基向量之间的内积,然后根据向量正交基展开系数为其与正交基向量内积的性质将内积运算转化为代数运算,得到一种快速匹配追踪算法。实验结果表明,基于Dirac基和DCT基构成的完备字典对信号leleccum进行稀疏分解时,与匹配追踪(MP)算法相比,该算法的计算速度提高了大约10倍。     

Incoherent dictionary learning and sparse representation for single-image rain removal

The incoherent dictionary learning and sparse representation algorithm was present and it was applied to single-image rain removal.The incoherence of the dictionary was introduced to design a new objective function in the dictionary learning,which addressed the problem of reducing the similarity between rain atoms and non-rain atoms.The divisibility of rain dictionary and non-rain dictionary could be ensured.Furthermore,the learned dictionary had similar properties to the tight frame and approximates the equiangular tight frame.The high frequency in the rain image could be decomposed into a rain component and a non-rain component by performing sparse coding based learned incoherent dictionary,then the non-rain component in the high frequency and the low frequency were fused to remove rain.Experimental results demonstrate that the learned incoherent dictionary has better performance of sparse representation.The recovered rain-free image has less residual rain,and preserves effectively the edges and details.So the visual effect of recovered image is more sharpness and natural.     

基于自适应冗余字典的语音信号稀疏表示算法

基于冗余字典的信号稀疏表示是一种新的信号表示理论,当前的理论研究主要集中在字典构造算法和稀疏分解算法两方面。该文提出一种新的基于自适应冗余字典的语音信号稀疏表示算法,该算法针对自相关函数为指数衰减的平稳信号,从K-L展开出发,建立了匹配信号结构的冗余字典,进而提出一种高效的基于非线性逼近的信号稀疏表示算法。实验结果表明冗余字典中原子的自适应性和代数结构使短时平稳语音信号稀疏表示具有较高的稀疏度和较好的重构精度,并使稀疏表示算法较好地应用于语音压缩感知理论。     

Sparse Bayesian learning for basis selection

Sparse Bayesian learning (SBL) and specifically relevance vector machines have received much attention in the machine learning literature as a means of achieving parsimonious representations in the context of regression and classification. The methodology relies on a parameterized prior that encourages models with few nonzero weights. In this paper, we adapt SBL to the signal processing problem of basis selection from overcomplete dictionaries, proving several results about the SBL cost function that elucidate its general behavior and provide solid theoretical justification for this application. Specifically, we have shown that SBL retains a desirable property of the /spl lscr//sub 0/-norm diversity measure (i.e., the global minimum is achieved at the maximally sparse solution) while often possessing a more limited constellation of local minima. We have also demonstrated that the local minima that do exist are achieved at sparse solutions. Later, we provide a novel interpretation of SBL that gives us valuable insight into why it is successful in producing sparse representations. Finally, we include simulation studies comparing sparse Bayesian learning with basis pursuit and the more recent FOCal Underdetermined System Solver (FOCUSS) class of basis selection algorithms. These results indicate that our theoretical insights translate directly into improved performance.     

Surveying and comparing simultaneous sparse approximation (or group-lasso) algorithms

In this paper, we survey and compare different algorithms that, given an overcomplete dictionary of elementary functions, solve the problem of simultaneous sparse signal approximation, with common sparsity profile induced by a ?_p−?_q mixed-norm. Such a problem is also known in the statistical learning community as the group lasso problem. We have gathered and detailed different algorithmic results concerning these two equivalent approximation problems. We have also enriched the discussion by providing relations between several algorithms. Experimental comparisons of the detailed algorithms have also been carried out. The main lesson learned from these experiments is that depending on the performance measure, greedy approaches and iterative reweighted algorithms are the most efficient algorithms either in term of computational complexities, sparsity recovery or mean-square error.     

特征聚类的局部敏感稀疏图像修复

针对图像修复过程中单一的字典迭代时间长、适应性差、修复效果不理想的缺点,提出了一种结合图像特征聚类与字典学习的改进的图像修复方式。首先破损的图像被分割成小块,并产生索引矩阵。然后使用控制核回归权值算法,对其进行图像聚类。通过对图像内在结构与未破损区域信息的挖掘,分割的图像块根据SKRW的相似性进行了分类。之后针对不同类型结构的图像,通过自适应局部明感字典学习的方式,获取每类字典的过完备字典。然后,通过构建自适应局部配适器,提高字典更新的收敛速度与稀疏字典的适应性。因为是通过多个字典匹配不同结构的图像,因此图像的稀疏表示更为准确。各个字典在达到收敛之前不断进行更新,而图像的稀疏因子也会随着改变。在对破损区域进行补丁更换之后,实现了对破损图像的修复。实验结果表明,该算法相较于目前的修复算法,视觉效果和客观评价上更好,且所需的修复时间更短。     

Design redundant Chebyshev dictionary with generalized extreme value distribution for sparse approximation and image denoising

This paper illustrates a novel method for designing redundant dictionary from Chebyshev polynomials for sparse coding. Having an overcomplete dictionary in ${{\mathbb R}^{d \times N}:d < N}$ from N, orthogonal functions need to sample d times from orthogonal intervals. It is proved (“Appendix B”) that uniform distribution is not optimal for sampling. Experiments show that using non-uniform measures for dividing orthogonal intervals has some advantages in making incoherent dictionary with a mutual coherence closer to equiangular tight frames, which is appropriate for sparse approximation methods. In this paper, we first describe the dictionary design problem, then modify this design with any kind of distribution, and define an objective function respect to its parameters. Because of the abundant extremums in this objective function, genetic algorithm is used to find the best parameters. Experimental results show that generalized extreme value distribution has better performance among others. This type of dictionary design improves the performance of sparse approximation and image denoising via redundant dictionary. The advantages of this method of designing overcomplete dictionaries are going to be compared with uniform ones in sparse approximation areas.     

Object tracking using discriminative sparse appearance model

Object tracking based on sparse representation formulates tracking as searching the candidate with minimal reconstruction error in target template subspace. The key problem lies in modeling the target robustly to vary appearances. The appearance model in most sparsity-based trackers has two main problems. The first is that global structural information and local features are insufficiently combined because the appearance is modeled separately by holistic and local sparse representations. The second problem is that the discriminative information between the target and the background is not fully utilized because the background is rarely considered in modeling. In this study, we develop a robust visual tracking algorithm by modeling the target as a model for discriminative sparse appearance. A discriminative dictionary is trained from the local target patches and the background. The patches display the local features while their position distribution implies the global structure of the target. Thus, the learned dictionary can fully represent the target. The incorporation of the background into dictionary learning also enhances its discriminative capability. Upon modeling the target as a sparse coding histogram based on this learned dictionary, our tracker is embedded into a Bayesian state inference framework to locate a target. We also present a model update scheme in which the update rate is adjusted automatically. In conjunction with the update strategy, the proposed tracker can handle occlusion and alleviate drifting. Comparative results on challenging benchmark image sequences show that the tracking method performs favorably against several state-of-the-art algorithms.     

The nonparametric Bayesian dictionary learning based interpolation method for WSNs missing data

The conventional data interpolation methods based on sparse representation usually assume that the signal is sparse under the overcomplete dictionary. Specially, they must confirm the dimensions of dictionary and the signal sparse level in advance. However, it is hard to know them if the signal is complicated or dynamically changing. In this paper, we proposed a nonparametric Bayesian dictionary learning based interpolation method for WSNs missing data, which is the combination of sparse representation and data interpolation. This method need not preset sparse degrees and dictionary dimensions, and our dictionary atoms are drawn from a multivariate normal distribution. In this case, the dictionary size will be learned adaptively by the nonparametric Bayesian method. In addition, we implement the Dirichlet process to exploit the spatial similarity of the sensing data in WSNs, thus to improve the interpolation accuracy. The interpolation model parameters, the optimal dictionary and sparse coefficients, can be inferred by the means of Gibbs sampling. The missing data will be estimated commendably through the derived parameters. The experimental results show that the data interpolation method we proposed outperforms the conventional methods in terms of interpolation accuracy and robustness.     

Deterministic and iterative solutions to subset selection problems

Signal decompositions with overcomplete dictionaries are not unique. We present two new approaches for identifying the sparsest representation of a given signal in terms of a given overcomplete dictionary. The first approach is an algebraic approach that attempts to solve the problem by generating other vectors that span the space of minimum dimension that includes the signal. Unlike other current techniques, including our proposed iterative technique, this algebraic approach is guaranteed to find the sparsest representation of the signal under certain conditions. For example, we can always find the exact solution if the size of the dictionary is close to the size of the space or when the dictionary can be represented by a Vandermonde matrix. Although our technique can work for high signal-to-noise cases, the exact solution is only guaranteed in noise-free cases. Our second approach is iterative and can be applied in cases where the algebraic approach cannot be used. This technique is guaranteed to achieve at least a local minimum of the error function representing the difference between the signal and its sparse representation     

Supervised within-class-similar discriminative dictionary learning for face recognition

The current study puts forward a supervised within-class-similar discriminative dictionary learning (SCDDL) algorithm for face recognition. Some popular discriminative dictionary learning schemes for recognition tasks always incorporate the linear classification error term into the objective function or make some discriminative restrictions on representation coefficients. In the presented SCDDL algorithm, we propose to directly restrict the representation coefficients to be similar within the same class and simultaneously include the linear classification error term in the supervised dictionary learning scheme to derive a more discriminative dictionary for face recognition. The experimental results on three large well-known face databases suggest that our approach can enhance the fisher ratio of representation coefficients when compared with several dictionary learning algorithms that incorporate linear classifiers. In addition, the learned discriminative dictionary, the large fisher ratio of representation coefficients and the simultaneously learned classifier can improve the recognition rate compared with some state-of-the-art dictionary learning algorithms.