[讨论]给大家出一个算法方面的问题

简单的说，就是，图像的旋转问题，要求能做到90度的旋转，并且要求对内存的占用最小。更加精确的描述如下：
1. 对原始图像IMAGE，其宽度分别为w和h，其图像数据存放在pdata所指向的缓冲区中，以一维的形式按行顺序存放，可以用一个三元组来描述这个图像 IMAGE(w, h, pdata);
2. 要求对IMAGE进行顺时针90度旋转的操作，并且使用最少的内存

这个问题提出的背景是，在一款数码产品上，可用内存只有20MB，当显示2000x2000x24bit的位图的时候，就会占用12MB左右的内存，如果使用常规的图片旋转算法，即另外创建一个同样大小但宽高相反的位图，然后计算旋转后的像素点到新的位图中。这样就会出现内存不足而无法旋转的问题。
传统的算法在理解和实现上都非常容易，但是要求申请与原位图同样大小的缓冲区，导致在空间上的开销太大。

大家不要小看这个问题，我仔细思考过，要在这个问题上节省空间真的很难。从理论上讲，这个问题是有解的，而且可以完全做到不申请任何额外的内存空间，即只对原始图像的pdata所指向的缓冲区进行操作，但是要写成通用性的代码的话，我现在都还没有想到一个好的算法。关键是要保证操作过程中图像数据不会因为被新的图像数据覆盖而丢失掉。并且还要保证旋转后的图像数据也是按行顺序存放。
想了半天，感觉如果不借助大量额外的缓冲区，这个问题似乎无解。
大家一起讨论下，帮忙想想办法。
我刚开始想到一个办法就是对矩阵做一次转置处理，然后再做一次水平翻转就可以了，但是这个算法只适用于宽高相等的位图。对于宽高不等的图像，要考虑更多的问题。

分成四等份,先把两边的转置并放到空余缓存中,清除原缓存中的图象,把剩下的部分转置后放到新释放出来的缓寸中....图象处理我不懂,也不知道这样行不行,只是个想法,表打我

举个例子：
原始图像
a b c d
e f g h
i j k l
int w = 4;
int h - 3;
BYTE pdata[] = { a, b, c, d, e, f, g, h, i, j, k, l };

旋转后的图像
i e a
j f b
k g c
l h d
int w = 3;
int h = 4;
BYTE pdata[] = { i, e, a, j, f, b, k, g, c, l, h, d };

实现如下的函数
void RotBitmap(BYTE *pdata, int *w, int *h);
要求空间上的开销尽量小。

这个跟图像处理关系不大，主要是看如果移动pdata中的元素。

RockCarry 兄我想到一个办法，不过还是要开辟额外的内存来标记哪些点已经被放置成功，

他要额外消耗的内存，比如你的图片 高 H， 宽 W

那么额外需要开辟 H*W /8 个字节。

2000x2000 / 8 = 500000 字节；换算成 M才0.4M多

所以我想也许可以满足你的要求

我们首先还是以你上面给出的例子进行说明：

a b c d
e f g h
i j k l
int w = 4;
int h = 3;
BYTE pdata[] = { a, b, c, d, e, f, g, h, i, j, k, l };

那么我们对待他的的时候，可以把 pdata[]数组看成是2维的，在提取数据的时候，自己转化就是了。

那么我们来看看他转化后的情况，来找出规律

i e a
j f b
k g c
l h d
int w = 3;
int h = 4;
BYTE pdata[] = { i, e, a, j, f, b, k, g, c, l, h, d };



这样我们得出的规律表是

a: (0,0) -> (2,0)
b: (1,0) -> (2,1)
c: (2,0) -> (2,2)
d: (3,0) -> (2,3)

e: (0,1) -> (1,0)
f: (1,1) -> (1,1)
g: (2,1) -> (1,2)
h: (3,1) -> (1,3)

i: (0,2) -> (0,0)
j: (1,2) -> (0,1)
l: (2,2) -> (0,2)
k: (3,2) -> (0,3)

他的规律很显而易见，就是 原来的 X变Y， 原来的Y由W-1-Y得到新的X。

然后我们建立一个标记表 ，W*H/8；在这里就是 3*4/8 = 1...4 也就需要两个字节来标记每个点的置换情况。

为了发表表达，我们把这个表也建立成2维的与原图对应，（当然在使用中应该开辟一个连续数组只是在用的时候在2维坐标和1维坐标之间相互转化就是了，当然这里是位操作）


标记表：(标记的2维坐标应该是转换后的情况，而且当然是以位来标记的)
0 0 0
0 0 0
0 0 0
0 0 0


好，我们来看整个是怎么云做的。

1. 首先看第一个元素 a (0,0) -> (2.0)
先查看 标记表的(2,0)位置，为0，说明没被置换。先记录，c元素原始位置 (2.0)那将a,c元素互换并操作标记表。这之后情况是

置换表
c b a d
e f g h
i j k l

标记表
0 0 1
0 0 0
0 0 0
0 0 0

2.查看C本来应该在的位置是否和现在相符，原本 c: (2,0) -> (2,2),而现在c在(0,0)
那么重复上面1过程，他与现在(2,2)处的k元素，互换，并记录下k元素的原始位置，这样后的结果是

置换表
k b a d
e f g h
i j c l

标记表
0 0 1
0 0 0
0 0 1
0 0 0

3.经过上面的步骤，最后将形成小范围的互换成功。就按上面继续，k将与i互换，而i将恰好被换到他本该到的(0,0)处。这样后一个小范围循环结束，最后的结果

置换表
i b a d
e f g h
k j c l

标记表
1 0 1
0 0 0
1 0 1
0 0 0

4.而后，我们将进行第二个元素，b的呼唤，经过一个循环过程，又将是小范围互换成功

简要经过 b<->g g<->j j<->e 最终e将停在正确位置，结果

置换表
i e a d
j f b h
k g c l

标记表
1 1 1
1 0 1
1 1 1
0 0 0

5.然后进行现在第3个元素a,可一检查标记表，他已经置换OK拉，所以，接下来就是第4个元素d,在经过以上步骤就可以实现全部的元素置换成功。



这个算法介绍完毕，现在补充一句 额外开辟的内存是 W*H/8 +2*int 因为要记录被置换元素的原始坐标。

我想这个算法应该可以满足RockCarry 兄的要求，只是在实现的过程中，要在优化优化，毕竟在嵌入试上跑要讲求效率

祝成功~！

[此贴子已经被作者于2007-8-8 23:18:40编辑过]

Jig能否精确的刻画一下你的算法。

我专业表达能力可能欠缺，所以举例子把你小型的按实际运作情况描述了一下，你看看吧，不知道说清楚了吗。

补充一下，在互换时应首先检查元素已所在处是否是已经被置换OK的

比如a (0, 0)->(2,0)

先检查标记表的(0,0)处，发现是0位被标记才继续进行，这样整个循环才能接上。

[此贴子已经被作者于2007-8-8 23:38:28编辑过]

JIG的方法我看了，但这样好像只适用于W=H的情况吧，也类似于先矩阵变换再翻转啊，如果图的宽高不同好像不行啊？

可以的，我知道你的顾虑，最开始的时候我也想过，当时我认为应该建立一个，以较大参数为准的方形标记表，比如上面例子应该是

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

后来想同了其实不用，你自己想想：一旦在检查标记表的时候发现没有此坐标就认为，此点没有被置换成功，继续进行置换工作，这样就避免了开辟过多内存。

注意，标记表应该是被置换后的2维形式，就按上面举的例子所以应该是

0 0 0
0 0 0
0 0 0
0 0 0

[此贴子已经被作者于2007-8-9 13:22:24编辑过]