WO2022121648A1 - 点云数据编码方法、解码方法、设备、介质及程序产品 - Google Patents

点云数据编码方法、解码方法、设备、介质及程序产品 Download PDF

Info

Publication number
WO2022121648A1
WO2022121648A1 PCT/CN2021/131278 CN2021131278W WO2022121648A1 WO 2022121648 A1 WO2022121648 A1 WO 2022121648A1 CN 2021131278 W CN2021131278 W CN 2021131278W WO 2022121648 A1 WO2022121648 A1 WO 2022121648A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
point cloud
encoding
point
data points
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CN2021/131278
Other languages
English (en)
French (fr)
Inventor
朱文婕
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Tencent Technology Shenzhen Co Ltd
Original Assignee
Tencent Technology Shenzhen Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Tencent Technology Shenzhen Co Ltd filed Critical Tencent Technology Shenzhen Co Ltd
Priority to EP21902355.3A priority Critical patent/EP4250726A4/en
Publication of WO2022121648A1 publication Critical patent/WO2022121648A1/zh
Priority to US17/974,829 priority patent/US12488507B2/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/001—Model-based coding, e.g. wire frame
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
    • H04N19/597—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding specially adapted for multi-view video sequence encoding
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three-dimensional [3D] modelling for computer graphics
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/004—Predictors, e.g. intraframe, interframe coding
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
    • G06V10/761—Proximity, similarity or dissimilarity measures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N13/00—Stereoscopic video systems; Multi-view video systems; Details thereof
    • H04N13/10—Processing, recording or transmission of stereoscopic or multi-view image signals
    • H04N13/106—Processing image signals
    • H04N13/161—Encoding, multiplexing or demultiplexing different image signal components
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding

Definitions

  • the embodiments of the present application relate to the technical field of point cloud applications, and in particular, to a point cloud data encoding method, decoding method, device, medium, and program product.
  • point cloud data is mainly encoded based on octrees.
  • the octree division method is to evenly divide the preset bounding box layer by layer, each node has eight child nodes, and through the eight The occupancy of each child node of the fork tree is indicated by '1' and '0'.
  • the 3D coordinate information of the point cloud data is converted into the corresponding Morton code by querying the Morton sequence table, and according to the order of each Morton code, the octree of each layer is obtained. corresponding point.
  • the 3D position distribution is relatively scattered, that is, most of the nodes in the octree are empty, resulting in high coding complexity and low coding efficiency based on octrees.
  • the embodiments of the present application provide a point cloud data encoding method, decoding method, device, medium and program product, which can reduce the complexity of encoding point cloud data and improve encoding efficiency.
  • the technical solution is as follows:
  • a point cloud data encoding method which is executed by a computer device, and the method includes:
  • the point cloud data set includes at least two data points
  • the respective data points are sequentially encoded to obtain the encoded point cloud data corresponding to the point cloud data set;
  • the coding order of the respective data points is determined based on the distances between the respective data points.
  • a point cloud data decoding method which is executed by a computer device, and the method includes:
  • the encoded point cloud data is obtained by encoding the respective data points sequentially by the encoding device based on the encoding order of each data point in the point cloud data set;
  • the coding order of the respective data points is determined based on the distance between the respective data points;
  • the reference information is used to indicate the starting reference data point in the encoding queue
  • the respective data points are sequentially decoded according to the encoding order of the respective data points.
  • an apparatus for encoding point cloud data comprising:
  • a point cloud acquisition module configured to acquire a point cloud data set, the point cloud data set includes at least two data points;
  • an encoding module configured to encode the respective data points in sequence according to the encoding order of the respective data points to obtain encoded point cloud data corresponding to the point cloud data set;
  • the coding order of the respective data points is determined based on the distances between the respective data points.
  • the apparatus further includes:
  • the queue adding module is used to encode the respective data points in turn according to the encoding order of the respective data points by the encoding module, and before obtaining the encoded point cloud data corresponding to the point cloud data set, based on the target
  • the distance between data point pairs, each data point in the point cloud data set is added to the encoding queue in turn;
  • the target data point pair is the existing data point in the encoding queue and the point cloud data set.
  • a pair of data points consisting of data points;
  • the encoding module is configured to encode the data points in sequence according to the order of the data points in the encoding queue to obtain encoded point cloud data corresponding to the point cloud data set.
  • the distance between the data point pairs includes:
  • the encoding module is configured to, for any adjacent first data point and second data point in the encoding queue, acquire the second data point and the first data point residual signal between points.
  • the queue adding module is used for,
  • the data points satisfying the specified conditions are sequentially selected from the point cloud data set and added to the encoding queue.
  • the specified conditions include:
  • the distance to the last data point in the encoding queue is the smallest
  • the sum of the distances to the data points already in the encoding queue is the smallest.
  • the apparatus further includes:
  • the initial data point determination module is used to sequentially add each data point in the point cloud data set to the encoding queue based on the distance between the target data point pairs in the queue adding module, in response to the encoding queue being empty, from determining initial data points in the point cloud data set;
  • an initial data point adding module configured to add the initial data point to the encoding queue.
  • the initial data point determination module is used to:
  • the initial data points are determined from the point cloud dataset in response to a data point division manner of the point cloud dataset.
  • the apparatus further includes:
  • the queue adjustment module is used for, before the encoding module sequentially encodes the respective data points according to the order of the respective data points in the encoding queue, based on the distance between adjacent data points in the encoding queue , adjust the order of the data points in the encoding queue.
  • the queue adjustment module is configured to:
  • the first distance is the distance between the i-th data point and the i+1-th data point in the encoding queue
  • the second distance is the encoding
  • the distance between the jth data point and the j+1th data point in the queue; i, j are integers greater than or equal to 1, and i ⁇ j;
  • the third distance is the distance between the i-th data point and the j+1-th data point
  • the fourth distance is the i-th data point the distance between 1 data point and the jth data point
  • the encoding module is configured to, in response to satisfying the sorting termination condition, execute the step of sequentially encoding the respective data points according to the order of the respective data points in the encoding queue ;
  • the termination conditions include:
  • the sum of the distances between the data points in the encoded queue reaches a specified threshold.
  • an apparatus for decoding point cloud data includes:
  • the data acquisition module is used to acquire the coded point cloud data corresponding to the point cloud data set;
  • the coded point cloud data is the coding order of the coding equipment based on each data point in the point cloud data set, and each data point is sequentially obtained by encoding; the encoding order of the respective data points is determined based on the distance between the respective data points;
  • a reference information acquisition module configured to acquire reference information; the reference information is used to indicate a starting reference data point of the encoding queue;
  • the decoding module is configured to decode the respective data points in sequence according to the encoding order of the respective data points based on the reference information and the encoded point cloud data.
  • the encoding device sequentially adds the respective data points to the encoding queue based on the distance between the target data point pairs, and executes the encoding process according to the respective data points.
  • the order in the encoding queue is obtained by encoding the data points in sequence;
  • the target data point pair is formed by the existing data points in the encoding queue and the data points in the point cloud data set data point pair;
  • the decoding module is configured to decode the respective data points in sequence according to the order of the respective data points in the encoding queue based on the reference information and the encoded point cloud data.
  • the reference information acquisition module is used to:
  • the reference information is obtained by parsing the hierarchical information of the data points in the point cloud dataset.
  • a computer device includes a processor and a memory, the memory stores at least one computer program, and the at least one computer program is loaded by the processor and executed. Execute to realize the above point cloud data encoding method or point cloud data decoding method.
  • a computer-readable storage medium where at least one computer program is stored in the computer-readable storage medium, and the at least one computer program is loaded and executed by a processor to implement the above point Cloud data encoding method or point cloud data decoding method.
  • an embodiment of the present application provides a computer program product or computer program, where the computer program product or computer program includes computer instructions, and the computer instructions are stored in a computer-readable storage medium.
  • the processor of the computer device reads the computer instructions from the computer-readable storage medium, and the processor executes the computer instructions, so that the computer device executes the above point cloud data encoding method or point cloud data decoding method.
  • the encoding end device sorts the data points according to the distance between the data points in the point cloud data, and then encodes them in sequence according to the sorting order, so that the data points in the point cloud data that are close in distance can be encoded in sequence, which can While ensuring the accuracy of coding, the coding complexity is significantly reduced, thereby improving the coding efficiency.
  • Fig. 1 is a kind of point cloud application frame diagram exemplarily shown in this application;
  • FIG. 2 is a simplified block diagram of a communication system provided by an embodiment of the present application.
  • Fig. 3 is the schematic diagram of the placement mode of the point cloud encoder and the point cloud decoder exemplarily shown in the present application in the streaming transmission environment;
  • FIG. 4 is a schematic diagram of a coding framework provided by an embodiment of the present application.
  • FIG. 5 is a flowchart of a point cloud data encoding method provided by an embodiment of the present application.
  • FIG. 6 is a flowchart of a point cloud data decoding method provided by an embodiment of the present application.
  • FIG. 7 is a flowchart of a method for encoding and decoding point cloud data provided by an embodiment of the present application.
  • FIG. 8 is a frame diagram of a point cloud data encoding process provided by an embodiment of the present application.
  • FIG. 9 is a block diagram of an apparatus for encoding point cloud data provided by an embodiment of the present application.
  • FIG. 10 is a block diagram of a point cloud data decoding apparatus provided by an embodiment of the present application.
  • FIG. 11 is a structural block diagram of a computer device provided by an embodiment of the present application.
  • a point cloud is a set of discrete points that are randomly distributed in space and express the spatial structure and surface properties of a three-dimensional object or scene.
  • Each point in the point cloud has at least three-dimensional position information, and may also have color, material, or other information depending on the application scenario.
  • each point in a point cloud has the same number of additional properties.
  • each point in the point cloud data can be called a data point.
  • Point cloud can express the spatial structure and surface properties of 3D objects or scenes flexibly and conveniently, so it is widely used. Its main application scenarios can be classified into two categories:
  • Machine perception point cloud such as autonomous navigation system, real-time inspection system, geographic information system, visual sorting robot, emergency rescue robot, etc.;
  • Point clouds such as point cloud application scenarios such as digital cultural heritage, free-view broadcasting, 3D immersive communication, and 3D immersive interaction.
  • the acquisition methods of point clouds include but are not limited to computer generation, 3D laser scanning, and 3D photogrammetry.
  • the computer can generate point clouds of virtual three-dimensional objects and scenes.
  • 3D scanning can obtain point clouds of static real-world 3D objects or scenes, and millions of point clouds can be obtained per second.
  • 3D cameras can obtain point clouds of dynamic real-world three-dimensional objects or scenes, and can obtain tens of millions of point clouds per second.
  • point clouds of biological tissues and organs can be obtained from Magnetic Resonance Imaging (MRI), Computed Tomography (CT), and electromagnetic positioning information.
  • MRI Magnetic Resonance Imaging
  • CT Computed Tomography
  • electromagnetic positioning information electromagnetic positioning information.
  • Point cloud data can be divided into dense point cloud and sparse point cloud according to the way of data acquisition; according to the time series type of data, it can be divided into static point cloud and dynamic point cloud.
  • FIG. 1 shows a frame diagram of a point cloud application involved in an embodiment of the present application.
  • G-PCC data as an example, in Figure 1, at the transmitting end, a real-world virtual scene (A) is captured by a set of cameras or a camera device 11 with multiple lenses and sensors. The acquisition result is the source point cloud data (B).
  • One or more point cloud frames are encoded by the G-PCC encoder 12 into an encoded G-PCC bitstream (E), including an encoded geometry bitstream and an attribute bitstream.
  • the file encapsulator 13 encapsulates one or more encoded bitstreams (E) into a media file (F) for file playback, or into an initialization segment and media for streaming, according to a specific media container file format Sequence of segments (Fs).
  • the file encapsulator 13 also includes metadata into the file or segment, and (Fs) is passed to the user through the delivery mechanism 14; A plurality of encoded bit streams (E'), and decoded (E') by the G-PCC decoder 16 to obtain one or more point cloud frames (D') after decoding, and presented by the presentation component 17 on the display component 18 A virtual scene (A') corresponding to one or more point cloud frames (D') is presented.
  • the TSP problem is a classic combinatorial optimization problem.
  • the classic TSP can be described as: a salesman is going to sell goods in several cities, the salesman starts from a city, needs to go through all the cities, and then returns to the place of departure. How the travel route should be chosen so that the overall trip is the shortest possible. From the point of view of graph theory, the essence of the problem is to find a circuit with the smallest weight in a weighted completely undirected graph. Since the feasible solution of this problem is the full arrangement of all vertices, as the number of vertices increases, combinatorial explosion will occur, and it is a non-deterministic polynomial (NP) complete problem.
  • NP polynomial
  • the city is the vertex of the graph
  • the road is the edge of the graph
  • the distance of the road is the length of the edge. It is a minimization problem that starts and ends at a particular vertex and visits each vertex exactly once.
  • the model is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between the two cities, adding a very long edge can complete the graph without affecting the computation of the optimal loop.
  • Communication system 200 includes a plurality of devices that can communicate with each other via, for example, network 250 .
  • the communication system 200 includes a first device 210 and a second device 220 interconnected by a network 250 .
  • the first device 210 and the second device 220 perform unidirectional data transfer.
  • the first device 210 may encode point cloud data, such as a stream of point cloud frames collected by the first device 210, for transmission to the second device 220 over the network 250.
  • the encoded point cloud data is transmitted as one or more encoded point cloud bitstreams.
  • the second device 220 may receive the encoded point cloud data from the network 250, decode the encoded point cloud data to restore the point cloud data, and present the point cloud according to the restored point cloud data.
  • One-way data transfer is common in applications such as media services.
  • the communication system 200 includes a third device 230 and a fourth device 240 that perform bidirectional transmission of encoded point cloud data.
  • each of the third device 230 and the fourth device 240 may encode the point cloud data for transmission to the other of the third device 230 and the fourth device 240 over the network 250 .
  • Each of the third device 230 and the fourth device 240 may also receive encoded point cloud data transmitted by the other of the third device 230 and the fourth device 240, and may perform an analysis of the encoded point cloud data Decoding is performed to recover the point cloud data, and the point cloud can be displayed on an accessible display device based on the recovered point cloud data.
  • the first device 210 , the second device 220 , the third device 230 and the fourth device 240 may be computer devices such as servers, personal computers and smart phones, but the principles disclosed in this application may not be limited thereto.
  • the embodiments of the present application are applicable to a PC (Personal Computer, personal computer), a mobile phone, a tablet computer, a virtual reality/augmented reality device, a media player, and/or a dedicated video conference device.
  • Network 250 represents any number of networks that communicate encoded point cloud data between first device 210, second device 220, third device 230, and fourth device 240, including, for example, wired and/or wireless communication networks.
  • Communication network 250 may exchange data in circuit-switched and/or packet-switched channels.
  • the network may include a telecommunications network, a local area network, a wide area network, and/or the Internet.
  • the architecture and topology of network 250 may be immaterial to the operations disclosed herein.
  • Figure 3 shows how the point cloud encoder and point cloud decoder are placed in a streaming environment.
  • the subject matter disclosed in this application is equally applicable to other point cloud-enabled applications, including, for example, virtual 3D conferences, digital TV (television), CD (Compact Disc), DVD (Digital Versatile Disc), Storage of compressed point clouds and the like on digital media such as memory sticks.
  • the streaming system may include an acquisition subsystem 313 , which may include a point cloud source 301 , such as a three-dimensional camera, that creates a stream 302 of uncompressed point cloud data. Compared to the encoded point cloud data 304 (or the encoded point cloud bitstream), the point cloud data stream 302 is depicted as a thick line to emphasize the high data volume of the point cloud data stream, which can be obtained by the electronic device.
  • the electronic device 320 including a point cloud encoder 303 coupled to the point cloud source 301 .
  • Point cloud encoder 303 may include hardware, software, or a combination of hardware and software to implement or implement various aspects of the disclosed subject matter as described in greater detail below.
  • encoded point cloud data 304 (or encoded point cloud bitstream 304) is depicted as a thin line to emphasize the lower amount of encoded point cloud data 304 (or encoded point cloud data 304).
  • point cloud bitstream 304 which can be stored on the streaming server 305 for future use.
  • One or more streaming client subsystems such as client subsystem 306 and client subsystem 308 in FIG. 3 , may access streaming server 305 to retrieve copies 307 and 309 of encoded point cloud data 304 .
  • Client subsystem 306 may include, for example, point cloud decoder 310 in electronic device 330 .
  • the point cloud decoder 310 decodes the incoming copy 307 of the encoded point cloud data and produces an output point cloud data stream 311 that can be presented on a display 312 (eg, a display screen) or another presentation device (not depicted).
  • the encoded point cloud data 304, point cloud data 307, and point cloud data 309 may be encoded according to certain point cloud encoding/compression standards.
  • electronic device 320 and electronic device 330 may include other components (not shown).
  • electronic device 320 may include a point cloud decoder (not shown), and electronic device 330 may also include a point cloud encoder (not shown).
  • the point cloud decoder is used to decode the received encoded point cloud data; the point cloud encoder is used to encode the point cloud data.
  • AVS Analog Video coding Standard
  • AVS3 Audio Video coding Standard
  • next-generation video coding standard AVS3
  • AVS3 next-generation video coding standard
  • V-PCC Video-based Point Cloud Compression
  • G-PCC Geometry-based Point Cloud Compression
  • the current point cloud encoding technology can be divided into geometric structure-based point cloud encoding and projection-based point cloud encoding for different point cloud data types.
  • geometric structure-based point cloud encoding G-PCC in the international video and audio codec standard (Moving Picture Expert Group, MPEG), and the point cloud encoding standard in China's national digital video and audio codec standard (AudioVideoCodingStandard-PCC, AVS-PCC ) as an example.
  • FIG. 4 is a schematic diagram of a coding framework provided by an embodiment of the present application.
  • point cloud coding is divided into geometric structure coding and attribute information coding.
  • the main operations and processing are as follows:
  • Pre-processing including coordinate transformation (Transformcoordinates) and voxelization (Voxelize).
  • the point cloud data in the 3D space is converted into integer form, and its minimum geometric position is moved to the coordinate origin.
  • Geometry encoding can contain multiple modes and can be used under different conditions.
  • the above-mentioned geometric coding can be divided into octree-based geometric coding (Octree) and triangular representation-based geometric coding (Trisoup), and so on.
  • geometric entropy encoding Take the octree-based geometric encoding as an example, perform statistical compression encoding on the occupancy code information of the octree, and finally output a binarized (0 or 1) compressed code stream.
  • Statistical coding is a lossless coding method that can effectively reduce the code rate required to express the same signal.
  • a commonly used statistical coding method is context-based binary arithmetic coding (Content Adaptive Binary Arithmetic Coding, CABAC).
  • Predicting Transform Select sub-point sets according to distance, divide the point cloud into multiple different levels (Level of Detail, LoD), and realize the point cloud representation from rough to fine. Bottom-up prediction can be implemented between adjacent layers, that is, the attribute information of the points introduced in the fine layer is predicted from the adjacent points in the rough layer, and the corresponding residual signal is obtained. Among them, the lowest point is encoded as reference information.
  • Lifting Transform Based on the prediction of LoD adjacent layers, the weight update strategy of neighborhood points is introduced, and finally the predicted attribute value of each point is obtained, and the corresponding residual signal is obtained.
  • Hierarchical region adaptive transform coding (Region Adaptive Hierarchical Transform, RAHT): After the attribute information is transformed by RAHT, the signal is converted into the transform domain, which is called transform coefficient.
  • RAHT Region Adaptive Hierarchical Transform
  • attribute information quantization the fineness of quantization is usually determined by a quantization parameter (QP).
  • QP quantization parameter
  • entropy coding is performed after quantizing residual values
  • RAHT entropy coding is performed after quantizing transform coefficients.
  • attribute entropy coding the quantized attribute residual signal or transform coefficient generally uses run length coding (run length coding) and arithmetic coding (arithmetic coding) to achieve final compression. Corresponding coding modes, quantization parameters and other information are also coded by an entropy coder.
  • a data point In point cloud data, a data point can be regarded as a city in a TSP problem, and the distance between two data points is equivalent to the distance between two cities.
  • the distance between each data point in the point cloud data is considered to determine the encoding order of each data point, and according to The determined encoding sequence is encoded in sequence to ensure the encoding accuracy and improve the encoding efficiency of the point cloud data.
  • FIG. 5 shows a flowchart of a point cloud data encoding method provided by an embodiment of the present application.
  • the computer equipment encoding end equipment
  • the computer equipment can perform the following steps:
  • Step 501 Obtain a point cloud data set, where the point cloud data set includes at least two data points.
  • Step 502 according to the coding order of each data point, encode each data point in turn to obtain coded point cloud data corresponding to the point cloud data set; the coding order of each data point is determined based on the distance between each data point .
  • FIG. 6 shows a flowchart of a point cloud data decoding method provided by an embodiment of the present application.
  • the computer equipment decoding end equipment
  • Step 601 Obtain coded point cloud data corresponding to the point cloud data set; the coded point cloud data is obtained by encoding each data point in turn based on the coding order of each data point in the point cloud data set; each data point is obtained by encoding.
  • the coding order of the points is determined based on the distance between the individual data points.
  • Step 602 Obtain reference information; the reference information is used to indicate the starting reference data point of the encoding queue.
  • Step 603 Based on the reference information and the encoded point cloud data, decode each data point in sequence according to the encoding order of each data point.
  • the encoding end device obtains a point cloud data set, and the point cloud data set contains at least two data points; based on the distance between the target data point pairs, the Each data point in the point cloud data set is added to the encoding queue in turn; according to the order of each data point in the encoding queue, each data point is encoded in sequence, and the encoded point cloud data corresponding to the point cloud data set is obtained.
  • the above target data point pair is the data point pair formed by the existing data point in the encoding queue and the data point in the point cloud data set; that is to say, each time a data point is added to the encoding queue, the encoding queue and the target data point will be updated accordingly.
  • the above-mentioned target data point pairs may include part of the point pairs composed of all the data points in the point cloud data set, or may include all the point pairs composed of all the data points in the point cloud data set.
  • the distance between the above data point pairs includes:
  • the decoding end device obtains the encoded point cloud data corresponding to the point cloud data set; and obtains reference information; the reference information is used to indicate the starting reference data point of the encoding queue;
  • the point cloud data is encoded, and each data point is decoded in sequence according to the order of each data point in the encoding queue.
  • the encoding end device performs the processing on each data point according to the distance between each data point in the point cloud data (for example, according to the distance between each data point in the point cloud data and the existing data point in the encoding queue).
  • coding is performed in sequence according to the sorting order, so that the data points in the point cloud data that are close in distance can be coded in sequence, which can ensure the accuracy of coding.
  • the solution shown in this application can significantly reduce coding complexity and improve coding efficiency.
  • the method provided in this application can be applied to the encoding and decoding process of point cloud data.
  • FIG. 7 shows a flowchart of a method for encoding and decoding point cloud data provided by an embodiment of the present application.
  • the computer equipment may include an encoding end device and a decoding end device.
  • the method may include the following steps:
  • Step 701 The encoding end device obtains a point cloud data set, where the point cloud data set includes at least two data points.
  • the solution shown in the embodiment of the present application can be used as an option for point cloud signal prediction, and can be set to act on the overall original point cloud data, or can act on the point cloud data set obtained through octree sub-nodes or other methods (such as a subset of the overall raw point cloud data).
  • Step 702 in response to the encoding queue being empty, the encoding end device determines an initial data point from the point cloud data set.
  • the encoding end device first creates an empty encoding queue, and selects a start data point for encoding from the point cloud data set, where the start data point may be a data point, or Can contain multiple data points.
  • the above-mentioned determination of initial data points from the point cloud dataset may include the following manners:
  • the encoding end device may randomly select a data point in the point cloud data set as the initial data point.
  • the encoding end device may set the above-mentioned point cloud data set, which is within a specified range, and whose normal vector has the largest difference as the above-mentioned initial data point.
  • the encoding end device may determine the data points in the above-mentioned point cloud data set at the position of the center of gravity of the point cloud formed by the point cloud data set in the 3D space as the initial data points.
  • the child node with the smallest number of data points in each child node of the octree is determined as the initial data point.
  • Step 703 the encoding end device adds the initial data point to the encoding queue.
  • the encoding end device may add the determined initial data point to the encoding queue as the foremost data point in the encoding queue.
  • the encoding end device After the encoding end device obtains the encoding queue with the initial data points added, it can start to add each data point in the point cloud data set to the encoding queue in turn based on the distance between the target data point pairs.
  • the queue addition process please refer to the following steps. .
  • Step 704 Based on the distance between the existing data points in the encoding queue and the data points in the point cloud data set, the encoding end device sequentially selects data points that satisfy the specified conditions from the point cloud data set to add to the encoding queue.
  • the encoding end device starts to sequentially add each data point in the point cloud data set to the encoding queue based on the distance between the target data point pairs, and can first obtain each data point pair in the point cloud data set ( The distance between all or part of the point pairs) formed by each data point in the point cloud dataset for subsequent use in the process of adding the encoding queue.
  • the distance between two data points in the data point pair may be characterized by the distance between the positions. That is, the distance between the above two data points is the distance between the coordinate positions of the two data points.
  • the distance between the above two data points can be characterized by the distance between attributes. That is to say, the distance between the above two data points may be the distance between attributes of the two data points (or called attribute difference, which can be intuitively expressed as the difference value of attributes such as color value).
  • the distance between the above two data points can be jointly characterized by the distance between the locations and the distance between the attributes.
  • the distance between the above two data points may be the Euclidean distance between the positions of the two data points, and the average or weighted average of the Euclidean distances between the attributes of the two data points.
  • the specified conditions include:
  • the distance to the last data point in the encoding queue is the smallest
  • the sum of the distances to the data points already in the encoding queue is the smallest.
  • the encoding end device when adding data points to the encoding queue, preferentially adds other data points that are closest to the last data point in the encoding queue to the encoding queue, or preferentially adds data points that are closest to the encoding queue to each data point in the encoding queue.
  • the other data points closest to the point group composed of points are added to the encoding queue to ensure subsequent encoding accuracy.
  • the method further includes:
  • the above-mentioned step of adding an encoding queue is also referred to as the planning of an encoding path, and the encoding path planning scheme may be as follows:
  • each data point is calculated only once during encoding queue construction; otherwise , each data point can be computed multiple times without removing x i+1 from U.
  • the criteria for selecting points include but are not limited to the following two:
  • the distance between xi+1 and xi is the smallest; that is, the distance between xi+1 and xi is the minimum value of the distance between each data point in U and xi .
  • the sum of the distances between x i+1 and all points in V is the smallest; that is, the sum of the distances between x i+1 and all points in V is the sum of the distances between each data point in U and all points in V The minimum value of the sum of the distances.
  • the method before sequentially encoding the data points according to the order of the data points in the encoding queue, the method further includes:
  • the order of the data points in the encoding queue is adjusted based on the distance between adjacent data points in the encoding queue.
  • the encoding device may further optimize and adjust the order of the data points in the encoding queue to improve subsequent encoding accuracy.
  • the order of the data points in the encoding queue is adjusted based on the distance between adjacent data points in the encoding queue, including:
  • the first distance is the distance between the i-th data point and the i+1-th data point in the encoding queue
  • the second distance is the first distance in the encoding queue.
  • the distance between the j data points and the j+1th data point; i, j are integers greater than or equal to 1, and i ⁇ j;
  • the third distance is the distance between the i-th data point and the j+1-th data point
  • the fourth distance is the i+1-th data point and the distance between the jth data point
  • the optimization adjustment method can be as follows: exchange and sort the point pairs in the sorted point set V, for example, the sorted point pairs x i , x i+1 and x j , x j+1 , i ⁇ j, the sum of the distances of two pairs of points is d 1 .
  • x i+1 and x j may be the same data point or different data points.
  • the encoder device may insert new data points (for example, will belong to the point cloud data set or the encoding queue) Data points from other point cloud datasets are inserted into the current point cloud dataset, or, new data points are inserted in the encoding queue).
  • the encoding end device may also delete existing data points in the point cloud data set or encoding queue. For example, when a data point in the current point cloud dataset is added to another point cloud dataset, the data point can be deleted from the current point cloud dataset.
  • the encoder in the queue adding stage in the encoding process, can add additional data points, or delete existing data points, which can improve the degree of freedom and flexibility of the encoding process.
  • Step 705 The encoding end device encodes the data points in sequence according to the order of the data points in the encoding queue, and obtains encoded point cloud data corresponding to the point cloud data set.
  • the respective data points are sequentially encoded according to the order of the respective data points in the encoding queue, including:
  • the termination conditions include:
  • the encoder device in the process of adding the encoding queue, if it is determined that the termination criterion is established, the encoder device can output the encoding queue and perform the next encoding.
  • the above-mentioned termination criteria may include but are not limited to the following methods:
  • the respective data points are sequentially encoded according to the order of the respective data points in the encoding queue, including:
  • the above-mentioned residual signal includes at least one of geometric residual and attribute residual of the corresponding data point.
  • the obtained residual can be encoded by a common entropy encoder, for example, after quantizing the residual, entropy encoding is performed by an entropy encoder to output a geometric bitstream and/or an attribute bitstream corresponding to the encoded point cloud data.
  • Step 706 the decoding end device obtains the encoded point cloud data corresponding to the point cloud data set.
  • the encoded point cloud data obtained after encoding in the above steps is transmitted to the decoding end device.
  • Step 707 The decoding end device obtains reference information; the reference information is used to indicate the starting reference data point of the encoding queue.
  • the obtaining reference information includes:
  • the decoding end device can obtain reference information before decoding.
  • initial location information Including but not limited to the following situations:
  • the current node of the octree is used as the starting position information, and there may be one or more starting position information;
  • Step 708 Based on the reference information and the encoded point cloud data, the decoding end device sequentially decodes the data points according to the order of the data points in the encoding queue.
  • the encoding end device After acquiring the encoded point cloud data, the encoding end device obtains the reference information and the residual signal through analysis, and uses the data point indicated by the reference signal as the initial reference data point corresponding to the above encoding queue, and starts from the initial reference data point.
  • the position information and attribute information of the initial reference data point are used as reference values, and each data point in the encoding queue is decoded and reconstructed in turn. Each time a data point is reconstructed, the previous reconstructed data point is used as a reference, and the corresponding residual signal is combined. to rebuild.
  • the decoding end device can parse the encoded point cloud data to obtain a residual signal ⁇ R
  • r i ⁇ R n , i 1,...,N-1 ⁇ , and the decoding goal is to obtain reconstruction Signal where n is the dimension of the signal (the dimension of the geometric information is 3, and the dimension of the attribute information is assumed to be 3), and N is the number of signals, which can be processed as follows:
  • the reconstructed signal is the sum of the previous signal and the corresponding residual signal in the TSP optimization sorting, namely
  • the reconstructed signal is the sum of the previous signal and the corresponding residual signal, namely
  • the encoding end device sorts each data point according to the distance between each data point in the point cloud data and the existing data point in the encoding queue, and then sorts each data point according to the sorted order.
  • the encoding is performed in sequence, so that the data points in the point cloud data that are close in distance can be encoded in sequence.
  • the decoding end device only needs to combine the reference information and the residual signal of each data point to reconstruct the point cloud data, which can ensure The accuracy of encoding and decoding, at the same time, can significantly reduce the complexity of encoding and decoding, and improve the efficiency of encoding and decoding.
  • a point cloud information prediction method is provided by sorting the data points in the point cloud and then performing residual coding in sequence, which can be used for geometric information.
  • the prediction of attribute information, the above coding scheme can be implemented independently of the traditional octree-based coding mode.
  • FIG. 8 shows a frame diagram of a point cloud data encoding process provided by an embodiment of the present application.
  • an exemplary encoding process involved in the foregoing embodiments of the present application may include the following main steps:
  • the encoder can perform preprocessing (including coordinate system transformation and voxelization) on the location information of the data points in the point cloud dataset.
  • the encoder may further preprocess the attribute information of the data points in the point cloud dataset, for example, perform color conversion on the data points in the point cloud dataset.
  • S82 Perform distance metric calculation on the data points in the preprocessed point cloud data set to obtain distance information between each data point.
  • the distance information between the above-mentioned respective data points may be a position distance, an attribute distance, or a joint distance of a position and an attribute.
  • the encoder may start from one or more initial data points according to the distance information between each data point, and sequentially collect the data in the point cloud data set that are closest to some or all of the data points in the encoding queue. Points are added to the end of the encoding queue until the termination condition is met.
  • the encoder can adjust the order of the data points in the encoding queue based on the distance between each group of adjacent point pairs in the encoding queue, so as to further improve the subsequent performance. encoding effect.
  • S85 Perform residual coding in sequence according to the arrangement order of each data point in the coding queue to obtain a residual signal of each data point.
  • performing residual coding on each data point in the coding queue in sequence may include performing residual coding on the position information and attribute information of each data point respectively, wherein the residual coding on attribute information may include: based on the position information
  • the corresponding residual signal/quantized residual information is subjected to position reconstruction and attribute re-coloring, and the result of position reconstruction and attribute re-coloring is subjected to residual encoding of attribute information, for example, through predictive transform coding, lifting transform coding or RAHT
  • the transform coding method performs residual coding on the attribute information to obtain a residual signal of the attribute information.
  • S86 Perform quantization and entropy encoding on the residual signal, and output the encoded point cloud data.
  • the encoded point cloud data After the encoder performs quantization and entropy encoding on the residual encoding of the position information and the residual encoding of the attribute information of each data point, the encoded point cloud data can be output.
  • the decoder only needs to obtain the encoded point cloud data, parse and obtain the reference signal, and obtain the first data point in the encoding queue. Based on the position residual and attribute residual of the first data point, according to the above S85 and S86 The inverse process of reconstructing each data point in the encoding queue in turn.
  • FIG. 9 shows a block diagram of an apparatus for encoding point cloud data provided by an embodiment of the present application.
  • the apparatus has the function of implementing the above-mentioned method example.
  • the apparatus may include:
  • a point cloud acquisition module 901 configured to acquire a point cloud data set, the point cloud data set includes at least two data points;
  • an encoding module 902 configured to encode the respective data points in sequence according to the encoding order of the respective data points to obtain encoded point cloud data corresponding to the point cloud data set;
  • the coding order of the respective data points is determined based on the distances between the respective data points.
  • the apparatus further includes:
  • the queue adding module is used for, before the encoding module 902 encodes the respective data points in sequence according to the encoding order of the respective data points, and obtains the encoded point cloud data corresponding to the point cloud data set, based on The distance between the target data point pairs, each data point in the point cloud data set is added to the encoding queue in turn; the target data point pair is the existing data point in the encoding queue and the point cloud data set.
  • the encoding module 902 is configured to encode the data points in sequence according to the order of the data points in the encoding queue to obtain encoded point cloud data corresponding to the point cloud data set.
  • the distance between the data point pairs includes:
  • the queue adding module is used for,
  • the data points satisfying the specified conditions are sequentially selected from the point cloud data set and added to the encoding queue.
  • the specified conditions include:
  • the distance to the last data point in the encoding queue is the smallest
  • the sum of the distances to the data points already in the encoding queue is the smallest.
  • the apparatus further includes:
  • the initial data point determination module is used to sequentially add each data point in the point cloud data set to the encoding queue based on the distance between the target data point pairs in the queue adding module, in response to the encoding queue being empty, from determining initial data points in the point cloud data set;
  • an initial data point adding module configured to add the initial data point to the encoding queue.
  • the initial data point determination module is used to:
  • the initial data points are determined from the point cloud dataset in response to a data point division manner of the point cloud dataset.
  • the apparatus further includes:
  • the queue adjustment module is configured to, before the encoding module 902 sequentially encodes the respective data points according to the order of the respective data points in the encoding queue, based on the difference between adjacent data points in the encoding queue. distance to adjust the order of data points in the encoding queue.
  • the queue adjustment module is configured to:
  • the first distance is the distance between the i-th data point and the i+1-th data point in the encoding queue
  • the second distance is the encoding
  • the distance between the jth data point and the j+1th data point in the queue; i, j are integers greater than or equal to 1, and i ⁇ j;
  • the third distance is the distance between the i-th data point and the j+1-th data point
  • the fourth distance is the i-th data point the distance between 1 data point and the jth data point
  • the encoding module 902 is configured to, in response to satisfying the sorting termination condition, perform a sequence of encoding the respective data points sequentially according to the order of the respective data points in the encoding queue. step;
  • the termination conditions include:
  • the sum of the distances between the data points in the encoded queue reaches a specified threshold.
  • the encoding end device sorts each data point according to the distance between each data point in the point cloud data, and then performs encoding in sequence according to the sorting order, so as to realize the The data points that are close to each other in the point cloud data are encoded in sequence.
  • the decoding end device only needs to combine the reference information and the residual signal of each data point to reconstruct the point cloud data, which can ensure the accuracy of encoding and decoding. At the same time, it can Significantly reduces the complexity of encoding and decoding, and improves encoding and decoding efficiency.
  • FIG. 10 shows a block diagram of an apparatus for decoding point cloud data provided by an embodiment of the present application.
  • the apparatus has the function of implementing the above-mentioned method example.
  • the apparatus may include:
  • the data acquisition module 1001 is used to acquire the encoded point cloud data corresponding to the point cloud data set; the encoded point cloud data is the encoding order of the encoding device based on each data point in the point cloud data set, and the data points are sequentially obtained by encoding; the encoding order of the respective data points is determined based on the distance between the respective data points;
  • a reference information obtaining module 1002 configured to obtain reference information; the reference information is used to indicate a starting reference data point of the encoding queue;
  • the decoding module 1003 is configured to sequentially decode the respective data points according to the encoding order of the respective data points based on the reference information and the encoded point cloud data.
  • the encoding device sequentially adds the respective data points to the encoding queue based on the distance between the target data point pairs, and executes the encoding process according to the respective data points.
  • the order in the encoding queue is obtained by encoding the data points in sequence;
  • the target data point pair is formed by the existing data points in the encoding queue and the data points in the point cloud data set data point pair;
  • the decoding module 1003 is configured to sequentially decode the data points according to the order of the data points in the encoding queue based on the reference information and the encoded point cloud data.
  • the reference information obtaining module 1002 is configured to:
  • the reference information is obtained by parsing the hierarchical information of the data points in the point cloud dataset.
  • the encoding end device sorts each data point according to the distance between each data point in the point cloud data, and then performs encoding in sequence according to the sorting order, so as to realize the The data points that are close to each other in the point cloud data are encoded in sequence.
  • the decoding end device only needs to combine the reference information and the residual signal of each data point to reconstruct the point cloud data, which can ensure the accuracy of encoding and decoding. At the same time, it can Significantly reduces the complexity of encoding and decoding, and improves encoding and decoding efficiency.
  • FIG. 11 shows a structural block diagram of a computer device provided by an embodiment of the present application.
  • the computer device may be the encoding end device described above, or the decoding end device described above.
  • the computer device 110 may include a processor 111 , a memory 112 , a communication interface 113 , an encoder/decoder 114 and a bus 115 .
  • the processor 111 includes one or more processing cores, and the processor 111 executes various functional applications and information processing by running software programs and modules.
  • the memory 112 can be used to store a computer program, and the processor 111 is used to execute the computer program to implement all or part of the steps in the method involved in the embodiment shown in FIG. 5 or FIG. 6 .
  • the communication interface 113 can be used to communicate with other devices, such as transceiving point cloud data.
  • the encoder/decoder 114 may be used to implement encoding and decoding functions, such as encoding and decoding point cloud data.
  • the memory 112 is connected to the processor 111 through a bus 115 .
  • the memory 112 can be implemented by any type of volatile or non-volatile storage device or a combination thereof.
  • the volatile or non-volatile storage device includes but is not limited to: magnetic disk or optical disk, EEPROM (Electrically Erasable Programmable Read) -Only Memory, Electrically Erasable Programmable Read-Only Memory), EPROM (Erasable Programmable Read-Only Memory, Erasable Programmable Read-Only Memory), SRAM (Static Random-Access Memory, Static Access Memory), ROM (Read-Only Memory, read-only memory), magnetic memory, flash memory, PROM (Programmable Read-Only Memory, programmable read-only memory).
  • FIG. 11 does not constitute a limitation on the computer device 110, and may include more or less components than those shown, or combine some components, or adopt different component arrangements.
  • a computer-readable storage medium is also provided, and at least one computer program is stored in the computer-readable storage medium, and when the at least one computer program is executed by a processor, the above-mentioned FIG. 5 , All or part of the steps in the method involved in the embodiment shown in FIG. 6 , FIG. 7 or FIG. 8 .
  • a computer program product or computer program comprising computer instructions stored in a computer readable storage medium.
  • the processor of the computer device reads the computer instructions from the computer-readable storage medium, and the processor executes the computer instructions, so that the computer device executes the methods involved in the embodiments shown in FIG. 5 , FIG. 6 , FIG. 7 or FIG. 8 . all or part of the steps.
  • references herein to "a plurality” means two or more.
  • "And/or" which describes the association relationship of the associated objects, means that there can be three kinds of relationships, for example, A and/or B, which can mean that A exists alone, A and B exist at the same time, and B exists alone.
  • the character “/” generally indicates that the associated objects are an "or" relationship.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Signal Processing (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Software Systems (AREA)
  • Artificial Intelligence (AREA)
  • Computing Systems (AREA)
  • Databases & Information Systems (AREA)
  • Evolutionary Computation (AREA)
  • General Health & Medical Sciences (AREA)
  • Medical Informatics (AREA)
  • Health & Medical Sciences (AREA)
  • Computer Graphics (AREA)
  • Geometry (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)

Abstract

一种点云数据编码方法、解码方法、设备、介质及程序产品，涉及点云应用技术领域。所述方法包括：获取点云数据集，所述点云数据集中包含至少两个数据点(501)；按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据(502)；其中，所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的；上述方案能够显著的降低点云数据的编码复杂度，提高点云数据的编码效率。

Description

点云数据编码方法、解码方法、设备、介质及程序产品
本申请要求于2020年12月07日提交的、申请号为202011440832.7、发明名称为“点云数据编码方法、解码方法、装置、设备及存储介质”的中国专利申请的优先权，其全部内容通过引用结合在本申请中。
技术领域
本申请实施例涉及点云应用技术领域，特别涉及一种点云数据编码方法、解码方法、设备、介质及程序产品。
背景技术
随着点云的获取方式的不断变革，点云的获取精度也越来越高，相应的获取成本也在逐渐降低，因此，点云在各种场景中的应用前景也越来越广阔。
在相关技术中，主要基于八叉树对点云数据进行编码。对三维(3-Dimension，3D)空间中的点云数据，八叉树划分方式是逐层次地对预先设定的包围盒进行均匀划分，每个节点都具有八个子节点，并通过对八叉树各个子节点的占用与否采用‘1’和‘0’指示。在基于八叉树进行编码时，将点云数据的3D坐标信息通过查询莫顿顺序表，转换成对应的莫顿码，并根据每一位莫顿码的排序，获得每层八叉树的对应点。
然而，对于稀疏型的点云数据来说，其3D位置分布较为分散，即八叉树中的大部分节点为空，导致基于八叉树的编码复杂度较高，编码效率较低。
发明内容
本申请实施例提供了一种点云数据编码方法、解码方法、设备、介质及程序产品，能够降低对点云数据进行编码的复杂度，提高编码效率。所述技术方案如下：
根据本申请实施例的一个方面，提供了一种点云数据编码方法，由计算机设备执行，所述方法包括：
获取点云数据集，所述点云数据集中包含至少两个数据点；
按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据；
其中，所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的。
根据本申请实施例的一个方面，提供了一种点云数据解码方法，由计算机设备执行，所述方法包括：
获取与点云数据集对应的已编码点云数据；所述已编码点云数据是编码设备基于点云数据集中的各个数据点的编码次序，对所述各个数据点依次进行编码得到的；所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的；
获取参考信息；所述参考信息用于指示所述编码队列中的起始参考数据点；
基于所述参考信息以及所述已编码点云数据，按照所述各个数据点的编码次序，对所述各个数据点依次进行解码。
根据本申请实施例的一个方面，提供了一种点云数据编码装置，所述装置包括：
点云获取模块，用于获取点云数据集，所述点云数据集中包含至少两个数据点；
编码模块，用于按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据；
其中，所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的。
在一种可能的实现方式中，所述装置还包括：
队列添加模块，用于在所述编码模块按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据之前，基于目标数据点对之间的距离，将所述点云数据集中的各个数据点依次添加至编码队列；所述目标数据点对是所述编码队列中已有的数据点与所述点云数据集中的数据点构成的数据点对；
所述编码模块，用于按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据。
在一种可能的实现方式中，所述数据点对之间的距离包括：
所述数据点对中的两个数据点的位置信息之间的距离；
或者，所述数据点对中的两个数据点的属性信息之间的距离；
或者，通过所述数据点对中的两个数据点的位置信息之间的距离，以及，所述两个数据点的属性信息之间的距离得到的联合距离。
在一种可能的实现方式中，所述编码模块，用于对于所述编码队列中的任意相邻的第一数据点和第二数据点，获取所述第二数据点与所述第一数据点之间的残差信号。
在一种可能的实现方式中，所述队列添加模块，用于，
基于所述编码队列中已有的数据点与所述点云数据集中的数据点之间的距离，从所述点云数据集中依次选择满足指定条件的数据点添加至所述编码队列。
在一种可能的实现方式中，所述指定条件包括：
与所述编码队列中的最后一个数据点之间的距离最小；
或者，
与所述编码队列中已有的数据点之间的距离之和最小。
在一种可能的实现方式中，所述装置还包括：
初始数据点确定模块，用于在队列添加模块基于目标数据点对之间的距离，将所述点云数据集中的各个数据点依次添加至编码队列之前，响应于所述编码队列为空，从所述点云数据集中确定初始数据点；
初始数据点添加模块，用于将所述初始数据点添加至所述编码队列。
在一种可能的实现方式中，所述初始数据点确定模块，用于，
从所述点云数据集中随机选择一个数据点，作为所述初始数据点；
基于所述点云数据集中包含的数据点的几何特征，从所述点云数据集中确定所述初始数据点；
基于所述点云数据集中包含的数据点的统计特征，从所述点云数据集中确定所述初始数据点；
或者，响应于所述点云数据集的数据点划分方式，从所述点云数据集中确定所述初始数据点。
在一种可能的实现方式中，所述装置还包括：
队列调整模块，用于在编码模块按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码之前，基于所述编码队列中的相邻数据点之间的距离，对所述编码队列中的数据点的顺序进行调整。
在一种可能的实现方式中，所述队列调整模块，用于，
获取第一距离与第二距离之和；所述第一距离是所述编码队列中的第i个数据点和第i+1个数据点之间的距离；所述第二距离是所述编码队列中的第j个数据点和第j+1个数据点之间的距离；i、j为大于或者等于1的整数，且i≠j；
获取第三距离与第四距离之和；所述第三距离是所述第i个数据点和所述第j+1个数据点之间的距离，所述第四距离是所述第i+1个数据点和所述第j个数据点之间的距离；
响应于所述第一距离与所述第二距离之和，大于所述第三距离与所述第四距离之和，交 换所述第i+1个数据点与所述第j+1个数据点在所述编码队列中的位置。
在一种可能的实现方式中，所述编码模块，用于响应于满足排序终止条件，执行按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码的步骤；
所述终止条件包括：
所述点云数据集中不存在未被添加至所述编码队列的数据点；
或者，
所述编码队列中的数据点之间的距离之和达到指定阈值。
根据本申请实施例的一个方面，提供了一种点云数据解码装置，所述装置包括：
数据获取模块，用于获取与点云数据集对应的已编码点云数据；所述已编码点云数据是编码设备基于点云数据集中的各个数据点的编码次序，对所述各个数据点依次进行编码得到的；所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的；
参考信息获取模块，用于获取参考信息；所述参考信息用于指示所述编码队列的起始参考数据点；
解码模块，用于基于所述参考信息以及所述已编码点云数据，按照所述各个数据点的编码次序，对所述各个数据点依次进行解码。
在一种可能的实现方式中，所述已编码点云数据是所述编码设备基于目标数据点对之间的距离，将所述各个数据点依次添加至编码队列，并按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码得到的；所述目标数据点对是所述编码队列中已有的数据点与所述点云数据集中的数据点构成的数据点对；
所述解码模块，用于基于所述参考信息以及所述已编码点云数据，按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行解码。
在一种可能的实现方式中，所述参考信息获取模块，用于，
获取默认的所述参考信息；
解析所述已编码点云数据的码流头信息，获得所述参考信息；
基于所述点云数据集的数据点划分方式获取所述参考信息；
解析所述点云数据集中的数据点的层级信息，获得所述参考信息。
根据本申请实施例的一个方面，提供了一种计算机设备，所述计算机设备包括处理器和存储器，所述存储器中存储有至少一条计算机程序，所述至少一条计算机程序由所述处理器加载并执行以实现上述点云数据编码方法或者点云数据解码方法。
根据本申请实施例的一个方面，提供了一种计算机可读存储介质，所述计算机可读存储介质中存储有至少一条计算机程序，所述至少一条计算机程序由处理器加载并执行以实现上述点云数据编码方法或者点云数据解码方法。
还一方面，本申请实施例提供了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存储介质中。计算机设备的处理器从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该计算机设备执行上述点云数据编码方法或者点云数据解码方法。
本申请实施例提供的技术方案可以包括如下有益效果：
编码端设备按照点云数据中各个数据点之间的距离，对各个数据点进行排序之后，按照排序的顺序依次进行编码，从而能够实现对点云数据中距离靠近的数据点进行依次编码，能够保证编码的准确性的同时，显著的降低编码复杂度，从而提高编码效率。
附图说明
图1是本申请示例性示出的一种点云应用框架图；
图2是本申请一个实施例提供的通信系统的简化框图；
图3是本申请示例性示出的点云编码器和点云解码器在流式传输环境中的放置方式的示 意图；
图4是本申请一个实施例提供的编码框架示意图；
图5是本申请一个实施例提供的点云数据编码方法的流程图；
图6是本申请一个实施例提供的点云数据解码方法的流程图；
图7是本申请一个实施例提供的点云数据编码及解码方法的流程图；
图8是本申请一个实施例提供的点云数据编码流程框架图；
图9是本申请一个实施例提供的点云数据编码装置的框图；
图10是本申请一个实施例提供的点云数据解码装置的框图；
图11是本申请一个实施例提供的计算机设备的结构框图。
具体实施方式
为使本申请的目的、技术方案和优点更加清楚，下面将结合附图对本申请实施方式作进一步地详细描述。
在对本申请实施例进行介绍说明之前，首先对本申请实施例涉及的一些名词概念进行介绍。
一、点云
点云是空间中一组无规则分布的、表达三维物体或场景的空间结构及表面属性的离散点集。点云中的每个点至少具有三维位置信息，根据应用场景的不同，还可能具有色彩、材质或其他信息。通常，点云中的每个点都具有相同数量的附加属性。
其中，点云数据中的每个点可以称为一个数据点。
点云可以灵活方便地表达三维物体或场景的空间结构及表面属性，因而应用广泛，其主要应用场景可以归为两大类别：
a)机器感知点云，例如自主导航系统、实时巡检系统、地理信息系统、视觉分拣机器人、抢险救灾机器人等等；
b)人眼感知点云，例如数字文化遗产、自由视点广播、三维沉浸通信、三维沉浸交互等点云应用场景。
点云的获取途径包括且不限于计算机生成、3D激光扫描、3D摄影测量等几种。其中，计算机可以生成虚拟三维物体及场景的点云。3D扫描可以获得静态现实世界三维物体或场景的点云，每秒可以获取百万级点云。3D摄像可以获得动态现实世界三维物体或场景的点云，每秒可以获取千万级点云。此外，在医学领域，由磁共振成像(Magnetic Resonance Imaging，MRI)、电子计算机断层扫描(Computed Tomography，CT)、电磁定位信息，可以获得生物组织器官的点云。这些技术降低了点云数据获取成本和时间周期，提高了数据的精度。点云数据获取方式的变革，使大量点云数据的获取成为可能。伴随着大规模的点云数据不断积累，点云数据的高效存储、传输、发布、共享和标准化，成为点云应用的关键。
点云数据从数据的获取方式划分，可以分为密集型点云和稀疏型点云；从数据的时序类型划分，可以分为静态点云和动态点云。
请参考图1，其示出了本申请实施例涉及的一种点云应用框架图。以G-PCC数据为例，在图1中，在发送端，一个真实世界的虚拟场景(A)是由一组摄像机或一个带有多个镜头和传感器的摄像设备11捕捉的。采集结果为源点云数据(B)。一个或多个点云帧被G-PCC编码器12编码为编码后的G-PCC比特流(E)，包括编码的几何比特流和属性比特流。然后，文件封装器13根据特定媒体容器文件格式，将一个或多个编码比特流(E)封装成用于文件回放的媒体文件(F)，或封装成用于流式传输的初始化段和媒体段的序列(Fs)。
文件封装器13还将元数据包含到文件或段中，(Fs)通过传递机制14传递给用户端；由用户侧的文件封装器15对(Fs)进行解封装，得到解封装后的一个或多个编码比特流(E’)，并通过G-PCC解码器16对(E’)解码得到解码后的一个或多个点云帧(D’)，并由呈现组件 17在显示组件18上呈现一个或多个点云帧(D’)对应的虚拟场景(A’)。
二、旅行商问题(Traveling Salesman Problem，TSP)
TSP问题是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个非确定性多项式(Non-deterministic Polynomial，NP)完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。
例如，用无向加权图来对TSP建模，则城市是图的顶点，道路是图的边，道路的距离就是该边的长度。它是起点和终点都在一个特定顶点，访问每个顶点恰好一次的最小化问题。通常，该模型是一个完全图(即每对顶点由一条边连接)。如果两个城市之间不存在路径，则增加一条非常长的边就可以完成图，而不影响计算最优回路。
在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图。这种对称性将解的数量减少了一半。在非对称TSP问题中，可能不是双向的路径都存在，或是来回的距离不同，形成了有向图。交通事故、单行道和出发与到达某些城市机票价格不同等都是打破这种对称性的例子。
如图2所示，其示出了本申请一个实施例提供的通信系统的简化框图。通信系统200包括多个设备，所述设备可通过例如网络250彼此通信。举例来说，通信系统200包括通过网络250互连的第一设备210和第二设备220。在图2的实施例中，第一设备210和第二设备220执行单向数据传输。举例来说，第一设备210可对点云数据例如由第一设备210采集的点云帧流进行编码以通过网络250传输到第二设备220。已编码的点云数据以一个或多个已编码点云比特流形式传输。第二设备220可从网络250接收已编码点云数据，对已编码点云数据进行解码以恢复点云数据，并根据恢复的点云数据呈现点云。单向数据传输在媒体服务等应用中是较常见的。
在另一实施例中，通信系统200包括执行已编码点云数据的双向传输的第三设备230和第四设备240。对于双向数据传输，第三设备230和第四设备240中的每个设备可对点云数据进行编码，以通过网络250传输到第三设备230和第四设备240中的另一设备。第三设备230和第四设备240中的每个设备还可接收由第三设备230和第四设备240中的另一设备传输的已编码点云数据，且可对所述已编码点云数据进行解码以恢复点云数据，且可根据恢复的点云数据在可访问的显示装置上显示点云。
在图2的实施例中，第一设备210、第二设备220、第三设备230和第四设备240可为服务器、个人计算机和智能电话等计算机设备，但本申请公开的原理可不限于此。本申请实施例适用于PC(Personal Computer，个人计算机)、手机、平板电脑、虚拟现实/增强现实设备、媒体播放器和/或专用视频会议设备。网络250表示在第一设备210、第二设备220、第三设备230和第四设备240之间传送已编码点云数据的任何数目的网络，包括例如有线连线的和/或无线通信网络。通信网络250可在电路交换和/或分组交换信道中交换数据。该网络可包括电信网络、局域网、广域网和/或互联网。出于本申请的目的，除非在下文中有所解释，否则网络250的架构和拓扑对于本申请公开的操作来说可能是无关紧要的。
作为实施例，图3示出点云编码器和点云解码器在流式传输环境中的放置方式。本申请所公开主题可同等地适用于其它支持点云的应用，包括例如虚拟3D会议、数字TV(电视)、 在包括CD(Compact Disc，光盘)、DVD(Digital Versatile Disc，数字通用光盘)、存储棒等的数字介质上存储压缩点云等等。
流式传输系统可包括采集子系统313，所述采集子系统可包括三维相机等点云源301，所述视频源创建未压缩的点云数据流302。相较于已编码的点云数据304(或已编码的点云比特流)，点云数据流302被描绘为粗线以强调高数据量的点云数据流，点云数据流302可由电子装置320处理，所述电子装置320包括耦接到点云源301的点云编码器303。点云编码器303可包括硬件、软件或软硬件组合以实现或实施如下文更详细地描述的所公开主题的各方面。相较于点云数据流302，已编码的点云数据304(或已编码的点云比特流304)被描绘为细线以强调较低数据量的已编码的点云数据304(或已编码的点云比特流304)，其可存储在流式传输服务器305上以供将来使用。一个或多个流式传输客户端子系统，例如图3中的客户端子系统306和客户端子系统308，可访问流式传输服务器305以检索已编码的点云数据304的副本307和副本309。客户端子系统306可包括例如电子装置330中的点云解码器310。点云解码器310对已编码的点云数据的传入副本307进行解码，且产生可在显示器312(例如显示屏)或另一呈现装置(未描绘)上呈现的输出点云数据流311。在一些流式传输系统中，可根据某些点云编码/压缩标准对已编码的点云数据304、点云数据307和点云数据309(例如点云比特流)进行编码。
应注意，电子装置320和电子装置330可包括其它组件(未示出)。举例来说，电子装置320可包括点云解码器(未示出)，且电子装置330还可包括点云编码器(未示出)。其中，点云解码器用于对接收到的已编码点云数据进行解码；点云编码器用于对点云数据进行编码。
需要说明的一点是，本申请实施例提供的技术方案可以应用于信源编码标准(Audio Video coding Standard，AVS)，如AVS3或者下一代视频编解码标准等支持点云编码的标准中，本申请实施例对此不作限定。
点云的编码方式可以分为基于传统视频编码的点云压缩(Video-based Point Cloud Compression，V-PCC)，以及基于几何模型的点云压缩(Geometry-based Point Cloud Compression，G-PCC)。
目前的点云编码技术，针对不同的点云数据类型，可以分为基于几何结构的点云编码以及基于投影的点云编码。以国际视音频编解码标准(Moving Picture Expert Group，MPEG)中的基于几何结构的点云编码G-PCC，以及中国国家数字视音频编解码标准中点云编码标准(AudioVideoCodingStandard-PCC，AVS-PCC)为例进行介绍。
G-PCC及AVS-PCC均针对静态的稀疏型点云，其编码框架大致相同，请参考图4，其是本申请一个实施例提供的编码框架示意图。如图4所示，点云编码分为几何结构编码以及属性信息编码。其中，对于几何结构编码，主要操作和处理如下：
S41，预处理(Pre-processing)：包括坐标变换(Transformcoordinates)和体素化(Voxelize)。
即通过缩放和平移的操作，将3D空间中的点云数据转换成整数形式，并将其最小几何位置移至坐标原点处。
S42，几何编码(Geometry encoding)：几何编码可以包含多种模式，可在不同条件下使用。比如，上述几何编码可以分为基于八叉树的几何编码(Octree)和基于三角表示的几何编码(Trisoup)等等。
S43，几何量化(Geometryquantization)：量化的精细程度通常由量化参数(Quantization Parameter，QP)来决定，QP取值较大，表示更大取值范围的系数将被量化为同一个输出，因此通常会带来更大的失真，及较低的码率；相反，QP取值较小，表示较小取值范围的系数将被量化为同一个输出，因此通常会带来较小的失真，同时对应较高的码率。在点云编码中，量化是直接对点的坐标信息进行的。
S44，几何熵编码(Geometryentropyencoding)：以基于八叉树的几何编码为例，针对八 叉树的占用码信息，进行统计压缩编码，最后输出二值化(0或者1)的压缩码流。统计编码是一种无损编码方式，可以有效的降低表达同样的信号所需要的码率。常用的统计编码方式是基于上下文的二值化算术编码(Content Adaptive Binary Arithmetic Coding，CABAC)。
对于属性信息编码，主要操作和处理如下：
S45，属性重上色(Recoloring)；有损编码情况下，在几何信息编码后，需编码端解码并重建几何信息，即恢复3D点云的各点坐标信息。在原始点云中寻找对应一个或多个邻近点的属性信息，作为该重建点的属性信息。
S46，属性变换编码(Transform)：属性变换编码中可以包含三种模式，可在不同条件下使用。
预测变换编码(Predicting Transform)：根据距离选择子点集，将点云划分成多个不同的层级(Level of Detail，LoD)，实现由粗糙到精细化的点云表示。相邻层之间可以实现自下而上的预测，即由粗糙层中的邻近点预测精细层中引入的点的属性信息，获得对应的残差信号。其中，最底层的点作为参考信息进行编码。
提升变换编码(Lifting Transform)：在LoD相邻层预测的基础上，引入邻域点的权重更新策略，最终获得各点的预测属性值，获得对应的残差信号。
分层区域自适应变换编码(Region Adaptive Hierarchical Transform，RAHT)：属性信息经过RAHT变换，将信号转换到变换域中，称之为变换系数。
S47，属性信息量化(Attribute quantization)：量化的精细程度通常由量化参数(QP)来决定。在预测变换编码及提升变换编码中，是对残差值进行量化后进行熵编码；在RAHT中，是对变换系数进行量化后进行熵编码。
S48，属性熵编码(Attributeentropy coding)：量化后的属性残差信号或变换系数一般使用行程编码(run length coding)及算数编码(arithmetic coding)实现最终的压缩。相应的编码模式，量化参数等信息也同样采用熵编码器进行编码。
在点云数据中，一个数据点可以视为一个TSP问题中的一个城市，两个数据点之间的距离相当于两个城市之间的距离。本申请后续所示的方案，参考TSP问题的解决思路，在对点云数据进行编码时，考虑点云数据中的各个数据点两两之间的距离，确定各个数据点的编码顺序，并按照确定的编码顺序依次进行编码，以保证编码准确性，并提高对点云数据的编码效率。
请参考图5，其示出了本申请一个实施例提供的点云数据编码方法的流程图。如图5所示，在编码阶段，计算机设备(编码端设备)可以执行以下步骤：
步骤501，获取点云数据集，点云数据集中包含至少两个数据点。
步骤502，按照各个数据点的编码次序，对各个数据点依次进行编码，获得与点云数据集对应的已编码点云数据；各个数据点的编码次序是基于各个数据点之间的距离确定的。
相应的，请参考图6，其示出了本申请一个实施例提供的点云数据解码方法的流程图。如图6所示，在解码阶段，计算机设备(解码端设备)执行以下步骤：
步骤601，获取与点云数据集对应的已编码点云数据；已编码点云数据是编码设备基于点云数据集中的各个数据点的编码次序，对各个数据点依次进行编码得到的；各个数据点的编码次序是基于各个数据点之间的距离确定的。
步骤602，获取参考信息；参考信息用于指示编码队列的起始参考数据点。
步骤603，基于参考信息以及已编码点云数据，按照各个数据点的编码次序，对各个数据点依次进行解码。
本申请各个实施例所示的方案，提出了一种基于数据点之间的顺序执行的点云数据编码和解码方案。
在一种可能的实现方式中，在点云数据编码方案中，编码端设备获取点云数据集，该点 云数据集中包含至少两个数据点；基于目标数据点对之间的距离，将该点云数据集中的各个数据点依次添加至编码队列；按照该各个数据点在该编码队列中的次序，对该各个数据点依次进行编码，获得该点云数据集对应的已编码点云数据。
上述目标数据点对是编码队列中已有的数据点与点云数据集中的数据点构成的数据点对；也就是说，每次向编码队列中添加一个数据点之后，编码队列以及目标数据点对会相应的更新。
其中，上述目标数据点对，可以包括点云数据集中的全部数据点两两组成的点对中的部分点对，也可以包括点云数据集中的全部数据点两两组成的点对中的全部点对。
在一种可能的实现方式中，上述数据点对之间的距离包括：
数据点对中的两个数据点的位置信息之间的距离；
或者，数据点对中的两个数据点的属性信息之间的距离；
或者，通过数据点对中的两个数据点的位置信息之间的距离，以及，两个数据点的属性信息之间的距离得到的联合距离。
相应的，在点云解码方案中，解码端设备获取点云数据集对应的已编码点云数据；并获取参考信息；参考信息用于指示编码队列的起始参考数据点；基于参考信息以及已编码点云数据，按照各个数据点在编码队列中的次序，对各个数据点依次进行解码。
通过上述方案，编码端设备按照点云数据中各个数据点之间的距离(比如，按照点云数据中各个数据点与编码队列中已有的数据点之间的距离)，对各个数据点进行排序之后，按照排序的顺序依次进行编码，从而能够实现对点云数据中距离靠近的数据点进行依次编码，能够保证编码的准确性，同时，相比于相关技术中基于八叉树的编码方式，本申请所示的方案能够显著的降低编码复杂度，提高编码效率。
本申请所提供的方法可应用于点云数据的编解码环节。
请参考图7，其示出了本申请一个实施例提供的点云数据编码及解码方法的流程图。为了便于说明，仅以各步骤执行主体为计算机设备进行介绍说明。该计算机设备可以包括编码端设备和解码端设备。该方法可以包括如下几个步骤：
步骤701，编码端设备获取点云数据集，该点云数据集中包含至少两个数据点。
本申请实施例所示的方案，可以作为点云信号预测的一种选项，可设置为作用于整体原始点云数据，也可以作用于通过八叉树子节点或者其他方式获得的点云数据集(比如整体原始点云数据的一个子集)。
步骤702，响应于编码队列为空，编码端设备从该点云数据集中确定初始数据点。
在本申请实施例中，编码端设备在编码过程中，首先创建一个空的编码队列，并从点云数据集中选择编码的起始数据点，其中该起始数据点可以是一个数据点，也可以包含多个数据点。
在一种可能的实现方式中，上述从该点云数据集中确定初始数据点，可以包括以下方式：
1)从该点云数据集中随机选择一个数据点，作为该初始数据点。
在本申请实施例中，编码端设备可以随机选择点云数据集中的一个数据点作为初始数据点。
2)基于该点云数据集中包含的数据点的几何特征，从该点云数据集中确定该初始数据点。
例如，编码端设备可以将上述点云数据集中，处于指定范围内，且法向量差异最大的数据点作为上述初始数据点。
3)基于该点云数据集中包含的数据点的统计特征，从该点云数据集中确定该初始数据点。
例如，编码端设备可以将上述点云数据集中，在3D空间中位于点云数据集构成的点云的重心位置的数据点，确定为初始数据点。
4)响应于该点云数据集的数据点划分方式，从该点云数据集中确定该初始数据点。
例如，响应于该点云数据集中的数据点按照八叉树进行划分，将该八叉树的父节点确定为该初始数据点；
再例如，响应于该点云数据集中的数据点按照八叉树进行划分，将该八叉树的各个子节点中，包含的数据点的数量最小的子节点，确定为该初始数据点。
步骤703，编码端设备将该初始数据点添加至该编码队列。
在本申请实施例中，编码端设备可以将确定的初始数据点作为编码队列中最前列的数据点，添加至编码队列中。
编码端设备获得添加了初始数据点的编码队列之后，即可以开始基于目标数据点对之间的距离，将该点云数据集中的各个数据点依次添加至编码队列，队列添加过程可以参考后续步骤。
步骤704，编码端设备基于该编码队列中已有的数据点与该点云数据集中的数据点之间的距离，从该点云数据集中依次选择满足指定条件的数据点添加至该编码队列。
在本申请实施例中，编码端设备开始基于目标数据点对之间的距离，将该点云数据集中的各个数据点依次添加至编码队列之前，可以先获取点云数据集中各个数据点对(点云数据集中各个数据点两两构成的全部或者部分点对)之间的距离，以便后续在编码队列添加过程中使用。
在本申请实施例中，数据点对中的两个数据点之间的距离可以通过位置之间的距离来表征。也就是说，上述两个数据点之间的距离是两个数据点的坐标位置之间的距离。
或者，上述两个数据点之间的距离可以通过属性之间的距离来表征。也就是说，上述两个数据点之间的距离可以是两个数据点的属性之间的距离(或者称为属性差异，直观的可以表现为色值等属性的差值)。
或者，上述两个数据点之间的距离可以通过位置之间的距离和属性之间的距离来联合表征。例如，上述两个数据点之间的距离，可以是两个数据点的位置之间的欧氏距离，与两个数据点的属性之间的欧氏距离的平均或加权平均。
在一种可能的实现方式中，该指定条件包括：
与该编码队列中的最后一个数据点之间的距离最小；
或者，
与该编码队列中已有的数据点之间的距离之和最小。
在本申请实施例中，编码端设备在向编码队列中添加数据点时，优先将距离编码队列中最后一个数据点最近的其它数据点添加至编码队列，或者，优先将距离编码队列中各个数据点组成的点群最近的其它数据点添加至编码队列，以保证后续的编码准确性。
在一种可能的实现方式中，该方法还包括：
将满足该指定条件的数据点从点云数据集中删除。
在本申请实施例中，上述编码队列的添加步骤也称为编码路径的规划，该编码路径规划方案可以如下：
1)建立点云数据点间的距离度量，可以采用各种常用的几何度量方法，例如：欧式距离等。其中，可以选择对所有点两两之间建立连接，即建立完全图；也可以对部分点两两之间建立连接，即有一部分点之间不存在连接关系；也可以根据起始点逐个选择点建立连接。
2)设原始点集为U(对应上述点云数据集)，已排序的点集为V(对应上述编码队列)。假设只有单一起始数据点x 1，根据一定的选点准则，逐一选择下一个次序的数据点x i+1加入V。
可选地，在将数据点x i+1加入V之后，还可以将x i+1从U中移除，这种情况下，每个数据点点在编码队列构建过程中只被计算一次；反之，若不将x i+1从U中移除，则每个数据点可被计算多次。其中，选择点的准则包括且不局限于以下两种：
x i+1与x i之间的距离最小；也就是，x i+1与x i之间的距离，是U中各个数据点分别到x i之间的距离的最小值。或者，x i+1与V的所有点之间的距离之和最小；也就是，x i+1与V的所有 点之间的距离之和，是U中各个数据点各自与V中所有点的距离之和的最小值。
在一种可能的实现方式中，在按照该各个数据点在该编码队列中的次序，对该各个数据点依次进行编码之前，还包括：
基于该编码队列中的相邻数据点之间的距离，对该编码队列中的数据点的顺序进行调整。
由于在向编码队列依次添加数据点的过程中，相邻数据点之间的距离并不一定能够保证最小，因此，在本申请实施例中，在向编码队列中添加数据点的过程中，或者在向编码队列中添加数据点之后，编码设备还可以对编码队列中的数据点的顺序进行优化调整，以提高后续的编码准确性。
在一种可能的实现方式中，该基于该编码队列中的相邻数据点之间的距离，对该编码队列中的数据点的顺序进行调整，包括：
获取第一距离与第二距离之和；该第一距离是该编码队列中的第i个数据点和第i+1个数据点之间的距离；该第二距离是该编码队列中的第j个数据点和第j+1个数据点之间的距离；i、j为大于或者等于1的整数，且i≠j；
获取第三距离与第四距离之和；该第三距离是该第i个数据点和该第j+1个数据点之间的距离，该第四距离是该第i+1个数据点和该第j个数据点之间的距离；
响应于该第一距离与该第二距离之和，大于该第三距离与该第四距离之和，交换该第i+1个数据点与该第j+1个数据点在该编码队列中的位置。
其中，优化调整方法可以如下：对已排序的点集V中的点对之间进行互换排序，例如，已排序的点对x i，x i+1与x j，x j+1，i≠j，两对点的距离之和为d 1。计算x i，x j+1，与x j，x i+1的距离之和为d 2。若d 1>d 2，则保持互换后的点间顺序。其中，x i+1与x j可以是同一个数据点，也可以是不同的数据点。
在一种可能的实现方式中，编码端设备在点云数据集在上述基于TSP的路径规划过程中，编码端设备可以在点云数据集或者编码队列中插入新的数据点(比如，将属于其它点云数据集的数据点插入当前的点云数据集，或者，在编码队列中插入新的数据点)。
在一种可能的实现方式中，在上述基于TSP的路径规划过程中，编码端设备也可以在点云数据集或者编码队列中删除已有的数据点。比如，将当前点云数据集中的数据点添加至其它点云数据集时，可以从当前点云数据集中删除该数据点。
也就是说，在本申请所示的方案中，在编码过程中的队列添加阶段，编码器可以额外添加数据点，或者，删除已有的数据点，能够提高编码过程的自由度和灵活性。
步骤705，编码端设备按照该各个数据点在该编码队列中的次序，对该各个数据点依次进行编码，获得该点云数据集对应的已编码点云数据。
在一种可能的实现方式中，该按照该各个数据点在该编码队列中的次序，对该各个数据点依次进行编码，包括：
响应于满足排序终止条件，执行按照该各个数据点在该编码队列中的次序，对该各个数据点依次进行编码的步骤；
该终止条件包括：
该点云数据集中不存在未被添加至该编码队列的数据点；
或者，
该编码队列中的数据点之间的距离之和达到指定阈值。
在本申请实施例中，在进行编码队列添加的过程中，若判断终止准则成立，则编码器设备可以输出编码队列，并进行下一步的编码。其中，上述终止准则可以包括且不局限于以下方法：
当
Figure PCTCN2021131278-appb-000001
所有点被遍历，终止排序；
当V中所有点的距离度量之和大于某个设定阈值；
当V中所有点的距离度量之和不能再被优化。
在一种可能的实现方式中，该按照该各个数据点在该编码队列中的次序，对该各个数据点依次进行编码，包括：
对于该编码队列中的任意相邻的第一数据点和第二数据点，获取该第二数据点与该第一数据点之间的残差信号。
其中，上述残差信号，包括对应的数据点的几何残差和属性残差中的至少一种。
在本申请实施例所示的方案中，编码端设备可以通过计算预测残差的方式对点云数据进行编码。也就是说，根据不同的条件设定，当排序终止后，残差的计算过程为：以前序点x i为参考点，后序点x i+1对应的残差为r i＝x i+1-x i。所得残差可通过常用熵编码器进行编码，比如，通过对残差量化之后，通过熵编码器进行熵编码，以输出已编码点云数据对应的几何比特流和/或属性比特流。
步骤706，解码端设备获取点云数据集对应的已编码点云数据。
在本申请实施例中，对于上述点云数据集，经过上述步骤编码后得到的已编码点云数据被传输至解码端设备中。
步骤707，解码端设备获取参考信息；该参考信息用于指示该编码队列的起始参考数据点。
在一种可能的实现方式中，该获取参考信息，包括：
获取默认的该参考信息；
解析该已编码点云数据的码流头信息，获得该参考信息；
基于该点云数据集的数据点划分方式获取该参考信息；
或者，解析该点云数据集中的数据点的层级信息，获得该参考信息。
在本申请实施例中，解码端设备在解码前，可以获得参考信息，比如，当上述编码过程中以编码队列中的首个数据点作为起始参考数据点为例，确认TSP所选的起始位置信息
Figure PCTCN2021131278-appb-000002
包含但不限于以下情况：
1)解析对应起始位置信息为默认值；
2)解析点云码流头信息，仅获得一个起始位置信息；
3)解析八叉树或其他划分方式，例如八叉树的当前节点作为起始位置信息，可有一个或多个起始位置信息；
4)解析LoD头信息，获得起始位置信息，可以有一个或多个起始位置信息。
步骤708，解码端设备基于该参考信息以及该已编码点云数据，按照该各个数据点在该编码队列中的次序，对该各个数据点依次进行解码。
编码端设备在获取到已编码点云数据之后，通过解析得到参考信息和残差信号，以参考信号指示的数据点作为上述编码队列对应的初始参考数据点，并从初始参考数据点开始，以初始参考数据点的位置信息和属性信息为参考值，依次解码重建上述编码队列中的各个数据点，每次重建一个数据点时，以前一个已重建的数据点为参考，结合对应的残差信号进行重建。
在本申请实施例中，解码端设备可以对已编码点云数据进行解析，获得残差信号{R|r i∈R n,i＝1,…,N-1}，解码目标是要获得重建信号
Figure PCTCN2021131278-appb-000003
其中n为信号的维度(几何信息的维度为3，假设属性信息的维度为3)，N为信号个数，可按以下方式进行处理：
对几何信息预测或属性信息单独预测时，即n＝3，基于解码的起始信号
Figure PCTCN2021131278-appb-000004
重建信号为TSP优化排序中的前一个信号与对应残差信号之和，即
Figure PCTCN2021131278-appb-000005
同时对几何和属性信息预测时，即n＝6，基于解码的起始信号
Figure PCTCN2021131278-appb-000006
重建信号为前一个信号与对应残差信号之和，即
Figure PCTCN2021131278-appb-000007
综上所述，本申请实施例所示的方案，编码端设备按照点云数据中各个数据点与编码队列中已有的数据点之间的距离，对各个数据点进行排序之后，按照排序的顺序依次进行编码， 从而能够实现对点云数据中距离靠近的数据点进行依次编码，相应的，解码端设备只需要结合参考信息和各个数据点的残差信号即可以重建点云数据，能够保证编解码的准确性，同时，能够显著的降低编解码的复杂度，提高编解码效率。
本申请所示的方案的各个步骤，可以组合使用，或者分开单独使用。在本申请上述实施例所示的方案中，提供了一种通过对点云中的数据点排序后，依序进行残差编码的点云信息预测方法，可用于对点云数据的几何信息、属性信息的预测，上述编码方案可以独立于传统的基于八叉树的编码模式来实现。
以本申请上述实施例所示的方案应用于编码过程为例，请参考图8，其示出了本申请一个实施例提供的点云数据编码流程框架图。如图8所示，本申请上述实施例涉及的一种示例性的编码流程可以包括如下主要步骤：
S81，对点云数据集中的数据点进行预处理。
编码器可以对点云数据集中的数据点的位置信息进行预处理(包括坐标系转换和体素化)。
可选的，编码器还可以对点云数据集中的数据点的属性信息进行预处理，例如，对点云数据集中的数据点进行颜色转换。
S82，对预处理后的点云数据集中的数据点进行距离度量计算，获得各个数据点两两之间的距离信息。
其中，上述各个数据点两两之间的距离信息可以是位置距离、属性距离、或者位置和属性的联合距离。
S83，按照各个数据点两两之间的距离信息，将点云数据集中的数据点依次添加到编码队列。
在本申请实施例中，编码器可以按照各个数据点两两之间的距离信息，从一个或者多个初始数据点开始，依次将点云数据集中距离编码队列的部分或者全部数据点最近的数据点添加至编码队列的末尾，直至满足终止条件。
其中，编码器依次将点云数据集中距离编码队列的部分或者全部数据点最近的数据点添加至编码队列的末尾的过程可以参考上述图5所述实施例中的相关步骤，此处不再赘述。
S84，对编码队列中的数据点的顺序进行优化调整。
编码器在构建编码队列过程中，或者，在构建编码队列之后，可以基于编码队列中各组相邻点对之间的距离，对编码队列中的数据点的顺序进行调整，以进一步提高后续的编码效果。
S85，按照编码队列中的各个数据点的排列顺序依次进行残差编码，获得各个数据点的残差信号。
其中，上述对编码队列中的各个数据点依次进行残差编码，可以包括对各个数据点的位置信息和属性信息分别进行残差编码，其中，对属性信息的残差编码可以包括：基于位置信息对应的残差信号/量化后的残差信息进行位置重建和属性重上色，位置重建和属性重上色的结果进行属性信息的残差编码，比如，通过预测变换编码、提升变换编码或者RAHT变换编码的方式对属性信息进行残差编码，得到属性信息的残差信号。
S86，对上述残差信号进行量化和熵编码，输出已编码点云数据。
编码器分别对上述各个数据点的位置信息的残差编码和属性信息的残差编码进行量化和熵编码之后，即可以输出已编码点云数据。
在解码侧，解码器只需要获取到已编码点云数据后，解析获得参考信号，得到编码队列中首个数据点，基于首个数据点的位置残差和属性残差，按照上述S85和S86的逆过程，对编码队列中的各个数据点依次进行重建。
下述为本申请装置实施例，可以用于执行本申请方法实施例。对于本申请装置实施例中未披露的细节，请参照本申请方法实施例。
请参考图9，其示出了本申请一个实施例提供的点云数据编码装置的框图。该装置具有实现上述方法示例的功能。该装置可以包括：
点云获取模块901，用于获取点云数据集，所述点云数据集中包含至少两个数据点；
编码模块902，用于按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据；
其中，所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的。
在一种可能的实现方式中，所述装置还包括：
队列添加模块，用于在所述编码模块902按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据之前，基于目标数据点对之间的距离，将所述点云数据集中的各个数据点依次添加至编码队列；所述目标数据点对是所述编码队列中已有的数据点与所述点云数据集中的数据点构成的数据点对；
所述编码模块902，用于按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据。
在一种可能的实现方式中，所述数据点对之间的距离包括：
所述数据点对中的两个数据点的位置信息之间的距离；
或者，所述数据点对中的两个数据点的属性信息之间的距离；
或者，通过所述数据点对中的两个数据点的位置信息之间的距离，以及，所述两个数据点的属性信息之间的距离得到的联合距离。
在一种可能的实现方式中，所述队列添加模块，用于，
基于所述编码队列中已有的数据点与所述点云数据集中的数据点之间的距离，从所述点云数据集中依次选择满足指定条件的数据点添加至所述编码队列。
在一种可能的实现方式中，所述指定条件包括：
与所述编码队列中的最后一个数据点之间的距离最小；
或者，
与所述编码队列中已有的数据点之间的距离之和最小。
在一种可能的实现方式中，所述装置还包括：
初始数据点确定模块，用于在队列添加模块基于目标数据点对之间的距离，将所述点云数据集中的各个数据点依次添加至编码队列之前，响应于所述编码队列为空，从所述点云数据集中确定初始数据点；
初始数据点添加模块，用于将所述初始数据点添加至所述编码队列。
在一种可能的实现方式中，所述初始数据点确定模块，用于，
从所述点云数据集中随机选择一个数据点，作为所述初始数据点；
基于所述点云数据集中包含的数据点的几何特征，从所述点云数据集中确定所述初始数据点；
基于所述点云数据集中包含的数据点的统计特征，从所述点云数据集中确定所述初始数据点；
或者，响应于所述点云数据集的数据点划分方式，从所述点云数据集中确定所述初始数据点。
在一种可能的实现方式中，所述装置还包括：
队列调整模块，用于在编码模块902按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码之前，基于所述编码队列中的相邻数据点之间的距离，对所述编码队列中的数据点的顺序进行调整。
在一种可能的实现方式中，所述队列调整模块，用于，
获取第一距离与第二距离之和；所述第一距离是所述编码队列中的第i个数据点和第i+1个数据点之间的距离；所述第二距离是所述编码队列中的第j个数据点和第j+1个数据点之间 的距离；i、j为大于或者等于1的整数，且i≠j；
获取第三距离与第四距离之和；所述第三距离是所述第i个数据点和所述第j+1个数据点之间的距离，所述第四距离是所述第i+1个数据点和所述第j个数据点之间的距离；
响应于所述第一距离与所述第二距离之和，大于所述第三距离与所述第四距离之和，交换所述第i+1个数据点与所述第j+1个数据点在所述编码队列中的位置。
在一种可能的实现方式中，所述编码模块902，用于响应于满足排序终止条件，执行按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码的步骤；
所述终止条件包括：
所述点云数据集中不存在未被添加至所述编码队列的数据点；
或者，
所述编码队列中的数据点之间的距离之和达到指定阈值。
综上所述，本申请实施例所示的方案，编码端设备按照点云数据中各个数据点之间的距离，对各个数据点进行排序之后，按照排序的顺序依次进行编码，从而能够实现对点云数据中距离靠近的数据点进行依次编码，相应的，解码端设备只需要结合参考信息和各个数据点的残差信号即可以重建点云数据，能够保证编解码的准确性，同时，能够显著的降低编解码的复杂度，提高编解码效率。
请参考图10，其示出了本申请一个实施例提供的点云数据解码装置的框图。该装置具有实现上述方法示例的功能。该装置可以包括：
数据获取模块1001，用于获取点云数据集对应的已编码点云数据；所述已编码点云数据是编码设备基于点云数据集中的各个数据点的编码次序，对所述各个数据点依次进行编码得到的；所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的；
参考信息获取模块1002，用于获取参考信息；所述参考信息用于指示所述编码队列的起始参考数据点；
解码模块1003，用于基于所述参考信息以及所述已编码点云数据，按照所述各个数据点的编码次序，对所述各个数据点依次进行解码。
在一种可能的实现方式中，所述已编码点云数据是所述编码设备基于目标数据点对之间的距离，将所述各个数据点依次添加至编码队列，并按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码得到的；所述目标数据点对是所述编码队列中已有的数据点与所述点云数据集中的数据点构成的数据点对；
所述解码模块1003，用于基于所述参考信息以及所述已编码点云数据，按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行解码。
在一种可能的实现方式中，所述参考信息获取模块1002，用于，
获取默认的所述参考信息；
解析所述已编码点云数据的码流头信息，获得所述参考信息；
基于所述点云数据集的数据点划分方式获取所述参考信息；
解析所述点云数据集中的数据点的层级信息，获得所述参考信息。
综上所述，本申请实施例所示的方案，编码端设备按照点云数据中各个数据点之间的距离，对各个数据点进行排序之后，按照排序的顺序依次进行编码，从而能够实现对点云数据中距离靠近的数据点进行依次编码，相应的，解码端设备只需要结合参考信息和各个数据点的残差信号即可以重建点云数据，能够保证编解码的准确性，同时，能够显著的降低编解码的复杂度，提高编解码效率。
请参考图11，其示出了本申请一个实施例提供的计算机设备的结构框图。该计算机设备可以是上文介绍的编码端端设备，也可以是上文介绍的解码端设备。该计算机设备110可以包括：处理器111、存储器112、通信接口113、编码器/解码器114和总线115。
处理器111包括一个或者一个以上处理核心，处理器111通过运行软件程序以及模块，从而执行各种功能应用以及信息处理。
存储器112可用于存储计算机程序，处理器111用于执行该计算机程序，以实现上述图5或图6所示实施例涉及的方法中的全部或部分步骤。
通信接口113可用于与其它设备进行通信，如收发点云数据。
编码器/解码器114可用于实现编码和解码功能，如对点云数据进行编码和解码。
存储器112通过总线115与处理器111相连。
此外，存储器112可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，易失性或非易失性存储设备包括但不限于：磁盘或光盘，EEPROM(Electrically Erasable Programmable Read-Only Memory，电可擦除可编程只读存储器)，EPROM(Erasable Programmable Read-Only Memory，可擦除可编程只读存储器)，SRAM(Static Random-Access Memory，静态随时存取存储器)，ROM(Read-Only Memory，只读存储器)，磁存储器，快闪存储器，PROM(Programmable Read-Only Memory，可编程只读存储器)。
本领域技术人员可以理解，图11中示出的结构并不构成对计算机设备110的限定，可以包括比图示更多或更少的组件，或者组合某些组件，或者采用不同的组件布置。
在示例性实施例中，还提供了一种计算机可读存储介质，所述计算机可读存储介质中存储有至少一条计算机程序，所述至少一条计算机程序在被处理器执行时实现上述图5、图6、图7或图8所示实施例涉及的方法中的全部或部分步骤。
在示例性实施例中，还提供了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存储介质中。计算机设备的处理器从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该计算机设备执行上述图5、图6、图7或图8所示实施例涉及的方法中的全部或部分步骤。
应当理解的是，在本文中提及的“多个”是指两个或两个以上。“和/或”，描述关联对象的关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，同时存在A和B，单独存在B这三种情况。字符“/”一般表示前后关联对象是一种“或”的关系。
以上所述仅为本申请的示例性实施例，并不用以限制本申请，凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。

Claims (20)

  1. 一种点云数据编码方法，由计算机设备执行，所述方法包括：
    获取点云数据集，所述点云数据集中包含至少两个数据点；
    按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据；
    其中，所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的。
  2. 根据权利要求1所述的方法，所述按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据之前，还包括：
    基于目标数据点对之间的距离，将所述点云数据集中的各个数据点依次添加至编码队列；所述目标数据点对是所述编码队列中已有的数据点与所述点云数据集中的数据点构成的数据点对；
    所述按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据，包括：
    按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据。
  3. 根据权利要求2所述的方法，所述数据点对之间的距离包括：
    所述数据点对中的两个数据点的位置信息之间的距离；
    或者，所述数据点对中的两个数据点的属性信息之间的距离；
    或者，通过所述数据点对中的两个数据点的位置信息之间的距离，以及，所述两个数据点的属性信息之间的距离得到的联合距离。
  4. 根据权利要求2所述的方法，所述按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码，包括：
    对于所述编码队列中的任意相邻的第一数据点和第二数据点，获取所述第二数据点与所述第一数据点之间的残差信号。
  5. 根据权利要求2所述的方法，所述基于目标数据点对之间的距离，将所述点云数据集中的各个数据点依次添加至编码队列，包括：
    基于所述编码队列中已有的数据点与所述点云数据集中的数据点之间的距离，从所述点云数据集中依次选择满足指定条件的数据点添加至所述编码队列；
    所述指定条件包括：
    与所述编码队列中的最后一个数据点之间的距离最小；
    或者，
    与所述编码队列中已有的数据点之间的距离之和最小。
  6. 根据权利要求2所述的方法，所述基于目标数据点对之间的距离，将所述点云数据集中的各个数据点依次添加至编码队列之前，还包括：
    响应于所述编码队列为空，从所述点云数据集中确定初始数据点；
    将所述初始数据点添加至所述编码队列。
  7. 根据权利要求6所述的方法，所述从所述点云数据集中确定初始数据点，包括：
    从所述点云数据集中随机选择一个数据点，作为所述初始数据点；
    基于所述点云数据集中包含的数据点的几何特征，从所述点云数据集中确定所述初始数据点；
    基于所述点云数据集中包含的数据点的统计特征，从所述点云数据集中确定所述初始数据点；
    或者，响应于所述点云数据集的数据点划分方式，从所述点云数据集中确定所述初始数据点。
  8. 根据权利要求2所述的方法，所述按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码之前，还包括：
    基于所述编码队列中的相邻数据点之间的距离，对所述编码队列中的数据点的顺序进行调整。
  9. 根据权利要求8所述的方法，所述基于所述编码队列中的相邻数据点之间的距离，对所述编码队列中的数据点的顺序进行调整，包括：
    获取第一距离与第二距离之和；所述第一距离是所述编码队列中的第i个数据点和第i+1个数据点之间的距离；所述第二距离是所述编码队列中的第j个数据点和第j+1个数据点之间的距离；i、j为大于或者等于1的整数，且i≠j；
    获取第三距离与第四距离之和；所述第三距离是所述第i个数据点和所述第j+1个数据点之间的距离，所述第四距离是所述第i+1个数据点和所述第j个数据点之间的距离；
    响应于所述第一距离与所述第二距离之和，大于所述第三距离与所述第四距离之和，交换所述第i+1个数据点与所述第j+1个数据点在所述编码队列中的位置。
  10. 根据权利要求2所述的方法，所述按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码，包括：
    响应于满足排序终止条件，执行按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码的步骤；
    所述终止条件包括：
    所述点云数据集中不存在未被添加至所述编码队列的数据点；
    或者，
    所述编码队列中的数据点之间的距离之和达到指定阈值。
  11. 一种点云数据解码方法，由计算机设备执行，所述方法包括：
    获取与点云数据集对应的已编码点云数据；所述已编码点云数据是编码设备基于点云数据集中的各个数据点的编码次序，对所述各个数据点依次进行编码得到的；所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的；
    获取参考信息；所述参考信息用于指示所述编码队列的起始参考数据点；
    基于所述参考信息以及所述已编码点云数据，按照所述各个数据点的编码次序，对所述各个数据点依次进行解码。
  12. 根据权利要求11所述的方法，所述已编码点云数据是所述编码设备基于目标数据点对之间的距离，将所述各个数据点依次添加至编码队列，并按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码得到的；所述目标数据点对是所述编码队列中已有的数据点与所述点云数据集中的数据点构成的数据点对；
    所述基于所述参考信息以及所述已编码点云数据，按照所述各个数据点的编码次序，对所述各个数据点依次进行解码，包括：
    基于所述参考信息以及所述已编码点云数据，按照所述各个数据点在所述编码队列中的 次序，对所述各个数据点依次进行解码。
  13. 根据权利要求11所述的方法，所述获取参考信息，包括：
    获取默认的所述参考信息；
    解析所述已编码点云数据的码流头信息，获得所述参考信息；
    基于所述点云数据集的数据点划分方式获取所述参考信息；
    或者，解析所述点云数据集中的数据点的层级信息，获得所述参考信息。
  14. 一种点云数据编码装置，所述装置包括：
    点云获取模块，用于获取点云数据集，所述点云数据集中包含至少两个数据点；
    编码模块，用于按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据；
    其中，所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的。
  15. 根据权利要求14所述的装置，还包括：
    队列添加模块，用于在所述编码模块按照所述各个数据点的编码次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据之前，基于目标数据点对之间的距离，将所述点云数据集中的各个数据点依次添加至编码队列；所述目标数据点对是所述编码队列中已有的数据点与所述点云数据集中的数据点构成的数据点对；
    所述编码模块，用于按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码，获得与所述点云数据集对应的已编码点云数据。
  16. 一种点云数据解码装置，所述装置包括：
    数据获取模块，用于获取与点云数据集对应的已编码点云数据；所述已编码点云数据是编码设备基于点云数据集中的各个数据点的编码次序，对所述各个数据点依次进行编码得到的；所述各个数据点的编码次序是基于所述各个数据点之间的距离确定的；
    参考信息获取模块，用于获取参考信息；所述参考信息用于指示所述编码队列的起始参考数据点；
    解码模块，用于基于所述参考信息以及所述已编码点云数据，按照所述各个数据点的编码次序，对所述各个数据点依次进行解码。
  17. 根据权利要求16所述的装置，所述已编码点云数据是所述编码设备基于目标数据点对之间的距离，将所述各个数据点依次添加至编码队列，并按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行编码得到的；所述目标数据点对是所述编码队列中已有的数据点与所述点云数据集中的数据点构成的数据点对；
    所述解码模块，用于基于所述参考信息以及所述已编码点云数据，按照所述各个数据点在所述编码队列中的次序，对所述各个数据点依次进行解码。
  18. 一种计算机设备，所述计算机设备包含处理器和存储器，所述存储器中存储有至少一条计算机程序；所述至少一条计算机程序由所述处理器加载并执行以实现如权利要求1至10任一所述的点云数据编码方法，或者，实现如权利要求11至13任一所述的点云数据解码方法。
  19. 一种计算机可读存储介质，所述存储介质中存储有至少一条计算机程序，所述至少一条计算机程序由处理器加载并执行以实现如权利要求1至10任一所述的点云数据编码方法，或者，实现如权利要求11至13任一所述的点云数据解码方法。
  20. 一种计算机程序产品，所述计算机程序产品包括计算机指令，所述计算机指令由计算机设备的处理器读取并执行，以实现如权利要求1至10任一所述的点云数据编码方法，或者，实现如权利要求11至13任一所述的点云数据解码方法。
PCT/CN2021/131278 2020-12-07 2021-11-17 点云数据编码方法、解码方法、设备、介质及程序产品 Ceased WO2022121648A1 (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP21902355.3A EP4250726A4 (en) 2020-12-07 2021-11-17 Point cloud data encoding method, point cloud data decoding method, device, medium, and program product
US17/974,829 US12488507B2 (en) 2020-12-07 2022-10-27 Point cloud data encoding method and decoding method, device, medium, and program product

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN202011440832.7A CN114598892B (zh) 2020-12-07 2020-12-07 点云数据编码方法、解码方法、装置、设备及存储介质
CN202011440832.7 2020-12-07

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US17/974,829 Continuation US12488507B2 (en) 2020-12-07 2022-10-27 Point cloud data encoding method and decoding method, device, medium, and program product

Publications (1)

Publication Number Publication Date
WO2022121648A1 true WO2022121648A1 (zh) 2022-06-16

Family

ID=81802671

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2021/131278 Ceased WO2022121648A1 (zh) 2020-12-07 2021-11-17 点云数据编码方法、解码方法、设备、介质及程序产品

Country Status (4)

Country Link
US (1) US12488507B2 (zh)
EP (1) EP4250726A4 (zh)
CN (2) CN118075494A (zh)
WO (1) WO2022121648A1 (zh)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11956470B2 (en) * 2020-04-07 2024-04-09 Qualcomm Incorporated Predictor index signaling for predicting transform in geometry-based point cloud compression
CN115102935B (zh) * 2022-06-17 2024-02-09 腾讯科技（深圳）有限公司 一种点云编码方法、点云解码方法及相关设备
CN115102934B (zh) * 2022-06-17 2023-09-19 腾讯科技（深圳）有限公司 点云数据的解码方法、编码方法、装置、设备及存储介质
CN120956878A (zh) * 2022-08-19 2025-11-14 腾讯科技（深圳）有限公司 点云数据的解码方法、编码方法、装置、存储介质及设备
CN116933359B (zh) * 2023-06-26 2024-02-02 武汉峰岭科技有限公司 一种建筑复杂屋顶建模方法及系统

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9530225B1 (en) * 2013-03-11 2016-12-27 Exelis, Inc. Point cloud data processing for scalable compression
CN111052189A (zh) * 2017-09-06 2020-04-21 苹果公司 点云几何结构压缩

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20130163879A1 (en) * 2010-08-30 2013-06-27 Bk-Imaging Ltd. Method and system for extracting three-dimensional information
US11297346B2 (en) * 2016-05-28 2022-04-05 Microsoft Technology Licensing, Llc Motion-compensated compression of dynamic voxelized point clouds
EP3467784A1 (en) * 2017-10-06 2019-04-10 Thomson Licensing Method and device for up-sampling a point cloud
WO2019182102A1 (ja) * 2018-03-23 2019-09-26 パナソニック インテレクチュアル プロパティ コーポレーション オブ アメリカ 三次元データ符号化方法、三次元データ復号方法、三次元データ符号化装置、及び三次元データ復号装置
US10911787B2 (en) * 2018-07-10 2021-02-02 Apple Inc. Hierarchical point cloud compression
CN110148144B (zh) * 2018-08-27 2024-02-13 腾讯大地通途（北京）科技有限公司 点云数据的分割方法和装置、存储介质、电子装置
CN109889840B (zh) * 2019-03-20 2022-11-22 北京大学深圳研究生院 点云编码和解码的方法、编码设备和解码设备
US12581114B2 (en) * 2019-05-30 2026-03-17 Lg Electronics Inc. Method and device of encoding point cloud data and method and device of decoding point cloud device
CN111602176A (zh) * 2019-06-03 2020-08-28 深圳市大疆创新科技有限公司 点云数据的位置坐标的编解码方法、系统和存储介质
WO2021049758A1 (ko) * 2019-09-11 2021-03-18 엘지전자 주식회사 포인트 클라우드 데이터 송신 장치, 포인트 클라우드 데이터 송신 방법, 포인트 클라우드 데이터 수신 장치 및 포인트 클라우드 데이터 수신 방법
CN110781894B (zh) * 2019-09-29 2025-04-04 腾讯科技（深圳）有限公司 点云语义分割方法、装置及电子设备
CN111242997B (zh) * 2020-01-13 2023-11-10 北京大学深圳研究生院 一种基于滤波器的点云属性预测方法及设备
CN111405281A (zh) * 2020-03-30 2020-07-10 北京大学深圳研究生院 一种点云属性信息的编码方法、解码方法、存储介质及终端设备

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9530225B1 (en) * 2013-03-11 2016-12-27 Exelis, Inc. Point cloud data processing for scalable compression
CN111052189A (zh) * 2017-09-06 2020-04-21 苹果公司 点云几何结构压缩

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
See also references of EP4250726A4
ZHU WENJIE; XU YILING; LI LI; LI ZHU: "Lossless point cloud geometry compression via binary tree partition and intra prediction", 2017 IEEE 19TH INTERNATIONAL WORKSHOP ON MULTIMEDIA SIGNAL PROCESSING (MMSP), IEEE, 16 October 2017 (2017-10-16), pages 1 - 6, XP033271558, DOI: 10.1109/MMSP.2017.8122226 *

Also Published As

Publication number Publication date
US20230051652A1 (en) 2023-02-16
EP4250726A1 (en) 2023-09-27
US12488507B2 (en) 2025-12-02
CN114598892B (zh) 2024-01-30
CN118075494A (zh) 2024-05-24
EP4250726A4 (en) 2024-06-12
CN114598892A (zh) 2022-06-07

Similar Documents

Publication Publication Date Title
US12488507B2 (en) Point cloud data encoding method and decoding method, device, medium, and program product
CN116033186B (zh) 一种点云数据处理方法、装置、设备以及介质
WO2023024840A1 (zh) 点云编解码方法、编码器、解码器及存储介质
CN115100302B (zh) 点云处理方法、装置、设备以及介质
CN116016951A (zh) 点云处理方法、装置、设备及存储介质
US20250274608A1 (en) Geometry mode determination
CN120982095A (zh) 点云编解码方法、编码器、解码器、码流及存储介质
HK40067089A (zh) 点云数据编码方法、解码方法、装置、设备及存储介质
HK40067089B (zh) 点云数据编码方法、解码方法、装置、设备及存储介质
CN119484866B (zh) 一种点云处理方法、装置、设备、存储介质及产品
WO2025076662A1 (zh) 点云编解码方法、码流、编码器、解码器以及存储介质
WO2023173238A1 (zh) 编解码方法、码流、编码器、解码器以及存储介质
WO2025007360A1 (zh) 编解码方法、码流、编码器、解码器以及存储介质
WO2025076659A1 (zh) 点云编解码方法、码流、编码器、解码器以及存储介质
WO2024065406A1 (zh) 编解码方法、码流、编码器、解码器以及存储介质
WO2025010601A1 (zh) 编解码方法、编码器、解码器、码流以及存储介质
WO2025076672A1 (zh) 编解码方法、编码器、解码器、码流以及存储介质
CN115720273A (zh) 点云编解码中的属性预测方法、装置、设备及存储介质
WO2024174092A9 (zh) 编解码方法、码流、编码器、解码器以及存储介质
WO2025076663A1 (zh) 编解码方法、编解码器以及存储介质
HK40080516A (zh) 点云编解码中的属性预测方法、装置、设备及存储介质
WO2023173237A1 (zh) 编解码方法、码流、编码器、解码器以及存储介质
WO2025010590A1 (zh) 解码方法、编码方法、解码器和编码器
WO2025147915A1 (zh) 点云编解码方法、编解码器、码流以及存储介质
CN117896536A (zh) 点云解码、编码方法、介质、电子设备及产品

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 21902355

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2021902355

Country of ref document: EP

Effective date: 20230620

NENP Non-entry into the national phase

Ref country code: DE