Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

Location and calculation-free node-scheduling schemes in large wireless sensor networks

In wireless sensor networks that consist of a large number of low-power, short-lived, unreliable sensors, one of the main design challenges is to obtain long system lifetime without sacrificing system original performance (sensing coverage and sensing reliability). To solve this problem, one of the potential approaches is to identify redundant nodes at the sensing interface and then assign them an off-duty operation mode that has lower energy consumption than the normal on-duty mode. In our previous work [J. Wireless Commun. Mobile Comput. 3 (2003) 271; Processing of ACM Wireless Sensor Network and Application Workshop 2002, September 2002], we proposed a node-scheduling scheme, which can provide a 100% sensing coverage preservation capability. This, however, requires each node to be aware of its own and its neighbors’ location information. Also, in that scheme, each node has to do accurate geometrical calculation to determine whether to take an off-duty status. In this paper, we propose and study several alternative node-scheduling schemes, which cannot completely preserve the original system coverage, but are nonetheless light-weighted and flexible compared with the previous one. Our simulation results compare these schemes with the previous one and demonstrate their effectiveness.     

Computer aided detection system for micro calcifications in digital mammograms

Breast cancer continues to be a significant public health problem in the world. Early detection is the key for improving breast cancer prognosis. Mammogram breast X-ray is considered the most reliable method in early detection of breast cancer. However, it is difficult for radiologists to provide both accurate and uniform evaluation for the enormous mammograms generated in widespread screening. Micro calcification clusters (MCCs) and masses are the two most important signs for the breast cancer, and their automated detection is very valuable for early breast cancer diagnosis. The main objective is to discuss the computer-aided detection system that has been proposed to assist the radiologists in detecting the specific abnormalities and improving the diagnostic accuracy in making the diagnostic decisions by applying techniques splits into three-steps procedure beginning with enhancement by using Histogram equalization (HE) and Morphological Enhancement, followed by segmentation based on Otsu's threshold the region of interest for the identification of micro calcifications and mass lesions, and at last classification stage, which classify between normal and micro calcifications ‘patterns and then classify between benign and malignant micro calcifications. In classification stage; three methods were used, the voting K-Nearest Neighbor classifier (K-NN) with prediction accuracy of 73%, Support Vector Machine classifier (SVM) with prediction accuracy of 83%, and Artificial Neural Network classifier (ANN) with prediction accuracy of 77%.     

基于RKNN的选址算法及其应用研究

为了使各个设施的整体利用效果最佳, 结合空间位置影响力查询技术, 提出了基于RKNN的选址算法。针对空间对象对空间位置的贡献具有多重性, 建立了一种新的空间位置影响力的度量模型, 该模型更加符合实际应用情况; 然后, 利用该模型计算选址方案中各个设施的影响力, 并引入均衡系数评价选址方案的合理性, 均衡系数越小, 方案越合理。实际应用表明基于RKNN的选址算法使村镇基础设施的选址更加合理、有效。     

LDE融合光谱回归分类的光照变化人脸识别

针对光照变化人脸识别问题中传统的光谱回归算法不能很好地进行特征提取而严重影响识别性能的问题,提出了局部判别嵌入优化光谱回归分类的人脸识别算法。计算出训练样本的特征向量;借助于数据的近邻和分类关系,利用局部判别嵌入算法构建分类问题所需的嵌入,同时学习每种分类的子流形所需的嵌入;利用光谱回归分类算法计算投影矩阵,并利用最近邻分类器完成人脸的识别。在两大人脸数据库扩展YaleB及CMU PIE上的实验验证了该算法的有效性,实验结果表明,相比其他光谱回归算法,该算法取得了更高的识别率、更好的工作特性,并且降低了计算复杂度。     

基于移动锚节点与多级通信的三维传感器网络节点自定位算法研究

在基于移动锚节点的三维传感器网络节点自定位算法SNLSFA(Sensor Node Localization Scheme based on Flying Anchors)的基础上,提出了一种新的基于移动锚节点与多级通信的三维传感器网络节点自定位算法SNLSFAMC(Sensor Node Localization Scheme based on Flying Anchors and Multi-level Communication)。首先由移动锚节点提供3个或4个辅助定位点,再由辅助定位点得到两条非平行线段,然后过线段中点分别做垂直于线段的平面,经两平面相交后得到一条经过待定位节点的直线,最后利用辅助定位点与待定位节点之间的距离作为通信半径即可得到待定位节点的位置。仿真结果表明,与SNLSFA相比,在相同锚节点数量下,SNLSFAMC提高了定位精度,且在相同定位精度下,SNLSFAMC降低了对锚节点数量的需求,提高了算法的响应时间。     

An alignment-free fingerprint bio-cryptosystem based on modified Voronoi neighbor structures

Bio-cryptography is an emerging security technology which combines cryptography with biometrics. A good bio-cryptosystem is required to protect the privacy of the relevant biometric data as well as achieving high recognition accuracy. Fingerprints have been widely used in bio-cryptosystem design. However, fingerprint uncertainty caused by distortion and rotation during the image capturing process makes it difficult to achieve a high recognition rate in most bio-cryptographic systems. Moreover, most existing bio-cryptosystems rely on the accurate detection of singular points for fingerprint image pre-alignment, which is very hard to achieve, and the image rotation transformation during the alignment process can cause significant singular point deviation and minutiae changes. In this paper, by taking full advantage of local Voronoi neighbor structures (VNSs), e.g. local structural stability and distortion insensitivity, we propose an alignment-free bio-cryptosystem based on fixed-length bit-string representations extracted from modified VNSs, which are rotation- and translation-invariant and distortion robust. The proposed alignment-free bio-cryptosystem is able to provide strong security while achieving good recognition performance. Experimental results in comparison with most existing alignment-free bio-cryptosystems using the publicly-available databases show the validity of the proposed scheme.     

基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。     

动态受限区域内的单纯型连续近邻链查询方法

受限区域内的单纯型连续近邻链查询在空间数据挖掘、数据的相似分析和推理、空间数据库等方面具有重要的作用。为了弥补已有方法的不足,详细研究了动态受限区域内的单纯型连续近邻链查询方法。基于计算几何中的Voronoi图给出了VOR_IN_CRSCNNC算法、VOR_EX_CRSCNNC算法和VOR_DE_CRSCNNC算法。进一步进行了实验比较和分析。理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一筛选和判断的冗余计算,在处理空间数据量较大、初始受限区域数据量较多、受限区域形状较为复杂的单纯型连续近邻链查询方面具有较大的优势。