人群聚集逻辑

一、只靠逻辑实现
http://www.xjishu.com/zhuanli/55/201810734133.html
图1是本发明提供的一种人群聚集检测方法的流程图。如图1所示，本发明实施例的一种人群聚集检测方法包括以下步骤：

s101：获取检测视频流：

获取被监控场所的监控视频流，将视频流中连续的每一帧图像作为分析处理图像。

s102：识别目标并计算目标坐标：

根据步骤s101获取的连续图像，通过先进的机器学习算法对图像进行处理，识别图像中的目标(人)并计算得到目标坐标，为相应的目标坐标点数据集，其中n为目标个数。

s103：根据所述目标和目标坐标计算目标局部密度：

根据步骤s102得到的数据集d，首先计算d中目标点两两之间的距离dij＝dist(pi，pj)，dist表示坐标点pi和pj之间的某种距离；然后计算每一个目标坐标点的密度其中函数dc＝κmr，r为单目标所占像素数量，κ∈(0，1)，m是设定的人群聚集圈内人群数量阈值。

s104：目标跟踪并获得目标移动方向：

根据步骤s102得到的目标、目标坐标，由跟踪算法(如kalmanfilter、kcf等跟踪算法)对每一帧图像进行多目标跟踪并计算获得各目标移动速度vi，然后计算第i个目标方向hi＝pk(x，y)-pi(x，y)，其中pi(x，y)是第i个目标坐标，pk(x)＝pi(x)+αvi，pk(y)＝pi(y)+avi。

s105：自动地构建人群聚集圈：

接下来对步骤s103得到的目标局部密度进行分析计算来自动地构建人群聚集圈。图2是人群聚集圈和位置计算的流程示意图。如图2所示，本发明中采用的人群聚集圈和位置计算包括以下步骤：

s201：计算度量值φi：

目标坐标点的密度ρi，计算φi用于描述点i到其他较高密度点之间的最小距离，那些有着比较大的密度ρi和很大的φi的点被认为是人群聚集的中心。

s202：计算目标点到中心点的距离：

根据度量值φi，计算每个目标点到各人群聚集中心点的距离

s203：获得各人群聚集圈和位置：

根据得到人群聚集度如果则确定了一个人群聚集圈，以此类推得到所有人群聚集圈和聚集圈中心位置。

s106：根据所述各人群聚集圈和目标移动方向判断人群聚集圈态势：

接下来对步骤s104得到的目标移动方向和步骤s105得到各人群聚集圈判断人群聚集圈态势。图3是具体实施例的人群聚集圈态势判断的流程示意图。如图3所示，本发明中判断人群聚集圈态势包括以下步骤：

s301：获得人群聚集圈方向hi：

设置人群聚集额定方向阈值为|ht|，根据步骤s4得到的各目标移动速度、方向和步骤s105人群聚集圈获得人群聚集圈方向hi，hi为各目标方向hi相加得到的向量。

s302：将空间划分为四个区域：

计算hi角度值θ并将空间划分为以下四个区域：

如果°0≤θ＜90°，则hi方向指向i区域；

如果°90≤θ＜180°，则hi方向指向ii区域；

如果°180≤θ＜270°，则hi方向指向iii区域；

如果°270≤θ＜360°，则hi方向指向iv区域。

s303：人群聚集圈态势判断：

根据方向hi和密度来判断人群聚集圈态势，分为以下十一种情况：

如果不变，|hi|＜ε，此人群聚集圈态势为静止；

如果变小，|hi|＜ε，此人群聚集圈态势为消散；

如果变大，|hi|＜ε，此人群聚集圈态势为内聚；

如果不变，ε＜|hi|＜|ht|，hi方向指向i区域，此人群聚集圈态势为慢速向i区域移动；

如果不变，ε＜|hi|＜|ht|，hi方向指向ii区域，此人群聚集圈态势为慢速向ii区域移动；

如果不变，ε＜|hi|＜|ht|，hi方向指向iii区域，此人群聚集圈态势为慢速向iii区域移动；

如果不变，ε＜|hi|＜|ht|，hi方向指向iv区域，此人群聚集圈态势为慢速向iv区域移动；

如果不变，|ht|＜|hi|，hi方向指向i区域，此人群聚集圈态势为快速向i区域移动；

如果不变，|ht|＜|hi|，hi方向指向ii区域，此人群聚集圈态势为快速向ii区域移动；

如果不变，|ht|＜|hi|，hi方向指向iii区域，此人群聚集圈态势为快速向iii区域移动；

如果不变，|ht|＜|hi|，hi方向指向iv区域，此人群聚集圈态势为快速向iv区域移动。

其中，ε是一个极小值。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

二、C++实现DBSCAN密度聚类算法
参考：http://www.zyiz.net/tech/detail-270770.html
代码：

/*
    DBSCAN Algorithm
    @author:TheQuiteSunshine
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
//为了便于可视化展示算法效果，引入OpenCV库。
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/core/core.hpp"
#include "opencv2/imgproc/imgproc.hpp"
using namespace cv;
 
/*
*   @样本点类型
*-- 邻域半径R内样本点的数量大于等于minpoints的点叫做核心点。
*-- 不属于核心点但在某个核心点的邻域内的点叫做边界点。
*-- 既不是核心点也不是边界点的是噪声点。
*/
enum ESampleType
{
    NOISE = 1,
    BORDER = 2,
    CORE = 3,
};
 
struct point
{
public:
    float x;
    float y;
    int cluster = 0; //所属类别（一个标识代号，属于同一类的样本具有相同的cluster）
 
    //邻域半径R内样本点的数量大于等于minpoints的点叫做核心点。
    //不属于核心点但在某个核心点的邻域内的点叫做边界点。既不是核心点也不是边界点的是噪声点
    int pointType = NOISE;       // 1:noise     2:border    3:core  （初始默认为噪声点）
    int pts = 0;                 //points in MinPts （指定领域内样本点的个数）
    vector<int> neighborCoreIdx; //对所有的corepoint，将其eps范围内的core point下标添加到vector neighborCoreIdx中
    int visited = 0;             //是否被遍历访问过
 
    point()
    {
    }
    point(float a, float b)
    {
        x = a;
        y = b;
        //cluster = c;
    }
};
 
float stringToFloat(string i)
{
    stringstream sf;
    float score = 0;
    sf << i;
    sf >> score;
    return score;
}
 
//读取文本文件，从中解析出数据。
vector<point> openFile(const char *dataset)
{
    fstream file;
    file.open(dataset, ios::in);
    if (!file)
    {
        cout << "Open File Failed!" << endl;
        vector<point> a;
        return a;
    }
 
    vector<point> data;
    int i = 1;
 
    while (!file.eof())
    {
        string temp;
        file >> temp;
        int split = temp.find(',', 0);
        point p(stringToFloat(temp.substr(0, split)), stringToFloat(temp.substr(split + 1, temp.length() - 1)));
        data.push_back(p);
    }
 
    file.close();
    cout << "successful!" << endl;
    return data;
}
 
//计算平面内两点之间的距离
float squareDistance(point a, point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
 
/** @brief   DBSCAN聚类算法
@param dataset：输入样本数据 [in][out]参数
@param Eps：领域半径
@param MinPts：聚类中心的下标
@return ：返回每个样本的类别，类别从1开始，0表示未分类或者分类失败
*/
void DBSCAN(vector<point> &dataset, float Eps, int MinPts)
{
    int count = 0;
    int len = dataset.size();
    //calculate pts
    cout << "计算各点的邻域数量" << endl;
 
    for (int i = 0; i < len; i++)
    {
        //特别注意 !!! 这里如果j从i开始，表明某点的邻域范围内样本数量包含自己，若j从i+1开始则不包含自己。
        for (int j = i; j < len; j++)
        {
            if (squareDistance(dataset[i], dataset[j]) < Eps)
            {
                dataset[i].pts++;
                dataset[j].pts++;
            }
        }
    }
 
    //core point ，若某个点在其领域Eps范围内的点个数>=MinPts，称该点为core point核心点
    cout << "寻找核心点" << endl;
    //核心点集合索引（索引为样本点原本的索引，从0开始）
    vector<int> corePtInxVec;
    for (int i = 0; i < len; i++)
    {
        if (dataset[i].pts >= MinPts)
        {
            dataset[i].pointType = CORE;
            dataset[i].cluster = (++count);
            corePtInxVec.push_back(i);
            printf("样本(%.1f, %.1f)的邻域点数量为:%d,被确立为核心点, cluster：%d\n", dataset[i].x, dataset[i].y, dataset[i].pts, dataset[i].cluster);
        }
    }
 
    //合并core point
    cout << "合并核心点" << endl;
    for (int i = 0; i < corePtInxVec.size(); i++)
    {
        for (int j = i + 1; j < corePtInxVec.size(); j++)
        {
            //对所有的corepoint，将其eps范围内的core point下标添加到vector corepts中
            if (squareDistance(dataset[corePtInxVec[i]], dataset[corePtInxVec[j]]) < Eps)
            {
                dataset[corePtInxVec[i]].neighborCoreIdx.push_back(corePtInxVec[j]);
                dataset[corePtInxVec[j]].neighborCoreIdx.push_back(corePtInxVec[i]);
 
                printf("核心点%.1f, %.1f)与核心点%.1f, %.1f)处在半径范围内，相互连接，可以合并\n",
                       dataset[corePtInxVec[i]].x, dataset[corePtInxVec[i]].y, dataset[corePtInxVec[j]].x, dataset[corePtInxVec[j]].y);
            }
        }
    }
 
    //对于所有的corepoint，采用深度优先的方式遍历每个core point的所有corepts，使得相互连接的core point具有相同的cluster编号
    for (int i = 0; i < corePtInxVec.size(); i++)
    {
        for (int j = 0; j < dataset[corePtInxVec[i]].neighborCoreIdx.size(); j++)
        {
            int idx = dataset[corePtInxVec[i]].neighborCoreIdx[j];
            dataset[idx].cluster = dataset[corePtInxVec[i]].cluster;
        }
    }
 
    //不属于核心点但在某个核心点的邻域内的点叫做边界点
    cout << "边界点，把边界点加入到靠近的核心点" << endl;
    //border point,joint border point to core point
    for (int i = 0; i < len; i++)
    {
        if (dataset[i].pointType == CORE) //忽略核心点
            continue;
 
        for (int j = 0; j < corePtInxVec.size(); j++)
        {
            int idx = corePtInxVec[j]; //核心点索引
            if (squareDistance(dataset[i], dataset[idx]) < Eps)
            {
                dataset[i].pointType = BORDER;
                dataset[i].cluster = dataset[idx].cluster;
                printf("样本(%.1f, %.1f)被确立为边界点, cluster：%d\n", dataset[i].x, dataset[i].y, dataset[i].cluster);
                break;
            }
        }
    }
 
    cout << "输出结果：" << endl;
    for (int i = 0; i < len; i++)
    {
        if (dataset[i].pointType == CORE)
        {
            printf("CORE: x:%.2f, y:%.2f cluster:%d\n", dataset[i].x, dataset[i].y, dataset[i].cluster);
        }
        else if (dataset[i].pointType == BORDER)
        {
            printf("BORDER: x:%.2f, y:%.2f cluster:%d\n", dataset[i].x, dataset[i].y, dataset[i].cluster);
        }
        else
        {
            printf("NOISE: x:%.2f, y:%.2f cluster:%d\n", dataset[i].x, dataset[i].y, dataset[i].cluster);
        }
    }
 
    // for(int i=0;i < corePoint.size(); i++)
    // {
    //      clustering<
    // }
}
 
/*
*@生成随机颜色
*/
cv::Scalar random_color()
{
    static cv::RNG _rng(10086);
    unsigned icolor = (unsigned)_rng;
    return cv::Scalar(icolor & 0xFF, (icolor >> 8) & 0xFF, (icolor >> 16) & 0xFF);
}
 
int main(int argc, char **argv)
{
    //加载数据
    vector<point> dataset = openFile("dataset.txt");
    float radius = 2.0; //邻域半径R
    int MinPts = 2;     //邻域半径R内样本点的数量大于等于minpoints的点叫做核心点
    //DBSCAN算法进行聚类
    DBSCAN(dataset, radius, MinPts);
 
    //设置了6种不同的颜色
    const int colorCnts = 6;
    cv::Scalar colors[] = {cv::Scalar(255, 100, 80), cv::Scalar(0, 255, 0), cv::Scalar(0, 0, 255),
                           cv::Scalar(0, 255, 255), cv::Scalar(255, 0, 255), cv::Scalar(255, 255, 0)};
 
    //画出原始数据分布图
    cv::Point offset(10, 10); //所有样本均加上这个偏移、防止离原点太近影响视觉显示效果
    cv::Mat originalMat = cv::Mat::zeros(cv::Size(300, 300), CV_8UC3);
    for (size_t i = 0; i < dataset.size(); i++)
    {
        cv::Point pt = offset + cv::Point(dataset[i].x * 10, dataset[i].y * 10);
        cv::circle(originalMat, pt, 2, cv::Scalar(0, 0, 255), 2);
    }
    cv::imshow("original data", originalMat);
 
    //画出结果示意图,不同的cluster样本点用不同的颜色表示。
    map<int, cv::Scalar> clusterMap;
    map<int, cv::Scalar>::iterator it;
 
    cv::Mat resultMat = cv::Mat::zeros(cv::Size(300, 300), CV_8UC3);
    cv::Scalar color;
    for (size_t i = 0; i < dataset.size(); i++)
    {
        it = clusterMap.find(dataset[i].cluster);
        if (it == clusterMap.end()) //首次出现，为该cluster随机分配一组颜色。
        {
            color = random_color();
            clusterMap.insert(std::make_pair(dataset[i].cluster, color));
        }
        else
            color = it->second;
 
        cv::Point pt = offset + cv::Point(dataset[i].x * 10, dataset[i].y * 10);
        cv::circle(resultMat, pt, 2, color, 2);
    }
    cv::imshow("cluster data", resultMat);
 
    cv::waitKey(0);
    getchar();
    return 0;
}
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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276

附程序所使用的dataset.txt文件：

0,0
3,8
2,2
1,1
5,3
4,8
6,3
5,4
6,4
7,5
12,4
12,5
12,6
13,4
17,8
18,9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16