Fast image (or matrix) transpose implementation in C++

Question

This post discussed about how to transpose an image with OpenCV, and here I want to go further: suppose the image is gray-scale one, what is the fastest way of transposing it (or matrix) using C++? My solution is as follows:

        // image data is stored in an image buffer image*buffer_

    unsigned char *mem = (unsigned char *) malloc(image.bufferSize_);

    int height = image.Height();
    int width = image.Width();
    for(int i=0; i<height; i++)
    {
        unsigned char *ptr =image.buffer_+i*width;
        for(int j=0; j<width; j++)
            *(mem+j*height+i) = *(ptr+j);
    }


    memcpy(image.buffer_,mem,image.bufferSize_);
    free(mem);

Some explanations above the above code: we create an image object that contains basic image information as well as the image pixels (in image.buffer_). When image pixels are stored in image.buffer_, we assume the image pixels are kept row by row. Any ideas on further improving the above codes?

Why are you using `malloc`/`free` when programming C++? – Some programmer dude Sep 18 '13 at 10:14 — Some programmer dude, Sep 18 '13 at 10:14
Why not just use `cvTranspose()` or `cv::transpose()` ? – Paul R Sep 18 '13 at 10:16 — Paul R, Sep 18 '13 at 10:16
why bother ? `Mat m; m.t();` is the transpose – berak Sep 18 '13 at 10:42 — berak, Sep 18 '13 at 10:42
I agree, you're not going to beat the cv::Mat::t() – jodag Sep 18 '13 at 16:42 — jodag, Sep 18 '13 at 16:42

iavr · Accepted Answer · 2013-09-18T16:23:19.010

Without touching the malloc/free part, the copying part could go like this:

    size_t len = image.bufferSize_,
           len1 = len - 1;

    unsigned char *src = image.buffer_,
                  *dest = mem,
                  *end = dest + len;

    for(size_t i = 0; i < len; i++)
    {
        *dest++ = *src;  // dest moves to next row
        src += height;   // src moves to next column

        // src wraps around and moves to next row
        if (src > end) src -= len1;
    }

This is a equivalent to having a column-wise destination iterator and a row-wise source iterator.

Without actually testing it, I feel this will be faster: it has 3 operations for offset computation in the inner loop vs. 4 in your version (plus 2 dereferencing operations in both versions).

EDIT

One more improvement, and a correction:

    //...
    unsigned char *src = image.buffer_,
                  *src_end = src + len,
                  *dest = mem,
                  *dest_end = dest + len;

    while (dest != dest_end)
    {
        *dest++ = *src;  // dest moves to next row
        src += height;   // src moves to next column

        // src wraps around and moves to next row
        if (src > src_end) src -= len1;
    }

This saves one more operation per iteration (i++ in the for loop). Also src was compared to the wrong end previously.

it should be if (src >= src_end) src -= len1; – feelfree Dec 23 '14 at 17:17 — feelfree, Dec 23 '14 at 17:17

Fast image (or matrix) transpose implementation in C++

1 Answers1