Fast polygonal approximation of digital curves using relaxed straightness properties

Several existing DSS (digital straight line segment) recognition algorithms can be used to determine the digital straightness of a given one-pixel-thick digital curve. Because of the inherent geometric constraints of digital straightness, these algorithms often produce a large number of segments to cover a given digital curve representing a real-life object=image. Thus, a curve segment, which is not exactly digitally straight, but appears to be visually straight, is fragmented into multiple DSS when these algorithms are run. In this paper, a new concept of approximate straightness is introduced by relaxing certain conditions of DSS, and an algorithm is described to extract those segments from a digital curve. The number of such segments required to cover the curve is found to be significantly fewer than that of the exact DSS-cover. As a result, the data set required for representing a curve also reduces to a large extent. The extracted set of segments can further be combined to determine a compact polygonal approximation of a digital curve based on certain approximation criteria and a specified error tolerance. The proposed algorithm involves only primitive integer operations and thus runs very fast compared to those based on exact DSS. The overall time complexity becomes linear in the number of points present in the representative set. Experimental results on several digital curves demonstrate the speed, elegance and efficacy of the proposed method.     

Techniques for assessing polygonal approximations of curves

Given the enormous number of available methods for finding polygonal approximations to curves techniques are required to assess different algorithms. Some of the standard approaches are shown to be unsuitable if the approximations contain varying numbers of lines. Instead, we suggest assessing an algorithm's results relative to an optimal polygon, and describe a measure which combines the relative fidelity and efficiency of a curve segmentation. We use this measure to compare the application of 23 algorithms to a curve first used by Teh and Chin (1989); their integral square errors (ISEs) are assessed relative to the optimal ISE. In addition, using an example of pose estimation, it is shown how goal-directed evaluation can be used to select an appropriate assessment criterion     

Fast polygonal approximation of digitized curves

We describe a new technique for fast “scan-along” computation of piecewise linear approximations of digital curves in 2-space. Our method is derived from earlier work on the theory of minimum-perimeter polygonal approximations of digitized closed curves.We demonstrate the specialization of this technique to the case where the error is measured as the largest Hausdorff-Euclidean distance between the approximation and the given digitized curve. We illustrate the application of this procedure to the boundaries of the images of a lung and a rib in chest radiographs.     

Speeding up simplification of polygonal curves using nested approximations

We develop a top-down multiresolution algorithm (TDMR) to solve iteratively the problem of polygonal curve approximation. This algorithm provides nested polygonal approximations of an input curve. We show theoretically and experimentally that, if the simplification algorithm A{\mathcal{A}} used between any two successive levels of resolution satisfies some conditions, the multiresolution algorithm will have a complexity lower than the complexity of A{\mathcal{A}} applied directly on the input curve to provide the crudest polygonal approximation. In particular, we show that if A{\mathcal{A}} has a O(N ²/K) complexity (the complexity of a reduced search dynamic programming solution approach), where N and K are, respectively, the number of segments in the input curve and the number of segments in the crudest approximation, the complexity of MR is in O(N). We experimentally compare the outcomes of TDMR with those of the optimal full search dynamic programming solution and of classical merge and split approaches. The experimental evaluations confirm the theoretical derivations and show that the proposed approach evaluated on 2D coastal maps either leads to a lower complexity or provides polygonal approximations closer to the initial curves.     

Curvature-based blending of closed planar curves

A common way of blending between two planar curves is to linearly interpolate their signed curvature functions and to reconstruct the intermediate curve from the interpolated curvature values. But if both input curves are closed, this strategy can lead to open intermediate curves. We present a new algorithm for solving this problem, which finds the closed curve whose curvature is closest to the interpolated values. Our method relies on the definition of a suitable metric for measuring the distance between two planar curves and an appropriate discretization of the signed curvature functions.     

Efficient convex hull computation for planar freeform curves

We present an efficient real-time algorithm for computing the precise convex hulls of planar freeform curves. For this purpose, the planar curves are initially approximated with G¹-biarcs within a given error bound ε in a preprocessing step. The algorithm is based on an efficient construction of approximate convex hulls using circular arcs. The majority of redundant curve segments can be eliminated using simple geometric tests on circular arcs. In several experimental results, we demonstrate the effectiveness of the proposed approach, which shows the performance improvement in the range of 200-300 times speed up compared with the previous results (Elber et al., 2001) [8].     

Genetic particle swarm optimization for polygonal approximation of digital curves

Polygonal approximation is an important technique in image representation which directly impacts on the accuracy and efficacy of the subsequent image analysis tasks. This paper presents a new polygonal approximation approach based on particle swarm optimization (PSO). The original PSO is customized to continuous function value optimization. To facilitate the applicability of PSO to combinatorial optimization involving the problem in question, genetic reproduction mechanisms, namely crossover and mutation, are incorporated into PSO. We also propose a hybrid strategy embedding a segment-adjusting-and-merging optimizer into the genetic PSO evolutionary iterations to enhance its performance. The experimental results show that the proposed genetic PSO significantly improves the search efficacy of PSO for the polygonal approximation problem, and the hybrid strategy can accelerate the convergence speed but still with good-quality results. The performance of the proposed method is compared to existing approaches on both synthesized and real image curves. It is shown that the proposed hybrid genetic PSO outperforms the polygonal approximation approaches based on genetic algorithms and ant colony algorithms. The text was submitted by the author in English. Peng-Yeng Yin was born in 1966 and received his B.S., M.S. and Ph.D. degrees in Computer Science from National Chiao Tung University, Hsinchu, Taiwan, in 1989, 1991 and 1994, respectively. From 1993 to 1994, he was a visiting scholar at the Department of Electrical Engineering, University of Maryland, and the Department of Radiology, Georgetown University. In 2000, he was a visiting Associate Professor in the Visualization and Intelligent Systems Lab (VISLab) at the Department of Electrical Engineering, University of California, Riverside (UCR). He is currently a Professor at the Department of Information Management, National Chi Nan University, Nantou, Taiwan. His current research interests include image processing, pattern recognition, machine learning, computational biology, and evolutionary computation. He has published more than 70 articles in refereed journals and conferences. Dr. Yin received the Overseas Research Fellowship from the Ministry of Education in 1993 and Overseas Research Fellowship from the National Science Council in 2000. He is a member of the Phi Tau Phi Scholastic Honor Society and listed in Who’s Who in the World.     

Ant colony search algorithms for optimal polygonal approximation of plane curves

This paper presents a new polygonal approximation method using ant colony search algorithm. The problem is represented by a directed graph such that the objective of the original problem becomes to find the shortest closed circuit on the graph under the problem-specific constraints. A number of artificial ants are distributed on the graph and communicate with one another through the pheromone trails which are a form of the long-term memory guiding the future exploration of the graph. The important properties of the proposed method are thoroughly investigated. The performance of the proposed method as compared to those of the genetic-based and the tabu search-based approaches is very promising.     

Efficient computation of optimal space-time performance curves for memory hierarchies

The problem of determining the best possible space-time performance for a given program executing in a two-level memory hierarchy for a given access time ratio is known to be computationally expensive. That one often wishes to determine such optimal performance across a broad range of access time ratios changes an expensive computational task into one which is often not feasible. We present a technique by which, given an acceptable error bound, a piecewise linear approximation to the actual space-time vs. access time ratio curve may be efficiently derived. That approximation is shown to deviate from the actual curve by no more than specified by the error bound. Such curves are useful in performance evaluation studies for memory management schemes in which the allocation of real memory is dynamically varied.     

Handwritten multilingual word segmentation using polygonal approximation of digital curves for Indian languages

Multimedia Tools and Applications - Multilingual Optical Character Recognition (OCR) is difficult to develop as different languages exhibit different writing and structural characteristics and it...     

Polygonal approximation of digital planar curves through break point suppression

This paper presents a new algorithm that detects a set of dominant points on the boundary of an eight-connected shape to obtain a polygonal approximation of the shape itself. The set of dominant points is obtained from the original break points of the initial boundary, where the integral square is zero. For this goal, most of the original break points are deleted by suppressing those whose perpendicular distance to an approximating straight line is lower than a variable threshold value. The proposed algorithm iteratively deletes redundant break points until the required approximation, which relies on a decrease in the length of the contour and the highest error, is achieved. A comparative experiment with another commonly used algorithm showed that the proposed method produced efficient and effective polygonal approximations for digital planar curves with features of several sizes.     

Fast computation of exact Zernike moments using cascaded digital filters

Zernike moments have been extensively used and have received much research attention in a number of fields: object recognition, image reconstruction, image segmentation, edge detection and biomedical imaging. However, computation of these moments is time consuming. Thus, we present a fast computation technique to calculate exact Zernike moments by using cascaded digital filters. The novelty of the method proposed in this paper lies in the computation of exact geometric moments directly from digital filter outputs, without the need to first compute geometric moments. The mathematical relationship between digital filter outputs and exact geometric moments is derived and then they are used in the formulation of exact Zernike moments. A comparison of the speed of performance of the proposed algorithm with other state-of-the-art alternatives shows that the proposed algorithm betters current computation time and uses less memory.     

Fast decomposition of digital curves into polygons using the Haartransform

The perimeters of features in digital images are decomposed into sets of straight lines using the Haar transform. The Haar basis functions preserve sharp changes in direction along the perimeter while still allowing smoothing. The coefficients of the Haar transform are simply related to the error between the polygonal decomposition and the true perimeter. The Haar transform can be calculated efficiently with a computational overhead linear in the number of data points     

Fast iterative computation of Gaussian mixture parameters and optimal image segmentation

We present a fast and accurate parameter estimation method for image segmentation using the maximum-likelihood function. The segmentation is based on a parametric model in which the probability density function of the grey levels in the image is assumed to be a mixture of two Gaussian density functions. For more accurate parameter estimation and segmentation, the algorithm is formulated as a compact iterative scheme. In order to reduce the computation time and to make convergence fast, histogram information is combined into the algorithm. Estimates of the initial values are properly selected for fast convergence. In addition, we find the optimal threshold values for several different types of mixture density which have one, two or no intersections between two component densities. The performance of the algorithm is evaluated on a set of artificial and real images and compared with those of other algorithms as well.     

Precise Hausdorff distance computation for planar freeform curves using biarcs and depth buffer

We present a real-time algorithm for computing the precise Hausdorff Distance (HD) between two planar freeform curves. The algorithm is based on an effective technique that approximates each curve with a sequence of G ¹ biarcs within an arbitrary error bound. The distance map for the union of arcs is then given as the lower envelope of trimmed truncated circular cones, which can be rendered efficiently to the graphics hardware depth buffer. By sampling the distance map along the other curve, we can estimate a lower bound for the HD and eliminate many redundant curve segments using the lower bound. For the remaining curve segments, we read the distance map and detect the pixel(s) with the maximum distance. Checking a small neighborhood of the maximum-distance pixel, we can reduce the computation to considerably smaller subproblems, where we employ a multivariate equation solver for an accurate solution to the original problem. We demonstrate the effectiveness of the proposed approach using several experimental results.     

Bisector curves of planar rational curves

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C₁(t) and C₂(r) as an implicit curve (t,r)=0, where (t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve (t,r)=0 has degree 4m−2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.     

A hybrid computer-aided linkage design system for tracing open and closed planar curves

This paper presents a computer-aided linkage design system for tracing prescribed open or closed planar curves. The mechanism design is considered a mixture of science and art. The former is about utilizing computers to rigorously size a mechanism in meeting a set of design requirements and the latter is about taking advantage of designers’ experience to narrow down the design domain and speed up the design process. The ultimate goal of the presented design system is to incorporate both science and art into the linkage design process by (1) developing an automatic design framework that is based on library searching and optimization techniques and (2) developing an interactive design framework that is based on advanced human–computer interfaces. To enable the design automation framework, we first pre-built a library of open and closed planar curves generated by commonly used planar linkages. We then turned the classical linkage path generation problem into a library searching problem together with a local optimization problem. To enable the interactive design framework, we developed a set of design interfaces that facilitate designers to intervene and steer the design process. This hybrid design system was developed based on our existing VRMDS (Virtual Reality Mechanism Design Studio) framework. To demonstrate its functionalities, we provided four representative design cases of 4-bar and crank-slider linkages. The result shows that the system returned a desired solution in seconds. We also demonstrate the extensibility of the system by implementing designs of planar 4-bar and crank-slider linkages.     

Fast clear-sky solar irradiation computation for very large digital elevation models

This paper presents a fast algorithm to compute the global clear-sky irradiation, appropriate for extended high-resolution Digital Elevation Models (DEMs). The latest equations published in the European Solar Radiation Atlas (ESRA) have been used as a starting point for the proposed model and solved using a numerical method. A new calculation reordering has been performed to (1) substantially diminish the computational requirements, and (2) to reduce dependence on both, the DEM size and the simulated period, i.e., the period during which the irradiation is calculated. All relevant parameters related to shadowing, atmospheric, and climatological factors have been considered. The computational results demonstrate that the obtained implementation is faster by many orders of magnitude than all existing advanced irradiation models while maintaining accuracy. Although this paper focuses on the clear-sky irradiation, the developed software also computes the global irradiation applying a filter that considers the clear-sky index.     

Robust adaptive polygonal approximation of implicit curves

We present an algorithm for computing a robust adaptive polygonal approximation of an implicit curve in the plane. The approximation is adapted to the geometry of the curve because the length of the edges varies with the curvature of the curve. Robustness is achieved by combining interval arithmetic and automatic differentiation.     

Induced rational approximations of transcendental curves

A novel technique for the construction of positive weight high-precision rational approximations to a class of transcendental curves is presented. The approximations are induced from the rational parametrisations of the circle. The previously published rational parametrisations of the circle are not suited to the induction process and the new parametrisations are constructed in the paper for the purpose. Explicit rational approximations of a number of transcendental curves are then given. The work is a development of the authors’ previous work on induced rational parametrisations of special algebraic curves.