用于生成基于结构的ASCII图片的方法和设备

1.一种用于根据矢量轮廓图生成ASCII图片的方法，包括：
将矢量轮廓图光栅化并划分成多个网格单元，所述多个网格单元中的至少之一具有对应的图像内容，所述图像内容作为用来与ASCII字符匹配的参照图；
利用对数-极坐标直方图将每个参照图与ASCII字符相匹配；以及
将所有匹配的ASCII字符组合以形成所述ASCII图片，
其中，所述匹配包括：
用相同的分布模板对参照图和所有的ASCII字符进行取样；
通过对参照图和每个ASCII字符中的每个相同采样点的特征向量进行比较，确定参照图和每个ASCII字符之间的形状不相似度；以及
选取与参照图具有最小的形状不相似度的ASCII字符与所述参照图匹配。
2.如权利要求1所述的方法，其中，所述矢量轮廓图是由以下步骤生成：
将图像转化成轮廓图；以及
对所述轮廓图进行矢量分析以生成所述矢量轮廓图。
3.如权利要求1所述的方法，其中所述光栅化包括：
根据目标字符分辨率以及ASCII字符的高和宽，将所述矢量轮廓图光栅化并划分为多个网格单元；以及
通过抽取所述矢量轮廓图的中心线，用与ASCII字符具有相同厚度的线条绘制所述矢量轮廓图。
4.如权利要求1所述的方法，其中，每个取样点的特征向量包括多个分量，每个分量对应于与所述取样点相关的对数-极坐标窗中一个区间内的灰度值总和。
5.如权利要求4所述的方法，其中，网格单元和ASCII字符之间的形状不相似度是基于所述网格单元和所述ASCII字符中的取样点的特征向量而确定。
6.如权利要求5所述的方法，其中，网格单元和ASCII字符之间的形状不相似度通过以下步骤确定：
确定第一特征向量组，所述第一特征向量组对应于网格单元中的取样点；
确定第二特征向量组，所述第二特征向量组对应于ASCII字符中的取样点；
计算第一特征向量组和第二特征向量组之差的范数；以及
将所述范数标准化以形成所述形状不相似度。
7.如权利要求1所述的方法，进一步包括：
确定所述矢量轮廓图与其匹配的ASCII图片之间的平均形状不相似度；
对所述矢量轮廓图迭代地变形；
确定每一幅变形的图像与其匹配的ASCII图片之间的平均形状不相似度；以及选取对应于最小的平均形状不相似度的ASCII图片。
8.如权利要求1所述的方法，进一步包括：
对所述矢量轮廓图迭代地变形；
确定每个变形的图像的局部变形程度值；以及
基于所述形状不相似度和所述局部变形程度值选取ASCII图像。
9.如权利要求1所述的方法，进一步包括：
对所述矢量轮廓图迭代地变形；
根据变形的图像中的每条线段的局部变形程度值和广域变形程度值中的较大值，确定每个变形图像的最终变形程度值；以及
基于所述形状不相似度和所述最终变形程度值选取ASCII图像。
10.一种用于根据矢量轮廓图生成ASCII图片的设备，包括：
光栅化模块，将矢量轮廓图光栅化并划分成多个网格单元，所述多个网格单元中的至少之一具有对应的图像内容，所述图像内容作为用来与ASCII字符匹配的参照图；
匹配模块，利用对数-极坐标直方图将每个参照图与ASCII字符相匹配；以及生成模块，将所有匹配的ASCII字符组合以形成所述ASCII图片，
其中，所述匹配模块包括：
取样单元，用相同的分布模板对参照图和所有的ASCII字符进行取样；
计算单元，确定参照图和每个ASCII字符之间的形状不相似度；
比较单元，通过对参照图和每个ASCII字符中的每个相同采样点的特征向量进行比较，确定参照图和每个ASCII字符之间的形状不相似度；以及
选择单元，选取与参照图具有最小的形状不相似度的ASCII字符与所述参照图匹配。
11.如权利要求10所述的设备，其中所述光栅化模块进一步被配置为：
根据目标字符分辨率以及ASCII字符的高和宽，将所述矢量轮廓图光栅化并划分为多个网格单元；以及
通过抽取所述矢量轮廓图的中心线，用与ASCII字符具有相同厚度的线条绘制所述矢量轮廓图。
12.如权利要求10所述的设备，其中，每个取样点的特征向量包括多个分量，每个分量对应于与所述取样点相关的对数-极坐标窗中一个区间内的灰度值总和。
13.如权利要求12所述的设备，其中，网格单元和ASCII字符之间的形状不相似度是基于所述网格单元和所述ASCII字符中的取样点的特征向量而确定。
14.如权利要求13所述的设备，其中，所述计算单元进一步被配置为：
确定第一特征向量组，所述第一特征向量组对应于网格单元中的取样点；
确定第二特征向量组，所述第二特征向量组对应于ASCII字符中的取样点；
计算第一特征向量组和第二特征向量组之差的范数；以及
将所述范数标准化以形成所述形状不相似度。
15.如权利要求10所述的设备，进一步包括变形模块，所述变形模块对所述矢量轮廓图迭代地变形；
其中，所述计算单元进一步被配置为确定所述矢量轮廓图与其匹配的ASCII图片之间的平均形状不相似度，并确定每一幅变形的图像与其匹配的ASCII图片之间的平均形状不相似度；所述选择单元进一步被配置为选取对应于最小的平均形状不相似度的ASCII图片。
16.如权利要求10所述的设备，进一步包括变形模块，所述变形模块对所述矢量轮廓图迭代地变形；
其中，所述计算单元进一步被配置为确定每个变形的图像的局部变形程度值；所述选择单元进一步被配置为基于所述形状不相似度和所述局部变形程度值选取ASCII图像。
17.如权利要求10所述的设备，进一步包括变形模块，所述变形模块对所述矢量轮廓图迭代地变形；
其中，所述计算单元进一步被配置为根据变形的图像中的每条线段的局部变形程度值和广域变形程度值中的较大值，确定每个变形图像的最终变形程度值；所述选择单元进一步被配置为基于所述形状不相似度和所述最终变形程度值选取ASCII图像。

用于生成基于结构的ASCII图片的方法和设备\n技术领域\n[0001] 本申请涉及ASCII技术，具体地，涉及用于生成基于结构的ASCII图片的方法和设备。\n背景技术\n[0002] 一般来说，ASCII图片可以被分为两个主要的类别，即，基于色调的图片和基于结构的图片。基于色调的ASCII图片维持了原图的明暗信息，而基于结构的ASCII图片可以捕获原图主要内容的结构信息。例如，参照图1(a)-1(c)，根据图1(a)中的原始图片可以获得图1(b)中基于色调的ASCII图片，也可以获得图1(c)中基于结构的ASCII图片。目前，已经存在很多处理方法来生成基于色调的ASCII图片。但是，令人满意的基于结构的ASCII图片还是只能用手工生成。至今依然没有工具能够有效而容易地生成基于结构的ASCII图片。\n[0003] 对基于结构的ASCII图片来说，面临的主要问题是很难用有限的字符形状和严格受限于网格的字符分布来表示无限的图像内容。图2(a)-2(c)示出了ASCII制作者生成基于结构的ASCII图片的两种常用匹配策略。图2(a)显示了图1(a)中的原始图生成的边缘图和图1(c)中基于结构的ASCII图片的重叠结果。通常，为了提高原图和字符的匹配机会，ASCII制作者会允许字符和原图结构非精确对准，如图2(b)所示，甚至会灵活地对原图做变形，如图2(c)所示。事实上，这种形状匹配的难题是一种常见的模式识别问题。在各种应用中，例如ASCII技术和光学字符识别(OCR)，形状匹配都应该允许适量的偏移和变形(例如缩放、平移和旋转)。举例来说，在识别字符“O”和“o”时，应该考虑缩放和平移，而在识别字符“6”和“9”时，应该考虑旋转。不幸的是，现有的形状匹配中的形状相似度度量或者要求完全对准，或者完全不受变形影响，因此都不适用。\n发明内容\n[0004] 本申请提出了一种可以捕获原始图片的结构信息来生成基于结构的ASCII图片的技术，其中设计并使用了一种非精确对准的形状相似度度量。本申请提出的相似度度量既允许适量的形变，同时还能够考虑到形变导致的差别。此外，本申请还引入受限的图像变形来提升字符匹配的机会。给定输入图片和目标字符分辨率，ASCII图片的生成可以简化为一个优化过程，该优化的目标是将与原图形状匹配的不相似度以及变形的程度最小化。\n[0005] 本申请旨在提供一种新的技术来生成目前只能由手工生成的基于结构的ASCII作品。本申请的方案只需极少的用户交互，并能在几分钟内生成出色的ASCII作品，这些作品的品质甚至可以比得上人们的手工作品。本申请为ASCII爱好者提供了一种有效且容易的基于结构的ASCII作品的生成方法。\n[0006] 根据本申请的一方面，一种用于根据矢量轮廓图生成ASCII图片的方法包括：将矢量轮廓图光栅化并划分成多个网格单元，所述多个网格单元中的至少之一具有对应的参照图；利用对数-极坐标直方图将每个参照图与ASCII字符相匹配；以及将所有匹配的ASCII字符组合以形成所述ASCII图片。\n[0007] 根据本申请的另一方面，一种用于根据矢量轮廓图生成ASCII图片的设备包括：\n光栅化模块，将矢量轮廓图光栅化并划分成多个网格单元，所述多个网格单元中的至少之一具有对应的参照图；匹配模块，利用对数-极坐标直方图将每个参照图与ASCII字符相匹配；以及生成模块，将所有匹配的ASCII字符组合以形成所述ASCII图片。\n附图说明\n[0008] 图1示出了由基于同一幅参照图生成的基于色调的ASCII图片和基于结构的ASCII图片。\n[0009] 图2示出了ASCII制作者通常使用的两种匹配策略。\n[0010] 图3示出了根据本申请第一实施方案的方法的流程图。\n[0011] 图4示出了根据本申请的一个实施方案在处理过程中生成的一系列图片。\n[0012] 图5示出了本申请采用的非精确对准的形状相似度度量。\n[0013] 图6示出了根据本申请的方法与三种常用度量之间的比较。\n[0014] 图7示出了本申请中的线段的变形。\n[0015] 图8示出了本申请的方法中采用的图像的受限变形。\n[0016] 图9示出了根据本申请第二实施方案的方法的流程图。\n[0017] 图10示出了根据本申请第三实施方案的方法的流程图。\n[0018] 图11示出了根据本申请第四实施方案的方法的流程图。\n[0019] 图12示出了根据本申请的一个实施方案的设备。\n[0020] 图13示出了本申请另一实施方案的设备。\n[0021] 图14示出了迭代变形过程中生成的中间结果。\n[0022] 图15示出了本申请的方法与现有技术中的方法之间的比较。\n具体实施方式\n[0023] 在下文中，将参照附图对本申请的示例性实施方案进行描述。\n[0024] 实施方式1\n[0025] 参照图3，根据本申请第一实施方案用于生成ASCII图片的方法300包括以下步骤。在步骤301，将输入的矢量轮廓图光栅化并将其划分为多个网格单元。在步骤302，利用基于非精确对准的形状相似度度量，将每一个网格单元中的图像内容与一个ASCII字符匹配。然后，在步骤303中，将匹配到的ASCII字符收集到一起以生成ASCII图片。在本方法中，待处理的图像可以是只包含多段线的矢量轮廓图。对于例如照片的其它图像，可应先用已知的简单的边缘检测方法或者高级的线条图生成方法将其转换成轮廓图，然后再向量化为矢量轮廓图。例如，图4中所示的图像401可以被转换和向量化成对应的矢量轮廓图\n402。光栅化和字符匹配的步骤将在下文详细描述。\n[0026] 步骤301：光栅化\n[0027] 按照本申请的实施方案，基于目标字符分辨率及ASCII字符的宽度和高度将矢量轮廓图光栅化并划分为多个网格单元。例如，目标字符分辨率假定为Rw×Rh，这里Rw和Rh分别指ASCII图片横向和纵向输出的最大ASCII字符数。一般来说，ASCII字符在不同字体中有不同的厚度和字符宽度。在用户选择字体和字符大小后，字符采用的宽度Tw和高度Th就被确定下来，从而字符的高宽比被固定为 此外，本方法中字符的厚度信息将通过抽取中心线的方式忽略掉，因此本方法只处理具有固定字符宽度和固定字符高宽比 的字体。输入的多段线和字符将被渲染为相同的线条厚度，这样就将可以匹配的重点放在形状上。已知W和H，则 因此，根据公式\n字符分辨率就可以由单一的变量Rw确定，这里W和H是以像素计算的\n输入图像的宽度和高度，在给定输入图像时后，该高度和宽度就是已知的；而变量Rw则是由用户指定的。根据以上的参数，纵向的字符分辨率就可以计算出来。因此，首先将向量图缩放并光栅化到TwRw×ThRh的域。然后对TwRw×ThRh个网格单元分别进行处理以匹配到相对应的ASCII字符。\n[0028] 步骤302：字符匹配\n[0029] 为了更容易地解释，将每一个网格中用来跟ASCII字符匹配的图像内容称为参照图。根据一个实施方式，对数-极坐标的直方图将被用于形状匹配。具体来说，就是在矢量轮廓图被光栅化并划分为网格单元后，对每一个网格单元采样，并确定其中的每一个采样点的对数-极坐标的直方图。对数-极坐标的直方图可以表征由一个对数-极坐标的窗口覆盖的、该采样点的局部邻居的形状特点。如图5(a)所示，对数-极坐标的窗口是一个包含60个区间的圆。这些区间在对数-极坐标的空间里对局部邻居均一地划分。对每一个区间，将计算其中像素的灰度总和，并将该灰度和被作为直方图的分量。因为这些区间被均一地分布在对数-极坐标的空间里，所以直方图将对距离近的点更为敏感。此外，对每一个采样点来说，因为只有区间里的灰度总和影响计算，因此直方图自然就可以做到对小幅度的变形不敏感，因此可以做到允许适量的形变。\n[0030] 在计算像素灰度和的时候，黑色的像素灰度值为1，白色的像素灰度值为0。对第i个采样点p来说，它的第k个区间的值hi，k可以用公式hi，k＝∑(q-p)∈bin(k)I(q)来计算，这里p是位于对数-极坐标的窗口中心的第i个采样点；q是当前参与计算的像素点；(q-p)是像素点q和对数-极坐标的窗口中心点p的相对位置关系；I(q)返回像素点q的灰度值。\n因此，第i个采样点p的所有的区间值hi，k就构成了它的特征向量hi。例如，假定每个采样点有60个区间，那么特征向量hi就包含60个区间值hi，k(k＝1，...，60)。\n[0031] 类似地，每一个ASCII字符都会被采样，每一个采样点也都会得到一个确定的对数-极坐标的直方图。注意，参照图和ASCII字符必须采用相同的采样模式。针对每一个采样点测算一个对数-极坐标的直方图。为了考虑形变情况(或者位置的变化)，在一个实施方式中，对参照图和ASCII字符在相同的网格分布模式下采样。根据图5(b)，将按照网格分布获得N个采样点。然后便可以将采样点的特征向量(直方图)们合并起来描述形状特征，如图5(c)所示。\n[0032] 因此，参照图和ASCII字符形状之间的形状不相似度可以通过逐点比较它们的特征向量来获得。特征向量与某个网格单元最相似的ASCII字符将被选择作为该网格单元的匹配字符。\n[0033] 按照本申请的一个实施方式，参照图和ASCII字符形状之间的形状不相似度可以通过用下式逐点比较它们的特征向量来衡量：\n[0034] \n[0035] 这里hi(h′i)是参照图S(ASCII字符S’)的第i个采样点的特征向量；M＝(n+n′)是归一化因子，n(n′)是形状S(S′)的总灰度值。与形状S的不相似度最小的形状S’将被选择作为形状S的匹配。在下文中，矢量轮廓图的第j个网格单元和它对应的ASCII字符之间的形状不相似度将被表示为\n[0036] 按照这样的匹配策略，归一化因子抵消了由绝对灰度值产生的影响，并且形状的全局形变也被考虑到。此外，对数-极坐标直方图本身就考虑到旋转信息。所有对数-极坐标直方图拥有相同的缩放比例，因此缩放信息也被考虑到了。因此本申请提出的匹配方法既不要求完全对齐，也能考虑形变影响。\n[0037] 根据先前所述，直方图根据经验可以设计为将半径轴在对数空间内分为5个区间，将角度轴分为12个区间。因此，直方图共包含有60个区间。覆盖窗口的半径大约为字符短边的一半。采样点的数目N等于(Sw/2)×(Sh/2)，这里Sw和Sh是以像素计算的图像的宽度和高度，分别表示图像的横向和纵向上的像素总数。为了抑制区间设计固有的离散性导致的锯齿现象，图像可以在比较形状特征前先通过一次高斯滤波，比如可选大小为7×7的高斯核函数进行滤波。\n[0038] 本申请中采用的形状匹配度量可以通过与其他常用的度量比较进行衡量，包括经典的形状上下文度量(shape context，其完全不受位移和缩放影响)、SSIM度量(要求精确对准的衡量结构相似度的度量)、以及模糊化后的RMSE度量(均方根误差)。对最后一种度量RMSE来说，为了得到更好的结果，它的衡量是基于7×7的高斯核函数模糊化后的图像得到的。\n[0039] 参照图6，四种不同的形状(第一列)试图查询合适的字符匹配。对每一种度量，都从95个可打印的ASCII字符中找到最优匹配字符。从匹配的结果来看，形状上下文度量强调了形状，而忽略了位置信息(如第2个和第4个查询所示)。SSIM和RMSE这两种度量要求精确对准，因此过度强调了查询图和字符之间重叠的区域，而忽视了形状信息(如第一个和第三个查询所示)。作为对比，在所有的查询结果中，本申请的方法都在形状和位置信息之间寻找到了最佳平衡。对一条长的位于中心的水平线(第4个查询)的查询证明了本申请的方法的优越性。形状上下文度量虽然最大化了形状的相似性，却完全忽略了大幅的偏移，选择了较长的下划线字符“_”来匹配这条长线段。而SSIM和RMSE度量则匹配到等于号“＝”，因为它的下线段和查询图重叠在了一起。本申请的方法既关注了形状信息(一条单线)，又不要求精确的对准，因此选择了稍短的连字号“-”作为最优匹配的字符。\n[0040] 实施方式2\n[0041] 按照本申请的第二实施方式，对参照图轻微地变形，以提升匹配到合适字符的机会。\n[0042] 图9是根据第二实施方式的方法900的流程图。在步骤901，一幅ASCII图片已经基于输入的矢量轮廓图产生出来。这个步骤可以按照上文所述的第一实施方式中的步骤301-303来实施。可以理解，矢量轮廓图的每一个网格单元和ASCII结果图片中匹配的ASCII字符之间的形状不相似度可以在步骤901中获得。然后，在步骤902中，通过用总的形状不相似度除以非空网格单元的数目来获得矢量轮廓图和ASCII结果图片之间的平均形状不相似度。在步骤903中，对矢量轮廓图轻微变形。举例来说，这样的变形可以通过迭代地调整多段线的顶点位置来实现。如图4所示，图像403就是一个变形后的结果。在这种情况下，对于每一幅生成的ASCII图片中的每一个网格单元，可确定其中每一个采样点的特征向量，也可以得到参照图的网格单元和ASCII字符之间的形状不相似度。如前所述，变形后的图片的每一个网格单元依然会寻找到最匹配的字符，并合在一起构成与其相应的ASCII图片结果。因此，在步骤904中，将产生与变形后的矢量轮廓图对应的ASCII图片，而变形后的矢量轮廓图和对应的ASCII图片之间的形状不相似度的均值将在步骤905中得到。举例来说，图4中的ASCII图片404就是变形后的图像403的对应匹配结果。\n[0043] 步骤903-905迭代执行，直到在步骤906确定迭代变形过程将会结束。上述过程可称为离散的优化过程。在优化过程的每一次迭代变形中，在矢量轮廓图中随机选择一个顶点，并将其位置随机移动一段距离，新位置与先前的位置之间的最大距离是字符图片较长边的长度。然后，所有受到位置替换影响的网格单元将被识别出，并再次为其找到最匹配的字符。对每一次变形，将获得一个平均的形状不相似度。这种情况下，在步骤906判断新获得的平均形状不相似度是否小于先前的不相似度。如果连续多次(例如，预先确定的次数)获得的平均形状不相似度都不比先前获得的不相似度小，该优化过程将在步骤906被判定需要结束。\n[0044] 作为一种选择，在步骤906可判断矢量轮廓图是否经过指定次数的变形。如果已经发生指定次数的变形，则该优化过程会结束。\n[0045] 在步骤906决定结束优化过程后，在步骤907，从所有生成的ASCII图片中选择出来一幅含有最小平均形状不相似度的ASCII图片和对应的矢量轮廓图，用以近似原始图片。例如，如图4所示，在经过指定次数的形变后，最优的结果图片405将被选择作为输出。\n[0046] 实施方式3\n[0047] 但是，在上述第二实施方式中，无约束的变形可能破坏输入图片的整体结构。在这种情况下，提出了第三实施方式用来量化变形的程度，并以此选择形变最小的ASCII图片。\n[0048] 在该实施方式中，向量图的形变程度以及字符和变形图片之间的不相似度都要被考虑到。按照第三实施方式的方法1000的流程图如图10所示。第三实施方式和第二实施方式很相似，除了步骤1006和步骤1007。在步骤1006中，对变形后的矢量轮廓图中的每一条线段计算一个与之相关的局部形变程度。在步骤1007，将基于形状不相似度和局部形变来计算目标函数。这两个步骤将在下文具体解释。此外，在该方案中，在步骤1002和1005中确定并在步骤1007使用矢量轮廓图的每一个网格单元和对应匹配的ASCII字符之间的形状不相似度，而不是整幅矢量轮廓图的平均不相似度。\n[0049] 局部约束\n[0050] 按照第三实施方式，将根据图像中的每一条线段来计算矢量轮廓图的形变。考虑到旋转和缩放，每一条线段的局部约束按如下定义。如图7(a)所示，一条原始线段AB(下文中称为线段Li)变形到A’B’，不考虑变形中的全局位移，线段li的局部形变可以用下式来衡量：\n[0051] Dlocal(Li)＝max{Vθ(Li)，Vr(Li)}， (2)\n[0052] 其中Vθ(Li)＝exp(λ1θ)，而\n[0053] 这里，Vθ和Vr分别是在旋转和缩放方面的变形程度，它们之中的较大值最终决定线段的局部形变程度。θ∈[0，π]是原始线段和变形后的线段之间的角度。r和r’分别表示原始线段和变形后的线段的长度。参数λ1、λ2和λ3是权重，可据经验将其分别设为8/π、2/min{Tw，Th}和0.5。函数exp()可以确保形变程度不小于1.0。权重λ1、λ2和λ3分别用来控制由于角度、绝对长度和相对长度导致的形变程度。绝对长度的变化用|r′-r|来衡量，而相对长度的变化则通过长度倍数 来衡量。这样，每一条线段的局部形变信息就都获得了。\n[0054] 相应地，对网格单元j来说，局部图像内容的变形程度 则可以按下面的公式来定义：\n[0055] \n[0056] 具体地，首先识别所有与当前网格单元j相交的的线段Li，并将其记为集合{L}。\nli是线段Li中被网格单元j占据的线段部分的长度。然后，可将网格单元j的局部形变值计算为所有参与计算的线段的形变程度的加权平均。\n[0057] 在这种情况下，步骤1007中，能量E将被如下定义为整体的目标函数来衡量每一幅根据变形后的图像生成的ASCII图片，如下面的公式，\n[0058] \n[0059] 其中m是字符单元的总数，K是非空单元的总数并在这里作为归一化因子。\n是第j个网格单元同相应的最优匹配的字符之间的不相似度，如公式(1)所定义，并在步骤\n1002或者1005中计算得到。 则是步骤1006中确定的第j个网格单元的局部形变程度。可以理解，对于没有经过变形步骤的原始矢量轮廓图， 可被认为等于1。\n[0060] 类似地，步骤1003-1007将被迭代执行，直到在步骤1008确定迭代变形过程结束。\n上述过程可被视为离散的优化过程。在优化过程的每一次迭代变形中，可在矢量轮廓图中随机选择一个顶点，将它的位置随机移动，新位置与先前的位置之间的最大距离是字符图片较长的边。然后，识别所有受到位置替换影响的网格单元，并再次为其找到最匹配的字符。对每一次变形，可以得到一个能量值E。在这种情况下，可采用模拟退火法。具体地，在步骤1008中判断新计算的E是否有减少。如果有减少，则位置替换将被接受。否则，可使用\n0.997\n转换概率Pr＝exp(-δ/t)来做决定，这里的δ是两次迭代之间的能量差；t＝0.2tac是温度；c是迭代索引；ta是初始的所有网格单元的匹配误差。如果Pr小于一个[0，1]之间的随机数，该次位置替换将被接受；否则，将被拒绝。当E连续co次迭代都不降低，则该优化过程结束。例如，在实现过程中，参数co可能被选择为5000。因此，如果能量E连续co次迭代都不降低，将在步骤1008中判定该优化过程将被结束。\n[0061] 作为一种选择，在步骤1008判断矢量轮廓图是否已变形指定的次数。如果已经发生指定次数的变形，该优化过程结束。\n[0062] 在步骤1008确定结束优化过程后，在步骤1009选择一幅含有最小能量E的ASCII图片，用以近似原始图片。\n[0063] 实施方式4\n[0064] 上文讨论的局部变形约束有效地防止了局部的过度变形，但是它不能避免整体上的过度变形。例如，如图8(b)所示，三个圆形窗户偏移了原来的位置并破坏了整体的布局，尽管它们每一个在局部上并没有多大的变形。在这个意义上说，局部的变形量不能很好地反映整体的变形程度。\n[0065] 为了限制整体上的变形，在第四实施方式中进一步引入了二维无障碍约束，从而使每一条线段和它周围线段的相对方位和位置都可以被保持下来。\n[0066] 图11示出了根据第四实施方式的方法1100的流程图。第四实施方式和第三实施方式的区别在于，在步骤1106中进一步计算变形后的矢量轮廓图中每一条线段的整体形变程度，如下文所述。\n[0067] 整体约束\n[0068] 为了计算线段(如图7(b)中的线段AB)的整体变形程度，多条射线从AB的中点向它的四周射出，从而找到周围跟它最接近的那些线段。对于每一条线段，进一步找出该线段上离点P最接近的点Pk。接下来，可以计算无障碍约束的值。例如，整体变形程度Daccess(Li)可以利用以下的公式来计算，\n[0069] \n[0070] 这里，nl是利用无障碍约束在点P周围找到的线段的总条数。Dlocal(PPk)是线段PPk的局部变形程度值，该值可以利用公式(2)计算得到。wk是权值，并可由公式计算得到，点Pk离点P越近，它相应的权值就越高。\n[0071] 因此，总体变形程度的值可以由以下的公式计算而得\n[0072] Ddeform(Li)＝max{Dlocal(Li)，Daccess(Li)}. (6)[0073] 基于以上的度量方法，每一个线段的变形程度值都可以被估算出来。因此，对于一个网格单元j里的图像内容，其变形程度值 也可以被计算出来。具体地，首先识别与当前网格单元j相交的全部线段，并将其记为集合{L}。li是线段Li在网格j里面的部分的长度。那么，网格单元j的变形程度值可计算为参与计算的所有线段的变形程度值的加权平均值，如以下公式所示：\n[0074] \n[0075] 在这种情况下，在步骤1107，作为目标函数的能量值E可定义为：\n[0076] \n[0077] 这里，m是字符单元的总数，K是非空单元的总数并用作归一化因子。 是第j个网格单元的图像内容和与它最匹配的字符的不相似度，如公式(1)定义。 是第j个网格单元的图像内容的变形程度值。\n[0078] 在执行第二实施方式所述的优化过程之后，并在步骤1108确定终止迭代之后，可在步骤1109选取对应于最小能量值E的ASCII图片作为原始图像的近似图。\n[0079] 在上文中，描述了根据本申请生成基于结构的ASCII图片的方法的示例性实施方式。接下来，将描述根据本申请生成基于结构的ASCII图片的设备。\n[0080] 图12示出了根据本申请用于生成基于结构的ASCII图片的设备1200。图中，设备\n1200由光栅化模块1210、匹配模块1220和生成模块1230组成。光栅化模块1210被配合为将矢量轮廓图光栅化并划分成多个网格单元，至少一个网格单元具有对应的参照图。匹配模块1220基于每个参照图的对数-极坐标直方图为相应的参照图找到最匹配的ASCII字符。生成模块1230把所有匹配的ASCII字符排列在一起形成ASCII图像。\n[0081] 匹配模块1220包含取样单元1221、计算单元1222、比较单元1223和选择单元\n1224。取样单元1221利用同一分布模板对参照图和所有的ASCII字符图像进行取样。计算单元1222确定参照图和每一个ASCII字符图像的形状不相似度。比较单元1223用于对确定的形状不相似度进行相互比较。选择单元1224用于选取选择和参照图的形状相似度最大的ASCII字符来与参照图匹配。\n[0082] 计算单元1222可进一步利用对数-极坐标直方图，计算参照图和每个ASCII字符图像中的每一个取样点的特征向量。基于这些特征向量，计算单元1222进一步计算出参照图和ASCII字符之间的形状不相似度。\n[0083] 光栅化单元1210可进一步根据目标分辨率和ASCII字符的宽、高，把矢量轮廓图光栅化并划分成多个网格单元，并且通过提取矢量轮廓图的中线用厚度与ASCII字符相同的线条来绘制矢量轮廓图。\n[0084] 每个取样点的特征向量可包含多个分量，每一个分量表示位于与一个取样点相关联的对数-极坐标窗内的一组点的灰度值总和。\n[0085] 基于网格单元和ASCII字符中的对应取样点的特征向量，可以计算出网格单元和ASCII字符之间的形状不相似度。\n[0086] 计算单元1222可以进一步确定对应于网格单元中的取样点的第一特征向量组；\n确定对应于ASCII字符中的取样点的第二特征向量组；计算这两个特征向量序列的差的范数；并把这个范数进行标准化以形成形状不相似度。\n[0087] 图13示出了根据本申请另一个实施方式用于生成基于结构的ASCII图像的设备\n1300。两个实施方式中相同或相似的部分用类似的标号示出。如图所示，装置1300进一步包括变形模块1340，该模块用于对矢量轮廓图像进行迭代地变形。\n[0088] 在这个实施方案中，计算单元1322可进一步确定矢量轮廓图与其匹配的ASCII图片之间的形状不相似度的平均值；确定每一幅变形图像与其匹配的ASCII图片之间的形状不相似度的平均值；并选取具有最小的平均形状不相似度ASCII图片。作为另一选择，计算单元1322可进一步确定每一个变形图像的局部变形程度值；并基于形状不相似度和局部变形程度值选取ASCII图像。作为又一选择，计算单元1322可进一步根据变形后图像中每条线段的局部变形程度值和广域变形程度值中的较大值确定每一个变形图像的最终变形程度值；并基于形状不相似度和最终变形程度值选取ASCII图像。\n[0089] 应该注意，对应不同字符分辨率的能量值是直接可比的，因为它们在能量方程中已经被标准化。图15显示了基于本申请提出的方法和现有技术的方法分别生成的三个不同字符分辨率的结果图，并示出了其能量值。下面一行的结果是由本申请提出的方法产生，其中，对应最小能量值的中间结果(28×21)其效果是最令人满意的，左边的结果能量值相对比较大，其视觉效果也差了一些。上面一行的结果是由之前的方法产生的，其效果明显比本申请提出的方法差了很多。\n[0090] 在当前的实现中，利用了模拟退火模型来解决离散的优化问题。其他用于解决离散优化问题的方法也可以适用。图14给出了优化过程的一些中间结果以及它们对应的能量值。可以看出，随着迭代次数的增加，能量值逐渐地减少，并且产生的ASCII艺术的视觉效果也越来越好。\n[0091] 用户可以利用系统确定最适合的字符分辨率。因为目标函数已经对字符分辨率作了相应的标准化处理，所以对应最小目标值的分辨率就是最适合的字符分辨率。\n[0092] 上文对本申请的实施方案结合附图进行了详细描述。但是，对本领域技术人员显而易见的是，并不一定要用到一个方案里提到的所有特征。上述所述的技术特征可适当地组合来实现本申请。