Квантование изображения - Алгоритмы

Пытаюсь придумать алгоритм создания палитры цветов. Но для хитрой палитры. Палитра состоит из N базовых цветов + дополнительные оттенки, которые получаются полусуммой любых базовых цветов. К примеру, пусть у нас будет 4 базовых цвета A, B, C, D. Тогда общая палитра будет таковой:

A AB AC AD
  B  BC ВD
     C  CD
        D

При этом выполняется равенство:

AB = (A + B)/2
AC = (A + C)/2
...
CD = (C + D)/2

Если бы не дополнительные оттенки – то проблем бы не было. Выбираем начальные точки медианным сечением, и дальше методом k-средних выводим наиболее оптимальные цифры.

Но для моей ситуации все чуть сложнее. Метод k-средних на каждой итерации смещает центры масс кластеров, что приводит к тому, что равенство перестает выполняться. И на каждой итерации мне нужно производить корректировку центров масс каждого кластера так, что бы исходное равенство снова стало верным.

Т.е. задача алгоритма – найти такие минимальные коэффициенты для каждого кластера, при умножении на которые (или при сложении с которыми?) исходное равенство снова становится верным. При этом каждый кластер имеет свой вес в виде количества цветов, относящихся к данному кластеру. Чем больше вес – тем меньше центр масс кластера должен смещаться.

Подскажите, в каком направлении двигаться.

Здравствуйте, Aniskin, Вы писали:

A>Пытаюсь придумать алгоритм создания палитры цветов. Но для хитрой палитры. Палитра состоит из N базовых цветов + дополнительные оттенки, которые получаются полусуммой любых базовых цветов. К примеру, пусть у нас будет 4 базовых цвета A, B, C, D. Тогда общая палитра будет таковой:

A>

A>A AB AC AD
A>  B  BC ВD
A>     C  CD
A>        D
A>

A>При этом выполняется равенство:

A>AB = (A + B)/2
A>AC = (A + C)/2
A>...
A>CD = (C + D)/2

A>Если бы не дополнительные оттенки – то проблем бы не было. Выбираем начальные точки медианным сечением, и дальше методом k-средних выводим наиболее оптимальные цифры.

A>Но для моей ситуации все чуть сложнее. Метод k-средних на каждой итерации смещает центры масс кластеров, что приводит к тому, что равенство перестает выполняться. И на каждой итерации мне нужно производить корректировку центров масс каждого кластера так, что бы исходное равенство снова стало верным.

A>Т.е. задача алгоритма – найти такие минимальные коэффициенты для каждого кластера, при умножении на которые (или при сложении с которыми?) исходное равенство снова становится верным. При этом каждый кластер имеет свой вес в виде количества цветов, относящихся к данному кластеру. Чем больше вес – тем меньше центр масс кластера должен смещаться.

A>Подскажите, в каком направлении двигаться.

Центры масс кластеров, в методе k-средних суть точки в пространстве, которые минимизируют потенциал

. Т.е. переходя к механической аналогии каждая точка кластера тянет точку mu_i с силой пропорциональной отклонению от mu_i.
Если точки mu связаны дополнительными механическими связями, то можно переложить силы действующие на зависимые точки, на те точки, на которые они опираются.

Т.е.:

В процедуре расчетов центров масс кластеров, рассчитывал центры масс только для основных цветов.
Если точка принадлежит кластеру цвета AB, то учитывал ее (с весом 1/2) в кластерах A и B.

Сумма отклонений должна на каждой итерации уменьшаться, также как и в обычном алгоритме k-средних.

Здравствуйте, Aniskin, Вы писали:

A>Но для моей ситуации все чуть сложнее. Метод k-средних на каждой итерации смещает центры масс кластеров, что приводит к тому, что равенство перестает выполняться. И на каждой итерации мне нужно производить корректировку центров масс каждого кластера так, что бы исходное равенство снова стало верным.
Лень вникать в детали того, что ты хочешь, но если к-средних не подходит, то возьми EM для GMM, зафиксируй мат ожидания и оптимизируй только по вероятности и ковариациям.

Здравствуйте, Chorkov, Вы писали:

C>В процедуре расчетов центров масс кластеров, рассчитывал центры масс только для основных цветов.
C>Если точка принадлежит кластеру цвета AB, то учитывал ее (с весом 1/2) в кластерах A и B.

Спасибо за идею. Но не могу сообразить, как ее применить на практике. Предположим, в какой-то момент образовались следующие кластеры:

A — состоит из одного цвета со значением 4, центр кластера 4.
AB — состоит из трех цветов со значениями 6, 7 и 8, центр кластера (6 + 7 + 8) / 3 = 7.
B — состоит из двух цветов со значениями 11 и 13, центр кластера (11 + 13) / 2 = 12.

Как посчитать правильные центры кластеров A и B для указанных значений?

Здравствуйте, 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
Получаешь простую линейную систему уравнений.
В твоём варианте примерно так A=3.3 B=11.6:

#!/usr/bin/lua

function AB(x)
    local function sum(a) local s=0 for i=1,#a do s=s+a[i] end return s end
    local n,s,a11,a22,a12,d,y
    n={} s={} for i=1,3 do n[i]=#x[i] s[i]=sum(x[i]) end
    a11=n[1]+n[2]/4
    a22=n[3]+n[2]/4
    a12=n[2]/4
    d=a11*a22-a12*a12
    y={ s[1]+s[2]/2, s[3]+s[2]/2 }
    return (y[1]*a22-y[2]*a12)/d, (y[2]*a11-y[1]*a12)/d 
end

print( AB{ {4}, {6,7,8}, {11,13} } )

3.2941176470588    11.647058823529

Здравствуйте, 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

Здравствуйте, kov_serg, Вы писали:

_>В общем виде как-то так: https://ideone.com/KOBjX6

Правильно ли я понимаю, что это код для произвольного кол-ва базовых цветов в палитре, а не только для двух?

Здравствуйте, Aniskin, Вы писали:

_>>В общем виде как-то так: https://ideone.com/KOBjX6

A>Правильно ли я понимаю, что это код для произвольного кол-ва базовых цветов в палитре, а не только для двух?
Да

Здравствуйте, Aniskin, Вы писали:

A>Правильно ли я понимаю, что это код для произвольного кол-ва базовых цветов в палитре, а не только для двух?

ps: Еще хочу напомнить, что есть различные способы представления цвета (цветовые пространства)
И прям линейность в них никто не обещает. Так что экспериментируйте.

Здравствуйте, kov_serg, Вы писали:

_>И прям линейность в них никто не обещает.

Я работаю с линейными значениями sRGB.

Здравствуйте, Aniskin, Вы писали:

_>>И прям линейность в них никто не обещает.

A>Я работаю с линейными значениями sRGB.
Хреновый выбор.

Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, Aniskin, Вы писали:

_>>>И прям линейность в них никто не обещает.

A>>Я работаю с линейными значениями sRGB.

_>Хреновый выбор.

Почему?

Здравствуйте, Aniskin, Вы писали:

A>>>Я работаю с линейными значениями sRGB.

_>>Хреновый выбор.

A>Почему?

В HSL формате есть очень простые алгоритмы создания палитр с помощью фиксированных смещений Hue относительно базового тона, как это например делается в подобных генераторах:

https://paletton.com

Но если у тебя несколько базовых тонов, то надо подключать "искусственный интеллект", потому что потребуется чувство "художественного вкуса".

	От:	Aniskin
	Дата:	15.01.21 07:20
	Оценка:

	От:	Chorkov
	Дата:	21.01.21 13:34
	Оценка:

	От:	Vzhyk2
	Дата:	21.01.21 14:45
	Оценка:

	От:	Aniskin
	Дата:	21.01.21 14:53
	Оценка:

	От:	kov_serg
	Дата:	21.01.21 18:22
	Оценка:

	От:	Dimonka
	Дата:	28.01.21 15:07
	Оценка: