Dictionary learning with the cosparse analysis model based on summation of blocked determinants as the sparseness measure

Dictionary learning is crucially important for sparse representation of signals. Most existing methods are based on the so called synthesis model, in which the dictionary is column redundant. This paper addresses the dictionary learning and sparse representation with the so-called analysis model. In this model, the analysis dictionary multiplying the signal can lead to a sparse outcome. Though it has been studied in the literature, there is still not an investigation in the context of dictionary learning for nonnegative signal representation, while the algorithms designed for general signal are found not sufficient when applied to the nonnegative signals. In this paper, for a more efficient dictionary learning, we propose a novel cost function that is termed as the summation of blocked determinants measure of sparseness (SBDMS). Based on this measure, a new analysis sparse model is derived, and an iterative sparseness maximization scheme is proposed to solve this model. In the scheme, the analysis sparse representation problem can be cast into row-to-row optimizations with respect to the analysis dictionary, and then the quadratic programming (QP) technique is used to optimize each row. Therefore, we present an algorithm for the dictionary learning and sparse representation for nonnegative signals. Numerical experiments on recovery of analysis dictionary show the effectiveness of the proposed method.     

Soft-competitive learning of sparse codes and its application to image reconstruction

We propose a new algorithm for the design of overcomplete dictionaries for sparse coding, neural gas for dictionary learning (NGDL), which uses a set of solutions for the sparse coefficients in each update step of the dictionary. In order to obtain such a set of solutions, we additionally propose the bag of pursuits (BOP) method for sparse approximation. Using BOP in order to determine the coefficients of the dictionary, we show in an image encoding experiment that in case of limited training data and limited computation time the NGDL update of the dictionary performs better than the standard gradient approach that is used for instance in the Sparsenet algorithm, or other state-of-the-art methods for dictionary learning such as the method of optimal directions (MOD) or the widely used K-SVD algorithm. In an application to image reconstruction, dictionaries trained with this algorithm outperform not only overcomplete Haar-wavelets and overcomplete discrete cosine transformations, but also dictionaries obtained with widely used algorithms like K-SVD.     

Random Exploration of the Procedural Space for Single-View 3D Modeling of Buildings

In this paper we tackle the problem of 3D modeling for urban environment using a modular, flexible and powerful approach driven from procedural generation. To this end, typologies of architectures are modeled through shape grammars that consist of a set of derivation rules and a set of shape/dictionary elements. Appearance (from statistical point of view with respect to the individual pixel’s properties) of the dictionary elements is then learned using a set of training images. Image classifiers are trained towards recovering image support with respect to the semantics. Then, given a new image and the corresponding footprint, the modeling problem is formulated as a search of the space of shapes, that can be generated on-the-fly by deriving the grammar on the input axiom. Defining an image-based score function for the produced instances using the trained classifiers, the best rules are selected, making sure that we keep exploring the space by allowing some rules to be randomly selected. New rules are then generated by resampling around the selected rules. At the finest level, these rules define the 3D model of the building. Promising results on complex and varying architectural styles demonstrate the potential of the presented method.     

Analysis and synthesis of textured motion: particles and waves

Natural scenes contain a wide range of textured motion phenomena which are characterized by the movement of a large amount of particle and wave elements, such as falling snow, wavy water, and dancing grass. In this paper, we present a generative model for representing these motion patterns and study a Markov chain Monte Carlo algorithm for inferring the generative representation from observed video sequences. Our generative model consists of three components. The first is a photometric model which represents an image as a linear superposition of image bases selected from a generic and overcomplete dictionary. The dictionary contains Gabor and LoG bases for point/particle elements and Fourier bases for wave elements. These bases compete to explain the input images and transfer them to a token (base) representation with an O(10(2))-fold dimension reduction. The second component is a geometric model which groups spatially adjacent tokens (bases) and their motion trajectories into a number of moving elements--called "motons." A moton is a deformable template in time-space representing a moving element, such as a falling snowflake or a flying bird. The third component is a dynamic model which characterizes the motion of particles, waves, and their interactions. For example, the motion of particle objects floating in a river, such as leaves and balls, should be coupled with the motion of waves. The trajectories of these moving elements are represented by coupled Markov chains. The dynamic model also includes probabilistic representations for the birth/death (source/sink) of the motons. We adopt a stochastic gradient algorithm for learning and inference. Given an input video sequence, the algorithm iterates two steps: 1) computing the motons and their trajectories by a number of reversible Markov chain jumps, and 2) learning the parameters that govern the geometric deformations and motion dynamics. Novel video sequences are synthesized from the learned models and, by editing the model parameters, we demonstrate the controllability of the generative model.     

Robust face recognition via occlusion dictionary learning

Sparse representation based classification (SRC) has recently been proposed for robust face recognition. To deal with occlusion, SRC introduces an identity matrix as an occlusion dictionary on the assumption that the occlusion has sparse representation in this dictionary. However, the results show that SRC's use of this occlusion dictionary is not nearly as robust to large occlusion as it is to random pixel corruption. In addition, the identity matrix renders the expanded dictionary large, which results in expensive computation. In this paper, we present a novel method, namely structured sparse representation based classification (SSRC), for face recognition with occlusion. A novel structured dictionary learning method is proposed to learn an occlusion dictionary from the data instead of an identity matrix. Specifically, a mutual incoherence of dictionaries regularization term is incorporated into the dictionary learning objective function which encourages the occlusion dictionary to be as independent as possible of the training sample dictionary. So that the occlusion can then be sparsely represented by the linear combination of the atoms from the learned occlusion dictionary and effectively separated from the occluded face image. The classification can thus be efficiently carried out on the recovered non-occluded face images and the size of the expanded dictionary is also much smaller than that used in SRC. The extensive experiments demonstrate that the proposed method achieves better results than the existing sparse representation based face recognition methods, especially in dealing with large region contiguous occlusion and severe illumination variation, while the computational cost is much lower.     

Improved Dynamic Dictionary Matching

In the dynamic dictionary matching problem, a dictionary D contains a set of patterns that can change over time by insertion and deletion of individual patterns. The user also presents text strings and asks for all occurrences of any patterns in the text. The two main contributions of this paper are: (1) a faster algorithm for dynamic string dictionary matching with bounded alphabets, and (2) a dynamic dictionary matching algorithm for two-dimensional texts and patterns. The first contribution is based on an algorithm that solves the general problem of maintaining a sequence of well-balanced parentheses under the operations insert, delete, and find nearest enclosing parenthesis pair. The main new idea behind the second contribution is a novel method to efficiently manipulate failure links for two-dimensional patterns.     

字典重建和空间分布关系约束下的特征选择与图像拼接

目的 针对大型图像检索领域中,复杂图像中SIFT特征描述子的冗余和高维问题,提出了一种基于字典重建和空间分布关系约束的特征选择的方法,来消除冗余特征并保留最具表现力的、保留原始空间结构性的SIFT特征描述子。方法 首先,实验发现了特征选择和字典学习方法在稀疏表示方面的内在联系,将特征选择问题转化为字典重构任务;其次,在SIFT特征选择问题中,为了保证特征空间中特征的鲁棒性,设计了新型的字典学习模型,并采用模拟退火算法进行迭代求解;最后,在字典学习的过程中,加入熵理论来约束特征的空间分布,使学习到的特征描述子能最大限度保持原始SIFT特征空间的空间拓扑关系。结果 在公开数据集Holiday大型场景图片检索数据库上,通过与国际公认的特征选择方法进行实验对比,本文提出的特征选择方法在节省内存空间和提高时间效率（30%~ 50%）的同时,还能保证所筛选的特征描述子的检索准确率比同类特征提高8%~ 14.1%;在国际通用的大型场景图片拼接数据库IPM上,验证本文方法在图像拼接应用中特征提取和特征匹配上的有效性,实验表明本文方法能节省（50% ~70%）图像拼接时间。结论 与已有的方法比较,本文的特征选择方法既不依赖训练数据集,也不丢失重要的空间结构和纹理信息,在大型图像检索、图像拼接领域和3D检索领域中,能够精简特征,提高特征匹配效率和准确率。     

SB-CIMS动态信息集成的设计与实现

数据库信息集成是CIMS中关键技术之一，本文在实现SB-CIMS静态信息集成的基础 上，进一步提出并分析阐述了异构库动态信息集成模式与设计原理，概要介绍了软件系统的 设计目标与功能，并对系统实现技术与软件结构原理作了较详细论述．通过应用于SB-CIMS 的实例表明新方法是可行和有效的．     

Parallel parsing algorithms for static dictionary compression

The data compression based on dictionary techniques works by replacing phrases in the input string with indexes into some dictionary. The dictionary can be static or dynamic. In static dictionary compression, the dictionary contains a predetermined fixed set of entries. In dynamic dictionary compression, the dictionary changes its entries during compression. We present parallel algorithms for two parsing strategies for static dictionary compression. One is the optimal parsing strategy with dictionaries that have the prefix properly, for which our algorithm requires O(L+log n) time and O(n) processors, where n is the number of symbols in the input string, and L is the maximum length of the dictionary entries, while previous results run in O(L+log n) time using O(n²) processors or in O(L+log² n) time using O(n) processors. The other is the longest fragment first (LFF) parsing strategy, for which our algorithm requires O(L+log n,) time and O(n log L) processors, while a previous result obtained an O(L log n) time performance on O(n/log n) processors. For both strategies, we derive our parallel algorithms by modifying the on-line algorithms using a pointer doubling technique     

Dynamic Dictionary Matching in External Memory

In thedynamic dictionary matchingproblem, a dictionaryDcontains a set of patterns that can change over time under insertion and deletion of individual patterns. Given an arbitrary textT, we must efficiently list all the dictionary patterns that occur at each text position. We investigate the I/O complexity of this problem for a large dictionary that must be stored in external storage devices. By following a completely new approach, we devise an efficient solution which is based upon the SB-tree data structure (P. Ferragina and R. Grossi, 1995,in“Proc. ACM Symposium on Theory of Computing,” pp. 693–702), and a novel notion of certificate for the dictionary matching problem. Our data structure can be adapted to efficiently work in main memory and to solve other problems, thus providing a new insight into the nature of the dictionary matching problem.     

基于稀疏字典的听觉显著性计算

听觉注意显著性计算模型是研究听觉注意模型的基本问题,显著性计算中选择合适的特征是关键,本文从特征选择的角度提出了一种基于稀疏字典学习的听觉显著性计算模型.该模型首先通过K-SVD字典学习算法学习各种声学信号的特征,然后对字典集进行归类整合,以选取的特征字典为基础,采用OMP算法对信号进行稀疏表示,并直接将稀疏系数按帧合并得到声学信号的听觉显著图.仿真结果表明该听觉显著性计算模型在特征选择上更符合声学信号的自然属性,基于基础特征字典的显著图可以突出噪声中具有结构特征的声信号,基于特定信号特征字典的显著图可以实现对特定声信号的选择性关注.     

具有不可控变迁离散事件系统的Petri网控制器

考虑可用具有不可控变迁的受控Petri网建模的离散事件动态系统.提出了在这类 系统中实现一组不等式约束的控制器的综合方法.所提出的控制器可通过给系统Petri网模 型增加一些Petri网元素来实现,其计算是建立在本文提出的Petrl网的路增益概念基础上 的.方法是系统、简单、计算量小.     

Competitive analysis of caching in distributed databases

This paper makes two contributions. First, we introduce a model for evaluating the performance of data allocation and replication algorithms in distributed databases. The model is comprehensive in the sense that it accounts for I/O cost, for communication cost, and, because of reliability considerations, for limits on the minimum number of copies of the object. The model captures existing replica-management algorithms, such as read-one-write-all, quorum-consensus, etc. These algorithms are static in the sense that, in the absence of failures, the copies of each object are allocated to a fixed set of processors. In modern distributed databases, particularly in mobile computing environments, processors will dynamically store objects in their local database and will relinquish them. Therefore, as a second contribution of this paper, we introduce an algorithm for automatic dynamic allocation of replicas to processors. Then, using the new model, we compare the performance of the traditional read-one-write-all static allocation algorithm to the performance of the dynamic allocation algorithm. As a result, we obtain the relationship between the communication cost and I/O cost for which static allocation is superior to dynamic allocation, and the relationships for which dynamic allocation is superior     

Dynamic Multiple-Fault Diagnosis With Imperfect Tests

In this paper, we consider a model for the dynamic multiple-fault diagnosis (DMFD) problem arising in online monitoring of complex systems and present a solution. This problem involves real-time inference of the most likely set of faults and their time-evolution based on blocks of unreliable test outcomes over time. In the DMFD problem, there is a finite set of mutually independent fault states, and a finite set of sensors (tests) is used to monitor their status. We model the dependence of test outcomes on the fault states via the traditional D-matrix (fault dictionary). The tests are imperfect in the sense that they can have missed detections, false alarms, or may be available asynchronously. Based on the imperfect observations over time, the problem is to identify the most likely evolution of fault states over time. The DMFD problem is an intractable NP-hard combinatorial optimization problem. Consequently, we decompose the DMFD problem into a series of decoupled subproblems, one for each sample epoch. For a single-epoch MFD, we develop a fast and high-quality deterministic simulated annealing method. Based on the sequential inferences, a local search-and-update scheme is applied to further improve the solution. Finally, we discuss how the method can be extended to dependent faults.     

Text analysis for constructing design representations

An emerging model in concurrent product design and manufacturing is the federation of workgroups across traditional functional ‘silos’. Along with the benefits of this concurrency comes the complexity of sharing and accessing design information. The primary challenge in sharing design information across functional workgroups lies in reducing the complex expressions of associations between design elements. Collaborative design systems have addressed this problem from the perspective of formalizing a shared ontology or product model. We share the perspective that the design model and ontology are an expression of the ‘meaning’ of the design and provide a means by which information sharing in design may be achieved. However, in many design cases, formalizing an ontology before the design begins, establishing the knowledge sharing agreements or mapping out the design hierarchy is potentially more expensive than the design itself. This paper introduces a technique for inducing a representation of the design based upon the syntactic patterns contained in the corpus of design documents. The association between the design and the representation for the design is captured by basing the representation on terminological patterns at the design text. In the first stage, we create a ‘dictionary’ of noun-phrases found in the text corpus based upon a measurement of the content carrying power of the phrase. In the second stage, we cluster the words to discover inter-term dependencies and build a Bayesian belief network which describes a conceptual hierarchy specific to the domain of the design. We integrate the design document learning system with an agent-based collaborative design system for fetching design information based on our ‘smart drawings’ paradigm.     

SAR图像稀疏优化滤波

提出一种基于稀疏优化模型的SAR图像滤波算法。该算法建立在超完备字典稀疏表示基础上,具有较强的数据稀疏性和稳健的建模假设。首先依据SAR图像的结构特征,运用正则化方法建立多目标稀疏优化模型,然后通过冗余字典稀疏优化变换系数,利用冗余字典以及具有点奇异性的小波和线奇异性的剪切波构造超完备字典,最后通过对优化问题的求解,重建SAR图像场景分辨单元的平均强度,实现了SAR图像的滤波。实验结果表明,该算法对SAR图像相干斑噪声具有很好的抑制效果,并且具有增强滤波图像纹理细节特征的优点。     

定量型关联规则在高层建筑结构选型中的应用

本文针对高层建筑结构实例库的特点，定义了同义词典和值域词典，给出同义词典的构造算法和简化方法，实现值域规范化动态管理；对Apriori算法作了一定的改进，提出高度的动态划分法，并探讨高层建筑结构实例库中定量型关联规则的发现以及应用。