基于Delaunay三角剖分的图象变形技术研究

Research on Metamorphosis Using Delaunay Triangulation

提出了一种新的图象变形方法 ,即基于 Delaunay三角剖分的图象变形方法 .与四边形网格方法相比 ,用三角形网格定义特征区域 ,特征点的选取更自由、数目更少 .针对变形过程中运算量最大的坐标变换 ,提出了一种基于 Bresenham算法的坐标变换算法 .该算法完全采用加减运算 ,避免了乘法及舍入取整运算 ,大大加快了图象变形的运算速度 .计算机仿真试验表明 ,在同等数目控制点的条件下 ,该算法变形效果及运算速度均优于四边形网格方法 .

This paper presents a new method to implement the digital image morphing based on Delaunay triangulation. Contrasting to the usually used quadrilateral meshes, the character regions are defined by triangular meshes, which can allow a more freely selection of control points and much less number of the selected control points. The two triangular meshes are determined by the corresponding control points on the two morphing images. In order to define a unique triangular mesh using a set of points on the integer grids as in digital images, three additional criterions are proposed as the complementary rule to the Delaunay triangulation. According to the large amount of computation in the coordinate transform process, a new algorithm of coordinate transform is presented based on the classical Bresenham algorithm, only addition and subtraction computation is employed, the multiplication and round computation are avoided, and then the whole process was accelerated greatly. With the new method a satisfying morphing result has been acquired.