forked from cristi-zz/pi_2020_vc_base
-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithms.cpp
137 lines (113 loc) · 3.88 KB
/
algorithms.cpp
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
#include "stdafx.h"
#include "common.h"
#include "algorithms.h"
#include <random>
std::default_random_engine gen;
std::uniform_int_distribution<int> d(0, 255);
// k-means clustering
std::vector<algorithms::Point> algorithms::kMeansClustering(std::vector<algorithms::Point>* points, int iterations, int Kclusters, double(*heuristicFunc)(algorithms::Point p, algorithms::Point other)) {
// initializing the clusters
std::vector<algorithms::Point> centroids;
srand(time(0));
for (int i = 0; i < Kclusters; i++) {
centroids.push_back(points->at(rand() % points->size()));
}
for (int i = 0; i < iterations; i++) {
// assigning points to a cluster
for (std::vector<algorithms::Point>::iterator centroidIt = std::begin(centroids); centroidIt != std::end(centroids); centroidIt++) {
long long int clusterId = centroidIt - begin(centroids);
for (std::vector<algorithms::Point>::iterator pointIt = points->begin(); pointIt != points->end(); pointIt++) {
algorithms::Point point = *pointIt;
double heuristic = centroidIt->heuristic(point, heuristicFunc);
if (heuristic < point.minHeuristic) {
point.minHeuristic = heuristic;
point.cluster = clusterId;
}
*pointIt = point;
}
}
// computing new centroids
std::vector<int> nPoints;
std::vector<double> sumX, sumY;
for (int j = 0; j < Kclusters; ++j) {
nPoints.push_back(0);
sumX.push_back(0.0);
sumY.push_back(0.0);
}
for (std::vector<algorithms::Point>::iterator pointIt = points->begin(); pointIt != points->end(); pointIt++) {
long long int clusterId = pointIt->cluster;
nPoints[clusterId] += 1;
sumX[clusterId] += pointIt->x;
sumY[clusterId] += pointIt->y;
pointIt->minHeuristic = __MAX_VALUE__;
}
for (std::vector<algorithms::Point>::iterator centroidIt = std::begin(centroids); centroidIt != std::end(centroids); centroidIt++) {
int clusterId = centroidIt - std::begin(centroids);
centroidIt->x = sumX[clusterId] / nPoints[clusterId];
centroidIt->y = sumY[clusterId] / nPoints[clusterId];
}
}
return centroids;
}
// binned histogram
std::vector<int> algorithms::binnedHistogram(Mat_<uchar> src, int numberOfBins) {
int height = src.rows;
int width = src.cols;
std::vector<int> hist(numberOfBins);
std::fill(hist.begin(), hist.end(), 0);
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
if (src(i, j) / (256 / numberOfBins) > numberOfBins - 1) {
hist[numberOfBins - 1]++;
}
else {
hist[src(i, j) / (256 / numberOfBins)]++;
}
}
}
return hist;
}
// color comparison
bool algorithms::compareColors(Vec3b colorA, Vec3b colorB) {
return colorA[0] == colorB[0] && colorA[1] == colorB[1] && colorA[2] == colorB[2];
}
// generates a random color
std::vector<Vec3b> algorithms::getRandomColors(int size) {
std::vector<Vec3b> colors(size, Vec3b(255, 255, 255));
for (int i = 0; i < size; i++) {
uchar b = d(gen);
uchar g = d(gen);
uchar r = d(gen);
colors[i] = Vec3b(b, g, r);
}
return colors;
}
// calculates the euclidian distance between 2 point features
double algorithms::euclidianHeuristic(Point p, Point other) {
double featuresCoefficient = 0.0;
for (int i = 0; i < p.features.size(); i++) {
double feature = p.features[i];
double featureOther = other.features[i];
if (isnan(feature)) {
feature = INSIGNIFICANT;
}
if (isnan(featureOther)) {
featureOther = INSIGNIFICANT;
}
featuresCoefficient += (feature - featureOther) * (feature - featureOther);
}
// min or max
return featuresCoefficient;
}
// calculates the cosine similarity distance between 2 point features
double algorithms::cosineSimilarityHeuristic(Point p, Point other) {
double s1 = 0.0, s2 = 0.0, s3 = 0.0;
for (int i = 0; i < p.features.size(); i++) {
s1 += p.features.at(i) * other.features.at(i);
s2 += p.features.at(i) * p.features.at(i);
s3 += other.features.at(i) * other.features.at(i);
}
return 1 - (s1 / (sqrt(s2) * sqrt(s3)));
}