JP2005196505A - Adaptive and hierarchical tetrahedral lattice structure representation generation method, program and apparatus for 3D image volume data - Google Patents

Abstract

An object of the present invention is to construct an adaptive tetrahedral hierarchical structure according to local features while considering discontinuity in input volume data.
In the present invention, an algorithm for generating an adaptive tetrahedral lattice structure called an adaptive grid is shown. Until the continuous volume is approximated with a constant accuracy regardless of the viewpoint change, a new grid point of the grid is generated according to local features such as first-order differentiation and isosurface curvature. We have developed a parallel algorithm for adaptive grid generation that recursively divides a body. We also developed a parallel algorithm that preserves discontinuities by avoiding the formation of cracks that occur during the process of each grid element independently performing grid partitioning.
[Selection] Figure 1

Description

  The present invention relates to an adaptive and hierarchical volume model that adaptively and hierarchically represents, reconstructs and visualizes image volume data of a three-dimensional object.

  With the development of CT and MRI, volume data of 3D objects can be obtained accurately and easily. In the field of CG, the problem of expressing, reconstructing, and visualizing such data has rapidly attracted attention (for example, see Non-Patent Documents 1 and 2).

  However, since the data thus obtained is generally enormous, efficient processing requires a volume model that can efficiently represent volume data based on clear accuracy. Researchers are therefore faced with the problem of building a volume model based on accuracy that can be used efficiently in a variety of visual processes.

  In the past decade, new approaches using tetrahedrons, the simplest and most robust cells, have been introduced to build a three-dimensional hierarchical model (eg, Non-Patent Documents 6, 7, 8, 9, 10, 11). A major problem that must be considered in building a hierarchical tetrahedral structure is that cracks may occur in the approximate volume when each tetrahedron is divided independently. This makes parallel implementation more difficult.

  Various approaches have been taken to solve the crack problem. Mauback devised a technique of avoiding cracks by first partially dividing and then expanding the mesh (see, for example, Non-Patent Document 11).

  The Bey method uses a combination of two types of division to avoid cracks (see Non-Patent Document 8, for example).

  Nielson proposed a new approach that uses a batch model by Coon that covers cracks (see, for example, Non-Patent Document 9).

  Although these new tetrahedral approaches have been established, we have developed an implementation for parallel processing and a method for approximating smooth volume data with arbitrary precision that is invariant to changes in viewpoint. There is a need to.

Japanese Patent Laid-Open No. 6-215076 (paragraph numbers 0009 to 0016, FIG. 1) A.E.Kaufman, “State of the Art in Volume Graphics,” VolumeGraphics, pp.3-28, 2001. G.M. Nielson, “Volume Modeling,” Volume Graphics, pp.29-48, 2001. C.H. Chien and J.K. Aggarwal, “VolumeSurface Octrees for the Representation of Three-DimensionalObjects,” Computer Vision Graphics and Image Processing, Vol.36, pp.100-113,1986. Y Zhou and B Chen and A Kaufman, “Multiresolution Tetrahedral Framework for Visualizing Regular Volume Data,” Proc. IEEE Visiualization '97, Phoenix, AZ, pp.135-142, 1997. Trotts.I, Hamann.B, Joy.K, Wiley.D, “Simplefication of tetrahedralmeshes with error bounds”, IEEE Transactions of Visualization and ComputerGraphics, 1999. G.M.Nielson, “Tools for triangulaions and tetrahedrizations intScientific Visualization,” IEEE CS, pp.429-525, 1997. M. Mauback, “Local bisection refinement for Nsimplicial gridsgenerated by reflection,” SIAM Journal of Scientific Computing, Vol. 16, No1, pp. 210-227, 1995. J Bey, “Tetrahedral mesh refinement,” Computing, Vol.55, No13, pp.355-378, 1995. G.M. Nielson and D. Holliday and R.T. Roxborough, “Cracking thecracking problem with Coons patches,” Proc. IEEE Visualization '99, SanFrancisco, CA, 1999. B. Gregorski, M. Duchaineau, P. Lindstrom, V. Pascucci, “InteractiveView-Dependent Rendering Of Large Isosurfaces”, IEEE Visualization 2002, pp.475-482, Nov, 2002. T.Roxborough, G.M.Nielson, “Tetrahedron Based, Least Squares, Progressive Volume Models with Application to Freehand Ultrasound Data”. Ieee2000, pp.93-100, 2000. H.T Tanaka and F.Kishino, “Adaptive mesh generation for surfacereconstruction: Parallel hierarchical triangulation without cracks,” Proc. IEEE10th International Conference on Pattern Recognition, pp.88-94, 1993. H.T Tanaka, “Accuracy-Based Sampling and Reconstruction with Adaptive Meshs for Paralle Hierarchical Triangulation,” int. Journal of Computer Vision and Image Understanding, Vol.61, No3, pp.335-350, 1987.

  Thus, the present invention seeks to construct an adaptive tetrahedral lattice structure for input volume data. The object of the present invention is to generate a grid point of a grid according to local features such as first-order differentiation and curvature of an isosurface until it is approximated with a constant accuracy regardless of changes in the viewpoint, and smoothly changes. To automatically build a hierarchical tetrahedral structure of volume data.

An adaptive and hierarchical tetrahedral lattice structure representation generation program for three-dimensional image data according to the present invention allows a computer to refer to a space represented by input three-dimensional image volume data. Is divided into a set of initial cubic lattice elements, initial setting means for dividing each initial cubic lattice element set by the initial setting means into six isomorphic tetrahedral lattices, and the initial dividing means is divided. A local feature quantity detecting means for detecting a difference in local feature quantities at grid points at both ends of the longest side of the tetrahedral grid,
Recursive neighborhood search means for searching by comparing the difference of the local feature amount with a preset approximation accuracy, and if the difference of the local feature amount does not satisfy the approximation accuracy, until the approximation accuracy is satisfied, A recursive dividing means for recursively dividing the tetrahedral lattice into two tetrahedral lattices at the midpoint of the longest side of the tetrahedral lattice, and when the difference between the local feature quantities satisfies the approximation accuracy In order to confirm the influence from the vicinity, whether or not the magnitude of the change in the local feature amount in each of the tetrahedral lattices adjacent to each other sharing each side of the tetrahedral lattice satisfies the approximation accuracy. A recursive confirmation means for recursively confirming, and based on the change of the local feature quantity recursively searched by the recursive neighborhood search means, the change amount of the local feature quantity in the tetrahedral lattice is a threshold value The recursive dividing means is By recursively divided into two grid, the computer, to produce an adaptive and hierarchical tetrahedral lattice structure representation of multi-resolution three-dimensional image volume data.

  As described above, the recursive confirmation unit is configured to share each side of the tetrahedral grid and share each adjacent tetrahedron in order to confirm the influence from the neighborhood even when the difference in the local feature amount satisfies the approximation accuracy. Since it is recursively confirmed whether or not the magnitude of the change in the local feature amount inside the body lattice satisfies the approximation accuracy, the occurrence of cracks can be avoided.

  In addition, the following affected area can be defined by recursively dividing the tetrahedral lattice divided from the initial cubic lattice elements by the method as described above. Note that the initial cubic lattice element introduced to refer to the space represented by the input three-dimensional image volume data may have an arbitrary size.

  An adaptive and hierarchical tetrahedral lattice structure representation generation program for 3D image data according to the present invention is an area in which the recursive neighborhood search means recursively searches for changes in local features of the initial cubic lattice elements. The distance between the boundary surface in a certain influence area and the surface of the initial cubic lattice element is the six tetrahedral lattices divided from the initial cubic lattice element by the initial dividing unit, and the recursive dividing unit recursively 2 By dividing, it becomes less than the distance of the length of one side of the initial cubic lattice element.

  Since the distance between the boundary surface in the influence area and the surface of the initial cubic lattice element is less than the length of one side of the initial cubic lattice element, there is no crack in the initial cubic lattice element surrounding the initial cubic lattice element. It is guaranteed that the influence of cracks generated in other initial cubic lattice elements does not reach itself.

  The adaptive and hierarchical tetrahedral lattice structure representation generation program for three-dimensional image data according to the present invention is characterized in that the recursive partitioning means, the recursive neighborhood search means, each of the initial cubic lattice elements independently. Based on the change of the local feature value recursively searched within the influence area of the cubic lattice element, the initial cubic lattice element is independently recursively divided into two.

  Accordingly, an adaptive and hierarchical tetrahedral lattice structure representation that does not generate cracks can be generated in parallel and at high speed for each initial cubic lattice element.

  In order to refer to the space represented by the input 3D image volume data, the adaptive and hierarchical tetrahedral lattice structure representation generating apparatus for 3D image data according to the present invention uses the initial cube. Initial setting means for dividing and setting into a set of lattice elements, initial dividing means for dividing each of the initial cubic lattice elements set by the initial setting means into six isomorphic tetrahedral lattices, and the initial dividing means For a tetrahedral grid, a local feature amount detecting means for detecting a difference in local feature amounts at the lattice points at both ends of the longest side of the tetrahedral lattice, and comparing the difference between the local feature amounts with a preset approximation accuracy If the difference between the recursive neighborhood search means for searching and the local feature amount does not satisfy the approximation accuracy, the four points at the midpoint of the longest side of the tetrahedral lattice until the approximation accuracy is satisfied. If the difference between the local feature amount and the recursive dividing means that recursively divides the body lattice into two tetrahedral lattices and satisfies the approximation accuracy, Recursive confirmation means for recursively confirming whether or not the magnitude of the change in local feature amount in each adjacent tetrahedral lattice sharing the sides of the tetrahedral lattice satisfies the approximation accuracy; The recursive neighborhood search means, based on the change of the local feature value recursively searched by the recursive neighborhood search means, until the change amount of the local feature value in the tetrahedral lattice is equal to or less than a threshold value, By recursively dividing the tetrahedral lattice into two, the computer is caused to generate an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation of the three-dimensional image volume data.

The adaptive and hierarchical tetrahedral lattice structure representation generation method for 3D image data according to the present invention uses the initial cube to refer to the space represented by the input 3D image volume data. Initial setting means for dividing and setting a set of lattice elements, recursive neighborhood search means for searching by comparing a difference of local feature amounts with a preset approximation accuracy, and the difference of the local feature amounts satisfy the approximation accuracy If not, recursive dividing means for recursively dividing the tetrahedral lattice into two tetrahedral lattices at the midpoint of the longest side of the tetrahedral lattice until the approximate accuracy is satisfied. A method for generating an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation of 3D image volume data from a space represented by 3D image volume data using an input computer. Preparing a space represented by the three-dimensional image volume data, and dividing the space into a set of initial cubic lattice elements to refer to the space represented by the input three-dimensional image volume data. A step of dividing each initial cubic lattice element set by the initial setting means into six isomorphic tetrahedral lattices; and local feature quantities at lattice points at both ends of the longest side of the tetrahedral lattice. A step for detecting a difference, a step of searching for a difference between the local feature amounts in comparison with a preset approximation accuracy, and if the difference in the local feature amounts does not satisfy the approximation accuracy, A step of recursively dividing the tetrahedral lattice into two tetrahedral lattices at the midpoint of the longest side of the tetrahedral lattice until the difference is satisfied; When the accuracy is satisfied, in order to confirm the influence from the vicinity, the magnitude of the change in the local feature amount in each adjacent tetrahedral lattice sharing each side of the tetrahedral lattice is the approximate accuracy. Recursively confirming whether or not, and based on the change of the local feature amount recursively searched by the recursive neighborhood search means,
The recursive dividing means recursively divides the tetrahedral lattice into two until the change amount of the local feature in the tetrahedral lattice is equal to or less than a threshold value, thereby adapting the three-dimensional image volume data to the computer. Generating a hierarchical and hierarchical multi-resolution tetrahedral lattice structure representation;
including.

  In this specification, field data is synonymous with the local feature amount at each lattice point, and is an arbitrary amount representing local features such as first-order differentiation and curvature of isosurface. Hereinafter, in the present specification, the local feature amount is referred to as field data or field value.

  In the following description, the three-dimensional image volume data is simply referred to as input volume data, and the initial cubic lattice element is referred to as an initial lattice.

  The present invention proposed an adaptive grid parallel algorithm that automatically constructs a tetrahedral hierarchical structure of input volume data. This tetrahedral representation, which can be used as an accurate and efficient volume model, has the advantage that it always satisfies any specified accuracy.

  The present invention also proposes a recursive neighborhood search algorithm that gathers information used for segmentation from neighboring tetrahedrons in order to invalidate the generation of cracks in volume approximation. From the boundary of the referenced neighborhood, the present invention has defined the limit of the reference area of each grid element.

  This definition allows each lattice element to be recursively divided independently. This means that a tetrahedral hierarchical structure without cracks can be constructed at high speed by parallel implementation within a temporal and spatial boundary.

  Furthermore, the above technique of the present invention can be used to adaptively compress any volume data. For example, the above method can be applied to volume data obtained from any image data such as a black and white image, a color image, an MR image, a distance image, or an infrared image.

  An adaptive and hierarchical tetrahedral lattice structure representation generation method, program, and apparatus for three-dimensional image volume data according to the present invention include the following algorithm in its configuration.

  That is, the algorithm according to the present invention includes an initial setting unit that divides and sets a space into a set of initial cube lattice elements to refer to the space represented by the input three-dimensional image volume data, and each initial cube. Initial dividing means for dividing each lattice element into six isomorphic tetrahedral lattices, local feature amount detecting means for detecting a difference in local feature amounts at the lattice points at both ends of the longest side of the tetrahedral lattice, and local feature amounts Recursive neighborhood search means for searching by comparing the difference between the values with a preset approximation accuracy. Furthermore, the algorithm according to the present invention, when the difference in local feature amount does not satisfy the approximation accuracy, converts the tetrahedron lattice into two tetrahedrons at the midpoint of the longest side of the tetrahedral lattice until the approximation accuracy is satisfied. When the recursive dividing means that recursively divides the lattice into two and the difference in local feature values satisfies the approximation accuracy, each side of the tetrahedral lattice is shared in order to confirm the influence from the neighborhood. And recursive confirmation means for recursively confirming whether or not the magnitude of the change in the local feature amount in each adjacent tetrahedral lattice satisfies the approximation accuracy.

  The algorithm according to the present invention is based on the change of the local feature amount recursively searched by the recursive neighborhood search means until the change amount of the local feature amount in the tetrahedral lattice is equal to or less than a threshold value. The means is an algorithm for generating an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation of three-dimensional image volume data by recursively dividing the tetrahedral lattice into two.

  The algorithm described in detail below is hereinafter referred to as an adaptive grid, and is an algorithm for generating an adaptive tetrahedral lattice structure. The adaptive grid is a three-dimensional extension of an adaptive mesh that proposes a method for adaptively reconstructing a free-form surface from an input range image in two dimensions (see, for example, Non-Patent Documents 12 and 13). ).

  In this embodiment, the grid points of the grid are newly set according to local features such as first-order differentiation and isosurface curvature until a continuous volume is approximated with a constant accuracy regardless of the viewpoint change. An adaptive grid generation parallel algorithm that recursively divides a tetrahedron while generating is provided. In addition, a parallel algorithm is provided that avoids the formation of cracks that occur during the process of each grid element independently performing grid division and preserves discontinuities.

  The algorithm for avoiding this crack collects discontinuous information while recursively expanding adjacent tetrahedrons until the discontinuity is confirmed. The boundary reached by this recursive extension defines a three-dimensional reference range for the lattice element.

  Here, the local definition of the reference range allows each lattice element to be divided independently. Therefore, parallelization of a tetrahedral hierarchical structure without cracks is possible in terms of time and space.

(1) Adaptive Grid An adaptive grid obtained by extending the adaptive mesh as shown in FIGS. 1 and 2 to three dimensions will be described below. An adaptive mesh is an algorithm that reconstructs a smooth free-form surface from a distance image based on local features that are invariant to changes in the viewpoint.

First, an adaptive mesh generation method will be described with reference to FIG. 1 (see, for example, Patent Document 1 and Non-Patent Documents 12 and 13). Step 1: Initial lattice. In FIG. 1A, black circles indicate nodes. The lines indicate that they are in parallel with (x, y) coordinate lines orthogonal to each other on the display plane. Step 2: Initial triangulation. In FIG. 1B, the surface shape is recovered together with the depth z, the perpendicular n, the main curvatures k ₁ and k ₂ , and the directions e ₁ and e ₂ at each node. The area bounded by each rectangle is first approximated by two triangles of four adjacent nodes. Step 3: Recursive bisection. In FIGS. 3C and 3D, nodes are increased along the line in accordance with the curvatures at both ends, and the region of high curvature is approximated by a finer triangular piece.

  The following is a recursive bisection algorithm also shown by Mauback (see Non-Patent Document 7). This is used to show parallel adaptive partitioning without cracks.

(1-1) In the algorithm initial setting means, the initial lattice is given at regular intervals as cubic cell elements each having a size of InitCubeSize ³ along the x, y and z axes constituting the volume space. Here, InitCubeSize is the length of one side of the cubic cell that is the initial lattice. The three-dimensional area divided by each cubic cell element is divided into six tetrahedral cells by the initial dividing means as shown in FIG.

Then, the tetrahedron of the route is independently recursively divided into two by the recursive dividing means according to the local features detected by the local feature amount detecting means. This division process is repeated until the internal volume is approximated to the given accuracy Acc _- Thresh.

  An arbitrary size is given as the size of the initial lattice. Grid initialization is independent of the size of the final tetrahedron. This is because all discontinuities are detected and stored by an algorithm that avoids the cracks shown below.

(1-2) The algorithm for constructing a recursive tetrahedral division hierarchy representation is based on dividing the initial lattice step by step. Bisection of the parent tetrahedron T _p is performed when the given accuracy Acc _- Thresh is not satisfied by any of the six sides of T _p .

の中点である。その後、Acc_-Threshが、左右の子四面体Ｔ_ｌとＴ_ｒでそれぞれ独立に再帰的に評価されることにより、四面体が再帰的に二分割されることになる。 A new grid point M is generated by dividing the parent tetrahedron T _p into two child tetrahedrons T _l and T _r . M is the longest side of the tetrahedron = base E
(Formula 1)

Is the middle point. Thereafter, Acc _- Thresh is recursively evaluated independently by the left and right child tetrahedrons T ₁ and T _r , thereby recursively dividing the tetrahedron into two.

(1-2-1) Shape of tetrahedron In the recursive bisection of the tetrahedron, three shapes of tetrahedron including mirror symmetry appear. As shown in FIG. 4, TYPE-I, TYPE-II, and TYPE-III are recursively generated at levels 3N, 3N + 1, and 3N + 2, respectively.

FIG. 5 shows that the tetrahedrons TYPE-I, TYPE-II, and TYPE-III are fixed by using the vertices (P ₀ , P ₁ , P ₂ , P ₃ ) of the parent tetrahedron and the midpoint M of the base. It is defined recursively by the law.

  FIG. 4 shows that, at level 3 (N + 1) after the level 3N tetrahedron TYPE-I is divided three times, a tetrahedron having the same shape with a side length of 1/2 and a volume of 1/8 is generated. It shows that.

ＴＹＰＥ−ＩＩは
（式３）、

ＴＹＰＥ−ＩＩＩは２である。 FIG. 6 shows that the surface shape of TYPE-I, TYPE-II, and TYPE-III is an isosceles triangle or a right triangle. The ratio of the longest / shortest side is TYPE-I (Equation 2),

TYPE-II is (Formula 3),

TYPE-III is 2.

  This tetrahedron split using the midpoint thus satisfies the equiangular requirement. Another advantage is that, for a given range of volume changes, the tree has more approximate levels so that a continuous level of volume approximation is provided.

(1-2-2) Initialization of lattice points The method of the present invention for dividing a cubic cell into six tetrahedrons has two originalities. One is that the six faces of the initial cubic cell share a diagonal line with the adjacent face as shown in FIG. 3A, so that only one tetrahedron needs to be divided. Second, any of the four diagonals that exist when dividing a cubic cell into tetrahedrons does not affect the final tetrahedron division.

  FIG. 17 shows the directions of four defined diagonal lines. These directions are determined by the diagonal directions shared by the six root tetrahedrons in the cubic cell. However, FIG. 17 also shows that after four different initial tetrahedral divisions, the result is the same tetrahedral division after three divisions.

  FIG. 18 shows that four patterns are adjacent in the initial cubic cell. Each set with 1/8 size cells in the same pattern is located diagonally, and all four sets match at the center of the initial cube cell. Thus, omnidirectional effects are irrelevant to the final result.

(1-2-3) Recursive bisection The steps for recursive bisection of a tetrahedron are shown in the code below.
[Code 1]

With each division, the size of all tetrahedrons is halved. Therefore, the maximum division depth n _max is given by the following equation.

  Here, InitCubeSize is the length of one side of the cubic cell that is the initial lattice.

(1-3) Recursive neighborhood search The recursive neighborhood search means and the recursive confirmation means will be described below. A major problem with adaptive segmentation is that cracks can occur when each tetrahedron is segmented independently.

  If there is a large field value change near the initial grid elements, cracks may form along the boundaries between the grid elements. This crack is caused by splitting only one of the lattice elements on the surface where the field value changes greatly.

  In the present invention, in order to prevent cracks between adjacent tetrahedrons, the division determination information is gathered from the neighborhood by recursively expanding the three-dimensional reference area until a sudden change in field data is confirmed. An algorithm was developed.

  In recursive bisection, all tetrahedrons are divided using the midpoint of the base. Inserting a midpoint affects the division of only adjacent tetrahedra that share a base.

For the base E of the tetrahedron T _p , as shown in FIG. 16A, a three-dimensional influence region RI (E) is defined by a set of tetrahedrons sharing E called diamond in this specification. (For example, refer nonpatent literature 10.).

立方体セルの一辺の長さをＬ，
（式４‘）、

とすると、立方体セルの各頂点は次の様に計算できる。
（式４“）、

If E is level 3N and a diagonal line in a cubic cell, RI (E) is composed of six tetrahedrons sharing E and the shape is a cubic cell. The two end points of a given edge E are expressed by (Equation 4),

The length of one side of the cubic cell is L,
(Formula 4 ′),

Then, each vertex of the cubic cell can be calculated as follows.
(Formula 4 "),

If E is a diagonal on the boundary shared by adjacent tetrahedral cells, RI (E) consists of four tetrahedra, two from its own cubic cell, and the other two , The next cubic cell. The vertex of diamond at this time can be calculated as follows.
(Formula 5),

If E is parallel to any of the x, y, and z axes, RI (E) is composed of eight tetrahedra in adjacent cubic cells that share E. The vertex of diamond at this time can be calculated as follows.
(Formula 6),

In the present invention, another division determination is added to the tetrahedron T _p in the affected area RI (E). If any one tetrahedron in RI (E) is divided by the midpoint M, the other tetrahedron is also divided by M. Thus, if the given accuracy is not satisfied by one side of any tetrahedron in the region RI (E), the tetrahedron T _p is defined as the left and right tetrahedron T _l at the midpoint M. It is divided into T _R.

  For each lattice element Cb (i, j, k), the present invention processes the root tetrahedron Rt [i] | (0 ≦ i ≦ 5) independently. First, accuracy is evaluated along the base E. If the accuracy of E does not reach the given accuracy, the tetrahedron RI (E) is immediately divided without performing the neighborhood search. There are two reasons for this.

  1) All tetrahedrons in RI (E) are divided by M from the constraint by E in the affected area RI (E). Thereby, even if the discontinuity of the field value is confirmed inside one tetrahedron in the region RI (E), no crack is generated in the region RI (E). 2) The insertion of the midpoint M only affects the division within the region RI (E). It does not affect the division of neighboring tetrahedrons outside the region RI (E) at all. On the other hand, the division request is postponed until the division determination collected from the vicinity of the lattice element Cb (i, j, k) can be confirmed that the division is correct.

Next, in the influence area RI (E _i ) | (1 ≦ i ≦ 2), the base sides of the tetrahedrons T ₁ and T _r are considered. Thereafter, it is evaluated whether or not the accuracy of the affected area RI (E) has reached a given threshold value. This evaluation process recursively defines a reference region for each base of tetrahedrons T _l and T _r at successive levels. FIG. 16B is a two-dimensional parallel projection of the affected area RI (E) after dividing the six root tetrahedrons in the cubic cell Cb (i, j, k) three times. This recursively expands the reference area of the cubic cell Cb (i, j, k) as shown in FIG.

  If the neighborhood search is performed by the recursive neighborhood search means along the base E (n) defined at the level n and the accuracy is reached in the region RI (E), or the threshold is not satisfied, the division is performed. Is at level n. After that, all tetrahedron division requests that have been searched for are propagated to the root tetrahedron of the cubic cell Cb (i, j, k).

On the other hand, the recursive definition of the affected area RI (E (n)) allowed by the extension of RR (Cb (i, j, k)) continues until the size of RI (E (n)) becomes 1. In this case, since the field value is constant in the neighboring area divided by RR (Cb (i, j, k)), the area divided by Cb (i, j, k) It can be approximated by a root tetrahedron. RI volume, after dividing three times, decreases by a factor of 2 ^3.

  Thus, the reference region RR (Cb (i, j, k)) is expanded recursively. FIG. 16D shows a reference region RR (Cb (i, j, k)) expanded by recursive definition of the affected region RI (E (n)) at each level.

The distance d from the boundary of the lattice element Cb (i, j, k) to the farthest boundary RI is given by the following equation.

  In Equation 2, k = [n / 3], and InitCubeSize is the length of one side of the initial lattice element.

・・・・・（＝１＋６＋８＊（１／６））＊（InitCubeSize）^３
であり、ボリュームの参照領域RR（Cb(ｉ,ｊ,k)）を境界として定義することができた。 Equation (2) means that d _max is limited by InitCubeSize, as shown in FIG. Therefore, as shown in FIG. 16C, from each initial lattice element Cb (i, j, k),
(Formula 7)

... (= 1 + 6 + 8 * (1/6)) * (InitCubeSize) ³
The volume reference region RR (Cb (i, j, k)) can be defined as a boundary.

The maximum division level n _max is given by the following equation.

  The definition of the boundary of the reference area allows each lattice element to be divided independently. This enables parallel computation of recursive tetrahedron division that does not cause cracks in time and space.

These steps are summarized in the code below.
(Code 2)

  Next, the accuracy used in the algorithm according to the present invention will be described in detail.

と、
（式９）

の方向のP_l及びP_ｒにおける曲率
（式１０）

に基づき決定する。 (2) Accuracy First, as in FIG. 19, along the x-axis E _i, field values along the E _i is in the 2D space S represents the height of the direction of the y-axis, tetrahedral all It is assumed that the field value changes along the side E _i of the. In FIG. 19, using an interpolation technique called B-spline, the field value curve between two points P ₁ and P _{r is made} into three B-spline segments (pink painted part, green painted part, red painted part). . The reference point of the colored B-spline purple and yellow, a contact circle defined by P _l and P _r is calculated from the equivalent plane defined by P _l and P _r, defined by Acc_thresh angle Generated by θ. Center O _l and O _r of the contact circle is perpendicular (8)

When,
(Formula 9)

Curvature at _Pl and _Pr in the direction of (Equation 10)

Determine based on.

Changes in field values of consecutive volume data C ₁ along the E _i should be drawn in rather curved than the line. Linear interpolation field values tetrahedron internalization used easily in many techniques, draw a line between points P _l and the point P _r in the space S equivalent (e.g., see Non-Patent Documents 10 and 11. ).

P _l and point P _r are the last points of E _i in space S, and D _i is the three-dimensional distance between P _l and point P _r . R _i is the reciprocal of the curvature of the field value along E _i . Such a curve can be obtained by a curve interpolation technique such as B-spline.

In the embodiment of the present invention, the curve is calculated using the fact that it touches a circle determined by the normal and curvature of the isosurface of the end points drawn as shown in FIG. The exact accuracy of this embodiment is given as the ratio of the field value curvature change to its linear approximation and applies to all sides E _i of all tetrahedrons.

The accuracy is given by:

In Equation 4, m is determined with an accuracy equivalent to the m polygon approximation of the unit circle depicted in FIG. Here, FIG. 7 represents an m-polygon approximation of a unit circle where R is the arc length and D is the code length. Show Acc_thresh as an m-polygon approximation of a unit circle and suppress the angle between gradient vectors of adjacent tetrahedra Acc_thresh = (arc length) / (code length) = π / m
Let sin (π / m) be shown as θ ≦ 2π / m, which suppresses the angle between adjacent adjacent triangles (pieces) of the equivalent surface. This criterion is equivalent to the suppression of the angle between the gradient vectors of adjacent tetrahedra.

Based on this accurate reference, division determination of a given tetrahedron T _p is performed by the following equation.

  The hierarchical volume model according to the present invention is easy to obtain from input data, and can be approximated to any volume data with arbitrary accuracy (see, for example, Non-Patent Documents 3, 4, and 5). ).

  An adaptive and hierarchical tetrahedral lattice structure representation generation method for 3D image volume data according to the present invention uses the above algorithm to generate 3D image volume data from a space represented by 3D image volume data. An adaptive and hierarchical multi-resolution tetrahedral lattice structure representation is generated.

  An adaptive and hierarchical tetrahedral lattice structure representation generation program for 3D image volume data according to the present invention uses the above algorithm to generate 3D image volume data from a space represented by 3D image volume data. It is a program that generates an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation.

  The adaptive and hierarchical tetrahedral lattice structure representation generation apparatus for 3D image volume data according to the present invention uses the above algorithm to generate 3D image volume data from a space represented by 3D image volume data. An apparatus for generating an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation.

  The present invention proposed an adaptive grid parallel algorithm that automatically constructs a tetrahedral hierarchical structure of input volume data. This tetrahedral representation, which can be used as an accurate and efficient volume model, has the advantage that it always satisfies any specified accuracy.

  The present invention also proposed a recursive neighborhood search algorithm that gathers information used for segmentation from neighboring tetrahedrons to invalidate the generation of cracks in volume approximation. From the boundary of the referenced neighborhood, the present invention has defined the limit of the reference area of each grid element.

  This definition allows each lattice element to be recursively divided independently. This means that a tetrahedral hierarchical structure without cracks can be constructed by parallel implementation within a temporal and spatial boundary.

  In the present invention, the three-dimensional image volume data is not particularly limited as long as it is an image sequence, and the image may be a black and white image, an MR image, a distance image, an infrared image, or another image. . The present invention automatically generates a hierarchical / multi-resolution tetrahedral lattice structure representation / model in which 3D image volume data is adaptively compressed to the first and second derivatives from any of the above 3D image volume data. Can be generated. This is because adaptively recursively dividing into two by the first and second derivatives of the voxel value, that is, the pixel value of one image, so what is the physical representation of each pixel value? Because there is no. Therefore, it can be said that the algorithm of the present invention is a general-purpose three-dimensional image volume data compression method.

  In addition, the present invention can be carried out in a mode in which various improvements, modifications, and changes are added based on the knowledge of those skilled in the art without departing from the spirit of the present invention.

  Examples are shown below. In the examples, a CPU-2, 8 GHz, and memory-2 GB PC were used as an experimental environment, C ++ was used as a program language, and VTK (Visualization ToolKit) was used for display.

  In the first embodiment, an experiment of the above algorithm was tried with volume data of a chair having a size of 67 × 129 × 67. The initial grid size is 16 Voxel. The maximum volume value of the data is 255.

FIG. 8 and FIG. 9 show the data of the chair of Example 1, and FIG. 10 and FIG. 11 show the results of parallel projection on the xy and yz planes. Table 1 shows compression ratios at levels 3, 6, 9, and 12.

  In Example 2, an experiment of the above algorithm was attempted using lobster volume data having a size of 320 × 320 × 34. The initial lattice size is 32 Voxel. The maximum volume value of data is 255 as in the first embodiment.

FIG. 12 shows the data of the lobster experimented in Example 2, and FIG. 13, FIG. 14, and FIG. 15 show the results of parallel projection of the results of levels 3, 6, and 9 on the x, y, yz, and zx planes. Shown in Table 2 shows compression ratios at levels 3, 6, 9, and 12.

  The above results indicate that the representation of complex volume data has been effectively and accurately visualized from adaptively sampled volume data.

The figure explaining the flow of the production | generation method of an adaptive mesh. (A) The figure showing the adaptive mesh showing a human face. FIG. 2B is a plan view of FIG. The figure explaining the flow of the initial tetrahedron division of a solid cell. The figure explaining the flow of the recursive division | segmentation of the cube of a primitive of Type-I, Type-II, and Type-III. Diagram illustrating a recursive definition of T _l and T _r for the three primitives. A diagram representing three tetrahedral primitives. The figure explaining m polygon approximation of the unit circle whose R is arc length and D is code length. The figure showing the input data of a chair. 3D drawing of a chair. The xy top view of a chair. The yz top view of a chair. The figure showing the input data of a lobster. Xy, yz, and zx plan view of a level 3 lobster. Xy, yz and zx plan views of a level 6 lobster. Xy, yz, and zx plan views of a level 9 lobster. A series of diagrams representing adjacent regions considered in two divisions of Cb (i, j, k). (A) The figure showing influence area RI (E) of base E. (B) Two-dimensional projection of RI (Cb (I, j, k)). (C) A diagram showing a three-dimensional reference region RR of Cb (i, j, k). (D) A two-dimensional projection view of the recursive extension of the reference region RR (Cb (I, j, k)) at each recursive level, where each level n (= 3N + P) is denoted as (NP). (E) The figure showing the upper limit area where d _max ≦ InitCubeSize. 4 is a flowchart for explaining that four types of first tetrahedron divisions with different diagonal lines result in the same tetrahedron division after one cycle of three divisions. The figure showing 4 patterns which the cell by which the tetrahedron was divided by the finer level adjoins. The interpolation technique of B-spline, the curve of the field values between two points P _l and P _r, 3 single B-spline segments (pink painted part, green painted parts, red painted portion) illustrating how to divide in FIG.

Claims (5)

Computer
Initial setting means for dividing and setting the space into a set of initial cubic lattice elements in order to refer to the space represented by the input three-dimensional image volume data;
Initial dividing means for dividing each initial cubic lattice element set by the initial setting means into six isomorphic tetrahedral lattices;
For a tetrahedral lattice divided by the initial division means, local feature amount detection means for detecting a difference in local feature amounts at the lattice points at both ends of the longest side of the tetrahedral lattice,
Recursive neighborhood searching means for searching for a difference between the local feature quantities by comparing with a preset approximation accuracy;
If the difference between the local feature quantities does not satisfy the approximation accuracy, the tetrahedral lattice is recursively converted into two tetrahedral lattices at the midpoint of the longest side of the tetrahedral lattice until the approximation accuracy is satisfied. Recursive dividing means that divides into two parts,
When the difference between the local feature quantities satisfies the approximation accuracy, in order to confirm the influence from the vicinity, the local feature quantities inside the adjacent tetrahedral grids sharing each side of the tetrahedral grid are checked. Recursive confirmation means for recursively confirming whether the magnitude of the change satisfies the approximation accuracy,
Function as
Based on the change of the local feature amount recursively searched by the recursive neighborhood search means,
Until the change amount of the local feature amount in the tetrahedral lattice is equal to or less than the threshold value,
The recursive dividing means recursively divides the tetrahedral lattice into two,
Causing the computer to generate an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation of 3D image volume data;
An adaptive and hierarchical tetrahedral lattice structure representation generation program for 3D image data. The distance between the boundary surface in the influence area that is an area in which the recursive neighborhood search means recursively searches for a change in the local feature of the initial cube lattice element and the surface of the initial cube lattice element is:
Six tetrahedral lattices divided by the initial dividing means from the initial cubic lattice elements,
By the recursive dividing means recursively dividing into two,
Less than the distance of the length of one side of the initial cubic lattice element,
The adaptive and hierarchical tetrahedral lattice structure representation generation program for three-dimensional image data according to claim 1. The recursive dividing means includes
The recursive neighborhood search means independently searches for the initial cube lattice element independently based on the change in the local feature amount recursively searched within the region of influence of the initial cube lattice element.
Bifurcating each of the initial cubic lattice elements recursively independently,
The adaptive and hierarchical tetrahedral lattice structure expression generation program for three-dimensional image data according to claim 2. In order to refer to the space represented by the input three-dimensional image volume data, initial setting means for dividing and setting the space into a set of initial cubic lattice elements;
Initial dividing means for dividing each initial cubic lattice element set by the initial setting means into six isomorphic tetrahedral lattices;
For a tetrahedral lattice divided by the initial division means, local feature amount detection means for detecting a difference in local feature amounts at both ends of the longest side of the tetrahedral lattice;
Recursive neighborhood search means for searching for a difference between the local feature quantities by comparing with a preset approximation accuracy;
If the difference between the local feature quantities does not satisfy the approximation accuracy, the tetrahedral lattice is recursively converted into two tetrahedral lattices at the midpoint of the longest side of the tetrahedral lattice until the approximation accuracy is satisfied. A recursive dividing means for dividing into two,
When the difference between the local feature quantities satisfies the approximation accuracy, in order to confirm the influence from the vicinity, the local feature quantities inside the adjacent tetrahedral grids sharing each side of the tetrahedral grid are checked. Recursive confirmation means for recursively confirming whether or not the magnitude of the change satisfies the approximation accuracy;
With
Based on the change of the local feature amount recursively searched by the recursive neighborhood search means,
Until the change amount of the local feature amount in the tetrahedral lattice is equal to or less than the threshold value,
The recursive dividing means recursively divides the tetrahedral lattice into two,
Causing the computer to generate an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation of 3D image volume data;
An adaptive and hierarchical tetrahedral lattice structure representation generation apparatus for 3D image data. In order to refer to the space represented by the input three-dimensional image volume data, initial setting means for dividing and setting the space into a set of initial cubic lattice elements;
Recursive neighborhood search means for searching for a difference between local feature quantities by comparing with a preset approximation accuracy;
If the difference between the local feature amounts does not satisfy the approximation accuracy, the tetrahedral lattice is recursively converted into two tetrahedral lattices at the midpoint of the longest side of the tetrahedral lattice until the approximation accuracy is satisfied. Recursive dividing means to divide,
Using a computer with
A method for generating an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation of 3D image volume data from a space represented by 3D image volume data,
Preparing a space represented by the input 3D image volume data;
Dividing the space into a set of initial cubic lattice elements in order to refer to the space represented by the input three-dimensional image volume data;
Dividing each initial cubic lattice element set by the initial setting means into six isomorphic tetrahedral lattices;
A step for detecting a difference in local features at the lattice points at both ends of the longest side of the tetrahedral lattice;
Searching for the difference between the local feature amounts compared to a preset approximation accuracy;
If the difference between the local feature quantities does not satisfy the approximate accuracy, the tetrahedral lattice is recursively reverted to two tetrahedral lattices at the midpoint of the longest side of the tetrahedral lattice until the approximate accuracy is satisfied. A step of dividing into two,
When the difference between the local feature quantities satisfies the approximation accuracy, in order to confirm the influence from the vicinity, the local feature quantities inside the adjacent tetrahedral grids sharing each side of the tetrahedral grid are checked. Recursively checking whether the magnitude of change satisfies the approximation accuracy; and
Based on the change of the local feature amount recursively searched by the recursive neighborhood search means,
Until the change amount of the local feature amount in the tetrahedral lattice is equal to or less than the threshold value,
The recursive dividing means recursively divides the tetrahedral lattice into two,
Causing the computer to generate an adaptive and hierarchical multi-resolution tetrahedral lattice structure representation of the three-dimensional image volume data;
including,
An adaptive and hierarchical tetrahedral lattice structure representation generation method for three-dimensional image data.

Images