闲鱼技术-深宇
概述
回归测试是指修改了旧代码后，重新进行测试以确认修改没有引入新的错误或导致其他的代码出现错误。传统的自动化回归测试需要手动编写脚本获得页面元素的视图树，与原有的元素视图树进行比对。当功能进行频繁迭代时，测试同学维护这些视图元素验证点比较繁杂。因此在自动化回归测试过程中，直接比较代码修改前录制的页面和代码修改后回放的页面差异，可以快速定位代码产生的缺陷，从而提高测试同学的工作效率。
以闲鱼应用举例，录制和回放页面差异检测存在的一些难点包括：图像上，闲鱼页面由顶部固定区域、中间可滚动区域、底部固定区域组成，需要对页面进行版面切割，之后分别对每一个区域进行处理。另外录制和回放页面中一些图标或者图片纹理复杂的区域往往像素值分布不同，但是语义层面又是同一个物体，因此需要从语义层面进行检测识别。业务上，两张页面中间区域因为滚动带来的差异不需要检测出来，并且一些特殊的标记差异(比如一张页面某个位置有光标，另一张页面同一位置没有光标)不需要检测出来。
如上图四组录制和回放页面所示，其中每组图左边为录制页面，右边是回放页面。a)中因为中间区域的滚动带来了文字和图标的差异，b)中价格组件“¥69”右边的光标带来了差异，c)中输入框里的文字不一样，d)中“库存”那一栏的图标具有语义差别。其中a)和b)中的差异不需要检测出来，c)和d)中的差异需要检测出来。
方法
算法流程
整个算法流程如下图所示：
- 输入的录制和回放页面图像灰度化后进行版面切割，提取顶部区域、中间区域、底部区域
- 两张页面的中间滚动区域进行对齐
- 两张页面的每个区域分别进行相似度计算并排除无效的差异框
- 两张页面中分别标记最终的差异框
版面切割
闲鱼大部分的页面是由顶部固定区域、中间可滚动区域、底部固定区域组成，版面切割的目的是找到中间可滚动区域的上下边界，即将页面切割为三块区域，之后对每块区域分别进行处理。
版面切割只针对中间区域有滚动的情况，对于中间区域无滚动的情况即可用整张图进行后续处理。考虑到录制和回放页面在滚动区域上下边界处会产生明显的差异，因此分别从图像的第一行和最后一行开始进行比较，比较对应行的结构相似度指数(SSIM)，当对应行的结构相似度指数小于给定的阈值，则终止。
结构相似度指数是一种衡量两幅图像相似度的指标，其从图像组成的角度将结构信息定义为独立于亮度、对比度的反映物体结构的属性，用均值作为亮度的估计，标准差作为对比度的估计，协方差作为结构相似程度的度量。具体公式如下：
其中(x,y)分别为录制和回放图像，ux,uy,σx2,σy2,σxy分别表示图像的均值、方差和协方差，c1,c2,c3为小的正常数，避免分母为零而出现不稳定，利用参数α,β,γ调整三个成分所占的比重。在实际工程中，一般设定α=β=γ=1，以及c3=c2/2，可以将SSIM简化为：
SSIM为介于0到1之间的一个值，值越大表明两幅图越相似。下图a)b)为高2001像素、宽1125像素的录制和回放页面图像，选取SSIM阈值为0.95，计算得到的滚动区域的上边界为192，下边界为1832，如c)所示。
滚动区域对齐
对齐录制和回放图像的滚动区域后便可对比同一位置的差异，本文采用基于特征点的图像对齐方法， 即检测录制图像的一组稀疏特征点来匹配回放图像的一组稀疏特征点，通过两组特征点的匹配来计算一个转换矩阵，这个转换矩阵能变换对齐两幅图像的滚动区域。由于滚动区域只在垂直方向有位移，因此采用一般的刚性配准方法，如下式:
录制图像坐标(x,y)通过一个3x3的位移矩阵转换到回放图像坐标(x',y')。位移转换矩阵可以通过对齐两幅图像的特征点来求取。在计算机视觉中，常见的特征点描述方法有SIFT、SURF、ORB等等，本文采用ORB方法，因为相比于SIFT和SURF方法，ORB在满足足够高的准确性前提下，速度更快并且使用不受专利约束。
ORB全称是Oriented FAST and Rotated BRIEF，即是由FAST特征点检测和BRIEF特征点描述组成，并且在两者基础上加入了图像金字塔和图像重心方向等改进措施使得ORB对尺度和旋转不敏感。
滚动区域对齐的具体步骤为：
1. 输入录制和回放滚动区域。当上一步版面切割没有计算出滚动区域时，输入整幅图像的中间部分<br>
2. 检测特征点。使用ORB检测两幅图像的角点。工程实现时可以设置每幅图像最多需检测出的特征点数<br>
3. 匹配特征点。利用hamming距离来衡量两组特征点的相似性以及Brute Force暴力法尝试所有特征点来找到最佳匹配。基于匹配的特征点距离值进行排序，选取距离值较小的一部分特征点<br>
4. 计算转换矩阵。输入两组特征点坐标位置通过最小二乘求解最优的转换矩阵<br>
5. 对齐图像。应用转换矩阵将回放图像滚动区域映射对齐录制图像滚动区域<br> 下图为匹配的两组特征点，计算出来的转换矩阵中tx=0，ty=-96
相似度计算及后处理
对录制和回放页面的顶部区域、底部区域和对齐的滚动区域分别计算结构相似度SSIM(如果图像不存在滚动区域，则对整图计算SSIM)，差异的地方用矩形框标识，后续通过一定的后处理排除掉无效的差异。具体步骤如下：
差异检测。对顶部区域、底部区域和对齐的滚动区域每个像素在一定的领域范围内计算SSIM，得到同等尺寸的SSIM结果图；再对SSIM结果图用大津法得到二值化的SSIM结果图，其中有差异的地方为1，没有差异的地方为0；接着提取二值化SSIM差异部分的外接轮廓；之后再计算轮廓的最小外接矩形框。得到的结果如下红框所示：
后处理。上图红框显示的是对齐滚动区域带来的差异，通过判断每个框是否落到特定区域范围内来进行排除，这个特定区域在垂直方向上以滚动区域上边界起始，向下移动ty行结束或者以滚动区域下边界起始，向上移动ty行结束。另外对于一些噪声点带来的差异，可以通过限制差异框包含的面积进行排除。对上图使用以上两步后处理后，红框全部被排除。其他一些录制和回放图像中的特殊标记(比如光标)差异在业务层面需要排除，或者一些纹理丰富的图标/图像虽然像素层面存在差异，但语义层面属于同一类，即使SSIM计算不相似，也需要排除。
上图a)显示光标差异模式，b)显示纹理丰富的图标/图像差异模式，c)显示其他差异模式。这些差异模式是对应位置差异框绝对差得到的结果，其中a)和b)需要排除，c)需要保留。分析这几种不同模式类型，设计了一种如下图所示CNN二分类网络。图像缩放到64x64大小，然后输入到三层conv+pooling+relu的卷积结构中，后接128个节点和2个节点的全连接层，以softmax作为类别判定输出。通过分类网络便可将业务层面或像素层面的差异进行排除。
结果
一些差异检测的结果如下，其中红框标示的是在录制和回放页面中存在差异的部分。a)只有中间区域滚动带来的差异，业务上不需要检测出来； b)和c)能将页面中存在语义差异的部分检测出来并且没有误检和漏检； d)两张页面不存在语义差异，但底部有个文字区域出现了误检，分析原因是页面在没有滚动的情况下，误检区域没有上下严格对齐，导致计算的SSIM值偏小，认为此处存在差异。
总结
本文以闲鱼自动化回归测试应用举例，实现了一种版面切割、滚动区域对齐、相似度计算及后处理的录制和回放页面差异检测方法。这种方法在使用过程中达到了检出语义差异的预期，并且方法具有普适性，对其他app的自动化回归测试具有一定的参考意义。当然本方法也存在着一些不足，对于像素分布不同但语义相同的差异模式会有一部分误检，这是由于SSIM在计算相似度时对于局部像素值的变化比较敏感，未来可对页面中的文字和图片独立提取出来进行进一步的语义分析优化。
