How to transpose in-place a bitmap in C++

Question

I trying to create a function to transpose in-place a bitmap. But so far, the result I get is all messed up, and I can’t find what I’m doing wrong.

Source bitmaps are as a 1d pixel array in ARGB format.

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;
        }
    }
}

UPDATE:

To clarify and avoid confusions as it seems some people think this is just a rotate image question. Transposing an image is composed by 2 transformations: 1) flip horizontally 2) Rotate by 90 CCW. (As shown in the image example, see the arrow directions)

Answer 1

I think the problem is more complex than you realise and is not simply a case of swapping the pixels at x, y with the pixels at y, x. If you consider a 3*7 pixel image in which I've labelled the pixels a-u:

abcdefg
hijklmn
opqrstu

Rotating this image gives:

aho
bip
cjq
dkr
els
fmt
gnu

Turning both images into a 1D array gives:

abcdefghijklmnopqrstu

ahobipcjqdkrelsfmtgnu

Notice that b has moved to the position of d but has been replaced by h.

Rethink your algorithm, draw it out for a small image and make sure it works before attempting to implement it.

Due to the complexity of the task it may actually end up being faster to create a temporary buffer, rotate into that buffer then copy back as it could end up with fewer copies (2 per pixel) than the inplace algorithm that you come up with.

Answer 2

Mostly equivalent code that should be easier to debug:

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;
        }
    }
}

If this doesn't work right, it is possible that it needs to know not just the width of the picture, but also the width of the underlying buffer. This only flips the square portion at the top-left, more work would be needed for non-square bitmaps. (or just pad everything to square before using...)

Answer 3

Note that transposing a matrix in place is not trivial when N!=M. See eg here for details.

The reason is that when N=M you can simply iterate through half of the matrix and swap elements. When N!=M this isnt the case.

For illustration, consider a simpler case:

First a 2d view on 1d data:

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;
}

Now a transpose that would work for 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;
}

Using it for some small matrix

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;
}

prints

1 2
3 4
5 6

1 2 3
4 5 6

1 3 2
2 2 6

Conclusion: The naive swapping elements approach does not work for non-square matrices.

Actually this answer just rephrases the one by @Alan Birtles. I felt challenged by his

Due to the complexity of the task it may actually end up being faster to create a temporary buffer [...]

just to come to the same conclusion ;).