基于fpga的图像实时识别算法

基于fpga的图像实时识别算法

图像识别包括选择什么样的函数来描述图像，并将这些函数形成一个独特的函数，或至少与这幅图像和其他图像进行区分，以实现有效识别图像的目的。现场可编程门阵列(FPGA)设计的一般过程是:提出算法,然后评估实现算法所需要的硬件资源(估计需要多少乘法器,多少存储空间,共需多少Gate电路),最后是检验用软件实现的算法与用FPGA实现的算法结果是否匹配.其中关键的两条指标是:算法本身是否正确有效,以及算法是否足够简单,以至于能够用足够少的与非门来实现.由于实现算法所需的Gate数目直接和芯片成本相关,所以为了节约硬件资源,要尽量减少实现算法所需要的Gate数目.而乘法器和存储器的实现需要大量的门电路,比如说一个8位乘8位的乘法器需要513个Gate电路,相比之下一个8位加8位的全法器只需要48个Gate电路;另外,存一个8位的数据,需要8个Register,相当于65个Gate电路.所以,适合于FPGA实现的算法,就要避免使用乘法器,并且尽可能减少需要的存储器数量,这样才有利于降低实现算法所需要的Gate数量.本文考虑的识别对象是标准字体的阿拉伯数字(0～9)和大写英文字母(A～Z)(以下简称数字和字母).具体地说,已知需要判别的图像是数字和字母中的一个标准字体(比如说是72号字体的TimesnewRoman的印刷体数字和字母),并假设图像噪声只以少量的孤立点、小的孤立块两种形式存在.在分析数字和字母的形状特征后,本文提出了一种适于FPGA实现的实时识别算法:首先提出了一种能够表征数字和字母的特征向量,然后经过简单的运算,就可以准确地识别这幅图像.该算法的关键技术就在于:不仅能够保证高的正确识别率,而且算法的FPGA实现很节约硬件资源,且只需要很少的存储器,不需要乘法器.仿真结果表明,本算法不仅正确识别率高,并且所需要的计算量和存储量很小,能够用FPGA或者芯片来实现.1识别算法1.1“横”、“斜”和“弯”的构成阿拉伯数字0～9以及英文大写字母A～Z具有如下特征:(1)不同的数字和字母具有不同的形状以及不同的边界形状.(2)同一幅数字和字母图像,在不同的位置具有不同的边界特征.(3)数字和字母的每一个连通区域都由“横”、“竖”、“斜”和“弯”构成,并且不同数字和字母具有不同的“横”、“竖”、“斜”“弯”的比例.“横”、“竖”、“斜”和“弯”又具有不同的边界属性,如“竖”具有左右边界上下边界相等的特征.(4)数字0～9以及字母A～Z可以分为5个子集:镜像(原点)对称的子集G1;既左右对称又上下对称的子集G2;左右对称且上下不对称的子集G3;上下对称且左右不对称的子集G4;完全不对称的子集G5.其中:G1有3个图像元素,G1={N,Z,S};G2有6个图像元素,G2={8,0,H,I,O,X};G3有7个图像元素,G3={A,M,T,U,V,W,Y};G4有7个图像元素,G4={1,3,B,C,D,E,K};G5有13个图像元素,G5={2,4,5,6,7,9,F,G,J,L,P,Q,R}.1.2图像的二值化处理本文处理的图像是指质量基本良好的印刷体数字和英文字母灰度图像,因此可以假定存在的噪声只以少量的孤立点、小的孤立块形式存在,所以去噪算法就变得很简单了.可以采用如下法则:如果一个像素的上下左右相邻的像素都不为黑,认为是孤立点噪声;检验连通区域块的黑像素数少于图像像素总数的3%,认为是小的孤立块噪声.去噪后,对实时进入内存的像素做二值化处理,则二值化后像素点:f(x,y)={1g(x,y)≤ˉg0g(x,y)>ˉg其中:g(x,y)为像素的灰度值;ˉg为整幅图像的平均灰度值.经过预处理,整幅图像转变为二值图像,这为下一步的定位和识别提供了方便.1.3图像左边界逐行扫描整幅二值化图像,得到每一行中第1个像素值为1的点,以及最后一个像素值为1的点,它们的横坐标分别记为Start_X(i)和End_X(i),其中i是行号.比较所有的Start_X(i),得到最小值X1=min(Start_X(i)),即为图像中字符的左边界坐标;比较所有的End_X(i),得到最大值X2=max(End_X(i)),即为图像中字符的右边界坐标.同理,可以得到图像中字符的上边界坐标Y1=min(Start_Y(i)),图像中字符的下边界坐标Y2=max(End_Y(i)).因此,图像中的字符就包含在以(X1,Y1)和(X2,Y2)为对角顶点的矩形框内.令X0=X1+X22‚Y0=Y1+Y22得到矩形框的中心点坐标(X0,Y0),并把图像分成4个区域:一区X1≤x≤X0∩Y1≤y≤Y0二区X0≤x≤X2∩Y1≤y≤Y0三区X1≤x≤X0∩Y0≤y≤Y2四区X0≤x≤X2∩Y0≤y≤Y21.4图像边界属性的统计每幅二值图像都是由取值为1或0的像素构成,考虑2×2的像素块,有如下16种特征:用上述16种特征描述数字和字母的边界属性.简单分析后,就可发现去掉孤立点和孤立块噪声后的图像不会出现5#和10#.一般来说,1#和11#,2#和7#,4#和14#,8#和3#是相生相伴的,如:有多少个1#,就大致有多少个11#,都表示了图像具有“弯”的边界属性,另外,6#表示了左边界属性,9#表示了右边界属性,3#表示了下边界属性,12#表示了上边界属性.因此,图像4个区域的边界属性可以用1#,2#,3#,4#,6#,8#,9#,12#来描述.分别统计图像1～4区具有1#,2#,3#,4#,6#,8#,9#,12#的数目,得:D1=[D11,D12,D13,D14,D15,D16,D17,D18]D2=[D21,D22,D23,D24,D25,D26,D27,D28]D3=[D31,D32,D33,D34,D35,D36,D37,D38]D4=[D41,D42,D43,D44,D45,D46,D47,D48]其中,Dij表示第i区中具有第j种特征的2×2像素块的数目.如图1所示,“B”的二区(即右上部分,第二象限)具有1个1#,1个2#,1个3#,1个4#,4个6#,3个8#,4个9#,3个12#,即二区的特征向量D2=.把4个区域的特征向量合并,就可以得到整幅图像的32维特征向量D=[D1,D2,D3,D4].可以看出,FPGA算法实现时只需要加减、逻辑运算,就可以统计每一幅图像的D,且逐行扫描过程中的任意时刻都只需要存储η+2个像素,其中η是图像中一行包含的像素个数,如图2所示.1.5图像的didi特征首先得到数字(0～9)和大写英文字母(A～Z)共36幅图像的特征向量D(k)(k=1,2,…,36),并把这36个特征向量作为基准.然后,对欲识别的图像进行统计边界特征,得到特征向量D(37).接着,对特征向量D(37)做子集判别:D37∈{G18∑i=1(|D1i-D3i|+|D2i-D4i|)<YG28∑i=1(|D1i-D2i|+|D3i-D4i|)<Y∩8∑i=1(|D1i-D4i|+|D2i-D3i|)<YG38∑i=1(|D1i-D2i|+|D3i-D4i|)<Y∩8∑i=1(|D1i-D4i|+|D2i-D3i|)≥YG48∑i=1(|D1i-D4i|+|D2i-D3i|)<Y∩8∑i=1(|D1i-D2i|+|D3i-D4i|)≥YG5其他其中:Y=α8∑i=1(|D1i+D2i|+|D3i+D4i|).一般地,α取0.125～0.25.最后,对D(37)所属子集内所有图像元素求如下距离:d(k)=4∑i=18∑j=1|Dij(k)-Dij(37)|k=1,2,⋯,n其中:Dij(k)为该子类集合中第k个图像元素的第i区中具有的第j种特征数量;Dij(37)为欲识别图像的第i区中具有的第j种特征数量;n为D(37)所属的子集中图像元素个数.得到类内最小距离d(k),则该子集中第k幅图像就是最佳判决图像.2实验证明及基本结论用FPGA实现了本文提出的识别算法,并采用50×75像素的摄像头,摄入36个字号大小为72的TimesnewRoman的印刷字体0～9和A～Z,算出36幅图像的特征向量,并得到5个子类集合图像元素相互间的距离差,如图3所示.由图3可知,5个子集中各图像元素特征向量彼此间的距离差很大(实际上,36幅图像特征向量的相互间的距离都很大),这说明了该特征向量具有很好的区分性,能够有效地识别图像.对正常摆放位置的数字和字母,正确识别率达到99%以上.下面的实验证明了本算法的健壮性,并且具有对平移和小角度旋转的不变性.如图4所示,经过左右旋转0°～10°的数字和字母图像和该图像原型的距离最小,所以本算法同样可以识别出经过左右旋转0°～10°的数字和字母图像,这充分证明了本算法具有对小角度旋转不变性.因为“竖”、“横”、“斜”、“弯”4种特征具有显著的差异性,而小角度的旋转对图像4个区域的特征向量的值改变不大,只要选择好合适的α值,就可以保证子类判别的正确.实验证明,对小角度旋转图像的正确识别率也达到97%以上.移动摄像头,让数字和字母位于摄入图像中的不同位置,仍然能够正确识别图像.这也证明了算法对平移具有不变性.因为无论数字和字母处在摄入图像的什么位置,经过算法中的定位处理后,总是能够正确地划分4块区域,并正确统计出图像边界特征向量.此外,算法的复杂度低,节省硬件资源.在上述算法中,预处理、定位、特征识别等所有步骤的FPGA实现都可以只用加法器和逻辑运算来实现,不必用到乘法器,并且只需要η+2像素的存储空间,其中η是图像一行包含的像素个数.QuartusII综合后,可以得到针对50×75像素大小的图像.本算法所有步骤的FPGA实现只需8000个Gate