JP7783841B2 - Mesh encoding device, mesh decoding device, mesh encoding method and program - Google Patents

Description

The present invention relates to a mesh encoding device, a mesh decoding device, a mesh encoding method, and a program.

The current video-based dynamic mesh coding (V-DMC) model includes two blocks: (1) the encoding process and (2) the decoding process.

In the encoding process, V-DMC first divides the input mesh into a tracked mesh and a non-tracked mesh.

Figure 1(a) shows an example of a non-tracked mesh, and Figure 1(b) shows an example of a tracked mesh. As shown in Figure 1(a), the non-tracked mesh does not have one-to-one vertex (vertex) correspondences or one-to-one edge correspondences between frames. On the other hand, as shown in Figure 1(b), the tracked mesh has both one-to-one vertex (vertex) correspondences and one-to-one edge correspondences between frames.

In Figure 1(b), the number of vertices and faces is the same between the left and right frames, and vertices with the same numbers correspond to each other, and faces with the same patterns correspond to each other.

For tracking meshes, V-DMC skips encoding the current base mesh and encodes the difference between the current base mesh and the previous base mesh, enabling better temporal prediction.

On the other hand, in V-DMC, non-tracked meshes are coded separately, resulting in poor coding efficiency.

Khaled Mammou, Jungsun Kim, Alexis M Tourapis, Dimitri Podborski, and Krasimir Kolarov, “[V-CG] Apple’s Dynamic Mesh Coding CfP Response,” April 2022, ISO/IEC JTC 1/SC 29/WG 7. Zhong, Yu. "Intrinsic shape signatures: A shape descriptor for 3d object recognition." 2009 IEEE 12th international conference on computer vision workshops, ICCV Workshops. IEEE, 2009. Rusinkiewicz, S., & Levoy, M. (2001, May). Efficient variants of the ICP algorithm. In Proceedings third international conference on 3-D digital imaging and modeling (pp. 145-152). IEEE. Sorkine, Olga, and Marc Alexa. "As-rigid-as-possible surface modeling." Symposium on Geometry processing. Vol. 4. 2007.

The above-mentioned conventional technology allows interframe coding only for frames of a tracking mesh that have a one-to-one correspondence between vertices and faces.

However, with the above-mentioned conventional technology, only intra-frame coding could be performed on frames of non-tracking meshes, resulting in low coding efficiency.

The present invention was made in consideration of the above-mentioned problems, and aims to propose a mesh encoding device, mesh decoding device, mesh encoding method, and program that can generate a tracking base mesh from a non-tracking mesh, enabling inter-frame coding and significantly improving coding efficiency.

A first feature of the present invention is a mesh encoding device comprising: a remeshing unit that divides an input mesh sequence into subgroups and generates a tracking base mesh sequence for each subgroup; and a subdivision unit that derives a displacement amount from the tracking base mesh sequence and the mesh sequence.

A second feature of the present invention is a mesh decoding device that includes a mesh decoding unit that rearranges the order of decoded basic meshes based on the decoded encoding order.

A third feature of the present invention is a mesh decoding method that includes a step of rearranging the order of decoded basic meshes based on the decoded encoding order.

A fourth feature of the present invention is a program that causes a computer to function as a mesh decoding device, the mesh decoding device comprising a mesh decoding unit that rearranges the order of decoded basic meshes based on the decoded encoding order.

The present invention provides a mesh encoding device, mesh decoding device, mesh encoding/decoding method, and program that enable inter-frame coding and significantly improve coding efficiency by generating a tracking base mesh from a non-tracking mesh.

FIG. 1 is a diagram for explaining the prior art. FIG. 2 is a diagram showing an example of the configuration of a mesh processing system 1 according to an embodiment. FIG. 3 is a diagram showing an example of functional blocks of the mesh coding device 100 according to an embodiment. FIG. 4 is a diagram showing an example of functional blocks of the remeshing unit 101 of the mesh coding device 100 according to an embodiment. FIG. 5A is a diagram showing an example of functional blocks of the dynamic tracking unit 101B of the remeshing unit 101 of the mesh encoding device 100 according to an embodiment. FIG. 5B is a diagram showing an example of functional blocks of the tracking and deformation unit 101B02 of the dynamic tracking unit 101B of the remeshing unit 101 of the mesh encoding device 100 according to an embodiment. FIG. 6 is a diagram for explaining the function of the rough deformation unit 101B02c of the tracking and deformation unit 101B02 of the dynamic tracking unit 101B of the remeshing unit 101 of the mesh coding device 100 according to an embodiment. FIG. 7 is a diagram for explaining the function of the fine deformation unit 101B02d of the tracking and deformation unit 101B02 of the dynamic tracking unit 101B of the remeshing unit 101 of the mesh coding device 100 according to an embodiment. FIG. 8 is a flowchart showing an example of the operation of the tracking base mesh generation unit 101C of the remeshing unit 101 of the mesh coding device 100 according to an embodiment. FIG. 9 is a diagram for explaining an example of edge removal by the tracking basic mesh generation unit 101C of the remeshing unit 101 of the mesh coding device 100 according to an embodiment. FIG. 10 is a diagram illustrating an example of functional blocks of a mesh decoding device 200 according to an embodiment.

Embodiments of the present invention will be described below with reference to the drawings. Note that the components in the following embodiments can be appropriately replaced with existing components, and various variations, including combinations with other existing components, are possible. Therefore, the following description of the embodiments does not limit the content of the invention described in the claims.

First Embodiment
The mesh processing system 1 according to this embodiment will be described below with reference to FIGS.

Figure 2 is a diagram showing an example of the configuration of a mesh processing system 1 according to this embodiment. As shown in Figure 2, the mesh processing system 1 includes a mesh encoding device 100 and a mesh decoding device 200.

Figure 3 is a diagram showing an example of functional blocks of the mesh coding device 100 according to this embodiment.

As shown in Figure 3, the mesh encoding device 100 includes a remeshing unit 101, a subdivision unit 102, and an encoding unit 103.

The remeshing unit 101 is configured to receive the input mesh sequence M and subgroup number k, and output the tracked and thinned tracking base mesh sequence TM and coding order C.

That is, the remeshing unit 101 is configured to divide the input mesh sequence M into subgroups and generate a tracking base mesh sequence TM for each subgroup.

Here, the mesh sequence M is composed of multiple meshes. Such a mesh sequence M may include only non-tracking meshes, or may include both non-tracking meshes and tracking meshes. If the mesh sequence M includes both non-tracking meshes and tracking meshes, only the non-tracking meshes may be subject to processing in the remeshing unit 101 and the subdivision unit 102, or both the non-tracking meshes and tracking meshes may be subject to processing in the remeshing unit 101 and the subdivision unit 102.

In this embodiment, the term "frame" is synonymous with "mesh."

Furthermore, the subgroup number k instructs the subblock to generate tracked meshes every k frames, and the order of the meshes is changed for each subgroup and recorded in the encoding order C.

The subdivision unit 102 is configured to derive the displacement D from the tracking base mesh sequence TM and the mesh sequence M.

Specifically, the subdivision unit 102 subdivides the tracking base mesh sequence TM obtained by the remeshing unit 101, and compares the tracking base mesh sequence TM with the mesh sequence M to derive the displacement amount D.

The encoding unit 103 compresses the above-mentioned tracking base mesh sequence TM, displacement D, and subgroup number k into a compressed bitstream b.

The encoding unit 103 also uses the same technology as in Non-Patent Document 1, but changes the encoding order to be given by encoding order C.

(Remeshing unit 101)
FIG. 4 is a diagram illustrating an example of functional blocks of the remeshing unit 101. As shown in FIG.

As shown in FIG. 4, the remeshing unit 101 includes a mesh refinement unit 101A, a dynamic tracking unit 101B, and a tracking base mesh generation unit 101C. Here, the remeshing unit 101 does not necessarily have to include the mesh refinement unit 101A.

The function of the remeshing unit 101 is to generate a sequence of tracking base meshes that have a one-to-one correspondence between vertices and edges.

(Mesh refinement unit 101A)
The mesh refinement unit 101A receives an input mesh sequence M and removes duplicate vertices and short edges from the input mesh sequence M.

Specifically, the mesh refinement unit 101A can remove duplicate vertices using the following method:

First, the mesh refinement unit 101A creates a KDTree of vertices, finds the closest vertex to the current vertex, and removes the current vertex if the distance from the current vertex to that closest vertex is 0.

Second, after removing duplicate vertices, the mesh refinement unit 101A removes all short edges whose length is less than 0.1 of the average length.

(Dynamic tracking unit 101B)
The dynamic tracking unit 101B is configured to receive the refined mesh sequence and subgroup number k as input, divide the mesh sequence into multiple subgroups of k frames each, and perform processing to track each subgroup.

That is, the dynamic tracking unit 101B is configured to divide the mesh sequence M into subgroups and generate a tracking mesh sequence for each subgroup.

As shown in Figure 5A, the dynamic tracking unit 101B includes a subgroup generation unit 101B01 and a tracking and deformation unit 101B02.

Essentially, the subgroup generation unit 101B01 divides the mesh sequence into subgroups of k frames each, where k is defined by the user.

The subgroup generation unit 101B01 can also divide such a mesh sequence into an even number of subgroups.

In this embodiment, the remeshing unit 101 designates a frame in each subgroup as reference frame Y and remeshes the other frames so that they have a one-to-one correspondence between vertices and edges with reference frame Y.

In this embodiment, the remeshing unit 101 basically specifies the [k/2]th frame of each subgroup as the reference frame, but it is also possible to specify any other frame as the reference frame.

Figure 5B is a diagram showing an example of the functional blocks of the tracking and deformation unit 101B02. The tracking and deformation unit 101B02 is configured to remesh the current frame X based on the reference frame Y.

As shown in FIG. 5B, the tracking and deformation unit 101B02 includes a keypoint generation unit 101B02a, a keypoint matching unit 101B02b, a coarse deformation unit 101B02c, a fine deformation unit 101B02d, and a motion estimation unit 101B02e.

Here, the tracking and deformation unit 101B02 does not necessarily have to include the motion estimation unit 101B02e.

The keypoint generation unit 101B02a is configured to detect (generate) keypoints of a mesh in a reference frame Y and keypoints of a mesh in a current frame X.

Specifically, the keypoint generation unit 101B02a is configured to separately generate keypoints for the current frame X and keypoints for the reference frame Y.

The keypoint generation unit 101B02a can generate such keypoints using the method of Non-Patent Document 2 or other keypoint generation methods. Here, the set of keypoints in the current frame X is denoted as {x ₁ , x ₂ , ... x _m }, and the set of keypoints in the reference frame Y is denoted as {y ₁ , y ₂ , ... _yn }.

The keypoint matching unit 101B02b is configured to associate keypoints of a mesh in the reference frame Y with keypoints of a mesh in the current frame X.

Specifically, the keypoint matching unit 101B02b is configured to match a set of keypoints {x ₁ , x ₂ , ... x _m } of the current frame X with a set of keypoints {y ₁ , y ₂ , ... _yn } of the reference frame Y, and generate two matching sets of keypoints {x ₁ ', x ₂ ', ... x _v '} and {y ₁ ', y ₂ ', ... y _v '}.

For example, the keypoint matching unit 101B02b can use the following Algorithm 1 to match the above-mentioned keypoints.

Here, the keypoint matching unit 101B02b basically finds nearby vertices by KDTree neighborhood search, but other neighborhood search methods can also be used.

In addition, in Non-Patent Document 3, the keypoint matching unit 101B02b aligns nearby vertices using the ICP Registration method, but it can also align nearby vertices using other point cloud alignment methods.

The coarse deformation unit 101B02c deforms the mesh of the reference frame Y so that the position of key point 7 in the reference frame Y moves to the position of key point 9 in the current frame X, as shown in Figure 6, to obtain a deformed reference frame Y1.

Basically, the rough deformation section 101B02c uses the method described in Non-Patent Document 4, but other deformation methods can also be used.

The fine deformation unit 101B02d moves all of the vertices of the deformed reference frame Y1 onto the surface of the mesh in the current frame X, as shown in Figure 7.

Basically, in this embodiment, the fine deformation unit 101B02d performs finer deformation than the coarse deformation unit 101B02c, using Algorithm 2 below.

That is, the coarse deformation unit 101B02c and the fine deformation unit 101B02d are configured to simultaneously perform coarse deformation and fine deformation, respectively, by remeshing the mesh of the reference frame Y to approximate the mesh of the current frame X.

When a mesh from a past frame Z is tracked by a mesh from a reference frame Y, a motion estimation unit 101B02e may be placed before the keypoint matching unit 101B02b.

The motion estimation unit 101B02e is configured to estimate motion from a mesh in a reference frame Y to a mesh in a current frame Z, and add the estimated motion to the mesh in the reference frame Y as input to the remeshing unit 101.

Basically, the motion estimation unit 101B02e calculates the motion vector MOV(Y,Z) from the reference frame Y to the previous frame Z, and adds 2MOV(Y,Z) to the mesh of the reference frame Y.

(Tracking basic mesh generation unit 101C)
The tracking base mesh generation unit 101C generates a tracking base mesh sequence for each subgroup.

Specifically, the tracking base mesh generation unit 101C is configured to perform edge collapse of all tracking mesh sequences within a subgroup, as described below, to generate a tracking base mesh sequence TM.

The tracking meshes within a subgroup have a one-to-one correspondence between vertices and edges.

Below, an example of the operation of the tracking base mesh generation unit 101C will be described with reference to Figure 8.

As shown in Figure 8, in step S101, the tracking base mesh generation unit 101C calculates the quadric error when folding each edge e_i.

In step S102, the tracking base mesh generation unit 101C finds the edge e_current with the smallest second-order error and folds this e_current.

In step S103, the tracking base mesh generation unit 101C determines whether the target count has been reached.

If the answer is Yes, this operation ends; if the answer is No, this operation proceeds to step S104.

In step S104, the tracking base mesh generation unit 101C updates the second-order error.

The tracking base mesh generation unit 101C repeats steps S102 and S104 until the target count is reached.

Here, the second-order error of the edge e_current is defined as follows (Equation 1):

where C _j is the length of e _current in the j-th mesh, Q _j (e _current ) is the quadratic error of e _current in the j-th mesh, and x is the Euclidean coordinate position of the new vertex to insert into the mesh.

The tracking base mesh generation unit 101C performs edge removal by simultaneously removing one edge from the mesh of all frames in the subgroup and inserting a new vertex back at position x, as shown in Figure 9.

Figure 10 shows an example of the configuration of a mesh decoding device 200 according to this embodiment.

As shown in FIG. 10, the mesh decoding device 200 includes a DEMUX unit 201, a basic mesh decoding unit 202, a coding order decoding unit 203, a displacement amount decoding unit 204, a subdivision unit 205, and a mesh decoding unit 206.

Here, the DEMUX unit 201, displacement amount decoding unit 204, subdivision unit 205, and mesh decoding unit 206 have the same functions as those described in Non-Patent Document 1.

The coding order decoding unit 203 is configured to decode the coding order C and transmit it to the basic mesh decoding unit 202.

The base mesh decoding unit 202 has the same functions as those described in Non-Patent Document 1, but is configured to rearrange the order of the decoded base meshes according to the encoding order C.

Here, since there is a large amount of movement between the first and last meshes contained in the basic mesh bitstream transmitted from the mesh encoding device 100 according to this embodiment, if the order of the decoded basic meshes is not rearranged, there is a possibility that the remeshing error will be large.

Therefore, the mesh decoding device 200 according to this embodiment can minimize remeshing errors by specifying a reference frame midway through a subgroup and rearranging the order of the base meshes according to the coding order C.

In other words, according to the mesh decoding device 200 of this embodiment, by rearranging the order of the basic meshes according to the encoding order C, the difference in shape between the meshes in the reference frame and the meshes in the current frame is reduced, reducing remeshing errors and improving compression quality.

The mesh processing system 1 according to this embodiment generates a tracking base mesh from a non-tracking mesh, enabling inter-frame coding and significantly improving coding efficiency.

The mesh encoding device 100 and mesh decoding device 200 described above may be realized as a program that causes a computer to execute each function (each process).

Note that, according to this embodiment, it is possible to achieve an improvement in overall service quality in video communication, for example, and therefore contribute to the achievement of Goal 9 of the United Nations-led Sustainable Development Goals (SDGs), which is to "Develop resilient infrastructure, promote sustainable industrialization and foster innovation."

DESCRIPTION OF SYMBOLS 1...Mesh processing system 100...Mesh encoding device 101...Remeshing unit 101A...Mesh refinement unit 101B...Dynamic tracking unit 101B01...Subgroup generation unit 101B02...Tracking and deformation unit 101B02a...Keypoint generation unit 101B02b...Keypoint matching unit 101B02c...Coarse deformation unit 101B02d...Fine deformation unit 101B02e...Motion estimation unit 101C...Tracking base mesh generation unit 102...Subdivision unit 103...Encoding unit 200...Mesh decoding device

Claims (9)

a remeshing unit that divides the input mesh sequence including the non-tracking mesh into subgroups and generates a tracking base mesh sequence and a coding order for each of the subgroups;
a subdivision unit for deriving displacements from the tracking base mesh sequence and the mesh sequence;
A mesh coding device comprising : a coding unit that compresses the tracking basic mesh sequence, the displacement amount, and the coding order into a bit stream . The remeshing unit
a dynamic tracking unit that divides the mesh sequence into the subgroups and generates a tracking mesh sequence for each of the subgroups;
2. The mesh encoding device according to claim 1, further comprising a tracking base mesh generation unit that performs edge erasure on all of the tracking mesh sequences in the subgroup and generates the tracking base mesh sequence. The dynamic tracking unit
Detecting mesh keypoints of the reference frame and mesh keypoints of the current frame;
Corresponding mesh keypoints of the reference frame with mesh keypoints of the current frame;
3. The mesh encoding device according to claim 2, wherein coarse and fine deformations are simultaneously performed by remeshing the mesh of the reference frame so as to approximate the mesh of the current frame. The mesh encoding device of claim 3, wherein the dynamic tracking unit estimates the movement of the mesh from the mesh of the reference frame to the current frame and adds the estimated movement to the mesh of the reference frame as input to the remeshing unit. A mesh decoding device that generates a decoded mesh from a bit stream in which a tracking basic mesh sequence, a displacement amount, and a coding order are compressed, comprising:
a DEMUX unit for separating the bitstream into a basic mesh bitstream, a coding order bitstream, and a displacement bitstream;
a coding order decoding unit that decodes the coding order bitstream to generate a coding order;
a base mesh decoding unit that decodes the base mesh bitstream to generate base meshes and rearranges the order of the base meshes based on the decoded coding order;
a subdivision unit configured to subdivide the base mesh to generate a subdivided mesh;
a displacement decoder configured to decode the displacement bitstream to generate displacements;
a mesh decoding unit configured to generate a decoded mesh using the subdivision mesh and the displacement amount . A mesh decoding method for generating a decoded mesh from a bit stream obtained by compressing a tracking basic mesh sequence, a displacement amount, and a coding order , comprising:
Separating the bitstream into a base mesh bitstream, a coding order bitstream, and a displacement bitstream;
decoding the coding order bitstream to generate a coding order;
decoding the base mesh bitstream to generate base meshes, and rearranging the order of the base meshes based on the decoded coding order ;
a step configured to subdivide the base mesh to generate a refined mesh;
configured to decode the displacement amount bitstream to generate displacement amounts;
generating a decoded mesh using the subdivision mesh and the displacement amount . A program that causes a computer to function as a mesh decoding device that generates a decoded mesh from a bit stream in which a tracking basic mesh sequence, a displacement amount, and an encoding order are compressed, the program comprising:
The mesh decoding device comprises:
a DEMUX unit for separating the bitstream into a basic mesh bitstream, a coding order bitstream, and a displacement bitstream;
a coding order decoding unit that decodes the coding order bitstream to generate a coding order;
a base mesh decoding unit that decodes the base mesh bitstream to generate base meshes and rearranges the order of the base meshes based on the decoded coding order ;
a subdivision unit configured to subdivide the base mesh to generate a subdivided mesh;
a displacement decoder configured to decode the displacement bitstream to generate displacements;
a mesh decoding unit configured to generate a decoded mesh using the subdivision mesh and the displacement amount . Dividing the input mesh sequence including non-tracking meshes into subgroups, and generating a tracking base mesh sequence and a coding order for each subgroup;
deriving a displacement from the tracking base mesh sequence and the mesh sequence;
A mesh coding method comprising a step of compressing the tracking base mesh sequence, the displacements and the coding order into a bitstream. A program that causes a computer to function as a mesh encoding device,
The mesh encoding device comprises:
a remeshing unit that divides the input mesh sequence including the non-tracking mesh into subgroups and generates a tracking base mesh sequence and a coding order for each of the subgroups;
a subdivision unit for deriving displacements from the tracking base mesh sequence and the mesh sequence;
A program comprising an encoding unit that compresses the tracking basic mesh sequence, the displacement amount, and the encoding order into a bit stream.