Rechnungen (Sättigung setzen) verschnellern

[thE_29]

Hallo!


Also es geht darum, dass ich bei einem Bild die Sättigung verändern muss.
Dazu gucke ich mir jeden Pixel an mit einer LookupTable und änder die Werte!

Zuerst habe ich RGB in HSB geändert und S = Saturaion = Sättingung geändert.

Bei meinem 2 Kerne Hobel flitzt das ganze natürlich dahin und braucht so 450MS. (Bei einer Auflösung von 1280x1024).

So, aber auf dem Teil wo die App laufen soll, braucht das ganze schonmal 2.5 Sekunden .


Bin dann hergegangen und wollte rausfinden wie sich die Sättigung auf die RGB Werte äußert!
Auf dieser Seite hier: http://home.comcast.net/~ed-abramson/14ColorTest/HSB-and-RGB-Colors.html kann man sich prima mit den Reglern spielen!

Mir sind dann folgende Dinger aufgefallen!

.) R = G = B == 0% Sättigung == Wert ändert sich NICHT (50% weniger Sättigung von 0 sind nunmal wieder 0)
.) Der höchste Wert von RGB bleibt immer bestehen!
.) Die anderen 2 Werte ändern sich in der Relation:
Zu berechnender Wert += (Höchster Wert - zu berechnender Wert) / 2 == 50% Sättigung.

Also ist R der höchste Wert sieht die Berechnung von G und B so aus

G = G + (R - G) / 2;
B = B + (R - B) / 2;

Das ganze braucht nun auf der Zielmaschine "nur noch" 1.5 Sekunden! Also 1 Sekunde Zeitersparnis dank wegfallender Umrechnung in HSB und wieder zurück in RGB.


Ich müsste das ganze aber noch schneller machen.

Mein Code sieht so aus:

    //Methode tauscht die Pixelfarben um
    public int[] lookupPixel(int[] src, int[] dest)
    {
      int x = 0, y = 0, z = 0;
      if(src[0] == src[1] && src[1] == src[2])
      {
        return src;
      }
      if(src[0] > src[1] && src[0] > src[2])
      {
        x = 2;
        y = 1;
        z = 0;
      }
      else if(src[1] > src[0] && src[1] > src[2])
      {
        x = 2;
        y = 0;
        z = 1;
      }
      else
      {
        x = 1;
        y = 0;
        z = 2;
      }
      //rechnet die Sättigung zurück (größte Wert von RGB bleibt bestehen, nur die 2 kleineren ändern sich)
      src[x] += (src[z] - src[x]) / INT_SAETTIGER;
      src[y] += (src[z] - src[y]) / INT_SAETTIGER;
      return src;
    }

Wobei INT_SAETTIGER == 2 == 50% ist.

Wie kann ich das ganze noch optimieren?

Habe schon probiert das src[] in eine Hashtable zu putten, aber da ich ne Kopie vom alten src dann brauche, da src wieder das neue ist (und sein muss, da er auf das Array src wieder zurückgreift zum Bild manipulieren und nicht auf das was man returniert), hat sich die Zeit auf meiner Maschine von 400MS auf 780MS fast verdoppelt.

mfg

 

[Marco13]

Hm. Ich glaube, so eine LookupOp ist per se nicht unbedingt die schnellste: Je nachdem, welchen Typ das Eingabebild hat, kann das Lesen und Schreiben der src und dst-Arrays glaubich relativ aufwändig sein. Wenn du ein compilierbares Beispiel posten würdest, würde ich später vielleicht nochmal ein bißchen rumspielen...

 

[Gast2]

Moin,

Wie kann ich das ganze noch optimieren?

Du hattest doch schon den richtigen Gedanken ... eine Look-Up-Table ... jeder Berechnungsschritt kostet Zeit und RGB->HSI sind nicht gerade wenig Rechenschritte ... Du musst die LUT allerdings aus gleich passend aufbauen

das Ganze ist zwar kein Java ... sollte aber nicht das Problem sein

	// HSI <-> RGB
	RGB2HSI = new int __gc [0x1000000];	// sollten 64 MB sein
	HSI2RGB = new int __gc [0x1000000];	// sollten 64 MB sein

	Diagnostics::Debug::Write("RGB2HSI - ");

	int prozent = 0; // RGB -> HSI
	for(int r = 0; r < 256; r++)
	{
		int p = (int) ( ((double) r / 255.0) * (double) 100 );
		if (p != prozent)
		{
			prozent = p;
			Diagnostics::Debug::Write(".");
			__raise InitProgress(p);
			if (!(p % 10)) Diagnostics::Debug::Write(p.ToString());
		}
		
		for(int g = 0; g < 256; g++)
		{
			for(int b = 0; b < 256; b++)
			{
				double R, G, B;
				double min, max;
				double H;
				double S;
				double V;

				R = r / 255.0;
				G = g / 255.0;
				B = b / 255.0;

				// min / max festlegen
				max = (R > B) ? R : B;
				max = (max > G) ? max : G;
				min = (R < B) ? R : B;
				min = (min < G) ? min : G;

				// H berechnen
				if (max == min)
				{
					H = 0;
				} else
				{
					if (R == max) H = (0 + (G - B) / (max - min)) * 60;
					if (G == max) H = (2 + (B - R) / (max - min)) * 60;
					if (B == max) H = (4 + (R - G) / (max - min)) * 60;
				}
				if (H < 0) H += 360;
				// ---> ??? ---> if (h > 360) H -= 360;
				if (H > 360) H -= 360;
				//H = (H / 360.0) * 255.0;	// wird in 2 Byte gespeichert

				// S berechnen
				if (max == 0)
				{
					S = 0;
				} else
				{
					S = (max - min) / max;
				}
				S = S * 100;

				// V brechnen ... sehr komplex
				V = max * 100;

				// das Ganze jetzt wieder packen und in den Wert schreiben
				//col = ((((int) Math::Round(H, 0) << 8) + (int) Math::Round(S, 0)) << 8) + (int) Math::Round(V, 0);
				int hsi = ((int) Math::Round(S, 0)) << 8;	// Saturation
				hsi |= (((int) Math::Round(H, 0)) << 15);	// Hue in die Bytes von Saturation mit rein !!
				hsi += (int) Math::Round(V, 0);

				RGB2HSI[(((r << 8) + g) << 8) + b] = hsi;
			}
		}
	}
	Diagnostics::Debug::WriteLine("");

	Diagnostics::Debug::Write("HSI2RGB - ");
	prozent = 0;	// HSI -> RGB
	for(int hue = 0; hue < 360; hue++)
	{
		int p = (int) ( ((double) hue / 360.0) * (double) 100 );
		if (p != prozent)
		{
			prozent = p;
			Diagnostics::Debug::Write(".");
			__raise InitProgress(p + 100);	// weil schon der nächste Schritt
			if (!(p % 10)) Diagnostics::Debug::Write(p.ToString());
		}
		
		for(int saturation = 0; saturation <= 100; saturation++)
		{
			for(int value = 0; value <= 100; value++)
			{
				double R, G, B;
				int h1 = (hue / 60);

				double d_hue = hue / 1.0;
				double d_value = value / 100.0;
				double d_saturation = saturation / 100.0;
				
				double f = (( (double) hue / 60.0) - (double) h1);
				double p = (d_value * (1 - d_saturation));
				double q = (d_value * (1 - (d_saturation * f)));
				double t = (d_value * (1 - (d_saturation * (1 - f))));

				switch (h1)
				{
					case 0:
					{
						R = d_value;
						G = t;
						B = p;
						break;
					}
					case 1:
					{
						R = q;
						G = d_value;
						B = p;
						break;
					}
					case 2:
					{
						R = p;
						G = d_value;
						B = t;
						break;
					}
					case 3:
					{
						R = p;
						G = q;
						B = d_value;
						break;
					}
					case 4:
					{
						R = t;
						G = p;
						B = d_value;
						break;
					}
					case 5:
					{
						R = d_value;
						G = p;
						B = q;
						break;
					}
				}
				R *= 255.0;
				G *= 255.0;
				B *= 255.0;

				int col = (pixel) Math::Round(R, 0) << 16;
				col += (pixel) Math::Round(G, 0) << 8;
				col += (pixel) Math::Round(B, 0);

				// das unterste Bit von Hue landet im Byte für Saturation !!!
				int hsi = (saturation & 0xff) << 8;	// Saturation
				hsi |= ((hue & 0x1ff) << 15);			// hier jetzt nur 15 Bit verschieben
				hsi += (value & 0xff);				// jetzt noch Value ... spart gesammt 64 MB

				HSI2RGB[hsi & 0xffffff] = col;
			}
		}
	}
	Diagnostics::Debug::WriteLine("");

anschließend brauchst Du nur Deinen RGB-Wert über die Tabelle in HSI konvertieren ... ziehst Dir S über Bit-Opperationen, änderst S und holst Dir den RGB-Wert über die 2. Tabelle

hand, mogel

 

[thE_29]

Achso, du meinst also ich soll schon mal alle Wert vorberechnen und dann halt diese schon zurückgeben?

Nur die Frage ist halt, ob er zum Nachschaun wieder nicht zulange Zeit braucht!
Der Weg übers Hashtable war ja auch net gerade ein Vorteil.

 

[Gast2]

Moin,

Achso, du meinst also ich soll schon mal alle Wert vorberechnen und dann halt diese schon zurückgeben?

Nur die Frage ist halt, ob er zum Nachschaun wieder nicht zulange Zeit braucht!
Der Weg übers Hashtable war ja auch net gerade ein Vorteil.

sehe da nicht das zeitliche Problem ... die LUT arbeitet mit O(1) ... die Hashtable mit O(ln)

int rgb = 0xff00f0;
int hsi = RGB2HSI[rgb];

hand, mogel

 

[thE_29]

Naja, das Problem ist nicht die Berechnung

Also ich brauche kein HSI/HSB/HSV für die Sättigung zum Ausrechnen!

 

[Gast2]

Moin,

Also ich brauche kein HSI/HSB/HSV für die Sättigung zum Ausrechnen!

so wie ich das verstanden habe, willst Du die Sättigung ändern

int rgb = 0xff00f0;  // Farbe "holen"
int hsi = RGB2HSI[rgb]; // nach HSI "rechnen"
int s = (hsi & 0xff00) >> 8; // Sättingung holen ... !!! Bits stimmen nicht !!!
s += 5; // Sättigung ändern
hsi = (hsi & 0xff00ff) & (s << 8);  // zurück schreiben
rgb = HSI2RGB[hsi]; // von HSI nach RGB

hand, mogel

 

[thE_29]

Mein Code oben ändert schon die Sättigung

Man braucht für die Sättigung kein HSB/HSV! Anscheinend weiß das keiner auf der Welt außer mir :bae:

Wenn du meinen Post liest, wirst du sehen das ich die Formel beschrieben habe, wie ich die Sättigung ändern kann.

Mein Problem besteht darin, dass auch das zulange dauert. Von RGB in HSB/HSI/HSV rechnen und wieder zurückrechnen will ich gar nicht reden (das braucht noch länger).

Mir gehts darum, mein obiges Codesegment zu verschnellern!!

 

[Marco13]

Ja, schneller geht es, wenn man sich direkt eine LookupTable für die Pixel baut

    private int lut[];

    void doit()
    {
       if (lut == null) initLUT();

       // beide Images vom Typ BufferedImage.TYPE_INT_RGB
        int in[] = (int[])originalImage.getRaster().getDataElements(0,0,w,h,null);
        int out[] = (int[])modifiedImage.getRaster().getDataElements(0,0,w,h,null);
        for (int i=0; i<in.length; i++)
        {
            out[i] = lut[in[i]];
        }
        modifiedImage.getRaster().setDataElements(0,0,w,h,out);
    }

    private void initLUT()
    {
        lut = new int[256*256*256];
        for (int i=0; i<lut.length; i++)
        {
            int b[] = new int[3];
            b[0] = (int)((i >>> 16) & 0xFF);
            b[1] = (int)((i >>>  8) & 0xFF);
            b[2] = (int)((i >>>  0) & 0xFF);
            saturationLookupTable.lookupPixel(b, null); // Deine LookupOp, jaja, ich bin faul....
            int rgb = (b[0] << 16) | (b[1] <<  8) | (b[2] <<  0);
            lut[i] = rgb;
        }

    }

Bei der LookupOp.filter-Methode braucht's bei mir bei einem Bild 250ms, mit dieser Methode nur 50...

 

[thE_29]

Da kommt leider das hier raus:
java.lang.ArrayIndexOutOfBoundsException: -8355712


Und zwar in der Zeile

out = lut[in];


Nachtrag: Also bei mir ist in durch die Bank negativ! Da ist kein einziger Eintrag positiv...

Selbst wenn ich nur ein schwarzes Rechteck hinmale, geht es nicht..


Könntest du mir dein Bsp zukommen lassen wo es funktioniert?

 

[Marco13]

Verwendest du als Eingaben wirklich BufferedImages vom Type BufferedImage.TYPE_INT_RGB und NICHT BufferedImage.TYPE_INT_ARGB?

Falls du das Bild (z.B. ein PNG) mit ImageIO liest, könntest du es mit

BufferedImage input = ImageIO.read(new File("C:/image.jpg"));
BufferedImage image = new BufferedImage(input.getWidth(), input.getHeight(), BufferedImage.TYPE_INT_RGB);
image.getGraphics().drawImage(input, 0,0,null);

in ein passendes Bild umwandeln.

Falls du Transparenz brauchst, müßte die LUT entsprechend größer sein (dann aber schon SEHR groß :? ) Man hat natürlich immer den Tradeoff zwischen Speicherplatz und Rechenzeit, da könnte man dann noch in die eine oder andere Richtung dran schrauben...

 

[WieselAc]

Zwei simple Ansätze habe ich noch:

Zum einen könntest du mal testen, ob es einen Zeitvorteil bringt das Bild von mehreren Threads parallel bearbeiten zu lassen... ich vermute zwar, dass du es schon probiert hast, aber da es hier noch nicht stand wollt ich es zumindest mal erwähnen.

Zum anderen könntest du je nach Art der Bilder versuchen die Anzahl der zu berechnenden Pixel zu reduzieren. zB.: Nur für jedes zweite Pixel die Sättigung berechnen und dazwischen interpolieren... Ob der Ansatz überhaupt Sinn macht und welche Strategie man da am besten benutzt hängt allerdings sehr stark von den Bildern ab.

 

[beastofchaos]

Ich weiß der Thread ist alt, aber ich hätte noch eine zeitsparendere Version, die aber die selbe Berechnung wie thE_29 benutzt.
Wenn sich R am höchsten sind, verändern sich die beiden anderen Werte nach der selben Formel, weshalb, du nicht für beide, sondern nur für eine beliebige "Zweitfarbe" deine tolle Formel anwenden musst.
Also hast du ein LUT mit "nur noch" 256² Einträgen. Die intensivste Farbe von 0..256 und eine beliebige andere, die sich nach dieser richtet, auch im Bereich 0...256.

Ich denke, ich muss nicht betonen, dass 256³ - 256² Berechnungen weniger ein Großteil an Zeit einsparen

Ich arbeite selbst an einem Grafikprogramm und probier das jetzt mal aus, was ich mir theoretisch erdacht habe und melde mich mit einem funktionierendem Codeausschnitt zurück

Gruß, Thomas

 

[beastofchaos]

Die angegebene Formel ("G = G + (R - G) / 2") stimmt leider nicht immer.
Also zwei Farbanteile lassen sich schon leicht definieren:

Die "größte" Farbe (MAX) bleibt immer gleich, während die "kleinste" Farbe (MIN) sich nach folgenden Formel richtet:

MIN = MAX * ( 1 - Saturation / 100)

Wie die mittlere Farbe (MID) sich verändert, kann ich leider nicht eindeutig erkennen, aber ich hab schon folgende Formel, für die man halt wissen muss, wie die Farbe bei Sättigung = 100 aussieht. Sprich der hier verwendete Wert MID_2 ist der Wert MID bei Sättigung = 100.

x = 100 / (MAX/MID_2 - 1)) + 100
MID = MAX * ( 1 - Saturation / x)

Um MID_2 zu umgehen, müsste man wissen, in welchen Schritten sich MID verändert...

Gruß, Thomas