简单图像矢量化

矢量化是指当你拍摄一些“我的世界”风格的光栅图像，并从中制作一张清晰的矢量图片的时候。

当你想把卫星照片变成地图时，它特别有用。或者，如果您想扫描一些蓝图并将其转换为CAD模型。或者，如果您想重新发布一个旧游戏，但您不想从头开始重新绘制所有的艺术作品。

我要告诉你的算法与所有这些事情没有任何关系。它是一种基本的矢量化技术，在最初的形式下，在行业中几乎没有应用。

从好的方面来说，它很好地说明了这种方法。它展示了双线性插值、梯度下降和参数样条线如何协同工作来解决真实世界的问题。至少，它让学习所有这些东西变得更有说服力了。

光栅图像本质上是一张由物体组成的矩形桌子。如果它是全彩色RGB，那么它就是彩色像素表。颜色像素是8位整数值的三元组，其中每个值表示红色、绿色和蓝色的量。

诸如从计算机断层扫描获得的医学图像通常是12位或16位整数的表格。它不是真正的颜色，因为这些值来自不可见的X射线辐射，但它们被称为灰度值。

卫星图像可能有很多频道。除了可见幽灵的颜色外，它们还可能含有紫外线和红外线的光度。通道可以用整数或浮点值表示。

从技术上讲，我们已经可以相当容易地将其转化为矢量。让我们就某个阈值达成一致，并标记所有值超过该阈值的像素的轮廓。

嗯，这很简单，但这不是我们想要的。我们要的是曲线，而不是拐角。为此，我们必须让我们的形象不那么拐弯抹角。

让我们假设我们的形象不是一张价值表。让我们假设我们只知道像素中心的值，我们必须以某种方式猜测它们之间的值。

这称为插值。最简单的情况是最近邻插值法，对于图像上的每个点，该值都是最近像素中心的值。但这只会把它变回一张桌子。

更先进一点的是双线性插值。该值是四个邻接值的线性和。看起来是这样的。

//带越界检查的像素值函数Pixel_in(象素，i，j){if(i&>；=Pixels.length)返回Pixel_in(象素，Pixels.length-1，j)；if(i<；0)返回Pixel_in(象素，0，j)；IF(j&>；=象素[0].length)返回Pixel_in(象素，i，象素[0].length-1)；IF(j<；0)返回Pixel_in(象素，i，0)；返回象素[i][j]；}//线性插值函数value_in(像素，x，y){var j=Math.Floor(x-0.5)；var tj=x-0.5-j；var i=Math.Floor(y-0.5)；var ti=y-0.5-i；返回Pixel_in(像素，i，j)*(1-ti)*(1-tj)+Pixel_in(像素，i，j+1)*(1-ti)*(Tj)+Pixel_in(像素，i+1，j+1)*(Ti)*(Tj)+Pixel_in(像素，i+1，j)*(Ti)*(Ti)*(1-Tj)；}。

如果我们把插值值达到阈值的像素变暗，我们就会得到某种轮廓。

还有其他方法。很多。但是线性插值很好地解决了拐角边界问题。尽管如此，我们看到的边界仅仅是某个门槛的边界。它还不是矢量表示法。

我们可以借鉴最简单的平滑等高线算法的思想。我们将从源像素建立一个初始边界，然后我们将使用线性插值图像来找到放置每个轮廓点的最佳位置，这样图像值将达到阈值。

当你有一个距离场时，这就很容易了。距离场是指对于空间中的任意点，您可以判断它离所需曲面的距离有多远。它基本上是一个从空间点到距离的函数。

你取它的梯度，取你的值和阈值之间的差值。因为它是距离字段，所以值差异正好是您应该移动点的距离。而梯度是完全相反的方向。你只需求逆、乘、加 - ，你就在那里了。

不幸的是，我们没有距离场。我们有一个连续的图像，它只与一个相似。

但这一原则仍然有效。如果您逆着渐变进行遍历，则会更接近阈值。差异越大，你就必须走得越远。只是你不会总是一次尝试就能做到。

//梯度函数梯度(像素，x，y){const EPS=1e-5；return[(value_in(像素，x+EPS，y)-value_in(像素，x，y))/EPS，(value_in(像素，x，y+EPS)-value_in(像素，x，y))/EPS]；}//如果value_in是距离函数GRADER_SHIFT(像素，阈值，x，y){var g=GRADER(像素，x，y)；var g_Norm=Math.sqrt(g[0]*g[0]+g[1]*g[1])；var d=Threshold-Value_in(像素，x，y)；返回[g[0]*d/g_NORM/g_NOROM，g[1]*d/g_NORM/g_NORM]；//如果value_in是距离函数，则返回[g[0]*d/g_NORM/g_NORM，g[1]*d/g_NORM/g_NORM]；}//使一个点更接近阈值隔离函数fit_point_Better(像素，阈值，点){const ok_error=1/255；if(Math.abs(value_in(像素，点[0]，点[1])-阈值)<；ok_error)返回点；gs=GRADER_SHIFT(像素，阈值，点[0]，点[1])var new_point=[point[0]+gs[0]，point[1]+gs[1]]；返回FIT_POINT_BETER(像素，阈值，NEW_POINT)；}。

我们将根据渐变移动轮廓点，直到我们足够接近阈值。

要使轮廓线光滑，只需将每条直线段变成一条参数三次曲线即可。

这听起来可能比实际情况复杂得多。一条参数三次曲线就是一对多项式。如果在这些点上有点和偏导数，就可以从这对线性系统中获得它们的系数：

Px(T1)'；=3aXt12+2bxt1+c=dx1/dtpx(T1)=axt13+bxt12+cxt1+d=x1px(T2)=axt23+bxt22+cxt2+d=x2px(T2)'；=3axt2+2bxt2+c=dx2/dtPy(T1)'；=3a yt 1 2+2b yt 1+c=dy 1/dt Py(T 1)=a yt 13+b yt 12+c yt 1+d=y 1 Py(T 2)=a yt 23+b yt 22+c+d=y 2 Py(T 2)'；=3a yt 22+2b yt 2+c=dy 2/dt。

更重要的是，由于我们可以选择参数范围，因此可以将其设置为[0..1]。这极大地简化了我们的系统，使其非常容易解决。

下面是从两对点和切值生成一个多项式系数数组的函数。

//特定于[0..1]参数化样条函数SPLINE_FOR(p1，p1d，p2，p2d){//A=[//[1，0，0，0]，//[0，1，0，0]，//[1，1，1，1]，//[0，1，2，3]]；//B=[p1，p1d，p2，p2d]return[p1，p1d，3*p2-p2d-3*p1-2*p1d，p2d+p1d-2*p2+2*p1]；}。

//多项式函数多项式_in_t(A，t){var pt=0.0；for(var i=0；i<；A.length；++i){pt+=A[i]*Math.pow(x，i)；}返回pt；}。

所以对于每条有切线的线段，我们可以做一个参数多项式。不过，有一个问题。我们没有切线。

我们有梯度，它与切线正交，但每个点都有两条可能的切线。切线可以从渐变向左或向右。

但这是可以解决的。让我们选择我们喜欢的方向，并保持一致。

让最初来自水平方向线段的曲线始终具有DX>；0的两条切线。而那些来自垂直方向的线段，将具有dy>；0。

让我们把向量化分成两部分。首先，我们将从像素中获取每个线段的点和切线。然后我们将把它全部变成多项式样条。

函数Turn_Pixels_Into_Points_and_Tangents(像素，阈值){var Points=[]；var Tangents=[]；//"；水平"；块(var i=0；i<；=Pixels.length；i+=1){var old_point=[]；var old_Tangent=[]；for(var j=0；j<；=像素[0].length；J+=1){//如果右、左、上、下四个像素有符号变化，//这里应该有样条线var sign_change_on_the_right=(Pixel_in(像素，i-1，j+0)-阈值)*(Pixel_in(像素，i+0，j+0)-阈值)<；0；Var Sign_Change_On_the_Left=(Pixel_in(像素，i-1，j-1)-阈值)*(Pixel_in(像素，i+0，j-1)-阈值)<；0；var sign_change_on_the_Bottom=(Pixel_in(像素，i+0，j-1)-阈值)*(Pixel_in(像素，i+0，j+0)-阈值)<；0；Var sign_change_on_the_top=(Pixel_in(像素，i-1，j-1)-阈值)*(Pixel_in(像素，i-1，j+0)-阈值)<；0；if(sign_change_on_the_right||sign_change_on_the_Left){//拟合阈值等值线上的点var point=fit_point_Better(像素，阈值，[j，i])；var g=渐变(像素，点[0]，点[1])；//我们希望我们的切线对于水平段是X正的var Tangent=g[1]>；=0？[g[1]，-g[0]]：[-g[1]，g[0]]；//这是一个T或X交叉点，如果(Sign_Change_On_the_Left+Sign_Change_On_the_Right+Sign_Change_On_the_Bottom>；2)Tangent=[0，0.]；//如果(Sign_Change_On_the_Left&Amp；)存在一个(Sign_Change_On_the_Left&Amp；)切线=[0，0.]；//这是T或X交叉点，切线是不明确的。&；old_point){points.ush([old_point，point])；Tangents.ush([old_Tangent，Tangent])；}//如果(Sign_Change_On_The_Right){old_point=point；old_Tangent=Tangent；}//"；(var j=0；j<；=像素[0].length；j+=1){var old_point=[]；Var old_Tangent=[]；for(var i=0；i<；=picels.length；i+=1){var sign_change_on_the_right=(Pixel_in(像素，i-1，j+0)-阈值)*(Pixel_in(像素，i+0，j+0)-阈值)<；0；Var Sign_Change_On_the_Left=(Pixel_in(像素，i-1，j-1)-阈值)*(Pixel_in(像素，i+0，j-1)-阈值)<；0；var sign_change_on_the_Bottom=(Pixel_in(像素，i+0，j-1)-阈值)*(Pixel_in(像素，i+0，j+0)-阈值)<；0；Var sign_change_on_the_top=(Pixel_in(像素，i-1，j-1)-阈值)*(Pixel_in(像素，i-1，j+0)-阈值)<；0；if(sign_change_on_the_Bottom||sign_change_on_the_top){var point=fit_point_Better(像素，阈值，[j，i])；var g=渐变(像素，点[0]，点[1])；var切线=g[0]<；0？[g[1]，-g[0]]：[-g[1]，g[0]]；if(sign_change_on_the_Left+sign_change_on_the_right+sign_change_on_the_Bottom>；2)切线=[0，0.]；if(sign_change_on_the_top&；&；old_point){points.ush([old_point，point])；Tangents.ush([old_Tangent，Tangent])；}if(Sign_Change_On_The_Bottom){old_point=point；old_Tangent=Tangent；}return[点，切线]；}。

函数turn_points_and_tangents_into_splines(points_and_tangents){变量样条=[]；变量POINTS=POINTS_AND_TENGNTS[0]；VAR TENTINTS=POINTS_AND_TENTINTS[1]；FOR(var i=0；i<；points.length；++i){var px=SPLINE_FOR(Points[i][0][0]，Tangents[i][0][0]，Points[i][1][0]，Tangents[i][1][0])；Var Py=SPLINE_FOR(点[i][0][1]，切线[i][0][1]，点[i][1][1]，切线[i][1][1])；样条线.推([px，Py])；}返回样条曲线}。

此拆分对于算法不是必需的，但它使编辑图像和样条线表示中的模型成为可能。

现在，当我们有了算法后，让我们看看它在实践中是如何工作的。让从PGM导入灰度图像，将其转换为样条线，对其进行编辑，然后将其导出为SVG。

PGM是一种单通道ASCII图像格式。可以在GIMP或任何其他光栅图像编辑器中生成PGM文件。

P216 162550 0 0 0 77 125 38 0 0 0 00 120 255 254203 144 96 3 0 0 0 00 34 253 255 255 255 230 154 94 8 0 0 00 0 196 255 255 255 252 241 139 83 6 0 00 0 149 255 255 255 250 213 80 00 0 98 255 255 255 224 58 00 0 2 224 255 255 255 242 152 4。0 00 0 0 145 255 255 255 154 1 0 00 0 0 0 82 251 255 255 255 253 156 1 0 00 0 0 6 237 255 255 255 3 00 0 0 149 255 243 149 252 255 255 240 21 00 0 0 69 249 255 152 1 150 252 255 238 71 0 00 0 0 0 211 224 4 0 1 137 240 86 0 0 00 0 0 0 73 57 0 0 2 20 0 0 00 0 0 0

导入图像时，我们可以逐个像素编辑源图像，也可以移动样条点和切线。单击画布以增加像素的亮度。单击按住Shift键可减小该值。请注意，在本例中，图像编辑覆盖矢量。

当您对样条线感到满意时，可以将其导出为SVG。在本例中，仅支持大纲。没有填充物，没有着色。

你不必输出多项式。SVG支持Bézier曲线，与三次多项式基本相同。只是你写下的不是系数，而是控制点。

第一个点是样条曲线的起点。第二个是第一个点与切向量的三分之一之和。第三个是样条曲线的终点和第二条切线的三分之一的减去。第四个是样条曲线的终点。

导出函数的代码，就像这里提到的所有代码(包括视觉效果)一样，可以在Github上找到。

该算法展示了双线性插值、多项式近似、微分分析和迭代算法如何协同工作来解决实际问题。

我希望这个页面不仅能满足人们的好奇心，还能帮助人们在学习这些东西的同时保持灵感。根据我的经验，我知道基础微积分虽然不比交通规则复杂，但特别难学，因为你不会马上看到应用程序。你学习级数、极限、导数、积分，原因是什么？如何将这些知识转化为有用的东西呢？