CN107256557B - Error-controllable subdivision surface image vectorization method - Google Patents

Abstract

The invention discloses an error-controllable subdivision surface image vectorization method, comprising the following steps: 1) detecting edge features of an image to obtain an initial image feature line segment with a width of one pixel; 2) constructing an initial grid based on the image features, And mark the image features in the grid; 3) Simplify the initial grid to construct a base grid that maintains the image features; 4) Obtain the control grid by fitting the loop subdivision surface with controllable error; 5) Rasterized vector representation. Given a raster image, the present invention can obtain a better vector image. If the error of the initial reconstruction result cannot meet the needs of the user, the present invention can measure the error between the vectorized reconstructed image and the original image. Adaptive subdivision is performed to achieve a specified error within a certain range, so that the error is controllable. The present invention studies image vectorization using subdivision surface technology, and aims to convert raster images into vector representations that meet error requirements, which has practical application value.

Description

An error-controllable subdivision surface image vectorization method

technical field

The invention relates to the field of image vectorization using subdivision surface technology, in particular to a subdivision surface image vectorization method with controllable error, which aims to convert a raster image into a vector representation that meets error requirements.

Background technique

In the computer, there are two typical representations of images, one is raster image, also known as bitmap, bitmap image, the other is vector image, also known as vector graphics, vector representation. Compared with raster images, vector graphics have many advantages, such as small storage, easy editing, resolution independent and so on. With the diversified development of display devices and the improvement of resolution, the advantages of vector images have become increasingly prominent. The purpose of image vectorization is to convert bitmap images into vector images.

In recent years, scholars have proposed many different image vectorization algorithms. A variety of different geometric primitives are proposed to represent vector graphics, including lines, curves, triangular meshes, parametric surfaces, subdivision surfaces, diffusion curves, etc. However, due to the complex characteristic curves and rich color changes of the image, these existing vector representations all have common difficulties. One is how to represent the original image well with fewer primitives, and the other is the vector representation. editability. Subdivision surfaces have many advantages, such as good smoothness, suitable for representing objects with arbitrary complex topology, and strong editability. In the literature [LIAO Z, HOPPE H, FORSYTH D, et al. A subdivision-based representation for vector imageediting [J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(11): 1858-1867.], Liao et al. A vector image editing algorithm based on piecewise smooth subdivision surface representation was proposed. The vector representation has powerful editability and can achieve multi-resolution. Under certain conditions, when the number of geometric primitives increases, the resolution will be higher, and vice versa. However, this algorithm also has some problems. First, the method models the discontinuity of color values on both sides of the image edge by splitting the sub-pixel edges, but the sub-pixel edge extraction used is not accurate enough, and the obtained color values on both sides are inaccurate, and The vectorization result is overly dependent on the base grid, and the error cannot be controlled. Therefore, the method of the framework is studied and improved in the present invention to achieve error control within a certain range.

SUMMARY OF THE INVENTION

The purpose of the present invention is to overcome the deficiencies of the image vectorization algorithm represented by the subdivision surface proposed by Liao et al., and propose a subdivision surface image vectorization method with a controllable error, which can achieve an error within a certain range for the vectorization result. Control to meet the user's error requirements.

In order to achieve the above purpose, the technical solution provided by the present invention is: a method for vectorizing a subdivision surface image with controllable error, comprising the following steps:

1) Detect image edge features

The image edge is the most significant image feature. In order to construct the base grid that maintains the image features, the image edge line segment detection method is used to extract the one-pixel-wide feature line of the image. The steps are:

①Gaussian filtering: Convolve the image with a Gaussian kernel to suppress image noise and smooth the image;

②Calculate the gradient magnitude and edge direction map: First, use the gradient operator to calculate the horizontal and vertical gradients of the pixel respectively, and then calculate the image gradient magnitude map. At the same time, compare the size of the horizontal and vertical gradients of the pixel to determine the pixel. The edge direction of the point, if the horizontal gradient is large, it is considered to be a vertical edge through the pixel, and vice versa;

③Extract anchor points: An anchor point can be considered as the end of the edge, that is, a pixel point with drastic feature changes in the horizontal and vertical directions. Here, the local gradient extreme value is selected as the anchor point, and the gradient between the pixel point and its adjacent pixels is compared. value to determine whether the pixel is an anchor point. For a horizontal pixel, compare it with the left and right adjacent pixels. If the gradient value of the pixel is greater than the gradient value of the left and right adjacent pixels by a specified threshold, it is considered that The pixel is the anchor point;

④ Connect anchor points to form line segments: Connect adjacent anchor points according to the gradient amplitude and edge direction map, starting from the anchor point that has not been detected each time, observe the edge direction passing through the anchor point, if it is a horizontal edge, The connection process is started by traveling left and right, if the vertical edge passes the anchor point, the connection process is performed by traveling up and down, during the movement, only three immediate neighbor pixels are considered, and the one with the largest gradient value is selected , when encountering a pixel with a gradient amplitude of 0 or encountering an edge pixel that has been detected before, the processing stops;

2) Construct an initial grid based on image features, and label image features in the grid

Build an initial triangular mesh M of pixel resolution on the 2D image plane. First establish the initial grid vertex, each pixel in the image corresponds to a vertex in the grid, and record the color value of the pixel in the vertex attribute; then connect the grid vertices in rows and columns to form a rectangular grid , which divides each rectangular grid in the grid into two triangular grids according to the image feature lines.

Image color discontinuities are associated with at least two adjacent pixels with very different color intensities, and image edge lines alone are not sufficient to represent image color discontinuities. Therefore, the present invention proposes to use a double characteristic line to represent the discontinuity of the color of the image. First, use the contour tracing algorithm to find the parallel line segments with a distance of one pixel on both sides of the image feature line, and then select the line segment with the larger average gradient as another feature line by comparing the image gradients on both sides. Retriangulate.

Next, the types of edges and vertices of the initial mesh are marked, so that different types are processed differently in subsequent operations such as mesh simplification, subdivision, etc. to maintain important image features. The invention divides the edges of the mesh into three types: boundary edge, smooth edge and crease edge, and divides the vertices of the mesh into four types: boundary point, smooth point, crease point and corner point. Label the double feature lines of the image as crease edges, the edges of the image matrix boundary as boundary edges, and the other edges as smooth edges. For mesh vertices, if the vertex is only connected with smooth edges, the vertex is marked as a smooth point; a crease vertex is connected with two adjacent crease edges; a boundary point is connected with two adjacent boundary edges; image feature line endpoints, Breakpoint intersections are marked as corners. To fix the rectangular image boundary, the four corners are marked as corner points.

3) Simplify the initial grid and construct a base grid that preserves image features

The QEM simplification algorithm is used to simplify the initial grid of the image, and the base grid MB is obtained. _The color attribute of the grid is regarded as a height field to calculate the quadratic error cost, and the subdivision curve is used to fit the image feature line during the simplification process. to preserve image features;

In the previous step, the vertices and edges of the mesh were classified according to the image features. In order to maintain the shape and characteristics of the image, different processing methods are adopted for different features: ① the corner points are not allowed to be folded; ② the boundary point can only be folded with two adjacent boundary points of the same boundary; ③ the crease point can only be folded with the same boundary The two adjacent crease points on the same crease edge are folded; ④The smooth point can be folded to the feature point.

的代价表示为：In addition, in order to obtain a high-quality base mesh that preserves image features, the edge folding cost of the QEM algorithm is improved, and the feature edge deformation cost Q _feature , the triangle regularity cost Q _re , and the area cost Q _area are added to the edge folding cost, and Give them corresponding weights, and use Q _{qem to} represent the QEM cost, then the edges can be folded

The cost is expressed as:

Cost(v ₁ ,v ₂ )=αQ _qem (v ₁ ,v ₂ )+βQ _feature (v ₁ ,v ₂ )+γQ _re (v ₁ ,v ₂ )+δQ _area (v ₁ ,v ₂ )(1 )

In the formula, the weights α, β, γ, and δ are specified by the user, and the order of edge folding is carried out according to Cost(v ₁ , v ₂ ) from small to large. It should be noted that, in order to ensure the quality of the simplified two-dimensional grid, except when calculating the QEM cost, the color attribute of the grid M is regarded as a height field, and when calculating other costs, only the two-dimensional image network is considered. grid, regardless of color properties. The definition of the QEM cost Q _qem , the characteristic edge deformation cost Q _feature , the triangle regularity cost Q _re , and the area cost Q _area are as follows:

QEM cost Q _qem : The quadratic error cost is used to calculate the quadratic error cost of the edge, which measures the distance from the point in the three-dimensional space to the plane, and the grid M is a two-dimensional grid, so the color attribute of the grid M is viewed form a height field, and use the RGB value as the height respectively, then each edge can calculate three costs, and use the sum as the quadratic error cost Q _qem of the edge;

Feature edge deformation cost Q _feature : The QEM cost does not take into account the sharp features of the model and cannot reflect the features of the image. Q _feature is defined as the distance between the feature point before folding and the line connecting the two adjacent feature points, which is used to measure the feature edge. The degree of deviation between the folding result and the folding point. The smaller the Q _feature value, the smaller the deviation. If the folded edge is a non-feature edge, the Q _feature value is 0;

Triangle regularity cost Q _re : The triangle regularity cost is added to the edge folding cost in order to reduce the appearance of long and narrow triangular patches. The regularity of a triangle is used to indicate the degree to which it is close to an equilateral triangle, which can be expressed by R(t)= cos(∠A)+cos(∠B)+cos(∠C) to measure the regularity of triangle t=ΔABC, let Re(t)=3-2R(t), then 0≤Re(t)≤1, The smaller the value of Re(t) is, the higher the regularity of the triangle is, and the regularity of the triangular patch set T is defined as:

Re(T)=max{Re(t)|t∈T} (2)

的正则性代价定义为：Define Q _re as the regularity increment of the relevant triangular patches before and after the edge is folded, then the edge is folded

The regularity cost of is defined as:

表示顶点

的邻接三角面片；in,

represents a vertex

The adjoining triangular patch of ;

的面积代价定义为：Area cost Q _area : The triangle regularity cost Q _re reflects the shape of the triangle patch, but not the size of the patch. Therefore, the area cost is added to the total cost to constrain the area of the patch, and the area cost Q _area is defined as edge folding After the sum of the areas of all adjacent faces of the new vertex, the edge is collapsed

The area cost of is defined as:

where area(t) represents the area of the triangle t.

Among them, the steps of the mesh simplification algorithm are as follows:

①Set the weights in the edge folding cost formula (1);

② Consider the color attribute of the grid M as a height field, and calculate the QEM cost Q _qem of all edges of the grid;

③ Calculate the folding cost of all foldable edges, put them into the minimum heap according to the folding cost, and calculate the folding cost of the two half-edges corresponding to each edge according to formula (1), then the folding cost of the edge takes two half-edge costs The small value of , and record the folding direction;

4. Take the edge with the smallest folding cost from the heap, and judge whether the relevant face will be flipped after it is folded. If so, add a penalty value to the cost of the edge and update its position in the heap; if it will not be reversed Flip, judge whether the edge is a feature edge, if it is a feature edge, fit and adjust the position of the feature point and judge whether the fitting error after folding meets the requirements, if not, do not fold the edge and delete it from the heap ; otherwise, complete the collapsing operation of the edge, recalculate the collapsing cost of the relevant edge and update their position in the heap;

⑤ If the simplified requirements are met or the minimum heap is empty, go to ⑥, otherwise go to ④;

⑥ Delete independent vertices in the mesh, update the mesh, and output the base mesh.

Although the patch regularity and area factors are considered in the mesh simplification process, a high-quality base mesh cannot be guaranteed, so the Laplacian operator is used to optimize the mesh geometry:

where N(v) and |N(v)| represent the set and number of all vertices in the 1-neighborhood of vertex v, respectively. The new positions of the vertices in the mesh are given iteratively by vnew = v+ ^λΔv , where λ takes the value 0.3.

In order to maintain the characteristics of the image, special processing is performed on the mesh feature vertices: first, the corners do not move. For the boundary vertex and feature point v, let (v _a , v ) and (v, v _b ) be the two locations where v is located. feature edges, then v is only adjusted according to the positions of v _a and v _b , that is, the Laplacian operator is defined as:

It should be noted that the mesh optimization can be performed during the mesh simplification process or after the mesh simplification is completed. If the mesh optimization will cause the patches to be flipped, the optimization will not be performed for the time being.

4) Control mesh obtained by loop subdivision surface fitting with controllable error

After grid simplification and optimization, the base grid reflecting the image features is obtained, and loop subdivision surface fitting with error control is proposed to fit the image color. In the process of calculating the control grid, the user can control the error. Obtain a vector image that meets your needs by specifying the error of the reconstructed image. The process mainly includes three parts: control grid calculation, error control and adaptive subdivision, as follows:

4.1) Control the calculation of the mesh.

然后使用网格

对原图像进行采样得到M_R，将M_R作为我们拟合的目标。像素点的颜色值在图像特征区域有着显著的变化，为了采样到准确的颜色值，我们对不同的网格特征采用不同的采样方式得到顶点的颜色值：对于折痕顶点，它的目标颜色为它所在的图像特征线上和它位置最接近的像素点的颜色值；对于角点，它在简化过程和细分过程中的位置都没有移动，所以它的目标颜色为顶点坐标确定的图像像素点的颜色值；对于平滑顶点，其颜色由其周围的像素点进行双线性插值得到。In order to increase the amount of data to fit the target, we first perform a 1-4 subdivision on the base grid _MB to obtain a grid

then use grid

Sampling the original image to get _MR , and take _MR as our fitting target. The color value of the pixel has a significant change in the image feature area. In order to sample the accurate color value, we use different sampling methods for different mesh features to obtain the color value of the vertex: for the crease vertex, its target color is The color value of the pixel point closest to its position on the image feature line where it is located; for corner points, its position has not moved during the simplification process and the subdivision process, so its target color is the image pixel determined by the vertex coordinates The color value of the point; for smooth vertices, the color is bilinearly interpolated from the surrounding pixels.

和M_R具有相同的拓扑关系。根据Loop极限模版求网格

的极限得到细分极限曲面M_S，拟合目标就是：In the process of mesh simplification, the feature vertex positions of the mesh have been fitted. For the convenience of calculation, only the colors of the mesh vertices are fitted here. Therefore, the control mesh M _C to be calculated and the base mesh _MB have the same topology. Therefore, the mesh obtained after a loop subdivision of the control mesh M _C

and _MR have the same topological relationship. Grid based on Loop limit template

The limit of the subdivision limit surface M _S is obtained, and the fitting objective is:

M _R = M _S (7)

表示网格M_C、M_R、

M_S的顶点颜色构成的向量，则根据带尖锐特征的Loop细分模版和极限模版，存在有细分矩阵S_m×n和极限矩阵L_m×m使得：

所以可以将Loop细分拟合方程(7)表示为：Let the number of vertices of the base mesh _{MB and the target mesh M C be} n and m, respectively.

Represents meshes _{M C} , MR ,

The vector formed by the vertex colors of M _S , according to the Loop subdivision template and limit template with sharp features, there are subdivision matrix S _m×n and limit matrix L _m×m such that:

So the Loop subdivision fitting equation (7) can be expressed as:

Let Z _m×n =L _m×m S _m×n , the equation system (8) is transformed into:

和

的大小分别为n×3和m×3，RGB三种颜色能够分开求解。The control mesh M _C can be obtained by solving the linear equation system (9), because the color of the mesh vertices is fitted here, so

and

The sizes are n×3 and m×3, respectively, and the three colors of RGB can be solved separately.

4.2) Error control.

The reconstruction error of each pixel is defined as the Euclidean distance between the reconstructed image and the color value of the corresponding pixel of the original image, and the reconstruction error e of the entire image is defined as the mean of the reconstruction errors of all pixels. The reconstruction error ^ef of a grid patch is defined as the mean of reconstruction errors of all pixel points corresponding to the patch after rasterization.

In the previous step, the control mesh is obtained by fitting the loop subdivision surface, so that the corresponding subdivision surface is as close to the original image as possible. However, the number of vertices of the control grid depends on the simplification of the grid. If the simplification is excessive, the number of vertices of the control grid is too small and the freedom is too large, which may lead to large reconstruction of the reconstructed image and the original image in some areas. Therefore, the present invention controls the reconstruction error of the image by adaptively subdividing the area with large error, so that the user can obtain the reconstructed image with the specified error.

For the calculation of the reconstruction error, the limit surface of the control grid is first estimated according to the Loop subdivision rule with sharp features and the limit rule, and the color value of each pixel on the limit surface is calculated, that is, the rasterized vector representation. Then, according to the base grid patch where each pixel point is located, the reconstruction error ^ef of each patch of the base grid is calculated. Finally, the error e of the entire reconstructed image is calculated. Through the above analysis, the process of obtaining the control grid with controllable error of the present invention is as follows:

① Backup the base mesh M _B , and use the Loop surface fitting method to calculate the control mesh M _C ;

② Estimating the limit surface M _S of the control grid M _C according to the fine loop division rule and the limit rule;

③ For the color value I(i) of each pixel point of the original raster image, calculate the color value I′(i) of the corresponding pixel point on the limit surface MS according to the _barycentric coordinates, calculate the pixel point error e _i , and find the pixel Point to the corresponding base mesh patch. Then calculate the average error ^ef of all pixels in each patch of the base grid _MB , and finally calculate the average reconstruction error e of the entire image;

④If the average reconstruction error e is less than the average error threshold ε specified by the user, terminate the algorithm and output the control grid M _C ; otherwise, find out the top k largest average error patch sets in the base grid M _B , and mark these The patch needs to be adaptively subdivided; where k ≥ 1 is specified by the user, in general, the larger the k, the faster the average error decreases.

⑤ Perform adaptive refinement on the marked base mesh to obtain a new base mesh _MB , then go to step ①, and continue the whole process until the reconstructed image with the specified error is obtained.

4.3) Adaptive subdivision

Adaptive subdivision allows subdividing only the area of interest. In error control, we need to locally increase the number of control vertices by adaptively subdividing the patches marked as not meeting the error requirements, thereby reducing the error. To avoid cracks in the new mesh, we must subdivide both the marked patch and its neighbors. For the marked mesh patch, we subdivide it 1-4. For the unmarked patch, we subdivide it according to the situation of its adjacent faces being marked: ① If the patch has 0 If the adjacent face is marked, it will not be subdivided; ② If the patch has 1 marked adjacent face, it will be subdivided by 1-2; ③ If the patch has 2 marked adjacent faces, Then subdivide it 1-3; ④ If the patch has 3 marked adjacent faces, subdivide it 1-4. After we subdivide all the patches of the base mesh with the above-mentioned subdivision mode, an adaptive subdivision is completed to form a new base mesh.

5) Rasterized vector representation

我们需要渲染控制网格M_C面片和它们相关的颜色信息到一个离散的光栅图像，也将该过程称为矢量表示光栅化。Since most of the current display devices only support the display of raster images, in order to display the vector representation obtained in the previous steps in these display devices

We need to render the control mesh _MC patches and their associated color information into a discrete raster image, a process also known as vector representation rasterization.

The vector representation is based on subdivision surfaces, so the corresponding subdivision surfaces must be obtained first, and then discretized into raster images. The rasterization process of the present invention is:

①According to the loop subdivision rule with sharp features, subdivide the control grid M _C for r times to obtain a refined grid M _r , r=2,3...;

② _Move all the vertices of Mr to the corresponding limit positions according to the Loop limit rule with sharp features, so as to obtain the approximate segmented _subdivision surface MS;

③ Since MS is a _piecewise linear surface, the color value of any point on the surface can be linearly represented by the color values of the three vertices of the triangular patch where the point is located. The present invention uses the barycentric coordinates to calculate the weights of the three vertices. For the entire limit surface mesh _MS , the rendering process: loop through each _patch of MS; for each triangular patch, find the bounding box of the patch; for each integer pixel in the bounding box, judge Whether the point belongs to the triangle patch, if so, find its barycentric coordinates; finally calculate the color value of the pixel point according to the barycentric coordinates. After traversing all the triangular surfaces of the grid, the colors of the corresponding raster image pixels can be filled, thereby realizing the generation of the raster image.

Compared with the prior art, the present invention has the following advantages and beneficial effects:

1. The present invention proposes to use the contour tracking algorithm to obtain the line segment on one side of the initial feature line segment, then form a double feature line with the initial feature line, and then use the double feature line to model the discontinuity of the colors on both sides of the image feature, which can be compared. Nicely captures the color values on both sides.

2. According to the characteristics of the image grid, the present invention improves the calculation method of the cost of the QEM simplification algorithm, and optimizes the topology and geometry of the simplified grid to obtain a base grid that can better reflect the image features. The quality is better.

3. For the error of the initial reconstruction result represented by the vector can not meet the needs of the user, the present invention can measure the error between the vectorized reconstructed image and the original image, and achieve the specified range within a certain range by adaptively subdividing the base grid. The error is controllable and has practical application value.

Description of drawings

FIG. 1 is a flow chart of the entire method of the present invention.

FIG. 2 is a schematic diagram of the initial grid structure of the present invention.

FIG. 3 is a schematic diagram of contour tracing of the present invention.

FIG. 4 is a simplified flow chart of the grid of the present invention.

FIG. 5 is a flowchart of the loop subdivision surface fitting with controllable error according to the present invention.

FIG. 6 is a schematic diagram of an adaptive subdivision mode of the present invention.

Fig. 7 is the vectorization process and result of Lena, an example of the present invention: (a) original image; (b) image features; (c) double feature lines; (d)-(f) represent 1%, 2%, Control mesh with 3% vertex count; (g)-(i) represent the reconstruction results of (d)-(f), respectively.

FIG. 8 is a diagram showing the vectorization results of more examples of the present invention, from left to right, the original image, the control mesh with 2% vertex count, and the reconstructed image are respectively shown.

Figure 9 shows the reconstruction results of two examples of the present invention under different reconstruction errors: the first row is the original image and the base mesh with a vertex ratio of 2%, and the second, third, and fourth rows are different reconstructions. The reconstructed image and reconstruction error are obtained under the reconstruction error.

Fig. 10 is a change trend diagram of the average error in the error control process of the example of Fig. 9(a) of the present invention.

Fig. 11 is a change trend diagram of the average error in the error control process of the example of Fig. 9(b) of the present invention.

Detailed ways

The present invention will be further described below in conjunction with specific embodiments.

As shown in FIG. 1, for a given raster image I to be vectorized, the steps of the image vectorization method for subdivision surfaces described in this embodiment are as follows:

1) Detect the edge features of the image and get a pixel-wide feature line segment

1) Detect image edge features

The image edge is the most significant image feature. In order to construct the base grid that maintains the image features, the image edge line segment detection method is used to extract the one-pixel-wide feature line of the image. The steps are:

①Gaussian filtering: Convolve the image with a Gaussian kernel to suppress image noise and smooth the image;

②Calculate the gradient magnitude and edge direction map: First, use the gradient operator to calculate the horizontal and vertical gradients of the pixel respectively, and then calculate the image gradient magnitude map. At the same time, compare the size of the horizontal and vertical gradients of the pixel to determine the pixel. The edge direction of the point, if the horizontal gradient is large, it is considered to be a vertical edge through the pixel, and vice versa;

③Extract anchor points: An anchor point can be considered as the end of the edge, that is, a pixel point with drastic feature changes in the horizontal and vertical directions. Here, the local gradient extreme value is selected as the anchor point, and the gradient between the pixel point and its adjacent pixels is compared. value to determine whether the pixel is an anchor point. For a horizontal pixel, compare it with the left and right adjacent pixels. If the gradient value of the pixel is greater than the gradient value of the left and right adjacent pixels by a specified threshold, it is considered that The pixel is the anchor point;

④ Connect anchor points to form line segments: Connect adjacent anchor points according to the gradient amplitude and edge direction map, starting from the anchor point that has not been detected each time, observe the edge direction passing through the anchor point, if it is a horizontal edge, The connection process is started by traveling left and right, if the vertical edge passes the anchor point, the connection process is performed by traveling up and down, during the movement, only three immediate neighbor pixels are considered, and the one with the largest gradient value is selected , when encountering a pixel with a gradient magnitude of 0 or encountering an edge pixel that has been detected before, the processing stops.

2) Construct an initial grid based on image features, and label image features in the grid

Build an initial triangular mesh M of pixel resolution on the 2D image plane. First establish the initial grid vertex, each pixel in the image corresponds to a vertex in the grid, and record the color value of the pixel in the vertex attribute; then connect the grid vertices in rows and columns to form a rectangular grid , each rectangular grid in the grid is divided into two triangular grids according to the image feature lines, as shown in (a) of Figure 2.

Image color discontinuities are associated with at least two adjacent pixels with very different color intensities, and image edge lines alone are not sufficient to represent image color discontinuities. Therefore, the present invention proposes to use a double characteristic line to represent the discontinuity of the color of the image. The strategy first uses the contour tracing algorithm to find parallel line segments with a distance of one pixel on both sides of the image feature line, as shown in (b) of Figure 2. Then, by comparing the image gradients on both sides, a line segment with a large average gradient is selected as another feature line, and the affected triangular mesh is re-triangulated, as shown in (c) of Figure 2.

To find the contours of the image feature lines, first mark the feature edges and feature vertices of the image on the grid. For each breakline, label the vertices on the breakline as + and the vertices on the non-breakline as -. If the two vertex labels of an edge are different, the contour will pass through the edge. We use the half-edge structure to trace the contour of the triangular mesh. The process is similar to the two-dimensional marching triangle algorithm, as shown in Figure 3. The process of contour tracing for one pixel on one side of each feature line is described as follows :

①First, find the first equivalent point on one side according to the first two vertices of the characteristic line, and add it to the contour segment, as shown in the v ₁ vertex in Figure 3, and then find the corresponding first half-edge he ₁ , Then judge whether the current half edge belongs to the first face, and judge whether the direction of the current half edge is correct according to the angle between the second half edge and the line connecting the first point and the second point of the feature line, and then determine the first search triangle f ₁ ;

② Find the second half-edge with an equivalent point on the relevant edge of the triangle, that is, the two vertices of the edge have different labels. As shown in the half-side he ₂ of Figure 3, the second iso-point is found. If the iso-point is the same as the previous iso-point, it will not be added to the iso-segment. If it is different, it will be added.

③ According to the half-side structure and the current half-side he ₂ , find the first half-side he ₃ of the next search triangle with an equivalent point, and then determine the next search triangle f ₂ ;

④ Execute ② and ③ recursively until no equivalent points are included in the search triangle.

Next, the types of edges and vertices of the initial mesh are marked, so that different types are processed differently in subsequent operations such as mesh simplification, subdivision, etc. to maintain important image features. The invention divides the edges of the mesh into three types: boundary edge, smooth edge and crease edge, and divides the vertices of the mesh into four types: boundary point, smooth point, crease point and corner point. Label the double feature lines of the image as crease edges, the edges of the image matrix boundary as boundary edges, and the other edges as smooth edges. For mesh vertices, if the vertex is only connected with smooth edges, the vertex is marked as a smooth point; a crease vertex is connected with two adjacent crease edges; a boundary point is connected with two adjacent boundary edges; image feature line endpoints, Breakpoint intersections are marked as corners. To fix the rectangular image boundary, the four corners are marked as corner points.

3) Simplify the initial grid and construct a base grid that preserves image features

The QEM simplification algorithm is mainly used to simplify the initial grid of the image to obtain the base grid _MB . The quadratic error cost is calculated by considering the color properties of the grid as a height field, and the image features are preserved using subdivision curves to fit image feature line segments during the simplification process.

In the previous step, we classified the vertices and edges of the mesh based on image features. In order to maintain the shape and characteristics of the image, different processing methods are adopted for different features: ① the corner points are not allowed to be folded; ② the boundary point can only be folded with two adjacent boundary points of the same boundary; ③ the crease point can only be folded with the same boundary The two adjacent crease points on the same crease edge are folded; ④The smooth point can be folded to the feature point.

的总折叠代价表示为：Furthermore, in order to obtain a high-quality base mesh that preserves image features, the edge-folding cost of the QEM algorithm is improved. The characteristic edge deformation cost Q _feature , the triangle regularity cost Q _re , and the area cost Q _area are added to the edge folding cost, and they are given corresponding weights. Using Q _{qem to} represent the QEM cost, the edges can be folded

The total folding cost of is expressed as:

Cost(v ₁ ,v ₂ )=αQ _qem (v ₁ ,v ₂ )+βQ _feature (v ₁ ,v ₂ )+γQ _re (v ₁ ,v ₂ )+δQ _area (v ₁ ,v ₂ )(1 )

Among them, the weights α, β, γ, and δ are specified by the user, and the order of edge folding is carried out according to Cost(v ₁ , v ₂ ) from small to large.

It should be noted that, in order to ensure the quality of the simplified two-dimensional grid, except when calculating the QEM cost, the color attribute of the grid M is regarded as a height field, and when calculating other costs, only the two-dimensional image grid is considered. , regardless of color properties. In the experiment, the weights α, β, γ, and δ are taken as 1, 10, 3, and 10, respectively. Calculate the cost of each item:

QEM cost Q _qem : The color attribute of the grid M is regarded as a height field, and the RGB value is used as the height, then three costs can be calculated for each edge, and the sum is used as the quadratic error cost Q _qem of the edge.

Feature edge deformation cost Q _feature : Define Q _feature as the distance between the _feature point before folding and the line connecting its two adjacent feature points, which is used to measure the degree of deviation between the feature edge folding result and the folding point. The smaller the deviation. If the collapsed edge is a non-feature edge, the Q _feature value is 0.

Triangle regularity cost Q _re : The triangle regularity cost is added to the edge folding cost in order to reduce the appearance of long and narrow triangle patches. The regularity of a triangle is used to indicate how close it is to an equilateral triangle. R(t)=cos(∠A)+cos(∠B)+cos(∠C) can be used to measure the regularity of triangle t=ΔABC. Let Re(t)=3-2R(t), then 0≤Re(t)≤1, the smaller the value of Re(t), the higher the regularity of the triangle. Then the regularity of the triangular patch set T can be defined as:

Re(T)=max{Re(t)|t∈T} (2)

的正则性代价定义为：Q _re is defined as the regularity increment of related triangular patches before and after edge folding. then the side is folded

The regularity cost of is defined as:

表示顶点

的邻接三角面片。in,

represents a vertex

of adjacent triangles.

的面积代价定义为：Area cost Q _area : The triangle regularity cost Q _re reflects the shape of the triangular patch, not the size of the patch. If the weight γ of Q _re is relatively large, the size of the grid patches may vary greatly. Therefore, an area cost is added to the total cost to constrain the area of the patch. The area cost Q _area is defined as the sum of the areas of all adjacent faces of the new vertex after the edge is collapsed. then the side is folded

The area cost of is defined as:

Among them, area(t) represents the area of triangle t;

According to the above analysis, as shown in Figure 4, the main steps of the grid simplification algorithm are:

①Set the weights in the edge folding cost formula (1);

② Consider the color attribute of the grid M as a height field, and calculate the QEM cost Q _qem of all edges of the grid;

③ Calculate the folding cost of all foldable edges and put them into the minimum heap according to the folding cost. Calculate the folding cost of the two half-edges corresponding to each edge according to formula (1).

④ Take the edge with the minimum folding cost from the heap, and first determine whether the relevant surface will be reversed after it is folded. If so, add a penalty value to the cost of the edge, and update its position in the heap; if it does not reverse. If it is flipped, judge whether the edge is a feature edge. If it is a feature edge, fit and adjust the position of the feature point and judge whether the fitting error after folding meets the requirements. If not, the edge is not folded, and it is removed from the stack. Delete; otherwise, complete the collapsing operation for the edge, recalculate the collapsing cost of the relevant edge and update their position in the heap.

⑤ If the simplified requirements are met or the minimum heap is empty, go to ⑥, otherwise go to ④.

⑥ Delete independent vertices in the mesh, update the mesh, and output the base mesh.

Although factors such as patch regularity and area are considered in the mesh simplification process, it is still not guaranteed that a high-quality base mesh can be obtained. Therefore, the present invention uses the simplest Laplacian operator to optimize the mesh geometry:

The new positions of the vertices in the mesh are given iteratively by vnew = v+ ^λΔv , where λ takes the value 0.3.

In order to preserve the characteristics of the image, the mesh feature vertices are treated specially. First, the corners do not move; for boundary vertices and feature points v, let (v _a , v ) and (v, v _b ) be the two characteristic edges where v is located, then v is only based on the positions of v _a and v _b Adjusted, that is, the Laplacian operator is defined as:

It should be noted that the mesh optimization can be carried out during the mesh simplification process, or can be carried out after the mesh simplification is completed. If the mesh optimization will cause the patch to flip, do not optimize it for now.

4) Control mesh obtained by loop subdivision surface fitting with controllable error

After simplification and optimization of the grid to obtain the base grid reflecting the image features, the present invention proposes the loop subdivision surface fitting with error control to fit the image color, and performs error control in the process of calculating the control grid, The user can obtain a vector image that meets the needs by specifying the error of the reconstructed image. The process mainly includes three parts: calculation of control grid, error control and adaptive subdivision.

4.1) Calculation of control grid

然后使用网格

对原图像进行采样得到M_R，将M_R作为我们拟合的目标。像素点的颜色值在图像特征区域有着显著的变化，为了采样到准确的颜色值，我们对不同的网格特征采用不同的采样方式得到顶点的颜色值：对于折痕顶点，它的目标颜色为它所在的图像特征线上和它位置最接近的像素点的颜色值；对于角点，它在简化过程和细分过程中的位置都没有移动，所以它的目标颜色为顶点坐标确定的图像像素点的颜色值；对于平滑顶点，其颜色由其周围的像素点进行双线性插值得到。In order to increase the amount of data to fit the target, we first perform a 1-4 subdivision on the base grid _MB to obtain a grid

then use grid

Sampling the original image to get _MR , and take _MR as our fitting target. The color value of the pixel has a significant change in the image feature area. In order to sample the accurate color value, we use different sampling methods for different mesh features to obtain the color value of the vertex: for the crease vertex, its target color is The color value of the pixel point closest to its position on the image feature line where it is located; for corner points, its position has not moved during the simplification process and the subdivision process, so its target color is the image pixel determined by the vertex coordinates The color value of the point; for smooth vertices, the color is bilinearly interpolated from the surrounding pixels.

和M_R具有相同的拓扑关系。根据Loop极限模版求网格

的极限得到细分极限曲面M_S，拟合目标就是：In the process of mesh simplification, the feature vertex positions of the mesh have been fitted. For the convenience of calculation, only the colors of the mesh vertices are fitted here. Therefore, the control mesh M _C to be calculated and the base mesh _MB have the same topology. Therefore, the mesh obtained after a loop subdivision of the control mesh M _C

and _MR have the same topological relationship. Grid based on Loop limit template

The limit of the subdivision limit surface M _S is obtained, and the fitting objective is:

M _R = M _S (7)

表示网格M_C、M_R、

M_S的顶点颜色构成的向量。则根据带尖锐特征的Loop细分模版和极限模版，存在有细分矩阵S_m×n和极限矩阵L_m×m使得：：

所以可以将Loop细分拟合方程(7)表示为：Let the number of vertices of the base mesh _{MB and the target mesh M C be} n and m, respectively.

Represents meshes _{M C} , MR ,

_A vector of vertex colors for MS. Then according to the loop subdivision template and limit template with sharp features, there are subdivision matrix S _m×n and limit matrix L _m×m such that:

So the Loop subdivision fitting equation (7) can be expressed as:

Let Z _m×n =L _m×m S _m×n , the equation system (8) can be transformed into:

和

的大小分别为n×3和m×3，RGB三种颜色可以分开求解。The control grid M _C can be obtained by solving the system of linear equations (9). Because the color of the mesh vertices is fitted here, so

and

The sizes are n×3 and m×3, respectively, and the three colors of RGB can be solved separately.

4.2) Error control

The reconstruction error of each pixel is defined as the Euclidean distance between the reconstructed image and the color value of the corresponding pixel of the original image, and the reconstruction error e of the entire image is defined as the mean of the reconstruction errors of all pixels. The reconstruction error ^ef of a grid patch is defined as the mean of reconstruction errors of all pixel points corresponding to the patch after rasterization.

In the previous step, the control mesh is obtained by fitting the loop subdivision surface, so that the corresponding subdivision surface is as close to the original image as possible. However, the number of vertices of the control grid depends on the simplification of the grid. If the simplification is excessive, the number of vertices of the control grid is too small and the freedom is too large, which may lead to large reconstruction of the reconstructed image and the original image in some areas. Therefore, the present invention controls the reconstruction error of the image by adaptively subdividing the area with large error, so that the user can obtain the reconstructed image with the specified error.

For the calculation of the reconstruction error, the limit surface of the control grid is first estimated according to the Loop subdivision rule with sharp features and the limit rule, and the color value of each pixel on the limit surface is calculated, that is, the rasterized vector representation. Then, according to the base grid patch where each pixel point is located, the reconstruction error ^ef of each patch of the base grid is calculated. Finally, the error e of the entire reconstructed image is calculated. Through the above analysis, as shown in FIG. 5 , the main process of obtaining the control grid with controllable error of the present invention is as follows:

① Backup the base mesh M _B , and use the Loop surface fitting method to calculate the control mesh M _C ;

② Estimating the limit surface M _S of the control grid M _C according to the fine loop division rule and the limit rule;

③ For the color value I(i) of each pixel point of the original raster image, calculate the color value I′(i) of the corresponding pixel point on the limit surface MS according to the _barycentric coordinates, calculate the pixel point error e _i , and find the pixel Point to the corresponding base mesh patch. Then calculate the average error ^ef of all pixels in each patch of the base grid _MB , and finally calculate the average reconstruction error e of the entire image;

④If the average reconstruction error e is less than the average error threshold ε specified by the user, terminate the algorithm and output the control grid M _C ; otherwise, find out the top k largest average error patch sets in the base grid M _B , and mark these The patch needs to be adaptively subdivided; where k ≥ 1 is specified by the user, in general, the larger the k, the faster the average error decreases.

⑤ Perform adaptive refinement on the marked base mesh to obtain a new base mesh _MB , then go to step ①, and continue the whole process until the reconstructed image with the specified error is obtained.

4.3) Adaptive subdivision

Adaptive subdivision allows subdividing only the area of interest. In error control, we need to locally increase the number of control vertices by adaptively subdividing the patches marked as not meeting the error requirements, thereby reducing the error. To avoid cracks in the new mesh, we must subdivide both the marked patch and its neighbors. For the marked mesh patch, we subdivide it 1-4, as shown in the patch marked 1 in Figure 6. For the unmarked patch, we subdivide it according to the condition of its adjacent faces being marked: ① If the patch has 0 marked adjacent faces, as shown in the patch marked 5 in Figure 6, then do not subdivide it; ② if the patch has 1 adjacent face that is marked, as shown in the patch marked 4 in Figure 6, it is subdivided 1-2; ③ if the patch has 2 There are marked adjacent faces, as shown in the patch marked 3 in Figure 6, it is subdivided by 1-3; ④ If the patch has 3 marked adjacent faces, as shown in Figure 6, it is marked as 2, then subdivide it 1-4. After we subdivide all the patches of the base mesh with the above-mentioned subdivision mode, an adaptive subdivision is completed to form a new base mesh.

5) Rasterized vector representation

我们需要渲染控制网格M_C面片和它们相关的颜色信息到一个离散的光栅图像，也将该过程称为矢量表示光栅化。Since most of the current display devices only support the display of raster images, in order to display the vector representation obtained in the previous steps in these display devices

We need to render the control mesh _MC patches and their associated color information into a discrete raster image, a process also known as vector representation rasterization.

We first obtain the corresponding subdivision surface, and then discretize it into a raster image. The rasterization process is:

①According to the loop subdivision rule with sharp features, subdivide the control grid M _C for r times to obtain a refined grid M _r , r=2,3...;

② _Move the vertices of Mr to the corresponding limit positions according to the Loop limit rule with sharp features, so as to obtain the approximate segmented _subdivision surface MS.

③ Since MS is a _piecewise linear surface, the color value of any point on the surface can be linearly represented by the color values of the three vertices of the triangular patch where the point is located. The present invention uses the barycentric coordinates to calculate the weights of the three vertices. For the entire limit surface mesh _MS , the rendering process: loop through each _patch of MS; for each triangular patch, find the bounding box of the patch; for each integer pixel in the bounding box, judge Whether the point belongs to the triangle patch, if so, find its barycentric coordinates; finally calculate the color value of the pixel point according to the barycentric coordinates. After traversing all the triangular surfaces of the grid, the colors of the corresponding raster image pixels can be filled, thereby realizing the generation of the raster image.

To sum up, for a given raster image to be vectorized, the method of the present invention can obtain a vector representation with good quality and maintaining the characteristics of the original image. 7 is the vectorization process and result of an example Lena of the present invention: (a) is the original image; (b) is the detected image feature; (c) is the double feature line obtained using the contour tracking algorithm; ( d)-(f) represent the control meshes with 1%, 2%, and 3% vertex counts, respectively; (g)-(i) represent the reconstruction results of (d)-(f), respectively. FIG. 8 is a diagram showing the vectorization results of more examples of the present invention, from left to right, the original image, the control mesh with 2% vertex count, and the reconstructed image are respectively shown. It can be seen from the figure that the method of the present invention can obtain a vector representation of good quality, and the more the number of vertices of the mesh, the closer the obtained vector representation is to the original image.

The method of the present invention can measure the error between the vectorized reconstructed image and the original image when the error of the initial reconstruction result represented by the vector cannot meet the needs of the user, and the base grid can be adaptively subdivided to achieve the specified range within a certain range. The error is controllable and has practical application value. Figure 9 shows the reconstruction results of two examples of the present invention under different reconstruction errors: the first row is the original image and the base mesh with a vertex ratio of 2%, and the second, third, and fourth rows are different reconstructions. The reconstructed image and reconstruction error are obtained under the reconstruction error. It can be seen from the figure that the reconstructed image of the second row has a large error at the edge of the image. After the iterative adaptive subdivision error control of the method of the present invention, the area with large error in the image is improved, so that A reconstruction result that meets the average error requirement is obtained, which can well represent the original image. It is illustrated that for the base grid of the same simplified scale, the method of the present invention can vectorize the results that meet different error requirements within a certain range.

The error control algorithm of the present invention has convergence properties. If the reconstructed image does not meet the error requirement, the method of the present invention selects the first k base mesh patches with the largest average error for adaptive subdivision in each iteration, thereby increasing the number of vertices on the final control mesh. Theoretically, as the number of vertices on the control mesh increases, the reconstruction error will become smaller and smaller, and eventually converge to a small value. FIG. 10 and FIG. 11 are the average error change trend diagrams in the error control process of the example of FIG. 9( a ) and the example of FIG. 9( b ) of the present invention, respectively. It can be seen from the figure: (1) With the increase of the number of iterations, the error of the reconstructed image gradually decreases as a whole, indicating that the error control algorithm of the present invention has convergence; (2) With the number of subdivided patches k in each iteration As , the rate at which the average error decreases increases, and the specified error threshold can be reached in fewer iterations. However, if k is too large, some base mesh patches with small errors will also be refined, making the number of patches and vertices increase rapidly, resulting in redundancy. Therefore, the user can specify the corresponding number of patches k subdivided in each iteration according to the acceptable error to reduce the number of iterations.

The above-mentioned embodiments are only preferred embodiments of the present invention, and are not intended to limit the scope of implementation of the present invention. Therefore, any changes made according to the shape and principle of the present invention should be included within the protection scope of the present invention.

Claims (1)

1. an error-controllable subdivision surface image vectorization method, is characterized in that, comprises the following steps: 1) Detect image edge features The image edge is the most significant image feature. In order to construct the base grid that maintains the image features, the image edge line segment detection method is used to extract the one-pixel-wide feature line of the image. The steps are: ①Gaussian filtering: Convolve the image with a Gaussian kernel to suppress image noise and smooth the image; ②Calculate the gradient magnitude and edge direction map: First, use the gradient operator to calculate the horizontal and vertical gradients of the pixel respectively, and then calculate the image gradient magnitude map. At the same time, compare the size of the horizontal and vertical gradients of the pixel to determine the pixel. The edge direction of the point, if the horizontal gradient is large, it is considered to be a vertical edge through the pixel, and vice versa; ③Extract anchor point: The anchor point is considered as the end of the edge, that is, the pixel point with drastic feature changes in the horizontal and vertical directions. Here, the local gradient extreme value is selected as the anchor point, and the gradient value of the pixel point and its adjacent pixel points is compared by comparing the gradient values. To judge whether the pixel is an anchor point, for a horizontal pixel point, compare it with the left and right adjacent pixels, if the gradient value of the pixel point is larger than the left and right adjacent pixel gradient value by a specified threshold, it is considered that the The pixel is the anchor point; ④ Connect anchor points to form line segments: Connect adjacent anchor points according to the gradient amplitude and edge direction map, starting from the anchor point that has not been detected each time, observe the edge direction passing through the anchor point, if it is a horizontal edge, The connection process is started by traveling left and right, if the vertical edge passes the anchor point, the connection process is performed by traveling up and down, during the movement, only three immediate neighbor pixels are considered, and the one with the largest gradient value is selected , when encountering a pixel with a gradient amplitude of 0 or encountering an edge pixel that has been detected before, the processing stops; 2) Construct an initial grid based on image features, and label image features in the grid Create an initial triangular mesh M with pixel resolution on the 2D image plane: First, create initial mesh vertices, each pixel in the image corresponds to a vertex in the mesh, and record the color of the pixel in the vertex attribute value, and then connect the grid vertices in rows and columns to form a rectangular grid, and divide each rectangular grid in the grid into two triangular grids according to the image feature lines; Image color discontinuities are associated with at least two adjacent pixels with very different color intensities, and image edge lines alone are not sufficient to represent image color discontinuities. Therefore, it is proposed to use dual feature lines to represent image color discontinuities. , first use the contour tracking algorithm to find the parallel line segments with a distance of one pixel on both sides of the image feature line, and then select the line segment with the larger average gradient as another feature line by comparing the image gradients on both sides, and analyze the affected triangulation. The lattice is re-triangulated; Next, the types of edges and vertices of the initial mesh are marked, so that different types are treated differently in subsequent mesh simplification and subdivision operations to maintain important image features; the edges of the mesh are divided into Three types: boundary edge, smooth edge, crease edge, divide the vertices of the mesh into four types: boundary point, smooth point, crease point, corner point; mark the double feature line of the image as the crease edge, Mark the edges of the image matrix boundary as boundary edges, and the other edges as smooth edges; for mesh vertices, if the vertex is connected only with smooth edges, the vertex is marked as a smooth point; crease vertices are connected with two adjacent crease edges ;Boundary points are connected with two adjacent boundary edges; the endpoints of image feature lines and the intersections of feature lines are marked as corner points; in order to fix the border of the rectangular image, the four corners are marked as corner points; 3) Simplify the initial grid and construct a base grid that preserves image features The QEM simplification algorithm is used to simplify the initial grid of the image, and the base grid MB is obtained. _The color attribute of the grid is regarded as a height field to calculate the quadratic error cost, and the subdivision curve is used to fit the image feature line during the simplification process. to preserve image features; In the previous step, the vertices and edges of the mesh are classified according to the image features. In order to maintain the shape and features of the image, different processing methods are adopted for different features: ① the corner points are not allowed to be folded; ② the boundary points are only It can be folded with two adjacent border points of the same border; ③The crease point can only be folded with the two adjacent crease points of the same crease edge; ④The smooth point can be folded to the feature point; In addition, in order to obtain a high-quality base mesh that preserves image features, the edge folding cost of the QEM algorithm is improved, and the feature edge deformation cost Q _feature , the triangle regularity cost Q _re , and the area cost Q _area are added to the edge folding cost, and Give them corresponding weights, and use Q _{qem to} represent the QEM cost, then the edges can be folded

The cost is expressed as: Cost(v ₁ ,v ₂ )=αQ _qem (v ₁ ,v ₂ )+βQ _feature (v ₁ ,v ₂ )+γQ _re (v ₁ ,v ₂ )+δQ _area (v ₁ ,v ₂ )(1 ) In the formula, the weights α, β, γ, and δ are specified by the user, and the order of edge folding is carried out according to Cost(v ₁ , v ₂ ) from small to large; it should be noted that, in order to ensure the quality of the simplified two-dimensional grid, except When calculating the QEM cost, the color attribute of the grid M is regarded as a height field. When calculating other costs, only the two-dimensional image grid is considered, and the color attribute is not considered. Among them, the QEM cost Q _qem , the characteristic edge deformation cost Q _feature , triangle regularity cost Q _re , and area cost Q _area are defined as follows: QEM cost Q _qem : The quadratic error cost is used to calculate the quadratic error cost of the edge, which measures the distance from the point in the three-dimensional space to the plane, and the grid M is a two-dimensional grid, so the color attribute of the grid M is viewed form a height field, and use the RGB value as the height respectively, then each edge can calculate three costs, and use the sum as the quadratic error cost Q _qem of the edge; Feature edge deformation cost Q _feature : The QEM cost does not take into account the sharp features of the model and cannot reflect the features of the image. Q _feature is defined as the distance between the feature point before folding and the line connecting the two adjacent feature points, which is used to measure the feature edge. The degree of deviation between the folding result and the folding point. The smaller the Q _feature value, the smaller the deviation. If the folded edge is a non-feature edge, the Q _feature value is 0; Triangle regularity cost Q _re : The triangle regularity cost is added to the edge folding cost in order to reduce the appearance of long and narrow triangular patches. The regularity of a triangle is used to indicate the degree to which it is close to an equilateral triangle, which can be expressed by R(t)= cos(∠A)+cos(∠B)+cos(∠C) to measure the regularity of triangle t=ΔABC, let Re(t)=3-2R(t), then 0≤Re(t)≤1, The smaller the value of Re(t) is, the higher the regularity of the triangle is, and the regularity of the triangular patch set T is defined as: Re(T)=max{Re(t)|t∈T} (2) Define Q _re as the regularity increment of the relevant triangular patches before and after the edge is folded, then the edge is folded

The regularity cost of is defined as:

In the formula,

represents a vertex

The adjoining triangular patch of ; Area cost Q _area : The triangle regularity cost Q _re reflects the shape of the triangle patch, but not the size of the patch. Therefore, the area cost is added to the total cost to constrain the area of the patch, and the area cost Q _area is defined as edge folding After the sum of the areas of all adjacent faces of the new vertex, the edge is collapsed

The area cost of is defined as:

In the formula, area(t) represents the area of the triangle t; Among them, the steps of the mesh simplification algorithm are as follows: ①Set the weights in the edge folding cost formula (1); ② Consider the color attribute of the grid M as a height field, and calculate the QEM cost Q _qem of all edges of the grid; ③ Calculate the folding cost of all foldable edges, put them into the minimum heap according to the folding cost, and calculate the folding cost of the two half-edges corresponding to each edge according to formula (1), then the folding cost of the edge takes two half-edge costs The small value of , and record the folding direction; 4. Take the edge with the smallest folding cost from the heap, and judge whether the relevant face will be flipped after it is folded. If so, add a penalty value to the cost of the edge and update its position in the heap; if it will not be reversed Flip, judge whether the edge is a feature edge, if it is a feature edge, fit and adjust the position of the feature point and judge whether the fitting error after folding meets the requirements, if not, do not fold the edge and delete it from the heap ; otherwise, complete the collapsing operation of the edge, recalculate the collapsing cost of the relevant edge and update their position in the heap; ⑤ If the simplified requirements are met or the minimum heap is empty, go to ⑥, otherwise go to ④; ⑥ Delete independent vertices in the mesh, update the mesh, and output the base mesh; Although the patch regularity and area factors are considered in the mesh simplification process, a high-quality base mesh cannot be guaranteed, so the Laplacian operator is used to optimize the mesh geometry:

where N(v) and |N(v)| represent the set and number of all vertices in the 1-neighborhood of vertex v, respectively; the new position of the vertex in the grid is given by the iterative formula of v ^new =v+λΔv, where λ takes The value is 0.3; In order to maintain the characteristics of the image, special processing is performed on the mesh feature vertices: first, the corners do not move. For the boundary vertex and feature point v, let (v _a , v ) and (v, v _b ) be the two locations where v is located. feature edges, then v is only adjusted according to the positions of v _a and v _b , that is, the Laplacian operator is defined as:

It should be noted that the mesh optimization can be carried out during the mesh simplification process or after the mesh simplification is completed. If the mesh optimization will cause the patches to flip, the optimization will not be carried out for the time being; 4) Control mesh obtained by loop subdivision surface fitting with controllable error After the simplification and optimization of the grid, the base grid reflecting the image features is obtained, and the loop subdivision surface fitting with error control is proposed to fit the image color. In the process of calculating the control grid, the error is controlled, and the user can By specifying the error of the reconstructed image to obtain a vector image that meets the requirements, the process includes three parts: the calculation of the control grid, the error control and the adaptive subdivision, as follows: 4.1) Calculation of control grid In order to increase the amount of data to fit the target, first subdivide the base grid _MB by 1-4 to obtain a grid

then use grid

Sampling the original image to obtain _MR , and taking _MR as the fitting target; the color value of the pixel has a significant change in the image feature area. In order to sample the accurate color value, different grid features are used for different sampling. The color value of the vertex is obtained by the method: for the crease vertex, its target color is the color value of the pixel point closest to its position on the image feature line where it is located; for the corner point, it is in the process of simplification and subdivision. The position has not moved, so its target color is the color value of the image pixel determined by the vertex coordinates; for a smooth vertex, its color is obtained by bilinear interpolation of the surrounding pixels; In the process of mesh simplification, the feature vertex positions of the mesh have been fitted. For the convenience of calculation, only the color of mesh vertices is fitted here. Therefore, the control mesh M _C to be calculated and the base mesh M _B have the same topology Structure, the mesh obtained after a loop subdivision of the control mesh M _C

Has the same topological relationship as _MR ; finds the mesh according to the Loop limit template

The limit of the subdivision limit surface M _S is obtained, and the fitting objective is: M _R = M _S (7) Let the number of vertices of the base mesh _{MB and the target mesh M C be} n and m, respectively.

Represents meshes _{M C} , MR ,

The vector formed by the vertex colors of M _S , according to the Loop subdivision template and limit template with sharp features, there are subdivision matrix S _m×n and limit matrix L _m×m such that:

So the Loop subdivision fitting equation (7) can be expressed as:

Let Z _m×n =L _m×m S _m×n , the equation system (8) is transformed into:

The control mesh M _C can be obtained by solving the linear equation system (9), because the color of the mesh vertices is fitted here, so

and

The sizes are n×3 and m×3, respectively, and the three colors of RGB can be solved separately; 4.2) Error control The reconstruction error of each pixel is defined as the Euclidean distance between the reconstructed image and the color value of the corresponding pixel of the original image, and the reconstruction error e of the entire image is defined as the mean of the reconstruction errors of all pixels. The reconstruction error ^ef of the grid patch is defined as the mean value of the reconstruction error of all pixel points corresponding to the patch after rasterization; In the previous step, the control mesh is obtained by fitting the loop subdivision surface, so that the corresponding subdivision surface is as close to the original image as possible, but the number of vertices of the control mesh depends on the mesh simplification. If the number of control mesh vertices is too small and the freedom is too large, there may be a large reconstruction error between the reconstructed image and the original image in some areas. Therefore, the image is controlled by adaptively subdividing the area with large error. , so that the user can obtain the reconstructed image with the specified error; For the calculation of the reconstruction error, the limit surface of the control grid is first estimated according to the Loop subdivision rule with sharp features and the limit rule, and the color value of each pixel on the limit surface is calculated, that is, the rasterized vector representation, and then according to each pixel Calculate the reconstruction error ^ef of each patch of the base grid, and finally calculate the error e of the entire reconstructed image; through the above analysis, the error can be controlled to control the calculation of the grid The process is as follows: ① Backup the base mesh M _B , and use the Loop surface fitting method to calculate the control mesh M _C ; ② Estimating the limit surface M _S of the control grid M _C according to the fine loop division rule and the limit rule; ③ For the color value I(i) of each pixel point of the original raster image, calculate the color value I′(i) of the corresponding pixel point on the limit surface MS according to the _barycentric coordinates, calculate the pixel point error e _i , and find the pixel _The base grid patch corresponding to the point, then calculate the average error ^ef of all pixel points in each patch of the base grid MB, and finally calculate the average reconstruction error e of the entire image; ④If the average reconstruction error e is less than the average error threshold ε specified by the user, terminate the algorithm and output the control grid M _C ; otherwise, find out the top k largest average error patch sets in the base grid M _B , and mark these The patch needs to be adaptively subdivided; where k≥1 is specified by the user, the larger the k, the faster the average error decreases; ⑤ Perform adaptive refinement on the marked base mesh to obtain a new base mesh _MB , then go to step ①, and continue the whole process until the reconstructed image with the specified error is obtained; 4.3) Adaptive subdivision Adaptive subdivision allows subdivision of only the region of interest. In error control, it is necessary to perform adaptive subdivision on the patches marked as not meeting the error requirements to locally increase the number of control vertices, thereby reducing the error; in order to To avoid cracks in the new mesh, both the marked patch and its adjacent faces must be subdivided; for the marked mesh patch, perform 1-4 subdivisions, and for the unmarked patch, according to Subdivide if its adjacent faces are marked: ① If the patch has 0 marked adjacent faces, it will not be subdivided; ② If the patch has 1 marked adjacent face, it will be subdivided. Perform 1-2 subdivision; ③ If the patch has 2 marked adjacent faces, perform 1-3 subdivision; ④ If the patch has 3 marked adjacent faces, perform 1 -4 subdivision; after subdividing all the patches of the base mesh with the above subdivision mode, an adaptive subdivision is completed to form a new base mesh; 5) Rasterized vector representation In order to display the vector representation obtained in the previous step on a display device

Need to render control mesh _MC patches and their associated color information into a discrete raster image, also known as vector representation rasterization; The vector representation is based on subdivision surfaces, so the corresponding subdivision surfaces must be obtained first, and then discretized into raster images. The rasterization process is as follows: ①According to the loop subdivision rule with sharp features, subdivide the control grid M _C for r times to obtain a refined grid M _r , r=2,3...; ② _Move all the vertices of Mr to the corresponding limit positions according to the Loop limit rule with sharp features, so as to obtain the approximate segmented _subdivision surface MS; ③ Since MS is a _piecewise linear surface, the color value of any point on the surface can be linearly represented by the color values of the three vertices of the triangular patch where the point is located; the weight of the three vertices is calculated using the barycentric coordinates, for the entire limit Surface mesh _MS , its rendering process: loop through each _patch of MS, for each triangular patch, find the bounding box of the patch, and judge the point for each integer pixel in the bounding box Whether it belongs to the triangular patch, if so, find its barycentric coordinates, and finally calculate the color value of the pixel point according to the barycentric coordinates; Fill it up to generate a raster image.

Images