IT++ Logo
vqtrain.cpp
Go to the documentation of this file.
1
30#include <itpp/base/matfunc.h>
31#include <itpp/base/random.h>
32#include <itpp/base/sort.h>
33#include <itpp/base/specmat.h>
35#include <itpp/stat/misc_stat.h>
36#include <iostream>
37
39
40namespace itpp
41{
42
43// the cols contains codevectors
44double kmeansiter(Array<vec> &DB, mat &codebook)
45{
46 int DIM = DB(0).length(), SIZE = codebook.cols(), T = DB.length();
47 vec x, xnum(SIZE);
48 mat xsum(DIM, SIZE);
49 int MinIndex, i, j, k;
50 double MinS, S, D, *xp, *cp;
51
52 xsum.clear();
53 xnum.clear();
54
55 D = 1E20;
56 D = 0;
57 for (k = 0;k < T;k++) {
58 x = DB(k);
59 xp = x._data();
60 MinS = 1E20;
61 MinIndex = 0;
62 for (i = 0;i < SIZE;i++) {
63 cp = &codebook(0, i);
64 S = sqr(xp[0] - cp[0]);
65 for (j = 1;j < DIM;j++) {
66 S += sqr(xp[j] - cp[j]);
67 if (S >= MinS) goto sune;
68 }
69 MinS = S;
70 MinIndex = i;
71 sune:
72 void();
73 }
74 D += MinS;
75 cp = &xsum(0, MinIndex);
76 for (j = 0;j < DIM;j++) {
77 cp[j] += xp[j];
78 }
79 xnum(MinIndex)++;
80 }
81 for (i = 0;i < SIZE;i++) {
82 for (j = 0;j < DIM;j++) {
83 codebook(j, i) = xsum(j, i) / xnum(i);
84 }
85 }
86 return D;
87}
88
89mat kmeans(Array<vec> &DB, int SIZE, int NOITER, bool VERBOSE)
90{
91 int DIM = DB(0).length(), T = DB.length();
92 mat codebook(DIM, SIZE);
93 int n, i, j;
94 double D, Dold;
95 ivec ind(SIZE);
96
97 for (i = 0;i < SIZE;i++) {
98 ind(i) = randi(0, T - 1);
99 j = 0;
100 while (j < i) {
101 if (ind(j) == ind(i)) {
102 ind(i) = randi(0, T - 1);
103 j = 0;
104 }
105 j++;
106 }
107 codebook.set_col(i, DB(ind(i)));
108 }
109
110
111 if (VERBOSE) std::cout << "Training VQ..." << std::endl ;
112
113 D = 1E20;
114 for (n = 0;n < NOITER;n++) {
115 Dold = D;
116 D = kmeansiter(DB, codebook);
117 if (VERBOSE) std::cout << n << ": " << D / T << " ";
118 if (std::abs((D - Dold) / D) < 1e-4) break;
119 }
120 return codebook;
121}
122
123mat lbg(Array<vec> &DB, int SIZE, int NOITER, bool VERBOSE)
124{
125 int S = 1, DIM = DB(0).length(), T = DB.length(), i, n;
126 mat cb;
127 vec delta = 0.001 * randn(DIM), x;
128 double D, Dold;
129
130 x = zeros(DIM);
131 for (i = 0;i < T;i++) {
132 x += DB(i);
133 }
134 x /= T;
135 cb.set_size(DIM, 1);
136 cb.set_col(0, x);
137 while (cb.cols() < SIZE) {
138 S = cb.cols();
139 if (2*S <= SIZE) cb.set_size(DIM, 2*S, true);
140 else cb.set_size(DIM, 2*S, true);
141 for (i = S;i < cb.cols();i++) {
142 cb.set_col(i, cb.get_col(i - S) + delta);
143 }
144 D = 1E20;
145 for (n = 0;n < NOITER;n++) {
146 Dold = D;
147 D = kmeansiter(DB, cb);
148 if (VERBOSE) std::cout << n << ": " << D / T << " ";
149 if (std::abs((D - Dold) / D) < 1e-4) break;
150 }
151 }
152
153 return cb;
154}
155
156mat vqtrain(Array<vec> &DB, int SIZE, int NOITER, double STARTSTEP, bool VERBOSE)
157{
158 int DIM = DB(0).length();
159 vec x;
160 vec codebook(DIM*SIZE);
161 int n, MinIndex, i, j;
162 double MinS, S, D, step, *xp, *cp;
163
164 for (i = 0;i < SIZE;i++) {
165 codebook.replace_mid(i*DIM, DB(randi(0, DB.length() - 1)));
166 }
167 if (VERBOSE) std::cout << "Training VQ..." << std::endl ;
168
169res:
170 D = 0;
171 for (n = 0;n < NOITER;n++) {
172 step = STARTSTEP * (1.0 - double(n) / NOITER);
173 if (step < 0) step = 0;
174 x = DB(randi(0, DB.length() - 1)); // seems unnecessary! Check it up.
175 xp = x._data();
176
177 MinS = 1E20;
178 MinIndex = 0;
179 for (i = 0;i < SIZE;i++) {
180 cp = &codebook(i * DIM);
181 S = sqr(xp[0] - cp[0]);
182 for (j = 1;j < DIM;j++) {
183 S += sqr(xp[j] - cp[j]);
184 if (S >= MinS) goto sune;
185 }
186 MinS = S;
187 MinIndex = i;
188 sune:
189 i = i;
190 }
191 D += MinS;
192 cp = &codebook(MinIndex * DIM);
193 for (j = 0;j < DIM;j++) {
194 cp[j] += step * (xp[j] - cp[j]);
195 }
196 if ((n % 20000 == 0) && (n > 1)) {
197 if (VERBOSE) std::cout << n << ": " << D / 20000 << " ";
198 D = 0;
199 }
200 }
201
202 // checking training result
203 vec dist(SIZE), num(SIZE);
204
205 dist.clear();
206 num.clear();
207 for (n = 0;n < DB.length();n++) {
208 x = DB(n);
209 xp = x._data();
210 MinS = 1E20;
211 MinIndex = 0;
212 for (i = 0;i < SIZE;i++) {
213 cp = &codebook(i * DIM);
214 S = sqr(xp[0] - cp[0]);
215 for (j = 1;j < DIM;j++) {
216 S += sqr(xp[j] - cp[j]);
217 if (S >= MinS) goto sune2;
218 }
219 MinS = S;
220 MinIndex = i;
221 sune2:
222 i = i;
223 }
224 dist(MinIndex) += MinS;
225 num(MinIndex) += 1;
226 }
227 dist = 10 * log10(dist * dist.length() / sum(dist));
228 if (VERBOSE) std::cout << std::endl << "Distortion contribution: " << dist << std::endl ;
229 if (VERBOSE) std::cout << "Num spread: " << num / DB.length()*100 << " %" << std::endl << std::endl ;
230 if (min(dist) < -30) {
231 std::cout << "Points without entries! Retraining" << std::endl ;
232 j = min_index(dist);
233 i = max_index(num);
234 codebook.replace_mid(j*DIM, codebook.mid(i*DIM, DIM));
235 goto res;
236 }
237
238 mat cb(DIM, SIZE);
239 for (i = 0;i < SIZE;i++) {
240 cb.set_col(i, codebook.mid(i*DIM, DIM));
241 }
242 return cb;
243}
244
245vec sqtrain(const vec &inDB, int SIZE)
246{
247 vec DB(inDB);
248 vec Levels, Levels_old;
249 ivec indexlist(SIZE + 1);
250 int il, im, ih, i;
251 int SIZEDB = inDB.length();
252 double x;
253
254 sort(DB);
255 Levels = DB(round_i(linspace(0.01 * SIZEDB, 0.99 * SIZEDB, SIZE)));
256 Levels_old = zeros(SIZE);
257
258 while (energy(Levels - Levels_old) > 0.0001) {
259 Levels_old = Levels;
260 for (i = 0;i < SIZE - 1;i++) {
261 x = (Levels(i) + Levels(i + 1)) / 2;
262 il = 0;
263 ih = SIZEDB - 1;
264 while (il < ih - 1) {
265 im = (il + ih) / 2;
266 if (x < DB(im)) ih = im;
267 else il = im;
268 }
269 indexlist(i + 1) = il;
270 }
271 indexlist(0) = -1;
272 indexlist(SIZE) = SIZEDB - 1;
273 for (i = 0;i < SIZE;i++) Levels(i) = mean(DB(indexlist(i) + 1, indexlist(i + 1)));
274 }
275 return Levels;
276}
277
278ivec bitalloc(const vec &variances, int nobits)
279{
280 ivec bitvec(variances.length());
281 bitvec.clear();
282 int i, bits = nobits;
283 vec var = variances;
284
285 while (bits > 0) {
286 i = max_index(var);
287 var(i) /= 4;
288 bitvec(i)++;
289 bits--;
290 }
291 return bitvec;
292}
293
294} // namespace itpp
295
vec log10(const vec &x)
log-10 of the elements
Definition: log_exp.h:271
T sum(const Vec< T > &v)
Sum of all elements in the vector.
Definition: matfunc.h:59
int min_index(const Vec< T > &in)
Return the postion of the minimum element in the vector.
Definition: min_max.h:234
T min(const Vec< T > &in)
Minimum value of vector.
Definition: min_max.h:125
vec sqr(const cvec &data)
Absolute square of elements.
Definition: elem_math.cpp:36
int max_index(const Vec< T > &in)
Return the postion of the maximum element in the vector.
Definition: min_max.h:208
int randi(int low, int high)
Generates a random integer in the interval [low,high].
Definition: random.h:815
double randn(void)
Generates a random Gaussian (0,1) variable.
Definition: random.h:831
ITPP_EXPORT mat vqtrain(Array< vec > &DB, int SIZE, int NOITER, double STARTSTEP=0.2, bool VERBOSE=true)
Function for vector quantization training.
vec linspace(double from, double to, int points)
linspace (works in the same way as the MATLAB version)
Definition: specmat.cpp:106
ITPP_EXPORT vec zeros(int size)
A Double vector of zeros.
double energy(const Vec< T > &v)
Calculate the energy: squared 2-norm. energy(v)=sum(abs(v).^2)
Definition: misc_stat.h:253
double mean(const vec &v)
The mean value.
Definition: misc_stat.cpp:36
Various functions on vectors and matrices - header file.
Minimum and maximum functions on vectors and matrices.
Miscellaneous statistics functions and classes - header file.
itpp namespace
Definition: itmex.h:37
ITPP_EXPORT int round_i(double x)
Round to nearest integer.
ITPP_EXPORT mat lbg(Array< vec > &DB, int SIZE, int NOITER=9999, bool VERBOSE=true)
ADD DOCUMENTATION HERE.
ITPP_EXPORT double kmeansiter(Array< vec > &DB, mat &codebook)
ADD DOCUMENTATION HERE.
ITPP_EXPORT mat kmeans(Array< vec > &DB, int SIZE, int NOITER=9999, bool VERBOSE=true)
ADD DOCUMENTATION HERE.
ITPP_EXPORT ivec bitalloc(const vec &variances, int nobits)
ADD DOCUMENTATION HERE.
ITPP_EXPORT vec sqtrain(const vec &inDB, int SIZE)
ADD DOCUMENTATION HERE.
int abs(const itpp::bin &inbin)
absolute value of bin
Definition: binary.h:186
Definition of classes for random number generators.
Sorting functions.
Definitions of special vectors and matrices.
Definitions of a vector quantizer training functions.

Generated on Tue Aug 17 2021 10:59:15 for IT++ by Doxygen 1.9.4