morzel.net

.net, js, html, arduino, java... no rants or clickbaits.

Szybkie operacje pikselowe w .NET (z i bez unsafe)

Klasa Bitmap posiada metody GetPixel i SetPixel, które pozwalają na pobranie i zmianę koloru piksela. Metody te są bardzo proste w użyciu, niestety są też niezwykle powolne. Mój poprzedni post szczegółowo opisuje ten temat, kliknij tutaj jeśli chcesz wiedzieć więcej.

Na szczęście nie trzeba używać zewnętrznych bibliotek (lub całkowicie rezygnować z .NET) by efektywnie przetwarzać obraz. Framework ma wbudowaną klasę ColorMatrix pozwalającą na wykonanie zmian na mapie bitowej w krótkim czasie. Właściwości takie jak kontrast lub nasycenie mogą być modyfikowane w ten sposób. Co jednak z manipulowaniem pojedynczymi pikselami? Da się to zrobić za pomocą metody Bitmap.LockBits i klasy BitmapData

Dobrym testem szybkości operacji pikselowych jest badanie różnicy kolorów. Zadanie polega na znalezieniu fragmentów obrazu, które mają kolor podobny do zadanego koloru. Jak sprawdzić czy kolory są podobne? Pomyśl o kolorze jako punkcie w trójwymiarowej przestrzeni, gdzie osiami są: czerwony, zielony i niebieski. Dwa kolory to dwa punkty. Różnica między kolorami jest więc opisana przez dystans dzielący te dwa punkty w przestrzeni RGB.

Kolory jako punkty w przestrzeni 3D

diff = sqrt((C1R-C2R)2+(C1G-C2G)2+(C1B-C2B)2)

Ta technika jest bardzo prosta w realizacji i daje przyzwoite rezultaty. Porównywanie kolorów jest jednak zagadnieniem bardzo złożonym. Inne przestrzenie koloru niż RGB nadają się lepiej do tego zadania. Pod uwagę należy również brać sposób percepcji koloru przez człowieka (np. nasze oczy są bardziej wyczulone na różnice w odcieniach zieleni niż koloru niebieskiego). Trzymajmy się jednak prostego rozwiązania…

Naszym testowym obrazem będzie to zdjęcie* Ultra HD 8K: 7680x4320, 33.1Mpx (na potrzeby bloga je oczywiście zmniejszyłem by nie marnować transferu):

Obraz wejściowy dla badania różnicy koloru (zmniejszony dla bloga)

Oto metoda, która może np. wyszukać piksele R=253 G=129 B=84 (inaczej „różowy stanik”) i ustawić je na kolor biały (reszta stanie się czarna):

static void DetectColorWithGetSetPixel(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    int toleranceSquared = tolerance * tolerance;

    for (int x = 0; x < image.Width; x++)
    {
        for (int y = 0; y < image.Height; y++)
        {
            Color pixel = image.GetPixel(x, y);

            int diffR = pixel.R - searchedR;
            int diffG = pixel.G - searchedG;
            int diffB = pixel.B - searchedB;

            int distance = diffR * diffR + diffG * diffG + diffB * diffB;

            image.SetPixel(x, y, distance > toleranceSquared ? Color.Black : Color.White);
        }
    }
}

Powyższy kod to nasza okropnie wolna baza porównawcza Get/SetPixel. Przy wywołaniu w taki sposób (parametry nazwana dla czytelności):

DetectColorWithGetSetPixel(image, searchedR: 253, searchedG: 129, searchedB: 255, tolerance: 84);

otrzymamy taki oto wynik:

Obraz wyjściowy dla badania różnicy koloru (zmniejszony dla bloga)

Rezultat jest całkiem ok ale czekanie na niego ponad 84300ms* to całkowita porażka.

Teraz rzuć okiem na tą metodę:

static unsafe void DetectColorWithUnsafe(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
    int bytesPerPixel = 3;

    byte* scan0 = (byte*)imageData.Scan0.ToPointer();
    int stride = imageData.Stride;

    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    for (int y = 0; y < imageData.Height; y++)
    {
        byte* row = scan0 + (y * stride);

        for (int x = 0; x < imageData.Width; x++)
        {
            // Uwaga na rzeczywistą kolejność (BGR)!
            int bIndex = x * bytesPerPixel;
            int gIndex = bIndex + 1;
            int rIndex = bIndex + 2;

            byte pixelR = row[rIndex];
            byte pixelG = row[gIndex];
            byte pixelB = row[bIndex];

            int diffR = pixelR - searchedR;
            int diffG = pixelG - searchedG;
            int diffB = pixelB - searchedB;

            int distance = diffR * diffR + diffG * diffG + diffB * diffB;

            row[rIndex] = row[bIndex] = row[gIndex] = distance > toleranceSquared ? unmatchingValue : matchingValue;
        }
    }

    image.UnlockBits(imageData);
}

Robi dokładnie to samo ale wykonuje się tylko 230ms ponad 360 razy szybciej!

Kod ten używa metody Bitmap.LockBits, która jest oprawką na natywną funkcję GdipBitmapLockBits (GDI+, gdiplus.dll). LockBits tworzy tymczasowy bufor przechowujący informacje o pikselach w żądanym formacie (w naszym przypadku RGB, po 8 bitów na składową koloru). Wszelkie zmiany w tym buforze są kopiowane do bitmapy przy wywołaniu UnlockBits (dlatego zawsze należy używać LockBits i UnlockBits jako pary). Bitmap.LockBits zwraca obiekt BitmapData (namespace System.Drawing.Imaging), który posiada dwie interesujące właściwości: Scan0 i Stride. Scan0 zwraca adres danych pierwszego piksela. Stride to szerokość jednego rzędu pikseli (tzw. scan line) w bajtach (z opcjonalnym wypełnieniem tak by wartość była podzielna przez 4). 

Układ BitmapData

Zauważ, że nie używam odwołań do Math.Pow i Math.Sqrt by obliczyć dystans między kolorami. Pisanie takiego kodu:

double distance = Math.Sqrt(Math.Pow(pixelR - searchedR, 2) + Math.Pow(pixelG - searchedG, 2) + Math.Pow(pixelB - searchedB, 2));

do przetwarzania milionów pikseli do straszny pomysł. Taka linia uczyniła by naszą zoptymalizowaną metodę około 25 razy wolniejszą. Używanie Math.Pow z parametrami całkowitymi to czyste marnotrawstwo, nie trzeba też wyliczać pierwiastka kwadratowego by określić czy odległość mieści się w pewnej tolerancji.

Pokazana wcześniej metoda jest oznaczona słowem kluczowym unsafe. Pozwala ono programowi C# na użycie operacji wskaźnikowych. Niestety tryb unsafe ma istotne ograniczenia. Kod, który go używa musi być skompilowany z opcją \unsafe oraz musi być wykonywany w pełni zaufanym assembly.

Na szczęście istnieje metoda Marshal.Copy (z przestrzeni nazw System.Runtime.InteropServices), dzięki której można przenosić dane między zarządzaną a niezarządzana pamięcią. Możemy jej użyć do skopiowania danych obrazu do tablicy bajtów i manipulowania pikselami w bardzo efektywny sposób. Przeanalizuj tą metodę:

static void DetectColorWithMarshal(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{        
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);

    byte[] imageBytes = new byte[Math.Abs(imageData.Stride) * image.Height];
    IntPtr scan0 = imageData.Scan0;

    Marshal.Copy(scan0, imageBytes, 0, imageBytes.Length);
  
    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    for (int i = 0; i < imageBytes.Length; i += 3)
    {
        byte pixelB = imageBytes[i];
        byte pixelR = imageBytes[i + 2];
        byte pixelG = imageBytes[i + 1];

        int diffR = pixelR - searchedR;
        int diffG = pixelG - searchedG;
        int diffB = pixelB - searchedB;

        int distance = diffR * diffR + diffG * diffG + diffB * diffB;

        imageBytes[i] = imageBytes[i + 1] = imageBytes[i + 2] = distance > toleranceSquared ? unmatchingValue : matchingValue;
    }

    Marshal.Copy(imageBytes, 0, scan0, imageBytes.Length);

    image.UnlockBits(imageData);
}

Wykonuje się ona tylko 280ms, jest wiec jedynie odrobinę wolniejsza od wersji unsafe. Pod względem CPU kod jest oszczędny jednak zużywa więcej pamięci niż poprzednia metoda – prawie 100 megabajtów dla naszego testowego obrazu Ultra HD 8K w formacie RGB 24.

Jeśli chcesz uzyskać jeszcze większą prędkość obróbki obrazu możesz przetwarzać różne części obrazu równolegle. Musisz jednak wykonać nieco testów ponieważ dla małych obrazów koszt użycia wielu wątków może okazać się większy niż zysk z wykonywania równoległego. Poniższa metoda to przykład kodu, który używa 4 wątków do jednoczesnego procesowania 4 fragmentów obrazu. Na mojej maszynie daje to ok 30% wzrostu wydajności. Traktuj ten kod jako szybką wskazówkę, ten post jest już i tak zbyt długi…

static unsafe void DetectColorWithUnsafeParallel(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
    int bytesPerPixel = 3;

    byte* scan0 = (byte*)imageData.Scan0.ToPointer();
    int stride = imageData.Stride;

    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    Task[] tasks = new Task[4];
    for (int i = 0; i < tasks.Length; i++)
    {
        int ii = i;
        tasks[i] = Task.Factory.StartNew(() =>
            {
                int minY = ii < 2 ? 0 : imageData.Height / 2;
                int maxY = ii < 2 ? imageData.Height / 2 : imageData.Height;

                int minX = ii % 2 == 0 ? 0 : imageData.Width / 2;
                int maxX = ii % 2 == 0 ? imageData.Width / 2 : imageData.Width;                        
                
                for (int y = minY; y < maxY; y++)
                {
                    byte* row = scan0 + (y * stride);

                    for (int x = minX; x < maxX; x++)
                    {
                        int bIndex = x * bytesPerPixel;
                        int gIndex = bIndex + 1;
                        int rIndex = bIndex + 2;

                        byte pixelR = row[rIndex];
                        byte pixelG = row[gIndex];
                        byte pixelB = row[bIndex];

                        int diffR = pixelR - searchedR;
                        int diffG = pixelG - searchedG;
                        int diffB = pixelB - searchedB;

                        int distance = diffR * diffR + diffG * diffG + diffB * diffB;

                        row[rIndex] = row[bIndex] = row[gIndex] = distance > toleranceSquared ? unmatchingValue : matchingValue;
                    }
                }
            });
    }

    Task.WaitAll(tasks);

    image.UnlockBits(imageData);
}

Oryginalnie miałem jakieś trójkąty i kwadraty jako ilustracje, ale modelki Victoria's Secret (źródło) są lepsze, co? :)

* Aplikacja konsolowa .NET 4 uruchamiana na laptopie MSI GE620 DX: Intel Core i5-2430M 2.40GHz (2 rdzenie, 4 wątki), 4GB DDR3 RAM, NVIDIA GT 555M 2GB DDR3, HDD 500GB 7200RPM, Windows 7 Home Premium x64.

Układ współrzędnych HTML5 Canvas, rysowanie z wartością y rosnącą ku górze ekranu

Układ współrzędnych w HTML 5 Canvas jest ustalony w taki sposób, że za punkt początkowy (0, 0) przyjęty jest lewy-górny róg canvas. To rozwiązanie nie jest niczym niezwykłym w świecie grafiki ekranowej (tak samo jest np. w Windows Forms czy SVG). Popularne kiedyś monitory CRT wyświetlały linie obrazu w kolejności od góry do dołu a obraz w linii tworzony był od lewej do prawej. Umieszczenie punktu (0,0) w lewym-górnym rogu było więc intuicyjne i ułatwiało budowanie sprzętu i oprogramowania do obsługi grafiki… 

Niestety czasem domyślny układ współrzędnych na canvas jest mało praktyczny. Przyjmijmy, że chcesz wykonać animację lotu pocisku. Naturalnie wydaje się, że dla wznoszącego się pocisku wartość współrzędnej y powinna rosnąć. Da to jednak dziwaczny efekt odwróconej trajektorii:

Domyślny układ współrzędnych (y rośnie ku dołowi ekranu)

Można temu zaradzić poprzez modyfikację wartości y przekazywanej do funkcji rysującej:

context.fillRect(x, offsetY - y, size, size);

Dla y = 0, pocisk zostanie umieszczony w miejscu wyznaczonym przez offsetY (by y = 0 oznaczało sam spód canvas ustaw offset na wartość równą wysokości canvas). Im większa będzie wartość y tym wyżej pocisk zostanie narysowany. Problem w tym, że możesz mieć w kodzie setki miejsc, w których wykorzystywana będzie współrzędna y. Wystarczy, że raz zapomnisz uwzględnić offsetY i cały obraz może zostać uszkodzony.

Na szczęście canvas umożliwia wprowadzenie zmian w układzie współrzędnych za pomocą transformacji. Nam przydadzą się dwie metody transformujące: translate(x, y) i scale(x, y). Pierwsza z nich umożliwia przesunięcie początku układu współrzędnych. Druga służy do zmiany wielkości rysowanych obiektów, jednak może też zostać użyta do odwrócenia współrzędnych.

Pojedyncze wykonanie tego kodu sprawi, że początek układu współrzędnych znajdzie się w punkcie (0, offsetY) a wartość y będzie wyższa u góry ekranu:

context.translate(0, offsetY);
context.scale(1, -1);

Przesunięcie i skalowanie układu współrzędnych

Od tej pory możemy wywoływać metody rysujące bez konieczności modyfikacji współrzędnych!

Jest jednak pewien problem: podanie -1 jako wartości drugiego parametru metody scale powoduje, że cały obraz tworzony jest dla odwróconej współrzędnej y. Dotyczy to także tekstu (wywołanie fillText sprawi, że tekst pojawi się „do góry nogami”). Przed wypisaniem tekstu należy więc przywrócić domyślny układ osi y. Ponieważ ręczne przywracanie stanu canvas byłoby bardzo kłopotliwe, istnieją metody save() i restore(), które umożliwiają odpowiednio: odłożenie stanu na stosie i przywrócenie stanu ze stosu. Zaleca się użycie metody save przed dokonaniem transformacji. W stan canvas wchodzą nie tylko użyte transformacje ale też wartości takie jak styl wypełnienia czy grubość linii...

context.save();

context.fillStyle = 'red';
context.scale(2, 2);
context.fillRect(0, 0, 10, 10);

context.restore();

context.fillRect(0, 0, 10, 10);

Powyższy kod sprawi, że zostaną narysowane 2 kwadraty:

Pierwszy z nich ma kolor czerwony i narysowany jest w skali 2x. Drugi jest rysowany w ustawieniach domyślnych canvas (kolor czarny i skala 1x). Dzieje się tak dlatego, że przed zmianami skali i koloru, stan canvas został odłożony na stosie po czym został przywrócony przed narysowaniem drugiego kwadratu.

Dlaczego użycie GetPixel i SetPixel jest tak bardzo nieefektywne?

Klasa Bitmap dostarcza dwie proste metody: GetPixel i SetPixel służące odpowiednio do pobierania koloru punktu obrazu (jako struktury Color) oraz ustawienia punktu obrazu. Poniższy kod ilustruje sposób pobrania/ustawiania wszystkich pikseli bitmapy:

private void GetSetPixel(Bitmap image) {
   for (int x = 0; x < image.Width; x++) {
      for (int y = 0; y < image.Height; y++) {
         Color pixel = image.GetPixel(x, y);
         image.SetPixel(x, y, Color.Black);
      }
   } 
}

Jak widać przeglądnięcie i modyfikacja pikseli jest niezwykle prosta. Niestety za prostotą kodu kryje się poważna pułapka wydajnościowa. O ile dla niewielkiej ilości odwołań do punktów obrazu, prędkość z jaką działają metody GetPixel i SetPixel jest zadowalająca, o tyle dla większych rozmiarów obrazu jest ona zdecydowanie za mała. Za dowód może posłużyć wykres z wynikami 10 testów*, które polegały na 10-krotnym wywołaniu w/w metody GetSetPixel na obrazach 100x100 i 1000x1000 pikseli:

Wyniki testów prędkości operacji na pikselach obrazu z użyciem metod GetPixel i SetPixel klasy Bitmap.

Średni czas testu dla obrazu o wymiarach 100 na 100 pikseli wyniósł 543 milisekundy. Taka wydajność jest możliwa do zaakceptowania o ile przetwarzanie obrazu nie będzie wykonywane często. Problem wydajnościowy jest natomiast jasno widoczny przy próbie obsługi obrazu o rozmiarach 1000 na 1000 pikseli. Wykonanie testu zabiera w tym przypadku średnio ponad 41 sekund – ponad 4 sek. na jedno wywołanie GetSetPixel (sic!) .


Dlaczego tak wolno?

Niska wydajność spowodowana jest tym, że dostęp do piksela nie jest prostym odwołaniem do obszaru pamięci. Każde pobranie lub ustawienie koloru wiąże się z wywołaniem metody .NET Framework, będącej oprawą dla natywnej funkcji zawartej w bibliotece gdiplus.dll. Wywołanie to następuje za pomocą mechanizmu P/Invoke (Platform Invocation), który służy do komunikacji kodu zarządzanego z API niezarządzanym (API z poza .NET Framework). Tak więc np. dla bitmapy o rozmiarze 1000x1000 pikseli dojdzie do miliona wywołań metody GetPixel, która prócz walidacji parametrów korzysta z funkcji natywnej GdipBitmapGetPixel. Metoda z API GDI+ musi z kolei przed zwróceniem informacji o kolorze wykonać takie operację jak np. wyliczenie położenia bajtów odpowiedzialnych za opis szukanego piksela... Sytuacja analogiczna zachodzi w przypadku metody SetPixel.

Spójrz na poniższy kod metody Bitmap.GetPixel uzyskany dzięki .NET Reflector (System.Drawing.dll, .NET Framework 2.0):

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”));
   }
   
   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);
}

A oto import funkcji z GDI+:

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

Teraz już wiesz dlaczego masowe użycie Get/SetPixel jest takie powolne. Na szczęście istnieją inne (dużo szybsze) sposoby obsługi pikseli z poziomu .NET. Przy pewnym wysiłku można napisać kod, który szybciej obsłuży obraz megapikselowy niż prymitywna metoda poradzi sobie z bitmapą 100x100!. Ale o tym, gdy znajdę nieco czasu... ;)

* Testowałem na takim laptopie: HP Pavilion dv5, procesor AMD Turion X2 Dual-Core Mobile RM-70, 3 GB RAM, Vista Home Premium

Badanie różnicy kolorów

W .NET Framework do opisu koloru wykorzystywana jest struktura Color. Jej najważniejsze właściwości to: R, G oraz B. Odpowiadają one za intensywność barw podstawowych (czerwonej, zielonej i niebieskiej).* Właściwości te przyjmują wartości z zakresu od 0 do 255. Trzy bajty użyte do opisu składowych dają możliwość stworzenia ponad 16 milionów barw (2^24 = 16 777 216)!

RGB(0, 0, 0) to kolor czarny, (255, 255, 255) to kolor biały, (255, 0, 0) to czerwony a np. (255, 255, 0) to żółty... Struktura Color posiada również właściowść A (kanał alfa), która jest wykorzystywana w grafice komputerowej do określania stopnia przeźroczystości. Wartość 255 oznacza pełną nieprzeźroczystość.

Do zbadania różnicy między kolorami można posłużyć się odległością euklidesową (dystans między punktami). Wyobraź sobie trójwymiarowy układ współrzędnych, których osie oznaczymy odpowiednio przez R, G oraz B (składową A pomijamy). Gdy umieścisz w takim układzie dwa punkty odpowiadające kolorom i zmierzysz odległość między nimi, otrzymasz informację o stopniu podobieństwa kolorów. Dzięki temu będziesz mógł np. wykryć na obrazie wszystkie miejsca mające odcień zieleni...

Color c1 =  Color.White;
Color c2 = Color.Black;

int odlegloscR = (c1.R - c2.R) * (c1.R - c2.R);
int odlegloscG = (c1.G - c2.G) * (c1.G - c2.G);
int odlegloscB = (c1.B - c2.B) * (c1.B - c2.B);

double roznicaKoloru = Math.Sqrt(odlegloscR + odlegloscG
 + odlegloscB);

W powyższym kodzie celowo nie korzystałem z funkcji Math.Pow. Jej zastosowanie przy takiej operacji jak podnoszenie do potęgi całkowitej to marnotrastwo CPU (gdy trzeba przebadać wiele punktów ma to znaczenie). Jeśli wyliczenie zmiennej roznicaKoloru ma słyżyć jedynie porównywaniu barw można by również zrezygnować z pierwiastkowania...

* Model RGB opisuje zjawisko syntezy addytywnej czyli mieszanie się swiatła emitowanego (np. przez monitor).

L-systemy. Tworzenie form roślinnych z wykorzystaniem System.Drawing.

Artykuł w prosty sposób opisuje ciekawe zganienie algorytmu wzrostu. Czyni to na przykładzie tworzenia realistycznie wyglądających form roślinnych, rysowanych w oparciu o klasy z przestrzeni nazw System.Drawing...

Wersja: 1.1 (06.2007, poprawki 07.2007)
Poziom trudności: średniozaawansowany
Uwagi: Artykuł ten pisałem w ramach nauki .NET Framework jako pracę uczestniczącą w konkursie portalu CodeGuru.pl (tekst zajął pierwsze miejsce w czerwcu 2007 r.).

Artykuł w PDF (v1.1 - 07.2007):
http://morzel.net/download/lsystemy_art.pdf

Artykuł na CodeGuru.pl (v1.0 - 06.2007):
http://www.codeguru.pl/article-703.aspx

Załączony kod (C#, VS 2005):
http://morzel.net/download/lsystemy_src.zip