A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes

We tighten a key estimate, which dictates the computational complexity of Guruswami-Sudan algorithm, on the lower bound of the degrees of freedom, and then propose a modified decoding algorithm for Reed-Solomon codes beyond half the minimum distance. The computational complexity of the modified algorithm is lower than the Guruswami-Sudan algorithm for the medium to high rate Reed-Solomon codes, and has the same asymptotic complexity as the algorithm proposed by Wu. Besides we also claim that our modified algorithm outperforms Wu's algorithm to some extent.     

Remote sensing of structural complexity indices for habitat and species distribution modeling

Spatial distribution models are increasingly used in ecological studies, but are limited by the poor accuracy of remote sensing (RS) for mapping microhabitat (< 0.1 ha) features. Mapping accuracy can be improved by combining advanced RS image-processing techniques with microhabitat data expressed as a structural complexity index (SCI). To test this idea, we used principal components analysis (PCA) and an additive SCI method developed for forest ecology (calculated by re-scaling and summing representative structural variables) to summarize 13 microhabitat-scale (0.04 ha) vegetation structure attributes describing the rare mountain bongo antelope's (Tragelaphus eurycerus isaaci) habitat in Kenya's Aberdare mountains. Microhabitat data were collected in 127 plots: 37 related to bongo habitat use, 90 from 1 km-spaced grid points representing overall habitat availability and bongo non-presence. We then assessed each SCI's effectiveness for discerning microhabitat variability and bongo habitat selection, using Wilcoxon Rank Sum tests for differences in mean SCI scores among plots divided into 4 vegetation classes, and the Area Under the Curve (AUC) of receiver operating characteristics from logistic regressions. We also examined the accuracy of predicted SCI scores resulting from regression models based on variables derived from a) ASTER imagery processed with spectral mixture and texture analysis, b) an SRTM DEM and c) rainfall data, using the 90 grid plots for model training and the bongo plots as an independent test dataset. Of the five SCIs derived, two performed best: the PCA-derived Canopy Structure Index (CSI) and an additive index summarizing 8 structural variables (AI₈). CSI and AI₈ showed significant differences between 5 of 6 vegetation class pairs, strong abilities to distinguish bongo-selected from available habitat (AUCs = 0.71 (CSI); 0.70 (AI₈)), and predicted scores 60-110% more accurate than reported by other studies using RS to quantify individual microhabitat structural attributes (CSI model R² = 0.51, RMSE = 0.19 (training) and 0.21 (test); AI₈ model R² = 0.46, RMSE = 0.17 (training) and 0.19 (test)). Repeating the Wilcoxon tests and logistic regressions with RS-predicted SCI values showed that AI₈ most effectively preserved the patterns found with the observed SCIs. These results demonstrate that SCIs effectively characterize microhabitat structure and selection, and boost microhabitat mapping accuracy when combined with enhanced RS image-processing techniques. This approach can improve distribution models and broaden their applicability, makes RS more relevant to applied ecology, and shows that processing field data to be more compatible with RS can improve RS-based habitat mapping accuracy.     

一种基于决策表的核增量式高效更新算法

引入简化决策表,结合简化二进制差别矩阵设计思想,提出一种基于决策表的核增量式高效更新算法.该算法在更新简化的二进制差别矩阵时,只需在原决策表基础上对记录进行相应的更新,不需要重复计算原决策表的二进制差别矩阵.采用边更新简化二进制差别矩阵边计算核,显著地提高了算法的效率和灵活性.新算法的时间复杂度和空间复杂度分别为O(|C||U′|)和O(|C||U′pos||U′|).最后用一个实例说明了新算法的高效性.     

切换到高一层路网最近四个点的最短路算法

针对基于大规模图的最短路问题求解速度慢的问题,提出了一个基于路网等级的求最短路的快速近似算法。该算法首先求出高一层路网到起点的4个最近点和到终点的4个最近点及最短路径,由高一层路网形成的子图T再加上这8个最短路径形成图T',在T'上求起点到终点的最短路。这种设计使得该算法适合在超大规模图上求解,理论上也证明了精度可控,同时预处理数据也是可行的,从而使两点间最短路的求解速度大大提高。在纽约公路网上的测试结果说明了该算法的有效性和合理性。     

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.     

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.     

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

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

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

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