笔迹手写识别

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
17,No.
9,September2006,pp.
18601866http://www.
jos.
org.
cnDOI:10.
1360/jos171860Tel/Fax:+86-10-625625632006byJournalofSoftware.
Allrightsreserved.
一种高效的数字笔迹多维数据编码算法李俊峰+,戴国忠(中国科学院软件研究所人机交互技术与智能信息处理实验室,北京100080)AnEfficientDigitalInkMulti-DimensionDataCodingAlgorithmLIJun-Feng+,DAIGuo-Zhong(HumanComputerInteractionandIntelligentInformationProcessingLaboratory,InstituteofSoftware,TheChineseAcademyofSciences,Beijing100080,China)+Correspondingauthor:Phn:+86-10-62540434,E-mail:solemnizeljf@hotmail.
com,http://www.
iscas.
ac.
cnLiJF,DaiGZ.
Anefficientdigitalinkmulti-dimensiondatacodingalgorithm.
JournalofSoftware,2006,17(9):18601866.
http://www.
jos.
org.
cn/1000-9825/17/1860.
htmAbstract:AnefficientdigitalinkdatacodingalgorithmIWPHSP(integerwaveletpacketbasedhierarchicalsetpartitioned)isproposedinthispaper.
Thealgorithmcompressesdigitalinkmulti-dimensiondatalosslesslyusingthreeapproaches:integerwaveletpackettransform,hierarchicalsetpartitioned,significantbitscombinationcodeandfastadaptivearithmeticcode.
TheexperimentsshowthattheIWPHSPalgorithmisefficient.
Keywords:digitalinkmulti-dimensiondatacoding;integerwaveletpackettransform;hierarchicalsetpartitioned;fastadaptivearithmeticcode摘要:提出了一种高效的数字笔迹数据编码算法IWPHSP(integerwaveletpacketbasedhierarchicalsetpartitioned).
该算法通过引入整数小波包变换、层次性集合分裂、重要位组合编码和快速自适应算术编码等方法,无损地压缩了数字笔迹多维数据.
实验证明,提出的IWPHSP算法是高效的.
关键词:数字笔迹多维数据编码;整数小波包变换;层次性集合分裂;快速自适应算术编码中图法分类号:TP391文献标识码:A笔式交互由于其基于纸笔隐喻、接近人们日常生活、自然高效的交互方式,已成为人机交互领域的一个热点.
在笔式交互过程中,用户通过数字笔输入数字笔迹,完成交互任务.
从数据角度上看,数字笔迹由若干笔划组成,每个笔划是数字笔在一次相继地按下和抬起之间所经过的笔迹;笔划由若干采样点组成,采样点一般有X坐标值、Y坐标值、压力值、时间值等属性.
如果用整数表示各个属性,则需要16个字节描述一个采样点.
由于数字笔的采样频率达到100Hz~133Hz,用户如果连续书写1分钟,数字笔迹的存储空间就需要1.
6KB.
庞大的数据量对计算机容量和网络传输技术都提出了很高的要求,这成为笔式交互深入发展的瓶颈.
因此,数字笔迹数据压缩成为笔式交互技术中的重要课题.
SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.
60273024,60033020(国家自然科学基金);theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.
2002CB312103(国家重点基础研究发展规划(973));theKeyInnovationProjectfromInstituteofSoftware,theChineseAcademyofSciences(中国科学院软件研究所创新基金重大项目)Received2005-07-06;Accepted2005-10-11李俊峰等:一种高效的数字笔迹多维数据编码算法1861为了方便数字笔迹的传输、处理、表示,W3C(worldwidewebconsortium)制定了InkML[1]标准,使数字笔迹可以在不同的应用之间实现互换.
InkML规范了数字笔迹存储格式,可用作手写识别、签名验证等功能.
InkML支持完整的手写笔迹表示方式,除了数字笔的位置,也可以记录笔的倾角、压力等.
但在InkML中,数字笔迹数据压缩并没有被深入研究.
胡云飞[2]设计了一种基于曲线拟合进行数字笔迹存储的方法.
该方法采用三阶B样条曲线作为拟合使用的曲线,综合了等距加权采样算法以及折点识别算法等算法的优点,对数字笔迹进行了压缩,平均压缩比为40%.
微软公司采用两种方式对数字笔迹进行压缩[3]:一种是直接压缩;另一种是转换为图像格式(GIF)存储.
但是,这些压缩方法都属于有损压缩,而且仅仅适用于采样点属性只有X坐标值和Y坐标值的情况.
为了无损地压缩数字笔迹的多维数据,本文提出一种编码算法IWPHSP(integerwaveletpacketbasedhierarchicalsetpartitioned).
该算法利用可逆整数小波包变换去除数字笔迹数据在时间维度上的强相关性,然后从变换系数自身特点出发,通过层次性集合分裂的编码方法,对变换系数进行嵌入式编码.
同时,部分编码结果用快速自适应算术编码再次压缩.
实验结果证明,算法能够无损地、高效率地压缩数字笔迹的多维数据.
1数字笔迹多维数据编码算法数字笔迹多维数据I在数据角度上看由笔划组成,I={Si|i∈[1,n],n为笔划数}.
笔划Si由采样点组成,ijL()[]{},,,|1,,iiiiiijjjjjiiSLxyptjkk=∈为采样点数.
由于数字笔的采样频率一般达到100Hz~133Hz,所以数字笔迹多维数据在时间维度上具有强相关性.
图1给出了数字笔迹截图及相应的多维数据.
(a)Captureviewofdigitalink(b)Correspondencemulti-dimensiondata(a)数字笔迹截图(b)相应的多维数据Fig.
1Thecaptureviewandmulti-dimensiondataofthedigitalink图1数字笔迹截图及相应的多维数据从图1可以看到:同一笔划内的属性具有相关性,而且不同笔划间的相同属性值也具有相关性,特别是时间值属性.
为了最大限度地去除数字笔迹属性值在时间维度上的相关性,编码算法将多个笔划Si合为一个笔划S,()[]1,,,|1,,njjjjjiiSLxyptjkkk==∈=∑.
为了解码需要,将原笔划包含的点数进行记录,K={ki|i∈[1,n]}.
由于采样点不同属性之间不存在相关性,所以编码算法会对K,X,Y,P,T分别进行压缩,其中X,Y,P,T分别是数字笔迹x坐标、y坐标、压力p、时间t属性值的集合.
为了方便起见,仅对编码算法压缩X集合进行叙述,X={xj|j∈[1,k]},其余集合的压缩类似于X集合的压缩.
IWPHSP数字笔迹多维数据编码算法过程如图2所示.
由于整数小波包变换具有优异的时频局部能力以及良好的去相关能力,编码算法首先利用整数小波包变换得到变换系数.
然后从变换系数自身特点出发,通过层次性集合分裂的编码方法对变换系数进行嵌入式编码.
同时,部分编码结果用快速自适应算术编码再次压缩.
1862JournalofSoftware软件学报Vol.
17,No.
9,September2006Kpropertyset……………………YpropertysetIntegerwaveletpackettransformInkmulti-dimensiondataHierarchicalsetpartitionedOutputbitsstreamWaveletcoefficientsEmbededbitsXpropertysetPpropertyset…………Tpropertyset…………Fig.
2IWPHSPdigitalinkmulti-dimensiondatacodediagram图2IWPHSP数字笔迹多维数据编码算法流程图1.
1整数小波包变换(integerwaveletpackettransform)自20世纪80年代末期Mallat[4]首次将快速小波变换引入数据处理以来,小波变换得到了广泛的应用,并取得了良好的效果.
但在实际应用中,快速小波变换有其自身的弱点:(1)需要作卷积运算,计算复杂;(2)对数据的尺寸有要求.
为此,Swelden[5]提出了基于提升模式的小波变换,它使人们用一种简单的方法来解释小波的基本理论,并且在提升模式下建立的整数小波变换具有变换可逆、运算简单、整数存储等优点,在图像压缩领域[6]得以深入的研究.
基于提升模式的整数小波变换分为分裂(split)、预测(predict)和更新(update)3个步骤.
分裂:将数据X分裂成两个互不相交的子集,通常是奇偶分裂,即E0(n)=X(2n);O0(n)=X(2n+1).
预测:采用预测算子P作用于偶信号,得到奇信号的预测值0PE,再将O0与预测值相减得到预测误差O1,即))(int()()(001nEnOnOP=.
更新:采用更新算子U作用于预测误差O1,得到偶信号的更新值,再将E1UO0与更新值相减得到E1,即))(int()()(101nOnEnEU=.
其中,int()为取整函数.
经过上述3个步骤后,数据实际上被分解为两个频率部分:偶信号对应低频;奇信号对应高频.
然而,在小波变换中,分解层数是一个模糊的数量,由编码算法任意规定.
更重要的是,进一步的分解只作用于低频部分,高频部分保持不动,这使得小波变换在处理高频部分复杂的数据时出现效果不理想等情况.
小波包变换[7]是小波变换的推广.
与小波变换不同的是,数据的高频部分也和低频部分一样被递归分解,所以它能够提供更灵活的、更适合于数据时频域特性的分解方式.
为了选择合适的小波包基,人们开展了大量的研究工作,大体上可分为全局搜索和局部搜索两种.
其中,全局搜索算法[8]必须等小波包完全分解后才能进行搜索,这无疑会大大增加计算量,影响数据的编码速度;而在局部搜索算法[9]中,通过定义费用指标,一边分解,一边判别父节点费用与子节点费用和的关系,对不满足条件的节点将停止分解,这使得编码速度有了大幅度的提高.
本文给出一种新的整数小波包变换算法,LSS为待分解集合列表,LDS为已分解集合列表,定义费用指标为∑∈=ZxjjxZF)(,Z为X的子集.
(1)初始化LSS为X集合,LDS为空集(2)处理LSS中的每一个集合Z,直到LSS为空集计算集合Z的费用∑∈==ZxjjxZFC)(利用整数小波变换,将Z分解为两个子集合Ze,Zo计算子集合费用和C′=F(Ze)+F(Zo)如果C′≤C,将Ze,Zo加入到LSS中,从LSS中去除Z李俊峰等:一种高效的数字笔迹多维数据编码算法1863否则,将Z从LSS移至LDS显然,整数小波包变换在具备整数小波变换快捷、能够在当前位置上完成计算、能够对任意尺寸数据进行变换等优点的同时,由于采用了变换系数幅值和的费用指标,使得变换结果的幅值和大幅度降低,为随后的嵌入式编码打下了良好的基础.
1.
2层次性集合分裂编码(hierarchicalsetpartitionedcoding)为了更好地对整数小波包变换后的变换系数进行编码,IWPHSP借鉴了图像编码中嵌入式编码的思想.
尤其是Asad和Pearlman提出的SPECK[10]算法,该算法具有完全嵌入性、渐进传输性、低计算复杂性、较高的信噪比和较好的图像复原质量等优点.
然而,理论分析和实验结果表明,该算法也存在一些不足.
具体表现为:当某一集合Z在当前量化步长下是非重要的,它会被留在LIS中,随着量化步长的更新,Z会不断地被测试,直到在某一量化步长下成为重要集合而被进一步分解为止.
在每一次测试中,由于Z是非重要集合,SPECK编码器会输出"0"作为解码标志.
由于IWPHSP将会对数字笔迹多维数据进行无损压缩,如果直接应用SPECK算法的基本步骤,那么上述情况会大量出现,必然导致编码器的低效.
而且在整数小波包变换后,LDS中的集合分布于各级分解层,已经不适合采用八带分裂的方式.
因此,本文给出层次性集合分裂编码方法HSP,通过改变SPECK编码算法的基本步骤,使得编码方法适合于整数小波包变换的结果,同时改进了整体编码算法的性能.
HSP编码算法的核心思想是:用"0,1,2,4,…,2n"取代"1,2,4,…,2n"作为编码过程中的量化阈值,n是初始化过程中的最大位面.
对应于每个量化阈值,编码算法建立待分解集合列表LSS,集合的重要性测试、分裂等操作只对当前LSS进行,最大限度地适应于小波系数的幅值特点,提高了编码性能.
集合X进行整数小波包变换后,已分解集合存在于LDS中,LDS={Zi|i=1,2,…,l}.
设LBP为待定位面集合列表,定义集合Z的重要性判定函数Sn(Z)、位面计算函数P(Z)、尺寸函数C(Z)分别为<≤=+∈else,02}{max2,1)(1niZxnnxZSi,=<+=∈∈∈||max0,0||max0,1||maxlog)(2iZxiZxiZxxxxZPiii,C(Z)=size(Z)=集合Z包含的变换系数的数目.
具体算法步骤如下:(1)初始化计算LDS中每一集合的位面ni=P(Zi),将Zi加入到LBP中输出n)(max1ilin≤≤=对应于每个量化阈值,建立待分解集合列表LSSj,其中0≤j≤n如果017,No.
9,September2006如果n=0,退出否则,将n1,转移至(2)HSP算法中用到的方法有ProcessS(),ProcessOne(),ProcessLBP():ProcessS(Z){利用二叉树分裂方法,将集合Z分裂为两个子集Z1,Z2组合输出Sn(Z1)Sn(Z2)处理子集Zm(m=1,2)如果Sn(Zm)=1如果C(Zm)=1,ProcessOne(Zm)否则,ProcessS(Zm)否则如果1因为如果Z集合分裂,那么该Z集合必然是重要的.
所以,在新生成的两个子集Zm中,必然有一个是重要的.
换句话说,组合编码中不会出现"00"的情况.
因此,如果第1个子集已经输出"0",则最后一个"1"无须输出.
(2)二进制自适应算术编码处理LBP中的集合Z,计算Z的位面P(Z),然后利用二进制自适应算术编码输出LBP中集合的位面.
相对于直接输出P(Z),二进制自适应算术编码无疑是较慢的.
但通过分析可知0≤P(Z)≤n,而数据经过整数小波包变换后,一般满足n≤20.
在这种情况下,利用快速算术编码[11]可以得到比较满意的编码效率.
基于算法复杂度、编码效率等因素的考虑,算法没有对符号位、重要位等类型的输出位进行算术编码.
2实验结果与分析实验在整数小波变换中采用5-3[12]提升模式,边缘采用镜面对称处理.
表1给出IWPSHP算法对不同数字笔迹压缩的字节率以及编解码时间,表2给出不同属性值在压缩流中所占的比例.
实验结果表明:IWPSHP能够无损地、高效地压缩数字笔迹多维数据,其中对时间属性的压缩最为有效,对压力属性的压缩效果比较差.
这是由于时间属性相比压力属性而言更为连续,这使得整数小波包变换对时间属李俊峰等:一种高效的数字笔迹多维数据编码算法1865性的相关性去除得更加有效.
在相同的采样点数条件下,字节率与数据的相关性成反比,即数据的相关性越大,字节率越低.
数据的相关性对应于数字笔迹书写的密集程度,如实验中的第2组和第3组(如图3所示),由于第3组的密集性较大,则字节率较低.
而且,IWPSHP的编解码所需的时间很少,这使得IWPSHP适合在实时性系统中应用.
如果数字笔迹含有更多的属性,如数字笔与书写平面所成的角度,IWPSHP同样可以进行高效的压缩.
Table1Thecompressionbyterateandcode/decodetimeondifferentdigitalinkdata表1不同数字笔迹压缩的字节率以及编解码时间Numberofsamplepoints77026032739383970769801Codingdata(Byte)21076739629665951667223525Bytepersamplepoint2.
7362.
5892.
301.
722.
352.
40Timeofcoding(s)0.
0470.
2190.
2190.
2500.
5780.
843Timeofdecoding(s)0.
0470.
2040.
1880.
2190.
4840.
750Table2Thecompressproportionofsamplepointsattributes表2对采样点属性的压缩比例Numberofsamplepoints0.
0228010.
0144930.
0228090.
0237450.
022920.
019329Coordinateproperty0.
4216120.
4066020.
4146460.
4032160.
4239050.
409741Pressureproperty0.
3788420.
4069680.
350060.
3728580.
3733530.
38343Timeproperty0.
1767460.
1719370.
2124850.
200180.
1798220.
1875(a)Theseconddigitalinkdata(b)Thethirddigitalinkdata(a)第2组数字笔迹(b)第3组数字笔迹Fig.
3Thedigitalinkdatawithdifferentdensity图3不同密集程度的数字笔迹3结论本文提出一种数字笔迹多维数据编码算法IWPHSP(integerwaveletpacketbasedhierarchicalsetpartitioned),其优越性主要体现在以下几个方面:(1)全面引入整数小波包变换,通过定义新的费用指标局部搜索最佳基.
编码算法在具备整数小波变换优点的同时,使得变换结果的幅值和大幅度降低,为随后的嵌入式编码打下了良好的基础;(2)充分分析小波系数幅值特点,采用层次性集合分裂方法,使得编码性能有了较大的提高;(3)IWPHSP利用组合编码和快速自适应算术编码,改进了比特分配策略;(4)IWPHSP在提高编码性能的同时,改进集合分裂、测试重要性程序,降低了算法复杂度.
IWPHSP算法在整数小波变换中单独采用5-3提升模式.
但是,通过实验可知:在同一提升模式下,不同的属性值具有不同的压缩效果.
所以,我们希望通过实验选用更加适合数字笔迹多维数据的提升模式,甚至不同属性值选用不同的提升模式,使压缩效果更佳.
另一方面,IWPHSP算法属于无损压缩算法,这使得IWPHSP算法不能应用于有损压缩的情况.
我们希望能对IWPHSP算法进行改进,使之能够满足有损、无损压缩等多种需求.
本文的算法充分结合了整数小波包变换与嵌入式集合分裂编码的优点,对未来数字笔迹多维数据编码算1866JournalofSoftware软件学报Vol.
17,No.
9,September2006法有积极的意义.
References:[1]CheeYM,MaganaJA,FrankeK,FroumentinM,RussellG,MadhvanathS,SeniG,TremblayC,YaegerL.
InkmarkuplanguageW3Cworkingdraft.
2004.
http://www.
w3.
org/TR/2004/WD-InkML-20040928/[2]HuYF,QinYY,DaiGZ.
Methodofstrokestoringandrenderingbasedoncurve-fitting.
JournalofComputerEngineeringandScience,2003,25(5):4245(inChinesewithEnglishabstract).
[3]MicrosoftCorporation.
Save(PresistenceFormat,CompressionMode).
2004.
http://msdn.
microsoft.
com/library/default.
aspurl=/library/en-us/tpcsdk10/lonestar/microsoft.
ink/Classes/ink/Methods/save0.
asp[4]MallatS.
Atheoryformultiresolutionsignaldecomposition:Thewaveletrepresentation.
IEEETrans.
onPatternAnalysisandMachineIntelligence,1989,11(7):674693.
[5]SweldensW.
Theliftingscheme:Aconstructionofsecondgenerationwavelets.
SIAMJournalofMathematicalAnalysis,1998,29(2):511546.
[6]ZhangLB,WangK.
Animagecompressionalgorithmbasedonintegerwavelettransform.
JournalofSoftware,2003,14(8):14331438(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/1433.
htm[7]ColifmanR,WickauserM.
Entropy-Basedalgorithmforbestbasisselection.
IEEETrans.
onInformationTheory,1992,38(2):909996.
[8]XiongZ,RamchandranK,OrchardMT.
Waveletpacketimagecodingusingspace-frequencyquantization.
IEEETrans.
onImageProcessing,1998,7(6):160174.
[9]ChenYY,ZhangB.
Compositewaveletpacketandbestbasis.
JournalofSoftware,1998,9(3):161168(inChinesewithEnglishabstract).
[10]IslamA,PearlmanWA.
Anembeddedandefficientlow-complexityhierarchicalimagecoder.
In:Proc.
oftheInt'lSocietyforeOpticalEngineeringConf.
on.
VisualCommunicationsandImageProcessing.
1999.
294305.
[11]BoddenE,ClasenM,KneisJ.
Arithmeticcodingrevealed.
In:Proc.
oftheProseminarDatenkompression2001,ChairforComputerScienceVI.
UniversityofTechnologyAachen/RWTH.
2003.
100157.
[12]AdamsMD,KossentiniF.
Reversibleinteger-to-integerwavelettransformsforimagecompression:Performanceevaluationandanalysis.
IEEETrans.
onImageProcessing,2000,9(6):10101024.
附中文参考文献:[2]胡云飞,秦严严,戴国忠.
基于曲线拟合的笔迹存储和绘制方法的研究.
计算机工程与科学,2003,25(5):4245.
[6]张立保,王珂.
一种基于整数小波变换的图像编码算法.
软件学报,2003,14(8):14331438.
http://www.
jos.
org.
cn/1000-9825/14/1433.
htm[9]陈玉宇,张钹.
混合小波包与最佳基.
软件学报,1998,9(3):161168.
李俊峰(1976-),男,辽宁盖州人,博士,主要研究领域为人机交互技术,模式识别.
戴国忠(1944-),男,研究员,博士生导师,CCF高级会员,主要研究领域为人机交互技术,实时智能,软件工程.