python - 查找像素簇和绘制 bbox 的最有效算法是什么

Question

我有以下场景，我有一个 N*N 二进制图像，我想找到簇的数量并在它们周围绘制 bbox。

一些要求: - 至少有 1 个集群，也可以有很多。 - 唯一“可控制”的参数是k，它是属于同一簇的像素之间的最大距离。

下面是一些代码来说明我在说什么:

1。生成具有 6 个簇的随机图像(只是一个随机示例)

注意:我不想改进这部分，这只是为了举例。

import numpy as np

from PIL import Image
from IPython.display import display

def display_array(image):
    image_display_ready = (image * 255).astype(np.uint8)

    img = Image.fromarray(image_display_ready)
    display(img)

def generate_image():
    image = np.zeros([256,256])

    for _ in range(200):
        while True:
            i, j = np.random.randint(25, 100, size=2)

            if image[i, j] == 0:
                break

        image[i, j] = 1

    for _ in range(200):
        while True:
            i, j = np.random.randint(150, 225, size=2)

            if image[i, j] == 0:
                break

        image[i, j] = 1

    for _ in range(100):
        while True:
            i, j = (np.random.randint(150, 225), np.random.randint(25, 50))

            if image[i, j] == 0:
                break

        image[i, j] = 1

    for _ in range(100):
        while True:
            i, j = (np.random.randint(150, 225), np.random.randint(75, 100))

            if image[i, j] == 0:
                break

        image[i, j] = 1

    for _ in range(100):
        while True:
            i, j = (np.random.randint(25, 50), np.random.randint(150, 225))

            if image[i, j] == 0:
                break

        image[i, j] = 1

    for _ in range(100):
        while True:
            i, j = (np.random.randint(75, 100), np.random.randint(150, 225))

            if image[i, j] == 0:
                break

        image[i, j] = 1

    return image

image = generate_image() 
display_array(image)

输出:

2。求簇数

下面是解决方案，我目前有，想知道是否可以改进。在我看来，这不是有效的解决方案。

注意: lookup_range是前面介绍的k参数

def compute_bbox_coordinates(mask_img, lookup_range, verbose=0):

    bbox_list = list()
    visited_pixels = list()

    bbox_found = 0

    for i in range(mask_img.shape[0]):
        for j in range(mask_img.shape[1]):

            if mask_img[i, j] == 1 and (i, j) not in visited_pixels:

                bbox_found += 1

                pixels_to_visit = list()

                bbox = {
                    'i_min': i,
                    'j_min': j,
                    'i_max': i,
                    'j_max': j
                }

                pxl_i = i
                pxl_j = j

                while True:

                    visited_pixels.append((pxl_i, pxl_j))

                    bbox['i_min'] = min(bbox['i_min'], pxl_i)
                    bbox['j_min'] = min(bbox['j_min'], pxl_j)
                    bbox['i_max'] = max(bbox['i_max'], pxl_i)
                    bbox['j_max'] = max(bbox['j_max'], pxl_j)

                    i_min = max(0, pxl_i - lookup_range)
                    j_min = max(0, pxl_j - lookup_range)

                    i_max = min(mask_img.shape[0], pxl_i + lookup_range + 1)
                    j_max = min(mask_img.shape[1], pxl_j + lookup_range + 1)

                    for i_k in range(i_min, i_max):
                        for j_k in range(j_min, j_max):

                            if mask_img[i_k, j_k] == 1 and (i_k, j_k) not in visited_pixels and (
                            i_k, j_k) not in pixels_to_visit:
                                pixels_to_visit.append((i_k, j_k))
                                visited_pixels.append((i_k, j_k))

                    if not pixels_to_visit:
                        break

                    else:
                        pixel = pixels_to_visit.pop()
                        pxl_i = pixel[0]
                        pxl_j = pixel[1]

                bbox_list.append(bbox)
    if verbose:
        print("BBOX Found: %d" % bbox_found)

    return bbox_list

bbox_coords = compute_bbox_coordinates(image, lookup_range=15, verbose=0)
print(bbox_coords)

输出:

Number of clusters: 6
[
    {'i_min': 25, 'j_min': 25, 'i_max': 99, 'j_max': 99}, 
    {'i_min': 25, 'j_min': 150, 'i_max': 49, 'j_max': 224}, 
    {'i_min': 75, 'j_min': 151, 'i_max': 99, 'j_max': 224}, 
    {'i_min': 150, 'j_min': 75, 'i_max': 224, 'j_max': 99}, 
    {'i_min': 150, 'j_min': 150, 'i_max': 224, 'j_max': 224}, 
    {'i_min': 151, 'j_min': 25, 'i_max': 224, 'j_max': 49}
]

3。从 bbox 坐标计算 bbox 覆盖

def compute_bbox_overlay(target_image, bbox_list):

    mask_img_bbox = np.copy(target_image)

    for bbox in bbox_list:
        mask_img_bbox[bbox['i_min'], bbox['j_min']:bbox['j_max']+1] = 1
        mask_img_bbox[bbox['i_max'], bbox['j_min']:bbox['j_max']+1] = 1
        mask_img_bbox[bbox['i_min']:bbox['i_max']+1, bbox['j_min']] = 1
        mask_img_bbox[bbox['i_min']:bbox['i_max']+1, bbox['j_max']] = 1

    return mask_img_bbox

display_array(compute_bbox_overlay(image, bbox_coords))

输出:

4。结语

我认为 compute_bbox_overlay 已经足够好了，不需要进一步优化。但是，如果您有任何让compute_bbox_coordinates 更快的想法，我真的很感兴趣，并且真的很想专注于改进这个函数，当图像中有大量集群时，它会非常慢。

如果您需要任何额外的精确度，我很乐意编辑我的帖子。我认为这篇文章更像是一场讨论，而不是真正期待一个交 key 解决方案；)

性能指标:

根据k的值，我有如下表现(对于step 2和step 3一起，大部分时间都在step 2执行)。

• k == 1:47 毫秒 => 又好又快#Yeah
• k == 25:1.4 秒 => 从那时起，已经太多了
• k == 100:8.8 秒 => 绝对禁止，完全无法使用
• k == 200: 20.7 秒 => 等待量子计算，可能会更快...

如您所见，还有改进的余地；)

Answer 1

如果您使用的是 OpenCV 等计算机视觉库，则可以使用 distance transform去做这个。 OpenCV distanceTransform计算源图像每个像素到最近零像素的距离。因此，对于您的示例图像，您可以简单地反转源图像、进行距离变换、阈值化并找到轮廓，然后计算它们的边界框。

import cv2
import numpy as np
from matplotlib import pyplot as plt

im = cv2.imread('gzRYR.png')
gray = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)
# distance-transform
dist = cv2.distanceTransform(~gray, cv2.DIST_L1, 3)
# max distance
k = 10
bw = np.uint8(dist < k)
# remove extra padding created by distance-transform
kernel = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (k, k))
bw2 = cv2.morphologyEx(bw, cv2.MORPH_ERODE, kernel)
# clusters
_, contours, _ = cv2.findContours(bw2, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
# draw clusters and bounding-boxes
i = 0
print(len(contours))
for cnt in contours:
    x, y, w, h = cv2.boundingRect(cnt)
    cv2.rectangle(im, (x, y), (x+w, y+h), (0, 255, 0), 2)
    cv2.drawContours(im, contours, i, (255, 0, 0), 2)
    i += 1

plt.subplot(121); plt.imshow(im)
plt.subplot(122); plt.imshow(bw2)