内容感知图像在JavaScript中调整大小

已经有许多关于接缝雕刻算法的伟大文章，但我无法抵制探索这种优雅，强大，更简单的算法的诱惑，并用它写下我的个人经历。引起了我注意的另一个点（作为JavaScript-Algorithms Repo的创造者）是动态编程（DP）方法可能会顺利地应用于解决它。而且，如果你＆＃39;像我一样，仍然在你的＆＃34;学习算法＆＃34;旅程，这种算法解决方案可以丰富您的个人DP阿森纳。

为您提供交互式内容感知的Resizer，以便您可以使用调整您自己的图像大小进行播放

解释实现算法的动态编程方法（我们＆＃39; ll使用typescript）

在改变图像比例方面，可以应用内容感知图像调整大小（即减少保持高度的宽度），并且当丢失图像的某些部分时是不可取的。在这种情况下，在这种情况下执行直接的图像缩放将扭曲其中的对象。为了保持对象的比例，同时改变图像比例，我们可以使用Shai Avidan和Ariel Shamir引入的缝雕算法。

下面的示例显示了使用内容感知调整大小（左图像）和直接缩放（右图像）如何将原始图像宽度降低了50％。在这种特殊情况下，由于保留了气球的比例，因此左图像看起来更自然。

接缝雕刻算法＆＃39;思路是找到对图像内容的最低贡献的接缝（连续的像素序列），然后雕刻（删除）它。此过程一遍又一遍地重复，直到我们获得所需的图像宽度或高度。在下面的示例中，您可能会发现热气囊像素比天空像素更多地贡献图像的内容。因此，首先被去除天空像素。

找到具有最低能量的接缝是计算昂贵的任务（特别是对于大图像）。为了更快地进行接缝搜索，可以应用动态编程方法（我们将通过下面的实施细节）。

基于其两个相邻像素之间的差异来计算每个像素（所谓的像素和＃39; s能量）的重要性。现在，如果我们人为地将像素能量设置为一些真正的低电平（即通过在它们的顶部绘制掩模），接缝雕刻算法将免费为我们执行对象。

我创建了JS Image Carver Web-App（并且还在Github上开放它），您可以用来调整自定义图像的大小。您也可以立即尝试下面的嵌入版本！此小部件使用We＆＃39;重新在本文中探索的缝雕算法。

海浪也是如此。该算法保留了波结构而不会扭曲冲浪器。

我们需要注意的是，接缝雕刻算法不是银子弹，并且它可能无法调整大多数像素是边缘的图像大小（对算法很重要）。在这种情况下，它即使是图像的重要部分也开始扭曲。在下面的例子中，内容感知的图像调整大小看起来非常类似于直接缩放，因为对于算法，所有像素看起来都很重要，并且它很难区分梵高＆＃39;从背景中脸部脸部的脸。

想象一下我们有一个1000 x 500 px的图片，我们希望将其大小缩小到500 x 500 px，使其正方形（设＆＃39; s说方比率更好地拟合Instagram进料）。在这种情况下，我们可能希望为调整大小的过程设置多个要求：

保留图像的重要部分（即，如果在调整之前有5棵树，我们也希望在调整大小后有5棵树）。

保留图像的重要部分的比例（即圆形车轮不应挤到椭圆轮）

为避免更改图像的重要部分，我们可以找到从上到下的像素（接缝）的连续序列，并且对图像内容具有最低贡献（避免重要的部件），然后将其移除。接缝移除将按1像素缩小图像。然后，我们将重复此步骤，直到图像达到所需的宽度。

问题是如何定义像素的重要性及其对内容的贡献（在原始纸中，作者正在使用像素的术语能量）。这样做的一种方法是将形成边缘的所有像素视为重要的。如果像素是边缘的一部分，其颜色将在邻居（左和右像素）之间具有比ISN＆＃39; T的一部分的像素之间的更大差异。

假设像素的颜色由4个数字表示（R - 红色，G - Green，B - 蓝，A-alpha），我们可以使用以下公式来计算颜色差（像素能量）：

在上面的公式中，我们省略了alpha（透明度）信道，假设图像中没有透明像素。后来我们将使用Alpha通道进行屏蔽和对象删除。

现在，由于我们知道如何找到一个像素的能量，我们可以计算，所谓的能量图，其将包含图像的每个像素的能量。在每个调整步骤上，应重新计算能量图（至少部分地，下面的内容，并且可以具有与图像相同的大小。

例如，在第一步的第一步，我们将拥有1000 x 500图像和1000 x 500的能量图。在第二调整步骤中，我们将从图像中删除接缝，并根据新的缩小图像重新计算能量图。因此，我们将获得999 x 500图像和999 x 500的能量图。

像素的能量越高，它的边缘的一部分越多，对于图像内容而言，我们需要删除它的可能性越小。

为了可视化能量图，我们可以将更亮色的颜色分配给具有较高能量的像素和较较较低能量的像素。这是一个人为的例子，了解能量图的随机部分的样子。您可能会看到表示边缘的明亮线，我们希望在调整大小期间保留。

这是您在上面看到的演示图像的能量图的真实例子（具有热气球）。

以下小部件在调整大小期间使能量贴图呈现。您可以使用您的自定义图像进行游戏，看看能量图如何看起来像。

我们可以使用能量图以找到具有最低能量的接缝（一个接一个），并通过执行此操作以确定应最终删除哪些像素。

找到具有最低能量的接缝不是琐碎的任务，并且需要在做出决定之前探索许多可能的像素组合。我们将应用动态编程方法来加速它。

在下面的示例中，您可能会看到能量贴图，其中最低能量接缝为它。

在上面的示例中，我们正在降低图像的宽度。可以采取类似的方法来降低图像高度。我们需要＆＃34;旋转＆＃34;但方法：

从顶部和底部像素邻居（而不是左右和右侧）开始计算像素能量

在搜索接缝时，我们需要从左到右移动（而不是从最多底部移动）

您可以在JS-Image-Carver存储库中找到源代码和下面提到的函数。

要实现我们将使用类型签名的算法。如果您想要JavaScript版本，您可以忽略（删除）类型定义及其用法。

出于简单原因，Let＆＃39; s仅为图像宽度降低实现SEAM雕算法。

首先，让＆＃39; s定义了我们＆＃39;重新实现算法的重新使用的一些常见类型。

//描述图像大小（宽度和高度）的类型。 type = {w：number，h：number}; //像素的坐标。 type = {x：number，y：number}; //接缝是一系列像素（坐标）。 type =坐标[]; // Energy映射是一个2D阵列，其具有相同的宽度和高度//作为图像的图像进行计算。 type = number [] []; //描述图像像素＆＃39; s rgba颜色的类型。 type = [r：number，//红色g：number，// green b：number，//蓝色a：number，// alpha（透明度）] | UINT8CLAMPEDARRAY;

根据能量图找到具有最低能量的接缝（这是我们将应用动态编程的地方）。

type = {img：imagedata，//我们要调整的图像数据。 Towidth：数字，//最终图像宽度我们希望图像缩小到。 }; type = {img：imagedata，//调整大小的图像数据。尺寸：图像化，//调整大小的图像尺寸（W x H）。 }; //执行使用Seam雕刻方法调整大小调整的内容感知图像宽度。 Export Const ResizeImageWidth =（{IMG，Towidth}：ResizeImageWidthargs，）：ResizeImageWidthresult =＆gt; {//出于性能原因，我们要避免更改IMG数据阵列大小。 //我们＆＃39; ll只是单独保持调整大小的图像宽度和高度的记录。 const大小：keepize = {w：img .width，h：img .height}; //计算要删除的像素数。 const pxtoremove = img .width - towidth; if（pxtoremove＆lt; 0）{投掷新（＆＃39;现在不支持upsizing＆＃39;）; }让Energymap：Energymap | null = null;让缝：接缝| null = null; //逐一取下最低能量接缝。 for（让i = 0; i＆lt; pxtoremove; i + = 1）{// 1.计算当前版本的图像的能量图。 Energymap = CalculateNergymap（IMG，尺寸）; // 2.找到基于能量图的最低能量的接缝。 Seam = FindLowEnergyseam（Energymap，尺寸）; // 3.从图像中删除具有最低能量接缝的接缝。 DeletEseam（IMG，Seam，Size）; //减少图像宽度，然后继续迭代。尺寸.w - = 1; } //返回调整大小的图像及其最终大小。 // IMG实际上是对IMAGEDATA的引用，所以从技术上//函数的来电已经具有这个指针。但是，Let＆＃39; s //仍然返回它以获得更好的代码可读性。返回{img，size}; };

需要调整大小的图像被传递到IMAGEDATA格式的函数。您可以在画布上绘制图像，然后从图中提取ImageData：

在JavaScript中上传和绘制图像的方式超出了本文的范围，但您可能会找到如何在JS-Image-Carver Repo中使用React完成的完整源代码。

让＆＃39; s分解每个步骤ony是一个并实现compulateNergymap（），findlowenergyseam（）和deleteseam（）函数。

在这里，我们应用上述色差公式。对于左右边框（当没有左或右邻居时），我们忽略邻居和Don＆＃39;在能量计算期间考虑到它们。

//计算像素的能量。 const getpixelenergy =（左：颜色| null，中间：颜色，右：颜色| null）：number =＆gt; {//中间像素是我们＆＃39的像素;重新计算能量。常数[MR，MG，MB] =中间; //来自左像素的能量（如果存在）。让Lenergy = 0; if（左）{const [lr，lg，lb] =左; Lenergy =（LR - MR）** 2 +（LG-MG）** 2 +（LB - MB）** 2; } //来自右像素的能量（如果存在）。让肾脏= 0; if（右）{const [rr，rg，rb] =右; renergy =（rr - mr）** 2 +（rg - mg）** 2 +（rb - mb）** 2; } //导致像素能量。返回数学。 SQRT（Lenergy +肾脏）; };

图片我们＆＃39;重新使用ImageData格式。这意味着所有像素（和它们的颜色）都存储在扁平（1D）Uint8ClampedArray阵列中。可用于可读性目的，Let＆＃39; s介绍了这对辅助函数的耦合，允许我们与UINT8ClampedArray数组相反，而不是2D矩阵。

//返回像素颜色的帮助函数。 const getpixel =（img：imagedata，{x，y}：坐标）：color =＆gt; {// imageData数据数组是一个扁平的1D阵列。因此，我们需要将X和Y坐标转换为线性索引。 const i = y * img .width + x; const cellerpercolor = 4; // RGBA //为了更好的效率，而不是创建新的子阵列，我们返回到Imagedata数组一部分的指针。返回img .data。子阵列（i * cellerpercolor，i * cellerpercolor + cellercolor）; }; //设置像素颜色的辅助函数。 const setpixel =（img：imagedata，{x，y}：坐标，颜色：颜色）：void =＆gt; {// imageData数据数组是一个扁平的1D阵列。因此，我们需要将X和Y坐标转换为线性索引。 const i = y * img .width + x; const cellerpercolor = 4; // rgba img .data。设置（颜色，i * cellerpercolor）; };

为了计算能量映射，我们通过每个图像像素，并调用先前描述的getPixelenergy（）函数。

//辅助函数创建特定//大小（w x h）的矩阵（2d阵列），并以指定的值填充它。常数矩阵=＆lt; T＆gt; （W：号码，H：号码，填充物：T）：T [] [] =＆gt; {返回新（h）。填充（null）。地图（（）=＆gt; {返回新（w）。填充（填充物）;}）; }; //计算图像的每个像素的能量。 Const CalculateNegyMap =（IMG：ImageData，{W，H}：图像化）：Energymap =＆gt; {//创建一个空的能量图，其中每个像素具有无限的能量。 //我们将更新每个像素的能量。 Const Energymap：Number [] [] =矩阵（W，H，Infinity）; for（让y = 0; y＆lt; h; y + = 1）{for（设定x = 0; x＆lt; x + = 1）{//左像素可能不存在，如果我们＆＃39;重新开始图像的左边缘。 const左=（x - 1）＆gt; = 0？ getpixel（img，{x：x - 1，y}）：null; //我们＆＃39;重新计算能量的中间像素的颜色。 const中间= getpixel（img，{x，y}）;如果我们＆＃39;重新在图像的非常右边，可能不存在//右像素。 const右=（x + 1）＆lt; W？ getpixel（img，{x：x + 1，y}）：null; Energymap [Y] [x] = getpixelenergy（左，中，右）; }}返回Energymap; };

每个调整大小迭代都将重新计算能量图。这意味着它将被重新计算，让＆＃39; s说，如果我们需要将图像缩小500像素，那么500次是不可最佳的。为了加速第二，第3，第3和进一步的步骤的能量图计算，我们可以仅为将要移除的接缝围绕的那些像素重新计算能量。为简单原因，此处省略了这种优化，但您可以在JS-Image-Carver Repo中找到示例源代码。

我以前描述了一些动态编程VS划分和征服文章中的一些动态编程基础。基于最小编辑距离问题存在DP示例。您可能想查看它以获得更多上下文。

我们现在需要解决的问题是找到从上到下的能量图上的路径（接缝），并且具有最小的像素能量。

从上到下，对于每个像素，我们有3个选项（↙︎向左转，↓下降，↘︎右向右）。这为我们提供了O（W * 3 ^ H）或简单o（3 ^ h）的时间复杂性，其中w和h是图像的宽度和高度。这种方法看起来很慢。

我们还可以尝试选择下一个像素作为具有最低能量的像素，希望得到的缝能量是最小的。

这种方法不是最糟糕的解决方案，但不能保证我们会找到最好的解决方案。在上面的图像上，您可能会看到贪婪的方法是如何先选择5而不是10，而是错过了最佳像素链。

关于这种方法的良好部分是它快速，并且它具有O（W + H）的时间复杂性，其中W和H是图像的宽度和高度。在这种情况下，速度的成本是调整大小的低质量。我们需要在第一行中找到最小值（遍历W单元），然后我们只探索每行的3个邻居像素（遍历H行）。

您可能已经注意到，在天真的方法中，我们在计算得到的接缝＆＃39时又一次地概括了相同的像素能量。活力。

在上面的示例中，您认为，对于前两个接缝，我们重新使用较短接缝的能量（其能量为235）。而不是做一个操作235 + 70以计算第二接缝的能量＆＃39;重新做四个操作（5 + 0 + 80 + 150）+ 70。

这一事实是，我们＆＃39;重新使用先前接缝的能量来计算电流接缝和＃39; S能量可以递归地递归地施以较短的接缝，直到一排缝。当我们有这样的重叠子问题时，它是一个符号，即一般问题可能通过动态编程方法优化。

因此，我们可以将当前接缝的能量节省在额外的接缝台中的特定像素中，以使其可重新使用，以便更快地计算下一个接缝（Seamsenergies表将具有与能量图和图像本身相同的大小） 。

我们还要记住，对于图像上的一个特定像素（即左下一），我们可能有几个先前接缝能量的若干值。

自从我们＆＃39;重新寻找具有最低结果能量的接缝，摘到最低的接缝也是最低的能量的有意义。

单元格[1] [x]：包含在行[0] [0] [0]的某处开始的接缝的最低能量，并于细胞[1] [x]。

当前的单元[2] [3]：包含在行[0] [0] [0]的某处开始的接缝的最低能量，并最终在细胞[2] [3]。要计算它，我们需要总结当前像素[2] [3]的能量[2] [3]（从能量图），min（Seam_energy_1_2，Seam_energy_1_3，Seam_energy_1_4）

如果我们完全填充了Seamsenergies表，那么最低排中的最小数字将是尽可能低的缝能量。

在填写后角接缝表后，我们可能会看到最低能量像素具有50的能量。为方便起见，在每个像素的Seamsenergies生成期间，我们可能不仅可以节省接缝的能量，而且还可以节省前一能量的坐标接缝。这将使我们能够容易地重建从底部到顶部的接缝路径。

DP方法的时间复杂度将是O（W * H），其中W和H是图像的宽度和高度。我们需要计算图像的每个像素的能量。

//接缝中像素的元数据。 type = {Energy：Number，//像素的能量。坐标：坐标，//像素的坐标。上一篇：坐标| null，//接缝中的先前像素。 }; //使用动态编程方法查找具有//最低结果的接缝（从上到下的像素序列）。 const findlowenergyseam =（Energymap：Energymap，{W，H}：图像化）：Seam =＆gt; {//大小的W和H大小的数组，其中每个像素包含//缝元（像素能量，像素坐标和从//此时的最低能量接缝）。 Const Seamsenergies :( Seampixelmeta | Null）[] [] =矩阵（W，H，NULL）; //只需从能量映射复制能量//来填充地图的第一行。 for（设法x = 0; x＆lt; w; x + = 1）{const y = 0; Seamsenergies [Y] [x] = {Energy：Energymap

......