图像原地旋转 -90°算法

gxqcn

现在有个比较有挑战性的问题，想与大家一起讨论。

需要在尽可能小的内存空间里，将一个位图逆时针旋转90°；
因为这将运行在嵌入式设备中，内存资源相当相当地宝贵。

gxqcn

还有些方面需要注意：

它的数据存放格式与普通位图的不一致，
它是将每一行的R通道的数据依次排列完，然后再依次排列G通道和B通道的数据；
一行像素排列完再紧跟着排列下一行，直至排列完。

旋转前与旋转后的数据格式均遵循该规则。

图像的宽W好高H均为4的整数倍，它们 W*H*3 约有 6M，
要求额外可用内存不到 1MB，当然在效率保证的前提下越少越好。


下面举个例子：假设旋转前 W=3, H=4 （实际上 W、H 都很大，且均为 4 的整数倍）

R11 R12 R13
G11 G12 G13
B11 B12 B13

R21 R22 R23
G21 G22 G23
B21 B22 B23

R31 R32 R33
G31 G32 G33
B31 B32 B33

R41 R42 R43
G41 G42 G43
B41 B42 B43

要求旋转后的数据如下：

R13 R23 R33 R43
G13 G23 G33 G43
B13 B23 B33 B43

R12 R22 R32 R42
G12 G22 G32 G42
B12 B22 B32 B42

R11 R21 R31 R41
G11 G21 G31 G41
B11 B21 B31 B41

注意：以上空格间开的均代表一个 BYTE 型的数据；旋转前后都是在同一块连续的buffer中。

gxqcn

这个问题的最大困难在于内存空间的紧张，
旋转前后的读与写会发生 overlap，很难实现。

这是我工作中新近碰到的一个难题，
在论坛里抛出来，看看大家可否有此类似经验？
或是否有资料或资源共享？
当然也欢迎高手多多指点。。。

mathe

其实这个基本上就是相当于矩阵原地旋转问题,过去在CSDN中讨论过的.可以使用O(1)的辅助空间来完成的.

gxqcn

可否帮忙找找链接？

这应该是个早已解决的问题，只是我以前没有积累。
我自己也在搜索中。。。

gxqcn

参考了一些网上资料，而后再加上自己的一些优化，
得到如下代码，测试通过：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. void output( int *a, int w, int h )
   
5. {
   
6.     int i, j;
   
7.     for ( i=0; i<h; ++i )
   
8.     {
   
9.         for( j=0; j<w; ++j )
   
10.         {
    
11.             printf( "%d ", a[i*w+j] );
    
12.         }
    
13.         printf( "\n" );
    
14.     }
    
15.     printf( "\n" );
    
16. }
    
17. 
    
18. void transf( int *a, int w, int h )
    
19. {
    
20.     int k, pos, t;
    
21.     div_t xy;
    
22. 
    
23.     for( k=(w*h)>>1; 0!=k--; )
    
24.     {
    
25.         pos = k;
    
26.         do
    
27.         {
    
28.             xy = div( pos, w  );
    
29.             pos = (w-1-xy.rem)*h + xy.quot;
    
30.         } while( pos > k );
    
31. 
    
32.         if( pos == k )
    
33.         {
    
34.             t = a[k];
    
35.             do
    
36.             {
    
37.                 xy = div( pos, w  );
    
38.                 pos = (w-1-xy.rem)*h + xy.quot;
    
39.                 a[pos] ^= t ^= a[pos] ^= t;
    
40.             } while( pos != k );
    
41.         }
    
42.     }
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.     int w=5, h=9, i, j;
    
48.     int *a = malloc( w*h*sizeof(int) );
    
49. 
    
50.     for( i=0; i<h; ++i )
    
51.     {
    
52.         for( j=0; j<w; ++j )
    
53.         {
    
54.             a[i*w+j]=i*w+j+1;
    
55.         }
    
56.     }
    
57. 
    
58.     output( a, w, h );
    
59.     transf( a, w, h );//旋转
    
60.     output( a, h, w );
    
61. 
    
62.     free( a );
    
63. 
    
64.     return 0;
    
65. }

复制代码

该算法的优点是无须大量临时空间，
缺点是读写的 cache 命中率不高（可以进一步改进成分块分区域进行旋转）。

该算法针对本主题的图像旋转依然适用，只是坐标变换法则更麻烦一点而已。

winxos

在坐标变换中，一般旋转是乘以旋转因子（一个特殊矩阵）得到的，不知道是不是gxqcn所寻找的？
请参考 http://17de.com/library/d3d_6im/d3dim6_5.htm

gxqcn

旋转因子是为了解决任意角度图像的旋转，
对于非90°整数倍的旋转，还涉及到插值运算等算法。

这与本主题讨论的重点是不一样的。

winxos

原帖由 gxqcn 于 2009-4-30 16:38 发表
旋转因子是为了解决任意角度图像的旋转，
对于非90°整数倍的旋转，还涉及到插值运算等算法。

这与本主题讨论的重点是不一样的。

90°就是一个特例啊？
你的意思是说90°可以有更简洁的方法？
好像我以前用下标运算也做过。

gxqcn

这个算法的核心思想是将一个交换环一次性处理。

我debug了一下，有些环非常长，甚至等于矩阵的元素总数，
也就是说全部交换环仅一个就完成了重排：
w=2, h=2;
w=2, h=5;
w=2, h=6;
w=2, h=9;
w=2, h=14;
w=2, h=18;
w=3, h=2;
w=3, h=6;
w=3, h=10;
w=3, h=14;
w=6, h=2;
w=6, h=10;
w=6, h=13;
w=6, h=17;
w=6, h=18;
w=7, h=10;
w=7, h=18;
w=10, h=6;
w=10, h=13;
w=10, h=18;
w=11, h=2;
w=11, h=6;
w=14, h=2;
w=14, h=9;
w=14, h=17;
w=15, h=10;
w=15, h=18;
w=18, h=2;
w=18, h=6;
w=18, h=9;
w=18, h=10;
w=19, h=10;
（以上是 $1 < w, h <= 20$ 范围内的单交换环之解）

大家看看可否归纳出一点规律？