A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.     

Optimum sweeps of simple polygons with two guards

A polygon P admits a sweep if two mobile guards can detect an unpredictable, moving target inside P  , no matter how fast the target moves. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an O(n²)$O(n^2)$ time and O(n)$O(n)$ space algorithm for optimizing this metric, where n   is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n)$O(n)$.     

Discourse cues to deception in the case of multiple receivers

Behavioral cues to deception are instrumental in detecting deception. As one of the primary sources of deception behavior, text has been analyzed at the level of sub-sentence or message but not the discourse of interaction. Additionally, empirical studies on cues to deception in the case of multiple receivers remain nonexistent. To fill these voids, we propose a discourse framework and six hypotheses about deception behaviors in a multi-receiver environment. The deception behaviors are operationalized by discourse features based on an analysis of real-world data. The results of statistical analysis validate the efficacy of discourse features in discriminating deceivers from truth-tellers.     

Jet bundle formulation of infinite-dimensional port-Hamiltonian systems using differential operators

We consider infinite-dimensional port-Hamiltonian systems described on jet bundles. Based on a power balance relation we introduce the port-Hamiltonian system representation using differential operators regarding the structural mapping, the dissipation mapping and the input mapping. In contrast to the well-known representation on the basis of the underlying Stokes–Dirac structure our approach is not necessarily based on using energy-variables which leads to a different port-Hamiltonian representation of the analyzed partial differential equations. The presented constructions will be specialized to mechanical systems to which class also the presented examples belong.     

HMM-based state classification of a user with a walking support system using visual PCA features

The improvement of safety and dependability in systems that physically interact with humans requires investigation with respect to the possible states of the user’s motion and an attempt to recognize these states. In this study, we propose a method for real-time visual state classification of a user with a walking support system. The visual features are extracted using principal component analysis and classification is performed by hidden Markov models, both for real-time fall detection (one-class classification) and real-time state recognition (multi-class classification). The algorithms are used in experiments with a passive-type walker robot called “RT Walker” equipped with servo brakes and a depth sensor (Microsoft Kinect). The experiments are performed with 10 subjects, including an experienced physiotherapist who can imitate the walking pattern of the elderly and people with disabilities. The results of the state classification can be used to improve fall-prevention control algorithms for walking support systems. The proposed method can also be used for other vision-based classification applications, which require real-time abnormality detection or state recognition.     

A new approach of audio emotion recognition

A new architecture of intelligent audio emotion recognition is proposed in this paper. It fully utilizes both prosodic and spectral features in its design. It has two main paths in parallel and can recognize 6 emotions. Path 1 is designed based on intensive analysis of different prosodic features. Significant prosodic features are identified to differentiate emotions. Path 2 is designed based on research analysis on spectral features. Extraction of Mel-Frequency Cepstral Coefficient (MFCC) feature is then followed by Bi-directional Principle Component Analysis (BDPCA), Linear Discriminant Analysis (LDA) and Radial Basis Function (RBF) neural classification. This path has 3 parallel BDPCA + LDA + RBF sub-paths structure and each handles two emotions. Fusion modules are also proposed for weights assignment and decision making. The performance of the proposed architecture is evaluated on eNTERFACE’05 and RML databases. Simulation results and comparison have revealed good performance of the proposed recognizer.     

基于类标记扩展的半监督网络流量特征选择算法

针对网络流量特征选择过程中存在的样本标记瓶颈问题,以及现有半监督方法无法选择强相关的特征的不足,提出一种基于类标记扩展的多类半监督特征选择(SFSEL)算法。该算法首先从少量的标记样本出发,通过K-means算法对未标记样本进行类标记扩展;然后结合基于双重正则的支持向量机(MDrSVM)算法实现多类数据的特征选择。与半监督特征选择算法Spectral、PCFRSC和SEFR在Moore数据集进行了对比实验,SFSEL得到的分类准确率和召回率明显都要高于其他算法,而且SFSEL算法选择的特征个数明显少于其他算法。实验结果表明: SFSEL算法能够有效地提高所选特征的相关性,获取更好的网络流量分类性能。     

基于局部重构的无监督特征选择方法

利用局部线性嵌入(LLE)算法中获得局部邻域之间的重构关系与使用最小角回归方法解决L1归一化问题都使用回归方法,针对在通过映射获得低维嵌入空间与通过特征选择获得低维空间上有着一致的思想,提出一种能保持局部重构关系的无监督谱特征选择方法.该方法利用最小二乘法计算样本的邻域重构系数,并用这些系数表示样本之间的关系,通过解决稀疏特征值问题获得能够保持样本间关系的低维嵌入空间,最后通过解决L1归一化问题实现自动特征选择.通过在四个不同数据集上的聚类实验结果证明,该方法能更准确地评价每个特征的重要性,能自动适应不同的数据集,受参数影响更小,可以明显提升聚类效果.     

基于文档文字特征的碎纸机碎片拼接算法

针对经碎纸机粉碎的文档碎片,提出拼接复原的模型并研制了相应的算法。首先研究文档碎片边界像素特征,据此提出碎片横向拼接的两种算法;然后,研究行高、字体间间距以及字体大小等文本特征,据此提出针对经横向拼接形成的水平残条的纵向拼接算法。最后根据算法编写Matlab程序,并进行实验,结果表明该算法效果良好。