JP7763786B2 - Three-dimensional data decoding method, three-dimensional data encoding method, three-dimensional data decoding device, and three-dimensional data encoding device - Google Patents

Description

The present disclosure relates to a three-dimensional data encoding method, a three-dimensional data decoding method, a three-dimensional data encoding device, and a three-dimensional data decoding device.

In the future, devices and services that utilize 3D data are expected to become widespread in a wide range of fields, including computer vision for autonomous operation of automobiles or robots, map information, surveillance, infrastructure inspection, and video distribution. 3D data can be acquired in a variety of ways, including using distance sensors such as rangefinders, stereo cameras, or a combination of multiple monocular cameras.

One method of representing three-dimensional data is a method called a point cloud, which uses a group of points in three-dimensional space to represent the shape of a three-dimensional structure. A point cloud stores the position and color of the points. Point clouds are expected to become the mainstream method of representing three-dimensional data, but point clouds contain a very large amount of data. Therefore, when storing or transmitting three-dimensional data, it is essential to compress the data volume through encoding, just as with two-dimensional video images (examples include MPEG-4 AVC or HEVC standardized by MPEG).

In addition, compression of point clouds is partially supported by public libraries (Point Cloud Library) that perform point cloud-related processing.

In addition, technology is known that uses three-dimensional map data to search for and display facilities located around a vehicle (see, for example, Patent Document 1).

International Publication No. 2014/020663

In three-dimensional data encoding and decoding processes, it is desirable to be able to improve encoding efficiency or reduce processing volume.

The present disclosure aims to provide a three-dimensional data encoding method, a three-dimensional data decoding method, a three-dimensional data encoding device, or a three-dimensional data decoding device that can improve encoding efficiency or reduce processing volume.

A three-dimensional data decoding method according to one aspect of the present disclosure acquires a bit stream containing encoded position information in which the position information of a three-dimensional point is encoded, generates the position information by decoding the encoded position information, and shifts the position information if the position information is expressed in a Cartesian coordinate system, and does not shift the position information if the position information is expressed in a polar coordinate system.

A three-dimensional data encoding method according to one aspect of the present disclosure generates encoded position information by encoding position information of three-dimensional points, and generates a bit stream including the encoded position information and shift information indicating whether the three-dimensional data decoding device shifts the decoded position information decoded by the three-dimensional data decoding device. Based on the shift information, the three-dimensional data decoding device shifts the decoded position information if the decoded position information is expressed in a Cartesian coordinate system, and does not shift the decoded position information if the decoded position information is expressed in a polar coordinate system.

The present disclosure provides a three-dimensional data encoding method, a three-dimensional data decoding method, a three-dimensional data encoding device, or a three-dimensional data decoding device that can improve encoding efficiency or reduce processing volume.

FIG. 1 is a diagram showing the configuration of a three-dimensional data encoding/decoding system according to the first embodiment. FIG. 2 is a diagram illustrating an example of the configuration of point cloud data according to the first embodiment. FIG. 3 is a diagram showing an example of the structure of a data file in which point cloud data information according to the first embodiment is described. FIG. 4 is a diagram showing types of point cloud data according to the first embodiment. FIG. 5 is a diagram showing a configuration of a first encoding unit according to the first embodiment. FIG. 6 is a block diagram of a first encoding unit according to the first embodiment. FIG. 7 is a diagram showing a configuration of a first decoding unit according to the first embodiment. FIG. 8 is a block diagram of the first decoding unit according to the first embodiment. FIG. 9 is a block diagram of a three-dimensional data encoding device according to the first embodiment. FIG. 10 is a diagram illustrating an example of location information according to the first embodiment. FIG. 11 is a diagram showing an example of an octree representation of position information according to the first embodiment. FIG. 12 is a block diagram of a three-dimensional data decoding device according to the first embodiment. FIG. 13 is a block diagram of the attribute information encoding unit according to the first embodiment. FIG. 14 is a block diagram of the attribute information decoding unit according to the first embodiment. FIG. 15 is a block diagram showing a configuration of an attribute information encoding unit according to the first embodiment. FIG. 16 is a block diagram of the attribute information encoding unit according to the first embodiment. FIG. 17 is a block diagram showing a configuration of the attribute information decoding unit according to the first embodiment. FIG. 18 is a block diagram of the attribute information decoding unit according to the first embodiment. FIG. 19 is a diagram illustrating a configuration of a second encoding unit according to the first embodiment. FIG. 20 is a block diagram of a second encoding unit according to the first embodiment. FIG. 21 is a diagram illustrating a configuration of a second decoding unit according to the first embodiment. FIG. 22 is a block diagram of a second decoding unit according to the first embodiment. FIG. 23 is a diagram showing a protocol stack related to PCC encoded data according to the first embodiment. FIG. 24 is a diagram illustrating the configuration of an encoding unit and a multiplexing unit according to the second embodiment. FIG. 25 is a diagram illustrating an example of the structure of coded data according to the second embodiment. FIG. 26 is a diagram showing an example of the structure of coded data and NAL units according to the second embodiment. FIG. 27 is a diagram illustrating an example of the semantics of pcc_nal_unit_type according to the second embodiment. FIG. 28 is a diagram showing an example of a prediction tree used in a three-dimensional data encoding method according to the third embodiment. FIG. 29 is a flowchart showing an example of a three-dimensional data encoding method according to the third embodiment. FIG. 30 is a flowchart showing an example of a three-dimensional data decoding method according to the third embodiment. FIG. 31 is a diagram for explaining a method for generating a prediction tree according to the third embodiment. FIG. 32 is a diagram illustrating a first example of a prediction mode according to the third embodiment. FIG. 33 is a diagram showing a second example of a table indicating predicted values calculated in each prediction mode according to Embodiment 3. In FIG. FIG. 34 is a diagram showing a specific example of a second example of a table indicating predicted values calculated in each prediction mode according to the third embodiment. In FIG. FIG. 35 is a diagram showing a third example of a table indicating predicted values calculated in each prediction mode according to Embodiment 3. In FIG. FIG. 36 is a diagram illustrating an example of the syntax of a header of location information according to the third embodiment. FIG. 37 is a diagram illustrating an example of the syntax of the position information according to the third embodiment. FIG. 38 is a diagram showing another example of the syntax of the location information according to the third embodiment. FIG. 39 is a block diagram of a three-dimensional data encoding device according to the fourth embodiment. FIG. 40 is a block diagram of a three-dimensional data decoding device according to the fourth embodiment. FIG. 41 is a block diagram of a three-dimensional data encoding device according to the fourth embodiment. FIG. 42 is a block diagram of a three-dimensional data decoding device according to the fourth embodiment. FIG. 43 is a diagram illustrating an example of inter prediction according to the fourth embodiment. FIG. 44 is a diagram showing an example of syntax of an SPS according to the fourth embodiment. FIG. 45 is a diagram illustrating an example of syntax of a GPS according to the fourth embodiment. FIG. 46 is a flowchart of a three-dimensional data encoding process according to the fourth embodiment. FIG. 47 is a flowchart of three-dimensional data decoding processing according to the fourth embodiment. FIG. 48 is a block diagram of a three-dimensional data encoding device according to the fifth embodiment. FIG. 49 is a block diagram of a three-dimensional data decoding device according to the fifth embodiment. FIG. 50 is a flowchart showing an example of a procedure for encoding each 3D point of a prediction tree according to the fifth embodiment. FIG. 51 is a flowchart showing an example of a procedure for decoding each 3D point of a prediction tree according to the fifth embodiment. FIG. 52 is a block diagram of a three-dimensional data encoding device according to a modification of the fifth embodiment. FIG. 53 is a block diagram of a three-dimensional data decoding device according to a modification of the fifth embodiment. FIG. 54 is an example of the syntax of the GPS according to the fifth embodiment. FIG. 55 shows an example of the syntax of each 3D point according to the fifth embodiment. FIG. 56 is a flowchart showing three-dimensional data encoding processing according to the fifth embodiment. FIG. 57 is a flowchart showing three-dimensional data decoding processing according to the fifth embodiment. FIG. 58 is a flowchart showing the coordinate system switching process in the encoding process according to the fifth embodiment. FIG. 59 is a flowchart showing the coordinate system switching process in the decoding process according to the fifth embodiment. FIG. 60 is a flowchart showing another example of the three-dimensional data encoding process according to the fifth embodiment. FIG. 61 is a flowchart showing another example of the three-dimensional data decoding process according to the fifth embodiment. FIG. 62 is a block diagram of a position information encoding unit according to the sixth embodiment. FIG. 63 is a block diagram of a position information encoding unit according to the sixth embodiment. FIG. 64 is a block diagram of a position information encoding unit according to the sixth embodiment. FIG. 65 is a block diagram of a position information decoding unit according to the sixth embodiment. FIG. 66 is a block diagram of a position information decoding unit according to the sixth embodiment. FIG. 67 is a block diagram of a position information decoding unit according to the sixth embodiment. FIG. 68 is a block diagram of a three-dimensional data encoding device according to the sixth embodiment. FIG. 69 is a block diagram of a three-dimensional data decoding device according to the sixth embodiment. FIG. 70 is a flowchart of three-dimensional data decoding processing according to the sixth embodiment. FIG. 71 is a flowchart of three-dimensional data encoding processing according to the sixth embodiment. FIG. 72 is a flowchart of three-dimensional data decoding processing according to the sixth embodiment. FIG. 73 is a block diagram of a position information encoding unit that encodes position information in a rectangular coordinate system according to the seventh embodiment. FIG. 74 is a diagram showing an example of shift processing for position information in a rectangular coordinate system according to the seventh embodiment. FIG. 75 is a diagram showing an example of shift processing for position information in a rectangular coordinate system according to the seventh embodiment. FIG. 76 is a block diagram of a position information encoding unit that encodes position information in a polar coordinate system according to the seventh embodiment. FIG. 77 is a diagram showing an example of processing for position information in a polar coordinate system according to the seventh embodiment. FIG. 78 is a block diagram of a position information decoding unit that decodes position information in an orthogonal coordinate system according to the seventh embodiment. FIG. 79 is a block diagram of a position information decoding unit that decodes position information in a polar coordinate system according to the seventh embodiment. FIG. 80 is a block diagram of a position information encoding unit according to the seventh embodiment, which encodes position information in a rectangular coordinate system and position information in a polar coordinate system. FIG. 81 is a block diagram of a position information decoding unit according to the seventh embodiment, which decodes position information in a rectangular coordinate system and position information in a polar coordinate system. FIG. 82 is a block diagram of a position information decoding unit that performs coordinate transformation according to the seventh embodiment. FIG. 83 is a flowchart of three-dimensional data decoding processing according to the seventh embodiment. FIG. 84 is a diagram illustrating an example of GPS syntax according to the seventh embodiment. FIG. 85 is a diagram showing an example of the syntax of a GDU header according to the seventh embodiment. FIG. 86 is a flowchart of three-dimensional data decoding processing according to the seventh embodiment. FIG. 87 is a flowchart of three-dimensional data encoding processing according to the seventh embodiment. FIG. 88 is a block diagram of a three-dimensional data creation device according to the eighth embodiment. FIG. 89 is a flowchart of a three-dimensional data creation method according to the eighth embodiment. FIG. 90 is a diagram showing the configuration of a system according to the eighth embodiment. FIG. 91 is a block diagram of a client device according to the eighth embodiment. FIG. 92 is a block diagram of a server according to the eighth embodiment. FIG. 93 is a flowchart of three-dimensional data creation processing by a client device according to the eighth embodiment. FIG. 94 is a flowchart of a sensor information transmission process by a client device according to the eighth embodiment. FIG. 95 is a flowchart of three-dimensional data creation processing by the server according to the eighth embodiment. FIG. 96 is a flowchart of a three-dimensional map transmission process performed by a server according to the eighth embodiment. FIG. 97 is a diagram showing the configuration of a modified example of the system according to the eighth embodiment. FIG. 98 is a diagram showing the configuration of a server and a client device according to the eighth embodiment. FIG. 99 is a diagram showing the configuration of a server and a client device according to the eighth embodiment. FIG. 100 is a flowchart of processing by a client device according to the eighth embodiment. FIG. 101 is a diagram showing the configuration of a sensor information collection system according to the eighth embodiment. FIG. 102 is a diagram illustrating an example of a system according to the eighth embodiment. FIG. 103 is a diagram showing a modified example of the system according to the eighth embodiment. FIG. 104 is a flowchart showing an example of application processing according to the eighth embodiment. FIG. 105 is a diagram showing the sensor ranges of various sensors according to the eighth embodiment. FIG. 106 is a diagram illustrating an example of the configuration of an autonomous driving system according to the eighth embodiment. FIG. 107 is a diagram showing an example of the structure of a bitstream according to the eighth embodiment. FIG. 108 is a flowchart of the point group selection process according to the eighth embodiment. FIG. 109 is a diagram showing an example of a screen for the point group selection process according to the eighth embodiment. FIG. 110 is a diagram showing an example of a screen for point cloud selection processing according to the eighth embodiment. FIG. 111 is a diagram showing an example of a screen for point cloud selection processing according to the eighth embodiment.

A three-dimensional data decoding method according to one aspect of the present disclosure acquires a bit stream containing encoded position information in which the position information of a three-dimensional point is encoded, generates the position information by decoding the encoded position information, and shifts the position information if the position information is expressed in a Cartesian coordinate system, and does not shift the position information if the position information is expressed in a polar coordinate system.

This allows the three-dimensional data decoding method to switch between performing shift processing on position information depending on whether the encoded position information is in a Cartesian coordinate system or a polar coordinate system. Here, if the position information is in a Cartesian coordinate system, the three-dimensional data encoding device performs shift processing before encoding, thereby improving encoding efficiency. If the position information is in a Cartesian coordinate system, the three-dimensional data decoding method performs shift processing, thereby allowing the bitstream to be properly decoded with improved encoding efficiency. Furthermore, if the position information is in a polar coordinate system, the three-dimensional data decoding method does not perform shift processing, thereby reducing the amount of processing.

For example, the bit stream may include first flag information indicating whether the position information is expressed in the polar coordinate system, and second flag information indicating whether the position information expressed in the polar coordinate system is converted into converted position information expressed in the Cartesian coordinate system.

For example, if the position information is expressed in the polar coordinate system and the position of the sensor generating the three-dimensional point is the origin of the polar coordinate system, the shift may not be performed.

For example, if shift information indicating the amount of shift is obtained from the bit stream and the position information is expressed in the polar coordinate system, the amount indicated by the shift information is zero, and the position information expressed in the polar coordinate system can be shifted based on the amount indicated by the shift information, thereby eliminating the need to shift the position information expressed in the polar coordinate system.

As a result, the three-dimensional data decoding method can apply shift processing to position information regardless of whether the position information is in a Cartesian coordinate system or a polar coordinate system, eliminating the need to control whether or not to perform shift processing, thereby simplifying processing.

For example, shift information indicating the amount of shift may be obtained from the bit stream, and if the position information is expressed in the Cartesian coordinate system, the position information may be shifted based on the amount indicated by the shift information, and if the position information is expressed in the polar coordinate system, the amount may be considered to be zero regardless of the amount indicated by the shift information.

According to this, when the position information is in a polar coordinate system, the three-dimensional data decoding method considers the shift amount to be zero regardless of the shift amount indicated by the shift information. This reduces the amount of processing required by the three-dimensional data encoding device that generates the bitstream. Furthermore, this three-dimensional data decoding method may be able to correctly decode the bitstream even if it contains errors.

For example, if the bit stream contains shift information indicating the amount of the shift, it may be determined that the position information is represented in the Cartesian coordinate system, and the position information may be shifted based on the amount indicated by the shift information; if the bit stream does not contain the shift information, it may be determined that the position information is represented in the polar coordinate system, and the position information may not need to be shifted.

This means that if the position information is in polar coordinates, the bitstream does not contain shift information, thereby reducing the amount of data in the bitstream.

For example, the bitstream may include encoded information in which positional information of multiple three-dimensional points including the three-dimensional point is encoded, the encoded information is divided into multiple division units into which the multiple three-dimensional points are divided, and the shift information may be included in a parameter set common to the multiple division units.

For example, the bit stream may include encoded information in which positional information of multiple three-dimensional points including the three-dimensional point is encoded, the encoded information is divided into multiple division units into which the multiple three-dimensional points are divided, and the shift information may be included in a header for each of the multiple division units.

For example, if the position information is expressed in the polar coordinate system, the position information may be converted into transformed position information expressed in the Cartesian coordinate system, and the transformed position information may be shifted.

Accordingly, even if the encoded position information is in a polar coordinate system, the three-dimensional data decoding method can convert the position information in the polar coordinate system into position information in a Cartesian coordinate system and output the position information in the Cartesian coordinate system.

A three-dimensional data encoding method according to one aspect of the present disclosure generates encoded position information by encoding position information of three-dimensional points, and generates a bit stream including the encoded position information and shift information indicating whether the three-dimensional data decoding device shifts the decoded position information decoded by the three-dimensional data decoding device. Based on the shift information, the three-dimensional data decoding device shifts the decoded position information if the decoded position information is expressed in a Cartesian coordinate system, and does not shift the decoded position information if the decoded position information is expressed in a polar coordinate system.

This three-dimensional data encoding method can generate a bitstream in which the three-dimensional data decoding device can switch whether to perform shift processing on the position information depending on whether the encoded position information is in a Cartesian coordinate system or a polar coordinate system. Here, when the position information is in a Cartesian coordinate system, the three-dimensional data encoding device performs shift processing before encoding, thereby improving encoding efficiency. When the position information is in a Cartesian coordinate system, the three-dimensional data decoding device performs shift processing, allowing it to properly decode a bitstream with improved encoding efficiency. Furthermore, when the position information is in a polar coordinate system, the three-dimensional data decoding device does not perform shift processing, thereby reducing the amount of processing.

For example, the bit stream may include first flag information indicating whether the position information is expressed in the polar coordinate system, and second flag information indicating whether the position information expressed in the polar coordinate system is converted into converted position information expressed in the Cartesian coordinate system.

For example, if the position information is expressed in the polar coordinate system and the position of the sensor generating the three-dimensional point is the origin of the polar coordinate system, the shift may not be performed.

For example, the shift information indicates the amount of shift when shifting the decoded position information, and when the position information is expressed in the polar coordinate system, the amount indicated by the shift information is zero, and the three-dimensional data decoding device shifts the position information expressed in the polar coordinate system based on the amount indicated by the shift information, thereby not shifting the position information expressed in the polar coordinate system.

As a result, for example, in a three-dimensional data decoding device, shift processing can be applied to position information regardless of whether the position information is in a Cartesian coordinate system or a polar coordinate system, eliminating the need to control whether or not to perform shift processing, thereby simplifying processing in the three-dimensional data decoding device.

For example, if the position information is expressed in the Cartesian coordinate system, the shift information indicates the amount of shift when shifting the decoded position information, and if the position information is expressed in the polar coordinate system, the shift information does not need to be stored in the bitstream.

This means that if the position information is in polar coordinates, the bitstream does not contain shift information, thereby reducing the amount of data in the bitstream.

For example, the bitstream may include encoded information in which positional information of multiple three-dimensional points including the three-dimensional point is encoded, the encoded information is divided into multiple division units into which the multiple three-dimensional points are divided, and the shift information may be included in a parameter set common to the multiple division units.

For example, the bit stream may include encoded information in which positional information of multiple three-dimensional points including the three-dimensional point is encoded, the encoded information is divided into multiple division units into which the multiple three-dimensional points are divided, and the shift information may be included in a header for each of the multiple division units.

In addition, a three-dimensional data decoding device according to one aspect of the present disclosure includes a processor and a memory, and the processor uses the memory to obtain a bit stream including encoded position information in which position information of three-dimensional points is encoded, generates position information by decoding the encoded position information, and shifts the position information if the position information is expressed in a Cartesian coordinate system, and does not shift the position information if the position information is expressed in a polar coordinate system.

This allows the three-dimensional data decoding device to switch whether to perform shift processing on the position information depending on whether the encoded position information is in a Cartesian coordinate system or a polar coordinate system. Here, if the position information is in a Cartesian coordinate system, the three-dimensional data encoding device performs shift processing before encoding, thereby improving encoding efficiency. If the position information is in a Cartesian coordinate system, the three-dimensional data decoding device performs shift processing, allowing it to properly decode a bitstream with improved encoding efficiency. Furthermore, if the position information is in a polar coordinate system, the three-dimensional data decoding device does not perform shift processing, thereby reducing the amount of processing.

Furthermore, a three-dimensional data encoding device according to one aspect of the present disclosure includes a processor and a memory, and the processor uses the memory to generate encoded position information by encoding position information of three-dimensional points, and generates a bit stream including the encoded position information and shift information indicating whether the three-dimensional data decoding device shifts the decoded position information decoded by the three-dimensional data decoding device, and based on the shift information, the three-dimensional data decoding device shifts the decoded position information if the decoded position information is expressed in a Cartesian coordinate system, and does not shift the decoded position information if the decoded position information is expressed in a polar coordinate system.

This allows the three-dimensional data encoding device to generate a bitstream in which the three-dimensional data decoding device can switch whether to perform shift processing on the position information depending on whether the encoded position information is in a Cartesian coordinate system or a polar coordinate system. Here, when the position information is in a Cartesian coordinate system, the three-dimensional data encoding device performs shift processing before encoding, thereby improving encoding efficiency. When the position information is in a Cartesian coordinate system, the three-dimensional data decoding device performs shift processing, allowing it to properly decode a bitstream with improved encoding efficiency. Furthermore, when the position information is in a polar coordinate system, the three-dimensional data decoding device does not perform shift processing, thereby reducing the amount of processing.

In addition, these comprehensive or specific aspects may be realized as a system, method, integrated circuit, computer program, or computer-readable recording medium such as a CD-ROM, or as any combination of a system, method, integrated circuit, computer program, and recording medium.

The following describes the embodiments in detail with reference to the drawings. Note that each of the embodiments described below represents a specific example of the present disclosure. The numerical values, shapes, materials, components, component placement and connection configurations, steps, and step order shown in the following embodiments are merely examples and are not intended to limit the present disclosure. Furthermore, among the components in the following embodiments, components that are not recited in the independent claims are described as optional components.

(Embodiment 1)
When using encoded point cloud data in an actual device or service, it is desirable to transmit and receive the information required for the application in order to reduce network bandwidth. However, until now, such a function has not existed in the encoding structure of 3D data, and no encoding method for this purpose has existed.

In this embodiment, we describe a three-dimensional data encoding method and a three-dimensional data encoding device that provide the function of transmitting and receiving information required for a particular purpose in encoded data of a three-dimensional point cloud, as well as a three-dimensional data decoding method and a three-dimensional data decoding device that decodes the encoded data, a three-dimensional data multiplexing method that multiplexes the encoded data, and a three-dimensional data transmission method that transmits the encoded data.

In particular, the first and second encoding methods are currently being considered as methods (encoding schemes) for encoding point cloud data, but the structure of the encoded data and the method for storing the encoded data in a system format have not been defined, which poses the problem that, as things stand, it is not possible to perform MUX processing (multiplexing) in the encoding unit, or to transmit or store the data.

In addition, there has been no method to date to support formats that mix two codecs, the first encoding method and the second encoding method, such as PCC (Point Cloud Compression).

In this embodiment, we will explain the structure of PCC encoded data that mixes two codecs, the first encoding method and the second encoding method, and how to store the encoded data in a system format.

First, the configuration of a three-dimensional data (point cloud data) encoding/decoding system according to this embodiment will be described. FIG. 1 is a diagram showing an example configuration of a three-dimensional data encoding/decoding system according to this embodiment. As shown in FIG. 1, the three-dimensional data encoding/decoding system includes a three-dimensional data encoding system 4601, a three-dimensional data decoding system 4602, a sensor terminal 4603, and an external connection unit 4604.

The three-dimensional data encoding system 4601 generates encoded data or multiplexed data by encoding point cloud data, which is three-dimensional data. The three-dimensional data encoding system 4601 may be a three-dimensional data encoding device realized by a single device, or a system realized by multiple devices. The three-dimensional data encoding device may also include some of the multiple processing units included in the three-dimensional data encoding system 4601.

The three-dimensional data encoding system 4601 includes a point cloud data generation system 4611, a presentation unit 4612, an encoding unit 4613, a multiplexing unit 4614, an input/output unit 4615, and a control unit 4616. The point cloud data generation system 4611 includes a sensor information acquisition unit 4617 and a point cloud data generation unit 4618.

The sensor information acquisition unit 4617 acquires sensor information from the sensor terminal 4603 and outputs the sensor information to the point cloud data generation unit 4618. The point cloud data generation unit 4618 generates point cloud data from the sensor information and outputs the point cloud data to the encoding unit 4613.

The presentation unit 4612 presents the sensor information or point cloud data to the user. For example, the presentation unit 4612 displays information or an image based on the sensor information or point cloud data.

The encoding unit 4613 encodes (compresses) the point cloud data and outputs the resulting encoded data, control information obtained during the encoding process, and other additional information to the multiplexing unit 4614. The additional information includes, for example, sensor information.

The multiplexing unit 4614 generates multiplexed data by multiplexing the coded data input from the coding unit 4613, control information, and additional information. The format of the multiplexed data is, for example, a file format for storage or a packet format for transmission.

The input/output unit 4615 (e.g., a communication unit or interface) outputs the multiplexed data to the outside. Alternatively, the multiplexed data is stored in a storage unit such as internal memory. The control unit 4616 (or application execution unit) controls each processing unit. In other words, the control unit 4616 controls encoding, multiplexing, etc.

In addition, the sensor information may be input to the encoding unit 4613 or the multiplexing unit 4614. In addition, the input/output unit 4615 may output the point cloud data or encoded data directly to the outside.

The transmission signal (multiplexed data) output from the three-dimensional data encoding system 4601 is input to the three-dimensional data decoding system 4602 via the external connection unit 4604.

The three-dimensional data decoding system 4602 generates point cloud data, which is three-dimensional data, by decoding the encoded data or multiplexed data. The three-dimensional data decoding system 4602 may be a three-dimensional data decoding device realized by a single device, or may be a system realized by multiple devices. The three-dimensional data decoding device may also include some of the multiple processing units included in the three-dimensional data decoding system 4602.

The three-dimensional data decoding system 4602 includes a sensor information acquisition unit 4621, an input/output unit 4622, a demultiplexing unit 4623, a decoding unit 4624, a presentation unit 4625, a user interface 4626, and a control unit 4627.

The sensor information acquisition unit 4621 acquires sensor information from the sensor terminal 4603.

The input/output unit 4622 acquires the transmission signal, decodes the multiplexed data (file format or packets) from the transmission signal, and outputs the multiplexed data to the demultiplexing unit 4623.

The demultiplexing unit 4623 obtains encoded data, control information, and additional information from the multiplexed data, and outputs the encoded data, control information, and additional information to the decoding unit 4624.

The decoding unit 4624 reconstructs the point cloud data by decoding the encoded data.

The presentation unit 4625 presents the point cloud data to the user. For example, the presentation unit 4625 displays information or images based on the point cloud data. The user interface 4626 acquires instructions based on user operations. The control unit 4627 (or the application execution unit) controls each processing unit. In other words, the control unit 4627 controls demultiplexing, decoding, presentation, etc.

The input/output unit 4622 may acquire point cloud data or encoded data directly from outside. The presentation unit 4625 may acquire additional information such as sensor information and present information based on the additional information. The presentation unit 4625 may also present information based on user instructions acquired by the user interface 4626.

The sensor terminal 4603 generates sensor information, which is information obtained by a sensor. The sensor terminal 4603 is a terminal equipped with a sensor or camera, and may be, for example, a moving object such as an automobile, a flying object such as an airplane, a mobile terminal, or a camera.

Sensor information that can be acquired by the sensor terminal 4603 includes, for example, (1) the distance between the sensor terminal 4603 and an object, or the reflectance of the object, obtained from a LIDAR, millimeter-wave radar, or infrared sensor, and (2) the distance between the camera and the object, or the reflectance of the object, obtained from multiple monocular camera images or stereo camera images. The sensor information may also include the sensor's attitude, orientation, gyro (angular velocity), position (GPS information or altitude), speed, acceleration, etc. The sensor information may also include temperature, air pressure, humidity, magnetism, etc.

The external connection unit 4604 is realized by an integrated circuit (LSI or IC), an external storage unit, communication with a cloud server via the Internet, or broadcasting, etc.

Next, we will explain point cloud data. Figure 2 is a diagram showing the structure of point cloud data. Figure 3 is a diagram showing an example of the structure of a data file in which information about point cloud data is described.

Point cloud data contains data on multiple points. The data for each point includes location information (three-dimensional coordinates) and attribute information for that location information. A collection of multiple points is called a point cloud. For example, a point cloud may represent the three-dimensional shape of an object.

Position information such as three-dimensional coordinates is sometimes called geometry. Furthermore, the data for each point may include attribute information of multiple attribute types. Attribute types include, for example, color or reflectance.

One piece of attribute information may be associated with one piece of location information, or multiple pieces of attribute information with different attribute types may be associated with one piece of location information. Also, multiple pieces of attribute information of the same attribute type may be associated with one piece of location information.

The example data file configuration shown in Figure 3 is an example where there is a one-to-one correspondence between location information and attribute information, and shows the location information and attribute information of N points that make up the point cloud data.

Position information is, for example, information on the three axes x, y, and z. Attribute information is, for example, RGB color information. A typical data file is a ply file.

Next, we will explain the types of point cloud data. Figure 4 is a diagram showing the types of point cloud data. As shown in Figure 4, point cloud data includes static objects and dynamic objects.

A static object is 3D point cloud data at any time (a certain instant of time). A dynamic object is 3D point cloud data that changes over time. Hereafter, 3D point cloud data at a certain time will be referred to as a PCC frame, or frame.

An object may be a point cloud with a somewhat restricted area, such as normal video data, or a large-scale point cloud with an unlimited area, such as map information.

There may also be point cloud data of various densities, including sparse point cloud data and dense point cloud data.

The details of each processing unit are explained below. Sensor information is acquired by various methods, such as distance sensors such as LIDAR or range finders, stereo cameras, or a combination of multiple monocular cameras. The point cloud data generation unit 4618 generates point cloud data based on the sensor information acquired by the sensor information acquisition unit 4617. The point cloud data generation unit 4618 generates position information as point cloud data and adds attribute information for the position information to the position information.

The point cloud data generation unit 4618 may process the point cloud data when generating position information or adding attribute information. For example, the point cloud data generation unit 4618 may reduce the amount of data by deleting point clouds with overlapping positions. In addition, the point cloud data generation unit 4618 may transform the position information (such as by shifting, rotating, or normalizing) or render the attribute information.

In Figure 1, the point cloud data generation system 4611 is included in the three-dimensional data encoding system 4601, but it may also be provided independently outside the three-dimensional data encoding system 4601.

The encoding unit 4613 generates encoded data by encoding the point cloud data based on a predefined encoding method. There are two main types of encoding methods: the first is an encoding method that uses position information, and this encoding method will be referred to as the first encoding method hereinafter. The second is an encoding method that uses a video codec, and this encoding method will be referred to as the second encoding method hereinafter.

The decoding unit 4624 decodes the point cloud data by decoding the encoded data based on a pre-specified encoding method.

The multiplexing unit 4614 generates multiplexed data by multiplexing the encoded data using an existing multiplexing method. The generated multiplexed data is transmitted or stored. In addition to the PCC encoded data, the multiplexing unit 4614 multiplexes other media such as video, audio, subtitles, applications, files, or reference time information. The multiplexing unit 4614 may also multiplex attribute information related to sensor information or point cloud data.

Multiplexing methods or file formats include ISOBMFF, and ISOBMFF-based transmission methods such as MPEG-DASH, MMT, MPEG-2 TS Systems, and RMP.

The demultiplexing unit 4623 extracts PCC encoded data, other media, time information, etc. from the multiplexed data.

The input/output unit 4615 transmits the multiplexed data using a method suited to the transmission medium or storage medium, such as broadcasting or communication. The input/output unit 4615 may communicate with other devices via the Internet, or may communicate with a storage unit such as a cloud server.

Communication protocols include http, ftp, TCP, and UDP. A pull-type communication method or a push-type communication method may be used.

Either wired or wireless transmission may be used. For wired transmission, Ethernet (registered trademark), USB, RS-232C, HDMI (registered trademark), or coaxial cable may be used. For wireless transmission, wireless LAN, Wi-Fi (registered trademark), Bluetooth (registered trademark), or millimeter waves may be used.

In addition, broadcasting methods such as DVB-T2, DVB-S2, DVB-C2, ATSC3.0, or ISDB-S3 are used.

Figure 5 is a diagram showing the configuration of a first encoding unit 4630, which is an example of an encoding unit 4613 that performs encoding using the first encoding method. Figure 6 is a block diagram of the first encoding unit 4630. The first encoding unit 4630 generates encoded data (encoded stream) by encoding point cloud data using the first encoding method. This first encoding unit 4630 includes a position information encoding unit 4631, an attribute information encoding unit 4632, an additional information encoding unit 4633, and a multiplexing unit 4634.

The first encoding unit 4630 is characterized by performing encoding with consideration of three-dimensional structure. The first encoding unit 4630 is also characterized by the attribute information encoding unit 4632 performing encoding using information obtained from the position information encoding unit 4631. The first encoding method is also called GPCC (Geometry-based PCC).

The point cloud data is PCC point cloud data such as a PLY file, or PCC point cloud data generated from sensor information, and includes position information (Position), attribute information (Attribute), and other additional information (MetaData). The position information is input to the position information encoding unit 4631, the attribute information is input to the attribute information encoding unit 4632, and the additional information is input to the additional information encoding unit 4633.

The position information encoding unit 4631 encodes the position information to generate encoded position information (Compressed Geometry), which is encoded data. For example, the position information encoding unit 4631 encodes the position information using an N-ary tree structure such as an octree. Specifically, in an octree, the target space is divided into eight nodes (subspaces), and 8-bit information (occupancy code) indicating whether or not a point cloud is included in each node is generated. Furthermore, the node that includes a point cloud is further divided into eight nodes, and 8-bit information indicating whether or not a point cloud is included in each of the eight nodes is generated. This process is repeated until the number of point clouds included in a predetermined hierarchy or node falls below a threshold.

The attribute information encoding unit 4632 generates encoded attribute information (Compressed Attribute), which is encoded data, by encoding using the configuration information generated by the position information encoding unit 4631. For example, the attribute information encoding unit 4632 determines a reference point (reference node) to reference when encoding the target point (target node) to be processed, based on the octree structure generated by the position information encoding unit 4631. For example, the attribute information encoding unit 4632 references a peripheral or adjacent node whose parent node in the octree is the same as that of the target node. Note that the method of determining the reference relationship is not limited to this.

The encoding process for attribute information may also include at least one of a quantization process, a prediction process, and an arithmetic coding process. In this case, referencing means using a reference node to calculate a predicted value for the attribute information, or using the state of the reference node (e.g., occupancy information indicating whether the reference node contains a point group) to determine encoding parameters. For example, encoding parameters include quantization parameters in a quantization process, or context in arithmetic coding.

The additional information encoding unit 4633 generates encoded additional information (Compressed MetaData), which is encoded data, by encoding compressible data from the additional information.

The multiplexing unit 4634 generates a coded stream (Compressed Stream) which is coded data by multiplexing the coding position information, coding attribute information, coding additional information, and other additional information. The generated coded stream is output to a processing unit in the system layer (not shown).

Next, we will explain the first decoding unit 4640, which is an example of a decoding unit 4624 that performs decoding using the first encoding method. Figure 7 is a diagram showing the configuration of the first decoding unit 4640. Figure 8 is a block diagram of the first decoding unit 4640. The first decoding unit 4640 generates point cloud data by decoding, using the first encoding method, encoded data (encoded stream). This first decoding unit 4640 includes a demultiplexing unit 4641, a position information decoding unit 4642, an attribute information decoding unit 4643, and an additional information decoding unit 4644.

An encoded stream (compressed stream), which is encoded data, is input to the first decoding unit 4640 from a processing unit of a system layer not shown.

The demultiplexing unit 4641 separates the encoded position information (Compressed Geometry), encoded attribute information (Compressed Attribute), encoded additional information (Compressed MetaData), and other additional information from the encoded data.

The position information decoding unit 4642 generates position information by decoding the encoded position information. For example, the position information decoding unit 4642 restores the position information of a point group represented by three-dimensional coordinates from encoded position information represented by an N-ary tree structure such as an octree.

The attribute information decoding unit 4643 decodes the encoded attribute information based on the configuration information generated by the position information decoding unit 4642. For example, the attribute information decoding unit 4643 determines a reference point (reference node) to reference when decoding the target point (target node) to be processed based on the octree structure obtained by the position information decoding unit 4642. For example, the attribute information decoding unit 4643 references a peripheral or adjacent node whose parent node in the octree is the same as that of the target node. Note that the method of determining the reference relationship is not limited to this.

The attribute information decoding process may also include at least one of an inverse quantization process, a prediction process, and an arithmetic decoding process. In this case, referencing means using a reference node to calculate a predicted value of the attribute information, or using the state of the reference node (e.g., occupancy information indicating whether the reference node contains a point group) to determine decoding parameters. For example, decoding parameters include quantization parameters in an inverse quantization process, or context in arithmetic decoding.

The additional information decoding unit 4644 generates additional information by decoding the encoded additional information. The first decoding unit 4640 uses the additional information required for the decoding process of the position information and attribute information during decoding, and outputs the additional information required for the application to the outside.

Next, an example configuration of the position information encoding unit will be described. Figure 9 is a block diagram of the position information encoding unit 2700 according to this embodiment. The position information encoding unit 2700 includes an octree generation unit 2701, a geometric information calculation unit 2702, a coding table selection unit 2703, and an entropy encoding unit 2704.

The octree generation unit 2701 generates, for example, an octree from the input position information and generates an occupancy code for each node in the octree. The geometric information calculation unit 2702 obtains information indicating whether an adjacent node of the target node is an occupied node. For example, the geometric information calculation unit 2702 calculates the occupancy information of the adjacent node (information indicating whether the adjacent node is an occupied node) from the occupancy code of the parent node to which the target node belongs. The geometric information calculation unit 2702 may also store encoded nodes in a list and search for adjacent nodes from that list. The geometric information calculation unit 2702 may also switch adjacent nodes depending on the position of the target node within the parent node.

The coding table selection unit 2703 selects a coding table to be used for entropy coding of the target node using the occupancy information of adjacent nodes calculated by the geometric information calculation unit 2702. For example, the coding table selection unit 2703 may generate a bit string using the occupancy information of adjacent nodes and select a coding table for the index number generated from the bit string.

The entropy coding unit 2704 generates coding position information and metadata by entropy coding the occupancy code of the target node using the coding table of the selected index number. The entropy coding unit 2704 may add information indicating the selected coding table to the coding position information.

The following explains the octree representation and the scanning order of position information. Position information (position data) is converted into an octree structure (octreeing) and then encoded. The octree structure consists of nodes and leaves. Each node has eight nodes or leaves, and each leaf has voxel (VXL) information. Figure 10 is a diagram showing an example of the structure of position information containing multiple voxels. Figure 11 is a diagram showing an example of the position information shown in Figure 10 converted into an octree structure. Here, of the leaves shown in Figure 11, leaves 1, 2, and 3 represent voxels VXL1, VXL2, and VXL3 shown in Figure 10, respectively, and represent a VXL containing a point cloud (hereinafter referred to as a valid VXL).

Specifically, node 1 corresponds to the global space containing the position information in Figure 10. The global space corresponding to node 1 is divided into eight nodes, and of these eight nodes, the node containing a valid VXL is further divided into eight nodes or leaves, and this process is repeated for each level of the tree structure. Here, each node corresponds to a subspace, and node information contains information (occupancy code) indicating the position of the next node or leaf after division. In addition, the lowest-level block is set as a leaf, and leaf information such as the number of points contained in the leaf is stored.

Next, an example configuration of the position information decoding unit will be described. Figure 12 is a block diagram of the position information decoding unit 2710 according to this embodiment. The position information decoding unit 2710 includes an octree generation unit 2711, a geometric information calculation unit 2712, an encoding table selection unit 2713, and an entropy decoding unit 2714.

The octree generator 2711 generates an octree for a space (node) using header information or metadata of the bitstream. For example, the octree generator 2711 generates a large space (root node) using the size of the x-axis, y-axis, and z-axis directions of a space added to the header information, and then generates an octree by dividing that space into two along the x-axis, y-axis, and z-axis directions to generate eight small spaces A (nodes A0 to A7). Nodes A0 to A7 are set in order as target nodes.

The geometric information calculation unit 2712 obtains occupancy information indicating whether an adjacent node of the target node is an occupied node. For example, the geometric information calculation unit 2712 calculates the occupancy information of the adjacent node from the occupancy code of the parent node to which the target node belongs. The geometric information calculation unit 2712 may also store decoded nodes in a list and search for adjacent nodes from that list. The geometric information calculation unit 2712 may also switch adjacent nodes depending on the position of the target node within the parent node.

The coding table selection unit 2713 selects a coding table (decoding table) to be used for entropy decoding of the target node using the occupancy information of adjacent nodes calculated by the geometric information calculation unit 2712. For example, the coding table selection unit 2713 may generate a bit string using the occupancy information of adjacent nodes and select a coding table for the index number generated from the bit string.

The entropy decoding unit 2714 generates position information by entropy decoding the occupancy code of the target node using the selected encoding table. The entropy decoding unit 2714 may also obtain information about the selected encoding table by decoding it from the bitstream, and then entropy decode the occupancy code of the target node using the encoding table indicated by the information.

The configuration of the attribute information encoding unit and attribute information decoding unit is described below. Figure 13 is a block diagram showing an example configuration of the attribute information encoding unit A100. The attribute information encoding unit may include multiple encoding units that execute different encoding methods. For example, the attribute information encoding unit may switch between the following two methods depending on the use case.

The attribute information encoding unit A100 includes an LoD attribute information encoding unit A101 and a transformed attribute information encoding unit A102. The LoD attribute information encoding unit A101 classifies each 3D point into multiple layers using the position information of the 3D points, predicts the attribute information of the 3D points belonging to each layer, and encodes the prediction residual. Here, each classified layer is called LoD (Level of Detail).

The transformed attribute information encoding unit A102 encodes the attribute information using RAHT (Region Adaptive Hierarchical Transform). Specifically, the transformed attribute information encoding unit A102 applies RAHT or Haar transform to each piece of attribute information based on the position information of the three-dimensional points to generate high-frequency and low-frequency components for each layer, and encodes these values using quantization, entropy coding, etc.

Figure 14 is a block diagram showing an example configuration of the attribute information decoding unit A110. The attribute information decoding unit may include multiple decoding units that perform different decoding methods. For example, the attribute information decoding unit may switch between the following two methods for decoding based on information contained in the header or metadata.

The attribute information decoding unit A110 includes an LoD attribute information decoding unit A111 and a converted attribute information decoding unit A112. The LoD attribute information decoding unit A111 classifies each 3D point into multiple hierarchies using the position information of the 3D points, and decodes the attribute values while predicting the attribute information of the 3D points belonging to each hierarchical level.

The transformed attribute information decoding unit A112 decodes the attribute information using RAHT (Region Adaptive Hierarchical Transform). Specifically, the transformed attribute information decoding unit A112 decodes the attribute values by applying an inverse RAHT or an inverse Haar transform to the high-frequency and low-frequency components of each attribute value based on the position information of the three-dimensional points.

Figure 15 is a block diagram showing the configuration of the attribute information encoding unit 3140, which is an example of the LoD attribute information encoding unit A101.

The attribute information encoding unit 3140 includes an LoD generation unit 3141, a surrounding search unit 3142, a prediction unit 3143, a prediction residual calculation unit 3144, a quantization unit 3145, an arithmetic coding unit 3146, an inverse quantization unit 3147, a decoded value generation unit 3148, and a memory 3149.

The LoD generation unit 3141 generates LoD using the position information of the three-dimensional points.

The surrounding search unit 3142 searches for nearby 3D points adjacent to each 3D point using the LoD generation result by the LoD generation unit 3141 and distance information indicating the distance between each 3D point.

The prediction unit 3143 generates a predicted value of the attribute information of the target 3D point to be encoded.

The prediction residual calculation unit 3144 calculates (generates) the prediction residual of the predicted value of the attribute information generated by the prediction unit 3143.

The quantization unit 3145 quantizes the prediction residual of the attribute information calculated by the prediction residual calculation unit 3144.

The arithmetic coding unit 3146 arithmetically codes the prediction residuals after quantization by the quantization unit 3145. The arithmetic coding unit 3146 outputs a bitstream including the arithmetically coded prediction residuals to, for example, a three-dimensional data decoding device.

In addition, the prediction residual may be binarized, for example, by a quantization unit 3145, before being arithmetically coded by the arithmetic coding unit 3146.

Furthermore, for example, the arithmetic coding unit 3146 may initialize the coding table used for arithmetic coding before arithmetic coding. The arithmetic coding unit 3146 may initialize the coding table used for arithmetic coding for each layer. Furthermore, the arithmetic coding unit 3146 may output information indicating the position of the layer for which the coding table has been initialized, by including it in the bitstream.

The inverse quantization unit 3147 inverse quantizes the prediction residual after being quantized by the quantization unit 3145.

The decoded value generation unit 3148 generates a decoded value by adding the predicted value of the attribute information generated by the prediction unit 3143 and the prediction residual after inverse quantization by the inverse quantization unit 3147.

Memory 3149 is a memory that stores the decoded values of the attribute information of each three-dimensional point decoded by the decoded value generation unit 3148. For example, when generating a predicted value for a three-dimensional point that has not yet been encoded, the prediction unit 3143 generates the predicted value using the decoded values of the attribute information of each three-dimensional point stored in memory 3149.

Figure 16 is a block diagram of an attribute information encoding unit 6600, which is an example of the transformed attribute information encoding unit A102. The attribute information encoding unit 6600 includes a sorting unit 6601, a Haar transform unit 6602, a quantization unit 6603, an inverse quantization unit 6604, an inverse Haar transform unit 6605, a memory 6606, and an arithmetic encoding unit 6607.

The sorting unit 6601 generates a Morton code using the position information of the 3D points and sorts multiple 3D points in Morton code order. The Haar transform unit 6602 generates coding coefficients by applying a Haar transform to the attribute information. The quantization unit 6603 quantizes the coding coefficients of the attribute information.

The inverse quantization unit 6604 inversely quantizes the quantized coding coefficients. The inverse Haar transform unit 6605 applies an inverse Haar transform to the coding coefficients. The memory 6606 stores values of attribute information for multiple decoded 3D points. For example, the attribute information for decoded 3D points stored in the memory 6606 may be used for predicting uncoded 3D points.

The arithmetic coding unit 6607 calculates ZeroCnt from the coding coefficients after quantization and arithmetically codes ZeroCnt. The arithmetic coding unit 6607 also arithmetically codes the non-zero coding coefficients after quantization. The arithmetic coding unit 6607 may binarize the coding coefficients before arithmetic coding. The arithmetic coding unit 6607 may also generate and code various header information.

Figure 17 is a block diagram showing the configuration of the attribute information decoding unit 3150, which is an example of the LoD attribute information decoding unit A111.

The attribute information decoding unit 3150 includes an LoD generation unit 3151, a surrounding search unit 3152, a prediction unit 3153, an arithmetic decoding unit 3154, an inverse quantization unit 3155, a decoded value generation unit 3156, and a memory 3157.

The LoD generation unit 3151 generates LoD using the position information of the three-dimensional points decoded by the position information decoding unit (not shown in Figure 17).

The surrounding search unit 3152 searches for nearby 3D points adjacent to each 3D point using the LoD generation result by the LoD generation unit 3151 and distance information indicating the distance between each 3D point.

The prediction unit 3153 generates a predicted value of the attribute information of the target 3D point to be decoded.

The arithmetic decoding unit 3154 arithmetically decodes the prediction residuals in the bitstream obtained from the attribute information encoding unit 3140 shown in Figure 15. The arithmetic decoding unit 3154 may initialize the decoding table used for arithmetic decoding. The arithmetic decoding unit 3154 initializes the decoding table used for arithmetic decoding for the layer on which the arithmetic encoding unit 3146 shown in Figure 15 performed the encoding process. The arithmetic decoding unit 3154 may initialize the decoding table used for arithmetic decoding for each layer. The arithmetic decoding unit 3154 may also initialize the decoding table based on information included in the bitstream indicating the position of the layer for which the encoding table has been initialized.

The inverse quantization unit 3155 inverse quantizes the prediction residual arithmetically decoded by the arithmetic decoding unit 3154.

The decoded value generation unit 3156 generates a decoded value by adding the predicted value generated by the prediction unit 3153 and the prediction residual after inverse quantization by the inverse quantization unit 3155. The decoded value generation unit 3156 outputs the decoded attribute information data to another device.

Memory 3157 is a memory that stores the decoded values of the attribute information of each three-dimensional point decoded by the decoded value generation unit 3156. For example, when generating a predicted value for a three-dimensional point that has not yet been decoded, the prediction unit 3153 generates the predicted value using the decoded values of the attribute information of each three-dimensional point stored in memory 3157.

Figure 18 is a block diagram of an attribute information decoding unit 6610, which is an example of the transformed attribute information decoding unit A112. The attribute information decoding unit 6610 includes an arithmetic decoding unit 6611, an inverse quantization unit 6612, an inverse Haar transform unit 6613, and a memory 6614.

The arithmetic decoding unit 6611 arithmetically decodes the ZeroCnt and coding coefficients contained in the bitstream. The arithmetic decoding unit 6611 may also decode various header information.

The inverse quantization unit 6612 inverse quantizes the arithmetically decoded coding coefficients. The inverse Haar transform unit 6613 applies an inverse Haar transform to the coding coefficients after inverse quantization. The memory 6614 stores values of attribute information for multiple decoded 3D points. For example, the attribute information for decoded 3D points stored in the memory 6614 may be used to predict undecoded 3D points.

Next, we will explain the second encoding unit 4650, which is an example of the encoding unit 4613 that performs encoding using the second encoding method. Figure 19 is a diagram showing the configuration of the second encoding unit 4650. Figure 20 is a block diagram of the second encoding unit 4650.

The second encoding unit 4650 generates encoded data (encoded stream) by encoding the point cloud data using a second encoding method. This second encoding unit 4650 includes an additional information generation unit 4651, a position image generation unit 4652, an attribute image generation unit 4653, a video encoding unit 4654, an additional information encoding unit 4655, and a multiplexing unit 4656.

The second encoding unit 4650 has the feature of generating position images and attribute images by projecting a three-dimensional structure onto a two-dimensional image, and encoding the generated position images and attribute images using an existing video encoding method. The second encoding method is also called VPCC (Video-based PCC).

The point cloud data is PCC point cloud data such as a PLY file, or PCC point cloud data generated from sensor information, and includes position information (Position), attribute information (Attribute), and other additional information (MetaData).

The additional information generation unit 4651 generates map information for multiple two-dimensional images by projecting three-dimensional structures onto two-dimensional images.

The position image generation unit 4652 generates a position image (Geometry Image) based on the position information and the map information generated by the additional information generation unit 4651. This position image is, for example, a distance image in which distance (Depth) is indicated as pixel values. Note that this distance image may be an image of multiple point clouds viewed from a single viewpoint (an image in which multiple point clouds are projected onto a single two-dimensional plane), multiple images of multiple point clouds viewed from multiple viewpoints, or a single image in which these multiple images are integrated.

The attribute image generation unit 4653 generates an attribute image based on the attribute information and the map information generated by the additional information generation unit 4651. This attribute image is, for example, an image in which attribute information (e.g., color (RGB)) is represented as pixel values. Note that this image may be an image of multiple point clouds viewed from a single viewpoint (an image in which multiple point clouds are projected onto a single two-dimensional plane), multiple images of multiple point clouds viewed from multiple viewpoints, or a single image in which these multiple images are integrated.

The video encoding unit 4654 generates encoded data, an encoded position image (Compressed Geometry Image) and an encoded attribute image (Compressed Attribute Image), by encoding the position image and attribute image using a video encoding method. Note that any known encoding method may be used as the video encoding method. For example, the video encoding method may be AVC or HEVC.

The additional information encoding unit 4655 generates encoded additional information (Compressed MetaData) by encoding additional information contained in the point cloud data, map information, etc.

The multiplexing unit 4656 generates a coded stream (Compressed Stream) which is coded data by multiplexing the coded position image, coded attribute image, coded additional information, and other additional information. The generated coded stream is output to a processing unit in the system layer (not shown).

Next, we will explain the second decoding unit 4660, which is an example of a decoding unit 4624 that performs decoding using the second encoding method. Figure 21 is a diagram showing the configuration of the second decoding unit 4660. Figure 22 is a block diagram of the second decoding unit 4660. The second decoding unit 4660 generates point cloud data by decoding, using the second encoding method, encoded data (encoded stream) encoded using the second encoding method. This second decoding unit 4660 includes a demultiplexing unit 4661, a video decoding unit 4662, an additional information decoding unit 4663, a position information generation unit 4664, and an attribute information generation unit 4665.

An encoded stream (compressed stream), which is encoded data, is input to the second decoding unit 4660 from a processing unit of a system layer not shown.

The demultiplexing unit 4661 separates the encoded position image (Compressed Geometry Image), encoded attribute image (Compressed Attribute Image), encoded additional information (Compressed MetaData), and other additional information from the encoded data.

The video decoding unit 4662 generates a position image and an attribute image by decoding the encoded position image and encoded attribute image using a video encoding method. Any known encoding method may be used as the video encoding method. For example, the video encoding method may be AVC or HEVC.

The additional information decoding unit 4663 decodes the encoded additional information to generate additional information including map information, etc.

The location information generation unit 4664 generates location information using the location image and map information. The attribute information generation unit 4665 generates attribute information using the attribute image and map information.

The second decoding unit 4660 uses the additional information required for decoding during decoding and outputs the additional information required for the application to the outside.

The following explains the issues with the PCC encoding method. Figure 23 is a diagram showing a protocol stack related to PCC encoded data. Figure 23 shows an example of multiplexing other media data, such as video (e.g., HEVC) or audio, onto PCC encoded data and transmitting or storing it.

Multiplexing methods and file formats have the function of multiplexing various types of coded data and transmitting or storing them. To transmit or store coded data, the coded data must be converted into the format of the multiplexing method. For example, HEVC specifies a technology for storing coded data in a data structure called a NAL unit and storing the NAL unit in ISOBMFF.

On the other hand, currently, the first encoding method (Codec1) and the second encoding method (Codec2) are being considered as methods for encoding point cloud data, but the structure of the encoded data and the method for storing the encoded data in a system format have not been defined, which poses the issue that, as things stand, MUX processing (multiplexing), transmission, and storage in the encoding section are not possible.

In the following, unless a specific encoding method is specified, it refers to either the first encoding method or the second encoding method.

(Embodiment 2)
In this embodiment, the types of coded data (position information (Geometry), attribute information (Attribute), additional information (Metadata)) generated by the above-described first coding unit 4630 or second coding unit 4650, a method for generating the additional information (metadata), and multiplexing processing in the multiplexing unit will be described. Note that the additional information (metadata) may also be referred to as a parameter set or control information.

In this embodiment, we will use the dynamic object (three-dimensional point cloud data that changes over time) described in Figure 4 as an example, but a similar method can also be used in the case of a static object (three-dimensional point cloud data at any time).

Figure 24 is a diagram showing the configuration of the encoding unit 4801 and multiplexing unit 4802 included in the three-dimensional data encoding device according to this embodiment. The encoding unit 4801 corresponds to, for example, the first encoding unit 4630 or the second encoding unit 4650 described above. The multiplexing unit 4802 corresponds to the multiplexing unit 4634 or 4656 described above.

The encoding unit 4801 encodes point cloud data of multiple PCC (Point Cloud Compression) frames and generates encoded data (Multiple Compressed Data) of multiple position information, attribute information, and additional information.

The multiplexing unit 4802 converts data of multiple data types (position information, attribute information, and additional information) into NAL units, converting the data into a data structure that takes into account data access in the decoding device.

Figure 25 is a diagram showing an example of the structure of encoded data generated by the encoding unit 4801. The arrows in the diagram indicate dependencies related to the decoding of encoded data, with the source of the arrow depending on the data at the end of the arrow. In other words, the decoding device decodes the data at the end of the arrow and uses that decoded data to decode the data at the end of the arrow. In other words, dependency means that the data on which the dependency is based is referenced (used) in the processing (encoding, decoding, etc.) of the data on which the dependency is based.

First, we will explain the process of generating encoded data for position information. The encoding unit 4801 generates encoded position data (Compressed Geometry Data) for each frame by encoding the position information of each frame. Furthermore, the encoded position data is represented as G(i), where i indicates the frame number, the time of the frame, etc.

The encoding unit 4801 also generates a location parameter set (GPS(i)) corresponding to each frame. The location parameter set includes parameters that can be used to decode the encoded location data. Furthermore, the encoded location data for each frame depends on the corresponding location parameter set.

Also, encoded position data consisting of multiple frames is defined as a position sequence (Geometry Sequence). The encoding unit 4801 generates a position sequence parameter set (Geometry Sequence PS: also referred to as Position SPS) that stores parameters commonly used in the decoding process for multiple frames in the position sequence. The position sequence depends on the Position SPS.

Next, the process of generating encoded attribute data for attribute information will be described. The encoding unit 4801 generates encoded attribute data (Compressed Attribute Data) for each frame by encoding the attribute information of each frame. The encoded attribute data is represented by A(i). Figure 25 shows an example in which attribute X and attribute Y exist, and the encoded attribute data for attribute X is represented by AX(i) and the encoded attribute data for attribute Y is represented by AY(i).

The encoding unit 4801 also generates an attribute parameter set (APS(i)) corresponding to each frame. The attribute parameter set for attribute X is represented by AXPS(i), and the attribute parameter set for attribute Y is represented by AYPS(i). The attribute parameter set includes parameters that can be used to decode the encoded attribute information. The encoded attribute data depends on the corresponding attribute parameter set.

Also, encoded attribute data consisting of multiple frames is defined as an attribute sequence. The encoding unit 4801 generates an attribute sequence parameter set (Attribute Sequence PS: also referred to as attribute SPS) that stores parameters commonly used in the decoding process for multiple frames in the attribute sequence. The attribute sequence depends on the attribute SPS.

Also, in the first encoding method, the encoded attribute data depends on the encoded position data.

Figure 25 also shows an example where two types of attribute information (attribute X and attribute Y) exist. When there are two types of attribute information, for example, two encoding units generate respective data and metadata. Also, for example, an attribute sequence is defined for each type of attribute information, and an attribute SPS is generated for each type of attribute information.

Note that Figure 25 shows an example in which there is one type of position information and two types of attribute information, but this is not limited to this, and there may be one type of attribute information, or three or more types. In this case, encoded data can be generated using a similar method. Also, in the case of point cloud data that does not have attribute information, the attribute information may not be necessary. In that case, the encoding unit 4801 does not need to generate a parameter set related to the attribute information.

Next, the process of generating additional information (metadata) will be described. The encoding unit 4801 generates a PCC stream PS (also referred to as stream PS), which is a parameter set for the entire PCC stream. The encoding unit 4801 stores parameters in the stream PS that can be used in common for decoding processes for one or more position sequences and one or more attribute sequences. For example, the stream PS includes identification information indicating the codec for the point cloud data, information indicating the algorithm used for encoding, and the like. The position sequence and attribute sequence depend on the stream PS.

Next, we will explain access units and GOFs. In this embodiment, we introduce the new concepts of access units (AUs) and GOFs (Groups of Frames).

An access unit is a basic unit for accessing data during decoding, and is composed of one or more pieces of data and one or more pieces of metadata. For example, an access unit is composed of position information at the same time and one or more pieces of attribute information. A GOF is a random access unit and is composed of one or more access units.

The encoding unit 4801 generates an access unit header (AU Header) as identification information indicating the beginning of an access unit. The encoding unit 4801 stores parameters related to the access unit in the access unit header. For example, the access unit header includes the configuration or information of the encoded data included in the access unit. The access unit header also includes parameters commonly used for the data included in the access unit, such as parameters related to the decoding of the encoded data.

In addition, instead of an access unit header, the encoding unit 4801 may generate an access unit delimiter that does not include parameters related to the access unit. This access unit delimiter is used as identification information that indicates the start of the access unit. The decoding device identifies the start of the access unit by detecting the access unit header or access unit delimiter.

Next, we will explain how to generate identification information for the start of a GOF. The encoding unit 4801 generates a GOF header as identification information that indicates the start of a GOF. The encoding unit 4801 stores parameters related to the GOF in the GOF header. For example, the GOF header includes the structure or information of the encoded data included in the GOF. The GOF header also includes parameters that are commonly used for the data included in the GOF, such as parameters related to the decoding of the encoded data.

In addition, instead of a GOF header, the encoding unit 4801 may generate a GOF delimiter that does not include parameters related to the GOF. This GOF delimiter is used as identification information indicating the beginning of the GOF. The decoding device identifies the beginning of the GOF by detecting the GOF header or GOF delimiter.

In PCC encoded data, for example, an access unit is defined as a PCC frame. A decoding device accesses a PCC frame based on the identification information at the beginning of the access unit.

Also, for example, a GOF is defined as one random access unit. The decoding device accesses the random access unit based on the identification information at the beginning of the GOF. For example, if PCC frames are not dependent on each other and can be decoded independently, the PCC frames may be defined as random access units.

In addition, two or more PCC frames may be assigned to one access unit, and multiple random access units may be assigned to one GOF.

The encoding unit 4801 may also define and generate parameter sets or metadata other than those described above. For example, the encoding unit 4801 may generate SEI (Supplemental Enhancement Information) that stores parameters (optional parameters) that may not necessarily be used during decoding.

Next, we will explain the structure of encoded data and how encoded data is stored in NAL units.

For example, a data format is defined for each type of encoded data. Figure 26 shows an example of encoded data and NAL units.

For example, as shown in FIG. 26, the encoded data includes a header and a payload. The encoded data may also include length information indicating the length (amount of data) of the encoded data, header, or payload. The encoded data may also not include a header.

The header contains, for example, identification information to identify the data. This identification information indicates, for example, the data type or frame number.

The header contains, for example, identification information indicating the reference relationship. This identification information is stored in the header when, for example, there is a dependency between data, and is information used to refer to the referenced data from the reference source. For example, the header of the referenced data contains identification information to identify the data. The header of the reference source contains identification information indicating the referenced data.

In addition, if the reference destination or reference source can be identified or derived from other information, the identification information for identifying the data or the identification information indicating the reference relationship may be omitted.

The multiplexing unit 4802 stores the encoded data in the payload of the NAL unit. The NAL unit header includes pcc_nal_unit_type, which is identification information for the encoded data. Figure 27 shows an example of the semantics of pcc_nal_unit_type.

As shown in Figure 27, when pcc_codec_type is Codec 1 (Codec1: first encoding method), the values 0 to 10 of pcc_nal_unit_type correspond to the encoded position data (Geometry), encoded attribute X data (AttributeX), encoded attribute Y data (AttributeY), position PS (Geom.PS), attribute XPS (AttrX.PS), attribute YPS (AttrX.PS), position SPS (Geometry Sequence PS), attribute XSPS (AttributeX Sequence PS), attribute YSPS (AttributeY Sequence PS), AU header (AU Header), and GOF header (GOF Values 11 and above are assigned as spares for Codec 1.

When pcc_codec_type is Codec 2 (Codec2: second encoding method), pcc_nal_unit_type values 0 to 2 are assigned to codec data A (DataA), metadata A (MetaDataA), and metadata B (MetaDataB). Values 3 and above are assigned as spares for Codec 2.

(Embodiment 3)
In the three-dimensional data encoding method according to the third embodiment, position information of a plurality of three-dimensional points is encoded using a prediction tree generated based on the position information.

Figure 28 is a diagram showing an example of a prediction tree used in a three-dimensional data encoding method according to embodiment 3. Figure 29 is a flowchart showing an example of a three-dimensional data encoding method according to embodiment 3. Figure 30 is a flowchart showing an example of a three-dimensional data decoding method according to embodiment 3.

As shown in Figures 28 and 29, in the three-dimensional data encoding method, a prediction tree is generated using multiple three-dimensional points, and then the node information contained in each node of the prediction tree is encoded. This results in a bitstream containing the encoded node information. Each piece of node information is, for example, information about one node of the prediction tree. Each piece of node information includes, for example, the position information of the node, the index of the node, the number of child nodes the node has, the prediction mode used to encode the position information of the node, and the prediction residual.

Also, as shown in Figures 28 and 30, in the three-dimensional data decoding method, each encoded node information contained in the bit stream is decoded, and then the position information is decoded while generating a prediction tree.

Next, we will explain how to generate a prediction tree using Figure 31.

Figure 31 is a diagram illustrating a method for generating a prediction tree in embodiment 3.

In the prediction tree generation method, as shown in (a) of Figure 31, the three-dimensional data encoding device first adds point 0 as the initial point of the prediction tree. The position information of point 0 is represented by coordinates including three elements: (x0, y0, z0). The position information of point 0 may be represented by coordinates in a three-axis Cartesian coordinate system or by coordinates in a polar coordinate system.

child_count is incremented by +1 each time a child node is added to the node for which child_count is set. After the prediction tree is generated, the child_count of each node indicates the number of child nodes that each node has, and is added to the bitstream. pred_mode indicates the prediction mode used to predict the value of the position information of each node. Details of prediction modes will be described later.

Next, as shown in (b) of Figure 31, the three-dimensional data encoding device adds point 1 to the prediction tree. At this time, the three-dimensional data encoding device may search for the closest point to point 1 from the group of points already added to the prediction tree, and add point 1 as a child node of that closest point. The position information of point 1 is represented by coordinates including three elements: (x1, y1, z1). The position information of point 1 may be represented by coordinates in a three-axis Cartesian coordinate system, or by coordinates in a polar coordinate system. In the case of Figure 31, point 0 is the closest point to point 1, and point 1 is added as a child node of point 0. Then, the three-dimensional data encoding device increments the value represented by child_count of point 0 by 1.

Note that the predicted value of the position information of each node may be calculated when the node is added to the prediction tree. For example, in the case of (b) in Figure 31, the three-dimensional data encoding device may add point 1 as a child node of point 0 and calculate the position information of point 0 as the predicted value. In this case, pred_mode may be set to 1. pred_mode is prediction mode information (prediction mode value) indicating the prediction mode. Furthermore, after calculating the predicted value, the three-dimensional data encoding device may calculate the residual_value (prediction residual) of point 1. Here, residual_value is the difference value obtained by subtracting the predicted value calculated in the prediction mode indicated by pred_mode from the position information of each node. In this way, the three-dimensional data encoding method can improve encoding efficiency by encoding the difference value from the predicted value rather than the position information itself.

Next, as shown in (c) of Figure 31, the three-dimensional data encoding device adds point 2 to the prediction tree. At this time, the three-dimensional data encoding device may search for the closest point to point 2 from the group of points already added to the prediction tree, and add point 2 as a child node of that closest point. The position information of point 2 is represented by coordinates including three elements: (x2, y2, z2). The position information of point 2 may be represented by coordinates in a three-axis Cartesian coordinate system, or by coordinates in a polar coordinate system. In the case of Figure 31, point 1 is the closest point to point 2, and point 2 is added as a child node of point 1. Then, the three-dimensional data encoding device increments the value represented by child_count of point 1 by 1.

Next, as shown in (d) of Figure 31, the three-dimensional data encoding device adds point 3 to the prediction tree. At this time, the three-dimensional data encoding device may search for the closest point to point 3 from the group of points already added to the prediction tree, and add point 3 as a child node of that closest point. The position information of point 3 is represented by coordinates including three elements: (x3, y3, z3). The position information of point 3 may be represented by coordinates in a three-axis Cartesian coordinate system, or by coordinates in a polar coordinate system. In the case of Figure 31, point 0 is the closest point to point 3, and point 3 is added as a child node of point 0. Then, the three-dimensional data encoding device increments the value represented by child_count of point 0 by 1.

In this way, the three-dimensional data encoding device adds all points to the prediction tree and completes the generation of the prediction tree. When the generation of the prediction tree is complete, the node with child_count = 0 ultimately becomes the leaf of the prediction tree. After the generation of the prediction tree is complete, the three-dimensional data encoding device encodes the child_count, pred_mode, and residual_value of each node selected in depth priority order from the root node. In other words, when the three-dimensional data encoding device selects a node in depth priority order, it selects an unselected child node from one or more child nodes of the selected node as the next node of the selected node. If the selected node does not have a child node, the three-dimensional data encoding device selects another unselected child node of the parent node of the selected node.

The encoding order is not limited to depth-first order, and may be width-first order, for example. When selecting a node in breadth-first order, the three-dimensional data encoding device selects an unselected node from among one or more nodes at the same depth (layer) as the selected node as the next node after the selected node. If there is no node at the same depth as the selected node, the three-dimensional data encoding device selects an unselected node from among one or more nodes at the next depth.

Note that points 0 to 3 are examples of multiple three-dimensional points.

In the above three-dimensional data encoding method, child_count, pred_mode, and residual_value are calculated when each point is added to the prediction tree, but this is not necessarily limited to this; for example, they may be calculated after the prediction tree has been generated.

The input order of multiple 3D points to the 3D data encoding device may be determined by sorting the input 3D points in ascending or descending Morton order and processing them in order, starting with the first 3D point. This allows the 3D data encoding device to efficiently search for the nearest neighbor of the 3D point being processed, improving encoding efficiency. Alternatively, the 3D data encoding device may process the 3D points in the order they are input without sorting them. For example, the 3D data encoding device may generate a prediction tree without branches based on the input order of multiple 3D points. Specifically, the 3D data encoding device may add the 3D point that is input after the first 3D point in the input order of multiple 3D points as a child node of a given 3D point.

Next, a first example of a prediction mode will be described using Figure 32. Figure 32 is a diagram for explaining a first example of a prediction mode according to embodiment 3. Figure 32 is a diagram showing a portion of a prediction tree.

Eight prediction modes may be set, as shown below. For example, as shown in Figure 32, the case of calculating the predicted value of point c will be described as an example. In the prediction tree, it is shown that the parent node of point c is point p0, the grandparent node of point c is point p1, and the great-grandparent node of point c is point p2. Note that points c, p0, p1, and p2 are examples of multiple three-dimensional points.

A prediction mode with a prediction mode value of 0 (hereinafter referred to as prediction mode 0) may be set to no prediction. In other words, in prediction mode 0, the three-dimensional data encoding device may calculate the position information of the input point c as the predicted value of that point c.

In addition, a prediction mode with a prediction mode value of 1 (hereinafter referred to as prediction mode 1) may be set to differential prediction with respect to point p0. In other words, the three-dimensional data encoding device may calculate the position information of point p0, which is the parent node of point c, as the predicted value of point c.

Furthermore, a prediction mode with a prediction mode value of 2 (hereinafter referred to as prediction mode 2) may be set to linear prediction using points p0 and p1. In other words, the three-dimensional data encoding device may calculate the predicted value of point c as the prediction result of linear prediction using the position information of point p0, which is the parent node of point c, and the position information of point p1, which is the grandparent node of point c. Specifically, the three-dimensional data encoding device calculates the predicted value of point c in prediction mode 2 using the following formula T1:

Predicted value = 2 × p0 - p1 (Equation T1)
In the formula T1, p0 indicates the position information of the point p0, and p1 indicates the position information of the point p1.

Furthermore, a prediction mode with a prediction mode value of 3 (hereinafter referred to as prediction mode 3) may be set to parallelogram prediction using points p0, p1, and p2. In other words, the three-dimensional data encoding device may calculate the predicted value of point c as the result of parallelogram prediction using the position information of point p0, which is the parent node of point c, the position information of point p1, which is the grandparent node of point c, and the position information of point p2, which is the great-grandparent node of point c. Specifically, the three-dimensional data encoding device calculates the predicted value of point c in prediction mode 3 using the following formula T2:

Predicted value = p0 + p1 - p2 (Equation T2)

In equation T2, p0 indicates the position information of point p0, p1 indicates the position information of point p1, and p2 indicates the position information of point p2.

In addition, a prediction mode with a prediction mode value of 4 (hereinafter referred to as prediction mode 4) may be set to differential prediction with respect to point p1. In other words, the three-dimensional data encoding device may calculate the position information of point p1, which is the grandparent node of point c, as the predicted value of point c.

In addition, a prediction mode with a prediction mode value of 5 (hereinafter referred to as prediction mode 5) may be set to differential prediction with respect to point p2. In other words, the three-dimensional data encoding device may calculate the position information of point p2, which is the great-grandfather node of point c, as the predicted value of point c.

Furthermore, a prediction mode with a prediction mode value of 6 (hereinafter referred to as prediction mode 6) may be set to the average of the position information of two or more of points p0, p1, and p2. In other words, the three-dimensional data encoding device may calculate the predicted value of point c as the average of two or more of the position information of point p0, which is the parent node of point c, the position information of point p1, which is the grandparent node of point c, and the position information of point p2, which is the great-grandparent node of point c. For example, when the three-dimensional data encoding device uses the position information of point p0 and the position information of point p1 to calculate the predicted value, it calculates the predicted value of point c in prediction mode 6 using the following formula T3:

Predicted value = (p0 + p1)/2 (Equation T3)

In equation T3, p0 represents the position information of point p0, and p1 represents the position information of point p1.

Furthermore, a prediction mode with a prediction mode value of 7 (hereinafter referred to as prediction mode 7) may be set to nonlinear prediction using the distance d0 between points p0 and p1 and the distance d1 between points p2 and p1. In other words, the three-dimensional data encoding device may calculate the prediction result of nonlinear prediction using the distance d0 and the distance d1 as the predicted value of point c.

Note that the prediction methods assigned to each prediction mode are not limited to the above example. Furthermore, the above eight prediction modes and the above eight prediction methods do not have to be combined as described above, and any combination is possible. For example, when encoding prediction modes using entropy coding such as arithmetic coding, a frequently used prediction method may be assigned to prediction mode 0. This improves encoding efficiency. Furthermore, the three-dimensional data encoding device may improve encoding efficiency by dynamically changing the assignment of prediction modes according to the frequency of use of prediction modes as the encoding process progresses. For example, the three-dimensional data encoding device may count the frequency of use of each prediction mode during encoding, and assign prediction modes indicated by smaller values to more frequently used prediction methods. This improves encoding efficiency. Note that M is the number of prediction modes, indicating the number of prediction modes. In the above example, there are eight prediction modes, prediction modes 0 to 7, so M = 8.

The three-dimensional data encoding device may calculate a predicted value (px,py,pz) of the position information (x,y,z) of a three-dimensional point to be encoded using the position information of three-dimensional points that are close to the three-dimensional point to be encoded among the three-dimensional points surrounding the three-dimensional point to be encoded. The three-dimensional data encoding device may also add prediction mode information (pred_mode) to each three-dimensional point, allowing the predicted value to be calculated to be selected according to the prediction mode.

For example, in a total of M prediction modes, the position information of the nearest three-dimensional point p0 could be assigned to prediction mode 0, ..., the position information of three-dimensional point p2 could be assigned to prediction mode M-1, and the prediction mode used for prediction could be added to the bitstream for each three-dimensional point.

The number of prediction modes M may be added to the bitstream. Alternatively, the number of prediction modes M may not be added to the bitstream, but may have a value specified in the profile, level, etc. of the standard. Alternatively, the number of prediction modes M may be a value calculated from the number of three-dimensional points N used for prediction. For example, the number of prediction modes M may be calculated as M = N + 1.

Figure 33 shows a second example of a table showing predicted values calculated in each prediction mode in embodiment 3.

The table shown in Figure 33 is an example where the number of three-dimensional points used for prediction N = 4 and the number of prediction modes M = 5.

In the second example, the predicted value of the position information of point c is calculated using the position information of at least one of points p0, p1, and p2. A prediction mode is added to each three-dimensional point to be encoded. The predicted value is calculated to a value according to the added prediction mode.

Figure 34 is a diagram showing a specific example of a second example of a table showing predicted values calculated in each prediction mode in embodiment 3.

The three-dimensional data encoding device may, for example, select prediction mode 1 and encode the position information (x, y, z) of the three-dimensional point to be encoded using the respective predicted values (p0x, p0y, p0z). In this case, a prediction mode value of "1" indicating the selected prediction mode 1 is added to the bitstream.

In this way, when selecting a prediction mode, the three-dimensional data encoding device may select a prediction mode that is common to the three elements as one prediction mode for calculating predicted values for each of the three elements included in the position information of the three-dimensional point to be encoded.

Figure 35 is a diagram showing a third example of a table showing predicted values calculated in each prediction mode in embodiment 3.

The table shown in Figure 35 is an example where the number of three-dimensional points used for prediction N = 2 and the number of prediction modes M = 5.

In the third example, the predicted value of the position information of point c is calculated using the position information of at least one of points p0 and p1. A prediction mode is assigned to each three-dimensional point to be encoded. The predicted value is calculated to a value corresponding to the assigned prediction mode.

Note that, as in the third example, if the number of points surrounding point c (number of adjacent points) is less than three, a prediction mode to which a predicted value has not been assigned may be set to "not available." Furthermore, when a prediction mode to which "not available" is set occurs, a different prediction method may be assigned to that prediction mode. For example, the position information of point p2 may be assigned as a predicted value to that prediction mode. Furthermore, a predicted value assigned to another prediction mode may be assigned to that prediction mode. For example, the position information of point p1 assigned to prediction mode 4 may be assigned to prediction mode 3 to which "not available" is set. At that time, the position information of point p2 may be newly assigned to prediction mode 4. In this way, when a prediction mode to which "not available" is set occurs, encoding efficiency can be improved by assigning a new prediction method to that prediction mode.

Figure 36 shows an example of the syntax of a location information header. NumNeighborPoint, NumPredMode, Thfix, QP, and unique_point_per_leaf in the syntax of Figure 36 will be explained in order.

NumNeighborPoint indicates the upper limit of the number of surrounding points used to generate a predicted value of the position information of a three-dimensional point. If the number of surrounding points M is less than NumNeighborPoint (M < NumNeighborPoint), the predicted value may be calculated using M surrounding points in the calculation process.

NumPredMode indicates the total number M of prediction modes used to predict position information. Note that the maximum possible value of the number of prediction modes, MaxM, may be specified by standards, etc. The three-dimensional data encoding device may add the value (MaxM-M) (0<M<=MaxM) to the header as NumPredMode, and then binarize and encode (MaxM-1) using a truncated unary code. Furthermore, the number of prediction modes, NumPredMode, does not need to be added to the bitstream, and its value may be specified by a profile or level, etc., of standards, etc. The number of prediction modes may also be specified as NumNeighborPoint + NumPredMode.

Thfix is a threshold value used to determine whether to fix the prediction mode. The distance d0 between points p1 and p0 used for prediction and the distance d1 between points p2 and p1 are calculated, and if the absolute difference distdiff = |d0-d1| is smaller than the threshold Thfix[i], the prediction mode is fixed to α. α is the prediction mode used to calculate a predicted value using linear prediction, and is set to "2" in the above embodiment. Note that Thfix does not need to be added to the bitstream, and its value may be specified in the profile or level of a standard, etc.

QP indicates the quantization parameter used when quantizing the position information. The three-dimensional data encoding device may calculate a quantization step from the quantization parameter and quantize the position information using the calculated quantization step.

unique_point_per_leaf is information that indicates whether or not the bitstream contains duplicate points (points with the same position information). unique_point_per_leaf = 1 indicates that there are no duplicate points in the bitstream. unique_point_per_leaf = 0 indicates that there is one or more duplicate points in the bitstream.

In this embodiment, the determination of whether to fix the prediction mode is made using the absolute difference between distance d0 and distance d1, but this is not necessarily limited to this, and any method of determination may be used. For example, this determination may be made by calculating the distance d0 between point p1 and point p0, and if distance d0 is greater than a threshold, determining that point p1 cannot be used for prediction and fixing the prediction mode value to "1" (predicted value p0); otherwise, setting a prediction mode. This makes it possible to improve coding efficiency while reducing overhead.

The above NumNeighborPoint, NumPredMode, Thfix, and unique_point_per_leaf may be entropy coded and added to the header. For example, each value may be binarized and computationally coded. Each value may also be coded at a fixed length to reduce the amount of processing.

Figure 37 shows an example of the syntax for location information. NumOfPoint, child_count, pred_mode, and residual_value[j] in the syntax of Figure 37 will be explained in order.

NumOfPoints indicates the total number of 3D points contained in the bitstream.

child_count indicates the number of child nodes that the i-th 3D point (node[i]) has.

pred_mode indicates the prediction mode for encoding or decoding the position information of the i-th 3D point. pred_mode takes on values from 0 to M-1 (M is the total number of prediction modes). If pred_mode is not present in the bitstream (if the condition distdiff >= Thfix[i] && NumPredMode > 1 is not satisfied), pred_mode may be estimated to a fixed value α. α is the prediction mode used to calculate a predicted value using linear prediction, and is "2" in the above embodiment. Note that α is not limited to "2," and any value between 0 and M-1 may be set as the estimated value. Furthermore, if pred_mode is not present in the bitstream, the estimated value may be added separately to a header, etc. Also, pred_mode may be binarized and arithmetically coded with a truncated unary code using the number of prediction modes to which the predicted value is assigned.

Note that when NumPredMode = 1, that is, when the number of prediction modes is 1, the 3D data encoding device may generate a bitstream that does not include a prediction mode value without encoding a prediction mode value that indicates the prediction mode. Furthermore, when the 3D data decoding device acquires a bitstream that does not include a prediction mode value, it may calculate a prediction value of a specific prediction mode when calculating a prediction value. The specific prediction mode is a predetermined prediction mode.

residual_value[j] indicates the coded data of the prediction residual between the predicted value of the position information. residual_value[0] may indicate element x of the position information, residual_value[1] may indicate element y of the position information, and residual_value[2] may indicate element z of the position information.

Figure 38 is a diagram showing another example of location information syntax. The example in Figure 38 is a modified example of the example in Figure 37.

pred_mode may indicate the prediction mode for each of the three elements of position information (x, y, z), as shown in Figure 38. That is, pred_mode[0] indicates the prediction mode for element x, pred_mode[1] indicates the prediction mode for element y, and pred_mode[2] indicates the prediction mode for element z. pred_mode[0], pred_mode[1], and pred_mode[2] may be added to the bitstream.

(Embodiment 4)
In this embodiment, inter prediction for position information (octree) of a point cloud will be described. Fig. 39 is a block diagram of a three-dimensional data encoding device 12800 according to this embodiment. Note that while Fig. 39 illustrates a processing unit related to encoding position information (geometry) of a point cloud, the three-dimensional data encoding device 12800 may also include other processing units, such as a processing unit that encodes attribute information of the point cloud. In inter prediction, a point cloud to be encoded is encoded while referring to an already-encoded point cloud.

The three-dimensional data encoding device 12800 comprises an octree conversion unit 12801, a buffer 12802, an entropy encoding unit 12803, a buffer 12804, a buffer 12805, a point group conversion unit 12806, a buffer 12807, a motion detection and compensation unit 12808, an octree conversion unit 12809, a buffer 12810, and a control unit 12811.

The octree conversion unit 12801 converts the input target point cloud, which is the data of the point cloud to be encoded, into an octree representation, thereby generating a target octree in which the position information of the target point cloud is expressed using an octree. In the input target point cloud, the positions of the point cloud are expressed, for example, using three-dimensional coordinates (e.g., x, y, z). The buffer 12802 stores the generated target octree. The octree is composed of multiple nodes (branching points), and the information for each node includes an 8-bit occupancy code indicating whether each of the node's eight child nodes contains a three-dimensional point. For example, the buffer 12802 may initialize the data stored for each octree (target point cloud).

The entropy coding unit 12803 generates a bitstream by entropy coding information for each node (e.g., occupancy code). In this entropy coding, probability parameters (also called coding tables or probability tables) are controlled based on information about coded nodes (intra-reference nodes) within the target point cloud or information about nodes (inter-reference nodes) within the coded point cloud.

Buffer 12804 stores information about the target node (e.g., occupancy code) as an intra-reference node (encoded node). For example, buffer 12804 may initialize the data it stores for each octree (target point group).

Buffer 12805 stores information about the target node (e.g., occupancy code). Buffer 12805 also stores information about the target node in octree units as an encoded octree. For example, buffer 12805 may initialize the data stored for each octree (target point group).

The point group generation unit 12806 generates an inter-reference point group (encoded point group) by converting the encoded octree into a point group. The buffer 12807 stores the inter-reference point group. In other words, the buffer 12807 stores multiple inter-reference point groups, which are one or more encoded point groups.

The motion detection and compensation unit 12808 detects the displacement between the inter reference point group and the target point group (motion detection), and corrects the inter reference point group based on the detected displacement (motion compensation), thereby generating a post-alignment point group, which is the inter reference point group after alignment.

The octree conversion unit 12809 converts the aligned point cloud into an octree representation to generate an inter-reference octree in which the position information of the aligned point cloud is expressed as an octree. The buffer 12810 stores the generated inter-reference octree. Furthermore, for example, the buffer 12810 may initialize the data stored for each octree (target point cloud).

The three-dimensional data encoding device 12800 may perform motion detection and motion compensation on a frame or octree basis, or on a node (point) basis. The three-dimensional data encoding device 12800 may also write information related to motion compensation, such as motion vectors, in the header section of the frame or octree, or may entropy-encode the information and then write it in the header section of the node information.

Furthermore, the inter-reference point group may be a point group contained in an already coded frame different from the frame to be coded, or may be an already coded point group contained in the same frame as the frame to be coded.

The control unit 12811 controls the probability parameters used by the entropy coding unit 12803 for entropy coding (arithmetic coding) of the target node using the intra reference node stored in buffer 12804 or the inter reference node included in the inter reference octree stored in buffer 12810. Whether control of the probability parameters using the intra reference node (hereinafter referred to as intra reference) or control of the probability parameters using the inter reference node (hereinafter referred to as inter reference) is used may be determined in advance, for example, on a frame or point cloud basis, or may be determined by any method. For example, the actual amount of coding may be estimated, and the reference method (intra reference or inter reference) that results in the least amount of coding may be selected.

For example, when intra-referencing is used, a probability parameter is selected from multiple probability parameters based on the occupancy status (whether the node contains a point) of multiple adjacent nodes (intra-reference nodes) of the target node. When inter-referencing is used, a probability parameter is selected from multiple probability parameters based on the occupancy status of a node (inter-reference node) that is located at the same position as the target node and at least one of the multiple adjacent nodes included in the inter-reference octree. When inter-referencing is selected, the probability parameter may be controlled by combining inter-referencing and intra-referencing. The multiple probability parameters may include a probability parameter that is updated according to the frequency of occurrence, or may include a fixed value.

In this way, the three-dimensional data encoding device 12800 can improve the prediction accuracy of the occurrence probability of the information of the target node by controlling the probability parameters of entropy encoding based on information of the inter-reference node as well as information of the intra-reference node. This may result in improved encoding efficiency.

The three-dimensional data encoding device 12800 does not need to constantly refer to the inter-reference point group, but may instead encode the target point group based only on the target point group information by clearing the buffer 12807 storing the inter-reference point group at a predetermined time interval (e.g., every second), a predetermined frame interval (e.g., every 30 frames), or at any timing notified to the three-dimensional data decoding device. This makes it possible for the three-dimensional data decoding device to jump in and start playback from a point group other than the beginning of the bitstream that does not reference the inter-reference point group. This potentially improves the random accessibility and error resilience of the bitstream.

Figure 40 is a block diagram of a three-dimensional data decoding device 12820 according to this embodiment. Note that while Figure 40 describes a processing unit related to decoding position information (geometry) of point clouds, the three-dimensional data decoding device 12820 may also include other processing units, such as a processing unit that decodes attribute information of point clouds. The three-dimensional data decoding device 12820 performs inter-prediction decoding, which decodes point clouds from an encoded bitstream while referencing the encoded point clouds. For example, the three-dimensional data decoding device 12820 decodes a bitstream generated by the three-dimensional data encoding device 12800 shown in Figure 39.

The three-dimensional data decoding device 12820 includes an entropy decoding unit 12821, a buffer 12822, a buffer 12823, a point group generation unit 12824, a buffer 12825, a motion compensation unit 12826, an octree generation unit 12827, a buffer 12828, and a control unit 12829.

The entropy decoding unit 12821 generates decoded node information (e.g., occupancy code) by entropy decoding the input bitstream for each branch point (node) of the octree. In this entropy decoding, probability parameters (also called coding tables or probability tables) are controlled based on information on decoded nodes (intra-reference nodes) within the target point cloud or information on nodes (inter-reference nodes) within the decoded point cloud.

Buffer 12822 stores information about the generated decoded nodes as intra reference nodes (decoded nodes). For example, buffer 12822 may initialize the data it stores for each octree (decoded point group).

Buffer 12823 stores information about the decoding nodes (e.g., occupancy codes). Buffer 12823 also stores information about the decoding nodes in octree units as a decoding octree. For example, buffer 12823 may initialize the data stored for each octree (decoding point cloud). Point cloud generation unit 12824 generates a decoded point cloud by converting the decoded octree into a point cloud.

The buffer 12825 stores the decoded point group as an inter reference point group. The motion compensation unit 12826 corrects (motion compensates) the displacement between the inter reference point group and the point group to be decoded, thereby generating an aligned point group, which is the inter reference point group after alignment. For example, the motion compensation unit 12826 obtains information related to motion compensation, such as motion vectors, from the header section of a frame or octree, or the header section of node information, and performs motion compensation using the obtained information.

The octree conversion unit 12827 converts the aligned point cloud into an octree representation to generate an inter-reference octree in which the position information of the aligned point cloud is expressed as an octree. The buffer 12828 stores the generated inter-reference octree. Furthermore, for example, the buffer 12828 may initialize the data stored for each octree (decoded point cloud).

In addition, the 3D data decoding device 12820 may perform motion compensation on a frame or octree basis, or on a node (point) basis.

Furthermore, the inter-reference point group may be a point group contained in a decoded frame different from the frame to be decoded, or a decoded point group contained in the same frame as the frame to be decoded.

The control unit 12829 controls the probability parameters used by the entropy decoding unit 12821 for entropy decoding (arithmetic decoding) of the target node, using the intra reference node stored in buffer 12822 or the inter reference node included in the inter reference octree stored in buffer 12828. Whether intra reference or inter reference is used may be determined, for example, based on control information included in the bitstream, may be predetermined on a frame or point cloud basis, or may be determined by any method.

For example, when intra-referencing is used, the probability parameter is selected based on the occupancy state (whether the node contains a point) of multiple adjacent nodes (intra-reference nodes) of the target node. Also, when inter-referencing is used, the probability parameter is selected based on the occupancy state of a node (inter-reference node) that is in the same position as the target node and at least one of the multiple adjacent nodes included in the inter-reference octree. Note that when inter-referencing is selected, the probability parameter may be controlled by combining inter-referencing and intra-referencing.

In this way, the three-dimensional data decoding device 12820 can control the probability parameters of entropy decoding based on information on inter-reference nodes as well as information on intra-reference nodes, thereby decoding a point cloud from an encoded bit stream (for example, a bit stream output from the three-dimensional data encoding device 12800 shown in Figure 39) while referring to an already encoded point cloud.

The three-dimensional data decoding device 12820 does not need to constantly refer to the inter-reference point group, but may decode the point group to be decoded based only on the information of the point group to be decoded, for example, by clearing the buffer 12825 storing the inter-reference point group at a predetermined time interval (e.g., every second), a predetermined frame interval (e.g., every 30 frames), or at any timing notified by the three-dimensional data encoding device, in accordance with the three-dimensional data encoding device. This allows the three-dimensional data decoding device 12820 to realize jump playback start from a point group other than the beginning of the bitstream that does not reference the inter-reference point group.

Figure 41 is a block diagram of a three-dimensional data encoding device 12800A, which is a modified example of the three-dimensional data encoding device 12800. The three-dimensional data encoding device 12800A shown in Figure 41 further includes a motion compensation unit 12812 in addition to the three-dimensional data encoding device 12800 shown in Figure 39.

The motion compensation unit 12812 performs motion compensation on the encoded point cloud generated by the point cloud generation unit 12806, thereby aligning it with the inter reference point cloud already stored in the buffer 12807. The buffer 12807 updates the inter reference point cloud it stores by integrating the motion-compensated encoded point cloud with the inter reference point cloud already stored. This makes it possible to use a dense point cloud, in which point clouds from multiple frames are superimposed, as the inter reference point cloud. Other processing is similar to that of, for example, the three-dimensional data encoding device 12800.

The inter-reference point group may be a point group contained in an already coded frame different from the frame to be coded, or it may be an already coded point group contained in the same frame as the frame to be coded.

In this way, the three-dimensional data encoding device 12800A may be able to improve the point cloud density of the inter-reference point cloud by aligning and integrating encoded point clouds. This improves the prediction accuracy of the occurrence probability of information for the target node, potentially further improving encoding efficiency.

The three-dimensional data encoding device 12800A does not need to reference all encoded point groups as inter-reference point groups. It may instead encode the target point group based on only the target point group, or on the target point group and some of the encoded point groups, by clearing all or part of the buffer 12807 storing the inter-reference point group at a predetermined time interval (e.g., every second), a predetermined frame interval (e.g., every five frames), or at any timing notified to the three-dimensional data decoding device. When encoding is performed based on only the target point group, the three-dimensional data decoding device can jump in and start playback from a point group other than the beginning of the bitstream that does not reference the inter-reference point group. This may improve the random accessibility and error resilience of the bitstream. Furthermore, when encoding is performed based on the target point group and some of the encoded point groups, the capacity of the buffer 12807 storing the inter-reference point group can be reduced, potentially reducing the implementation costs of the three-dimensional data encoding device and the three-dimensional data decoding device.

Figure 42 is a block diagram of a three-dimensional data decoding device 12820A, which is a modified example of the three-dimensional data decoding device 12820. The three-dimensional data decoding device 12820A shown in Figure 42 further comprises a motion compensation unit 12830 in addition to the three-dimensional data decoding device 12820 shown in Figure 40. For example, the three-dimensional data decoding device 12820A decodes a point cloud from the bitstream generated by the three-dimensional data encoding device 12800A shown in Figure 41.

The motion compensation unit 12830 performs motion compensation on the decoded point group to align it with the inter reference point group already stored in the buffer 12825. The buffer 12825 updates the stored inter reference point group by integrating the motion-compensated decoded point group with the already stored inter reference point group. This makes it possible to use a dense point group obtained by overlapping point groups from multiple frames as the inter reference point group. Other processing is similar to that of, for example, the 3D data decoding device 12820.

Note that the inter-reference point group may be a point group contained in a decoded frame different from the frame to be decoded, or a decoded point group contained in the same frame as the frame to be decoded.

In this way, the three-dimensional data decoding device 12820A has a configuration that aligns and integrates decoded point clouds, and can decode point clouds from a bit stream encoded by a three-dimensional data encoding device having a similar configuration (for example, a bit stream generated by the three-dimensional data encoding device 12800A shown in Figure 41).

In addition, the three-dimensional data decoding device 12820A does not need to refer to all decoded point groups as inter-reference point groups, and may decode the point group to be decoded based on information on only the point group to be decoded, or on the point group to be decoded and some of the decoded point groups, by clearing all or part of the buffer 12825 storing the inter-reference point group at a predetermined time interval (e.g., every second), a predetermined frame interval (e.g., every five frames), or at any timing notified by the three-dimensional data encoding device.

When the three-dimensional data decoding device 12820A performs decoding based only on information about the point group to be decoded, it can realize jump-start playback from a point group other than the beginning of the bitstream that does not reference the inter-reference point group. This has the potential to improve the random accessibility and error resilience of the bitstream. Furthermore, when the three-dimensional data decoding device performs decoding based on information about the point group to be decoded and some of the decoded point groups, it can reduce the capacity of the buffer 12825 that holds the inter-reference point group. This has the potential to reduce the implementation costs of the three-dimensional data encoding device and the three-dimensional data decoding device.

Figure 43 shows an example of inter prediction in the 3D data encoding device shown in Figures 39 and 41. Note that the same applies to inter prediction in the 3D data decoding device shown in Figures 40 and 42.

As shown in FIG. 43, for example, the three-dimensional data encoding device sets a first rectangular parallelepiped containing the target point cloud. The three-dimensional data encoding device sets a second rectangular parallelepiped obtained by translating the first rectangular parallelepiped. The second rectangular parallelepiped is a space containing an encoded point cloud that is referenced when encoding the target point cloud. In addition, the three-dimensional data encoding device may write the x, y, and z components of the translation distance between the first rectangular parallelepiped and the second rectangular parallelepiped as motion vector information in the header section of the frame or octree, or may entropy-code the information and then write it in the header section of the node information.

Note that here we have shown an example of setting a space containing an encoded point cloud to be referenced when encoding a target point cloud by parallel translation, but any other method can be used as long as it can uniquely set a space containing an encoded point cloud to be referenced.

Next, an example of header information will be described. Figure 44 is a diagram showing an example of the syntax of a sequence parameter set (SPS) included in a bitstream. SPS is control information common to multiple frames, multiple point clouds, or multiple slices, and is control information common to attribute information and position information.

As shown in FIG. 44, the SPS includes sps_inter_prediction_enabled_flag and sps_max_num_ref_frames_minus1.

Below are example semantics of sequence parameter sets: sps_inter_prediction_enabled_flag equal to 1 specifies that the use of inter prediction is allowed for bitstreams that reference SPS. sps_inter_prediction_enabled_flag equal to 0 specifies that inter prediction is disabled for bitstreams that reference SPS.

sps_max_num_ref_frames_minus1+1 (sps_max_num_ref_frames_minus1 plus 1) specifies the maximum number of reference point cloud frames referenced by a frame. The value of sps_max_num_ref_frames_minus1 must be in the range of 0 to MaxNumRefFrames-1.

sps_max_num_ref_frames_minus1 is included in the SPS if sps_inter_prediction_enabled_flag is 1, and is not included in the SPS if sps_inter_prediction_enabled_flag is 0.

Figure 45 shows an example syntax of the location information parameter set (GPS) included in the bitstream. GPS is control information common to multiple frames, multiple point clouds, or multiple slices, and is control information for location information.

As shown in Figure 45, GPS includes gps_inter_prediction_enabled_flag and gps_num_ref_frames_minus1.

Below is an example of the semantics of the location information parameter set. gps_inter_prediction_enabled_flag equal to 1 specifies that the use of inter prediction is allowed in the decoding process of location information data units of bitstreams that reference GPS. gps_inter_prediction_enabled_flag equal to 0 specifies that inter prediction is disabled in the decoding process of location information data units of bitstreams that reference GPS. If sps_inter_prediction_enabled_flag is 0, then gps_inter_prediction_enabled_flag is 0.

gps_num_ref_frames_minus1+1 (the value of gps_num_ref_frames_minus1 plus 1) specifies the number of reference point cloud frames referenced in the GPS reference frame. The value of gps_num_ref_frames_minus1 must be within the range of 0 to sps_max_num_ref_frames_minus1.

gps_num_ref_frames_minus1 is included in GPS if gps_inter_prediction_enabled_flag is 1, and is not included in GPS if gps_inter_prediction_enabled_flag is 0.

As shown in these examples, the three-dimensional data encoding device may notify the three-dimensional data decoding device of information indicating whether inter-prediction coding is permitted, such as sps_inter_prediction_enabled_flag and gps_inter_prediction_enabled_flag, in the sequence parameter set and position information parameter set. Furthermore, when notifying the three-dimensional data decoding device of information indicating that inter-prediction coding is permitted, the three-dimensional data encoding device may notify the three-dimensional data decoding device of information regarding the number of frames to reference in inter-prediction coding or its maximum value, such as sps_max_num_ref_frames_minus1 and gps_num_ref_frames_minus1.

In addition, MaxNumRefFrames is a fixed value set as a requirement that the three-dimensional data decoding device must satisfy, and may be set to a number of frames, such as six frames, but it may also be set to a larger value as long as the same value is used for processing in both the three-dimensional data encoding device and the three-dimensional data decoding device.

By communicating this information from the three-dimensional data encoding device to the three-dimensional data decoding device, it may be possible to optimize the allocation of memory used for processing in the three-dimensional data decoding device.

In addition, the information indicating whether or not the implementation of the above-mentioned inter-prediction coding is permitted, and information regarding the number of frames to be referenced in inter-prediction coding or its maximum value, etc., may be stored in both the SPS and GPS, or in only one of them. Furthermore, this information may be stored in control information other than the SPS and GPS.

The devices, processes, syntax, etc. disclosed using Figures 39 to 45 may be implemented in combination with at least a portion of other disclosures in this disclosure. Furthermore, parts of the devices, processes, syntax, etc. disclosed using Figures 39 to 45 may be implemented in combination with other disclosures.

Furthermore, not all of the components disclosed using Figures 39 to 45 are always required, and each device may only have some of the components.

As described above, the three-dimensional data encoding device according to this embodiment performs the processing shown in FIG. 46. The three-dimensional data encoding device performs motion compensation on multiple encoded point groups (S12801). The three-dimensional data encoding device generates a reference point group (for example, the inter-reference point group shown in FIG. 41) by integrating (combining) multiple encoded point groups after motion compensation (S12802). The three-dimensional data encoding device generates an N-ary tree structure (N is an integer greater than or equal to 2) of the target point group (for example, the target octree shown in FIG. 41) (S12803). The three-dimensional data encoding device encodes the N-ary tree structure of the target point group using the reference point group (S12804). Note that N is, for example, 8, but may be any power of 2 or any other value.

This allows the three-dimensional data encoding device to improve encoding efficiency by encoding the target point group using a reference point group that integrates multiple encoded point groups.

For example, when a three-dimensional data encoding device encodes the N-ary tree structure of a target point group (S12804), it performs motion compensation on the reference point group relative to the target point group, generates an N-ary tree structure of the reference point group after motion compensation (for example, the inter-reference octree shown in Figure 41), and encodes the N-ary tree structure of the target point group using the N-ary tree structure of the reference point group.

For example, in encoding the N-ary tree structure of the target point group (S12804), the three-dimensional data encoding device entropy encodes the N-ary tree structure of the target point group and controls the probability parameters used in the entropy encoding based on the reference point group. For example, the three-dimensional data encoding device selects a probability parameter to use from multiple probability parameters based on the reference point group.

For example, a three-dimensional data encoding device generates an encoded target point group (e.g., the encoded point group shown in Figure 41) from the N-ary tree structure of the target point group, performs motion compensation on the encoded target point group relative to the reference point group, and updates the reference point group by integrating the motion-compensated encoded target point group into the reference point group.

For example, each of the encoded multiple point clouds belongs to a different frame than the target point cloud. For example, each of the encoded multiple point clouds belongs to the same frame as the target point cloud.

For example, the three-dimensional data encoding device stores first information (e.g., sps_inter_prediction_enabled_flag or gps_inter_prediction_enabled_flag) indicating whether encoding using a reference point group is allowed in control information common to multiple point groups (e.g., SPS or GPS).

For example, if the first information indicates that encoding using a reference point cloud is permitted, the three-dimensional data encoding device stores second information regarding the number of encoded point clouds (e.g., sps_max_num_ref_frames_minus1 or gps_num_ref_frames_minus1) in control information common to the multiple point clouds (e.g., SPS or GPS). For example, the second information indicates the number or maximum number of encoded point clouds to be integrated.

For example, a three-dimensional data encoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

The 3D data decoding device according to this embodiment also performs the processing shown in FIG. 47. The 3D data decoding device performs motion compensation on multiple decoded point groups (S12811). The 3D data decoding device generates a reference point group (e.g., the inter-reference point group shown in FIG. 42) by integrating (combining) multiple decoded point groups after motion compensation (S12812). The 3D data decoding device uses the reference point group to decode an N-ary tree structure (N is an integer greater than or equal to 2) (e.g., the decoded octree shown in FIG. 42) of the target point group (S12813). In other words, the 3D data decoding device obtains the N-ary tree structure of the target point group by decoding the bit stream (encoded data) generated by encoding the N-ary tree structure of the target point group. The 3D data decoding device generates a decoded point group of the target point group from the N-ary tree structure of the target point group (S12814). Note that N is, for example, 8, but may be any power of 2 or any other value.

This allows the three-dimensional data decoding device to decode the target point group using a reference point group that integrates multiple decoded point groups.

For example, in decoding the N-ary tree structure of the target point group (S12813), the three-dimensional data decoding device performs motion compensation on the reference point group relative to the target point group, generates an N-ary tree structure of the reference point group after motion compensation (for example, the inter-reference octree shown in Figure 42), and decodes the N-ary tree structure of the target point group using the N-ary tree structure of the reference point group.

For example, in decoding the N-ary tree structure of the target point group (S12813), the three-dimensional data decoding device entropy decodes the N-ary tree structure of the target point group and controls the probability parameters used in the entropy decoding based on the reference point group. For example, the three-dimensional data decoding device selects a probability parameter to use from multiple probability parameters based on the reference point group.

For example, a three-dimensional data decoding device performs motion compensation on the decoded point group of the target point group relative to the reference point group, and updates the reference point group by integrating the decoded point group after motion compensation with the reference point group.

For example, each of the decoded multiple point groups belongs to a different frame than the target point group. For example, each of the decoded multiple point groups belongs to the same frame as the target point group.

For example, the three-dimensional data decoding device obtains first information (e.g., sps_inter_prediction_enabled_flag or gps_inter_prediction_enabled_flag) indicating whether decoding using a reference point group is permitted from control information common to multiple point groups (e.g., SPS or GPS).

For example, when the first information indicates that decoding using a reference point group is permitted, the three-dimensional data decoding device obtains second information regarding the number of decoded point groups (e.g., sps_max_num_ref_frames_minus1 or gps_num_ref_frames_minus1) from control information common to the multiple point groups (e.g., SPS or GPS). For example, the second information indicates the number or maximum number of decoded point groups to be integrated.

For example, a three-dimensional data decoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

Fifth Embodiment
In this embodiment, a case will be described in which inter prediction and intra prediction are switched and performed on position information of a point cloud.

Figure 48 is a block diagram of a three-dimensional data encoding device 12900 according to this embodiment. Note that while Figure 48 describes a processing unit related to encoding position information (geometry) of point clouds, the three-dimensional data encoding device 12900 may also include other processing units, such as a processing unit that encodes attribute information of point clouds. In inter prediction and intra prediction, the point cloud to be encoded is encoded while referring to an already encoded point cloud.

The three-dimensional data encoding device 12900 includes a grouping unit 12901, a buffer 12902, a quantization unit 12903, an inverse quantization unit 12904, a buffer 12905, an intra prediction unit 12906, a buffer 12907, a motion estimation and compensation unit 12908, an inter prediction unit 12909, a switching unit 12910, and an entropy encoding unit 12911.

The grouping unit 12901 extracts a group of points to be used as a prediction tree (Predtree), which is a unit of encoding, from the input target point group, which is data of the point group to be encoded, and sets it as one group. In the input target point group, the positions of the points are expressed, for example, by three-dimensional coordinates (e.g., x, y, z). The buffer 12902 stores the generated prediction tree. For example, the buffer 12902 may initialize the data stored for each prediction tree. Encoding processing is performed sequentially on each of the multiple three-dimensional points included in the prediction tree (Predtree) stored in the buffer 12902. The three-dimensional coordinates may be expressed in either Cartesian coordinates or polar coordinates. Hereinafter, position information expressed in Cartesian coordinates will be referred to as position information in a Cartesian coordinate system, and position information expressed in polar coordinates will be referred to as position information in a polar coordinate system.

Then, the difference (first residual signal) between each of the multiple 3D points included in the prediction tree (Predtree) and the selected prediction point is calculated. This first residual signal is also called a prediction residual. The first residual signal is also an example of a first residual.

The quantization unit 12903 quantizes the first residual signal. The entropy coding unit 12911 entropy codes the quantized first residual signal to generate coded data, and outputs (generates) a bitstream including the coded data.

The inverse quantization unit 12904 inversely quantizes the first residual signal quantized by the quantization unit 12903. The inversely quantized first residual signal is added to a predicted value based on selected prediction points (one or more candidate points) to be decoded as a three-dimensional point (reference point) used for intra prediction and inter prediction. Note that, as described in the above embodiment, the predicted value is calculated based on the position information of one or more candidate points. The buffer 12905 holds a group of decoded reference points for intra prediction. For example, the buffer 12905 may initialize the data held for each prediction tree (target point group). Furthermore, the buffer 12907 holds a group of reference points for inter prediction. For example, the buffer 12907 may initialize the data held for each prediction tree (target point group).

The intra prediction unit 12906 determines the intra prediction point to be used for prediction using a predetermined method, by referencing information in the prediction tree (Predtree) that includes the 3D point to be encoded, such as multiple 3D points (a group of reference points for intra prediction) included in the prediction tree (Predtree). For example, the intra prediction unit 12906 may determine the intra prediction point by extrapolating using two 3D points (decoded points) that have been dequantized immediately before the 3D point to be encoded (e.g., an ancestor node such as a parent node in the prediction tree).

The motion detection and compensation unit 12908 reconstructs the encoded point group based on multiple three-dimensional points (multiple decoded points) included in a prediction tree (Predtree) that includes the three-dimensional point to be encoded, detects (motion detection) the displacement between the encoded point group and the point group to be encoded, and corrects (motion compensation) the encoded point group based on the detected displacement, thereby generating an inter-prediction point group, which is a reference point group for inter-prediction after alignment.

The inter prediction unit 12909 determines the inter prediction point to be used for prediction using a predetermined method based on the group of motion-compensated inter prediction points. For example, the inter prediction unit 12909 may select the point closest to the intra prediction point from the group of inter prediction points as the inter prediction point, or may select a 3D point near the immediately preceding (last) encoded 3D point (e.g., a 3D point corresponding to an ancestor node such as a parent node in a prediction tree) as the inter prediction point without referring to the intra prediction point.

The switching unit 12910 selects either an intra-prediction point or an inter-prediction point to determine the prediction point to be used for prediction. In this way, the 3D data encoding device 12900 determines the position information of one or more candidate points from among multiple encoded 3D points as prediction points, and calculates a prediction value based on the prediction point. The intra-prediction unit 12906 and the inter-prediction unit 12909 determine the prediction point (intra-prediction point or inter-prediction point) based on the 3D point encoded immediately before the 3D point to be encoded. In other words, the 3D data encoding device 12900 determines one or more candidate points for calculating a prediction value based on one or more reference points from among multiple encoded 3D points. The one or more reference points are 3D points encoded immediately before the 3D point to be encoded, and may, for example, be 3D points corresponding to the parent node (ancestor node) of the 3D point to be encoded in a prediction tree.

The 3D data encoding device 12900 may select either an intra-prediction point or an inter-prediction point as a prediction point according to the procedure of the flowchart in Figure 50, which will be described later. Prediction-related information (prediction information) for selecting whether an intra-prediction point or an inter-prediction point is to be used as a prediction point may be entropy-coded and written in the header section of each 3D point, or may be interleaved with each 3D point. Motion compensation information, such as motion vectors, may be written in the header section of a frame or a prediction tree (Predtree), or may be entropy-coded and written in the header section of each 3D point, or may be interleaved with each 3D point. The reference points for inter-prediction may be a point group included in an encoded frame different from the frame to be encoded, or may be a coded point group included in the same frame as the frame to be encoded.

In this way, the three-dimensional data encoding device 12900 can predict the point to be encoded using inter prediction in addition to intra prediction, thereby reducing the amount of information in the first residual signal to be entropy encoded, potentially improving encoding efficiency.

The 3D data encoding device 12900 does not need to constantly reference inter-prediction points, but may instead encode based only on information about the point group to be encoded, by initializing the buffer 12907 that stores the inter-prediction reference point group at a predetermined time interval (e.g., every second), a predetermined frame interval (e.g., every 30 frames), or at any timing notified to the 3D data decoding device. This makes it possible for a corresponding 3D data decoding device to jump in and start playback from a point group that is not at the beginning of a bitstream that does not reference inter-prediction points, potentially improving the random accessibility or error resilience of the bitstream.

When the input point cloud to be encoded has coordinates expressed in Cartesian coordinates as position information, the three-dimensional data encoding device 12900 encodes the position information indicated by the coordinates expressed in Cartesian coordinates.When the input point cloud to be encoded has coordinates expressed in polar coordinates as position information, the three-dimensional data encoding device 12900 encodes the position information indicated by the coordinates expressed in polar coordinates.

Figure 49 is a block diagram of a three-dimensional data decoding device 12920 according to this embodiment. Note that while Figure 49 describes a processing unit related to decoding position information (geometry) of point clouds, the three-dimensional data decoding device 12920 may also include other processing units, such as a processing unit that decodes attribute information of point clouds. The three-dimensional data decoding device 12920 performs inter-prediction decoding, which decodes the point cloud to be decoded while referencing point clouds that have already been decoded. For example, the three-dimensional data decoding device 12920 decodes the bitstream generated by the three-dimensional data encoding device 12900 shown in Figure 48.

The three-dimensional data decoding device 12920 includes an entropy decoding unit 12921, an inverse quantization unit 12922, a buffer 12923, an intra prediction unit 12924, a buffer 12925, a motion compensation unit 12926, an inter prediction unit 12927, and a switching unit 12928.

The three-dimensional data decoding device 12920 obtains the bitstream generated by the three-dimensional data encoding device 12900.

The entropy decoding unit 12921 generates a quantized first residual signal by entropy decoding the input bitstream for each 3D point in the prediction tree (Predtree). The inverse quantization unit 12922 inverse quantizes the quantized first residual signal to reproduce the first residual signal. The first residual signal for each 3D point is added to a predicted value based on the prediction point corresponding to each 3D point, and then generated (output) as a decoded point. In other words, the 3D data decoding device 12920 calculates the position information of one 3D point to be decoded by adding the predicted value and the prediction residual.

Buffer 12923 stores the generated decoded points as a group of reference points for intra prediction. For example, buffer 12923 may initialize the data stored for each prediction tree (target point group). Buffer 12925 stores the generated decoded points as a group of reference points for inter prediction. For example, buffer 12925 may initialize the data stored for each prediction tree (target point group).

The intra prediction unit 12924 determines the intra prediction point to be used for prediction using a predetermined method, by referencing information in the prediction tree (Predtree) that includes the 3D point to be decoded, such as multiple 3D points (a group of reference points for intra prediction) included in the prediction tree (Predtree). For example, the intra prediction unit 12924 may determine the intra prediction point by extrapolating using two 3D points (decoded points) that have been dequantized immediately before the 3D point to be decoded (e.g., an ancestor node such as a parent node in the prediction tree).

The motion compensation unit 12926 reconstructs a decoded point group based on multiple three-dimensional points (multiple decoded points) included in a prediction tree (Predtree) that includes the three-dimensional point to be decoded, and corrects (motion compensates) the displacement between the decoded point group and the point group to be decoded, thereby generating an inter-prediction point group, which is a reference point group for inter-prediction after alignment.

The inter prediction unit 12927 determines the inter prediction point to be used for prediction using a predetermined method based on the group of motion-compensated inter prediction points. For example, the inter prediction unit 12927 may select a point from the group of inter prediction points that is closest to the intra prediction point as the inter prediction point, or may select a 3D point near the most recently decoded 3D point (e.g., a 3D point corresponding to an ancestor node such as a parent node in a prediction tree) as the inter prediction point without referring to the intra prediction point.

The switching unit 12928 selects either an intra-prediction point or an inter-prediction point to determine the prediction point to be used for prediction. In this way, the 3D data decoding device 12920 determines the position information of one or more candidate points from among multiple decoded 3D points as prediction points, and calculates a predicted value based on the prediction point. The intra-prediction unit 12924 and the inter-prediction unit 12927 determine the prediction point (intra-prediction point or inter-prediction point) based on the 3D point decoded immediately before the 3D point to be decoded. In other words, the 3D data decoding device 12920 determines one or more candidate points for calculating a predicted value based on one or more reference points from among multiple decoded 3D points. The one or more reference points are 3D points encoded immediately before the 3D point to be decoded, and may, for example, be 3D points corresponding to the parent node (ancestor node) of the 3D point to be decoded in a prediction tree.

The 3D data decoding device 12920 may select either an intra-prediction point or an inter-prediction point as a prediction point according to the procedure of the flowchart in FIG. 51, which will be described later. The 3D data decoding device 12920 may also select either an intra-prediction point or an inter-prediction point as a prediction point based on prediction-related information (prediction information) for selecting whether an intra-prediction point or an inter-prediction point is to be used as a prediction point. The prediction information may be entropy-encoded and written in the header section of each 3D point, or may be interleaved with each 3D point. Information related to motion compensation, such as motion vectors, may be written in the header section of a frame or a prediction tree (Predtree), or may be entropy-encoded and written in the header section of each point, or may be interleaved with each 3D point. In this way, the prediction information or information related to motion compensation may be notified to the 3D data decoding device 12920 from the corresponding 3D data encoding device 12900. In addition, the reference points for inter prediction may be a group of points included in an already coded frame different from the frame to be coded, or may be a group of coded points included in the same frame as the frame to be coded.

In this way, the three-dimensional data decoding device 12920 can predict the points to be decoded using inter prediction in addition to intra prediction, thereby decoding the point group from the encoded bit stream (for example, the bit stream output from the three-dimensional data encoding device 12900 in Figure 48) while referring to the decoded point group.

The 3D data decoding device 12920 does not need to constantly reference inter-prediction points, but may instead decode based only on information about the point group to be decoded, for example by initializing the buffer 12925 storing the inter-prediction reference point group at a predetermined time interval (e.g., every second), a predetermined frame interval (e.g., every 30 frames), or at any timing notified by the corresponding 3D data encoding device 12900. This enables the 3D data decoding device 12920 to jump in and start playback from a point group that is not at the beginning of the bitstream and does not reference inter-prediction points, potentially improving the random accessibility and error resistance of the bitstream.

When the bitstream contains coded data in which position information represented by coordinates expressed in Cartesian coordinates is coded, the three-dimensional data decoding device 12920 decodes the position information represented by coordinates expressed in Cartesian coordinates.When the bitstream contains coded data in which position information represented by coordinates expressed in polar coordinates is coded, the three-dimensional data decoding device 12920 decodes the position information represented by coordinates expressed in polar coordinates.

Figure 50 is a flowchart showing an example of a procedure for encoding each three-dimensional point of a prediction tree (Predtree) in a three-dimensional data encoding device 12900.

In this example, the 3D data encoding device 12900 first determines an intra-prediction point from a group of intra-prediction reference points (S12901). The 3D data encoding device 12900 may determine the intra-prediction point using, for example, a method of determining a prediction point using a prediction tree, as disclosed in the previously described embodiments. For example, the 3D data encoding device 12900 may generate a prediction tree using multiple encoded 3D points and select one or more candidate points from the multiple encoded 3D points based on the prediction tree. The 3D data encoding device 12900 may determine, as the intra-prediction point, the prediction point that results in the smallest amount of coding among at least one intra-prediction point determined by at least one of the above methods. Furthermore, the 3D data encoding device 12900 may determine, as the intra-prediction point, the prediction point that results in the smallest absolute sum (or sum of squares) of coordinate residuals among at least one intra-prediction point determined by at least one of the above methods.

Next, the three-dimensional data encoding device 12900 outputs intra-prediction related parameters (S12902). If there are two or more candidate methods for determining the intra-prediction points to be determined in step S12901, the three-dimensional data encoding device 12900 may output information indicating the selected candidate method to the bitstream as intra-prediction related parameters.

Next, the 3D data encoding device 12900 determines an inter-prediction point by referring to at least one candidate point extracted from the group of inter-prediction points. For example, the 3D data encoding device 12900 may determine one candidate point as the inter-prediction point, or may determine a prediction point having, as its coordinates, the average values of the coordinates of multiple candidate points as the inter-prediction point. Alternatively, the 3D data encoding device 12900 may determine, as the inter-prediction point, a prediction point having, as its coordinates, the average values of the coordinates of the intra-prediction point and at least one candidate point.

Here, the three-dimensional data encoding device 12900 may search for a point located near the intra-prediction point as at least one candidate point (S12903).

Next, the 3D data encoding device 12900 may assign smaller index values to each of the at least one determined inter prediction point in order of proximity to the intra prediction point (S12904).

Next, the three-dimensional data encoding device 12900 determines whether the search has ended (S12905). If the search has ended (Yes in S12905), the process proceeds to the next step S12906. If the search has not ended (No in S12905), the process returns to step S12903. The end of the search may be determined by finding a predetermined number of inter-prediction points, by searching all of the point clouds in a predetermined range, or by satisfying either finding a predetermined number of inter-prediction points or searching all of the point clouds in a predetermined range.

Next, the 3D data encoding device 12900 determines a prediction method (S12906). Specifically, the 3D data encoding device 12900 determines whether to use intra prediction or inter prediction as the method for determining a prediction point. In other words, the 3D data encoding device 12900 determines whether to use intra prediction points or inter prediction points as prediction points. For example, the 3D data encoding device 12900 may determine the prediction method for the intra prediction point or the inter prediction point that results in the smallest amount of coding. Furthermore, the 3D data encoding device 12900 may determine the prediction method for the intra prediction point or the inter prediction point that results in the smallest absolute sum (or sum of squares) of coordinate residuals.

The three-dimensional data encoding device 12900 determines whether the mode of the determined prediction method is an inter mode indicating that the prediction method is inter prediction, or an intra prediction mode indicating that the prediction method is intra prediction (S12907).

If the determined prediction method is inter prediction (inter mode in S12907), the three-dimensional data encoding device 12900 outputs identification information (e.g., a flag) indicating that the inter prediction point has been determined as the prediction point to the bitstream (S12908).

Next, the 3D data encoding device 12900 outputs, to the bitstream as inter-prediction-related parameters, information regarding the number of candidate points used to determine the coordinates of the inter-prediction point, and index values for each candidate point used (S12909). Index values may be assigned to one or more candidate points used to determine the prediction value.

Furthermore, if the determined prediction method is intra prediction (intra mode in S12907), the 3D data encoding device 12900 outputs identification information (e.g., a flag) indicating that an intra prediction point has been determined as the prediction point to the bitstream (S12911). Note that the identification information in steps S12908 and S12911 is information indicating whether an inter prediction point or an intra prediction point has been determined as the prediction point.

After step S12909 or step S12911, the three-dimensional data encoding device 12900 encodes the coordinate information of the three-dimensional point to be encoded by referring to the predicted point obtained by the determined prediction method (S12910).

In this way, the three-dimensional data encoding device 12900 determines at least one inter-prediction point by referring to the inter-prediction point group and the intra-prediction points, determines a method for obtaining a prediction point from these intra-prediction points and inter-prediction points, and encodes the position information (coordinate information) of the three-dimensional point to be encoded by referring to the prediction point.

In S12903, the inter-prediction point may be searched for in the vicinity of a 3D point that is uniquely determined without reference to intra-prediction parameters, such as a 3D point that was encoded immediately before (for example, a 3D point corresponding to an ancestor node such as a parent node of a prediction tree), without referencing the intra-prediction point. In this case, S12902 may not be performed immediately after S12901, but may be performed immediately after S12911.

Figure 51 is a flowchart showing an example of a procedure for decoding each 3D point of a prediction tree (Predtree) in a 3D data decoding device 12920. Figure 51 corresponds to the decoding of a bitstream generated according to the encoding procedure of Figure 50. In other words, the bitstream includes an encoded first residual signal (prediction residual) and an index value assigned to one candidate point used to calculate a prediction value.

In this example, the 3D data decoding device 12920 first obtains intra-prediction related parameters from the bitstream (S12921).

Next, the 3D data decoding device 12920 determines intra-prediction points based on the acquired intra-prediction-related parameters (S12922). Specifically, the 3D data decoding device 12920 determines intra-prediction points in a manner similar to step S12901 in FIG. 50. The 3D data decoding device 12920 is notified of the intra-prediction-related parameters from the corresponding 3D data encoding device 12900, and determines intra-prediction points in accordance with the intra-prediction-related parameters. The intra-prediction-related parameters are acquired in step S12921 and include information specifying at least one method for determining intra-prediction points and parameters accompanying this information.

Next, the three-dimensional data decoding device 12920 obtains identification information indicating the mode of the prediction method from the bitstream (S12923).

Next, the 3D data decoding device 12920 determines whether the acquired identification information indicates an inter mode, which indicates that the prediction method is inter prediction, or an intra prediction mode, which indicates that the prediction method is intra prediction (S12924).

If the prediction method is inter prediction (inter mode in step S12924), the 3D data decoding device 12920 obtains inter prediction related parameters from the bitstream (S12925).

Next, the 3D data decoding device 12920 executes processing (S12926 to S12929) for determining an inter-prediction point. Specifically, the 3D data decoding device 12920 determines an inter-prediction point using a method similar to steps S12903 to S12905 of FIG. 50. For example, the 3D data decoding device 12920 determines an inter-prediction point by referring to at least one candidate point extracted from the inter-prediction point group. For example, the 3D data decoding device 12920 may determine one candidate point as an inter-prediction point, or may determine a prediction point having, as its coordinates, the average values of the coordinates of multiple candidate points as an inter-prediction point. Alternatively, the 3D data decoding device 12920 may determine, as an inter-prediction point, a prediction point having, as its coordinates, the average values of the coordinates of the intra-prediction point and at least one candidate point.

Here, the 3D data decoding device 12920 may search for a point located near the intra-prediction point as at least one candidate point (S12926).

Next, the 3D data decoding device 12920 may assign smaller index values to each of the at least one determined inter prediction point in order of proximity to the intra prediction point (S12927).

Next, the 3D data decoding device 12920 determines whether the search has ended (S12928). If the search has ended (Yes in S12928), the process proceeds to the next step S12929. If the search has not ended (No in S12928), the process returns to step S12926. The end of the search may be determined by finding a predetermined number of inter-prediction points, by searching all of the point clouds in a predetermined range, or by satisfying either finding a predetermined number of inter-prediction points or searching all of the point clouds in a predetermined range.

Next, the 3D data decoding device 12920 determines an inter-prediction point based on the inter-prediction-related parameters while referring to the inter-prediction point group and the intra-prediction point (S12929). For example, the 3D data decoding device 12920 identifies candidate points to be used in determining the coordinates of the inter-prediction point based on information included in the inter-prediction-related parameters regarding the number of candidate points to be used in determining the coordinates of the inter-prediction point and an index value assigned to each candidate point used, and determines the coordinates of the inter-prediction point using the identified candidate points, thereby determining the inter-prediction point. In other words, the 3D data decoding device 12920 selects one candidate point from multiple decoded 3D points based on the index value included in the bitstream.

After step S12929, or if intra mode is selected in step S12924, the three-dimensional data decoding device 12920 decodes the position information (coordinate information) of the three-dimensional point to be decoded by referring to the predicted point obtained using the specified prediction method (S12930).

In this way, when the prediction method is inter prediction, the 3D data decoding device 12920 decodes the coordinate information of the point to be decoded by referring to the inter prediction point, and when the prediction method is intra prediction, it decodes the coordinate information of the point to be decoded by referring to the intra prediction point.

In S12926, the inter-prediction point may be searched for in the vicinity of a 3D point that is uniquely determined without reference to intra-prediction parameters, such as the most recently decoded 3D point (e.g., a 3D point corresponding to an ancestor node such as a parent node of a prediction tree), without reference to the intra-prediction point. In this case, S12921 and S12922 may not be performed immediately before S12923, and S12921 and S12922 may be performed if intra mode is determined in S12924.

Figure 52 is a block diagram of a three-dimensional data encoding device 12930 according to a modified example of this embodiment. While Figure 52 illustrates a processing unit related to encoding the position information (geometry) of a point cloud, the three-dimensional data encoding device 12930 may also include other processing units, such as a processing unit that encodes attribute information of the point cloud. In inter-prediction and intra-prediction, the point cloud to be encoded is encoded while referencing an already-encoded point cloud. The three-dimensional data encoding device 12930 differs in its configuration and operation from the three-dimensional data encoding device 12900 of Figure 48 in that it includes a coordinate conversion unit 12931 that converts a point cloud having position information expressed in Cartesian coordinates into position information expressed in polar coordinates for encoding, does not quantize the prediction residual (first residual signal) of the position information expressed in polar coordinates, and quantizes a second residual signal in Cartesian coordinates that corresponds to the error that occurs in the conversion between Cartesian coordinates and polar coordinates. On the other hand, the three-dimensional data encoding device 12930 is the same in configuration and operation as the three-dimensional data encoding device 12900 except for the differences described above.

The three-dimensional data encoding device 12930 includes a coordinate transformation unit 12931, a grouping unit 12932, a buffer 12933, a buffer 12934, an intra prediction unit 12935, a buffer 12936, a motion estimation and compensation unit 12937, an inter prediction unit 12938, a switching unit 12939, a coordinate transformation unit 12940, a buffer 12941, a quantization unit 12942, and an entropy encoding unit 12943.

The coordinate conversion unit 12931 converts the coordinate system of the position information of the target point group, which is the input data of the point group to be encoded, from a Cartesian coordinate system to a polar coordinate system. In other words, the coordinate conversion unit 12931 generates position information in the polar coordinate system by converting the coordinate system of the position information of a single three-dimensional point to be encoded in the Cartesian coordinate system. The point group to be encoded converted to polar coordinates is output to the grouping unit 12932.

The grouping unit 12932 extracts a group of points to be used as a prediction tree (Predtree), which is a unit of encoding, from the target point group, which is a group of points to be encoded that have been converted into polar coordinates, and sets it as one group. The buffer 12933 stores the generated prediction tree. For example, the buffer 12933 may initialize the data stored for each prediction tree. The encoding process is performed sequentially on each of the multiple three-dimensional points included in the prediction tree (Predtree) stored in the buffer 12933.

A difference (first residual signal) is calculated between each of the multiple three-dimensional points (points to be coded) included in the prediction tree stored in buffer 12933 and the prediction point selected for the point to be coded. This first residual signal is a residual signal of position information expressed in polar coordinates. The first residual signal is also called a prediction residual. This first residual signal is an example of a first residual. Because the position information of the multiple three-dimensional points stored in buffer 12933 has been converted to a polar coordinate system, the first residual is the difference between the position information in the polar coordinate system after the conversion and the predicted value.

The first residual signal and the predicted point are then added together and stored in buffers 12934 and 12936 as decoded points that have been encoded. The position information of the decoded points stored in buffers 12934 and 12936 is expressed in polar coordinates. In this respect, the functions of buffers 12934 and 12936 differ from those of buffers 12905 and 12907, but otherwise their functions are the same.

Similarly, the intra prediction unit 12935, motion detection and compensation unit 12937, inter prediction unit 12938, and switching unit 12939 differ in function from the intra prediction unit 12906, motion detection and compensation unit 12908, inter prediction unit 12909, and switching unit 12910 in that the position information of the three-dimensional point to be processed is expressed in polar coordinates, but otherwise their functions are the same.

The coordinate conversion unit 12940 acquires the same decoding points as those stored in the buffers 12934 and 12936, and converts the coordinate system of the position information of the acquired decoding points from a polar coordinate system to a Cartesian coordinate system. In other words, the coordinate conversion unit 12940 generates position information in a Cartesian coordinate system by inversely converting the coordinate system of the polar coordinate system position information after conversion by the coordinate conversion unit 12931.

Buffer 12941 holds the position information of three-dimensional points expressed in Cartesian coordinates input to the three-dimensional data encoding device 12930.

Then, the difference (second residual signal) between the input position information in the Cartesian coordinate system and the position information in the Cartesian coordinate system obtained by converting the coordinate system from a polar coordinate system to a Cartesian coordinate system in the coordinate conversion unit 12940 is calculated. This second residual signal is an example of a second residual. In other words, the second residual signal is the difference between the position information in the Cartesian coordinate system that has not been subjected to coordinate conversion in the coordinate conversion unit 12931 and the position information that has been converted to polar coordinates and then converted back to a Cartesian coordinate system, and is a conversion error that occurs due to the coordinate conversion.

The quantization unit 12942 quantizes the second residual signal.

The entropy coding unit 12943 entropy codes the first residual signal and the quantized second residual signal to generate coded data and outputs a bitstream including the coded data.

In this way, the three-dimensional data encoding device 12930 converts the coordinate system of the position information of three-dimensional points from a Cartesian coordinate system to a polar coordinate system and encodes the position information in the polar coordinate system. This makes it possible to improve the prediction accuracy of the points to be encoded when encoding a point cloud generated by acquiring the three-dimensional positions of surrounding objects centered on a sensor position, such as with LiDAR, and potentially improve encoding efficiency.

Figure 53 is a block diagram of a three-dimensional data decoding device 12950 relating to a modified example of this embodiment. Note that while Figure 53 describes a processing unit related to decoding position information (geometry) of point clouds, the three-dimensional data decoding device 12950 may also include other processing units, such as a processing unit that decodes attribute information of point clouds. The three-dimensional data decoding device 12950 performs inter-prediction decoding, which decodes the point cloud to be decoded while referencing point clouds that have already been decoded. For example, the three-dimensional data decoding device 12950 decodes the bitstream generated by the three-dimensional data encoding device 12930 shown in Figure 52. The three-dimensional data decoding device 12950 differs in basic configuration and operation from the three-dimensional data decoding device 12920 of Fig. 49 in that it does not perform inverse quantization of the first residual signal (prediction residual), and in that it entropy decodes and inverse quantizes a second residual signal in orthogonal coordinates that corresponds to the conversion error that occurs in the conversion between orthogonal coordinates and polar coordinates to reproduce it, adds it to a point converted from the corresponding decoded point in polar coordinates to orthogonal coordinates, and outputs it as a decoded point in orthogonal coordinates. On the other hand, the three-dimensional data decoding device 12950 is the same as the three-dimensional data decoding device 12920 in all respects except for the above differences.

The three-dimensional data decoding device 12950 includes an entropy decoding unit 12951, a buffer 12952, an intra prediction unit 12953, a buffer 12954, a motion compensation unit 12955, an inter prediction unit 12956, a switching unit 12957, a coordinate transformation unit 12958, and an inverse quantization unit 12959.

The entropy decoding unit 12951 entropy decodes the input bitstream for each 3D point in the prediction tree (Predtree) to generate a first residual signal and a quantized second residual signal. The first residual signal for each 3D point is added to a predicted value based on the prediction point corresponding to each 3D point, and then generated (output) as a decoded point expressed in polar coordinates.

Buffer 12952 holds the generated decoded points as a group of reference points for intra prediction. For example, buffer 12952 may initialize the data it holds for each prediction tree (target point group). Buffer 12954 also holds the generated decoded points as a group of reference points for inter prediction. For example, buffer 12954 may initialize the data it holds for each prediction tree (target point group). The position information of the decoded points held in buffers 12952 and 12954 is expressed in polar coordinates. In this respect, the functions of buffers 12952 and 12954 differ from those of buffers 12923 and 12925, but the other functions are the same.

Similarly, the intra prediction unit 12953, motion compensation unit 12955, inter prediction unit 12956, and switching unit 12957 differ in function from the intra prediction unit 12924, motion compensation unit 12926, inter prediction unit 12927, and switching unit 12928 in that the position information of the three-dimensional point to be processed is expressed in polar coordinates, but otherwise their functions are the same.

The coordinate conversion unit 12958 acquires the same decoding points as those stored in buffers 12952 and 12954, and converts the coordinate system of the position information of the acquired decoding points from a polar coordinate system to a Cartesian coordinate system.

The inverse quantization unit 12959 inverse quantizes the quantized second residual signal to reproduce the second residual signal.

The position information in the Cartesian coordinate system obtained by coordinate transformation by the coordinate transformation unit 12958 and the second residual signal reproduced by inverse quantization by the inverse quantization unit 12959 are added together and then generated (output) as a decoded point including position information in the Cartesian coordinate system.

In this way, the three-dimensional data decoding device 12950 is equipped with means for converting the coordinate system of a decoded point having position information in a polar coordinate system from a polar coordinate system to a Cartesian coordinate system, and adding it to a second residual signal in Cartesian coordinates that corresponds to the error that occurs in the conversion between the position information in the Cartesian coordinate system and the position information in the polar coordinate system. This allows the three-dimensional data decoding device 12950 to decode a point cloud from an encoded bit stream (e.g., a bit stream output from the three-dimensional data encoding device 12930 in Figure 52) while referencing the point cloud that has already been encoded in polar coordinates.

Figure 54 shows an example of geometry parameter set (GPS) syntax. This syntax is used in the three-dimensional data encoding devices 12900, 12930 and three-dimensional data decoding devices 12920, 12950 described using Figures 48 to 53.

As shown in these examples, GPS may notify information, such as gps_alt_coordinates_flag, indicating whether a coordinate system other than Cartesian coordinates, such as polar coordinates, is used in the decoding process for each point. When gps_alt_coordinates_flag is set to 1 (i.e., when gps_alt_coordinates_flag = 1), it indicates that an alternative coordinate system (e.g., a polar coordinate system) is used in the decoding process for data units of position information in the bitstream that reference GPS. When gps_alt_coordinates_flag is set to 0 (i.e., when gps_alt_coordinates_flag = 0), it indicates that an alternative coordinate system is not used in the decoding process for data units of position information in the bitstream that reference GPS. In other words, gps_alt_coordinates_flag may indicate whether the encoded data includes first encoded data calculated in a polar coordinate system. Note that gps_alt_coordinates_flag is an example of first identification information indicating whether the encoded data includes first encoded data calculated in a polar coordinate system.

Furthermore, when a coordinate system (alternate coordinate system) other than a Cartesian coordinate system, such as a polar coordinate system, is used in the decoding process of each 3D point (e.g., when gps_alt_coordinates_flag = 1), coordinate transformation information, such as gps_coordinate_trans_enabled_flag, may be notified, indicating whether to perform coordinate transformation of each decoded point (e.g., from a polar coordinate system to a Cartesian coordinate system) before outputting the 3D point from the 3D data decoding device. When gps_alt_coordinates_flag = 1 (i.e., when the first identification information indicates that the encoded data includes first encoded data), specifically, the position information of one or more candidate points used to calculate the predicted value and the position information of one 3D point to be encoded used to calculate the first residual are position information in the polar coordinate system. In this case, the bitstream includes gps_coordinate_trans_enabled_flag. gps_coordinate_trans_enabled_flag is an example of second identification information indicating whether to output position information in the polar coordinate system or the Cartesian coordinate system during decoding. Furthermore, when gps_alt_coordinates_flag=1, the three-dimensional data encoding device 12900 quantizes the first residual during encoding and encodes the quantized first residual, encoding position information in a polar coordinate system. Therefore, when gps_alt_coordinates_flag=1 and gps_coordinate_trans_enabled_flag=0, it can be said that position information in a polar coordinate system is encoded, and gps_coordinate_trans_enabled_flag=0 can be said to indicate that position information in a polar coordinate system is output during decoding. Whether or not to output position information in a polar coordinate system may be switched by another flag (identification information).

Note that if gps_alt_coordinates_flag=0 (i.e., if the first identification information indicates that the encoded data does not include the first encoded data), the bitstream does not need to include gps_coordinate_trans_enabled_flag (second identification information).

When gps_coordinate_trans_enabled_flag is set to 1 (i.e., when gps_coordinate_trans_enabled_flag=1), it indicates that the coordinate system is converted to another coordinate system during the decoding process of the data unit of position information in the bitstream that references GPS. Therefore, when gps_alt_coordinates_flag=1 and gps_coordinate_trans_enabled_flag=0, position information in the Cartesian coordinate system is decoded, so gps_coordinate_trans_enabled_flag=0 can be said to indicate that position information in the Cartesian coordinate system is output during decoding.

When gps_coordinate_trans_enabled_flag is set to 0 (i.e., when gps_coordinate_trans_enabled_flag=0), it indicates that the coordinate system will not be converted to another coordinate system when decoding data units of position information in the bitstream that reference GPS. Note that when gps_coordinate_trans_enabled_flag is not specified, the value of gps_coordinate_trans_enabled_flag may be considered to be set to 0.

Note that if coordinate transformation of decoded points is not performed before each 3D point is output from the 3D data decoding device (for example, when gps_coordinate_trans_enabled_flag = 0), the point cloud may be encoded and decoded using the 3D data encoding device 12900 shown in Figure 48 and the 3D data decoding device 12920 shown in Figure 49. Note that if coordinate transformation of decoded points is performed before each 3D point is output from the 3D data decoding device (for example, when gps_coordinate_trans_enabled_flag = 1), the point cloud may be encoded and decoded using the 3D data encoding device 12930 shown in Figure 52 and the 3D data decoding device 12950 shown in Figure 53.

By notifying the three-dimensional data encoding device of gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag, it becomes possible to switch between the three-dimensional data encoding device 12900 shown in Figure 48 and the three-dimensional data encoding device 12930 shown in Figure 52 depending on the point group to be encoded, even when a coordinate system other than Cartesian coordinates, such as polar coordinates, is used to encode and decode each three-dimensional point (for example, when gps_alt_coordinates_flag = 1), which may improve encoding efficiency.

Note that Figure 54 illustrates GPS syntax, but gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag may be included in the SPS, the header of the data unit, or as metadata in other control information.

Figure 55 is an example of the syntax for each three-dimensional point (Predtree node). This syntax is used in the three-dimensional data encoding devices 12900, 12930 and three-dimensional data decoding devices 12920, 12950 described using Figures 48 to 54.

In this example, the three-dimensional data encoding devices 12900, 12930 first notify the three-dimensional data decoding devices 12920, 12950 of identification information (pred_mode) indicating how to determine intra-prediction points at three-dimensional points to be encoded or decoded. In addition, the three-dimensional data encoding devices 12900, 12930 may notify the three-dimensional data decoding devices 12920, 12950 of additional information for determining intra-prediction points according to the identification information (pred_mode).

Next, if inter-prediction is enabled in the GPS referenced by the prediction tree (predtree) being encoded (e.g., if gps_inter_prediction_enabeled_flag = 1), the 3D data encoding devices 12900, 12930 may notify the 3D data decoding devices 12920, 12950 of information (intra_pred_flag) indicating whether the prediction method for the 3D point to be encoded or decoded is intra-prediction or not (i.e., inter-prediction). Note that if gps_inter_prediction_enabeled_flag = 0, the value of intra_pred_flag may be set to 1 (intra-prediction). If the prediction method for the 3D point to be encoded or decoded is inter-prediction (e.g., intra_pred_flag = 0), identification information (inter_pred_mode) indicating how to determine the inter-prediction point for the 3D point to be encoded or decoded may be notified. Furthermore, the 3D data encoding devices 12900 and 12930 may set the number of candidate points in the inter-prediction point group referenced when determining an inter-prediction point to NumRefPoints according to the identification information (inter_pred_mode), and may notify the 3D data decoding devices 12920 and 12950 of NumRefPoints' worth of indices (inter_ref_point_idx) of each candidate point. If multiple candidate points are specified in the inter-prediction point group referenced when determining an inter-prediction point, the average value of the coordinates of the specified multiple candidate points may be used as the coordinate of the inter-prediction point. Furthermore, the 3D data encoding devices 12900 and 12930 may provide an inter_pred_mode that omits notification of the candidate point index and selects a specific candidate point, such as the one with the smallest index. For example, the 3D data encoding devices 12900 and 12930 may omit notification of the candidate point index by, for example, providing a process for determining whether inter_pred_mode indicates the relevant mode or by setting the value of NumRefPoints to 0. Furthermore, this can be implemented as long as the information necessary for a method of uniquely determining an inter-prediction point is notified. For example, instead of inter_pred_mode, the number of candidate points in the inter-prediction point group to be referenced when determining an inter-prediction point may be notified.

In addition, when searching for candidate points in an inter-prediction point group near a three-dimensional point that is uniquely determined without depending on identification information (pred_mode) indicating how to determine an intra-prediction point, such as the three-dimensional point that was most recently encoded or decoded (for example, a three-dimensional point corresponding to an ancestor node such as a parent node of a prediction tree), the three-dimensional data decoding device 12920, 12950 may be notified of identification information (pred_mode) indicating how to determine an intra-prediction point and additional information for determining an intra-prediction point only when the prediction method for the three-dimensional point to be encoded or decoded is intra-prediction (for example, intra_pred_flag=1).

Next, the three-dimensional data encoding devices 12900 and 12930 may notify the first difference (1st_residual_value) between the position information (coordinate value) of the point to be encoded or decoded and the position information (coordinate value) of the predicted point. If coordinate transformation of the decoded points is performed before outputting each three-dimensional point from the three-dimensional data decoding devices 12920 and 12950 (for example, when gps_coordinate_trans_enabled_flag = 1), the decoding results in another coordinate system, such as polar coordinates, may be transformed into the original coordinate system, such as rectangular coordinates, and the second difference (2nd_residual_value) between the original position information (coordinate value). Note that while an example has been shown in which this difference information is notified as a single syntax, it may also be decomposed into multiple syntax elements, such as positive/negative information and absolute value information, and notified.

This information is communicated from the three-dimensional data encoding devices 12900, 12930 to the three-dimensional data decoding devices 12920, 12950, making it possible for the three-dimensional data encoding devices 12900, 12930 and the three-dimensional data decoding devices 12920, 12950 to perform consistent prediction processing, and the three-dimensional data decoding devices 12920, 12950 can decode the three-dimensional points to be processed without causing any inconsistency with the corresponding three-dimensional data encoding devices 12900, 12930.

The devices, processes, syntax, etc. disclosed using Figures 48 to 55 may be implemented in combination with at least a portion of other embodiments. Furthermore, the devices, processes, portions of syntax, etc. disclosed using Figures 48 to 55 may be implemented in combination with other embodiments. Furthermore, all of the components disclosed using Figures 48 to 55 are not necessarily required, and only some of the components may be included.

As described above, the three-dimensional data encoding device according to this embodiment performs the processing shown in FIG. 56. The three-dimensional data encoding device determines a predicted value based on position information of one or more candidate points from among a plurality of encoded three-dimensional points (S12931). The three-dimensional data encoding device calculates a prediction residual, which is the difference between the position information of one three-dimensional point to be encoded from among the plurality of three-dimensional points, and the predicted value (S12932). The three-dimensional data encoding device generates encoded data by encoding the prediction residual (S12933). The three-dimensional data encoding device generates a bitstream including the encoded data (S12934). In step S12931, the three-dimensional data encoding device determines one or more candidate points based on one or more reference points from among the plurality of encoded three-dimensional points.

For example, the multiple 3D points form a prediction tree. One or more reference points include a 3D point corresponding to the parent node of the 3D point to be encoded.

This allows one or more candidate points used to calculate a predicted value to be determined based on the parent node of a single three-dimensional point to be encoded in the prediction tree, thereby reducing the prediction residual and improving encoding efficiency.

For example, one or more candidate points are assigned index values. The bitstream further includes the index values assigned to the candidate points used to determine the predicted value.

This allows the three-dimensional data decoding device to easily identify candidate points based on the index values, thereby reducing the processing load on the three-dimensional data decoding device.

For example, a three-dimensional data encoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

The three-dimensional data decoding device according to this embodiment also performs the processing shown in FIG. 57. The three-dimensional data decoding device acquires a bitstream including an encoded prediction residual and an index value assigned to one candidate point used to calculate a predicted value (S12941). The three-dimensional data decoding device determines one candidate point based on one or more reference points from among multiple decoded three-dimensional points, based on the index value (S12942). The three-dimensional data decoding device calculates a predicted value based on position information of the determined candidate point (S12943). The three-dimensional data decoding device calculates a prediction residual by decoding the encoded prediction residual (S12944). The three-dimensional data decoding device calculates position information of the one three-dimensional point to be decoded by adding the predicted value and the prediction residual (S12945).

This allows one candidate point to be determined based on one or more reference points among multiple encoded three-dimensional points, and the three-dimensional point to be decoded can be decoded using a predicted value based on the position information of the determined candidate point.

For example, the multiple 3D points form a prediction tree. One or more reference points include a 3D point corresponding to the parent node of the 3D point to be encoded.

For example, one or more candidate points are assigned index values. The bitstream further includes the index values assigned to the candidate points used to determine the predicted value.

This allows the three-dimensional data decoding device to easily identify candidate points based on the index values, thereby reducing the processing load on the three-dimensional data decoding device.

For example, a three-dimensional data decoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

Figure 58 is a flowchart showing the coordinate system switching process in the encoding process. The flowchart in Figure 58 switches between encoding using the three-dimensional data encoding device 12900 described in Figure 48 and encoding using the three-dimensional data encoding device 12930 described in Figure 52. The flowchart in Figure 58 also switches between encoding position information in a Cartesian coordinate system and encoding position information in a polar coordinate system.

First, the three-dimensional data encoding device checks the coordinate system of the input point cloud and determines the coordinate system for the encoding and decoding processes (S13001). In other words, the three-dimensional data encoding device determines the coordinate system of the position information that is the target of the encoding and decoding processes.

Next, the three-dimensional data encoding device determines whether the coordinate system of the input point group is the same as the coordinate system of the determined encoding process and decoding process (S13002).

If the three-dimensional data encoding device determines that the coordinate system of the input point cloud is the same as the coordinate system of the determined encoding process and decoding process (Yes in S13002), it sets gps_coordinate_trans_enabled_flag=0 and determines to encode the position information of the point cloud in the determined coordinate system without performing coordinate transformation (S13003).

If the three-dimensional data encoding device determines that the coordinate system of the input point cloud is not the same as the coordinate system of the determined encoding process and decoding process (No in S13002), it sets gps_coordinate_trans_enabled_flag=1, performs coordinate transformation, and determines to encode the position information of the point cloud in the determined coordinate system (S13004).

Note that the three-dimensional data encoding device 12930 described in Figure 52 shows an example in which the coordinate system of the input point cloud is polar coordinates and the coordinate system of the encoding process and decoding process is Cartesian coordinates, but the coordinate system of the input point cloud may be Cartesian coordinates and the coordinate system of the encoding process and decoding process may be polar coordinates. In this case, Figure 52 can be explained by reading the polar coordinate system as a Cartesian coordinate system and the Cartesian coordinate system as a polar coordinate system.

Next, the three-dimensional data encoding device determines whether the encoding coordinate system is a polar coordinate system or not (Cartesian coordinate system) (S13005).

If the three-dimensional data encoding device determines that the encoding coordinate system is a polar coordinate system (Yes in S13005), it sets gps_alt_coordinates_flag=1 and encodes the point cloud position information in the polar coordinate system (S13006).

If the three-dimensional data encoding device determines that the encoding coordinate system is not a polar coordinate system (i.e., a Cartesian coordinate system) (No in S13005), it sets gps_alt_coordinates_flag=0 and encodes the point cloud position information in the Cartesian coordinate system (S13007).

When determining the syntax using the above process, the gps_coordinate_trans_enabled_flag and gps_alt_coordinates_flag described using Figure 54 may be configured as syntax elements that are indicated independently and without dependency. In other words, gps_coordinate_trans_enabled_flag may be indicated in the GPS regardless of the presence or absence of gps_alt_coordinates_flag or the value of gps_alt_coordinates_flag.

In addition, in the above processing, the syntax configuration of Figure 54 may be adopted by swapping processing 1 in steps S13002 to S13004 and processing 2 in steps S13005 to S13007, and configuring processing 1 to be performed when gps_alt_coordinates_flag = 1 in processing 2.

Figure 59 is a flowchart showing the coordinate system switching process in the decoding process. The flowchart in Figure 59 switches between decoding using the three-dimensional data decoding device 12920 described in Figure 49 and decoding using the three-dimensional data decoding device 12950 described in Figure 53. The flowchart in Figure 59 also switches between decoding position information in a rectangular coordinate system and decoding position information in a polar coordinate system.

First, the 3D data decoding device analyzes the metadata contained in the bitstream (S13011). Specifically, the metadata is control information contained in GPS, SPS, headers, etc. The 3D data decoding device checks the gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag contained in the metadata.

Next, the three-dimensional data decoding device determines whether gps_alt_coordinates_flag=1 (S13012).

If gps_alt_coordinates_flag=1 (Yes in S13012), the three-dimensional data decoding device decides to decode in the polar coordinate system (S13013).

If gps_alt_coordinates_flag = 0 (No in S13012), the three-dimensional data decoding device decides to decode in the Cartesian coordinate system (S13014).

In this way, the coordinate system of the calculated position information of one three-dimensional point to be decoded is determined according to the value of gps_alt_coordinates_flag, and is therefore determined to be a coordinate system depending on whether or not it includes the first encoded data indicated by the first identification information.

Next, the three-dimensional data decoding device determines whether gps_coordinate_trans_enabled_flag = 1 (S13015).

If gps_coordinate_trans_enabled_flag = 1 (Yes in S13015), the three-dimensional data decoding device decodes the position information in the determined coordinate system without coordinate conversion (S13016). In this case, the position information of the point cloud is decoded using the configuration of the three-dimensional data decoding device 12920. Note that since gps_coordinate_trans_enabled_flag is indicated when gps_alt_coordinates_flag = 1, if gps_coordinate_trans_enabled_flag = 1 (i.e., if the second identification information indicates that position information in a polar coordinate system is to be output during decoding), the coordinate system of the calculated position information of one three-dimensional point to be decoded is a polar coordinate system.

If gps_coordinate_trans_enabled_flag = 0 (No in S13015), the 3D data decoding device performs coordinate transformation and decodes the position information in the determined coordinate system (S13017). In this case, the point cloud position information is decoded using the configuration of the 3D data decoding device 12950. Note that gps_coordinate_trans_enabled_flag is indicated when gps_alt_coordinates_flag = 1. Therefore, if gps_coordinate_trans_enabled_flag = 0 (i.e., when the second identification information indicates that position information in a Cartesian coordinate system is output during decoding), the coordinate system of the polar coordinate system position information obtained by adding the predicted value and the first residual is transformed, and the Cartesian coordinate system position information obtained by the transformation is calculated as the position information of one 3D point to be decoded. In this case, the encoded data includes a second residual, and the three-dimensional data decoding device calculates the second residual by decoding the encoded second residual, and in calculating the position information of one three-dimensional point to be decoded, the device adds the position information of the orthogonal coordinate system obtained by converting the coordinate system to the second residual, and calculates the position information obtained by the addition as the position information of one three-dimensional point to be decoded.

When metadata is configured with the syntax configuration of Figure 54, if the coordinate system to be decoded is determined to be polar coordinates in process 1 of steps S13012 to S13014, the process proceeds to process 2 of steps S13015 to S13017, and if the coordinate system to be decoded is determined to be Cartesian coordinates in process 1, the determination of process 2 may be skipped and decoding may be performed using a three-dimensional data decoding device 12920 with the configuration of Figure 49.

Note that gps_coordinate_trans_enabled_flag is coordinate transformation information indicating whether or not coordinate transformation is performed on each decoded point before outputting the point from the 3D data decoding device. However, it may also be information indicating whether or not coordinate transformation was performed when encoding each 3D point, or information indicating whether error information (transformation error) that occurs due to coordinate transformation is included in the bitstream. Furthermore, if such information is included, it may be determined whether or not coordinate transformation is performed in the 3D data decoding device or application.

While the process switching based on the combination of the coordinate system of the input point cloud, the coordinate system of the output point cloud, the coordinate system of the position information to be encoded, and the coordinate system of the position information to be decoded, and the signaling method for indicating these coordinate systems, have been described using predictive tree encoding as an example, a similar method may also be used in the case of octree encoding. Furthermore, if the coordinate system of the input point cloud, the coordinate system of the output point cloud, the coordinate system of the position information to be encoded, and the coordinate system of the position information to be decoded are all the same, the switching process may be omitted, or the process may be expanded when there are three or more types of coordinate systems. Furthermore, while the coordinate system used for encoding and decoding position information has been described as an example, a similar method may be used to switch processes when the coordinate system used for encoding and decoding attribute information corresponds to multiple coordinate systems, or when there is a possibility that the coordinate systems of the input point cloud and output point cloud will be switched to other coordinate systems. For example, syntax similar to that shown in Figure 54 may be included in attribute_parameter_set.

In addition, the coordinate system used to encode and decode location information and the coordinate system used to encode and decode attribute information may be controlled to be the same.

As described above, the three-dimensional data encoding device according to this embodiment performs the processing shown in FIG. 60. The three-dimensional data encoding device encodes a plurality of three-dimensional points in either a Cartesian coordinate system or a polar coordinate system. The three-dimensional data encoding device calculates a predicted value based on position information of one or more candidate points among the plurality of encoded three-dimensional points (S13021). The three-dimensional data encoding device calculates a first residual, which is the difference between the position information of one three-dimensional point to be encoded among the plurality of three-dimensional points and the predicted value (S13022). The three-dimensional data encoding device generates encoded data by encoding the first residual (S13023). The three-dimensional data encoding device generates a bitstream including encoded data and first identification information indicating whether the encoded data includes first encoded data calculated in a polar coordinate system (S13024).

As a result, the bit stream contains first identification information indicating whether the encoded data includes first encoded data calculated in a polar coordinate system, allowing the three-dimensional data decoding device to perform appropriate decoding processing based on the first identification information.

For example, the bitstream further includes second identification information. If the position information of one or more candidate points used to calculate the predicted value and the position information of one three-dimensional point to be encoded used to calculate the first residual are position information in a polar coordinate system, the first identification information indicates that the encoded data includes first encoded data calculated in a polar coordinate system. In this case, the second identification information also indicates whether position information in a polar coordinate system or position information in a Cartesian coordinate system is to be output during decoding.

For example, if the first identification information indicates that the encoded data does not include the first encoded data, the bitstream does not include the second identification information.

For example, when position information in a polar coordinate system is output during decoding, the second identification information indicates that position information in a polar coordinate system is output during decoding. In this case, when encoding the first encoded data, the first residual is quantized and the quantized first residual is encoded.

For example, if the calculation of the first residual further includes generating position information in a polar coordinate system by transforming the coordinate system of position information in a Cartesian coordinate system of one three-dimensional point to be encoded, and the first residual is the difference between the transformed position information in the polar coordinate system and the predicted value, the three-dimensional data encoding device generates position information in a Cartesian coordinate system by inversely transforming the coordinate system of the transformed position information in the polar coordinate system. The three-dimensional data encoding device calculates a second residual, which is the difference between the position information in the Cartesian coordinate system and the position information in the Cartesian coordinate system after the inverse transformation. In generating encoded data, the first residual and the second residual are encoded to generate the encoded data. The first identification information indicates that the encoded data includes the first encoded data. The second identification information indicates that the position information in the Cartesian coordinate system is to be output during decoding.

For example, the second identification information indicates whether the coded data of the second residual is included in the bitstream.

For example, a three-dimensional data encoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

The three-dimensional data decoding device according to this embodiment also performs the processing shown in FIG. 61. The three-dimensional data decoding device decodes multiple three-dimensional points in either a rectangular coordinate system or a polar coordinate system. The three-dimensional data decoding device acquires a bitstream including coded data in which a first residual is coded and first identification information indicating whether the coded data includes first coded data calculated in a polar coordinate system (S13031). The three-dimensional data decoding device calculates a predicted value based on position information of one or more candidate points among the multiple decoded three-dimensional points (S13032). The three-dimensional data decoding device calculates the first residual by decoding the coded first residual (S13033). The three-dimensional data decoding device calculates position information of one three-dimensional point to be decoded by adding the predicted value and the first residual. The coordinate system of the calculated position information of one three-dimensional point to be decoded is a coordinate system that depends on whether the coded data includes the first coded data indicated by the first identification information.

This allows the coordinate system of the positional information of one three-dimensional point to be decoded to be determined based on the first identification information indicating whether the encoded data includes first encoded data calculated in a polar coordinate system, so the three-dimensional data decoding device can perform appropriate decoding processing based on the first identification information.

For example, the bitstream further includes second identification information indicating whether position information in a polar coordinate system or position information in a Cartesian coordinate system is to be output during decoding. When the first identification information indicates that the encoded data includes first encoded data, the position information of one or more candidate points used to calculate the predicted value and the position information of one three-dimensional point to be encoded used to calculate the first residual are position information in a polar coordinate system.

For example, if the first identification information indicates that the encoded data does not include the first encoded data, the bitstream does not include the second identification information.

For example, if the second identification information indicates that position information in a polar coordinate system is to be output during decoding, the encoded data is data obtained by quantizing and encoding the first residual. In this case, the coordinate system of the calculated position information of one three-dimensional point to be decoded is a polar coordinate system.

For example, if the first identification information indicates that the encoded data includes the first encoded data and the second identification information indicates that position information in a Cartesian coordinate system is output during decoding, the position information of one three-dimensional point to be decoded is calculated by converting the coordinate system of the position information in a polar coordinate system obtained by adding the predicted value and the first residual, and calculating the position information in the Cartesian coordinate system obtained by the conversion as the position information of one three-dimensional point to be decoded.

For example, if the first identification information indicates that the encoded data includes first encoded data and the second identification information indicates that position information in a Cartesian coordinate system is output during decoding, the encoded data further includes an encoded second residual. The three-dimensional data encoding device calculates the second residual by decoding the encoded second residual. In calculating the position information of one three-dimensional point to be decoded, the device adds the position information in the Cartesian coordinate system obtained by converting the coordinate system to the second residual, and calculates the position information obtained by the addition as the position information of one three-dimensional point to be decoded.

For example, the second identification information indicates whether the coded data of the second residual is included in the bitstream.

For example, a three-dimensional data decoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

(Embodiment 6)
The configuration of a position information encoding unit that encodes the position information of three-dimensional points contained in point cloud data will be described. FIG. 62 is a block diagram showing the configuration of a position information encoding unit when the coordinate system of the input position information and the coordinate system of the position information used for encoding are both Cartesian coordinate systems. That is, this configuration is the configuration of a position information encoding unit when gps_alt_coordinates_flag = 0. Here, in FIGS. 62 to 64, (x, y, z) in a block indicates that processing is performed using a Cartesian coordinate system, and (r, q, f) in a block indicates that processing is performed using a polar coordinate system. A signal with (x, y, z) indicates that the Cartesian coordinate system is used, and a signal with (r, q, f) indicates that the polar coordinate system is used.

The gps_alt_coordinates_flag is included, for example, in the GPS (location information parameter set). The GPS is control information (parameter set) for location information included in the bitstream, and is control information common to multiple frames, multiple point clouds, or multiple slices. The gps_alt_coordinates_flag is information indicating whether a coordinate system other than Cartesian coordinates, such as polar coordinates, is used in the encoding or decoding process of each point. In other words, the gps_alt_coordinates_flag indicates whether the location information encoded data includes first location information encoded data calculated in a polar coordinate system. For example, gps_alt_coordinates_flag = 1 indicates that a polar coordinate system is used in the encoding or decoding process of location information referencing GPS. The gps_alt_coordinates_flag = 0 indicates that a Cartesian coordinate system is used in the encoding or decoding process of location information referencing GPS.

As shown in Figure 62, the position information encoding unit includes a prediction unit 13601, a quantization unit 13602, and an encoding unit 13603. The prediction unit 13601 calculates a predicted value of the position information in the input orthogonal coordinate system, and calculates a residual, which is the difference between the position information and the predicted value. Note that the predicted value and residual calculated here are expressed in the orthogonal coordinate system.

The quantization unit 13602 quantizes the residual in the Cartesian coordinate system. The encoding unit 13603 generates a bitstream by encoding (e.g., entropy encoding or arithmetic encoding) the quantized residual. In other words, in the position information encoding unit shown in Figure 62, all processing is performed in the Cartesian coordinate system.

Figure 63 is a block diagram showing the configuration of the location information encoding unit when the coordinate system of the input location information is a Cartesian coordinate system and the coordinate system of the location information used for encoding is a polar coordinate system. In other words, this configuration is the configuration of the location information encoding unit when gps_alt_coordinates_flag = 1 and gps_coordinate_trans_enabled_flag = 1.

The gps_coordinate_trans_enabled_flag is included in GPS, for example. The gps_coordinate_trans_enabled_flag is information indicating whether or not to perform coordinate transformation (e.g., from a polar coordinate system to a Cartesian coordinate system) of each decoded point before outputting the three-dimensional point from the three-dimensional data decoding device. In other words, the gps_coordinate_trans_enabled_flag indicates whether to output position information in a polar coordinate system or a Cartesian coordinate system during decoding. For example, gps_alt_coordinates_flag = 1 indicates that coordinate transformation is performed, and gps_alt_coordinates_flag = 0 indicates that coordinate transformation is not performed.

As shown in FIG. 63, the position information encoding unit includes a conversion unit 13611, a prediction unit 13612, an encoding unit 13613, a conversion unit 13614, a subtraction unit 13615, a quantization unit 13616, an encoding unit 13617, and a combination unit 13618.

The conversion unit 13611 converts the input position information in the Cartesian coordinate system into position information in the polar coordinate system. The prediction unit 13612 calculates a predicted value for the position information in the polar coordinate system and calculates residual 1, which is the difference between the position information and the predicted value. Note that the predicted value and residual 1 calculated here are expressed in the polar coordinate system. The encoding unit 13613 encodes residual 1 (e.g., entropy encoding or arithmetic encoding).

The conversion unit 13614 restores the position information in the polar coordinate system by adding the predicted value to the residual 1, and converts the position information into position information in the Cartesian coordinate system. The conversion unit 13614 may also convert the polar coordinate system position information generated by the conversion unit 13611 into position information in the Cartesian coordinate system. The subtraction unit 13615 calculates the residual 2, which is the difference between the input Cartesian coordinate system position information and the Cartesian coordinate system position information obtained by the conversion unit 13614. This residual 2 corresponds to the conversion error when the Cartesian coordinate system position information is converted into polar coordinate system position information, and the obtained polar coordinate system position information is converted back into Cartesian coordinate system position information.

The quantization unit 13616 quantizes residual 2 in the Cartesian coordinate system. The encoding unit 13617 encodes (e.g., entropy encoding or arithmetic encoding) the quantized residual 2. The combining unit 13618 generates a bitstream including encoded residual 1 and encoded residual 2.

In this way, in the position information encoding unit shown in Figure 63, position information in the Cartesian coordinate system is converted into position information in the polar coordinate system, and encoding processing (prediction, encoding) is performed on the position information in the polar coordinate system.

Figure 64 is a block diagram showing the configuration of the location information encoding unit when the coordinate system of the input location information and the coordinate system of the location information used for encoding are both polar coordinate systems. In other words, this configuration is the configuration of the location information encoding unit when gps_alt_coordinates_flag = 1 and gps_coordinate_trans_enabled_flag = 0.

As shown in Figure 64, the position information encoding unit includes a prediction unit 13621, a quantization unit 13622, and an encoding unit 13623. The prediction unit 13621 calculates a predicted value of the input position information in the polar coordinate system, and calculates a residual, which is the difference between the position information and the predicted value. Note that the predicted value and residual calculated here are expressed in the polar coordinate system.

The quantization unit 13622 quantizes the residual in the polar coordinate system. The encoding unit 13623 generates a bitstream by encoding (e.g., entropy encoding or arithmetic encoding) the quantized residual. In other words, in the position information encoding unit shown in Figure 64, all processing is performed in the polar coordinate system.

Thus, although the configurations shown in Figures 62 and 64 are similar, the coordinate systems of the data handled in the prediction, quantization, and encoding for calculating residuals are different. Note that the data processing content may differ between the configurations shown in Figures 62 and 64.

The three-dimensional data encoding device may also use the gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag to switch the function of the position information encoding unit to one of those shown in Figures 62 to 64. In other words, the three-dimensional data encoding device may have the three position information encoding units shown in Figures 62 to 64 and switch the position information encoding unit to be used. Alternatively, the three-dimensional data encoding device may use the gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag to switch the presence or absence and content of processing on a processing block basis. This allows common processing blocks to be shared among the processing blocks included in the three position information encoding units shown in Figures 62 to 64, potentially making it possible to realize a position information encoding unit that can achieve the functions of the configurations shown in Figures 62 to 64 with a small configuration.

As mentioned above, the switching of the processes shown in Figures 62 to 64 is indicated by a combination of gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag. Note that this information may be indicated in any form. In other words, the bit stream includes information indicating which of the Cartesian coordinate system and the polar coordinate system is used for the position information output (decoded) by the decoding device. The bit stream also includes information indicating which of the Cartesian coordinate system and the polar coordinate system is used for encoding or decoding. The bit stream also includes information indicating whether coordinate transformation is performed.

Here, point cloud data acquired by a sensor such as LiDAR is data composed of, for example, angle and distance information from the sensor, as well as reflectance, and includes position information in a polar coordinate system. In order to input the polar coordinate system point cloud data output from this sensor into an encoding unit that inputs point cloud data in a Cartesian coordinate system, such as that shown in Figure 62 or 63, the position information of the point cloud data must first be converted from the polar coordinate system to a Cartesian coordinate system. This conversion introduces a conversion error into the position information, so some information is lost when the polar coordinate system is converted to a Cartesian coordinate system. For this reason, it is not possible to convert from the polar coordinate system to a Cartesian coordinate system and then perform a reversible inverse conversion.

On the other hand, by using the configuration shown in Figure 64 and the method described in this embodiment, it is possible to encode data in a polar coordinate system without conversion errors. In other words, lossless compression is possible when encoding point cloud data output from a sensor and decoding the encoded point cloud data.

Next, we will explain the configuration of the position information decoding unit that decodes the bit stream generated by the position information encoding unit.

Figure 65 is a block diagram showing the configuration of a location information decoding unit when the coordinate system of the output location information and the coordinate system of the location information used for decoding are both Cartesian coordinate systems. In other words, this configuration is the configuration of a location information decoding unit when gps_alt_coordinates_flag = 0. For example, this location information decoding unit decodes the bit stream generated by the location information encoding unit shown in Figure 62.

Here, in Figures 65 to 67, (x, y, z) in a block indicates that processing is performed using a Cartesian coordinate system, and (r, q, f) in a block indicates that processing is performed using a polar coordinate system. Signals marked with (x, y, z) indicate that they are signals that use a Cartesian coordinate system, and signals marked with (r, q, f) indicate that they are signals that use a polar coordinate system.

As shown in Figure 65, the position information decoding unit includes a decoding unit 13631, an inverse quantization unit 13632, and a reconstruction unit 13633. The decoding unit 13631 generates residuals (residuals after quantization) by decoding the bitstream (e.g., entropy decoding or arithmetic decoding). The inverse quantization unit 13632 inverse quantizes the residuals obtained by the decoding unit 13631. The reconstruction unit 13633 calculates predicted values and adds the predicted values to the residuals after inverse quantization to generate position information in an orthogonal coordinate system. Note that the predicted values and residuals calculated here are represented in an orthogonal coordinate system. As such, in the position information decoding unit shown in Figure 65, all processing is performed in an orthogonal coordinate system.

Figure 66 is a block diagram showing the configuration of a location information decoding unit when the coordinate system of the output location information is a Cartesian coordinate system and the coordinate system of the location information used for decoding is a polar coordinate system. In other words, this configuration is the configuration of a location information decoding unit when gps_alt_coordinates_flag = 1 and gps_coordinate_trans_enabled_flag = 1. For example, this location information decoding unit decodes the bit stream generated by the location information encoding unit shown in Figure 63.

As shown in FIG. 66, the position information decoding unit includes a separation unit 13641, a decoding unit 13642, a reconstruction unit 13643, a conversion unit 13644, a decoding unit 13645, an inverse quantization unit 13646, and an addition unit 13647.

The separation unit 13641 obtains the coded data of residual 1 and the coded data of residual 2 from the bitstream. The decoding unit 13642 generates residual 1 by decoding (e.g., entropy decoding or arithmetic decoding) the coded data of residual 1. The reconstruction unit 13643 calculates a predicted value and generates position information in a polar coordinate system by adding the predicted value to residual 1 after inverse quantization. Note that the predicted value and residual 1 calculated here are expressed in a polar coordinate system. The conversion unit 13644 converts the position information in the polar coordinate system into position information in a Cartesian coordinate system.

The decoding unit 13645 generates residual 2 (quantized residual 2) by decoding (e.g., entropy decoding or arithmetic decoding) the coded data of residual 2. The inverse quantization unit 13646 inverse quantizes residual 2 obtained by the decoding unit 13645. The predicted value and residual 2 calculated here are expressed in a Cartesian coordinate system.

The addition unit 13647 generates the final position information in the Cartesian coordinate system by adding residual 2 to the position information in the Cartesian coordinate system obtained by the conversion unit 13644.

In this way, the position information decoding unit shown in Figure 66 performs a decoding process (prediction and decoding) on the position information in the polar coordinate system, and the obtained position information in the polar coordinate system is converted into position information in the Cartesian coordinate system.

Figure 67 is a block diagram showing the configuration of a location information decoding unit when the coordinate system of the output location information and the coordinate system of the location information used for decoding are both polar coordinate systems. In other words, this configuration is the configuration of a location information decoding unit when gps_alt_coordinates_flag = 1 and gps_coordinate_trans_enabled_flag = 0. For example, this location information decoding unit decodes the bit stream generated by the location information encoding unit shown in Figure 64.

As shown in Figure 67, the position information decoding unit includes a decoding unit 13651, an inverse quantization unit 13652, and a reconstruction unit 13653. The decoding unit 13651 generates residuals (residuals after quantization) by decoding the bitstream (e.g., entropy decoding or arithmetic decoding). The inverse quantization unit 13652 inverse quantizes the residuals obtained by the decoding unit 13651. The reconstruction unit 13653 calculates predicted values and adds the predicted values to the residuals after inverse quantization to generate position information in a polar coordinate system. Note that the predicted values and residuals calculated here are expressed in a polar coordinate system. As such, in the position information decoding unit shown in Figure 67, all processing is performed in a polar coordinate system.

Thus, although the configurations shown in Figures 65 and 67 are similar, the coordinate systems of the data handled in prediction, inverse quantization, and decoding for calculating residuals are different. Note that the data processing content may differ between the configurations shown in Figures 65 and 67.

The three-dimensional data decoding device may also use the gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag to switch the function of the location information decoding unit to one of those shown in Figures 65 to 67. In other words, the three-dimensional data encoding device may have the three location information decoding units shown in Figures 65 to 67 and switch the location information decoding unit to be used. Alternatively, the three-dimensional data decoding device may use the gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag to switch the presence or absence and content of processing on a processing block basis. This allows the processing blocks included in the three location information decoding units shown in Figures 65 to 67 to be shared, potentially making it possible to realize a location information decoding unit that can achieve the functions of the configurations shown in Figures 65 to 67 with a small configuration.

Next, the configuration of a three-dimensional data encoding device will be described. Figure 68 is a block diagram showing the configuration of a three-dimensional data encoding device that encodes position information and attribute information contained in point cloud data. The three-dimensional data encoding device shown in Figure 68 includes a overlapping point joining unit 13661, a position information encoding unit 13662, an attribute information conversion unit 13663, an attribute information encoding unit 13664, and a joining unit 13665.

If multiple points in the input position information (data A) have the same position information, i.e., if there are duplicate points, the overlapping point merger 13661 merges the multiple points with the same position information into one point. An overlapping point exists when there is already an overlapping point in the input point cloud, or when an overlapping point occurs due to the quantization process.

The position information encoding unit 13662 generates encoded position information data by encoding the merged position information. For example, the position information encoding unit 13662 includes at least one of the three position information encoding units shown in Figures 62 to 64.

When overlapping points are merged, the attribute information conversion unit 13663 generates attribute information for a single merged point from the attribute information for the multiple overlapping points. The attribute information conversion unit 13663 may generate attribute information for a single merged point using any of the multiple overlapping points, or may convert multiple attribute information for multiple overlapping points into attribute information for a single point using a specified method. For example, the attribute information conversion unit 13663 may use the position information before the merge (data A) and the position information after the merge (data B) to determine the value of the attribute information by weighting and adding based on the distance between the merged point and the point before the merge.

The attribute information encoding unit 13664 generates attribute information encoded data by encoding the attribute information obtained by the attribute information conversion unit 13663 based on the position information (data C). Specifically, when encoding attribute information using LoD (Level of Detail), the attribute information encoding unit 13664 generates LoD hierarchies using the position information. Here, LoD is a method of classifying each 3D point into multiple hierarchies using the position information of the 3D points, generating predicted values of the attribute information of the 3D points based on the set hierarchies, and encoding the prediction residual between the attribute information and the predicted values. In other words, the position information is used, for example, to generate predicted values of the attribute information.

Alternatively, the attribute information encoding unit 13664 uses position information when encoding attribute information using RAHT (Region Adaptive Hierarchical Transform) or Haar transform. In these methods, the attribute information encoding unit 13664 generates high-frequency and low-frequency components for each layer and performs quantization and entropy coding on those values. In addition, the position information is used to set two three-dimensional points to be used as a pair for the calculation at the lowest layer.

For example, if the coordinate system of data A is a Cartesian coordinate system, the position information encoding unit 13662 and the attribute information encoding unit 13664 perform processing using position information in the Cartesian coordinate system. In other words, in this case, data B and data C are in Cartesian coordinate systems. In this way, using a Cartesian coordinate system may improve the efficiency of attribute information conversion and attribute information encoding.

Furthermore, for example, if the coordinate system of data A is a polar coordinate system, the position information encoding unit 13662 and the attribute information encoding unit 13664 perform processing using position information in the polar coordinate system. In other words, data B and data C are in polar coordinate systems. This has the potential to improve encoding efficiency. Furthermore, since coordinate conversion processing is not required, the processing volume and processing delay can be reduced. In this way, the three-dimensional data encoding device may be equipped with a configuration that performs processing corresponding to both the Cartesian coordinate system and the polar coordinate system, and may switch between processing in the Cartesian coordinate system and processing in the polar coordinate system based on the coordinate system of the input position information.

The three-dimensional data encoding device may perform encoding in a coordinate system that is more likely to improve encoding efficiency. In other words, the three-dimensional data encoding device may convert the coordinate system of the position information. For example, if the input data is arranged in angular order, the three-dimensional data encoding device may perform encoding using a polar coordinate system regardless of the input coordinate system.

Furthermore, when a three-dimensional data encoding device is equipped with a configuration that processes either a Cartesian coordinate system or a polar coordinate system, if the coordinate system of the input position information differs from the coordinate system of the equipped configuration, the three-dimensional data encoding device may convert the coordinate system of the position information to the coordinate system of the equipped configuration. For example, when the position information encoding unit 13662 and the attribute information encoding unit 13664 support Cartesian coordinate systems, if the coordinate system of data A is a polar coordinate system, the three-dimensional data encoding device converts data B and data C from the polar coordinate system to the Cartesian coordinate system. As a result, when a three-dimensional data encoding device is equipped with a configuration of one coordinate system, it can encode data A in both coordinate systems.

In other words, the attribute information encoding unit 13664 generates attribute information encoded data by encoding the attribute information of one three-dimensional point to be encoded using the position information of the one three-dimensional point to be encoded in a first coordinate system, which is the coordinate system of the position information output during decoding, of the Cartesian coordinate system and the polar coordinate system.

The combining unit 13665 generates a bitstream including position information encoded data and attribute information encoded data.

Next, the configuration of a three-dimensional data decoding device will be described. Figure 69 is a block diagram showing the configuration of a three-dimensional data decoding device that decodes position information and attribute information contained in point cloud data. The three-dimensional data decoding device shown in Figure 69 includes a separation unit 13671, a position information decoding unit 13672, and an attribute information decoding unit 13673.

The separation unit 13671 obtains position information encoded data and attribute information encoded data from the input bit stream. The position information decoding unit 13672 generates position information (data D) by decoding the position information encoded data. For example, the position information decoding unit 13672 includes at least one of the three position information decoding units shown in Figures 65 to 67.

The attribute information decoding unit 13673 generates attribute information by decoding the attribute information encoded data using the decoded position information (data D). Specifically, when the attribute information decoding unit 13673 decodes the attribute information using LoD, it uses the position information to generate an LoD hierarchy. In other words, the position information is used, for example, to generate a predicted value of the attribute information. Alternatively, the attribute information decoding unit 13673 uses the position information when encoding the attribute information using the RAHT or Haar transform.

Here, the coordinate system of the decoded position information (data D) is either a rectangular coordinate system or a polar coordinate system. For example, when decoding is performed using the configuration of Figure 65 or Figure 66, data D is in a rectangular coordinate system, and when decoding is performed using the configuration of Figure 67, data D is in a polar coordinate system.

If the coordinate system of data D is a Cartesian coordinate system, the attribute information decoding unit 13673 performs processing using position information in the Cartesian coordinate system. By using position information in the Cartesian coordinate system, the attribute information decoding unit 13673 may be able to improve the conversion of attribute information and the encoding efficiency of the attribute information. Furthermore, if the coordinate system of data D is a polar coordinate system, the attribute information decoding unit 13673 performs processing using position information in the polar coordinate system. By using position information in the polar coordinate system, the attribute information decoding unit 13673 may be able to improve encoding efficiency. Furthermore, since coordinate conversion processing is not required, the processing volume and processing delay can be reduced. In this way, the three-dimensional data decoding device may be equipped with configurations that perform processing corresponding to both the Cartesian coordinate system and the polar coordinate system, and may switch between processing in the Cartesian coordinate system and processing in the polar coordinate system based on the coordinate system of the input encoded position information data.

Furthermore, when the three-dimensional data decoding device is equipped with a configuration that processes either a Cartesian coordinate system or a polar coordinate system, if the coordinate system of the position information (data D) from the position information decoding unit 13672 differs from the coordinate system of the equipped configuration, the coordinate system of the position information may be converted to the coordinate system of the equipped configuration. For example, when the attribute information decoding unit 13673 supports a Cartesian coordinate system, if the coordinate system of the position information (data D) is a polar coordinate system, the three-dimensional data decoding device converts data D from the polar coordinate system to a Cartesian coordinate system. As a result, when the three-dimensional data decoding device is equipped with a configuration of one of the coordinate systems, it can decode attribute information based on data D in the polar coordinate system and data D in the Cartesian coordinate system.

In this way, the attribute information decoding unit 13673 generates attribute information for one three-dimensional point to be decoded by decoding the attribute information encoded data using the position information of the one three-dimensional point to be decoded in a first coordinate system, which is a coordinate system of the position information of the one three-dimensional point to be decoded, either a Cartesian coordinate system or a polar coordinate system.

The data D input to the attribute information decoding unit 13673 may be normalized so that the data value falls within a certain range. For example, if the data D is in a Cartesian coordinate system, the three-dimensional data decoding device may derive the maximum value of the position information based on the coordinates (x, y, z) of the points that make up the point cloud or information about the bounding box that encompasses the point cloud, and normalize the value of the position information of the data D based on the derived maximum value. Furthermore, if the data D is in a polar coordinate system, the three-dimensional data decoding device may derive the maximum value based on the distance r from the origin to the points that make up the point cloud, and normalize the value of the position information of the data D based on the derived maximum value. For example, the three-dimensional data decoding device may divide the value of the position information of the data D by the derived maximum value.

In addition, the position information decoding unit 13672 may derive the above-mentioned maximum value or bounding box information and output it to the attribute information decoding unit 13673, which may then normalize the data D using the maximum value or bounding box information. In this way, by having the attribute information decoding unit 13673 perform normalization based on the information output from the position information decoding unit 13672, it may be possible to reduce the processing amount and processing delay of the process of deriving the maximum value in the attribute information decoding unit 13673.

Note that, while an example of normalization in a three-dimensional data decoding device has been described above, similar processing may also be performed on data C in a three-dimensional data encoding device. Furthermore, the position information encoding unit 13662, like the position information decoding unit 13672, may derive maximum value or bounding box information and output it to the attribute information encoding unit 13664, and the attribute information encoding unit 13664 may then normalize data C using the maximum value or bounding box information.

Also, above, a coordinate system in which position information is represented by (x, y, z) was described as a Cartesian coordinate system, but it is sometimes called a Cartesian coordinate system. Also, a coordinate system in which position information is represented by (r, q, f) was described as a polar coordinate system, but it is sometimes called a spherical coordinate system.

Figure 70 is a flowchart of the three-dimensional data decoding process according to this embodiment. First, the three-dimensional data decoding device decodes position information from the bit stream (S13601). Next, as process 1 (S13602), the three-dimensional data decoding device determines the coordinate system of the position information to be used in decoding the attribute information. Specifically, if the position information has been decoded in a polar coordinate system (Yes in S13611), the three-dimensional data decoding device determines to decode the attribute information using position information in the polar coordinate system (S13612). On the other hand, if the position information has not been decoded in a polar coordinate system (No in S13611), that is, if the position information has been decoded in a Cartesian coordinate system, the three-dimensional data decoding device determines to decode the attribute information using position information in the Cartesian coordinate system (S13613).

Next, as process 2 (S13603), the three-dimensional data decoding device normalizes the position information used to decode the attribute information. Specifically, if it is determined that position information in a polar coordinate system is to be used to decode the attribute information (Yes in S13621), the three-dimensional data decoding device normalizes the position information in the polar coordinate system (S13623). For example, as described above, the three-dimensional data decoding device performs normalization based on the distance r from the origin to the points that make up the point cloud. For example, the three-dimensional data decoding device divides the value of the position information of data D by the maximum value of the distance r.

On the other hand, if the three-dimensional data decoding device determines that polar coordinate system position information will not be used to decode the attribute information (No in S13621), that is, if it determines that Cartesian coordinate system position information will be used to decode the attribute information, it converts the Cartesian coordinate system position information into polar coordinate system position information (S13622) and normalizes the obtained polar coordinate system position information (S13623).

Next, the three-dimensional data decoding device encodes the attribute information using the normalized position information. Note that when the three-dimensional data decoding device decodes the attribute information using position information in a Cartesian coordinate system, it may convert the normalized position information into a Cartesian coordinate system and decode the attribute information using the obtained position information. Alternatively, when the three-dimensional data decoding device decodes the attribute information using position information in a Cartesian coordinate system, it may normalize the position information in the Cartesian coordinate system without performing the coordinate conversion in step S13622.

As described above, the three-dimensional data encoding device according to this embodiment performs the processing shown in FIG. 71. The three-dimensional data encoding device encodes a plurality of three-dimensional points. The three-dimensional data encoding device calculates a predicted value based on position information of one or more candidate points from among the plurality of encoded three-dimensional points (S13631), calculates a first residual, which is the difference between the predicted value and the position information of one three-dimensional point to be encoded from among the plurality of three-dimensional points (S13632), generates encoded position information data by encoding the first residual (S13633), and generates first identification information (e.g., gps_alt_coordinates_flag) indicating whether the encoded position information data includes first encoded position information data calculated in a polar coordinate system (S13634).

The three-dimensional data encoding device generates attribute information encoded data by encoding the attribute information of one three-dimensional point to be encoded using position information of the one three-dimensional point to be encoded in a first coordinate system, which is the coordinate system of the position information output during decoding, of either a Cartesian coordinate system or a polar coordinate system (S13635).The three-dimensional data encoding device generates a bit stream including the position information encoded data, the first identification information, and the attribute information encoded data (S13636).

With this, the three-dimensional data encoding device encodes attribute information using first coordinates, which are the coordinate system of the position information output during decoding. This improves encoding efficiency. In addition, the amount of processing can be reduced because coordinate conversion processing and the like are no longer necessary.

For example, when the first coordinate system is a polar coordinate system, the three-dimensional data encoding device normalizes the position information in the polar coordinate system of one three-dimensional point to be encoded, and encodes the attribute information of the one three-dimensional point to be encoded using the position information in the normalized polar coordinate system. This allows the three-dimensional data encoding device to limit the range of position information values used to decode the attribute information, thereby reducing the amount of processing.

For example, when generating encoded position information data, the three-dimensional data encoding device generates information indicating the maximum value of multiple three-dimensional coordinates or a bounding box encompassing multiple three-dimensional points, uses the generated information to normalize the position information in a first coordinate system of one three-dimensional point to be encoded, and encodes the attribute information of the one three-dimensional point to be encoded using the normalized position information in the first coordinate system. This allows the three-dimensional data encoding device to reduce the amount of processing required to decode the attribute information.

For example, if the position information of one or more candidate points used to calculate the predicted value and the position information of one three-dimensional point to be encoded used to calculate the first residual are position information in a polar coordinate system, the first identification information indicates that the position information encoded data includes first position information encoded data, and the bitstream further includes second identification information (gps_coordinate_trans_enabled_flag) indicating whether position information in a polar coordinate system or position information in a Cartesian coordinate system is output during decoding.

For example, if the first identification information indicates that the position information encoding data does not include the first position information encoding data, the bitstream does not include the second identification information.

For example, when encoding, the first residual is quantized and the quantized first residual is encoded, the second identification information indicates that position information in a polar coordinate system is output when decoding.

For example, when calculating the first residual, the three-dimensional data encoding device further generates position information in a polar coordinate system by transforming the coordinate system of the position information in the Cartesian coordinate system of one three-dimensional point to be encoded, and if the first residual is the difference between the position information in the polar coordinate system after the transformation and the predicted value, the three-dimensional data encoding device further generates position information in a Cartesian coordinate system by inversely transforming the coordinate system of the position information in the polar coordinate system after the transformation, and calculates a second residual that is the difference between the position information in the Cartesian coordinate system and the position information in the Cartesian coordinate system after the inverse transformation, and when generating the position information encoded data, generates position information encoded data by encoding the first residual and the second residual, the first identification information indicates that the position information encoded data includes the first position information encoded data, and the second identification information indicates that the position information in the Cartesian coordinate system is to be output during decoding.

For example, a three-dimensional data encoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

The three-dimensional data decoding device according to this embodiment also performs the processing shown in FIG. 72. The three-dimensional data decoding device decodes multiple three-dimensional points. The three-dimensional data decoding device acquires a bitstream including position information encoded data in which a first residual is encoded, first identification information (e.g., gps_alt_coordinates_flag) indicating whether the position information encoded data includes first position information encoded data calculated in a polar coordinate system, and attribute information encoded data (S13641). The three-dimensional data decoding device calculates a predicted value based on position information of one or more candidate points among the multiple decoded three-dimensional points (S13642), calculates a first residual by decoding the encoded first residual (S13643), and calculates position information of one three-dimensional point to be decoded by adding the predicted value and the first residual (S13644). The first coordinate system, which is the coordinate system of the position information of the one three-dimensional point to be decoded and is either a Cartesian coordinate system or a polar coordinate system, is a coordinate system that depends on whether or not the first position information encoded data indicated by the first identification information is included. The three-dimensional data decoding device generates attribute information of the one three-dimensional point to be decoded by decoding the attribute information encoded data using the position information in the first coordinate system of the one three-dimensional point to be decoded (S13645).

With this, the three-dimensional data decoding device decodes the attribute information using the position information of the first coordinate. This improves encoding efficiency. In addition, the amount of processing can be reduced because coordinate conversion processing and the like are no longer necessary.

For example, when the first coordinate system is a polar coordinate system, the three-dimensional data decoding device normalizes the position information in the polar coordinate system of one three-dimensional point to be decoded, and decodes the attribute information encoded data using the position information in the normalized polar coordinate system. This allows the three-dimensional data decoding device to limit the range of position information values used to decode the attribute information, thereby reducing the amount of processing.

For example, when calculating the position information of a single 3D point to be decoded, the 3D data decoding device generates information indicating the maximum value of multiple 3D coordinates or a bounding box encompassing multiple 3D points, uses the generated information to normalize the position information in a first coordinate system of the single 3D point to be decoded, and decodes the attribute information encoded data using the normalized position information in the first coordinate system. This allows the 3D data decoding device to reduce the amount of processing required to decode the attribute information.

For example, the bitstream further includes second identification information (gps_coordinate_trans_enabled_flag) indicating whether position information in a polar coordinate system or position information in a Cartesian coordinate system is output during decoding, and when the first identification information indicates that the position information encoded data includes first position information encoded data, the position information of one or more candidate points used to calculate the predicted value and the position information of one three-dimensional point to be encoded used to calculate the first residual are position information in a polar coordinate system.

For example, if the first identification information indicates that the position information encoding data does not include the first position information encoding data, the bitstream does not include the second identification information.

For example, if the second identification information indicates that position information in a polar coordinate system is to be output during decoding, the coordinate system of the calculated position information of one three-dimensional point to be decoded is a polar coordinate system.

For example, when the first identification information indicates that the position information encoded data includes first position information encoded data and the second identification information indicates that position information in a Cartesian coordinate system is to be output during decoding, the three-dimensional data decoding device calculates the position information of one three-dimensional point to be decoded by converting the coordinate system of the position information in a polar coordinate system obtained by adding the predicted value and the first residual, and calculating the position information in the Cartesian coordinate system obtained by the conversion as the position information of one three-dimensional point to be decoded.

For example, if the first identification information indicates that the position information encoded data includes first position information encoded data and the second identification information indicates that decoding outputs position information in a Cartesian coordinate system, the position information encoded data further includes an encoded second residual, and the three-dimensional data decoding device further calculates the second residual by decoding the encoded second residual, and in calculating the position information of one three-dimensional point to be decoded, adds the position information in the Cartesian coordinate system obtained by converting the coordinate system to the second residual, and calculates the position information obtained by the addition as the position information of one three-dimensional point to be decoded.

For example, a three-dimensional data decoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

Seventh Embodiment
In this embodiment, the encoding process and decoding process of the position information when the coordinate system of the position information of the three-dimensional point group is a Cartesian coordinate system and a polar coordinate system will be described. First, the encoding process will be described.

Figure 73 is a block diagram showing the configuration of the position information encoding unit 13700 when the coordinate system of the position information of the input three-dimensional point cloud is a Cartesian coordinate system. The position information encoding unit 13700 is included in a three-dimensional data encoding device and comprises a shift unit 13701 and an encoding unit 13702.

In Figure 73 and elsewhere, information marked with (x, y, z) indicates that the Cartesian coordinate system is used, and information marked with (r, θ, φ) indicates that the polar coordinate system is used. Here, r is the distance from the origin to a point that makes up the point cloud, θ is the horizontal angle at which the point that makes up the point cloud is located on a horizontal plane including the origin, and φ is the elevation angle at which the point that makes up the point cloud is located from the origin.

The shifting unit 13701 generates shifted position information in the Cartesian coordinate system by shifting the position information in the Cartesian coordinate system. The encoding unit 13702 generates a bitstream by encoding the shifted position information.

Figure 74 is a diagram showing an example of shift processing when the input position information is in a Cartesian coordinate system and the position information in the Cartesian coordinate system is encoded. As shown in Figure 74, when the input position information is in a Cartesian coordinate system, the shift unit 13701 shifts the coordinates of the point cloud (position information) before encoding the position information. For example, when encoding the position information using a Cartesian coordinate system, the shift unit 13701 shifts (subtracts) the coordinates of the point cloud so that the coordinates of the bounding box of the point cloud (e.g., the coordinates of the lower left corner) become the origin. The shift unit 13701 may also shift the coordinates of the point cloud so that the center of the coordinates of the bounding box of the point cloud becomes the origin.

Note that the example shown in Figure 74 is a diagram of two arbitrary axes, and shifting is not limited to this. In other words, shifting refers to movement of position along at least one axis.

Figure 75 is a diagram showing an example of shift processing when input position information is in a Cartesian coordinate system and position information in a polar coordinate system is encoded. For example, the example shown in Figure 75 is a case where position information in a Cartesian coordinate system is converted to position information in a polar coordinate system and the position information in the polar coordinate system is encoded. When encoding using a polar coordinate system, the shift unit 13701 shifts the coordinates of the Cartesian coordinate system of the point cloud so that the position of a sensor such as LiDAR that acquires the point cloud becomes the origin. A conversion unit (not shown in Figure 73) converts the position information in the Cartesian coordinate system into position information in a polar coordinate system. The conversion unit is arranged between the shift unit 13701 and the encoding unit 13702.

Note that the shifted coordinates are not limited to the above example, and may be set to coordinates that can improve encoding efficiency. For example, by shifting the position information, the value of the position information, i.e., the absolute value, can be reduced, thereby reducing the amount of encoding. In another example, by shifting the position information, it is possible to obtain position information with a value close to that of already encoded position information, thereby improving encoding efficiency. Furthermore, the encoding unit 13702 may include coordinate information regarding the shifted coordinates (for example, information indicating the origin before the shift, or information indicating the shift amount) in the bitstream as metadata. Note that the shift amount may be represented by a single value common to each component in the coordinate system, or may be represented by a value for each component, and the values for each component may be the same or different. Furthermore, the metadata may or may not be encoded.

Figure 76 is a block diagram showing the configuration of the position information encoding unit 13710 when the coordinate system of the position information of the input three-dimensional point cloud is a polar coordinate system. The position information encoding unit 13710 is included in a three-dimensional data encoding device and has an encoding unit 13711.

Figure 77 is a diagram showing an example of processing when the input position information is in a polar coordinate system and the position information in the polar coordinate system is encoded. As shown in Figure 77, the position information of the input point cloud is in a polar coordinate system and the position of the sensor, such as LiDAR, that acquires the point cloud is the origin, so the position information encoding unit 13710 does not shift the coordinates of the position information. Note that the position of the sensor, such as LiDAR, that acquires the point cloud does not have to be the origin. If the position of the sensor does not coincide with the origin, the position information in the polar coordinate system may be shifted, for example, so that the position of the sensor coincides with the origin. However, the shifting of the position information in the polar coordinate system is not limited to this example. The encoding unit 13711 generates a bitstream by encoding the input position information in the polar coordinate system as is.

The encoding unit 13711 may also include sensor position information indicating the coordinates of the sensor position in the bitstream as metadata.

In addition, the three-dimensional data encoding device may be equipped with both the position information encoding unit 13700 shown in Figure 73 and the position information encoding unit 13710 shown in Figure 76, or may be equipped with only one of them.

Next, we will explain the decoding process for decoding the bit stream generated above. Figure 78 is a block diagram showing the configuration of a position information decoding unit 13720 that decodes a bit stream generated by encoding position information in a Cartesian coordinate system. In other words, the position information decoding unit 13720 outputs position information in a Cartesian coordinate system. The position information decoding unit 13720 is included in a three-dimensional data decoding device, and comprises a decoding unit 13721 and an inverse shift unit 13722. Note that the example shown in Figure 78 is a case where the position information in the Cartesian coordinate system is restored by decoding a bit stream generated by encoding position information after shifting in a Cartesian coordinate system, and performing an inverse shift process on the obtained position information based on the coordinate information.

The decoding unit 13721 obtains post-shift position information in the Cartesian coordinate system by decoding the bitstream. The decoding unit 13721 also obtains coordinate information, which is metadata, from the bitstream (for example, information indicating the origin before the shift, or information indicating the shift amount).

The inverse shift unit 13722 inversely shifts (adds) the decoded shifted position information by the shift amount indicated in the shift information, which is metadata. Note that this shift amount is a value calculated based on the difference between the origin coordinates before the shift and the origin coordinates after the shift. This makes it possible for the three-dimensional data decoding device to restore the point cloud input to the three-dimensional data encoding device.

Figure 79 is a block diagram showing the configuration of a position information decoding unit 13730 that decodes a bit stream generated by encoding position information in a polar coordinate system. In other words, the position information decoding unit 13730 outputs position information in a polar coordinate system. The position information decoding unit 13730 is included in a three-dimensional data decoding device and has a decoding unit 13731.

The decoding unit 13731 obtains position information in the polar coordinate system by decoding the bitstream. The decoding unit 13731 also obtains sensor position information, which is metadata indicating the coordinates of the sensor's position, from the bitstream. The position information decoding unit 13730 outputs the decoded position information in the polar coordinate system as is without shifting it.

Note that the polar coordinate system may be expressed using parameters other than (r, θ, φ). For example, (r, φ, ι) may be used. Here, r is the radius when the point is projected onto the x-y plane, and ι is an index representing the height or θ.

In addition, the three-dimensional data decoding device may be equipped with both the position information decoding unit 13720 shown in FIG. 78 and the position information decoding unit 13730 shown in FIG. 79, or may be equipped with only one of them.

Below, we will explain a modified example of the above configuration. For example, the shift unit 13701 may be shared between the configuration shown in Figure 73 and the configuration shown in Figure 76. In this case, if the input position information is in a polar coordinate system, the three-dimensional data encoding device sets the shift amount in the shift processing of the shift unit 13701 to 0. This makes it possible to reduce implementation costs.

The three-dimensional data encoding device may also switch whether to perform shift processing based on whether the coordinate system of the input position information is a Cartesian coordinate system or a polar coordinate system. Figure 80 is a block diagram showing the configuration of the position information encoding unit 13740 in this case. The position information encoding unit 13740 is included in the three-dimensional data encoding device, and comprises a switching unit 13741, a shift unit 13742, and an encoding unit 13743.

If the input position information is position information in a Cartesian coordinate system, the switching unit 13741 outputs the position information to the shifting unit 13742. Furthermore, if the input position information is position information in a polar coordinate system, the switching unit 13741 outputs the position information to the encoding unit 13743.

The shifting unit 13742 generates shifted position information in a Cartesian coordinate system by shifting the position information in the Cartesian coordinate system. The encoding unit 13743 generates a bit stream by encoding the shifted position information. The encoding unit 13743 also generates a bit stream by encoding the position information in a polar coordinate system. The encoding unit 13743 also stores the sensor position information in the bit stream. Note that the encoding unit 13743 may store the sensor position information in the bit stream only when the position information is expressed in a polar coordinate system.

With this configuration, the position information encoding unit 13740 can reduce the amount of processing by not performing shift processing when the position information is in a polar coordinate system.

Alternatively, the configuration may include the configuration shown in Figure 78 and the configuration shown in Figure 79, and each decoding unit may output shifted position information in a Cartesian coordinate system or a polar coordinate system to the inverse shift unit 13722. In this case, if the output position information is in a polar coordinate system, the inverse shift unit 13722 sets the shift amount to 0 regardless of the value of the sensor position information. In other words, the inverse shift unit 13722 does not perform a shift. Alternatively, the three-dimensional data decoding device may determine that the bit stream is a non-compliant stream if the sensor position information is not 0. This makes it possible to reduce implementation costs.

The three-dimensional data decoding device may also switch whether to perform reverse shift processing based on whether the coordinate system of the output position information is a Cartesian coordinate system or a polar coordinate system. Figure 81 is a block diagram showing the configuration of the position information decoding unit 13750 in this case. The position information decoding unit 13750 is included in the three-dimensional data decoding device, and comprises a decoding unit 13751, a reverse shift unit 13752, and a switching unit 13753.

The decoding unit 13751 decodes the bit stream to generate shifted position information in a Cartesian coordinate system or position information in a polar coordinate system. Furthermore, when the decoding unit 13751 decodes position information in a polar coordinate system, it obtains sensor position information from the bit stream.

Here, the decoding unit 13751 may use the gps_alt_coordinates_flag and gps_coordinate_trans_enabled_flag shown in embodiment 6 as information indicating the coordinate system of the position information encoded by the three-dimensional data encoding device.

gps_alt_coordinates_flag is information that indicates whether a coordinate system other than Cartesian coordinates, such as polar coordinates, is used in the encoding or decoding process of each point. For example, gps_alt_coordinates_flag = 1 indicates that a polar coordinate system is used in the encoding or decoding process of location information that references GPS, and gps_alt_coordinates_flag = 0 indicates that a Cartesian coordinate system is used in the encoding or decoding process of location information that references GPS.

gps_coordinate_trans_enabled_flag indicates whether to output location information in the polar coordinate system or the Cartesian coordinate system during decoding. For example, gps_alt_coordinates_flag = 1 indicates that coordinate transformation of location information referencing GPS is performed, and gps_alt_coordinates_flag = 0 indicates that coordinate transformation of location information referencing GPS is not performed.

Based on this information, decoding processing is performed in the decoding unit 13751, and shifted position information in the Cartesian coordinate system or position information in the polar coordinate system is output.

The inverse shift unit 13752 generates position information in the Cartesian coordinate system by inversely shifting the shifted position information in the Cartesian coordinate system.

The switching unit 13753 outputs the decoded location information if it is location information in a Cartesian coordinate system, and outputs the location information if it is location information in a polar coordinate system. The switching unit 13753 may also perform switching based on the information in the gps_coordinate_trans_enabled_flag.

The above-described operation examples of the decoding unit 13751 and the switching unit 13753 were based on the gps_alt_coordinates_flag and the gps_coordinate_trans_enabled_flag, but the decoding unit 13751 and the switching unit 13753 may operate based on other information. For example, the decoding unit 13751 and the switching unit 13753 may operate based on information (e.g., mode information) included in the bitstream that indicates the combination of the input coordinate system, whether or not the coordinate system is converted, and the output coordinate system.

With this configuration, the location information decoding unit 13750 can reduce the amount of processing by not performing reverse shift processing when the location information is in a polar coordinate system.

Note that the examples shown in Figures 80 and 81 are examples where the coordinate system of the position information input to the three-dimensional data encoding device is the same as the coordinate system of the position information output from the three-dimensional data decoding device. For example, if the coordinate system of the position information input to the three-dimensional data encoding device (for example, the position information shown in Figure 80) is a Cartesian coordinate system, then the coordinate system output from the three-dimensional data decoding device (the position information shown in Figure 81) is also a Cartesian coordinate system. Furthermore, if the coordinate system of the position information input to the three-dimensional data encoding device is a polar coordinate system, then the coordinate system output from the three-dimensional data decoding device is also a polar coordinate system.

In contrast, when the decoded position information is in a polar coordinate system, the three-dimensional data decoding device may convert the position information into position information in a Cartesian coordinate system and output the converted position information in the Cartesian coordinate system. Figure 82 is a block diagram showing the configuration of the position information decoding unit 13760 in this case. The position information decoding unit 13760 is included in the three-dimensional data decoding device and comprises a decoding unit 13761, a coordinate conversion unit 13762, a shifting unit 13763, and a switching unit 13764. Note that the shifting unit 13763 performs any shift, not just an inverse shift corresponding to the shift on the encoding side. Furthermore, the coordinate system of the position information output from the switching unit 13764 is not limited to that specified by the encoding side, but may be any coordinate system. The arbitrary shift and arbitrary coordinate system can be determined, for example, by user instructions or settings.

The decoding unit 13761 includes, for example, the position information decoding unit 13750 shown in FIG. 81. The decoding unit 13761 generates position information in a Cartesian coordinate system or position information in a polar coordinate system by decoding the bit stream. Furthermore, when the decoding unit 13761 decodes position information in a polar coordinate system, it obtains sensor position information from the bit stream.

The coordinate conversion unit 13762 converts the position information in the polar coordinate system into position information in the Cartesian coordinate system. The shift unit 13763 shifts the position information in the Cartesian coordinate system obtained by the coordinate conversion unit 13762 using the sensor position information. For example, the shift unit 13763 adds the position (coordinates) of the sensor indicated by the sensor position information to the position information of the point cloud.

The switching unit 13764 outputs the position information if the decoded position information is position information in a Cartesian coordinate system, outputs the position information if the decoded position information is position information in a polar coordinate system and no coordinate conversion is performed, and outputs the shifted polar coordinate system position information obtained by the shift unit 13763 if the decoded position information is position information in a polar coordinate system and coordinate conversion is performed.

By performing encoding and decoding using the above configuration, it is possible to realize a three-dimensional data encoding method and a three-dimensional data decoding method that can handle any combination of cases where the coordinate system of the position information of the point cloud input to the three-dimensional data encoding device is a Cartesian coordinate system or a polar coordinate system, and cases where the coordinate system of the position information of the point cloud output from the three-dimensional data decoding device is a Cartesian coordinate system or a polar coordinate system.

Figure 83 is a flowchart of the three-dimensional data decoding process. For example, this is a flowchart of the three-dimensional data decoding process in the position information decoding unit 13750 shown in Figure 81. First, the three-dimensional data decoding device decodes position information from the bit stream (S13701). Next, the three-dimensional data decoding device determines whether the decoding of the position information will be performed in a polar coordinate system or a Cartesian coordinate system (S13702). In other words, the three-dimensional data decoding device determines whether the bit stream was generated by encoding position information in a polar coordinate system or by encoding position information in a Cartesian coordinate system. For example, the three-dimensional data decoding device makes this determination based on the gps_alt_coordinates_flag included in the bit stream.

If the three-dimensional data decoding device determines that the decoding of the position information should be performed in the polar coordinate system (Yes in S13702), it decodes the position information in the polar coordinate system (S13703). Next, the three-dimensional data decoding device determines whether to output position information in the polar coordinate system or in the Cartesian coordinate system (S13705). For example, this determination may be made based on the gps_coordinate_trans_enabled_flag input from outside the three-dimensional data decoding device, or may be made based on information contained in the bitstream.

If the three-dimensional data decoding device outputs position information in the polar coordinate system (Yes in S13705), it outputs the position information in the polar coordinate system obtained in step S13703 (S13708).

On the other hand, if the three-dimensional data decoding device outputs position information in the Cartesian coordinate system (No in S13705), it converts the position information in the polar coordinate system obtained in step S13703 into position information in the Cartesian coordinate system (S13706). Next, the three-dimensional data decoding device inversely shifts the converted position information in the Cartesian coordinate system using the shift amount (S13707), and outputs the shifted position information in the Cartesian coordinate system (S13708).

Also, in step S13702, if the three-dimensional data decoding device determines that the decoding of the position information is to be performed in a Cartesian coordinate system (No in S13702), it decodes the position information in the Cartesian coordinate system (S13704). Next, the three-dimensional data decoding device shifts the obtained position information in the Cartesian coordinate system using the coordinate information (S13707), and outputs the position information in the Cartesian coordinate system after the shift (S13708).

Next, an example of metadata will be described. Figures 84 and 85 are diagrams showing syntax related to shift information (the above-mentioned sensor position coordinates or coordinate information (e.g., information indicating the origin before the shift, or information indicating the shift amount)).

For example, if the coordinate system of the point cloud position information input to the three-dimensional data encoding device or the point cloud position information output from the three-dimensional data decoding device is a Cartesian coordinate system, the bit stream includes shift information. Also, if the coordinate system of the point cloud input to the three-dimensional data encoding device or the point cloud output from the three-dimensional data decoding device is a polar coordinate system, the bit stream does not include shift information. This allows the amount of information to be reduced, thereby improving encoding efficiency.

Figure 84 shows an example of the syntax of GPS (geometry_parameter_set). Here, the coded data of the point cloud's position information is divided into multiple GDUs (geometry data units), which are divided data units, and stored in the bitstream. Note that a divided data unit is, for example, a slice, tile, or other subspace. GPS (geometry parameter set) is a parameter set (control information or header) common to multiple GDUs.

As shown in FIG. 84, GPS includes gps_alt_coordinates_flag, gps_coordinate_trans_enabled_flag, and shift information (origin_x, origin_y, origin_z).

The shift information is, for example, the sensor position coordinates or coordinate information described above (for example, information indicating the origin before the shift, or information indicating the shift amount), and indicates, for example, the coordinates to which the origin is shifted (i.e., the shift amount) when shifting position information in a three-dimensional data decoding device. Note that while Figure 84 shows the shift amount in a Cartesian coordinate system, the shift amount may also be expressed in a polar coordinate system.

gps_alt_coordinates_flag indicates whether the encoded location information is in polar coordinates or Cartesian coordinates. For example, if the encoded location information is in polar coordinates, gps_alt_coordinates_flag is set to the value 1, and if the encoded location information is in Cartesian coordinates, gps_alt_coordinates_flag is set to the value 0.

For example, gps_coordinate_trans_enabled_flag is included in GPS when the encoded location information is in a polar coordinate system, and is not included in GPS when the encoded location information is in a Cartesian coordinate system. If the encoded location information is in a Cartesian coordinate system and the value of gps_alt_coordinates_flag is 0, gps_coordinate_trans_enabled_flag is presumed to be 0. In other words, if gps_coordinate_trans_enabled_flag is not encoded, the value of gps_coordinate_trans_enabled_flag is presumed to be 0. The gps_coordinate_trans_enabled_flag indicates whether or not the 3D data decoding device performs coordinate transformation to convert the decoded position information from the polar coordinate system into the Cartesian coordinate system. For example, if coordinate transformation is performed, the gps_coordinate_trans_enabled_flag is set to a value of 1, and if coordinate transformation is not performed, the gps_coordinate_trans_enabled_flag is set to a value of 0.

For example, GPS does not include shift information (origin_x, origin_y, origin_z) when the encoded position information is in a polar coordinate system and coordinate conversion is not performed (i.e., when the three-dimensional data decoding device outputs position information in a polar coordinate system), but includes shift information in other cases. In other words, GPS includes shift information when the encoded position information is in a Cartesian coordinate system. Also, GPS includes shift information when the encoded position information is in a polar coordinate system and coordinate conversion is performed. In other words, GPS includes shift information when the three-dimensional data decoding device outputs position information in a Cartesian coordinate system.

Figure 85 shows an example of the syntax of the GDU header (geometry_dataunit_set). The GDU header is the header (control information) for each GDU. The GDU header contains shift information (origin_x, origin_y, origin_z) and is encoded.

For example, the GDU header does not include shift information (origin_x, origin_y, origin_z) if the encoded position information is in a polar coordinate system and coordinate conversion is not performed (i.e., if the three-dimensional data decoding device outputs position information in a polar coordinate system), but includes shift information in other cases. In other words, the GDU header includes shift information if the encoded position information is in a Cartesian coordinate system. Also, the GDU header includes shift information if the encoded position information is in a polar coordinate system and coordinate conversion is performed. In other words, the GDU header includes shift information if the three-dimensional data decoding device outputs position information in a Cartesian coordinate system. This allows the amount of information to be reduced, thereby improving encoding efficiency.

Note that the shift information may be included in either the GPS or GDU header, or in both. Note that if shift information is included in both the GPS and GDU headers and their values are different, the three-dimensional data decoding device may prioritize the shift information included in the GDU header. Furthermore, if shift information is not included in the bit stream, the three-dimensional data decoding device may consider the values of the coordinates (x, y, z) indicated by the shift information to be 0 on all three axes.

Also, as shown in FIG. 82, when the coordinate system of the point cloud position information input to the three-dimensional data encoding device or the point cloud position information decoded by the three-dimensional data decoding device is a polar coordinate system, the bit stream includes shift information, and the three-dimensional data decoding device may convert the decoded polar coordinate system position information into position information in a Cartesian coordinate system, and shift the Cartesian coordinate system position information using the shift information.

When performing such coordinate transformation, the shift information may be stored in either the GPS or GDU header as described above, or in a sequence-based parameter set other than the GPS and GDU headers (e.g., SPS). For example, to indicate the amount of shift in the position information after combining GDUs, the shift information may be stored in the GDU header but not in the GPS. Furthermore, the shift information may be stored in both the GPS and GDU headers, or may be stored in at least one of the GPS and GDU headers and one or more parameter sets or headers other than the GPS and GDU headers.

In addition, regardless of the coordinate system of the point cloud position information input to the three-dimensional data encoding device and the point cloud position information output from the three-dimensional data decoding device, the bit stream may always include shift information.

As described above, the three-dimensional data decoding device according to this embodiment performs the processing shown in FIG. 86. The three-dimensional data decoding device acquires a bit stream including encoded position information in which the position information of three-dimensional points is encoded (S13711), and generates position information by decoding the encoded position information (S13712). If the position information is expressed in a Cartesian coordinate system (Yes in S13713), the three-dimensional data decoding device shifts the position information (S13714), and if the position information is expressed in a polar coordinate system (No in S13713), it does not shift the position information.

This allows the three-dimensional data decoding device to switch whether to perform shift processing on the position information depending on whether the encoded position information is in a Cartesian coordinate system or a polar coordinate system. Here, if the position information is in a Cartesian coordinate system, the three-dimensional data encoding device performs shift processing before encoding, thereby improving encoding efficiency. If the position information is in a Cartesian coordinate system, the three-dimensional data decoding device performs shift processing, thereby allowing the device to properly decode a bitstream with improved encoding efficiency. Furthermore, if the position information is in a polar coordinate system, the three-dimensional data decoding device does not perform shift processing, thereby reducing the amount of processing. Furthermore, if the position information is in a polar coordinate system, not performing shift processing can eliminate errors that occur when converting polar coordinate position information to Cartesian coordinate position information. As a result, three-dimensional points can be encoded without errors.

In addition, the three-dimensional data decoding device derives position information of the three-dimensional point from the bit stream, and if the position information is expressed in Cartesian coordinates, shifts the first position indicated by the position information, and the shift does not have to be performed if the position information is expressed in a polar coordinate system.

In addition, the three-dimensional data decoding device may further determine whether the position information is represented in a Cartesian coordinate system or a polar coordinate system based on shift information contained in the bitstream.

In addition, the bit stream (e.g., shift information) may include first flag information (e.g., gps_alt_coordinates_flag) indicating whether the position information is expressed in a polar coordinate system, and second flag information (e.g., gps_coordinate_trans_enabled_flag) indicating whether the position information expressed in the polar coordinate system is converted into transformed position information expressed in a Cartesian coordinate system.

Note that if the position information is expressed in a polar coordinate system and the second position of the sensor that generates the three-dimensional point is the origin of the polar coordinate system, no shifting may be performed. Note that not shifting the position information means that the position information is not actually shifted, and may include, for example, performing a shift process with a shift amount of zero.

For example, the three-dimensional data decoding device acquires shift information (e.g., sensor position coordinates or coordinate information) indicating the shift amount from the bit stream, and shifts the position information based on the shift amount indicated by the shift information regardless of whether the position information is expressed in a Cartesian coordinate system or a polar coordinate system, and if the position information is position information expressed in a polar coordinate system, the shift amount indicated by the shift information is set to zero. In other words, the three-dimensional data decoding device acquires shift information indicating the shift amount from the bit stream, and if the position information is expressed in a polar coordinate system, the amount indicated by the shift information is zero, and does not shift the position information expressed in the polar coordinate system by shifting the position information based on the amount indicated by the shift information.

As a result, the three-dimensional data decoding device can apply shift processing to position information regardless of whether the position information is in a Cartesian coordinate system or a polar coordinate system, eliminating the need to control whether or not to perform shift processing, thereby simplifying processing.

For example, a three-dimensional data decoding device obtains shift information (e.g., sensor position coordinates or coordinate information) indicating the amount of shift from the bit stream, and if the position information is expressed in a Cartesian coordinate system, shifts the position information based on the amount indicated by the shift information, and if the position information is expressed in a polar coordinate system, considers the amount to be zero regardless of the amount indicated by the shift information.

According to this, when the position information is in a polar coordinate system, the three-dimensional data decoding device considers the shift amount to be zero, regardless of the shift amount indicated in the shift information. This reduces the amount of processing required by the three-dimensional data encoding device that generates the bitstream. Furthermore, the three-dimensional data decoding device may be able to correctly decode the bitstream even if it contains an error.

For example, if the bit stream contains shift information indicating the amount of shift, the three-dimensional data decoding device determines that the position information is represented in a Cartesian coordinate system and shifts the position information based on the shift amount indicated by the shift information; if the bit stream does not contain shift information, the device determines that the position information is represented in a polar coordinate system and does not shift the position information.

This means that if the position information is in polar coordinates, the bitstream does not contain shift information, thereby reducing the amount of data in the bitstream.

For example, the encoded position information includes multiple unit data (e.g., GDU) in which position information for each division unit obtained by dividing multiple three-dimensional points is encoded, and the shift information is included in a parameter set (e.g., GPS) included in the bit stream and common to multiple unit data. In other words, the bit stream includes encoded information in which position information for multiple three-dimensional points including a three-dimensional point is encoded, and the encoded information is divided into multiple division units obtained by dividing multiple three-dimensional points, and the shift information is included in a parameter set common to the multiple division units. For example, the encoded information includes encoded position information.

For example, the encoded position information includes multiple unit data (e.g., GDUs) in which position information for each division unit obtained by dividing multiple three-dimensional points is encoded, and the shift information is included in a header (e.g., a GDU header) for each of the multiple unit data included in the bitstream. In other words, the bitstream includes encoded information in which position information for multiple three-dimensional points, including a three-dimensional point, is encoded, and the encoded information is divided into multiple division units obtained by dividing the multiple three-dimensional points, and the shift information is included in a header for each of the multiple division units. For example, the encoded information includes encoded position information.

For example, when position information is expressed in a polar coordinate system, the three-dimensional data decoding device converts the position information expressed in the polar coordinate system into transformed position information expressed in a Cartesian coordinate system and shifts the transformed position information.

As a result, even if the encoded position information is in a polar coordinate system, the three-dimensional data decoding device can convert the position information in the polar coordinate system into position information in a Cartesian coordinate system and output the position information in the Cartesian coordinate system.

For example, a three-dimensional data decoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

The three-dimensional data encoding device according to this embodiment also performs the processing shown in FIG. 87. The three-dimensional data encoding device generates encoded position information by encoding the position information of the three-dimensional point (S13721), and generates a bitstream including the encoded position information and shift information (e.g., sensor position coordinates, coordinate information, gps_alt_coordinates_flag, or gps_coordinate_trans_enabled_flag) indicating whether the three-dimensional data decoding device shifts the decoded position information decoded by the three-dimensional data decoding device (S13722).

Based on the shift information, the three-dimensional data decoding device shifts the decoded position information if the decoded position information is expressed in a Cartesian coordinate system, and does not shift the decoded position information if the decoded position information is expressed in a polar coordinate system.

This allows the three-dimensional data encoding device to generate a bitstream in which the three-dimensional data decoding device can switch whether to perform shift processing on the position information depending on whether the encoded position information is in a Cartesian coordinate system or a polar coordinate system. Here, when the position information is in a Cartesian coordinate system, the three-dimensional data encoding device performs shift processing before encoding, thereby improving encoding efficiency. When the position information is in a Cartesian coordinate system, the three-dimensional data decoding device performs shift processing, allowing it to properly decode a bitstream with improved encoding efficiency. Furthermore, when the position information is in a polar coordinate system, the three-dimensional data decoding device does not perform shift processing, thereby reducing the amount of processing.

For example, a three-dimensional data encoding device generates encoded position information by encoding position information of a three-dimensional point, generates a bit stream including the encoded position information, and shifts a first position indicated by the position information if the position information is expressed in Cartesian coordinates, and the shift may not be performed if the position information is expressed in a polar coordinate system.

For example, the bitstream may include shift information indicating whether the position information is represented in a Cartesian coordinate system or a polar coordinate system.

In addition, the bit stream (e.g., shift information) may include first flag information (e.g., gps_alt_coordinates_flag) indicating whether the position information is expressed in a polar coordinate system, and second flag information (e.g., gps_coordinate_trans_enabled_flag) indicating whether the position information expressed in the polar coordinate system is converted into transformed position information expressed in a Cartesian coordinate system.

For example, if the position information is expressed in a polar coordinate system and the second position of the sensor generating the three-dimensional point is the origin of the polar coordinate system, no shift may be performed.

For example, the shift information indicates the amount of shift when shifting the decoded position information, and when the position information is expressed in a polar coordinate system, the amount indicated by the shift information is zero, and the three-dimensional data decoding device does not shift the position information expressed in the polar coordinate system by shifting the position information based on the amount indicated by the shift information.

As a result, for example, in a three-dimensional data decoding device, shift processing can be applied to position information regardless of whether the position information is in a Cartesian coordinate system or a polar coordinate system, eliminating the need to control whether or not to perform shift processing, thereby simplifying processing in the three-dimensional data decoding device.

For example, when the position information is expressed in a Cartesian coordinate system, the shift information indicates the amount of shift when shifting the decoded position information, and when the position information is expressed in a polar coordinate system, the three-dimensional data encoding device does not store the shift information in the bitstream.

This means that if the position information is in polar coordinates, the bitstream does not contain shift information, thereby reducing the amount of data in the bitstream.

For example, the encoded position information includes multiple unit data (e.g., GDU) in which position information for each division unit obtained by dividing multiple three-dimensional points is encoded, and the shift information is included in a parameter set (e.g., GPS) included in the bit stream and common to multiple unit data. In other words, the bit stream includes encoded information in which position information for multiple three-dimensional points, including a three-dimensional point, is encoded, and the encoded information is divided into multiple division units obtained by dividing multiple three-dimensional points, and the shift information is included in a parameter set common to the multiple division units.

For example, the encoded position information includes multiple unit data (e.g., GDUs) in which position information for each division unit obtained by dividing multiple three-dimensional points is encoded, and the shift information is included in a header (e.g., a GDU header) for each of the multiple unit data included in the bitstream. In other words, the bitstream includes encoded information in which position information for multiple three-dimensional points, including a three-dimensional point, is encoded, and the encoded information is divided into multiple division units obtained by dividing multiple three-dimensional points, and the shift information is included in a header for each of the multiple division units.

For example, a three-dimensional data encoding device includes a processor and a memory, and the processor uses the memory to perform the above processing.

Eighth Embodiment
Next, the configuration of a three-dimensional data creation device 810 according to this embodiment will be described. Fig. 88 is a block diagram showing an example configuration of a three-dimensional data creation device 810 according to this embodiment. This three-dimensional data creation device 810 is mounted on a vehicle, for example. The three-dimensional data creation device 810 transmits and receives three-dimensional data to and from an external traffic monitoring cloud, a leading vehicle, or a following vehicle, and also creates and stores three-dimensional data.

The three-dimensional data creation device 810 comprises a data receiving unit 811, a communication unit 812, a reception control unit 813, a format conversion unit 814, multiple sensors 815, a three-dimensional data creation unit 816, a three-dimensional data synthesis unit 817, a three-dimensional data storage unit 818, a communication unit 819, a transmission control unit 820, a format conversion unit 821, and a data transmission unit 822.

The data receiving unit 811 receives three-dimensional data 831 from a traffic monitoring cloud or a preceding vehicle. The three-dimensional data 831 includes information such as a point cloud, visible light image, depth information, sensor position information, or speed information, including areas that cannot be detected by the vehicle's own sensor 815.

The communication unit 812 communicates with the traffic monitoring cloud or the vehicle in front, and sends data transmission requests, etc. to the traffic monitoring cloud or the vehicle in front.

The receiving control unit 813 exchanges information such as supported formats with the communication destination via the communication unit 812 and establishes communication with the communication destination.

The format conversion unit 814 generates three-dimensional data 832 by performing format conversion, etc. on the three-dimensional data 831 received by the data receiving unit 811. In addition, if the three-dimensional data 831 is compressed or encoded, the format conversion unit 814 performs decompression or decoding processing.

The multiple sensors 815 are a group of sensors that acquire information about the outside of the vehicle, such as LiDAR, a visible light camera, or an infrared camera, and generate sensor information 833. For example, if the sensor 815 is a laser sensor such as LiDAR, the sensor information 833 is three-dimensional data such as a point cloud (point cloud data). Note that the number of sensors 815 does not need to be multiple.

The three-dimensional data creation unit 816 generates three-dimensional data 834 from the sensor information 833. The three-dimensional data 834 includes information such as a point cloud, visible light image, depth information, sensor position information, or velocity information.

The three-dimensional data synthesis unit 817 synthesizes three-dimensional data 834 created based on the vehicle's own sensor information 833 with three-dimensional data 832 created by the traffic monitoring cloud or the vehicle in front, etc., to construct three-dimensional data 835 that includes the space in front of the vehicle in front, which cannot be detected by the vehicle's own sensor 815.

The three-dimensional data storage unit 818 stores the generated three-dimensional data 835, etc.

The communication unit 819 communicates with the traffic monitoring cloud or a following vehicle and sends data transmission requests, etc. to the traffic monitoring cloud or the following vehicle.

The transmission control unit 820 exchanges information such as supported formats with the communication destination via the communication unit 819, and establishes communication with the communication destination. The transmission control unit 820 also determines a transmission area, which is the space of the three-dimensional data to be transmitted, based on the three-dimensional data construction information of the three-dimensional data 832 generated by the three-dimensional data synthesis unit 817 and a data transmission request from the communication destination.

Specifically, in response to a data transmission request from the traffic monitoring cloud or a following vehicle, the transmission control unit 820 determines a transmission area that includes the space ahead of the vehicle that cannot be detected by the sensors of the following vehicle. The transmission control unit 820 also determines the transmission area by determining whether the space available for transmission or the space that has already been transmitted has been updated based on the three-dimensional data construction information. For example, the transmission control unit 820 determines the area specified in the data transmission request and in which the corresponding three-dimensional data 835 exists as the transmission area. The transmission control unit 820 then notifies the format conversion unit 821 of the format supported by the communication destination and the transmission area.

The format conversion unit 821 generates three-dimensional data 837 by converting the three-dimensional data 836 of the transmission area, which is part of the three-dimensional data 835 stored in the three-dimensional data storage unit 818, into a format supported by the receiving side. The format conversion unit 821 may also reduce the amount of data by compressing or encoding the three-dimensional data 837.

The data transmission unit 822 transmits three-dimensional data 837 to the traffic monitoring cloud or the following vehicle. This three-dimensional data 837 includes information such as a point cloud ahead of the vehicle, visible light image, depth information, or sensor position information, including areas that are blind spots for the following vehicle.

Note that although an example has been described in which format conversion is performed by format conversion units 814 and 821, format conversion does not necessarily have to be performed.

With this configuration, the three-dimensional data creation device 810 externally acquires three-dimensional data 831 of an area that cannot be detected by the vehicle's sensor 815, and generates three-dimensional data 835 by combining the three-dimensional data 831 with three-dimensional data 834 based on sensor information 833 detected by the vehicle's sensor 815. This allows the three-dimensional data creation device 810 to generate three-dimensional data of an area that cannot be detected by the vehicle's sensor 815.

In addition, the three-dimensional data creation device 810 can transmit three-dimensional data including the space ahead of the vehicle that cannot be detected by the sensors of the following vehicle to the traffic monitoring cloud or the following vehicle, etc., in response to a data transmission request from the traffic monitoring cloud or the following vehicle.

Next, we will explain the procedure for transmitting three-dimensional data to a following vehicle in the three-dimensional data creation device 810. Figure 89 is a flowchart showing an example of the procedure for transmitting three-dimensional data to a traffic monitoring cloud or a following vehicle by the three-dimensional data creation device 810.

First, the three-dimensional data creation device 810 generates and updates three-dimensional data 835 of the space including the space on the road ahead of the vehicle (S801). Specifically, the three-dimensional data creation device 810 constructs three-dimensional data 835 including the space ahead of the vehicle ahead that cannot be detected by the vehicle's own sensor 815, for example, by combining three-dimensional data 834 created based on the vehicle's own sensor information 833 with three-dimensional data 831 created by a traffic monitoring cloud or a vehicle ahead.

Next, the three-dimensional data creation device 810 determines whether the three-dimensional data 835 contained in the transmitted space has changed (S802).

If a change occurs in the three-dimensional data 835 contained in the space that has already been transmitted, such as when a vehicle or person enters the space from outside (Yes in S802), the three-dimensional data creation device 810 transmits three-dimensional data including the three-dimensional data 835 of the space where the change occurred to the traffic monitoring cloud or a following vehicle (S803).

The three-dimensional data creation device 810 may transmit the three-dimensional data of the space in which a change has occurred in accordance with the transmission timing of the three-dimensional data transmitted at predetermined intervals, or may transmit the data immediately after detecting the change. In other words, the three-dimensional data creation device 810 may transmit the three-dimensional data of the space in which a change has occurred in priority over the three-dimensional data transmitted at predetermined intervals.

In addition, the three-dimensional data creation device 810 may transmit all of the three-dimensional data of the space in which a change has occurred as the three-dimensional data of the space in which a change has occurred, or may transmit only the differences in the three-dimensional data (for example, information on three-dimensional points that have appeared or disappeared, or displacement information of three-dimensional points, etc.).

The three-dimensional data creation device 810 may also transmit metadata regarding the vehicle's risk-avoidance actions, such as a sudden braking warning, to the following vehicle prior to transmitting the three-dimensional data of the space where the change has occurred. This allows the following vehicle to recognize the sudden braking of the vehicle in front at an early stage and to begin risk-avoidance actions, such as deceleration, earlier.

If there is no change in the three-dimensional data 835 contained in the transmitted space (No in S802), or after step S803, the three-dimensional data creation device 810 transmits the three-dimensional data contained in a space of a predetermined shape at a distance L ahead of the vehicle to the traffic monitoring cloud or a following vehicle (S804).

Furthermore, for example, the processing of steps S801 to S804 is repeated at a predetermined time interval.

In addition, the three-dimensional data creation device 810 does not need to transmit the three-dimensional data 837 of the space if there is no difference between the three-dimensional data 835 of the space currently being transmitted and the three-dimensional map.

In this embodiment, the client device transmits sensor information obtained by the sensor to a server or another client device.

First, the configuration of the system according to this embodiment will be described. Figure 90 is a diagram showing the configuration of a system for transmitting and receiving 3D maps and sensor information according to this embodiment. This system includes a server 901 and client devices 902A and 902B. When there is no need to distinguish between client devices 902A and 902B, they will also be referred to as client device 902.

The client device 902 is, for example, an in-vehicle device mounted on a moving object such as a vehicle. The server 901 is, for example, a traffic monitoring cloud, and is capable of communicating with multiple client devices 902.

The server 901 transmits a three-dimensional map composed of a point cloud to the client device 902. Note that the composition of the three-dimensional map is not limited to a point cloud, but may represent other three-dimensional data such as a mesh structure.

The client device 902 transmits sensor information acquired by the client device 902 to the server 901. The sensor information includes, for example, at least one of LiDAR acquisition information, visible light image, infrared image, depth image, sensor position information, and velocity information.

Data sent and received between the server 901 and the client device 902 may be compressed to reduce data size, or may remain uncompressed to maintain data accuracy. When compressing data, a three-dimensional compression method based on an octree structure, for example, can be used for point clouds. Furthermore, a two-dimensional image compression method can be used for visible light images, infrared images, and depth images. Examples of two-dimensional image compression methods include MPEG-4 AVC or HEVC, which are standardized by MPEG.

Furthermore, the server 901 transmits the three-dimensional map managed by the server 901 to the client device 902 in response to a request to send the three-dimensional map from the client device 902. Note that the server 901 may transmit the three-dimensional map without waiting for a request to send the three-dimensional map from the client device 902. For example, the server 901 may broadcast the three-dimensional map to one or more client devices 902 located in a predetermined space. Furthermore, the server 901 may transmit a three-dimensional map appropriate to the location of the client device 902 at regular intervals to the client device 902 once it has received a transmission request. Furthermore, the server 901 may transmit the three-dimensional map to the client device 902 each time the three-dimensional map managed by the server 901 is updated.

The client device 902 issues a request to the server 901 to send a three-dimensional map. For example, if the client device 902 wants to estimate its own position while driving, the client device 902 sends a request to the server 901 to send a three-dimensional map.

In the following cases, the client device 902 may issue a request to the server 901 to send a three-dimensional map. If the three-dimensional map held by the client device 902 is old, the client device 902 may issue a request to the server 901 to send a three-dimensional map. For example, if a certain period of time has passed since the client device 902 obtained the three-dimensional map, the client device 902 may issue a request to the server 901 to send a three-dimensional map.

A certain time before the client device 902 leaves the space shown in the three-dimensional map held by the client device 902, the client device 902 may issue a request to the server 901 to send a three-dimensional map. For example, if the client device 902 is located within a predetermined distance from the boundary of the space shown in the three-dimensional map held by the client device 902, the client device 902 may issue a request to the server 901 to send a three-dimensional map. Furthermore, if the movement path and movement speed of the client device 902 are known, the time when the client device 902 will leave the space shown in the three-dimensional map held by the client device 902 may be predicted based on these.

If the error when aligning the three-dimensional data created by the client device 902 from sensor information with the three-dimensional map is greater than a certain level, the client device 902 may request the server 901 to send the three-dimensional map.

The client device 902 transmits sensor information to the server 901 in response to a request to transmit sensor information transmitted from the server 901. Note that the client device 902 may send sensor information to the server 901 without waiting for a request to transmit sensor information from the server 901. For example, once the client device 902 receives a request to transmit sensor information from the server 901, it may periodically transmit the sensor information to the server 901 for a certain period of time. Furthermore, if the error in aligning the three-dimensional data created by the client device 902 based on the sensor information with the three-dimensional map obtained from the server 901 is equal to or greater than a certain level, the client device 902 may determine that a change may have occurred in the three-dimensional map around the client device 902, and may transmit this information along with the sensor information to the server 901.

The server 901 issues a request to send sensor information to the client device 902. For example, the server 901 receives location information of the client device 902, such as GPS, from the client device 902. If the server 901 determines, based on the location information of the client device 902, that the client device 902 is approaching a space with little information in the three-dimensional map managed by the server 901, it issues a request to send sensor information to the client device 902 in order to generate a new three-dimensional map. The server 901 may also issue a request to send sensor information when it wants to update the three-dimensional map, when it wants to check road conditions during snowfall or disasters, when it wants to check traffic congestion, or when it wants to check incident and accident status, etc.

In addition, the client device 902 may set the amount of data of the sensor information to be sent to the server 901 depending on the communication state or bandwidth at the time of receiving a request to send the sensor information from the server 901. Setting the amount of data of the sensor information to be sent to the server 901 means, for example, increasing or decreasing the data itself or appropriately selecting a compression method.

Figure 91 is a block diagram showing an example configuration of a client device 902. The client device 902 receives a three-dimensional map composed of a point cloud or the like from the server 901, and estimates the client device 902's own position from three-dimensional data created based on the client device 902's sensor information. The client device 902 also transmits the acquired sensor information to the server 901.

The client device 902 includes a data receiving unit 1011, a communication unit 1012, a reception control unit 1013, a format conversion unit 1014, multiple sensors 1015, a three-dimensional data creation unit 1016, a three-dimensional image processing unit 1017, a three-dimensional data storage unit 1018, a format conversion unit 1019, a communication unit 1020, a transmission control unit 1021, and a data transmission unit 1022.

The data receiving unit 1011 receives a three-dimensional map 1031 from the server 901. The three-dimensional map 1031 is data including a point cloud such as a WLD or SWLD. The three-dimensional map 1031 may include either compressed data or uncompressed data.

The communication unit 1012 communicates with the server 901 and sends data transmission requests (e.g., requests to transmit three-dimensional maps) to the server 901.

The receiving control unit 1013 exchanges information such as supported formats with the communication destination via the communication unit 1012 and establishes communication with the communication destination.

The format conversion unit 1014 generates a three-dimensional map 1032 by performing format conversion, etc. on the three-dimensional map 1031 received by the data receiving unit 1011. Furthermore, if the three-dimensional map 1031 is compressed or encoded, the format conversion unit 1014 performs decompression or decoding processing. Note that if the three-dimensional map 1031 is uncompressed data, the format conversion unit 1014 does not perform decompression or decoding processing.

The multiple sensors 1015 are a group of sensors, such as LiDAR, a visible light camera, an infrared camera, or a depth sensor, that acquire information about the outside of the vehicle in which the client device 902 is mounted, and generate sensor information 1033. For example, if the sensor 1015 is a laser sensor such as LiDAR, the sensor information 1033 is three-dimensional data such as a point cloud (point cloud data). Note that the number of sensors 1015 does not need to be multiple.

The three-dimensional data creation unit 1016 creates three-dimensional data 1034 of the surroundings of the vehicle based on the sensor information 1033. For example, the three-dimensional data creation unit 1016 creates point cloud data with color information of the surroundings of the vehicle using information acquired by LiDAR and visible light images acquired by a visible light camera.

The three-dimensional image processing unit 1017 performs processing such as estimating the vehicle's own position using a three-dimensional map 1032 such as a received point cloud and three-dimensional data 1034 of the surroundings of the vehicle generated from sensor information 1033. The three-dimensional image processing unit 1017 may also generate three-dimensional data 1035 of the surroundings of the vehicle by combining the three-dimensional map 1032 and the three-dimensional data 1034, and perform processing such as estimating the vehicle's own position using the generated three-dimensional data 1035.

The three-dimensional data storage unit 1018 stores three-dimensional map 1032, three-dimensional data 1034, three-dimensional data 1035, etc.

The format conversion unit 1019 generates sensor information 1037 by converting the sensor information 1033 into a format supported by the receiving side. The format conversion unit 1019 may reduce the amount of data by compressing or encoding the sensor information 1037. The format conversion unit 1019 may also omit processing if format conversion is not necessary. The format conversion unit 1019 may also control the amount of data to be transmitted depending on the specified transmission range.

The communication unit 1020 communicates with the server 901 and receives data transmission requests (requests to transmit sensor information) and the like from the server 901.

The transmission control unit 1021 exchanges information such as supported formats with the communication destination via the communication unit 1020 and establishes communication.

The data transmission unit 1022 transmits the sensor information 1037 to the server 901. The sensor information 1037 includes information acquired by multiple sensors 1015, such as information acquired by LiDAR, a luminance image acquired by a visible light camera, an infrared image acquired by an infrared camera, a depth image acquired by a depth sensor, sensor position information, and speed information.

Next, the configuration of the server 901 will be described. Figure 92 is a block diagram showing an example configuration of the server 901. The server 901 receives sensor information transmitted from the client device 902 and creates three-dimensional data based on the received sensor information. The server 901 uses the created three-dimensional data to update the three-dimensional map managed by the server 901. In addition, the server 901 transmits the updated three-dimensional map to the client device 902 in response to a request from the client device 902 to transmit the three-dimensional map.

The server 901 includes a data receiving unit 1111, a communication unit 1112, a receiving control unit 1113, a format conversion unit 1114, a three-dimensional data creation unit 1116, a three-dimensional data synthesis unit 1117, a three-dimensional data storage unit 1118, a format conversion unit 1119, a communication unit 1120, a transmission control unit 1121, and a data transmission unit 1122.

The data receiving unit 1111 receives sensor information 1037 from the client device 902. The sensor information 1037 includes, for example, information acquired by LiDAR, a luminance image acquired by a visible light camera, an infrared image acquired by an infrared camera, a depth image acquired by a depth sensor, sensor position information, and speed information.

The communication unit 1112 communicates with the client device 902 and sends data transmission requests (e.g., requests to transmit sensor information) to the client device 902.

The receiving control unit 1113 exchanges information such as supported formats with the communication destination via the communication unit 1112 and establishes communication.

If the received sensor information 1037 is compressed or encoded, the format conversion unit 1114 performs decompression or decoding processing to generate sensor information 1132. Note that if the sensor information 1037 is uncompressed data, the format conversion unit 1114 does not perform decompression or decoding processing.

The three-dimensional data creation unit 1116 creates three-dimensional data 1134 of the surroundings of the client device 902 based on the sensor information 1132. For example, the three-dimensional data creation unit 1116 creates point cloud data with color information of the surroundings of the client device 902 using information acquired by LiDAR and visible light images acquired by a visible light camera.

The three-dimensional data synthesis unit 1117 updates the three-dimensional map 1135 by synthesizing the three-dimensional data 1134 created based on the sensor information 1132 with the three-dimensional map 1135 managed by the server 901.

The three-dimensional data storage unit 1118 stores three-dimensional maps 1135, etc.

The format conversion unit 1119 generates the three-dimensional map 1031 by converting the three-dimensional map 1135 into a format supported by the receiving side. The format conversion unit 1119 may reduce the amount of data by compressing or encoding the three-dimensional map 1135. The format conversion unit 1119 may also omit processing if format conversion is not necessary. The format conversion unit 1119 may also control the amount of data to be transmitted depending on the specified transmission range.

The communication unit 1120 communicates with the client device 902 and receives data transmission requests (requests to transmit three-dimensional maps) and the like from the client device 902.

The transmission control unit 1121 exchanges information such as supported formats with the communication destination via the communication unit 1120 and establishes communication.

The data transmission unit 1122 transmits the three-dimensional map 1031 to the client device 902. The three-dimensional map 1031 is data including a point cloud such as a WLD or SWLD. The three-dimensional map 1031 may include either compressed data or uncompressed data.

Next, we will explain the operational flow of the client device 902. Figure 93 is a flowchart showing the operation of the client device 902 when acquiring a three-dimensional map.

First, the client device 902 requests the server 901 to send a three-dimensional map (such as a point cloud) (S1001). At this time, the client device 902 may also send location information of the client device 902 obtained by GPS or the like, thereby requesting the server 901 to send a three-dimensional map related to that location information.

Next, the client device 902 receives the three-dimensional map from the server 901 (S1002). If the received three-dimensional map is compressed data, the client device 902 decodes the received three-dimensional map to generate an uncompressed three-dimensional map (S1003).

Next, the client device 902 creates three-dimensional data 1034 of the surroundings of the client device 902 from sensor information 1033 obtained by the multiple sensors 1015 (S1004). Next, the client device 902 estimates its own position using the three-dimensional map 1032 received from the server 901 and the three-dimensional data 1034 created from the sensor information 1033 (S1005).

Figure 94 is a flowchart showing the operation of the client device 902 when transmitting sensor information. First, the client device 902 receives a request to transmit sensor information from the server 901 (S1011). Upon receiving the transmission request, the client device 902 transmits the sensor information 1037 to the server 901 (S1012). Note that if the sensor information 1033 includes multiple pieces of information obtained from multiple sensors 1015, the client device 902 may generate the sensor information 1037 by compressing each piece of information using a compression method appropriate for that piece of information.

Next, the operational flow of the server 901 will be described. Figure 95 is a flowchart showing the operation of the server 901 when acquiring sensor information. First, the server 901 requests the client device 902 to transmit sensor information (S1021). Next, the server 901 receives the sensor information 1037 transmitted from the client device 902 in response to the request (S1022). Next, the server 901 creates three-dimensional data 1134 using the received sensor information 1037 (S1023). Next, the server 901 reflects the created three-dimensional data 1134 in the three-dimensional map 1135 (S1024).

Figure 96 is a flowchart showing the operation of the server 901 when transmitting a three-dimensional map. First, the server 901 receives a request to transmit a three-dimensional map from the client device 902 (S1031). Having received the request to transmit a three-dimensional map, the server 901 transmits a three-dimensional map 1031 to the client device 902 (S1032). At this time, the server 901 may extract a three-dimensional map of the vicinity based on the location information of the client device 902 and transmit the extracted three-dimensional map. The server 901 may also compress the three-dimensional map composed of a point cloud using, for example, a compression method with an octree structure, and transmit the compressed three-dimensional map.

Below, we will explain some variations of this embodiment.

The server 901 creates three-dimensional data 1134 of the vicinity of the position of the client device 902 using the sensor information 1037 received from the client device 902. Next, the server 901 calculates the difference between the three-dimensional data 1134 and the three-dimensional map 1135 by matching the created three-dimensional data 1134 with a three-dimensional map 1135 of the same area managed by the server 901. If the difference is equal to or greater than a predetermined threshold, the server 901 determines that some kind of abnormality has occurred in the vicinity of the client device 902. For example, when ground subsidence occurs due to a natural disaster such as an earthquake, a large difference may occur between the three-dimensional map 1135 managed by the server 901 and the three-dimensional data 1134 created based on the sensor information 1037.

The sensor information 1037 may include information indicating at least one of the sensor type, sensor performance, and sensor model number. Furthermore, a class ID or the like according to the sensor performance may be added to the sensor information 1037. For example, if the sensor information 1037 is information acquired by LiDAR, an identifier may be assigned to the sensor performance, such as Class 1 for a sensor that can acquire information with an accuracy of several millimeters, Class 2 for a sensor that can acquire information with an accuracy of several centimeters, and Class 3 for a sensor that can acquire information with an accuracy of several meters. Furthermore, the server 901 may estimate the sensor performance information, etc., from the model number of the client device 902. For example, if the client device 902 is installed in a vehicle, the server 901 may determine the sensor specification information from the vehicle model. In this case, the server 901 may acquire vehicle model information in advance, or this information may be included in the sensor information. Furthermore, the server 901 may use the acquired sensor information 1037 to switch the degree of correction for the three-dimensional data 1134 created using the sensor information 1037. For example, if the sensor performance is high accuracy (class 1), the server 901 does not perform correction on the three-dimensional data 1134. If the sensor performance is low accuracy (class 3), the server 901 applies correction according to the accuracy of the sensor to the three-dimensional data 1134. For example, the server 901 increases the degree (strength) of correction as the accuracy of the sensor decreases.

The server 901 may simultaneously issue requests to send sensor information to multiple client devices 902 in a certain space. When the server 901 receives multiple pieces of sensor information from multiple client devices 902, it is not necessary for the server 901 to use all of the sensor information to create the three-dimensional data 1134; for example, the server 901 may select the sensor information to use depending on the performance of the sensor. For example, when updating the three-dimensional map 1135, the server 901 may select high-precision sensor information (Class 1) from the multiple pieces of sensor information it has received, and use the selected sensor information to create the three-dimensional data 1134.

The server 901 is not limited to a server such as a traffic monitoring cloud, but may also be another client device (mounted in a vehicle). Figure 97 shows the system configuration in this case.

For example, client device 902C issues a request to send sensor information to nearby client device 902A and acquires the sensor information from client device 902A. Client device 902C then creates three-dimensional data using the acquired sensor information from client device 902A and updates the three-dimensional map of client device 902C. This allows client device 902C to generate a three-dimensional map of the space that can be acquired from client device 902A, taking advantage of the performance of client device 902C. For example, it is thought that such a case will occur when client device 902C has high performance.

In this case, client device 902A, which provided the sensor information, is granted the right to obtain the high-precision three-dimensional map generated by client device 902C. Client device 902A receives the high-precision three-dimensional map from client device 902C in accordance with that right.

Client device 902C may also issue requests to multiple nearby client devices 902 (client device 902A and client device 902B) to send sensor information. If the sensor of client device 902A or client device 902B is high performance, client device 902C can create three-dimensional data using the sensor information obtained by this high performance sensor.

Figure 98 is a block diagram showing the functional configuration of the server 901 and the client device 902. The server 901 includes, for example, a three-dimensional map compression/decoding processing unit 1201 that compresses and decodes three-dimensional maps, and a sensor information compression/decoding processing unit 1202 that compresses and decodes sensor information.

The client device 902 comprises a three-dimensional map decoding processing unit 1211 and a sensor information compression processing unit 1212. The three-dimensional map decoding processing unit 1211 receives encoded data of the compressed three-dimensional map and decodes the encoded data to obtain the three-dimensional map. The sensor information compression processing unit 1212 compresses the sensor information itself instead of the three-dimensional data created from the acquired sensor information, and transmits the encoded data of the compressed sensor information to the server 901. With this configuration, the client device 902 only needs to internally include a processing unit (device or LSI) that performs the processing to decode the three-dimensional map (point cloud, etc.), and does not need to internally include a processing unit that performs the processing to compress the three-dimensional data of the three-dimensional map (point cloud, etc.). This allows the cost and power consumption of the client device 902 to be reduced.

As described above, the client device 902 according to this embodiment is mounted on a mobile body and creates three-dimensional data 1034 of the surroundings of the mobile body from sensor information 1033 indicating the surrounding conditions of the mobile body, obtained by the sensor 1015 mounted on the mobile body. The client device 902 estimates the self-position of the mobile body using the created three-dimensional data 1034. The client device 902 transmits the acquired sensor information 1033 to the server 901 or another client device 902.

According to this, the client device 902 transmits sensor information 1033 to the server 901, etc. This may reduce the amount of data transmitted compared to when transmitting three-dimensional data. In addition, since the client device 902 does not need to perform processes such as compressing or encoding the three-dimensional data, the amount of processing by the client device 902 can be reduced. Therefore, the client device 902 can reduce the amount of data transmitted or simplify the device configuration.

The client device 902 also transmits a request to the server 901 to send a three-dimensional map, and receives the three-dimensional map 1031 from the server 901. The client device 902 estimates its own location using the three-dimensional data 1034 and the three-dimensional map 1032.

In addition, the sensor information 1033 includes at least one of information obtained by a laser sensor, a brightness image, an infrared image, a depth image, sensor position information, and sensor speed information.

In addition, sensor information 1033 includes information indicating the performance of the sensor.

In addition, the client device 902 encodes or compresses the sensor information 1033, and when transmitting the sensor information, transmits the encoded or compressed sensor information 1037 to the server 901 or another client device 902. This allows the client device 902 to reduce the amount of data transmitted.

For example, the client device 902 has a processor and memory, and the processor uses the memory to perform the above processing.

In addition, the server 901 according to this embodiment is capable of communicating with a client device 902 mounted on the mobile body, and receives from the client device 902 sensor information 1037 indicating the surrounding conditions of the mobile body, obtained by a sensor 1015 mounted on the mobile body. The server 901 creates three-dimensional data 1134 of the surroundings of the mobile body from the received sensor information 1037.

According to this, the server 901 creates three-dimensional data 1134 using sensor information 1037 transmitted from the client device 902. This potentially reduces the amount of data transmitted compared to when the client device 902 transmits the three-dimensional data. In addition, since the client device 902 does not need to perform processes such as compressing or encoding the three-dimensional data, the amount of processing required by the client device 902 can be reduced. Therefore, the server 901 can reduce the amount of data transmitted or simplify the device configuration.

The server 901 also sends a request to the client device 902 to send sensor information.

The server 901 further updates the three-dimensional map 1135 using the created three-dimensional data 1134 and transmits the three-dimensional map 1135 to the client device 902 in response to a request from the client device 902 to transmit the three-dimensional map 1135.

In addition, the sensor information 1037 includes at least one of information obtained by a laser sensor, a brightness image, an infrared image, a depth image, sensor position information, and sensor velocity information.

Sensor information 1037 also includes information indicating the performance of the sensor.

The server 901 also corrects the three-dimensional data according to the performance of the sensor. This allows the three-dimensional data creation method to improve the quality of the three-dimensional data.

Furthermore, when receiving sensor information, the server 901 receives multiple pieces of sensor information 1037 from multiple client devices 902, and selects the sensor information 1037 to use in creating the three-dimensional data 1134 based on multiple pieces of information indicating the performance of the sensors contained in the multiple pieces of sensor information 1037. This allows the server 901 to improve the quality of the three-dimensional data 1134.

The server 901 also decodes or decompresses the received sensor information 1037 and creates three-dimensional data 1134 from the decoded or decompressed sensor information 1132. This allows the server 901 to reduce the amount of data transmitted.

For example, server 901 has a processor and memory, and the processor uses the memory to perform the above processing.

Below, we will explain a modified example. Figure 99 is a diagram showing the configuration of a system related to this embodiment. The system shown in Figure 99 includes a server 2001, a client device 2002A, and a client device 2002B.

Client device 2002A and client device 2002B are mounted on a moving object such as a vehicle and transmit sensor information to server 2001. Server 2001 transmits a three-dimensional map (point cloud) to client device 2002A and client device 2002B.

Client device 2002A comprises a sensor information acquisition unit 2011, a memory unit 2012, and a data transmission feasibility determination unit 2013. Client device 2002B has a similar configuration. In the following, when there is no particular distinction between client device 2002A and client device 2002B, they will also be referred to as client device 2002.

Figure 100 is a flowchart showing the operation of the client device 2002 in this embodiment.

The sensor information acquisition unit 2011 acquires various sensor information using a sensor (sensor group) mounted on the mobile body. In other words, the sensor information acquisition unit 2011 acquires sensor information indicating the surrounding conditions of the mobile body, obtained by the sensor (sensor group) mounted on the mobile body. The sensor information acquisition unit 2011 also stores the acquired sensor information in the memory unit 2012. This sensor information includes at least one of LiDAR acquisition information, visible light images, infrared images, and depth images. The sensor information may also include at least one of sensor position information, speed information, acquisition time information, and acquisition location information. The sensor position information indicates the position of the sensor that acquired the sensor information. The speed information indicates the speed of the mobile body when the sensor acquired the sensor information. The acquisition time information indicates the time when the sensor information was acquired by the sensor. The acquisition location information indicates the position of the mobile body or sensor when the sensor information was acquired by the sensor.

Next, the data transmission possibility determination unit 2013 determines whether the mobile body (client device 2002) is in an environment where it can transmit sensor information to the server 2001 (S2002). For example, the data transmission possibility determination unit 2013 may use information such as GPS to identify the location and time of the client device 2002 and determine whether data can be transmitted. The data transmission possibility determination unit 2013 may also determine whether data can be transmitted based on whether it can connect to a specific access point.

When the client device 2002 determines that the mobile object is in an environment where it can transmit sensor information to the server 2001 (Yes in S2002), it transmits the sensor information to the server 2001 (S2003). In other words, when the client device 2002 is in a situation where it can transmit sensor information to the server 2001, the client device 2002 transmits the sensor information it holds to the server 2001. For example, a millimeter wave access point capable of high-speed communication is installed at an intersection, etc. When the client device 2002 enters the intersection, it uses millimeter wave communication to transmit the sensor information it holds to the server 2001 at high speed.

Next, the client device 2002 deletes the sensor information that has been transmitted to the server 2001 from the storage unit 2012 (S2004). The client device 2002 may delete sensor information that has not been transmitted to the server 2001 if the sensor information satisfies a predetermined condition. For example, the client device 2002 may delete the sensor information from the storage unit 2012 when the acquisition time of the retained sensor information becomes older than a predetermined time from the current time. In other words, the client device 2002 may delete the sensor information from the storage unit 2012 when the difference between the time the sensor information was acquired by the sensor and the current time exceeds a predetermined time. The client device 2002 may also delete the sensor information from the storage unit 2012 when the location where the retained sensor information was acquired becomes more than a predetermined distance away from the current location. In other words, the client device 2002 may delete the sensor information from the storage unit 2012 when the difference between the position of the mobile object or sensor when the sensor information was acquired by the sensor and the current position of the mobile object or sensor exceeds a predetermined distance. This makes it possible to reduce the capacity of the storage unit 2012 of the client device 2002 .

If the client device 2002 has not finished acquiring sensor information (No in S2005), the client device 2002 performs the processing from step S2001 onwards again. Also, if the client device 2002 has finished acquiring sensor information (Yes in S2005), the client device 2002 ends the processing.

The client device 2002 may also select the sensor information to be transmitted to the server 2001 in accordance with the communication conditions. For example, when high-speed communication is possible, the client device 2002 will prioritize transmitting sensor information that is large in size and stored in the memory unit 2012 (e.g., LiDAR acquisition information, etc.). When high-speed communication is difficult, the client device 2002 will transmit sensor information that is small in size and has a high priority and is stored in the memory unit 2012 (e.g., visible light images). This allows the client device 2002 to efficiently transmit the sensor information stored in the memory unit 2012 to the server 2001 in accordance with the network conditions.

The client device 2002 may also acquire time information indicating the current time and location information indicating the current location from the server 2001. The client device 2002 may also determine the acquisition time and acquisition location of the sensor information based on the acquired time information and location information. In other words, the client device 2002 may acquire time information from the server 2001 and generate acquired time information using the acquired time information. The client device 2002 may also acquire location information from the server 2001 and generate acquired location information using the acquired location information.

For example, with regard to time information, the server 2001 and client device 2002 synchronize their time using a mechanism such as NTP (Network Time Protocol) or PTP (Precision Time Protocol). This allows the client device 2002 to obtain accurate time information. Furthermore, since time can be synchronized between the server 2001 and multiple client devices, the time in the sensor information obtained by different client devices 2002 can be synchronized. Therefore, the server 2001 can handle sensor information that indicates synchronized time. Note that the time synchronization mechanism may be any method other than NTP or PTP. GPS information may also be used as the above-mentioned time information and location information.

The server 2001 may acquire sensor information from multiple client devices 2002 by specifying a time or location. For example, if an accident occurs, in order to search for clients who were nearby, the server 2001 broadcasts a sensor information transmission request to multiple client devices 2002, specifying the time and location of the accident. Then, the client device 2002 that has sensor information for the corresponding time and location transmits the sensor information to the server 2001. In other words, the client device 2002 receives a sensor information transmission request from the server 2001, including specification information that specifies the location and time. If the client device 2002 determines that sensor information obtained at the location and time indicated by the specification information is stored in the memory unit 2012 and that a mobile object is in an environment where it can transmit sensor information to the server 2001, it transmits the sensor information obtained at the location and time indicated by the specification information to the server 2001. In this way, the server 2001 can acquire sensor information related to the occurrence of an accident from multiple client devices 2002 and use it for accident analysis, etc.

When the client device 2002 receives a request to send sensor information from the server 2001, the client device 2002 may refuse to send the sensor information. The client device 2002 may also set in advance which of multiple pieces of sensor information are available for transmission. Alternatively, the server 2001 may inquire of the client device 2002 each time whether or not it is possible to send the sensor information.

Points may also be awarded to client devices 2002 that transmit sensor information to server 2001. These points can be used, for example, to pay for gasoline purchases, EV (electric vehicle) charging fees, highway tolls, or rental car fees. After acquiring the sensor information, server 2001 may delete information for identifying the client device 2002 that transmitted the sensor information. For example, this information may be information such as the network address of client device 2002. This allows the sensor information to be anonymized, allowing users of client device 2002 to transmit sensor information to server 2001 with peace of mind. Server 2001 may also be composed of multiple servers. For example, by sharing sensor information among multiple servers, even if one server fails, other servers can communicate with client device 2002. This makes it possible to avoid service interruptions due to server failures.

The specified location specified in the sensor information transmission request indicates the location of an accident, etc., and may differ from the location of the client device 2002 at the specified time specified in the sensor information transmission request. Therefore, the server 2001 can specify a range, such as within XX meters of the specified location, to request information acquisition from client devices 2002 located within that range. Similarly, for the specified time, the server 2001 may specify a range, such as within N seconds before or after a certain time. This allows the server 2001 to acquire sensor information from client devices 2002 that were located "at a location: within XX meters of absolute position S, from time: t-N to t+N." When transmitting three-dimensional data such as LiDAR, the client device 2002 may transmit data generated immediately after time t.

Furthermore, the server 2001 may separately specify, as the specified location, information indicating the location of the client device 2002 from which sensor information is to be acquired and the location from which sensor information is desired. For example, the server 2001 specifies that sensor information including at least a range of YYm from absolute position S is to be acquired from client devices 2002 located within XXm of absolute position S. When selecting three-dimensional data to transmit, the client device 2002 selects one or more randomly accessible units of three-dimensional data so as to include at least the sensor information in the specified range. Furthermore, when transmitting visible light images, the client device 2002 may transmit multiple temporally consecutive image data sets including at least the frames immediately before or after time t.

If the client device 2002 can use multiple physical networks, such as 5G or Wi-Fi, or multiple modes in 5G, to transmit sensor information, the client device 2002 may select a network to use according to the priority notified by the server 2001. Alternatively, the client device 2002 itself may select a network that can ensure an appropriate bandwidth based on the size of the transmission data. Alternatively, the client device 2002 may select a network to use based on the cost of data transmission, etc. In addition, the transmission request from the server 2001 may include information indicating a transmission deadline, such as that the client device 2002 will transmit if it is able to start transmission by time T. The server 2001 may issue a transmission request again if it is unable to obtain sufficient sensor information within the deadline.

The sensor information may include header information indicating characteristics of the sensor data along with compressed or uncompressed sensor data. The client device 2002 may transmit the header information to the server 2001 via a different physical network or communication protocol than that used for transmitting the sensor data. For example, the client device 2002 transmits the header information to the server 2001 prior to transmitting the sensor data. The server 2001 determines whether to acquire the sensor data of the client device 2002 based on the analysis results of the header information. For example, the header information may include information indicating the LiDAR point cloud acquisition density, elevation angle, or frame rate, or the resolution, signal-to-noise ratio, or frame rate of the visible light image. This allows the server 2001 to acquire sensor information from the client device 2002 having sensor data of the determined quality.

As described above, the client device 2002 is mounted on a mobile object, acquires sensor information indicating the surrounding conditions of the mobile object obtained by sensors mounted on the mobile object, and stores the sensor information in the memory unit 2012. The client device 2002 determines whether the mobile object is in an environment where it can transmit the sensor information to the server 2001, and if it determines that the mobile object is in an environment where it can transmit the sensor information to the server, it transmits the sensor information to the server 2001.

In addition, the client device 2002 further creates three-dimensional data of the surroundings of the mobile body from the sensor information and estimates the mobile body's own position using the created three-dimensional data.

The client device 2002 further transmits a request to the server 2001 to send a three-dimensional map and receives the three-dimensional map from the server 2001. The client device 2002 estimates its own location using the three-dimensional data and the three-dimensional map.

In addition, the processing by the above-mentioned client device 2002 may be realized as an information transmission method in the client device 2002.

The client device 2002 may also be equipped with a processor and memory, and the processor may use the memory to perform the above processing.

Next, a sensor information collection system according to this embodiment will be described. Figure 101 is a diagram showing the configuration of a sensor information collection system according to this embodiment. As shown in Figure 101, the sensor information collection system according to this embodiment includes a terminal 2021A, a terminal 2021B, a communication device 2022A, a communication device 2022B, a network 2023, a data collection server 2024, a map server 2025, and a client device 2026. Note that when there is no particular distinction between terminal 2021A and terminal 2021B, they are also referred to as terminal 2021. When there is no particular distinction between communication device 2022A and communication device 2022B, they are also referred to as communication device 2022.

The data collection server 2024 collects data such as sensor data obtained by sensors equipped in the terminal 2021 as location-related data associated with positions in three-dimensional space.

Sensor data is, for example, data acquired by using a sensor equipped in terminal 2021, such as the state of the surroundings of terminal 2021 or the state of the interior of terminal 2021. Terminal 2021 transmits sensor data collected from one or more sensor devices located in positions that can communicate with terminal 2021 directly or via one or more relay devices using the same communication method to data collection server 2024.

Data included in the location-related data may include, for example, information indicating the operating status of the terminal itself or the equipment included in the terminal, operation logs, service usage status, etc. Data included in the location-related data may also include information associating the identifier of the terminal 2021 with the location or movement route of the terminal 2021, etc.

The information indicating a location included in the location-related data corresponds to information indicating a location in three-dimensional data, such as three-dimensional map data. Details of the information indicating a location will be described later.

In addition to location information, which is information indicating a location, location-related data may include at least one of the time information described above and information indicating the attributes of the data included in the location-related data or the type of sensor that generated the data (e.g., model number). The location information and time information may be stored in the header field of the location-related data or the header field of a frame that stores the location-related data. In addition, the location information and time information may be transmitted and/or stored separately from the location-related data as metadata associated with the location-related data.

The map server 2025 is connected to the network 2023, for example, and transmits three-dimensional data such as three-dimensional map data in response to requests from other devices such as the terminal 2021. As described in the above-mentioned embodiments, the map server 2025 may also have a function for updating the three-dimensional data using sensor information transmitted from the terminal 2021.

The data collection server 2024 is connected to the network 2023, for example, and collects location-related data from other devices such as the terminal 2021, and stores the collected location-related data in a storage device internally or in another server. The data collection server 2024 also transmits the collected location-related data or metadata of three-dimensional map data generated based on the location-related data to the terminal 2021 in response to a request from the terminal 2021.

Network 2023 is a communications network such as the Internet. Terminal 2021 is connected to network 2023 via communication device 2022. Communication device 2022 communicates with terminal 2021 by switching between one or more communication methods. Communication device 2022 is, for example, (1) a base station such as LTE (Long Term Evolution), (2) an access point (AP) such as Wi-Fi or millimeter wave communication, (3) a gateway of an LPWA (Low Power Wide Area) network such as SIGFOX, LoRaWAN, or Wi-SUN, or (4) a communications satellite that communicates using a satellite communications method such as DVB-S2.

In addition, the base station may communicate with terminal 2021 using a method classified as LPWA, such as NB-IoT (Narrow Band-IoT) or LTE-M, or may communicate with terminal 2021 by switching between these methods.

Here, we will use as an example a case in which the terminal 2021 has the ability to communicate with a communication device 2022 that uses two types of communication methods, and communicates with the map server 2025 or the data collection server 2024 using one of these communication methods, or by switching between these multiple communication methods and the communication device 2022 that is the direct communication partner; however, the configuration of the sensor information collection system and the terminal 2021 is not limited to this. For example, the terminal 2021 may not have the ability to communicate using multiple communication methods, but may instead have the ability to communicate using any one of the communication methods. The terminal 2021 may also support three or more communication methods. Each terminal 2021 may also support a different communication method.

The terminal 2021 has, for example, the configuration of the client device 902 shown in FIG. 91. The terminal 2021 performs position estimation, such as its own position, using the received three-dimensional data. The terminal 2021 also generates position-related data by associating the sensor data acquired from the sensor with the position information obtained by the position estimation process.

The location information added to the location-related data indicates, for example, a location in the coordinate system used in the three-dimensional data. For example, the location information is a coordinate value expressed as latitude and longitude values. In this case, the terminal 2021 may include in the location information, together with the coordinate value, information indicating the coordinate system that serves as the basis for the coordinate value and the three-dimensional data used for location estimation. The coordinate value may also include altitude information.

The position information may also be associated with a data unit or a spatial unit that can be used to encode the three-dimensional data described above. Examples of such units include WLD, GOS, SPC, VLM, or VXL. In this case, the position information is expressed, for example, by an identifier for identifying a data unit such as an SPC that corresponds to the position-related data. Note that the position information may also include, in addition to an identifier for identifying a data unit such as an SPC, information indicating three-dimensional data that encodes a three-dimensional space that includes the data unit such as an SPC, or information indicating a detailed position within the SPC. The information indicating the three-dimensional data is, for example, the file name of the three-dimensional data.

In this way, by generating location-related data associated with location information based on location estimation using three-dimensional data, the system can assign location information to sensor information with higher accuracy than when location information based on the client device's (terminal 2021) own location acquired using GPS is added to the sensor information. As a result, even when the location-related data is used by another device for another service, it may be possible to more accurately identify the location corresponding to the location-related data in real space by performing location estimation based on the same three-dimensional data.

In this embodiment, the data transmitted from terminal 2021 is location-related data, but the data transmitted from terminal 2021 may be data that is not associated with location information. In other words, the transmission and reception of three-dimensional data or sensor data described in other embodiments may be performed via network 2023 described in this embodiment.

Next, different examples of location information indicating a position in three-dimensional or two-dimensional real space or map space will be described. The location information added to the location-related data may be information indicating a relative position with respect to a feature point in the three-dimensional data. Here, the feature point that serves as the reference for the location information is, for example, a feature point that has been encoded as an SWLD and notified to the terminal 2021 as three-dimensional data.

The information indicating the relative position with respect to a feature point may be expressed as a vector from the feature point to the point indicated by the position information, and may indicate the direction and distance from the feature point to the point indicated by the position information. Alternatively, the information indicating the relative position with respect to a feature point may be information indicating the amount of displacement along the X-axis, Y-axis, and Z-axis from the feature point to the point indicated by the position information. Furthermore, the information indicating the relative position with respect to a feature point may be information indicating the distance from each of three or more feature points to the point indicated by the position information. Note that the relative position may not be the relative position of the point indicated by the position information expressed relative to each feature point, but may be the relative position of each feature point expressed relative to the point indicated by the position information. An example of position information based on the relative position with respect to a feature point includes information for identifying the reference feature point and information indicating the relative position of the point indicated by the position information with respect to that feature point. Furthermore, if the information indicating the relative position with respect to a feature point is provided separately from the three-dimensional data, the information indicating the relative position with respect to the feature point may include the coordinate axes used to derive the relative position, information indicating the type of three-dimensional data, and/or information indicating the size per unit amount (e.g., scale) of the value of the information indicating the relative position.

The location information may also include information indicating the relative position of multiple feature points with respect to each feature point. When location information is expressed as a relative position with respect to multiple feature points, the terminal 2021 attempting to identify the position indicated by the location information in real space may calculate a candidate point for the position indicated by the location information from the position of each feature point estimated from sensor data, and determine that the point obtained by averaging the calculated candidate points is the point indicated by the location information. This configuration reduces the impact of errors when estimating the position of a feature point from sensor data, thereby improving the estimation accuracy of the point indicated by the location information in real space. Furthermore, when location information includes information indicating the relative position with respect to multiple feature points, even if there is a feature point that cannot be detected due to constraints such as the type or performance of the sensor equipped in the terminal 2021, it is possible to estimate the value of the point indicated by the location information as long as any one of the multiple feature points can be detected.

Feature points can be points that can be identified from sensor data. Points that can be identified from sensor data are points or points within an area that satisfy specific conditions for feature point detection, such as the aforementioned three-dimensional feature values or visible light data feature values being equal to or greater than a threshold value.

Also, markers placed in real space may be used as feature points. In this case, the markers only need to be able to be detected and located from data acquired using a sensor such as a LiDAR or camera. For example, the markers may be represented by changes in color or brightness (reflectance), or by a three-dimensional shape (such as unevenness). Alternatively, coordinate values indicating the position of the marker, or a two-dimensional code or barcode generated from the marker's identifier, may be used.

Also, a light source that transmits an optical signal may be used as a marker. When a light source of an optical signal is used as a marker, not only information for acquiring a position, such as coordinate values or an identifier, but also other data may be transmitted by the optical signal. For example, the optical signal may include information indicating the content of a service corresponding to the position of the marker, an address such as a URL for acquiring the content, or an identifier of a wireless communication device for receiving the service, and a wireless communication method for connecting to the wireless communication device. Using an optical communication device (light source) as a marker makes it easier to transmit data other than information indicating a position, and enables dynamic switching of the data.

The terminal 2021 grasps the correspondence between feature points between different data, for example, using an identifier commonly used between the data, or information or a table indicating the correspondence between feature points between the data. Furthermore, if there is no information indicating the correspondence between feature points, the terminal 2021 may determine that the feature point that is closest when the coordinates of a feature point in one of the three-dimensional data are converted to a position in the three-dimensional data space of the other is the corresponding feature point.

When using location information based on the relative positions described above, even between terminals 2021 or services that use different three-dimensional data, it is possible to identify or estimate the location indicated by the location information based on common feature points contained in or associated with each piece of three-dimensional data. As a result, it is possible to identify or estimate the same location with higher accuracy between terminals 2021 or services that use different three-dimensional data.

In addition, even when using map data or three-dimensional data expressed using different coordinate systems, the impact of errors associated with coordinate system conversion can be reduced, making it possible to link services based on more accurate location information.

The following describes examples of functions provided by the data collection server 2024. The data collection server 2024 may forward the received location-related data to another data server. If there are multiple data servers, the data collection server 2024 determines to which data server the received location-related data should be forwarded, and forwards the location-related data to the data server determined as the forwarding destination.

The data collection server 2024 determines the destination of transfer, for example, based on destination server determination rules that are pre-set in the data collection server 2024. The destination server determination rules are set, for example, in a destination table that associates an identifier associated with each terminal 2021 with the destination data server.

The terminal 2021 adds an identifier associated with the terminal 2021 to the location-related data to be transmitted, and transmits the data to the data collection server 2024. The data collection server 2024 identifies the destination data server corresponding to the identifier added to the location-related data based on a destination server determination rule using a destination table or the like, and transmits the location-related data to the identified data server. The destination server determination rule may also be specified by a determination condition using the time or location at which the location-related data was acquired. Here, the identifier associated with the aforementioned source terminal 2021 is, for example, an identifier unique to each terminal 2021, or an identifier indicating the group to which the terminal 2021 belongs.

Furthermore, the forwarding destination table does not have to directly associate the identifier associated with the source terminal with the destination data server. For example, the data collection server 2024 holds a management table that stores tag information assigned to each unique identifier of the terminal 2021, and a forwarding destination table that associates the tag information with the destination data server. The data collection server 2024 may use the management table and the forwarding destination table to determine the destination data server based on the tag information. Here, the tag information is, for example, management control information or service provision control information assigned to the type, model number, owner, group to which the terminal 2021 corresponding to the identifier corresponds, or other identifier. Furthermore, the forwarding destination table may use an identifier unique to each sensor instead of the identifier associated with the source terminal 2021. Furthermore, the rules for determining the destination server may be set from the client device 2026.

The data collection server 2024 may determine multiple data servers as destinations and transfer the received location-related data to those multiple data servers. With this configuration, for example, when automatically backing up location-related data or when location-related data needs to be sent to a data server providing each service in order to share the data across different services, the intended data transfer can be achieved by changing the settings on the data collection server 2024. As a result, the amount of work required to build and modify the system can be reduced compared to when setting the destination of location-related data on individual terminals 2021.

In response to a transfer request signal received from a data server, the data collection server 2024 may register the data server specified in the transfer request signal as a new transfer destination and transfer subsequently received location-related data to that data server.

The data collection server 2024 may store the location-related data received from the terminal 2021 in a recording device, and in response to a transmission request signal received from the terminal 2021 or the data server, may transmit the location-related data specified in the transmission request signal to the requesting terminal 2021 or data server.

The data collection server 2024 may determine whether or not it can provide the location-related data to the requesting data server or terminal 2021, and if it determines that it can provide the data, it may transfer or transmit the location-related data to the requesting data server or terminal 2021.

When a request for current location-related data is received from client device 2026, even if it is not the timing for terminal 2021 to transmit location-related data, data collection server 2024 may request terminal 2021 to transmit location-related data, and terminal 2021 may transmit the location-related data in response to the transmission request.

In the above explanation, it is stated that terminal 2021 transmits location information data to data collection server 2024, but data collection server 2024 may also have functions necessary for collecting location-related data from terminal 2021, such as a function for managing terminal 2021, or functions used when collecting location-related data from terminal 2021.

The data collection server 2024 may have the function of transmitting a data request signal to the terminal 2021 requesting the transmission of location information data and collecting location-related data.

Management information such as an address for communicating with the terminal 2021 from which data is to be collected or an identifier unique to the terminal 2021 is pre-registered in the data collection server 2024. The data collection server 2024 collects location-related data from the terminal 2021 based on the registered management information. The management information may include information such as the type of sensor equipped in the terminal 2021, the number of sensors equipped in the terminal 2021, and the communication method supported by the terminal 2021.

The data collection server 2024 may collect information from the terminal 2021, such as the operating status or current location of the terminal 2021.

Registration of management information may be performed from the client device 2026, or the registration process may be initiated by the terminal 2021 sending a registration request to the data collection server 2024. The data collection server 2024 may have a function to control communication with the terminal 2021.

The communication between the data collection server 2024 and the terminal 2021 may be a dedicated line provided by a service provider such as an MNO (Mobile Network Operator) or MVNO (Mobile Virtual Network Operator), or a virtual dedicated line configured using a VPN (Virtual Private Network). This configuration enables secure communication between the terminal 2021 and the data collection server 2024.

The data collection server 2024 may have a function to authenticate the terminal 2021 or a function to encrypt data transmitted and received between the terminal 2021. Here, the authentication process for the terminal 2021 or the data encryption process is performed using an identifier unique to the terminal 2021 or an identifier unique to a terminal group including multiple terminals 2021, which is shared in advance between the data collection server 2024 and the terminal 2021. This identifier is, for example, an IMSI (International Mobile Subscriber Identity), which is a unique number stored in a SIM (Subscriber Identity Module) card. The identifier used in the authentication process and the identifier used in the data encryption process may be the same or different.

The authentication or data encryption process between the data collection server 2024 and the terminal 2021 can be provided as long as both the data collection server 2024 and the terminal 2021 have the functionality to perform the process, and is independent of the communication method used by the relaying communication device 2022. Therefore, a common authentication or encryption process can be used regardless of the communication method used by the relaying communication device 2021, improving the convenience of system construction for users. However, being independent of the communication method used by the relaying communication device 2022 means that it is not necessary to change it depending on the communication method. In other words, for the purpose of improving transmission efficiency or ensuring security, the authentication or data encryption process between the data collection server 2024 and the terminal 2021 may be switched depending on the communication method used by the relaying device.

The data collection server 2024 may provide the client device 2026 with a UI for managing data collection rules, such as the type of location-related data to be collected from the terminal 2021 and the data collection schedule. This allows the user to use the client device 2026 to specify the terminal 2021 from which data is to be collected, as well as the time and frequency of data collection. The data collection server 2024 may also specify an area on a map from which data is to be collected, and collect location-related data from the terminal 2021 included in that area.

When managing data collection rules on a per-terminal 2021 basis, the client device 2026, for example, presents a list of the terminals 2021 or sensors to be managed on the screen. The user sets whether or not data collection is required and the collection schedule for each item on the list.

When specifying an area on a map from which data is to be collected, the client device 2026 presents, for example, a two-dimensional or three-dimensional map of the area to be managed on the screen. The user selects the area from which data is to be collected on the displayed map. The area selected on the map may be a circular or rectangular area centered on a point specified on the map, or a circular or rectangular area that can be specified by dragging. The client device 2026 may also select an area in pre-defined units such as a city, an area within a city, a block, or a major road. Instead of specifying an area using a map, the area may be set by entering numerical latitude and longitude coordinates, or the area may be selected from a list of candidate areas derived based on input text information. The text information may be, for example, the name of a region, city, or landmark.

In addition, the user may specify one or more terminals 2021 and set conditions such as a range of 100 meters around the terminal 2021, allowing data to be collected while dynamically changing the specified area.

Furthermore, if the client device 2026 is equipped with a sensor such as a camera, an area on a map may be designated based on the position of the client device 2026 in real space obtained from the sensor data. For example, the client device 2026 may estimate its own position using the sensor data and designate an area within a predetermined distance or a user-specified distance from a point on the map corresponding to the estimated position as an area from which data is to be collected. The client device 2026 may also designate the sensing area of the sensor, i.e., the area corresponding to the acquired sensor data, as an area from which data is to be collected. Alternatively, the client device 2026 may designate an area based on a position corresponding to the user-specified sensor data as an area from which data is to be collected. The area on the map or the location corresponding to the sensor data may be estimated by the client device 2026 or by the data collection server 2024.

When specifying an area on a map, the data collection server 2024 may identify the terminals 2021 within the specified area by collecting current location information of each terminal 2021, and request the identified terminals 2021 to transmit location-related data. Alternatively, rather than the data collection server 2024 identifying the terminals 2021 within the area, the data collection server 2024 may transmit information indicating the specified area to the terminal 2021, determine whether the terminal 2021 is within the specified area, and transmit location-related data if it is determined that the terminal 2021 is within the specified area.

The data collection server 2024 transmits to the client device 2026 data such as lists or maps for providing the above-mentioned UI (User Interface) in the application executed by the client device 2026. The data collection server 2024 may transmit not only data such as lists or maps but also application programs to the client device 2026. The above-mentioned UI may also be provided as content created in HTML or the like that can be displayed in a browser. Note that some data, such as map data, may be provided from a server other than the data collection server 2024, such as the map server 2025.

When the user inputs information to notify that the input is complete, such as by pressing a settings button, the client device 2026 transmits the input information as setting information to the data collection server 2024. Based on the setting information received from the client device 2026, the data collection server 2024 transmits a signal to each terminal 2021 requesting location-related data or notifying the rules for collecting location-related data, and collects location-related data.

Next, we will explain an example of controlling the operation of terminal 2021 based on additional information added to three-dimensional or two-dimensional map data.

In this configuration, object information indicating the position of a power supply unit such as a wireless power supply antenna or power supply coil buried in a road or parking lot is included in or associated with the three-dimensional data and provided to a terminal 2021, such as a car or drone.

When a vehicle or drone acquires the object information to charge, it automatically moves its own position so that the position of its charging antenna, charging coil, or other charging unit faces the area indicated by the object information, and charging begins. In the case of a vehicle or drone without an autonomous driving function, the driver or operator is informed of the direction to move or the operation to be performed using images displayed on a screen or audio. When it is determined that the position of the charging unit calculated based on the vehicle's estimated position is within the area indicated by the object information or within a specified distance from that area, the image or audio displayed changes to one requesting the driver or operator to stop driving or operating the vehicle, and charging begins.

In addition, the object information may not be information indicating the position of the power supply unit, but may be information indicating an area within which a charging efficiency equal to or greater than a predetermined threshold can be achieved when a charging unit is placed. The position of the object information may be represented by a point at the center of the area indicated by the object information, or by an area or line in a two-dimensional plane, or an area, line, or plane in three-dimensional space.

This configuration makes it possible to determine the position of the power feeding antenna, which cannot be determined from LiDER sensing data or camera images, and therefore allows for more accurate alignment of the wireless charging antenna installed in a vehicle or other device 2021 with a wireless power feeding antenna buried in a road or other location. As a result, it is possible to shorten the charging speed during wireless charging and improve charging efficiency.

The object information may be an object other than a power supply antenna. For example, the three-dimensional data may include the position of a millimeter wave wireless communication AP as object information. This allows terminal 2021 to know the position of the AP in advance, and therefore to start communication by directing the beam in the direction of the object information. As a result, it is possible to improve communication quality by improving transmission speed, shortening the time until communication starts, and extending the period during which communication is possible.

The object information may include information indicating the type of object corresponding to the object information. The object information may also include information indicating the processing that the terminal 2021 should perform when the terminal 2021 is within an area in real space corresponding to the position of the three-dimensional data of the object information, or within a predetermined distance from the area.

The object information may be provided from a server different from the server that provides the three-dimensional data. If the object information is provided separately from the three-dimensional data, object groups containing object information used in the same service may be provided as separate data depending on the type of target service or target device.

The three-dimensional data used in combination with object information may be WLD point cloud data or SWLD feature point data.

When a three-dimensional data encoding device hierarchically encodes attribute information of a target three-dimensional point, which is the three-dimensional point to be encoded, using LoD (Level of Detail), the three-dimensional data decoding device decodes attribute information up to the LoD level required by the three-dimensional data decoding device, and does not need to decode attribute information in levels that are not required. For example, if the total number of LoDs of attribute information in a bitstream encoded by the three-dimensional data encoding device is N, the three-dimensional data decoding device may decode M (M < N) LoDs from LoD0 to LoD(M-1) in the top layer, and not need to decode the remaining LoDs up to LoD(N-1). This allows the three-dimensional data decoding device to decode attribute information from LoD0 to LoD(M-1) required by the three-dimensional data decoding device while reducing processing load.

Figure 102 is a diagram illustrating the above use case. In the example shown in Figure 102, the server holds a three-dimensional map obtained by encoding three-dimensional position information and attribute information. The server (three-dimensional data encoding device) broadcasts the three-dimensional map to client devices (three-dimensional data decoding devices: for example, vehicles or drones) in the area managed by the server, and the client devices use the three-dimensional map received from the server to determine their own location, or to display map information to a user operating the client device.

An example of operation in this example is explained below. First, the server encodes the location information of the 3D map using an octree structure or the like. Then, the server hierarchically encodes the attribute information of the 3D map using N LoDs constructed based on the location information. The server saves the bitstream of the 3D map obtained by hierarchical encoding.

The server then transmits the encoded 3D map bitstream to the client device in response to a request for map information sent from the client device in the area managed by the server.

The client device receives the 3D map bitstream transmitted from the server and decodes the location information and attribute information of the 3D map according to the client device's intended use. For example, if the client device performs highly accurate self-location estimation using location information and attribute information for N LoDs, the client device determines that it needs decoded results down to dense 3D points as attribute information and decodes all information in the bitstream.

In addition, when a client device displays three-dimensional map information to a user, etc., the client device determines that it needs decoded results up to sparse three-dimensional points as attribute information, and decodes the location information and attribute information of LoDs from LoD0 to M (M < N) which are in the upper layer of LoD.

In this way, by switching the LoD of the attribute information to be decoded depending on the purpose of the client device, the processing load on the client device can be reduced.

In the example shown in Figure 102, for example, the 3D point map includes location information and attribute information. The location information is coded using an octree. The attribute information is coded using N LoDs.

Client device A performs highly accurate self-location estimation. In this case, client device A determines that all location information and attribute information is necessary, and decodes all location information in the bitstream and all attribute information consisting of N LoDs.

Client device B displays a three-dimensional map to the user. In this case, client device B determines that location information and attribute information of M (M < N) LoDs are necessary, and decodes the location information in the bitstream and the attribute information consisting of M LoDs.

The server may broadcast, multicast, or unicast the 3D map to the client device.

The following describes a modified example of the system according to this embodiment. When a three-dimensional data encoding device hierarchically encodes attribute information of a target three-dimensional point, which is the three-dimensional point to be encoded, using LoD, the three-dimensional data encoding device may encode attribute information up to the LoD layer required by the three-dimensional data decoding device, and may not encode attribute information in layers that are not required. For example, if the total number of LoDs is N, the three-dimensional data encoding device may generate a bitstream by encoding M (M<N) LoDs from the top layer LoD0 to LoD(M-1) and not encoding the remaining LoDs up to LoD(N-1). In this way, the three-dimensional data encoding device can provide a bitstream that encodes attribute information required by the three-dimensional data decoding device from LoD0 to LoD(M-1) in response to a request from the three-dimensional data decoding device.

Figure 103 is a diagram illustrating the above use case. In the example shown in Figure 103, the server holds a three-dimensional map obtained by encoding three-dimensional position information and attribute information. The server (three-dimensional data encoding device) unicasts the three-dimensional map to client devices (three-dimensional data decoding devices: for example, vehicles or drones) in the area managed by the server in response to a request from the client device, and the client device uses the three-dimensional map received from the server to determine its own location or display the map information to a user operating the client device.

An example of operation in this example is described below. First, the server encodes the location information of the 3D map using an octree structure or the like. Then, the server generates a bitstream of 3D map A by hierarchically encoding the attribute information of the 3D map using N LoDs constructed based on the location information, and stores the generated bitstream on the server. Furthermore, the server generates a bitstream of 3D map B by hierarchically encoding the attribute information of the 3D map using M (M<N) LoDs constructed based on the location information, and stores the generated bitstream on the server.

The client device then requests the server to transmit a 3D map according to the client device's intended use. For example, when performing highly accurate self-location estimation using location information and attribute information for N LoDs, the client device determines that decoded results down to dense 3D points are required as attribute information, and requests the server to transmit a bitstream of 3D map A. Furthermore, when displaying 3D map information to a user, the client device determines that decoded results down to sparse 3D points are required as attribute information, and requests the server to transmit a bitstream of 3D map B, which includes location information and attribute information for up to M (M<N) LoDs from LoD0 in the upper LoD layer. The server then transmits the bitstream of encoded 3D map A or 3D map B to the client device in response to a request to transmit map information from the client device.

The client device receives the bitstream of 3D map A or 3D map B sent from the server depending on the client device's intended use, and decodes the bitstream. In this way, the server switches the bitstream to be sent depending on the client device's intended use. This reduces the processing load on the client device.

In the example shown in Figure 103, the server holds three-dimensional maps A and B. The server generates three-dimensional map A by encoding the position information of the three-dimensional map, for example, using an octree, and encoding the attribute information of the three-dimensional map using N LoDs. In other words, the NumLoD included in the bitstream of three-dimensional map A indicates N.

The server also generates three-dimensional map B by encoding the location information of the three-dimensional map, for example, using an octree, and encoding the attribute information of the three-dimensional map using M LoDs. In other words, the NumLoD included in the bitstream of three-dimensional map B indicates M.

Client device A performs highly accurate self-location estimation. In this case, client device A determines that all location information and attribute information is required, and sends a request to the server to send 3D map A containing all location information and attribute information consisting of N LoDs. Client device A receives 3D map A and decodes all location information and attribute information consisting of N LoDs.

Client device B displays a three-dimensional map to the user. In this case, client device B determines that location information and attribute information for M (M<N) LoDs are required, and sends a request to the server to send three-dimensional map B containing all location information and attribute information consisting of M LoDs. Client device B receives three-dimensional map B and decodes all location information and attribute information consisting of M LoDs.

In addition to three-dimensional map B, the server (three-dimensional data encoding device) may encode three-dimensional map C, which encodes the attribute information of the remaining N-M LoDs, and transmit three-dimensional map C to client device B upon request from client device B. Client device B may also obtain the decoded results of the N LoDs using the bitstreams of three-dimensional map B and three-dimensional map C.

An example of application processing is described below. Figure 104 is a flowchart showing an example of application processing. When application operation is started, the three-dimensional data demultiplexing device acquires an ISOBMFF file containing point cloud data and multiple pieces of encoded data (S7301). For example, the three-dimensional data demultiplexing device may acquire the ISOBMFF file via communication or may read it from stored data.

Next, the three-dimensional data demultiplexing device analyzes the overall configuration information in the ISOBMFF file and identifies the data to be used for the application (S7302). For example, the three-dimensional data demultiplexing device acquires data to be used for processing and does not acquire data not to be used for processing.

Next, the three-dimensional data demultiplexing device extracts one or more data to be used for the application and analyzes the configuration information of the data (S7303).

If the data type is coded data (coded data in S7304), the three-dimensional data demultiplexing device converts the ISOBMFF into a coded stream and extracts the timestamp (S7305). The three-dimensional data demultiplexing device may also determine whether or not the data is synchronized by, for example, referencing a flag indicating whether or not the data is synchronized, and may perform synchronization processing if the data is not synchronized.

Next, the three-dimensional data demultiplexing device decodes the data in a predetermined manner according to the timestamp and other instructions, and processes the decoded data (S7306).

On the other hand, if the data type is coded data (RAW data in S7304), the three-dimensional data demultiplexing device extracts the data and timestamp (S7307). The three-dimensional data demultiplexing device may also determine whether the data is synchronized, for example, by referring to a flag indicating whether the data is synchronized, and perform synchronization processing if it is not. Next, the three-dimensional data demultiplexing device processes the data in accordance with the timestamp and other instructions (S7308).

For example, we will explain an example where the sensor signals acquired by beam LiDAR, FLASH LiDAR, and a camera are each encoded and multiplexed using different encoding methods. Figure 105 is a diagram showing an example of the sensor ranges of beam LiDAR, FLASH LiDAR, and a camera. For example, beam LiDAR detects in all directions around the vehicle (sensor), while FLASH LiDAR and a camera detect a range in one direction (e.g., forward) of the vehicle.

For applications that handle LiDAR point clouds in an integrated manner, the 3D data demultiplexer references the overall configuration information to extract and decode the coded data from beam LiDAR and FLASH LiDAR. The 3D data demultiplexer does not extract camera images.

The three-dimensional data demultiplexing device processes the encoded data of each with the same timestamp simultaneously according to the timestamps of the LiDAR and FLASH LiDAR.

For example, the three-dimensional data demultiplexing device may present the processed data on a presentation device, combine point cloud data from beam LiDAR and FLASH LiDAR, or perform processing such as rendering.

In addition, in applications that require calibration between data, the three-dimensional data demultiplexing device may extract sensor position information and use it in the application.

For example, the three-dimensional data demultiplexing device may select whether to use beam LiDAR information or FLASH LiDAR in an application and switch processing depending on the selection result.

In this way, data acquisition and encoding processes can be adaptively changed according to application processing, thereby reducing processing volume and power consumption.

The following describes use cases in autonomous driving. Figure 106 is a diagram showing an example configuration of an autonomous driving system. This autonomous driving system includes a cloud server 7350 and an edge 7360 such as an in-vehicle device or a mobile device. The cloud server 7350 includes a demultiplexing unit 7351, decoding units 7352A, 7352B, and 7355, a point cloud data synthesis unit 7353, a large-scale data accumulation unit 7354, a comparison unit 7356, and an encoding unit 7357. The edge 7360 includes sensors 7361A and 7361B, point cloud data generation units 7362A and 7362B, a synchronization unit 7363, encoding units 7364A and 7364B, a multiplexing unit 7365, an update data storage unit 7366, a demultiplexing unit 7367, a decoding unit 7368, a filter 7369, a self-position estimation unit 7370, and a driving control unit 7371.

In this system, the edge 7360 downloads large-scale data, which is large-scale point cloud map data stored in the cloud server 7350. The edge 7360 performs self-location estimation processing for the edge 7360 (vehicle or terminal) by matching the large-scale data with sensor information obtained by the edge 7360. The edge 7360 also uploads the obtained sensor information to the cloud server 7350 and updates the large-scale data to the latest map data.

In addition, various applications that handle point cloud data within the system handle point cloud data using different encoding methods.

The cloud server 7350 encodes and multiplexes the large-scale data. Specifically, the encoding unit 7357 performs encoding using a third encoding method suitable for encoding large-scale point clouds. The encoding unit 7357 also multiplexes the encoded data. The large-scale data storage unit 7354 stores the data encoded and multiplexed by the encoding unit 7357.

Edge 7360 performs sensing. Specifically, point cloud data generation unit 7362A generates first point cloud data (position information (geometry) and attribute information) using sensing information acquired by sensor 7361A. Point cloud data generation unit 7362B generates second point cloud data (position information and attribute information) using sensing information acquired by sensor 7361B. The generated first point cloud data and second point cloud data are used for self-position estimation or vehicle control for autonomous driving, or map updating. In each process, part of the information from the first point cloud data and second point cloud data may be used.

The edge 7360 performs self-location estimation. Specifically, the edge 7360 downloads large-scale data from the cloud server 7350. The demultiplexing unit 7367 demultiplexes the large-scale data in file format to obtain encoded data. The decoding unit 7368 decodes the obtained encoded data to obtain large-scale data, which is large-scale point cloud map data.

The self-position estimation unit 7370 estimates the vehicle's self-position on the map by matching the acquired large-scale data with the first point cloud data and second point cloud data generated by the point cloud data generation units 7362A and 7362B. The driving control unit 7371 also uses the matching results or the self-position estimation results for driving control.

The self-position estimation unit 7370 and the driving control unit 7371 may extract specific information, such as location information, from the large-scale data and perform processing using the extracted information. Furthermore, the filter 7369 performs processing such as correction or thinning on the first point cloud data and the second point cloud data. The self-position estimation unit 7370 and the driving control unit 7371 may use the first point cloud data and the second point cloud data after this processing has been performed. Furthermore, the self-position estimation unit 7370 and the driving control unit 7371 may use sensor signals obtained by sensors 7361A and 7361B.

The synchronization unit 7363 performs time synchronization and position correction between multiple sensor signals or multiple point cloud data. The synchronization unit 7363 may also correct the position information of the sensor signals or point cloud data to match the large-scale data based on position correction information between the large-scale data and the sensor data generated by the self-position estimation process.

Note that synchronization and position correction may be performed by the cloud server 7350 rather than the edge 7360. In this case, the edge 7360 may multiplex the synchronization information and position information and transmit them to the cloud server 7350.

Edge 7360 encodes and multiplexes sensor signals or point cloud data. Specifically, the sensor signals or point cloud data are encoded using a first encoding method or a second encoding method suitable for encoding the respective signals. For example, encoding unit 7364A generates first encoded data by encoding the first point cloud data using the first encoding method. Encoding unit 7364B generates second encoded data by encoding the second point cloud data using the second encoding method.

The multiplexing unit 7365 generates a multiplexed signal by multiplexing the first encoded data, the second encoded data, synchronization information, etc. The update data storage unit 7366 stores the generated multiplexed signal. The update data storage unit 7366 also uploads the multiplexed signal to the cloud server 7350.

The cloud server 7350 synthesizes the point cloud data. Specifically, the demultiplexing unit 7351 demultiplexes the multiplexed signal uploaded to the cloud server 7350 to obtain first encoded data and second encoded data. The decoding unit 7352A decodes the first encoded data to obtain first point cloud data (or sensor signal). The decoding unit 7352B decodes the second encoded data to obtain second point cloud data (or sensor signal).

The point cloud data synthesis unit 7353 synthesizes the first point cloud data and the second point cloud data using a predetermined method. If synchronization information and position correction information are multiplexed in the multiplexed signal, the point cloud data synthesis unit 7353 may use this information to perform synthesis.

The decoding unit 7355 demultiplexes and decodes the large-scale data stored in the large-scale data storage unit 7354. The comparison unit 7356 compares the point cloud data generated based on the sensor signals obtained by the edge 7360 with the large-scale data held by the cloud server 7350, and determines which point cloud data needs to be updated. The comparison unit 7356 updates the point cloud data determined to need to be updated from the large-scale data to the point cloud data obtained from the edge 7360.

The encoding unit 7357 encodes and multiplexes the updated large-scale data and stores the resulting data in the large-scale data storage unit 7354.

As described above, the signals handled may differ depending on the intended use or application, and the signals or encoding methods to be multiplexed may also differ. Even in such cases, multiplexing data of various encoding methods using this embodiment enables flexible decoding and application processing. Furthermore, even if the signal encoding method is different, converting to an encoding method more suitable for demultiplexing, decoding, data conversion, encoding, and multiplexing processing makes it possible to build a variety of applications and systems and provide flexible services.

Below, examples of decoding and application of split data will be explained. First, the information on the split data will be explained. Figure 107 is a diagram showing an example of the configuration of a bit stream. The overall information on the split data indicates the sensor ID (sensor_id) and data ID (data_id) of each split data. The data ID is also indicated in the header of each encoded data.

Note that, similar to FIG. 92, the overall information of the divided data shown in FIG. 107 may include at least one of the following in addition to the sensor ID: sensor information (Sensor), sensor version (Version), sensor manufacturer name (Maker), sensor installation information (Mount Info.), and sensor location coordinates (World Coordinate). This allows the three-dimensional data decoding device to obtain information about various sensors from the configuration information.

The overall information about the split data may be stored in the metadata SPS, GPS, or APS, or in the SEI, which is metadata that is not essential for encoding. Furthermore, the 3D data encoding device stores the SEI in an ISOBMFF file during multiplexing. The 3D data decoding device can obtain the desired split data based on the metadata.

In Figure 107, SPS is metadata for the entire encoded data, GPS is metadata for location information, APS is metadata for each attribute information, G is encoded data for location information for each divided data, and A1 etc. are encoded data for attribute information for each divided data.

Next, we will explain an example application for divided data. We will explain an example application that selects any point cloud from point cloud data and presents the selected point cloud. Figure 108 is a flowchart of the point cloud selection process executed by this application. Figures 109 to 111 are figures showing example screens for the point cloud selection process.

As shown in FIG. 109, the three-dimensional data decoding device that executes the application has, for example, a UI unit that displays an input UI (user interface) 8661 for selecting an arbitrary point cloud. The input UI 8661 has a presentation unit 8662 that presents the selected point cloud and an operation unit (buttons 8663 and 8664) that accepts user operations. After a point cloud is selected in the UI 8661, the three-dimensional data decoding device obtains the desired data from the storage unit 8665.

First, the point cloud information that the user wants to display is selected based on the user's operation on input UI 8661 (S8631). Specifically, by selecting button 8663, a point cloud based on sensor 1 is selected. By selecting button 8664, a point cloud based on sensor 2 is selected. Alternatively, by selecting both buttons 8663 and 8664, both the point cloud based on sensor 1 and the point cloud based on sensor 2 are selected. Note that the method of selecting point clouds is an example and is not limited to this.

Next, the three-dimensional data decoding device analyzes the overall information of the divided data contained in the multiplexed signal (bit stream) or encoded data, and identifies the data IDs (data_id) of the divided data that make up the selected point cloud from the sensor ID (sensor_id) of the selected sensor (S8632). Next, the three-dimensional data decoding device extracts encoded data containing the identified desired data ID from the multiplexed signal, and decodes the extracted encoded data to decode the point cloud based on the selected sensor (S8633). Note that the three-dimensional data decoding device does not decode other encoded data.

Finally, the three-dimensional data decoding device presents (e.g., displays) the decoded point cloud (S8634). Figure 110 shows an example where the sensor 1 button 8663 is pressed, and the point cloud of sensor 1 is presented. Figure 111 shows an example where both the sensor 1 button 8663 and the sensor 2 button 8664 are pressed, and the point clouds of sensor 1 and sensor 2 are presented.

The above describes a three-dimensional data encoding device and a three-dimensional data decoding device relating to embodiments of the present disclosure, but the present disclosure is not limited to these embodiments.

Furthermore, each processing unit included in the three-dimensional data encoding device and three-dimensional data decoding device according to the above embodiments is typically realized as an LSI, which is an integrated circuit. These may be individually implemented on a single chip, or some or all of them may be included on a single chip.

In addition, integrated circuits are not limited to LSIs, but may be realized using dedicated circuits or general-purpose processors. FPGAs (Field Programmable Gate Arrays), which can be programmed after LSI manufacturing, or reconfigurable processors, which allow the connections and settings of circuit cells within an LSI to be reconfigured, may also be used.

Furthermore, in each of the above embodiments, each component may be configured with dedicated hardware or may be realized by executing a software program appropriate for each component. Each component may also be realized by a program execution unit such as a CPU or processor reading and executing a software program recorded on a recording medium such as a hard disk or semiconductor memory.

The present disclosure may also be realized as a three-dimensional data encoding method or a three-dimensional data decoding method executed by a three-dimensional data encoding device, a three-dimensional data decoding device, etc.

Furthermore, the division of functional blocks in the block diagram is one example, and multiple functional blocks may be realized as a single functional block, one functional block may be divided into multiple blocks, or some functions may be moved to other functional blocks. Furthermore, the functions of multiple functional blocks with similar functions may be processed in parallel or time-shared by a single piece of hardware or software.

The order in which each step in the flowchart is performed is merely an example to specifically explain the present disclosure, and orders other than those described above may also be used. Furthermore, some of the steps may be performed simultaneously (in parallel) with other steps.

The above describes three-dimensional data encoding devices and three-dimensional data decoding devices according to one or more aspects based on embodiments, but the present disclosure is not limited to these embodiments. Various modifications conceivable by those skilled in the art to these embodiments, as well as configurations constructed by combining components from different embodiments, may also be included within the scope of one or more aspects, provided they do not deviate from the spirit of the present disclosure.

This disclosure is applicable to three-dimensional data encoding devices and three-dimensional data decoding devices.

810 Three-dimensional data creation device 811 Data receiving unit 812, 819 Communication unit 813 Reception control unit 814, 821 Format conversion unit 815 Sensor 816 Three-dimensional data creation unit 817 Three-dimensional data synthesis unit 818 Three-dimensional data accumulation unit 820 Transmission control unit 822 Data transmission unit 831, 832, 834, 835, 836, 837 Three-dimensional data 833 Sensor information 901 Server 902, 902A, 902B, 902C Client device 1011, 1111 Data receiving unit 1012, 1020, 1112, 1120 Communication unit 1013, 1113 Reception control unit 1014, 1019, 1114, 1119 Format conversion unit 1015 Sensor 1016, 1116 3D data creation unit 1017 3D image processing unit 1018, 1118 3D data accumulation unit 1021, 1121 Transmission control unit 1022, 1122 Data transmission unit 1031, 1032, 1135 3D map 1033, 1037, 1132 Sensor information 1034, 1035, 1134 3D data 1117 3D data synthesis unit 1201 3D map compression/decoding processing unit 1202 Sensor information compression/decoding processing unit 1211 3D map decoding processing unit 1212 Sensor information compression processing unit 2001 Server 2002, 2002A, 2002B Client device 2011 Sensor information acquisition unit 2012 Storage unit 2013 Data transmission possibility determination unit 2021, 2021A, 2021B Terminal 2022, 2022A, 2022B Communication device 2023 Network 2024 Data collection server 2025 Map server 2026 Client device 2700 Position information encoding unit 2701, 2711 Octree generation unit 2702, 2712 Geometric information calculation unit 2703, 2713 Encoding table selection unit 2704 Entropy encoding unit 2710 Position information decoding unit 2714 Entropy decoding unit 3140 Attribute information encoding unit 3141, 3151 LoD generation unit 3142, 3152 Surroundings search unit 3143, 3153 Prediction unit 3144 Prediction residual calculation unit 3145 Quantization unit 3146 Arithmetic encoding unit 3147, 3155 Inverse quantization unit 3148, 3156 Decoded value generation unit 3149, 3157 Memory 3150 Attribute information decoding unit 3154 Arithmetic decoding unit 4601 Three-dimensional data encoding system 4602 Three-dimensional data decoding system 4603 Sensor terminal 4604 External connection unit 4611 Point cloud data generation system 4612 Presentation unit 4613 Encoding unit 4614 Multiplexing unit 4615 Input/output unit 4616 Control unit 4617 Sensor information acquisition unit 4618 Point cloud data generation unit 4621 Sensor information acquisition unit 4622 Input/output unit 4623 Demultiplexing unit 4624 Decoding unit 4625 Presentation unit 4626 User interface 4627 Control unit 4630 First encoding unit 4631 Position information encoding unit 4632 Attribute information encoding unit 4633 Additional information encoding unit 4634 Multiplexing unit 4640 First decoding unit 4641 Demultiplexing unit 4642 Position information decoding unit 4643 Attribute information decoding unit 4644 Additional information decoding unit 4650 Second encoding unit 4651 Additional information generation unit 4652 Position image generation unit 4653 Attribute image generation unit 4654 Video encoding unit 4655 Additional information encoding unit 4656 Multiplexing unit 4660 Second decoding unit 4661 Demultiplexing unit 4662 Video decoding unit 4663 Additional information decoding unit 4664 Position information generation unit 4665 Attribute information generation unit 4801 Encoding unit 4802 Multiplexing unit 6600 Attribute information encoding unit 6601 Sorting unit 6602 Haar conversion unit 6603 Quantization unit 6604, 6612 Inverse quantization unit 6605, 6613 Inverse Haar transform unit 6606, 6614 Memory 6607 Arithmetic coding unit 6610 Attribute information decoding unit 6611 Arithmetic decoding unit 7350 Cloud server 7351 Demultiplexing unit 7352A, 7352B Decoding unit 7353 Point cloud data synthesis unit 7354 Large-scale data accumulation unit 7355 Decoding unit 7356 Comparison unit 7357 Encoding unit 7360 Edge 7361A, 7361B Sensor 7362A, 7362B Point cloud data generation unit 7363 Synchronization unit 7364A, 7364B Encoding unit 7365 Multiplexing unit 7366 Update data accumulation unit 7367 Demultiplexing unit 7368 Decoding unit 7369 Filter 7370 Self-position estimation unit 7371 Driving control unit 8661 Input UI
8662 Presentation unit 8663, 8664 Button 8665 Storage unit 12800, 12800A Three-dimensional data encoding device 12801, 12809 Octree generation unit 12802 Buffer 12803 Entropy encoding unit 12804, 12805, 12807, 12810 Buffer 12806 Point group generation unit 12808 Motion detection and compensation unit 12811 Control unit 12812 Motion compensation unit 12820, 12820A Three-dimensional data decoding device 12821 Entropy decoding unit 12822, 12823, 12825, 12828 Buffer 12824 Point group generation unit 12826 Motion compensation unit 12827 Octree generation unit 12829 Control unit 12830 Motion compensation unit 12900, 12930 Three-dimensional data encoding device 12901, 12932 Grouping unit 12902, 12905, 12907, 12923, 12925, 12933, 12934, 12936, 12941, 12952, 12954 Buffer 12903, 12942 Quantization unit 12904, 12922, 12959 Inverse quantization unit 12906, 12924, 12935, 12953 Intra prediction unit 12908, 12937 Motion estimation and compensation unit 12909, 12927, 12938, 12956 Inter prediction unit 12910, 12928, 12939, 12957 Switching unit 12911, 12943 Entropy coding unit 12920, 12950 Three-dimensional data decoding device 12921, 12951 Entropy decoding unit 12926, 12955 Motion compensation unit 12931, 12940, 12958 Coordinate transformation unit 13601, 13612, 13621 Prediction unit 13602, 13616, 13622 Quantization unit 13603, 13613, 13617, 13623 Encoding unit 13611, 13614, 13644 Transformation unit 13615 Subtraction unit 13618, 13665 Combination unit 13631, 13642, 13645, 13651 Decoding units 13632, 13646, 13652 Inverse quantization units 13633, 13643, 13653 Reconstruction units 13641, 13671 Separation units 13647 Addition units 13661 Overlap point joining units 13662 Position information encoding units 13663 Attribute information conversion units 13664 Attribute information encoding units 13672 Position information decoding units 13673 Attribute information decoding units 13700, 13710, 13740 Position information encoding units 13701, 13742, 13763 Shift units 13702, 13711, 13743 Encoding units 13720, 13730, 13750, 13760 Position information decoding units 13721, 13731, 13751, 13761 Decoding units 13722, 13752 Reverse shift units 13741, 13753, 13764 Switching units 13762 Coordinate conversion units A100 Attribute information encoding units A101 LoD attribute information encoding units A102 Transformed attribute information encoding units A110 Attribute information decoding units A111 LoD attribute information decoding units A112 Transformed attribute information decoding units

Claims (18)

Obtain a bitstream containing encoded position information in which position information of the three-dimensional point is encoded;
generating the position information by decoding the encoded position information;
shifting the position information when the position information is expressed in a Cartesian coordinate system;
When the position information is expressed in a polar coordinate system, the position information is not shifted.
Three-dimensional data decoding method. The bitstream comprises:
First flag information indicating whether the position information is expressed in the polar coordinate system;
and second flag information indicating whether the position information expressed in the polar coordinate system is converted into converted position information expressed in the Cartesian coordinate system.
2. The three-dimensional data decoding method according to claim 1. If the position information is expressed in the polar coordinate system and the position of the sensor generating the three-dimensional point is the origin of the polar coordinate system, the shift is not performed.
2. The three-dimensional data decoding method according to claim 1. obtaining shift information indicating the amount of the shift from the bitstream;
When the position information is expressed in the polar coordinate system, the amount indicated by the shift information is zero;
The position information expressed in the polar coordinate system is shifted based on the amount indicated by the shift information, so that the position information expressed in the polar coordinate system is not shifted.
2. The three-dimensional data decoding method according to claim 1. obtaining shift information indicating the amount of the shift from the bitstream;
When the position information is expressed in the Cartesian coordinate system, shifting the position information based on the amount indicated by the shift information;
When the position information is expressed in the polar coordinate system, the amount is considered to be zero regardless of the amount indicated by the shift information.
2. The three-dimensional data decoding method according to claim 1. If the bitstream includes shift information indicating the amount of the shift, determining that the position information is expressed in the Cartesian coordinate system, and shifting the position information based on the amount indicated by the shift information;
If the shift information is not included in the bit stream, it is determined that the position information is expressed in the polar coordinate system, and the position information is not shifted.
2. The three-dimensional data decoding method according to claim 1. the bitstream includes encoded information in which position information of a plurality of three-dimensional points including the three-dimensional point is encoded;
the encoded information is divided into a plurality of division units obtained by dividing the plurality of three-dimensional points,
The shift information is included in a parameter set common to the plurality of division units.
The three-dimensional data decoding method according to any one of claims 4 to 6. the bitstream includes encoded information in which position information of a plurality of three-dimensional points including the three-dimensional point is encoded;
the encoded information is divided into a plurality of division units obtained by dividing the plurality of three-dimensional points,
The shift information is included in a header for each of the plurality of division units.
The three-dimensional data decoding method according to any one of claims 4 to 6. When the position information is expressed in the polar coordinate system, the position information is converted into converted position information expressed in the Cartesian coordinate system, and the converted position information is shifted.
The three-dimensional data decoding method according to any one of claims 1 to 8. Generate encoded position information by encoding the position information of the three-dimensional point;
generating a bitstream including the encoded position information and shift information indicating whether the three-dimensional data decoding device shifts the decoded position information decoded by the three-dimensional data decoding device;
Based on the shift information, the three-dimensional data decoding device
When the decoded position information is expressed in a Cartesian coordinate system, shifting the decoded position information;
When the decoding position information is expressed in a polar coordinate system, the decoding position information is not shifted.
Three-dimensional data encoding method. The bitstream comprises:
First flag information indicating whether the position information is expressed in the polar coordinate system;
and second flag information indicating whether the position information expressed in the polar coordinate system is converted into converted position information expressed in the Cartesian coordinate system.
The three-dimensional data encoding method according to claim 10. If the position information is expressed in the polar coordinate system and the position of the sensor generating the three-dimensional point is the origin of the polar coordinate system, the shift is not performed.
The three-dimensional data encoding method according to claim 10. the shift information indicates an amount of shift when the decoding position information is shifted,
When the position information is expressed in the polar coordinate system, the amount indicated by the shift information is zero;
the three-dimensional data decoding device shifts the position information expressed in the polar coordinate system based on the amount indicated by the shift information, thereby not shifting the position information expressed in the polar coordinate system;
The three-dimensional data encoding method according to claim 10. When the position information is expressed in the orthogonal coordinate system, the shift information indicates an amount of shift when the decoded position information is shifted,
The three-dimensional data encoding method according to claim 10 , wherein when the position information is expressed in the polar coordinate system, the shift information is not stored in the bitstream. the bitstream includes encoded information in which position information of a plurality of three-dimensional points including the three-dimensional point is encoded;
the encoded information is divided into a plurality of division units obtained by dividing the plurality of three-dimensional points,
The shift information is included in a parameter set common to the plurality of division units.
The three-dimensional data encoding method according to any one of claims 10 to 14. the bitstream includes encoded information in which position information of a plurality of three-dimensional points including the three-dimensional point is encoded;
the encoded information is divided into a plurality of division units obtained by dividing the plurality of three-dimensional points,
The shift information is included in a header for each of the plurality of division units.
The three-dimensional data encoding method according to any one of claims 10 to 14. a processor;
a memory;
The processor uses the memory to:
Obtain a bitstream containing encoded position information in which position information of the three-dimensional point is encoded;
generating position information by decoding the encoded position information;
shifting the position information when the position information is expressed in a Cartesian coordinate system;
When the position information is expressed in a polar coordinate system, the position information is not shifted.
Three-dimensional data decoding device. a processor;
a memory;
The processor uses the memory to:
Generate encoded position information by encoding the position information of the three-dimensional point;
generating a bitstream including the encoded position information and shift information indicating whether the three-dimensional data decoding device shifts the decoded position information decoded by the three-dimensional data decoding device;
Based on the shift information, the three-dimensional data decoding device
When the decoded position information is expressed in a Cartesian coordinate system, shifting the decoded position information;
When the decoding position information is expressed in a polar coordinate system, the decoding position information is not shifted.
Three-dimensional data encoding device.