在单色背景上绘制的精灵的边界矩形是否有计算算法？

Question

假设有一个纯白的矩形位图，大小为1024x768像素。在位图上绘制了一些（不重叠的）精灵：圆形、正方形和三角形。

是否存在一种算法（可能是C++实现），可以根据位图和背景颜色（例如上面的白色），生成一个包含每个精灵最小边界矩形的列表？

以下是一些示例：左侧是我的代码提供的样本位图（以及“背景”为白色的信息）。右侧是相同图像以及四个形状的边界矩形（红色）；我正在寻找的算法计算这些矩形的几何形状。

一些绘画程序具有类似的选择形状功能：它们甚至可以计算看似任意的边界多边形。您不需要手动拖动选择矩形，只需单击“背景”（背景和非背景由某个阈值确定），然后该工具会自动计算绘制到背景上的对象的形状。我需要类似的功能，不过如果我只有对象的矩形边界区域也完全没问题。

我了解到OpenCV；它似乎很相关（它似乎是一个包括我能想到的每种图形算法 - 以及其他一些东西的库），但在大量的信息中我找不到我所考虑的算法。如果OpenCV不能做到这一点，我会感到惊讶，但是我担心您必须拥有博士学位才能使用它。 :-)

- Frerich Raabe

---

你是在谈论边缘检测吗？ - FailedDev

@FailedDev：不完全正确；我不知道正确的术语，但是谷歌搜索“边缘检测”表明它可以找到亮度急剧变化的边界。我基本上只需要找到“最外层”的边界。 - Frerich Raabe

一张图片胜过千言万语——画出当前情况和你想要的结果。我可以猜测，但有了图片会更好... - Daniel Mošmondor

就像这样：http://imageshack.us/photo/my-images/209/selectg.png/，在红色圆圈周围画一个框？ - Mooing Duck

@DanielMošmondor：我想你是对的。我现在添加了两张图片，展示了一个样本输入位图，然后是相同的位图，包括（红色）边界矩形；我正在寻找的算法可以计算这些矩形的几何形状。 - Frerich Raabe

Answer 1

这里有一篇关于该主题的优秀文章：

http://softsurfer.com/Archive/algorithm_0107/algorithm_0107.htm

我认为这里不需要博士学位 :)

- Daniel Mošmondor

Answer 2

以下是我的第一篇想法，除了边缘检测之外都不复杂

For each square, 
   if it's not-white
       mark as "found"
       if you havn't found one next to it already
           add it to points list
for each point in the points list
    use basic edge detection to find outline
    keep track of bounds while doing so
    add bounds to shapes list
remove duplicates from shapes list. (this can happen for concave shapes)

我刚刚意识到这将把白色“洞”（例如您示例中最左边的圆中的洞）视为自己的形状。如果第一个“循环”是泛洪填充，则不会出现此问题，但速度会慢得多/占用更多内存。

我想到的基本边缘检测很简单：

given eight cardinal directions left, downleft, etc...
given two relative directions cw(direction-1) and ccw(direction+1)
starting with a point "begin"
set bounds to point
find direction d, where the begin+d is not white, and begin+cw(d) is white.
set current to begin+d
do 
    if current is outside of bounds, increase bounds
    set d = cw(d)
    while(cur+d is white or cur+ccw(d) is not white)
        d = ccw(d)
    cur = cur + d;
while(cur != begin

http://ideone.com/

这里有一些未被考虑到的边缘情况：如果开始是一个单点，它是否延伸到图片的边缘，如果起始点只有1个像素宽，但两侧都有斑点等等... 但基本算法并不那么复杂。

- Mooing Duck

---

我甚至认为你不需要边缘检测。只需查找所有非白色像素相邻的像素即可。一旦没有更多要测试的像素，就返回刚刚遍历过的形状的边界框。 - David Brigada

边缘检测将比泛洪查找所有非白色区域更快，编码也更容易。 - Mooing Duck

+1 有趣的想法！当你写“基本边缘检测”时，你有特定的边缘检测算法吗？ - Frerich Raabe

@FrerichRaabe：更新了答案，加入了一个简单的边缘检测算法。 - Mooing Duck