C оптимизация поворот изображения

Question

Это для всех экспертов вы C там ..

Первая функция принимает двумерную матрицу SRC [DIM] [DIM], представляющий пиксели изображения, и поворачивается на 90 градусов в матрица адреса dst [dim] [dim]. Вторая функция принимает один и тот же src [dim] [dim] и сглаживает изображение, заменяя каждое значение пикселя на среднее значение всех пикселей вокруг него (в максимальном размере 3 × 3 окна с центром в этом пикселе).

мне нужно оптимизировать программу учета времени и циклов, как еще я мог бы оптимизировать следующие ?:

void rotate(int dim, pixel *src, pixel *dst,) 
{ 
    int i, j, nj; 
    nj = 0; 

    /* below are the main computations for the implementation of rotate. */ 
    for (j = 0; j < dim; j++) { 
     nj = dim-1-j;    /* Code Motion moved operation outside inner for loop */ 
     for (i = 0; i < dim; i++) { 
      dst[RIDX(nj, i, dim)] = src[RIDX(i, j, dim)]; 
     } 
    } 
} 



/* A struct used to compute averaged pixel value */ 
typedef struct { 
    int red; 
    int green; 
    int blue; 
    int num; 
} pixel_sum; 

/* Compute min and max of two integers, respectively */ 
static int minimum(int a, int b) 
{ return (a < b ? a : b); } 
static int maximum(int a, int b) 
{ return (a > b ? a : b); } 

/* 
* initialize_pixel_sum - Initializes all fields of sum to 0 
*/ 
static void initialize_pixel_sum(pixel_sum *sum) 
{ 
    sum->red = sum->green = sum->blue = 0; 
    sum->num = 0; 
    return; 
} 

/* 
* accumulate_sum - Accumulates field values of p in corresponding 
* fields of sum 
*/ 
static void accumulate_sum(pixel_sum *sum, pixel p) 
{ 
    sum->red += (int) p.red; 
    sum->green += (int) p.green; 
    sum->blue += (int) p.blue; 
    sum->num++; 
    return; 
} 

/* 
* assign_sum_to_pixel - Computes averaged pixel value in current_pixel 
*/ 
static void assign_sum_to_pixel(pixel *current_pixel, pixel_sum sum) 
{ 
    current_pixel->red = (unsigned short) (sum.red/sum.num); 
    current_pixel->green = (unsigned short) (sum.green/sum.num); 
    current_pixel->blue = (unsigned short) (sum.blue/sum.num); 
    return; 
} 

/* 
* avg - Returns averaged pixel value at (i,j) 
*/ 
static pixel avg(int dim, int i, int j, pixel *src) 
{ 
    int ii, jj; 
    pixel_sum sum; 
    pixel current_pixel; 

    initialize_pixel_sum(&sum); 
    for(ii = maximum(i-1, 0); ii <= minimum(i+1, dim-1); ii++) 
     for(jj = maximum(j-1, 0); jj <= minimum(j+1, dim-1); jj++) 
      accumulate_sum(&sum, src[RIDX(ii, jj, dim)]); 

    assign_sum_to_pixel(&current_pixel, sum); 
    return current_pixel; 
} 

void smooth(int dim, pixel *src, pixel *dst) 
{ 
    int i, j; 


    /* below are the main computations for the implementation of the smooth function. */ 

    for (j = 0; j < dim; j++) 
     for (i = 0; i < dim; i++) 
      dst[RIDX(i, j, dim)] = avg(dim, i, j, src); 
} 

я переехал дим-1-J вне внутренней для петли вращать, что сокращает время и циклы, используемые в программе, но есть ли что-нибудь еще, что можно использовать для основной функции?

Спасибо!

Answer 1

Существует несколько оприметий, которые вы можете сделать; какой-то компилятор может сделать для вас, но лучше всего написать это самостоятельно. Например: перемещение константных выражений из цикла (вы сделали это один раз, есть больше мест, где вы можете это сделать - не забывайте, что условие проверяется на каждую итерацию тоже, поэтому оптимизируйте условие цикла таким же образом) и, как указал Крис, используйте указатели, которые вы увеличиваете, а не индексируете полный массив. Я также вижу некоторые вызовы функций, которые можно переписать в строке.

Я также хочу указать на статью о stackoverflow о матричном умножении и оптимизации использования кеша процессора. По сути, он сначала реорганизовывает аранжировки в ячейки памяти, которые соответствуют кешу, затем выполняет операцию над этими блоками, затем переходит к следующему блоку и так далее. Возможно, вы сможете повторно использовать идеи для своего вращения. См. Optimizing assembly generated by Microsoft Visual Studio Compiler

Answer 2

Для поворота вы получаете лучшее использование кеша, разлагая более мелкие фрагменты изображения.

Для сглаживания,

1) расширить всю операцию внутри основной двойной петли, не следует использовать эти промежуточные микро-функции;

2) полностью разворачивает накопление и усреднение (это всего лишь сумма из 9 терминов), жесткое кодирование индексов;

3) обрабатываются в разных циклах по краям (где не все 9 пикселей доступны) и посередине. Середина заслуживает максимальной оптимизации (особенно (2));

4) попытайтесь избежать делений на 9 (вы можете подумать о замене деления на поиск таблицы).

Максимальная скорость будет получена с помощью векторной оптимизации (SSE/AVX), но для этого требуется определенный опыт. Опция многоядерности также является опцией.

Чтобы дать вам представление, можно применить среднее значение 3x3 на полутоновом изображении 1 МБ менее чем за 0,5 мс (монокор, Core i7 @ 3,4 ГГц). Мы можем экстраполировать до 2 мс или около того для 1 Мпиксельного изображения RGB.

Answer 3

Поскольку вы не можете обеспечить выполнение программы это лишь идеи вещей, которые могли бы помочь:

• Предполагая, что значения в диапазоне [0,256), а затем использовать uint8_t как ваши ценности rgbn.Это занимает 1/4 от памяти версии int, но, скорее всего, потребуется больше циклов; Я не знаю, будет ли это быстрее или нет, без каких-либо знаний. Идея состоит в том, что, поскольку вы используете 1/4 памяти, у вас больше шансов сохранить больше значений в кеше L1-L3.
• Поскольку ваши соседи одинаковы независимо от того, повернуты вы или нет, вычислите среднее значение перед вращением. Я подозреваю, что это поможет в кэшировании, но опять же не может быть уверенным; это зависит от кода, который я не вижу.
• Распределить внешний контур. Поскольку у вас есть простые размеры сетки, а входы и выходы не имеют конфликтов чтения/записи, это тривиальная задача. Это, безусловно, займет больше циклов, но, возможно, будет быстрее.
• Жесткий код ваших краев; вы в настоящее время выполняете максимальные и минимальные операции для каждого вызова в среднем, но для внутренних точек он не нужен. Вычислите ребра и внутренние точки отдельно.