Сообщение Re[4]: Квантование изображения от 22.01.2021 10:54
Изменено 22.01.2021 12:06 kov_serg
Re[4]: Квантование изображения
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, Aniskin, Вы писали:
A>>Здравствуйте, Chorkov, Вы писали:
C>>>В процедуре расчетов центров масс кластеров, рассчитывал центры масс только для основных цветов.
C>>>Если точка принадлежит кластеру цвета AB, то учитывал ее (с весом 1/2) в кластерах A и B.
A>>Спасибо за идею. Но не могу сообразить, как ее применить на практике. Предположим, в какой-то момент образовались следующие кластеры:
A>>A — состоит из одного цвета со значением 4, центр кластера 4.
A>>AB — состоит из трех цветов со значениями 6, 7 и 8, центр кластера (6 + 7 + 8) / 3 = 7.
A>>B — состоит из двух цветов со значениями 11 и 13, центр кластера (11 + 13) / 2 = 12.
A>>Как посчитать правильные центры кластеров A и B для указанных значений?
_>Можно ввести функцию ошибки и её минимизировать. Например так:
_>S(a,b)=(a-4)^2 + ((a+b)/2-6)^2 + ((a+b)/2-7)^2 + ((a+b)/2-8)^2 + (b-11)^2 + (b-13)^2
_>dS/da = 0
_>dS/db = 0
_>Получаешь простую линейную систему уравнений.
В общем виде как-то так: https://ideone.com/KOBjX6
_>Здравствуйте, Aniskin, Вы писали:
A>>Здравствуйте, Chorkov, Вы писали:
C>>>В процедуре расчетов центров масс кластеров, рассчитывал центры масс только для основных цветов.
C>>>Если точка принадлежит кластеру цвета AB, то учитывал ее (с весом 1/2) в кластерах A и B.
A>>Спасибо за идею. Но не могу сообразить, как ее применить на практике. Предположим, в какой-то момент образовались следующие кластеры:
A>>A — состоит из одного цвета со значением 4, центр кластера 4.
A>>AB — состоит из трех цветов со значениями 6, 7 и 8, центр кластера (6 + 7 + 8) / 3 = 7.
A>>B — состоит из двух цветов со значениями 11 и 13, центр кластера (11 + 13) / 2 = 12.
A>>Как посчитать правильные центры кластеров A и B для указанных значений?
_>Можно ввести функцию ошибки и её минимизировать. Например так:
_>S(a,b)=(a-4)^2 + ((a+b)/2-6)^2 + ((a+b)/2-7)^2 + ((a+b)/2-8)^2 + (b-11)^2 + (b-13)^2
_>dS/da = 0
_>dS/db = 0
_>Получаешь простую линейную систему уравнений.
В общем виде как-то так: https://ideone.com/KOBjX6
typedef double flt;
class Solver {
int n; flt *A, *b;
static inline flt abs(flt a) { return a<0?-a:a; }
static inline void swp(flt &a,flt &b) { flt t=a;a=b;b=a; }
public:
Solver(int n) { init(n);reset(); }
~Solver() { done(); }
void init(int n) { this->n=n; A=new flt[n*n+n]; b=A+n*n; }
void done() { delete[] A; A=0; b=0; n=0; }
void reset() { int m=n*n+n; for(int i=0;i<m;++i) A[i]=0; }
Solver& add(int i,int j,flt a) {
A[i*n+i]+=0.5; A[i*n+j]+=0.5;
A[j*n+i]+=0.5; A[j*n+j]+=0.5;
b[i]+=a; b[j]+=a;
return *this;
}
Solver& add(int i,flt a) { return add(i,i,a); }
int solve(flt* x) {
int i,mi,j,k,p; flt mv,mf,t;
for(i=0;i<n;i++) { // forward
mi=i; mv=abs(A[i+i*n]); // find top
for(j=i+1;j<n;j++) { t=abs(A[i+j*n]); if (t>mv) { mv=t;mi=j; } }
if (mv==0) return 1; // no solution
if (i!=mi) { swp(b[i],b[mi]); for(k=0;k<n;k++) swp(A[k+i*n],A[k+mi*n]); }
for(int k=i+1;k<n;k++) { // clear under
mf=A[i+k*n]/A[i+i*n];
for(p=i+1;p<n;p++) A[p+k*n]-=mf*A[p+i*n];
A[i+k*n]=0; b[k]-=mf*b[i];
}
}
for(j=n-1;j>=0;j--) { // backward
t=b[j]; for(k=j+1;k<n;k++) t-=A[k+j*n]*x[k];
x[j]=t/A[j+j*n];
}
return 0; // no problem
}
};
#include <stdio.h>
int main(int argc, char const *argv[]) {
enum { A,B, N=2 }; flt x[N]; Solver solver(N);
solver
.add(A,4)
.add(A,B,6)
.add(A,B,7)
.add(A,B,8)
.add(B,11)
.add(B,13)
;
if (solver.solve(x)) { fprintf(stderr,"shit happens\n"); return 1; }
printf("a=%.3f b=%.3f\n",x[0],x[1]);
return 0;
}
a=3.294 b=11.647
Re[4]: Квантование изображения
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, Aniskin, Вы писали:
A>>Здравствуйте, Chorkov, Вы писали:
C>>>В процедуре расчетов центров масс кластеров, рассчитывал центры масс только для основных цветов.
C>>>Если точка принадлежит кластеру цвета AB, то учитывал ее (с весом 1/2) в кластерах A и B.
A>>Спасибо за идею. Но не могу сообразить, как ее применить на практике. Предположим, в какой-то момент образовались следующие кластеры:
A>>A — состоит из одного цвета со значением 4, центр кластера 4.
A>>AB — состоит из трех цветов со значениями 6, 7 и 8, центр кластера (6 + 7 + 8) / 3 = 7.
A>>B — состоит из двух цветов со значениями 11 и 13, центр кластера (11 + 13) / 2 = 12.
A>>Как посчитать правильные центры кластеров A и B для указанных значений?
_>Можно ввести функцию ошибки и её минимизировать. Например так:
_>S(a,b)=(a-4)^2 + ((a+b)/2-6)^2 + ((a+b)/2-7)^2 + ((a+b)/2-8)^2 + (b-11)^2 + (b-13)^2
_>dS/da = 0
_>dS/db = 0
_>Получаешь простую линейную систему уравнений.
В общем виде как-то так: https://ideone.com/KOBjX6
_>Здравствуйте, Aniskin, Вы писали:
A>>Здравствуйте, Chorkov, Вы писали:
C>>>В процедуре расчетов центров масс кластеров, рассчитывал центры масс только для основных цветов.
C>>>Если точка принадлежит кластеру цвета AB, то учитывал ее (с весом 1/2) в кластерах A и B.
A>>Спасибо за идею. Но не могу сообразить, как ее применить на практике. Предположим, в какой-то момент образовались следующие кластеры:
A>>A — состоит из одного цвета со значением 4, центр кластера 4.
A>>AB — состоит из трех цветов со значениями 6, 7 и 8, центр кластера (6 + 7 + 8) / 3 = 7.
A>>B — состоит из двух цветов со значениями 11 и 13, центр кластера (11 + 13) / 2 = 12.
A>>Как посчитать правильные центры кластеров A и B для указанных значений?
_>Можно ввести функцию ошибки и её минимизировать. Например так:
_>S(a,b)=(a-4)^2 + ((a+b)/2-6)^2 + ((a+b)/2-7)^2 + ((a+b)/2-8)^2 + (b-11)^2 + (b-13)^2
_>dS/da = 0
_>dS/db = 0
_>Получаешь простую линейную систему уравнений.
В общем виде как-то так: https://ideone.com/KOBjX6
typedef double flt;
class Solver {
int n; flt *A, *b;
static inline flt abs(flt a) { return a<0?-a:a; }
static inline void swp(flt &a,flt &b) { flt t=a;a=b;b=a; }
public:
Solver(int n) { init(n);reset(); }
~Solver() { done(); }
void init(int n) { this->n=n; A=new flt[n*n+n]; b=A+n*n; }
void done() { delete[] A; A=0; b=0; n=0; }
void reset() { int m=n*n+n; for(int i=0;i<m;++i) A[i]=0; }
Solver& add(int i,int j,flt a) {
A[i*n+i]+=0.5; A[i*n+j]+=0.5;
A[j*n+i]+=0.5; A[j*n+j]+=0.5;
b[i]+=a; b[j]+=a;
return *this;
}
Solver& add(int i,flt a) { A[i+i*n]+=2;b[i]+=2*a; return *this; }
int solve(flt* x) {
int i,mi,j,k,p; flt mv,mf,t;
for(i=0;i<n;i++) { // forward
mi=i; mv=abs(A[i+i*n]); // find top
for(j=i+1;j<n;j++) { t=abs(A[i+j*n]); if (t>mv) { mv=t;mi=j; } }
if (mv==0) return 1; // no solution
if (i!=mi) { swp(b[i],b[mi]); for(k=0;k<n;k++) swp(A[k+i*n],A[k+mi*n]); }
for(int k=i+1;k<n;k++) { // clear under
mf=A[i+k*n]/A[i+i*n];
for(p=i+1;p<n;p++) A[p+k*n]-=mf*A[p+i*n];
A[i+k*n]=0; b[k]-=mf*b[i];
}
}
for(j=n-1;j>=0;j--) { // backward
t=b[j]; for(k=j+1;k<n;k++) t-=A[k+j*n]*x[k];
x[j]=t/A[j+j*n];
}
return 0; // no problem
}
};
#include <stdio.h>
int main(int argc, char const *argv[]) {
enum { A,B, N=2 }; flt x[N]; Solver solver(N);
solver
.add(A,4)
.add(A,B,6)
.add(A,B,7)
.add(A,B,8)
.add(B,11)
.add(B,13)
;
if (solver.solve(x)) { fprintf(stderr,"shit happens\n"); return 1; }
printf("a=%.3f b=%.3f\n",x[0],x[1]);
return 0;
}
a=3.294 b=11.647