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

Question

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

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 连通区域增长。这是图像处理中的一种标准技术，您选择一个种子像素并“增长”。这可以通过BFS在像素数的线性时间内完成：

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

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