快速二维（精选五篇）
快速二维 篇1
关键词：环,快速选取,自动识别
0 引言
二维图形处理中,环是基本的单元,环是由一系列首尾相连的几何元素(直线、圆弧和曲线)构成。其中环的起点和终点相重合的环称为闭环,如何在这些几何元素中快速选取所有的闭环,以及环的自动判别是二维图形处理的关键。
在传统的环选取采用的是遍历查找的算法,对每一个几何元素的起点和终点进行判别,从而获得图形区域中的所有闭环。由于采用遍历的方式,以及点比较中的大量的浮点运算,所以速度较慢。本文按照离散的思路,首先将二维图形区域离散成m×n的矩阵网格。将几何元素的起点和终点转化成网格的索引值,根据索引值可以快速定位到同一网格内的所有几何元素。只要将同一网格内的元素进行判断,就可以得到所有的闭合环。从而将大量的浮点运算转化为整型运算以及较少量的浮点运算。另外环的识别是指根据所有闭合环的关系(相交、包含、被包含、相离)采用递归调用的方式,自动生成环关系的树状拓扑图。
1 环的快速选取
本文从环数据结构定义出发,给出了一种快速选取闭合环的解决方案。
1.1 环数据结构定义
几何元素类为CLine,CArc,CSpline,CCircle都继承于几何元素基类CEntity类,基类中有几何元素的起点和终点信息。将这些信息根据其元素索引值按序添加到环的数据结构中。元素类型和索引信息组成的数据结构为CRun。
Loop为环的数据结构,包含了所有的几何元素的类型和索引信息。
1.2 矩阵网格划分与数据结构定义
根据图形的细密程度,设置离散精度d。d值越大,同一个网格内几何元素的起终点个数越多,判断时间越长;若d值太小离散量则太大,运算速度反而会减慢;所以在综合考虑上述两项因素的基础上,设置最佳d值。使得每一个矩形网格内只有两个几何元素的起点或终点。根据d值将图形离散成m×n矩阵,并定义如下包围盒数据结构。
图1所示为二维图形的矩阵网格划分。闭合环有四段直线、一段圆弧、一段样条组成。将这些几何元素的起点和终点信息同精度d值相除取整后的值作为包围盒的索引值,将这些几何元素添加到相应的包围盒中,供快速选取时使用。为了快速选取图中的闭合环信息,处理过程如图2所示。
1.3 处理过程
选中某一几何元素后,以该元素的起点为环的起点,根据该起点同精度d相除取整值作为包围盒的索引值,根据索引值获得包围盒中所有的几何元素的点信息,遍历查找包围盒内重合点。若存在重合点,则以该重合点所在几何元素的下一点同精度相除,取整后得到下一个包围盒的索引值,继续查找遍历,直到没有重合点为止,并且判断重合点是否和环的起点重合,若重合则为闭合环,得到环中所有几何元素信息。
处理过程中将重合点的判断限制在包围盒内,从而大大减少了因判断重合点而需要的大量浮点运算。
①若当前点是几何元素的起点,则下一点为几何元素的终点,否则相反。
②在循环过程中,凡是被选中过的几何元素不进入下一轮循环。
使用该算法将浮点运算转化为整型运算可以降低因浮点运算而消耗的时间。提高了环选取得速度。
2 环的自动识别
环的自动识别是指二维图形中被选取的多个环之间的拓扑关系。主要包括:父子关系,兄弟关系两类。首先将所有的环转化成正则图形,所谓正则图形是指,任意两个环不相交。本文对相交环不处理。其次判断任意两个环之间的关系:兄弟关系、包含关系、被包含关系。比如有甲乙两个环,将甲环中每一个元素的起点和终点采用射线法同乙环比较,判断点是否在乙环内部。若在内部,则乙环包含甲环;使用同样的方法可以判断甲环是否包含乙环。若两环互不包含,则两环为兄弟关系。
如图3为某次选取环的顺序,4环和3环是两个父环,每个父环包含了若干个子环。子环中又有若干个兄弟环,比如环5和6;以及环2和环7。
定义如下数据结构
环的起始几何元素指针。
}contour;
首先将所有的环按选取顺序以单向链表的形式链接,并将每个环的兄弟环和子环设为空。同时定义1环为根环。如图4所示。
对根环及其根环右边的环(图3中为2环到7环)递归循环,定义如下递归函数。
contour* Get(contour*tree,contour* p)
{
……
switch(两环关系)
{
case相交:
出错处理并返回空。
case tree环包含p环:
如果tree环没有子环,则将p环作为tree的子环并返回tree环;若tree环有子环则:
tree→son=Get(tree→son,p);
返回根环。
case p环包含tree环:
p环的子环为tree环,并将p环作为新的根环。同时将p环同tree环的兄弟环递归比较,使p环的兄弟环为比较结果的返回值。
返回根环。
case兄弟关系:
若tree环的兄弟环为空,则将p环作为tree的兄弟环。否则将p环同tree环的兄弟递归判断,并将返回值作为tree环的新兄弟环。
返回根环。
}
………
}
通过对根环及其兄弟环的循环递归调用,可以将图4的单向链表处理成如图5所示关系。
图5显示了经过处理后各环之间的树状拓扑结构。根据树状拓扑结构可以实现对环的自动判断。
3 结束语
首先给出了一种新的快速选取二维图形闭合环的方法。选取多个环后不必人工去判断各环之间的关系,通过环之间的几何关系,自动识别出环的拓扑关系,并生成最终的树状拓扑结构。该方法已经在数控等离子切割系统中得到了应用。
参考文献
[1]谢叻,周来水,周儒荣.多型腔零件加工区域的自动识别和刀轨生成[J].南京航空航天大学学报,1998(8).
二维DCT快速算法及硬件实现 篇2
关键词：图像处理；二维离散余弦变换；流水线；并行处理
离散余弦变换作为频域变换最先在图像处理中的模式识别和维纳滤波提出，DCT广泛应用于图像压缩、语音压缩和数字水印等技术，JPEG(Joint Photographic Experts Group，联合图片专家组)、MPEG(Moving Picture Expert Group，运动图像专家组)、H.263和H.264等标准都采用了DCT技术作为压缩编码的主要方案。然而，DCT的算法复杂，如果直接进行计算，计算量很大。以8×8的图像块为例，若采用直接计算，那么进行二维DCT(2D-DCT)运算需要1024次乘法和896次加法[1]，难于满足实时处理的要求。考虑到DCT的正交性和对称性，人们提出了许多快速的算法。在这些快速算法中，一类是利用快速傅里叶变换 (FFT)来计算DCT，另一类是直接根据DCT的规律寻求快速算法。在第2类算法中，最常用的是采用行列快速算法，该算法首先逐行计算一维DCT，再逐列计算一维DCT，从而把乘法的计算量减少了一半，其算法规律性强，特别适合于DCT算法芯片的研制[2]。
1 二维DCT算法
对于一个大小为N×N的像素块来说，假设x(i，j)为输入的像素点阵数据，其二维DCT变换公式如下
由于系数矩阵全是浮点数，为了能用定点乘法器运算，将它们扩大26倍后再取整[4]。
3 硬件电路设计
3.1 硬件结构规划
由前面的算法可知，2D-DCT的实现可采用基于共享乘积因子的1D-DCT，采用行列分解的结构实现2D-DCT。如图1所示为基于一维DCT复用的二维DCT实现框图。
二维DCT被分解为两个一维DCT。首先进行的是列变换，此时输入数据首先经过输入控制模块进入1D-DCT模块，经过10个时钟周期后，将得到的1D-DCT系数写入转置矩阵，待8组1D-DCT系数全部输入转置模块后的下一个周期，开始行DCT变换。这时候矩阵转置模块中的数据按照行的顺序逐个读取出来，经过输入控制模块进入1D-DCT模块。1D-DCT模块处理完后再由转置模块处理得到2D-DCT变换结果Y，由输出控制模块控制产生输出Y。
3.2 二维DCT模块的时序规划
文中设计的二维DCT模块连续处理16组数据，即批处理两个8×8的像素块，这样二维DCT模块在128个周期内处理2组YCbCr，即在128个周期内处理6个Block(8×8像素块)。二维DCT模块中，各子模块的时序规划表，如表 1所示。二维DCT模块在128个周期内依次处理YCb，CrY，CbCr六个Block。
表中TZTZY/b表示对Y、Cb块依次进行一维DCT变换(Z)，转置(T)，一维DCT变换(Z)，转置(T)得到的二维DCT结果(TZTZY/b)，其他以此类推。
3.3 1D-DCT的实现
一维DCT模块中，乘法器采用基于查找表的三级流水线结构，这样做能在保证吞吐量的前提下合理降低乘法器的复杂性减小消耗的硬件资源；加、减法器中，从数据输入到数据输出需要1个周期，吞吐量为1data/sec。
设计乘法器时的三级流水线结构为：第一步将有符合数分成若干块，并寄存符号位以满足流水同步，第二步用前面若干数字块作为地址，查找固定系数的乘法表，第三步移位并相加输出结果。这样每一个乘法运算虽然要三个周期，但由于采用流水结构同样能达到1data/sec的吞吐量。
3.4 矩阵转置模块的设计
如图2所示，为基于移位寄存器的矩阵转置模块的实现框图f0，f1，f2，f3，f4，f5，f6，f7为输入数据，来自1D-DCT模块。F0，F1，F2，F3，F4，F5，F6，F7为矩阵转置模块的输出数据。基于移位寄存器的矩阵转置模块主要由8个移位寄存器组(8 depth shift registers-15 depth shift registers)、8个8输入的多路选择器(MUX)和一个地址发生及输出控制模块(AGOC)构成。
f0，f1，f2，f3，f4，f5，f6，f7为输入数据，来自1D-DCT模块。F0，F1，F2，F3，F4，F5，F6，F7为矩阵转置模块的输出数据。基于移位寄存器的矩阵转置模块主要由8个移位寄存器组(8 depth shift registers-15 depth shift registers)、8个8输入的多路选择器(MUX)和一个地址发生及输出控制模块(AGOC)构成。
1D-DCT模块同时并行处理8个像素，则8×8的像素块全部被处理需要八个周期。经过1D-DCT模块处理的八个输出数据直接分别进入八个移位寄存器组。当8×8的像素块全部处理输出后的下一个周期多路选择器在地址发生及输出控制模块的控制下产生转置输出。对应于F0的MUX的8个输入数据分别来自八个寄存器组的最后一个寄存器输出，对应于F1的MUX的8个输入数据分别来自八个寄存器组的倒数第二个寄存器输出，其他的以此类推。地址发生及输出控制模块产生的地址依次为0，1，2，3，4，5，6，7，作为多路选择器的选择信号。且各个MUX的sel信号为0时选中8 depth shift registers寄存器组中输出的数据，sel信号为1时选中9 depth shift registers寄存器组中输出的数据。其他的以此类推。
因为矩阵转置模块第一组输出数据的是原来从f0端口输入的八个数据，故第一组移位寄存器只需要八个寄存器，待来自f0端口的八个数据全部进入寄存器组的下一个周期便可产生转置输出。而第二个转置输出来自f1端口，发生在下一周期，故需要多加一个寄存器。以此类推，来自f7端口的转置输出对应的寄存器组需要15个寄存器。
4 FPGA实现与仿真结果
各模块都用StratixII族中的EF2S15F484C3器件为目标器件，在QuartusII中进行综合，综合策略为blance，设定工作频率为110MHz。2D-DCT模块的实质是用1D-DCT模块的复用来实现二维的DCT，那么，除设计出基于快速优化算法的1D-DCT模块，转置模块所消耗的器件资源也是需要重点考虑的问题，由上面的综合结果可知：1D-DCT模块消耗了器件17%的资源，矩阵转置模块消耗了器件7%的资源。如果直接用两个1D-DCT模块实现2D-DCT变换，则消耗的资源为41%，现在用基于1D-DCT模块复用的2D-DCT变换消耗的总资源为25%，这样节省了约40%的资源。
用RAW测试矩阵，在ModelSim中编写验证二维DCT模块的RTL代码，得到RTL仿真结果如图3所示。
如图4为二维DCT的Matlab仿真结果，以检验RTL仿真结果。对照两图可知硬件实现功能和时序的正确性。
5 结束语
文中研究了基于FPGA的二维DCT算法的芯片设计，并给出了具体的实现电路。由于采用了高度并行的流水线结构和基于寄存器整列的高效矩阵转置技术和1D-DCT的复用，整个设计方案获得了很好的性能，共同构造出完整的视频、图像处理芯片。
参考文献
[1] 沈兰荪，卓力，田栋等.视频编码与低速率传输[M].北京:电子工业出版社，2001.
[2] 李跃新，张吉烈.二维DCT并行流水线算法及FPGA实现[J]. 贵州大学学报(自然科学版)，2009，26(4)，82-83.
[3] 朱竹青，郭裕顺，覃兴.快速二维离散余弦变换的VLSI设计[J].机电工程，2010，27(7)，69-73.
[4] 沈斌. JPEG编码器的设计与优化[D].合肥:合肥工业大学，2008.
快速二维 篇3
二维激光摄像式传感器由面阵式摄像机(下文简称摄像机)及激光器构成。如图1所示,激光器发射扇形激光切面,若被测目标出现在扇形激光切面范围内,则会在被测物体表面形成一条激光轮廓线,摄像机主光轴与扇形激光切面呈固定夹角,摄像机实时获取目标轮廓图像信息,采用图像处理方式对目标轮廓线进行识别,同时,基于摄像机三角测距原理,对目标轮廓进行定位并测距。
二维激光摄像式传感器采用非接触式测量方式,具有量程大、精度适中等优点,基于二维激光摄像式传感器的工业检测系统被广泛应用于工件完整性、表面平整度及设备外形尺寸的测量。
采用二维激光摄像式传感器进行视觉检测,事先需要进行摄像机标定,标定示意图如图1所示。传统摄像机线性模型包括11个未知参数[1],求解过程较为繁琐,从工程和产品化的角度出发,标定方法应该在保证测量精度的前提下,尽量做到简便易行。一般来说,建立的摄像机模型越复杂,标定难度就越大,目前的锯齿靶法、拉丝法获得的标定点的数量有限,且操作不方便;利用交比不变性原理需要高精度的三维立体靶标,且同样存在标定点数量少的问题,因此并不适合现场快速标定[2~5]。
本文充分利用摄像机内部参数已知信息、激光标定平面与摄像机坐标系之间的相对位置关系,忽略摄像机镜头畸变、CCD芯片变形及主光轴偏心带来的误差影响,提出将摄像机主光轴与激光切面交点作为世界坐标系原点,从而大大简化了摄像机模型的数学表达式。
本文从摄像机成像原理出发,建立了基于透视变换的摄像机模型,提出了一种基于最小二乘法的二维激光摄像式传感器快速标定算法,并推导了该标定方法计算公式。通过标定试验,验证了该标定方法具有标定速度快、收敛性好的优点,对于标定速度及稳定性要求较高的应用场合,具有一定使用价值。
1 摄像机模型及标定方法
如图2所示,建立图像像素坐标系ORXEYE,(单位:像素);建立图像物理坐标系O1XY,(单位:mm);建立摄像机坐标系建立世界坐标系Ocxcyczc,(单位:mm);其中,将二维激光摄像式传感器激光切面所在的平面作为世界坐标系Owxwyw参考平面,将激光切面Owxwyw与摄像机主光轴Oczc的交点作为世界参考坐标系的原点Ow,Owyw//Ocyc,Owxw、Owzw分别与Ocxc、Oczc存在a夹角;
设像元尺寸为m,(单位:mm/像素);设焦距为f,(单位:mm);图像物理坐标系O1在图像像素坐标系ORXEYE中的坐标为(Cx,Cy),(单位:像素),(Cx,Cy)作为已知参数给出,设
OwOc为摄像机坐标系Ocxcyczc原点与世界坐标系Owxwywzw原点的距离,设z0=OwOc;
将图2三维空间示意图转换为图3中的二维平面示意图,如图3中所示,Owxwyw中任意一点坐标为(xw,yw,0)其在摄像机坐标系Ocxcyczc中坐标为:
由摄像机透视投影关系可得[7]:
将公式(2)带入公式(3),可得公式(4):
将公式(4)展开可得公式(5):
将公式(5)变形可得公式(6):
将公式(6)中的方程相加,可得公式(7):
其中,(xw,yw,U,V)为已知参数为未知参数,至此,二维激光摄像式传感器标定模型建立完成。
2 数值求解
整理公式(8)可得公式(9):
设A,B为如下参数矩阵:
由公式(9)、(10)、(11)可得公式(12):
至此,摄像机参数得出,将带入公式(6),已知世界坐标系中任何一点像素坐标(U,V),即可求得其在世界参考坐标系中的坐标,计算方法如公式(15)所示:
3 标定试验
为了验证该标定方法的可行性及标定精度,在专用的棋盘格标定板上进行标定试验,摄像机采用北京微视公司MVC1000SAM_GE30摄像机,分辨率为1280×1024;采用Kowa公司型号为LM12NCL镜头,镜头焦距为12mm;
标定板实测图像如图4所示,共标定17组数据,标定数据对(U,V)、(xw,yw)如表1所示。
图5、6分别为摄像机坐标系(U,V)与(xw yw)对应曲线,采用表1中17组标定数据对,采用第2、3节中的摄像机标定及计算方法,可得:
由公式(16),可得二维激光摄像式传感器在世界参考坐标系下的模型为:
将(U,V)带入公式(17),得到(xw1,yw1),设
(xw1,yw1)分别如图7、8所示,(∆x,∆y)分别如图9、10所示,由图9、10可知,采用文中所述的二维激光摄像式传感器快速标定算法,水平方向误差基本控制在3mm以内,垂直方向误差基本控制在1mm以内。
4 结论
本文针对二维激光摄像式传感器,提出将激光切面与摄像机主光轴交点作为世界参考坐标系原点,简化了摄像机模型数学表达式。利用摄像机成像原理,推到了基于最小二乘法的二维激光摄像式传感器快速标定方法,并进行了标定试验,获取了17组标定数据对,运用上述方法,对上述摄像机模型参数进行了求解,结果表明:该标定方法简化了标定过程,具有标定速度快,收敛性好的优点,标定误差分析表明:采用文中摄像机及镜头,水平方向误差基本控制在3mm以内,垂直方向误差基本控制在1mm以内。
摘要：本文针对二维激光摄像式传感器应用环境,提出将激光切面与摄像机主光轴交点作为世界参考坐标系原点,简化了摄像机模型数学表达式,推导了基于最小二乘法的二维激光摄像式传感器快速标定方法,并进行了标定试验。试验结果表明:该方法简化了二维激光摄像式传感器标定过程,且具有标定速度快、收敛性好的优点,水平方向最大标定误差、垂直方向最大标定误差基本控制在3mm和1mm以内。
关键词：摄像机,二维激光,标定,视觉检测,最小二乘法
参考文献
[1]Z.Zhang,A Flexible New Technique for CameraCalibration[J],IEEE Trans.Pattern Analysis and MachineIntelligence,2000,22(11),1330-1334.
[2]徐光,刘立峰,曾建超,等.一种新的基于结构光的三维视觉系统标定方法[J].计算机学报,1995,18(6):450-456.
[3]段发阶,刘凤梅,叶声华.一种新型线结构光传感器结构参数标定方法[J].仪器仪表学报,2000,21(1):108-110.
[4]周会成,陈吉红,周济.标定线结构光视觉测头基本参数的一种新方法[J].仪器仪表学报,2000,21(2):125-131.
[5]周富强,张广军,江洁.线结构光视觉传感器的现场标定方法[J].机械工程学报,2004,40(6):169-173.
[6]方帅,曹洋,徐心和.一种非标定摄像机的定位新算法[J].仪器仪表学报,2005,26(8):845-848.
快速二维 篇4
阵列天线广泛应用于雷达无线通信和电子对抗等领域方向图综合作为阵列天线的关键技术在抗干扰参数估计等方面有着重要的作用.文献[1-4]通过粒子群优化算法对电流幅值和相位的连续值进行优化取得了不错的效果.但在实际应用中可以分别使用数字衰减器和数字相移器对电流幅值和相位进行量化比如文献[5]用粒子群优化算法对阵列天线电流相位进行量化优化文献[6]中用改进的遗传算法对连续的电流幅值和量化的电流相位进行优化文献[7]中对连续的电流幅值量化的电流和6位相位进行优化同时为了减少相邻阵元间耦合的影响在目标函数中加入了阵元电流幅值动态范围比文献[8]中用克隆选择算法对连续的电流幅值和量化的电流相位进行了优化得到了不错的阵列天线方向图文献[9]中用蜜蜂算法对量化的电流幅值和量化的电流相位进行优化该文献把幅值和电流都离散化取得了不错的效果。
粒子群算法 (Particle Swarm Optimization) 是由James kenny和Russell Eberhart在1995年提出的一种基于种群搜索的智能优化算法[10], 其一经提出就广受学者们重视, 其广泛的应用于电磁优化计算问题。
2 二维螺旋阵的综合
本文的思想是将螺旋天线的远场处的三维电场场强用神经网络拟合, 通过训练的神经网络以及阵列综合理论, 求和阵列特定方向的电场作为粒子群算法的适应度值, 迭代粒子群算法, 寻求在特定方向上电场最大, 所对应的每个天线阵元的幅值和相位。基本步骤为:
(1) 使用仿真软件计算螺旋天线, 导出远场处每个角度所对应的电场大小;将角度作为输入参量, 电场大小作为输出参量, 训练神经网络;
(2) 对于特定的输入角度, 通过神经网络得出其对应的电场大小, 将每个天线阵元的幅值和相位分别作为优化变量, 使用粒子群算法求解最优解;
(3) 将粒子群算法最优粒子对应的每个天线阵元的幅值和相位输出。
其中, 粒子群算法的适应度函数为:
这样在外界给出一个需要天线阵进行最大功率辐射的角度后, 即可通过上述方法实现快速的复制和相位的调节。
3 仿真与计算
本文采用的螺旋天线如图1所示, 其为等角螺旋天线与阿基米德螺旋天线结合型天线, 并在其外圈辅以2个圆环以提高圆极化特性。使用HFSS仿真软件进行仿真计算, 其远场电场场强分布如图2所示。将角度作为输入参量, 电场场强作为输出参量, 训练神经网络, 这里神经网络使用了matlab工具箱, 采用lm学习规则, 5000次训练迭代, 训练过程如图3所示。
采用10×10的二维天线阵列, 分别在θ=0deg, φ=30deg, φ=0deg, θ=30deg做了两组优化综合, 粒子群适应度函数变化趋势如图4, 图5所示。
4 结语
本文提出一种使用神经网络结合粒子群算法完成二维天线阵快速响应综合的方法, 该方法中, 使用神经网络拟合天线远场电场场强, 通过粒子群算法优化得到特定角度的场强最大值。方法与传统的天线阵综合法相比, 将天线的远场场强考虑在阵列综合之内, 而不是范范讨论不存在的全向天线综合。
摘要：本文通过神经网络建模拟合螺旋天线远场电场场强, 使用粒子群优化算法, 完成螺旋天线二维阵列的快速综合。与传统的讨论理想全向天线相比, 本文将天线的场分布考虑在了天线综合之中, 更具有实际运用价值。本文在10×10螺旋天线阵, 频率2GHz, 间隔75mm的条件下, 计算了螺旋天线阵幅值和相位。
关键词：神经网络,粒子群算法,天线综合
参考文献
[1]KHODIER M, CHRISTODOULOU G.Linear array geometry synthesis with minimum side-lobe level and null control using particle swarm optimization[J].IEEE Trans.AP 2005, 53 (08) :2674-2679.
[2]金荣洪, 袁智皓, 耿军平等.基于改进粒子群算法的天线方向图综合技术[J].电波科学学报, 2006, 21 (06) :873-878.
[3]焦永昌, 杨科, 陈胜兵.粒子群优化算法用于阵列天线方向图综合设计[J].电波科学学报2006, 21 (16) :16-20.
[4]李金金, 田雨波.基于量子粒子群改进算法的直线阵综[J].电波科学学报, 2012, 27 (02) :255-259.
[5]GIES D, RAHMAT-SAMII Y.Particle swarm optimization for reconfigurable phase-differentiated array design[J].Microwave and Optical Technology Letters, 2003, 38 (03) :168-175.
[6]BASKAR S, ALPHONES A, SUGANTHAN P N.Genetic-algorithmbased designed of a reconfigurable antenna array with discrete phase shifters[J].Microwaveand Optical Technology Letters, 2005, 45 (06) :461-465.
[7]PATHAK N, MAHANTI G, KSINHA MAHA-PATRA T K.Genetic algorithms for design of discrete phase-only reconfigurable array antennas with fixed dynamic range ratio[J].International Journal Infrared and Millimeter Waves, 2007 (28) :953-960.
[8]AKDAGLI A, GUNEY K, BABAYIGIT B.Clonal selection algorithm for design of reconfigurable antenna array with discrete phase shifters[J].Journal of Electromagnetic Waves and Application.2007, 21 (02) :215-227.
[9]GUNEY K, ONAY M.Bees algorithm for design of dual-beam linear antenna arrays with digital attenuators and digital phase shifters[J].International Journal of RF and Microwave Computer-Aided Engineering.2008 (18) :337-347.
快速二维 篇5
目前,应用比较广的定位方法中利用码盘、加速度传感器等实现的被动式传感器定位方法的优点是成本低、可靠性高,但是不可避免地存在累积误差。主动式传感器定位方法中,路标定位是常用方法,该方法运用灵活、精度高,但是路标识别的效率是研究的难点。
1 二维码定位和识别技术概述
本文选取了贴于家居环境地板上的二维码[1]作为路标,每个路标处的二维码的码值即为该点的坐标值。该方法能够及时校正累计误差,确保定位精度。针对普遍存在于路标识别算法中效率低下的问题,我们提出了一种基于训练模型的几何特征提取的二维码快速识别方法。
2 二维码初定位方法改进
二维码作为路标使用时,通过图像处理对二维码进行定位和识别流程[2]的一般步骤是首先对二维码进行初定位,然后采用普遍应用的二维码识别技术[3]进行识别。本文通过改进初定位算法的速率来提升二维码识别和定位技术的时效性。
本文将二维码矩阵标签设计成矩阵阵列,向8个方向分别扩展了一个码的信息,增加了每个方向的容错能力。目前,普遍应用的传统的下采样灰度差分投影法[4]不能满足多码识别的应用要求。本文以二维码的探测块作为初定位的识别目标,提出了一种改进的几何特征评价算子,提高了初定位的识别速率。
2.1 图像分割
2.1.1 阈值分割算法对比
图像分割是进行几何特征提取的前提。本文通过对几种阈值分割方法进行实验分析,提出了适合本文应用的实时性高并且降低非二维码区域噪声的阈值分割算法。
大津法[5]的基本原理是选取最佳阈值T将像素分为2个部分,使这2个部分类间方差取最大值。大津法中灰度变化较大区域的图像灰度值对最佳阈值的决定权也较大,但是对于图像中灰度分布的区域特征及灰度分布不均这些因素没有设置评价函数进行克服。因此,大津法使用过程中对于灰度分布不均的现象会发生阈值分割失败。
简单统计法[6]的原理是将每一点对分割阈值的贡献权重用每一点邻域梯度值占梯度累加总和的比重来代替,进而计算出最终阈值。
综合表1的时间效率对分割效果对比,可以看出大津法运行速度快、效果稳定,但是自适应能力有待改善。简单统计法速度较慢,但是对单一码阈值选取效果好,可以在对速度要求不高的训练学习模型中作为阈值选取算法。
2.1.2 改进的基于阈值训练模型的自适应变阈值分割法
本文在传统算法的基础上给出了一种以大津法为主体,结合训练模型的自适应变阈值分割算法,而且由于训练信息的引入缩小了大津法阈值选取的初始区间,进一步提升了阈值选择的速率。本文论述改进的阈值分割算法中的训练模型。首先对图像分区,然后采用简单统计法对训练样本中的每个单个二维码进行阈值选取,获得单个二维码的码上最优阈值。按照分区统计每个区域最优阈值的最大值Tmax和最小值Tmin。
区间[Tmin-a×T255,Tmax+a×T255]中a的取值根据训练样本与系统真正运行时的实验图像的新旧差距决定。如果新旧差距大,则a值选取大;反之,a值选取小。根据本文的实验环境,新旧差距较小,设置a取0.2效果较好。
区间[Tmin-b×T255,Tmax+b×T255]中b值取值要求小于a值。对经过前一步筛选出来的阈值进行进一步的筛选。本区间用于为最优阈值的选取提供参考区间,去除掉根据训练信息判定的不可能作为阈值区间的候选阈值。本实验环境中b取0.1,得到了较好的实验效果。
改进的结合训练模型的阈值选取算法的总体流程如图1所示。首先在每个区域训练得到的初始区间[Tmina×T255,Tax+a×T255]的指导下进行分区大津法阈值统计,获得该区域的最优阈值。然后将该最优阈值与训练获得的预选区间[Tmin-b×T255,Tmax+b×T255]进行比较,看最优阈值是否在该区间之内。如果在该区间之内,则认为该区域内二维码出现概率较高,并标记这样的区域为可能有码区域。在可能有码区域中遵从T3、T2、T1的优先顺序,选取该区域的最优阈值作为全局最优阈值,如果没有可能有码区域,直接选用T3区域的Tmin作为阈值对全图像进行分割。
2.2 基于训练信息的几何特征提取初定位算法
二维码的探测块中心是一个黑色正方形连通域,具有规则易于提取的几何特征。本文在对图像进行连通域分析的基础上,选用几何复杂度算子对连通域进行评判,进而定位二维码的探测块图形。
2.2.1 几何特征提取
首先对图像分割得到的二值图像进行游程编码[7],然后对团块进行连通域分析,简称BLOB分析。本文采取的BLOB算法是将目标像素聚合成连通的团块,并返回团块的面积、重心位置等信息。当团块面积S满足区间[Smin,Sman]时被标记为候选连通域和分别表示探测块的面积的上下限,是通过训练模型得到的探测块图形的先验信息。
对于前面获得的候选连通域可以用8邻域链码提取轮廓的边长。8邻域链码法就是用8个代码分别代表一个像素邻域内的8个像素,并用这8个代码组成的链码表示平面内连续的线条图像的编码方法[8]。以前述的BLOB连通域分析筛获得的重心点为搜索起点对连通域进行链码,得到链码信息。并近似认为边界上水平和垂直方向移动一个像素记为步长1,斜对角方向的一个像素移动设置为1.5。这样由链码就可以获得连通域边界的周长。
本文利用复杂度算子作为特征评价函数对不同形状的连通域进行区分。本论文选用的复杂度算子如公式(1),其含义是连通域周长的平方除以连通域的面积。
本文中的目标探测块为一个正方形,根据正方形周长和面积的关系,C取值为16。因为阈值分割可能会使得目标不是严格的正方形,复杂度算子的计算值可能会有误差,所以选用通过训练模型得到的复杂度算子的取值区间作为评价函数的评价区间。
2.2.2 几何特征训练模型
几何特征训练模型通过对待识别二维码标签的识别,获得其探测块中心正方形的面积和复杂度评价算子的取值,然后相应地扩展为一个评价区间,对候选连通域进行筛选。几何特征模型需要的学习参数都可以通过预先对二维码路标的训练学习获得。
3 实验结果与分析
本节采用下采样灰度差分投影法和改进后的算法进行实验,对比算法的时间效率和稳定性。随机选取250张实验图像进行算法时间统计,给出改进算法中各部分耗时的统计信息,见表2。
表3是传统算法与改进之后算法探测块初定位部分时间效率对比。可以看出改进之后的算法在运行速度较之传统算法实现了2～3倍的提升,同时错检率低于1%,能够稳定地为移动机器人提供地面坐标信息。
4 小结
本文根据二维码探测块的几何特征设计了基于训练信息的几何特征评价算子,能够快速地识别探测块的位置。目标分割过程中,在对大量阈值分割算法实验分析的基础上,提出了一种基于训练模型的自适应变阈值目标分割方法,克服了传统阈值算法的弊端,兼顾了系统稳定性、快速性和准确性的均衡。基于训练模型的几何特征识别定位算法的运行速度较之传统算法实现了2～3倍的提升,为二维码的快速定位和识别问题提出了一种崭新的解决方法。
参考文献
[1]Kato H,Tan K T.Pervasive 2D barcodes for camera phone applications[J].Pervasive Computing IEEE,2007,6(4):76-85.
[2]屈卫锋.低质量QR二维码快速识别与软件设计研究[D].成阳:西北农林科技大学,2016.
[3]胡秋玉.QRcode识别算法的研究与改进[D].成都:西南石油大学,2014.
[4]刘家听,刘家朋,赵宇明.基于边缘增强的二维码区域快速检测定位算法[J].Computer Engineering,201 2,38(12).
[5]王璇,张帆,程京.基于改进最大类间方差法的灰度图像分割[J].微计算机信息,2010,26(35):206-207.
[6]王成顺.表面缺陷检测GPU并行图像处理技术[D].合肥:合肥工业大学,2012.
[7]於正强.实时的图像连通域分析算法设计与实现[D].杭州:浙江大学,2014.