Search

Transformations are integral part of graphics programs for visualization. Rotation transformations allow viewing objects from different angles. Rotations about the principal axes are straightforward whereas the rotation about an arbitrary axis is complex. We present a new algorithm simpler than the existing techniques for creating arbitrary rotation matrix. It builds upon the change of basis instead of a sequence of rotations based on the angles it makes with the principal axes/planes. We compare it with the existing proofs. Finally, we give an example by creating an axis interactively and 3D object created by rotation a mouse drive polygonal curve. The application developers and practitioners will find this intuitive and simpler algorithm useful.

The rotary wing UAV has an important practical significance in the military and civil fields. The ability of autonomous flight control and obstacle avoidance is the precondition for ensuring the safe flight of unmanned aerial vehicles. This paper uses contour map data to see the closed contour curve as an obstacle, extracts the height data of the control points, and removes the insertion values outside the measured elevation to get the closed polygonal curve as obstacles to carry out UAV path planning. The simulation results show that the algorithm is feasible and has some advantages in the complex terrain, such as mountain area, city and so on.

Conventionally, the equirectangular projection (ERP) has been used for representing 360-degree panorama videos. However, ERP suffers from over stretching in polar regions and thus increases the bitrate and the encoding/decoding complexity. This paper presents the nested polygonal chain packing method where the top and bottom stripes of an ERP picture are resampled sample-row-wise. The sampling ratio is a linear function of the sample row being processed. The height of the top or bottom stripe can be for example a quarter of the height of the ERP picture. The resampled sample rows are arranged in nested polygonal chains. According to the presented experimental results, the proposed nested polygonal chain packing provides on average 6.1% bitrate reduction compared to ERP.

We study the geometry of a 2-dimensional cyclic pursuit problem where n identical mobile agents modeled as unicycles are driven by a distributed control law. The agent i pursuits the agent i + 1 modulo n with the same constant forward speed. We propose, for the first time, a stable relative (1 : n)-periodic trajectory (RPT) for the polygonal chain formed by the system with a sufficiently large n. Unlike regular polygon, the polygonal chain evolves into the shape of figure-eight while the system follows this RPT. The shape of the figure-eight can be approximated by closed Euler elastica. We show several geometrical and dynamical properties of this polygonal chain such as curve length and configuration precession. In addition, it reveals that the rotation number of an unbroken polygonal chain is a geometric invariant when it converges to a stable formation.

Face recognition under surveillance circumstances still poses a significant problem due to low data quality. Nevertheless, automatic analysis is highly desired for criminal investigations due to the growing amount of security cameras worldwide. We suggest a face recognition system addressing the typical issues such as motion blur, noise or compression artifacts to improve low-quality recognition rates. A low-resolution adapted residual neural net serves as face image descriptor. It is trained by quality adjusted public training data generated by data augmentation strategies such as motion blurring or adding compression artifacts. To further reduce noise effects, a noise resistant manifold-based face track descriptor using a polygonal chain is proposed. This leads to a performance improvement on in-the-wild surveillance data compared to conventional local feature approaches or the state-of-the-art high-resolution VGG-Face network.

This paper proposes an O(nlog n) time algorithm capable of finding near-shortest path on polygonal surfaces. Shortest-path planning in 3-dimensional space is an NP-hard problem. Theoretically, if the number of Steiner points in Kanai and Suzuki's algorithm is allowed to approach infinity, the path obtained will be optimal. In practice, the results generated by the KS's algorithm with 29 Steiner points are very close to the optimal solutions. We thus compared the experimental results of our algorithm to the results of the KS's algorithm using 29 Steiner points. Under such configuration, the average path length obtained by our method is slightly longer than the KS's, but our computing time is much shorter. The comparisons indicate that the proposed method is highly efficient for path-planning on polygonal surfaces. The method can be potentially applied to many important research and industrial fields such as 3D route planning, GIS, CNC tooling, etc.

In view of the existing polygonal approximation algorithm of digital curves can't effectively solve the problem of polygonal approximation constrained by the offset direction, this paper proposes an algorithm of polygonal approximation constrained by the offset direction. First, the offset polygon of the original digital curve is calculated under the control of offset direction and distance. Second, the summation of the squared Euclidean distances between the vertices on the offset polygon and its corresponding segment in the approximated polygon is selected as the fitness function. Finally, under the control of the offset distance and fitness function, this paper implements a PSO-based polygonal approximation algorithm to approximate the offset polygon. Experiments show that the proposed method can not only satisfy the polygonal approximation with directional requirements, but also can greatly improve the operating efficiency.

We present a new symmetry transform finding rectangles based on a gradient and corner information of images. We succeed the Fast Radial Symmetry Transform (FRST) finding radial objects with low cost and high accuracy. But FRST focused on using image gradient to find small circle shapes so that FRST can not detect larger polygonal shapes well. Our transform used image gradient and image corner to construct polygonal symmetry maps and extract regions of interest from images. We referred the set of polygon features as the Polygonal Symmetry Transform (PST). Then PST has large coverage with the advantages of FRST. To verify PST, we designed a polygon detectors which finds the road traffic sign such as radial and polygonal shapes. Our detector extracted regions of interest from real road images and calculated performances including detection rate for traffic signs and processing time per image in our experiments.

Since the intricate and dangerous working environment of steam generator, it's risk for workers to complete fastening bolts of blocking plate. The paper introduces a fastening bolt method based on image recognition. The mechanical structure and control system were proposed gradually to be a carrier for the method. Then the image recognition adapted the Canny algorithm to realize the image binaryzation and draw the image counter. After the polygonal curve algorithm was utilized to get the hexagon, the center coordination values of the hexagon was obtained by the hexagonal spatial moment. In addition, the fastening bolt method was displayed, which adapted the torque and time control method. Finally the precision and bolt experiment validated the procedure of the image recognition and fastening bolt.

We present structural properties of the farthest line-segment Voronoi diagram in the piecewise linear L_infinity and L_1 metrics, which are computationally simpler than the standard Euclidean distance and very well suited for VLSI applications. We introduce the farthest line-segment hull, a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and is related to it similarly to the way an ordinary convex hull relates to the farthest-point Voronoi diagram. In L_infinity (resp. L_1) the farthest line-segment hull, and thus the farthest line-segment Voronoi diagram, has size O(h), where h ranges from O(1) e.g., axis parallel line-segments, to O(n), and it can be constructed in time O(n log h). Once the L_infinity (resp. L_1) farthest line-segment hull is available, the corresponding Voronoi diagram can be constructed in additional O(h) time.

We present a method to approximate a digital curve with a straight line sequence. The curve approximation curve has been posed as an optimization problem, and a genetic algorithm is used to solve such a problem. The proposed approach outputs a set of ending points for the line segments used to encode the resulting polygonal approximation. We have tested our method with a curve dataset composed of 11 open and closed curves. The results show that the proposed method performs qualitatively well on the test dataset. We show also quantitative measures of the similarity between the original input curve and the results of the genetic algorithm-based optimization process.

How many linear segments are sufficient to represent a shape? In this paper we consider the problem of the nonparametric polygonal and multimodel approximation of digital curves. In order to solve the problem, we propose algorithm that is based on the parameterized model of the Rate-Distortion curve and the multiplicative cost function. By analyzing the minimum of the cost function, we define a solution that produces the best possible balance between the number of segments and the approximation error. The algorithm performed well as it produced the relevant polygonal approximation and two-model approximation (with linear segments and circular arcs).

A 2D convex polygons recognition method is proposed. The algorithm is suitable for robot vision, quality control or photogrammetry applications when the image objects to be processed have convex shapes. First, an adaptive convex polygonal vertex detection is applied. Then a polygonal fitting algorithm using as input the detected vertices and the object contour provides a precise object identification and description.

This paper presents a novel type of binary operation on medial axes: fusion of medial axes. A method for fusing medial axes of two-dimensional objects is described. The method is applicable to a pair of the medial axes of adjacent multiply-connected polygonal domains in the plane. The algorithm computes the medial axis from a structure called Delaunay graph which embodies information about adjacency in the Voronoi diagram of the edges and vertices. It is shown how Delaunay graphs can be merged and hence how the fused medial axis can be computed from individual Delaunay graphs. The main singularity of the fusing operation is that to construct the medial axis for a union of two adjacent figures in is not necessary to explicitly union the figures. This makes sense in those cases when two figures sharing finite number of polygonal chains overlap in the plane and cannot be united. Such problem of overlapped polygons occurs frequently in handling geospatial map objects in GIS (for example, bridge and road different level parts within an interchange). The complexity of the proposed method is O(n log n) where n is a number of vertices both in two polygonal figures.

In this paper, we present a novel non-parametric polygonal approximation algorithm for planar curves. The proposed algorithm first selects all the breakpoints on the contour. From this set, a smaller set of high curvature points, cut-points, are obtained. An optimization procedure adaptively finds the best fitting polygonal approximation. Our algorithm adaptively locates segments of the contour with different levels of details. The proposed algorithm follows the contour more closely where the level of details on the curve is high. Experimental results demonstrate that the proposed algorithm is robust for noisy, real-life contours and compares favorably with other algorithms.

The problem considered in this work is to find a dimension independent algorithm for the generation of signed scalar fields exactly representing polygonal objects and satisfying the following requirements: the defining real function takes zero value exactly at the polygonal object boundary; no extra zero-value isosurfaces should be generated; C1 continuity of the function in the entire domain. The proposed algorithms are based on the binary space partitioning (BSP) of the object by the planes passing through the polygonal faces and are independent of the object genus, the number of disjoint components, and holes in the initial polygonal mesh. Several extensions of the basic algorithm are proposed to satisfy the selected optimization criteria. The generated BSP-fields allow for applying techniques of the function-based modelling to already existing legacy objects from CAD and computer animation areas, which is illustrated by several examples.

The mathematical model of isometric polygonal curve was analyzed. To predigest the construct of isometric polygonal profile, and the realization on engineering application and the favorable of NC machining being taken into account, the practical isometric polygonal curve was put forward. The mathematical model of practical isometric polygonal was analysed, and the 2D model and solid machining process simulation were put forward. At the same time, the experiment of practical isometric-trilateral profile shaft was carried out. The results of simulation and experiment showed that the derivation of isometric polygonal curve equation and the establishment of mathematical model were correct, the NC milling program generated by MasterCAM 9.1 can be used process after little modification, and the isometric polygonal profile can be high-precision, high-efficiency and high-flexibility machining by the method of NC milling.

In this paper, we propose a new polygonal mesh geometry coding scheme based on a process of structuring by acquiring surrounding vertices of the polygonal mesh one layer at a time. The structuring process begins by selecting the start vertex and proceeding by acquiring surrounding vertices of the polygonal mesh. As a result, we obtain a 2-D structured vertex table. Structured geometry data are generated according to the structured vertices and encoded by a multiresolution decomposition and space frequency quantization coding method. In our proposed scheme, the multiresolution decomposition uses the connectivity of the polygonal mesh. In addition, with a space frequency quantization coding scheme, we can reduce redundancies of decomposed coefficients at similar positions in different components of decomposition level. Experimental results show that the proposed scheme gives better coding performance at lower bit-rates than the usual schemes.

A fast online algorithm was developed for polygonal approximation of signals and curves with a minimum number of line segments for a given constraint on the standard deviation of the approximation error. A continuous Dynamic Programming search with piecewise backtracking of the locally optimal solutions is performed in overlapping windows. The developed online algorithm can be used for polygonal approximation of data streams, time series, digital signals, curves, and trajectories.

The segmentation of 2D images or polygonal using discrete geometry conducts most of the time at the appearance of artifacts along side the curves obtained after binarization. This is either of the variation of light, the sensor or its position relative to the light. The emergence of this noise leads us to make images of pre-treatment before use it. The algorithm for optimal polygonal approximation of the closed curve is generalized for opened curves and used as part of our work on the stereo images.

We present algorithms for computing approximate distance functions and shortest paths from a generalized source (point, segment, polygonal chain or polygonal region) on a weighted non-convex polyhedral surface in which obstacles (represented by polygonal chains or polygons) are allowed. We also describe an algorithm for discretizing, by using graphics hardware capabilities, distance functions. Finally, we present algorithms for computing discrete k-order Voronoi diagrams.

A two step procedure for removing noise from polygonal shapes is presented here. The first step is the removal of vertices by linear and different nonlinear inverse diffusion filters. In the second step we apply the triangle method which identifies least dominant vertices from the polygon obtained from the first stage. Those vertices whose adjacent sides form triangles of the smallest area are defined as least dominant and most likely to be noise. A thorough testing of this method on the shapes typical in video images demonstrates that it successfully removes noise vertices while it preserves dominant ones.

Shape representation is a very important issue in computer vision and pattern recognition. This paper presents a novel shape representation algorithm based on equilateral polygonal approximation. Firstly, the problem and definition of equilateral polygonal approximation are presented in this paper. Then a new equilateral polygonal approximation method based on detecting optimal edge length using genetic algorithm is proposed.

We introduce a method for de-noising, segmenting and measuring similarity of shapes. The proposed method consists of two techniques. First we use an inverse diffusion filter for enhancement of relevant polygonal vertices and removal of noise and irrelevant edges. Second we apply a technique that removes the vertices that form the triangles with the smallest areas. In a thorough experimental evaluation, the combined method shows successful noise suppression while preserving dominant vertices present in the input shape.

We present an algorithm for computing exact shortest paths, and consequently distances, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex polyhedral surface in which polygonal chain or polygon obstacles are allowed. We also present algorithms for computing discrete Voronoi diagrams of a set of generalized sites (points, segments, polygonal chains or polygons) on a polyhedral surface with obstacles. To obtain the discrete Voronoi diagrams our algorithms, exploiting hardware graphics capabilities, compute shortest path distances defined by the sites.

A fast algorithm is proposed for polygonal approximation of a digitized curve based on genetic evolution. The polygon is represented by a set of dominant points. The dominant points are identified as the points on the curve with local maximum curvatures. The optimization problem for the digitized curve with the approximating polygon is employing the genetic algorithm. Thus, a chromosome is used to represent a polygon. The break point detection on the chromosome is conducted to reduce the computations for optimization. Experimental results are included to show the effectiveness of this method.

In the paper, the polygonal approximation is regarded as finding the minimum value of restricted function which is defined by the arc-to-chord deviation between the polygon and the curve. We construct a 2D annealed chaotic Hopfield network, ACHN, array with the rows representing the curve points and the columns representing the breakpoints of the approximation polygon. The proposed ACHN overcomes the disadvantage of converging toward local minimum of traditional neural network due to its chaotic, so we can find the approximated polygon more similar to the curve.

We propose optimal and near-optimal algorithm for multiresolution polygonal approximation of digital curves. The solution with minimum number of segments is constructed as the shortest path in a weighted graph where the weights are recursively defined as the number of segments of all embedded layers.

Polygonal approximation of closed contours with minimum number of segments can be found by applying optimal algorithm for the open curves repeated for all possible starting points, or by using heuristic adjustment of the starting point. A better approach, however, is to extend the optimal algorithm from open to closed curves by extending the search space circularly. In this paper, we adopt this idea to the case of min-# problem. The proposed algorithm finds the optimal solution in less than 1.5 times of the time required by the open curve.

A robust shape matching approach should be invariable to rotation, displacement, scale as well as independence to the distortion caused by noise and segmentation error. The outline of a shape image is described using Haar's function. A multi-scale shape matching approach is presented based on discrete curve evolution. Some algorithm about the hierarchical polygon evolution and the comparability measurement degree for two outlines are put forward. The experimental studies are carried using Haar's transformation under different maximum transformation error. The results shows that the approach studied not only decomposes 2D object into polygonal curve but also induces a hierarchical structure of shape, and that combining "coarse level" with "fine level" in hierarchical similar matching, the retrieval of shape image can be effective for both retrieval accuracy and efficiency.

Fast algorithm for joint near-optimal approximation of multiple polygonal curves is proposed. It is based on iterative reduced-search dynamic programming introduced earlier for the min-/spl epsiv/ problem of a single polygonal curve. The proposed algorithm jointly optimizes the number of line segments allocated to the different individual curves, and the approximation of the curves by the given number of segments. Trade-off between time and optimality is controlled by the breadth of (the search, and by the numbers of iterations applied.

This paper describes a new computational method for creating a triangular and quadrilateral mesh of an arbitrary polygonal surface while controlling the anisotropy and directionality of the mesh. The input polygonal surface may include non-manifold edges and holes, and it can be either a closed polyhedron or an open polygonal surface. The method creates a mesh in two steps. In the first step, volumetric cells are packed - ellipsoidal bubbles for a triangular mesh or rectangular solid bubbles for a quadrilateral mesh - on the input polygonal surface, then vertices are created at the centers of the bubbles and superimposed onto the input polygonal surface. In the second step, the original vertices of the input polygonal surface are deleted. The method is tolerant to the noise typically introduced by the measurement error of a laser range scanner, it can control element size and anisotropy precisely, and it creates high quality mesh elements. Applications of the proposed scheme include: reducing the number of elements of a mesh created by a laser range scanner, CT scanner, or MRI scanner; creating a surface mesh that can be a starting mesh for a tetrahedral or a hexahedral finite element mesh; and solution-adaptive anisotropic remeshing for finite element analysis.

Summary form only given. A polygonal complex is a polygonal mesh that defines a curve with additional differential information such as tangent plane or normal and curvature values. In this sense, a polygonal complex corresponds to a curve interpolated by the limit surface of any polygonal mesh embodying it. We advance an approach for the deformation of subdivision surfaces under interpolation constraints. This is achieved by allowing the user to tag a configuration consisting of points, points with normal, or even control polygons and to deform the surface while maintaining the interpolation constraints. The constraints information can be converted, by means of a graphical user interface, into scalars defining various transformation parameters which have the ability to deform the surface when applied to the faces of the complex.

A method of improving the traditional polygonal approximation methods is described. It has properties such as scalability, resilience to noise, controlled levels of approximation and good visual representation. These properties are a direct result of the use of scale space information to derive the vertices positions of the polygonal approximation. The vertices are situated on the contour points where the changes of the contour directions are at their major sharp positions. An encoding method with a scalable polygonal approximation of shapes is defined, which results in a good relation between the distortion and the bit rate.

We show that the minimum value of a distance measure between 3-D polygonal arcs of equal length is the smallest eigenvalue of a certain matrix. Using this we develop a mismatch measure and a matching algorithm for 3-D polygonal arcs of unequal lengths.

The Fourier descriptors {A/sub n/, /spl alpha//sub n/}/sub 1//sup /spl infin// are proper for the analysis and synthesis of closed plane curves. Using tactile matrix sensors for the exploration of the 2D-shapes, binary imprints are often generated. An algorithm for computing the Fourier descriptors of the polygonal curve /spl gamma/ (Freeman outline) obtained by processing a binary imprint is proposed. First the coordinates of the curve starting point as well as the parameters /spl delta//sub 0/, a*/sub p/, /spl Delta/l/sub p/, /spl Delta//spl phi//sub p/ are determined; then L and the Fourier descriptors are computed. The most important properties of {A/sub n/, /spl alpha//sub n/}/sub 1//sup /spl infin// are presented and verified using the program that implements this algorithm. Knowing the Fourier descriptors of the shape binary outlines, much useful information for the description and tactile recognition of the shape have been obtained.

This paper addresses the problem of computing stable grasps of 2-D polygonal objects. We consider the case of a hand equipped with three hard fingers and assume point contact with friction. We prove new sufficient conditions for equilibrium and force closure that are linear in the unknown grasp parameters. This reduces computing the stable grasp regions in configuration space to constructing the three-dimensional projection of a five-dimensional polytope. We present an efficient projection algorithm based on linear programming and variable elimination among linear constraints. Maximal object segments where fingers can be positioned independently while ensuring force closure are found by linear optimization within the grasp regions. The approach has been implemented and several examples are presented.