Как транспонировать растровое изображение на месте в переполнении стека

Question

Как транспонировать растровое изображение на месте в переполнении стека

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

Исходные растровые изображения представлены в виде 1-пиксельного массива в формате ARGB.

void transpose(uint8_t* buffer, const uint32_t width, const uint32_t height)
{
const size_t stride = width * sizeof(uint32_t);

for (uint32_t i = 0; i < height; i++)
{
uint32_t* row = (uint32_t*)(buffer + (stride * i));
uint8_t* section = buffer + (i * sizeof(uint32_t));

for (uint32_t j = i + 1; j < height; j++)
{
const uint32_t tmp = row[j];
row[j] = *((uint32_t*)(section + (stride * j)));
*((uint32_t*)(section + (stride * j))) = tmp;
}
}
}

ОБНОВИТЬ:

Чтобы уточнить и избежать путаницы, как кажется, некоторые люди думают, что это просто вопрос поворота изображения. Транспонирование изображение состоит из двух преобразований: 1) перевернуть горизонтально 2) повернуть на 90 против часовой стрелки. (Как показано на примере изображения, см стрелки направления)

1

bitmap c++in-place transpose

Решение

Другие решения

В основном эквивалентный код, который должен быть легче отлаживать:

inline uint32_t * addr(uint8_t* buffer, const uint32_t width, uint32_t i, uint32_t j) {
uint32_t * tmp = buffer;
return tmp+i*width+j;
}

void transpose(uint8_t* buffer, const uint32_t width, const uint32_t height) {
for (uint32_t i = 0; i < min(width,height); i++) {
for (uint32_t j = 0; j < i; j++) {
uint32_t * a = addr(buffer, width, i, j);
uint32_t * b = addr(buffer, width, j, i);
const uint32_t tmp = *a;
*a = *b;
*b = tmp;
}
}
}

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

0

Обратите внимание, что транспонирование матрицы на месте не тривиально, когда N!=M, См. Например Вот для деталей.

Причина в том, что когда N=M Вы можете просто перебрать половину матрицы и поменять местами элементы. когда N!=M это не так.

Для иллюстрации рассмотрим более простой случай:

Сначала 2d просмотр 1d данных:

struct my2dview {
std::vector<int>& data;
int width,height;
my2dview(std::vector<int>& data,int width,int height):data(data),width(width),height(height){}
int operator()(int x,int y) const { return data[x*width + y]; }
int& operator()(int x,int y){ return data[x*width + y]; }
my2dview get_transposed() { return my2dview(data,height,width);}
};std::ostream& operator<<(std::ostream& out, const my2dview& x){
for (int h=0;h<x.height;++h){
for (int w=0;w<x.width;++w){
out << x(h,w) << " ";
}
out << "\n";
}
return out;
}

Теперь транспонирование, которое будет работать для N=M:

my2dview broken_transpose(my2dview x){
auto res = x.get_transposed();
for (int i=0;i<x.height;++i){
for (int j=0;j<x.width;++j){
res(j,i) = x(i,j);
}
}
return res;
}

Используя его для небольшой матрицы

int main() {
std::vector<int> x{1,2,3,4,5,6};
auto v = my2dview(x,2,3);
std::cout << v << '\n';
std::cout << v.get_transposed() << '\n';
auto v2 = broken_transpose(v);
std::cout << v2;
}

печать

Вывод: метод наивных элементов обмена не работает для неквадратных матриц.

На самом деле этот ответ перефразирует ответ @Alan Birtles. Я чувствовал, что его

Из-за сложности задачи на самом деле может оказаться быстрее создать временный буфер […]

просто чтобы прийти к такому же выводу;).

0

Источник

Accepted Answer

Я думаю, что проблема сложнее, чем вы думаете, и это не просто случай замены пикселей на x, y с пикселями в y, x, Если вы рассматриваете изображение размером 3 * 7 пикселей, в котором я пометил пиксели a—u:

abcdefg
hijklmn
opqrstu

Вращение этого изображения дает:

aho
bip
cjq
dkr
els
fmt
gnu

Превращение обоих изображений в одномерный массив дает:

abcdefghijklmnopqrstu

ahobipcjqdkrelsfmtgnu

Заметить, что b перешел в положение d но был заменен h,

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

Из-за сложности задачи на самом деле может оказаться быстрее создать временный буфер, повернуть его в этот буфер и затем скопировать обратно, так как в результате может быть меньше копий (2 на пиксель), чем у алгоритма на месте, который вы придумали.

1