Как я могу сделать цветную или числовую замену с битовой / логической логикой - PullRequest
1 голос
/ 29 ноября 2011

Как я могу сделать замену цвета, как показано ниже, без использования оператора if, и вместо этого использовать булеву алгебру (или какую-то другую магию, которая не вводит условную логику)

Проблема (извините за код):

private Image ReplaceRectangleColors(Bitmap b, 
                                     Rectangle rect, 
                                     Color oldColor, 
                                     Color newColor)
    {
        BitmapData bmData = b.LockBits(rect, 
                                       ImageLockMode.ReadWrite,
                                       PixelFormat.Format24bppRgb);
        int stride = bmData.Stride;
        IntPtr Scan0 = bmData.Scan0;

        byte red = 0;
        byte blue = 0;
        byte green = 0;

        unsafe
        {
            byte * p = (byte *)(void *)Scan0;
            int nOffset = stride - rect.Width *3; 

            for(int y=0; y < rect.Height; ++y)
            {
                for(int x=0; x < rect.Width; ++x )
                {
                    red = p[0];
                    blue = p[1];
                    green = p[2];

                    if (red == oldColor.R 
                        && blue == oldColor.B 
                        && green == oldColor.G)
                    {
                        p[0] = newColor.R;
                        p[1] = newColor.B;
                        p[2] = newColor.G;
                    }

                    p += 3;
                }
                p += nOffset;
            }
        }

        b.UnlockBits(bmData);

        return (Image)b;
    }

Проблема, с которой я столкнулся, заключается в том, что если изображение огромно, этот код выполняется много раз и имеет плохую производительность. Я знаю, что должен быть способ заменить замену цвета чем-то более чистым / более быстрым. Есть идеи?

Чтобы подвести итог и упростить, я хочу включить
если (красный == oldColor.R && blue == oldColor.B && green == oldColor.G) { красный = newColor.R; синий = newColor.B; зеленый = новый цвет.G; }

в битовую операцию, в которой нет оператора if.

Ответы [ 2 ]

2 голосов
/ 29 ноября 2011

Нет побитовых операций, которые заменили бы пиксели одного цвета другим. На самом деле, чтение пикселя, применение побитовой операции и запись результатов для каждого пикселя , вероятно, будут работать медленнее, чем чтение пикселя, и только выполнять какую-либо работу с ним и записывать его обратно, если он соответствует вашей цели цвет.

Однако есть несколько вещей, которые можно сделать для ускорения кода с повышением уровня сложности:

1) Первое, что вы можете сделать, это не читать 3 байта перед сравнением. Если вы читаете каждый байт только так, как это необходимо для сравнения, то в случае, если красный байт не совпадает, нет необходимости читать или сравнивать зеленые / синие байты. (Оптимизатор может решить эту проблему от вашего имени)

2) Используйте когерентность кэша, получая доступ к данным в том порядке, в котором они хранятся. (Вы делаете это, работая на линиях сканирования, помещая x во внутренний цикл).

3) Использовать многопоточность. Разбейте изображение на (например) 4 полосы и обработайте их параллельно, и вы сможете ускорить процесс «в несколько раз», если у вас есть 4+ ядерный процессор.

4) Возможно, вы сможете работать в несколько раз быстрее, используя 32-разрядное или 64-разрядное значение вместо четырех или восьми 8-разрядных значений. Это связано с тем, что для извлечения одного байта из памяти может потребоваться такое же время (дать или взять некоторую когерентность кэша и т. Д.) Для извлечения всего регистра ЦП (4 или 8 байтов). Получив значение в регистре, вы можете выполнить одно сравнение (RGBA) вместо четырех (R, G, B, A байт отдельно), а затем выполнить однократную обратную запись - потенциально в 4 раза быстрее. Это простой случай (для 32-битных изображений), поскольку они удобно помещаются по одному пикселю на целое, поэтому вы можете использовать 32-битное целое число для чтения / сравнения / записи всего пикселя RGBA за одну операцию.

Но для других глубин изображения вам будет гораздо сложнее, так как число байтов в каждом пикселе не будет точно соответствовать размеру вашего 32-битного целого. Например, для изображений с 24 битами на дюйм вам необходимо прочитать три 32-битных слова (12 байт), чтобы затем обрабатывать четыре пикселя (3 байта x 4 = 12) на каждой итерации цикла. Вам нужно будет использовать побитовые операции, чтобы отделить эти 3 целых и сравнить их со своим «старым цветом» (см. Ниже). Дополнительным осложнением является то, что вы должны быть осторожны, чтобы не пропустить конец каждой строки развертки, если вы обрабатываете его в 4-х пиксельных переходах. Аналогичный процесс применяется к использованию 64-битных длинных или обработке изображений с более низким bpp - но вам придется начать выполнять более сложные побитовые операции, чтобы аккуратно извлекать данные, и это может быть довольно сложным.

Так как вы сравниваете пиксели?

Первый пиксель прост.

int oldColour = 0x00112233;    // e.g. R=33, G=22, B=11
int newColour = 0x00445566;

int chunk1 = scanline[i];      // Treating scanline as an array of int, read 3 ints (12 bytes)
int chunk2 = scanline[i+1];    // We cache them in ints as we will read/write several times
int chunk3 = scanline[i+2];

if (chunk1 & 0x00ffffff == oldColour)              // read and check 3 bytes of pixel
    chunk2 = (chunk2 & 0xff000000) | newColour;    // Write back 3 bytes of pixel

Следующий пиксель имеет один байт в первом int и 2 байта в следующем int:

if ((chunk1 >> 24) == (oldColour & 0xff))    // Does B byte match?
{
    if ((chunk2 & 0x0000ffff) == (oldColour >> 8))
    {
        chunk1 = (chunk1 & 0x00ffffff) | (newColour & 0xff);   // Replace B byte in chunk1
        chunk2 = (chunk2 & 0xffff0000) | (newColour >> 8);     // Replace G, B bytes in chunk2
    }
}

Тогда третий пиксель имеет 2 байта (RG) в chunk2 и 1 байт (B) в chunk3:

if ((chunk2 >> 16) == (oldColour & 0xffff))
{
    if ((chunk3 & 0xff) == (oldColour >> 16))
    {
        chunk2 = (chunk2 & 0x0000ffff) | (newColour << 16);  // Replace RG bytes in chunk2
        chunk3 = (chunk3 & 0xffffff00) | (newColour >> 16);  // Replace B byte in chunk3
    }
}

И, наконец, последние 3 байта в чанке 3 - это последний пиксель

if ((chunk3 >> 8) == oldCOlour)
    chunk3 = (chunk3 & 0x000000ff) | (newColour << 8);

... и затем запишите чанки в буфер строки сканирования.

В этом вся суть (и мое маскирование / комбинирование выше может иметь некоторые ошибки, так как я быстро написал пример кода и, возможно, перепутал некоторые пиксели!).

Конечно, как только он заработает, вы сможете оптимизировать его загрузку - например, когда я сравниваю материал с частями старого цвета (например, oldColour >> 16), я могу предварительно рассчитать эту константу вне всего цикла обработки, просто используйте переменную oldColourShiftedRight16, чтобы избежать ее пересчета при каждом проходе цикла. То же самое касается всех битов newColour, которые используются. Потенциально вы можете добиться некоторой выгоды, избегая записи значений, которые также не были затронуты, так как многие ваши пиксели, вероятно, не будут соответствовать тому, который вы хотите изменить.

Так что это должно дать вам некоторое представление о том, что вы просили. Это не особенно просто, но это очень весело: -)

Когда вы все это напишете и будете супероптимизированы, последним шагом будет выбросить это и просто использовать вашу видеокарту, чтобы сделать все это в несколько миллиардов раз быстрее в оборудовании - но давайте посмотрим правде в глаза, где весело в этом? : -)

0 голосов
/ 29 ноября 2011

Недавно я написал проект, в котором я делал манипуляции с цветом по пикселям на пиксель. Он должен был работать быстро, так как он будет обновляться, пока вы перемещаете курсор мыши.

Я начал с небезопасного кода, но мне не нравится небезопасный код, и поэтому я перешел на безопасную территорию, и когда я это сделал, у меня возникли проблемы со скоростью, но разрешение не меняло условную логику. Он разрабатывал лучшие алгоритмы для манипулирования пикселями.

Я дам вам обзор того, что я сделал, и я надеюсь, что он поможет вам стать тем, кем вы хотите быть, потому что это действительно близко.

Первое: у меня было несколько возможных форматов ввода пикселей. Из-за этого я не мог предположить, что байты RGB были в определенных смещениях или даже статической ширине. Таким образом, я читаю информацию из переданного изображения и возвращаю «цвет», который представляет размеры каждого поля:

    private System.Drawing.Color GetOffsets(System.Drawing.Imaging.PixelFormat PixelFormat)
    {
        //Alpha contains bytes per color,
        // R contains R offset in bytes
        // G contains G offset in bytes
        // B contains B offset in bytes
        switch(PixelFormat)
        {
            case System.Drawing.Imaging.PixelFormat.Format24bppRgb:
                return System.Drawing.Color.FromArgb(3, 0, 1, 2);
            case System.Drawing.Imaging.PixelFormat.Format32bppArgb:
            case System.Drawing.Imaging.PixelFormat.Format32bppPArgb:
                return System.Drawing.Color.FromArgb(4, 1, 2, 3);
            case System.Drawing.Imaging.PixelFormat.Format32bppRgb:
                return System.Drawing.Color.FromArgb(4, 0, 1, 2);
            case System.Drawing.Imaging.PixelFormat.Format8bppIndexed:
                return System.Drawing.Color.White;
            default:
                return System.Drawing.Color.White;
        }
    }

Например, предположим, что источником является 24-битное RGB-изображение. Я не хотел менять альфа-значения, так как собираюсь смешать с ним цвет.

Таким образом, R со смещением 0, B со смещением 1 и G со смещением 2, и каждый пиксель имеет ширину в три бита. Это я создаю временный цвет с этими данными.

Далее, поскольку это пользовательский элемент управления, я не хотел мерцания, поэтому я переопределил OnPaintBackground и отключил его:

    protected override void OnPaintBackground(System.Windows.Forms.PaintEventArgs pevent)
    {
        //base.OnPaintBackground(pevent);
    }

Наконец, и вот часть, которая доходит до сути того, что вы делаете, я рисую новое изображение на каждом OnPaint (которое вызывается при перемещении мыши, потому что я «аннулирую» его в обработчике события перемещения мыши)

Полный код - прежде чем я вызову определенные разделы ...

    protected override void OnPaint(System.Windows.Forms.PaintEventArgs pe)
    {
        base.OnPaint(pe);
        pe.Graphics.FillRectangle(new System.Drawing.SolidBrush(this.BackColor), pe.ClipRectangle);
        System.Drawing.Rectangle DestinationRect = GetDestinationRectangle(pe.ClipRectangle);
        if(DestinationRect != System.Drawing.Rectangle.Empty)
        {
            System.Drawing.Image BlendedImage = (System.Drawing.Image) this.Image.Clone();
            if(HighlightRegion != System.Drawing.Rectangle.Empty && this.Image != null)
            {
                System.Drawing.Rectangle OffsetHighlightRegion = 
                    new System.Drawing.Rectangle(
                        new System.Drawing.Point(
                            Math.Min(Math.Max(HighlightRegion.X + OffsetX, 0), BlendedImage.Width - HighlightRegion.Width -1), 
                            Math.Min(Math.Max(HighlightRegion.Y + OffsetY, 0), BlendedImage.Height - HighlightRegion.Height -1)
                            )
                            , HighlightRegion.Size
                            );
                System.Drawing.Bitmap BlendedBitmap = (System.Drawing.Bitmap) BlendedImage;
                System.Drawing.Color OffsetRGB = GetOffsets(BlendedImage.PixelFormat);
                byte BlendR = SelectionColor.R;
                byte BlendG = SelectionColor.G;
                byte BlendB = SelectionColor.B;
                byte BlendBorderR = SelectionBorderColor.R;
                byte BlendBorderG = SelectionBorderColor.G;
                byte BlendBorderB = SelectionBorderColor.B;
                if(OffsetRGB != System.Drawing.Color.White) //White means not supported
                {
                    int BitWidth = OffsetRGB.G - OffsetRGB.R;
                    System.Drawing.Imaging.BitmapData BlendedData = BlendedBitmap.LockBits(new System.Drawing.Rectangle(0, 0, BlendedBitmap.Width, BlendedBitmap.Height), System.Drawing.Imaging.ImageLockMode.ReadWrite, BlendedBitmap.PixelFormat);
                    int StrideWidth = BlendedData.Stride;
                    int BytesPerColor = OffsetRGB.A;
                    int ROffset = BytesPerColor - (OffsetRGB.R + 1);
                    int GOffset = BytesPerColor - (OffsetRGB.G + 1);
                    int BOffset = BytesPerColor - (OffsetRGB.B + 1);
                    byte[] BlendedBytes = new byte[Math.Abs(StrideWidth) * BlendedData.Height];
                    System.Runtime.InteropServices.Marshal.Copy(BlendedData.Scan0, BlendedBytes, 0, BlendedBytes.Length);

                    //Create Highlighted Region
                    for(int Row = OffsetHighlightRegion.Top ; Row <= OffsetHighlightRegion.Bottom ; Row++)
                    {
                        for(int Column = OffsetHighlightRegion.Left ; Column <= OffsetHighlightRegion.Right ; Column++)
                        {
                            int Offset = Row * StrideWidth + Column * BytesPerColor;
                            if(Row == OffsetHighlightRegion.Top || Row == OffsetHighlightRegion.Bottom || Column == OffsetHighlightRegion.Left || Column == OffsetHighlightRegion.Right)
                            {
                                BlendedBytes[Offset + ROffset] = BlendBorderR;
                                BlendedBytes[Offset + GOffset] = BlendBorderG;
                                BlendedBytes[Offset + BOffset] = BlendBorderB;
                            }
                            else
                            {
                                BlendedBytes[Offset + ROffset] = (byte) ((BlendedBytes[Offset + ROffset] + BlendR) >> 1);
                                BlendedBytes[Offset + GOffset] = (byte) ((BlendedBytes[Offset + GOffset] + BlendG) >> 1);
                                BlendedBytes[Offset + BOffset] = (byte) ((BlendedBytes[Offset + BOffset] + BlendB) >> 1);
                            }
                        }
                    }
                    System.Runtime.InteropServices.Marshal.Copy(BlendedBytes, 0, BlendedData.Scan0, BlendedBytes.Length);
                    BlendedBitmap.UnlockBits(BlendedData);

                    //base.Image = (System.Drawing.Image) BlendedBitmap;
                }
            }
            pe.Graphics.DrawImage(BlendedImage, 0, 0, DestinationRect, System.Drawing.GraphicsUnit.Pixel);
        }
    }

Ниже приведено несколько объяснений кода ...

System.Drawing.Image BlendedImage = (System.Drawing.Image) this.Image.Clone();

Важно рисовать закадровое изображение - это создает одно такое изображение. В противном случае рисунок будет намного медленнее.

if(HighlightRegion != System.Drawing.Rectangle.Empty && this.Image != null)

HighlightRegion - это RECT, который удерживает область, которую нужно «пометить» на исходном изображении. Я использовал это для разметки областей изображения размером 4 миллиона пикселей, и он все еще работает достаточно быстро, чтобы быть в «реальном времени»

Некоторый код ниже используется, потому что пользователь может прокручивать изображение вверх или вниз, поэтому я изменяю пункт назначения по количеству прокрутки.

Ниже я приведу ИЗОБРАЖЕНИЕ к BITMAP и получу ранее упомянутую информацию о Цвете, которую мне нужно будет начать использовать сейчас. В зависимости от того, что вы делаете, вы можете захотеть кэшировать это вместо того, чтобы получать его каждый раз.

System.Drawing.Bitmap BlendedBitmap = (System.Drawing.Bitmap) BlendedImage;

На моем элементе управления я выставил два свойства Color - SelectionColor и SelectionBorderColor - так, чтобы мои регионы все еще имели приятную границу с ними. Часть моей оптимизации скорости состояла в том, чтобы предварительно преобразовать их в байты, так как я буду делать побитовые операции через мгновение.

Вы увидите комментарий в коде «Белый не поддерживается» - в этом случае «Белый» - это «Поддельный цвет», который мы используем для хранения нашей битовой ширины. Я использовал «Белый» для обозначения «Я не могу оперировать этими данными»

Следующая строка устанавливает, что на самом деле каждый цвет является одним битом, потому что они могут не зависеть от нашего целевого формата цвета путем вычитания смещения R и G. Обратите внимание, что если вы не можете гарантировать, что ваш G следует вашему R, вам нужно будет использовать что-то еще. В моем случае это было гарантировано.

Теперь, где начинается та часть, которую вы действительно ищете. Я использую LockBits для получения битовых данных. После этого я использую данные, чтобы завершить настройку некоторых переменных перед циклом.

А потом я копирую данные в байтовый массив. Я собираюсь перебрать этот байтовый массив, изменить значения и затем скопировать его данные обратно в BITMAP. Я работал над BITMAP непосредственно перед тем, как подумать, что, поскольку он вне экрана, он будет таким же быстрым, как и работа с собственным массивом.

Я был не прав. Профилирование производительности доказало это мне. Это быстрее, чтобы скопировать все в байтовый массив и работать в этом.

Теперь цикл начинается. Это идет строка за строкой, столбец за столбцом. Смещение - это число, указывающее нам, где в байтовом массиве мы находимся с точки зрения «текущего пикселя».

Затем я смешиваю 50% или рисую границу. Обратите внимание, что для каждого пикселя у меня есть не только оператор IF, но и ИЛИ.

И все так же быстро, как пылает.

Наконец, я копирую обратно и разблокирую биты. А затем скопируйте изображение на экранную поверхность.

...