在图像中查找空白区域

Question

这个问题不太依赖于特定的编程语言，但我用的是numpy数组。

我正在通过PIL库来计算两张图片之间的差异：

img = ImageChops.difference(img1, img2)

我想找到那些显示出变化的矩形区域。虽然有一个内置的 .getbbox() 方法，但如果有两个区域发生了变化，它会返回一个从一个区域到另一个区域的框。如果每个角落只有1个像素的变化，它会返回整个图像。

比如说，考虑下面的情况，其中 o 是一个非零像素：

______________________
|o            ooo    |
|      oooo   ooo    |
|      o             |
|      o  o          |
|                    |
|     oo       o     |
|    o  o     ooo    |
|     oo     ooooo   |
|             ooo    |
|              o     |
|____________________|

我想得到包含每个非零区域边界框的4x4元组。对于这种特殊情况的

oooo
o
o  o

结构，我并不太担心怎么处理——无论是分别获取两个部分还是一起获取，因为倒L形的边界会完全覆盖单个像素的边界。

我之前没有做过这么复杂的图像处理，所以在真正开始写代码之前，我想先听听大家的意见（如果我已经在用的模块里有现成的方法，我也很欢迎！）。

我的伪代码大致是这样的：

for line in image:
   started = False
   for pixel in line:
      if pixel and not started:
         started = True
         save start coords
      elif started and not pixel:
         started = False
         save end coords (x - 1 of course)

这应该能给我一个坐标列表，但接下来我需要确定这些区域是否是相连的。我可以用图搜索的方法来实现吗？（我们上学期的算法课上做了很多深度优先搜索和广度优先搜索）当然，我想我可以在之前的循环中做这个？

我不会处理“很大”的图像——这些图像是从网络摄像头获取的，我现在最好的图像是640x480。最多我会处理720p或1080p，但那是未来的事，现在还不太担心。

所以我的问题是：我走在正确的道路上吗，还是偏离了方向？更重要的是，有没有什么内置的函数可以让我避免重复造轮子？最后，有没有好的资源（教程、论文等）可以帮助我？

谢谢！

Answer 1

一个聚类工具包（比如这个）应该能完成大部分工作（找到相连的像素）。然后，找出一个聚类的边界框就简单多了。

Answer 2

你可以在图片中寻找相连的部分，然后确定这些部分的边界框。

Answer 3

我认为 scipy的ndimage模块 包含了你所需要的一切……

这里有个简单的例子

import numpy as np
import scipy as sp
import scipy.ndimage.morphology

# The array you gave above
data = np.array( 
        [
           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 1, 0, 0, 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, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
           [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
        ])


# Fill holes to make sure we get nice clusters
filled = sp.ndimage.morphology.binary_fill_holes(data)

# Now seperate each group of contigous ones into a distinct value
# This will be an array of values from 1 - num_objects, with zeros
# outside of any contigous object
objects, num_objects = sp.ndimage.label(filled)

# Now return a list of slices around each object
#  (This is effectively the tuple that you wanted)
object_slices =  sp.ndimage.find_objects(objects)

# Just to illustrate using the object_slices
for obj_slice in object_slices:
    print data[obj_slice]

这个例子输出的是：

[[1]]
[[1 1 1]
 [1 1 1]]
[[1 1 1 1]
 [1 0 0 0]
 [1 0 0 1]]
[[1]]
[[0 1 1 0]
 [1 0 0 1]
 [0 1 1 0]]
[[0 0 1 0 0]
 [0 1 1 1 0]
 [1 1 1 1 1]
 [0 1 1 1 0]
 [0 0 1 0 0]]

注意，“object_slices”基本上就是你最初想要的内容，如果你需要实际的索引。

补充说明：我想指出，尽管它看起来能很好地处理边界情况

[[1 1 1 1]
 [1 0 0 0]
 [1 0 0 1]]

但实际上并没有处理好（所以会多出一个孤零零的 [[1]]）。你可以通过打印“objects”数组，查看对象3和4来确认这一点。

[[1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0]
 [0 0 0 0 0 0 3 3 3 3 0 0 0 2 2 2 0 0 0 0]
 [0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 3 0 0 4 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 5 5 0 0 0 0 0 0 0 6 0 0 0 0 0]
 [0 0 0 0 5 5 5 5 0 0 0 0 0 6 6 6 0 0 0 0]
 [0 0 0 0 0 5 5 0 0 0 0 0 6 6 6 6 6 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0]]

希望这能帮到你！

[1]