0

我有很多不重叠的彩色矩形的图像。每个矩形都是一种独特的颜色，我提前知道颜色。（奇怪的情况，我知道。）我试图找到每个矩形的像素位置和大小，我需要尽可能快。我可以用 RMagick 或类似的库做任何有趣的技巧来使这比遍历每个像素更容易吗？

我目前的计划是这样的：

for each pixel (moving left-to-right, top-to-bottom):
  if pixel color's in our list and we haven't seen it yet:
    save pixel location as starting location for that color
  else if pixel color's in our list and we've already seen it:
    save pixel location as ending location for that color

（是的，如果我们知道它们在矩形中，我们可以优化和跳过某些像素区域。）在循环结束时，我们应该有每个矩形的第一个和最后一个像素，我们可以用它们来推断矩形方面。但这对我来说似乎有些难看。

我能做得更好吗？

4

1 回答 1

1

此答案仅在存在最小矩形大小（理想情况下至少为 3x3）时才有效，这样额外的复杂性就会得到回报。

假设最小矩形大小为 (m, n)，使用该步长运行建议的算法以获得近似的起点和终点，然后通过逐个像素（在两个 L 形路径中）检查其中的位置来细化这些近似值两个对角是。您可以表明，与扫描整个图像相比，这将始终检查较少数量的像素。

for each pixel (moving left-to-right step m, top-to-bottom step n):
  if pixel color's in our list and we haven't seen it yet:
    save pixel location as rough starting location (xs,ys) for that color
    save pixel location as rough ending location (xe,ye) for that color
  else if pixel color's in our list and we've already seen it:
    save pixel location as rough ending location (xe,ye) for that color

然后细化位置

for each color
  with starting location (xs , ys)
    while color at (xs, ys - 1) is same, update ys = ys - 1
    while color at (xs - 1, ys) is same, update xs = xs - 1
  with ending location (xe , ye)
    while color at (xe, ye + 1) is same, update ye = ye + 1
    while color at (xe + 1, ye) is same, update xe = xe + 1

如果最小尺寸为 3x3，则要查找 20 个矩形，图像为 100x100：

  • 完整扫描将读取 10000 像素
  • 优化的扫描将读取 33x33 像素，然后通过读取 20x10（平均）来细化 20 个矩形中的每一个。总共 1289 像素。
于 2013-07-19T08:41:35.667 回答