c - 如何优化图像像素化程序

Question

我已经编写了一些串行代码，我想在使用 OpenMP 将其并行化之前尽可能对其进行优化。该程序通过遍历 4x4 单元格(变量 c)中的像素数据来读入 PPM 文件，然后找到每个 4x4 单元格的平均 RGB 值，最后写入一个新文件通过再次输出每个 4x4 单元格的平均颜色值。这会产生一种马赛克/像素化效果。

对我的代码进行性能分析，主要瓶颈是 fscanf 和 fprintf。我忽略了读/写磁盘的执行时间，所以这两个函数无关紧要。

到目前为止我为优化所做的努力:

• 循环干扰:代码中有两个嵌套的 FOR 循环，它们具有完全相同的循环条件。但是，第二组嵌套的 FOR 循环要求计算平均 RGB 值所需的函数保留在该特定组之外。然后需要在第三组嵌套 FOR 循环(具有与第二组相同的循环条件)中使用平均 RGB 值计算。正因为如此，我一直在努力组合第二和第三组嵌套 FOR 循环，尽管它们很相似。

• 循环不变计算:我曾尝试尽可能将某些操作移出循环，但事实证明这很困难。

总结一下:我如何优化这个程序以尽可能减少执行时间？

我的代码:

typedef struct {                                //struct holding RGB type int
    int r, g, b;    //12 bytes
} pixelInt;
typedef struct {                                //struct holding RGB type unsigned char
    unsigned char r, g, b;  //3 bytes
} pixel;

int c = 4;             // Variable of 4x4 grids
int width, height;    //image variable declarations

//Raw 1 dimensional store of pixel data - will contain all the data for each pixel in the image
pixel *data = (pixel *)calloc(width * height, sizeof(pixelInt));

//Loop through entire input image 
        for (int yy = 0; yy < height; yy += c)
        {
            for (int xx = 0; xx < width; xx += c)
            {
                //the total colour of cell of size 'c'
                pixelInt cell_tot = { 0, 0, 0 };        //zero initialize struct containing mosaic cell pixel totals.

                unsigned int counter = 0; //the counter for how many pixels are in a 4x4 cell

                int bx = xx + c;  //used in loop conditions
                int by = yy + c;

                // Store each color from the cell into cell_tot struct
                for (int y = yy; y < by; y++)
                {
                    for (int x = xx; x < bx; x++)
                    {
                        unsigned int index_1d = x + y * width;      //calculate 1d index from x-index (x), y-index(y) and width;

                        unsigned char r, g, b; //maximum vales are 255, i.e. unsigned char data type                    

                        fscanf(f, "%hhu %hhu %hhu", &r, &g, &b); //%hhu is unsigned char specifier

                        //store the pixel value into data array
                        data[index_1d].r = r;
                        data[index_1d].g = g;
                        data[index_1d].b = b;

                        counter++; //increment counter

                        //average pixel color of cell
                        cell_tot.r += r;
                        cell_tot.g += g;
                        cell_tot.b += b;

                    }
                }

                //average colour of cell found by dividing cell total by loop counter 
                pixel cell_average;
                cell_average.r = cell_tot.r / counter;
                cell_average.g = cell_tot.g / counter;
                cell_average.b = cell_tot.b / counter;

                //Loop through the new image in cells of size c 
                for (int y = yy; y < by; y++)
                {
                    for (int x = xx; x < bx; x++)
                    {
                        unsigned int index_1d = x + y * width;      //calculate 1d index from x-index (x), y-index(y) and width;

                        //Assign average cell value to the pixels in the cell
                        data[index_1d].r = cell_average.r;
                        data[index_1d].g = cell_average.g;
                        data[index_1d].b = cell_average.b;

                        //Output the average colour value for the image  
                        fprintf(f_output, "%hhu %hhu %hhu \t", data[index_1d].r, data[index_1d].g, data[index_1d].b);
                    }
                    fprintf(f_output, "\n");    //Prints new line 
                }
            }
        } 

Answer 1

在我机器上的 1024x1024 图像上，您的代码在 0.325s 内执行。以下代码在 0.182s 内执行:

unsigned w = width/c, h = height/c;
unsigned *accum = (unsigned*)malloc(3*sizeof(unsigned)*w);
char *line = (char*)malloc(12*w);
unsigned denom = c*c;

//Loop through entire input image 
for (int yy = 0; yy < h; ++yy)
{
    memset(accum, 0, 3*sizeof(unsigned)*w);

    // read and accumulate c lines
    for(int y = 0; y < c; ++y)
    {
        for (int xx = 0; xx < w; ++xx)
        {
            for (int x = 0; x < c; ++x)
            {
                unsigned char r, g, b;
                fscanf(f, "%hhu %hhu %hhu", &r, &g, &b);
                accum[3*xx+0] += r;
                accum[3*xx+1] += g;
                accum[3*xx+2] += b;
            }
        }
    }

    // format a line
    for(int xx = 0; xx < w; ++xx)
    {
        char *cell = line + 12*c*xx; 
        snprintf(cell, 12, "%3u%4u%4u", accum[3*xx]/denom, accum[3*xx+1]/denom, accum[3*xx+2]/denom);
        cell[11] = '\t';
        for(int x = 1; x < c; ++x)
            memcpy(cell + 12*x, cell, 12);
    }

    // write it out times c
    line[12*w-1] = '\n';
    for(int y = 0; y < c; ++y)
        fwrite(line, 12*w, 1, f_output);
}

这里的技巧是只对平均值格式化一次，然后复制格式化的字符串。此外，通过一次对一行进行操作，我可以更好地利用内存缓存。

要超越它，您需要重新实现 fscanf 以更快地解析整数。