[C#] Histogram van aantal kleuren uit bitmap

[Verwijderd]

In een andere topic heb ik geprobeerd om de transparante kleur op te vragen van een png en eventueel die kleur te gebruiken om het plaatje als nog transparant te maken.

Ik kreeg een linkje naar een JAVA tooltje.

Het tooltje telt voor alle kleuren hoe vaak ze voorkomen. Vervolgens is de kleur met de hoogste waarde de achtergrond kleur. Dit geldt natuurlijk niet altijd, maar in mijn situatie is dat wel altijd zo.

Nu probeer ik hetzelfde in C# te maken, maar daar kom ik niet goed uit.
Ik kan de palette uitlezen en vervolgens van elke pixel de waarde opvragen met GetPixel, maar dat duurt erg lang.
Ik kan het ook met Lockbits en Pointers werken, maar dat is unsafe code en die kan ik niet gebruiken, omdat ik een onderdeel van een grotere applicatie schrijf en die staat geen unsafe code toe.

Is er nog een andere manier om zo'n histogram te maken?
Als JAVA het kan, moet C# het toch ook kunnen

[Reptile209]

Uiteindelijk zal de JAVA-implementatie - neem ik aan - ook alle pixels aflopen om te kijken welke kleur ze hebben. Ze hebben hem alleen gewrapped in één of andere handige analyse-klasse. Blijkbaar hebben ze daar een snellere implementatie voor gemaakt dan dat jij hebt. Post eens wat (relevante) code, misschien dat op basis daarvan (grote) verbeteringen te maken zijn die je al voldoende verder helpen.

[NickThissen]

Je zou misschien een iets minder nauwkeurige analyze kunnen uitvoeren. Bijvoorbeeld de kleuren middelen (het plaatje als het ware 'blurren') en daarna een op de 10 pixels of iets dergelijks uitlezen. Dat blurren zal natuurlijk ook weer tijd kosten, dus je zult wat moeten experimenteren om te kijken of je het wel sneller kan krijgen of dat het alleen maar langzamer wordt.

EDIT
Ook dacht ik dat ik wel eens iets van een LockBits gezien had, en dat was in VB.NET wat, voor zover ik weet, geen unsafe code ondersteund. Weet je zeker dat LockBits unsafe code nodig heeft?

[ Voor 21% gewijzigd door NickThissen op 25-05-2010 15:10 ]

[Janoz]

Hmmm... blurren... 4 pixel waarden uitlezen, deze vervolgens middelen en dan weer naar de 4 pixels wegschrijven. Dat zal vast een stuk sneller zijn dan alleen 4 pixels uitlezen..

[NickThissen]

Zijn er geen andere, snellere manieren om te blurren dan? Met een matrix vermenigvuldigen ofzo? Het hoeft ook niet perse blurren te zijn (die stap kun je desnoods ook helemaal weglaten), zolang je de kleuren maar een beetje middelt, anders ga je wel erg veel informatie negeren door maar een tiende van alle pixels te tellen.

[Janoz]

Om iets met de kleur te doen moet je weten welke kleur het heeft. Ook bij een matrix vermenigvuldiging zul je toch echt de data op moeten halen voordat je er iets mee kunt doen. Data ophalen, bewerking uitvoeren, data wegschrijven, data opvragen en histogram maken is natuurlijk altijd langzamer dan data opvragen en histogram maken.


De TS zal waarschijnlijk moeten kijken wat de bottleneck is bij de getPixel implementatie. Het zou best kunnen dat deze methode geoptimaliseerd is voor het opvragen van een enkele pixel in de bitmap en er tijdens die aanroep een heleboel extra dingen gebeurt.

De java implementatie doet inderdaad gewoon het aflopen van alle pixels. Hier in regel 81 t/m 87.

[ Voor 10% gewijzigd door Janoz op 25-05-2010 15:31 ]

[Reptile209]

edit:
Eh, ja, wat hij ^^ zegt dus

NickThissen: welke methode je ook zou kiezen, het komt - zoals Janoz terecht zegt - altijd uit op:
1) lees bestaande pixelwaarden in
2) doe blur
3) schrijf nieuwe pixelwaarden weg

De TS is al klaar met stap 1, dus kosten 2 en 3 per definitie meer tijd. Wat jij zoekt is allen het tellen van elke 2e (of 3e of 10e) pixel, maar dan loop je het risico dat er geen hout van je histogram kost. Stel je telt alleen elke 2e pixel (eentje wel, eentje niet, eentje wel, enz.) en je hebt een zwart/wit raster met puntje zwart, puntje wit, puntje zwart, enz.). Dan zie je al dat je vreselijk nat gaat. Bij een echte figuur zal het minder sterk zijn, maar toch.

[ Voor 3% gewijzigd door Reptile209 op 25-05-2010 15:34 ]

[NickThissen]

Ik heb even gekeken met .NET Reflector wat de GetPixel methode doet, en zoals te verwachten wordt een funcite in gdiplus.dll aangeroepen:

C#:

public Color GetPixel(int x, int y)
{
    int argb = 0;
    if ((x < 0) || (x >= base.Width))
    {
        throw new ArgumentOutOfRangeException("x", SR.GetString("ValidRangeX"));
    }
    if ((y < 0) || (y >= base.Height))
    {
        throw new ArgumentOutOfRangeException("y", SR.GetString("ValidRangeY"));
    }

    // gdiplus.dll functie aanroep:
    int status = SafeNativeMethods.Gdip.GdipBitmapGetPixel(new HandleRef(this, base.nativeImage), x, y, out argb);

    if (status != 0)
    {
        throw SafeNativeMethods.Gdip.StatusException(status);
    }
    return Color.FromArgb(argb);
}

Die SafeNativeMethods.Gdip.GdipBitmapGetPixel() methode kan ik verder niet zien, behalve de declaratie:

C#:

[DllImport("gdiplus.dll", CharSet=CharSet.Unicode, SetLastError=true, ExactSpelling=true)]
internal static extern int GdipBitmapGetPixel(HandleRef bitmap, int x, int y, out int argb);

Je zou die functie zelf nog kunnen opzoeken om te kijken of die nog sneller kan, maar het lijkt me sterk. De range check voor x en y die de GetPixel functie doet zullen je code ook niet veel langzamer maken (hoewel je die natuurlijk ook weg kan laten als je zeker weet je dat x en y binnen de range blijven).

[Reptile209]

Ik gok dat het probleem niet in de GetPixel-functie zelf zit, maar in de code die TS daar omheen gebrouwen heeft. Dit zal inderdaad niet veel sneller kunnen (of hoeven, tenzij je 100-megapixel plaatjes wil gaan bewerken).

[NickThissen]

Ik heb toch wel vaker gehoord dat GetPixel gewoon traag is, en dat je voor een serieuze toepassing toch altijd op LockBits terug moet vallen.

[Davio]

Post de code eens zoals je hem nu hebt.

[CodeIT]

NickThissen schreef op dinsdag 25 mei 2010 @ 15:49:
Ik heb toch wel vaker gehoord dat GetPixel gewoon traag is, en dat je voor een serieuze toepassing toch altijd op LockBits terug moet vallen.

Dat komt volgens mij doordat voor elke call naar GetPixel/SetPixel de gehele bitmap wordt gelockd en unlocked in gdiplus.dll.

[matthijsln]

Janoz schreef op dinsdag 25 mei 2010 @ 15:29:
De java implementatie doet inderdaad gewoon het aflopen van alle pixels. Hier in regel 81 t/m 87.

Ik heb het Java tooltje maar wat geoptimaliseerd want dat was het eerst niet Het traagst was trouwens het gebruik maken van een hashmap in een inner loop. De images zijn gegarandeerd met een palette dus max 256 kleuren, dat is efficienter bij te houden met een array.

In Java is het trouwens zo dat je ook bij pixels kunt komen in een grote array zonder voor elke pixel een methode aan te roepen, maar dat was niet heel veel sneller (mogelijk dat dat voor .NET anders is). Ter info, voor een 7500x7500 plaatje kost het tellen ongeveer 666 ms op mijn 2.66 GHz Core 2.

[Verwijderd]

matthijsln schreef op dinsdag 25 mei 2010 @ 16:01:
[...]


Ik heb het Java tooltje maar wat geoptimaliseerd want dat was het eerst niet Het traagst was trouwens het gebruik maken van een hashmap in een inner loop. De images zijn gegarandeerd met een palette dus max 256 kleuren, dat is efficienter bij te houden met een array.

In Java is het trouwens zo dat je ook bij pixels kunt komen in een grote array zonder voor elke pixel een methode aan te roepen, maar dat was niet heel veel sneller (mogelijk dat dat voor .NET anders is). Ter info, voor een 7500x7500 plaatje kost het tellen ongeveer 666 ms op mijn 2.66 GHz Core 2.

Maar als als je gegarandeerd een pallet van 255 waarden hebt moet elk pixel toch precies 1 byte zijn? Kun je dan niet veel makkelijker gewoon het bestand parsen (In geval van een ongecomprimeerd BMP bestand)?
Of misschien kijken of je de BitmapStream op een andere manier kunt bereiken in C#

[Davio]

Oh, minder dan 1 seconde, dat is te overleven.

[Janoz]

matthijsln schreef op dinsdag 25 mei 2010 @ 16:01:
[...]


Ik heb het Java tooltje maar wat geoptimaliseerd want dat was het eerst niet Het traagst was trouwens het gebruik maken van een hashmap in een inner loop. De images zijn gegarandeerd met een palette dus max 256 kleuren, dat is efficienter bij te houden met een array.

Inderdaad. Toen ik die regel zag jeukte het ook wel in mijn ogen. Het is een beetje het gevolg van het enkel objecten op te kunnen slaan in een collection, maar er zijn een stuk efficientere methoden te verzinnen waarbij je niet voor elke pixel een nieuw object aanmaakt.

[Verwijderd]

Ik ben wat aan het stoeien gegaan en op deze code gekomen:

C#:

private static Color GetTransparentColor(string imageFileName)
{
    Color color = Color.Black;
    Dictionary<Color, int> histogram = new Dictionary<Color, int>();
    using (Bitmap image = (Bitmap)Bitmap.FromFile(imageFileName))
    {
        // Loop through part of the image the get the colors:
        int width = 100;
        int height = 100;

        for (int w = 0; w < width; w++)
        {
            for (int h = 0; h < height; h++)
            {

                color = image.GetPixel(w, h);
                if (histogram.ContainsKey(color))
                {
                    histogram[color] = histogram[color] + 1;
                }
                else
                {
                    histogram.Add(color, 1);
                }
            }
        }    
    }

    // Get color with highest count:
    int maxValue = 0;
    foreach (KeyValuePair<Color, int> item in histogram)
    {
        if (item.Value > maxValue)
        {
            maxValue = item.Value;
            color = item.Key;
        }
    }
    return color;
}

Ik controleer alleen het eerste deel van het plaatje en dat gaat inderdaad best snel.

Mijn vraag kwam meer uit het feit dat er wordt gezegd dat je LockBits moet gebruiken als je alle pixels bij langs wilt.
Op zich werkt GetPixel zo ook goed genoeg. Ik zal het ook nog even testen met een groter zoekgebied.

Mochten er nog optimalisaties zijn, dan hoor ik dat graag.

[matthijsln]

Verwijderd schreef op dinsdag 25 mei 2010 @ 16:11:
[...]
Maar als als je gegarandeerd een pallet van 255 waarden hebt moet elk pixel toch precies 1 byte zijn?

Hoeft niet perse, je hebt ook plaatjes met palette met 1, 2 of 4 bits per pixel

[pedorus]

Ideetje, zonder unsafe code, maar met een trucje via bmp (gaat uit van Bitmap op PixelFormat.Format32bppArgb):

C#:

            var bitmap = new Bitmap(200, 100);
            Graphics.FromImage(bitmap).FillRectangle(Brushes.Green, 0, 0, 199, 100);
            var counts = new Dictionary<int, int>();
            using (var ms = new MemoryStream())
            {
                bitmap.Save(ms, ImageFormat.Bmp);
                var size = bitmap.Width * bitmap.Height;
                ms.Position = ms.Length - size * 4;
                using (var br = new BinaryReader(ms))
                    for (int i = 0; i < size; i++)
                    {
                        var key = br.ReadInt32();
                        int elem = 0;
                        counts.TryGetValue(key, out elem);
                        counts[key] = elem + 1;
                    }
            }
            var most = 0;
            var mostUsed = Color.Black;
            foreach (var count in counts)
                if (count.Value > most)
                {
                    most = count.Value;
                    mostUsed = Color.FromArgb(count.Key);
                }

[Feanathiel]

NickThissen schreef op dinsdag 25 mei 2010 @ 15:08:
Je zou misschien een iets minder nauwkeurige analyze kunnen uitvoeren. Bijvoorbeeld de kleuren middelen (het plaatje als het ware 'blurren') en daarna een op de 10 pixels of iets dergelijks uitlezen. Dat blurren zal natuurlijk ook weer tijd kosten, dus je zult wat moeten experimenteren om te kijken of je het wel sneller kan krijgen of dat het alleen maar langzamer wordt.

Verwijderd schreef op dinsdag 25 mei 2010 @ 16:20:
Mochten er nog optimalisaties zijn, dan hoor ik dat graag.

Als het dan toch niet zo precies komt... Is het niet mogelijk om de afbeelding een factor-x kleiner te maken? Het voordeel is dat het helemaal in c(++) berekend word door de gdi library en nog een bijkomend voordeel is dat je maar de helft (of nog minder zelfs) hoeft te berekenen in C#.

/Edit: plus dat het alsnog wat geblurd word wanneer er geresized word met een factor dat niet precies kan uit worden gedrukt in precieze pixels. (3/2 = 1.5 -> blur)

[ Voor 8% gewijzigd door Feanathiel op 25-05-2010 18:21 . Reden: Zie edit ]

[Zeebonk]

Een simpele optimalisatie is het schrappen van het gebruik van een Dictionairy en deze te vervangen voor een 3-dimensionale array. Bij een plaatje van 2960x1050 ging ik van 4499ms met een Dictionairy naar 3676ms met een array.

Code wordt dan als volgt:

C#:

      Color c;

      int[, ,] bins = new int[256, 256, 256];
      for (int x = 0; x < bitmap.Width; x++)
        for (int y = 0; y < bitmap.Height; y++)
        {
          c = bitmap.GetPixel(x,y);
          bins[c.R, c.G, c.B]++;
        }

      int maxValue = 0;
      Color maxColor;

      for (int r = 0; r < 256; r++)
        for (int g = 0; g < 256; g++)
          for (int b = 0; b < 256; b++)
            if (bins[r, g, b] > maxValue)
            {
              maxValue = bins[r, g, b];
              maxColor = Color.FromArgb(r, g, b);
            }

      return maxColor;

[Verwijderd]

Bedankt, ik ga de array zeker proberen.

[Zeebonk]

Ik was nog niet helemaal bevredigd met het behaalde resultaat en ben even verder gaan zoeken. Ik kwam uit op het gebruik maken van een BitmapData object. Ik doe nu het zelfde plaatje in ongeveer 500ms!

Dan word het ongeveer:

C#:

      Rectangle rect = new Rectangle(0, 0, bitmap.Width, bitmap.Height);

      // Get bitmap data 
      BitmapData bmpData = bitmap.LockBits(rect, ImageLockMode.ReadOnly, 
                                                          bitmap.PixelFormat);

      // Get the address of the first line.
      IntPtr ptr = bmpData.Scan0;

      // Declare an array to hold the bytes of the bitmap.
      int bytes = bmpData.Stride * bitmap.Height;
      byte[] rgbValues = new byte[bytes];

      // Copy the RGB values into the array.
      Marshal.Copy(ptr, rgbValues, 0, bytes);

      // Unlock the bits.
      bitmap.UnlockBits(bmpData);

      // Count all colors
      int[, ,] bins = new int[256, 256, 256];
      for (int i = 0; i < rgbValues.Length; i += 3)
        bins[rgbValues[i + 2], rgbValues[i + 1], rgbValues[i]]++; //BGR --> RGB

Let hierbij op dat de rgb waardes in een andere volgorde in de byte array staan: BRG.

Uitstel gedrag... moet eigenlijk tentamens leren

[ Voor 4% gewijzigd door Zeebonk op 26-05-2010 18:10 ]

[pedorus]

Zeebonk schreef op woensdag 26 mei 2010 @ 14:37:
Bij een plaatje van 2960x1050 ging ik van 4499ms met een Dictionairy naar 3676ms met een array.

Het idee van de array is goed. Deze getallen lijken me enkel erg traag. Test je wel buiten de debugger? Vergelijk het eens met:

C#:

            int[] bins = new int[0x1000000];
            byte[] bytes;
            using (var ms = new MemoryStream())
            {
                bitmap.Save(ms, ImageFormat.Bmp);
                bytes = ms.ToArray();
            }
            int start = bytes.Length - bitmap.Width * bitmap.Height * 4;
            for (int i = start; i < bytes.Length - 3; i += 4)
                bins[(bytes[i + 2] << 16) + (bytes[i + 1] << 8) + bytes[i]]++;
            int mostFrequent = 0;
            int most = 0;
            for (int i = 0; i < bins.Length; i++)
                if (bins[i] > most)
                {
                    most = bins[i];
                    mostFrequent = i;
                }
            var mostFrequentColor = Color.FromArgb(-0x1000000 | mostFrequent);

<200 ms bij 2960x1050 Dit is met PixelFormat.Format32bppArgb, maar het is vrij eenvoudig om te schrijven naar een ander formaat.

Zeebonk schreef op woensdag 26 mei 2010 @ 17:59:
Ik kwam uit op het gebruik maken van een BitmapData object. Ik doe nu het zelfde plaatje in ongeveer 500ms!

Nog steeds lang.. LockBits mocht niet (zie TS), maar in dat geval kun je beter met pointers werken dan met Marshal, dan gaat het vast een stuk sneller.

[Zeebonk]

pedorus schreef op woensdag 26 mei 2010 @ 18:24:
[...]

Het idee van de array is goed. Deze getallen lijken me enkel erg traag. Test je wel buiten de debugger? Vergelijk het eens met:

C#:

*knip*

<200 ms bij 2960x1050 Dit is met PixelFormat.Format32bppArgb, maar het is vrij eenvoudig om te schrijven naar een ander formaat.

Nee test niet buiten de debugger (denk ik ). Om eerlijk te zijn ook geen idee hoe ik dat zou moeten doen.

[...]

Nog steeds lang.. LockBits mocht niet (zie TS), maar in dat geval kun je beter met pointers werken dan met Marshal, dan gaat het vast een stuk sneller.

Jouw code net gestart gebruikt. Moest nog even de *4 en de += 4 veranderen naar 3, wat volgens mij wel klopt omdat het steeds om drie bytes gaat. Kom dan uit op 370ms. Zal zonder debug mode dan wel in de buurt van jouw 200ms komen

[pedorus]

Zeebonk schreef op woensdag 26 mei 2010 @ 19:39:
Nee test niet buiten de debugger (denk ik ). Om eerlijk te zijn ook geen idee hoe ik dat zou moeten doen.

ctrl-f5 ipv f5? Ik meet overigens met Stopwatch.StartNew().

Jouw code net gestart gebruikt. Moest nog even de *4 en de += 4 veranderen naar 3, wat volgens mij wel klopt omdat het steeds om drie bytes gaat. Kom dan uit op 370ms. Zal zonder debug mode dan wel in de buurt van jouw 200ms komen

En die -3 moet -2 worden. Met Format24bppRgb is het wel zo'n 50% trager (evengoed zul je nog wel <200ms krijgen). Format8bppIndexed is weer veel sneller (in ieder geval <50ms)..

[Zeebonk]

Goed, kom ik nu op rond de 250ms uit. Ik bedacht me dat het plaatje waar ik mee werkte nog een png afbeelding was. Deze eerst maar eens omgezet naar een 24bits rgb bmptje. Dat scheelde al een hoop

Testen met ctrl+f5 maakte nagenoeg geen verschil. Het gebruiken van een stopwatch hielp wel een beetje in vergelijking met datetimes.

De rest van het verschil zal wel in de gebruikte hardware zitten...

[ Voor 0% gewijzigd door Zeebonk op 26-05-2010 21:57 . Reden: typo ]

[Korben]

Zeebonk schreef op woensdag 26 mei 2010 @ 17:59:
Ik was nog niet helemaal bevredigd met het behaalde resultaat en ben even verder gaan zoeken. Ik kwam uit op het gebruik maken van een BitmapData object. Ik doe nu het zelfde plaatje in ongeveer 500ms!

Dan word het ongeveer:
*snip*

Let hierbij op dat de rgb waardes in een andere volgorde in de byte array staan: BRG.

Uitstel gedrag... moet eigenlijk tentamens leren

Mooie code, maar niet correct; jij gaat er van uit dat alle bytes in de array daadwerkelijk kleuren zijn, maar dat zijn ze niet. De BitmapData die je terugkrijgt van LockBits bevat een property Stride, en dat is het aantal bytes per rij in de afbeelding; dit kan meer zijn dan Width * 3. Correcter:

C#:

for (int y = 0; y < bitmap.Height; y++)
{
    int offset = y * (lockData.Stride);

    for (int x = 0; x < bitmap.Width; x++)
    {
        byte r = bytes[offset + x * 3 + 2];
        byte g = bytes[offset + x * 3 + 1];
        byte b = bytes[offset + x * 3];

        reds[r]++;
        greens[g]++;
        blues[b]++;
    }
}

[D-Raven]

Overigens is dit een probleem wat prima te parralleliseren (sp?) is. Wellicht dat je daar nog wat kan winnen. Ik denk zelf dan aan de nieuwe Parrallel extensions in .Net 4.0, die maken het iig een stuk makkelijk om zoiets te realiseren.

[pedorus]

Korben schreef op donderdag 27 mei 2010 @ 10:07:
[...]

Mooie code, maar niet correct; jij gaat er van uit dat alle bytes in de array daadwerkelijk kleuren zijn, maar dat zijn ze niet.

Zolang breedte*bytespp % 4==0 geldt dat ook, maar dit is inderdaad iets om rekening mee te houden als je geen 32bpp hebt, ook via bmp.

[Zeebonk]

Korben schreef op donderdag 27 mei 2010 @ 10:07:
Mooie code, maar niet correct; jij gaat er van uit dat alle bytes in de array daadwerkelijk kleuren zijn, maar dat zijn ze niet. De BitmapData die je terugkrijgt van LockBits bevat een property Stride, en dat is het aantal bytes per rij in de afbeelding; dit kan meer zijn dan Width * 3. Correcter:
*knip*

Moet toegeven dat ik mij weinig had verdiept in het formaat van een bmp. Ik ga er van uit dat het tellen van de kleuren alleen maar even als voorbeeld is? Want op deze manier kan je natuurlijk niet achterhalen welke kleur(encombinatie) het meest voorkomt.

[Korben]

Zeebonk schreef op donderdag 27 mei 2010 @ 11:25:
[...]


Moet toegeven dat ik mij weinig had verdiept in het formaat van een bmp. Ik ga er van uit dat het tellen van de kleuren alleen maar even als voorbeeld is? Want op deze manier kan je natuurlijk niet achterhalen welke kleur(encombinatie) het meest voorkomt.

Jij wil een histogram; mijn voorbeeld is afaik hoe je een histogram berekent: het tellen van zwartwit-tinten uit een van de kanalen van een afbeelding (rood, blauw, groen of zwart-wit).

[.oisyn]

Punt is alleen dat de TS geen histogram wilt, maar gewoon wilt weten welke kleur het meest voorkomt. Daarnaast is jouw definitie van een histogram een veel specifiekere dan de daadwerkelijke definitie van een histogram, wat gewoon een staafdiagram van een frequentieanalyse is. Of je dat voor de R, G en B kanalen apart doet of specifieke kleuren gaat tellen, het heet allebei een histogram. Leesvoer.

Voor histogrammen in imaging wil je meestal iets met luminance of hue, een aparte histogram voor de R, G en B kanalen is doorgaans niet bijzonder nuttig.

[ Voor 80% gewijzigd door .oisyn op 27-05-2010 14:29 ]