首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >zbar源码分析--技术关键点及优化策略

zbar源码分析--技术关键点及优化策略

作者头像
心跳包
发布2020-08-31 11:19:04
1.4K0
发布2020-08-31 11:19:04
举报

前面一篇文章已经说过zbar中QR的解码流程,现在这里主要介绍一些技术关键点和专注优化策略上的建议:

仿射变换:已知三个点:(x1,y1)、(x2,y2)、(x3,y3),原点为(x1,y1),映射到(0,0)、(1,0)、(0,1)。没有采用高斯消元法求解线性方程,二是直接采用最终推导公式计算相关参数。1、计算三个点组成的行列式。2、使用克拉姆法则计算h1、h2、h4、h5,h3、h6是平移参数,h3 = x1,h6=y0。为了提高效率,全部采用整数运算,在实际中坐标1放大2^res倍。

Homography变换:已知四个点:(x1,y1)、(x2,y2)、(x3,y3),(x4,y4),原点为(x1,y1),映射到(0,0)、(1,0)、(0,1),(1,1)。4个点,9个参数,在正常情况下需要采用svd(奇异值分解)计算相关参数,令h9=1,其他参数采用高斯消元法推导最终结果。为了提高效率,采用整数运算,单位1放大16384倍,也即是14个比特位。QR最大版本40有177个模块数,每个模块占据的92个数据单位,版本39有173个模块数,每个模块占据94个数据单位,也就是对版本之间至少有2个数据单位的差异,已经足够。从方形区域变换到原始图像中的位置时,需要使用在方形区域中估计的水平模块尺寸和垂直模块尺寸作为递增单位。由于homography采用的是齐次坐标系统,所以变换的结果还需要除以第三个分量。

最小二乘法拟合直线:也可以采用hough变换,但是hough变换需要计算对应参数小直线上的点数最大值,其算法复杂度(2m*180,m为图像最大尺寸),另外还需要计算相关参数。而用最小二乘法,只需要估算相关参数(复杂度为n,n为点数),另外还可以将浮点数运算改为整数运算。直线的参数形式为Ax + By + C=0,采用这个样的参数形式就可以不用考虑斜率不存在时的情况。最小二乘法拟合时B有可能为零,所以拟合的参数为A/B或B/A。

Ransac算法:用最小二乘法拟合直线的缺点是受噪声影响很大,所以需要采用ransac算法先估计集中的点,剔除噪声点。这样整个算法就是ransac算法的复杂度加上最小二乘法的复杂度。Ransac关键是要找到判断不是集中的点的判定规则,对于拟合直线来说,先取两个点,认为所有的点都在这两个点拟合的直线上,然后根据判定规则加入第三个点,第四个点等等。经过多轮的迭代,标记点数最多对应的直线。三点在一条直线的判断规则是,计算三点对应的行列式的值,在实际操作中可以设定一个阈值,小于阈值则在一条直线上,大于阈值则不共线。另外,确定迭代次数,是一个数学难点。算法缺陷,对于点数很大的情况下,迭代的次数增多,可能会影响效率。

Alignment pattern 搜索算法:一、初始化25个数据点;alignment pattern刚好是5x5模块,将理想网格中的25个模块映射至图像中,这25个作为之后读取的模版,模版的中心作为下面搜索中心点。二、读取25个点的网格数据;计算新的中心点与上面的网格中心的偏移,将偏移与模版对应点相加,读取的数据位保存在一个32位整型数据的二进制中。三、计算汉明距离;汉明距离表示的是实际模版与标准模版之间的最少不能匹配的数量,其得到的值为0表示完全匹配,例如3,表示有3个模块不能匹配。四、搜索最佳汉明距离点。以搜索中心点为中心,搜索半径为r,搜索区域为2r-1宽度的方形区域,从区域的左上角开始,顺时针 遍历方形的四边上的点,以这些点作为中心点,按照5x5的模版读取数据。找到最小汉明距离的点。中途如果汉明距离为零,终止搜索。五、调整alignment pattern中心位置。针对四步找出的最小汉明距离对应的点进行调整,相当于精确定位alignment pattern中心点。对最佳匹配模版与测试掩码模版与运算满足其对应测试掩码模版的8种情况之一,找到满足白-黑-白的中心点,对这个点坐标相对于最小汉明距离对应点的偏移加权求平均 ,满足中心为黑色模块的赋予更大的权值,否则赋予更小的权值。

Right、bottom直线的拟合方式:初始直线为一个finder pattern 的一条边的边缘点拟合的直线,如下图左边两条虚边框,底部两条虚边框。两条虚边框中其中一条起始点为find pattern中白色模块中心,另一条起始点虚边框起始点在白色外框中心(quiet边)。沿着虚线扫描,步长为半个模块宽度,每扫描一个点,寻找两条线上两个点之间是否满足白-黑-白,如果满足,则找到它们的中心点,然后将这个点加入到边缘直线中(边缘直线就是QR边界穿过边界模块中心的直线)。每当边缘点数增加1/4时,重新拟合直线,修正直线扫描的相关参数,例如扫描的步长。根据左下角find pattern 和 右上finder pattern(方向是仿射变换之后的方向)的范围确定大致扫描的范围或者遇到白色外边框则终止扫描。最后如果得到的直线上的点够数,则再次拟合直线,否则,采用仿射变换后的默认直线,right 直线平行于左上角finder pattern和左下角finder pattern 构成的直线;bottom 直线平行于左上finder pattern 和右上finder pattern 构成的直线。如下面图: 右图:找不到满足白-黑-白连续14次以上,终止扫描,见right直线扫描

Bresenham算法:参见,http://blog.csdn.net/mikedai/article/details/62885701对实现原理做了很详细的介绍。

图像二值化:阈值等于T = (m/n)-D,,其中D=3,m是(x,y)坐标w*h领域内像素值之和,如果T>f(x0,y0),则二值化的结果为0,否则为1。实现时,为了避免除法运算,T>f(x0,y0)变换为:f(x0,y0)*w*h+3 >m,乘法换成移位运算,对于m的计算先初始化h列的和,然后在计算下一行时减去窗口第一行加上窗口下一行即可,对下一列也可以采用同样的处理。算法的缺陷是引入了一些随机噪声,这没有对识别效果影响太多。相关的讨论代码中的注释很清楚: /The above algorithms are computationally expensive, and do not work as well as the simple algorithm below.Sauvola by itself does an excellent job of classifying regions outside the QR code as background, which greatly reduces the chance of false alarms.However, it also tends to over-shrink isolated black dots inside the code,making them easy to miss with even slight mis-alignment.Since the Gatos method uses Sauvola as input to its background interpolation method, it cannot possibly mark any pixels as foreground which Sauvola classified as background, and thus suffers from the same problem.The following simple adaptive threshold method does not have this problem,though it produces essentially random noise outside the QR code region. QR codes are structured well enough that this does not seem to lead to any actual false alarms in practice, and it allows many more codes to be detected and decoded successfully than the Sauvola or Gatos binarization methods./

优化策略: 现有的zbar解码程序可能需要考虑pdf417的解码,所以扫描图像时至少需要扫描2遍,还有就是可能针对纵向排布的一维条码。然而,在实际中pdf417在手机应用上很少,所以可以考虑不支持其解码。所以就没有必要扫描2次,可以采用下面的处理:一、先纵向扫描,对手机应用来说是旋转90度的,估计可能QR finder pattern的范围。二、可能漏掉横向的一维条码,所以在横向扫描17条线。如下图红色区域。

当然,这种优化也有可能会产生一些比较坏的情况,例如下图,有的红色区域严重重叠。测试图片为理想图片,红色区域部分是需要水平扫描的部分。

另一种优化方面的考虑是,隔行或隔数行扫描一行,但是这样处理会影响定位精度,然而,对于模块尺寸相对较大的应用领域,这样处理无疑是提升效率的有效手段。 在内存优化方面,可以用0、1值代替现有的0、255,这样8个像素点占据一个byte,内存使用量变为原来的1/8。 对于finder pattern中心定位精度,现有的处理方式效果是不太好的,可以考虑在已经估计finder pattern中心的基础上,重新校正中心,满足黑-白-黑-白-黑比为1:1:3:1:1,找到这条直线中心,在一这条直线中心做相同的校正。由此估计一个精确点。如果估计失败,采用原来的中心点。

最后可以去掉原有的边界检查和将一些乘法运算换成加法运算。将一些函数挑用换成宏定义或采用内联函数。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-11-05 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档