The Absolute Line Quadric and Camera Autocalibration

We introduce a geometrical object providing the same information as the absolute conic: the absolute line quadric (ALQ). After the introduction of the necessary exterior algebra and Grassmannian geometry tools, we analyze the Grassmannian of lines of P from both the projective and Euclidean points of view. The exterior algebra setting allows then to introduce the ALQ as a quadric arising very naturally from the dual absolute quadric. We fully characterize the ALQ and provide clean relationships to solve the inverse problem, i.e., recovering the Euclidean structure of space from the ALQ. Finally we show how the ALQ turns out to be particularly suitable to address the Euclidean autocalibration of a set of cameras with square pixels and otherwise varying intrinsic parameters, providing new linear and non-linear algorithms for this problem. We also provide experimental results showing the good performance of the techniques. This work has been partly supported by the Comisión Interministerial de Ciencia y Tecnología (CICYT) of the Spanish Government.     

Euclidean upgrading from segment lengths: DLT-like algorithm and its variants

In this paper, how to calibrate a fixed multi-camera system and simultaneously achieve a Euclidean reconstruction from a set of segments is addressed. It is well known that only a projective reconstruction could be achieved without any prior information. Here, the known segment lengths are exploited to upgrade the projective reconstruction to a Euclidean reconstruction and simultaneously calibrate the intrinsic and extrinsic camera parameters. At first, a DLT(Direct Linear Transformation)-like algorithm for the Euclidean upgrading from segment lengths is derived in a very simple way. Although the intermediate results in the DLT-like algorithm are essentially equivalent to the quadric of segments (QoS), the DLT-like algorithm is of higher accuracy than the existing linear algorithms derived from the QoS because of a more accurate way to extract the plane at infinity from the intermediate results. Then, to further improve the accuracy of Euclidean upgrading, two weighted DLT-like algorithms are presented by weighting the linear constraint equations in the original DLT-like algorithm. Finally, using the results of these linear algorithms as the initial values, a new weighted nonlinear algorithm for Euclidean upgrading is explored to recover the Euclidean structure more accurately. Extensive experimental results on both the synthetic data and the real image data demonstrate the effectiveness of our proposed algorithms in Euclidean upgrading and multi-camera calibration.     

Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions

We propose algorithmic frameworks based on the iterated local search (ILS) metaheuristic to obtain good‐quality solutions for the Euclidean Steiner tree problem (ESTP) in n dimensions. This problem consists in finding a tree with minimal total length that spans p points given in an n‐dimensional Euclidean space and, eventually, also some additional points whose insertion contributes to reduce the total length of the tree. These ILS approaches make use of both the tree enumeration structure, called topology‐describing vector, and the exact minimization step of a well‐known branch‐and‐bound method for the ESTP. Computational results are provided.     

Kinetic Facility Location

We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor larger than the optimal cost. In our scenario, each point can change its status between client and facility and moves continuously along a known trajectory in a d-dimensional Euclidean space, where d is a constant.     

On reachable sets for linear systems with delay and bounded peak inputs

Linear systems with constant coefficients and time-varying delays are considered. We address the problem of finding an ellipsoid that bounds the set of the states in the Euclidean space that are reachable from the origin, in finite time, by inputs with peak value that is bounded by a prechosen positive scalar. The system may encounter uncertainties in the matrices of its state space model and in the delay length. The Lyapunov-Razumikhin approach is applied and a bounding ellipsoid is obtained by solving a set of linear matrix inequalities that depend on the upper-bound of the delay length.     

Geodesic regression on spheres from a numerical optimization viewpoint

In the geodesic regression problem it is given a set of data points at known times and the goal is to find a geodesic that best fits the data. This problem corresponds to the generalization of the classical linear regression problem to curved spaces. Here we are interested in the geodesic regression problem on Euclidean spheres. Contrary to the Euclidean situation, the normal equations turn out to be highly nonlinear. To overcome this difficulty, we look at the geodesic regression problem in the unit n-sphere as an optimization problem in the Euclidean space ?ⁿ⁺¹ and use the MATLAB optimization toolbox to solve it numerically.     

Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems

We analyze several NP-hard problems related to clustering and searching, in a given set of vectors in a Euclidean space, for a subset of vectors of fixed size. An important data mining problem related to sum of squares optimization reduces to these problems. We show pseudopolynomial algorithms that are guaranteed to find an optimum in these problems in case when vector components have integer values and the dimension is fixed.     

On bending invariant signatures for surfaces

Isometric surfaces share the same geometric structure, also known as the "first fundamental form." For example, all possible bendings of a given surface that includes all length preserving deformations without tearing or stretching the surface are considered to be isometric. We present a method to construct a bending invariant signature for such surfaces. This invariant representation is an embedding of the geometric structure of the surface in a small dimensional Euclidean space in which geodesic distances are approximated by Euclidean ones. The bending invariant representation is constructed by first measuring the intergeodesic distances between uniformly distributed points on the surface. Next, a multidimensional scaling technique is applied to extract coordinates in a finite dimensional Euclidean space in which geodesic distances are replaced by Euclidean ones. Applying this transform to various surfaces with similar geodesic structures (first fundamental form) maps them into similar signature surfaces. We thereby translate the problem of matching nonrigid objects in various postures into a simpler problem of matching rigid objects. As an example, we show a simple surface classification method that uses our bending invariant signatures.     

Molecular distance geometry methods: from continuous to discrete

Distance geometry problems (DGP) arise from the need to position entities in the Euclidean K‐space given some of their respective distances. Entities may be atoms (molecular distance geometry), wireless sensors (sensor network localization), or abstract vertices of a graph (graph drawing). In the context of molecular distance geometry, the distances are usually known because of chemical properties and nuclear magnetic resonance experiments; sensor networks can estimate their relative distance by recording the power loss during a two‐way exchange; finally, when drawing graphs in two or three dimensions, the graph to be drawn is given, and therefore distances between vertices can be computed. DGPs involve a search in a continuous Euclidean space, but sometimes the problem structure helps reduce the search to a discrete set of points. In this paper we survey some continuous and discrete methods for solving some problems of molecular distance geometry.     

New results for the minimum weight triangulation problem

Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is known to find a triangulation of minimum weight, nor is the minimum weight triangulation problem known to be NP-hard. This paper proposes a new heuristic algorithm that triangulates a set ofn points inO(n ³⁾ time and that never produces a triangulation whose weight is greater than that of a greedy triangulation. The algorithm produces an optimal triangulation if the points are the vertices of a convex polygon. Experimental results indicate that this algorithm rarely produces a nonoptimal triangulation and performs much better than a seemingly similar heuristic of Lingas. In the direction of showing the minimum weight triangulation problem is NP-hard, two generalizations that are quite close to the minimum weight triangulation problem are shown to be NP-hard.This research was done while the second author was with the Department of Computer Science, Virginia Polytechnic Institute and State University.     

Finding All Minimal Shapes in a Routing Channel

We present an algorithm to find a set of all optimal solutions for a channel placement problem. A channel consists of two rows of horizontal line segments (representing components). Each line segment contains some terminals with fixed positions. Sets of terminals, called nets, are to be connected. The relative ordering of line segments in each row is fixed. The line segments can be shifted left or right, which will affect the width needed for routing and the length of the channel. We want to find the tradeoff between channel length and routing width. Since the channel routing problem is NP-complete, we use a lower bound on routing width, called density. The density of a placement is the maximum number of nets crossing each vertical cut. We can increase the total length to minimize the channel density, or minimize the total length by increasing the channel density. The pair (density, total length) is called the shape of a placement. A shape is minimal if a decrease in density would cause an increase in total length, and vice versa. Our algorithm computes all the minimal shapes in O (N ⁴ ) time, where N is the number of nets. This is the first known algorithm for this problem whose running time is polynomial in the number of nets and independent of the length of the channel. Received January 18, 1996; revised December 2, 1996.     

Top-k查询结果的有界多样化方法

查询结果重复率高是top-k查询处理过程中亟待解决的问题,已有的解决方法需要遍历初始结果集中所有的对象,因此,查询处理的效率较低.为了提高查询处理的效率,把初始结果集映射到欧氏空间中,根据拉式策略,可选用基于得分或基于距离两种方法之一从该空间选出差异最优子空间,在基于距离的方法中,对欧氏子空间进行分割并且利用探测位置和Voronoi图的几何特性减少二次查询对象的数目.在此基础上,提出了top-k查询结果有界多样化算法,并证明了算法的正确性.实验结果表明,所提出的算法提高了top-k查询处理效率.     

Optimal algorithms for some intersection radius problems

The intersection radius of a set ofn geometrical objects in ad-dimensional Euclidean space,E ^d , is the radius of the smallest closed hypersphere that intersects all the objects of the set. In this paper, we describe optimal algorithms for some intersection radius problems. We first present a linear-time algorithm to determine the smallest closed hypersphere that intersects a set of hyperplanes inE ^d , assumingd to be a fixed parameter. This is done by reducing the problem to a linear programming problem in a (d+1)-dimensional space, involving 2n linear constraints. We also show how the prune-and-search technique, coupled with the strategy of replacing a ray by a point or a line can be used to solve, in linear time, the intersection radius problem for a set ofn line segments in the plane. Currently, no algorithms are known that solve these intersection radius problems within the same time bounds.     

The cost optimal solution of the multi-constrained multicast routing problem

In this paper, we define the cost optimal solution of the multi-constrained multicast routing problem. This problem consists in finding a multicast structure that spans a source node and a set of destinations with respect to a set of constraints, while minimizing a cost function. This optimization is particularly interesting for multicast network communications that require Quality of Service (QoS) guarantees. Finding such a structure that satisfies the set of constraints is an NP-hard problem. To solve the addressed routing problem, most of the proposed algorithms focus on multicast trees. In some cases, the optimal spanning structure (i.e. the optimal multicast route) is neither a tree nor a set of trees nor a set of optimal QoS paths. The main result of our study is the exact identification of this optimal solution. We demonstrate that the optimal connected partial spanning structure that solves the multi-constrained multicast routing problem always corresponds to a hierarchy, a recently proposed generalization of the tree concept. We define the directed partial minimum spanning hierarchies as optimal solutions for the multi-constrained multicast routing problem and analyze their relevant properties. To our knowledge, our paper is the first study that exactly describes the cost optimal solution of this NP-hard problem.     

Orthogonal queries in segments

We consider theorthgonal clipping problem in a set of segments: Given a set ofn segments ind-dimensional space, we preprocess them into a data structure such that given an orthogonal query window, the segments intersecting it can be counted/reported efficiently. We show that the efficiency of the data structure significantly depends on a geometric discrete parameterK named theProjected-image complexity, which becomes Θ(n ²) in the worst case but practically much smaller. If we useO(m) space, whereK log^4d−7 n≥m≥n log^4d−7 n, the query time isO((K/m)^1/2 log^{max{4, 4d−5}} n). This is near to an Ω((K/m)^1/2) lower bound.     

Precomputation for intra-domain QoS routing

Quality-of-service routing (QoSR), seeking to find a feasible path with multiple constraints, is an NP-complete problem. We propose a novel precomputation approach to multi-constrained intra-domain QoS routing (PMCP). It is assumed that a router maintains the link state information of the entire domain. PMCP cares each QoS weight to several degrees, and computes a number of QoS coefficients uniformly distributed in the multi-dimensional QoS metric space. Based on each coefficient, a linear QoS function is constructed to convert the multiple QoS metrics to a single QoS value. We then create a shortest path tree with respect to the QoS value by Dijkstra’s algorithm. Finally, according to the multiple coefficients, different shortest path trees are calculated to compose the QoS routing table. We analyze linear QoS functions in the QoS metric space, and give a mathematical model to determine the feasibility of a QoS request in the space. After PMCP is introduced, we analyze its computational complexity and present a method of QoS routing table lookup. Extensive simulations evaluate the performance of the proposed algorithm and present a comparative study.     

An evaluation of one-class classification techniques for speaker verification

Speaker verification is a challenging problem in speaker recognition where the objective is to determine whether a segment of speech in fact comes from a specific individual. In supervised machine learning terms this is a challenging problem as, while examples belonging to the target class are easy to gather, the set of counter-examples is completely open. This makes it difficult to cast this as a supervised classification problem as it is difficult to construct a representative set of counter examples. So we cast this as a one-class classification problem and evaluate a variety of state-of-the-art one-class classification techniques on a benchmark speech recognition dataset. We construct this as a two-level classification process whereby, at the lower level, speech segments of 20 ms in length are classified and then a decision on an complete speech sample is made by aggregating these component classifications. We show that of the one-class classification techniques we evaluate, Gaussian Mixture Models shows the best performance on this task.     

Fast computation of optimal polygonal approximations of digital planar closed curves

We face the problem of obtaining the optimal polygonal approximation of a digital planar curve. Given an ordered set of points on the Euclidean plane, an efficient method to obtain a polygonal approximation with the minimum number of segments, such that, the distortion error does not excess a threshold, is proposed. We present a novel algorithm to determine the optimal solution for the min-# polygonal approximation problem using the sum of square deviations criterion on closed curves.Our proposal, which is based on Mixed Integer Programming, has been tested using a set of contours of real images, obtaining significant differences in the computation time needed in comparison to the state-of-the-art methods.     

Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks

In this paper, we study the problem of continuous monitoring of reverse k nearest neighbors queries in Euclidean space as well as in spatial networks. Existing techniques are sensitive toward objects and queries movement. For example, the results of a query are to be recomputed whenever the query changes its location. We present a framework for continuous reverse k nearest neighbor (RkNN) queries by assigning each object and query with a safe region such that the expensive recomputation is not required as long as the query and objects remain in their respective safe regions. This significantly improves the computation cost. As a byproduct, our framework also reduces the communication cost in client–server architectures because an object does not report its location to the server unless it leaves its safe region or the server sends a location update request. We also conduct a rigid cost analysis for our Euclidean space RkNN algorithm. We show that our techniques can also be applied to answer bichromatic RkNN queries in Euclidean space as well as in spatial networks. Furthermore, we show that our techniques can be extended for the spatial networks that are represented by directed graphs. The extensive experiments demonstrate that our techniques outperform the existing techniques by an order of magnitude in terms of computation cost and communication cost.     

A distance-limited continuous location-allocation problem for spatial planning of decentralized systems

We introduce a new continuous location-allocation problem where the facilities have both a fixed opening cost and a coverage distance limitation. The problem has wide applications especially in the spatial planning of water and/or energy access networks where the coverage distance might be associated with the physical loss constraints. We formulate a mixed integer quadratically constrained problem (MIQCP) under the Euclidean distance setting and present a three-stage heuristic algorithm for its solution: In the first stage, we solve a planar set covering problem (PSCP) under the distance limitation. In the second stage, we solve a discrete version of the proposed problem where the set of candidate locations for the facilities is formed by the union of the set of demand points and the set of locations in the PSCP solution. Finally, in the third stage, we apply a modified Weiszfeld’s algorithm with projections that we propose to incorporate the coverage distance component of our problem for fine-tuning the discrete space solutions in the continuous space. We perform numerical experiments on three example data sets from the literature to demonstrate the performance of the suggested heuristic method.