| The triangulation algorithm of image uses triangular mesh to represent the image, which is a model-based image coding technique. The image representation method based on triangular mesh is a new model-based image coding method which can represent the image effectively. It has been widely used in the motion estimation, motion compensation and image compression, and the operability of the triangular mesh is also one of its prospects.With respect to mathematical methods in computational geometry and related algorithms in image processing, two triangulation algorithms of image have been mainly researched and optimized.Delaunay triangulation algorithm is an algorithm which base on the image boundary feature extraction for triangular mesh. The algorithm using polygon growing algorithm to extract the vertices of the polygon as the initial point set, and then taken advantage of Lawson algorithm to generate the initial triangular mesh. The results show that: Compared with the traditional feature extraction algorithm,the number of characteristic points of polygon growing algorithm decreases by more than 12%. Significantly improve image quality, PSNR values increased by 8% to 12%.Triangular mesh generated by Delaunay algorithm is a convex hull. We do optimization to solve this problem. The input of Delaunay algorithm is a discrete set of points. Triangular mesh formed by these points can not fully cover the whole image. Optimization algorithm discovers the image area that is not covered first. Then split the area into several polygons, which will be triangulate in order to get the triangular mesh of full picture. After using this optimization algorithm, the noise ratio of reconstructed image increased by 2% ~ 3%.With respect to image content, a two-way template based triangulation algorithm is proposed. First of all, three pairs of two-way template and a diagonal template are defined. The original image is divided into 256 rectangular blocks with multi-stage wavelet transform. Each rectangular block can be represented by the corresponding template base on the original image intensity distribution. And then triangulate the template mesh to get the triangular mesh of the whole image. The Experimental results show that the size of the triangular mesh generated by TBT algorithm is half of the one generated by Delaunay algorithm in the case of little difference in image quality. And the mesh is more consistent with the image content. Experimental result of TBT algorithm is better than WBT algorithm. The size of its triangular mesh is a litter smaller than the WBT algorithm. And TBT algorithm is simple and low complexity.In order to improve the quality of reconstructed image, triangular mesh subdivision needs to be done. Take the maximum image intensity error as grading standards, and continuously insert into sub-points. We can see reconstructed image is closer and closer to the original image with the expansion of the triangular mesh. Experimental results show that, the reconstructed image of PSNR values increase by 66% after subdivision, and subjective and objective evaluation of results have greatly improved.Considering both of the size of triangular mesh and the quality of reconstructed image, an algorithm is proposed to reduce the size of triangular mesh when there is little effect in the quality of reconstructed image. Algorithm use a variable called flatness to analyze whether the points can be removed. After using this algorithm, the size of the triangular mesh reduce by 10% with the reconstructed image PSNR values decrease about 2%.Based on the characteristics of TBT algorithm, a data storage structure is put forward to store the triangular mesh by binary data stream. This structure records only the template and the sub-points. According to the inverse process of storage method, we can open this file format. The storage method is a very effective image compression algorithm. The compression ratio can reach 4 or above basically when the size of triangular mesh is not very large. |
PDF Full Text Request