CN114785998A - A point cloud compression method, device, electronic device and storage medium - Google Patents
A point cloud compression method, device, electronic device and storage mediumDownload PDFInfo
- Publication number
- CN114785998A CN114785998ACN202210694204.4ACN202210694204ACN114785998ACN 114785998 ACN114785998 ACN 114785998ACN 202210694204 ACN202210694204 ACN 202210694204ACN 114785998 ACN114785998 ACN 114785998A
- Authority
- CN
- China
- Prior art keywords
- point cloud
- sub
- graph
- pairs
- compressed
- 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.)
- Pending
Links
Images
Classifications
- 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
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F18/00—Pattern recognition
- G06F18/20—Analysing
- G06F18/23—Clustering techniques
- 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
- H04N19/169—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding
- H04N19/17—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being an image region, e.g. an object
- H04N19/176—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being an image region, e.g. an object the region being a block, e.g. a macroblock
- 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
- 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/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- H04N19/96—Tree coding, e.g. quad-tree coding
Landscapes
- Engineering & Computer Science (AREA)
- Signal Processing (AREA)
- Multimedia (AREA)
- Data Mining & Analysis (AREA)
- Theoretical Computer Science (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Evolutionary Biology (AREA)
- Evolutionary Computation (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Bioinformatics & Computational Biology (AREA)
- Artificial Intelligence (AREA)
- Life Sciences & Earth Sciences (AREA)
- Image Processing (AREA)
Abstract
Description
Translated fromChinese技术领域technical field
本公开涉及点云处理技术领域，具体而言，涉及一种点云的压缩方法、装置、电子设备及存储介质。The present disclosure relates to the technical field of point cloud processing, and in particular, to a point cloud compression method, device, electronic device and storage medium.
背景技术Background technique
三维点云是现实世界数字化的重要表现形式。随着三维扫描设备（激光、雷达等）的快速发展，点云的精度、分辨率更高。高精度点云广泛应用于城市数字化地图的构建，在如智慧城市、无人驾驶、文物保护等众多热门研究中起技术支撑作用。点云是三维扫描设备对物体表面采样所获取的，一帧点云的点数一般是百万级别，其中每个点包含几何信息和颜色、反射率等属性信息，数据量十分庞大。三维点云庞大的数据量给数据存储、传输等带来巨大挑战，所以点云压缩十分必要。3D point cloud is an important form of digitization of the real world. With the rapid development of 3D scanning equipment (laser, radar, etc.), the accuracy and resolution of point clouds are higher. High-precision point clouds are widely used in the construction of urban digital maps, and play a technical supporting role in many popular researches such as smart cities, unmanned driving, and cultural relics protection. A point cloud is obtained by sampling the surface of an object by a 3D scanning device. The number of points in a frame of point cloud is generally in the millions. Each point contains geometric information and attribute information such as color and reflectivity, and the amount of data is very large. The huge data volume of 3D point cloud brings great challenges to data storage and transmission, so point cloud compression is very necessary.
目前，各种各样的几何压缩方法被提出，包括：渐进式八叉树、预测树、动态二值分解、形状自适应小波变换、图变换、平面近似和旅行商预测等多种几何表示模型。其中的图变换，因为它对不规则离散结构上的信号具有频域稀疏表示能力，常常用于点云的属性压缩。然而，现有的图定义方法只考虑几何拓扑，不能充分反映点之间的属性相关性，限制了压缩性能。在纹理丰富的点云块中，由于具有快速变换的属性值，点与点之间的属性相关性变弱，并不能有效的利用点之间的距离体现属性相关，因此往往压缩性能较差。At present, various geometric compression methods have been proposed, including: progressive octree, prediction tree, dynamic binary decomposition, shape adaptive wavelet transform, graph transform, plane approximation and traveling salesman prediction and other geometric representation models . Among them, the graph transformation is often used for attribute compression of point clouds because of its sparse representation capability in the frequency domain for signals on irregular discrete structures. However, the existing graph definition methods only consider the geometric topology, which cannot fully reflect the attribute correlation between points, which limits the compression performance. In a point cloud with rich texture, due to the rapidly changing attribute values, the attribute correlation between points becomes weak, and the distance between points cannot be effectively used to reflect the attribute correlation, so the compression performance is often poor.
发明内容SUMMARY OF THE INVENTION
本公开实施例至少提供一种点云的压缩方法、装置、电子设备及存储介质，可以提升点云属性压缩的压缩性能与压缩效果。The embodiments of the present disclosure provide at least a point cloud compression method, device, electronic device, and storage medium, which can improve the compression performance and compression effect of point cloud attribute compression.
本公开实施例提供了一种点云的压缩方法，所述方法包括：An embodiment of the present disclosure provides a point cloud compression method, the method includes:
获取待压缩点云；Get the point cloud to be compressed;
将所述待压缩点云划分为多个子点云块，其中，所述子点云块通过图进行描述，确定所述子点云块对应的权重矩阵；Divide the point cloud to be compressed into a plurality of sub-point cloud blocks, wherein the sub-point cloud blocks are described by a diagram, and determine the weight matrix corresponding to the sub-point cloud blocks;
采用谱聚类算法将所述图过划分为多个子图；using spectral clustering algorithm to over-divide the graph into a plurality of subgraphs;
根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图；Iteratively merge the subgraphs according to a preset cost function, and determine an optimized graph corresponding to the subgraphs;
确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵；Determine the target adjacency matrix corresponding to the optimization graph, and update the weight matrix according to the target adjacency matrix;
根据更新后的所述权重矩阵确定所述优化图对应的拉普拉斯矩阵，根据所述拉普拉斯矩阵压缩所述待压缩点云。The Laplacian matrix corresponding to the optimization graph is determined according to the updated weight matrix, and the to-be-compressed point cloud is compressed according to the Laplacian matrix.
一种可选的实施方式中，所述将所述待压缩点云划分为多个子点云块，具体包括：In an optional implementation manner, the dividing the point cloud to be compressed into a plurality of sub-point cloud blocks specifically includes:
根据所述待压缩点云的几何结构，将所述待压缩点云划分为多个点云块；According to the geometric structure of the point cloud to be compressed, the point cloud to be compressed is divided into a plurality of point cloud blocks;
针对每个所述点云块，采用归一化分割方式将该所述点云块过分割为多个所述子点云块。For each of the point cloud blocks, the point cloud block is over-segmented into a plurality of the sub-point cloud blocks by using a normalized segmentation method.
一种可选的实施方式中，所述确定所述子点云块对应的权重矩阵，具体包括：In an optional implementation manner, the determining the weight matrix corresponding to the sub-point cloud block specifically includes:
将所述子点云块中的每个节点转换为所述权重矩阵中的顶点；converting each node in the sub-point cloud block into a vertex in the weight matrix;
采用高斯核函数计算所述顶点之间的边权值，根据所述边权值构建所述权重矩阵。A Gaussian kernel function is used to calculate edge weights between the vertices, and the weight matrix is constructed according to the edge weights.
一种可选的实施方式中，所述根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图，具体包括：In an optional implementation manner, the iteratively merging the subgraphs according to a preset cost function to determine the optimized graph corresponding to the subgraphs specifically includes:
将相邻的所述子图两两合并，生成多个子图对；Merging the adjacent sub-graphs two by two to generate a plurality of sub-graph pairs;
根据所述代价函数，确定每个所述子图对对应的合并代价；According to the cost function, determine the merging cost corresponding to each of the sub-graph pairs;
确定全部所述子图对中每两个所述子图对之间的代价差，合并所述代价差最大的两个所述子图对，其中，所述代价差为两个所述子图对分别对应的所述合并代价之和，与两个所述子图对合并后对应的合并代价之间的差值；Determine the cost difference between every two sub-graph pairs in all the sub-graph pairs, and combine the two sub-graph pairs with the largest cost difference, wherein the cost difference is the two sub-graphs The difference between the sum of the respectively corresponding merge costs and the merge costs corresponding to the merged two sub-graph pairs;
重复所述确定全部所述子图对中，每两个所述子图对之间的代价差，合并所述代价差最大的两个所述子图对的步骤，直至全部所述子图对之间的代价差小于零；Repeat the step of determining the cost difference between every two subgraph pairs among all the subgraph pairs, and merging the two subgraph pairs with the largest cost difference, until all the subgraph pairs The cost difference between them is less than zero;
将合并完成后的所述子图确定为所述优化图。The subgraph after the merging is completed is determined as the optimized graph.
一种可选的实施方式中，所述确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵，具体包括：In an optional embodiment, the determining the target adjacency matrix corresponding to the optimization graph, and updating the weight matrix according to the target adjacency matrix, specifically includes:
根据所述优化图对应的连通性，将所述优化图转换为对应的目标邻接矩阵；Converting the optimization graph into a corresponding target adjacency matrix according to the connectivity corresponding to the optimization graph;
构建以邻接矩阵作为变量，与所述权重矩阵相关联的惩罚函数，将所述目标邻接矩阵代入至所述惩罚函数，确定更新后的所述权重矩阵。Constructing a penalty function associated with the weight matrix with an adjacency matrix as a variable, substituting the target adjacency matrix into the penalty function, and determining the updated weight matrix.
本公开实施例还提供一种点云的压缩装置，所述装置包括：Embodiments of the present disclosure also provide a point cloud compression device, the device comprising:
获取模块，用于获取待压缩点云；The acquisition module is used to acquire the point cloud to be compressed;
第一划分模块，用于将所述待压缩点云划分为多个子点云块，其中，所述子点云块通过图进行描述，确定所述子点云块对应的权重矩阵；a first division module, configured to divide the point cloud to be compressed into a plurality of sub-point cloud blocks, wherein the sub-point cloud blocks are described by a graph, and a weight matrix corresponding to the sub-point cloud blocks is determined;
第二划分模块，用于采用谱聚类算法将所述图过划分为多个子图；The second division module is used to over-divide the graph into a plurality of subgraphs by using a spectral clustering algorithm;
合并模块，用于根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图；a merging module, configured to iteratively merge the subgraphs according to a preset cost function, and determine an optimized graph corresponding to the subgraphs;
确定模块，用于确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵；A determination module, configured to determine a target adjacency matrix corresponding to the optimization graph, and update the weight matrix according to the target adjacency matrix;
压缩模块，用于根据更新后的所述权重矩阵确定所述优化图对应的拉普拉斯矩阵，根据所述拉普拉斯矩阵压缩所述待压缩点云。A compression module, configured to determine a Laplacian matrix corresponding to the optimization graph according to the updated weight matrix, and compress the to-be-compressed point cloud according to the Laplacian matrix.
一种可选的实施方式中，所述第一划分模块具体用于：In an optional implementation manner, the first division module is specifically used for:
根据所述待压缩点云的几何结构，将所述待压缩点云划分为多个点云块；According to the geometric structure of the point cloud to be compressed, the point cloud to be compressed is divided into a plurality of point cloud blocks;
针对每个所述点云块，采用归一化分割方式将该所述点云块过分割为多个所述子点云块。For each of the point cloud blocks, the point cloud block is over-segmented into a plurality of the sub-point cloud blocks by using a normalized segmentation method.
一种可选的实施方式中，所述第一划分模块还用于：In an optional implementation manner, the first division module is further used for:
将所述子点云块中的每个节点转换为所述权重矩阵中的顶点；converting each node in the sub-point cloud block into a vertex in the weight matrix;
采用高斯核函数计算所述顶点之间的边权值，根据所述边权值构建所述权重矩阵。A Gaussian kernel function is used to calculate edge weights between the vertices, and the weight matrix is constructed according to the edge weights.
一种可选的实施方式中，所述合并模块具体用于：In an optional implementation manner, the merging module is specifically used for:
将相邻的所述子图两两合并，生成多个子图对；Merging the adjacent sub-graphs two by two to generate a plurality of sub-graph pairs;
根据所述代价函数，确定每个所述子图对对应的合并代价；According to the cost function, determine the merging cost corresponding to each of the sub-graph pairs;
确定全部所述子图对中每两个所述子图对之间的代价差，合并所述代价差最大的两个所述子图对，其中，所述代价差为两个所述子图对分别对应的所述合并代价之和，与两个所述子图对合并后对应的合并代价之间的差值；Determine the cost difference between every two sub-graph pairs in all the sub-graph pairs, and combine the two sub-graph pairs with the largest cost difference, wherein the cost difference is the two sub-graphs The difference between the sum of the respectively corresponding merge costs and the merge costs corresponding to the merged two sub-graph pairs;
重复所述确定全部所述子图对中，每两个所述子图对之间的代价差，合并所述代价差最大的两个所述子图对的步骤，直至全部所述子图对之间的代价差小于零；Repeat the step of determining the cost difference between every two subgraph pairs among all the subgraph pairs, and merging the two subgraph pairs with the largest cost difference, until all the subgraph pairs The cost difference between them is less than zero;
将合并完成后的所述子图确定为所述优化图。The subgraph after the merging is completed is determined as the optimized graph.
一种可选的实施方式中，所述更新模块具体用于：In an optional implementation manner, the update module is specifically used for:
根据所述优化图对应的连通性，将所述优化图转换为对应的目标邻接矩阵；Converting the optimization graph into a corresponding target adjacency matrix according to the connectivity corresponding to the optimization graph;
构建以邻接矩阵作为变量，与所述权重矩阵相关联的惩罚函数，将所述目标邻接矩阵代入至所述惩罚函数，确定更新后的所述权重矩阵。Constructing a penalty function associated with the weight matrix with an adjacency matrix as a variable, substituting the target adjacency matrix into the penalty function, and determining the updated weight matrix.
本公开实施例还提供一种电子设备，包括：处理器、存储器和总线，所述存储器存储有所述处理器可执行的机器可读指令，当电子设备运行时，所述处理器与所述存储器之间通过总线通信，所述机器可读指令被所述处理器执行时执行上述点云的压缩方法，或上述点云的压缩方法中任一种可能的实施方式中的步骤。Embodiments of the present disclosure further provide an electronic device, including: a processor, a memory, and a bus, where the memory stores machine-readable instructions executable by the processor, and when the electronic device runs, the processor and the The memories communicate with each other through a bus, and when the machine-readable instructions are executed by the processor, the above method for compressing a point cloud or steps in any possible implementation manner of the above method for compressing a point cloud are executed.
本公开实施例还提供一种计算机可读存储介质，该计算机可读存储介质上存储有计算机程序，该计算机程序被处理器运行时执行上述点云的压缩方法，或上述点云的压缩方法中任一种可能的实施方式中的步骤。Embodiments of the present disclosure also provide a computer-readable storage medium, where a computer program is stored on the computer-readable storage medium, and the computer program is executed by a processor to execute the above point cloud compression method, or the above point cloud compression method. steps in any possible implementation.
本公开实施例提供的一种点云的压缩方法、装置、电子设备及存储介质，通过获取待压缩点云；将所述待压缩点云划分为多个子点云块，其中，所述子点云块通过子图进行描述，确定所述子点云块对应的权重矩阵；根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图；确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵；根据更新后的所述权重矩阵确定所述优化图对应的拉普拉斯矩阵，根据所述拉普拉斯矩阵压缩所述待压缩点云。可以提升点云属性压缩的压缩性能与压缩效果。In a point cloud compression method, device, electronic device, and storage medium provided by the embodiments of the present disclosure, the point cloud to be compressed is obtained by obtaining the point cloud to be compressed; the point cloud to be compressed is divided into a plurality of sub-point cloud blocks, wherein the sub-point The cloud blocks are described by sub-graphs, and the weight matrix corresponding to the sub-point cloud blocks is determined; the sub-graphs are iteratively merged according to a preset cost function, and the optimized graph corresponding to the sub-graph is determined; target adjacency matrix, update the weight matrix according to the target adjacency matrix; determine the Laplacian matrix corresponding to the optimization graph according to the updated weight matrix, and compress the to-be-compressed matrix according to the Laplacian matrix point cloud. It can improve the compression performance and compression effect of point cloud attribute compression.
为使本公开的上述目的、特征和优点能更明显易懂，下文特举较佳实施例，并配合所附附图，作详细说明如下。In order to make the above-mentioned objects, features and advantages of the present disclosure more obvious and easy to understand, the preferred embodiments are exemplified below, and are described in detail as follows in conjunction with the accompanying drawings.
附图说明Description of drawings
为了更清楚地说明本公开实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，此处的附图被并入说明书中并构成本说明书中的一部分，这些附图示出了符合本公开的实施例，并与说明书一起用于说明本公开的技术方案。应当理解，以下附图仅示出了本公开的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。In order to explain the technical solutions of the embodiments of the present disclosure more clearly, the following briefly introduces the accompanying drawings required in the embodiments, which are incorporated into the specification and constitute a part of the specification. The drawings illustrate embodiments consistent with the present disclosure, and together with the description serve to explain the technical solutions of the present disclosure. It should be understood that the following drawings only show some embodiments of the present disclosure, and therefore should not be regarded as limiting the scope. Other related figures are obtained from these figures.
图1示出了本公开实施例所提供的一种点云的压缩方法的流程图；FIG. 1 shows a flowchart of a method for compressing a point cloud provided by an embodiment of the present disclosure;
图2示出了本公开实施例所提供一种子图的合并方法的流程图；FIG. 2 shows a flowchart of a method for merging subgraphs provided by an embodiment of the present disclosure;
图3示出了本公开实施例所提供的一种点云的压缩装置的示意图；FIG. 3 shows a schematic diagram of a point cloud compression device provided by an embodiment of the present disclosure;
图4示出了本公开实施例所提供的一种电子设备的结构示意图。FIG. 4 shows a schematic structural diagram of an electronic device provided by an embodiment of the present disclosure.
具体实施方式Detailed ways
为使本公开实施例的目的、技术方案和优点更加清楚，下面将结合本公开实施例中附图，对本公开实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本公开一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本公开实施例的组件可以以各种不同的配置来布置和设计。因此，以下对在附图中提供的本公开的实施例的详细描述并非旨在限制要求保护的本公开的范围，而是仅仅表示本公开的选定实施例。基于本公开的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本公开保护的范围。In order to make the purposes, technical solutions and advantages of the embodiments of the present disclosure more clear, the technical solutions in the embodiments of the present disclosure will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present disclosure. Obviously, the described embodiments are only These are some, but not all, embodiments of the present disclosure. The components of the disclosed embodiments generally described and illustrated in the drawings herein may be arranged and designed in a variety of different configurations. Therefore, the following detailed description of the embodiments of the disclosure provided in the accompanying drawings is not intended to limit the scope of the disclosure as claimed, but is merely representative of selected embodiments of the disclosure. Based on the embodiments of the present disclosure, all other embodiments obtained by those skilled in the art without creative work fall within the protection scope of the present disclosure.
应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。It should be noted that like numerals and letters refer to like items in the following figures, so once an item is defined in one figure, it does not require further definition and explanation in subsequent figures.
本文中术语“和/或”，仅仅是描述一种关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，同时存在A和B，单独存在B这三种情况。另外，本文中术语“至少一种”表示多种中的任意一种或多种中的至少两种的任意组合，例如，包括A、B、C中的至少一种，可以表示包括从A、B和C构成的集合中选择的任意一个或多个元素。The term "and/or" in this paper only describes an association relationship, which means that there can be three kinds of relationships, for example, A and/or B, which can mean: the existence of A alone, the existence of A and B at the same time, the existence of B alone. a situation. In addition, the term "at least one" herein refers to any combination of any one of the plurality or at least two of the plurality, for example, including at least one of A, B, and C, and may mean including from A, B, and C. Any one or more elements selected from the set of B and C.
经研究发现，目前，各种各样的几何压缩方法被提出，包括：渐进式八叉树、预测树、动态二值分解、形状自适应小波变换、图变换、平面近似和旅行商预测等多种几何表示模型。其中的图变换，因为它对不规则离散结构上的信号具有频域稀疏表示能力，常常用于点云的属性压缩。然而，现有的图定义方法只考虑几何拓扑，不能充分反映点之间的属性相关性，限制了压缩性能。在纹理丰富的点云块中，由于具有快速变换的属性值，点与点之间的属性相关性变弱，并不能有效的利用点之间的距离体现属性相关，因此往往压缩性能较差。The research found that, at present, various geometric compression methods have been proposed, including: progressive octree, prediction tree, dynamic binary decomposition, shape adaptive wavelet transform, graph transform, plane approximation and traveling salesman prediction, etc. A geometric representation model. Among them, the graph transformation is often used for attribute compression of point clouds because of its sparse representation capability in the frequency domain for signals on irregular discrete structures. However, the existing graph definition methods only consider the geometric topology, which cannot fully reflect the attribute correlation between points, which limits the compression performance. In a point cloud with rich texture, due to the rapidly changing attribute values, the attribute correlation between points becomes weak, and the distance between points cannot be effectively used to reflect the attribute correlation, so the compression performance is often poor.
基于上述研究，本公开提供了一种点云的压缩方法、装置、电子设备及存储介质，通过获取待压缩点云；将所述待压缩点云划分为多个子点云块，其中，所述子点云块通过子图进行描述，确定所述子点云块对应的权重矩阵；根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图；确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵；根据更新后的所述权重矩阵确定所述优化图对应的拉普拉斯矩阵，根据所述拉普拉斯矩阵压缩所述待压缩点云。可以提升点云属性压缩的压缩性能与压缩效果。Based on the above research, the present disclosure provides a point cloud compression method, device, electronic device and storage medium, by obtaining the point cloud to be compressed; dividing the point cloud to be compressed into a plurality of sub-point cloud blocks, wherein the The sub-point cloud blocks are described by sub-graphs, and the weight matrix corresponding to the sub-point cloud blocks is determined; the sub-graphs are iteratively merged according to a preset cost function to determine the optimization graph corresponding to the sub-graphs; the optimization graph is determined The corresponding target adjacency matrix, the weight matrix is updated according to the target adjacency matrix; the Laplacian matrix corresponding to the optimization graph is determined according to the updated weight matrix, and the Laplacian matrix is compressed according to the Laplacian matrix. The point cloud to be compressed. It can improve the compression performance and compression effect of point cloud attribute compression.
为便于对本实施例进行理解，首先对本公开实施例所公开的一种点云的压缩方法进行详细介绍，本公开实施例所提供的点云的压缩方法的执行主体一般为具有一定计算能力的计算机设备，该计算机设备例如包括：终端设备或服务器或其它处理设备，终端设备可以为用户设备（User Equipment，UE）、移动设备、用户终端、终端、蜂窝电话、无绳电话、个人数字助理（Personal Digital Assistant，PDA）、手持设备、计算设备、车载设备、可穿戴设备等。在一些可能的实现方式中，该点云的压缩方法可以通过处理器调用存储器中存储的计算机可读指令的方式来实现。In order to facilitate the understanding of this embodiment, a method for compressing a point cloud disclosed in the embodiment of the present disclosure is first introduced in detail. The execution subject of the method for compressing a point cloud provided by the embodiment of the present disclosure is generally a computer with a certain computing capability. equipment, the computer equipment includes, for example: terminal equipment or server or other processing equipment, the terminal equipment can be user equipment (User Equipment, UE), mobile equipment, user terminal, terminal, cellular phone, cordless phone, personal digital assistant (Personal Digital Assistant) Assistant, PDA), handheld devices, computing devices, in-vehicle devices, wearable devices, etc. In some possible implementations, the method for compressing the point cloud may be implemented by the processor invoking computer-readable instructions stored in the memory.
参见图1所示，为本公开实施例提供的一种点云的压缩方法的流程图，所述方法包括步骤S101~S106，其中：Referring to FIG. 1 , which is a flowchart of a method for compressing a point cloud provided by an embodiment of the present disclosure, the method includes steps S101 to S106 , wherein:
S101、获取待压缩点云。S101. Obtain a point cloud to be compressed.
在具体实施中，可以通过测绘激光雷达、3D相机等三维扫描设备对物体表面采样所获取得到待压缩点云，待压缩点云中包含有反映被扫描物体表面特征的海量点数据集合。In a specific implementation, a point cloud to be compressed can be obtained by sampling the surface of an object with a three-dimensional scanning device such as a surveying and mapping lidar, 3D camera, etc., and the point cloud to be compressed contains a massive set of point data reflecting the surface characteristics of the scanned object.
需要说明的是，这里不对待压缩点云的来源进行限制，不论是使用三维坐标测量机所得到的点数量比较少，点与点的间距也比较大的稀疏点云，还是使用三维激光扫描仪或照相式扫描仪得到的点数量比较大并且比较密集的密集点云，均可采用本公开实施例提供的点云的压缩方法进行压缩处理。It should be noted that there is no restriction on the source of the compressed point cloud, whether it is a sparse point cloud with a relatively small number of points obtained by a 3D coordinate measuring machine and a relatively large distance between points, or a 3D laser scanner. Or a dense point cloud with a relatively large number of and dense points obtained by a photographic scanner can be compressed by using the point cloud compression method provided by the embodiment of the present disclosure.
S102、将所述待压缩点云划分为多个子点云块，其中，所述子点云块通过图进行描述，确定所述子点云块对应的权重矩阵。S102. Divide the point cloud to be compressed into a plurality of sub-point cloud blocks, wherein the sub-point cloud blocks are described by a diagram, and determine a weight matrix corresponding to the sub-point cloud blocks.
在具体实施中，针对获取到的待压缩点云进行划分处理，将待压缩点云划分为多个子点云块，并将每个子点云块初始化为独立的图，采用图的方式描述该子点云块，之后计算每个子点云块对应的权重矩阵。In the specific implementation, the obtained point cloud to be compressed is divided and processed, the point cloud to be compressed is divided into a plurality of sub-point cloud blocks, and each sub-point cloud block is initialized as an independent graph, and the sub-point cloud block is described in the form of a graph. Point cloud block, and then calculate the weight matrix corresponding to each sub-point cloud block.
这里，在将待压缩点云划分为多个子点云块的过程中，首先需要根据待压缩点云的几何结构，将待压缩点云划分为多个点云块，之后针对划分后的每个所述点云块，利用归一化分割算法将点云块过分割为多个子点云块，每个子点云块通过一个图进行描述，其中，每个子点云块由一些具有相同特征（纹理、颜色、明度等）点云节点构成。Here, in the process of dividing the point cloud to be compressed into multiple sub-point cloud blocks, it is first necessary to divide the point cloud to be compressed into multiple point cloud blocks according to the geometric structure of the point cloud to be compressed, and then for each divided point cloud For the point cloud block, the normalized segmentation algorithm is used to divide the point cloud block into multiple sub-point cloud blocks, and each sub-point cloud block is described by a graph, wherein each sub-point cloud block is composed of some sub-point cloud blocks with the same characteristics (texture). , color, brightness, etc.) point cloud nodes.
需要说明的是，在使用归一化分割算法将点云块过分割为多个子点云块的过程中，需要将点云块对应的色彩信号作为相似性度量输入至归一化分割算法中。It should be noted that, in the process of using the normalized segmentation algorithm to over-segment the point cloud block into multiple sub-point cloud blocks, the color signal corresponding to the point cloud block needs to be input into the normalized segmentation algorithm as a similarity measure.
作为一种可能的实施方式，可以利用三维KD树结构将待压缩点云划分为多个点云块，对于待压缩点云中的每一个非叶节点，可以被一个超平面划分为两个子空间，并且相应的每一个子空间又可以以相同的方式递归地通过超平面进行分割。其中，KD树的分割是沿坐标轴进行的，所有超平面都垂直于相应的坐标轴。例如沿着x轴分割，只需要给定某x值就可以确定超平面的位置，该超平面将原节点空间分割成两个子空间，其中一个子空间的所有点的x值均小于另外一个子空间中所有点的x值。As a possible implementation, the three-dimensional KD tree structure can be used to divide the point cloud to be compressed into multiple point cloud blocks, and each non-leaf node in the point cloud to be compressed can be divided into two subspaces by a hyperplane , and each corresponding subspace can be recursively divided by the hyperplane in the same way. Among them, the division of the KD tree is carried out along the coordinate axis, and all hyperplanes are perpendicular to the corresponding coordinate axis. For example, by dividing along the x-axis, the position of the hyperplane can be determined only by a given x value. The hyperplane divides the original node space into two subspaces, where the x values of all points in one subspace are smaller than those of the other subspace. The x-values of all points in space.
需要说明的是，将待压缩点云划分为点云块的方法包括但不局限于KD树，八叉树，K-means聚类算法和超体素聚类等方式，在此不做具体限制。It should be noted that the methods for dividing the point cloud to be compressed into point cloud blocks include but are not limited to KD tree, octree, K-means clustering algorithm and supervoxel clustering, etc., which are not limited here. .
进一步的，确定子点云块对应的权重矩阵的方法可以为：将所述子点云块中的每个节点转换为所述权重矩阵中的顶点；采用高斯核函数计算所述顶点之间的边权值，根据所述边权值构建所述权重矩阵。在具体实施中，点云块中顶点与顶点之间的边权值可以通过如下公式进行计算：Further, the method for determining the weight matrix corresponding to the sub-point cloud block may be: converting each node in the sub-point cloud block into a vertex in the weight matrix; using a Gaussian kernel function to calculate the relationship between the vertices. Edge weights, the weight matrix is constructed according to the edge weights. In a specific implementation, the edge weight between the vertices in the point cloud block can be calculated by the following formula:
其中，
这里，边权值可以反映两个顶点之间的信号相似性，两个顶点上的信号相似性越大，则两个顶点之间的边权值越大，并且这两个顶点之间的信号是平滑的。针对用以描述子点云块的子图，如果图上信号是平滑的，则图中能量集中在低频范围，因此很容易被压缩。Here, the edge weight can reflect the signal similarity between two vertices, the greater the signal similarity on the two vertices, the greater the edge weight between the two vertices, and the signal between the two vertices is smooth. For the sub-image used to describe the sub-point cloud, if the signal on the image is smooth, the energy in the image is concentrated in the low-frequency range, so it is easy to be compressed.
S103、采用谱聚类算法将所述图过划分为多个子图。S103, using a spectral clustering algorithm to over-divide the graph into multiple subgraphs.
在具体实施中，针对每个子点云块，将用于描述该子点云块的图采用谱聚类算法进行过划分处理，每个图均可得到对应的多个子图。In a specific implementation, for each sub-point cloud block, the graph used to describe the sub-point cloud block is over-divided by using a spectral clustering algorithm, and each graph can obtain a plurality of corresponding sub-graphs.
S104、根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图。S104. Iteratively merge the subgraphs according to a preset cost function, and determine an optimization graph corresponding to the subgraphs.
在具体实施中，针对被过分割的多个子点云块，在预设的代价函数的指导下将描述每个子图进行迭代合并，以生成对应的优化图。In a specific implementation, for a plurality of sub-point cloud blocks that are over-segmented, under the guidance of a preset cost function, each sub-graph will be described and merged iteratively to generate a corresponding optimized graph.
作为一种可能的实施方式，预设的代价函数可以通过如下公式定义：As a possible implementation, the preset cost function can be defined by the following formula:
其中，
其中，q代表量化步长；
其中，
其中，
进一步的，根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图的步骤可以如图2所示，图2为本公开实施例提供的一种子图的合并方法的流程图，所述方法包括步骤S1041~S1045，其中：Further, iteratively merges the subgraphs according to a preset cost function, and the step of determining the optimization graph corresponding to the subgraphs may be as shown in FIG. Flow chart, the method includes steps S1041-S1045, wherein:
S1041、将相邻的所述子图两两合并，生成多个子图对。S1041. Combine the adjacent sub-pictures two by two to generate a plurality of sub-picture pairs.
这里，可以采用贪心算法将相邻的两个子图两两合并，组成多个子图对。Here, a greedy algorithm can be used to combine two adjacent subgraphs to form multiple subgraph pairs.
S1042、根据所述代价函数，确定每个所述子图对对应的合并代价。S1042. Determine, according to the cost function, a merging cost corresponding to each of the sub-graph pairs.
S1043、确定全部所述子图对中每两个所述子图对之间的代价差，合并所述代价差最大的两个所述子图对，其中，所述代价差为两个所述子图对分别对应的所述合并代价之和，与两个所述子图对合并后对应的合并代价之间的差值。S1043. Determine a cost difference between every two sub-graph pairs in all the sub-graph pairs, and combine the two sub-graph pairs with the largest cost difference, wherein the cost difference is two of the sub-graph pairs The difference between the sum of the merging costs corresponding to the sub-picture pairs respectively and the merging costs corresponding to the two sub-picture pairs after merging.
在具体实施中，针对相邻子图两两合并生成的多个子图对，针对多个子图对中的每两个子图对，计算这两个子图对中每个子图对分别对应的合并代价之和，并计算这两个子图对若进行合并时对应的合并代价，将两者差值确定为两个子图对之间的代价差，筛选出代价差最大的两个子图对进行合并。In a specific implementation, for multiple sub-graph pairs generated by merging adjacent sub-graphs two by two, for every two sub-graph pairs in the multiple sub-graph pairs, calculate the sum of the merging costs corresponding to each sub-graph pair in the two sub-graph pairs respectively. and, and calculate the corresponding merging cost of these two subgraph pairs when they are merged, determine the difference between the two as the cost difference between the two subgraph pairs, and filter out the two subgraph pairs with the largest cost difference for merging.
需要说明的是，若代价差小于零，则说明两个子图对之间无法进行合并。若出现两个相同的代价差，则同时合并每个代价差对应的两个子图对。It should be noted that if the cost difference is less than zero, it means that the two subgraph pairs cannot be merged. If there are two identical cost differences, the two subgraph pairs corresponding to each cost difference are merged at the same time.
示例性的，针对子图对1、子图对2、子图对3以及子图对4，子图对1对应的合并代价值为0.8、子图对2对应的合并代价值为0.3、子图对3对应的合并代价值为0.5、子图对4对应的合并代价值为0.9。在进行合并时，以子图对1为例，若子图对1与子图对2进行合并后的合并代价值为0.4，则子图对1与子图对2之间的代价差为：0.8+0.3-0.4=0.7；若子图对1与子图对3进行合并后的合并代价值为0.1，则子图对1与子图对3之间的代价差为：0.8+0.5-0.1=1.2；若子图对1与子图对4进行合并后的合并代价值为0.7，则子图对1与子图对3之间的代价差为：0.8+0.9-0.7=1.0；由此可见子图对1与子图对3进行合并的代价差最大，因此可以将子图对1与子图对3进行合并。Exemplarily, for sub-image pair 1, sub-image pair 2, sub-image pair 3, and sub-image pair 4, the merge cost value corresponding to sub-image pair 1 is 0.8, the merge cost value corresponding to sub-image pair 2 is 0.3, and the The merge cost value corresponding to image pair 3 is 0.5, and the merge cost value corresponding to subgraph pair 4 is 0.9. When merging, take sub-image pair 1 as an example, if the combined cost of sub-image pair 1 and sub-image pair 2 is 0.4, then the cost difference between sub-image pair 1 and sub-image pair 2 is: 0.8 +0.3-0.4=0.7; if the combined cost value of sub-image pair 1 and sub-image pair 3 is 0.1, then the cost difference between sub-image pair 1 and sub-image pair 3 is: 0.8+0.5-0.1=1.2 ; If the combined cost value of sub-image pair 1 and sub-image pair 4 is 0.7, then the cost difference between sub-image pair 1 and sub-image pair 3 is: 0.8+0.9-0.7=1.0; it can be seen that the sub-image The cost difference of merging pair 1 and subgraph pair 3 is the largest, so subgraph pair 1 and subgraph pair 3 can be merged.
S1044、重复所述确定全部所述子图对中，每两个所述子图对之间的代价差，合并所述代价差最大的两个所述子图对的步骤，直至全部所述子图对之间的代价差小于零。S1044. Repeat the step of determining the cost difference between every two sub-graph pairs among all the sub-graph pairs, and merging the two sub-graph pairs with the largest cost difference, until all the sub-graph pairs are The cost difference between graph pairs is less than zero.
在具体实施过程中，可以将合并后的子图对作为新的子图对再次进行步骤S1043的处理方式，继续获取子图对之间的代价差并将代价差最大的两个子图对进行合并，如此重复进行，直至全部子图对之间的代价差均小于零，此时即可认为合并完成，合并完成后形成的新的子图即为优化图。In the specific implementation process, the merged sub-graph pair may be used as a new sub-graph pair to perform the processing method of step S1043 again, continue to obtain the cost difference between the sub-graph pairs and merge the two sub-graph pairs with the largest cost difference , and this is repeated until the cost difference between all pairs of subgraphs is less than zero, at which point the merging can be considered complete, and the new subgraph formed after the merging is completed is the optimized graph.
S1045、将合并完成后的所述子图确定为所述优化图。S1045. Determine the subgraph after the merging is completed as the optimized graph.
S105、确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵。S105. Determine a target adjacency matrix corresponding to the optimization graph, and update the weight matrix according to the target adjacency matrix.
在具体实施中，未优化的子图的顶点与权重处于全连通的状态，在采用高斯核函数计算顶点之间的边权值时，仅考虑了几何度量来定义图形权重，若成对的顶点i和j具有相似的属性值或将低权重指定给连接不同顶点的边时，子图上的属性值变化很小，可完全适用于纹理块，并且可以避免描述图形结构的额外代价。但是如果这些成对顶点跨越纹理边界，则很可能会出现权重异常值，在处理顶点之间的距离较为接近的情况时，这些跨越纹理边界的异常值将被赋予较高的权重值，但在评估它们的不同属性时，应该需要配置较低的权重值。因此，需要使用邻接矩阵作为惩罚函数的变量，经过惩罚函数的处理后更新权重矩阵来调整离群值。In the specific implementation, the vertices and weights of the unoptimized subgraph are in a fully connected state. When the Gaussian kernel function is used to calculate the edge weights between vertices, only geometric metrics are considered to define the graph weights. When i and j have similar attribute values or assign low weights to edges connecting different vertices, the attribute value changes on subgraphs are small, fully applicable to texture blocks, and the extra cost of describing the graph structure can be avoided. But if these pairs of vertices cross the texture boundary, it is very likely that there will be weight outliers, and when dealing with close distances between vertices, these outliers that cross the texture boundary will be given a higher weight value, but in When evaluating their different properties, it should be necessary to configure lower weight values. Therefore, it is necessary to use the adjacency matrix as the variable of the penalty function, and update the weight matrix to adjust the outliers after processing the penalty function.
需要说明的是，由于需要将邻接矩阵写入比特流中进行解码。为了联合优化图上的信号平滑度和邻接矩阵的编码成本，因此采用经过代价函数合并后的优化图寻找到最佳邻接矩阵，用以更新权重矩阵。It should be noted that the adjacency matrix needs to be written into the bit stream for decoding. In order to jointly optimize the signal smoothness on the graph and the coding cost of the adjacency matrix, the optimal adjacency matrix is found by using the optimized graph merged by the cost function to update the weight matrix.
具体的，可以根据所述优化图对应的连通性，将所述优化图转换为对应的目标邻接矩阵；构建以邻接矩阵作为变量，与所述权重矩阵相关联的惩罚函数，将所述目标邻接矩阵代入至所述惩罚函数，确定更新后的所述权重矩阵。Specifically, the optimization graph can be converted into a corresponding target adjacency matrix according to the corresponding connectivity of the optimization graph; a penalty function associated with the weight matrix is constructed using the adjacency matrix as a variable, and the target adjacency matrix is constructed. The matrix is substituted into the penalty function to determine the updated weight matrix.
这里，目标邻接矩阵即为用以更新权重矩阵的最佳邻接矩阵，目标邻接矩阵根据优化图内的连通性确定，即在优化图中，每个子图内的顶点是全连接的，不同的子图之间的顶点是断开的。Here, the target adjacency matrix is the best adjacency matrix used to update the weight matrix. The target adjacency matrix is determined according to the connectivity in the optimization graph, that is, in the optimization graph, the vertices in each subgraph are fully connected, and different subgraphs are fully connected. Vertices between graphs are disconnected.
作为一种可能的实施方式，可以通过以下公式定义所述惩罚函数：As a possible implementation, the penalty function can be defined by the following formula:
其中，A代表邻接矩阵；W代表权重矩阵；
S106、根据更新后的所述权重矩阵确定所述优化图对应的拉普拉斯矩阵，根据所述拉普拉斯矩阵压缩所述待压缩点云。S106. Determine a Laplacian matrix corresponding to the optimization graph according to the updated weight matrix, and compress the to-be-compressed point cloud according to the Laplacian matrix.
在具体实施中，在确定更新后的权重矩阵后，即可根据权重矩阵确定对应的度矩阵，这里，度矩阵为一个对角矩阵，其对角线上的值等于权重矩阵中每行元素之和，即连接顶点i的所有边的边权重之和。根据度矩阵以及权重矩阵，即可确定拉普拉斯矩阵，拉普拉斯矩阵中的特征向量可以反应待压缩点云中的属性信息，使用预设的压缩机根据拉普拉斯矩阵进行编码即可完成待压缩点云的压缩工作。In specific implementation, after the updated weight matrix is determined, the corresponding degree matrix can be determined according to the weight matrix. Here, the degree matrix is a diagonal matrix, and the value on the diagonal is equal to the sum of the elements of each row in the weight matrix. and, that is, the sum of the edge weights of all edges connecting vertex i. According to the degree matrix and the weight matrix, the Laplacian matrix can be determined. The eigenvectors in the Laplacian matrix can reflect the attribute information in the point cloud to be compressed, and the preset compressor is used to encode according to the Laplacian matrix. The compression work of the point cloud to be compressed can be completed.
具体的，可以基于以下公式计算拉普拉斯矩阵：Specifically, the Laplace matrix can be calculated based on the following formula:
其中，
本公开实施例提供的一种点云的压缩方法，通过获取待压缩点云；将所述待压缩点云划分为多个子点云块，其中，所述子点云块通过子图进行描述，确定所述子点云块对应的权重矩阵；根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图；确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵；根据更新后的所述权重矩阵确定所述优化图对应的拉普拉斯矩阵，根据所述拉普拉斯矩阵压缩所述待压缩点云。可以提升点云属性压缩的压缩性能与压缩效果。A method for compressing a point cloud provided by an embodiment of the present disclosure includes obtaining a point cloud to be compressed; dividing the point cloud to be compressed into a plurality of sub-point cloud blocks, wherein the sub-point cloud blocks are described by sub-graphs, Determine the weight matrix corresponding to the sub-point cloud block; iteratively merge the sub-graphs according to a preset cost function, and determine the optimization graph corresponding to the sub-graph; determine the target adjacency matrix corresponding to the optimization graph, according to the target The adjacency matrix updates the weight matrix; the Laplacian matrix corresponding to the optimization graph is determined according to the updated weight matrix, and the point cloud to be compressed is compressed according to the Laplacian matrix. It can improve the compression performance and compression effect of point cloud attribute compression.
本领域技术人员可以理解，在具体实施方式的上述方法中，各步骤的撰写顺序并不意味着严格的执行顺序而对实施过程构成任何限定，各步骤的具体执行顺序应当以其功能和可能的内在逻辑确定。Those skilled in the art can understand that in the above method of the specific implementation, the writing order of each step does not mean a strict execution order but constitutes any limitation on the implementation process, and the specific execution order of each step should be based on its function and possible Internal logic is determined.
基于同一发明构思，本公开实施例中还提供了与点云的压缩方法对应的点云的压缩装置，由于本公开实施例中的装置解决问题的原理与本公开实施例上述点云的压缩方法相似，因此装置的实施可以参见方法的实施，重复之处不再赘述。Based on the same inventive concept, the embodiment of the present disclosure also provides a point cloud compression device corresponding to the point cloud compression method, because the principle of the device in the embodiment of the present disclosure to solve the problem is the same as the above-mentioned point cloud compression method of the embodiment of the present disclosure. Similar, therefore, the implementation of the apparatus may refer to the implementation of the method, and repeated descriptions will not be repeated.
请参阅图3，图3为本公开实施例提供的一种点云的压缩装置的示意图。如图3中所示，本公开实施例提供的压缩装置300包括：Please refer to FIG. 3 , which is a schematic diagram of a point cloud compression device according to an embodiment of the present disclosure. As shown in FIG. 3 , the
获取模块310，用于获取待压缩点云。The obtaining
第一划分模块320，用于将所述待压缩点云划分为多个子点云块，其中，所述子点云块通过子图进行描述，确定所述子点云块对应的权重矩阵。The
第二划分模块330，用于采用谱聚类算法将所述图过划分为多个子图。The
合并模块340，用于根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图。The merging
更新模块350，用于确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵。The updating
压缩模块360，用于根据更新后的所述权重矩阵确定所述优化图对应的拉普拉斯矩阵，根据所述拉普拉斯矩阵压缩所述待压缩点云。A
一种可选的实施方式中，所述第一划分模块320具体用于：In an optional implementation manner, the
根据所述待压缩点云的几何结构，将所述待压缩点云划分为多个点云块；According to the geometric structure of the point cloud to be compressed, the point cloud to be compressed is divided into a plurality of point cloud blocks;
针对每个所述点云块，采用归一化分割方式将该所述点云块过分割为多个所述子点云块。For each of the point cloud blocks, the point cloud block is over-segmented into a plurality of the sub-point cloud blocks by using a normalized segmentation method.
一种可选的实施方式中，所述第一划分模块320还用于：In an optional implementation manner, the
将所述子点云块中的每个节点转换为所述权重矩阵中的顶点；converting each node in the sub-point cloud block into a vertex in the weight matrix;
采用高斯核函数计算所述顶点之间的边权值，根据所述边权值构建所述权重矩阵。A Gaussian kernel function is used to calculate edge weights between the vertices, and the weight matrix is constructed according to the edge weights.
一种可选的实施方式中，所述合并模块340具体用于：In an optional implementation manner, the merging
将相邻的所述子图两两合并，生成多个子图对；Merging the adjacent sub-graphs two by two to generate a plurality of sub-graph pairs;
根据所述代价函数，确定每个所述子图对对应的合并代价；According to the cost function, determine the merging cost corresponding to each of the sub-graph pairs;
确定全部所述子图对中每两个所述子图对之间的代价差，合并所述代价差最大的两个所述子图对，其中，所述代价差为两个所述子图对分别对应的所述合并代价之和，与两个所述子图对合并后对应的合并代价之间的差值；Determine the cost difference between every two sub-graph pairs in all the sub-graph pairs, and combine the two sub-graph pairs with the largest cost difference, wherein the cost difference is the two sub-graphs The difference between the sum of the respectively corresponding merge costs and the merge costs corresponding to the merged two sub-graph pairs;
重复所述确定全部所述子图对中，每两个所述子图对之间的代价差，合并所述代价差最大的两个所述子图对的步骤，直至全部所述子图对之间的代价差小于零；Repeat the step of determining the cost difference between every two subgraph pairs among all the subgraph pairs, and merging the two subgraph pairs with the largest cost difference, until all the subgraph pairs The cost difference between them is less than zero;
将合并完成后的所述子图确定为所述优化图。The subgraph after the merging is completed is determined as the optimized graph.
一种可选的实施方式中，所述更新模块350具体用于：In an optional implementation manner, the
根据所述优化图对应的连通性，将所述优化图转换为对应的目标邻接矩阵；Converting the optimization graph into a corresponding target adjacency matrix according to the connectivity corresponding to the optimization graph;
构建以邻接矩阵作为变量，与所述权重矩阵相关联的惩罚函数，将所述目标邻接矩阵代入至所述惩罚函数，确定更新后的所述权重矩阵。Constructing a penalty function associated with the weight matrix with an adjacency matrix as a variable, substituting the target adjacency matrix into the penalty function, and determining the updated weight matrix.
关于装置中的各模块的处理流程、以及各模块之间的交互流程的描述可以参照上述方法实施例中的相关说明，这里不再详述。For the description of the processing flow of each module in the apparatus and the interaction flow between the modules, reference may be made to the relevant descriptions in the foregoing method embodiments, which will not be described in detail here.
本公开实施例提供的一种点云的压缩装置，通过获取待压缩点云；将所述待压缩点云划分为多个子点云块，其中，所述子点云块通过子图进行描述，确定所述子点云块对应的权重矩阵；根据预设的代价函数迭代合并所述子图，确定所述子图对应的优化图；确定所述优化图对应的目标邻接矩阵，根据所述目标邻接矩阵更新所述权重矩阵；根据更新后的所述权重矩阵确定所述优化图对应的拉普拉斯矩阵，根据所述拉普拉斯矩阵压缩所述待压缩点云。可以提升点云属性压缩的压缩性能与压缩效果。An embodiment of the present disclosure provides a point cloud compression device, by acquiring the point cloud to be compressed; dividing the point cloud to be compressed into a plurality of sub point cloud blocks, wherein the sub point cloud blocks are described by sub graphs, Determine the weight matrix corresponding to the sub-point cloud block; iteratively merge the sub-graphs according to a preset cost function, and determine the optimization graph corresponding to the sub-graph; determine the target adjacency matrix corresponding to the optimization graph, according to the target The adjacency matrix updates the weight matrix; the Laplacian matrix corresponding to the optimization graph is determined according to the updated weight matrix, and the to-be-compressed point cloud is compressed according to the Laplacian matrix. It can improve the compression performance and compression effect of point cloud attribute compression.
对应于图1中的点云的压缩方法，本公开实施例还提供了一种电子设备400，如图4所示，为本公开实施例提供的电子设备400的结构示意图，包括：Corresponding to the point cloud compression method in FIG. 1 , an embodiment of the present disclosure further provides an electronic device 400 . As shown in FIG. 4 , a schematic structural diagram of the electronic device 400 provided by an embodiment of the present disclosure includes:
处理器41、存储器42、和总线43；存储器42用于存储执行指令，包括内存421和外部存储器422；这里的内存421也称内存储器，用于暂时存放处理器41中的运算数据，以及与硬盘等外部存储器422交换的数据，处理器41通过内存421与外部存储器422进行数据交换，当所述电子设备400运行时，所述处理器41与所述存储器42之间通过总线43通信，使得所述处理器41执行图1中的点云的压缩方法的步骤。The
本公开实施例还提供一种计算机可读存储介质，该计算机可读存储介质上存储有计算机程序，该计算机程序被处理器运行时执行上述方法实施例中所述的点云的压缩方法的步骤。其中，该存储介质可以是易失性或非易失的计算机可读取存储介质。Embodiments of the present disclosure further provide a computer-readable storage medium, where a computer program is stored on the computer-readable storage medium, and when the computer program is run by a processor, the steps of the point cloud compression method described in the foregoing method embodiments are executed . Wherein, the storage medium may be a volatile or non-volatile computer-readable storage medium.
本公开实施例还提供一种计算机程序产品，该计算机程序产品包括有计算机指令，所述计算机指令被处理器执行时可以执行上述方法实施例中所述的点云的压缩方法的步骤，具体可参见上述方法实施例，在此不再赘述。Embodiments of the present disclosure further provide a computer program product, where the computer program product includes computer instructions, and when the computer instructions are executed by a processor, the steps of the point cloud compression method described in the above method embodiments can be executed, specifically Refer to the above method embodiments, which are not repeated here.
其中，上述计算机程序产品可以具体通过硬件、软件或其结合的方式实现。在一个可选实施例中，所述计算机程序产品具体体现为计算机存储介质，在另一个可选实施例中，计算机程序产品具体体现为软件产品，例如软件开发包（Software Development Kit，SDK）等等。Wherein, the above-mentioned computer program product can be specifically implemented by means of hardware, software or a combination thereof. In an optional embodiment, the computer program product is embodied as a computer storage medium, and in another optional embodiment, the computer program product is embodied as a software product, such as a software development kit (Software Development Kit, SDK), etc. Wait.
所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述装置的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。在本公开所提供的几个实施例中，应该理解到，所揭露的装置和方法，可以通过其它的方式实现。以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，又例如，多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些通信接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。Those skilled in the art can clearly understand that, for the convenience and brevity of description, for the specific working process of the device described above, reference may be made to the corresponding process in the foregoing method embodiments, which will not be repeated here. In the several embodiments provided in the present disclosure, it should be understood that the disclosed apparatus and method may be implemented in other manners. The apparatus embodiments described above are only illustrative. For example, the division of the units is only a logical function division. In actual implementation, there may be other division methods. For example, multiple units or components may be combined or Can be integrated into another system, or some features can be ignored, or not implemented. On the other hand, the shown or discussed mutual coupling or direct coupling or communication connection may be through some communication interfaces, indirect coupling or communication connection of devices or units, which may be in electrical, mechanical or other forms.
所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。The units described as separate components may or may not be physically separated, and components displayed as units may or may not be physical units, that is, may be located in one place, or may be distributed to multiple network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solution in this embodiment.
另外，在本公开各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。In addition, each functional unit in each embodiment of the present disclosure may be integrated into one processing unit, or each unit may exist physically alone, or two or more units may be integrated into one unit.
所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个处理器可执行的非易失的计算机可读取存储介质中。基于这样的理解，本公开的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备（可以是个人计算机，服务器，或者网络设备等）执行本公开各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器（Read-OnlyMemory，ROM）、随机存取存储器（Random Access Memory，RAM）、磁碟或者光盘等各种可以存储程序代码的介质。The functions, if implemented in the form of software functional units and sold or used as stand-alone products, may be stored in a processor-executable non-volatile computer-readable storage medium. Based on such understanding, the technical solutions of the present disclosure can be embodied in the form of software products in essence, or the parts that contribute to the prior art or the parts of the technical solutions. The computer software products are stored in a storage medium, including Several instructions are used to cause a computer device (which may be a personal computer, a server, or a network device, etc.) to execute all or part of the steps of the methods described in various embodiments of the present disclosure. The aforementioned storage medium includes: U disk, mobile hard disk, read-only memory (Read-Only Memory, ROM), random access memory (Random Access Memory, RAM), magnetic disk or optical disk and other media that can store program codes.
最后应说明的是：以上所述实施例，仅为本公开的具体实施方式，用以说明本公开的技术方案，而非对其限制，本公开的保护范围并不局限于此，尽管参照前述实施例对本公开进行了详细的说明，本领域的普通技术人员应当理解：任何熟悉本技术领域的技术人员在本公开揭露的技术范围内，其依然可以对前述实施例所记载的技术方案进行修改或可轻易想到变化，或者对其中部分技术特征进行等同替换；而这些修改、变化或者替换，并不使相应技术方案的本质脱离本公开实施例技术方案的精神和范围，都应涵盖在本公开的保护范围之内。因此，本公开的保护范围应所述以权利要求的保护范围为准。Finally, it should be noted that the above-mentioned embodiments are only specific implementations of the present disclosure, and are used to illustrate the technical solutions of the present disclosure rather than limit them. The protection scope of the present disclosure is not limited thereto, although referring to the foregoing The embodiments describe the present disclosure in detail. Those of ordinary skill in the art should understand that: any person skilled in the art can still modify the technical solutions described in the foregoing embodiments within the technical scope disclosed by the present disclosure. Changes can be easily thought of, or equivalent replacements are made to some of the technical features; and these modifications, changes or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the embodiments of the present disclosure, and should be covered in the present disclosure. within the scope of protection. Therefore, the protection scope of the present disclosure should be based on the protection scope of the claims.
Claims (10)
Translated fromChinesePriority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210694204.4ACN114785998A (en) | 2022-06-20 | 2022-06-20 | A point cloud compression method, device, electronic device and storage medium |
| PCT/CN2022/134512WO2023245981A1 (en) | 2022-06-20 | 2022-11-25 | Point cloud compression method and apparatus, and electronic device and storage medium |
| PCT/CN2022/134513WO2023245982A1 (en) | 2022-06-20 | 2022-11-25 | Point cloud compression method and apparatus, electronic device, and storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210694204.4ACN114785998A (en) | 2022-06-20 | 2022-06-20 | A point cloud compression method, device, electronic device and storage medium |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN114785998Atrue CN114785998A (en) | 2022-07-22 |
Family
ID=82421993
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210694204.4APendingCN114785998A (en) | 2022-06-20 | 2022-06-20 | A point cloud compression method, device, electronic device and storage medium |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114785998A (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115421161A (en)* | 2022-11-03 | 2022-12-02 | 上海伯镭智能科技有限公司 | Unmanned mine car control method based on laser radar ranging |
| WO2023245981A1 (en)* | 2022-06-20 | 2023-12-28 | 北京大学深圳研究生院 | Point cloud compression method and apparatus, and electronic device and storage medium |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107403456A (en)* | 2017-07-28 | 2017-11-28 | 北京大学深圳研究生院 | A kind of point cloud genera compression method based on KD trees and optimization figure conversion |
| US20190156520A1 (en)* | 2017-11-22 | 2019-05-23 | Apple Inc. | Point cloud occupancy map compression |
| CN111133476A (en)* | 2017-09-18 | 2020-05-08 | 苹果公司 | Point cloud compression |
| US20200279404A1 (en)* | 2019-03-01 | 2020-09-03 | Tencent America LLC | Method and apparatus for point cloud compression |
| CN112214775A (en)* | 2020-10-09 | 2021-01-12 | 平安国际智慧城市科技股份有限公司 | Injection type attack method and device for graph data, medium and electronic equipment |
| CN113127697A (en)* | 2021-03-30 | 2021-07-16 | 清华大学 | Method and system for optimizing graph layout, electronic device and readable storage medium |
| CN113766229A (en)* | 2021-09-30 | 2021-12-07 | 咪咕文化科技有限公司 | Encoding method, decoding method, device, equipment and readable storage medium |
- 2022
- 2022-06-20CNCN202210694204.4Apatent/CN114785998A/enactivePending
Patent Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107403456A (en)* | 2017-07-28 | 2017-11-28 | 北京大学深圳研究生院 | A kind of point cloud genera compression method based on KD trees and optimization figure conversion |
| CN111133476A (en)* | 2017-09-18 | 2020-05-08 | 苹果公司 | Point cloud compression |
| US20190156520A1 (en)* | 2017-11-22 | 2019-05-23 | Apple Inc. | Point cloud occupancy map compression |
| US20200279404A1 (en)* | 2019-03-01 | 2020-09-03 | Tencent America LLC | Method and apparatus for point cloud compression |
| CN111641836A (en)* | 2019-03-01 | 2020-09-08 | 腾讯美国有限责任公司 | Method and device for point cloud compression, computer equipment and storage medium |
| CN112214775A (en)* | 2020-10-09 | 2021-01-12 | 平安国际智慧城市科技股份有限公司 | Injection type attack method and device for graph data, medium and electronic equipment |
| CN113127697A (en)* | 2021-03-30 | 2021-07-16 | 清华大学 | Method and system for optimizing graph layout, electronic device and readable storage medium |
| CN113766229A (en)* | 2021-09-30 | 2021-12-07 | 咪咕文化科技有限公司 | Encoding method, decoding method, device, equipment and readable storage medium |
Non-Patent Citations (1)
| Title |
|---|
| FEI SONG ET AL.: ""Rate-Distortion Optimized Graph for Point Cloud Attribute Coding"", 《IEEE SIGNAL PROCESSING LETTERS》* |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2023245981A1 (en)* | 2022-06-20 | 2023-12-28 | 北京大学深圳研究生院 | Point cloud compression method and apparatus, and electronic device and storage medium |
| CN115421161A (en)* | 2022-11-03 | 2022-12-02 | 上海伯镭智能科技有限公司 | Unmanned mine car control method based on laser radar ranging |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Zorzi et al. | Polyworld: Polygonal building extraction with graph neural networks in satellite images | |
| Berger et al. | A survey of surface reconstruction from point clouds | |
| CN109964222A (en) | System and method for processing an input point cloud with multiple points | |
| CN114219890B (en) | A three-dimensional reconstruction method, device, equipment and computer storage medium | |
| CN104574515B (en) | Method, device and terminal that a kind of three-dimensional body is rebuild | |
| CN114782564B (en) | A point cloud compression method, device, electronic device and storage medium | |
| CN110838122B (en) | Point cloud segmentation method and device and computer storage medium | |
| CN114785998A (en) | A point cloud compression method, device, electronic device and storage medium | |
| WO2025092176A1 (en) | Reconstruction method and apparatus for three-dimensional entity model, device, medium and program product | |
| Celebi et al. | An effective real-time color quantization method based on divisive hierarchical clustering | |
| WO2023082089A1 (en) | Three-dimensional reconstruction method and apparatus, device and computer storage medium | |
| Zhang et al. | Clustering and DCT based color point cloud compression | |
| CN113592987B (en) | Skeleton mapping method, device, equipment, and storage medium | |
| Tang et al. | Multi-scale surface reconstruction based on a curvature-adaptive signed distance field | |
| WO2024255426A1 (en) | Material extraction method and apparatus, device and storage medium | |
| CN115222879A (en) | A model surface reduction processing method, device, electronic device and storage medium | |
| CN115311418B (en) | A single reconstruction method and device for multi-detail tree model | |
| WO2023155778A1 (en) | Encoding method and apparatus, and device | |
| WO2023245981A1 (en) | Point cloud compression method and apparatus, and electronic device and storage medium | |
| CN117635875B (en) | Three-dimensional reconstruction method, device and terminal | |
| CN119648515A (en) | Point cloud data processing method and device, storage medium and electronic device | |
| CN117934764B (en) | Model simplifying method and system based on mesh model | |
| CN107066926A (en) | Positioned using the 3D objects of descriptor | |
| CN107016732A (en) | Positioned using the 3D objects of descriptor | |
| KR20010046823A (en) | Automatic CAD Model Synthesis From Unorganized 3-D Range Data |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication | Application publication date:20220722 |