[讨论]给大家出一个算法方面的问题(页 1) - C语言论坛 - C图形专区 - 编程论坛

RockCarry 发表于 2007-8-8 21:10

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

简单的说，就是，图像的旋转问题，要求能做到90度的旋转，并且要求对内存的占用最小。更加精确的描述如下： 1. 对原始图像IMAGE，其宽度分别为w和h，其图像数据存放在pdata所指向的缓冲区中，以一维的形式按行顺序存放，可以用一个三元组来描述这个图像 IMAGE(w, h, pdata); 2. 要求对IMAGE进行顺时针90度旋转的操作，并且使用最少的内存 这个问题提出的背景是，在一款数码产品上，可用内存只有20MB，当显示2000x2000x24bit的位图的时候，就会占用12MB左右的内存，如果使用常规的图片旋转算法，即另外创建一个同样大小但宽高相反的位图，然后计算旋转后的像素点到新的位图中。这样就会出现内存不足而无法旋转的问题。 传统的算法在理解和实现上都非常容易，但是要求申请与原位图同样大小的缓冲区，导致在空间上的开销太大。 大家不要小看这个问题，我仔细思考过，要在这个问题上节省空间真的很难。从理论上讲，这个问题是有解的，而且可以完全做到不申请任何额外的内存空间，即只对原始图像的pdata所指向的缓冲区进行操作，但是要写成通用性的代码的话，我现在都还没有想到一个好的算法。关键是要保证操作过程中图像数据不会因为被新的图像数据覆盖而丢失掉。并且还要保证旋转后的图像数据也是按行顺序存放。 想了半天，感觉如果不借助大量额外的缓冲区，这个问题似乎无解。 大家一起讨论下，帮忙想想办法。 我刚开始想到一个办法就是对矩阵做一次转置处理，然后再做一次水平翻转就可以了，但是这个算法只适用于宽高相等的位图。对于宽高不等的图像，要考虑更多的问题。

奔跑的鸟 发表于 2007-8-8 21:20

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

RockCarry 发表于 2007-8-8 21:25

举个例子： 原始图像 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 };

RockCarry 发表于 2007-8-8 21:28

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

RockCarry 发表于 2007-8-8 21:31

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

jig 发表于 2007-8-8 22:32

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 兄的要求，只是在实现的过程中，要在优化优化，毕竟在嵌入试上跑要讲求效率 祝成功~！
[align=right][color=#000066][此贴子已经被作者于2007-8-8 23:18:40编辑过][/color][/align]

RockCarry 发表于 2007-8-8 22:49

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

jig 发表于 2007-8-8 23:20

我专业表达能力可能欠缺，所以举例子把你小型的按实际运作情况描述了一下，你看看吧，不知道说清楚了吗。 补充一下，在互换时应首先检查元素已所在处是否是已经被置换OK的 比如a (0, 0)->(2,0) 先检查标记表的(0,0)处，发现是0位被标记才继续进行，这样整个循环才能接上。
[align=right][color=#000066][此贴子已经被作者于2007-8-8 23:38:28编辑过][/color][/align]

一笔苍穹 发表于 2007-8-9 08:38

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

jig 发表于 2007-8-9 13:18

可以的，我知道你的顾虑，最开始的时候我也想过，当时我认为应该建立一个，以较大参数为准的方形标记表，比如上面例子应该是 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 
[align=right][color=#000066][此贴子已经被作者于2007-8-9 13:22:24编辑过][/color][/align]

kk4868 发表于 2007-8-9 13:20

一个原始图片，宽为W，高为H，可以每次置换H个点，分W-1次完成操作，我试验了一个7*4的矩阵是可行的 但是置换的规律太难找了，呵呵 这样只需要增加一个像素的临时空间
[align=right][color=#000066][此贴子已经被作者于2007-8-9 13:32:53编辑过][/color][/align]

一笔苍穹 发表于 2007-8-9 14:29

<DIV class=quote>以下是引用kk4868在2007-8-9 13:20:11的发言： 一个原始图片，宽为W，高为H，可以每次置换H个点，分W-1次完成操作，我试验了一个7*4的矩阵是可行的 但是置换的规律太难找了，呵呵 这样只需要增加一个像素的临时空间 </DIV>
呵呵，我想明白了。不过这样空间是省了，但实现可能太慢了。

kk4868 发表于 2007-8-9 16:52

其实也不是太慢，毕竟都是对内存的数据移动吗，而且是在一个一维数组内。很少的点要两次移动。 感觉速度还可以吧。 就是规律我没有总结出来，老董总结出来了？详细说说啊

一笔苍穹 发表于 2007-8-10 08:34

规律还在想，孙靖那套的规律好找些，嘿嘿。

RockCarry 发表于 2007-8-10 19:20

Jig的算法时间复杂度还是有点高，而且这里要求处理的数据量很大。2440的主频为400MHz，如果使用传统算法，在旋转1000x1000大小的图片就需要2s左右的时间。如果采用Jig的算法，在处理更大的图片时，则会需要更多的时间，恐怕给用户的感觉就是像死机一样了。 还来我想了，用临时文件来存放大量的数据，临时文件将会保存到SD卡上，这样文件的长度可以说是不受限制。旋转时，先把结果数据写到临时文件，然后再从临时文件读回数据。想来似乎可行，后来试验了一下，发现SD卡的读写速度跟不上，目前SD卡的读写速度能到达1MB/s（这个已经是我经过许多优化才取得的成果），这样算下来，旋转一个图片消耗在文件读写上的时间就需要20s以上，这是无法接受的。

RockCarry 发表于 2007-8-10 19:21

到目前为止，还是没有找到更好的旋转算法。这个算法对时间和空间的要求都比较高。

RockCarry 发表于 2007-8-10 19:49

不过这个问题到后面有了新的解决办法。 其实项目需要完成的是一个图片浏览器，能够支持 JPEG 和 BMP 图片的浏览。BMP 的显示可以借助 WinCE API 来实现，JPEG 图片的解码则选用了 Independent JPEG Group 的一个 JPEG Codec。数码产品的 LCD 屏只有 480x272 大小。浏览器中，提供了图片原始大小、图片缩放、旋转等功能，在图片不能完全显示时，给出水平滚动条和垂直滚动条供用户拖动。在调用 JPEG 解码库时，根据图片的原始大小创建了一个位图对象，然后将 JPEG 图片解码到这个位图对象中。因此对于大尺寸的 JPEG 图片，就需要占用很大的内存。然而，实际的 LCD 只有 480x272 大小。因此，我们打算，在 JPEG 解码的时候，就对尺寸的图片进行缩放，缩放到合适的尺寸，使其既能保证内存足够，又能保证显示效果。因为在浏览大尺寸图片时，其实图片都要经过缩放处理（都是缩小），因此，对于大尺寸的图片在解码时就进行缩放处理，几乎不过影响用户浏览图片的效果，只会在图片原始大小，或者放大时，会有图片质量上的损失。 根据这个思路，我们将图片浏览器可用的内存空间定为8MB，其中4MB用于位图的存放，另外4MB则是用于旋转等处理的临时缓冲区。在遇到大图片时，先判断其所需要的内存是否大于4MB，如果是，就在解码时进行缩放处理。然后，剩下的问题就已经不是问题了。 也不必去研究前面的算法如何实现。当然，工程上的实现往往都是这样，尽量避开技术难点，采用最直接、最简单的办法解决问题。 然而，如果是单纯将这个问题当作算法来研究的话，我认为还是有价值的。我也会继续思考这个问题的解决办法。大家也帮忙想想。

jig 发表于 2007-8-10 23:11

我也先过啦，似乎在效率上是很难兼顾 开始我想看是不是直接采用按转换规律直接在屏幕上打点，可我不知道你的屏幕型号，可液晶一般是慢速器件，也许那样在旋转时其实就是重绘过程，这样图片的显示就有个过程（可能是慢慢刷出来的），我想这样也不能满住要求 至于以文件形式，我想也更不可能SD卡的读写。。。。。。黑嘿。 要不就扩内存吧，看能不能控制一下成本。

hjj1123 发表于 2007-8-11 01:14

我没有看动JIG的算法。自己想了个，大家看看行不。这个办法理论上非常好，可是我有个地方没解决，内存开销回比较大，但是能满足LZ的要求。 原始图像 a b c d e f g h i j k l int w1 = 4; int h1=- 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 w2 = 3; int h2 = 4; BYTE pdata[] = { i, e, a, j, f, b, k, g, c, l, h, d }; JIG也说过了，转换的规律是 X1=y0; Y1=w2-1-x0; (x0,y0,x1,y1分别是转换前后的坐标，没有考虑字长),称为公式1 原始图像: |(0,0),(0,1),(0,2),(0,3)| |(1,0),(1,1),(1,2),(1,3)| |(2,0),(2,1),(2,2),(2,3)| int w1 = 4; int h1=- 3; 旋转后的图像: |(2,0)/ (0,0),(1,0)/ (0,1),(0,0)/ (0,2)| |(2,1)/ (1,0),(1,1)/ (1,1),(0,1)/ (1,2)| |(2,2)/ (2,0),(1,2)/ (2,1),(0,2)/(2,2)| |(23)/ (3,0),(1,3)/ (3,1),(0,3)/(3,2)| int w2 = 3;int h2 = 4; /前面是转换后的数据在转换前数组中的坐标，/后是在新数组中的坐标； 由于BYTE pdata[] = { a, b, c, d, e, f, g, h, i, j, k, l }一维的形式按行顺序存放，所以位置需要转换一下， 公式为： x2=(x1*w2+y1)/w1; y2=(x1*w2+y1)-y2*w1; 称为公式2 （0,0）(原图像中的位子)---公式1---(0,2)（现在图像中的位子）-- 公式2---(0,2) （原来图像中被占用的数据位子，也是第二次原图像中的位子）----公式1--(2,2) （第二次现在图像中的位子） -- 公式2---(2,0)（依次类推……） ---公式1-(0,0) （依次类推……） 注意现在开始循环了。这是我刚开始时没想到的，我以为它会持续下去直到完成。 0 1 2 0 |(2,0)，，（0,0）| 1 | ，， | 2 | ，，(0,2)| 3 | ，， | 这是一次循环所填的点，在做几次循环就可以完成整个数组填充。现在麻烦有两个： 1：如何判断已经完成整个数组填充？ 2：起始点如何选择？ 对于第一个问题可以设置一个变量，在每填充一次计一次数，让它和总数比较，用以判断是否完成。这个应该难度不大。第二个问题我还没有解答，我试过数组的对角线，边线上的点的坐标作为起始点，但是遗憾没有完全包含整个数组。想到了最笨的办法，就是将每个点都假设为起始点，建立一个数组START[4000000][2] 刚好是LZ剩下的八M空间，元素为(0,0),(0,1),(0,2)……….(1998,1999),(1999,1999),然后进行前面描述的循环，每填充一个点，便在START数组中删掉相应坐标，完成一次循环后在START数组中拿第二个点做起始点开始下一次循环，同时删掉第一个起始点，直到START数组为空。
这是没办法的办法，如果能找到办法提取所有的起始点坐标那就完美了，最多需要几十K的空间，那像这笨办法要那么多的空间。 有不妥的地方请大家明示！！！

RockCarry 发表于 2007-8-11 13:56

大概懂了 hjj1123 的算法原理。即找一个起始点，计算出其旋转以后的坐标，根据这个坐标，计算出旋转后在数组中的实际偏移地址，然后将这个地址上的元素与起始点的元素进行交换。然后再对起始点进行处理，此时起始点保存的数据实际上是前面交换过来的数据，这个数据在原始图像中的坐标也可以算出来，然后来根据这个坐标计算出旋转以后的坐标，然后再如此重复。

页: [1] 2

编程论坛's Archiver

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