Wie kann ich diese Farbdifferenzfunktion weiter optimieren?

Question

Ich habe diese Funktion zu berechnen Farbunterschiede im CIE-Lab-Farbraum gemacht, aber es fehlt Geschwindigkeit. Da ich keine Java-Experte bin, frage ich mich, wenn jedes Java-Guru um einige Tipps hat, die die Geschwindigkeit hier verbessern.

Der Code basiert auf der Matlab-Funktion im Kommentarblock genannt.

/**
 * 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 ist teuer, vor allem 4 in einer Reihe. Sie scheinen zu cos Berechnung (n a + b) wobei b eine Konstante ist und n eine kleine ganze Zahl. Dieses Mittel kann man cos (b) und sin (b) und zur Laufzeit berechnet precompute nur cos (PS) und sin (PS). Sie können cos erhalten (n a + b) durch wiederholten Gebrauch machen

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

Sie werden ein paar sins und coss für einige Multiplikationen und Additionen werden Handel, mit ziemlicher Sicherheit lohnenswert.

Sie können es besser machen, wenn Sie ehrgeizig fühlen. Sie bekommen hp indirekt von einem atan2. Das Muster trig-function(rational-function(inverse-trig-function(x))) kann häufig durch eine Kombination von Polynomen und Wurzeln ersetzt werden, die schneller zu bewerten sind als Funktionen trig.

Ich weiß nicht, wie pow in Java implementiert ist, aber wenn es Protokolle verwendet, kann besser sein Cp7 mit Cp2=Cp*Cp;Cp4=Cp2*Cp2;Cp7=Cp4*Cp2*Cp; off bekommen

Update: Erste ein bisschen mehr spekulativ jetzt, da ich eigentlich keine Zeit haben, um den Code neu schreiben. Die Leistungsoptimierung und die Triglyzerid-Optimierung ist eigentlich die gleiche Sache in der Verkleidung! Die trig-Optimierung ist eine Version der Leistungsoptimierung auf komplexe Zahlen angewendet. Was mehr ist, die Zeile

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

ist ein Teil einer komplexen Zahl Quadratwurzeloperation. Das macht mich denken, dass ein großer Teil dieser Code tatsächlich geschrieben werden komplexe Zahlen verwenden fast alle der trigonometrischen Funktionen zu beseitigen. Ich weiß nicht, wie Sie Ihre Arithmetik mit komplexen Zahlen ist allerdings ...

Answer 2

Im allgemeinen kann jedes System, das diese implementiert und Probleme ernst Geschwindigkeit wird nicht zufällige Farben zu tun. Es wird mehrere verschiedene Farben zu tun. Selbst ein riesiges Bild voll von verschiedenen Farben wird typischerweise nur ein paar tausend Farben hat. I sehr hoch ein Caching-Algorithmus empfehlen. Obwohl, wenn Geschwindigkeit ist ein Anliegen Sie aufrollen sollten Sie Ihre eigenen (Sie wollen Primitiven nur, Geschwindigkeit).

Es gibt nicht viel zu optimieren mit der tatsächlichen Farbe Abstand Routine zu tun selbst, aber ich schrieb schneller ein Caching-System für diese Sache, und es ging auf der Größenordnung von 100 mal. Der Abstand Routine ging von dem überwältigenden dominierenden Faktor auf einen Ausrutscher. Sie sollten nicht versuchen, die Geschwindigkeit, das zu reduzieren. Sie könnten aus etwas eek. Aber, reduzieren die Anzahl der Zeiten, die Sie aufrufen, um die Sache richtig.

Sie haben zwei Set-Eingänge und erzeugt einen einzigen Satz ausgegeben, und zwar nach einer sehr langen Zeit. 7 Doppelzimmer pro Caching-Index. Das ist 14 Bytes. Für einen 14 meg Speicherbedarf (oder so, zu ignorieren Hashes oder was nicht, wahrscheinlich reden wir doppelt). Sie können eine Million Einträge speichern und das ist genug, wenn man wie 1k typische verschiedene Farben haben werden Sie hohe 90% s Cache-Hits bekommen. Sie können sogar diese enorm reduzieren, wenn Sie Ihre Anfangsfarben von RGB nach Lab konvertieren (diese Umwandlungen zu zwischengespeichert werden sollen). Sie werden eine Geschwindigkeit sehen, wenn Sie wie 5% der Zeit getroffen. Und Sie werden Hits wahrscheinlich 99% der Zeit erhalten (es sei denn, Sie etwas seltsam wie zufällige Farbvergleiche zu tun sind). Aus meinen Beobachtungen macht es CIEDE2000 das gleiche über die Zeit, wie die euklidischen RGB ziemlich viel.