2021SC@SDUSC
目录
一、Image Scanner
二、小波阈值去噪
图像噪声
理论依据
去噪过程
阈值去噪
硬阈值去噪
软阈值去噪
阈值选择
三、scanner.c中的阈值计算
四、边界处理
五、更新边界
线性插值算法
算法内容
插值在图像处理中的应用
六、总结
一、Image Scanner
Image Scanner是ZBar实现对读入图像进行扫描的功能模块。Image Scanner的核心主要由img_scanner.c和scanner.c两个文件组成。
其中,img_scanner.c中的核心函数是zbar_scan_image(),而scanner.c中的核心函数是zbar_scan_y()。经过简单分析得到,zbar_scan_image主要负责ZBar对读入图像的扫描工作,函数主要根据设定的扫描密度(density)控制像素点读取(按Z字形读取,这也是ZBar名称的由来),scanner.c文件内的zbar_scan_y()来完成滤波,阈值,确定边缘,转化成宽度流。
上次博客分析了scanner.c中的ZBar扫描器的内存分配以及图像的边界判断(包括差分的运算和应用),这次博客继续分析关于阈值的计算等内容。
二、小波阈值去噪
图像噪声
噪声可以理解为“妨碍人们感觉器官对所接收的信源信息理解的因素”。
例如,一幅黑白图片,其平面亮度分布假定为f(x,y),那么对其接收起干扰作用的亮度分布R(x,y),即可称为图像噪声。
但是,噪声在理论上可以定义为“不可预测,只能用概率统计方法来认识的随机误差”。因此将图像噪声看成是多维随机过程是合适的,因而描述噪声的方法完全可以借用随机过程的描述,即用其概率分布函数和概率密度分布函数。
理论依据
图像和噪声在经过小波变换后具有不同的特性,因为将含噪信号在各尺度上进行小波分解后,图像的能量主要集中在低分辨率子带上,而噪声信号的能量主要分布在各个高频子带上。
原始图像信息的小波系数绝对值较大,噪声信息小波系数的绝对值较小,在这种前提下,我们可以通过设定一个合适的阈值门限,采用阈值办法保留有用信号系数。而且这个去噪的过程其实也就是对高频的小波系数进行处理的过程。
去噪过程
如下图:
阈值去噪
硬阈值去噪
当小波系数小于某个临界阈值时,认为当时的小波系数主要是由噪声引起的,应该舍弃;当小波系数大于这个临界阈值时,认为这时的小波系数主要是由信号引起的,应该把小波系数直接保留下来。
软阈值去噪
进行比较含噪信号的小波系数与选定的阈值大小,大于阈值的点收缩为该点值与阈值的差值,小于阈值相反数的点收缩为该点值与阈值的和,绝对值小于等于阈值的点为0。
阈值选择
阈值的确定在阈值萎缩中是最关键的。
目前使用的阈值可以分成全局阈值和局部适应阈值两类。
其中,全局阈值对各层所有的小波系数或同一层内的小波系数都是统一的;而局部适应阈值是根据当前系数周围的局部情况来确定阈值。目前提出的全局阈值主要有以下几种:
(1)Donoho和Johastone统一阈值(简称DJ阈值):
PS:σ为噪声标准方差,N为信号的尺寸或长度
(2)基于零均值正态分布的置信区间阈值:
(3)Bayes Shrink阈值和Map Shrink阈值。在小波系数服从广义高斯分布的假设下,Chang等人得出了阈值:
PS:R为噪声标准方差,RB为广义高斯分布的标准方差值
(4)最小最大化 阈值:这是Donoho和John Stone在最小最大化意义下得出的阈值,与上述的阈值不同,它是依赖于信号的,而且没有显式表达式,在求取时需要预先知道原信号。
(5)理想 阈值:理想阈值是在均方差准则下的最优阈值,同最大最小化阈值一样,也没有显式的表达式,并且这个阈值的计算通常也需先知道信号本身。
三、scanner.c中的阈值计算
static inline unsigned calc_thresh (zbar_scanner_t *scn)
{
/* threshold 1st to improve noise rejection */
unsigned dx, thresh = scn->y1_thresh;
unsigned long t;
if((thresh <= scn->y1_min_thresh) || !scn->width) {
dbprintf(1, " tmin=%d", scn->y1_min_thresh);
return(scn->y1_min_thresh);
}
/* slowly return threshold to min */
dx = (scn->x << ZBAR_FIXED) - scn->last_edge;
t = thresh * dx;
t /= scn->width;
t /= ZBAR_SCANNER_THRESH_FADE;
dbprintf(1, " thr=%d t=%ld x=%d last=%d.%d (%d)",
thresh, t, scn->x, scn->last_edge >> ZBAR_FIXED,
scn->last_edge & ((1 << ZBAR_FIXED) - 1), dx);
if(thresh > t) {
thresh -= t;
if(thresh > scn->y1_min_thresh)
return(thresh);
}
scn->y1_thresh = scn->y1_min_thresh;
return(scn->y1_min_thresh);
}
关于小波变换等处理在process.c文件中给出,由其他组员负责分析。
ZBar采用的算法是上述提到的(最大)最小化阈值,即在预先知道原信号的情况下,在最小(最大)化意义下得出的阈值。
首先对信号进行一阶差分,在此基础上,对一阶差分计算阈值,有利于去噪。
取得扫描器结构中的阈值,如果当前阈值小于最小阈值,或者边缘宽度为0,则返回最小阈值。
接下来求相对阈值。
相对阈值 = 上一次的阈值 * 当前边缘和上一次边缘之间的距离 /?再上一个距离的比值
如果上一次的阈值大于相对阈值,则用上一次的阈值减去相对阈值,结果如果大于最小阈值,则返回这个结果,否则返回最小阈值。
四、边界处理
static inline zbar_symbol_type_t process_edge (zbar_scanner_t *scn,
int y1)
{
if(!scn->y1_sign)
scn->last_edge = scn->cur_edge = (1 << ZBAR_FIXED) + ROUND;
else if(!scn->last_edge)
scn->last_edge = scn->cur_edge;
scn->width = scn->cur_edge - scn->last_edge;
dbprintf(1, " sgn=%d cur=%d.%d w=%d (%s)\n",
scn->y1_sign, scn->cur_edge >> ZBAR_FIXED,
scn->cur_edge & ((1 << ZBAR_FIXED) - 1), scn->width,
((y1 > 0) ? "SPACE" : "BAR"));
scn->last_edge = scn->cur_edge;
#if DEBUG_SVG > 1
svg_path_moveto(SVG_ABS, scn->last_edge - (1 << ZBAR_FIXED) - ROUND, 0);
#endif
/* pass to decoder */
if(scn->decoder)
return(zbar_decode_width(scn->decoder, scn->width));
return(ZBAR_PARTIAL);
}
process_edge函数对满足边界判定规则的点进行边缘处理。
上篇博客提到,ZBar边缘判定规则是根据二阶导数(y1_sign,即最后一个斜坡的坡度)为零的位置是一阶时的最大值或最小值,认为是边缘点。而last_edge是最后定位的边的插值位置。
ZBar扫描图像,对于每一个元素,若当前扫描位置不是元素的边缘点,则继续往下扫描(Z字型扫描);若遇到边缘点,则判断是否在当前扫描元素的最外沿(根据last_edge是否在最后定位的边的插值位置)。直到找到符合上述两个条件的位置,继续向下执行。
找到边界后,将最外沿位置与另一端位置相减,得到元素的宽度。然后将cur_edge赋值给last_edge,准备扫描下一个元素。
最后还需要将元素宽度传给解码器进行解码处理。
if(scn->cur_edge != x || scn->y1_sign > 0) {
zbar_symbol_type_t edge = process_edge(scn, -scn->y1_sign);
dbprintf(1, "flush0:");
scn->cur_edge = x;
scn->y1_sign = -scn->y1_sign;
return(edge);
}
另一方面,在zbar_scanner_flush()函数中,调用了边界处理函数。
在每次刷新扫描器时,需要对已经处理过边界的元素进行初始化,这里处理得很巧妙的是将y1_sign的相反数赋值给y1_sign,即取其二阶导数的相反数。
五、更新边界
线性插值算法
算法内容
线性插值是指插值函数为一次多项式的插值方式,其在插值节点上的插值误差为零。线性插值可以用来近似代替原函数,也可以用来计算得到查表过程中表中没有的数值。
?
插值在图像处理中的应用
在播放视频时,常遇到视频尺寸与画布尺寸不一致的情况。为了让视频按比例填充画布,需要对视频中的每一帧图像做缩放处理。
?
?
?
假设源图像大小为mxn,目标图像为axb。那么两幅图像的边长比分别为:m/a和n/b。注意,通常这个比例不是整数,编程存储的时候要用浮点型。目标图像的第(i,j)个像素点(i行j列)可以通过边长比对应回源图像。其对应坐标为(i*m/a,j*n/b)。 显然,这个对应坐标一般来说不是整数,而非整数的坐标是无法在图像这种离散数据上使用的。双线性插值通过寻找距离这个对应坐标最近的四个像素点,来计算该点的值(灰度值或者RGB值)。如果你的对应坐标是(2.5,4.5),那么最近的四个像素是(2,4)、(2,5)、(3,4),(3,5)。 若图像为灰度图像,那么(i,j)点的灰度值可以通过一下公式计算: f(i,j)=w1*p1+w2*p2+w3*p3+w4*p4; 其中,pi(i=1,2,3,4)为最近的四个像素点,wi(i=1,2,3,4)为各点相应权值。
inline zbar_symbol_type_t zbar_scanner_flush (zbar_scanner_t *scn)
{
unsigned x;
if(!scn->y1_sign)
return(ZBAR_NONE);
x = (scn->x << ZBAR_FIXED) + ROUND;
if(scn->cur_edge != x || scn->y1_sign > 0) {
zbar_symbol_type_t edge = process_edge(scn, -scn->y1_sign);
dbprintf(1, "flush0:");
scn->cur_edge = x;
scn->y1_sign = -scn->y1_sign;
return(edge);
}
scn->y1_sign = scn->width = 0;
if(scn->decoder)
return(zbar_decode_width(scn->decoder, 0));
return(ZBAR_PARTIAL);
}
ZBar通过线性插值算法获得新的边界:
首先更新阈值,然后对运动均值后的图像一阶差分,然后乘以一个常数,得到插值结果,即新的边界。
六、总结
本次博客对ZBar扫描器的图像阈值计算、边界判断、边界重置等算法进行了分析。如有不足,敬请指正。
|