logo标签列表

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

algorithmimagemathmatrix
3

假设我有一张像这样的图片：

original image

每个正方形都是一个像素。它们是白色或红色的。
给定一个外框宽度 w，我想在红色区域周围画一个绿色的轮廓线。
我试了一些算法，但结果看起来并不好，对角线看起来很奇怪，不能反映原始图像：

my result

什么方法可以在保持良好性能的同时，获得更平滑、更好的结果？
为了简单起见，假设我有一个属于边界的点p。
2个回答
5

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

非常复杂... O(n^4)? 其中n是宽度或高度，它们相同=16... 这意味着-是的，你是正确的... - iAmOren
我点赞是因为你的努力和好看的结果，但是在问题中我要求一个良好的性能算法。这个任务将在移动应用程序中运行，我无法承受O(n^4)算法，因为我的纹理不会是16x16 xD。 - Daniel
我目前正在运行一个O(n²)的解决方案，我的问题是结果质量，正如问题所示。 - Daniel
@MattTimmermans，谢谢！请查看我在你的回答中的评论/问题。 - iAmOren
1
@Metabolic，谢谢你！（还有点赞 - 我猜其中一个是你） - iAmOren
显示剩余11条评论
5

绿色轮廓显示了与红色像素之间的曼哈顿距离小于或等于w像素的像素。

你希望测量欧几里得距离，找到那些与红色像素之间距离小于或等于w像素的像素。

虽然有点棘手，但你实际上可以在线性时间（O（width * height））内完成此操作。

第一遍扫描：创建一个新矩阵M[y][x]，给出从（x，y）到红色像素的垂直距离，如果距离大于w，则为w + 1。 你可以通过沿每列向上和向下扫描来在线性时间内完成此操作。

第二遍扫描：从左到右依次扫描每一行。当M[y][x] ≤ w时，你可以将像素（x，y）和其右侧sqrt(w2-M[y][x]2)个像素涂成绿色。记住已经涂过的像素的最右边位置，并避免重新涂色已经完成的像素，这个过程也需要线性时间。从右到左执行相同的操作。

制作一个查找表，以避免一直计算sqrt(w2-M[y][x]2)。

由于@iAmOren很好心地提供了可工作的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) {
  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: "));

谢谢你的认可（和点赞）！ 我都运行了一下，你的速度明显更快（2毫秒对比10毫秒+）。 （通过使用 var t=new Date();outline(3);console.log(new Date() - t);） 结果似乎有些不同，但总体上目标已经实现了。 我仍然不明白为什么这被认为不是O(n^4)，如果不是，那么我的代码为什么不是小于O(n^4)呢。 - iAmOren
1
如果您想更准确地了解复杂性，这个算法的时间复杂度是O(wid * hei)，因为它对每个像素都执行恒定数量的操作，而您的算法的时间复杂度是O(wid^2*hei^2)，因为对于图像中的每个清晰像素，它都会在整个图像中搜索附近的红色像素。您可以轻松将其优化为O(wid * hei * w^2)，只需搜索w个像素即可，但当w很大时，速度仍然会慢很多。 - Matt Timmermans
由于w和h都为n，即使它们的一部分是O(w*n)，而搜索即使在有限距离内（没有真正的方法来搜索一个圆形，所以）-需要搜寻一个框，O(w * n)，并且合起来：O(w^2 * h^2) => O(n^4)，同时，因为距离可能为n（w | h）。 当然，我可以使我的代码更加高效，但作为入门者，我想要一个可用的代码。 给石轮加上橡胶比发明轮子更容易。 :) - iAmOren
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接