An algorithm for polygonal approximation of a digital object

A fast and simple heuristic algorithm for polygonal approximation is presented. The algorithm is based on a mark and sweep technique. Results of computer implementation with various images are reported.     

物体轮廓线的多边形拟合

本文讨论了在给定数字轮廓线顶点数目为N的情况下，从其上选择k个点来构造拟和多边形来近似原图，使得物体轮廓线的形状丢失最小。本文的贡献在于1）本文的轮廓线拟和是以物体轮廓线的形状的信息丢失最小为目标的。而传统的方法是以拟和多边形和原图的面积差距最小。2）本文认为每一个点具有一定的形状信息，然后建立了一个以丢失的形状信息最小的0—1规划模型：3）使用了两种方：去对轮廓线进行了多边形拟合，并把两个结果进行了比较。     

物体轮廓线的多边形拟合

本文讨论了在给定数字轮廓线顶点数目为N的情况下,从其上选择k个点来构造拟和多边形来近似原图,使得物体轮廓线的形状丢失最小。本文的贡献在于1)本文的轮廓线拟和是以物体轮廓线的形状的信息丢失最小为目标的。而传统的方法是以拟和多边形和原图的面积差距最小。2)本文认为每一个点具有一定的形状信息,然后建立了一个以丢失的形状信息最小的0-1规划模型;3)使用了两种方法对轮廓线进行了多边形拟合,并把两个结果进行了比较。     

A topology-preserving parallel 3D thinning algorithm for extracting the curve skeleton

We introduce a new topology-preserving 3D thinning procedure for deriving the curve voxel skeleton from 3D binary digital images. Based on a rigorously defined classification procedure, the algorithm consists of sequential thinning iterations each characterized by six parallel directional sub-iterations followed by a set of sequential sub-iterations. The algorithm is shown to produce concise and geometrically accurate 3D curve skeletons. The thinning algorithm is also insensitive to object rotation and only moderately sensitive to noise. Although this thinning procedure is valid for curve skeleton extraction of general elongated objects, in this paper, we specifically discuss its application to the orientation modeling of trabecular biological tissues.     

Step response classification for model-based autotuning via polygonal curve approximation

A model-based autotuning method consists of an identification and a regulator tuning phase. To achieve satisfactory performance and robustness, it is advisable that both phases be tailored a priori to the characteristics of the observed process dynamics. Such characteristics include, but are not limited to, the model structure. For example, overdamped and underdamped models with the same pole-zero structure are parametrised and controlled in different ways. Step response data, that are typically used for the identification phase in the autotuning context, can also be pre-processed to reveal those characteristics. This paper presents a step response classification method suitable for the above purpose. The method is based on a polygonal curve approximation technique for data pre-processing, followed by a neural network classifier. Only normalised I/O data are employed, so that the neural network can be trained off-line with simulated data. Simulation results are reported to show the effectiveness of the proposed classification method in terms of the achievable tuning results.     

An efficient evolutionary algorithm for accurate polygonal approximation

An optimization problem for polygonal approximation of 2-D shapes is investigated in this paper. The optimization problem for a digital contour of N points with the approximating polygon of K vertices has a search space of C(N, K) instances, i.e., the number of ways of choosing K vertices out of N points. A genetic-algorithm-based method has been proposed for determining the optimal polygons of digital curves, and its performance is better than that of several existing methods for the polygonal approximation problems. This paper proposes an efficient evolutionary algorithm (EEA) with a novel orthogonal array crossover for obtaining the optimal solution to the polygonal approximation problem. It is shown empirically that the proposed EEA outperforms the existing genetic-algorithm-based method under the same cost conditions in terms of the quality of the best solution, average solution, variance of solutions, and the convergence speed, especially in solving large polygonal approximation problems.     

A new shape preserving parallel thinning algorithm for 3D digital images

This paper is concerned with a new parallel thinning algorithm for three-dimensional digital images that preserves the topology and maintains their shape. We introduce an approach of selecting shape points and outer-layer used for erosion during each iteration. The approach produces good skeleton for different types of corners. The concept of using two image versions in thinning is introduced and its necessity in parallel thinning is justified. The robustness of the algorithm under pseudo-random noise as well as rotation with respect to shape properties is studied and the results are found to be satisfactory.     

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.     

An O(N) algorithm for polygonal approximation

A new, sequential algorithm for polygonal approximation of plane, closed curves is presented. It runs in O(N) time and is based on a tolerance independent of the scale factor.     

A simple algorithm for detection of significant vertices for polygonal approximation of chain-coded curves

A simple but efficient method is proposed for detection of significant points of chain-coded curves. The polygonal approximation is achieved by joining successive significant vertices. The algorithm is based on manipulation with chain codes only.     

A modified fast parallel algorithm for thinning digital patterns

A modified version of the fast parallel thinning algorithm proposed by Zhang and Suen is presented in this paper. It preserves the original merits such as the contour noise immunity and good effect in thinning crossing lines; and overcomes the original demerits such as the serious shrinking and line connectivity problems.     

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.     

A new subdivision based approach for piecewise smooth approximation of 3D polygonal curves

This paper presents an algorithm dealing with the data reduction and the approximation of 3D polygonal curves. Our method is able to approximate efficiently a set of straight 3D segments or points with a piecewise smooth subdivision curve, in a near optimal way in terms of control point number. Our algorithm is a generalization for subdivision rules, including sharp vertex processing, of the Active B-Spline Curve developed by Pottmann et al. We have also developed a theoretically demonstrated approach, analysing curvature properties of B-Splines, which computes a near optimal evaluation of the initial number and positions of control points. Moreover, our original Active Footpoint Parameterization method prevents wrong matching problems occurring particularly for self-intersecting curves. Thus, the stability of the algorithm is highly increased. Our method was tested on different sets of curves and gives satisfying results regarding to approximation error, convergence speed and compression rate. This method is in line with a larger 3D CAD object compression scheme by piecewise subdivision surface approximation. The objective is to fit a subdivision surface on a target patch by first fitting its boundary with a subdivision curve whose control polygon will represent the boundary of the surface control polyhedron.     

三次插值样条曲线拟合多核并行算法

充分利用多核技术提升多核处理器的资源利用率,缩短执行时间,发挥多核系统的优异性能。在多核计算机上设计了解三对角方程组的奇偶约化多线程并行程序,实现了三次样条曲线拟合的快速计算。通过实验结果的加速比对比,可以看出并行后缩短了求解方程组的时间,多核资源得到充分利用。结果表明,奇偶约化多核并行算法在三次样条曲线拟合中的应用是有效及可行的。     

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...     

An algorithm for detection of dominant points and polygonal approximation of digitized curves

A new technique for the detection of dominant points and polygonal approximation of digitized curves is proposed. The procedure needs no input parameter and remains reliable even when features of multiple size are present. Unlike the existing algorithms, the present technique introduces the concept of an asymmetric region of support and k-l-cosine. The dominant points are the local maxima of k-l-cosine. The polygon is obtained joining the dominant points successively.     

An adaptive steganographic algorithm for 3D polygonal meshes

This paper presents a new adaptive digital steganographic technique for three-dimensional (3D) polygonal meshes. It is based on an adaptive substitutive blind procedure in the spatial domain. We use angle features to remove all restrictions of fixed embedding size in each vertex to provide larger embedding capacity and to minimize the distortion by minimum distortion distance estimation. This method exploits the correlation between neighboring polygons with respect to the human visual system to estimate the degree of smoothness or roughness properties. If the vertex is located on a rough surface, then it may tolerate larger position changes by embedding more messages than those on smooth surfaces. Our method provides an easy way to produce a more imperceptible result. In addition, a simple contagious diffusion technique is devoted to improving performance for polygonal meshes traversal. Experimental results show that the proposed technique is adaptive, simple, efficient, general, and secure. This technique has high capacity and low distortion, and it is robust against affine transformations. Our technique provides an adaptive method and has proven feasible in steganography.     

A novel parallel hybrid intelligence optimization algorithm for a function approximation problem

A novel parallel hybrid intelligence optimization algorithm (PHIOA) is proposed based on combining the merits of particle swarm optimization with genetic algorithms. The PHIOA uses the ideas of selection, crossover and mutation from genetic algorithms (GAs) and the update velocity and situation of particle swarm optimization (PSO) under the independence of PSO and GAs. The proposed algorithm divides the individuals into two equation groups according to their fitness values. The subgroup of the top fitness values is evolved by GAs and the other subgroup is evolved by the PSO algorithm. The optimal number is selected as a global optimum at every circulation which shows better results than both PSO and GAs, then improves the overall performance of the algorithm. The PHIOA is used to optimize the structure and parameters of the fuzzy neural network. Finally, the experimental results have demonstrated the superiority of the proposed PHIOA to search the global optimal solution. The PHIOA can improve the error accuracy while speeding up the convergence process, and effectively avoid the premature convergence to compare with the existing methods.