过滤离群点让特征匹配更精确

 &emsp在《SIFT+KNN加持下的Android测试自动化脚本》中介绍了利用特征点来快速匹配图形的方法。但是在实际使用中，特征点匹配的结果可能存在离群点，即某些特征点由于受环境的影响会远离大多数匹配上的特征点。下图展示了在Settings界面下特征匹配时出现的离群点（红框处）

  如果特征点中存在离群点会给计算图形边界时带来误差。如上图所示，匹配相似度超过80%，也就是说程序可以认为已匹配上图形，而匹配上的边界则需要包含所有特征点，很明显这个范围实际上已超过了真正需要覆盖的范围，那么在这个范围内的所有图形都会被认为是已被识别过，从而导致错误跳过本应该被遍历的控件。

解决方案

  既然知道了离群点的影响危害（并不是所有离群点都是有害的，在某些场景下反而是离群点才是有效的数据），那么就需要过滤掉离群点。去除算法有很多，如：MAD、3∑、百分法、LOF以及CLOF算法。这里我采用MAD算法来去除离群值。

  MAD算法简单的来讲就是将所有点与中位数比较，如果相差大于门限值，则认为该值为离群值。

  这就好像在一个操场上点名，假设所有人的声音都是一样大，那么你听到的声音约大，则表示这个人离你越近，反之则越远。而你所在的地方就是一个参考位置（中位数）。

代码

  OpenCV读取的图片是以二维数组保存 因此处理时，需要按轴方向进行处理。

def __remove_outlier(points): 
    median = np.median(points, axis=0) 
    deviations = abs(points - median) 
    mad = np.median(deviations, axis=0) 
    remove_idx = np.where(deviations > mad * Global.MAD_THRESHOLD) 
    return np.delete(points, remove_idx, axis=0) 

  MAD_THRESHOLD是自定义的门限值，这里实际值为1。

  效果如下图所示：

  匹配结果完全符合预期，效果上还是不错的。