Search

CN-115830211-B - Curve skeleton line extraction method of three-dimensional tubular body model based on hierarchical graph

CN115830211BCN 115830211 BCN115830211 BCN 115830211BCN-115830211-B

Abstract

The invention provides a three-dimensional tubular body model curve skeleton line extraction method based on a hierarchical graph, which comprises the steps of inputting three-dimensional tubular body model data, preprocessing, extracting end points, calculating shortest paths, calculating geometric features among different paths, constructing initial discrete skeleton points, calculating distances and angles of the paths, determining positions of candidate points of bifurcation points, dividing original data, performing fitting optimization on ball B splines to obtain skeleton line data, outputting the skeleton line data, estimating the positions of bifurcation points through tracking the shortest paths, obtaining accurate positions of bifurcation points through an elastic ball collision moving algorithm, and dividing a data model into a plurality of branches by using the bifurcation points as spherical centers through a dynamic ball expansion algorithm, so as to lay a foundation for construction and parallel calculation of subsequent hierarchical graphs.

Inventors

  • WANG XINGCE
  • WANG SHUANGYUAN
  • DU PENG
  • WU ZHONGKE

Assignees

  • 北京师范大学

Dates

Publication Date
20260505
Application Date
20221012

Claims (8)

  1. 1. The curvilinear skeleton line extraction method of the three-dimensional tubular body model based on the hierarchical graph is characterized by comprising the following steps of: step1, inputting three-dimensional tubular body model data O; Step 2, preprocessing input model data O, and extracting end points VE of the three-dimensional tubular body; step 3, calculating the shortest path between any end points p, q E VE on the three-dimensional tubular body, calculating the geometric features of different paths, and constructing an initial discrete skeleton point; Step 4, calculating the distance and the angle of the path between two identical starting points and different ending points on the three-dimensional tubular body, and determining the position of the bifurcation point candidate point: fitting two discrete paths with a B-spline curve, expressed as For the following In the following Finding a point in (b) Satisfy the path D represents the minimum distance between two points, Is the included angle of tangent vector of the projection point and the point corresponding to the original point, when D and Greater than a given threshold and When the iteration is stopped, the current iteration is stopped Determining candidate points of the bifurcation point, sequentially solving path candidate points on any two paths with the same starting point and different ending points, and obtaining bifurcation point candidate point data; Clustering the path candidate points by adopting a K-means clustering method, taking each clustering center point as a candidate point of a bifurcation point, and taking each clustering center point as a candidate point of a bifurcation point For expanding the ignition points, if curves of different ignition points collide with each other, a neighborhood relation between the two ignition points is established, all candidate points with the degree smaller than 3 are deleted, the rest points form the candidate points in the current level, all bifurcation points of the outermost layer are found, the bifurcation points of the next layer are iteratively found by taking the bifurcation points of the outermost layer as new endpoints until all bifurcation points are obtained, and a set of bifurcation point candidate points is formed ; Step 5, optimizing and adjusting the positions of the bifurcation points through a dynamic bead expansion algorithm to obtain final bifurcation points, establishing a layered topological structure, and dividing the original data by applying a contraction algorithm according to the topological structure: For each bifurcation point The electric field force to which this point is subjected is defined as: ......(5); Wherein n represents all of Distance of | − || ≤ Is defined by the number of points of the pattern, For a given threshold value of the value, Representing each point on the boundary Pointing to Is used for the vector of the unit of (a), And The potential energy between the two points is Euclidean distance between the two points, wherein m represents a weight parameter, the ideal position of the bifurcation point is defined as a point with the internal field intensity of 0, and for each change of the candidate bifurcation point, the moving direction of vi is calculated according to an electrostatic field model, the moving distance is calculated by an elastic small ball method, and then one-time movement is completed; Define the sphere center of the elastic pellet as The sphere with radius r is: ,......(6); For each of Definition of Distance moved by the center of sphere after each collision Where r is the radius of the current sphere, Expressed in terms of The number of voxels included in the sphere that is the center of the sphere, , As a coefficient, after the collision of the current sphere with the boundary, the potential field value at the point and the moving direction are recalculated, and the position of the new sphere center is calculated Is defined as , , Continuously iterating until reaching a stable state, finally obtaining the ideal position of the bifurcation point, wherein the sphere center of each dynamic pellet forms the final bifurcation point set ; Step 6, obtaining initial skeleton line through a distance conversion field for each piece of data on the three-dimensional tubular body; And 7, outputting skeleton line data.
  2. 2. The method for extracting curvilinear skeleton lines of a three-dimensional tubular body model based on a hierarchical graph according to claim 1, wherein in step 2, a neighborhood exploration algorithm is adopted to extract the end points of the three-dimensional tubular body: Calculating the number of foreground points in the 6 neighborhood and the 26 neighborhood of a voxel, wherein m is the number of foreground points in the 6 neighborhood of the object voxel, n is the number of foreground points in the 26 neighborhood of the object voxel, and the candidate point set of the end points is expressed as follows: ......(1), Wherein, the As the data points in the model data O, And Respectively data points The 6 neighborhood and the 26 neighborhood of the candidate endpoint set are obtained through the expression of the formula (1); clustering candidate points of the endpoints by adopting a K-means method, and defining: ......(2), ......(3), Wherein, the Is an inter-class distance between the two, 、 The mean value of the ith and the jth clusters respectively, k is the number of clusters, In order to be an intra-class distance, Each of the data points is represented as such, As a cluster mean, the loss function is: ......(4); the inter-class distance and the intra-class distance determine average contour coefficients, the clustering effect is evaluated through the average contour coefficients, and the number k of clusters in the formula (2) is calculated according to the average contour coefficients; performing iterative computation according to the K-means algorithm until a termination condition is reached; taking the center of each cluster as an endpoint voxel to form an endpoint set 。
  3. 3. The method for extracting a curved skeleton line of a three-dimensional tubular object model based on a hierarchical map according to claim 1, wherein in step 6, obtaining an initial skeleton line by a distance conversion field comprises: calculating the minimum distance between each voxel point and the boundary, and defining For the distance value between each voxel point and the boundary, any voxel Is equivalent to a radius of Is a central sphere with voxel points The maximum center sphere that is centered is defined as no other sphere within the model can contain After the distance conversion field is calculated, extracting the sphere center of the maximum center sphere to obtain an initialization skeleton point; adopting a grass burning model to obtain branch end points, iteratively calculating covered _points and fire_front sets to simulate a fire transfer process, wherein fire_front represents a voxel point set in which fire is currently burning, covered _points represents a voxel point set in which fire is already burning, all voxel points are contained in the covered _points set as termination conditions, and recording the time t to which the voxel point at the outermost layer of covered _points is transferred; And taking the initial skeleton point obtained by the distance field method and the end point obtained by the grass burning model method as initial points of the skeleton lines of the final branches.
  4. 4. A method of extracting a skeleton line from a three-dimensional tubular object model based on a hierarchical map according to claim 3, wherein in step 6, the method comprises fitting the skeleton line with a B-spline curve: Fitting discrete points using 3 times spline basis as basis function for m+1 data points Find a 3-degree B-spline: ......(7); Satisfy the following requirements , Remaining data points The calculation is carried out by a least square method, and the optimization function is as follows: ......(8); the optimization function is related to n-1 control vertices Wherein A parameter value for a data point, the parameter value being determined by accumulating chord parameters, letting: ......(9); Will be Carrying out calculation to obtain: ......(10); The solution of equation (10) is a least squares problem, requiring n-1 control vertices to minimize the objective function f Is 0, wherein The first derivative of (2) is: ......(11); Obtaining an equation set containing n-1 equations with unknown quantity, solving through a Gaussian elimination method, obtaining a 3-degree B spline curve, and fitting discrete skeleton points into skeleton lines through parameter expression.
  5. 5. The method for extracting the curved skeleton line of the three-dimensional tubular body model based on the hierarchical graph according to claim 4, wherein in the step 6, fitting optimization is performed by using ball B splines, the original splines are optimized by introducing Hausdorff distances, and the optimized objective function is as follows: ......(12); the Hausdorff distance from all scattered points to the B spline curve is represented, and the final optimization function is as follows: ......(13); Wherein, the Representation of A projection point on the surface of the ball B-spline; And adopting a quasi-Newton algorithm to carry out iterative optimization adjustment on the coordinates, the number and the sphere radius of the sphere B spline curve control sphere, and obtaining the optimized sphere B spline curve according to the error precision.
  6. 6. The method for extracting a curved skeleton line of a three-dimensional tubular body model based on a hierarchical map according to claim 1, wherein in step 2, preprocessing the input model data O includes denoising and downsampling.
  7. 7. The method for extracting a curved skeleton line of a three-dimensional tubular body model based on a hierarchical map according to claim 1, wherein in step1, the model data is a discrete point sequence described using three-dimensional coordinates.
  8. 8. The method for extracting a curved skeleton line from a three-dimensional tubular object model based on a hierarchical graph according to claim 5, wherein in step 6, the shortest total time length for which all voxel points are covered is optimized, and then the voxel point of the outermost layer of the secondary combustion is obtained as an endpoint, and the optimization formula is as follows: ......(14); Wherein, the Indicating from the source ignition point to The time elapsed by the point.

Description

Curve skeleton line extraction method of three-dimensional tubular body model based on hierarchical graph Technical Field The invention belongs to the technical field of computer graphics, and particularly relates to a curvilinear skeleton line extraction method of a three-dimensional tubular body model based on a hierarchical graph. Background The skeleton line extraction of the three-dimensional volume data model is an important research topic in computer graphics, the three-dimensional curve skeleton is one-dimensional expression of the three-dimensional model, the three-dimensional curve skeleton has topological isomorphic characteristics, the skeleton line can be used for realizing the dimension reduction expression of the model, and complexity and redundancy are reduced. Skeletonization provides an effective and compact method, the skeletons of the objects are obtained by reducing the dimensions of the objects, the topological structure and the geometric characteristics of the data can be reserved, after the concept of the central axis is put forward from Blum in the 60 th century, the academy makes a lot of expansion in the aspect of skeleton line extraction, the skeletonization thought is that the two-dimensional objects are simplified into one-dimensional curves, the three-dimensional objects are simplified into two-dimensional curves or one-dimensional curves by reducing the dimensions of the objects, and the skeletons have the characteristics of neutrality, smoothness, topological isomorphism and the like. The algorithm of the skeleton has great difference, but can be roughly divided into five types from the aspects of calculation and strategy, namely, the first type is a morphological refinement algorithm, the method is based on simulating a grass burning model of Blum in digital voxels to carry out iterative corrosion propagation until one-dimensional skeleton lines are obtained, the method of the type is simple to realize, has good effect on smooth data, but can not guarantee single-pixel property, smoothness and centering of the skeleton, is sensitive to noise, and is easy to generate irrelevant branches; the second is a method of distance field, which calculates the distance from all points to the boundary, then searches local ridge points, connects all ridge points and prunes to obtain skeleton lines, which is mainly suitable for three-dimensional graphics of tubular objects, and has poor centering and smoothness of the obtained skeleton, but has very high calculation efficiency, can reconstruct original objects, is simple to realize, has translational rotation invariance, can ensure topological connectivity, and is usually applied to forward work of some algorithms, the third is a geometric approximation method, which mainly comprises Voronoi diagrams and Reeb diagrams, the middle axis surface of a model is calculated by the two diagrams, and then the skeleton lines are obtained, the method of the type does not depend on the middle axis surface, can directly produce one-dimensional skeleton lines, but has long time consumed by extracting the skeleton by the geometric method, and is not widely applied by the geometric method, the fourth is a field function method, such as forming an electric field or potential field at the boundary of the object, extracting the skeleton according to the distribution of the electric field, the method has relatively insensitive to the noise of the boundary points of the object, the method of the average points is relatively insensitive to the boundary points, in addition, the method has the other disadvantage that the calculation process designs first-order and second-order derivatives, and the calculation is unstable, so that the method cannot be widely used; the fifth class is to approximate the skeleton line according to the ridge points of the shortest path algorithm connection data model, the main advantage of the method is that the shortest cost path has scale independence and has good effect in noise detection, and meanwhile, the algorithm can be easily realized but has the characteristics of poor centering and poor smoothness. Since skeleton lines do not have a uniform and well-recognized mathematical definition, there are differences between different definitions, which also results in the appearance of a large number of algorithms for optimization and iteration on different skeleton line definitions, selecting an appropriate skeletonizing method for a specific application is a great challenge, but in most applications, it is desirable that the skeleton of the model has the characteristics of robustness, smoothness, and neutrality under different digitizing and imaging conditions, and skeleton path tracking can be realized, allowing acceptable reconstruction of the original object, but the former algorithms have certain limitations and do not fully possess all the above properties. Aiming at the defects of the algorithm, the invention provides a curv