《中文信息处理技术原理与应用》由会员分享,可在线阅读,更多相关《中文信息处理技术原理与应用(63页珍藏版)》请在金锄头文库上搜索。
1、中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 中文信息处理技术原理与应用(三)北京信息工程学院计算机系李宝安1中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 第三章 汉字字形存储与压缩技术 汉字字形存储与字形码汉字字形存储与字形码 点阵存储与压缩存储点阵存储与压缩存储 汉字压缩存储常见方法分类汉字压缩存储常见方法分类 压缩与还原技术及其重要指标压缩与还原技术及其重要指标 汉字笔画矢量存储方法汉字笔画矢量存储方法 部件组字压缩部件组字压缩 汉字子信息块哈夫曼树存储方法汉字子信息块哈夫曼树存储方法 汉字字形轮廓存储方法汉字字形轮廓存
2、储方法 黑白段与线性增量存储方法黑白段与线性增量存储方法 笔画轮廓压缩存储方法笔画轮廓压缩存储方法 2中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字字形存储与字形码 产生汉字字形的方法有产生汉字字形的方法有模拟式模拟式和和数字式数字式两种:两种:模拟式:模拟式:如字模板、字模摄像、飞点扫描字模、全如字模板、字模摄像、飞点扫描字模、全息照相等,特点是文字质量高,价格较便宜,缺息照相等,特点是文字质量高,价格较便宜,缺点是文字读出机构复杂,读取速度低、维护要求点是文字读出机构复杂,读取速度低、维护要求高,文字变动困难。高,文字变动困难。数字式:数字式:输出文字
3、一致性好,稳定不变,速度快,输出文字一致性好,稳定不变,速度快,文字尺寸变更比较灵活,但存储量大、成本较高。文字尺寸变更比较灵活,但存储量大、成本较高。随着中文信息处理技术的发展,模拟式产生文字随着中文信息处理技术的发展,模拟式产生文字字形的方法已逐渐淘汰,这里只介绍数字式汉字字形的方法已逐渐淘汰,这里只介绍数字式汉字字形产生和存储的方法。字形产生和存储的方法。 3中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字字形的数字化 由于计算机内部只认由于计算机内部只认0 0和和1 1这些二进制代码,汉这些二进制代码,汉字字形信息要想保存下来,也必须象汉字的键字字形
4、信息要想保存下来,也必须象汉字的键盘码和交换码一样,实现计算机内部的盘码和交换码一样,实现计算机内部的“数字数字化化”。 将汉字写在划分有将汉字写在划分有m m行行n n列小方格的网格方块列小方格的网格方块中,该方块称为中,该方块称为mnmn点阵,每个小方格是一个点阵,每个小方格是一个点,有笔画部分是黑点,文字的背景部分是白点,有笔画部分是黑点,文字的背景部分是白点,点阵中的黑点就描绘出汉字字形,称为汉点,点阵中的黑点就描绘出汉字字形,称为汉字点阵字形。字点阵字形。 4中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 不同使用领域对汉字质量的要求 使 用 领 域分
5、辨率(线/毫米)密度品质点阵规格要求(以3.7mm2的五号字为例)监视器显示462.02.5低1616 2424通用型字形简易印刷(一般打印、文稿输出)6162.22.5中2424 32324848 6464制版印刷20250.1高100100精密型字形5中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 整字存储与压缩存储 汉字字形存储按存储方法分为整字存储和压缩汉字字形存储按存储方法分为整字存储和压缩存储两大类。存储两大类。 整字存储整字存储: :把汉字字形点阵信息按字节全部存放把汉字字形点阵信息按字节全部存放在存储器中,需要使用时直接读出,这种存储在存储器中,
6、需要使用时直接读出,这种存储方式就是整字存储,它原理简单、使用方便,方式就是整字存储,它原理简单、使用方便,响应时间快,可以保证字形质量。响应时间快,可以保证字形质量。 压缩存储压缩存储: :不是直接将字形信息存储起来,而是不是直接将字形信息存储起来,而是先用压缩技术对点阵文字信息进行压缩,压缩先用压缩技术对点阵文字信息进行压缩,压缩后的信息存入存储器,使用时,再把压缩信息后的信息存入存储器,使用时,再把压缩信息还原成点阵字形。这样做的目的主要是为了减还原成点阵字形。这样做的目的主要是为了减少存储量。少存储量。6中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 问
7、题:随着近年来存储器价格大幅度下降,并且由于压缩字库在使用时有一个字形还原的过程,出字速度有影响,字形可能存在失真现象等缺点,请问压缩字形存储器在当前是不是毫无竞争力而被淘汰呢? 7中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 回答:NO!8中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 原因压缩存储在价格上存在优势,这不仅因为存储容量本身小、价格低,而压缩存储在价格上存在优势,这不仅因为存储容量本身小、价格低,而且还要考虑到维持电路(如电源、存储器辅助电路等)的开销比整字存且还要考虑到维持电路(如电源、存储器辅助电路等)的开销
8、比整字存储低;储低;汉字字数或字号增加,整字存储的存储量会线性增加,而压缩存储能够汉字字数或字号增加,整字存储的存储量会线性增加,而压缩存储能够方便地应付,存储量增加不多;方便地应付,存储量增加不多;制版印刷用的精密型汉字字形,目前都采用压缩方法存储;制版印刷用的精密型汉字字形,目前都采用压缩方法存储;压缩字形便于制成小型卡式压缩存储的专用字库,体积很小,便于在单压缩字形便于制成小型卡式压缩存储的专用字库,体积很小,便于在单板机和通用微机中使用,所占用的空间较少,在板卡的制造工艺上具有板机和通用微机中使用,所占用的空间较少,在板卡的制造工艺上具有优势;优势;设计压缩字形存储指导思想的改变,不是
9、一味追求压缩率,而是针对克设计压缩字形存储指导思想的改变,不是一味追求压缩率,而是针对克服压缩存储的主要缺点,把提高复原后的汉字质量和出字速度作为主要服压缩存储的主要缺点,把提高复原后的汉字质量和出字速度作为主要解决的问题,把压缩率降到次要地位。这种从实用出发,适当控制压缩解决的问题,把压缩率降到次要地位。这种从实用出发,适当控制压缩率的做法是推广压缩存储的有效措施;率的做法是推广压缩存储的有效措施;某些压缩方法和技术对中文处理系统的设计有启发;某些压缩方法和技术对中文处理系统的设计有启发;计算机计算机CPUCPU的运算速度越来越快,压缩字库的字形还原也越来越快;的运算速度越来越快,压缩字库的
10、字形还原也越来越快;对于计算机辅助设计(如在建筑对于计算机辅助设计(如在建筑CADCAD软件中)等应用领域,经常要求的字软件中)等应用领域,经常要求的字形的变倍处理,采用压缩存储方法更容易实现。形的变倍处理,采用压缩存储方法更容易实现。 9中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字压缩存储常见方法分类 字形压缩方法很多,约有数十种,各有优缺点字形压缩方法很多,约有数十种,各有优缺点和应用对象,将它们归纳一下,可分为两大类:和应用对象,将它们归纳一下,可分为两大类:图形压缩和汉字结构压缩。图形压缩和汉字结构压缩。 图形压缩图形压缩采用了一般二维图形的信息
11、压缩方法;采用了一般二维图形的信息压缩方法;结构压缩结构压缩是针对汉字结构特点而提出的压缩方是针对汉字结构特点而提出的压缩方法。法。 笔画矢量、哈夫曼树、部件组合适合于低、中笔画矢量、哈夫曼树、部件组合适合于低、中质量的通用型汉字宇形压缩;质量的通用型汉字宇形压缩; 字形轮廓适用于高质量通用型汉字字型压缩字形轮廓适用于高质量通用型汉字字型压缩 ; 黑白段、线性增量、笔画轮廓适用于精密型汉黑白段、线性增量、笔画轮廓适用于精密型汉字字型压缩。字字型压缩。10中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 压缩与还原技术及其重要指标 1 1压缩率压缩率,用来衡量压缩后
12、字形存储容量减少的程度。用来衡量压缩后字形存储容量减少的程度。 其中其中L L为压缩前字形所占存储字节数,为压缩前字形所占存储字节数,C C为压缩后字形所占存储字节数。为压缩后字形所占存储字节数。2 2 失真率失真率,用来衡量压缩后字形相对于原来字形失真的程度用来衡量压缩后字形相对于原来字形失真的程度 。其中其中Q Q为压缩前字形的信息量,为压缩前字形的信息量,E E为经压缩还原后失真的信息总量。为经压缩还原后失真的信息总量。3 3字形复原速率字形复原速率R R,用来衡量压缩后复原到原点阵字形的速度。用来衡量压缩后复原到原点阵字形的速度。 R = 1R = 1秒内产生的汉字字形数目秒内产生的汉
13、字字形数目4 4压缩字形的自动生成能力,利用压缩存储方法生成压缩字库的能力。压缩字形的自动生成能力,利用压缩存储方法生成压缩字库的能力。5 5压缩后字形变换能力,包括还原成原点阵字形,生成各种大小字形的变倍性能。压缩后字形变换能力,包括还原成原点阵字形,生成各种大小字形的变倍性能。 L=(L C) 100%Q=E 100%11中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字笔画矢量存储方法基本原理汉字是直线性文字,一个汉字是许多直线段所组成的二维几何图形。如果能够对汉字是直线性文字,一个汉字是许多直线段所组成的二维几何图形。如果能够对这些直线段实现压缩,则整
14、个汉字的字形信息也可得到压缩。这些直线段实现压缩,则整个汉字的字形信息也可得到压缩。笔画矢量压缩中的笔画矢量压缩中的“笔画笔画”指的就是这些直线段,给二维汉字图形加上笛卡儿坐指的就是这些直线段,给二维汉字图形加上笛卡儿坐标标X-YX-Y,汉字笔画(注意,即上述的直线段)。汉字笔画(注意,即上述的直线段)。输出汉字时,用表示字形的各笔画信息,得出笔画形状,一般为输出汉字时,用表示字形的各笔画信息,得出笔画形状,一般为1 1bitbit宽的直线段,宽的直线段,形成该字点阵字形数据。存储汉字的实质就是把字形转化为坐标,输出汉字就是形成该字点阵字形数据。存储汉字的实质就是把字形转化为坐标,输出汉字就是
15、根据坐标转换为字形。根据坐标转换为字形。 具体有三种表达方法:具体有三种表达方法:笔画的两个端点坐标(笔画的两个端点坐标(xi1xi1、yi1yi1)和(和(xi2xi2、yi2yi2),),其其中中i i是汉字图形中某一笔画,是汉字图形中某一笔画,1 1是起点坐标,是起点坐标,2 2是终点坐标。这种表示法叫笔画坐标是终点坐标。这种表示法叫笔画坐标法;法;用矢量表示笔画,即用矢量的起点(用矢量表示笔画,即用矢量的起点(x i1x i1,y i1y i1)和矢量的长度、方向。和矢量的长度、方向。常用矢量在常用矢量在x x、y y轴上的投影长度轴上的投影长度LxiLxi和和LyiLyi表示向量的长
16、度、方向;表示向量的长度、方向;用一系列尾用一系列尾首相接的矢量来表示笔画。矢量有虚实之分,实矢量表示实有笔画,虚矢量表示首相接的矢量来表示笔画。矢量有虚实之分,实矢量表示实有笔画,虚矢量表示没有的空笔画,一个矢量的起点(没有的空笔画,一个矢量的起点(xi1xi1, yi1 yi1)是上一矢量的终点(是上一矢量的终点(x x(i-1i-1)2 2,y y(i-1i-1)2 2)。)。这种表示法叫做矢量存储法。这种表示法叫做矢量存储法。12中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 笔画坐标法 笔画坐标法用存储汉字笔画两个端点坐标来压缩字形信息。若取点阵左上角
17、为坐标原点,对于图3-3(a)的“汉”字,8个笔画端点ABCDBFGHIJKL的坐标(xi,yi),其中 i =l,2,12就确定了“汉”字的字形。若用1616点阵,则x和y值可用4位二进制数来表示,用8位存储器存放“汉”字各端点坐标值,前4位存x值,后4位存y值。13中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 xy7 4 3 0笔画坐标法端点坐标数据结构:“汉”字端点的存储数据 :14中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 从上面从上面“汉汉”字的笔画坐标法存储数据看,存储字的笔画坐标法存储数据看,存储“汉汉”字的笔
18、画字的笔画端点一共用了端点一共用了1212个字节,而直接存储个字节,而直接存储16161616点阵字形需要点阵字形需要28=3228=32个字节。采用笔画坐标法存储个字节。采用笔画坐标法存储“汉汉”字,信息是直接存储的字,信息是直接存储的1 12.72.7,即压缩率为,即压缩率为62.5%62.5%。 据统计,常用六千多汉字的平均笔画根数约为据统计,常用六千多汉字的平均笔画根数约为1414,由此可算出对,由此可算出对应不同点阵字形笔画坐标压缩法所需要的存储量,见表应不同点阵字形笔画坐标压缩法所需要的存储量,见表3 34 4。比。比较表较表3 34 4与对应点阵在整字存储方式下的字节数可知,笔画
19、坐标与对应点阵在整字存储方式下的字节数可知,笔画坐标法可以压缩字形信息,而且,随着字形点阵规格的增加,压缩率法可以压缩字形信息,而且,随着字形点阵规格的增加,压缩率也随之提高,当然,字形的美观也受到更多的损失。也随之提高,当然,字形的美观也受到更多的损失。 如采用如采用16161616点阵时,压缩率为点阵时,压缩率为12.512.5,即所需的存储量下降到,即所需的存储量下降到原来的原来的87.587.5。而采用。而采用32323232点阵,压缩率为点阵,压缩率为72.772.7,存储量下,存储量下降到原来的降到原来的1/31/3以下。实际采用笔画坐标法压缩时,还可使用一些以下。实际采用笔画坐标
20、法压缩时,还可使用一些别的措施进一步提高压缩率。别的措施进一步提高压缩率。15中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 表表3 34 4 笔画坐标法压缩汉字字形的存储量笔画坐标法压缩汉字字形的存储量 16中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 笔画坐标法实例 字形采用字形采用15161516点阵,取坐标原点在字的左上点阵,取坐标原点在字的左上角,角,x x是列数,是列数,y y是行数。因此,每个汉字是是行数。因此,每个汉字是x x方向方向1515个单位、个单位、y y方向方向1616个单位的平面图形。个单位的平面图形
21、。笔画端点坐标范围笔画端点坐标范围x x方向是方向是00E E,y y方向是方向是00F F。 根据存储的汉字每个笔画的端点坐标,生成汉根据存储的汉字每个笔画的端点坐标,生成汉字时,按照一定规律从起点到终点画出每条直字时,按照一定规律从起点到终点画出每条直线,也就形成了汉字线,也就形成了汉字15161516点阵字形。点阵字形。 17中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 (l)存储用的压缩信息 1)1)直接笔画信息直接笔画信息笔画两个端点的坐标值,分为以下两种。笔画两个端点的坐标值,分为以下两种。 基本笔画信息基本笔画信息 有九种。每个基本笔画都用两个字
22、节表示起、终点坐标。有九种。每个基本笔画都用两个字节表示起、终点坐标。 复合笔画信息。复合笔画信息。包括汉字中常出现的一些基本笔画的组合,如图包括汉字中常出现的一些基本笔画的组合,如图3535(1 1)所示。若)所示。若将该图复合笔画的端点和折点给出如图将该图复合笔画的端点和折点给出如图3535(2 2)所示的编号,则)所示的编号,则这些复合笔画的坐标信息列出如表这些复合笔画的坐标信息列出如表3535。因为。因为x x方向坐标范围是方向坐标范围是0 0到到E E,所以,第一字节的第一位所以,第一字节的第一位F F可以作为复合笔画的标志。由表可以作为复合笔画的标志。由表335 5可知,对于复合笔
23、画,没有必要将所有端、折点的坐标值都存可知,对于复合笔画,没有必要将所有端、折点的坐标值都存入,因为未存入的其他点阵坐标可以根据已知信息产生。入,因为未存入的其他点阵坐标可以根据已知信息产生。 横竖撇捺点挑折捺勾双笔竖一丨丿、 乛丨18中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 图3-5 复合笔画及端、折点编号 12312312431234143212341234 A B C D E F G19中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 A AB BC CD DE EF FGG第一字节第一字节 FXFX2 2FXFX2 2
24、FFFFFFFFFFFFFFFFFFFF第二字节第二字节 x x1 1y y1 1x x3 3y y3 3 x x1 1y y1 1 x x2 2y y4 4 x x1 1y y2 2 x x1 1y y1 1 x x1 1y y1 1 第三字节第三字节 x x3 3y y3 3 x x1 1y y1 1 x x3 3y y3 3 x x1 1y y1 1 x x3 3y y4 4 x x3 3y y4 4 x x3 3y y3 3 第四字节第四字节 x x3 3y y3 3 表3-5 复合笔画坐标信息 20中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 2)部
25、件信息 在笔画坐标法中引入部件信息,其含意和部件在笔画坐标法中引入部件信息,其含意和部件组字压缩法不同。这里是把存储器内多个汉字组字压缩法不同。这里是把存储器内多个汉字公用的笔画信息提出来做为部件,并用直接笔公用的笔画信息提出来做为部件,并用直接笔画信息来表示,而且也不组成部件库。画信息来表示,而且也不组成部件库。 在其它汉字用到某个部件时,以两个字节作为在其它汉字用到某个部件时,以两个字节作为指针指向这个部件,即可根据部件的直接笔画指针指向这个部件,即可根据部件的直接笔画信息画出相应的点阵。在笔画坐标法中引出部信息画出相应的点阵。在笔画坐标法中引出部件概念,显然能进一步压缩存储信息量。件概念
26、,显然能进一步压缩存储信息量。 21中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 3)全点阵信息 某些笔画多又便于拆成部件的字,存放全部点某些笔画多又便于拆成部件的字,存放全部点阵信息反而能使信息量小些。例如阵信息反而能使信息量小些。例如“囊囊”字有字有2626段笔画,用笔画坐标存储需段笔画,用笔画坐标存储需5252字节,而点阵字节,而点阵直接存储只要直接存储只要3232字节。字节。 综上所述,用笔画坐标构成的压缩存储器是汉综上所述,用笔画坐标构成的压缩存储器是汉字自行端点坐标信息和部件指针信息的集合。字自行端点坐标信息和部件指针信息的集合。汉字中相同部件的笔
27、画信息集中存放,它和其汉字中相同部件的笔画信息集中存放,它和其他汉字是通过部件指针互相联系的。他汉字是通过部件指针互相联系的。22中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 (2) 汉字的生成 用笔画坐标法构成压缩存储器后,接着就是根据这些用笔画坐标法构成压缩存储器后,接着就是根据这些信息形成被查找的汉字点阵,使输出的汉字笔画布局信息形成被查找的汉字点阵,使输出的汉字笔画布局匀称,清晰美观。这主要是解决如何区分笔画类型和匀称,清晰美观。这主要是解决如何区分笔画类型和写出合适的笔画这两个问题。写出合适的笔画这两个问题。 1)1)笔画的区分笔画的区分 23中文信
28、息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 2 2)笔画的形成笔画的形成 形成横、竖、双笔竖等笔画点阵比较直观,如对坐标形成横、竖、双笔竖等笔画点阵比较直观,如对坐标(x x1 1y y1 1)起到(起到(x xi2i2y y2 2)止的各字节止的各字节y y1 1位置上全部位置上全部x x值置值置“1 1”就形成笔画横的点阵。就形成笔画横的点阵。 对于撇、捺、挑、捺钩等笔画,由于同一笔画各段粗对于撇、捺、挑、捺钩等笔画,由于同一笔画各段粗细不同,在不同字中形状也不一样,所以要根据它们细不同,在不同字中形状也不一样,所以要根据它们在不同字形的不同位置和各段不同粗细
29、来形成合适的在不同字形的不同位置和各段不同粗细来形成合适的点阵。这些笔画各段的粗细变化是有规律的、连续的,点阵。这些笔画各段的粗细变化是有规律的、连续的,利用这一点可以形成对应于各段粗细不同的笔画点阵。利用这一点可以形成对应于各段粗细不同的笔画点阵。 而同一种笔画在不同字中或在同一字的不同部位有不而同一种笔画在不同字中或在同一字的不同部位有不同的斜率,是随着笔画坐标差同的斜率,是随着笔画坐标差x x和和y y的比值而变化,的比值而变化,是坐标差之比的函数。所以,根据是坐标差之比的函数。所以,根据x /x /y y可分类形成可分类形成不同形状的同一种笔画。不同形状的同一种笔画。24中文信息处理技
30、术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 矢量存储法 取坐标原点为文字的左上角,用一系列矢量表示汉字字形的笔画,在存储器内存储矢量的端点到一矢量端点的坐标增量。x(或y)增量为正,表示自左向右(或自上向下);为负则反之。规定每个汉字的第一矢量起点是坐标原点,实矢量为实有笔画,用“1”表示;虚矢量是没有的空笔画,用“0”表示 25中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 表表3-9 3-9 对应于图对应于图3-73-7(c c)“汉汉”字矢量存储法的数据字矢量存储法的数据 矢 量xy实矢量/虚矢量OA110AB221BC-310CD2
31、21DE-190EF3-71FG1-60GH801HI-481IJ-551JK2-110KL361LM55126中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 字形信息的描述 对于对于16161616点阵,用两个字节表示一个矢量。点阵,用两个字节表示一个矢量。 其中其中F F称为笔形特征,有称为笔形特征,有6 6位二进制数,用位二进制数,用“000000000000”表示空笔画,用表示空笔画,用“000001000001”表示实表示实笔画,当笔画,当F F“111111111111”时表示实笔画的末笔。时表示实笔画的末笔。x x,y y各用各用5 5位二进制数,
32、包括了一位符号位二进制数,包括了一位符号位,位,x x、y y可以表示可以表示1515到到1515之间的任何整之间的任何整数。数。 F x y 15 10 9 5 4 0 27中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 笔形特征的利用 上述矢量表示中,笔形特征上述矢量表示中,笔形特征F F未能充分利用,可未能充分利用,可用它来扩展矢量表示法的功能。例如在汉字中,用它来扩展矢量表示法的功能。例如在汉字中,组合笔画组合笔画“口口”用得很多,可以定义一种专用用得很多,可以定义一种专用表示表示“口口”的笔形码,如的笔形码,如 : : 由于某一种笔形特征后还有由于某一
33、种笔形特征后还有x x,y y作为参数,作为参数,所以,其表现能力是很强的。例如所以,其表现能力是很强的。例如“口口”笔形笔形信息,可表示各种大、小、长、扁的信息,可表示各种大、小、长、扁的“口口”,而且只要把起点设置好就可以放到任何位置上。而且只要把起点设置好就可以放到任何位置上。利用笔形特征利用笔形特征F F剩余的编码,可定义几十种常剩余的编码,可定义几十种常用的组合笔画,以进一步压缩字形信息。用的组合笔画,以进一步压缩字形信息。0 0 0 0 1 0 x y 15 10 9 5 4 0 28中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 F000010表示
34、“口”字形, x, y是“口”的宽度和高度。它实际上取代了由四个矢量组合而成的“口”字。0000010y000001x00000010-y000001-x0再如,我们用F 000011表 示组合笔画“冂”它也由四个矢量组成。0000010y000001x00000010-y000001 -x029中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 部件信息的利用 汉字中,有些部件使用率很高,如氵、木、忄、汉字中,有些部件使用率很高,如氵、木、忄、扌、讠、礻、艹、纟、亻、彳、冫等等,很多扌、讠、礻、艹、纟、亻、彳、冫等等,很多汉字都共有这些部件。把它们做成标准部件,汉
35、字都共有这些部件。把它们做成标准部件,这些部件在汉字中有固定位置,这样,在许多这些部件在汉字中有固定位置,这样,在许多字中可以直接调用这些部件信息,可以进一步字中可以直接调用这些部件信息,可以进一步压缩存储量。压缩存储量。如规定如规定F F100000100000为调用标准部件命令,为调用标准部件命令,D D是指是指向标准部件的指针,有十位二进制,可以表示向标准部件的指针,有十位二进制,可以表示10241024种部件。种部件。30中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 1 0 0 0 0 0 D15 10 9 0 31中文信息处理技术中文信息处理技术中文
36、信息处理技术原理与应用原理与应用原理与应用 字形信息的还原 字形信息还原指的是从矢量信息反转成点阵信息。字形信息还原指的是从矢量信息反转成点阵信息。1 1) 用程序把部件调用信息和组合笔画信息转换成矢量信息。用程序把部件调用信息和组合笔画信息转换成矢量信息。2 2) 把有序实虚矢量还原成点阵把有序实虚矢量还原成点阵凡是虚笔画不描点,只是改变起点位置。凡是虚笔画不描点,只是改变起点位置。凡凡是是实实笔笔画画要要描描点点,根根据据x x,y y值值决决定定描描点点数数和和方方向向。由由下列直线方程决定下列直线方程决定 y yy /y /x x x x 其中,其中,x x1 1,2 2,33(x x
37、,y0y0) 若若x x是是正正,向向右右走走;x x是是负负,向向左左走走。y y为为正正则则下下走走,y y为为负负则则上上走走。这这样样,对对应应一一个个x x,计计算算出出y y,取取整整后后决决定定描点的位置。描点的误差小于等于描点的位置。描点的误差小于等于0.50.5格。格。 矢量存储法的压缩率是笔画矢量法中最高的,缺点是生成点矢量存储法的压缩率是笔画矢量法中最高的,缺点是生成点阵信息较慢。笔画矢量压缩共同的缺点是生成的字形不大美阵信息较慢。笔画矢量压缩共同的缺点是生成的字形不大美观,对观,对16161616点阵压缩率较低。点阵压缩率较低。 32中文信息处理技术中文信息处理技术中文
38、信息处理技术原理与应用原理与应用原理与应用 子信息块哈夫曼树压缩 汉字点阵的冗余度 具有最小带权路径长度的哈夫曼(Huffman)树 哈夫曼树的构成和压缩码的获得 主要算法和结果33中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字点阵的冗余度 汉字是一种二维图形,可以从图形角度进行信息压缩。将汉字点阵图形分割成汉字是一种二维图形,可以从图形角度进行信息压缩。将汉字点阵图形分割成mnmn子子矩阵,称为子信息块,发现有许多子信息块是相同的,说明汉字图形有较大冗余度。矩阵,称为子信息块,发现有许多子信息块是相同的,说明汉字图形有较大冗余度。因此,利用子信息块编码存
39、储,便可达到压缩汉字点阵信息量的目的。因此,利用子信息块编码存储,便可达到压缩汉字点阵信息量的目的。 在在16161616、24242424汉字点阵图形中,子信息块可取汉字点阵图形中,子信息块可取2222,1313,2121,1212等。对于等。对于mnmn子信息块子信息块, , 所表达的状态数所表达的状态数N N为为: : N=2 N=2 mnmn 如对于如对于2222子信息块,有子信息块,有N N1616种状态。这种状态。这N N种子信息块状态在汉字中并不足等概率出种子信息块状态在汉字中并不足等概率出现的,实际出现的概率颁布和等概率有较大偏差,偏差愈大,对压缩编码愈有利。现的,实际出现的概
40、率颁布和等概率有较大偏差,偏差愈大,对压缩编码愈有利。 由于汉字使用的笔画中横、竖为多,而且横多于竖,所以相邻子信息块关系密切,左由于汉字使用的笔画中横、竖为多,而且横多于竖,所以相邻子信息块关系密切,左右相信的子信息块关系最密切。例如,某汉字的一个子块如图右相信的子信息块关系最密切。例如,某汉字的一个子块如图310310(a a)所示,则其)所示,则其相邻的右边的子块的状态如图相邻的右边的子块的状态如图310310(a a)的概率要远大于如图)的概率要远大于如图310310(b b)的概率。)的概率。 (a) (b) 图3-10 两种子块的状态图3-1034中文信息处理技术中文信息处理技术中
41、文信息处理技术原理与应用原理与应用原理与应用 子信息块哈夫曼树压缩的设计思想 汉字点阵中各相邻的子块之间具有一定的统计规汉字点阵中各相邻的子块之间具有一定的统计规律。如果汉字采用全点阵信息表示,其冗余度很律。如果汉字采用全点阵信息表示,其冗余度很大。对子信息块状态进行统计分析,可以得到一大。对子信息块状态进行统计分析,可以得到一个各状态出现概率的高低序列,设法使概率高的个各状态出现概率的高低序列,设法使概率高的代码短,概率低的代码长,从而使平均码最短,代码短,概率低的代码长,从而使平均码最短,这就是哈夫曼树算法,所以利用汉字点阵的冗余这就是哈夫曼树算法,所以利用汉字点阵的冗余度和哈夫曼树具有最
42、小带权路径长度这个性质,度和哈夫曼树具有最小带权路径长度这个性质,能将汉字点阵信息进行压缩。能将汉字点阵信息进行压缩。35中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 具有最小带权路径长度的哈夫曼(Huffman)树 怎样利用汉字点阵的冗余度进行压缩编码呢?用怎样利用汉字点阵的冗余度进行压缩编码呢?用哈夫曼树是一个好办法。哈夫曼树是一个好办法。 给定数列给定数列w1,w2,wnw1,w2,wn,以此,以此n n个数构成森林个数构成森林F F。其中,每棵树其中,每棵树TiTi的根结点为的根结点为Wi Wi ,而其左、右子树,而其左、右子树均为空。将均为空。将F
43、FT1,T2,TnT1,T2,Tn从小到大排序,先从小到大排序,先取出取出T1,T2T1,T2组成一棵树,使其根结点组成一棵树,使其根结点T TT1+T2T1+T2,然后再根据其大小插入到然后再根据其大小插入到F F中去。反复此过程,直中去。反复此过程,直到到F FT T只有一棵树为止。这样构成的树称为哈夫只有一棵树为止。这样构成的树称为哈夫曼树曼树 。36中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 哈夫曼(Huffman)树建造实例 例如例如WG= WG= 7 7、5 5、2 2、4 4,其构造过程如图其构造过程如图311311所示,在所示,在这个数列中的
44、每个数对应哈夫这个数列中的每个数对应哈夫曼树的一片叶子,这些叶子即曼树的一片叶子,这些叶子即哈夫曼树所带的权。此例的构哈夫曼树所带的权。此例的构造过程共造过程共4 4步,其带权路径长步,其带权路径长度为度为 WPLWPL7 75252232343433535 从构造过程可明显看出,这样从构造过程可明显看出,这样的哈夫曼树必然具有最小的带的哈夫曼树必然具有最小的带权路径长度。用哈夫曼树叶子,权路径长度。用哈夫曼树叶子,权值大的离根近,权值小的离权值大的离根近,权值小的离根远的性质可以形成最短编码。根远的性质可以形成最短编码。图3-11 哈夫曼树构造过程 37中文信息处理技术中文信息处理技术中文信
45、息处理技术原理与应用原理与应用原理与应用 哈夫曼树的构成和压缩码的获得 将给定某子信息块相邻将给定某子信息块相邻N N个子信息块状态的概个子信息块状态的概率,这率,这N N个数列作为叶子,用哈夫曼算法构成个数列作为叶子,用哈夫曼算法构成哈夫曼树,并取每一级的左路径代码为哈夫曼树,并取每一级的左路径代码为0 0,右,右路径代码为路径代码为1 1,从树根开始到相应的叶子,即,从树根开始到相应的叶子,即可得到不等长的编码。可得到不等长的编码。 设取设取2222子块,共有子块,共有1616种不同状态,如图种不同状态,如图312312所示。设给定子块状态为所示。设给定子块状态为P0P0,在这个条件下,在
46、这个条件下,其相邻子点阵的其相邻子点阵的1616种不同状态产生的概率为种不同状态产生的概率为w0w0、w1w1、w2w2、w15w15,如表,如表312312所示。表中所示。表中概率值是统计具有代表性的概率值是统计具有代表性的384384个个14141414点阵点阵汉字所得。汉字所得。38中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 图3-12 22子块的16种状态表3-12 相邻于P0的16种不同状态子块产生的概率 39中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 以以w0w0、w1w1、w2w2、w15w15为叶子构成哈为
47、叶子构成哈夫曼树,并取毎一级夫曼树,并取毎一级的左路径代码为的左路径代码为0 0,右,右路径代码为路径代码为1 1,如图,如图331313所示。所示。 由于子块的状态有由于子块的状态有1616种,因而构成的哈夫种,因而构成的哈夫曼树有曼树有1616棵。棵。 从哈夫曼树根起到树从哈夫曼树根起到树叶止,可得到对应该叶止,可得到对应该树叶的状态的代码,树叶的状态的代码,如表如表313313所示所示 图3-13 以表3-12中的数列构成的哈夫曼树40中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 状态状态条件概率值条件概率值代码代码P P0 00.4380.4381 1
48、P P1 10.0500.0500000000000P P2 20.0110.01101110000111000P P3 30.0410.0410001000010P P4 40.0320.0320110001100P P5 50.1320.132010010P P6 60.0320.0320001100011P P7 70.0140.014011011011011表3-13 图3-13的哈夫曼树叶的状态代码41中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 由表由表313313可见,发生概率小的状态分得的代码可见,发生概率小的状态分得的代码长,发生概率大的状态
49、分得的代码短。这样,长,发生概率大的状态分得的代码短。这样,平均代码长度就缩短了。平均代码长度就缩短了。 平均代码长度带权路径长度平均代码长度带权路径长度0.43810.43810.05050.05050.01170.01170.04150.04150.03250.03250.13230.13230.03250.03250.01460.01460.01160.01160.02460.02460.14830.14830.02360.02360.02550.02550.00280.00280.01560.01560.00180.00182.82.8 而变换前子块平均代码长为而变换前子块平均代码长为
50、4 4,由于变换后所,由于变换后所得代码的平均长度缩短,所以用子信息块哈夫得代码的平均长度缩短,所以用子信息块哈夫曼树法可以压缩存储量。曼树法可以压缩存储量。42中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 主要算法和结果 用子信息块哈夫曼树压缩汉字字形,其主要算法有五个:(用子信息块哈夫曼树压缩汉字字形,其主要算法有五个:(1 1)哈)哈夫曼树叶子的获得夫曼树叶子的获得 频次(正比于条件概率值)统计算法。(频次(正比于条件概率值)统计算法。(2 2)哈夫曼树的构造算法。(哈夫曼树的构造算法。(3 3)优化哈夫曼树的构造算法。()优化哈夫曼树的构造算法。(4
51、4)压)压缩算法。(缩算法。(5 5)还原算法。)还原算法。 下面给出一个用子信息块哈夫曼树压缩汉字字形的结果。下面给出一个用子信息块哈夫曼树压缩汉字字形的结果。 字数字数39433943,其中包括一级汉字,其中包括一级汉字37553755个。个。 点阵点阵14151415,按列存储。,按列存储。 子信息块为子信息块为2222。 压缩率为压缩率为32.932.9,汉字若采用,汉字若采用24242424点阵,压缩率可点阵,压缩率可 达到达到4848。 还原速度,用软件每秒还原速度,用软件每秒8080个字。个字。 子信息块哈夫曼树压缩法,压缩率虽比笔画矢量法、部件组字法子信息块哈夫曼树压缩法,压缩
52、率虽比笔画矢量法、部件组字法为低,但它的最大特点是压缩后复原的字形和原点阵字形完全相为低,但它的最大特点是压缩后复原的字形和原点阵字形完全相同,是一种可逆式压缩方法,即其失真率为同,是一种可逆式压缩方法,即其失真率为0 0。因而,输出字形质。因而,输出字形质量远胜于前述两种方法输出的字形。量远胜于前述两种方法输出的字形。43中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 字形轮廓压缩 设计思想:汉字字形这种特殊的二值图像由象素设计思想:汉字字形这种特殊的二值图像由象素为为1 1的笔画构成,有着确定、封闭的轮廓,字形与的笔画构成,有着确定、封闭的轮廓,字形与轮廓有
53、一一对应关系。如果记下了轮廓,也就代轮廓有一一对应关系。如果记下了轮廓,也就代表存储了字形。表存储了字形。 字形轮廓压缩的过程首先是跟踪字形轮廓,用链字形轮廓压缩的过程首先是跟踪字形轮廓,用链接码存储,其次,在还原时将轮廓内部区域充黑接码存储,其次,在还原时将轮廓内部区域充黑(即置成(即置成1 1),生成点阵字形。),生成点阵字形。 由于链接码用矢量记录轮廓,所以通过矢量比例由于链接码用矢量记录轮廓,所以通过矢量比例变换可以方便地使文字尺寸倍率改变。变换可以方便地使文字尺寸倍率改变。44中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 字形轮廓跟踪和链接码存储 跟
54、踪封闭字形轮廓的方法很多,下面介绍一种简单的跟踪封闭字形轮廓的方法很多,下面介绍一种简单的方法。设某黑点的八个方向值如图方法。设某黑点的八个方向值如图314314所示。并设当所示。并设当前点方向值为前点方向值为d0,d0,下一点方向值为下一点方向值为d d,自上而下,从左,自上而下,从左到右对字形扫描,遇到第一个黑点为始轮廓点,记为到右对字形扫描,遇到第一个黑点为始轮廓点,记为DrDr,设,设DrDr的方向值为的方向值为d0d07 7,由当前黑点求下一黑点,由当前黑点求下一黑点的算法为的算法为 (1 1)若)若d04d04,则,则d dd04d04,否则,否则d dd0d04 4。 (2 2)
55、若)若d0d00 0,则,则d d7 7,否则,否则d dd01d01。 (3 3)若按上述二步搜索到下一个黑点,则为下一个轮)若按上述二步搜索到下一个黑点,则为下一个轮廓点,而且回到第一步,否则回到第二步。这样一直廓点,而且回到第一步,否则回到第二步。这样一直跟踪到始轮廓为止。跟踪扫描时要解决封闭曲线中的跟踪到始轮廓为止。跟踪扫描时要解决封闭曲线中的孔和一个文字有多个封闭曲线的问题。孔和一个文字有多个封闭曲线的问题。 图图315315就是一个字形轮廓跟踪的例子。就是一个字形轮廓跟踪的例子。 45中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 图3-14 黑点的
56、八个方向值 图3-15 字形轮廓跟踪示例 46中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 字形轮廓的存储 跟踪出字形的轮廓线后,怎样存储它们呢?跟踪出字形的轮廓线后,怎样存储它们呢? 直观的办法是直接存储轮廓点序列,如果字形直观的办法是直接存储轮廓点序列,如果字形为为64646464点阵,存储每个轮廓点的绝对坐标需点阵,存储每个轮廓点的绝对坐标需要要1212位,存储量大。若存储相对坐标,即绝对位,存储量大。若存储相对坐标,即绝对坐标的差坐标的差 x x, y y,由于,由于 x x, y y各需要表示各需要表示0 0,1 1,11三个值,所以存储一个轮廓点总
57、共三个值,所以存储一个轮廓点总共要要4 4位,大大节省了存储量。位,大大节省了存储量。 更好的办法是采用链接码,存储矢量的方向值。更好的办法是采用链接码,存储矢量的方向值。这样对每个轮廓点只要表示八个方向值,即这样对每个轮廓点只要表示八个方向值,即3 3位就可以了。位就可以了。47中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 一个具体的存储字形轮廓线不同方法需要的存储量例子如表314所示,它是根据1000个楷书字库(6464点阵)统计出来的。存储方法存储方法一字平均一字平均码长码长绝对坐标绝对坐标646.1646.1相对坐标相对坐标215.4215.4链接码链
58、接码161161差分链码差分链码95.895.8表3-14 不同字形轮廓线存储方法的平均码长48中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 轮廓字形填充 在字形复原时,由于压缩存储的是在字形复原时,由于压缩存储的是字形轮廓信息,需要对轮廓内部区字形轮廓信息,需要对轮廓内部区域填充黑,下面介绍两种填充方法。域填充黑,下面介绍两种填充方法。1.1.割线填充割线填充 已知字形轮廓多边形的顶点坐标,已知字形轮廓多边形的顶点坐标,求出求出y yY Ymaxmax点点A A和和y y Y Yminmin点点B B。如。如图图3 31616所示。从所示。从y y Y Ym
59、axmax开始向下开始向下扫描,即用一条水平割线穿过多边扫描,即用一条水平割线穿过多边形,必将与多边形产生偶数个交点形,必将与多边形产生偶数个交点(对于类似于图(对于类似于图316316所示的所示的A A点和点和割线相交,则认为有两个交点),割线相交,则认为有两个交点),第一点与第二点,第三点与第四点,第一点与第二点,第三点与第四点,之间的区域便为内部区域。如之间的区域便为内部区域。如图中图中y yC C割线,在割线,在DEDE、FGFG之间即之间即为内部区域,将这些线段之间的白为内部区域,将这些线段之间的白点置为黑点,即完成填充。这样一点置为黑点,即完成填充。这样一直扫描到直扫描到y y Y
60、 Yminmin为止。为止。图3-16 割线填充49中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 轮廓字形填充2 连通性填充 条件是已知某一区域中的任一白点,那么,用它作种子,把与它连通的所有白点都改为黑点,直至遇到轮廓为止,这样就完成了填充。 这种方法的缺点是要知道所有封闭区域内部的一个确定白点种子。另外,填充时间开销也较大。50中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 比例变换 存储的字形是根据某种特定尺存储的字形是根据某种特定尺寸原稿字形压缩而成的。复原寸原稿字形压缩而成的。复原后,往往要求能输出多种尺寸、后,往往要
61、求能输出多种尺寸、不同大小的文字,这就要藉助不同大小的文字,这就要藉助于比例变换技术,对存储字形于比例变换技术,对存储字形进行放大或缩小。进行放大或缩小。 下面介绍两种比例变换的方法。下面介绍两种比例变换的方法。1 1。点阵线性变换。点阵线性变换 设原字形点阵为设原字形点阵为A A(i,j i,j), ,变换变换到到B B(x,yx,y),其比例系数为),其比例系数为P1P1i/x, P2i/x, P2j/y,j/y,(见图(见图317317)变)变换方程为换方程为图3-17 点阵字形线性变换51中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 比例变换2 2。矢
62、量线性变换。矢量线性变换 采用字形轮廓矢量存储时,通过矢量线性变采用字形轮廓矢量存储时,通过矢量线性变换,很容易生成大小不同的输出字形,换,很容易生成大小不同的输出字形,设字形轮廓上一矢量为设字形轮廓上一矢量为ABAB(见图(见图331818),始点为),始点为A A,终点为,终点为B B,其坐标分,其坐标分别为(别为(x1,y1x1,y1)和()和(x2,y2x2,y2),对坐标点),对坐标点A A(x1,y1x1,y1),可以看成从坐标原点),可以看成从坐标原点OO到到A A点的矢量点的矢量OAOA,这样就,这样就AB=OB OAAB=OB OA 如要变换到如要变换到PABPAB(P P为
63、常数),则有为常数),则有(公式(公式3636)PABPABPP(OB OAOB OA) P OB P OAP OB P OA (P x2P x2,P y2P y2)(P x1P x1,P y1P y1) 有这种基于矢量的轮廓点到点的变换有这种基于矢量的轮廓点到点的变换是比例变换,对图是比例变换,对图319319而言,如轮廓而言,如轮廓线段线段ABAB放大成新的线段放大成新的线段PAPBPAPB。 字形轮廓压缩,对字形轮廓压缩,对64646464点阵字形,压点阵字形,压缩率为缩率为7575左右,失真率很小,每秒左右,失真率很小,每秒能生成数十个文字。字形压缩复原后能生成数十个文字。字形压缩复原
64、后几乎没有失真。几乎没有失真。图3-18 矢量线性变换图3-1852中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 黑白段与线性增量压缩 用于制版印刷的精密型汉字字形,要求每毫米达到用于制版印刷的精密型汉字字形,要求每毫米达到2020线以线以上的分辨率(例如:激光照排机的文字分辨率为上的分辨率(例如:激光照排机的文字分辨率为29.229.2线线/ /毫毫米),正文五号字点阵为米),正文五号字点阵为108108108108,报用标题特大号字点,报用标题特大号字点阵为阵为576576576576。印刷中使用的字体也很多,有书版宋、报。印刷中使用的字体也很多,有书版宋
65、、报版宋、仿宋、黑体、楷体、长宋、扁宋、长仿宋、长黑、版宋、仿宋、黑体、楷体、长宋、扁宋、长仿宋、长黑、扁黑等,每种体需用十几种字号,每种字号要收扁黑等,每种体需用十几种字号,每种字号要收600060001000010000个汉字,这样,若用点阵存储,总存储量起码为个汉字,这样,若用点阵存储,总存储量起码为210n210n字节,这显然是不允许的。字节,这显然是不允许的。 如果说通用型汉字字形不一定都要压缩存储,那么精密型如果说通用型汉字字形不一定都要压缩存储,那么精密型字形则要求有一整套字形压缩、放大缩小、压缩复原等技字形则要求有一整套字形压缩、放大缩小、压缩复原等技术才能实用。术才能实用。5
66、3中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 黑白段压缩 黑白段压缩是一种对图形压缩编码的方法。汉字中横、竖笔画较多,横笔多于竖笔,用黑白段存储可比点阵直接存储能减少存储量。 用数字化仪逐行扫描字稿,依次记录每行连续的空白点数(白段)和连续的有笔画的点数(黑段),形成以下记录格式。 54中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 行标志重复行数白段黑段行标志重复行数白段黑段白段黑段白段黑段 * * n W1 B1 Wm Bmn W1 B1 Wm Bm每组每组WiWi,BiBi值相当于给出了通过该行的第值相当于给出了通过该行
67、的第i i笔段的起、止位置,若无笔段的起、止位置,若无WW、B B值,则表值,则表示空白行。这种行信息格式(称为列压缩)不仅使压缩信息能自动生成和便于示空白行。这种行信息格式(称为列压缩)不仅使压缩信息能自动生成和便于输出,而且列压缩倍数也是较高的,平均约为输出,而且列压缩倍数也是较高的,平均约为1313倍左右。倍左右。图3-19 文字的黑白段55中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 黑白段压缩的特点 黑白段压缩在行压缩上可用重复列数表示,仅当相邻黑白段压缩在行压缩上可用重复列数表示,仅当相邻n n行的所有黑、白段数值完全相同,即全为空白行或所行的所有
68、黑、白段数值完全相同,即全为空白行或所有笔画均为竖直线时才能压缩,对汉字而言,这种行有笔画均为竖直线时才能压缩,对汉字而言,这种行压缩法显得不得力,这不仅因为汉字笔画中非垂直者压缩法显得不得力,这不仅因为汉字笔画中非垂直者多;还因字稿很难放正,而且噪声、干扰要产生毛刺,多;还因字稿很难放正,而且噪声、干扰要产生毛刺,要大量破坏垂直压缩的条件,这是黑白段压缩法压缩要大量破坏垂直压缩的条件,这是黑白段压缩法压缩倍数不高的根源所在。平均来看,行压缩倍数略低于倍数不高的根源所在。平均来看,行压缩倍数略低于2 2倍。倍。 这种压缩方法为英国蒙纳公司的激光汉字照排机所采这种压缩方法为英国蒙纳公司的激光汉字
69、照排机所采用,它用的汉字原始信息为用,它用的汉字原始信息为1380138013801380点阵,可输出点阵,可输出从从9696磅到磅到5 5磅(磅(33.633.6毫米到毫米到1.751.75毫米)各种字号的高质毫米)各种字号的高质量文字。量文字。56中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 线性增量压缩 线性增量压缩是对黑白段压缩的改进,它仍采用线性增量压缩是对黑白段压缩的改进,它仍采用黑白段信息格式,保留上述的垂直压缩,但增加黑白段信息格式,保留上述的垂直压缩,但增加了一种新的压缩格式,使得只要相邻了一种新的压缩格式,使得只要相邻n n行笔段数相行笔段
70、数相同,各笔段边缘为任何方向的斜线变化都可以压同,各笔段边缘为任何方向的斜线变化都可以压缩,其行信息格式为:缩,其行信息格式为:行标法重复行数白段白段增量黑段黑段增量行标法重复行数白段白段增量黑段黑段增量白段白段增量黑段黑段增量白段白段增量黑段黑段增量 * * n W1 n W1 W1 B1 W1 B1 B1 Wm B1 Wm Wm Bm Wm Bm BmBm 其中其中n2n2(否则不当作斜线,而用原黑白段法压(否则不当作斜线,而用原黑白段法压缩),增量数值可正可负。缩),增量数值可正可负。57中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 图3-20 文字的黑
71、白段和线性增量图中n行中第一行是不考虑增量值的黑、白段信息,最后一行为加上相应增量的信息,其余n2行可按斜率为(增量/ n1)的斜线去补齐。58中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 字体字体试试验验字字数数随机抽随机抽样样字数范字数范围围黑白段信息压缩方法黑白段信息压缩方法线性增量压缩方法线性增量压缩方法增量压缩增量压缩法比黑白法比黑白段压缩法段压缩法提高压缩提高压缩倍数倍数压缩信息平压缩信息平均长度(字均长度(字节)节)对原始信息对原始信息平均压缩倍平均压缩倍数数压缩信息平压缩信息平均长度(字均长度(字节)节)对原始信息对原始信息平均压缩倍平均压缩倍
72、数数仿宋仿宋1001006912691211764.3511764.3520.2820.281400.231400.23170.05170.058.458.45宋体宋体50502002009905.539905.5324.0824.08975.77975.77244.01244.0110.210.2黑体黑体505035035010083.0510083.0523.6523.651468.291468.29162.17162.176.916.91楷体楷体50506006008558.438558.4327.8627.861050.131050.13226.73226.738.198.19平均平均
73、505010077.8410077.8423.9723.971223.611223.61200.74200.748.448.44表3-15 线性增量压缩方法和黑白段压缩方法对照表59中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 线性增量压缩方法小结 若以若以9696磅(磅(33.633.6毫米)宋、仿宋、黑、楷四种体,每种体毫米)宋、仿宋、黑、楷四种体,每种体70007000汉字的规模建立汉字存储器,采用黑白段压缩信息需汉字的规模建立汉字存储器,采用黑白段压缩信息需占占282.2282.2兆字节容量,而对同等规模的采用线性增量法的兆字节容量,而对同等规模的采用
74、线性增量法的汉字存储器,仅需占用汉字存储器,仅需占用34.334.3兆字节,压缩兆字节,压缩8 8倍多。倍多。 由于该方法保留了黑白段法黑白段描述的格式,所以,仍由于该方法保留了黑白段法黑白段描述的格式,所以,仍能用数字化仪自动生成。在用原来的黑白段法生成一个汉能用数字化仪自动生成。在用原来的黑白段法生成一个汉字信息的(包括操位时间)的全过程中,仅需增加字信息的(包括操位时间)的全过程中,仅需增加“ “增量增量压缩信息生成程序压缩信息生成程序” ”的的1212秒处理时间。秒处理时间。 使用线性增量法增加的斜线压缩格式,复原也比较容易。使用线性增量法增加的斜线压缩格式,复原也比较容易。该压缩方法
75、已在中国印刷技术研究所激光照排中心实现。该压缩方法已在中国印刷技术研究所激光照排中心实现。60中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 本章总结 在本章中分别介绍了通用型汉字字形压缩与还原的方法,如笔画在本章中分别介绍了通用型汉字字形压缩与还原的方法,如笔画矢量存储方法、子信息块哈夫曼树存储方法、部件组字压缩、汉矢量存储方法、子信息块哈夫曼树存储方法、部件组字压缩、汉字字形轮廓存储方法。字字形轮廓存储方法。 笔画矢量存储方法、汉字字形轮廓存储方法在字形边倍能力上比笔画矢量存储方法、汉字字形轮廓存储方法在字形边倍能力上比较好,因此在较好,因此在AutoCAD
76、AutoCAD等汉字支撑环境中有很高实用价值。部件组等汉字支撑环境中有很高实用价值。部件组字压缩提供了一种压缩率很高的用于通用性字形存储的方法,其字压缩提供了一种压缩率很高的用于通用性字形存储的方法,其字形变倍能力也不错。这四种方法均存在不同程度的字形失真现字形变倍能力也不错。这四种方法均存在不同程度的字形失真现象。象。 子信息块哈夫曼树存储方法是以上各种方法中唯一不失真的压缩子信息块哈夫曼树存储方法是以上各种方法中唯一不失真的压缩存储方法,但其算法复杂,压缩率和字形复原速率等指标相对较存储方法,但其算法复杂,压缩率和字形复原速率等指标相对较差(由于哈夫曼树存储方法的不失真特点,在差(由于哈夫
77、曼树存储方法的不失真特点,在UNIXUNIX系统中也有类系统中也有类似的采用哈夫曼树方法压缩文件系统的软件工具)。似的采用哈夫曼树方法压缩文件系统的软件工具)。 黑白段与线性增量存储方法、笔画轮廓压缩存储方法是目前精密黑白段与线性增量存储方法、笔画轮廓压缩存储方法是目前精密型汉字字形压缩的几种主要方法,特别是笔画轮廓压缩存储方法型汉字字形压缩的几种主要方法,特别是笔画轮廓压缩存储方法和线性增量存储方法,都具有很高的压缩率,比较适合存储用于和线性增量存储方法,都具有很高的压缩率,比较适合存储用于制版印刷领域的高密度汉字,在字形还原质量上笔画轮廓压缩方制版印刷领域的高密度汉字,在字形还原质量上笔画轮廓压缩方法有着更好的解决方法,字形失真率很低。法有着更好的解决方法,字形失真率很低。61中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 下课了。追求追求休息一会儿。休息一会儿。62中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 部分资料从网络收集整理而来,供大家参考,感谢您的关注!