Python实现超像素算法：如何优化超像素坐标存储的数据结构？

你的核心痛点在于原三维numpy数组的内存浪费，同时需要兼顾numba加速下的读写/运算效率。以下是几个比原方案更优的替代方案，完全适配你的需求：

方案1：二维数组+偏移量数组（最推荐） #

这是内存效率最高、numba优化效果最好的方案，本质是用连续内存存储所有坐标，再用一个偏移数组标记每个超像素的坐标范围，彻底解决稀疏性问题。

实现思路 #

• 用一个二维数组coords存储所有像素的(x,y)坐标，总内存仅为N*2*4字节（用int32足够存储图像坐标，1080p仅占~16MB）
• 用offsets数组记录每个超像素的起始/结束索引：offsets[sp_id]是第sp_id个超像素的第一个坐标在coords中的位置，offsets[sp_id+1]是最后一个坐标的下一位
• 每个超像素的像素数可直接通过offsets[sp_id+1] - offsets[sp_id]计算，无需额外维护inside_index

代码示例 #

import numpy as np
from numba import njit

# 初始化参数：假设超像素数量为num_sp，总像素数N
num_sp = 1000
N = 1920 * 1080

# 存储所有坐标的连续数组（用int32省内存）
coords = np.empty((N, 2), dtype=np.int32)
# 偏移数组，长度为超像素数+1，初始全0
offsets = np.zeros(num_sp + 1, dtype=np.int64)
current_offset = 0

# numba加速的像素添加函数
@njit
def add_pixel(sp_id, x, y):
    global current_offset
    coords[current_offset] = (x, y)
    offsets[sp_id + 1] += 1
    current_offset += 1

# 所有像素添加完成后，计算前缀和得到正式的偏移索引
offsets = np.cumsum(offsets)

# numba加速的超像素坐标获取函数
@njit
def get_sp_coords(sp_id):
    start = offsets[sp_id]
    end = offsets[sp_id + 1]
    return coords[start:end]

优点 #

• 内存利用率拉满，完全没有浪费
• 连续内存访问，numba编译后速度极快，支持所有numpy向量运算（直接对切片操作即可）
• 读写、批量操作效率远超稀疏矩阵和列表

方案2：Numba类型化列表存储独立数组 #

如果需要动态扩展超像素（比如不确定总像素数），可以用numba的typed.List存储每个超像素的独立坐标数组，比普通Python列表快得多。

代码示例 #

from numba import njit, typed

num_sp = 1000
# 用numba类型化列表存储每个超像素的坐标数组
sk = typed.List()
for _ in range(num_sp):
    # 预先分配部分空间减少resize次数，比如每个超像素先留100个位置
    sk.append(np.empty((100, 2), dtype=np.int32))
# 单独维护每个超像素的实际像素数（替代inside_index）
sp_counts = np.zeros(num_sp, dtype=np.int64)

@njit
def add_pixel(sp_id, x, y):
    count = sp_counts[sp_id]
    arr = sk[sp_id]
    # 空间不足时自动扩容
    if count == arr.shape[0]:
        sk[sp_id] = np.resize(arr, (arr.shape[0]*2, 2))
    sk[sp_id][count] = (x, y)
    sp_counts[sp_id] += 1

@njit
def get_sp_coords(sp_id):
    return sk[sp_id][:sp_counts[sp_id]]

优点 #

• 无需预先知道总像素数，动态扩容灵活
• numba类型化列表避免了Python列表的性能开销，读写效率接近纯numpy数组

为什么你的原方案/稀疏矩阵不合适 #

• 原三维数组：本质是用稠密数组存储稀疏数据，即使Mac延迟分配，随着填充量增加，内存占用会急剧上升，且大部分空间都是无效的
• Scipy稀疏矩阵：CSR适合静态稀疏矩阵运算，动态添加元素效率极低；LIL虽然修改方便，但存储格式（把x/y拆成连续元素）不利于坐标的向量运算，访问效率远不如紧凑数组

内容的提问来源于stack exchange，提问作者Chasname