扫描算法范文

扫描算法范文（精选7篇）

扫描算法 第1篇

车牌识别 (License Plate Recognition, LPR) 技术是交通管理自动化的重要手段和车辆检测系统的一个重要环节。文章研究了使用边缘检测与线扫描相结合的定位车牌区域的方法, 能够满足车牌定位的要求, 实现车牌定位这个功能, 主要步骤如下:

1) 输入图像;

2) 将24位真彩色图像转化为灰度图像;

3) 将灰度图像转化为二值化图像;

4) 将二值化图像进行边缘检测, 得到边缘图像;

5) 对边缘图像进行扫描, 确定候选车牌区域。

2. 图像预处理

2.1 图像灰度化

为提高后续算法速度进行图像预处理将图像灰度化。彩色图像的像素点是由R (红色) 、G (绿色) 、B (兰色) 三元色混合而成的, 一般使用256级灰度图, 24位真彩色图像转灰度图像的公式如下:

灰度值=0.299R+0.587G+0.114B

将图像灰度化后继续将其进行二值化处理, 即转化为只有黑白两色构成的图像。二值化过程可表示为公式1:

公式1二值化过程

这里采用阈值分割法进行灰度图像二值化, 其中T为二值化阈值。

2.2 Canny边缘检测算子

Canny算子分为几个步骤:

1) 对源图像进行高斯平滑;

2) 产生一个一维高斯分布函数, 用高斯算子的一阶微分对图像进行卷积运算, 得到每个像素梯度的大小G和方向θ;

3) 抑制局部像素非最大梯度点, 梯度的方向可以被定义为属于4个区之一, 各个区用不同的邻近像素进行比较, 以决定局部极大值, 这个过程也称“非极大抑制”;

4) 根据梯度计算及经过非最大值抑制后的结果设定阈值;

5) 寻找边界点并实现Canny函数。

3. 车牌扫描定位算法

3.1 车牌图像扫描

在二值边缘图中, 由于车牌区域字符的纹理特征, 对边缘图进行扫描时, 会发现车牌区域灰度值跳变频率明显高于其它非车牌区域。定义扫描前一个像素的值与后一个像素的值不等即为一次跳变。一般车牌区域字符与字符之间的距离在一定范围内且字符数固定, 相对于其他非车牌区域跳变次数有规律, 通常为14以上。整个扫描过程分为以下几步:

1) 进行行扫描。定义T和step两个值, 每次扫描每行T个像素, step为第二次扫描的起始像素与第一次扫描的起始像素之间相隔的像素, 由于图像大小的限制, 所以选择初始T为75, step为50, 对每一行的扫描可以如图1所示:

2) 扫描每一个T区间产生一个count用来记录每一个T区间里的灰度跳变次数, 每扫描到一次跳变, 对应的count就自加一次。

3) 对图像进行列扫描, 以每个T区间为单位扫描, 根据图像的特点设定一个阈值, 在每一列区间中凡是灰度跳变次数 (count) 大于这个阈值, 定义了名为num[j]的数组记录下每一列有几个区间是灰度跳变次数大于这个阈值的。

4) 到这里为止只是确定了车牌区域像素所在的列的位置, 为了得到确切位置, 还要进行一次像上面所述的扫描, 不过改变的是先扫描列, 得到新的T区间的跳变次数后, 进行行扫描, 以确定车牌区域所在的行的位置。

3.2 车牌图像定位

根据图像本身的情况对先行后列和先列后行两次扫描分别选择两个阈值, 一个是从图像的左边开始, 凡是num[i]小于25的, 也就是那列中灰度跳变次数大于10的区间少于25个, 那么这列就为车牌区域开始的列的位置, 第二次从图像的右边开始, 凡是num[i]小于15, 那么这列就是车牌区域结束的列的位置。

3.3 车牌图像提取

我们采用从剪贴板中将原灰度图像的车牌部分剪裁下与提取出来的车牌二值化边缘图像相重合, 得到车牌部分的完整图像。

4. 实验结果

扫描实验采用了共200幅由公路摄像机获取的汽车图片, 包括各种车型。图2所示真彩色图像转化为边缘图像:

转化后用扫描算法进行车牌提取, 结果如图3所示:

由实验结果得出, 本文提出的定位方法定位率高, 定位准确。

5. 结论

本文结合Canny算子对图像进行边缘提取, 得到边缘图像后再对结合扫描算法对边缘图像进行扫描, 准确提取出出车牌部分的图像, 进行车牌定位, 结果表明, 该方法能有效定位车牌, 定位率及准确率都能达到实验要求。

参考文献

[1]刘伟铭.一种基于扫描行的汽车车牌定位算法[J].长沙交通学院, 2004, (6) .

扫描算法 第2篇

伴随数字媒体技术的发展,大量的电子媒体产品在互联网上发布与传播,通过信息网络技术,对其进行非法的修改、拷贝和删除,从而保护数字产品所有权显得更为迫切重要。数字水印技术是为了验证作品拥有权的问题,在数字产品中嵌入特殊标记信息,并且通过对水印的检测分析来保证数字产品的安全可靠,使数字产品的知识产权得到保护,比如,通过LSB方法、Patchwork方法等经典的水印算法来实现。除此之外,文献[1]通过判断数字水印存在与否,提出了基于两重水印方法的提取算法。文献[2] 算法的理论依据是Sharmir提出的基于Lagrange公式的密钥共享方法,为了保证水印的安全性,将加密后的水印信息分为n组分别嵌入图像的不同DCT区域块中,提取时只要获得其中的t(tn)份水印就可恢复原始水印,该算法在抵抗多种复合攻击上较有长处。文献[3]是对在嵌入水印强弱方面,采用了相应的调节处理方法。文献[4]通过掩饰的特征来调节水印强弱大小,得出了提取盲水印算法,提取算法只要求判断水印是否存在。文献[5]算法利用离散傅里叶变换对旋转、缩放、平移的不变性,通过对幅度谱进行矢量量化,在宿主图像DFT域中心化频谱的每个同心圆中嵌入位信息,提取时根据“多数原则”来恢复水印的位信息。文献[6]利用分形维数来度量图像的特征区域,这些区域被分为边缘、弱纹理与强纹理等类别,从而在实施水印操作时赋以不同的强度。文献[7]通过使Hilbert逻辑相邻的两88块的对应DCT系数之间满足特定关系来表示1与-1两种信息,即隐藏了水印信息,水印的提取不依赖原始图像。

参数B样条曲线是形状数学描述组成内容之一,它为工程、几何造型等应用中的大量问题建立数学模型提供了重要的工具与手段。小波分析也获得日益广泛的应用,包括信号处理、图像压缩、图形学等领域,B样条曲线的多分辨表示就是小波分析应用于图形光顺的一个重要技术。当然可以考虑沿用这些理论基础到数字水印技术研究上,如文献[8],其算法是对数字图像进行小波变换,水印的检测要参考原始图像。但为了使小波分析与B样条技术更好地融入数字水印研究中,本文提出一种新的数字图像水印算法,算法直接应用图像灰度值控制三次准均匀B样条曲线,进而通过对该曲线的多分辨表示实现水印,水印的提取不需要参考原始图像。

1 理论基础

1.1 小波划分和重组

设γ(t)是任意一个带有2j+3个控制顶点的准均匀三次B样条曲线,则γ(t)可划分为低频部分γj-1(t)和高频部分βj-1(t),且γj-1(t)和βj-1(t)均为同样的曲线[9]。令Cj表示γ(t)的2j+3个控制顶点构成的列向量,则γ(t)分解为低频部分γj-1(t)和高频部分βj-1(t)等同于将Cj划分为相应部分的Cj-1与Dj-1。它们之间的公式表示如下:

Cj=PjCj-1+QjDj-1 (1)

在从已知条件Cj求解出Cj-1过程中,我们需要把式(1)转化为:

$[{\rm P}{}_j|Q{}_j]\left[\frac{C{}_{j-1}}{D{}_{j-1}}\right]=C{}_j$

为了得到唯一Cj-1和Dj-1,解上式的线性方程组,然后将Cj分解成低频部分Cj-1和高频部分Dj-1。为了降低算法复杂度,可参考文献[9]所提到的线性方程组解法。

1.2 混沌伪随机数集

设U⊂R(R为实数空间),f:UU为一维混沌映射:

xk+1=f(xk,λ) xk∈U λ∈R

其中k=1,2,表示迭代次数,λ为控制系统混沌行为的参数。

给定实数初值x1,由混沌映射迭代生成的混沌序列二值化后可得{0,1}二值序列,顺次取m比特可得十进制混沌伪随机数集{ai|0ai<2m,i=0,1,},直到集合的元素达到所需要的个数n。

2 水印嵌入算法

step1 利用Arnold变换将大小为NN的二值水印Wo的信息次序打乱处理后[6],得到处理后的图像,再用行扫描将该置乱图像处理变换为一维向量,并对该向量进行二极化处理得:W={w(i)|w(i)∈{-1,1},0im-1},这里m=NN;

step2 由于希尔伯特变换扫描具有保持良好的图像局部区域关联性,将源图像I按44区域分块,将该分块区域按希尔伯特变换重新扫描排列,处理得出排序列H,H={H(i)|i=0,1,,MN/16-1};

step3 给定一混沌初值(密钥K),由混沌映射迭代k次后构造一个11个元素的混沌伪随机数集A={ai|0ai<24,i=0,1,}(即取m=4,n=11);

再选取一正偶数R和正整数T0<R/2,令T1= T0+R/2;令τ=0,取待嵌入水印比特w(τ);

step4 从H选出两相邻44块H(2τ)和H(2τ+1),分别对两44块中的像素进行Hilbert扫描形成一维向量C(1)和C(2),C(s)=(v${}_0^{(s)}$,v${}_1^{(s)}$,,v${}_{15}^{(s)}$)T,(s=1,2),这里v${}_i^{(s)}$为经Hilbert扫描时第i+1像素的灰度值;

step5 以向量C(s)中下标在集合A中出现的11个分量构造新的向量,新向量仍用C(s)表示,而且为表述方便,不妨设C(s)=(v${}_0^{(s)}$,v${}_1^{(s)}$,,v${}_{10}^{(s)}$)T,(s=1,2)。

以C(s)作为控制顶点列向量,和(0,0,0,0,1/2j,,1-1/2j,1,1,1,1) 为节点矢量(j=3)定义两条三次准均匀B样条曲线γ(s)(t)(0t1),γ(s)(t)经两次小波分解后得到低分辨部分C${}_{j-1}^{(s)}$=(v${}_0^{(s)}$,v${}_1^{(s)}$,,v${}_4^{(s)}$)T和细节部分D1${}_{j-1}^{(s)}$=(d${}_0^{(s)}$,d${}_1^{(s)}$,,d${}_3^{(s)}$)T与D2${}_{j-1}^{(s)}$=(d${}_0^{(s)}$,d${}_1^{(s)}$)T,(s=1,2);

step6 令$\mu {}_s={\displaystyle \sum _{i=0}^{2{}^{j-2}+2}v}{}_i^{(s)}‚(s=1,2)$;μdif=(μ1-μ2)modR;

当w(τ)=1时,求得:

而当w(τ)=-1时,则求得:

并令v${}_i^{(1)}$=v${}_i^{(1)}$+σ,v${}_i^{(2)}$=v${}_i^{(2)}$-σ,i=0,1,,2j-2+2;

step7 由C${}_{j-1}^{(s)}$和D1${}_{j-1}^{(s)}$与D2${}_{j-1}^{(s)}$,(s=1,2),用式(1)重构新的控制顶点向量C(1)和C(2),表示两相邻44块H(2τ)和H(2τ+1)已嵌入水印信息;

step8 令τ=τ+1,重复执行step4～step6,直到全部水印比特嵌入完成。最后按Hilbert扫描的逆映射把各像素映射到Hilbert扫描之前的像素位置,得到加水印图像。

说明:step5与step7的小波分解与重构算法如第1.1节所述。

3 水印提取算法

E-step1 将原始图像I(图像大小为MN)按44分块,并将该分块区域按希尔伯特变换重新排列,整理得出了排序列H,H={H(i)|i=0,2,,MN/16-1};

E-step2 给定密钥K,构造11个元素的混沌伪随机数集A={ai|0ai<24,i=0,1,};也确定嵌入水印时的值T1,并取τ=0;

E-step3 从H选出两相邻44块H(2τ)和H(2τ+1),分别对两44块中的像素进行Hilbert扫描形成一维向量C(1)和C(2),C(s)=(v${}_{01}^{(s)}$,v${}_1^{(s)}$,,v${}_{15}^{(s)}$)T,(s=1,2);

E-step4 以向量C(s)中下标属于A的分量构造新的向量,仍记为C(s);以C(s)作为控制顶点向量的三次准均匀B样条曲线经两次小波分解后得到低分辨部分C${}_{j-1}^{(s)}$=(v${}_0^{(s)}$,v${}_1^{(s)}$,,v${}_4^{(s)}$)T,(s=1,2);

E-step5 令$\mu {}_s={\displaystyle \sum _{i=0}^{2{}^{j-2}+2}v}{}_i^{(s)}‚(s=1,2)$;μdif=(μ1-μ2)modR;,w′(τ)即为提取的水印比特;

E-step6τ增1,转E-step3,直到τ>=m(m为水印比特总数);

E-step7 计算提取水印与真实水印的相关性:

$\rho =\frac{{\displaystyle \sum _{\tau =0}^{m-1}w}(\tau )w^{\prime }(\tau )}{m}$

其中,m为原水印比特数,w′(τ)表示提取水印的第τ比特(t=0,1,,m-1)。

4 测试结果

本文选择了尺寸为512512的Baboon等一些灰度测试图像,通过相应地水印嵌入处理后,进一步测试是否攻击后水印的不同提取情况。论文选用的水印是5050图像区域,如图1(a)所示,通过该算法变换处理后如图1(b)所示,再二极化处理为W={w(i)|w(i)∈{-1,1},0i<1600}。检测阈值ρT取0.13,对应的虚警概率为Pfp=8.3810-8。参数取值为R=30,T0=8,T1=23。

对Baboon图像嵌入水印,加水印后图像峰值信噪比(PSNR)为44.144,视觉效果上感觉不到嵌入水印的图像与原始图像的差异(如图2)。在未经攻击情况下,水印相关性ρ值为1.00。

对水印图像分别作中值滤波、JPEG压缩(取质量因子Q=40)处理后提取的水印相关性如表1所示。图3(a)～(c)分别为Baboon、Lena、Boat等水印图像33中值滤波后提取的水印情况,图3(d)～(f)分别为Baboon、Lena、Boat水印图像经JPEG压缩(因子Q=40)后提取的水印情况。Baboon经过中值滤波,以及质量因子为90、70、50、40的JPEG压缩后提取的水印见表2与表3,表中同时列出与文献[11]的比较。

水印的稳健性与可扩展性测试通常包括加噪、旋转、扭曲等攻击测试,水印图像加不同方差高斯白噪声后水印提取效果见表4和图4,旋转、扭曲、剪切后水印进行提取效果见表5。

通过对上述的实验结果分析,本算法与文献[11]的算法之间性能高低比较如表6所示。

5 结 语

本文提出了一种基于参数样条多分辨表示和双重希尔伯特变换扫描的水印算法,它具有以下特色:(1)水印具备良好的安全性和可持续发展性。主要是利用准均匀B样条的多分辨表示来实现水印方案。(2)水印算法利用了图像块间的局部相关性技术。Hilbert曲线能最好地保持空间局部邻接性[12],Hilbert逻辑相邻的两图像块之间的局部相关性可以较好地保持,在媒体受到攻击时也如此,因此本文这种盲水印算法的稳健性显得更为突出。在B样条曲线的低分辨部分嵌入了水印,并重构新的B样条曲线时,水印信息就分散到图像块内的有关像素上,提取水印时,分散的信息又集中到低分辨部分。

摘要：提出一种基于双重Hilbert扫描的数字水印算法。该算法先将原始图像各4×4块按Hilbert扫描顺序排列,再对4×4块内的像素按Hilbert扫描顺序转换为准均匀三次B样条曲线的控制顶点向量。然后对B样条曲线进行小波分解获得曲线的低分辨部分。通过调整Hilbert逻辑相邻的两B样条曲线低分辨系数关系来实现水印信号的嵌入。水印嵌入后重构新的B样条控制顶点,新的控制顶点经逆Hilbert重置得到水印图像。实验结果表明,算法对图像压缩、滤波、缩放等攻击具有较强抵抗力。

关键词：B样条曲线,数字水印,小波,多分辨表示

参考文献

[1]Liu J C,Chen S Y.Fast two-layer image watermarking without referring to the original image and watermark[J].Image and Vision Computing,2001,19:1083-1097.

[2]牛少彰,钮心忻,杨义先.基于Shamir秘密共享方案的数字水印算法[J].中国图象图形学报,2003,8(10):1178-1182.

[3]王向阳,杨红颖.DCT域自适应彩色图像二维数字水印算法研究[J].计算机辅助设计与图形学学报,2004,16(2):243-247.

[4]Barni M,Bartolini F,Piva A.Improved wavelet-based watermarking through pixel-wise masking[J].IEEE Trans.on Iamge Processing,2001,10(5):783-791.

[5]石磊,钟铭,洪帆.抵抗几何变换的基于量化的水印技术[J].计算机辅助设计与图形学学报,2004,16(6):850-855.

[6]倪蓉蓉,阮秋琦.一种基于迭代映射和图像内容的自适应水印算法[J].通信学报,2004,25(5):182-189.

[7]杨恒伏,杨子华.结合Hilbert扫描的DCT域鲁棒公开水印算法[J].小型微型计算机系统,2004,25(5):891-895.

[8]姚志强,潘日晶,邹柏贤,等.用B样条方法实现数字水印[J].计算机辅助设计与图形学学报,2005(7).

[9]朱心雄.自由曲线曲面面造型[M].北京:科学出版社,2000:315-317.

[10]王宏霞,何晨,丁科.基于混沌映射的鲁棒性公开水印[J].软件学报,2004,15(8):1245-1251.

[11]胡玉平,孙伟,石磊,等.基于人眼视觉特征的小波树量化水印[J].小型微型计算机系统,2004,25(7):1491-1494.

基于扫描线的隐藏线消除改进算法 第3篇

目前采用的大多数消隐算法都需要进行直线和平面多边形的求交, 线段和线段之间的求交等。线段求交是消隐算法中一个很重要的内容, 线段求交算法的效率直接影响整个消隐算法的效率。可以说, 求交计算是计算机辅助设计系统的重要组成部分, 它的准确性与效率直接影响计算机辅助设计系统的可靠性与实用性。求交运算也是消隐算法中不可缺少的一步。但是求交运算是非常复杂的, 如果采用传统的求交算法, 对一个三维形体的n条边求交, 那么它的时间复杂度就是, 而一个三维形体的边的个数可能达到几万条, 这样整个消隐过程所花费的时间可能会是几分钟, 那么为了提高消隐算法的运算速度, 需要提高求线段交点的运算速度, 因此采用了扫描线算法来求线段的交点, 之后把这些算法应用到隐藏线消隐算法中, 就得到了输出敏感的隐藏线消除改进算法。

2、扫描线求交算法

扫描线求交算法使用一种称为“扫”的技术, 这种技术对很多计算几何算法都是通用的, 而且对此算法只要做简单的修改, 就能使用它来解决其他的计算几何问题。在“扫”过的过程中, 想象中的垂直扫描线通常从左到右通过给定的几何对象, 扫描线提供一种排序几何对象的方法, 为了充分利用它们之间的关系, 通常把这些几何对象放在一个动态的数据结构中。

2.1 排序线段

假设没有垂直的线段, 那么任何一个与给定的垂直扫描线相交的输入线段与垂直扫描线一定相交于一点。因而能够根据相交点的坐标来排序那些与垂直扫描线相交的线段。为了更精确, 考虑两条线段、, 如果垂直扫描线与线段、都相交, 这两条线段在横坐标处是可以比较的。如果和是可比较的, 同时垂直扫描线与的交点的纵坐标大于与的交点的纵坐标时, 称在的上面记为。这样, 对于任何给定的x, 关系是与x处的垂直线相交的线段的一个全序。也就是说, 对于平面上给定的n条线段, 若用一条垂直线从左到右扫描整个平面, 在垂直扫描线与给定线段集的交非空时, 关系将保持一个全序关系。然而, 随着线段的进入和离开, 对于给定的不同的x值, 这个序列可能会不同。当一条线段的左端点与扫描线相遇时, 此线段进入这个序列, 当线段的右端点与扫描线相遇时, 此线段离开这个序列。为了简化算法的描述, 假设在所给的线段集中所有线段的端点和线段之间的交点的x坐标都不相同。当出现端点或交点的x坐标相同的情形时, 在算法中应将其作为有序集中键值相同的不同元素来处理。

2.2 移动扫描线

计算线段相交的平面扫描算法用了两个基本的数据结构:扫描线状态和事件进度表。扫描线状态:扫描线状态用于描述与扫描线相交的线段集的次序关系。事件进度表:事件进度表是一个x坐标序列, 从左到右排序, 它定义了扫描线的停止位置, 每一个这样的停止点为一个事件点, 仅在事件点处, 扫描线状态会发生变化。当一条线段的左端点遇到扫描线时, 我们把这条线段插入到扫描线状态中。当线段的右端点遇到扫描线时, 从扫描线状态中删除这条线段。当两条线段在全序序列中第一次变成邻接, 就来判断这两条线段是否相交, 如果相交, 求出交点。

随着x坐标值的增加从左到右地把线段的端点进行排序。如果两条或更多条线段的端点有同样的x坐标, 解决的办法是把所有这样线段的左端点放在右端点的前面。如果两条线段的左端点的x坐标是相同的, 那么把y坐标值小的放在前面, 当两条线段的右端点的x坐标是相同时, 也同样处理。为了报告所有的交点, 当垂直线扫描平面时, 一定要能维持关系。仅在线段的左端点或右端点, 或线段交点的不同的横坐标处变更关系。当先给定所有线段的左端点和右端点时, 由平面扫描找到的一个交点动态地产生一个事件, 一般地, 它一定被记录, 且在适当的时候由算法来处理。事实上, 注意到在检出一个交点的时刻和处理对应事件的时刻之间可能必须处理几个事件的横坐标。

综合以上两步, 得出扫描线求交算法的基本思想是:用一条垂直的扫描线从左到右扫过整个平面, 在每个事件点 (即每条线段端点或线段对的交点) 处修改数据结构, 且检测修改后变成相邻的线段是否相交。若检测到一个交点, 则报告该线段对及其交点的坐标。且把它的横坐标插入到事件点进度表中去。

3、隐藏线消除算法

本文主要做的是利用扫描线来处理潜在可见边, 为完成操作, 需要以下几个表:边表 (ET) :为投影到可视平面的所有多边形的所有非水平边, 建立一个ET。按照边的最小的y坐标值排序, 在边的最小的y坐标值相同的情况下按照两条边的另外一个端点的x坐标值排序。表中三表字段分别表示为x:最小y坐标的端点的x坐标, ymax:边的另外一个端点的y坐标ID:多边形的编号, 表示此边属于哪一个多边形。面表 (FT) :建立一个面表, 它至少包含下面的信息:面的方程的系数, 面是否隐藏或者是颜色信息。活动边表 (AEC) ::建立一个活动边表, 记录扫描线正在扫过的边。事件点优先队列:用于事件处理, 即为扫描线求交算法的事件点进度表。活动面表:用来记录当前扫描线正在处理的边所在的面。利用扫描线求交的过程中, 处理每一条潜在可见边被扫描线分割的每一小段来判断它是否被活动面遮挡, 从而判断每一小段的可见性。具体的实现步骤如下:

(1) 如果扫描线遇到的是可见边的起点。如果是水平边的话, 存入水平边向量队列;否则, 存入活动边向量队列。

(2) 如果活动边向量队列为空, 则直接判断水平边向量队列中的水平边的可见性并显示。

(3) 对活动边表向量以活动边与扫描线的交点x坐标值, 以及方向关系为关键字进行排序。

(4) 对每两个相邻的活动边求交, 增加可能的事件扫描线, 同时把交点的y坐标插入到事件点优先队列中。

(5) 判断水平边向量队列中的水平边的可见性并显示。 (6) 如果活动边表向量为空, 则结束本次循环。

(7) 判断当前扫描线至下一扫描线之间各个活动边的可见性。取活动边中点的y坐标值, 活动面的个数设为0;对于每个活动边, 首先退出某些活动面, 并给出它的一个可见面, 如果活动边是某一活动面的右边的边并且此活动边可见或者活动边是光滑的, 那么退出此活动边的左边的面, 否则, 给出此活动边的右边的面;进行当前活动边的可见性判断, 如果此活动边只有一个活动面可见或者此边是不光滑的且如果活动面的个数大于0, 那么求出此活动边中点的x坐标值, 根据此活动面, 判断此中点的可见性, 否则, 可见变量为true, 如果可见变量为真, 同时此活动边的上一段不可见或者可见变量为假, 同时此活动边的上一段可见, 那么如果此活动边的上一段可见则显示上一段设置最后一段的可见性以及最后一个分割点的x, y坐标;循环继续处理当前活动边, 加入活动面并进行活动边循环。

(8) 删除活动边, 并改变活动边的x坐标。

(9) 扫瞄线继续向下移动, 循环以上操作。

4、测试分析

采用基于扫描线的输出敏感的隐藏线消除算法所花费的时间比采用传统消隐算法所花费的时间要少得多, 前者的运算速度是非常快的。探究其原因, 一个是边和边之间求交时间消耗减少了, 在传统消隐算法中, 求交所花费的时间为, 而采用扫描线求交, 所花费的时间为, 而这个时间要比小得多。其次, 在传统算法中要进行点在多边形内外的判断, 但是对被扫描线分割的每一小段, 只需判断它是否被活动面遮挡即可, 而活动面可以认为是常数。综合以上两方面的原因得出这样的结论:采用基于扫描线的隐藏线消除算法比采用传统的隐藏线消除算法的运算速度要快得多。

摘要：隐藏线消除是计算机图形学的一个基本问题, 是计算机图形学中真实感显示的一个重要方面, 通过隐藏线消除不但能增强图形的立体感, 避免产生不确定性, 而且大大提高图形明暗描绘的效率。为了提高消隐算法的运算速度, 需要提高求线段交点的运算速度, 采用扫描线算法求交, 把此求交算法应用到隐藏线消隐中, 这种输出敏感的隐藏线消除算法的运行速度比采用传统求交算法实现消隐的速度有很大提高。

关键词：隐藏线消除,线段交点,扫描线算法

参考文献

[1]潘云鹤, 董金祥等。计算机图形学。北京:高等教育出版社, 2003。

[2]王晓东, 傅清祥, 范庆等。线段相交问题的新的平面扫描型算法。计算机工程。94学术年会论文专刊。

扫描算法 第4篇

随着当代通信技术的发展,技术设备在航空系统、军队、工业等领域的应用已成业务运行的根本保障,大多数设备需24 h无间断供电,这就要求对电源有智能检测和实时的监控,以便及时处理断电事故,保障设备正常运行。而在实际应用中,为了确保有足够的时间抢修断电线路,通常在设备供电中采用多路供电,形成一主用、二备用、三应急的构架[1]。因此,在多路断电线路中实时检测断电线路并进行报警已经成为及时恢复正常供电的关键。本文提出基于改进型的键盘扫描算法,通过设计相关检测硬件电路和监控软件,对多路供电系统进行智能检测报警和远程监控。

1 系统结构

本系统已在民航汕头空管站信标台机房投入使用,下面以其为例简述设计基本结构。

系统硬件部分主要由检测硬件电路、AT89C51单片机及其相关组件和PC机组成。软件部分为断电信号的键盘编码、键盘扫描算法的改进和PC机监控软件的设计。具体实现是通过检测电路发送断电信号给单片机[2],单片机通过键盘扫描算法得出断电线路对应的键盘码,PC监控软件则通过串口通信将单片机送来不同的键码给予相关的报警处理,如图1所示。

在信标台机房中,共有市电输入1、市电输入2和油机电输入3路供电,平时正常状况为2路市电互为主备用,油机待机不发电(2路市电皆断电时,油机启动发电应急)。因此有以下4种供电状态:

(1) 正常情况,2路市电供电,油机待机;

(2) 只有一路市电供电,另一路市电故障,油机待机;

(3) 2路市电都发生故障,油机启动发电;

(4) 2路市电都发生故障,油机未启动。

对于以上4种状态,A状态可设为监控系统初始状态,其余共有4种断电状态(B状态有2种情况)。分别对其进行键盘编码,使每一种断电状态都有惟一的键码与之对应,电路设计采用24的键盘,硬件电路如图2所示。通过键码识别,PC机上的监控软件可以实时判断断电线路提出报警。

2 系统设计

2.1 硬件设计[3,4]

如图2所示,电路采用光电耦合器进行强电隔离,起到防雷作用,并将模拟信号转换成数字信号,实现A/D转换。输入的220 V交流电经整流二极管D1整流、电容C1滤波后,形成直流电。

电流分成两路,一路经R1限流电阻使指示灯LED发光;另一路经R2限流后送入光电耦合器4N25,点亮内部的发光二极管,使光敏晶体管导通,在光电耦合器的4脚得到一个高电平。当输入的220 V交流电断电时,光电耦合器输入端电压消失,发光二极管熄灭,光敏晶体管截止,4脚得到一个低电平,经过相关的逻辑电路处理后,控制继电器吸合(继电器代替了键盘按钮)。从而实现了把断电信号模拟成键盘按下的状态,方便下一步处理。

2.2 单片机改进型键盘扫描算法

对于多路供电的情况,可以通过对线路断电信号进行键盘编码,从而使识别多路断电成为可能。由于电路对报警实时性和准确性的要求,采用了改进型的键盘扫描算法。实验证明,该算法在系统的应用中有很好的效果。实时检测断电信号是系统准确性的一项重要指标,由于传统键盘扫描算法在抖动算法调用的同时会屏蔽掉中断,因此有必要对键盘扫描算法进行改进。

算法改进主要分成3步:首先在中断运行程序中设置中断变量,记录运行次数。判断中断执行次数是否符合延时时间,然后再判断键盘是否按下(也就是断电信号是否真实)[5]。其次,每次调用键盘扫描分析程序均需经过10 ms同步,当第1次检测到按键时仅设置一个标志,第2次检测到按键时(与第一次检测到按键相隔10 ms)再进行键分析[6],实现报警准确性的同时,提高系统的实时性。最后,系统根据不同的状态对信号进行编码,三路电路由于有4种不同的状态而编成4个统一独立的键码,减少了键码分析的复杂性,提高系统的实时性。

2.3 基于VC++6.0的监控软件设计

在VC++6.0平台上设计监控软件[7]。该软件主要由系统设置、运行状况和状态显示3部分组成,界面简洁方便监控。系统设置了对系统状态显示复位的功能、选择通信串口的功能以及通信测试的功能。

通信测试主要用于日常维护,对于本系统来说,单片机与PC机的通信链路至关重要,通过日常维护的通信测试可以减少系统下线未报警的风险。在运行状况模块中,监控软件提供了两路市电运行报告和油机的状态报告,如图3所示。

状态显示可以智能地显示出断电线路,实现现场无人监管、远程监控,如图4所示。

3 结 语

本文提出基于改进型键盘扫描算法的多路电源断电报警系统设计,利用键盘扫描算法的简洁可行性,对多路断电线路信号进行键盘编码,终端监控报警软件通过断电信号的对应键盘码进行识别,断电线路提出报警。该系统简化了一般电源断电报警系统,在实际应用中,系统实现简单,识别断电时间为μs级,报警准确,目前已投入实际使用。

参考文献

[1]张震.论机房电源安全[J].计算机与网络,2008(9):231-234.

[2]胡汉才.单片机原理及其接口技术[M].北京:清华大学出版社,2001.

[3]曹才开.电工技术[M].北京:清华大学出版社,2007.

[4]武战强.光电耦合器介绍及应用[J].家电检修技术,2007(8):61-62.

[5]杜道山,白荣华,田秀英,等.伺服控制系统键盘扫描程序的处理[J].机床与液压,2005(10):156-157.

[6]刁世伦,潘文良.一种高效的键盘扫描分析算法[J].科技信息,2010(9):23-25.

[7]田敏,郑瑶,李江全.Visual C++数据采集与串口通信测控应用实战[M].北京:人民邮电出版社,2010.

[8]鲁庆宾.矩阵式键盘部分连击的处理[J].电子设计工程,2011(17):34-36.

[9]鹿璇,宋晓,杜冲.基于单片机和FPGA的人机交互系统的设计[J].电子设计工程,2010(9):155-157.

[10]于淼.CAN总线在多机通信中的应用[J].电子科技,2011(2):54-56.

[11]孙梦宇,赵敏,吴毅杰,等.基于ARM的电子负载网络监控系统[J].电子科技,2010(3):46-49.

扫描算法 第5篇

光纤耦合成像系统采用六角形排列叠层结构的光纤束耦合图像, 可获得超高空间分辨率的遥感图像[1]。然而耦合系统的波特率高达480 Mbps, 如不进行压缩处理, 很难做到实时传输。利用传像光纤束耦合的扫描系统成像时, 由于加工工艺所限, 目前国内只能加工六角形排列的光纤束, 且相邻层光纤间存在水平方向上的错位[2], 这些特性使得耦合图像细节信息比一般的遥感图像更为丰富, 为保证图像的完全重构, 系统需采用无损压缩技术来解决带宽资源不足的问题。

随着小波的发展, 小波变换在图像压缩领域的表现已经得到广泛学者的认可。基于小波分解, 近些年来也涌现出很多能有效组织和压缩小波系数的嵌入式编解码算法, 其中以嵌入式零树编码 (EZW) [3]、集合树的分裂算法 (SPIHT) [4]和嵌入式优化截断块编码 (EBCOT) [5]最为流行。EBCOT算法虽然压缩比性能极高且已被JPEG2000[6]标准采用, 但由于采用了复杂的率失真优化控制单元和自适应算术编码技术, 算法复杂度高, 硬件实现困难且成本较高。而作为EZW改进的SPIHT则以简单高效而被广泛采用, 其输出码流即使不经过熵编码或算数编码仍可达到很高的压缩比。

本文的编解码器采用基于整型提升实现的双正交5/3小波变换来去除图像数据的相关性, 选用基于小波变换的集合树分裂 (SPIHT) 编码算法进行无损压缩编解码。

1 双正交整数小波变换的提升实现

1.1 提升算法简介

自从Sweldens提出了不依赖傅里叶变换的小波提升方法[7], 小波变换便摆脱了傅里叶变换的限制, 从而使得第一代小波变换算法的性能得到很大的改进。提升算法的运算量相比经典的Mallat算法减少了一半, 并能实现小波变换的原位计算, 即整个计算过程不需要申请辅助存储空间, 可以节省存储单元。整数小波变换以及逆小波变换的实现也非常简单快捷, 再加上简单有效的边界处理机制, 使其可以应用于图像的无损压缩。

1.2 小波变换性能的分析

图像无损压缩中小波变换的提升实现需考虑到以下两个问题:小波基的选取和边界滤波问题。

(1) 小波基的选取

计算复杂度被认为是评价整数小波变换性能好坏最重要的标准[8], 而小波基的选择直接决定了整数小波变换在无损压缩中的性能。文献[8]中给出了12种备受关注的整数小波变换, 并对这12个变换的无损压缩性能做了全面的比较。在本文中, 笔者旨在找到符合系统需求且计算复杂度和内存需求不高的整数小波变换。

由于除法运算可以采用移位实现, 从而对小波变换计算复杂度影响最大的便是乘法运算, 相同条件下乘法运算所占的比例越高, 计算复杂度越高。在文献[9]中列举了常用的小波滤波器的整数提升实现。其中, 5/3、2/6、5/11-C、6/14和5/11-A变换所采用的提升滤波器系数都是严格的2的整数次幂, 所以实现他们不需要乘法运算。5/3小波和2/6小波是上述12个小波中计算复杂度最小的两个变换。相比于实数运算, 整数运算过程中, 采用16位数存放变量, 内存需求更低, 同时采用取模整数算法可以保证数据的可逆性。

相比于2/6小波, 5/3小波在无损压缩中的表现更佳, JPEG2000标准将用提升算法实现的5/3双正交小波滤波器作为无损压缩的默认滤波器。所以本文选择5/3小波滤波器来去除光纤耦合图像的相关性。

(2) 边界处理

对有限长信号进行小波变换时需采用延拓与截取操作来处理边界信号, 以确保小波变换量与输入数据量一致, 才能完全重构[10]。延拓的方法一般有三种:周期延拓、对称延拓和单步取代延拓。周期延拓是处理有限长信号最简单的方法, 但是由于周期延拓通常会再信号边界引入不必要的高频成分, 所以在图像无损压缩编码中应用很少。对称延拓是处理有限长信号的重要方法, 它同时又是周期延拓, 具有周期延拓的优点, 但同时不会再边界引入高频成分。5/3小波滤波器是严格对称的双正交滤波器, 采用对称周期延拓的信号边界处理方案则不仅可以实现小波变换的完全重构, 同时又不增加变换后的数据量。设N为输入信号长度, 5/3滤波器两端延拓信号长度都为2, 变换后截取中间的N/2的信号量既为变换结果。

1.3 5/3整数小波变换的提升实现

正向小波变换的提升实现算法:

步骤1懒小波变换

步骤2提升与对偶提升

对于i=0, 1, , n, 有:

即先用偶序列去预测奇序列dli-1来实现提升, 再用奇序列的预测误差di来更新偶序列sli-1来完成对偶提升。

步骤3比例变换

对于l=0, 1, , N/2-1, 有:

其中K为比例系数, 最后得到的s和d分别为小波分解的低频分量和高频分量。

逆变换只需简单地调整一下变换中的正负号, 并改变一下预测更新的顺序就可实现, 其算法复杂度和正变换的算法复杂度相当。

5/3小波滤波器如下:

对5/3小波滤波器的多相位矩阵进行因式分解得到其Z域表达式为:

其中τ=-0.5, υ=0.25, 。

通过提升算法, 并将算子 (下取整算子) 作用于每个提升步骤中且忽略归一化因子即可得到JPEG2000标准中推荐的5/3小波的提升实现的整数形式:

式 (9) 至式 (10) 为一次提升的表达式, 其实现流程图如图1所示。同时, 改变更新和预测的顺序并将图中减号改成加号即可实现逆小波变换, 计算复杂度和正小波变换完全一样。

5/3提升算法核心代码如下:

2 集合树分裂算法 (SPIHT)

SPIHT算法的基本思想是:伴随着一个集合的分裂, 依据幅值大小对系数进行排序并且对重要的比特位平面优先传输。整个算法分为初始化、排序、细化和阈值更新四个步骤。

SPIHT算法采用如下集合定义表示层次树结构 (为简单起见用 (i, j) 表示坐标 (i, j) 位置上的小波系数) :

(1) O (i, j) :结点 (i, j) 所有直接后代组成的集合;

(2) D (i, j) :结点 (i, j) 所有后代系数组成的集合 (D型)

(3) L (i, j) :L (i, j) =D (i, j) -O (i, j) , (L型) ;

(4) H:树根结点。

重要性测试:

即定义函数Sn (T) 指示集合T的重要性, 重要则其值为1, 否则为0。

建立3个链表LIP, LSP, LIS分别存放不重要系数、重要系数和不重要集合。在LIS中, 节点 (i, j) 代表集合D (i, j) 或L (i, j) , 并分别标记为D型与L型以示区分。

对于给定阈值T, SPIHT算法排序过程如下:

首先, 检测LIP中各系数的重要性, 输出测试结果, 如果重要则一并输出其系数正负符号;

其次, 对LIS中的各项 (i, j) 做如下操作:

若为D型集合, 输出Sn ( (i, j) D) , 如果Sn ( (i, j) D) =1, 则将D (i, j) 分裂为O (i, j) 和L (i, j) , 并分别处理。对O (i, j) 中的各个系数检测其重要性并输出结果, 重要则加入LSP, 不重要则加入LIP;如果L (i, j) 不为空集, 把L (i, j) 项移至LIS表尾并标记为L型, 若为空集, 则直接将其从LIS中删除;

若为L型集合, 输出Sn ( (i, j) L) , 如果Sn ( (i, j) L) =1, 则将L (i, j) 分裂为以O (i, j) 中各结点为根的树, 并将根结点坐标加入LIS中标记为D型。

细化过程输出LSP中除当前排序过程得到的系数以外的各系数的当前位平面值。如果没有达到要求的码率且量化阈值大于0, 则阈值减半 (n=n-1) 重复上述排序和细化过程, 直到编码完成。

SPIHT算法的伪码描述如下:

1) 初始化

2) 排序扫描

2.1) for each entry (i, j) ∈LIP do:

2.1.1) output Sn (i, j) ;

2.1.2) if Sn (i, j) ==1then move (i, j) to the LSP and output the sign of ci, j;

2.2) for each entry (i, j) ∈LIS do:

2.2.1) if the entry is of type D then

2.2.2) if the entry is of type L then

3) 细化扫描

for each entry (i, j) ∈LSP, except those included in the last sorting pass, output the nth MSB of|ci, j|;

4) 阈值更新

decrement n by 1 and go to Step2。

3 系统分析与实现

我们在VC++6.0环境下对上述无损压缩方案进行了仿真。在对耦合图像进行无损压缩和解压时我们发现, 耦合图像的压缩比均低于标准测试图像的压缩比 (如表1所示) 。而当对其采用有损压缩时, 即使控制为很低的压缩比, 解压的耦合图像也出现了明显的失真, 重构图像如图2所示, 这将严重影响后期的处理。所以系统在对光纤耦合图像进行压缩编码前, 需先对其做预处理以提高压缩比。我们加入如下预处理模块来改善压缩效果:

(1) 图像分割

将图像划分为大小相等的若干区域, 对每一个区域独立进行压缩处理。这样不仅可以较好地避免处理过多的图像断层而引入的边界细节信息, 还可以降低压缩过程中的内存需求。

(2) 直流电平 (DC) 移位

在对图像原始数据进行采样时, 将采样精度为p的无符号整数减去2p-1, 使原来位于[0, 2p-1-1]范围内的样本移位到关于0对称的范围[-2p-1, 2p-1-1]内。比如, 处理的是8 bit的BMP格式的图片, 图像数据分布在[0, 255]区间, 通过直流电平移位处理, 图像数据分布在[-128, 127]区间。这在简化处理数值溢出等问题的同时不会影响编码的编码效率, 与此同时比特率还有略微的提高。

图3给出了系统的信号流程图。

4 实验结果及结论

实验选取的双正交5/3整数小波变换, 采取对称的周期延拓方式, 分解级数为5级。在算法性能的度量上, 我们采用压缩比作为系统压缩性能的评价依据;选用波特率作为系统传输效率的评价标准。压缩率定义如下:

为了验证压缩方案的可行性, 我们先在PC机上对算法进行了仿真。在配置信息为Intel Core2 Dou CPU 2.80GHz、3GB内存、windows XP环境下的Visual C++6.0开发环境下, 我们将成像系统采集的图像转换为2562568 bit的bmp图, 同时采用了标准的2562568 bit lena.bmp, gold hill.bmp, mandill.bmp, barbara.bmp图像用于对比, 压缩比如表1所示。从表1中可以看出, 耦合图像由于纹理细节丰富, 压缩比极低, 不宜于直接压缩, 同时若对图像进行低压缩率的有损压缩, 重构图像 (如图2所示) 表现出了明显的失真。

压缩系统信号流如图3所示。我们加入了文中的预处理模块先对图像进行预处理, 设定的图像分割的区域大小为500470 (像素) , 总计256个序列单元 (全图空间分辨率8 0007 520) 。随机抽取了9张分割的耦合序列图, 对其进行解压重构 (如图4所示) , 并分别计算它们的压缩比 (如表2所示) , 可以看到压缩比较表1中的耦合图像压缩比有了很大程度的提高。然后我们对全部的压缩后的序列图进行解压并拼接重构, 256张 (500470) 耦合图像序列解压后拼接还原的图像 (8 0007 520) 如图5所示。对比图2和图5我们可以看到, 图5实现了完全重构。图4中的各图像区域也都实现了无损重构, 且各区域的压缩比相比表1中的数据均有提高, 通过统计计算, 各分割区域的平均压缩比达到了2.3, 同时图像分割更便于硬件实现。

实验结果表明, 解压的图像能完全重构, 且未出现数据丢失不能重构图像的现象。经计算系统平均压缩比达到2.3以上, 传输波特率降到了200 Mbps, 说明本文无损压缩编解码器的引入, 解决了传输系统带宽不足的问题, 并保证了图像最终的完全重构。

参考文献

[1]安博文, 崔安杰, 薛冰玢, 等.光纤耦合的亚像元超分辨率扫描成像图像处理[J].红外与激光工程, 2012, 41 (4) :1107-1112.

[2]安博文, 陈桂林.光纤耦合系统中非均匀性校正[J].红外技术, 2007, 29 (5) :262-264.

[3]Shapiro J M.Embedded Image Coding Using Zerotrees of Wavelet Coefficients[J].IEEE Trans.Signal Processing, 1993, 41 (12) :3445-3462.

[4]Said A, Pearlman W A.A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees[J].IEEE Trans.Circuits and Systems for Video Technology, 1996, 6 (3) :243-250.

[5]Taubman D.High performance scalable image compression with EBCOT[J].IEEE Trans.Image Processing, 1999 (3) :344-348.

[6]Skodras A, Christopoulos C, Ebrahimi T.The JPEG-2000 Still Image Compression Standard[J].Signal Processing Magazine, IEEE, 2001, 18 (5) :36-58.

[7]Sweldens W.The Lifting scheme:A custom-design construction of biorthogonal wavelets[J].Appl Comput Harmon Anal, 1996, 3 (2) :186-200.

[8]Adams M D.Reversible integer-to-integer wavelet transforms for image coding[D].University of British Columbia, 2002.

[9]钱昌松, 刘志刚, 刘代志, 等.基于可逆整数小波变换的图像无损压缩[J].计算机工程与应用, 2004 (23) :89-91.

扫描算法 第6篇

QR Code具有高密度编码,信息容量大,纠错能力强,易制作等特点[1],被越来越多地用于各种商品中。目前,智能手机也推出了多种QR Code扫描识别APP,大多数扫描方式是使用摄像头来进行QR Code扫描,这种方式在处理中,需要经过对焦,扫描,识别等步骤。使用摄像头扫描QR Code具有很多缺点,在环境光线较弱时,摄像头扫描有局限性;摄像头扫描数据是YUV格式,在图像预处理过程中,需要将其转换为灰度图像才能进行后续处理[2];摄像头由于其本身会给扫描到的图像带来畸变,运算量较大。为此,本文提出使用CIS代替摄像头进行QR Code的扫描。CIS是一种光电转换器件,它将光直接打在物体上,根据收集到的反射光的强度转换为不同的模拟电平值输出。CIS自带光源[3],对环境光不敏感,扫描图像时无需对焦,使用方便。CIS扫描得到的数据直接代表灰度值。针对CIS的特点,本文提出一种QR Code图像识别的算法,在扫描上,根据手的滑动速度不均匀,会给图像带来非线性拉伸,但在扫描垂直方向上,无非线性形变,仅存在线性等比例缩放,因此在处理过程中,可以省略传统的图像校正和旋转算法,省略大量图像存储空间和浮点运算量,实现基于CIS的QR Code的扫描和识别。

1 接触式图像传感器

工作时序如图1所示。

2 系统算法设计

2.1 图像采集时序

CIS在500k Hz工作时钟下,通过控制SI信号和单色红光光源LEDr信号,每次最多可采集一行784个像素值[4]。

2.2 二值化

使用bitband方式存储图片,CIS获取的784个byte中,取每个byte中的最高一位bit放在bitband中,实现二值化,如此,实现了用1个byte代替8个byte,节省内存。

设图像大小为Px×Py,其中Px和Py分别为图像的宽和高,则存储图像所需内存大小为:

采用bitband方式存储图像后,内存占用情况为:

图像存储占用空间减少到原来的1/64。

2.3 确定旋转角度

为了减少运算量,不对图像进行旋转,而是直接在当前角度进行采样,获取整张QR Code中的各点像素值。

其中,确定旋转角度的算法为:

①遍历数组,找到第一个白到黑的跳变点后,在其8邻域内寻找黑到白的跳变点,记录下每个白到黑和黑到白的跳变点。

②用坐标中相对较大的减去坐标中相对较小的,得到黑块和白块的像素个数,如果黑块和白块之间的比例满足1∶1∶3∶1∶1且间隔交替出现的话,就说明明找到了定位符。根据三个点的坐标可以确定出图像的旋转角度[5]。

如图2所示。图中A点是第一个出现的黑块到白块的跳变点,B点是第二个白块到黑块的跳变点,C点是第二个黑块到白块的跳变点,设A点坐标为(X0,Y0),B(X1,Y1),C点(X2,Y2),则可得到如下两个向量:

两向量之间的夹角为:

由此可确定图像的旋转角度,为了减少运算量,不对图像进行旋转,而是直接在当前角度进行采样,即可获取整张QRCode中的各点像素值。

2.4 除去图像厚度以及图像滤波

CIS采集得到的图像中,每个黑块和白块都由许多行像素组成。如图3所示,图中黑块代表QR Code的比特1,白块代表QR Code的比特0。

将其中一个比特0单独抽出来,像素组成如图4所示。

以左上角为原点,建立向右向下的坐标系,显然,(3,1)和(1,2)属于图像噪点。如此,在竖直方向上,即可确定出每3行图像属于QR Code中的同一行,在水平方向上,可确定出每一行中0,1比特的构成。由于手动扫描的速度不同,因此,构成QR Code每行的CIS数据量不一定相同,因此,需要判断哪几行可归为QR Code的同一行。如图5所示。

判断条件为前后两行图像数据如果存在连续5个像素值不同时,认为这两行属于QR Code的不同的两行,如图5所示,可认为第1,2,3行图像数据属于QR Code的同一行,第4,5,6,7,8行图像数据属于QR Code的同一行,如此就除去了图像在竖直方向上的厚度,也达到了降噪的目的。

图像在水平方向上的厚度需要通过遍历图像数组来消除。遍历图像的每一行,寻找黑到白的跳变点和白到黑的跳变点,图像扫描的第一行是QR Code的定位符的第一行[6],在低版本21*21的QR Code中,固定为7个比特1,如图6所示。

第1,2,…,29个像素代表7个比特1,第30,31,32,33个像素代表1个比特0,当且仅当连续4个像素值为0,其后连续4个像素值为1时,认为是黑到白的跳变点,白到黑的跳变点采用同样的方法,记录下各个黑到白和白到黑的跳变点,用第一个黑到白的跳变点除以7[7](根据不同尺寸QR Code规定),即可得到水平方向上每个比特由多少个像素代替,对以后每一行用这个标尺进行等比例缩减,得到每一行的0,1比特流,最终得到的是和QR Code尺寸相同大小的一个比特流数组。

2.5 比特流译码

遵循以下步骤,寻找定位符,获取格式信息,消除掩模,RS纠错,分割译码[2]。具体流程如图7所示。定位符如图8所示。

其中定位算法可描述为:

①如图7所示,设水平扫描线11与定位图形黑白跳变沿的交点为p11,p12,p13,p14,p15,p16,垂直扫描线12与定位图形黑白跳变沿的交点为p21,p22,p23,p24,p25,p26。

②p11,p21,p16,p26应处于同一连通域边沿上,p12,p22,p15,p25应处于同一连通域的另一个边沿上,p13,p23,p14,p24应处于另一连通域的边沿上。

③本算仅仅跟踪连通边界而不连通边界,因此可省略大量处理空间和运算量。以任意一个边界位置的黑点为起始点,对其八邻域进行逆时针搜索,找到由黑到白的跳变点。

④将搜索点移动至上一搜索到的跳变点,进行八邻域边界搜索,反复执行,直到搜索点回到起始点或搜索次数已超过预先设定的最大值。

3 结束语

测试不同的QR Code正确译码率如表1所示,在实验室环境下测得该算法准确识别率约为78%左右。

与传统QR Code译码算法相比,本方案中提到的算法主要有以下特点:

①根据CIS采集到的数据,使用bitband方式存储,节省内存开销。

②图像滤波算法与除去图像厚度同时完成,算法高效。

③只需处理CIS带来的线性形变,提高处理速度。

④图像旋转部分没有直接对图像进行旋转和校正,而是根据定位符计算出一个旋转的角度以后,对图像进行当前角度旋转下进行采样,如此减少了浮点运算。

参考文献

[1]龙清清.基于二维码识别的Android智能手机导游系统研究[D].杭州:中国计量学院,2013.

[2]王素玉,沈兰荪.基于对象的视频编码技术[J].测控技术,2006,25(5):20-23.

[3]段俊欢.基于CIS的图像采集处理设备的硬件设计与实现[D].广州:华南理工大学,2013.

[4]关振明.基于CIS的图像采集处理设备的系统软件研究[D].广州:华南理工大学,2013.

[5]牛风慧.基于内容的图像非等比例缩放和图像旋转[D].上海:华东师范大学,2012.

[6]宋晓甲.基于嵌入式图像采集处理的QR码识别系统的研究[D].天津:天津大学,2010.

扫描算法 第7篇

交叉点检测是图像处理中一项重要的内容,为图像的特征提取、图像理解提供了重要的参数和依据[1]。传统检测算法在对待测图像扫描检测的基础上,得到一组点的集合,并认为这组点就是待测图像中的交叉点。这种检测算法的核心思想主要是通过判断图像非零像素8邻域内值的变化次数来判断该像素点是否为交叉点,但通过对已有算法的实验、研究和分析,发现该方法并不能获得完整的交叉点的集合,而且会出现直观认识中的一个点对应目标集合中多个相邻点的情况,准确性不够,需要改进。

2 二值图像中交叉点的检测

目前交叉点检测问题在计算机视觉领域还是一个没有完全解决的问题,主要有以下传统的检测算法[1][2]:

如图1所示,设p点为一目标像素点,p1,p2,,p8分别表示p点周围8邻点的像素值,定义:

如果Tdot1(p)(以下简称T1)的值等于1,则该点为端点;如果T1的值等于2,则该点位内点,如果T1的值等于3,则该点位交叉点。扫描图像中的每个点并进行交叉点的判断,从而得到这幅二值图像中的交叉点的个数。

根据本算法,对图2进行检测的结果为图3所示,第一列为交叉点的序号,第二列为交叉点的横坐标,第三列为交叉点的纵坐标。

提出问题:从图2中,我们可以得知交叉点个数总共为9个,但得到的结果却只有7个交叉点,显然与我们所想要的正确结果还是有出入的。经过对结果和图像的分析研究,发现:

1)结果中有的点是相邻的。例如第3、4点就是横坐标相同,纵坐标只相差2的相邻点。对这两点周围像素放大后如图4所示:

在直观视觉中,一个交叉点却对应了实际检测结果的两个点,而且,我们可以看出,这两个点其实都不是最合理的交叉点位置。

2)再看结果中最后两点,我们发现,两点是相邻点,因为相邻店间最多有一个交叉点,故此,这里就出现了一个错误。

3)直观视觉中对应的某些点此算法并没有检测出来,所以有了得到的结果和真确结果之间的出入。

对点(49,150)周围的像素进行局部放大后,得到图5如下所示:

经过对图5的观察可知,尽管很明显这是一个交叉点,但是该点及其周围任意一点都没有出现在检测结果中。这样就导致了检测结果的丢失。

4)同样的,对(76,53)和(71,71)两个点周围像素放大后(结果如图6所示),我们发现:直观视觉中的两个十字形交叉点也并没有出现在检测结果中。

3 改进算法的描述与分析

3.1 算法描述

根据以上的研究和分析,本文提出改进的交叉点检测算法的具体步骤如下:

输入:一幅线宽为一的二值图像。

输出:交叉点的集合。

(1)根据式(2),从上到下、从左到右扫描目标点,计算每个目标像素点的Tdot2(p)(以下简称T2)值,如果某点的T2值等于3,则将该点的坐标加入crn3集合中,如果某点的T2值等于4,则将该点的坐标加入crn4集合中,如果某点的T2值等于5,则将该点的坐标加入crn5集合中。

(2)如果crn4集合中某点8领域内没有任何一点在crn4集合或crn5集合中,则从crn4集合中去除该点。

(3)如果crn3集合中某点8领域内有一点属于crn4集合或crn5集合,则从crn3集合中去除该点。

(4)如果crn4集合中某点8领域内有一点属于crn5集合,则从crn4集合中去除该点。

(5)分别对crn3集合、crn4集合、crn5集合中一段相邻点之间取一点,删除剩余的点。选取的原则如下:

ⅰ、若某点8领域内的值呈中心对称,则取该点,舍弃其余各点;

ⅱ、若任意一点8领域内的值都不呈中心对称,则取此段相邻点的中间点。

(6)整合。将crn3集合、crn4集合、crn5集合合并为cross集合。

3.2 算法分析

本文提出的算法与传统算法相比,有以下不同:

a)由于计算方法的不同在T2值的计算过程中,不仅记录的T2值等于3的点的集合,同时也记录T2值等于4和的T2值等于5的点的集合。因为我们从图4和图5的示例中可知,交叉点的T2值也有可能是4或者5。如果仅仅记录等于3的点,那么结果必然是不完整的。

因为在直线的交叉点上,我们可知,任意的3*3像素区域内,最多只有6个目标点。故任意一点的T值最大为5,所以在做直线的交叉点检测时,我们只记录T值为3、4、5的点的集合即可。而在做非直线的交叉点检测时,则需记录T值为6、7和8的点的集合。并对算法的(3)、(4)、(5)做相应的修改即可。

b)通过增加步骤(2),我们就保证了当某一直线的端点和另一直线的内点相接时(图3所示),不会错误的将T值为4的点误认为是交叉点。

c)步骤(4)和(5)保证某一区域内只记录一个交叉点。这样就有效的解决了现实中的一个交叉点在二值图像中对应检测结果中多个点的情况。使得计算结果更贴近实际。

d)可以有效检测十字形交叉点并准确记录其位置。

4 实验结果及分析

为验证算法的性能,我们应用本算法对图7(a)所示的图像进行实验。对图像进行灰度化、二值化[3]、细化[4]处理后的结果如图7(b)所示,所得到的交叉点位置坐标如图7(c)所示。

从实验结果可知:(1)改进后的算法很好的解决了传统算法检测结果与实际情况不相符合的问题。(2)检测结果(交叉点的数量和位置坐标)更加完整准确。(3)本算法第2步使得一直线端点与另一直线内点相接时,所记录的交叉点位置更加精确。(4)引入的算法步骤4和5使得相邻某一区域中不再记录多余的交叉点。从图7(d)各交叉点位置坐标中我们可以看到,所有的交叉点的位置都是不相邻的(即两两交叉点的横纵座标的差的绝对值都不小于5)。(5)改进后的算法考虑了几乎所有可能出现的情况,检测结果符合人们的直观视觉。检测结果准确、有效。

5 结束语

交叉点的检测是图像处理领域中的一个非常重要的内容。本文提出的改进的交叉点检测算法,从人的直观视觉的角度,结合传统算法的特点,扩展并改进了传统算法。改进后的算法不仅解决了传统算法检测结果中多个点对应直观视觉中的一个点的情况,而且扩展了检测结果,能很好的检测出各种角度交叉所成的交叉点,所检测的交叉点位置比较准确。实验结果表明,新算法实用性强、准确性高。

参考文献

[1]王福生.基于纹理与形状特性的鞋底花纹自动识别算法的研究[D].大连:大连海事大学,2006.

[2]H FREEMAN.Boundary Encoding and Processing[A].B SLipkin,A Rosenfeld[C].Picture Processing and Psychopictorics,Academic,New York,1970.241-266.

[3]RAFAEL C GONZALEZ,RICHARD E WOODS.Digital Image Processing 2nd Edition[M].北京:电子工业出版社,2003.