2009年12月18日 星期五 16:38
Dear all, 有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形?就是类似 于Linux下的3D桌面转动时候的效果,我想用2D模拟一个这种效果, 我尝试过很 多,但效率都差强人意。 我目前的做法是从网上找的一些投影原理,按照角度来 算,然后一个像素一个像素的取,但是效率极差,基本都到O(n^2)了,请问有没 有更好的算法? 把这个问题简化一下:就是要把一个矩形变成一个等腰梯形,就像GIMP中 Perspective Transformation Matrix 那样。 Thanks Kermit
2009年12月18日 星期五 18:08
On Fri, 2009-12-18 at 01:38 -0700, Kermit Mei wrote: > Dear all, > > 有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形?就是类似 > 于Linux下的3D桌面转动时候的效果,我想用2D模拟一个这种效果, 我尝试过很 > 多,但效率都差强人意。 我目前的做法是从网上找的一些投影原理,按照角度来 > 算,然后一个像素一个像素的取,但是效率极差,基本都到O(n^2)了,请问有没 > 有更好的算法? > > 把这个问题简化一下:就是要把一个矩形变成一个等腰梯形,就像GIMP中 > Perspective Transformation Matrix 那样。 哎,这个问题貌似没这么简单。下午搜索了很多资料,这是个矩阵变换的问题,看 来我得回去好好研究一下线性代数了,呵呵。
2009年12月20日 星期日 12:43
2009/12/18 Kermit Mei <kermit.mei在gmail.com>: > On Fri, 2009-12-18 at 01:38 -0700, Kermit Mei wrote: >> 有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形?就是类似 >> 把这个问题简化一下:就是要把一个矩形变成一个等腰梯形,就像GIMP中 >> Perspective Transformation Matrix 那样。 > > 哎,这个问题貌似没这么简单。下午搜索了很多资料,这是个矩阵变换的问题,看 > 来我得回去好好研究一下线性代数了,呵呵。 矩阵变换其实就是一个仿射变换或者射影变换: 在仿射变换中 X1 = A * X + C X是初始点,X1是变到的点,都是二维向量,A是一个2x2的非退化矩阵,C是位移向量。 射影变换复杂一些,每个点可以用三个分量表示,变换矩阵A是3x3的非退化矩阵,变换式为 X1 = A * X 三位向量的含义:设X = (x, y, z)' ,那么 z!=0时 X就代表点(x/z, y/z)。 希望能有所帮助。
2009年12月20日 星期日 22:55
On Sun, 2009-12-20 at 12:43 +0800, guo yixuan wrote: > 2009/12/18 Kermit Mei <kermit.mei在gmail.com>: > > On Fri, 2009-12-18 at 01:38 -0700, Kermit Mei wrote: > >> 有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形?就是类似 > >> 把这个问题简化一下:就是要把一个矩形变成一个等腰梯形,就像GIMP中 > >> Perspective Transformation Matrix 那样。 > > > > 哎,这个问题貌似没这么简单。下午搜索了很多资料,这是个矩阵变换的问题,看 > > 来我得回去好好研究一下线性代数了,呵呵。 > > 矩阵变换其实就是一个仿射变换或者射影变换: > 在仿射变换中 X1 = A * X + C > X是初始点,X1是变到的点,都是二维向量,A是一个2x2的非退化矩阵,C是位移向量。 > > 射影变换复杂一些,每个点可以用三个分量表示,变换矩阵A是3x3的非退化矩阵,变换式为 X1 = A * X > 三位向量的含义:设X = (x, y, z)' ,那么 z!=0时 X就代表点(x/z, y/z)。 > > 希望能有所帮助。 恩,谢谢提示! 我再学习一下,现在才意识到线代功底不行关键时候是要掉链子 的:)
2009年12月22日 星期二 16:14
2009/12/18 Kermit Mei <kermit.mei在gmail.com>: > Dear all, > 有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形?就是类似 > 于Linux下的3D桌面转动时候的效果,我想用2D模拟一个这种效果, 我尝试过很 > 多,但效率都差强人意。 准确的说,这个问题的运算目前都是用 GPU 完成的。因为大量的并行运算与浮点运算是GPU的强项。 简单的说,只讲究效率不讲究效果的话这个问题其实可以非常简单:你只要按比例抽取一定像素走就可以。当然,如果你需要消除锯齿和平滑缩放的话,估计是非GPU不可的,建议直接找3D相关函数完成吧。
2009年12月22日 星期二 16:38
On Tue, 2009-12-22 at 16:14 +0800, pan shizhu wrote: > 2009/12/18 Kermit Mei <kermit.mei在gmail.com>: > > Dear all, > > 有没有什么高效的算法可以按像素把一个矩形转换成一个等腰梯形?就是类似 > > 于Linux下的3D桌面转动时候的效果,我想用2D模拟一个这种效果, 我尝试过很 > > 多,但效率都差强人意。 > > 准确的说,这个问题的运算目前都是用 GPU 完成的。因为大量的并行运算与浮点运算是GPU的强项。 > > 简单的说,只讲究效率不讲究效果的话这个问题其实可以非常简单:你只要按比例抽取一定像素走就可以。当然,如果你需要消除锯齿和平滑缩放的话,估计是非GPU不可的,建议直接找3D相关函数完成吧。 我要拿到板子上跑,别说GPU,就连CPU的效率都很底,比现在的2440慢多了。 所 以希望按照一定比例抽取像素…… 但是我分析的效率最高的算法还是O(n^2)的,一直想找一个O(n)的……如果屏幕宽度 是320x240,那么每次图片大小都是320x240=76800。 Thanks B.R Kermit
2009年12月22日 星期二 18:53
2009/12/22 Kermit Mei <kermit.mei在gmail.com>: > 但是我分析的效率最高的算法还是O(n^2)的,一直想找一个O(n)的……如果屏幕宽度 > 是320x240,那么每次图片大小都是320x240=76800。 你是说的O(n^2)指的是 76800^2么? 如果是这样的话,抽取算法确实是 O(n)的,假设你把 320x240 的图片变成 160 为顶边,320为底边,240为高的等腰梯形。那么你把第一行每两个点抽取一个点就可以了。剩下的可以依此类推,按比例抽掉一部分点,最后一行就还是320点不变,完工。 这样出来的图像效果是不好的,不过如果仅仅是用于动画的话,问题也不大。对于诸如两三百兆的嵌入式CPU,320x240最优状态达到5帧是可能的。――当然,如果你对动画的平滑度要求更高的话,那真的没办法了。毕竟你CPU性能摆那里在
2009年12月23日 星期三 09:45
On Tue, 2009-12-22 at 18:53 +0800, pan shizhu wrote: > 2009/12/22 Kermit Mei <kermit.mei在gmail.com>: > > 但是我分析的效率最高的算法还是O(n^2)的,一直想找一个O(n)的……如果屏幕宽度 > > 是320x240,那么每次图片大小都是320x240=76800。 > > 你是说的O(n^2)指的是 76800^2么? 不是,是320*240,一个for遍历320中要抽取的项,另一个嵌套在这个for里,遍历 240中要抽取的像素。 for(遍历要抽取的列) { for(遍历该列中每一个像素) { 画这个点(x,y) } } 我幻想得到一个遍历320次就能搞定的算法……貌似不合乎逻辑。 > 如果是这样的话,抽取算法确实是 O(n)的,假设你把 320x240 的图片变成 160 > 为顶边,320为底边,240为高的等腰梯形。那么你把第一行每两个点抽取一个点就可以了。剩下的可以依此类推,按比例抽掉一部分点,最后一行就还是320点不变,完工。 > > 这样出来的图像效果是不好的,不过如果仅仅是用于动画的话,问题也不大。对于诸如两三百兆的嵌入式CPU,320x240最优状态达到5帧是可能的。――当然,如果你对动画的平滑度要求更高的话,那真的没办法了。毕竟你CPU性能摆那里在 我的主频不到200兆……
2009年12月23日 星期三 10:47
2009/12/23 Kermit Mei <kermit.mei在gmail.com>: > 不是,是320*240,一个for遍历320中要抽取的项,另一个嵌套在这个for里,遍历 > 240中要抽取的像素。 > > for(240) { > for(320) { > 画这个点(x,y) > } > } > > 我幻想得到一个遍历320次就能搞定的算法......貌似不合乎逻辑。 从你的这个描述来看,你只遍历了一次,而不是320次。正确的定义是:把所有点访问一次,算作一次遍历。
2009年12月23日 星期三 10:57
On Wed, 2009-12-23 at 10:47 +0800, pan shizhu wrote: > 2009/12/23 Kermit Mei <kermit.mei在gmail.com>: > > 不是,是320*240,一个for遍历320中要抽取的项,另一个嵌套在这个for里,遍历 > > 240中要抽取的像素。 > > > > for(240) { > > for(320) { > > 画这个点(x,y) > > } > > } > > > > 我幻想得到一个遍历320次就能搞定的算法......貌似不合乎逻辑。 > > 从你的这个描述来看,你只遍历了一次,而不是320次。正确的定义是:把所有点访问一次,算作一次遍历。 的确只遍历了一次,但单从代码上看,我算的是两个嵌套的for循环,这样下来粗 略地估计就是O(n^2)了。 要是能比这个再高效一些就好了……
2009年12月23日 星期三 11:04
2009/12/23 Kermit Mei <kermit.mei在gmail.com>: > > 的确只遍历了一次,但单从代码上看,我算的是两个嵌套的for循环,这样下来粗 > 略地估计就是O(n^2)了。 要是能比这个再高效一些就好了…… 算法复杂度的标记不是你这样算的。作为图像处理来说,一个点遍历一遍,你这就是 O(n) 算法。 如果对于每一个点,都需要把整个图像遍历一遍。这才是 O(n^2)算法,它的复杂度是基于 76800*76800。
2009年12月23日 星期三 11:13
On Wed, 2009-12-23 at 11:04 +0800, pan shizhu wrote: > 2009/12/23 Kermit Mei <kermit.mei在gmail.com>: > > > > 的确只遍历了一次,但单从代码上看,我算的是两个嵌套的for循环,这样下来粗 > > 略地估计就是O(n^2)了。 要是能比这个再高效一些就好了…… > > 算法复杂度的标记不是你这样算的。作为图像处理来说,一个点遍历一遍,你这就是 O(n) 算法。 > > 如果对于每一个点,都需要把整个图像遍历一遍。这才是 O(n^2)算法,它的复杂度是基于 76800*76800。 恩。我在猜想,即便是Frame Buffer最底层的操作,拿到一张图片要画出来也应该 是这个效率吧? 它至少也要把所有像素遍历一次才行呐。
Zeuux © 2024
京ICP备05028076号