四叉树卷积神经网络Pradeep Kumar Jayaraman、Jianhan Mei、Jianfei Cai和Jianmin Zheng新加坡南洋理工大学{pradeepkj@,jianhan001@e.,www.example.comntu.edu.sg抽象。本文提出了一种四叉树卷积神经网络(QCNN),用于有效地从表示稀疏数据的图像数据集(如手写体、钢笔笔划、手绘草图等)中学习。代替存储稀疏的草图在常规的密集张量,我们的方法分解和表示的图像作为一个线性四叉树,只细化在非空的部分的图像。对应于非零像素的实际图像数据存储在四叉树的最细节点卷积和池化操作仅限于稀疏像素,从而在计算时间和内存使用方面具有更好的效率具体而言,QCNN中的计算和存储成本在非零像素的数量上线性增长,而传统CNN的成本在像素数量上是二次的。这使得QCNN能够更快地从稀疏图像中学习,并处理高分辨率图像,而无需传统CNN面临的内存限制。我们在四个稀疏图像数据集上研究了QCNN,用于草图分类和简化任务。结果表明,QCNN可以获得相当的精度,大大减少了计算和内存成本。关键词:四叉树,神经网络,稀疏卷积1介绍卷积神经网络(CNN)是一种强大而流行的方法,用于各种任务,包括图像,视频和三维物体的分析大多数真实世界的图像数据,如自然照片或体积网格,都可以表示为密集张量,实际上,传统的CNN最初被提出来通过局部权重连接和参数共享从这些数据中最佳地学习特征。另一方面,观察到一些数据集本质上是稀疏的例如,表示自由形式的2D草图和手写的图像不幸的是,大多数传统的CNN架构,特别是对于图像,无法利用这种数据的稀疏性,并且从这种数据集学习在训练时间和存储器消耗方面都是不必要的低效随着深度网络的兴起,这一点尤其令人担忧,深度网络越来越多地用于草图简化[1]等应用中的各种高分辨率稀疏图像,以及资源稀缺的移动或嵌入式设备。2Pradeep Kumar Jayaraman、Jianhan Mei、Jianfei Cai和Jianmin Zheng在3D数据的情况下,卷积神经网络最初是通过将网格体素化为密集的3D张量来设计的[2]。然而,由于存储器和计算限制,这种方法不能扩展到高分辨率。为了缓解这一问题,最近的工作,如OctNets[3],O-CNN [4]和OGN [5],将3D网格分层分解为八叉树,并调整CNN操作以考虑特殊的八叉树结构。受这些3D作品的启发,我们在本文中提出了一种四叉树卷积神经网络(QCNN),用于有效地从稀疏的2D图像数据集中学习。虽然这些3D网络被设计用于处理由网格或点云表示的3D形状,但我们的目标是通常具有更任意结构或拓扑的一般稀疏图像。这将使所开发的方法具有广泛的应用,特别是在计算能力和存储器有限的移动设备我们的主要思想是将稀疏图像分解成四叉树,将非零图像像素存储在最细的节点中,并设计特殊的数据表示,考虑到CPU和GPU的特点。计算工作将集中在感兴趣的区域上,这避免了不提供有意义的信息的空像素的存储,从而减少了存储器消耗。我们从四叉树的最精细级别开始,并在这些节点上执行卷积以计算特征,然后通过池化对特征进行下采样并将其传播到下一个较粗糙的四叉树级别。在最终获得关于某个预定义目标和损失函数的网络输出之前,可以将该操作堆叠多次我们的方法在效率方面有几个优势。首先,由于我们仅将图像的非零像素存储在稀疏四叉树的最底层,因此存储和计算要求在非零像素的数量上是线性的,并且完全独立于图像分辨率。其次,众所周知,现代CPU和GPU在处理存储器中连续的数据方面是高效因此,我们使用线性四叉树表示,其中四叉树的每个级别通过用空间填充z阶曲线索引四叉树节点而存储为线性1D阵列。第三,我们通过考虑特殊的数据表示来适应四叉树中的需要对相同深度中的每个四叉树节点进行邻域访问的卷积经由使用Moser-de Bruijn序列的基于高效查找表的方案来实现,并且池化与将每四个子节点的最大值/平均值我们证明了QCNN在几个稀疏图像数据集的分类和草图简化的计算工作方面的效率。2相关工作2.1分层数据表示四叉树[6]和八叉树[7]分别是2D和3D空间数据的分层表示,以及二叉树的推广它们已广泛用于各种图形和图像处理应用中,诸如四叉树卷积神经网络3碰撞检测、光线跟踪和细节层次[8-10]。使用指针实现四叉树和八叉树是常见的。然而,为了表示用于CNN训练目的的数据,这是不可行的,因为CPU和GPU在处理连续阵列数据方面是有效的。线性四叉树或八叉树[11],其中树的每个级别中的2D/3D节点索引使用空间填充曲线转换为1D索引,与我们的应用更相关2.2稀疏卷积神经网络使用稀疏性可以导致更高分辨率的输入被有效地处理。然而,只有少数网络架构利用稀疏性。最初,CNN被用于通过将网格体素化为3D密集体积张量来处理3D数据由于这种表示具有很高的计算和内存成本,输入分辨率必须限制在30- 3左右。Gra- ham提出了一种用于2D图像[12]和3D体素[13]数据的CNN的稀疏版本,该版本仅在内核的感受野内的非零站点及其邻居上执行卷积然而,当大量卷积层被放置在池化层之间时,该方法变得特征膨胀问题最近由Graham和Maaten [14]通过仅在非零位点上限制卷积来处理他们的工作需要额外的簿记,以便为一个数据库的输出执行额外的簿记,以及高效的另一方面,四叉树/八叉树结构可以一次性计算,并事先清楚地定义数据的结构,与网络中的卷积或池化参数此外,由于它们的规则结构,它们可以此外,简单地使特征映射符合四叉树/八叉树结构足以显著防止特征膨胀。为了支持高分辨率3D数据,Riegler等人。[15]结合了八叉树和网格结构,并将CNN操作限制在3D形状的内部体积。虽然这与使用密集体素相比是有效的,但是存储3D表面数据的内部体积仍然是浪费的。Wang等人[4]仅考虑了八叉树表示中3D数据的表面体素,并在执行CNN操作时大幅提高了内存和计算成本。与八叉树类似,我们的工作引入了四叉树结构,用于有效地从稀疏图像数据中学习。3四叉树卷积神经网络3.1动机考虑一个一般场景,其中密集的n维张量用于表示要被馈送到卷积神经网络中的某个输入。该张量可以表示灰度图像(n= 2)、彩色图像(n= 3)、来自3D点云或表面的体素(n= 3)等。稀疏性产生于n维张量4Pradeep Kumar Jayaraman、Jianhan Mei、Jianfei Cai和Jianmin Zheng当它被用来表示低维(