在彩色区域中绘制轮廓的算法

Question

假设我有这样的图像：

每个正方形都是一个像素。它们是白色或红色。

我想在给定轮廓宽度w的红色区域周围绘制绿色轮廓。

我尝试了一些算法，但结果看起来不太好，对角线看起来很奇怪并且不反映原始图像：

我应该使用什么方法来获得更流畅、更好的结果和良好的性能？

为简单起见，假设我有一个属于边界的点p。

Answer 1

这是使用 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: "));

Answer 2

您的绿色轮廓显示距离红色像素 <= w 像素的像素（使用曼哈顿距离测量）。

您希望距离红色像素 <= w 像素的像素（使用欧几里德距离测量）。

这有点棘手，但实际上您可以在线性（O（宽度*高度））时间内完成此操作。

PASS1：创建一个新矩阵 M[y][x] 给出从 (x,y) 到红色像素的垂直距离，如果距离大于 w，则给出 w+1。您可以通过向上然后向下扫描每一列来在线性时间内完成此操作。

PASS2：每行从左到右扫描。当 M[y][x] <= w 时，您可以将像素 (x,y) 以及右侧的sqrt(w ² -M[y][x] ^{2 ) 像素着色为绿色。}记住你已经着色了多远，并避免重新着色你已经完成的像素，所以这个过程也将花费线性时间。做同样的事情从右到左扫描。

^{为 sqrt(w 2} -M[y][x] ² )制作一个查找表，以避免一直计算它。

由于 @iAmOren 足够好，可以提供工作 JS，我将公然复制它并修复它以使用更快的算法：

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