Controlled bidirectional grammars

We investigate context-free grammars the rules of which can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. We distinguish several modes of derivation for this kind of grammar. The resulting language families (properly) extend the family of context-free languages. We establish some closure properties of these language families and some grammatical transformations which yield a few normal forms for this type of grammar. Finally, we consider some special cases (viz. the context-free grammar is linear or left-linear), and generalizations, in particular, the use of arbitrary rather than regular control languages.     

面向数据的句法分析消歧

面向数据的分析技术(Data-Oriented Parsing,DOP)是一种概率分析策略,其概率模型的主要目的在于为一个给定的句子找到最可能的分析,即分析消歧。实际上,有关算法计算复杂度的大量研究证明,该类消歧问题属于NP-完全问题。因此,为有效实现最可能的分析,国外学者提出许多近似分析算法。本文主要论述在 DOP 框架中,基于 Monte Carlo 方法找到最可能分析的近似分析算法,并说明该方法可在合理的算法时间代价范围内实现,而且在统计上受控,以确保所获得的近似解确实对应着分析消歧后的精确解。     

角色反演算法

给出了面向上下文无关语言的句法分析的一种计算机制:角色反演算法.这种机制通过引入句法范畴的"角色"这一概念以及相应的角色反演操作,用较小的空间代价在Chart算法中实现了较强的"预读"(look ahead)功能.这使其能节约大量的无用边,从而加速分析过程的推进.这种机制可以用于自然语言处理等多种应用领域.     

Algorithms for syllabic hypothesization in continuous speech

The paper describes a new method for representing and using syllabic knowledge in a Speech Understanding System. The aims of this representation are the generation of syllabic hypotheses, given in terms of phonetic features and phonemes, (KS used in a data-driven way) and the better specification of consonant clusters (KS used in a model-driven way). The generation of syllabic hypotheses is performed by a non-directional parser.     

典型数控延迟单元的归类分析

目前已有很多种实现数控延迟单元的电路结构,有关这方面的研究文献也层出不穷,但是这些文献大部分都是对某种电路结构进行的定性分析或者理论计算,很少有涉及到具体实现时应该注意的问题以及具体的晶体管尺寸选择问题。在对常用延迟单元结构进行总结的基础上,抽象出了两种典型的数控单元实现方式。根据理论分析及电路模拟结果指出了这两种结构各自的优缺点以及进行具体实现时应该注意的问题。同时,通过对电路模拟结果的总结和分析提出了一种简单实用的晶体管尺寸选择方法,从而简化了电路设计的复杂程度。     

Improved Algorithms and Complexity Results for Power Domination in Graphs

The NP-complete Power Dominating Set problem is an “electric power networks variant” of the classical domination problem in graphs: Given an undirected graph G=(V,E), find a minimum-size set P?V such that all vertices in V are “observed” by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that Power Dominating Set can be solved by “bounded-treewidth dynamic programs.” For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for Power Dominating Set in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that Power Dominating Set remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that Power Dominating Set parameterized by |P| is W[2]-hard and it cannot be better approximated than Dominating Set.     

信息双向融合的机器人协同导航方法

根据双足机器人足部惯性导航系统与轮式机器人航位递推/同步定位与建图(SLAM)导航系统不同的误差发散特性构建信息双向融合滤波器,即利用双足机器人导航系统中的误差零速修正(ZUPT)方法减少轮式机器人导航系统误差,并利用轮式机器人导航系统中的SLAM算法在一定环境条件下修正双足机器人的定位误差,从而同步提高两类机器人导航系统的定位与航向精度.实验结果表明:导航系统定位误差约为行进距离的2.3％,在室内等卫星导航系统失效的环境中可有效提高机器人群体导航系统的综合导航性能.     

基于快速增量式视觉感知的类脑SLAM

传统的RatSLAM算法中视觉处理受环境、光照的影响大,进而导致建图精度及稳定性下降。因此,提出了一种快速增量式视觉处理方法克服原RatSLAM系统中的视觉处理的缺陷。以一个改进型的二叉搜索树为检索算法,通过动态岛屿机制对图像进行分组,最终通过序列匹配的形式实现环境识别,达到了在线、准确、快速识别环境的目的。实验结果表明,所提算法的位置识别准确率高于99%,召回率高于80%,平均处理时间低于50ms。本系统的闭环性能、时间性能及建图稳定性均显著优于现有方案,进一步证明了基于快速增量式视觉处理方法的鲁棒性、高效性。     

基于Kinect和视觉词典的三维SLAM

针对传统滤波器方法解决机器人同时定位与地图创建(SLAM)时的误差积累问题,提出了一种基于视觉词典(BOW)的三维SLAM算法,以有效解决机器人长时间运动下误差积累的问题。相比图优化SLAM中常用的随机检测和Kd树(Kd-Tree)算法,采用基于树结构的视觉词典闭环检测算法来提高相似场景的检索效率。首先采用基于GPU的特征提取算法提取图像特征,并利用交叉匹配和k最近邻(kNN)算法取得图像中鲁棒性较强的内点;然后通过基于随机抽样一致性奇异值分解(RANSAC SVD)算法计算出相邻帧的初始位姿变换,并利用通用迭代最近点(G-ICP)算法进行优化,得到高精度的位姿变换;最后利用增量平滑和建图(iSAM)图优化方法得出最终位姿,拼接出高精度的点云地图和运动轨迹。标准数据集的测试表明,所提算法在复杂情况下具有良好的鲁棒性和精度。     

一种自适应的Graph SLAM鲁棒闭环算法

针对在常规Graph SLAM(simultaneous location and mapping)算法中后端优化无法高效排除错误闭环影响的问题,提出一种自适应的Graph SLAM鲁棒闭环算法.通过分析代价函数中尚未确定的参数对优化过程的影响,根据迭代得到的最新信息,对这些参数进行更新,从而加快算法收敛速度,并对不同的数据集有很好的适应性.利用公开的数据集对算法进行实验,通过对比发现,在添加不同类型、不同数量的异常闭环条件下,本文算法对不同数据集具有良好适应性且收敛速度较快,证明了算法的有效性.     

一种基于聚类分组的快速联合兼容SLAM数据关联算法

针对在移动机器人同时定位与建图（SLAM）过程中如何快速准确获取数据关联结果的问题,提出了一种基于DBSCAN（density-based spatial clustering of application with noise）聚类分组的快速联合兼容SLAM数据关联算法（DFJCBB）．首先,采用局部关联策略将参与关联的特征点限定在局部地图中;其次,针对多数环境中量测都有较明显的分布,采用一种基于密度聚类的方法DBSCAN对当前时刻的量测进行分组,从而得到若干关联度小的观测小组;最后,在每个小组中采用联合兼容分支定界（JCBB）算法进行数据关联,以获得每个小组量测与局部地图特征之间的最优关联解,并将这些关联解组合获得最终的关联结果．基于模拟器和标准数据集的仿真实验验证了该关联算法的性能,结果表明该关联算法在保证获得较高关联准确度的同时,大大降低了算法复杂度、缩短了运行时间,适用于解决不同复杂环境中的SLAM数据关联问题．     

基于软分配SIFT特征的回环检测算法

回环检测能够消除视觉SLAM的累积误差,对SLAM系统意义重大。其中,应用较广泛的视觉词袋模型算法存在着视觉单词同一性和歧义性问题,影响了回环检测效果。为改善这些问题并提高回环检测效果,提出了一种基于软分配SIFT（scale-invariant feature transform）特征的回环检测算法。该算法将图像提取出的SIFT特征点分配到欧氏距离最近的几个单词上,并根据距离排序加权,剔除距离单词较远的特征点,生成更具区分性的描述子。并且在筛选候选项时,加入相同单词特征点占比以及单词偏移稳定性约束,筛选出少量候选项。实验结果中,该算法相较于传统视觉词袋模型以及近些年的几种回环检测算法,在三种数据集中的100%准确率下的召回率有所提升,图像平均查询时间在40 ms左右。结果表明,该算法对回环检测效果有一定提升,并且保证了实时性。     

一种基于时间戳的高扩展性的持久性软件事务内存

新兴的非易失性内存(non-volatile memory, NVM)具有字节寻址、持久性、大容量和低功耗等优点,然而,在NVM上进行并发编程往往比较困难,用户既要保证数据的崩溃一致性又要保证并发的正确性.为了降低用户开发难度,研究人员提出持久性事务内存方案,但是现有持久性事务内存普遍存在扩展性较差问题.测试发现限制扩展性的关键因素在于全局逻辑时钟和冗余NVM写操作.针对这2个方面,提出了线程逻辑时钟方法,通过允许每个线程拥有一个独立时钟,消除全局逻辑时钟中心化问题;提出了缓存行感知的双版本方法,为数据维护2个版本,通过循环更新这2个版本来保证数据的崩溃一致性,从而消除冗余的NVM写操作.基于所提出的这2个方法,实现了一个基于时间戳的高扩展的持久性软件事务内存(scalable durable transactional memory, SDTM),对比测试显示,在YCSB负载下,与DudeTM和PMDK相比,SDTM的性能最多分别提高了2.8倍和29倍.     

Selection and Evaluation of the Optimal Scale in Multi-scale Segmentation of Remote Sensing Images

Multi-scale segmentation is the premise and key step of Object-Based Image Analysis (OBIA). The quality of multi-scale segmentation directly affects the accuracy of object-oriented classification. However, scale selection and evaluation remains a challenge in multi-scale segmentation. According to the fact that the optimal segmentation scale of the remote sensing image is closely related to the complexity of the objects of the image, a top-down method to select the optimal scale based on the complexity of segmented objects is proposed. In the top-down segmentation process, image features of each segmented object are extracted to construct the complexity function, and the optimal scale of each object is determined by setting a threshold value and iterating calculation. Then, the segmentation results with the best scale are obtained and applied to the ZY-3 satellite multispectral image and the GF-2 fusion image to obtain segmentation and classification results. Qualitative visual evaluation method, unsupervised evaluation method and supervised classification evaluation method were used to compare them with results obtained by the optimal single-scale segmentation and the unsupervised evaluation method. The experimental results show that the method can accurately obtain the scale matching with the ground targets, and improve segmentation effect and the classification accuracy, it is of practical value.     

Soft Computing Based Pattern Classifiers for the Obstacle Avoidance Behavior of Intelligent Autonomous Vehicles (IAV)

To ensure more autonomy and intelligence with real-time processing capabilities for the obstacle avoidance behavior of Intelligent Autonomous Vehicles (IAV), the use of soft computing is necessary to bring this behavior near to that of humans in the recognition, learning, adaptation, generalization, reasoning and decision-making, and action. In this paper, pattern classifiers of spatial obstacle avoidance situations using Neural Networks (NN), Fuzzy Logic (FL), Genetic Algorithms (GA) and Adaptive Resonance Theory (ART) individually or in combination are suggested. These classifiers are based on supervised learning and adaptation paradigms as Gradient Back-Propagation (GBP), FL, GA and Simplified Fuzzy ArtMap (SFAM) resulting in NN/GBP and FL as Intelligent Systems (IS) and in NN/GA, NN/GA-GBP, NN-FL/GBP and NN-FL-ART/SFAM as Hybrid Intelligent Systems (HIS). Afterwards, a synthesis of the suggested pattern classifiers is presented where their results and performances are discussed as well as the Field Programmable Gate Array (FPGA) architectures, characterized by their high flexibility and compactness, for their implementation.     

Structural developments of fuzzy systems with the aid of information granulation

We introduce a design procedure for fuzzy systems using the concept of information granulation and genetic optimization. Information granulation and resulting information granules themselves become an important design aspect of fuzzy models. By accommodating the formalism of fuzzy sets, the model is geared towards capturing relationship between information granules (fuzzy sets) rather than concentrating on plain numeric data. Information granulation realized with the use of the standard C-Means clustering helps determine the initial values of the parameters of the fuzzy models. This in particular concerns such essential components of the rules as the initial apexes of the membership functions standing in the premise part of the fuzzy rules and the initial values of the polynomial functions standing in the consequence part. The initial parameters are afterwards tuned with the aid of the genetic algorithms (GAs) and the least square method (LSM). The overall design methodology arises as a hybrid development process involving structural and parametric optimization. Especially, genetic algorithms and C-Means are used to generate the structurally as well as parametrically optimized fuzzy model. To identify the structure and estimate parameters of the fuzzy model we exploit the methodologies such as joint and successive method realized by means of genetic algorithms. The proposed model is evaluated using experimental data and its performance is contrasted with the behavior of the fuzzy models available in the literature.     

一种面向TTCN 3测试系统的共享内存管理框架*

为了提高TTCN-3测试组件间通信的性能,在基于TTCN-3的基础测试平台上设计并实现了一套支持动态切换内存管理策略的共享内存管理框架,并在该框架下实现了三套不同的共享内存分配和自动回收策略.框架能够根据系统运行时刻的共享内存统计特征在这些策略中选择性能预期最好的一套,并动态地将当前内存管理策略切换为该套方案.在基础测试平台上运行一系列并发测试用例表明,该框架能提升内存管理以及整个系统的平均性能.     

What can be controlled: actionable ICT4D in the case of Palestine

ABSTRACT

A thriving information and communication technology (ICT) economy is an aspiration for developing countries. This research identifies the factors that can motivate or inhibit ICT opportunities in a developing country to grow a sustainable economy. We build an ICT4D decision framework that provides a three-dimensional view based on (1) key factors (e.g. infrastructure, policies), (2) the ICT supply chain, and (3) stakeholders (e.g. industry, government, academia). The framework is applied to the case of Palestine. We use secondary and primary data to understand how both controllable and non-controllable country characteristics have contributed to or inhibited the growth and development of an ICT sector. Results from extensive secondary data sources demonstrate the usability of the framework to analyze the current setting of the ICT sector, in addition to help investigate a range of possible opportunities for action. Then, via a targeted set of interviews with academic, industrial, and governmental sources who are experts in the Palestinian ICT arena, we perform an exploratory study that focuses on key controls and impacts for future development of the ICT economy. The outcomes of this research have the ability to frame and inform economic development decisions that could define the future of the Palestinian state.     

一种面向HEVC的编码单元深度决策算法

新一代高性能视频编码(HEVC)标准采用灵活的四叉树自适应存储结构、可变尺寸的编码块、35种帧内预测模式等新技术,能够有效提升HEVC的编码效率,但也造成了更高的编码复杂度。为此,提出一种基于时空相关性的编码单元深度决策算法。融合关联帧编码单元的深度信息及当前帧相邻编码单元的深度信息,从而预测当前编码单元的深度范围。实验结果表明,与HEVC标准测试算法相比,该算法能在不明显影响编码质量的基础上平均减少30.2%的编码时间。