Информация об изменениях

Сообщение Re[4]: Квантование изображения от 22.01.2021 10:54

Изменено 22.01.2021 12:07 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

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

Re[4]: Квантование изображения

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