JP7710885B2 - DATA PROCESSING APPARATUS, DATA PROCESSING METHOD, AND PROGRAM - Google Patents

Description

This disclosure relates to a data processing technique for generating a point cloud corresponding to the shape of an object from data indicating the shape of the object.

There are techniques for reducing the number of vertices in a mesh when generating a mesh that corresponds to the surface of an object. Patent Document 1 discloses a technique for reducing the total number of edges so as to reduce the amount of deformation of the mesh when the edges are removed, thereby gradually reducing the number of vertices in the mesh while suppressing deterioration of the mesh's shape. Here, an edge refers to a combination of two common vertices that make up adjacent polygons. In addition, a commonly known technique for simply reducing the number of vertices in a mesh is to generate a low-resolution volume by reducing the resolution of the volume, and then generate a mesh from the generated low-resolution volume.

JP 2003-91742 A

The method disclosed in Patent Document 1 can suppress deterioration of the mesh shape, but has the problem that a mesh with a reduced number of vertices (hereinafter referred to as a "simplified mesh") cannot be generated quickly due to the high processing load when evaluating the deformation amount of the mesh. On the other hand, the method of generating a mesh from a low-resolution volume can generate a simplified mesh quickly compared to the method disclosed in Patent Document 1, but has the problem that the shape of the generated simplified mesh deteriorates. Note that the above-mentioned problem is not limited to the case of generating a simplified mesh from volume data representing the three-dimensional shape of an object, but is also the same when identifying a polygon representing the outline of an object from two-dimensional map data such as a silhouette image representing the two-dimensional shape of the object.

The present disclosure is intended to solve these problems, and makes it possible to quickly generate a simplified point cloud that corresponds to the shape of an object and suppresses shape degradation.

A data processing device according to the present disclosure includes an acquisition means for acquiring first information representing a shape of an object using a plurality of first unit areas; a first generation means for generating, based on the first information, second information representing the shape of the object using a plurality of second unit areas larger than the first unit areas; a first identification means for identifying, based on the first information, a plurality of first unit areas corresponding to an outline of the object; a second identification means for identifying, based on the second information, a plurality of boundaries between adjacent second unit areas that correspond to the outline of the object; and a second generation means for generating a point cloud corresponding to the outline of the object based on the first unit areas identified by the first identification means and the boundaries identified by the second identification means, wherein the first identification means generates a point cloud corresponding to the outline of the object based on the first information and the second information. Each of the first unit areas is associated with the second unit area including the position of the first unit area, or the second unit area located closest to the position of the first unit area, and the second generation means generates the point cloud corresponding to the outer shape of the object for each second unit area based on the first unit area associated with the second unit area among the first unit areas identified by the first identification means, and the boundary corresponding to the second unit area identified by the second identification means, and when associating the first unit area with the second unit area located closest to the position of the first unit area, if there are multiple second unit areas located closest to the position of the first unit area, the first identification means associates the first unit area with all of the second unit areas located closest to the position of the first unit area .

According to the present disclosure, it is possible to quickly generate a simplified point cloud that corresponds to the shape of an object and suppresses shape degradation.

1 is a block diagram showing an example of a configuration of a data processing device according to a first embodiment. FIG. 2 is an explanatory diagram showing an example of the configuration of a base volume and a macro volume; 1 is a block diagram showing an example of a hardware configuration of a data processing device according to a first embodiment. 4 is a flowchart showing an example of a processing flow of the data processing device according to the first embodiment. FIG. 5 is an explanatory diagram for explaining the process of the flowchart shown in FIG. 4 . 10 is a flowchart illustrating an example of a processing flow of a generating unit according to the first embodiment. FIG. 4 is an explanatory diagram for explaining processing of a generation unit according to the first embodiment. 10 is a flowchart showing an example of a processing flow of a data processing device according to a second embodiment. FIG. 9 is an explanatory diagram for explaining the process of the flowchart shown in FIG. 8 . 10 is an explanatory diagram showing an example of correspondence between surface base voxels and macro voxels in a base identification unit according to the first embodiment; FIG.

The following describes in detail the embodiments of the present disclosure with reference to the attached drawings. Note that the configurations shown in the following embodiments are merely examples, and the scope of the present disclosure is not limited to these configurations.

[First embodiment]
A data processing device 100 according to the first embodiment will be described with reference to Fig. 1 to Fig. 7. The configuration of the data processing device 100 according to the first embodiment will be described with reference to Fig. 1. Fig. 1 is a block diagram showing an example of the configuration of the data processing device 100 according to the first embodiment. The data processing device 100 includes an acquisition unit 110, a simplification unit 120, a macro identification unit 130, a base identification unit 140, a generation unit 150, and an output unit 160.

In the first embodiment, as an example, a case will be described in which the data processing device 100 acquires volume data representing the three-dimensional shape of an object, and outputs a surface point cloud corresponding to the surface shape of the object. The data processing device 100 may acquire two-dimensional map data representing the two-dimensional shape of an object, and output a point cloud corresponding to the contour shape of the object. A description of the form in which the data processing device 100 acquires two-dimensional map data representing the two-dimensional shape of an object, and outputs a point cloud corresponding to the contour shape of the object will be omitted, as this is a reduction of three dimensions to two dimensions.

In the first embodiment, an object, a volume, a voxel, a point, a point cloud, a polygon, and a mesh are defined as follows. An object is a three-dimensional object. A volume is one of the forms for expressing the three-dimensional shape of an object. Specifically, a volume is a circumscribing rectangle (hereinafter also referred to as a "bounding box") set in a three-dimensional space, its interior is divided into grid-like regions (hereinafter referred to as "grids"), and each grid is assigned a value. A voxel is each grid that constitutes a volume. A voxel holds a voxel value that is a scalar value or a vector value. The voxel value can be binary, multi-value, or continuous. In particular, when the voxel value is binary, in this disclosure, a voxel whose voxel value is 1 is called an ON voxel, and a voxel whose voxel value is 0 is called an OFF voxel.

A point is something that can be represented by a single coordinate in three-dimensional space. A point cloud is one form for expressing the three-dimensional shape of an object. Specifically, a point cloud is a collection of one or more points, and is a form of expression in which the position of each point is expressed by coordinates. A polygon is a polygonal surface defined by three or more points. A mesh is one form for expressing the three-dimensional shape of an object. Specifically, a mesh is a form of expression of a three-dimensional shape with multiple faces that is composed of a collection of multiple polygons. In this disclosure, as an example, a polygon is a triangular polygon having a triangular surface defined by three points, and a mesh is composed of multiple triangular polygons.

The acquisition unit 110 acquires first information representing the shape of an object using a plurality of first unit regions. Specifically, the acquisition unit 110 acquires a volume (hereinafter referred to as a "base volume") representing the three-dimensional shape of an object using a plurality of voxels (hereinafter referred to as "base voxels"). That is, in the first embodiment, the first unit regions are base voxels, and the first information representing the shape of an object is a base volume representing the three-dimensional shape of the object. The acquisition unit 110 outputs the acquired base volume to the simplification unit 120 and the base identification unit 140.

The simplification unit 120 simplifies the first information and generates second information representing the shape of the object using a plurality of second unit regions larger than the first unit regions. Specifically, the simplification unit 120 receives the base volume output by the acquisition unit 110 and simplifies the base volume. The simplification unit 120 simplifies the base volume to generate a volume (hereinafter referred to as a "macro volume") representing the three-dimensional shape of the object using a plurality of voxels (hereinafter referred to as "macro voxels") larger than the base voxels. That is, in the first embodiment, the second unit regions are macro voxels, and the second information representing the shape of the object is a macro volume representing the three-dimensional shape of the object. For example, when the simplification unit 120 simplifies the base volume to generate the macro volume, it simplifies according to a predetermined simplification factor. The simplification factor may be one that is held in advance by the simplification unit 120 or one that is acquired by the acquisition unit 110.

The base voxels and macro voxels will be described with reference to FIG. 2. FIG. 2(a) is an explanatory diagram showing an example of the configuration of the base volume 201 acquired by the acquisition unit 110. The base volume 201 shown in FIG. 2(a) is, as an example, configured of 64 base voxels arranged in four in each of the X-axis direction, Y-axis direction, and Z-axis direction. The outer shape of the base volume 201 including the 64 base voxels is the bounding box of the base volume 201. Each base voxel holds a voxel value indicating whether or not a part or all of the base voxels belong to an object. Some of the base voxels constituting the base volume 201 are ON voxels in which a part or all of the base voxels belong to an object. The remaining part is OFF voxels in which no part of the base voxels belongs to an object, or the entire base voxels do not belong to an object. FIG. 2B is an explanatory diagram showing an example of the configuration of a macro volume 202 obtained by simplifying the base volume 201 by the simplification unit 120. For example, the simplification unit 120 simplifies eight base voxels arranged in pairs in the X-axis direction, Y-axis direction, and Z-axis direction in the base volume 201 into one macro voxel. As a result, the simplification unit 120 generates a macro volume 202 composed of eight macro voxels arranged in pairs in the X-axis direction, Y-axis direction, and Z-axis direction. In this case, the simplification factor in the simplification unit 120 is 2.

The simplification unit 120 also determines for each macrovoxel whether there is an ON voxel among the eight base voxels corresponding to the macrovoxel. For a macrovoxel for which at least one ON voxel is present among the eight base voxels as a result of the determination, the simplification unit 120 sets the voxel value of the macrovoxel to 1 to make it an ON voxel. For a macrovoxel for which there is no ON voxel among the eight base voxels as a result of the determination, the simplification unit 120 sets the voxel value of the macrovoxel to 0 to make it an OFF voxel. The simplification unit 120 may determine whether to make a macrovoxel an ON voxel or an OFF voxel by comparing the number of ON voxels or the ratio of ON voxels among the eight base voxels corresponding to the macrovoxel with a predetermined threshold value. Note that the threshold value may be, for example, one that is stored in advance by the simplification unit 120 or one that is acquired by the acquisition unit 110.

Based on the second information, the macro specification unit 130 specifies a number of boundaries between adjacent second unit regions that correspond to the outer shape of the object. Specifically, based on the macro volume, the macro specification unit 130 specifies a number of boundary surfaces (hereinafter referred to as "surface boundary surfaces") between adjacent macro voxels that correspond to the surface of the object. Note that the boundary surfaces between adjacent macro voxels include the contact surface between the macro voxels and the bounding box, which is the outer shape of the macro volume, in addition to the contact surface between the adjacent macro voxels. Specifically, for example, the macro specification unit 130 specifies the contact surface between the bounding box or the macro voxel of the OFF voxel and the macro voxel of the ON voxel as the surface boundary surface.

The macro specification unit 130 also specifies the position of a point (hereinafter referred to as a "surface voxel boundary") on the surface boundary surface for each of the surface boundary surfaces. Specifically, for example, the macro specification unit 130 specifies a point on the boundary surface that characterizes the surface boundary surface, for example, a predetermined position on the surface boundary surface such as the center point of the surface boundary surface, as the position of the surface voxel boundary. The macro specification unit 130 may specify the position of the surface voxel boundary by the following method. First, the macro specification unit 130 sets a virtual voxel having a vertex that is a predetermined point belonging to each of eight macro voxels in which one of the multiple vertices that define the macro voxel exists at the same position, for each position of the vertices of the macro voxel. Next, the macro specification unit 130 specifies a point group or a surface corresponding to the surface of the object inside each virtual voxel based on each voxel value of the above-mentioned eight macro voxels. Furthermore, the macro specification unit 130 specifies the position of the surface voxel boundary based on a point group or a surface inside the specified virtual voxel. The method for identifying a point group or a surface corresponding to the surface of an object inside a virtual voxel is similar to, for example, part of the processing in the well-known Marching cubes method (hereinafter referred to as the "MC method"), and therefore will not be described here.

2B shows, as an example, two adjacent macrovoxels 203 and 204 extracted from the macro volume 202. The combination of the macrovoxels 203 and 204 includes 11 boundary surfaces and points (hereinafter referred to as "voxel boundaries") corresponding to each boundary surface. For example, the macro specification unit 130 assigns a different index (hereinafter referred to as "boundary index") to each voxel boundary in order to identify the voxel boundary corresponding to each boundary surface. The macro specification unit 130 also generates information (hereinafter referred to as "surface information") that associates the boundary index with information indicating whether the boundary surface corresponding to each boundary index is a surface boundary surface or information indicating the position of the surface voxel boundary.

The base identification unit 140 identifies a plurality of first unit regions corresponding to the outer shape of the object based on the first information. Specifically, the base identification unit 140 identifies a plurality of base voxels (hereinafter referred to as "surface base voxels") corresponding to the surface of the object based on the base volume. Specifically, for example, the base identification unit 140 identifies the base voxel of an ON voxel adjacent to the base voxel of an OFF voxel as the surface base voxel.

The base identification unit 140 also identifies a point (hereinafter referred to as a "base boundary point") belonging to the surface base voxel for each surface base voxel. Specifically, for example, the base identification unit 140 identifies a predetermined position inside the surface base voxel, such as the center point of the surface base voxel, as the position of the base boundary point. The base identification unit 140 may also identify a predetermined position on the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel as the position of the base boundary point. The base identification unit 140 may also identify the position of the base boundary point by the following method. First, the base identification unit 140 sets a virtual voxel for each vertex position of the base voxel, the vertex of which is a predetermined point belonging to each of the eight base voxels in which one of the multiple vertices defining the base voxel exists at the same position. Next, the base identification unit 140 identifies a point group or a surface corresponding to the surface of the object inside each virtual voxel based on each voxel value of the above-mentioned eight base voxels. Furthermore, the base identification unit 140 identifies the position of the base boundary point based on the point group or surface inside the identified virtual voxel. The method of identifying the point group or surface corresponding to the surface of the object inside the virtual voxel is similar to, for example, a part of the processing of the Marching cubes method (hereinafter referred to as the "MC method"), which is a well-known method, so a description will be omitted. In the following, in the first embodiment, the base identification unit 140 will be described as identifying the position of the center point of the surface base voxel as the position of the base boundary point. Note that the method in which the base identification unit 140 identifies a predetermined position on the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel as the position of the base boundary point will be described in the second embodiment.

Furthermore, for each surface boundary surface, the base identification unit 140 identifies a macrovoxel (hereinafter referred to as a "surface macrovoxel") that exists on the object side of two macrovoxels separated by the surface boundary surface, and associates the surface boundary surface with the surface macrovoxel. Next, for each surface macrovoxel, the base identification unit 140 calculates a feature value indicating the distribution at the positions of all base boundary points corresponding to one or more surface base voxels among the multiple base voxels corresponding to the surface macrovoxel. Hereinafter, the feature value indicating the distribution of the positions of the base boundary points calculated by the base identification unit 140 will be referred to as a base feature value. Here, the base feature value is a statistical value at the positions of all base boundary points corresponding to one or more surface base voxels among the multiple base voxels corresponding to the surface macrovoxel. In addition, the statistical value at the positions of all base boundary points is at least one of the maximum value, minimum value, mean, variance, standard deviation, median, mode, kurtosis, skewness, etc. at the positions of all base boundary points.

The size of the macrovoxel may be an integer multiple of the size of the base voxel, or a real multiple that is not an integer multiple (hereinafter referred to as a "non-integer multiple"). When the size of the macrovoxel is an integer multiple of the size of the base voxel, each of the positions of all of the base voxels will be included in one of the macrovoxels. Therefore, in this case, the base identification unit 140 associates the surface base voxel with a macrovoxel that includes the position of the surface base voxel. On the other hand, when the size of the macrovoxel is a non-integer multiple of the size of the base voxel, there may be a base voxel whose position is not included in the macrovoxel. In this case, the base identification unit 140 associates the surface base voxel with the macrovoxel as follows.

For example, when the position of the surface base voxel is included in a certain macrovoxel, the base identification unit 140 associates the surface base voxel with the macrovoxel to which the position of the surface base voxel is closest. When the position of the surface base voxel is not included in any macrovoxel, the base identification unit 140 associates the surface base voxel with the macrovoxel to which the position of the surface base voxel is closest. In this case, when there are multiple macrovoxels to which the position of the surface base voxel is closest, for example, the base identification unit 140 associates the surface base voxel with all of the macrovoxels that are closest. In such a case, the base identification unit 140 may associate the surface base voxel with the macrovoxel with which the number of surface base voxels associated is the smallest among the multiple macrovoxels to which the position of the surface base voxel is closest. The association between the surface base voxel and the macrovoxel in the base identification unit 140 may be performed according to a predetermined association condition. Fig. 10(a) is an explanatory diagram showing an example of the correspondence between a surface base voxel and a macro voxel when the size of the macro voxel is an integer multiple (2 times) of the size of the base voxel. Fig. 10(b) is an explanatory diagram showing an example of the correspondence between a surface base voxel and a macro voxel when the size of the macro voxel is a non-integer multiple (1.5 times) of the size of the base voxel.

The generating unit 150 generates a simplified point group corresponding to the outer shape of the object based on the first unit area identified by the base identifying unit 140 and the boundary identified by the macro identifying unit 130. Specifically, the generating unit 150 generates a simplified point group (hereinafter referred to as a "surface point group") corresponding to the surface of the object based on the surface base voxels identified by the base identifying unit 140 and the surface boundary surface identified by the macro identifying unit 130. For example, the generating unit 150 first associates each of the surface boundary surfaces identified by the macro identifying unit 130 with a macro voxel (hereinafter referred to as a "surface macro voxel") that exists on the object side of two macro voxels separated by the surface boundary surface. Next, the generating unit 150 generates a simplified surface point group by calculating the position of a point corresponding to the surface of the object for each surface macro voxel.

Specifically, the generating unit 150 generates a simplified surface point group based on the positions of the base boundary points identified by the base identifying unit 140 and the positions of the surface voxel boundaries identified by the macro identifying unit 130. For example, the generating unit 150 generates a simplified surface point group by performing the following process. First, the generating unit 150 identifies a macro voxel (surface macro voxel) that exists on the object side of two macro voxels separated by a surface boundary surface for each surface boundary surface, and associates the surface boundary surface with the surface macro voxel. Next, the generating unit 150 calculates, for each surface macro voxel, a feature amount (hereinafter referred to as a "voxel boundary feature amount") that indicates a distribution at the positions of all surface voxel boundaries corresponding to one or more surface boundary surfaces associated with the surface macro voxel based on the surface information. Here, the voxel boundary feature amount is a statistical value at the positions of all surface voxel boundaries corresponding to one or more surface boundary surfaces associated with the surface macro voxel. Furthermore, the statistical value at the positions of all surface voxel boundaries is at least one of the maximum value, minimum value, average, variance, standard deviation, median, mode, kurtosis, skewness, etc. at the positions of all surface voxel boundaries. Furthermore, the generating unit 150 generates a simplified surface point group by calculating, for each surface macrovoxel, the position of a point corresponding to the surface of the object based on the base feature and voxel boundary feature corresponding to the surface macrovoxel.

The output unit 160 outputs information indicating the simplified surface point group generated by the generation unit 150. In the above explanation, the voxel boundary feature amount has been described as being calculated by the macro identification unit 130, but it may be calculated by the generation unit 150. Similarly, in the above explanation, the base feature amount has been described as being calculated by the base identification unit 140, but it may be calculated by the generation unit 150.

The processing of each unit of the data processing device 100 is performed by hardware such as an ASIC (Application Specific Integrated Circuit) built into the data processing device 100. The processing of each unit of the data processing device 100 may be performed by hardware such as an FPGA (Field Programmable Gate Array) built into the data processing device 100. The processing may also be performed by software using a CPU (Central Processor Unit) or a GPU (Graphic Processor Unit) and memory.

With reference to FIG. 3, the hardware configuration of the data processing device 100 when each unit of the data processing device 100 operates as software will be described. FIG. 3 is a block diagram showing an example of the hardware configuration of the data processing device 100 according to the first embodiment. The data processing device 100 is configured by a computer, which has a CPU 311, a ROM 312, a RAM 313, an auxiliary storage device 314, a display unit 315, an operation unit 316, a communication unit 317, and a bus 318, as shown as an example in FIG. 3.

The CPU 311 controls the computer using programs or data stored in the ROM 312 or the RAM 313, thereby causing the computer to function as each unit of the data processing device 100 shown in FIG. 1. The data processing device 100 may have one or more dedicated hardware units different from the CPU 311, and at least a part of the processing by the CPU 311 may be executed by the dedicated hardware units. Examples of the dedicated hardware units include an ASIC, an FPGA, and a DSP (digital signal processor). The ROM 312 stores programs that do not require modification. The RAM 313 temporarily stores programs or data supplied from the auxiliary storage device 314, or data supplied from the outside via the communication unit 317. The auxiliary storage device 314 is composed of, for example, a hard disk drive, and stores various data such as image data or audio data.

The display unit 315 is configured, for example, by a liquid crystal display or LEDs, and displays a GUI (Graphical User Interface) or the like for the user to operate or view the data processing device 100. The operation unit 316 is configured, for example, by a keyboard, mouse, or touch panel, and inputs various instructions to the CPU 311 in response to operations by the user. The CPU 311 also operates as a display control unit that controls the display unit 315, and as an operation control unit that controls the operation unit 316.

The communication unit 317 is used for communication with devices external to the data processing device 100. For example, when the data processing device 100 is connected to an external device by wire, a communication cable is connected to the communication unit 317. When the data processing device 100 has a function of wireless communication with an external device, the communication unit 317 is equipped with an antenna. The bus 318 connects each unit of the data processing device 100 to transmit information. In the first embodiment, the display unit 315 and the operation unit 316 are described as being present inside the data processing device 100, but at least one of the display unit 315 and the operation unit 316 may be present as a separate device outside the data processing device 100.

The operation of the data processing device 100 will be described in detail with reference to Figures 4 and 5. Figure 4 is a flowchart showing an example of a processing flow of the data processing device 100 according to the first embodiment. Figure 5 is an explanatory diagram for explaining the processing of the flowchart shown in Figure 4.

First, in S401, the acquisition unit 110 acquires a base volume. The base volume 501 shown in FIG. 5 shows, as an example, a cross section of the base volume acquired by the acquisition unit 110 cut along a plane perpendicular to the X-axis direction, the Y-axis direction, or the Z-axis direction. Next, in S402, the simplification unit 120 simplifies the base volume acquired by the acquisition unit 110 to generate a macro volume. The macro volume 502 shown in FIG. 5 is the base volume 501 simplified by the acquisition unit 110. Note that, when the simplification magnification factor n (n is a positive real number) is set, the voxel resolution of the macro volume 502 is 1/n of the voxel resolution of the base volume 501. Here, by limiting the simplification magnification factor n to a positive integer, the macro voxels can be arranged so that the vertices of the macro voxels in the macro volume 502 overlap the vertices of the base voxels in the base volume 501. As a result, by limiting the simplification factor n to a positive integer, it is easy to associate macrovoxels with base voxels. Note that the simplification factor in Figure 5 is 2.

Next, in S411, the macro specification unit 130 specifies all boundary surfaces in the macro volume generated by the simplification unit 120, and secures in the RAM 313 an area of the boundary surface array corresponding to the number of specified boundary surfaces. Here, the boundary surface array is, for example, an array that associates a boundary index capable of identifying each boundary surface, a surface flag that indicates by a binary value whether or not the boundary surface corresponds to the surface of the object, and information indicating the position of the voxel boundary that corresponds to the boundary surface. When securing the area of the boundary surface array in the RAM 313, the macro specification unit 130 initializes, for example, the values of all surface flags to 0, which indicates that the boundary surface does not correspond to the surface of the object. The macro volume 503 shown in FIG. 5 shows the boundary surface array in a state in which the surface flag is initialized to 0.

Next, in S412, the macro specification unit 130 specifies a plurality of surface boundary surfaces. For example, the macro specification unit 130 changes the value of the surface flag corresponding to each of the specified surface boundary surfaces to 1. The macro volume 504 shown in FIG. 5 shows the boundary surface array in a state in which the value of the surface flag corresponding to each of the surface boundary surfaces has been changed to 1. Next, in S413, the macro specification unit 130 specifies the position of the surface voxel boundary corresponding to each of the surface boundary surfaces. For example, the macro specification unit 130 writes information indicating the position of the specified surface voxel boundary to the corresponding surface boundary surface, that is, to the boundary index corresponding to the surface boundary surface, in the corresponding location of the boundary surface array. After writing information indicating the position of the corresponding surface voxel boundary for all surface boundary surfaces to the boundary surface array, the macro specification unit 130 outputs the boundary surface array to the generation unit 150 as surface information. In addition, by creating a boundary surface array before the macro specification unit 130 performs the process of specifying the surface boundary surface, the macro specification unit 130 can perform the process of determining whether each boundary surface corresponds to the surface of the object in parallel for multiple boundary surfaces.

Next, in S421, the base identification unit 140 identifies a plurality of surface base voxels. Next, in S422, the base identification unit 140 identifies the positions of the base boundary points corresponding to each of the surface base voxels. In the base volume 505 shown in FIG. 5, a plurality of surface base voxels identified by the base identification unit 140 and base boundary points corresponding to each surface base voxel are shown. Note that the base volume 505 shown in FIG. 5 shows, as an example, a case in which the base boundary points are set at the center of the base voxel. Next, in S423, the base identification unit 140 calculates the base feature amount. Next, in S431, the generation unit 150 generates a simplified surface point group. Next, in S432, the output unit 160 outputs information indicating the simplified surface point group generated by the generation unit 150. After S432, the data processing device 100 ends the processing of the flowchart shown in FIG. 4.

The operation of the generation unit 150 will be described in detail with reference to Figs. 6 and 7. Fig. 6 is a flowchart showing an example of the processing flow of the generation unit 150 according to the first embodiment. Specifically, Fig. 6 is a flowchart showing an example of the internal processing flow of S431 shown in Fig. 4. Fig. 7 is an explanatory diagram for explaining the processing of the generation unit 150 according to the first embodiment.

First, in S601, the generating unit 150 associates the surface boundary surface with the surface macrovoxel. In the macro volume 701 shown in FIG. 7, the surface macrovoxel to which the surface boundary surface is associated is indicated by an arrow. Next, in S602, the generating unit 150 calculates a voxel boundary feature for each surface macrovoxel. Next, in S603, the generating unit 150 calculates vertex coordinates in which the position of the surface voxel boundary is corrected for each surface voxel boundary based on the voxel boundary feature and the base feature. Specifically, for example, the generating unit 150 calculates vertex coordinates in which the position of the surface voxel boundary is corrected for each surface voxel boundary using the following formula (1). More specifically, for example, the generating unit 150 corrects the position of the surface voxel boundary for each surface voxel boundary and for each axis of the X-axis, Y-axis, and Z-axis, and calculates vertex coordinates.
p _i ′=(p _i -μ _p )×(σ _r /σ _p )+μ _r ... Equation (1)

Here, μ _r is the average value at the positions of all base boundary points corresponding to one or more surface base voxels corresponding to a certain surface macrovoxel. Furthermore, σ _r is the standard deviation at the positions of all base boundary points corresponding to one or more surface base voxels corresponding to the surface macrovoxel. Furthermore, p _i is the position of the surface voxel boundary corresponding to the surface macrovoxel and corresponding to the boundary index i. Furthermore, μ _p is the average value of the positions of one or more surface voxel boundaries corresponding to the surface macrovoxel. Furthermore, σ _p is the standard deviation of the positions of one or more surface voxel boundaries corresponding to the surface macrovoxel. Furthermore, p _i ' is the vertex coordinate obtained by correcting the position of the surface voxel boundary corresponding to the boundary index i. In the base volume 702 shown in FIG. 7, the correspondence between the position of the surface voxel boundary before correction and the point group obtained by coordinate correction of the position of the surface voxel boundary is indicated by arrows.

Next, in S604, the generating unit 150 generates a surface point group in which the calculated vertex coordinates are arranged in a list. After S604, the generating unit 150 ends the processing of the flowchart shown in FIG. 6. Note that the formula (1) used by the generating unit 150 when calculating the vertex coordinates with the position of the surface voxel boundary corrected is merely an example. The generating unit 150 is not limited to using the formula (1) as long as it calculates the vertex coordinates with the position of the surface voxel boundary corrected for each surface voxel boundary based on the voxel boundary feature and the base feature. Note that, as described above, the voxel boundary feature may be at least one statistical value of the maximum value, minimum value, mean, variance, standard deviation, median, mode, kurtosis, skewness, etc. at the positions of all surface voxel boundaries associated with a certain surface macrovoxel. In addition, the base feature may be at least one statistical value of the maximum value, minimum value, mean, variance, standard deviation, median, mode, kurtosis, skewness, etc. at the positions of all base boundary points corresponding to one or more surface base voxels corresponding to the surface macrovoxel.

With the above configuration, the data processing device 100 can obtain a simplified surface point group indicated by black circles in the base volume 506 shown in FIG. 5. The number of vertices in the simplified surface point group indicated in the base volume 506 is less than the number of base boundary points indicated in the base volume 505. On the other hand, the simplified surface point group indicated in the base volume 506 is equal to or approximately equal to the surface point group obtained based on the base boundary points indicated in the base volume 505. Therefore, according to the data processing device 100, a simplified surface point group that corresponds to the surface shape of an object and suppresses shape deterioration can be generated at high speed. Here, as described above, the data processing device 100 can also process two-dimensional map data that represents the two-dimensional shape of an object. Therefore, it goes without saying that the data processing device 100 can generate a simplified point group that corresponds to the shape of an object and suppresses shape deterioration at high speed.

In the first embodiment, the data processing device 100 processes volume data composed of voxels with binary voxel values, but may process volume data composed of voxels with multi-value or continuous voxel values. When the voxel values of the base volume are multi-value or continuous, for example, the base identification unit 140 identifies the surface base voxel or identifies the position of the base boundary point by comparing the voxel value with a predetermined threshold. The threshold may be one previously held by the base identification unit 140 or one acquired by the acquisition unit 110 from the auxiliary storage device 314 or the like. In this case, for example, when simplifying the base volume, the simplification unit 120 determines the voxel value of the macrovoxel by comparing each voxel value of the multiple base volumes corresponding to the macrovoxel with a predetermined threshold. The simplification unit 120 may determine the voxel value of the macrovoxel by comparing the sum or average value of each voxel value of multiple base volumes corresponding to the macrovoxel with a predetermined threshold value.

In addition, when the voxel values of the macro volume are multi-valued or continuous, for example, the macro identification unit 130 identifies the surface boundary surface or the position of the surface voxel boundary by comparing the voxel values with a predetermined threshold value. Note that a macro volume with multi-valued or continuous voxel values is generated by, for example, the simplification unit 120 setting the average value of each voxel value of multiple base volumes corresponding to the macro voxel as the voxel value of the macro voxel.

[Second embodiment]
A data processing device 100 according to a second embodiment (hereinafter referred to as "data processing device 100a") will be described with reference to FIGS.

The data processing device 100 according to the first embodiment outputs information indicating a simplified surface point group corresponding to the surface of an object from a volume that represents the shape of the object using multiple voxels. In contrast, the data processing device 100a outputs a simplified mesh (hereinafter referred to as a "simplified mesh") corresponding to the surface of the object from the volume, or information that can generate the simplified mesh.

The data processing device 100a may acquire two-dimensional map data representing the two-dimensional shape of an object, and output information indicating a polygon corresponding to the contour shape of the object. The form in which the data processing device 100a acquires two-dimensional map data representing the two-dimensional shape of an object, and outputs information indicating a polygon corresponding to the contour shape of the object, is omitted here because it is a reduction of three dimensions to two dimensions. Note that the definitions of object, volume, voxel, point, point cloud, polygon, and mesh in the second embodiment are the same as those in the second embodiment, and therefore are omitted here.

The data processing device 100a, like the data processing device 100 according to the first embodiment, includes an acquisition unit 110, a simplification unit 120, a macro identification unit 130, a base identification unit 140, a generation unit 150, and an output unit 160, as shown as examples in FIG. 1. Note that the acquisition unit 110 and the simplification unit 120 according to the second embodiment are similar to the acquisition unit 110 and the simplification unit 120 according to the first embodiment, and therefore a description thereof will be omitted.

The macro specification unit 130 according to the second embodiment (hereinafter referred to as the "macro specification unit 130a"), like the macro specification unit 130 according to the first embodiment, specifies a plurality of surface boundary surfaces and specifies the positions of the surface voxel boundaries corresponding to each of the surface boundary surfaces. In addition to specifying the positions of the surface boundary surfaces and the surface voxel boundaries, the macro specification unit 130a also specifies the connection relationships between the surface voxel boundaries. Specifically, for example, the macro specification unit 130a specifies all the connection relationships between the surface voxel boundaries by specifying a plurality of polygonal surfaces having each of the specified plurality of surface voxel boundaries as a vertex. The polygonal surfaces are, for example, polygons. The process of specifying the polygonal surfaces having the surface voxel boundaries as vertices can be realized, for example, by a process similar to a part of the process of the MC method that can specify a point group or a surface corresponding to the surface of an object inside a virtual voxel. Note that the process for identifying polygonal surfaces with surface voxel boundaries as vertices is not limited to processes similar to some of the processes in the MC method, as long as it is possible to identify polygonal surfaces with surface voxel boundaries as vertices.

The macro specification unit 130a generates connection information indicating the specified connection relationships and outputs it to the generation unit 150 or the output unit 160. The connection information is, for example, a list of combinations of boundary indexes that correspond to the surface boundary surfaces to which the multiple surface voxel boundaries that are the vertices of each polygonal surface specified by the macro specification unit 130a belong. When the polygonal surface specified by the macro specification unit 130a is a triangular surface, the connection information is a triangle list that corresponds to the boundary indexes corresponding to the surface boundary surfaces to which the three surface voxel boundaries belong.

The base identification unit 140 according to the second embodiment (hereinafter referred to as the "base identification unit 140a") identifies multiple surface base voxels in the same manner as the base identification unit 140 according to the first embodiment. Also, the base identification unit 140a identifies the position of the base boundary point corresponding to each surface base voxel in the same manner as the base identification unit 140 according to the first embodiment. Furthermore, the base identification unit 140a calculates the base feature amount for each surface macrovoxel in the same manner as the base identification unit 140 according to the first embodiment. However, the base identification unit 140a identifies a predetermined position on the contact surface, such as the center point of the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel, as the position of the base boundary point. Note that the contact surface includes the contact surface between the surface base voxel and the bounding box in addition to the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel.

The base identification unit 140a may identify the position of the base boundary point on the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel by the following method. First, the base identification unit 140 sets a virtual voxel whose vertex is a predetermined point belonging to each of the eight base voxels in which one of the multiple vertices defining the base voxel exists at the same position for each vertex position of the base voxel. Next, the base identification unit 140 identifies a point group or a surface corresponding to the surface of the object inside each virtual voxel based on each voxel value of the above-mentioned eight base voxels. Furthermore, the base identification unit 140 identifies the position of the base boundary point on the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel based on the point group or surface inside the identified virtual voxel. In the following description, the base identification unit 140a is assumed to identify the center point of the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel as the position of the base boundary point.

The generating unit 150 according to the second embodiment (hereinafter, referred to as the "generating unit 150a") generates a simplified surface point group in the same manner as the generating unit 150 according to the first embodiment. In addition to generating a simplified surface point group, the generating unit 150a may generate a simplified mesh corresponding to the surface of the object. Specifically, for example, the generating unit 150a generates a simplified mesh corresponding to the surface of the object based on the connection information generated by the macro specifying unit 130a and the simplified surface point group generated by the generating unit 150a. More specifically, for example, the generating unit 150a first identifies a combination of surface voxel boundaries by referring to the combination of boundary indexes indicated by the connection information. Next, the generating unit 150a generates a simplified mesh corresponding to the surface of the object by generating a polygon composed of the combination of surface voxel boundaries for each combination of boundary indexes indicated by the connection information based on the coordinates of the surface voxel boundaries indicated by the surface point group.

The output unit 160 (hereinafter, referred to as "output unit 160a") according to the second embodiment outputs information indicating the simplified mesh generated by the generation unit 150a. For example, the information indicating the simplified mesh output by the output unit 160a is an image signal indicating the simplified mesh, and the output unit 160a outputs the image signal to the display unit 315 to display it. The output unit 160a may output information indicating the simplified surface point group generated by the generation unit 150a and the connection information generated by the macro specification unit 130a. In this case, the user can generate the simplified mesh later using the data processing device 100a or another device capable of generating a mesh based on the information indicating the simplified surface point group and the connection information. In the following description, the generation unit 150a generates the simplified mesh, and the output unit 160a outputs information indicating the simplified mesh.

The operation of the data processing device 100a will be described in detail with reference to Figures 8 and 9. Figure 8 is a flowchart showing an example of a processing flow of the data processing device 100 (data processing device 100a) according to the second embodiment. Figure 9 is an explanatory diagram for explaining the processing of the flowchart shown in Figure 8. Note that in Figures 8 and 9, the same reference numerals are used for configurations or processing similar to those in Figures 4 and 5, and explanations thereof will be omitted.

First, the data processing device 100a executes the processes from S401 to S413. After S413, in S814, the macro specification unit 130 specifies polygonal surfaces having surface voxel boundaries as vertices and generates connection information. The macro volume 904 shown in FIG. 9 shows a boundary surface array similar to the boundary surface array shown in the macro volume 504 shown in FIG. 5. In addition, in the macro volume 504, the connection relationships between surface voxel boundaries are shown by solid lines connecting the boundary surface arrays.

After S814, the data processing device 100a executes the process of S421. After S421, in S822, the base identification unit 140a identifies the position of the base boundary point on the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel for each surface base voxel. The base volume 905 shown in FIG. 9 shows a plurality of surface base voxels identified by the base identification unit 140a and the base boundary points corresponding to each surface base voxel. The base boundary point shown in the base volume 505 shown in FIG. 5 was located at the center of the surface base voxel. In contrast, the base boundary point shown in the base volume 905 shown in FIG. 9 is located on the contact surface between the surface base voxel and the base voxel of the OFF voxel adjacent to the surface base voxel.

After S822, the data processing device 100a sequentially executes the processes of S423 and S431. In addition, in the process of S431, the generation unit 150a generates a simplified surface point group using, for example, the above-mentioned formula (1). After S431, in S832, the generation unit 150a generates a simplified mesh. In the base volume 906 shown in FIG. 9, the simplified surface point group generated by the generation unit 150a is indicated by black circles. In addition, in the base volume 906, the generated simplified mesh is indicated by solid lines connecting the black circles. After S832, in S833, the output unit 160a outputs information indicating the simplified mesh generated by the generation unit 150a. After S833, the data processing device 100a ends the process of the flowchart shown in FIG. 8.

With the above configuration, the data processing device 100a can obtain a simplified surface point group indicated by black circles in the base volume 906 shown in FIG. 9. The number of vertices in the simplified surface point group indicated in the base volume 906 is less than the number of base boundary points indicated in the base volume 905. On the other hand, the simplified mesh indicated in the base volume 906 is equivalent or approximately equivalent to the mesh obtained based on the base boundary points indicated in the base volume 505. Therefore, according to the data processing device 100a, a simplified surface point group that is a surface point group corresponding to the surface shape of an object and has suppressed shape deterioration can be generated at high speed. Furthermore, according to the data processing device 100a, a simplified mesh that has suppressed shape deterioration can be generated at high speed from a volume. Here, as described above, the data processing device 100a can also process two-dimensional map data that represents the two-dimensional shape of an object. Therefore, it goes without saying that the data processing device 100a can generate a simplified point group that is a point group corresponding to the shape of an object and has suppressed shape deterioration at high speed.

[Other embodiments]
The present disclosure can also be realized by a process in which a program for implementing one or more of the 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. Also, the present disclosure can be realized by a circuit (e.g., ASIC) for implementing one or more of the functions.

Within the scope of this disclosure, it is possible to freely combine the embodiments, modify any of the components of each embodiment, or omit any of the components of each embodiment.

100 Data processing device, 110 Acquisition unit, 120 Simplification unit, 130 Macro identification unit, 140 Base identification unit, 150 Generation unit, 160 Output unit.

Claims (21)

an acquisition means for acquiring first information representing a shape of an object using a plurality of first unit regions;
a first generating means for generating second information representing a shape of the object using a plurality of second unit areas, the second unit areas being larger than the first unit areas, based on the first information;
a first specifying means for specifying a plurality of the first unit areas corresponding to an outer shape of the object based on the first information;
a second identification means for identifying a plurality of boundaries between the second unit areas adjacent to each other, the boundaries corresponding to the outer shape of the object, based on the second information;
a second generating means for generating a point cloud corresponding to the outer shape of the object based on the first unit area identified by the first identifying means and the boundary identified by the second identifying means;
having
the first specifying means, based on the first information and the second information, associates each of the plurality of first unit areas specified by the first specifying means with the second unit area including a position of the first unit area, or with the second unit area located closest to the position of the first unit area;
the second generation means generates, for each of the second unit areas, the point cloud corresponding to the outer shape of the object based on the first unit area associated with the second unit area among the first unit areas identified by the first identification means and the boundary corresponding to the second unit area identified by the second identification means;
When the first unit area corresponds to the second unit area located closest to the position of the first unit area, if there are a plurality of second unit areas located closest to the position of the first unit area, the first specifying means corresponds the first unit area to all of the second unit areas located closest to the position of the first unit area.
A data processing device comprising : The data processing device according to claim 1 , further comprising an output unit that outputs information indicating the point cloud generated by the second generation unit. the acquiring means acquires, as the first information, a first volume that represents a three-dimensional shape of the object using a plurality of first voxels that are a plurality of the first unit regions;
the first generation means generates, as the second information, a second volume representing a three-dimensional shape of the object using a plurality of second voxels that are second unit regions larger in size than the first voxels, based on the first volume;
the first identification means identifies, based on the first volume, a plurality of first voxels corresponding to a surface of the object as a plurality of first unit regions corresponding to the outer shape of the object;
the second identification means identifies, as the boundary, a plurality of boundary surfaces between adjacent second voxels corresponding to a surface of the object, based on the second volume;
2. The data processing device according to claim 1, wherein the second generating means generates, as the point cloud, a surface point cloud corresponding to a surface shape of the object, based on the first voxel identified by the first identifying means and the boundary surface identified by the second identifying means. The data processing apparatus according to claim 3 , wherein the second generating means generates a mesh based on the group of surface points generated by the second generating means. The data processing apparatus according to claim 4 , further comprising: an output unit that outputs information indicating the mesh generated by the second generation unit. The first identification means identifies, for each of the first voxels identified by the first identification means, a position of the first point that belongs to the first voxel and characterizes the first voxel;
The second identification means identifies, for each of the boundary surfaces identified by the second identification means, a position of a second point that belongs to the boundary surface and characterizes the boundary surface;
5. The data processing device according to claim 3, wherein the second generating means generates the surface point group based on a position of the first point in the first voxel identified by the first identifying means and a position of the second point identified by the second identifying means. 5. The data processing device according to claim 3 , wherein the second specifying means specifies a contact surface between the second voxel of an OFF voxel and the second voxel of an ON voxel as the boundary surface corresponding to a surface of the object. The data processing apparatus according to claim 6 , wherein the second specifying means specifies a predetermined position on the boundary surface specified by the second specifying means as the position of the second point. 7. The data processing device according to claim 6, wherein the second identification means identifies the position of the second point by identifying a point group or a surface corresponding to the surface of the object inside a virtual voxel having predetermined points belonging to each of the eight second voxels as vertices, based on each voxel value of the eight second voxels in which one of the multiple vertices defining the second voxel is located at the same position. 5. The data processing apparatus according to claim 3 , wherein the first specifying means specifies the first voxel of ON voxels adjacent to the first voxel of OFF voxels as the first voxel corresponding to a surface of the object . 7. The data processing apparatus according to claim 6 , wherein the first specifying means specifies a predetermined position within the first voxel specified by the first specifying means as the position of the first point. 7. The data processing device according to claim 6, wherein the first identification means identifies, as the position of the first point, a predetermined position on a contact surface between the first voxel identified by the first identification means and the first voxel of an OFF voxel adjacent to the first voxel. 5. The data processing device according to claim 3, wherein the second generation means generates the surface point group by associating each of the boundary surfaces identified by the second identification means with a second voxel that is present on the object side of two second voxels separated by the boundary surface, and calculating the position of a point corresponding to a surface of the object for each associated second voxel. the first identifying means calculates, for each of the second voxels present on the object side among the two second voxels separated by the boundary surface identified by the second identifying means, a first feature amount indicating a distribution of positions of the first points in the first voxels identified by the first identifying means among the plurality of first voxels corresponding to the second voxels;
7. The data processing device according to claim 6, wherein the second generating means calculates a second feature value indicating a distribution of positions of the second points corresponding to the second voxels for each of the second voxels that are present on the object side of the two second voxels separated by the boundary surface identified by the second identifying means, and generates the surface point group based on the first feature value and the second feature value. the first identification means calculates, as the first feature amount, at least one statistical value of a maximum value, a minimum value, a mean, a variance, a standard deviation, a median, a mode, a kurtosis, and a skewness of the position of the first point;
15. The data processing device according to claim 14, wherein the second generating means calculates, as the second feature amount, at least one statistical value of a maximum value, a minimum value, a mean, a variance, a standard deviation, a median, a mode, a kurtosis, and a skewness of the position of the second point. The first identification means identifies a position of a first point in each of the first voxels identified by the first identification means;
the second identification means identifies a position of a second point belonging to each of the boundary surfaces identified by the second identification means, and further identifies a combination of the second points, in which a polygonal surface defined by the second points in the combination corresponds to a surface of the object;
5. The data processing device according to claim 4, wherein the second generating means generates the surface point group based on a position of the first point in the first voxel identified by the second identifying means and a position of the second point identified by the second identifying means, and further generates the mesh based on the combination identified by the second identifying means and the surface point group generated by the second generating means. 17. The data processing device according to claim 16, wherein the second identification means identifies the combination of the second points by identifying a point group or a surface corresponding to the surface of the object inside a virtual voxel having predetermined points belonging to each of the eight second voxels as vertices, based on each voxel value of the eight second voxels in which one of the multiple vertices defining the second voxel is located at the same position. an acquisition means for acquiring first information representing a shape of an object using a plurality of first unit regions;
a first generating means for generating second information representing a shape of the object using a plurality of second unit areas, the second unit areas being larger than the first unit areas, based on the first information;
a first specifying means for specifying a plurality of the first unit areas corresponding to an outer shape of the object based on the first information;
a second identification means for identifying a plurality of boundaries between the second unit areas adjacent to each other, the boundaries corresponding to the outer shape of the object, based on the second information;
a second generating means for generating a point cloud corresponding to the outer shape of the object based on the first unit area identified by the first identifying means and the boundary identified by the second identifying means;
having
the acquiring means acquires, as the first information, a first volume that represents a three-dimensional shape of the object using a plurality of first voxels that are a plurality of the first unit regions;
the first generation means generates, as the second information, a second volume representing a three-dimensional shape of the object using a plurality of second voxels that are second unit regions larger in size than the first voxels, based on the first volume;
the first identification means identifies, based on the first volume, a plurality of first voxels corresponding to a surface of the object as a plurality of first unit regions corresponding to the outer shape of the object;
the second identification means identifies, as the boundary, a plurality of boundary surfaces between adjacent second voxels corresponding to a surface of the object, based on the second volume;
the second generating means generates, as the point group, a surface point group corresponding to a surface shape of the object, based on the first voxel identified by the first identifying means and the boundary surface identified by the second identifying means;
The first identification means identifies, for each of the first voxels identified by the first identification means, a position of a first point that belongs to the first voxel and characterizes the first voxel;
The second identification means identifies, for each of the boundary surfaces identified by the second identification means, a position of a second point that belongs to the boundary surface and characterizes the boundary surface;
The second generating means generates the surface point group based on the position of the first point in the first voxel identified by the first identifying means and the position of the second point identified by the second identifying means.
A data processing device comprising: an acquisition step of acquiring first information representing a shape of an object using a plurality of first unit regions;
a first generation step of generating second information representing a shape of the object using a plurality of second unit areas, the second unit areas being larger than the first unit areas, based on the first information;
a first identification step of identifying a plurality of the first unit areas corresponding to an outer shape of the object based on the first information;
a second identification step of identifying a plurality of boundaries between the second unit areas adjacent to each other, the boundaries corresponding to the outer shape of the object, based on the second information;
a second generation step of generating a point cloud corresponding to the outer shape of the object based on the first unit area identified in the first identification step and the boundary identified in the second identification step;
having
In the first specifying step, each of the first unit areas specified in the first specifying step is associated with the second unit area including a position of the first unit area or with the second unit area located closest to the position of the first unit area, based on the first information and the second information;
In the second generating step, for each of the second unit areas, the point cloud corresponding to the outer shape of the object is generated based on the first unit area associated with the second unit area among the first unit areas identified in the first identifying step, and the boundary corresponding to the second unit area identified in the second identifying step;
In the first specifying step, when associating the first unit area with the second unit area located closest to the position of the first unit area, if there are a plurality of second unit areas located closest to the position of the first unit area, the first unit area is associated with all of the second unit areas located closest to the position of the first unit area.
1. A data processing method comprising: an acquisition step of acquiring first information representing a shape of an object using a plurality of first unit regions;
a first generation step of generating second information representing a shape of the object using a plurality of second unit areas, the second unit areas being larger than the first unit areas, based on the first information;
a first identification step of identifying a plurality of the first unit areas corresponding to an outer shape of the object based on the first information;
a second identification step of identifying a plurality of boundaries between the second unit areas adjacent to each other, the boundaries corresponding to the outer shape of the object, based on the second information;
a second generation step of generating a point cloud corresponding to the outer shape of the object based on the first unit area identified in the first identification step and the boundary identified in the second identification step;
having
In the acquiring step, a first volume expressing a three-dimensional shape of the object is acquired using a plurality of first voxels which are a plurality of the first unit regions as the first information;
In the first generation step, a second volume is generated as the second information based on the first volume, the second volume being represented by a plurality of second voxels which are second unit regions larger than the first voxels, and the second volume represents a three-dimensional shape of the object;
In the first identification step, a plurality of first voxels corresponding to a surface of the object are identified as a plurality of first unit regions corresponding to the outer shape of the object based on the first volume;
In the second identification step, a plurality of boundary surfaces are identified as the boundary, the boundary surfaces being boundary surfaces between adjacent second voxels and corresponding to a surface of the object, based on the second volume;
In the second generation step, a surface point group corresponding to a surface shape of the object is generated as the point group based on the first voxel identified in the first identification step and the boundary surface identified in the second identification step;
In the first identification step, for each of the first voxels identified by the first identification step, a position of the first point that belongs to the first voxel and characterizes the first voxel is identified;
In the second identification step, for each of the boundary surfaces identified in the second identification step, a position of the second point that belongs to the boundary surface and characterizes the boundary surface is identified;
In the second generation step, the surface point group is generated based on the position of the first point in the first voxel identified in the first identification step and the position of the second point identified in the second identification step.
1. A data processing method comprising: Computer,
A program for causing the data processing device according to any one of claims 1 to 18 to operate as each of the means.