Come posso ottimizzare ulteriormente questa funzione differenza di colore?

Question

ho fatto questa funzione per differenze di colore calcolati secondo il metodo colore CIE Lab, ma manca la velocità. Dal momento che io non sono un esperto di Java, mi chiedo se qualsiasi guru Java ha circa alcuni suggerimenti che possono migliorare la velocità qui.

Il codice è basato sulla funzione MATLAB menzionato nel blocco di commento.

/**
 * Compute the CIEDE2000 color-difference between the sample color with
 * CIELab coordinates 'sample' and a standard color with CIELab coordinates
 * 'std'
 *
 * Based on the article:
 * "The CIEDE2000 Color-Difference Formula: Implementation Notes,
 * Supplementary Test Data, and Mathematical Observations,", G. Sharma,
 * W. Wu, E. N. Dalal, submitted to Color Research and Application,
 * January 2004.
 * available at http://www.ece.rochester.edu/~gsharma/ciede2000/
 */
public static double deltaE2000(double[] lab1, double[] lab2)
{
    double L1 = lab1[0];
    double a1 = lab1[1];
    double b1 = lab1[2];

    double L2 = lab2[0];
    double a2 = lab2[1];
    double b2 = lab2[2];

    // Cab = sqrt(a^2 + b^2)
    double Cab1 = Math.sqrt(a1 * a1 + b1 * b1);
    double Cab2 = Math.sqrt(a2 * a2 + b2 * b2);

    // CabAvg = (Cab1 + Cab2) / 2
    double CabAvg = (Cab1 + Cab2) / 2;

    // G = 1 + (1 - sqrt((CabAvg^7) / (CabAvg^7 + 25^7))) / 2
    double CabAvg7 = Math.pow(CabAvg, 7);
    double G = 1 + (1 - Math.sqrt(CabAvg7 / (CabAvg7 + 6103515625.0))) / 2;

    // ap = G * a
    double ap1 = G * a1;
    double ap2 = G * a2;

    // Cp = sqrt(ap^2 + b^2)
    double Cp1 = Math.sqrt(ap1 * ap1 + b1 * b1);
    double Cp2 = Math.sqrt(ap2 * ap2 + b2 * b2);

    // CpProd = (Cp1 * Cp2)
    double CpProd = Cp1 * Cp2;

    // hp1 = atan2(b1, ap1)
    double hp1 = Math.atan2(b1, ap1);
    // ensure hue is between 0 and 2pi
    if (hp1 < 0) {
        // hp1 = hp1 + 2pi
        hp1 += 6.283185307179586476925286766559;
    }

    // hp2 = atan2(b2, ap2)
    double hp2 = Math.atan2(b2, ap2);
    // ensure hue is between 0 and 2pi
    if (hp2 < 0) {
        // hp2 = hp2 + 2pi
        hp2 += 6.283185307179586476925286766559;
    }

    // dL = L2 - L1
    double dL = L2 - L1;

    // dC = Cp2 - Cp1
    double dC = Cp2 - Cp1;

    // computation of hue difference
    double dhp = 0.0;
    // set hue difference to zero if the product of chromas is zero
    if (CpProd != 0) {
        // dhp = hp2 - hp1
        dhp = hp2 - hp1;
        if (dhp > Math.PI) {
            // dhp = dhp - 2pi
            dhp -= 6.283185307179586476925286766559;
        } else if (dhp < -Math.PI) {
            // dhp = dhp + 2pi
            dhp += 6.283185307179586476925286766559;
        }
    }

    // dH = 2 * sqrt(CpProd) * sin(dhp / 2)
    double dH = 2 * Math.sqrt(CpProd) * Math.sin(dhp / 2);

    // weighting functions
    // Lp = (L1 + L2) / 2 - 50
    double Lp = (L1 + L2) / 2 - 50;

    // Cp = (Cp1 + Cp2) / 2
    double Cp = (Cp1 + Cp2) / 2;

    // average hue computation
    // hp = (hp1 + hp2) / 2
    double hp = (hp1 + hp2) / 2;

    // identify positions for which abs hue diff exceeds 180 degrees
    if (Math.abs(hp1 - hp2) > Math.PI) {
        // hp = hp - pi
        hp -= Math.PI;
    }
    // ensure hue is between 0 and 2pi
    if (hp < 0) {
        // hp = hp + 2pi
        hp += 6.283185307179586476925286766559;
    }

    // LpSqr = Lp^2
    double LpSqr = Lp * Lp;

    // Sl = 1 + 0.015 * LpSqr / sqrt(20 + LpSqr)
    double Sl = 1 + 0.015 * LpSqr / Math.sqrt(20 + LpSqr);

    // Sc = 1 + 0.045 * Cp
    double Sc = 1 + 0.045 * Cp;

    // T = 1 - 0.17 * cos(hp - pi / 6) +
    //       + 0.24 * cos(2 * hp) +
    //       + 0.32 * cos(3 * hp + pi / 30) -
    //       - 0.20 * cos(4 * hp - 63 * pi / 180)
    double hphp = hp + hp;
    double T = 1 - 0.17 * Math.cos(hp - 0.52359877559829887307710723054658)
            + 0.24 * Math.cos(hphp)
            + 0.32 * Math.cos(hphp + hp + 0.10471975511965977461542144610932)
            - 0.20 * Math.cos(hphp + hphp - 1.0995574287564276334619251841478);

    // Sh = 1 + 0.015 * Cp * T
    double Sh = 1 + 0.015 * Cp * T;

    // deltaThetaRad = (pi / 3) * e^-(36 / (5 * pi) * hp - 11)^2
    double powerBase = hp - 4.799655442984406;
    double deltaThetaRad = 1.0471975511965977461542144610932 * Math.exp(-5.25249016001879 * powerBase * powerBase);

    // Rc = 2 * sqrt((Cp^7) / (Cp^7 + 25^7))
    double Cp7 = Math.pow(Cp, 7);
    double Rc = 2 * Math.sqrt(Cp7 / (Cp7 + 6103515625.0));

    // RT = -sin(delthetarad) * Rc
    double RT = -Math.sin(deltaThetaRad) * Rc;

    // de00 = sqrt((dL / Sl)^2 + (dC / Sc)^2 + (dH / Sh)^2 + RT * (dC / Sc) * (dH / Sh))
    double dLSl = dL / Sl;
    double dCSc = dC / Sc;
    double dHSh = dH / Sh;
    return Math.sqrt(dLSl * dLSl + dCSc * dCSc + dHSh * dHSh + RT * dCSc * dHSh);
}

Answer 1

cos è costoso, soprattutto 4 di fila. Sembra che tu stia cos calcolo (n a + b) dove b è una costante e n è un numero intero piccolo. Questo significa che potete precompute cos (B) e il peccato (B) e in fase di esecuzione di calcolo solo cos (CV) e il peccato (CV). È possibile ottenere cos (n a + b) facendo uso ripetuto di

cos(a+b) = cos(a)*cos(b)-sin(a)*sin(b)

Ti verrà scambiato un paio di sins e coss per alcune moltiplicazioni e addizioni, quasi certamente la pena.

Si può fare di meglio, se ti senti ambizioso. Stai diventando hp indirettamente da un atan2. Il trig-function(rational-function(inverse-trig-function(x))) modello può spesso essere sostituito da una combinazione di polinomi e radici che sono più veloci da valutare che funzioni trigonometriche.

Non so come pow è implementato in Java, ma se usa i registri, si può essere meglio ottenere Cp7 utilizzando Cp2=Cp*Cp;Cp4=Cp2*Cp2;Cp7=Cp4*Cp2*Cp;

Aggiornamento: Ottenere un po 'di più speculativa in questo momento, come non ho tempo per davvero riscrivere il codice. L'ottimizzazione di potenza e l'ottimizzazione trig sono in realtà la stessa cosa sotto mentite spoglie! L'ottimizzazione trig è una versione della ottimizzazione potenza applicata ai numeri complessi. Cosa c'è di più, la riga

double dH = 2 * Math.sqrt(CpProd) * Math.sin(dhp / 2);

è parte di un'operazione di radice quadrata numero complesso. Questo mi fa pensare che un grande pezzo di questo codice potrebbe effettivamente essere scritto per usare numeri complessi eliminando quasi tutte le funzioni trigonometriche. Non so come il vostro numero di aritmetica complessa è, però ...

Answer 2

In generale qualsiasi sistema che implementa questa ed ha problemi di velocità gravi non sta per essere fare i colori casuali. E 'intenzione di fare diversi colori distinti. Anche un'immagine gigante pieno di diversi colori è in genere sta per avere solo poche migliaia di colori. Io consiglio caldamente un algoritmo di caching. Anche se se la velocità è una preoccupazione si dovrebbe rotolare il proprio (che si desidera primitive solo, velocità).

Non c'è molto ottimizzando essere fatto con l'attuale routine di distanza colore stesso, ma ho scritto un sistema di caching per questa cosa ed è andato dell'ordine di 100 volte più veloci. La routine di distanza è andato dal fattore dominante schiacciante per un blip. Non si dovrebbe cercare di ridurre la velocità di questo. Si potrebbe eek fuori qualcosa. Ma, ridurre il numero di volte voi invoco la cosa in modo corretto.

Hai due ingressi impostati e produce una singola uscita insieme, e lo fa dopo un tempo molto lungo. 7 doppie per indice di caching. Questo è 14 byte. Per un ingombro di memoria 14 mega (o giù di lì, ignorando hash o cosa no, probabilmente stiamo parlando di doppio). È possibile memorizzare un milione di voci e questo è sufficiente che se avete come 1k tipici colori diversi si otterrà alta 90% s riscontri nella cache. Si può anche ridurre questo enorme se si sta convertendo i colori iniziali da RGB a Lab (quelle conversioni devono essere memorizzate nella cache troppo). Vedrete una velocità fino se si ha colpito come il 5% del tempo. E si otterrà successi probabilmente il 99% del tempo (a meno che non si sta facendo qualcosa di strano come i confronti colore casuale). Dalle mie osservazioni rende CIEDE2000 prendere più o meno la stessa cosa di tempo come euclidea RGB.