A novel adaptive steganography based on local complexity and human vision sensitivity

This paper presents a novel adaptive steganographic scheme that is capable of both preventing visual degradation and providing a large embedding capacity. The embedding capacity of each pixel is dynamically determined by the local complexity of the cover image, allowing us to maintain good visual quality as well as embedding a large amount of secret messages. We classify pixels into three levels based on the variance of the local complexity of the cover image. When determining which level of local complexity a pixel should belong to, we take human vision sensitivity into consideration. This ensures that the visual artifacts appeared in the stego image are imperceptible, and the difference between the original and stego image is indistinguishable by the human visual system. The pixel classification assures that the embedding capacity offered by a cover image is bounded by the embedding capacity imposed on three levels that are distinguished by two boundary thresholds values. This allows us to derive a combination ratio of the maximal embedding capacity encountered with at each level. Consequently, our scheme is capable of determining two threshold values according to the desired demand of the embedding capacity requested by the user. Experimental results demonstrated that our adaptive steganographic algorithm produces insignificant visual distortion due to the hidden message. It provides high embedding capacity superior to that offered by a number of existing schemes. Our algorithm can resist the RS steganalysis attack, and it is statistically invisible for the attack of histogram comparison. The proposed scheme is simple, efficient and feasible for adaptive steganographic applications.     

SPC: Fast and Efficient Scalable Predictive Coding of Animated Meshes

Animated meshes are often represented by a sequence of static meshes with constant connectivity. Due to their frame-based representation they usually occupy a vast amount of bandwidth or disk space. We present a fast and efficient scalable predictive coding (SPC) scheme for frame-based representations of animated meshes. SPC decomposes animated meshes in spatial and temporal layers which are efficiently encoded in one pass through the animation. Coding is performed in a streamable and scalable fashion. Dependencies between neighbouring spatial and temporal layers are predictively exploited using the already encoded spatio-temporal neighbourhood. Prediction is performed in the space of rotation-invariant coordinates compensating local rigid motion. SPC supports spatial and temporal scalability, and it enables efficient compression as well as fast encoding and decoding. Parts of SPC were adopted in the MPEG-4 FAMC standard. However, SPC significantly outperforms the streaming mode of FAMC with coding gains of over 33%, while in comparison to the scalable FAMC, SPC achieves coding gains of up to 15%. SPC has the additional advantage over FAMC of achieving real-time encoding and decoding rates while having only low memory requirements. Compared to some other non-scalable state-of-the-art approaches, SPC shows superior compression performance with gains of over 16% in bit-rate.     

d-子树划分问题

边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分(d为非负实数),如果这些子树的顶点集的并等于此图的顶点集,且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d,边赋非负权二分平面图的d-子树划分问题是NP-完全问题;提出了求解边赋非负权树d-子树划分问题的一个线性时间算法,详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点.     

基于视觉权值的分块颜色直方图图像检索算法

为了进一步提高基于颜色直方图的图像检索系统工作效率, 本文以人眼视觉感知特性为基础, 结合局部图像相关性, 提出了一种基于视觉权值的分块颜色直方图图像检索新方法. 该方法首先对图像进行分块处理, 并计算出图像子块的颜色直方图; 然后结合反映局部区域变化的像素点颜色复杂度, 计算出图像子块的视觉权值; 最后利用视觉权值对子块颜色直方图进行加权处理, 并根据加权颜色直方图进行图像检索. 仿真实验结果表明, 本文算法能够准确和高效地查找出用户所需内容的彩色图像, 并且具有较好的查准率和查全率.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

Line planning on tree networks with applications to the Quito Trolebús system

We discuss an optimization model for the line planning problem in public transport in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the computational complexity of this problem for tree network topologies as well as several categories of line operations that are important for the Quito Trolebús system. In practice, these instances can be solved quite well, and significant optimization potentials can be demonstrated.     

用差别矩阵思想设计的基于正区域的高效属性约简算法

近来一些学者用差别矩阵或差别矩阵的思想设计了基于正区域的属性约简算法.由于计算差别矩阵是一个既消耗时间又消耗空间的过程,故这些算法的效率并不好.为了降低这类属性约简算法的复杂度,文中利用基于区分对象对的属性约简的思想,在简化决策表的基础上,定义了一个函数,该函数能度量简化决策表中条件属性集产生的区分对象对的个数,并用该函数设计了一个启发函数,同时给出了计算该启发函数的快速算法,经分析其时间和空间复杂度均为O(|U/C|).最后用该启发函数设计了一个有效的基于正区域的属性约简算法,该算法的时间复杂度降为O(|C||U|),空间复杂度降为O(|U|).文中还用一个具体实例说明了新算法的有效性.经实验证明,新算法具有较高的效率.     

最坏情况下#3-SAT问题最小上界

最坏情况下#SAT问题上界的研究已成为一个热门的研究领域.#SAT问题的时间复杂性是根据问题实例的大小所组成的函数计算所得.#SAT问题实例的大小不仅依赖于变量的数量,还依赖于子句的数量.以子句数量为参数研究#SAT问题在最坏情况下的上界,不仅可以从另一个角度衡量算法的好坏,而且在某种程度上更能准确地反映出算法的性能.首先从子句数量的角度证明了之前提出的基于扩展规则的模型计数算法(CER算法)的上界O(2m),其中m是公式中子句的数量.为了提高#3-SAT问题的求解效率,采用了多种分裂规则,进一步给出了一种基于Davis-Putnam-Logemann-Loveland(DPLL)的#3-SAT算法MCDP.通过分析该算法得到了以子句数量为参数的#3-SAT问题在最坏情况下的上界O(1.8393m).     

GF(3)上一类新型自缩控序列

设计GF(3)上一类新型的钟控模型,它由累积函数和钟控生成器复合生成。讨论这种模型所生成序列的数据率、周期、线性复杂度、1-重量复杂度等密码学性质。分析结果表明,生成的新序列具有数据率使用高、周期和线性复杂度较大等伪随机性,且该模型易于实现和推广,适合在通信密码中应用。     

一种最大向量平均个数的估计方法

提出一种估计n个d维向量中最大向量平均个数的方法。该方法通过分析单个向量与其他向量子集的支配关系,求出最大向量平均个数的解析式。证明解析式满足已知的递归关系,得到最大向量平均个数的近似估计。与已有方法相比,该方法可应用到估计k个其他向量支配的平均个数问题。