Algorithm to draw outline in a colored region

user_5348875 0
Viewed 120

Suppose I have a image like this:

original image

Each square is a pixel. They are white or red.

I want to draw a green outline around the red region given an outline width w.

I tried some algorithms but the result isn't looking good, the diagonals look strange and don't reflect the original image:

my result

What approach should I use to get a smoother and better result with a good performance?

For simplicity, suppose I have a point p that belongs to the boundary.

math matrix image algorithm
2 Answers

Here is a solution using JavaScript:

var matrix=[
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];

function createMatrixDivs() {
  for(var r=0; r<16; r++) {
    for(var c=0; c<16; c++) {
      var cell=document.createElement("div");
      cell.style="border:1px solid blue;position:absolute;width:10px;height:10px;left:"+10*c+"px;top:"+10*r+"px;";
      cell.id=r+","+c;
      document.body.append(cell);
    }
  }
}

function drawMatrixDivs() {
  for(var r=0; r<16; r++) {
    for(var c=0; c<16; c++) {
      document.getElementById(r+","+c).style.backgroundColor=(matrix[r][c]==0?"white":matrix[r][c]==1?"red":matrix[r][c]==2?"green":"gray");
    }
  }
}

function outline(w) {
  for(var r1=0; r1<16; r1++) {
    for(var c1=0; c1<16; c1++) {
      if(matrix[r1][c1]==0) {
        for(var r2=0; r2<16; r2++) {
          for(var c2=0; c2<16; c2++) {
            if(r2!=r1 && c2!=c1 && matrix[r2][c2]==1 && Math.round(Math.sqrt(Math.pow(r2-r1,2)+Math.pow(c2-c1,2)))<=w) {
              matrix[r1][c1]=2;
            }
          }
        }
      }
    }
  }
  drawMatrixDivs();
}

createMatrixDivs();
drawMatrixDivs();
outline(+prompt("Enter outline width: "));

user_57925090

Your green outline shows the pixels that are <= w pixels away from the red ones, as measured using manhattan distance.

You want the pixels that are <= w pixels away from the red ones, as measured using Euclidean distance.

It's a little tricky, but you can actually do this in linear (O(width*height)) time.

PASS1: make a new matrix M[y][x] gives the vertical distance from (x,y) to a red pixel, or w+1 if the distance is more than w. You can do this in linear time by scanning up and then down through each column.

PASS2: scan from left to right in each row. Where M[y][x] <= w, you can color pixel (x,y) green, along with the sqrt(w2-M[y][x]2) pixels to the right. remember how far right you've colored, and avoid recoloring pixels you've already done, so this process will take linear time, too. Do the same thing scanning from right to left.

Make a lookup table for sqrt(w2-M[y][x]2) to avoid calculating it all the time.

Since @iAmOren was nice enough to provide working JS, I will blatantly copy that and fix it to use the faster algorithm:

var matrix=[
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];


function createMatrixDivs() {
  for(var r=0; r<16; r++) {
    for(var c=0; c<16; c++) {
      var cell=document.createElement("div");
      cell.style="border:1px solid blue;position:absolute;width:10px;height:10px;left:"+10*c+"px;top:"+10*r+"px;";
      cell.id=r+","+c;
      document.body.append(cell);
    }
  }
}

function drawMatrixDivs() {
  for(var r=0; r<16; r++) {
    for(var c=0; c<16; c++) {
      document.getElementById(r+","+c).style.backgroundColor=(matrix[r][c]==0?"white":matrix[r][c]==1?"red":matrix[r][c]==2?"green":"gray");
    }
  }
}

function outline(w) {
  var M = matrix.map(function(row) {
    return row.slice();
  });
  var x,y,d,i,s,e;

  //PASS 1 - put vertical distances in M

  for(x=0; x<16; x++) {
    d=w+1;
    for(y=0; y<16; y++) {
      if (matrix[y][x]==1) {
        d=0;
      } else if (d<=w) {
        ++d;
      }
      M[y][x]=d;
    }
    d=w+1;
    for(y=15; y>=0; y--) {
      if (matrix[y][x]==1) {
        d=0;
      } else if (d<=w) {
        ++d;
      }
      if (M[y][x] > d) {
        M[y][x] = d;
      }
    }
  }

  // Precalculate vertical distance -> horizontal span
  var spans=[];
  for (i=0; i<=w; ++i) {
    spans[i] = Math.sqrt((w+0.3)*(w+0.3) - i*i)|0;
  }

  // PASS 2 fill every pixel within w

  for(y=0; y<16; y++) {
    e=-1;
    for (x=0; x<16; ++x) {
      d = M[y][x];
      if (d<=w) {
        s=Math.max(x,e);
        e=Math.max(e,x+spans[d]);
        for(; s<=e && s<16; ++s) {
          matrix[y][s] = matrix[y][s]||2;
        }
      }
    }
    e=17;
    for (x=15; x>=0; --x) {
      d = M[y][x];
      if (d<=w) {
        s=Math.min(x,e);
        e=Math.min(e,x-spans[d]);
        for(; s>=e && s>0; --s) {
          matrix[y][s] = matrix[y][s]||2;
        }
      }
    }
  }
  drawMatrixDivs();
}
createMatrixDivs();
drawMatrixDivs();
outline(+prompt("Enter outline width: "));

user_54835260
Related