быстрый порог и алгоритм упаковки битов (возможные улучшения?) - PullRequest
Новая
       23

быстрый порог и алгоритм упаковки битов (возможные улучшения?)

1 голос
/ 14 сентября 2010

Я работаю над алгоритмом, который выполняет глобальное установление порога 8-битного изображения в градациях серого в 1-битное (упакованное битами, такое, что 1 байт содержит 8 пикселей) монохромное изображение. Каждый пиксель в изображении в градациях серого может иметь значение яркости от 0 до 255.

Моя среда - Win32 в Microsoft Visual Studio C ++.

Мне интересно максимально оптимизировать алгоритм из любопытства. 1-битное изображение будет преобразовано в TIFF. В настоящее время я устанавливаю FillOrder как MSB2LSB (от старшего значащего к младшему значащему биту) только потому, что спецификация TIFF предполагает это (необязательно должен быть MSB2LSB)

Просто фон для тех, кто не знает:

MSB2LSB упорядочивает пиксели слева направо в байте так же, как пиксели ориентируются на изображении по мере увеличения координаты X. Если вы пересекаете изображение в градациях серого слева направо по оси X, это, очевидно, требует от вас думать «назад», когда вы упаковываете биты в свой текущий байт. С учетом вышесказанного позвольте мне показать вам, что у меня есть в данный момент (это на C, я еще не пробовал ASM или Compiler Intrinsics только потому, что у меня очень мало опыта с этим, но это было бы возможно).

Поскольку монохромное изображение будет иметь 8 пикселей на байт, ширина монохромного изображения будет 

(grayscaleWidth+7)/8;

К вашему сведению, мое самое большое изображение имеет ширину 6000 пикселей:

Первое, что я делаю (перед обработкой любого изображения), это

1) вычислить справочную таблицу величин, которые мне нужно сдвинуть в определенный байт, учитывая координату X из моего изображения в градациях серого: 

int _shift_lut[6000];

for( int x = 0 ; x < 6000; x++)
{ 
    _shift_lut[x] = 7-(x%8);
}

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

monochrome_pixel |= 1 << _shift_lut[ grayX ];

, что в итоге приводит к огромному увеличению скорости по сравнению с 

monochrome_pixel |= 1 << _shift_lut[ 7-(x%8)];

Вторая таблица поиска, которую я вычисляю, является таблицей подстановок, в которой указывается X-индекс моего монохромного пикселя с учетом X-пикселя на пикселе оттенков серого. Это очень простое LUT рассчитывается так: 

int xOffsetLut[6000];
int element_size=8; //8 bits
for( int x = 0; x < 6000; x++)
{
    xOffsetLut[x]=x/element_size;
}

Этот LUT позволяет мне делать такие вещи, как 

monochrome_image[ xOffsetLut[ GrayX ] ] = packed_byte; //packed byte contains 8 pixels

Моё изображение в градациях серого - это простой символ без знака *, как и мое монохромное изображение;

Вот как я инициализирую монохромное изображение: 

int bitPackedScanlineStride = (grayscaleWidth+7)/8;
int bitpackedLength=bitPackedScanlineStride * grayscaleHeight;
unsigned char * bitpack_image = new unsigned char[bitpackedLength];
memset(bitpack_image,0,bitpackedLength);

Затем я вызываю свою функцию бинаризации следующим образом: 

binarize(
    gray_image.DataPtr(),
    bitpack_image,
    globalFormThreshold,
    grayscaleWidth,
    grayscaleHeight,
    bitPackedScanlineStride,
    bitpackedLength,
    _shift_lut,  
    xOffsetLut);

А вот и моя функция Binarize (как вы можете видеть, я сделал какое-то развертывание цикла, которое может или не может помочь). 

void binarize( unsigned char grayImage[], unsigned char bitPackImage[], int threshold, int grayscaleWidth, int grayscaleHeight, int  bitPackedScanlineStride, int bitpackedLength,  int shiftLUT[], int xOffsetLUT[] )
{
    int yoff;
    int byoff;
    unsigned char bitpackPel=0;
    unsigned char pel1=0;
    unsigned char  pel2=0;
    unsigned char  pel3=0;
    unsigned char  pel4=0;
    unsigned char  pel5=0;
    unsigned char  pel6=0;
    unsigned char  pel7=0;
    unsigned char  pel8=0;
    int checkX=grayscaleWidth;
    int checkY=grayscaleHeight;

    for ( int by = 0 ; by < checkY; by++)
    {
    yoff=by*grayscaleWidth;
    byoff=by*bitPackedScanlineStride;

    for( int bx = 0; bx < checkX; bx+=32)
    {
        bitpackPel = 0;

        //pixel 1 in bitpack image
        pel1=grayImage[yoff+bx];
        pel2=grayImage[yoff+bx+1];
        pel3=grayImage[yoff+bx+2];
        pel4=grayImage[yoff+bx+3];
        pel5=grayImage[yoff+bx+4];
        pel6=grayImage[yoff+bx+5];
        pel7=grayImage[yoff+bx+6];
        pel8=grayImage[yoff+bx+7];

        bitpackPel |= ( (pel1<=threshold) << shiftLUT[bx]);
        bitpackPel |= ( (pel2<=threshold) << shiftLUT[bx+1] );
        bitpackPel |= ( (pel3<=threshold) << shiftLUT[bx+2] );
        bitpackPel |= ( (pel4<=threshold) << shiftLUT[bx+3] );
        bitpackPel |= ( (pel5<=threshold) << shiftLUT[bx+4] );
        bitpackPel |= ( (pel6<=threshold) << shiftLUT[bx+5] );
        bitpackPel |= ( (pel7<=threshold) << shiftLUT[bx+6] );
        bitpackPel |= ( (pel8<=threshold) << shiftLUT[bx+7] );

        bitPackImage[byoff+(xOffsetLUT[bx])] = bitpackPel;

        //pixel 2 in bitpack image
        pel1=grayImage[yoff+bx+8];
        pel2=grayImage[yoff+bx+9];
        pel3=grayImage[yoff+bx+10];
        pel4=grayImage[yoff+bx+11];
        pel5=grayImage[yoff+bx+12];
        pel6=grayImage[yoff+bx+13];
        pel7=grayImage[yoff+bx+14];
        pel8=grayImage[yoff+bx+15];

        bitpackPel = 0;

        bitpackPel |= ( (pel1<=threshold) << shiftLUT[bx+8]  );
        bitpackPel |= ( (pel2<=threshold) << shiftLUT[bx+9]  );
        bitpackPel |= ( (pel3<=threshold) << shiftLUT[bx+10] );
        bitpackPel |= ( (pel4<=threshold) << shiftLUT[bx+11] );
        bitpackPel |= ( (pel5<=threshold) << shiftLUT[bx+12] );
        bitpackPel |= ( (pel6<=threshold) << shiftLUT[bx+13] );
        bitpackPel |= ( (pel7<=threshold) << shiftLUT[bx+14] );
        bitpackPel |= ( (pel8<=threshold) << shiftLUT[bx+15] );

        bitPackImage[byoff+(xOffsetLUT[bx+8])] = bitpackPel;

        //pixel 3 in bitpack image
        pel1=grayImage[yoff+bx+16];
        pel2=grayImage[yoff+bx+17];
        pel3=grayImage[yoff+bx+18];
        pel4=grayImage[yoff+bx+19];
        pel5=grayImage[yoff+bx+20];
        pel6=grayImage[yoff+bx+21];
        pel7=grayImage[yoff+bx+22];
        pel8=grayImage[yoff+bx+23];

        bitpackPel = 0;

        bitpackPel |= ( (pel1<=threshold) << shiftLUT[bx+16]  );
        bitpackPel |= ( (pel2<=threshold) << shiftLUT[bx+17]  );
        bitpackPel |= ( (pel3<=threshold) << shiftLUT[bx+18] );
        bitpackPel |= ( (pel4<=threshold) << shiftLUT[bx+19] );
        bitpackPel |= ( (pel5<=threshold) << shiftLUT[bx+20] );
        bitpackPel |= ( (pel6<=threshold) << shiftLUT[bx+21] );
        bitpackPel |= ( (pel7<=threshold) << shiftLUT[bx+22] );
        bitpackPel |= ( (pel8<=threshold) << shiftLUT[bx+23] );

        bitPackImage[byoff+(xOffsetLUT[bx+16])] = bitpackPel;

        //pixel 4 in bitpack image
        pel1=grayImage[yoff+bx+24];
        pel2=grayImage[yoff+bx+25];
        pel3=grayImage[yoff+bx+26];
        pel4=grayImage[yoff+bx+27];
        pel5=grayImage[yoff+bx+28];
        pel6=grayImage[yoff+bx+29];
        pel7=grayImage[yoff+bx+30];
        pel8=grayImage[yoff+bx+31];

        bitpackPel = 0;

        bitpackPel |= ( (pel1<=threshold) << shiftLUT[bx+24]  );
        bitpackPel |= ( (pel2<=threshold) << shiftLUT[bx+25]  );
        bitpackPel |= ( (pel3<=threshold) << shiftLUT[bx+26] );
        bitpackPel |= ( (pel4<=threshold) << shiftLUT[bx+27] );
        bitpackPel |= ( (pel5<=threshold) << shiftLUT[bx+28] );
        bitpackPel |= ( (pel6<=threshold) << shiftLUT[bx+29] );
        bitpackPel |= ( (pel7<=threshold) << shiftLUT[bx+30] );
        bitpackPel |= ( (pel8<=threshold) << shiftLUT[bx+31] );

        bitPackImage[byoff+(xOffsetLUT[bx+24])] = bitpackPel;
    }
}
}

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

Как вы можете видеть для каждого монохромного байта, я обрабатываю 8 пикселей в градациях серого.

Где вы видите pel8 <= порог это аккуратный маленький трюк, который разрешается до 0 или 1 и намного быстрее, чем если бы {} else {} </p>

Для каждого приращения X я упаковываю бит в бит более высокого порядка, чем предыдущий X

так для первого набора из 8 пикселей в изображении в градациях серого 

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

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

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

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

При включенной оптимизации компилятора эта функция занимает в среднем 16 миллисекунд на изображении размером примерно 5000 x 2200 пикселей на компьютере Core 2 Duo.

EDIT:

R .. предложил удалить смещение LUT и просто использовать константы, которые на самом деле совершенно логичны ... Я изменил OR для каждого пикселя, чтобы он был таким: 

void binarize( unsigned char grayImage[], unsigned char bitPackImage[], int threshold, int grayscaleWidth, int grayscaleHeight, int  bitPackedScanlineStride, int bitpackedLength,  int shiftLUT[], int xOffsetLUT[] )
{
int yoff;
int byoff;
unsigned char bitpackPel=0;
unsigned char pel1=0;
unsigned char  pel2=0;
unsigned char  pel3=0;
unsigned char  pel4=0;
unsigned char  pel5=0;
unsigned char  pel6=0;
unsigned char  pel7=0;
unsigned char  pel8=0;
int checkX=grayscaleWidth-32;
int checkY=grayscaleHeight;

for ( int by = 0 ; by < checkY; by++)
{
    yoff=by*grayscaleWidth;
    byoff=by*bitPackedScanlineStride;

    for( int bx = 0; bx < checkX; bx+=32)
    {
        bitpackPel = 0;

        //pixel 1 in bitpack image
        pel1=grayImage[yoff+bx];
        pel2=grayImage[yoff+bx+1];
        pel3=grayImage[yoff+bx+2];
        pel4=grayImage[yoff+bx+3];
        pel5=grayImage[yoff+bx+4];
        pel6=grayImage[yoff+bx+5];
        pel7=grayImage[yoff+bx+6];
        pel8=grayImage[yoff+bx+7];

        /*bitpackPel |= ( (pel1<=threshold) << shiftLUT[bx]);
        bitpackPel |= ( (pel2<=threshold) << shiftLUT[bx+1] );
        bitpackPel |= ( (pel3<=threshold) << shiftLUT[bx+2] );
        bitpackPel |= ( (pel4<=threshold) << shiftLUT[bx+3] );
        bitpackPel |= ( (pel5<=threshold) << shiftLUT[bx+4] );
        bitpackPel |= ( (pel6<=threshold) << shiftLUT[bx+5] );
        bitpackPel |= ( (pel7<=threshold) << shiftLUT[bx+6] );
        bitpackPel |= ( (pel8<=threshold) << shiftLUT[bx+7] );*/
        bitpackPel |= ( (pel1<=threshold) << 7);
        bitpackPel |= ( (pel2<=threshold) << 6 );
        bitpackPel |= ( (pel3<=threshold) << 5 );
        bitpackPel |= ( (pel4<=threshold) << 4 );
        bitpackPel |= ( (pel5<=threshold) << 3 );
        bitpackPel |= ( (pel6<=threshold) << 2 );
        bitpackPel |= ( (pel7<=threshold) << 1 );
        bitpackPel |= ( (pel8<=threshold)  );

        bitPackImage[byoff+(xOffsetLUT[bx])] = bitpackPel;

        //pixel 2 in bitpack image
        pel1=grayImage[yoff+bx+8];
        pel2=grayImage[yoff+bx+9];
        pel3=grayImage[yoff+bx+10];
        pel4=grayImage[yoff+bx+11];
        pel5=grayImage[yoff+bx+12];
        pel6=grayImage[yoff+bx+13];
        pel7=grayImage[yoff+bx+14];
        pel8=grayImage[yoff+bx+15];

        bitpackPel = 0;

        /*bitpackPel |= ( (pel1<=threshold) << shiftLUT[bx+8]  );
        bitpackPel |= ( (pel2<=threshold) << shiftLUT[bx+9]  );
        bitpackPel |= ( (pel3<=threshold) << shiftLUT[bx+10] );
        bitpackPel |= ( (pel4<=threshold) << shiftLUT[bx+11] );
        bitpackPel |= ( (pel5<=threshold) << shiftLUT[bx+12] );
        bitpackPel |= ( (pel6<=threshold) << shiftLUT[bx+13] );
        bitpackPel |= ( (pel7<=threshold) << shiftLUT[bx+14] );
        bitpackPel |= ( (pel8<=threshold) << shiftLUT[bx+15] );*/
         bitpackPel |= ( (pel1<=threshold) << 7);
        bitpackPel |= ( (pel2<=threshold) << 6 );
        bitpackPel |= ( (pel3<=threshold) << 5 );
        bitpackPel |= ( (pel4<=threshold) << 4 );
        bitpackPel |= ( (pel5<=threshold) << 3 );
        bitpackPel |= ( (pel6<=threshold) << 2 );
        bitpackPel |= ( (pel7<=threshold) << 1 );
        bitpackPel |= ( (pel8<=threshold)  );


        bitPackImage[byoff+(xOffsetLUT[bx+8])] = bitpackPel;

        //pixel 3 in bitpack image
        pel1=grayImage[yoff+bx+16];
        pel2=grayImage[yoff+bx+17];
        pel3=grayImage[yoff+bx+18];
        pel4=grayImage[yoff+bx+19];
        pel5=grayImage[yoff+bx+20];
        pel6=grayImage[yoff+bx+21];
        pel7=grayImage[yoff+bx+22];
        pel8=grayImage[yoff+bx+23];

        bitpackPel = 0;

        /*bitpackPel |= ( (pel1<=threshold) << shiftLUT[bx+16]  );
        bitpackPel |= ( (pel2<=threshold) << shiftLUT[bx+17]  );
        bitpackPel |= ( (pel3<=threshold) << shiftLUT[bx+18] );
        bitpackPel |= ( (pel4<=threshold) << shiftLUT[bx+19] );
        bitpackPel |= ( (pel5<=threshold) << shiftLUT[bx+20] );
        bitpackPel |= ( (pel6<=threshold) << shiftLUT[bx+21] );
        bitpackPel |= ( (pel7<=threshold) << shiftLUT[bx+22] );
        bitpackPel |= ( (pel8<=threshold) << shiftLUT[bx+23] );*/
          bitpackPel |= ( (pel1<=threshold) << 7);
        bitpackPel |= ( (pel2<=threshold) << 6 );
        bitpackPel |= ( (pel3<=threshold) << 5 );
        bitpackPel |= ( (pel4<=threshold) << 4 );
        bitpackPel |= ( (pel5<=threshold) << 3 );
        bitpackPel |= ( (pel6<=threshold) << 2 );
        bitpackPel |= ( (pel7<=threshold) << 1 );
        bitpackPel |= ( (pel8<=threshold)  );


        bitPackImage[byoff+(xOffsetLUT[bx+16])] = bitpackPel;

        //pixel 4 in bitpack image
        pel1=grayImage[yoff+bx+24];
        pel2=grayImage[yoff+bx+25];
        pel3=grayImage[yoff+bx+26];
        pel4=grayImage[yoff+bx+27];
        pel5=grayImage[yoff+bx+28];
        pel6=grayImage[yoff+bx+29];
        pel7=grayImage[yoff+bx+30];
        pel8=grayImage[yoff+bx+31];

        bitpackPel = 0;

        /*bitpackPel |= ( (pel1<=threshold) << shiftLUT[bx+24]  );
        bitpackPel |= ( (pel2<=threshold) << shiftLUT[bx+25]  );
        bitpackPel |= ( (pel3<=threshold) << shiftLUT[bx+26] );
        bitpackPel |= ( (pel4<=threshold) << shiftLUT[bx+27] );
        bitpackPel |= ( (pel5<=threshold) << shiftLUT[bx+28] );
        bitpackPel |= ( (pel6<=threshold) << shiftLUT[bx+29] );
        bitpackPel |= ( (pel7<=threshold) << shiftLUT[bx+30] );
        bitpackPel |= ( (pel8<=threshold) << shiftLUT[bx+31] );*/
         bitpackPel |= ( (pel1<=threshold) << 7);
        bitpackPel |= ( (pel2<=threshold) << 6 );
        bitpackPel |= ( (pel3<=threshold) << 5 );
        bitpackPel |= ( (pel4<=threshold) << 4 );
        bitpackPel |= ( (pel5<=threshold) << 3 );
        bitpackPel |= ( (pel6<=threshold) << 2 );
        bitpackPel |= ( (pel7<=threshold) << 1 );
        bitpackPel |= ( (pel8<=threshold)  );


        bitPackImage[byoff+(xOffsetLUT[bx+24])] = bitpackPel;
    }
}
}

Я сейчас тестирую на Intel Xeon 5670, используя (GCC) 4.1.2.Согласно этим спецификациям жестко закодированное смещение битов на 4 мс медленнее, чем при использовании моего оригинального алгоритма LUT.В Xeon и GCC алгоритм LUT занимает в среднем 8,61 мс, а жестко закодированное смещение битов - в среднем 12,285 мс.

Ответы [ 2 ]

2 голосов
/ 14 сентября 2010

Попробуйте что-то вроде: 

unsigned i, w8=w>>3, x;
for (i=0; i<w8; i++) {
    x = thres-src[0]>>1&0x80;
    x |= thres-src[1]>>2&0x40;
    x |= thres-src[2]>>3&0x20;
    x |= thres-src[3]>>4&0x10;
    x |= thres-src[4]>>5&0x08;
    x |= thres-src[5]>>6&0x04;
    x |= thres-src[6]>>7&0x02;
    x |= thres-src[7]>>8&0x01;
    out[i] = x;
    src += 8;
}

Вы можете определить дополнительный код для остатка в конце строки ширины, не кратного 8, или вы можете просто дополнить / выровнять источник, чтобы убедиться, что он кратен 8.

1 голос
/ 14 сентября 2010

Вы можете сделать это с помощью SSE довольно легко, обрабатывая 16 пикселей за раз, например,

  • вектор нагрузки (16 x 8 бит без знака)
  • add (255 - порог)для каждого элемента
  • используйте PMOVMSKB для извлечения знаковых битов в 16-разрядное слово
  • сохранение 16-разрядного слова

Пример кода с использованием встроенных функций SSE (предупреждение: не проверено!):

void threshold_and_pack(
    const uint8_t * in_image,       // input image, 16 byte aligned, height rows x width cols, width = multiple of 16
    uint8_t * out_image,            // output image, 2 byte aligned, height rows x width/8 cols, width = multiple of 2
    const uint8_t threshold,        // threshold
    const int width,
    const int height)
{
    const __m128i vThreshold = _mm_set1_epi8(255 - threshold);
    int i, j;

    for (i = 0; i < height; ++i)
    {
        const __m128i * p_in = (__m128i *)&in_image[i * width];
        uint16_t * p_out = (uint16_t *)&out_image[i * width / CHAR_BIT];

        for (j = 0; j < width; j += 16)
        {
            __m128i v = _mm_load_si128(p_in);
            uint16_t b;

            v = _mm_add_epi8(v, vThreshold);
            b = _mm_movemask_epi8(v);   // use PMOVMSKB to pack sign bits into 16 bit word

            *p_out = b;

            p_in++;
            p_out++;
        }
    }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...