c++ - 查找图像中的不同部分

Question

假设给你一个 vector<vector<bool>> (方形区域)其中 1 对应于“填充”框。有什么方法可以在 O(n) 时间内找到整个区域吗？例如，这个 vector 将有两个完整的区域:

0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0
0 0 1 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0

Answer 1

这叫做 8-connected region growing .这是图像处理中的标准技术，您选择一个种子像素并“增长”。这可以通过 BFS 来完成在像素数的线性时间内:

• 与边缘保持队列，将初始种子放在那里
• 从队列中获取一个元素，将其称为当前点并添加到您的“区域”列表中
• 将当前点的相邻点推送到队列中，永远不要将您已经推送到队列中的点推送到队列中
• 队列为空时结束。

区域列表包含一个区域，将其设置为零。找到另一个种子并再次运行，直到找不到种子。