Незначительная оптимизация:
for(int shiftY = 0; shiftY < rangeY; shiftY++) {
for(int shiftX = 0; shiftX < rangeX; shiftX++) {
// if you can assume SAD is already filled with 0-es,
// you don't need the next line
SAD[shiftX][shiftY]=0;
for(int tx = 0, imx=shiftX; x < lenTemplateX; tx++,imx++) {
for(int ty = 0, imy=shiftY; y < lenTemplateY; ty++,imy++) {
// two increments of imx/imy may be cheaper than
// two addition with offsets
SAD[shiftY][shiftX]+=abs(template_grid[tx][ty] - image[imx][imy]);
}
}
}
}
Развертывание цикла с использованием шаблонов C ++
Может быть, сумасшедшая идея для вашей конфигурации (меня беспокоит компилятор C ++), но она может работать. Я не даю никаких гарантий, но попробуйте.
Идея может работать, потому что ваши template_grid размеры и диапазоны постоянны - таким образом, они известны во время компиляции.
Кроме того, чтобы это работало, ваши image и template_grid должны быть организованы с одинаковым макетом (первый столбец или первый ряд) - способ, которым ваш "пример кода" изображен в вопросе, смешивает SAD x/y с template_grid y/x.
В дальнейшем я буду использовать организацию «по столбцу», так что SAD[ix] обозначает столбец ix th вашей матрицы SAD**. Код работает так же, как и «row first», за исключением того, что имя переменных не будет соответствовать значению ваших массивов значений.
Итак, начнем:
template <
typename sad_type, typename val_type,
size_t template_len
> struct sad1D_simple {
void operator()(
const val_type* img, const val_type* templ,
sad_type& result
) {
// template specialization recursion, with one less element to add
sad1D_simple<sad_type, val_type, template_len-1> one_shorter;
// call it incrementing the img and template offsets
one_shorter(img+1, templ+1, result);
// the add the contribution of the first diff we skipped over above
result+=abs(*(img+template_len-1)-*(templ+template_len-1));
}
};
// at len of 0, the result is zero. We need it to stop the
template <
typename sad_type, typename val_type
>
struct sad1D_simple<sad_type, val_type, 0> {
void operator()(
const val_type* img, const val_type* templ,
sad_type& result
) {
result=0;
}
};
Почему функтор struct - struct с оператором? C ++ не допускает частичную специализацию шаблонов функций .
Что делает sad1D_simple: развертывает цикл for, который вычисляет SAD двух входных массивов без какого-либо смещения, основываясь на том факте, что длина вашего массива template_grid является постоянной, известной во время компиляции. Это в том же духе, что и «вычисление факториала времени компиляции с использованием шаблонов C ++»
Как это помогает?
Пример использования в приведенном ниже коде:
typedef ulong SAD_t;
typedef int16_t pixel_val_t;
const size_t lenTemplateX = 7; // number of cols in the template_grid
const size_t lenTemplateY = 61;
const size_t rangeX=10, rangeY=45;
pixel_val_t **image, **template_grid;
SAD_t** SAD;
// assume those are initialized somehow
for(size_t tgrid_col=0; tgrid_col<lenTemplateX; tgrid_col++) {
pixel_val_t* template_col=template_grid[tgrid_col];
// the X axis - horizontal - is the column axis, right?
for(size_t shiftX=0; shiftX < rangeX; shiftX++) {
pixel_val_t* img_col=image[shiftX];
for(size_t shiftY = 0; shiftY < rangeY; shiftY++) {
// the Y axis - vertical - is the "offset in a column"=row, isn't it?
pixel_val_t* img_col_offsetted=img_col+shiftY;
// this functor is made by recursive specialization
// there's no cycle inside it, it was unrolled into
// lenTemplateY individual subtractions, abs-es and additions
sad1D_simple<SAD_t, pixel_val_t, lenTemplateY> calc;
calc(img_col_offsetted, template_col, SAD[shiftX][shiftY]);
}
}
}
Мммм ... мы можем сделать лучше? Нет, это не будет развертывание по оси X, мы все еще хотим остаться в одномерной области, но ... ну, может быть, если мы создадим ранжированный sad1D и развернем еще один цикл на той же оси?
Это будет работать , если f rangeX также является постоянным.
template <
typename sad_type, typename val_type,
size_t range, size_t template_len
> struct sad1D_ranged {
void operator()(
const val_type* img, const val_type* templ,
// result is assumed to have at least `range` slots
sad_type* result
) {
// we'll compute here the first slot of the result
sad1D_simple<sad_type, val_type, template_len>
calculator_for_first_sad;
calculator_for_first_sad(img, templ, *(result));
// now, ask for a recursive specialization for
// the next (range-1) sad-s
sad1D_ranged<sad_type, val_type, range-1, template_len>
one_less_in_range;
// when calling, pass the shifted img and result
one_less_in_range(img+1, templ, result+1);
}
};
// for a range of 0, there's nothing to do, but we need it
// to stop the template specialization recursion
template <
typename sad_type, typename val_type,
size_t template_len
> struct sad1D_ranged<sad_type, val_type, 0, template_len> {
void operator()(
const val_type* img, const val_type* templ,
// result is assumed to have at least `range` slots
sad_type* result
) {
}
};
А вот как вы его используете:
for(size_t tgrid_col=0; tgrid_col<lenTemplateX; tgrid_col++) {
pixel_val_t* template_col=template_grid[tgrid_col];
for(size_t shiftX=0; shiftX < rangeX; shiftX++) {
pixel_val_t* img_col=image[shiftX];
SAD_t* sad_col=SAD[shiftX];
sad1D_ranged<SAD_t, pixel_val_t, rangeY, lenTemplateY> calc;
calc(img_col, template_col, sad_col);
}
}
Да ... но вопрос: это улучшит производительность ?
Черт возьми, если я знаю. Для небольшого числа циклов в цикле и для сильной локальности данных (значения близки друг к другу, так что они находятся в кэшах ЦП), развертывание цикла должно улучшить производительность. При большем числе циклов вы можете отрицательно повлиять на предсказание ветвления ЦП и другие "бесполезные", "я знаю, может повлиять на производительность, но я не знаю, как".
Чувство мужества: даже если одна и та же техника развертывания может работать для двух других циклов, ее использование может привести к снижению производительности: нам нужно перейти с одного смежного вектора (столбец image) на другой - все изображение может не помещаться в кэш процессора.
Примечание: , если ваши данные template_grid также постоянны (или у вас есть конечный набор постоянных сеток шаблонов), можно сделать еще один шаг и создать структурные функторы с выделенными масками. Но я выдохся на сегодня.