CN102376099B - 一种改善矢量图形填充效果的方法及系统 - Google Patents

Abstract

本发明属于图形、图像和文字处理技术领域，具体公开了一种改善矢量图形填充效果的方法，其包括下述步骤：1)基于扫描线而检测所述矢量图形中是否存在待弥补区域；2)基于丢点笔划表而判断所存在的待弥补区域是否为交点凹陷，并对确认为交点凹陷的待弥补区域进行填充。此外，本发明还提供一种改善矢量图形填充效果的系统。本发明提供的系统和方法能够消除因交点凹陷而带来的各种图形畸变，从而大大改善低分辨率下的诸如矢量字形的矢量图形的填充效果，并使文字/图形的可辨识度得到提升。

Description

一种改善矢量图形填充效果的方法及系统

技术领域

本发明涉及图形、图像和文字处理技术，具体而言，涉及一种改善矢量图形填充效果的方法及系统；更具体地，涉及一种基于中心覆盖规则的矢量图形填充效果的改善方法及系统。

背景技术

矢量图形是印前领域中大量使用的一种页面描述对象，由于它具有在坐标变换下的高度保真性，因而可以较为精确地还原出描述者的本来意图。文字是印前领域中大量使用的另一种页面描述对象，主要分为两类：点阵字形和矢量字形，其中，矢量字形应用更为广泛，而其内部描述数据也是基于矢量图形的，因此，矢量图形的光栅化是整个印前输出系统的核心部件。矢量图形光栅化的主要工作是将用户坐标空间下的矢量描述数据转换为设备坐标空间下的点阵信息，其中最重要及最关键的一步，是对组成矢量图形对象的每一个路径按照一定的规则进行填充，得到相应的内部像素点阵描述信息。

通常，一个路径由一个或多个子路径构成，一个子路径由一组首尾互相连接的直线矢量或曲线矢量构成，子路径所形成的轮廓是封闭的。对于单个的不自交的子路径，全部区域被其剖分而成的内部和外部十分明确，填充区域(即子路径所围的内部区域)一目了然；但对其他情形，则由于子路径本身可能存在自交，子路径与子路径之间也可能存在包含或相交的关系，内部与外部不再显而易见，因此必须考虑填充的缠绕规则，以便在子路径发生包含或相交的情况时据之确定填充区域。对于全部区域上的任意一点，以之为起点任意作一条通往无限远处的射线，该点有一个初始值为0的缠绕数，当路径中的某一子路径从左向右穿越该射线时，缠绕数加1，当路径中的某一子路径从右向左穿越该射线时，缠绕数减1，当按射线方向顺次计算完该路径与该射线所有的穿越情况之后，即得到该点最终的缠绕数，为此，可以定义两种缠绕规则：非零规则和奇偶规则。非零规则就是将那些缠绕数不等于0的点定义为内部点，其组成的区域为填充区域。奇偶规则则是将那些缠绕数为奇数的点定义为内部点，其组成的区域为填充区域。对于简单的路径，这两种缠绕规则定义的填充区域是相同的，填充结果自然也完全一样。但对于复杂的路径，这两种缠绕规则定义的填充区域就会产生差别，填充结果也会不一样。例如，有两个路径，分别构成五角星和圆环的形状，用非零规则填充的结果如图1所示，用奇偶规则填充的结果如图2所示。两种规则各有其方便适宜的应用领域，一种完善的矢量图形的填充方法需要正确处理这两种缠绕规则，而对于矢量字形来说，因其轮廓描述相对较为规范，故一般都使用非零规则来进行填充。

对一个路径进行填充的过程，可视为将该路径所围成的封闭区域内部的设备空间上的像素进行涂黑的过程。当一个像素完全落在填充区域内部时，毫无疑问该像素应当被涂黑；当一个像素完全落在填充区域外部时，毫无疑问该像素不应当被涂黑；当一个像素一部分落在填充区域内部、一部分落在填充区域外部时，该像素是否应当被涂黑则是一个需要仔细考虑的问题，不同的像素涂黑规则可能会产生不同的填充结果，从而直接影响到最终的视图效果。对于较大尺寸的路径或者较高分辨率的情况，设备空间上的像素相对较多，路径的各个细节部分都包含了足够多的像素，因而无论采取何种像素涂黑规则，都能够得到满意的填充结果。在高分辨率下填充矢量字形“$”的路径，结果如图3所示。一种常见的像素涂黑规则是“任意相交”规则，即只要一个像素的任意部分与填充区域内部相交就涂黑该像素，亦即当一个像素一部分落在填充区域内部、一部分落在填充区域外部时，则涂黑该像素。采用任意相交的像素涂黑规则，可以保证不会出现丢点的现象，其实现也相对容易，然而，对于较小尺寸的路径或者较低分辨率的情况，设备空间上的像素相对较少，完全落在路径所围成的封闭区域内部的像素也相对减少，而部分落在路径所围成的封闭区域内部的像素则相对增多，此时采用任意相交的像素涂黑规则就会使得众多这样的路径边缘像素被涂黑，从而导致填充结果中细节大量丢失，图形畸变严重，特别地，基于矢量图形描述的小文字的填充结果会出现大量笔划粘连，变得难以辨识。在低分辨率下用任意相交的像素涂黑规则填充矢量字形“$”的路径，结果如图4所示。

为此，另一种像素涂黑规则应运而生，这就是“中心覆盖”规则，即只涂黑那些中心点被填充区域内部覆盖的像素，亦即当且仅当一个像素的中心点落在填充区域内部时，涂黑该像素。采用中心覆盖的像素涂黑规则可以有效地解决上述低分辨率下填充结果出现大量像素粘连、细节丢失、严重畸变从而导致可辨识性大大降低的问题。在低分辨率下用中心覆盖的像素涂黑规则填充矢量字形“$”的路径，结果如图5所示。

然而，单纯采用中心覆盖规则，也会产生新的问题，那就是当路径中存在较细小的区域时，这些区域有可能会因为无法覆盖到任何像素中心而被丢失，由此将导致填充结果中出现丢点、断线甚至丢线等情况，特别地，基于矢量图形描述的小文字的填充结果会出现笔划的局部或整体性缺失，从而大大降低了文字的可辨识性。在低分辨率下单纯用中心覆盖的像素涂黑规则填充较细字体的矢量字形“$”的路径，结果如图6所示。

因此，如何恰当地避免丢点是基于中心覆盖规则的矢量图形填充方法面临的一大难题，而对于要求具有较高可辨识性的矢量字形来说这一难题更为突出。在现有技术中，一种对策是利用反走样机制即灰度填充的方式，对丢点在一定程度上进行弥补，但这种弥补只能是相对的，效果十分有限，当丢点所对应的填充区域小到一定程度时，反走样就无法对其进行弥补了，并且，灰度填充又会引入填充不实、平直轮廓边缘发虚等新问题，其实际效果也无法令人满意。另一种对策是专门针对矢量字形的中心覆盖填充方法的，即在其内部增加对丢点的弥补机制：当出现路径中的轮廓矢量在竖直或水平方向上以两个相反方向穿越某相邻两像素中心之间的水平或竖直连线并且这两个像素中心都未被路径的填充区域覆盖时，即认为发生了竖直或水平方向上的丢点，需要对这两个像素之一进行涂黑以弥补丢点，采用该对策可以有效地防止矢量字形在进行中心覆盖填充时出现丢点，然而对弥补丢点所涂黑像素的选择策略却将大大影响字形最终的填充效果，从而直接关系到文字的可辨识性。一种简单直观的丢点弥补像素选择策略是左下丢点弥补，即在中心覆盖填充的过程中，当检测出水平方向上有丢点发生时，涂黑水平相邻两个像素中的左边那个像素，当检测出竖直方向上有丢点发生时，涂黑竖直相邻两个像素中的下边那个像素。在低分辨率下用中心覆盖加左下丢点弥补的像素涂黑规则填充较细字体的矢量字形“$”的路径，结果如图7所示，其中按照左下丢点弥补规则增加的像素在图中用深色上对角线(即左下-右上对角线)表示。这一策略对于普通的矢量字形通常可以得到尚能接受的效果，但是在某些情况下，其效果则不够令人满意，即使对左下丢点弥补策略加以优化(例如，可以算出丢点位置中心与相邻两个像素中心的距离，对离丢点位置更近的一个像素进行涂黑来弥补丢点)，也无法避免畸变产生，因而得到很差的效果。一种常见的典型情况，出现在两个笔划垂直相交时，有且仅有其中一个笔划落入丢点区域，此时按照上面所述的填充规则，就可能会出现“交点凹陷”的现象。例如，采用左下丢点弥补策略，则当竖直笔划落入丢点区域时，会出现与水平笔划左端的交点向右凹陷的现象，而当水平笔划落入丢点区域时，会出现与竖直笔划下端的交点向上凹陷的现象；且无论采用何种其他的丢点弥补策略，这一交点凹陷的现象都无法避免。在低分辨率下用中心覆盖加左下丢点弥补的像素涂黑规则填充宋体的矢量字形“上”的路径，结果如图8所示，其中按照左下丢点弥补规则增加的像素在图中用深色上对角线(即左下-右上对角线)表示。

由于两个笔划垂直相交的情况在汉字中出现得相当频繁(此情况在日语的假名、朝-韩语的谚文等其他受汉字影响发明的方块文字中同样存在)，以宋体(在日语中称为明体或明朝体)为代表的一系列字体又是中文排版中最常用的正文字体，而宋体字家族的一大特征是横平竖直且横笔划较细，这就导致在字号不是很大的情况下(包括许多较常用的正文或标题字号)，这些较细的笔划很容易落入丢点区域，于是用中心覆盖填充规则对这样的矢量字形进行填充时便经常会出现上面描述的“交点凹陷”现象，例如，像一些很常用的汉字，用并不算小的宋体来显示，都会出现“交点凹陷”现象：在低分辨率下用中心覆盖加左下丢点弥补的像素涂黑规则填充宋体的矢量字形“山”、“田”、“里”、“正”的路径，结果分别如图9、图10、图11、图12所示，其中按照左下丢点弥补规则增加的像素在图中用深色上对角线(即左下-右上对角线)表示；而对于一些笔划稍多的汉字，其填充效果则更是不尽人意：在低分辨率下用中心覆盖加左下丢点弥补的像素涂黑规则填充宋体的矢量字形“奰”的路径，结果如图13所示，其中按照左下丢点弥补规则增加的像素在图中用深色上对角线(即左下-右上对角线)表示，此字共有多达6处的“交点凹陷”。

由此可见，采用常用的中心覆盖加左下丢点弥补的像素涂黑规则填充矢量图形(例如，矢量字形)时，难以避免上述交点凹陷的产生，这样，不仅使得上述矢量图形的填充效果(特别是在低分辨率下的矢量图形填充效果)较差，而且也使得这样填充的矢量图形的可辨识度较低。为此，本领域的技术人员一直试图寻找到一种有效手段来避免或克服上述矢量图形填充中的交点凹陷问题。然而迄今为止，针对上述问题的有效解决方案仍未出现。

发明内容

为解决上述技术问题，本发明提供了一种改善矢量图形填充效果的方法及系统，其能够有效避免矢量图形填充过程中的交点凹陷问题，进而使得被填充的矢量图形具有较好的填充效果和较高的可辨识度。

为此，本发明提供了一种改善矢量图形填充效果的方法，其包括下述步骤：1)基于扫描线而检测所述矢量图形中是否存在待弥补区域；2)基于丢点笔划表而判断所存在的待弥补区域是否为交点凹陷，并对确认为交点凹陷的待弥补区域进行填充；

其中，所述丢点笔划表为表示待弥补区域相关信息的动态表，其中的每一条记录均对应于一个所述已检测出的待弥补区域，并且每一条记录均包括相应待弥补区域的纵坐标、左横坐标、右横坐标、非丢点标志和丢点标志五个表项；

其中，在所述步骤2)中，采用下述规则判断每一条扫描线所对应的矢量图形部分中的待弥补区域是否为交点凹陷：若所述待弥补区域为非丢点待弥补区域并且当前丢点笔划表中存在这样的记录：即，所述待弥补区域下端点的纵坐标向下取整得到的纵坐标值与该记录的纵坐标相同且所述待弥补区域的横坐标比该记录中的右横坐标大一，则判定所述待弥补区域为交点凹陷。

其中，在所述步骤2)中，基于每一条扫描线而判断出相应待弥补区域为交点凹陷后，即对该待弥补区域进行填充。

其中，在所述步骤2)之前或之后还包括这样的步骤：即，若判断出所述待弥补区域为丢点待弥补区域，则采用丢点弥补机制对其填充。

其中，每一条所述扫描线为同一横坐标上的像素的中心的连线，所述扫描线的扫描顺序为自左向右逐一扫描，或自右向左逐一扫描。或者，每一条所述扫描线为同一纵坐标上的像素的中心的连线，所述扫描线的扫描顺序为自下向上逐一扫描，或自上向下逐一扫描。

作为另一个技术方案，本发明还提供一种改善矢量图形填充效果的系统，其包括：待弥补区域检测单元，用以检测扫描线所经过的矢量图形部分是否存在待弥补区域；丢点笔划表管理单元，用以根据所检测到的待弥补区域而动态地建立和维护丢点笔划表；交点凹陷判别单元，用以基于丢点笔划表来判断所存在的待弥补区域是否为交点凹陷，并在判断出该待弥补区域为交点凹陷后，向交点凹陷弥补单元发送弥补指令；以及交点凹陷弥补单元，用以根据所述弥补指令而对已确认为交点凹陷的待弥补区域进行填充；

所述丢点笔划表为表示待弥补区域相关信息的动态表，其中的每一条记录均对应于一个所述已检测出的待弥补区域，并且每一条记录均包括相应待弥补区域的纵坐标、左横坐标、右横坐标、非丢点标志和丢点标志五个表项；

其中，所述交点凹陷判别单元采用下述规则判断每一条扫描线所对应的矢量图形部分中的待弥补区域是否为交点凹陷：若所述待弥补区域为非丢点待弥补区域并且当前丢点笔划表中存在这样的记录：即，所述待弥补区域下端点的纵坐标向下取整得到的纵坐标值与该记录的纵坐标相同且所述待弥补区域的横坐标比该记录中的右横坐标大一，则判定所述待弥补区域为交点凹陷。

其中，所述交点凹陷判别单元基于每一条扫描线，判断相应待弥补区域是否为交点凹陷，并在判断出该待弥补区域为交点凹陷后，向交点凹陷弥补单元发送弥补指令。

相对于现有技术，本发明具有下述有益效果：

本发明提供的方法/系统是基于中心覆盖规则的矢量字形填充效果的改善方法/系统，其在对诸如矢量字形的矢量图形路径进行中心覆盖填充的过程中动态建立和维护丢点笔划表，并利用精致与简洁的算法和数据结构，快速而高效地记录和判断出路径中可能出现的各种交点凹陷区域，并对其进行弥补，以使笔划相交处的凹陷区域得到复原，从而消除因凹陷区域所带来的矢量图形中的各种畸变，进而大大改善矢量图形路径的填充效果(特别是在低分辨率下的矢量图形填充效果)，并使矢量图形的可辨识度得到一定程度的提升。

附图说明

图1是五角星和圆环状路径用现有非零规则填充的结果示意图；

图2是五角星和圆环状路径用现有奇偶规则填充的结果示意图；

图3是现有技术中在高分辨率下对某一字体的矢量字形“$”的路径进行填充的结果示意图；

图4是在低分辨率下对同一字体的矢量字形“$”的路径用任意相交的像素涂黑规则进行填充的结果示意图；

图5是在低分辨率下对同一字体的矢量字形“$”的路径用中心覆盖的像素涂黑规则进行填充的结果示意图；

图6是在低分辨率下对另一较细字体的矢量字形“$”的路径单纯用中心覆盖的像素涂黑规则进行填充的结果示意图；

图7是在低分辨率下对另一较细字体的矢量字形“$”的路径用中心覆盖加左下丢点弥补的像素涂黑规则进行填充的结果示意图；

图8是在低分辨率下对宋体的矢量字形“上”的路径用中心覆盖加左下丢点弥补的像素涂黑规则进行填充的结果示意图；

图9是在低分辨率下对宋体的矢量字形“山”的路径用中心覆盖加左下丢点弥补的像素涂黑规则进行填充的结果示意图；

图10是在低分辨率下对宋体的矢量字形“田”的路径用中心覆盖加左下丢点弥补的像素涂黑规则进行填充的结果示意图；

图11是在低分辨率下对宋体的矢量字形“里”的路径用中心覆盖加左下丢点弥补的像素涂黑规则进行填充的结果示意图；

图12是在低分辨率下对宋体的矢量字形“正”的路径用中心覆盖加左下丢点弥补的像素涂黑规则进行填充的结果示意图；

图13是在低分辨率下对宋体的矢量字形“奰”的路径用中心覆盖加左下丢点弥补的像素涂黑规则进行填充的结果示意图；

图14是本发明提供的改善矢量图形填充效果的方法的流程示意图；

图15A和图15B是本发明一个具体实施例提供的改善矢量图形填充效果的方法的流程示意图；

图16是在低分辨率下对某字体的矢量字形“圭”的路径用中心覆盖加左下丢点弥补再加本发明提出的交点凹陷弥补的像素涂黑规则进行填充的效果示意图；

图17是在低分辨率下对宋体的矢量字形“上”的路径用中心覆盖加左下丢点弥补再加本发明提出的交点凹陷弥补的像素涂黑规则进行填充的效果示意图；

图18是在低分辨率下对宋体的矢量字形“山”的路径用中心覆盖加左下丢点弥补再加本发明提出的交点凹陷弥补的像素涂黑规则进行填充的效果示意图；

图19是在低分辨率下对宋体的矢量字形“田”的路径用中心覆盖加左下丢点弥补再加本发明提出的交点凹陷弥补的像素涂黑规则进行填充的效果示意图；

图20是在低分辨率下对宋体的矢量字形“里”的路径用中心覆盖加左下丢点弥补再加本发明提出的交点凹陷弥补的像素涂黑规则进行填充的效果示意图；

图21是在低分辨率下对宋体的矢量字形“正”的路径用中心覆盖加左下丢点弥补再加本发明提出的交点凹陷弥补的像素涂黑规则进行填充的效果示意图；以及

图22是在低分辨率下对宋体的矢量字形“奰”的路径用中心覆盖加左下丢点弥补再加本发明提出的交点凹陷弥补的像素涂黑规则进行填充的效果示意图。

具体实施方式

为了使本技术领域的人员更好地理解本发明的技术方案，下面结合实施例和附图对本发明提供的改善矢量图形填充效果的方法及系统进行详细描述。

首先，需要说明的是，本文中为叙述方便起见，将处理顺序定义为从左到右、从下到上；将扫描线的方向定义为竖直方向，该方向上的坐标称为纵坐标，另一垂直方向上的坐标称为横坐标。当然可以理解是，在实际应用中不必拘泥于上述处理顺序、扫描线的方向以及坐标命名。

请参阅图14，本发明提供的改善矢量图形填充效果的方法具体包括下述步骤：

110)基于扫描线而检测所述矢量图形中是否存在待弥补区域。

在实际应用中，每一条所述扫描线为同一横坐标上的像素的中心的连线，所述扫描线的扫描顺序可以为自左向右逐一扫描，或者自右向左逐一扫描。类似地，每一条所述扫描线为同一纵坐标上的像素的中心的连线，所述扫描线的扫描顺序可以为自下向上逐一扫描，或者自上向下逐一扫描。

120)基于“丢点笔划表”而判断所存在的待弥补区域是否为交点凹陷，并对确认为交点凹陷的待弥补区域进行填充。

所述“丢点笔划表”为表示待弥补区域相关信息的动态表，其中的每一条记录均对应于一个所述已检测出的待弥补区域。并且，每一条记录均包括相应待弥补区域的纵坐标、左横坐标、右横坐标、非丢点标志和丢点标志五个表项，并分别用符号r、s、t、u和v来表示。这样，“丢点笔划表”中的每一条记录即表示为上述五元组(r，s，t，u，v)。对于前面三个坐标表项而言，坐标值分为未定义值和有定义值两类，其中，未定义值由(-1)来表示，有定义值则由向下取整到像素中心的整数值来表示。对于后面两个标志表项而言，取值为1时，表示为“真”；取值为0时，表示为“假”。为表述方便，在下文中以像素(即，纵坐标，横坐标)表示待弥补区域。

在实际应用中可以采用这样的规则来判断每一条扫描线所对应的矢量图形部分中的待弥补区域是否为交点凹陷：若所述待弥补区域为非丢点待弥补区域并且当前丢点笔划表中存在这样的记录：即，所述待弥补区域下端点的纵坐标向下取整得到的纵坐标值与该记录的纵坐标相同且所述待弥补区域的横坐标比该记录中的右横坐标大一，则判定所述待弥补区域为交点凹陷。并且，在判断出相应待弥补区域为交点凹陷后，随即对该待弥补区域进行填充。

而且，在步骤120)之前或者之后，若判断出待弥补区域为丢点时，则启动丢点弥补机制将其涂黑。

130)重复所述步骤110)至步骤120)，直至已基于全部扫描线而完成对矢量图形的检测。具体地，判断本扫描线是否为最后一条扫描线，若否，则启用下一条扫描线，并转到步骤110)；若是，则说明全部扫描线均对所述矢量图形进行了扫描，并结束上述矢量图形填充操作。

下面结合图15A和图15B详细说明本发明提供的改善矢量图形填充效果的方法的一个具体实施例。如图所示，本实施例中提供的改善矢量图形填充效果的方法主要包括下述步骤100至步骤300，其中，步骤200至步骤239对应于图14中的步骤2，也就是说，步骤200至步骤239详细说明了如何根据“丢点笔划表”来判断所存在的待弥补区域是否为交点凹陷，并对确认为交点凹陷的待弥补区域进行填充。

100)基于扫描线而检测所述矢量图形中是否存在待弥补区域。在本实施例中，所述扫描线为前述的竖直扫描线，并且扫描顺序为自左向右。至于如何判断是否存在待弥补区域，例如可以采用现有的方法，在此不再赘述。进行检测，判断待弥补区域是否为丢点

200)根据中心覆盖填充中丢点发生的条件来判断所述待弥补区域是否为丢点待弥补区域，若是，则转到步骤210)；若否，则转到步骤230)。其中，所述丢点判断规则例如可以采用现有技术中的丢点判断规则：当发现待弥补区域位于相邻两个像素中心之间时，则判定发生了丢点，也就是说，该待弥补区域为丢点待弥补区域。

210)继续判断当前丢点笔划表中是否存在这样的记录：即，所述待弥补区域的纵坐标向下取整而得到的纵坐标值与该记录中的纵坐标相同且所述待弥补区域的横坐标比该记录中的右横坐标大一(即，所述待弥补区域为当前该记录所表示的区域右侧的第一个像素)，若是，则转到步骤211)；若否，则转到步骤214)。

211)继续判断该记录中的非丢点标志是否为“真”，若是，则判定存在交点凹陷，所述交点凹陷区域的纵坐标为该记录中的纵坐标，所述交点凹陷区域的横坐标介于该记录中的左横坐标至右横坐标之间，而后转到步骤212)；若否，则转到步骤213)。

212)对所述交点凹陷区域进行填充，并将该记录中的非丢点标志设置为“假”、左横坐标设置为未定义。

213)将该记录的右横坐标更新为本横坐标，并将该记录的丢点标志设置为“真”。所谓本横坐标，指的是当前扫描线所对应的横坐标值。

214)判断所述待弥补区域的纵坐标向下取整所得到的纵坐标值是否大于等于当前丢点笔划表所含记录中的纵坐标，若是，则转到步骤216)；若否，则说明当前丢点笔划表中没有与所述待弥补区域相对应的记录，并且转到步骤215)。

215)在当前丢点笔划表中新增一条记录，并设置该新记录中的纵坐标为所述待弥补区域的纵坐标、右横坐标为本横坐标、非丢点标志为“假”、丢点标志为“真”，而后转到步骤300)。

216)判断该记录中的丢点标志和非丢点标志是否均为“真”，若是，则判定存在交点凹陷，所述交点凹陷区域的纵坐标为该记录中的纵坐标，所述交点凹陷区域的横坐标介于该记录中的左横坐标至右横坐标之间，而后转到步骤217)；若否，则转到步骤218)。

217)对所述交点凹陷区域进行填充，并将该记录从当前丢点笔划表中删除，而后转到步骤300)。

218)判断所述待弥补区域的横坐标是否比该记录中的右横坐标大一以上(例如，如果大2，则表示所述待弥补区域为当前该记录所表示的区域右侧的第2个像素)，若是，则将该记录从当前丢点笔划表中删除，而后转到步骤300)。

230)根据丢点判断规则而判断出所述待弥补区域为非丢点待弥补区域后，继续判断当前丢点笔划表中是否存在这样的记录：即，该待弥补区域下端点的纵坐标向下取整所得到的纵坐标值与该记录的纵坐标相同且该待弥补区域的横坐标比该记录中的右横坐标大一，若是，则转到步骤231)；若否，则转到步骤234)。

231)判断该记录中的非丢点标志是否为“假”，若是，则转到步骤232)；若否，则直接转到步骤233)。

232)将该记录中的非丢点标志设置为“真”，并将左横坐标设置为本横坐标。

233)将该记录中的右横坐标更新为本横坐标，而后转到步骤300)。

234)判断该待弥补区域的纵坐标向下取整是否大于等于当前丢点笔划表所含记录中的纵坐标，若是，则转到步骤236)，若否，则转到步骤235)。

235)在当前丢点笔划表中新增一条记录，并设置该新记录中的纵坐标为该待弥补区域下端点的纵坐标、左横坐标和右横坐标均为本横坐标、非丢点标志为“真”、丢点标志为“假”，而后转到步骤300)。

236)判断该记录的丢点标志和非丢点标志是否都为“真”，若是，则判定存在交点凹陷，所述交点凹陷区域的纵坐标为该记录中的纵坐标，所述交点凹陷区域的横坐标介于该记录中的左横坐标到右横坐标之间，而后转到步骤237)；若否，则转到步骤239)。

237)对所述交点凹陷区域进行填充。

238)将该记录从当前丢点笔划表中删除，而后转到步骤300)。

239)判断该待弥补区域的横坐标是否比该记录中的右横坐标大一以上，若是，则将该记录从当前丢点笔划表中删除。

300)重复所述步骤100)至步骤239)，直至已基于全部扫描线而完成对矢量图形的检测和弥补。

需要指出的是，上述步骤200至步骤239详细说明了交点凹陷的判断及弥补，但是并未说明对于丢点的弥补，事实上，在实际应用中若判断出所述待弥补区域为丢点待弥补区域，可以立即采用丢点弥补机制对其填充。换言之，在上述步骤200至步骤239中，可以采用这样的方式来填充待弥补区域：即，一旦判断出待弥补区域为丢点待弥补区域，则填充该丢点待弥补区域；一旦判断出待弥补区域为非丢点待弥补区域，则填充该非丢点待弥补区域，也就是说，对于矢量图形中的丢点和非丢点边进行判断边进行填充弥补。当然，也可以采用这样的方式：即，判断出整个矢量图形中的全部丢点待弥补区域和全部非丢点待弥补区域之后，对这些待弥补区域一并进行填充弥补。当然，还可以采用前面结合图14所说明的方式：即，对应于每一条扫描线，当判断出待弥补区域为丢点像素或非丢点像素(而非由连续的多个像素所形成的区域)时，立即对该像素进行填充弥补，只是这样的方式不如前述填充方式的效率高。

而且，上述交点凹陷的处理与中心覆盖填充中对丢点的弥补可以同时进行，即，在全部扫描线完成一次扫描后，被扫描矢量图形中的全部丢点和交点凹陷即已全部被弥补填充完毕。当然，上述交点凹陷的处理与中心覆盖填充中对丢点的弥补也可以不同时进行，只是该方式在效率上逊于前者。

进一步需要指出的是，在对交点凹陷区域进行填充弥补时，可以先判断待弥补的交点凹陷区域的像素是否已被涂黑，也就是说，在此仅仅涂黑那些尚未被涂黑的像素即可。并且，前述交点凹陷和丢点的弥补处理可以与基于中心覆盖原则而进行的填充涂黑阶段一同完成。

下面以某字体的矢量字形“圭”为例，对本发明提供的改善矢量图形填充效果的方法作进一步阐述。

在某字号及某分辨率的设置下，该矢量字形将在16×16的像素点阵中进行填充，按照中心覆盖基本规则填充结果的像素在图中用25％灰色表示，按照左下丢点弥补规则增加的像素在图中用深色上对角线(即左下-右上对角线)表示，而按照本发明提出的交点凹陷弥补方法增加的像素在图中用深色下对角线(即左上-右下对角线)表示。

以下依次描述竖直扫描线0到f中每一条扫描线的处理过程，并且在下面描述中所涉及的各像素点坐标表示为(横坐标，纵坐标)。

0)以竖直扫描线0进行检测，并确定本扫描线对应的两个待弥补区域，即像素(0，0)和像素(0，8)，都是丢点。根据前述步骤200至步骤218，判断出当前的“丢点笔划表”中不存在满足步骤210所述条件的记录，即，当前“丢点笔划表”中不存在该待弥补区域相对应的记录，因此，根据步骤215，而在“丢点笔划表”中当前位置新增两条与上述两个像素相对应的记录，在所述记录中，将纵坐标项设置为该丢点的纵坐标，左横坐标项为未定义值并表示为(-1)，将右横坐标项设置为本扫描线的横坐标，将非丢点标志项设置为“假”，将丢点标志项设置为“真”，于是，对应于上述两个丢点而新增的两条记录即为(0，-1，0，0，1)和(8，-1，0，0，1)。

1)以竖直扫描线1进行检测，并确定本扫描线对应的两个待弥补区域，即像素(1，0)和像素(1，8)，都是丢点。根据前述步骤200至步骤218，这两个丢点满足步骤210但不满足步骤211，因此转到步骤213，并将“丢点笔划表”中的两条记录的右横坐标项设置为本扫描线1的横坐标，将非丢点标志项设置为“假”，将丢点标志项设置为“真”，于是，当前的“丢点笔划表”中的两条记录即更新为(0，-1，1，0，1)和(8，-1，1，0，1)。

2)以竖直扫描线2进行检测，并确定本扫描线对应的四个待弥补区域中，第一个涂黑区域(2，0)是丢点，于是采用类似于扫描线1的处理方式而将“丢点笔划表”中的记录(0，-1，1，0，1)更新为(0，-1，2，0，1)；第二个涂黑区域(2，4)也是丢点，采用类似于扫描线0的处理方式而在“丢点笔划表”中新增一条与之对应的记录(4，-1，2，0，1)；第三个涂黑区域(2，8)也是丢点，采用类似于扫描线1的处理方式而将“丢点笔划表”中的记录(8，-1，1，0，1)更新为(8，-1，2，0，1)；第四个涂黑区域(2，c)不是丢点，于是转到步骤235，并在“丢点笔划表”中新增一条与之对应的记录(c，-1，2，1，0)。

3)以竖直扫描线3进行检测，并确定本扫描线对应的四个待弥补区域中，前三个待弥补区域(3，0)、(3，4)和(3，8)都是丢点，且它们的纵坐标均不是新增的，于是采用类似于扫描线1的处理方式，并对应于这三个待弥补区域而将“丢点笔划表”中的记录(0，-1，2，0，1)、(4，-1，2，0，1)和(8，-1，2，0，1)分别更新为(0，-1，3，0，1)、(4，-1，3，0，1)和(8，-1，3，0，1)；第四个待弥补区域(3，c)不是丢点，并且满足步骤230的条件却不满足步骤231的条件，于是转到步骤233，并将“丢点笔划表”中的已有记录(c，-1，2，1，0)”更新为(c，-1，3，1，0)。

4～6)扫描线4、5、6的处理与扫描线3完全类似，经过扫描线的三次变更后(扫描线3变更为扫描线4、扫描线4变更为扫描线5、扫描线5变更为扫描线6)，“丢点笔划表”中原有4条记录相应地更新为(0，-1，6，0，1)、(4，-1，6，0，1)、(8，-1，6，0，1)和(c，-1，6，1，0)。

7)以竖直扫描线7进行检测，并确定扫描线7对应的两个待弥补区域都不是丢点，并且都满足步骤230和步骤231的条件，于是执行步骤231至步骤233的操作，将“丢点笔划表”中相应的两条记录(0，-1，6，0，1)和(8，-1，6，0，1)分别更新为(0，7，7，1，1)和(8，7，7，1，1)。

8)以竖直扫描线8进行检测，并确定扫描线8对应的两个待弥补区域也都不是丢点，并且都满足步骤230的条件却不满足步骤231的条件，于是依照步骤233处理，将“丢点笔划表”中的原有记录(0，7，7，1，1)和(8，7，7，1，1)相应地更新为(0，7，8，1，1)和(8，7，8，1，1)；同时，依照步骤239处理，将“丢点笔划表”中的记录(4，-1，6，0，1)和(c，-1，6，1，0)从表中删除。

9)以竖直的扫描线9进行检测，并确定扫描线9对应四个待弥补区域，其中，第一个待弥补区域(9，0)是丢点，并且满足步骤210和步骤211的条件，此时需要进行交点凹陷的弥补，于是依照步骤212的处理，将尚未涂黑的交点凹陷区域——待弥补区域(0，7)到(0，8)进行涂黑，同时将“丢点笔划表”中的记录(0，7，8，1，1)更新为(0，-1，9，0，1)；第二个待弥补区域(9，4)也是丢点，根据步骤215的处理，在“丢点笔划表”中新增一条记录(4，-1，9，0，1)；第三个待弥补区域(9，8)也是丢点，并且满足步骤210和步骤211的条件，此时需要进行交点凹陷的弥补，于是依照步骤212处理，将尚未涂黑的交点凹陷区域——待弥补区域(8，7)到(8，8)进行涂黑，同时将“丢点笔划表”中的记录(8，7，8，1，1)更新为(8，-1，9，0，1)；第四个待弥补区域(9，c)不是丢点，于是依照步骤235的处理，往“丢点笔划表”中新增一条记录(c，-1，9，1，0)。

a)以竖直扫描线a进行检测，并确定扫描线a对应的四个待弥补区域中，前三个待弥补区域都是丢点，且不是它们的纵坐标均不是新增的，于是对应于这三个待弥补区域，并依照类似于扫描线9的处理方式而将“丢点笔划表”中的记录(0，-1，9，0，1)、(4，-1，9，0，1)和(8，-1，9，0，1)分别更新为(0，-1，a，0，1)、(4，-1，a，0，1)和(8，-1，a，0，1)；第四个待弥补区域(a，c)不是丢点，并且满足步骤230的条件却不满足步骤231的条件，于是依照步骤233处理，将“丢点笔划表”中的记录(c，-1，9，1，0)更新为(c，-1，a，1，0)。

b)以竖直扫描线b进行检测，并确定扫描线b的处理与扫描线a完全类似，因而采用类似于扫描线a所述的方式，将已根据扫描线a而更新得到的“丢点笔划表”中的四条记录相应地分别更新为(0，-1，b，0，1)、(4，-1，b，0，1)、(8，-1，b，0，1)和(c，-1，b，1，0)。

c)以竖直扫描线c进行检测，并确定扫描线c仍然对应四个待弥补区域，第一个待弥补区域(c，0)是丢点，依照类似于扫描线b的处理方式而将“丢点笔划表”中的记录(0，-1，b，0，1)更新为(0，-1，c，0，1)；第二个待弥补区域(c，4)不是丢点，并且满足步骤230和步骤231的条件，于是依照步骤231至步骤233处理，将“丢点笔划表”中的记录(4，-1，b，0，1)更新为(4，c，c，1，1)；第三个待弥补区域(c，8)是丢点，依照类似于扫描线b的处理方式而将“丢点笔划表”中的记录(8，-1，b，0，1)更新为(8，-1，c，0，1)；第四个待弥补区域(c，c)不是丢点，依照类似于扫描线b的处理方式而将“丢点笔划表”中的记录(c，-1，b，1，0)更新为(c，-1，c，1，0)。

d)以竖直扫描线d进行检测，并确定扫描线d仍然对应四个待弥补区域，其中第一个、第三个和第四个丢点的情形类似于扫描线c所对应的第一个、第三个和第四个丢点的情形类似，因而对于这三个丢点采用与扫描线c类似的处理方式，而将“丢点笔划表”中的三条对应记录分别更新为(0，-1，d，0，1)、(8，-1，d，0，1)和(c，-1，d，1，0)。至于第二个待弥补区域(d，4)，其不是丢点，并且满足步骤230的条件却不满足步骤231的条件，于是依照步骤233处理，将“丢点笔划表”中的对应记录(4，c，c，1，1)更新为(4，c，d，1，1)。

e)以竖直扫描线e进行检测，并确定扫描线e对应的两个待弥补区域都不是丢点，并且都满足步骤230和步骤231的条件，于是依照步骤231至步骤233的处理方式而将“丢点笔划表”中的对应记录(0，-1，d，0，1)和(8，-1，d，0，1)分别更新为(0，e，e，1，1)和(8，e，e，1，1)；同时，根据步骤236至步骤238，判断出“丢点笔划表”中的记录(4，c，d，1，1)所对应的尚未涂黑的交点凹陷区域需要进行弥补，并将该交点凹陷区域所对应的像素(4，c)到(4，d)进行涂黑，然后将该记录从表中删除；同时，依照步骤238的处理，将“丢点笔划表”中的记录(c，-1，d，1，0)从表中删除。

f)以竖直扫描线f进行检测，确定扫描线f对应的两个待弥补区域都是丢点，并且都满足步骤211的条件，此时需要进行交点凹陷的弥补，于是依照步骤212的处理，将尚未涂黑的交点凹陷区域——待弥补区域(0，e)和待弥补区域(8，e)进行涂黑，同时由于这是最后一个扫描线，遂将“丢点笔划表”中的相应记录都删除，“丢点笔划表”至此也就清空了。

经过上述0～f过程后，在低分辨率下对某字体的矢量字形“圭”的路径用中心覆盖加左下丢点弥补再加本发明提出的交点凹陷弥补的像素涂黑规则进行填充的结果即如图16所示。

请一并参阅图17至图22，对于前述图8至图13所示存在交点凹陷的矢量字形“上”、“山”、“田”、“里”、“正”和“奰”，在采用本发明提供的改善矢量图形填充效果的方法而分别对其进行交点凹陷弥补后，上述各矢量字形的填充效果分别如图17至22所示。至于这些矢量字形中交点凹陷的判别和填充方法及过程，类似于前面结合图16所作的说明，在此不再赘述。

由上可知，在本发明中，“丢点笔划表”的创建、维护与使用是弥补交点凹陷的关键，其算法与数据结构的实现非常精致高效，通过恰当的控制，可以方便地增加规则以改善交点凹陷弥补的质量。采用本发明的方法，能够在很大程度上消除由交点凹陷引起的各种字形笔划中的畸变，从而大大改善低分辨率下矢量字形路径的填充效果，并使文字的可辨识度得到有效的提升。

此外，本发明还提供一种改善矢量图形填充效果的系统，其包括：待弥补区域检测单元、丢点笔划表管理单元、交点凹陷判别单元和交点凹陷弥补单元。

其中，待弥补区域检测单元用以检测扫描线所经过的矢量图形部分是否存在待弥补区域。

丢点笔划表管理单元用以根据所检测到的待弥补区域而动态地建立和维护丢点笔划表。所述丢点笔划表为表示待弥补区域相关信息的动态表，其中的每一条记录均对应于一个所述已检测出的待弥补区域，并且每一条记录均包括相应待弥补区域的纵坐标、左横坐标、右横坐标、非丢点标志和丢点标志五个表项。在实际应用中，丢点笔划表管理单元建立丢点笔划表，并根据待弥补区域检测单元所检测到的每一待弥补区域而在该丢点笔划表中增添、变更或删除相关记录以动态维护该丢点笔划表。

交点凹陷判别单元用以基于丢点笔划表来判断所存在的待弥补区域是否为交点凹陷，并在判断出该待弥补区域为交点凹陷后，向交点凹陷弥补单元发送弥补指令。

交点凹陷弥补单元用以根据所述弥补指令而对已确认为交点凹陷的待弥补区域进行填充。

需要指出的是，在实际应用中，所述交点凹陷判别单元可以基于每一条扫描线，判断相应待弥补区域是否为交点凹陷，并在判断出该待弥补区域为交点凹陷后，向交点凹陷弥补单元发送弥补指令。判断每一条扫描线所对应的矢量图形部分中的待弥补区域是否为交点凹陷的规则可以为：若所述待弥补区域为非丢点待弥补区域并且当前丢点笔划表中存在这样的记录：即，所述待弥补区域下端点的纵坐标向下取整得到的纵坐标值与该记录的纵坐标相同且所述待弥补区域的横坐标比该记录中的右横坐标大一，则判定所述待弥补区域为交点凹陷。

进一步需要指出的是，前述各个单元的工作过程类似于前面结合本发明提供的改善矢量图形填充效果的方法所作的说明，在此不再赘述。并且，本发明中所说的矢量图形包括图形和字形等。

还需要指出的是，以上实施方式仅仅是为了说明本发明的原理而采用的示例性实施方式，然而本发明并不局限于此。对于本领域内的普通技术人员而言，在不脱离本发明的精神和实质的情况下，可以做出各种变型和改进，这些变型和改进也视为本发明的保护范围。

Claims (7)

1.一种改善矢量图形填充效果的方法，其特征在于，包括下述步骤：

1)基于扫描线而检测所述矢量图形中是否存在待弥补区域；

2)基于丢点笔划表而判断所存在的待弥补区域是否为交点凹陷，并对确认为交点凹陷的待弥补区域进行填充；其中，

所述丢点笔划表为表示待弥补区域相关信息的动态表，其中的每一条记录均对应于一个所述已检测出的待弥补区域，并且每一条记录均包括相应待弥补区域的纵坐标、左横坐标、右横坐标、非丢点标志和丢点标志五个表项；

在所述步骤2)中，采用下述规则判断每一条扫描线所对应的矢量图形部分中的待弥补区域是否为交点凹陷：

若所述待弥补区域为非丢点待弥补区域并且当前丢点笔划表中存在这样的记录：即，所述待弥补区域下端点的纵坐标向下取整得到的纵坐标值与该记录的纵坐标相同且所述待弥补区域的横坐标比该记录中的右横坐标大一，则判定所述待弥补区域为交点凹陷。

2.根据权利要求1所述的改善矢量图形填充效果的方法，其特征在于，在所述步骤2)中，基于每一条扫描线而判断出相应待弥补区域为交点凹陷后，即对该待弥补区域进行填充。

3.根据权利要求1所述的改善矢量图形填充效果的方法，其特征在于，所述步骤2)具体包括下述步骤：

200)判断所述待弥补区域是否为丢点待弥补区域，若是，则转到步骤210)；若否，则转到步骤230)；

210)判断当前丢点笔划表中是否存在这样的记录：即，所述待弥补区域的纵坐标向下取整而得到的纵坐标值与该记录中的纵坐标相同且所述待弥补区域的横坐标比该记录中的右横坐标大一，若是，则转到步骤211)；若否，则转到步骤214)；

211)判断该记录中的非丢点标志是否为“真”，若是，则判定存在交点凹陷，所述交点凹陷区域的纵坐标为该记录中的纵坐标，所述交点凹陷区域的横坐标介于该记录中的左横坐标至右横坐标之间，而后转到步骤212)；若否，则转到步骤213)；

212)对所述交点凹陷区域进行填充，并将该记录中的非丢点标志设置为“假”、左横坐标设置为未定义；

213)将该记录的右横坐标更新为本横坐标，并将该记录的丢点标志设置为“真”；

214)判断所述待弥补区域的纵坐标向下取整所得到的纵坐标值是否大于等于当前丢点笔划表所含记录中的纵坐标，若是，则转到步骤216)；若否，则转到步骤215)；

215)在当前丢点笔划表中新增一条记录，并设置该新记录中的纵坐标为所述待弥补区域的纵坐标、右横坐标为本横坐标、非丢点标志为“假”、丢点标志为“真”，而后转到步骤3)；

216)判断该记录中的丢点标志和非丢点标志是否均为“真”，若是，则判定存在交点凹陷，所述交点凹陷区域的纵坐标为该记录中的纵坐标，所述交点凹陷区域的横坐标介于该记录中的左横坐标至右横坐标之间，而后转到步骤217)；若否，则转到步骤218)；

217)对所述交点凹陷区域进行填充，并将该记录从当前丢点笔划表中删除，而后转到步骤3)；

218)判断所述待弥补区域的横坐标是否比该记录中的右横坐标大一以上，若是，则将该记录从当前丢点笔划表中删除，而后转到步骤3)；

230)判断当前丢点笔划表中是否存在这样的记录：即，该待弥补区域下端点的纵坐标向下取整所得到的纵坐标值与该记录的纵坐标相同且该待弥补区域的横坐标比该记录中的右横坐标大一，若是，则转到步骤231)；若否，则转到步骤234)；

231)判断该记录中的非丢点标志是否为“假”，若是，则转到步骤232)；若否，则直接转到步骤233)；

232)将该记录中的非丢点标志设置为“真”，并将左横坐标设置为本横坐标；

233)将该记录中的右横坐标更新为本横坐标，而后转到步骤3)；

234)判断该待弥补区域的纵坐标向下取整是否大于等于当前丢点笔划表所含记录中的纵坐标，若是，则转到步骤236)，若否，则转到步骤235)；

235)在当前丢点笔划表中新增一条记录，并设置该新记录中的纵坐标为该待弥补区域下端点的纵坐标、左横坐标和右横坐标均为本横坐标、非丢点标志为“真”、丢点标志为“假”，而后转到步骤3)；

236)判断该记录的丢点标志和非丢点标志是否都为“真”，若是，则判定存在交点凹陷，所述交点凹陷区域的纵坐标为该记录中的纵坐标，所述交点凹陷区域的横坐标介于该记录中的左横坐标到右横坐标之间，而后转到步骤237)；若否，则转到步骤239)；

237)对所述交点凹陷区域进行填充；

238)将该记录从当前丢点笔划表中删除，而后转到步骤3)；

239)判断该待弥补区域的横坐标是否比该记录中的右横坐标大一以上，若是，则将该记录从当前丢点笔划表中删除；

所述步骤3)包括：重复所述步骤1)和步骤2)，直至已基于全部扫描线而完成对矢量图形的检测和弥补。

4.根据权利要求1所述的改善矢量图形填充效果的方法，其特征在于，在所述步骤2)之前或之后还包括这样的步骤：即，若判断出所述待弥补区域为丢点待弥补区域，则采用丢点弥补机制对其填充。

5.根据权利要求1所述的改善矢量图形填充效果的方法，其特征在于，每一条所述扫描线为同一横坐标上的像素的中心的连线，所述扫描线的扫描顺序为自左向右逐一扫描，或者自右向左逐一扫描；或者

每一条所述扫描线为同一纵坐标上的像素的中心的连线，所述扫描线的扫描顺序为自下向上逐一扫描，或者自上向下逐一扫描。

6.一种改善矢量图形填充效果的系统，其特征在于包括：

待弥补区域检测单元，用以检测扫描线所经过的矢量图形部分是否存在待弥补区域；

丢点笔划表管理单元，用以根据所检测到的待弥补区域而动态地建立和维护丢点笔划表；

交点凹陷判别单元，用以基于丢点笔划表来判断所存在的待弥补区域是否为交点凹陷，并在判断出该待弥补区域为交点凹陷后，向交点凹陷弥补单元发送弥补指令；以及

交点凹陷弥补单元，用以根据所述弥补指令而对已确认为交点凹陷的待弥补区域进行填充；

所述丢点笔划表为表示待弥补区域相关信息的动态表，其中的每一条记录均对应于一个所述已检测出的待弥补区域，并且每一条记录均包括相应待弥补区域的纵坐标、左横坐标、右横坐标、非丢点标志和丢点标志五个表项；

所述交点凹陷判别单元采用下述规则判断每一条扫描线所对应的矢量图形部分中的待弥补区域是否为交点凹陷：

若所述待弥补区域为非丢点待弥补区域并且当前丢点笔划表中存在这样的记录：即，所述待弥补区域下端点的纵坐标向下取整得到的纵坐标值与该记录的纵坐标相同且所述待弥补区域的横坐标比该记录中的右横坐标大一，则判定所述待弥补区域为交点凹陷。

7.根据权利要求6所述的改善矢量图形填充效果的系统，其特征在于，所述交点凹陷判别单元基于每一条扫描线，判断相应待弥补区域是否为交点凹陷，并在判断出该待弥补区域为交点凹陷后，向交点凹陷弥补单元发送弥补指令。

Images