A standard way to approximate the distance between two vertices p and q in a graph is to compute a shortest path from p to q that goes through one of k sources, which are well-chosen vertices. Precomputing the distance between each of the k sources to all vertices yields an efficient computation of approximate distances between any two vertices. One standard method for choosing k sources is the so-called Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources.In this paper, we analyze the stretch factor F FPS of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that F FPS can be bounded in terms of the minimal value F * of the stretch factor obtained using an optimal placement of k sources as F FPS ≤ 2 r e 2 F * + 2 r e 2 + 8 r e + 1 , where r e is the length ratio of longest edge over the shortest edge in the graph. We further show that the factor r e is not an artefact of the analysis by providing a class of graphs for which F FPS ź 1 2 r e F * .
The FPS algorithm has been used for a variety of isometry-invariant surface processing tasks. The algorithm was first introduced for graph clustering @cite_14 , and later independently developed for 2D images @cite_6 and extended to 3D meshes @cite_9 . Ben @cite_10 and Giard and Macq @cite_7 used this sampling strategy to efficiently compute approximate geodesic distances, Elad and Kimmel @cite_13 and M ' e moli and Sapiro @cite_19 used FPS in the context of shape recognition. @cite_16 and @cite_4 used FPS to efficiently compute point-to-point correspondences between surfaces. While it has been shown experimentally that FPS is a good heuristic for isometry-invariant surface processing tasks @cite_10 @cite_7 @cite_13 @cite_19 @cite_16 @cite_4 , to the best of our knowledge, the worst-case stretch of the geodesics has not been analyzed theoretically.
@cite_13 @cite_14 @cite_4 @cite_7 @cite_9 @cite_6 @cite_19 @cite_16 @cite_10
2159361280 1973264045 2123631536 1810598584 92634156 2563408008 2137387796 2098578926 2162114735
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. The problem of clustering a set of points so as to minimize the maximum intercluster distance is studied. An O(kn) approximation algorithm, where n is the number of points and k is the number of clusters, that guarantees solutions with an objective function value within two times the optimal solution value is presented. This approximation algorithm succeeds as long as the set of points satisfies the triangular inequality. We also show that our approximation algorithm is best possible, with respect to the approximation bound, if PZ NP. We present an approach to find dense point-to-point correspondences between two deformed surfaces corresponding to different postures of the same non-rigid object in a fully automatic way. The approach requires no prior knowledge about the shapes being registered or the initial alignment of the shapes. We consider surfaces that are represented by possibly incomplete triangular meshes. We model the deformations of an object as isometries. To solve the correspondence problem, our approach maps the intrinsic geometries of the surfaces into a low-dimensional Euclidean space via multi-dimensional scaling. This results in posture-invariant shapes that can be registered using rigid correspondence algorithms. We introduce the Fast Marching farthest point sampling (FastFPS) approach for the progressive sampling of planar domains and curved manifolds in triangulated, point cloud or implicit form. By using Fast Marching methods 2 , 3, 6 for the incremental computation of distance maps across the sampling domain, we obtain a farthest point sampling technique superior to earlier point sampling principles in two important respects. Firstly, our method performs equally well in both the uniform and the adaptive case. Secondly, the algorithm is applicable to both images and higher dimensional surfaces in triangulated, point cloud or implicit form. This paper presents the methods underlying the algorithm and gives examples for the processing of images and triangulated surfaces. A companion report 4 provides details regarding the application of the FastFPS algorithm to point clouds and implicit surfaces. A new method of farthest point strategy (FPS) for progressive image acquisition-an acquisition process that enables an approximation of the whole image at each sampling stage-is presented. Its main advantage is in retaining its uniformity with the increased density, providing efficient means for sparse image sampling and display. In contrast to previously presented stochastic approaches, the FPS guarantees the uniformity in a deterministic min-max sense. Within this uniformity criterion, the sampling points are irregularly spaced, exhibiting anti-aliasing properties comparable to those characteristic of the best available method (Poisson disk). A straightforward modification of the FPS yields an image-dependent adaptive sampling scheme. An efficient O(N log N) algorithm for both versions is introduced, and several applications of the FPS are discussed. Point clouds are one of the most primitive and fundamental surface representations. A popular source of point clouds are three dimensional shape acquisition devices such as laser range scanners. Another important field where point clouds are found is in the representation of high-dimensional manifolds by samples. With the increasing popularity and very broad applications of this source of data, it is natural and important to work directly with this representation, without having to go to the intermediate and sometimes impossible and distorting steps of surface reconstruction. A geometric framework for comparing manifolds given by point clouds is presented in this paper. The underlying theory is based on Gromov-Hausdorff distances, leading to isometry invariant and completely geometric comparisons. This theory is embedded in a probabilistic setting as derived from random sampling of manifolds, and then combined with results on matrices of pairwise geodesic distances to lead to a computational implementation of the framework. The theoretical and computational results here presented are complemented with experiments for real three dimensional shapes. An efficient algorithm for isometry-invariant matching of surfaces is presented. The key idea is computing the minimum-distortion mapping between two surfaces. For this purpose, we introduce the generalized multidimensional scaling, a computationally efficient continuous optimization algorithm for finding the least distortion embedding of one surface into another. The generalized multidimensional scaling algorithm allows for both full and partial surface matching. As an example, it is applied to the problem of expression-invariant three-dimensional face recognition. We present a heuristic algorithm to compute approximate geodesic distances on a triangular manifold S containing n vertices with partially missing data. The proposed method computes an approximation of the geodesic distance between two vertices pi and pj on S and provides an upper bound of the geodesic distance that is shown to be optimal in the worst case. This yields a relative error bound of the estimate that is worst-case optimal. The algorithm approximates the geodesic distance without trying to reconstruct the missing data by embedding the surface in a low dimensional space via multi-dimensional scaling (MDS). We derive a new heuristic method to add an object to the embedding computed via least-squares MDS.