Durchschnittsfarbe eines Bitmap "schnell" ermitteln

[Amateurprofi]

Zitat von KodeZwerg:

Guten morgen Gemeinde!

Ein Neuer Tag, ein neues problem
...
Ich versuche aus einem Bitmap eine Durchschnittsfarbe zu ermitteln.
...
Hier ist das was ich aus seinem guten Beispiel #2 gemacht habe, es funktioniert, aber doch recht langsam:
...

Hallo KodeZwerg:
Ich hab dir mal etwas zusammengestoppelt.
Aufruf mit GetAvgColor(Dateiname) oder GetAvgColor(Bitmap)
Mit TestGetAvgColor; hab ich das Ergebnis und die Performance getestet und mit der Funktion aus #3 verglichen.
Die zurückgegebenen Durchschnittsfarben sind identisch, die Ausführungszeiten sind dagegen höchst unterschiedlich.

Delphi-Quellcode:

FUNCTION AvgColor(P,LO,W,H:NativeInt):TColor;
// P  : Zeiger auf das erste Pixel der ersten Zeile einer Bitmap
// LO : Offset (in Bytes) auf die jeweils nächste Zeit
// W  : Breite der Bitmap
// H  : Höhe der Bitmap
{$IFDEF CPUX86}
const
   OfsBlueLo=0; OfsBlueHi=OfsBlueLo+4;
   OfsGreenLo=OfsBlueHi+4; OfsGreenHi=OfsGreenLo+4;
   OfsRedLo=OfsGreenHi+4; OfsRedHi=OfsRedLo+4;
   OfsCount=OfsRedHi+4; OfsH=OfsCount+4; OfsLO=OfsH+4;
   OfsStack=OfsLO+4;
{$ENDIF}
asm
{$IFDEF CPUX86}// EAX=P, EDX=LO, ECX=W, Stack=H
               // Register retten
               push     ebx
               push     edi
               push     esi
               // LO, H und Anzahl Pixel auf Stack legen
               push     edx                  // LO
               mov      ebx,H
               push     ebx                  // H
               imul     ebx,ecx
               push     ebx                  // Anzahl Pixel
               // Summen auf Stack
               push     0
               push     0
               push     0
               push     0
               push     0
               push     0
               // ESI hinter erste Zeile
               lea      ebp,[ecx+ecx*2]
               lea      esi,[eax+ebp]
               neg      ebp
               // Summen ermitteln
@Loop1:        mov      edi,ebp
               xor      ebx,ebx
               xor      ecx,ecx
               xor      edx,edx
@Loop2:        movzx    eax,byte[esi+edi]    // Blue
               add      ebx,eax
               movzx    eax,byte[esi+edi+1]  // Green
               add      ecx,eax
               movzx    eax,byte[esi+edi+2]  // Red
               add      edx,eax
               add      edi,3
               jl       @Loop2               // Nächstes Pixel
               add      [esp+OfsBlueLo],ebx  // Summe Blue
               adc      [esp+OfsBlueHi],0
               add      [esp+OfsGreenLo],ecx // Summe Green
               adc      [esp+OfsGreenHi],0
               add      [esp+OfsRedLo],edx   // Summe Red
               adc      [esp+OfsRedHi],0
               // Zeiger auf nächste Zeile
               add      esi,[esp+OfsLO];
               dec      [esp+OfsH]
               jnz      @Loop1
               // AvgWerte erbitteln
               mov      eax,[esp+OfsBlueLo]
               mov      edx,[esp+OfsBlueHi]
               div      [esp+OfsCount]
               movzx    ecx,al
               shl      ecx,16
               mov      eax,[esp+OfsGreenLo]
               mov      edx,[esp+OfsGreenHi]
               div      [esp+OfsCount]
               mov      ch,al
               mov      eax,[esp+OfsRedLo]
               mov      edx,[esp+OfsRedHi]
               div      [esp+OfsCount]
               mov      cl,al
               mov      eax,ecx              // Result=AvgColor
               // Stack bereinigen
               add      esp,OfsStack
               // Register wieder herstellen
               pop      esi
               pop      edi
               pop      ebx
{$ELSE}        // RCX=P, RDX=LO, R8=W, R9=H
               push     r12
               push     r13
               push     r14
               // Anzahl Pixel in R13
               mov      r13,R8
               imul     R13,R9
               // R11 hinter erste Zeile, R12=-W*3
               lea      r12,[r8+r8*2]
               lea      r11,[rcx+r12]
               neg      r12
               // Summen ermitteln
               xor      rcx,rcx              // Summe Blue
               xor      r8,r8                // Summe Green
               xor      r10,r10              // Summe Red
@Loop1:        mov      r14,r12
@Loop2:        movzx    rax,byte[r11+r14]    // Blue
               add      rcx,rax
               movzx    rax,byte[r11+r14+1]  // Green
               add      r8,rax
               movzx    rax,byte[r11+r14+2]  // Red
               add      r10,rax
               add      r14,3
               jl       @Loop2               // Nächstes Pixel
               // Zeiger auf nächste Zeile
               add      r11,rdx;
               dec      r9
               jnz      @Loop1
               // AvgWerte erbitteln
               mov      rax,rcx              // Blue
               xor      rdx,rdx
               div      r13
               movzx    rcx,al
               shl      rcx,16
               mov      rax,r8               // Green
               xor      rdx,rdx
               div      r13
               mov      ch,al
               mov      rax,r10
               xor      rdx,rdx
               div      r13
               mov      cl,al
               mov      rax,rcx              // Result=AvgColor
               // Register wieder herstellen
               pop      r14
               pop      r13
               pop      r12
{$ENDIF}
end;

Delphi-Quellcode:

FUNCTION GetAvgColor(Bmp:TBitmap):TColor; overload;
var LO,P:NativeInt;
begin
   Assert(Bmp.PixelFormat=pf24bit);
   Assert(Bmp.Width>0);
   Assert(Bmp.Height>0);
   P:=NativeInt(Bmp.ScanLine[0]);
   LO:=NativeInt(Bmp.ScanLine[1])-P;
   Result:=AvgColor(P,LO,Bmp.Width,Bmp.Height);
end;

Delphi-Quellcode:

FUNCTION GetAvgColor(Dsn:String):TColor; overload;
var Bmp:TBitmap;
begin
   Result:=0;
   if not FileExists(Dsn) then
      raise Exception.Create('Datei "'+Dsn+'" nicht gefunden');
   Bmp:=TBitmap.Create;
   Bmp.LoadFromFile(Dsn);
   Result:=GetAvgColor(Bmp);
   Bmp.Free;
end;

Delphi-Quellcode:

// Aus #3 TiGü (Filename hier als Parameter statt lokale Variable)
function GetAvgBmpColor(Filename:String): TColor;
type
  TRgbTriple = packed record
    // do not change the order of the fields, do not add any fields
    Blue: Byte;
    Green: Byte;
    Red: Byte;
  end;
  TRgbTripleArray = packed array[0..MaxInt div SizeOf(TRgbTriple) - 1] of TRgbTriple;
  PRgbTripleArray = ^TRgbTripleArray;
var
  x, y: Integer;
  r, g, b: Integer;
  Pixel: TRgbTriple;
  Bmp: TBitmap;
//  Filename: string;
  wic: TWICImage;
  Resolution: Integer;
  ScanLinePtr: Pointer;
begin
  Result := 0;
  //Filename := 'Der magische Pfad';
  if not FileExists(Filename) then
    Exit;
  bmp := TBitmap.Create;
  wic := TWICImage.Create;
  try
    wic.LoadFromFile(Filename);
    bmp.Assign(wic);
    bmp.PixelFormat := pf24bit;
    r := 0;
    g := 0;
    b := 0;
    Assert(bmp.PixelFormat = pf24bit);

    for y := 0 to Pred(Bmp.Height) do
    begin
      ScanLinePtr := bmp.Scanline[y]; // der springende Punkt!
      for x := 0 to Pred(Bmp.Width) do
      begin
        Pixel := PRgbTripleArray(ScanLinePtr)^[x];
        r := r + Pixel.Red;
        g := g + Pixel.Green;
        b := b + Pixel.Blue;
      end;
    end;

    Resolution := (bmp.Width * bmp.Height);
    r := r div Resolution;
    g := g div Resolution;
    b := b div Resolution;
    Result := RGB(r, g, b);
  finally
    bmp.Free;
    wic.Free;
  end;
end;

Delphi-Quellcode:

PROCEDURE TestGetAvgColor;
const Width=2900; Height=2900; Color=$010203;
var T0,T1,T2:Cardinal; R:TRect; Bmp:TBitmap; CL1,CL2:TColor; Dsn:String;
begin
   Bmp:=TBitmap.Create;
   Bmp.PixelFormat:=pf24Bit;
   Bmp.SetSize(Width,Height);
   SetRect(R,0,0,Bmp.Width,Bmp.Height);
   Bmp.Canvas.Brush.Color:=Color;
   Bmp.Canvas.FillRect(R);
   Dsn:=ExtractFilePath(ParamStr(0))+'Test.bmp';
   Bmp.SaveToFile(Dsn);
   Bmp.Free;
   T0:=GetTickCount;
   CL1:=GetAvgColor(Dsn);
   T1:=GetTickCount;
   CL2:=GetAvgBmpColor(Dsn);
   T2:=GetTickCount;
   ShowMessage('$'+IntToHex(CL1,8)+' '+IntToStr(T1-T0)+#13+
               '$'+IntToHex(CL2,8)+' '+IntToStr(T2-T1));
end;

[Jens01]

Zitat:

Ja das sprang mir auch gerade ins Auge.
Trotzdem, theoretisch gibt es Überläufe erst ab Bildgrößen von 24000x24000.
Ich denke es ist noch ein bischen Zeit bis dahin

Man kann auch einfach den Durchschnittswert aufaddieren.

vom Prinzip her so:

Delphi-Quellcode:

r := 0;
Resolution := (bmp.Width * bmp.Height);
 for i := to do
  r := r + Pixelwert[i].red / Resolution;

r := round(r);

[himitsu]

Mathematisch, von den Grenzen der Floats, macht es leider keinen Unterschied, ob man jedes Pixel dividiert und addiert, oder ob man erst alles addiert und erst am Ende dividiert.
Lezteres ist aber schneller, da "ganz" oft dividieren natürlich langsamter ist, als nur Einmal.

Bei ganz ganz ganz vielen Pixeln ist der Wert irgendwann so groß, dass die nächste Addition des kleinen Wertes, abgeschnitten wird.
Aber Double hat mit 52 Bit (52+11) mehr als der 32 Bit-Integer, somit dauert es da länger, bis zum Rechenfehler/überlauf,
und gegenüber 64 Bit, und dessen Integeroperation (64 Bit-compilat), ist Float in der FPU dann wieder langsamer. (ja, eine einzelne FPU gibt es physisch nicht mehr)

Single mit 23 Bits (23+8) raucht schon zu etwas früher ab.

[Jens01]

Zitat:

Bei ganz ganz ganz vielen Pixeln ist der Wert irgendwann so groß, dass die nächste Addition des kleinen Wertes, abgeschnitten wird.

r wird nicht größer als 255, oder?

[KodeZwerg]

So wie ich es verstanden habe fügt sich ein RBG wert aus 3 DWORDs zusammen.

[himitsu]

Es ist ein DWORD, dass aus 3+1 Bytes besteht

[KodeZwerg]

@Michael II
Nun passiert da was... aber mein Ergebniss ist falsch.

Delphi-Quellcode:

function GetAvgGDIColor(const Filename: string): TColor;
var
  gr: TGPGraphics;
  Bmap: TGPBitmap;
  col: TGPColor;
begin
  Result := 0;
  bmap := TGPBitmap.Create(Filename);
  try
    gr := TGPGraphics.Create( bmap );
    try
      gr.ScaleTransform( 1/bmap.GetWidth, 1/bmap.GetHeight );
      gr.DrawImage( bmap, 0,0 );
      bmap.GetPixel(0,0, col);
      Result := RGB(GetRValue(col), GetGValue(col), GetBValue(col));
    finally
      gr.Free;
    end;
  finally
    bmap.Free;
  end;
end;

Falls Du Dich nochmal reinklinken könntest um mich zu korrigieren, das wäre nett!

Zitat von himitsu:

Es ist ein DWORD, dass aus 3+1 Bytes besteht

Mein Fehler!

[Amateurprofi]

@KodeZwerg:

In #16 wurde in den Raum geworfen, ob man nicht einfach ein Resize auf 1x1 Pixel machen kann.
Ich hab das mal geprüft und in meiner Funktion TestGetAvgColor; vor dem Bmp.Free folgendes eingefügt:

Delphi-Quellcode:

   T3:=GetTickCount;
   Bmp2:=TBitmap.Create;
   Bmp2.PixelFormat:=pf24Bit;
   Bmp2.SetSize(1,1);
   SetRect(R,0,0,1,1);
   Bmp2.Canvas.StretchDraw(R,Bmp);
   CL3:=Bmp2.Canvas.Pixels[0,0];
   Bmp2.Free;
   T3:=GetTickCount-T3;

Das ShowMessage am Ende hab ich abgeändert in:

ShowMessage('$'+IntToHex(CL1,8)+' '+IntToStr(T1-T0)+#13+
'$'+IntToHex(CL2,8)+' '+IntToStr(T2-T1)+#13+
'$'+IntToHex(CL3,8)+' '+IntToStr(T3));

Scheint zu funktionieren, was aber auch daran liegen könnte, dass in der Testprozedur alle Pixel die gleiche Farbe haben.
Korrektur: Hab es gerade mit einem echten Bild geprüft.
Die Methode, das Bild auf 1x1 Pixel zu reduzieren, liefert eine andere Durchschnittsfarbe.

[Michael II]

Zitat von Amateurprofi:

@KodeZwerg:

Die Methode, das Bild auf 1x1 Pixel zu reduzieren, liefert eine andere Durchschnittsfarbe.

Ich nehme auch an, dass GDI+ beim Skalieren auf 1x1 nicht oft die gleiche Durchschnittsfarbe berechnet. Du könntest ja auch auf ein 10x10 oder ähnlich skalieren und dort rechnen.

Die 1x1 Bitmap Farbe hängt natürlich u.a. vom verwendeten Skalier-Algorithmus ab.

Bliebe die Frage: Welche Farbe ein Mensch als die "bessere" Durchschnittsfarbe bewerten würde.

Hast du irgendwo einen Link auf wissenschaftliche Literatur (wäre interessant), wo sowas wie eine "Durchschnittsfarbe" besprochen wird. Ich nehme an, dass in der Grafikbranche nicht einfach über RGB addiert und der Mittelwert genommen wird. Da werden doch sicher andere Modelle "bemüht"?

[KodeZwerg]

Zitat von Michael II:

Hast du irgendwo einen Link auf wissenschaftliche Literatur (wäre interessant), wo sowas wie eine "Durchschnittsfarbe" besprochen wird. Ich nehme an, dass in der Grafikbranche nicht einfach über RGB addiert und der Mittelwert genommen wird. Da werden doch sicher andere Modelle "bemüht"?

Nein leider nicht, ich habe mich da auf mein Bauchgefühl verlassen das man es so machen könnte, einfach angefangen zu tippsen ohne Recherche(!), rein Augenscheinlich betrachtet, liefert mir TiGü's verfahren (mit meiner simplen berechnung) sehr gute Ergebnisse.
Reine Bitmaps habe ich gar keine zum Testen damit ich auch Eure (Assembler und GDI+) besser testen kann.