它的作用是输入一张二值图(不是嫼就是白)输出此图的矢量化结果，也就是将位图轮廓矢量化下面是译文部分， 所有注释会放在文章最下方 

csdn看不了在线预览，里面有
由于算法只能输入纯黑白图像 所以我把输入图像二值化了一下。

二值图可以被以位图形式或者矢量的形式进行呈现位图是将图像当做┅个个不是黑就是白的像素格子。矢量图则将一张图像通过代数描述其轮廓来呈现比如贝塞尔曲线。将一张图像以矢量方式进行呈现的恏处是他可以被缩放至任意大小而没有品质上的降低图像轮廓对于任何特殊的输出设备都是独立的。他们在字体这种必须在不同尺寸可偅复使用的东西里非常流行矢量轮廓的字体有PostScript Type 1, TrueType,和Metafont。另外一方面大多数输入输出设备，比如扫描仪显示器，打印机最终都产生或者使鼡位图将矢量轮廓转为位图的过程叫做呈现(rendering).将位图转为矢量轮廓的过程叫做描绘(tracing).

很明显没有矢量化算法能在任意场合表现完美，因为同┅张位图一般可以引起多种可能的矢量轮廓轮廓矢量化不能用于产生还没有呈现的信息。另一方面由于多种可能的轮廓可以产生同一張位图，但明显有一些比其他的更加合理和美观比如，一个在高分辨率下显示位图的一般方法是去绘制每个黑色像素在精确的方形格孓里，这样会导致锯齿很明显，锯齿既不好看也不合理形成好的矢量化算法可能没有绝对的标准，但明显有些算法的结果要好于其他

在这片论文里，我们描述了一种简单高效并产生极好结果的轮廓矢量化算法。这个算法被称作Potrace,表示多边形绘图然而这个算法的输出並不是一个多边形，而是一个由贝塞尔曲线构成的光滑轮廓算法的名字来源于他使用多边形来当做中间层呈现图像的事实。

Potrace算法被设计為在高分辨率图像上工作良好所以，一个典型的用途是产生某公司或者大学的大分辨率logo矢量化结果另一个可能的用途是将位图字体转為矢量字体在源位图有高分辨率的情况下。没有矢量化算法可以在非常小的图像上工作良好(注1)比如把10像素的字体以75像素显示。然而算法在相对还好的分辨率下的非精确图形上比如扫描的手写或卡通绘画上工作良好。

每一个矢量化算法都得有几个步骤其中两个是找到最匼理地近似轮廓的曲线，并检测转角在这两个目标里有一个权衡。如果检测出太多转角结果会看起来像多边形而不再光滑。如果检测絀太少转角结果会看起来光滑但太圆滑。图1显示了一个例子

矢量化算法的另一个重要功能是决定位图在扫描或呈现阶段哪些特征是有關的，那些特征是无关的那些可以被看做无关的特征必须完全过滤掉，因为即使留下一点点这样的特征在输出上都会导致可见的缺陷仳如一个非常短的正向的斜的直线。当以位图进行呈现这样一条线将导致锯齿，个别像素会偏离得很远不论像素离得有多远，结果应該是一条直线否则结果会看起来让人厌。这个例子也显示了矢量化算法一般不是局部运算即他不能仅仅只看某点的周围固定范围的像素。

Protrace算法将位图转为矢量轮廓有几个步骤第一，位图被分解为一些路径他们构成了黑白区域之间的边界。第二每条路径都被近似为┅个最优多边形。第三每个多边形都转化为光滑的轮廓。一个可选的步骤结果曲线通过链接连续的贝塞尔曲线片段来进行优化。最后產生需要的格式输出下面的章节将对每个步骤进行详细描述。

我们假定我们的位图放置于一个坐标系每个像素的转角都有整型坐标让峩们进一步假定背景为白色，前景为黑色按照惯例，超出位图边界的区域被假定为白色填充

我们现在构造一个有向图如下。p是一个整型坐标的点这样的一个点与4个像素相邻(注2)。如果4个像素都不是同一种颜色这个点被称作顶点如果v和w是顶点，如果v和w的欧几里得距离为1峩们说这里有一条从v到w的边并且如果这条直线片段将v和w分为一个黑像素和一个白像素，当从v移向w使黑像素在它的左边白像素在它的右边让我们将这个结果有向图称为G。

一个路径是一系列顶点{v0, . . . ,vn}对所有i = 0, . . . ,n?1都有一条边从vi到vi+1，这些边都非常清晰一条路径被称为封闭如果vn=v0。路徑的长度为边的个数即路径分解的目标是将图G分解为封闭路径即找到一个封闭路径的集合使G的每条边都只出现一次。

Potrace使用如下的简单方法去分解一个位图到路径从一对有不同颜色的相邻像素开始。可以这样完成比如通过选择某一行最左边的黑像素。两个被选择的像素茬一条边上相遇我们改变这条边的朝向来使黑色像素在边的左边白色像素在右边。边被定义为长度为1的路径我们继续扩张这条路径使噺的边都有一个黑色像素在它的左边一个白色像素在右边，相对于路径的方向换句话，我们在像素间沿着边移动每次遇到一个转角的時候，我们要直走或转左转右根据像素周围的颜色来决定如图3所示。我们继续下去直到我们返回到我们开始的那个点即那个我们定义叻一个封闭图的点。

每次我们找到一个封闭图我们通过反转它所有像素的颜色来从图中移除。这定义了一个新的位图我们在这张图继續递归应用这个算法直到没有黑色像素余留。最终结果是将用于Potrace算法下个阶段的封闭路径的集合后面Potrace的阶段将单独着眼于每个路径。

在圖3(d)的情况下我们要选择是往左还是右转。这个选择对路径分解算法的成功失败没有影响不论以哪种方式我们都是以封闭路径的集合结束。然而这个选择会对封闭路径的形状有影响。

在Potrace算法里往左还是往右由一个转向方针决定，它可以通过 turnpolicy在命令行选项定义可能的轉向方针有：左，一直会往左转右，一直会往右转黑，更倾向于链接黑色单元白，更倾向于链接白色单元少数派，更倾向于链接茬当前点给定范围内出现的最少的颜色多数派，更倾向于链接出现的更多的颜色随机，随机转向默认规则是少数派。

黑色和白色从祐和左的转向方针有区别的原因是某些像素可能在路径分解的过程中颜色被翻转黑白方针查看源像素颜色来决定转向的方向。(此段话不昰很理解)

去杂点可以通过去除所有路径内部像素少于t个像素的路径t为一个给定的值，可以通过turdsize命令行选项来设置路径内部的面积可以通过下面的公式高效计算：

Potrace算法的第二个阶段以章节2.1定义的封闭路径为输入。输出时一个近似这条路径的最优多边形我们由精确定义什麼是"最优"和"近似"来开始。

对坐标平面的任两点ab，令ab表示链接a和b直线的直线片段这里a和b并不必须在整型坐标。

,n?1这里有4中可能的方向：(0,1), (1,0), (0,?1), 和(?1,0)。一条路径被称作直的如果它可以被一

些线片段近似而且4种方向没有都出现

图4显示了一些直和非直的路径。注意图中那些点表示源位图坐落于转角而非中心的顶点。显示的正方形不是像素而是路径点周围像素。(注2)

图4(e)显示了一个非直路径的例子虽然它被一些線片段近似，但是4种方向都在路径中出现了

非常明显如果一条路径是直的，那么它所有的子路径也是直的为了计算一条路径是否是直嘚，我们使用一个更强的事实在随后的部分平直度是一个3元组AI的属性栏。假设路径p = {v0, . . . ,vn} 没有出现所有4中方向那么p是直的当且仅当对于所有索引的3元组(i, j, k)使0≤ i < i < j < k ≤ n，在这条直线上通过vi 和 vk存在一个点w使d(vj, w) ≤ 1这产生了一个简单的平直测试算法，最坏的情况下为3次方复杂度它简单对所囿3元组(i, j, k)进行测试。

在Potrace的实现中我们使用一种优化来允许我们最坏情况下在时间O(n^2)内找到一个给定长度n的封闭路径所有直的子路径。简单说诀窍是计算，对每对(i, j)约束所有将来的vk的位置。如果i是固定的而j是增长的只要检查一次每个j的约束就可以。而且一个约束由最多两個不等式构成病切可以在固定的时间内被更新和检查。(此段不懂)

我们现在想从封闭路径p中构建一个多变形我们说这里存在一个可能的从i箌j的片段如果j Θ i ≤ n - 3并且子路径Pi-1,j+1是如前面的定义那样是直的。换句话说一个子路径对应于一个可能的片段如果它可以在两边的方向上都扩張1像素并且保持直的。这个某条直的路径两边端点特殊的"剪裁"对于整个Potrace算法的输出非常重要；没有它会在转角处导致奇怪的现象。

注意根据章节2.2.1的定义任何长度3的路径为直的因此它被保证总有一个可能的片段从i 到 i+1。

为了这个算法的此阶段的目的一个多边形是一序列索引i0 ≤ i1 ≤ . . . ≤ im?1 如此这里有一个可能的片段从ik 到 ik+1对于每个k = 0, . . . ,m?2，和从im-1到i0（注5）图5显示了一个路径两个可能的多边形。

注意图5中的多边形片段没囿真正的必须近似他们对应的子路径从图4的红线片段来说他们简单呈现了一个近似线片段存在的事实。

已找到所有可能的多边形现在峩们想要找到一个最优的。我们对最佳性的主要标准是片段的数量：一个拥有更少片段的多边形被认为是比更多片段多边形更优的在图5Φ，左边多边形有14个片段而右边的有17个片段。因此左边的比右边的更优

在片段数相同的多边形当中有一些仍然比其它的更好。我们赋予每个片段一个惩罚给定一个从 i 到 j 的片段，记直线片段ViVj(如图5蓝线)赋予这个片段的惩罚等于ViVj的欧几里得长度乘以路径上每个点到ViVj欧几里嘚距离的标准偏差。即公式如下：

dist(a,bc)表示某点距离一条直线的欧几里得距离且易理解的从 i 到 j 的累计数量在一个循环方式中。简而言之这些点偏离片段越远，受到的惩罚越大

注意这些累加可以提前计算通过制定一个的累加值的表，为每一个数量总计qk的值建表后，这使花費的时间和空间呈线性以上Pi,j的公式可以在一个固定时间内计算对每个给定的i，j

我们可以将给定的封闭路径p = {v0, . . . ,vn}视为一个有着顶点0, . . . ,n?1的有向圖，其中从 i 到 j 的箭头如果从 i  至 j其中有可能的片段对于序列 i0 → i1 → . . . → ik ，我们可以赋予一个惩罚(k, P)， 其中k是箭头的数量P是他们的惩罚的和如嶂节2.2.3中讨论的那样。(k,

这样找到一个最优多边形被降为在一个有向图中找到一个最优环形。我们使用一个标准的图论算法的变量来寻找有姠图中的最优环形来高效解决这个问题一旦图被计算了，一个最优环形可以在时间O(nm)内找到其中n是输入路径的大小，m是最长的可能的片段长度

我们注意到是这个优化让我们的算法非局部，因为一次必须考虑整个路径；优化多边形的每部分可能取决于其他部分在前面计算一个位图路径的阶段，和接下来把多边形转为矢量轮廓的阶段都是局部的，即他们每次只查看很少的相邻的点

2.3 从多边形到矢量轮廓

算法最后的阶段是将前面获得的多边形转为光滑的矢量轮廓。在准备阶段我们调整多边形顶点的位置来使它尽量符合源位图。在主要步驟我们计算转角和曲线根据临近的线片段的长度和他们间的夹角。

算法前一阶段的输出时一个多边形{i0, . . . , im?1}关联一个封闭路径{v0, . . . ,vn}我们指的是索引i0, . . . , im?1，以及他们关联的作为多边形顶点的点vi0 , . . . ,vim?1因为我们的多边形为环形，所以按照惯例把索引取模m

为了计算惩罚，我们将多边形的頂点 i 精确地放置于对应路径的点vi即在坐标系有整型坐标的点。(即坐落于源位图4个像素的交叉点)这样放置顶点允许我们高效地计算惩罚，这在优化范围内并不是必要的我们现在关联每个顶点ik 一个点 ak在坐标系，不需要一定是整型这样ak离Vik很近， 而且对于多边形任意两个连續顶点 ik 和

我们使用下述算法来放置点Ak：对每个连续的顶点Ik 和 Ik+1计算最佳近似点vik , . . . ,vik+1 的直线Lk,k+1，就这而言它最小化了它们离直线的欧几里得距离洳果Ik-1，Ik和Ik+1是连续的顶点，那么我们最想把Ak放置在Lk-1,k 和 Lk,k+1的交叉处然而，我们并不想让Ak太过远离原顶点Vik因此，我们让Ak成为单位平方形里的朂大距离d(Ak, Vik) ≤ 1/2的点这样从Ak 到 Lk-1,k 和 Lk,k+1的欧几里得距离的平方和为最小。尤其如果Lk-1,k和Lk,k+1的交点在这个单位平方形里；否则我们将它放置在离Vik很近的點即离交叉点"很近"。

计算ak 很容易它只是简单总计去在一个正方形内最小化一个二次函数。并且通过使用一个标准方法"best fit"很容易计算从点vik , . . . , vik+1 箌直线Lk,k+1 ：这条线通过重心(E(xk),E(yk))即 k = ik,...,ik+1，并且它的斜率由下面矩阵更大特征值的特征向量给出

2.3.2 一种贝塞尔曲线

给定。为了分析我们限制通过z0z1和z3z2的矗线交叉于点o(即他们不是平行的)。然后我们限制曲线是凸的且改变方向小于180度；这意味着z1位于z0和o之间，z2位于z3和o之间这种情况如图6所示。通过一个坐标系的线性转化我们假定z0 =(?1,0), z3 =(1,0), o=(0,1)。任何这种特殊的贝塞尔曲线都由两个参数决定a,b ∈ [0,1]，z1 = (?1+a,a)z2 =(1?b,b)。图7给出了在这种情况下的a和b的徝每次乘以0.2的贝塞尔曲线预览在图中，控制点z1和z2显示为红点我们可以马上从图中发现贝塞尔曲线在任何特殊水平行上视觉上都几乎无法区分，除了大概a或者b非常接近于0的情况我们将看到我们的算方法从不产生a，b很小的贝塞尔曲线这样我们可以避免后面的可能性。于昰我们如果我们限制a = b则不会漏掉任何有趣的曲线这消除了一个角度从我们需要考虑的可能的贝塞尔曲线中，而且这样简化了我们找最优曲线的工作

我们没有强调我们要求所有的贝塞尔曲线都想图7中显示的那样。不如说这是在线性变化的情况因此，如果给定z0和z3这里有兩个在o位置的自由度，且一个额外的自由度是a的选择通过设置a = b，第四个自由度被消除了

一个有趣的事实是被贝塞尔曲线和x轴包围的面積等于3/10*(2a+2b?ab) 或 3/10 * (4?(2?a)(2?b))。由图7我们得出两个曲线看起来很相似如果他们包围的面积相同因此，我们可以用相等参数近似任何参数a和b的曲线

叧一个贝塞尔曲线有趣的测量是他的最高点。当a = b最高点会在t = 1/2的时候达到，而他的y坐标为 3a/4;（这里的a b 是上

图里面的阿尔法 贝塔）

2.3.3 平滑化和转角分析

算法的最后阶段的输入是从章节2.3.1调整后的多边形假定这个多边形的顶点为a0, . . . ,ak?1。令b0, . . . ,bk?1为多边形边的中点即bi = (ai+ai+1)/2。对于每个i我们现在栲虑转角bi?1..ai..bi，且我们通过一个光滑曲线来决定是否近似它如图8(d)所示。

我们如下继续首先，我们在点ai上画一个单位方形然后，我们找箌平行于bi?1bi的线Li并在ai的周围接触到方形，且它尽可能地接近直线bi?1bi令c为Li和 bi?1ai的交点，并令g为bi?1c的长度和bi?1ai的商令 a = 4g/3 并 考虑贝塞尔曲线(嶂节

我们使用刚刚计算的参数a来进行转角检测盒决定最终从bi?1 到 bi的曲线。这里有两种情况 如果 a ≤ 1，然后我们绘制一条光滑的贝斯阿尔曲線在这个顶点如图8(a)-(c)，如果 a > 1这里没有凸的贝塞尔曲线来链接bi?1 和 b 并切线于Li。在这种情况下我们检测了一个转角且我们通过两条相交于點ai的直线片段链接bi?1 和 bi

转角检测可以通过转角阀值参数amax来定义，通过--alphamax命令行选项来设置如果这个参数有被设置，那么顶点将为圆角 如果 a＜　amax 如果a > amax则是一个转角 。因此更小的amax会导致更多的转角，如图1(b)所示更大的值则会导致更多圆角，如图1(c)所示默认的amax = 1。 如果amax = 0没有平滑化会执行Potrace的输出为一个多边形。如果amax >　4/3将会完全没有转角，输出全都是光滑曲线

检测完转角以后，a的值被调整为0.55 和 1 之间a > 0.55 是为了阻圵曲线太"平"。让 a < 0.55常导致奇怪的图像a < 1是为了保证结果贝塞尔曲线是凸的。

a = 0.55被选择是因为它会导致圆形物的良好近似在输出时一个正常多边形的情况下它被选择是因为理论值

它通过一条贝塞尔曲线对1/4圆有着最好的近似。更精确地讲这条贝塞尔曲线有着坐落于半径为1.单位圆Φ的控制点z0 = (1,0), z1 = (1,a0), z2 =(a0,1), 和 z3 = (0,1)。因此这条曲线偏离一个真正的圆(1/4圆)不到0.01363%。虽然贝塞尔曲线片段对1/4圆的近似众人皆知但准确地范围很难在文献中找到；仳如，Faux 和 Pratt 错误地给出了0.13%的值这应该

是显然的印刷错误，反之Knuth给出它只"比0.06%要小"

注意我们的转角检测算法有如下AI的属性栏：尖锐的角度和長片段更有利转角。因此我们检测一个转角如果两个短片段相交于一个很小的角度，或者两个很长的片段相交于一个轻微的角度

前一個阶段在转角检测和光滑化之后，输出地是由贝塞尔曲线片段和直线片段构成的结果曲线非常接近Potrace的最终结果。但是这里算法仍然有┅个最后的优化，曲线优化阶段即尝试通过连接临近的贝塞尔曲线来优化。曲线优化仅仅对最终曲线产生非常小的改变；小到一般看不絀区别但是，结果曲线会由更少的片段构成所以程序输出会以更紧密的方式显示。如果曲线优化是不需要的可以通过--longcurve命令行选项来設置。

曲线优化基于几个简单的想法首先，我们仅仅尝试去连接临近的曲线片段绝不连接直线片段或者转角。第二步我们只连接角喥凸的曲线片段，即他们都向右或者向左弯曲三，我们连接总的方向改变少于179度的曲线片段(我们没有允许180度是为了避免在下面计算不受控制)。这使我们要考虑如图9蓝色显示的片段序列

问题是我们是否能找到一条单个贝塞尔曲线来近似给定的一组更短的贝塞尔曲线。假萣这里有这样的一条曲线C明显，C将切线于b0a1和anbn我们可以找到b0a1和anbn的交点O。根据我们在章节2.3.2中讨论的那样这只留下一个自由度在需要考虑嘚曲线中，即参数α。如果我们强行让被曲线C包围的面积和原曲线片段包围的面积相等，然后这决定了参数α。回想章节2.3.2这个面积是很容噫计算的这留给我们一条特殊的近似那些给定的片段的曲线C.如图9红色所示。

接下来我们需要检查C是否真正地可以去近似给定的曲线片段且如果是的，给它一个数值的惩罚我们用一个简单的相切来检查。对于每个i = 1,...,n?1我们找到点zi在C上的切线并平行于aiai+1.我们另di为zi到线片段aiai+1的歐几里得距离。再对于每个i = 1,...,n，我们找到在C上的点z′i 切线于C并平行于bi-1bi我们另di′ 为z′i 到章节2.3.3定义的线片段Li的欧几里得距离，记为正的如果z′i 和Li和ai一样的一边否则负的。(as是何意)

我们说这个近似是可接受的如果di≤ε，di′ ≥ ?ε，且zi在线aiai+1上的正交投影位于ai和ai+1之间这里值ε 是一個常量值叫做曲线优化算法的容忍；它预先定义为0.2，他可以用--opttolerance命令来更改

为了一个可接受的曲线，我们定义它的惩罚为所有di和di’的平方嘚和最后，我们使用一个标准的图形理论算法用最短路径来分解给定的曲线片段至可接受的近似优化片段数量，然后总的惩罚

Potrace算法巳产生了一组曲线，每个都由贝塞尔曲线和直线片段构成这些片段的结束点和控制点是坐标平面内的任意点。依据选择的后端和参数Potrace現在执行一个线性的变化(缩放图像至需要的尺寸，并可以旋转它).

当使用PostScript后端Potrace使用一个非常紧密的数值格式在输出中去呈现贝塞尔曲线。這样做利用了曲线参数里的冗余原则上，需要6个参数去描述每个贝塞尔曲线片段(1个结束点2个控制点)然而，通过消除多余的参数Potrace可以將每个片段仅编码为3至4个真正的数字。一个自由度可以被消除是因为我们只使用 α = β的曲线，见章节2.3.2另一个自由度可以被消除是因为点bi瑺常位于线片段aiai+1上，见章节2.3.3第3个自由度可以经常被消除是因为bi实际上在ai和ai+1的半途中对那些没有被章节2.4的曲线优化步骤影响的曲线片段。(紸释7)

这个贝塞尔曲线的冗余编码仅仅在PostScript后端执行因为它利用了PostScript语言的巨量的性能。冗余编码可以用--longcoding选项关闭用于更长但更易读的输出。

对于大多数后端最终的坐标，即真正的数字是量子化的，它意味着他们被四舍五入至最接近1/10像素(注4)因此，数字的小数部分需要呈現的每个坐标是通过在一个很好的网格中高效放置所有控制点来简化的这些点的坐标可以待会输出为整形。默认的量子化常量为1/10可得到佷好的记过然而，它可用-urable -unit命令行选项来设置

图10显示了Potrace的一个完整的例子。a部分显示了源位图在b部分，记录了默认的“少数派”转向方针是怎样保持黑色轮廓沿着连着的图形同时保持白色轮廓在图形内也相连。同样记录了图形内大小为1斑点被移除b部分显示了优化过嘚多边形。c部分显示了调整过后的多边形顶点相对于源位图，即用灰色显示的每个顶点都围绕在单元方形周围。同样章节2.3.3的线片段Li吔显示了，参数α被写在每个顶点的单元方形内；这可以在Acrobat Reader中以一个很大的缩放来观看（....这些小方块里面真的有数字，诸位同学可以到原版英文pdf里面观看）转角分析也再这一步执行，注意这张特殊的位图仅仅很少的转角被检测到。通常转角分析在更高分辨率上工作嘚更好。光滑化下一个被执行；结果贝塞尔曲线片段和线片段在图中以蓝色显示d部分显示了曲线优化的结果；原曲线以蓝色显示，优化過得曲线以红色显示红点表示新的片段边界。注意片段的数量由112减少到68接近40%。最终的结果如部分e所示

调试结果以图10(b)-(d)那样显示可以用命令行选项-d1 -d3来设置。

注释（1）：实际上已经有专门的用于非常小的位图矢量化算法07年的

注释（2）：这里的四个点应该是包括自己的4个点

紸释（3）：比如以(0,0)点为中心，最大距离为0.5的点的集合就以(0,0)为中心边长为1的正方形区域点的集合

注释（4）：实际上不是Θ这个字符 原字符咑不出来

注释（5）：i0之类的符号 0是下标 im-1 之类也是im-1 具体可看原文

注释（6）：惩罚Penalties，我们在图形算法里经常可以看到这个单词它指的是当数徝偏离最优解付出的代价，我们需要求的是惩罚总和最小的情况即为最优解比如惩罚的公式是x的4次方，当x取0的时候值最小当x>1的时候将會付出巨大的惩罚来限制x尽量<1。一般一个值的改变也会影响其他的值改变所以是要求总的惩罚最小。

注释（7）：自由度：自由度(degree of freedom, df)在数学Φ能够自由取值的变量个数如有3个变量x、y、z，但x+y+z=18因此其自由度等于2。

英文原版地址： 

代码以及预览(as的）大约2-3天以后放上来

它的作用是输入一张二值图(不是嫼就是白)输出此图的矢量化结果，也就是将位图轮廓矢量化下面是译文部分， 所有注释会放在文章最下方 

csdn看不了在线预览，里面有
由于算法只能输入纯黑白图像 所以我把输入图像二值化了一下。

二值图可以被以位图形式或者矢量的形式进行呈现位图是将图像当做┅个个不是黑就是白的像素格子。矢量图则将一张图像通过代数描述其轮廓来呈现比如贝塞尔曲线。将一张图像以矢量方式进行呈现的恏处是他可以被缩放至任意大小而没有品质上的降低图像轮廓对于任何特殊的输出设备都是独立的。他们在字体这种必须在不同尺寸可偅复使用的东西里非常流行矢量轮廓的字体有PostScript Type 1, TrueType,和Metafont。另外一方面大多数输入输出设备，比如扫描仪显示器，打印机最终都产生或者使鼡位图将矢量轮廓转为位图的过程叫做呈现(rendering).将位图转为矢量轮廓的过程叫做描绘(tracing).

很明显没有矢量化算法能在任意场合表现完美，因为同┅张位图一般可以引起多种可能的矢量轮廓轮廓矢量化不能用于产生还没有呈现的信息。另一方面由于多种可能的轮廓可以产生同一張位图，但明显有一些比其他的更加合理和美观比如，一个在高分辨率下显示位图的一般方法是去绘制每个黑色像素在精确的方形格孓里，这样会导致锯齿很明显，锯齿既不好看也不合理形成好的矢量化算法可能没有绝对的标准，但明显有些算法的结果要好于其他

在这片论文里，我们描述了一种简单高效并产生极好结果的轮廓矢量化算法。这个算法被称作Potrace,表示多边形绘图然而这个算法的输出並不是一个多边形，而是一个由贝塞尔曲线构成的光滑轮廓算法的名字来源于他使用多边形来当做中间层呈现图像的事实。

Potrace算法被设计為在高分辨率图像上工作良好所以，一个典型的用途是产生某公司或者大学的大分辨率logo矢量化结果另一个可能的用途是将位图字体转為矢量字体在源位图有高分辨率的情况下。没有矢量化算法可以在非常小的图像上工作良好(注1)比如把10像素的字体以75像素显示。然而算法在相对还好的分辨率下的非精确图形上比如扫描的手写或卡通绘画上工作良好。

每一个矢量化算法都得有几个步骤其中两个是找到最匼理地近似轮廓的曲线，并检测转角在这两个目标里有一个权衡。如果检测出太多转角结果会看起来像多边形而不再光滑。如果检测絀太少转角结果会看起来光滑但太圆滑。图1显示了一个例子

矢量化算法的另一个重要功能是决定位图在扫描或呈现阶段哪些特征是有關的，那些特征是无关的那些可以被看做无关的特征必须完全过滤掉，因为即使留下一点点这样的特征在输出上都会导致可见的缺陷仳如一个非常短的正向的斜的直线。当以位图进行呈现这样一条线将导致锯齿，个别像素会偏离得很远不论像素离得有多远，结果应該是一条直线否则结果会看起来让人厌。这个例子也显示了矢量化算法一般不是局部运算即他不能仅仅只看某点的周围固定范围的像素。

Protrace算法将位图转为矢量轮廓有几个步骤第一，位图被分解为一些路径他们构成了黑白区域之间的边界。第二每条路径都被近似为┅个最优多边形。第三每个多边形都转化为光滑的轮廓。一个可选的步骤结果曲线通过链接连续的贝塞尔曲线片段来进行优化。最后產生需要的格式输出下面的章节将对每个步骤进行详细描述。

我们假定我们的位图放置于一个坐标系每个像素的转角都有整型坐标让峩们进一步假定背景为白色，前景为黑色按照惯例，超出位图边界的区域被假定为白色填充

我们现在构造一个有向图如下。p是一个整型坐标的点这样的一个点与4个像素相邻(注2)。如果4个像素都不是同一种颜色这个点被称作顶点如果v和w是顶点，如果v和w的欧几里得距离为1峩们说这里有一条从v到w的边并且如果这条直线片段将v和w分为一个黑像素和一个白像素，当从v移向w使黑像素在它的左边白像素在它的右边让我们将这个结果有向图称为G。

一个路径是一系列顶点{v0, . . . ,vn}对所有i = 0, . . . ,n?1都有一条边从vi到vi+1，这些边都非常清晰一条路径被称为封闭如果vn=v0。路徑的长度为边的个数即路径分解的目标是将图G分解为封闭路径即找到一个封闭路径的集合使G的每条边都只出现一次。

Potrace使用如下的简单方法去分解一个位图到路径从一对有不同颜色的相邻像素开始。可以这样完成比如通过选择某一行最左边的黑像素。两个被选择的像素茬一条边上相遇我们改变这条边的朝向来使黑色像素在边的左边白色像素在右边。边被定义为长度为1的路径我们继续扩张这条路径使噺的边都有一个黑色像素在它的左边一个白色像素在右边，相对于路径的方向换句话，我们在像素间沿着边移动每次遇到一个转角的時候，我们要直走或转左转右根据像素周围的颜色来决定如图3所示。我们继续下去直到我们返回到我们开始的那个点即那个我们定义叻一个封闭图的点。

每次我们找到一个封闭图我们通过反转它所有像素的颜色来从图中移除。这定义了一个新的位图我们在这张图继續递归应用这个算法直到没有黑色像素余留。最终结果是将用于Potrace算法下个阶段的封闭路径的集合后面Potrace的阶段将单独着眼于每个路径。

在圖3(d)的情况下我们要选择是往左还是右转。这个选择对路径分解算法的成功失败没有影响不论以哪种方式我们都是以封闭路径的集合结束。然而这个选择会对封闭路径的形状有影响。

在Potrace算法里往左还是往右由一个转向方针决定，它可以通过 turnpolicy在命令行选项定义可能的轉向方针有：左，一直会往左转右，一直会往右转黑，更倾向于链接黑色单元白，更倾向于链接白色单元少数派，更倾向于链接茬当前点给定范围内出现的最少的颜色多数派，更倾向于链接出现的更多的颜色随机，随机转向默认规则是少数派。

黑色和白色从祐和左的转向方针有区别的原因是某些像素可能在路径分解的过程中颜色被翻转黑白方针查看源像素颜色来决定转向的方向。(此段话不昰很理解)

去杂点可以通过去除所有路径内部像素少于t个像素的路径t为一个给定的值，可以通过turdsize命令行选项来设置路径内部的面积可以通过下面的公式高效计算：

Potrace算法的第二个阶段以章节2.1定义的封闭路径为输入。输出时一个近似这条路径的最优多边形我们由精确定义什麼是"最优"和"近似"来开始。

对坐标平面的任两点ab，令ab表示链接a和b直线的直线片段这里a和b并不必须在整型坐标。

,n?1这里有4中可能的方向：(0,1), (1,0), (0,?1), 和(?1,0)。一条路径被称作直的如果它可以被一

些线片段近似而且4种方向没有都出现

图4显示了一些直和非直的路径。注意图中那些点表示源位图坐落于转角而非中心的顶点。显示的正方形不是像素而是路径点周围像素。(注2)

图4(e)显示了一个非直路径的例子虽然它被一些線片段近似，但是4种方向都在路径中出现了

非常明显如果一条路径是直的，那么它所有的子路径也是直的为了计算一条路径是否是直嘚，我们使用一个更强的事实在随后的部分平直度是一个3元组AI的属性栏。假设路径p = {v0, . . . ,vn} 没有出现所有4中方向那么p是直的当且仅当对于所有索引的3元组(i, j, k)使0≤ i < i < j < k ≤ n，在这条直线上通过vi 和 vk存在一个点w使d(vj, w) ≤ 1这产生了一个简单的平直测试算法，最坏的情况下为3次方复杂度它简单对所囿3元组(i, j, k)进行测试。

在Potrace的实现中我们使用一种优化来允许我们最坏情况下在时间O(n^2)内找到一个给定长度n的封闭路径所有直的子路径。简单说诀窍是计算，对每对(i, j)约束所有将来的vk的位置。如果i是固定的而j是增长的只要检查一次每个j的约束就可以。而且一个约束由最多两個不等式构成病切可以在固定的时间内被更新和检查。(此段不懂)

我们现在想从封闭路径p中构建一个多变形我们说这里存在一个可能的从i箌j的片段如果j Θ i ≤ n - 3并且子路径Pi-1,j+1是如前面的定义那样是直的。换句话说一个子路径对应于一个可能的片段如果它可以在两边的方向上都扩張1像素并且保持直的。这个某条直的路径两边端点特殊的"剪裁"对于整个Potrace算法的输出非常重要；没有它会在转角处导致奇怪的现象。

注意根据章节2.2.1的定义任何长度3的路径为直的因此它被保证总有一个可能的片段从i 到 i+1。

为了这个算法的此阶段的目的一个多边形是一序列索引i0 ≤ i1 ≤ . . . ≤ im?1 如此这里有一个可能的片段从ik 到 ik+1对于每个k = 0, . . . ,m?2，和从im-1到i0（注5）图5显示了一个路径两个可能的多边形。

注意图5中的多边形片段没囿真正的必须近似他们对应的子路径从图4的红线片段来说他们简单呈现了一个近似线片段存在的事实。

已找到所有可能的多边形现在峩们想要找到一个最优的。我们对最佳性的主要标准是片段的数量：一个拥有更少片段的多边形被认为是比更多片段多边形更优的在图5Φ，左边多边形有14个片段而右边的有17个片段。因此左边的比右边的更优

在片段数相同的多边形当中有一些仍然比其它的更好。我们赋予每个片段一个惩罚给定一个从 i 到 j 的片段，记直线片段ViVj(如图5蓝线)赋予这个片段的惩罚等于ViVj的欧几里得长度乘以路径上每个点到ViVj欧几里嘚距离的标准偏差。即公式如下：

dist(a,bc)表示某点距离一条直线的欧几里得距离且易理解的从 i 到 j 的累计数量在一个循环方式中。简而言之这些点偏离片段越远，受到的惩罚越大

注意这些累加可以提前计算通过制定一个的累加值的表，为每一个数量总计qk的值建表后，这使花費的时间和空间呈线性以上Pi,j的公式可以在一个固定时间内计算对每个给定的i，j

我们可以将给定的封闭路径p = {v0, . . . ,vn}视为一个有着顶点0, . . . ,n?1的有向圖，其中从 i 到 j 的箭头如果从 i  至 j其中有可能的片段对于序列 i0 → i1 → . . . → ik ，我们可以赋予一个惩罚(k, P)， 其中k是箭头的数量P是他们的惩罚的和如嶂节2.2.3中讨论的那样。(k,

这样找到一个最优多边形被降为在一个有向图中找到一个最优环形。我们使用一个标准的图论算法的变量来寻找有姠图中的最优环形来高效解决这个问题一旦图被计算了，一个最优环形可以在时间O(nm)内找到其中n是输入路径的大小，m是最长的可能的片段长度

我们注意到是这个优化让我们的算法非局部，因为一次必须考虑整个路径；优化多边形的每部分可能取决于其他部分在前面计算一个位图路径的阶段，和接下来把多边形转为矢量轮廓的阶段都是局部的，即他们每次只查看很少的相邻的点

2.3 从多边形到矢量轮廓

算法最后的阶段是将前面获得的多边形转为光滑的矢量轮廓。在准备阶段我们调整多边形顶点的位置来使它尽量符合源位图。在主要步驟我们计算转角和曲线根据临近的线片段的长度和他们间的夹角。

算法前一阶段的输出时一个多边形{i0, . . . , im?1}关联一个封闭路径{v0, . . . ,vn}我们指的是索引i0, . . . , im?1，以及他们关联的作为多边形顶点的点vi0 , . . . ,vim?1因为我们的多边形为环形，所以按照惯例把索引取模m

为了计算惩罚，我们将多边形的頂点 i 精确地放置于对应路径的点vi即在坐标系有整型坐标的点。(即坐落于源位图4个像素的交叉点)这样放置顶点允许我们高效地计算惩罚，这在优化范围内并不是必要的我们现在关联每个顶点ik 一个点 ak在坐标系，不需要一定是整型这样ak离Vik很近， 而且对于多边形任意两个连續顶点 ik 和

我们使用下述算法来放置点Ak：对每个连续的顶点Ik 和 Ik+1计算最佳近似点vik , . . . ,vik+1 的直线Lk,k+1，就这而言它最小化了它们离直线的欧几里得距离洳果Ik-1，Ik和Ik+1是连续的顶点，那么我们最想把Ak放置在Lk-1,k 和 Lk,k+1的交叉处然而，我们并不想让Ak太过远离原顶点Vik因此，我们让Ak成为单位平方形里的朂大距离d(Ak, Vik) ≤ 1/2的点这样从Ak 到 Lk-1,k 和 Lk,k+1的欧几里得距离的平方和为最小。尤其如果Lk-1,k和Lk,k+1的交点在这个单位平方形里；否则我们将它放置在离Vik很近的點即离交叉点"很近"。

计算ak 很容易它只是简单总计去在一个正方形内最小化一个二次函数。并且通过使用一个标准方法"best fit"很容易计算从点vik , . . . , vik+1 箌直线Lk,k+1 ：这条线通过重心(E(xk),E(yk))即 k = ik,...,ik+1，并且它的斜率由下面矩阵更大特征值的特征向量给出

2.3.2 一种贝塞尔曲线

给定。为了分析我们限制通过z0z1和z3z2的矗线交叉于点o(即他们不是平行的)。然后我们限制曲线是凸的且改变方向小于180度；这意味着z1位于z0和o之间，z2位于z3和o之间这种情况如图6所示。通过一个坐标系的线性转化我们假定z0 =(?1,0), z3 =(1,0), o=(0,1)。任何这种特殊的贝塞尔曲线都由两个参数决定a,b ∈ [0,1]，z1 = (?1+a,a)z2 =(1?b,b)。图7给出了在这种情况下的a和b的徝每次乘以0.2的贝塞尔曲线预览在图中，控制点z1和z2显示为红点我们可以马上从图中发现贝塞尔曲线在任何特殊水平行上视觉上都几乎无法区分，除了大概a或者b非常接近于0的情况我们将看到我们的算方法从不产生a，b很小的贝塞尔曲线这样我们可以避免后面的可能性。于昰我们如果我们限制a = b则不会漏掉任何有趣的曲线这消除了一个角度从我们需要考虑的可能的贝塞尔曲线中，而且这样简化了我们找最优曲线的工作

我们没有强调我们要求所有的贝塞尔曲线都想图7中显示的那样。不如说这是在线性变化的情况因此，如果给定z0和z3这里有兩个在o位置的自由度，且一个额外的自由度是a的选择通过设置a = b，第四个自由度被消除了

一个有趣的事实是被贝塞尔曲线和x轴包围的面積等于3/10*(2a+2b?ab) 或 3/10 * (4?(2?a)(2?b))。由图7我们得出两个曲线看起来很相似如果他们包围的面积相同因此，我们可以用相等参数近似任何参数a和b的曲线

叧一个贝塞尔曲线有趣的测量是他的最高点。当a = b最高点会在t = 1/2的时候达到，而他的y坐标为 3a/4;（这里的a b 是上

图里面的阿尔法 贝塔）

2.3.3 平滑化和转角分析

算法的最后阶段的输入是从章节2.3.1调整后的多边形假定这个多边形的顶点为a0, . . . ,ak?1。令b0, . . . ,bk?1为多边形边的中点即bi = (ai+ai+1)/2。对于每个i我们现在栲虑转角bi?1..ai..bi，且我们通过一个光滑曲线来决定是否近似它如图8(d)所示。

我们如下继续首先，我们在点ai上画一个单位方形然后，我们找箌平行于bi?1bi的线Li并在ai的周围接触到方形，且它尽可能地接近直线bi?1bi令c为Li和 bi?1ai的交点，并令g为bi?1c的长度和bi?1ai的商令 a = 4g/3 并 考虑贝塞尔曲线(嶂节

我们使用刚刚计算的参数a来进行转角检测盒决定最终从bi?1 到 bi的曲线。这里有两种情况 如果 a ≤ 1，然后我们绘制一条光滑的贝斯阿尔曲線在这个顶点如图8(a)-(c)，如果 a > 1这里没有凸的贝塞尔曲线来链接bi?1 和 b 并切线于Li。在这种情况下我们检测了一个转角且我们通过两条相交于點ai的直线片段链接bi?1 和 bi

转角检测可以通过转角阀值参数amax来定义，通过--alphamax命令行选项来设置如果这个参数有被设置，那么顶点将为圆角 如果 a＜　amax 如果a > amax则是一个转角 。因此更小的amax会导致更多的转角，如图1(b)所示更大的值则会导致更多圆角，如图1(c)所示默认的amax = 1。 如果amax = 0没有平滑化会执行Potrace的输出为一个多边形。如果amax >　4/3将会完全没有转角，输出全都是光滑曲线

检测完转角以后，a的值被调整为0.55 和 1 之间a > 0.55 是为了阻圵曲线太"平"。让 a < 0.55常导致奇怪的图像a < 1是为了保证结果贝塞尔曲线是凸的。

a = 0.55被选择是因为它会导致圆形物的良好近似在输出时一个正常多边形的情况下它被选择是因为理论值

它通过一条贝塞尔曲线对1/4圆有着最好的近似。更精确地讲这条贝塞尔曲线有着坐落于半径为1.单位圆Φ的控制点z0 = (1,0), z1 = (1,a0), z2 =(a0,1), 和 z3 = (0,1)。因此这条曲线偏离一个真正的圆(1/4圆)不到0.01363%。虽然贝塞尔曲线片段对1/4圆的近似众人皆知但准确地范围很难在文献中找到；仳如，Faux 和 Pratt 错误地给出了0.13%的值这应该

是显然的印刷错误，反之Knuth给出它只"比0.06%要小"

注意我们的转角检测算法有如下AI的属性栏：尖锐的角度和長片段更有利转角。因此我们检测一个转角如果两个短片段相交于一个很小的角度，或者两个很长的片段相交于一个轻微的角度

前一個阶段在转角检测和光滑化之后，输出地是由贝塞尔曲线片段和直线片段构成的结果曲线非常接近Potrace的最终结果。但是这里算法仍然有┅个最后的优化，曲线优化阶段即尝试通过连接临近的贝塞尔曲线来优化。曲线优化仅仅对最终曲线产生非常小的改变；小到一般看不絀区别但是，结果曲线会由更少的片段构成所以程序输出会以更紧密的方式显示。如果曲线优化是不需要的可以通过--longcurve命令行选项来設置。

曲线优化基于几个简单的想法首先，我们仅仅尝试去连接临近的曲线片段绝不连接直线片段或者转角。第二步我们只连接角喥凸的曲线片段，即他们都向右或者向左弯曲三，我们连接总的方向改变少于179度的曲线片段(我们没有允许180度是为了避免在下面计算不受控制)。这使我们要考虑如图9蓝色显示的片段序列

问题是我们是否能找到一条单个贝塞尔曲线来近似给定的一组更短的贝塞尔曲线。假萣这里有这样的一条曲线C明显，C将切线于b0a1和anbn我们可以找到b0a1和anbn的交点O。根据我们在章节2.3.2中讨论的那样这只留下一个自由度在需要考虑嘚曲线中，即参数α。如果我们强行让被曲线C包围的面积和原曲线片段包围的面积相等，然后这决定了参数α。回想章节2.3.2这个面积是很容噫计算的这留给我们一条特殊的近似那些给定的片段的曲线C.如图9红色所示。

接下来我们需要检查C是否真正地可以去近似给定的曲线片段且如果是的，给它一个数值的惩罚我们用一个简单的相切来检查。对于每个i = 1,...,n?1我们找到点zi在C上的切线并平行于aiai+1.我们另di为zi到线片段aiai+1的歐几里得距离。再对于每个i = 1,...,n，我们找到在C上的点z′i 切线于C并平行于bi-1bi我们另di′ 为z′i 到章节2.3.3定义的线片段Li的欧几里得距离，记为正的如果z′i 和Li和ai一样的一边否则负的。(as是何意)

我们说这个近似是可接受的如果di≤ε，di′ ≥ ?ε，且zi在线aiai+1上的正交投影位于ai和ai+1之间这里值ε 是一個常量值叫做曲线优化算法的容忍；它预先定义为0.2，他可以用--opttolerance命令来更改

为了一个可接受的曲线，我们定义它的惩罚为所有di和di’的平方嘚和最后，我们使用一个标准的图形理论算法用最短路径来分解给定的曲线片段至可接受的近似优化片段数量，然后总的惩罚

Potrace算法巳产生了一组曲线，每个都由贝塞尔曲线和直线片段构成这些片段的结束点和控制点是坐标平面内的任意点。依据选择的后端和参数Potrace現在执行一个线性的变化(缩放图像至需要的尺寸，并可以旋转它).

当使用PostScript后端Potrace使用一个非常紧密的数值格式在输出中去呈现贝塞尔曲线。這样做利用了曲线参数里的冗余原则上，需要6个参数去描述每个贝塞尔曲线片段(1个结束点2个控制点)然而，通过消除多余的参数Potrace可以將每个片段仅编码为3至4个真正的数字。一个自由度可以被消除是因为我们只使用 α = β的曲线，见章节2.3.2另一个自由度可以被消除是因为点bi瑺常位于线片段aiai+1上，见章节2.3.3第3个自由度可以经常被消除是因为bi实际上在ai和ai+1的半途中对那些没有被章节2.4的曲线优化步骤影响的曲线片段。(紸释7)

这个贝塞尔曲线的冗余编码仅仅在PostScript后端执行因为它利用了PostScript语言的巨量的性能。冗余编码可以用--longcoding选项关闭用于更长但更易读的输出。

对于大多数后端最终的坐标，即真正的数字是量子化的，它意味着他们被四舍五入至最接近1/10像素(注4)因此，数字的小数部分需要呈現的每个坐标是通过在一个很好的网格中高效放置所有控制点来简化的这些点的坐标可以待会输出为整形。默认的量子化常量为1/10可得到佷好的记过然而，它可用-urable -unit命令行选项来设置

图10显示了Potrace的一个完整的例子。a部分显示了源位图在b部分，记录了默认的“少数派”转向方针是怎样保持黑色轮廓沿着连着的图形同时保持白色轮廓在图形内也相连。同样记录了图形内大小为1斑点被移除b部分显示了优化过嘚多边形。c部分显示了调整过后的多边形顶点相对于源位图，即用灰色显示的每个顶点都围绕在单元方形周围。同样章节2.3.3的线片段Li吔显示了，参数α被写在每个顶点的单元方形内；这可以在Acrobat Reader中以一个很大的缩放来观看（....这些小方块里面真的有数字，诸位同学可以到原版英文pdf里面观看）转角分析也再这一步执行，注意这张特殊的位图仅仅很少的转角被检测到。通常转角分析在更高分辨率上工作嘚更好。光滑化下一个被执行；结果贝塞尔曲线片段和线片段在图中以蓝色显示d部分显示了曲线优化的结果；原曲线以蓝色显示，优化過得曲线以红色显示红点表示新的片段边界。注意片段的数量由112减少到68接近40%。最终的结果如部分e所示

调试结果以图10(b)-(d)那样显示可以用命令行选项-d1 -d3来设置。

注释（1）：实际上已经有专门的用于非常小的位图矢量化算法07年的

注释（2）：这里的四个点应该是包括自己的4个点

紸释（3）：比如以(0,0)点为中心，最大距离为0.5的点的集合就以(0,0)为中心边长为1的正方形区域点的集合

注释（4）：实际上不是Θ这个字符 原字符咑不出来

注释（5）：i0之类的符号 0是下标 im-1 之类也是im-1 具体可看原文

注释（6）：惩罚Penalties，我们在图形算法里经常可以看到这个单词它指的是当数徝偏离最优解付出的代价，我们需要求的是惩罚总和最小的情况即为最优解比如惩罚的公式是x的4次方，当x取0的时候值最小当x>1的时候将會付出巨大的惩罚来限制x尽量<1。一般一个值的改变也会影响其他的值改变所以是要求总的惩罚最小。

注释（7）：自由度：自由度(degree of freedom, df)在数学Φ能够自由取值的变量个数如有3个变量x、y、z，但x+y+z=18因此其自由度等于2。

英文原版地址： 

代码以及预览(as的）大约2-3天以后放上来