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

TL;DR

已经有很多关于Seam Carving算法的精彩文章，但我无法抗拒自己探索这个优雅、强大且简单的算法的诱惑，并写下我个人使用它的经验。引起我注意的另一点是动态规划(DP)方法可以顺利应用来解决它。而且，如果您像我一样仍在“学习算法”之旅中，那么这种算法解决方案可能会丰富您的个人DP武器库。

所以，通过这篇文章，我想做三件事：

1. 为您提供交互式内容感知大小调整器，以便您可以调整自己的图像大小
2. 解释Seam Carving算法背后的想法
3. 解释实现算法的动态编程方法（我们将使用TypeScript）

内容感知图像大小调整

当涉及到改变图像比例（即在保持高度的同时减小宽度）和不希望丢失图像的某些部分时，可能会应用内容感知图像大小调整。在这种情况下，直接进行图像缩放会扭曲其中的对象。为了在改变图像比例的同时保留对象的比例，我们可以使用Shai Avidan和Ariel Shamir引入的Seam Carving算法。

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

Seam Carving算法的思想是找到对图像内容贡献最小的接缝（像素的连续序列），然后对其进行雕刻（去除）。这个过程一遍又一遍地重复，直到我们得到所需的图像宽度或高度。在下面的示例中，您可能会看到热气球像素对图像内容的贡献大于天空像素。因此，天空像素首先被移除。

 寻找能量最低的接缝是一项计算成本很高的任务（尤其是对于大图像）。为了使接缝搜索更快，可能会应用动态编程方法（我们将在下面介绍实现细节）。

物体移除

每个像素的重要性（所谓的像素能量）是根据两个相邻像素之间的颜色( R, G, B, A)差异来计算的。现在，如果我们人为地将像素能量设置为某个非常低的水平（即，通过在它们之上绘制蒙版），Seam Carving算法将免费为我们执行对象移除。

JS图像雕刻机演示

我创建了JS IMAGE CARVER Web应用程序，您可以使用它来调整自定义图像的大小。

更多示例

以下是该算法如何处理更复杂背景的更多示例。

背景中的山脉正在平滑地缩小，没有可见的接缝。

海浪也是如此。该算法在不扭曲冲浪者的情况下保留了波浪结构。

我们需要记住，Seam Carving算法不是灵丹妙药，它可能无法调整大部分像素为边缘的图像的大小（看起来对算法很重要）。在这种情况下，它甚至开始扭曲图像的重要部分。在下面的示例中，内容感知图像大小调整看起来与直接缩放非常相似，因为对于算法而言，所有像素看起来都很重要，并且很难将梵高的脸与背景区分开来。

接缝雕刻算法的工作原理

想象一下，我们有一张1000 x 500 px图片，我们想改变它的大小以500 x 500 px使其成为正方形（假设正方形比例更适合Instagram提要）。在这种情况下，我们可能希望对调整大小的过程设置几个要求：

• 保留图像的重要部分（即，如果在调整大小之前有5棵树，我们希望在调整大小后也有5棵树）。
• 保留图像重要部分的比例（即圆形车轮不应该挤到椭圆车轮上）

为了避免改变图像的重要部分，我们可能会找到连续的像素序列（接缝），从上到下，对图像内容的贡献最小（避开重要部分），然后将其删除。接缝去除将使图像缩小1个像素。然后我们将重复此步骤，直到图像获得所需的宽度。

问题是如何定义像素的重要性及其对内容的贡献（在原始论文中，作者使用了像素能量这个术语）。其中一种方法是将形成边缘的所有像素视为重要像素。如果像素是边缘的一部分，则其颜色在相邻像素（左右像素）之间的差异将大于不属于边缘的像素。

假设一个像素的颜色用4个数字（R-red, G-green, B-blue, A-alpha）表示，我们可以使用下面的公式来计算色差（像素能量）：

其中：

• mEnergy-中间像素[0..626]的能量（重要性）（如果四舍五入）
• lR-左侧像素([0..255])的红色通道值
• mR-中间像素([0..255])的红色通道值
• rR-右侧像素([0..255])的红色通道值
• lG-左侧像素([0..255])的绿色通道值
• 等等...

在上面的公式中，我们暂时忽略了alpha（透明度）通道，假设图像中没有透明像素。稍后，我们将使用Alpha通道进行遮罩和对象移除。

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

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

像素的能量越高，它就越有可能是边缘的一部分，它对图像内容很重要，我们需要移除它的可能性就越小。

为了可视化能量图，我们可以为具有较高能量的像素分配较亮的颜色，为具有较低能量的像素分配较暗的颜色。这是一个人为的例子，说明能量图的随机部分可能是什么样子。您可能会看到代表边缘的亮线，我们希望在调整大小时保留它。

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

我们可以使用能量图来找到能量最低的接缝（一个接一个），并通过这样做来决定最终应该删除哪些像素。

找到具有最低能量的接缝并非易事，需要在做出决定之前探索许多可能的像素组合。我们将应用动态规划方法来加速它。

在下面的示例中，您可能会看到为其找到的第一个最低能量接缝的能量图。

在上面的示例中，我们减小了图像的宽度。可以采取类似的方法来降低图像高度。不过，我们需要“轮换”该方法：

• 开始使用顶部和底部像素邻居（而不是左右像素）来计算像素能量
• 寻找接缝时，我们需要从左到右移动（而不是从上到下）

TypeScript中的实现

为了实现该算法，我们将使用TypeScript。如果你想要一个JavaScript版本，你可以忽略（删除）类型定义及其用法。

为简单起见，我们只为缩小图像宽度来实现接缝雕刻算法。

内容感知宽度调整（入口函数）

首先，让我们定义一些我们将在实现算法时使用的常见类型。

// Type that describes the image size (width and height).
type ImageSize = { w: number, h: number };

// The coordinate of the pixel.
type Coordinate = { x: number, y: number };

// The seam is a sequence of pixels (coordinates).
type Seam = Coordinate[];

// Energy map is a 2D array that has the same width and height
// as the image the map is being calculated for.
type EnergyMap = number[][];

// Type that describes the image pixel's RGBA color.
type Color = [
  r: number, // Red
  g: number, // Green
  b: number, // Blue
  a: number, // Alpha (transparency)
] | Uint8ClampedArray;

在高层次上，该算法包括以下步骤：

1. 计算当前版本图像的能量图。
2. 根据能量图找到能量最低的接缝（这是我们将应用动态编程的地方）。
3. 从图像中删除具有最低能量接缝的接缝。
4. 重复直到图像宽度减小到所需值。

type ResizeImageWidthArgs = {
  img: ImageData,  // Image data we want to resize.
  toWidth: number, // Final image width we want the image to shrink to.
};

type ResizeImageWidthResult = {
  img: ImageData,  // Resized image data.
  size: ImageSize, // Resized image size (w x h).
};

// Performs the content-aware image width resizing using the seam carving method.
export const resizeImageWidth = (
  { img, toWidth }: ResizeImageWidthArgs,
): ResizeImageWidthResult => {
  // For performance reasons, we want to avoid changing the img data array size.
  // Instead, we'll just keep the record of the resized image width and height separately.
  const size: ImageSize = { w: img.width, h: img.height };

  // Calculating the number of pixels to remove.
  const pxToRemove = img.width - toWidth;
  if (pxToRemove < 0) {
    throw new Error('Upsizing is not supported for now');
  }

  let energyMap: EnergyMap | null = null;
  let seam: Seam | null = null;

  // Removing the lowest energy seams one by one.
  for (let i = 0; i < pxToRemove; i += 1) {
    // 1. Calculate the energy map for the current version of the image.
    energyMap = calculateEnergyMap(img, size);

    // 2. Find the seam with the lowest energy based on the energy map.
    seam = findLowEnergySeam(energyMap, size);

    // 3. Delete the seam with the lowest energy seam from the image.
    deleteSeam(img, seam, size);

    // Reduce the image width, and continue iterations.
    size.w -= 1;
  }

  // Returning the resized image and its final size.
  // The img is actually a reference to the ImageData, so technically
  // the caller of the function already has this pointer. But let's
  // still return it for better code readability.
  return { img, size };
};

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

const ctx = canvas.getContext('2d');
const imgData = ctx.getImageData(0, 0, imgWidth, imgHeight);

让我们将每个步骤分解为一个步骤并实现calculateEnergyMap(),findLowEnergySeam()和deleteSeam()函数。

计算像素的能量

在这里，我们应用上述色差公式。对于左右边界（当没有左右邻居时），我们忽略邻居并且在能量计算时不考虑它们。

// Calculates the energy of a pixel.
const getPixelEnergy = (left: Color | null, middle: Color, right: Color | null): number => {
  // Middle pixel is the pixel we're calculating the energy for.
  const [mR, mG, mB] = middle;

  // Energy from the left pixel (if it exists).
  let lEnergy = 0;
  if (left) {
    const [lR, lG, lB] = left;
    lEnergy = (lR - mR) ** 2 + (lG - mG) ** 2 + (lB - mB) ** 2;
  }

  // Energy from the right pixel (if it exists).
  let rEnergy = 0;
  if (right) {
    const [rR, rG, rB] = right;
    rEnergy = (rR - mR) ** 2 + (rG - mG) ** 2 + (rB - mB) ** 2;
  }

  // Resulting pixel energy.
  return Math.sqrt(lEnergy + rEnergy);
};

计算能量图

我们正在使用的图像具有ImageData格式。这意味着所有像素（及其颜色）都存储在一个平面(1D ) Uint8ClampedArray数组中。出于可读性的目的，让我们介绍几个帮助函数，它们将允许我们像使用2D矩阵一样使用Uint8ClampedArray数组。

// Helper function that returns the color of the pixel.
const getPixel = (img: ImageData, { x, y }: Coordinate): Color => {
  // The ImageData data array is a flat 1D array.
  // Thus, we need to convert x and y coordinates to the linear index.
  const i = y * img.width + x;
  const cellsPerColor = 4; // RGBA
  // For better efficiency, instead of creating a new sub-array, we return
  // a pointer to the part of the ImageData array.
  return img.data.subarray(i * cellsPerColor, i * cellsPerColor + cellsPerColor);
};

// Helper function that sets the color of the pixel.
const setPixel = (img: ImageData, { x, y }: Coordinate, color: Color): void => {
  // The ImageData data array is a flat 1D array.
  // Thus, we need to convert x and y coordinates to the linear index.
  const i = y * img.width + x;
  const cellsPerColor = 4; // RGBA
  img.data.set(color, i * cellsPerColor);
};

为了计算能量图，我们遍历每个图像像素并针对它调用前面描述的getPixelEnergy()函数。

// Helper function that creates a matrix (2D array) of specific
// size (w x h) and fills it with specified value.
const matrix = (w: number, h: number, filler: T): T[][] => {
  return new Array(h)
    .fill(null)
    .map(() => {
      return new Array(w).fill(filler);
    });
};

// Calculates the energy of each pixel of the image.
const calculateEnergyMap = (img: ImageData, { w, h }: ImageSize): EnergyMap => {
  // Create an empty energy map where each pixel has infinitely high energy.
  // We will update the energy of each pixel.
  const energyMap: number[][] = matrix(w, h, Infinity);
  for (let y = 0; y < h; y += 1) {
    for (let x = 0; x < w; x += 1) {
      // Left pixel might not exist if we're on the very left edge of the image.
      const left = (x - 1) >= 0 ? getPixel(img, { x: x - 1, y }) : null;
      // The color of the middle pixel that we're calculating the energy for.
      const middle = getPixel(img, { x, y });
      // Right pixel might not exist if we're on the very right edge of the image.
      const right = (x + 1) < w ? getPixel(img, { x: x + 1, y }) : null;
      energyMap[y][x] = getPixelEnergy(left, middle, right);
    }
  }
  return energyMap;
};

能量图将在每次调整大小迭代时重新计算。这意味着如果我们需要将图像缩小500像素，那么它将被重新计算，比如说500次，这不是最优的。为了加快第2步、第3步和其他步骤的能量图计算，我们可能只为将要移除的接缝周围的那些像素重新计算能量。

寻找能量最低的接缝（动态规划方法）

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

天真的方法

天真的方法是一个接一个地检查所有可能的路径。

从上到下，对于每个像素，我们有3个选项（↙︎左下，↓下，↘︎右下）。这给了我们时间复杂度O(w * 3^h)或简单地说O(3^h)，其中w和h是图像的宽度和高度。这种方法看起来很慢。

贪婪的方法

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

这种方法没有给出最坏的解决方案，但它不能保证我们会找到最佳的可用解决方案。在上图中，您可能会看到贪婪方法最初选择5而不是10，从而错过了最佳像素链。

这种方法的优点是速度快，时间复杂度为O(w + h)，其中w和h是图像的宽度和高度。在这种情况下，速度的代价是调整大小的低质量。我们需要在第一行（遍历单元格）中找到最小值w，然后我们只探索每行（遍历h行）的3个相邻像素。

动态规划方法

您可能已经注意到，在简单的方法中，我们在计算结果接缝的能量时一遍又一遍地总结相同的像素能量。

在上面的示例中，您看到对于前两个接缝，我们正在重新使用较短接缝的能量（其能量为235）。我们不是只做一个操作235 + 70来计算第二个接缝的能量，而是做四个操作(5 + 0 + 80 + 150) + 70。

我们重新使用前一个接缝的能量来计算当前接缝的能量这一事实可能会递归地应用于所有较短的接缝，直到最上面的第一排接缝。当我们有这样的重叠子问题时，这表明一般问题可能会通过动态规划方法进行优化。

因此，我们可以将当前接缝在特定像素处的能量保存在一个附加seamsEnergies表中，以使其可重用于更快地计算下一个接缝（该seamsEnergies表将具有与能量图和图像本身相同的大小）。

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

由于我们正在寻找产生能量最低的接缝，因此选择产生能量最低的前一个接缝也是有意义的。

一般来说，我们有三种可能的先前似乎可供选择：

你可以这样想：

• 单元格[1][x]：包含从行[0][?]上某处开始并在单元格[1][x]处结束的接缝的最低能量
• 当前单元格[2][3] ：包含从行[0][?]某处开始到单元格[2][3]结束的接缝的最低能量。为了计算它，我们需要将当前像素[2][3]的能量（来自能量图）与min(seam_energy_1_2, seam_energy_1_3, seam_energy_1_4) 相加。

如果我们完全填满seamsEnergies表格，那么最低行中的最小数字将是可能的最低接缝能量。

让我们尝试填充这个表格的几个单元格，看看它是如何工作的。

填写seamsEnergies表格后，我们可以看到最低能量像素的能量为50。为方便起见，在seamsEnergies生成每个像素的过程中，我们不仅可以保存接缝的能量，还可以保存之前最低能量接缝的坐标。这将使我们能够轻松地重建从底部到顶部的接缝路径。

DP方法的时间复杂度是O(w * h)，其中w和h是图像的宽度和高度。我们需要计算图像每个像素的能量。

以下是如何实现此逻辑的示例：

// The metadata for the pixels in the seam.
type SeamPixelMeta = {
  energy: number,              // The energy of the pixel.
  coordinate: Coordinate,      // The coordinate of the pixel.
  previous: Coordinate | null, // The previous pixel in a seam.
};

// Finds the seam (the sequence of pixels from top to bottom) that has the
// lowest resulting energy using the Dynamic Programming approach.
const findLowEnergySeam = (energyMap: EnergyMap, { w, h }: ImageSize): Seam => {
  // The 2D array of the size of w and h, where each pixel contains the
  // seam metadata (pixel energy, pixel coordinate and previous pixel from
  // the lowest energy seam at this point).
  const seamsEnergies: (SeamPixelMeta | null)[][] = matrix(w, h, null);

  // Populate the first row of the map by just copying the energies
  // from the energy map.
  for (let x = 0; x < w; x += 1) {
    const y = 0;
    seamsEnergies[y][x] = {
      energy: energyMap[y][x],
      coordinate: { x, y },
      previous: null,
    };
  }

  // Populate the rest of the rows.
  for (let y = 1; y < h; y += 1) {
    for (let x = 0; x < w; x += 1) {
      // Find the top adjacent cell with minimum energy.
      // This cell would be the tail of a seam with lowest energy at this point.
      // It doesn't mean that this seam (path) has lowest energy globally.
      // Instead, it means that we found a path with the lowest energy that may lead
      // us to the current pixel with the coordinates x and y.
      let minPrevEnergy = Infinity;
      let minPrevX: number = x;
      for (let i = (x - 1); i = 0 && i < w && seamsEnergies[y - 1][i].energy < minPrevEnergy) {
          minPrevEnergy = seamsEnergies[y - 1][i].energy;
          minPrevX = i;
        }
      }

      // Update the current cell.
      seamsEnergies[y][x] = {
        energy: minPrevEnergy + energyMap[y][x],
        coordinate: { x, y },
        previous: { x: minPrevX, y: y - 1 },
      };
    }
  }

  // Find where the minimum energy seam ends.
  // We need to find the tail of the lowest energy seam to start
  // traversing it from its tail to its head (from the bottom to the top).
  let lastMinCoordinate: Coordinate | null = null;
  let minSeamEnergy = Infinity;
  for (let x = 0; x < w; x += 1) {
    const y = h - 1;
    if (seamsEnergies[y][x].energy < minSeamEnergy) {
      minSeamEnergy = seamsEnergies[y][x].energy;
      lastMinCoordinate = { x, y };
    }
  }

  // Find the lowest energy energy seam.
  // Once we know where the tail is, we may traverse and assemble the lowest
  // energy seam based on the "previous" value of the seam pixel metadata.
  const seam: Seam = [];
  if (!lastMinCoordinate) {
    return seam;
  }

  const { x: lastMinX, y: lastMinY } = lastMinCoordinate;

  // Adding new pixel to the seam path one by one until we reach the top.
  let currentSeam = seamsEnergies[lastMinY][lastMinX];
  while (currentSeam) {
    seam.push(currentSeam.coordinate);
    const prevMinCoordinates = currentSeam.previous;
    if (!prevMinCoordinates) {
      currentSeam = null;
    } else {
      const { x: prevMinX, y: prevMinY } = prevMinCoordinates;
      currentSeam = seamsEnergies[prevMinY][prevMinX];
    }
  }

  return seam;
};

以最低能量去除接缝

一旦我们找到能量最低的接缝，我们需要从图像中移除（雕刻）形成它的像素。移除是通过将接缝右侧的像素向左移动1px来实现的。出于性能原因，我们实际上并没有删除最后一列。相反，渲染组件将忽略超出调整大小的图像宽度的图像部分。

// Deletes the seam from the image data.
// We delete the pixel in each row and then shift the rest of the row pixels to the left.
const deleteSeam = (img: ImageData, seam: Seam, { w }: ImageSize): void => {
  seam.forEach(({ x: seamX, y: seamY }: Coordinate) => {
    for (let x = seamX; x < (w - 1); x += 1) {
      const nextPixel = getPixel(img, { x: x + 1, y: seamY });
      setPixel(img, { x, y: seamY }, nextPixel);
    }
  });
};

物体移除

接缝雕刻算法首先尝试去除由低能量像素组成的接缝。我们可以利用这一事实并通过手动为某些像素分配低能量（即，通过在图像上绘制并遮蔽某些区域），我们可以让Seam Carving算法免费为我们进行对象移除。

目前，在getPixelEnergy()函数中，我们只使用R, G,B颜色通道来计算像素的能量。但是还有我们还没有使用的颜色的A（alpha，transparency）参数。我们可以使用透明通道告诉算法透明像素是我们想要移除的像素。

以下是该算法如何用于对象移除。

问题和下一步

当然，JS IMAGE CARVER Web应用程序远非生产就绪的大小调整器。它的主要目的是交互式地试验缝雕刻算法。所以未来的计划是继续试验。

原始论文描述了Seam Carving算法如何不仅可以用于图像的缩小，还可以用于图像的放大。反过来，放大可能用于在对象移除后将图像放大回其原始宽度。

另一个有趣的实验领域可能是让算法实时工作。

这些是未来的计划，但就目前而言，我希望图像缩小的示例对您来说很有趣和有用。我也希望你有使用动态编程来实现它的想法。

https://www.codeproject.com/Articles/5322937/Content-Aware-Image-Resizing-in-JavaScript