On the symmetric angle-restricted nearest neighbor problem

We present an O(nlogn) time divide-and-conquer algorithm for solving the symmetric angle-restricted nearest neighbor (SARNN) problem for a set of n points in the plane under any Lp metric, 1?p?∞. This algorithm is asymptotically optimal (within a multiplicative constant) for any constant p?1.     

Maximizing bichromatic reverse nearest neighbor for <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-norm in two- and three-dimensional spaces

Bichromatic reverse nearest neighbor (BRNN) has been extensively studied in spatial database literature. In this paper, we study a related problem called MaxBRNN: find an optimal region that maximizes the size of BRNNs for L _p -norm in two- and three- dimensional spaces. Such a problem has many real-life applications, including the problem of finding a new server point that attracts as many customers as possible by proximity. A straightforward approach is to determine the BRNNs for all possible points that are not feasible since there are a large (or infinite) number of possible points. To the best of our knowledge, there are no existing algorithms which solve MaxBRNN for any L _p -norm space of two- and three-dimensionality. Based on some interesting properties of the problem, we come up with an efficient algorithm called MaxOverlap for to solve this problem. Extensive experiments are conducted to show that our algorithm is efficient.     

A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains

We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O((n+k) log(n+k)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+k) . Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L ₁ metric. Received February 15, 1996; revised November 2, 1996.     

Fast and versatile algorithm for nearest neighbor search based on a lower bound tree

In this paper, we present a fast and versatile algorithm which can rapidly perform a variety of nearest neighbor searches. Efficiency improvement is achieved by utilizing the distance lower bound to avoid the calculation of the distance itself if the lower bound is already larger than the global minimum distance. At the preprocessing stage, the proposed algorithm constructs a lower bound tree (LB-tree) by agglomeratively clustering all the sample points to be searched. Given a query point, the lower bound of its distance to each sample point can be calculated by using the internal node of the LB-tree. To reduce the amount of lower bounds actually calculated, the winner-update search strategy is used for traversing the tree. For further efficiency improvement, data transformation can be applied to the sample and the query points. In addition to finding the nearest neighbor, the proposed algorithm can also (i) provide the k-nearest neighbors progressively; (ii) find the nearest neighbors within a specified distance threshold; and (iii) identify neighbors whose distances to the query are sufficiently close to the minimum distance of the nearest neighbor. Our experiments have shown that the proposed algorithm can save substantial computation, particularly when the distance of the query point to its nearest neighbor is relatively small compared with its distance to most other samples (which is the case for many object recognition problems).     

A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem

We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the facilities and the demands of the clients are uniform. The goal is to open a subset of the input points as facilities such that the accumulated cost for the whole point set, consisting of the opening costs for the facilities and the connection costs for the clients, is minimized. We present a randomized distributed algorithm that computes in expectation an ${\mathcal {O}}(1)$ -approximate solution to the metric facility location problem described above. Our algorithm works in a synchronous message passing model, where each point is an autonomous computational entity that has its own local memory and that communicates with the other entities by message passing. We assume that each entity knows the distance to all the other entities, but does not know any of the other pairwise distances. Our algorithm uses three rounds of all-to-all communication with message sizes bounded to $\mathcal{O}(\log(n))$ bits, where n is the number of input points. We extend our distributed algorithm to constant powers of metric spaces. For a metric exponent ?≥1, we obtain a randomized ${\mathcal {O}}(1)$ -approximation algorithm that uses three rounds of all-to-all communication with message sizes bounded to $\mathcal{O}(\log(n))$ bits.     

Computing the relative neighborhood graph in the L1 and L∞ metrics

The Relative Neighborhood Graph (RNG) of a set of nk-dimensional points connects “relatively close” neighbors: two points are connected by an edge if they are at least as close to each other as to any other point. Toussaint recently investigated the properties of the RNG in the Euclidean metric and proposed algorithms for its computation. This note examines one of the open problems listed by Toussaint: the extension of the analysis to non-Euclidean metrics. It is shown that Bentley's range query data structures may be used to improve the speed of the best known RNG algorithm in the L_∞ (for k ? 2) and L₁ (for k = 2) metrics.     

K Nearest Neighbor Equality: Giving equal chance to all existing classes

The nearest neighbor classification method assigns an unclassified point to the class of the nearest case of a set of previously classified points. This rule is independent of the underlying joint distribution of the sample points and their classifications. An extension to this approach is the k-NN method, in which the classification of the unclassified point is made by following a voting criteria within the k nearest points.The method we present here extends the k-NN idea, searching in each class for the k nearest points to the unclassified point, and classifying it in the class which minimizes the mean distance between the unclassified point and the k nearest points within each class. As all classes can take part in the final selection process, we have called the new approach k Nearest Neighbor Equality (k-NNE).Experimental results we obtained empirically show the suitability of the k-NNE algorithm, and its effectiveness suggests that it could be added to the current list of distance based classifiers.     

An Experimental Comparison of the Nearest-Neighbor and Nearest-Hyperrectangle Algorithms

Algorithms based on Nested Generalized Exemplar (NGE) theory (Salzberg, 1991) classify new data points by computing their distance to the nearest generalized exemplar (i.e., either a point or an axis-parallel rectangle). They combine the distance-based character of nearest neighbor (NN) classifiers with the axis-parallel rectangle representation employed in many rule-learning systems. An implementation of NGE was compared to thek-nearest neighbor (kNN) algorithm in 11 domains and found to be significantly inferior to kNN in 9 of them. Several modifications of NGE were studied to understand the cause of its poor performance. These show that its performance can be substantially improved by preventing NGE from creating overlapping rectangles, while still allowing complete nesting of rectangles. Performance can be further improved by modifying the distance metric to allow weights on each of the features (Salzberg, 1991). Best results were obtained in this study when the weights were computed using mutual information between the features and the output class. The best version of NGE developed is a batch algorithm (BNGE FW_MI) that has no user-tunable parameters. BNGE FW_MI's performance is comparable to the first-nearest neighbor algorithm (also incorporating feature weights). However, thek-nearest neighbor algorithm is still significantly superior to BNGE FW_MI in 7 of the 11 domains, and inferior to it in only 2. We conclude that, even with our improvements, the NGE approach is very sensitive to the shape of the decision boundaries in classification problems. In domains where the decision boundaries are axis-parallel, the NGE approach can produce excellent generalization with interpretable hypotheses. In all domains tested, NGE algorithms require much less memory to store generalized exemplars than is required by NN algorithms.     

一种改进的SIFT图像配准方法

针对普通SIFT算法效率因128维的特征点描述算子而降低的问题,提出一种改进的SIFT算法,利用圆环的特性同时对每一个特征向量进行序列化,以保证物体旋转不变性,在降低描述算子维数的基础上,利用遍历搜索查找样本特征点的最近邻和次近邻特征点。实验结果表明,当图像存在不同程度的几何变形、辐射畸变和噪声影响时,改进算法更稳定、更快速。     

防接入点丢失的KNN室内定位算法

为了增强室内定位系统的鲁棒性提出了一种WLAN环境下防接入点丢失的室内定位算法。在[K]最近邻法的基础上根据信号空间畸变对接入点丢失情况进行实时检测并不断更新各接入点的丢失可能性,当检测到存在接入点丢失时对信号空间距离进行修正。实验结果表明,该算法可以在部分接入点丢失的条件下仍提供可靠的位置估计并在获取一定数量观测值后确定一个丢失接入点集合,为定位系统排除异常提供依据。     

Visible Reverse k-Nearest Neighbor Query Processing in Spatial Databases

Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings) and their presence may affect the visibility between objects. In this paper, we introduce a novel variant of RNN queries, namely, visible reverse nearest neighbor (VRNN) search, which considers the impact of obstacles on the visibility of objects. Given a data set P, an obstacle set O, and a query point q in a 2D space, a VRNN query retrieves the points in P that have q as their visible nearest neighbor. We propose an efficient algorithm for VRNN query processing, assuming that P and O are indexed by R-trees. Our techniques do not require any preprocessing and employ half-plane property and visibility check to prune the search space. In addition, we extend our solution to several variations of VRNN queries, including: 1) visible reverse k-nearest neighbor (VRkNN) search, which finds the points in P that have q as one of their k visible nearest neighbors; 2) delta-VRkNN search, which handles VRkNN retrieval with the maximum visible distance delta constraint; and 3) constrained VRkNN (CVRkNN) search, which tackles the VRkNN query with region constraint. Extensive experiments on both real and synthetic data sets have been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.     

Efficient algorithms for the all nearest neighbor and closest pair problems on the linear array with a reconfigurable pipelined bus system

We present two O(1)-time algorithms for solving the 2D all nearest neighbor (2D/spl I.bar/ANN) problem, the 2D closest pair (2D/spl I.bar/CP) problem, the 3D all nearest neighbor (3D/spl I.bar/ANN) problem and the 3D-closest pair (3D/spl I.bar/CP) problem of n points on the linear array with a reconfigurable pipelined bus system (LARPBS) from the computational geometry perspective. The first O(1) time algorithm, which invokes the ANN properties (introduced in this paper) only once, can solve the 2D/spl I.bar/ANN and 2D/spl I.bar/CP problems of n points on an LARPBS of size 1/2n/sup 5/3+c/, and the 3D/spl I.bar/ANN and 3D/spl I.bar/CP problems pf n points on an LARPBS of size 1/2n/sup 7/4+c/, where 0 < /spl epsi/ = 1/2/sup c+1/-1 /spl Lt/ 1, c is a constant and positive integer. The second O(1) time algorithm, which recursively invokes the ANN properties k times, can solve the kD/spl I.bar/ANN, and kD/spl I.bar/CP problems of n points on an LARPBS of size 1/2n/sup 3/2+c/, where k = 2 or 3, 0 < /spl epsi/ = 1/2/sup n+1/-1 /spl Lt/ 1, and c is a constant and positive integer. To the best of our knowledge, all results derived above are the best O(1) time ANN algorithms known.     

An Extension of Fuzzy L‐R Data Classification with Fuzzy OWA Distance

K‐Nearest neighbor (K‐NN) algorithm is a classification algorithm widely used in machine learning, statistical pattern recognition, data mining, etc. Ordered weighted averaging (OWA) distance based CxK nearest neighbor algorithm is a kind of K‐NN algorithm based on OWA distance. In this study, the aim is two‐fold: i) to perform the algorithm with two different fuzzy metric measures, which are Diamond distance, and weighted dissimilarity measure composed by spread distances and center distances, and ii) to evaluate the effects of different metric measures. K neighbors are searched for each class, and OWA distance is used to aggregate the information. The OWA distance can behave as intercluster distance approaches single, complete, and average linkages by using different weights. The experimental study is performed on well‐known three classification data sets (iris, glass, and wine). N‐fold cross‐validation is used for the evaluation of performances. It is seen that single linkage approach by using two different metric measures has significant different results.     

Finsler度量在KNN算法中的应用研究

为了克服传统K近邻(Knearest neighbor,KNN)算法在距离定义上的不足,提出了一种基于Finsler度量的KNN算法(Finsler metric KNN,FMKNN)。该算法将样本点间的距离定义为Finsler度量,保留了样本属性对样本间距离度量的影响,使得样本点间的距离度量更具一般性。在手写体数据集上的实验表明,FMKNN算法的分类准确率高于传统KNN算法。     

A new approach for maximizing bichromatic reverse nearest neighbor search

Maximizing bichromatic reverse nearest neighbor (MaxBRNN) is a variant of bichromatic reverse nearest neighbor (BRNN). The purpose of the MaxBRNN problem is to find an optimal region that maximizes the size of BRNNs. This problem has lots of real applications such as location planning and profile-based marketing. The best-known algorithm for the MaxBRNN problem is called MaxOverlap. In this paper, we study the MaxBRNN problem and propose a new approach called MaxSegment for a two-dimensional space when the $L_2$ -norm is used. Then, we extend our algorithm to other variations of the MaxBRNN problem such as the MaxBRNN problem with other metric spaces, and a three-dimensional space. Finally, we conducted experiments on real and synthetic datasets to compare our proposed algorithm with existing algorithms. The experimental results verify the efficiency of our proposed approach.     

基于特征点的单应矩阵鲁棒估计

提出了一种基于特征点的单应矩阵鲁棒估计算法.在图像的尺度空间中提取特征点,并对特征点进行亚像素定位.同时赋予主方向.根据邻域信息计算得到特征向量后,利用最近邻特征点距离与次近邻特征点距离之比得到初始匹配点对.用RANSAC(Random Sample Consensus)算法匹配特征点对,同时计算得到两幅图像之间的单应...     

改进Harris-SIFT算法在双目立体视觉中的应用

针对双目立体视觉图像匹配的实时性问题,提出了一种改进Harris-SIFT算法,克服了原SIFT算法提取的特征点不是角点且耗时长等问题。该算法首先用改进Harris算子进行角点提取,然后用SIFT算子构建特征描述子,最后对提取的特征点采用欧氏距离度量点对的相似性,利用最近邻搜索策略进行特征匹配。在VC++6.0与Open CV平台上,通过实验比较了所提算法与SIFT算法的特征点提取匹配结果,证明了所提算法的有效性与实时性。     

多幅图像的自动拼接算法研究

提出一种基于特征点的多幅图像自动拼接算法。根据SIFT或SURF算法在图像的尺度空间中提取特征点,对特征点进行亚像素定位,并赋予主方向。根据特征点邻域信息分布计算得到特征向量后,基于k-d树进行最近邻和次最近邻搜索,利用最近邻特征点距离与次近邻特征点距离之比得到初始匹配点对。使用RANSAC（Random Sample Consensus）算法剔除错误匹配特征点对,同时对图像之间的变换参数进行鲁棒估计,使用多频带融合算法消除拼接痕迹。实验验证了该算法能够完成多幅图像的自动无缝拼接。     

Fast agglomerative clustering using information of k-nearest neighbors

In this paper, we develop a method to lower the computational complexity of pairwise nearest neighbor (PNN) algorithm. Our approach determines a set of candidate clusters being updated after each cluster merge. If the updating process is required for some of these clusters, k-nearest neighbors are found for them. The number of distance calculations for our method is O(N²), where N is the number of data points. To further reduce the computational complexity of the proposed algorithm, some available fast search approaches are used. Compared to available approaches, our proposed algorithm can reduce the computing time and number of distance calculations significantly. Compared to FPNN, our method can reduce the computing time by a factor of about 26.8 for the data set from a real image. Compared with PMLFPNN, our approach can reduce the computing time by a factor of about 3.8 for the same data set.     

Fast agglomerative clustering using a k-nearest neighbor graph

We propose a fast agglomerative clustering method using an approximate nearest neighbor graph for reducing the number of distance calculations. The time complexity of the algorithm is improved from O(tauN²) to O(tauN log N) at the cost of a slight increase in distortion; here, tau denotes the lumber of nearest neighbor updates required at each iteration. According to the experiments, a relatively small neighborhood size is sufficient to maintain the quality close to that of the full search