Fork me on GitHub

队列的简单应用

发表于 | 分类于 | | 本文总阅读量 次
本文用队列实现了一个简单的应用---图元识别。该实例可以演化成的多种问题都可以用队列来求解。

1. 队列的简单应用汇总

1.1. 图元识别

问题描述：数字化图像是一个 m*m 的像素矩阵。在单色图像中，每个像素的值要么为0，要么为1。值为1的像素表示图元上的一个点，称其为图元像素。两个像素是相邻的，是指它们左右相邻或上下相邻。像个相邻的图元像素是同一个图元的像素。图元识别的目的就是给图元像素做标记，使两个像素标记相同，当且仅当它们是同一个图元的像素。

1
2
3
4
5
6
                                |    0 1 0 1 1           0 2 0 3 3
                                |    0 1 1 0 1           0 2 2 0 3
0 1 1           0 2 2           |    0 0 1 0 1           0 0 2 0 3
1 0 1           3 0 2           |    1 0 0 0 1           4 0 0 0 3
1 1 0           3 3 0           |    1 1 0 1 1           4 4 0 3 3
a1) 3*3的图像   a2)已标记的图元   |  b1) 5*5的图像       b2) 已标记的图元

在上图中，图元像素都做了标记，两个像素标记相同，当且仅当它们属于同一个图元，用数字 2，3，4… 作为图元标记。

求解策略：通过扫描像素来识别图元，扫描的方式是逐行扫描，每一行逐行扫描。当扫描到一个未标记的图元像素时，给它一个图元标记。然后把这个图元像素作为一个新图元的种子，通过识别和标记所有与该种子相邻的图元像素，来寻找新图元剩余的像素。这个过程一直持续到没有新的、未标记的、相邻的图元像素为止。

标记图元像素的程序用到很多技巧：用 0 值像素在图像四周建立“围墙”；用数组 offset 来寻找与给定像素相邻的像素。借助一个队列（也可以是个栈），来存储本身已经标记，而其相邻位置尚未标记的方格。

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
#include <iostream>
#include <queue>

using namespace std;

/* 图元识别 */
typedef struct position{
    int row;
    int col;
}position;
vector<vector<int> > pixel;     // 数字化图像，方形
int size;                       // 数字化图像尺寸
void labelComponents(){
    // 给图元编号

    // 初始化数组 offset
    position offset[4];
    offset[0].row = 0; offset[0].col = 1;   // 右
    offset[1].row = 1; offset[1].col = 0;   // 下
    offset[2].row = 0, offset[2].col = -1;  // 左
    offset[3].row = -1; offset[3].col = 0;  // 上

    // 初始化 0 值像素围墙
    for (int i = 0; i <= size + 1; ++i){
        pixel[0][i] = pixel[size + 1][i] = 0;       // 底部和顶部
        pixel[i][0] = pixel[i][size + 1] = 0;       // 左和右
    }

    int numOfNbrs = 4;          // 一个像素的相邻位置数
    // 扫描所有像素，标记图元
    queue<position> q;
    position here, nbr;
    int id = 1;                 // 图元 id
    for (int r = 1; r <= size; ++r){            // 图像的行 r
        for (int c = 1; c <= size; ++c){        // 图像的列 c
            if (pixel[r][c] == 1){               // 新图源
                pixel[r][c] = ++id;             // 取下一个图元
                here.row = r;
                here.col = c;

                while (true){                   // 寻找其他图元
                    for (int i = 0; i < numOfNbrs; ++i){        // 检查所有相邻位置
                        nbr.row = here.row + offset[i].row;
                        nbr.col = here.col + offset[i].col;
                        if (pixel[nbr.row][nbr.col] == 1){      // 当前图元的一部分
                            pixel[nbr.row][nbr.col] = id;
                            q.push(nbr);
                        }
                    }
                    // 图元中任意未考察的像素
                    if (q.empty()) break;
                    here = q.front();                   // 一个图像的图元
                    q.pop();
                }
            }
        }
    }
}

/* main 函数 */
int main(int argc, char **argv)
{
    /* 图元问题 */
    size = 3;
    int temp[5][5] = {
        {0, 0, 0, 0, 0}, 
        {0, 0, 1, 1, 0},
        {0, 1, 0, 1, 0},
        {0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0}};
    
    pixel.resize(5);
    for (int i = 0; i < 5; ++i){
        pixel[i].assign(&temp[i][0], &temp[i][5]);
    }

    labelComponents();

    for (int i = 1; i <= size; ++i){
        for (int j = 1; j <= size; ++j){
            cout << pixel[i][j] << " ";
        }
        cout << endl;
    }
    return 1;
}

时间复杂度：函数 labelComponents 总的时间复杂度为 O(m^2)

1.2. 工厂仿真

略