CN119478074A 三维数据编码方法、三维数据解码方法、三维数据编码装置、以及三维数据解码装置 （松下电器（美国）知识产权公司）

201980026225.52019.04.18码方法、三维数据编码装置和三维数据解码装置。本发明的三维数据编码方法将表示第1三维数据的空间的第1信息附加于所述第1三维数据据的位置信息和所述第2三维数据的位置信息进2将表示第1三维数据的空间的第1信息附加于所述第1三维将表示第2三维数据的空间的第2信息附加于所述第2三维对所述第1三维数据的位置信息和所述第2三维数据的位置信息在所述编码中，使用第1上下文对所述第1三维数据的所述位置信息将三维数据分割为所述第1三维数据和所述第在所述第1三维数据的所述编码中不参照所在所述第2三维数据的所述编码中不参照所从第1三维数据的头部取得表示所述第1三维数据的空间从第2三维数据的头部取得表示所述第2三维数据的空间对编码所述第1三维数据的位置信息而生成的第1编码数据和编码所述第2三维数据的所述第1三维数据和所述第2三维数据是从三维数据分割得到在所述第1编码数据的所述解码中不参照所在所述第2编码数据的所述解码中不参照所将表示第1三维数据的空间的第1信息附加于所述第1三维将表示第2三维数据的空间的第2信息附加于所述第2三维对所述第1三维数据的位置信息和所述第2三维数据的位置信息从第1三维数据的头部取得表示所述第1三维数据的空间3从第2三维数据的头部取得表示所述第2三维数据的空间对编码所述第1三维数据的位置信息而生成的第1编码数据和编码所述第2三维数据的4[0005]并且，关于点云的压缩，有一部分由进行点云关联的处理的公开的程序库[0014]本公开的一个方式的三维数据编码方法将表示第1三维数据的空间的第1信息附[0015]本公开的一个方式的三维数据解码方法从第1三维数据的头部取得表示所述第15信息，对编码所述第1三维数据的位置信息而生成的第1编码数据和编码所述第2三维数据[0048]图31是由实施方式6的客户端装置进行的三维数据制作处理的流程图。图32是由6[0064]图49是由实施方式7的三维数据编码装置进行的三维数据编码处理的流程图。图50是由实施方式7的三维数据解码装置进行的三维数据解码处理的流程图。图51示出了实78示有关实施方式11的使用结构信息的编码表的选择例的图。图116是表示有关实施方式11的使用属性信息的编码表的选择例的图。图117是表示有关实施方式11的使用属性信息的9[0157]图150是表示实施方式12的变形例2的对象节点及相邻节点的例子的图。图151是[0160]图154是表示实施方式13的模式信息为1的情况下的八叉树的结构例的图。图155[0167]图163是表示实施方式14的1比特占有位置以及剩余比特的例子的图。图164是用于说明实施方式14的是否应用占有位置编码的判定处理的图。图165是表示实施方式14的[0220]本公开的一个方式的三维数据编码方法将三维数据中包含的多个三维点分割为包含第1子三维点群和第2子三维点群的多个子三维点群，将表示所述第1子三维点群的空息附加于所述第2子三维点群的头部，将所述第1子三维点群和所述第2子三维点群各自编据解码装置能够选择性地对第1子三维点群以及第2子三维点群中的一方进行解码。因此，构分割为多个分支，所述多个分支包含与所述第1子三维点群对应的第1分支和与所述第2个第1三维点的属性信息和所述多个第2三维点的属性信息各自编码为能够维点的属性信息和所述多个第2三维点的属性信息中的每一个中的一方编码为能够独立解(2)所述多个第1三维点的属性信息和所述多个第2三维点的属性信息的每一述第2信息表示所述第2子三维点群的所述空间第1编码数据和所述第2编码数据通过将多个子三维点群所包含的第1子三维点群和第2子三维数据解码装置能够选择性地对第1子三维点群以及第2子三维点群中的一方进行解码。述第1编码位置数据通过对所述第1子三维点群中包含的多个第1三维点的位置信息进行编码而生成，所述第1编码属性数据通过对所述多个第1三维点的属性信息进行编码而生成，所述第2子三维点群中包含的多个第2三维点的位置信息进行编码而生成，所述第2编码属和所述第2编码位置数据生成为能够独立解码，所述所述第2编码属性数据和所述第2编码群所包含的多个第1三维点以及所述第2子三维点群所包含的多个第2三维点的位置信息以信息以及所述属性信息的所述一方，所述三维数据解码方法进一步取得第3编码数据以及多个第2三维点的所述位置信息以及所述属性信息中的另一方各自编码为具有依赖关系而维点以及所述多个第2三维点的所述位置信息以及所述属性信息的所述第2信息表示所述第2子三维点群的所述空间点群的多个子三维点群，将表示所述第1子三维点群的空间的第1信息附加于所述第1子三维点群的头部，将表示所述第2子三维点群的空间的第2信息附加于所述第2子三维点群的码数据通过将多个子三维点群所包含的第1子三维点群和第2子三维点群各自编码为能够三维数据解码装置能够选择性地对第1子三维点群以及第2子三维点群中的一方进行解码。[0252]在本实施方式中，三维空间被分割为相当于动态图像的编码中的图片的空间[0258]并且，如图1所示，作为包括多个空间的处理单位，有作为随机存取单位的GOS[0259]世界空间所占的空间区域通过GPS或纬度以及经度信息等，与地球上的绝对位置含的三维数据例如包括三维坐标等空间位置与颜色信息码的GOS。在开放式GOS中，在GOS内，比开头I_SPC的显示时刻早的一部分SPC参照不同的[0271]并且，编码装置或解码装置也可以是以解码装置大致掌握GOS并能够逐渐提高分内的GOS进行连续的编码。在一个xz平面内的所有的GOS的编码结束后，对y轴的值进行更[0286]在此，世界空间的三维空间与GPS、或纬度以及经度等地理上的绝对坐标一一对在对象的密度越高的情况下，就越将GOS的大小设定为小、将GOS内的I_SPC的间隔设定为[0289]接着，对本实施方式所涉及的三维数据编码装置的构成以及工作的流程进行说[0290]图6所示的三维数据编码装置100通过对三维数据111进行编码，来生成编码三维[0293]接着，分割部103将编码对象的区域中包含的点群数据分割为各个处理单位。在第2处理单位(SPC)的每一个进行编码。并且，三维数据编码装置100在各个第2处理单位装置100不参照与处理对象的第1处理单位(GOS)不同的第1处理单位(GOS)中包含的第2处1处理单位(GOS)中包含的处理对象的第2处理单位(SPC)，参照处理对象的第1处理单位理单位(GOS)中包含的第2处理单位(SPC)进行照其他的第2处理单位(SPC)的第1类型(I_SPC)、参照其他的一个第2处理单位(SPC)的第2[0301]接着，对本实施方式所涉及的三维数据解码装置的构成以及工作的流程进行说[0302]图8所示的三维数据解码装置200通过对编码三维数据211进行解码，来生成解码码装置200通过对分别与三维坐标对应的第1处理单位(GOS)的编码三维数据211的每一个进行解码，来生成作为随机存取单位的第1处理单位(GOS)的解码三维数据212。更具体而言，三维数据解码装置200在各个第1处理单位(GOS)对多个第2处理单位(SPC)的每一个进[0314]这样，三维数据编码装置100生成第1信息，该第1信息示出多个第1处理单位[0321]并且，元信息也可以包括点云的生成中所使用的距离传感器或摄像机等识别信[0324]编码装置或解码装置可以对彼此不同的两个以上的SPC或GOS并行进行编码或解码装置或解码装置也可以使离自身位置或行走路径远的空间的优先级比近的空间的优先[0329]并且，在汽车或机器人的自动走行时所进行的自身位置估计或物体识别等用途[0330]并且，编码装置也可以对表现室内和室外的空间形状的点云分别独立地进行编如，在动态对象的出现频度或比例超过阈值的情况下，动态对象与静态对象混在的SPC或个处理完毕的空间来编码或解码的P_SPC、参照任意的两个处理完毕的空间来编码或解码[0343]动态对象按每个对象来编码或解码，与仅包含静态对象的一个以上的空间对码装置以使I_SPC的劣化减少的方式(解码后，原本的三维数据能够更忠实地被再现)来进[0351]编码装置以及解码装置参照处理完毕的GOS内的空间，对处理对象的GOS内的P空比该SPC下层的层中包含的SPC来进行编[0356]并且，编码装置以及解码装置对彼此不同的两个以上的空间或GOS并行进行编码编码数据进行解码的三维数据解码方法以及三维数[0365]将具有一定以上的特征量的体素(VXL)定义为特征体素(FVXL)，将以FVXL构成的世界空间(WLD)定义为稀疏世界空间(SWLD)。图11示出了稀疏世界空间以及世界空间的构[0367]作为三维特征量，采用SHOT特征量(SignatureofHistogramsofOrienTations：方位直方图特征)、PFH特征量(PointFeatureHistograms：点特征直方[0368]SHOT特征量通过对VXL周边进行分割，并对基准点与被分割的区域的法线向量的(Scale_InvariantFeatureTransform：尺度不变特征转换)、SURF(SpeededUp[0373]SWLD可以按照每个特征量来生成。例如基于SHOT特征量的SWLD1和基于SIFT特征也可以将算出的各FVXL的特征量作为特征量信息来保[0374]接着，对稀疏世界空间(SWLD)的利用方法进行说明。由于SWLD仅包含特征体素[0377]如图13所示，在作为车载装置的客户端2需要作为三维地图等地图描绘的用途的[0378]如以上所示，服务器在主要需要自身位置估计这种各VXL的特征量的用途中，将[0380]接着，将要说明的是对稀疏世界空间(SWLD)与世界空间(WLD)的收发进行切换的[0381]可以按照网络带宽来对WLD或SWLD的接收进行切换。图14示出了这种情况下的工(标志或类型等)来区別。[0390]如图17所示，首先，获得部401获得作为三维空间内的点群数据的输入三维数据数据411提取特征量为阈值以上的提取三维414是包含SWLD的流的信息附加到编[0396]作为被赋予到编码三维数据413以及414的头的信息例如被定义为“world_type”[0397]并且，WLD编码部404对WLD进行编码时使用的编码方法可以与SWLD编码部405对[0400]并且，SWLD编码部405以SWLD的编码三维数据414的数据大小比WLD的编码三维数[0401]例如，SWLD提取部403再次生成提取的特征点的数量减少了[0402]并且，SWLD编码部405在不能将SWLD的编码三维数据414的数据大小比WLD的编码[0408]并且，与编码装置同样，WLD解码部503在对WLD进行解码时使用的解码方法、与[0411]具体而言，各节点以及叶节点与三维位置对应。节点1与图20所示的所有的块对止的障碍物的检测的对WLD进行了下采样的下采样世界空间(SubWLD)，并可以将SWLD与与具有预先规定的属性的物体对应的数据作为提取三维数据41等交通信息是否重要等信息。并且，属性中也可以包括车道信息(GDF：GeographicDataFiles等)中的与Feature(交叉点或道路等)的对加特征量信息的情况下，客户端也能够在接收SWLD时来算出FVXL的特征量。另外，此时，[0425]如以上所述，三维数据编码装置400从输入三维数据411(第1三维数据)提取特征[0426]据此，三维数据编码装置400生成对特征量为阈值以上的数据进行编码而得到的[0430]据此，三维数据编码装置400能够针对输入三维数据411与提取三维数据412分别[0432]据此，三维数据编码装置400能够针对邻接的数据间的相关容易变低的提取三维[0436]据此，解码装置能够容易地判断获取的编码三维数据是编码三维数据413还是编[0437]并且，三维数据编码装置400以编码三维数据414的数据量比编码三维数据413的[0438]据此，三维数据编码装置400能够使编码三维数据414的数据量比编码三维数据[0440]据此，三维数据编码装置400能够生成包括解码装置所需要的数据的编码三维数[0443]并且，客户端的状态包括客户端的通信状况(例如网络带宽)或客户端的移动速[0448]据此，三维数据解码装置500针对特征量为阈值以上的数据被编码而得到的编码数据411与提取三维数据412分别采用维数据是通过对输入三维数据411进行编码而得到的编码三维数据、还是通过对输入三维数据411中的一部分进行编码而得到的编码三维数据。三维数据解码装置500参照该标识[0454]据此，三维数据解码装置500能够容易地判断获得的编码三维数据是编码三维数[0457]并且，客户端的状态包括客户端的通信状况(例如网络带宽)或客户端的移动速[0458]并且，三维数据解码装置500进一步向服务器请求编码三维数据413以及414的一[0462]图24是本实施方式所涉及的三维数据制作装置620的方框图。该三维数据制作装[0464]首先，三维数据制作部621利用由自身车辆具备的传感器检[0466]接着，通过解码部625对接收的编码三维数据634进行解码，而获得第2三维数据数据652加工为自身车辆所请求的第6三维数据654，并通过对第6三维数据654进行编码来[0470]首先，三维数据制作部641利用由周围车辆具备的传感器检[0476]自身位置估计是通过对三维地图、与搭载于自身车辆的测距仪(LIDAR等)或立体相机等传感器所获得的自身车辆周边的三维信息(以后称为自身车辆检测三维数据)进行[0485]以下将要说明的是为了对应三维地图或自身车辆检测三维数据中的异常情况的了超声波或激光的一维数据的传感器等用于检测自身车辆周边的结构物体或移动物体的三维地图711以及自身车辆检测三维数据712的至少一方判[0491]在异常情况被检测出的情况下，应对工作决定部704决定针对异常情况的应对工第1三维位置信息包括多个随机存取单位，多个随机存取单位的每一个为一个以上的部分[0496]三维信息处理装置700在判断第1三维位置信息或第2三维位置信息为异常的情况[0497]据此，三维信息处理装置700能够检测第1三维位置信息或第2三维位置信息的异[0500]图27是示出本实施方式所涉及的三维数据制作装置810的构成例的方框图。该三[0502]数据接收部811从交通云监控或前方车辆接收三维数据831。三维数据831例如包[0503]通信部812与交通云监控或前方车辆进行通信，将数据发送请求等发送到交通云[0505]格式转换部814通过对数据接收部811接收的三维数据831进行格式转换等来生成根据自身车辆的传感器信息833而制作的三维数据834，从而能够构筑自身车辆的传感器815不能检测的前方车辆的前方的空间也包括在内的三维[0510]通信部819与交通云监控或后方车辆进行通信，将数据发送请求等发送到交通云部820通过根据三维数据构筑信息来判断能够发送的空间或已发送空间的更新有无等，从[0513]格式转换部821通过将被蓄积在三维数据蓄积部818的三维数据835中的发送区域[0514]数据发送部822将三维数据837发送到交通云监控或后方车辆。该三维数据837例的区域的三维数据831，并通过对三维数据831与基于自身车辆的传感器815检测到的传感生成自身车辆的传感器815不能检测的范[0517]并且，三维数据制作装置810能够按照来自交通云监控或后方车辆的数据发送请[0519]在实施方式5将要说明的例子是，车辆等客户端装置将三维数据发送到其他的车[0523]客户端装置902向服务器901发送由客户端装置902获得的传感器信息。传感器信行驶时想要进行自身位置估计的情况下，客户端装置902将三维地图的发送请求发送到服握到客户端装置902的移动路径以及移动速度的情况下，可以根据掌握到的移动路径和移动速度，来预测客户端装置902从客户端装置902所保持的三维地图示出的空间出来的时[0529]在客户端装置902根据传感器信息制作的三维数据与三维地图的位置对照时的误客户端装置902的周边的三维地图有发生变化的可能性，并将这一判断结果和传感器信息端装置902接收GPS等客户端装置902的位置信息。服务器901根据客户端装置902的位置信息，在判断为客户端装置902接近到服务器901所管理的三维地图中信息少的空间的情况[0533]图29是示出客户端装置902的构成例的方框图。客户端装置902从服务器901接收计客户端装置902的自身位置。并且，客户端装置902将获得的传感器信息发送到服务器[0538]格式转换部1014通过对数据接收部1011所接收的三维地图1[0540]三维数据制作部1016根据传感器信息1033，制作自身车辆的周边的三维数据1019可以对按照发送范围的指定来发送的数据[0544]通信部1020与服务器901进行通信，从服务器901接收数据发送请求(传感器信息[0546]数据发送部1022将传感器信息1037发送到服务器901。传感器信息1037例如包括[0548]服务器901具备：数据接收部1111、通信部1112、接收控制部1113、格式转换部[0549]数据接收部1111从客户端装置902接收传感器信息1037。传感器信息1037例如包[0553]三维数据制作部1116根据传感器信息1132，制作客户端装置902的周边的三维数[0554]三维数据合成部1117将基于传感器信息1132而制作的三维数据1134，与服务器1119可以对按照发送范围的指定来发送的数据[0557]通信部1120与客户端装置902进行通信，从客户端装置902接收数据发送请求(三户端装置902从服务器901接收传感器信息的发送请求(S1011)。接收了发送请求的客户端的获得时的工作的流程图。首先，服务器901向客户端装置902请求传感器信息的发送(S1021)。接着，服务器901接收按照该请求而从客户端装置902发送的传感器信息1037[0566]图34是示出服务器901进行的三维地图的发送时的工作的流程图。首先，服务器901从客户端装置902接收三维地图的发送请求(S1031)。接收了三维地图的发送请求的服[0568]服务器901利用从客户端装置902接收的传感器信息1037，来制作客户端装置902901在差分为预先决定的阈值以上的情况下，判断在客户端装置902的周边发生了某种异[0570]服务器901也可以向存在于某个空间的多个客户端装置902同时发出传感器信息接收的多个传感器信息中选择高精确度的传感[0572]例如，客户端装置902C向附近存在的客户端装置902A发出传感器信息的发送请[0574]并且也可以是，客户端装置902C向附近存在的多个客户端装置902(客户端装置902A以及客户端装置902B)发出传感器信息的发送请求。在客户端装置902A或客户端装置[0575]图36是示出服务器901以及客户端装置902的功能构成的方框图。服务器901例如[0576]客户端装置902具备：三维地图解码处理部1211、以及传感器信息压缩处理部接收三维地图1031。客户端装置902在自身位置的估计中，利用三维数据1034和三维地图[0582]并且，客户端装置902对传感器信息1033进行编码或压缩，在传感器信息的发送[0583]例如，客户端装置902具备处理器以及存储器，处理器利用存储器进行上述的处数据1134的制作中使用的传感器信息1037。据此，服务器901能够提高三维数据1134的品置1300通过对三维数据进行编码，从而[0597]分割部1301将三维数据中包含的各空间(SPC)分割为作为编码单位的多个体积三维数据编码装置1300也可以将深度信息附加到对所有时间的世界空间进行管理的头部[0606]并且，变换部1303也可以不利用一维的正交变换而可以利用二维以上的正交变[0607]例如，变换部1303将预测残差的扫描顺序与体积内的八叉树中的扫描顺序(宽度优先或深度优先等)吻合。据此，由于不必将示出预测残差的扫描顺序的信息附加到比特三维数据编码装置1300可以将是否跳过变换部1303的处理的信息(标志)置1300可以将表示各频率成分的权重的参三维数据编码装置1300也可以将示出是否跳过量化部1304的处理的信息(标志)附加到比理有关的RT信息附加到比特流。不同时刻T_LX例如是在所述某个时刻T_Cur之前的时刻T_据编码装置1300可以将与适用了时刻T_L1的空间的旋转以及平移处理有关的RT信息RT_L1移有关的RT信息RT_L0以及RT_L1这双编码装置1300将参照的多个已编码空间，通过两个参照列表(L0列表以及L1列表)来管理。可以将示出是否按照每个参照空间毎适用旋转以及平移的信息(RT适用标志等)附加到比数据编码装置1300在ICP错误值为预先规定的一定值以下的情况下，判断为不需要进行旋[0628]MaxRefSpc_l1示出参照列表L1内包含的参照空间数。RT_flag_l1[i]是参照列表[0630]帧间预测部1311利用被存放在参照空间存储器1310的已[0632]并且，帧间预测部1311在从ICP的结果得到的ICP错误值比预先规定的第1阈值小[0637]预测控制部1312对采用帧内预测以及帧间预测的哪一个来编码编码对象体积进放到参照体积存储器1405或参照空间存储[0644]帧内预测部1406利用参照体积存储器1405内的参照体积以及被附加到比特流的[0645]帧间预测部1408利用参照空间存储器1407内的参照空间以及被附加到比特流的是三维数据编码装置1300进行的帧间预包含的编码对象体积与位置信息的差为最小的体积，将得到的体积作为预测体积来使用。[0653]并且可以是，三维数据编码装置1300对参照三维数据中包含的三维点的位置信到的三维点的位置信息，以比第1单位细小的第2单位(例如体积)来适用第2旋转以及平移置信息的编码与三维点的属性信息的编码之中1400针对参照三维数据中包含的三维点的位置信息不适用旋转以及平[0671]另外，三维数据解码装置1400可以以第1单位(例如空间)来进行旋转以及平移处得到的三维点的位置信息，以比第1单位细小的第2单位(例如体积)来适用第2旋转以及平坐标信息被用于提高子地图的编码效率。该子坐标信息示出子地图的子坐标(sub_coordinate)。子坐标是以基准坐标(referencecoordinate)为基准的子地图的坐标。另[0694]首先，客户端1502接收从服务器1501发送的子地图的编码比特流和基准坐标(S1511)。接着，客户端1502通过对编码比特流进行解码，从而获得子地图和子坐标信息coordinate_x表示子坐标的x坐标。sub_coordinate_y表示子坐标的y坐标。sub_[0698]三维数据解码装置针对作为第i个的点云的全体坐标的point_cloud[i]_x、个的点云的全体坐标的x坐标。point_cloud[i]_y是第i个的点云的全体坐标的y坐标。point_cloud[i]_z是第i个的点云的全体[0705]图58示出了进行这种切换的情况下的子地图的句法例子。图58所示的coding_点云所具有的颜色信息的平均值设定为子颜色信息(sub_color)，对各点云的颜色信息与的句法与图58所示的句法基本相同，各信息为体积单位的信息之处不同。具体而言，diff_x[i]表示体积内的第i个点云的x坐标与子坐标的x坐标的差分值。diff_y[i]表示体积内的第i个点云的y坐标与子坐标的y坐标的差分值。diff_z[i]表示体积内的第i个点云三维数据中包含的多个空间单位(例如子地图、空间或体积)中的对象空间单位进行编码位的情况下(S1532的“是”)，三维数据解码装置以八叉树结构来解码对象空间单位[0740]在由上述信息示出不以八叉树结构对所述对象空间单位进行解码的情况下(S1532的“否”)，三维数据解码装置以与八叉树结构不同的方式来解码对象空间单位对象空间单位中包含的三维点的坐标的差分进串称为占用率代码(Occupancycode)。将通过位置编码得到的比特串称为位置代码点所具有的8个子节点或叶节点是否分别包含三维点的信息用8比特的占用率代码来表示。[0751]图72是表示图71所示的四叉树结构中的表示重要三维点A及C的占用率代码以及占用率编码中的哪一个进行了编码的信息附加在比特流的头此，三维数据编码装置对从该第3级别到最深共用节点的第2级别以及第3级别适用占用率[0777]图78是表示通过包含重要三维点的情况下的混合编码而生成的比特流的一个例非重要三维点的编码数据被存放在重要三维点的编[0782]这样，三维数据编码装置将原本的树结构分割为包含重要三维点的第1树结构和[0791]图83所示的isleaf是表示对象节点是否为叶节点的标志。isleaf＝1表示对象节示所适用的编码类型的编码类型信息。coding_type＝00表示适用了位置编码，coding_[0796]idx[i][j]表示从对象节点到三维子节点与通过将与对象节点对应的对象块在空间上进行8分割而得到的8个子块的每一个code是对象节点的占用率代码。在八叉树的情况下，occupancy_code是例如比特串装置可以将表示最大深度的信息附加在coding_type成为占用率编码的最初的节点，也可[0802]此外，三维数据编码装置也可以对通过上述方法生成的各节点的coding_type、特流中附加用于切换占用率编码和位置编码的信息树以及十六叉树等N叉树(N为2以上的整数)或者其他的树结构[0806]首先，三维数据编码装置用八叉树结构表现三维数据中包含的多个三维点着，三维数据编码装置通过对对象节点进行节点编码处理，生成八叉树结构的比特串(S1603)。接着，三维数据编码装置通过对所生成的比特串进行熵编码而生成比特流维数据编码装置将编码类型(coding_type[0819]图87是节点解码处理(S1632)的流程图。首先，三维数据解码装置从比特串获得得编码类型(coding_type)(S1643)。三维数据解码装置判断编码类型是否为占用率编码[0828]如以上所述，本实施方式的三维数据编码装置生成以第1方式(位置编码)表示三维数据中包含的多个三维点的N(N为2以上的整数)叉树结构的第1信息，生成包含第1信息息包含与N叉树结构中的多个层的每一个对应的索引(idx)。各索引表示属于对应的层的N[0835]例如，三维数据编码装置在多个三维点的数量为预先规[0839]另外，本实施方式的三维数据解码装置从比特流获得以第1方式(位置编码)表示三维数据中包含的多个三维点的N(N为2以上的整数)叉树结构的第1信息(位置代码)。第1信息包含与多个三维点的每一个对应的三维点信息包含多个与属于N叉树结构中的多个层的多个子块的每一个对应，并表示在对应的子块中[0853]三维数据编码装置在树结构的某层(layer)中，计算各分支中包含的三维点的数[0854]图89例如是表示层5的各分支所具有的有效叶节点的数量(3Dpoints)的例子的基于各分支中包含的三维点的数量计算的三维点支的子三维点群B(稀疏的三维点群)的例置编码)的例子，但例如三维数据编码装置也可以对子三维点群A和子三维点群B使用相同生成编码数据(S1703)。另外，三维数据编码装置也可以将子三维点群B通过手法A进行编[0868]头部信息也可以包含表示各子三维点群中包含的三维点的数量和编码方法的信[0869]头部信息也可以包含用来识别各子三维点群的编码数据的开始位置或末端位置三维数据编码装置也可以将子三维点群A和子三维点群三维数据解码装置从所获得的比特流中将子三维点群A的编码数据与子三维点群B的编码到子三维点群B(S1713)。接着，三维数据解码装置将子三维点群A与子三维点群B结合三维数据解码装置也可以将子三维点群A和子三维点群[0882]接着，三维数据编码装置通过将在步骤S1722中得到的稀疏的三维点群的编码数据与在步骤S1723中得到的稠密的三维点群的[0885]头部信息也可以包含表示各子三维点群中包含的三维点的数量和编码方法的信[0886]头部信息也可以包含用来识别各子三维点群的编码数据的开始位置或末端位置[0887]此外，三维数据编码装置也可以将稀疏的三维点群和稠密的三维点群并行地编三维数据解码装置从所获得的比特流分离为稀疏的三维点群的编码数据和稠密的三维点据解码装置使用头部信息从比特流分离稀疏的三维点群和稠密的三维点群的[0893]另外，三维数据解码装置也可以将稀疏的三维点群和稠密的三维点群并行地解点群是LiDAR数据的重要区域中包含的三维点群的情况下，三维数据解码装置将该重要区据编码装置通过将在步骤S1742中得到的稀疏的三维点群的编码数据与在步骤S1743中得解码装置通过将稠密的三维点群的编码数据解码而得到稠密的三维点群的解码数据三维点群的解码数据与在步骤S1753中得到的稀疏的三维点群的解码数据结合而生成三维[0899]此外，三维数据编码装置也可以将稠密的三维点群和稀疏的三维点群的一方编[0900]此外，三维数据解码装置也可以将稠密的三维点群和稀疏的三维点群的一方解[0902]接着，三维数据编码装置将处理对象的位置从八叉树的根节点移动到层L的开头[0903]接着，三维数据编码装置将层L的处理对象的分支的有效叶节点数进行计数据编码装置将处理对象的分支作为稠密的分支，向稠密的三维点群登记(S1765)。另一方据编码装置将层L和阈值TH的组设定多个样式，使用各组生成稠密的三维点群和稀疏的三树结构中包含的多个三维点的总数的一半的值设定为维点群这两种的例子，但三维数据编码装置也可以将输入三维点群分类为3种以上的三维点群。例如，三维数据编码装置在处理对象的分支的有效叶节点数是阈值TH1以上的情况三维数据编码装置在处理对象的分支的有效叶节点数小于第2阈值TH2且为第3阈值TH3以[0909]图101所示的num_sub_pc表示子三维点群的数量。numPoint[i]表示第i个子三维点群之中包含的三维点的数量。coding_type[i]是表示应用于第i个子三维点群的编码类type_01_data是应用了coding_type为01的编码类型的编码数据，例如是应用了占用率编没有用于编码数据的固定的比特串。由此，三维数据解码装置通过从比特流中搜索例如稀疏的分支的层的层信息和表示稀疏的分支是该层的第几个分支的分支信息编码为稀疏三维数据编码装置判定是否在步骤S1771中生成的全部的稠密的分支的编码已完成置选择下一个稠密的分支(S1774)，通过将所选择的稠密的分支编码而生成编码数据置选择下一个稀疏的分支(S1777)，通过将所选择的稀疏的分支编码而生成编码数据码装置将在步骤S1772及S1775中生成的编码数[0928]接着，三维数据解码装置判定是否在步骤S1781中提取出的全部的稠密的分支的编码数据的解码已完成(S1783)。在全部的稠密的分支的编码数据的解码没有完成的情况三维数据解码装置通过将稀疏的分支的编码数据解码，得到稀疏的分支的解码数据[0930]接着，三维数据解码装置判定是否在步骤S1781中提取出的全部的稀疏的分支的编码数据的解码已完成(S1786)。在全部的稀疏的分支的编码数据的解码没有完成的情况[0931]另一方面，在全部的稀疏的分支的编码数据的解码已完成的情况下(S1786的点群(S1788)。[0940]layer_id[i]表示第i个子三维点群所属的层号。branch_id[i]表示第i个子三维[0941]layer_id[i]及branch_id[i]是表示例如八叉树的分支的场所的层信息及分支信[0945]首先，三维数据编码装置生成三维数据中包含的多个三维点的N(N为2以上的整编码处理进行编码，从而生成第1编码数据，第1层是N叉树结构中包含的多个层的某一个[0947]此外，三维数据编码装置将以第1层中包含的与第1节点不同的第2节点为根节点的第2分支通过与第1编码处理不同的第2编码处理进行编码，从而生成第2编码数据[0949]由此，三维数据编码装置能够应用适合于N叉树结构中包含的各个分支的编码处[0951]例如，第1编码数据包含以第1方式表示第1分支中包含的多个第1三维点的第一N叉树结构的第1信息。第2编码数据包含以第2方式表示第2分支中包含的多个第2三维点的[0953]例如，在第2编码处理中使用的量化参数与在第1编码处理中使用的量化参数不节点为根节点的第1分支被编码而得到的，所述第1层是多个三维点的N(N为2以上的整数)[0962]此外，三维数据解码装置通过将第2编码数据用与第1解码处理不同的第2解码处[0963]接着，三维数据解码装置使用第1解码数据和第2解码数据，复原多个三维点[0966]例如，第1编码数据包含以第1方式表示第1分支中包含的多个第1三维点的第一N叉树结构的第1信息。第2编码数据包含以第2方式表示第2分支中包含的多个第2三维点的[0968]例如，在第2解码处理中使用的量化参数与在第1解码处理中使用的量化参数不[0976]图110是表示四叉树的树结构的一例的图。图111是表示图110所示的树结构的占[0977]有关本实施方式的三维数据编码装置将八叉树的8比特的占用率代码进行熵编[0982]图113是表示几何信息的一例的图。几何信息包括对象节点的多个相邻节点各自包含三维点(occupiedornon－occupied)的信息来计算对象节点的周边的几何学上的配象节点不同的时间的相同位置或其空间上的转后的形状。因此，三维数据编码装置判断为这些几何样式的几何类似性[0984]图114是表示图113所示的(1)～(4)的几何样式中的对象节点的占用率代码和在[0986]接着，对使用树结构的结构信息(structureinformation)的自适应的熵[0991]使用三维点的属性信息，能够将具有类似的几何学上的配置的三维点进行分例如，作为三维点所具有的共通的属性信息，可以使用表示各三维点的方向的法线向量数据编码装置也可以根据对象节点所属的对象物的分类来选择编码表。图117是用来说明方式的三维数据编码装置生成的比特流的结构例的图。如图118所示，比特流包括编码表[0999]三维数据编码装置使用对象节点的几何信息、结构信息维数据解码装置能够使用附加在头中的编码表的信息将占用[1004]接着，表示比特流及编码表的其他例。图121是表示比特流的变形例的结构例的率代码中包含的每1个比特表示与该1个比特对应的上下文模型及上下[1008]具体而言，占用率代码的各比特与将对应于对象节点的空间块分割后的子块对[1011]图125是包括使用几何信息的自适应的熵编码处理的三维数据编码处理的流程[1018]三维数据编码装置使用对象节点的几何信息、结构信息[1020]图126是包括使用几何信息的自适应的熵解码处理的三维数据解码处理的流程解码装置在结束了单位长度的处理的情况下，将边界框的位置作为三维点和位置来保存。[1027]图127是包括使用结构信息的自适应的熵编码处理的三维数据编码处理的流程[1033]图128是包括使用结构信息的自适应的熵解码处理的三维数据解码处理的流程[1039]图129是包括使用属性信息的自适应的熵编码处理的三维数据编码处理的流程[1045]图130是包括使用属性信息的自适应的熵解码处理的三维数据解码处理的流程[1052]三维数据编码装置也可以作为几何信息而使用例如树结构的几何组的信息来切维数据编码装置选择编码表0(S1962)。在由几何信息表示的几何组是几何组1的情况下 信息表示的几何组是几何组2的情况下使用编码表2等，根据几何组的值进一步切换编码[1056]另外，三维数据解码装置中的使用几何信息的编码表的选择处理(S1915)也与上[1058]三维数据编码装置也可以作为结构信息而使用例如树结构的层的信息来切换在编码表1(S1974)。在其以外的情况下(S1973的“否”)，三维数据编码装置选择编码表2[1061]此外，三维数据解码装置中的使用结构信息的编码表的选择处理(S1935)也与上[1063]三维数据编码装置也可以作为属性信息而使用例如对象节点所属的对象物的信三维数据编码装置选择编码表0(S1982)。在对象节点的法线向量属于法线向量群1的情况据编码装置使用从多个编码表中选择的编码表将表示三维数据中包含的多个三维点的N(N比特的信息。N比特的信息包括N个表示在对应的节点的N个子节点各自中是否存在三维点装置在熵编码中，使用在所选择的编码表中对该比特设置的上下文将N比特的信息的各比[1088]图136以及图137是表示本实施方式所涉及的参照关系的图，图136是在八叉树结[1097]在此，CodingTable表示对象节点的占用率代码用的编码表，表示值0～7的任一数据编码装置也可以使用父节点的占用率代码中所示式所涉及的三维数据编码装置2100的框图。图141所示的三维数据编码装置2100具备八叉[1103]编码表选择部2103使用由几何信息计算部2102算出的相选择对象节点的占用率代码的熵编码中使用的编码表。熵编码部2104使用所选择的编码[1106]几何信息计算部2112获得表示对象节点的相邻参照节点是否为占有的占有信[1107]编码表选择部2113使用由几何信息计算部2112算出的相[1108]比特流中包含的占用率代码(8比特)的各比特表示在8个小空间A(节点A0～节点进行编码这样的处理直至节点不能分割(S2107)。即，递归地重复步骤S2102～S2106的处对象节点的父节点的占用率代码算出(获得)对象节点的相邻参照节点的占有信息码装置通过参照octree_scan_order，能够知道比特流以宽度优先以及深度优先的哪一个据解码装置能够从比特流的头部获得表示是否禁止[1129]此时，假如相邻节点是例如图149的相邻节点X0那样为不能参照(禁止参照)的情编码装置许可参照多个相邻节点中的、父节点与对象节点的父节点相同的第1节点的子节[1133]三维数据编码装置也可以通过例如下式算出对对象节点2的占用率代码进行熵编[1136]此外，三维数据编码装置也可以根据父节点内的对象节点2的节点位置来变更编点的N(N为2以上的整数)叉树结构中包含的对象节点的信息(例如占用率代码)进行编码。据编码装置由于不参照多个相邻节点中的、父节点与对象节点的父节点不同的第2节点的[1140]例如，三维数据编码装置进一步决定是否禁止参照第2节点的信息，在上述编码占有信息)，第2节点的信息是表示在第2节点是否存在三维点的信息(第2节点的占有信的N(N为2以上的整数)叉树结构中包含的对据解码装置由于不参照多个相邻节点中的、父节点与对象节点的父节点不同的第2节点的[1151]例如，三维数据解码装置进一步从比特流获得表示是否禁止参照第2节点的信息占有信息)，第2节点的信息是表示在第2节点是否存在三维点的信息(第2节点的占有信(PointCloud)进行编码的情况下，反复分割并进行编码直到八叉树中包含的叶节点具有1信息为假的情况下(八叉树的各叶节点包含1个以图61～图67所记载的那样表示叶节点所包含的三维点的相对坐标等的信息、或者这两者。装置能够使用叶节点信息正确地复原叶节点内[1164]图153是表示本实施方式的比特流的头部信息的句法例的图。该头部信息例如是点是指八叉树中包含的所有叶节点包含1个三维点(即，不存在包含2个以上的三维点的叶[1165]另外，八叉树的各叶节点包含1个以上的三维点意味着八叉树中包含的多个叶节节点包含1个三维点的情况下，三维数据编码装置也可以将模式信息(single_point_per_流的头部的例子，但也可以不将模式信息附加到头部，而是根据标准或标准的档次[1172]图156所示的num_point_per_leaf是叶节点信息，表示叶节点中包含的三维点的point_per_leaf1的情况下不被也可以将叶节点所包含的三维点的位置信息作为叶节点[1177]另外，在将同一叶节点内的2个以上的三维点的位置信息作为叶节点信息分别编[1178]另外，三维数据编码装置也可以将同一叶节点内的M个以上的三维点的位置信息编码装置也可以通过例如平均化等将M个以上的三维点的M个以上的属性信息舍入而生成N数据编码装置决定是以八叉树的各叶节点包含1个三维点的方式进行编码，还是以八叉树相同的三维点的情况下，决定为以八叉树的各叶节点包含1个以上的三维点的方式进行编[1180]三维数据编码装置在决定为以八叉树的各叶节点包含1个三维点的方式进行编码[1181]在决定以八叉树的各叶节点包含1个以上的三维点的方式进行编码的情况下以八叉树的各叶节点包含1个三维点的方式生成八叉树，在根据模式信息表示八叉树的各对表示叶节点所包含的三维点的数量等的叶置不对表示叶节点所包含的三维点的数量等的叶节维数据解码装置对比特流中包含的头部内的模式信息(single_point_per_leaf)进行解码装置对表示叶节点所包含的三维点的数量等的置不对表示叶节点所包含的三维点的数量等的叶节[1193]以下，对本实施方式的三维数据编码装置以及三维数据解码装置的结构进行说方式进行编码，并生成表示决定的结果的模式信息。即，模式决定部2202设定single_部2203将叶节点信息(single_point_per_lea[1198]模式信息解码部2212根据比特流的头部信息对模式信息(single_point_per_且使用解码后的占用率代码和叶节点信息来维数据编码装置将第1信息(模式信息)附加到比特流装置以叶节点包含1个三维点的方式生成N叉树结构(S2223)，对该N叉树结构进行编码[1203]由此，三维数据编码装置能够选择性地使用叶节点包含1个三维点的树结构和叶置将与叶节点相关的第2信息(叶节点信息)附加到比特流，在由第1信息表示叶节点包含1息也可以表示叶节点所包含的2个以上的三维结构进行解码是指例如基于根据在叶节点中仅包含1个三维点这样的前提而生成的规则，结构进行解码是指例如基于根据有时在叶节点中包含2个以上的三维点的前提而生成的规[1215]由此，三维数据解码装置能够选择性地使用叶节点包含1个三维点的树结构和叶码装置在由第1信息表示多个叶节点包含2个以上的三维点的情况下，以多个叶节点包含2息也可以表示叶节点所包含的2个以上的三维[1226]在本实施方式中，三维数据编码装置用1比特占有位置(1bitoccupiedposition)和剩余比特(remainingbit)来表现占用率代码，分别用不同的方法对1比特占[1227]1比特占有位置表示在从左扫描了包含在占用率代码中的各比特的情况下最初出[1228]剩余比特表示与占用率代码的1比特占有位置相比靠右侧的比特串。剩余比特是[1229]图163是表示由占用率代码生成的1比特占有位置和剩余比特的例子的图。在图比特串的1比特占有位置1比特1比特地进行二进制编码(二值的算术编码)。三维数据编码[1235]此外，1比特占有位置的定义也可以是在从右扫描占用率代码的各比特的情况下[1238]也可以是，三维数据编码装置判定编码对象的对象占用率代码是1比特占有代码率代码是否是1比特占有代码来高效地判定对象占用率代码是1比特占有代码的可能性是[1243]如图165所示，节点信息包括1bit_occupied_position和remaining_bit。1bit_所以如图165所示，remaining_bit也可以不被编码。另外，三维数据编码装置也可以将编码装置也可以使用编码表来对根据remaining_bit的比特串计算出的十进制数的值进行之外，还将扫描比特串而第2个占1的位置作为例如2比特占有位置(2bit_occupied_以是，三维数据编码装置将扫描比特串而第N个占1的位置作为例如N比特占有位置(Nbit_[1247]在本实施方式中，三维数据编码装置在对象节点的占用率代码为1比特占有代码置也可以在通过将0和1的发生概率固定为50％而跳过发生概率的计算的旁路模式下对1比[1252]另外，三维数据编码装置也可以在对象节点的占用率代码中包含的值1的比特数[1254]首先，三维数据编码装置判定对象节点的父节点的占用率代码是否是1比特占有[1259]在不满足Diff＞_1的情况下(S2313的“否”)，三维数据编码装置对a设定a_1[1261]接着，三维数据编码装置计算剩余比特(S2306)，对剩余比特进行二进制编码[1263]接着，三维数据编码装置判定是否满足b＜0(S2327)。在不满足b＜0的情况下[1265]首先，三维数据解码装置判定父节点的占用率代码是否是1比特占有代码装置进行对通过占有位置编码而被编码的编码数据进行于1比特占有位置来计算占用率代码的一部分(从占用率代码的左端到1比特占有位置)从比特流中解码1比特占有位置(S2334)，使用1比特占有位置来计算占用率代码的一部分[1273]接着，三维数据解码装置判定是否满足b＜0(S2356)。在不满足b＜0的情况下维点的N(N是2以上的整数)叉树结构中包含的对象节点的信息、即表示属于对象节点的子有位置)的位置信息，和(ii)所述比特串中的所述扫描顺序中的比所述开头位置靠后的比[1284]例如，三维数据编码装置具有对所述位置信息和所述剩余比特进行编码的第1模式(例如占有位置编码)和对所述比特串进码装置从比特流中解码三维数据所包含的多个三维点的N(N为2以上的整数)叉树结构所包含的对象节点的信息，即(i)在以预先规定的扫描顺序对表示属于所述对象节点的子节点各自是否存在三维点的N比特的信息的比特串(例如占用率代码)进行了扫描的情况下，表示最初出现预先规定的代码的所述比特串中的[1300]在本实施方式中，三维数据编码装置对所输入的三维点群(PointCloud)的三维置将用于控制将该重复点作为八叉树的叶节点信息如何进行编码的信息附加到头部。由包括如图174所示的点A以及点B那样原本的三维位置处于接近的位置，三维位置的信息被[1301]例如，三维数据编码装置将作为控制是否合并重复点的标志的重复点合并标志(MergeDuplicatedPointFlag)附加到头部信息。图175是示意性地表示与重复点合并标志[1305]在重复点合并标志为0的情况下，三维数据编码装置将重复点的信息作为叶节点置也可以在点A与点B的三维位置之差为预先规定的阈值α以下的情况下，将点A与点B视为[1314]另外，三维数据编码装置也可以使用点A的三维位置作为重复点的三维位置。或编码装置也可以使用根据点A的三维位置和点B的三维位置计算出的三维位置作为重复点[1317]另外，三维数据编码装置也可以将合并后的叶节点内的点的数量(N)附加到头部[1319]接着，对重复点合并标志的句法例进行说明。图176是表示头部信息的句法例的