Faster image rotation
in [Embedded]
|
From: robin on 17 Apr 2010 04:44 "Noob" <root(a)127.0.0.1> wrote in message news:hphm36$puk$1(a)speranza.aioe.org... | I need to rotate a picture clockwise 90 degrees. | | Conceptually, my picture is represented by a matrix | (W columns, H rows) of pixels, with each pixel | represented by 3 octets. | | pixel original_picture[W][H]; | pixel rotated_picture[H][W]; | | At the implementation level, I'm dealing with 1D integer arrays. | | int src[W*H*3]; | int dest[W*H*3]; | | Conceptually, the rotation operation comes down to | | rotated_picture[j][H-1-i] = original_picture[i][j] | | My actual code is | | for (i = 0; i < H; ++i) | for (j = 0; j < W; ++j) | memcpy(dest+(H*j+H-1-i)*3, src+(W*i+j)*3, 3); This is not going to be fast because:- 1. you are calling a subroutine 1,913,616 times to move 9 or 48 bits each time. 2. You are multiplying by 3 twice for each move. 3. You are using integer arrays. 1. Best to use ordinary assignment. 2. Eliminate *3 by changing to adds. 3. Use byte arrays (but I'm not clear about what you say. You say that you have octets. Now 3 octets will be 9 bits, not 3 integers equal to 48 bits.) This is how it would look in PL/I:- declare (src(m,n), dest(n,m)) char (3); do i = 1 to m; dest(*, m-i+1) = src(i,*); end; If the color information really is octets, then the declaration is changed to bit (9) aligned.
From: glen herrmannsfeldt on 17 Apr 2010 05:50 In comp.lang.pl1 robin <robin_v(a)bigpond.com> wrote: > "Noob" <root(a)127.0.0.1> wrote in message news:hphm36$puk$1(a)speranza.aioe.org... > | I need to rotate a picture clockwise 90 degrees. > | Conceptually, my picture is represented by a matrix > | (W columns, H rows) of pixels, with each pixel > | represented by 3 octets. > | pixel original_picture[W][H]; > | pixel rotated_picture[H][W]; > | At the implementation level, I'm dealing with 1D integer arrays. > | int src[W*H*3]; > | int dest[W*H*3]; > | Conceptually, the rotation operation comes down to > | rotated_picture[j][H-1-i] = original_picture[i][j] > | My actual code is > | for (i = 0; i < H; ++i) > | for (j = 0; j < W; ++j) > | memcpy(dest+(H*j+H-1-i)*3, src+(W*i+j)*3, 3); This is basically a matrix transpose (with the difference that one goes down instead of up). There are cache friendly matrix transpose algorithms that should also speed this one up. > This is not going to be fast because:- > 1. you are calling a subroutine 1,913,616 times to move > 9 or 48 bits each time. Many C compilers implement memcpy() inline. I suppose you believe that PL/I does a subroutine call for the MOD function? > 2. You are multiplying by 3 twice for each move. Most can also figure that one out. > 3. You are using integer arrays. > 1. Best to use ordinary assignment. > 2. Eliminate *3 by changing to adds. > 3. Use byte arrays (but I'm not clear about what you say. > You say that you have octets. Now 3 octets will be 9 bits, > not 3 integers equal to 48 bits.) -- glen
From: larwe on 17 Apr 2010 13:15 On Apr 8, 5:43 am, Noob <r...(a)127.0.0.1> wrote: > > Are you sure you will *always* want to rotate CW by > > exactly 90 deg? > > I'm displaying JPEG photographs. Some users want to rotate the pictures > (landscape to portrait). AFAICS, all I need is 90° either way. When I did my first digital picture frame project, I had a standardized "put_image" routine that took parameters for width, height, destination pixel step and destination row step. The p-code was something like: for (i=0;i<height;i++) { for (j=0;j<width;j++) { *dest++ = *src; src += pixel_step; } src += row_step; } // outer loop You will save time by combining decimation and rotation into one step. When I did my _second_ such project, I had a "real" hardware platform, so I just used OpenGL - I set up the unrotated image as a texture, and drew a rectangle with that texture. All I had to do to rotate or scale was change the coordinates of the corners, and the graphics chip did the rendering :)
From: larwe on 17 Apr 2010 13:25 On Apr 17, 1:15 pm, larwe <zwsdot...(a)gmail.com> wrote: > On Apr 8, 5:43 am, Noob <r...(a)127.0.0.1> wrote: > > > > Are you sure you will *always* want to rotate CW by > > > exactly 90 deg? > > > I'm displaying JPEG photographs. Some users want to rotate the pictures > > (landscape to portrait). AFAICS, all I need is 90° either way. > > When I did my first digital picture frame project, I had a > standardized "put_image" routine that took parameters for width, > height, destination pixel step and destination row step. The p-code > was something like: > > for (i=0;i<height;i++) { > for (j=0;j<width;j++) { > *dest++ = *src; > src += pixel_step; > > } > src += row_step; > } // outer loop > > You will save time by combining decimation and rotation into one step. > > When I did my _second_ such project, I had a "real" hardware platform, > so I just used OpenGL - I set up the unrotated image as a texture, and > drew a rectangle with that texture. All I had to do to rotate or scale > was change the coordinates of the corners, and the graphics chip did > the rendering :) Oops, make that dest +=, not src +=
From: John W Kennedy on 17 Apr 2010 23:40
On 2010-04-17 04:44:49 -0400, robin said: > Now 3 octets will be 9 bits, Robin, will you /please/ stop blithering on about things you don't understand?! Buy a Data Processing dictionary, for God's sake! The rest of this is addressed to the original poster: I don't understand why you're using int variables for octets; they should be char. For the rest, I'd do the following: typedef struct __Pixel { unsigned char red, green, blue; } Pixel; Pixel src[W][H]; Pixel dest[H][W]; for (int i = 0; i < W; ++i) for (int j = 0; j < H; ++i) { dest[j][i].red = src[i][j].red; dest[j][i].green = src[i][j].green; dest[j][i].blue = src[i][j].blue; } I'd also try: for (int i = 0; i < W; ++i) for (int j = 0; j < H; ++i) memcpy(dest[j][i], src[i][j], sizeof (Pixel)); and see which one is faster; it will depend on the individual compiler. (Make sure you test at the same optimization level you plan to use.) -- John W Kennedy "There are those who argue that everything breaks even in this old dump of a world of ours. I suppose these ginks who argue that way hold that because the rich man gets ice in the summer and the poor man gets it in the winter things are breaking even for both. Maybe so, but I'll swear I can't see it that way." -- The last words of Bat Masterson |