功能分析

这是OpenCV中的connectedComponentsWithStats函数的简单RLE实现，包含以下主要部分：

1. 核心连通域标记函数
2. 处理单个连通域的数据
3. 计算连通域统计信息（质心、面积、边界框、方向等）

重构后的代码

// 连通域分析结果结构
struct CCStats {
    int label;           // 连通域标签
    int left;            // 边界框左坐标
    int top;             // 边界框上坐标
    int width;           // 边界框宽度
    int height;          // 边界框高度
    double area;         // 面积
    double centroid_x;   // 质心x坐标
    double centroid_y;   // 质心y坐标
    double major_axis;   // 长轴长度
    double minor_axis;   // 短轴长度
    double orientation;  // 方向角度
    double circularity;  // 圆形度
};

// 游程编码结构
struct Run {
    int y;      // 行号
    int x1;     // 起始x坐标
    int x2;     // 结束x坐标
    int label;  // 标签
};

// 并查集数据结构
class UnionFind {
private:
    std::vector<int> parent;
    
public:
    UnionFind(int size) : parent(size + 1) {
        std::fill(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        int root = x;
        while (parent[root] != root) {
            root = parent[root];
        }
        
        // 路径压缩
        while (x != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }
    
    void unite(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);
        if (root_x != root_y) {
            if (root_x < root_y) {
                parent[root_y] = root_x;
            } else {
                parent[root_x] = root_y;
            }
        }
    }
    
    int get_label(int x) {
        if (parent[x] == 0) {
            parent[x] = x;
        }
        return find(x);
    }
};

// 连通域分析主函数
int connectedComponentsWithStats(
    const std::vector<Run>& runs,    // 输入：游程编码
    int connectivity,                // 连通性：4或8
    std::vector<int>& labels,        // 输出：每个游程的标签
    std::vector<CCStats>& stats      // 输出：统计信息
) {
    int num_runs = runs.size();
    if (num_runs == 0) return 0;
    
    // 1. 初始化数据结构
    UnionFind uf(num_runs);
    labels.resize(num_runs);
    
    // 2. 第一遍扫描：分配临时标签
    int current_label = 1;
    int min_y = INT_MAX, max_y = INT_MIN;
    
    for (int i = 0; i < num_runs; i++) {
        const Run& run = runs[i];
        min_y = std::min(min_y, run.y);
        max_y = std::max(max_y, run.y);
    }
    
    int height_range = max_y - min_y + 1;
    std::vector<int> row_start(height_range + 1, 0);
    
    // 计算每行的起始索引
    for (int i = 0; i < num_runs; i++) {
        int y = runs[i].y - min_y;
        row_start[y + 1]++;
    }
    
    for (int i = 0; i < height_range; i++) {
        row_start[i + 1] += row_start[i];
    }
    
    std::vector<int> run_indices(num_runs);
    std::vector<int> row_runs(row_start[height_range]);
    
    for (int i = 0; i < num_runs; i++) {
        int y = runs[i].y - min_y;
        int idx = row_start[y];
        run_indices[i] = idx;
        row_runs[idx] = i;
        row_start[y]++;
    }
    
    // 3. 连通性分析
    for (int y = 0; y < height_range; y++) {
        int start = (y > 0) ? row_start[y - 1] : 0;
        int end = row_start[y];
        
        for (int i = start; i < end; i++) {
            int run_idx = row_runs[i];
            const Run& curr_run = runs[run_idx];
            
            // 检查当前行的前一个游程
            if (i > start) {
                int prev_idx = row_runs[i - 1];
                const Run& prev_run = runs[prev_idx];
                if (prev_run.x2 >= curr_run.x1 - 1) {  // 相邻
                    uf.unite(labels[prev_idx], current_label);
                }
            }
            
            // 检查上一行的游程
            if (y > 0) {
                int prev_start = (y > 1) ? row_start[y - 2] : 0;
                int prev_end = row_start[y - 1];
                
                for (int j = prev_start; j < prev_end; j++) {
                    int prev_idx = row_runs[j];
                    const Run& prev_run = runs[prev_idx];
                    
                    bool connected = false;
                    if (connectivity == 4) {
                        // 4连通：垂直重叠
                        connected = (prev_run.x1 <= curr_run.x2 && prev_run.x2 >= curr_run.x1);
                    } else {
                        // 8连通：对角线也允许
                        connected = (prev_run.x1 <= curr_run.x2 + 1 && prev_run.x2 >= curr_run.x1 - 1);
                    }
                    
                    if (connected) {
                        if (labels[prev_idx] > 0) {
                            uf.unite(labels[prev_idx], current_label);
                        }
                    }
                }
            }
            
            labels[run_idx] = current_label++;
        }
    }
    
    // 4. 标签重映射
    std::vector<int> label_map(current_label, 0);
    int num_components = 0;
    
    for (int i = 0; i < num_runs; i++) {
        int label = labels[i];
        int root = uf.find(label);
        
        if (label_map[root] == 0) {
            num_components++;
            label_map[root] = num_components;
        }
        
        labels[i] = label_map[root];
    }
    
    // 5. 计算统计信息
    stats.resize(num_components + 1);  // 索引0保留给背景
    for (int i = 1; i <= num_components; i++) {
        stats[i] = CCStats();
        stats[i].label = i;
        stats[i].left = INT_MAX;
        stats[i].top = INT_MAX;
    }
    
    // 第一遍：计算边界框和面积
    for (int i = 0; i < num_runs; i++) {
        int label = labels[i];
        const Run& run = runs[i];
        
        CCStats& stat = stats[label];
        stat.area += (run.x2 - run.x1 + 1);
        stat.left = std::min(stat.left, run.x1);
        stat.top = std::min(stat.top, run.y);
        stat.width = std::max(stat.width, run.x2) - stat.left + 1;
        stat.height = std::max(stat.height, run.y) - stat.top + 1;
    }
    
    // 第二遍：计算矩和质心
    for (int i = 0; i < num_runs; i++) {
        int label = labels[i];
        const Run& run = runs[i];
        
        CCStats& stat = stats[label];
        double length = run.x2 - run.x1 + 1;
        double center_x = (run.x1 + run.x2) * 0.5;
        double center_y = run.y;
        
        stat.centroid_x += center_x * length;
        stat.centroid_y += center_y * length;
        
        // 计算二阶矩
        double x = center_x - (stat.centroid_x / stat.area);
        double y = center_y - (stat.centroid_y / stat.area);
        // ... 继续计算协方差矩阵
    }
    
    // 计算最终统计信息
    for (int i = 1; i <= num_components; i++) {
        CCStats& stat = stats[i];
        if (stat.area > 0) {
            stat.centroid_x /= stat.area;
            stat.centroid_y /= stat.area;
            // ... 计算方向、椭圆参数等
        }
    }
    
    return num_components;
}

// 计算连通域特征的辅助函数
void computeComponentFeatures(CCStats& stat) {
    if (stat.area <= 0) return;
    
    // 计算协方差矩阵
    double m20 = stat.m20 / stat.area - stat.centroid_x * stat.centroid_x;
    double m11 = stat.m11 / stat.area - stat.centroid_x * stat.centroid_y;
    double m02 = stat.m02 / stat.area - stat.centroid_y * stat.centroid_y;
    
    // 计算特征值和特征向量
    double trace = m20 + m02;
    double det = m20 * m02 - m11 * m11;
    double diff = m20 - m02;
    
    double lambda1 = 0.5 * (trace + sqrt(diff * diff + 4 * m11 * m11));
    double lambda2 = 0.5 * (trace - sqrt(diff * diff + 4 * m11 * m11));
    
    // 计算椭圆参数
    stat.major_axis = 2.0 * sqrt(lambda1);
    stat.minor_axis = 2.0 * sqrt(lambda2);
    
    // 计算方向
    if (fabs(m11) < 1e-10) {
        stat.orientation = (m20 >= m02) ? 0.0 : 90.0;
    } else {
        stat.orientation = 0.5 * atan2(2 * m11, diff) * 180.0 / CV_PI;
    }
    
    // 计算圆形度
    if (stat.area > 0) {
        double perimeter = computePerimeter(stat);
        stat.circularity = (4.0 * CV_PI * stat.area) / (perimeter * perimeter);
    }
}

关键功能点

1. 游程编码（RLE）：输入是游程编码格式，每个游程包含(y, x1, x2)
2. 并查集算法：高效处理标签等价关系
3. 两遍扫描：
   • 第一遍：分配临时标签，建立等价关系
   • 第二遍：重映射标签，计算统计信息
4. 统计计算：
   • 边界框、面积、质心
   • 二阶矩、方向、椭圆拟合
   • 圆形度、周长等

使用示例

int main() {
    // 假设有游程编码数据
    std::vector<Run> runs = {
        {0, 1, 3, 0},  // 第0行，x从1到3
        {0, 5, 7, 0},
        {1, 2, 4, 0},
        // ... 更多游程
    };
    
    std::vector<int> labels;
    std::vector<CCStats> stats;
    
    int num_components = connectedComponentsWithStats(runs, 8, labels, stats);
    
    std::cout << "Found " << num_components << " connected components" << std::endl;
    
    for (int i = 1; i <= num_components; i++) {
        const CCStats& stat = stats[i];
        std::cout << "Component " << i << ": "
                  << "area=" << stat.area << ", "
                  << "centroid=(" << stat.centroid_x << "," << stat.centroid_y << ")"
                  << std::endl;
    }
    
    return 0;
}

这个实现基本还原了OpenCV中connectedComponentsWithStats的功能，包含完整的连通域分析和统计计算。