控制字符

控制字符（共7篇）

控制字符 篇1

一、基于“控制字符”的网页信息隐藏技术原理

控制字符是在网页当中插入的, 但是在浏览网页时看不到的字符。在实际网页源代码中控制字符是存在的, 包括一些空白位和特殊字符。在ASCII码字符中一共存在33个控制字符, 它们的ACSII编码分别是0-31和127, 其中1-8和14-31是特殊字符, 0是null空值, 32是空白符。如:DEL (删除) 、BS (退格) 、BEL (振铃) 、LF (换行) 、CR (回车) 、FF (换页) 等;通信控制专用字符:SOH (文头) 、EOT (文尾) 、ACK (确认) 等;ASCII值为8、9、10和13分别转换为退格、制表、换行和回车字符。它们当中没有特定的图形显示, 但会依不同的应用程序, 而对文本显示有不同的影响。将所有控制字符定义为一组:Si={i=[0-31]}。

如果普通的字符可以转换为控制字符中的一个, 那么就可以将秘密信息嵌入所操作的网页中。控制字符在ASCII字符集中最大的编码是32, 但是其他可见字符则大于这个值, 字母和数字在ASCII中就都在后面, 数字“1”是49, 字母“a”是97。因此, 秘密信息需要转换成控制字符才能进行隐藏。

下面定义一个转换阀值, R=M-T

其中M是控制字符S的ASCII编码, T是转换阀值, 通过这一转换阀值将秘密信息的二进制位进行转换, R就是秘密信息经过转换后的ASCII编码。

假设R被随机的分为两段代码, 即R1和R2, R=R1+R2。

那么, 通过转换阈值T和控制字符的两段代码R1和R2, 可以对秘密信息进行隐藏了。网页信息隐藏技术分为两个阶段, 即网页的发送和接收, 在网页发送前将秘密信息嵌入其中, 当浏览器从网络接收到网页后, 将秘密信息提取出来, 详细过程如图1-1所示:

二、算法的设计

1、字符转换算法的设计

需要隐藏的秘密信息需要使用相应的方法转换成隐藏字符, 普通字符选择的范围是大写的字母A-Z, 小写的字母a-z, 数字0-9, 以及空格, 所以秘密信息可以是一串带有空格的字符。

具体应用举例如下:字母z的ASCII十进制编码是122, 所以M=122, T=60, R=62。这时候R需要分成两个31, 其对应的控制字符则是单元分隔符。而空白键则可以直接嵌入。

在秘密信息转换完成之后, 就进入了信息的嵌入和提取过程。秘密信息S的ASCII代码描述为如下公式:

转换阀值T, 可以描述为如下公式:

那么转换结果, 可以按如下公式获取:

另外, 在通过提取算法的执行得到ASCII代码的过程中:

在秘密信息提取的阶段, T可做如下定义:

2、嵌入算法的设计

嵌入算法的作用是这样的, 将需要隐藏的秘密信息嵌入到一个网页当中, 生成另外一个新的网页。

输入内容:秘密信息S=s1s2s3…sn, 原始网页为WEB1, 该网页可以嵌入信息的数量为n。

输出内容:生成一个带有秘密信息的网页WEB2。

秘密信息的嵌入算法如下:

(1) 将秘密信息S按照公式 (n1) 转换为ASCII代码M (M=m1m2m3…mn) ;

(2) 通过公式 (n2) 和 (n3) 得到R的值R (R={ri (i=0, 1, 2, …, n) }) ;

(3) i赋值为0;按照顺序从H中读取一个代码ri;

(4) 从网页WEB1中读取一行L;检查L这一行中存在的标记语言, 如果存在就继续往下执行, 不存在返回步骤;

(5) 重新读取一行;计算ri1和ri2的值, 通过ri1和ri2的值确定ri=ri1+ri2;

(6) 从</Ti>到</Tiri1ri2>更新行L中的标记, 这里的<Ti>是HTML标记语言中的一种标记;同时i赋值为i=i+1, 返回步骤 (4) 循环执行, 直到全部完成, 继续往下;获得新的网页WEB2。

通过此算法后, WEB1和WEB2两个网页在浏览器中显示是完全一样的, 没有任何区别, 用户在查看网页时, 不能察觉到隐藏信息的存在。

3、提取算法的设计

当接收端在通过网络从服务器中接收到网页WEB2后, 需要将秘密信息从网页中提取出来。在提取秘密信息时需要进行字符重组和信息融合。

提取算法的作用就是将秘密信息从网页中提取出来。

输入内容:携带有秘密信息的网页WEB2,

输出内容:秘密信息S。

秘密信息的提取算法如下:

(1) i赋值为0;从网页WEB2中读取一行L‘;

(2) 检查L‘这一行中存在的标记语言, 如果存在就继续往下执行, 不存在返回重新读取一行;

(3) 从标记语言</Tiri1ri2>中分离出ri1和ri2, 并去除标记中ri1和ri2的值;

(4) 通过计算ri=ri1+ri2, 得到ri的值;依照前面的公式 (n4) 和 (n5) , 得到ASCII代码mi;从ai的ASCII代码得出字符si;

(5) i赋值为i=i+1, 如果到了网页WEB2的末尾, 往下执行步骤 (6) , 不是末尾则返回步骤 (2) 继续读取;

(6) 提取算法全部完成后, 得到完整的秘密信息字符串S=s1s2s3…sn;

三、算法程序的实现与分析

1、算法程序的实现

算法的实现是通过C#编程来实现的, 图1-2显示了基于控制字符的网页信息隐藏技术主界面。

首先定义两个函数, 分别是asc () 和rasc () , 函数asc () 的作用是将秘密信息的字符转换为ASCII代码十进制, rasc () 作用相反, 将十进制数字转换为相应的ASCII字符。

2、隐藏算法性能的分析

这里主要从隐藏的容量和隐藏误码率来分析该网页信息隐藏算法的性能。

(1) 字符隐藏效果的计算

字符隐藏效果指的是, 字符在嵌入到提取的过程中, 反映字符精确性的指标, 主要指的是有没有产生误码。假设秘密信息S的ASCII代码代码是A=a1a2a3…an, 在经过传输后, 通过提取算法将秘密信息提取后的信息为A′=a′1a′2a′3…a′n, 隐藏字符误码率Q如下公式所示:

(2) 隐藏容量的计算

在基于控制字符的网页信息隐藏方法中, 每一个可用的超文本标记都可以隐藏一个字符, 如果在网页WEB1中可用的超文本标记的数量为n, 那么信息隐藏的容量V就是:

当然这个隐藏的容量只是一个理论值, 在具体的使用过程中, 是不可能利用网页中所有的超文本标记来进行信息隐藏的。另外, 每一个字符都可以被转为一个8位的二进制位, 就现存的基于标记的嵌入方法而言, 一个标记可以隐藏两个字符, 那么通过信息隐藏容量的计算, 基于控制字符的网页信息隐藏方法的隐藏容量是其他同类隐藏方法的4倍。

四、结语

本文通过三方面来探讨基于“控制字符”网页信息的隐藏技术, 对于“控制字符”网页信息的隐藏技术原理进行详细描述, 同时对隐藏技术的算法设计全面剖析, 最后通过算法程序来进行验证隐藏技术算法。

参考文献

[1]孙圣和, 陆哲明等, 数字水印技术及应用[M]北京.科学教育出版社, 2004.

[2]姚晓枝基于两种不同载体的信息隐藏方法研究[D]上海.复旦大学, 2008.

[3]戴祖旭文本载体信息隐藏研究[D]武汉.华中科技大学, 2007.

控制字符 篇2

1程序设计

1.1算法思想

常用的数据加密方法主要有移位和置换法,目前,实现移位和置换的算法很多。从特点看,异或运算最适合用于简易加解密运算,因为当一个数A和另一个数B进行异或运算会生成另一个数C,如果再将C和B进行异或运算则C又会还原为A。使用这种算法能够比较容易地对明文和密文进行转换。

使用XOR对数据加密是很容易破解的。因为利用XOR对明文字符进行置换,相同的明文字符会置换为相同的密文字符。如果有足够多的密文,就可以根据字符使用的频率,在密文中猜测出使用最多的几个字符,进而猜测出英文单词或中文字词,这就比较容易的破译密文。例如字符e,假设密钥为11,其XOR结果为chr(asc(“e”)XOR 11)=n。字符串eeeeee的密文为nnnnnn。根据统计结果在英文中字符e用的最多,在足够多的明文中统计出现最多的字符,得出的结果为n,即可推断n的明文应为字符e,据此可推算出密钥11,破译也就十分容易了。

要增加其难度,就要在对文件加密时加入一随机因子,使相同的明文以不同的字符呈现在密文中。仍以字符串eeeeee为例,将字符的位值k与密钥11相加,与其XOR的结果为:

字符串eeeeee的密文为ihkjut。相同的明文字符变成了不同的密文字符。

1.2在VB中实现的可行性

VB中的所有和字符串相关的函数使用的字符集都是Unicode。Unicode是用两个字节表示一个字符的字符编码方案。此方案与其它传统单一字节的字符集不同的是,其使用两个字节来表示一个字符,这使得可用字符的数量大大增加。Unicode的字符都是双字节的,VB在进行内部处理时,英文字符和中文字符被同等对待。并且支持世界上的所有的常用文字。

VB提供了XOR函数,可以对数字、布尔变量,字符进行异或运算,两次异或的结果即为原值。因此,是基本加/解密函数。例如:对于中文字符“息”,asc(“息”)XOR28=24943,24943 XOR 28=24687,chrw(24687)=“息”。

由此可以认为:以位值作为随机因子,用XOR运算对数据进行加/解密在VB中是可以编程实现的。

1.3程序界面

程序使用单一窗口,窗口中的主要控件如下。

1.4参考代码

2结束语

加/解密程序虽然使用代码较少,但由于密钥与字符位值的结合,使得相同字符在密文中的呈现各不相同,增大了破译难度。

参考文献

[1][美]Scott Warner著.Visual Basic6.0程序设计.第一版.汉明工作室,译.北京:人民邮电出版社,1999-08.

控制字符 篇3

1 车牌字符特征与字符分割

一般而言,车牌进行字符分割之前都要进过一定的预处理,包括二值化,校正车牌的水平和垂直倾斜,去除车牌的上下边缘及无关的背景和归一化等。根据不同的算法,所采用的预处理方法不同。最后,车牌图片只剩下由字符和背景构成的二值化图或彩色图。

根据文献[1]规定,完整的97式车牌图像由7个字符组合而成,包含汉字、字母和数字,每个字符间都存在一个固定的间距。此外,我国根据车辆、车型、用途的不同制定了多种格式尺寸,不同颜色搭配的牌照以示区别。除了字符之间存在间隙的简单特征之外,车牌中的字符还存在以下特征:

1)标准车牌字符的高度H和宽度W分别为90mm和45mm,即标准字符的高宽比为2:1;

2)除第二和第三个字符之间的宽度为34mm外,其余各个字符之间的间隙宽度均为12mm;

可得到如下结论:第二和第三个字符的中轴线相距约79/90H或79/45w,其他应个字符的中轴线间距约为57/90H或57/45w。

如图1,根据这些特点,车牌的字符分割方法较多。根据车牌颜色的分割,比如基于伴生与互补颜色特征的车牌字符分割新方法[2];根据车牌图像纹理特征的分割,如基于边缘检测与Hough变换的车牌字符分割[3],基于字符像素投影统计的分割算法[4],这些算法中,基于伴生与互补颜色特征的车牌字符分割的方法只能主要处理彩色图像,对图像颜色比较敏感,特别是褪色的车牌分割效果很差。基于直线检测的车牌字符分割计算量大,执行效率差。基于字符像素点X轴投影统计的分割算法是一种最经典的算法,对正常车牌的分割效果最好。

现实中,由于各种因素影响,比如光线、天气以及车牌污损,车牌边框干扰等,车牌中存在的字符相互粘连或字符投影间距不明显的情况。由于字符点投影间隙不明确,使得上述几种算法不能对车牌图像进行有效分割。如图的车牌,由于字符粘连和车牌边框的干扰,使用投影算法进行分割的结果如图。由图2可知,单纯使用投影算法不能有效地识别,需要进行改进。

2 基于车牌字符综合特征的字符分割算法

通过对字符特征的分析,文章提出一种新的基于字符分布特征的车牌字符分割算法。先使用预处理切除车牌上下边缘,去除边框的干扰。而后,根据字符投影的方法,以字符间距为依据将车牌分割。接着将获得的所有间距进行排序,取中间值作为车牌的标准宽度,并以取得的标准字符宽度建立如图的模板。最后将模板在车牌图像区域内平移,统计模板区域内字符点的个数N,取N最大时模板所分割的各区域作为字符分割的结果。

2.1 预处理

据理想状态下的车牌特征,车牌上边框和字符上部存在一条431mm×20.5mm的近似矩形背景区域,该区域被车牌固定螺丝大致分为三个隔离区域,从左至右这三个区域的宽度分别约为车牌整体宽度的1/4,1/2和1/4,这是划分车牌字符和车牌上边框的依据,可以依此将多余部分切除。本算法分别以车牌高度的三分之一处和三分之二处为起点,分别向上和向下搜索。鉴于上下边缘的检测步骤完全一致,只是方向不同,本文以上边缘切割为例进行说明,具体算法如下:

1)取得当前行的索引下标i,判断i是否大于零,若i>0则表明检测未结束,转(2);否则表明检测结束,车牌上边缘不需要切割,跳出循环。

2)统计当前行i的最长的连续背景像素点的宽度bg_num和最长的连续字符像素点char_num的宽度,求得连续背景像素点的宽度在该行所占的比例η=bg_num/ω和连续字符像素点在该行所占的比例φ=char_num/ω,其中ω为校正后车牌的宽度,转(3)。

3)若η>1/4或φ>1/2,则该行即为非车牌行,取车牌的上边界为第i+1行,将行下标小于i+1的所有行去除,而后跳出循环;否则该行仍属车牌部分,i=i-1,跳到当前行的上一行,转(1)继续对上一行判断。

经过预处理,车牌的上下边框已经基本切除,实验效果如图3。下一步的目标是将粘连的字符分开。

2.2 字符分割

第一步:字符点纵向投影统计。

从车牌图片左边缘开始,逐列向X轴方向投影,统计各列中像素点颜色为白色的字符像素点个数,将各列扫描结果依次存储到数组中count(n)中。设定各初始参数,初始列的下标i=1,单个字符区域的开始列下标S=0,结束列下标E=0,C(n),n∈N用于存储N个符合要求的字符候选区域,N根据各车牌实际情况而定。

1)判断下标i是否大于车牌宽度W,是则结束投影分割,否则转2)。

2)以单列出现2个字符点作为判断是否是字符部分的阈值。若第i列的字符点个数count(i)≤2,表明此处为背景,转(3);反之则认为此列属字符区域,转(4)。不直接设为阈值为0的目的是为了防止噪点的干扰。

3)若S=0,则表明此列不包含字符图像,则i=i+1进入下一列,而后转1);若S≠0,则表明此处为字符与背景边界,取E=i-1,则字符候选区域宽度Ci=E-S,转(5);

4)若S=0,则表明此列为字符图像开始部分,则S=i,而后转1);若S=0,则表明此处仍在字符区域内,取进入下一列i=i+1,重复(1);

5)根据样本字符的高宽比为2的规则,判断截取的车牌区域的高度H与3)获得的间距Wi的比值是否达到指定要求。若H/Wi>1.7时,则认定该区域为字符候选区域,将宽度Ci存入字符候选数组C(i),N=N+1;若H/Wi<1.7,则认为该处为噪点,抛弃,i=S+1,转(1)开始新一列的检测。

字符点纵向投影统计的效果如图4所示。

第二部分:计算标准字符宽度,并定制模板。

将C(n),n∈N进行排序,取得排序后的中间值作为标准字符宽度ω。根据车牌的高宽比为2,将字符间距转为使用w的表示形式。根据图的比例,除第二个字符与第三个字符的间距为79/45w,其他各字符间距均为57/45w,模板如图5所示。

第三部分:分割字符区域。

将定制好的模板在车牌图片区域内平移,确保模板左右边界不超出图像区域。在平移过程中,统计平移过程中各字符区域内字符点的个数Ni,并记录相应模板左边界i。平移后,将统计结果Ni进行排序,取最大的Ni时的i为模板左边界,使用模板进行分割。

整体分割实验结果如图6、图7,车牌字符左边界Li=8,字符间距为2个像素,所需时间为0.3246秒。

3 总结

实验表明,本算法能够很好的分割正常的字符,同时对有粘连的字符分割也比较准确,执行速度也比较快。本算法的关键之处在于两个问题:能否准确的获得车牌字符的宽度,以及在车牌宽度准确的前提下准确定制出车牌字符分割模板。通过对分割失败的原因分析,发现大多数分割失败的原因主要在于没有非常准确的获得车牌宽度。此外,车牌在矫正的过程中存在变形,也会影响车牌字符的分割。这些问题也将是对该算法进一步改进的主要突破口。

摘要：字符分割技术是车牌识别系统的关键技术之一。字符分割最主要的问题是字符粘连及车牌边框的影响。鉴于车牌字符具有布局规整,字符个数确定,字符大小一致、宽高存在规律等特征,文章提出一种将投影和字符间距相结合的基于字符综合特征的字符分割算法。实验证明该算法那对分割粘连字符具有较好效果。

关键词：车牌识别系统,字符分割,字符特征,字符粘连

参考文献

[1]GA36-2007.中华人民共和国机动车号牌[S].

[2]王枚,王国宏.基于伴生与互补颜色特征车牌特征的车牌字符分割新方法[J].山东大学学报:工学版,2007,37(1):1-4.

[3]马腾飞,郑永果,赵卫东.基于边缘检测与Hough变换的车牌字符分割算法[J].系统仿真学报,2006,18(1):391-403.

控制字符 篇4

1 字符串的存储

字符串可以看作一组字符型数据的集合, 例如字符串“Hello”存储如图1所示。

注意每个字符串末尾都有一个字符“�”做结束符, 这里的“�”是ASCII码的八进制表示, 也就是ASCII码为0的Null字符, 称为以零结尾的字符串 (Null-terminated String) 。

1.1 字符数组

可以使用字符数组存储字符串, 主要的有以下二种用法。

一种方法是char str[10]=“hello”;初始化字符串数组时, 编译器自动将字符串最后一个字符后面加上“�”, 以表示字符串的结束。相当于char str[10]={“h”, “e”, “l”, “l”, “o”, “�”};

如果数组的大小大于字符串的长度+1, 那么把字符串结束后面的元素也都初始化为“�”。

如果数组的大小小于字符串的长度+1, 则数组str只包含字符串的前10个字符, 不包含“�”字符, 这种情况编译器会给出警告。

如果要用一个字符串的字符准确地初始化一个字符数组, 最好的办法是不指定数组的长度, 让编译器自己计算:char str[]=“Hello”, 字符串的长度包括“�”字符在内一共6个字符, 编译器会确定数组str的长度为6。这是第二种常用的方法。

1.2 字符指针

char*ptr=“abc”, 前面提到字符串是作为字符数组进行存储, 编译器把“abc”当成常量并它放到程序的常量区, 按照C/C++标准的描述, “abc”是string literal (字符字面量、字符文字量) , 具有静态存储性质, 类型是数组类型, 并且不能被改变。因此定义的是一个指向字符类型的指针ptr, 这个指针指向了字符串的首地址。建议的写法应该是const char*ptr=“abc”。

2 字符串的使用

2.1 用字符数组处理字符串

字符数组中存放的字符串可以像普通数组一样逐个引用数组元素进行赋值和其他运算, 也可以和普通数组不同, 通过字符数组名将整个字符串一次输入、输出[2]。参考例1, 本文的程序在VC++6.0系统下调试通过。

例1中用str数组存放字符串“hello”, 其中str[0]='h', str[1]='e', str[2]='l', str[3]='l', str[4]='o', str[5]=“�” (由系统自动加入’�’) , 使用while循环, 当数组元素不是字符串的结束符“�”时, 输出数组元素。

C/C++中, 数组名作为数组元素的首地址, 输出时, 是将从数组首地址开始输出字符直到字符串结束。

2.2 使用字符指针处理字符串

例3中, 字符指针ps指向字符串常量“hello”的首地址, 即*ps=“h”。可以用指针输出这个字符串 (从字符串的第一个字符开始输出到字符串的结束符“�”为止) 。将字符指针加一ps++后, ps指针指向字符串的第二个字符, 即*ps=“e”, 依次使用指针将字符串的每一个字符赋值给字符数组str, 最后将“�”放入数组。

3 一些需要注意的问题

char*ps=“hello”;字符指针指向的是一个常量, 因此, *ps=“a”, 这样的语句由于试图对常量进行改变, 尽管编译通过, 在运行时仍会出现错误。另外, 也有这样的输入字符串的方式char*p;cin>>p;这种方式在编译时会给出警告, 因为指针p并没有被赋值, 也就是说指针p的指向是不确定的, 可能指向空闲的存储单元, 也可能指向程序或数据区域, 因此, 在使用时必须先给指针赋值, 如char s[10], *p=s。

摘要：C/C++中使用字符数组和字符指针处理字符串, 本文对字符数组, 字符指针及字符串的初始化、赋值和使用进行了细致深入的探讨。

关键词：C/C++,字符指针,字符串

参考文献

[1]谭浩强.C程序设计[M].清华大学出版社, 1997:157.

LSort字符排序算法研究 篇5

关键词：排序,算法,有序序列

1 排序算法的基本概念

随着计算机技术的发展及互联网的普及,各类数据量迅猛增长,导致日常数据查询效率较低,构造一个合适的排序算法可以极大提高工作效率。

传统的排序功能要求给定一个无序数据序列,经过排序操作后,将序列按从大到小或从小到大的顺序排列成有序序列,即:

输入序列:N1,N2,N3,...,Nn

排序算法一般分为稳定类算法与不稳定类算法,稳定类算法指当有两个相等记录的关键字Keyword1与Keyword2时,在原数据序列中Keyword1出现在Keyword2之前,经过排序操作后,关键字Keyword1仍然在关键字Keyword2之前;而不稳定排序类算法会在相等的键值中改变记录的相对顺序,所以在构造排序算法过程中,应该尽量避免不稳定类排序算法。目前,稳定类排序算法有冒泡排序算法、合并排序算法等[2]。

2 经典冒泡排序算法

冒泡排序算法属于典型的交换类排序算法,交换类算法的主要思想是将待排序数据的关键字进行两两比较,当两个元素的值大小相反时交换其位置,同理依次对所有数据进行两两比较[3]。

经典冒泡排序算法的核心思想是将被排序的无序数据序列N[1..n]进行垂直排列,每个数据N[i]被看作是重量为N[i].m的气泡。根据轻气泡在上重气泡在下的原则,从下往上扫描整个数据序列N,遇到顺序不符的轻气泡时调换其位置。对所有“气泡”进行扫描,使所有“气泡”都符合轻上重下的原则[4]。

每次排序过程都使有序气泡增加1个,在经过n-1次排序后,数据序列中就有n-1个气泡,而无序数据序列中气泡的重量大于或等于有序数据序列中气泡的重量,所以整个排序过程至多需要进行n-1次排序。若在某一次排序中未发现气泡位置交换,则说明待排序的无序序列中所有气泡都满足轻者在上重者在下的原则。

衡量算法优劣一般采用时间复杂度及空间复杂度方法,冒泡排序算法的时间复杂度为O(n2),空间复杂度为O(1)。

3 LSort字符排序算法

一个问题往往可采用多种算法进行解决,而算法的优劣将直接影响最终程序的效率。算法分析的目的在于选择合适算法和改进算法,冒泡排序算法在多种情况下,每个元素都需要与其它n-1个元素进行比较,在对大量数据进行排序操作时效率较低。为了提高排序操作的效率,本文设计一种新的排序方法—LSort字符排序算法。

其核心思想是对于一个无序字符序列,另外开辟一个与原来序列相同大小的空序列,新序列中要求所有存储元素都是有序的,即添加的元素与新序列中的每个元素进行比较,比如元素3添加到新序列:1,2,4,5中时,将元素3与第1个元素比较,当比较到元素4时,将元素4和5往后退一个空间,然后将3放到元素4之前的位置,具体实现代码如下:

4 LSort字符排序算法的时间复杂度

算法的时间复杂度在计算机科学中是一个函数,大概描述了算法的运行时间。时间复杂度一般使用“O”符号表达,结果一般以最高阶次为准,不考虑函数的低阶项和各项系数。时间复杂度一般考察输入值趋近无穷时的情况[5]。

排序算法中的基本操作重复执行的问题是规模n的函数,假设问题的规模是n,基本操作重复执行的次数是函数f(n),那么时间复杂度记作:T(n)=O(f(n))。

排序算法花费的时间与算法中语句的执行次数成正比,语句执行次数越多,对应的时间复杂度就越大。算法的时间频度从理论上不能直接计算出来,需要上机试运行才能得到具体频度值。时间复杂度一般考虑问题规模n的增长率,一般考虑重复执行次数关于n的阶数。

LSort算法中for循环操作重复n-1次,其它赋值判断等操作重复n-1次,所以LSort算法的时间复杂度T(n)=O(n)。

5 LSort字符排序算法的空间复杂度

空间复杂度是对算法运行过程中占用存储空间的一种量度。通过算法空间复杂度计算,可对程序运行所需内存的多少进行预估。算法执行除了包含程序本身所使用的指令、常数、变量和输入数据外,还需包含对数据进行操作的工作单元,以及部分辅助存储空间[5]。程序运行过程执行的存储空间主要分为以下两部分:

(1)固定空间:固定空间部分的大小与输入/出数据个数无关。主要包含代码空间、数据空间,属于静态存储空间。

(2)可调空间:主要包括动态分配的空间,以及递归堆栈所用的空间等,与算法有关。

算法空间复杂度一般考虑程序在运行过程中为局部变量分配的存储空间,具体包括形参列表分配的存储空间大小,以及在函数体中定义的局部变量的存储空间。对于递归类算法,空间复杂度等于所用堆栈空间的大小,等于调用所用的临时存储空间乘以被调用次数的积。

算法空间复杂度一般以数量级的形式表示,例如一个算法的空间复杂度为常量,即不随规模n的大小而改变时,算法空间复杂度等于O(1);当算法的空间复杂度与规模n呈线性比例关系时,可表示为O(n);当算法的空间复杂度与log2n成正比时,可表示为O(log2n)。假设形参为数组类型,只需为它分配实参传送来的地址指针所占用的空间;假如形参为引用类型,只需要分配存储地址所占用的存储空间。

LSort算法排序过程中,新序列所使用的空间为常量,且规模n的增长对空间并没有产生影响,所以其空间复杂度S(n)=O(1)。

6 结语

本文分析了排序算法的特点,讨论了经典冒泡排序算法的核心思想,并针对冒泡排序算法的效率提出了LSort字符排序算法。通过建立新的有序列表,能有效减少排序过程中的比较次数,经测试该算法适合对大量无序字符数据进行排序。

参考文献

[1]王红梅.数据结构(C++版)[M].北京:清华大学出版社,2011:167-188.

[2]贾丹.排序算法的性能分析[J].电脑知识与技术,2015(26):75.

[3]钟全.简单选择排序算法稳定性探究及其改进[J].软件导刊,2016(2):60-63.

[4]张朝鑫.C语言中的冒泡排序算法优化究[J].硅谷,2013(19):166.

基于统计的车牌字符识别 篇6

按照我国机动车号牌标准, 车牌的第一个字符为汉字, 并且该字符为省、自治区、直辖市简称和一些特殊字符, 总共37个汉字, 且汉字字体有标准统一, 因为所有的机动车号牌中第一个汉字字符固定, 是37个汉字中的一个, 因此我们可以对每个字符进行特征统计, 通过聚类的思想对字符进行分类。

2 基于聚类的汉字字符判别

汉字字符的分类识别识别与其他分类一样, 同样分为三个步骤:分类对象特征提取;构建分类器;分类计算。

2.1 提取特征向量

本文将通过数字图像的统计特征进行字符特征的提取。

对每个字符iy建立特征向量yi (28) (7) xil, xi2, (43) , xin (8) 。首先, 对车牌中的37汉字字符标准的图像样本进行特征统计, 读取图像后, 转换为二值图像。提取特征包括字体占有率、左右分布比例、上下分布比例。

从37个字符中可以看出, 随着每个汉字字符的笔画数目复杂程度不同, 字符的占有率、左右分布、上下分布各不相同。因此, 这些特征对于字符的判别分类具有重要的意义, 首先, 通过图像的数值矩阵结构特征计算图像边界:Bou, 1Bou2, Bou3, Bou4分别为边界上下左右的行列号。下面对这些特征信息进行提取:

占有率:

左右分布:

上下分布:

至此, 完成对汉字特征的提取, 下面对汉字进行识别。

2.2 聚类分类识别

这里我们仍然采用聚类分析的思想, 通过衡量距离计算相似度, 达到对汉字字符分辨识别的目的。根据上面建立的样本集合Y, Y (28) yii (28) , 1, 2, 3 (43) , 37, 首先, 采集样本信息, 计算出每一个向量iy, 然后对每个判别对象y0进行相同信息的提取, 然后进行测度衡量。

2.3 分类计算

下面将样本代入进行计算, 通过预处理、放缩、角度校正等得到字符图像的二值图, 对样本y0进行直接聚类法判别, 结果如表1。

从表1中我们可以看出, 最小距离为1.1521, 判别结果为‘京’, 结果正确。

摘要：车牌字符分割后的字符识别是车牌识别系统的技术关键, 目前字符识别的主流技术方法为基于字符特征提取的神经网络识别。目前国际上对字符识别技术有了较为成熟的研究成果, 但是, 这些技术尚不能对中国机动车牌中的汉字部分进行识别。本文将对车牌的汉字识别技术提出基于统计的识别方法, 并对汉字的特征提取提出相应的技术方案。

关键词：统计,车牌识别,特征提取,分类器

参考文献

[1]邹永星.车牌字符分割方法的研究[D].硕士学位论文, 湖南:湖南师范大学, 2008.

[2]王广宇.车辆牌照识别系统综述[J].郑州轻工业学院学报 (自然科学版) , 2001, 16 (2) :47-50.

利用反馈的车牌字符分割算法 篇7

随着信息技术和人工智能技术的发展, 交通管理系统的信息化、智能化是大势所趋, 智能交通系统已成为一个热点研究领域。车牌识别系统是智能交通系统的重要组成部分, 在现代交通管理中占有举足轻重的地位。车牌识别系统包括三个主要环节, 即车牌定位、字符分割和字符识别。目前的字符识别算法基本上是针对单一字符, 因此字符分割是一项十分关键的技术。

目前的车牌字符分割方法主要有: (1) 基于二值化图像垂直投影的方法[1,2]。这是最普遍采用的方法, 优点是速度快, 但对图像质量要求较高, 当牌照中出现字符粘连和断裂等情况时会发生分割错误; (2) 基于垂直投影和先验知识的方法[3,4,5], 该方法除了应用垂直投影外, 还考虑字符的宽度等先验知识, 改善了字符分割效果, 但当字符褪色严重或有干扰信息时会分割失败; (3) 基于模板匹配的字符分割方法[6,7], 该方法设计车牌字符串模板, 通过模板匹配确定字符位置, 该方法具有较好的字符分割效果, 但如何设计匹配模板是一个难点。

本文提出了一种新的车牌字符分割算法。该算法避免仅采用垂直投影分割字符, 而是将垂直投影和反馈相结合, 既考虑车牌的先验知识, 又考虑字符的纹理特点, 通过字符个数与字符宽度反馈以及字符识别反馈, 经由粗到精的过程分割车牌字符图像。

1 图像预处理

1.1 光照不均校正与对比度增强

光照度一般变化缓慢, 可采用低通滤波获得图像背景的照度估计, 再从原始图像中减去此照度来校正光照不均, 最后通过对比拉伸变换增强对比度。图1为原始车牌图像, 图2为经过对光照不均的校正与对比度增强后的图像。

1.2 倾斜校正

倾斜的车牌图像有三种倾斜模式:水平倾斜、垂直倾斜和水平垂直倾斜。本文采用文献[8]的方法, 即通过水平和垂直边缘检测结合旋转投影来求取车牌的水平和垂直倾斜角度, 对水平倾斜的车牌进行双线性插值旋转校正, 对垂直倾斜的车牌进行双线性插值错位偏移校正, 在倾斜校正的同时确定车牌的上下位置。图3为倾斜校正后的图像。

1.3 边缘增强与二值化

将车牌图像归一化为48像素高, 然后以宽度为w, 幅值为w/2 (w根据笔画宽度选取) 的阶梯信号与车牌图像卷积进行边缘增强, 然后二值化。边缘增强图像和二值化图像分别如图4和图5所示。

2 基于垂直投影的字符粗分割

垂直投影法是字符分割的常用方法, 其基本原理是, 设车牌图像二值化后的背景点为黑像素0, 字符点为白像素1, 则在垂直方向统计白像素的个数, 获得白像素的垂直投影分布。由于字符区域白像素较多, 而字符间空隙区域白像素较少, 因此可将白像素个数的波谷作为字符间的分界处。

我们将上述垂直投影法进行了改进。首先对二值化车牌图像进行垂直投影, 然后选取阈值T, 若投影值小于T, 则将该投影值设为0, 垂直投影结果如图6所示。根据垂直投影获得的粗分割图像如图7所示。由图可见, 字母“C”被分割为两个字符, 而数字“7”被分割为三个字符。

3 基于两级反馈的字符精分割

3.1 基于字符个数与字符宽度反馈的字符分割

车牌图像的特点之一是具有7个字符, 字符的字段宽度固定。因此, 可以计算粗分割后字段的个数和每个字段的宽度, 并给它们设定合适的阈值, 然后通过反馈进行字符分割。字段个数阈值为7, 字段宽度阈值范围为[D1, D2]。如果字段的个数大于7, 将字段宽度最小的字段与其相邻两个字段中宽度小的字段合并, 否则将字段宽度最大的字段进行分裂, 直到字段的个数等于7;如果字段的宽度大于D2, 则对该字段进行分裂操作, 如果字段的宽度小于D1, 则进行合并操作。图8为分割结果。

3.2 基于识别反馈的字符分割

3.2.1 基于离散余弦变换的字符纹理特征

车牌字符具有明显的纹理特征, 该纹理特征可通过字符的垂直投影来描述。

当求车牌字符的垂直投影时, 可得到坐标对 (0, y0) , (1, y1) , …, (N-1, yN-1) , 其中N为字符区域宽度。这样, 垂直投影就可以表示为一个序列f (n) ={yn}, n=0, 1, …, N-1。求取f (n) 的离散余弦变换为:

其中, F (u) 为f (n) 的频域描绘子。由于高频系数决定细节部分, 低频系数决定总体形状, 所以可使用前m个系数 (即低频系数) 重构垂直投影图得到f^ (n) , 这里, 取m=8。

根据重构的垂直投影图可获得如下统计量:

(1) 均值μ

(2) 标准偏差σ

(3) 三阶矩3

结合重构后垂直投影的统计量, 将字符的纹理特征向量定义为:

3.2.2 基于识别反馈的字符分割

将标准车牌字符模板图像二值化和归一化, 尺寸为48×24, 按式 (7) 计算模板字符的纹理特征向量MTV和待识别字符的纹理特征向量BTV, 则与模板匹配的置信度R定义如下:

其中, m=27是纹理特征向量的维数。

按如下步骤进行字符分割:

(1) 设3.1中分割的字符子图像的宽度为N, 若N<24, 则将其和相邻子图像合并。

(2) 在子图像内移动48×24的滑动窗口, 计算窗口内图像的纹理特征向量BTV, 与字符模板序列相匹配, 计算字符匹配置信度R1, R2, …, Rd, 其中d=N-23。

(3) 设Rmax=max{Ri, i=1, 2, …, d}, 若Rmax大于给定阈值, 则匹配成功, 其对应的窗口区域为字符, 否则, 将此子图像和相邻子图像合并, 转 (2) 。

最后的字符精分割结果如图9所示。

4 实验结果

本文对154幅有严重影响的车牌图像进行字符分割, 正确分割率为98.7%, 在具有PⅣ2.66GHz CPU, 512MB内存的计算机上运行由MATLAB编写的本算法程序, 平均用时8.530s, 实际应用时采用C语言编程能够满足实时性要求。在相同的实验环境下应用文献[4]中的算法, 正确分割率为97.4%, 平均用时8.850s。图10为本文算法与文献[4]中算法的部分实验对比结果。从实验结果看, 文献[4]算法在有半圆的出租车标志牌干扰信息时分割失败, 而本文算法能正确分割。而且, 对光照不均、对比度较小、倾斜、污迹严重、褪色、字符粘连和断裂等质量严重退化的车牌图像, 本文算法也具有更好的分割效果。

5 结论

本文提出的算法具有很好的车牌字符分割性能。采取的图像预处理技术较好地解决了车牌图像光照不均、对比度较小、倾斜等问题;所采取的由粗到精, 两级反馈的方法能正确地分割污迹、褪色、字符粘连和断裂等严重影响的车牌字符图像。特别是在基于识别反馈的字符分割中, 通过对字符的垂直投影进行离散余弦变换, 应用其低频系数重构垂直投影, 可抑制噪声, 在此基础上构建的纹理特征更能反映车牌的字符纹理, 提高了字符分割的准确率。

参考文献

[1]宋建才.汽车牌照识别技术研究[J].工业控制计算机, 2004, 17 (4) :44-45.

[2]Zhang Jian, Fan Xiaoping, Huang Cailun.Research On characters seg-mentation and characters recogition in intelligent license plate recogi-tion system[C]//Proceedings of the 25th Chinese Control Conference, Harbin, 2006:1753-1755.

[3]迟晓君, 孟庆春.基于投影特征值的车牌字符分割算法[J].计算机应用研究, 2006, 7 (2) :256-257.

[4]Jia Xiaodan, Wang Xinnian, Li Wenju, et al.A novel algorithm for char-acter segmentation of degraded license plate based on prior knowledge[C]//Proceedings of the IEEE International Conference on Automa-tion and Logistics, Jinan, 2007:249-253.

[5]朱俊梅, 陈少平.基于改进的投影方法的车牌图像字符分割[J].中南民族大学学报:自然科学版, 2007, 26 (4) :58-61.

[6]王兴玲.最大类间方差车牌字符分割的模板匹配算法[J].计算机工程, 2006, 32 (19) :193-195.

[7]邓红耀, 管庶安, 宋秀丽.投影和模板匹配相结合分割车牌字符[J].计算机工程与设计, 2008, 29 (6) :1568-1570.