Draw boxes around shapes on canvas

Question

I've got an image like this:

The little circles are not regular but they are all black.

I'm looking for an algorithm to obtain an array made of all the rectangle bounds of every shape, like this:

I'm trying to do this with HTML5 canvas, but I'm not finding a way to get the bounds and go ahead with next shape. What I've done is obtaining the 2d array with x and y position of black pixels:

   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

You can do this naively with a simple flood fill-style algorithm that keeps track of the max/min points of each black area in all 4 directions.

The algorithm may visit every pixel twice and uses linear space. It also uses recursion, so it'll blow the stack if your black blobs are too large. Refactoring to use an explicit stack would avoid that. In other words, it's not optimized at all, just a proof of concept.

Here's the basic algorithm without a canvas. Note that it gives the points only within grid bounds, which would technically put the box on the edges of the shape, but you can add/subtract 1 (or another padding amount) to each corner to move the bounding box outside of the shape as desired.

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));

Now, on a canvas. I'm converting the image data to a 2d grid for ease of coding, which isn't 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";