0%

基于区域的图像分割——区域分裂与合并

Posted on Edited on In Valine:

​ 分裂与合并是一种区域分割方式，将图像划分成不相交的区域，以某一检测准则从四叉树数据结构的任一层开始，对区域进行分裂或合并。并逐步改善区域划分的性能，直到最后将图像分成数量最小的均匀区域为止。

img.jpg

result.jpg

算法

步骤

  1. 定义用于同质性的标准；
  2. 将图像分成相等大小的区域；
  3. 计算每个区域的同质性；
  4. 如果区域同质，则将其与邻居合并；
  5. 重复该过程，直到所有区域均通过均一性测试。

image.png

同质性

​ 可有多种同质性的定义方式，比如：

  • 方差-灰度方差

    image.png

    当区域方差小于指定值时，则该区域符合同质性。

C++实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <iostream>
#include <opencv2/opencv.hpp>
using namespace cv;
using namespace std;

struct Block{
    int row; //起始行
    int col; //起始列
    int height; //高度
    int width; //宽度
}; //区域


/**
 计算区域的灰度方差
 img为原图像，blocks为区域集
 */
double variance(Mat img, vector<Block> blocks){
    // 求得区域方差
    double ave_I = 0; //区域平均灰度值
    int aero = 0; //区域集面积
    for (int i = 0; i < blocks.size(); i++) {
        for (int nrow = blocks[i].row; nrow < blocks[i].row+blocks[i].height; nrow++) {
            for (int ncol = blocks[i].col; ncol < blocks[i].col+blocks[i].width; ncol++) {
                ave_I += img.ptr<uchar>(nrow)[ncol];
            }
        }
        aero += blocks[i].height * blocks[i].width;
    }
    ave_I /= double(aero);
    
    double v = 0; //区域灰度方差
    for (int i = 0; i < blocks.size(); i++) {
        for (int nrow = blocks[i].row; nrow < blocks[i].row+blocks[i].height; nrow++) {
            for (int ncol = blocks[i].col; ncol < blocks[i].col+blocks[i].width; ncol++) {
                v += (img.ptr<uchar>(nrow)[ncol] - ave_I)*(img.ptr<uchar>(nrow)[ncol] - ave_I);
            }
        }
    }
    v /= double(aero - 1);
    return v;
}


/**
 画线
 */
void drawLines(Mat &img, vector<vector<Block>> homo_blocks){
    for (int i = 0; i < homo_blocks.size(); i++) {
        Mat linePic = Mat::zeros(img.size(), CV_8UC1);
        for (int j = 0; j < homo_blocks[i].size(); j++) {
            // 上下边缘
            for (int ncol = homo_blocks[i][j].col; ncol < homo_blocks[i][j].col+homo_blocks[i][j].width; ncol++) {
                // 上边缘
                int I = linePic.ptr<uchar>(homo_blocks[i][j].row)[ncol];
                if (I == 0) { //如果为黑，还未划线
                    linePic.ptr<uchar>(homo_blocks[i][j].row)[ncol] = 255;
                } else if (I == 255) { //已划线则去掉线
                    linePic.ptr<uchar>(homo_blocks[i][j].row)[ncol] = 0;
                }
                // 下边缘
                I = linePic.ptr<uchar>(homo_blocks[i][j].row+homo_blocks[i][j].height)[ncol];
                if (I == 0) { //如果为黑，还未划线
                    linePic.ptr<uchar>(homo_blocks[i][j].row+homo_blocks[i][j].height)[ncol] = 255;
                } else if (I == 255) { //已划线则去掉线
                    linePic.ptr<uchar>(homo_blocks[i][j].row+homo_blocks[i][j].height)[ncol] = 0;
                }
            }
            // 左右边缘
            for (int nrow = homo_blocks[i][j].row; nrow < homo_blocks[i][j].row+homo_blocks[i][j].height; nrow++) {
                // 左边缘
                int I = linePic.ptr<uchar>(nrow)[homo_blocks[i][j].col];
                if (I == 0) { //如果为黑，还未划线
                    linePic.ptr<uchar>(nrow)[homo_blocks[i][j].col] = 255;
                } else if (I == 255) { //已划线则去掉线
                    linePic.ptr<uchar>(nrow)[homo_blocks[i][j].col] = 0;
                }
                // 右边缘
                I = linePic.ptr<uchar>(nrow)[homo_blocks[i][j].col+homo_blocks[i][j].width];
                if (I == 0) { //如果为黑，还未划线
                    linePic.ptr<uchar>(nrow)[homo_blocks[i][j].col+homo_blocks[i][j].width] = 255;
                } else if (I == 255) { //已划线则去掉线
                    linePic.ptr<uchar>(nrow)[homo_blocks[i][j].col+homo_blocks[i][j].width] = 0;
                }
            }
        }
        for (int nrow = 0; nrow < img.rows; nrow++) {
            for (int ncol = 0; ncol < img.cols; ncol++) {
                if (linePic.ptr<uchar>(nrow)[ncol] == 255) {
                    img.ptr<uchar>(nrow)[ncol] = 255;
                }
            }
        }
    }
}


/**
 区域分裂与合并
 img为原图像，result为处理后的图像，threshold为方差阈值
 */
void splitMerge (Mat img, Mat &result, double threshold){
    Block init_block = {
        .row = 0,
        .col = 0,
        .height = img.rows,
        .width = img.cols
    }; //初始区域
    vector<Block> blocks; //不符合同质性区域集
    vector<vector<Block>> homo_blocks; //符合同质性的区域集
    
    blocks.push_back(init_block); //将初始区域压入不符合同质性区域集
    
    // 分裂与合并的迭代
    while (!blocks.empty()) {
        // 取出一个不符合同质性的区域
        Block current_block = blocks.back();
        blocks.pop_back();
        
        // 面积为8以上可分
        if (current_block.height * current_block.width >= 8) {
            Block child_blocks[4] = {
                {.row = current_block.row, .col = current_block.col, .height = (current_block.height+1)/2, .width = (current_block.width+1)/2},
                {.row = current_block.row, .col = current_block.col+(current_block.width+1)/2, .height = (current_block.height+1)/2, .width = current_block.width-(current_block.width+1)/2},
                {.row = current_block.row+(current_block.height+1)/2, .col = current_block.col, .height = current_block.height-(current_block.height+1)/2, .width = (current_block.width+1)/2},
                {.row = current_block.row+(current_block.height+1)/2, .col = current_block.col+(current_block.width+1)/2, .height = current_block.height-(current_block.height+1)/2, .width = current_block.width-(current_block.width+1)/2}
            }; //区域分裂成四块子区域
            
            // 判断子区域是否具有同质性
            for (int i = 0; i < 4; i++) {
                vector<Block> c_block = {child_blocks[i]};
                if (variance(img, c_block) <= threshold) { //如果具有同质性（方差小于阈值），进行合并
                    // 如果符合同质性的区域集为空
                    if (homo_blocks.size() == 0) {
                        homo_blocks.push_back(c_block); //将该子区域压入符合同质性的区域集
                    } else{
                        // 遍历符合同质性的区域集
                        int n;
                        double min_v = 0;
                        int min_n = 0;
                        for (n = 0; n < homo_blocks.size(); n++) {
                            vector<Block> bk = homo_blocks[n];
                            bk.push_back(child_blocks[i]);
                            if (n == 0) {
                                min_v = variance(img, bk);
                            } else{
                                if (variance(img, bk) < min_v) {
                                    min_v = variance(img, bk);
                                    min_n = n;
                                }
                            }
                        }
                        // 需合并，修改添加入区域
                        if (min_v <= threshold) {
                            vector<Block> bk = homo_blocks[min_n];
                            bk.push_back(child_blocks[i]);
                            homo_blocks[min_n] = bk;
                        } else { //不需合并，直接加入该区域
                            homo_blocks.push_back(c_block);
                        }
                    }
                }else{ //如果不具有同质性
                    blocks.push_back(child_blocks[i]); //压入不符合同质性区域集
                }
            }
        }
    }
    
    drawLines(result, homo_blocks);
}


int main() {
    Mat img,result;
    img = imread("img.jpg", IMREAD_GRAYSCALE); //获取原图的灰度图像
    // 读取图片失败，则停止
    if (img.empty()) {
        printf("读取图像文件失败");
        system("pause");
        return -1;
    }
    result = img.clone();
    double threshold = 200; //方差阈值
    splitMerge(img, result, threshold); //区域分裂与合并
    
    // 图像显示
    imshow("img",img);
    imshow("result",result);
    imwrite("result.jpg", result);
    waitKey(); //等待键值输入
    
    return 0;
}

结果

原图像：

img.jpg

​ 该图片由HOerwin56在Pixabay上发布

处理后的图像：

result.jpg