如何在OpenCV中高效打包二值图像的分割块？

针对二值图像的前景分割块紧凑打包，结合图像分割场景的特性，推荐采用天际线算法（Skyline Algorithm）+ 首次适应递减（FFD）策略，既能保证打包效率，又能达到较高的紧凑度。以下是具体实现步骤与代码：

核心思路 #

1. 从二值图像中提取所有前景连通域的边界框
2. 按块面积从大到小排序（FFD策略，优先放置大块减少空间浪费）
3. 用天际线算法快速定位每个块的最优放置位置，动态更新可用空间
4. 将原图像中的块裁剪后复制到目标画布的对应位置

具体实现步骤 #

1. 提取前景连通域与边界框 #

首先用OpenCV提取二值图像中的所有前景连通域，同时获取每个块的边界框、面积信息：

import cv2
import numpy as np

# 读取二值图像（确保输入为二值图，若不是先做阈值处理）
img = cv2.imread("binary_image.png", cv2.IMREAD_GRAYSCALE)
_, binary_img = cv2.threshold(img, 127, 255, cv2.THRESH_BINARY)

# 获取连通域及统计信息：ret, labels, stats, centroids
_, _, stats, _ = cv2.connectedComponentsWithStats(binary_img, connectivity=8)

# 过滤掉背景（索引0）和小噪点块
min_area = 100  # 根据实际场景调整
blocks = []
for stat in stats[1:]:
    x, y, w, h, area = stat
    if area >= min_area:
        # 存储块的宽高、原图像中的坐标
        blocks.append({"w": w, "h": h, "x": x, "y": y})

2. 按面积递减排序块 #

采用FFD策略，将块按面积从大到小排序，优先放置大块：

# 按面积递减排序
blocks.sort(key=lambda b: b["w"] * b["h"], reverse=True)

3. 实现天际线打包算法 #

天际线算法通过维护当前已放置块的顶部轮廓（天际线），快速找到每个新块的最佳放置位置：

def skyline_pack(blocks):
    if not blocks:
        return [], 0, 0
    
    # 初始化天际线：[(x_start, height), ...]，初始为(0, 0)
    skyline = [(0, 0)]
    total_width = 0
    total_height = 0
    
    placements = []  # 存储每个块的放置坐标(x, y)
    
    for block in blocks:
        bw, bh = block["w"], block["h"]
        best_x = None
        best_y = 0
        
        # 遍历天际线，寻找能放下当前块的最左位置
        for i in range(len(skyline)):
            current_x, current_h = skyline[i]
            # 检查从current_x开始是否有足够宽度放下块
            if i == len(skyline) - 1:
                available_width = float("inf")
            else:
                available_width = skyline[i+1][0] - current_x
            
            if available_width >= bw:
                # 计算当前位置的最低放置高度
                current_max_h = max(h for x, h in skyline[i:] if x < current_x + bw)
                if best_x is None or current_max_h < best_y:
                    best_x = current_x
                    best_y = current_max_h
        
        # 如果没有找到合适位置，扩展天际线到右侧
        if best_x is None:
            best_x = total_width
            best_y = max(h for x, h in skyline)
        
        # 记录放置位置
        placements.append((best_x, best_y))
        
        # 更新总宽度和高度
        total_width = max(total_width, best_x + bw)
        total_height = max(total_height, best_y + bh)
        
        # 更新天际线
        # 移除被当前块覆盖的天际线段
        new_skyline = []
        added = False
        for x, h in skyline:
            if x < best_x:
                new_skyline.append((x, h))
            elif x >= best_x + bw:
                new_skyline.append((x, h))
            else:
                if not added:
                    new_skyline.append((best_x, best_y + bh))
                    added = True
        # 处理天际线衔接，合并连续同高的线段
        merged_skyline = []
        for x, h in new_skyline:
            if merged_skyline and merged_skyline[-1][1] == h:
                continue
            merged_skyline.append((x, h))
        skyline = merged_skyline
    
    return placements, total_width, total_height

4. 生成打包后的图像 #

根据打包位置，从原图像裁剪块并粘贴到目标画布：

# 执行打包
placements, pack_width, pack_height = skyline_pack(blocks)

# 创建空白目标图像（白色背景）
packed_img = np.ones((pack_height, pack_width), dtype=np.uint8) * 255

# 逐个粘贴块
for block, (px, py) in zip(blocks, placements):
    # 从原图像裁剪块
    block_img = binary_img[block["y"]:block["y"]+block["h"], block["x"]:block["x"]+block["w"]]
    # 粘贴到目标位置
    packed_img[py:py+block["h"], px:px+block["w"]] = block_img

# 保存或显示结果
cv2.imwrite("packed_image.png", packed_img)
cv2.imshow("Packed Result", packed_img)
cv2.waitKey(0)
cv2.destroyAllWindows()

优化建议 #

• 加速查找：如果处理的块数量极大（数千以上），可以用线段树或区间树优化天际线的查找过程，将时间复杂度从O(n²)降低到O(n log n)
• 极致紧凑度：若不追求实时性，可采用遗传算法、模拟退火等启发式算法，但这类算法计算成本较高，适合离线处理
• 方向优化：对部分细长块，可以尝试旋转90度后再打包，进一步提升紧凑度（需在排序前加入旋转判断逻辑）

内容的提问来源于stack exchange，提问作者ma.mehralian