¿Cómo puedo optimizar aún más esta función de la diferencia de color?
https://stackoverflow.com/questions/3049213
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Me han hecho esta función para calcular las diferencias de color en el espacio de color CIE Lab, pero carece de la velocidad. Como yo no soy un experto en Java, me pregunto si cualquier gurú de Java rodea tiene algunos consejos que pueden mejorar la velocidad aquí.
El código se basa en la función de Matlab se menciona en el bloque de comentario.
/**
* 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);
}
Solución
cos es caro, especialmente 4 en una fila. Parece que está cos computación (n a + b) donde b es una constante y n es un entero pequeño. Esto significa que puede calcular previamente cos (B) y sin (B) y al cómputo de tiempo de ejecución simplemente cos (CV) y sin (CV). Puede obtener cos (n a + b), haciendo uso repetido de
cos(a+b) = cos(a)*cos(b)-sin(a)*sin(b)
va a ser el comercio de un par de sins y coss para algunas multiplicaciones y sumas, es casi seguro que vale la pena.
Se puede hacer mejor si se siente ambicioso. Que está recibiendo hp indirectamente de un atan2. El trig-function(rational-function(inverse-trig-function(x))) patrón de frecuencia puede ser sustituida por una combinación de polinomios y raíces que son más rápidos de evaluar que trig funciones.
No sé cómo pow está implementado en Java, pero si utiliza los registros, que puede ser mejor de conseguir Cp7 usando Cp2=Cp*Cp;Cp4=Cp2*Cp2;Cp7=Cp4*Cp2*Cp;
Actualización: Conseguir un poco más especulativo en este momento, ya que no tengo tiempo para realmente volver a escribir el código. La optimización de la energía y la optimización de trigonometría son realmente la misma cosa disfrazada! La optimización de trigonometría es una versión de la optimización de la energía aplicada a los números complejos. Lo que es más, la línea
double dH = 2 * Math.sqrt(CpProd) * Math.sin(dhp / 2);
es parte de una serie compleja operación de raíz cuadrada. Esto me hace pensar que una gran parte de este código en realidad podría ser escrito para utilizar números complejos eliminando casi todas las funciones trigonométricas. No sé cómo su número de aritmética compleja es, sin embargo ...
Otros consejos
En general, cualquier sistema que implementa este y tiene serios problemas de velocidad no va a estar haciendo colores al azar. Se va a hacer varios colores distintos. Incluso una imagen gigante lleno de diferentes colores se va normalmente sólo para que unos pocos miles de colores. Recomiendo encarecidamente un algoritmo de almacenamiento en caché. Aunque si la velocidad es una preocupación que debe enrollar su propio (desea primitivas solamente, velocidad).
No hay mucho optimizando al hacerse con la rutina actual distancia de color en sí, sino que escribió un sistema de almacenamiento en caché para esta cosa y se fue del orden de 100 veces más rápidas. La rutina de la distancia iba desde el factor dominante abrumadora a un bache. No se debe tratar de reducir la velocidad de eso. Es posible que eek algo. Sin embargo, reducir el número de veces le invocar la cosa correctamente.
Usted tiene dos entradas de ajuste y produce una sola salida de conjunto, y lo hace después de un tiempo muy largo. 7 dobles por índice de almacenamiento en caché. Eso es 14 bytes. Para una huella de memoria 14 meg (más o menos, haciendo caso omiso de los hashes o lo que no, que estamos hablando de matrimonio). Puede almacenar un millón de entradas y eso es suficiente para que si tiene como 1k diferentes colores típicos podrás llegar alto 90% s aciertos de caché. Incluso se puede reducir este enorme si va a convertir sus colores iniciales de RGB a Lab (aquellas conversiones deben almacenarse en caché también). Verás una velocidad de hasta si se golpea como el 5% de las veces. Y obtendrá éxitos probable que el 99% del tiempo (a menos que estés haciendo algo extraño como comparaciones de color al azar). De mis observaciones que hace CIEDE2000 tomar más o menos lo mismo acerca del tiempo como euclidiana RGB.
