JP7614801B2 - Image processing device, image processing method and program - Google Patents

Description

The present invention relates to a technology for generating data that represents the three-dimensional shape of an object using polygons.

In applications such as VR, AR, and street viewing, there is a demand for the generation of high-quality computer graphics (hereinafter referred to as "CG") polygon models that represent the three-dimensional shapes of people and the like. Generally, polygon models are created manually by creators, and it is very difficult and time-consuming to create polygon models with a large number of polygons and beautiful appearances. As a method to reduce the creator's efforts, there is a technology called photogrammetry that generates polygon models from images of real-world objects. In the volume intersection method, one of the representative photogrammetry methods, the silhouette of an object is extracted from images captured from multiple viewpoints, and data is generated that represents the three-dimensional shape of the object in voxels based on the extracted silhouette information. Then, a polygon model is generated that is represented by polygons that cover the voxel surface according to the arrangement of the voxels in the three-dimensional space.

By appropriately reducing the number of polygons in a polygon model obtained by photogrammetry, a simplified polygon model (with a coarser polygon mesh) can be obtained depending on the intended use. Non-Patent Document 1 discloses a method (hereinafter referred to as the "QEM method") for reducing the number of polygons by aggregating two vertices connected by an edge in a polygon model into one vertex.

Michael Garland, Paul S. Heckbert, “Surface Simplification Using Quadric Error Metrics”, 1997.

However, with the QEM method, there was an issue that after inputting a high-density polygon model, it took a lot of time to calculate pairs of vertices that would minimize shape error and then aggregate them into a single appropriate vertex.

The technology disclosed herein aims to propose a technique that reduces the burden of generating shape data represented by polygons.

The image processing device according to the present disclosure comprises a determination means for determining polygons according to a voxel arrangement based on shape data in which the three-dimensional shape of an object is represented in voxels, a calculation means for calculating vertices in voxel units of a specific scale from information regarding the polygons determined by the determination means, and a generation means for generating shape data in which the three-dimensional shape of the object is represented in polygons based on connecting the vertices calculated by the calculation means, wherein when the specific scale is r times (r>1), the calculation means calculates the vertices based on the distance relationship between the one or more faces to be generated and points that can become the vertices .

The technology disclosed herein can reduce the burden of generating shape data represented by polygons.

FIG. 1 is a diagram showing an example of the configuration of a virtual viewpoint video system. FIG. 1 is a diagram for explaining an overview of a polygon model generation technique according to the present disclosure. Diagram explaining macro-scale voxels Block diagram showing the functional configuration of an image processing device 1 is a flowchart showing a process for generating a polygon model according to the first embodiment. Diagram explaining the MC method FIG. 1 is a diagram showing an example of an MC table. A diagram explaining the relationship between MC voxels and edge indices. FIG. 1 is a diagram for explaining the connection relationship between an MC voxel and an adjacent MC voxel. A diagram showing the surface generation pattern in the MC method. A diagram showing a three-dimensional space in which multiple MC voxels are aligned. 1A is a diagram showing an example of a result of a calculation process of a representative vertex, and FIG. 1B is a diagram showing an example of a result of a topology determination process. 10 is a flowchart showing the flow of a process for generating a polygon model according to a second embodiment. FIG. 13 is a diagram for explaining a polygon model obtained according to the second embodiment;

The following describes an embodiment of the present invention with reference to the drawings. Note that the following embodiment does not limit the present invention, and not all of the combinations of features described in the present embodiment are necessarily essential to the solution of the present invention. Note that the same components are described with the same reference numerals.

[Embodiment 1]
In this embodiment, a case where a simplified polygon model is generated as three-dimensional shape data of an object required for generating a virtual viewpoint video will be described as an application example. The virtual viewpoint video is obtained by rendering using the polygon model, which is the three-dimensional shape data of the object.

<System Configuration>
FIG. 1 is a diagram showing an example of the configuration of a virtual viewpoint video system in this embodiment. The virtual viewpoint video is a video generated by an end user and/or a designated operator freely manipulating the position and posture of a virtual viewpoint (a virtual camera that does not exist in reality), and is also called a free viewpoint video or an arbitrary viewpoint video. The virtual viewpoint image allows the highlight scenes of sports such as soccer and rugby to be viewed from various angles, so that a high sense of realism can be given to the user compared to normal images. The virtual viewpoint video system shown in FIG. 1 includes an image processing device 100, a camera group 110, and a virtual viewpoint video generation device 120.

The image processing device 100 receives video data from the camera group 110. This video data is video data captured from multiple different viewpoints. Then, from the received video data corresponding to the multiple viewpoints, a polygon model is generated, which is shape data that represents the three-dimensional shape of an object using polygons. The generated polygon model is sent to the virtual viewpoint video generation device 120.

The camera group 110 is composed of multiple digital video cameras (hereinafter simply referred to as "cameras") that serve as imaging devices. Each camera is equipped with a video signal interface such as a serial digital interface (SDI), and outputs video data captured by each camera to the image processing device 100 via the video signal interface.

The virtual viewpoint video generating device 120 performs rendering processing using the polygon model received from the image processing device 100 to generate a virtual viewpoint video that represents the view from the virtual viewpoint specified by the user. In the rendering processing, a process of applying texture to the surface of the three-dimensional shape represented by the polygon model (a process of determining the color of the surface) is performed according to separately input virtual viewpoint information, thereby generating a virtual viewpoint video. The generated virtual viewpoint video data is output and displayed on a display device (not shown), such as a liquid crystal display, for viewing by the user.

The virtual viewpoint information includes at least information about the position and direction of the virtual viewpoint. Furthermore, the specification of the virtual viewpoint includes at least specification of the position and direction of the virtual viewpoint. Furthermore, the specification of the virtual viewpoint does not have to be specified by the user. For example, the device may be configured to specify it automatically. There are various other components in addition to those mentioned above regarding the system configuration, but as they are not the main focus of the present invention, a description of them will be omitted.

<Hardware configuration of image processing device>
Next, the hardware configuration of the image processing device 100 will be described with reference to FIG. 1. The image processing device 100 includes a CPU 101, a main memory 102, a HDD 103, an input unit 104, a display unit 105, and an external I/F 106, and each unit is connected via a bus 107. First, the CPU 101 is an arithmetic processing device that controls the image processing device 100 in an integrated manner, and executes various programs stored in the HDD 103 or the like, controls the camera group 110 to acquire multiple viewpoint video data, and performs various image processing including a polygon model generation process described later. The main memory 102 temporarily stores data and parameters used in various processes, and provides a working area for the CPU 101. The HDD 103 is a non-volatile large-capacity storage device that stores various programs and input video data, and may be, for example, an SSD. The input unit 104 is a device such as a keyboard, a mouse, an electronic pen, or a touch panel, and accepts various user instructions. The display unit 105 is composed of a liquid crystal panel or the like, and displays a UI (user interface) screen. The external I/F unit 106 is a communication interface that transmits and receives various data, such as video data captured by each camera and polygon models, to and from each camera constituting the camera group 110 and the virtual viewpoint video device 120 via a network (here, LAN 108). The bus 107 connects the above-mentioned units and transfers data. The virtual viewpoint video device 120 also has a configuration similar to that of the image processing device 100, and performs the above-mentioned rendering process using a CPU and main memory.

<Overview of the technology disclosed herein>
2 is a diagram for explaining an overview of the polygon model generation process according to the present disclosure. Here, an example will be described in which an object 200 having a simple shape combining a quadrangular pyramid and a cube is captured from various viewpoints using multiple cameras 201, and its three-dimensional shape is restored based on the obtained multiple viewpoint images.

<STEP 1>
A plurality of cameras 201 are arranged to surround the object 200 and capture images corresponding to a plurality of viewpoints, and captured images are obtained. At this time, the orientation, posture, focal length, exposure control parameters, etc. of each of the cameras 201 constituting the camera group 110 are set so that the object 200 is appropriately contained within the angle of view.

<STEP 2>
Shape data (hereinafter referred to as "voxel data") expressing the three-dimensional shape of the object 200 in voxels is generated from silhouette information of the object 200 in each captured image corresponding to a plurality of viewpoints using a visual volume intersection method or the like. In Fig. 2, black rectangles indicate remaining voxels (ON voxels) that were located inside the visual volume, and white rectangles indicate deleted voxels (OFF voxels) that were located outside the visual volume.

<STEP 3>
A surface (polygon) according to the voxel arrangement is determined for the voxel data obtained in STEP 2. In Fig. 2, the white dotted lines indicate the determined surfaces.

<STEP 4>
By referring to the information on the surface, the most likely vertices in the simplified polygon model are calculated in units of voxels with a specific scale larger than that of the input voxel. In the following description, the specific scale is called "macroscale" and the voxels in the macroscale are called "macrovoxels". FIG. 3 is a diagram for explaining macrovoxels. The smallest rectangle 300 indicates the input voxel, the largest rectangle 301 indicates a macrovoxel with a scale of 8 times, the rectangle 302 indicates a macrovoxel with a scale of 4 times, and the rectangle 303 indicates a macrovoxel with a scale of 2 times. Note that the scale of the macrovoxel may be the same as that of the input voxel (i.e., the scale is 1 times). In FIG. 2, the rectangle with the dashed dotted line indicates the macrovoxel, and the double circle indicates the most likely vertex calculated in units of the macrovoxel.

<STEP 5>
A topology is determined for the likely vertices calculated in STEP 4, and the vertices are connected to generate a polygon model with a simplified shape. In Fig. 2, the white solid lines indicate the determined topology (≒ faces).

The above is an overview of the polygon model generation process according to the present disclosure. Note that the objects to which the technology of the present disclosure can be applied are not limited to objects with simple shapes such as those shown in FIG. 2, but it goes without saying that the technology can also be applied to the reconstruction of the three-dimensional shapes of objects with more complex shapes, such as general living things, buildings, and vehicles.

<Software configuration of image processing device>
4 is a block diagram showing the functional configuration of the image processing device 100 according to this embodiment. The image processing device 100 includes a captured image acquisition unit 401, a camera calibration unit 402, a silhouette image generation unit 403, a voxel data generation unit 404, a surface determination unit 405, a representative vertex calculation unit 406, and a representative vertex connection unit 407.

The captured image acquisition unit 401 acquires data of images (multiple viewpoint images) captured from different viewpoints by the multiple cameras 201 that make up the camera group 110. The acquired multi-viewpoint image data is input to the camera calibration unit 402 and the silhouette image generation unit 403.

The camera calibration unit 402 performs camera calibration, for example, at a timing such as before the start of a match, and derives the camera parameters of each camera 201 constituting the camera group 110. The camera parameters include internal parameters, external parameters, and distortion parameters. The camera calibration procedure is roughly as follows. First, a planar pattern such as a square grid is captured by each camera 201. Next, feature points are detected from each of the captured images of each camera 201 obtained, and the coordinates of the feature points are obtained in the image coordinate system. Here, the feature points are the intersection points of orthogonal straight lines in the case of a square grid. Then, the initial values of the internal parameters are calculated using the coordinates of the obtained feature points. Here, the internal parameters are parameters that represent the focal length and the optical center called the principal point. In addition, the initial values of the internal parameters do not necessarily need to be calculated from the feature points in the image, and the design values of the camera may be used. Next, the internal parameters, external parameters, and distortion parameters are calculated by a nonlinear optimization process called bundle adjustment. Here, the external parameters are parameters that represent the camera position, line of sight, and rotation angle around the line of sight. The distortion parameters are coefficients that represent radial image distortion caused by differences in the refractive index of the lenses, and circumferential distortion caused by the lens and the image plane not being parallel. There are many other camera calibration methods, but details are omitted as they are not the focus of this invention. The camera parameters of each camera 201 obtained by camera calibration are stored in the HDD 103.

The silhouette image generation unit 403 extracts an area (foreground area) corresponding to the silhouette of an object from each captured image constituting the multi-viewpoint image, and generates a binary image (silhouette image) in which the foreground area is represented by "1" and the other background areas are represented by "0". There are various methods for extracting the foreground area, and no particular limitation is imposed. For example, in the case of the background difference method, images are captured when an object is present and when it is not present, and the area corresponding to the difference between the two captured images is extracted as the silhouette of the object.

The voxel data generation unit 404 generates voxel data that expresses the three-dimensional shape of an object as a set of voxels based on the silhouette image generated by the silhouette image generation unit 403 and the camera parameters derived by the camera calibration unit 402. There are various methods for deriving the three-dimensional shape of an object from a silhouette image, and there is no particular limitation to these. In this embodiment, the visual hull (VH) method is used. The VH method is a method in which the silhouette area (foreground area) in the silhouette image is projected into space based on the camera parameters, and the intersection of the projected areas is defined as the shape of the object. Specifically, a three-dimensional space in which voxels of a certain scale are laid out is first defined. Next, for all voxels in the three-dimensional space, the voxels are projected from the three-dimensional coordinates onto the two-dimensional image of each camera. At this time, it is determined whether the projected voxels overlap with the silhouette of the object of each camera, and if the number of cameras determined to overlap is equal to or greater than a preset threshold, the voxel is defined as part of the shape of the object. For example, a flag of "0" is assigned to all voxels as an initial value, and a flag of "1" is assigned to voxels that are determined to be part of the shape of an object. A set of voxels that are assigned a flag of "1" becomes voxel data that represents the three-dimensional shape of an object. In this embodiment, an example of generating voxel data using the VH method is described, but the method of obtaining the three-dimensional shape of an object does not necessarily have to be the VH method. For example, voxel data can be obtained by acquiring the shape of an object as a point cloud using a stereo matching method, and then assigning a flag of "1" to the area in which the acquired point cloud exists in a three-dimensional space divided by a voxel grid of a certain scale. It is also possible to acquire the shape as a point cloud by using a laser measuring device to find the distance to the object from the relationship between the time it takes for the emitted laser to return and the speed of the laser. Thereafter, the point cloud is converted into voxels using the same method as above, and the voxel data can be obtained. There are many other methods for estimating the voxel shape, but they are not the main focus of the present invention, so they will be omitted.

The surface determination unit 405 determines surfaces for the voxel data generated by the voxel data generation unit 404 according to the voxel arrangement. There are various methods for determining surfaces from voxel data, but in this embodiment, the Marching Cubes method (hereinafter referred to as the "MC method") is used. The surface determination unit 405 also saves information about the determined surfaces as surface information. This surface information is referenced in the processing of the representative vertex calculation unit 406 and the representative vertex connection unit 408.

The representative vertex calculation unit 406 uses the above-mentioned face information to calculate the most likely vertex (representative vertex) in the simplified polygon model. The information on the calculated representative vertex is input to the representative vertex connection unit 407.

The representative vertex connection unit 407 connects the representative vertices calculated by the representative vertex calculation unit 406 with reference to the face information, to generate a polygon model consisting of fewer polygons (i.e., with a simplified shape).

<Polygon model generation flow>
Next, a series of processing steps up to generating a polygon model with a simplified shape in image processing device 100 will be described in detail with reference to the flowchart shown in Fig. 5. This series of processing steps is realized by CPU 101 reading a predetermined program from HDD 103, developing it in main memory 102, and executing it. In the following description, the symbol "S" means a step.

First, in S501, the captured image acquisition unit 401 acquires data of images (multiple viewpoint images) captured by the camera group 110 via the LAN 108, the external I/F unit 106, and the bus 107. The acquired data of the multiple viewpoint images is stored in the main memory 102. Then, in S502, the camera parameters of each camera 201 constituting the camera group 110 that captured the above-mentioned multiple viewpoint images are read from the HDD 103. Note that the camera calibration unit 402 may perform the above-mentioned calibration at this timing to acquire the camera parameters.

Next, in S503, the silhouette image generation unit 403 generates a silhouette image based on the multiple viewpoint images acquired in S501. Then, in S504, the voxel data generation unit 404 uses the silhouette image generated in S503 and the camera parameters acquired in S502 to generate voxel data that represents the three-dimensional shape of the object using a collection of voxels flagged with "1" or "0". The generated voxel data is input to the surface determination unit 405.

In the next step S505, the face determination unit 405 determines faces for the voxel data generated in S504 according to the arrangement of the voxels. A typical method for determining faces is the Marching Cubes (MC) method. Here, the MC method will be described with reference to FIG. 6. In the MC method, a cube consisting of eight adjacent voxels as shown in FIG. 6 is considered as one unit. For example, as shown in FIG. 6, a point defined by the value of "0" or "1" assigned in S504 is considered at the center of each adjacent voxel, and the cube obtained by connecting these points is considered as one unit. In this case, the value of "0" or "1" is assigned to each of the eight vertices of the unit cube, so that there are 256 possible combinations of vertex values. These combinations become indexes that represent various faces in the unit cube. Hereinafter, the unit cube in the MC method will be called an "MC voxel," and the method of determining faces corresponding to the above 256 possible combinations will be called an "MC index." In the MC method, the MC index is derived from a combination of the values "0" or "1" attached to the vertices of eight adjacent voxels, so the number of MC voxels for the input voxel data is reduced by one on each of the x-axis, y-axis, and z-axis. The input voxel data may have a value of "1" at the endpoints of the x-axis, y-axis, and z-axis, in which case the endpoint processing may fail and the shape may collapse. To prevent such collapse of the shape, the MC method is usually applied after performing a padding process in which xp, yp, and zp voxels with a value of "0" are added to each of the x, y, and z axes. The rectangular boundary that surrounds the three-dimensional space in which such voxels are tiled is called a bounding box.

In the normal MC method, the vertex positions constituting the triangular faces are managed using the edge index (EI) of the MC voxel. Here, the edge index refers to an index number from 1 to 12 assigned between the vertices of the MC voxel and the corresponding coordinates. In this embodiment, this edge index and normal information corresponding to the generated face are associated with the MC index and stored as the above-mentioned face information in a table format as shown in FIG. 7. Note that the number of faces generated and information on the vertex positions constituting the faces may also be stored as face information. Hereinafter, a table like that in FIG. 7 will be referred to as an "MC table." In addition, the MC table also stores information indicating the connection relationship with adjacent MC voxels as face information. Details of the MC table will be described later. The MC table including such face information is held in the HDD 103.

In S506, the representative vertex calculation unit 406 refers to the above-mentioned MC table and calculates the position of the representative vertex in voxel units of the specified macro scale. The macro scale is variable, and the degree of simplification can be adjusted by changing the macro scale. In this embodiment, a likely vertex (representative vertex) is calculated in units of MC voxels having a scale S _vm that is an integer multiple of the scale S _vi of the input MC voxel. Hereinafter, an MC voxel having a scale that is an integer multiple of the input MC voxel will be referred to as a "macro MC voxel." Note that the macro scale to be actually applied may be determined in advance in consideration of the type and shape of the target object, or the user may specify a desired scale each time via a UI or the like. The representative vertex calculation unit 406 performs such calculation of the representative vertex for all macro MC voxels. Note that in this calculation process, the macro MC voxels may be processed one by one in sequence, or multiple macro MC voxels may be processed in parallel. Details of the representative vertex calculation process will be described later. The calculation result is output to the representative vertex connection unit 407.

In S507, the representative vertex connection unit 407 determines the topology for the representative vertices calculated in S506, connects the representative vertices to each other, and generates a polygon model with a simplified shape. The representative vertex connection unit 407 determines the topology for all macro MC voxels. The topology determination process will be described in detail later.

The above is the polygon model generation flow according to this embodiment.

<Details of MC table>
Next, the MC table will be described in detail. Fig. 8 is a diagram for explaining the relationship between MC voxels and edge indexes, and Fig. 9 is a diagram for explaining the connection relationship between MC voxels and adjacent MC voxels. Now, for the MC index number 1, it is defined that only vertex 1 has a value of "1" and vertices other than vertex 1 have a value of "0". In this case, as shown in Fig. 8, faces are applied to edge indexes _EI1 , _EI2 , and _EI3 . Such correspondence between MC indexes and edge indexes is stored in the MC table. Normal information corresponding to the faces specified by the edge indexes is also stored in the MC table.

Normal information can be obtained as follows. First of all, the intercept of a three-dimensional normal varies depending on the surface, but its slope is unique to the MC index. In general, if the equation of a plane in three-dimensional space is given as in the following equation (1), the normalized normal vector n is expressed as in the following equation (2).

Therefore, for example, the normal vector (nx _{, ny, nz} ) for the MC index number 1 is expressed by the following formula (3), taking into account the front and back of the face.

The normal vector ( _nx , _ny , _nz ) thus obtained is also stored in the MC table in association with the MC index. Note that the stored normal vector ( _nx , _ny , _nz ) does not necessarily have to be normalized.

Next, consider the connection relationship with adjacent voxels. For example, in the case of the MC index number 1, three edges E ₁₂ (edge connecting EI ₁ and EI ₂ ), E ₂₅ (edge connecting EI ₂ and EI ₅ ), and E ₅₁ (edge connecting EI ₅ and EI ₁ ) are formed in the target MC voxel. Therefore, as shown in FIG. 9, the target MC voxel is connected to three adjacent MC voxels MV1, MV2, and MV3 out of six adjacent MC voxels (MV1 to MV6) existing above, below, left, and right of the target MC voxel. These connection relationships are stored in the MC table in correspondence with the MC index. Note that the connection relationships do not necessarily need to be stored in units of MC voxels, and may be stored in units of input voxels existing at positions shifted by half a voxel from the MC voxel. For example, in the case of MC index number 1, the voxel centered on vertex 1 is connected to three input voxels centered on vertices 2, 4, and 5, respectively (see Figures 8 and 6), so it is sufficient to store the information of these voxels.

As mentioned above, when considering the combinations of "0" and "1" at the eight vertices of a unit cube in the MC method, there are 256 possible face generation patterns. However, there are many cases where the same generation pattern results from rotation or inversion, and these are summarized in the 15 generation patterns shown in Figure 10. In Figure 10, black circles among the eight vertices of the unit cube indicate vertices marked with "1," and white circles indicate vertices marked with "0."

<Details of Representative Vertex Calculation Process>
Next, the process of calculating the representative vertex in S506 described above will be explained in detail for different cases.

<When the macro scale is 1x>
As described above, a macro scale of 1 means that the scale S _vi of the input MC voxel and the scale S _vm of the macro MC voxel are the same. In this case, there are several methods for calculating the representative vertex. First, a method for calculating the average position of the vertices of the surface generated by the input MC voxel will be described. FIG. 11 shows a three-dimensional space in which a plurality of MC voxels are aligned and arranged. Now, the start position of the input MC voxel to be processed is set to MV(0,0,0), and k, l, and m are voxel coordinates representing the number of voxels in each axial direction from the start position. When the MC index of MV(k,l,m) is number 1, the average vertex position C of the surface can be obtained by the following formula (4) using the positions of the edge indexes EI ₁ , EI ₂ , and EI ₅ .

In the above formula (4), EI _x,i,k , EI _y,i,l , and EI _z,i,m+ are as shown in the following formulas (5) to (7), respectively.

In addition, when two or more faces are generated (all generated patterns except for patterns 1 and 2 in FIG. 10), a method for calculating the representative vertex position is Quadrilateral Error Metrics (hereinafter referred to as "QEM") in Non-Patent Document 1. By using QEM, it is possible to approximate the error when multiple vertices are aggregated into one vertex. Here, the equation of a plane in three-dimensional space is the above formula (1), and the QEMs of the two planes are Q1 and Q2. In this case, the error Δv when the vertices included in the two faces are aggregated into vertex v is expressed as the following formula (9) under the conditions of the following formula (8).

Note that in the above formula (9),

where Q1 and Q2 are defined as follows:

Furthermore, the sum of the errors Δv' from the vertices included in the n faces to a certain vertex v' is calculated using the following formula (10).

Note that in the above formula (10),

The vertex for which this error Δv' is smallest is the most likely vertex, i.e., the representative vertex. Therefore, under the conditions shown in the following formula (11), the following formula (12) holds.

Then, assuming that an inverse matrix exists for the matrix multiplied by v' in the above formula (12), calculate v' that satisfies the following formula (13).

Also, when there is no inverse matrix, the average value of the vertices of each face may be v'. In this case, for the coefficients a, b, and c of the equation of the plane in the above formula (13), the coefficients of the normal corresponding to the index of the input MC voxel are referred to from the MC table, and then converted to satisfy the condition of the above formula (8). Also, since the scale of the macro MC voxel and the scale of the input MC voxel are equal, the position of the edge index EI through which the face passes can be easily calculated from the scale S _vi and position (k, l, m) of the input MC voxel. Therefore, the coordinates of a, b, c, and EI may be substituted into the above formula (1) to calculate the constant term d. Of course, d may be calculated directly from the position of the MC voxel using the nature of the parallel movement of the face.

In addition, when multiple faces are generated, the representative vertex to be calculated does not necessarily have to be one. FIG. 12(a) shows the case where the representative vertex is calculated for each of the three faces generated by generation pattern 6 in FIG. 10. For each face, the connection relationship with adjacent MC voxels is preserved, and the connection relationship of the faces within each input MC voxel is known from the MC index. Therefore, the average vertex may be found for each face and calculated as the representative vertex. This method is useful when it is desired to express a partially complex shape. By using this method when aggregating MC voxels with a scale of 1 into one vertex would result in over-aggregation, it is possible to express a partially detailed shape while maintaining the connection with other MC voxels.

<When the macro scale is more than twice the normal size>
Next, consider the case where the scale of the macro MC voxel with respect to the input MC voxel is r times, where r is a positive integer greater than 1 (r≧2).

Once the scale of the macro MC voxel is determined, it is first identified which input MC voxels are included in that macro MC voxel. At this time, the MC index corresponding to the identified input MC voxel is also determined. Then, by referring to the MC table shown in Figure 7 above, the normal coefficients corresponding to these MC indexes are determined, and the equation of the plane to be generated is determined from the position of the input MC voxel. The sum of the errors Δv' from all the faces determined in this way to a certain vertex is expressed by the following equation (14).

In the above formula (14), IMV represents the input voxel and MMV represents the macro MC voxel.

Note that even if the scale of the macro MC voxel is larger than that of the input MC voxel, if multiple faces are generated, the representative vertex generated for the macro MC voxel does not necessarily have to be one.

(Details of the topology determination process)
Next, the topology determination process in S507 described above will be explained in detail for different cases, similar to the representative vertex calculation process.

<When the macro scale is 1x>
The MC table generated in S505 stores information that can identify adjacent MC voxels in a connected relationship. Since the MC method creates a polygon mesh (≒ a collection of faces) without holes, adjacent MC voxels always form faces. Therefore, a representative vertex is always calculated for each face, and this is the connection target. Specifically, first, an MC index corresponding to an input MC voxel is acquired by referring to the MC table. Next, a topology is determined for the acquired MC index using a connection relationship with adjacent MC voxels. A topology (i.e., a new edge) can be determined by connecting the representative vertex of the input MC voxel with the representative vertex of an adjacent MC voxel in a connected relationship with the input MC voxel. A specific example is shown in FIG. 12(b). In FIG. 12(b), it is known from the information of adjacent MC voxels in the MC table that MC voxel 2, which has a face according to the above-mentioned generation pattern 6, is connected to MC voxel 1, which has a face according to generation pattern 9, and some continuous face is generated. A simplified polygon mesh is generated by connecting the representative vertices 1 and 2 calculated from the MC voxels 1 and 2 (see the dashed lines in the figure) and also connecting them to the representative vertices of other adjacent MC voxels that are similarly connected. Note that overlapping topology connections can be prevented by setting rules in advance about the direction in which the vertices are connected (for example, connecting the vertices in the positive directions of x, y, and z).

<When the macro scale is more than twice the normal size>
The basic idea is the same even when the scale of the macro MC voxel relative to the input MC voxel is r times (r>2). In this case, first, it is specified which input MC voxel is included in the macro MC voxel. At this time, the MC index corresponding to the specified input MC voxel is also determined. Then, as described above, the topology is determined using the connection relationship between the corresponding MC index and the adjacent MC voxel. Since the connection relationship between the adjacent MC voxel and the input MC voxel is stored in the MC table, it is sufficient to connect the calculated representative vertices after determining which macro MC voxel the corresponding input MC voxel is included in.

In this embodiment, the MC method is used to calculate likely vertices in a simplified polygon model, but the scope of application of this embodiment is not limited to this. For example, the present invention can also be applied to polygon model generation methods such as the finite element method, geometric fitting, and function fitting. These methods have a predefined function system for generating polygon meshes (e.g., an interpolation function for isolated points), and similar processing is possible by deriving and referencing normals and connection relationships from these predefined function systems.

As described above, according to this embodiment, after determining faces for the voxel data according to the voxel arrangement, the representative vertices are calculated by referencing information about the faces to determine the topology. This makes it possible to reduce the number of polygons in a polygon model quickly and with high accuracy.

[Embodiment 2]
Next, an aspect in which the scale of a macro MC voxel is changed according to the complexity of the shape will be described as embodiment 2. Note that the description of the contents common to embodiment 1, such as the basic system configuration, will be omitted or simplified, and the following description will focus on the difference, that is, the generation flow of a polygon model.

<Polygon model generation flow>
13 is a flowchart showing the flow of a polygon model generation flow according to this embodiment. Each process from S1301 to S1305 corresponds to each process from S501 to S505 in the flow of FIG. 5 of the embodiment, and there is no particular difference, so a description thereof will be omitted.

In S1306, the representative vertex calculation unit 406 sets an initial scale value of the macro MC voxel for the input MC voxel of interest among all the input MC voxels. This initial scale value may be set to a value such as r=8 (i.e., a scale 8 times that of the input MC voxel), taking into account the maximum allowable degree of simplification.

In S1307, the representative vertex calculation unit 406 calculates the shape complexity based on information about the faces generated in the macro MC voxel of the set scale. Here, the dot product value of the normal n of face p included in the macro MC voxel is used as the shape complexity CP. In this case, the larger the dot product value of the normals, the more likely it is that the normals point in the same direction, and the lower the shape complexity CP. The shape complexity CP is expressed by the following equation (15).

In the above formula (15), MMV represents a macro MC voxel. The representative vertex calculation unit 406 first determines an input MC voxel included in the macro MC voxel of the set scale. Next, by referring to the MC table generated in S1305, it obtains an MC index corresponding to the determined input MC voxel, and further obtains the normal coefficient corresponding to the MC index, and calculates the shape complexity CP using the above formula (15).

In S1308, the representative vertex calculation unit 406 determines whether the shape complexity is higher than a predetermined level based on the shape complexity CP calculated in S1307. If the result of this threshold determination process indicates that the shape complexity is high, the process proceeds to S1309.

In S1309, it is determined whether the currently set scale is equal to the scale of the input MC voxel. If the determination shows that they are not equal (i.e., the scale is 2x or more), the process proceeds to S1310. On the other hand, if they are equal (i.e., the scale is 1x), the scale cannot be updated (the scale cannot be made smaller than this), so the process proceeds to S1311. In this case, the scale of the macro MC voxel for the input MC voxel of interest is determined to be equal to the scale.

In S1310, a scale update process is performed to reduce the scale of the macro MC voxel. In this embodiment, the scale is changed to half the currently set scale (for example, if the current scale is 8 times, it is changed to 4 times). After updating the scale, the process returns to S1307, and the calculation process of the shape complexity is performed again for the macro MC voxel of the newly set scale (i.e., half the original scale). On the other hand, if the result of the above-mentioned threshold determination process indicates that the shape complexity is not high, the scale of the macro MC voxel for the input MC voxel of interest is determined to be the currently set scale. After the scale is determined, the process proceeds to S1311.

In S1311, it is determined whether or not macro MC voxel processing has been completed for all input MC voxels. If the above processing has been completed for all input MC voxels, proceed to S1312. On the other hand, if there are unprocessed input MC voxels, return to S1306 to determine the next input MC voxel of interest, and repeat the same processing.

In S1312, the representative vertex calculation unit 406 calculates a representative vertex for each macro MC voxel of the determined scale. Then, in S1313, the representative vertex connection unit 407 performs processing to determine a topology for the representative vertices calculated in S1312 and connect the representative vertices together. Note that the contents of the representative vertex calculation processing and the topology determination processing are as described in S506 and S507 in the flow of FIG. 5 in embodiment 1, and therefore will not be described here.

The above is the polygon generation flow according to this embodiment. Figure 14 shows an example of a polygon model obtained by changing the scale of macro MC voxels according to the complexity of the shape using the method of this embodiment. In the case of this embodiment, faces and vertices can be generated sparsely for areas with low complexity and densely for areas with high complexity, so it can be seen that a more accurate polygon model can be obtained.

<Modification>
In this embodiment, the inner product value of the normals of the generated faces is used as an index for measuring the complexity of the shape, but instead, the number of faces generated may be used. Specifically, it is as follows. First, the maximum number of faces that can be generated per MC voxel is 5. For example, in the case of a macro MC voxel with a scale of 2, the number of input MC voxels contained therein is 8, so the maximum number of faces generated is 8 x 5 = 40. Therefore, a value (ratio) indicating how many faces are actually generated relative to this maximum number of faces is calculated, and this is used as an index of the complexity of the shape. In this case, the threshold value may be set to, for example, a threshold value th = 0.4.

As described above, according to this embodiment, although the processing load increases compared to the method of embodiment 1, it is possible to obtain a polygon model with higher accuracy.

Other Examples
The technology of the present disclosure can also be realized by a process in which a program for realizing one or more functions of the above-described embodiments is supplied to a system or device via a network or a storage medium, and one or more processors in a computer of the system or device read and execute the program. It can also be realized by a circuit (e.g., ASIC) that realizes one or more functions.

100 Image processing device 405 Face determination unit 406 Representative vertex calculation unit 407 Representative vertex connection unit

Claims (12)

A determining means for determining polygons according to a voxel arrangement based on shape data in which a three-dimensional shape of an object is expressed by voxels;
a calculation means for calculating vertices in voxel units of a specific scale from information about the polygon determined by the determination means;
a generating means for generating shape data in which a three-dimensional shape of the object is expressed by polygons based on connecting the vertices calculated by the calculating means;
Equipped with
the calculation means calculates the vertices based on a distance relationship between the one or more faces to be generated and points that can become the vertices when the specific scale is r times (r>1);
13. An image processing device comprising: The image processing device according to claim 1, characterized in that the specific scale is an integer multiple of the scale of the voxels that constitute the shape data represented by the voxels. The image processing device according to claim 2, characterized in that the specific scale is variable. The image processing device according to claim 3, characterized in that the calculation means determines the complexity of the shape based on one or more faces generated within the input voxel of the specific scale, and reduces the scale if the complexity is higher than a predetermined level. The information about the polygon includes information about normals corresponding to the one or more faces to be generated;
5. The image processing apparatus according to claim 4, wherein the calculation means calculates the complexity based on an inner product value of the normals. The information about the polygon includes information about the number of the one or more faces to be generated,
The calculation means calculates the complexity based on the information on the number of faces.
5. The image processing device according to claim 4, A determining means for determining polygons according to a voxel arrangement based on shape data in which a three-dimensional shape of an object is expressed by voxels;
a calculation means for calculating vertices in voxel units of a specific scale from information about the polygon determined by the determination means;
a generating means for generating shape data in which a three-dimensional shape of the object is expressed by polygons based on connecting the vertices calculated by the calculating means;
Equipped with
the specific scale is an integer multiple of the scale of the voxels constituting the shape data expressed by the voxels, and the specific scale is variable;
The calculation means calculates a degree of complexity of a shape based on one or more faces generated within a voxel of the input specific scale, and reduces the scale when the degree of complexity is higher than a predetermined level;
The information about the polygon includes information about the number of the one or more faces to be generated,
The calculation means calculates the complexity based on the information on the number of faces.
The image processing device according to the present invention is characterized in that the calculation means calculates the vertex by obtaining an average position of a plurality of vertices constituting the one or more faces to be generated when the specific scale is 1;
8. The image processing device according to claim 1, The image processing device according to any one of claims 1 to 8, characterized in that the determination means determines the polygon by any one of the following methods: marching cubes method, finite element method, geometric fitting, and function fitting. The image processing device according to any one of claims 1 to 9, characterized in that the generating means refers to information about the polygon and connects the vertices calculated by the calculating means. A determination step of determining polygons according to a voxel arrangement based on shape data in which a three-dimensional shape of an object is expressed by voxels;
a calculation step of calculating vertices in voxel units of a specific scale from information about the polygon determined in the determination step;
a generating step of generating shape data in which a three-dimensional shape of the object is expressed by polygons based on connecting the vertices calculated in the calculating step;
Including,
In the calculation step, when the specific scale is r times (r>1), the vertices are calculated based on a distance relationship between the one or more faces to be generated and points that can become the vertices.
13. An image processing method comprising: A program for causing a computer to function as an image processing device according to any one of claims 1 to 10.

Images