Calculate bounding box of arbitrary pixel-based drawing

Question

Given a contiguous drawing of arbitrary pixels (e.g. on an HTML5 Canvas) is there any algorithm for finding the axis-aligned bounding box that is more efficient than simply looking at every pixel and recording the min/max x/y values?

Cathexis

Does this answer your question? Determine bounds of shape / graphics drawn into a Canvas – Barrett

Answer 1

Just scanline from top left to right and down to get y top,and similar algorithm with different directions for the rest.

---

Edit by Phrogz:

Here's a pseudo-code implementation. An included optimization ensures that each scan line does not look at pixels covered by an earlier pass:

function boundingBox()
  w = getWidth()            # Assuming graphics address goes from [0,w)
  h = getHeight()           # Assuming graphics address goes from [0,h)
  for y=h-1 to 0 by -1      # Iterate from last row upwards
    for x=w-1 to 0 by -1    # Iterate across the entire row
      if pxAt(x,y) then
        maxY=y
        break               # Break out of both loops

  if maxY===undefined then  # No pixels, no bounding box
    return               

  for x=w-1 to 0 by -1      # Iterate from last column to first
    for y=0 to maxY         # Iterate down the column, up to maxY
      if pxAt(x,y) then
        maxX=x
        break               # Break out of both loops

  for x=0 to maxX           # Iterate from first column to maxX
    for y=0 to maxY         # Iterate down the column, up to maxY
      if pxAt(x,y) then
        minX=x
        break               # Break out of both loops

  for y=0 to maxY           # Iterate down the rows, up to maxY
    for x=0 to maxX         # Iterate across the row, up to maxX
      if pxAt(x,y) then
        minY=y
        break               # Break out of both loops

  return minX, minY, maxX, maxY

The result (in practice) performs about the same as the brute-force algorithm for a single pixel, and significantly better as the object gets larger.

Demo: http://phrogz.net/tmp/canvas_bounding_box2.html

For fun, here's a visual representation of how this algorithm works:

       
       
       
       
       

It doesn't matter in what order you choose to do the sides, you just have to make sure that you take the previous results into account so that you are not double-scanning the corners.

Mohock

There's no need for so many loops. See my and @Eric Stotch's answers. – Fab

Answer 2

I dislike the current answer. Here's my code that I plugged into OP website. It's much faster in firefox and chrome.

The idea is check all pixels on x axis to see if there's a hit on the Y axis. If so update Y and increase X so we can scan for max X

function contextBoundingBox(ctx,alphaThreshold){
    if (alphaThreshold===undefined) alphaThreshold = 15;
    var w=ctx.canvas.width,h=ctx.canvas.height;
    var data = ctx.getImageData(0,0,w,h).data;

    let minX=w;
    let maxX=0
    let minY=h
    let maxY=0
    for(let y=0; y<h; y++)
    {
        for(let x=0; x<w; x++)
        {
            if (data[y*w*4 + x*4+3])
            {
                minX = Math.min(minX, x);
                maxX = Math.max(maxX, x);
                minY = Math.min(minY, y);
                maxY = y;
                x=maxX
            }
        }
    }

    return {x:minX,y:minY,maxX:maxX,maxY:maxY,w:maxX-minX,h:maxY-minY};
}

Noodlehead

Answer 3

You might be able to use some kind of binary search, or sample on a coarse grid then a successively finer grid. The correctness of this method depends on if 'holes' are allowed in your drawing.

Mope

A binary search can easily fail if the graphic has any concave boundary portions. – Cathexis

Answer 4

No need for so many loops. Here's a (imo) cleaned up version of the other answers:

const getBbox = (ctx: CanvasRenderingContext2D) => {
  // get dimensions
  const width = ctx.canvas.width;
  const height = ctx.canvas.height;
  // get image data
  const { data } = ctx.getImageData(0, 0, width, height);
  // min/max x/y's
  let left = width;
  let top = height;
  let right = 0;
  let bottom = 0;
  // number of pixels, 4 components (rgba) each
  const pixels = data.length / 4;
  // go through each pixel
  for (let pixel = 0; pixel < pixels; pixel++) {
    // get color components from every 4 array elements
    const [r, g, b, a] = data.slice(pixel * 4, pixel * 4 + 4);
    // if pixel "empty" by some criteria, ignore
    if (a === 0) continue;
    // get coordinates
    const x = pixel % width;
    const y = Math.floor(pixel / height);
    // update mins/maxes
    if (x < left) left = x;
    if (y < top) top = y;
    if (x > right) right = x;
    if (y > bottom) bottom = y;
  }
  // return bbox
  return { x: left, y: top, width: right - left + 1, height: bottom - top + 1 };
};

Fab