用最少数量的固定大小方块覆盖 0-1 图像中的所有 1 个像素

Question

问题定义

对于像素形状为 MxN 且给定整数 A 的 0-1 图像，问题的可行解定义为一定数量的 AxA 形状的像素方块，其并集可以覆盖 MxN 图像中的所有 1 像素，其中正方形的边缘平行于 MxN 图像的边缘并与像素对齐。 对于所有可行的解决方案，我需要找到其中包含最小数量的正方形的任何一个。

我想问的是，有没有什么算法可以解决这样的问题或类似的问题？或者，关于我可以寻找我想要的算法的区域（计算机视觉？或离散优化？）有什么建议吗？

可行解决方案示例

问题集

• M = N = 25，A = 15
• 下图中要覆盖的区域为灰色

可行的解决方案

• 三个方块覆盖部分区域，颜色饱和度较高。
• 以及正方形的并集，覆盖所有灰色像素
• 所以这三个正方形组成了问题的可行解，实际上也是最优解之一。

其他信息

• 要覆盖的区域几乎肯定不是凸的，而是相连的。
• 实际上我不需要策略来找到数学最优解。我更喜欢一种可以在有限的时间/复杂性内找到足够好的、几乎可行的解决方案的政策。

Answer 1

次优解决方案是使用滑动窗口（方形），找到与原始图像的最大交叉区域并从图像中删除该部分，然后重复直到没有留下任何东西。 这里是如何用

python

做到这一点。

读取图像

from skimage import io, filters
from skimage.transform import resize
import matplotlib.pyplot as plt

image = 1-io.imread("img.png", as_gray=True).astype(np.uint8)
image = resize(image, (25, 25))
t = filters.threshold_otsu(image)
image = (image>=t).astype(np.uint8)
plt.imshow(image, cmap=plt.cm.gray)

def get_square_masks(image, square_size=15):

    # copy the image to keep it unchanged
    image_c = image.copy()

    # this will create a view of (square_size, square_size) sliding window with stride=1
    image_parts = util.view_as_windows(image_c, (square_size, square_size), step=1)
    masks = []

    # repeat until you will get blank image
    while image_c.sum() !=0 :
        
        overlapping_areas = image_parts.sum(axis=(2, 3))
        r, c = np.where(overlapping_areas==overlapping_areas.max())

        # taking the first coordinates of maximum overlapping area,
        # may be others should be checked as well
        # since it is view, setting 0 will set overlapped squares with 0 as well
        image_parts[r[0], c[0]] = 0 

        # creating the square mask
        r_start = r[0]
        c_start = c[0]
        r_end = r_start + square_size
        c_end = c_start + square_size
        mask = np.zeros_like(image_c)
        mask[r_start:r_end,c_start:c_end] = 1
        
        masks.append(mask)
        
    return masks

masks = get_square_masks(image, 15)

我用这种天真的方法得到了 4 个面具。但我认为这是一个很好的起点。此外，您可以通过将它们视为潜在候选者来尝试优化

masks

。由于掩码的数量取决于第一个选择，我们可以迭代检索到的掩码，并选择第一个以外的掩码作为我们的第一选择，看看它是否更优化，如下所示：

import numpy as np

def try_reduce_masks(image, masks, square_size=15):
    masks_min = masks
    for m in masks[1:]:
        # remove the mask from image
        new_image = image*np.logical_xor(image, m).astype(np.uint8)
        # get new masks with different starting point
        new_masks = get_square_masks(new_image, square_size)
        new_masks.append(m)
        # by the end if get less masks then save it
        if len(new_masks) < len(masks_min):
            masks_min = new_masks
    return masks_min

masks = try_reduce_masks(image, masks, 15)

但是，如果您从

overlapping_areas

函数查看

get_square_masks

，您将在滑动窗口（方形）的每个步骤中获得重叠区域。我相信从这张地图中你可以找到更智能的方法来找到更优化的解决方案。

array([[177, 181, 181, 179, 175, 166, 153, 139, 124, 109,  94],
       [178, 183, 184, 183, 180, 172, 159, 146, 132, 117, 102],
       [175, 181, 183, 183, 181, 175, 163, 151, 138, 124, 109],
       [170, 177, 180, 182, 182, 178, 168, 157, 145, 132, 117],
       [161, 170, 175, 179, 181, 179, 171, 162, 151, 139, 125],
       [150, 161, 168, 174, 178, 178, 172, 165, 156, 145, 132],
       [137, 150, 159, 167, 173, 175, 171, 166, 159, 149, 137],
       [123, 137, 148, 158, 166, 170, 168, 165, 160, 152, 141],
       [108, 122, 135, 147, 157, 163, 163, 162, 159, 153, 144],
       [ 94, 107, 121, 134, 146, 154, 156, 157, 156, 152, 145],
       [ 82,  94, 107, 120, 133, 143, 147, 150, 151, 149, 144]])

可视化

plt.imshow(image)
for m in masks:
    plt.imshow(m, alpha=0.3, interpolation='nearest', cmap=plt.cm.gray)
plt.show()

我相信这可以通过强化学习通过选择适当的奖励函数来解决。例如，我们可以惩罚较小的重叠区域并奖励较少的步数。