在 canvas 上围绕形状绘制方框

Question

我有这样一张图片：

小圆圈不规则，但都是黑色的。

我正在寻找一种算法来获取由每个形状的所有矩形边界组成的数组，如下所示：

我正在尝试使用 HTML5 canvas 执行此操作，但我没有找到获得边界并继续下一个形状的方法。我所做的是获得带有黑色像素 x 和 y 位置的二维数组：

   var x = 0,
       y = 0,
       cells = [];  
   for (var i = 0; i < imgdata.data.length; i += 4) {
      if (imgdata.data[i] != 255) {
        var p = [x,y];
        cells.push(p);
      }
      if (x > image.width) {
        x = 0;
        y = y+1;
      }
      x = x+1;
   }
   console.log(cells);

Answer 1

您可以使用简单的 flood fill 风格的算法天真地做到这一点，该算法跟踪所有 4 个方向上每个黑色区域的 max/min 点。

该算法可能会访问每个像素两次并使用线性space。它还使用递归，所以如果你的黑色斑点太大，它会破坏堆栈。重构为使用显式堆栈可以避免这种情况。换句话说，它根本没有优化，只是概念验证。

这是没有 canvas 的基本算法。请注意，它仅给出网格边界内的点，从技术上讲，这会将框放在形状的边缘，但您可以 add/subtract 1（或其他填充量）到每个角以将边界框移到形状的外部随心所欲的形状。

const findBoundingBoxes = grid => {
  const flood = (i, j, best) => {
    if (i < 0 || j < 0 ||
        i >= grid.length || j >= grid[i].length ||
        !grid[i][j] || visited[i][j]) {
      return;
    }

    visited[i][j] = true;
    best.top = Math.min(best.top, i);
    best.bottom = Math.max(best.bottom, i);
    best.left = Math.min(best.left, j);
    best.right = Math.max(best.right, j);

    for (let di = -1; di < 2; di++) {
      for (let dj = -1; dj < 2; dj++) {
        if (di !== 0 || dj !== 0) {
          flood(i + di, j + dj, best);
        }
      }
    }
  };

  const boxes = [];
  const visited = [...Array(grid.length)]
    .map((_, i) => [...Array(grid[i].length)].fill(false));

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (!grid[i][j] || visited[i][j]) {
        continue;
      }

      const best = {top: i, bottom: i, left: j, right: j};
      flood(i, j, best);
      boxes.push({
        topLeft: {x: best.left, y: best.top},
        topRight: {x: best.right, y: best.top},
        bottomLeft: {x: best.left, y: best.bottom},
        bottomRight: {x: best.right, y: best.bottom},
      });
    }
  }

  return boxes;
};

const grid = [
  "0000000000000",
  "0001100001000",
  "0011110111110",
  "0001100111100",
  "0000000000000",
].map(e => e.split("").map(Number));
console.log(findBoundingBoxes(grid));

现在，canvas。我正在将图像数据转换为二维网格以便于编码，这不是 performance-conscious。

const findBoundingBoxes = grid => {
  const flood = (i, j, best) => {
    if (i < 0 || j < 0 ||
        i >= grid.length || j >= grid[i].length ||
        !grid[i][j] || visited[i][j]) {
      return;
    }

    visited[i][j] = true;
    best.top = Math.min(best.top, i);
    best.bottom = Math.max(best.bottom, i);
    best.left = Math.min(best.left, j);
    best.right = Math.max(best.right, j);

    for (let di = -1; di < 2; di++) {
      for (let dj = -1; dj < 2; dj++) {
        if (di !== 0 || dj !== 0) {
          flood(i + di, j + dj, best);
        }
      }
    }
  };

  const boxes = [];
  const visited = [...Array(grid.length)]
    .map((_, i) => [...Array(grid[i].length)].fill(false));

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (!grid[i][j] || visited[i][j]) {
        continue;
      }

      const best = {top: i, bottom: i, left: j, right: j};
      flood(i, j, best);
      boxes.push({
        topLeft: {x: best.left, y: best.top},
        topRight: {x: best.right, y: best.top},
        bottomRight: {x: best.right, y: best.bottom},
        bottomLeft: {x: best.left, y: best.bottom},
      });
    }
  }

  return boxes;
};

const canvas = document.createElement("canvas");
canvas.style.border = "1px solid blue";
document.body.appendChild(canvas);
const ctx = canvas.getContext("2d");
const img = new Image();
img.onload = function() {
  const {width: w, height: h} = this;
  canvas.width = w;
  canvas.height = h;
  ctx.drawImage(this, 0, 0, w, h);
  const {data} = ctx.getImageData(0, 0, w, h);
  const grid = [...Array(h)].map((_, i) => 
    [...Array(w)].map((_, j) => data[(i*w+j)*4] < 255 ? 1 : 0)
  );
  const pad = 1;
  ctx.strokeStyle = "red";

  for (const box of findBoundingBoxes(grid)) {
    const w = box.topRight.x - box.topLeft.x;
    const h = box.bottomLeft.y - box.topLeft.y;
    ctx.strokeRect(
      box.topLeft.x - pad + 0.5,
      box.topLeft.y - pad + 0.5,
      w + pad * 2, h + pad * 2
    );
  }
};
img.src = "data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAMgAAADICAIAAAAiOjnJAAABhGlDQ1BJQ0MgcHJvZmlsZQAAKJF9kT1Iw0AcxV9TxSIVB4uIimSoThZERRylikWwUNoKrTqYXPoFTRqSFBdHwbXg4Mdi1cHFWVcHV0EQ/ABxdHJSdJES/5cUWsR4cNyPd/ced+8AoV5mqtkxAaiaZSRjUTGTXRW7XuFHAP0YwZDETD2eWkzDc3zdw8fXuwjP8j735+hRciYDfCLxHNMNi3iDeGbT0jnvE4dYUVKIz4nHDbog8SPXZZffOBccFnhmyEgn54lDxGKhjeU2ZkVDJZ4mDiuqRvlCxmWF8xZntVxlzXvyFwZz2kqK6zSHEcMS4khAhIwqSijDQoRWjRQTSdqPevgHHX+CXDK5SmDkWEAFKiTHD/4Hv7s181OTblIwCnS+2PbHKNC1CzRqtv19bNuNE8D/DFxpLX+lDsx+kl5raeEjoHcbuLhuafIecLkDDDzpkiE5kp+mkM8D72f0TVmg7xboXnN7a+7j9AFIU1fLN8DBITBWoOx1j3cH2nv790yzvx9wDHKmj+oRMgAAAAlwSFlzAAAuIwAALiMBeKU/dgAAAAd0SU1FB+YDCBYgCuMnEn4AAAAZdEVYdENvbW1lbnQAQ3JlYXRlZCB3aXRoIEdJTVBXgQ4XAAAC7klEQVR42u3d0WrkMAxA0Trk/3/ZfS20U5jBUizr3NeFZRmfkZ1smo4555e0ustHILAElsCSwBJYAksCS2AJLAksgSWwJLAElsCSwBJYAksCS2AJLAks7di92z9ojPHqj/wIZKHGDqv1DybIwEoihRdYgaTwAiuQFF6uCmNVhf7N2h1W9Nqz1RFWzqqz1QtW5nqz1QVW/kqzdT6sp9aYrZNhPbu6bHW5KhRYhwwMQ8vEElilRoWhZWIJrFJDwtAysQSWBJbKw9rzQOOYZWIJLAksgSWwJLAElsCSEmDt+RPJfk7axBJYElgqD2u3A40DloklsIoMCePKxBJYRUaFcWViCawiA8O4OnliPbW6VJ2/FeavMVVdzliZK01Vr8N7znpT1fGqMHrVqWoKK3Ttqdoqv0tHZ8FawgspsBbzQgqsZchgAkuuCiWwBJbAksBSiW4fQeFL+jfv/2XeAXC7oQWpfGdgdSSVYMsZC1OwVIisrdCwiTBgYslWKLAElgSWwBJYqteqewRB95vAkomllGEDlvalCZbAUp2dFKymOKLPZx5NPh/cz+cg0s77JpYxZmJpV0a/86CfTKyPvz3vPGzpmwbWYlLqBeuzN2YhBdYCc6+urgWWLe+o3McSWAJLYEltDu8O4yaWVGdiPZL/zDGxqAJLYElgCSwHrH4VeII09J4WUn0n1pzT8oNltMgZS53PWEFHLiPQxFoPgioTa/0Mowos2QolsASWwJLAElgCSwJLYAksCSyBJbAElo9AYKlMXgryR55+XvAZetBvuSfCwMp+w1ufT/twWBu+GbCJrXNgFXq7ZAdbN1ICCyZbIVK9d8OLKnWHRRVYVHX/ktzWQM5YAsu4AksCS2AJLAksgSWwJLAElsCSwBJYAksCS2AJLAksgSWwpMNheX0XWGzJViiwBJbdUNUmFltgsSVnLIFlaIElsKplaIElsGTugmU3BIstsCSwDC2w1PErcVkhgcUWWALL0BJYbNXoG/O8PCbkm47lAAAAAElFTkSuQmCC";

在 canvas 上围绕形状绘制方框

Draw boxes around shapes on canvas

javascript

canvas