44 double kmeansiter(Array<vec> &DB, mat &codebook)
46 int DIM = DB(0).length(), SIZE = codebook.cols(), T = DB.length();
49 int MinIndex, i, j, k;
50 double MinS, S, D, *xp, *cp;
57 for (k = 0;k < T;k++) {
62 for (i = 0;i < SIZE;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;
75 cp = &xsum(0, MinIndex);
76 for (j = 0;j < DIM;j++) {
81 for (i = 0;i < SIZE;i++) {
82 for (j = 0;j < DIM;j++) {
83 codebook(j, i) = xsum(j, i) / xnum(i);
89 mat
kmeans(Array<vec> &DB,
int SIZE,
int NOITER,
bool VERBOSE)
91 int DIM = DB(0).length(), T = DB.length();
92 mat codebook(DIM, SIZE);
97 for (i = 0;i < SIZE;i++) {
98 ind(i) =
randi(0, T - 1);
101 if (ind(j) == ind(i)) {
102 ind(i) =
randi(0, T - 1);
107 codebook.set_col(i, DB(ind(i)));
111 if (VERBOSE) std::cout <<
"Training VQ..." << std::endl ;
114 for (n = 0;n < NOITER;n++) {
117 if (VERBOSE) std::cout << n <<
": " << D / T <<
" ";
118 if (
std::abs((D - Dold) / D) < 1e-4)
break;
123 mat
lbg(Array<vec> &DB,
int SIZE,
int NOITER,
bool VERBOSE)
125 int S = 1, DIM = DB(0).length(), T = DB.length(), i, n;
127 vec delta = 0.001 *
randn(DIM), x;
131 for (i = 0;i < T;i++) {
137 while (cb.cols() < SIZE) {
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);
145 for (n = 0;n < NOITER;n++) {
148 if (VERBOSE) std::cout << n <<
": " << D / T <<
" ";
149 if (
std::abs((D - Dold) / D) < 1e-4)
break;
156 mat
vqtrain(Array<vec> &DB,
int SIZE,
int NOITER,
double STARTSTEP,
bool VERBOSE)
158 int DIM = DB(0).length();
160 vec codebook(DIM*SIZE);
161 int n, MinIndex, i, j;
162 double MinS, S, D, step, *xp, *cp;
164 for (i = 0;i < SIZE;i++) {
165 codebook.replace_mid(i*DIM, DB(
randi(0, DB.length() - 1)));
167 if (VERBOSE) std::cout <<
"Training VQ..." << std::endl ;
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));
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;
192 cp = &codebook(MinIndex * DIM);
193 for (j = 0;j < DIM;j++) {
194 cp[j] += step * (xp[j] - cp[j]);
196 if ((n % 20000 == 0) && (n > 1)) {
197 if (VERBOSE) std::cout << n <<
": " << D / 20000 <<
" ";
203 vec dist(SIZE), num(SIZE);
207 for (n = 0;n < DB.length();n++) {
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;
224 dist(MinIndex) += MinS;
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 ;
234 codebook.replace_mid(j*DIM, codebook.mid(i*DIM, DIM));
239 for (i = 0;i < SIZE;i++) {
240 cb.set_col(i, codebook.mid(i*DIM, DIM));
245 vec
sqtrain(
const vec &inDB,
int SIZE)
248 vec Levels, Levels_old;
249 ivec indexlist(SIZE + 1);
251 int SIZEDB = inDB.length();
256 Levels_old =
zeros(SIZE);
258 while (
energy(Levels - Levels_old) > 0.0001) {
260 for (i = 0;i < SIZE - 1;i++) {
261 x = (Levels(i) + Levels(i + 1)) / 2;
264 while (il < ih - 1) {
266 if (x < DB(im)) ih = im;
269 indexlist(i + 1) = il;
272 indexlist(SIZE) = SIZEDB - 1;
273 for (i = 0;i < SIZE;i++) Levels(i) =
mean(DB(indexlist(i) + 1, indexlist(i + 1)));
278 ivec
bitalloc(
const vec &variances,
int nobits)
280 ivec bitvec(variances.length());
282 int i, bits = nobits;
Various functions on vectors and matrices - header file.
ITPP_EXPORT int round_i(double x)
Round to nearest integer.
ITPP_EXPORT double kmeansiter(Array< vec > &DB, mat &codebook)
ADD DOCUMENTATION HERE.
int randi(int low, int high)
Generates a random integer in the interval [low,high].
Definitions of a vector quantizer training functions.
double randn(void)
Generates a random Gaussian (0,1) variable.
vec log10(const vec &x)
log-10 of the elements
T sum(const Vec< T > &v)
Sum of all elements in the vector.
Minimum and maximum functions on vectors and matrices.
double mean(const vec &v)
The mean value.
ITPP_EXPORT vec zeros(int size)
A Double vector of zeros.
T min(const Vec< T > &in)
Minimum value of vector.
int max_index(const Vec< T > &in)
Return the postion of the maximum element in the vector.
double energy(const Vec< T > &v)
Calculate the energy: squared 2-norm. energy(v)=sum(abs(v).^2)
Miscellaneous statistics functions and classes - header file.
ITPP_EXPORT vec sqtrain(const vec &inDB, int SIZE)
ADD DOCUMENTATION HERE.
vec sqr(const cvec &data)
Absolute square of elements.
Definitions of special vectors and matrices.
int min_index(const Vec< T > &in)
Return the postion of the minimum element in the vector.
vec linspace(double from, double to, int points)
linspace (works in the same way as the MATLAB version)
ITPP_EXPORT mat kmeans(Array< vec > &DB, int SIZE, int NOITER=9999, bool VERBOSE=true)
ADD DOCUMENTATION HERE.
ITPP_EXPORT mat lbg(Array< vec > &DB, int SIZE, int NOITER=9999, bool VERBOSE=true)
ADD DOCUMENTATION HERE.
ITPP_EXPORT mat vqtrain(Array< vec > &DB, int SIZE, int NOITER, double STARTSTEP=0.2, bool VERBOSE=true)
Function for vector quantization training.
Definition of classes for random number generators.
bin abs(const bin &inbin)
absolute value of bin
ITPP_EXPORT ivec bitalloc(const vec &variances, int nobits)
ADD DOCUMENTATION HERE.