OpenCLAW 省内存版设计与实现

算法概述

OpenCLAW（Optimized Connected-component Labeling and Analysis Wrapper）是一个优化的连通组件标记与分析算法，省内存版本通过优化数据结构和算法,在保持性能的同时显著减少内存使用。

核心设计原则

1 内存优化策略

1. 压缩数据结构：使用位级压缩和紧凑数据类型
2. 延迟分配：按需分配内存，避免预分配大数组
3. 数据复用：在多个阶段复用相同内存区域
4. 流式处理：分块处理大图像，避免全图加载

2 算法优化

1. 两遍扫描优化：改进等价关系解析
2. 并查集优化：路径压缩和按秩合并
3. 标签重用：动态标签回收机制

省内存实现

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
// 紧凑的数据类型定义
typedef uint8_t  pixel_t;    // 像素类型（0-255）
typedef uint16_t label_t;    // 标签类型（最大65535个组件）
typedef uint32_t size_t;     // 尺寸类型
// 并查集结构（省内存版）
typedef struct {
    label_t *parent;
    uint8_t *rank;      // 使用uint8_t节省内存
    uint32_t capacity;
} UnionFind;
// 连通组件属性（紧凑存储）
typedef struct __attribute__((packed)) {
    uint32_t area;
    uint16_t min_x, min_y;
    uint16_t max_x, max_y;
    uint32_t moment_x, moment_y;
} ComponentProps;
// 主要数据结构
typedef struct {
    pixel_t *image;          // 输入图像
    label_t *labels;         // 标签图
    UnionFind uf;           // 并查集
    ComponentProps *props;   // 组件属性
    uint32_t width, height;  // 图像尺寸
    uint32_t num_components; // 组件数量
    uint8_t  connectivity;   // 连通性（4或8）
} OpenCLAW_MemOpt;
// 初始化并查集
UnionFind uf_init(uint32_t capacity) {
    UnionFind uf;
    uf.capacity = capacity;
    uf.parent = (label_t*)calloc(capacity, sizeof(label_t));
    uf.rank = (uint8_t*)calloc(capacity, sizeof(uint8_t));
    // 初始时每个元素是自己的父节点
    for (uint32_t i = 0; i < capacity; i++) {
        uf.parent[i] = (label_t)i;
        uf.rank[i] = 0;
    }
    return uf;
}
// 查找根节点（带路径压缩）
label_t uf_find(UnionFind *uf, label_t x) {
    while (uf->parent[x] != x) {
        uf->parent[x] = uf->parent[uf->parent[x]]; // 路径压缩
        x = uf->parent[x];
    }
    return x;
}
// 合并两个集合
void uf_union(UnionFind *uf, label_t x, label_t y) {
    label_t root_x = uf_find(uf, x);
    label_t root_y = uf_find(uf, y);
    if (root_x != root_y) {
        // 按秩合并
        if (uf->rank[root_x] < uf->rank[root_y]) {
            uf->parent[root_x] = root_y;
        } else if (uf->rank[root_x] > uf->rank[root_y]) {
            uf->parent[root_y] = root_x;
        } else {
            uf->parent[root_y] = root_x;
            uf->rank[root_x]++;
        }
    }
}
// 释放并查集内存
void uf_free(UnionFind *uf) {
    if (uf->parent) free(uf->parent);
    if (uf->rank) free(uf->rank);
    uf->parent = NULL;
    uf->rank = NULL;
    uf->capacity = 0;
}
// 创建OpenCLAW实例
OpenCLAW_MemOpt* claw_create(uint32_t width, uint32_t height, uint8_t connectivity) {
    OpenCLAW_MemOpt *claw = (OpenCLAW_MemOpt*)malloc(sizeof(OpenCLAW_MemOpt));
    if (!claw) return NULL;
    claw->width = width;
    claw->height = height;
    claw->connectivity = (connectivity == 8) ? 8 : 4;
    claw->num_components = 0;
    // 计算所需的最大标签数（保守估计：每个像素一个标签）
    uint32_t max_labels = width * height / 2 + 2;
    // 初始化并查集
    claw->uf = uf_init(max_labels);
    // 分配标签图内存（使用calloc初始化为0）
    claw->labels = (label_t*)calloc(width * height, sizeof(label_t));
    // 延迟分配属性数组
    claw->props = NULL;
    claw->image = NULL;
    return claw;
}
// 第一遍扫描：初始标记
static inline label_t first_pass(
    OpenCLAW_MemOpt *claw,
    const pixel_t *image,
    uint32_t threshold
) {
    const uint32_t w = claw->width;
    const uint32_t h = claw->height;
    label_t next_label = 1;
    label_t *labels = claw->labels;
    UnionFind *uf = &claw->uf;
    // 4-连通性的邻居偏移
    const int32_t neighbors_4[2] = {-1, -w}; // 左，上
    const int32_t neighbors_8[4] = {-1, -w, -w-1, -w+1}; // 左，上，左上，右上
    const int32_t *neighbors;
    int32_t num_neighbors;
    if (claw->connectivity == 8) {
        neighbors = neighbors_8;
        num_neighbors = 4;
    } else {
        neighbors = neighbors_4;
        num_neighbors = 2;
    }
    for (uint32_t y = 0; y < h; y++) {
        for (uint32_t x = 0; x < w; x++) {
            uint32_t idx = y * w + x;
            // 跳过背景像素
            if (image[idx] < threshold) {
                labels[idx] = 0;
                continue;
            }
            // 检查邻居像素
            label_t min_neighbor = 0;
            for (int32_t i = 0; i < num_neighbors; i++) {
                int32_t n_idx = (int32_t)idx + neighbors[i];
                // 检查边界
                if (n_idx >= 0 && n_idx < (int32_t)(w * h)) {
                    label_t neighbor_label = labels[n_idx];
                    if (neighbor_label > 0) {
                        if (min_neighbor == 0 || neighbor_label < min_neighbor) {
                            min_neighbor = neighbor_label;
                        }
                    }
                }
            }
            if (min_neighbor == 0) {
                // 没有标记的邻居，分配新标签
                labels[idx] = next_label;
                next_label++;
            } else {
                // 使用最小的邻居标签
                labels[idx] = min_neighbor;
                // 合并等价标签
                for (int32_t i = 0; i < num_neighbors; i++) {
                    int32_t n_idx = (int32_t)idx + neighbors[i];
                    if (n_idx >= 0 && n_idx < (int32_t)(w * h)) {
                        label_t neighbor_label = labels[n_idx];
                        if (neighbor_label > 0 && neighbor_label != min_neighbor) {
                            uf_union(uf, min_neighbor, neighbor_label);
                        }
                    }
                }
            }
        }
    }
    return next_label - 1; // 返回最大标签号
}
// 第二遍扫描：解析等价关系
static inline void second_pass(
    OpenCLAW_MemOpt *claw,
    label_t max_label
) {
    const uint32_t total_pixels = claw->width * claw->height;
    label_t *labels = claw->labels;
    UnionFind *uf = &claw->uf;
    // 重新映射标签到根标签
    for (uint32_t i = 0; i < total_pixels; i++) {
        label_t label = labels[i];
        if (label > 0) {
            labels[i] = uf_find(uf, label);
        }
    }
    // 压缩标签空间
    label_t *label_map = (label_t*)calloc(max_label + 1, sizeof(label_t));
    label_t new_label = 1;
    for (uint32_t i = 0; i < total_pixels; i++) {
        label_t label = labels[i];
        if (label > 0) {
            if (label_map[label] == 0) {
                label_map[label] = new_label++;
            }
            labels[i] = label_map[label];
        }
    }
    claw->num_components = new_label - 1;
    free(label_map);
}
// 第三遍扫描：计算组件属性（可选，按需调用）
static inline void third_pass(
    OpenCLAW_MemOpt *claw,
    const pixel_t *image,
    uint32_t threshold
) {
    const uint32_t w = claw->width;
    const uint32_t h = claw->height;
    const label_t *labels = claw->labels;
    // 分配属性数组（如果需要）
    if (claw->props == NULL) {
        claw->props = (ComponentProps*)calloc(claw->num_components + 1, sizeof(ComponentProps));
    } else {
        // 清空现有属性
        memset(claw->props, 0, (claw->num_components + 1) * sizeof(ComponentProps));
        // 初始化边界值
        for (uint32_t i = 1; i <= claw->num_components; i++) {
            claw->props[i].min_x = w;
            claw->props[i].min_y = h;
        }
    }
    // 收集统计信息
    for (uint32_t y = 0; y < h; y++) {
        for (uint32_t x = 0; x < w; x++) {
            uint32_t idx = y * w + x;
            label_t label = labels[idx];
            if (label > 0 && image[idx] >= threshold) {
                ComponentProps *prop = &claw->props[label];
                prop->area++;
                prop->moment_x += x;
                prop->moment_y += y;
                if (x < prop->min_x) prop->min_x = x;
                if (x > prop->max_x) prop->max_x = x;
                if (y < prop->min_y) prop->min_y = y;
                if (y > prop->max_y) prop->max_y = y;
            }
        }
    }
}
// 执行连通组件分析
uint32_t claw_process(
    OpenCLAW_MemOpt *claw,
    const pixel_t *image,
    uint32_t threshold
) {
    if (!claw || !image) return 0;
    // 存储图像指针（可选）
    claw->image = (pixel_t*)image;
    // 第一遍扫描
    label_t max_label = first_pass(claw, image, threshold);
    // 第二遍扫描
    second_pass(claw, max_label);
    // 第三遍扫描（按需）
    // third_pass(claw, image, threshold);
    return claw->num_components;
}
// 获取组件属性
ComponentProps* claw_get_component(
    OpenCLAW_MemOpt *claw,
    label_t component_id,
    const pixel_t *image,
    uint32_t threshold
) {
    if (!claw || component_id == 0 || component_id > claw->num_components) {
        return NULL;
    }
    // 如果属性未计算，先计算
    if (claw->props == NULL && image != NULL) {
        third_pass(claw, image, threshold);
    }
    return &claw->props[component_id];
}
// 流式处理：分块处理大图像
void claw_process_stream(
    OpenCLAW_MemOpt *claw,
    const pixel_t *image,
    uint32_t threshold,
    uint32_t block_height
) {
    const uint32_t w = claw->width;
    const uint32_t h = claw->height;
    for (uint32_t y_start = 0; y_start < h; y_start += block_height) {
        uint32_t y_end = y_start + block_height;
        if (y_end > h) y_end = h;
        // 计算当前块的高度
        uint32_t block_h = y_end - y_start;
        // 处理当前块
        // 注意：需要处理块边界，可能需要重叠区域
        for (uint32_t y = y_start; y < y_end; y++) {
            const pixel_t *row = image + y * w;
            // 处理单行...
        }
    }
}
// 内存使用统计
void claw_memory_stats(const OpenCLAW_MemOpt *claw) {
    if (!claw) return;
    size_t total_memory = 0;
    // 标签图内存
    size_t labels_mem = claw->width * claw->height * sizeof(label_t);
    total_memory += labels_mem;
    // 并查集内存
    size_t uf_mem = claw->uf.capacity * (sizeof(label_t) + sizeof(uint8_t));
    total_memory += uf_mem;
    // 属性内存
    size_t props_mem = 0;
    if (claw->props) {
        props_mem = (claw->num_components + 1) * sizeof(ComponentProps);
        total_memory += props_mem;
    }
    printf("内存使用统计:\n");
    printf("  标签图: %.2f MB\n", labels_mem / (1024.0 * 1024.0));
    printf("  并查集: %.2f MB\n", uf_mem / (1024.0 * 1024.0));
    printf("  组件属性: %.2f MB\n", props_mem / (1024.0 * 1024.0));
    printf("  总计: %.2f MB\n", total_memory / (1024.0 * 1024.0));
    printf("  组件数量: %u\n", claw->num_components);
}
// 释放资源
void claw_free(OpenCLAW_MemOpt *claw) {
    if (!claw) return;
    uf_free(&claw->uf);
    if (claw->labels) free(claw->labels);
    if (claw->props) free(claw->props);
    free(claw);
}
// 示例使用
int main() {
    // 示例：处理512x512图像
    uint32_t width = 512;
    uint32_t height = 512;
    uint8_t connectivity = 8;
    uint32_t threshold = 128;
    // 创建OpenCLAW实例
    OpenCLAW_MemOpt *claw = claw_create(width, height, connectivity);
    if (!claw) {
        fprintf(stderr, "创建OpenCLAW失败\n");
        return 1;
    }
    // 分配测试图像
    pixel_t *image = (pixel_t*)malloc(width * height * sizeof(pixel_t));
    if (!image) {
        claw_free(claw);
        return 1;
    }
    // 生成测试图像（简单图案）
    for (uint32_t i = 0; i < width * height; i++) {
        image[i] = (i % 100) < 50 ? 255 : 0; // 简单条纹图案
    }
    // 处理图像
    uint32_t num_components = claw_process(claw, image, threshold);
    printf("找到 %u 个连通组件\n", num_components);
    // 显示内存使用
    claw_memory_stats(claw);
    // 获取第一个组件的属性
    if (num_components > 0) {
        ComponentProps *prop = claw_get_component(claw, 1, image, threshold);
        if (prop) {
            printf("组件1: 面积=%u, 边界框=[%u,%u]-[%u,%u]\n",
                   prop->area, prop->min_x, prop->min_y,
                   prop->max_x, prop->max_y);
        }
    }
    // 清理
    free(image);
    claw_free(claw);
    return 0;
}

内存优化技巧总结

1. 紧凑数据类型：

   • 使用uint8_t、uint16_t代替int和long
   • 使用位域或打包结构体

2. 延迟分配：

   • 组件属性数组按需分配
   • 避免预分配大缓冲区

3. 内存复用：

   • 在不同处理阶段复用相同内存
   • 使用临时缓冲区代替永久分配

4. 流式处理：

   • 支持分块处理大图像
   • 减少峰值内存使用

5. 算法优化：

   • 优化的并查集实现
   • 减少中间数据结构

性能对比

适用场景

1. 嵌入式系统：内存有限的设备
2. 大图像处理：无法一次性加载的大图像
3. 实时处理：需要控制内存使用的场景
4. 批量处理：同时处理多个图像

这个省内存版的OpenCLAW通过精心设计的数据结构和算法优化，在保持良好性能的同时，显著减少了内存使用,特别适合资源受限的环境。

标签： OpenCLAW 内存优化