44 double kmeansiter(Array<vec> &DB, mat &codebook)
46 int DIM = DB(0).length(), SIZE = codebook.cols(), T = DB.length();
49 int n, MinIndex, i, j, k;
50 double MinS, S, D, Dold, *xp, *cp;
59 for (k = 0;k < T;k++) {
64 for (i = 0;i < SIZE;i++) {
66 S =
sqr(xp[0] - cp[0]);
67 for (j = 1;j < DIM;j++) {
68 S +=
sqr(xp[j] - cp[j]);
69 if (S >= MinS)
goto sune;
77 cp = &xsum(0, MinIndex);
78 for (j = 0;j < DIM;j++) {
83 for (i = 0;i < SIZE;i++) {
84 for (j = 0;j < DIM;j++) {
85 codebook(j, i) = xsum(j, i) / xnum(i);
91 mat
kmeans(Array<vec> &DB,
int SIZE,
int NOITER,
bool VERBOSE)
93 int DIM = DB(0).length(), T = DB.length();
94 mat codebook(DIM, SIZE);
99 for (i = 0;i < SIZE;i++) {
100 ind(i) =
randi(0, T - 1);
103 if (ind(j) == ind(i)) {
104 ind(i) =
randi(0, T - 1);
109 codebook.set_col(i, DB(ind(i)));
113 if (VERBOSE) std::cout <<
"Training VQ..." << std::endl ;
116 for (n = 0;n < NOITER;n++) {
119 if (VERBOSE) std::cout << n <<
": " << D / T <<
" ";
120 if (
std::abs((D - Dold) / D) < 1e-4)
break;
125 mat
lbg(Array<vec> &DB,
int SIZE,
int NOITER,
bool VERBOSE)
127 int S = 1, DIM = DB(0).length(), T = DB.length(), i, n;
129 vec delta = 0.001 *
randn(DIM), x;
133 for (i = 0;i < T;i++) {
139 while (cb.cols() < SIZE) {
141 if (2*S <= SIZE) cb.set_size(DIM, 2*S,
true);
142 else cb.set_size(DIM, 2*S,
true);
143 for (i = S;i < cb.cols();i++) {
144 cb.set_col(i, cb.get_col(i - S) + delta);
147 for (n = 0;n < NOITER;n++) {
150 if (VERBOSE) std::cout << n <<
": " << D / T <<
" ";
151 if (
std::abs((D - Dold) / D) < 1e-4)
break;
158 mat
vqtrain(Array<vec> &DB,
int SIZE,
int NOITER,
double STARTSTEP,
bool VERBOSE)
160 int DIM = DB(0).length();
162 vec codebook(DIM*SIZE);
163 int n, MinIndex, i, j;
164 double MinS, S, D, step, *xp, *cp;
166 for (i = 0;i < SIZE;i++) {
167 codebook.replace_mid(i*DIM, DB(
randi(0, DB.length() - 1)));
169 if (VERBOSE) std::cout <<
"Training VQ..." << std::endl ;
173 for (n = 0;n < NOITER;n++) {
174 step = STARTSTEP * (1.0 - double(n) / NOITER);
175 if (step < 0) step = 0;
176 x = DB(
randi(0, DB.length() - 1));
181 for (i = 0;i < SIZE;i++) {
182 cp = &codebook(i * DIM);
183 S =
sqr(xp[0] - cp[0]);
184 for (j = 1;j < DIM;j++) {
185 S +=
sqr(xp[j] - cp[j]);
186 if (S >= MinS)
goto sune;
194 cp = &codebook(MinIndex * DIM);
195 for (j = 0;j < DIM;j++) {
196 cp[j] += step * (xp[j] - cp[j]);
198 if ((n % 20000 == 0) && (n > 1)) {
199 if (VERBOSE) std::cout << n <<
": " << D / 20000 <<
" ";
205 vec dist(SIZE), num(SIZE);
209 for (n = 0;n < DB.length();n++) {
214 for (i = 0;i < SIZE;i++) {
215 cp = &codebook(i * DIM);
216 S =
sqr(xp[0] - cp[0]);
217 for (j = 1;j < DIM;j++) {
218 S +=
sqr(xp[j] - cp[j]);
219 if (S >= MinS)
goto sune2;
226 dist(MinIndex) += MinS;
229 dist = 10 *
log10(dist * dist.length() /
sum(dist));
230 if (VERBOSE) std::cout << std::endl <<
"Distortion contribution: " << dist << std::endl ;
231 if (VERBOSE) std::cout <<
"Num spread: " << num / DB.length()*100 <<
" %" << std::endl << std::endl ;
232 if (
min(dist) < -30) {
233 std::cout <<
"Points without entries! Retraining" << std::endl ;
236 codebook.replace_mid(j*DIM, codebook.mid(i*DIM, DIM));
241 for (i = 0;i < SIZE;i++) {
242 cb.set_col(i, codebook.mid(i*DIM, DIM));
247 vec
sqtrain(
const vec &inDB,
int SIZE)
250 vec Levels, Levels_old;
251 ivec indexlist(SIZE + 1);
253 int SIZEDB = inDB.length();
258 Levels_old =
zeros(SIZE);
260 while (
energy(Levels - Levels_old) > 0.0001) {
262 for (i = 0;i < SIZE - 1;i++) {
263 x = (Levels(i) + Levels(i + 1)) / 2;
266 while (il < ih - 1) {
268 if (x < DB(im)) ih = im;
271 indexlist(i + 1) = il;
274 indexlist(SIZE) = SIZEDB - 1;
275 for (i = 0;i < SIZE;i++) Levels(i) =
mean(DB(indexlist(i) + 1, indexlist(i + 1)));
280 ivec
bitalloc(
const vec &variances,
int nobits)
282 ivec bitvec(variances.length());
284 int i, bits = nobits;