A hybrid refinement/decimation triangulation method for image approximation

This paper proposes an improved method for image approximation. The proposed method includes two novel points. The first is the dynamic structure of the triangulation, which the refinement and decimation processes are repeatedly applying in order to optimize the distribution of the vertices. The second is the novel vertex selection methods that improve the performance considerably. In the refinement step vertices are selected by a new algorithm with the new selection scheme. This step has a structure similar to the incremental Delaunay triangulation algorithm which adds vertices in a greedy way. The decimation step is based on the near-optimal adaptive thinning algorithm, which removes vertices in a greedy way. Repeatedly applying these two steps, the data points will be organized in a better configuration, raising the signal to noise ratio, while preserving the number of vertices. Comparative results shown in this paper indicates the superiority of the proposed algorithm over other incremental and decimation methods, including adaptive thinning for modeling images, which itself is known to be competitor of JPEG2000.