CN115496875A - Method for generating high-quality measurement ground contour line - Google Patents

Abstract

The invention provides a method for generating high-quality geodesic contours. The generating method includes: preprocessing the image data to obtain triangular grid data of the image; calculating the geodesic distance to the vertices of the grid; and All trisector points of the mesh edges; generate a cubic interpolation function for each triangular mesh edge; take k evenly spaced sample points from each trisector edge, and extrapolate the approximate geodesic distance at the sample points ;According to the distance weighted calculation of the sampling point Apollonius diagram, the triangle is divided into several parts, and then the geodesic contour of each part is extracted to obtain a high-quality geodesic contour; the sampling point is a trisecting point and sample points. The invention can improve the precision of geodesic contour extraction, and the method is applied to the technical field related to image extraction.

Description

A Method for Generating High Quality Geodesic Contours

technical field

The invention relates to the technical field of image extraction, in particular to a method for generating high-quality geodesic contours.

Background technique

Geodesics, also known as geodesics or geodesics, can be defined as the local shortest or longest paths between two points in space. Geodesic gets its name from geodesy, the study of the size and shape of the earth. An object like the Earth does not follow a curved orbit due to a force called gravity, but instead follows the closest approximation to a straight line in curved space called a geodesic. For example, the surface of the earth is a curved two-dimensional space. A geodesic on Earth is called a great circle and is the shortest path between two points. Since the geodesic is the shortest distance between two airports, this is exactly the route the navigator tells the pilot to fly. In general relativity, objects always follow the geodesics of four-dimensional space-time. However, in our 3D space it looks like it follows a curved path (this is like watching an airplane fly over very mountainous terrain. While it flies in a straight line in 3D space, in 2D but its shadow follows a curved path).

A contour is a solution to a given scalar field that has straight lines or curves of the same scalar value. Contours provide an intuitive way to visualize a given scalar field and have many applications in engineering. For example, weathermen often use contour maps to show differences in heat in different regions. The hottest areas are usually red, warmer areas are yellow, and colder areas are blue. Contours thus provide an intuitive way to visualize the behavior of a scalar field over a given domain. In general, no explicit form exists for arbitrary input scalar functions. Therefore, the commonly used method is to discretize the given domain into a group of simple units or small units, and then extract the isoline of each unit. As a special scalar field, geodesic distance field has been widely used in computer graphics and geography. Likewise, one can observe the behavior of geodesic metrics by visualizing geodesic contours.

In practical applications, there are also cases where geodesic contours are used. 3D printing is a good example, with the increasing popularity of additive processes and 3D printing in computer graphics, one should not lose sight of the fact that in most cases, subtractive manufacturing compared to additive manufacturing Faster and more cost-effective at the same level of product accuracy, on a wider range of materials, and with the ability to achieve excellent surface finishes. In addition, subtractive manufacturing is primarily accomplished with computer numerically controlled (CNC) machining tools. A CNC machine operates a cylindrical cutter that cuts material from shape stock in 3D space to "expose" the target 3D object. The tool tip traces a curve in space, called the toolpath, which must completely fill the surface of the object. Desirable characteristics of toolpaths for efficient CNC machining, especially high-speed machining (HSM), include fairness (i.e. low curvature) and continuity (i.e. fewer on/off toggles or tool retractions), similar to additive manufacturing , so it is necessary to calculate the tool path more accurately. In general, the toolpath for 3D printing is mainly divided into ① extraction of geodesic contours ② connection of contours into a continuous toolpath ③ smoothing of the toolpath while keeping the gap variation as small as possible. The extraction of geodesic contours is self-evident for 3D printing.

However, few methods have been proposed to extract geodesic contours. Based on the MMP algorithm, Liu et al. proposed a practical algorithm for extracting exact contours, bisectors and Voronoi diagrams. This method first precomputes the geodesic distance field using MMP, then keeps all propagation windows on each edge of the grid, recursively divides each edge into monotonic sub-edges, and re-splits at each Search for arcs in the triangle of . This process and the construction of the interval tree are used as precomputation, and then O(log n'+k log k) dichotomy search and marching process are used to solve the contour line of any genus-r model, where n' is the number of triangles resubdivided , k is the number of triangles that the contour passes through. In addition, Gehre et al. also proposed Geodesic Contour Line Feature (GICS), which can capture the length from an isoline with a certain radius on a surface to a certain point x. GICS computes robust approximate geodesic distances and finds intersections of contour segments and triangles. GICS uses the cumulative distance of these line segments to identify topological events and thus depends significantly on the precision of the contours. These algorithms do not provide accurate contours because edge-based segment intersection calculations ignore ridge points inside triangles and generate inaccurate contour lengths or spurious topology.

Geodesic contours reflect both the input accuracy and the geometric variation of the input surface. In the field of computer graphics, the geodesic field is first calculated on a triangular grid composed of thousands of triangles, and then the required spatial geodesic contours are extracted, and then the geodesic contours are extracted triangle by triangle, The geodesic field is assumed to be linear on each triangular face. However, it was found that even though the geodesic method is accurate, the contours extracted by this method often have obvious flaws, especially where the real contours have sharp bends or topological changes. The main reason is that geodesic distance fields are not smooth and may contain "ridges". Therefore, it is difficult to reconstruct sharp angles or topological changes of geodesic contours in high quality by simply piecewise linearizing the geodesic distance field.

Contents of the invention

The purpose of the present invention is to provide a method for generating high-quality geodesic contours, so as to make up for the deficiencies in the prior art.

The sharp bend of the geodesic contour is closely related to the ridge point, and a ridge point has at least two geodesic paths to the source point. In the present invention, the ridge curve is represented by calculating the weighted Voronoi diagram, which is also called the Apollonius diagram. It is calculated that the geodesic distance is continuous rather than smooth. Therefore, △ABC is divided into several parts by the ridge line, and the change of the geodesic distance inside each part is considered to be linear. At the same time, ridges can also reveal where geodesic contours may have sharp turns or topological changes. Therefore, this invention can approximately determine the position of the ridge point, and then better generate geodesic contour lines.

In order to extract the geodesic contour, the present invention extracts the geodesic contour from the existing vertex-based geodesic distance field. The quality and operational performance of geodesic contours relies heavily on the computation of distance fields.

In order to achieve the above-mentioned purpose, based on the above-mentioned technical scheme, the concrete technical scheme that the present invention takes is:

A method for generating high-quality geodesic contours, comprising the following steps:

S1: Preprocessing the image data to obtain the triangle mesh data of the image;

S2: Calculate the geodesic distance to the vertices of the mesh, and all the trisecting points of the edges of the triangular mesh;

S3: Generate a cubic interpolation function for each triangle mesh edge;

S4: Take k evenly spaced sample points from the edge of each trisector, and infer the approximate geodesic distance at the sample points;

S5: Calculate the Apollonius diagram according to the weighted distance of the sampling points, divide the triangle into several parts, and then extract the geodesic contours of each part to obtain high-quality geodesic contours; the sampling points are trisected points and sample points.

Further, in S2, the calculation of the geodesic distance includes computational geometry, partial differential equations and graph-based methods; this method is used to calculate the geodesic distances of all grid vertices.

Further, in S3, since the distance prediction using quadratic interpolation is not as accurate as cubic interpolation, less prior distance information is required, and the key properties of the distance field can be maintained with a small amount of additional computational cost, and the network can be inferred by cubic interpolation The geodesic distance of grid edge; The cubic interpolation function is specifically:

(1) Take two trisecting points for the grid edge, (2) Run the existing algorithm to calculate the geodesic distance of the trisect, (3) Generate a 3rd order interpolation function to simulate the distance change along the grid edge ; Let e=v1v2 be the grid edge, d1, d2, d3, d4 are the distance values of v1, (2v1+v2)/3, (v1+2v2)/3, v2 respectively;

The cubic interpolation function is:

Further, in the S5, Apollonius is defined as

Ω _i : {x∈Ω|||xx _i ||-w _i ≤||xx _j ||-w _j , j≠i}.; After the Apollonius graph is completed, construct Apollonius vertices and sampling points for triangulation.

Further, in said S5, calculate and extract the contour of the geodesic distance field, first extract the geodesic contour of all regions in a single triangular grid, and then extract the geodesic contour of each part one by one line, and merge all contour elements into a complete contour element; specifically:

(1) Define the linear function of each sub-region, and observe that the geodesic distance field in each region is basically linear;

(2) All subregions are then collected and a graph is used to encode the adjacency relations; this graph allows computation of geodesic distances between arbitrary pairs of points (not necessarily mesh vertices) in constant time O(1);

(3) Treat each subregion as a node, and keep the contour element in the corresponding node, and generate a complete contour by visiting the node:

1) Assume that the contour line at d is extracted;

2) Find the undetermined contour element whose distance is d, and mark this element as "fixed";

3) As long as the contour is not closed or does not reach the surface boundary, it will continue to find the contour element in the adjacent node and connect it to the existing contour segment.

A 3D printing method based on high-quality geodesic contours, comprising the following steps:

(1) Obtain an input model of a 3D printing image;

(2) Generate high-quality geodesic contours;

(3) connecting the geodesic contours obtained in step (2) into a continuous tool path;

(4) Smoothing the tool path while keeping the gap variation as small as possible;

(5) Finish the 3D printing at last.

Further, the step (2) is the same as the method for generating high-quality geodesic contours.

Compared with prior art, advantage and beneficial effect of the present invention are:

The invention enables the computation of high-quality geodesic distance field contours on triangular meshes, overlaying the results with a baseline (a more accurate solution computed on subdivided meshes) in order to visualize the quality. The invention guarantees that the geodesic backtracking cannot cross the ridge curve, so ideal precision is expected to be achieved. Compared with the piecewise linear method, the present invention significantly reduces the average error, consumes less memory, and overcomes the flat ridge defect produced by the piecewise linear method and the partial equivalence caused by the sensitivity of the partial differential equation to triangulation. Inaccurate line problem.

The invention can improve the precision of geodesic contour extraction, and the method is applied to the technical field related to image extraction.

Description of drawings

FIG. 1 is a basic flow chart of image geodesic contours in Embodiment 1.

Figure 2 is an Apollonius diagram showing two sites.

Figure 3 shows the Apollonius diagram for a set of 9 sites.

Fig. 4 is a diagram of continuous tool trajectory connected by contour lines in Embodiment 2.

FIG. 5 is a diagram of tool path generation in Embodiment 2. FIG.

detailed description

The present invention will be further explained and described below through specific embodiments in conjunction with the accompanying drawings.

Embodiment 1: The method is described by taking a specific image as an example.

A method for generating high-quality geodesic contours, as shown in Figure 1, includes the following steps:

S1: Preprocessing the image data to obtain the triangle mesh data of the image;

S2: Calculation of geodesic distances to mesh vertices, and all trisector points of triangular mesh edges; computation of geodesic distances, including computational geometry, partial differential equations, and graph-based methods; employing the method to compute The geodesic distance of all mesh vertices.

S3: Generate a cubic interpolation function for each triangle mesh edge;

S4: Take k evenly spaced sample points from the edge of each trisector, and infer the approximate geodesic distance at the sample points;

S5: Calculate the Apollonius diagram according to the weighted distance of the sampling points, divide the triangle into several parts, and then extract the geodesic contours of each part to obtain high-quality geodesic contours; the sampling points are trisected points and sample points.

In said S3, since the distance prediction using quadratic interpolation is not as accurate as cubic interpolation, requires less prior distance information, and can maintain the key properties of the distance field with a small additional computational cost, we infer the grid edges by cubic interpolation The geodesic distance; the cubic interpolation function is specifically:

(1) Take two trisecting points for the grid edge, (2) Run the existing algorithm to calculate the geodesic distance of the trisect, (3) Generate a 3rd order interpolation function to simulate the distance change along the grid edge ; Let e=v1v2 be the grid edge, d1, d2, d3, d4 are the distance values of v1, (2v1+v2)/3, (v1+2v2)/3, v2 respectively;

The cubic interpolation function is:

Further, in said S5,

划分为区域，其中xi支配子区域Ω_i：{x∈Ω｜｜｜x-x_i||≤||x-x_j||，j≠i}.这称为站点xi的Voronoi单元。Apollonius图是Voronoi的变体。A Voronoi diagram divides a given domain in terms of straight-line distances to a set of points {xi∈Ω}ni=1 (called stations or generators)

Divide into regions where xi dominates the subregion Ω _i : {x ∈ Ω|||xx _i ||≤||xx _j ||, j≠i}. This is called the Voronoi cell of site xi. Apollonius diagrams are a variant of Voronoi.

Apollonius is defined as Ω _i : {x∈Ω｜｜｜xx _i ||-w _i ≤||xx _j ||-w _j , j≠i}.; After the Apollonius graph is completed, construct Apollonius vertices and steps (2- 2,3) The points that have been taken are triangulated;

Figure 2 shows the Apollonius diagram for the two sites. When the {wi} coincidences are equal, the Apollonius diagram reduces to a traditional Voronoi diagram. The sets of connecting points that belong to exactly two Apollonius cells are called Apollonius edges, which are hyperbolas, while the points that belong to more than two Apollonius cells are called Apollonius vertices. Figure 3 shows the Apollonius diagram for a set of 9 sites. If the weights are positive, the Apollonius diagram can be viewed as a Voronoi diagram of a set of circles. Points outside the circle have positive distances, while points inside the circle have negative distances. However, unlike stations in a Voronoi diagram, station Pi may have an empty cell. If this is the case, we call the site hidden. Sites that are not hidden will be referred to as visible sites. The Apollonius graph does not change if all weights add up to the same value.

It is worth noting that unlike the traditional Voronoi diagram, the Apollonius diagram is composed of straight line segments and hyperbolic segments. In general, a site in an Apollonius diagram may dominate a multiply connected cell. Each cell must be connected individually, which can be attributed to the same reason: geodesics cannot pass through ridge points.

So it can be proved that as long as the triangular surface f does not contain a source point, f can be divided into m regions, where m cannot exceed the total number of sample points on the bounded edge of f (there may be hidden points in the Apollonius graph). By visiting the non-hidden points one by one, the triangular surface f can be divided into several parts, each part is surrounded by straight line segments and hyperbolic segments. In fact, by taking the main site as a pseudo-source, it is easy to infer the geodesic distance of each section. It can be proved that, for any destination point p, the geodesic path from p to the nearest source point cannot pass through a ridge point except that the ridge point is a saddle vertex, that is, the ridge curve is a split crest. Such that points on different sides of the ridge curve define different gradient directions. With the help of the Apollonius diagram, it can be guaranteed that the geodesic backtracking cannot cross the ridge curve, thus hopefully achieving the desired accuracy.

In said S5, calculate and extract the contour of the geodesic distance field, first extract the geodesic contour of all regions in a single triangular grid, and then extract the geodesic contour of each part one by one, and Merge all contour elements into a complete contour element; specifically:

(1) Define the linear function of each sub-region, and observe that the geodesic distance field in each region is basically linear;

(2) All subregions are then collected and a graph is used to encode the adjacency relations; this graph allows computation of geodesic distances between arbitrary pairs of points (not necessarily mesh vertices) in constant time O(1);

(3) Treat each subregion as a node, and keep the contour element in the corresponding node, and generate a complete contour by visiting the node:

1) Assume that the contour line at d is extracted;

2) Find the undetermined contour element whose distance is d, and mark this element as "fixed";

3) As long as the contour is not closed or does not reach the surface boundary, it will continue to find the contour element in the adjacent node and connect it to the existing contour segment.

Example 2:

A 3D printing method based on high-quality geodesic contours, comprising the following steps:

(1) Obtain an input model of a 3D printing image;

(2) Generate high-quality geodesic contours;

(3) Connect the geodesic contours obtained in step (2) into a continuous tool path; use the Fermat spiral generation technology to connect the contours into a continuous tool path, as shown in Figure 4;

(4) Smooth the tool path while keeping the gap change as small as possible; while keeping the gap change as small as possible. The smoothness requirement is expressed using conventional Laplacian smoothing techniques, and requires that the widest space at p between adjacent parts of the path Π cannot exceed the gap constraint g(p,Π) (written as g for simplicity ), or equivalently, the radius of the largest empty circle is no greater than g/2, and (ii) the narrowest space at p is as close to g as possible. Let {xi}ni=1 be the sequence of points representing the tool path. So far, the tool path is generated, as shown in Figure 5.

(5) Finish the 3D printing at last.

The accuracy of image extraction by using the present invention is higher, and can be applied to different scenes.

On the basis of the above-mentioned embodiments, the present invention continues to describe in detail the technical features involved and the functions and effects of the technical features in the present invention, so as to help those skilled in the art fully understand the present invention. technical solutions and reproduce them.

Finally, although this description is described according to implementation modes, not each implementation mode only includes an independent technical solution. This description in the description is only for the sake of clarity. The technical solutions in the examples can also be properly combined to form other implementations that can be understood by those skilled in the art.

Claims (4)

1. A method for generating high-quality geodesic contours, characterized in that the method for generating comprises the following steps: S1: Preprocessing the image data to obtain the triangle mesh data of the image; S2: Calculate the geodesic distance to the vertices of the mesh, and all the trisecting points of the edges of the triangular mesh; S3: Generate a cubic interpolation function for each triangle mesh edge; S4: Take k evenly spaced sample points from the edge of each trisector, and infer the approximate geodesic distance at the sample points; S5: Calculate the Apollonius diagram according to the weighted distance of the sampling points, divide the triangle into several parts, and then extract the geodesic contours of each part to obtain high-quality geodesic contours; the sampling points are trisected points and sample points. 2. generation method as claimed in claim 1, is characterized in that, among the described S2, the calculation of geodesic distance comprises computational geometry, partial differential equation and method based on graph; Adopt this method to calculate all grid vertices The geodesic distance of . 3. generation method as claimed in claim 1, is characterized in that, in described S3, described cubic interpolation function is specifically: (1) Take two trisecting points for the grid edge, (2) Run the existing algorithm to calculate the geodesic distance of the trisect, (3) Generate a 3rd order interpolation function to simulate the distance change along the grid edge ; Let e=v1v2 be the grid edge, d1, d2, d3, d4 are the distance values of v1, (2v1+v2)/3, (v1+2v2)/3, v2 respectively; The cubic interpolation function is:

Further, in the S5, Apollonius is defined as Ω _i : {x∈Ω|||xx _i ||-ω _i ≤||xx _j ||-ω _j , j≠i}. After the Apollonius diagram is completed, Construct Apollonius vertices and triangulate the sampling points. 4. generation method as claimed in claim 1 is characterized in that, in described S5, calculate and extract the contour of geodesic distance field, first extract the geodesic contour of all regions in a single triangular grid, and then The geodesic contours of each part are extracted triangular by triangular mesh, and all contour elements are merged into a complete contour element; specifically: (1) Define the linear function of each sub-region, and observe that the geodesic distance field in each region is basically linear; (2) All subregions are then collected, and a graph is used to encode the adjacency relations; this graph allows computing geodesic distances between arbitrary pairs of points (not necessarily mesh vertices) in constant time O(1); (3) Each sub-region is regarded as a node, and the contour element is kept in the corresponding node, and the complete contour is generated by visiting the node.

Images