An improved error-diffusion approach for generating mesh models of images

• We propose a mesh-generation framework for image representation.
• Our framework is based on the Yang–Wernick–Brankov error-diffusion (ED) method.
• We propose two mesh-generation methods derived from our framework.
• We show that the proposed methods perform much better than the ED method.

In earlier work, Yang et al. proposed a highly-effective technique for generating triangle-mesh models of images, known as the error diffusion (ED) method. Unfortunately, the ED method, which chooses triangulation connectivity via a Delaunay triangulation, typically yields triangulations in which many triangulation edges crosscut image edges, leading to increased approximation error. In this paper, we propose a computational framework for mesh generation that modifies the ED method to use data-dependent triangulations (DDTs) in conjunction with the Lawson local optimization procedure (LOP) and has several free parameters. Based on experimentation, we recommend two particular choices for these parameters, yielding two specific mesh-generation methods, known as MED1 and MED2, which make different tradeoffs between approximation quality and computational cost. Through the use of DDTs and the LOP, triangulation connectivity can be chosen optimally so as to minimize approximation error. As part of our work, two novel optimality criteria for the LOP are proposed, both of which are shown to outperform other well known criteria from the literature. Through experimental results, our MED1 and MED2 methods are shown to yield image approximations of substantially higher quality than those obtained with the ED method, at a relatively modest computational cost.