Fast computation of optimal polygonal approximations of digital planar closed curves
| Autor: | Manuel J. Marín-Jiménez, F. J. Madrid-Cuevas, E.J. Aguilera-Aguilera, A. Carmona-Poyato |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Computation 02 engineering and technology Real image 01 natural sciences Computer Graphics and Computer-Aided Design Square (algebra) Distortion (mathematics) Set (abstract data type) Modeling and Simulation Polygonal chain Discrete optimization 0103 physical sciences 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Geometry and Topology 010306 general physics Integer programming Algorithm Software Mathematics |
| Zdroj: | Graphical Models. 84:15-27 |
| ISSN: | 1524-0703 |
| DOI: | 10.1016/j.gmod.2016.01.004 |
| Popis: | A novel method to solve the min-# polygonal approximation problem is proposed.The approach uses a modified Mixed Integer Programming model to solve the min-# problem.The proposed model is smaller than previous proposals.The novel procedure obtains the optimal solution faster than state-of-the-art methods.Only one execution of our procedure is needed to assure the optimality of the solution. Display Omitted 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect