关键词：
本文来自ICASSP2021论文《Decision Tree Based Inter Partition Termination For AV1 Encoding》
AV1引入了很多新的编码工具，导致其计算复杂度非常高。论文通过决策树在帧间预测进行块划分时预测划分方式，从而及早停止划分以减少时间。
简介
AV1的superblock的大小为128x128，在帧间预测时有10种划分方式，如Fig.1所示。
其中R表示递归划分，最小划分到4x4。在每个划分深度上都需要对所有模式进行RDO计算选择最优模式导致计算复杂度非常高。因此论文提出了使用决策树来对这个过程进行剪枝。
统计发现，划分模式NONE对non-split块的RD cost要小于split块。同时发现，相邻块间往往有相同的划分决策。
论文方法
运动补偿块MCB
在利用相邻信息时，不仅可以利用空域相邻信息还可以利用时域相邻信息。传统方法都是利用同位块作为时域相邻块，但是由于物体运动，同位块经常不是最优的参考块，尤其针对小尺寸块而言。为了解决这个问题，论文使用运动补偿块MCB。运动补偿是帧间预测必不可少的步骤，搜索到的匹配块即为MCB。
一个MCB可能不是在一个CU内，而是跨了多个CU，在这种情况下，MCB的RD cost定义为重叠CU的RD cost的加权平均，
如果MCB的80%在一个CU里，则该CU的划分状态作为MCB的划分状态。否则，如果大部分重叠的CU在该深度下选择划分，则MCB也标记为划分。
叶子节点属性选择
决策树包含一系列叶子节点，每个节点包含一个属性进行二分类。属性的选择对于分类精度有很大影响。
论文使用块的直方图的皮尔森相关系数来描述两个块的相似度，如下，
该指标绝对值越大表示相关性越高。
信息增益（IG）常被作为选择特征构建决策树的指标。IG表示按照该特征进行划分后熵的减小量。基于此本文使用下面的特征构建模型：
-
当前块、上方块、左侧块、MCB按照模式NONE进行划分后的RD cost归一化后的值RD_curr、RD_above、RD_left、RD_mcb。
-
上方块、左侧块和MCB块的划分决策Split_above、Split_left、Split_mcb。
-
当前块和上方块的相似度Corr_above，当前块和左侧块的相似度Corr_left。
表2是当块尺寸为128x128时各特征的IG。
构建决策树
论文使用著名的数据挖掘软件WEKA3.8构建决策树。从数据集objective-1-fast中取6条视频训练决策树，视频用cq-level 32编码，编码的块用于构建训练集。
训练好的决策树在AV1帧间预测过程中进行二分类，整个过程如Fig.3所示。
对于每个划分深度，在检查完划分模式NONE后，提取特征用于计算决策树的输出。如果输出为1表示要划分，编码器计算RDO，再下一个深度再进行决策树计算。否则，递归划分终止，检查在该划分深度下的其他模式。整个决策树如Fig.4所示。
实验结果
实验平台为libaom2.0.0，序列为CTC中的9条序列，720p序列使用200帧，1080p和1600p序列使用100帧，编码模式为LD，cq-level=32,37,43,50。
实验结果如表3，
实验结果显示，论文算法平均可节省23.6%的编码时间，BD-rate的损失仅为0.73%。
感兴趣的请关注微信公众号Video Coding
icassp2021：面向scc的自适应双重树结构
本文来自ICASSP2021论文《AdaptiveDualTreeStructureforScreenContentCoding》在HEVC中，CTU采用四叉树方式递归划分，同一个CTU的亮度CTB和色度CTB采用相同的划分结构即单重树结构。而对于VVC，采用帧内预测模式的CTU的亮度CTB和色度CT... 查看详情
icassp2021：基于显著性进行目标检测的vvc编码
本文来自ICASSP2021论文《SALIENCY-DRIVENVERSATILEVIDEOCODINGFORNEURALOBJECTDETECTION》论文基于VVC提出了面向显著性的编码框架用于处理机器任务。为了在编码前获取显著性区域，论文使用YOLO进行目标检测。为了验证编码对于机器处理的效... 查看详情
icassp2021：端到端的图像编码方法
本文来自ICASSP2021论文《ImageCodingForMachines:AnEnd-to-endLearnedApproach》基于深度学习的计算机视觉在图像领域应用越来越广泛，每天产生的图像数量爆发式增长，传统的图片编码器是面向人眼视觉而不是机器处理。本文提出基... 查看详情
icassp2021：通过码率限制降低me复杂度
本文来自ICASSP2021《RelyingonaRateConstrainttoReduceMotionEstimationComplexity》运动估计ME是视频编码中最耗时的部分之一，本文提出基于码率的MV候选项消除策略。研究发现最优MV通常在MVP附近，通过限制MV的码率缩小运动搜索窗口从... 查看详情
决策树与随机森林算法
决策树决策树模型是一种树形结构，基于特征对实例进行分类或回归的过程。即根据某个特征把数据分划分到若干个子区域(子树)，再对子区域递归划分，直到满足某个条件则停止划分并作为叶子节点，不满足条件则继续递归划... 查看详情
数据挖掘领域经典算法——cart算法
...有ID3，这三者的不同之处在于特征的划分：ID3：特征划分基于信息增益C4.5：特征划分基于信息增益比CART：特征划分基于基尼指数基本思想CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”... 查看详情
数据挖掘领域经典算法——cart算法
...有ID3，这三者的不同之处在于特征的划分：ID3：特征划分基于信息增益C4.5：特征划分基于信息增益比CART：特征划分基于基尼指数基本思想CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”... 查看详情
决策树算法——处理一些特殊的分类
...的功能模块。首先是创建数据集，然后计算香农熵，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分好之后，数据将被向下传递到树分支的一个节点，在这个... 查看详情
《机器学习》西瓜书习题第4章(代码片段)
...选择准则的结果.而这是绝对的过拟合.4.3 试编程实现基于信息熵进行划分选择的决策树算法,并为表(4.3)中数据生成一棵决策树.4.4 试编程实现基于基尼指数进行划分选择的决策树算法,为表(4.2)中数据生成预剪枝、后剪枝决... 查看详情
h264转av1后大小相差多少
...结构1.头信息2.编解码框架差异3.块划分结构4.帧内预测5.帧间预测6.变换7.熵编码8.滤波9.加速技术10.其他技术0.码流结构：H.264:NAL层（NetworkAbstractionLayer）：网络抽象层，主要用于网络传输。按照一定格式，对视频编码层输出的数... 查看详情
推荐系统系列3-基于决策树做推荐系统的方法
1、决策树概念 决策树是基于树的结构来进行决策的，这与人类的认知方法类似，例如：今天会下雨么？针对此问题我们首先会进行一系列的判断或者决策；今天阴天么，如果阴天，大概率会下雨；如果晴天，大概率不... 查看详情
机器学习与人工智障:决策树与随机森林
...R到决策树 1.总体流程与核心问题 (1)决策树是基于树的结构进行决策： 每个“内部节点”对应于某个属性上的“测试” 每个分支对应于该测试的一种可能结果(即该属性上的每个取值) ... 查看详情
机器学习--决策树
...这就是根本性的区别。1.2“树”的成长过程决策树基于“树”结构进行决策的，这时我们就要面临两个问题：“树”怎么长。这颗“树”长到什么时候停。弄懂了这两个问题，那么这个模型就已经建立起... 查看详情
决策树的部分理解
决策树的部分理解决策树是表示基于特征对实例进行分类的树形结构从给定的训练数据集中，依据特征选择的准则，递归的选择最优划分特征，并根据此特征将训练数据进行分割，使得各子数据集有一个更好的分类的过程决策树... 查看详情
拍乐云基于av1的实时视频系统技术实践
点击上方“LiveVideoStack”关注我们实时视频系统对于时延的要求极高，视频编码器必须满足实时性的要求。新一代视频标准AV1相比主流H.264在Rate-distortation性能的提升上是以复杂度的上升为代价的，当前应用设备的碎片化... 查看详情
基于决策树的简单验证码识别(代码片段)
原理核心思想：相似的输入必会产生相似的输出。原理：首先从训练样本矩阵中选择第一个特征进行划分，使每个子表中该特征的值全部相同(比如第一个特征是男女，则可以划分出两个子表，男表和女表)，然后再在每个子表中... 查看详情
cart决策树----基尼指数划分(代码片段)
文章目录CART决策树----基尼指数划分一.决策树算法的构建二.划分选择——基尼指数三.剪枝处理1.预剪枝2.后剪枝四.算法代码CART决策树----基尼指数划分一.决策树算法的构建一般的，一棵决策树包含一个根节点，若干个内... 查看详情
av1比特流&解码过程规范-符号和缩略语
...中定义，其他的常数定义如下:符号名值描述REFS_PER_FRAME7帧间编码可以使用的参考帧数目TOTAL_REFS_PER_FRAME8参考帧类型的数量(包括帧内类型)BLOCK_SI 查看详情