@article {12439, title = {Statistical Computations on Grassmann and Stiefel Manifolds for Image and Video-Based Recognition}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, volume = {33}, year = {2011}, month = {2011/11//}, pages = {2273 - 2286}, abstract = {In this paper, we examine image and video-based recognition applications where the underlying models have a special structure-the linear subspace structure. We discuss how commonly used parametric models for videos and image sets can be described using the unified framework of Grassmann and Stiefel manifolds. We first show that the parameters of linear dynamic models are finite-dimensional linear subspaces of appropriate dimensions. Unordered image sets as samples from a finite-dimensional linear subspace naturally fall under this framework. We show that an inference over subspaces can be naturally cast as an inference problem on the Grassmann manifold. To perform recognition using subspace-based models, we need tools from the Riemannian geometry of the Grassmann manifold. This involves a study of the geometric properties of the space, appropriate definitions of Riemannian metrics, and definition of geodesics. Further, we derive statistical modeling of inter and intraclass variations that respect the geometry of the space. We apply techniques such as intrinsic and extrinsic statistics to enable maximum-likelihood classification. We also provide algorithms for unsupervised clustering derived from the geometry of the manifold. Finally, we demonstrate the improved performance of these methods in a wide variety of vision applications such as activity recognition, video-based face recognition, object recognition from image sets, and activity-based video clustering.}, keywords = {activity based video clustering, activity recognition, computational geometry, Computational modeling, Data models, face recognition, feature representation, finite dimensional linear subspaces, geometric properties, Geometry, Grassmann Manifolds, Grassmann., HUMANS, Image and video models, image recognition, linear dynamic models, linear subspace structure, Manifolds, maximum likelihood classification, maximum likelihood estimation, Object recognition, Riemannian geometry, Riemannian metrics, SHAPE, statistical computations, statistical models, Stiefel, Stiefel Manifolds, unsupervised clustering, video based face recognition, video based recognition, video signal processing}, isbn = {0162-8828}, doi = {10.1109/TPAMI.2011.52}, author = {Turaga,P. and Veeraraghavan,A. and Srivastava, A. and Chellapa, Rama} } @conference {12490, title = {The role of geometry in age estimation}, booktitle = {2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP)}, year = {2010}, month = {2010/03/14/19}, pages = {946 - 949}, publisher = {IEEE}, organization = {IEEE}, abstract = {Understanding and modeling of aging in human faces is an important problem in many real-world applications such as biometrics, authentication, and synthesis. In this paper, we consider the role of geometric attributes of faces, as described by a set of landmark points on the face, in age perception. Towards this end, we show that the space of landmarks can be interpreted as a Grassmann manifold. Then the problem of age estimation is posed as a problem of function estimation on the manifold. The warping of an average face to a given face is quantified as a velocity vector that transforms the average to a given face along a smooth geodesic in unit-time. This deformation is then shown to contain important information about the age of the face. We show in experiments that exploiting geometric cues in a principled manner provides comparable performance to several systems that utilize both geometric and textural cues. We show results on age estimation using the standard FG-Net dataset and a passport dataset which illustrate the effectiveness of the approach.}, keywords = {age estimation, Aging, Biometrics, computational geometry, Face, Face Geometry, Facial animation, Feature extraction, function estimation problem, geometric face attributes, Geometry, Grassmann manifold, human face modeling, human face understanding, HUMANS, Mouth, regression, Regression analysis, SHAPE, Solid modeling, solid modelling, velocity vector}, isbn = {978-1-4244-4295-9}, doi = {10.1109/ICASSP.2010.5495292}, author = {Turaga,P. and Biswas,S. and Chellapa, Rama} } @conference {15573, title = {Tradeoffs in Approximate Range Searching Made Simpler}, booktitle = {Computer Graphics and Image Processing, 2008. SIBGRAPI {\textquoteright}08. XXI Brazilian Symposium on}, year = {2008}, month = {2008/10//}, pages = {237 - 244}, abstract = {Range searching is a fundamental problem in computational geometry. The problem involves preprocessing a set of n points in R^d into a data structure, so that it is possible to determine the subset of points lying within a given query range. In approximate range searching, a parameter eps epsiv gt; 0 is given, and for a given query range R the points lying within distance eps diam(R) of the range{\textquoteright}s boundary may be counted or not. In this paper we present three results related to the issue of tradeoffs in approximate range searching. First, we introduce the range sketching problem. Next, we present a space-time tradeoff for smooth convex ranges, which generalize spherical ranges. Finally, we show how to modify the previous data structure to obtain a space-time tradeoff for simplex ranges. In contrast to existing results, which are based on relatively complex data structures, all three of our results are based on simple, practical data structures.}, keywords = {approximate range searching, computational geometry, data structure, Data structures, query range}, doi = {10.1109/SIBGRAPI.2008.24}, author = {Arya,S. and Fonseca,G. and Mount, Dave} } @article {13260, title = {A Dimension-Independent Representation for Multiresolution Nonmanifold Meshes}, journal = {Journal of Computing and Information Science in Engineering}, volume = {6}, year = {2006}, month = {2006///}, pages = {397 - 404}, abstract = {We consider the problem of representing and manipulating nonmanifold objects of any dimension and at multiple resolutions. We present a modeling scheme based on (1) a multiresolution representation, called the vertex-based nonmanifold multitessellation, (2) a compact and dimension-independent data structure, called the Simplified Incidence Graph (SIG), and (3) an atomic mesh update operator, called vertex-pair contraction/vertex expansion. We propose efficient algorithms for performing the vertex-pair contraction on a simplicial mesh encoded as a SIG, and an effective representation for encoding this multiresolution model based on a compact encoding of vertex-pair contractions and vertex expansions.}, keywords = {computational geometry, graph theory, mesh generation}, doi = {10.1115/1.2364207}, url = {http://link.aip.org/link/?CIS/6/397/1}, author = {De Floriani, Leila and Hui,Annie} } @conference {14224, title = {Integration of motion fields through shape}, booktitle = {IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005. CVPR 2005}, volume = {2}, year = {2005}, month = {2005/06/20/25}, pages = {663- 669 vol. 2 - 663- 669 vol. 2}, publisher = {IEEE}, organization = {IEEE}, abstract = {Structure from motion from single flow fields has been studied intensively, but the integration of information from multiple flow fields has not received much attention. Here we address this problem by enforcing constraints on the shape (surface normals) of the scene in view, as opposed to constraints on the structure (depth). The advantage of integrating shape is two-fold. First, we do not need to estimate feature correspondences over multiple frames, but we only need to match patches. Second, the shape vectors in the different views are related only by rotation. This constraint on shape can be combined easily with motion estimation, thus formulating motion and structure estimation from multiple views as a practical constrained minimization problem using a rank-3 constraint. Based on this constraint, we develop a 3D motion technique, which locates through color and motion segmentation, planar patches in the scene, matches patches over multiple frames, and estimates the motion between multiple frames and the shape of the selected scene patches using the image gradients. Experiments evaluate the accuracy of the 3D motion estimation and demonstrate the motion and shape estimation of the technique by super-resolving an image sequence.}, keywords = {3D motion estimation, Automation, CAMERAS, computational geometry, Computer vision, constrained minimization problem, decoupling translation from rotation, Educational institutions, image colour analysis, image gradients, image resolution, Image segmentation, image sequence, Image sequences, integration of motion fields, Layout, minimisation, Motion estimation, motion field integration, motion segmentation, parameter estimation, planar patches, rank-3 constraint, scene patches, SHAPE, shape and rotation, shape estimation, structure estimation}, isbn = {0-7695-2372-2}, doi = {10.1109/CVPR.2005.190}, author = {Ji,H. and Ferm{\"u}ller, Cornelia} } @article {15001, title = {Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines}, journal = {Information Processing Letters}, volume = {95}, year = {2005}, month = {2005/08/16/}, pages = {382 - 388}, abstract = {We develop efficient algorithms for a number of generalized intersection reporting problems, including orthogonal and general segment intersection, 2D range searching, rectangular point enclosure, and rectangle intersection search. Our results for orthogonal and general segment intersection, 3-sided 2D range searching, and rectangular pointer enclosure problems match the lower bounds for their corresponding standard versions under the pointer machine model. Our results for the remaining problems improve upon the best known previous algorithms.}, keywords = {algorithms, computational geometry, Generalized intersection}, isbn = {0020-0190}, doi = {10.1016/j.ipl.2005.04.008}, url = {http://www.sciencedirect.com/science/article/pii/S0020019005001183}, author = {Shi,Qingmin and JaJa, Joseph F.} } @article {14263, title = {The Argus eye: a new imaging system designed to facilitate robotic tasks of motion}, journal = {IEEE Robotics \& Automation Magazine}, volume = {11}, year = {2004}, month = {2004/12//}, pages = {31 - 38}, abstract = {This article describes an imaging system that has been designed to facilitate robotic tasks of motion. The system consists of a number of cameras in a network, arranged so that they sample different parts of the visual sphere. This geometric configuration has provable advantages compared to small field of view cameras for the estimation of the system{\textquoteright}s own motion and, consequently, the estimation of shape models from the individual cameras. The reason is, inherent ambiguities of confusion between translation and rotation disappear. Pairs of cameras may also be arranged in multiple stereo configurations, which provide additional advantages for segmentation. Algorithms for the calibration of the system and the three-dimensional (3-D) motion estimation are provided.}, keywords = {Argus eye, Calibration, CAMERAS, computational geometry, Design automation, Eyes, image formation, imaging system, Information geometry, Layout, Motion estimation, multiple stereo configurations, panoramic robots, robot vision, Robot vision systems, robotic motion tasks, Robotics and automation, SHAPE, shape model estimation, system calibration}, isbn = {1070-9932}, doi = {10.1109/MRA.2004.1371606}, author = {Baker, P. and Ogale, A. S and Ferm{\"u}ller, Cornelia} } @conference {16944, title = {A Rank-by-Feature Framework for Unsupervised Multidimensional Data Exploration Using Low Dimensional Projections}, booktitle = {IEEE Symposium on Information Visualization, 2004. INFOVIS 2004}, year = {2004}, month = {2004///}, pages = {65 - 72}, publisher = {IEEE}, organization = {IEEE}, abstract = {Exploratory analysis of multidimensional data sets is challenging because of the difficulty in comprehending more than three dimensions. Two fundamental statistical principles for the exploratory analysis are (1) to examine each dimension first and then find relationships among dimensions, and (2) to try graphical displays first and then find numerical summaries (D.S. Moore, (1999). We implement these principles in a novel conceptual framework called the rank-by-feature framework. In the framework, users can choose a ranking criterion interesting to them and sort 1D or 2D axis-parallel projections according to the criterion. We introduce the rank-by-feature prism that is a color-coded lower-triangular matrix that guides users to desired features. Statistical graphs (histogram, boxplot, and scatterplot) and information visualization techniques (overview, coordination, and dynamic query) are combined to help users effectively traverse 1D and 2D axis-parallel projections, and finally to help them interactively find interesting features}, keywords = {axis-parallel projections, boxplot, color-coded lower-triangular matrix, computational complexity, computational geometry, Computer displays, Computer science, Computer vision, Data analysis, data mining, data visualisation, Data visualization, Displays, dynamic query, Educational institutions, exploratory data analysis, feature detection, feature detection/selection, Feature extraction, feature selection, graph theory, graphical displays, histogram, Information Visualization, interactive systems, Laboratories, Multidimensional systems, Principal component analysis, rank-by-feature prism, scatterplot, statistical analysis, statistical graphics, statistical graphs, unsupervised multidimensional data exploration, very large databases}, isbn = {0-7803-8779-3}, doi = {10.1109/INFVIS.2004.3}, author = {Seo,J. and Shneiderman, Ben} } @article {12430, title = {A Survey of Shape Similarity Assessment Algorithms for Product Design and Manufacturing Applications}, journal = {Journal of Computing and Information Science in EngineeringJ. Comput. Inf. Sci. Eng.}, volume = {3}, year = {2003}, month = {2003/06/00/}, pages = {109 - 118}, keywords = {CAD, computational geometry, production engineering computing, spatial reasoning}, doi = {10.1115/1.1577356}, url = {http://link.aip.org/link/?CIS/3/109/1}, author = {Cardone, Antonio and Gupta, Satyandra K. and Karnik,Mukul} } @article {15541, title = {Algorithmic issues in modeling motion}, journal = {ACM Comput. Surv.}, volume = {34}, year = {2002}, month = {2002/12//}, pages = {550 - 572}, abstract = {This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.}, keywords = {computational geometry, Computer vision, mobile networks, modeling, molecular biology, motion modeling, physical simulation, robotoics, spatio-temporal databases}, isbn = {0360-0300}, doi = {10.1145/592642.592647}, url = {http://doi.acm.org/10.1145/592642.592647}, author = {Agarwal,Pankaj K. and Guibas,Leonidas J. and Edelsbrunner,Herbert and Erickson,Jeff and Isard,Michael and Har-Peled,Sariel and Hershberger,John and Jensen,Christian and Kavraki,Lydia and Koehl,Patrice and Lin,Ming and Manocha,Dinesh and Metaxas,Dimitris and Mirtich,Brian and Mount, Dave and Muthukrishnan,S. and Pai,Dinesh and Sacks,Elisha and Snoeyink,Jack and Suri,Subhash and Wolefson,Ouri} } @conference {15624, title = {A local search approximation algorithm for k-means clustering}, booktitle = {Proceedings of the eighteenth annual symposium on Computational geometry}, series = {SCG {\textquoteright}02}, year = {2002}, month = {2002///}, pages = {10 - 18}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {In k-means clustering we are given a set of n data points in d-dimensional space Rd and an integer k, and the problem is to determine a set of k points in {\'O}C;d, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+\&egr;)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-\&egr;). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd{\textquoteright}s algorithm, this heuristic performs quite well in practice.}, keywords = {Approximation algorithms, clustering, computational geometry, k-means, local search}, isbn = {1-58113-504-1}, doi = {10.1145/513400.513402}, url = {http://doi.acm.org/10.1145/513400.513402}, author = {Kanungo,Tapas and Mount, Dave and Netanyahu,Nathan S. and Piatko,Christine D. and Silverman,Ruth and Wu,Angela Y.} } @conference {17586, title = {Distributions on level-sets with applications to approximation algorithms}, booktitle = {42nd IEEE Symposium on Foundations of Computer Science, 2001. Proceedings}, year = {2001}, month = {2001/10/08/11}, pages = {588 - 597}, publisher = {IEEE}, organization = {IEEE}, abstract = {We consider a family of distributions on fixed-weight vectors in {0, 1}t; these distributions enjoy certain negative correlation properties and also satisfy pre-specified conditions on their marginal distributions. We show the existence of such families, and present a linear-time algorithm to sample from them. This yields improved approximation algorithms for the following problems: (a) low-congestion multi-path routing; (b) maximum coverage versions of set cover; (c) partial vertex cover problems for bounded-degree graphs; and (d) the Group Steiner Tree problem. For (a) and (b), the improvement is in the approximation ratio; for (c), we show how to speedup existing approximation algorithms while preserving the best-known approximation ratio; we also improve the approximation ratio for certain families of instances of unbounded degree. For (d), we derive an approximation algorithm whose approximation guarantee is at least as good as what is known; our algorithm is shown to have a better approximation guarantee for the worst known input families for existing algorithms.}, keywords = {Approximation algorithms, approximation guarantee, approximation theory, bounded-degree graphs, computational geometry, Concrete, fixed-weight vectors, group Steiner tree problem, level-sets, linear-time algorithm, low-congestion multi-path routing, marginal distributions, maximum coverage versions, negative correlation properties, partial vertex cover problems, trees (mathematics)}, isbn = {0-7695-1116-3}, doi = {10.1109/SFCS.2001.959935}, author = {Srinivasan, Aravind} } @article {15567, title = {Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses}, journal = {Computational Geometry}, volume = {19}, year = {2001}, month = {2001/06//}, pages = {1 - 33}, abstract = {Fitting two-dimensional conic sections (e.g., circular and elliptical arcs) to a finite collection of points in the plane is an important problem in statistical estimation and has significant industrial applications. Recently there has been a great deal of interest in robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50\%) of outlying data points that can corrupt the estimator. In this paper we introduce nonlinear Theil{\textendash}Sen and repeated median (RM) variants for estimating the center and radius of a circular arc, and for estimating the center and horizontal and vertical radii of an axis-aligned ellipse. The circular arc estimators have breakdown points of ≈~21\% and 50\%, respectively, and the ellipse estimators have breakdown points of ≈ 16\% and 50\%, respectively. We present randomized algorithms for these estimators, whose expected running times are O(n2logn) for the circular case and O(n3logn) for the elliptical case. All algorithms use O(n) space in the worst case.}, keywords = {Aligned ellipse fitting, Arrangements, Circular arc fitting, computational geometry, randomized algorithms, Range searching, RM estimator, robust estimation, Theil{\textendash}Sen estimator}, isbn = {0925-7721}, doi = {10.1016/S0925-7721(01)00009-8}, url = {http://www.sciencedirect.com/science/article/pii/S0925772101000098}, author = {Mount, Dave and Netanyahu,Nathan S.} } @article {18800, title = {A Geometric Algorithm for Finding the Largest Milling Cutter}, volume = {ISR; TR 2000-40}, year = {2000}, month = {2000///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {In this paper, we describe a new geometric algorithm to determine the largest feasible cutter size for2-D milling operations to be performed using a single cutter. In particular:

1. We give a general definition of the problem as the task of covering a target region without interfering with anobstruction region. This definition encompasses the task of milling a general 2-D profile that includes bothopen and closed edges.

2. We discuss three alternative definitions of what it means for a cutter to be feasible, and explain which of thesedefinitions is most appropriate for the above problem.

3. We present a geometric algorithm for finding the maximal cutter for 2-D milling operations, and we show thatour algorithm is correct.}, keywords = {algorithms, computational geometry, computer aided manufacturing CAM, cutter selection, Manufacturing, Next-Generation Product Realization Systems, path planning}, url = {http://drum.lib.umd.edu//handle/1903/6137}, author = {Yao,Zhiyang and Gupta, Satyandra K. and Nau, Dana S.} } @conference {15589, title = {Nearly optimal expected-case planar point location}, booktitle = {Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on}, year = {2000}, month = {2000///}, pages = {208 - 218}, abstract = {We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that a query point lies within this polygon. The goal is to compute a search structure to determine which cell of the subdivision contains a given query point, so as to minimize the expected search time. This is a generalization of the classical problem of computing an optimal binary search tree for one-dimensional keys. In the one-dimensional case it has long been known that the entropy H of the distribution is the dominant term in the lower bound on the expected-case search time, and further there exist search trees achieving expected search times of at most H+2. Prior to this work, there has been no known structure for planar point location with an expected search time better than 2H, and this result required strong assumptions on the nature of the query point distribution. Here we present a data structure whose expected search time is nearly equal to the entropy lower bound, namely H+o(H). The result holds for any polygonal subdivision in which the number of sides of each of the polygonal cells is bounded, and there are no assumptions on the query distribution within each cell. We extend these results to subdivisions with convex cells, assuming a uniform query distribution within each cell}, keywords = {computational geometry, convex cells, data structure, expected search time, nearly optimal expected-case planar point location, optimal binary search tree, planar point location, planar polygonal subdivision, polygonal cells, polygonal subdivision, probability, search problems, search structure, subdivision, trees (mathematics)}, doi = {10.1109/SFCS.2000.892108}, author = {Arya,S. and Malamatos,T. and Mount, Dave} } @conference {17609, title = {Improved bounds and algorithms for hypergraph two-coloring}, booktitle = {39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings}, year = {1998}, month = {1998/11/08/11}, pages = {684 - 693}, publisher = {IEEE}, organization = {IEEE}, abstract = {We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn){\texttimes}2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1){\texttimes}2n due to Beck (1978). We further generalize this to a {\textquotedblleft}local{\textquotedblright} version, improving on one of the first applications of the Lovasz Local Lemma}, keywords = {algorithms, Application software, Approximation algorithms, bounds, computational geometry, Computer science, Contracts, Erbium, graph colouring, History, hypergraph two-coloring, Lab-on-a-chip, MATHEMATICS, n-uniform hypergraph, Parallel algorithms, Polynomials, probability}, isbn = {0-8186-9172-7}, doi = {10.1109/SFCS.1998.743519}, author = {Radhakrishnan,J. and Srinivasan, Aravind} } @conference {15588, title = {Randomized and deterministic algorithms for geometric spanners of small diameter}, booktitle = {Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on}, year = {1994}, month = {1994/11//}, pages = {703 - 712}, abstract = {Let S be a set of n points in IRd and let t gt;1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions}, keywords = {computational geometry, deletions, deterministic algorithms, directed graph, directed graphs, geometric spanners, insertions, randomised algorithms, randomized algorithms}, doi = {10.1109/SFCS.1994.365722}, author = {Arya,S. and Mount, Dave and Smid,M.} } @conference {14176, title = {Motion constraint patterns}, booktitle = {, Proceedings of IEEE Workshop on Qualitative Vision, 1993}, year = {1993}, month = {1993/06/14/}, pages = {128 - 139}, publisher = {IEEE}, organization = {IEEE}, abstract = {The problem of egomotion recovery has been treated by using as input local image motion, with the published algorithms utilizing the geometric constraint relating 2-D local image motion (optical flow, correspondence, derivatives of the image flow) to 3-D motion and structure. Since it has proved very difficult to achieve accurate input (local image motion), a lot of effort has been devoted to the development of robust techniques. A new approach to the problem of egomotion estimation is taken, based on constraints of a global nature. It is proved that local normal flow measurements form global patterns in the image plane. The position of these patterns is related to the three dimensional motion parameters. By locating some of these patterns, which depend only on subsets of the motion parameters, through a simple search technique, the 3-D motion parameters can be found. The proposed algorithmic procedure is very robust, since it is not affected by small perturbations in the normal flow measurements. As a matter of fact, since only the sign of the normal flow measurement is employed, the direction of translation and the axis of rotation can be estimated with up to 100\% error in the image measurements}, keywords = {3D motion parameters, Automation, computational geometry, Computer vision, correspondence, Educational institutions, egomotion recovery, Fluid flow measurement, geometric constraint, Geometrical optics, Image motion analysis, image plane, Laboratories, local image motion, local normal flow measurements, Motion estimation, Motion measurement, motion parameters, optical flow, Rotation measurement}, isbn = {0-8186-3692-0}, doi = {10.1109/WQV.1993.262942}, author = {Ferm{\"u}ller, Cornelia} } @conference {14233, title = {Multi-resolution shape description by corners}, booktitle = {, 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1992. Proceedings CVPR {\textquoteright}92}, year = {1992}, month = {1992/06/15/18}, pages = {271 - 276}, publisher = {IEEE}, organization = {IEEE}, abstract = {A robust method for describing planar curves in multiple resolution using curvature information is presented. The method is developed by taking into account the discrete nature of digital images as well as the discrete aspect of a multiresolution structure (pyramid). The main contribution lies in the robustness of the technique, which is due to the additional information that is extracted from observing the behavior of corners in the whole pyramid. Furthermore, the resulting algorithm is conceptually simple and easily parallelizable. Theoretical results are developed analyzing the curvature of continuous curves in scale-space and showing the behavior of curvature extrema under varying scale. The results are used to eliminate any ambiguities that might arise from sampling problems due to the discreteness of the representation. Experimental results demonstrate the potential of the method}, keywords = {ambiguities, Automation, computational geometry, Computer vision, continuous curves, corners, curvature extrema, curvature information, curve fitting, digital images, Feature extraction, IMAGE PROCESSING, image resolution, Image segmentation, Laboratories, multiple resolution, multiresolution structure, parallelizable, planar curves, Robustness, Sampling methods, scale-space, SHAPE, Smoothing methods, varying scale}, isbn = {0-8186-2855-3}, doi = {10.1109/CVPR.1992.223264}, author = {Ferm{\"u}ller, Cornelia and Kropatsch,W.} } @article {15202, title = {On a triangle counting problem}, journal = {Information Processing Letters}, volume = {33}, year = {1990}, month = {1990/02/10/}, pages = {319 - 321}, abstract = {We consider the following problem: given a set S of n points in the plane, we would like to compute for each point pϵS, how many triangles with corners at points in set S contain p. We give an O(n2) algorithm to solve the problem.}, keywords = {combinatorics, computational geometry, Range query}, isbn = {0020-0190}, doi = {10.1016/0020-0190(90)90217-L}, url = {http://www.sciencedirect.com/science/article/pii/002001909090217L}, author = {Khuller, Samir and Mitchell,Joseph S.B.} }